The Research And Improvement Of SIFT Algorithm

Algebraic invariants was used in computer vision in 1888 by Isaac Weiss,thenthe vision invariant theories established. Invariant features refer to thefeatures those are invariant to image scaling, translation, rotation, affineand projective. Feature extraction algorithm has its measure. Generallyspeaking, extraciong ingdense and fine feathers do not mean that it is a goodfeature extraction algorithm.A good feature extraction algorithm shouldgenerally meet the following constraints:1.Separability of samples: The distance between similar samples shouldas small as possible, the distance between different types of samples shouldbe as large as possible, so that can effectively distinguish the differenttypes of samples;2.Effectiveness of characteristics: the extracted features of thealgorithm should meet the general requirements and special requirements, andthe classification error rate below a particular value;3.Ability of anti-mode distortion: Feature points should be invarianceto the general pattern of distortion such as translation, rotation, scalingand affine changes;4.Complexity: The time spent of extracting feature points, and it is alsothe time complexity of algorithms;5.Adaptability: feature extraction algorithm should be applied to manytypes of images. By verifying its relevance matching and the size of residuals,it can verify the adaptability of feature extraction algorithms.The investigation in this paper is about SIFT,SIFT is an algorithm basedon vision invariant.SIFT(Scale Invariant Feature Transform) algorithm is proposed by DavidLowe in 1999,and perfected and summarization in 2004. The features areinvariant to image scaling and rotation, and partially invariant to changein illumination and 3D camera viewpoint. They are well localized in both thespatial and frequency domains, reducing the probability of disruption byocclusion, clutter, or noise.SIFT algorithm contains lots of advantages,such as:1. SIFT algorithm is robustness and anti-interference;2. SIFT algorithm is unique and contains lots of infromation.It can beused in image maching when the database is huge.3. SIFT algorithm can extract lots of descriptors from some object.4. SIFT algorithm is extensible,it can be combined with other featherextraction algorithm.The major stages of computation used to generate the set of image features:scale-space extrema detection,keypoint localization, orientation assignment,keypoint descriptor.Because of the high dimension of SIFT descriptor, algorithm cost lots oftime to generate the descriptor, and don't fit to storage and search in largedatabase. The researchers both in home and abord have done lots of work toimprove the algorithm. Y.Ke used PCA to instead of histogram in descriptor.The improved algorithm has a dimension of 20 or less. Mikolajczyk has testedten local descriptors include SIFT, PCA-SIFT and so on. SIFT and its improvedalgorithm have the best robustness of all.The generation of descriptor cost lots of time, so in this paper we tryto simplify the descriptor. The new descriptor divided the region to a setof concentric circles. The region that we should calculate didn't change.The improved algorithm is still invariant to change in scaling and rotation,illumination and 3D camera viewpoint.This paper pay attention to choose the appropriate dimension.First,wedefined the keypoint matching, and choose the method of Mikolajczyk to measureit.The Mikolajczyk's method used the recall and precision to measure thealgorithm.When the dimension choose 6,8,10,12,14, statistics and analyse therecall and precision rate. We can see from the curve chart that when thedimension increase,the number of wrong matching points reduce,especially the obvious wrong matching points.When the dimension is 8,thereare lots of obvious wrong matching points,but when the dimension is 10,thenumber reduce a lot.The reason is the information in the descriptor increaseas the dimension. In different situations,we can choice different dimensionto improve the rate of matching points and reduce the time.In this paper,wechoice 10.We also contrast and analyse the improved algorithm and SIFT in the change of scaling and rotation, illumination ,3D camera viewpoint change and the timecost.We can see from the curve chart that the improved SIFT is invariant toimage scaling and rotation, and partially invariant to change in illuminationand 3D camera viewpoint, and more fit to the searching in large database.The improved SIFT can used in image matching,the image matching is a basicaspect of the issues of computer vision.It includes image recognition,3Dconstruction, three-dimensional consistent,action trace. Andrew Zissermanintroduce a method Video Google that used SIFT in image recognition in ICCV2003conference.Because of the small dimension,improved SIFT save lots of time inimage matching, and fit to the image matching in large database.Before the keypoint matching,we should cut the wrong matching points.Weuse RANSAC to reduce the wrong matching point.RANSAC is a useful method incomputer vision.There are two important steps in RANSAC: hypothesize and test.This paper used MATLAB and C to compile the program.C should compile toMEX file. The advantage of MATLAB is that it is good to image processing, andC cost less time than MATLAB.SIFT algorithm has already used in object recognition,robot locatizationand mapping,panorama stitching,3D scene modeling,recognition and tracking andhuman action recognition.And more and more researchers involved in researchingSIFT algorithm,and I believe that it will be used in more aspect.