張艷珠，王 濤

(沈陽理工大學 自動化與電氣工程學院，沈陽 110159)

序列圖像的快速配準算法研究

張艷珠，王 濤

(沈陽理工大學 自動化與電氣工程學院，沈陽 110159)

基于特征的圖像配準算法至今已取得了很多研究成果，然而在現(xiàn)有的計算機性能條件下依然不能實現(xiàn)實時性的結(jié)果。針對基于快速魯棒特征(Speed Up Robust Features,SURF)的序列圖像拼接算法中圖像配準時間長、計算繁瑣等問題，提出一種結(jié)合感知哈希算法的SURF圖像配準方法。設計了一種快速的搜索算法，對待拼接的相鄰序列圖像進行重合區(qū)域檢測，確定有效的拼接區(qū)域，對有效拼接區(qū)域提取SURF特征點及描述子實現(xiàn)特征的配準。實驗結(jié)果表明，該方法能夠顯著提高匹配速度和效率，提取穩(wěn)定準確的特征點，減少誤匹配，與現(xiàn)有算法相比有更好的實時性。

圖像配準；感知哈希；SURF

圖像拼接技術(shù)是將有重合區(qū)域的小視域圖像(可以是來自不同時間和角度，甚至不同的設備)進行無縫化的拼接，來得到滿足分辨率要求的大視域圖像的一種技術(shù)[1]。這一技術(shù)使得人們用普通的照相機就可以獲得寬視野的全景圖，而不必使用廣角鏡頭等昂貴設備，且可以有效地解決鏡頭邊緣失真的問題?，F(xiàn)在，這一技術(shù)已經(jīng)廣泛應用在遙感地圖測繪、全景圖像拼接、醫(yī)療圖像分析領(lǐng)域等。

圖像配準是圖像拼接過程的關(guān)鍵技術(shù)，配準算法的優(yōu)劣直接影響最后結(jié)果的質(zhì)量，同時配準過程的效率也決定了整個拼接過程的實時性。關(guān)于配準算法已有很多非常成熟的研究成果，如Richard Szeliski[2]提出的基于投影變換模型的配準算法，提出了一種2D空間的八參數(shù)投影模型來實現(xiàn)配準；Kuglin等[3]提出的相位相關(guān)法，借助傅立葉變換思想，將圖像信息變換到頻域范圍內(nèi)計算平移矢量；Xiaowei Han等[4]提出的灰度相關(guān)的匹配算法，先將兩幅圖像轉(zhuǎn)化成二值化的圖像粗略計算出匹配位置，然后采用序貫相似性方法完成精確匹配?；谔卣鞯膱D像配準算法是以圖像的特征點為基礎進行匹配的一種算法，該類算法具有比較高的魯棒性。其中，里程碑式的方法為Lowe提出的尺度不變特征變換(Scale Invariant Feature Transform，SIFT)算法[5]和Bay等人提出的快速魯棒特征(Speeded Up Robust Features，SURF)算法[6]。SIFT特征檢測算法通過形成關(guān)鍵點的局部特征描述子作為兩幅拼接圖像的相似特征判別依據(jù)，具有良好的尺度、光照及空間旋轉(zhuǎn)不變性，被認為是最流行且有效的特征提取方法；受到SIFT算法的啟發(fā)，SURF算法對SIFT算法進行了計算速度方面的改進，應用了簡化近似的思想，巧妙地運用了積分圖像和DoH(Determinant of Hessian)近似,其優(yōu)點是速度快于SIFT，有實驗表明[7]，SURF中采用的DoH近似算法比SIFT中的DoG算法快3倍，綜合性能優(yōu)于SIFT算法。但是，在實際的工程應用中，如果沒有專用的圖形計算加速設備，在現(xiàn)有計算機性能條件下難以滿足實時性的要求，例如某些規(guī)定在幾秒甚至幾毫秒時間內(nèi)完成特征檢測、特征匹配、目標識別等一系列操作的場合，現(xiàn)有算法則難以完成。

在研究了基于特征的圖像拼接算法之后，本文提出結(jié)合感知哈希算法和SURF算法的序列圖像快速拼接方法。經(jīng)典的SURF算法是首先對待拼接的圖像進行所有特征點的提取，然后進行隨后的特征點匹配等操作，本文提出的方法是在特征檢測和提取之前，首先運用感知哈希算法進行拼接區(qū)域的檢測，然后在有效拼接區(qū)域內(nèi)進行特征檢測和提取，省去對無關(guān)區(qū)域的檢測操作，這可以大大減少SURF特征提取的運算量和運算時間，同時可以減少誤匹配對，提高配準的準確性和效率。

1 圖像感知哈希算法

1.1 感知哈希算法原理

感知哈希[8](Perceptual Hash)和加密算法中所說的哈希函數(shù)，或散列函數(shù)不同，它是根據(jù)圖像內(nèi)容的特征生成該圖像的一個二進制形式的“指紋”字符串(Fingerprint),如果兩幅圖像是相同或相似的，則它們的感知哈希值就是相同或近似的，即“指紋”相似度越高，則圖像越接近。所以該算法常常用于相同或相似文件的檢測，例如以圖識圖的搜索算法。常用的感知哈希算法有均值哈希和基于離散余弦變換(Discrete Cosine Transformation)的DCT hash算法，算法流程圖如圖1所示。

圖1 感知哈希算法流程圖

1.2 感知哈希相似度檢測

哈希算法實例如圖2所示，相對于圖2a，圖2b、圖2c、圖2d分別發(fā)生了尺度、旋轉(zhuǎn)、亮度及對比度的變化。

采用均值哈希和DCT哈希算法進行相似度檢測，算法實現(xiàn)步驟：

(1)將圖像轉(zhuǎn)化為256級灰度圖像，縮小圖像尺寸到8×8或32×32像素。均值哈希為8×8，DCT哈希為32×32。這樣做去除了圖像的高頻信息，保留了圖像的輪廓等低頻信息。以圖2a為例，結(jié)果如圖3所示。

圖2 哈希算法實例圖

圖3 圖2a灰度轉(zhuǎn)化與尺寸縮小

(2)將圖像的顏色空間轉(zhuǎn)化為64級灰度。

(3)在均值哈希算法里，計算所有像素的灰度平均值；在DCT哈希里，計算圖像的DCT變換，得到32×32的DCT系數(shù)矩陣，只保留左上角8×8的系數(shù)，因為這部分保留了圖像低頻的主要部分，并計算系數(shù)的平均值。計算結(jié)果如圖4、表1所示。

圖4 圖2a DCT變換圖

圖2a圖2b圖2c圖2d灰度均值24243737DCT均值37283852128456587

(4)生成哈希值。均值哈希中，像素灰度值大于等于平均值置為1，否則置為0，結(jié)果如圖5所示；DCT哈希類似，通過和系數(shù)均值的比較生成哈希值，結(jié)果如圖6所示。

圖5 均值哈希算法哈希值結(jié)果

圖6 DCT哈希算法哈希值結(jié)果

得出圖像的哈希值之后，可以通過圖像哈希值的漢明距離(Hamming Distance)來判斷兩幅圖像的相似程度。相似度計算公式為

相似度檢測過程中，同時采用計時函數(shù)clock()對算法的運算時間進行監(jiān)測，計時單位為毫秒，計時代碼如下：

clock_t start_time = clock();

{//相似度檢測算法}

clock_t end_time = clock();

cout<<“time is∶” <(end_time-start_time) / CLOCKS_PER_SEC* 1000 << “ms” <

實驗結(jié)果數(shù)據(jù)如表2所示。

表2 相似度檢測結(jié)果

從表2實驗結(jié)果來看，哈希算法在圖像相似性檢測中有很好的性能，對各種圖像變化檢測的準確率能達到50%以上，尤其是在尺寸變化、亮度及對比度變化上檢測結(jié)果非常準確，且運算速度非?？欤脮r在十幾毫秒之內(nèi)。DCT哈希算法和均值哈希算法相比，相似度結(jié)果更加準確，在耗時方面只是略慢于均值哈希，綜合性能較好。本文在序列圖像拼接前，先采用DCT哈希算法進行圖像重合區(qū)域的檢測，從而快速確定匹配區(qū)域，在匹配區(qū)域進行拼接操作，可以大大提高拼接效率。

2 重合區(qū)域搜索算法

圖像的重合區(qū)域指相鄰圖像之間相同的圖像范圍。常用的算法有基于模板的匹配算法。即在其中一幅圖上選取一塊區(qū)域作為檢測的模板，在另一幅圖中進行檢索，找到相同或者相似的區(qū)域，以確定重合區(qū)域，這種方法計算繁瑣，而且容易受到光照等變化的影響，在實際運用中不具有實時性。

本文結(jié)合感知哈希算法提出一種簡單有效的重合區(qū)域檢測算法，算法原理如圖7所示。根據(jù)實際情況，可以知道大多數(shù)序列圖的重合范圍在30%～50%之間，所以設計了參數(shù)λ來表示重合范圍占原圖百分比的最優(yōu)值。設初值從圖像的20%處開始(圖像1從右邊開始算起，圖像2從左邊開始算起)，隨著λ逐漸增大，檢測區(qū)域也逐漸增大，在λ增大的過程中，逐步匹配檢測區(qū)域的相似度。

圖7 搜索算法原理示意圖

由實際情況可知，隨著λ的變化，被檢測區(qū)域的相似度曲線如圖8所示。

圖8 檢測區(qū)域相似度曲線

在λ的搜索過程中，存在一個λ值使待檢測區(qū)域的相似度達到最高，此時λ所找到的區(qū)域就是兩幅圖像重合的區(qū)域，即檢測區(qū)域哈希值的最優(yōu)匹配。為了使算法能夠較為準確地確定重合區(qū)域，同時又不增加算法的時間復雜度，需要對λ的搜索速度進行試驗以滿足要求。以圖9兩組圖像為實驗對象，圖9a組為重合區(qū)域較大的情況，圖像像素大小為3264×1840，圖9b組為重合區(qū)域較小的情況，圖像像素大小為3264×2448。對比每組圖像在不同搜索步長、次數(shù)、準確率和耗時等方面的表現(xiàn)。圖9a組實驗結(jié)果如表3所示，圖9b組實驗結(jié)果如表4所示。

圖9 搜索算法實驗圖

表3 圖9a組實驗結(jié)果數(shù)據(jù)

表4 圖9b組實驗結(jié)果數(shù)據(jù)

對于圖9a組實驗對象，由表3可知，當搜索步長為1%和3%時，算法均能達到設定的相似度閾值，且λ值結(jié)果相同均為0.47，與實際情況相符。3%的搜索步長更快達到最優(yōu)值，綜合性能比1%快3倍左右。而從5%的搜索步長來看，結(jié)果并沒有達到設定的閾值，且λ也沒有達到最優(yōu)解，由此可知，5%的步長設定偏高，不能檢測到最優(yōu)匹配。對于圖9b組實驗對象，結(jié)論與圖9a組類似，即在重合區(qū)域較小的情況下(重合區(qū)域在30%左右)，3%的步長也能較快地找到最優(yōu)匹配，綜合性能最優(yōu)。

因此，在重合區(qū)域確定時，可以以待拼接序列圖像3%的幅度作為搜索步長，結(jié)合感知哈希算法的快速性，便可以很快地確定重合區(qū)域。

3 基于SURF的圖像配準

3.1 特征點提取

SURF算法中感興趣點的檢測主要用到了海森矩陣(Hessian Matrix)近似法。其中要借助積分圖像(Integral Image),將圖像在高斯微分模板下的濾波變?yōu)榉e分圖像的加減運算，這樣可以大大減少運算時間。積分圖由Viola等[9]提出，Simard等[10]將其用于盒子濾波(Box Filter)。

設任意一點(i,j)的像素值I(i,j)為圖像左上角到點(i,j)的對角線區(qū)域灰度值總和，為

(1)

p(i′,j′)表示點(i′,j′)的灰度值。如圖10所示，在求區(qū)域W的像素總灰度值時，不管W怎么變化，都能通過該區(qū)域的4個角點，即(i1,j1)、(i2,j2)、(i3,j3)、(i4,j4)的灰度值加減得到，為∑w=I(i4,j4)-I(i2,j2)-I(i3,j3)+I(i1,j1)

(2)

圖10 積分圖像計算窗口內(nèi)灰度和

設圖像I中任意一個點X=(x,y)，在尺度參數(shù)是σ下的Hessian矩陣H(X,σ)為

(3)

其中，卷積的近似過程是用盒子濾波(BoxFilter)模板代替原來的高斯模板，模板區(qū)域里分為幾個小區(qū)域，每個小區(qū)域里都是相同的權(quán)值，如圖11所示。其中，白色部分權(quán)值填1，黑色部分填-1，灰色部分為0。

圖11 高斯二階微分模板簡化

文獻[6]中設定模板尺寸為9×9，σ=1.2，對圖像進行濾波和特征檢測，Dxx、Dxy和Dyy分別代表不同模板與圖像濾波的結(jié)果，則Hessian矩陣的行列式為

Det(Happrox)=DxxDyy-(0.9Dxy)2

(4)

Dxx、Dxy和Dyy的計算采用對積分圖像的加減運算。用這個行列式的值代表圖像中關(guān)鍵點的響應值，對整幅圖像進行搜索就可以形成全圖的關(guān)鍵點響應圖。然后改變?yōu)V波模板的大小，分別與圖像做卷積運算，便可以形成不同尺度下的關(guān)鍵點響應值圖像，找出響應值中的極值點，完成特征點的提取操作。

3.2 特征點描述子

m=∑dx+∑dy

(5)

(6)

主方向即：θ′=θ|max(m)。

接下來就是生成特征描述子，具體步驟為：

(1)以特征點為中心，將邊長20s的矩形窗口劃分成4×4的子塊，每個子塊有25個像元。

(2)使用尺度為2s的小波對子塊進行響應值計算，分別得到沿主方向的dy和垂直主方向的dx。得到每個子塊的矢量：

V子塊=[∑dx,∑|dx|,∑dy,∑|dy|]

(7)

共有16個子塊，則特征描述子共有16×4=64維。

這樣，SURF特征描述子不僅具有尺度和旋轉(zhuǎn)不變性，而且小波響應本身具有亮度不變性，歸一化后也有對比度不變性。使得算法能夠得到比較穩(wěn)定的興趣點。

4 實驗分析與比較

實驗主要對比原SURF算法和本文算法在圖像配準方面的效果。實驗源圖像如圖12所示。實驗工具借助Matlab R2012b和Visual Studio 2013軟件，運行條件為Windows7系統(tǒng)，CPU主頻2.67GHz，內(nèi)存2GB。

圖12 實驗源圖像

SURF算法特征點匹配如圖13所示，配準結(jié)果如圖14所示。

采用感知哈希和本文設計的搜索算法對源圖像重合區(qū)域進行檢測，重合度檢測閾值設定為0.8，λ初值為0.1，重合區(qū)域檢測結(jié)果如圖15所示，圖中矩形區(qū)域即重合區(qū)域，重合區(qū)域特征點匹配如圖16所示。

圖13 SURF特征點匹配圖

圖14 SURF算法配準結(jié)果

圖15 重合區(qū)域檢測結(jié)果

圖16 重合區(qū)域特征點匹配

重合區(qū)哈希值結(jié)果如圖17所示，檢測數(shù)據(jù)結(jié)果如表5所示。

圖17 重合區(qū)域哈希值結(jié)果

搜索次數(shù)λ相似度/%耗時/ms130468125160

本文算法匹配結(jié)果如圖18所示，矩形區(qū)域為標注出的重合區(qū)域。SURF算法和本文算法數(shù)據(jù)對比如表6所示。

圖18 本文算法匹配結(jié)果

特征點數(shù)SURF圖12a圖12b131156本文算法圖12a圖12b5683匹配對數(shù)2919檢測耗時/ms32941423

由實驗結(jié)果容易看出，本文算法在保證配準質(zhì)量的前提下，獲得了更快的匹配速度。在特征點檢測上，由于先搜索了有效的重合區(qū)域，所以省去了無關(guān)區(qū)域的特征點檢測，在特征點數(shù)目的檢測耗時上比原算法縮短了一半多，而特征點匹配對的數(shù)目為19對，與原算法相比保留了絕大部分匹配對，保證了圖像的配準質(zhì)量。

5 結(jié)束語

將圖像感知哈希算法融合到圖像的配準過程中，設計了有效的搜索算法，可以快速準確地確定出拼接區(qū)域，從而大大減少了特征檢測的運算量和時間。實驗結(jié)果表明，結(jié)合感知哈希的SURF圖像配準算法具有更高的匹配效率，且匹配效果能夠滿足視覺要求。研究主要針對圖像間存在先

后關(guān)系的序列圖像，如何設計出適合更復雜情況的配準算法有待于進一步研究。

[1]杜往澤,宋執(zhí)環(huán),閆文博,等.單攝像頭旋轉(zhuǎn)監(jiān)控下的快速圖像拼接[J].中國圖象圖形學報,2016,21(2):245-254.

[2]R Szeliski.Video Mosaics for Virtual Environment[J].IEEE Computer Graphics and Applications,1996,16(2):22-30.

[3]C Kuglin,D Hines.The Phase Correlation Image Alignment Method[C] // IEEE International Conference on Cybernetics and Society.New York,1975:163 -165.

[4]Xiaowei Han,Lei Yan,Hongying Zhao.An approach of fast image mosaic based on binary region segmentation[C]//27th International Congress on High-Speed Photography and Photonics.SanJose,2007:627957.

[5]Lowe D G.Object recognition from local scale-invariant features[C]//Proceedings of the IEEE International Conferenceon Computer Vision.Corfu,Greece,1999:1150-1157.

[6]Herbert Bay,Andreas Ess,Tinne Tuytelaars,et al.Speeded-Up Robust Features (SURF) [J].Computer Visionand Image Understanding,2008,110(3):346-359.

[7]Juan L,Gwun O.A comparison of sift,pca-sift and surf[J].International Journal of Image Processing (IJIP),2009,3(4):143-152.

[8]李雨佳,李京兵.基于DCT和感知哈希的紋理防偽標簽鑒別算法[J].計算機應用研究,2014,31(12):3734-3737.

[9]P Viola,M Jones.Rapid object detection using a boosted cascadeof simple features[C]//Computer VisionandPatternRecognition.Kauai,2001:511-518.

[10]P Simard,L Bottou,P Haffner,et al.Boxlets:a fast convolution algorithm for signal processing and neural networks[C]// Conference on Advances in Neural Information Processing Systems.Denver,1998:571-577.

(責任編輯：馬金發(fā))

Research on Fast Registration Algorithm for Sequence Image

ZHANG Yanzhu，WANG Tao

(Shenyang Ligong University，Shenyang 110159，China)

The great progress has been made in the feature-based image registration algorithm,however,it is still difficult to achieve real-time results under the existing conditions of computer performance.For the issue of high complexity for computing time in image registration algorithm based on speed up robust features(SURF) in sequence images,a method is proposed on the basis of perceptual hash algorithm by using fast SURF.Firstly,a fast search algorithm is designed，and the overlap area in two adjacent images is detected,which determines the effective region.Then,feature points and SURF descriptor are extracted in this region to complete feature points matching.Experimental results show that the proposed method can significantly improve matching speed and efficiency within stable and accurate feature points,reducing mismatch and has better real-time performance in comparison with the existing algorithms. Key words： image registration;perceptual hash;SURF

2016-06-23

張艷珠(1971—)，女，副教授，博士，研究方向：目標識別，分數(shù)階控制，智能算法。

1003-1251(2017)03-0058-07

TP391

A