Study On Fast And Reliable Pattern Match

Image matching is widely applied in the fields of computer vision and videometrics. The application including target location, object tracking, motion detection and three demntional reconstruction, etc. The speed and robustness of image matching have significant affects on the performance of those applications.Image matching can be divided as template based methods(also known as pattern matching) and feature based methods. Pattern matching is the task of seeking a given pattern in a given image by per-pixel comparison. Compared with image features, pattern can provide more complete information of image. As a result, pattern matching can provide more relabel result for the textureless images or the images polluted by noise or blur. Howerver, the current pattern matching algorithms is still not fast or reliable enough for some real-time tasks or the multi-modality image matching which is hindered by serious noise and complicate gray distortion. Therefore, the study on fast and reliable pattern matching has signification meaning.Pattern matching based terminal guidance application and video stabilization are taken as the research background of this dissertation. We make an intense rearch on the measures and intirsic image extraction of pattern matching. The research mainly serves two purposes: increasing the speed of template match and enhancing the reliability of pattern matchning for images with serious noise or grayscale distortion. The main achievements of this dissertation are given as follows:1. For handling the problem that the speed of pattern matching based on L1-norm is slow, a measure based on sum of cosine is proposed. For pattern matching, measure is the estimation of the similarity or dissimilarity between two images. L1-norm is a reliable dissimilarity measure, but the pattern matching based on L1-norm is slow. The feature of the proposed measure is that it has similar matching reliability with L1-norm while be able to achieve very fast matching speed by employing techniques based on fast Fourier transform(FFT) or orthogonal decomposition.2. For enhancing the speed of pattern matching using normalized cross corealation(NCC) as measure, a fast algorithm for NCC pattern matching based on orthogonal decomposition is also proposed. The proposed algorithm won’t affect the reliabity of the NCC pattern matching while be able to achieve very fast matching speed. The experimental result shows that if the image noise is not significant, the proposed algorithm can reduce run times by about 1~2 orders of magnitude compared with full search algorithm; otherwise, it can terminate the iteration adaptively to prevent excessive increase of calculation.3. For handling the gray distortion problem, which is very common between multi-sensor images, a novel algorithm for intrinsic image extraction based on structure tensor is proposed. It relieves the affection of gray distortion and noise by changing the gray image to intrinsic image based on structure tensor. As a result, the reliability of the pattern matching is increased effectively. Tests use multi-sensor image to compare the proposed algorithm with existing algorithms. The results show that the proposed algorithm not just improves the matching accuracy, but also increases matching speed.4. Aiming at the target location in terminal guidance applications, a fast pattern matching algorithm based on triangle inequality and orthogonal decomposition is proposed. To achieve the real-time requirement, the pattern matching for terminal guidance has to decrease the time of online processing as much as possible. The feature of the pattern matching for some terminal guidance applications is that the base image and its relevant data can be prepared during the offline stage. Based on that fact, the proposed algorithm decreases the time of online processing effectively by accomplish the most calculation of pattern matching in the offline stage.5. For video stabilization, a real-time video stabilization based on associate Kalman filter is proposed. First, a novel method combined by feature point tracking and pattern matching is employed to estimate the video motion. After that, the video motion is smoothed by the associate Kalman filter so as to stabilize the input video. Compared with the video stabilization based on 3D reconstruction or feature trajectories, the proposed method can adapt to noise, motion blur, or light change more effictively. Experiments show that the proposed video stabilization method can offer real-time stabilizing for videos with 2D scenes or the 3D scenes with moderate depth variation.