基于成長型神經網絡以線段為基元的曲線重建

王世東 ， 張佑生， 王煥寶

（1. 中國科學技術大學火災科學國家重點實驗室，安徽 合肥 230026;2. 安徽建筑工業學院信息網絡中心，安徽 合肥 230022;3. 安徽三聯學院計算機科學與技術系，安徽 合肥 230601）

逆向工程的主要任務是由物理模型重建出幾何表示模型，通常包含4個步驟：數據采集、數據預處理、曲面擬合和CAD模型重建。其中,曲面擬合和CAD模型重建是逆向工程中最為重要的部分[1]。Alrashdan將逆向工程分成三個主要步驟：零件數字化，特征提取，CAD建模。其中，特征提取是通過點云分塊以及表面特征識別來完成的[2-3]。近年來，在逆向工程中，對特征提取問題的研究比較活躍。Géza Kós等對等半徑過渡特征曲面提取問題進行了研究[4]。Lu等對等/變半徑過渡曲面特征提取進行了研究[5]。文獻[4-5]只能針對比較規則簡單特征的提取。Ke等深入研究了點云切片算法和拉伸面特征的提取[6-7]，能高效地構造點云有序組織形式和提取如拉伸面、旋轉面等復雜曲面特征。隨著神經網絡技術的廣泛應用，使用神經網絡實現特征提取逐漸成為一個熱門研究課題。Jun等研究了基于神經網絡的棱柱特征[8]，如邊、孔等的識別。Xiao等提出使用正交神經網絡重建曲線[9]，但當點云具有明顯角點和較多噪聲數據時，文獻[8-9]算法重建效果并不理想。

IVRISSIMTZIS等提出使用成長型神經網絡以三角面片為基元重建實體模型[10]。在此基礎上，本文提出基于成長型神經網絡以線段為基元的曲線重建算法。給定某一曲線的散亂點集和一個初始折線，使用成長型神經網絡優化折線上頂點的位置，使折線更好地逼近散亂點；持續分裂折線上活動性強的頂點和刪除活動性最弱的頂點，使頂點的分布更符合散亂點數據的概率分布。算法使折線上的頂點不斷增加，折線不斷成長，直至達到要求的重建效果。實驗結果表明，該算法的計算速度不受輸入數據量大小的影響，非常適合大規模散亂點集和含噪聲數據的學習，能夠取得良好的曲線重建效果。

1 曲線重建原理

1.1 成長型神經網絡

成長型神經網絡（Growing Cell Structures,下文簡稱 GCS網絡）屬于自組織特征映射神經網絡（Self-Organizing Feature Map，下文簡稱SOM網絡）。SOM網絡是芬蘭學者Kohonen在1980年根據生理學規律提出的。它是一種具有側向聯想能力的兩層網絡，能把輸入層含m維的向量特征映射到一維或二維拓撲空間中，如圖1所示，該網絡輸入為m維向量，輸出為一維拓撲神經元。SOM 引入變化鄰域概念來模擬生物神經網絡中的側抑制現象：生物神經元接受刺激并進行競爭產生獲勝神經元，該神經元和它鄰域的神經元得到加強，鄰域之外的神經元由于距離它較遠而受到抑制，這樣就可實現網絡的自組織特性。

圖1 一維輸出的SOM模型

GCS網絡是一種特殊的SOM網絡，它能夠增量生長。該網絡在學習輸入向量的過程中，根據神經元競爭獲勝次數的多少確定它們活動性的強弱，分裂活動性強的神經元，刪除活動性最弱的神經元，使網絡更好地體現輸入向量的內在特征。

1.2 曲線重建模型

基于 GCS網絡曲線重建模型的輸入向量為散亂點 X，輸出層 k個神經元為折線上的頂點,神經元的權向量Wj=[wj1,wj2, wj3]T, j=1,2,…, k為折線上頂點vj的坐標。在學習過程中，獲取與散亂點 X歐氏距離最小的折線頂點作為競爭獲勝頂點vw，將它和它的拓撲鄰域內的頂點向該散亂點移動。通過這種移動，使頂點的位置更逼近散亂點。該過程如圖2所示。

圖2 折線頂點的學習過程

折線上每一頂點有一計數器，其值的大小反映該頂點活動性的強弱。在學習每一散亂點時，更新所有頂點計數器值，使競爭獲勝頂點和它拓撲鄰域內的頂點計數器值增大，其它頂點計數器值減小。學習指定個數散亂點后，分裂活動性強的頂點，刪除活動性最弱的頂點。分裂頂點和刪除頂點過程如圖3所示。圖3(b)中，頂點E分裂后新增一頂點F，圖3(c)中，C點被刪除后，相鄰兩頂點相連形成一條新邊。模型通過對散亂點的學習，持續分裂活動性強的頂點和刪除活動性最弱的頂點，使折線上頂點個數不斷增長并愈來愈逼近實際曲線，從而實現曲線重建。

圖3 頂點的分裂和刪除

2 曲線重建算法

使用成長型神經網絡以線段為基元的曲線重建算法的基本思路是：從散亂點集中隨機取出一散亂點，在折線上找出與該點歐氏距離最小的頂點作為競爭獲勝頂點，將它向該散亂點移動一定距離；同時調整其拓撲鄰域內的各頂點的位置和所有頂點計數器值，在學習過程中，不斷分裂活動性強的頂點，刪除活動性最弱的頂點。直至滿足預定的結束條件。

如上所述，折線用L表示，折線上頂點v的集合用V表示，算法的步驟如下：

（1）取初始折線L，設散亂點集P中的點數為 N，令 n＝0表示初始迭代次數，初始學習速率為η(n)<1。

（2）從P中隨機選取一散亂點X。

（3）在 V中找到與散亂點 X歐氏距離最小的頂點vw，如式（1）所示

（4）更新vw和它拓撲鄰域內頂點的位置。vw的新位置是它原來位置和采樣點X的位置的線性組合。如式（2）所示

vw拓撲鄰域內其他頂點位置的更新，如式（3）所示

式(3)中，λ(n)值如式（4）所示

式中 t為5～40較合適。

（5）更新學習速率η(n)，如式(5)所示

（6）更新L中所有頂點的計數器值，競爭獲勝頂點的計數器值的更新按式（6）進行

其它頂點計數器值的更新按式（7）進行

式中 α為小于1的正數。

（7）上述(2)～(6)步迭代若干次，分裂具有最高計數器值的頂點，如圖3(b)所示。折線L的彈性能量[10]如式（8）所示

式中 Q為折線上邊的集合。新增頂點的位置應使折線的彈性能量最小化。通過式（8）可求出折線新增頂點的位置應為分裂頂點較長鄰接邊的1/2處為宜。以圖3(b)為例，則F點坐標如式（9）所示

令式Z(F)=DF2+EF2，即求頂點F相鄰邊長度的平方和。則頂點分裂后E點和F點計數器值如式（10）和式（11）所示

（8）上述(2)～(7)步迭代若干次，刪除L中計數器值最小的一頂點。刪除該頂點后，連接它拓撲鄰域的兩頂點，如圖3(c)所示，拓撲鄰域內兩頂點計數器值保持不變。

上述(2)～(8)的過程重復迭代，直至達到預設最大迭代次數為止。

3 實驗結果與分析

作者在Pentium 4-2.5GHz 處理器、1024M內存微機平臺上，用VC6.0和OpenGL實現了本算法，用它對某些曲線的散亂數據點集訓練并進行重建，取得良好效果。圖4為的散亂點集。

圖5為 y =s inx, x ∈ [ 0,2π]散亂點集的重建過程，共使用 8740個散亂點。圖5(a)為包含 2個頂點的初始折線。

圖4 y=sinx的散亂點集

圖5 sinx曲線重建過程

表1給出了y=sinx重建過程中的相關參數。

表1 y=sinx重建相關參數

圖6為古代一刀具輪廓的散亂點集。

圖6 刀具輪廓散亂點集

圖 7為刀具散亂點集的重建過程，共使用6480個散亂點。圖7 (a)為包含3個頂點的初始折線。

圖7 刀具輪廓重建過程

表2給出了刀具重建過程中的相關參數。

表2 刀具重建相關參數

從圖5和圖7可看出，重建結果幾乎不受噪聲數據的影響，有非常好的重建效果。從表1和表2中可看出，曲線重建后，頂點間距已達到常用顯示設備像素間距水平，圖5折線上頂點投影到原始曲線的平均距離誤差幾乎為零，頂點對原始曲線有很好的擬合；輸入數據量與重建時間近似成線性關系，重建過程所需時間短，重建速度較快。

4 結束語

本文提出基于成長型神經網絡以線段為基元的曲線重建算法，使用該算法優化折線上頂點的位置，使折線更好地逼近散亂點；持續分裂折線上活動性強的頂點和刪除活動性最弱的頂點，使頂點的分布更符合散亂點數據的概率分布。實驗結果表明該算法十分有效，且具有重建速度快，不受散亂點數據量大小影響的特點。

[1]Várady Tamás, Ralph R R, Jordan Coxf. Reverse engineering of geometric models-an introduction [J].Computer-Aided Design, 1997, 29(4): 255-268.

[2]Alrashdan Abdalla, Motavalli Saeid, Fallah Behrooz.Automatic segmentation of digitized data for reverse engineering applications [J]. IIE Transactions, 2000,32(1): 59-69.

[3]Huang Jianbing, Menq Chia-hsiang. Automatic data segmentation for geometric feature extraction from unorganized 3-D coordinate points [J]. IEEE Transactions on Robotics and Automation, 2001, 17(3):268-279.

[4]Géza Kós, Martin R R, Várady Tamás. Methods to recover constant radius rolling ball blends in reverse engineering [J]. Computer Aided Geometric Deign,2000, 17(2): 127-160.

[5]Lu Zhen, Ke Yinglin, Sun Qing, et al. Extraction of blend body feature in reverse engineering [J]. Chinese Journal of Mechanical Engineering, 2003, 16(3):248-251.

[6]Ke Yinglin, Wang qing. Research on point cloud slicing technique in reverse engineering [J]. Journal of Computer–Aided Design & Computer Graphics, 2005,17(8): 1798-1802.

[7]Ke Yinglin, Li An. Extruded surface extraction base on unorganized point cloud in reverse engineering [J].Journal of Computer–Aided Design & Computer Graphics, 2005, 17(6): 1329-1334.

[8]Jun Y, Raja V, Park S. Geometric feature recognition for reverse engineering using neural networks [J].International Journal of Advanced Manufacturing Technology, 2001, 17(6): 462-470.

[9]Xiao Shaoyong, Jin Shigang, Shi Wenjun. Curve reconstruction based on orthogonal neural network [J].Journal of Image and Graphics, 2000, 5(1): 62-65.

[10]IVRISSIMTZIS I P, JEONG W-K, SEIDEL H-P.Using growing cell structures for surface reconstruction [DB/OL]. http://csdl2.computer.org/comp/proceedings/smi/2003/1845/00/18450288.pdf,2005-10-7.