[發(fā)明專利]一種大規(guī)模稠密點云法線的確定方法

有效

• 申請?zhí)枺?/td>: 201810111004.5
• 申請日: 2018-02-05
• 公開（公告）號: CN109325953B
• 公開（公告）日: 2021-09-21
• 發(fā)明（設(shè)計）人: 孟祥林;何萬濤;程俊廷;郭延艷;霍濱焱;車向前;趙燦;周波
• 申請（專利權(quán)）人: 黑龍江科技大學(xué)
• 主分類號: G06T7/11
• 分類號: G06T7/11;G06T3/40;G06K9/62
• 代理公司: 深圳市智科友專利商標事務(wù)所 44241
• 代理人: 曲家彬

1.一種大規(guī)模稠密點云法線的確定方法，該方法基于法線的雙線性插值算法，通過對稠密點云進行空間分割，構(gòu)造插值節(jié)點，確定插值節(jié)點計算法線及為點云數(shù)據(jù)法線的插值計算處理，得到所有稠密點云數(shù)據(jù)的法線，其特征在于：該方法由以下步驟實現(xiàn)：

步驟1.給定點云數(shù)據(jù)S＝{X_t＝(x_t,y_t,z_t)∈R³|t＝1,…,N}，遍歷點云數(shù)據(jù)獲得點云數(shù)據(jù)在X、Y和Z方向上的最大坐標值和最小坐標值x_max、x_min、y_max、y_min、z_max、z_min；

根據(jù)總點數(shù)N利用公式(1)計算分割點云立方體邊長L；

步驟2.利用公式(2)計算立方體在X、Y和Z方向上的總數(shù)量index_i、index_j和index_k；

步驟3.根據(jù)給定序號(i,j,k)對全部立方體按公式(3)進行編號；

key＝index_i×index_j×k+index_i×j+i (3)

步驟4.根據(jù)任意給定點云X_t的坐標(x_t,y_t,z_t)，按公式(4)將該點云分割到相應(yīng)的立方體內(nèi)，由于立方體與整體點云相比很小，設(shè)定為單個立方體內(nèi)的點法向量為線性變化的；

步驟5.根據(jù)立方體編號(i,j,k)和邊長L計算所有立方體最小坐標值的頂點p的坐標值(x_p,y_p,z_p)，搜索與頂點p鄰近的8個立方體內(nèi)的所有點作為頂點p的鄰域；

表達式為：Q＝{X_t＝(x_t,y_t,z_t)∈R³|t＝1,…,M}；

其中：M為鄰域內(nèi)點的數(shù)量；

X_t為鄰域的任意點，(x_t,y_t,z_t)為X_t點的坐標值；

Q為鄰域點集；

頂點p的坐標值計算公式(5)；

步驟6.根據(jù)主成分分析算法，利用點集Q構(gòu)造協(xié)方差矩陣CV，對CV進行奇異值分解獲得特征值λ₁≥λ₂≥λ₃及對應(yīng)的特征向量v₁,v₂,v₃，取最小特征值對應(yīng)的特征向量v₃并單位化，即可獲得p點處的法線n＝(n_x,n_y,n_z)，其中：

步驟7.將點集Q擬合為通過點集中心點X_c并以n為法線的平面π，X_c的坐標值(x_c,y_c,z_c)的計算如下；

步驟8.將點p沿著n的方向投影到平面π上，得到投影點p₁的坐標值(x,y,z)，則p到p₁的向量與n成比例，令這個比例為r，則有：

步驟9、由于點p₁在平面π上，根據(jù)平面的點法式方程有：

n_x(x-x_c)+n_y(y-y_c)+n_z(z-z_c)＝0 (9)

步驟10.將方程(8)和(9)聯(lián)立，解得比例r：

步驟11.根據(jù)式(6)，r可寫為：

r＝n_x(x_c-x_p)+n_y(y_c-y_p)+n_z(z_c-z_p) (11)

步驟12.根據(jù)方程(8)和(11)得到p₁點坐標：

步驟13.由于點p不在平面上，點p₁距離p最短，因此令曲面在p₁處的法線n₁＝(n_x1,n_y1,n_z1)等于p的法線n；

步驟14.比較p₁對應(yīng)的法線n₁的X、Y和Z方向分量；比較結(jié)果|n_z1|為最大值時，則該分量為Z分量，則搜索當前立方體及其后面鄰近的8個立方體并沿Z方向投影投影至XOY平面，將投影重疊的立方體兩兩一組分為4組，搜索立方體[1,5],[2,6],[3,7],[4,8]得到投影點p₁和距離p₁最近的3個立方體最小坐標值頂點的投影點p₂、p₃、p₄以及p₁所在XOY平面的投影坐標p’₁＝(x₁,y₁)、p’₂＝(x₂,y₂)、p’₃＝(x₃,y₃)、p’₄＝(x₄,y₄)，令p₁、p₂、p₃、p₄點對應(yīng)的法線為n₁、n₂、n₃、n₄，若鄰近的投影點少于3個，則缺少點的投影坐標以(0,0)代替，比較結(jié)果|n_x1|或|n_y1|為最大值時，則該分量分別為X或Y分量，則搜索當前立方體及其后面鄰近的8個立方體并分別沿X或Y方向投影投影至ZOY或ZOX平面，將投影重疊的立方體兩兩一組分為4組，搜索立方體順序分別為[1,2],[3,4],[5,6],[7,8]或[1,3],[2,4],[5,7],[6,8]，采用|n_z1|為最大值時的處理方法，分別得p₁、p₂、p₃、p₄點在ZOY或ZOX平面的投影坐標；

其中：[1,5]表示為序號為1和5的立方體；

[2,6]表示為序號為2和6的立方體；,

[3,7]表示為序號為3和7的立方體；

[4,8]表示為序號為4和8的立方體；

[1,2]表示為序號為1和2的立方體；

[3,4]表示為序號為3和4的立方體；

[5,6]表示為序號為5和6的立方體；

[7,8]表示為序號為7和8的立方體；

[1,3]表示為序號為1和3的立方體；

[2,4]表示為序號為2和4的立方體；

[5,7]表示為序號為5和7的立方體；

[6,8]表示為序號為6和8的立方體；

步驟15.給定p₁點所在立方體內(nèi)的任意一點p_t＝(x_t,y_t,z_t)，其對應(yīng)的投影點坐標為p’_t＝(x_t,y_t)，根據(jù)步驟4中的假設(shè)，p_t點的法線n_t可由雙線性插值獲得，由投影關(guān)系可知該雙線性插值過程可在投影點p’₁、p’₂、p’₃、p’₄以及p’_t之間展開；

步驟16.設(shè)p₁在平面π上任意點云為p_t，根據(jù)p’₁、p’₂、p’₃、p’₄及p_t點坐標值x_t利用線性插值計算p_a和p_b坐標：

步驟17.調(diào)整參與插值的法向量，如果n₁·n₂0，則令n₂＝-n₂，當法線n₁、n₂、n₃、n₄方向一致后，利用線性插值計算p_a和p_b的法向量n_a和n_b：

步驟18.根據(jù)p_t點坐標y_t、p_a和p_b及法向量n_a和n_b利用線性插值計算出任意點云p_t投影點p’_t＝(x_t,y_t)處的法線n_t，計算公式(15)求p_t點的法線n_t：

步驟19.遍歷立方體內(nèi)的所有點，重復(fù)步驟16至步驟19，得到立方體內(nèi)所有點的法向量；

步驟20.遍歷所有立方體，重復(fù)步驟14～步驟19，得到所有點云的法線。