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

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

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

關(guān)鍵詞：魚群算法;小波變換;快速圖像匹配

1 ? ?基本人工魚群優(yōu)化算法

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

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

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

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

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

人工魚群優(yōu)化算法還需設(shè)立公告板，公告板一直維持也僅維持最優(yōu)值。在算法結(jié)束時，公告板中數(shù)據(jù)就是我們搜索的全局最優(yōu)解。

2 ? ?小波變換

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

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

分解過程如圖1所示。

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

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

3.1 ? ?算法設(shè)計

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

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

3.2 ? ?算法實現(xiàn)

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

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

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

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

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

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

3.3 ? ?實驗結(jié)果與分析

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

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

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

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

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

3.3.2 ? ?噪聲環(huán)境下算法的魯棒性及快速性測試

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

4 ? ?結(jié)語

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

[參考文獻]

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

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

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

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

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

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

收稿日期：2020-08-05

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