王世東 ， 張佑生， 王煥寶

（1. 中國科學(xué)技術(shù)大學(xué)火災(zāi)科學(xué)國家重點實驗室，安徽 合肥 230026;2. 安徽建筑工業(yè)學(xué)院信息網(wǎng)絡(luò)中心，安徽 合肥 230022;3. 安徽三聯(lián)學(xué)院計算機科學(xué)與技術(shù)系，安徽 合肥 230601）

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

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

1 曲線重建原理

1.1 成長型神經(jīng)網(wǎng)絡(luò)

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

圖1 一維輸出的SOM模型

GCS網(wǎng)絡(luò)是一種特殊的SOM網(wǎng)絡(luò)，它能夠增量生長。該網(wǎng)絡(luò)在學(xué)習(xí)輸入向量的過程中，根據(jù)神經(jīng)元競爭獲勝次數(shù)的多少確定它們活動性的強弱，分裂活動性強的神經(jīng)元，刪除活動性最弱的神經(jīng)元，使網(wǎng)絡(luò)更好地體現(xiàn)輸入向量的內(nèi)在特征。

1.2 曲線重建模型

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

圖2 折線頂點的學(xué)習(xí)過程

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

圖3 頂點的分裂和刪除

2 曲線重建算法

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

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

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

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

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

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

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

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

式中 t為5～40較合適。

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

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

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

式中 α為小于1的正數(shù)。

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

圖4 y=sinx的散亂點集

圖5 sinx曲線重建過程

表1給出了y=sinx重建過程中的相關(guān)參數(shù)。

表1 y=sinx重建相關(guān)參數(shù)

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

圖6 刀具輪廓散亂點集

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

圖7 刀具輪廓重建過程

表2給出了刀具重建過程中的相關(guān)參數(shù)。

表2 刀具重建相關(guān)參數(shù)

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

4 結(jié)束語

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

[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.