張睿，余代俊

1. 成都理工大學(xué) 地球科學(xué)學(xué)院，成都 610059；

2. 廣東省建筑設(shè)計(jì)研究院有限公司，廣州 510010

1 引 言

三維激光掃描技術(shù)可快速獲取掃描對(duì)象的表面點(diǎn)云數(shù)據(jù)，基于點(diǎn)云數(shù)據(jù)對(duì)物體進(jìn)行三維重建是當(dāng)前三維重構(gòu)的研究熱點(diǎn)（程效軍和方芳，2014；張娟等，2018)。

對(duì)于完整的三維點(diǎn)云，提取其邊界通常需要將其分割為若干個(gè)面片后對(duì)各個(gè)面片進(jìn)行邊界提取。王瓊等（2017)認(rèn)為點(diǎn)云邊界特征是物體重要的幾何特征，對(duì)三維重構(gòu)起著重要作用。Previtali 等（2014)提出了一種高度自動(dòng)化的方法，該方法首先將建筑立面的點(diǎn)云分割為平面元素，然后利用一些先驗(yàn)知識(shí)從識(shí)別的平面簇中自動(dòng)提取立面隔斷線以供之后生成模型。部分研究借助霍夫變換實(shí)現(xiàn)點(diǎn)云的分割，Song 等（2019)利用三維霍夫變換實(shí)現(xiàn)了大規(guī)模點(diǎn)云的地面提取；Widyaningrum 等（2019)提出有序點(diǎn)輔助霍夫變換（ordered pointsaided Hough transform，OHT)算法，該算法使用有序建筑物邊緣點(diǎn)輔助霍夫變換，進(jìn)而從機(jī)載激光雷達(dá)（light detection and ranging，LiDAR)點(diǎn)云中高質(zhì)量地提取出建筑物輪廓。聞平等（2020)提出漸進(jìn)式建筑物輪廓線提取方法，該方法先通過(guò)漸進(jìn)數(shù)學(xué)形態(tài)學(xué)濾波分離非地面點(diǎn)，然后使用改進(jìn)的三維霍夫變換分類(lèi)出建筑物點(diǎn)云，進(jìn)而提取建筑物輪廓點(diǎn)?；舴蜃儞Q的穩(wěn)健性較好，抗噪性較強(qiáng)，但計(jì)算量較大，對(duì)于稀疏點(diǎn)云可用，但較稠密的點(diǎn)云不太適用該方法。Mineo 等（2019)提出利用鄰域點(diǎn)特征來(lái)提取邊界點(diǎn)，優(yōu)點(diǎn)是能跳過(guò)分割直接提取完整的三維點(diǎn)云輪廓。對(duì)于分割后的點(diǎn)云，常用的邊界提取方法有圖像法、區(qū)域增長(zhǎng)算法、alpha-shapes算法等。鄒紀(jì)偉等（2020)通過(guò)將點(diǎn)云內(nèi)插為深度圖像，使用圖像邊緣檢測(cè)方法提取邊界?；羝M芃等（2019)指出基于影像的自動(dòng)化提取方式不需要人工干預(yù)，效率較高。該方法的缺點(diǎn)是點(diǎn)云轉(zhuǎn)換影像在重采樣過(guò)程中會(huì)丟失細(xì)節(jié)特征，導(dǎo)致提取邊界精度較低。趙傳（2017)將區(qū)域增長(zhǎng)算法應(yīng)用于建筑物屋頂面輪廓提取，但該算法對(duì)數(shù)據(jù)噪聲、數(shù)據(jù)缺失敏感。詹曦和張建生（2013)使用基于三角網(wǎng)格的邊界提取算法，但由于涉及轉(zhuǎn)換三角網(wǎng)格模型，時(shí)間成本較高。alpha-shapes 算法是近年較為常用的一種提取點(diǎn)云邊界的算法。沈蔚等（2008)將該算法應(yīng)用于LiDAR 點(diǎn)云建筑物輪廓的提取，成功提取出了各類(lèi)凹凸多邊形輪廓線。廖中平等（2019)提出了一種可調(diào)節(jié)滾動(dòng)圓半徑的alpha-shapes 平面點(diǎn)云邊界提取算法，該算法具有良好的穩(wěn)健性。伍陽(yáng)等（2021)提出了一種可自適應(yīng)變換滾動(dòng)圓半徑的alpha-shapes 算法，能夠有效提取機(jī)載LiDAR 建筑物點(diǎn)云頂部輪廓，具有較高的提取效率和良好的穩(wěn)健性，提取的輪廓精度較高。針對(duì)alpha-shapes算法運(yùn)算速度慢的缺點(diǎn)，聶玉澤等（2016)提出了包裹圓算法提取LiDAR 點(diǎn)云的邊緣點(diǎn)，并給出了包裹圓半徑的經(jīng)驗(yàn)值。但包裹圓算法僅對(duì)密度均勻的點(diǎn)云有較好的適應(yīng)性，當(dāng)點(diǎn)的密度分布不均勻或點(diǎn)的密度未知時(shí)，包裹圓算法難以確定包裹圓半徑及包裹圓內(nèi)部點(diǎn)數(shù)的閾值。

本文針對(duì)上述包裹圓算法難以確定包裹圓內(nèi)部點(diǎn)數(shù)閾值的問(wèn)題，提出了改進(jìn)的包裹圓算法，以方位角為基準(zhǔn)將包裹圓劃分為若干區(qū)域，以每個(gè)區(qū)域內(nèi)是否都存在點(diǎn)為條件，判斷各個(gè)點(diǎn)是否為邊界點(diǎn)，避免了閾值選取問(wèn)題，且無(wú)須依賴(lài)點(diǎn)云密度確定包裹圓半徑。

2 包裹圓算法邊緣點(diǎn)提取

對(duì)于建筑物立面點(diǎn)云，提取其輪廓線步驟為：首先，將立面從建筑物點(diǎn)云中提取出來(lái)，其次，通過(guò)旋轉(zhuǎn)算法將立面點(diǎn)云旋轉(zhuǎn)至與某一坐標(biāo)面平行，一般旋轉(zhuǎn)至與XOY面平行，旋轉(zhuǎn)后的立面點(diǎn)即可以用X、Y坐標(biāo)顯示；再次，利用邊緣點(diǎn)提取算法對(duì)建筑物的邊緣點(diǎn)進(jìn)行提??；最后，將提取出來(lái)的邊緣點(diǎn)擬合，形成建筑物的輪廓線。

2.1 包裹圓算法原理

包裹圓算法通過(guò)設(shè)定一個(gè)半徑r及包裹圓內(nèi)點(diǎn)數(shù)閾值h，以點(diǎn)云內(nèi)每個(gè)點(diǎn)為圓心作半徑為r的圓，稱(chēng)為包裹圓，并統(tǒng)計(jì)包裹圓內(nèi)點(diǎn)的個(gè)數(shù)：若包裹圓內(nèi)點(diǎn)數(shù)大于等于h，則判斷該點(diǎn)為內(nèi)部點(diǎn)；否則為邊緣點(diǎn)。以圖1 矩形為例，在邊緣部分以邊緣點(diǎn)為圓心形成包裹圓，包裹圓內(nèi)圓心角有180°范圍內(nèi)沒(méi)有點(diǎn)的存在，角點(diǎn)處有270°范圍內(nèi)沒(méi)有點(diǎn)的存在，以1.5 倍點(diǎn)間距作為包裹圓的半徑，理論上角點(diǎn)包裹圓會(huì)包裹4 個(gè)點(diǎn)，邊緣點(diǎn)包裹圓會(huì)包裹6 個(gè)點(diǎn)，內(nèi)部點(diǎn)包裹圓會(huì)包裹9 個(gè)點(diǎn)。利用落在包裹圓內(nèi)部點(diǎn)數(shù)不同這一特征，可將邊緣點(diǎn)提取出來(lái)。但對(duì)于未知密度或密度不均勻的點(diǎn)云，包裹圓算法很難確定閾值h及包裹圓半徑r，需要不斷人工嘗試以確定，極大影響了算法的自動(dòng)化程度。

圖1 包裹圓算法仿真示意圖（單位：cm)Fig.1 Wrapping circle algorithm workflow（Unit：cm)

2.2 包裹圓算法步驟

包裹圓算法輸入?yún)?shù)為包裹圓半徑r及包裹圓內(nèi)部點(diǎn)數(shù)閾值h，當(dāng)某點(diǎn)的包裹圓內(nèi)部點(diǎn)數(shù)大于h時(shí)，判斷該點(diǎn)為內(nèi)部點(diǎn)；反之則為邊緣點(diǎn)。算法流程，如圖2 所示。

圖2 包裹圓算法流程Fig.2 Wrapping circle algorithm process

3 改進(jìn)的包裹圓算法

改進(jìn)的包裹圓算法將包裹圓按照方位角θ劃分為若干個(gè)區(qū)域，通過(guò)判斷各個(gè)區(qū)域內(nèi)是否都存在點(diǎn)進(jìn)而判斷邊緣點(diǎn)。對(duì)于內(nèi)部點(diǎn)而言，包裹圓的各個(gè)區(qū)域必然都存在點(diǎn)，但邊緣點(diǎn)的包裹圓會(huì)有若干個(gè)區(qū)域不存在點(diǎn)。因此，若某點(diǎn)包裹圓內(nèi)各個(gè)區(qū)域都存在點(diǎn)，則判斷其為內(nèi)部點(diǎn)；反之則為邊緣點(diǎn)。

3.1 改進(jìn)算法步驟

有別于alpha-shapes 算法與包裹圓算法，改進(jìn)算法可應(yīng)用于建筑物整體的輪廓提取，而不局限于單個(gè)立面，即可用于提取三維點(diǎn)云的輪廓，而非僅適用于二維點(diǎn)云。

（1)對(duì)于單個(gè)建筑立面（二維點(diǎn)云)，改進(jìn)算法為：①創(chuàng)建kdtree，用于執(zhí)行半徑近鄰搜索；②選取點(diǎn)云中一點(diǎn)，以其為圓心作半徑為r的包裹圓，并將包裹圓等分為若干個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)的圓心角為θ；③使用半徑近鄰搜索獲取落在包裹圓內(nèi)的點(diǎn)，并計(jì)算落在包裹圓內(nèi)的點(diǎn)所在的區(qū)域；④判斷包裹圓內(nèi)各個(gè)區(qū)域是否都存在點(diǎn)，若都存在則包裹圓圓心為內(nèi)部點(diǎn)，反之則為邊緣點(diǎn)；⑤選取另一個(gè)點(diǎn)為包裹圓圓心，執(zhí)行步驟②、③、④直至點(diǎn)云內(nèi)所有點(diǎn)都遍歷完畢。

（2)對(duì)于建筑物整體輪廓提取，實(shí)施步驟為：①使用隨機(jī)采樣一致性（random sample consensus，RANSAC)算法擬合建筑物中一個(gè)立面（趙燁等，2014；劉亞坤等，2021；鄒鵬等，2020；Wu 等，2021)對(duì)應(yīng)的平面A，獲取該平面相對(duì)準(zhǔn)確的參數(shù)解（雷經(jīng)發(fā)等，2020)，根據(jù)羅德里格斯旋轉(zhuǎn)公式，計(jì)算將該平面旋轉(zhuǎn)至與XOY面平行的旋轉(zhuǎn)矩陣，根據(jù)得到的旋轉(zhuǎn)矩陣旋轉(zhuǎn)點(diǎn)云；②對(duì)點(diǎn)云使用上述提到的單個(gè)建筑立面輪廓提取的算法，該步驟會(huì)提取出建筑點(diǎn)云中所有與平面A平行立面的輪廓；③重復(fù)步驟①、②直至建筑物整體輪廓提取完成。

3.2 時(shí)間復(fù)雜度分析

（1)包裹圓算法主要步驟的時(shí)間復(fù)雜度分析。設(shè)點(diǎn)集內(nèi)有n個(gè)點(diǎn)，對(duì)于算法的時(shí)間復(fù)雜度，每次迭代均需要計(jì)算包裹圓圓心與點(diǎn)集內(nèi)每個(gè)點(diǎn)的距離，該步驟的時(shí)間復(fù)雜度為O(n)；獲取距離小于r的點(diǎn)數(shù)目a，該步驟的時(shí)間復(fù)雜度為O(n)。綜上，包裹圓算法每次迭代的時(shí)間復(fù)雜度為O(n)，由于點(diǎn)集內(nèi)每個(gè)點(diǎn)都需要遍歷，所以需要執(zhí)行n次迭代，算法的總體復(fù)雜度為O(n2)。

（2)改進(jìn)算法主要步驟的時(shí)間復(fù)雜度分析。建立kdtree 在迭代之前進(jìn)行，時(shí)間復(fù)雜度為O(nlogn)，進(jìn)入迭代后，創(chuàng)建包裹圓的時(shí)間復(fù)雜度為O(1)，可以忽略，半徑近鄰搜索的時(shí)間復(fù)雜度為O(n1-1/k+m)，其中，k為kdtree 的維度，m為返回的點(diǎn)數(shù)目，計(jì)算包裹圓內(nèi)各點(diǎn)與包裹圓圓心的位置關(guān)系的時(shí)間復(fù)雜度為O(m)。綜上，改進(jìn)算法每次迭代的時(shí)間復(fù)雜度為O(n1-1/k)，算法的總體時(shí)間復(fù)雜度為nO(n1-1/k+m)。

根據(jù)兩種算法的時(shí)間復(fù)雜度分析，當(dāng)n較小時(shí)，兩種算法的時(shí)間消耗應(yīng)當(dāng)大致相同，甚至在k較大而n較小時(shí)，包裹圓算法的執(zhí)行時(shí)間可能小于改進(jìn)算法；但隨著n增大，改進(jìn)算法與包裹圓算法的時(shí)間消耗會(huì)逐漸接近，當(dāng)n足夠大時(shí)，改進(jìn)算法的時(shí)間消耗會(huì)遠(yuǎn)小于包裹圓算法。

4 實(shí)驗(yàn)與分析

研究以Matlab 為平臺(tái)，以實(shí)際測(cè)量某建筑點(diǎn)云為實(shí)驗(yàn)數(shù)據(jù)。由于邊緣檢測(cè)算法對(duì)離群點(diǎn)和噪聲十分敏感，在應(yīng)用邊緣檢測(cè)算法時(shí)先對(duì)點(diǎn)云做降噪處理（鞏育江等，2022)。

4.1 單個(gè)立面輪廓提取實(shí)驗(yàn)

實(shí)驗(yàn)用點(diǎn)云數(shù)據(jù)，如圖3（a)所示。由于原始數(shù)據(jù)的點(diǎn)密度不均勻，難以使用包裹圓算法提取邊緣點(diǎn)，所以包裹圓算法所用點(diǎn)云經(jīng)過(guò)了體素降采樣，采樣距離設(shè)置為3 cm，取包裹圓半徑為1.5 倍點(diǎn)間距，即4.5 cm，取閾值h=7，結(jié)果如圖3（b)所示。改進(jìn)算法可應(yīng)用于密度不均勻的點(diǎn)云，所以直接使用原始數(shù)據(jù)進(jìn)行處理，取包裹圓半徑r=5 cm，θ=60°，結(jié)果如圖3（c)所示?？梢钥闯觯捎诮?jīng)過(guò)降采樣，包裹圓算法已經(jīng)無(wú)法提取出點(diǎn)云內(nèi)的門(mén)，且包裹圓算法提取的文字邊緣略顯模糊，改進(jìn)算法提取點(diǎn)云輪廓的效果優(yōu)于包裹圓算法，且包裹圓算法必須要應(yīng)用在點(diǎn)密度均勻的點(diǎn)云上，否則很難確定算法的參數(shù)。

圖3 基于點(diǎn)云數(shù)據(jù)的包裹圓算法和改進(jìn)算法兩種方法處理效果對(duì)比Fig.3 Comparison of the processing effects of the wrapping circle method and improved algorithm based on point cloud data

兩種方法提取邊緣點(diǎn)的耗時(shí)對(duì)比，如表1 所示。在點(diǎn)數(shù)較小的時(shí)候，改進(jìn)算法耗時(shí)較包裹圓算法較長(zhǎng)，此時(shí)兩種方法耗時(shí)都較短；隨著點(diǎn)數(shù)的增加，改進(jìn)算法的耗時(shí)增長(zhǎng)更慢，包裹圓算法耗時(shí)的增長(zhǎng)較快，當(dāng)點(diǎn)數(shù)足夠大時(shí)，改進(jìn)算法的耗時(shí)較包裹圓算法大大縮短。

表1 兩種算法提取邊緣點(diǎn)的耗時(shí)對(duì)比Tab.1 Comparison of the time consumption between two methods

4.2 建筑物整體輪廓提取實(shí)驗(yàn)

通過(guò)反射率濾波將反射率較低的部分點(diǎn)（如玻璃窗戶(hù))濾除，研究使用預(yù)處理后的點(diǎn)云，如圖4（b)所示。

圖4 實(shí)驗(yàn)用的原始點(diǎn)云和預(yù)處理后點(diǎn)云數(shù)據(jù)Fig.4 Original point cloud and preprocessed point cloud data used in the experiments

采用傳統(tǒng)的先分割后提取方法與本文的不進(jìn)行分割方法，分別進(jìn)行建筑物的整體輪廓提取，實(shí)驗(yàn)結(jié)果如圖5 所示?？梢钥闯觯嬖谕蛊鸬膲w及一扇凸起的門(mén)，傳統(tǒng)方法提取的輪廓中已丟失這些輪廓，本文方法可很好地保留這些細(xì)節(jié)；且傳統(tǒng)方法在各個(gè)立面交線處有許多冗余的點(diǎn)，這可能是因?yàn)樵诹⒚娣指钸^(guò)程中未能很好地處理交線處的點(diǎn)，本文方法避免了對(duì)交線處點(diǎn)的處理，大大減少了交線處的冗余點(diǎn)。

圖5 本文方法與傳統(tǒng)方法的實(shí)驗(yàn)結(jié)果對(duì)比Fig.5 Experimental comparison of the method in this article and traditional method

相較于傳統(tǒng)輪廓提取算法，研究特點(diǎn)主要體現(xiàn)在：①建筑立面上通常會(huì)有凸起的物體，如空調(diào)、雨棚等，傳統(tǒng)方法通過(guò)點(diǎn)云分割將立面點(diǎn)云分割出來(lái)后會(huì)將其投影為二維點(diǎn)云，在投影的過(guò)程中這些凸起的物體會(huì)丟失，導(dǎo)致提取出的輪廓丟失許多細(xì)節(jié)，改進(jìn)算法提取輪廓可以很好地保留這些立面上的凸起物體，使提取的輪廓細(xì)節(jié)更完善；②傳統(tǒng)方法需要通過(guò)點(diǎn)云分割將建筑物各個(gè)立面提取出來(lái)，提取出的輪廓受點(diǎn)云分割結(jié)果的影響較大，改進(jìn)算法可規(guī)避點(diǎn)云分割這一步驟，避免點(diǎn)云分割結(jié)果對(duì)最終提取出的輪廓的影響且由于無(wú)需處理點(diǎn)云分割的成果，自動(dòng)化程度更高。

5 結(jié) 論

針對(duì)包裹圓算法存在的，處理點(diǎn)的密度分布不均勻時(shí)，難以確定其包裹圓半徑及點(diǎn)數(shù)閾值的問(wèn)題，本文提出將包裹圓劃分區(qū)域，通過(guò)針對(duì)區(qū)域內(nèi)點(diǎn)的分布情況判斷邊緣點(diǎn)的改進(jìn)算法。針對(duì)傳統(tǒng)立面輪廓提取流程受點(diǎn)云分割結(jié)果影響較大的不足，提出了不進(jìn)行點(diǎn)云分割的立面輪廓提取方法。實(shí)驗(yàn)表明：本文的改進(jìn)算法不僅在效果上優(yōu)于包裹圓算法，且自動(dòng)化程度較高，當(dāng)點(diǎn)云規(guī)模較大時(shí)，處理速度也明顯優(yōu)于包裹圓算法；對(duì)于建筑物整體的輪廓提取，本文方法能避免傳統(tǒng)方法由投影帶來(lái)的部分三維細(xì)節(jié)丟失問(wèn)題及點(diǎn)云分割帶來(lái)的立面交線處冗余點(diǎn)問(wèn)題。