一種改進的折線逼近算法在建筑物輪廓線規則化中的應用研究

摘要：建筑物輪廓線的規則化是提取建筑物形狀信息的重要步驟，文章對多邊形建筑物輪廓線規則化進行研究，采用折線逼近算法以及改進后的折線逼近算法分別對多邊形建筑物輪廓線進行規則化試驗，實驗結果表明，基于輪廓曲率角點的折線逼近算法能夠有效規則化建筑物輪廓線。

關鍵詞：折線逼近；輪廓曲率角點；建筑物輪廓線；規則化

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2025）06 -0131-03開放科學（資源服務）標識碼（OSID）：

0引言

目前，多邊形建筑物輪廓線規則化的算法主要基于最小擬合誤差原則進行形狀逼近，主要有兩種方法：首先是折線逼近算法，在滿足精度要求的前提下，通過多段折線實現最佳逼近[1]；其次是利用多邊形的角點，通過提取多邊形輪廓線的特征角點，重建多邊形輪廓線[2]。

關于建筑物輪廓線規則化研究，很多學者采用先計算建筑物的主導方向，再判斷主導方向是否與建筑物的邊緣輪廓線正交，最后利用正交約束，直角約束等條件進行處理。此種方法對于沒有正交關系的建筑物輪廓線效果不佳。例如吳秀蕓[3]采用的算法只適用于規則形狀的建筑物輪廓線。本文采用結合基于輪廓曲率檢測角點的折線逼近算法進行建筑物輪廓線規則化的應用研究。

建筑物輪廓線多為多邊形，多邊形可以用一個二元組來表示：M=（K，V），二元組中V是多邊形上全部頂點的集合；K是M中拓撲連接關系的集合，且每個頂點有且只有兩條鄰邊。對于已知的多邊形，其輪廓線簡化原則是需要盡量保證簡化后的多邊形與已知的多邊形在形狀上保持一致，在此前提條件下，減少頂點或角點個數。

1建筑物輪廓線鏈碼跟蹤

利用折線逼近算法進行輪廓線規則化之前，先要得到輪廓點，再使用折線逼近算法進行建筑物輪廓線的規則化。在計算機中，物體的邊界由多個相鄰的像素點表示。一條曲線可以用曲線遍歷的起始點和各邊界點的方向碼值進行定義，此方法被稱為鏈碼表示法。鏈碼根據中心像素點的鄰接方向分為4連通鏈碼和8連通鏈碼[4]。

本文利用8連通鏈碼輪廓線跟蹤算法來跟蹤邊界線，8連通鏈碼表示任意一個像素周圍均有8個鄰接點，與像素點的實際相符。8連通鏈碼跟蹤物體輪廓的示意圖如圖1所示。

建筑物輪廓線一般是封閉的連通區域，分別對多個連通區域進行標記并依次逐個跟蹤，本文8連通鏈碼的輪廓跟蹤具體步驟如下。

1）按照順序遍歷建筑物輪廓圖像，最小行值和最小列值作為首個輪廓起始點，定義掃描方向變量a，變量用來記錄遍歷輪廓點的移動方向，初始值為7；

2）按照逆時針方向搜索當前像素周圍3×3鄰域的范圍，對于8連通區域，若掃描方向變量a 為奇數，取（a+7）mod 8；若a為偶數，取（a+6）mod 8，本文實驗掃描方向變量a 的起始值為7；在3×3鄰域中遍歷搜索到的第一個點與當前像素值相同的像素點，則認為是新的邊界輪廓點n，與此同時，變更掃描方向變量a 作為新的方向值。

3）如果點n 等于第二個邊界點，并且前一個邊界點n-1等于第一個邊界點，就停止搜索，完成鏈碼跟蹤，否則繼續進行第2個步驟繼續進行鏈碼跟蹤；

4）最后將由邊界點0、1、2......構成鏈碼跟蹤邊界。利用實驗數據，通過輪廓線的8鄰域鏈碼跟蹤得到的輪廓點如圖2所示，圖2（a）中表示跟蹤的邊界輪廓點，圖2（b）是局部放大圖。

2折線逼近算法

折線逼近算法旨在利用少數關鍵點或特征點對多邊形進行擬合，在保證物體輪廓線特征的情況下，最大限度地減少輪廓線的數據量[5]。國內外學者做過相關研究，如Ray的順序法[6]、Dinesh和Damle的分裂融合法[7]、Carnona Poyato 和Fernadez Garcia 的支配點檢測法[8]、Shu和Luo的基于幾何矩計算的方法[9]等。該算法通過多段直線擬合不規則曲線，對于檢測出來的輪廓點，進行折線最佳逼近，得到較規則的圖形。

折線逼近算法用于二維平面中給定的一個由N 個點組成的數字輪廓曲線，從這N個點中，選出M個點組成新的多邊形，由最終的多邊形來代表原始輪廓線[10]。在利用鏈碼跟蹤算法對建筑物輪廓線進行跟蹤之后，根據得到的輪廓點進行折線逼近，折線逼近算法的原理示意圖如圖3所示。

折線逼近算法的步驟如下：

1）首先確定閾值ε，用于判斷點到直線的距離與閾值ε 的大小關系。

2）在同一連通區域內，對輪廓線上的點進行折線逼近，對每條輪廓線上首尾兩點連成一條直線，成為基準線，求出所有點與基準線的距離，并找出距離的最大值d_max，比較d_max 與閾值ε 的大小。如果d_maxlt;ε，則刪除曲線上中間的所有點，首尾兩點的連線即為折線逼近結果。如果存在d_max≥ε，則將距離基準線最遠的點標記為第i個點，刪除基準線，并將第一個點和第i個點，以及第i個點和最后一個點連線，形成的新的基準線，如圖3中的直線P₁P_i 和直線P_iP_j 即為形成的新的基準線。

3）重復步驟（2），繼續計算折線上的點到新的基準線的距離，并判斷距離的最大值d_max 與ε 的大小關系。直到所有的點到基準線的距離都小于ε 時，保留的基線即為折線逼近的結果。

通過鏈碼跟蹤的輪廓點數據進行折線逼近擬合建筑物輪廓線，為了能夠得到較規則的輪廓線結果，文中對折線逼近的結果進行了平滑處理，實驗結果如圖4所示。實驗可知，運用折線逼近算法進行輪廓線規則化，能夠得到平滑的建筑物輪廓線，但輪廓線直角處同時被平滑，最終會存在直角圓弧化的現象。算法忽略了輪廓線角點的重要作用，所以直接用折線逼近算法得到的結果不能夠滿足建筑物輪廓線規則化的要求。

3基于輪廓曲率角點的折線逼近

為解決上述問題，采用基于輪廓曲率檢測角點的折線逼近算法進行建筑物輪廓線的規則化。基于輪廓曲率的多邊形角點檢測算法[11]一文已明確物體的形狀是反映物體特性的關鍵因素，形狀信息是通過形狀的邊界輪廓線來反映，而最能反映輪廓線特性的是輪廓線上曲率變化較大的點，即角點。

基于輪廓曲率角點的折線逼近算法是利用基于輪廓曲率角點檢測算法檢測出來的圖像角點進行限制，設定角點分別為（x₁ ，y₁），（x₂ ，y₂），……（x_n ，y_n），首先查找圖形的連通區域，若存在多個連通區域，分別對連通區域進行標記，然后依次對每個連通區域內相鄰的輪廓角點作為折線逼近的首尾兩點，連接這兩點進行折線逼近。該方法首先利用輪廓曲率角點檢測算法檢測出的兩個相鄰角點作為曲線的兩個端點，然后根據折線逼近算法進行實驗。算法的具體流程與折線逼近算法類似，結合輪廓曲率算法檢測出的角點作為折線逼近的兩個端點，再利用折線逼近算法進行規則化實驗，實驗結果如圖5所示。可以看出，結合輪廓曲率角點的折線逼近的效果仍不理想，輪廓曲率角點檢測算法在支撐區域較小的情況下，檢測出來的角點不夠齊全，會出現圖中輪廓直角并非嚴格正交，如圖中標注的虛線框部分。針對上述問題，本文制定了輪廓線規則化的基本原則，規則化的基本原則如下：

1）通過輪廓線檢測得出角點坐標（x₁ ，y₁），（x₂ ，y₂），……（x_n ，y_n），每相鄰兩點可以確定一條直線，按照順時針依次計算相鄰直線段之間的夾角，夾角可由余弦計算公式求出。

2）判斷計算出的直線夾角與90°的差值，設定15° 為夾角差值的閾值。如果計算出來的角度差值小于閾值，則進行直線正交化。將兩直線段中較短的直線段強制正交于較長的直線段，使建筑物輪廓角嚴格直角化。若角度差值大于閾值，則不進行直線正交化，保留原狀。

3）若計算出的直線夾角大于90°且與180°的差值小于設定的閾值，此處閾值也是15°，通過設定的閾值，可判斷這兩條之間的夾角接近于水平角，則將兩直線段合并成一條直線。其他夾角的情況不進行任何處理。

4）若連續出現較多鋸齒狀，且直線段較短，直線之間的夾角接近于180°，則將鋸齒狀首尾的點連成直線。

通過上述方法對建筑物輪廓線進行規則化結果如圖6（a），根據航拍影像圖6（b）的判斷，本文規則化結果符合實際情況。規則化的結果能夠基本能將具有正交關系的建筑物輪廓線正交化。圖6（c）是將規則化的建筑物輪廓線疊加到原始點云生成的深度影像上進行比較，從疊加效果圖上可以看出本文算法基本能夠得到較為滿意的規則化結果。

4 結論

在角點檢測全面且準確的情況下，基于輪廓曲率角點的折線逼近算法能夠有效規則化建筑物輪廓線。如果角點檢測不夠全面，則需依據規則化原則對建筑物輪廓線進行規則化。本文的規則化原則在一定程度上能夠滿足建筑物輪廓線規則化的要求，但該算法沒有考慮到弧線的規則化，算法還存在可改進的地方，值得進一步研究。