| Line 1: | Line 1: | ||
| − | == A Solution Method For Zero-Dimensional Polynomial Equation System == | + | == A Solution Method For Zero-Dimensional Polynomial Equation System == |
'''Motivation''' | '''Motivation''' | ||
| Line 7: | Line 7: | ||
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. | 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. | + | 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. |
</div> <div style="width: 30%; float: right;"> | </div> <div style="width: 30%; float: right;"> | ||
[[Image:Butterfly model.jpg|250px]] | [[Image:Butterfly model.jpg|250px]] | ||
| − | </div> <div style="width: 100%; float: left;"></div> | + | </div> <div style="width: 100%; float: left;"></div> |
| + | '''Pipeline of the Solution Method''' [[Image:Schematic Rep.jpg|860px]] | ||
| − | ''' | + | '''Algorithm''' |
| − | + | ||
| − | + | Univariate Polynomial Equations: | |
| − | + | [[Image:Algorithm Univariate.jpg|900px]] | |
| − | + | Multivariate Polynomial Equations: | |
| − | + | [[Image:Algorithm Multivariate.jpg|900px]] | |
| − | + | '''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. | |
| − | + | <br> | |
| − | + | ||
| + | [[Image:L2normdegree5oringinal.png|center|400px]] | ||
Revision as of 11:05, 22 April 2010
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.
