基于分形幾何的甲骨文字形識(shí)別方法

顧紹通

(江蘇師范大學(xué) 語言科學(xué)與藝術(shù)學(xué)院，江蘇 徐州 221009)

0 引言

甲骨文是書寫在龜甲和獸骨上的文字，是我國迄今發(fā)現(xiàn)的最早的一種成熟文字系統(tǒng)。

甲骨文字形的輸入可以采用編碼輸入或者識(shí)別輸入的方法。目前對(duì)甲骨文字形采用編碼輸入的方案已有多種，如基于甲骨文字形動(dòng)態(tài)描述庫的輸入方法[1]、可視化甲骨文輸入法[2]、基于拓?fù)浣Y(jié)構(gòu)的輸入方法[3]、甲骨文自由筆畫輸入法[4]和象形碼輸入方法[5]。以上方案或多或少需要記住某些規(guī)則，這對(duì)它的推廣使用是不利的。以上方案從字形某一方面的特點(diǎn)出發(fā)進(jìn)行編碼，在一定程度上解決了甲骨文字形的輸入問題，但也存在不足之處。出土甲骨拓片上的甲骨文字形中，大部分字形無法正確辨識(shí)其讀音和意義，使得甲骨文編碼輸入方法存在規(guī)則繁瑣、重碼多和效率低的局限。要讓一般用戶掌握其復(fù)雜的規(guī)則并不現(xiàn)實(shí)，只有少數(shù)從事甲骨文研究方面的專家學(xué)者才能掌握復(fù)雜的編碼規(guī)則，這使得編碼輸入方法的實(shí)用性受到限制。隨著信息技術(shù)的發(fā)展，甲骨文的識(shí)別輸入受到越來越多的重視。目前，已出現(xiàn)多種甲骨文字形識(shí)別方案，如顧紹通提出的基于拓?fù)渑錅?zhǔn)的識(shí)別方法[6]；周新倫等[7]提出利用圖論和筆劃特點(diǎn)來識(shí)別甲骨文字形的方法；李鋒等[8]提出利用圖特征的原理來識(shí)別甲骨文字形的方法，并且取得了不錯(cuò)的效果；栗青生等[9]提出利用圖同構(gòu)的方法來識(shí)別甲骨文字形，這種方法對(duì)于那些甲骨文中不同構(gòu)但仍為同一字形的異寫字的識(shí)別沒有進(jìn)行處理，且雖然同構(gòu)但是卻不是同一個(gè)字形的情況大量存在，這種算法的魯棒性很低，因而實(shí)用性受到限制。

本文將首先分析甲骨文字形的分形性質(zhì)，通過計(jì)算字形的分形維數(shù)并與通用甲骨文字庫中字形的特征庫進(jìn)行匹配，實(shí)現(xiàn)甲骨文字形的識(shí)別。文章其余部分的組織結(jié)構(gòu)如下： 第一節(jié)介紹了分形幾何的一般理論；第二節(jié)分析了甲骨文字形的分形性質(zhì)；第三節(jié)是基于分形幾何的識(shí)別算法；第四節(jié)是實(shí)驗(yàn)結(jié)果和分析；第五節(jié)對(duì)全文進(jìn)行總結(jié)。

1 分形幾何理論

普通幾何學(xué)研究的對(duì)象，一般都具有整數(shù)的維數(shù)。比如，零維的點(diǎn)、一維的線、二維的面、三維的立體、乃至四維的時(shí)空。分形幾何研究的是客觀事物具有自相似的層次結(jié)構(gòu)，局部與整體在形態(tài)、功能、信息、時(shí)間、空間等方面具有統(tǒng)計(jì)意義上的相似性，成為自相似性。分形是關(guān)于自相似性的一般概念，由Mandelbrot[10]提出，用于描述具有相似結(jié)構(gòu)的幾何形狀。分形理論認(rèn)為維數(shù)也可以是分?jǐn)?shù)，數(shù)學(xué)家從測(cè)度的角度引入了維數(shù)概念，將維數(shù)從整數(shù)擴(kuò)大到分?jǐn)?shù)，從而突破了一般拓?fù)浼S數(shù)為整數(shù)的界限。

嚴(yán)格的分形維數(shù)的定義如下： 如果一個(gè)集X的Hausdorff維數(shù)h(X)不是整數(shù)，則稱集全X是分形集。直觀地說，當(dāng)X?Rm，令n(?)為覆蓋X所需要的直徑為?的m維球的數(shù)量，如果當(dāng)?→0時(shí)n(?)的增加與?之間關(guān)系滿足,如式(1)所示。

n(ε)ε-D， 當(dāng)?→0，

(1)

(2)

其中，inf是指用直徑小于?>0的集合si組成對(duì)X的所有的有限覆蓋。md(X)可以為無，也可以為有限，其值取決于d的選取。F. Hausdorff曾經(jīng)證明存在唯一的非負(fù)實(shí)數(shù)d*(X)，其滿足如下性質(zhì)： 若0≤d≤d*(X)，則md(X)=∞，這說明測(cè)量的尺度太細(xì)小；若d8

h(X)=sup{d∈R+:md(X)=}

(3)

Hausdorff維數(shù)的基本思想是，對(duì)于任何一個(gè)有確定維數(shù)的幾何體，如果用與它相同維數(shù)的“尺”去量度，則可得到一確定的數(shù)值N；如果用低于它維數(shù)的“尺”去量它，結(jié)果為無窮大；如果用高于它維數(shù)的“尺”去量它，結(jié)果為零。其數(shù)字表達(dá)式為N(r)～r-DH，對(duì)其兩邊取自然對(duì)數(shù)，再進(jìn)行簡(jiǎn)單運(yùn)算后，可得式(4)。

DH=lnN(r)/ln(1/r)

(4)

式中DH就稱為Hausdorff維數(shù)。它可以是整數(shù)，也可以是分?jǐn)?shù)。

一般來說，如果要嚴(yán)格地計(jì)算Hausdorff維數(shù)是很困難的。自然界存在大量統(tǒng)計(jì)意義下的自相似體，通常并不知道其分形維數(shù)。為了解決這類自相似體的維數(shù)計(jì)算，產(chǎn)生了多種計(jì)算相似維數(shù)的方法，如結(jié)構(gòu)函數(shù)法、自仿射法以及盒子覆蓋法，這些計(jì)算方法性能各異。在實(shí)際應(yīng)用中，盒子覆蓋法因計(jì)算簡(jiǎn)單、性能較好、快速準(zhǔn)確,應(yīng)用比較廣泛。

設(shè)F是Rn的非空有界子集，Nr(F)是覆蓋F的長度至多為r的集合的個(gè)數(shù)。F的上、下盒計(jì)數(shù)維數(shù)分別定義為式(5)～式(7)。

則稱其公共值F的盒計(jì)數(shù)維或盒子維數(shù)

(7)

由于盒子維數(shù)的計(jì)算簡(jiǎn)便，在實(shí)際中應(yīng)用廣泛。例如為了得到平面集合F的盒維數(shù)，可以畫出每個(gè)小格長為r的正方形或盒網(wǎng)，對(duì)各個(gè)充分小的r計(jì)數(shù)覆蓋F的個(gè)數(shù)Nr(F)，維數(shù)是當(dāng)r→0時(shí)Nr(F)遞增的對(duì)數(shù)比率，可以用lnNr(F)與-lnr圖像的斜率來估計(jì)其值。

2 甲骨文字形的分形性質(zhì)

分形的基本特點(diǎn)是自相似性。所有的分形都具有一個(gè)重要的特征： 可以通過一個(gè)特征數(shù)，即分形維數(shù)來測(cè)定其不平度、復(fù)雜性或卷積度。由于書寫材料的質(zhì)地堅(jiān)硬、甲骨文創(chuàng)制人員的復(fù)雜，使得甲骨文字形的形態(tài)變化多樣。具體表現(xiàn)在不同的人對(duì)一個(gè)甲骨文字形有多種不同的刻寫方法，不同的契刻方法造就了不同的甲骨文形體，不同字形之間形體差別很大。體現(xiàn)在分形特點(diǎn)上，每個(gè)字形的分形特性也不一樣。具體表現(xiàn)是每個(gè)字形由于刻畫形狀不一樣，分形維數(shù)也會(huì)存在細(xì)微差別。不僅不同字形之間在分形特性上存在差異，就每一個(gè)具體字形來講，同一個(gè)字形由于每一部分筆畫形狀不一樣，每一部分字形的筆畫在分形特征上也存在差異。具體來說，如果將一個(gè)字形的重心為原點(diǎn)，建立平面直角坐標(biāo)系，則字形在平面上可以劃分為如下四個(gè)象限： 第一象限、第二象限、第三象限和第四象限，如圖1和圖2所示。

圖1 甲骨文字形“”及細(xì)化處理后的四個(gè)象限

圖2 甲骨文字形“”及細(xì)化處理后的四個(gè)象限

表1 甲骨文字形分形維數(shù)

從以上分析可見，甲骨文字形可由字形的分形維數(shù)以及第一、二、三、四象限的分形維數(shù)，即(d,d1，d2，d3，d4)描述。顯而易見，僅僅利用四個(gè)象限分形維數(shù)的有限組合，如1和4象限(d1，d4)或2和3象限(d2，d3)，或1和2象限(d1，d2)或3和4象限(d3，d4)，在識(shí)別字形的有效性上并不如(d,d1，d2，d3，d4)五元組向量識(shí)別甲骨文字形。實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 分形維數(shù)組合識(shí)別有效性對(duì)比

甲骨文字形每個(gè)象限的分形維數(shù)在甲骨文字庫中的分布如圖3所示。

圖3 分形維數(shù)分布

3 基于分形幾何的識(shí)別算法

從以上對(duì)甲骨文字形分形特點(diǎn)的描述可以看出，甲骨文字形可以利用其本身的分形維數(shù)來描述。分形配準(zhǔn)是將不同圖形的分形描述特征進(jìn)行匹配的過程。分形配準(zhǔn)可以定義如下：

給定兩幅待配準(zhǔn)的圖形的分形描述如下F1(x,y)和F2(x,y)，稱其中之一F1(x,y)為基準(zhǔn)分形，另一個(gè)F2(x,y)為待配準(zhǔn)分形，則稱分形配準(zhǔn)為兩分形關(guān)系的映射變換，如式(8)所示。

F1(x,y)=g[F2(x,y)]

(8)

在這里，g為一個(gè)二維坐標(biāo)變換。

分形配準(zhǔn)的一般步聚是： 首先對(duì)兩幅圖像進(jìn)行分形維數(shù)計(jì)算得到分形描述；通過進(jìn)行相似性度量找到匹配的分形描述。

分形特征提取是分形配準(zhǔn)的重要環(huán)節(jié)。準(zhǔn)確的分形特征提取為特征匹配的成功進(jìn)行提供了保障。因此，尋求具有良好不變性和準(zhǔn)確性的特征提取方法，對(duì)于匹配精度至關(guān)重要。如果能夠精確描述兩幅不同字形圖像的分形特征，就可以實(shí)現(xiàn)字形在分形關(guān)系上的配準(zhǔn)。

綜上所述，甲骨文字分形配準(zhǔn)算法如下：

Step1對(duì)輸入字形圖像進(jìn)行細(xì)化處理，得到細(xì)化后的字形圖像；

Step2通過計(jì)算甲骨文字形的分形維數(shù)，得到字形的分形描述；

Step3計(jì)算待識(shí)字形分形描述碼與甲骨文字形分形特征庫中分形碼(d)的距離；

Step4大于給定閾值的兩個(gè)分形描述碼的字形被識(shí)別為分形不等價(jià)，否則被識(shí)別為分形等價(jià)。如果兩個(gè)分形碼等價(jià)，并且識(shí)別結(jié)果出現(xiàn)重碼，則執(zhí)行Step5；

Step5計(jì)算待識(shí)字形分形描述碼與甲骨文字形分形特征庫中分形碼(d1,d4)、(d2，d3)、(d1，d2)、(d3，d4)的距離；

Step6大于給定閾值的兩個(gè)分形描述碼的字形被識(shí)別為分形不等價(jià)，否則被識(shí)別為分形等價(jià)。如果兩個(gè)分形碼等價(jià)，且識(shí)別結(jié)果出現(xiàn)重碼，則執(zhí)行Step7；

Step7計(jì)算待識(shí)字形分形描述碼與甲骨文字形分形特征庫中分形碼(d1，d2，d3,d4)的距離；

Step8大于給定閾值的兩個(gè)分形描述碼的字形被識(shí)別為分形不等價(jià)，否則被識(shí)別為分形等價(jià)。

甲骨文字形配準(zhǔn)識(shí)別系統(tǒng)識(shí)別甲骨文字形的流程如圖4所示。

在判定兩個(gè)分形描述碼是否等價(jià)的過程中，兩個(gè)字形的分形描述碼之間距離閾值的選取對(duì)于識(shí)別結(jié)果有著直接的影響。那么，閾值如何確定呢？一般來說，如果兩個(gè)甲骨文字形的分形描述碼等價(jià)，即屬于同一甲骨文字形，那么這兩個(gè)分形描述碼之間的距離要小于不同甲骨文字的分形描述碼的距離。甲骨文中，同一甲骨文字的異寫字形有很多，這些異寫字形之間的分形描述碼距離要小于其與另一甲骨文字分形描述碼的距離。因此，確定閾值的一個(gè)合理的解決辦法是，對(duì)每一個(gè)甲骨文字，計(jì)算此甲骨文字異寫字形之間分形描述碼的距離，在所有的甲骨文字中，找出兩個(gè)異寫字形的最大的分形描述碼的距離，此距離作為閾值。

用數(shù)學(xué)語言描述如下： 令T表示閾值，如式(9)所示。

T=max{maxC1，maxC2，…，maxCn}

(9)

其中maxCn表示甲骨文字Cn的異寫字形之間的分形描述碼距離的最大值。

圖4 甲骨文字形分形配準(zhǔn)識(shí)別流程圖

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

我們?cè)赪indows環(huán)境下主頻3.30GHz的雙處理器計(jì)算機(jī)上，利用Visual C++ 2010和OpenCV 3.0實(shí)現(xiàn)了以上算法，設(shè)計(jì)并實(shí)現(xiàn)了基于分形幾何的甲骨文字形自動(dòng)識(shí)別系統(tǒng)。系統(tǒng)的字庫平臺(tái)是Windows環(huán)境下自主開發(fā)的通用甲骨文字庫，字庫中的甲骨文字形采用基于二次Bezier曲線的輪廓描述技術(shù)。系統(tǒng)識(shí)別的步驟如下： 對(duì)輸入的圖形進(jìn)行細(xì)化處理后，由識(shí)別系統(tǒng)計(jì)算字形的分形維數(shù)，對(duì)字形進(jìn)行分形描述，得到字形的分形描述碼。通過計(jì)算待配準(zhǔn)字形的分形描述碼與分形特征庫中分形描述碼的距離，實(shí)現(xiàn)甲骨文字形的配準(zhǔn)識(shí)別。識(shí)別的結(jié)果在計(jì)算機(jī)屏幕上用曲線輪廓將甲骨文字形及對(duì)應(yīng)的漢字顯示出來。實(shí)驗(yàn)顯示，本文提出基于分形幾何的甲骨文字形識(shí)別算法，既可以識(shí)別目前已識(shí)讀的甲骨文字形，也能識(shí)別目前尚無法識(shí)讀的甲骨文字形，實(shí)驗(yàn)數(shù)據(jù)如表3所示。

表3 實(shí)驗(yàn)數(shù)據(jù)表

5 結(jié)論

甲骨文作為我國最古老的成熟文字系統(tǒng)，在科學(xué)研究、文化傳承方面具有極其重要的價(jià)值。作為最古老的文字系統(tǒng)，甲骨文只為少數(shù)專家學(xué)者所認(rèn)識(shí)，對(duì)于普通大眾來說甲骨文字形難寫難記，一般用戶對(duì)傳統(tǒng)的甲骨文字形編碼輸入方法很難掌握，使得編碼輸入方法的實(shí)用性受到很大限制。甲骨文字形作為一種平面圖形，由于書寫形體不同，在一定程度上具有分形性質(zhì)。本文利用分形幾何的原理，把甲骨文字形視為分形圖形，通過計(jì)算字形的分形維數(shù)以及平面圖形上四個(gè)象限內(nèi)部分的分形維數(shù)，利用一組分形描述碼將甲骨文字形表示出來，實(shí)現(xiàn)甲骨文字形描述的形式化。再通過將甲骨文字形的分形描述碼與分形特征庫進(jìn)行配準(zhǔn)，從而識(shí)別甲骨文字形。利用本文提出的算法設(shè)計(jì)了甲骨文字形識(shí)別系統(tǒng)，實(shí)驗(yàn)結(jié)果顯示，文章提出的算法是有效的。