焦麗龍，韓 燮，李定主

（1.中北大學 計算機與控制工程學院，山西 太原030051；2.北方自動化控制研究所，山西 太原030051）

0 引 言

圖像拼接技術(shù)正廣泛應(yīng)用于計算機圖形圖像處理、醫(yī)學圖像和虛擬現(xiàn)實等領(lǐng)域，關(guān)鍵技術(shù)是配準和融合，配準是根據(jù)圖像之間重疊區(qū)的一致性求出圖像之間的投影變換，融合［1］是實現(xiàn)無縫拼接。

目前，國內(nèi)外已經(jīng)提出了很多種圖像拼接方法，一般分為基于區(qū)域［2］和基于特征［3，4］的方法。其中，基于區(qū)域的方法往往由于亮度、對比度的不同導(dǎo)致拼接失敗，而基于特征方法的匹配效果相對穩(wěn)定，并且運算效率高。其中，SIFT［5］算法是目前研究最多、應(yīng)用最廣泛的一種。但是該算法僅利用了局部鄰域信息，所以當待匹配圖像有大量的相似結(jié)構(gòu)時，相似結(jié)構(gòu)中的點極易發(fā)生誤匹配。目前剔除誤匹配點對的主要方法是采用極幾何約束和迭代求精。然而用傳統(tǒng)的RANSAC［6］算法效率很低，特別是當匹配特征點對的 “內(nèi)點”（準確匹配點）比例比較小時，會直接影響到拼接算法的效率。文獻［7］提出的基于中值濾波的特征點對匹配算法，不能完全剔除誤匹配點，且執(zhí)行效率較低。文獻［8］提出用中值濾波檢測RANSAC 的初始迭代特征點對，該方法沒有考慮剔除誤匹配點，對RANSAC的執(zhí)行效率沒有實質(zhì)的改進。本文針對誤匹配造成內(nèi)點比例低時，RANSAC算法效率低、配準不穩(wěn)定的問題，提出了一種新的方法預(yù)篩粗匹配點對，再使用RANSAC算法提純，來提高算法效率和配準穩(wěn)定性。圖像融合部分，采用加權(quán)平均算法來解決因曝光參數(shù)不同而存在的亮度差異。

1 SIFT特征點提取

1.1 SIFT算法介紹

SIFT 算法于1999年首次被Lowe提出（SIFT 算法定義請參見文獻［9］），該算法提取的特征具有平移、縮放、旋轉(zhuǎn)的不變性，并且對光照、仿射及投影的變化也有一定的魯棒性。

1.2 特征點提取

SIFT 算法是在不同的尺度空間上進行特征檢測，而高斯核具有線性、平移、旋轉(zhuǎn)不變性等特點，所以只有高斯核才可以構(gòu)成多尺度空間的核［10］。提取特征點的步驟：

（1）確定特征點。將一個圖像的尺度空間表示為L（x，y，），它是由一個可變尺度的高斯函數(shù)G（x，y，）和原始圖像I（x，y）的卷積產(chǎn)生的，即

其中

在圖像的二維平面空間和DoG（difference－of－Gaussian）尺度空間中同時檢測局部極值作為特征點，使得特征點具有良好的獨特性和穩(wěn)定性。將待檢測的點與其所在層的點比較，如果是極值，則該點作為SIFT 的候選點。DoG 的響應(yīng)值圖像D（x，y，）是兩個相鄰高斯尺度空間的圖像相減得到的，其具有計算簡單的特點，是LoG（Laplacian－of－Gaussian）的近似。其中

式中：k——兩相鄰尺度空間倍數(shù)的常數(shù)。

檢測D（x，y，）的局部極值。每個采樣點都要與其同尺度的8個相鄰點和尺度中相鄰圖像的18 個相鄰點進行比較，把找到的極值點作為侯選特征點提取出來。通過尺度空間DoG 函數(shù)的曲線擬合和Hessian 矩陣方法去除不穩(wěn)定的點。

（2）為特征點分配主方向。用L（x，y）表示圖像，則圖像中點（x，y）處的幅角m（x，y）和幅值θ（x，y）的計算公式如下

對圖像中的每個特征點分別用式（4）和式（5）計算，然后使用直方圖統(tǒng)計該特征點的幅角和幅值，峰值就是該特征點的主方向。

2 特征點匹配與篩選

圖像的SIFT 特征點提取后，從待匹配圖像中選擇一個特征點，采用優(yōu)先k－d樹［11］從基準圖像中查找與該點歐氏距離最近的前兩個特征點，從而得到距離最近的與距離次近的比值，若比值小于給定的閾值，則認為距離最近的點為匹配點。歐氏距離計算公式

2.1 傳統(tǒng)的RANSAC算法

采用歐氏距離比值匹配的粗匹配點對包含大量誤匹配。為了增強算法的魯棒性，使用經(jīng)典的RANSAC 算法剔除誤匹配。該算法的原理是：隨機選擇n個樣本估計模型參數(shù)，再利用得到的模型計算，把小于閾值的匹配點作為內(nèi)點。重復(fù)C 次以上過程，選擇包含內(nèi)點最多的點集計算出準確的模型參數(shù)。

其中估計次數(shù)C 是影響算法效率的主要參數(shù)，計算公式

式（7）表示，經(jīng)過C 次至少有一次估計中的所有數(shù)據(jù)點都是內(nèi)點的概率是p。其中，w 為內(nèi)點概率，n 為確定模型參數(shù)的最少點數(shù)。

RANSAC算法能夠剔除誤匹配點對，并且實現(xiàn)簡單，因此在圖像處理中到了廣泛應(yīng)用。但是該算法在內(nèi)點概率w 很小時，估計次數(shù)高達567 次，導(dǎo)致其運算效率低下。該算法的估計次數(shù)C 與集合中內(nèi)點比例關(guān)系見表1。

表1 估計次數(shù)C 與集合中內(nèi)點比例關(guān)系

因此本文提出添加約束的方法預(yù)篩選粗匹配點對，提高內(nèi)點的比例，大大減少估計次數(shù)，來提高RANSAC 算法的運算效率。

2.2 改進的RANSAC算法

針對傳統(tǒng)的RANSAC 算法，內(nèi)點的概率w 很小時，估計次數(shù)高，導(dǎo)致算法運算效率低的問題，在運用RANSAC算法提純前，采用分類分析統(tǒng)計技術(shù)，根據(jù)相鄰匹配點對的特征點距離大致相等的特性對其進行篩選。圖像A 和圖像B 表示待匹配的圖像，根據(jù)式（8）計算特征點對距離差，設(shè)置閥值υ進行篩選

式中：aij、bij——圖像A、圖像B 的第i個和第j 個特征點之間的距離。特征點分別取自圖像A 和圖像B 的粗匹配點集合m＝（m1，m2，…，mp）和n＝（n1，n2，…，np）。

算法具體可分以下4個步驟：

（2）剔除誤匹配點對。求出其余所有點對與4 對正確點對的距離，然后與閥值υ進行比較，并統(tǒng)計出小于閥值υ的次數(shù)，將次數(shù)小于3次的匹配點對剔除。

（3）使用RANSAC 算法對篩選出的特征點對進行提純，求解變換矩陣。

（4）根據(jù)變換矩陣，完成統(tǒng)一坐標變換。

2.3 誤匹配點剔除算法步驟

Algorithm：SelectCorrectPair

Input：T＝｛（Mij，Nij），i，j＝1，2，…，p，j≠i｝

Output：P＝｛pi，i＝1，2，…，t，t≤p｝

1.Initialization：O＝｛oi，i＝1，2，3，4｝count＝0num＝0

2.if｜Mij－Nij｜＜υand count＜4then

3.num＝num＋1

5.count＝count＋1

6.oi＝i

7.end while

8.num＝0

9.end if

10.if｜Mjoi－Njoi｜＜υthen

11.count＝count＋1

12.while count＞2

13.pi＝j(luò)

14.end while

15.count＝0

16.end if

17.return P

算法的輸入是兩個圖像的特征點對的距離差集合，輸出為正確匹配點對在粗匹配點對中的序號。先將距離與閥值的比較找到4對正確點對，然后求出其它點對與這4對正確點對的距離集合，再將距離集合與閥值比較，如果同一點對與大于2對正確點對的距離小于閥值，則該點對被確定為正確匹配點對。

2.4 求解變換矩陣

將兩幅圖像之間的變換矩陣表示為H，設(shè)m（i，j），n（i′，j′）是正確匹配的點對。經(jīng)過齊次坐標變換，得到H的求解公式

根據(jù)式（9），理論上只需4組數(shù)據(jù)便可計算出變換矩陣的8個參數(shù)。然后將待拼接圖像根據(jù)所求的變換矩陣轉(zhuǎn)換，完成統(tǒng)一坐標變換。

2.5 融合部分

圖像拼接后往往因為兩張圖像的曝光參數(shù)不同而產(chǎn)生明顯的拼接線，本文采用加權(quán)平均算法來處理拼接線。設(shè)A（i，j），B（i，j）是待拼接的兩張圖，重疊區(qū)域圖像的像素C（i，j）的計算公式為

其中 ＝（i2－i）／（i2－i1），i1＜i＜i2。i1，i2分別是重疊區(qū)域x軸的最小和最大值。

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

實驗平臺為Windows XP系統(tǒng)，1.8GHz主頻，2GB內(nèi)存，利用Matlab R2012b編程進行實驗。實驗數(shù)據(jù)來源于在校園內(nèi)拍攝的22組800×1066分辨率的照片。實驗的算法流程如圖1所示。

圖1 實驗算法整體流程

圖2（a）（大小已放縮）是22 組照片中的1 組照片的原圖，圖2（b）是SIFT 算法提取圖片的特征，圖2（c）是特征點對篩選前后匹配對比，圖2（d）是最后的效果圖。

統(tǒng)計結(jié)果見表2，從表2中可以看出，預(yù)篩選后迭代特征點對減少了68.9%，耗時減少了59.9%。篩選前后匹配點對對數(shù)對比如圖3（a）所示，原算法與改進算法耗時對比如圖3（b）所示。

圖2 原圖、提出特征點圖和匹配特征點對比圖及最后效果

表2 統(tǒng)計結(jié)果

表2中平均運行時間＝運行總時間／總組數(shù)，平均迭代特征點對＝迭代總對數(shù)／總組數(shù)。

實驗結(jié)果表明：采用分類統(tǒng)計技術(shù)添加約束條件，對粗匹配點對進行外點剔除，有效提高了內(nèi)點的概率，從而減少了RANSAC 算法的估計次數(shù)，提高了算法的運行效率，拼接效果較好；加權(quán)平均算法處理拼接線，較好地解決了因曝光參數(shù)不同而存在的亮度差異。

4 結(jié)束語

圖3 優(yōu)化前后特征點對數(shù)和算法耗時對比

本文通過SIFT 算法提取圖像的特征點，在特征點匹配階段添加約束條件剔除誤匹配點對，提高了內(nèi)點的概率，有效減少了RANSAC算法的估計次數(shù)，得到穩(wěn)定的變換矩陣，用加權(quán)平均算法實現(xiàn)拼接圖像融合。提高了算法的效率和配準精度。實驗結(jié)果證明，該算法對視差和光照變化較大的圖像拼接效果較好，但是對于實時拼接的應(yīng)用，該算法還有待進一步完善。

［1］ZHANG Ruijuan.Study on the theory and algorithm of image registration ［D］.Xi’an：Xidian University，2009 （in Chinese）.［張銳娟.圖像配準及算法研究 ［D］.西安：西安電子科技大學，2009.］

［2］Bay H，Ess A，Tuytelaars T，et al.Speeded－up robust features（SURF） ［J］.Computer Vision and Image Understanding，2008，110 （3）：346－359.

［3］Zheng Zhibin，Ye Zhongfu.Image registration algorithm based on phase－correlation ［J］.Journal of Data Acquisition and Processing，2006，21 （4）：444－449.

［4］Guizar－Sicairos M，Thurman ST，F(xiàn)ienup J R.Efficient subpixel image registration algorithms［J］.Optics Letters，2008，33 （2）：156－158.

［5］Brown M，Lowe D G.Automatic panoramic image stitching using invariant features［J］.International Journal of Computer Vision，2007，4 （1）：59－73.

［6］LIU Kun，GE Junfeng，LUO Yupin，et al.Probability guided random sample consensus［J］.Journal of Computer－Aided Design and Computer Graphics，2009，21 （5）：657－662 （in Chinese）.［劉坤，葛俊鋒，羅予頻，等.概率引導(dǎo)的隨機采樣一致性算法 ［J］.計算機輔助設(shè)計與圖形學學報，2009，21（5）：657－662.］

［7］ZOU Beiji，RUAN Peng，XIANG Yao.An exact match automatic panorama stitching algorithm ［J］.Computer Engineering and Science，2010，32 （8）：60－63 （in Chinese）. ［鄒北驥，阮鵬，向遙.一種精確匹配的全景圖自動拼接算法 ［J］.計算機工程與科學，2010，32 （8）：60－63.］

［8］FANG Xianyong，ZHANG Mingmin，PAN Zhigeng，et al.A new method of manifold mosaic for large displacement images［J］.Journal of Computer Science and Technology，2006，21（2）：218－223.

［9］WANG Yongming，WANG Guijin.Image local invariant features and description ［M］.Beijing：National Defense Industry Press，2010 （in Chinese）.［王永明，王貴錦，圖像局部不變性特征與描述 ［M］.北京：國防工業(yè)出版社，2010.］

［10］ZHU Licheng，YAO Minghai.Object matching algorithm based on SIFT and identification ［J］.Mechanical and Electrical Engineering，2009，26 （4）：73－75 （in Chinese）.［朱利成，姚明海.基于SIFT 算法的目標匹配和識別 ［J］.機電工程，2009，26 （4）：73－75.］

［11］LIN Lujun，SUN Lingling，LI Xungen，et al.An improved template matching based microscopic cell image mosaic algorithm ［J］.computer software and application，2010，27（1）：108－110 （in Chinese）. ［林陸軍，孫 玲 玲，李 訓 根，等.一種改進的基于模板匹配的顯微細胞圖像拼接算法 ［J］.計算機應(yīng)用與軟件，2010，27 （1）：108－110.］