摘 要

特征检测与匹配在图像识别领域起着重要作用。SIFT算法是从图像中检测和提取特征的最强大的方法之一，用来检测图像里局部的特征。但是，高复杂性使得SIFT算法工作时间较长，难以满足实时环境的要求。我们需要改进SIFT的实现，提高其适用性。目前，CPU和GPU运算能力得到显著增强，提高了各种算法的效率。同时伴随移动终端的当前的快速发展，并行计算不仅局限于PC端，手机和平板都可以实现了并行计算。这标志着应用已经发展到了一个新的阶段，可以应用PC上的应用到移动设备实现。

本文首先分析SIFT算法基本原理和实现算法基本流程，介绍了OpenCL并行技术及其搭建方式，及OpenCL编程一般采用的步骤，介绍了如何在Android平台通过调用C和C 来实现更强功能的方法，阐述了JNI作为连接接口的原理和作用。之后提出了基于OpenCL的对SIFT算法本身实现步骤进行优化，降低其计算复杂度，然后对CPU和GPU之间的具体任务进行优化，利用GPU计算能力较强的特性，把较大任务安排在GPU计算，减少算法的运算时间，并且保持算法的效率，提高运算能力。

本文针对移动终端的并行优化方案，完成了在Android平台基于OpenCL的SIFT特征检测算法的优化。

关键词：SIFT 并行计算 OpenCL 移动平台

Abstract

Feature detection and matching are important parts in image processing and recognition applications. Scale-invariant feature transform (SIFT) algorithm is one of the most powerful methods to detect and extract features from image features. On the scaling and rotation to maintain invariance, affine transformation, lighting, noise also maintain local invariance. However, the high complexity makes the SIFT algorithm work longer and makes it difficult to meet the requirements for real-time environment. We need to improve the implementation of SIFT to improve its applicability. At present, the computational power of the processor is more and more powerful, and the heterogeneous parallel programming model is realized, which greatly improves the efficiency of the SIFT algorithm. With the rapid development of the current mobile smart devices, smart phones and tablet PCs have achieved heterogeneous computing. This marks the application of this multi-pc has been developed to a new stage, you can apply the pc until the mobile device to achieve.

This paper first analyzes the basic principle of SIFT algorithm and the basic flow of implementing algorithm. It introduces OpenCL parallel technology and its construction mode. In view of the high complexity of SIFT algorithm, the SIFT algorithm itself is optimized and the operation time is reduced. On the one hand the use of the mobile GPU relative to the CPU's powerful computing power, CPU-GPU task allocation between the specific optimization, balance algorithm calculation and data transmission time, the use of parallel way between the CPU and GPU SIFT algorithm partition , To minimize the buffer transmission time, in order to achieve better performance.

In this paper, the optimization strategy of mobile platform is used to realize the feature detection and extraction of SIFT feature detection algorithm based on OpenCL on mobile intelligent terminal.

Keywords：SIFT Concurrent computation OpenCL Mobile platform

目录

摘要 I

Abstract II

目录 III

第1章 绪论 1

1.1研究背景及意义 1

1.2国内外研究现状 1

1.2.1国外研究现状 1

1.2.2国内研究现状 2

1.3研究的主要内容和结构安排 3

1.3.1本文研究的主要内容 3

1.3.2结构安排 3

第2章 本设计关键技术 4

2.1SIFT算法 4

2.1.1 构建尺度空间 4

2.1.2 确立特征点 7

2.1.3 计算特征描述符 8

2.1.4 特征点匹配 9

2.2OpenCL并行技术 9

2.2.1平台模型 10

2.2.2内存模型 11

2.2.3执行模型 12

2.2.4编程模型 13

2.2.5OpenCL编程步骤 14

2.3OpenCL平台搭建 14

2.4.Android平台调用C/C 函数 15

2.4.1Android平台架构 15

2.4.2JNI原理 15

2.5本章小结 17

第3章 基于OpenCL并行SIFT特征检测算法 18

3.1SIFT算法并行设计总体方案 18

3.2基于OpenCL的并行优化 20

3.2.1NDRange优化 20

3.2.2向量化读取 20

3.2.3存储优化 21

3.3本章小结 21

第4章 移动平台SIFT并行加速算法设计 22

4.1 图像预处理 22

4.2特征检测并行加速实现 22

4.2.1 构建尺度空间 22

4.2.2 确立特征点 23

4.2.3 计算特征描述符 24

4.3 特征点匹配 25

4.4本章小结 26

第5章 实验结果与分析 27

5.1 特征检测分析 27

5.2 特征点匹配性能分析 28

5.3 本章小结 31

第6章 总结与展望 32

6.1设计总结 32

6.2展望 32

致谢 33

参考文献 34

第1章 绪论

1.1研究背景及意义

随着互联网图像视频非文字数据的爆炸式增长，从大量的媒体数据库中的有效信息检索变得十分重要。其中，非文字信息数据已经成为最常见的类型之一。作为非文字捡索应用的基本组成部分，图像检测算法已成为研究热点之一。要自动搜索出来这这么多数据，需要去除提取其中某些的一些功能。在物体识别、三维重建、图像配准、视频理解等诸多领域具有非常重要的应用，但由于不同图像成像条件复杂、场景多样和存在各种几何形变，图像特征检测与匹配依旧是一个极具挑战性的热点研究课题。

目前为止，大量的特征检测算法被提出，在这些算法中，SIFT算法已经早已被证明是最强大提取的算法之一。SIFT算法自其被提出之日便受到图像处理诸多研究人员的研究，在图像领域解决许多问题。然而，SIFT 算法在通用 CPU 上处理图像或视频帧大约需要四秒钟，这远远不是实时处理要求，在实际应用中还需要进一步加快速度。因此，迫切需要加速 SIFT 算法。

近年来随着移动智能设备的高速发展，移动设备不仅是我们的生活越来越方便，也使得移动端所承担的功能越来越多。这些移动设备开始配备上了性能强大的多核CPU、GPU，越来越强大的摄像头，还有指纹识别等最新技术。移动图像检索技术从此开始迅速发展，它将更广泛的大量增强现实信息叠加到用户的视界，同时用户可以与增强现实应用进行简单的交互，甚至直接连接上互联网或者物联网，通过网络的数据通信与传输，与其他用户或者智能硬件进行交互。

1.2国内外研究现状

1.2.1国外研究现状

SIFT算法早在年由提出来的，并且之后进行了完善^[[1]]。SIFT算法自发表之时就是图像研究领域研究的经典算法。算法性能较好，当两张图片在各种非正常情况下像强烈光照、视角变化图形旋转、受压缩和变换等等各种情况，基本不影响它的匹配准确度。它的优点是特征匹配的稳定性和精度好，缺点是过于复杂，步骤耗时较长。

SIFT算法在被提出之后，大量的相关学者和研究者在此基础上提出了许多的算法。其中比较具有代表性的为SURF，该算法是Herbert Bay于年提出的图像特征提取算法，在此算法中，他使用积分搭建尺度空间，减少了大量的运算复杂度，测试了SIFT与SURF算法的性能，仅具有近似的旋转不变性，且在光照变化上也不如SIFT，是以一定的性能牺牲换取的速度提升。但是在匹配准确度上相对较差。此外也有许多的研究图像领域的学者发表了了其他个人的方案，Ysn提出了PCA-SIFT算法，它在生成梯度图像的时候使用了主成分分析方法。