基于SUSAN分層快速角點檢測的改進算法

趙 杰，馬海超

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

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

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

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

1 基于SUSAN的分層快速角點檢測算法

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

1.1 提升小波變換理論

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

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

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

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

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

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

1.2 由粗到細的分層快速角點檢測算法

直接運用SUSAN算法檢測角點，速度較慢。而若能快速找到角點的粗略位置，再進行準確判斷，則可大大節(jié)約時間。

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

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

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

圖2 一行中兩種典型圖像

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

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

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

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

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

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

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

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

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

圖6 USAN的6種典型情況

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

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

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

式中，r0i、r0j分別是角點在圖像上的坐標位置，ri是最小距離，Crobuse取值 0.9。

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

3 試驗結(jié)果

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

圖7 算法驗證實驗圖像

4 結(jié)論

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

[1]張法全,陳良益,何俊華,等.基于VC和GPIB的數(shù)字示波器遠程控制[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).提取圖像邊界角點的新方法[J].微電子學(xué)與計算機，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].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005 （5）：966-970.

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

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