基于Sobel邊緣檢測的圓周Harris角點檢測算法

董立紅，彭業勛，符立梅

（西安科技大學計算機科學與技術學院，陜西西安710054）

0 引 言

圖像亮度發生劇烈變化，亦或者圖像邊緣曲線上曲率的極大值點［1］，稱之為角點。角點是在圖像處理中的一個重要特征，它主要運用到運動目標識別和跟蹤、圖像匹配等計算機視覺領域。角點檢測的精確度，直接決定了識別、跟蹤及匹配結果的好壞，因此角點檢測是計算機視覺處理中十分重要的環節。

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

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

1 Harris角點檢測

1. 1 Harris角點檢測原理

Harris算法是一種傳統的角點檢測算法，角點就是二維圖像灰度值的突變或者圖像邊緣的交線的輪廓點，在對圖像I（x，y）進行移動時，當移動距離是（Δx，Δy），可根據自相關函數給出公式

式中 （x，y）為中心圖像；w（x，y）為加權函數，一般為高斯加權函數。

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

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

可以簡單理解為圖像發生平移后，其自相關函數變成了近似的二項式函數

式中

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

1）當2個特征值差距很大時，即λ1?λ2亦或者λ2?λ1，表明自相關系數在一個方向上大，在其他方向上小，是圖像中的一條直線；

2）2個特征值相似且比較小，表明其在各個方向上的自相關系數都小，是圖像的平面區域；

3）2個特征值都比較大，而且近似，自相關函數在所有的方向上都增大，即為角點。

但是在進行讀圖像的角點檢測時，特征值的計算量十分的大，一般運用特征點的響應函數［17-18］CRF來計算。

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

1. 2 Harris算法步驟及不足

通過對Harris角點檢測的理解分析，可將其過程分為3部分

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

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

3）計算出每個Harris角點的響應值 CRF，對局部鄰域進行非極大值抑制，與給定閾值進行比較，大于閾值的角點設置為角點。

Harris角點檢測有許多不足之處，比如人工設置閾值、抗躁性差、易產生角點簇、偽角點，及其運算時間長等缺點。

2 圓周Harris角點檢測

文中提出的圓周Harris角點檢測算法，首先采用Sobel邊緣檢測的方法來獲取備選角點，以此來提高檢測效率并剔除部分偽角點；隨后，對于圓周模板的旋轉不變性［21-22］，提出了圓周模板來代替傳統的矩形模板，提高了角點的檢測精度；最后對于角點簇，文中采用鄰近角點剔除的方法，剔除偽角點和角點簇，進一步提高了算法的檢測精度。

2. 1 備選角點的選取

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

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

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

當梯度G大于給定閾值時（文中選取閾值為150），文中認為該點就是邊緣檢測點，即備選角點。

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

Harris角點檢測的灰度相關矩陣為

角點檢測判別式為

圖片I經過旋轉、平移、縮放后，I′=h·S·I+β，其中G（σ）為卷積函數；h為標量，表明縮放的比例大小；S為旋轉矩陣；β為偏移量。變換后的坐標變換關系為

一階導數關系

式中Iu，Iv為圖像在u和v方向的偏導數。

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

原圖像的相關矩陣為

帶入可得

由于變換后的灰度相關性為

故變換后的灰度相關矩陣為

當h=1時，即發生平移和旋轉時，變換前后的矩陣是相似的，故其行列式det和跡trace不發生改變，所以旋轉和平移后判別式沒有影響。

當h≠1時，即縮放變換，變換后的矩陣不相似，故Harris角點檢測不具有尺度不變性。

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

圖1 實驗結果對比Fig.1 Comparison of experimental results

2. 3 剔除部分偽角點

在進行了角點的預篩選以及非極大值抑制之后，局部會有一些角點簇和偽角點出現，即在一定的領域內可能出現2個或者多個角點，這對于一些后續處理可能導致不準確，比如圖像匹配，角點簇可能導致匹配概率的明顯增加，因此文中應該消除這種現象的出現，文中采用鄰近角點的剔除，即在一定的局部范圍內，只允許一個非極大值的出現，當在局部范圍內，出現2個或者以上的角點，選取非極大值最大的作為角點，排除其他的角點，文中采用5*5的模板。

3 實驗結果和分析

為了更好地驗證文中算法的準確度，選擇積木圖像作為實驗原圖像（如圖1（a）所示）。參數分別選取 p＝0. 010，p＝0. 005，半徑 R＝2，將圓周窗口算法與傳統算法進行對比實驗，實驗結果如圖1所示。

3. 1 算法時間和準確度對比

閾值選取為p·Max，將傳統算法和文中算法進行比較，算法效率見表1，算法準確度（正確角點數／（正確角點數+偽角點數+漏檢角點數數））見表2.

圖2 傳統算法和圓周算法Fig.2 Traditional and circumferential algorithms

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

3. 2 旋轉不變性對比

將圖1（a）圖像旋轉45°角后作為實驗圖像，采用“錯準比”（（誤檢數+漏檢數）／準確數）對文中圓周檢測算法及傳統算法進行結果比較，實驗結果如圖3所示，錯準比比值越大，檢測效果越差，見表3.

表1 算法運行時間（單位秒）對比結果Tab le 1 Com parison of algorithm running time（in seconds）

表2 算法精確度對比結果Table 2 Algorithm accuracy comparison result

由表3可知，對于旋轉后圖像，提出的圓周檢測算法偽角點數得到了明顯的減少，漏檢角點也有所改善，因此文中算法的錯準比明顯低于傳統算法，尤其當p＝0.010時，錯準比由傳統算法的45／22下降至30／22.由此可見，提出的圓周檢測算法具有較強的旋轉不變性。

表3 實驗對比結果（旋轉45°）Table 3 Experimental comparison results（rotation 45°）

圖3 旋轉不變形實驗對比Fig.3 Rotation without deformation experiment comparison

3. 3 抗噪性對比

對原始圖像加入φ=0，δ=0. 005的高斯白噪聲［20］，對傳統算法和文中算法進行試驗對比。

如圖4所示對比傳統Harris角點檢測算法，文中算法大大改善了角點簇和偽角點的影響，因此文中算法具有較強的抗噪性。

圖4 加入噪音后實驗對比Fig.4 Experimental comparison after adding noise

4 結 論

1）實驗結果表明文中改進算法相較于傳統算法，檢測精度提高了約10.52%，檢測效率提高了約69.05%；

2）提出的改進算法相較于傳統算法，具有旋轉不變性及較強的抗噪性。由于本文算法閾值的選擇仍為人工選取，適用性與適應度不夠高，是未來研究的重點。