角點檢測簡介
角點檢測算法可歸納為3類：基於灰度圖像的角點檢測、基於二值圖像的角點檢測、基於輪廓曲線的角點檢測。基於灰度圖像的角點檢測又可分為基於梯度、基於模板和基於模板梯度組合3類方法，其中基於模板的方法主要考慮像素領域點的灰度變化，即圖像亮度的變化，將與鄰點亮度對比足夠大的點定義為角點。常見的基於模板的角點檢測算法有Kitchen-Rosenfeld角點檢測算法，Harris角點檢測算法、KLT角點檢測算法及SUSAN角點檢測算法。和其他角點檢測算法相比，SUSAN角點檢測算法具有算法簡單、位置準確、抗噪聲能力強等特點。
算法
SUSAN是Smith和Brady提出的一種圖像處理方法，該算法是基於像素領域包含若干元素的近似圓形模板，對每個像素基於該模板領域的圖像灰度計算角點回響函式（CRF）的數值，如果大於某閾值且為局部極大值，則認為該點為角點。角點的精度與圓形模板大小無關，圓形模板越大，檢測的角點數越多，則計算量也越大，本文圓形模板包含37個元素，該近似圓形模板結構如圖1所示。
SUSAN圓形模板與物體位置關係圖如圖2所示為SUSAN圓形模板與物體的5種幾何位置關係，對於圖像中非紋理區域的任一點，在以它為中心的模板窗中存在一塊亮度與其相同的區域，這塊區域即為SUSAN的USAN（Univalve Segment Assimilating Nucleus）區域。USAN區域包含了圖像結構的重要信息，由圖可知，當模板中心像素點位於區域內部時，USAN的面積最大，當該像素點位於區域邊界時，則面積為最大的一半，當該像素點為角點時，USAN區域面積約為最大的1/4。SUSAN根據不同位置時USAN區域的面積來考察當前像素點為區域內部點、邊緣點或角點。
USAN區域面積通過圓模板內各像素與中心點像素比較得到的相似點的個數總和來表示，該相似比較函
數為：
函式其中（x0,y0），(x,y)分別為模板中心像素點和待比較像素點的坐標，t為相似度閾值，本文該值取整幅圖像灰度最大值和最小值差值的1/10。
則與中心點像素相似點的個數為：
本文取圖像每11×11領域範圍內來搜尋CRF為極大值的像素點，當該像素點CRF數值大於控制閾值thresh （本文取13），則將該點標記為角點。角點（十字形標識）檢測效果如圖3所示。
示例
#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 ); //創建顯示視窗
//載入一副圖片
srcImage = cvLoadImage("..//..//c//pic3.png", 1);
grayImage = cvCreateImage(cvGetSize(srcImage), IPL_DEPTH_8U, 1);
//將原圖灰度化
cvCvtColor(srcImage, grayImage, CV_BGR2GRAY);
//創建兩個與原圖大小相同的臨時圖像
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;
}
技術綜述
角點是圖像很重要的特徵,對圖像圖形的理解和分析有很重要的作用。對灰度圖像、二值圖像、邊緣輪廓曲線的角點檢測算法進行綜述,分析了相關的算法,並對各種檢測算法給出了評價。
角點檢測程式角點檢測特徵點； 綜述中圖法分類號：TP391
文獻標識碼：A
文章編號：1001-3695(2006)10-0017-03
Survey on Corner Detection
ZHAO Wen?bin, ZHANG Yan?ning
(Key Lab. of Shanxi Province Computer Graphics, College of Computer, Northwestern Polytechnical University, Xi’an Shanxi 710072, China) Abstract:Corner is important feature in the analysis and understanding of images or computer graphics. This paper attempt to summarize corner detection method in gray?level image, binary image and curve of edge, also to compare with many property of corner detection algorithm.
Key words:Corner Detection; Feature Point; Survey
角點沒有明確的數學定義,但人們普遍認為角點是二維圖像亮度變化劇烈的點或圖像邊緣曲線上曲率極大值的點。這些點在保留圖像圖形重要特徵的同時,可以有效地減少信息的數據量,使其信息的含量很高,有效地提高了計算的速度,有利於圖像的可靠匹配,使得實時處理成為可能。其在三維場景重建、運動估計、目標跟蹤、目標識別、圖像配準與匹配等計算機視覺領域起著非常重要的作用。
角點檢測算法可以說各種各樣。一般使用者僅僅要求得到一個準確的角點檢測結果或該檢測算法易於編程實現,滿足實際後續匹配等套用需要。本文對角點檢測按檢測目標進行分類,對各種類下的檢測算法逐一進行歸納分析。
灰度圖像
基於梯度的方法
基於梯度的方法是通過計算邊緣的曲率來判斷角點的存在性,角點計算數值的大小不僅與邊緣強度有關,而且與邊緣方向的變化率有關,該方法對噪聲比基於模板的角點檢測方法對噪聲更為敏感。L.Kchen和A.Rosedfeld給出了具體的角點檢測運算元K,通過檢測K在圖像某一領域的極大值來達到提取角點的目的。該運算元為K=tp?2 rq?2-2spqp?2 q?2,它表現為水平面截線上某點(x,y)的曲率與該點的最大梯度的乘積。但田原和梁德群等人指出K(x,y)在最大梯度方向上並不是極大值點,而是呈現單調變化的,所以在某一個鄰域內曲率和該點的最大梯度乘積的極大值並不會出現在角點上。因此通過計算基於梯度的算法來確定的角點是不合理的。
考慮到角點作為一種重要的信號特徵,屬於圖像的細節,按照Witkin尺度空間理論,該角點應該在較大的尺度空間存在。基於小波多尺度分析的角點檢測,通過提出不同尺度上角點的對應關係準則由大尺度跟蹤到小尺度上精確的角點位置。設定提取角點的最大尺度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,根據C與給定的閾值大小關係來判定該點是否是角點。
Harris等人檢測方法考慮的是用一個高斯窗或矩形窗在圖像上移動,由模板視窗取得原圖像衍生出2×2的局部結構矩陣，M=∑x,yw(x,y)I?2xI?xI?y I?xI?yI?2?y,w(x,y)為視窗函式。對該模板矩陣求取特徵值λ?1和λ?2,建立度量函式R=detM-k(traceM)?2,detM=λ?1λ?2,traceM=λ?1 λ?2，根據R是否大於0即可判斷該點是否是角點。值得注意的是該方法具有鏇轉不變性,但檢測的角點有較大的冗餘,需要根據實際經驗來確定R的閾值。
被大多數人所熟悉的KLT角點檢測算法[6，7]也是對基於一個計算視窗模板D×D下的圖像計算局部結構矩陣，計算其特徵值λ?1和λ?2，根據給定閾值λ按照式子min（λ?1,λ?2）>λ來判定其是否為角點。這裡的關鍵是閾值λ和視窗D的大小的確定，D的大小一般為2~10,太大的視窗會引起角點移動,視窗太小則會丟失相距較近的角點。
USAN或SUSAN角點檢測算法得到越來越多的關注，最小亮度變化算法(MIC)[8]、同值分割吸收核(Univalue Segment Assimilating Nucleus，USAN)算法[9]都是基於像素鄰域半徑為k的圓形模板。該算法基於角點回響函式(CRF),對每個像素基於其模板鄰域的圖像灰度計算CRF值,如果大於某一閾值且為局部極大值,則認為該點為角點，一般k取1或2。
由算法的實現和相關結果可以看出,KLT算法比Harris算法檢測角點的質量高,但KLT算法適用於角點數目不多且光源簡單的情況,Harris適用於角點數目較多且光源複雜的情況。除了對單幅圖像能進行角點檢測以外,KLT算法和Harris算法對圖像序列的角點檢測效果更好。Kitchen?Rosenfeld算法和USAN算法一般來說不適合序列圖像的角點跟蹤,對於單幅圖像的角點檢測,USAN算法要比Kitchen?Rosenfeld算法好得多。但Harris算法的實現公式中有平滑部分,因此具有較強的魯棒且對噪聲也不太敏感。但在實際計算過程中,圓形模板需要離散化,這就帶來了較大的量化誤差,容易導致邊緣點和角點的判斷混亂。對於邊緣模糊的圖像,使用小模板會丟失角點,這就需要動態地判斷究竟用哪種模板最優。文獻[10]針對此問題提出模糊度的概念,對每一個像素在計算其CRF值之前首先測定其模糊度。若達到模糊的標準,就使用大的模板來計算；若清晰,則選用小的模板來計算。這使得判定的準確性得到很大的提高,減少了虛報機率。
費旭東等人[11]採用基於知識的查表技術來進行角點的快速提取,其特點是便於用硬體來實現,但必須先得到圖像的邊界鏈碼錶示,原則上屬於模板匹配。
一般來說,各種角點檢測運算元要與圖像進行卷積運算,所以也應該屬於模板類的方法。
文獻[12]採用高斯—拉普拉斯二階微分運算元來檢測角點。高斯二階微分函式與離散信號的卷積相當於高斯函式與信號的卷積再求二階差分,因此對噪聲的敏感度較大。文獻[13]基於神經細胞(Gauglion Cell，GC)感受野數學模型提出雙高斯差(Difference Of Gaussian，DOG)模型來檢測角點,指出高斯二階微分函式是DOG函式在其兩個高斯函式相互逼近時的一個極端形式特例。DOG函式與信號的卷積相當於兩個高斯函式與信號的卷積結果之差,因此抗噪聲的能力較強。
基於模板梯度組合方法
除了直接對灰度圖像的像素操作以外,羅斌等人[14]採用了變換的方法,用電磁場理論中矢勢的鞍點檢測來代替角點的檢測,是一種綜合了模板角點檢測和灰度曲率角點檢測的方法。通過高斯模板和圖像的卷積獲得Canny邊緣映射圖,再計算梯度和邊緣矢量就得到了矢勢。對於矢勢計算高斯曲率和平均曲率來判定是否是鞍點,對應的應該是圖像的角點。因為涉及到了曲率的計算,也有人將該方法歸到邊緣曲線的角點檢測。
二值圖像
一組角點檢測模板和原理說明劉文予等人[15]提出一種基於形態骨架的角點檢測方法,該方法將原始圖像看作一個多邊形,則多邊形的角點一定在骨架的延長線上,且角點所對應的骨架點的最大圓盤半徑應該趨於0,檢測骨架中的最大圓盤為0的點,即為角點。因為在二值圖像階段處理,計算量並不是很大,所以保證了計算的實時性。應該指出的是,雖然將二值圖像作為一個單獨的檢測目標列出來,但是基於灰度圖像的各種處理方法對此仍然有效。二值圖像處於灰度和邊緣輪廓圖像的中間步驟,所以專門針對此類圖像的角點檢測方法並不多見。
輪廓曲線
計算角點強度k
早在1975年，Rosenfeld A等人[16]和Freeman H等人[17]就提出通過計算角點強度k來提取角點,不過這種方法雖然簡單，但容易受噪聲干擾，效果不是很理想。為了將干擾去除,減少邊緣毛刺干擾，Asada等人[18]提出首先對邊緣採用高斯平滑,即減少了將局部彎曲度突然增大而誤判為角點的機率。但角點強度k是預先確定還是根據曲線的彎曲度自適應調節,對於檢測的結果影響很大。文獻[19]指出自適應的彎曲度測定實際上是要自適應地確定曲線段支持區域的大小,支持區域的選擇應該能夠根據曲線的彎曲程度自適應地調整,在此支持區域上求取的曲線彎曲度才能較為準確地反映平面對象邊界曲線的平滑和彎曲程度。文獻[20]提出採用自適應彎曲度求取算法計算曲線上任意點所在位置的曲線彎曲度,將曲線邊界點集中滿足限定條件的點組成候選角點集合,增加平滑參數開始新的循環,直到達到預先設定的最大平滑因子為止,最後將所有候選角點集合中出現次數滿足一定門限的邊界點定義為角點。
文獻[21]認為數位化曲線是離散的,是基於像素基礎的,這樣隱含的一個假設就是數位化曲線上相鄰兩個像素之間的距離是一個常數,但在實際中該假設並不成立,因此質疑早先對角點的估計方法是否可擬合穩定。基於這個發現,文章提出了基於曲線累加弦長的角點檢測方法,主要是在確定支持域時充分考慮相鄰像素點之間的實際距離,即相鄰的距離應該是1和2,並由此出發提出隱式精化數位化曲線的策略,推導出了一種新的角點強度計算公式。利用該公式可以對如尖角和圓角進行區別,檢測結果具有鏇轉不變性。該方法被認為是在數位化圖像處理中引入了納米技術。
計算曲線曲率的極值
對於曲線曲率的計算,一種是直接對離散的曲線進行計算,另一種是用某類函式對原始曲線分段擬合,然後根據擬合後的曲線分段方程,計算曲線曲率極值得到角點的位置。
文獻[22]使用了三次多項式來擬合離散的數據點,文獻[23]提出了B樣條來擬合曲線,由於要事先實現計算曲線的擬合方程,其運算量比較大。文獻[21]提出算法根據曲線上任意點的彎曲度,結合模糊識別的方法來檢測對象邊界曲線的角點。而文獻[24]認為既然角點是曲線上曲率較大的點,角點檢測的關鍵是估計當前輪廓點前後曲線的方向,該方向的度量採用定義的一個方向差角d?θ=180°-min{|θ?1-θ?2|,360°-|θ?1-θ?2|},差角越大,表示曲率越大。其中基於距離誤差的直線擬合可以自適應地調整擬合視窗,很好地減少了邊緣噪聲的干擾。在文獻[25]中除了像文獻[24]對角點兩側的點構成向量的夾角繼續關注以外,還對曲線角點的特徵進行了多方位的考慮,同時引用模糊集合的概念,採用隸屬度對點領域的四個特徵進行描述。這四個特徵分別為角點前後點組成的向量與角點的距離特徵、角點前後向量夾角特徵、角點的前向直線特徵、角點的後向直線特徵。採用隸屬度描述後,對真實角點的相鄰點有很強的抑制作用,檢出的角點符合人類視覺感知規律。但該算法僅考慮了角點的局部特性,沒有考慮全局特徵,因此存在一定的漏檢現象。在關注角點細節特徵的同時,如何能有效地考慮全局整體特徵,應該是該算法需要完善的地方。
多尺度角點檢測
濾波器的尺度選擇並不是一件容易的事情,要求在濾掉噪聲的同時保持邊界曲線的基本形狀特徵。同時曲線上各角點均有著不同尺度的支撐域,無法事先定義出一個最優的解析度來進行角點檢測。在使用多尺度分析後求取不同尺度的空間時,輪廓曲線已經被不同的小波函式所平滑,所以能最大限度地減少邊緣毛刺噪聲。
Witkin[20]和Koenderink[26]提出基於尺度空間的圖像分析理論後,多尺度曲線分析成為解決該問題的主要方法,在曲線尺度空間中,隨著曲線尺度由小變大,一直保持較高彎曲度的點必定是所要求取的角點。基於此,文獻[27]提出基於尺度空間的角點檢測思想,文獻[28]對採用二階導數零交叉邊緣檢測運算元和圍線跟蹤算法得到的邊緣曲線,使用一組自相似二進Gabor小波變換的濾波器將整個頻域從高頻到低頻分為多個子帶,對兩個不同尺度下的濾波器輸出求差並取模,根據結果即可判定該點是否是角點。
在上面的多尺度檢測中,僅考慮了角點的位置信息,文獻[29]提出在利用角點的位置信息時不能忽略有關角點的幅度信息。在選定小波為高斯函式的一階導數後,對圖像輪廓的Freeman鏈碼C={P?i=(x?i,y?i),i=1,…,n}投影成函式φ(i)=arctg[(y?i q-y?i-q)/(x?i q-x?i-q)],對φ(i)進行小波變換,在不同的尺度上,角點的小波變換幅值始終是最大的,位置始終是不變的。如果有噪聲,那么噪聲的幅值只存在於有限的尺度空間上,結合幅值判據和位置判據就能夠很好地確定角點,剔除偽角點,結果的準確性很高。同時結合不同的角點模型,還可以對角點是單角、雙角、三角的屬性作出判別。
小結
角點作為圖像上的特徵點,包含有重要的信息，在圖像融合和目標跟蹤及三維重建中有重要的套用價值。但是基於實際套用需求,從角點檢測的快速性、準確性、魯棒性等要求出發,可以看出上面對各種角點檢測算法的分析各有利弊。直接基於圖像的角點檢測基本上是全局搜尋；基於邊緣輪廓的角點檢測數據量較少,可以採用多分辨分析並行處理,從灰度圖像得到邊緣輪廓曲線要經過兩次以上的全局搜尋,速度並不是很快,但對角點的誤檢和漏檢要比直接基於圖像的方法好得多。如果在得到輪廓曲線的過程中套用一些其他的變換方法,就計算的速度而言,下降不少，所以一般快速的、較準確的角點檢測使用直接基於圖像模板的方法完全可以滿足需要,但如果對角點的完備性要求較高,那么使用基於輪廓線的多尺度分析方法應該給予考慮。
參考文獻
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.
一種改進的SUSAN角點檢測算法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]劉文予,朱光喜.二值圖像角點檢測的形態骨架法[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]邱衛國,昂海松.基於隸屬度特徵的曲線角點檢測方法[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-),男,助教,博士,主要研究方向為醫學圖形圖像處理、醫學三維重建與識別、虛擬手術.
張艷寧(1967-），女，中國電子學會信號處理分會委員，中國體視學學會理事及圖像分析分會秘書長，IEEE會員，主任，教授，博導，博士，主要研究方向為信號與信息處理、圖像處理與模式識別等。
