《基于mdsp的并行图像匹配算法的设计与实现》由会员分享，可在线阅读，更多相关《基于mdsp的并行图像匹配算法的设计与实现（90页珍藏版）》请在金锄头文库上搜索。
1、国防科学技术大学 硕士学位论文 基于MDSP的并行图像匹配算法的设计与实现 姓名：邢彬朝 申请学位级别：硕士 专业：软件工程 指导教师：刘仲 2011-03 国防科学技术大学研究生院工程硕士学位论文 第 i 页 摘 要 图像匹配是图像处理的重要研究方向之一，也是图像融合、立体视觉、运动分析等图 像分析技术的基础。通过研究基于多核 DSP 的并行图像匹配算法，提高算法的执行速度， 对计算机视觉、目标跟踪等实时性要求较高的应用有十分重要的意义。 本文深入研究了基于特征的图像匹配算法 SIFT、PCA-SIFT 和 SURF，设计和实现了 基于单核 DSP 的 SIFT 算法、PCA-SIFT 算法
2、、SURF 算法，重点研究、设计和实现了基于 多核 DSP（MDSP）的并行 SIFT 算法、并行 PCA-SIFT 算法和并行 SURF 算法。主要的研 究工作包括以下几个方面： 1. 深入研究了图像匹配算法。对图像匹配的相关研究进行概括和总结，重点研究了 SIFT 算法、 PCA-SIFT 算法和 SURF 算法， 对算法的原理和实现细节进行了详细的 研究。 2. 设计和实现了基于单核 DSP 的 SIFT 算法、PCA-SIFT 算法和 SURF 算法。在深入 研究算法原理的基础上，基于计算精度和运算复杂度的权衡，针对单核 DSP 体系 结构的特点，对算法进行了合理的裁剪和优化；根据算法
3、对存储空间的要求，优 化了图像和中间结果的存放位置的设计，保证 DSP 存储空间的成功分配并提高了 程序的稳定性和执行速度。对于初步匹配点中的误配点，本文设计和实现了基于 RANSAC 算法误配点剔除算法，剔除了存在的误配点。 3. 深入研究了基于多核 DSP 的并行图像匹配算法，设计并实现了基于 MDSP 体系结 构的并行 SIFT 算法、并行 PCA-SIFT 算法和并行 SURF 算法。针对 MDSP 多核体 系结构的特点，对 SIFT 算法、PCA-SIFT 算法和 SURF 算法的实现流程进行详细 的分析，提出了数据级并行算法方案。通过对图像进行合理的分割，四个 DSP 核 同时提取
4、图像特征；特征匹配时，每个 DSP 核依次作为主控结点，寻找实时图的 匹配点。获得初步的匹配点后，采用基于 RANSAC 算法的误配点剔除算法，剔除 存在的误配点。DSP 核间的数据通信采用了 QLink 和 SDP 相结合的方式，充分开 发 MDSP 的多级并行性。 4. 针对尺度变化、图像旋转、光照明暗变化、噪声影响和仿射变换五种图像形变， 对设计的单核算法和多核并行算法进行综合测试实验。实验的结果为：SIFT 的平 均加速比为 2.94，PCA-SIFT 的平均加速比为 2.996，SURF 的平均加速比为 3.7， 表明 SURF 算法的并行性较好；在重复率方面，MDSP 与单核 DS
5、P 的重复率接近； 算法对图像形变的适应性方面，SIFT 算法对图像形变的综合适应能力最好，但运 算速度慢，SURF 算法的适应能力接近 SIFT，但运算速度比 SIFT 快十倍左右， PCA-SIFT 的综合适应性不如 SIFT 和 SURF。 关键字：多核 DSP；图像匹配；并行；SIFT；PCA-SIFT；SURF 国防科学技术大学研究生院工程硕士学位论文 第 ii 页 ABSTRACT Image matching is one of the most important branch of image processing, it also is the foundational t
6、echnology 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 tr
7、acking 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
8、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 al
9、gorithm 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-of
10、f 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 locatio
11、n, 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 match
12、ing 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 alg
13、orithms 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
14、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 ima
15、ge deformation of scale change, image rotation, illumination change, 国防科学技术大学研究生院工程硕士学位论文 第 iii 页 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
16、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, MDSPs repeatability is close to the repeatability of the single-core DSP; About the adaptability for image deformation, SIFT algorithms 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
