SURF算法在嵌入式对称多处理机上的并行设计与实现

摘要

随着手持移动设备性能和屏幕分辨率的快速提升，用户对全景照相、图片拼接等应用有了越来越高的要求。这些应用耗时最长的部分是以SURF算法为代表的图像局部特征提取算法。现有的SURF算法实现大都基于桌面计算机平台，但是在嵌入式领域，由于设备计算能力较弱，内存较小，SURF算法需要消耗大量的时间，严重影响了用户体验。因此，对SURF算法进行优化设计，使其能够高效地运行于嵌入式平台，是当下的一个研究热点。
　　本文以嵌入式对称多处理系统作为硬件平台，利用OpenMP编程模型，对SURF算法进行并行优化设计。本文首先对并行程序的设计方法、设计原则和评价指标作了介绍;其次，结合SURF算法理论对OpenSURF源码做了详细分析;最后，利用性能分析工具对OpenSURF进行了热点代码检测，对热点代码进行了并行可行性分析，并对热点函数做了针对性的并行设计与实现。在实验部分，本文首先研究了OpenMP版OpenSURF在Pandaboard（双核）、树莓派二代（四核）和Odroid-XU3（八核）三个平台上运行时的最优线程数和最优调度策略;在此基础之上使用与SURF原文相同的测试图集对设计目标进行验证。
　　实验结果表明:本文所设计的OpenSURF程序相比未经优化的源程序，在Pandaboard和树莓派二代开发板上处理SURF原文测试图集的平均耗时分别从1.97秒下降到了1.05秒和从4.25秒下降到了1.25秒;加速比分别达到1.8和3.39;并行效率分别达到0.9和0.85;问题规模加倍的条件下其在树莓派二代上的并行效率达到0.91，高于在单倍问题规模下Pandaboard上的并行效率0.9，证明了它的可扩展性;本文还设计了Pthreads版的OpenSURF作为参照实验，在相同测试图集的测试下OpenMP版OpenSURF较Pthreads版OpenSURF在Pandaboard上的平均运行时间低5.77％，计算效率平均高5.99％。

目录

声明

摘要

第一章 绪论

1．1 课题背景与意义

1．2 国内外研究现状

1．3 研究内容及目标

1．3．1 研究内容

1．3．2 研究目标

1．4 论文组织

第二章 并行计算理论基础

2．1 并行计算发展简介

2．2 并行硬件介绍

2．3 并行程序的设计方法和设计原则

2．3．1 并行程序设计方法

2．3．2 并行程序设计原则

2．4 并行程序评价指标

2．4．1 加速比和并行效率

2．4．2 可扩展性

2．5 并行编程模型介绍和选择

2．6 OpenMP编程问题

2．7 本章小结

第三章 SURF算法的串行代码实现分析

3．1 SURF算法流程概述

3．2 特征点检测的实现分析

3．2．1 建立积分图像

3．2．2 构建Hessian矩阵

3．2．3 构造尺度空间

3．2．4 定位特征点

3．3 特征点描述和匹配的实现分析

3．3．1 分配特征点主方向

3．3．2 构造基于Haar小波响应的描述符

3．3．3 特征点匹配

3．4 本章小结

第四章 SURF算法的并行设计与实现

4．1 算法并行化分析

4．1．1 热点代码分析

4．1．2 并行可行性分析

4．2 并行设计与实现

4．2．1 修改Makefile

4．2．2 积分图像构造的并行设计实现

4．2．3 特征点检测的并行设计与实现

4．2．4 特征点描述的并行设计与实现

4．2．5 特征点匹配的并行设计与实现

4．3 本章小结

第五章 实验与结果分析

5．1 实验平台与测试方法

5．1．1 实验软硬件平台介绍

5．1．2 测试指标与测试方法

5．2 最优参数选择与分析

5．2．1 最优线程数选择与分析

5．2．2 最优调度选择与分析

5．2．3 最优参数小结

5．3 量化指标验证

5．4 Pthreads版OpenSURF对比分析

5．5 实验结果总结

5．6 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

致谢

参考文献

攻读硕士学位期间发表的论文