基于SLIC区域分割的三维地形重建算法*

常方媛，冯志勇，徐 超

(1.天津大学计算机科学与技术学院，天津 300072；2.天津大学软件学院，天津 300072)

基于SLIC区域分割的三维地形重建算法*

常方媛1，冯志勇1，徐 超2

(1.天津大学计算机科学与技术学院，天津 300072；2.天津大学软件学院，天津 300072)

为利用无人机在高空连续拍摄的两幅航拍图像准确实现三维地形重建，提出了通过将图像进行区域分割来达到不同地形区域分别生成数字高程模型DEM数据的方法。首先利用简单线性迭代聚类SLIC超像素算法将图像分割为多个包含单一地形的超像素区域，再利用各区域的颜色信息进行相邻同类地形区域的融合，最后在所得的各区域内通过SIFT特征点提取与匹配、计算三维坐标来生成DEM数据。通过将重建地形结果与卫星地图对比表明，利用该方法能够有效实现地形重建；通过对比本文算法与传统地形重建算法的重建结果表明，利用该方法能准确呈现各地形间的边界信息。

地形重建;简单线性迭代聚类超像素算法;区域分割;SIFT算法

1 引言

三维地形重建是在已有数据基础上，建立描述某一部分地球表面及其特征的曲面模型，与原数据相比，它具有更强的立体感与真实感，拥有广阔的应用前景[1]。等高线数据是进行地形重建常用的一种数据形式，Zhang Z等人[2]基于等高线数据，提出了一种纯粹几何算法来进行地形重建，该算法利用贴砖准则确保了在地形重建过程中，任意分枝地形都能进行正确的拓扑划分。等高线数据虽然具有高度准确性，但对于数据的读取需要一定的专业知识基础[3]，且在一定程度上无法提供足够的精确性，因此在地形重建过程中，更多的是利用数字高程模型DEM(Digital Elevation Model)数据与二维图像来实现[4]。Wilson R C和Hancock E R在方差偏差分析基础上对DEM数据进行网格优化；Lu Y H等人[5]在对图像进行图像匹配与分割后，分别获得图像中的房屋、树木等区域，最后根据DEM数据实现地形重建；介鸣等人利用两幅图像进行特征点的匹配，然后通过运动估计、图像校正与视差计算实现月球表面的地形重建；Chen Jie等人[6]通过对无人机拍摄的具有大面积重叠的图像对进行像素级的SIFT特征点匹配与像素坐标计算来实现地形重建。

与DEM数据相比，二维图像的获取更加容易，因此本文将二维图像作为三维地形重建的原始数据；与此同时，无人机航拍图像具有分辨率高、拍摄范围广、对拍摄环境要求低等优点，同时因为它的拍摄角度是随机选取，无法过多地进行人为的调整，因此利用无人机航拍图像进行地形重建的算法也更具有普适性。然而，现有的地形重建算法通常是在整幅图像范围内进行数据处理，当处理无人机航拍图像等分辨率高的图像时耗时较多[7]，同时由于图像中会同时存在多种不同的地形，若使用统一的方法进行地形重建，会不可避免地造成不同地形间的边界模糊与位置不准确等问题。因此，本文首先利用改进的简单线性迭代聚类SLIC(Simple Linear Iterative Clustering)超像素分割算法将图像中的不同地形进行了区域划分，然后集合并改进了几种简单而有效的算法，在各个区域内分别生成三维坐标数据，最终实现三维地形的重建。该重建算法主要包括三个部分：基于SLIC算法的区域分割、SIFT特征点的提取与匹配、特征点坐标计算及DEM数据生成。本文首先利用SLIC算法将图像分割成多个仅包含一种地形的超像素区域，再利用它们的颜色信息实现相邻超像素间同类地形的融合，从而大大减少SLIC算法中所得超像素数量，以提高算法效率；然后进行SIFT特征点的提取与匹配，为了便于后续分区域计算坐标数据，此步骤在第一阶段生成的各个超像素区域内分别进行；最后在各个区域内计算特征点的三维坐标并分别生成DEM数据，从而实现地形的三维重建。

2 基于SLIC区域分割的三维地形重建算法

2.1 SLIC超像素分割算法

超像素算法将像素聚合成有意义的子区域，既方便计算图像特征，又能降低图像处理复杂度[8]，因此在近几年被广泛应用于图像预处理阶段[9,10]。其中，SLIC算法是一种基于颜色相似度和空间临近度的像素聚类方法[11]，不仅生成的超像素边缘清晰，而且具有运算速度快、灵活易用等优点[12]。因此，本文首先利用SLIC算法将图像进行超像素分割，使得每个超像素中仅存在一种地形。

对于一幅CIELAB颜色空间中的彩色图像，该算法首先将图像分成k个大小均匀的矩形区域，作为初始的超像素集合。在每个超像素集合中，将在3×3的邻域内梯度最小的点选定为各集合的初始中心点Ci=[li,ai,bi,xi,yi]T，其中li、ai、bi分别为点Ci的L、A、B颜色分量值，xi、yi为点Ci在图中的坐标，这样选取可以有效地避免边界点与噪声像素被选为中心点。

(1)

式(1)中引入了新的参数m，它代表了超像素分割后的紧凑程度，取值范围为[1，20] ，默认情况下取m=10。

重复上述过程直到残差E小于设定的阈值δ为止。

2.2 基于SLIC的区域分割算法

经过SLIC分割以后，图像被划分成了k个区域，但为了保证不同区域间的边界被正确划分，k值不能取得过小。若在这种情况下，直接对k个超像素集合分别进行三维重建，将会造成算法的繁琐与低效，因此本文在SLIC算法的基础上，利用图像的RGB颜色信息，将相邻的同类地形区域融合为一个更大的超像素集合。融合的方法为：

(1)提取各个超像素集合的RGB颜色信息，分别计算R、G、B颜色分量的均值，并将均值数值最大的颜色(如R)作为该超像素集合的主颜色；

(2)对于任意两个相邻的超像素集合，在主颜色相同(如同为R)的情况下，计算主颜色均值差值的绝对值(如|Rs-Rt|)，若小于设定的阈值，则将这两个超像素集合进行融合。

此融合方法仅计算了各超像素集合内的主颜色数值，虽然另外两种颜色分量间的差别也会对融合结果造成影响，但考虑到无人机航拍图像的分辨率相对于图像中实际地形大小而言，颜色细节仍然比较粗糙，各地形区域的主颜色会呈现同类地形数值相近、不同地形数值相差较多的趋势，因此造成的影响可以忽略不计。实验结果也证明，仅考虑主颜色进行融合完全能够满足实验需求。

本文提出的基于SLIC的区域分割算法，是基于“具有相同语义的相邻区域间颜色相近”的假定，因此此分割算法主要适用于同类地形相对集中且颜色相近、不同地形间颜色差别比较明显的自然场景图像。当图像内包含过多的人为建筑时，由于区域颜色与语义之间的对应关系被削弱，因此会影响区域分割的准确性；此外，当航拍图像受外界因素影响，导致图像间色调发生较大偏差时，同样会对分割结果产生不利影响。

2.3 SIFT特征点的提取与匹配

SIFT算法由Lowe D在1999年发表，并于2004年进行了发展与完善。该算法主要包括两个阶段[13]，第一阶段是SIFT特征的生成，第二阶段是SIFT特征向量的匹配。其中特征向量的生成算法主要包括四个步骤：(1)通过尺度空间极值检测，来初步确定关键点的位置与所在的尺度；(2)通过拟合三维二次函数来精确确定关键点的位置和尺度，同时去除对比度低的关键点和不稳定的边缘响应点；(3)为各个关键点指定方向参数；(4)生成SIFT特征向量。当两幅图像的SIFT特征向量生成后，利用关键点特征向量间的欧氏距离作为匹配的判定标准。

连续拍摄的图像虽然具有大面积的重叠，但仍会存在形状、颜色的局部差异，而SIFT算法对平移、旋转、尺度缩放、亮度变化、遮挡和噪声等具有良好的不变性[14]，因此本文利用SIFT算法进行特征点的提取与匹配。

在进行SIFT特征点的提取与匹配时，存在两种不同的方式，一种是在整幅图像范围内进行，另一种是在各个超像素区域内分别进行。由于连续拍摄的两幅图像间除了位置的偏移，在其他方面没有较大的差别，因此两种方式下得到的特征点数量不会存在太大差异。但是，当在各区域内分别进行时，因为去掉了区域以外的部分，减少了对特征点匹配过程的干扰，所以能够有效地减少误匹配特征点对的数量。图1显示了利用不同方式进行匹配的结果。从图1中可见，在整幅图像范围内进行匹配时出现了明显的错误，而在超像素区域内进行时并未发生；在算法运行时间方面，第一种方式用时7.08 s，第二种方式用时10.13 s，虽然分区域进行特征点提取与匹配耗时较多，但若综合考虑算法的精度与速度，显然后一种方式更具优势；此外，将各个超像素区域内所含特征点的匹配结果彼此分开，将方便后续阶段在各个区域内分别生成DEM数据。因此，本文在进行SIFT特征点的提取与匹配时，采取在各个超像素区域内分别进行的方式。

Figure 1 Matching results in different ways

2.4 基于双目立体视觉的三维地形重建

在得到了匹配的特征点对以后，利用它们的坐标关系，通过双目立体视觉原理，便可以计算出各特征点的深度值[15]，进而得到三维坐标。假定输入的两幅航拍图像为无人机在空中飞行过程中，先后拍摄的两幅图像，两幅图像的拍摄间隔较短；飞机在飞行过程中沿直线飞行，且机身与地面平行，因此可以近似地认为连续拍摄的两张图像处于同一XY平面内且相互之间平行[16]，此时特征点对的坐标值与深度值的关系可简化为：

(2)

其中， x1与 x2分别为一对特征点在两幅图像中的横坐标，λ为相机焦距，B为拍摄两幅图像的间隔距离，W(X,Y,Z)为特征点对所对应的世界坐标，h为点W(X,Y,Z)相对于无人机的深度值。在得到点W(X,Y,Z)的深度值以后，再利用图像拍摄时无人机相对于地面的相对高度值，便能方便地得出点W(X,Y,Z)的相对高度值，即特征点的三维高度信息。

经上述步骤得到各超像素区域的特征点三维坐标后，针对不同区域内地形特点，可以使用不同的插值方法来分别生成DEM数据，其中地势平坦、坡度较缓的道路、农田等利用少数特征点直接进行线性插值即可，对于高度较大、坡度较陡的山地则可以采用AMLE算法[17]，最后利用OpenGL实现地形的三维重建。

在此算法的三个阶段之中，区域分割算法主要适用于同类地形相对集中且颜色相近、不同地形间颜色差别比较明显的自然场景图像；特征点的提取与匹配阶段选用了适应性较好的SIFT特征，因此对输入图像几乎没有限制；DEM数据生成阶段则是需要根据不同的地形特征选取与之相应的插值方法，因此本文算法的适用范围与区域分割算法适用范围一致。

3 实验结果与分析

基于上述方法，选取了无人机在北纬45.285 67°、东经119.888 8°处连续拍摄的两幅图像作为原始数据(如图2所示)，两幅图像的尺寸均为5 616×3 744，图中方框内为两幅图像的重叠区域，即需要进行地形重建的区域。实验平台为Intel(R) Core(TM) i5处理器，4.00 GB内存，软件平台为Windows 7操作系统，Matlab2012a、Visual C++ 6.0和三维图形标准库OpenGL。

Figure 2 Original pictures

首先，分别对两幅图像进行SLIC超像素分割，其中参数k根据经验选取为k=60。图3显示了不同m值情况下的分割结果，当m=10时，分割所得的超像素区域细节过于繁琐(如图3a所示)，不利于在此基础上进行区域融合，因此适当增大m值，由图3b可知，当 m=15时分割结果已经可以满足后续的实验需求，因此取 m=15。接下来利用2.2节提出的方法对所得的超像素集合进行融合，通过对比不同阈值的融合效果，最终选取 γ=0.15，经过在SLIC超像素分割算法的基础上进行融合，两幅图像分别被分割成了四个超像素区域(如图4所示)，上述两个步骤共用时257.65 s。由图4可以看出，本文算法对图像进行的区域分割是合理的，且两幅图像的分割结果基本一致，这表明本文算法能够有效地实现图像的区域分割。接下来，将上步中得到的各对应区域分别进行SIFT特征点的提取与匹配，总共用时10.13 s；由于所拍摄图像中大部分地形比较平缓，因此本文在利用式(2)计算得到特征点的三维坐标后，在各区域内利用线性插值方法分别生成DEM数据；最后将重叠区域的图像作为纹理，利用OpenGL进行地形的三维重建，总共用时10.51 s，重建结果如图5a所示。

Figure 3 Segmentation results of the superpixel algorithm

Figure 4 Segmentation results

Figure 5 Comparison between the 3D terrain reconstruction result and the satellite map

利用Google地球对图像拍摄位置进行定位，得到卫星地图如图5b所示，通过将其与本文算法重建出的三维地形进行对比可以看出，本文重建出的地形与卫星地图的地形在地势起伏走向方面是完全一致的，相对应的部分已在图中进行了标示，这表明本文算法能够有效地实现地形的三维重建。为了更清晰地表明此算法在三维地形重建中的优势，利用去除算法的第一步而保持其他部分不变，即不进行图像的区域分割，直接进行特征点提取与匹配，最后生成DEM数据的方法再次进行了地形的三维重建，结果如图6所示。通过对比两种方法所得结果不难看出，在不进行图像分割的情况下，图中被标出的部分本应向下凹陷，但由于两侧地形内特征点的海拔高度相近，因此当利用线性插值方法生成DEM数据时，此处变成了左右两部分的过渡区域，丢失了两个区域之间的边界信息，导致重建出的地形与实际地形差别较大，而利用本文算法得到的实验结果则能较准确地呈现出左右两个区域之间的边界细节；此外，由于利用整幅图像进行SIFT特征点的提取与匹配无法自动去除误匹配点，因此会造成特征点三维坐标的计算错误，最终导致生成地形中右上角的地形趋势与实际地形不符，而利用本文算法则能有效地减少此类错误的发生。因此，虽然本文算法进行图像区域分割额外耗费了一些时间，但它对于提高重建地形的准确性具有至关重要的作用。

Figure 6 3D terrain reconstruction results with and without segmentation

4 结束语

为了解决三维地形重建中出现的不同地形间边界模糊、位置不准确的问题，本文提出了基于SLIC区域分割的三维地形重建算法。该算法首先利用SLIC超像素分割算法对图像进行预处理，接着再利用各个超像素的颜色信息进行相邻超像素间同类地形融合，从而实现图像中不同地形区域的分割；然后在各区域内分别进行特征点的提取与匹配、DEM数据的生成；最终实现对地形的重建。通过与卫星地图对比可知，本文算法重建出的地形是准确、可靠的；与未经区域分割重建出的地形对比表明，本文算法能够很好地解决地形重建中边界模糊、位置不准确等问题，从而大大提高地形重建的准确性。在接下来的研究中，可以通过增加原始图像数量来不断扩展图像间的重叠部分，从而对DEM数据进行修正，使生成的三维地形更加准确；此外，在对连续拍摄的序列图像进行区域分割时，可以令后一幅图像在前面图像分割结果的基础上通过修正来实现，从而减少算法的运行时间。

[1] Xiong Qiu-bo. Based on two-dimension image 3d modeling technology research[J]. China Computer & Communication,2009(11):63-64.(in Chinese)

[2] Zhang Z Y,Knoon K,Tokuyama Y. 3D terrain reconstruction based on contours[C]∥Proc of the 9th International Conference on Computer Aided Design and Computer Graphics,2005:325-300.

[3] Wang Ning,Zhang Chuan-lin,Zhang Wen-zheng. A simple 3-D surface reconstruction method[J]. Journal of Jinan University(Natural Science),2010,31(5):467-470. (in Chinese)

[4] Pollefeys M,Luc V G. From images to 3D models[J]. Communication of the ACM,2002,45(7):50-55.

[5] Lu Y H,Kubik K,Bennamoun M. Image segmentation and image matching for 3D terrain reconstruction[C]∥Proc of the 14th International Conference on Pattern Recognition,1998:1535-1537.

[6] Chen J,Fang Y M,Xia Y H,et al. A study of three-dimensional reconstruction using high overlap aerial photograph sequence[C]∥Proc of 2011 International Symposium on Image and Data Fusion,2011:1-4.

[7] Domrongwatthanayothin B, Roeksabutr A, Chongchaewchamnanand M, et al. A simple static-shadow based algorithm for 3D complex-terrain surface reconstruction[C]∥Proc of 2005 IEEE International Geoscience and Remote Sensing Symposium,2005:1738-1741.

[8] Radhakrishna A,Appu S,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] Lawrence Zitnick C,Sing B K. Stereo for image-based rendering using image over-segmentation[J]. International Journal of Computer Vision,2007,75(1):49-65.

[10] Fulkerson B,Vedaldi A,Soatto S. Class segmentation and object localization with superpixel neighborhoods[C]∥Proc of IEEE 12th International Conference on Computer Vision,2009:670-677.

[11] Radhakrishna A,Appu S,Smith K,et al. SLIC superpixels: EPFL-Report-149300[R]. 2010.

[12] Kim K S,Zhang D N,Kang M C,et al. Improved simple linear iterative clustering superpixels[C]∥Proc of IEEE 17th International Symposium on Consumer Electronics(ISCE),2013:259-260.

[13] Wang J D,Li X Y,Shou L D,et al. A SIFT pruning algorithm for efficient near-duplicate image matching[J]. Journal of Computer Aided Design & Computer Graphics,2010,22(6):1042-1055.

[14] Zhang J,Sang H S. SIFT matching method based on scale transformation[J]. Journal of Infrared and Millmeter Waves,2014,33(2):177-182.

[15] Liu W,Wang Z C,Ning X L,et al. An object recognition and location based on binocular stereo vision[C]∥Proc of International Forum on Computer Science-Technology and Applications,2009:97-99.

[16] Du J J,He J S,Zhu J J. A method study of generating digital terrain map for Lunar exploration based on the stereo vi-

sion[C]∥Proc of 2011 IEEE International Conference on Information and Automation,2011:117-122.

[17] Andrés A,Frédéric C,Yann G,et al. Interpolation of digital elevation models using AMLE and related methods[J]. IEEE Transactions on Geoscience and Remote Sensing,2002,40(2):314-325.

附中文参考文献:

[1] 熊秋波. 基于二维图像的三维建模技术研究[J]. 信息与电脑,2009(11):63-64.

[3] 王宁，张传林，张文争. 一种简单的三维地形重建方法[J]. 暨南大学学报(自然科学版),2010,31(5):467-470.

常方媛(1989-),女,河北唐山人，硕士生，研究方向为区域分割和三维重建。E-mail:fangyuanc@163.com

CHANG Fang-yuan,born in 1989,MS candidate,her research interests include region segmentation, and 3D reconstruction.

冯志勇(1965-),男,内蒙古呼和浩特人，博士，教授，CCF会员(E200007516S)，研究方向为知识工程、服务计算和计算机认知。E-mail:zyfeng@tju.edu.cn

FENG Zhi-yong,born in 1965,PhD,professor,CCF member(E200007516S)，his research interests include knowledge engineering, service computing, and computer cognition.

徐超(1982-),男,山东沂水人，博士，副教授，CCF会员(E200013645M),研究方向为情感计算、预动计算和知识管理。E-mail:xc@tju.edu.cn

XU Chao,born in 1982,PhD,associate professor,CCF member(E200013645M)，his research interests include affective computing, proactive computing, and knowledge management.

A 3D terrain reconstruction algorithm based on SLIC segmentation

CHANG Fang-yuan1,FENG Zhi-yong1,XU Chao2

(1.School of Computer Science and Technology,Tianjin University,Tianjin 300072;2.School of Computer Software,Tianjin University,Tianjin 300072,China)

Most traditional 3D terrain reconstruction algorithms cannot represent the accurate structure of the terrain and are time consuming as well, thus the technological development is seriously hindered . In order to realize the 3D terrain reconstruction accurately by using pictures taken by unmanned aerial vehicle (UAV) with the advantages of high resolution, wide camera range and low demand of shot environment, we propose a method that generates digital elevation model (DEM) data respectively in different superpixel terrain areas by segmenting the images at the preprocessing stage. Firstly, the simple linear iterative clustering (SLIC) algorithm, which shows good performance in superpixel generation and is convenient to use, is adopted to segment the images into multiple superpixel terrain areas which contain just a single terrain type. Then the adjacent superpixel areas containing the same terrain are fused according to the LAB color information, in which way the number of superpixel areas is decreased and the speed of the algorithm is improved. Thirdly the scale-invariant feature transform (SIFT) feature points’ extraction and matching are done in each area. Based on the matching results, the 3D coordinates are computed with the method of binocular stereo vision and DEM data are generated in the end to reconstruct the terrain. Comparing with the satellite map, the proposed algorithm can reconstruct 3D terrains effectively, and it can present the boundaries information accurately in contrast with traditional 3D terrain algorithms.

terrain reconstruction;simple linear iterative clustering superpixel algorithm;region segmentation;scale-invariant feature transform algorithm

1007-130X(2015)09-1718-06

2014-10-11;

2015-01-16基金项目：国家自然科学基金资助项目(61304262)

TP751.1

A

10.3969/j.issn.1007-130X.2015.09.020

通信地址：300072 天津市天津大学计算机科学与技术学院

Address:School of Computer Science and Technology,Tianjin University,Tianjin 300072,P.R.China