一種快速自適應的Harris角點檢測方法研究

王慧勇

(1.上海交通大學電子信息與電氣工程學院，上海 200240;2.上海電視廣播集團，上海 200070)

角點是一種重要的圖像特征點，其在各個方向梯度變化較大，或在邊緣曲線上具有曲率極大值，包含了重要的圖像特征信息。所以在物體識別、圖像配準、全景拼接等方面具有十分重要的意義［1-3］。準確并快速地提取到角點，能有效地降低信息處理量，大幅提高處理效率。

目前角點檢測方法通常基于圖像灰度信息，這種方法主要通過測算點的曲率及梯度來檢測角點。此類方法應用最廣泛的是Harris算法［4］，通過計算像素點所在位置的梯度來檢測角點。實驗結果表明，Harris角點檢測法具有良好的檢測效果，但該算法對圖像中的每個點都計算其響應值，然后在鄰域中選擇最優點，計算量大，難以滿足實時性要求。而Edward Rosten and Tom Drummond提出的FAST角點檢測法實時性好，但對邊緣易產生偽響應。同時傳統的檢測算法處理不同圖片，需要人為給出一個經驗閾值才能得到較理想的角點。

本文結合Harris算法和FAST算法的優勢，提出了一種快速自適應Harris角點檢測算法。該方法能有效地自適應提取角點，并滿足實時性要求。

1 Harris算法原理

Harris角點檢測算法［5-8］是C.Harris和MJ.Stephens提出的，是Moravec算法的改進。Moravec算法將像素點周邊的一個鄰域作為一個圖像塊，并檢測這個圖像塊經過少量偏移和原圖像塊的相關性。如圖1所示，假設像素點(x，y)的灰度值為f(x，y)，則圖像中每個像素點 (x，y)移動(a，b)后，灰度變化強度表示為

式中:(a，b)可以取(0，1)，(-1，1)，(-1，0)，(-1，-1)，(0，-1)，(1，-1)，(1，0)，(1，1)這 8 個基本方向。于是可以得到8個灰度變化強度值。將8個值中最小的值作為該像素點的角點像素變化值。求出每一個像素點的角點像素變化值，在局部圖像塊中，該值最大的點為角點。

可以發現，Moravec角點檢測算法有幾個很明顯的缺陷:

圖1 中心點沿(1，1)方向移動一格

1)由于窗口是方形，并且是二元的，因此響應函數會有噪聲;

2)自相關強度值的計算，只有離散的8個45°方向。

Harris角點檢測算法針對些缺陷做出以下改進:

1)用像素的變化梯度代替像素值相減，并引入高斯窗函數(見圖2)代替二值窗口函數，對離中心點越近的像素賦于越大的權重，以減少噪聲影響。

圖2 高斯窗函數

2)Moravec算子只考慮了每隔45°方向的共計8個固定的方向。Harris算子用Taylor展開去近似任意方向，可以計算任意方向上的像素值變化。于是對于局部微小的移動量［u，v］，可以近似得到下面的表達

寫成矩陣形式

式中:Ix為x方向的差分;Iy為y方向的差分;w(x，y)為高斯函數。

在完善了Moravec算法的缺陷后，Harris定義角點響應函數R=detM-k(traceM)2來確定像素點是否角點。其中detM= λ1× λ2，traceM= λ1+ λ2，k取(0.04～0.06)。

在圖像中，像素點可分為3種類型:平坦區域的像素點，物體邊緣的像素點，角點。它們分別有著不同的特性，如圖3所示。

結合R=detM-k(traceM)2，可知:1)平坦區域，λ1，λ2都很小;2)邊緣的點，λ1，λ2中一個值大，另外一個值小;3)角點:λ1，λ2都比較大(見圖4)。

顯而易見，Harris算法將遍歷圖像中的每一個像素點，求其角點響應函數R，R的值越大，對應的2個特征值λ1，λ2都應該很大，最后對整幅圖像得到的R做一個非極大抑制。通過設置R的閾值，在w×w范圍內尋找極大值點，對提取的角點個數進行限制。則在圖像中，同時滿足像素點R值大于閾值T和其R值在w×w鄰城內是局部極大值這兩個條件的點被視為是角點。

2 Harris角點檢測算法的局限

Harris角點檢測法具有良好的檢測效果，但是依然存在以下不足:

1)Harris角點檢測算法采用7×7的矩形高斯窗口，且對圖像中的每個點都計算其角點響應R值，然后在鄰域中選擇最優點。一張w×h圖像，共需進行w×h次角點響應R值計算和閾值比較。在處理大分辨率圖像時，該算法檢測時間將會大幅上升，難以滿足實時性要求。

2)Harris算法雖然利用非極大值抑制，但角點提取的效果完全依賴于閾值的設定。當閾值過大的時候，兩個像素點灰度值相差很大才能成為角點，從而丟失了很多應有的角點;而當閾值過小的時候，灰度值相差較小的兩個區域點也可滿足閾值條件，就產生了大量的偽角點。在處理不同圖像時，需要人為改變閾值，Harris角點檢測算法才能得到較理想的角點。

3 基于預篩選及自適應閾值的Harris角點檢測算法

針對以上兩個問題，本文引入預篩選以及自適應閾值的概念，具體流程圖如圖5所示。

圖5 原Harris算法和改進的Harris算法流程圖

3.1 預篩選

在處理圖片時先提取一批初選角點，然后再對提取出的初選角點進行Harris角點檢測。根據流程圖，雖然在計算角點響應值前增加了預篩選的過程，但預篩選后，留下來的待處理像素點數目遠遠小于圖像的所有像素點數目，如此將大幅縮短運算時間，提高角點檢測的效率。

改進的算法思想是利用像素點的相似度來提取初選角點。像素點的相似度將指檢測窗口中心點灰度值與其周圍n鄰域內其他像素點灰度值的相似程度，這種相似程度是用兩者灰度值之差來描述。如果鄰域內點的灰度值與中心點Point(i，j)的灰度值之差的絕對值在一個閾值t范圍內，則認為這個點與中心點是相似的。同時，計數器Counter開始計數。在中心點Point(i，j)點的n鄰域點全部被遍歷一邊之后，根據計數器Counter的大小，就可以判斷這個中心點是否是初選角點。

改進的算法將使用FAST角點檢測算法來考量像素點的相似度。FAST角點檢測算法是Edward Rosten和Tom Drummond在2006年提出的一種簡單快速的角點探測算法。該算法將角點定義為在角點的周圍鄰域內有足夠多的像素點的灰度值大于該點的灰度值或者小于該點的灰度值。

圖6中p點附近半徑為3的圓環上有16個點，若其中有連續的12個點的灰度值與p點的灰度值差別超過某一閾值，則可以認為p點為角點。通過預篩選的過程，可以得到初選角點。然后再對這些初選角點進行Harris運算去除偽角點，避免了對整幅圖像進行掃描，提高了角點檢測的效率。

圖6 FAST初選角點判定法

3.2 自適應閾值

對于某一幅特定的圖片采用某個閾值會得到比較好的角點檢測效果，但將這個特定的閾值應用到其他圖片上未必是最佳閾值。這就要求算法本身有能力計算出適合不同圖片的閾值。

考慮到閾值是在提取角點時才會使用，本文通過記錄角點響應函數值R，得出R的最大值Rmax，不同圖像的Rmax也不同。本文通過統計大量圖片，其中圖片來源為創意素材庫網(http://sc.52design.com/)，涵括人物、動物、風景、建筑等，基本能代表現實中的各種圖片。通過記錄素材庫中每張圖片Rmax，可以得到Rmax統計分布如圖7所示。

圖7 Rmax取值分布圖

分析得出:Rmax=p×108，其中p＞0，定義閾值T=k×Rmax，選取素材庫中圖片進行實驗。發現當0＜p＜1時，灰度值變化不大，k取經驗值0.04;當1＜p＜5時，灰度值變化一般，k取經驗值0.02;當p＞5時，灰度值變化較大，k取經驗值0.01。如此，基本可以檢測出所有角點，并且偽角點比較少。可以得到

式中:p=Rmax/108。

4 實驗結果及性能分析

選取若干分辨率不同的圖像進行MATLAB仿真實驗，如圖8所示。

圖8 不同分辨率的測試圖片

1)將利用FAST算法預篩選與原始Harris算法相比較，結果如表1所示。

表1 采用預篩選算法與原Harris算法效率對比

由表1可以發現:對于所采集的圖像，預篩選后，后續需要遍歷的像素點只占原算法像素點的10%左右，遍歷時間一般都能降低一半。從表中可以看出改進算法在處理大分辨率圖像時，優勢更加明顯。大大縮短了角點檢測時間，有利于在實時處理中的應用。

2)為了對比采用自適應閾值算法與原算法的實際效果。選取兩張不同的圖片，閾值T分別為2×106和5×106，實際角點檢測情況如圖9和圖10所示。

圖9 閾值T=2×106處理不同圖片效果差異

從圖9和圖10可以發現:同一個閾值在處理不同圖片時，檢測效果差異很大。對于示例中左邊圖像，灰度變化差異小，需要選擇相對小的閾值。示例中右邊圖像則相反。如果實踐中發現檢測效果不佳，則需要人為設置閾值，效率低下。采用自適應閾值算法后，其閾值T是圖像角點響應函數最大值的一個比值。這對于任意圖像都設定了閾值比較基準，可以得到較好的檢測效果。

圖10 閾值T=5×106處理不同圖片效果差異

實際效果如圖11所示。

圖11 采用自適應閾值算法角點檢測效果

通過實驗可以發現:基于Harris的快速自適應角點檢測算法相比基于Harris角點檢測算法能得到更多的正確角點，同時抑制了偽角點的數目。避免了閾值選取不當導致的角點檢測不準確，且減少了大量校調閾值的工作。

5 結論

文中對Harris角點檢測算法進行了分析，并在此基礎上改進了算法。通過使用FAST算法對圖像進行預篩選，提高算法的運行效率，并采用了自適應閾值使算法能根據圖像具體情況自動給出合理的閾值。對比改進的算法與原始算法，新算法避免了閾值的選擇，有效地克服了閾值選擇不當造成的角點冗余或丟失，并大幅縮短運算時間。

［1］SZELISKI R.Image alignment and stitching［EB/OL］.［2013-01-20］.http://research.microsoft.com/apps/pubs/default.aspxid=75695.

［2］SZELISKI R，KANG S B.Direct methods for visual scene reconstruction［C］//Proc.IEEE Workshop on Presentation of Visual Scenes.［S.l.］:IEEE Press，1995:25-33.

［3］CANNY J.A computational approach to edge detection［C］//Proc.IEEE Trans.PAMI，1996，8(6):679-697.

［4］陳白帆.基于尺度空間理論的Harris角點檢測［J］.中南大學學報:自然科學版，2005，36(5):751-754.

［5］朱建尚.基于GPU的實時亞像素Harris角點檢測［J］.計算機工程，2010，36(12):213-215.

［6］蔡耀儀，林海軍.基于Harris角點檢測的嵌入式穩像系統設計［J］.電視技術，2012，36(13):12-16.

［7］倪樂真，李玉山，劉洋，等.一種基于角點配對的穩像算法［J］.電視技術，2009，33(S2):71-74.

［8］王玉珠，楊丹，張小洪.基于B樣條的改進型Harris角點檢測算法［J］.計算機應用研究，2012，36(9):73-75.