基于Sobel邊緣檢測(cè)的圓周Harris角點(diǎn)檢測(cè)算法

董立紅，彭業(yè)勛，符立梅

（西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西西安710054）

0 引 言

圖像亮度發(fā)生劇烈變化，亦或者圖像邊緣曲線上曲率的極大值點(diǎn)［1］，稱之為角點(diǎn)。角點(diǎn)是在圖像處理中的一個(gè)重要特征，它主要運(yùn)用到運(yùn)動(dòng)目標(biāo)識(shí)別和跟蹤、圖像匹配等計(jì)算機(jī)視覺領(lǐng)域。角點(diǎn)檢測(cè)的精確度，直接決定了識(shí)別、跟蹤及匹配結(jié)果的好壞，因此角點(diǎn)檢測(cè)是計(jì)算機(jī)視覺處理中十分重要的環(huán)節(jié)。

Harris算法是一種傳統(tǒng)的角點(diǎn)檢測(cè)算法，它是在Moravec算法的基礎(chǔ)上，由Harris C和Stephens M兩人在1988年改進(jìn)發(fā)展而來的。Harris角點(diǎn)檢測(cè)存在一些不足，如需人工設(shè)置閾值［2］，存在偽角點(diǎn)、角點(diǎn)簇，角點(diǎn)定位不精確以及檢測(cè)效率低下。針對(duì)Harris角點(diǎn)的信息丟失和位置偏移問題，2009年毛雁明、蘭美輝等人提出了雙閾值的想法，根據(jù)2次非極大值抑制，結(jié)合一定區(qū)域內(nèi)有一個(gè)角點(diǎn)的方法，確定角點(diǎn)，但是并沒有解決人工閾值選取［3］。對(duì)于定位不精確的問題，2013年張晶等提出B樣條函數(shù)來代替?zhèn)鹘y(tǒng)算法算法中的高斯平滑函數(shù)，進(jìn)而改進(jìn)了窗口大小選擇困難的問題，提高了定位精度［4］。2015年龔平、劉相濱提出了運(yùn)用像素點(diǎn)響應(yīng)值進(jìn)行曲線擬合的方法，根據(jù)峰值來確定角點(diǎn)，解決了人工閾值選取帶來的角點(diǎn)分布不均現(xiàn)象［5］。2015年鄒志遠(yuǎn)等人提出了一種自適應(yīng)閾值的方法，對(duì)人工選取閾值得到的改善，從而避免人工選取閾值造成的角點(diǎn)分布不合理的現(xiàn)象［6］。2016年趙萌等人提出了一種高斯函數(shù)參數(shù)自適應(yīng)的Harris角點(diǎn)檢測(cè)算法［7］，解決了高斯函數(shù)參數(shù)選取的不確定性影響。由于人工設(shè)置閾值易產(chǎn)生角點(diǎn)簇的現(xiàn)象，2017年張見雙等人提出了一種改進(jìn)的算法［8］，通過圖像分塊處理，并在每個(gè)圖像塊中進(jìn)行自適應(yīng)閾值設(shè)置［9-10］的方法，改善了角點(diǎn)簇現(xiàn)象。

針對(duì)Harris算法的不足，上述提到的不同方法都取得了一定的成效，但均不同程度地降低了檢測(cè)算法的運(yùn)算效率，如何在提高檢測(cè)算法效率的同時(shí)，降低誤檢測(cè)的率成為文中的研究方向。文中提出運(yùn)用Sobel邊緣檢測(cè)［11-12］來備選角點(diǎn)來提高檢測(cè)｀效率；在進(jìn)行非極大值抑制時(shí)，文中把傳統(tǒng)的矩形模板改為圓周模板，該模板具有旋轉(zhuǎn)不變性，大大改善了圖像角點(diǎn)的檢測(cè)精度，最后采用鄰域內(nèi)臨近角點(diǎn)剔除［13-14］的方法，排除角點(diǎn)簇，進(jìn)一步提高檢測(cè)的精確度。

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

1. 1 Harris角點(diǎn)檢測(cè)原理

Harris算法是一種傳統(tǒng)的角點(diǎn)檢測(cè)算法，角點(diǎn)就是二維圖像灰度值的突變或者圖像邊緣的交線的輪廓點(diǎn)，在對(duì)圖像I（x，y）進(jìn)行移動(dòng)時(shí)，當(dāng)移動(dòng)距離是（Δx，Δy），可根據(jù)自相關(guān)函數(shù)給出公式

式中 （x，y）為中心圖像；w（x，y）為加權(quán)函數(shù)，一般為高斯加權(quán)函數(shù)。

一般我們把上式中 I（u+Δx，v+Δy）進(jìn)行一階的泰勒展開

式中 Ix，Iy分別為I（x，y）在 x軸方向上和y軸方向上的一階偏導(dǎo)數(shù)，由以上（2）代入式（1）可得

可以簡(jiǎn)單理解為圖像發(fā)生平移后，其自相關(guān)函數(shù)變成了近似的二項(xiàng)式函數(shù)

式中

二次函數(shù)就是一個(gè)橢圓函數(shù)，它的扁率和尺寸是由矩陣M（x，y）的特征值決定的，假設(shè)它的特征值［15-16］分別為 λ1，λ2，當(dāng)它的大小可分為 3種情況

1）當(dāng)2個(gè)特征值差距很大時(shí)，即λ1?λ2亦或者λ2?λ1，表明自相關(guān)系數(shù)在一個(gè)方向上大，在其他方向上小，是圖像中的一條直線；

2）2個(gè)特征值相似且比較小，表明其在各個(gè)方向上的自相關(guān)系數(shù)都小，是圖像的平面區(qū)域；

3）2個(gè)特征值都比較大，而且近似，自相關(guān)函數(shù)在所有的方向上都增大，即為角點(diǎn)。

但是在進(jìn)行讀圖像的角點(diǎn)檢測(cè)時(shí)，特征值的計(jì)算量十分的大，一般運(yùn)用特征點(diǎn)的響應(yīng)函數(shù)［17-18］CRF來計(jì)算。

式中 det M為M的行列式；trace M為矩陣M的跡；CRF為角點(diǎn)的響應(yīng)函數(shù)；k為常數(shù)，一般取k∈（0. 04，0. 06）。響應(yīng)函數(shù) CRF值大于預(yù)先設(shè)定的閾值，且為局部最大值，我們稱這個(gè)點(diǎn)為候選角點(diǎn)。

1. 2 Harris算法步驟及不足

通過對(duì)Harris角點(diǎn)檢測(cè)的理解分析，可將其過程分為3部分

1）首先應(yīng)該求出矩陣M以及分別在x軸（水平方向）、y軸（垂直方向）上的梯度；

2）對(duì)圖像做高斯濾波［19-20］處理，求出新的矩陣M；

3）計(jì)算出每個(gè)Harris角點(diǎn)的響應(yīng)值 CRF，對(duì)局部鄰域進(jìn)行非極大值抑制，與給定閾值進(jìn)行比較，大于閾值的角點(diǎn)設(shè)置為角點(diǎn)。

Harris角點(diǎn)檢測(cè)有許多不足之處，比如人工設(shè)置閾值、抗躁性差、易產(chǎn)生角點(diǎn)簇、偽角點(diǎn)，及其運(yùn)算時(shí)間長(zhǎng)等缺點(diǎn)。

2 圓周Harris角點(diǎn)檢測(cè)

文中提出的圓周Harris角點(diǎn)檢測(cè)算法，首先采用Sobel邊緣檢測(cè)的方法來獲取備選角點(diǎn)，以此來提高檢測(cè)效率并剔除部分偽角點(diǎn)；隨后，對(duì)于圓周模板的旋轉(zhuǎn)不變性［21-22］，提出了圓周模板來代替?zhèn)鹘y(tǒng)的矩形模板，提高了角點(diǎn)的檢測(cè)精度；最后對(duì)于角點(diǎn)簇，文中采用鄰近角點(diǎn)剔除的方法，剔除偽角點(diǎn)和角點(diǎn)簇，進(jìn)一步提高了算法的檢測(cè)精度。

2. 1 備選角點(diǎn)的選取

通過對(duì)角點(diǎn)定義易得，角點(diǎn)一定在圖像的邊緣上，因此文中采用Sobel邊緣檢測(cè)算法對(duì)圖像進(jìn)行邊緣檢測(cè)，設(shè)置一個(gè)閾值（文中Sobel中閾值為150），當(dāng)某一像素的梯度值大于閾值時(shí)，文中認(rèn)為它就是邊緣，否則認(rèn)為其不是邊緣，把檢測(cè)到的邊緣當(dāng)做備選角點(diǎn)，從而為后來Harris角點(diǎn)檢測(cè)減少了運(yùn)行時(shí)間。文中采用積木圖作為實(shí)驗(yàn)原圖（如圖1（a）所示），通過 Sobel邊緣算法進(jìn)行備選角點(diǎn)，由于只在積木的邊緣點(diǎn)進(jìn)行檢測(cè)故得到5 141個(gè)角點(diǎn)（如圖1（b）所示）。原圖積木圖為256*256=65 536個(gè)像素點(diǎn)，備選角點(diǎn)遠(yuǎn)小于原積木的像素點(diǎn)個(gè)數(shù)，運(yùn)行個(gè)數(shù)約為原來的7.84%，極大地減少了運(yùn)行時(shí)間。

Sobel算子包含2組（橫向和縱向）3*3的矩陣，它們分別在x方向和y方向與原圖像進(jìn)行平面卷積，為了得出x方向及y方向的亮度差分近似值。假設(shè)我們把A作為我們的原始圖像，Gx及Gy分別為方向x及方向y的圖像，其公式如下

計(jì)算每一個(gè)像素的梯度大小，可以用Gx和Gy近似值可得公式如下

當(dāng)梯度G大于給定閾值時(shí)（文中選取閾值為150），文中認(rèn)為該點(diǎn)就是邊緣檢測(cè)點(diǎn)，即備選角點(diǎn)。

2. 2 圓周非極大值抑制窗口

Harris角點(diǎn)檢測(cè)的灰度相關(guān)矩陣為

角點(diǎn)檢測(cè)判別式為

圖片I經(jīng)過旋轉(zhuǎn)、平移、縮放后，I′=h·S·I+β，其中G（σ）為卷積函數(shù)；h為標(biāo)量，表明縮放的比例大小；S為旋轉(zhuǎn)矩陣；β為偏移量。變換后的坐標(biāo)變換關(guān)系為

一階導(dǎo)數(shù)關(guān)系

式中Iu，Iv為圖像在u和v方向的偏導(dǎo)數(shù)。

將矩陣窗函數(shù)變成一維向量，利用相關(guān)矩陣表示相關(guān)矩陣M，在原圖像中，Iu加權(quán)后利用一維向量表示為a，Iv加權(quán)后用一維向量表示為b，同理，Iu′，Iv′變換后用 a′，b′來表示。公式如下所示

原圖像的相關(guān)矩陣為

帶入可得

由于變換后的灰度相關(guān)性為

故變換后的灰度相關(guān)矩陣為

當(dāng)h=1時(shí)，即發(fā)生平移和旋轉(zhuǎn)時(shí)，變換前后的矩陣是相似的，故其行列式det和跡trace不發(fā)生改變，所以旋轉(zhuǎn)和平移后判別式?jīng)]有影響。

當(dāng)h≠1時(shí)，即縮放變換，變換后的矩陣不相似，故Harris角點(diǎn)檢測(cè)不具有尺度不變性。

在一般的Harris檢測(cè)中，一般選用3*3的模板（如圖2（a）所示）進(jìn)行與周圍的8鄰域進(jìn)行比較角點(diǎn)響應(yīng)值，只有當(dāng)8鄰域響應(yīng)值均小于中心點(diǎn)時(shí)，認(rèn)為此時(shí)的中心點(diǎn)是該模板中的極大值點(diǎn)。在傳統(tǒng)的算法中，由于非極大值抑制窗口為矩形，當(dāng)圖像發(fā)生旋轉(zhuǎn)時(shí)，非極大值抑制窗口內(nèi)的值將會(huì)發(fā)生變化，對(duì)于檢測(cè)的角點(diǎn)的非極大值抑制也會(huì)隨之改變（如圖2（b）所示），因此文中提出圓周非極大值抑制窗口方法（如圖2（c）所示），通過圓周上像素點(diǎn)與中心點(diǎn)的比較來確定角點(diǎn)，當(dāng)中心點(diǎn)的角點(diǎn)響應(yīng)值大于圓周上所有的值時(shí)，認(rèn)為此時(shí)的中心點(diǎn)就是角點(diǎn)。由于圓周上各點(diǎn)到中心點(diǎn)距離相等，當(dāng)圖像發(fā)生旋轉(zhuǎn)時(shí)，圓周上的點(diǎn)不會(huì)發(fā)生變化，進(jìn)而模板內(nèi)的非極大值抑制也不會(huì)改變（如圖2（d）所示），因此文中提出的圓周非極大值抑制窗口算法具有旋轉(zhuǎn)不變性。

圖1 實(shí)驗(yàn)結(jié)果對(duì)比Fig.1 Comparison of experimental results

2. 3 剔除部分偽角點(diǎn)

在進(jìn)行了角點(diǎn)的預(yù)篩選以及非極大值抑制之后，局部會(huì)有一些角點(diǎn)簇和偽角點(diǎn)出現(xiàn)，即在一定的領(lǐng)域內(nèi)可能出現(xiàn)2個(gè)或者多個(gè)角點(diǎn)，這對(duì)于一些后續(xù)處理可能導(dǎo)致不準(zhǔn)確，比如圖像匹配，角點(diǎn)簇可能導(dǎo)致匹配概率的明顯增加，因此文中應(yīng)該消除這種現(xiàn)象的出現(xiàn)，文中采用鄰近角點(diǎn)的剔除，即在一定的局部范圍內(nèi)，只允許一個(gè)非極大值的出現(xiàn)，當(dāng)在局部范圍內(nèi)，出現(xiàn)2個(gè)或者以上的角點(diǎn)，選取非極大值最大的作為角點(diǎn)，排除其他的角點(diǎn)，文中采用5*5的模板。

3 實(shí)驗(yàn)結(jié)果和分析

為了更好地驗(yàn)證文中算法的準(zhǔn)確度，選擇積木圖像作為實(shí)驗(yàn)原圖像（如圖1（a）所示）。參數(shù)分別選取 p＝0. 010，p＝0. 005，半徑 R＝2，將圓周窗口算法與傳統(tǒng)算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖1所示。

3. 1 算法時(shí)間和準(zhǔn)確度對(duì)比

閾值選取為p·Max，將傳統(tǒng)算法和文中算法進(jìn)行比較，算法效率見表1，算法準(zhǔn)確度（正確角點(diǎn)數(shù)／（正確角點(diǎn)數(shù)+偽角點(diǎn)數(shù)+漏檢角點(diǎn)數(shù)數(shù)））見表2.

圖2 傳統(tǒng)算法和圓周算法Fig.2 Traditional and circumferential algorithms

由實(shí)驗(yàn)結(jié)果可知，原始Harris角點(diǎn)檢測(cè)算法的漏檢角點(diǎn)比較多，運(yùn)行時(shí)間比較長(zhǎng)，提出的圓周角點(diǎn)檢測(cè)算法，漏檢角點(diǎn)明顯減少，以p＝0.010為例，準(zhǔn)確度由傳統(tǒng)算法的61.19%提高到76.92%，且通過采用Sobel邊緣檢測(cè)角點(diǎn)備選方法，大大提高了算法的檢測(cè)效率，平均時(shí)間從原來的0.769 583 s降低到0.238 220 s，約為傳統(tǒng)算法的31%.

3. 2 旋轉(zhuǎn)不變性對(duì)比

將圖1（a）圖像旋轉(zhuǎn)45°角后作為實(shí)驗(yàn)圖像，采用“錯(cuò)準(zhǔn)比”（（誤檢數(shù)+漏檢數(shù)）／準(zhǔn)確數(shù)）對(duì)文中圓周檢測(cè)算法及傳統(tǒng)算法進(jìn)行結(jié)果比較，實(shí)驗(yàn)結(jié)果如圖3所示，錯(cuò)準(zhǔn)比比值越大，檢測(cè)效果越差，見表3.

表1 算法運(yùn)行時(shí)間（單位秒）對(duì)比結(jié)果Tab le 1 Com parison of algorithm running time（in seconds）

表2 算法精確度對(duì)比結(jié)果Table 2 Algorithm accuracy comparison result

由表3可知，對(duì)于旋轉(zhuǎn)后圖像，提出的圓周檢測(cè)算法偽角點(diǎn)數(shù)得到了明顯的減少，漏檢角點(diǎn)也有所改善，因此文中算法的錯(cuò)準(zhǔn)比明顯低于傳統(tǒng)算法，尤其當(dāng)p＝0.010時(shí)，錯(cuò)準(zhǔn)比由傳統(tǒng)算法的45／22下降至30／22.由此可見，提出的圓周檢測(cè)算法具有較強(qiáng)的旋轉(zhuǎn)不變性。

表3 實(shí)驗(yàn)對(duì)比結(jié)果（旋轉(zhuǎn)45°）Table 3 Experimental comparison results（rotation 45°）

圖3 旋轉(zhuǎn)不變形實(shí)驗(yàn)對(duì)比Fig.3 Rotation without deformation experiment comparison

3. 3 抗噪性對(duì)比

對(duì)原始圖像加入φ=0，δ=0. 005的高斯白噪聲［20］，對(duì)傳統(tǒng)算法和文中算法進(jìn)行試驗(yàn)對(duì)比。

如圖4所示對(duì)比傳統(tǒng)Harris角點(diǎn)檢測(cè)算法，文中算法大大改善了角點(diǎn)簇和偽角點(diǎn)的影響，因此文中算法具有較強(qiáng)的抗噪性。

圖4 加入噪音后實(shí)驗(yàn)對(duì)比Fig.4 Experimental comparison after adding noise

4 結(jié) 論

1）實(shí)驗(yàn)結(jié)果表明文中改進(jìn)算法相較于傳統(tǒng)算法，檢測(cè)精度提高了約10.52%，檢測(cè)效率提高了約69.05%；

2）提出的改進(jìn)算法相較于傳統(tǒng)算法，具有旋轉(zhuǎn)不變性及較強(qiáng)的抗噪性。由于本文算法閾值的選擇仍為人工選取，適用性與適應(yīng)度不夠高，是未來研究的重點(diǎn)。