一種優(yōu)化的手寫字符自動分割算法

黃一琦，鄭佳春，曹長玉

(1.集美大學航海學院，福建 廈門 361021；2.集美大學信息工程學院，福建 廈門 361021)

0 引言

傳統(tǒng)的人工閱卷方式需要耗費大量的人力和時間，為了讓教師將更多的時間投入到重要的教學任務中，出現(xiàn)了機器自動閱卷。試卷自動評閱的實質是手寫體答案的自動識別。識別過程包括：試卷答案預處理、答案字符分割、答案識別等階段。其中，字符分割是最為關鍵的，它直接影響著字符識別的準確率和答案判定的可靠性。因此，手寫字符分割值得研究。

目前國內外對字符分割的研究已經(jīng)取得一些成果：文獻[1]提出將圖片上的字符分割開后，再結合傳統(tǒng)的機器學習相關算法，可以得到一個較好的識別效果；文獻[2]提出一種基于投影的豎直分割的方法，它解決了大部分情況下非粘連字符的分割，但在粘連字符的分割上效果不理想；文獻[3]提出一種利用中軸點作為字符分割點的方法，其中中軸點表示在背景中兩個分離的字符像素之間的背景中心像素點，該算法針對那些工整字符之間寬度一致的不粘連的字符具有良好的分割效果；文獻[4]提出一種基于局部極小值和最小投影值的字符分割方法，但它對交叉重疊和扭曲字符進行分割效果較差；文獻[5]根據(jù)平均寬度的相關倍數(shù)得到一個預設寬度來分割圖像，每個特征對應著不同的結果，然后找出最佳片段來作為最終結果；文獻[6]提出了一種滴水算法分割手寫數(shù)字字符,它解決了一些基本粘連字符的分割問題；文獻[7]采用上下輪廓差投影法大體確定字符間的坐標位置，然后再利用水滴算法進行字符切割；文獻[8]認為在驗證碼字符粘連處字符像素的密度較大，通過SOM聚類來找到這些像素密集的地方，但是這種假設依賴于字符筆畫的寬度與字符粘連的程度，并不適用于所有粘連的情況。

現(xiàn)有的分割方法在粘連手寫字符間寬度差較大、字符筆畫重疊粘連、字符不連貫且含有斷點等特殊情況的分割效果不夠理想。針對這些問題，本文在滴水算法研究基礎上，提出一種優(yōu)化的通用性分割方法。

1 傳統(tǒng)字符分割算法存在的問題

1.1 字符分割存在的普遍問題

對于字符分割問題，豎直投影分割是較早得到應用的方法，它對于不粘連的字符分割效果還是較理想的。由于手寫字符大多比較不工整，常出現(xiàn)書寫連筆或筆畫搭在另一個字符上的情況，導致字符粘連在一起，此時用豎直投影分割法會出現(xiàn)字符分割不完整、錯誤分割、筆畫斷裂等現(xiàn)象，進而導致識別率不理想。而滴水算法可以解決上面豎直投影分割法對于簡單粘連字符分割出現(xiàn)的問題。從樣本中取一張字符“48”(見圖1a)，兩種分割方法的路徑及結果如圖1所示。

從圖1可以看出，滴水算法分割粘連字符的效果明顯好于豎直投影分割效果。因為滴水算法的分割路徑是沿著右邊字符“8”的邊緣輪廓向下的，避免了豎直投影分割中出現(xiàn)的破壞字符完整性的情形。

關于一些特殊的粘連形式，傳統(tǒng)分割方法的效果一般。在豎直投影時，由于上下交錯導致投影得到的像素值大于0從而誤判為粘連情況，但實際上兩個字符之間沒有真正粘連在一起，這種情況一般被稱為投影粘連[9]，如圖2所示。使用豎直投影分割的話會導致字符分割斷裂，而傳統(tǒng)滴水算法分割在此情況下的效果比前者更差。

1.2 特殊情況字符的分割問題

在圖3a所示的“12”這個字符中可以看到，左邊“1”和右邊“2”的寬度值差距較大并局部粘連在一起。此情況下利用傳統(tǒng)滴水算法分割，可能會將其識別為一個字符；也有可能因為起始點位置選取的不準確，導致字符從右邊“2”開始分割，造成字符錯誤分割的現(xiàn)象，其效果如圖3所示。

在圖4所示的“20”這個字符中可以看到，左邊“2”和右邊“0”局部粘連在一起，且字符“0”上出現(xiàn)兩個的斷點。這種筆畫不連續(xù)且含斷點的粘連字符，使用之前的分割方法導致將其錯誤分割為3個字符，其效果如圖4所示。針對此類情況，需要加一些字符寬度以及高度閾值條件進行判斷從而合并字符，即當小的連通區(qū)域的寬度范圍包含在大的連通區(qū)域范圍之內，則將小的連通區(qū)域與大的連通區(qū)域合并。

2 字符分割算法的優(yōu)化

2.1 滴水算法

滴水算法(drop fall algorithm)基本思想是模擬水滴從高處向低處滴落的過程來對粘連字符進行分割。在重力作用下，水滴從字符串之間的頂部向下滴落，當水滴遇到字符時只能沿字符輪廓向下滴落或者水平左右滾動。當水滴陷在輪廓的凹陷處時，則進行滲透處理，即從輪廓最低點滲漏到字符筆畫中，然后穿透筆畫繼續(xù)滴落，最終水滴所經(jīng)過的軌跡就是分割路徑[7]。這種方法可以解決豎直投影分割字符所帶來的字符斷裂、過分割等問題。滴水算法的影響因素主要有：起始滴落點、移動規(guī)則和方向不同。水滴的周圍狀況如圖5所示。其中，d0表示水滴當前的位置，水滴的下一滴落位置由d1、d2、d3、d4、d5這5個周圍像素點的情況決定。

2.2 CFS分割

CFS算法是由Yan等[11]提出，通過使用顏色填充字符塊的方式，將字符標記成顏色不同的區(qū)塊，這樣就可以將沒有粘連的字符分割出來，因此稱之為CFS(color filling segmentation)分割法。其主要工作原理是：將字符圖片從左到右，從上到下進行掃描，當掃描到第一個黑色像素點時，以它為中心在其相鄰的八個方向繼續(xù)探測，若存在新黑像素點，就認為這是一個字符區(qū)塊。然后以這個新像素點為新的中心點繼續(xù)進行上述步驟，直到不再探測到新黑像素點時就認為這一字符區(qū)塊結束，并用顏色填充探測到的字符區(qū)塊[12]。接著在區(qū)塊外新的像素點繼續(xù)重復以上流程，直到所有字符區(qū)塊都被檢測出來，這樣就會得到若干字符區(qū)塊，然后根據(jù)填充顏色的不同進行分割，圖6為示例圖。傳統(tǒng)的連通域分割是利用像素點之間的連通性，把不同連通域的字符塊分割開來。只要字符之間不粘連，即使字符存在傾斜扭曲，其分割效果都不受影響。

2.3 起始點的設計

通常傳統(tǒng)滴水算法的起始滴落點是以從上到下從左到右掃描手寫體圖片中每一行像素點，然后使第一個滿足像素分布為(…0*1…10…)的白像素點(*)作為起始滴落點，其中0,1分別代表黑色、白色像素點[13]?？梢钥闯鰝鹘y(tǒng)滴落起始點的選擇具有一般性，對于特殊情況，這種選擇方法得到的分割效果不太理想。按照傳統(tǒng)滴水算法規(guī)則，在遇到字符筆畫凹陷時，很大可能就以此為起始點，進而造成手寫體字符分割斷裂。并且水滴在字符上移動時還會由于字符輪廓的不平滑，而出現(xiàn)錯誤分割現(xiàn)象。綜上可知，起始滴落點的選擇對于滴水算法分割的效果是至關重要的。

圖7 最佳起始滴落點的選擇流程Fig.7 Best starting drip point selection process

一般來說，字符的粘連點會出現(xiàn)在豎直投影直方圖中的極小值處。因此，本文結合兩種方法來確定最佳起始滴落點，即利用豎直投影法輔助局部掃描分析起始滴落點，這樣便能在粘連字符中選擇較準確的起始點，起始點重新設計的流程如圖7所示。

本研究的局部掃描模塊是指根據(jù)分割字符的寬度W，取粘連字符0.2W與0.8W之間為掃描區(qū)域I。選取這個區(qū)域是為了消去粘連字符兩端的開始、結尾筆畫的影響，即把起始點選擇區(qū)域集中在粘連字符居中的位置。對區(qū)域I按水平方向從左到右、從上到下依次掃描像素點，選出最初滿足像素分布為(…0*1…10…)的一行。先將所有滿足條件的白像素點(*)位置坐標存入列表number中，接著將豎直投影法中存在的極小值點的位置坐標按大小存入列表number中，最后參照字符中間位置坐標，選取列表number中最右邊的白像素點start_xn作為最優(yōu)滴落起始點。

本研究根據(jù)得到的最優(yōu)滴落起始點進行滴水算法分割粘連字符，具有良好的分割效果。圖8為起始滴落點的正確與錯誤選擇的對比示意圖，不同起始滴落點的分割效果有明顯的差異。

2.4 通用性優(yōu)化設計

根據(jù)2.1分析可知：手寫字符出現(xiàn)粘連時，不能使用豎直投影算法分割；字符之間緊密粘連且字符有斷裂部分，不能直接使用連通域算法分割；有些粘連字符之間寬度差較大，起始滴落點選擇不理想，不能直接使用滴水算法分割。本文結合以上三種分割算法，設計出一種通用性更強的方法，分割出單個字符，并且對樣本字符的寬度、高度和像素點數(shù)進行統(tǒng)計，在分割時用來作為判斷字符塊中包含的字符個數(shù)的依據(jù)。流程圖見圖9。

圖9 通用性字符分割方法流程

本文通用性分割方法設計主要有以下三個模塊：

1)手寫字符輸入模塊。該模塊首先通過CFS分割，它主要有兩個作用：一是當字符為非粘連字符時，直接進行字符分割；二是當字符為非粘連字符時，它可以用來判斷字符區(qū)塊是否含有粘連字符的情況，若存在則進入下一步分析。所以，該方法通用于字符不粘連和字符粘連的情況。

2)滴落起始點選擇模塊。該模塊會對粘連字符進行局部掃描，并將符合條件的像素點與豎直投影得到的極小值像素點進行分析，以便確定最佳的起始滴落點。

3)字符分割與優(yōu)化模塊。該模塊根據(jù)最佳起始滴落點來進行滴水算法分割粘連字符，將字符分割之后的結果送入閾值判斷中，經(jīng)再次判斷以避免字符的分割遺漏。相當于自適應的優(yōu)化分割，從而對分割結果進行最后的確認。

本分割方法根據(jù)粘連情況將三種分割方法依次使用，并不是一次性分割出所有粘連字符，而是根據(jù)粘連程度逐步進行字符分割。

3 實驗與分析

3.1 實驗環(huán)境及數(shù)據(jù)

本文實驗在Ubuntu18.04系統(tǒng)進行，在PyCharm開發(fā)環(huán)境下使用Python3.6編寫，測試代碼。實驗主要使用30張小學數(shù)學試卷答案，取其中字符不粘連、字符輕微粘連、字符特殊粘連各500個，總計1500個字符。手寫體答案在字體大小、書寫格式、清晰度上等有所不同。本研究還采用500個手寫英文字符和網(wǎng)絡驗證碼字符樣本作為實驗驗證集，驗證其通用性效果。

3.2 實驗結果

針對傳統(tǒng)分割方法出現(xiàn)的分割錯誤情況，本研究改進的分割方法與傳統(tǒng)分割方法的效果對比如圖10所示。改進算法對30張試卷答案手寫字符實驗樣本進行分割測試，實驗部分分割效果如圖11～12所示。

字符分割準確率計算公式為：字符分割正確率(%)=正確分割字符個數(shù)/字符總個數(shù)×100%。實驗結果如表1所示。對于1500個樣本數(shù)據(jù)集，改進算法的準確率達到92.4%，傳統(tǒng)滴水算法為80.8%，CFS和豎直投影算法都為33%。相對于傳統(tǒng)滴水算法，改進算法準確率提升了11.6%。

表1 字符分割結果對比

本文對驗證集樣本進行字符分割測試，驗證集中粘連字的分割效果如圖13所示。從圖13中看出改進算法的分割效果是比較理想的，說明改進算法在粘連字符分割上具有良好的通用性。

4 結束語

在實驗樣本中，很多手寫字符是粘連在一起的，尤其是投影粘連這種情況。豎直投影分割法對無粘連字符但存在傾斜的字符，以及粘連字符的分割大多會造成字符分割斷裂，即把完整的字符分割為兩個部分，所以針對這種情況采用豎直投影分割法對手寫體測試樣本的分割成功率是最低的。CFS分割對不粘連字符的分割效果理想，而對粘連嚴重的字符無法分割。傳統(tǒng)滴水算法對于字符傾斜且沒有明顯粘連時分割效果理想；但在字符粘連扭曲復雜、寬度相差較大的兩個字符粘連，以及字符中筆畫不連續(xù)含斷點等粘連情況下，它的分割效果不理想。從實驗結果來看，本文提出對傳統(tǒng)分割方法加以組合使用，找出滴水算法的最佳起始滴落點，按照新的起始滴落點的滴落軌跡分割粘連字符。該方法能夠正確有效地分割粘連手寫字符間寬度差較大、字符筆畫重疊粘連、字符不連貫且含有斷點等特殊情況，但在出現(xiàn)粘連嚴重、筆畫重疊交叉嚴重的情況時，就會出現(xiàn)錯誤分割現(xiàn)象，導致分割準確率下降。整體來說，改進算法的分割準確率相較于傳統(tǒng)分割算法提高了11.6%，針對字符粘連和字符不粘連的情況都能有較理想的分割效果。

接下來的探索方向是利用SOM聚類結合字符骨架化分析來繼續(xù)提高字符分割的準確率，以及通過卷積神經(jīng)網(wǎng)絡識別字符。