基于AFSA和小波變換的快速圖像匹配算法研究

何志明 閆文耀 李顯峰 陳圣偉 熊琴

摘要：提出了一種基于人工魚群算法（簡稱AFSA）和小波變換的快速圖像匹配算法，該算法不但能提高匹配速度，而且增強了匹配算法的抗噪性能和魯棒性。

關鍵詞：魚群算法;小波變換;快速圖像匹配

1 ? ?基本人工魚群優化算法

人工魚群算法（簡稱AFSA）是李曉磊在2002年提出的：假設搜索目標空間是一個D維空間，在搜索空間內有N條人工魚，那么第i條魚的狀態向量就可表示為：xi=（xi1，xi2，xi3，…，xiD），其中i=1，2，…，N。我們可以將目標函數適應度表示成食物的濃度：y=f（x）。每條人工魚的狀態就是潛在的解，通過代入xi，計算出yi，然后再通過比較yi的大小來衡量xi的質量。本文討論的最優化都是指最大，因為求解極大、極小問題可以相互轉換。

人工魚群優化算法主要模擬自然魚群覓食的過程，其主要行為有覓食、群聚、追尾和選擇四種。在算法開始時，首先初始化一組隨機解作為人工魚群的初始種群，然后人工魚群將依據周圍環境情況在覓食、群聚或是追尾行為中選擇最優行為執行，并反復執行該過程，也就是迭代更新，直到找到最優解。所以說，人工魚群具有一定自適應能力。人工魚群的主要行為有以下幾種：

（1）覓食行為。假設xi、yi分別是第i條人工魚的當前狀態和適應度值，然后該人工魚將在其感知范圍內隨機搜索并選擇適應度函數值大于yi的狀態xv，隨后向xv前進，得到一個較好的新狀態xinext，若達到最大預設試探次數也無法發現理想xv，那么人工魚就在視野感知范圍內隨機移動一步，從而得到新狀態xinext。

（2）群聚行為。人工魚的群聚行為是指人工魚在游動過程中，盡量向魚群中心移動，但又要控制與其他人工魚的距離，從而避免過度擁擠。設第i條人工魚視野感知范圍內的人工魚集合為Sj，且人工魚數目記為Nf，若Sj為不為空，表明xi的視野感知內存在其他人工魚，即Nf>1，若Nf/N（N為人工魚群種群大小）小于給定閾值δ，說明中心位置不擁擠，向中心位置移動一步。

（3）追尾行為。設xi、yi分別是人工魚的當前狀態及適應度函數值，xmax、ymax分別是其感知范圍內適應度函數值最大的人工魚及適應度函數值。若ymax>yi，統計xmax周圍的人工魚數目Nf，如果滿足ymax>yi和Nf·ymax<δ·yi（δ>1），則人工魚執行追尾行為，否則繼續覓食。

人工魚群優化算法還需設立公告板，公告板一直維持也僅維持最優值。在算法結束時，公告板中數據就是我們搜索的全局最優解。

2 ? ?小波變換

分層搜索是一種極為有效且簡單的減小搜索空間的方法，能較大程度地提高搜索效率。分層搜索的精髓就是由粗到細地搜索。

小波分解圖像的大致過程就是把原圖像按不同的順序在水平和垂直方向進行低通濾波、高通濾波以及抽取，得到不同的分解圖和細節圖像。

分解過程如圖1所示。

3 ? ?基于人工魚群和小波變換的快速圖像匹配算法

根據小波變換和人工魚群算法原理，本文提出了一種抗噪性較好、匹配速度快且匹配率較高的快速圖像匹配算法，簡稱WAFSA。

3.1 ? ?算法設計

小波分解層數越多，圖像越小，匹配時間也將迅速遞減，但圖像的信息也會減少，所以匹配概率也會隨之降低。但在分層數小于5時，圖像匹配概率基本能保持97%以上。因此，若圖像較大，那么我們可以將其多分解幾層，若圖像本身就較小，那么就應該減少分解層數，因為匹配速度主要由運行計算量決定。本圖像分層采用三層小波分解以平衡匹配速度和精度之間的矛盾。

在該匹配算法中，圖像的像素坐標（i，j）可表示為一個二維向量xij，然后我們用該二維向量表示一條人工魚。搜索空間是原圖像進行三層小波分解后的第三層低頻圖像，并將新搜索圖像分成L個小區域，每個區域內隨機產生Number/L條人工魚，Number是人工魚群的初始種群大小。

3.2 ? ?算法實現

基于人工魚群和小波變換的快速圖像匹配算法基本步驟如下：

（1）將搜索圖像、模板圖像分別進行三層小波分解，然后將第三層分解層的低頻圖像作為新的搜索圖像及模板圖像。

（2）利用改進后的魚群算法搜索新模板圖像在新搜索圖像中的最大匹配點（i，j）。

（3）根據相鄰尺度下像素點間的位置關系找出第L層的像素點系數（i，j）在第L-1層的對應像素點系數（2×i，2×j），并找出所有與點（2×i，2×j）距離為3的像素點構成點（i，j）在L-1層的候選點集。也可根據需要擴大半徑，增加候選點集，提高匹配精度。

（4）在L-l層上的候選點集范圍內進行匹配，找出最大匹配點。

（5）重復（3）（4）步驟直到找到第1層上的最大匹配點，即為最佳匹配點。

3.3 ? ?實驗結果與分析

本實驗環境為Pentium Ⅳ 2.4 GHz PC，MATLAB7.0。為減小實驗中隨機性帶來的影響，所有實驗次數均為100次。實驗結果中，若匹配點與理想匹配點的誤差在1個像素內，則認為正確匹配;運行時間則是100次實驗的平均時間。

3.3.1 ? ?算法的準確性與快速性測試

本實驗搜索圖像為512×512的lena圖像，模板圖像則是在該圖中以（200，200）為左上角截取的大小為200×200的子圖，因此，理想匹配位置就是點（200，200）。本實驗中，小波分解層數為3層，魚群種群初始大小為10，最大循環次數Try_number為8，迭代次數T為50，測試WAFSA的準確性與快速性。

下面同時給出傳統的序貫相似性檢測算法（SSDA）實驗結果進行比較，以衡量新算法的性能。實驗結果如圖2所示，測試數據如表1所示。

圖2（c）中框選部分即為模板圖像在搜索圖像中的準確位置，該圖表明本匹配算法得到的匹配圖中，模板圖像和搜索圖像嵌接較為自然且光滑，紋理也銜接自然、完整。而從表1中我們可以發現：兩個算法的匹配正確率都是100%，但WAFSA的匹配時間僅為SSDA算法的4.6%，因此，WAFSA具有較好的快速性。

3.3.2 ? ?噪聲環境下算法的魯棒性及快速性測試

現在測試WAFSA的魯棒性，分別將強度為0.2的椒鹽噪聲，強度0.2的斑點噪聲加入到搜索圖像中，然后再進行實驗。實驗結果如圖3所示，測試數據如表2所示。

4 ? ?結語

本文首先介紹了基本人工魚群算法及其主要過程，然后介紹了小波分解的基本思想，再根據小波多分辨率提出了一種新的快速圖像匹配算法——基于人工魚群優化算法和多分辨率小波變換的快速圖像匹配算法并進行了進行實驗，最后對結果進行了對比分析。

[參考文獻]

[1] 李曉磊，路飛，田國會，等.組合優化問題的人工魚群算法應用[J].山東大學學報（工學版），2004，34（5）：64-67.

[2] 董永峰，雷曉輝，董瑤，等.改進ORB特征提取與匹配算法研究[J].傳感器與微系統，2020，39（4）：59-62.

[3] 趙振華，郝曉弘.局部保持鑒別投影及其在人臉識別中的應用[J].電子與信息學報，2013，35（2）：463-467.

[4] 郭倩茜.圖像匹配的主要方法分析[J].科技創新與應用，2016（20）：81.

[5] 沈軍宇，李林燕，夏振平，等.一種基于YOLO算法的魚群檢測方法[J].中國體視學與圖像分析，2018，23（2）：174-180.

[6] 李琳.小波變換在圖像壓縮中的應用[J].數字技術與應用，2012（3）：84.

收稿日期：2020-08-05

作者簡介：何志明（1979—），女，重慶人，講師，研究方向：圖像處理和模式識別。