Fitting discrete polynomial curve and surface to noisy data (Q499719)

The problem of fitting geometric models (line, circles, and planes) leads to many applications in image analysis and computer vision, such as object recognition, shape approximation and image segmentation. One issue of the problem is that of using discrete models when the discrete spaces are discussed. Classically, such models are defined as the result of discretization locally applied to a continuous model. The goal of the paper is to develop a technique for discrete polynomial curve and surface fitting to a given set of discrete points, accepting the presence of outliers. A 2D discrete polynomial curve supposes a set of integer points lying between two polynomial curves. The 2D discrete polynomial curve fitting problem is described as a discrete optimization problem where the number of inliers (data points consistent with a given model with allowing some error threshold) is maximized. The solution is proposed as a combination of the RANSAC method (random sample consensus), which maximizes the number of inliers working regardless the fraction of outliers, with a local search called rock climbing, the method achieving a solution that guarantees local maximality. The authors also extend the proposed method for the 3D discrete polynomial surface fitting problem and prove the efficiency and the robustness through some experimental results for both the 2D and 3D cases.