Point Set Registration Methods Based On Algebra And Geometric Invariants

Image registration is a fundamental problem in computer vision, pattern recog-nition, image analysis, medical image processing and other fields. It has a widerange of application, including flight navigation, radar tracking, industry detec-tion, automatic monitoring, character recognition and medical diagnosis. Imageregistration is particularly important in medical application, as imaging is widelyused in clinical diagnosis. Present image registration methods can be classified intotwo types. The first type of methods perform registration by directly matching thepixel grey values, the others match image by the features extracted from the im-ages. The latter must first extract some feature points from the original imagesand then match the image from these feature points. Once the feature is extracted,feature point set matching becomes the key for image registration.Besides its application in image registration, point set matching or registrationby itself is an important field in theory and application. It.s possible that point setcomes directly from human labeling or sensor, rather than from feature extraction.A lot of research has been carried out around the classical problem of point setmatching due to it importance in theory and practice. The mainstream research onthis topic uses optimization-based methods. Problems common to optimization-based methods include local optimum and initial guessing, or even guaranteedconvergence in some cases. The methods must rely on other methods for an initialguess when a reasonable guess is not available. Spectral methods do not requireoptimization, but typically involves complicated computation and are prone tooutliers.This thesis investigates the classic problem of point set registration. To over-come the limitation of traditional optimization-based methods, we proposed newglobal, non-iterative and closed-form methods for point set registration in two typ-ical scenarios with practical application. The methods directly compute globalsolutions using either algebraic or geometric-invariant based techniques, thus ob- viate the problem of local optimum and convergence commonly encountered inoptimization-based methods, and reduce the computational complexity by simpli-fying the computation. The thesis discussed the efect of noise and outliers as well.The methods proposed can also be used to compute a reasonable initial values forthose optimization-based methods to speed up convergence. The proposed meth-ods are expected to have promising application in many important fields includingmedical image processing, video image tracking. To be specific, this thesis consistsof the following parts.The first part proposed an efcient algebraic method for solving afne pointset registration in3D space without outliers. For many difcult problems, algebraicsolutions are often very elegant if available. The problem is that algebraic solutionsor even algebraic representation is hardly available in many cases. Point set regis-tration problem belong to these cases. In2007, an elegant algebraic method basedon complex representation was proposed for the same problem in2D space. Themethod regards each point as a complex number, and point set as the roots of apolynomial of high degree. Based on the relation between the roots and coefcientsof polynomials, the rotation between two point sets is regarded a relation betweenthe coefcients of two polynomials. The transformation and point correspondenceis determined using the coefcients of polynomials. The method is very elegant andits computational complexity is linear, the lowest possible. However this methodis hard to generalize to higher dimensions due to the lack of algebraic structuresimilar to complex number for2D space.Inspired by the work on2D, we introduced quaternion representation of3Dpoint and proposed an algebraic method for afne point set registration in3D,despite the diference of algebraic structure between complex number and quater-nion. To overcome the difculty resulting from the fact that commutative law doesnot hold for quaternion, direct compuation of elementary symmetric polynomials isperformed, which is further reduced to summation of powers by generalizing New-ton’s identity to quaternions. The proposed method works for arbitrary rotation,with a consistent linear time and space complexity. The degenerated cases whenthis method fails are discussed too. It’s shown from the experiments that the newmethod runs faster than traditional optimization-based methods including LMICP,GMM and CPD by an order of magnitude and the accuracy is better in low-level noise.The second part proposed a method for solving rigid (isometric) point setregistration, based on the concept of geometric invariants. The method deals withalmost any number of outliers. This method use the distance as a rigid invariant.The concept of Gaussian inner product between diferent dimensions of vectorswas introduced, so was Gaussian product of two matrices. A matching matrix iscomputed by using Gaussian multiplication between distance matrices, and then asearch on the matrix for elements was performed to obtain point correspondence.By adoption of Fast Gauss Transform(FGT), the computational complexity of thismethod is reduced to O(MN(M+N))§where M and N is the size of the twopoint sets. It is the lowest complexity among existing methods in the same class.Compared to that reported by McAuley in2012, the proposed method reached anaccuracy at the same level with a reduced time complexity. Experimental resultsshowed that this method nearly always find the correct correspondence with zeroerror in noiseless case even with several times more outliers. The performance ofthe method keeps moderate up to a certain level of noise. Techniques to furtherimprove the performance was also discussed.The third part discussed the generalization of the methods proposed in theabove part. To be more specific, generalization of algebraic method for3D pointset registration to higher dimensions than4D was discussed. Compared to2D or3D,4D or higher dimensions are less important in practical application, but stillvaluable in theory. For the geometric-invariant based method for rigid point setregistration, the ideas of generalize it to more wide scope like similarity transoformor afne transform was explored.In summary, this thesis proposed a highly efcient algebraic method for solvingpoint set registration problem in3D without outlier, and discussed the generaliza-tion to higher dimension. The results show the power and potential of algebraicmethods in point set registration, valuable in both theory and application. Thisthesis also proposed a new geometric-invariant based approach for rigid point setregistration, which achieves nearly zero error in absence of noise. This methodalso serves as a reference for solving more complex point matching problem. Bothmethods proposed by this thesis are expected to have potential application in thesefields like medical image processing, multimedia and pattern recognition. The methods proposed in this these show great performance at low level ofnoise, but the performance drops faster at higher levels of noise. More work isrequired in order to improve noise response, as well as to generalize the algebraicand invariant method for point matching to more complex transformation.