-
摘要: 针对计算机辅助文物虚拟复原中由于破损文物断裂部位边缘受损而引起的轮廓线不能充分表示断裂面几何特征的问题，提出了一种基于断裂面拓扑特征的破碎文物自动拼接算法.首先，定义碎片模型顶点显著度指标函数，提取断裂面特征点，依据Morse-Smale复形理论构建并简化断裂面的几何拓扑图；然后，通过定义基准点与0值面，从而计算目标点的对应高度差值，将拓扑图中四边形曲面构造成为能完整表示断裂面几何特征的特征描述符，并根据凹凸互补性计算初始特征四边形匹配集的误差，筛选出最优匹配集；最后，采用四元组方法计算旋转、平移矩阵，利用穷举搜索法实现碎片的精确拼接.实验结果表明，该方法针对断裂部位边缘受损的破碎文物模型可获得较满意的拼接效果.
-
关键词:
- Morse-Smale复形 /
- 刚体变换 /
- 特征描述符 /
- 四元数 /
- 穷举搜索
Abstract: In order to address the problem that the traditional break-curves methods fail to reassemble fractured fragments with incompleteness in contours, a novel automatic reassembly method is proposed using topological feature of fracture surfaces in this paper. First, the Morse-Smale complex on the fractured surfaces of fragments is constructed with curvedness as the indicator function. Then, the tangent plane is calculated through height comparison among key points and the quadrilateral descriptor is obtained by computing height difference. After that, according to the correlation between adjacent regions, optimal quadrilateral descriptors are selected. The rigid transformation matrices that maximize the contact area between surfaces are obtained by quaternion method, such that two fragments can be precisely aligned based on optimal rigid motion through exhaustive search. Experimental results show that satisfactory performance can be achieved by several uses of the algorithm on the fragments of the terracotta warriors. -
三维破碎物体的匹配与拼接是计算机图形学、模式识别、可视化技术等众多领域里一个颇具挑战的问题. 20世纪末, 随着计算机技术的快速发展, 将计算机技术引入到文物碎片的虚拟拼接过程中, 提高了文物复原的效率, 对文物保护和复原至今有着重要的意义.
文物数字化虚拟拼接技术, 根据复原过程中是否有专家参与可分为自动复原方法和交互式复原方法.其中, 现有的刚体匹配算法主要结合破损文物断裂区域的几何特征, 作为判断相邻碎片之间相似性的主要依据, 从而实现破损文物的完整拼合[1].
根据文物的厚度信息, 自动化虚拟复原技术可大致分为两类:薄壁类和非薄壁类文物碎片.早期薄壁类破损文物的虚拟拼接, 主要以提取断裂面轮廓线, 并将其映射成为二维平面曲线, 实现碎片拼合[1-6].例如Cooper等[1]通过结合碎片轮廓线及其法向, 以最大似然函数为基础进行自底向上的搜索, 完成碎片模型的自动拼合.樊少荣等[2]区分三角网格曲面模型的外表面与断裂面从而正确提取出内轮廓线和外轮廓线, 实现碎片的精确拼合. Oxholm等[3]将断裂面轮廓线上顶点的曲率、挠率以及颜色信息进行结合, 组成特征属性串, 采用最长公共子串的方法实现轮廓线间的匹配. Willi等[4]将贝叶斯分析应用在半自动拼合方法中, 该算法对断裂面光滑平整且轴对称的三维模型有很好的匹配效果, 其局限性是只能作用于有限形状的三维模型. Zhang等[5]基于模板匹配的思想确定颅骨碎片的位置关系, 再结合相邻碎片轮廓曲线实现碎片拼接. Huang等[6]通过计算模型表面顶点的积分不变量值提取碎块表面尖锐的边缘线, 基于向前搜索技术和表面一致性的约束方法实现碎片的两两拼合.空间轮廓曲线匹配方法在几何特征的数值化计算时具有简单高效的特点; 但由于其采样点数量有限, 因此这类方法对噪声较敏感并且易忽略厚度信息的部分文物碎片模型效果较差.
非薄壁类刚体匹配对文物重建、数字化遗产保护有着重要的意义[7]. Papaioannou等[8]采用Z缓冲方法, 获取三维模型断裂面投影, 计算当前位置断裂区域的"位置误差", 通过最小化误差获得最优匹配, 实现虚拟复原, 该方法适用于雕塑、纪念碑等大体积破碎模型的修复.李姬俊男等[9]基于相邻断裂面间的凹凸互补性, 通过提取约束性的特征簇完成碎片间的两两拼合. Sahner等[10]通过计算断裂区域顶点的坐标和法向, 采用层次聚类方法进行破损文物碎块之间的拼合.由于断裂面中包含了较多的特征信息, 能够准确地反映模型断裂区域的邻接关系, 因此, 针对非薄壁类文物碎片, 基于空间曲面的碎片拼合, 具有一定优势, 但针对断裂面部位受损较严重的碎块, 匹配的正确性无法保证.
因此针对破损文物断裂部位边缘受损而引起的轮廓线不能充分表示断裂面几何信息的问题, 本文基于文献[11]中的特征线提取方法, 提出一种基于Morse-Smale的断裂面拓扑几何特征的破碎刚体自动拼接方法.本文算法包括断裂面拓扑图的生成、四边形描述符的定义、匹配集的确定以及碎片拼合4个主要部分, 步骤如图 1所示.本文算法的核心思想是采用曲面四边形描述符表示断裂面几何特征信息.在传统的基于空间曲线的碎片拼合方法中, 针对断裂部位边缘受损而提取的轮廓线不精确, 错误的曲线匹配导致断裂面渗透; 传统的基于空间曲面的碎片拼合方法, 并没有考虑断裂面特征点之间的拓扑关系, 可能出现断裂面的错误配准.因此, 为了提高碎片拼合的效果, 基于Morse-Smale复形[12]本身的四边形性质及其可控性和鲁棒性, 本文借助能有效融合断裂面上凹凸信息的四边形曲面, 更好地反映空间曲面特征, 并且可精确地确定邻接碎片的匹配关系, 同时采用凹凸互补阈值方法筛选出最优匹配集, 将计算量较大的空间点对应关系转换成少数的四边形匹配, 有效地提高了刚体转换的效率, 最后采用穷举搜索的方法实现破损碎片精确拼接.
1. 拓扑图提取及相关术语
本文通过曲面四边形表示断裂面上的几何特征, 从而实现碎片拼合, 因此, 本节提取能有效融合断裂面几何特征的拓扑图.以三角网格模型为研究对象, 首先, 依据顶点的显著度指标函数, 提取关键点并分类; 然后, 采用最大角度法构建特征线; 最后, 对提取的断裂面Morse-Smale复形进行简化.
1.1 Morse-Smale理论
Morse理论主要用来研究$n$维空间内的$d$维流行$M$ $(M\subseteq {\bf R}^{n})$的形状, 通过Morse函数, 将二维流行表面分割为一系列Morse单元, 而Morse-Smale复形为这些莫斯单元的集合.其主要思想是将形状的拓扑研究同映射函数集合特性的定量分析结合起来, 通过定义特征点并判断其类型, 按照一定的寻径方法利用特征线将其连接起来, 形成关键网络或转换成其他数据模型, 从而表达流形表面的拓扑结构与形态特征, 是对特征提取和几何形状的分析, 保存其拓扑性质及形态的强大工具.
拓扑特征是对图像中区域结构形状的总体描述, 其特点是不受旋转与平移等变形影响, 描述能力强、计算速度快的优点, 可有效、准确地表示物体模型或图像的局部形状.常见的图像拓扑特征有基于骨架结构表示的目标检测算法和基于形态图表示的三维识别算法.
基于Morse函数的特征提取算法在由二维图像扩展到三模型表面时, 依据三角网格顶点的显著度度量指标(曲率值、法向量改变值等顶点属性)提取的极值点、升降线与Morse-Smale复形做为模型表面的显著特征, 避免了没有实际意义的非显著特征提取, 保证了Morse-Smale复形的拓扑完整性.
1.2 特征点提取
针对三维模型表面的网格数据, 特征提取是指采用指标函数来提取出具有明显特征的点集合.本文采用曲度函数$f\left ( v \right )$作为三角网格上各顶点的显著度指标函数[13], 定义如下:
$ \begin{equation} f\left ( v \right )= \sqrt{\frac{1}{2}\left [ k^{2}_{\max}\left ( v \right ) +k^{^{2}}_{\min}\left ( v \right )\right ]} \end{equation} $
(1) 其中, $v$为三角网格上任意一个顶点; $k^{2}_{\max}\left ( v \right )$和$k^{2}_{\min}\left ( v \right )$分别为顶点$v$的最大和最小主曲率.
采用曲度函数作为指标函数是为了将曲率绝对值最大的特征点提取出来.断裂面上曲率绝对值最大的点即为凹点、凸点和鞍点, 均是能够表示物体模型表面几何特征的点.
1.3 特征线构建
基于上节提取的断裂面特征点, 本节通过最大角度法[14]构建特征线, 构造能完整表示断裂面几何关系的拓扑图.
首先, 对提取的特征点进行判定, 并对其进行分类.定义$v_{i}\left ( i= 1, 2, \cdots, n \right )$为兵马俑碎块断裂面的三角网格上的任意顶点, 其中, $n$为三角网格数, 其所对应的显著度指标函数为$f\left ( v_{i} \right )$.若其一阶邻域点的显著度函数值均小于该顶点的显著度函数值, 则定义该顶点为极大值点; 同理, 若其一阶邻域点的显著度函数值均大于该顶点的显著度函数值, 该顶点则被定义为极小值点.若目标点的邻域中有某段连续区域内的顶点, 其指标函数值均大于目标点的函数值, 则称该段连续区域能取得的最大范围为上升区间; 若其指标函数值均小于目标点的函数值, 则称该段连续区域能取得的最大范围为下降区间.定义鞍点是同时连接两个上升区间和两个下降区间的特征点.如图 2所示, 分别对应断裂面上曲率绝对值最大的顶点, 即特征点.
基于以上分析, 本文采用最大角度法构建特征线, 构建规则如下:对任意一个鞍点都存在2条沿着指标函数值下降至极小值点和2条沿着指标函数值上升到极大值点的特征线, 计算鞍点与其邻域顶点的边, 选择上升或下降最快的点作为下一个路径点位, 构成特征线.以升弧为例, 以鞍点为出发点, 方向为鞍点上升区间中指标函数值最大的邻点所指示的方向, 直至到达极大值点.设$v_{i}$为三角网格上的任意顶点, 其方向为$\vec{q}$, 则有:
$ \begin{equation} \vec{q}=\max\frac{\left | f\left ( v_{i} \right )-f\left ( v_{j} \right ) \right |}{\left \| v_{i} -v_{j}\right \|} \end{equation} $
(2) 式中, $v_{j}$为$v_{i}$的一阶邻域点.降弧构造方式与升弧类似, 沿着最大角度反方向搜索.
1.4 拓扑简化
针对所提取的断裂面拓扑图, 本节采用注销和移动操作[15]进行简化, 从而获取准确的纯四边形拓扑图.
Morse-Smale复形中的特征点以及升弧、降弧构成初始特征集合.一般情况, 特征线会将模型表面划分成若干四边形区域, 所有四边形都是由两个鞍点, 一个极大值点和一个极小值点构成.在现实情况中, 存在一些特殊问题, 如图 3 (a)深色弧线部分生成的环状, 对某个鞍点在上升空间中寻找极大值点时, 两条升弧同时连接到一个极大值点, 使得拓扑图中出现环状回路, 以及中心区域可能出现孤立极值点, 如图 3 (c).
综上所述, 针对拓扑图中环状回路的问题, 本文采用注销的方法消除多余或者不规则的关键点.注销是一种双重边缘收缩的方法, 即去除鞍点与极值点之间连成的两条重复特征线, 其中包含所有的弧线以及这个鞍点和两个胞腔, 结果如图 3 (b).若鞍点$v$所连接的两条降弧和鞍点$x$的极小值点重复, 而特征线$\overrightarrow{xu}$, $\overrightarrow{uv}$, $\overrightarrow{vw}$均为升弧, 因此将这些升弧合并为一条升弧, 且删除重复的两条降线, 简化结果如图 3 (d).
针对初始特征集合, 某些鞍点在特征线构建过程中, 搜索下一个路径点位时可能存在微小误差, 线段间误差积累, 导致构建的初始莫尔斯复形中存在一些次要特征线, 如图 4所示, 鞍点的下一个最优路径点位可能是沿着图 4 (c)中虚线所示的方向, 而实际在构建过程中是沿着图 4 (a)或4 (b)中三角形边方向.
文献[15]中将这些次要特征线及其所连接的临界点一并删除, 但是针对模型表面的几何特征, 删除误差积累导致的次要特征线可能会造成模型表面特征的不完整性, 因此本文基于此方法进行改进, 简化规则如下: 1)通过定义特征线的显著度, 确定其重要性程度; 2)设定阈值$\delta _{0}$, 当特征线的显著度低于该阈值时, 定义为次要特征线; 3)针对次要特征线进行移动操作从而寻找最准确的特征线.
一般地, 升弧上的指标函数值与其所在区域的指标函数差值越大, 则该升弧越重要, 显著度越高; 降弧上的函数值与其所在区域的函数值差值越小, 则该降弧越重要, 显著度越高[16].因此, 本文定义特征线的显著度为该特征线与其邻接区域的平均指标函数值之差.
基于以上分析, 每个鞍点连接2条升弧和2条降弧, 本文将其合并为一条升弧$R$和一条降弧$r$, 假设降弧$r$, 其所对应的上升域为$D\left ( m^{1} \right )$和$D\left ( m^{2} \right )$; 升弧$R$, 对应的下降域为$A\left ( m^{1} \right )$和$A\left ( m^{2} \right )$.则升弧$R$相对于$A\left ( m^{i} \right )$的显著度为
$ \begin{equation} \delta \left ( R, A\left ( M^{i} \right ) \right )= \frac{\int_{R}f{\rm d}R}{{\rm length}\left ( R \right )}-\frac{\int_{A\left ( M^{i} \right )}f{\rm d}D}{{\rm area}\left ( A\left ( M^{i} \right ) \right )} \end{equation} $
(3) 其中, $i= 1, 2.$
最大角度法构建特征线过程中, 特征线方向沿着三角网格上三角形边前进.因此, 每条特征线都是由若干个特征点$p_{i}\left ( i=1, 2, \cdots, n \right )$连接而成的, 即升弧$R$是由若干首尾相连的线段组成, 如图 5所示.
因此, $R$上的积分可近似表示为
$ \begin{equation} \int_{R}f{\rm d}R\approx \sum\limits_{j}\frac{f\left ( p_{1}^{j} \right )+f\left ( p_{2}^{j} \right )}{2}\left \| p_{1}^{j} - p_{2}^{j} \right \| \end{equation} $
(4) 式中, $p_{1}^{j}$, $p_{2}^{j}$是特征线$R$上的第$j$条线段上的2个端点, 区域$A\left ( M^{i} \right )$上的积分则可近似表示为
$ \begin{equation} \int_{A\left ( M^{i} \right )}f{\rm d}D\approx \sum\limits_{k}\frac{f\left ( p_{1} ^{k}\right )+f\left ( p_{2} ^{k}\right )+f\left ( p_{3} ^{k}\right )}{3}A^{k} \end{equation} $
(5) 式中, $p_{1} ^{k}$, $p_{2} ^{k}$以及$p_{3} ^{k}$分别为区域$A\left ( M^{i} \right )$中第$k$个三角形的顶点; $A^{k}$为该三角形的面积.
通常, 对任意的特征线都有两个邻接区域, 因此会相应的有两个显著度.假设特征线$R$的2个邻域分别为$A\left ( M^{1} \right )$和$A\left ( M^{2} \right )$, 相对应的2个显著度为$\delta \left ( R, A\left ( M^{1} \right ) \right )$和$\delta \left ( R, A\left ( M^{2} \right ) \right )$, 取较小值为该特征线的整体显著度:
$ \begin{equation} \delta \left ( R \right )= \min\left \{ \delta \left ( R, A\left ( M^{1} \right ) \right ) , \delta \left ( R, A\left ( M^{2} \right ) \right )\right \} \end{equation} $
(6) 同理, 降弧$r$的两个邻接区域为$D\left ( m^{1} \right )$和$D\left ( m^{2} \right )$, 则$r$的显著度为
$ \begin{equation} \delta \left ( r, D\left ( m^{i} \right ) \right )= \frac{\int_{D\left ( m^{i} \right )}f{\rm d}A}{{\rm area}\left ( D\left ( m^{i} \right ) \right )}-\frac{\int_{r}f{\rm d}r}{{\rm length}\left ( r \right )} \end{equation} $
(7) 其中, $i=1, 2. $则该条降弧的整体显著度为
$ \begin{equation} \delta \left ( r \right )= \min\left \{ \delta \left ( r, D\left ( m^{1} \right ) \right ) , \delta \left ( r, D\left ( m^{2} \right ) \right )\right \} \end{equation} $
(8) 对任意特征线, 若其特征线显著度低于所给定的阈值, 则将该特征线进行移动操作, 即从该特征线的起始鞍点开始, 重新搜索下一个最优的路径点位, 从而获取该区域内最准确并且显著度最高的特征线, 构造断裂面上的纯四边形拓扑图.
2. 特征描述符定义及搜索
为了将拓扑图中曲面四边形构造成能够有效表示断裂面几何信息的四边形描述符, 首先, 定义基准点和0值面, 采用顶点高度差的方法对曲面四边形进行编码, 获得四边形描述符; 然后, 通过凹凸互补误差筛选出最优四边形匹配集.
2.1 四边形定义
断裂面上的Morse-Smale复形, 由多个四边形曲面构成, 这些曲面四边形将断裂面进行剖分, 四边形本身具有各向异性的特点, 使得四边形网格更易与模型特征对应, 因此本文将断裂面上的曲面四边形作为特征描述符, 以相邻碎片断裂面间的凹凸特性为基准进行碎块拼合.设待匹配的两个断裂面分别为$\varphi _{A}$和$\varphi _{B}$, 定义$\varphi _{A}$为源面, $\varphi _{B}$为目标面, 对于源面$\varphi _{A}$上的Morse-Smale复形中的任意曲面四边形, 假设两个鞍点分别为$s_{1}$和$s_{2}$, 极大值为$M_{1}$, 极小值为$m_{1}$.
如图 6所示, 设以极大值点$M_{1}$所在的切平面$l_{0}$为0值面, 定义极大值点$M_{1}$为基准点, 鞍点$s_{1}$、$s_{2}$, 极小值点$m_{1}$为目标点.用$h_{1}$表示鞍点$s_{1}$到该切平面的垂直距离, 极小值点$m_{1}$到该切平面的垂直距离为$h_{2}$, 鞍点$s_{2}$的对应距离为$h_{3}$, 极大值点的对应距离为$h_{0}$, 将该高度差值作为每个顶点的属性值, 并按照一定规则进行编码.
编码规则:本文以源面$\varphi _{A}$上任意曲面四边形为例, 以四边形中极大值点开始, 顺时针编码, 如图 6所示的四边形中, 极大值点$M_{1}$为基准点, 则定义$h_{0}^{A}= 0$; 依次鞍点$s_{1}$、极小值点$m_{1}$、鞍点$s_{2}$所对应的属性值为$h_{1}^{A}$, $h_{2}^{A}$, $h_{3}^{A}$, 则该四边形的一个属性编码为$H\left( s_{i}^{A} \right)= \left(h_{0}^{A}, h_{1}^{A}, h_{2}^{A}, h_{3}^{A} \right)$.
类似地, 目标面$\varphi _{B}$在选取基准点时, 根据匹配碎块断裂面的凹凸互补性, 基准点选择特征四边形中的极小值点$m_{1}$, 以其切平面作为0值面, 然后求得其余三个目标点到0直面的垂直距离$h_{i}^{B}$, 以同一编码规则获得任意特征四边形的属性编码$H\left (s_{i}^{B} \right)$.
2.2 最优匹配集搜索
基于本文定义的四边形属性, 从破损的兵马俑断裂面上提取出特征四边形集, 如图 7所示, 但由于特征四边形的数目较多, 断裂面$\varphi _{A}$和$\varphi _{B}$之间的匹配关系会比较复杂.因此, 本文设置凹凸互补阈值条件, 减少误匹配四边形集合个数, 求取少量的最优匹配集合.
假设$\varphi _{A}$和$\varphi _{B}$为两个待匹配的断裂面, $S_{A}= \left \{ s_{i}^{A} |s_{i}^{A}\in R^{3}, i= 1, 2, \cdots, n\right \}$和$S_{B}= \left \{ s_{i}^{B} |s_{i}^{B}\in R^{3}, i= 1, 2, \cdots, n\right \}$分别为$\varphi _{A}$和$\varphi _{B}$上的初始特征四边形集合.设$s_{i}^{A}$和$s_{i}^{B}$是待匹配的两个断裂面$\varphi _{A}$和$\varphi _{B}$上相对应的可匹配特征四边形, 则定义凹凸互补误差为
$ \begin{equation} \varepsilon= \sqrt{\left \| s_{i}^{A}-s_{i}^{B} \right \|}, \quad\varepsilon > 0 \end{equation} $
(9) 假设四边形$s_{1}^{A}$为断裂面$\varphi _{A}$上的任意特征曲面四边形, 属性编码如下:
$ \begin{equation} s_{1}^{A}= \left ( h_{0}^{A}, h_{1}^{A}, h_{2}^{A}, h_{3}^{A} \right ) \end{equation} $
(10) 相对应的, 断裂面$\varphi _{B}$上对应的特征四边形$s_{1}^{B}$为
$ \begin{equation} s_{1}^{B}= \left ( h_{0}^{B}, h_{1}^{B}, h_{2}^{B}, h_{3}^{B} \right ) \end{equation} $
(11) 则凹凸互补误差公式为
$ \begin{equation} \varepsilon \left ( s_{1}^{A}, s_{i}^{B} \right )=\sqrt{ x_{1}^{2}+ x_{2}^{2}+ x_{3}^{2}+ x_{4}^{2}} \end{equation} $
(12) 其中, $x_{1}= h_{0}^{A}-h_{0}^{B}$, $x_{2}= h_{1}^{A}-h_{2}^{B}$, $x_{3}= h_{3}^{A}-h_{3}^{B}$, $x_{4}= h_{2}^{A}-h_{1}^{B}$.当$\varepsilon $越接近0, 表示该对特征四边形的匹配度越高.因此, 设定凹凸互补阈值$\varepsilon_{0}> 0$, 对四边形$s_{1}^{A}$, 若在断裂面$\varphi _{B}$上满足$\varepsilon \left ( s_{1}^{A}, s_{i}^{B} \right )< \varepsilon _{0}$的特征四边形存在$m$个, 则取最优匹配对$\left ( s_{1}^{A}, s_{1}^{B} \right )=\min\left \{ \varepsilon \left ( s_{1}^{A}, s_{i}^{B} \right )< \varepsilon _{0}|i= 0, 1, 2, \cdots, m \right \}$, 并将该最优匹配对$\left ( s_{1}^{A}, s_{1}^{B} \right )$加入到最优匹配集$s= \left \{ \left ( s_{i}^{A}, s_{i}^{B} \right )|s_{i}^{A}\in \varphi _{A}, s_{i}^{B}\in \varphi _{B}, i\in \left ( 1, m \right )\right \}$; 否则, 删除该匹配对.本文通过凹凸互补阈值方法约束特征四边形, 筛选出匹配度较高的匹配集, 提高断裂面的匹配精度并且降低刚体转换的复杂性. 图 8是初始特征匹配到最优特征集匹配的结果对比图.
3. 刚体变换
对特征四边形进行初步筛选后, 确定了待匹配断裂面上的最优特征集合$S_{A}^{'}$和$S_{B}^{'}$, 以及由此构成的最优匹配集$S= \left \{ \left ( s_{i}^{A}, s_{i}^{B} \right )|s_{i}^{A}\in \varphi _{A}, s_{i}^{B}\in \varphi _{B}, i=1, 2, \cdots, m \right \}$, 但由于两个碎片之间的方向与位置均不同, 为了能将碎块完整的拼合, 需根据两个四边形匹配集计算出对齐碎片的旋转矩阵$R$和平移矩阵$T$[17].
基于特征四边形区域的质心坐标, 采用四元组方法[18]求解出最优匹配集中的3组质心不共线特征四边形匹配对的旋转矩阵$R$和平移矩阵$T$, 并采用穷举搜索法[19]筛选出匹配正确率较高的刚体变换, 实现碎片的精确拼合, 算法步骤如下:
步骤1. 设任意特征四边形$S$的4个顶点为$\left \{ p_{1}, p_{2}, p_{3}, p_{4} \right \}$, 点$p_{i}$的三维坐标为$\left ( x_{i}, y_{i}, z_{i} \right )$, 定义$S$的质心为$\bar{p}$.
步骤2. 根据三角形理论, 从匹配集中筛选出所有满足该条件且质心不共线的3组特征四边形对, 构成集合$M$: $M= \left \{ \left ( s_{i}^{A}, s_{i}^{B} \right ), \left ( s_{j}^{A}, s_{j}^{B} \right ), \left ( s_{k}^{A}, s_{k}^{B} \right ) |i, j, k\in \left [0, m \right]\right \}$, 其中, $i\neq j\neq k$, 设$M$中的元素个数为$e$个.
步骤3. 从上述集合$M$中选取任意一组特征四边形对, 采用四元组法计算出断裂面$\varphi _{A}$和$\varphi _{B}$之间的刚体变换矩阵$R$和$T$, 遍历集合$M$中所有的特征对元素, 求得刚体变换数组$D$.
步骤4. 计算$D\left [t \right], t=1, \cdots, e$的匹配正确率; $c$为正确匹配对个数, 初值设为0;集合$S$中任意的特征四边形对经过$D\left [t \right]$变换之后, 若满足$\left | s_{i}^{A}-\left ( s_{i}^{B}R_{t}+T_{t} \right ) \right |< \sigma _{1}, \sigma _{1}> 0$, 则表明该特征四边形对匹配正确, $c= c+1$, 否则为错误匹配; 遍历集合$S$可求出$D\left [t \right]$的匹配正确率$q= {c}/{m}$; 遍历整个数组$D\left [e \right]$, 计算所有特征对刚体变换的正确匹配率.
步骤5. 选取匹配正确率最高的刚体变换, 完成待拼接碎片的精确对齐.
4. 实验结果与分析
为检验本文算法的有效性, 以秦始皇陵1号坑出土的部分兵马俑碎片网格模型作为实验数据.本文实验采用Visual C++ (Visual studio 2010)和OpenGL编程, 在Intel Core i7-3770 CPU/3.4 GHz, 4 GB内存的PC机上实现.实验阈值均是通过经验值以及数据统计获取的, $\delta _{0}= 0.02$, $\varepsilon _{0}= 5.0$ mm, $\sigma _{1}= 2.0$ mm, 碎片在断裂处均存在边界受损, 几何特征缺失现象.
4.1 本文算法结果
图 9~11所示为G10-26号俑、G10-19号俑和G10-23号俑采用本文算法在部分邻接碎片上的实验结果, 可以看出, 本文算法在边缘受损的碎片模型上可取得较好的拼合结果. 图 12~14所示为本文算法在一组整俑上的拼接结果, 实验结果表明, 本文算法在断裂部位边缘受损的整俑模型上, 如图 12中矩形框标注的有小部分缺失的碎片, 仍可取得较好的拼合结果.本文实验数据采用的兵马俑模型均为陶俑模型, 碎片断裂面具有一定厚度, 碎片数量较多并且网格数据总量较大, 因此在邻接碎片的搜索时复杂度较高.实验数据如表 1所示, 邻接碎片在断裂面提取的特征四边形随碎片网格数增加, 碎片的数量决定了邻接碎片的断裂面个数, 其对特征四边形个数也有直接的影响; 由表 1中数据可得, 本文算法可取得较高的匹配精度.
图 9 G10-26号俑部分邻接碎片拼接结果Fig. 9 Reassembly results of some adjacent fragments of Warriors G10-26
图 10 G10-19号俑部分邻接碎片拼接结果Fig. 10 Reassembly results of some adjacent fragments of Warriors G10-19
图 11 G10-23号俑部分邻接碎片拼接结果Fig. 11 Reassembly results of some adjacent fragments of Warriors G10-23
图 12 G10-18号俑部分邻接碎片拼接结果Fig. 12 Reassembly results of some adjacent fragments of Warriors G10-18
图 13 G10-36号俑部分邻接碎片拼接结果Fig. 13 Reassembly results of some adjacent fragments of Warriors G10-36
图 14 G10-22号俑部分邻接碎片拼接结果Fig. 14 Reassembly results of some adjacent fragments of Warriors G10-22表 1 兵马俑碎片实验数据Table 1 Experimental datas of the Terracotta Army fragments编号 碎片数量 网格总数 特征四边形总数 匹配精度 G10-18 7 674 477 253 0.924 G10-26 2 38 602 32 0.929 G10-36 6 591 641 191 0.961 G10-22 5 451 750 103 0.975 G10-19 3 94 276 93 0.924 G10-23 3 12 147 84 0.896 本文将图 7中的碎片裁剪为薄壁模型后, 断裂面上的特征四边形提取结果示意图如图 15, 有效特征四边形定义为四边均处于碎片模型断裂面上的四边形, 如图 15中矩形框标注所示.由于薄壁模型断裂面上的特征点数量较少, 提取的有效特征四边形数量不足从而无法完整表示断裂面的几何结构, 造成特征匹配不准确的问题, 从而影响后续邻接碎片位置的判断.因此, 本文算法针对薄壁类文物碎片模型, 拼合效果较差.
4.2 算法运行时间
本文算法针对成组的兵马俑碎片拼合时间如表 2所示, 其中, 断裂面曲面四边形特征提取为T1, 本文每次提取2个碎片的断裂面四边形特征; 特征匹配集获取为T2, 同理, 每次获取2个碎片的特征匹配集; T3为碎片拼合.实验数据表明, 随着碎片数据的增加, 运行时间也会随之增加, 这是因为断裂面上四边形特征描述符提取为本文算法最耗时的部分, 需要遍历断裂面网格上的所有顶点.
表 2 本文算法运行时间Table 2 Execute times of the proposed algorithm编号 T1 (s) T2 (s) T3 (s) 总时间(s) G10-18 68.461 17.436 7.246 93.143 G10-36 53.534 16.990 6.128 76.652 G10-22 30.157 12.631 4.021 46.809 G10-26 7.065 3.518 0.981 11.564 G10-19 17.913 6.349 2.065 26.327 G10-23 19.254 7.521 2.731 29.506 4.3 对比实验结果
图 16所示分别为采用基于形态图方法[20]及基于断裂面几何特征方法[7]的碎片拼合结果, 选取3组碎片模型为实验数据, 分别为: G10-18号俑, G10-19号俑及G10-36号俑部分邻接碎片.该3组邻接碎片具有不同的特点: G10-18号俑碎片模型断裂部位边缘受损较少; G10-19号俑碎片模型断裂部位边缘受损较严重且断裂面存在缺损; G10-36号俑邻接碎片断裂部位面积较大, 碎片存在缺失.
若两个断裂面可实现正确匹配, 那么当两个碎片完成精确配准之后, 相邻的两个断裂面之间不应该发生明显的碰撞, 存在缝隙过大以及相互重叠交错[21]. 图 16 (a)所示为G10-18号俑碎片采用文献[20]中提出的基于形态图方法的拼合结果, 将碎片模型转换成点云数据, 可看出, 当碎片的断裂处存在缺损时, 基于断裂面出轮廓线的拼合方法会出现相互渗透的现象, 如图 16 (a)中矩形框中标注所示, 难以达到较好的拼合结果; 图 16 (b)中所示为采用文献[7]的基于断裂面特征簇的拼合方法对G10-19号俑部分碎片的拼合结果, 由于碎片断裂面存在缺损, 则导致几何信息无法有效表示断裂面结构, 造成断裂面相互渗透现象, 如图 16 (b)中矩形框标注所示; 当碎片存在小部分的缺损时, 则会造成不准确的位置匹配, 出现碎片表面纹饰信息不连续的现象, 如图 16 (c)所示.
实验结果表明, 相较于其他拓扑特征的拼合方法和基于断裂面几何特征的拼合方法, 本文算法通过融合断裂面几何特征的四边形曲面, 增强了特征描述符的约束性, 能够准确有效地判断碎片的邻接位置, 针对断裂面边缘受损的碎片具有更好的拼合效果.
5. 结语
针对破损文物断裂部位边缘受损而引起的轮廓线不能充分表示断裂面几何特征的问题, 本文提出了一种基于Morse-Smale的断裂面拓扑特征的破损文物自动拼接算法.该算法将断裂面上特征点的曲度函数作为特征检测算法, 根据断裂面几何特征提取特征点; 采用最大角度法对特征点进行特征线构建, 并计算特征线重要度简化拓扑图, 得到断裂面的纯四边形拓扑图; 将拓扑图中四边形曲面构造成为能有效表示断裂面集合特征的描述符, 弥补了传统方法反映局部特征的不足, 提高了匹配的精度和效率, 同时扩展了匹配算法的使用范围.本文算法需要较为精确地识别出碎片的断裂面, 解决薄壁类破损碎片断裂面特征平滑, 无法取得精确地拼合结果的难题.
由于本文算法采用了拓扑图四边形为特征描述符, 因此在提取特征描述符时较耗时, 寻找一种更加鲁棒、高效地特征提取算法以减少计算量, 将是我们下一步工作的重点.
-
图 9 G10-26号俑部分邻接碎片拼接结果
Fig. 9 Reassembly results of some adjacent fragments of Warriors G10-26
图 10 G10-19号俑部分邻接碎片拼接结果
Fig. 10 Reassembly results of some adjacent fragments of Warriors G10-19
图 11 G10-23号俑部分邻接碎片拼接结果
Fig. 11 Reassembly results of some adjacent fragments of Warriors G10-23
图 12 G10-18号俑部分邻接碎片拼接结果
Fig. 12 Reassembly results of some adjacent fragments of Warriors G10-18
图 13 G10-36号俑部分邻接碎片拼接结果
Fig. 13 Reassembly results of some adjacent fragments of Warriors G10-36
图 14 G10-22号俑部分邻接碎片拼接结果
Fig. 14 Reassembly results of some adjacent fragments of Warriors G10-22
表 1 兵马俑碎片实验数据
Table 1 Experimental datas of the Terracotta Army fragments
编号 碎片数量 网格总数 特征四边形总数 匹配精度 G10-18 7 674 477 253 0.924 G10-26 2 38 602 32 0.929 G10-36 6 591 641 191 0.961 G10-22 5 451 750 103 0.975 G10-19 3 94 276 93 0.924 G10-23 3 12 147 84 0.896 
下载: 导出CSV
表 2 本文算法运行时间
Table 2 Execute times of the proposed algorithm
编号 T1 (s) T2 (s) T3 (s) 总时间(s) G10-18 68.461 17.436 7.246 93.143 G10-36 53.534 16.990 6.128 76.652 G10-22 30.157 12.631 4.021 46.809 G10-26 7.065 3.518 0.981 11.564 G10-19 17.913 6.349 2.065 26.327 G10-23 19.254 7.521 2.731 29.506
下载: 导出CSV
-
[1] Cooper D B, Willis A, Andrews S, Baker J, Cao Y, Han D J, et al. Bayesian pot-assembly from fragments as problems in perceptual-grouping and geometric-learning. In: Proceedings of the 16th International Conference on Pattern Recognition (ICPR'02). Washington, D. C., USA: IEEE, 2002, 3: Article No. 30297 [2] 樊少荣, 茹少峰, 周明全, 耿国华.破碎刚体三角网格曲面模型的特征轮廓线提取方法.计算机辅助设计与图形学学报, 2005, 17(9):2003-2009 doi: 10.3321/j.issn:1003-9775.2005.09.018Fan Shao-Rong, Ru Shao-Feng, Zhou Ming-Quan, Geng Guo-Hua. A method of extracting feature contour from triangular mesh surface model of fractured solid. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(9):2003-2009 doi: 10.3321/j.issn:1003-9775.2005.09.018 [3] Oxholm G, Nishino K. Reassembling thin artifacts of unknown geometry. In: Proceedings of the 12th International Conference on Virtual Reality, Archaeology and Cultural Heritage. Prato, Italy: ACM, 2011. 49-56 [4] Willis A R, Cooper D B. Bayesian assembly of 3D axially symmetric shapes from fragments. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, D. C., USA: IEEE, 2004, 1: I-82-I-89 [5] Zhang K, Yu W Y, Manhein M, Waggenspack W, Li X. 3D fragment reassembly using integrated template guidance and fracture-region matching. In: Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV). Santiago, Chile: IEEE, 2015. 2138-2146 [6] Huang Q X, Flöry S, Gelfand N, Hofer M, Pottmann H. Reassembling fractured objects by geometric matching. ACM Transactions on Graphics, 2006, 25(3):569-578 doi: 10.1145/1141911 [7] Winkelbach S, Rilk M, Schönfelder C, Wahl F M. Fast random sample matching of 3D fragments. In: Proceedings of the 26th DAGM Symposium on Pattern Recognition. Tübingen, Germany: Springer, 2004. 129-136 [8] Papaioannou G, Karabassi E A, Theoharis T. Virtual archaeologist:assembling the past. Computer Graphics and Applications, 2001, 21(2):53-59 doi: 10.1109/38.909015 [9] 李姬俊男, 耿国华, 周明全, 康馨月.文物碎块虚拟拼接中的表面特征优化.计算机辅助设计与图形学学报, 2014, 26(12):2149-2154 http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb201412007Li Ji-Jun-Nan, Geng Guo-Hua, Zhou Ming-Quan, Kang Xin-Yue. Surface feature optimization for virtual matching of relic fragments. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(12):2149-2154 http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb201412007 [10] Sahner J, Weber B, Prohaska S, Lamecker H. Extraction of feature lines on surface meshes based on discrete Morse theory. In: Proceedings of the 10th Joint Eurographics/IEEE-VGTC Conference on Visualization. Eindhoven, The Netherlands: IEEE, 2008. 735-742 [11] 邱彦杰, 周雄辉, 柳伟.基于Morse-Smale复形的三角网格特征线提取.上海交通大学学报, 2010, 44(8):1074-1078 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK201001992212Qiu Yan-Jie, Zhou Xiong-Hui, Liu Wei. Feature lines extraction from triangular mesh based on Morse-Smale complex. Journal of Shanghai Jiaotong University, 2010, 44(8):1074-1078 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK201001992212 [12] Shivashankar N, Natarajan V. Parallel computation of 3D Morse-Smale complexes. Computer Graphics Forum, 2012, 31(3):965-974 https://www.researchgate.net/publication/51866285_Parallel_Computation_of_3D_Morse-Smale_Complexes [13] Winkelbach S, Wahl F M. Pairwise matching of 3D fragments using cluster trees. International Journal of Computer Vision, 2008, 78(1):1-13 doi: 10.1007/s11263-007-0121-5 [14] 张春亢, 赵学胜, 王洪斌.采用Morse理论的小尺度地形特征提取方法.测绘科学技术学报, 2015, 32(3):266-270 doi: 10.3969/j.issn.1673-6338.2015.03.011Zhang Chun-Kang, Zhao Xue-Sheng, Wang Hong-Bin. Feature points extraction of small-scale terrain based on Morse theory. Journal of Geomatics Science and Technology, 2015, 32(3):266-270 doi: 10.3969/j.issn.1673-6338.2015.03.011 [15] Gyulassy A, Bhatia H, Bremer P T, Pascucci V. Computing accurate Morse-Smale complexes from gradient vector fields. Topological and Statistical Methods for Complex Data: Tackling Large-Scale, High-Dimensional, and Multivariate Data Spaces. Berlin Heidelberg, Germany: Springer, 2015. 205-218 [16] 张春亢. 基于Morse理论的三角网格特征提取及简化研究[博士学位论文], 中国矿业大学(北京), 中国, 2016. http://cdmd.cnki.com.cn/Article/CDMD-11413-1016062794.htmZhang Chun-Kang. Research on features extraction and simplification from triangle mesh based on Morse theory[Ph. D. dissertation], China University of Mining & Technology, Beijing, China, 2016. http://cdmd.cnki.com.cn/Article/CDMD-11413-1016062794.htm [17] Andreadis A, Gregor R, Sipiran I, Mavridis P, Papaioannou G, Schreck T. Fractured 3D object restoration and completion. In: Proceedings of ACM SIGGRAPH 2015 Posters. Los Angeles, California, USA: ACM, 2015. Article No. 74 [18] 江刚武, 王净, 张锐.基于单位四元数的绝对定向直接解法.测绘科学技术学报, 2007, 24(3):193-195, 199 doi: 10.3969/j.issn.1673-6338.2007.03.011Jiang Gang-Wu, Wang Jing, Zhang Rui. A close-form solution of absolute orientation using unit quaternions. Journal of Zhengzhou Institute of Surveying & Mapping, 2007, 24(3):193-195, 199 doi: 10.3969/j.issn.1673-6338.2007.03.011 [19] 李姗姗, 耿国华, 周明全, 李姬俊男.基于表面邻接约束的交互式文物碎片重组.计算机辅助设计与图形学学报, 2016, 28(6):924-931 doi: 10.3969/j.issn.1003-9775.2016.06.007Li Shan-Shan, Geng Guo-Hua, Zhou Ming-Quan, Li Ji-Jun-Nan. Interactive reassembly of fractured fragments based on surface adjacency constraint. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(6):924-931 doi: 10.3969/j.issn.1003-9775.2016.06.007 [20] 李群辉, 张俊组, 耿国华, 周明全.以轮廓曲线为特征的断裂面匹配.西安交通大学学报, 2016, 50(9):105-110 http://d.old.wanfangdata.com.cn/Periodical/xajtdxxb201609017Li Qun-Hui, Zhang Jun-Zu, Geng Guo-Hua, Zhou Ming-Quan. Fracture surfaces matching based on contour curve. Journal of Xi'an JiaoTong University, 2016, 50(9):105-110 http://d.old.wanfangdata.com.cn/Periodical/xajtdxxb201609017 [21] 李群辉. 基于断裂面匹配的破碎刚体复原研究[博士学位论文], 西北大学, 中国, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10697-1013253357.htmLi Qun-Hui. Research on fractured slid recovery based on bracture surfaces matching[Ph. D. dissertation], Northwest University, China, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10697-1013253357.htm 期刊类型引用(11)
1. 刘鹏欢，周强，王莹，朱建锋，罗宏杰，王露，王甜. 基于凹凸性和转向角的古陶瓷碎片二次匹配算法. 计算机工程. 2024(09): 356-366 . 
百度学术2. 郭子旭，谢晓尧，刘嵩，刘旭斌. 基于快速点直方图和深度学习的断裂面分割算法. 信息技术与信息化. 2024(12): 136-141 . 百度学术3. 郑玉彤，李雪龙，殷梓轩，高歌，翁彧. 多特征融合的敦煌古籍残片自动缀合. 中国图象图形学报. 2023(08): 2330-2342 . 百度学术4. 吉雨田，张春亢，尹耀. 分段线性Morse理论下的地表拓扑特征提取与简化. 激光与光电子学进展. 2022(08): 318-324 . 百度学术5. 耿国华，冯龙，李康，周明全，王小凤. 秦陵文物数字化及虚拟复原研究综述. 西北大学学报(自然科学版). 2021(05): 710-721 . 百度学术6. 周强，张敏，李巍，ANVARJON NORMURODOV，杜丹阳. 基于点云数据的古陶瓷碎片边缘轮廓提取技术. 陕西科技大学学报. 2021(06): 174-181 . 百度学术7. 刘晓宁，狄宏璋，杨稳，林芃樾，王世雄. 基于SURF特征描述符和杰卡德距离的文物碎片拼接. 光学精密工程. 2020(04): 963-972 . 百度学术8. 胡佳贝，周蓬勃，耿国华，陈小雪，杨稳，王飘. 基于生成树代价和和几何约束的文物碎片自动重组方法. 自动化学报. 2020(05): 946-956 . 本站查看9. 张春亢，李红梅，张霞. 非对偶性点云拓扑特征识别与过渡特征保护. 光学精密工程. 2020(10): 2301-2310 . 百度学术10. 高宏娟，耿国华，王飘. 基于关键点特征描述子的三维文物碎片重组. 计算机辅助设计与图形学学报. 2019(03): 393-399 . 百度学术11. 陈华伟，伍权，徐卫平，余泽云. 基于Laplace调和方程的网格重构算法. 河北科技大学学报. 2019(03): 199-207 . 百度学术其他类型引用(14)
-
下载:
计量
- 文章访问数: 2671
- HTML全文浏览量: 365
- PDF下载量: 597
- 被引次数: 25
