常方媛，馮志勇，徐 超

(1.天津大學計算機科學與技術學院，天津 300072；2.天津大學軟件學院，天津 300072)

基于SLIC區(qū)域分割的三維地形重建算法*

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

(1.天津大學計算機科學與技術學院，天津 300072；2.天津大學軟件學院，天津 300072)

為利用無人機在高空連續(xù)拍攝的兩幅航拍圖像準確實現(xiàn)三維地形重建，提出了通過將圖像進行區(qū)域分割來達到不同地形區(qū)域分別生成數(shù)字高程模型DEM數(shù)據(jù)的方法。首先利用簡單線性迭代聚類SLIC超像素算法將圖像分割為多個包含單一地形的超像素區(qū)域，再利用各區(qū)域的顏色信息進行相鄰同類地形區(qū)域的融合，最后在所得的各區(qū)域內(nèi)通過SIFT特征點提取與匹配、計算三維坐標來生成DEM數(shù)據(jù)。通過將重建地形結果與衛(wèi)星地圖對比表明，利用該方法能夠有效實現(xiàn)地形重建；通過對比本文算法與傳統(tǒng)地形重建算法的重建結果表明，利用該方法能準確呈現(xiàn)各地形間的邊界信息。

地形重建;簡單線性迭代聚類超像素算法;區(qū)域分割;SIFT算法

1 引言

三維地形重建是在已有數(shù)據(jù)基礎上，建立描述某一部分地球表面及其特征的曲面模型，與原數(shù)據(jù)相比，它具有更強的立體感與真實感，擁有廣闊的應用前景[1]。等高線數(shù)據(jù)是進行地形重建常用的一種數(shù)據(jù)形式，Zhang Z等人[2]基于等高線數(shù)據(jù)，提出了一種純粹幾何算法來進行地形重建，該算法利用貼磚準則確保了在地形重建過程中，任意分枝地形都能進行正確的拓撲劃分。等高線數(shù)據(jù)雖然具有高度準確性，但對于數(shù)據(jù)的讀取需要一定的專業(yè)知識基礎[3]，且在一定程度上無法提供足夠的精確性，因此在地形重建過程中，更多的是利用數(shù)字高程模型DEM(Digital Elevation Model)數(shù)據(jù)與二維圖像來實現(xiàn)[4]。Wilson R C和Hancock E R在方差偏差分析基礎上對DEM數(shù)據(jù)進行網(wǎng)格優(yōu)化；Lu Y H等人[5]在對圖像進行圖像匹配與分割后，分別獲得圖像中的房屋、樹木等區(qū)域，最后根據(jù)DEM數(shù)據(jù)實現(xiàn)地形重建；介鳴等人利用兩幅圖像進行特征點的匹配，然后通過運動估計、圖像校正與視差計算實現(xiàn)月球表面的地形重建；Chen Jie等人[6]通過對無人機拍攝的具有大面積重疊的圖像對進行像素級的SIFT特征點匹配與像素坐標計算來實現(xiàn)地形重建。

與DEM數(shù)據(jù)相比，二維圖像的獲取更加容易，因此本文將二維圖像作為三維地形重建的原始數(shù)據(jù)；與此同時，無人機航拍圖像具有分辨率高、拍攝范圍廣、對拍攝環(huán)境要求低等優(yōu)點，同時因為它的拍攝角度是隨機選取，無法過多地進行人為的調整，因此利用無人機航拍圖像進行地形重建的算法也更具有普適性。然而，現(xiàn)有的地形重建算法通常是在整幅圖像范圍內(nèi)進行數(shù)據(jù)處理，當處理無人機航拍圖像等分辨率高的圖像時耗時較多[7]，同時由于圖像中會同時存在多種不同的地形，若使用統(tǒng)一的方法進行地形重建，會不可避免地造成不同地形間的邊界模糊與位置不準確等問題。因此，本文首先利用改進的簡單線性迭代聚類SLIC(Simple Linear Iterative Clustering)超像素分割算法將圖像中的不同地形進行了區(qū)域劃分，然后集合并改進了幾種簡單而有效的算法，在各個區(qū)域內(nèi)分別生成三維坐標數(shù)據(jù)，最終實現(xiàn)三維地形的重建。該重建算法主要包括三個部分：基于SLIC算法的區(qū)域分割、SIFT特征點的提取與匹配、特征點坐標計算及DEM數(shù)據(jù)生成。本文首先利用SLIC算法將圖像分割成多個僅包含一種地形的超像素區(qū)域，再利用它們的顏色信息實現(xiàn)相鄰超像素間同類地形的融合，從而大大減少SLIC算法中所得超像素數(shù)量，以提高算法效率；然后進行SIFT特征點的提取與匹配，為了便于后續(xù)分區(qū)域計算坐標數(shù)據(jù)，此步驟在第一階段生成的各個超像素區(qū)域內(nèi)分別進行；最后在各個區(qū)域內(nèi)計算特征點的三維坐標并分別生成DEM數(shù)據(jù)，從而實現(xiàn)地形的三維重建。

2 基于SLIC區(qū)域分割的三維地形重建算法

2.1 SLIC超像素分割算法

超像素算法將像素聚合成有意義的子區(qū)域，既方便計算圖像特征，又能降低圖像處理復雜度[8]，因此在近幾年被廣泛應用于圖像預處理階段[9,10]。其中，SLIC算法是一種基于顏色相似度和空間臨近度的像素聚類方法[11]，不僅生成的超像素邊緣清晰，而且具有運算速度快、靈活易用等優(yōu)點[12]。因此，本文首先利用SLIC算法將圖像進行超像素分割，使得每個超像素中僅存在一種地形。

對于一幅CIELAB顏色空間中的彩色圖像，該算法首先將圖像分成k個大小均勻的矩形區(qū)域，作為初始的超像素集合。在每個超像素集合中，將在3×3的鄰域內(nèi)梯度最小的點選定為各集合的初始中心點Ci=[li,ai,bi,xi,yi]T，其中l(wèi)i、ai、bi分別為點Ci的L、A、B顏色分量值，xi、yi為點Ci在圖中的坐標，這樣選取可以有效地避免邊界點與噪聲像素被選為中心點。

(1)

式(1)中引入了新的參數(shù)m，它代表了超像素分割后的緊湊程度，取值范圍為[1，20] ，默認情況下取m=10。

重復上述過程直到殘差E小于設定的閾值δ為止。

2.2 基于SLIC的區(qū)域分割算法

經(jīng)過SLIC分割以后，圖像被劃分成了k個區(qū)域，但為了保證不同區(qū)域間的邊界被正確劃分，k值不能取得過小。若在這種情況下，直接對k個超像素集合分別進行三維重建，將會造成算法的繁瑣與低效，因此本文在SLIC算法的基礎上，利用圖像的RGB顏色信息，將相鄰的同類地形區(qū)域融合為一個更大的超像素集合。融合的方法為：

(1)提取各個超像素集合的RGB顏色信息，分別計算R、G、B顏色分量的均值，并將均值數(shù)值最大的顏色(如R)作為該超像素集合的主顏色；

(2)對于任意兩個相鄰的超像素集合，在主顏色相同(如同為R)的情況下，計算主顏色均值差值的絕對值(如|Rs-Rt|)，若小于設定的閾值，則將這兩個超像素集合進行融合。

此融合方法僅計算了各超像素集合內(nèi)的主顏色數(shù)值，雖然另外兩種顏色分量間的差別也會對融合結果造成影響，但考慮到無人機航拍圖像的分辨率相對于圖像中實際地形大小而言，顏色細節(jié)仍然比較粗糙，各地形區(qū)域的主顏色會呈現(xiàn)同類地形數(shù)值相近、不同地形數(shù)值相差較多的趨勢，因此造成的影響可以忽略不計。實驗結果也證明，僅考慮主顏色進行融合完全能夠滿足實驗需求。

本文提出的基于SLIC的區(qū)域分割算法，是基于“具有相同語義的相鄰區(qū)域間顏色相近”的假定，因此此分割算法主要適用于同類地形相對集中且顏色相近、不同地形間顏色差別比較明顯的自然場景圖像。當圖像內(nèi)包含過多的人為建筑時，由于區(qū)域顏色與語義之間的對應關系被削弱，因此會影響區(qū)域分割的準確性；此外，當航拍圖像受外界因素影響，導致圖像間色調發(fā)生較大偏差時，同樣會對分割結果產(chǎn)生不利影響。

2.3 SIFT特征點的提取與匹配

SIFT算法由Lowe D在1999年發(fā)表，并于2004年進行了發(fā)展與完善。該算法主要包括兩個階段[13]，第一階段是SIFT特征的生成，第二階段是SIFT特征向量的匹配。其中特征向量的生成算法主要包括四個步驟：(1)通過尺度空間極值檢測，來初步確定關鍵點的位置與所在的尺度；(2)通過擬合三維二次函數(shù)來精確確定關鍵點的位置和尺度，同時去除對比度低的關鍵點和不穩(wěn)定的邊緣響應點；(3)為各個關鍵點指定方向參數(shù)；(4)生成SIFT特征向量。當兩幅圖像的SIFT特征向量生成后，利用關鍵點特征向量間的歐氏距離作為匹配的判定標準。

連續(xù)拍攝的圖像雖然具有大面積的重疊，但仍會存在形狀、顏色的局部差異，而SIFT算法對平移、旋轉、尺度縮放、亮度變化、遮擋和噪聲等具有良好的不變性[14]，因此本文利用SIFT算法進行特征點的提取與匹配。

在進行SIFT特征點的提取與匹配時，存在兩種不同的方式，一種是在整幅圖像范圍內(nèi)進行，另一種是在各個超像素區(qū)域內(nèi)分別進行。由于連續(xù)拍攝的兩幅圖像間除了位置的偏移，在其他方面沒有較大的差別，因此兩種方式下得到的特征點數(shù)量不會存在太大差異。但是，當在各區(qū)域內(nèi)分別進行時，因為去掉了區(qū)域以外的部分，減少了對特征點匹配過程的干擾，所以能夠有效地減少誤匹配特征點對的數(shù)量。圖1顯示了利用不同方式進行匹配的結果。從圖1中可見，在整幅圖像范圍內(nèi)進行匹配時出現(xiàn)了明顯的錯誤，而在超像素區(qū)域內(nèi)進行時并未發(fā)生；在算法運行時間方面，第一種方式用時7.08 s，第二種方式用時10.13 s，雖然分區(qū)域進行特征點提取與匹配耗時較多，但若綜合考慮算法的精度與速度，顯然后一種方式更具優(yōu)勢；此外，將各個超像素區(qū)域內(nèi)所含特征點的匹配結果彼此分開，將方便后續(xù)階段在各個區(qū)域內(nèi)分別生成DEM數(shù)據(jù)。因此，本文在進行SIFT特征點的提取與匹配時，采取在各個超像素區(qū)域內(nèi)分別進行的方式。

Figure 1 Matching results in different ways

2.4 基于雙目立體視覺的三維地形重建

在得到了匹配的特征點對以后，利用它們的坐標關系，通過雙目立體視覺原理，便可以計算出各特征點的深度值[15]，進而得到三維坐標。假定輸入的兩幅航拍圖像為無人機在空中飛行過程中，先后拍攝的兩幅圖像，兩幅圖像的拍攝間隔較短；飛機在飛行過程中沿直線飛行，且機身與地面平行，因此可以近似地認為連續(xù)拍攝的兩張圖像處于同一XY平面內(nèi)且相互之間平行[16]，此時特征點對的坐標值與深度值的關系可簡化為：

(2)

其中， x1與 x2分別為一對特征點在兩幅圖像中的橫坐標，λ為相機焦距，B為拍攝兩幅圖像的間隔距離，W(X,Y,Z)為特征點對所對應的世界坐標，h為點W(X,Y,Z)相對于無人機的深度值。在得到點W(X,Y,Z)的深度值以后，再利用圖像拍攝時無人機相對于地面的相對高度值，便能方便地得出點W(X,Y,Z)的相對高度值，即特征點的三維高度信息。

經(jīng)上述步驟得到各超像素區(qū)域的特征點三維坐標后，針對不同區(qū)域內(nèi)地形特點，可以使用不同的插值方法來分別生成DEM數(shù)據(jù)，其中地勢平坦、坡度較緩的道路、農(nóng)田等利用少數(shù)特征點直接進行線性插值即可，對于高度較大、坡度較陡的山地則可以采用AMLE算法[17]，最后利用OpenGL實現(xiàn)地形的三維重建。

在此算法的三個階段之中，區(qū)域分割算法主要適用于同類地形相對集中且顏色相近、不同地形間顏色差別比較明顯的自然場景圖像；特征點的提取與匹配階段選用了適應性較好的SIFT特征，因此對輸入圖像幾乎沒有限制；DEM數(shù)據(jù)生成階段則是需要根據(jù)不同的地形特征選取與之相應的插值方法，因此本文算法的適用范圍與區(qū)域分割算法適用范圍一致。

3 實驗結果與分析

基于上述方法，選取了無人機在北緯45.285 67°、東經(jīng)119.888 8°處連續(xù)拍攝的兩幅圖像作為原始數(shù)據(jù)(如圖2所示)，兩幅圖像的尺寸均為5 616×3 744，圖中方框內(nèi)為兩幅圖像的重疊區(qū)域，即需要進行地形重建的區(qū)域。實驗平臺為Intel(R) Core(TM) i5處理器，4.00 GB內(nèi)存，軟件平臺為Windows 7操作系統(tǒng)，Matlab2012a、Visual C++ 6.0和三維圖形標準庫OpenGL。

Figure 2 Original pictures

首先，分別對兩幅圖像進行SLIC超像素分割，其中參數(shù)k根據(jù)經(jīng)驗選取為k=60。圖3顯示了不同m值情況下的分割結果，當m=10時，分割所得的超像素區(qū)域細節(jié)過于繁瑣(如圖3a所示)，不利于在此基礎上進行區(qū)域融合，因此適當增大m值，由圖3b可知，當 m=15時分割結果已經(jīng)可以滿足后續(xù)的實驗需求，因此取 m=15。接下來利用2.2節(jié)提出的方法對所得的超像素集合進行融合，通過對比不同閾值的融合效果，最終選取 γ=0.15，經(jīng)過在SLIC超像素分割算法的基礎上進行融合，兩幅圖像分別被分割成了四個超像素區(qū)域(如圖4所示)，上述兩個步驟共用時257.65 s。由圖4可以看出，本文算法對圖像進行的區(qū)域分割是合理的，且兩幅圖像的分割結果基本一致，這表明本文算法能夠有效地實現(xiàn)圖像的區(qū)域分割。接下來，將上步中得到的各對應區(qū)域分別進行SIFT特征點的提取與匹配，總共用時10.13 s；由于所拍攝圖像中大部分地形比較平緩，因此本文在利用式(2)計算得到特征點的三維坐標后，在各區(qū)域內(nèi)利用線性插值方法分別生成DEM數(shù)據(jù)；最后將重疊區(qū)域的圖像作為紋理，利用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地球對圖像拍攝位置進行定位，得到衛(wèi)星地圖如圖5b所示，通過將其與本文算法重建出的三維地形進行對比可以看出，本文重建出的地形與衛(wèi)星地圖的地形在地勢起伏走向方面是完全一致的，相對應的部分已在圖中進行了標示，這表明本文算法能夠有效地實現(xiàn)地形的三維重建。為了更清晰地表明此算法在三維地形重建中的優(yōu)勢，利用去除算法的第一步而保持其他部分不變，即不進行圖像的區(qū)域分割，直接進行特征點提取與匹配，最后生成DEM數(shù)據(jù)的方法再次進行了地形的三維重建，結果如圖6所示。通過對比兩種方法所得結果不難看出，在不進行圖像分割的情況下，圖中被標出的部分本應向下凹陷，但由于兩側地形內(nèi)特征點的海拔高度相近，因此當利用線性插值方法生成DEM數(shù)據(jù)時，此處變成了左右兩部分的過渡區(qū)域，丟失了兩個區(qū)域之間的邊界信息，導致重建出的地形與實際地形差別較大，而利用本文算法得到的實驗結果則能較準確地呈現(xiàn)出左右兩個區(qū)域之間的邊界細節(jié)；此外，由于利用整幅圖像進行SIFT特征點的提取與匹配無法自動去除誤匹配點，因此會造成特征點三維坐標的計算錯誤，最終導致生成地形中右上角的地形趨勢與實際地形不符，而利用本文算法則能有效地減少此類錯誤的發(fā)生。因此，雖然本文算法進行圖像區(qū)域分割額外耗費了一些時間，但它對于提高重建地形的準確性具有至關重要的作用。

Figure 6 3D terrain reconstruction results with and without segmentation

4 結束語

為了解決三維地形重建中出現(xiàn)的不同地形間邊界模糊、位置不準確的問題，本文提出了基于SLIC區(qū)域分割的三維地形重建算法。該算法首先利用SLIC超像素分割算法對圖像進行預處理，接著再利用各個超像素的顏色信息進行相鄰超像素間同類地形融合，從而實現(xiàn)圖像中不同地形區(qū)域的分割；然后在各區(qū)域內(nèi)分別進行特征點的提取與匹配、DEM數(shù)據(jù)的生成；最終實現(xiàn)對地形的重建。通過與衛(wèi)星地圖對比可知，本文算法重建出的地形是準確、可靠的；與未經(jīng)區(qū)域分割重建出的地形對比表明，本文算法能夠很好地解決地形重建中邊界模糊、位置不準確等問題，從而大大提高地形重建的準確性。在接下來的研究中，可以通過增加原始圖像數(shù)量來不斷擴展圖像間的重疊部分，從而對DEM數(shù)據(jù)進行修正，使生成的三維地形更加準確；此外，在對連續(xù)拍攝的序列圖像進行區(qū)域分割時，可以令后一幅圖像在前面圖像分割結果的基礎上通過修正來實現(xiàn)，從而減少算法的運行時間。

[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-),女,河北唐山人，碩士生，研究方向為區(qū)域分割和三維重建。E-mail:fangyuanc@163.com

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

馮志勇(1965-),男,內(nèi)蒙古呼和浩特人，博士，教授，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