結(jié)合點(diǎn)云占比和平滑度的碗狀碎塊內(nèi)表面識別算法

孫進(jìn) 丁煜 王寧 習(xí)俊通 朱興龍

摘?要：基于內(nèi)表面特性的碗狀碎塊重組算法可有效避免由斷裂曲面引起的過分割問題，但其難點(diǎn)在于內(nèi)表面的準(zhǔn)確提取，為此提出一種結(jié)合點(diǎn)云占比和平滑度的碗狀碎塊內(nèi)表面識別算法。首先基于區(qū)域生長算法將碗狀碎塊的表面分割成斷裂曲面、底面、原始表面、內(nèi)表面和外表面;然后根據(jù)其點(diǎn)云占比的顯著差異從中識別出內(nèi)表面和外表面，最后利用平滑度提取內(nèi)表面。實(shí)驗(yàn)結(jié)果表明該算法能實(shí)現(xiàn)碗狀碎塊內(nèi)表面的準(zhǔn)確提取，并且具有更快的運(yùn)算速度。

關(guān)鍵詞：點(diǎn)云占比;平滑度;碗狀碎塊;內(nèi)表面;識別

DOI：10.15938/j.jhust.2020.03.024

中圖分類號：?TP301.6

文獻(xiàn)標(biāo)志碼：?A

文章編號：?1007-2683（2020）03-0157-06

Abstract：The?bowl-shaped?broken?pieces?reassembly?algorithm?based?on?the?inner?surface?characteristics?can?effectively?avoid?the?over?segmentation?problem?caused?by?the?fracture?surface，?while?the?difficulty?lies?in?the?accurate?extraction?of?inner?surface.?Therefore，?an?identification?algorithm?for?inner?surface?of?bowl-shaped?broken?pieces?based?on?point?cloud?proportion?and?smoothness?is?proposed.?Firstly，?the?surface?of?bowl-shaped?broken?pieces?is?divided?into?fracture?surface，?bottom?surface，?original?surface，?inner?surface?and?outer?surface?based?on?the?region?growing?algorithm.?And?then，?according?to?the?significant?difference?of?point?cloud?proportion，?the?inner?surface?and?outer?surface?are?identified?from?the?segmented?surface?group.?Finally，?the?inner?surface?is?extracted?by?the?smoothness?value.?The?experimental?results?show?that?this?algorithm?can?accurately?extract?the?inner?surface?of?bowl-shaped?broken?pieces?and?has?a?higher?calculation?speed?than?other?algorithm.

Keywords：point?cloud?proportion;?smoothness;?bowl-shaped?broken?pieces;?inner?surface;?identification

0?引?言

人類悠久的文明使得河流、湖泊、海洋下隱藏著眾多的文化遺跡。以近期結(jié)束清理工作的“南海一號”為例，從這艘沉船打撈出的十四多萬件文物中有九成以上是以碗狀器型存在的瓷器[1]。這些水下文物在水底經(jīng)過長時間的侵蝕和顛簸，大多數(shù)變得破碎殘缺。由于破損文物數(shù)量眾多，利用計(jì)算機(jī)輔助技術(shù)將其數(shù)字化后進(jìn)行虛擬拼接，對水下文物的保護(hù)有著十分重要的意義。為便于文物數(shù)字化表征，基于厚度值大致將破損物體分為兩類：厚度小于1mm的如紙幣、油畫[2]和地圖[3]等，稱為碎片;厚度大于1mm的如碗、壁畫[4]和兵馬俑[5]等，稱為碎塊。考慮到水下文物中大部分是以碗狀器型存在的物件，故本文以碗狀碎塊為研究對象。

在三維碎塊拼接領(lǐng)域，傳統(tǒng)的碎塊重組算法主要圍繞斷裂曲面的幾何特征[6]展開，因此許多專家學(xué)者提出了關(guān)于斷裂曲面的識別算法。如清華大學(xué)的Huang等[7]使用積分幾何量勾勒出碎塊各曲面的特征，并基于曲面局部彎曲能量進(jìn)行斷裂曲面的識別。在曲面局部彎曲能量的基礎(chǔ)上，2017年，雅典經(jīng)濟(jì)與商業(yè)大學(xué)Papaioannou等[8]結(jié)合球體體積積分不變量來表征曲面特性，然后通過閾值來判別曲面是否是斷裂曲面。2018年，西北大學(xué)的趙夫群[9]利用曲面的平均粗糙度數(shù)值來認(rèn)定斷裂曲面，但是上述算法過于依賴給定的閾值范圍，其普適性需要實(shí)驗(yàn)驗(yàn)證。此外雅典國立科技大學(xué)的Papaodysseus等[10]通過提取壁畫碎塊上下平面之間最大連通子集片段來識別斷裂曲面。2014年，巖手大學(xué)的Altantsetseg等[11]根據(jù)空間點(diǎn)的曲率檢測得到曲面的脊點(diǎn)和谷點(diǎn)，然后通過基于距離的聚類算法累計(jì)脊點(diǎn)和谷點(diǎn)的數(shù)量從而識別出碎塊的斷裂曲面。2015年，路易斯安那州立大學(xué)的Zhang等[12]通過提取曲率值較高的點(diǎn)建立最小生成樹，并將這些點(diǎn)連接成的曲線來代表斷裂曲面的輪廓曲線，從而在碎塊中識別出斷裂曲面。2016年，西北大學(xué)的李群輝[13]根據(jù)高斯曲率和平均曲率判斷曲面頂點(diǎn)的凹凸性，然后對凹凸點(diǎn)進(jìn)行聚類實(shí)現(xiàn)斷裂面的識別。2017年，首爾大學(xué)的Son等[14]利用法向量方差，二面角和成對距離描述斷裂曲面的凸域和凹域，并定義曲面識別標(biāo)志來提取斷裂曲面。

上述斷裂曲面的識別算法存在兩個共性問題：一是對于幾何信息不明顯的斷裂曲面來說，容易在匹配三維碎塊的過程中產(chǎn)生拼接錯誤，從而導(dǎo)致拼接算法準(zhǔn)確率的下降;二是對于幾何信息豐富的斷裂曲面來說，容易在曲面分割時產(chǎn)生過分割現(xiàn)象，從而在提取特征前需要合并過分割的斷裂曲面，增加了拼接過程的時間。相較于斷裂曲面可能存在的問題，內(nèi)表面除了幾何信息，還擁有比斷裂曲面更豐富的顏色信息和紋理信息，可防止拼接過程中因使用單一特征所導(dǎo)致的拼接失誤;同時內(nèi)表面的識別算法不需要對斷裂曲面分割后產(chǎn)生的眾多曲面進(jìn)行合并，僅需正確區(qū)分?jǐn)嗔亚婧蛢?nèi)表面即可，可避開過分割帶來的問題。因此本文提出一種結(jié)合點(diǎn)云占比和平滑度的碗狀碎塊內(nèi)表面識別算法。

1?曲面分類的概述

在一般的碎塊模型中，主要存在兩種類型的曲面：斷裂曲面和非斷裂曲面，通?？梢愿鶕?jù)曲面的粗糙程度來識別斷裂曲面。相比于非斷裂曲面，斷裂曲面上空間點(diǎn)的法向量變化程度更大，表面更凹凸不平。為描述曲面全局或局部空間的幾何差異，引入彎曲能量[7]來表示其曲面粗糙度：

設(shè)置一個以p為球心，r為半徑的包圍球，則點(diǎn)p在鄰域Br（p）內(nèi)的局部彎曲能力定義為

其中：n為曲面S上的空間點(diǎn)個數(shù)。若平均粗糙度ρ（S）大于給定閾值ρ′，則曲面S可判定為斷裂曲面。

而對于碗狀碎塊的點(diǎn)云數(shù)據(jù)模型，采用區(qū)域生長算法[15]經(jīng)過曲面分割后，可以將非斷裂曲面細(xì)分為底面、原始表面、外表面和內(nèi)表面4種類型。其中底面指的是碗狀物體底部的曲面，外表面指的是碗狀碎塊外側(cè)的曲面，內(nèi)表面指的是碗狀碎塊內(nèi)側(cè)的曲面，原始表面指的是區(qū)域生長算法在外表面和內(nèi)表面交界處過度分割的曲面，這部分曲面表面積較小，僅存在外表面和內(nèi)表面相鄰的部分碗狀碎塊中。曲面的分割結(jié)果如圖1所示。

2?內(nèi)表面的識別

2.1?點(diǎn)云占比

點(diǎn)云占比主要受兩方面因素的影響：三維掃描儀的掃描原理和碎塊自身的幾何形態(tài)。與顏色特征和曲率等幾何特征不同，受到測量過程中人為因素、環(huán)境因素或者測量方式的影響，點(diǎn)云占比通常無法精準(zhǔn)反映碎塊的表面特征。然而在使用相同的掃描方式和盡量避噪聲點(diǎn)干擾的前提下，點(diǎn)云占比可以定性地反映碎塊曲面的性質(zhì)。

本文采用點(diǎn)云占比定性分析碗狀碎塊各分割曲面的性質(zhì)。這主要是因?yàn)橄啾扔谄渌愋偷乃閴K，碗狀碎塊的厚度較薄，導(dǎo)致其外表面和內(nèi)表面的表面積要大于其他曲面，也造成外表面和內(nèi)表面的點(diǎn)云占比明顯大于其他曲面。點(diǎn)云占比可以描述碎塊中各分割曲面的大小，數(shù)值上等于曲面的空間點(diǎn)個數(shù)在碎塊點(diǎn)云中所占的百分比。假設(shè)碗狀碎塊共有φ個分割曲面，且曲面Sφ（1≤φ≤φ）的空間點(diǎn)個數(shù)為Gφ，則曲面Sφ的點(diǎn)云占比可表示為

通常根據(jù)各個曲面的點(diǎn)云占比，可以從碗狀碎塊的眾多分割曲面中識別出外表面和內(nèi)表面。

2.2?平滑度

考慮到碗狀物體在平時生活中的實(shí)際應(yīng)用，外表面常用于抓取接觸，內(nèi)表面要便于清洗使用，而且一般情況下外表面還會設(shè)計(jì)一些凸出的紋飾特征，因此內(nèi)表面一般比外表面更加光滑平整。數(shù)學(xué)表征為：相比于外表面，內(nèi)表面上某一空間點(diǎn)的法向量與其周圍點(diǎn)的法向量變化程度較小。為定量表征，本文引入平滑度的概念。

由于曲面上任意一點(diǎn)的法向量求取方法近似于計(jì)算曲面的一個相切面的法向量，因此曲面上任意一點(diǎn)的法向量計(jì)算可轉(zhuǎn)化成一個最小二乘法的平面擬合估計(jì)問題。在三維空間坐標(biāo)下，曲面Sφ可視作由l個點(diǎn)構(gòu)成，即Sφ={p1，p2，…，pl}，其中第?α個點(diǎn)pα（1≤α≤l）周圍有m個鄰域點(diǎn)pβ（1≤β≤m），那么這些點(diǎn)的質(zhì)心pc可以表示為

利用最小二乘法擬合pα所在的局部曲面，通過求解局部曲面的法向量來表示pα的法向量，此時可以構(gòu)建局部曲面的3×3協(xié)方差矩陣[16]：

矩陣M的3個特征值分別為a，b，c，其中a≤b≤c，最小特征值a所對應(yīng)的特征向量即為pα的法向量，那么曲面Sφ的平滑度εφ可以表示為

其中φα，β為pα的法向量與其鄰域點(diǎn)pβ的法向量的夾角。

εφ的大小可以定量地反映曲面Sφ的平滑度。曲面中相鄰點(diǎn)之間的法向量變化愈小，則說明曲面的平滑度愈大。一般來說，碗狀碎塊的內(nèi)表面平滑度數(shù)值要大于外表面。

2.3?內(nèi)表面識別算法

結(jié)合碗狀碎塊的數(shù)據(jù)特點(diǎn)，本文依據(jù)點(diǎn)云占比和平滑度從碗狀碎塊的眾多分割曲面中識別出內(nèi)表面，識別算法如圖2所示。具體步驟如下：

步驟1：新建集合Ω，放入碗狀碎塊的φ個分割曲面，即Ω={S1，S2，…，Sφ};

步驟2：計(jì)算Ω中每個曲面的點(diǎn)云占比PΩ，即PΩ={P1，P2，…，Pφ}。將點(diǎn)云占比的數(shù)值從大到小排列Psort={Pmax1，Pmax2，…，Pmaxφ}，相對應(yīng)的曲面為Ωsort={Smax1，Smax2，…，Smaxφ}，則挑選出點(diǎn)云占比數(shù)值最大的兩個曲面Smax1和Smax2放入新建集合Φ中，待進(jìn)一步識別;

步驟3：分別計(jì)算集合Φ中Smax1和Smax2的平滑度數(shù)值εmax1和εmax2。如果εmax1>εmax2，則曲面?Smax1可判定為碗狀碎塊的內(nèi)表面，曲面Smax2為碗狀碎塊的外表面;否則，曲面Smax2可判定為碗狀碎塊的內(nèi)表面，曲面Smax1為碗狀碎塊的外表面。

3?實(shí)?驗(yàn)

3.1?實(shí)驗(yàn)結(jié)果

文中碗狀碎塊三維點(diǎn)云數(shù)據(jù)由Einscan-S三維激光掃描儀采集。軟件架構(gòu)為Visual?Studio?2010，VTK?5.8.0（Visualization?Toolkit，視覺化工具函式庫）和PCL1.7.2（Point?Cloud?Library，點(diǎn)云庫），在Intel?Core?i3-4160?CPU@3.60Hz處理器，4.0GB內(nèi)存的PC上運(yùn)行。實(shí)驗(yàn)選用12個不同的碗狀碎塊進(jìn)行。

首先采用區(qū)域生長算法對碗狀碎塊進(jìn)行曲面分割，圖3為碗狀碎塊的分割結(jié)果。結(jié)合上文中的圖1可以看出，碎塊01的表面由斷裂曲面、底面、內(nèi)表面和外表面組成;碎塊09的表面由斷裂曲面、原始表面、內(nèi)表面和外表面組成。同時統(tǒng)計(jì)分割后得到的曲面數(shù)量，結(jié)果如表1所示。

然后根據(jù)其點(diǎn)云占比的顯著差異，從分割曲面組中識別內(nèi)表面和外表面。圖4為碗狀碎塊各分割曲面的點(diǎn)云占比分布圖，從左至右依次是12個碎塊中各分割曲面的點(diǎn)云占比計(jì)算結(jié)果。從實(shí)驗(yàn)結(jié)果可以看出，外表面和內(nèi)表面的點(diǎn)云占比數(shù)值明顯大于其他類型的曲面?；邳c(diǎn)云占比的曲面識別方法優(yōu)勢在于算法簡單，充分利用了碗狀碎塊的厚度特性，可以準(zhǔn)確地從各分割曲面中識別出外表面和內(nèi)表面。

最后利用平滑度提取內(nèi)表面。圖5為各碎塊中內(nèi)表面和外表面的平滑度計(jì)算結(jié)果，將曲面識別結(jié)果與曲面性質(zhì)進(jìn)行比對，12個碎塊的內(nèi)表面平滑度數(shù)值均大于外表面的平滑度數(shù)值，與2.2節(jié)中的理論判斷一致，從而證明通過計(jì)算平滑度數(shù)值可以準(zhǔn)確區(qū)分碗狀碎塊的內(nèi)表面和外表面。

3.2?實(shí)驗(yàn)分析

如表2所示，將本文所提出的結(jié)合點(diǎn)云占比和平滑度的算法用于識別碗狀碎塊的內(nèi)表面，將文[9]所提出的曲面粗糙度法用于識別碗狀碎塊的斷裂曲面，從而對12個碗狀碎塊的曲面識別結(jié)果進(jìn)行進(jìn)一步分析。在部分碗狀碎塊中，底面或原始表面的凹凸程度與斷裂曲面的凹凸程度相近，同時固定閾值導(dǎo)致了曲面粗糙度法的錯誤識別，統(tǒng)計(jì)結(jié)果表明曲面粗糙度法的曲面識別準(zhǔn)確率為83.33%。而采用點(diǎn)云占比可以正確區(qū)分內(nèi)外表面和其他類型的曲面，同樣平滑度幫助本文算法成功識別12個碗狀碎塊的內(nèi)表面，因此本文算法比曲面粗糙度法的曲面識別準(zhǔn)確率提高了20.00%。另外，對比文[9]的計(jì)算式（1）～（3）和本文算法的計(jì)算公式（7），結(jié)合點(diǎn)云占比和平滑度的計(jì)算方法更加簡便，而且無需對過分割的斷裂曲面進(jìn)行合并，因此本文算法的平均運(yùn)算速度比曲面粗糙度法的平均運(yùn)算速度提高了144.63%。綜上所述，采用點(diǎn)云占比和平滑度相結(jié)合的算法在識別碗狀碎塊的內(nèi)面上更具備優(yōu)越性，該算法擁有更高的曲面識別準(zhǔn)確率和更快的運(yùn)算速度。

4?結(jié)?論

傳統(tǒng)的碎塊重組算法在曲面分割過程中容易產(chǎn)生由斷裂曲面引起的過分割問題，基于內(nèi)表面特性的碗狀碎塊重組算法可以有效避免這一問題。為了能夠準(zhǔn)確提取內(nèi)表面，本文提出一種結(jié)合點(diǎn)云占比和平滑度的碗狀碎塊內(nèi)表面識別算法。該算法首先采用區(qū)域生長算法對碗狀碎塊進(jìn)行曲面分割，然后通過計(jì)算各分割曲面的點(diǎn)云占比從眾多曲面中識別出內(nèi)表面和外表面，最后再利用平滑度區(qū)分出內(nèi)表面。實(shí)驗(yàn)結(jié)果證明該算法可以成功識別所有碗狀碎塊的內(nèi)表面，而且相比于用來識別斷裂曲面的曲面粗糙度法，本文算法在曲面識別準(zhǔn)確率上提高了20.00%，在平均運(yùn)算速度上快了144.63%。另外，結(jié)合點(diǎn)云占比和平滑度的內(nèi)表面識別算法不需要合并過分割的斷裂曲面，可以從根本上提高碎塊重組的效率，同時內(nèi)表面還擁有比斷裂曲面更豐富的顏色紋理信息，可防止碎塊重組過程中因使用單一特征所導(dǎo)致的拼接失誤。在今后的工作中應(yīng)該繼續(xù)研究不同類型碎塊的內(nèi)表面識別方法，為后續(xù)基于內(nèi)表面特性的碎塊重組與復(fù)原建立堅(jiān)實(shí)的基礎(chǔ)。

參?考?文?獻(xiàn)：

[1]?黎繼立，?何斌，?劉衛(wèi)東，?等.?南海一號出水景德鎮(zhèn)窯與龍泉窯青瓷特征的無損分析研究[J].?光譜學(xué)與光譜分析，?2016，?36（5）：?1500.

LI?Jili，?HE?Bin，?LIU?Weidong，?et?al.?Nondestructive?Analysis?of?Jingdezhen?and?Longquan?Celadon?Wares?Excavated?from?Nanhai?No.1?Shipwreck[J].?Spectroscopy?and?Spectral?Analysis，?2016，?36（5）：?1500.

[2]?EFTHYMIA?T，?IOANNIS?P.?Automatic?Color?Based?Reassembly?of?Fragmented?Images?and?Paintings[J].?IEEE?Transactions?on?Image?Processing?A?Publication?of?the?IEEE?Signal?Processing?Society，?2010，?19（3）：?680.

[3]?ZHANG?M，?CHEN?S，?SHU?Z，?et?al.?Fast?Algorithm?for?2D?Fragment?Assembly?Based?on?Partial?EMD[J].?The?Visual?Computer，?2017，?33（12）：?1601.

[4]?BROWN?B，?LAKEN?L，?DUTRE?P，?et?al.?Tools?for?Virtual?Reassembly?of?Fresco?Fragments[J].?International?Journal?of?Heritage?in?the?Digital?Era，?2014，?1（2）：?313.

[5]?高宏娟，?耿國華，?王飄.?基于關(guān)鍵點(diǎn)特征描述子的三維文物碎片重組[J].?計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，?2019，?31（3）：?393.

GAO?Hongjuan，?GENG?Guohua，?WANG?Piao.?3D?Archaeological?Fragment?Reassembly?Based?on?Feature?Descriptors?of?Key?Points[J].?Journal?of?Computer-Aided?Design?&?Computer?Graphics，?2019，?31（3）：?393.

[6]?PAPAIOANNOU?G，?THEOHARIS?T.?Fast?Fragment?Assemblage?Using?Boundary?Line?and?Surface?Matching[C]//Proceedings?of?IEEE?Computer?Society?Conference?on?Computer?Vision?and?Pattern?Recognition?Workshops.?Madison，?Wisconsin，?USA：?IEEE?Conference?on?Computer?Vision?and?Pattern?Recognition?Workshop，?2003：?1.

[7]?HUANG?Q，?SIMON?F，?GELFAND?N，?et?al.?Reassembling?Fractured?Objects?by?Geometric?Matching[J].?ACM?Transactions?on?Graphics，?2006，?25（3）：?569.

[8]?PAPAIOANNOU?G，?SCHRECK?T，?ANDREADIS?A，?et?al.?From?Reassembly?to?Object?Completion[J].?Journal?on?Computing?and?Cultural?Heritage，?2017，?10（2）：?1.

[9]?ZHAO?Fuqun，?ZHOU?Mingquan，?GENG?Guohua，?et?al.?Rigid?Blocks?Matching?Method?Based?on?Contour?Curves?and?Feature?Regions[J].?IET?Computer?Vision，?2018，?12（1）：?76.

[10]PAPAODYSSUS?C，?ARABADJIS?D，?EXARHOS?M，?et?al.?Efficient?Solution?to?the?3D?Problem?of?Automatic?Wall?Paintings?Reassembly[J].?Computers?&?Mathematics?with?Applications，?2012，?64（8）：?2712.

[11]ALTANTSETSEG?E，?MATSUYAMA?K，?KONNO?K.?Pairwise?Matching?of?3D?Fragments?Using?Fast?Fourier?Transform[J].?The?Visual?Computer，?2014，?30（6/8）：?929.

[12]ZHANG?Kang，?YU?Wuyi，?MANHEIN?M，?et?al.?3D?Fragment?Reassembly?Using?Integrated?Template?Guidance?and?Fracture-region?Matching[C]//2015?IEEE?International?Conference?on?Computer?Vision.?Santiago，?Chile：?IEEE，?2015：?2138.

[13]李群輝，?張俊祖，?耿國華，?等.?基于凹凸區(qū)域的斷裂面匹配算法[J].?計(jì)算機(jī)工程與應(yīng)用，?2016，?52（13）：?187.

LI?Qunhui，?ZHANG?Junzu，?GENG?Guohua，?et?al.?Fractured?Surfaces?Matching?Based?on?Concave-convex?Regions[J].?Computer?Engineering?and?Applications，?2016，?52（13）：?187.

[14]SON?Taegeun，?LEE?Jusung，?LIM?Jeonghun，?et?al.?Reassembly?of?Fractured?Objects?Using?Surface?Signature[J].?Visual?Computer，?2017，?15（2）：?1.

[15]李仁忠，?劉陽陽，?楊曼，?等.?基于改進(jìn)的區(qū)域生長三維點(diǎn)云分割[J].?激光與光電子學(xué)發(fā)展，?2018，?55（5）：?325.

LI?Renzhong，?LIU?Yangyang，?YANG?Man，?et?al.?Three-Dimensional?Point?Cloud?Segmentation?Algorithm?Based?on?Improved?Region?Growing[J].?Laser?&?Optoelectronics?Progress.?2018，?55（5）：?325.

[16]ZHANG?Yuhe，?GENG?Guohua，?WEI?Xiaoran，?et?al.?A?Statistical?Approach?for?Extraction?of?Feature?Lines?from?Point?Clouds[J].?Computers?&?Graphics，?2016，?56（S1）：?31.

（編輯：溫澤宇）