付永慶，宋寶森，吳建芳

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

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

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

1 標準SIFT算法

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

1.1 尺度空間極值點檢測

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

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

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

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

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

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

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

1.4 特征點描述子生成

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

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

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

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

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

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

2 改進SIFT算法

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

2.1 邊緣類提取

2.1.1 邊緣類的定義

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

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

2.1.2 局部幾何不變矩的計算

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

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)分別為圖像像素對應的紅、綠和藍色分量.

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

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

2.1.3 邊緣類的提取

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

求取梯度的公式為

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

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

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

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

2.2 邊緣類調(diào)整

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

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

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

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

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

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

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

2.3 改進SIFT算法實現(xiàn)

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

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

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

2)建立DOG圖像金字塔.

建立DOG金字塔時同標準SIFT算法相同.

3)極值點檢測.

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

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

3 改進前后SIFT算法仿真和實驗

為了比較改進SIFT算法和標準SIFT算法的運算速度及特征點冗余情況，組織了以下實驗驗證.

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

3.1 評價方法

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

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

3.2 實驗結(jié)果

3.2.1 運行時間和特征點數(shù)目對比

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

圖3 改進前后SIFT算法提取特征點對比Fig.3 Feature point contrast of EG-SIFT and SIFT

3.2.2 消除冗余特征點對比

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

圖4 改進前后SIFT特征點K-D樹匹配的特征點對比Fig.4 Counterpart points contrast of of EG-SIFT and SIFT

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

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

3.3 實驗結(jié)果分析

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

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

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

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

4 結(jié)論

本文提出的改進SIFT算法通過引入矩不變性，建立圖像邊緣類，可在2個方面相對標準SIFT算法獲得性能改善:

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

2)較大幅度地減少了冗余特征點，使匹配處理時間和計算復雜性大幅度下降.

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

后續(xù)研究將結(jié)合基于邊緣類和描述子2個方面作出進一步改進，以達到真正在實時場合應用的目的.

［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.