黃一琦，鄭佳春，曹長(zhǎng)玉

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

0 引言

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

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

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

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

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

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

從圖1可以看出，滴水算法分割粘連字符的效果明顯好于豎直投影分割效果。因?yàn)榈嗡惴ǖ姆指盥窂绞茄刂疫呑址?”的邊緣輪廓向下的，避免了豎直投影分割中出現(xiàn)的破壞字符完整性的情形。

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

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

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

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

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

2.1 滴水算法

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

2.2 CFS分割

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

2.3 起始點(diǎn)的設(shè)計(jì)

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

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

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

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

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

2.4 通用性優(yōu)化設(shè)計(jì)

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

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

本文通用性分割方法設(shè)計(jì)主要有以下三個(gè)模塊：

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

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

針對(duì)傳統(tǒng)分割方法出現(xiàn)的分割錯(cuò)誤情況，本研究改進(jìn)的分割方法與傳統(tǒng)分割方法的效果對(duì)比如圖10所示。改進(jìn)算法對(duì)30張?jiān)嚲泶鸢甘謱懽址麑?shí)驗(yàn)樣本進(jìn)行分割測(cè)試，實(shí)驗(yàn)部分分割效果如圖11～12所示。

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

表1 字符分割結(jié)果對(duì)比

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

4 結(jié)束語

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

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