一種改進的Shi-Tomasi角點檢測方法

彭曉星 羅 霄 韓寶玲

1(北京理工大學光電學院 北京 100081) 2(北京理工大學計算機學院 北京 100081) 3(北京理工大學機械與車輛學院 北京 100081)

0 引 言

為了從圖像中獲取我們感興趣的信息，我們通常通過提取圖像特征的方式來實現。點特征作為圖像特征的其中一種，它保留了圖像中物體的重要特征信息并且具有表征圖像特征準確、穩定可靠的特點[1]。角點檢測算法廣泛應用在圖像匹配、運動估計、相機標定與視覺定位等方面[2]。

目前已有的角點檢測算法主要分為兩大類：(1) 基于圖像邊緣信息的角點檢測；(2) 基于圖像灰度變化的角點檢測算法。基于圖像邊緣信息的角點檢測算法是通過對圖像進行邊緣提取，再通過尋找邊緣上曲率較大的點或者多條邊緣線的交點來提取角點。這類算法有基于小波變換模極大的角點檢測算法[3]、基于邊界曲率的角點檢測算法[4]等，此類算法中角點對邊緣線依賴較大，當邊緣發生中斷時，角點提取算法則會產生很大誤差。基于圖像灰度變化的角點提取算法是通過圖像中像素的灰度變化來實現角點提取。這類算法有Moravec算法[5]、Harris算法[6]、SUSAN算法[7]、Shi-Tomasi算法[8]等。此類算法中Harris角點檢測算法表現較好，應用十分廣泛，但其不具備尺度不變性的特點，基于此許多學者提出了相應的改進算法，為了使Harris算法具備在多尺度下實現角點的有效提取，張小洪等[2]在Harris算法中引入了多尺度的思想，從大尺度到小尺度提取候選點集，從而實現Harris多尺度角點檢測的算法。文獻[9-10]基于小波變換和B樣條函數實現Harris多尺度角點檢測。但是他們只使用了單一尺度，在提取候選角點時尺度過大時容易丟失真實角點，尺度過小容易受噪聲的影響。針對此缺陷，葉鵬等[11]提出在多個尺度上分別求得角點響應值和模糊系數,通過疊加求出原始圖像每個點的模糊角點響應值，充分利用了各個尺度的信息。上述方法都具有計算量大且提取角點不夠準確的問題，本文針對這些問題，選擇比Harris角點計算量小的Shi-Tomasi角點算法來進行改進，首先通過構建圖像金字塔使得算法可以在多尺度下提取角點，同時通過對每層圖像進行均值濾波對圖像去噪，提升抗噪性，利用雙模板組合的方式去除偽角點，提升角點檢測的精度。

1 Shi-Tomasi角點檢測算法原理及其局限性

1993年Shi等在Harris算法的基礎上提出Shi-Tomasi角點檢測算法，他們發現使用Harris角點檢測算法中自相關矩陣較小的特征值即可很好地表示角點。因此定義了更為簡單的角點響應函數。Shi-Tomasi算法的主體與Harris算法一致，首先來看Harris算法，Harris算法角點的原理是計算窗口內點的灰度變化來檢測角點。如圖1所示，朝各個方向移動固定大小窗口，如果窗口內的灰度幾乎不變，認為是平坦區域，不存在角點；如果在某個方向上灰度發生了較大的變化而在另一些方向上灰度幾乎不變，認為窗口內是直線；如果沿各個方向移動，窗口區域內灰度發生了較大的變化，認為窗口內存在角點。

圖1 Harris角點窗口示意圖

將上述過程建立數學模型，對于二維圖像I(x,y)，當點在(x,y)處平移了(Δx,Δy)，用自相關函數表示窗口移動前后的相似度：

I(u+Δx,v+Δy))2

(1)

式中：W(x,y)是以(x,y)為中心的窗口；w(u,v)是窗口內的加權函數，一般為高斯函數。I(u+Δx,v+Δy)進行一階泰勒展開并忽略二階高次項：

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

(2)

式中：Ix(u,v)和Iy(u,v)為圖像的偏導數。將式(2)代入式(1)可得：

(3)

其中：

(4)

式中：矩陣M為圖像梯度的協方差矩陣；λ1和λ2為矩陣M的特征值。

Harris算法利用矩陣的跡tr(M)和行列式det(M)來定義角點響應函數R(x,y)，其表達式為：

R(x,y)=det(M)-k(Trace(M))2

(5)

式中：det(M)=λ1λ2；Trace(M)=λ1+λ2；k為經驗常數，k∈[0.04，0.06]。給定閾值T，當R(x,y)>T,并且在局部窗口內取得最大時，則該像素點(x,y)為特征點。

Shi-Tomasi算法的角點響應函數定義如下：

R(x,y)=min(λ1,λ2)

(6)

只需要找最小的特征值來獲取角點即可，其定義較Harris角點響應函數定義更為簡單，減少了角點響應函數的計算時間。

雖然Harris算法及其改進算法Shi-Tomasi都十分經典，但是它們都具有一些局限性：Shi-Tomasi算法只能在單一尺度下提取角點，角點響應函數的閾值的設定對角點提取影響較大，當閾值較大時，容易漏檢角點，當閾值較小時，又容易提取出偽角點。因此提取角點的準確度不高。

2 改進的Shi-Tomasi角點檢測算法

針對Shi-Tomasi角點在單一尺度下角點提取精度低、易提取偽角點、抗噪性差的問題，本文提出一種改進的Shi-Tomasi角點檢測方法，首先通過構建圖像金字塔使得算法可以在多尺度下提取角點，同時通過對每層圖像進行均值濾波對圖像去噪，提升抗噪性，利用雙模板組合的方式去除偽角點，進一步提升角點檢測的精度。

2.1 圖像金字塔構建

圖像金字塔的形式類似于金字塔，它指的是通過上采樣或下采樣的方式使同一幅圖像能夠擁有在不同尺度下的表達。上采樣是指通過對原始圖像在偶數行和列上進行插值并進行卷積運算平滑新增的像素，使圖片的尺寸越來越大，圖像的分辨率越來越高，上采樣方式構建的代表算法有拉普拉斯圖像金字塔算法。而下采樣則是朝著相反的方向，它指的是選擇原始圖像的偶數行和列的像素并刪除，這樣使得圖片尺寸越來越小，圖像的分辨率越來越低，下采樣方式構建的代表算法有高斯圖像金字塔算法。本文構建的圖像也采用下采樣的方式。

傳統的高斯圖像金字塔是由很多組金字塔構成，并且每組金字塔都包含若干層。從第i幅圖像到第i+1幅圖像需要進行的操作為：首先對第i幅圖像進行高斯內核卷積，達到平滑圖像的效果。其次去除圖像的偶數的行和列,縮減圖像的尺寸大小。兩個步驟循環反復，直到構建出完整高斯圖像金字塔。

通過構建多層圖像進行角點的提取，雖然實現了多尺度下的角點提取，但是此種方法計算量大，且容易提取出偽角點。因此，本文通過構建簡單的圖像金字塔(如圖2所示)來減少計算量，后續再通過雙模板組合的方式去除偽角點。本文只構建簡單的圖像金字塔，其算法大致步驟為：

(1) 將原始圖像進行均值濾波去除圖像中的椒鹽噪聲后作為第0層，并push到圖像數組中。

(2) 將第0層圖像按照設定的scale進行下采樣，獲得第1層圖像，并進行均值濾波去噪聲。

(3) 循環直至滿足設定的圖像金字塔的層數閾值。

(4) 遍歷所有層圖像，設定角點提取總數nfeatures，并按照1/scale的比例一次減少每層角點提取數量，從第0層到第nlevels-1層提取Shi-Tomasi角點，push到角點數組中。

圖2 圖像金字塔

本文構造的圖像金字塔較為簡單，不像傳統高斯圖像金字塔那樣，每一組有多層圖像，本文構建的圖像金字塔每一組只有1層圖像，既解決了尺度的問題。又通過縮小總圖像的數量，達到減少計算量的效果。并且在構建圖像金字塔的過程中，進行了多次均值濾波，達到去噪的效果。其流程如圖3所示。

圖3 圖像金字塔提取Shi-Tomasi角點流程

2.2 雙模板組合剔除偽角點

通過構建圖像金字塔雖然解決了尺度的問題，但是在這樣的情況下很容易提取偽角點，所以本文提出通過圖像金字塔提取的角點集作為候選點集，之后通過雙模板組合的方式進一步剔除偽角點，提高角點提取的準確度。該算法步驟為：

(1) 遍歷候選點集，對每一個候選點進行操作。

(2) 構建1個3×3的模板和一個4×4的模板(如圖4所示)，以候選角點為中心，其灰度表示為Ip_i-Ip_center，求出8鄰域內和24鄰域內的像素的灰度與候選角點的灰度差絕對值：|Ip_i-Ip_center|，首先將8領域內的像素差絕對值與設定閾值τ1進行比較，如果|Ip_i-Ip_center|小于閾值τ1，表示兩個像素灰度相似的個數nums1值加一，其次對4×4的模板也進行同樣的處理，將模板內鄰域像素點與中心點像素灰度進行比較，同理設置閾值τ2,如果滿足條件，則表示兩個像素灰度相似的個數nums2值加一。

(3) 如果nums1<2,認為該候選角點為噪聲點或孤立點。如果nums1>6,認為該候選角點與鄰域相似像素過多，認為是平坦區域。2

(4) 當nums1滿足條件時，進一步限制nums2的取值范圍，經過反復試驗，得出當nums2處于6至18的區域時能獲取較好的偽角點去除效果，選取此候選角點push到角點集中。

(a) 模板樣式 (b) 角點 (c) 角點 (d) 噪聲點 (e) Flat區域圖4 模板及角點判斷示例圖

通過雙模板組合的方式能夠對候選角點進行偽角點的剔除，實現進一步的精提取，提高角點檢測的準確性。

3 實驗結果與分析

3.1 多尺度實驗

本文提出通過構建圖像金字塔使得Shi-Tomasi角點提取算法具有尺度不變性的特點，我們在同一幅圖像的5個不同尺度下提取角點，設定提取角點數為100，實際角點提取情況如表1所示。

表1 不同尺度角點提取數

由表1可知，本文算法在5個不同尺度上按比例提取不同數量的角點，實現角點的粗提取。提取出的角點數量比原算法只能在單一尺度上提取的角點數量大，避免了在單一尺度下角點可能漏檢的情況。但是由于引入多尺度會提取出一些偽角點，后續通過雙模板組合的方式去除偽角點，實現精提取。

3.2 精確性

為了驗證本文提出的多尺度Shi-Tomasi角點提取算法提取角點的精確性，進行了與原Shi-Tomasi角點提取算法的對比實驗。首先，取兩個不同場景的圖像對本文算法不同階段提取角點情況進行對比說明，如圖5所示。

(a) 本文初步提取角點 (b) 本文最終提取角點圖5 本文算法不同階段角點提取情況

本文構建圖像金字塔實現在多尺度下提取角點，構成粗選點集。如圖5(a)所示。再通過雙模板組合的形式去除偽角點，實現精提取，如圖5(b)所示。

此外，將本文算法與原算法及文獻[2]算法進行對比，結果如圖6所示。表2為三種算法提取角點中偽角點個數的對比，從圖6和表2可以看出原算法和文獻[2]算法都會提取出很多偽角點，而本文提出的多尺度Shi-Tomasi角點提取算法能有效地去除偽角點，提升角點檢測的精確性。

(a) 本文算法 (b) 文獻[2]算法 (c) 原算法圖6 本文算法與原Shi-Tomasi角點提取算法對比圖

表2 兩種算法提取角點情況對比

3.3 抗噪性

除了上述兩個實驗外，本文還針對抗噪性這一指標進行了對比實驗，通過對圖像添加椒鹽噪聲，在此條件下對比兩種算法角點提取的情況，如圖7所示。

(a) 本文算法 (b) 文獻[2]算法 (c) 原算法圖7 噪聲條件下角點提取情況對比

可以看出，在添加噪聲后，原Shi-Tomasi角點提取算法和文獻[2]算法的準確性快速下降，將很多噪聲誤認為是角點提取出來；相對而言本文算法在噪聲條件下依然能有效提取出部分角點，且偽角點較少，說明了本文算法有一定的抗噪性。

4 結 語

本文基于原Shi-Tomasi角點不具備尺度不變性的特點，通過構建圖像金字塔實現Shi-Tomasi算法可在多尺度下提取角點，并通過構建雙模板組合的方式減少由引入多尺度帶來的偽角點，最后進行了對比實驗，表明本文算法增強了圖像的抗噪性以及提升了提取角點的精確性。