結合點云占比和平滑度的碗狀碎塊內表面識別算法

孫進 丁煜 王寧 習俊通 朱興龍

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

關鍵詞：點云占比;平滑度;碗狀碎塊;內表面;識別

DOI：10.15938/j.jhust.2020.03.024

中圖分類號：?TP301.6

文獻標志碼：?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?引?言

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

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

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

1?曲面分類的概述

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

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

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

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

2?內表面的識別

2.1?點云占比

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

本文采用點云占比定性分析碗狀碎塊各分割曲面的性質。這主要是因為相比于其他類型的碎塊，碗狀碎塊的厚度較薄，導致其外表面和內表面的表面積要大于其他曲面，也造成外表面和內表面的點云占比明顯大于其他曲面。點云占比可以描述碎塊中各分割曲面的大小，數值上等于曲面的空間點個數在碎塊點云中所占的百分比。假設碗狀碎塊共有φ個分割曲面，且曲面Sφ（1≤φ≤φ）的空間點個數為Gφ，則曲面Sφ的點云占比可表示為

通常根據各個曲面的點云占比，可以從碗狀碎塊的眾多分割曲面中識別出外表面和內表面。

2.2?平滑度

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

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

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

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

其中φα，β為pα的法向量與其鄰域點pβ的法向量的夾角。

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

2.3?內表面識別算法

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

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

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

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

3?實?驗

3.1?實驗結果

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

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

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

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

3.2?實驗分析

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

4?結?論

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

參?考?文?獻：

[1]?黎繼立，?何斌，?劉衛東，?等.?南海一號出水景德鎮窯與龍泉窯青瓷特征的無損分析研究[J].?光譜學與光譜分析，?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]?高宏娟，?耿國華，?王飄.?基于關鍵點特征描述子的三維文物碎片重組[J].?計算機輔助設計與圖形學學報，?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]李群輝，?張俊祖，?耿國華，?等.?基于凹凸區域的斷裂面匹配算法[J].?計算機工程與應用，?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].?激光與光電子學發展，?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.

（編輯：溫澤宇）