A Solution Method For Zero-Dimensional Polynomial Equation System
Motivation
Consider the problem of curve registration, that is, finding the rotation and translation that best maps (i.e., registers) a cloud of points onto a template object, as described on the right.
We first approximate the curve defined by the contour of the template object by an implicit polynomial equation. This yields a bivariate polynomial equation p(x,y) = 0 whose solution set approximates the template contour.
Let (x_i,y_i) , i=1, ..., N be the points of the point cloud. We are looking for the rotation R and the translation T such that p((xi, yi)R + T) = 0 for all i = 1, ..., N. Then we have an overdetermined polynomial equation system with noisy coefficient, which contains N equations and unknown variables R and T. We need to solve this overdetermined polynomial system.
Pipeline of the Solution Method
Algorithm
Univariate Polynomial Equations:
Multivariate Polynomial Equations:
Theorems
Numerical Results
Picking 20 points along the contour of the butterfly and rotating and translating these 20 points using R = [0.6 -0.8; 0.8 0.6], and T = (-1, -1). Then registering the resulting 20 points back onto the original butterfly using the proposed method. To demonstrate how the method allows us to deal with noisy observations of the template boundary, we added an increasing amount of Gaussian noise (with standard deviation between 0.01 and 0.2) to the x and y coordinates of the 20 points, repeating each experiment 10 times, and recorded the average Euclidean distance between the registered points and the original curve every time. The results are plotted below.
