基于拓?fù)渑錅?zhǔn)的甲骨文字形識別方法*

顧紹通

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

?

基于拓?fù)渑錅?zhǔn)的甲骨文字形識別方法*

顧紹通

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

甲骨文字形具備較為穩(wěn)定的拓?fù)浣Y(jié)構(gòu)特征,雖然異體字較多,但是同一字形的不同寫法具有一定的拓?fù)浞€(wěn)定性,這使得從字形上區(qū)分不同的甲骨文字形成為可能。文章通過分析甲骨文字形的拓?fù)涮卣?研究甲骨文字形的拓?fù)漤旤c(diǎn)及拓?fù)漤旤c(diǎn)之間的拓?fù)潢P(guān)系,建立了拓?fù)漤旤c(diǎn)間拓?fù)潢P(guān)系的拓?fù)涿枋?將圖畫性質(zhì)的甲骨文字形轉(zhuǎn)化為拓?fù)鋱D形,并對拓?fù)鋱D形進(jìn)行編碼,實(shí)現(xiàn)了甲骨文字形拓?fù)浣Y(jié)構(gòu)的形式化描述。

拓?fù)渑錅?zhǔn); 拓?fù)浣Y(jié)構(gòu); 拓?fù)漤旤c(diǎn); 拓?fù)潢P(guān)系; 拓?fù)渚幋a; 甲骨文; 字形識別

Class NumberTP391

1　引言

甲骨文是書寫在龜甲和獸骨上的文字,是我國迄今發(fā)現(xiàn)的最早的一種成熟文字系統(tǒng)。出土甲骨拓片上的甲骨文字形中,大部分字形無法正確辨識其讀音和意義,已有的甲骨文編碼輸入方法存在規(guī)則繁瑣、重碼多、效率低的局限[1～3],要讓一般用戶掌握其復(fù)雜的規(guī)則并不現(xiàn)實(shí),只有少數(shù)從事甲骨文研究方面的專家學(xué)者才能掌握復(fù)雜的編碼規(guī)則,因而實(shí)用性并不強(qiáng)。對于現(xiàn)代漢字已出現(xiàn)多種識別方法,大致可分為基于結(jié)構(gòu)模式的方法和基于統(tǒng)計(jì)模式的方法?；诮Y(jié)構(gòu)模式的識別方法,如隱馬爾科夫模型[4]等,基于統(tǒng)計(jì)模式的識別方法,如貝葉斯決策的分類方法[5]等。這些方法都是針對現(xiàn)代漢字特點(diǎn)提出的識別方法,對于和現(xiàn)代漢字具有巨大差別的甲骨文字形識別適應(yīng)性存在局限性。甲骨文是刻寫在龜甲和獸骨上的文字,其構(gòu)成方式主要有象形、指事、形聲、會意等四種,其中象形字占大多數(shù),這就決定了大多數(shù)甲骨文字形具有圖畫性,即使是一些會意字、形聲字也是以象形字為基礎(chǔ),大都具有圖畫性,這也決定了甲骨文筆畫繁多、構(gòu)造復(fù)雜的特點(diǎn)；同時(shí)甲骨文的字形剛勁有力,筆端尖細(xì),難以區(qū)分筆畫,只能作為一個(gè)整體進(jìn)行處理。針對甲骨文字形本身的特點(diǎn),目前,已有學(xué)者已提出甲骨文字形的識別方法,如周新倫(1996)[6]提出利用圖論和筆劃特點(diǎn)來識別甲骨文字形的方法,李鋒(1996)[7]提出利用圖特征的原理來識別甲骨文字形的方法；利用圖特征來識別甲骨文取得了不錯(cuò)的效果。栗青生(2011)等[8]提出利用圖同構(gòu)的方法來識別甲骨文字形,這種方法對于那些甲骨文中不同構(gòu)但是仍為同一字形的異寫字的識別沒有進(jìn)行處理,而且雖然同構(gòu)但是卻不是同一個(gè)字形的情況大量存在,這種算法的魯棒性很低,因而實(shí)用性受到限制。

甲骨文的特色不僅在于是我國最早的成熟的文字系統(tǒng)以及它獨(dú)特的書寫材料,還在于它形成了中國文字體系結(jié)構(gòu)的雛形。由于書寫材料的質(zhì)地堅(jiān)硬、甲骨文創(chuàng)制人員的復(fù)雜,使得甲骨文字形的形態(tài)變化多樣,具體表現(xiàn)在一個(gè)甲骨文字形不同的人有多種不同的刻寫方法,不同的契刻方法造就了不同的甲骨文形體,有些形體之間差別還很大。但是如果仔細(xì)觀察這些不同形體的甲骨文字形就會發(fā)現(xiàn),不同形體之間雖然筆畫順序以及組合關(guān)系不同,但是它們之間的大體結(jié)構(gòu)卻是相似的,現(xiàn)代的學(xué)者能將不同形體的甲骨文字形歸為一類,很大的原因在于字形之間結(jié)構(gòu)的相似性,也就是同一甲骨文字形的不同形體之間在拓?fù)浣Y(jié)構(gòu)上具有同一性。本文將考察甲骨文字形拓?fù)浣Y(jié)構(gòu)的特點(diǎn),并將甲骨文字形的拓?fù)涮卣餍问交?從拓?fù)涮卣魃蠈で笞R別甲骨文字形的方法。

本文將首先分析甲骨文字形的拓?fù)漤旤c(diǎn)及拓?fù)漤旤c(diǎn)之間的拓?fù)潢P(guān)系,建立甲骨文字形的拓?fù)涿枋?構(gòu)造甲骨文字形的拓?fù)鋱D形(從字形抽象出來的的拓?fù)漤旤c(diǎn)之間連結(jié)構(gòu)成的圖形),將圖畫性質(zhì)的甲骨文字形轉(zhuǎn)化為拓?fù)鋱D形；然后對甲骨文字形的拓?fù)鋱D形進(jìn)行編碼,通過對甲骨文字形的拓?fù)渚幋a與通用甲骨文字庫中字形的拓?fù)涮卣鲙爝M(jìn)行配準(zhǔn),實(shí)現(xiàn)甲骨文字形的識別。

2　甲骨文字形結(jié)構(gòu)的拓?fù)浔磉_(dá)

2.1拓?fù)鋵W(xué)的一般知識

拓?fù)鋵W(xué)最初是幾何學(xué)的一個(gè)分支,是從圖論演變過來的。拓?fù)鋵W(xué)將實(shí)體抽象成與其大小、形狀無關(guān)的點(diǎn),將連接實(shí)體的線路抽象成線,進(jìn)而研究點(diǎn)、線、面之間的關(guān)系。簡單地說,拓?fù)鋵W(xué)主要研究幾何圖形在連續(xù)變形下保持不變的性質(zhì),現(xiàn)在已成為研究連續(xù)性現(xiàn)象的重要的數(shù)學(xué)分支。直線上的點(diǎn)和線的結(jié)合關(guān)系、順序關(guān)系,在拓?fù)渥儞Q下不變,這是拓?fù)湫再|(zhì)。

設(shè)X和Y是拓?fù)淇臻g,如果f:x→y是一一映射,并且f及其逆g:y→x都是連續(xù)的,則稱f是一個(gè)拓?fù)渥儞Q,或稱同胚映射。 當(dāng)存在x到y(tǒng)的拓?fù)渥儞Q時(shí),稱x與y拓?fù)涞葍r(jià),或稱同胚,記作X?Y。例如圖1中的各圖形雖然形狀各異,但是它們?nèi)匀皇峭負(fù)涞葍r(jià)的。

圖1　 拓?fù)涞葍r(jià)示意圖

拓?fù)洳蛔兞渴峭負(fù)淇臻g一個(gè)比較重要的拓?fù)湫再|(zhì),它描述了彈性變化,如拉伸、旋轉(zhuǎn)和縮放等條件下不變的性質(zhì)。

拓?fù)鋵W(xué)中比較簡單的拓?fù)洳蛔兞坑校?/p>

1)連通性及連通支的個(gè)數(shù)。從直觀上來說,連在一起的圖形是連通的,如果圖形是由幾個(gè)不相連接的部分組成的,則圖形是不連通的,組成圖形的互不連接的部分的數(shù)目稱為連通支的個(gè)數(shù)。連通支的個(gè)數(shù)是1時(shí),圖形是連通的。連通支的個(gè)數(shù)是一個(gè)拓?fù)洳蛔兞俊?/p>

2)割點(diǎn)的個(gè)數(shù)。在一個(gè)圖形上有這樣的點(diǎn),去掉該點(diǎn)后,余下的是一個(gè)不連通的圖形,具有這種性質(zhì)的點(diǎn),稱為圖形的割點(diǎn)?！案铧c(diǎn)”的概念是一個(gè)拓?fù)湫再|(zhì),割點(diǎn)在同胚映射下的象點(diǎn)仍然是割點(diǎn)。因而,割點(diǎn)的個(gè)數(shù)是一個(gè)拓?fù)洳蛔兞俊?/p>

3)點(diǎn)的指數(shù)。設(shè)一個(gè)圖形是由有限條弧組成的,x是這個(gè)圖形的點(diǎn),從x點(diǎn)引出的該圖形的弧的個(gè)數(shù),叫做點(diǎn)x在該圖形中的指數(shù)。

對于給定的兩個(gè)拓?fù)淇臻gX與Y,如果要證明它們是拓?fù)涞葍r(jià)的,只需要構(gòu)造出從X到Y(jié)的同胚映射即可。若要證明給定的兩個(gè)拓?fù)淇臻g是不同胚的,可以通過尋找拓?fù)洳蛔兞?如果這兩個(gè)拓?fù)淇臻g的拓?fù)洳蛔兞渴遣幌嗤?那么就可以認(rèn)為這兩個(gè)拓?fù)淇臻g是不同胚的,即拓?fù)洳坏葍r(jià)。

由此可見,證明兩個(gè)圖形同胚,需要找出同胚映射,或者借助于橡皮變形能將一個(gè)變成另一個(gè)。如果兩個(gè)圖形是同胚的,那么這兩個(gè)圖形就是拓?fù)涞葍r(jià)的,即拓?fù)浣Y(jié)構(gòu)是相同的。

2.2甲骨文字形的拓?fù)漤旤c(diǎn)

字形是指構(gòu)成每一個(gè)方塊漢字的二維平面圖形。構(gòu)成漢字拓?fù)淇臻g的要素是筆畫及其位置關(guān)系。筆畫是構(gòu)成漢字字形的最小連筆單位,落筆處為筆畫的起點(diǎn),提筆處為筆畫的終點(diǎn)。直線上的點(diǎn)和線的結(jié)合關(guān)系、順序關(guān)系,在拓?fù)渥儞Q下不變,這是拓?fù)湫再|(zhì)。甲骨文作為漢字的一種早期形態(tài),從本質(zhì)上來說,是一種平面圖形,層次性不強(qiáng),存在構(gòu)形復(fù)雜,異寫字、異構(gòu)字繁多等特點(diǎn),比如“犬”在甲骨文中的形態(tài)有一百多種。但是,我們?nèi)匀荒軌蛘J(rèn)知這一百多個(gè)不同形態(tài)的“犬”字,正是因?yàn)榧坠俏木邆淞送負(fù)浣Y(jié)構(gòu)不變性的特征。判斷兩個(gè)甲骨文字形是否在拓?fù)渖系葍r(jià),可以轉(zhuǎn)化為判斷兩個(gè)甲骨文字形在拓?fù)渖夏芊衽錅?zhǔn)。

圖2是甲骨文字形“貞”的圖像,圖3是經(jīng)過細(xì)化處理后的圖像。甲骨文筆劃線條相交的地方形成交點(diǎn),甲骨文筆劃的交點(diǎn)和字形筆劃的端點(diǎn)統(tǒng)稱為頂點(diǎn)。如圖4所示。從圖4可以看出,甲骨文字形的拓?fù)漤旤c(diǎn)是指筆劃線條的交點(diǎn)以及甲骨文字形筆劃的端點(diǎn)。甲骨文字形經(jīng)過細(xì)化處理后,成為由細(xì)線條連接而成的圖形。根據(jù)周新倫等(1996)[6]的研究,在目前已考證出的甲骨文字形中,指數(shù)高于6的頂點(diǎn)尚未發(fā)現(xiàn)。因而,甲骨文字形的拓?fù)漤旤c(diǎn)可以分為以下7類：孤立點(diǎn)、端點(diǎn)、二叉點(diǎn)、三叉點(diǎn)、四叉點(diǎn)、五叉點(diǎn)和六叉點(diǎn)。孤立點(diǎn)是甲骨文字形拓?fù)鋱D形中指數(shù)為0的頂點(diǎn),即沒有邊與之連接,端點(diǎn)是甲骨文字形拓?fù)鋱D形中指數(shù)為1的頂點(diǎn),二叉點(diǎn)是甲骨文字形拓?fù)鋱D形中指數(shù)為2的頂點(diǎn),三叉點(diǎn)、四叉點(diǎn)、五叉點(diǎn)、六叉點(diǎn)依此類推。從指數(shù)上看,甲骨文字形的頂點(diǎn)有7類,由排列組合關(guān)系知,甲骨文字形中兩個(gè)頂點(diǎn)之間的連接關(guān)系可達(dá)7+6+5+4+3+2+1=28種。圖4中標(biāo)號1、5、7、10、12、13的點(diǎn)是端點(diǎn),標(biāo)號2、3、9、11的點(diǎn)是三叉點(diǎn),標(biāo)號8、14的點(diǎn)是四叉點(diǎn)。圖4中甲骨文字形的頂點(diǎn)連接關(guān)系可以分為以下幾類： 1) 端點(diǎn)與三叉點(diǎn)連接,如圖4中頂點(diǎn)1與頂點(diǎn)2、頂點(diǎn)5與頂點(diǎn)4、頂點(diǎn)7與頂點(diǎn)6、頂點(diǎn)10與頂點(diǎn)9、頂點(diǎn)12與頂點(diǎn)11、頂點(diǎn)13與頂點(diǎn)14的關(guān)系即屬于此類； 2) 端點(diǎn)與四叉點(diǎn)連接,圖4中頂點(diǎn)13與頂點(diǎn)14的關(guān)系屬于此類； 3) 三叉點(diǎn)與三叉點(diǎn)連接,如圖4中頂點(diǎn)2與頂點(diǎn)3、頂點(diǎn)3與頂點(diǎn)4、頂點(diǎn)4與頂點(diǎn)6、頂點(diǎn)9與頂點(diǎn)11； 4) 三叉點(diǎn)與四叉點(diǎn)連接,圖4中頂點(diǎn)2與頂點(diǎn)14、頂點(diǎn)3與頂點(diǎn)8、頂點(diǎn)6與頂點(diǎn)8、頂點(diǎn)9與頂點(diǎn)8、頂點(diǎn)11與頂點(diǎn)14的關(guān)系屬于這一類； 5) 四叉點(diǎn)與四叉點(diǎn)連接,圖4中頂點(diǎn)8與頂點(diǎn)14即屬此類。對甲骨文字形的頂點(diǎn)進(jìn)行進(jìn)一步抽象,便得到甲骨文字形的拓?fù)鋱D形,甲骨文字形“貞”的拓?fù)鋱D形如圖5所示。

圖2　甲骨文字形“貞”

圖3　細(xì)化后的字形

圖4　細(xì)化字形“貞”的拓?fù)漤旤c(diǎn)

圖5　“貞”的拓?fù)鋱D形

提取字形圖像的拓?fù)漤旤c(diǎn)的過程如下：先對字形圖像進(jìn)行細(xì)化處理,按照從上到下順序掃描細(xì)化后字形圖像的每一行的像素,對每一個(gè)像素應(yīng)用八連通模板進(jìn)行判斷,如果像素在所有方向均無連通區(qū)域,則這一點(diǎn)為孤立點(diǎn)；如果像素只在一個(gè)方向存在連通區(qū)域,則這一點(diǎn)為端點(diǎn)；如果像素在三個(gè)方向存在連通區(qū)域,則為三叉點(diǎn)。四叉點(diǎn)、五叉點(diǎn)、六叉點(diǎn)依此類推。二叉點(diǎn)是指數(shù)為2的頂點(diǎn),這類頂點(diǎn)在甲骨文字形中比較特殊。由于甲骨文書寫材料的獨(dú)特性以及甲骨文創(chuàng)制人員的復(fù)雜,使得甲骨文形態(tài)變化多樣,一個(gè)甲骨文字形不同的人有多種不同的刻寫方法,不同的契刻方法造就了不同的甲骨文形體。如果仔細(xì)觀察這些不同形體的甲骨文字形就會發(fā)現(xiàn),不同形體之間雖然筆畫順序以及組合關(guān)系不同,但是它們之間的大體結(jié)構(gòu)卻是相似的。從拓?fù)浣Y(jié)構(gòu)上來說,二叉點(diǎn)和弧線段、直線段不存在拓?fù)渖系膮^(qū)別,但是有些二叉點(diǎn)卻不宜與弧線段、直線段等同。因此,在具體處理中,需要對這兩類二叉點(diǎn)區(qū)別對待。對于夾角大于90度的二叉點(diǎn),可以將此二叉點(diǎn)關(guān)聯(lián)的邊視為弧線段或直線段。只需對夾角小于或等于90度的二叉點(diǎn)加以處理。由此可見,某些二叉點(diǎn)雖然可以顯示字形刻寫時(shí)形體上的差異,但并不一定能構(gòu)成不同的甲骨文。對于字形的拓?fù)浣Y(jié)構(gòu)來說,也不會產(chǎn)生變化。

從以上對甲骨文字形頂點(diǎn)的分析可以看出,甲骨文字形拓?fù)漤旤c(diǎn)之間的拓?fù)潢P(guān)系可以表述為各頂點(diǎn)之間的連接關(guān)系。這種拓?fù)潢P(guān)系由甲骨文字形的各拓?fù)漤旤c(diǎn)以及拓?fù)漤旤c(diǎn)相互之間的連接關(guān)系唯一確定。因而甲骨文字形拓?fù)潢P(guān)系包括拓?fù)漤旤c(diǎn)的數(shù)目及拓?fù)漤旤c(diǎn)之間的連接關(guān)系。具有相同數(shù)目的拓?fù)漤旤c(diǎn)以及相同連接關(guān)系的拓?fù)淇臻g之間可以建立一個(gè)同胚映射關(guān)系,因而是拓?fù)涞葍r(jià)的。由此可見,拓?fù)漤旤c(diǎn)數(shù)量相同,拓?fù)漤旤c(diǎn)之間的連接關(guān)系不一定相同；拓?fù)漤旤c(diǎn)數(shù)量不同,拓?fù)漤旤c(diǎn)之間的連接關(guān)系必不相同；拓?fù)漤旤c(diǎn)之間的連接關(guān)系相同,拓?fù)漤旤c(diǎn)數(shù)量必相同；拓?fù)漤旤c(diǎn)之間的連接關(guān)系不同,拓?fù)漤旤c(diǎn)的數(shù)量未必不同。所以,如果兩個(gè)字形的拓?fù)漤旤c(diǎn)數(shù)量相同,并且拓?fù)漤旤c(diǎn)之間的連接關(guān)系也相同的話,那么這兩個(gè)字形一定是同一個(gè)字形。但是,甲骨文字形是一種字形結(jié)構(gòu)不穩(wěn)定的字形,同一個(gè)字有很多不同的寫法,造成甲骨文中存在很多的異寫字,拓?fù)漤旤c(diǎn)的數(shù)量、拓?fù)漤旤c(diǎn)之間的連接關(guān)系不同的字形卻可能是同一個(gè)字,例如：與雖然拓?fù)浣Y(jié)構(gòu)不相同,但在甲骨文中卻是同一個(gè)字“師”。

甲骨文字形的細(xì)化處理是提取甲骨文字形拓?fù)漤旤c(diǎn)的基礎(chǔ)和先決條件,對于拓?fù)漤旤c(diǎn)的分析至關(guān)重要,沒有甲骨文字形的細(xì)化處理便無法準(zhǔn)確分析字形的拓?fù)漤旤c(diǎn)。目前,圖像細(xì)化的處理算法有很多,大體上可以分為串行細(xì)化算法和并行細(xì)化算法。串行細(xì)化算法如Hilditch細(xì)化算法[9]、Pavlidis算法[10],并行細(xì)化算法如Rosenfeld細(xì)化算法[11],Zhang并行快速細(xì)化算法[12]等,Zhang并行快速細(xì)化算法細(xì)化之后的輪廓走勢與原圖保持得相對較好。因此,對于甲骨文字形的細(xì)化處理,本文采用Zhang并行快速細(xì)化算法。

2.3拓?fù)渚幋a

甲骨文字形的拓?fù)渚幋a就是給甲骨文字形的每一種拓?fù)浣Y(jié)構(gòu)進(jìn)行形式化的表達(dá),通過這種形式化的表達(dá),可以比較兩個(gè)拓?fù)浣Y(jié)構(gòu)的異同。這種編碼應(yīng)該能夠描述甲骨文字形的結(jié)構(gòu)關(guān)系。在甲骨文字形拓?fù)漤旤c(diǎn)的各種連接關(guān)系中,端點(diǎn)與三叉點(diǎn)以及端點(diǎn)與四叉點(diǎn)的連接關(guān)系比較特殊。甲骨文中異體字繁多,存在正反無別的現(xiàn)象,由于甲骨文是由不同的書寫者在不同的時(shí)期所作,因而對于同一字形書寫方式各異,比如圖6中a、b是同一個(gè)甲骨文字形“安”不同寫法的細(xì)化圖像。在圖6a中端點(diǎn)與三叉點(diǎn)、四叉點(diǎn)的連接現(xiàn)象在圖6b中消失了,但這并不妨礙我們把他們視為同一個(gè)甲骨文字形。因而甲骨文字形拓?fù)浣Y(jié)構(gòu)的編碼應(yīng)該具有這樣的容錯(cuò)性和魯棒性。由此可見,端點(diǎn)在甲骨文字形拓?fù)浣Y(jié)構(gòu)中并不是一個(gè)非常重要的因素。由定義可知,不同的叉點(diǎn)關(guān)聯(lián)的邊的數(shù)目不同,體現(xiàn)在拓?fù)浣Y(jié)構(gòu)上也必不相同,因此他們的權(quán)值也不相同。可以預(yù)見,W1

圖6　甲骨文字形“安”的細(xì)化圖像

令Nv、Ne、N0、N1、N2、N3、N4、N5、N6分別表示拓?fù)鋱D形的頂點(diǎn)、邊、孤立點(diǎn)(0叉點(diǎn))、端點(diǎn)(1叉點(diǎn))、二叉點(diǎn)、三叉點(diǎn)、四叉點(diǎn)、五叉點(diǎn)、六叉點(diǎn)的數(shù)目,N表示各叉點(diǎn)的權(quán)值之和,T表示甲骨文字形C的拓?fù)渚幋a,R表示拓?fù)漤旤c(diǎn)之間的連接關(guān)系。那么一個(gè)甲骨文字形的拓?fù)浣Y(jié)構(gòu)的編碼可以用一個(gè)4元組表示為

T(C)=(f1,f2,N,R)

其中,f1、f2分別為連通支、割點(diǎn)的數(shù)目,N=0×N0+0.1×N1+0.2×N2+0.3×N3+0.4×N4+0.5×N5+0.6×N6。R表示拓?fù)漤旤c(diǎn)之間的連接關(guān)系,可以用無向圖描述如下：設(shè)G=(Nv,Ne)是具有Nv個(gè)頂點(diǎn)、Ne條邊的圖。G的鄰接矩陣是具有如下性質(zhì)的n階方陣：

2.4甲骨文字形拓?fù)漤旤c(diǎn)關(guān)系的數(shù)據(jù)結(jié)構(gòu)描述及

拓?fù)渑錅?zhǔn)算法

從以上對甲骨文字形拓?fù)漤旤c(diǎn)關(guān)系的描述可以看出,決定甲骨文字形拓?fù)浣Y(jié)構(gòu)關(guān)系的要素有：連通支、頂點(diǎn)以及頂點(diǎn)之間的連接關(guān)系。頂點(diǎn)包括孤立點(diǎn)、端點(diǎn)、二叉點(diǎn)、三叉點(diǎn)、四叉點(diǎn)、五叉點(diǎn)和六叉點(diǎn)。根據(jù)甲骨文字形的拓?fù)浣Y(jié)構(gòu)關(guān)系,甲骨文字形拓?fù)鋱D形的形式化描述可以通過建立拓?fù)漤旤c(diǎn)、連接矩陣等要素之間的數(shù)學(xué)關(guān)系來實(shí)現(xiàn)。

拓?fù)渑錅?zhǔn)是將不同圖形的拓?fù)浣Y(jié)構(gòu)進(jìn)行匹配的過程,其一般步聚是：首先對兩幅圖像進(jìn)行特征提取得到拓?fù)漤旤c(diǎn)；根據(jù)拓?fù)漤旤c(diǎn)之間的連續(xù)關(guān)系構(gòu)造拓?fù)潢P(guān)系圖；對拓?fù)潢P(guān)系圖進(jìn)行量化編碼；通過進(jìn)行相似性度量找到匹配的拓?fù)潢P(guān)系圖。

拓?fù)渑錅?zhǔn)可以定義如下：給定兩幅待配準(zhǔn)的圖形的拓?fù)浣Y(jié)構(gòu)如下T1(x,y)和T2(x,y),稱其中之一T1(x,y)為基準(zhǔn)拓?fù)?另一個(gè)T2(x,y)為待配準(zhǔn)拓?fù)?則稱拓?fù)渑錅?zhǔn)為兩拓?fù)潢P(guān)系的映射變換。

T2(x,y)=g(T1(x,y))

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

特征提取和拓?fù)淞炕幋a是拓?fù)渑錅?zhǔn)的重要環(huán)節(jié)。特征提取是配準(zhǔn)技術(shù)中的關(guān)鍵,準(zhǔn)確的特征提取為特征匹配的成功進(jìn)行提供了保障。因此,尋求具有良好不變性和準(zhǔn)確性的特征提取方法,對于匹配精度至關(guān)重要。如果能夠精確描述兩幅不同字形圖像的拓?fù)涮卣?就可以實(shí)現(xiàn)字形在拓?fù)潢P(guān)系上的配準(zhǔn)。

綜上所述,甲骨文字形拓?fù)鋱D形的配準(zhǔn)算法如下：

Step1:提取字形圖形的拓?fù)漤旤c(diǎn)；

Step2:構(gòu)造拓?fù)漤旤c(diǎn)之間的拓?fù)潢P(guān)系；

Step3:對字形的拓?fù)潢P(guān)系進(jìn)行量化編碼；

Step4:計(jì)算基準(zhǔn)拓?fù)渑c待配準(zhǔn)拓?fù)渲g的距離；

Step5:小于給定閾值的兩個(gè)拓?fù)溟g距離的字形圖形被識別為拓?fù)涞葍r(jià),否則拓?fù)洳坏葍r(jià)。

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

圖7　甲骨文字形配準(zhǔn)識別

在判定兩個(gè)拓?fù)溟g是否等價(jià)的過程中,基準(zhǔn)拓?fù)渑c待配準(zhǔn)拓?fù)渲g的距離的閾值的選取對于識別結(jié)果有著直接的影響。那么,閾值如何確定呢？一般來說,如果兩個(gè)甲骨文字形的拓?fù)鋱D形等價(jià),即屬于同一甲骨文,那么這兩個(gè)拓?fù)鋱D形之間的距離要小于不同甲骨文字的拓?fù)鋱D形的距離。甲骨文中,同一甲骨文字的異寫字形有很多,這些異寫字形之間的拓?fù)渚嚯x要小于其與另一甲骨文字拓?fù)鋱D形的距離。因此,確定閾值的一個(gè)合理的解決辦法是,對每一個(gè)甲骨文字,計(jì)算此甲骨文字異寫字形之間拓?fù)渚嚯x的值,在所有的甲骨文字中,找中兩個(gè)異寫字形的最大的拓?fù)渚嚯x,此距離作為閾值。

用數(shù)學(xué)語言描述如下：令T表示閾值,則

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

其中maxCn表示甲骨文字Cn的異寫字形之間拓?fù)渚嚯x的最大值。

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

我們在Windows環(huán)境下主頻2.60GHz的計(jì)算機(jī)上,利用Visual C++ 6.0和OpenCV 1.0實(shí)現(xiàn)了上文提出的算法,設(shè)計(jì)了甲骨文字形自動識別系統(tǒng)。該系統(tǒng)的字庫平臺是自主開發(fā)的通用甲骨文 字庫,該TTF格式字庫建立在Windows環(huán)境下,字形采用基于二 次Bezier曲線的輪廓描述技術(shù),字庫含有甲骨文字形3673個(gè)。系統(tǒng)識別流程如下：對輸入的圖形進(jìn)行細(xì)化處理后,由識別系統(tǒng) 提取細(xì)化后圖形的頂點(diǎn),構(gòu)造甲骨文字形圖形的拓?fù)鋱D形,然后對拓?fù)鋱D形進(jìn)行數(shù)學(xué)描述。通過計(jì)算待配準(zhǔn)拓?fù)渑c拓?fù)涮卣鲙熘型負(fù)渚幋a的距離,實(shí)現(xiàn)甲骨文字形的配準(zhǔn)識別。識別的結(jié)果在計(jì)算機(jī)屏幕上用曲線輪廓甲骨文字形及對應(yīng)的漢字顯示出來,對于無法與現(xiàn)代漢字對應(yīng)的字形直接顯示曲線輪廓甲骨文字形。該識別系統(tǒng)對于甲骨文中的異寫字具有一定的容錯(cuò)性和魯棒性。實(shí)驗(yàn)結(jié)果表明,本文提出的算法,既可以識別目前已識讀的甲骨文字形,也能夠識別目前尚無法識讀的甲骨文字形。

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

4　結(jié)語

甲骨文作為我國最古老的成熟的系統(tǒng)文字體系,已經(jīng)具備了較為穩(wěn)定的拓?fù)浣Y(jié)構(gòu)特征,奠定了漢字形體拓?fù)浣Y(jié)構(gòu)的雛形。甲骨文字形異體字較多,但是同一字形的不同寫法的拓?fù)涮卣骶哂蟹€(wěn)定性,這也使得今天的人們能夠從字形上區(qū)分不同的甲骨文字形。甲骨文字形的結(jié)構(gòu)可以由構(gòu)成甲骨文字形的拓?fù)漤旤c(diǎn)唯一確定。拓?fù)漤旤c(diǎn)之間不同的組合關(guān)系形成了不同的甲骨文字形。本文分析了甲骨文字形的拓?fù)浣Y(jié)構(gòu),確定甲骨文字形的拓?fù)漤旤c(diǎn),具體分析了甲骨文字形拓?fù)漤旤c(diǎn)之間的拓?fù)潢P(guān)系,通過對拓?fù)漤旤c(diǎn)、拓?fù)潢P(guān)系、拓?fù)渚幋a相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來刻畫甲骨文字形頂點(diǎn)之間的關(guān)系,將圖畫性質(zhì)的甲骨文字形轉(zhuǎn)化為拓?fù)鋱D形,并對每種拓?fù)鋱D形進(jìn)行編碼,實(shí)現(xiàn)了對甲骨文字形的拓?fù)涿枋?。在此基礎(chǔ)上,利用拓?fù)渑錅?zhǔn)的方法,通過計(jì)算基準(zhǔn)拓?fù)渑c待配準(zhǔn)拓?fù)渲g的歐氏距離,實(shí)現(xiàn)基于拓?fù)浣Y(jié)構(gòu)的甲骨文字形的配準(zhǔn),從而識別甲骨文字形。

[1] 顧紹通,馬小虎,楊亦鳴.基于字形拓?fù)浣Y(jié)構(gòu)的甲骨文輸入編碼研究[J].中文信息學(xué)報(bào),2008,22(4):123-128.

GU Shaotong, MA Xiaohu, YANG Yiming.Topological Frame Based Input Method Coding of Jiaguwen[J].Journal of Chinese Information Processing,2008,22(4):123-128.

[2] 李繼明.計(jì)算機(jī)文字信息處理技術(shù)新探——甲骨文象形碼設(shè)計(jì)方案[J].中文信息學(xué)報(bào),1996,10(3):18-29.

LI Jiming. A newly discovery on words processing technology——The design of pictographic code to inscriptions on bones or tortoise shells[J].Journal of Chinese Information Processing,1996,10(3):18-29.

[3] 肖明,趙慧,甘仲惟.甲骨文象形碼編碼方法研究[J].中文信息學(xué)報(bào),2003,17(5):60-65.

XIAO Ming, ZHao Hui, GAN Zhongwei. Study for the method of Jiaguwen symbol coding[J]. Journal of Chinese Information Processing,2003,17(5):60- 65.

[4] 劉家鋒,唐健華,黃降龍.基于HMM的聯(lián)機(jī)漢字識別系統(tǒng)及其改進(jìn)的訓(xùn)練方法[J].中文信息學(xué)報(bào),2001,15(4):47-52.

LIU Jiafeng,TANG Jianhua,HUANG Xianglong. A HMM based on-line Chinese character recognition system and improved training algorithm[J].Journal of Chinese Information Processing,2001,15(4):47-52.

[5] 藺志青,郭軍.貝葉斯分類器在手寫漢字識別中的應(yīng)用[J].電子學(xué)報(bào),2000,30(12)：1804-1807.

LIN Zhiqing,GUO Jun. An application of Bayesian classifier in the recognition of handwritten Chinese character[J].Acta Electronica Sinica, 2000,30(12):1804-1807.

[6] 周新倫,李鋒,華星城,等.甲骨文計(jì)算機(jī)識別方法研究[J].復(fù)旦學(xué)報(bào)(自然科學(xué)版),1996,35(5)：481-486.

ZHOU Xinlun, LI Feng, HUA Xingcheng, et al. A method of Jia Gu Wen recognition based on a two-level classification[J].Journal of Fudan University(Normal Science),1996,35(5):481-486.

[7] 李鋒,周新倫.甲骨文自動識別的圖論方法[J].電子科學(xué)學(xué)刊,1996,18(增刊)：41-47.

LI Feng,ZHOU Xinlun. Recognition of Jia Wu Wen based on graph theory[J].Journal of Electronics,1996,18(supplied):41-47.

[8] 栗青生,楊玉星,王愛民.甲骨文識別的圖同構(gòu)方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(8)：112-114.

LI Qingsheng,YANG Yuxing,WANG Aimin.Recognition of inscriptions on bones or tortoise shells based on graph isomorphism[J].Computer Engineering and Application, 2011,47(8):112-114.

[9] Hilditch C J. Linear Skeletons from Square Cupboards[A].In:Meltzer,B. and Michie,D. eds,Machine Intelligence,New York:Elsevier,1969:403-420.

[10] Pavlidis T. A thinning algorithm for discrete binary images[J]. Computer Graphics and Image Processing,1980,13(2):142-157.

[11] Rosenfeld A. A characterization of parallel thinning algorithms[J]. Information Control,1975,29(3):286-291.

[12] Zhang T Y,Suen C Y. A fast parallel algorithm for thinning digital patterns[J]. Communications of the ACM,1984,27(3):236-239.

Identification of Oracle-bone Script Fonts Based on Topological Registration

GU Shaotong

(School of Linguistic Science and Art,Jiangsu Normal University, Xuzhou221009)

Oracle-bone script,as the character system with stable topological structure,although has many variant forms,same characters share the semblable topological structure for different forms. This characteristic makes it possible to identify different fonts based on the forms. By analyzing the topological characteristic,topological vertexes,and the topological relation among topological vertexes,the research describes the topological relation among topological vertexes and converts oracle-bone script fonts to topological graphs. Meanwhile,by coding the topological graphs,the authors realize the formal description of topological frame.

topological registration, topological frame, topological vertex, topological relation, topological coding, oracle-bone script, font identification

2016年4月10日,

2016年5月16日

國家社會科學(xué)基金(編號：13CYY039);教育部社會科學(xué)基金(編號：10YJC740032);江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項(xiàng)目(編號：PAPD);江蘇省高校哲學(xué)社會科學(xué)重點(diǎn)研究基地基金資助。

顧紹通，男，碩士，講師，研究方向：中文信息處理。

TP391

10.3969/j.issn.1672-9722.2016.10.029