摘 要： 提出了一種針對篆書和隸書等多類別書法字圖像筆畫及筆順信息的提取算法。算法通過使用書法字骨架圖與輪廓圖相結合的方式，使用針對交叉處輪廓點角度聚類及該點與交叉中心歐氏距離相結合的聚類準則，完成交叉處筆畫的信息補全、處理，并根據書寫規則提取書法字的筆順信息。最后，針對楷體、隸書、篆書三類書法字圖像做筆畫以及筆順信息的提取，實驗結果表明本文所提出的方法對多類別書法字圖像筆畫提取取得了較好的效果。

0 引言

中華民族五千年文化中有大量書法作品，這些書法作品被掃描成頁面圖像，能夠有利于書法作品的保護以及便于書法作品的流傳、鑒賞，但是書法頁面圖像卻無法表現漢字書寫的過程，丟失了筆順信息。

書法字筆畫、筆順信息除了有益于書法教學之外，在書法書寫過程重現、書法風格自動識別等領域中也是最為重要的信息。

本文提出的方法利用書法單字骨架，結合輪廓圖提取完整筆畫，并依據書寫規則，確定筆畫書寫順序。

1 相關工作

1.1 筆畫提取

目前，有很多的方法來完成筆畫提取的工作。在筆畫提取過程中主要需要解決兩個關鍵問題：（1）獨立筆畫的提取；（2）交叉筆畫在交叉段的處理。

目前大多數的筆畫提取方法是細化處理：將輸入的漢字圖片處理為骨架圖。對整個漢字骨架進行跟蹤，初步提取筆畫。此時，無交叉筆畫已完成提取，但分叉點連接著多個不完整的筆畫段。此后通過一定的合并、拆分規則，最終獲得準確筆畫。這種處理方式能夠將漢字的筆畫方向信息完整地保留下來，同時因為整個骨架圖為單像素寬度，降低了后續筆畫提取的計算復雜度。這種方式也存在著較為明顯的缺點：（1）失去了筆畫的寬度信息；（2）在細化過程中，會引入一定的形變，為后續筆畫的正確提取造成了一定的難度[1-3]。

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

參考文獻[4]提出了基于Delaunay三角剖分的三角網格表征與點到邊界方向距離PBOD曲線相結合的筆畫提取方法。相較于傳統的基于漢字細化和LGA等方法，該方法從漢字的基礎特征著手，提取效果較好。

上述方法只是針對于某一單一風格的書法字筆畫提取，或者印刷體漢字提取，沒有針對多類別的書法字的筆畫提取進行驗證。

1.2 筆順信息提取

漢字是一種象形文字，其典型的書寫規則：先左后右，先上后下。本文利用該規則，結合已有的筆畫信息，對筆畫進行排序，獲得筆順信息。

2 系統框架

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

3 骨架筆畫提取

3.1 漢字骨架

漢字的骨架由細化算法獲取，它必須滿足[5]：

（1）只有一個像素寬；

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

（3）必須保持物體的拓撲結構。

將漢字骨架中的點分為三類[5]：

（1）Nc（P）=1，則P為端點；

（2）Nc（P）=2，則P為普通點；

（3）Nc（P）≥3，則P為交叉點。

其中Nc（P）為骨架點P八鄰域內鄰居點數量。圖2為書法字骨架及端點、交叉點提取結果示例。

3.2 筆畫段提取

本文中所使用的骨架筆畫段提取方法是根據文獻[5]、[6]、[7]中所提出的筆畫提取方法，并對其進一步改進而來。

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

非獨立筆畫：某一筆畫與該漢字其他筆畫中的一筆或者多筆相交或粘連，則該筆畫稱之為非獨立筆畫，它是由端點、普通點以及交叉點構成，或者由交叉點、普通點所構成。

骨架筆畫段提取步驟如下：

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

骨架筆畫段的記錄方式為：

Si={Bi，Ei，Sni}（1）

式中i表示筆畫段的標號，Bi、Ei為筆畫段的起點與終點，Sni為筆畫段的鏈碼表示，如圖2所示的左上角的筆畫“撇”的筆畫表示為：

{（19，17），（11，33），（666566645644646654）}

筆畫段提取完成之后，可能存在錯誤的筆畫段，因此需要依據下述規則對筆畫段進行修正，以獲得準確的骨架筆畫。

規則1.如果li<L×η（i=1，2，3，…，Ns），則該筆畫為一個錯誤筆畫。其中，η為閾值，本文設為1/3，Ns為已提取到的筆畫數，li為第i筆筆畫長度：li=lenght（Sni） 1。

設L為該字已提取筆畫的平均筆畫長度：

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

經過二值化處理之后的圖像可以認為是一個多邊形，黑色像素點數目可以近似為該多邊形的面積S，骨架的總長度可以看作經過多邊形中軸的多邊形的底b，漢字筆畫的平均寬度可以近似看作這個多邊形的高h，由多邊形面積公式S=b×h推導出近似的平均筆畫寬度μw的計算公式：

NPB為經過二值化處理之后的書法字黑色像素點數，NSP為骨架點的數目。

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

4 筆順信息獲取

漢字的書寫順序大致滿足如下規則：從左到右，從上到下。本文依據該規則提取書法的筆順信息。

4.1 筆畫起止點的確定

本文規定書法圖像左上起點為坐標原點，x軸正向為原點指向其右側，y軸正向為原點指向其下側。

對于骨架筆畫Si的端點Bi，Ei，當其滿足如下條件之一：

Bi.x≥Ei.x&Bi.y>Ei.y（4）

Bi.x>Ei.x&Bi.y≥Ei.y（5）

則將端點Bi，Ei進行交換。

4.2 標定筆畫順序

對已正確獲得起止點的筆畫，按照如下確定筆畫提取的優先順序：

（1）如果Bi.x<Bj.x，則筆畫Si先于Sj書寫；

（2）如果Bi.x=Bj.x且Bi.y<Bj.y，則筆畫Si先于Sj書寫；

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

Si=max{Ei.x 1.3×Ei.y}（6）

則該筆畫為末筆。

5 筆畫復原

前文中所提取的骨架筆畫丟失了書法字的寬度信息，將筆畫寬度信息恢復。

獨立筆畫的完整筆畫輪廓是一條封閉的曲線；非獨立筆畫在剔除交叉區后，其輪廓線是斷開的，需要補全成為封閉曲線。因此，對于獨立筆畫而言其所對應的輪廓只需通過連通性檢測即可實現寬度信息恢復。本文重點解決對于存在交叉區域的筆畫寬度信息恢復。

5.1 交叉點簇與交叉區域

由于骨架圖在提取過程中會產生一定的形變，因此交叉區域在骨架中會產生兩種情況：

（1）在交叉區域，由交叉點與普通點組成，如圖4左圖：由兩個交叉點包圍著多個普通點在小的鄰域內連續出現。

（2）在交叉區域，骨架圖完全由交叉點組成，如圖4右部，在一個小的鄰域內連續出現交叉點。

第二種情況是由骨架圖的形變所引起。為了修正形變，根據最大圓準則[5-8]進行簡化處理：對于骨架圖中的兩個特征點（交叉點），分別計算出它們在原圖（未骨架化的圖像）中到筆畫輪廓的最大內切圓的半徑。如果兩個特征點之間的距離小于或等于各自內切圓半徑之和，那么這兩個特征點對應一個筆畫的相交區域。將第二種情況中的由交叉點所包圍的普通點標定為交叉點。進一步將上文中所述的兩種情況歸并為對交叉點簇的處理。

本文使用點簇的虛擬質心Pc來標定筆畫交叉區域，Pc的計算如式（7）所示：

其中，N為交叉點簇中交叉點的數量，pif為該點簇中的第i個交叉點。

5.2 交叉區處理

前文中通過交叉點簇的中心完成了交叉區域的定位，為了進一步減少待處理的像素點的數目，使用輪廓圖來進行交叉區域的處理。

骨架是圖像的中軸[9-11]，因此，對書法字輪廓圖做筆畫提取，交叉區域的輪廓圖有如下的特點：

（1）位于交叉區域的輪廓線，相對于交叉區域質心位置相對固定，且局部不相交。

（2）筆畫在交叉區域的輪廓缺失。

因此，要提取到完整的筆畫信息需要補全筆畫缺失的輪廓點。

5.2.1 聚類坐標系建立

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

（1）坐標系原點為交叉區域質心，x軸正方向為由原點指向右側，y軸正方向為由原點指向上側。

（2）若交叉筆畫在交叉處的行筆方向LDir（i）、LDir（j）與（1）中所建立的坐標系中坐標軸不平行，則坐標系逆時針旋轉θ=45°。

5.2.2 輪廓點聚類

坐標系的建立，為輪廓點的分類奠定了基礎。按照輪廓點所屬象限將輪廓點分為四個類別，具體步驟如下：

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

（2）計算每一個輪廓點與x軸正方向的夾角θ，同時計算其與原點的距離|piCo-Pc|并記錄。

（3）計算每一個點的類別C（θ），并將其記錄。

其中：

5.2.3 輪廓連接點確定

使用輪廓圖提取筆畫的關鍵點是找到輪廓點中拐點或角點，來確定筆畫的走向，完成筆畫的提取。為了補全筆畫所缺失的輪廓點，需要確定輪廓線在交叉區域的拐點，找到各個象限中距離原點最近的點，從而確定輪廓圖在交叉區域的拐點即筆畫在此處的鏈接點Plinkc。

Plinkc=arg min{piCo-Pc |piCo∈P_set（c）}（9）

其中，P_set（c）為第c類輪廓點集合，Plinkc為第c類連接點。

交叉筆畫可以分為“十”型交叉及“T”型交叉，針對不同的交叉類型，選擇不同連接點。

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

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

6 實驗分析

6.1 實驗結果

圖8為楷體字“生”的筆畫及筆順提取示意。為了驗證本文所提出算法的有效性，本文使用三類不同書法風格的單字圖像完成筆畫提取實驗。實驗結果如表1、表2所示。

6.2 實驗結果分析

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

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

7 總結

本文提出將書法漢字圖像骨架圖與輪廓圖相結合的方法，能夠完成適應多類書法風格的書法漢字筆畫提取以及基于書寫規則的筆順信息提取。相較于傳統方法，本文所提出的算法能夠有效地降低筆畫提取操作所需要的時間，簡化了計算復雜度，并且對多類書法字的筆畫、筆順提取都取得了較好的效果。

下一步的工作將是繼續對算法進行修正，以獲得針對更多類別書法字的筆畫提取的結果，提高筆畫提取的準確率。

參考文獻

[1] 張世輝，孔令富.漢字識別及現狀分析[J].燕山大學學報，2003，27（4）：367-369.

[2] 李正華，胡奇光.漢字筆畫提取的算法與實現[J].計算機應用與軟件，2004，21（7）：96-97.

[3] 王建平，藺菲，陳軍.基于手寫體漢字筆畫提取重構的識別方法[J].人工智能及識別技術，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] 陳睿.漢字離線識別技術中筆畫提取模型研究[D].重慶：西南師范大學，2004.

[6] 陳睿，唐雁，邱玉輝.基于筆畫段分割和組合的漢字筆畫提取模型[J].計算機科學，2003，30（10）：74-77.

[7] 章夏芬.中國數字書法檢索與作品真偽鑒別的研究[D].杭州：浙江大學，2006.

[8] 章夏芬，莊越挺，魯偉明，等.根據形狀相似性的書法內容檢索[J].計算機輔助設計與圖形學報，2005，17（11）：2565-2569.

[9] 郭晨.基于圖像處理技術的手寫體漢字特征分析的研究[D].天津：天津科技大學，2010.

[10] 孫華，李愛平.支持向量機的古漢字識別研究[J].電腦知識與技術，2013，9（18）：4296-4298.

[11] 苗晉誠.基于骨架化、骨架劃分獲取書法漢字結構特征的方法[J].昆明理工大學學報（理工版），2008，33（3）：53-61.