黃 磊，張李超，鄢 然

引言

數(shù)字散斑相關(guān)方法（digital speckle correlation method，DSCM）是上世紀(jì)八十年代初日本的I.Yamaguchi［1］與美國南卡羅來納大學(xué)的 W.H.Peter和 W.F.Ranson［2］等人同時獨(dú)立提出的一種光力學(xué)測量技術(shù)。經(jīng)過幾十年的研究發(fā)展積累，數(shù)字散斑相關(guān)技術(shù)已成為一種成熟的測量方法。比起傳統(tǒng)測量方法，數(shù)字散斑相關(guān)方法有著光路簡單、對測量環(huán)境要求低、全場非接觸測量等優(yōu)點(diǎn)。但是普通的CPU數(shù)字散斑相關(guān)算法需要進(jìn)行大量繁復(fù)耗時的串行相關(guān)運(yùn)算，數(shù)據(jù)處理量巨大，極大影響了該方法的實(shí)時處理速度，一直以來都是該方法在各大領(lǐng)域應(yīng)用的一大難點(diǎn)。

在傳統(tǒng)串行計算越來越難以滿足大數(shù)據(jù)量處理的背景下，并行計算的高性能優(yōu)越性越發(fā)突顯并引起廣泛關(guān)注和研究。1999年nVidia公司首先提出了計算機(jī)圖形處理器（graphics processing unit，GPU）的概念，與中央處理器（central processing unit，CPU）不同，GPU架構(gòu)特別為圖形處理設(shè)計，具有天然的并行特性，極大提升了計算機(jī)圖形處理的速度。

本文通過將GPU高性能并行運(yùn)算應(yīng)用于傳統(tǒng)的數(shù)字散斑逐點(diǎn)搜索算法，在不損失精度的前提下大幅提高了散斑識別速度，并探討了GPU高性能并行運(yùn)算應(yīng)用于其他常見散斑識別算法的可行性。

1 數(shù)字散斑識別原理

數(shù)字散斑相關(guān)方法通過攝像機(jī)記錄物體運(yùn)動或變形前后的數(shù)字散斑圖像，對2幅圖像灰度場進(jìn)行相關(guān)運(yùn)算，通過搜索相關(guān)系數(shù)的極值來獲取物體的運(yùn)動或變形信息。

如圖1，在運(yùn)動前圖像中取待測點(diǎn)P（x，y），以P為中心取大小為m×m（m最好為奇數(shù)）個像素的子集，通過相關(guān)搜索算法在運(yùn)動后圖像中搜索以Q（x′，y′）為中心的子集，使兩者相關(guān)系數(shù)取得最大值。由于散斑的隨機(jī)性，根據(jù)統(tǒng)計學(xué)可認(rèn)為Q即為P運(yùn)動后的對應(yīng)點(diǎn)，兩者的坐標(biāo)差值即為待測點(diǎn)P的位移。

圖1 數(shù)字散斑識別原理示意圖Fig.1 Schematic diagram of digital speckle pattern recognition

相關(guān)系數(shù)公式［3］為

式中：f＝f（i，j），g＝g（i＋u，j＋v）分別為源點(diǎn)和目標(biāo)點(diǎn)為中心的散斑圖的灰度值；u和v為其水平和垂直方向位移值；＜f＞和＜g＞為其子集平均值。

2 GPU高性能運(yùn)算及CUDA

GPU高性能運(yùn)算用于提升計算機(jī)大數(shù)據(jù)量處理速度在過去的開發(fā)方式非常復(fù)雜，2006年11月nVidia公司推出了基于G80的并行編程模型和C語言開發(fā)環(huán)境CUDA（compute unified device architecture，計算統(tǒng)一設(shè)備架構(gòu)），程序員不再需要詳細(xì)了解GPU的內(nèi)部實(shí)現(xiàn)就可以高效編寫出基于GPU的高性能計算程序。

CUDA的線程層次如圖2所示，一維、二維或三維的線程網(wǎng)格（grid）由線程塊（block）組成，線程塊則包含了大量的線程束，總的線程數(shù)即為線程塊數(shù)與每個線程塊中的線程數(shù)之積。

圖2 CUDA線程層次Fig.2 Thread level of CUDA

3 常見數(shù)字散斑相關(guān)算法及其GPU高性能加速實(shí)驗(yàn)

3.1 逐點(diǎn)搜索算法

逐點(diǎn)搜索算法是最基礎(chǔ)的方法，通過簡單粗暴的遍歷運(yùn)動后圖像灰度場，搜索相關(guān)系數(shù)的極值。這種方法雖然耗時較長，但由于每次相關(guān)運(yùn)算均相互獨(dú)立從而具有良好的可并行性，非常適合于進(jìn)行GPU高性能加速運(yùn)算。逐點(diǎn)搜索算法流程如圖3所示。

圖3 逐點(diǎn)搜索算法流程圖Fig.3 Flow chart of point－by－point search algorithm

實(shí)驗(yàn)中通過編寫程序?yàn)檫\(yùn)動后的散斑圖像灰度場中每個像素分配一個GPU線程，每個線程分別計算出相應(yīng)的相關(guān)系數(shù)，然后遍歷搜索極值從而獲得位移信息。由并行原理可知，對于像素越多數(shù)據(jù)越復(fù)雜的圖像，通過GPU加速處理的性能越發(fā)突顯。對于不同像素大小的散斑圖像，其GPU高性能算法搜索時間也應(yīng)趨于穩(wěn)定。

實(shí)驗(yàn)?zāi)M采集不同像素大小的運(yùn)動前后散斑圖像，并用傳統(tǒng)的常規(guī)算法和GPU高性能算法分別進(jìn)行搜索，得到實(shí)驗(yàn)結(jié)果如表1所示。

表1 逐點(diǎn)搜索算法及其GPU高性能運(yùn)算實(shí)驗(yàn)結(jié)果Table 1 Experimental result of point－by－point search algorithm and its GPU high－performance application

3.2 十字搜索算法

十字搜索算法是由芮嘉白等人提出的一種快速搜索方法，該方法的理論基礎(chǔ)是認(rèn)為相關(guān)系數(shù)曲面分布具有良好的單峰性。十字搜索算法首先在運(yùn)動后的散斑圖像灰度場中取初始點(diǎn)P，計算該點(diǎn)及其水平、垂直方向的距離一個步長的4個像素點(diǎn)的相關(guān)系數(shù)，若P點(diǎn)的相關(guān)系數(shù)最大，則表明P即為一個峰值；若P周圍4個像素點(diǎn)中某點(diǎn)取得相關(guān)系數(shù)最大值，則將P點(diǎn)向該點(diǎn)移動，重復(fù)此過程直至P點(diǎn)相關(guān)系數(shù)取得最大值［7－8］。十字搜索算法流程如圖4所示。

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

十字搜索法的效率明顯優(yōu)于逐點(diǎn)搜索算法，但其對于散斑圖像單峰性的前提也相當(dāng)苛刻。實(shí)際應(yīng)用中必須考慮次峰帶來的干擾，避免十字搜索止于次峰而錯誤匹配。為此可以通過設(shè)置閥值進(jìn)行過濾，閥值大小則與具體實(shí)驗(yàn)條件有關(guān)。一旦P點(diǎn)取得峰值但小于閥值，則應(yīng)加大步長繼續(xù)十字搜索，直至搜索到主峰結(jié)束。

為盡量滿足散斑圖像相關(guān)系數(shù)呈單峰性分布，搜索像素的子集大小不宜太小，否則會出現(xiàn)過多的次峰，并失去主峰的平滑性。實(shí)驗(yàn)中取像素子集大小為21×21，算出主峰周圍的相關(guān)系數(shù)如圖5所示。圖中主峰已經(jīng)比較平滑，非常利于附近點(diǎn)向主峰的逼近，十字搜索的準(zhǔn)確性也更加穩(wěn)健。

圖5 散斑圖像主峰周圍的相關(guān)系數(shù)Fig.5 Correlation coefficient around main peak of speckle image

由流程圖可知，十字搜索算法運(yùn)算過程本身具有很強(qiáng)的串行性，無法直接轉(zhuǎn)為并行計算。而十字搜索算法的起始點(diǎn)選擇至關(guān)重要，直接影響了搜索效率和準(zhǔn)確性。為此可以將散斑圖像劃分為密集網(wǎng)格，每個網(wǎng)格點(diǎn)對應(yīng)一個GPU線程的起始點(diǎn)，每個線程獨(dú)立搜索，一旦某個線程率先到達(dá)主峰則全部線程結(jié)束。

傳統(tǒng)十字搜索的耗時與物體具體移動的位移大小和搜索起始點(diǎn)有關(guān)，通過劃分網(wǎng)格并行十字搜索可以將時間控制為幾乎等同于單個網(wǎng)格內(nèi)的十字搜索。劃分網(wǎng)格適當(dāng)減小，開啟線程越多，整體耗時也將減少，從而大幅提高搜索效率。與逐點(diǎn)搜索的GPU高性能算法一樣，理論上十字搜索的GPU高性能算法同樣可以將時間穩(wěn)定在一定范圍內(nèi)，一定范圍內(nèi)散斑圖像實(shí)際大小對其影響不大。

實(shí)驗(yàn)利用十字搜索算法對運(yùn)動前后散斑圖像進(jìn)行模擬識別，以及GPU高性能運(yùn)算進(jìn)行加速，得到實(shí)驗(yàn)結(jié)果如表2。

表2 十字搜索算法及其GPU高性能運(yùn)算實(shí)驗(yàn)結(jié)果Table 2 Experimental result of cross search algorithm and its GPU high－performance application

3.3 遺傳算法

遺傳算法是美國Michigan大學(xué)JohnHolland教授在1969年提出的模擬進(jìn)化算法。該算法基于進(jìn)化論、物種選擇學(xué)說和群體遺傳學(xué)說。遺傳算法的基本思想是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過程搜索最優(yōu)解的算法。遺傳算法一般運(yùn)算流程如圖6，過程如下：

a）初始化種群。隨機(jī)生成N個個體作為初始種群X（0），設(shè)定終止進(jìn)化判斷條件，進(jìn)化代數(shù)計數(shù)器置零。

b）適應(yīng)度評估。評估種群X（t）內(nèi)各個個體的適應(yīng)度。

c）選擇。利用選擇算子從X（t）中選出母體。

d）交叉。利用交叉算子對母體進(jìn)行交叉運(yùn)算，形成中間個體。

e）變異。利用變異算子對中間個體進(jìn)行變異運(yùn)算。

此時種群X（t）通過選擇、交叉、變異運(yùn)算即得到了下一代群體X（t＋1）。

f）判斷終止條件。根據(jù)設(shè)定的終止進(jìn)化判斷條件進(jìn)行檢測，當(dāng)循環(huán)次數(shù)達(dá)到規(guī)定值時，將具有最大適應(yīng)度的個體作為最優(yōu)解，算法結(jié)束。

圖6 遺傳算法流程圖Fig.6 Flow chart of genetic algorithm

遺傳算法具有天然的隱含并行性，非常適合于在GPU上實(shí)現(xiàn)。目前的研究總共提出了4種遺傳算法的并行模型：主從式模型、粗粒度模型、細(xì)粒度模型及混合模型［9－10］。主從式模型保留遺傳算法的結(jié)構(gòu)特點(diǎn)，直接將種群的選擇、交叉、變異等全局處理交給主機(jī)（CPU）串行執(zhí)行，而相對耗時的適應(yīng)度評估和計算則由設(shè)備（GPU）并行高效處理，從而有效縮短遺傳算法的運(yùn)算時間。

主從式較易于實(shí)現(xiàn)，本文即采用主從式模型進(jìn)行編程，對不同大小的散斑圖像進(jìn)行識別實(shí)驗(yàn)，初始種群大小設(shè)為100，最大代數(shù)為20，交叉概率為0.8，變異概率為0.3，每次保留2個個體，得出實(shí)驗(yàn)數(shù)據(jù)如表3所示。從表中數(shù)據(jù)可知，通過將GPU高性能運(yùn)算應(yīng)用于遺傳算法，可使其計算效率平均提高約31倍～44倍。

以上實(shí)驗(yàn)均通過Visual Studio聯(lián)合CUDA編程實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境如圖7所示，通過運(yùn)動平臺控制CCD相機(jī)做x方向運(yùn)動，以及物體做y方向運(yùn)動，從而獲取物體運(yùn)動前后的散斑圖像。

表3 遺傳算法及其GPU高性能運(yùn)算實(shí)驗(yàn)結(jié)果Table 3 Experimental result of genetic algorithm and its GPU high－performance application

圖7 實(shí)驗(yàn)現(xiàn)場圖Fig.7 Scene picture of experiment

4 結(jié)論和展望

數(shù)字散斑相關(guān)方法作為一種光路簡單、全場、非接觸性的有效測量手段，其應(yīng)用前景非常廣闊。本文介紹了數(shù)字散斑相關(guān)方法的基本原理和瓶頸以及GPU高性能運(yùn)算的優(yōu)勢，通過將GPU高性能運(yùn)算應(yīng)用于常見的數(shù)字散斑相關(guān)方法，使這幾種算法的計算效率得到了大幅的提升，尤其是逐點(diǎn)搜索算法，對于1 000×1 000像素的散斑圖像達(dá)到了424倍的提速。十字搜索算法通過不同起始點(diǎn)并行計算，對于1 000×1 000像素的散斑圖像達(dá)到了116倍的提速。而遺傳算法本身即具有一定的并行性，對于1 000×1 000像素的散斑圖像也提速了44倍。但是這僅是初步的嘗試和探索，逐點(diǎn)搜索算法往往僅常見于實(shí)驗(yàn)室環(huán)境，十字搜索算法的穩(wěn)健性還有待加強(qiáng)，散斑遺傳算法的其他復(fù)雜并行模型實(shí)現(xiàn)和應(yīng)用也值得更加深入探討，這也是我們接下來進(jìn)一步研究的方向。

［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.

金觀昌.計算機(jī)輔助光學(xué)測量［M］.2版.北京：清華大學(xué)出版社，2007.

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

阮秋琦.數(shù)字圖像處理學(xué)［M］.北京：電子工業(yè)出版社，2001.

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

劉海波，沈晶，郭聳.Visual C＋＋數(shù)字圖像處理技術(shù)詳解［M］.北京：機(jī)械工業(yè)出版社，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實(shí)戰(zhàn)［M］.聶雪軍，譯.北京：機(jī)械工業(yè)出版社，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.

芮嘉白，金觀昌，徐秉業(yè).一種新的數(shù)字散斑相關(guān)方法及其應(yīng)用［J］.力學(xué)學(xué)報，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.

孫一翎，李善祥，李景鎮(zhèn).數(shù)字散斑相關(guān)測量方法的研究與改進(jìn)［J］.光子學(xué)報，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］.控制理論與應(yīng)用，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］.浙江工業(yè)大學(xué)學(xué)報，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平臺的遺傳算法并行實(shí)現(xiàn)研究［J］.計算機(jī)工程與科學(xué)，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并行計算技術(shù)分析與應(yīng)用［J］.信息技術(shù)，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.

吳恩華，柳有權(quán).基于圖形處理器（GPU）的通用計算［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2004，16（5）：601－612.