On Key Algorithms Of 3D Reconstruction

The object of computer vision is to make the computer have the ability of understanding 3D environmental information from 2D images, which is a complicated inverse problem since it recurs to the combinatorial optimization techniques and projective geometry theory and is very sensitive to errors caused by noises and discretization. Image matching and camera calibration are the foundations for realizing 3D reconstruction, which are both abnormal on problems solving. Hence research on image matching and camera calibration has both theoretical significance and practical values. We think that the focus of improving the above two kinds of algorithms should be searching optimization methods and determining the constraint conditions. Under above idea, the thesis presents algorithms of feature matching of images based on spectral graph theory, dense matching of images based on graph cut optimization, and camera calibration based on projective geometry theory.The thesis focuses on the key algorithms of 3D reconstruction: image matching and camera calibration, and acquires the main achievements as follows:1. The algorithm of feature points matching based on Laplacian spectral theorey. Given feature points of two images, we define Laplacian matrices respectively, analysis the eigenvalues and eigenvectors of the matrices, and construct a feature points matching matrix. By information of magnitude and position of entries in the matching matrix, we realize the feature points matching. Furthermore, we theoretically prove that our algorithm can acquire an exact matching under an equilong transformation or equiform transformation on images. Real experiments show that the matching rate may attain 80% upwards.2. The algorithm of dense matching of images based on graph cuts optimization. Firstly, the energy function is established and the problem of matching can be transformed into that of energy function minimization. A network is constructed such that the energies can be related to the capacities of the cuts of the network. Finally,the minimization of the energy function is obtained by the theory of network-flows, and hence the disparity data are obtained. Comparing with some known algorithms based on graph cuts, the algorithm in this paper extends the label from ID vector to ID vector, and adapts visual matching of more general cases; furthermore the algorithm can obtain the minimization in global. Real experiments show that the matching rate can achieve 75% upwards.3. The algorithm of camera self-calibration based on planar structural information of scenes. We give explicit forms of the homography between a plane in the scene and that of an image, the absolute conic and its images, and the constraints of circular points to the camera intrinsic parameters. Applying above forms, we give methods of camera self-calibration based on three kinds of planar structural information of scene which are rectangles, isosceles trapezoids, equilateral triangles. Experimental results show that all methods have high accuracy.4. The algorithm of camera self-calibration with moving ID objects using a bi-cameras setting. First, we give the images of circular points in the plane which the ID object translates on, and the constraints of them to the camera intrinsic parameters, and also give a numerical solving method of the constraints equations (and hence obtain the camera intrinsic parameters). By recovering the coordinates of 3D points under camera coordinates system, we can resolve the poses between two cameras (i.e. the camera external parameters). For a general rigid motion of ID objects, we give a method which transforms it into translations. Experimental results of both simulated data and real-world data show that this method has a high accuracy and practical values.