劉穎濱 孫燕南 荀恩東

?

一種基于三維空間信息的字形匹配方法

劉穎濱?孫燕南 荀恩東

北京語言大學(xué)大數(shù)據(jù)與語言教育研究所, 北京 100083; ?通信作者, E-mail: liuyb@blcu.edu.cn

提出一種基于三維空間信息的字形匹配方法。首先將字形輪廓Bézier曲線的二維控制點(diǎn)集擴(kuò)展至三維, 然后為三維點(diǎn)集建立高斯混合模型, 最后通過最小化高斯混合模型間的歐氏距離(L2)完成匹配。采用三維空間信息可以充分利用字形所蘊(yùn)含的內(nèi)在約束條件。采用高斯混合模型有利于在匹配過程中保持字形整體結(jié)構(gòu)特征和局部書寫特征。實(shí)驗(yàn)結(jié)果表明, 該方法提升了漢字單筆畫以及整字字形匹配的準(zhǔn)確度和美觀度, 并且具有穩(wěn)定性高、擴(kuò)展性強(qiáng)的特點(diǎn)。

字形匹配; 高斯混合模型; 點(diǎn)集匹配; 三維空間

字形匹配指按照一定的準(zhǔn)則, 衡量漢字字形的相似程度, 從而建立對應(yīng)關(guān)系并進(jìn)行變換的過程, 是字形美化的關(guān)鍵步驟[1–2]。傳統(tǒng)字形匹配方法有基于骨架的方法[3]、基于筆畫還原的方法[4]和基于特征提取的方法[5]等。近年來, 點(diǎn)集匹配算法[6-11]發(fā)展較快, 并且已經(jīng)被應(yīng)用到字形匹配領(lǐng)域[12–14]。

記兩個有限維空間中的點(diǎn)集{,}為待匹配點(diǎn)集, 其中為目標(biāo)點(diǎn)集,為模型點(diǎn)集。在匹配過程中,保持固定不變,向不斷逼近。點(diǎn)集匹配問題可描述為找到一個變換, 使得經(jīng)過變換后的結(jié)果點(diǎn)集與目標(biāo)點(diǎn)集實(shí)現(xiàn)最優(yōu)匹配。點(diǎn)集匹配算法分為基于剛體變換和基于非剛體變換兩種。非剛體變換屬于局部性幾何形變, 自由度更高, 匹配效果較好。Myronenko等[9]提出的一致性點(diǎn)漂移算法(Coherent Point Drift, CPD)是一種具有代表性的基于非剛體變換的點(diǎn)集匹配方法。CPD算法將模型點(diǎn)集中各點(diǎn)視作高斯混合模型(Gaussian Mixture Model, GMM)中各個高斯分量質(zhì)心。在匹配過程中,作為一個整體逐漸向進(jìn)行保持拓?fù)浣Y(jié)構(gòu)一致性的漂移運(yùn)動。Sun等[13]和Lian等[14]使用CPD算法進(jìn)行漢字筆畫的抽取, 提出一種基于結(jié)構(gòu)指導(dǎo)的快速一致點(diǎn)漂移算法(Structure-Guided Coherent Point Drift, SGCPD)。Jian等[12]提出一個統(tǒng)一的基于高斯混合模型的點(diǎn)集匹配算法框架, 利用概率統(tǒng)計(jì)方法將點(diǎn)集匹配轉(zhuǎn)化為數(shù)值計(jì)算問題?，F(xiàn)有的點(diǎn)集匹配算法[7–11]都可用此框架重新解釋。該框架的核心思想是針對點(diǎn)集建立高斯混合模型, 從而將點(diǎn)集匹配問題轉(zhuǎn)化為高斯混合模型間的相似度最大化問題。實(shí)驗(yàn)證明, 基于此框架的點(diǎn)集匹配算法具有內(nèi)在的統(tǒng)計(jì)魯棒性, 且易于實(shí)現(xiàn)[12]。

一般地, 通用的點(diǎn)集匹配算法適用于多維點(diǎn)集, 而在字形匹配領(lǐng)域, 目前基于點(diǎn)集匹配的方法[12–14]限于字形的二維點(diǎn)集。實(shí)驗(yàn)表明, 僅采用二維點(diǎn)集進(jìn)行匹配的結(jié)果往往不夠理想, 原因之一在于漢字字形內(nèi)在的特殊性和復(fù)雜性。僅使用二維點(diǎn)集進(jìn)行匹配時, 漢字字形輪廓中所蘊(yùn)含的許多信息被忽略, 無法在匹配過程中發(fā)揮作用。本文將字形信息定義為超越二維幾何信息的多維數(shù)據(jù), 以期充分表達(dá)書寫過程, 提升匹配精度。作為利用多維字形信息的第一步, 本文結(jié)合字形本身特征, 將字形二維點(diǎn)集和擴(kuò)充為三維點(diǎn)集′和′, 然后再進(jìn)行匹配, 具體步驟為: 1)提取二維字形控制點(diǎn)集并擴(kuò)充至三維; 2)為三維字形點(diǎn)集建立GMM; 3)通過最小化兩個GMM之間的歐氏距離(L2)完成匹配; 4)將匹配后的三維結(jié)果轉(zhuǎn)化為二維, 經(jīng)平滑處理后生成字形曲線。

本文的創(chuàng)新之處主要體現(xiàn)在: 1)采用三維點(diǎn)集進(jìn)行匹配, 嘗試采用擴(kuò)充維度的方法來改進(jìn)匹配結(jié)果; 2)僅使用字體信息, 不依賴其他附加信息; 3) 選用最小化高斯混合模型間的L2距離來求解匹配關(guān)系, 實(shí)現(xiàn)簡單且穩(wěn)定性好。

1 數(shù)據(jù)處理

本文采用漢字字體輪廓的Bézier曲線[15]控制點(diǎn)集定義字形, 優(yōu)勢在于: 1)控制點(diǎn)集可以從數(shù)學(xué)上精確定義輪廓曲線, 并且可以根據(jù)需要繪制(字形骨架點(diǎn)必須通過額外工作才能還原輪廓[14]); 2) 標(biāo)準(zhǔn)TrueType字庫均采用Bézier控制點(diǎn)來定義曲線輪廓, 具有普遍性; 3)Bézier曲線便于進(jìn)行插值和 細(xì)分。

1.1 二維控制點(diǎn)集

TrueType字體[16]使用直線和二次Bézier曲線定義字形輪廓。在設(shè)計(jì)字體時, 利用二次Bézier曲線的C1連續(xù)性條件, 往往會省略部分在曲線上的控制點(diǎn)以減小數(shù)據(jù)量。因此, TrueType字體輪廓的原始控制點(diǎn)可能疏密不均, 需要進(jìn)行優(yōu)化處理。為了統(tǒng)一表達(dá), 本文將直線視為特殊的二次Bézier曲線, 認(rèn)為字形輪廓由若干分段二次Bézier曲線連接而成?？刂泣c(diǎn)集優(yōu)化是還原完整的分段二次Bézier曲線控制點(diǎn)的過程, 包括還原被省略的控制點(diǎn)、將直線統(tǒng)一為二次Bézier曲線以及輪廓封閉處理3個步驟。在優(yōu)化過程中, 還可以利用Bézier曲線任意細(xì)分而不改變原始曲線形狀的性質(zhì), 對控制點(diǎn)集進(jìn)行適當(dāng)加密以便于匹配, 加密方法不在此贅述。圖1為楷體“乙”字的原始控制點(diǎn)集以及經(jīng)過優(yōu)化后的結(jié)果。

1.2 三維點(diǎn)集

實(shí)驗(yàn)表明, 直接采用字形的二維控制點(diǎn)集進(jìn)行匹配, 結(jié)果往往不夠理想, 原因在于漢字字形輪廓中蘊(yùn)含的約束條件在匹配過程中很可能被破壞, 導(dǎo)致匹配結(jié)果不符合漢字的審美標(biāo)準(zhǔn)。例如, 單筆畫匹配時, 某些較細(xì)的筆畫輪廓兩邊的點(diǎn)對應(yīng)錯位; 整字匹配時, 某些筆畫輪廓被匹配到其他筆畫。為了彌補(bǔ)二維信息的不足, 本文將二維點(diǎn)集擴(kuò)充為三維點(diǎn)集。擴(kuò)充的基本思想在于利用字形本身特征生成第三維信息, 使點(diǎn)集分布在三維空間中, 以減少二維匹配產(chǎn)生的錯誤。擴(kuò)充過程不改變原始的二維坐標(biāo)。

以模型點(diǎn)集為例,= [XY]表示中第個點(diǎn), 對于, 使得

上式中,= (arg maxy-arg miny)-(arg maxx– arg minx),= 1, 2, …,。

表示三維點(diǎn)集所在平面與平面所成的夾角。的取值對匹配結(jié)果有一定影響, 此處取經(jīng)驗(yàn)值=p/4。利用上述方法將二維控制點(diǎn)集和擴(kuò)充為三維點(diǎn)集′和′。圖2為楷體“乙”的三維點(diǎn)集的生成過程。

2 建立高斯混合模型

作為常用的統(tǒng)計(jì)學(xué)方法, 高斯混合模型用若干個高斯概率分布的線性組合來表示數(shù)據(jù)的概率分布[17–18]。一個階的高斯混合模型的概率密度函數(shù)可以表示為

其中,為維隨機(jī)變量;(=1, 2, …,)為每個高斯分布的權(quán)重, 且滿足;為 每個子分布的維的聯(lián)合高斯概率分布,是子分布的均值向量,是協(xié)方差矩陣。參數(shù)可表示為。

漢字字形輪廓控制點(diǎn)的分布并不嚴(yán)格服從特定的概率密度函數(shù), 但是, 由中心極限定理可知, 任意形狀的概率分布都可以用若干個高斯密度函數(shù)的線性組合來逼近。在字形匹配研究中, 可對三維點(diǎn)集建立高斯混合模型, 從而將字形匹配問題轉(zhuǎn)化為GMM的匹配問題。根據(jù)式(1), 令=3,為三維點(diǎn)集中點(diǎn)的個數(shù), 則的GMM定義如下:

選用GMM定義三維點(diǎn)集的優(yōu)勢在于: 1)將字形匹配問題轉(zhuǎn)化為GMM匹配問題, 可使問題得到簡化; 2)GMM能精確表達(dá)三維點(diǎn)集的概率分布情況, 體現(xiàn)字形整體與局部的字形特征, 提升匹配精確度。

3 匹配算法

通過定義并求解基于GMM的目標(biāo)函數(shù)可以解決對應(yīng)的三維點(diǎn)集的匹配問題。目標(biāo)函數(shù)的定義可采用最小化歐氏距離(L2)、最大化對數(shù)似然函數(shù)[12]和最大化內(nèi)核相關(guān)(Kernel Correlation)[19]等方法。其中, L2距離簡單直觀, 穩(wěn)定性強(qiáng), 而且在多維空間中存在明確定義, 比較適合三維字形匹配。本文采用最小化L2距離作為目標(biāo)函數(shù), 用GMM間的L2距離來衡量GMM間相似度, L2距離越小, 則GMM間的相似度越高, 字形的匹配度就越高。

對于三維模型點(diǎn)集′和目標(biāo)點(diǎn)集′, 用表示帶參數(shù)的非剛體變換, 則目標(biāo)函數(shù)定義如下:

本文采用的匹配算法框架如下。

輸入: 模型點(diǎn)集′, 目標(biāo)點(diǎn)集′, 參數(shù)化的變換

開始:

設(shè)置循環(huán)次數(shù)times, 循環(huán)計(jì)數(shù)變量count=0

定義目標(biāo)函數(shù)(式(3))

重復(fù):

更新參數(shù), 即←argmind2

count ← count +1

直到達(dá)到設(shè)定的循環(huán)次數(shù)count ≥ times

結(jié)束

上述算法中, 常用的變換模型有薄板樣條函數(shù)(Thin-plate Splines, TPS)[20]和高斯徑向基函數(shù)(Gaussian Radial Basis Functions, GRBF)[21–22]等。本文采用TPS作為匹配時的變換模型, 將匹配后的三維結(jié)果平行投影到平面得到最終的二維結(jié)果。由于中輪廓曲線的分段連續(xù)性條件在匹配過程中可能被破壞, 所以根據(jù)模型點(diǎn)集中的相應(yīng)的分段連續(xù)關(guān)系, 對進(jìn)行局部平滑操作, 并生成最后的字形曲線。

4 實(shí)驗(yàn)結(jié)果

本文選取“仿宋”和“楷體”兩種字體的33個基本筆畫進(jìn)行字形匹配實(shí)驗(yàn), 見表1。根據(jù)使用的變換模型、目標(biāo)函數(shù)以及數(shù)據(jù)維度, 將實(shí)驗(yàn)所涉及的方法分別命名。本文提出的基于三維空間信息的字形匹配方法命名為TPS_L2_3D方法。另外選取具有代表性的TPS_L2和EM_GRBF方法(EM_GRBF方法即CPD方法)[12]作為對照實(shí)驗(yàn), 兩種方法都使用二維點(diǎn)集建立GMM。前者通過最小化L2距離完成匹配并以TPS作為變換模型; 后者通過最大化對數(shù)似然函數(shù)完成匹配, 以GRBF作為變換模型。TPS_L2方法簡單且穩(wěn)定性強(qiáng), EM_GRBF匹配精確度高, 但容易受到噪聲點(diǎn)的影響[12]。

表1 實(shí)驗(yàn)筆畫及其編號

本文的實(shí)驗(yàn)結(jié)果分析主要從平均匹配概率和視覺效果兩個方面來衡量。平均匹配概率(averaged assignment probability, AAP)[13]的定義如下:

其中,表示目標(biāo)點(diǎn)集,表示模型點(diǎn)集匹配后的結(jié)果,和分別表示與的點(diǎn)集大小,p表示中第個點(diǎn)與中第個點(diǎn)的匹配概率。AAP反映點(diǎn)集中各點(diǎn)的最優(yōu)匹配概率的平均水平, 這一指標(biāo)在一定程度上體現(xiàn)變換后的點(diǎn)集與目標(biāo)點(diǎn)集的相似度。由于字形的特殊性, 匹配結(jié)果的美觀程度也是評價匹配結(jié)果的一個重要標(biāo)準(zhǔn)。

圖3為3種方法在筆畫實(shí)驗(yàn)中的平均匹配概率分布。從圖3可以看出, 本文提出的TPS_L2_3D方法比TPS_L2方法在平均匹配概率上有顯著提升; TPS_L2_3D的匹配結(jié)果與EM_GRBF結(jié)果相近, 部分筆畫的平均匹配概率比EM_GRBF方法更高。以具體筆畫為例, 圖3中箭頭標(biāo)示的“豎彎鉤”和“橫折彎”這兩個筆畫的平均匹配概率都是TPS_L2_3D方法最高, 其對應(yīng)的控制點(diǎn)匹配結(jié)果分別如圖4和5所示。從圖4和5可以看出, 就匹配的整體視覺效果而言, TPS_L2_3D的匹配結(jié)果比TPS_L2和EM_GRBF方法更接近目標(biāo)點(diǎn)集, 這一點(diǎn)與平均匹配概率的數(shù)據(jù)分析結(jié)果一致; 在局部匹配上, 對于圖4和5中箭頭標(biāo)示部分的匹配, TPS_L2_3D方法匹配的更為精細(xì)。

對于部分TPS_L2_3D平均匹配概率低于EM_GRBF的情況, 我們發(fā)現(xiàn)兩種方法的匹配結(jié)果視覺上都具備目標(biāo)字形的基本輪廓特征, 整體效果相似; TPS_L2_3D未造成明顯的匹配錯誤, 甚至局部的匹配結(jié)果優(yōu)于EM_GRBF。以圖6筆畫“捺”為例, 雖然其TPS_L2_3D平均最優(yōu)匹配概率AAP值低于EM_GRBF, 但是TPS_L2_3D匹配結(jié)果卻更好地保持了字形的基本輪廓特征。同時, 第三維信息的加入能夠幫助提升局部點(diǎn)的匹配精度, 例如在箭頭標(biāo)示區(qū)域, TPS_L2_3D的匹配結(jié)果比EM_ GRBF的匹配結(jié)果更美觀。

對于部分TPS_L2_3D匹配結(jié)果的平均匹配概率高于EM_GRBF的情況, 由于TPS_L2_3D方法穩(wěn)定性強(qiáng), 對于噪聲點(diǎn)不敏感, 因此在匹配過程中能夠較好地保持字形的整體拓?fù)浣Y(jié)構(gòu)。EM_GRBF方法對噪聲點(diǎn)比較敏感, 算法的結(jié)果和效率受調(diào)整參數(shù)的影響較大[12], 因此可能會造成匹配結(jié)果偏離目標(biāo)字形。如圖7所示, 筆畫“橫折”的EM_GRBF匹配結(jié)果在箭頭標(biāo)示處出現(xiàn)明顯的偏差, 而TPS_L2_3D匹配結(jié)果則明顯占優(yōu)。

本文另外選取部分漢字, 進(jìn)行從仿宋到楷體的整字匹配實(shí)驗(yàn)。以“漢”和“字”為例, 整字匹配結(jié)果經(jīng)過光滑處理后得到的字形曲線分別如圖8和9 所示。通過對比3種方法的匹配結(jié)果, 可見TPS_L2_3D的綜合匹配結(jié)果最理想: 1)整體效果最接近目標(biāo)字形, 具備楷體的風(fēng)格, 而另外兩種方法仍帶有較明顯的仿宋體的特征; 2)在拐角等關(guān)鍵點(diǎn)的匹配更為精準(zhǔn), 筆畫流暢, 符合書寫特點(diǎn); 3)算法效率高, TPS_L2_3D與TPS_L2的復(fù)雜度大致相同, 但在精確性和美觀性方面, 前者的匹配結(jié)果比后者提升很多。

5 總結(jié)和展望

采用基于高斯混合模型的三維點(diǎn)集匹配算法解決字形匹配問題, 是漢字字形匹配領(lǐng)域的一次創(chuàng)新。本文使用了多維數(shù)據(jù)定義字形信息, 從而改善了字形匹配結(jié)果。實(shí)驗(yàn)結(jié)果表明, 通過旋轉(zhuǎn)變換來擴(kuò)充第三維數(shù)據(jù)可以有效提升字形匹配精度, 從而驗(yàn)證了使用多維度信息對于改善字形匹配效果的可行性。從宏觀上講, 盡管字形本身是二維信息, 但是書寫過程本質(zhì)上包含多個維度的信息(如書寫速度、力度等)。以往的研究中, 這些信息多抽象為書寫規(guī)則或個人經(jīng)驗(yàn)的形式進(jìn)行描述; 字形匹配的工作也局限于二維幾何信息, 多關(guān)注于書寫結(jié)果的研究而忽略了書寫過程。將來的研究中, 我們會嘗試從多維度的視角來解決字形匹配問題, 通過收集書寫過程的多維度信息, 發(fā)現(xiàn)規(guī)律并提取特征, 充分還原書寫過程的多維度屬性。

通過有效的多維度字形匹配, 有助于解決中文字形領(lǐng)域內(nèi)的許多問題, 具有廣闊的應(yīng)用前景。除標(biāo)準(zhǔn)字體外, 還可以應(yīng)用到手寫漢字字形美化領(lǐng)域。在獲取手寫字的多維字形信息后, 可以通過字形匹配使手寫字具備目標(biāo)字形的特征, 從而達(dá)到美化字形的目的; 通過設(shè)置字形匹配的參數(shù), 用戶可以定制兼顧個人書寫風(fēng)格與特定目標(biāo)字體風(fēng)格的個性化字體。

[1]莊崇彪, 金連文. 在線漢字書寫正誤及工整的智能評判算法. 信號處理, 2005, 8(4A): 276–279

[2]楊曉江. 漢字智能書寫及其算法. 計(jì)算機(jī)工程, 2003, 29(21): 154–155

[3]劉云飛. 脫機(jī)手寫體漢字識別中細(xì)化、特征提取和相似字識別算法研究[D]. 長春: 吉林大學(xué), 2006

[4]荀恩東, 呂曉晨, 安維華, 等. 面向書寫教學(xué)的手寫漢字圖像筆畫還原. 北京大學(xué)學(xué)報(bào): 自然科學(xué)版, 2015, 51(2): 241–248

[5]孫華, 張航. 漢字識別方法綜述. 計(jì)算機(jī)工程, 2010, 36(20): 194–197

[6]趙鍵. 點(diǎn)模式匹配算法研究[D]. 長沙: 國防科學(xué)技術(shù)大學(xué), 2012

[7]Besl P J, McKay H D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239–256

[8]Jian B, Vemuri B C, A robust algorithm for point set registration using mixture of Gaussians//ICCV. Beijing, 2005: 1246–1251

[9]Myronenko A, Song X B. Point-set registration: Coherent point drift．IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12): 2262–2275

[10]Chui H, Rangarajan A. A new algorithm for non-rigid point registration. CVPR, 2000, 89(2): 2044–2051

[11]Myronenko A, Song X B. Non-rigid point setre-gistration: coherent point drift. NIPS, 2006, 32(12): 1009–1016

[12]Jian B, Vemuri B C. Robust point set registration using gaussian mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1633–1645

[13]Sun Hao, Lian Zhouhui, Tang Yingming, et al. Non-rigid point set registration for chinese characters using structure-guided coherent point drift // IEEE International Conference on Image Processing (ICIP). Paris, 2014: 4752–4756

[14]Lian Zhouhui, Xiao Jianguo. Automatic shape morphing for Chinese characters // 5th ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia (SIGGRAPH ASIA 2012). Singapore, 2012: Article No. 2

[15]張明星. 廣義Bézier曲線與B樣條曲線的研究[D]. 長沙: 中南大學(xué), 2013

[16]吳海輝, 樊慶林, 王虎, 等. TrueType字體技術(shù)的研究分析與應(yīng)用. 電腦知識與技術(shù)(學(xué)術(shù)交流), 2007, 1(3): 783–784, 794

[17]管濤, 李玲玲. 高斯混合模型、求解算法及視覺應(yīng)用綜述. 中國圖象圖形學(xué)報(bào), 2012, 17(12): 1461–1471

[18]趙玲麗. 基于高斯混合模型的語音轉(zhuǎn)換技術(shù)研究[D]. 南京: 南京郵電大學(xué), 2011

[19]Tsin Y, Kanade T. A correlation-based approach to robust point set registration // ECCV. Berlin: Springer, 2004: 558–569

[20]Bookstein F L, Principal W. Thin-plate splines and the decomposition of deformations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989, 11(6): 567–585

[21]Fornefett M, Rohr K, Stiehl H S. Elastic registration of medical images using radial basis functions with compact support // IEEE Computer Society Con-ference on Computer Vision and Pattern Recognition. Colorada, 1999: 402–407

[22]Powell M J D. Radial basis functions for multivariate interpolation: a review // Conf 1st Algorithms for Approximation (Inst Math Its Appl Conf Series). Oxford: ClarendonPress, 1987: 143–147

Chinese Calligraphy Alignment Based on 3D Point Set Registration

LIU Yingbin?, SUNYannan, XUN Endong

Institute of Big Data and Language Education, Beijing Language and Culture University, Beijing 100083; ?Correspondence author, E-mail: liuyb@blcu.edu.cn

This paper presents an innovative method to align two glyph contours with three steps. First, 2D Bézier curve control points of glyph contours of each character are expanded into 3D space. Second, a Gaussian Mixture Model (GMM) is constructed using this 3D point set. Finally, the authors establish alignment by minimizing the Euclidean Distance (L2) between two GMMs and then apply transformation accordingly. Expansion to 3D space helps make use of inherent constraints of Chinese calligraphy beyond 2D coordinates. The advantage of using Gaussian Mixture Model is to maintain both the overall shape property and the local writing features during the alignment process. Experiments results verify the feasibility and effectiveness of proposed method and it performs well for both single stroke and whole character.

Chinese calligraphy alignment; Gaussian Mixture Model; point set registration; 3D point set

10.13209/j.0479-8023.2016.016

TP391

2015-06-03;

2015-08-15; 網(wǎng)絡(luò)出版日期: 2015-09-30

國家自然科學(xué)基金(61170162, 61202249)和國家語言文字工作委員會科研項(xiàng)目(YB125-42)資助