 |
| S—起始点；E—终止点；N—连接点.图 1 小篆与隶书的字“止”及其属性关系图Fig. 1 “Zhi” and its attributed-relation graph in seal script and clerical script |
| 图选项 |
1) 两个相邻特征点之间的笔段为图的一条边,边可以根据它的方向分为横、竖、撇、捺4种类型.这4种类型普遍存在于汉字的各个阶段当中,并且有自己的方向(0°,90°,135°和45°).这里使用线性回归计算笔段方向,并判断笔段类型,允许有±15°的差异.笔段分类后骨架变为一个有向无环图.2) 特征点作为图的顶点,它可以分为3种类型.入度为0,出度不为0的顶点叫做起始点;入度不为0,出度为0的点叫做终止点;既不为起始点也不为终止点的点称作连接点. 1.2 骨架图匹配 通过建立起始点和终止点的对应关系来匹配2个图模型,因为这些点一般都是本文书写时的起点和终点,而连接点并没有参与匹配.接下来先介绍匹配中的相似度度量方式.假设有I个起始点和J个终止点在图G中,I′个起始点和J′个终止点在图G′中.ui(i=1,2,…,I),vi′(i′=1,2,…,I′)分别表示2个模型中的起始点,uj(j=I+1,I+2,…,I+J),vj′(j′=I′+1,I′+2,…,I′+J′)分别表示2个模型中的终止点.同类点间的相似度用欧式距离表示,公式如下:
其中x,y为归一化到[0,1]后的坐标值.一个起始点到一个终止点的最短路径由p(ui,uj)表示,本文记录p(ui,uj)中的笔画类型(横、竖、撇、捺)和顺序作为笔画路径ps(ui,uj),如图 2所示.那么任意2个路径的相似度表示为
式中,LLCS为2个序列的最大公共子序列的长度;l为序列的长度.
 |
| 图 2 起始点与终止点间的笔画路径Fig. 2 Stroke-paths between startpoints and endpoints |
| 图选项 |
由以上2个相似度方程,可以将对应问题转化为求解最优匹配问题.先假设一个匹配矩阵 M ,mii’∈{0,1},mii′=1表示图G中的ui匹配到G′中的vi′,mii′=0则表示不匹配.并且 M 的纵向之和与横向之和都为1,确保G与G′之间的匹配一一对应.相似度方程可以写为
式中c和d分别用式(1)和式(2)计算.目标是寻找最优匹配,最大化该方程,使用双分解方法[15]求解.对应结果在图 3中显示,图 3(a)的结果可以由本文的算法直接得到,图 3(b)的结果需要通过2.2节的步骤得到.
 |
| 图 3 小篆与隶书笔画的对应结果Fig. 3 Correspondence results between seal script and clerical script |
| 图选项 |
2 变形动画 本节将介绍使用骨架图匹配进行汉字变形的具体方法.本文的方法主要包括以下3个步骤:①部件分割.输入待变形的2个汉字,用半自动的方式分割和匹配部件.②笔画对应.对部件进行骨架提取,拆分笔段后使用骨架图匹配算法进行匹配,产生顶点和笔段的对应关系.③形状插值.根据对应结果对2个汉字同构三角化,并使用尽可能刚性的形状插值产生动画. 2.1 部件分割除了独体字外,汉字通常由2个以上部件组成.比如“堤”字有“土”字和“是”组成,如图 4所示.因此有必要首先分析汉字找到部件的结构特点.为了获取对应的部件使用最小包围盒去分割输入的不同时代汉字,并根据最小包围盒之间的相对位置构造汉字的块模型[16],如图 5所示.之后,在块模型中位于相同位置的部件就是匹配的部件.然而由于部件间可能会有交叉、粘连等情况出现,上述方法并不一定能产生正确的匹配结果.因此使用变形模版[17]自动分割部件,并用文献[16]中的人工交互的方式确保结果正确.
 |
| 图 4 小篆(左边)与隶书(右边)的“堤”字的层次结构和对应关系Fig. 4 Hierarchical structure and corresponding relationship of “di” in seal script(left) and clerical script(right) |
| 图选项 |
 |
| 图 5 小篆(左边)与隶书(右边)的“堤”字的块模型Fig. 5 Block-model of “di” in seal script and clerical script |
| 图选项 |
2.2 笔画对应 在此使用1.2节中介绍的骨架图匹配方法对汉字部件进行对应.在产生图 3(a)中的匹配结果后,可以得到笔画路径的对应关系.如mii′mjj′=1,表示p(ui,,uj)与p(vi′,,vj′)对应.每个对应赋予它所经过的骨架点一个属性值wij,,这样所有的骨架点都可以得到一个属性集合,如{w13,w14}.一个字里具有相同属性集合的点划分为同一个笔画,两个字中相同属性的笔画为对应的笔画，如图 3(b)所示.为了方便进行形状插值,不匹配的边将与相邻的边合并. 2.3 形状插值 在笔画对应之后,将轮廓点分配到最近的骨架上面,然后采用文献[12]中的插值方法进行路径插值.这个方法对两形状的同构三角形进行插值而不是直接对轮廓点进行插值.为了获得同构三角形,细对应根据之前的笔画对应结果产生.一个笔段有一个起点和一个终点,当它们对应上之后,剩下的点用采样的方式一一对应.这些点用文献[18]中的方法构造同构三角形,如图 6(a)所示.然而同构三角形的质量并不好,因此需要采用文献[19]的方法进行优化,产生高质量的同构三角形,优化结果如图 6(b)所示.
 |
| 图 6 同构三角化和三角化优化的结果Fig. 6 Results of compatible triangulations and triangulations optimization |
| 图选项 |
在构建了同构三角化之后,问题就转化成了对应点的路径插值问题.对于单个三角形,原始三角形记作 P =(p1,p2,p3)目标图像顶点记作 Q =(q1,q2,q3)矩阵 A 表示 P 到 Q 的仿射矩阵,则
假设中间状态为 V (t)= A (t) P ,可以定义 A (t)=(1-t) I +t A .基本思想是将矩阵 A 分解成旋转部分和伸缩部分.由于奇异值分解(SVD)结果对称,而且维数可以任意定义,将矩阵 A 分解为旋转部分和伸缩部分,分解结果如下式:
基于这种分解可以得到:
对于三角形集合T={T{i,j,k}},每一个初始三角形 P =(pi,pj,pk)与目标三角形 Q =(qi,qj,qk)都有一一对应关系.对于每一对三角形来说,计算一种映射 A {i,j,k}(t).由于大部分的顶点对应于不止一个三角形,所有顶点的映射通常来说不符合各自的最优变换 A {i,j,k}(t).令V(t)为顶点的期望路径,能够在真实矩阵 B {i,j,k}(t)和期望矩阵 A {i,j,k}(t) 之间确定最小二次误差，表示如下:
式中 · 为Frobenius范数.为得到E V (t)的唯一最小值,应该预先确定一个顶点的位置,如v1x(t),v1y(t),插值方法如线性插值.令 u T=(1,v2x(t),v2y(t),…,vnx(t),vny(t)),则E V (t)可表示为
式中,c∈ R 表示常数; G ∈ R 2n×1是线性的; H ∈ R 2n×2n为二次型E V (t)的混合或者单一二次项系数.令自由变量的梯度 Δ E V (t) 为0，求解最小值,并对矩阵 H 求逆,然后利用与 G (t) 相乘来求解:
3 实验与结果分析实验环境为2.66GHz Intel Core Quad CPU 和3.0GB DDR2内存,Windows操作系统.算法用Microsoft Visual Studio 2010编程实现.所有的汉字图像分辨率均统一为396×350.实验数据主要是小篆和隶书图片,因为这两种字体是古代汉字与现代汉字的分水岭,文字的变形最剧烈,在汉字演变过程中具有代表性.为了验证本文方法的效果,将与两种现存方法比较:CPD(Coherent Point Drift)[10, 11]和SC(Shape Context)[6].使用细化算法提取骨架,然后随机采样骨架点作为两个方法的输入.部分试验数据在图 7中展示,实验结果在图 8中显示.可以看到本文的方法可以精确地找到相似的笔画结构,然而其他两种方法产生了错误的结果.这是因为本文的方法通过搜索笔画路径找到了最相似的部分作为对应结果,适合处理这类问题.
 |
| 图 7 一些小篆与隶书的例子Fig. 7 Some examples in seal script and clerical script |
| 图选项 |
 |
| 图 8 对应算法的实验结果Fig. 8 Experimental results of correspondence algorithms |
| 图选项 |
最终,变形动画也依据对应结果产生,结果在图 9中展示.实验当中的汉字变形非常复杂,根据笔画情况可分为:①笔画数量增多的情况;②笔画数量不变的情况;③笔画发生巨大变化的情况.结果表明本文的方法可较好地解决这些问题.
 |
| 图 9 小篆到隶书的变形动画Fig. 9 Morphing animation from seal script to clerical script |
| 图选项 |
4 结 论本文提出了基于骨架的图匹配算法解决汉字对应问题,并将它应用于不同时期间的汉字变形问题上.结果表明本文的方法具有一定效果,但是该方法仍有局限性:①笔画相似度的度量依赖于骨架和笔画提取的效果.②本文的方法不适用于笔画变化极大的问题.将在未来继续研究相关问题并改进算法,用于推动汉字的文化教育与国际传播.
参考文献
| [1] | 王宁. 汉字构形史丛书[M].上海:上海教育出版社,2003. Wang N.Series of books:history of Chinese characters'structure[M].Shanghai:Shanghai Education Press,2003(in Chinese). |
| [2] | Sederberg T W, Greenwood E.A physically based approach to 2D shape blending[C]//ACM Computer Graphics.New York:ACM,1992,26(2):25-34. |
| [3] | Zhang Y. A fuzzy approach to digital image warping[J].IEEE Computer Graphics and Applications, 1996,16(4):34-41. |
| Click to display the text | |
| [4] | Carmel E, Cohen-Or D.Warp-guided object space morphing[J].The Visual Computer,1997,13(9-10):465-478. |
| [5] | Yang W W, Feng J Q,Jin X G,et al.2-D shape blending based on visual feature decomposition[C]//Proceedings of Computer Animation and Social Agents,2004:139-146. |
| [6] | Belongie S, Malik J,Puzicha J.Shape matching and object recognition using shape contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(4):509-522. |
| [7] | Liu L G, Wang G P,Zhang B,et al.Perceptually based approach for planar shape morphing[C]//12th Pacific Conference on Computer Graphics and Applications.Washington:IEEE,2004:111-120. |
| [8] | Mortara M, Spagnuolo M.Similarity measures for blending polygonal shapes[J].Computers & Graphics,2001,25(1):13-27. |
| Click to display the text | |
| [9] | Bai X, Latecki L J.Path similarity skeleton graph matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(7):1282-1292. |
| Click to display the text | |
| [10] | Myronenko A, Song X.Point set registration:coherent point drift[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(12):2262-2275. |
| Click to display the text | |
| [11] | Lian Z H, Xiao J G.Automatic shape morphing for Chinese characters[C]//SIGGRAPH Asia 2012 Technical Briefs.New York:ACM,2012,2:1-4. |
| [12] | Alexa M, Cohen-Or D,Levin D.As-rigid-as-possible shape interpolation[C]//Proceedings of the ACM SIGGRAPH Conference on Computer Graphics.New York:ACM,2000:157-164. |
| [13] | Zhang T, Suen C Y.Fast parallel algorithm for thinning digital patterns[J].Communications of the ACM,1984,27(3):236- 239. |
| Click to display the text | |
| [14] | Shi J B, Tomasi C.Good features to track[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos,CA:IEEE,1994:593-600. |
| [15] | Torresani L, Kolmogorov V,Rother C.Feature correspondence via graph matching:models and global optimization[C]//Proceedings of the 10th European Conference on Computer Vision.Heidelberg:Springer Verlag,2008:596-609. |
| [16] | Xia Y, Wu J Q,Gao P C,et al.Ontology-based model for Chinese calligraphy synthesis[J].Computer Graphics Forum,2013 32(7):11-20. |
| [17] | Chung F, Ip W W S.Complex character decomposition using deformable model[J].IEEE Transactions on Systems,Man and Cybernetics Part C:Applications and Reviews,2001,31(1):126-132. |
| Click to display the text | |
| [18] | Gupta,H, Wenger R.Constructing piecewise linear homeomorphisms of simple polygons[J].Journal of Algorithms,1997,22(1): 142-157. |
| Click to display the text | |
| [19] | Surazhsky V, Gotsman C.High quality compatible triangulations[J].Engineering with Computers,2004:20(2):147-156. |
