基于書(shū)寫(xiě)規(guī)則的書(shū)法字筆畫(huà)及筆順提取*

劉佳巖，章夏芬（上海海事大學(xué) 信息工程學(xué)院，上海 201306）

基于書(shū)寫(xiě)規(guī)則的書(shū)法字筆畫(huà)及筆順提取*

劉佳巖，章夏芬
（上海海事大學(xué) 信息工程學(xué)院，上海 201306）

提出了一種針對(duì)篆書(shū)和隸書(shū)等多類別書(shū)法字圖像筆畫(huà)及筆順信息的提取算法。算法通過(guò)使用書(shū)法字骨架圖與輪廓圖相結(jié)合的方式，使用針對(duì)交叉處輪廓點(diǎn)角度聚類及該點(diǎn)與交叉中心歐氏距離相結(jié)合的聚類準(zhǔn)則，完成交叉處筆畫(huà)的信息補(bǔ)全、處理，并根據(jù)書(shū)寫(xiě)規(guī)則提取書(shū)法字的筆順信息。最后，針對(duì)楷體、隸書(shū)、篆書(shū)三類書(shū)法字圖像做筆畫(huà)以及筆順信息的提取，實(shí)驗(yàn)結(jié)果表明本文所提出的方法對(duì)多類別書(shū)法字圖像筆畫(huà)提取取得了較好的效果。

書(shū)法字；筆畫(huà)提取；書(shū)寫(xiě)規(guī)則；書(shū)法筆順

0　引言

中華民族五千年文化中有大量書(shū)法作品，這些書(shū)法作品被掃描成頁(yè)面圖像，能夠有利于書(shū)法作品的保護(hù)以及便于書(shū)法作品的流傳、鑒賞，但是書(shū)法頁(yè)面圖像卻無(wú)法表現(xiàn)漢字書(shū)寫(xiě)的過(guò)程，丟失了筆順信息。

書(shū)法字筆畫(huà)、筆順信息除了有益于書(shū)法教學(xué)之外，在書(shū)法書(shū)寫(xiě)過(guò)程重現(xiàn)、書(shū)法風(fēng)格自動(dòng)識(shí)別等領(lǐng)域中也是最為重要的信息。

本文提出的方法利用書(shū)法單字骨架，結(jié)合輪廓圖提取完整筆畫(huà)，并依據(jù)書(shū)寫(xiě)規(guī)則，確定筆畫(huà)書(shū)寫(xiě)順序。

1　相關(guān)工作

1.1筆畫(huà)提取

目前，有很多的方法來(lái)完成筆畫(huà)提取的工作。在筆畫(huà)提取過(guò)程中主要需要解決兩個(gè)關(guān)鍵問(wèn)題：（1）獨(dú)立筆畫(huà)的提?。唬?）交叉筆畫(huà)在交叉段的處理。

目前大多數(shù)的筆畫(huà)提取方法是細(xì)化處理：將輸入的漢字圖片處理為骨架圖。對(duì)整個(gè)漢字骨架進(jìn)行跟蹤，初步提取筆畫(huà)。此時(shí)，無(wú)交叉筆畫(huà)已完成提取，但分叉點(diǎn)連接著多個(gè)不完整的筆畫(huà)段。此后通過(guò)一定的合并、拆分規(guī)則，最終獲得準(zhǔn)確筆畫(huà)。這種處理方式能夠?qū)h字的筆畫(huà)方向信息完整地保留下來(lái)，同時(shí)因?yàn)檎麄€(gè)骨架圖為單像素寬度，降低了后續(xù)筆畫(huà)提取的計(jì)算復(fù)雜度。這種方式也存在著較為明顯的缺點(diǎn)：（1）失去了筆畫(huà)的寬度信息；（2）在細(xì)化過(guò)程中，會(huì)引入一定的形變，為后續(xù)筆畫(huà)的正確提取造成了一定的難度［1-3］。

另一部分筆畫(huà)提取方法使用的是輪廓圖或線鄰接圖（LAG）。提取輪廓特征點(diǎn)，計(jì)算各特征點(diǎn)的曲率，尋找出曲率最大的點(diǎn)，確定為筆畫(huà)拐點(diǎn)。由于在筆畫(huà)交叉處，必然存在拐點(diǎn)或角點(diǎn)，因此確定拐點(diǎn)或角點(diǎn)的位置能夠進(jìn)一步確定筆畫(huà)的走向，完成交叉段不同筆畫(huà)的分割、提?。?-3］。

［4］提出了基于Delaunay三角剖分的三角網(wǎng)格表征與點(diǎn)到邊界方向距離PBOD曲線相結(jié)合的筆畫(huà)提取方法。相較于傳統(tǒng)的基于漢字細(xì)化和LGA等方法，該方法從漢字的基礎(chǔ)特征著手，提取效果較好。

上述方法只是針對(duì)于某一單一風(fēng)格的書(shū)法字筆畫(huà)提取，或者印刷體漢字提取，沒(méi)有針對(duì)多類別的書(shū)法字的筆畫(huà)提取進(jìn)行驗(yàn)證。

1.2筆順信息提取

漢字是一種象形文字，其典型的書(shū)寫(xiě)規(guī)則：先左后右，先上后下。本文利用該規(guī)則，結(jié)合已有的筆畫(huà)信息，對(duì)筆畫(huà)進(jìn)行排序，獲得筆順信息。

2　系統(tǒng)框架

算法的流程圖如圖1所示。

3　骨架筆畫(huà)提取

3.1漢字骨架

漢字的骨架由細(xì)化算法獲取，它必須滿足［5］：

（1）只有一個(gè)像素寬；

（2）必須穿越物體的中間；

（3）必須保持物體的拓?fù)浣Y(jié)構(gòu)。

將漢字骨架中的點(diǎn)分為三類［5］：

（1）Nc（P）=1，則 P為端點(diǎn)；

（2）Nc（P）=2，則 P為普通點(diǎn)；

（3）Nc（P）≥3，則 P為交叉點(diǎn)。

其中Nc（P）為骨架點(diǎn)P八鄰域內(nèi)鄰居點(diǎn)數(shù)量。圖2為書(shū)法字骨架及端點(diǎn)、交叉點(diǎn)提取結(jié)果示例。

圖2　骨架及端點(diǎn)、交叉點(diǎn)提取結(jié)果示例

3.2筆畫(huà)段提取

本文中所使用的骨架筆畫(huà)段提取方法是根據(jù)文獻(xiàn)［5］、［6］、［7］中所提出的筆畫(huà)提取方法，并對(duì)其進(jìn)一步改進(jìn)而來(lái)。

獨(dú)立筆畫(huà)：某一筆畫(huà)與該漢字的其他筆畫(huà)無(wú)相交、無(wú)粘連，則該筆畫(huà)稱之為獨(dú)立筆畫(huà)，其特征是筆畫(huà)的起點(diǎn)與終點(diǎn)必為端點(diǎn)，除端點(diǎn)之外的其他骨架點(diǎn)均為普通點(diǎn)。

非獨(dú)立筆畫(huà)：某一筆畫(huà)與該漢字其他筆畫(huà)中的一筆或者多筆相交或粘連，則該筆畫(huà)稱之為非獨(dú)立筆畫(huà)，它是由端點(diǎn)、普通點(diǎn)以及交叉點(diǎn)構(gòu)成，或者由交叉點(diǎn)、普通點(diǎn)所構(gòu)成。

骨架筆畫(huà)段提取步驟如下：

以任意端點(diǎn)為起點(diǎn)，沿其鄰接的普通點(diǎn)方向做坐標(biāo)更新，并記錄每次更新的坐標(biāo)與上一次坐標(biāo)的方向編碼，直至遇到交叉點(diǎn)或端點(diǎn)。具體的方向編碼方式如圖3所示。

圖3　鏈碼方向及編碼方式

骨架筆畫(huà)段的記錄方式為：

式中i表示筆畫(huà)段的標(biāo)號(hào)，Bi、Ei為筆畫(huà)段的起點(diǎn)與終點(diǎn)，Sni為筆畫(huà)段的鏈碼表示，如圖 2所示的左上角的筆畫(huà)“撇”的筆畫(huà)表示為：

｛（19，17），（11，33），（666566645644646654）｝

筆畫(huà)段提取完成之后，可能存在錯(cuò)誤的筆畫(huà)段，因此需要依據(jù)下述規(guī)則對(duì)筆畫(huà)段進(jìn)行修正，以獲得準(zhǔn)確的骨架筆畫(huà)。

規(guī)則 1.如果 li＜L×η（i=1，2，3，…，Ns），則該筆畫(huà)為一個(gè)錯(cuò)誤筆畫(huà)。其中，η為閾值，本文設(shè)為1/3，Ns為已提取到的筆畫(huà)數(shù)，li為第i筆筆畫(huà)長(zhǎng)度：li=lenght（Sni）+1。

規(guī)則 2.如果筆畫(huà) Si，Sj（i≠j）滿足如下條件：（1）Dis （Si，Sj）＜λ×μw；（2）筆畫(huà)走向一致或相近，則 Si，Sj可以合并為同一筆畫(huà)。其中 Dis（Si，Sj）為筆畫(huà)起止點(diǎn)之間的歐式距離。μw為近似的書(shū)法字平均筆畫(huà)寬度，λ為閾值，本文λ=0.5。

經(jīng)過(guò)二值化處理之后的圖像可以認(rèn)為是一個(gè)多邊形，黑色像素點(diǎn)數(shù)目可以近似為該多邊形的面積S，骨架的總長(zhǎng)度可以看作經(jīng)過(guò)多邊形中軸的多邊形的底b，漢字筆畫(huà)的平均寬度可以近似看作這個(gè)多邊形的高h(yuǎn)，由多邊形面積公式S=b×h推導(dǎo)出近似的平均筆畫(huà)寬度μw的計(jì)算公式：

NPB為經(jīng)過(guò)二值化處理之后的書(shū)法字黑色像素點(diǎn)數(shù)，NSP為骨架點(diǎn)的數(shù)目。

規(guī)則 3.如果筆畫(huà) Si，Sj（i≠j）滿足如下條件：（1）Si，Sj與同一交叉點(diǎn)簇相交；（2）Si，Sj筆畫(huà)走向一致或相近，則 Si，Sj可以合并為同一筆畫(huà)。

4　筆順信息獲取

漢字的書(shū)寫(xiě)順序大致滿足如下規(guī)則：從左到右，從上到下。本文依據(jù)該規(guī)則提取書(shū)法的筆順信息。

4.1筆畫(huà)起止點(diǎn)的確定

本文規(guī)定書(shū)法圖像左上起點(diǎn)為坐標(biāo)原點(diǎn)，x軸正向?yàn)樵c(diǎn)指向其右側(cè)，y軸正向?yàn)樵c(diǎn)指向其下側(cè)。

對(duì)于骨架筆畫(huà) Si的端點(diǎn) Bi，Ei，當(dāng)其滿足如下條件之一：

則將端點(diǎn)Bi，Ei進(jìn)行交換。

4.2標(biāo)定筆畫(huà)順序

對(duì)已正確獲得起止點(diǎn)的筆畫(huà)，按照如下確定筆畫(huà)提取的優(yōu)先順序：

（1）如果Bi.x＜Bj.x，則筆畫(huà) Si先于 Sj書(shū)寫(xiě)；

（2）如果Bi.x=Bj.x且Bi.y＜Bj.y，則筆畫(huà)Si先于Sj書(shū)寫(xiě)；

（3）如果Si滿足式（6）：

則該筆畫(huà)為末筆。

5　筆畫(huà)復(fù)原

前文中所提取的骨架筆畫(huà)丟失了書(shū)法字的寬度信息，將筆畫(huà)寬度信息恢復(fù)。

獨(dú)立筆畫(huà)的完整筆畫(huà)輪廓是一條封閉的曲線；非獨(dú)立筆畫(huà)在剔除交叉區(qū)后，其輪廓線是斷開(kāi)的，需要補(bǔ)全成為封閉曲線。因此，對(duì)于獨(dú)立筆畫(huà)而言其所對(duì)應(yīng)的輪廓只需通過(guò)連通性檢測(cè)即可實(shí)現(xiàn)寬度信息恢復(fù)。本文重點(diǎn)解決對(duì)于存在交叉區(qū)域的筆畫(huà)寬度信息恢復(fù)。

5.1交叉點(diǎn)簇與交叉區(qū)域

由于骨架圖在提取過(guò)程中會(huì)產(chǎn)生一定的形變，因此交叉區(qū)域在骨架中會(huì)產(chǎn)生兩種情況：

（1）在交叉區(qū)域，由交叉點(diǎn)與普通點(diǎn)組成，如圖4左圖：由兩個(gè)交叉點(diǎn)包圍著多個(gè)普通點(diǎn)在小的鄰域內(nèi)連續(xù)出現(xiàn)。

（2）在交叉區(qū)域，骨架圖完全由交叉點(diǎn)組成，如圖 4右部，在一個(gè)小的鄰域內(nèi)連續(xù)出現(xiàn)交叉點(diǎn)。

圖4　交叉點(diǎn)簇示例

第二種情況是由骨架圖的形變所引起。為了修正形變，根據(jù)最大圓準(zhǔn)則［5-8］進(jìn)行簡(jiǎn)化處理：對(duì)于骨架圖中的兩個(gè)特征點(diǎn)（交叉點(diǎn)），分別計(jì)算出它們?cè)谠瓐D（未骨架化的圖像）中到筆畫(huà)輪廓的最大內(nèi)切圓的半徑。如果兩個(gè)特征點(diǎn)之間的距離小于或等于各自內(nèi)切圓半徑之和，那么這兩個(gè)特征點(diǎn)對(duì)應(yīng)一個(gè)筆畫(huà)的相交區(qū)域。將第二種情況中的由交叉點(diǎn)所包圍的普通點(diǎn)標(biāo)定為交叉點(diǎn)。進(jìn)一步將上文中所述的兩種情況歸并為對(duì)交叉點(diǎn)簇的處理。

本文使用點(diǎn)簇的虛擬質(zhì)心Pc來(lái)標(biāo)定筆畫(huà)交叉區(qū)域，Pc的計(jì)算如式（7）所示：

其中，N為交叉點(diǎn)簇中交叉點(diǎn)的數(shù)量，pif為該點(diǎn)簇中的第i個(gè)交叉點(diǎn)。

5.2交叉區(qū)處理

前文中通過(guò)交叉點(diǎn)簇的中心完成了交叉區(qū)域的定位，為了進(jìn)一步減少待處理的像素點(diǎn)的數(shù)目，使用輪廓圖來(lái)進(jìn)行交叉區(qū)域的處理。

骨架是圖像的中軸［9-11］，因此，對(duì)書(shū)法字輪廓圖做筆畫(huà)提取，交叉區(qū)域的輪廓圖有如下的特點(diǎn)：

（1）位于交叉區(qū)域的輪廓線，相對(duì)于交叉區(qū)域質(zhì)心位置相對(duì)固定，且局部不相交。

（2）筆畫(huà)在交叉區(qū)域的輪廓缺失。

因此，要提取到完整的筆畫(huà)信息需要補(bǔ)全筆畫(huà)缺失的輪廓點(diǎn)。

5.2.1聚類坐標(biāo)系建立

為了更好地提取四條輪廓線，應(yīng)按照如圖5所示的方式建立聚類坐標(biāo)系：

（1）坐標(biāo)系原點(diǎn)為交叉區(qū)域質(zhì)心，x軸正方向?yàn)橛稍c(diǎn)指向右側(cè)，y軸正方向?yàn)橛稍c(diǎn)指向上側(cè)。

圖5　坐標(biāo)系建立示意圖

（2）若交叉筆畫(huà)在交叉處的行筆方向LDir（i）、LDir（j）與（1）中所建立的坐標(biāo)系中坐標(biāo)軸不平行，則坐標(biāo)系逆時(shí)針旋轉(zhuǎn)θ=45°。

5.2.2輪廓點(diǎn)聚類

坐標(biāo)系的建立，為輪廓點(diǎn)的分類奠定了基礎(chǔ)。按照輪廓點(diǎn)所屬象限將輪廓點(diǎn)分為四個(gè)類別，具體步驟如下：

（1）以原點(diǎn)為圓心，以間隔角度ω=1°，最大半徑R= 3μw，做掃描，記錄落入圓內(nèi)的所有輪廓點(diǎn)。

（3）計(jì)算每一個(gè)點(diǎn)的類別C（θ），并將其記錄。其中：

5.2.3輪廓連接點(diǎn)確定

使用輪廓圖提取筆畫(huà)的關(guān)鍵點(diǎn)是找到輪廓點(diǎn)中拐點(diǎn)或角點(diǎn)，來(lái)確定筆畫(huà)的走向，完成筆畫(huà)的提取。為了補(bǔ)全筆畫(huà)所缺失的輪廓點(diǎn)，需要確定輪廓線在交叉區(qū)域的拐點(diǎn)，找到各個(gè)象限中距離原點(diǎn)最近的點(diǎn)，從而確定輪廓圖在交叉區(qū)域的拐點(diǎn)即筆畫(huà)在此處的鏈接點(diǎn) Plinkc。

其中，P_set（c）為第 c類輪廓點(diǎn)集合，Plinkc為第 c類連接點(diǎn)。

交叉筆畫(huà)可以分為“十”型交叉及“T”型交叉，針對(duì)不同的交叉類型，選擇不同連接點(diǎn)。

（1）“十”型交叉如圖 6，交叉各筆畫(huà)缺失兩條輪廓線，因此需要選擇四個(gè)連接點(diǎn)，依據(jù)筆畫(huà)在交叉處的行筆方向，組合為兩條平行于筆畫(huà)交叉處行筆方向的輪廓線的起止點(diǎn)，完成輪廓線的補(bǔ)全。

（2）“T”型交叉如圖 7，交叉各筆畫(huà)，均缺失同一條輪廓線，因此需要選取兩個(gè)連接點(diǎn)，依據(jù)某一筆畫(huà)在交叉處的行筆方向，選取相同的兩類連接點(diǎn)作為一條輪廓線的起始點(diǎn)（該輪廓線平行于一條筆畫(huà)的行筆方向，垂直于與該筆畫(huà)相交的筆畫(huà)的行筆方向），完成輪廓線的補(bǔ)全。

6　實(shí)驗(yàn)分析

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

圖8為楷體字“生”的筆畫(huà)及筆順提取示意。為了驗(yàn)證本文所提出算法的有效性，本文使用三類不同書(shū)法風(fēng)格的單字圖像完成筆畫(huà)提取實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1、表2所示。

圖7　“T”型交叉的示意圖，相交筆畫(huà)缺失同一條輪廓線

表1　筆畫(huà)提取結(jié)果（骨架圖）

表2　筆畫(huà)提取結(jié)果（二值化圖）

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

整個(gè)實(shí)驗(yàn)共有110幅單字圖片，不同類別的圖片數(shù)分別為40、40、30。由表1可以看出，針對(duì)不同類別的書(shū)法單字圖像的筆畫(huà)提取的準(zhǔn)確率不同，對(duì)篆書(shū)書(shū)法字的提取效果最好，行楷提取效果最差。在表2中針對(duì)提取正確的書(shū)法單字圖像做完整筆畫(huà)提取，可以看到準(zhǔn)確率均在90％以上?？偟墓P畫(huà)提取（骨架）正確率為83.9％，針對(duì)筆畫(huà)提?。ü羌埽┱_的圖像做完整的筆畫(huà)提取總的準(zhǔn)確率為93.2％。

可以看到，本文提出的基于骨架與輪廓圖相結(jié)合的筆畫(huà)提取算法能夠較好地完成不同類別的書(shū)法單字的筆畫(huà)提取，受書(shū)法字骨架引入的形變的影響較小。同時(shí)可以看出，筆畫(huà)提?。ü羌埽┑恼_率對(duì)整體的筆畫(huà)提取工作有著較大的影響。如何進(jìn)一步完成筆畫(huà)（骨架）的修正是提高整體筆畫(huà)提取正確率的關(guān)鍵。

7　總結(jié)

本文提出將書(shū)法漢字圖像骨架圖與輪廓圖相結(jié)合的方法，能夠完成適應(yīng)多類書(shū)法風(fēng)格的書(shū)法漢字筆畫(huà)提取以及基于書(shū)寫(xiě)規(guī)則的筆順信息提取。相較于傳統(tǒng)方法，本文所提出的算法能夠有效地降低筆畫(huà)提取操作所需要的時(shí)間，簡(jiǎn)化了計(jì)算復(fù)雜度，并且對(duì)多類書(shū)法字的筆畫(huà)、筆順提取都取得了較好的效果。

下一步的工作將是繼續(xù)對(duì)算法進(jìn)行修正，以獲得針對(duì)更多類別書(shū)法字的筆畫(huà)提取的結(jié)果，提高筆畫(huà)提取的準(zhǔn)確率。

參考文獻(xiàn)

［1］張世輝，孔令富.漢字識(shí)別及現(xiàn)狀分析［J］.燕山大學(xué)學(xué)報(bào)，2003，27（4）：367-369.

［2］李正華，胡奇光.漢字筆畫(huà)提取的算法與實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用與軟件，2004，21（7）：96-97.

［3］王建平，藺菲，陳軍.基于手寫(xiě)體漢字筆畫(huà)提取重構(gòu)的識(shí)別方法［J］.人工智能及識(shí)別技術(shù)，2007，33（10）：230-232.

［4］Wang Xiaoqing，Liang Xiaohui，Sun Linjia，et al.Triangular mesh based stroke segmentation for Chinese calligraphy［C］.International Conference on Document Analysis and Recognition，2013：1155-1159.

［5］陳睿.漢字離線識(shí)別技術(shù)中筆畫(huà)提取模型研究 ［D］.重慶：西南師范大學(xué)，2004.

［6］陳睿，唐雁，邱玉輝.基于筆畫(huà)段分割和組合的漢字筆畫(huà)提取模型［J］.計(jì)算機(jī)科學(xué)，2003，30（10）：74-77.

［7］章夏芬.中國(guó)數(shù)字書(shū)法檢索與作品真?zhèn)舞b別的研究［D］.杭州：浙江大學(xué)，2006.

［8］章夏芬，莊越挺，魯偉明，等.根據(jù)形狀相似性的書(shū)法內(nèi)容檢索［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2005，17（11）：2565-2569.

［9］郭晨.基于圖像處理技術(shù)的手寫(xiě)體漢字特征分析的研究［D］.天津：天津科技大學(xué)，2010.

［10］孫華，李愛(ài)平.支持向量機(jī)的古漢字識(shí)別研究［J］.電腦知識(shí)與技術(shù)，2013，9（18）：4296-4298.

［11］苗晉誠(chéng).基于骨架化、骨架劃分獲取書(shū)法漢字結(jié)構(gòu)特征的方法［J］.昆明理工大學(xué)學(xué)報(bào)（理工版），2008，33（3）：53-61.

Calligraphy′s strokes and orders extraction based on the rules of writing

Liu Jiayan，Zhang Xiafen
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China）

This paper proposes a novel stroke and the orders extraction algorithm adopted to multiple classes of the Chinese calligraphy.In order to process the region of fork strokes，the paper proposes a new cluster method which combine the skeleton image and the contour image.The rules of clustering is based on the angle of the contour points and the Euclid distance of the point to the fork region′s center point.And then completing the stroke′s missing information in the fork region，extracting the orders of the stroke based on the rules of writing.Finally，the strokes of three types Chinese calligraphy are extracted with this algorithm.Experimental results show that the proposed algorithm achieves a better effect.

Chinese calligraphy；stroke extraction；rules of writing；orders of calligraphy′s stroke

TP391.1

A

1674-7720（2015）15-0051-04

劉佳巖，章夏芬.基于書(shū)寫(xiě)規(guī)則的書(shū)法字筆畫(huà)及筆順提?。跩］.微型機(jī)與應(yīng)用，2015，34（15）：51-54，58.

2015-03-13）

劉佳巖（1990-），男，碩士研究生，主要研究方向：數(shù)字圖像處理與模式識(shí)別。

國(guó)家自然科學(xué)基金（61303100）；上海海事大學(xué)?；穑?0130467）

章夏芬（1977-），女，博士，講師，主要研究方向：圖像處理、模式識(shí)別、數(shù)字圖書(shū)館。