武岫緣，龍永新，高總總

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

基于SIFT-ACO的圖像拼接算法

武岫緣，龍永新，高總總

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

針對(duì)具有一定旋轉(zhuǎn)角度的多幅圖像拼接問(wèn)題，提出了一種基于SIFT-ACO的圖像拼接算法。對(duì)拼接圖像進(jìn)行預(yù)處理后，用SIFT算法提取圖像特征，將經(jīng)典的生物智能優(yōu)化算法ACO加入到圖像配準(zhǔn)中，對(duì)圖像特征點(diǎn)進(jìn)行配準(zhǔn)，最后將多幅圖像融合，得到一幅寬視角、無(wú)縫、高精度的圖像。對(duì)多組不同角度拍攝的圖像進(jìn)行拼接試驗(yàn)。試驗(yàn)結(jié)果表明：在不影響整體視覺(jué)效果的前提下，該算法能有效地提高圖像拼接精度。

圖像拼接；蟻群算法；圖像配準(zhǔn)

1 相關(guān)研究

圖像拼接是計(jì)算機(jī)視覺(jué)領(lǐng)域研究最早和最廣泛的方向之一，也是遙感圖像處理、醫(yī)學(xué)圖像處理、3D視覺(jué)重建、虛擬現(xiàn)實(shí)等領(lǐng)域的研究熱點(diǎn)[1]。圖像拼接技術(shù)能將多幅有重疊部分的圖像拼接成一幅寬視角、無(wú)縫、高分辨率的圖像，以滿足人們大視野視覺(jué)的需求[2]。而待拼接的圖像可能是在不同時(shí)間、不同角度、不同光照強(qiáng)度、不同分辨率或者不同傳感器條件下所拍攝，因此，圖像之間會(huì)存在差異。如何消除這些差異，使拼接后的圖像能自然平滑過(guò)渡，是圖像拼接的關(guān)鍵。國(guó)內(nèi)外學(xué)者已提出了多種圖像拼接算法，目的是使圖像拼接的速度和精度達(dá)到最優(yōu)的折中。

圖像拼接通常分為圖像預(yù)處理、特征提取、圖像配準(zhǔn)、圖像融合4個(gè)步驟。其中，圖像配準(zhǔn)是圖

綜上所述，本文提出了尺度不變特征變換匹配算法（scale-invariant feature transform，SIFT）和蟻群算法（ant colony optimization，ACO）相結(jié)合的圖像拼接算法。將群體智能的ACO算法引入到圖像拼接中，能有效地提高圖像配準(zhǔn)精度。經(jīng)過(guò)大量的試驗(yàn)證明，此算法對(duì)旋轉(zhuǎn)、平移、縮放、仿射變換、尺度、亮度等能保持一定的不變性，對(duì)噪聲也能保持較好的穩(wěn)定性，雖然稍微增加了拼接時(shí)間，但是提高了圖像配準(zhǔn)的精度。

2 SIFT-ACO算法介紹

對(duì)在同一水平面拍攝，但有部分重疊的多幅圖像進(jìn)行拼接的方法已非常成熟，且有些軟件已具有這種圖像拼接的功能。但對(duì)有一定旋轉(zhuǎn)角度的圖像進(jìn)行拼接時(shí)，現(xiàn)有的方法存在實(shí)時(shí)性差或精度低的缺點(diǎn)，因此，本課題組提出了將蟻群算法應(yīng)用到圖像配準(zhǔn)中，以提高對(duì)此類圖像拼接的精度。

2.1 圖像預(yù)處理

獲取圖像的過(guò)程中，會(huì)出現(xiàn)一些不確定、不穩(wěn)定的因素，如：光照變化、焦距調(diào)節(jié)、圖像變形等，因此，拍攝的圖像會(huì)存在不同程度的差異，這導(dǎo)致了視覺(jué)差異，且對(duì)圖像拼接也造成了困難[5-6]。因此，圖像拼接前，需要對(duì)其進(jìn)行預(yù)處理，如：幾何校正、統(tǒng)一坐標(biāo)系、去噪等，目的是減少配準(zhǔn)的難度，提高配準(zhǔn)和拼接的速度和精度。圖1為2幅有重疊區(qū)域的原始圖像，圖2是經(jīng)過(guò)預(yù)處理后的圖像。

圖1 原始圖像Fig.1 Original image

圖2 預(yù)處理后的圖像Fig.2 The preprocessed image

2.2 SIFT算法特征提取

SIFT算法，是一種穩(wěn)健的基于特征點(diǎn)的圖像配準(zhǔn)算法，處理發(fā)生了旋轉(zhuǎn)、平移、尺度、視角、仿射變換、光照等變化的圖像，具有一定的不變性和魯棒性[7]。該算法的主要思想是，通過(guò)高斯差分函數(shù)將圖像分成不同的尺度空間，在不同的尺度空間檢測(cè)極值點(diǎn)，去除噪聲點(diǎn)和邊緣點(diǎn)后，對(duì)感興趣的特征點(diǎn)進(jìn)行準(zhǔn)確定位，用特征向量描述符對(duì)特征點(diǎn)進(jìn)行描述。這為下一步對(duì)圖像的特征點(diǎn)進(jìn)行高質(zhì)量地匹配打下基礎(chǔ)。SIFT算法的主要步驟如下。

1）產(chǎn)生圖像尺度空間，檢測(cè)圖像尺度空間的特征點(diǎn)

先通過(guò)可變尺度的二維高斯核函數(shù)G(x, y, )與圖像I(x, y)進(jìn)行卷積，產(chǎn)生圖像尺度空間L(x, y, )，再用尺度空間對(duì)圖像進(jìn)行高斯濾波，即

然后，將2個(gè)相鄰高斯尺度空間的圖像相減，得到DOG圖像的響應(yīng)值圖像，即

k為常數(shù)，表示2個(gè)相鄰尺度之間的間隔；

2）確定特征點(diǎn)方向，生成特征描述符

以特征點(diǎn)為中心，取16×16的鄰域作為窗口，將采樣點(diǎn)與特征點(diǎn)的相對(duì)方向通過(guò)高斯加權(quán)后，歸入包含8個(gè)方向的直方圖，繪制每個(gè)梯度方向的累加值，形成一個(gè)種子點(diǎn)。一個(gè)特征點(diǎn)由4×4共16個(gè)種子點(diǎn)組成，特征描述子由所有子塊的梯度方向直方圖構(gòu)成。因此，關(guān)鍵點(diǎn)描述符向量為128維。

對(duì)圖2中的2幅圖像進(jìn)行特征提取后，結(jié)果圖見(jiàn)圖3。

圖3 特征提取圖像Fig.3 The feature extraction image

通過(guò)以上方法，輸入的2幅圖像可以獲得SIFT特征點(diǎn)，每個(gè)特征點(diǎn)都包括唯一確定的位置、尺度和方向信息，利用這些信息再進(jìn)行特征匹配。

2.3 ACO特征匹配

傳統(tǒng)的SIFT算法中，描述子用128維向量表示，而一幅圖像有成千上萬(wàn)個(gè)描述子[8-9]，這種維度災(zāi)難極大地降低了配準(zhǔn)的速度。蟻群算法是一種用來(lái)在圖中尋找優(yōu)化路徑的算法，具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。研究結(jié)果顯示，蟻群算法的離散性和并行性特點(diǎn)適合處理離散的數(shù)字圖像，在求解復(fù)雜優(yōu)化問(wèn)題，特別是離散優(yōu)化問(wèn)題，該算法有獨(dú)特的優(yōu)越性。本文針對(duì)傳統(tǒng)的SIFT算法特征點(diǎn)匹配錯(cuò)誤率比較高的問(wèn)題，提出了將生物智能算法ACO運(yùn)用到圖像匹配中，可提高圖像匹配的準(zhǔn)確率。

ACO特征匹配原理如下。

自然界中螞蟻搜索食物過(guò)程是一個(gè)不斷聚類的過(guò)程，食物就是聚類中心。將SIFT算法提取的特征點(diǎn)Xi（i=1, 2,…, n）看作一個(gè)螞蟻，將每一個(gè)螞蟻在不同時(shí)刻的觀測(cè)數(shù)據(jù)視為點(diǎn)的坐標(biāo)，螞蟻分別聚集到 j個(gè)聚類中心X'j（j=1, 2,…, m），建立城市坐標(biāo)模型；然后構(gòu)造一種灰色距離關(guān)聯(lián)度Di,j，將灰色關(guān)聯(lián)度作為相似性函數(shù)，從距離空間的角度反映系統(tǒng)因素間的關(guān)聯(lián)性，即

假設(shè)算法中的螞蟻具有一定的記憶能力，能根據(jù) 2 幅待拼接圖像的灰色關(guān)聯(lián)度選擇轉(zhuǎn)移方向，從而引導(dǎo)螞蟻向灰色關(guān)聯(lián)度最大值的方向移動(dòng)。在圖像拼接過(guò)程中，將圖像 A 中的窗口在 圖像B中搜索迭代的過(guò)程看成是“i只螞蟻的城市模型”，從而使得螞蟻可以在這個(gè)模型圖上進(jìn)行爬行，并且保證了螞蟻爬行所獲得的每個(gè)哈密頓路都對(duì)應(yīng)一個(gè)灰色關(guān)聯(lián)度最大的組合。

螞蟻在運(yùn)動(dòng)過(guò)程中，根據(jù)個(gè)體路徑上的信息量決定其轉(zhuǎn)移方向。用禁忌表tabuk（k=1, 2,…, q）來(lái)記錄螞蟻當(dāng)前走過(guò)的城市。在搜索過(guò)程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來(lái)計(jì)算狀態(tài)轉(zhuǎn)移概率，即：

式中：allowedk為螞蟻k下一步允許選擇的城市集；

最后，利用RANSAC算法（randomsampleconsensus）消除誤匹配，具體過(guò)程如下：

1）從匹配點(diǎn)集中隨機(jī)反復(fù)采樣一組數(shù)據(jù)，每一組抽樣的樣本數(shù)為估算模型所需最小數(shù)據(jù)量，計(jì)算該抽樣本所對(duì)應(yīng)的模型，模型參數(shù)為4對(duì)匹配點(diǎn)。

2）進(jìn)行全數(shù)據(jù)檢驗(yàn)，統(tǒng)計(jì)滿足該模型的內(nèi)點(diǎn)數(shù)量，計(jì)算內(nèi)點(diǎn)變換點(diǎn)和內(nèi)點(diǎn)匹配點(diǎn)的歐氏距離之和，距離和公式為

3）根據(jù)內(nèi)點(diǎn)數(shù)量和歐氏距離和來(lái)選擇模型的參數(shù)。

4）重復(fù)步驟1），2），直到選出滿足評(píng)選標(biāo)準(zhǔn)的模型，找出模型對(duì)應(yīng)的內(nèi)點(diǎn)，最終計(jì)算出模型參數(shù)。

2.4 圖像融合

圖像拼接之后，拼接的部分會(huì)出現(xiàn)一條拼接縫。本文通過(guò)對(duì)漸入漸出法的研究，提出了一種基于反正切函數(shù)的圖像整體勻色方法。該方法針對(duì)傳統(tǒng)整體勻色方法的缺點(diǎn)進(jìn)行了改進(jìn)。利用反正切函數(shù)作為平滑函數(shù)曲線，通過(guò)設(shè)置合適的權(quán)重，使拼接后的圖像像素改動(dòng)范圍減小，降低圖像的模糊度，使拼接后的圖像能夠最大限度地恢復(fù)到平滑自然過(guò)渡的效果。圖4為帶有拼接縫的圖像，圖5為圖像融合后的效果圖。

圖4 帶有拼接縫的圖像Fig.4 The seam image

圖5 融合圖像Fig.5 The image fusion

SIFT-ACO算法流程如圖6所示。

圖6 拼接流程圖Fig.6 The imag mosaic flowchart

3 試驗(yàn)結(jié)果分析

將SIFT算法、Harris角點(diǎn)檢測(cè)算法和本文算法，從圖像拼接速度和精度2個(gè)方面進(jìn)行對(duì)比，試驗(yàn)結(jié)果如表1所示。本文中的RANSAC算法參數(shù)設(shè)為：最小距離閾值d=1.416，迭代次數(shù)N=50。

表1 3種算法的試驗(yàn)數(shù)據(jù)Table1 The experimental data of three algorithms

從表1可以看出，本文算法雖然增加了圖像拼接時(shí)間，但有效地提高了圖像拼接的精度。

4 結(jié)語(yǔ)

目前，全景圖是通過(guò)多幅相鄰的圖像拼接而成，因此，全景圖生成技術(shù)的關(guān)鍵是相鄰圖像的配準(zhǔn)及拼接。本文提出了將SIFT算法和ACO算法相結(jié)合的方法，來(lái)實(shí)現(xiàn)圖像拼接。本文方法是，先通過(guò)SIFI算法檢測(cè)出圖像的特征點(diǎn)，再通過(guò)ACO算法實(shí)現(xiàn)特征匹配，通過(guò)漸入漸出的方法進(jìn)行圖像融合。最后，將本文算法與SIFT算法、Harris算法從圖像拼接的時(shí)間和精度進(jìn)行了對(duì)比，試驗(yàn)結(jié)果表明，與其他2種算法相比，本文算法的拼接精度更高。

[1]Brown L G. A Survey of Image Registration Techniques[J].ACM Computing Surveys，1992，24(4)：325-376.

[2] 林小平，周石琳，張官亮，等. 一種基于蟻群算法和互信息測(cè)度的圖像拼接技術(shù)[J]. 重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)，2013，27(1)：76-81. Lin Xiaoping，Zhou Shilin，Zhang Guanliang，et al. A Image Mosaic Technology Based on Ant Colony Algorithm and Mutual Information Measure[J]. Journal of Chongqing University of Technology：Natural Science，2013，27(1)：76-81.

[3] 雷 震，李 東，吳玲達(dá). 基于粒子群優(yōu)化和互信息量的全景圖拼接算法[J]. 計(jì)算機(jī)仿真，2009，26(4)：256-358，347. Lei Zhen，Li Dong，Wu Lingda. A Mosaic Algorithm of Panoramic Image Based on Particle Swarm Optimization and Mutual Information[J]. Computer Simulation，2009，26(4)：256-358，347.

[4] 馮雪芳. 基于互信息的圖像配準(zhǔn)技術(shù)的研究[D]. 無(wú)錫：江南大學(xué)，2012. Feng Xuefang. Research on Image Registration Technology Based on Mutual Information[D]. Wuxi：Jiangnan University，2012.

[5] 魏雪麗，張 樺，馬艷潔，等. 基于最大互信息的圖像拼接優(yōu)化算法[J]. 光電子·激光，2009，20(10)：1399-1402. Wei Xueli，Zhang Hua，Ma Yanjie，et al. A Optimization Algorithm of Image Mosaic Based on Maximum Mutual Information[J]. Journal of Optoelectronic·Laser，2009，20(10)：1399-1402.

[6] Maes F，Collignon A，Vandermeulen D，et al. Multimodality Image Registration by Maximization of Mutual Information[J]. IEEE Transactions on Medical Imaging，1997，16(2)：187-198.

[7] 程 旭， 珺李擬 ，吳鎮(zhèn)揚(yáng). 基于SIFT特征的粒子群優(yōu)化的視覺(jué)跟蹤算法[J]. 重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，24(5)：652-656. Cheng Xu，Li Nijun，Wu Zhenyang. Visual Tracking Algorithm with Particle Swarm Optimization Based on SIFT Feature[J]. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition，2012，24 (5)：652-656.

[8]周軍太，龍永紅. 一種改進(jìn)SURF 算法的圖像配準(zhǔn)[J]. 湖南工業(yè)大學(xué)學(xué)報(bào)，2011，25(2) ：96-99. Zhou Juntai，Long Yonghong. An Improved SURF Algorithm of Image Registration[J]. Journal of Hunan University of Technology，2011，25(2) ：96-99.

[9] 蔣 鴻，胡永祥. 非線性擴(kuò)散圖像配準(zhǔn)[J]. 湖南工業(yè)大學(xué)學(xué)報(bào)，2011，25(5)：87-91. Jiang Hong，Hu Yongxiang. Nonlinear Diffusion Image Registration[J]. Journal of Hunan University of Technology，2011，25(5)：87-91.

[10]王維真，熊義軍，魏開(kāi)平，等. 基于粒子群算法的灰度相關(guān)圖像匹配技術(shù)[J]. 計(jì)算機(jī)工程與應(yīng)用，2010，46(12)：169-171. Wang Weizhen，Xiong Yijun，Wei Kaiping，et al. Gray Intensity Correlated Image-Matching Technology Based on PSO[J]. Computer Engineering and Applications，2010，46(12)：169-171.

（責(zé)任編輯：鄧 彬）

Image Mosaic Optimization Algorithm Based on SIFT-ACO

Wu Xiuyuan，Long Yongxin，Gao Zongzong
（School of Computer and Communication，Hunan University of Technology， Zhuzhou Hunan 412007，China）

For problems of multiple images stitching of certain rotation angle, puts forward an image mosaic optimization algorithm based on SIFT-ACO. After the mosaic image preprocessing, the algorithm uses SIFT algorithm to extract the image features, adds classic intelligent optimization algorithm to image registration and makes image feature points registration, at last fuses multiple images and obtains a wide viewing angle, seamless and high precision image. The experimental result of image mosaic of different angles indicates that the algorithm can improve the accuracy of image matching effectively without affecting the overall visual effect.

image mosaic；ant colony algorithm；image registration

TP391

：A

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

2013-10-07

國(guó)家自然科學(xué)基金資助項(xiàng)目（61170102），湖南省自然科學(xué)基金資助項(xiàng)目（11JJ3070），湖南省教育廳基金資助項(xiàng)目（12A039）

武岫緣（1988-），女，河北唐山人，湖南工業(yè)大學(xué)碩士生，主要研究方向?yàn)閳D像拼接等，像拼接的核心，配準(zhǔn)的精度直接影響后續(xù)的圖像處理過(guò)程，所以，圖像配準(zhǔn)非常重要[3-4]。圖像配準(zhǔn)的算法大致分為3種：1）基于像素的圖像配準(zhǔn)。由于圖像的像素?cái)?shù)量巨大，該方法的處理速度很慢。2）基于特征的圖像配準(zhǔn)。與第一種方法相比，特征點(diǎn)數(shù)量大大減少，配準(zhǔn)速度有所提高。3）基于變換域的圖像配準(zhǔn)。該方法的計(jì)算復(fù)雜，計(jì)算量大，只能針對(duì)特定圖像?？梢?jiàn)，基于特征的圖像匹配方法具有更大的優(yōu)勢(shì)。為了滿足實(shí)時(shí)性要求，該方法的匹配速度還有待提高。

E-mail：851104011@qq.com

10.3969/j.issn.1673-9833.2014.01.016