一種快速自適應(yīng)的Harris角點(diǎn)檢測方法研究

王慧勇

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

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

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

本文結(jié)合Harris算法和FAST算法的優(yōu)勢，提出了一種快速自適應(yīng)Harris角點(diǎn)檢測算法。該方法能有效地自適應(yīng)提取角點(diǎn)，并滿足實(shí)時(shí)性要求。

1 Harris算法原理

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

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

可以發(fā)現(xiàn)，Moravec角點(diǎn)檢測算法有幾個(gè)很明顯的缺陷:

圖1 中心點(diǎn)沿(1，1)方向移動(dòng)一格

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

2)自相關(guān)強(qiáng)度值的計(jì)算，只有離散的8個(gè)45°方向。

Harris角點(diǎn)檢測算法針對些缺陷做出以下改進(jìn):

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

圖2 高斯窗函數(shù)

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

寫成矩陣形式

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

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

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

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

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

2 Harris角點(diǎn)檢測算法的局限

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

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

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

3 基于預(yù)篩選及自適應(yīng)閾值的Harris角點(diǎn)檢測算法

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

圖5 原Harris算法和改進(jìn)的Harris算法流程圖

3.1 預(yù)篩選

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

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

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

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

圖6 FAST初選角點(diǎn)判定法

3.2 自適應(yīng)閾值

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

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

圖7 Rmax取值分布圖

分析得出:Rmax=p×108，其中p＞0，定義閾值T=k×Rmax，選取素材庫中圖片進(jìn)行實(shí)驗(yàn)。發(fā)現(xiàn)當(dāng)0＜p＜1時(shí)，灰度值變化不大，k取經(jīng)驗(yàn)值0.04;當(dāng)1＜p＜5時(shí)，灰度值變化一般，k取經(jīng)驗(yàn)值0.02;當(dāng)p＞5時(shí)，灰度值變化較大，k取經(jīng)驗(yàn)值0.01。如此，基本可以檢測出所有角點(diǎn)，并且偽角點(diǎn)比較少?？梢缘玫?/p>

式中:p=Rmax/108。

4 實(shí)驗(yàn)結(jié)果及性能分析

選取若干分辨率不同的圖像進(jìn)行MATLAB仿真實(shí)驗(yàn)，如圖8所示。

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

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

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

由表1可以發(fā)現(xiàn):對于所采集的圖像，預(yù)篩選后，后續(xù)需要遍歷的像素點(diǎn)只占原算法像素點(diǎn)的10%左右，遍歷時(shí)間一般都能降低一半。從表中可以看出改進(jìn)算法在處理大分辨率圖像時(shí)，優(yōu)勢更加明顯。大大縮短了角點(diǎn)檢測時(shí)間，有利于在實(shí)時(shí)處理中的應(yīng)用。

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

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

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

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

實(shí)際效果如圖11所示。

圖11 采用自適應(yīng)閾值算法角點(diǎn)檢測效果

通過實(shí)驗(yàn)可以發(fā)現(xiàn):基于Harris的快速自適應(yīng)角點(diǎn)檢測算法相比基于Harris角點(diǎn)檢測算法能得到更多的正確角點(diǎn)，同時(shí)抑制了偽角點(diǎn)的數(shù)目。避免了閾值選取不當(dāng)導(dǎo)致的角點(diǎn)檢測不準(zhǔn)確，且減少了大量校調(diào)閾值的工作。

5 結(jié)論

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

［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角點(diǎn)檢測［J］.中南大學(xué)學(xué)報(bào):自然科學(xué)版，2005，36(5):751-754.

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

［6］蔡耀儀，林海軍.基于Harris角點(diǎn)檢測的嵌入式穩(wěn)像系統(tǒng)設(shè)計(jì)［J］.電視技術(shù)，2012，36(13):12-16.

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

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