Revision as of 19:09, 22 April 2010 by Huang94 (Talk | contribs)

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.

Butterfly model.jpg

Pipeline of the Solution Method Schematic Rep.jpg

Algorithm

Univariate Polynomial Equations:

                                                            Algorithm Univariate.jpg

Multivariate Polynomial Equations:

                                                            Algorithm Multivariate.jpg

Theorems

                                       Theorems1.png

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 global match results and robustness analysis of the matches are plotted below.

                              Butterflyfit.png

To illustrate how the length of the curve being approximated by the point cloud affect the accuracy, we picked a segment of the butterfly contour curve and incrementally shrank the size of this contour. For each size increment, we picked 20 points on the curve segment and added Gaussian noise with standard deviation equal 0.05. Each experiment was repeated 10 times. The accuracy of the results, measured by the average Euclidean distance between the registered points and the butterfly contour, is plotted below. Some sample results are also given after that. One can see that the accuracy begins to degrade when the part of the curve being registered does not fit well with the implicit polynomial representation.

                                                                    Localmap.png Localsample.png

References

[1] M. Boutin J. Zhang, S. Huang, Effective curve registration using a novel solution method for overdetermined systems of polynomial equations', In IS&T/SPIE joint symposium, Computational Imaging IV conference, San Jose, CA, Jan. 2009.

[2] Ji Zhang, A solution method for zero dimensional polynomial equation systems and a pose-free framework for the robust solution of the structure from motion problem, Ph.D. Thesis, Purdue University, Apr. 2009

Alumni Liaison

Followed her dream after having raised her family.

Ruth Enoch, PhD Mathematics