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

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

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

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

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

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

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

0 引言

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

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

1 圖像預(yù)處理

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

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

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

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

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

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

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

1.2 量化和反量化

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

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

量化值計(jì)算公式如下：

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

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

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

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

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

2 算法流程

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

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

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

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

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

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

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

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

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

4）消除誤匹配特征點(diǎn)。關(guān)鍵點(diǎn)匹配并不能標(biāo)志算法結(jié)束，因?yàn)樵谄ヅ涞倪^程中存在著大量的誤匹配特征點(diǎn)。消除誤匹配特征點(diǎn)，就要使用RANSAC算法。

2.2 改進(jìn)的預(yù)檢驗(yàn)策略

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

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

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

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

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

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

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

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

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

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

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

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

特征3 視差梯度Gd為

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

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

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

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

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

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

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

選擇的實(shí)驗(yàn)平臺(tái)為Visual C++6.0，改進(jìn)圖像拼接算法過程圖如圖1所示。

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

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

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

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

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

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

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

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

表1 改進(jìn)算法與原算法對(duì)比Tabel1 The improved algorithm comparing with the original algorithm

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

4 結(jié)語

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

[1] 張 琳，褚龍現(xiàn). 基于全局拼接的船舶圖像拼接算法研究[J]. 計(jì)算機(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]. 北京：清華大學(xué)出版社，2006：68-70. Zhang Chuntian，Su Yuting，Zhang Jing. Digital Image Compression Coding[M]. Beijing：Tsinghua University Press，2006：68-70.

[5] 曹 楠，王 萍. 基于SIFT特征匹配的圖像無縫拼接算法[J]. 計(jì)算機(jī)與應(yīng)用化學(xué)，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]馬頌德，張正友. 計(jì)算機(jī)視覺[M]. 北京：北京科學(xué)出版社，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.

（責(zé)任編輯：申 劍）

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è)大學(xué)碩士生，主要研究方向?yàn)榍度胧较到y(tǒng)，

E-mail ：1525127621@qq.com

10.3969/j.issn.1673-9833.2014.01.015