角點檢測小結

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

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

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

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

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

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

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

在上面的多尺度檢測中,僅考慮了角點的位置信息,文獻[29]提出在利用角點的位置信息時不能忽略有關角點的幅度信息。在選定小波為高斯函數(shù)的一階導數(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ù)和位置判據(jù)就能夠很好地確定角點,剔除偽角點,結果的準確性很高。同時結合不同的角點模型,還可以對角點是單角、雙角、三角的屬性作出判別。

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

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

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

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

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

Harris等人檢測方法考慮的是用一個高斯窗或矩形窗在圖像上移動,由模板窗口取得原圖像衍生出2×2的局部結構矩陣，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即可判斷該點是否是角點。值得注意的是該方法具有旋轉不變性,但檢測的角點有較大的冗余,需要根據(jù)實際經(jīng)驗來確定R的閾值。

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

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

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

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

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

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

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

#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);

//在原圖中將角點標記出來

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;

}

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

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]楊莉,初秀琴,李玉山.最小亮度變化角點自適應檢測算法研究[J].西安電子科技大學學報,2003,30(4):530-533.

[11]費旭東,荊仁杰.基于知識的快速角點提取[J].計算機學報,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].紅外與毫米波學報,1998,17(3):171?176.

[14]羅斌,E R Hancock.圖像角點檢測的矢量場方法[J].中國圖像圖形學報,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]肖茜,魯宏偉.基于高斯平滑的自適應角點檢測[J].計算機輔助設計與圖形學學報,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]鐘寶江,廖文和.基于精化曲線累加弦長的角點檢測技術[J].計算機輔助設計與圖形學學報,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]喬宇,黃席樾,柴毅.基于自適應直線擬合地角點檢測[J].重慶大學學報,2003,26(2):29-31.

[25]邱衛(wèi)國,昂海松.基于隸屬度特征的曲線角點檢測方法[J].重慶大學學報,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]王展,黃埔堪,萬建偉.基于多尺度小波變換的二維圖像角點檢測技術[J].國防科技大學學報,1999,21(2):46-49.

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

作者簡介:

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

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