基于SUSAN分層快速角點(diǎn)檢測(cè)的改進(jìn)算法

趙 杰，馬海超

（河北大學(xué) 電子信息工程學(xué)院，河北 保定 071000）

角點(diǎn)是圖像的重要特征，它在保留圖像重要信息的同時(shí)可有效減少數(shù)據(jù)量，而且對(duì)透視變換及變形都具有較強(qiáng)的魯棒性[1]。利用角點(diǎn)特征可顯著提高立體視覺匹配和三維重建算法的效率，因此，角點(diǎn)檢測(cè)在圖像匹配以及三維重建中具有重要意義。

角點(diǎn)檢測(cè)算法主要分為基于圖像邊緣法[2]和基于圖像灰度法[3]兩大類?；趫D像邊緣法對(duì)邊緣提取算法的依賴性較大，計(jì)算復(fù)雜且不能很好地定位角點(diǎn)?；趫D像灰度的方法則不存在上述缺點(diǎn)，該方法又分為兩類：一類是基于圖像導(dǎo)數(shù)的Plessey[4]算法，其可靠性高，但計(jì)算復(fù)雜，速度慢；而另一類是基于圖像灰度對(duì)比關(guān)系算法，如SUSAN算法，此類算法定位準(zhǔn)確，具有積分特性，無需求導(dǎo)運(yùn)算。因此，該算法在抗噪能力上具有較大優(yōu)勢(shì)，運(yùn)算速度有所提高，但仍不能滿足實(shí)時(shí)性要求。

基于上述分析，這里引入基于SUSAN算法的分層快速角點(diǎn)檢測(cè)法與角點(diǎn)“性能好壞”判別算法相結(jié)合的角點(diǎn)檢測(cè)法。采用由粗到細(xì)的分層策略，通過小波變換對(duì)角點(diǎn)進(jìn)行粗略定位，再經(jīng)“好壞”判別減少角點(diǎn)數(shù)量，最后運(yùn)用SUSAN算法對(duì)角點(diǎn)進(jìn)行精細(xì)查找，準(zhǔn)確定位角點(diǎn)，從而有效解決了基于SUSAN算法的分層快速角點(diǎn)檢測(cè)法在對(duì)實(shí)際圖像進(jìn)行角點(diǎn)檢測(cè)時(shí)，角點(diǎn)數(shù)量太多，不利于角點(diǎn)匹配，計(jì)算速度慢的問題。

1 基于SUSAN的分層快速角點(diǎn)檢測(cè)算法

基于SUSAN的分層快速角點(diǎn)檢測(cè)算法是針對(duì)SUSAN算法在角點(diǎn)檢測(cè)中運(yùn)算速度較慢的問題而提出的。該算法根據(jù)圖像中像素周圍圖像灰度的相似性和角點(diǎn)的特性,引入提升小波變換理論，采用由粗到細(xì)的分層策略，從而提高了運(yùn)算速度。

1.1 提升小波變換理論

傳統(tǒng)的小波變換受到Fourie變換的局限,而不依賴于Fourie變換的小波提升技術(shù)[5]實(shí)現(xiàn)了定位運(yùn)算，可節(jié)省存儲(chǔ)空間，提高運(yùn)算速度。圖1為提升小波變換原理框圖。

圖1 提升小波變換原理框圖

提升小波變換過程主要包括分裂、預(yù)測(cè)和更新3個(gè)步驟。其中，分裂是將原始信號(hào)分為兩個(gè)互不相交的子集，最簡(jiǎn)單的分裂方法是將信號(hào)分為偶數(shù)序列和奇數(shù)序列，即

式中，S 表示分解操作；s，d 表示信號(hào)；j表示層數(shù)；e，o分別表示偶數(shù)序列和奇數(shù)序列。

預(yù)測(cè)是根據(jù)原始數(shù)據(jù)的相關(guān)性，采用偶數(shù)序列的預(yù)測(cè)值P（s）預(yù)測(cè)奇數(shù)序列的值，用來表示兩者逼近程度，即

更新是保證變換后的圖像保持原始圖像的屬性，用U產(chǎn)生一個(gè)更好的數(shù)值保留原始圖像的一些特性，即

1.2 由粗到細(xì)的分層快速角點(diǎn)檢測(cè)算法

直接運(yùn)用SUSAN算法檢測(cè)角點(diǎn)，速度較慢。而若能快速找到角點(diǎn)的粗略位置，再進(jìn)行準(zhǔn)確判斷，則可大大節(jié)約時(shí)間。

小波變換后，原始圖像分為低頻區(qū)域和高頻區(qū)域。低頻區(qū)域是原始圖像的近似表示，高頻區(qū)域是原始圖像的細(xì)節(jié)表示，能夠描述細(xì)節(jié)變化。在圖像中，大部分像素周圍的灰度值相似，但角點(diǎn)附近像素的灰度值變化較大，且能反映小波變換的高頻區(qū)域。小波變換的這種特性以及提升小波變換的高速算法為快速找到角點(diǎn)的大概位置提供條件。

分層檢測(cè)法先對(duì)輸入的圖像進(jìn)行提升小波行變換，再進(jìn)行提升小波列變換，在其高頻區(qū)域很容易檢測(cè)到角點(diǎn)的粗略位置，最后用SUSAN算法精確定位角點(diǎn)。使用由粗到細(xì)的分層策略可大大減少運(yùn)算時(shí)間。

快速、高效地粗略定位角點(diǎn)位置的關(guān)鍵在于快速、有效的提升小波變換。行、列圖像的提升小波變換相似，這里以行圖像為例說明。圖2表示一行中兩種典型圖像。圖中黑、白色圓圈表示像素的灰度，分別代表目標(biāo)和背景。奇、偶表示目標(biāo)從奇數(shù)或偶數(shù)位置開始。將原始圖像按奇、偶分開，分裂后的結(jié)果如圖3所示。

圖2 一行中兩種典型圖像

圖3 圖像的奇偶分裂結(jié)果

最簡(jiǎn)單的方法是小波預(yù)測(cè)法，有Harr小波預(yù)測(cè)和線性小波變換預(yù)測(cè)2種方案。如果采用Harr小波預(yù)測(cè)，即

預(yù)測(cè)后，從奇數(shù)位置開始的行由細(xì)節(jié)圖像可以準(zhǔn)確定位原來的起始位置（2k+1），但從偶數(shù)位置開始的行，由于其細(xì)節(jié)圖像無法提供細(xì)節(jié)，不能準(zhǔn)確判定角點(diǎn)的位置，如圖4所示。

圖4 圖像的Harr小波預(yù)測(cè)

結(jié)合實(shí)時(shí)性要求及檢測(cè)效果，采用線性小波變換的預(yù)測(cè)方法最好。即采用

線性小波預(yù)測(cè)可大大減少數(shù)據(jù)量，適合搜索角點(diǎn)的粗略位置。如圖5所示，目標(biāo)從奇數(shù)位置開始的行，根據(jù)其細(xì)節(jié)圖像，計(jì)算出的起始位置為2k，可準(zhǔn)確定位原來的起始位置。目標(biāo)從偶數(shù)位置開始的行，計(jì)算出的起始位置為（2k-1），只出現(xiàn)1個(gè)偏移，為精確定位角點(diǎn)創(chuàng)造條件。

圖5 圖像的線性小波預(yù)測(cè)

2 角點(diǎn)“好壞”判定函數(shù)的引入

SUSAN分層快速角點(diǎn)檢測(cè)法在檢測(cè)角點(diǎn)時(shí)只能判斷是否為角點(diǎn)，不能判斷角點(diǎn)的“好壞”程度，這樣在檢測(cè)實(shí)際圖像角點(diǎn)時(shí)應(yīng)用效果不佳。通常一幅實(shí)際圖像的特征點(diǎn)很多，若全部檢測(cè)出來，會(huì)增加后續(xù)匹配的計(jì)算量。而如果隨意去除部分角點(diǎn)，則會(huì)使圖像缺失部分重要角點(diǎn)。雖然通過調(diào)整每幅圖像閾值能夠拼湊合適的角點(diǎn)數(shù)量，但計(jì)算量太大?；诖?，這里在快速角點(diǎn)檢測(cè)算法中引入評(píng)價(jià)角點(diǎn)好壞的判定函數(shù)。圖6為USAN的6種典型情況。

圖6 USAN的6種典型情況

圖6 中,角點(diǎn)有“L 型”、“T”型、“Y”型，“L 型”角點(diǎn)為好的角點(diǎn)。 圖 6（d）為“L 型”角點(diǎn)，是 nmax的 1/4，這里定義為 ngood。圖 6（b）則是一個(gè)邊緣，圖 6（f）可能是角點(diǎn),也可能是噪聲,但在實(shí)際圖像中噪聲的概率更大一些。圖 6（c）和圖 6（e）是普通角點(diǎn)。采用判定角點(diǎn)“好壞”的函數(shù)

式中，Y（r0）分布在（0,1）區(qū)間內(nèi)。

對(duì)圖像進(jìn)行角點(diǎn)檢測(cè)后，根據(jù)Y（r0）的大小對(duì)所有角點(diǎn)進(jìn)行排序，選取最好的即可。但完全根據(jù)Y（r0）的大小排序后角點(diǎn)的分布不均勻，也不利于實(shí)現(xiàn)匹配算法。因此通過計(jì)算角點(diǎn)間的距離實(shí)現(xiàn)角點(diǎn)的均勻分布。距離計(jì)算公式如下：

式中，r0i、r0j分別是角點(diǎn)在圖像上的坐標(biāo)位置，ri是最小距離，Crobuse取值 0.9。

根據(jù)距離r對(duì)角點(diǎn)排序，這樣可使角點(diǎn)均勻地分布在圖像上，有利于圖像的匹配。引入好壞判斷函數(shù)后的算法具體步驟為：1）應(yīng)用SUSAN算法計(jì)算圖像上的所有角點(diǎn)；2）用式（6）計(jì)算角點(diǎn)好壞程度；3）由式（7）計(jì)算角點(diǎn)的距離；4）對(duì)距離排序，如果角點(diǎn)數(shù)量小于閾值（如取500）就取所有角點(diǎn)，如果大于閾值則取前500個(gè)角點(diǎn)。

3 試驗(yàn)結(jié)果

為驗(yàn)證本文算法的有效性,通過Microsoft Visual C++6.0進(jìn)行一系列實(shí)驗(yàn)，如圖 7所示。圖 7（a）為原始圖像，圖 7（b）為采用原SUSAN算法檢測(cè)的圖像，檢測(cè)出611個(gè)角點(diǎn)，圖 7（c）為按Y（r0）值排序取所有角點(diǎn)的圖像，圖 7（d）為按ri值排序取所有角點(diǎn)的圖像。結(jié)果顯示，使用該方法可有效保留“好”的角點(diǎn)，并使角點(diǎn)均勻分布在圖像上，有利于角點(diǎn)的匹配[8-10]。

圖7 算法驗(yàn)證實(shí)驗(yàn)圖像

4 結(jié)論

圖像匹配中角點(diǎn)的快速檢測(cè)算法研究對(duì)于計(jì)算機(jī)視覺和圖像處理有重要的理論和實(shí)踐意義，但目前主流的角點(diǎn)檢測(cè)算法均存在一定的缺陷。本文針對(duì)基于SUSAN算法的分層快速角點(diǎn)檢測(cè)算法存在的計(jì)算量大、無法滿足實(shí)時(shí)性等缺陷，提出評(píng)價(jià)角點(diǎn)“性能好壞”的判定函數(shù)和由粗到細(xì)的檢測(cè)算法。實(shí)驗(yàn)結(jié)果證實(shí)：改進(jìn)的算法可大大縮短運(yùn)算時(shí)間，提高實(shí)時(shí)性，同時(shí)使圖像匹配效果也有較大改善。

[1]張法全,陳良益,何俊華,等.基于VC和GPIB的數(shù)字示波器遠(yuǎn)程控制[J].微計(jì)算機(jī)信息，2007，23（28）：103-104.

[2]Wurtz R P,Lourens T.Corner detection in color images by multiscale combination of end-stopped cortical cells[C]//ICANN.London:Springer-Verlag，1997：901-906.

[3]李俊平，周振環(huán).提取圖像邊界角點(diǎn)的新方法[J].微電子學(xué)與計(jì)算機(jī)，2006，23（11）：188-199.

[4]Harris C,Stephens.A combined corner and edge detecter[C]//Matthews M M.Processdings of the 4th Vision Conference.Manchester the University of Sheffield printing Unit,1998,147-151.

[5]Trajkovic M,Hedley M.Fast corner detection[J].Image and Vision Computing,1998（18）：75-87.

[6]Tang B D.Jamel A B,Bogdan J M.An efficient feature based matching algorithm for stereo images[J].Proceedings of the Geometric Modeling and Imaging IEEE,2006，90（4）：72-75.

[7]趙鋒偉,李吉成,沈振康.景象匹配技術(shù)研究[J].系統(tǒng)工程與電子技術(shù),2002,24（12）：110-113.

[8]羅鐘鉉，劉成明.灰度圖像匹配的快速算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005 （5）：966-970.

[9]姜 凱,陳海霞,湯建華.一種快速圖像匹配算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2004，87（3）：87-89.

[10]王巖松，阮秋琦.一種基于互相關(guān)的圖像定位匹配算法研究及應(yīng)用[J].北方交通大學(xué)學(xué)報(bào)，2002，26（2）：20-24.