基于改進CS算法的整像素數字散斑相關方法

周海芳，楊秋翔，楊 劍

（中北大學 計算機與控制工程學院，山西 太原030051）

0 引 言

數字散斑相關方法 （digital speckle correlation method，DSCM）研究的核心內容是相關搜索方法［1］，早期的相關搜索方法主要有兩種類型［2］：一種是將位移和位移導數同時搜索，如粗－細相關法；另一種是認為位移導數值對相關系數的貢獻遠小于位移值，為了節省時間只進行位移搜索，如十字搜索法。為了提高搜索的速度，將相關搜索用數學手段轉化為迭代格式求解，如Newton－Rapson 迭代算法，但迭代算法嚴重依賴初值的選取。若將上述相關搜索方法用于多峰值搜索就很容易陷入局部最優，從而導致搜索結果不準確，為此一些學者將新的數學理論 （如頻域傅里葉方法、神經網絡方法、小波變換方法等）引入到DSCM 方法中，給相關搜索帶來了新的途徑，不僅使得搜索精度有了數量級的提高，而且算法更加智能化。

布谷鳥搜索 （cuckoo search，CS）算法［3，4］是一種新穎的群體智能優化算法，其優勢主要是模擬鳥類及果蠅特殊的Lévy飛行模式進行搜索，算法簡單、參數少，易于實現。然而CS算法是一種新興的仿生算法，其收斂速度和求精能力仍需要進一步改善。Valian等研究了步長因子對算法性能的影響，采用動態調整的策略增加了算法的性能［5］；鄭洪清等給出了基于最佳鳥巢位置的自適應調整步長的策略［6］；王凡等提出將高斯分布引入CS算法［7］。本文通過引入非均勻變異算子和最優鳥巢擾動策略對CS算法進行改進，并用4個標準測試函數進行驗證，最后將改進后的CS算法應用到了數字散斑相關方法中。

1 數字散斑相關方法基本原理

數字散斑相關方法基本原理請參見文獻 ［8］。相關系數公式是目標子區與樣本子區相互關系的定量描述，表示匹配時的相似程度［8］。相關系數公式有很多種，本文采用以下公式

式中：C—— 相關系數，C 越大表示越相關，C ＝1時完全相關。f＝f（i，j）、g＝g（i＋u，j＋v）表示分別為以源點和目標點為中心的散斑圖的灰度值函數；f′、g′分別為所在標記區域的平均灰度。

2 基本的CS算法

布谷鳥搜索算法是模擬自然界中布谷鳥種群寄生繁衍的生物行為而衍生出的搜索算法，同時結合了鳥類及果蠅特殊的Lévy飛行模式，全局搜索能力很強，適合用于多目標優化問題求解。該算法的構建基于3個理想規則，具體規則請參見文獻 ［4］。在3個理想規則的基礎上，布谷鳥按Lévy飛行模式搜索鳥巢的路徑和位置更新公式如下

式中：x（t）i——第t代的第i 個鳥巢位置；——點對點乘法；——步長信息；Lévy（λ）——隨機搜索路徑。

在按一定的發現概率Pa丟棄部分鳥巢之后采用隨機游動重新生成相同數量的新鳥巢，位置更新公式如下

式中：r 是 （0，1）區間均勻分布的隨機數，x（t）j、x（t）k是第t代的兩個隨機鳥巢位置。

3 改進后的CS算法 （ICS算法）

3.1 非均勻變異算子

布谷鳥每次尋巢過程中的隨機搜索路徑即Lévy（λ）的長度和方向都是髙度隨機改變的，具有非常大的盲目性。雖然算法在迭代初期很利于全局搜索，但在迭代后期就很容易跳過最優解，出現震蕩現象，造成算法收斂速度和尋優精度大大降低。本文引入非均勻變異算子［9］，自適應調節步長使得算法在迭代前期可以在整個定義域中大范圍搜索，盡可能發現潛在的區域，隨著迭代的進行，步長逐漸減小，到迭代臨近結束時，步長趨于零，此時布谷鳥可以在當前最優鳥巢位置的狹小鄰域中精細搜索，從而準確定位最優鳥巢位置。

假 設 第t 代 的 第i 個 鳥 巢 的 位 置 為xi（t）＝｛xi（1t），xi（2t），…，xi（dt）｝T，對鳥 巢的第j維 位 置 執 行 變 異，則 變異后的分量為

在Δ（t，y）＝y·（1－y（1－Tt）b）中，t是當前迭代次數，T是最大迭代次數，r 是服從 （0，1）區間均勻分布的隨機數，b為決定變異非均勻度的系統參數，［LB，UB］為搜索空 間 的 范 圍， 則 更 新 后 的 鳥 巢 位 置 為 yi（t＋1）＝｛yi（1t＋1），yi（2t＋1），…，yi（dt＋1）｝T。

3.2 鳥巢位置更新策略

在標準CS算法中，各個布谷鳥都是按照自己的方式盲目飛行，相互之間并沒有進行交流，這并沒有充分顯示出智能算法的優點。本文借鑒粒子群算法的飛行速度和位置更新機制，令通過隨機游動得到的新鳥巢位置由兩部分組成，其中一部分信息繼承于自身的位置，另一部分吸收于上一代的最優鳥巢位置信息，從而加快整個算法的收斂速度。具體公式如下

式中：r是（0，1）區間均勻分布的隨機數，y（t＋1）i是通過非均勻變異因子更新得到的鳥巢位置，bestnest是第t代的最優鳥巢位置。

3.3 最優鳥巢擾動策略

在鳥巢主人發現外來布谷鳥蛋步驟后，不是直接進入下一次迭代而是引入最優鳥巢擾動策略。在多維函數的尋優過程中，對不同維數采用相同范圍的擾動顯然不能滿足求解需求，本文將最優鳥巢位置依據方差可調的正態隨機分布進行逐維擾動，該變異操作不但能有效避免CS算法陷入局部最優，而且可以增加整個種群的多樣性

3.4 ICS算法的基本步驟

步驟1 初始化參數：將不同的求解問題按照相應的要求初始化鳥巢個數n，解空間維數d，最大迭代次數T，搜索空間范圍 ［LB，UB］，發現概率Pa，適應度函數fit（x）。

步驟2 初始化種群：在 ［LB，UB］空間范圍內隨機生成n個鳥巢，令t＝1，其中第i個鳥巢的位置為xi（1）＝｛xi（11），xi（21）…，xij（1）…xi（d1）｝T，計 算 各 個 鳥 巢 的 適 應 度 函 數值，求出最優鳥巢bestnest。

步驟3 鳥巢位置進行隨機游動操作：將每個鳥巢按式（4）方式隨機游走，式 （5）確定鳥巢按游走方式得到的最終位置并計算適應度函數值，與更新前的比較后保留較優鳥巢位置。

步驟4 鳥巢主人發現外來鳥蛋操作：產生服從 ［0，1］均勻分布的隨機數r，若r ＞Pa，則按式 （3）更新鳥巢位置并計算適應度函數值，與更新前的比較后保留較優鳥巢位置同時更新bestnest。

步驟5 最優鳥巢擾動操作：將bestnest按式 （6）、式（7）進行擾動得到更新后的鳥巢并計算適應度函數值，與更新前的比較后保留較優鳥巢為bestnest。

步驟6 判斷操作：若fit（bestnest）沒有達到要求且t＜T，則令t＝t＋1，跳轉到步驟3，否則循環結束，輸出最優鳥巢位置及適應度函數值。

4 仿真實驗

4.1 實驗設計

本文通過尋找4個標準測試函數的最小值0為例，進行仿真實驗來評估ICS算法的性能，標準測試函數及其相關參數設置見表1，測試平臺為Matlab2013a、windows7，處理器CPUM370，主頻2.4GHz，內存2G。

表1 測試函數及其參數設置

實驗中種群規模n＝100，T＝500。為克服算法的偶然誤差，對各測試函數獨立運行50 次，取其最優值、最差值、平均值和標準偏差與基本CS算法進行比較。

4.2 實驗結果分析

表2描述了標準CS和ICS算法對以上4個測試函數的測試結果，對于低維函數Schaffe和Rosenbrock，ICS比CS算法的平均搜索精度分別提高4和9個數量級，最優值分別提高8個數量級，ICS的最差值比CS算法的最優值還要分別提高3和5個數量級。在高維函數Sphere中，ICS比CS算法的平均搜索精度提高7個數量級，且成功找到最優值，最差值要比CS算法的最優值還要提高6個數量級。在高維函數Rastigrin中，ICS比CS算法的平均搜索精度提高1個數量級，最優值提高7個數量級?？v觀整個數據表，無論是解的質量上 （最優值、平均值和最差值），還是算法穩定性方面 （標準偏差），ICS算法都要優于CS算法。

從圖1 （a）～ （d）的ICS和CS算法的收斂曲線可以看出，ICS算法的收斂速度有明顯提高且迭代次數遠小于CS算法。

表2 兩種優化算法的計算結果

圖1 相關測試函數收斂曲線

5 ICS算法在數字散斑相關方法中的應用

5.1 ICS算法測量散斑圖像位移的流程

基于以上討論，用改進的布谷鳥搜索算法對散斑圖平移后的位移進行整像素的相關搜索，流程如圖2所示。

圖2 ICS算法流程

5.2 ICS算法測量模擬散斑圖位移

先制作模擬散斑圖，圖3（a）為源圖片，將源圖片向右平移17個像素，向下5個像素，得到移動后的圖片圖3（b）。

圖3 模擬散斑

以模擬散斑圖為研究對象，取移動前某一點的位移進行相關搜索。以該點為中心選取邊長為21像素的正方形區域作為樣本子區［10］，在移動后的圖片上以相同的點為中心取邊長為80像素的正方形區域作為搜索區域，相關系數C在搜索區域內的分布如圖4所示?？梢园l現，圖4的中央有一個最高峰，在最高峰附近還有多個較高的局部峰。

ICS算法測量模擬散斑圖位移時初始參數設置為：Tmax為30，鳥巢個數為15，樣本子區為21×21 像素，搜索區域為80×80像素，Pa.max＝0.95，Pa.min＝0.15。

圖5 （a）～ （c）分別給出了迭代次數N＝1、5、15時各個鳥巢在相關系數水平等勢線上所處的位置?？梢园l現，第1代鳥巢的分布是雜亂無章的，而第5代鳥巢整體上向最優解靠攏，在第15代時絕大數鳥巢與最優解重合。

圖4 相關系數分布

5.3 ICS算法與CS、PSO （particle swarm optimization）算法比較

用3種算法測量相同的散斑圖位移，固定迭代次數為30，種群個數為15，樣本子區尺寸為21×21像素，搜索域尺寸為60×60像素，各算法分別進行100次的獨立實驗，表3列出了適應度C 的最差值，最優值，平均值，尋優成功率和各算法獨立運行一次所用的平均時間。

從表3可以看出，3種算法在100次獨立試驗中都找到過最優值，但綜合C 最差值、平均值、尋優成功率可以看出PSO 算法最容易陷入局部最優，并且在100次獨立實驗中陷入局部最優的次數最多；ICS算法相對PSO、CS算法尋優成功率分別提高29.3%、18.3%，平均誤差分別降低了294%、85.8%。說明ICS算法與CS算法在計算時間相差不大的情況下擁有更強的跳出局部最優的能力，搜索精度更高，尋優成功的概率更大。

為了進一步分析各算法在測量散斑圖位移的收斂性能，圖6給出了各算法在測量散斑圖位移時的迭代過程。圖中標記點的適應度函數值都是取在100次獨立實驗中迭代次數對應的適應度平均值。

圖5 鳥巢運動軌跡

表3 各算法的計算結果

圖6 各算法迭代過程

從圖6可以看出：在迭代初期，ICS算法全局尋優能力最強，在鎖定最優值范圍后，局部收斂能力最強并且求精能力最優。而CS算法在收斂速度和求精能力上都比粒子群算法略優。

6 結束語

針對基于傳統DSCM 的計算結果容易陷入局部最優，求解精度不高，后期收斂速度慢等缺點，本文將基于群體智能的CS算法引入到DSCM 中，并對基本的CS算法進行了改進，將ICS，CS，PSO 這3種算法用于測量預制模擬散斑圖平移后的整像素位移，實驗結果表明CS 算法在DSCM 中是有效的，并且ICS 方法較CS，PSO 算法在DSCM 中跳出局部最優的能力最強，收斂速度最快和尋優精度最高。

［1］YANG Yuhang.Study of digital speckle correlation method［D］.Jilin：Changchun University of Science and Technology，2014：5－23 （in Chinese）. ［楊宇航.數字散斑相關方法的研究 ［D］.吉林：長春理工大學，2014：5－23.］

［2］LIANG Heng.Research on measurement techniques based on digital speckle correlation method ［D］.Anhui：Hefei University of Technology，2014：10－30 （in Chinese）. ［梁恒.基于數字散斑相關方法的測量技術研究 ［D］.安徽：合肥工業大學，2014：10－30.］

［3］LONG Wen，CHEN Le.Hybrid cuckoo search algorithm for solving constrained chemical engineering optimization problems［J］.Journal of Computer Applications，2014，34 （2）：523－527 （in Chinese）.［龍文，陳樂.求解約束化工優化問題的混合布 谷 鳥 搜 索 算 法 ［J］.計 算 機 應 用，2014，34 （2）：523－527.］

［4］Gandomt A，Yang X，Alavi A.Cuckoo search algorithm：Ameta－heuristic approach to solve structural optimization problems ［J］.Engineering with Computer，2013，29 （1）：17－35.

［5］Valian E，Mohanna S，Tavakoli S.Improved cuckoo search algorithm for global optimization ［J］.Int J Communications and Information Technology，2011，1 （1）：31－44.

［6］ZHENG Hongqing，ZHOU Yongquan.Self－adaptive step cuckoo search algorithm ［J］.Computer Engineering and Applications，2013，49 （10）：68－71 （in Chinese）. ［鄭 洪 清，周永權.一種自適應步長布谷鳥搜索算法 ［J］.計算機工程與應用，2013，49 （10）：68－71.］

［7］WANG Fan，HE Xingshi，WANG Yan.The cuckoo search algorithm based on Gaussian disturbance［J］.Journal of Xi’an Polytechnic University，2011，25 （4）：566－569 （in Chinese）.［王凡，賀興時，王燕.基于高斯擾動的布谷鳥搜索算法 ［J］.西安工程大學學報，2011，25 （4）：566－569.］

［8］CHEN Zhixin，LIANG Jin，GUO Cheng.Application of digital speckle correlation method to deformation measurement［J］.Optics and Precision Engineering，2011，19 （7）：1480－1485 （in Chinese）.［陳志新，梁晉，郭成.數字散斑相關法在變形測量中的應用 ［J］.光學精密工程，2011，19 （7）：1480－1485.］

［9］ZHAO Xinchao，LIU Guoli，LIU Huqiu，et al.Particle swarm optimization algorithm base on non－uniform mutation and multiple stages perturbation ［J］.Chinese Journal of Computers，2014，37 （9）：2058－2070 （in Chinese）. ［趙新超，劉國蒞，劉虎球，等.基于非均勻變異和多階段擾動的粒子群優化算法 ［J］.計算機學報，2014，37 （9）：2058－2070.］

［10］DU Yazhi，WANG Xuebin.Digital image correlation method based on particle swarm optimization algorithm without subpixel interpolation ［J］.Computer Engineering and Applications，2012，48 （6）：200－228 （in Chinese）.［杜亞志，王學濱.基于粒子群算法的整像素數字圖像相關方法 ［J］.計算機工程與應用，2012，48 （6）：200－228.］