基於數據動態存取模型的產品點雲型面特徵分析方法
2023-07-22 11:31:36
專利名稱：基於數據動態存取模型的產品點雲型面特徵分析方法
技術領域：
本發明提供一種基於數據動態存取模型的產品點雲型面特徵分析方法，屬於產品逆向工程技術領域。
背景技術：
在逆向工程中，點雲型面特徵分析可以基於產品局部型面數據對所有測量點進行型面特徵參數估算以實現點雲型面特徵的整體性評估，是數據預處理及曲面模型重建過程中的關鍵性技術之一，其實現方法主要有三種三角面片法矢量估計法、局部數據點集拋物面逼近估計法和採樣點4D Shepard插值計算法。
三角面片法矢量估計法採用三角曲面模型對點雲進行插值或逼近，根據三角曲面模型中相鄰三角面片法矢量方向的變化狀況對點雲型面進行整體型面特徵區域評估。該方法對於數據分布較為均勻的點雲，評估結果較為準確，但存在著三角曲面模型生成過程複雜、存儲冗餘度高，相鄰面片查詢效率低等不足。另外，該方法易受點雲中噪聲數據的幹擾而導致型面特徵分析結果失真。
局部數據點集拋物面逼近估計法以點雲中任意一個數據點作為目標點，通過查詢其鄰近點獲取點雲局部型面參考數據點集，以拋物面對該數據點集進行逼近，然後計算當前點在拋物面上對應點的曲率值，並以該值作為目標點在點雲型面上對應點的型面曲率估算結果。採用該方法可計算出點雲全部數據點的型面曲率值，根據數據點曲率分布狀況來描述點雲型面特徵，其數據適應性優於三角面片法矢量估計法。但由於該方法基於靜態數據結構實現點雲數據的存取管理，無法有效實現數據近鄰點查詢，其數據處理效率受數據點雲規模的限制；另外，拋物面對於型面較為複雜的局部數據點集逼近精度低，影響點雲整體數據型面特徵分析結果的準確性。
採樣點4D Shepard插值計算法首先採用柵格空間八叉樹細分方法對點雲進行全局採樣處理，對點雲採樣數據建立4D Shepard插值曲面模型，將點雲中任意點的坐標值代入4D Shepard曲面公式中即可計算出該點曲率值。在計算出點雲所有數據點的型面曲率值後，後續處理與局部數據點集拋物面逼近估計法同。該方法對於數據分布均勻的點雲可以很好地避免數據噪聲的幹擾，點雲曲率計算過程穩定，但由於目前所採用的點雲採樣算法對所處理數據的自適應性差，在點雲數據分布不均勻、型面特徵結構較複雜的情況下，採樣結果準確性低，導致生成的4D Shepard曲面模型精度低，從而影響了最終型面特徵分析結果的準確性。另外，在柵格空間八叉樹細分以及4D Shepard曲面插值中皆進行了大量的拋物面逼近局部數據點集處理，降低了算法的整體執行效率。
綜上所述，現有的點雲型面特徵分析方法僅在特定條件下可以獲得較好的分析結果，對於不同數據規模、拓撲類型及型面複雜程度的點雲數據缺乏通用性，導致點雲型面參數計算過程的穩定性與計算結果的準確性都無法滿足工程需求。
發明內容
為克服現有點雲型面特徵分析方法的不足，本發明目的在於提供一種基於數據動態存取模型的產品點雲型面特徵分析方法。該方法可準確地對點雲型面特徵進行整體性評估，根據評估結果進行產品模型重建，能顯著提高逆向工程建模效率及模型精度，其實現方案為一種基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於步驟依次為1)點雲數據輸入；2)基於三維R*-tree為點雲創建數據動態存取模型；3)估算點雲中所有數據點的型面曲率值；4)根據點雲中所有數據點的型面曲率值分布對點雲型面特徵進行整體評估。
為實現發明目的，所述的多維數據動態存取機制，在步驟1)中將產品數位化設備輸出的數據點雲文件讀入到存儲器中，並為數據建立線性表存儲結構，以滿足對數據結點基本存儲及數據順序遍歷的需求。
為實現發明目的，所述的基於數據動態存取模型的產品點雲型面特徵分析方法，在步驟2)中，以相互嵌套的多維矩形對點雲數據進行聚類劃分，組織數據點之間的拓撲鄰近關係，為點雲建立一種支持數據動態存取的平衡樹數據動態存取模型。
為實現發明目的，所述的基於數據動態存取模型的產品點雲型面特徵分析方法，在步驟3)中對點雲數據線性表進行順序遍歷，以當前遍歷點為目標點查詢其鄰近數據點獲取點雲局部型面參考數據點集，並對其逼近生成自由樣條曲面，在曲面上計算目標點參數對應點的高斯曲率值，以該曲率值作為目標點的型面曲率值。完成上述遍歷過程後，即可計算出所有數據點型面曲率值。
為實現發明目的，所述的基於數據動態存取模型的產品點雲型面特徵分析方法，在步驟3)中點雲局部型面參考數據的獲取方法是以目標點為球心，建立一個可自適應向外擴散的空心球區域，將其與數據動態存取模型多維矩形進行區域求交，獲取落入交集空間中的近鄰點。以目標點及其近鄰點構成點雲局部型面參考數據來表達點雲局部型面幾何特徵。
為實現發明目的，所述的基於數據動態存取模型的產品點雲型面特徵分析方法，在步驟3)中，對點雲局部型面參考數據矩形域參數化過程中，首先需要對所獲取的點雲局部型面參考數據採用微切平面逼近並將點集投影到微切平面；然後為投影點集建立參數坐標系，將投影點集由世界坐標系變換到在該坐標系下；最後，計算點集的二維最小包圍矩形域，在該區域中將投影點坐標值進行正規化處理，處理後的投影點坐標即為對應點雲局部型面參考數據點的參數值。
為實現發明目的，所述的基於數據動態存取模型的產品點雲型面特徵分析方法，在步驟4)中，將點雲中所有數據點的型面曲率值映射為RGB顏色值，從而生成點雲型面彩色曲率雲圖，以曲率雲圖漸進變化的顏色區域反映點雲型面特徵。
本發明與現有技術相比，具有以下優點1)為點雲建立了動態存取模型，通過對點雲數據進行空間聚類劃分來組織數據的拓撲關係，提高了點雲型面特徵分析方法對於點雲數據類型的自適應性。
2)可快速獲取點雲型面局部參考數據點集以準確表現點雲局部型面特徵，提高了點雲型面特徵分析結果的穩定性。
3)採用Bezier曲面片對點雲局部型面參考數據精確逼近，提高了點雲型面特徵分析結果的準確性。
圖1是本發明程序流程圖。
圖2是本發明步驟二所建立的數據動態存取模型示意圖。
圖3～圖7是本發明整車外部型面點雲實施例數據動態存取模型各層索引結點三維最小包圍矩形模型圖。
圖8是本發明步驟三點雲數據型面曲率計算程序流程圖。
圖9～圖11是本發明點雲局部型面參考數據參數化示意圖。
圖12是本發明對某點雲局部型面參考數據逼近生成的Bezier曲面片。
圖13～圖14是本發明型面特徵分析方法對某汽車車身點雲數據型面特徵分析效果。
圖15～圖16是本發明型面特徵分析方法對米老鼠點雲數據型面特徵分析效果。
具體實施例方式
下面結合附圖對本發明作進一步說明。
如圖1所示，是本發明點雲型面特徵分析程序實現流程圖。基於數據動態存取模型的點雲型面特徵分析程序包含數據輸入程序1，點雲數據動態存取模型構建程序2，點雲數據型面曲率計算程序3，以及點雲型面特徵整體性評估程序4。其中，數據輸入程序1負責讀入產品數位化採集設備輸出的三維點雲數據，並為其創建線性表存儲結構，以支持對數據點線性順序遍歷。當點雲線性表所佔用內存儲空間超出內存儲器容量時，可存儲於輔存設備的數據文件中。點雲數據動態存取模型構建程序2採用嵌套的三維矩形對點雲數據進行動態空間聚類劃分，為數據輸入程序1所生成的數據線性表建立上層R*-tree動態空間索引結構。點雲數據型面曲率計算程序3通過順序遍歷點雲數據線性表，計算出點雲中所有數據點的型面曲率值。在點雲型面特徵整體性評估程序4中，將點雲數據點型面曲率值映射為RGB顏色雲圖，以曲率雲圖漸進變化的顏色區域反映點雲型面特徵。
如圖2所示，是本發明點雲數據動態存取模型構建程序2採用C++程序設計語言為三維R*-tree為點雲建立的數據動態存取模型示意圖。數據動態存取模型的索引結點分為根結點、內部索引結點和葉索引結點，其中內部索引結點中存儲了其父結點地址、子結點(可能是內部索引結點，也可能是葉索引結點)地址表和該結點的三維最小包圍矩形參數(即三維矩形兩對角頂點信息)。葉索引結點中存儲了其父結點地址、數據結點地址表和該結點的空間最小包圍矩形(Spatial Minimum Box Rectangle SMBR)信息。多維數據動態存取模型數據結構的根結點結構可能與內部結點相同，也可能與葉索引結點相同，區別是其根結點的父結點地址為空。多維數據動態存取模型數據結構中的數據結點存儲空間對象信息項的地址。在各類索引結點的實現中，本發明利用C++純虛函數技術，在程序運行中，根據虛函數的返回值判別結點類型。對於多維數據動態存取模型各層結點的子結點數的上限M、下限m，以及R*樹結點重新插入數目R的取值，皆由用戶根據數據點雲的規模自行設置，通常取m＝M×40％，R＝M×30％。
如圖3～7所示，是本發明調用點雲數據動態存取模型構建程序2對來自於Atos三維掃描儀器輸出的整車外部型面數據點雲所建立的數據動態存取模型數據結構各層結點三維最小包圍矩形模型圖。實驗所用點雲的數據點數為85.6112萬，所採用的索引參數m＝40、M＝100，重新插入結點數R＝30，多維數據動態存取模型數據結構構建時間約為110秒。其中圖3顯示了整車外部型面數據動態存取模型數據結構的根結點的SMBR，圖4顯示了其首層內部索引結點的SMBR，圖5)顯示了第二層內部索引結點的SMBR，圖6顯示了葉索引結點SMBR，圖7顯示了數據結點層，即原始整車外部型面數據，由於是對稱件，所以僅掃描了車身的一側。該實驗表明，採用三維動態索引結構可準確實現對產品反求工程中大規模散亂數據的空間聚類劃分，具有較高的數據自適應性。
如圖8所示，是本發明點雲數據型面曲率計算程序3實現流程圖。點雲數據型面曲率計算程序3在對點雲數據線性表順序遍歷中，以當前遍歷到的數據點作為目標點，依次調用目標點近鄰查詢程序5、數據點集參數化程序6、Bezier曲面片逼近程序7及目標點曲率估算程序8，最後輸出點雲中所有數據點的型面曲率值。其中目標點近鄰查詢程序5對目標點的k近鄰進行快速查詢，準確獲取點雲局部型面參考數據點集。數據點集參數化程序6對目標點近鄰查詢程序3提取的數據點集進行矩形域自由曲面參數分配，為點集中每個數據點分配一個二維參數坐標(u，v)。Bezier曲面逼近程序7對參數化後的點雲局部型面參考數據點集採用最小二乘法精確逼近生成用於體現點雲型面微分幾何性質的Bezier曲面片。目標點曲率估算程序8根據數據點集參數化程序6為目標點所分配的參數值，在Bezier曲面逼近程序7中生成的曲面上計算出對應點的高斯曲率值，並以該值作為目標點的型面曲率值。
目標點近鄰查詢程序5包含點查詢程序9、範圍查詢程序10。其中，點查詢程序9負責快速確定目標點所在的葉索引結點地址，範圍查詢程序10則負責搜索落入用戶指定區域中的數據點。目標點近鄰查詢程序5會首先調用點查詢程序9在數據動態存取模型中確定目標點所在的葉索引結點，由該葉索引結點的三維最小包圍矩形參數初始化一個空心球區域S(c，r1，r2)，其球心c為三維最小包圍矩形中心，內徑r1＝0，外徑r2=rkM]]>(r為三維最小包圍矩形外接球半徑，k為用戶指定的目標點近鄰點數)；然後調用範圍查詢程序10搜索落入S(c，r1，r2)的數據點，這些數據點即為目標點的鄰近點。若所獲取的鄰近點數小於k，則對S(c，r1，r2)根據公式r1＝r2，r2=r2k-nn+1]]>進行自適應擴散；若所獲取的鄰近點數大於或等於用戶指定k值，則程序返回前k個數據點信息。
點查詢程序9具體實現步驟如下1)設指針pCurrent指向多維數據動態存取模型根結點；2)若pCurrent所指結點類型為葉索引結點，且查詢目標點落入該結點SMBR中，則程序返回pCurrent；若查詢目標點未落入該結點SMBR中，則程序返回空值；3)順序遍歷pCurNode所指結點的子結點，在遍歷中，遞歸調用點查詢操作，新建指針類型retPtr，接受點查詢操作的返回值；4)返回retPtr。
範圍查詢程序10具體實現步驟如下1)設pCurNode指向多維數據動態存取模型數據結構根結點；2)若pCurNode所指結點為葉結點類型且該結點三維最小包圍矩形與空間查詢域相交，則將pCurNode所指結點內落入空間查詢域的子結點依次添加到全局線性表中，然後程序返回；3)順序遍歷pCurNode所指結點的子結點，在遍歷中，以當前子結點作為查詢子樹遞歸調用範圍查詢操作。
如圖9～11所示，是本發明數據點集參數化程序6的工作過程示意圖。在圖9中，目標點為x，且點雲局部型面參考數據點集為X。採用最小二乘法生成點集X的微切平面，然後將X向微切平面投影，得到投影點集X′。在圖10中，以X′中目標點x的投影點x′為坐標原點，以x′與其在點集X′中距其最遠的投影點構成向量u，另設微切平面的法向量為w，可得向量v＝w×u。由向量u、v、w建立右手正交坐標系C。如圖11所示，將點集X′變換到該坐標系下，得點集X″，分別對X″中數據點的u坐標值和v坐標值遞增排序，得兩個坐標分量序列Uc＝{uci|i＝0，1，…，k}和Vc＝{Vci|i＝0，1，…，k}。在坐標系C下，計算出點集X″的uv平面最小包圍矩形((uc0，vc0)，(uck，vck))及其u向邊長lu和v向邊長lv，然後對點集X″中任意數據點(ui，vi)的坐標按公式ui=ui-ucilu,vi=vi-vcilv]]>進行正規化處理。由於點集X、X′和X″中的數據點存在一一映射關係，所得(ui′，vi′)即為對點集X中對應三維數據點的參數值。
在Bezier曲面逼近程序7的實現中，設對參數化後的點雲局部型面參考數據點集X的n×m次Bezier曲面插值公式為S(ui,vi)=i=0nj=0mBi,n(uk)Bj,m(vk)pi,j=qt]]>(qt∈X，t＝0，1，2，…，k)。若將插值公式中的Bezier曲面基函數記為Di，j(u，v)＝Bj，n(u)Bj，m(v)，則Bezier曲面插值公式可寫成矩陣方程D=D0,0(u0,v0)D0,1(u0,v0)D0,m(u0,v0)Dn,0(u0,v0)Dn,m(u0,v0)D0,0(uk,vk)D0,1(uk,vk)D0,m(uk,vk)Dn,0(ukvk)Dn,m(uk,vk)]]>對該方程，點雲局部型面參考數據點集中的點數k可能大於(n×m)，也可能小於或者等於(n×m)，因此對應插值曲面的控制點集可能有無限多解，也可能無解或者有唯一解。本發明採用奇異值分解法對該矩陣方程進行求解，最終可得插值曲面的控制點集的一個最優解。設係數矩陣D的奇異值分解結果為D＝UWVT，其中U為(k+1)×(m+1)(n+1)的列正交矩陣，W為元素均為正數或0的(k+1)階對角陣，V為(m+1)(n+1)階正交矩陣。因而Bèzier曲面的控制點集最終解可寫為p0,0p0,mpn,m=VW-1U-1q0q1qk]]>在獲取控制點集的解後，即可確定逼近點雲局部型面參考數據點集的Bezier曲面表達式。
如圖12所示，為Bezier曲面逼近程序5對點雲中一組局部型面結構較為複雜的參考數據逼近生成的曲面，數據逼近精度為0.0031mm(曲面與參考數據距離均值)，標準差為0.0027。實驗表明，採用Bezier曲面可以不受數據型面複雜性的限制。
在目標點曲率估算程序6中，曲面上目標點對應參數位置的高斯曲率值的計算公式為K=(Suun)(Svvn)-(Suvn)2Su2Sv2-(SuSv)2]]>式中Bèzier曲面S(u，v)上任意位置的法向量，可由n=SuSv|SuSv|]]>求得。另外Su、Sv為n×m次Bèzier曲面的一階偏導，Suu、Svv、Suv為曲面的二階偏導。最後將所求得高斯曲率值作為目標點的型面曲率值。
在點雲型面特徵整體性評估程序4中，對點雲中數據型面曲率值進行排序，統計其分布範圍，得到曲率值分布區間[Ca，Cb]及曲率均值 。將計算機中RGB顏色索引表分為增1或減1步進區間[rgb(0,255,0)，rgb(255,255,0)]和[rgb(255,255,0)，rgb(255,0,0)]兩個顏色索引區間，所表達的顏色遞進關係是由綠色遞進到黃色，再由黃色遞進到紅色。在點雲數據型面曲率區間[ ]與[rgb(0,255,0)，rgb(255,255,0)]之間為其建立等分區間段映射關係；對區間[ ]與[rgb(255,255,0)，rgb(255,0,0)]作同樣處理。最後可以實現在點雲數據型面曲率較低區域以綠色系顯示，在點雲數據型面曲率均值附近區域以黃色系顯示，在曲率最大附近區域，以紅色高亮域顯示。
如圖13所示，是某汽車車身點雲數據，圖14是其型面特徵分析RGB顏色雲圖。圖15為本發明對型面較複雜的米老鼠點雲數據，圖16是其型面特徵分析RGB顏色雲圖。圖中點雲數據由低到高的型面曲率區間被圖形化為由暗到明的顏色區域。通常型面曲率較小且變化幅度低的區域為模型主結構型面，在曲面建模中，將這部分區域所對應的數據提取出來，快速完成產品型面的主結構的構造。圖中，主結構型面的過渡區域為圓角特徵，這部分特徵由於型面曲率較大且變化幅度也大，顯示為亮度較高的黃、紅色系。
權利要求
1.一種基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於依次包含以下步驟1)將產品數位化設備輸出的數據點雲文件讀入到存儲器中，並為數據建立線性表存儲結構；2)基於三維R*-tree為點雲創建數據動態存取模型；3)估算點雲中所有數據點的型面曲率值；4)根據點雲中所有數據點的型面曲率值分布對點雲型面特徵進行整體評估。
2.如權利要求1所述的基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於步驟2)中，以相互嵌套的多維矩形對點雲數據進行聚類劃分，組織數據點之間的拓撲鄰近關係，為點雲建立一種支持數據動態存取的平衡樹數據動態存取模型。
3.如權利要求1所述的基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於步驟3)中對點雲數據線性表進行順序遍歷，以當前遍歷點為目標點查詢其鄰近數據點獲取點雲局部型面參考數據點集，並對其逼近生成自由樣條曲面，在曲面上計算目標點參數對應點的高斯曲率值，以該曲率值作為目標點的型面曲率值，遍歷結束後，即可計算出所有數據點型面曲率值。
4.如權利要求3所述的基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於點雲局部型面參考數據點集的獲取方法是以目標點為球心，建立一個可自適應向外擴散的空心球區域，將其與數據動態存取模型多維矩形進行區域求交，獲取落入交集空間中的近鄰點，以目標點及其近鄰點構成點雲局部型面參考數據。
5.如權利要求3所述的基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於對點雲局部型面參考數據矩形域參數化過程中，首先需要對所獲取的點雲局部型面參考數據採用微切平面逼近並將點集投影到微切平面；然後為投影點集建立參數坐標系，將投影點集由世界坐標系變換到在該坐標系下；最後，計算點集的二維最小包圍矩形域，在該區域中將投影點坐標值進行正規化處理，處理後的投影點坐標即為對應點雲局部型面參考數據點的參數值。
6.如權利要求1所述的基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於步驟4)中，將點雲中所有數據點的型面曲率值映射為RGB顏色值，從而生成點雲型面彩色曲率雲圖，以曲率雲圖漸進變化的顏色區域反映點雲型面特徵。
全文摘要
本發明提供一種基於數據動態存取模型的產品點雲型面特徵分析方法，其特徵在於首先將產品數位化設備輸出的數據點雲文件讀入到存儲器中，並為數據建立線性表存儲結構；然後採用三維R*－tree對點雲數據進行快速空間聚類劃分，建立數據動態存取模型；然後在對點雲數據順次遍歷過程中，以當前數據結點為目標點，基於數據動態存取模型快速獲取點雲局部型面參考數據點集，採用Bezier曲面精確逼近該點集估算目標點的型面曲率值；最後將點雲中所有數據點的型面曲率值映射為RGB顏色模式，以型面曲率顏色雲圖顯示點雲整體型面特徵分布。實驗結果表明該方法數據適應性強、點雲型面曲率計算結果穩定、準確，可顯著提高逆向工程建模效率及模型精度。
文檔編號G06F17/00GK101017476SQ200610045319
公開日2007年8月15日 申請日期2006年7月10日 優先權日2006年7月10日
發明者孫殿柱, 李延瑞, 範志先 申請人:山東理工大學