基于MLS的點云模型特征提取算法的研究及應用

王杏等

摘要：點云數據處理技術一直都是逆向工程所研究的重要領域之一，對準確而形象地再現真實物體有著重要的意義。其中三維點云模型的特征提取對展現物體模型的三維基本信息有著重要的作用。本文從工程結構有限元分析的角度，對三維點云數據的預處理技術及其特征提取的算法等逆向工程中的關鍵技術進行了研究，并提出了一種改進的特征提取算法，將其應用于工程有限元模型的快速建立，用來減少建模人員在有限元建模時的工作量。

關鍵詞：MLS 點云模型 特征提取 線性相關性 有限元模型

1 概述

到目前為止，很多國內外學者對三維點云數據的特征提取進行了研究，但將提取的點云特征模型應用于建立工程有限元模型的研究未見報道[1][2][3]。鄒冬、龐明勇等于2011年采用估算投影殘差的方法來判別三維點云模型潛在的特征點，此算法能夠準確地提取點云模型上的特征點和特征線，但特征識別時間代價太高[4]。故本文結合研究對象棱角分明的特點，以及文獻[4]、[5]的優點與缺點，提出一種改進的基于MLS的點云模型特征提取的新算法，能夠快速、簡單、有效地提取研究對象的邊界特征點和特征線，并應用于建立三維有限元模型，在很大程度上減少結構有限元分析時建模的工作量，從而加快建立所研究的結構有限元模型。

2 基于MLS的點云模型特征的提取算法

2.1 邊界特征點的提取 假設預處理后的點云數據

2.2 自動生成特征線。由上述算法得到特征點集合P后，需要將這些特征點首尾連接，生成特征線集合L。本文結合最近點搜索方法和雙向搜索方法來實現邊界特征線的提取。

Step 1：在特征點集合P中，任取一點pi作為特征線的始點，記為pb，搜索離pb最近的點pi+1或者pi-1作為此特征線的終點pe，連接pbpe，記為l1，保存在特征線集合L 里。

將點集U按x，y，z三個方向最長軸的中值劃分成8個新的點集。使用二叉樹方法搜尋給定點pi的最近點集，用歐式距離公式計算各點集內的其中一點與pi（x，y，z）的距離，取其中距離值最小的點的集合作為最近點集。

由于距離公式涉及到開方運算，相對較慢，而比較距離的平方效果也一樣。因此本文采用比較平方的形式，將兩點間的距離公式定義為：

Step 2：以pb和pe作為新的起點，使用Step1的方法，從剩余的點集P中背向搜索相應的最近點pi+2與pi-1或pi+1與pi-2，作為下一終點連接起來，記為l2和l3，存入特征線集合L中，并對既為終點又為起始點的點加以標記。

Step 3：判斷特征點集合P是否均為標記的點，若為空，則停止搜索，否則轉到Step 1繼續進行。

2.3 特征修復。在生成的特征線中不可避免地會產生一些缺陷，導致提取點云特征模型不完整，主要有兩種情況[1]：一是單條特征邊的缺口；另一種是兩條或多條特征邊在角部區域形成夾角的情況。所以生成特征線之后，需要為交匯的特征線建立合適的連接角點。結合以上兩種情形，將改進后的特征修復方法介紹如下：

Step 1：從特征線集合L中任意選擇一條特征線li，以其終點pe為中心，r為半徑構造一個球鄰域，查找r-鄰域內的特征點或點集。若在此鄰域內無其他的終點，則標記終點pe為缺口，并將半徑r變為2r，繼續搜索另一終點。

若有1個，則認為是單個特征邊的缺口，將兩終點連接起來，并將新生成的特征線存入L集合。若無，則接著擴大半徑，迭代進行。為了能夠覆蓋特征線之間的空白區域，半徑參數r應選擇稍大一些。

Step 2：若r（2r）-鄰域點N（p）是數目大于或等于2，則認為是兩條或多條特征邊缺口。設點pi，pj，pk∈N（p），先尋找某一特征終點pi的次尾部特征點pi-1，并和點pi建立直線li。同樣為點pj，pk建立直線lj，lk。建立的三條直線反向延伸交于一點σ，記點σ為模型的角點。

3 實驗結果和分析

本文通過在VC++6.0的環境下，使用OpenGL編程實現了點云特征的提取算法，獲得了點云的特征模型。再通過導入AutoCAD 2007中獲得CAD模型，接著再導入到ANSYS 12.0大型有限元軟件中，經過一系列定義分析類型和材料參數，并對其施加網格劃分等簡單處理，最終將提取的點云特征模型應用于有限元模型的快速建立，為下一步進行結構有限元分析做好建模準備工作。

參考文獻：

[1]鄒冬，龐明勇.點云模型特征的提取算法[J].農業機械學報，2011，42（11）：222-227.

[2]陳義仁，王一賓，等.一種改進的散亂點云邊界特征點提取算法[J].合肥：計算機工程與應用，2012，48（23）：177.

[3]馬驪溟，徐毅，李澤湘.基于高斯曲率極值點的散亂點云數據特征點的提取[J].深圳：系統仿真學報，2008，20（8）：2341-2344.

[4]柯映林，范樹遷.基于點云的邊界特征提取直接提取技術[J].機械工程學報，2004，40（09）：116-120.

[5]賀美芳，周來水，朱延娟.基于局部基面參數化的點云數據邊界自動提取[J].機械科學與技術，2004，23（8）：912-915.endprint

摘要：點云數據處理技術一直都是逆向工程所研究的重要領域之一，對準確而形象地再現真實物體有著重要的意義。其中三維點云模型的特征提取對展現物體模型的三維基本信息有著重要的作用。本文從工程結構有限元分析的角度，對三維點云數據的預處理技術及其特征提取的算法等逆向工程中的關鍵技術進行了研究，并提出了一種改進的特征提取算法，將其應用于工程有限元模型的快速建立，用來減少建模人員在有限元建模時的工作量。

關鍵詞：MLS 點云模型 特征提取 線性相關性 有限元模型

1 概述

到目前為止，很多國內外學者對三維點云數據的特征提取進行了研究，但將提取的點云特征模型應用于建立工程有限元模型的研究未見報道[1][2][3]。鄒冬、龐明勇等于2011年采用估算投影殘差的方法來判別三維點云模型潛在的特征點，此算法能夠準確地提取點云模型上的特征點和特征線，但特征識別時間代價太高[4]。故本文結合研究對象棱角分明的特點，以及文獻[4]、[5]的優點與缺點，提出一種改進的基于MLS的點云模型特征提取的新算法，能夠快速、簡單、有效地提取研究對象的邊界特征點和特征線，并應用于建立三維有限元模型，在很大程度上減少結構有限元分析時建模的工作量，從而加快建立所研究的結構有限元模型。

2 基于MLS的點云模型特征的提取算法

2.1 邊界特征點的提取 假設預處理后的點云數據

2.2 自動生成特征線。由上述算法得到特征點集合P后，需要將這些特征點首尾連接，生成特征線集合L。本文結合最近點搜索方法和雙向搜索方法來實現邊界特征線的提取。

Step 1：在特征點集合P中，任取一點pi作為特征線的始點，記為pb，搜索離pb最近的點pi+1或者pi-1作為此特征線的終點pe，連接pbpe，記為l1，保存在特征線集合L 里。

將點集U按x，y，z三個方向最長軸的中值劃分成8個新的點集。使用二叉樹方法搜尋給定點pi的最近點集，用歐式距離公式計算各點集內的其中一點與pi（x，y，z）的距離，取其中距離值最小的點的集合作為最近點集。

由于距離公式涉及到開方運算，相對較慢，而比較距離的平方效果也一樣。因此本文采用比較平方的形式，將兩點間的距離公式定義為：

Step 2：以pb和pe作為新的起點，使用Step1的方法，從剩余的點集P中背向搜索相應的最近點pi+2與pi-1或pi+1與pi-2，作為下一終點連接起來，記為l2和l3，存入特征線集合L中，并對既為終點又為起始點的點加以標記。

Step 3：判斷特征點集合P是否均為標記的點，若為空，則停止搜索，否則轉到Step 1繼續進行。

2.3 特征修復。在生成的特征線中不可避免地會產生一些缺陷，導致提取點云特征模型不完整，主要有兩種情況[1]：一是單條特征邊的缺口；另一種是兩條或多條特征邊在角部區域形成夾角的情況。所以生成特征線之后，需要為交匯的特征線建立合適的連接角點。結合以上兩種情形，將改進后的特征修復方法介紹如下：

Step 1：從特征線集合L中任意選擇一條特征線li，以其終點pe為中心，r為半徑構造一個球鄰域，查找r-鄰域內的特征點或點集。若在此鄰域內無其他的終點，則標記終點pe為缺口，并將半徑r變為2r，繼續搜索另一終點。

若有1個，則認為是單個特征邊的缺口，將兩終點連接起來，并將新生成的特征線存入L集合。若無，則接著擴大半徑，迭代進行。為了能夠覆蓋特征線之間的空白區域，半徑參數r應選擇稍大一些。

Step 2：若r（2r）-鄰域點N（p）是數目大于或等于2，則認為是兩條或多條特征邊缺口。設點pi，pj，pk∈N（p），先尋找某一特征終點pi的次尾部特征點pi-1，并和點pi建立直線li。同樣為點pj，pk建立直線lj，lk。建立的三條直線反向延伸交于一點σ，記點σ為模型的角點。

3 實驗結果和分析

本文通過在VC++6.0的環境下，使用OpenGL編程實現了點云特征的提取算法，獲得了點云的特征模型。再通過導入AutoCAD 2007中獲得CAD模型，接著再導入到ANSYS 12.0大型有限元軟件中，經過一系列定義分析類型和材料參數，并對其施加網格劃分等簡單處理，最終將提取的點云特征模型應用于有限元模型的快速建立，為下一步進行結構有限元分析做好建模準備工作。

參考文獻：

[1]鄒冬，龐明勇.點云模型特征的提取算法[J].農業機械學報，2011，42（11）：222-227.

[2]陳義仁，王一賓，等.一種改進的散亂點云邊界特征點提取算法[J].合肥：計算機工程與應用，2012，48（23）：177.

[3]馬驪溟，徐毅，李澤湘.基于高斯曲率極值點的散亂點云數據特征點的提取[J].深圳：系統仿真學報，2008，20（8）：2341-2344.

[4]柯映林，范樹遷.基于點云的邊界特征提取直接提取技術[J].機械工程學報，2004，40（09）：116-120.

[5]賀美芳，周來水，朱延娟.基于局部基面參數化的點云數據邊界自動提取[J].機械科學與技術，2004，23（8）：912-915.endprint

摘要：點云數據處理技術一直都是逆向工程所研究的重要領域之一，對準確而形象地再現真實物體有著重要的意義。其中三維點云模型的特征提取對展現物體模型的三維基本信息有著重要的作用。本文從工程結構有限元分析的角度，對三維點云數據的預處理技術及其特征提取的算法等逆向工程中的關鍵技術進行了研究，并提出了一種改進的特征提取算法，將其應用于工程有限元模型的快速建立，用來減少建模人員在有限元建模時的工作量。

關鍵詞：MLS 點云模型 特征提取 線性相關性 有限元模型

1 概述

到目前為止，很多國內外學者對三維點云數據的特征提取進行了研究，但將提取的點云特征模型應用于建立工程有限元模型的研究未見報道[1][2][3]。鄒冬、龐明勇等于2011年采用估算投影殘差的方法來判別三維點云模型潛在的特征點，此算法能夠準確地提取點云模型上的特征點和特征線，但特征識別時間代價太高[4]。故本文結合研究對象棱角分明的特點，以及文獻[4]、[5]的優點與缺點，提出一種改進的基于MLS的點云模型特征提取的新算法，能夠快速、簡單、有效地提取研究對象的邊界特征點和特征線，并應用于建立三維有限元模型，在很大程度上減少結構有限元分析時建模的工作量，從而加快建立所研究的結構有限元模型。

2 基于MLS的點云模型特征的提取算法

2.1 邊界特征點的提取 假設預處理后的點云數據

2.2 自動生成特征線。由上述算法得到特征點集合P后，需要將這些特征點首尾連接，生成特征線集合L。本文結合最近點搜索方法和雙向搜索方法來實現邊界特征線的提取。

Step 1：在特征點集合P中，任取一點pi作為特征線的始點，記為pb，搜索離pb最近的點pi+1或者pi-1作為此特征線的終點pe，連接pbpe，記為l1，保存在特征線集合L 里。

將點集U按x，y，z三個方向最長軸的中值劃分成8個新的點集。使用二叉樹方法搜尋給定點pi的最近點集，用歐式距離公式計算各點集內的其中一點與pi（x，y，z）的距離，取其中距離值最小的點的集合作為最近點集。

由于距離公式涉及到開方運算，相對較慢，而比較距離的平方效果也一樣。因此本文采用比較平方的形式，將兩點間的距離公式定義為：

Step 2：以pb和pe作為新的起點，使用Step1的方法，從剩余的點集P中背向搜索相應的最近點pi+2與pi-1或pi+1與pi-2，作為下一終點連接起來，記為l2和l3，存入特征線集合L中，并對既為終點又為起始點的點加以標記。

Step 3：判斷特征點集合P是否均為標記的點，若為空，則停止搜索，否則轉到Step 1繼續進行。

2.3 特征修復。在生成的特征線中不可避免地會產生一些缺陷，導致提取點云特征模型不完整，主要有兩種情況[1]：一是單條特征邊的缺口；另一種是兩條或多條特征邊在角部區域形成夾角的情況。所以生成特征線之后，需要為交匯的特征線建立合適的連接角點。結合以上兩種情形，將改進后的特征修復方法介紹如下：

Step 1：從特征線集合L中任意選擇一條特征線li，以其終點pe為中心，r為半徑構造一個球鄰域，查找r-鄰域內的特征點或點集。若在此鄰域內無其他的終點，則標記終點pe為缺口，并將半徑r變為2r，繼續搜索另一終點。

若有1個，則認為是單個特征邊的缺口，將兩終點連接起來，并將新生成的特征線存入L集合。若無，則接著擴大半徑，迭代進行。為了能夠覆蓋特征線之間的空白區域，半徑參數r應選擇稍大一些。

Step 2：若r（2r）-鄰域點N（p）是數目大于或等于2，則認為是兩條或多條特征邊缺口。設點pi，pj，pk∈N（p），先尋找某一特征終點pi的次尾部特征點pi-1，并和點pi建立直線li。同樣為點pj，pk建立直線lj，lk。建立的三條直線反向延伸交于一點σ，記點σ為模型的角點。

3 實驗結果和分析

本文通過在VC++6.0的環境下，使用OpenGL編程實現了點云特征的提取算法，獲得了點云的特征模型。再通過導入AutoCAD 2007中獲得CAD模型，接著再導入到ANSYS 12.0大型有限元軟件中，經過一系列定義分析類型和材料參數，并對其施加網格劃分等簡單處理，最終將提取的點云特征模型應用于有限元模型的快速建立，為下一步進行結構有限元分析做好建模準備工作。

參考文獻：

[1]鄒冬，龐明勇.點云模型特征的提取算法[J].農業機械學報，2011，42（11）：222-227.

[2]陳義仁，王一賓，等.一種改進的散亂點云邊界特征點提取算法[J].合肥：計算機工程與應用，2012，48（23）：177.

[3]馬驪溟，徐毅，李澤湘.基于高斯曲率極值點的散亂點云數據特征點的提取[J].深圳：系統仿真學報，2008，20（8）：2341-2344.

[4]柯映林，范樹遷.基于點云的邊界特征提取直接提取技術[J].機械工程學報，2004，40（09）：116-120.

[5]賀美芳，周來水，朱延娟.基于局部基面參數化的點云數據邊界自動提取[J].機械科學與技術，2004，23（8）：912-915.endprint