產品模型點雲邊界特徵快速提取方法
2023-10-10 05:11:04 1
專利名稱：產品模型點雲邊界特徵快速提取方法
技術領域：
本發明提供一種產品模型點雲邊界特徵快速提取方法，屬於產品逆向工程技術領域。
背景技術：
在產品逆向工程中，通常採用雷射掃描儀等設備獲取產品實體模型表面的產品模型點雲， 產品模型點雲邊界特徵作為表達曲面的重要幾何特徵，其提取精度和速度對曲面重建的質量 和效率起著重要作用，邊界提取技術在逆向工程領域中的文物復原、曲面拼接、點雲補洞等 方面得到廣泛應用。
對現有技術文獻檢索發現，李江雄在學術期刊《機械設計與製造工程》2000， 29(2), P26-28 上發表的學術論文"反求工程中複雜曲面邊界線的自動提取技術"及白仲棟等在學術期刊《機 械科學與技術》2001， 20(4)， P481-482上發表的學術論文"複雜曲面反求工程中的邊界處理 技術研究"中，提出一種自動構造曲面邊界曲線的方法，將散亂點雲投影到一平面上，利用分 割法獲取包圍曲面的初始邊界曲線，通過對曲線光順獲取曲面邊界，此類方法僅適合於在平 面上投影不重疊的單值曲面，局限性大。柯映林等在學術期刊《機械工程學報》2004， 9(40), P116-120上發表的學術論文"基於點雲的邊界特徵直接提取技術"中，首先對點雲數據進行空 間三維劃分，建立基於空間柵格的邊界提取模型，然後通過研究線性時間複雜度的種子邊界 柵格識別和生長算法以及空間拓撲構型推理算法，從點雲數據中直接提取邊界信息，該算法 提取的邊界特徵點集包含部分內部點，提取精度低，無法直接擬合參數曲線。張獻穎等在學 術期刊《中國圖像圖形學報》2003, 8(10)， P1223-1226上發表的學術論文"空間三角網格曲 面的邊界提取方法"中，通過建立產品模型點雲的三角網格模型提取點雲邊界特徵，該算法邊 界特徵提取準確，但目前適應任何數據點雲的三角化算法還沒得到完全有效的解決，且三角 化算法本身時間複雜度高，需耗費大量的系統資源，所以基於三角網格拓撲結構提取點雲邊 界的效率非常低。
綜上所述，現有的產品模型點雲邊界提取方法存在邊界提取精度低、邊界提取效率低、 適用性差等問題。
發明內容
本發明的目的在於提供一種產品模型點雲邊界特徵快速提取方法，快速準確提取任意產品模型點雲的邊界特徵。其技術方案為
一種產品模型點雲邊界特徵快速提取方法，其特徵在於步驟依次為1)基於R、樹組織 產品模型點雲的動態空間索引結構；2)採用動態空心球擴展算法査詢目標點的yt近鄰點集， 過程具體是基於產品模型點雲動態空間索引結構採用深度優先遍歷算法査找包含目標點的
葉結點，計算其MBR即最小包圍矩形的外接球半徑r，以目標點為球心，〃2=^_/^為半徑，
確定空間球區域，獲取該空間球區域內的數據點，若數據點的個數大於A:，則從中査找與目
標點之間距離最近的a:個點，否則以當前球半徑為內徑即V-g，
+ 1為外徑，
其中"為已取得的近鄰點數，動態擴展空心球區域，直到球內包含的點數大於等於a:個，從 中查找與目標點之間距離最近的a個點，獲取目標點的a近鄰點集；3)將目標點及其a近鄰 點集作為局部型面參考數據，建立其切平面，方法具體是以最小二乘法擬合局部型面參考 數據的切平面，設平面方程為C^ + C2^ + C^ + C4-0，其矩陣方程為^0 = 0，式中
formula see original document page 5
則切平面方程為
formula see original document page 5
採用特徵向量估計法求解該方程，對矩陣j"^進行奇異值分解得
formula see original document page 5
其中c/和f為正交矩陣，a、 ％、 "3、 a為4^4的特徵值，其中最小特徵值對應的特徵
向量即為切平面方程的最小二乘解，從而求得目標點及其a:近鄰點集的切平面；4)將局部型 面參考數據投影到其切平面上，並建立投影點的基準平面；5)將各投影點到基準平面的距離 與目標點到該平面的距離進行比較，判斷目標點是否為邊界點，識別點雲邊界特徵。為實現發明目的，所述的產品模型點雲邊界特徵快速提取方法，在步驟4)中，建立投影 點基準平面的方法具體是設目標點局部型面參考數據在其切平面上的投影點集為
X = {p,|/ = 0，U}，由公式C = + 計算該點集的型心c，設目標點的投影點為
,'=0
p,作向量1^;,從點集z中査詢距目標點投影點/)最遠的點w，建立到點/)距離為1/ 鵬|且
垂直於向量v的平面丄，以點集義的基準平面，考察點集的分布情況，設^ =( ,^，、)， c = (^，K，^)，則基準平面丄的方程可由公式jjc ++ Cz + ￡> = 0表示，式中^4=^1，醜=^—X，
一 1
—zc, d採用公式d=) /H 5 —計算。
為實現發明目的，所述的產品模型點雲邊界特徵快速提取方法，在步驟5)中，判斷目標
點是否為邊界點的方法具體是設p, = O,，X，z,.)為點集％中任一點，則點a到平面Z的距
」
離可採用公式^(/ ,,丄)=0^,.+外，+cz, +d)(j2+￡2 +c2)—n十算，所以目標點的投影點/ 到
平面丄的距離為dO，丄)，點集X中各點到Z的最大距離為maxW(/>,，Z)},令 /(/;) = JO，丄)(maxWO,.，丄》)-'並以其表徵目標點為邊界點的概率，將/0)與預設閥值0"比 較，若/(P)〉cj，則目標點為邊界點；否則目標點為內部點(根據經驗，C7取0.9-1.0時可
得到較理想的邊界特徵)。
本發明與現有技術相比，具有以下優點
1) 採用r、樹建立產品模型點雲空間索引結構，可對各種複雜型面產品模型點雲進行邊 界特徵提取；
2) 採用動態空心球擴展算法進行a近鄰查詢，實現了目標點局部型面參考數據的快速獲 取，可有效提高散亂點雲邊界特徵的提取效率；
3) 根據目標點局部型面參考數據在其切平面內的分布情況提取點雲邊界，可準確識別散 亂點雲的邊界特徵點。
圖1是本發明程序實現流程圖
圖2是本發明實施例一中的汽車產品模型點雲；
圖3~圖5是圖1所示實施例一汽車產品模型點雲空間索引結構各層結點mbr模型圖； 圖6是本發明中/t近鄰査詢時構建初始空心球示意圖；圖7是本發明中A近鄰査詢時獲取查詢區域內近鄰點示意圖； 圖8是本發明中A近鄰査詢時動態擴展空心球示意圖； 圖9是實施例一提取的邊界特徵點；
圖IO是實施例一採用自由曲線擬合的汽車模型邊界曲線； 圖11是本發明實施例二中的鈑金件產品模型點雲； 圖12是本發明實施例二提取的鈑金件的邊界特徵點。
具體實施例方式
下面結合附圖及實施例對本發明作進一步說明-
圖1是本發明產品模型產品模型點雲邊界特徵提取方法程序實現流程圖。首先建立產品
模型點雲的R、樹動態空間索引結構，其中將索引結構各結點統一表示為四維點對象，採用 k-means算法對產品模型點雲進行聚類分簇，完成產品模型點雲動態空間索引結構的建立；採 用動態空心球擴展算法査詢目標點的A:近鄰點集；將目標點及其A近鄰點集作為局部型面參 考數據，建立其切平面；將局部型面參考數據投影到其切平面上，並建立投影點的基準平面; 將各投影點到基準平面的距離與目標點到該平面的距離進行比較，設目標點的投影點p到平 面L的距離為rf(p,"，點集X中各點到丄的最大距離為max(c/(p,，丄))，令
/(/;)-d(/;,i:)(maxW(A,丄")—i並以其表徵目標點為邊界點的概率，將/(/ )與預設閥值<7比
較，若/0)〉o"，則目標點為邊界點；否則目標點為內部點。根據經驗，CJ取0.9 1.0時可
得到較理想的邊界特徵。
實施例一提取如圖2所示汽車模型一半點雲的邊界特徵。
圖3~圖5是圖2所示實施例一中產品模型點雲及其空間索引結構各層結點MBR模型圖， 實驗所用點雲的數據點數為3.6323萬，建樹的相關參數為結點最小子結點數/ =8、最大子結 點數M二20，結點重新插入次數及=17，產品模型點雲動態空間索引結構構建時間為5.247秒。 其中圖3顯示了汽車產品模型點雲動態空間索引結構根結點的MBR，圖4顯示了內部結點的 MBR，圖5顯示了葉結點的MBR。
圖6是本實施例構建初始空心球示意圖。取點雲數據文件中第一個點p(-26.8173,18.6080, -26.0836)為目標點，查詢其&近鄰點集(取* = 10),採用深度優先遍歷方法遍歷散亂點雲動 態空間索引結構，查詢目標點所在葉結點N並計算其MBR外接球半徑r，構建球心為目標點
p、內徑。為零、外徑。w、/^的初始空心球51(/^，。。圖7是本實施例確定查詢區域示意圖。採用深度優先遍歷方法獲取目標點所在的葉結點， 由公式(1)及公式(2)分別計算各結點MBR到目標點p的最小距離minD/W及最大距離 maxDM。若葉結點的MBR到目標點的最小距離小於空心球外徑且最大距離大於空心球內
徑，gPminZ)W〈^且maxD/W2n，則表明該葉結點與空心球相交，將與空心球相交的葉結 點集合作為査詢區域。
min Z)/W(/ ,及)=|p, - I (1)
其中^頂點。
v, A > v,， p,為點p第z'維坐標值，(m,.，v,)為葉結點R的MBR最小、最大
max Z)〖W(/ ， i ) = |/ ,. — r,. ||
(2)
其中^-f"' A>("'+J0/2， p,為點p第/維坐標值，("i,Vi)為葉結點R的MBR最 k,兌<(",+v,)/2
小、最大頂點。
計算查詢區域內各數據點到空心球球心的距離，若該距離值小於空心球外徑且大於空心 球內徑，則將該點添加到近鄰點序列L中。
圖8是本實施例自適應擴展空心球示意圖。若查詢到的近鄰點數小於用戶設定的閾值，
則將當前空心球so^,。擴展為空心球s'O^V2')，其內徑。'=^,外徑v二v--
+ 1 ，
確定與空心球S'(p,^力')相交的查詢區域，獲取S'(p,V,^)中數據點，並將距目標點較近的
丸-w個數據點添加到近鄰點序列L中，若L中數據點數為A:，則終止空心球的擴展，完成局部 型面參考數據的査詢；否則繼續擴展空心球。實驗證明，通常將空心球擴展1-2次便可滿足 査詢要求。通過擴展空心球內外半徑，可有效保證局部型面參考數據査詢算法的準確性。 以最小二乘法擬合局部型面參考數據的切平面，設平面方程為+ c2y + c3z + c4 = 0 ，
其矩陣方程為^6 = 0，式中
formula see original document page 8則切平面方程為
formula see original document page 9
採用特徵向量估計法求解該方程，對矩陣v4^4進行奇異值分解得
formula see original document page 9
其中f/和F為正交矩陣，a、 《2、 w3、 ^為^^4的特徵值，其中最小特徵值對應的特徵 向量即為切平面方程的最小二乘解，從而求得目標點及其&近鄰點集的切平面，平面方程為 0.1764x — 0.9843少—0.0058z + 22.8873 = 0 。
將目標點局部型面參考數據中各點按公式《=^-^^"向其切平面上投影(其中，《
HI
為目標點局部型面參考數據中任意一點，#1為其切平面法矢)，目標點的投影點p坐標為
_i *
(-26.9937， 19.5923, -26.0778)，按公式C = (A: + l)— Sp,計算所有投影點的型心c = (-25.7794，
19.0163,-27.8830)，向量v = pc=(1.2143, -0.5760,0.8052)，距離p最遠的投影點m為(-23.8034, 18.0790, -26.5727)，基於點法式求得目標點局部型面參考數據的基準平面方程 1.2 143jc - 0.5760_y + 0馬2z + 60.7143 = 0 。
_ i
採用公式4/ ") = (^+^+(^+^)042+52+<^)—5計算點p到基準平面的距離，得
Ap，丄)-3.5656mm，所有投影點中到基準平面的最大距離為3.5703mm，兩者之間的比值為
0.9987，所以目標點為邊界點。
判斷其它各點是否為邊界點方法同上，提取的邊界點如圖9所示，提取時間為1.19s，採
用自由曲線擬合提取的邊界點獲得的汽車模型邊界曲線如圖10所示。
實施例二提取如圖ll鈑金件模型產品模型點雲的邊界特徵，方法同上，提取的邊界
特徵點如圖12所示，提取時間為0.263s。
權利要求
1、一種產品模型點雲邊界特徵快速提取方法，其特徵在於步驟依次為1)基於R*-樹組織產品模型點雲的動態空間索引結構；2)採用動態空心球擴展算法查詢目標點的k近鄰點集，過程具體是基於產品模型點雲動態空間索引結構採用深度優先遍歷算法查找包含目標點的葉結點，計算其MBR即最小包圍矩形的外接球半徑r，以目標點為球心，為半徑，確定空間球區域，獲取該空間球區域內的數據點，若數據點的個數大於k，則從中查找與目標點之間距離最近的k個點，否則以當前球半徑為內徑即r1′＝r2，為外徑，其中n為已取得的近鄰點數，動態擴展空心球區域，直到球內包含的點數大於等於k個，從中查找與目標點之間距離最近的k個點，獲取目標點的k近鄰點集；3)將目標點及其k近鄰點集作為局部型面參考數據，建立其切平面，方法具體是以最小二乘法擬合局部型面參考數據的切平面，設平面方程為c1x+c2y+c3z+c4＝0，其矩陣方程為Ac＝0，式中則切平面方程為採用特徵向量估計法求解該方程，對矩陣ATA進行奇異值分解得其中U和V為正交矩陣，ω1、ω2、ω3、ω4為ATA的特徵值，其中最小特徵值對應的特徵向量即為切平面方程的最小二乘解，從而求得目標點及其k近鄰點集的切平面；4)將局部型面參考數據投影到其切平面上，並建立投影點的基準平面；5)將各投影點到基準平面的距離與目標點到該平面的距離進行比較，判斷目標點是否為邊界點，識別點雲邊界特徵。
2、 如權利要求1所述的產品模型點雲邊界特徵快速提取方法，其特徵在於在步驟4) 中，建立投影點基準平面的方法具體是設目標點局部型面參考數據在其切平面上的投影點集為1 = {/;;|/ = 0,1廣^}，由公式c = (A: + l)—^/;,.計算該點集的型心c，設目標點的投影點為P，作向量v = ^ ，從點集;r中查詢距目標點投影點p最遠的點附，建立到點p距離為|/wf|且垂直於向量v的平面Z ，以點集Z的基準平面，考察點集的分布情況，設/^ =( ,力,^)， c = (、,k，^)，則基準平面Z的方程可由公式爿x ++ Cz + Z) = 0表示，式中及=&1，」C=^—^，"採用公式/H (^2 +甘+C2)— —2 —04$十辦p 計算。
3、 如權利要求1所述的產品模型點雲邊界特徵快速提取方法，其特徵在於在步驟5) 中，將各投影點到基準平面的距離與目標點到該平面的距離進行比較，判斷目標點是否為邊 界點，方法具體是設A-0,.，X，Z,.)為點集X中任一點，則點/7,到平面i:的距離可採用公式^(/;;,￡) = 0^ +5乂 +Cz, +Z))(^2 +(:2)1計算，所以目標點的投影點/;到平面丄的距 離為i/(/;,Z)，點集X中各點到丄的最大距離為max{^>,，Z)}， 令/(p) = d(/7,Z)(maxW(/;;,Z)})-'並以其表徵目標點為邊界點的概率，將/(/0與預設陶值O"比較，若/0)>0"，則目標點為邊界點；否則目標點為內部點，cr取值範圍為0.9~1.0。
全文摘要
本發明提供一種產品模型點雲邊界特徵快速提取方法，其特徵在於基於R*-樹組織產品模型點雲的動態空間索引結構，採用動態空心球擴展算法查詢目標點的k近鄰點集，將目標點及其k近鄰點集作為局部型面參考數據，建立其切平面，將局部型面參考數據投影到其切平面上，並建立投影點的基準平面，將各投影點到基準平面的距離與目標點到該平面的距離進行比較，判斷目標點是否為邊界點，識別點雲邊界特徵。採用本方法可快速、準確提取產品模型點雲的邊界特徵。
文檔編號G06K9/46GK101510308SQ20091002020
公開日2009年8月19日 申請日期2009年3月26日 優先權日2009年3月26日
發明者健 劉, 孫殿柱, 崔傳輝, 朱昌志 申請人:山東理工大學