基于SIFT算法改進(jìn)的圖像匹配算法

章雷 王國明

摘要：傳統(tǒng)SIFT圖像匹配算法約束條件較為單一，導(dǎo)致SIFT算法在原圖像中存在相似特征很多的情況下，誤匹配問題比較明顯，不能有效剔除誤匹配點(diǎn)。為解決這個(gè)問題，提出了一種基于SIFT特征點(diǎn)構(gòu)建近鄰圖結(jié)構(gòu)和增加向量約束條件的圖像匹配方法。首先，使用K-mean方法對(duì)SIFT的特征點(diǎn)集進(jìn)行聚類，進(jìn)而生成K近鄰圖結(jié)構(gòu)完成初始匹配。然后，在歐氏距離約束條件的基礎(chǔ)上，增加向量相似度約束對(duì)傳統(tǒng)SIFT算法約束條件進(jìn)行改進(jìn)，并根據(jù)相關(guān)系數(shù)進(jìn)行匹配點(diǎn)的篩選，完成精確匹配。實(shí)驗(yàn)結(jié)果表明，該算法有效。

關(guān)鍵詞：SIFT;向量相似度;K-mean;約束條件;歐式距離

中圖分類號(hào)：G623? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2019）01-0185-03

Improved Image Matching Algorithm Based on SIFT Algorithm

ZHANG Lei，WANG Guo-Ming

（College of Computer Science and Engineering，Anhui University of Science &Technology， Huainan 232001，China）

Abstract：The constraint condition of the traditional SIFT image matching algorithm is relatively single， which leads to the fact that the SIFT algorithm has many similar features in the original image， the problem of mismatched is relatively obvious， and the mismatched points cannot be effectively eliminated.To solve this problem， an image matching method based on SIFT operator fusion vision dictionary and adding vector constraints is proposed.First， k-mean method is used to cluster the feature point set of SIFT， and then the k-nearest neighbor graph structure is generated to complete the initial matching.Then， on the basis of the Euclidean distance constraint， the constraint condition of the traditional SIFT algorithm was improved by adding the vector similarity constraint， and the matching point was screened according to the correlation coefficient to complete the accurate matching.Experimental results show that the algorithm is effective.

Key word：SIFT;Vector similarity; K-mean;Constraint Condition; Euclidean distance

近些年，計(jì)算機(jī)視覺領(lǐng)域發(fā)展迅速。圖像匹配技術(shù)是計(jì)算機(jī)視覺領(lǐng)域中的一項(xiàng)重要的技術(shù)[1，2]。目前已經(jīng)在許多領(lǐng)域得到了應(yīng)用，諸如人臉識(shí)別、圖像三維重建、計(jì)算機(jī)視覺等。

圖像匹配指的是利用相關(guān)的匹配算法將兩幅圖像同一的位置點(diǎn)關(guān)聯(lián)在一起的過程[3]。在實(shí)際應(yīng)用中，由于目標(biāo)位置以及相機(jī)視角的變化，光照強(qiáng)度不同等諸多干擾因素導(dǎo)致重復(fù)特征多，亮度變化大、干擾特征多等問題，給圖像的精確匹配帶來了不小的挑戰(zhàn)[4]。

傳統(tǒng)SIFT算法中采用的約束條件是與樣本最近鄰特征點(diǎn)歐式距離與次近鄰特征點(diǎn)比值小于0.8來提取匹配點(diǎn)[5]，傳統(tǒng)SIFT圖像匹配算法約束條件較為單一，在原圖像中存在相似特征較多的情況下，誤匹配問題比較明顯，不能有效剔除誤匹配點(diǎn)，易出現(xiàn)錯(cuò)配和誤配情況。

針對(duì)以上提出的問題，本文提出了一種基于SIFT特征點(diǎn)構(gòu)建近鄰圖結(jié)構(gòu)和增加向量約束條件的改進(jìn)的SIFT算法圖像匹配方法。該方法分兩步，第一步，在初始匹配階段，使用K-mean方法對(duì)SIFT的特征點(diǎn)集進(jìn)行聚類，進(jìn)而生成K近鄰圖結(jié)構(gòu)[6]，完成初始圖匹配，從圖集合中篩選出可能與原圖匹配的候選圖;第二步，精確匹配階段，候選圖的特征點(diǎn)集在歐式距離的約束下，增加對(duì)SIFT算法中特征向量進(jìn)行向量相似度的計(jì)算，增加向量的相似性約束，然后根據(jù)相關(guān)系數(shù)進(jìn)行匹配點(diǎn)的篩選，最終完成精確匹配。

1 初始階段

本節(jié)首先介紹了SIFT算法基本原理，然后定義圖匹配的模型，最后說明了初始匹配階段的主圖匹配算法過程。

1.1 SIFT算法基本原理

尺度不變特征變換（SIFT）[7]的基本思想是在尺度空間概念構(gòu)建尺度空間提取位置、尺度和旋轉(zhuǎn)無關(guān)量。具體做法是先構(gòu)建尺度空間，在尺度空間中尋找局部極值點(diǎn)，確定關(guān)鍵點(diǎn)的主方向，生成關(guān)鍵點(diǎn)的描述子，最后進(jìn)行匹配。以下是SIFT算法的5個(gè)主要步驟：

STEP 1? 尺度空間的極值檢測

首先將圖像轉(zhuǎn)換到尺度空間上，采用高斯函數(shù)[Gx，y，σ]與圖像[Ix，y]進(jìn)行卷積運(yùn)算，將二維圖像[Ix，y]轉(zhuǎn)換到尺度空間圖像[Lx，y，σ]，[σ]為空間尺度因子。

[Lx，y，σ=Gx，y，σ*Ix，y? ? ? ?]? ? ? ? ? ? ? ? ? ? （1）

[? Gx，y，σ=12πσ2exp-x2+y22σ2]? ? ? ? ? ? ? ? ? ? ? （2）

為了進(jìn)行尺度空間的極值檢測，可以采用高斯函數(shù)（DOG）與圖像[Ix，y]進(jìn)行卷積計(jì)算得到尺度空間的極值點(diǎn)，其計(jì)算過程為：

[D（x，y，σ）=（G（x，y，kσ）-G（x，y，σ））*I（x，y）]? ? （3）

其中，k為乘數(shù)因子，用于改變相鄰尺度的尺度大小。

STEP 2? 關(guān)鍵點(diǎn)定位

對(duì)于關(guān)鍵點(diǎn)的定位可以對(duì)DOG函數(shù)進(jìn)行二次泰勒展開進(jìn)行運(yùn)算，并對(duì)采樣點(diǎn)進(jìn)行計(jì)算：

[DX=D+?DT?XX+12XT?2D?DX2X]? ? ? ? ? ? ? ? ?（4）

其中，為極值點(diǎn)到樣本數(shù)據(jù)點(diǎn)的偏移量，對(duì)求導(dǎo)后取極值可獲得極值點(diǎn)的位置。

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

SIFT變換過程中為圖像局部特征的每個(gè)關(guān)鍵點(diǎn)都設(shè)定了一個(gè)相對(duì)方向，因此可以實(shí)現(xiàn)對(duì)圖像的旋轉(zhuǎn)的不變性。關(guān)鍵點(diǎn)方向參數(shù)通過求該關(guān)鍵點(diǎn)相鄰像素的梯度方向分布特性得到。

STEP 4? 特征點(diǎn)生成

首先計(jì)算關(guān)鍵點(diǎn)附近像素點(diǎn)的梯度模值和方向，以每個(gè)關(guān)鍵點(diǎn)為中心取16×16像素窗口，并在每個(gè)窗口中取4×4像素種子點(diǎn)來描述，單個(gè)關(guān)鍵點(diǎn)就形成了128維的描述特征向量。

STEP 5? 特征點(diǎn)匹配

SIFT特征描述符向量生成后，求查詢樣本到目標(biāo)樣本最近鄰特征點(diǎn)歐氏距離與次近鄰特征點(diǎn)歐氏距離。如果最近鄰特征點(diǎn)歐氏距離與次近鄰特征點(diǎn)歐氏距離比值小于某一閾值時(shí)，認(rèn)為該特征點(diǎn)對(duì)匹配成功，否則匹配失敗。此處的閾值一般設(shè)定為0.8。

1.2 圖匹配

在基于圖模型的應(yīng)用中，圖匹配[8]是一項(xiàng)基礎(chǔ)而又重要的技術(shù)。在本文中圖模型的節(jié)點(diǎn)是圖像的特征點(diǎn)，圖模型[9]的邊用來描述特征點(diǎn)之間的關(guān)系。利用圖模型描述圖像特征以后，圖像的特征匹配問題就可以轉(zhuǎn)化為圖的頂點(diǎn)匹配問題[10]。以下是主圖匹配的算法步驟：

輸入：目標(biāo)圖像P，圖像集合Qm

輸出：候選圖Gw

步驟：

Step1 對(duì)目標(biāo)圖像P進(jìn)行SIFT特征點(diǎn)提取，生成特征點(diǎn)集MP={mi};

Step2 分別對(duì)圖像集合Qm進(jìn)行SIFT特征點(diǎn)提取，生成特征點(diǎn)集W={M1，M2，...，Mn};

Step3 對(duì)特征點(diǎn)集MP={mi}進(jìn)行聚類操作，生成新的點(diǎn)集Mp={mi};

Step4 對(duì)特征點(diǎn)集W={M1，M2，...，Mn}進(jìn)行聚類操作，生成新的點(diǎn)W={M1，...，Mn};

Step5 生成近鄰圖Gm=（VM，EM）。其中VM是圖節(jié)點(diǎn)，EM={eij}，當(dāng)i點(diǎn)和j是點(diǎn)近鄰并且兩點(diǎn)之間的距離小于所有點(diǎn)集之間的距離平均值時(shí)，點(diǎn)和點(diǎn)之間構(gòu)成一條無向邊eij;

Step6 運(yùn)用Step5中的方法，為點(diǎn)集W={M1，M2，...，Mn}生成K近鄰圖集合Gw={Gm1，Gm2，...，Gmn};

Step7 將Gm與Gw中的每個(gè)元素進(jìn)行匹配，選出候選圖Gw={G1，G2，...，Gm}，其中m<=n。

2 精確匹配

本節(jié)介紹了精確匹配階段需要的向量相似度計(jì)算理論，然后說明了將向量的相關(guān)系數(shù)融入傳統(tǒng)SIFT算法中，對(duì)SIFT算法進(jìn)行了改進(jìn)。

2.1 向量相似度計(jì)算

相似度是指兩個(gè)對(duì)象之間的類似的程度[11]。在本文中，采用的是SIFT特征點(diǎn)描述符，由于它是128維向量組成，故采用一般向量的相似度函數(shù)來度量相似程度[12，13]。假設(shè)對(duì)于任意兩向量[X，Y]，從向量的大小和方向的角度綜合表征兩向量的相似程度[14]?？啥x向量之間的關(guān)系如下：

定義1：向量[X，Y]的長度相似度（[αX，Y]），長度相似度是衡量向量大小的標(biāo)準(zhǔn)。

設(shè)存在向量[X=x1，x2，…，xn]，[ Y=y1，y2，…，yn]，則向量[X，Y]的長度相似度為

[αX，Y=1-X-YX] 其中[X]表示向量[X]的范數(shù)（5）

定義2：向量[X，Y]的方向相似度（[βX，Y]），方向相似度是衡量向量之間夾角大小的標(biāo)準(zhǔn)。

設(shè)存在向量[X=x1，x2，…，xn]，[ Y=y1，y2，…，yn] 則[βX，Y]為

[βX，Y=1-θ90°] ，其中

[θ=arccosX，YXY? ?0≤θ≤180°]? ? ? ? ? ? ? ? （6）

定義3：設(shè)存在向量

[X=x1，x2，…，xn]，[ Y=y1，y2，…，yn]，則向量[X，Y]的相似度（[γX，Y]為

[γX，Y=αX，Y?βX，Y]? ? ? ? ? ? ? ? ?（7）

其中（[γX，Y∈1，-1]? ，當(dāng)[θ=90°]時(shí)，兩個(gè)向量正交，此時(shí)相似度系數(shù)[γX，Y=0];當(dāng)[θ=0°] 時(shí)，并且范數(shù)相同時(shí)，兩向量的相似度系數(shù)[γX，Y=1];當(dāng)[θ=180°]時(shí)，并且范數(shù)相同時(shí)，兩向量的相似度系數(shù)[γX，Y=-1] 。

2.2 向量的相關(guān)系數(shù)

在主圖匹配完成后，篩選出符合條件的候選圖，將候選圖在SIFT初始匹配的點(diǎn)集M={mi}和W={wi}與待匹配的圖的特征點(diǎn)集進(jìn)行匹配。

SIFT算法在相似區(qū)域較多的圖像以及特征信息很相似時(shí)，容易出現(xiàn)錯(cuò)配和誤配情況。原SIFT算法中采用與樣本最近鄰特征點(diǎn)歐式距離來提取匹配點(diǎn)，沒有考慮到特征向量間的相關(guān)性。歐式距離[15]是一種距離度量法，通過度量向量空間距離來表示向量間的相似程度，距離越近則向量越相似;當(dāng)相似特征很多時(shí)，會(huì)有多個(gè)向量之間在向量空間距離是近似相等的，便會(huì)出現(xiàn)誤配現(xiàn)象。在原有的約束條件下，運(yùn)用相關(guān)系數(shù)法，增加向量間的相似性度量，提高了其匹配的精準(zhǔn)度。

具體做法：在目標(biāo)圖像與待匹配圖像之間的某一組特征描述滿足于歐氏距離比小于0.8的前提下，進(jìn)一步來計(jì)算這兩組向量之間的相關(guān)系數(shù)R，其中R的取值范圍為[0，1]，當(dāng)相關(guān)系數(shù)越大時(shí)，說明兩向量越相似。以下是精確匹配階段的算法步驟：

輸入：候選圖Gw

輸出：是否找到目標(biāo)圖像P的匹配圖像P

步驟：

Step1? 對(duì)目標(biāo)圖像P特征點(diǎn)集MP={mi}，進(jìn)行向量相關(guān)系數(shù)計(jì)算;

Step2? 對(duì)候選圖Gw={G1，G2，...，Gm}在W={M1，M2，...，Mn}對(duì)應(yīng)的特征點(diǎn)集進(jìn)行向量相關(guān)系數(shù)計(jì)算;

Step3? 將向量相關(guān)系數(shù)約束融入SIFT匹配算法中，完成匹配。

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

3.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)硬件環(huán)境為CPU 為Intel CORE I5，內(nèi)存為4G的PC機(jī)。仿真實(shí)驗(yàn)環(huán)境是Windows8.1下的Matlab2016（a）軟件，實(shí)驗(yàn)所采用的圖像為Daniel Scharstein和Richard Szeliski立體匹配試驗(yàn)時(shí)使用的圖像，從中選取了Bull、ohta 、venus、poster等四組試驗(yàn)圖像。

本次實(shí)驗(yàn)從每組圖像中選取兩張圖像，一張圖像作為目標(biāo)圖像，一張圖像作為待匹配圖像，在待匹配圖像中匹配到目標(biāo)圖像。由于圖像的中心事物不變，導(dǎo)致兩張圖像存在大量相似區(qū)域。選用這些圖像能有效地檢驗(yàn)算法的匹配能力。選取的圖像如圖2所示：

3.2 試驗(yàn)結(jié)果分析

圖3是傳統(tǒng)的SIFT算法對(duì)bull圖進(jìn)行圖像匹配的效果圖，圖4是改進(jìn)的算法進(jìn)行圖像匹配的效果圖。由圖3和圖4可見，對(duì)于重復(fù)和相似的特征點(diǎn)的問題，改進(jìn)的算法有效地緩解了這一問題。表1是對(duì)試驗(yàn)圖特征點(diǎn)結(jié)果的統(tǒng)計(jì)。

綜合分析， 由表1試驗(yàn)結(jié)果統(tǒng)計(jì)結(jié)果可知，對(duì)Daniel Scharstein和Richard Szeliski立體匹配試驗(yàn)時(shí)使用的bull、ohta 、venus、poster等四組圖像，本文中算法減少了重復(fù)特征點(diǎn)的數(shù)目，提高了匹配正確率，解決了由于相似區(qū)域較多帶來的誤匹配點(diǎn)多的問題，使用本文算法后，能捕獲到更多的正確匹配點(diǎn)。試驗(yàn)結(jié)果基本滿足算法設(shè)計(jì)目的。

4 結(jié)語

本文在傳統(tǒng)的SIFT算法的基礎(chǔ)上，針對(duì)SIFT圖像匹配算法誤配率比較高的問題，提出了增加向量約束條件的圖像匹配方法。首先對(duì)SIFT的特征點(diǎn)集進(jìn)行聚類，生成K近鄰圖結(jié)構(gòu)，對(duì)K近鄰圖進(jìn)行匹配操作。匹配成功后，在歐式距離的約束下，進(jìn)一步對(duì)SIFT算法中特征向量增加了向量的相似性約束，保證了特征點(diǎn)的質(zhì)量，減少了重復(fù)特征點(diǎn)的數(shù)目，提高了匹配的正確率，減少了誤匹配點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該算法有效。

參考文獻(xiàn)：

[1] 羅斌.數(shù)字圖像的結(jié)構(gòu)圖建模、特征描述和匹配研究[J].安徽大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， （1）： 1-2.

[2] 項(xiàng)英倬，譚菊仙，韓杰思，等.圖匹配技術(shù)研究[J].計(jì)算機(jī)科學(xué)，2018，（6）：27-31，45.

[3] 江波，湯進(jìn)，羅斌.計(jì)算機(jī)視覺中的圖匹配方法研究綜述[J].安徽大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， （1）：29-36.

[4] 謝宜婷，王愛平，鄒海.基于局部近鄰圖的特征描述與特征匹配算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2017，（8）：185-190，196.

[5] 白廷柱，侯喜報(bào).基于SIFT算子的圖像匹配算法研究[J].北京理工大學(xué)學(xué)報(bào)，2013， （6）： 622-627.

[6]? Park， Youngki，Park， Sungchan，Jung， Woosung， et al.Reversed CF： A fast collaborative filtering algorithm using a k-nearest neighbor graph[J].Expert Systems with Application， 2015，

[7]? LOWE D G.Distinctive image features from scale-invarlant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-100.

[8] 白雪冰，陳凱，郭景秋， 等.基于k-mean聚類與灰度梯度最大熵的樹木圖像分割[J].森林工程，2014，（6）：84-88.

[9] 趙一丹，肖秦琨，高嵩.基于模糊神經(jīng)網(wǎng)絡(luò)和圖模型推理的動(dòng)作識(shí)別[J].計(jì)算機(jī)技術(shù)與發(fā)展，2018，（8）：80-85.

[10] 張文靜，王備戰(zhàn)，張志宏.基于圖的特征選擇算法綜述[J].安徽大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， （1）：10-20.

[11] Image quality assessment method based on nonlinear feature extraction in kernel space[J].信息與電子工程前沿（英文版），2016，（10）：1008-1017.

[12] 賀飛躍，田錚，段西發(fā)，等.高效的圖模型點(diǎn)模式匹配算法[J].計(jì)算機(jī)工程與應(yīng)用，2013， （24）： 19-23.

[13] 張宇，劉雨東，計(jì)釗.向量相似度測度方法[J].聲學(xué)技術(shù)，2009，28（4）：532-536.

[14] 花小朋，徐森，李先鋒.Least squares weighted twin support vector machines with local information[J].中南大學(xué)學(xué)報(bào)（英文版），2015，（7）：2638-2645.

[15] 張明，田娜，紀(jì)志成.基于適應(yīng)值歐式距離比的均衡蜂群算法[J].系統(tǒng)仿真學(xué)報(bào)，2015， （5）： 980-989.