三維建筑模型的規則化重構方法

陳佳舟，陸鵬飛，徐陽輝，王宇航，金靈楓,2,李凱勇，秦緒佳

1(浙江工業大學 計算機科學與技術學院，杭州 310012) 2(東南數字經濟發展研究院 數字空間技術研發中心，浙江 衢州 324000) 3(青海民族大學 物理與電子信息工程學院，青海 西寧 810007)

1 引 言

隨著無人機的普及，傾斜攝影測量技術在測繪領域得到廣泛應用.該技術利用圖形學中的Structure of Motion(SfM)和Multi-View Stereo(MVS)方法[1-3]，通過多組無人機航拍照片重建出高精度三維城市模型，極大地推動著智慧城市的發展.典型的SfM和MVS方法首先自動提取和匹配輸入圖像幾何每個像素點之間的特征，然后恢復出圖片的內部和外部攝像機參數，再由像素點對生成密集的3D點云模型，最后重建網格并貼上紋理.

雖然傾斜攝影測量技術能夠重建出大規模逼真的三維城市建筑，但這些模型在城市規劃、安防、GIS系統、虛擬現實和建筑設計等領域卻難以廣泛應用.其中一個重要的原因是傾斜攝影測量技術自動構建的三維建筑網格模型頂點數量龐大、噪聲多，給數據存儲、傳輸以及語義表達等諸多方面帶來了難以逾越的障礙.

三維網格模型的規則化重構(部分論文中譯為三維模型的簡化，下文出現的模型簡化即規則化重構)，是解決上述頂點數量爆炸和噪聲多問題的重要途徑之一.SketchUp的Pointools插件(1)http：//www.pointools.com/pointools-plug-in-for-sketchup.php，2019.允許用戶直接在3D點云上進行簡化，但簡化的準確性依賴于用戶的熟練程度.用戶需要通過目視檢查是否手動將簡化后幾何線條對準了模型中相應的點云.由于點云模型中存在固有的噪聲，用戶還需通過手動移動邊緣點來封閉簡化過程中出現的間隙，效率較低.此類簡化算法[4-7]通過提供用戶界面以手動的方式簡化模型，但簡化的準確性依賴于用戶的技術和耐心.大量半自動[8-13]和全自動[14-18]的簡化系統在近年來取得了一定成效，但半自動系統需要過多的人工干預，而全自動系統不是依賴先驗信息(圖像和視頻等)，就是對待簡化模型有著嚴格的假設，難以大范圍推廣.比如，Chen和Chen提出了一種通過在圖中搜索哈密頓回路來簡化模型多邊形表面的方法[12].該方法的前提是假設存在完整的平面集及其相鄰信息.如果兩個平面對應點集之間的最小距離在一定距離閾值內，則判斷它們是相鄰的.由于現實數據普遍存在數據錯誤和缺失，所以需要更復雜的算法來解決此問題.最近，Nan等人提出了一個PolyFit系統[16]，首先通過改進的RANSAC聚類方法進行點云的聚類，然后用聚類出的結果將模型切割成小塊的平面，再規則化提取出的平面，最后將問題轉化為二進制標記問題選出適合的候選平面，從而擬合出簡化結果.然而，該方法對點云模型的精度要求較高，對粗糙建筑模型的魯棒性較低.因此，三維建筑網格模型的規則化重構是一個亟需解決但又充滿挑戰的課題，一直都是計算機圖形學領域的熱點問題.

與地面激光或雷達不同，無人機拍攝是在低空自上而下完成的，無人機照片中屋頂的可見性較高，而建筑底部的可見性通常較低.因此，基于傾斜攝影測量重建的三維建筑模型往往屋頂比較精確；底部由于相互遮擋和其他建筑物干擾等原因，重建精度遠遠低于建筑頂部.基于上述觀察，本文提出了一種基于屋頂輪廓線的三維建筑模型規則化重構方法.首先，分割屋頂并提取屋頂的外輪廓線，進行化簡并規則化；接著，通過改進的平面擬合提取屋頂的內輪廓線；然后，根據屋頂內外輪廓線進一步組合優化擬合出屋頂平面幾何基元；最后，針對屋頂中的非平面部分(太陽能、煙囪等)，進行補充規則化處理.

本文方法無需借助任何其他先驗信息，能夠自動地將粗糙的三維建筑模型重構為少量三角面片組成的規則化三維模型，數據量平均極大減少(僅為原始模型的0.25%).大量的實驗表明，本文方法具有效率高、穩定性好等優點，有助于打通傾斜攝影測量到智慧城市應用的最后一個數據障礙.

2 算法設計

本文方法將傾斜攝影測量重建的三維建筑網格模型作為輸入，主要研究目標是將三維模型自動重構為規則化的簡化模型.如圖1所示，本文方法主要分為3個步驟：屋頂面外輪廓線提取與精化、屋頂面內輪廓線提取、規則化模型的生成.其中，外輪廓提取與精化和內輪廓線提取為規則化模型的生成提供了重要的基本元素，而重構后的規則化三維模型則是整個算法的最終成果.

圖1 算法流程圖Fig.1 Overview of our method

2.1 屋頂面外輪廓線提取與精化

針對單幢三維網格建筑物模型，本文首先進行預處理，提取出屬于屋頂面的三角面片.具體而言，將面片高度大于h，且面片法向量與地面法向量夾角小于θ的三角面片視作屋頂面片.h在本文中可自由調整，一般取1/2建筑物高度的值；θ取20度.需要指出的是，這兩個參數對本文方法的結果影響很小，少量立面部件(如太陽能)未被提取并不影響外輪廓線的生成，且在非平面基元提取部分進行補充處理.本文所有實驗均取上述兩個數值.圖1左圖為本論文需要規則化重構的原始三維建筑模型，圖1所示的屋頂面外輪廓線提取與精化部分左圖中的白色部分為預處理所提取出的屋頂面片.

在提取完屋頂面片后，提取屋頂面外輪廓線.通過三角面片的鄰接關系提取屋頂面外輪廓線是一種普遍的三角面片輪廓線提取方法，但該方法容易將斷裂的內輪廓誤判為外輪廓，使屋頂內部有一部分點被錯誤地提取為邊緣點.本文采用Alpha Shapes[19]方法來解決這一問題.該方法是一種有效的恢復離散點集原始形狀的輪廓線提取算法，提取過程等同于用一個半徑為α的圓在點集周圍滾動.只要參數α足夠大，圓只會在點集外部滾動，不會進入點集內部引起斷裂.在本文所有實驗中，α取3米.

經過Alpha Shapes方法提取出來的輪廓線段往往非常粗糙(圖2左圖)，一般需要進一步對其進行簡化處理.本文提出了一種基于最小平方法的輪廓線化簡方法，詳細設計步驟如算法1所示.該方法需要兩個參數，即點到直線的最大距離閾值d和最小直線長度閾值l.在本論文中，d一般設置為0.5倍的平均點間距，l設置為3倍的平均點間距.

圖2 外輪廓線提取過程Fig.2 Extraction process of outer-contours

算法1.

輸入：按序排列的外輪廓二維點集US.

輸出：按序排列的經過簡化后的二維點集.

Step 1.按順序依次選取輪廓線上US的3個連續的頂點a、b、c，并且用最小平方法擬合出經過這3個頂點的一條直線L，計算3個頂點到直線L的距離，如果任意一個頂點到直線L的距離大于閾值d，則下一步轉到Step 4；否則，令集合U={a，b，c}，轉Step 2；

Step 2.取集合U兩端點作為p和q，分別以p和q作為起點向兩側進行延伸，延伸過程中會遇到新的頂點，如果新的頂點到直線L的距離小于閾值d，則將其加入到集合U中，并將其作為新的端點，轉Step 3；

Step 3.在Step 2中，如果存在新的頂點被加入集合U中，則對集合U中的所有頂點用最小平方法重新擬合一條直線L，轉Step 2；否則，轉Step 4；

Step 4.判斷集合U擬合出的直線的長度，若直線長度大于閾值l，則將集合U兩端的頂點保留，舍棄中間的頂點，轉Step 5；否則，舍棄所有的頂點，轉Step 5；

Step 5.如果還有連續的3個頂點沒有判斷過，則轉Step 1；否則，結束算法.

圖2中圖是最小平方法的輪廓線化簡算法的結果.建筑物通常具有相對規則的幾何形狀，因此，針對建筑物外輪廓線的規則化應充分考慮垂直和平行這兩個最基本的特征，本文通過提出的分類強制正交規則化方法進行處理.具體方法是找出最長的線段為初始線段，其他線段與之判斷，若兩線段方位角的差在閾值范圍內，則歸為A類，否則歸到B類；然后根據每類線段的長度加權平均方位角調整每一條線段，計算出線段的新端點，即保持A類線段平均方位角不變，將B類線段平均方位角強制與其正交，得到B類線段新的平均方位角；然后調整每條線段，以線段中心點為軸心，將線段調整至新平均方位角，并求出新線段兩兩相交的交點作為新的端點；最后將所有新的端點依次首尾相連，得到一個規則化的建筑物外輪廓線(圖2右圖).

2.2 屋頂面內輪廓線提取

2.2.1 屋頂面聚類

要實現屋頂面內輪廓線提取，首先需要將復雜的屋頂面進行分割聚類，其中，具有代表性的聚類算法有：

1)區域增長法，該方法首先計算三角面片的局部特征(如法向量)，然后根據面片的連通性和局部特征之間的關系來進行聚類，該算法過于簡單，易受局部干擾點的影響；

2)空間Hough變換[20]，該方法通過在參數空間里進行聚類的計算，因此需要對參數空間進行離散化，但離散化的程度會直接影響聚類的精度；

3)RANSAC算法[21]，采用迭代的方式從一組包含離群的被觀測數據中估算出數學模型的參數，該算法可以容忍數據集中含有的噪聲，但它的聚類結果完美貼近數學意義上的一致性，忽略了數據攜帶的幾何特性，因此不適合直接用于復雜建筑的基元提取.

本文提出了一種改進的RANSAC算法，先通過區域增長法粗分割屋頂面，充分挖掘數據中的幾何信息，然后利用粗分割的結果作為先驗知識，采用RANSAC算法從粗到細提取屋頂面.

(1)

建筑物屋頂通常是由多個平面或相對規則的曲面構成的，落在同一屋頂面上的三角面片法向量大致相同，因此，法向量是屋頂面粗聚類的重要特征.首先，隨機定位區域增長的種子點，根據當前三角面片法向量和連通性判斷，使用基于廣度優先遍歷的方法先將周圍最近一圈的三角面片聚為一類，然后不同往外擴張，直至沒有新的面片加入為止.使用RANSAC算法的基本思想是通過迭代隨機的從樣本集S中抽取一個樣本子集S′，計算當前平面模型M，再從S中抽取符合平面模型M閾值條件的樣本子集T，重復以上流程若干次，最后將迭代過程中得到的最大樣本子集T作為最佳子集T*.但該算法存在一個缺陷，如式(1)所示該算法以一定的概率α得到一個滿意的聚類結果.其中，ε為實際模型的概率，必須加大其迭代次數N，才能提高概率α.當遇到復雜數據時，算法的效率將會顯著降低.

針對這個缺陷，本文設計一種基于先驗知識的RANSAC算法提取屋頂面，將粗提取的聚類結果作為樣本集S，利用局部采樣方法獲取樣本子集S′.在α一定的情況下，減少了迭代次數.本系統中迭代次數N設為50，如圖1的屋頂面內輪廓線提取部分的左圖所示，可保證建筑物屋頂大部分平面聚類出來，且聚類時間在可接受范圍內.實驗部分將給出迭代次數的效果比較和具體的效率數據.

2.2.2 內輪廓線提取

內輪廓線主要是指兩屋頂面相交的部分，可分為直交線段和懸交線段，直交線段是指直接相鄰的兩屋頂平面所構成的線段，懸交線段是指非直接相鄰的兩屋頂面向下投影到水平面后，互相緊鄰且不存在重疊部分，但在兩水平面上直接形成了一條明顯的交界線.所以，內輪廓線都在相鄰屋頂面之間產生，準確的找到屋頂面之間的鄰接關系有助于提取出正確的內輪廓線.

本小節首先簡要介紹一下獲取屋頂面之間鄰接關系的操作方法，詳細步驟說明：首先將所有屋頂面上的點云投影到一個水平面，對該平面上的二維點云進行網格化處理，網格單元長度為平均點間距的2倍；然后對每個網格單元進行標記，統計每個網格單元內包含點云數量最多的屋頂面，將該屋頂面ID號作為該網格單元的標識；最后通過遍歷每個網格單元，判斷該單元八鄰域內網格單元的標識符.若兩個標識符不同，則這兩個標識符所對應的兩個屋頂面應為相鄰屋頂面.

(2)

(3)

得到相鄰屋頂面集合后，則可以計算兩個屋頂面之間的內輪廓線.如前所述，內輪廓線段有兩類：直交線段和懸交線段.其中，直交線段可以通過兩平面的平面方程直接求交獲??；懸交線段的計算更為復雜：首先通過將兩平面先投影到一個水平面上，求出水平的候選懸交線段；然后求出該候選懸交線段所在的豎直平面方程；最后將豎直平面方程分別與兩個屋頂平面方程求交，用求直交線段的方法分別求出兩條懸交線段(圖1的屋頂面內輪廓線提取部分的右圖).直線方程可由式(2)的參數方程表示，其中，(a3，b3，c3)代表直線的方向向量，(x0，y0，z0)代表直線上任意一點.直線上任意一點可以取兩個聚類的公共端點，或其中一個聚類的邊緣點.直線的方向向量N3可以通過式(3)計算得到，其中，N1和N2是兩平面的法向量.

2.3 規則化重構

2.3.1 平面基元的生成

平面基元是由線段順序組合而成的閉合區域，平面基元的提取就是要確定每個閉合區域的輪廓，而輪廓是由外輪廓線段和內輪廓線段(直交線段和懸交線段)組成，但上述工作得到的線段端點通常不夠精確，不能直接用于基元的提取.因此，需要對特征線段進行精化，具體是指根據建筑的幾何特征修改線段的端點坐標，使線段端點滿足相同端點坐標重合的條件，同時避免線段“虛相交”和“過相交”.

圖3 規則化重構示意圖Fig.3 Illustration of our regularized reconstruction

如圖3(a)，針對“頂點重合”、“虛相交”和“過相交”這3個問題分別進行一些形式化的定義，以便于對其進行統一處理.其中，將“頂點重合”問題定義為重合約束，是指兩個頂點之間的距離小于一定的閾值；而將“虛相交”和“過相交”這兩個問題定義為共線約束，是指某頂點到一特征線段的距離小于一定的閾值.如圖3(a)，AF、BG、CH和DE為待處理的特征線段，其中兩個頂點A和D具有等式重合約束，應直接滿足式(4)(其中xA、yA為頂點A的x坐標和y坐標，以此類推)；頂點B落在DE直線上，具有共線約束，應滿足式(5)；同理，頂點C也具有共線約束，應滿足式(5).本文通過將特征線段精化問題抽象成等式約束問題來求解，校正完每條特征線段后，按照先前的聚類結果將同一個平面上的特征線段依次按序相連，獲得平面基元(圖1的規則化模型的生成部分的左圖).

(4)

(xB-xD)(yE-yD)-(xE-xD)(yB-yD)=0

(5)

2.3.2 非平面基元的生成

通過恢復所有平面基元每個頂點的高程值，并依序連接構成重構模型的屋頂面；然后將每個屋頂面頂點向地面投影，生成地面頂點，連接相應的屋頂面頂點和地面頂點構成幾何多邊形，作為模型的墻面，類似豎直往下擠壓，生成平面基元的規則化重構結果，但該結果相對于原始模型是不完整的，缺少了因煙囪、太陽能等不規則物體而未被聚類的部分.因此需要將非平面基元部分重構出來.非平面基元由于其形狀不是一個規則的平面，大多是凹凸不平的，所以不能放在屋頂面聚類過程中一起處理提取.本文在提取完屋頂面全部的平面基元后，對剩下的屋頂三角面片僅采用區域增長法，不考慮三角面片法向量之間的關系，進行非平面部分的連通性聚類，找出非平面基元的聚類后，本文將此部分進行平面化處理.如圖3(b)左圖，具體是先通過閾值設定，將大面積的非平面基元的聚類結果進行保留；然后如圖3(b)右上圖所示通過計算當前非平面聚類的中心點O，從中心點O出發找距離最近的兩條輪廓線段，且這兩條線段法向量互相垂直；最后如圖3(b)右下圖所示求出這兩條輪廓線的交點P作為該非平面基元的一個頂點，以該頂點為起始點，向兩邊進行完整性探測，求出另外兩個端點Q和R，最后再恢復出對角線上的頂點，將此非平面基元重構成矩形.

通過恢復所有平面和非平面基元每個頂點的高程值，得到具有三維坐標信息的空間平面.為了獲得封閉的建筑物實體模型，先將每個基元上的頂點依序連接構成屋頂面，然后將每個屋頂面頂點向地面投影，生成地面頂點，并連接相應的屋頂面頂點和地面頂點構成幾何多邊形，作為重構模型的墻面，如圖1右圖所示，往下擠壓生成最終的規則化模型.

3 實驗結果與分析

本文方法已經在2.50 GHz Intel(R)Core(TM)PC機上的Microsoft Visual studio 2017平臺利用C++實現.使用Windows平臺下的OpenGL庫和Qt庫實現基于屋頂面輪廓線提取的規則化模型的重構.其中，利用OpenGL渲染三維建筑物模型，使用Qt進行用戶界面的開發.根據輸入的單幢建筑物的面片數據，自動進行高效的建筑物模型規則化重構，重構過程中，用戶無需具備專業知識與技能，只需進行簡單的參數調整，得到最優的規則化模型即可.

在考慮改進型RANSAC聚類算法迭代次數選取時，針對輸入的三維建筑物，分別給出不同的迭代次數本文方法的聚類效果如圖4所示.表1所示為對于不同迭代次數所需的聚類時間，可以看出，迭代次數N取50次時，聚類時間較快，且結果更精確.因此，本實驗中所有模型在聚類時迭代次數N設定為50.

圖5所示為本文方法與PolyFit方法的效果比較，針對單幢三維建筑物，PolyFit方法首先通過改進過的RANSAC聚類方法進行點云的聚類，然后用聚類出的結果將模型切割成小塊的平面，再規則化提取出的平面，最后將問題轉化為二進制標記問題，選出適合的候選平面，從而擬合出規則化重構模型.由于PolyFit方法對模型精度要求較高，本文分別將輸入模型的點云進行采樣至10萬個、20萬個和30萬個，然后用PolyFit方法進行化簡.圖5(b)、(c)為點云采樣至10萬個和20萬個的結果，可以看出PolyFit方法雖然可以快速簡化出結果，但其過于追求模型的密閉性和整體性，模型中的一些局部特性(如邊之間的平行性)不能很好的保留下來；而增加采樣個數至30萬個，由于聚類出的平面個數過多，PolyFit方法在二進制標記求解過程中陷入了復雜的計算中，無法輸出最后的規則化重構結果.相對而言，本文方法能夠規則化重構出更為精確的三維模型，且無需手動交互，大大減少了簡化時間，提高了算法的效率.

圖4 不同迭代次數下的聚類結果Fig.4 Clustering results with different iterations

表1 不同迭代次數下聚類時間統計Table1 Clustering time statistics under different iterations

圖5 本文與PolyFit方法比較Fig.5 Comparison between our method and PolyFit

值得指出的是，本文方法在場景中的規則化重構結果如圖6(b)、(d)所示，能較好地實現絕大部分建筑物的規則化重構.圖6(e)為場景中若干實例的規則化重構結果，其中，第1行為輸入的原始三維建筑物模型，第2行表示最后的規則化重構模型.從圖6(e)中可以看出，對于具有3個、5個和6個等不同屋頂面個數的建筑物，本文方法均能實現高效的模型規則化重構.與已有規則化重構方法比較，本文方法針對屋

圖6 更多建筑規則化重構結果Fig.6 More results

頂由多邊形組合成的建筑物在簡化過程中交互簡單，且能高效地實現貼近原始三維模型的簡化效果.此外，對于非平面組成的構件(如太陽能、煙囪等)，本文方法可以有效利用基元之間的相鄰關系將非平面基元恢復成平面基元并完成規則化重構.然而，文方法難以處理由圓柱體、圓錐體、球體等部件組成的屋頂，未來將進一步考慮，使建筑物規則化重構方法適用性更廣、實用性更強.

4 結 語

本文針對傾斜攝影技術重建的三維建筑模型，提出了一種基于屋頂輪廓線的三維建筑模型規則化重構方法，能夠將復雜的、帶噪聲的三維建筑網格模型重構簡化為簡單、規則的建筑模型，首先分割屋頂并提取屋頂的外輪廓線，并對粗糙的外輪廓線進行精化；接著通過改進的平面擬合提取屋頂的內輪廓線；最后組合內外輪廓線，利用重合約束和共線約束進行優化生成平面基元；針對屋頂面中的非平面部分，本文通過連通性聚類進行規則化保留.本文方法不依賴用戶交互和先驗信息，實驗結果表明了，本文方法在精確性和魯棒性兩個方面的優勢.

然而，本文方法僅適用于屋頂由多邊形組合而成的三維建筑物模型，對于其他更為復雜的建筑物(如屋頂由圓柱體、球體等構成的建筑物)，則是未來需要進一步考慮的.另一方面，本文方法并沒有考慮門、窗和陽臺等細節的規則化.由于傾斜攝影技術重建的三維建筑模型精度并不高，直接對這些細節進行規則化的精度較差，將來可以利用深度學習技術對它們進行識別后再處理，或許能實現細粒度的三維建筑模型規則化重構.