Image Matching Algorithm Based On Lifting Wavelet Transform

To achieve the aim of reducing the location time in image matching and maintain the high reliability and precision of the matching in the case of the existence of noise, this thesis studies the image matching based on lifting wavelet transform, and an algorithm of based on lifting wavelet transform combining projection in image matching is proposed and it is a coarse-to-fine image matching method.Based on the image features which are used in the image matching method, the image matching methods can be divided into three classes: the method based on the intensity, the method based on the image features and the method based on the image relation. Among the three classes, the traditional methods of the three classes are studied.An integrated analysis, experiment and summarization to the image matching method based on the intensity is made in this thesis. There are some traditional algorithms of image matching based on intensity. Normalized intensity correlation algorithm is an algorithm which makes correlation operation used every pixel gray value. Although this algorithm has large amount data calculation, it is robust to the noise when there is existence of noise. Mean-residual normalized intensity correlation is an improved algorithm of normalized correlation algorithm and has a character of intensifying the matching location and restraining the non-matching location. SSDA is an algorithm which computes the errors accumulation of corresponding pixel gray value of two images. In this algorithm, the location which reaches the error threshold quickly will be abandoned and the location whose accumulation time is the most will be the final image result. This algorithm speeds the matching, but the reliability of the matching will be influenced when there is noise.In the method based on the image features, two algorithms are mainly researched. They are invariant moment matching and projection matching. Invariant moment is robust to the small shifting, scaling and rotating transform of an image, but it has a large amount of data calculation of template image moment and original image moment so that go against to the use of real time image matching. Projection matching is an algorithm which projects two-dimensionimage to one-dimension data first and then operate the matching with one-dimension data. It reduces the amount of calculation of the image matching and it is robust to the linear change of the image intensity. But its precision will be influenced in the case of noise existence.Based on the analysis above, projection matching is used to the coarse matching part so that the amount of calculation can be reduced and the matching will be speeded. Furthermore, normalized intensity correlation is used to the fine matching part so that the precise can be enhanced.In the image matching method based on relation, the multi-resolution analysis (MRA) is mainly studied. Wavelet multi-resolution has the ability of successive approach and decomposes the image with multi-resolution. The low frequency image of every resolution can be decomposed to an approach image of low frequency and three detail image of high frequency of the next resolution. Every low frequency or high frequency image will be 1/4 of the image whose resolution is before. Low frequency image has most of the energy and framework information of original image, and high frequency image has little energy and information of the original image and has the noise which should be got rid of, too. Based on the theory of wavelet multi-resolution image matching can be carried in the low frequency image which is an approach image to the original image after decomposed, and continue to upper resolution matching with the outcome. Then because the low frequency image keeps the most information of the original image, reliability is guaranteed and noise is eliminated at the same time. As a result of using the outcome of the low resolution image as the input of the high resolution image, the calculation is reduced at the same time and it speeds the image matching.Lifting wavelet is different from the traditional wavelet transform and analyzes the items in the time region (space region). It not only holds the features of the traditional wavelet and also contains traditional wavelet so that all the traditional wavelet can be formed through the lifting method. Lifting framework technique can effectively accomplish the wavelet decompose and restoration with a series lifting (split, predict and update). Lifting wavelet also has the feature of multi-resolution analysis and offers a method of multi-resolution analysis. Lifting wavelet calculates in the original location. It is simple and understandability and its reverse transform is easy to achieve. So the lifting wavelet transform that has the feature of multi-resolution analysis is applied to the image matching, which notonly reserves the superiority of multi-resolution based on wavelet, and also speed image matching, and it is a simpler method.After the analysis and summarizing to the algorithms based on the intensity and features and studying the lifting wavelet which has the trait of multi-resolution analysis, specially studying the lifting scheme of Haar wavelet, this paper referred to a coarse-to-fine image matching method which is an image matching algorithm based on the lifting wavelet combining projection matching is proposed. In the coarse matching part, the two images are decomposed with lifting wavelet and the low frequency image of multi-resolution analysis can be received. Then carry on the image matching with projection matching in the lowest resolution image and continue the image matching with projection matching in the next resolution image using the outcome of the lowest resolution image as input of this resolution. Repeat this process until the highest resolution and a series of coarse points can be formed, so the coarse matching part is completed. In the fine matching part, normalized intensity correlation is used in the neighborhood of every coarse point to achieve the final matching point.Through the experience and analysis of comparing kinds of algorithms, the algorithm based on lifting wavelet transform combining projection matching has some traits below.(1) Speedy matching. Lifting wavelet transform which has the trait of multi-resolution analysis is used in this algorithm, so the amount of calculation is reduced and the matching is speeded. In every resolution image matching the projection matching is used and two-dimension data is projected to one-dimension data and difference to 0-1 character string, so the matching actually is comparing the 0-1 character strings and the amount of calculation is reduced and the matching is speeded again. When comparing the 0-1 character an error threshold is set up and the location of the bigger error is abandoned, so the needless calculation is reduced and matching is speeded.(2) High matching reliability. When there is noise in the real time image, the algorithm is robust to the noise because of using the lifting wavelet to pick-up the low frequency image and getting rid of a part of noise which is in high frequency. When a series coarse matching point is formed, normalized intensity correlation method is used to calculate the coarse matching point in the series, so the matching reliability is also enhanced.(3) High precision. Because of using the method of coarse-to-fine strategy, in the fine matching part normalized intensity correlation method is used in the neighborhood of coarse matching point to make precision emendation. The weakness of projection matching algorithm which has one or two pixel shifting from real matching location is overcome when there is noise in the real time image. This method can make matching location precise.In the research of image matching, the study of image matching method based on lifting wavelet transform is only a beginning. There are many items deserved more research. Lifting wavelet will make more action in the field of image matching, and will force development in other image processing techniques in the future.