基于建筑物的點云分割與提取技術研究

喬周民 侯岳 蔣達

摘 要：本文對建筑物點云分割與提取的方法和流程進行研究。在研究過程中，通過對建筑物頂面進行分割，提取出建筑物各頂面的點云，精確構建建筑物房頂面片，進而實現建筑物的三維重建。

關鍵詞：點云數據；法線；曲率；鄰域點集

中圖分類號：TP311.52 文獻標識碼：A 文章編號：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

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

1 法線的計算與曲率的估計

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

2 鄰域點集的確定

對于給定點[Pq]，其臨近點集[Pk=P1kp，Pk2…Pkk]，定義鄰域的概念為：

[pik-pq≤dm] （1）

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

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

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

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

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

基于K-D tree最鄰近搜索算法實現的關鍵是設置合理的參數，即如何設定k值和r值才能最優地實現鄰域點集的搜索。k值和r值作為閾值，其設定的尺度大小是影響估算搜索點法線方向的重要因素，如果設定的尺度較為合理，估算的法線方向會趨于真實方向，如果設定的尺度過大，估算的法線方向和真實方向會有所偏差。

3 法線的計算

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

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

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

[di=0] （4）

定義x為點集[Pk]擬合平面的中心，即

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

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

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

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

4 曲率的估計

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

①定義[K，H]來表示某點在曲面的曲率。

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

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

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

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

但是，利用該方法定義曲率時，噪聲點對結果的影響較大，且不能從一組采樣點直接進行估算。

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

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

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

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

[ξi=exp-d2iμ2，pki∈外部點1，pki∈內部點] （11）

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

該方法的優點在于考慮了外部點的影響，有助于減少噪聲的影響。同時，在不同的平面接邊處也能得到很好的計算結果。平面估計采用了RMSAC（Randomized M-Estimator Sample Consensus）算法。

參考文獻：

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

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

[3]何望君，劉紀平，張福浩.一種基于GPU的地形頂點法向量并行計算方法[J].遼寧工程技術大學學報（自然科學版），2017（7）：734-738.

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

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