一種新的自適應閾值SSDA算法

摘 要:在傳統(tǒng)的序慣相似度檢測算法和自適應閾值的序慣相似度檢測算法的基礎上，運用粗匹配中取三點最小值分別作為精匹配中的初始門限值，然后進行三次精匹配，比較三次匹配結果取最小值，轉變?yōu)樽罱K的圖像匹配點，實現(xiàn)一種新的自適應閾值的序慣相似度檢測算法。實驗結果表明，這種改進自適應閾值的序慣相似度檢測算法，在略微降低算法的執(zhí)行速度的同時，能夠很好地保持自適應閾值的序慣相似度檢測算法的圖像匹配準確性，具有很好的實時性。

關鍵詞:序慣相似度檢測算法;自適應閾值;圖像匹配;實時性

中圖分類號:TP274文獻標識碼:A

文章編號:1004-373X(2010)06-135-02

NewAdaptive Threshold SSDA Algorithm

DU Desheng，YE Jianping

(Harbin Polytechnic University，Harbin，150080，China)

Abstract:In the traditional sequential similarity detection algorithm and adaptive threshold sequential similarity detection algorithm，based on the use of coarse match，taking three matches in a fine match，respectively，the minimum initial threshold，and then refining for three matches to compare the results of three matches from the minimum，changing the images for the final match point，a new adaptive threshold of sequential similarity detection algorithm is realized，experimental results show that the improved adaptive sequential threshold similarity detection algorithm，the algorithm in a slightly lower speed at the same time，able to maintain the adaptive threshold of sequential similarity detection algorithm and to match accuracy of the images，it has very good real-time.

Keywords:sequential similarity detection algorithm;adaptive threshold;image matching;real-time

隨著科學技術的發(fā)展，圖像匹配在近代信息處理研究中的地位越來越重要，使用范圍十分廣泛[1]。在圖像匹配技術[2]的研究中，基于統(tǒng)計學理論的匹配技術比較成熟和完善，并且已經(jīng)成功地應用于很多領域，這種匹配技術又分為基于灰度相關的圖像匹配和基于特征的圖像匹配兩個方面，對于前者，基于序貫相似度檢測(SSDA)的算法在實時應用中比較有效。近年來，人們對匹配技術提出很多的改進算法，以期能更好地滿足實時性和匹配準確度的要求。本文在基于序貫相似度檢測(SSDA)算法[5]和基于自適應閾值SSDA算法的基礎上，提出一種改進的自適應閾值SSDA圖像匹配算法。試驗結果表明，改進算法在保持SSDA算法的精度的同時大大提高了運算速度[6]，改進效果明顯。

1 序貫相似度檢測(SSDA)和自適應閾值SSDA算法

設待匹配圖像F為具有L個灰度等級，大小為M×M，即0≤F(i，j)≤L-1;0≤i，j≤M-1。W為具有相同灰度等級的模板圖像，大小為N×N，即0≤W(s，t)≤L-1;0≤s，t≤N-1。模板圖像W疊放在待匹配圖像F上(模板覆蓋下的那塊搜索區(qū)域定義為子圖)依次平移，以找出與給定模板圖像最相似的子圖像位置，即匹配點。

其相似性度量準則為:

D(i，j)=1N∑N-1s=0∑N-1t=0|F(i+s，j+t)-W(s，t)|(1)

SSDA算法隨機不重復地選取待匹配圖像像素，比較的判據(jù)是像素之差的絕對值之和。但這種求和不需要進行到最后，而是在求和的每一步判別其和是否超過某個規(guī)定的閾值，當超過該閾值就停止比較，并把跨越閾值所需的求和步數(shù)作為一個函數(shù)記錄下來，這一函數(shù)在圖像的不相似區(qū)域的值比較小，這也意味著在圖像不相似區(qū)域只耗費很小的計算量。

自適應閾值SSDA算法將待搜索區(qū)域的左上角的點作為相關跟蹤的起始點(x1，y1)，計算目標模板圖像T(x，y)和待搜索圖像S(x，y)之間的匹配累計誤差∑ε，并將其作為自適應閾值序列的初值，然后按照行列順序選擇第二點(x2，y1)進行匹配檢測。在第二點的計算過程中，如果累加和超過了自適應閾值序列的初值，則停止計算，進入下一點的匹配檢測;如果該點匹配檢測完畢后得到的誤差累加和∑ε小于上一點的誤差累加和，則用該點的誤差累加和∑ε取代原來的閾值初值，按照上述方法繼續(xù)進行下去，則可較快找到匹配點。雖然自適應閾值序列的SSDA算法比固定閾值SSDA算法計算量減少，但仍需對(N-M+1)2個參考點遍歷檢測。

2 改進的自適應閾值SSDA算法

該算法將自適應門限序列的SSDA算法的匹配過程分為兩步進行，第一步為粗匹配，第二步為精匹配。

2.1 粗匹配過程

在此過程中要首先確定粗匹配門限初值，利用式(1)計算D(0，0)，在計算過程中選取模板圖像和實測圖像中隔n行和隔m列的像素參與計算。接下來做模板圖像和實測圖像全圖相關匹配。在實測圖像F(x，y)的每一個像素(x，y)上利用式(1)計算D(x，y)。門限T的初始值為D(0，0)，如果在計算像素(x，y)的D(x，y)過程中，D(x，y)累加超過門限T時，停止計算像素(x，y)轉而計算下一像素點;如果計算完像素(x，y)的D(x，y)，D(x，y)不大于門限T時更新門限T并且將此像素的位置坐標賦予相關匹配點，門限T按下述公式取值:

T=T， T≤D(x，y)

T=D， T>D(x，y)(2)

這樣在遍歷完實測圖像F(x，y)后，即可找到粗相關匹配點，所要注意的是在計算過程中應選取實測圖像F(x，y)和模板圖像W(x，y)中隔n行隔m列的像素參與計算。其中，在粗匹配過程中取三個最小值作為精匹配過程中的閾值，進行三次精匹配。

2.2 精匹配過程

在粗匹配過程中得到的三個閾值分別作為精匹配門限初值。假定粗匹配過程得到的粗相關匹配點為Temp，利用式(1)逐行逐列計算Temp點的D(x，y)，并以此D(x，y)作為精匹配門限初值。接下來在以粗匹配點為矩心，尺寸為2n×2m的精相關匹配區(qū)域內(nèi)對上一步得到的粗相關匹配點作修正。修正方法如下:根據(jù)式(1)計算精相關匹配區(qū)域內(nèi)每一像素的D(x，y)，并按上一步敘述的方法和式(2)終止計算和更新精匹配門限值。這樣在遍歷完精相關匹配區(qū)域后即可最終給出精相關匹配點，所要注意的是在按式(1)計算過程中實測圖像F(x，y)和模板圖像W(x，y)中每一個像素都參與計算。

通過此過程，最終得出三個精匹配門限值，然后對它們進行比較，取最小的值作為最終門限值，由此找到了最終匹配點。

3 實驗結果

文中對SSDA算法、自適應閾值的SSDA算法和文中所提出的算法在處理時間上進行了比較，并給出了仿真圖。實驗環(huán)境為:P4處理器，512 MB內(nèi)存的計算機，Windows XP系統(tǒng)，Matlab編程軟件。處理結果，如表1所示。

表1 SSDA各算法處理時間比較

待匹配圖像尺寸512×5121 280×800

模板圖像尺寸80×80163×163

原始SSDA算法9.11 s48.156 s

自適應閾值SSDA算法1.609 s11.375 s

粗精匹配SSDA算法46 ms172 ms

粗三點精匹配SSDA算法110 ms312 ms

粗匹配中得出的最小三點門限值k1=5.784 3，

k2=6.105 9，

k3=6.827 5

k1=3.360 8，

k2=4.713 7，

k3=6.223 5

可見，原始SSDA算法計算量大，耗時長，很難滿足匹配要求;自適應閾值SSDA算法減少了計算量，但速度還是比較慢;粗精匹配算法，省去了大量不必要的計算，但在圖像很大和模板圖像很小的情況下，效果不明顯和有漏掉圖像中最適當位置的危險性;粗三點精匹配算法在保證準確性的同時，大大提高了匹配速度，其中，在圖像很大和模板圖像很小的情況下，粗三點精匹配SSDA算法能夠很好地解決上述問題。通過表1比較顯現(xiàn)出了該算法的優(yōu)越性。仿真圖如圖1，圖2所示。

圖1 待匹配圖像1和模板圖像1及匹配結果

圖2 待匹配圖像2和模板圖像2及匹配結果

4 結 語

新算法在傳統(tǒng)SSDA算法基礎上，運用粗三點精匹配，在算法運算量略微增加的情況下，解決了粗精匹配帶來的不足，更好地保證了匹配的精度。實驗結果表明本算法具有很好的實時性和精確性。

參考文獻

[1]龔聲蓉，劉純平，王強.數(shù)字圖像處理與分析[M].北京:清華大學出版社，2006.

[2]劉征.一種新的圖像匹配算法研究[J].電腦開發(fā)與應用，2005，18(11):25-26，29.

[3][美]Kenneth R Castleman.Digital Image Processing[J].北京:電子工業(yè)出版社，2000.

[4]蔣曉瑜，黃應清.基于小波變化的多分辨模板匹配[J].中國圖像圖形學報，2005(4):304-308.

[5]梁棟，童強，屈磊，等.一種基于極幾何和單應約束的圖像匹配算法[J].系統(tǒng)仿真學報，2006，18(1):44-46.

[6]陳付幸，王潤生.基礎矩陣估計的聚類分析算法[J].計算機輔助設計與圖形學學報，2005，17(10):2 251-2 256.

[7]楊小岡，付光遠，繆棟，等.基于圖像NMI特征的目標識別新方法[J].計算機工程，2002(6):149-151.

[8]劉曙，羅予頻，楊士元.基于臨界特征點的圖像匹配算法[J].計算機工程，2007，33(19):173-175.

[9]陽方林，楊風暴，韋全芳，等.一種新的快速圖像匹配算法[J].計算機工程與應用，2005(5):51-53.

[10]劉忠艷，周波，車向前.一種高效的圖像匹配算法[J].計算機技術與發(fā)展，2009(4):45-47.