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

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

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

形狀變形是指在源形狀與目標(biāo)形狀之間建立平滑的變化過(guò)程，它是計(jì)算機(jī)圖形學(xué)中的重要技術(shù)，并廣泛應(yīng)用于電視、電影特效，卡通動(dòng)畫和表面重構(gòu)等工作.它主要包括2個(gè)步驟:①對(duì)應(yīng).建立源形狀與目標(biāo)形狀之間的對(duì)應(yīng)關(guān)系.②路徑插值.計(jì)算中間形狀的位置.

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

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

1 骨架圖匹配

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

1.1 構(gòu)造屬性關(guān)系圖

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

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

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

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

1.2 骨架圖匹配

通過(guò)建立起始點(diǎn)和終止點(diǎn)的對(duì)應(yīng)關(guān)系來(lái)匹配2個(gè)圖模型，因?yàn)檫@些點(diǎn)一般都是本文書寫時(shí)的起點(diǎn)和終點(diǎn)，而連接點(diǎn)并沒有參與匹配.接下來(lái)先介紹匹配中的相似度度量方式.

假設(shè)有I個(gè)起始點(diǎn)和J個(gè)終止點(diǎn)在圖G中，I′個(gè)起始點(diǎn)和 J′個(gè)終止點(diǎn)在圖 G′中.ui(i=1，2，…，I)，vi′(i′=1，2，…，I′)分別表示 2 個(gè)模型中的起始點(diǎn)，uj(j=I+1，I+2，…，I+J)，vj′(j′=I′+1，I′+2，…，I′+J′)分別表示 2 個(gè)模型中的終止點(diǎn).同類點(diǎn)間的相似度用歐式距離表示，公式如下:

其中x，y為歸一化到［0，1］后的坐標(biāo)值.

一個(gè)起始點(diǎn)到一個(gè)終止點(diǎn)的最短路徑由p(ui，uj)表示，本文記錄 p(ui，uj)中的筆畫類型(橫、豎、撇、捺)和順序作為筆畫路徑 ps(ui，uj)，如圖2所示.那么任意2個(gè)路徑的相似度表示為

式中，LLCS為2個(gè)序列的最大公共子序列的長(zhǎng)度;l為序列的長(zhǎng)度.

圖2 起始點(diǎn)與終止點(diǎn)間的筆畫路徑Fig.2 Stroke-paths between startpoints and endpoints

由以上2個(gè)相似度方程，可以將對(duì)應(yīng)問(wèn)題轉(zhuǎn)化為求解最優(yōu)匹配問(wèn)題.先假設(shè)一個(gè)匹配矩陣M，mii’∈{0，1}，mii′=1 表示圖 G 中的 ui匹配到G′中的 vi′，mii′=0 則表示不匹配.并且 M 的縱向之和與橫向之和都為1，確保G與G′之間的匹配一一對(duì)應(yīng).相似度方程可以寫為

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

圖3 小篆與隸書筆畫的對(duì)應(yīng)結(jié)果Fig.3 Correspondence results between seal script and clerical script

2 變形動(dòng)畫

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

2.1 部件分割

除了獨(dú)體字外，漢字通常由2個(gè)以上部件組成.比如“堤”字有“土”字和“是”組成，如圖4所示.因此有必要首先分析漢字找到部件的結(jié)構(gòu)特點(diǎn).為了獲取對(duì)應(yīng)的部件使用最小包圍盒去分割輸入的不同時(shí)代漢字，并根據(jù)最小包圍盒之間的相對(duì)位置構(gòu)造漢字的塊模型［16］，如圖5所示.之后，在塊模型中位于相同位置的部件就是匹配的部件.然而由于部件間可能會(huì)有交叉、粘連等情況出現(xiàn)，上述方法并不一定能產(chǎn)生正確的匹配結(jié)果.因此使用變形模版［17］自動(dòng)分割部件，并用文獻(xiàn)［16］中的人工交互的方式確保結(jié)果正確.

圖4 小篆(左邊)與隸書(右邊)的“堤”字的層次結(jié)構(gòu)和對(duì)應(yīng)關(guān)系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 筆畫對(duì)應(yīng)

在此使用1.2節(jié)中介紹的骨架圖匹配方法對(duì)漢字部件進(jìn)行對(duì)應(yīng).在產(chǎn)生圖3(a)中的匹配結(jié)果后，可以得到筆畫路徑的對(duì)應(yīng)關(guān)系.如 mii′mjj′=1，表示 p(ui，，uj)與 p(vi′，，vj′)對(duì)應(yīng).每個(gè)對(duì)應(yīng)賦予它所經(jīng)過(guò)的骨架點(diǎn)一個(gè)屬性值wij，，這樣所有的骨架點(diǎn)都可以得到一個(gè)屬性集合，如{w13，w14}.一個(gè)字里具有相同屬性集合的點(diǎn)劃分為同一個(gè)筆畫，兩個(gè)字中相同屬性的筆畫為對(duì)應(yīng)的筆畫，如圖3(b)所示.為了方便進(jìn)行形狀插值，不匹配的邊將與相鄰的邊合并.

2.3 形狀插值

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

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

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

基于這種分解可以得到:

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

圖8 對(duì)應(yīng)算法的實(shí)驗(yàn)結(jié)果Fig.8 Experimental results of correspondence algorithms

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

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

4 結(jié)論

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

References)

［1］ 王寧.漢字構(gòu)形史叢書［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.