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

文永革

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

0 引言

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

1 SIFT 算法

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

1.1 SIFT 特征檢測

(1) 尺度空間極值檢測

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

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

(1)

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

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

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

(2)

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

(2) 特征點(diǎn)的定位

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

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

(3)特征點(diǎn)的方向

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

(3)

(4)

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

(4)特征點(diǎn)的描述

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

2 K-means聚類算法

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

2.1 K-means 算法

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

2.2 K-MEANS 算法基本流程

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

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

(5)

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

(6)

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

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

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

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

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

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

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

(7)

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

(8)

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

4.2 輻射模型分析

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

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

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

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

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

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

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

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

5.2 特征點(diǎn)匹配精度實(shí)驗(yàn)

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

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

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

6 結(jié)束語

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