喬周民 侯岳 蔣達(dá)

摘 要：本文對(duì)建筑物點(diǎn)云分割與提取的方法和流程進(jìn)行研究。在研究過程中，通過對(duì)建筑物頂面進(jìn)行分割，提取出建筑物各頂面的點(diǎn)云，精確構(gòu)建建筑物房頂面片，進(jìn)而實(shí)現(xiàn)建筑物的三維重建。

關(guān)鍵詞：點(diǎn)云數(shù)據(jù)；法線；曲率；鄰域點(diǎn)集

中圖分類號(hào)：TP311.52 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-5168（2018）17-0013-02

Research on Point Cloud Segmentation and Extraction

Technology Based on Buildings

QIAO Zhoumin1 HOU Yue2 JIANG Da2

Abstract： In this paper， the method and process of segmentation and extraction of building point cloud were studied. In the study， the top surface of the building was extracted by dividing the top surface of the building， and the top surface of the building was accurately constructed， and then the three-dimensional reconstruction of the building was realized.

Keywords： point cloud data；normals；curvature；neighborhood point set

雖然建筑物的頂部造型各異，但一般都由一個(gè)或者多個(gè)平滑表面組成。目前，處理建筑物的點(diǎn)云分割算法主要有隨機(jī)抽樣一致性算法[1]、聚類算法、區(qū)域增長算法和3D霍夫變換等。當(dāng)提取大面積的建筑物頂部形狀時(shí)，由于建筑物頂部造型不一樣，組成頂部的面片大小不同，難以采用統(tǒng)一的參數(shù)對(duì)范圍內(nèi)所有的建筑物頂部面片進(jìn)行分割處理。本文通過點(diǎn)云數(shù)據(jù)法向量的分析建立了一種建筑物頂面區(qū)域增長分割種子點(diǎn)選取和特征參數(shù)的設(shè)置方法。

1 法線的計(jì)算與曲率的估計(jì)

法線[2]是描述曲面特征的一項(xiàng)重要指標(biāo)，法線的估計(jì)對(duì)曲面特征的描述有著不可估量的意義。在三維空間中，法向量通常被表示為具有3個(gè)變量的矢量，一般用[n=x，y，z]表示。一般情況下，對(duì)于一個(gè)孤立的點(diǎn)，認(rèn)為其是沒有法向量的，但如果用一系列孤立的點(diǎn)表示一個(gè)物體時(shí)，可以利用孤立點(diǎn)[Pi]及其臨近點(diǎn)擬合出一個(gè)曲面，用曲面的法向量近似代表該點(diǎn)的法向量，這樣，就定義了孤立點(diǎn)的法向量。法向量的計(jì)算方法[3]有很多種，根據(jù)算法思想可以歸為2類：一類是擬合出[Pi]及其附近點(diǎn)的曲面，利用曲面的法線向量近似代替[Pi]的法向量；另一類是直接利用[Pi]及其附近點(diǎn)推算[Pi]的法向量。本論文用第二類方法計(jì)算[Pi]的法向量。該方法應(yīng)首先確定[Pi]的鄰域點(diǎn)集，然后計(jì)算該點(diǎn)的法線和曲率。

2 鄰域點(diǎn)集的確定

對(duì)于給定點(diǎn)[Pq]，其臨近點(diǎn)集[Pk=P1kp，Pk2…Pkk]，定義鄰域的概念為：

[pik-pq≤dm] （1）

式（1）中，[dm]是臨近點(diǎn)到定點(diǎn)的最大允許距離，[·x]是閔可夫斯基距離范式的一個(gè)實(shí)例。鄰域點(diǎn)集[Pk]的數(shù)量k可以預(yù)先設(shè)定。

如果采用公式（1）對(duì)所有點(diǎn)云進(jìn)行最鄰近點(diǎn)的搜索，工作量巨大且搜索過于頻繁，導(dǎo)致搜索過程沒有太大的意義，因此本文利用近似最近鄰搜索算法[4]。

該方法可描述為：在可接受的誤差范圍內(nèi)，設(shè)定一參數(shù)[ε≥0]，獲取的鄰域點(diǎn)集[Pki]到給定點(diǎn)的距離與最鄰近點(diǎn)[qk]到給定點(diǎn)的距離之比不超過[1+ε]，即

[pki-pqx≤1+εqk-pqx] （2）

為了加快計(jì)算速度，本文采用了一種基于K-D tree[5]的最鄰近搜索算法在多維空間中實(shí)現(xiàn)點(diǎn)的最鄰近搜索。若按使用的角度，該算法實(shí)現(xiàn)查詢點(diǎn)[Pq]的鄰域點(diǎn)集[Pk]可通過2條途徑：①確定與查詢點(diǎn)[Pq]的最鄰近的k個(gè)點(diǎn)（k-search）；②確定與查詢點(diǎn)k的距離在半徑r內(nèi)的所有k個(gè)點(diǎn)（r-search）。

基于K-D tree最鄰近搜索算法實(shí)現(xiàn)的關(guān)鍵是設(shè)置合理的參數(shù)，即如何設(shè)定k值和r值才能最優(yōu)地實(shí)現(xiàn)鄰域點(diǎn)集的搜索。k值和r值作為閾值，其設(shè)定的尺度大小是影響估算搜索點(diǎn)法線方向的重要因素，如果設(shè)定的尺度較為合理，估算的法線方向會(huì)趨于真實(shí)方向，如果設(shè)定的尺度過大，估算的法線方向和真實(shí)方向會(huì)有所偏差。

3 法線的計(jì)算

求表面某點(diǎn)[Pi]的法向量問題近似于求一相切面的法線問題，即求在鄰域點(diǎn)集[Pk]中最小二乘平面擬合問題，若平面用一個(gè)點(diǎn)x和一個(gè)法向量[n]表示，那么[Pi]到平面的距離定義為：

[di=pi-x·n] （3）

其中，x和向量[n]使用最小二乘法計(jì)算，即

[di=0] （4）

定義x為點(diǎn)集[Pk]擬合平面的中心，即

[x=P=1k·i=1kPi] （5）

計(jì)算法向量[n]可采用主成分分析法，那么計(jì)算表面法線的問題就變成分析一個(gè)協(xié)方差矩陣的特征矢量和特征值，這個(gè)協(xié)方差矩陣從查詢點(diǎn)的臨近元素中創(chuàng)建，假如協(xié)方差矩陣用C表示，那么：

[C=1ki=1kξi·pi-p·pi-pT] （6）

[C·vj=λ·vj，j∈0，1，2] （7）

4 曲率的估計(jì)

曲率是衡量幾何體不平坦程度的指標(biāo)，把曲率的概念引入點(diǎn)云中，是為了描述點(diǎn)[Pi]和其臨近點(diǎn)之間的緩急關(guān)系。對(duì)于曲率的估算方法，國內(nèi)外學(xué)者已做了大量的研究，有很多種方法定義一點(diǎn)所在曲面的曲率，但這些方式一般要求表面已被表示為三角網(wǎng)格，而不僅僅是用一個(gè)孤立點(diǎn)來計(jì)算。例如下面兩種曲率定義方式：

①定義[K，H]來表示某點(diǎn)在曲面的曲率。

[K=k1·k2，H=k1+k22，H2≥K] （8）

其中，[k1]和[k2]是曲面的主曲率。但是，[K，H]代表性較差，主要是由于估計(jì)值的相互作用。

②若用形狀指數(shù)[SI∈0，1]定義曲率，則有：

[SI=12-1πarctan，k1≥k2] （9）

但是，利用該方法定義曲率時(shí)，噪聲點(diǎn)對(duì)結(jié)果的影響較大，且不能從一組采樣點(diǎn)直接進(jìn)行估算。

本文定義了一種新的曲率表達(dá)，利用主成分特征分析推算點(diǎn)P的曲率，采用協(xié)方差C的特征值[λj]近似作為P點(diǎn)的曲面變化度。如果[λ0=minλj]，那么P點(diǎn)沿曲面法線[n]的變化度可表示為：

[σp=λ0λ0+λ1+λ2] （10）

即最小特征值和所有特征值的比值近似表示以P為中心的k-鄰域曲率值，且用這種表示方式的曲率具有尺度不變性。較小的[σp]，則說明P點(diǎn)的k-鄰域內(nèi)所有的點(diǎn)位于表面的切平面上，因此建筑物頂面分割區(qū)域增長算法中選取最小曲率的點(diǎn)作為種子點(diǎn)。

式中，[σp]的計(jì)算依賴于k值的選取和協(xié)方差C的計(jì)算，且受噪聲的影響較大。本文采用基于最優(yōu)擬合面的協(xié)方差陣C來消除噪聲的影響，即不再采用最小二乘擬合切平面，而是尋找最優(yōu)平面模型。依據(jù)點(diǎn)到最優(yōu)平面的距離[di]的大小，將鄰域[pk]中的點(diǎn)分為內(nèi)部點(diǎn)[di≤dmax]和外部點(diǎn)[di>dmax]，計(jì)算協(xié)方差矩陣時(shí)，內(nèi)部點(diǎn)和外部點(diǎn)采用不同的權(quán)重[ξi]：

[ξi=exp-d2iμ2，pki∈外部點(diǎn)1，pki∈內(nèi)部點(diǎn)] （11）

式中，[μ]表示點(diǎn)[pq]到鄰域點(diǎn)[pki∈pk]的平均距離。

該方法的優(yōu)點(diǎn)在于考慮了外部點(diǎn)的影響，有助于減少噪聲的影響。同時(shí)，在不同的平面接邊處也能得到很好的計(jì)算結(jié)果。平面估計(jì)采用了RMSAC（Randomized M-Estimator Sample Consensus）算法。

參考文獻(xiàn)：

[1]李孟迪，蔣勝平，王紅平.基于隨機(jī)抽樣一致性算法的穩(wěn)健點(diǎn)云平面擬合方法[J].測繪科學(xué)，2015（1）：102-106.

[2]趙春海.三維點(diǎn)云數(shù)據(jù)鄰域搜索與特征描述子提取算法研究[D].秦皇島：燕山大學(xué)，2015.

[3]何望君，劉紀(jì)平，張福浩.一種基于GPU的地形頂點(diǎn)法向量并行計(jì)算方法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2017（7）：734-738.

[4]張婷.基于量化的近似最近鄰搜索技術(shù)研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2017.

[5]劉宇，熊有倫.基于有界kd樹的最近點(diǎn)搜索算法[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2008（7）：73-76.