基于SIFT特征匹配的圖像拼接算法

廖 飛，葉瑋瓊，王鵬程，吳金津，許可可

（湖南工業大學 計算機與通信學院，湖南 株洲 412007）

基于SIFT特征匹配的圖像拼接算法

廖 飛，葉瑋瓊，王鵬程，吳金津，許可可

（湖南工業大學 計算機與通信學院，湖南 株洲 412007）

針對傳統圖像拼接算法效率低和魯棒性差的問題，提出一種改進的基于SIFT特征匹配的圖像拼接算法。在圖像預處理階段，首次運用離散余弦變換、量化、反離散余弦變換、反量化，來對圖像增強。其次，在計算變換模型時，由于沒有預檢驗策略，致使RANSAC算法迭代次數增加。為此，提出了預檢驗策略。實驗結果表明，在不改變匹配精度的前提下，該改進算法得到了比較理想的效果。

圖像拼接；離散余弦變換；RANSAC算法；SIFT算法

0 引言

圖像拼接是指將二幅或以上具有部分重疊的圖像利用一定的圖像拼接算法進行無縫拼接，得到一幅大型的無縫高分辨率寬視角圖像。圖像拼接可分為圖像配準和圖像融合兩個步驟。圖像配準是將不同時間、不同傳感器（成像設備）或不同條件下（天候、照度、攝像位置和角度等）獲取的兩幅或多幅圖像進行匹配、疊加的過程。圖像融合是指綜合和提取兩個或多個多源圖像信息，獲得對同一場景或者目標更為準確、全面和可靠的圖像，使之更適應于人眼感知或計算機后續處理。目前，圖像融合技術在算法上已經相當成熟，對圖像拼接的質量影響不大，圖像配準的好壞直接關系到圖像拼接的質量和效率，是圖像拼接的關鍵[1]。尺度不變特征變換匹配算法[2]（scale invariant feature transform，SIFT）由于其對圖像旋轉和尺度變化等均具有不變性，是廣泛使用的一種特征匹配算法。但是SIFT算法提取特征點后，必須消除不匹配點。傳統的隨機取樣一致性算法[3]（random sample consensus，RANSAC）在消除過程中效率非常低，尤其當圖像待匹配特征點中誤匹配點比例較大時，耗時較多，大大影響了圖像拼接算法效率。

針對傳統圖像拼接算法效率低和魯棒性差的問題，課題組提出一種改進的基于SIFT特征匹配的圖像拼接算法。在圖像預處理階段，首先，運用離散余弦變換、量化、反離散余弦變換、反量化對圖像增強。其次，在計算變換模型時，由于沒有預檢驗策略，致使RANSAC算法迭代次數增加。因此，提出了預檢驗策略，通過改進大大減少了算法迭代次數，提高了匹配效率。

1 圖像預處理

為了剔除圖像噪聲和提升圖像品質，要對原始圖像和目標圖像進行預處理操作。利用人眼對高頻部分不敏感的特性，采用空間域的低通濾波器和量化過程實現圖像數據優化處理。

1.1 離散余弦變換和反離散余弦變換

離散余弦變換（discrete cosine transform，DCT）實際上是空間域的低通濾波器，具有很強的“能量集中”特性。大多數自然信號（包括聲音和圖像）的能量都集中在離散余弦變換后的低頻部分。

二維正向離散余弦變換F(u, v)（forward DCT，FDCT）計算公式如下（采用 8×8 圖像塊）：

式中：c(u)為第u個余弦變換系數；c(v)為第v個余弦變換系數；u，v為廣義頻率變量；f(i, j)為空間域中的二維向量；u, v, i, j=0, 1, 2,…, N-1。

當對圖像解碼時，使用反向離散余弦變換f(i, j)（inverse DCT，IDCT），變換公式如下：

二維離散余弦變換具有可分離性，所以二維變換可分解為一系列的一維變換G(i, v)。（行，列）計算公式如下：

1.2 量化和反量化

量化是在不引起明顯的視覺效果失真的前提下，部分拋棄圖像數據，以達到剔除圖像中噪聲的目的[4]。量化過程實際上是簡單地把頻率領域上的每個值，除以量化表中對應的常數，四舍五入取最接近的整數。整個量化的目的是減小非“0”系數的幅度以及增加“0”值系數的數目。

圖像塊（8×8）經過DCT變換后，低頻分量都集中在左上角，高頻分量分布在右下角。由于圖像的主要信息包含在低頻率分量中，而高頻分量往往包含噪聲信號，影響圖像品質和數據優化處理，所以可以剔除高頻分量。將高頻分量去除就是量化，反量化是量化的逆過程。由于量化表左上角的值較小，右下角的值較大，這樣就起到了保持低頻分量和抑制高頻分量的作用。

量化值計算公式如下：

式中：Sq(u, v)為量化后的結果；F(u, v)為DCT系數；S(u, v)為量化表中的數值。

圖像預處理過程具體實現步驟如下：

Step1 將兩幅圖像進行離散余弦變換，把圖像中點與點間的規律呈現出來；

Step2 進行量化處理，在高頻段，將出現大量連續的零，這樣就剔除了圖像中的噪聲；

Step3 進行反量化和反離散余弦變換，把圖像從空間域變換到時間域，預處理過程結束。

2 算法流程

傳統SIFT特征匹配算法可歸為在不同尺度空間上查找特征點的問題。由于其具有很好的不變性，所以被廣泛運用于圖像的特征提取和匹配中，但是其提取出來的特征點往往包含著大量誤匹配特征點對，因此，對其進行改進，添加預檢驗策略過程。

2.1 傳統的SIFT特征匹配算法

1999年British Columbia大學大衛·勞伊（David G. Lowe）教授總結了現有的基于不變量技術的特征檢測方法，正式提出了一種基于尺度空間的、對圖像縮放、旋轉甚至仿射變換保持不變性的圖像局部特征描述算子SIFT[5]。

傳統的SIFT算法具體實現步驟如下。

1）關鍵點檢測。關鍵點是一些十分突出并且不會因光照條件的改變而消失的、在不同尺度空間的圖像檢測出的具有方向信息的局部極值點。

高斯核是唯一可產生多尺度空間的變換核[6]，一個函數的尺度空間L(x, y, )，定義為輸入圖像I(x, y)（代表圖像在位置(x, y)的像素值）與一個可變尺度的二維高斯函數G(x, y, )卷積運算（ 為高斯正態分布標準差，稱為尺度空間因子）。

為更有效檢測出尺度空間中的穩定特征點和簡化運算，引入高斯差分函數D(x, y, )（k為相鄰兩個圖像的尺度比例因子的尺度）：

2）關鍵點描述。描述的目的是在關鍵點計算后，用一組向量將這個關鍵點描述出來，這個描述子不但包括關鍵點，也包括關鍵點周圍對其有貢獻的像素點。通過對關鍵點周圍圖像區域分塊，計算塊內梯度直方圖，生成具有獨特性的向量。

3）關鍵點匹配。分別對原始圖像和目標圖像建立關鍵點描述子集合。目標的識別通過兩點集內關鍵點描述子的比對來完成。采用歐式距離作為具有128維的關鍵點描述子的相似性度量。即取一幅圖像的一個特征點，找出另一幅圖像中與其距離最近的前兩個特征點，在這兩個特征點中，若最近距離除以次近距離小于比例閾值，則接受該匹配點。

4）消除誤匹配特征點。關鍵點匹配并不能標志算法結束，因為在匹配的過程中存在著大量的誤匹配特征點。消除誤匹配特征點，就要使用RANSAC算法。

2.2 改進的預檢驗策略

改進算法思想為：用RANSAC算法對誤匹配特征點進行提純時，因存在大量誤匹配特征點，而RANSAC算法沒有預檢驗策略，將在錯誤變換模型的計算和檢驗上耗費大量時間，致使其迭代次數增加、效率降低，并且影響拼接圖像質量。為此，提出一種改進的預檢驗策略，在計算變換模型之前，用聚類法預篩選數據；再將篩選出來的數據用視差梯度法二次篩選，通過兩次篩選大大減少了誤匹配特征點對數目，提高了RANSAC算法效率。

2.2.1 預檢驗策略聚類法初次篩選

在運行RANSAC算法之前，根據待拼接圖像匹配點之間的連線斜率應相同或相近的特性，將兩幅待匹配的圖像置于同一坐標系下，然后以某一斜率值為中心，設定一鄰域閾值，依據以下特征找到某一較小鄰域內包含最多的斜率相近點對，則這些點就是最精確匹配的相關點對。

定義如下特征來判斷關鍵點是否是精確匹配的特征點對。

式中：ki，kj分別代表第i和第j條直線的斜率。

式中：t為鄰域閾值（依據經驗值本文取0.02）。

具體預檢驗策略實現步驟如下：

Step1 將原始圖像和目標圖像變換到同一坐標系下，計算粗匹配數據集中所有直線的斜率值；

Step2 由特征1和特征2循環計算值，并記下此時值，由此計算出鄰域內的點對集，作為預選出的待匹配點，刪除在鄰域外的點對集；

Step3 如此循環，遍歷整個粗匹配特征點集，得到初次篩選匹配特征點集。

2.2.2 預檢驗策略視差梯度法二次篩選

根據視差梯度的定義[7]，若原始圖像中的兩個相鄰的特征點m，n分別和目標幅圖像中的特征點m′，n′匹配，則視差梯度應小于2。采用視差梯度可以更精確地對特征點進行篩選，視差梯度的定義如特征3所示。

特征3 視差梯度Gd為

式中：（Xm, Ym）和（Xn，Yn）是對應特征點的圖像坐標向量；·表示向量的模。

具體預檢驗策略實現步驟如下：

Step1 對2.2.1節篩選出的待匹配點集，從中隨機選擇兩對匹配點，根據特征3計算它們的視差梯度值，若其視差梯度小于2，則接收該特征點對為精確匹配特征點對，否則剔除該點對；

Step2 如此循環，遍歷所有特征點集，得到二次篩選匹配點集；

Step3 對篩選出來的匹配點集，再由RANSAC算法對其進行精確提純，得到的結果集即為匹配的特征點對；

Step4 使用匹配的特征點計算變換矩陣，并用列文伯格-馬夸爾特法[8]（levenberg-marquardt，LM）算法進行優化，最終完成特征匹配。

3 實驗結果與分析

選擇的實驗平臺為Visual C++6.0，改進圖像拼接算法過程圖如圖1所示。

圖1 圖像拼接算法過程圖Fig.1 The process of image stitching algorithm

為了更好地驗證算法的有效性，選擇2幅具有部分重疊區域的自然場景圖像進行實驗，圖像如圖2～3所示。

圖2 待拼接圖像1Fig.2 Original image 1

圖3 待拼接圖像2Fig.3 Original image 2

利用SIFT算法提取2幅圖像的特征點并匹配，得到272個匹配點對。其結果如圖4所示。由圖4可以看出，對于圖像的匹配結果存在誤匹配現象。本研究組采用預檢驗策略和RANSAC算法對粗匹配點集進行提純，刪除誤匹配特征點，對于同一圖像得到篩選后的匹配點92對。最后，圖像拼接后的效果圖如圖5所示。

圖4 SIFT特征提取與匹配Fig.4 SIFT features extracting and matching

圖5 圖像拼接后的效果圖Fig.5 The result of images stitching

通過和原算法比較，得到的對比結果如表1所示。

表1 改進算法與原算法對比Tabel1 The improved algorithm comparing with the original algorithm

從表1可以看出，改進算法一方面所用時間有所減少（其中包括預檢驗策略消耗的時間）、迭代次數明顯降低；另一方面，用預檢驗策略剔除誤匹配點時，消耗了大量時間，并且增加了算法復雜度。

4 結語

基于SIFT特征匹配的圖像拼接算法，彌補了傳統圖像拼接方法在尺度、光照變化上的缺陷，但是該算法提取出來的粗匹配特征點包含大量誤匹配特征點對，影響匹配效率。因此，提出兩點改進之處：在SIFT算法之前，加入低通濾波器，使用量化過程剔除圖像中的噪聲，使圖像增強；在運行RANSAC算法之前，用預檢驗策略篩選特征點集。實驗結果表明，在不改變匹配精度的前提下，該改進算法效率更高。

[1] 張 琳，褚龍現. 基于全局拼接的船舶圖像拼接算法研究[J]. 計算機仿真，2012，29(4)：282-285. Zhang Lin，Chu Longxian. Aerial Image Mosaic AlgorithmsResearch Based on Global Mosaic[J]. Computer Simulation，2012，29(4)：282-285.

[2]Brown M，Love D. Recognizing Panoramas[C]//Proceeding of the 9th International Conference on Computer Vision. Nite：[s.n.]，2003：218-225.

[3]Chen Fuxing，Wang Runsheng. Fast RANSAC with Preview Model Parameters Evaluation[J]. Journal of Software，2005，16(8)：1431-1437.

[4]張春田，蘇育挺，張 靜. 數字圖像壓縮編碼[M]. 北京：清華大學出版社，2006：68-70. Zhang Chuntian，Su Yuting，Zhang Jing. Digital Image Compression Coding[M]. Beijing：Tsinghua University Press，2006：68-70.

[5] 曹 楠，王 萍. 基于SIFT特征匹配的圖像無縫拼接算法[J]. 計算機與應用化學，2011，28(2)：242-244. Cao Nan，Wang Ping. Seamless Image Stitching Based on SIFT Feature Matching[J]. Computers and Applied Chemistry，2011，28(2)：242-244.

[6] Koenderink J J. The Structure of Images[J]. Biological Cybernetics，1984，50：363-370.

[7]馬頌德，張正友. 計算機視覺[M]. 北京：北京科學出版社，1988：82-83. Ma Songde，Zhang Zhengyou. Computer Vision[M]. Beijing：Beijing Science and Technology Press，1988：82-83.

[8]Richard Szeliski，Hung-Yung Shum. Creating Full View Panoramic Image Mosaics and Environment Maps[C]// Proceeding of 24th Annual Conference on Computer Graphics and Interactive Techniques，Los Angels：ACM Press，1997：251-258.

（責任編輯：申 劍）

Image Mosaic Algorithm Based on SIFT Feature Matching

Liao Fei，Ye Weiqiong，Wang Pengcheng，Wu Jinjin，Xu Keke
（School of Computer and Communication， Hunan University of Technology，Zhuzhou Hunan 412007，China）

In order to solve the problem of low efficiency and poor robustness of traditional image mosaic algorithm, an improved SIFT-based feature matching algorithm for image stitching were put forward. Firstly enhanced the images by using the discrete cosine transform，quantization, inverse discrete cosine transform and inverse quantization in the image preprocessing stage, and then proposed the pre-inspection strategy in view of the RANSAC algorithm iteration increasing when computing the transformation models. The experimental results showed that the improved algorithm obtained the quite ideal effect without changing the matching precision.

image mosaic；discrete cosine transform；RANSAC algorithm；SIFT algorithm

TP317.4

：A

：1673-9833(2014)01-0071-05

2013-10-18

廖 飛（1988-），男，湖南常德人，湖南工業大學碩士生，主要研究方向為嵌入式系統，

E-mail ：1525127621@qq.com

10.3969/j.issn.1673-9833.2014.01.015