Design And Implementation Of Parallel Image Matching Algorithm Based On MDSP

Image matching is one of the most important branch of image processing, it also is the foundational technology of image fusion, stereo vision, motion analysis. Researching on parallel image matching algorithm based on multi-core DSP can improve the speed of calculating, it is very significant for the application that having high requirement of real-time computing, such as computer vision, target tracking and so on.The thesis researches image matching algorithms of feature-based deeply: SIFT, PCA-SIFT and SURF, it designs and implements SIFT algorithm, PCA-SIFT algorithm, SURF algorithm based on single-core DSP, especially,it focuses on parallel SIFT algorithm,parallel PCA-SIFT algorithm and parallel SURF algorithm based on multi-core DSP(MDSP). The research job of the thesis mainly includes the following aspects:1. it researches image matching algorithms deeply. it generalizes and summarizes the research relating to image matching, especially focuses on the SIFT algorithm, PCA-SIFT algorithm and the SURF algorithm whose theory and implementation specific are studied in detail.2. The SIFT algorithm, the PCA-SIFT algorithm and the SURF algorithm based on single-core DSP are designed and implemented. On the basis of in-depth research of the principle of algorithms and the trade-off between the accuracy and the computational complexity, it makes algorithms a reasonable cut and optimized based on the characteristics of the single-core DSP architecture; According to the requirements of storage space of algorithms, it optimizes images and the intermediate results'storage location, ensuring the success of DSP memory space allocation, improving the stability and the speed of procedures execution. After the elementary matching points are obtained, it designs and implements algorithm based on RANSAC which is used for removing fault matching points.3. it researches image matching algorithms deeply based on multi-core DSP, designs and implements the parallel SIFT algorithm, the parallel PCA-SIFT algorithm, the parallel SURF algorithm. After a detailed analysis of implementation flow of the SIFT algorithm, the PCA-SIFT algorithm, the SURF algorithm, data level parallel algorithms are proposed based on the architecture features of multi-core DSP. Through reasonable segmenting of the image, image features are extracted on the four DSP cores at the same time; When matching these feature, each DSP core is used as the master node in turn to find the matching point of the real-time image. After initial matching points are obtained, it uses RANSAC algorithm that is designed to remove these points which are mistaken for right. Data communication among DSP cores uses QLink and SDP alternately, which develops multi-level parallelism of the MDSP fully.4. For the five image deformation of scale change, image rotation, illumination change, noise affecting and affine transformation, comprehensive tests are done on the single-core DSP algorithms designed and multi-core parallel algorithms designed. Experiment results show that: the average speedup of SIFT is 2.94, the average speedup of PCA-SIFT is 2.996, the average speedup of SURF is 3.7, which concludes that SURF algorithm has better parallelism than SIFT and PCA-SIFT; About repeatability, MDSP's repeatability is close to the repeatability of the single-core DSP; About the adaptability for image deformation, SIFT algorithm's comprehensive capacity of adaptability is best, but its speed of calculating is slow, the adaptability for image deformation of SURF is close to SIFT, but the calculating speed of SURF is ten times of SIFT's, PCA-SIFT's comprehensive ability of image matching is worse than SIFT and SURF.