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

王 萍， 王 港

(天津大学 电气与自动化工程学院，天津 300072)



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

王 萍， 王 港

(天津大学 电气与自动化工程学院，天津 300072)

为解决航拍地图拼接计算量大、内容复杂多变的问题，提出使用超像素尺度不变特征变换(SIFT)特征进行地图拼接。首先利用近邻传播(AP)算法改进简单线性迭代聚类(SLIC)算法实现超像素自适应分割。然后在引导信息下对少数超像素提取SIFT特征，进行SIFT特征匹配。最后在线生成监督机制，在随机抽样一致性(RANSAC)算法配合下，得到少而精的匹配点，计算变换矩阵融合图像，实现图像拼接。实验结果显示：对于较高分辨率的图像,该算法与单纯SIFT拼接算法相比，在计算时间和拼接质量上都显示出较大的优势。

自适应近邻传播(AP)； 超像素； 尺度不变特征变换(SIFT)； 随机抽样一致性； 地图拼接

0 引 言

航拍地图由无人机等飞行器在高空拍摄得到的。由于无人机飞行的高度和相机焦距的限制，单幅航拍地图很难包含目标的所有内容，因此，航拍地图拼接成为航拍地图处理的关键问题。关于图像拼接的方法可以分为基于像素的方法和基于特征的方法。在基于特征的方法中，尺度不变特征变换(scale invariant feature transform,SIFT)是目前研究最多、应用最广的一种特征[1]。角点检测提取SIFT特征进行图像拼接[2]和加速健壮特征(speed-up robust features,SURF)算法[3]。但文献[1]方法计算量偏大；文献[2]方法去噪和几何矫正能力对低对比度图像不敏感；文献[3]方法的高效率却牺牲拼接准确率。另外，航拍地图通常具有分辨率高、富含相似结构的特点，致使图像配准耗时较大且易发生误匹配。因此，需要对提取的匹配点进行筛选[4]。

本文首先通过坐标和颜色联合空间下的近邻传播(affinity propagation,AP)算法[5]进行自适应超像素分割，利用属于超像素的SIFT特征集[6]进行匹配区域的筛选，提出有监督随机抽样一致(random sample consensus，RANSAC)算法进行匹配点和匹配超像素精选，获得可靠的匹配点集，从而得到变换矩阵实现图像拼接。本文通过基于超像素的区域匹配的思想，减少区域匹配计算量、增加拼接准确度。

1 图像分割与特征获取

图像拼接是局部图像匹配问题。将SIFT特征的全局匹配合理地收缩到有限的范围之内，将各SIFT特征的“单兵作战”改为来自局部区域的“小集团作战”是本文方法的基本思想。为此，首先需要对图像进行一种比较合理的划分(图像分割)。

1.1 自适应超像素分割

超像素[7]是指图像中局部区域内连通的、特征相近(亮度、颜色、纹理、目标等)的像素集合。显然，基于超像素的区域划分是满足本文图像分割需求的合适方法。超像素分割常用简单线性迭代聚类(simple linear iterative clustering，SLIC)[8],但其超像素个数需要人为确定[9]，为此，本文利用AP算法[5]改进SLIC，实现超像素的自适应分割。以下给出本文改进的相似性测度的定义。

定义1：相似性测度

(1)

式中

(2)

(3)

(4)

定义2：吸引函数

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

(5)

定义3：归属函数

(6)

1.2 提取超像素SIFT特征

在获得的超像素上提取特征点用于接下来的匹配。本文选用SIFT特征[10～12]进行局部区域描述。

2 图像匹配与融合

2.1 引导信息的提取

由于SIFT特征的高维数，盲目配对计算耗时较长。首先从图像中寻找有用的配对引导信息，具体做法如下：

i=1,2,…

(7)

式中 R(k),G(k),B(k)为区域内像素k的三通道颜色分量，它们在整幅图像内的最大值和最小值为Rmax,Gmax,Bmax和Rmin,Gmin,Bmin，n为区域的像素点数。

(8)

2.2 基于k-d树特征结构的超像素匹配

SIFT特征匹配时间复杂度为o(n2)。k-d树(k-dimensiontree)[13]使搜索最匹配特征的时间复杂度降低到o(nlgn)。

设超像素ωA(i)∈A和超像素ωB(j)∈B满足引导条件(式(8)),则对特征SIFTpi∈ωA(i)的最佳匹配SIFTpj∈ωB(j)应满足主条件(式(9))和附加条件(式(10)),即

‖SIFTpi-SIFTpj‖=α0

(9)

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

(10)

式中 SIFTqj∈ωB(j)，且在ωB(j)的所有特征中，它与SIFTpi的欧氏距离仅大于α0。附加条件保证可靠性，阈值β越小，则匹配点对(pi,pj)越可靠。

用上述方法，对两幅待拼接航拍地图进行基于超像素的特征匹配，得到的匹配结果经人工核对存在少数误匹配。

2.3 RANSAC匹配点精选

图像A的超像素ωA(i)和图像B的超像素ωB(j)之间形成含有少量的特征误匹配点对，称为异常数据。RANSAC[14]用于匹配超像素匹配点的精选。

2.4 有监督条件下的超像素匹配对的收集

超像素是图像中较小区域，需要使用2.2～2.3的方法将最佳超像素匹配对数扩大。将已获得的最佳超像素匹配对信息转化为监督条件，以限定搜索。方法如下：

设图像A的超像素ωA(i)获得图像B的最佳匹配超像素ωB(j)，则有：

1)选ωA(i)的四邻域超像素，找到满足式(8)且与ωB(j)相邻的超像素，(可能不止一个)；

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

3)将(ωA(i),ωB(j))作区域屏蔽，令新的超像素匹配对为(ωA(i),ωB(j))。如果最佳超像素匹配对数超过了设定的阈值(本文定为3)，则结束;否则,返回步骤(1)。

上述方法体现了基于超像素的小特征团队思想。

2.5 图像融合

建立两幅图像的坐标转换矩阵，实现图像融合[15]。

3 图像拼接测试

将本文算法和单纯SIFT算法在拼接准确率和拼接速度两方面展开对比分析。测试平台为Windows7，3.20GHz主频，4GB内存PC，利用Matlab2013b进行编程测试。测试样本由中国天津气象局提供。测试内容为拼接准确率和拼接效率。

图1～图3列举了三种类型航拍地图拼接的情况。可以看出：三种情况下本文算法得到了满意的拼接结果，而单纯SIFT算法在第三种情况下出现了错配。

图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图像拼接过程中的部分主要参数，可以看出：与单纯SIFT算法相比，本文算法提取的SIFT特征点数和匹配点数大幅度下降，加之本文算法增加超像素分割所用的时间开销，总体拼接时间降低了近50%。同时，三对图像拼接结果中，单纯SIFT算法有一例出现了明显拼接偏差。

表1 超像素SIFT拼接与单纯SIFT拼接速度与准确率对比

建立不同分辨率不同场景下的待拼接图像测试样本库。运行算法，测试每一组的实验结果。建立平均运算时间和最大运算时间随分辨率的变化曲线，如图4所示。

图4 算法运算时间与分辨率的关系图Fig 4 Relationship between computation time of algorithm and resolution

4 结束语

航拍地图分辨率高，内容复杂多变，需要有效且快速的算法进行拼接处理。SIFT特征对航拍地图拼接具有很好的应用效果，但准确率和计算效率都有待提高。本文提出了超像素SIFT拼接算法，利用有限的超像素上的SIFT特征实现航拍地图的匹配和拼接。在超像素分割中，提出的将AP算法融入SLIC的AP-SLIC算法改善了其不能自适应确定超像素数目的问题，并使用图像颜色标准差自适应调节颜色空间和坐标空间的相互关系，使分割算法更加适应内容复杂多变的航拍地图。匹配点筛选引入监督机制。实验表明：与单纯SIFT算法相比，面对600×600及以上的图像拼接问题，本文算法在计算时间和匹配准确度上优势明显。

[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-)，女，天津人,硕士,教授,主要从事模式识别方法及应用,图像理解,运动对象跟踪等方面的研究工作。

王 港，通讯作者，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

公益性行业(气象)科研项目(GYHY200706004)；天津市自然科学基金资助项目(09JCYBJC07500)

TP 751.1

A

1000—9787(2016)12—0017—03