基于SIFT與K-means聚類的多源圖像匹配算法

文永革

(綿陽師范學(xué)院信息工程學(xué)院，四川綿陽 621000)

0 引言

數(shù)字圖像匹配是計算機圖像信息處理領(lǐng)域的重要技術(shù)，在多源圖像的3D重構(gòu)、立體匹配和運動跟蹤等應(yīng)用領(lǐng)域中得到廣泛深入的研究.目前，基于圖像特征的匹配方法仍是計算機視覺及相關(guān)領(lǐng)域的研究熱點，重心在對圖像中點、線、區(qū)域等圖像顯著特征的提取，獲得圖像間較高的匹配度[1].近年來，業(yè)界對圖像的局部特征描述符進行了大量的研究，其中，加拿大教授Lowe提出的SIFT局部特征提取算法[2]得到了業(yè)界重點關(guān)注，通過構(gòu)建128維特征描述子，和多次迭代運算提取圖像特征點，雖然SIFT算法已廣泛應(yīng)用在多個領(lǐng)域，但其計算量大、效率不高，文獻[3]對SIFT描述子作了一定的改進，降低了特征向量的維數(shù)，使得算法的復(fù)雜度得到了降低，文獻[4]提出一種基于分塊匹配的新型SIFT匹配算法，核心在于對圖像塊的切分和重疊區(qū)域的計算，通過剔除非重疊區(qū)域來降低特征提取和匹配的時間損耗，文獻[5]提出了一種基于 RANSAC的SIFT匹配優(yōu)化，采用加權(quán)的圓形鄰域替代原有 SIFT 描述子矩形鄰域，并以最優(yōu)匹配點作為RANSAC 算法初始樣本數(shù)據(jù)集，進一步提純特征點，文獻[6]提出了一種基于SIFT、K-Means 和LDA的圖像檢索算法，對圖像庫中圖片按其本身特征進行自動分類，有效提高圖像檢索效率.針對計算效率，文獻[7]采用CPU與GPU協(xié)同方式對SIFT算法進行加速，但是由于較大圖像在GPU內(nèi)存中的傳輸速度的限制，算法對于較大圖像的計算速度提升并沒有得到理想的效果.本文在SIFT算法的基礎(chǔ)上結(jié)合了K-means聚類算法，通過亞像素插值提升特征點坐標(biāo)精確度，在此基礎(chǔ)上設(shè)計輻射模型排除強噪聲等不良點以獲得穩(wěn)定的聚類中心，對特征點的選取與匹配進行了進一步優(yōu)化，又保持了SIFT良好的旋轉(zhuǎn)不變性與尺度不變性， 通過實驗仿真，本文算法對不同分辨率、不同尺度圖像的匹配精度有較穩(wěn)定的提升.

1 SIFT 算法

灰度圖像中像素點的灰度分布特征與二維高斯模型相似，中心處最亮，離中心越遠亮度隨之降低，因此本文中的圖像灰度分布特征，用優(yōu)化的高斯模型代之描述.SIFT算法正是通過用不同尺度的高斯函數(shù)對圖像進行平滑處理，比較平滑后圖像的差別，差別大的像素就是局部范圍內(nèi)的極值點，根據(jù)這些點的鄰域采樣求得特征向量，提取這些點的位置、尺度、旋轉(zhuǎn)不變量.SIFT算法對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性[2]，經(jīng)優(yōu)化的匹配算法適用于海量特征數(shù)據(jù)快速、準(zhǔn)確的匹配，還可以滿足一定程度的實時性要求.

1.1 SIFT 特征檢測

(1) 尺度空間極值檢測

差分尺度空間的極植點檢測是通過高斯核與圖像的卷積運算實現(xiàn).圖像的尺度空間函數(shù)用L(x,y,σ)表示，通過尺度變化的高斯函數(shù)G與數(shù)字圖像I卷積運算，搜索所有尺度上的特征圖像位置，因此，一幅二維圖像的尺度空間可表示為：

L(x,y,σ)=I(x,y)?G(x,y,σ)

(1)

式中(x,y)代表像素點的空間坐標(biāo)，σ代表采用的尺度參數(shù)，σ的大小決定圖像的平滑程度，值越大對應(yīng)圖像的粗糙特征，越小對應(yīng)圖像的細節(jié)特征.

SIFT算法圖像空間中特征點的檢測，通過兩個相鄰高斯尺度空間的圖像相減得到高斯差分DoG[8]的響應(yīng)值圖像D(x,y,σ)，其響應(yīng)值圖像表達式如下：

D(x,y,σ)=I(x,y)?(G(x,y,kσ)-G(x,y,σ))

(2)

k為兩相鄰尺度空間倍數(shù)的常數(shù).

(2) 特征點的定位

圖1 相鄰尺度空間極值點比較示意圖Fig.1 Comparison of Extremum Points in Adjacent Scale Spaces

圖像特征點的定位是通過對圖像D(x,y,σ)進行局部極值搜索來實現(xiàn)，在位置空間和尺度空間中定位特征點.如下圖所示，為了實現(xiàn)查找尺度空間的極值點，需要每一個采樣點與它同尺度8個相鄰點和兩相鄰尺度空間的18個相鄰點進行大小比較，如一個點在上述空間是最大或最小值，則認(rèn)為該點是圖像在該尺度的一個特征點，移動滑動模板，直到完成對尺度空間中每個像素的最大最小值比較.

(3)特征點的方向

計算特征點幅值大小，并根據(jù)極值點鄰域像素的梯度方向分布特性，為每個極值點指定方向參數(shù)，使算子具備尺度和旋轉(zhuǎn)不變性.

(3)

(4)

a(x,y)為極值點處梯度的模值，θ(x,y)為此特征點的梯度方向，L為(x,y)點所在的尺度.在此，圖像的關(guān)鍵點已檢測結(jié)束，且其位置、方向、尺度三個特征值已確定.

(4)特征點的描述

通過以上步驟，每個特征點都具有位置、尺度和方向三種屬性，將特征點相鄰點分成4×4個子區(qū)域，每個子區(qū)域包含一個種子點，每個種子點通過高斯加權(quán)后以45°角為度確定8個梯度方向，箭頭的方向代表了特征點梯度方向，箭頭長度代表該點的幅值大小，用一組向量來描述，該描述子使用128維信息來表達尺度空間的SIFT特征向量.

2 K-means聚類算法

針對SIFT特征點優(yōu)化問題，根據(jù)關(guān)鍵點特征向量的歐式距離，運用K-means聚類算法對SIFT特征向量進行聚類，選取與整體差異最小的特征向量作為初始聚類中心，據(jù)此實現(xiàn)特征向量匹配可大大降低計算維度.

2.1 K-means 算法

是一種迭代聚類算法，其算法思想是對大量樣本數(shù)據(jù)進行撫今迭代計算，按樣本間的歐式距離大小歸類成k個簇，每個簇內(nèi)數(shù)據(jù)間聚集更緊，簇間的距離盡量變大.算法快速、簡單, 其時間復(fù)雜度O(ntk)近于線性，正比于數(shù)據(jù)集中對象的數(shù)量n、算法迭代的次數(shù)t和簇的數(shù)目k，對于處理大數(shù)據(jù)集計算有較高的效率.

2.2 K-MEANS 算法基本流程

(1)從n個數(shù)據(jù)對象S=x1,x2,x3…xn，任意選擇k個對象μ1, μ2…μk作為初始聚類中心；

(2)算法采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)，根據(jù)每個聚類對象的均值求得中心對象，計算每個對象與所有中心對象的距離；并根據(jù)最小距離將相應(yīng)對象歸入距離最近的中心對象的類中.

(5)

(3)重新計算每個聚類Cj的均值uj，確定該聚類的中心對象；

(6)

(4)重復(fù)(2)(3)步直到每個聚類中心變化小于閾值為止.

3 SIFT 特征點優(yōu)化和輻射聚類模型

SIFT特征點初步定位的坐標(biāo)值一般采用整數(shù)值，并非特征點精確坐標(biāo)，這在相機標(biāo)定、圖像匹配、圖像融合以及三維重構(gòu)等應(yīng)用中，計算圖像間距離和像素距聚類中心距離時會產(chǎn)生較大誤差，導(dǎo)致聚類中心不穩(wěn)定和局部優(yōu)化.為了進一步減小圖像特征點計算、匹配時的誤差，文中采用亞像素插值算法對特征點進行精確定位，采用優(yōu)化輻射模型進一步排出噪聲等異常點的影響，提高中心精確度和減小計算量.

圖2 離散空間和連續(xù)空間的極值點Fig.2 Extremum Points of Discrete Space and Continuous Space

3.1 亞像素插值法sub-pixel interpolation(特征點的精確定位)

傳統(tǒng)SIFT算法結(jié)合Harris角點算法對特征點進行篩選，對篩選結(jié)果中的不良點排除未達最優(yōu)化，其特征點結(jié)果可能是離散空間中的局部極值點，如不能正確排除，特征點的選擇誤差會嚴(yán)重影響后續(xù)聚類中心的計算和特征點的匹配[9].為了進一步準(zhǔn)確定位sift特征點，在前期研究基礎(chǔ)上，本文對離散空間的極值點進行三維亞像素插值，以提高圖像分辨率以彌補成像設(shè)備不足，得到連續(xù)空間中更準(zhǔn)確的極值點的位置，如圖2所示.

對式(2)有，根據(jù)泰勒展開式有：

(7)

式中D(X)即為D(x,y,σ)，X=(x,y,σ)T.

(8)

圖3 輻射模型示意圖Fig.3 Diagram of Radiation Model

4.2 輻射模型分析

文中采用Euclidean度量方法計算空間像素點距離，算法要求每一個數(shù)據(jù)點參與均值計算，故均值的計算結(jié)果對噪聲和孤立點較為敏感，少量的異常點會對平均值產(chǎn)生較大的影響，導(dǎo)致聚類中心的計算出現(xiàn)較大誤差.本文在反復(fù)實踐的基礎(chǔ)上提出了一種搜尋聚類對象的輻射模型，從聚類中心以不同步長向外輻射，找到輻射范圍內(nèi)特征相近的點，直到聚類的最外環(huán)相切，這類特征點在更大程度上具有內(nèi)容關(guān)聯(lián)性[10]，對于其余未歸并入某一聚類的特征點，再根據(jù)其距聚類中心的距離遠近歸并到相應(yīng)聚類中.在程序?qū)崿F(xiàn)中定義了輻射步長：radioStep=meanRange*radio*step，通過逐次調(diào)整不同的step步長來限制輻射的精度，調(diào)整篩選的粒度，其中步長step代表兩個圓的徑向長度變化值.

輻射模型算法實現(xiàn)了兩點：第一，保證了并入聚類中的點是正確的.第二，對于少量未歸并入聚類的點，根據(jù)相似性原理進行歸并，大大減少了計算量，同時，也保證了該點歸并入聚類的正確性.因此，輻射模型算法保證每一個點的分類正確，減少計算量，克服異常點對聚類中心計算產(chǎn)生的影響，從而提升聚類計算的正確率.

5 實驗結(jié)果分析

5.1 旋轉(zhuǎn)不變性與尺度不變性實驗

為了驗證本文算法在旋轉(zhuǎn)不變性與尺度不變性上保留了良好特性，文中使用幾幅經(jīng)典的數(shù)字圖像作為實驗圖像，將對比圖像中的一張進行0～180度的旋轉(zhuǎn)，并使用本文算法對旋轉(zhuǎn)前后的圖像進行匹配，如圖4所示，并將對比圖像中一張進行尺度大小變化，對比示意圖如圖5，記錄每次匹配的結(jié)果與匹配正確率.

圖4 旋轉(zhuǎn)不變性匹配示意圖Fig.4 Schematic Diagram of Matching Rotation-invariant

圖5 尺度不變性匹配示意圖Fig.5 Schematic Diagram of Scale-invariant

通過匹配結(jié)果可以看出，本文算法對旋轉(zhuǎn)前后、縮放前后的圖像進行特征點匹配時，特征點匹配準(zhǔn)確度并未發(fā)生變化，可見，算法保持了良好的旋轉(zhuǎn)不變性與尺度不變性.

5.2 特征點匹配精度實驗

本組實驗采用的是相同景物的不同視角圖像，以第一張為基準(zhǔn)圖，與第二張進行匹配，并與給定的特征點參考表進行比對，得到匹配正確率.優(yōu)化前后算法執(zhí)行結(jié)果如表1和圖6所示:

從本組對比實驗可得，本文算法處理結(jié)果減少了原有SIFT點匹配中的多處錯誤匹配，是由于K-means聚類結(jié)合了圖像自身內(nèi)容的判斷，提高了特征點的定位精度，提供了準(zhǔn)確實現(xiàn)數(shù)據(jù)對象聚類的優(yōu)化條件，實現(xiàn)圖像特征點的提取正確率，較好地克服了原有SIFT特征點計算局部最優(yōu)的不足.

圖6 SIFT算法(上)與本文算法(下)匹配精度對比Fig.6 Comparison of Matching Accuracy between SIFT Algorithm (above) and Algorithm in this Paper (below)

6 結(jié)束語

本文針對原始的SIFT特征點匹配算法進行了對匹配特征點數(shù)量與精度的優(yōu)化，提出了一種結(jié)合K-means的SIFT特征匹配算法.首先對SIFT特征點進行聚類分析，為克服SIFT特征點坐標(biāo)取整帶來的欠準(zhǔn)確，使用亞像素插值算法搜索更精確的特征點位置，進一步通過輻射模型優(yōu)化聚類來剔除強噪聲點和孤立點，從而提高特征點匹配的精確度和正確率.實驗結(jié)果表明，本文算法在保證圖像特征點匹配的旋轉(zhuǎn)不變性與尺度不變性的前提下，通過提高圖像特征點的定位精度，剔除不良點提升特征點正確率，實現(xiàn)了多視角圖像的精確匹配，算法實現(xiàn)的時間復(fù)雜度研究未在本文過多涉及.