一种基于邻接约束的交互式文物模型复原系统

李姬俊男,耿国华,周明全,李姗姗

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



一种基于邻接约束的交互式文物模型复原系统

李姬俊男,耿国华,周明全,李姗姗

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

提出了一种基于邻接约束的计算机辅助匹配方法,该方法的重点在于关注处理流程中的用户领域经验和直觉。通过对拼合过程中几何约束的定性和定量分析,并定义一种灵活、可扩展的描述符,将碎片的所属位置限制在一个合理的空间范围内,由此确定拼合线索。在系统的设计上考虑到专家的领域知识,通过规范其操作规则,引导受损文物的重组。实验表明该系统的有效性。

文物虚拟复原;人机交互;邻接约束;几何特征可视化

虚拟复原问题是计算机图形学、模式识别、可视化技术和机器智能众多领域里一个颇具挑战的问题。20世纪初是该问题研究较为集中的时期,此后也不断有学者从事这一领域的深入研究,至今虚拟复原作为图形学落地的重要代表性技术依然是研究的热点。根据虚拟复原过程中是否有人为干涉,可分为自动化的复原方法和半自动的复原方法;在自动化复原中,根据所选取的不同特征,可分为基于几何特征的虚拟复原和非几何特征的复原。

根据对文物模型数据的不同抽象表示方法,虚拟复原技术大体上可以分为两类:一类将文物视为厚度可以忽略的薄壁碎片,针对这种数据特性设计出了基于空间轮廓曲线的拼合方案,代表性研究为茹少峰[1]提出的复原技术,其解决问题的思想是以几何特征参数对空间曲线进行编码,通过对比编码确定曲线的匹配程度,进而确定轮廓曲线所属物体的拼合关系,在他的实验中选取了微分几何量作为特征参数。这一方法是对二维平面曲线匹配的延伸,二维曲线的匹配通常应用于研究壁画等物体的拼合[5]。此外还有学者在空间曲线的编码策略和匹配策略上不断改进算法,Cristina[6]运用动态规划的思想将曲线上顶点的曲率进行编码,对比编码求得曲线的相邻关系。针对空间三维的轮廓线匹配拼接,Üçoluk[7]将离散的几何特征参数构成特征向量,把空间曲线匹配转换成简单的特征串匹配,继而完成两碎片的拼接。Kong[8]给出了曲线亲密度的定义,通过亲密度得到曲线的邻接关系,计算能量最小化将相邻的空间曲线进行对齐。Wolfson[9]等人对轮廓线先进行重采样,以采样点的曲率值进行字符编码,最后运用哈希算法进行匹配。Oxholm[10]等人综合轮廓曲线上顶点的曲率、挠率和颜色值为特征描述符,采用最长公共子串的匹配方法寻找最佳相邻碎片对,该方法能够较好地支持碎片的部分匹配。Cohen[11]提出了以轮廓曲线上顶点的矩不变量为特征,寻找特征匹配的对应关系,以距离的误差作为曲线对齐的评价标准。

另一类方法则将文物厚度作为重要的拼合线索,针对这一类型的数据特性设计出了基于断裂部位空间曲面匹配的拼合方案,代表性研究为Huang[4],其设计了一个完整的复原管线,包括断裂面的分割与识别、积分特征的提取与表示、两两对齐和多碎片拼合,并率先采用积分几何量勾勒出碎片表面的尖锐特征,从而对断裂面进行分割提取,采用基于向前搜索技术将两两断裂面进行匹配对齐,将对齐的碎片进行融合从而重组文物。决定这一算法有效与否的关键在于曲面的分割和特征的匹配。

除上述研究外,还有半自动或以人机交互为主要手段的虚拟复原方法。半自动的典型方法是“传统复原方式”,即考古学家和文物修复工作者采用的重组方法，不以数字模型为基础,而是直接用手工或者联合技术,例如摄影技术对碎片复原。此过程涉及碎片的分类、碎片类型目录的构造、碎片配对等。这一方法的问题在于,复原的好坏很大程度取决于操作者的经验,并且耗时间过长;此外还有Papaioannou[12]采用的人工智能方法处理几何特征的重组流程。采用交互手段解决虚拟复原研究的代表为Parikh[13],该方法通过从碎片集合中迭代地选取明显的可匹配部件,使用户轻易的重组出文物模型的外形,在此基础上对细小的、拼合线索不明显的碎片采用自动化方法做拼合验证;Mellado[14]提出了一种可以实时反馈的重组流程,并通过一个触摸屏用户界面设计,允许领域专家制定碎片间初始相对位置和方向。上述方法为解决复杂拼合问题提供了研究思路。

复杂拼合问题的特殊性,客观反映出了过分依赖算法求解的局限性,基于几何形状度量的方法在这类文物模型上难以得到正确的参数信息,因而对拼合阶段的算法鲁棒性提出了苛刻的要求,也促使本研究转向交互手段以寻求突破。本文提出了一种基于邻接约束的计算机辅助匹配方法,该方法的重点在于关注处理流程中的用户领域经验和直觉。

对于断裂面受损严重的情况,断裂面信息和轮廓线信息均难以保证实验结果的有效,如图1所示,由于该陶俑其他部位的碎片都已完成拼合,余下的碎片在几何外形上没有明显的拼合线索,并且对于是否存在缺失碎片的情况也是未知的,从而为拼合工作带来了极大的挑战;此时只能引入交互手段,在给出可视化特征的基础上,由领域专家确定碎片的邻接关系。

图1　几何特征失效的拼合情况Fig.1　The failure case of merging by geometric features

约束的选择通常可以指定一个或多个,例如本研究所采用的邻接约束,以及有标注过部位信息的部位约束,甚至是厚度信息、纹理信息等物理约束;约束的选择和具体的案例有关,需要根据文物的外形、材质等予以综合考虑。因而，这种描述符的优点是灵活、可扩展,限制在于所选择的约束是必须能够合理量化的;并且约束条件的选取范围应当尽可能的小,约束范围的增大可以增加系统的灵活性和描述能力,但同时也会增大实现的复杂性。

邻接约束被定义为允许用户交互地选择相邻两个碎片之间预期的拼合区域,以选取对应点为主要手段,由这些对应点确定的潜在对应区域将会被用于计算匹配实体所需的刚体变换,最终输出一个满足给定约束集合中的最优映射,图2为选取邻接约束的示意图。针对邻接约束,量化的标准为预期拼合区域的相似程度,描述该相似程度可类比部分匹配问题中的配准求解,通过定义碎片间的距离能量函数予以度量。

图2　邻接约束的选取以及对拼合结果的影响Fig.2　Select the adjacent constraints and impact on the registration results

该方法中还涉及以下定义:

碎片:数字化后的文物碎片模型,可由点云或网格数据类型表示。

约束:一条约束规则定义了两个碎片间的空间关系,这种空间关系不一定直观地反映在几何外形上,可能蕴涵在其他物理属性中。

群组:用于描述碎片拼合的层次结构,存储形式为一个碎片的集合,这些碎片可以满足约束条件下的匹配;同时群组的定义是递归的,群组可以由其他群组组成。

1　约束图构造

约束图是对邻接碎片关系的编码,参与编码的内容包括:碎片、碎片所在的群组以及它们之间的约束,通过碎片间的关联约束对不同的碎片或碎片组进行分层编码。约束图为每个碎片或组定义一个节点,每条边代表一个约束,整个图代表了一个求解序列,即约束序列应能够利用用户定义的层次结构进行重新调整并且形成合适的序列。为了确保求解序列的唯一性,设计约束图为树形结构,并以刚体变换要能够缩减样本之间距离为邻接约束条件。

图3　邻接约束下的二维约束图示例Fig.3　An example of two-dimensional constraint graph adjacency constraint

图3给出了采用约束图求解的具体步骤:

步骤1根据碎片及其约束的层次结构初始化约束图,并根据分层策略,对低层次的碎片对(即约束图中的叶节点)进行相对变换。然后分别调整碎片A与碎片B、碎片C与碎片D的相对转换使之满足约束条件,过程如图3(b)所示。

步骤2对得到的碎片构成的碎片组,重复步骤1。但是,在重组E和F的时候要注意,对它们进行转换的同时要考虑到其碎片成员。图3(c)给出了重组碎片通过相互匹配形成约束图的过程。

步骤3根据用户所定义的约束图重复上述两个步骤,使重组过程在约束图中向上扩散,直到所有的碎片被放置在最终位置,实现对象的完整重组。

步骤4删除中间层来减少全局能量消耗,最终得到全局连贯性更好的重组结果，结果见图3(d)。

2　交互式拼合过程

2.1能量最小化

对于每个邻接约束,要尽量减少两个样本之间的距离,这一过程类似几何驱动下的最近点迭代。从该角度出发,可以定义每个约束的局部能量函数,并采用模型间的加权平方距离予以度量,优化目标是使全局范围内每个约束的能量之和最小,定义为

2.2刚体变换

刚体变换的过程中通常不考虑碎片或碎片组的缩放或倾斜因素。对于给定的碎片A或碎片组G,定义刚性变换为一个3×3旋转矩阵RA和平移向量TA。能量方程(1)可这样定义

碎片A的最小化输出集是一组变换(RA,TA),但旋转矩阵的性质det(R)=1和RT=R-1不是线性的,不能保证所得的变换是刚性的,因此不能直接用它们来定义线性约束。在此采用迭代的方法寻找旋转矩阵R′A,它相似于矩阵RA。找到旋转矩阵之后对样本进行更新,从而使迭代过程达到收敛,收敛条件通过检查优化过程中剩余能量是否因为约束而增加予以判断。此外,可以采用旋转矩阵的斜对称矩阵进行编码加以优化,这样可以使每个旋转矩阵的编码变量由9减少到3。

2.3交互设计

交互式的用户界面设计对重组方法同样重要,本研究对考古专家的用户体验反馈中分析发现得出以下4点需求:

1)交互界面设计需要支持利用约束条件对碎片进行实时的拼合,并且能够清晰明确地反映出重组碎片过程中生成的层次约束图。

2)在重组过程中用户对碎片进行操作的同时还需要灵活地扩展所需约束。

3)设计的系统不仅能够通过能量最小化的方法确定每个碎片的最终位置，同时还应对拼合的结果进行评估。

4)对于漫长、复杂的碎片重组过程,任何中间状态都要能够修改和恢复。

最终设计出的界面由三大部分组成:

1)图修改区。这部分是用来定义约束图。它可以创建一个新的组或将现有的组进行分割,并且能够添加、删除和修改现有的约束。

2)工作区。这个区域允许用户在两个不同的碎片或碎片组中选择点来定义新的邻接约束。这两个工作区的主要目的是让用户能够仔细观察每一块碎片并且能够从碎片中选择出距离最接近的样本。

3)结果显示区。这个区域用来展示重建的中间过程和最终结果,即每个能量最小化的迭代结果。

由于碎片的重组过程是一个用户驱动的交互方式,在这一过程中可能会出现约束的不一致性,需要借助系统辅助来实现结果的验证。采用以下两种交互设计方法对这种不一致性进行检测:

1)约束能量可视化。在最小化过程中使用不同的颜色比例来表示约束的剩余能量,蓝色代表低能量,红色代表高能量。

2)渗透。不一致的约束会造成碎片断裂部位间的相互渗透;但与碰撞检测不同的是,领域专家所关注的不是几何变换的过程,而是用户界面上更为直观的反映。本文采用GPU深度剥离方法[14]来检测渗透,并在交互界面的约束插入区域和结果可视区域中用红色来表示渗透现象。图4显示了渗透的例子。

在实例化过程中，如果约束数量不足或者相关点位置定义不正确,都会导致不合理的碎片拼合结果,可通过适当地引入多个邻接约束,对刚体变换进行微调;但由于需要提供实时的能量可视化,邻接约束会增大运算开销。此外针对本节提出的第四点需求,将恢复当前工作所需的碎片、碎片组、样本、层次约束图以及约束条件,生成所含信息的XML文件,从而完成项目的恢复和加载工作。

图4　交互环境下邻接约束造成的模型渗透的可视化展示Fig.4　The visual display of model penetration caused by adjacency constraint in the interactive environment

3　实验结果及分析

本文设计的交互式系统在Meshlab平台上开发,采用Qt5.2版本,硬件环境为IntelCorei5CPU/4GB内存/NVIDIAGeForceGT420,工作平台的操作系统是Windows7。可以看出，采用邻接约束的方法由于引入了领域专家的经验,使得一些几何上无法辨别的碎片能够拼合在一起。

表1为采用邻接约束对无明显几何可匹配特征碎片拼合时,能量最小化阶段的参数。通过邻接约束的引入,迭代次数明显降低,这是由于能量最小化只考虑邻接约束点确定的刚体运动;从实验结果中还可以看出,随着待拼合碎片数目的提升,还需要在拼合得到群组上定义邻接约束,这一过程会显著增加迭代次数和运算开销,因而在实际操作中应尽量在碎片间定义邻接约束,避免在碎片和群组间定义。

表1邻接约束求解过程中的实验参数

Tab.1Experimental parameters in the process of solving the adjacency constraint

模型拼合碎片数/片邻接约束/个运算开销/s迭代次数/次230.0173230.0245220.01125160.167

4　总　结

本文讨论的重点在于复杂拼合问题的求解,通过对这一问题的细化，设计出了采用交互设计的一种求解方法,将自动拼合方法中的关键判定信息可视化,从而形成了一种对考古专家直观、易于接受的系统。并在此基础上制定了可扩展的约束描述符,以及能实时反映拼合阶段的层次约束图,实验表明这一设计思路是灵活且有效的。

从目前的进展来看,本文对需要采取何种约束方法给出了判定依据,但未能给出严格的定量标准,实践中还需要根据特定文物数据类型制定解决方案。

[1]茹少峰. 破碎物体复原技术与计算机辅助文物复原研究[D].西安：西北大学,2005.

[2]RAN G, DANIEL C O. Salient geometric features for partial shape matching and similarity[J]. ACM Transactions on Graphics, 2006, 25(1):130-150.

[3]POTTMANN H, WALLNER J, HUANG Q X, et al. Integral invariants for robust geometry processing[J]. Computer Aided Geometric Design, 2009, 26(1): 37-60.

[4]HUANG Q X, FlÖRY S, GELFAND N, et al. Reassembling fractured objects by geometric matching[J]. ACM Transactions on Graphics (TOG), 2006，25(3): 569-578.

[5]SHIN H, DOUMAS C, FUNKHOUSER T, et al. Analyzing fracture patterns in Theran wall paintings[C]. Proceedings of the 11th International conference on Virtual Reality, Archaeology and Cultural Heritage: Eurographics Association, 2010: 71-78.

[6]CRISTINA H, LEITO G, STOLFI J. A multi-scale method for the re-assembly of fragmented objects[C]∥BMVC. 2000:1-10.

[7]ÜÇOLUK G, HAKKI T I. Automatic reconstruction of broken 3-D surface objects[J]. Computers & Graphics, 1999, 23(4): 573-582.

[8]KONG W, KIMIA B B. On solving 2D and 3D puzzles using curve matching[C]. Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on: IEEE, 2001: 583-590.

[9]WOLFSON H J. On curve matching[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1990, 12(5): 483-489.

[10] OXHOLM G, NISHINO K. Reassembling thin artifacts of unknown geometry[C]. Proceedings of the 12th International conference on Virtual Reality, Archaeology and Cultural Heritage: Eurographics Association, 2011: 49-56.

[11] COHEN F, LIU Z, EZGI T. Virtual reconstruction of archeological vessels using expert priors and intrinsic differential geometry information[J]. Computers & Graphics, 2013, 37(1): 41-53.

[12] PAPAIOANNOU G, KARABASSI E, THEOHARIS T. Virtual archaeologist: assembling the past[J]. IEEE Computer Graphics and Applications, 2001, 21(2):40-45.

[13] PARIKH D, SUKTHANKAR R, CHEN T, et al. Feature-based part retrieval for interactive 3D reassembly[C]∥Applications of Computer Vision, 2007. WACV′07. IEEE Workshop on IEEE,2007:14.

[14] MELLADO N, REUTER P, SCHLICK C. Semi-automatic geometry-driven reassembly of fractured archeological objects[C]. Proceeding of VAST 2010. Eurographics, 2010:33-38.

(编辑李静，曹大刚)

A computer-assisted system for virtual relic assembling based on adjacency constraint

LI Ji-junnan, GENG Guo-hua, ZHOU Ming-quan, LI Shan-shan

(School of Information Science and Technology, Northwest University, Xi′an 710127， China)

A computer-assisted constraint-based methodology was propose for virtual reassembly of Cultural Heritage (CH) artworks. Instead of focusing on automatic, unassisted reassembly, the study targeted the scenarios where the reconstruction process is not only based on shape properties, but also is built over the experience and intuition of a CH expert. The purpose is therefore to design a flexible interactive system, based on the selection of a set of constraints which relates different fragments, according to the understanding and experience of the CH operator. Once the user has defined those constraints, the system searches for a suitable solution, using a global energy minimization strategy that considers simultaneously all the pieces involved in the reconstruction process. Additionally, the framework provides the possibility to work in a hierarchical way, mimicking the traditional physical procedure that archaeologists use to reassemble tangible fractured objects. The framework is designed to work even with fragments that have been severely damaged or eroded. On those data sets, automatic approaches may often fail, since the fractured regions do not contain enough geometric information to infer the correct matches.

virtual relic assembling; human-computer interaction; adjacency constraint; geometric feature visualization

2015-03-14

国家自然科学基金资助项目(61373117)

李姬俊男，男，陕西西安人，从事计算机图形学和机器视觉的研究。

TP391

ADOI：10.16152/j.cnki.xdxbzr.2016-01-010