貪婪投影算法理解

2022-12-19 18:26 作者:生醫(yī)小王子 0人讀過 | 我要投稿

一、概述

貪婪投影算法（Greedy Projection Algorithm）是M. Gopi等人[1]于2003年提出的點(diǎn)云表面重建算法。該算法從一個(gè)數(shù)據(jù)點(diǎn)R開始，找到與R相鄰的一組數(shù)據(jù)點(diǎn) $C_R$ ，連接R與 $C_R$ ，就可得到數(shù)據(jù)點(diǎn)R的所有鄰接三角形（頂點(diǎn)中包含R的三角形）。然后以廣度優(yōu)先搜索的形式，遍歷 $C_R$ 中的數(shù)據(jù)點(diǎn)，找到這些數(shù)據(jù)點(diǎn)的鄰接三角形，直到遍歷完所有數(shù)據(jù)點(diǎn)。該算法的重點(diǎn)在于如何連接數(shù)據(jù)點(diǎn)R和 $C_R$ 以生成高質(zhì)量三角形（避免小角度），并保證三角形不會(huì)交疊。算法通過投影的方式，將三維數(shù)據(jù)點(diǎn)投影至二維，在二維平面內(nèi)連接數(shù)據(jù)點(diǎn)，以獲取不交疊三角形；通過貪婪的方式，當(dāng)有多個(gè)數(shù)據(jù)點(diǎn)可連成三角形時(shí)，盡可能生成角度大的三角形。

二、算法流程

1 獲取數(shù)據(jù)點(diǎn)R的相鄰點(diǎn)集 $C_R$

論文通過以下2個(gè)步驟確定相鄰點(diǎn)集。首先以R為中心，長(zhǎng)為 $2*%5Cmu*m$ 的正方體初步篩選相鄰數(shù)據(jù)點(diǎn)。其中 $%5Cmu$ 為用戶定義的常量，表示相鄰區(qū)域的范圍；m為R與最近點(diǎn)的距離。然后計(jì)算數(shù)據(jù)點(diǎn)到R的距離，準(zhǔn)確篩選出半徑 $%5Cmu*m$ 以內(nèi)的數(shù)據(jù)點(diǎn) $C_R$ 。

而在PCL中，是通過設(shè)置常量 $%5Cmu$ (mu_)，搜索半徑(search_radius_)，最大搜索數(shù)目(nnn_)來確定相鄰數(shù)據(jù)點(diǎn)。首先搜索最近的nnn_個(gè)數(shù)據(jù)點(diǎn)，然后選出距離小于 $%5Cmu*m$ 和search_radius_的數(shù)據(jù)點(diǎn)作為 $C_R$ 。

2 投影R和 $C_R$ 至二維平面

對(duì)于一個(gè)光滑表面，當(dāng)數(shù)據(jù)點(diǎn)R所在的局部區(qū)域無限小時(shí)，該區(qū)域接近于曲面在數(shù)據(jù)點(diǎn)R處的切平面，因此在這局部區(qū)域三維數(shù)據(jù)點(diǎn)連線問題可以簡(jiǎn)化至二維平面。我們可以沿著數(shù)據(jù)點(diǎn)R的法向量進(jìn)行投影，R的投影R_為投影平面的坐標(biāo)原點(diǎn)， $C_R$ 的投影結(jié)果定義為 $C_R%5Ep$ 。

3 按角度排序 $C_R%5Ep$

投影點(diǎn) $C_R%5Ep$ 與坐標(biāo)原點(diǎn)R_可連成向量，根據(jù)這些向量到X軸的角度排序 $C_R%5Ep$ 。按照該排序依次連接 $C_R%5Ep$ 中的數(shù)據(jù)點(diǎn)就可以形成不交疊的三角形。但是 $C_R%5Ep$ 中可能有部分點(diǎn)已經(jīng)生成過三角形，增加的三角形可能與原有三角形交疊，所以要?jiǎng)h除部分?jǐn)?shù)據(jù)點(diǎn)以避免與原三角形交疊。另外，當(dāng)有多個(gè)數(shù)據(jù)點(diǎn)可以連接時(shí)，如何形成最優(yōu)三角形也需要探討。

4 根據(jù)可見度刪除數(shù)據(jù)點(diǎn)(Pruning by Visibility)

論文通過以下3個(gè)步驟刪除 $C_R%5Ep$ 中會(huì)產(chǎn)生交疊三角形的數(shù)據(jù)點(diǎn)（如圖1中R與數(shù)據(jù)點(diǎn)V的連線會(huì)與已有三角形相交，應(yīng)刪除數(shù)據(jù)點(diǎn)V）。

邊界邊：僅與單個(gè)三角形連接的邊。

（1）刪除數(shù)據(jù)點(diǎn)R的邊界邊之間的數(shù)據(jù)點(diǎn)。定義數(shù)據(jù)點(diǎn)R的邊界邊之間區(qū)域?yàn)镽的不可見區(qū)域，如圖1黑色點(diǎn)，當(dāng)R與這些黑色點(diǎn)相連時(shí)會(huì)與現(xiàn)有三角形交疊，所以應(yīng)刪除這些黑色點(diǎn)。

（2）若數(shù)據(jù)點(diǎn)的不可見區(qū)域中包括R，這些數(shù)據(jù)點(diǎn)也應(yīng)刪除。如圖1紅色的V點(diǎn)，R點(diǎn)在V點(diǎn)邊界邊之間。

（3）刪除會(huì)被已有網(wǎng)格阻擋的數(shù)據(jù)點(diǎn)（主要探討沒有連線的自由點(diǎn)），如圖1白色點(diǎn)W。該過程要求遍歷所有邊，以判斷這些邊是否與線段R-W相交。論文推導(dǎo)了一個(gè)定理來簡(jiǎn)化這一判斷過程：只需判斷 $C_R$ 中數(shù)據(jù)點(diǎn)的邊界邊是否與線段R-W相交即可，而不用遍歷所有邊。

圖1? 根據(jù)可見度刪除數(shù)據(jù)點(diǎn)；（a）R為當(dāng)前點(diǎn)，SR為R的鄰域搜索范圍；黑色、紅色、白色點(diǎn)為應(yīng)刪除點(diǎn)；綠色為保留點(diǎn)；（b）數(shù)據(jù)點(diǎn)連接結(jié)果 [1]

5 根據(jù)角度刪除數(shù)據(jù)點(diǎn)（Pruning by Angle Criterion）

根據(jù)可見度刪除數(shù)據(jù)點(diǎn)后，依次連接相鄰點(diǎn)就可形成不交疊的三角形，如圖3（a）依次連接 $P$ ， $N_1$ ， $N_2$ ， $N_3$ ， $N_4$ ， $N_5$ 。但是這樣很容易形成 $%5Ctriangle%20RN_1N_2$ 這樣的小角度三角形。最好的方式是直接連接 $P$ 和 $N_5$ 形成大角度三角形 $%5Ctriangle%20RPN_5$ ，但這樣點(diǎn) $N_3$ 和 $N_4$ 就在三角形內(nèi)部了，這是不允許的。為此論文提出了如下方法來尋找所有可與線段RP連成三角形的數(shù)據(jù)點(diǎn)。其中，按到R的距離從小到大排列相鄰點(diǎn)， $P_S%3D(N_1%2CN_2%2CN_5%2CN_4%2CN_3)$ ；按角度排列相鄰點(diǎn) $R_S%3D(N_1%2CN_2%2CN_3%2CN_4%2CN_5)$ 。

使用圖2偽代碼后， $N_1$ ， $N_2$ ， $N_3$ 可與線段RP連成三角形，根據(jù)貪婪算法要求，連接P和 $N_3$ 形成最大角度。隨后尋找可與線段 $RN_3$ 連成三角形的數(shù)據(jù)點(diǎn)，僅有 $N_4$ 符合要求，故連接 $N_3$ 和 $N_4$ 。

圖2? 尋找所有可與線段RP連成三角形的數(shù)據(jù)點(diǎn)（形成的三角形中不包含其他點(diǎn)）[1]

圖3? 中心點(diǎn)R和其相鄰點(diǎn)；（a）從P點(diǎn)開始連接三角形，其中∠N1RN2，∠N3RN4，∠N4RN5為小角度角；（b）△RPN4中包含N3，△RN3N5中包含N4[1]

6 三角化

依次連接剩下的數(shù)據(jù)點(diǎn)就可連成三角形。若相鄰數(shù)據(jù)點(diǎn)的角度過大（如大于120°），則不連成三角形，算法認(rèn)為這是模型的孔洞。

三、參考文獻(xiàn)

[1] M. Gopi, S. Krishnan. A Fast and Efficient Projection Based Approach for Surface Reconstruction. Brazilian Symposium on Computer Graphics & Image Processing. 2003, 179-186

標(biāo)簽：