基于CDPM的東巴象形文字預(yù)處理算法?

楊玉婷 康厚良

（1.昆明理工大學(xué)津橋?qū)W院電氣與信息工程學(xué)院 昆明 650000）（2.云南經(jīng)濟管理學(xué)院人文藝術(shù)學(xué)院 昆明 650000）

1 引言

東巴文是一種十分原始的圖畫象形文字，納西語稱“森究魯究”，直譯為“留在木石上的印跡”［1］，由于這種文字主要是由納西族祭祀——東巴用來書寫傳遞民族文化典籍的東巴經(jīng)，所以也稱為東巴文［2］。納西東巴象形文字作為人類早期的一種圖畫文字向象形文字、標(biāo)音文字過度的文字形式，具有字符類型多，字體結(jié)構(gòu)復(fù)雜和字形變化多等特點［3～5］。特別是其中所包含的變形字和綴加字［6］，雖然與基本構(gòu)字元素同屬一類文字，具有相同或相似的文字形態(tài)，但是卻有著各不相同的含義，這給東巴字的特征提取、檢索和識別帶來巨大干擾，如表1所示。

表1 基本字素及其同形字素、變形字素和加綴字素舉例

對東巴文字的檢索和識別的研究較多［7～11］，并且從不同角度應(yīng)用各類不同的算法來實現(xiàn)，但是在預(yù)處理階段大多都一筆帶過，或者是使用常見的灰度化、二值化、直方圖等方法來完成［12～15］。顯然，不充分的預(yù)處理不但會增加文字特征提取的復(fù)雜度，也會影響文字檢索和識別的準(zhǔn)確度。因此，通過分析東巴象形文字的造字方法，給出了基于CDPM的東巴字預(yù)處理算法，該算法不但能快速去除東巴字中的部分形變和離散的綴加元素，同時也能去除字符輪廓中具有粘連性的綴加元素，使得到的輪廓曲線能準(zhǔn)確反映東巴字的本質(zhì)特征。

2 基于鏈碼的連通域優(yōu)先級標(biāo)記算法（CDPM）

基于鏈碼的連通域優(yōu)先級標(biāo)記算法（ConnectedDomainPriorityMarkingAlgorithm，CDPM）［16］可準(zhǔn)確提取東巴字符的特征輪廓，其核心思想是：設(shè)給定的字符為G，Pi(i∈{1,2,…,n})為G中所包含的特征點，即Pi∈G。從G上的第一個特征點P1出發(fā)，按逆時針方向遍歷。若已知特征點Pi(i≥2)的前一個已知點為Pi-1，后一個待測點為Pi+1，且由Pi-1和Pi組成的方向向量為那么，當(dāng)向量滿足v.x≠0且v.y≠0時，以點Pi為核心的8鄰域點優(yōu)先級權(quán)值在局部滿足順時針排列的方式，且優(yōu)先級最低的鄰接點是向量反方向所指向的點，而優(yōu)先級值最大的點即為待測點Pi+1。然后，將Pi+1作為已知特征點，重復(fù)執(zhí)行上述過程，直到得到完整的字符特征輪廓曲線為止。

需要說明的是，為了保證字符輪廓的連續(xù)性和閉合性，當(dāng)字符中包含由單個像素點組成的線條時，CDPM會重復(fù)存儲組成單像素線條的特征點，以保證字符輪廓的連續(xù)性和完整性。

3 基于CDPM的預(yù)處理算法

東巴象形文字預(yù)處理算法的目的是去除文字中的干擾成分，包括文字中的噪音、綴加的文字成份及文字的形變成份，降低字符特征提取階段的復(fù)雜度，使相同類型的東巴字能夠得到相同或相似的特征曲線，而不同類型文字的特征曲線又具有較大的差異性，具體包括三個階段的內(nèi)容。首先，去除文字中具有非粘連性的加綴點、線和字塊；其次，確定字符輪廓提取的起點，確保不同字符所提取的特征曲線的一致性；最后，使用CDPM算法提取文字的特征輪廓，并結(jié)合CDPM算法重復(fù)存儲單像素線條的特性去除輪廓中具有粘連性的加綴點和線，使得到的特征曲線能夠反映文字的本質(zhì)。

3.1 去除離散綴加元素

3.1.1 東巴文字的細(xì)化

由于東巴文字一般使用竹筆（屬于硬筆）書寫，文字的線條寬度基本一致［3］。細(xì)化文字線條有利于降低復(fù)雜度。但是，在東巴字中，有的文字通過填充或局部填充的方法表示貶義或反義詞，例如：（花）、（劇毒）和（毒草），若直接細(xì)化可能得到的是字符的骨架，而非筆劃。因此，在細(xì)化前應(yīng)判斷字符是否被填充過，判斷條件如下：

其 中 ，GlyphPixeloriginal為 原 始 字 符 ，而GlyphPixelFilled表示填充后的字符。那么，當(dāng)字符填充前后的像素點數(shù)比例小于80%，說明原字符未被填充過，可以細(xì)化；否則，不能細(xì)化。

3.1.2 離散元素的判斷與去除

另外，結(jié)合東巴文字的造字特點可知，東巴文字中的綴加成份一般只起到豐富文字含義的作用，作為文字的輔助元素，它的大小一定小于該文字的基本構(gòu)字元素。因此，對于由n個離散子字塊組成的任意東巴字G，各子字塊用GPi(i∈{1,2,…,n})表示，子字塊對應(yīng)的外接矩形面積用RectAreai表示，則面積最大的子字塊即為G的基本構(gòu)字元素，即

3.2 東巴文字結(jié)構(gòu)分析及輪廓起點確定

東巴文字的結(jié)構(gòu)一般可分為三種，即完全閉合 全、閉半合閉的合輪及廓非線閉，例合 如。：完全閉（合房指屋）的 、是文字（具手）有等完；半字樓）閉局等合部；指是也的閉有是合的文的是字，半沒例包有如圍完的全，閉（例廚合如房的）輪 、廓（線貧，困有（戶竹的）文墻、（輪人廓）（、特壓 征） ，等（特 蹲； 別非）、是閉以合人（指形拔的）為是和基文礎(chǔ)字的（本文吹身字笛沒子，有例）明等如顯。的與前兩種類型相比，非閉合型文字是以文字線條來表示含義，處理相對簡單，因此，僅著重討論前兩種文字的處理方法。

對于完全閉合及半閉合型文字，在使用CDPM提取輪廓時，一般選取字符x/y軸最小值點或字符的終端點作為起點。但是，由于文字結(jié)構(gòu)的多樣性，有的終端點未在輪廓上，若采用終端點作為起點，則無法得到正確的輪廓，如圖1（上）所示；而有的文字是半閉合的，若采用x/y軸最小值作為起點，則無法獲得完整的輪廓，如圖1（下）所示。由于無法判斷終端點或x/y軸最小值點是否是潛在的有效起點，而選擇不當(dāng)將會導(dǎo)致文字輪廓提取不全或提取錯誤。

圖1 選取不同的起點可能得到不同的文字輪廓

為了獲得正確的字符輪廓，選擇兩種不同的起點分別計算字符的輪廓，并將其中較大的輪廓作為文字的最終輪廓，即

以終端點和y軸的最小值點作為起點，使用CDPM算法提取字符的輪廓，分別使用Contourendpoint和Contourmin(y)表示字符輪廓，BoundRectendpoint和BoundRectmin()y表示輪廓的綁定矩形。基于字符輪廓最大原則，如果Contourendpoint的外接矩陣面積較大，則將Contourendpoint作為最終的字符輪廓，否則，將Contourmin(y)作為最終的字符輪廓，從而保證使用CDPM算法字符輪廓提取的正確性，判斷條件如下：

3.3 去除粘連的綴加元素

在CDPM算法中，為了保證字符輪廓的連續(xù)性和完整性，當(dāng)字符中包含單像素組成的線條時，會重復(fù)存儲組成輪廓的特征點。雖然會產(chǎn)生一些干擾，但是，卻為判斷字符中是否存在粘連綴加元素提供了幫助。例如，圖2所示字符中包含了一條單像素粘連的綴加線條，為了保證字符輪廓的連續(xù)性，CDPM算法重復(fù)存儲了P5→P8的多個連續(xù)特征點。值得注意的是，這些被重復(fù)存儲的點是具有規(guī)律性的。

因此，對于任意具有連續(xù)性且由n個點組成的字符輪廓C，若最初發(fā)生重復(fù)的點為Pi(i∈{1,2,…,n})且 重 復(fù) 的 位 置 為i和j，即Pi→Contour(i) Pi→Contour(j)，其中i,j∈{1,2,…,n}，使得輪廓C被分為兩個連續(xù)的曲線段Ci→(j-1)和 C(j→end)∪(1→(i-1))，若 下 一 個 重 復(fù) 點Pk(k∈{i+1,i+2,…,n})的重復(fù)位置為i+1和j-1，即Pk→Contour(i +1) Pk→Contour( j-1)，則曲線段Ci→(j-1)是輪廓中重復(fù)存儲的綴加線條；否則，C(j→end)∪(1→(i-1))是輪廓中重復(fù)存儲的綴加線條。

圖2 字符中粘連的綴加線條的去除

因此，在輪廓中循環(huán)查找重復(fù)存儲的特征點時，對于Pi→Contour(i) Pi→Contour(j)可能存在i＞j的情況，為了保證所有重復(fù)存儲的特征點能被全部找出，使用count統(tǒng)計重復(fù)點的數(shù)量，在完成一遍所有輪廓點的遍歷后，還需再次遍歷，直到輪廓中的所有重復(fù)點都被去除（count=0）為止。

4 實驗

東巴文字預(yù)處理算法的目的包括三個方面：1）去除字符中離散的綴加點、線或字塊；2）確定CDPM算法的有效起點，保證提取的特征輪廓的完整性和正確性；3）去除字符輪廓中粘連的綴加點或綴加線條，最終得到字符的特征曲線。因此，著重從差異性、通用性性、準(zhǔn)確性及一致性等幾個方面對預(yù)處理算法進(jìn)行評估。

4.1 差異性評估

差異性評估的目的是對于不同類型的東巴文字，預(yù)處理算法是否都能得到預(yù)期的效果。因此，分別選取半閉合字符、半包圍字符及包含離散和粘連綴加元素的作為測試樣例，測試結(jié)果如圖3所示。其中，圖3（a）為不同東巴字的二值圖；圖3（b）為字符線條細(xì)化及去除了離散的綴加點、線和字塊后的效果；圖3（c）為使用CDPM提取的字符輪廓；圖3（d）為字符輪廓去除粘連綴加元素后得到的最終字符特征曲線。

圖3 待測字符的二值圖及三個處理階段的效果圖

4.2 通用性和一致性評估

為了進(jìn)一步驗證算法的通用性，從東巴象形文字中選取包括魚蟲、鳥、花、手、山、（閉合的）房屋、水、東巴祭祀、牲畜和（半閉合的房屋）等10類具有相似特征的字符，并且每種類別中都包括數(shù)目不等的東巴字。這10類東巴字在文字結(jié)構(gòu)上包括完全閉合型、半閉合型兩種。而在綴加元素方面，包括綴加點、綴加線、綴加字塊、綴加點和線、綴加點和字塊、綴加線和字塊、綴加點和線及字塊等7種，具體如表2所示。

表2 具有相似特征的10組東巴字符

在10類東巴字中任意提取其中的5個字符進(jìn)行預(yù)處理操作，如圖4所示。圖4中每幅圖片的奇數(shù)行為原字符，而偶數(shù)行為該字符對應(yīng)的特征曲線。分析圖4可知，所有文字中所包含的綴加成份（離散的和粘連的）和形變都得到了較好的去除。另外，圖4中，相同類型的東巴字符得到的字符輪廓基本相同，而不同類型的東巴字的字符輪廓具有明顯的差異性。說明，對于同類型的東巴文字及不同類型的東巴文字，預(yù)處理算法都能提取體現(xiàn)它們本質(zhì)的特征曲線，具有較好的通用性。

圖4 各類東巴字符及對應(yīng)的特征輪廓曲線

4.3 準(zhǔn)確性

為了進(jìn)一步驗證預(yù)處理算法的準(zhǔn)確性，對表2中的所有字符以類別為單位分別比較CDPM算法和預(yù)處理算法兩種不同方法獲得的字符特征曲線，并對同類型字符中具有相似特征曲線的個數(shù)進(jìn)行統(tǒng)計，統(tǒng)計結(jié)果如圖5所示。顯然，由于預(yù)處理算法去除了字符本身包含的形變和綴加元素，因此，同類型東巴字的特征曲線相似度較高，并且10種類型的東巴字特征曲線的相似個數(shù)均高于直接使用CDPM算法得到的結(jié)果。說明，預(yù)處理算法能夠提取顯著反映東巴文字本質(zhì)的特征曲線。

圖5 同類型東巴字中具有相似的輪廓曲線和特征曲線的個數(shù)比較

5 結(jié)語

基于CDPM的東巴文字預(yù)處理算法能夠快速去除東巴字中的部分形變、離散的綴加元素及粘連的綴加元素，使最終得到的特征曲線能夠更好地反映文字的本質(zhì)，一方面加大了不同類型文字之間的差異性，另一方面也提高了同類型文字間查找的準(zhǔn)確性，降低文字檢索和識別的復(fù)雜度，為實現(xiàn)東巴文字的快速檢索和識別奠定堅實的基礎(chǔ)，也為其他象形文字的預(yù)處理研究提供有益參考。