焦麗龍，韓 燮，李定主

（1.中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原030051；2.北方自動(dòng)化控制研究所，山西 太原030051）

0 引 言

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

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

1 SIFT特征點(diǎn)提取

1.1 SIFT算法介紹

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

1.2 特征點(diǎn)提取

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

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

其中

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

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

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

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

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

2 特征點(diǎn)匹配與篩選

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

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

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

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

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

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

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

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

2.2 改進(jìn)的RANSAC算法

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

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

算法具體可分以下4個(gè)步驟：

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

（3）使用RANSAC 算法對(duì)篩選出的特征點(diǎn)對(duì)進(jìn)行提純，求解變換矩陣。

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

2.3 誤匹配點(diǎn)剔除算法步驟

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

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

2.4 求解變換矩陣

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

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

2.5 融合部分

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

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

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

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

圖1 實(shí)驗(yàn)算法整體流程

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

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

圖2 原圖、提出特征點(diǎn)圖和匹配特征點(diǎn)對(duì)比圖及最后效果

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

表2中平均運(yùn)行時(shí)間＝運(yùn)行總時(shí)間／總組數(shù)，平均迭代特征點(diǎn)對(duì)＝迭代總對(duì)數(shù)／總組數(shù)。

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

4 結(jié)束語

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

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

［1］ZHANG Ruijuan.Study on the theory and algorithm of image registration ［D］.Xi’an：Xidian University，2009 （in Chinese）.［張銳娟.圖像配準(zhǔn)及算法研究 ［D］.西安：西安電子科技大學(xué)，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ī)采樣一致性算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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）. ［鄒北驥，阮鵬，向遙.一種精確匹配的全景圖自動(dòng)拼接算法 ［J］.計(jì)算機(jī)工程與科學(xué)，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 算法的目標(biāo)匹配和識(shí)別 ［J］.機(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）. ［林陸軍，孫 玲 玲，李 訓(xùn) 根，等.一種改進(jìn)的基于模板匹配的顯微細(xì)胞圖像拼接算法 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2010，27 （1）：108－110.］