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

關(guān)鍵詞:序慣相似度檢測(cè)算法;自適應(yīng)閾值;圖像匹配;實(shí)時(shí)性

中圖分類號(hào):TP274文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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

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

1 序貫相似度檢測(cè)(SSDA)和自適應(yīng)閾值SSDA算法

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

其相似性度量準(zhǔn)則為:

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

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

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

2 改進(jìn)的自適應(yīng)閾值SSDA算法

該算法將自適應(yīng)門限序列的SSDA算法的匹配過(guò)程分為兩步進(jìn)行，第一步為粗匹配，第二步為精匹配。

2.1 粗匹配過(guò)程

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

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

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

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

2.2 精匹配過(guò)程

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

通過(guò)此過(guò)程，最終得出三個(gè)精匹配門限值，然后對(duì)它們進(jìn)行比較，取最小的值作為最終門限值，由此找到了最終匹配點(diǎn)。

3 實(shí)驗(yàn)結(jié)果

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

表1 SSDA各算法處理時(shí)間比較

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

模板圖像尺寸80×80163×163

原始SSDA算法9.11 s48.156 s

自適應(yīng)閾值SSDA算法1.609 s11.375 s

粗精匹配SSDA算法46 ms172 ms

粗三點(diǎn)精匹配SSDA算法110 ms312 ms

粗匹配中得出的最小三點(diǎn)門限值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算法計(jì)算量大，耗時(shí)長(zhǎng)，很難滿足匹配要求;自適應(yīng)閾值SSDA算法減少了計(jì)算量，但速度還是比較慢;粗精匹配算法，省去了大量不必要的計(jì)算，但在圖像很大和模板圖像很小的情況下，效果不明顯和有漏掉圖像中最適當(dāng)位置的危險(xiǎn)性;粗三點(diǎn)精匹配算法在保證準(zhǔn)確性的同時(shí)，大大提高了匹配速度，其中，在圖像很大和模板圖像很小的情況下，粗三點(diǎn)精匹配SSDA算法能夠很好地解決上述問(wèn)題。通過(guò)表1比較顯現(xiàn)出了該算法的優(yōu)越性。仿真圖如圖1，圖2所示。

圖1 待匹配圖像1和模板圖像1及匹配結(jié)果

圖2 待匹配圖像2和模板圖像2及匹配結(jié)果

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

[6]陳付幸，王潤(rùn)生.基礎(chǔ)矩陣估計(jì)的聚類分析算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17(10):2 251-2 256.

[7]楊小岡，付光遠(yuǎn)，繆棟，等.基于圖像NMI特征的目標(biāo)識(shí)別新方法[J].計(jì)算機(jī)工程，2002(6):149-151.

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

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

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