数字散斑识别算法中的GPU高性能运算应用研究

黄 磊，张李超，鄢 然

引言

数字散斑相关方法（digital speckle correlation method，DSCM）是上世纪八十年代初日本的I.Yamaguchi［1］与美国南卡罗来纳大学的 W.H.Peter和 W.F.Ranson［2］等人同时独立提出的一种光力学测量技术。经过几十年的研究发展积累，数字散斑相关技术已成为一种成熟的测量方法。比起传统测量方法，数字散斑相关方法有着光路简单、对测量环境要求低、全场非接触测量等优点。但是普通的CPU数字散斑相关算法需要进行大量繁复耗时的串行相关运算，数据处理量巨大，极大影响了该方法的实时处理速度，一直以来都是该方法在各大领域应用的一大难点。

在传统串行计算越来越难以满足大数据量处理的背景下，并行计算的高性能优越性越发突显并引起广泛关注和研究。1999年nVidia公司首先提出了计算机图形处理器（graphics processing unit，GPU）的概念，与中央处理器（central processing unit，CPU）不同，GPU架构特别为图形处理设计，具有天然的并行特性，极大提升了计算机图形处理的速度。

本文通过将GPU高性能并行运算应用于传统的数字散斑逐点搜索算法，在不损失精度的前提下大幅提高了散斑识别速度，并探讨了GPU高性能并行运算应用于其他常见散斑识别算法的可行性。

1 数字散斑识别原理

数字散斑相关方法通过摄像机记录物体运动或变形前后的数字散斑图像，对2幅图像灰度场进行相关运算，通过搜索相关系数的极值来获取物体的运动或变形信息。

如图1，在运动前图像中取待测点P（x，y），以P为中心取大小为m×m（m最好为奇数）个像素的子集，通过相关搜索算法在运动后图像中搜索以Q（x′，y′）为中心的子集，使两者相关系数取得最大值。由于散斑的随机性，根据统计学可认为Q即为P运动后的对应点，两者的坐标差值即为待测点P的位移。

图1 数字散斑识别原理示意图Fig.1 Schematic diagram of digital speckle pattern recognition

相关系数公式［3］为

式中：f＝f（i，j），g＝g（i＋u，j＋v）分别为源点和目标点为中心的散斑图的灰度值；u和v为其水平和垂直方向位移值；＜f＞和＜g＞为其子集平均值。

2 GPU高性能运算及CUDA

GPU高性能运算用于提升计算机大数据量处理速度在过去的开发方式非常复杂，2006年11月nVidia公司推出了基于G80的并行编程模型和C语言开发环境CUDA（compute unified device architecture，计算统一设备架构），程序员不再需要详细了解GPU的内部实现就可以高效编写出基于GPU的高性能计算程序。

CUDA的线程层次如图2所示，一维、二维或三维的线程网格（grid）由线程块（block）组成，线程块则包含了大量的线程束，总的线程数即为线程块数与每个线程块中的线程数之积。

图2 CUDA线程层次Fig.2 Thread level of CUDA

3 常见数字散斑相关算法及其GPU高性能加速实验

3.1 逐点搜索算法

逐点搜索算法是最基础的方法，通过简单粗暴的遍历运动后图像灰度场，搜索相关系数的极值。这种方法虽然耗时较长，但由于每次相关运算均相互独立从而具有良好的可并行性，非常适合于进行GPU高性能加速运算。逐点搜索算法流程如图3所示。

图3 逐点搜索算法流程图Fig.3 Flow chart of point－by－point search algorithm

实验中通过编写程序为运动后的散斑图像灰度场中每个像素分配一个GPU线程，每个线程分别计算出相应的相关系数，然后遍历搜索极值从而获得位移信息。由并行原理可知，对于像素越多数据越复杂的图像，通过GPU加速处理的性能越发突显。对于不同像素大小的散斑图像，其GPU高性能算法搜索时间也应趋于稳定。

实验模拟采集不同像素大小的运动前后散斑图像，并用传统的常规算法和GPU高性能算法分别进行搜索，得到实验结果如表1所示。

表1 逐点搜索算法及其GPU高性能运算实验结果Table 1 Experimental result of point－by－point search algorithm and its GPU high－performance application

3.2 十字搜索算法

十字搜索算法是由芮嘉白等人提出的一种快速搜索方法，该方法的理论基础是认为相关系数曲面分布具有良好的单峰性。十字搜索算法首先在运动后的散斑图像灰度场中取初始点P，计算该点及其水平、垂直方向的距离一个步长的4个像素点的相关系数，若P点的相关系数最大，则表明P即为一个峰值；若P周围4个像素点中某点取得相关系数最大值，则将P点向该点移动，重复此过程直至P点相关系数取得最大值［7－8］。十字搜索算法流程如图4所示。

图4 十字搜索算法流程图Fig.4 Flow chart of cross search algorithm

十字搜索法的效率明显优于逐点搜索算法，但其对于散斑图像单峰性的前提也相当苛刻。实际应用中必须考虑次峰带来的干扰，避免十字搜索止于次峰而错误匹配。为此可以通过设置阀值进行过滤，阀值大小则与具体实验条件有关。一旦P点取得峰值但小于阀值，则应加大步长继续十字搜索，直至搜索到主峰结束。

为尽量满足散斑图像相关系数呈单峰性分布，搜索像素的子集大小不宜太小，否则会出现过多的次峰，并失去主峰的平滑性。实验中取像素子集大小为21×21，算出主峰周围的相关系数如图5所示。图中主峰已经比较平滑，非常利于附近点向主峰的逼近，十字搜索的准确性也更加稳健。

图5 散斑图像主峰周围的相关系数Fig.5 Correlation coefficient around main peak of speckle image

由流程图可知，十字搜索算法运算过程本身具有很强的串行性，无法直接转为并行计算。而十字搜索算法的起始点选择至关重要，直接影响了搜索效率和准确性。为此可以将散斑图像划分为密集网格，每个网格点对应一个GPU线程的起始点，每个线程独立搜索，一旦某个线程率先到达主峰则全部线程结束。

传统十字搜索的耗时与物体具体移动的位移大小和搜索起始点有关，通过划分网格并行十字搜索可以将时间控制为几乎等同于单个网格内的十字搜索。划分网格适当减小，开启线程越多，整体耗时也将减少，从而大幅提高搜索效率。与逐点搜索的GPU高性能算法一样，理论上十字搜索的GPU高性能算法同样可以将时间稳定在一定范围内，一定范围内散斑图像实际大小对其影响不大。

实验利用十字搜索算法对运动前后散斑图像进行模拟识别，以及GPU高性能运算进行加速，得到实验结果如表2。

表2 十字搜索算法及其GPU高性能运算实验结果Table 2 Experimental result of cross search algorithm and its GPU high－performance application

3.3 遗传算法

遗传算法是美国Michigan大学JohnHolland教授在1969年提出的模拟进化算法。该算法基于进化论、物种选择学说和群体遗传学说。遗传算法的基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。遗传算法一般运算流程如图6，过程如下：

a）初始化种群。随机生成N个个体作为初始种群X（0），设定终止进化判断条件，进化代数计数器置零。

b）适应度评估。评估种群X（t）内各个个体的适应度。

c）选择。利用选择算子从X（t）中选出母体。

d）交叉。利用交叉算子对母体进行交叉运算，形成中间个体。

e）变异。利用变异算子对中间个体进行变异运算。

此时种群X（t）通过选择、交叉、变异运算即得到了下一代群体X（t＋1）。

f）判断终止条件。根据设定的终止进化判断条件进行检测，当循环次数达到规定值时，将具有最大适应度的个体作为最优解，算法结束。

图6 遗传算法流程图Fig.6 Flow chart of genetic algorithm

遗传算法具有天然的隐含并行性，非常适合于在GPU上实现。目前的研究总共提出了4种遗传算法的并行模型：主从式模型、粗粒度模型、细粒度模型及混合模型［9－10］。主从式模型保留遗传算法的结构特点，直接将种群的选择、交叉、变异等全局处理交给主机（CPU）串行执行，而相对耗时的适应度评估和计算则由设备（GPU）并行高效处理，从而有效缩短遗传算法的运算时间。

主从式较易于实现，本文即采用主从式模型进行编程，对不同大小的散斑图像进行识别实验，初始种群大小设为100，最大代数为20，交叉概率为0.8，变异概率为0.3，每次保留2个个体，得出实验数据如表3所示。从表中数据可知，通过将GPU高性能运算应用于遗传算法，可使其计算效率平均提高约31倍～44倍。

以上实验均通过Visual Studio联合CUDA编程实现，实验环境如图7所示，通过运动平台控制CCD相机做x方向运动，以及物体做y方向运动，从而获取物体运动前后的散斑图像。

表3 遗传算法及其GPU高性能运算实验结果Table 3 Experimental result of genetic algorithm and its GPU high－performance application

图7 实验现场图Fig.7 Scene picture of experiment

4 结论和展望

数字散斑相关方法作为一种光路简单、全场、非接触性的有效测量手段，其应用前景非常广阔。本文介绍了数字散斑相关方法的基本原理和瓶颈以及GPU高性能运算的优势，通过将GPU高性能运算应用于常见的数字散斑相关方法，使这几种算法的计算效率得到了大幅的提升，尤其是逐点搜索算法，对于1 000×1 000像素的散斑图像达到了424倍的提速。十字搜索算法通过不同起始点并行计算，对于1 000×1 000像素的散斑图像达到了116倍的提速。而遗传算法本身即具有一定的并行性，对于1 000×1 000像素的散斑图像也提速了44倍。但是这仅是初步的尝试和探索，逐点搜索算法往往仅常见于实验室环境，十字搜索算法的稳健性还有待加强，散斑遗传算法的其他复杂并行模型实现和应用也值得更加深入探讨，这也是我们接下来进一步研究的方向。

［1］ Yamaguchi I.A Laser－speckle strain gage［J］.Journal of Physis E：Scientific Instruments，1981，14：1270－1273.

［2］ Ranson W F，Peters W H.Digital image techniques in experimental stress analysis［J］.Optical Engineering，1982，21（3）：427－431.

［3］ Jin Guanchang.Computer assistant optic measurement［M］.2nd ed.Beijing：Tsinghua University Press，2007.

金观昌.计算机辅助光学测量［M］.2版.北京：清华大学出版社，2007.

［4］ Ruan Qiuqi.Digital image processing［M］.Beijing：Publishing House of Electronics Industry，2001.

阮秋琦.数字图像处理学［M］.北京：电子工业出版社，2001.

［5］ Liu Haibo，Shen Jing，Guo Song.Digital image processing using C＋＋［M］.Beijing：China Machine Press，2010.

刘海波，沈晶，郭耸.Visual C＋＋数字图像处理技术详解［M］.北京：机械工业出版社，2010.

［6］ Jason Sanders.CUDA by example：an introduction to general－purpose GPU programming［M］.translated by Nie Xuejun，Beijing：China Machine Press，2011.

桑德斯.GPU高性能编程CUDA实战［M］.聂雪军，译.北京：机械工业出版社，2011.

［7］ Rui Jiabai，Jin Guanchang，Xu Binye.An advanced digital speckle correlation method and its application［J］.Acta Mechanica Sinica，1994，26（5）：599－607.

芮嘉白，金观昌，徐秉业.一种新的数字散斑相关方法及其应用［J］.力学学报，1994，26（5）：599－607.

［8］ Sun Yiling，Li Shanxiang，Li Jingzhen.Investigation and modification of the digital speckle correlation method［J］.Acta Photonica Sinica，2001，30（1）：54－57.

孙一翎，李善祥，李景镇.数字散斑相关测量方法的研究与改进［J］.光子学报，2001，30（1）：54－57.

［9］ Xi Yugeng，Chai Tianyou，Yun Weimin.Survey on genetic algorithm［J］.Control theory and applications，1996，13（6）：697－708.

席裕庚，柴天佑，恽为民.遗传算法综述［J］.控制理论与应用，1996，13（6）：697－708.

［10］Gao Jiaquan，He Guixia.A review of parallel genetic algorithms［J］.Journal of Zhejiang University of Technology，2007，35（1）：56－72.

高家全，何桂霞.并行遗传算法研究综述［J］.浙江工业大学学报，2007，35（1）：56－72.

［11］Tan Caifeng，Ma Anguo，Xing Zuocheng.Research on the parallel implementation of genetic algorithm on CUDA platform［J］.Computer Engineering ＆Science，2009，31（A1）：68－72.

谭彩凤，马安国，邢座程.基于CUDA平台的遗传算法并行实现研究［J］.计算机工程与科学，2009，31（A1）：68－72.

［12］Zhang Zhaohui，Liu Junqi，Xu Qinjian.Analysis and application of the GPU parallel computing technology［J］.Information Technology，2009，11：86－89.

张朝晖，刘俊起，徐勤建.GPU并行计算技术分析与应用［J］.信息技术，2009，11：86－89.

［13］Wu Enhua，Liu Youquan.General purpose computing on GPU［J］.Journal of Computer－Aid Design ＆Computer Graphics.2004，16（5）：601－612.

吴恩华，柳有权.基于图形处理器（GPU）的通用计算［J］.计算机辅助设计与图形学学报，2004，16（5）：601－612.