基于流水模式的古籍文獻漢字切分算法

倪 劼

0 引言

在我國，古籍是指1912年之前書寫或印刷的，具有中國古典裝幀形式的書籍。以語言文字分類，漢文古籍占比最大。通過現(xiàn)存古籍數(shù)字化，尤其是漢文古籍全文數(shù)據(jù)庫建設，不僅可以讓更多讀者挖掘其中蘊藏的財富，也可以最大程度保護中華文脈和傳統(tǒng)文化。古籍文獻漢字切分作為古籍文獻全文數(shù)據(jù)庫建設前期重要的基礎性工作之一，主要是將圖像化后的文獻進行計算機處理，使其中的文字逐個呈現(xiàn)出來，切分的準確度將對后期的文字識別有直接影響。因此，加強這方面的技術研究可以提高切分的準確性與適用性，在促進古籍數(shù)字化工作方面具有重要的意義。

目前用于文字切分的算法有基于圖論的切分算法[1]、基于神經網絡的切分算法[2]、基于信息測度的切分算法[3]、基于偏微分方程的切分算法[4]，大多數(shù)算法并未在古籍文獻方面應用。古籍文獻因其特殊性，受保存條件影響，頁面內容會有缺失、模糊等情況，且刻本與抄本中往往內容非常“擁擠”，文字間常有交錯與粘連現(xiàn)象，這些因素都成為文字切分的難點。在較早一段時期，基于投影法的切分方式使用較為普遍[5-6]，通過對二值化后的圖像進行逐行或逐列累加形成投影圖，利用投影中的間隙找出相鄰文字的分界點實現(xiàn)切分。但在具體應用中，對圖像質量以及文字分布有著較為苛刻的要求。于是，基于連通域算法的方式在古籍文獻切分中得到了較多的運用[7-10]，連通域算法常用于圖像目標的分割與提取，具有相同像素值的鄰接點組成的區(qū)域為連通區(qū)域，對連通區(qū)域進行分析從而實現(xiàn)圖像目標的分割提取。另外，基于滴水算法的切分方式也被常用于古籍文獻中，其原理是水滴沿著圖像字符輪廓下落或水平滾動，在輪廓凹陷處，它將穿透輪廓繼續(xù)下落，最終水滴運動軌跡就形成了字符切分路徑，該算法常被用于字符粘連部分的輪廓切分[11-13]。近年來，基于分層投影過濾的遞歸切分算法[14]、基于猶豫模糊集的切分方法[15]，基于最小加權分割路徑的切分方法[16]，基于可變窗口的切分方法[17]，基于分段投影方式的切分[18]，以及基于改進后的SOM聚類算法[19]等等，這些方法在古籍文獻切分中也有應用。在現(xiàn)有研究中，投影法、連通域算法、滴水算法的三種切分方式存在著一定的局限性，若圖像噪聲較大，文字間存在交錯、粘連等情況時，采用投影法將無法準確進行文字切分。連通域算法在進行切分時，可以很好地解決文字交錯的問題，但是面對文字粘連情況卻無能為力。滴水算法則受到起始位置、水滴下落規(guī)則以及方向等因素制約，在不加限制的情況下容易出現(xiàn)切分錯誤，受制于古籍文獻的復雜度，精確給定起始位置的難度較大。其他的研究成果中，大多是在傳統(tǒng)算法基礎上進行了改進，雖取得了一定效果，但從實驗過程來看，選擇樣本種類較為單一，樣本數(shù)量較少，且樣本中并未有明顯的文字交錯與粘連，其算法的適用性未能有所體現(xiàn)。

面對上述問題，本文提出新的古籍文獻漢字方式，能在多種類型的古籍文獻中實現(xiàn)漢字切分，解決古籍文獻切分算法中的局限和適用性不強的問題，具體流程見圖1。首先，對古籍文獻圖像進行預處理，包括圖像矯正、高斯濾波、二值化操作、形態(tài)處理等操作；其次，利用投影法與圖像形態(tài)處理實現(xiàn)列切分；最后，結合古籍文獻漢字特征，借鑒流水在下落時的狀態(tài)，以呈現(xiàn)的運動軌跡作為切分依據(jù)，實現(xiàn)古籍文獻漢字切分，并將這種新的切分方式命名為流水算法。

圖1 古籍文獻漢字切分流程

1 材料與方法

1.1 研究對象

本文選擇不同時期、不同類型的古籍文獻作為研究樣本。以蘇州圖書館藏宋刻本《容齋隨筆》、南京圖書館藏清抄本《金陵防守利便》、清刻本《蓮洋詩抄》、清抄本《鉅鹿東觀集》、明刻本《初唐詩》、明刻本《博異記》為例，樣本數(shù)據(jù)見表1。樣本各有特點，時間跨度較大，其中有刻本、抄本，內容有印章、批點、列分割線，文字有稀疏之異、版面有框格之分，且字與字之間有一定的交錯與粘粘，確保樣本選擇有一定代表性，部分樣本見圖2。本文系統(tǒng)開發(fā)工具為Python3.7，圖像處理使用OpenCV3.3。

圖2 樣本圖示

表1 本文研究樣本數(shù)據(jù)詳細列表

1.2 圖像預處理

切分前，對圖像進行預處理。古籍圖像的版面會有大量信息而產生復雜的噪聲，如原圖中的印章、批點、劃線，以及筆畫不均、字體斷裂、版面污漬、圖像傾斜等情況。圖像預處理目的就是將圖像中的不利信息進行最大程度消除，增強圖像質量，改善文字清晰度，為后期的處理提供最佳環(huán)境。本文預處理包括圖像矯正、高斯濾波、直方圖處理、二值化操作、圖像形態(tài)處理這幾個步驟。圖像矯正是通過計算機算法，去除原始圖像中的傾斜角度，使得圖像保持最佳角度，方便后期的切分。本文采用使用Hough變換算法，尋找最長間隔線計算矯正傾斜角，完成對原始圖像的傾斜矯正。圖像預處理見圖3，采用高斯濾波方式去除原圖中的噪聲，以及灰度化、直方圖、直方圖均衡化、二值化處理，最終進行圖像形態(tài)操作，預處理結果見圖3(f)。

圖3 圖像預處理

1.3 列切分

古籍文獻多以豎式排列，列與列之間具有一定間隔，且有些文獻中存在分割線。列切分一般由投影法完成，因為列與列之間存在明顯的間隔，這非常適用投影法來處理，列切分處理過程如圖4所示。首先將圖4(a)二值化圖中每一列的白色像素值相加，形成圖4(b)的投影圖，通過投影圖已經能夠大致辨別出每一列所在的位置，但由于古籍圖像的列與列之間會存在分割線以及邊頁等情況，這些內容也會被投影出來，將影響到列切分的準確性。本文采用對投影圖像再一次進行形態(tài)運算，運用其中閉運算和開運算將投影圖像進行處理，對二值化圖像中的分割線、非正文內容進行消除，最終圖4(c)呈現(xiàn)的就是正文列投影，以此為依據(jù)可以得到正文列位置。

圖4 列切分處理過程

1.4 字切分

1.4.1 基本思路

古籍多為繁體字，結構豐富。古籍中的漢字也是書法表現(xiàn)形式，以楷書居多，筆畫形式以“永字八法”為基礎，具有點畫齊備、結字方整、章法和諧的特征。這些特征使古籍文獻漢字呈現(xiàn)出有利于切分的顯性要素：一是古籍文獻漢字呈現(xiàn)矩形形態(tài)，可以以此分析出文字的大致位置；二是書法的形式使得字體能夠呈現(xiàn)更加完美的結構，利用其中的起筆、運筆、收筆時的變化，可對文字進行細切分。

流水在高處下落時，會受重力作用一直垂直向下運動。在這個過程中若遇到障礙物，流水會沿障礙物邊緣繼續(xù)向下，當進入一片洼地時，會逐步將洼地注滿，再進一步沿障礙邊緣行進，直至到達底部。在進行古籍文獻漢字切分時，可以借鑒流水模式，將待切分圖像中的文字，看做是流水行進中的障礙物，以流水在障礙中的運動軌跡作為最終切分的依據(jù)。根據(jù)古籍文獻漢字呈現(xiàn)的矩形形態(tài)以及書法特征，通過投影法加上閾值的方式，可以大致確定出交錯與粘連部分的具體區(qū)域，這個區(qū)域將作為流水的運動有效區(qū)域，使用算法計算得到最終切分位置。在待切分區(qū)域，將嘗試各個位置點作為流水起點，選擇將流水最終能夠到達底部的軌跡進行比較，路徑最短的那條軌跡將作為最終切分依據(jù)，實現(xiàn)交錯文字的切分；如流水不能到達底部，則將圖像上下翻轉，再進行一次反方向嘗試，若兩次均不能到達時底部，則認為該區(qū)域文字存在粘連現(xiàn)象。這時，將根據(jù)古籍文獻漢字中的書法特征，利用其起筆、運筆、收筆時的變化，以兩次流水軌跡中最接近的位置作為切分依據(jù)，實現(xiàn)粘連文字的切分，本文將此切分方式命名為流水算法。通過流水算法，可以實現(xiàn)古籍文獻漢字間隔、交錯、粘連情況的切分，解決了傳統(tǒng)算法中局限性的問題。

1.4.2 算法模型

采用逐字方式，在列切分的基礎上實現(xiàn)字切分，字與字之間的狀態(tài)可分為間隔、交錯、粘連三種情況。間隔狀態(tài)切分較為簡單，可直接通過投影法實現(xiàn)切分。在遇到交錯或粘連情況時，首先需要劃出待切分區(qū)域，再通過算法模型對區(qū)域內的字進行切分。待切分區(qū)域由投影法結合閾值獲得，結合古籍漢字中呈現(xiàn)的書法特征，本文選取黃金分割率0.618作為閾值參數(shù)，以平均字符高度的黃金分割點作為待切分區(qū)域的開始，在此基礎上增加半個字符平均高度值作為待切分區(qū)域的結束，具體表達公式如下：

式(1)中H表示平均字符高度，λ表示閾值參數(shù)0.618，hstart、hend分別表示待切分區(qū)域的起始和結束位置。待切分區(qū)域處理過程見圖5，圖5(a)為原圖中上下文字存在交錯或粘連，首先將圖5(a)進行二值化處理并向右旋轉90度得到圖5(b)，方框部分表示由公式確定出的待切分區(qū)域，再將待切分區(qū)域單獨取出，并以坐標軸的方式顯示，結果如圖5(c)所示。其中以X軸坐標每個像素點作為流水起始點，T記錄流水運動路徑，對該區(qū)域的流水路徑進行比較分析，作為最終切分依據(jù)。

圖5 待切分區(qū)域

在一個二值化圖像中，一個像素點只有可能是黑色或白色，本文中前景色為白色，即二值化后的文字顏色，背景色為黑色。流水每一步行進路徑選擇均與周圍像素值有關，若流水在坐標軸范圍內順利到達Y軸底部將被認為是有效路徑選擇，以此為依據(jù)進行交錯文字切分；若當前坐標x、y值超出X軸極值，或y值為負值時，均會認為選擇當前X軸像素點無法到達Y軸底部，則以此進行粘連部分切分。

在流水每次行進時都會首先查看當前點下面的三個像素，此時將有兩種情況：一是三個像素點顏色不全為白色；二是三個像素點全為白色。三個像素點不全為白色時，運動軌跡選擇如圖6所示。其中T 表示當前點位置，*為無關像素點，w為白色像素點，b為黑色像素點。圖中6(a)列出當前點下面三個像素位置以及命名，分別為p1、p2、p3。若p1、p2、p3不全為白色像素時，判斷順序如圖6(a)-(g)：第一步，只要p2為黑色，p1、p3不全為白色，下一步都將向p2位置移動，如圖6(b)、(c)所示；第二步，若p1為黑色，p2、p3為白色，下一步移動至p1位置，如圖6(d)所示；第三步，若p3為黑色，p1、p2為白色，下一步移動至p3位置，如圖6(e)所示，可以看出流水始終沿著重力向下移動；第四步，若p1、p3為黑色，p2為白色，則認為該像素為噪點，將會被流水吞沒，即p2像素值由白色轉為黑色，并將下一步移動至p2位置，如圖6(f)所示；第五步，若p2 為黑色，p1、p3為白色，則認為流水將流入洼地，此時需要將洼地用水注滿，即p2像素值由黑色轉為白色，并且移動位置保持不變，如圖6(g)所示。

圖6 流水運動軌跡選擇(一)

為避免待切分圖像中出現(xiàn)極細縫隙或極窄障礙條等極端情況，從而影響實際切分效果，本文在預處理過程使用多次濾波、以及調整卷積核大小方式對圖像進行操作，最大程度消除待切分圖像噪聲點。以上流程中的第四、五兩個步驟，也均是針對文字邊緣噪點的進一步處理。如當前點下面三個像素點全為白色，運動軌跡則有另一種選擇，如圖7所示。圖7中可以看出，p1、p2、p3同時為白色時，則需要獲取當前點左右兩側像素值，分別為：若右下方黑色像素距離當前點更近，則下一步向右移動，如圖7(a)所示。同理，若左下方黑色像素距離當前點更近，則下一步向左移動，如圖7(b)所示。若當前像素兩側出現(xiàn)白色像素時，則認為當前這一行像素為洼地，此時需要將這一行洼地用水注滿，即這一行像素值由黑色轉為白色，并且移動位置退回至上一步，如圖7(c)所示。

圖7 流水運動軌跡選擇(二)

所有位置都嘗試完成后，進入切分計算。待切分區(qū)域有交錯或粘連兩種情況，待切分區(qū)域的處理方式也分為兩種。

一是如果有流水軌跡能夠順利到達待切分區(qū)域底部，則認為該區(qū)域存在文字交錯。具體公式如下：

式(2)中T表示流水運動軌跡(x，y)坐標集合，n表示有效運動軌跡T的總數(shù)量。將有效軌跡做比較，得到其中最短的軌跡作為結果Tmin；式(3)中將Tmin集合中所有X軸坐標求平均值，得到結果x為最終的交錯部分切分的位置。

二是如果在所有位置進行嘗試后，未能有流水軌跡到達待切分區(qū)域底部，首先會將待切分區(qū)域圖像倒轉，再從反方向進行嘗試。若兩次嘗試都未有軌跡到達待切分區(qū)域底部，則認為該區(qū)域字符存在粘連。筆者認為，此時可根據(jù)書法的特征，古籍圖像漢字粘連時，粘連部位存在筆鋒最短路徑，可利用此作為切分依據(jù)，如圖8所示。

圖8 粘連位置選擇切分點

此時比較兩側軌跡，取兩側軌跡中最接近部分作為粘連字符切分點。公式如下：

式(4)中i、j分別表示以不同方式行進的軌跡坐標，對兩側所有軌跡的距離進行計算，得到距離的集合。

在式(5)中，對n個距離集合進行比較，取最短距離dmin作為最終的切分點。以上方式，通過借鑒流水模式，結合古籍文獻漢字特征，實現(xiàn)了間隔、交錯、粘連情況下的文字切分。

1.4.3 字切分演示

字切分演示如圖9所示。圖9(a)為待處理列文字，首先將二值化列文字圖像進行投影，得到圖9(b)。此時若想通過投影法切分文字將十分困難，除“容”與“齋”、“總”與“序”字之間可以通過投影法進行切分，其余切分點很難被找到。為更直觀看出不同算法切分實際效果，使用三種算法對演示部分圖像文字進行切分軌跡比較，三種算法分別是傳統(tǒng)滴水算法、改進滴水算法以及本文的流水算法。圖9(c)采用傳統(tǒng)滴水算法，在待切分區(qū)域中通過Descending-left 方式，由待切分區(qū)域x軸的0點作為滴水起始位置進行切分，看到“隨”與“筆”、“集”與“總”字大體上切分軌跡能沿著字體邊緣行進?！拔濉迸c“集”字之間受到筆畫因素影響，切分軌跡出現(xiàn)了一些小的偏離。而“筆”與“五”字之間由于起始位置不佳，最終將“五”字的一部分切分出去。在實際切分過程中，無法給出合適的起始點位置是傳統(tǒng)滴水算法存在的最大問題。為此，本文通過選擇待切分區(qū)域投影值最小的點作為起始位置嘗試切分，對傳統(tǒng)滴水算法進行改進，改進后的切分效果如圖9(d)所示。從圖中可以看出，調整起始位置后，交錯部分的切分軌跡比傳統(tǒng)滴水算法有了很大改善，但粘連部分的“筆”與“五”字之間切分軌跡仍沒有能夠達到理想位置。本文流水算法切分效果如圖9(e)所示，為了便于觀察，在原圖上使用不同顏色進行切分展示，通過流水算法形成了間隔、交錯、粘連三種不同情況時流水的軌跡，作為最終字切分依據(jù)。圖9(e)中的細直線表示可以通過投影法直接切分；若上下文字存在交錯，則通過流水軌跡中最短路徑作為交錯部分的切分位置；若存在文字粘連，則通過算法求出粘連部分最接近點坐標，以此位置作為粘連切分點。從圖9(c)中可以看出，“容”與“齋”、“總”與“序”字之間通過投影法進行切分，“隨”與“筆”、“五”與“集”、“集”與“總”字之間存在交錯，通過穿越交錯區(qū)域流水最短路徑平均值作為切分依據(jù)；而“筆”與“五”字之間存在粘連現(xiàn)象，則是通過上下流水聚集區(qū)域最接近點作為切分依據(jù)。

圖9 字切分處理演示

2 古籍文獻漢字切分實踐

2.1 列切分結果分析

列切分的準確率受頁面分割線、圖像傾斜角度等因素影響，列切分準確率公式為：

式(6)中Ln表示正確切分的列數(shù)，Lt表示列總數(shù)，Sl為列切分正確百分比。本文采用二值化投影后的形態(tài)處理，消除頁面中的分割線、以及非正文內容殘影。本文對三種古籍文獻共計888列進行切分，總體準確率為98.65%，列切分結果如表2所示。列切分準確率受到文獻保存完整性影響較大，在面對版面污漬較多、頁面內容不完整情況時，會出現(xiàn)切分錯誤現(xiàn)象。

表2 樣本列切分結果

2.2 字切分結果分析

樣本切分效果如圖10所示。為了更加清楚了解切分中的過程，圖中分別用不同顏色的方框來表示切分時遇到的情況。紅色方框，表示該字與下方文字存在一定間隔；綠色方框，表示該字與下方文字存在交錯；藍色方框，表示該字與下方文字存在粘連。從圖中可以看出，運用本文中算法取得了較好的切分效果，能夠較為準確地切分到每個漢字的主體結構，且從圖10(c)可以看出，圖像預處理對原圖中的傾角進行了矯正。

圖10 切分效果顯示

流水算法實現(xiàn)古籍文獻漢字切分時，雖然有的字一些邊緣部分被切分了出去，但對字的整體識別沒有影響，本文認為這種情況屬于正確切分。本文將未能正確切分情況，分為過切與漏切兩種，切分結果判定示例如圖11所示。圖11(a)中的“齋”與“隨”字之間存在交錯情況，通過流水算法能夠很好地就交錯位置進行切分。從圖中可以看出，雖然“齋”有少量邊緣部分被切除出去，但并不影響整體字的識別，此類情況將被判定為正確切分。圖11(b)中“乘”與“木”之間存在明顯的粘連，通過流水算法能夠準確以粘連位置作為切分點。圖11(c)“十”字由于字體所占像素較少，且有部分殘缺，被誤認為版面污漬，造成了漏切。圖11(d)中，由于“一”與“爻”兩字間的間隙較小，被誤認為一個字，造成了漏切。圖11(e)中，由于受到版面污漬影響，造成了過切。另外，切分結果受到版面圖像中的批點、模糊等因素，以及頁面殘損、字體結構分離影響，這也是造成錯誤切分的原因。若版面由墨汁等因素造成的污漬較大，將會被誤認為正文內容，造成過切。字體的結構也是造成錯誤切分的因素之一，若字體上下結構分離嚴重，或字與字間高度粘連，將也會出現(xiàn)過切或漏切現(xiàn)象。

圖11 字切分判定

為驗證流水算法效率，本文將采用分類任務評價方式，對流水算法在古籍文獻漢字切分中的可行性進行評估。分類任務的常用評價指標有：精確率(Precision)、召回率(Recall)、F 值(F1 Score)等等。具體公式如下：

式(7)中的p為精準率，本文表示被流水算法實際切分的漢字當中，結果為正樣本的比例，其中TP表示正確切分數(shù)，F(xiàn)P為過切數(shù)。

式(8)中的r為召回率，本文表示針對樣本總漢字數(shù)量而言，通過流水算法實際切分為正樣本所占比例，其中TP表示正確切分數(shù)，F(xiàn)N為漏切數(shù)。

式(9)中的f為精準率與召回率的綜合評價值，本文表示流水算法在切分樣本數(shù)據(jù)中的整體調和均值。

具體樣本切分結果見表3，所有樣本切分數(shù)量全部小于實際樣本數(shù)量，且從FP與FN值比較可以看出，不論何種樣本，漏切數(shù)均超過了過切數(shù)。導致這一結果的原因與本文算法中的流水區(qū)域閾值選擇有關，為盡量避免由于字體結構分離使得的過切分概率增大，本文選擇黃金分割0.618作為閾值參數(shù)，雖然有效避免了過切分現(xiàn)象發(fā)生，但是也使得實驗過程中的漏切分數(shù)量增加。從表中也可以看到，《金陵防守利便》《鉅鹿東觀集》兩種抄本的精準率雖然與其他刻本相差不多，但召回率分別為90.69%、95.05%。與其他刻本相比，受到字體、版面等因素影響，抄本中出現(xiàn)漏切現(xiàn)象較多?？傮w來看，文獻的年代對結果影響不大，僅與文獻的保存情況直接相關。最終實驗結果，樣本總體字切分精準率為99.00%，召回率為95.62%，F(xiàn)值為97.27%。

表3 樣本數(shù)據(jù)切分結果

3 結論

古籍文獻漢字呈現(xiàn)的復雜度較高，造成切分時難度遠大于現(xiàn)代印刷品，除去文獻的保存完整性因素，文字間的交錯、粘連情況也是切分難點。本文利用古籍文獻漢字特征，提出借鑒流水模式的思路實現(xiàn)古籍文獻漢字切分，并選取6本文獻中的87頁內容、共計14，503字進行算法適用性驗證。最終，列切分準確率達到98.65%，字切分精準率為99.00%，召回率為95.62%，F(xiàn)值為97.27%。受到樣本復雜度影響，刻本切分效果整體好于抄本。結果表明，流水算法在面對古籍文獻漢字存在交錯、粘連等情況時，也能取得較好的切分效果。流水算法實現(xiàn)難度低、易用性強、實際效果好，適合在古籍收藏機構推廣使用，配合當前國內大型互聯(lián)網公司的文字云識別產品，使得很多中小圖書館自主推進古籍數(shù)字化工作成為可能。本文研究雖然取得一定的效果，但在面對古籍中版面存在破損、多粘連漢字、結構分離嚴重的漢字等情況時，仍會有切分不準確的情況存在，還需要后續(xù)開展更深入的研究。隨著具體實踐研究的增多，相信古籍數(shù)字化工作將會不斷取得突破。