Fitting discrete polynomial curve and surface to noisy data

摘要

Fitting geometric models such as lines, circles or planes is an essential task in image analysis and computer vision. This paper deals with the problem of fitting a discrete polynomial curve to given 2D integer points in the presence of outliers. A 2D discrete polynomial curve is defined as a set of integer points lying between two polynomial curves. We formulate the problem as a discrete optimization problem in which the number of points included in the discrete polynomial curve, i.e., the number of inliers, is maximized. We then propose a robust method that effectively achieves a solution guaranteeing local maximality by using a local search, called rock climbing, with a seed obtained by RANSAC. We also extend our method to deal with a 3D discrete polynomial surface. Experimental results demonstrate the effectiveness of our proposed method.