S-Harris:一種改進的角點檢測算法

孫萬春，張建勛，朱佳寶，陳虹伶，鄭集元

(重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院, 重慶 400054)

角點檢測[1]是一種計算圖像中角點的數(shù)學(xué)方法，目前主要運用在圖像匹配、監(jiān)控視頻采集、目標跟蹤、圖像拼接、3D模型的建立等計算機視覺領(lǐng)域，通過提取圖像中的一些特殊興趣點，將其定義為角點，其是局部特征提取時間復(fù)雜度的關(guān)鍵性因素。在圖像中，角點檢測到的興趣點對局部特性的描述也起決定性作用[2]，同時由于角點的特殊性，其并不受旋轉(zhuǎn)、尺度變化等干擾，因此對其進行深入探究具有非常重要的意義。

目前，角點檢測方法分為三大類[3]：① 基于灰度圖像的角點檢測。計算邊緣曲率來判斷角點的存在，其主要和邊緣強度、邊緣方向的變化率有關(guān)。目前此類方法主要包含Harris算法、SUSAN算法、Moravec算法等。② 基于二值圖像角點檢測。由于經(jīng)過二值化處理，計算復(fù)雜性較低。袁寧等[4]利用細化圖像的特殊性，采用形態(tài)骨架來提取角點。由于二值圖像的角點檢測方法的一些計算過程在灰度圖像和輪廓曲線方法中均有采用，所以目前單獨對此方法進行研究的人較少。③ 基于輪廓曲線的角點檢測。通過高低尺度對目標圖像分離出輪廓曲率較大的值，再通過閾值參數(shù)的選定篩選出角點，常用的算法包括Mokhtarian的CSS算法[5]。

由于Harris算法計算較為簡單，并且計算結(jié)果比較穩(wěn)定[6]，國內(nèi)外眾多學(xué)者均采用該算法進行相關(guān)的工作。許佳佳等[7]通過構(gòu)建高斯尺度空間優(yōu)化Harris算法的尺度特性，但是該算法并未針對Harris算法本身進行相關(guān)算法上的優(yōu)化，不利于后期深入拓展。葛盼盼等[8]提出了一種Harris和Surf融合特征方法，利用Surf對尺度變化的魯棒性和Harris算法的特征提取穩(wěn)定性來進行圖像匹配。張從鵬等[9]利用Harris角點檢測效果的穩(wěn)定性，將其運用到了矩形窗口檢測上。王民等[10]針對Harris算法在抗噪性和實時性能上的劣勢，提出了一種基于像素點灰度差的角點檢測算法，該算法雖然提高了檢測的效率，但是對于一些灰度變化較小以及紋理信息豐富的圖像，會因為灰度差丟失特征信息。

針對上述算法存在的問題，提出了一種灰度差分均值的思想。此外，針對算法在窗口滑動過程中對重疊像素點進行重復(fù)計算的情況，引入了積分圖像的思想，。

1 Harris角點檢測及其缺陷

1.1 Harris角點檢測方法

Harris角點檢測算法是由C.Harris和M.J.Stephens在1988年提出的一種基于信號點特征的提取算法[11-12]，其理論基礎(chǔ)是Moravec算法。Moravec算法對圖像中的中心像素點定義一個局部矩形檢測窗口，該窗口可以任意在水平、垂直、正反對角線等各個方向上進行微移，在不斷的微移過程提取矩形窗口的平均能量變化，并通過泰勒級數(shù)的思想來計算窗口的變化值，計算出角點。對于給定的一個圖像像素中心點C(x,y)，其任意微移后的灰度強度變化可表示為

[I(u,v)-I(u+Δx,v+Δy)]2

(1)

式(1)中矩形窗口的移動方向及其移動方向的相關(guān)權(quán)重u、v定義如下：

(2)

由式(2)定義區(qū)間可知，通過式(1)的窗口滑動，總共會產(chǎn)生8種不同方向的強度變化，如圖1所示。

圖1 窗口滑動任意方向示意圖

從圖1可知：Harris算法解決了Moravec算法在任意方向移動的難點。對式(1)的子項進行泰勒展開，并取其近似值，結(jié)果如式(4)所示。

I(u+Δx,v+Δy)=I(u,v)+Ix(u,v)·

Δx+Iy(u,v)·Δy+…+Rn(u,v)≈

I(u,v)+Ix(u,v)·Δx+Iy(u,v)·Δy

(4)

將求得的近似值式(4)代入自相關(guān)函數(shù)中可得：

(5)

通過式(5)可以看出：該算法解決了Moravec算法在任意方向移動的難點，其中Ix和Iy分別表示圖像在水平方向和垂直方向的導(dǎo)數(shù)。對式(5)中子項[Ix(u,v)·Δx+Iy(u,v)·Δy]2進行展開，結(jié)果如下：

2Ix(u,v)Iy(u,v)ΔxΔy=

(6)

將式 (6)代入原自相關(guān)表達式 (1)中可得：

[Ix(u,v)·Δx+Iy(u,v)·Δy]2=

(7)

式(7)中M表示為

(8)

由式(8)可知其為矩陣，假定其特征值分別為λ1、λ2，數(shù)學(xué)意義如圖2所示。

分析可知：特征值的大小有以下的性質(zhì)：① 在光滑區(qū)域λ1、λ2相近且差值較小；② 在邊緣、線段λ1、λ2差值較大；③ 在角點區(qū)域λ1、λ2相近且差值較大。

Harris算法針對計算特征值來判別角點的方法計算量大的問題，定義了一個角點響應(yīng)值R判斷準則：

R=detM-α·(traceM)2

(9)

式(9)中：detM是矩陣M的行列式；traceM是矩陣M的跡；α是經(jīng)驗常數(shù)值，通常取值范圍為0.04～0.06。因此，通過式(9)即可求得一幅圖像中所有的角點。

1.2 Harris算法存在的不足

在算法的實際運用中發(fā)現(xiàn)以下問題：① 在矩陣窗口的滑動過程中容易受到噪聲的干擾，對角點的最終位置等產(chǎn)生較大的影響。② 在角點響應(yīng)[13]的計算的過程中，容易產(chǎn)生相鄰像素的重疊，增加計算的復(fù)雜度。③ 閾值的選擇對角點的判斷有直接關(guān)系。在Harris算法中，閾值的選取只能通過經(jīng)驗來進行判斷。閾值過大不僅會丟失角點信息，還會造成偽角點的產(chǎn)生；閾值較小不僅降低了角點的質(zhì)量，也會增大對噪聲的敏感。

圖2 λ1、λ2特征值相關(guān)數(shù)學(xué)意義

2 S-Harris:改進的角點檢測算法

2.1 算法改進思想

針對Harris算法存在的上述問題，特別是其不具備抗噪的特性，提出了一種灰度差分均值的思想。該方法首先對圖像中滑動窗口中的像素點，計算其鄰域周邊像素點的像素均值，對求得的均值再計算其灰度差值，通過求得的灰度差值來計算其灰度差均值，從而計算其方差。針對其在窗口滑動過程中對重疊像素點重復(fù)計算的情況，引入了積分圖像的思想。

2.2 自適應(yīng)灰度差分

,i=0,1,…,P-1

(10)

(11)

根據(jù)對比度值及其均值，計算標準差D：

(12)

由標準差近似估計離散度σ:

(13)

對像素中心點C(x,y)進行二值化編碼：

(14)

其中s(t) 是量化函數(shù)，定義如下：

(15)

從上述離散度的計算過程看，離散度會隨著每個鄰域的變化而變化，這說明離散度對選取點具有自適應(yīng)性。同時離散度受像素點選取的變化影響較小，因此其在同一類情況下的離散度變化也不大，說明離散度都能有效地描述選擇的像素點及其變化關(guān)系。因此，把離散度σ選作自適應(yīng)閾值具有有效性。

2.3 積分圖像

積分圖像[15]在對圖像中矩形區(qū)域特征進行描述時具有運算速度快的特性。在圖像矩形特征計算過程中，一旦計算出積分圖像，則可以在常量的時間內(nèi)計算出該積分圖像內(nèi)部任意大小矩形區(qū)域的特征信息，可以在降低運算量的同時提升計算機處理速度。

由圖3可知，對于任意一個滑動窗口區(qū)域∑S，可得到：

∑S=iiA+iiC-iiB-iiD

(16)

其中ii(x,y)定義如下：

(17)

依據(jù)上述公式改進式(1)，便可解決窗口滑動過程中重復(fù)計算問題。

圖3 積分圖像

3 實驗結(jié)果及分析

3.1 實驗環(huán)境

為了驗證改進的Harris算法在抗噪、檢測時間上可取得良好效果進行實驗。實驗平臺環(huán)境為DELL Windows 10系統(tǒng)，基于VS2012開發(fā)環(huán)境，采用Opencv2.4.13圖像處理庫。Intel i5-3470,3.20 GHz,8 GB 內(nèi)存空間。

3.2 實驗結(jié)果

為了驗證本文所提出的灰度差分理念以及引入積分圖像思想后對Harris算法的改進有效性，與Harris算法角點檢測結(jié)果進行了比較。

3.2.1 光噪下的角點檢測準確性

在驗證Harris算法抗噪性能時，選擇了一張重慶理工大學(xué)校門的圖片。對于實驗圖，分別對其高斯噪聲做均值為0.02、0.05和0.1處理，處理效果如圖4所示。

圖5為使用Harris算法后，原始圖像和高斯噪聲處理后的實驗效果。

圖6為使用S-Harris算法后，原始圖像和高斯噪聲處理后的實驗效果。

圖4 噪聲前后對比

圖5 噪聲對Harris算法的影響

圖6 噪聲對S-Harris算法的影響

從圖4～6可以看出：對圖像進行噪聲處理后，改進后的S-Harris算法相比Harris算法，檢測效果較好。算法本身受噪聲影響較小。表1是通過對重慶理工大學(xué)校門進行噪聲處理后角點檢測數(shù)量對比結(jié)果。

表1 改進的Harris算法在不同噪聲強度下的識別效果

實驗中，隨著噪聲強度的增加，Harris算法的誤檢概率較大，改進的S-Harris算法雖然也存在誤檢率，但是相比原算法，改進后效果較好。

3.2.2 角點檢測時間對比

對于同一幅圖像，研究角點檢測所花費的總時間，以此檢測S-Harris算法同Harris算法相比是否在時間消耗上進行了優(yōu)化。為了能更好地突出實驗效果，本實驗對比過程中選擇了已采用的重慶理工大學(xué)校門圖，同時對圖像分辨率分別進行適當(dāng)?shù)姆糯蠛涂s小，在此選擇300×65、450×98、675×147、1012×220、1 518×330的像素來進行實驗比較。圖7為在300×65像素下的實驗檢測效果對比。

圖7 300×65像素下算法對比效果

由表2可知：改進的S-Harris算法相比傳統(tǒng)的算法，運算時間效率上得到了明顯的提高，這得益于積分圖像的優(yōu)勢。

表2 算法運算時間效率對比

4 結(jié)束語

本文提出了一種S-Harris角點檢測算法，此方法針對Harris角點檢測算法存在的缺陷問題，引入了自適應(yīng)的灰度差分理念和積分圖像的思想。前者增強了該算法的抗噪性，根據(jù)像素點領(lǐng)域內(nèi)的對比度偏差，選取其自適應(yīng)的閾值，通過實驗證明該方法在不同的噪聲環(huán)境下，對角點提取的準確性和精確性相比原算法都得到了較好的提高。后者則有效地降低了時間復(fù)雜度。在圖像矩形特征計算中，計算出其積分圖像，則可在常量時間內(nèi)計算出該積分圖像內(nèi)部任意大小矩形區(qū)域的特征信息，不僅能降低運算量，還能提升計算機的處理能力。通過在不同的分辨率圖像下的對比實驗證明，利用該方法能夠在不改變?nèi)魏螀?shù)的前提下以及不降低角點檢測的準確性的同時檢測效率得到顯著提升。

通過將灰度差分理念和積分圖像思想相結(jié)合的方法，本文所提及的S-Harris算法不僅能在對不同噪聲環(huán)境下得到有較穩(wěn)定的角點檢測效果，并且對于較高的圖像分辨率角點檢測時間也有明顯的改善。未來工作中，計劃在視頻圖像應(yīng)用領(lǐng)域中應(yīng)用該算法，進一步驗證算法的有效性。