參數曲面理想人造點云生成算法

胡明曉，何才透

溫州大學 計算機與人工智能學院，浙江 溫州 325035

點云通常是3D設備（如3D照相機、LiDAR）采集的結果。曲面點云的處理在模式識別、機器人、醫學影像等領域非常有研究價值，研究人員需要大量的實拍點云進行實驗，以檢驗算法的處理效果和性能。這種實驗不僅費時費力，而且成本昂貴。本文提供一種人造點云的生成算法，能夠快速、廉價地生成大量帶標注3D 點云，以供醫學影像處理、逆向工程等研究者檢驗點云處理算法，為研究人員建立測試數據節省時間和精力[1-2]。同樣，在機器學習領域，也存在點云庫的需求，大量帶標注點云用來測試有監督學習模型的性能和準確度，提高樣本訓練質量[3-4]。此外，人造點云還可應用于教學、廣告、動畫設計等領域。

目前，一些物理掃描方式形成的點云庫已建立，如斯坦福大學的3D Scanning Repository（http：//graphics.stanford.edu/data/3Dscanrep）。本算法面向非物理掃描方式建立大量的帶標注點云，即人造點云或點云生成。目前點云生成的研究涉及以下幾個方面：基于2D 圖像的點云生成、基于已有3D 點云的點云修正（如補全、簡化、下采樣）、基于曲面方程或模型的3D點云生成（如采樣、合成）。

在2D圖像的人造點云方面，有許多研究文獻報道，其中一些研究使用物理模擬、藍噪音采樣等方法由2D模型生成看起來“均勻”的點云圖像[5-7]，也有據2D 照片合成3D點云的研究[8]。

生成式點云補全作為一種特殊的修正點云，近幾年研究較多，文獻[9]采用事件驅動相位噪音方法補全空白；文獻[10]討論了一種基于點素擴散方法（point-voxel diffusion）的3D形狀不可見部位點云補全。這些研究結合機器學習補全點云，不要求與事先給定模型相吻合。通過獲取模型參數（如密度、曲率）再修正點云亦屬人造點云，近年出現的研究有點云簡化[11]、點云下采樣（down-sampling）[12]等。

基于模型或方程的生成點云，已建有一些靜態數據庫，如華盛頓大學的OBJ/PLY2PCD 數據庫（http：//rgbddataset.cs.washington.edu），該庫提供一批RGB彩色點云以及3D實體模型OBJ/PLY到點云的轉換代碼和實例。

3D人造點云方面，用于特定使用場景（如自動駕駛環境）的實時生成算法如文獻[13]；模擬LiDAR拍攝，自動標注點云的算法如文獻[14]。直接基于特定類型3D模型生成點云的研究如Montlahuc 等[15]的CAD 模型模擬點云生成方法，直接以CAD 文件為虛擬物體，生成CAD零件的均勻白噪音點云，同時也能模擬3D攝像機的角度、距離對生成過程進行調節，模擬非理想點云。Chaudhury 等[16]在植物分型（plant phenotyping）研究中亦包含一個基于模型的點云生成步驟，對虛擬植物模型運用類似L-systems 的方法對其表面進行采樣，生成白噪音點云。

基于一般3D 模型的點云生成，Corsini 等[17]介紹一種使用約束Poisson 圓盤生成Monte Carlo 藍噪音點云的方法，該方法適用于曲面的三角網格表示，能產生曲面上均勻的點云。Kang 等[18]根據曲面方程，使用MLS（moving least squares）方法生成均勻、光滑采樣的點云，并經曲面重建檢驗其光滑性，據其實驗效果優于VGD（voxel grid sampling）。Huang 等[19]提出一種FPN點云采樣方法，不同于一般的隨機采樣和最遠距離采樣，而是用快速點云網絡將隨機初始點驅趕至“最合適”的位置。

以上根據方程或模型生成點云的方法要么直接在精確的3D表面上生成點云，著重于點的精確定位，或者滿足一定的光滑性要求，要么僅關注曲面切向的均勻視覺效果，未考慮隨機點云的空間藍噪音化，生成點云不具有厚度。具有厚度尤其是基礎真實（ground truth）厚度的理想化點云在檢驗曲面重建算法和有監督的機器學習中能客觀地反映算法性能，在科研領域存在質和量上的需求，出于這一動機，本課題聚焦于生成具有統一厚度的理想化點云。

精確位于曲面上的點云是厚度為零的點云，一旦厚度加大，涉及法向偏移時，高曲率就會影響點云的理想化程度，因此通過以下創新點在切向均勻化的同時實現法向的模式化分布：

（1）曲率偏差現象的分析和曲率補償；

（2）以法向為主方向的藍噪音模擬。

本研究目標是根據曲面的參數方程生成曲面切向均勻分布、曲面法向模式化分布、等標準差、各向同性的理想化3D點云，所述模式化分布是指密度函數對稱、單調、方差存在的分布，如正態分布、高階柯西分布。

1 問題描述

參數曲面具有解析性好、形式多樣、易于變換、易于插值、能分段拼接形成Bezier 曲面或NURBS 曲面等優點，在幾何建模中廣泛使用，本文選擇參數曲面作為曲面的表示類型。

作為生成點云與之吻合的確定性模型，一般的參數曲面方程為：

其中，u、v為曲面參數。

記一階導數混合矩陣為：

其中，i,j,k為笛卡爾坐標單位向量。

點p(u,v)處的法向量是：

單位法向量N=n/‖n‖2。

2D參數曲線的方程是：

其中，t為曲線參數。

類似地，3D參數曲線的方程是：

在原理示意時本文有時用曲線來說明。

本研究模擬理想3D掃描儀、LiDAR等3D數字化設備的獲取數據，生成人造點云，理想化目標如下：

（R.1）沿曲面（2D時曲線）均勻分布。

（R.2）法線方向點云體密度（2D 時面密度）呈標準差統一為σ的模式化分布(σ2)。

（R.3）3D藍噪音。

（R.4）各向同性。

2 生成算法

已知參數方程（1）中的函數f,g,h及一階、二階導函數。設參數區域為Ω，一般情況下，Ω=[a,b]×[c,d]。如圖1，點云生成的頂層步驟由方程預處理、曲面表面點采樣、法向模式化分布、曲率補償和空間主方向藍噪音模擬組成。在生成過程中，除了指定點數外，還需要指定兩個參量：標準差σ和截尾因子λ，前者用來表征統一的厚度，后者用于實現各向同性。模式化分布密度函數為(x)。

圖1 頂層流程圖Fig.1 Top-level pipeline

2.1 預處理：參數速度上限估計

曲面的參數速度為面積S的微分：

類似地，曲線的情形更簡單，2D 曲線或3D 曲線的參數速度為曲線長度的微分，即：

同樣方法可得上限估計值H。

2.2 曲面表面采樣

通過參數采樣即生成曲面點采樣，需要特別處理之處是要做基于參數速度的調節，保證采樣點的面密度均勻。為此，引入一個輔助隨機變量t。首先，隨機產生Ω×[0,H]中的隨機3D 點(u,v,t)，然后計算s(u,v)，再判斷t＜s(u,v)，如果成立，采樣，否則放棄，重新產生隨機點(u,v,t)。由于參數速度是關于面積微元的變化率，參數速度越快的位置，采樣機會越大，容易分析其切向面密度是均勻的，從而實現理想化目標（R.1）。

2.3 法向模式化分布

在曲面采樣點周圍的3D空間生成3維正態分布的隨機點。從理想點云的要求上看，應該在點的曲面法向上等標準差高斯化，即在法向方向產生以曲面點為中心、以σ為統一標準差的一維模式化分布，以高斯分布為例，相對密度函數為：

本文注意到簡單情況下3D高斯的疊加能生成法向的高斯或其近似，分析如下。

（1）3D平面點云的情況。不妨設O-XY平面分布有面密度為μ，在各中心點p有服從N(p,σ2)分布的3D點云，其疊加分布的密度函數是：

這說明一組點數相同、標準差均為σ的單點正態分布點云均勻分布在空間平面上，其疊加結果在平面法向的邊緣分布上仍服從標準差是σ的正態分布，與切平面平行的任意平面服從均勻分布（f(x,y,z)與x,y無關）。這正是本文想得到的分布。所以只需先產生曲面上點p的均勻分布，再產生點p為中心的3D正態分布，就能滿足要求（R.2）。此法無需考慮點p處的法向。

（2）2D 圓點云的情況。不妨設在一個以原點為圓心半徑為r的圓上分布有線密度為ρ，在各中心點p有服從N(p,σ2)分布的2D點云。在極坐標系統下，θ處微元dθ處的點數量是ρrdθ，以二維正態分布于整個平面，疊加后的關于(R,Θ)的聯合分布密度為：

關于Θ的分布顯然均勻，關于R的分布不再是正態分布，利用辛普森數值積分：

可知該分布近似于如下分布：

這仍是以σ-高斯為主的分布，所以這種情況直接將單點3D高斯疊加即可基本滿足要求（R.2）。

單點疊加的總步驟是，先參數采樣p0(u,v)，然后按單點模式化分布律得偏移向量r，最后向量疊加，得采樣點p=p0+r。此外，對每個單點的隨機偏移，本文進行圓形截尾（2D）或球形截尾（3D），還會使疊加點云各向同性，實現理想化目標（R.4）。以2D 為例，圓形截尾的效果示意如圖2（c）。

圖2 截尾類型Fig.2 Tail-cutting types

2.4 曲率補償

理想點云的一個重要要求是3D點云體密度（或2D點云面密度）ρ服從關于點到曲面（或曲線）有符號幾何距離dG的模式化分布，即：

此種分布才保證點云在曲面高曲率部分呈現均勻的視覺效果。對簡單的曲面表面采樣和法向模式化分布，曲面高曲率處容易產生曲率中心內側密度大外側密度小的曲率偏差現象（如圖3）。因此，需要進行曲率補償，即在高曲率處模式化分布疊加后將一部分曲率中心內側點搬移到外側點。

圖3 曲率偏差現象Fig.3 Curvature bias phenomenon

以正態分布為例，考慮曲面/曲線上固定點p0，設p0處離曲率中心的法向量為n，曲率半徑為R。p是法線上有符號幾何距離為x（曲率中心側為負）的點（如圖4），在極坐標系O-rθη（2D時O-rθ）下，r軸上線密度偏差量正比于(x+R)2（2D曲線時(x+R)）。因此，用公式（8）調整相對密度函數（2D曲線用公式（9））能糾正偏差。公式（6）、（8）、（9）示意如圖5。

圖4 曲率偏差分析Fig.4 Curvature bias analysis

圖5 密度糾偏函數Fig.5 Density correcting functions

根據曲面的微分幾何，曲面的曲率有主曲率、高斯曲率和綜合曲率。隨機點云生成依據綜合曲率進行曲率補償是最恰當的。

記二階導數矩陣為：

在式（1）下，點p(u,v)=(f(u,v),g(u,v),h(u,v))T處的綜合曲率Hˉ是[20]：

由此得向心法向量為Sgn()·n。若0,n側點云應變稀疏，否則n側點云應變稠密。曲率半徑R=|1/|，據式（8）確定補償率。

實際上，為消除不同模式化分布函數的差異，降低曲率補償計算復雜性，本文只需估計曲率并分級處理。可作差分近似，如：

圖6 表示出分級曲率補償前后的曲面內外側密度比的分布情況。

圖6 分級曲率補償效果示意圖Fig.6 Illustration of discrete curvature compensation

對2D曲線，先計算曲線曲率：

向量n=(-g′(t),f′(t))T是參數遞增方向的左側法向量。若κ ＞0，說明n向心，否則離心。Sgn(κ)·n總是向心法向量，再據公式（9）確定補償率。3D曲線處理方式類似。

法向模式化分布與曲率補償結合，共同實現了理想化目標（R.2）。

2.5 藍噪音模擬

理想點云的噪音模擬用單點的三維模式化分布疊加而成，在疊加前采用MBC（Mitchell’s best candidate）方法來模擬主方向藍噪音，實現點云的理想化目標（R.3）。設噪音標準差為σ，當前點云的點集為P。按照單點疊加的方法連續采樣k個曲面參數(ui,vi)和偏移ri(i=1,2,…,k)，主方向為點pi=p(ui,vi)處單位法向量Ni。分別計算法向偏移量：

及規范化距離：

圖7 單點模式化分布藍噪音點云Fig.7 Blue noised point clouds with patterned distributions

3 實驗結果

本算法用Visual C++.net+OpenGL 代碼實現，在2.6 GHz Pentium 雙核CPU、2 GB 內存的計算機上進行實驗，所涉及曲面/曲線都縮放至邊長為6 的包圍盒中。對封閉曲面，還限制在邊長為4的包圍盒中。未加特別說明的法向模式化分布都是高斯分布。

3.1 視覺效果

（1）簡單曲面曲線

圖8 是由2D 曲線拋物線生成的各種規格點云，點數N=10 000。

圖8 2D曲線生成點云Fig.8 2D curve point clouds

圖9是由3D曲線莫比烏斯帶邊緣線生成的各種規格點云，點數N=10 000。

圖9 3D曲線生成點云Fig.9 3D curve point clouds

圖10 是由同一環面生成的各種規格點云，點數N=20 000。圖11是不同環面生成的同種規格點云，其中環面的兩個半徑參數相對變化，從R=1.25,r=0.25開始，將r逐漸增大直至1.25 產生奇點，生成點云一直保持均勻的視覺效果。

圖10 曲面生成點云Fig.10 Surface point clouds

圖11 不同參量曲面生成點云Fig.11 Surface point clouds on different parameters

（2）復雜曲面

具有簡單解析式曲線曲面的生成點云視覺上達到理想的均勻分布效果，而任意復雜曲面可用三角網格表示，其中每個面片可以參數化，由此亦能生成理想點云，以Bunny Rabbit(N=50 000)和Utah Teapot(N=50 000)為例，各種規格點云如圖12、13。

圖12 三角網格曲面生成點云（一）Fig.12 Triangular meshed surface point clouds（1）

圖13 三角網格曲面生成點云（二）Fig.13 Triangular meshed surface point clouds（2）

（3）開放曲面

封閉曲面是3D實體的表面，除了封閉曲面之外，開放曲面的點云也能夠生成。圖14是由開放曲面生成的點云結果，點數N=50 000。

圖14 開放曲面生成點云Fig.14 Open surface point clouds

（4）非理想點云

為了與理想結果對比，本文生成一組非理想點云與理想點云圖12（b）對比。如圖15，（a）呈現條紋，非各向同性；（b）法向非模式化分布（均勻分布）；（c）未經曲率補償，高曲率處內外密度有偏差；（d）局部點集不均勻，非藍噪音采樣。3D點云（b）（c）肉眼較難分辨其不同之處，下一節給出量化對比。為更清晰展示理想點云的視覺效果，圖16給出一組2D情形的對比點云，其中（b）為理想點云，易見已基本消除高曲率處的密度偏差，（c）為法向非模式化分布，（d）為未曲率補償，易見其在頂端高曲率處的非理想結果。

圖15 非理想點云(σ=0.01,λ=5)Fig.15 Unqualified point clouds(σ=0.01,λ=5)

圖16 非理想2D點云Fig.16 Unqualified 2D point clouds

3.2 量化指標比較

實驗結果用兩個指標度量3D 曲面點云：面密度和厚度。面密度表征曲面切向密度，定義為曲面上小鄰域內的點的數量與鄰域面積之比：ρ=N/S。厚度表征點云在曲面法向的噪音強度，與標準差關系密切。由于[-d,d]噪音均勻分布時標準差是，因此，對噪音呈σ-模式化分布，用作為厚度。

點云中每個點的ρ和h都一一計算，方法如下：取點pi，根據測地距離構造鄰域點集（方法如Cartesian grid based（CGB）[21]），假設點集包含ni個點，由圓并集面積算法得鄰域面積Si，于是

然后構造scatter矩陣[22]，計算特征值，由于scatter是半正定對稱陣，特征值必非負，取最小特征值λi，即得標準差：

及厚度：

（1）與真實指標比較

面密度和厚度的基礎真實值ρT、hT容易通過參數曲面及其參數范圍事先計算，它們都是全局指標。厚度與標準差只差一個常數因子，故下面直接比較標準差。對生成的點云，按上述方法計算每個點的指標后，再根據以下兩式計算全局平均值：

表1（相應圖如圖17）列出3.1節大部分點云的全局平均密度和全局厚度與基礎真實值的比較，部分模型點數有增減，厚度僅用標準差代替。與基礎真實值相比，10個模型中有5個模型，全局密度的相對誤差在10%以內，7 個模型在30%以內；關于厚度，則有4 個模型相對誤差在10%以內，7個模型在30%以內。可以看出，指定的標準差ρT在0.001～0.1范圍內生成點云的誤差很小，過小（≤0.001）或過大（≥0.1）都不利于理想點云的模擬。

表1 與真實值的比較Table 1 Comparison to ground truth

圖17 與基礎真實值的比較Fig.17 Comparison to ground truth

（2）與其他方法比較

依據參數曲面生成理想點云時，期望點云的面密度處處相同，厚度亦然。所以本文比較點云各點的局部面密度ρi=Ni/Si的均等程度，方案是選擇各種方法的一組實驗模型，對每種方法，每個模型的密度分布的均值都歸一化到單位1，再對各模型的歸一化分布作總評，得到單一分布，作為該方法的數量化表達。

對每種方法，計算面密度、厚度的總評（Summerized）分布標準差σρ、σσ，標準差越小說明均等程度越好。

歸一化處理可以合理地在不同模型、不同方法之間進行點云生成質量比較。本算法參與總評的點云模型來自3.1節。CAD Assembly模型來自文獻[15]的表格，括號中注明的是表號和行號。Plant Phenotyping 模型來自文獻[16]提供鏈接的4個下載文件，分別是：

Lilac1：Lilac_2Labels_onlyPoints.xyz

Lilac2：Lilac_multilabel_onlyPoints.xyz

Arabido.1：Arabidopsis_1_onlyPoints.xyz

Arabido.2：Arabidopsis_4_onlyPoints.xyz

面密度和厚度比較如表2，列出兩種方法（plant phenotyping 和CAD assembly）和本算法歸一化后的標

表2 密度厚度均勻性比較Table 2 Comparison of density and thickness uniformity

注：來源附于模型名之后，例如：Tab.3-8表示來自文獻[15]Table 3第8行。準差，本文的密度和厚度分布標準差都最小(σρ=0.108 2,σσ=0.223 2)。

表3 與非理想點云的量化比較Table 3 Quatitative comparison to unqualified

圖18 是密度分布情況，其中將[0,3σ]等分成22段。從圖中可看出，本算法不但標準差小（非常集中），而且偏度亦小（對稱性高），說明分布十分理想。

圖18 密度分布比較Fig.18 Comparison of density distribution

圖19是厚度分布情況，將[0,12σ]等分成22段。圖中可看出，本算法厚度分布標準差也小（比較集中），且偏度小（對稱性高），說明分布比較理想，點云的厚度基本上處處統一。

圖19 厚度分布比較Fig.19 Comparison of thickness distribution

（3）與非理想點云比較

對肉眼不易辨別的非理想點云（圖15（b）（c）），特別給出定量比較，如表3，列出它們的面密度、厚度的相對誤差eρ、eσ（與基礎真實比較）和分布標準差σρ、σσ，其中圖12（b）是本算法的理想化點云。

表3 中顯示，理想點云在視覺效果占優的同時，數量指標總體亦較優，尤其是相對誤差，均為最優。標準差略有損失，但不嚴重。

4 結束語

由參數方程生成理想點云的算法能以低成本生成人造點云，本算法能夠使人造點云模擬理想3D 掃描儀的拍攝結果，具有視覺上的“均勻性”，具體上說，面密度均等，法向同標準差分布，空間藍噪音，各向同性，高曲率處內外密度偏差小。基于這些特征，通過本算法能以低成本建立點云庫，而且易獲取伴隨點云的基礎真實值并加標注，從而為3D 曲面重建的算法測試和機器學習的有監督學習提供大規模的基礎數據。