Research On Algorithm For Images Matching And 3D Reconstruction Based On Graph

The technique of images matching and 3D reconstruction is the key subject in computer vision field, which is widely applied in precise industrial measurement, object recognition, virtual reality, auto navigation, automatization of production, military affair and many other fields. Recently, the algorithm based on graph for images matching and 3D reconstruction is the most popular research subject in the world. In the algorithm, pixels in images are processed directly to obtain the information of matching and depth by the combination optimization method based on graph spectra and graph cut, then the scene reconstruction can be realized. The algorithm has good robustness and real time. So, the research on the images matching and 3D reconstruction based on graph has not only important theory meaning but wide perspective of application.The systematic research on the algorithm of images matching and scene reconstruction based on graph is addressed in this dissertation, which includes images matching based on graph cut, images matching based on graph cut and epipolar constraint, images matching based on graph spectra, depth reconstruction based on graph cut and the 3D shape reconstruction using multiple view geometry theory and the results of images matching and depth reconstruction. The main research works and achievements are outlined as follow:1. A new algorithm for images matching based graph cut is presented. A new energy function is defined, the label is extended from 1 dimension to 2 dimensions, and a simpler construction method of graph is given. The algorithm adapts to matching of static images and matching of motion sequence images in more general conditions. Furthermore, the minimization in global is can be obtained. The experimental results show that the new algorithm not only can apply in more conditions but has a high accuracy.2. An algorithm for images matching based on graph cut and epipolarconstraint is proposed. The two original images are firstly rectified by epipolar constraint to make their epipolar lines parallel to the scan-lines. So the 2D matching of images is simplified to that of ID. Then the matching disparities can be gained by the ID matching algorithm based on graph cut. The label is ID in the energy function, and only 2-neibourghhood in scan-line is involved. Therefore, the searching range is greatly decreased. The experimental results indicate the new algorithm is simple, fast and high precise.3. After studying the images matching algorithm based on graph spectra in details, an algorithm for images matching based on Laplacian matrixes is presented. In this algorithm, the Laplacian matrixes of the feature point sets of the two images are constructed and decomposed by SVD respectively. Then a relation matrix which denotes the matching degree among feature points is constructed by the result of the decomposition. Finally, the matching feature points of the two images are obtained according to the relation matrixes. Experimental results indicate that the algorithm in the paper has the higher precision of matching.4. The algorithm for depth reconstruction based on graph cut is deeply researched, and the energy is improved. Then the depth is gained by the optimization method in the dissertation. Furthermore, according to the matching images and depth information, the 3D shape reconstruction is given using multiple view geometry theory.