[發明專利]一種基于射線原理的帶邊界保留的云數據精簡算法

有效

• 申請號: 201410360076.5
• 申請日: 2014-07-24
• 公開（公告）號: CN104361625B
• 公開（公告）日: 2017-12-22
• 發明（設計）人: 王美麗;廖昌粟;張宏鳴;胡少軍;何東健;牛曉靜
• 申請（專利權）人: 西北農林科技大學
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及數據處理領域，尤其涉及一種基于射線原理的帶邊界保留的云數據精簡算法。

背景技術

近年來，隨著三維掃描儀成本的降低以及精度的提高，三維點云數據已經成為圖形學、逆向工程和工業領域中一種重要的數據表現形式。然而原始采集的三維點云數據量非常大，這對后期的三維重建帶來很大的困難，因此三維點云的去噪和簡化工作是點云處理中至關重要的一個環節。

目前三維點云數據精簡的算法有基于聚類的簡化、基于曲率的簡化等，這些方法雖然能夠在一定程度上精簡點云數量，保留點云模型的特征，提高模型的重建效果，但是由于大多需要進行遞歸操作或者曲率估算，所以對于點云數據量較大的模型，此類算法顯得非常耗時。

鑒于上述缺陷，本發明創作者經過長時間的研究和實踐終于獲得了本創作。

發明內容

本發明的目的在于提供一種基于射線原理的帶邊界保留的云數據精簡算法，用以克服上述技術缺陷。

為實現上述目的，本發明提供一種基于射線原理的帶邊界保留的云數據精簡算法，該具體過程為：

步驟a，輸入點云數據，建立k-d樹以形成散亂點云之間的拓撲關系；

步驟b，利用點云數據生成包圍三維點云模型的立方體V_m，并將該立方體依據點云模型的中心點分為8個子立方體V_i(i＝0，1，...，7)，將所有的數據點依據其空間所在位置進行歸類，歸入各自的子立方體中；

步驟c，依據點云模型子立方體，將立方體V_m的每一個面分為4個子平面，根據上述步驟b中的射線生成方法生成射線；

步驟d，利用公式計算出子立方體V_i(i＝0，1，...，7))中每個數據點到通過該立方體的每條射線之間的距離d_i(i＝0，1，...，Max)，并由數據點到中心點Mid之間的距離得出每個數據點相應的判斷閾值dis_i(i＝0，1，...，Max)，若d_i＜dis_i，則視為數據點需要被精簡。

進一步，設定閾值Num，表示當檢測到某數據點為非邊界點時，其鄰近點中無需判斷便被視為非邊界點的點云數量，閾值Num可隨三維點云模型的數據量增大而增大，通過對比例系數e和閾值Num的結合控制。

進一步，在上述步驟b中，

根據兩點確定一條直線的原理，以三維點云模型的中心點作為所有射線的公共點，則只需要按一定規則生成射線另一點的坐標，就可以生成所有的射線；

步驟b1，生成一個最小的能夠包圍點云模型的立方體V_m，設該立方體的邊長為L，散亂點云在X、Y、Z軸方向的最大值和最小值分別為：X_max、Y_max、Z_max、X_min、Y_min、Z_min，則立方體邊長的計算方法如下：

L＝Max((X_max-X_min)，(Y_max-Y_min)，(Z_max-Z_min)) (1)

L為邊長，(X_min，Y_min，Z_min)為一頂點，作立方體，并使其能夠完全包圍點云模型；

步驟b2，在立方體的6個平面上生成所需要的點，以某一與xoy面平行的平面為例，設該平面分別平行于X軸和Y軸的兩邊為L1、L2，并且已知兩邊的端點分別為P1(x₁，y₁，z₁)、P2(x₂，y₂，z₂)和P2、P3(x₃，y₃，z₃)。

進一步，在上述步驟b2中，設閾值d，假設生成的點為P_i(x_i，y_i，z_i)，則生成點坐標計算方法如下：

x_i＝(i/d)×(x₁-x₂)+x₂ (i＝0，1，2，...，d-1，d) (2)