超像素SIFT特征航拍地圖拼接研究*

王 萍， 王 港

(天津大學(xué) 電氣與自動化工程學(xué)院，天津 300072)

?

超像素SIFT特征航拍地圖拼接研究*

王 萍， 王 港

(天津大學(xué) 電氣與自動化工程學(xué)院，天津 300072)

為解決航拍地圖拼接計算量大、內(nèi)容復(fù)雜多變的問題，提出使用超像素尺度不變特征變換(SIFT)特征進(jìn)行地圖拼接。首先利用近鄰傳播(AP)算法改進(jìn)簡單線性迭代聚類(SLIC)算法實現(xiàn)超像素自適應(yīng)分割。然后在引導(dǎo)信息下對少數(shù)超像素提取SIFT特征，進(jìn)行SIFT特征匹配。最后在線生成監(jiān)督機制，在隨機抽樣一致性(RANSAC)算法配合下，得到少而精的匹配點，計算變換矩陣融合圖像，實現(xiàn)圖像拼接。實驗結(jié)果顯示：對于較高分辨率的圖像,該算法與單純SIFT拼接算法相比，在計算時間和拼接質(zhì)量上都顯示出較大的優(yōu)勢。

自適應(yīng)近鄰傳播(AP)； 超像素； 尺度不變特征變換(SIFT)； 隨機抽樣一致性； 地圖拼接

0 引 言

航拍地圖由無人機等飛行器在高空拍攝得到的。由于無人機飛行的高度和相機焦距的限制，單幅航拍地圖很難包含目標(biāo)的所有內(nèi)容，因此，航拍地圖拼接成為航拍地圖處理的關(guān)鍵問題。關(guān)于圖像拼接的方法可以分為基于像素的方法和基于特征的方法。在基于特征的方法中，尺度不變特征變換(scale invariant feature transform,SIFT)是目前研究最多、應(yīng)用最廣的一種特征[1]。角點檢測提取SIFT特征進(jìn)行圖像拼接[2]和加速健壯特征(speed-up robust features,SURF)算法[3]。但文獻(xiàn)[1]方法計算量偏大；文獻(xiàn)[2]方法去噪和幾何矯正能力對低對比度圖像不敏感；文獻(xiàn)[3]方法的高效率卻犧牲拼接準(zhǔn)確率。另外，航拍地圖通常具有分辨率高、富含相似結(jié)構(gòu)的特點，致使圖像配準(zhǔn)耗時較大且易發(fā)生誤匹配。因此，需要對提取的匹配點進(jìn)行篩選[4]。

本文首先通過坐標(biāo)和顏色聯(lián)合空間下的近鄰傳播(affinity propagation,AP)算法[5]進(jìn)行自適應(yīng)超像素分割，利用屬于超像素的SIFT特征集[6]進(jìn)行匹配區(qū)域的篩選，提出有監(jiān)督隨機抽樣一致(random sample consensus，RANSAC)算法進(jìn)行匹配點和匹配超像素精選，獲得可靠的匹配點集，從而得到變換矩陣實現(xiàn)圖像拼接。本文通過基于超像素的區(qū)域匹配的思想，減少區(qū)域匹配計算量、增加拼接準(zhǔn)確度。

1 圖像分割與特征獲取

圖像拼接是局部圖像匹配問題。將SIFT特征的全局匹配合理地收縮到有限的范圍之內(nèi)，將各SIFT特征的“單兵作戰(zhàn)”改為來自局部區(qū)域的“小集團作戰(zhàn)”是本文方法的基本思想。為此，首先需要對圖像進(jìn)行一種比較合理的劃分(圖像分割)。

1.1 自適應(yīng)超像素分割

超像素[7]是指圖像中局部區(qū)域內(nèi)連通的、特征相近(亮度、顏色、紋理、目標(biāo)等)的像素集合。顯然，基于超像素的區(qū)域劃分是滿足本文圖像分割需求的合適方法。超像素分割常用簡單線性迭代聚類(simple linear iterative clustering，SLIC)[8],但其超像素個數(shù)需要人為確定[9]，為此，本文利用AP算法[5]改進(jìn)SLIC，實現(xiàn)超像素的自適應(yīng)分割。以下給出本文改進(jìn)的相似性測度的定義。

定義1：相似性測度

(1)

式中

(2)

(3)

(4)

定義2：吸引函數(shù)

r(i,k)=s(i,k)-maxk′≠k{a(i,k′)+s(i,k′)}

(5)

定義3：歸屬函數(shù)

(6)

1.2 提取超像素SIFT特征

在獲得的超像素上提取特征點用于接下來的匹配。本文選用SIFT特征[10～12]進(jìn)行局部區(qū)域描述。

2 圖像匹配與融合

2.1 引導(dǎo)信息的提取

由于SIFT特征的高維數(shù)，盲目配對計算耗時較長。首先從圖像中尋找有用的配對引導(dǎo)信息，具體做法如下：

i=1,2,…

(7)

式中 R(k),G(k),B(k)為區(qū)域內(nèi)像素k的三通道顏色分量，它們在整幅圖像內(nèi)的最大值和最小值為Rmax,Gmax,Bmax和Rmin,Gmin,Bmin，n為區(qū)域的像素點數(shù)。

(8)

2.2 基于k-d樹特征結(jié)構(gòu)的超像素匹配

SIFT特征匹配時間復(fù)雜度為o(n2)。k-d樹(k-dimensiontree)[13]使搜索最匹配特征的時間復(fù)雜度降低到o(nlgn)。

設(shè)超像素ωA(i)∈A和超像素ωB(j)∈B滿足引導(dǎo)條件(式(8)),則對特征SIFTpi∈ωA(i)的最佳匹配SIFTpj∈ωB(j)應(yīng)滿足主條件(式(9))和附加條件(式(10)),即

‖SIFTpi-SIFTpj‖=α0

(9)

‖SIFTpi-SIFTpj‖2/‖SIFTpi-SIFTqj‖2<β

(10)

式中 SIFTqj∈ωB(j)，且在ωB(j)的所有特征中，它與SIFTpi的歐氏距離僅大于α0。附加條件保證可靠性，閾值β越小，則匹配點對(pi,pj)越可靠。

用上述方法，對兩幅待拼接航拍地圖進(jìn)行基于超像素的特征匹配，得到的匹配結(jié)果經(jīng)人工核對存在少數(shù)誤匹配。

2.3 RANSAC匹配點精選

圖像A的超像素ωA(i)和圖像B的超像素ωB(j)之間形成含有少量的特征誤匹配點對，稱為異常數(shù)據(jù)。RANSAC[14]用于匹配超像素匹配點的精選。

2.4 有監(jiān)督條件下的超像素匹配對的收集

超像素是圖像中較小區(qū)域，需要使用2.2～2.3的方法將最佳超像素匹配對數(shù)擴大。將已獲得的最佳超像素匹配對信息轉(zhuǎn)化為監(jiān)督條件，以限定搜索。方法如下：

設(shè)圖像A的超像素ωA(i)獲得圖像B的最佳匹配超像素ωB(j)，則有：

1)選ωA(i)的四鄰域超像素，找到滿足式(8)且與ωB(j)相鄰的超像素，(可能不止一個)；

2)利用2.2和2.3方法確定新的最佳超像素匹配對；

3)將(ωA(i),ωB(j))作區(qū)域屏蔽，令新的超像素匹配對為(ωA(i),ωB(j))。如果最佳超像素匹配對數(shù)超過了設(shè)定的閾值(本文定為3)，則結(jié)束;否則,返回步驟(1)。

上述方法體現(xiàn)了基于超像素的小特征團隊思想。

2.5 圖像融合

建立兩幅圖像的坐標(biāo)轉(zhuǎn)換矩陣，實現(xiàn)圖像融合[15]。

3 圖像拼接測試

將本文算法和單純SIFT算法在拼接準(zhǔn)確率和拼接速度兩方面展開對比分析。測試平臺為Windows7，3.20GHz主頻，4GB內(nèi)存PC，利用Matlab2013b進(jìn)行編程測試。測試樣本由中國天津氣象局提供。測試內(nèi)容為拼接準(zhǔn)確率和拼接效率。

圖1～圖3列舉了三種類型航拍地圖拼接的情況?？梢钥闯觯喝N情況下本文算法得到了滿意的拼接結(jié)果，而單純SIFT算法在第三種情況下出現(xiàn)了錯配。

圖1 色差較小的橫向圖拼接Fig 1 Cross stitching of small color difference

圖2 色差較大的橫向圖拼接Fig 2 Cross stittching of large color difference

圖3 色差較小的縱向圖拼接Fig 3 Longitudinal splicing

表1給出了圖1～圖3圖像拼接過程中的部分主要參數(shù)，可以看出：與單純SIFT算法相比，本文算法提取的SIFT特征點數(shù)和匹配點數(shù)大幅度下降，加之本文算法增加超像素分割所用的時間開銷，總體拼接時間降低了近50%。同時，三對圖像拼接結(jié)果中，單純SIFT算法有一例出現(xiàn)了明顯拼接偏差。

表1 超像素SIFT拼接與單純SIFT拼接速度與準(zhǔn)確率對比

建立不同分辨率不同場景下的待拼接圖像測試樣本庫。運行算法，測試每一組的實驗結(jié)果。建立平均運算時間和最大運算時間隨分辨率的變化曲線，如圖4所示。

圖4 算法運算時間與分辨率的關(guān)系圖Fig 4 Relationship between computation time of algorithm and resolution

4 結(jié)束語

航拍地圖分辨率高，內(nèi)容復(fù)雜多變，需要有效且快速的算法進(jìn)行拼接處理。SIFT特征對航拍地圖拼接具有很好的應(yīng)用效果，但準(zhǔn)確率和計算效率都有待提高。本文提出了超像素SIFT拼接算法，利用有限的超像素上的SIFT特征實現(xiàn)航拍地圖的匹配和拼接。在超像素分割中，提出的將AP算法融入SLIC的AP-SLIC算法改善了其不能自適應(yīng)確定超像素數(shù)目的問題，并使用圖像顏色標(biāo)準(zhǔn)差自適應(yīng)調(diào)節(jié)顏色空間和坐標(biāo)空間的相互關(guān)系，使分割算法更加適應(yīng)內(nèi)容復(fù)雜多變的航拍地圖。匹配點篩選引入監(jiān)督機制。實驗表明：與單純SIFT算法相比，面對600×600及以上的圖像拼接問題，本文算法在計算時間和匹配準(zhǔn)確度上優(yōu)勢明顯。

[1] Brown M,Lowe D G.Recognising panoramas[C]∥Proceedings of The 9th IEEE International Conference on Computer Vision(ICCV),2003:1218.[2] Tao Z J,Huang H.Fundusimages mosaic based on improved Harris and SIFT algorithm[J].Computer Engineering and Design,2012,33(9):3507-3511.

[3] Bay H,Tuytelaars T,Van Gool L.Surf:Speeded up robust features[M].Berlin Heidelberg:Springer,2006:404-417.

[4] Fischler M A,Bolles R C.Random sample consensus:A paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM,1981,24(6):381-395.

[5] Frey B J,Dueck D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[7] Ren X,Malik J.Learning a classification model for segmenta-tion[C]∥2003 Proceedings of the Ninth IEEE International Conference on Computer Vision IEEE,2003:10-17.

[8] Achanta R,Shaji A,Smith K,et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(11):2274-2282.

[9] Achanta R,Shaji A,Smith K,et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(11):2274-2282.

[10] Lowe D G.Object recognition from local scale-invariant feature-s[C]∥1999 Proceedings of the Seventh IEEE International Conference on Computer Vision,IEEE,1999:1150-1157.

[11] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Com-puter Vision,2004,60(2):91-110.

[12] Harris C,Stephens M.A combined corner and edge detector[C]∥Alvey Vision Conference,1988:50.

[13] Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM,1975,18(9):509-517.

[14] Brown M,Lowe D G.Automatic panoramic im-age stitching using invariant features[J].International Journal of Computer Vision,2007,74(1):59-73.

[15] Hartley R,Zisserman A.Multiple view geometry in computer vision[M].Cambridge:Cambridge Uni-versity Press,2003:25-259.

王 萍 (1955-)，女，天津人,碩士,教授,主要從事模式識別方法及應(yīng)用,圖像理解,運動對象跟蹤等方面的研究工作。

王 港，通訊作者，E—mail:wanggg@tju.edu.cn。

Research on aerial image mosaic algorithm based on SIFT features of superpixels*

WANG Ping, WANG Gang

(School of Electrical and Automation Engineering,Tianjin University，Tianjin 300072,China)

In order to address dynamically changing contents and large computation in aerial image mosaic,propose a region-matching algorithm based on scale invariant feature transform(SIFT) features of superpixels.Firstly,improve a simple linear iterative clustering(SLIC) by affinity propagation(AP),and the method is used to accomplish adaptive superpixel segmentation; Next,a few superpixels are described with SIFT features to acquire coarse point matching under the guidance.Finally,supervision is obtained online to select more superpixels to be matched and random sample consensus(RANSAC) method is constructed so that aerial image mosaic is accomplished precisely.Experimental results demonstrate that,compared with SIFT mosaic algorithm in high resolution,the method greatly reduces computation time and improves quality of aerial image mosaic.

adaptive affinity propagation(AP); superpixel; scale invariant feature transform(SIFT); random sample consensus (RANSAC); aerial image mosaic

10.13873/J.1000—9787(2016)12—0017—03

2016—01—06

公益性行業(yè)(氣象)科研項目(GYHY200706004)；天津市自然科學(xué)基金資助項目(09JCYBJC07500)

TP 751.1

A

1000—9787(2016)12—0017—03