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

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

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

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

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

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

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

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

0 引言

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

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

1 圖像預(yù)處理

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

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

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

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

式中：c(u)為第u個余弦變換系數(shù)；c(v)為第v個余弦變換系數(shù)；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 量化和反量化

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

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

量化值計算公式如下：

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

圖像預(yù)處理過程具體實現(xiàn)步驟如下：

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

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

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

2 算法流程

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

2.1 傳統(tǒng)的SIFT特征匹配算法

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

傳統(tǒng)的SIFT算法具體實現(xiàn)步驟如下。

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

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

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

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

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

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

2.2 改進的預(yù)檢驗策略

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

2.2.1 預(yù)檢驗策略聚類法初次篩選

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

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

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

式中：t為鄰域閾值（依據(jù)經(jīng)驗值本文取0.02）。

具體預(yù)檢驗策略實現(xiàn)步驟如下：

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

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

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

2.2.2 預(yù)檢驗策略視差梯度法二次篩選

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

特征3 視差梯度Gd為

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

具體預(yù)檢驗策略實現(xiàn)步驟如下：

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

[1] 張 琳，褚龍現(xiàn). 基于全局拼接的船舶圖像拼接算法研究[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]張春田，蘇育挺，張 靜. 數(shù)字圖像壓縮編碼[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]. 計算機與應(yīng)用化學，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-），男，湖南常德人，湖南工業(yè)大學碩士生，主要研究方向為嵌入式系統(tǒng)，

E-mail ：1525127621@qq.com

10.3969/j.issn.1673-9833.2014.01.015