角點檢測簡介

角點檢測算法可歸納為3類:基于灰度圖像的角點檢測、基于二值圖像的角點檢測、基于輪廓曲線的角點檢測。基于灰度圖像的角點檢測又可分為基于梯度、基于模板和基于模板梯度組合3類方法，其中基于模板的方法主要考慮像素領(lǐng)域點的灰度變化，即圖像亮度的變化，將與鄰點亮度對比足夠大的點定義為角點。常見的基于模板的角點檢測算法有Kitchen-Rosenfeld角點檢測算法，Harris角點檢測算法、KLT角點檢測算法及SUSAN角點檢測算法。和其他角點檢測算法相比，SUSAN角點檢測算法具有算法簡單、位置準(zhǔn)確、抗噪聲能力強等特點。

#include "cv.h"

#include "highgui.h"

#define max_corners 100

int main( int argc, char** argv )

{

int cornerCount=max_corners;

CvPoint2D32f corners[max_corners];

double qualityLevel = 0.05;

double minDistance = 5;

IplImage *srcImage = 0, *grayImage = 0, *corners1 = 0, *corners2 = 0;

int i;

CvScalar color = CV_RGB(255,0,0);

cvNamedWindow( "image", 1 ); //創(chuàng)建顯示窗口

//加載一副圖片

srcImage = cvLoadImage("..//..//c//pic3.png", 1);

grayImage = cvCreateImage(cvGetSize(srcImage), IPL_DEPTH_8U, 1);

//將原圖灰度化

cvCvtColor(srcImage, grayImage, CV_BGR2GRAY);

//創(chuàng)建兩個與原圖大小相同的臨時圖像

corners1= cvCreateImage(cvGetSize(srcImage), IPL_DEPTH_32F, 1);

corners2= cvCreateImage(cvGetSize(srcImage),IPL_DEPTH_32F, 1);

//角點檢測

cvGoodFeaturesToTrack (grayImage, corners1, corners2, corners,

&cornerCount, qualityLevel, minDistance, 0);

printf("num corners found: %d\n", cornerCount);

//在原圖中將角點標(biāo)記出來

if(cornerCount>0)

{

for (i=0; i <cornerCount;++i){

cvCircle(srcImage, cvPoint((int)(corners[i].x), (int)(corners[i].y)), 6,

color, 2, CV_AA, 0);

}

}

cvShowImage( "image", srcImage );

cvReleaseImage(&srcImage);

cvReleaseImage(&grayImage);

cvReleaseImage(&corners1);

cvReleaseImage(&corners2);

cvWaitKey(0);

return 0;

}

基于梯度的方法是通過計算邊緣的曲率來判斷角點的存在性,角點計算數(shù)值的大小不僅與邊緣強度有關(guān),而且與邊緣方向的變化率有關(guān),該方法對噪聲比基于模板的角點檢測方法對噪聲更為敏感。L.Kchen和A.Rosedfeld給出了具體的角點檢測算子K,通過檢測K在圖像某一領(lǐng)域的極大值來達(dá)到提取角點的目的。該算子為K=tp?2 rq?2-2spqp?2 q?2,它表現(xiàn)為水平面截線上某點(x,y)的曲率與該點的最大梯度的乘積。但田原和梁德群等人指出K(x,y)在最大梯度方向上并不是極大值點,而是呈現(xiàn)單調(diào)變化的,所以在某一個鄰域內(nèi)曲率和該點的最大梯度乘積的極大值并不會出現(xiàn)在角點上。因此通過計算基于梯度的算法來確定的角點是不合理的。

考慮到角點作為一種重要的信號特征,屬于圖像的細(xì)節(jié),按照Witkin尺度空間理論,該角點應(yīng)該在較大的尺度空間存在?；谛〔ǘ喑叨确治龅慕屈c檢測,通過提出不同尺度上角點的對應(yīng)關(guān)系準(zhǔn)則由大尺度跟蹤到小尺度上精確的角點位置。設(shè)定提取角點的最大尺度2?k、梯度閾值Thg和曲率值Th?c,對圖像進(jìn)行小波變換,得到各個尺度上的小波分量W?x??2??j(x,y)和W?y??2??j(x,y);利用各個尺度上的小波分量在相應(yīng)的尺度上提取角點,記錄這些角點的位置;從最大的尺度k開始,按照前面所確定的原則尋找較小尺度上的對應(yīng)角點,直到最小的尺度為止;清除最小尺度上與上一尺度不對應(yīng)的點,得到最終角點結(jié)果。針對文獻(xiàn)的錯誤,就對某一尺度上的角點檢測算法,文獻(xiàn)指出角點不僅是水平面截線上的曲率極值點,也是該點在最大梯度方向上其最大梯度的模達(dá)到極大值，是滿足兩個條件的點集的交集。

基于模板的方法主要考慮像素鄰域點的灰度變化,即圖像亮度的變化,將與鄰點亮度對比足夠大的點定義為角點。

較早的直接基于灰度圖像角點檢測是文獻(xiàn)提出的Kitchen?Rosenfeld算法,通過模板窗口局部梯度幅值和梯度方向的變換率來計算角點度量值C=I?xyI?2?y I?yyI?2?x-2I?xyI?xI?yI?2?x I?2?y,根據(jù)C與給定的閾值大小關(guān)系來判定該點是否是角點。

Harris等人檢測方法考慮的是用一個高斯窗或矩形窗在圖像上移動,由模板窗口取得原圖像衍生出2×2的局部結(jié)構(gòu)矩陣，M=∑x,yw(x,y)I?2xI?xI?y I?xI?yI?2?y,w(x,y)為窗口函數(shù)。對該模板矩陣求取特征值λ?1和λ?2,建立度量函數(shù)R=detM-k(traceM)?2,detM=λ?1λ?2,traceM=λ?1 λ?2，根據(jù)R是否大于0即可判斷該點是否是角點。值得注意的是該方法具有旋轉(zhuǎn)不變性,但檢測的角點有較大的冗余,需要根據(jù)實際經(jīng)驗來確定R的閾值。

被大多數(shù)人所熟悉的KLT角點檢測算法[6，7]也是對基于一個計算窗口模板D×D下的圖像計算局部結(jié)構(gòu)矩陣，計算其特征值λ?1和λ?2，根據(jù)給定閾值λ按照式子min(λ?1,λ?2)>λ來判定其是否為角點。這里的關(guān)鍵是閾值λ和窗口D的大小的確定，D的大小一般為2~10,太大的窗口會引起角點移動,窗口太小則會丟失相距較近的角點。

USAN或SUSAN角點檢測算法得到越來越多的關(guān)注，最小亮度變化算法(MIC)[8]、同值分割吸收核(Univalue Segment Assimilating Nucleus，USAN)算法[9]都是基于像素鄰域半徑為k的圓形模板。該算法基于角點響應(yīng)函數(shù)(CRF),對每個像素基于其模板鄰域的圖像灰度計算CRF值,如果大于某一閾值且為局部極大值,則認(rèn)為該點為角點，一般k取1或2。

由算法的實現(xiàn)和相關(guān)結(jié)果可以看出,KLT算法比Harris算法檢測角點的質(zhì)量高,但KLT算法適用于角點數(shù)目不多且光源簡單的情況,Harris適用于角點數(shù)目較多且光源復(fù)雜的情況。除了對單幅圖像能進(jìn)行角點檢測以外,KLT算法和Harris算法對圖像序列的角點檢測效果更好。Kitchen?Rosenfeld算法和USAN算法一般來說不適合序列圖像的角點跟蹤,對于單幅圖像的角點檢測,USAN算法要比Kitchen?Rosenfeld算法好得多。但Harris算法的實現(xiàn)公式中有平滑部分,因此具有較強的魯棒且對噪聲也不太敏感。但在實際計算過程中,圓形模板需要離散化,這就帶來了較大的量化誤差,容易導(dǎo)致邊緣點和角點的判斷混亂。對于邊緣模糊的圖像,使用小模板會丟失角點,這就需要動態(tài)地判斷究竟用哪種模板最優(yōu)。文獻(xiàn)[10]針對此問題提出模糊度的概念,對每一個像素在計算其CRF值之前首先測定其模糊度。若達(dá)到模糊的標(biāo)準(zhǔn),就使用大的模板來計算;若清晰,則選用小的模板來計算。這使得判定的準(zhǔn)確性得到很大的提高,減少了虛報概率。

費旭東等人[11]采用基于知識的查表技術(shù)來進(jìn)行角點的快速提取,其特點是便于用硬件來實現(xiàn),但必須先得到圖像的邊界鏈碼表示,原則上屬于模板匹配。

一般來說,各種角點檢測算子要與圖像進(jìn)行卷積運算,所以也應(yīng)該屬于模板類的方法。

文獻(xiàn)[12]采用高斯-拉普拉斯二階微分算子來檢測角點。高斯二階微分函數(shù)與離散信號的卷積相當(dāng)于高斯函數(shù)與信號的卷積再求二階差分,因此對噪聲的敏感度較大。文獻(xiàn)[13]基于神經(jīng)細(xì)胞(Gauglion Cell，GC)感受野數(shù)學(xué)模型提出雙高斯差(Difference Of Gaussian，DOG)模型來檢測角點,指出高斯二階微分函數(shù)是DOG函數(shù)在其兩個高斯函數(shù)相互逼近時的一個極端形式特例。DOG函數(shù)與信號的卷積相當(dāng)于兩個高斯函數(shù)與信號的卷積結(jié)果之差,因此抗噪聲的能力較強。

除了直接對灰度圖像的像素操作以外,羅斌等人[14]采用了變換的方法,用電磁場理論中矢勢的鞍點檢測來代替角點的檢測,是一種綜合了模板角點檢測和灰度曲率角點檢測的方法。通過高斯模板和圖像的卷積獲得Canny邊緣映射圖,再計算梯度和邊緣矢量就得到了矢勢。對于矢勢計算高斯曲率和平均曲率來判定是否是鞍點,對應(yīng)的應(yīng)該是圖像的角點。因為涉及到了曲率的計算,也有人將該方法歸到邊緣曲線的角點檢測。

劉文予等人[15]提出一種基于形態(tài)骨架的角點檢測方法,該方法將原始圖像看 作一個多邊形,則多邊形的角點一定在骨架的延長線上,且角點所對應(yīng)的骨架點的最大圓盤半徑應(yīng)該趨于0,檢測骨架中的最大圓盤為0的點,即為角點。因為在二值圖像階段處理,計算量并不是很大,所以保證了計算的實時性。應(yīng)該指出的是,雖然將二值圖像作為一個單獨的檢測目標(biāo)列出來,但是基于灰度圖像的各種處理方法對此仍然有效。二值圖像處于灰度和邊緣輪廓圖像的中間步驟,所以專門針對此類圖像的角點檢測方法并不多見。

早在1975年，Rosenfeld A等人[16]和Freeman H等人[17]就提出通過計算角點強度k來提取角點,不過這種方法雖然簡單，但容易受噪聲干擾，效果不是很理想。為了將干擾去除,減少邊緣毛刺干擾，Asada等人[18]提出首先對邊緣采用高斯平滑,即減少了將局部彎曲度突然增大而誤判為角點的概率。但角點強度k是預(yù)先確定還是根據(jù)曲線的彎曲度自適應(yīng)調(diào)節(jié),對于檢測的結(jié)果影響很大。文獻(xiàn)[19]指出自適應(yīng)的彎曲度測定實際上是要自適應(yīng)地確定曲線段支持區(qū)域的大小,支持區(qū)域的選擇應(yīng)該能夠根據(jù)曲線的彎曲程度自適應(yīng)地調(diào)整,在此支持區(qū)域上求取的曲線彎曲度才能較為準(zhǔn)確地反映平面對象邊界曲線的平滑和彎曲程度。文獻(xiàn)[20]提出采用自適應(yīng)彎曲度求取算法計算曲線上任意點所在位置的曲線彎曲度,將曲線邊界點集中滿足限定條件的點組成候選角點集合,增加平滑參數(shù)開始新的循環(huán),直到達(dá)到預(yù)先設(shè)定的最大平滑因子為止,最后將所有候選角點集合中出現(xiàn)次數(shù)滿足一定門限的邊界點定義為角點。

文獻(xiàn)[21]認(rèn)為數(shù)字化曲線是離散的,是基于像素基礎(chǔ)的,這樣隱含的一個假設(shè)就是數(shù)字化曲線上相鄰兩個像素之間的距離是一個常數(shù),但在實際中該假設(shè)并不成立,因此質(zhì)疑早先對角點的估計方法是否可擬合穩(wěn)定?；谶@個發(fā)現(xiàn),文章提出了基于曲線累加弦長的角點檢測方法,主要是在確定支持域時充分考慮相鄰像素點之間的實際距離,即相鄰的距離應(yīng)該是1和2,并由此出發(fā)提出隱式精化數(shù)字化曲線的策略,推導(dǎo)出了一種新的角點強度計算公式。利用該公式可以對如尖角和圓角進(jìn)行區(qū)別,檢測結(jié)果具有旋轉(zhuǎn)不變性。該方法被認(rèn)為是在數(shù)字化圖像處理中引入了納米技術(shù)。

對于曲線曲率的計算,一種是直接對離散的曲線進(jìn)行計算,另一種是用某類函數(shù)對原始曲線分段擬合,然后根據(jù)擬合后的曲線分段方程,計算曲線曲率極值得到角點的位置。

文獻(xiàn)[22]使用了三次多項式來擬合離散的數(shù)據(jù)點,文獻(xiàn)[23]提出了B樣條來擬合曲線,由于要事先實現(xiàn)計算曲線的擬合方程,其運算量比較大。文獻(xiàn)[21]提出算法根據(jù)曲線上任意點的彎曲度,結(jié)合模糊識別的方法來檢測對象邊界曲線的角點。而文獻(xiàn)[24]認(rèn)為既然角點是曲線上曲率較大的點,角點檢測的關(guān)鍵是估計當(dāng)前輪廓點前后曲線的方向,該方向的度量采用定義的一個方向差角d?θ=180°-min{|θ?1-θ?2|,360°-|θ?1-θ?2|},差角越大,表示曲率越大。其中基于距離誤差的直線擬合可以自適應(yīng)地調(diào)整擬合窗口,很好地減少了邊緣噪聲的干擾。在文獻(xiàn)[25]中除了像文獻(xiàn)[24]對角點兩側(cè)的點構(gòu)成向量的夾角繼續(xù)關(guān)注以外,還對曲線角點的特征進(jìn)行了多方位的考慮,同時引用模糊集合的概念,采用隸屬度對點領(lǐng)域的四個特征進(jìn)行描述。這四個特征分別為角點前后點組成的向量與角點的距離特征、角點前后向量夾角特征、角點的前向直線特征、角點的后向直線特征。采用隸屬度描述后,對真實角點的相鄰點有很強的抑制作用,檢出的角點符合人類視覺感知規(guī)律。但該算法僅考慮了角點的局部特性,沒有考慮全局特征,因此存在一定的漏檢現(xiàn)象。在關(guān)注角點細(xì)節(jié)特征的同時,如何能有效地考慮全局整體特征,應(yīng)該是該算法需要完善的地方。

濾波器的尺度選擇并不是一件容易的事情,要求在濾掉噪聲的同時保持邊界曲線的基本形狀特征。同時曲線上各角點均有著不同尺度的支撐域,無法事先定義出一個最優(yōu)的分辨率來進(jìn)行角點檢測。在使用多尺度分析后求取不同尺度的空間時,輪廓曲線已經(jīng)被不同的小波函數(shù)所平滑,所以能最大限度地減少邊緣毛刺噪聲。

Witkin[20]和Koenderink[26]提出基于尺度空間的圖像分析理論后,多尺度曲線分析成為解決該問題的主要方法,在曲線尺度空間中,隨著曲線尺度由小變大,一直保持較高彎曲度的點必定是所要求取的角點。基于此,文獻(xiàn)[27]提出基于尺度空間的角點檢測思想,文獻(xiàn)[28]對采用二階導(dǎo)數(shù)零交叉邊緣檢測算子和圍線跟蹤算法得到的邊緣曲線,使用一組自相似二進(jìn)Gabor小波變換的濾波器將整個頻域從高頻到低頻分為多個子帶,對兩個不同尺度下的濾波器輸出求差并取模,根據(jù)結(jié)果即可判定該點是否是角點。

在上面的多尺度檢測中,僅考慮了角點的位置信息,文獻(xiàn)[29]提出在利用角點的位置信息時不能忽略有關(guān)角點的幅度信息。在選定小波為高斯函數(shù)的一階導(dǎo)數(shù)后,對圖像輪廓的Freeman鏈碼C={P?i=(x?i,y?i),i=1,…,n}投影成函數(shù)φ(i)=arctg[(y?i q-y?i-q)/(x?i q-x?i-q)],對φ(i)進(jìn)行小波變換,在不同的尺度上,角點的小波變換幅值始終是最大的,位置始終是不變的。如果有噪聲,那么噪聲的幅值只存在于有限的尺度空間上,結(jié)合幅值判據(jù)和位置判據(jù)就能夠很好地確定角點,剔除偽角點,結(jié)果的準(zhǔn)確性很高。同時結(jié)合不同的角點模型,還可以對角點是單角、雙角、三角的屬性作出判別。

角點作為圖像上的特征點,包含有重要的信息，在圖像融合和目標(biāo)跟蹤及三維重建中有重要的應(yīng)用價值。但是基于實際應(yīng)用需求,從角點檢測的快速性、準(zhǔn)確性、魯棒性等要求出發(fā),可以看出上面對各種角點檢測算法的分析各有利弊。直接基于圖像的角點檢測基本上是全局搜索;基于邊緣輪廓的角點檢測數(shù)據(jù)量較少,可以采用多分辨分析并行處理,從灰度圖像得到邊緣輪廓曲線要經(jīng)過兩次以上的全局搜索,速度并不是很快,但對角點的誤檢和漏檢要比直接基于圖像的方法好得多。如果在得到輪廓曲線的過程中應(yīng)用一些其他的變換方法,就計算的速度而言,下降不少，所以一般快速的、較準(zhǔn)確的角點檢測使用直接基于圖像模板的方法完全可以滿足需要,但如果對角點的完備性要求較高,那么使用基于輪廓線的多尺度分析方法應(yīng)該給予考慮。

Deriche R,Giraudon G. A Computational Approach for Corner and Vertex Detection[J]. Computer Vision, 1993,10(2):101?124. L Kitchen, A Rosenfeld. Gray Level Corner Detection[J]. Pattern Recognition Letters, 1982,3(1):95?102.

田原,梁德群,吳更石.直接基于灰度圖像的多尺度角點檢測方法[J].信號處理,1998,14(7?11):6-9.

L Kitchen, A Rosenfeld. Analysis of Gray Level Corner Detection[J]. Pattern Recognition Letters, 1999,20(2):149?162.

Chris Harris, Mike Stephens. A Combined Corner and Edge Detector[C]. Manchester: Proceedings of the 4th Alvey Vision Conference, 1988.147?151.

C Tomasi, T Kanade. Detection and Tracking of Point Features[R]. Carnegie Mellon University, 1991.

J Shi, C Tomasi. Good Features to Track[C]. CVPR'94, 1994.593-600. [8]Miroslav T, Mark H. Fast Corner Detection[J]. Image and Vision Computing, 1998,16(1):75-87.

[9]Smith S M, Brady J M.SUSAN: A New Approach to Low Level Image Processing[J]. Int. Journal of Compuer Vision, 1997,23(1):45-78. [10]楊莉,初秀琴,李玉山.最小亮度變化角點自適應(yīng)檢測算法研究[J].西安電子科技大學(xué)學(xué)報,2003,30(4):530-533.

[11]費旭東,荊仁杰.基于知識的快速角點提取[J].計算機(jī)學(xué)報,1994,17(1):30-36.

[12]G Giraudon, R Derich. On Corner and Vertex Detection[J]. Computer Vision and Pattern Recognition, 1991,3(6):650-655.

[13]陳燕新,戚飛虎.一種新的提取輪廓特征點的方法[J].紅外與毫米波學(xué)報,1998,17(3):171?176.

[14]羅斌,E R Hancock.圖像角點檢測的矢量場方法[J].中國圖像圖形學(xué)報,1998,3(10):832-835.

[15]劉文予,朱光喜.二值圖像角點檢測的形態(tài)骨架法[J].信號處理,2000,16(3):276-280.

[16]Rosenfeld A, Weszka J S. An Improved Method of Angel Detection on Digital Curves[J]. IEEE Trans.Computers,1975,C?24(9):940-941.

[17]Freeman H, Davis L S. A Corner Finding Algorithm for Chain Coded Curves[J]. IEEE Trans. Computers, 1977,26(3):297-303.

[18]Asada H, Brady M. The Curvature Primal Sketch[J]. IEEE Trans. PAMI,1986,8(1):2?14.

[19]肖茜,魯宏偉.基于高斯平滑的自適應(yīng)角點檢測[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2003,15(11):1358?1361.

[20]Witkin A P. Scale Space Filtering[C]. Karlsruhe: Proceedings of the 8th International Joint Conference on Artificial Intelligence, 1983.1019?1021.

[21]鐘寶江,廖文和.基于精化曲線累加弦長的角點檢測技術(shù)[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2004,16(7):939-943.

[22]Langridge D J. CurveEncodingand the Detection of Discontinuities[J]. CVGIP, 1982,20(1):58-71.

[23]Mediono G, Yasumoto Y. Corner Detection and Curve Representation Using Cubic B?splines[J]. Computer Vision, Graphics and Image Processing, 1987,39(3):267-278.

[24]喬宇,黃席樾,柴毅.基于自適應(yīng)直線擬合地角點檢測[J].重慶大學(xué)學(xué)報,2003,26(2):29-31.

[25]邱衛(wèi)國,昂海松.基于隸屬度特征的曲線角點檢測方法[J].重慶大學(xué)學(xué)報,2004,27(11):43-46.

[26]Koenderink J J. The Structure of Image[J]. Biological Cybernetics, 1984,50(5):363-370.

[27]Anothai Rattarangsi, Chin Roland T. Scale?based Detection of Corners of Planar Curves[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(4):430-449.

[28]王展,黃埔堪,萬建偉.基于多尺度小波變換的二維圖像角點檢測技術(shù)[J].國防科技大學(xué)學(xué)報,1999,21(2):46-49.

[29]戚飛虎,劉健峰.一種有效的不變性角點檢測方法[J].上海交通大學(xué)學(xué)報,1995,29(6):112?116.

作者簡介:

趙文彬(1974-),男,助教,博士,主要研究方向為醫(yī)學(xué)圖形圖像處理、醫(yī)學(xué)三維重建與識別、虛擬手術(shù).

張艷寧(1967-)，女，中國電子學(xué)會信號處理分會委員，中國體視學(xué)學(xué)會理事及圖像分析分會秘書長，IEEE會員，主任，教授，博導(dǎo)，博士，主要研究方向為信號與信息處理、圖像處理與模式識別等。