基于分形幾何的甲骨文字形識別方法

顧紹通

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

0 引言

甲骨文是書寫在龜甲和獸骨上的文字，是我國迄今發現的最早的一種成熟文字系統。

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

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

1 分形幾何理論

普通幾何學研究的對象，一般都具有整數的維數。比如，零維的點、一維的線、二維的面、三維的立體、乃至四維的時空。分形幾何研究的是客觀事物具有自相似的層次結構，局部與整體在形態、功能、信息、時間、空間等方面具有統計意義上的相似性，成為自相似性。分形是關于自相似性的一般概念，由Mandelbrot[10]提出，用于描述具有相似結構的幾何形狀。分形理論認為維數也可以是分數，數學家從測度的角度引入了維數概念，將維數從整數擴大到分數，從而突破了一般拓撲集維數為整數的界限。

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

n(ε)ε-D， 當?→0，

(1)

(2)

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

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

(3)

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

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

(4)

式中DH就稱為Hausdorff維數。它可以是整數，也可以是分數。

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

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

則稱其公共值F的盒計數維或盒子維數

(7)

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

2 甲骨文字形的分形性質

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

圖1 甲骨文字形“”及細化處理后的四個象限

圖2 甲骨文字形“”及細化處理后的四個象限

表1 甲骨文字形分形維數

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

表2 分形維數組合識別有效性對比

甲骨文字形每個象限的分形維數在甲骨文字庫中的分布如圖3所示。

圖3 分形維數分布

3 基于分形幾何的識別算法

從以上對甲骨文字形分形特點的描述可以看出，甲骨文字形可以利用其本身的分形維數來描述。分形配準是將不同圖形的分形描述特征進行匹配的過程。分形配準可以定義如下：

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

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

(8)

在這里，g為一個二維坐標變換。

分形配準的一般步聚是： 首先對兩幅圖像進行分形維數計算得到分形描述；通過進行相似性度量找到匹配的分形描述。

分形特征提取是分形配準的重要環節。準確的分形特征提取為特征匹配的成功進行提供了保障。因此，尋求具有良好不變性和準確性的特征提取方法，對于匹配精度至關重要。如果能夠精確描述兩幅不同字形圖像的分形特征，就可以實現字形在分形關系上的配準。

綜上所述，甲骨文字分形配準算法如下：

Step1對輸入字形圖像進行細化處理，得到細化后的字形圖像；

Step2通過計算甲骨文字形的分形維數，得到字形的分形描述；

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

Step4大于給定閾值的兩個分形描述碼的字形被識別為分形不等價，否則被識別為分形等價。如果兩個分形碼等價，并且識別結果出現重碼，則執行Step5；

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

Step6大于給定閾值的兩個分形描述碼的字形被識別為分形不等價，否則被識別為分形等價。如果兩個分形碼等價，且識別結果出現重碼，則執行Step7；

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

Step8大于給定閾值的兩個分形描述碼的字形被識別為分形不等價，否則被識別為分形等價。

甲骨文字形配準識別系統識別甲骨文字形的流程如圖4所示。

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

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

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

(9)

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

圖4 甲骨文字形分形配準識別流程圖

4 實驗結果與分析

我們在Windows環境下主頻3.30GHz的雙處理器計算機上，利用Visual C++ 2010和OpenCV 3.0實現了以上算法，設計并實現了基于分形幾何的甲骨文字形自動識別系統。系統的字庫平臺是Windows環境下自主開發的通用甲骨文字庫，字庫中的甲骨文字形采用基于二次Bezier曲線的輪廓描述技術。系統識別的步驟如下： 對輸入的圖形進行細化處理后，由識別系統計算字形的分形維數，對字形進行分形描述，得到字形的分形描述碼。通過計算待配準字形的分形描述碼與分形特征庫中分形描述碼的距離，實現甲骨文字形的配準識別。識別的結果在計算機屏幕上用曲線輪廓將甲骨文字形及對應的漢字顯示出來。實驗顯示，本文提出基于分形幾何的甲骨文字形識別算法，既可以識別目前已識讀的甲骨文字形，也能識別目前尚無法識讀的甲骨文字形，實驗數據如表3所示。

表3 實驗數據表

5 結論

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