Contour Correspondence Method Based On Circumcircles Of Triangles

This work focus on the contour correspondence problem, namely how to confirm thecorrect correspondence relationship among contours which lie on adjacent cross sections inthe process of3D surface reconstruction based on2D contours. The correspondence problemplays an important role in the process of3D reconstruction. Since there may be more than onecorrespondence relationships among contours lying on adjacent cross sections due to thecomplex topology structure of the object, such as1vs.1case,1vs. n case and n vs. n case.Only when the correspondence relationship among contours which lie on adjacentcross sections is confirmed, it is possible to tie them together. At present, twoproblems need to be resolved in the study of contour correspondence:(1) how to solvethe problem that there are branching contours and nesting contours in an object;(2)how to get the ideal result when the interval between cross sections is large or there isno significant overlap among contours which lie on adjacent cross sections. Thus, acorrect and robust contour correspondence method should be proposed to solve allthose problems.In this thesis, a contour correspondence method based on circumcircles of triangles,including contour classification and the study of contour correspondence method, isproposed. In this method, a contour is represented by a set of circumcircles, byinvestigating the correspondence relationship among circumcircles, thecorrespondence relationship among contours which lie on adjacent cross sections canbe determined. Firstly, in order to ensure the accuracy of the correspondence algorithmand the correctness of the reconstructed shape of the object, all the contours areclassified as external contour or internal nesting contour according to the Jordan CurveTheorem, and the nesting level of external contour and internal nesting contour ismarked and arrayed. Secondly, triangulate each contour, and legalize the triangles byDelaunay constraint method that maximize the minimum angles to avoid long and thintriangles. Then a set of circumcircles extracted from the triangles which have been legalized are used to represent a contour. Thirdly, the local area correspondencerelationship among contours can be confirmed by investigating the correspondencerelationship among circumcircles, and then the correspondence relationship amongcontours can be confirmed.Circumcircles will only correspond with the nearest circumcircles which lie on theadjacent cross sections by using the contour correspondence method proposed in thisthesis. Because the nearness relationship is reciprocal and small circumcircles tends tohave a local effect on the correspondence, this algorithm allows existing area that isnot connected. This local correspondence characteristic can accurately process theobject with branching contours and nesting contours.