不規(guī)則物體點(diǎn)云切片中的多輪廓分割算法

張瑾，徐文，周宇喬，劉凱*

不規(guī)則物體點(diǎn)云切片中的多輪廓分割算法

張瑾1，徐文1，周宇喬2，劉凱1*

（1.四川大學(xué) 電氣工程學(xué)院，成都 610065； 2.綠色化學(xué)與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室（四川大學(xué)），成都 610064）（ ? 通信作者電子郵箱kailiu@scu.edu.cn）

使用切片法進(jìn)行不規(guī)則物體點(diǎn)云體積測(cè)量時(shí)，現(xiàn)有的多邊形拆分再重組（PSR）算法難以正確拆分較近的輪廓，進(jìn)而導(dǎo)致計(jì)算精度較低。針對(duì)這一問(wèn)題，提出一種多輪廓分割算法——改進(jìn)最近點(diǎn)搜索（INPS）算法。首先，通過(guò)局部點(diǎn)的單次使用原則分割多輪廓；其次，使用多邊形內(nèi)點(diǎn)判定（PIP）算法判斷輪廓的包含關(guān)系，以確認(rèn)輪廓面積的正負(fù)；最后，采用切片面積乘以厚度并累加的方式獲取不規(guī)則物體點(diǎn)云的體積。實(shí)驗(yàn)結(jié)果表明，在兩個(gè)公開點(diǎn)云數(shù)據(jù)集和一個(gè)化學(xué)電子密度等值面點(diǎn)云數(shù)據(jù)集上，所提算法都能實(shí)現(xiàn)高正確率的邊界分割，具有一定的普適性；且該算法體積測(cè)量的平均相對(duì)誤差為0.043 6%，低于PSR算法的0.062 7%，可見所提算法實(shí)現(xiàn)了高正確率的邊界分割。

點(diǎn)云體積測(cè)量；點(diǎn)云切片；多輪廓分割；多邊形內(nèi)點(diǎn)判定算法；最近點(diǎn)搜索法

0 引言

體積是三維空間中物體的重要屬性參數(shù)［1］，體積計(jì)算是空間中對(duì)象形態(tài)分析的基本內(nèi)容［2］，涉及規(guī)則幾何體和不規(guī)則幾何體。其中，不規(guī)則幾何體的體積測(cè)量，因?yàn)樗男螒B(tài)各異，無(wú)法歸納普適的計(jì)算方法，仍是普遍面臨且亟待解決的現(xiàn)實(shí)難題［3］。三維激光掃描的方式可以快速獲取包含物體表面結(jié)構(gòu)信息的點(diǎn)云數(shù)據(jù)，由此得到對(duì)象的三維封閉曲面模型或者多層二維輪廓邊界，這兩種方法均可計(jì)算不規(guī)則物體體積，即逆向建模法和切片法技術(shù)路線。前者體積計(jì)算準(zhǔn)確可靠，但需要經(jīng)過(guò)掃描階段、點(diǎn)云階段和曲面擬合階段才能生成目標(biāo)模型［4］，而且需要進(jìn)行拓?fù)錂z查和孔洞填充等操作［5］，計(jì)算過(guò)程耗費(fèi)資源和時(shí)間；后者將一個(gè)三維曲面問(wèn)題簡(jiǎn)化成了多個(gè)二維曲線問(wèn)題，降低了空間復(fù)雜度，以犧牲小部分精度的代價(jià)大幅減少了計(jì)算時(shí)間。因此，切片法因具有直觀和易于編程實(shí)現(xiàn)的優(yōu)勢(shì)，被廣泛地應(yīng)用于工程項(xiàng)目中，如不規(guī)則樹冠體積測(cè)量［6］、商品包裝體積測(cè)量［7］、油罐和洞庫(kù)容量計(jì)量［8］和船舶排水量計(jì)量［9］等諸多領(lǐng)域。此外，在計(jì)算化學(xué)理論研究領(lǐng)域，針對(duì)分子范德瓦爾表面上靜電勢(shì)的研究可以用于預(yù)測(cè)反應(yīng)位點(diǎn)，預(yù)測(cè)分子性質(zhì)，解釋分子間弱相互作用；而分子范德瓦爾表面（后文稱為分子電子密度等值面）的體積是一個(gè)重要參數(shù)，本文中使用Multiwfn［10］得到分子電子密度格點(diǎn)數(shù)據(jù)和靜電勢(shì)格點(diǎn)數(shù)據(jù)，經(jīng)過(guò)處理得到相應(yīng)點(diǎn)云［10-11］。

切片法測(cè)量體積的流程可以概括為獲取點(diǎn)云數(shù)據(jù)、點(diǎn)云數(shù)據(jù)切片、切片上點(diǎn)云投影、多輪廓分割及包含關(guān)系判斷、點(diǎn)云片面積計(jì)算和點(diǎn)云體積計(jì)算這6個(gè)步驟。其中，切片面積計(jì)算需要正確排序截面上無(wú)規(guī)則的點(diǎn)，生成輪廓邊界，是得到正確體積值的關(guān)鍵?，F(xiàn)有的邊界排序算法中，極坐標(biāo)排序法［9］不適用于極端凹多邊形，點(diǎn)云輪廓提取法易擴(kuò)大輪廓體積［12］，依據(jù)最小夾角原則的輪廓排序法［13］和凹包點(diǎn)內(nèi)插法［14］在面對(duì)復(fù)雜輪廓情況時(shí)仍會(huì)出錯(cuò)，雙向最近點(diǎn)搜索法［3，15］表現(xiàn)較好，但仍然和前兩者一樣局限于如墩臺(tái)、儲(chǔ)油罐和船舶等單一輪廓邊界排序。使用先分類后排序思想時(shí)，-means聚類［16］、譜聚類［17］等需要事先已知分類個(gè)數(shù)的算法不適用于此類情況。使用數(shù)字圖像方法可以分割多個(gè)輪廓，但它們對(duì)格柵大小的要求嚴(yán)格，且兩次矢柵轉(zhuǎn)換會(huì)引入新的誤差［18］。多邊形拆分再重組（Polygon Splitting and Recombination， PSR）算法［19］雖然可以區(qū)分多個(gè)輪廓，但當(dāng)切片上存在較多輪廓隨機(jī)分布時(shí)，基于統(tǒng)計(jì)學(xué)方法對(duì)異常邊拆分的方式的可靠性會(huì)較低。

針對(duì)以上不足，本文提出改進(jìn)最近點(diǎn)搜索（Improved Nearest Point Search， INPS）算法。首先，通過(guò)局部點(diǎn)的單次使用原則分割多輪廓；其次，使用多邊形內(nèi)點(diǎn)判定（Point Inclusion in Polygon， PIP）算法［20］判斷輪廓的包含關(guān)系，確認(rèn)輪廓面積的正負(fù)；最后，采用切片乘以厚度并累加的方式得到點(diǎn)云的體積，即不規(guī)則物體體積。

1 基本原理

本文算法最初針對(duì)分子電子密度等值面點(diǎn)云，該類點(diǎn)云的形狀輪廓相對(duì)簡(jiǎn)單，但在實(shí)際的分層中，截面上會(huì)出現(xiàn)數(shù)量偏多且隨機(jī)分布的輪廓邊界。本文選擇手性雙氮氧金屬配合物催化劑與底物結(jié)合模型電子密度等值面點(diǎn)云（簡(jiǎn)稱Cat6點(diǎn)云）作為實(shí)驗(yàn)對(duì)象，它的表面變化大，分層情況復(fù)雜，如圖1所示。

圖1　實(shí)驗(yàn)點(diǎn)云Cat6

圖2　分子電勢(shì)點(diǎn)云生成流程

點(diǎn)云數(shù)據(jù)是計(jì)算的基礎(chǔ)，它的獲取途徑通常是三維激光掃描，本文數(shù)據(jù)和激光掃描得到的數(shù)據(jù)的分層方式不同。

對(duì)于激光掃描數(shù)據(jù)，它的分層數(shù)為：

對(duì)于分子電子密度等值面點(diǎn)云，它的分層數(shù)為：

1.1　點(diǎn)云數(shù)據(jù)切片

MC算法的基本思想如下：遍歷格點(diǎn)數(shù)據(jù)中所有的體素（由8個(gè)點(diǎn)構(gòu)成的長(zhǎng)方體），根據(jù)它的頂點(diǎn)值與等值面閾值的關(guān)系，將它歸類到15種關(guān)系之一［21］，通過(guò)插入三角形重建物體的表面。取圖2（b）中分子等值面點(diǎn)云頂部?jī)蓪?，通過(guò)觀察電子密度格點(diǎn)點(diǎn)云中等值面內(nèi)部的點(diǎn)與重建后等值面上的點(diǎn)之間的位置關(guān)系，歸納針對(duì)此類點(diǎn)云的一種切片上投影點(diǎn)的預(yù)處理方法，可以有效去除非輪廓上的點(diǎn)，流程如圖3所示。

圖3（a）中紅色點(diǎn)表示格點(diǎn)點(diǎn)云在曲面內(nèi)的點(diǎn)，藍(lán)色點(diǎn)表示重建后的電子密度等值面點(diǎn)云，圖3（b）為圖3（a）中黑框所示的頂部?jī)蓪拥狞c(diǎn)云，重建后的藍(lán)色點(diǎn)與紅色點(diǎn)重合或者在紅色點(diǎn)外部。兩層紅點(diǎn)之間散落著一些藍(lán)色點(diǎn)，這是通過(guò)MC算法插值得到的三角形的頂點(diǎn)。圖3（c）是連接這些三角形后的示意圖。圖3（d）是俯視視角示意圖，其中綠色線段是觀察子圖3（c）畫出的輪廓線?？梢钥闯?，輪廓線上的點(diǎn)均沒(méi)有落在棋盤格點(diǎn)上（沿軸方向投影，格點(diǎn)文件某一層的點(diǎn)呈現(xiàn)類似于圍棋棋盤格點(diǎn)的分布），圖3（e）中列出的幾種邊界處體素的情況可用于解釋。其中，綠色點(diǎn)表示格點(diǎn)點(diǎn)云在等值面外的點(diǎn)，根據(jù)它們的分布，在體素內(nèi)插入不同數(shù)量和位置的三角形，并將三角形沿軸方向投影，落在棋盤格點(diǎn)上的點(diǎn)均處于體素上下兩層間的棱上，而構(gòu)成輪廓線的點(diǎn)正是那些在體素上下兩層面上的點(diǎn)。

圖3　MC算法處理后的輪廓線示意圖

因此，針對(duì)由MC算法得到的點(diǎn)云，按照式（4）分層后，再將落在棋盤格點(diǎn)上的點(diǎn)剔除，從而得到高質(zhì)量的輪廓線，從上述點(diǎn)云中選取其中3層，展示輪廓分布情況，如圖4所示。

圖4　具有代表性的兩層切片點(diǎn)云投影

1.2　多輪廓分割

最近點(diǎn)搜索法和雙向最近搜索法的搜索策略是連接平面上所有的點(diǎn)，因此這兩種方法都無(wú)法區(qū)分多個(gè)輪廓。本文提出的INPS是基于局部點(diǎn)單次使用原則區(qū)分不同輪廓：對(duì)于一個(gè)理想的輪廓點(diǎn)集，每一個(gè)點(diǎn)只需和距離自身最近的兩個(gè)點(diǎn)連接，得到一個(gè)閉合的輪廓線。因此，當(dāng)一個(gè)點(diǎn)附近的所有點(diǎn)均已被使用（即進(jìn)行過(guò)連接），則判斷已經(jīng)完成一次輪廓連接，并從下一個(gè)未使用過(guò)的點(diǎn)開始連線。具體步驟如下：

4）判斷是否完成所有輪廓搜索。若還有未使用點(diǎn)，重復(fù)步驟1），否則輪廓搜索結(jié)束。

圖5　INPS算法進(jìn)行點(diǎn)集分割

圖6　經(jīng)INPS算法處理后的輪廓線

1.3　截面面積計(jì)算

精確的截面面積計(jì)算決定了不規(guī)則物體體積計(jì)算的準(zhǔn)確度，而輪廓之間包含關(guān)系的正確判斷，是截面面積精確計(jì)算的關(guān)鍵。點(diǎn)云切片中的輪廓只應(yīng)存在包含和相離兩種位置關(guān)系，判斷方法如圖7所示，常見的分布情況如圖8所示。INPS算法的判斷思路是：首先，使用高斯面積公式［1］計(jì)算各個(gè)輪廓的面積；其次，使用PIP算法判斷輪廓間的位置狀態(tài)，判斷每個(gè)輪廓和除自己以外的輪廓之間的包含關(guān)系，若該輪廓被其他輪廓包含，則記錄該輪廓被包含數(shù)加1；最后通過(guò)式（12）判斷輪廓面積正負(fù)。

其中表示輪廓被包含的次數(shù)。

圖8　多輪廓位置關(guān)系

在圖7中，使用INPS算法將點(diǎn)集分為3個(gè)輪廓點(diǎn)集，分別用圓形、三角形和正方形表示。判斷三角形點(diǎn)集和正方形點(diǎn)集是否被圓形點(diǎn)集包含，只需要從每個(gè)點(diǎn)集中任選一個(gè)點(diǎn)，找到圓形輪廓線中與該點(diǎn)相交的線段，確定線段的方向（例如從軸方向小值指向大值），然后計(jì)算點(diǎn)與線段法向量的乘積。若所有值的乘積為負(fù)數(shù)，則被包含；反之則不包含。圖8中輪廓2只被輪廓1包含，因此面積為負(fù)數(shù)，而輪廓3被包含2次，面積仍為正。

2 實(shí)驗(yàn)與結(jié)果分析

逆向建模法計(jì)算得到的體積準(zhǔn)確可靠，可以作為本文點(diǎn)云體積的真值，作為改進(jìn)算法的檢驗(yàn)依據(jù)。因此，本文使用Geomagic Wrap 2017軟件計(jì)算點(diǎn)云體積真值和截面面積真值。實(shí)驗(yàn)基于Matlab語(yǔ)言實(shí)現(xiàn)了INPS算法和多邊形拆分再重組（PSR）算法［19］，并對(duì)比分析了使用場(chǎng)景和計(jì)算精度。

2.1　分子電子密度點(diǎn)云

針對(duì)分子電子密度等值面點(diǎn)云，對(duì)比INPS算法和PSR算法［19］的結(jié)果。表1為Cat6點(diǎn)云數(shù)據(jù)信息，使用兩種算法時(shí)，PSR算法和INPS算法的輪廓分割系數(shù)分別為2.5、3.0。使用PSR算法時(shí)，6個(gè)位置數(shù)據(jù)下的標(biāo)準(zhǔn)差與分割閾值見表2。選取Cat6點(diǎn)云在3個(gè)方向上具有代表性的3個(gè)位置進(jìn)行展示，沿3個(gè)方向投影的平面均命名為，結(jié)果如圖9～11所示。通過(guò)觀察發(fā)現(xiàn)沿軸切片時(shí)，輪廓的情況最復(fù)雜，數(shù)量多且隨機(jī)分布，因此重點(diǎn)分析該方向。針對(duì)Cat6點(diǎn)云的6個(gè)切片位置，使用Geomagic Wrap計(jì)算得到的面積作為真值，誤差分析結(jié)果見表3。

表1　Cat6點(diǎn)云數(shù)據(jù)信息

表2　PSR算法中的標(biāo)準(zhǔn)差與分割閾值

表3　Cat6點(diǎn)云不同切片位置處截面面積計(jì)算結(jié)果對(duì)比（Z軸）

圖9　Cat6點(diǎn)云在不同切片位置（Z軸）的輪廓分割結(jié)果對(duì)比

圖10　Cat6點(diǎn)云在不同切片位置（Y軸）的輪廓分割結(jié)果對(duì)比

圖11　Cat6點(diǎn)云不同切片位置（X軸）的輪廓分割結(jié)果對(duì)比

2.2　公開點(diǎn)云數(shù)據(jù)集

為驗(yàn)證算法的有效性和魯棒性，使用三維激光掃描公開數(shù)據(jù)集（由斯坦福大學(xué)計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn)室公布）中Stanford Bunny和Happy Buddha（如圖12所示）進(jìn)行實(shí)驗(yàn)。

圖12　實(shí)物和三維曲面模型

由于原始點(diǎn)云密度較低，造成切片質(zhì)量差，因此對(duì)原始點(diǎn)云上采樣。先使用移動(dòng)最小二乘法（Moving Least Squares， MLS）對(duì)三維點(diǎn)云進(jìn)行平滑擬合，然后重采樣。與分子點(diǎn)云相比，Stanford Bunny和Happy Buddha這兩組數(shù)據(jù)單一輪廓的邊界形狀更復(fù)雜，但切片上的輪廓數(shù)較少。

兩組點(diǎn)云的數(shù)據(jù)信息、分層間隔和輪廓分割系數(shù)取值如表4所示，處理后的結(jié)果如圖13～14所示（其中PSR算法的效果圖可參考文獻(xiàn)［19］），3個(gè)切片位置處面積的相對(duì)誤差結(jié)果如表5所示。

圖13　Stanford Bunny點(diǎn)云在不同切片位置（Z軸）的輪廓分割結(jié)果對(duì)比

表4　兩組點(diǎn)云數(shù)據(jù)處理中的參數(shù)

表5　PSR和INPS算法對(duì)Stanford Bunny 和Happy Buddha點(diǎn)云中6個(gè)截面的面積誤差對(duì)比

圖14　Happy Buddha點(diǎn)云在不同切片位置（Z軸）的輪廓分割結(jié)果對(duì)比

2.3　切片多輪廓分割

根據(jù)上述實(shí)驗(yàn)結(jié)果，可以得出以下結(jié)論。

1）適用性。無(wú)論是針對(duì)MC算法處理后的點(diǎn)云，還是針對(duì)激光掃描得到的點(diǎn)云，INPS算法均表現(xiàn)了良好的輪廓分割效果，截面面積的誤差也大致相同。從圖9（a）可知，在針對(duì)分子電勢(shì)點(diǎn)云時(shí)，與PSR算法相比，INPS算法的誤連情況更少。在公開數(shù)據(jù)集上，INPS算法的效果和PSR算法的效果相當(dāng)。

2）魯棒性。在圖9中，相較于PSR算法，INPS算法更加穩(wěn)定。如圖9（b）所示，PSR算法都出現(xiàn)了不同程度的誤連，這是因?yàn)樵谶@3幅圖中，輪廓數(shù)量多，輪廓之間誤連的線段也相應(yīng)增多，計(jì)算得到的標(biāo)準(zhǔn)差偏大，導(dǎo)致一些距離較近的輪廓之間的誤連線段難以被剔除，此時(shí)對(duì)式（9）中系數(shù)的選擇條件較為苛刻。INPS算法的優(yōu)勢(shì)是，在輪廓中一點(diǎn)的搜索范圍內(nèi)，只要距離仍在該輪廓中一點(diǎn)的距離小于到其他輪廓任意點(diǎn)的距離，就不會(huì)出現(xiàn)誤連，即使是在截面投影點(diǎn)質(zhì)量較差的情況，也幾乎不存在誤連的情況，如圖13～14所示。同時(shí)，INPS算法對(duì)于一個(gè)輪廓搜索完成的判定條件，使得對(duì)于系數(shù)的選擇也更寬松。

2.4　點(diǎn)云體積計(jì)算

1）準(zhǔn)確性。

PSR和INPS算法針對(duì)3組點(diǎn)云的誤差都在0.1%內(nèi)，并且本文算法的誤差均低于PSR算法，其中，INPS算法的平均相對(duì)誤差為0.043 6%，低于PSR算法的0.062 7%。如在圖9中，PSR算法針對(duì)個(gè)別距離較近的輪廓沒(méi)有糾正誤連線段，導(dǎo)致該截面處輪廓的面積計(jì)算偏大。從表6可知，針對(duì)Cat6點(diǎn)云體積計(jì)算，INPS算法得到的體積小于PSR算法得到的體積，這也和實(shí)際情況符合。

2）高效性。

從算法的流程分析，由于PSR算法是基于雙向最近點(diǎn)搜索法的改進(jìn)算法，在最開始需要使用雙向最近點(diǎn)搜索法排序截面中所有的點(diǎn)，而INPS算法在同樣的排序過(guò)程中已經(jīng)將點(diǎn)分類。這是因?yàn)镮NPS算法在對(duì)點(diǎn)排序的同時(shí)，根據(jù)伴隨該點(diǎn)排序得到的數(shù)據(jù)也對(duì)點(diǎn)分類；而PSR算法更關(guān)注根據(jù)統(tǒng)計(jì)學(xué)數(shù)據(jù)拆分長(zhǎng)度異常邊，然后重組。因此，INPS算法在復(fù)雜度上低于PSR算法，并且實(shí)驗(yàn)結(jié)果也驗(yàn)證了INPS算法正確率略高于PSR算法。

表6　PSR和INPS算法對(duì)3組數(shù)據(jù)體積測(cè)量結(jié)果的對(duì)比

2.5　誤差分析

1）輪廓線不正確。針對(duì)公開點(diǎn)云數(shù)據(jù)集，使用投影的方法得到輪廓點(diǎn)時(shí)，難免出現(xiàn)局部點(diǎn)密度過(guò)大或過(guò)小的情況，導(dǎo)致無(wú)法反映真實(shí)的輪廓線，引入誤差；而使用MC算法處理的點(diǎn)云，由于它的數(shù)據(jù)特征，與投影的方法相比，可以很大程度避免此類誤差。

2）自相交。一個(gè)正確的輪廓線不存在其中某兩條線段交叉的情況，但在點(diǎn)分布不規(guī)則的局部，可能會(huì)出現(xiàn)輪廓線相交的情況［25］。

3）使用截面面積乘以厚度模擬不規(guī)則物體在該處體積本身就存在一定的誤差，并且該誤差具有不確定性，可能會(huì)隨機(jī)地互補(bǔ)，并且沿著切片的累加積累。

3 結(jié)語(yǔ)

本文提出了一種改進(jìn)的基于最近點(diǎn)搜索法的多輪廓分割算法，并與多邊形拆分再重組算法進(jìn)行實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)結(jié)果表明，本文算法針對(duì)特定數(shù)據(jù)和公開數(shù)據(jù)集均能出色地完成多輪廓的分割，具有普適性和良好的抗干擾性；并且當(dāng)存在多個(gè)輪廓隨機(jī)分布時(shí)，本文算法的分割效果優(yōu)于多邊形拆分再重組算法。因?yàn)榇藭r(shí)根據(jù)統(tǒng)計(jì)學(xué)分割異常邊的可靠性較低，而本文算法的判斷方式（局部點(diǎn)單次使用原則）更加貼合人為分割輪廓時(shí)的思維方式，故抗干擾能力更強(qiáng)。相較于多邊形拆分再重組法，采用本文算法計(jì)算體積的正確率略高（針對(duì)3組數(shù)據(jù)的相對(duì)誤差分別是0.075 3%、0.033 0%和0.022 6%），且具有更強(qiáng)的魯棒性和更小的算法復(fù)雜度。但是本文算法仍存在不足，針對(duì)公開數(shù)據(jù)集，沒(méi)有可靠的投影方案，若使用點(diǎn)云密度相關(guān)的投影厚度，則無(wú)法自適應(yīng)地選取合適的投影厚度。在后續(xù)工作中，針對(duì)不同密度的點(diǎn)云，為了得到更高質(zhì)量的輪廓點(diǎn)，我們將研究如何實(shí)現(xiàn)普適性更強(qiáng)的自適應(yīng)截面點(diǎn)投影算法。

[1] 郭仁忠. 空間分析［M］. 2版. 北京：高等教育出版社， 2001： 143-145.（GUO R Z. Spatial Analysis［M］. 2nd ed. Beijing： Higher Education Press， 2001： 143-145.）

[2] ANDERSEN H E. Estimation of critical forest structure metrics through the spatial analysis of airborne laser scanner data［D］. Seattle， WA： University of Washington， 2003： 197-202.

[3] 劉明學(xué)，崔進(jìn)業(yè). 基于點(diǎn)云三維坐標(biāo)數(shù)據(jù)計(jì)算復(fù)雜物體體積［J］. 測(cè)繪地理信息， 2018， 43（3）： 96-98.（LI M X， CUI J Y. Calculate volume of complex objects based on 3D coordinates of points cloud data［J］. Journal of Geomatics， 2018， 43（3）： 96-98.）

[4] 魏言標(biāo)，鄭磊，薛少兵，等. 基于三坐標(biāo)測(cè)量和3D掃描的凸輪逆向建模設(shè)計(jì)［J］. 機(jī)械設(shè)計(jì)， 2021， 38（9）： 71-74.（WEI Y B， ZHENG L， XUE S B， et al. Reverse modeling design of the cam based on three-coordinate measurement and 3D scanning［J］. Journal of Machine Design， 2021， 38（9）： 71-74.）

[5] 王鑫龍，孫文磊，張建杰，等. 基于點(diǎn)云數(shù)據(jù)的逆向工程技術(shù)研究綜述［J］. 制造技術(shù)與機(jī)床， 2018（2）： 49-53.（WANG X L， SUN W L， ZHANG J J， et al. Review on reverse engineering research based on point cloud data［J］. Manufacturing Technology and Machine Tool， 2018（2）： 49-53.）

[6] 董亞涵，李永強(qiáng)，李鵬鵬，等. 基于改進(jìn)凸包算法的樹冠輪廓點(diǎn)提取與體積計(jì)算［J］. 測(cè)繪工程， 2018， 27（8）： 66-71.（DONG Y H， LI Y Q， LI P P， et al. Tree crown outline points extracting and volume calculation based on improved convex hull algorithm［J］. Engineering of Surveying and Mapping， 2018， 27（8）： 66-71.）

[7] 陳琛，李寶順，包亞萍. 基于光柵投影和點(diǎn)云體積計(jì)算的過(guò)度包裝檢測(cè)系統(tǒng)［J］. 計(jì)算機(jī)測(cè)量與控制， 2014， 22（12）： 3919-3922.（CHEN C， LI B S， BAO Y P. Excessive packaging detection system based on point set volume calculation method and grating projection［J］. Computer Measurement and Control， 2014， 22（12）： 3919-3922.）

[8] 呂小寧，劉曉麗，段云嶺，等. 地下能源儲(chǔ)庫(kù)群容積激光測(cè)量方法及現(xiàn)場(chǎng)實(shí)驗(yàn)［J］. 中國(guó)激光， 2016， 43（10）： No.1004002.（LYU X N， LIU X L， DUAN Y L， et al. Laser measurement method and in-situ experiment of underground energy storage caverns volume［J］. Chinese Journal of Lasers， 2016， 43（10）： No.1004002.）

[9] 張吉星，程效軍，程小龍. 三維激光掃描技術(shù)在船舶排水量計(jì)量中的應(yīng)用［J］. 中國(guó)激光， 2016， 43（12）： No.1204003.（ZHANG J X， CHENG X J， CHENG X L. Application of three-dimensional laser scanning technology in measurement of ship displacement［J］. Chinese Journal of Lasers， 2016， 43（12）： No.1204003.）

[10] LU T， CHEN F W. Multiwfn： a multifunctional wavefunction analyzer［J］. Journal of Computational Chemistry， 2012， 33（5）： 580-592.

[11] LU T， CHEN F. Quantitative analysis of molecular surface based on improved Marching Tetrahedra algorithm［J］. Journal of Molecular Graphics and Modelling， 2012， 38： 314-323.

[12] 連強(qiáng)強(qiáng)，顧敏. 基于α-shape的三維激光點(diǎn)云計(jì)算樹冠體積的研究［J］. 青海大學(xué)學(xué)報(bào)， 2020， 38（5）： 74-79.（LIAN Q Q， GU M. Research on the calculation of tree crown volume by 3D laser point cloud based on α-shape［J］. Journal of Qinghai University， 2020， 38（5）： 74-79.）

[13] 付敬帥，李斌. 基于點(diǎn)云截面數(shù)據(jù)點(diǎn)的多輪廓排序算法［J］. 河南科學(xué)， 2019， 37（6）： 933-937.（FU J S， LI B. Multi-contour sorting algorithm based on point cloud cross-section data points［J］. Henan Science， 2019， 37（6）： 933-937.）

[14] 程效軍，熊鑫鑫，楊澤鑫，等. 基于地面激光雷達(dá)的洞庫(kù)容量計(jì)量［J］. 激光與光電子學(xué)進(jìn)展， 2019， 56（23）： No.231201.（CHENG X J， XIONG X X， YANG Z X， et al. Cavern capacity calculation using terrestrial lidar［J］. Laser and Optoelectronics Progress， 2019， 56（23）： No.231201.）

[15] 錢錦鋒，陳志楊，張三元，等. 點(diǎn)云數(shù)據(jù)壓縮中的邊界特征檢測(cè)［J］. 中國(guó)圖象圖形學(xué)報(bào)， 2005， 10（2）： 164-169.（QIAN J F， CHEN Z Y， ZHANG S Y， et al. The detection of boundary point of point cloud compression［J］. Journal of Image and Graphics， 2005， 10（2）： 164-l69.）

[16] JAIN A K. Data clustering： 50 years beyond K-means［J］. Pattern Recognition Letters， 2010， 31（8）： 65l-666.

[17] NG A Y， JORDAN M I， WEISS Y. On spectral clustering analysis and an algorithm［C］// Proceedings of the 14th International Conference on Neural Information Processing Systems： Natural and Synthetic. Cambridge： MIT Press， 2001 ：849-856.

[18] 程效軍，方芳. 基于形態(tài)學(xué)的散亂點(diǎn)云輪廓特征線提?。跩］. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2014， 42（11）： 1738-1743.（CHENG X J， FANG F. Morphology-based scattered point cloud contour extraction［J］. Journal of Tongji University （Natural Science）， 2014， 42（11）： 1738-1743.）

[19] 劉金錦，李浩軍. 基于點(diǎn)云切片改進(jìn)法的不規(guī)則物體體積測(cè)量［J］. 光學(xué)學(xué)報(bào)， 2021， 41（23）： No.2312003.（LIU J J， LI H J. Volume measurement of irregular objects based on improved point cloud slicing method［J］. Acta Optica Sinica， 2021， 41（23）： No.2312003.）

[20] HAINES E. Point in polygon strategies［M］// HECKBERT P S. Graphics Gems IV. San Diego， CA： Academic Press， 1994： 24-46.

[21] LORENSEN W E， CLINE H E. Marching cubes： a high resolution 3D surface construction algorithm［J］. ACM SIGGRAPH Computer Graphics， 1987， 21（4）：163-169.

[22] LIU K， RAN X， GONG J， et al. Extending epipolar geometry for real-time structured light illumination Ⅱ： lossless accuracy［J］. Optics Letters， 2021， 46（4）： 837-840.

[23] JIA M， YANG X， LIU K. Automatically detecting rigidly and nonrigidly deformed facial landmarks from coarseness to fineness［J］. Journal of Electronic Imaging， 2019， 28（6）： No.063009.

[24] ZHANG G， XU B， LAU D L， et al. Correcting projector lens distortion in real time with a scale-offset model for structured light illumination［J］. Optics Express， 2022， 30（14）： 24507-24522.

[25] 柯映林，王青. 反求工程中的點(diǎn)云切片算法研究［J］. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2005， 17（8）： 1798-1802.（KE Y L， WANG Q. Research on point cloud slicing technique in reverse engineering［J］. Journal of Computer-Aided Design and Computer Graphics， 2005， 17（8）： 1798-1802.）

Multi-contour segmentation algorithm for point cloud slices of irregular objects

ZHANG Jin1， XU Wen1， ZHOU Yuqiao2， LIU Kai1*

（1，，610065，；2，（），610064，）

When using the slicing method to measure the point cloud volumes of irregular objects， the existing Polygon Splitting and Recombination （PSR） algorithm cannot split the nearer contours correctly， resulting in low calculation precision. Aiming at this problem， a multi-contour segmentation algorithm — Improved Nearest Point Search （INPS） algorithm was proposed. Firstly， the segmentation of multiple contours was performed through the single-use principle of local points. Then， Point Inclusion in Polygon （PIP） algorithm was adopted to judge the inclusion relationship of contours， thereby determining positive or negative property of the contour area. Finally， the slice area was multiplied by the thickness and the results were accumulated to obtain the volume of irregular object point cloud. Experimental results show that on two public point cloud datasets and one point cloud dataset of chemical electron density isosurface， the proposed algorithm can achieve high-accuracy boundary segmentation and has certain universality. The average relative error of volume measurement of the proposed algorithm is 0.043 6%， which is lower than 0.062 7% of PSR algorithm， verifying that the proposed algorithm achieves high accuracy boundary segmentation.

volume measurement of point cloud; point cloud slicing; multi-contour segmentation; Point Inclusion in Polygon (PIP) algorithm; nearest point search method

This work is partially supported by Key Research and Development Project of Science and Technology Department of Sichuan Province （22ZDYF3012）， Sichuan Higher Education Talent Training Quality and Teaching Reform Project （JG2021-36）， Sichuan University Science Characteristic Direction Cultivation Program （2020SCUNL204）， Sichuan University Postgraduate Education and Teaching Reform Research Project （GSSCU2021020）.

ZHANG Jin， born in 1998， M. S. candidate. His research interests include point cloud analysis， structured light three-dimensional imaging and its applications.

XU Wen， born in 1992， Ph. D. candidate. Her research interests include structured light three-dimensional imaging and its applications， artificial intelligence.

ZHOU Yuqiao， born in 1988， Ph. D. His research interests include X-ray crystallography， structural chemistry， computational chemistry.

LIU Kai， born in 1973， Ph. D.， professor. His research interests include structured light three-dimensional imaging and its applications， computer vision， digital image/signal processing.

1001-9081（2023）10-3209-08

10.11772/j.issn.1001-9081.2022101536

2022?10?13；

2023?01?10；

四川省科技廳重點(diǎn)研發(fā)項(xiàng)目（22ZDYF3012）；四川省高等教育人才培養(yǎng)質(zhì)量和教學(xué)改革項(xiàng)目（JG2021?36）；四川大學(xué)理科特色方向培育計(jì)劃項(xiàng)目（2020SCUNL204）；四川大學(xué)研究生教育教學(xué)改革研究項(xiàng)目（GSSCU2021020）。

張瑾（1998—），男，四川南充人，碩士研究生，主要研究方向：點(diǎn)云分析、結(jié)構(gòu)光三維成像及應(yīng)用； 徐文（1992—），女（彝族），四川雅安人，博士研究生，主要研究方向：結(jié)構(gòu)光三維成像及應(yīng)用、人工智能； 周宇喬（1988—），男，浙江紹興人，博士，主要研究方向：X射線晶體學(xué)、結(jié)構(gòu)化學(xué)、計(jì)算化學(xué)； 劉凱（1973—），男（壯族），江蘇無(wú)錫人，教授，博士生導(dǎo)師，博士，主要研究方向：結(jié)構(gòu)光三維成像及應(yīng)用、機(jī)器視覺(jué)、數(shù)字圖像/信號(hào)處理。

TP301.6

A

2023?01?11。