邊緣分類SIFT算法

付永慶，宋寶森，吳建芳

(1.哈爾濱工程大學(xué) 水下智能機(jī)器人技術(shù)國防科技重點(diǎn)實(shí)驗(yàn)室，黑龍江 哈爾濱 150001;2.哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001)

引局部特征提取方法作為圖像處理的關(guān)鍵技術(shù)，已被廣泛地研究［1-3］.在已提出的方法中，具有代表性的方法是 Harris角點(diǎn)檢測子［4］和 SIFT算法［5］.Harris角點(diǎn)檢測子以圖像中的拐角和梯度較大的區(qū)域作為特征，進(jìn)行圖像匹配，但是它對圖像尺度變化特別敏感［5］.為解決該問題，David Lowe在1999 年提出 SIFT［1］，并在 2004 年將其完善［5］.雖然SIFT解決了場景部分遮擋、旋轉(zhuǎn)縮放、視點(diǎn)變化引起的圖像變形等問題，但是它仍存在諸如閾值較多且不好確定、特征描述符維數(shù)過高導(dǎo)致計(jì)算過于復(fù)雜等問題，故使實(shí)時(shí)應(yīng)用受到限制.有學(xué)者優(yōu)化了特征描述子［1，6-9］，但也同樣忽視了對實(shí)時(shí)性的改進(jìn).

盡管SIFT算法已成功應(yīng)用在圖像全景拼接中［10］，但存在的主要問題是關(guān)鍵點(diǎn)具有很大的冗余性.根據(jù)Lowe的研究，將SIFT算法用于物體識別時(shí)，如果超過3個(gè)點(diǎn)能夠匹配，則可以確定圖像中存在目標(biāo)物體［1］.而在一幅512×512像素點(diǎn)的圖像中，SIFT可提供的關(guān)鍵點(diǎn)達(dá)1 000個(gè)左右，為了增強(qiáng)魯棒性，大部分的關(guān)鍵點(diǎn)需要被濾除，也就是真正對生成描述符產(chǎn)生貢獻(xiàn)的關(guān)鍵點(diǎn)僅為原有關(guān)鍵點(diǎn)的20%～50%，因此用于刪除冗余關(guān)鍵點(diǎn)所需的計(jì)算成為重要的運(yùn)算負(fù)荷.為了解決此問題，經(jīng)過研究，發(fā)現(xiàn)SIFT的特征點(diǎn)幾乎都在圖像的邊緣附近，基于此事實(shí)，改變了原有極值點(diǎn)的搜索方案.首先利用圖像的幾何不變矩［11］提取圖像的邊緣類，然后在邊緣類對應(yīng)的尺度空間中提取圖像的關(guān)鍵點(diǎn)，由于邊緣類已拋棄了生成絕大部分冗余關(guān)鍵點(diǎn)的圖像區(qū)域，因此得到的關(guān)鍵點(diǎn)既符合SIFT特征點(diǎn)分布在邊緣的特性，也極大提高了SIFT算法的運(yùn)算速度.

1 標(biāo)準(zhǔn)SIFT算法

SIFT算法是一種局部特征提取方法，其算法主要由4個(gè)步驟組成:1)檢測尺度空間極值點(diǎn)(以下稱關(guān)鍵點(diǎn));2)精確定位關(guān)鍵點(diǎn);3)為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù);4)生成特征點(diǎn)描述子.

1.1 尺度空間極值點(diǎn)檢測

生成尺度空間:標(biāo)準(zhǔn)SIFT使用DOG算子來近似尺度歸一化LOG算子，以生成尺度空間.尺度空間生成主要有2步:1)是構(gòu)建圖像金字塔，圖像金字塔共O組，每組有S+3層，下一組的圖像由上一組圖像降采樣得到，對每組的S+3幅圖像都要進(jìn)行高斯平滑;2)是由每組內(nèi)部相鄰圖像相減得到S+2幅差分圖像，O組全部完成相減后形成尺度空間.

極值點(diǎn)檢測:每一個(gè)采樣點(diǎn)要和它所有相鄰點(diǎn)比較，即要與其同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)做比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn).

1.2 精確定位關(guān)鍵點(diǎn)

為增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力，還需對關(guān)鍵點(diǎn)做以下3步處理:1)通過三維二次函數(shù)對像素插值以精確確定關(guān)鍵點(diǎn)的位置和尺度;2)利用門限(文獻(xiàn)［1］中取0.03)去除低對比度的關(guān)鍵點(diǎn);3)利用門限(文獻(xiàn)［1］中取10)去除不穩(wěn)定邊緣響應(yīng)的關(guān)鍵點(diǎn)(DOG算子會產(chǎn)生較強(qiáng)的邊緣響應(yīng)).

1.3 關(guān)鍵點(diǎn)方向分配

利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù).即在以關(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向(梯度直方圖的范圍是0～360°，其中每10°一個(gè)柱，共36個(gè)柱)，直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向.

至此，圖像的關(guān)鍵點(diǎn)已檢測完畢，每個(gè)關(guān)鍵點(diǎn)有3個(gè)信息:位置、尺度、方向.

1.4 特征點(diǎn)描述子生成

利用鄰域方向性信息聯(lián)合的思想來構(gòu)造特征描述子.即以關(guān)鍵點(diǎn)為中心取16×16的窗口，形成4×4個(gè)種子點(diǎn)，每個(gè)種子點(diǎn)對應(yīng)一個(gè)4×4像素的區(qū)域，在該區(qū)域內(nèi)分別計(jì)算8個(gè)方向的梯度累加值，繪制各梯度方向的方向直方圖.最終由16個(gè)種子點(diǎn)可獲得一個(gè)128維的特征描述子.

根據(jù)文獻(xiàn)［5-7，9］介紹，SIFT 特征有以下特點(diǎn):

1)對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性.

2)獨(dú)特性好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進(jìn)行準(zhǔn)確的匹配.

3)具有可擴(kuò)展性，方便與其他形式的特征向量聯(lián)合.

4)多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量SIFT特征向量.因此用于全景拼接時(shí)，計(jì)算復(fù)雜度增加，計(jì)算效率下降.

2 改進(jìn)SIFT算法

標(biāo)準(zhǔn)SIFT算法是把整個(gè)尺度空間搜索到的極值點(diǎn)都作為關(guān)鍵點(diǎn)，故產(chǎn)生冗余是很自然的事.為降低無效的計(jì)算負(fù)荷，提出一種關(guān)鍵點(diǎn)定位策略，它不是在整個(gè)尺度空間中尋找極值點(diǎn)，而是首先利用幾何不變矩來提取圖像的邊緣類，然后在邊緣類對應(yīng)的尺度空間中搜索極值點(diǎn)，搜索完畢后的處理仍沿用SIFT方法，故稱之為改進(jìn)SIFT算法(EG-SIFT).

2.1 邊緣類提取

2.1.1 邊緣類的定義

邊緣類定義為包含圖像邊緣信息區(qū)域的集合.一個(gè)說明實(shí)例如圖1中斜線部分所示.

圖1 圖像邊緣類Fig.1 Edge group of image

2.1.2 局部幾何不變矩的計(jì)算

考慮到SIFT算法不便處理彩色圖像的情況，同時(shí)也為降低計(jì)算的復(fù)雜度，提取彩色圖像的亮度信息作為計(jì)算圖像局部幾何矩的灰度值，計(jì)算公式為

g(i，j)=0.3R(i，j)+0.59G(i，j)+0.11B(i，j).(1)式中:R(i，j)、G(i，j)、B(i，j)分別為圖像像素對應(yīng)的紅、綠和藍(lán)色分量.

為計(jì)算圖像的局部幾何不變矩，將寬度和高度為m×n(m，n應(yīng)為2的整數(shù)倍)的圖像分割成N×N(N應(yīng)為2的整數(shù)倍)的子塊.為使圖像子塊的矩具有平移、旋轉(zhuǎn)和尺度不變性，本文引用HU提出的第1 個(gè)不變矩［11］，其定義如下:

式中:l∈(0，m/N)和 k∈(0，n/N)為圖像子塊的索引值;為圖像的中心矩，定義為式中:為圖像矩心的模擬坐標(biāo)位置;g(i，j)為像素灰度值，p+q 為矩的階數(shù)，mpq為圖像的幾何矩，定義為

2.1.3 邊緣類的提取

邊緣類提取的思想，是將相鄰矩值跳躍較大的局部不變矩對應(yīng)的圖像子塊作為圖像的邊緣類，即把圖像子塊看作像素，把圖像的幾何不變矩看作像素的灰度值，取梯度后對小于門限部分歸零處理，大于門限部分對應(yīng)的圖像子塊的集合經(jīng)過調(diào)整后作為圖像的邊緣類.

求取梯度的公式為

求得梯度后做歸零處理的公式為

式中:T為門限值，不為零的F(l，k)所對應(yīng)的圖像子塊為圖像邊緣類的侯選區(qū)域.為了能相對精確地提取邊緣類，還要對侯選區(qū)域進(jìn)行調(diào)整.

門限T的選取對于邊緣類的提取是一個(gè)很關(guān)鍵的因素.在實(shí)驗(yàn)中，如果對于所有梯度值采用同一個(gè)固定的門限T，則T大時(shí)會遺漏部分邊緣區(qū)域，而T小時(shí)會出現(xiàn)虛假邊緣區(qū)域.為了取得折中值，可依下式選擇門限T:

整幅圖像局部亮度值可能不在一個(gè)數(shù)量級上，故采用固定門限不可能同時(shí)區(qū)分出不同數(shù)量級的亮度跳躍.根據(jù)局部亮度信息確定門限，可區(qū)分不同數(shù)量級的亮度跳躍.

2.2 邊緣類調(diào)整

在分割圖像的時(shí)候，邊緣區(qū)域的圖像子塊并不是全部正好跨在圖像的邊緣線上，而是大部分子塊都偏移，甚至有的正好以圖像邊緣線作為分割線，如圖2所示(網(wǎng)格線為分割線).如果這樣的子塊作為圖像的邊緣類區(qū)域，則會大大降低邊緣類包含的邊緣信息.所以要對梯度處理后保留的子塊進(jìn)行調(diào)整，使其盡量正好跨在圖像的邊緣線上，這樣才能保證邊緣類中包含大部分的邊緣信息.

調(diào)整Fl，k的起始坐標(biāo)，并使用下式作為停止條件:

不等式右端是一個(gè)可變的門限，選取方法和選擇梯度門限是一樣的.

圖2 圖像子塊分割Fig.2 Sub block of image

調(diào)整后，根據(jù)圖像子塊幾何不變矩來構(gòu)造一個(gè)新的參考圖像，其像素值由下式確定:

式中:fl，k(x，y)為第l列k行的圖像子塊內(nèi)的各個(gè)像素值，x和y在一個(gè)圖像子塊內(nèi)(N×N)取值.

經(jīng)過以上兩步驟，提取的圖像邊緣類為參考圖像中不為零的區(qū)域，極值點(diǎn)的檢測將在原圖像相應(yīng)區(qū)域中進(jìn)行.搜索完畢極值點(diǎn)的后續(xù)處理過程與SIFT相同.

2.3 改進(jìn)SIFT算法實(shí)現(xiàn)

1)提取邊緣類并建立參考圖象金字塔.

對圖像進(jìn)行子塊分割，計(jì)算子塊幾何不變矩的梯度，用梯度超過門限的圖像子塊創(chuàng)建一幅新的邊緣類參考圖像.

將邊緣類參考圖像依次降采樣，取得O幅參考圖像，分別與DOG圖像金字塔的O組相對應(yīng).即DOG圖像金字塔的每組S+2幅圖像使用同一幅參考圖像.

2)建立DOG圖像金字塔.

建立DOG金字塔時(shí)同標(biāo)準(zhǔn)SIFT算法相同.

3)極值點(diǎn)檢測.

搜索極值點(diǎn)時(shí)，首先看當(dāng)前像素對應(yīng)組參考圖像中的對應(yīng)像素是否為零，如果為零則轉(zhuǎn)向下一個(gè)像素，不為零則繼續(xù)與相鄰的26個(gè)像素做比較，判斷當(dāng)前點(diǎn)是否為極值點(diǎn).

找出所有極值點(diǎn)后的處理同SIFT算法，經(jīng)過“精確定位關(guān)鍵點(diǎn)”、“關(guān)鍵點(diǎn)方向分配”和“特征點(diǎn)描述子生成”等步驟最后形成一定數(shù)量的特征點(diǎn).顯然，本文提出的改進(jìn)SIFT算法比標(biāo)準(zhǔn)SIFT算法節(jié)省了在所有尺度空間檢測極值點(diǎn)的時(shí)間，同時(shí)通過改變圖像子塊大小(N×N)，可不同程度地減少特征點(diǎn)冗余.

3 改進(jìn)前后SIFT算法仿真和實(shí)驗(yàn)

為了比較改進(jìn)SIFT算法和標(biāo)準(zhǔn)SIFT算法的運(yùn)算速度及特征點(diǎn)冗余情況，組織了以下實(shí)驗(yàn)驗(yàn)證.

實(shí)驗(yàn)用計(jì)算機(jī)配置為:主頻 1.8 GHz，內(nèi)存1GByte;仿真軟件為 Microsoft visual C++6.0;利用的函數(shù)庫為OpenCV.

3.1 評價(jià)方法

為了對比改進(jìn)前后SIFT算法運(yùn)行時(shí)間的差異，分別對同一張圖片進(jìn)行特征點(diǎn)提取，用微秒級Windows API函數(shù)記錄其各自的運(yùn)行時(shí)間，并記錄各自特征點(diǎn)個(gè)數(shù)然后進(jìn)行顯示.為客觀評價(jià)改進(jìn)SIFT算法在圖像拼接中消除特征點(diǎn)冗余的性能，利用K-D樹搜索近似最近鄰的方法對兩幅有重疊圖中的對應(yīng)特征點(diǎn)進(jìn)行匹配，并記錄改進(jìn)前后特征點(diǎn)匹配對數(shù).

針對圖像全景拼接應(yīng)用，給出了圖像子塊大小對SIFT特征點(diǎn)數(shù)目的影響曲線.

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 運(yùn)行時(shí)間和特征點(diǎn)數(shù)目對比

對440×340像素點(diǎn)的彩色圖像用SIFT法提取的特征點(diǎn)如圖3(a)所示(黑色箭頭線起點(diǎn)是特征點(diǎn)位置，長度代表方向模值).提取特征點(diǎn)315個(gè)，花費(fèi)時(shí)間1 173 ms，其中建立DOG圖像金字塔時(shí)間為357 ms.用改進(jìn)SIFT法提取的特征點(diǎn)如圖3(b)所示，采用的圖像子塊為14×14像素點(diǎn)，提取特征點(diǎn)173個(gè)，花費(fèi)時(shí)間817 ms，其中提取邊緣類、建立邊緣類參考圖像金字塔為27 ms，建立DOG圖像金字塔為357 ms.

圖3 改進(jìn)前后SIFT算法提取特征點(diǎn)對比Fig.3 Feature point contrast of EG-SIFT and SIFT

3.2.2 消除冗余特征點(diǎn)對比

利用K-D樹搜索近似最近鄰法對兩幅有重疊圖像進(jìn)行了特征點(diǎn)匹配，如圖4所示，(a)為標(biāo)準(zhǔn)SIFT算法提取的特征點(diǎn)經(jīng)過匹配后的圖像，其中黑色線連接的是兩幅圖像中相對應(yīng)的特征點(diǎn)，經(jīng)過匹配后，找到41對匹配點(diǎn);圖4(b)為改進(jìn)SIFT算法提取的特征點(diǎn)經(jīng)過匹配后的圖像，找到12對匹配點(diǎn).

圖4 改進(jìn)前后SIFT特征點(diǎn)K-D樹匹配的特征點(diǎn)對比Fig.4 Counterpart points contrast of of EG-SIFT and SIFT

3.2.3 圖像子塊大小和特征點(diǎn)數(shù)目曲線

使用圖3的原圖像，并從6×6到20×20更改圖像子塊的大小，記錄提取出的特征點(diǎn)數(shù)，結(jié)果曲線如圖5所示.

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

由圖3可見，改進(jìn)SIFT的特征點(diǎn)要明顯少于標(biāo)準(zhǔn)SIFT的特征點(diǎn)，由315降至173，SIFT改進(jìn)前后耗時(shí)由1 173 ms降至817 ms，節(jié)省了總運(yùn)行時(shí)間的30.3%.通過對描述子生成過程的跟蹤，發(fā)現(xiàn)生成每個(gè)描述子的時(shí)間約為 2.6 ms，173個(gè)特征點(diǎn)需450 ms，加上DOG金字塔生成時(shí)間357 ms和邊緣類參考圖像生成時(shí)間27 ms，理論上耗時(shí)834 ms而實(shí)際為817 ms，節(jié)省的17 ms為在搜索關(guān)鍵點(diǎn)時(shí)直接拋棄不屬于邊緣類的點(diǎn)所得.

圖5 圖像子塊大小和特征點(diǎn)數(shù)目關(guān)系曲線Fig.5 Relation of sub-block and feature points

由圖4可見SIFT匹配對由改進(jìn)前41對下降到12對，冗余度大大降低.根據(jù)文獻(xiàn)［3］知，3對正確的匹配對可以完成幾何關(guān)系校正矩陣參數(shù)的求解，而7對以上就可以更好的求解各參數(shù).現(xiàn)在改進(jìn)SIFT算法有至少12對可利用，完全可以實(shí)現(xiàn)圖像拼接過程中的幾何關(guān)系校正，且使計(jì)算復(fù)雜度和計(jì)算時(shí)間大幅度降低.

從圖5可見，子塊從6×6到18×18的時(shí)候，特征點(diǎn)的數(shù)目會少量增加，而到20×20以后呈少量下降趨勢，主要是因?yàn)樵?8×18以下時(shí)，邊緣類提取算法可以很好的提取邊緣信息區(qū)域，而當(dāng)子塊為20×20以上時(shí)，不能正確提取邊緣類造成邊緣信息丟失，從而特征點(diǎn)數(shù)目會下降一些.通過實(shí)驗(yàn)，推薦子塊大小在8×8到14×14之間選擇.該實(shí)驗(yàn)中選擇的子塊是14×14.

4 結(jié)論

本文提出的改進(jìn)SIFT算法通過引入矩不變性，建立圖像邊緣類，可在2個(gè)方面相對標(biāo)準(zhǔn)SIFT算法獲得性能改善:

1)縮小了極值點(diǎn)的搜索范圍，大幅度提高了SIFT算法極值點(diǎn)搜索速度.

2)較大幅度地減少了冗余特征點(diǎn)，使匹配處理時(shí)間和計(jì)算復(fù)雜性大幅度下降.

3)由于改進(jìn)算法是基于邊緣信息的，所以其適用于邊緣信息相對豐富的圖像.

后續(xù)研究將結(jié)合基于邊緣類和描述子2個(gè)方面作出進(jìn)一步改進(jìn)，以達(dá)到真正在實(shí)時(shí)場合應(yīng)用的目的.

［1］LOWE D G.Object recognition from local scale-invariant features［C］//Proceedings of the International Conference on Computer Vision.Corfu，Greece，1999:1150-1157.

［2］MIKOLAJCZYK K，SCHMID C.Scale and affine invariant interest point detectors［J］.Int＇l J Computer Vision，2004，1(60):63-86.

［3］GOOL L V，MOONS T，UNGUREANU D.Affine/photometric invariants for planar intensity patterns［C］//Proc.Fourth European Conf Computer Vision，Cambridge，England.1996:642-651.

［4］HARRIES C，STEPHENS M.A combined corner and edge detector［C］//Fourth Alvey Vision Conference.Manchester，UK，1988:147-151.

［5］LOWE D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.

［6］KE Y，SUKTHANKAR R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//Proc Conf Computer Vision and Pattern Recognition.Washington D.C.，USA，2004:511-517.

［7］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis And Machine Intelligence，2005(10):1615-1630.

［8］MORENO P，BERNARDINO A.Improving the SIFT descriptor with smooth derivative filters［J］.Pattern Recognition Letters，2009，30(1):18-26.

［9］ZHOU H Y，YUAN Y，SHI C M.Object tracking using SIFT features and mean shift［J］.Computer Vision and Image Understanding，2009，113(3):345-352.

［10］BROWN M，LOWE D.Recognising panoramas［C］//Proc Ninth Int＇l Conf Computer Vision.Washington D.C.，USA，2003:1218-1227.

［11］HU M K.Visual pattern recognition by moment invariants［J］.IRE Trans Inf Theory，1962，8(2):179-187.