基于骨架圖匹配的漢字變形技術

劉敏，詹華年，梁曉輝*，胡佳佳

(1.北京航空航天大學 計算機學院，北京100191;2.北京師范大學 文學院，北京100875)

漢字是一種典型的表意語言，每一個字符都由一個象征性的書寫符號來表示.在它漫長的發(fā)展歷史當中，漢字共經(jīng)歷5個主要階段:甲骨文、金文、小篆、隸書和楷書.雖然形狀和拓撲發(fā)生了極大的改變，但是這些階段之間是相互關聯(lián)的.其中前3種統(tǒng)一稱作古文字，而后2種稱作今文字.對語言文字研究可以分為共時與歷時2個方向.共時是指研究語言在特定事件的情況，而歷時是指研究語言在較長歷史時期所經(jīng)歷的變化.如果能夠理解演化的過程，將對漢字歷時研究起到重要的作用［1］.漢字演化過程中的變化主要包括:①筆畫形狀的改變;②漢字拓撲結構的改變;③部分增加或減少.在本文中主要工作在于利用漢字過程中保持不變的特征進行漢字的匹配對應，并用于生成盡可能平滑的變形結果，為漢字歷時研究和漢字教育提供技術基礎.

形狀變形是指在源形狀與目標形狀之間建立平滑的變化過程，它是計算機圖形學中的重要技術，并廣泛應用于電視、電影特效，卡通動畫和表面重構等工作.它主要包括2個步驟:①對應.建立源形狀與目標形狀之間的對應關系.②路徑插值.計算中間形狀的位置.

為了形成準確的匹配結果人們已經(jīng)做了大量的工作.文獻［2］中提出基于物理的方法，其核心是將2個多邊形看作線框，多邊形之間的漸變過程被看作初始線框變化到目標線框的過程，而線框之間的變化做功可分為伸縮和彎曲做功2部分，通過最小化做功函數(shù)來建立頂點對應關系.文獻［3］中通過形狀頂點所構成的三角形間的相似度來建立對應.以上方法都通過使用角度、邊長和三角形區(qū)域等幾何性質(zhì)來建立源形狀與目標形狀之間的對應關系.然而，這些性質(zhì)與其形狀所代表的含義毫無關系，因此這類方法不能建立使人滿意的對應結果.另一些方法使用半自動的方式建立對應文獻［4-5］，這類方法處理復雜圖像時人的工作難度大大增加，耗時耗力.其他方法采用局部特征進行匹配，如文獻［6］用均勻采樣產(chǎn)生的點集合表示形狀，用每一個采樣點與其他點的相對位置關系表示該點的特征.文獻［7］中的特征點用主成分分析(PCA)的方法進行描述，特征點的形狀性質(zhì)包括計算凹凸性、梯度方向.文獻［8-9］獲取近似的骨架描述形狀，并通過匹配骨架建立頂點的對應.

已經(jīng)有相關研究運用點集合定位［10-11］等算法進行現(xiàn)代漢字的變形，然而這些方法處理范圍并不包括不同階段漢字之間的變形，不適用于處理演化過程中的復雜變化.一方面，漢字由部件組成，部件通常包含獨特的結構.只采用局部形狀特征的方法無法表現(xiàn)出一個整體的特點.另一方面漢字的拓撲結構也在發(fā)生著改變，簡單的拓撲變化無法滿足漢字變形的需要.為此本文提出一種基于骨架的圖匹配方法來解決漢字中的對應問題.該方法的基本思路是通過比較所選取的特征點間的最短筆畫路徑來決定最優(yōu)匹配.這與文獻［9］中的思路相似，但是本文的方法比它更適合處理漢字間的問題.這種方法與直接比較骨架拓撲結構的傳統(tǒng)方法相比，復雜度低，速度更快，易于找到兩漢字中最相似的部分而不受多余部分干擾.對應產(chǎn)生之后，本文使用盡可能剛性的插值方法［12］產(chǎn)生漸變動畫.

1 骨架圖匹配

在漢字研究中，細化后的骨架仍然保留了漢字的語義和結構信息，因此本文直接對骨架進行處理而不是輪廓.骨架圖匹配是用一種基于骨架的圖模型匹配方法.骨架通常用屬性關系圖表示，通過找到屬性關系圖的最優(yōu)匹配來產(chǎn)生對應關系.

1.1 構造屬性關系圖

首先依次使用Zhang-Suen快速并行細化算法［13］和 Shi-Tomasi角點檢測方法［14］提取骨架和特征點.然后以特征點作為頂點，特征點間的筆段作為邊構造屬性關系圖，如圖1所示.具體細節(jié)如下.

1)兩個相鄰特征點之間的筆段為圖的一條邊，邊可以根據(jù)它的方向分為橫、豎、撇、捺4種類型.這4種類型普遍存在于漢字的各個階段當中，并且有自己的方向(0°，90°，135°和 45°).這里使用線性回歸計算筆段方向，并判斷筆段類型，允許有±15°的差異.筆段分類后骨架變?yōu)橐粋€有向無環(huán)圖.

2)特征點作為圖的頂點，它可以分為3種類型.入度為0，出度不為0的頂點叫做起始點;入度不為0，出度為0的點叫做終止點;既不為起始點也不為終止點的點稱作連接點.

圖1 小篆與隸書的字“止”及其屬性關系圖Fig.1 “Zhi”and its attributed-relation graph in seal script and clerical script

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個相似度方程，可以將對應問題轉(zhuǎn)化為求解最優(yōu)匹配問題.先假設一個匹配矩陣M，mii’∈{0，1}，mii′=1 表示圖 G 中的 ui匹配到G′中的 vi′，mii′=0 則表示不匹配.并且 M 的縱向之和與橫向之和都為1，確保G與G′之間的匹配一一對應.相似度方程可以寫為

式中c和d分別用式(1)和式(2)計算.目標是尋找最優(yōu)匹配，最大化該方程，使用雙分解方法［15］求解.對應結果在圖3中顯示，圖3(a)的結果可以由本文的算法直接得到，圖3(b)的結果需要通過2.2節(jié)的步驟得到.

圖3 小篆與隸書筆畫的對應結果Fig.3 Correspondence results between seal script and clerical script

2 變形動畫

本節(jié)將介紹使用骨架圖匹配進行漢字變形的具體方法.本文的方法主要包括以下3個步驟:①部件分割.輸入待變形的2個漢字，用半自動的方式分割和匹配部件.②筆畫對應.對部件進行骨架提取，拆分筆段后使用骨架圖匹配算法進行匹配，產(chǎn)生頂點和筆段的對應關系.③形狀插值.根據(jù)對應結果對2個漢字同構三角化，并使用盡可能剛性的形狀插值產(chǎn)生動畫.

2.1 部件分割

除了獨體字外，漢字通常由2個以上部件組成.比如“堤”字有“土”字和“是”組成，如圖4所示.因此有必要首先分析漢字找到部件的結構特點.為了獲取對應的部件使用最小包圍盒去分割輸入的不同時代漢字，并根據(jù)最小包圍盒之間的相對位置構造漢字的塊模型［16］，如圖5所示.之后，在塊模型中位于相同位置的部件就是匹配的部件.然而由于部件間可能會有交叉、粘連等情況出現(xiàn)，上述方法并不一定能產(chǎn)生正確的匹配結果.因此使用變形模版［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節(jié)中介紹的骨架圖匹配方法對漢字部件進行對應.在產(chǎn)生圖3(a)中的匹配結果后，可以得到筆畫路徑的對應關系.如 mii′mjj′=1，表示 p(ui，，uj)與 p(vi′，，vj′)對應.每個對應賦予它所經(jīng)過的骨架點一個屬性值wij，，這樣所有的骨架點都可以得到一個屬性集合，如{w13，w14}.一個字里具有相同屬性集合的點劃分為同一個筆畫，兩個字中相同屬性的筆畫為對應的筆畫，如圖3(b)所示.為了方便進行形狀插值，不匹配的邊將與相鄰的邊合并.

2.3 形狀插值

在筆畫對應之后，將輪廓點分配到最近的骨架上面，然后采用文獻［12］中的插值方法進行路徑插值.這個方法對兩形狀的同構三角形進行插值而不是直接對輪廓點進行插值.為了獲得同構三角形，細對應根據(jù)之前的筆畫對應結果產(chǎn)生.一個筆段有一個起點和一個終點，當它們對應上之后，剩下的點用采樣的方式一一對應.這些點用文獻［18］中的方法構造同構三角形，如圖6(a)所示.然而同構三角形的質(zhì)量并不好，因此需要采用文獻［19］的方法進行優(yōu)化，產(chǎn)生高質(zhì)量的同構三角形，優(yōu)化結果如圖6(b)所示.

在構建了同構三角化之后，問題就轉(zhuǎn)化成了對應點的路徑插值問題.對于單個三角形，原始三角形記作P=(p1，p2，p3)目標圖像頂點記作Q=(q1，q2，q3)矩陣A表示P到Q的仿射矩陣，則

圖6 同構三角化和三角化優(yōu)化的結果Fig.6 Results of compatible triangulations and triangulations optimization

基于這種分解可以得到:

對于三角形集合 T={T{i，j，k}}，每一個初始三角形 P=(pi，pj，pk)與目標三角形 Q=(qi，qj，qk)都有一一對應關系.對于每一對三角形來說，計算一種映射 A{i，j，k}(t).由于大部分的頂點對應于不止一個三角形，所有頂點的映射通常來說不符合各自的最優(yōu)變換 A{i，j，k}(t).令 V(t)為頂點的期望路徑，能夠在真實矩陣 B{i，j，k}(t)和期望矩陣A{i，j，k}(t)之間確定最小二次誤差，表示如下:

式中，c∈R 表示常數(shù);G∈R2n×1是線性的;H∈R2n×2n為二次型 EV(t)的混合或者單一二次項系數(shù).令自由變量的梯度 ΔEV(t)為0，求解最小值，并對矩陣H求逆，然后利用與G(t)相乘來求解:

3 實驗與結果分析

實驗環(huán)境為2.66GHz Intel Core Quad CPU和3.0GB DDR2內(nèi)存，Windows操作系統(tǒng).算法用Microsoft Visual Studio 2010編程實現(xiàn).所有的漢字圖像分辨率均統(tǒng)一為396×350.實驗數(shù)據(jù)主要是小篆和隸書圖片，因為這兩種字體是古代漢字與現(xiàn)代漢字的分水嶺，文字的變形最劇烈，在漢字演變過程中具有代表性.

為了驗證本文方法的效果，將與兩種現(xiàn)存方法 比 較:CPD(Coherent Point Drift)［10-11］和 SC(Shape Context)［6］.使用細化算法提取骨架，然后隨機采樣骨架點作為兩個方法的輸入.部分試驗數(shù)據(jù)在圖7中展示，實驗結果在圖8中顯示.可以看到本文的方法可以精確地找到相似的筆畫結構，然而其他兩種方法產(chǎn)生了錯誤的結果.這是因為本文的方法通過搜索筆畫路徑找到了最相似的部分作為對應結果，適合處理這類問題.

圖7 一些小篆與隸書的例子Fig.7 Some examples in seal script and clerical script

圖8 對應算法的實驗結果Fig.8 Experimental results of correspondence algorithms

最終，變形動畫也依據(jù)對應結果產(chǎn)生，結果在圖9中展示.實驗當中的漢字變形非常復雜，根據(jù)筆畫情況可分為:①筆畫數(shù)量增多的情況;②筆畫數(shù)量不變的情況;③筆畫發(fā)生巨大變化的情況.結果表明本文的方法可較好地解決這些問題.

圖9 小篆到隸書的變形動畫Fig.9 Morphing animation from seal script to clerical script

4 結論

本文提出了基于骨架的圖匹配算法解決漢字對應問題，并將它應用于不同時期間的漢字變形問題上.結果表明本文的方法具有一定效果，但是該方法仍有局限性:①筆畫相似度的度量依賴于骨架和筆畫提取的效果.②本文的方法不適用于筆畫變化極大的問題.將在未來繼續(xù)研究相關問題并改進算法，用于推動漢字的文化教育與國際傳播.

References)

［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.

［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，F(xiàn)eng 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.

［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.

［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.

［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.

［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.

［18］ Gupta，H，Wenger R.Constructing piecewise linear homeomorphisms of simple polygons［J］.Journal of Algorithms，1997，22(1):142-157.

［19］ Surazhsky V，Gotsman C.High quality compatible triangulations［J］.Engineering with Computers，2004:20(2):147-156.