散文網(wǎng) » 科技 »學(xué)習(xí) » alpha shape算法原理和PCL實(shí)現(xiàn)

alpha shape算法原理和PCL實(shí)現(xiàn)

2022-07-31 14:56 作者:生醫(yī)小王子 0人讀過(guò) | 我要投稿

一、alpha shape概述

PCL庫(kù)在ConcaveHull類(lèi)中實(shí)現(xiàn)了alpha-shape算法（凹包），以將點(diǎn)云重建為三角形網(wǎng)絡(luò)。本文主要介紹2D和3D alpha-shape算法的原理以及PCL庫(kù)算法實(shí)現(xiàn)流程。

凹包可以定義為點(diǎn)云所占距的區(qū)域，而alpha-shape算法通過(guò)創(chuàng)建一個(gè)多邊形外殼（alpha shape）來(lái)近似估計(jì)這一區(qū)域。該多邊形的頂點(diǎn)即為點(diǎn)云數(shù)據(jù)點(diǎn)，多邊形的精細(xì)程度由一個(gè)常數(shù)α決定，α越大，多邊形越接近凸包；α越小，多邊形越接近于點(diǎn)云。

二、alpha shape算法常規(guī)流程

1. 2D alpha-shape算法

2D alpha-shape算法的基本思想是將一個(gè)半徑為α的圓圍繞給定的離散點(diǎn)集S滾動(dòng)，如圖3所示。當(dāng)α取值適當(dāng)，這個(gè)圓就不會(huì)滾到S的內(nèi)部，與圓相交的點(diǎn)就是S的邊緣輪廓點(diǎn)，其滾動(dòng)的痕跡就是S的邊界線。可以通過(guò)如下準(zhǔn)則確定邊界線：在點(diǎn)集S內(nèi)任取兩個(gè)點(diǎn) $p_%7B1%7D%20$ 和 $p_%7B2%7D%20$ ，過(guò)這兩點(diǎn)繪制半徑為α的圓，若圓內(nèi)沒(méi)有其他點(diǎn)，則可以認(rèn)為 $p_%7B1%7D%20$ $p_%7B2%7D%20$ 是邊界線[3]。注意，當(dāng)點(diǎn) $p_%7B1%7D%20$ 和 $p_%7B2%7D%20$ 的距離小于2α?xí)r，會(huì)有2個(gè)圓通過(guò)這兩個(gè)點(diǎn)，只要有一個(gè)圓中沒(méi)有其他點(diǎn)， $p_%7B1%7D%20$ $p_%7B2%7D%20$ 就是邊界線，因?yàn)檫吔缇€外面是空白的，在外面的圓中不會(huì)包含其他點(diǎn)。

1.1 暴力算法[5]

（1）遍歷每條邊 $p_%7B1%7D%20$ $p_%7B2%7D%20$

（2）如果邊 $p_%7B1%7D%20$ $p_%7B2%7D%20$ 的長(zhǎng)度大于直徑2α，則跳過(guò)（無(wú)法找到這兩個(gè)點(diǎn)的圓）

（3）求出兩個(gè)圓的圓心 $C_%7B1%7D$ 和 $C_%7B2%7D$

（4）計(jì)算其他點(diǎn)到 $C_%7B1%7D$ 和 $C_%7B2%7D$ 的距離，若存在圓不包含點(diǎn)集S中的其他點(diǎn)，則邊 $p_%7B1%7D%20$ $p_%7B2%7D%20$ 為邊界

1.2 改進(jìn)算法[5]

為減少計(jì)算量，先建立三角網(wǎng)，再?gòu)娜蔷W(wǎng)的外邊界開(kāi)始判斷

（1）根據(jù)點(diǎn)集S建立Delaunay三角網(wǎng)

（2）若三角形中某條邊的長(zhǎng)度大于2α，則刪除該三角形

（3）對(duì)三角網(wǎng)每條邊進(jìn)行判斷：若過(guò)某條邊的兩點(diǎn)且半徑為α的圓包含其他點(diǎn)，則刪除該三角形

（4）求出剩余三角網(wǎng)的邊緣，該邊緣即為點(diǎn)集S的邊緣線

圖4? 不滿(mǎn)足alpha-shape要求的三角形；要判斷的三角形為△ABC，要判斷的邊為AB，因?yàn)榘霃綖棣燎疫^(guò)AB兩點(diǎn)的圓包含點(diǎn)C，從三角網(wǎng)中刪除△ABC[5]

2. 3D alpha shape算法[6]

3D alpha-shape算法與2D算法相似，以一個(gè)半徑為α的小球在點(diǎn)集上滾動(dòng)，與小球相交的3個(gè)點(diǎn)所構(gòu)成的三角形為點(diǎn)集邊界面。3D alpha-shape算法的輸入為n×3的三維空間點(diǎn)集S矩陣，每一行的三維向量代表空間中的一個(gè)點(diǎn)。輸出為m×3的邊界三角形序號(hào)集合矩陣M，其中m代表邊界三角形數(shù)目，每一行的三維向量代表三角形的3個(gè)頂點(diǎn)序號(hào)。

（1）從點(diǎn)集S中任意選擇一點(diǎn) $p_%7B1%7D%20$ ，將與之距離小于等于2α的點(diǎn)組成新的點(diǎn)集 $S_%7B1%7D%0A$ ，從 $S_%7B1%7D%0A$ 中任意選取一組點(diǎn) $p_%7B2%7Dp_%7B3%7D%0A%0A$ ，求出過(guò)點(diǎn) $p_%7B1%7D%20$ $p_%7B2%7Dp_%7B3%7D%0A%0A$ 且半徑為α的球的球心 $C_%7B1%7D$ 和 $C_%7B2%7D$

（2）遍歷點(diǎn)集 $S_%7B1%7D%0A$ ，依次求出其他點(diǎn)到球心 $C_%7B1%7D$ 和 $C_%7B2%7D$ 的距離d和d'。如果d和d'中有1個(gè)集合的距離均大于等于半徑α，則可以判斷不是邊緣輪廓點(diǎn)，停止遍歷，轉(zhuǎn)到第3步

（3）選擇 $S_%7B1%7D%0A$ 中的下一組點(diǎn)按步驟1,2進(jìn)行判斷，直到 $S_%7B1%7D%0A$ 中的全部點(diǎn)判斷結(jié)束

（4）選擇S中下一個(gè)點(diǎn)按步驟1~3進(jìn)行判斷，直到S中的全部點(diǎn)判斷結(jié)束，輸出邊界三角形矩陣M

三、PCL算法實(shí)現(xiàn)

1. 前提知識(shí)

（1）Lifting Map算法[2]

Lifting Map是一種計(jì)算點(diǎn)云Delaunay三角網(wǎng)的方法。該算法將3維點(diǎn)云映射至4維空間。計(jì)算4維空間點(diǎn)云的凸包，將該凸包下邊界映射回3維空間即可得到點(diǎn)集的Delaunay三角網(wǎng)。

（2）Alpha Complexes[2]

Alpha Complexes是指alpha shape外殼內(nèi)的單純形復(fù)合體，且Alpha Complexes是點(diǎn)云Delaunay三角網(wǎng)的子集，Alpha Complexes可以簡(jiǎn)單理解為點(diǎn)云內(nèi)數(shù)據(jù)點(diǎn)相連而形成的內(nèi)部結(jié)構(gòu)。單純形是二維的三角形，三維的四面體，可在任意維度推廣，n維單純形是一個(gè)有n+1個(gè)頂點(diǎn)，n+1個(gè)面的多面體，即這些頂點(diǎn)的凸包。當(dāng) $%CE%B4_%7B%CF%84%7D%0A$ 為Delaunay三角網(wǎng)中的單純形，且 $%CE%B4_%7B%CF%84%7D%0A$ 的外接球/圓的半徑小于α，則 $%CE%B4_%7B%CF%84%7D%0A$ 屬于Alpha Complexes，即 $%CE%B4_%7B%CF%84%7D%0A$ 在alpha shape的內(nèi)部。

2. alpha-shape算法的PCL實(shí)現(xiàn)

PCL實(shí)現(xiàn)的大致流程為：使用Lifting Map算法計(jì)算點(diǎn)云的Delaunay三角網(wǎng)；確定Alpha Complexes，計(jì)算Delaunay三角網(wǎng)中的四面體/三角形的外接球/圓半徑r，保留r<α的四面體/三角形；確定alpha shape，遍歷Alpha Complexes中所有單純形（四面體/三角形）的嶺（三角形/邊），若他們相鄰的嶺中有不屬于Alpha Complexes的，則為邊界單純形。

算法流程如下：

（1）點(diǎn)云預(yù)處理。計(jì)算并減去點(diǎn)云質(zhì)心坐標(biāo)，將點(diǎn)云移動(dòng)至坐標(biāo)軸中心；計(jì)算點(diǎn)云特征值和特征向量，對(duì)點(diǎn)云做旋轉(zhuǎn)變換（只有2D點(diǎn)云需要做旋轉(zhuǎn)變換）

（2）計(jì)算Delaunay三角網(wǎng)。調(diào)用qhull庫(kù)，通過(guò)qh_new_qhull函數(shù)計(jì)算點(diǎn)云在4D空間的凸包

（3）計(jì)算每個(gè)單純形的中心。調(diào)用qhull庫(kù)，通過(guò)qh_setvoronoi_all函數(shù)計(jì)算每個(gè)單純形（四面體/三角形）的球心/圓心

（4）確定Alpha Complexes。3D時(shí)，遍歷土堡中位于下邊界（Delaunay三角網(wǎng)）的四面體，計(jì)算四面體外接球半徑r，若r<α，則保存該四面體的4個(gè)三角形邊界；若r>=α，則找出四面體中滿(mǎn)足要求的三角形并保存。2D時(shí)，遍歷Delaunay三角網(wǎng)中的三角形，計(jì)算三角形外接圓半徑r，若r<α，則保存該三角形的3條邊，否則跳過(guò)（可能單獨(dú)留下一條邊沒(méi)有什么意義）

（5）確定alpha shape。3D時(shí)，遍歷Alpha Complexes中所有三角形，若相鄰的三角形中有不屬于Alpha Complexes的，則為邊界三角形，保存下來(lái)。2D時(shí)，遍歷所有邊，若相鄰邊有不屬于Alpha Complexes的，則為邊界邊，保存下來(lái)

（6）將點(diǎn)云旋轉(zhuǎn)回來(lái)，并加回質(zhì)心坐標(biāo)

PCL代碼如下：

（1）點(diǎn)云預(yù)處理