聚類+連體段判別的維吾爾文檔圖像單詞切分

徐學斌，吾爾尼沙·買買提，阿力木江·艾沙，朱亞俐，庫爾班·吾布力

1.新疆大學 信息科學與工程學院，烏魯木齊 830046

2.新疆大學 圖書館，烏魯木齊 830046

3.新疆大學 教師工作部，烏魯木齊 830046

1 引言

文檔圖像檢索作為信息檢索的重要分支，一直是研究的熱點。對于中文和英文等語言而言，字符都是獨立書寫，不存在字符與字符黏連書寫的情況，此類印刷體文檔圖像檢索一般是通過OCR（Optical Character Recognition）轉化后進行檢索，準確率高，檢索速度快。對于我國新疆地區的少數民族語言維吾爾語而言，其字母既可以獨立書寫，也可以有多個字母通過不同的順序組合相連書寫，因此對印刷體維吾爾文檔圖像進行字母切分與識別時準確率不高，用OCR技術對維吾爾文檔圖像進行檢索的研究相對滯后。近年來有學者提出針對維吾爾文檔圖像的關鍵詞檢索，首先對文檔圖像進行單詞切分，然后對輸入單詞圖像在切分好的單詞圖像庫中進行特征匹配，返回單詞圖像庫中匹配成功的圖像所屬的文檔圖像。由于只需對文檔圖像中的單詞進行切分和特征匹配，無需精確識別所有字母，因此系統復雜度大大降低，同時檢索效率較高。

文檔圖像的關鍵詞檢索系統首先要對文檔圖像進行準確的單詞切分，切分效果直接影響檢索結果。目前針對印刷體維吾爾文檔圖像的切分研究大多集中在字母切分方向，單詞切分方向的文獻較少。針對印刷體維吾爾文檔圖像的單詞切分，文獻[1]對投影得到的連體段進行聚類分析，通過計算連體段的重疊率來合并屬于同一單詞的連體段，平均單詞切分準確率達到了97%。文獻[2]針對手寫體維吾爾文檔圖像的單詞切分采用FCM（FuzzyC-means）融合K-means的聚類算法對文字區域之間的空白間距進行聚類，把距離分成單詞內距離和單詞間距離，從而得到單詞的切分點信息，平均切分正確率為80.68%。以上文獻在統計實驗結果時均忽略了“<< >>”“（ ）”“[]”等特殊標點符號漏切分的影響，未對文本行末尾被拆分書寫的單詞進行合并處理，而且切分準確率有待提高。針對以上問題對關鍵詞檢索結果的影響，本文采用K-means算法[3]對印刷體文本行圖像投影后連體段之間的空白間隙進行聚類分析，得出最佳間距判別閾值，同時對與空白間隙相鄰的連體段進行篩選和識別，結合二者信息得到最佳切分點的位置信息和需要進行單詞合并的單詞位置信息，實現對印刷體維吾爾文檔圖像準確的單詞切分。

2 維吾爾文單詞切分規則概述

2.1 單詞劃分

詞是維吾爾語中能獨立運用的最小語言單位 ，詞與詞之間有明顯的間隙分隔開，不存在像漢語中單詞切分時的分詞問題。因此詞與詞之間的間距是維吾爾語文檔圖像中確定單詞切分點時最重要的依據，多數關于單詞切分的文獻都是以單詞與單詞之間的間距為基礎。本文通過對文本行中所有連體段之間的間距進行聚類分析來設置間隙判別閾值，區分單詞間的間距和單詞內部的間距，連體段之間的間距大于設定閾值則說明此相鄰連體段屬于不同的單詞。

2.2 標點符號的影響

維吾爾語中，一般而言標點符號與單詞之間的間距小于詞與詞之間的間距，但明顯大于單詞內部各連體段之間的間距，比如“.”“?”“!”“：”“?”等標點符號。因此，設置合適的間距判別閾值，即可獲得此類標點符號與單詞之間的切分點坐標。然而對于“<< >>”“（ ）”“[]”等標點符號，通常是左半部分與單詞的間距略大于單詞內連體段的間距，而右半部分與單詞的間距和單詞內連體段的間距相同，因此無法根據這類標點符號與單詞的間距來確定單詞的切分點位置。文獻[1]中將此類標點符號看作與其間距最小的單詞的一部分來進行切分，不符合后續關鍵詞檢索系統的需要，本文中將所有的標點符號看作一個獨立的切分單元進行切分。

2.3 合并拆分書寫的單詞

由于維吾爾語中不同單詞的長度一般不同，某些長度較長的單詞位于行末時，由于書寫位置不夠往往被拆分成兩個部分進行書寫，一部分位于第一行的行末位置，并在末尾用符號“-”進行標示，另一部分位于下一行的開始位置。在印刷體維吾爾文檔中這種寫法大量存在，被拆分的部分沒有詞意，屬于無意義切分。本文中對所有按這種書寫方式書寫的單詞在切分時進行合并處理，生成完整的單詞圖像。

2.4 本文方法系統框圖

與基于形態學操作的切分方法相比，對文檔圖像直接進行投影[4]的切分方法計算量較大，但是直接投影法[5]能夠獲得單詞圖像最底層的紋理特征，可操作性強，能夠使切分更加準確。因此，本文選擇在對文本圖像直接進行投影的基礎上，對投影所得的數據進行綜合分析與判斷，從而找到單詞圖像的精確切分點。本文方法的系統流程圖如圖1所示。

3 預處理

3.1 文檔圖像收集

文檔圖像的來源為新疆大學出版社出版發行的書籍《馬列主義經典著作選編》的維吾爾語版本，為模擬不同的辦公環境，用不同型號的打印機將紙質書籍掃描為文檔圖像，尺寸為716×1 011。由于長期翻閱導致文檔發黃，加上掃描的環境不同以及紙質文檔是雙面打印的影響，收集的文檔圖像帶有各種各樣的噪聲，如傾斜、椒鹽噪聲等，一些圖像甚至帶有較明顯的重影，如圖2所示。

3.2 圖像去噪

圖1 單詞切分系統流程圖

圖2 原始文檔

為最大限度保留文檔圖像上文字的筆畫信息，去除其他干擾信息，首先需要對所收集的文檔圖像進行去噪處理。圖像上的噪聲基本是在紙質文檔印刷后引入的，如翻閱、掃描等過程，與圖像上的文字信息無關。維納濾波[6]當噪聲與信號無關時有很好的的效果，因此本文通過維納濾波來去除圖像上的噪聲。

3.3 圖像增強

為了能夠使圖像中文字的筆畫信息更加清晰，突出文字像素和背景像素之間的差別，同時減小不同圖像之間的亮度和對比度差別，本文選取線性灰度增強的方式對原始圖像進行增強處理。設原始圖像 f(x,y)在變換前的灰度范圍是[a,b]，增強后F(x,y)灰度范圍為[c,d]，則線性灰度增強函數的表達式為：

其中saturate_cast表示將增強后的像素值歸一化至0～255范圍內，通過調整a、b、c、d的值使增強后的圖像中像素的灰度差異性變大，易于設置閾值來區分文字像素與背景像素。

3.4 傾斜校正

所收集的部分文檔圖像在掃描過程中引入了不同程度的傾斜，而利用水平和垂直投影對維吾爾文檔圖像進行連體段切分時要求圖像的傾斜角不能大于0.5°，因此需要對所收集的文檔圖像進行傾斜校正。本文通過對常用的霍夫直線傾斜角檢測方法[7]進行優化，來實現文檔圖像的傾斜校正。由于部分圖像的文本傾斜角小于1°，計算傾斜角時誤差較大，因此本文首先統一對所有收集的文檔圖像逆時針旋轉2.5°，然后進行霍夫直線檢測，根據檢出的直線上兩個點的坐標求得該直線的傾斜角。最后刪除數值明顯過大的傾斜角，對剩余的傾斜角求均值，將求得的均值作為該文檔圖像的傾斜角，利用此傾斜角順時針旋轉文檔圖像，從而實現傾斜校正，降低檢測誤差造成的影響。

3.5 圖像的灰度化與二值化

圖像的灰度化采用常用的加權平均法，設原圖像為f(x,y)，灰度化后的圖像為g(x,y)，則表達式如下：

g(x,y)=0.299R(x,y)+0.578G(x,y)+0.114B(x,y)（2）其中，R(x,y)、G(x,y)、B(x,y)分別為原圖像的三個顏色通道的像素值。圖像的二值化采用最大類間方差法[8]，即按圖像的灰度特性，將圖像分成文字信息和背景圖像兩部分，尋找使背景和文字像素之間的類間方差最大時的閾值，作為圖像二值化的全局閾值，文檔圖像經過預處理后的效果如圖3所示。

圖3 預處理效果圖

4 單詞切分

4.1 文本行切分

設 p(x,y)為圖像上任意一點的像素值，將經過預處理后的文檔圖像的每一行的像素值進行累加，P(y)為每一行的像素累加值，P(Y)為所有行像素累加值的最大值，表達式如下所示：

其中，m為圖片寬度，n為圖片高度，j為圖片上任意行坐標，i取0到m-1之間的所有整數。設區分空白行與文字行的閾值為K，用每一行的行像素累加值與K比較大小，大于K則判定該行中沒有文字信息，為背景行，反之則判定該行中存在文字信息。由于經過預處理后的文檔圖圖像仍然存在殘留噪聲點的干擾，因此根據經驗設閾值為所有行像素累加值的最大值減去200，來

降低殘存噪聲點的干擾。根據閾值K獲取任意文本行在垂直方向的切分點坐標的表達式如下：

P(yi-1)>K?P(yi)>K?P(yi+1)K?P(yj+1)>K （6）其中，i與 j為圖像的行坐標，且滿足 j-i>10，則該文本行在垂直方向的開始行坐標為i，結束行坐標為 j，根據i與 j的坐標即可將此文本行在圖像中切分出來，切分效果圖如圖4所示。

4.2 連體段切分

連體段[9]是對文本行進行垂直投影時彼此相連，沒有空白間隙的單元，獨立的字母、幾個字母相連以及標點符號等都視為一個連體段，連體段是最小的切分單元。與文本行切分原理一樣，設 p(x,y)為文本行圖像上任意點的像素值，P(x)為文本行圖像上任意一列的像素累加值，P(X)為所有列的像素累加值的最大值，設區分文本行圖像中空白列與文字列的閾值為H，表達式如下：

其中，l為已讀取文本行圖像的高度，i為圖像上任意列的坐標，j取0與l-1之間的整數。同理閾值H取值為P(X)-100，若圖像上列像素累加值大于H則視為空白列，反之則為帶文字信息列，依據此規則計算連體段的切分位置坐標的表達式如下：

其中，i、j為文本行圖像上任意行坐標，且i-j>3,i與j分別為連體段初始位置和末端位置的行坐標，根據位置坐標即可將連體段切分出來，效果圖如圖5所示。

4.3 合并連體段

4.3.1 自適應閾值計算

利用維吾爾語單詞內部連體段之間的間距和單詞之間的間距的差別，設置合適的閾值來區分各連體段，若相鄰兩連體段之間的間距大于閾值，則其屬于不同的單詞，在此間隙處進行切分處理。若相鄰兩連體段之間的間距小于閾值，且經過分析間距兩側的連體段都不是標點符號，則對此間隙兩側的連體段進行合并處理，若此間隙兩側連體段經過分析存在標點符號，則在此間隙處進行切分處理。設判別閾值為M，為了適應不同字體、字號與格式的文檔圖像，用K-means算法對任意文本行中的所有連體段之間的間距進行聚類分析，計算出適合此文本行的判別閾值。任意文本行圖像上連體段之間的間距分為兩類，第一類為單詞之間的間距以及標點符號與單詞之間的間距，第二類為單詞內部連體段之間的間距。計算閾值M的表達式如下：

其中，A與B分別為兩類間距的聚類中心，在求聚類中心時根據經驗去除了數值過大的間距值，來消除頁邊距空白處殘留的噪聲點對聚類結果的影響。

4.3.2 標點符號處理

對于“.”“?”“!”“：”“?”等標點符號[10-11]，其與單詞之間的間距一般大于M，根據此類標點符號與單詞之間的間距大小即可將其正確切分。“<< >>”“（ ）”“[]”等標點符號因其與單詞之間的間距與單詞內部連體段之間的間距相似，無法根據閾值M判斷切分點，對于這類標點符號通過對其提取特征來進行區分。由于標點符號的寬度一般都小于2M，因此在對文本行中的連體段進行切分時，針對寬度小于2M且與相鄰連體段之間的間距小于M的連體段，首先提取其輪廓的高度、寬度，以及距文本行上下邊界的距離等特征。若以上特征值滿足表達式（12）或表達式（13），說明該連體段可能為要尋找的標點符號，但仍需對其做進一步判斷，表達式如下：

圖4 文本行投影圖

圖5 連體段投影圖

其中a、b、c、d分別為連體段的寬度、高度，以及與上下邊界的間距值，表達式（12）為判斷符號“（）”與“[]”的條件，表達式（13）為判斷符號“<< >>”的條件。用間距判別閾值M作為判別基礎是因為M本身包含了文本行中文字的字體與字號等信息，將其作為對連體段的簡單輪廓特征進行判別與篩選的基礎，能夠減小字體字號等變化帶來的影響。隨著文字的字體變化，標點符號的輪廓大小在整個文本行中所占的比例也會變化，因此在根據連體段的輪廓特征對其進行判別和篩選時，在篩選范圍值中加入了一定的緩沖量，以此來消除字體等變化對篩選結果的影響。

根據連體段的簡單輪廓特征可以將其與多數連體段區分開來，但無法區分與其有相似輪廓特征的符號，比如符號“”“”“”“”的輪廓大小與符號“（ ）”“[]”相似，符號“”“”輪廓大小與“<< >>”相似，因此需進一步提取特征來判斷。對于“（）”“[]”等符號而言，其特點是寬度較窄且高度較高，同時構成符號的黑像素彼此相連，沒有被背景像素隔開的黑像素。對于與其大小相似的符號而言，構成這類符號的黑像素都被背景像素分割成了幾部分。因此，在篩選與“（）”等標點符號相似的連體段時，首先將連體段圖像放大四倍，然后進行水平投影，根據放大后的連體段的高度信息以及放大后的圖像在水平投影中得到的連體段數目信息即可將與其相似的標點符號區分開來。構成符號“<< >>”的黑像素的特點是被背景像素分隔成兩部分，而與其輪廓大小相似的符號的黑像素彼此相連，沒有被背景像素分開，因此根據這一特點可將與其相似的符號進行區分。由于符號“<< >>”無法根據投影來獲取連體段的數目，因此用凸包檢測[12]的方法來獲得連體段的數目。對連體段做進一步特征提取的示意圖如圖6所示。

圖6 特殊標點判別示意圖

圖6 中e為對符號“（）”“[]”及與其輪廓大小相似的圖像按原圖高度的四倍和寬度的兩倍放大后進行水平方向投影，得到的連體段數目；f為放大后符號的高度，根據實驗下限取值為閾值M的9倍時，滿足切分要求；g為將符號“<< >>”及與其輪廓大小相似的圖像放大3倍后檢測到的凸包的數目，這里凸包檢測的方式設為只檢測最外圍輪廓[13]，包含在外圍輪廓內的內圍輪廓被忽略，并且在檢測時略去了輪廓范圍太小的凸包，來消除筆畫邊緣噪聲點對檢測結果的影響。符號“（）”“[]”以及符號“<< >>”的判別條件分別如式（14）和式（15）所示：

4.3.3 合并拆分書寫單詞

維吾爾語中當單詞寬度大于文本行的剩余位置能夠容納的寬度時，單詞被拆分成兩個部分書寫[14]，并在行末用連接符“-”進行標注。當檢測到文本行的最后一個連體段為符號“-”時，說明此文本行末尾有單詞被拆分書寫。連接符“-”的寬度會隨著字體的變化而變化，但其高度一般與單詞的筆畫寬度相同。檢測連接符“-”的過程如下，首先將位于文本行末尾且寬度滿足表達式（16）的連體段篩選出來，寬度判別表達式如下所示：

其中，a為位于文本行末尾連體段的寬度，將篩選出的連體段圖像按兩倍高度和四倍寬度的比例放大，檢測放大后連體段的高度和寬度。圖像放大的目的是增大連接符“-”與其他連體段的輪廓大小的差值范圍，減小噪聲和圖像質量退化對檢測結果的影響。設放大后連體段的高度為h，寬度為l，若h和l滿足式（17）時：

則說明此文本行末尾有單詞被拆分，記錄此連體段右側被拆分單詞以及下一行第一個單詞的位置信息，表達式（16）與（17）為對不同字號的文本進行實驗時根據實驗數據得出的取值范圍。

根據記錄的被拆分部分單詞圖像合成完整單詞時，首先分別對兩部分圖像進行水平投影，分別找出每一行行像素累加值的最小值所在的行坐標。該行坐標即為單詞的基線所在行的坐標，合并被拆分的兩部分單詞圖像時按基線在同一條水平線的規則將被拆分圖像在垂直方向上對齊。當單詞拆分點位于單詞內兩相鄰連體段之間的空白處時，采用有間距合并的方式，即將基線對齊后的兩部分單詞圖像中相鄰連體段之間留出空白間距，間距值等于文本行中單詞內部間距的聚類中心B。若拆分點在連體段上，進行合并時將基線對齊后的兩部分單詞圖像上拆分點處相鄰的連體段緊密相連，單詞合并示意圖如圖7所示。

圖7 拆分單詞合并規則示意圖

為判斷拆分點位置，分別檢測拆分點兩側連體段的邊緣高度。設拆分點兩側連體段的邊緣高度分別為g1、g2,若g1與g2滿足判別式（18），則說明拆分點位于連體段上，應采用無間距合并，反之則說明拆分點位于單詞內連體段之間的間隙處，采用有間距合并。判別式（18）如下所示：在檢測邊緣高度時，檢測寬度設為兩個像素，并且去除了連體段上的附加符號比如“¨”“∴”等，來減小檢測誤差。高度判別閾值設為M-2是因為拆分點位于連體段上時，其邊緣高度即為單詞的基線高度，根據實驗基線高度總是小于M-2的。當拆分點位于單詞內連體段之間的間隙時，其邊緣高度一般遠大于M-2。

4.4 切分效果圖

這里只截取了一張完整文檔圖像的一部分，從圖中可以看出一些比較難切分的標點符號都被準確地切分了出來，滿足后續基于關鍵詞檢索系統對單詞切分的需要，切分效果圖如圖8所示。

5 實驗結果與分析

為了驗證本文所提出的方法針對印刷體維吾爾文檔圖像的單詞切分效果，從收集的文檔圖像數據庫中選取包含不同字號、行間距，以及清晰度的100張文檔圖像進行實驗。特殊標點符號如“<< >>”“（ ）”“[]”往往是單詞錯誤切分的主要來源，因此首先從已有的100張文檔圖像中選取5張特殊標點符號數目較多的文檔圖像進行切分實驗，實驗結果如表1所示。

從表1可知在選取的5張文檔圖像中“<< >>”“（）”“[]”三類標點符號共有80個，全部都切分正確，證明本文方法對此類與單詞間間隙較小的標點符號的切分有很好的效果，同時保持較高的單詞切分準確率。為驗證本文方法對合并被拆分單詞的有效性，從已有的100張文檔圖像中選取5張被拆分單詞數目較多的文檔圖像進行單詞切分實驗，實驗結果如表2所示。

表1 包含較多特殊標點符號的維吾爾文印刷體文檔圖像單詞切分實驗結果統計

表2 包含較多被拆分單詞的維吾爾文印刷體文檔圖像單詞切分實驗結果統計

從表2可知在選取的5張文檔圖像中共有57個單詞被以拆分的形式書寫，經過本文方法處理后有54個單詞被正確合并，合并準確率達到94.73%，證明本文方法對被拆分單詞的合并有很好的效果。為觀察本文方法對不同數量的印刷體維吾爾文文檔圖像進行單詞切分時錯誤切分率的變化范圍，隨機從已有的100張文檔圖像中分別選取數量分別為5、10、15、25、50張的文檔圖像進行單詞切分實驗，實驗結果如表3所示。

表3 隨機選取不同數量的維吾爾文印刷體文檔圖像單詞切分實驗結果統計

圖8 印刷體維吾爾文檔圖像單詞切分效果圖

表3通過隨機選取不同數量的文檔圖像進行實驗，降低了偶然性對統計切分結果時的影響。在本實驗中將標點符號看作獨立的切分單元，并且將被拆分書寫的單詞在切分時進行了合并。從表3可以看出，單詞切分的準確率依據文檔圖像及其數量的不同會有小范圍波動，但是切分準確率都在99%以上，證明本文方法對印刷體維吾爾文檔圖像單詞切分有很好的的效果。

為對比本文方法與已有方法的相比的差異性，從已有數據庫中隨機選取了10幅印刷體維吾爾文檔圖像，與直接投影法[15]以及形態學梯度算法[16]進行了對比實驗。由于對比文獻中的方法未考慮單詞拆分影響，因此在統計切分結果時忽略單詞拆分的影響，對比實驗結果如表4～6所示。

表4 固定閾值+直接使用水平和垂直投影算法的印刷體維吾爾文檔圖像單詞切分實驗結果

表5 使用形態學梯度算法的印刷體維吾爾文檔圖像單詞切分實驗結果

從表中數據可知，在選取的10幅印刷體維吾爾文圖像中共有2 257個單詞，基于全局閾值的直接投影法的平均切分錯誤率為5%，共切錯112個，基于形態學梯度算法平均切分錯誤率為2.6%，共切錯62個單詞，切分效果優于直接投影法，平均切分錯誤率降低了2.4個百分點。本文提出的間距聚類融合連體段判斷的方法平均錯誤率為0.9%，共切錯21個單詞，平均切分錯誤率比直接投影法降低了4.1個百分點，比形態學梯度算法降低了1.7個百分點。分析可知直接投影法只利用了單詞間的空白間距信息來確定切分點，并且使用全局閾值來對多幅圖像進行切分，對版面格式的適應性差，故切分錯誤率較高。形態學梯度算法通過膨脹和腐蝕[17]操作，使用膨脹后的單詞圖像減去腐蝕后的單詞圖像，從而得到整個單詞的邊緣輪廓信息。該方法能夠適應不同版面格式的變化，因此效果優于直接投影法，但兩種方法本質都只利用了連體段之間的空白間距信息，因此對一些無法根據間距信息切出的特殊符號無效。本文提出的基于間距聚類和連體段判斷的維吾爾文圖像單詞切分方法通過間距聚類，計算動態閾值來適應不同版面格式的變化，同時結合連體段的輪廓信息能夠去除無法用間距信息去除的特殊標點符號，因此切分準確率較高。但由于本文是在投影法的基礎上進行，對文檔圖像的質量較高，因此圖像預處理算法仍然需要改進。三種切分方法切分效果對比圖如圖9所示。

表6 間距聚類+連體段判別的印刷體維吾爾文檔圖像單詞切分實驗結果

圖9 三種方法錯誤切分單詞數目對比圖

6 結束語

為了后續開發基于關鍵詞的印刷體維吾爾文檔圖像檢索系統，首先需要對文檔圖像進行準確的切分。現有的切分方法中基于膨脹腐蝕的形態學操作方法與基于連體段聚類的投影切分方法都存在著標點符號漏切分，被拆分書寫單詞未合并等問題。本文通過投影法獲取文本行中連體段的位置、大小、基本形狀等信息，然后對連體段之間的間隙進行K-means聚類分析獲取自適應間隙判別閾值，結合二者信息來獲得單詞的精確切分點，同時合并被拆分書寫的單詞。投影法對文檔圖像的對比度、清晰度等要求較高，圖像質量差是影響本文切分效果的主要因素。不同的質量、文本格式的文檔數據庫會影響本文方法對單詞切分的準確率，因此如何提高本文對噪聲干擾嚴重、模糊以及不同文本格式的圖像的切分效果，進一步提高本文對不同質量與種類的文檔圖像的魯棒性，將是下一步的研究重點。