基于輪廓曲線的角點識別方法

謝志明，黃偉瓊，黃道平

(華南理工大學自動化科學與工程學院，廣州 510640)

基于輪廓曲線的角點識別方法

謝志明，黃偉瓊，黃道平

(華南理工大學自動化科學與工程學院，廣州 510640)

Harris角點檢測算法是一種經(jīng)典的角點檢測算子，針對其過于依賴閾值選取及計算量大的缺點，論文提出一種改進的基于輪廓曲線的角點識別的方法，通過判斷邊緣點方向性，先確定出粗角點，再采取由小尺度到大尺度逐步剔除偽角點的方法，最終實現(xiàn)角點識別。實驗結(jié)果表明，文中方法對角點提取的時間僅為Harris算法的5%，而且角點定位精確，漏檢率低。

Harris算法;角點檢測;輪廓曲線;角點定位

0 前言

圖像中的角點包含著圖像的重要信息，為具有高曲率的點，一般為圖像中兩條或者多條輪廓邊界的相交點或者灰度變化較為劇烈的點［1］。相對于圖像整體像素，圖像上的角點數(shù)較少，卻包含著圖像的重要信息，即它在有效減少信息量的同時，還保留著圖像中物體的重要特征信息，故角點的角點提取對后面的圖像分析具有重要意義，而且角點檢測在大多數(shù)的視覺處理任務(wù)中都有基礎(chǔ)性的意義，如運動估計、圖像匹配、攝像機標定、形狀分析以及視覺的定位和測量等方面。在機器視覺中，角點檢測被證實為一種重要的分析手段，正確識別角點，能夠有效識別圖像中物體形狀，進而進行圖像匹配以及參數(shù)計算［1］。

目前常用的角點檢測算法可歸納為3類:基于二值圖像的角點檢測、基于輪廓曲線的角點檢測、基于灰度圖像的角點檢測。Harris算子是基于圖像灰度的角點檢測方法，它通過計算像素點所在位置的梯度變化來檢測角點，若像素點所在位置的x方向梯度與y方向梯度的絕對值均比較大，則將該像素點判定為角點。然而傳統(tǒng)的Harris算子因為對圖像上所有像素點都進行角點響應(yīng)函數(shù)計算，如果圖片像素值較大，則計算量大，耗時較多，不能進行實時性處理;而且，Harris算子對角點響應(yīng)函數(shù)執(zhí)行非極大值抑制時，角點提取的效果依賴于閾值的設(shè)定:若閾值設(shè)置過大，則會導(dǎo)致有用角點信息的丟失;閾值設(shè)置過小，則會導(dǎo)致大量偽角點被提取。針對Harris算子耗時大及閾值設(shè)置不當?shù)膯栴}，本文在Harris算子的思想上，提出一種改進的基于輪廓曲線的角點檢測方法。

1 Harris角點檢測算法

Harris角點檢測算子［2］是Harris等人在1988年提出的［3］，是基于 Moravec 算子［4］的改進方法。Moravec 算子通過計算各像素沿 0°、45°、90°、135°等四個不同角度方向的平均灰度變化值，并選取最小值為該像素點的興趣值［5］。該算法簡單快速，但存在各向異性性、容易識別偽角點以及不能有效抑制噪聲等不足。針對這些不足，Harris受信號處理中自相關(guān)函數(shù)的啟發(fā)，給出與自相關(guān)函數(shù)相聯(lián)系的矩陣M［5］。M陣的特征值是自相關(guān)函數(shù)的一階曲率，在兩個曲率值都高的情況下，認為該點是特征點，從而可以改進Moravec算子識別出偽角點的不足。并且通過使用高斯濾波器平滑圖像來消除噪聲對于角點檢測的影響。

Harris算法以Moravec算法為基礎(chǔ)，以目標像素點為中心，取一個小窗口，將窗口沿上、下、左、右4個方向移動，計算窗口內(nèi)的灰度變化，并取最小值為該像素點的興趣值，即角點響應(yīng)函數(shù)值，再將該興趣值與閾值相比對，若大于，則認為該像素點為角點［1，5-6］。在某一點的圖像灰度自相關(guān)函數(shù)可以表示如式(1):

圖像在像素點(x，y)的極值曲率就可用矩陣M的特征值表示:如果矩陣M的兩個特征值都比較小，說明點(x，y)在平滑區(qū)域;如果矩陣M的有一個特征值比較大，一個特征值比較小，說明(x，y)在邊緣上;如果矩陣M兩個特征值都比較大，表明此時圖像窗口沿任意方向的曲率都非常大，說明點(x，y)為圖像的角點。

角點響應(yīng)函數(shù)可表示如式(5):

其中Det(M)為矩陣M的行列式，Det(M)=AB－C2，Tr(M)為矩陣M的跡，Tr(M)=A+B。當在某點R(x，y)大于給定的閾值時，認為該點為角點。

由于Harris角點檢測算法對角點的定位精度較差，過于依賴所選取的閾值，閾值過大，容易漏檢角點;若閾值過小，則易檢測出偽角點。在影像測量中，對圖像中的圖形進行尺寸計算是在圖像邊緣信息基礎(chǔ)上進行的，由Harris算子中所提出的角點檢測是依據(jù)像素點所在位置的梯度變化所啟發(fā)，提出了一種基于輪廓曲線的角點檢測方法。

2 基于輪廓曲線的角點檢測

圖像邊緣包含著圖像豐富的信息，是圖像分析的重要內(nèi)容，在影像測量中，對圖像中的圖形進行尺寸計算是在圖像邊緣信息基礎(chǔ)上進行的，本角點識別方法在對圖像進行預(yù)處理后，采用Roberts算子對圖像進行邊緣像素點識別，得到圖像的單像素邊緣。對圖像的單像素邊緣進行局部放大，可觀察到角點在邊緣輪廓上具有明顯的特點，與周圍邊緣點具有一定的夾角，根據(jù)這一特點，提出一種基于輪廓曲線的角點檢測方法。

通過觀察圖像的邊緣放大圖，可發(fā)現(xiàn)在小模板窗口中，圖像邊緣像素點排列呈現(xiàn)出單方向性，即0°、45°、90°、135°四種方向邊緣，當角點出現(xiàn)時，在像素點兩邊會出現(xiàn)兩種角度方向，本文的角點檢測算法是針對角點周圍的邊緣點相對位置信息的這種特點提出來的，為減小計算量，先采用小窗口模板(3*3)對角點進行粗定位，再用大窗口進行角點精確定位。算法實現(xiàn)如下:

(1)先對圖像進行中值濾波處理，再采用roberts算子進行邊緣單像素提取。

Roberts邊緣提取算子如式(7):

(2)對3*3窗口內(nèi)的邊緣像素進行方向判斷，若只有一個邊緣方向，則為普通邊緣點;若包括兩種方向信息，則先判斷為粗角點。由圖1c的角點粗定位圖可知，角點都被檢測出來了，但是同時也檢測出了很多偽角點，需要對角點進行篩選，精確定位。

圖1 角點粗定位實驗結(jié)果

采用3*3模板如圖2，計算模板中心點與兩邊像素點的夾角θ:

即若中心點 w5 兩邊的邊緣點同在 0°、45°、90°、135°方向，則確定該邊緣點為非角點。

圖2 3*3窗口模板

(3)在粗角點處采用由小尺度到大尺度模板，求角點兩邊直線夾角θ，若θ＜15°，即兩邊直線幾近成一條直線，則該角點為偽角點，去除之;反之，則為真角點，保持該角點信息。

3 時間復(fù)雜度分析

采用Harris算法進行圖像角點識別時，需要計算圖像中每一個像素點的角點響應(yīng)值，若Harris算法采用5*5的方形模板，方向?qū)?shù)采用Roberts算子，則計算每個像素點的角點響應(yīng)值中所需乘法次數(shù)為:(4+1+2+2+1)*(5*5)+4=254，加法次數(shù)為:(3+3+3)*(5*5)+2=227。采用本文所提出的基于輪廓曲線的角點識別方法進行角點識別時，計算邊緣點時候每個像素加減法次數(shù)為2次，每個邊緣點加減法12次，從粗角點到最終角點確認:加減法4次，乘除法3次;一般情況下，邊緣點和粗角點占圖像總像素比例較小，故每個像素點計算次數(shù)為:加減法:2+12+4=18，乘除法:3。對于大小為N*M像素的圖像，不考慮邊界的影響，將兩個方法的時間復(fù)雜度用表1進行比較:

表1 時間復(fù)雜度分析

4 角點提取實驗結(jié)果與分析

本節(jié)采用一張1024*1280的工件圖片對兩個算法分別進行實驗，并對結(jié)果進行分析比較。

4.1 實驗結(jié)果

通過圖3和圖4兩幅實驗結(jié)果圖比較分析可知，圖3中方框所選中的角點為Harris角點檢測算法多檢測出的偽角點，圖4中實線圓選中的角點為本文角點檢測方法的精確定位角點，虛線圓中為漏掉的角點。

圖3 Harris角點檢測

圖4 基于曲線輪廓的角點檢測

4.2 實驗結(jié)果時間復(fù)雜度分析

兩算法運行時間對比見表2。

表2 兩算法運行時間對比

4.3 角點識別精確度分析

角度識別精度見表3。

表3 角點識別精確度

通過圖3和圖4兩幅實驗結(jié)果圖比較分析可發(fā)現(xiàn)，本文提出的基于曲線輪廓的角點檢測算法對角點的提取比較完整，漏檢率較低，且運行速度快，算法實現(xiàn)簡單，適用于實時性的視覺測量系統(tǒng)。

5 結(jié)論

本文分析了Harris角點檢測算法的原理及其存在的缺點，針對其計算量大，非實時性的特點，提出一種改進的基于輪廓曲線的角點檢測算法，采用小尺度到大尺度逐步去除偽角點的方法。實驗結(jié)果表明，本文方法對角點提取的時間僅為Harris算法的5%，而且角點定位精確，漏檢率低。不過本文所提出的基于輪廓曲線的角點識別方法對噪聲比較敏感，須在后續(xù)工作中進行改進，提高它的抗噪性能。

［1］張海燕，李元媛，儲晨昀.基于圖像分塊的多尺度Harris角點檢測方法［J］.計算機應(yīng)用，2011，31(2):356－357.

［2］HARRISC，STEPHENSM.A combined corner and edge detector［C］.Proceedings of the Fourth Alvey Vision Conference，Manchester，UK，1998:147 －151.

［3］韓瑩.數(shù)字圖像角點檢測算法探討［J］.科技信息，2011:631.

［4］MORAVECHP.Towards automatic visual obstacle avoidance［C］.Proceedings of international joint conference on artificial intelligence，canbridge，MA，USA，1977:584－590.

［5］郭曉晶.圖像角點檢測方法的研究［D］.青島:青島大學，2009.

［6］王葳，唐一平，任娟莉，等.一種改進的harris角點提取算法［J］.光學精密工程，2008，16(10):1995－2001.

［7］Kitchen L，Rosenfeld A.Gray-level Corner Detection［J］.Pattern Recognition Letters，1982，1(2):95 －102.

［8］Mokhtarian F，Suomela R.Robust Image Corner Detection Through Curvature Scale Space［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，1998，20(12):1376－1381.

［9］ Freeman H，Davis L S.A Corner Fiding Algorithm for Chain-coded Curves［J］.IEEE Transaction on Computers，1977，C －26(3):297 －303.

［10］Wang H，Brandy M.Real-time Corner Detection Algorithm for Motion Estimation［J］.Image and Vision Computing，1995，13(9):695－703.

(編輯 趙蓉)

Identification Method Based on the Corner of the Contour Curve

XIE Zhi-ming，HUANGWei-qiong，HUANG Dao-ping
(College of Automation Science and Engineering，South China University of Technology，Guangzhou 510640，China)

Harris corner detection algorithm is a classical corner detection operator，for the shortcomings of over-reliance on the threshold and lots of calculation，this paper presents an improvedmethod of identification based on the corner of the contour curve，by judging the direction of edge points，determining the rough corners firstly，then gradually eliminating the pseudo-corner from small scale to large scale，finally achieving corner distinguished.The experimental result shows that the time of thismethod on corner extraction is just5%of the Harris algorithm，and locating corner precisely w ith low undetected.

harris algorithm;corner detection;profile curve;corner locating

TH165;TP391.41

A

1001－2265(2013)03－0090－03

2012－07－09;

2012－08－21

謝志明(1985—)，男，廣州人，華南理工大學自動化科學與工程學院碩士研究生，主要從事數(shù)控機床方面的研究，(E－mail)jimmy_ming@163.com;黃道平(1961—)，男，廣東河源人，華南理工大學自動化科學與工程學院教授，博士生導(dǎo)師，主要從事神經(jīng)網(wǎng)絡(luò)，Matlab教學與仿真等研究。