基于多目標優化的SIFT特征匹配算法

摘 要:SIFT算子在實際應用中，由于地面圖像本身特征不明顯且提取出的特征點多、亂以及灰度變化不明顯等特點的影響，從而導致特征點誤匹配。為此提出一種改進的SIFT圖像特征匹配算法。該算法是在SIFT特征匹配的基礎上，利用多目標優化算法，建立相關匹配模板，利用給定同一場景的兩幅圖像， 尋找同一場景點投影到圖像中的模板之間的相關性建立數學模型即目標函數，根據同一幅圖像中模板間的距離建立邊界約束條件，從而剔除一些誤匹配點。實驗表明，該算法可以有效地提高圖像匹配精度。

關鍵詞:SIFT; 多目標優化; 特征匹配; 誤匹配點

中圖分類號:TN911.73 文獻標識碼:A

文章編號:1004-373X(2010)12-0099-04

SIFT Feature Matching Algorithm Based on Multi-objective Optimization

YAN Zhi， WANG Li-ming，CHEN Ping

(National Key Laboratory for Electronic Measurement Technology， North University of China， Taiyuan 030051， China)

Abstract:SIFT (Scale Invariant Feature Transform) descriptor is commonly used in image matching due to the invariance of scale， rotation and illumination. While in practical applications， incorrect matching of feature points was happened because the ground image′s features were not obvious and the feature points extracted by SIFT were more， chaos as well as gray-scale did not change significantly. In order to solve the problem， an improved SIFT image feature point matching method is proposed. The method based on SIFT feature matching algorithm and used multi-objective optimization algorithm to establish correlation matching template， the two images of same scene was given to find an image projected onto a template to establish the correlation between the mathematical model of the objective function. According to distance between the template in the same image to establish the boundary constraint conditions， thus eliminate some 1 matching points. The experiments show that the algorithm can effectively improve its accuracy.

Keywords:SIFT;multi-objective optimization;feature matching; incorrect matching point

0 引 言

圖像特征匹配是計算機視覺和模式識別等領域研究的基本問題以及物體識別、跟蹤等應用的重要基礎，廣泛應用于攝影測量與遙感、資源分析、三維重建、目標識別、圖像拼接、圖像檢索等眾多領域， 一直是研究者關注的焦點， 在針對地面圖像的特征匹配方面得到了深入研究，以及對運動目標軌跡提取具有較高的研究意義和應用價值。但是由于它受到天氣、陽光、遮擋等外界因素的嚴重影響， 并且存在因不同的成像時間、角度、距離等因素而導致的圖像平移、旋轉、縮放等問題， 這都給目標特征檢測及特征匹配的工作帶來了很大的難度[1] 。針對這些不足，尤其是在尺度方面的不足，David G.Lowe在2004年總結了現有的基于不變量技術的特征檢測方法，提出了一種基于尺度空間的特征匹配算法——尺度不變特征變換(scale invariant feature transform，SIFT)算法[2-3] 。SIFT算法檢測的點特征是圖像的局部特征，該特征對平移、旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變化、噪聲也保持一定程度的穩定性和適應性，而且即使是信息量較少的圖像也能提取大量的SIFT特征點。然而在這些大量特征點中，也會產生一些誤匹配點，從而會導致圖像匹配精度，尤其是地面圖像，由于其本身特征點多、亂、灰度變化不明顯以及沒有角點、直線、邊緣、模板、區域和輪廓等明顯特征，導致部分特征點會發生誤配和亂配情況[4] 。

針對上述問題，本文提出基于多目標優化的特征匹配算法，該算法經過同一場景點投影到圖像中的模板建立目標函數，根據同一幅圖像中模板之間的歐氏距離建立約束條件，剔除誤匹配點，實現特征點的二次精確匹配。

1 SIFT 特征匹配理論

1.1 SIFT 特征匹配的主要思想

SIFT 算法是一種基于尺度空間、對圖像縮放、旋轉甚至仿射變換保持不變性的圖像局部特征描述操作數，可以理解兩幅圖像之間發生平移、旋轉、仿射變換、光照變化情況下的匹配問題，甚至在某種程度上對任意角度拍攝的圖像也具備較為穩定的特征匹配能力，從而可以實現差異較大的兩幅圖像之間的特征的匹配[3] 。

1.2 SIFT 特征匹配步驟

SIFT操作數首先在尺度空間進行特征檢測，并確定關鍵點的位置和關鍵點所處的尺度，然后使用關鍵點鄰域梯度的主方向作為該點的方向特征，以實現操作數對尺度和方向的無關性。

(1) 尺度空間的形成。

高斯卷積核實現尺度變換的惟一線形核，于是一幅二維圖像的尺度空間定義為:

L(x，y，σ)=G(x，y，σ)I(x，y)

式中:(x，y)是空間坐標;σ是尺度坐標，圖像被平滑的越少，相應的坐標值也就越小。大尺度對應于圖像的概貌特征，小尺度對應于圖像的細節特征。

為了有效地在尺度空間檢測到穩定的關鍵點，提出了高斯差分尺度空間(DOG)。DOG操作數定義為2個不同尺度的高斯核差分，DOG操作數如下:

D(x，y，σ)=[ G(x，y，kσ)-G(x，y，σ)] *I(x，y)=

L(x，y，kσ)-L(x，y，σ)

(2) 空間極值點的檢測。

為了尋找尺度空間的極值點，每一個采樣要和其所有相鄰點比較，以確保在尺度空間和二維圖像空間都檢測到極值點，通過擬和三維二次函數以精確確定關鍵點的位置和尺度，同時去除地對比度的關鍵點和不穩定的邊緣回應點，以增強匹配穩定性、提高抗噪聲能力[4] 。

(3) 關鍵點方向分配。

利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數，使操作數具備旋轉不變性。每個關鍵點有3個信息:位置、尺度、方向。由此確定一個SIFT特征區域。

(4) 特征點描述子生成。

為了增強匹配的穩健性，對每個關鍵點可使用4×4共16個種子點來描述，這樣對于一個關鍵點形成128維的SIFT特征向量[5-7]。

2 多目標優化理論與方法

最優化的目的是根據一定的標準(目標)在許多可供選擇的方案中搜索出最好的或最令人滿意的方案。如果選擇時需要同時考慮的標準多于一個，最優化問題就成為多目標優化問題。多目標優化的圖像處理問題是通過調節多個目標之間的權衡問題，使在一定的約束條件下同時達到最優，以此來減小圖像處理領域中的一些誤操作，如:增強、匹配、識別等。

maxy = F ( x )=(f1( x )，f2( x )，…，fk( x ))

s.t. ei( x )≤0， i=1，2，…，m

式中: x 稱為決策向量，x =(x1，x2，…，xn)∈Ω R n通常由模型參數組成;Ω為決策空間;fi( x )為第i個目標函數; y 為目標向量，y ∈Y R k，Y為目標空間，ei(x)為約束條件[8] 。

對于 x ∈Ω，如果X*∈Ω滿足下式，則稱向量為Pareto優解。

i∈{1，2，…，k}，fi( x )=fi( x *)∨

i∈{1，2，…，k}，fi( x )

在圖像處理多目標優化問題的可行解集中沒有比Pareto優解更好的解。由Pareto優解構成的集合稱為Pareto優集，Pareto優集中任何一個解都是可能的最優解。在圖像處理優化時，根據圖像處理者(稱為決策者)對優化目標主觀偏好程度與Pareto優解搜索過程之間的相互影響關系，多目標優化方法主要分為3類:先驗優先權法、后驗優先權法與優先權演化法[9] 。

3 基于多目標優化的SIFT 特征特征匹配算法

本文結合SIFT特征的眾多不變性優點，對地面圖像進行特征提取與匹配，且利用改進的特征點匹配算法計算候選目標的精確位置。然而在特征匹配的過程中，受天氣、光線和地面圖像復雜度的影響，會出現特征點的誤匹配，導致圖像出現匹配誤差。針對上述問題，該系統在SIFT特征匹配的基礎上引入多目標優化理論。在SIFT特征點提取的基礎上，利用多目標優化準則，實現2幅圖像的SIFT特征點的精確匹配。

如圖1所示，在進行圖像處理工作時，首先分析圖像處理的任務，根據實際要求建立圖像處理模型并確定優化目標和約束條件;其次根據優化目標涉及的參數設計相關變量，選擇設計優化算法并對變量進行優化搜索，在確定初始參數后，通過對模型參數的優化搜索和對優化結果的評價進行循環迭代，逐漸得到最優解。

圖1 圖像優化處理系統流程圖

在SIFT特征匹配中往往由于孤立點、噪聲點和地面圖像本身特征點多、亂、灰度變化不明顯以及直線、邊緣、輪廓等不明顯特征的影響，導致部分特征點會發生誤匹配和亂匹配，從而降低了特征匹配的精度。

具體算法流程如下:

(1) 利用SIFT算子對采集到的地面圖像進行特征點檢測，將采集到的特征點進行相似性度量，得到圖像間的粗匹配;

(2) 利用多目標優化算法對粗匹配的特征點進行分析。

建立模型如下:

(1) 在相機采集的第n幀圖像中，分別尋求圖像右半區域3個特征點并結合周圍的點組合成模板f11，f12，f13;且l1，l2分別為模板f11與f12之間的距離和f12與f13之間的距離。如圖2所示，在第n+1幀圖像中，根據車速以及相機的幀率估計第n幀圖像中3個特征出現的范圍，再從中依次遍歷SIFT特征點，并以該點為中心擴展模板f21，f22，f23;l1′，l2′ 分別為f21與f22之間的距離和f22與f23之間的距離。2幅圖像中的模板大小應保持一致。

圖2 第n幀圖像

圖3 第n+1幀圖像

(2) 確定優化設計的目標函數，如圖2、圖3所示，根據2幅地面圖像模板之間的相互關系建立目標函數:

max r=max cov[ f11，f21(x，y)]

max r=max cov[ f12，f22(x1，y1)]

max r=max cov[ f13，f23(x2，y2)]

式中:(xi，yi)(i=1，2，3)為第n+1幀圖像中的所遍歷的SIFT特征點的坐標值;cov[ f1i，f2i(xi，yi)] 為2個對應模板之間的相關系數。

(3) 確定約束條件。

對于2幅相鄰的圖像，其特征點的之間的距離要么不變，要么隨尺度的變化同時放大和縮小，為此可以二者距離的比值作為約束條件。

s.t.l1=l1′

l2=l2′

4 實驗驗證

為了體現此改進算法匹配精度的優越性，該實驗采用高速CCD相機拍取路面圖像并進行閉合曲線運動。如圖4所示。

在采集到的地面原始圖像中提取SIFT特征點，如圖5所示，從圖中可以看出，在采集圖像的過程中，由于地面圖像其本身特征點多、亂、灰度變化不明顯以及沒有角點、直線、邊緣、模板、區域和輪廓等明顯特征，不可避免地存在部分噪聲點和孤立點，導致部分特征點會發生誤配和亂配的情況，從其匹配結果(見圖6)可以看出這些孤立點和噪聲影響到了特征匹配精度。

圖4 相鄰兩幀地面原始圖像

圖5 對原始圖像提取出的特征點

圖6 未經多目標優化的匹配圖像

圖7 經多目標優化后的匹配圖像

圖8 常規方法提取出的相機軌跡

對粗匹配后的兩幅圖像進行多目標優化分析，從匹配結果(見圖7)來看，剔除了易產生誤匹配的特征點，幾乎沒有發生誤匹配現象。故提取出的相機軌跡(見圖8)可以看出，與實際的閉合曲線運動軌跡存在誤差。從提取出的相機運行軌跡(見圖9)來看，相機從某一起點出發并最終回到同一起點，較好地完成了閉合的曲線運動。

圖9 相機軌跡(閉合曲線)描述

5 結 語

本文針對地面提出了一種改進的SIFT特征匹配算法。首先在采集的圖像中提取出SIFT粗匹配特征點，然后再對這些特征點進行多目標優化分析，實現特征點的二次精確匹配。從實驗結果可看出，這種算法效果明顯，能夠有效地避免地面圖像中的噪聲點、孤立點對圖像匹配的影響，從而有效地提高了匹配精度。

參考文獻

[1]TOMASI C， KANADE T. Detection and tracking of point feature [R].Carnegie Mellon University Technical Report CMU - CS -91 - 132， Pittsburgh， USA， 1991.

[2]高建，黃心漢.一種簡化的SIFT圖像特征點提取算法[ J] .計算機應用研究，2008，25(7):2213-2215.

[3]LOWE David G. Distinctive image features from scale-invariant keypoints[ J] . International Journal of Computer Vision， 2004，60(2)，91-110.

[4]LOWE D G. Object recognition from local scale !invariant features [C]//International Conference on Computer Vision.[ S.l.] :[ s.n.] ， 1999: 1150-1157.

[5]王國美，陳孝威.SIFT特征匹配算法研究[ J] .鹽城工學院學報，2007，20(2):1-5.

[6]王楠，王勇峰，劉積仁.車行軌跡曲線的實施提取與描述[J].東北大學學報，1999，10(2):111-113.

[7]張健，周曉東，張春華.空間目標運動軌跡提取算法研究[J].紅外技術，2007，29(8):459-463.

[8]薛毅.最優化原理與方法[ M] .北京:北京工業大學出版社，2001.

[9]FLETCHER R. Practical Methods of Optimization[ M] . [ S.l.] : Wiley， 1980.

[10]傅英定，成孝予，唐應輝.最優化理論與方法[ M] .北京:國防工業出版社，2008.