李 康， 李 静， 孙家泽， 耿国华， 马忠玲， 刘 磊

(西北大学信息科学与技术学院，陕西 西安 710127)

一种改进的薄壁文物碎片特征轮廓线提取技术

李 康， 李 静， 孙家泽， 耿国华， 马忠玲， 刘 磊

(西北大学信息科学与技术学院，陕西 西安 710127)

针对使用一般的边界提取方法提取三维网格模型特征轮廓线不完整问题，提出一种新的薄壁文物碎片特征轮廓线提取的综合算法。区别了特征轮廓线和轮廓线的概念，引入主轮廓线和次轮廓线以及二级邻接生长曲面的概念。主轮廓线的提取使用改进的基于边重数判断的提取方法；提出次轮廓线的一种新的提取方法：首先对三维网格曲面分割并识别断裂面，然后对断裂面的二级邻接生长曲面进行曲面扫描，提取次轮廓线；最后从主轮廓线和次轮廓线中得到三维模型的特征轮廓线。使用该算法准确地提取了文物碎片的特征轮廓线，实验结果表明此方法稳定且准确。

三维薄壁文物模型；主次轮廓线；曲面分割；断裂面二级邻接生长；特征轮廓线

文物碎片三维模型的特征提取是计算机辅助文物虚拟复原研究中的关键环节，其提取准确性直接决定了碎片匹配效果。对于薄壁类的碎片来说，特征轮廓线是其最重要的特征之一，是碎片进行形状互补匹配复原[1-2]的重要依据，文物碎片三维模型的特征轮廓线精确提取方法也成为碎片拼接关键技术之一。

碎片模型的特征轮廓线不同于轮廓线。碎片模型的特征轮廓线是指文物碎片的外表面与断裂面的交线，轮廓线是指模型的曲面边界线(本文称其为主轮廓线)，如图1所示。模型曲面边界不能精确的表示文物碎片模型的边界特征，这样就不能简单地提取主轮廓线作为模型的特征轮廓线进行匹配，而应该结合断裂面和外表面的交线(次轮廓线)共同确定三维模型特征轮廓线。

图1 采集到部分断裂面的碎片模型1

吴亚东和刘玉树[3]提出了两种新的抽取三维模型轮廓线算法，先利用轮廓线的局部极值特性来获得部分轮廓边，然后利用轮廓线的连通性，通过简单的比较运算，即可获得三维模型的外部轮廓线。Decarlo等[4]使用基于视角的特征线提取方法，提取三维模型形状的细节特征，但该算法只能找到可见的外凸区域内的主观轮廓线。还有很多提取模型轮廓线的优秀算法，但都只是提取了模型的边界线，即主轮廓线，而非次轮廓线，而本文所要提取的特征轮廓线是主轮廓线和次轮廓线的组合，所以上述方法提取模型的特征轮廓线并不完整。

樊少荣等[5]提取的特征轮廓线是由内轮廓线和外轮廓线组合而成，本文借鉴这一思路展开研究，提出了一种新的提取三维模型特征轮廓线的算法。将文献[5]的内外轮廓线分别重新定义为主、次轮廓线，因为模型的边界线是轮廓线的主要组成部分，也是模型的一个明显特征，所以称其为主轮廓线更加贴切，而内轮廓线是形成特征轮廓线的一个小部分，所以称其为次轮廓线。本文算法主要步骤如下：①改进的基于边重数判断的主轮廓线提取方法；②区域生长算法对三维网格模型曲面分割，并用一种简化的边界移除法合并小的区域；③识别并提取断裂面；④用扫描曲线扫描断裂面的二级邻接生长曲面，找出曲率极值点，得出次轮廓线；⑤根据所提取的主次轮廓线构成三维文物模型的特征轮廓线。本文提取的碎片模型的特征轮廓线是与视角无关的空间轮廓曲线。

本文算法的流程图如图2所示。

图2 本文算法流程图

在主轮廓线提取部分，本文算法对文献[5]算法进行了改进。采用并行搜索的思想改进了文献[5]方法，节省了时间开销。次轮廓线的提取部分，原文需要采集大量数据以计算出断裂面和外表面的夹角合理阈值，以及包含次轮廓线的特征点集的两次提取的繁琐步骤，阈值确定的是否准确直接影响轮廓线的提取效果的好坏。而本文算法不依赖样本数据的先验知识，并且因为特征点集存在于断裂面区域，所以直接提取断裂面，一步确定包含次轮廓线的特征点集。

1 主轮廓线提取

本文算法中主轮廓线的提取结合并行搜索的思想，对基于边重数判断的主轮廓线提取算法进行了改进。采用两条线路并行搜索的策略，以相反的方向同时寻找模型的边界，两条线路搜索出的边界线共同合成模型的主轮廓线。边的重数N指这条边所属的三角形个数，N取值1或2。本文改进后的算法主要步骤如下：

(1) 找出模型中任意一条N=1的边，把这条边的2个顶点P1和P2分别入栈S1和S2；

(2) 以2个栈的栈顶的点为当前2个起点，分别按照相反方向搜索模型的边，在当前点的邻接点集中搜索与其构成的边的重数为 1的点， 把该点加入当前栈；

(3) 判断栈S1和S2的栈顶元素是否为同一个点，若是，转步骤(4)，否则转步骤(2)；

(4) 栈S1和S2中的点出栈，连接形成模型的主轮廓线。

对于图3(a)中的碎片模型1和2，使用本文算法提取其主轮廓线的结果如图3(b)所示，本文算法和文献[5]算法在提取主轮廓线部分的基本原理是一样的，所以提取的结果基本一样。文献[5]算法中用来存储边的栈是没有意义的，因为栈中所存储边的2个点已经记录在点栈，而本文算法合理利用了2个栈，分别存储2个方向搜索的边界点，既省去了文献[5]算法中冗余的空间占用，同时，并行搜索也使算法执行时间减半，提高了算法的效率。表1是算法改进前后的执行时间对比。

图3 两个碎片模型和主轮廓线

表1 算法执行时间对比

2 次轮廓线提取

若碎片模型中包含断裂面，只用边界线来描述轮廓线会给后期的匹配拼接带来困难，所以还需要提取碎片的次轮廓线。

实验发现，文献[5]算法存在很大的局限性，由于有的陶俑碎片表面较为复杂，很难计算断裂面和外表面的夹角，所以采集大量数据计算出一个平均夹角值更为困难，而且计算的夹角阈值不适用于很多兵马俑碎片，所以提取的特征轮廓线不准确，为后期碎片拼接带来困难。

本文提取次轮廓线的算法流程和所参考的方法有很大不同，因为次轮廓线点集处于碎片断裂面的边缘部分，因此本文是从碎片断裂面中提取模型的次轮廓线，算法主要分为以下4个步骤：①采用区域生长法对三维模型进行曲面分割；②合并小的分割曲面；③识别并提取模型断裂面；④对断裂面的二级邻接生长曲面进行扫描得出内轮廓线。

2.1 曲面分割并识别断裂面

本文的次轮廓线需要从碎片的断裂面提取，所以需要对碎片三维模型曲面分割，然后提取碎片的断裂面。借鉴文献[6]的网格模型分割方法，本文的曲面分割算法采用了一种基于曲率和法向量判断的区域生长法。因为碎片模型表面信息复杂并且存在噪声，所以曲面过度分割是不可避免，然后借鉴文献[7]中边界移除的思想，采用一种简化的区域合并方法将相邻块整体融合从而对分割结果进行优化处理。经过上面的分析，通过以下3个主要步骤进行断裂面的提取：

(1) 区域生长。本文算法根据对模型三角面片的几何属性值的判断，进行区域生长。计算各个三角面片的曲率值和法向量，区域生长条件是欲生长单元T和已生长区域S的曲率差值和法向量夹角都满足阈值条件。具体步骤如下：①选取模型中曲率均值最大的三角面片Ti作为种子生长点，并将Ti加入到空的生长区域Si中；②以深度优先的搜索策略生长Ti的邻接三角面片，把满足生长条件的三角面片加入到已生长区域Si中，直到区域Si不能再加入三角面片，该区域生长结束；③选取模型中还未生长且曲率极大的三角面片 Tj作为下一个种子生长点，并加入到空的区域Sj中，按照第②步的方法生长区域。重复以上步骤，最后直到所有三角面片都进行了区域生长，最终将网格模型分割成多个曲面。

(2) 区域合并。由于模型噪声和表面特性的影响，过度分割问题不可避免，经过上面的区域生长，模型曲面会被分割成过多的小区域，需要对这些区域进行合并。每次选择面积较小的区域判断是否能和其相邻区域进行合并。首先引入移除概率pij概念，即一个区域的边界Ei相对于另一条边界Ej被移除的概率，Pij公式定义如下：

其中，Length(Ei)是指边界线Ei的长度，Avg(θi)指边界线的平均二面角值。实验发现边界的平均二面角值比长度更加影响合并因素，所以取β取值为0.1。

若相邻两个区域的公共边界线的pij在各自区域都是最大的，则其满足区域合并的条件，移除这条边界线，合并两个区域，并更新合并后新的区域的信息。

以图3(a)中的兵马俑碎片模型2为例的实验，在对模型进行区域生长后，模型被分割为多个小的区域(如图4(a))，经过区域合并，最终形成理想的被分割后的曲面，曲面被合并成了较大且有意义的区域(如图4(b))。从表2中的数据可以看出，使用区域合并后，在没有改变模型三角面片数的情况下，分割的曲面个数从16减少到2，有效合并了由于曲面过度分割产生的没有意义的分割区域。

图4 碎片曲面分割结果

表2 曲面分割结果

(3) 识别断裂面。断裂面和原始面的显著区别在于断裂面较原始面粗糙，所以根据所分割面上所有顶点的法矢扰动值[8]的大小并结合区域生长得到的各个分割区域的面积值，来区分模型的断裂面和原始面。

为了避免过分依赖阈值导致算法稳定性太差的问题，并且每个碎片模型的特征各不相同，不设定曲面法矢扰动阈值来作为区分断裂面和原始面的条件。因为断裂面的法矢扰动明显大于原始面，所以根据曲面法矢扰动值的大小对比以及曲面的面积，区分碎片的断裂面和原始面。若曲面的法矢扰动明显小于其他曲面，则它为光滑的外表面，若曲面的法矢扰动明显大于其他曲面，并且该曲面的面积值小于相对其他曲面较小，则它为断裂面。

表3列出了碎片的曲面法矢扰动值和面积值，通过表中的数据可以看出曲面1为外表面，曲面2为断裂面。

表3 识别模型断裂面

2.2 断裂面的二级邻接生长

因为次轮廓线是外表面与断裂面的交线，所以次轮廓线必定位于断裂面的边界，并且是特征值变化极值点。由于模型数据噪声干扰或曲面分割阶段一些不确定影响因素，提取的断裂面边界部分有可能数据丢失，为确保断裂面的边界线信息完整无误，对断裂面进行二级邻接生长，使包含次轮廓线的特征点集位于曲面内部，从而对曲面扫描找出特征极值点。

首先阐述一个概念：二阶邻接曲面生长。设断裂面的三角面片集为 TriBreak，对断裂面的每个三角面片TriBreak[i](i=0,1,2,···,a)，找出它的邻接三角面片，若这个邻接三角面片没在 TriBreak中，则将其加入到 TriBreak，从而扩大了断裂面区域，这称为一级邻接曲面生长。对一阶邻接曲面生长得到的邻接三角面片再进行一次邻接曲面生长称为二级邻接曲面生长，新形成的曲面为TriBreakNew。

假设图 5(a)是经过曲面分割得到的断裂曲面三角面片集TriBreak，点G、A、B、C连接成的线段是已提取的部分主轮廓线。对断裂曲面进行二级邻接曲面生长后得到图 5(b)所示的新的网格曲面TriBreak New，阴影部分为新加入的三角面片，图5(b)为断裂面的二级生长曲面。

图5 曲面的二级邻接生长

2.3 曲面扫描提取次轮廓线

由于次轮廓线的特征点集存在于断裂面的二级邻接生长曲面TriBreakNew上，所以需要分析计算曲面TriBreakNew的特征值，以找出特征点集。本文采用曲面扫描的方法，即用一组平行面去切割曲面TriBreakNew，通过分析扫描数据，计算这组扫描面上的曲率极值点，可获得特征点集[9]。具体提取步骤如下：

(1) 计算曲面TriBreakNew的平均法向量a；

(2) 确定一组和a平行且互相平行的面组Sn作为扫描面；

(3) 求出扫描面组Sn和曲面TriBreakNew的交线组Ln，这组交线即为扫描线；

(4) 计算每条扫描线Li(i=1,2,···,n)上每点的曲率值，找出曲率极值点集Pi；

(5) 所有曲率极值点集Pn构成最终的次轮廓线特征点集；

(6) 对点集Pn曲线拟合，确定次轮廓线。

图 6是第一条扫描线L1的曲率情况分布直方图，在扫描线L1上的第80个点附近出现曲率极值点，这个点将是次轮廓线点集的一部分。

图6 扫描线的曲率分布情况

和文献[5]算法的原理一样，只是所扫描的曲面不同，文献[5]算法中是对所求得的包络次轮廓线特征点集的拟合曲面进行曲面扫描，而本文算法是对断裂面的二级邻接生长曲面扫描。

3 生成特征轮廓线

通过本文算法分别提取了碎片模型的主轮廓线Lm和次轮廓线Ln，而模型的特征轮廓线是外表面和断裂面的交线，所以特征轮廓线是由主次轮廓线的共同组成。对于存在断裂面的部分选取相应的次轮廓线，否则选取主轮廓线，最后将这些选取的线段连接起来构成闭合曲线Ls，即三角网格曲面模型的特征轮廓线。如图7所示，以黑色的粗线标示碎片的轮廓线，图7 (a)表示主轮廓线，图7(b)标示次轮廓线，图7(c)为通过主、次轮廓线的选取，确定最终的特征轮廓线。

图7 经主、次轮廓线连接而成的碎片特征轮廓线

4 实验结果

实验通过对陶俑碎片1和2特征轮廓线进行提取，对比了文献[5]算法和本文算法。通过实验结果可以看出，文献[5]算法不是对所有碎片都能正确提取次轮廓线。可能出现 2种情况的错误提取：①由于阈值选择的不合适，完全提取不到次轮廓线，如图8(a)提取的碎片1的次轮廓线为空，因为碎片 2断裂面和外表面的夹角较小，文献[5]算法中确定的阈值过大，导致包含次轮廓线的特征点集没有被提取到，所以最终形成的特征轮廓线也只是碎片的边界线。②有的提取到的次轮廓线有偏差，如图8(b)提取的碎片2的次轮廓线一部分是错误的，导致最终碎片的特征轮廓线还包含了错误的特征线。图9(a)和9(b)是使用本文算法提取碎片1和2的特征轮廓线，观察碎片模型可以看出提取的轮廓线是准确的。

图8 文献[5]算法实验结果图

图9 改进后的算法实验结果图

表4是所提取碎片的轮廓线包含点的个数，从表中的数据可以更清楚地看到文献[5]算法在提取有的碎片会出现提取错误的情况，例如通过文献[5]算法所提取的碎片 1次轮廓线特征点数为 0的情况。

表4 实验结果参数对比(个)

选取一个兵马俑中的一些碎片模型，分别使用文献[5]算法和本文算法提取碎片的特征轮廓线，图10列出了其中3个碎片的实验结果，第1列为3个碎片模型，第2列是使用文献[5]算法提取的碎片的特征轮廓线，第3列是使用本文算法所提取的特征轮廓线的结果。从图10可以看出对碎片1和碎片2使用文献[5]算法所提取的特征轮廓线是有错误的，而本文算法正确提取了碎片模型的特征轮廓线。碎片 3使用本文算法都正确提取了模型的特征轮廓线。

通过实验可以得出文献[5]算法不是对所有碎片模型都能正确提取特征轮廓线，而本文算法对所有碎片都正确提取特征轮廓线。碎片1

图10 文献[5]算法和本文算法提取的特征轮廓线

5 结 束 语

本文借鉴已有的特征轮廓线的形成思想，提出了一种改进的特征轮廓线提取算法，对内、外轮廓线的概念进行了重新命名定义，并分别对主、次轮廓线提取方法的都做了改进和变更。主轮廓线提取的算法合理利用了数据空间，并使算法执行时间减半。在文献[5]算法中次轮廓线提取部分过分依赖阈值的确定，稳定性太差，本文算法通过从提取的断裂面中获得特征点集提取的次轮廓线是精确并且稳定的，算法适用性强，针对薄壁文物碎片能正确地提取特征轮廓线，所以本文改进后的算法是稳定且准确的。

[1] Cohen F, Taslidere E, Liu Zexi, et al. Virtual reconstruction of archaeological vessels using expert priors ＆SurfaceMarkings [C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.San Francisco, USA: IEEE ComputerSociety, 2010: 7-14.

[2] 周术诚. 三维复杂形状拼接与破碎物体复原技术研究[D]. 西安: 西北大学, 2007．

[3] 吴亚东, 刘玉树. 三维模型轮廓线抽取算法[J]. 中国图象图形学报: A版, 2001, 6(2): 192-194.

[4] DeCarlo D, Finkelstein A, RusinkiewiczS, et al.Suggestive contours for conveyingShape [C]//Proc ofSIGGRAPH. New York: ACM Press, 2003: 848-855．

[5] 樊少荣, 茹少峰, 周明全, 等. 破碎刚体三角网格曲面模型的特征轮廓线提取方法[J]. 计算机辅助设计与图形学学报, 2005, 17(9): 2004-2007.

[6] 曹彩霞, 董洪伟, 丁金仲. 基于区域生长的网格模型分割[J]. 计算机工程与应用, 2008,44(31): 84-86.

[7] 杨 飞, 周 凡, 王若梅. 一种快速有效地基于区域增长的网格分割算法[C]//第六届全国几何设计与计算学术会议论文集, 大连, 2013.

[8] Huang Qixing, FloryS, Gelfand N, et al. Reassembling fractured objects by geometricMatching [J]. ACM Transactions on Graphics, 2006, 25(3): 569-578．

[9] Deschenes F, Ziou D. Detection of line junctions and line terminations using curvilinear features [J]. Pattern Recognition Letters, 2000, 21(6-7): 637-649.

An Improved Technique of Extracting Feature Contour from Thin-Walled Cultural Relic Fragments

Li Kang, Li Jing, Sun Jiaze, Geng Guohua, Ma Zhongling, Liu Lei
(School of InformationScience and Technology, Northwest University, Xi′anShaanxi 710127, China)

Aiming at the problem of incomplete feature contour extraction for 3DMeshModel by using GeneralMethod of detecting the edge, a new integrated algorithm of extracting feature contour from thin-walled cultural relic fragments is proposed. This paper distinguished the concept of feature contour from contour. Then it introduced theMain contours andSecondary contours, and proposed the concept of twice adjacent growth ofSurfaces. The algorithm used the improvedMethod based on edge weight number judgment to extract theMain contours; a newMethod of extracting theSecondary contours is proposed. Firstly, theSurface of 3DMesh isSegmented and the fractureSurface is recognized. Then the algorithmScans the two adjacentSurfaces of growth of fractureSurface withSurface to extract theSecondary contours. Finally, it could get the feature contour of 3DMeshModel from theMain contours andSecondary contours. It extracted the feature contour of cultural relic fragments accurately with this algorithm. The experimental resultsShow that thisMethod is efficient and accurate.

3D thin-walled cultural relic fragments;Main andSecondary contours;SurfaceSegmentation; twice adjacent growth of fractureSurface; feature contour

A

2095-302X(2015)02-0251-06

2014-10-08；定稿日期：2014-10-24

国家自然科学基金面上项目(61373117)；陕西省科技统筹创新工程计划资助项目(2011KTCG03-08)；陕西省教育厅产业化培育资助项目(2012JC24)

李 康(1980–)，男，陕西宝鸡人，讲师，博士。主要研究方向为计算机可视化技术。E-mail：854092@qq.com

TP 391