謝志明，黃偉瓊，黃道平

(華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣州 510640)

基于輪廓曲線的角點(diǎn)識(shí)別方法

謝志明，黃偉瓊，黃道平

(華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣州 510640)

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

Harris算法;角點(diǎn)檢測(cè);輪廓曲線;角點(diǎn)定位

0 前言

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

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

1 Harris角點(diǎn)檢測(cè)算法

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

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

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

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

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

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

2 基于輪廓曲線的角點(diǎn)檢測(cè)

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

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

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

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

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

圖1 角點(diǎn)粗定位實(shí)驗(yàn)結(jié)果

采用3*3模板如圖2，計(jì)算模板中心點(diǎn)與兩邊像素點(diǎn)的夾角θ:

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

圖2 3*3窗口模板

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

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

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

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

4 角點(diǎn)提取實(shí)驗(yàn)結(jié)果與分析

本節(jié)采用一張1024*1280的工件圖片對(duì)兩個(gè)算法分別進(jìn)行實(shí)驗(yàn)，并對(duì)結(jié)果進(jìn)行分析比較。

4.1 實(shí)驗(yàn)結(jié)果

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

圖3 Harris角點(diǎn)檢測(cè)

圖4 基于曲線輪廓的角點(diǎn)檢測(cè)

4.2 實(shí)驗(yàn)結(jié)果時(shí)間復(fù)雜度分析

兩算法運(yùn)行時(shí)間對(duì)比見(jiàn)表2。

表2 兩算法運(yùn)行時(shí)間對(duì)比

4.3 角點(diǎn)識(shí)別精確度分析

角度識(shí)別精度見(jiàn)表3。

表3 角點(diǎn)識(shí)別精確度

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

5 結(jié)論

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

［1］張海燕，李元媛，儲(chǔ)晨昀.基于圖像分塊的多尺度Harris角點(diǎn)檢測(cè)方法［J］.計(jì)算機(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ù)字圖像角點(diǎn)檢測(cè)算法探討［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］郭曉晶.圖像角點(diǎn)檢測(cè)方法的研究［D］.青島:青島大學(xué)，2009.

［6］王葳，唐一平，任娟莉，等.一種改進(jìn)的harris角點(diǎn)提取算法［J］.光學(xué)精密工程，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—)，男，廣州人，華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院碩士研究生，主要從事數(shù)控機(jī)床方面的研究，(E－mail)jimmy_ming@163.com;黃道平(1961—)，男，廣東河源人，華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院教授，博士生導(dǎo)師，主要從事神經(jīng)網(wǎng)絡(luò)，Matlab教學(xué)與仿真等研究。