基于特征感知的三維點云簡化算法研究

蘇江姍

（四川大學計算機學院，成都610065）

0 引言

隨著三維激光掃描技術和硬件處理能力的提高，使用點云對三維模型進行表示和繪制在過去十幾年中得到了廣泛的應用，點云模型的處理技術也受到了計算機圖形領域的關注。隨著掃描設備的精密化，獲得的點云數據精度和密度越來越高，若直接對點云數據進行管理與渲染會消耗計算機大量的處理時間，并且會占用很大的儲存空間。在實際應用中，高精度的點云在許多情況下并不必要，因此多三維點云模型進行簡化就十分有必要。

早期點云簡化算法主要研究在簡化的過程中如何更好地保留點云模型的集合特征。Alexa[1]提出基于移動最小二乘法（MLS）的簡化方法。該方法的主要思想是計算每個點到MLS 擬合平面的距離，并且不斷移除距離最小的頂點。Scheidegger[2]提出將基于MLS 的方法擴展至局部鄰域點的擬合曲面簡化。Pauly[3]基于曲面變化度分別提出頂點聚類法、迭代法和粒子模擬法，對比三種簡化方法在不同衡量標準下的優劣得出結論。基于迭代的簡化方法具有最小的簡化誤差，但在簡化過程中無法控制簡化后頂點的密度。頂點聚類法具有最快的簡化效率，但簡化前后模型產生較大的誤差。基于粒子模擬的簡化方法可以較好地控制模型表面頂點的分布，但簡化效率不佳。Song[4]提出基于全局聚類的點云簡化方法，該方法通過使得簡化前后的幾何誤差最小化得到全局最優解。

點云模型數據除了能表示模型的位置信息，有些點云數據還含有法線顏色信息。因此在簡化時考慮顏色誤差、法線變化率等也成為了相關領域研究者的關注點。Miao[5]提出了一種可以識別曲率的適應性采樣算法，該研究提出了一套適應性的均值漂移聚類方案來生成非均勻分布的采樣結果。Huang[6]提出了保留幾何和顏色特征的誤差度量方法，優先考慮對誤差較小的局部鄰域合并達到簡化目的。Leal[7]提出基于點云局部密度的簡化方法，該方法對點云中的噪聲點和異常點具有較好的魯棒性。

在點云簡化算法研究中，如何在最大程度地保留細節特征的前提下減少點云數據量是研究的關鍵。現有的點云簡化方法可分為兩類：一類方法是基于頂點聚類的簡化，另一類則是計算點云局部復雜度并迭代刪除頂點的簡化。

基于頂點聚類的簡化方法分為兩種：一種是基于體素劃分的點云聚類。對點云模型按照一定的單元大小進行空間上的均勻體素劃分，并將點云中的點劃分到相應體素單元中，每個體素單元保留離質心最近的頂點作為該體素的簡化結果。由于體素尺寸的固定，該方法不能適用于不均勻采樣的點云模型，并且在均勻采樣的模型細節復雜處與模型細節簡單處保留大致相同的頂點數，導致模型細節在簡化后得不到更好地保留。同時，使用該方法時如果體素尺寸過大，模型表面不連接的部分容易被劃分至同一體素，造成簡化結果錯誤。另一種是基于點云模型表面的聚類，可以將整體點云模型自上而下進行劃分生成基于模型表面的聚類，也可以通過區域增長法收集鄰近點云區域逐漸產生基于模型表面的聚類。該方法適用于均勻與不均勻采樣的點云模型，但該方法在聚類時僅考慮在局部區域尋找最優解，因此會造成部分生成的聚類跨越特征邊界的問題。另一類基于迭代刪除點的簡化方法則是通過在一定鄰域內計算點的局部曲面參數值和顏色變化度來衡量局部表面的復雜程度，根據點云模型中點的局部復雜度由小至大迭代地刪除頂點達到點云簡化目的。

1 算法實現

1.1 算法描述

本文對點云場景簡化方法進行研究，基于迭代和聚類的點云簡化思想，提出基于特征感知的點云簡化方法，通過最大程度保持點云模型表面的幾何與顏色特征并減少點云數據量達到簡化目的。通過衡量局部半徑內點云簡化前后產生的幾何和顏色誤差作為誤差度量因子，按照每個點的誤差由小至大迭代地進行鄰域內的頂點聚類，直到簡化程度達到用戶設定的簡化率。最后，實現基于點的渲染方法達到可視化的目的。假設當前頂點p的誤差搜索半徑為r，即簡化后點云半徑為r，逐頂點計算的誤差簡化公式為：

其中f(r,p)為頂點p在r半徑內的誤差公式，ΔG為幾何誤差，ΔC為顏色誤差，α為誤差權重值。

1.2 幾何誤差度量

本文使用點云模型表面的曲面變分來估計點云局部曲面的幾何誤差ΔG，此方法可以簡單有效地反映模型表面的曲面復雜程度。曲面變分的數值越大則表明在模型局部的曲面越彎曲，若曲面變分的數值越小則表明局部點云越平坦。

假設點云模型中的任意一點記為pi，該點周圍半徑內點記為pk，其中pk∈NB(pi)，NB(pi)表示以pi為中心，一定半徑的鄰域內的K 個數據點，為pi周圍鄰域點的均值，即：

點pi的協方差矩陣定義為：

其中Ci是對稱半正定矩陣，有性質：對稱半定矩陣的特征值為實數，因此該矩陣存在三個實數特征值，設為x=m(u):R2→R2，它們對應特征向量分別為v1、v2和v3，v2和v3張成了點pi處的最小二乘擬合平面，v1則是該擬合平面的法向量，λ1大小表示局部鄰域擬合的曲面在pi處沿法向方向的變化量。曲面變分則定義為：

1.3 顏色誤差度量

本文使用一定半徑內頂點的顏色與平均顏色色差的方差作為顏色誤差的度量因子ΔC，即評估一定半徑內頂點顏色之間的相似程度。本節首先介紹RGB顏色空間存在的局限性，對HSV 空間色差的計算進行詳細敘述。

RGB 顏色空間是使用最為廣泛的顏色空間，該顏色空間利用三個通道表示顏色：紅色R、綠色G 和藍色B，通過這三個顏色分量的線性組合來表示其他任何顏色。但當需要對顏色進行連續變換時，并不能通過調整三個分量直觀地反映顏色連續變化。同時，表示在自然環境下獲取的顏色對亮度信息非常敏感。而通過調整RGB 分量達到亮度變化，需要對三個分量都進行調整，這種方式是不夠直觀的。最后，人眼對紅綠藍三種顏色分量的敏感程度也是不同的，眼睛對紅色較為不敏感，卻對藍色最為敏感，因此使用RGB 顏色空間表示的顏色，通過人眼觀察均勻性較差。

在精確表示顏色處理的應用中，使用的通常是HSV 顏色空間的信息。HSV 顏色空間可以更直觀地表達顏色的色調、明暗、鮮艷程度。方便對不同的顏色進行統一規范的比較。

由于水文序列的隨機性、灰色性以及不穩定性等特征，在對徑流量進行模擬預測時產生了較大的誤差。而誤差修正模型則是對當前預測模型的補充，該方法即克服了單一方法的局限性，又高效地提高了預測模型的適用范圍以及其預測精度。文中采用ARIMA模型來對徑流量模擬產生的誤差進行修正，其具體步驟如下：

HSV 顏色空間可以表示為一個圓錐模型，這個模型中的顏色參數分別是：色調H、飽和度S 和明度V，如圖1 所示。

圖1 HSV顏色空間模型

由圖1 所示，色差的計算在HSV 空間可以轉換成圓錐上點的距離。在斜邊長R，底面圓半徑為r，高為h的HSV 圓錐體模型中，以地面圓心為原點，H=0 為x軸正方向建立坐標軸。假設色值為（H，S，V）的點的三維坐標為（X，Y，Z）：

2 基于Surface Splatting的點云渲染

2.1 算法思想

為避免在使用基于點的渲染方式進行渲染時，點與點之間有鏤空的問題，基于面片的渲染算法將每個點視為點面元（Surfel），通過這些面元形成幾何表面進行渲染。Zwicker[8]提出了基于橢圓加權濾波（Elliptical Weighted Average，EWA）的渲染框架。該渲染框架的主要思想是在世家坐標系下利用一定鄰域內的點集作為輸出，重建出連續的幾何表面。但是點集經過模型變換、視角變換、投影變換等操作后，在屏幕坐標系下的幾何形態會出現明顯的扭曲走樣。因此需要直接在屏幕空間下進行二維圖像的重建工作，生成光滑形態正常的結果。

2.2 算法流程

首先利用一定鄰域內的點來對模型表面進行擬合。如圖2 左所示，模型表面局部鄰域內任意一點Q的屬性是通過鄰域內的點集使用定義在二維局部空間下的三維重建核擬合而成。該算法將連續曲面函數fc(u)定義為：

其中，k表示鄰域點集，wk表示點的屬性，例如坐標、法向量、顏色等。rk表示二維局部空間下的三維重建核，u為在局部坐標系下的曲面上任意一點。

圖2 EWA基本思想[8]

接著，將連續曲面函數映射到屏幕空間，基本思想如圖3 所示。該算法定義了從局部參數坐標系到屏幕坐標系的映射關系x=m(u):R2→R2，通過映射變換得到屏幕空間下連續曲面函數：

圖3 局部坐標到屏幕坐標的映射[8]

其次，需要對曲面函數進行低通濾波處理。在經過模型變換、視角變換、投影變換等操作后，生成屏幕上的像素會產生走樣現象，因此需要進行濾波處理。定義h(x)為低通濾波函數，與gc(x)進行卷積運算得到處理后曲面幾何函數

其中，pk是屏幕空間下的重采樣核。

Surface Splatting 是一種新的點云渲染方法，它將EWA 的優點用于基于點的表面的表示和渲染。該算法提供了一個完整的數學分析過程，從空間中不規則的點通過數學變換得到了基于二維屏幕坐標的函數。

3 實驗結果

本節將會展示點云模型使用我們的簡化算法得到的簡化結果，利用基于Surface Splatting 方法進行渲染，驗證簡化算法的正確性。實驗設備為：

CPU：Intel Core i3-4160 CPU@3.60GHz

RAM：8.0GB

System：Windows 10

GPU：NVIDIA GeForce GTX 1050

圖4 展示了熊貓原始點云模型以及簡化率為25%、50%和75%時相同簡化半徑點云的效果。

圖4 不同簡化率下的簡化效果

圖5展示了簡化率為50%的屋頂模型在使用幾何誤差和顏色誤差作為誤差度量因子的簡化結果，其中使用幾何誤差作為度量因子的簡化結果較好地保留了模型的幾何特征，使用顏色誤差作為度量因子的簡化結果更好地保留了模型的顏色特征。

圖5 簡化率為50%時使用幾何誤差和顏色誤差的簡化效果

4 結語

本文給出了基于特征感知的三維點云簡化算法，通過輸入初始點云數據和簡化率目標，生成簡化后的點云模型，并對簡化前后的點云模型使用基于點的渲染方式進行可視化，驗證了簡化方法的有效性和正確性，得到的簡化后模型數據可進行管理和處理。

雖然我們的方法可以得到保留幾何和顏色特征的簡化后的模型數據，但是當模型使用基于點的渲染方式進行可視化時，使用上述方式無法保證模型表面頂點的分布足夠均勻，即簡化后模型并不能保證在用點的渲染方式獲得最優效果。因此，在后續的研究中會考慮模型表面點的分布情況，將模型局部頂點的緊密度作為誤差度量因素，保證簡化后的點云在可視化時有最優效果。