逼近散亂點云數據的三角形網格精確剖分

張 偉

（中國計量學院機電工程學院，浙江 杭州 310018）

逼近散亂點云數據的三角形網格精確剖分

張 偉

（中國計量學院機電工程學院，浙江 杭州 310018）

基于自組織特征映射神經網絡構建的三角形網格模型可以實現測量點云壓縮后的Delaunay三角逼近剖分，但該模型存在逼近誤差和邊緣誤差。為減小三角形網格的逼近誤差和邊緣誤差，構建了精確逼近的三角形網格模型。首先采用整個測量點云，對三角形網格模型中的所有神經元進行整體訓練；然后對三角形網格中的網格神經元的位置權重，沿網格頂點法矢方向進行修正；最后采用測量點云中的邊界點集，對三角形網格模型中的網格邊界神經元進行訓練。算例表明，應用該模型，可以有效減小三角形網格的邊緣誤差，三角形網格逼近散亂點云的逼近精度得到大幅提高并覆蓋散亂點云整體分布范圍。

逆向工程；三角形網格；神經網絡；逼近誤差；邊緣誤差；散亂點云

逆向工程是從一個已有的物理模型產生出相應CAD模型或實體模型的過程。在離散數據的逆向工程中，常采用小三角平面片（三角形網格）或三角域上的Bezier曲面片進行產品外形擬合。三角曲面能夠適應復雜的形狀及不規則的邊界，因而在對復雜型面的曲面構造過程中以及在逆向工程中，具有很大的應用潛力。在面向快速原型制造的應用中，只要對給定的離散數據點進行三角剖分就能得到STL格式的零件幾何表示。

近年來，以掃描測量為基礎的“點云”數據采集的發展非常迅速，由此生成的三角形網格可多達幾萬甚至上百萬個，這樣不僅占用了大量的存儲空間，也不利于網格的后續處理，尤其是在快速原型制造領域的應用更是存在著很多不便之處。如果依然沿用傳統的三角片逼近造型方法，將遇到難以克服的困難[1]。

國內外學者對模型簡化的研究已取得了一系列成果。Schroeder和Zarge[2]提出了基于頂點刪除的網格刪減方法；Hamann[3]通過曲率計算移去三角形，從而簡化模型；Hoppe和Derose[4]提出了一種整體的網格優化過程，此后又采用漸進網格[5]的表示方法來存儲和傳輸三角網格；Eck的 Rossignac[6]利用小波技術進行模型簡化；Dehamer和Zyda[7]應用了自適應剖分方法進行網格簡化；Garland和Heckbert[8]應用了邊折疊操作方法進行網格簡化；Hussain[9]提出了一種高效的特征保持簡化算法；Chong等[10]結合遺傳算法對大規模網格模型進行簡化和優化。國內在這方面的研究起步較晚，但也取得了許多研究成果[11-17]。張偉等[18]進行了基于自組織特征映射(self-organizing feature map, SOFM)神經網絡[19]的三維散亂測量點云的拓撲三角形網格自組織壓縮重建的探索。該文所建三角形網格模型可以實現測量點云壓縮后的Delaunay三角逼近剖分。Zhang等[20]在文獻[18]的基礎上，將單視密集散亂數據壓縮、拓撲三角形網格逼近剖分和網格頂點法矢量生成統一在一個進程中。文獻[18]、[20]不足之處是三角形網格模型在效率與精度層面與神經網絡規模關聯程度較高，提高神經網絡規模，可以提高三角形網格的逼近精度，但同時也使神經網絡的訓練時間延長。

現有的三角形網格簡化模型構建方法在效率與精度層面有待提高。本文將在文獻[20]的基礎上研究構建高效精確逼近散亂點云數據的簡化三角形網格模型及其訓練模式。

1 精確逼近的三角形網格模型

1.1 三角形網格自組織壓縮重建

用于散亂點云數據壓縮的 SOFM神經網絡二維陣列模型，如圖1所示。圖中網絡的輸入矢量就是復雜曲面上的測點矢量Pj(x, y, z)，網絡輸出層具有m×n個神經元結點，即該三角形網格重建模型具有m×n個神經元。網絡神經元對曲面空間測量樣本點的學習和訓練來模擬曲面上的點與點之間的內在關系，結點連接權重矢量集重構曲面樣本點的內在拓撲關系及實現對測點集的工程近似化，實現曲面三維散亂點云的自組織壓縮，構成三角剖分。

圖1 數據壓縮二維陣列網絡模型

圖2 六角形陣列鄰區Nc

圖1所示神經網絡的權重矢量調節算法如式(1)所示。

式中，Pj為測點矢量；Wi(t)為神經元連接權重矢量； α( t)為修正率；Nc為以結點 c為中心的輸出結點集合，如圖2所示，圖中c為與輸入矢量Pj匹配最佳的輸出結點； β（ di）是修正率加權函數，其中 di為鄰區集合Nc中結點i到c之間的距離。

經過訓練，權重矢量Wi收斂到所代表的感受野（即測量點集中與權重矢量Wi的歐氏距離最近的點集）的平均值，其反映了測量點集的統計特性。三角網格剖分可按如下步驟進行：①圖2中tc時刻的六角形陣列鄰區Nc集合中的結點c依次與Nc中6個相鄰結點相連便形成三角網格剖分；②對輸出層上的每一結點都如此處理；③神經元結點對應的權重矢量Wi在三維空間構成測量點集壓縮后的Delaunay三角網格逼近剖分[18]。

1.2 三角形網格頂點法向矢量

設欲重構的曲面可以用參數方程式(2)表示。

式中，P表示曲面的笛卡兒坐標(x, y, z), Q表示曲面參數(u, v)。對于曲面采樣測點矢量集，曲面參數可設為(x, y)。

曲面參數方程(2)是一復雜的非線性變換，要用一個函數擬合所測得的數字化點群數據是困難的。為此可將式(2)在Qs處泰勒展開。

式中，Ps，As和Qs可用擴展SOFM(ESOFM)[20]神經網絡學習而得。此式表示所構造的神經網絡權重矢量Ps處的微切平面方程。依據此式，微切平面逼近式(2)表示的曲面，在Qs局域Fs中可達到很高的精度。Fs由式(4)定義。

式中，s是激活神經元；Fs是神經元s對應的輸入空間，即感受野；Ω是輸入空間；Qr是神經元r的外部輸入權重，即分類核心。

設s為自組織特征映射神經網絡陣列中的任一神經元，SOFM自組織學習算法可使 s與 Qs形成空間有序特征映射。通過SOFM算法擴展同時使s與(Ps，As)建立映射關系。通過ESOFM神經網絡訓練，學習Ps、As及Qs，以滿足式(3)。ESOFM神經網絡的權重矢量Ps、As及Qs的訓練采用文獻[20]的調節算法。

按上述建立的ESOFM神經網絡中，每一個神經元s有一個感受野Fs以及外部輸入權重Qs，那么該神經元的輸出就是Ps。當輸入Q偏離Qs時，則神經元的輸出由式(3)得到。這樣ESOFM神經網絡將整個數字化點群數據分成許多子區域，每個子區域用一個微切平面逼近，每組權重各自對相應的子區域負責。式(3)中的 As可用于計算相應子區域權重矢量 Ps（即三角形網格頂點）處的法向矢量ns，其計算公式如下。

式中，As由ESOFM神經網絡訓練后直接得到。

1.3 三角形網格模型的改進訓練模式

文獻[20]按照 1.1～1.2節所述模型及其訓練算法，采用整個測量的散亂點云，對三角形網格模型中的神經元陣列進行若干循環的整體訓練，實現將單視密集散亂數據壓縮、拓撲三角形網格逼近剖分和網格頂點法向矢量生成統一在一個進程中。為減小三角形網格的逼近誤差和邊緣誤差，本文擬按照以下3步訓練模式，依次進行三角形網格模型的訓練，3步訓練的結果之間具有繼承性（后繼承前）。

1.3.1 網格神經元整體訓練的改進

按照 1.1～1.2節所述模型及其訓練算法，采用整個測量的散亂點云，對模型中的神經元陣列進行若干循環的整體訓練。此步訓練與文獻[20]采用的訓練方式不同之處在于此步的訓練調高了與測量點云中的邊界點集匹配的神經元的訓練修正率 α( t)，以加大三角形網格邊界神經元及其鄰區的神經元對應的位置權重矢量向測量點云邊界趨近的強度，如此生成的三角形網格Ⅰ可以減小邊緣誤差。

1.3.2 網格神經元位置權重矢量的修正

設三角形網格頂點神經元 s，網格頂點位置權重矢量為Ps，網格頂點法向矢量為ns，網格頂點神經元s在位置權重矢量Ps處的空間感受野為Fs。則本文提出的網格神經元s的位置權重矢量Ps修正如圖3所示，修正步驟如下：

（1）在位置權重矢量Ps處的空間感受野Fs中，求出與Ps最近的點q；

（2）然后過點q作法向矢量ns（其經過Ps點）的垂直交線，垂足為′相對于Ps更加逼近被測曲面；

（3）按式(7)修正位置權重矢量Ps。

圖3 網格神經元位置權重矢量的修正

按照上述位置權重矢量修正而產生的三角形網格Ⅱ較三角形網格Ⅰ更加逼近采樣曲面。

1.3.3 網格邊界神經元的微調訓練

為進一步減小三角形網格邊緣誤差，按以下訓練方式訓練網格邊界神經元。

（1）采用點云數據中的邊界點集，只對三角形網格模型中的網格邊界神經元進行訓練，微調三角形網格邊界神經元對應的位置權重矢量向測量點云邊界趨近。網格內部神經元不參與訓練。三角形網格邊界神經元采用“0”六角形鄰區 Nc進行訓練，其等價為一維訓練方式，可有效使三角形網格邊界神經元對應的位置權重矢量趨近邊界點集。

（2）采用邊界點集中的角點點集，只對與邊界角點匹配最佳的網格邊界神經元進行訓練，微調與邊界角點匹配最佳的三角形網格邊界神經元對應的位置權重矢量向測量點云邊界角點趨近。網格其他神經元不參與訓練。與邊界角點匹配最佳的三角形網格邊界神經元采用“0”六角形鄰區Nc進行訓練，其等價為一維訓練方式，可有效使與邊界角點匹配最佳的三角形網格邊界神經元對應的位置權重矢量趨近邊界角點點集。

如此生成的三角形網格Ⅲ可以進一步減小邊緣誤差。

2 三角形網格逼近精度的仿真實驗

分別以球面點集和復雜曲面點集為對象，對所構建的三角形網格模型在個人計算機上進行仿真實驗。

2.1 采用球面點集的仿真實驗

仿真實驗中，三角形網格模型中的神經元陣列包含10×12個神經元，采用式(8)表示的球面的隨機采樣點集進行訓練，仿真實驗結果如圖4所示。

圖4(a)表示采樣點集，球面采樣的參數范圍為：u=0～π/4，v=0～π/3，R=10。采樣點集包含3524個點，其中邊界點集包含324個點，角點點集包含4個點；圖4(b)表示應用文獻[20]訓練模式的仿真實驗結果，圖中繪出了所構建的三角形網格的頂點位置、頂點處的法向矢量以及采樣邊界點集，從圖中可以看到存在較為明顯的三角形網格邊緣誤差；圖4(c)表示將圖4(b)所示的三角形網格神經元位置權重矢量沿法向矢量方向修正的結果；圖4(d)表示應用本文改進的整體訓練模式的仿真實驗結果，圖中繪出了所構建的三角形網格的頂點位置及頂點處的法向矢量，從圖中可以看到三角形網格邊緣誤差大幅減小；圖4(e)表示將圖4(d)所示的三角形網格神經元位置權重矢量沿法向矢量方向修正的結果；圖4(f)表示應用本文提出的網格邊界神經元的微調訓練模式對圖4(e)所示的三角形網格Ⅱ的網格邊界神經元進行訓練，所生成的三角形網格Ⅲ。

圖4 仿真實例1

仿真實驗中生成的三角形網格逼近散亂數據的逼近誤差與邊緣誤差如表1所示。表1中2～6列分別表示圖4(b)～(f)所對應的仿真實驗精度。

表1 仿真實例1的實驗精度(mm)

表1中三角形網格的邊緣誤差表示三角形網格邊界頂點與曲面邊界相離的程度。本文按以下步驟計算度量：①搜尋與網格邊界頂點距離最近的邊界點集中的點；②計算兩者的歐氏距離；③求取所有網格邊界頂點與邊界點集相應的歐氏距離的平均值。這是一種相對評估邊緣誤差的方式，邊界點集的采樣密度對按此方式計算的邊緣誤差量值有較大影響。

表1中三角形網格的逼近誤差表示三角形網格頂點集偏離曲面的程度，具體可采用逼近誤差Ⅰ和逼近誤差Ⅱ進行度量。

逼近誤差Ⅰ按式(9)進行計算度量。

式中，m×n表示神經元陣列中分布的神經元數目；R表示球面半徑；Ps表示三角形網格頂點的位置權重矢量，即三角形網格頂點的空間位置。

逼近誤差Ⅱ表示沿網格頂點法矢方向度量網格頂點偏離曲面的程度，其按以下步驟計算度量：①過網格頂點并沿網格頂點法向矢量 ns方向，相交于曲面得交點p；②計算網格頂點與相應交點p之間的歐氏距離；③求取所有網格頂點與相應交點之間的歐氏距離的平均值。

采用不同神經網絡規模進行仿真實驗，各種訓練模式的仿真實驗精度對比，如表2所示。

表2 仿真實驗的逼近誤差I(mm)

2.2 采用非規則曲面點集的仿真實驗

仿真實驗中，三角形網格模型中的神經元陣列包含8×8個神經元，采用式(10)表達的非規則曲面的隨機采樣點集進行訓練，仿真實驗結果，如圖5所示。

圖5(a)表示采樣點集，非規則曲面采樣的參數范圍為：x=π/2～5π/4，y=π/7～5π/6。采樣點集包含2524個點，其中邊界點集包含324個點，角點點集包含4個點；圖5(b)表示應用文獻[20]訓練模式的仿真實驗結果，圖中繪出了所構建的三角形網格的頂點位置、頂點處的法向矢量以及采樣邊界點集；圖5(c)表示將圖5(b)所示的三角形網格神經元位置權重矢量沿法向矢量方向修正的結果；圖5(d)表示應用本文改進的整體訓練模式的仿真實驗結果，圖中繪出了所構建的三角形網格的頂點位置及頂點處的法矢；圖5(e)表示將圖5(d)所示的三角形網格神經元位置權重矢量沿法矢方向修正的結果；圖5(f)表示應用本文提出的網格邊界神經元的微調訓練模式對圖5(e)所示的三角形網格Ⅱ的網格邊界神經元進行訓練，所生成的三角形網格Ⅲ。

仿真實驗中生成的三角形網格逼近散亂數據的逼近誤差Ⅱ、邊緣誤差及神經網絡訓練時間如表3所示。表3中2～6列分別表示圖5(b)～(f)所對應的仿真實驗結果。表3中的訓練時間表示得到相應三角形網格所需的訓練時間總和。

圖5 仿真實例2

表3 仿真實例2的實驗精度(mm)

2.3 仿真實驗結果的分析

由表1和表3可知本文所構建的三角形網格模型及其訓練模式顯著減小了三角形網格的逼近誤差和邊緣誤差。

在采用二種點集的仿真實驗中，對網格頂點位置權重矢量Ps，采用沿網格頂點法向矢量方向修正的算法，可以使三角形網格更加逼近采樣曲面，大幅降低了三角形網格的逼近誤差。該算法對本文和文獻[20]構建的三角形網格模型均適用。表1中逼近誤差Ⅰ與逼近誤差Ⅱ相差極其微小，這可以間接證明所求的三角形網格頂點處的法向矢量非常接近相應交點 p處的曲面法向矢量，也表明了逼近誤差Ⅰ與逼近誤差Ⅱ在度量三角形網格逼近散亂數據點集的偏離程度方面是等同的。經過運用本文提出的網格邊界神經元的微調訓練模式，三角形網格的邊緣誤差再次明顯減小，網格邊界神經元逼近球面的逼近精度略有提高，結果使三角形網格頂點集逼近球面的平均逼近誤差進一步減小。表 2表明，提高神經網絡規模可以減小三角形網格的逼近誤差。相比較而言，在減小三角形網格的逼近誤差方面，采用本文構建的三角形網格模型中的訓練算法，要比采用提高神經網絡規模的方法更加合理和更有成效。

3 結 束 語

仿真實驗表明本文構建的三角形網格模型及其訓練模式在應用中呈現以下特性：①可以實現測量點云壓縮后的Delaunay三角逼近剖分；②顯著減小了三角形網格的邊緣誤差；③三角形網格逼近散亂點云的逼近誤差得到大幅降低；④三角形網格覆蓋點云整體分布范圍。所構建的三角形網格，既可用于構造散亂數據插值曲面的前置處理，也可用于快速原型STL格式的零件幾何表示。今后此研究主題的工作重心是關于復雜拓撲模型和大規模分布范圍的密集散亂數據的三角形網格高效精確重建，擬采取先分片三角形網格構建，后整體融合訓練重構的思路。

[1] 王平江, 黃雪梅, 陳吉紅, 周 濟. 曲面激光密集測量三維數據的三角片逼近方法[J]. 工程圖學學報, 1998, 19(1): 17-27.

[2] Schroeder W J, Zarge J A. Decimation of triangle meshes [J]. Computer Graphics, 1992, 26(2): 65-70.

[3] Hamann B. A data reduction scheme for triangulated surfaces [J]. Computer Aided Geometric Design, 1994, 11(2): 197-214.

[4] Hoppe H, Derose T. Mesh optimization [J]. Computer Graphics, 1993, 27(1): 19-26.

[5] Hoppe H. Progressive meshes [J]. Computer Graphics, 1996, 30(2): 119-128.

[6] Eck M, Rossignac J R. Multi-resolution analysis of arbitrary meshes [J]. Computer Graphics, 1995, 29(2): 171-182.

[7] Dehamer J M, Zyda M J. Simplification of objects rendered by polygonal approximations [J] Computer Graphics, 1991, 25(2): 175-184.

[8] Garland M, Heckbert P S. Surface simplification using quadric error metrics [J]. Computer Graphics, 1997, 31(3): 209- 216.

[9] Hussain M. Efficient and feature-preserving triangular mesh decimation [J]. Journal of WSCG, 2004, 12(1): 167-174.

[10] Chong C S, Lee H P, Kumar A S. Genetic algorithms in mesh optimization for visualization and finite element models [J]. Journal of Neural Computing & Applications, 2006, 15(3): 366-372.

[11] 孫玉文, 王曉明, 郭東明. 反求工程中復雜多面體模型的網格簡化算法[J]. 中國機械工程, 2001, 12(8): 922-925.

[12] 蔣亞軍, 朱 理. 一種基于視覺特性的三角網格簡化算法[J]. 計算機仿真, 2006, 23(10): 178-180.

[13] 陳華鴻. 基于四邊形折疊的三角網格簡化算法[J].中山大學學報(自然科學版), 2008, 47(4): 19-24.

[14] 車翔玖, 劉 楊, 趙義武, 車 娜, 高占恒. 基于k-鄰域密度的離散點云簡化算法與實現[J]. 吉林大學學報(理學版), 2009, 47(5): 994-998.

[15] 閆 濤, 姜曉峰, 王 昱. 基于三角網格模型簡化的研究[J]. 計算機工程與科學, 2010, 32(12): 69-72.

[16] 李 龍, 何明一. 基于特征保持和二次誤差測度的網格簡化[J]. 西北大學學報(自然科學版), 2010, 40(3): 419-422.

[17] 張 果, 劉旭敏. 一種基于八叉剖分的近似曲率的邊折疊簡化算法[J]. 計算機應用研究, 2010, 27(5): 1955-1958.

[18] 張 偉, 姜獻峰, 陳麗能, 馬亞良. 基于神經網絡的三角形網格智能重建[J]. 工程圖學學報, 2004, 25(1): 71-75.

[19] Kohonen T. The self-organizing map [J]. Proceeding of IEEE, 1990, 78(9): 1464-1479.

[20] Zhang Wei, Jiang Xianfeng, Chen Lineng, Ma Yaliang. Mesh generation from dense 3D scattered data using neural network [J]. CADDM, 2004, 14(1): 30-35.

Reconstruction of Triangle Mesh for Unorganized Point Cloud Data with High Approximation Precision

Zhang Wei
(College of Mechanical and Electronic Engineering, China Jiliang University, Hangzhou Zhejiang 310018, China)

An approach based on the self-organizing feature map (SOFM) neural network has been developed to reconstruct Delaunay triangle mesh for the unorganized measured point cloud. However the approach suffers from approximation and boundary problems. A triangle mesh model with high approximation precision is proposed in order to reduce the approximation error and boundary error. First all the neurons of the mesh model are trained directly over the unorganized point cloud. Next the neuron location weights of the mesh model are adjusted along the normal vectors of the mesh vertices. Last only the boundary neurons of the mesh model undergo training by the boundary points of the measured point cloud. As a result of applying the proposed mesh model, the boundary error is greatly reduced and the mesh is drawn toward the sampled object with higher precision comparing with the original SOFM training algorithm. The feasibility of the developed mesh model is demonstrated on two examples.

reverse engineering; triangle mesh; neural network; approximation error; boundary error; unorganized point cloud

TP 391

A

2095-302X (2014)02-0188-07

2013-05-13；定稿日期：2013-06-17

浙江省自然科學基金資助項目（Y1091012）；國家質檢總局科技計劃資助項目（2006QK65）

張 偉（1964-），男，浙江金華人，副教授，博士。主要研究方向為CAD/CAM/RE、神經網絡技術與應用等。E-mail：zhangwei@cjlu.edu.cn