Image Structure Description And Matching Based On Graph Theory

Image description and image matching are two fundamental tasks in imageengineering and hot research topics in the field of computer vision and patternrecognition. The structure of an image which consists of image elements and theirrelationships is one of the most stable features in the image and reflects the essentialcontent of the image. And graph, which is an important and effective way to representthe structural information, can describe the relationships of image elements well.Therefore, it is receiving more and more attention to represent the image structure usinggraph and to solve the image feature matching problem by graph matching. In this thesis,we use graph to represent the structural information of images and investigate theproblem of structural description and matching of images in detail. The main researchworks and achievements are outlined as follows:(1)A method for structural description of images based on MST(MinimumSpanning Tree) is proposed. The MST constructed from the structural elements extractfrom the image support the image like the skeleton of the image, which reflects thestructure of image. Three indexes for evaluating the distribution uniformity, thedistinctiveness and the spanning degree of a set of image structural elements are definedbased on the MST. The evaluating indexes can be used to analyze the structuralinformation of an image and can also be used to evaluate the capability of a set ofstructural elements to describe the structure of an image.(2)The structural description of an image using feature points as structuralelements is studied. Firstly, a new binary descriptor for feature point is proposed.Comparing to the traditional floating-point descriptors of high-dimension vector, thisdescriptor yields comparable matching performance while running very fast andrequiring comparatively smaller amounts of memory. Then, the MST is constructedusing the points extracted from the image and the evaluating indexes are computed toanalyze the distribution of the points in the image and the repetitive pattern in the image,which reflect the structural information of the image. Taking the indexes as evaluatingprinciple, a method for choosing a set of points based on the pruning of MST isproposed. Experimental results show that the method can selecting a set of points whichare optimal or suboptimal in principle to describe the structure of the image.(3)The structural description of an image using feature lines as structural elementsis discussed. Since the detection results of standard edge detectors contain a lot ofspurious edges, an contour edge detection algorithm based on the adaptive facilitationand suppression mechanism of NCRF(Non-Classical Receptive Field) is presented. Bysimulating the facilitation and inhibition mechanism of NCRF, the algorithm strengthenthe gradient magnitudes of contour edges and decrease the gradient magnitudes of spurious edges, which simplifies the post-processing and improves the contour detectionperformance of standard edge detectors. Aiming at the phenomenon of double edgesgiven by traditional edge detectors when processing the ridge-type edges, a modifiedwide-line detector based on USAN(Univalue Segment AssimilatingNucleus)—M-USAN detector is presented, which treat the ridge-type edges aswide-lines and can extract the center-line of the wide lines. Moreove, in order to removethe redundant computation in the implementation of USAN wide-line detector andM-USAN wide-line detector, two acceleration algorithms—ASM-USAN detector(Adaptive Step Moving USAN detector) and R-USAN detector (Randomized USANdetector) are proposed, which successfully improve the speed of the USAN detectorwhile keeping its detection performance almost unspoiled.(4)A graph matching method based on association graph and path similarity isproposed. Firstly, the association graph whose nodes are the potential correspondencesof the two matching graphs is constructed, then its affinity matrix is computed bycomparing the corresponding shortest path in the two matching graphs, and finally thecorrect assignments are recovered by using the principal eigenvector of the affinitymatrix. For the graph constructed from different features, such as feature points andstraight lines, different similarity transformation invariants and affine transformationinvariants are used to construct the descriptive vector of shortest path between twovertexes in the graph. Experiments results on both the simulated images and real imagesdemonstrate the effectiveness of the method.