蘇江姍

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

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

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

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

在點(diǎn)云簡化算法研究中，如何在最大程度地保留細(xì)節(jié)特征的前提下減少點(diǎn)云數(shù)據(jù)量是研究的關(guān)鍵?，F(xiàn)有的點(diǎn)云簡化方法可分為兩類：一類方法是基于頂點(diǎn)聚類的簡化，另一類則是計(jì)算點(diǎn)云局部復(fù)雜度并迭代刪除頂點(diǎn)的簡化。

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

1 算法實(shí)現(xiàn)

1.1 算法描述

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

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

1.2 幾何誤差度量

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

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

點(diǎn)pi的協(xié)方差矩陣定義為：

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

1.3 顏色誤差度量

本文使用一定半徑內(nèi)頂點(diǎn)的顏色與平均顏色色差的方差作為顏色誤差的度量因子ΔC，即評(píng)估一定半徑內(nèi)頂點(diǎn)顏色之間的相似程度。本節(jié)首先介紹RGB顏色空間存在的局限性，對(duì)HSV 空間色差的計(jì)算進(jìn)行詳細(xì)敘述。

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

在精確表示顏色處理的應(yīng)用中，使用的通常是HSV 顏色空間的信息。HSV 顏色空間可以更直觀地表達(dá)顏色的色調(diào)、明暗、鮮艷程度。方便對(duì)不同的顏色進(jìn)行統(tǒng)一規(guī)范的比較。

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

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

圖1 HSV顏色空間模型

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

2 基于Surface Splatting的點(diǎn)云渲染

2.1 算法思想

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

2.2 算法流程

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

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

圖2 EWA基本思想[8]

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

圖3 局部坐標(biāo)到屏幕坐標(biāo)的映射[8]

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

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

Surface Splatting 是一種新的點(diǎn)云渲染方法，它將EWA 的優(yōu)點(diǎn)用于基于點(diǎn)的表面的表示和渲染。該算法提供了一個(gè)完整的數(shù)學(xué)分析過程，從空間中不規(guī)則的點(diǎn)通過數(shù)學(xué)變換得到了基于二維屏幕坐標(biāo)的函數(shù)。

3 實(shí)驗(yàn)結(jié)果

本節(jié)將會(huì)展示點(diǎn)云模型使用我們的簡化算法得到的簡化結(jié)果，利用基于Surface Splatting 方法進(jìn)行渲染，驗(yàn)證簡化算法的正確性。實(shí)驗(yàn)設(shè)備為：

CPU：Intel Core i3-4160 CPU@3.60GHz

RAM：8.0GB

System：Windows 10

GPU：NVIDIA GeForce GTX 1050

圖4 展示了熊貓?jiān)键c(diǎn)云模型以及簡化率為25%、50%和75%時(shí)相同簡化半徑點(diǎn)云的效果。

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

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

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

4 結(jié)語

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

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