一種改進(jìn)的Shi-Tomasi角點(diǎn)檢測(cè)方法

彭曉星 羅 霄 韓寶玲

1(北京理工大學(xué)光電學(xué)院 北京 100081) 2(北京理工大學(xué)計(jì)算機(jī)學(xué)院 北京 100081) 3(北京理工大學(xué)機(jī)械與車(chē)輛學(xué)院 北京 100081)

0 引 言

為了從圖像中獲取我們感興趣的信息，我們通常通過(guò)提取圖像特征的方式來(lái)實(shí)現(xiàn)。點(diǎn)特征作為圖像特征的其中一種，它保留了圖像中物體的重要特征信息并且具有表征圖像特征準(zhǔn)確、穩(wěn)定可靠的特點(diǎn)[1]。角點(diǎn)檢測(cè)算法廣泛應(yīng)用在圖像匹配、運(yùn)動(dòng)估計(jì)、相機(jī)標(biāo)定與視覺(jué)定位等方面[2]。

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

1 Shi-Tomasi角點(diǎn)檢測(cè)算法原理及其局限性

1993年Shi等在Harris算法的基礎(chǔ)上提出Shi-Tomasi角點(diǎn)檢測(cè)算法，他們發(fā)現(xiàn)使用Harris角點(diǎn)檢測(cè)算法中自相關(guān)矩陣較小的特征值即可很好地表示角點(diǎn)。因此定義了更為簡(jiǎn)單的角點(diǎn)響應(yīng)函數(shù)。Shi-Tomasi算法的主體與Harris算法一致，首先來(lái)看Harris算法，Harris算法角點(diǎn)的原理是計(jì)算窗口內(nèi)點(diǎn)的灰度變化來(lái)檢測(cè)角點(diǎn)。如圖1所示，朝各個(gè)方向移動(dòng)固定大小窗口，如果窗口內(nèi)的灰度幾乎不變，認(rèn)為是平坦區(qū)域，不存在角點(diǎn)；如果在某個(gè)方向上灰度發(fā)生了較大的變化而在另一些方向上灰度幾乎不變，認(rèn)為窗口內(nèi)是直線；如果沿各個(gè)方向移動(dòng)，窗口區(qū)域內(nèi)灰度發(fā)生了較大的變化，認(rèn)為窗口內(nèi)存在角點(diǎn)。

圖1 Harris角點(diǎn)窗口示意圖

將上述過(guò)程建立數(shù)學(xué)模型，對(duì)于二維圖像I(x,y)，當(dāng)點(diǎn)在(x,y)處平移了(Δx,Δy)，用自相關(guān)函數(shù)表示窗口移動(dòng)前后的相似度：

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

(1)

式中：W(x,y)是以(x,y)為中心的窗口；w(u,v)是窗口內(nèi)的加權(quán)函數(shù)，一般為高斯函數(shù)。I(u+Δx,v+Δy)進(jìn)行一階泰勒展開(kāi)并忽略二階高次項(xiàng)：

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

(2)

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

(3)

其中：

(4)

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

Harris算法利用矩陣的跡tr(M)和行列式det(M)來(lái)定義角點(diǎn)響應(yīng)函數(shù)R(x,y)，其表達(dá)式為：

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

(5)

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

Shi-Tomasi算法的角點(diǎn)響應(yīng)函數(shù)定義如下：

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

(6)

只需要找最小的特征值來(lái)獲取角點(diǎn)即可，其定義較Harris角點(diǎn)響應(yīng)函數(shù)定義更為簡(jiǎn)單，減少了角點(diǎn)響應(yīng)函數(shù)的計(jì)算時(shí)間。

雖然Harris算法及其改進(jìn)算法Shi-Tomasi都十分經(jīng)典，但是它們都具有一些局限性：Shi-Tomasi算法只能在單一尺度下提取角點(diǎn)，角點(diǎn)響應(yīng)函數(shù)的閾值的設(shè)定對(duì)角點(diǎn)提取影響較大，當(dāng)閾值較大時(shí)，容易漏檢角點(diǎn)，當(dāng)閾值較小時(shí)，又容易提取出偽角點(diǎn)。因此提取角點(diǎn)的準(zhǔn)確度不高。

2 改進(jìn)的Shi-Tomasi角點(diǎn)檢測(cè)算法

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

2.1 圖像金字塔構(gòu)建

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

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

通過(guò)構(gòu)建多層圖像進(jìn)行角點(diǎn)的提取，雖然實(shí)現(xiàn)了多尺度下的角點(diǎn)提取，但是此種方法計(jì)算量大，且容易提取出偽角點(diǎn)。因此，本文通過(guò)構(gòu)建簡(jiǎn)單的圖像金字塔(如圖2所示)來(lái)減少計(jì)算量，后續(xù)再通過(guò)雙模板組合的方式去除偽角點(diǎn)。本文只構(gòu)建簡(jiǎn)單的圖像金字塔，其算法大致步驟為：

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

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

(3) 循環(huán)直至滿(mǎn)足設(shè)定的圖像金字塔的層數(shù)閾值。

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

圖2 圖像金字塔

本文構(gòu)造的圖像金字塔較為簡(jiǎn)單，不像傳統(tǒng)高斯圖像金字塔那樣，每一組有多層圖像，本文構(gòu)建的圖像金字塔每一組只有1層圖像，既解決了尺度的問(wèn)題。又通過(guò)縮小總圖像的數(shù)量，達(dá)到減少計(jì)算量的效果。并且在構(gòu)建圖像金字塔的過(guò)程中，進(jìn)行了多次均值濾波，達(dá)到去噪的效果。其流程如圖3所示。

圖3 圖像金字塔提取Shi-Tomasi角點(diǎn)流程

2.2 雙模板組合剔除偽角點(diǎn)

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

(1) 遍歷候選點(diǎn)集，對(duì)每一個(gè)候選點(diǎn)進(jìn)行操作。

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

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

(4) 當(dāng)nums1滿(mǎn)足條件時(shí)，進(jìn)一步限制nums2的取值范圍，經(jīng)過(guò)反復(fù)試驗(yàn)，得出當(dāng)nums2處于6至18的區(qū)域時(shí)能獲取較好的偽角點(diǎn)去除效果，選取此候選角點(diǎn)push到角點(diǎn)集中。

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

通過(guò)雙模板組合的方式能夠?qū)蜻x角點(diǎn)進(jìn)行偽角點(diǎn)的剔除，實(shí)現(xiàn)進(jìn)一步的精提取，提高角點(diǎn)檢測(cè)的準(zhǔn)確性。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 多尺度實(shí)驗(yàn)

本文提出通過(guò)構(gòu)建圖像金字塔使得Shi-Tomasi角點(diǎn)提取算法具有尺度不變性的特點(diǎn)，我們?cè)谕环鶊D像的5個(gè)不同尺度下提取角點(diǎn)，設(shè)定提取角點(diǎn)數(shù)為100，實(shí)際角點(diǎn)提取情況如表1所示。

表1 不同尺度角點(diǎn)提取數(shù)

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

3.2 精確性

為了驗(yàn)證本文提出的多尺度Shi-Tomasi角點(diǎn)提取算法提取角點(diǎn)的精確性，進(jìn)行了與原Shi-Tomasi角點(diǎn)提取算法的對(duì)比實(shí)驗(yàn)。首先，取兩個(gè)不同場(chǎng)景的圖像對(duì)本文算法不同階段提取角點(diǎn)情況進(jìn)行對(duì)比說(shuō)明，如圖5所示。

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

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

此外，將本文算法與原算法及文獻(xiàn)[2]算法進(jìn)行對(duì)比，結(jié)果如圖6所示。表2為三種算法提取角點(diǎn)中偽角點(diǎn)個(gè)數(shù)的對(duì)比，從圖6和表2可以看出原算法和文獻(xiàn)[2]算法都會(huì)提取出很多偽角點(diǎn)，而本文提出的多尺度Shi-Tomasi角點(diǎn)提取算法能有效地去除偽角點(diǎn)，提升角點(diǎn)檢測(cè)的精確性。

(a) 本文算法 (b) 文獻(xiàn)[2]算法 (c) 原算法圖6 本文算法與原Shi-Tomasi角點(diǎn)提取算法對(duì)比圖

表2 兩種算法提取角點(diǎn)情況對(duì)比

3.3 抗噪性

除了上述兩個(gè)實(shí)驗(yàn)外，本文還針對(duì)抗噪性這一指標(biāo)進(jìn)行了對(duì)比實(shí)驗(yàn)，通過(guò)對(duì)圖像添加椒鹽噪聲，在此條件下對(duì)比兩種算法角點(diǎn)提取的情況，如圖7所示。

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

可以看出，在添加噪聲后，原Shi-Tomasi角點(diǎn)提取算法和文獻(xiàn)[2]算法的準(zhǔn)確性快速下降，將很多噪聲誤認(rèn)為是角點(diǎn)提取出來(lái)；相對(duì)而言本文算法在噪聲條件下依然能有效提取出部分角點(diǎn)，且偽角點(diǎn)較少，說(shuō)明了本文算法有一定的抗噪性。

4 結(jié) 語(yǔ)

本文基于原Shi-Tomasi角點(diǎn)不具備尺度不變性的特點(diǎn)，通過(guò)構(gòu)建圖像金字塔實(shí)現(xiàn)Shi-Tomasi算法可在多尺度下提取角點(diǎn)，并通過(guò)構(gòu)建雙模板組合的方式減少由引入多尺度帶來(lái)的偽角點(diǎn)，最后進(jìn)行了對(duì)比實(shí)驗(yàn)，表明本文算法增強(qiáng)了圖像的抗噪性以及提升了提取角點(diǎn)的精確性。