角點檢測（角點檢測）

角點檢測簡介

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

算法

SUSAN是Smith和Brady提出的一種圖像處理方法，該算法是基于像素領域包含若干元素的近似圓形模板，對每個像素基于該模板領域的圖像灰度計算角點響應函數(shù)（CRF）的數(shù)值，如果大于某閾值且為局部極大值，則認為該點為角點。角點的精度與圓形模板大小無關，圓形模板越大，檢測的角點數(shù)越多，則計算量也越大，本文圓形模板包含37個元素，該近似圓形模板結(jié)構(gòu)如圖1所示。

如圖2所示為SUSAN圓形模板與物體的5種幾何位置關系，對于圖像中非紋理區(qū)域的任一點，在以它為中心的模板窗中存在一塊亮度與其相同的區(qū)域，這塊區(qū)域即為SUSAN的USAN（Univalve Segment Assimilating Nucleus）區(qū)域。USAN區(qū)域包含了圖像結(jié)構(gòu)的重要信息，由圖可知，當模板中心像素點位于區(qū)域內(nèi)部時，USAN的面積最大，當該像素點位于區(qū)域邊界時，則面積為最大的一半，當該像素點為角點時，USAN區(qū)域面積約為最大的1/4。SUSAN根據(jù)不同位置時USAN區(qū)域的面積來考察當前像素點為區(qū)域內(nèi)部點、邊緣點或角點。

USAN區(qū)域面積通過圓模板內(nèi)各像素與中心點像素比較得到的相似點的個數(shù)總和來表示，該相似比較函

數(shù)為：

函數(shù)

則與中心點像素相似點的個數(shù)為：

本文取圖像每11×11領域范圍內(nèi)來搜索CRF為極大值的像素點，當該像素點CRF數(shù)值大于控制閾值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 ); //創(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 ", cornerCount);

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

if(cornerCount>0)

{

for (i=0; 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;

}

技術綜述

角點是圖像很重要的特征，對圖像圖形的理解和分析有很重要的作用。對灰度圖像、二值圖像、邊緣輪廓曲線的角點檢測算法進行綜述，分析了相關的算法，并對各種檢測算法給出了評價。

角點檢測程序

文獻標識碼：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

角點沒有明確的數(shù)學定義，但人們普遍認為角點是二維圖像亮度變化劇烈的點或圖像邊緣曲線上曲率極大值的點。這些點在保留圖像圖形重要特征的同時，可以有效地減少信息的數(shù)據(jù)量，使其信息的含量很高，有效地提高了計算的速度，有利于圖像的可靠匹配，使得實時處理成為可能。其在三維場景重建、運動估計、目標跟蹤、目標識別、圖像配準與匹配等計算機視覺領域起著非常重要的作用。

角點檢測算法可以說各種各樣。一般使用者僅僅要求得到一個準確的角點檢測結(jié)果或該檢測算法易于編程實現(xiàn)，滿足實際后續(xù)匹配等應用需要。本文對角點檢測按檢測目標進行分類，對各種類下的檢測算法逐一進行歸納分析。

灰度圖像

基于梯度的方法

基于梯度的方法是通過計算邊緣的曲率來判斷角點的存在性，角點計算數(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開始，按照前面所確定的原則尋找較小尺度上的對應角點，直到最小的尺度為止；清除最小尺度上與上一尺度不對應的點，得到最終角點結(jié)果。針對文獻的錯誤，就對某一尺度上的角點檢測算法，文獻指出角點不僅是水平面截線上的曲率極值點，也是該點在最大梯度方向上其最大梯度的模達到極大值，是滿足兩個條件的點集的交集。

基于模板的方法

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

較早的直接基于灰度圖像角點檢測是文獻提出的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的局部結(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）>λ來判定其是否為角點。這里的關鍵是閾值λ和窗口D的大小的確定，D的大小一般為2~10,太大的窗口會引起角點移動，窗口太小則會丟失相距較近的角點。

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

由算法的實現(xiàn)和相關結(jié)果可以看出,KLT算法比Harris算法檢測角點的質(zhì)量高，但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ù)與信號的卷積結(jié)果之差，因此抗噪聲的能力較強。

基于模板梯度組合方法

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

二值圖像

一組角點檢測模板和原理說明

輪廓曲線

計算角點強度k

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

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

計算曲線曲率的極值

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

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

多尺度角點檢測

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

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

在上面的多尺度檢測中，僅考慮了角點的位置信息，文獻[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)進行小波變換，在不同的尺度上，角點的小波變換幅值始終是最大的，位置始終是不變的。如果有噪聲，那么噪聲的幅值只存在于有限的尺度空間上，結(jié)合幅值判據(jù)和位置判據(jù)就能夠很好地確定角點，剔除偽角點，結(jié)果的準確性很高。同時結(jié)合不同的角點模型，還可以對角點是單角、雙角、三角的屬性作出判別。

小結(jié)

角點作為圖像上的特征點，包含有重要的信息，在圖像融合和目標跟蹤及三維重建中有重要的應用價值。但是基于實際應用需求，從角點檢測的快速性、準確性、魯棒性等要求出發(fā)，可以看出上面對各種角點檢測算法的分析各有利弊。直接基于圖像的角點檢測基本上是全局搜索；基于邊緣輪廓的角點檢測數(shù)據(jù)量較少，可以采用多分辨分析并行處理，從灰度圖像得到邊緣輪廓曲線要經(jī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.

一種改進的SUSAN角點檢測算法

[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]費旭東，荊仁杰?；谥R的快速角點提取[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]肖茜，魯宏偉?；诟咚蛊交淖赃m應角點檢測[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]王展，黃埔堪，萬建偉?；诙喑叨刃〔ㄗ儞Q的二維圖像角點檢測技術[J].國防科技大學學報,1999,21(2):46-49.

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

作者簡介：

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

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