三維掃描的點雲孔洞填補方法

2023-05-29 00:36:36 3

專利名稱：三維掃描的點雲孔洞填補方法
技術領域：
本發明涉及一種對三維圖形的修補方法，尤其涉及一種三維掃描的點雲孔洞填補方法。
背景技術：
逆向工程(Reverse Engineering，RE)技術是20世紀80年代後期出現在先進位造領域裡的新技術，其一般包括四個基本環節三維形體檢測與轉換(物理數據的獲得)、數據預處理(點雲處理、識別、多視拼接)，CAD模型的建立(曲面重構)、CAM製件成型，其基本流程圖如附圖1所示。在三維形體檢測與轉換的過程中，通過三維數位化掃描儀對實物模型表面進行三維快速掃描測量，在滿足離散採樣速度和數據質量的前提下，獲取產品的三維離散數據，點雲孔洞的出現造成了這些數據的不完整，因此對孔洞進行補償即對數據進行預處理是逆向工程中非常關鍵的承上啟下的一環，直接影響重構成功與否和CAD模型的質量，對其後續環節起著非常關鍵的制約作用。本發明主要是涉及到在逆向工程的數位化過程中，用三維掃描系統(附圖2)獲取產品點雲模型出現孔洞時的一種自動補償方法。
近年來，點雲孔洞的填補算法在國內外均取得了很大的進展，已發表了相當數量的文獻，其中一些算法獲得了較為廣泛的應用，如基於能量優化和細分、三角網格模型、網格曲面模型中孔洞的填補算法。這些算法需先對三維掃描直接獲得的點雲模型做一定的前期處理或者對點雲孔洞進行邊界識別，實時性不強，複雜度也比較高。在實際的工程應用中，對出現的問題應能及時解決。
文獻「Minimal energy surfaces using parametric splines.」(Gregory E.Fasshauer，LarryL.Schumarker.Computer Aided Geometric Design，1996，1345～79)通過求解以「變形能量函數」為基礎的優化目標函數，實現對孔洞的填補，保證了一定的光順性，然而這類方法大多需要細分曲面，並且對多個子曲面片進行拼接，因此對曲面邊界的連續性要求較高，通常很難達到曲面間的二階連續。由於現有的三角網格模型的相關算法比較成熟，現有的算法大多都是基於此模型的，例如文獻「A study of stereolithography file errors and repair」(Leong K F，ChuaC K，Ng Y M.International Journal of Advanced Manufacturing，1996，12415～422)將孔洞填補歸結為一個空間多邊形的三角剖分問題。但大多在構造新三角片時僅僅採用原有的孔洞多邊形頂點，沒有增加新的三角片頂點，因而難以獲得較好的用於填補孔洞的三角片形狀，填補效果不夠理想。並且這類算法對於複雜的點雲數據編程建立三角網格模型運算量較大，在填補孔洞的過程中還需要改變三角網格的拓撲結構，因此具有對三角網格模型修改和再設計能力不足的缺點，複雜度高，這些缺點都限制了它在實踐中的應用。對一類多邊形孔洞的填充算法不適用於一般的點雲模型。對於一般曲面網格的填充算法均需要準確的獲得孔洞邊界信息，難度大，不易實現。通過對點雲孔洞周圍散亂點集進行曲面擬合補償孔洞的算法過程中，散亂點的參數化必不可少。通常有均勻參數化、向心參數化和累積弦長參數化方法，而這些方法主要針對呈拓撲矩形陣列的數據點，對無規則分布的點雲數據，需要對其排序，難度也比較大。
傳統的三角曲面插值算法也得到了較為廣泛的應用，同時也獲得了較好的效果。例如文獻「An Adaptive Method for Smooth Surface Approximation to Scattered 3D Points.」(Park H，KimK.ComputerAided Design，1995，27(12)929～939)中提出的構造光滑曲面擬合散亂點的自適應插值算法。這類插值算法雖然速度比較快，但有其致命的缺點，即1隻能處理單值的非封閉曲面；2要假定偏導矢在域邊界曲線上呈線性分布；3重構的曲面依賴於估算出的偏導矢，所以曲面插值方法對離散點的逼近效果並不好，並且計算量大效率低。
在實際的應用過程中，用三維掃描系統得到的通常是具有海量散亂點的點雲原始模型。此時就不可避免的存在孔洞現象，對這些孔洞進行及時的填補是關鍵。為此，本發明中使用一種新算法對孔洞進行補償。如何對散亂點參數化以及提高曲面的擬合精度是此類算法中的難點。本發明中提出的對散亂點進行參數化的方法以及對曲面的迭代逼近優化方法能達到對孔洞的光滑擬合填充。

發明內容
本發明提供一種能夠提供曲面擬合精確度的三維掃描的點雲孔洞填補方法。
本發明採用如下技術方案一種基於三角域貝塞爾曲面的三維掃描的點雲孔洞填補方法第一步在點雲孔洞周圍且在屏幕坐標平面內設定一個三角形ABC，該三角形ABC的區域範圍能使點雲孔洞及其周圍的點向屏幕坐標平面的投影落入三角形ABC內，並將投影落入三角形ABC內的點作為補孔時擬合曲面的點Ps(s＝0，1，…，m-1)，根據擬合曲面的點Ps在三角形ABC平面的投影Ps』位置計算其曲面參數化坐標(us，vs，ws)，us＝(ΔAPs』B面積)/(ΔABC面積)、vs＝(ΔAPs』C面積)/(ΔABC面積)、ws＝(ΔBPs』C面積)/(ΔABC面積)，將擬合曲面的點Ps(s＝0，1，…，m-1)的坐標及其曲面參數化坐標(us，vs，ws)代入n次Bezier曲面方程並用最小二乘法得到n次Bezier曲面的控制點，從而得到初步擬合的曲面S(u，v，w)；第二步求出各個擬合曲面的點Ps(s＝0，1，…，m-1)到曲面的距離向量d(u，v，w)及曲面分別對對應點參數方向的偏微分Su(u，v，w)，Sv(u，v，w)，Sw(u，v，w)，令f(u,v,w)=d(u,v,w)Su(u,v,w)=0g(u,v,w)=d(u,v,w)Sv(u,v,w)=0h(u,v,w)=d(u,v,w)Sw(u,v,w)=0]]>擬合曲面的點Ps的參數化坐標為(us，vs，ws)，以(us，vs，ws)為初始估計值，根據牛頓迭代法求解以上方程組，有HσT＝κT式中σ＝(δu，δv，δw)，其中，δu，δv，δw為曲面u，v，w三個方向上的迭代步長。
κ＝-(f(us，vs，ws)，g(us，vs，ws)，h(us，vs，ws))H=fufvfwgugvgwhuhvhw=||Su||2+dSuuSvSu+dSuvSwSu+dSuwSuSv+dSvu||Sv||2+dSvvSwSv+dSvwSuSw+dSwuSvSw+dSwv||Sw||2+dSww]]>式中，d＝d(us，vs，ws)；fu，fv，fw，gu，gv，gw，hu，hv，hw分別表示在點(us，vs，ws)處相應的向量對u，v，w的一階偏導數；Suu，Suv，Suw，Svv，Svu，Svw，Sww，Swu，Swv是曲面S(u，v，w)在點(us，vs，ws)處分別對u，v，w的二階偏導數。
則可得||Su||2+dSuuSvSu+dSuvSwSu+dSuwSuSv+dSvu||Sv||2+dSvvSwSv+dSvwSuSw+dSwuSvSw+dSwv||Sw||2+dSwwuvw=-f(us,vs,ws)g(us,vs,ws)h(us,vs,ws)]]>根據三角Bezier曲面的定義可知δu+δv+δw＝0，即δw＝-δu-δv，因此得到如下迭代方程組||Su||2-SwSu+d(Suu-Suw)SvSu-SwSu+d(Suv-Suw)SuSv-SwSv+d(Svu-Svw)||Sv||2-SwSv+d(Svv-Svw)SuSw-||Su||2+d(Swu-Sww)SvSw-||Sw||2+d(Swv-Sww)uv=-f(us,vs,ws)g(us,vs,ws)h(us,vs,ws)]]>其中，δu，δv為u，v兩個方向上的迭代步長。Suu，Suv，Suw，Svv，Svu，Svw，Sww，Swu，Swv是曲面S(u，v，w)在點(us，vs，ws)處分別對u，v，w的二階偏導數，迭代求解直到1/ms=0m-1||d(us+u,vs+v,ws+w)-d(us,vs,ws)||,]]>ε為預置曲面擬合精度，從而得到最終確定的三角Bezier曲面S』(u，v，w)；第三步在所述的三角Bezier曲面S』(u，v，w)上基於曲率的等參數取線，再在線上等參數取點，用於填補點雲孔洞，在求曲率的過程中首先需對三維點雲進行刪格劃分，該刪格劃分為構造一個點雲數據的最小外接正方體，其兩兩垂直的3條邊分別與笛卡兒坐標系的3個坐標軸平行，沿三個坐標軸方向劃分成邊長為L空間六面體立方刪格，其次在擬合曲面的點Ps的27個鄰近子包圍盒內求出其k個鄰近點，然後設擬合曲面的點Ps和其k個鄰近點組成集合K(Ps)，S(Ps)為擬合曲面的點Ps的k個鄰近點最小二乘擬合平面，令P為擬合曲面的點Ps的k個鄰近點集合K(Ps)的形心，稱為擬合曲面的點Ps的中心點，該中心點為P=1(k+1)PsK(Ps)Ps]]>設擬合曲面的點Ps的第j個鄰近點到最小二乘平面S(Ps)的距離為dj，到P的距離為λj，那麼對擬合曲面的點Ps的第j個點存在函數fj(Ps)，該函數fj(Ps)為fj(Ps)=djj]]>那麼擬合曲面的點Ps的曲率函數可以表示為f(Ps)=1kj=1kfj(Ps)]]>根據曲率函數f(Ps)求出，擬合曲面的點Ps的平均曲率ρs，同理求出整個點雲的平均曲率ρ0。令d為整個點雲的平均點距，則取點間隔Δω＝ρ0×d/ρs，在Bezier曲面片上取點時，首先在曲面一個參數方向上以Δω等間隔取等參數曲線，再對每一條等參數曲線在另一個參數方向上以Δω等間隔取點，求得填補孔洞的點。
本發明主要用於對三維掃描系統中各種具有複雜曲面形狀的點雲原始模型中孔洞進行填補的應用場合。利用本發明中的曲面擬合算法，即可得到一張精確逼近孔洞周圍散亂點的曲面，隨後在面上根據曲率的變化取點可以即可實現對孔洞的光滑填補。該方法主要有以下優點(1)由於傳統的曲面插值方法對離散點的逼近效果並不好，本發明採用曲面擬合的方法能得到一張精確擬合孔洞周圍散亂點集的曲面。
(2)採用基於三角域上的曲面擬合方法，比四邊域的曲面更容易表現無規則的表面，能保證一定的光順性和保形性。
(3)相比較多數算法中的網格化處理，本發明主要針對三維掃描系統得到的原始點雲模型，不需要任何的網格化處理，適用性廣，速度快。
(4)擬合曲面時，交互選取孔洞周圍的散亂點，所以當孔洞邊界形狀比較複雜時，也同樣適用。
(5)對散亂點參數化時，無需擬合孔洞的邊界曲線，由於避免了孔洞的邊界識別，因此對於絕大多數具有任意形狀的孔洞也同樣適用。
(6)由於對散亂點進行曲面擬合採用了初步擬合和迭代逼近優化兩步方法，能夠使擬合的曲面獲得更高的精度。
(7)可以根據實際需要，在曲面擬合過程中人為控制曲面的次數及擬合的精度，避免了不必要的計算冗餘。
(8)在面上取點時，考慮曲率變化，能實現對孔洞的光滑補償，一般在點雲中，點雲密度大的地方，曲率變化也比較大，因此，基於曲率的等參數取點能光滑的填補孔洞。
(9)操作過程比較簡單，只要交互選定孔洞周圍的離散點，接下來的的步驟都可自動完成，速度快。並且該方法具有很強的通用性。
此外要注意的是，選取散亂點時，儘量在孔洞周圍大範圍內選取，可以避免自適應增加散亂點數量，以進一步提高算法的效率。


圖1是逆向工程流程圖。
圖2是光柵式三維掃描系統組成圖。
圖3是算法整體流程圖。
圖4是選取圓蓋點雲中的孔洞附近的點集實例示意圖。
圖5散亂點參數化流程圖。
圖6是曲面初步擬合流程圖。。
圖7是對圓蓋點雲中的孔洞附近的點集擬合曲面實例示意圖。
圖8是是曲面迭代逼近優化流程9是對圓蓋點雲中的孔洞填補實例示意圖。
圖10是刪格化圖。
圖11是曲率函數求解圖。
圖12是面上取點填補孔洞流程圖。
具體實施例方式
一種基於三角域貝塞爾曲面的三維掃描的點雲孔洞填補方法第一步在點雲孔洞周圍且在屏幕坐標平面內設定一個三角形ABC，該三角形ABC的區域範圍能使點雲孔洞及其周圍的點向屏幕坐標平面的投影落入三角形ABC內，並將投影落入三角形ABC內的點作為補孔時擬合曲面的點Ps(s＝0，1，…，m-1)，根據擬合曲面的點Ps在三角形ABC平面的投影Ps』位置計算其曲面參數化坐標(us，vs，ws)，us＝(ΔAPs』B面積)/(ΔABC面積)、vs＝(ΔAPs』C面積)/(ΔABC面積)、ws＝(ΔBPs』C面積)/(ΔABC面積)，將擬合曲面的點Ps(s＝0，1，…，m-1)的坐標及其曲面參數化坐標(us，vs，ws)代入n次Bezier曲面方程並用最小二乘法得到n次Bezier曲面的控制點，從而得到初步擬合的曲面S(u，v，w)；第二步求出各個擬合曲面的點Ps(s＝0，1，…，m-1)到曲面的距離向量d(u，v，w)及曲面分別對對應點參數方向的偏微分Su(u，v，w)，Sv(u，v，w)，Sw(u，v，w)，令f(u,v,w)=d(u,v,w)Su(u,v,w)=0g(u,v,w)=d(u,v,w)Sv(u,v,w)=0h(u,v,w)=d(u,v,w)Sw(u,v,w)=0]]>擬合曲面的點Ps的參數化坐標為(us，vs，ws)，以(us，vs，ws)為初始估計值，根據牛頓迭代法求解以上方程組，有HσT＝κT式中σ＝(δu，δv，δw)，其中，δu，δv，δw為曲面u，v，w三個方向上的迭代步長。
κ＝-(f(us，vs，ws)，g(us，vs，ws)，h(us，vs，ws))H=fufvfwgugvgwhuhvhw=||Su||2+dSuuSvSu+dSuvSwSu+dSuwSuSv+dSvu||Sv||2+dSvvSwSv+dSvwSuSw+dSwuSvSw+dSwv||Sw||2+dSww]]>式中，d＝d(us，vs，ws)；fu，fv，fw，gu，gv，gw，hu，hv，hw分別表示在點(us，vs，ws)處相應的向量對u，v，w的一階偏導數；Suu，Suv，Suw，Svv，Svu，Svw，Sww，Swu，Swv是曲面S(u，v，w)在點(us，vs，ws)處分別對u，v，w的二階偏導數。
則可得||Su||2+dSuuSvSu+dSuvSwSu+dSuwSuSv+dSvu||Sv||2+dSvvSwSv+dSvwSuSw+dSwuSvSw+dSwv||Sw||2+dSwwuvw=-f(us,vs,ws)g(us,vs,ws)h(us,vs,ws)]]>根據三角Bezier曲面的定義可知δu+δv+δw＝0，即δw＝-δu-δv，因此得到如下迭代方程組||Su||2-SwSu+d(Suu-Suw)SvSu-SwSu+d(Suv-Suw)SuSv-SwSv+d(Svu-Svw)||Sv||2-SwSv+d(Svv-Svw)SuSw-||Su||2+d(Swu-Sww)SvSw-||Sw||2+d(Swv-Sww)uv=-f(us,vs,ws)g(us,vs,ws)h(us,vs,ws)]]>其中，δu，δv為u，v兩個方向上的迭代步長。Suu，Suv，Suw，Svv，Svu，Svw，Sww，Swu，Swv是曲面S(u，v，w)在點(us，vs，ws)處分別對u，v，w的二階偏導數，迭代求解直到1/ms=0m-1||d(us+u,vs+v,ws+w)-d(us,vs,ws)||,]]>ε為預置曲面擬合精度，從而得到最終確定的三角Bezier曲面S』(u，v，w)；
第三步在所述的三角Bezier曲面S』(u，v，w)上基於曲率的等參數取線，再在線上等參數取點，用於填補點雲孔洞，在求曲率的過程中首先需對三維點雲進行刪格劃分，該刪格劃分為構造一個點雲數據的最小外接正方體，其兩兩垂直的3條邊分別與笛卡兒坐標系的3個坐標軸平行，沿三個坐標軸方向劃分成邊長為L空間六面體立方刪格，其次在擬合曲面的點Ps的27個鄰近子包圍盒內求出其k個鄰近點，然後設擬合曲面的點Ps和其k個鄰近點組成集合K(Ps)，S(Ps)為擬合曲面的點Ps的k個鄰近點最小二乘擬合平面，令P為擬合曲面的點Ps的k個鄰近點集合K(Ps)的形心，稱為擬合曲面的點Ps的中心點，該中心點為P=1(k+1)PsK(Ps)Ps]]>設擬合曲面的點Ps的第j個鄰近點到最小二乘平面S(Ps)的距離為dj，到P的距離為λj，那麼對擬合曲面的點Ps的第j個點存在函數fj(Ps)，該函數fj(Ps)為fj(Ps)=djj]]>那麼擬合曲面的點Ps的曲率函數可以表示為f(Ps)=1kj=1kfj(Ps)]]>根據曲率函數f(Ps)求出，擬合曲面的點Ps的平均曲率ρs，同理求出整個點雲的平均曲率ρ0。令d為整個點雲的平均點距，則取點間隔Δω＝ρ0×d/ρs，在Bezier曲面片上取點時，首先在曲面一個參數方向上以Δω等間隔取等參數曲線，再對每一條等參數曲線在另一個參數方向上以Δω等間隔取點，求得填補孔洞的點。
下面參照附圖，對本發明加以詳細描述在逆向工程中，面對的是密集的點雲散亂數據。擬合曲面時，如果曲面的對象邊界和形狀極其複雜時，一般不便直接運用常規的曲面構造方法，而Bezier曲面由於其構造靈活，邊界適應性好，具有構造複雜形狀的潛力，而且其本身具有良好的性質光滑性、局部性和保形性。基於三角域曲面的擬合方法最適合表現無規則型面的物體，特別是人面，地貌等自然物體以及玩具等產品，基於四邊域參數曲面的擬合方法，通常要求數據點是有序的，這個條件比較苛刻，綜合以上，因此本發明採用三角域上的Bezier曲面對孔洞部分進行擬合填充。總體算法流程見附圖3。
本發明主要涉及以下四方面的內容1)散亂點的選定及參數化過程在圓蓋點雲孔洞屏幕二維坐標系附近選擇不共線的三點A、B、C，構成需要初步擬合的三角Bezier曲面片的三個角點，將孔洞周圍的點向這三點所構成的三角形平面投影，如果點落在三角形平面內，則認為是擬合曲面時所需的點Ps(s＝0，1，…，m-1)，見附圖4。
根據選取的點Ps在三角形ABC平面的投影位置計算其曲面參數化坐標。即如果Ps在三角形平面ABC內相對應的投影點為Ps』，那麼Ps的參數化坐標(us，vs，ws)分別為us＝area(ΔAPs』B)/area(ΔABC)、vs＝area(ΔAPs』C)/area(ΔABC)、ws＝area(ΔBPs』C)/area(ΔABC)。算法流程圖見附圖5。
2)最小二乘自適應初步擬合三角域ABC上n次Bezier曲面的表達式為
S(u,v,w)=i=0nj=0n-iBijkn(u,v,w)bijk]]>式中Bijkn(u,v,w)=n!i!j!k!uivjwk00u,v,w1,u+v+w=10i,j,kn,i+j+k=n]]>三角域上n次Bezier曲面的表達式中未知量為Ps的參數化坐標(us，vs，ws)，以及(n+1)(n+2)/2個控制頂點，(us，vs，ws)根據上步已知，所以只要求出(n+1)(n+2)/2個控制頂點坐標bijk(0≤i，j，k≤n，i+j+k＝n)，即可確定出一個三角Bezier曲面。
根據三角Bezier曲面的性質可知三角Bezier曲面的三個角點正好是其控制多面體網格的三個控制頂點，那麼所選三角形的三個頂點A、B、C即可做為三個已知控制頂點b00n，b0n0，bn00，把Ps(s＝0，1，…，m-1)的坐標代入三角Bezier曲面方程，構成以(n+1)(n+2)/2-3個未知控制頂點為未知量的m個線性方程組。在所選三角形內部的三維坐標點數m一般大於(n+1)(n+2)/2-3，在不滿足此條件即待求方程組係數矩陣奇異時，以三角形ABC的重心為基點，自適應擴大三角形ABC的面積來增加m的個數。最後採用最小二乘法求解此過約束方程組，確定出曲面其它的未知控制頂點，得到初步擬合的曲面S(u，v，w)。算法流程圖見附圖6。
3)曲面逼近優化經過最小二乘初步擬合後，散亂點集Ps與曲面S(u，v，w)的距離誤差還比較大，因此需要進一步修正控制頂點，改變控制多面體的形狀，從而改變曲面的形狀，使曲面逼近點集。本發明採用了以牛頓迭代法為基礎的迭代逼近算法，提高擬合精度，最終確定出曲面S』(u，v，w)，見附圖7。
具體步驟如下(1)求出各個散亂點到曲面的距離向量d(u，v，w)及曲面分別對對應點參數方向的偏微分Su(u，v，w)，Sv(u，v，w)，Sw(u，v，w)，組成待求方程組如下f(u,v,w)=d(u,v,w)Su(u,v,w)=0g(u,v,w)=d(u,v,w)Sv(u,v,w)=0h(u,v,w)=d(u,v,w)Sw(u,v,w)=0]]>(2)採用基於牛頓迭代法的方法求解此方程組，最終可求得的迭代方程組為||Su||2-SwSu+d(Suu-Suw)SvSu-SwSu+d(Suv-Suw)SuSv-SwSv+d(Svu-Svw)||Sv||2-SwSv+d(Svv-Svw)SuSw-||Sw||2+d(Swu-Sww)SvSw-||Sw||2+d(Swv-Sww)uv=-f(us,vs,ws)g(us,vs,ws)h(us,vs,ws)]]>(3)迭代求解以上方程組，當擬合曲面的點數少於迭代方程組的未知數個數時，及方程組係數奇異時，同樣以三角形ABC的重心為基點，自適應擴大三角ABC的面積來增加m的個數，重複(2)。
算法流程圖見附圖8。
4)面上取點在所述的三角Bezier曲面S』(u，v，w)上基於曲率的等參數取線，再在線上等參數取點，用於填補點雲孔洞，見附圖9。在求曲率的過程中首先需對三維點雲進行刪格劃分，該刪格劃分為構造一個點雲數據的最小外接正方體，其兩兩垂直的3條邊分別與笛卡兒坐標系的3個坐標軸平行，沿三個坐標軸方向劃分成邊長為L空間六面體立方刪格，見附圖10，其次在擬合曲面的點Ps的27個鄰近子包圍盒內求出其k個鄰近點，然後設擬合曲面的點Ps和其k個鄰近點組成集合K(Ps)，S(Ps)為擬合曲面的點Ps的k個鄰近點最小二乘擬合平面，令P為擬合曲面的點Ps的k個鄰近點集合K(Ps)的形心，稱為擬合曲面的點Ps的中心點，該中心點為P=1(k+1)PsK(Ps)Ps]]>設擬合曲面的點Ps的第j個鄰近點到最小二乘平面S(Ps)的距離為dj，到P的距離為λj，見附圖11，那麼對擬合曲面的點Ps的第j個點存在函數fj(Ps)，該函數fj(Ps)為fj(Ps)=djj]]>那麼擬合曲面的點Ps的曲率函數可以表示為f(Ps)=1kj=1kfj(Ps)]]>根據曲率函數f(Ps)求出，擬合曲面的點Ps的平均曲率ρs，同理求出整個點雲的平均曲率ρ0。令d為整個點雲的平均點距，則取點間隔Δω＝ρ0×d/ρs，在Bezier曲面片上取點時，首先在曲面一個參數方向上以Δω等間隔取等參數曲線，再對每一條等參數曲線在另一個參數方向上以Δω等間隔取點，求得填補孔洞的點。
算法流程圖見附圖12。
權利要求
1.一種三維掃描的點雲孔洞填補方法，其特徵在於第一步在點雲孔洞周圍且在屏幕坐標平面內設定一個三角形ABC，該三角形ABC的區域範圍能使點雲孔洞及其周圍的點向屏幕坐標平面的投影落入三角形ABC內，並將投影落入三角形ABC內的點作為補孔時擬合曲面的點Ps(s＝0，1，…，m-1)，根據擬合曲面的點Ps在三角形ABC平面的投影Ps』位置計算其曲面參數化坐標(us，vs，ws)，us＝(ΔAPs』B面積)/(ΔABC面積)、vs＝(ΔAPs』C面積)/(ΔABC面積)、ws＝(ΔBPs』C面積)/(ΔABC面積)，將擬合曲面的點Ps(s＝0，1，…，m-1)的坐標及其曲面參數化坐標(us，vs，ws)代入n次Bezier曲面方程並用最小二乘法得到n次Bezier曲面的控制點，從而得到初步擬合的曲面S(u，v，w)；第二步求出各個擬合曲面的點Ps(s＝0，1，…，m-1)到曲面的距離向量d(u，v，w)及曲面分別對對應點參數方向的偏微分Su(u，v，w)，Sv(u，v，w)，Sw(u，v，w)，令f(u,v,w)=d(u,v,w)Su(u,v,w)=0g(u,v,w)=d(u,v,w)Sv(u,v,w)=0h(u,v,w)=d(u,v,w)Sw(u,v,w)=0]]>根據牛頓迭代法，得到如下迭代方程組||Su||2-SwSu+d(Suu-Suw)SvSu-SwSu+d(Suv-Suw)SuSv-SwSv+d(Svu-Suw)||Sv||2-SwSv+d(Svv-Svw)SuSw-||Sw||2+d(Swu-Sww)SvSw-||Sw||2+d(Swv-Sww)uv=-f(us,vs,ws)g(us,vs,ws)h(us,vs,ws)]]>其中，δu，δv為u，v兩個方向上的迭代步長，Suu，Suv，Suw，Svv，Svu，Svw，Sww，Swu，Swv是曲面S(u，v，w)在點(us，vs，ws)處分別對u，v，w的二階偏導數，迭代求解直到1/ms=0m-1||d(us+u,vs+v,ws+w)-d(us,vs,ws)||,]]>ε為預置曲面擬合精度，從而得到最終確定的三角Bezier曲面S』(u，v，w)；第三步在所述的三角Bezier曲面S』(u，v，w)上基於曲率的等參數取線，再在線上等參數取點，用於填補點雲孔洞，在求曲率的過程中首先需對三維點雲進行刪格劃分，該刪格劃分為構造一個點雲數據的最小外接正方體，其兩兩垂直的3條邊分別與笛卡兒坐標系的3個坐標軸平行，沿三個坐標軸方向劃分成邊長為L空間六面體立方刪格，其次在擬合曲面的點Ps的27個鄰近子包圍盒內求出其k個鄰近點，然後設擬合曲面的點Ps和其k個鄰近點組成集合K(Ps)，S(Ps)為擬合曲面的點Ps的k個鄰近點最小二乘擬合平面，令P為擬合曲面的點Ps的k個鄰近點集合K(Ps)的形心，稱為擬合曲面的點Ps的中心點，該中心點為P=1(k+1)PsK(Ps)Ps]]>設擬合曲面的點Ps的第j個鄰近點到最小二乘平面S(Ps)的距離為dj，到P的距離為λj，那麼對擬合曲面的點Ps的第j個點存在函數fj(Ps)，該函數fj(Ps)為fj(Ps)=djj]]>那麼擬合曲面的點Ps的曲率函數可以表示為f(Ps)=1kj=1kfj(Ps)]]>根據曲率函數f(Ps)求出，擬合曲面的點Ps的平均曲率 同理求出整個點雲的平均曲率 令d為整個點雲的平均點距，則取點間隔=0d/s,]]>在Bezier曲面片上取點時，首先在曲面一個參數方向上以Δω等間隔取等參數曲線，再對每一條等參數曲線在另一個參數方向上以Δω等間隔取點，求得填補孔洞的點。
2.根據權利要求1所述的三維掃描的點雲孔洞填補方法，其特徵在於擬合曲面的點數少於曲面控制頂點數時，擴大所設定三角形ABC的面積，使擬合曲面的點數大於曲面控制頂點數。
3.根據權利要求1所述的三維掃描的點雲孔洞填補方法，其特徵在於擬合曲面的點數少於迭代方程組的未知數個數時，擴大所設定三角形ABC的面積，使擬合曲面的點數大於或等於迭代方程組的未知數個數。
全文摘要
本發明公開了一種能夠提供曲面擬合精確度的三維掃描的點雲孔洞填補方法。在點雲孔洞周圍選擇作為初步擬合曲面時需要的坐標點P
文檔編號G06T17/00GK1885349SQ20061008824
公開日2006年12月27日 申請日期2006年7月5日 優先權日2006年7月5日
發明者達飛鵬, 朱春紅 申請人:東南大學