黃 磊，張李超，鄢 然

引言

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

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

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

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

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

如圖1，在運動前圖像中取待測點P（x，y），以P為中心取大小為m×m（m最好為奇數(shù)）個像素的子集，通過相關(guān)搜索算法在運動后圖像中搜索以Q（x′，y′）為中心的子集，使兩者相關(guān)系數(shù)取得最大值。由于散斑的隨機性，根據(jù)統(tǒng)計學(xué)可認(rèn)為Q即為P運動后的對應(yīng)點，兩者的坐標(biāo)差值即為待測點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）分別為源點和目標(biāo)點為中心的散斑圖的灰度值；u和v為其水平和垂直方向位移值；＜f＞和＜g＞為其子集平均值。

2 GPU高性能運算及CUDA

GPU高性能運算用于提升計算機大數(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)部實現(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高性能加速實驗

3.1 逐點搜索算法

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

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

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

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

表1 逐點搜索算法及其GPU高性能運算實驗結(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ù)曲面分布具有良好的單峰性。十字搜索算法首先在運動后的散斑圖像灰度場中取初始點P，計算該點及其水平、垂直方向的距離一個步長的4個像素點的相關(guān)系數(shù)，若P點的相關(guān)系數(shù)最大，則表明P即為一個峰值；若P周圍4個像素點中某點取得相關(guān)系數(shù)最大值，則將P點向該點移動，重復(fù)此過程直至P點相關(guān)系數(shù)取得最大值［7－8］。十字搜索算法流程如圖4所示。

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

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

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

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

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

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

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

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

3.3 遺傳算法

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

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

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

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

d）交叉。利用交叉算子對母體進行交叉運算，形成中間個體。

e）變異。利用變異算子對中間個體進行變異運算。

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

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

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

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

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

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

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

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

4 結(jié)論和展望

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

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

金觀昌.計算機輔助光學(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］.北京：機械工業(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實戰(zhàn)［M］.聶雪軍，譯.北京：機械工業(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］.光子學(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平臺的遺傳算法并行實現(xiàn)研究［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］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2004，16（5）：601－612.