自適應(yīng)字符切分及提取算法研究

金海燕, 夏 婷, 王 彬

(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048)

?

自適應(yīng)字符切分及提取算法研究

金海燕, 夏 婷, 王 彬

(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048)

在字符識(shí)別技術(shù)日趨成熟的現(xiàn)狀下，單個(gè)字符的正確切分及提取已經(jīng)成為制約字符識(shí)別精確度的關(guān)鍵因素。本文針對(duì)二手車發(fā)票上印刷體的日期數(shù)字(阿拉伯?dāng)?shù)字)，對(duì)圖像二值化處理后，采用垂直方向投影和輪廓特征兩種策略進(jìn)行自適應(yīng)字符切分及提取。實(shí)驗(yàn)結(jié)果表明，該方法提高了從圖像中定位出來(lái)的字符串的切分率，并保證了字符切分和提取的正確率平均達(dá)到99%。

字符切分及提取； 字符識(shí)別； 圖像二值化

單一字符識(shí)別技術(shù)發(fā)展迅速，目前，多數(shù)字符識(shí)別系統(tǒng)對(duì)于印刷字符數(shù)字的識(shí)別已經(jīng)達(dá)到較高識(shí)別率，此時(shí)字符的正確切分就成為進(jìn)一步提高識(shí)別率的關(guān)鍵因素。

目前，一些學(xué)者已經(jīng)提出了一些字符切分方法。投影法[1]主要是對(duì)字符圖像二值化后向水平方向投影，投影曲線兩個(gè)相鄰波谷的位置就是切割線的位置，該方法簡(jiǎn)單、快速，但是對(duì)噪聲等干擾因素敏感。上下輪廓(Upper/Lower Contour)特征法[2]通過(guò)逐列搜索掃描來(lái)確定字符的上下輪廓曲線，并根據(jù)其輪廓曲線來(lái)近似確定單個(gè)字符。該方法對(duì)字符寬度、間隔不固定的圖像切分效果不好。滴水算法(Drop-Falling)[3]根據(jù)水滴運(yùn)動(dòng)所經(jīng)過(guò)的路徑軌跡來(lái)確定字符的分割路徑，該方法對(duì)粘連字符有很好的切割效果，但對(duì)于有傾斜或本身是凹形結(jié)構(gòu)的字符會(huì)造成字符斷裂，對(duì)某些左中右結(jié)構(gòu)的漢字會(huì)造成過(guò)度切分。連通域法[4]是基于字符本身的像素連續(xù)性，每一個(gè)字符或者字符的一部分構(gòu)成一個(gè)連通域,該方法抗噪性較好，但是對(duì)一些由互不相連的幾部分組成的漢字，會(huì)將其分割成幾部分，從而導(dǎo)致切分不正確。

綜上所述，字符切分中的最小單元是單個(gè)字符，描述字符單元最精確的知識(shí)就是字符形狀[5]。字符切分過(guò)程就是對(duì)單個(gè)字符的外輪廓邊界準(zhǔn)確定位的過(guò)程，根據(jù)字符的外輪廓確定字符的外邊界，進(jìn)而確定切割的位置。而單個(gè)字符數(shù)字內(nèi)部的間斷、字符間的粘連以及圖像背景噪聲不同程度的污染等，都是造成不能精確切分的主要因素及難點(diǎn)[6]。本文就二手車發(fā)票日期字符的識(shí)別提出自適應(yīng)字符切分及提取算法。該算法采用兩種策略多次自適應(yīng)切分及提取，首先采用上下輪廓追蹤法切分，如果切分結(jié)果不理想，再進(jìn)行垂直投影法切分。切分過(guò)程中可以根據(jù)字符的寬高來(lái)判斷切分結(jié)果是否正確，最后根據(jù)日期的有效位數(shù)去除年、月、日后，提取8位數(shù)字圖片。

1 自適應(yīng)字符切分及提取算法

1.1 字符的切分及提取算法

本文算法主要采用直線檢測(cè)法定位出日期位置，因此對(duì)日期位置沒(méi)有明確要求。假設(shè)日期位置位于發(fā)票的左上方，首先定位日期位置，切取發(fā)票的日期數(shù)字部分，再對(duì)該部分進(jìn)行初步的預(yù)處理[7-9]。本文提出的字符切分及提取方法分為兩步。

1.1.1 上下輪廓追蹤

首先，用簡(jiǎn)單統(tǒng)計(jì)法[10]將灰度位圖二值化，并對(duì)二值位圖進(jìn)行邊緣噪聲清理和消除孤立點(diǎn)，然后，追蹤搜索上下輪廓特征，分析空白間隔，切除不需要的部分，對(duì)保留下來(lái)的部分搜索極值點(diǎn)，進(jìn)而于特征點(diǎn)處切分。

預(yù)處理原始圖像，裁剪出左上角位圖，從而大大減少后續(xù)操作數(shù)據(jù)量，并按固定比例進(jìn)行縮放，記錄此時(shí)高度h0、寬度w0。

用最大類間方差(OTSU)[11]算法二值化該灰度圖，利用霍夫變換檢測(cè)表格線和傾斜角度，定位出表格左上角及角度的矯正。以位圖左上角為坐標(biāo)原點(diǎn)，將二值圖像像素值為0的直角坐標(biāo)系下的坐標(biāo)點(diǎn)(x,y)轉(zhuǎn)換為極角坐標(biāo)下的坐標(biāo)點(diǎn)(r,θ)，并將累加個(gè)數(shù)存儲(chǔ)于hough矩陣數(shù)組中，如公式(1)所示。

r=x×cosθ+y×sinθ

(1)

從r=h0-a處開(kāi)始降序搜索hough矩陣中同一(r,θ)的數(shù)量值，當(dāng)首次出現(xiàn)大于預(yù)設(shè)的門(mén)限值b時(shí)設(shè)：

up_dis=r;

angle=θ;

式中，up_dis為表格最上邊直線距原點(diǎn)的距離，angle為表格傾斜角度，a、b為常量。

同理，從r=a處升序搜索hough矩陣中同一(r,θ)的數(shù)量值，當(dāng)首次出現(xiàn)大于預(yù)設(shè)的門(mén)限值c時(shí)設(shè)：

left_dis=r；

式中，left_dis為表格最左邊直線距原點(diǎn)的距離，c為常量。

若θ≠0，判斷表格傾斜角度angle及表格左上角坐標(biāo)(x0,y0)，編寫(xiě)如下程序：

x0=left_dis;

if(angle>90°)

angle=180°-angle;

y0=h0×cos(angle×3.14÷180)-up_dis;

else

y0=h0×cos(angle×3.14÷180)-up_dis+

w0×sin(angle×3.14÷180);

angle=-angle;

采用鄰近插值算法[12]以angle角度對(duì)位圖進(jìn)行傾斜矯正。

以(x0,y0)為矩形左下角，按固定比例從原灰度圖中裁剪出目標(biāo)所在區(qū)域部分，此時(shí)位圖矩陣記為image0。

采用簡(jiǎn)單統(tǒng)計(jì)法二值化image0，搜索8鄰域連通域消除孤立噪聲點(diǎn)，并進(jìn)行邊緣清理，記錄此時(shí)二值位圖為I1。

在I1中定位字符的上下輪廓特征，可采用先自上而下再自下而上沿縱軸方向掃描像素點(diǎn)的方法，用一維數(shù)組U(1,I1_x)、D(1,I1_x)分別記錄上下輪廓的縱坐標(biāo)點(diǎn)，得到上下輪廓之間距離的離散值span(1,I1_x)，如公式(2)所示。

(2)

式中，I1_x為I1的寬，i初始化為0，上限為I1_x-1，移動(dòng)步長(zhǎng)為1。

分析span(1,i)空白間隔處，并自適應(yīng)選取縮小目標(biāo)區(qū)域的切割點(diǎn)(x1,y1)，基于image0圖裁剪出日期矩陣image1。

依據(jù)先遞減后遞增的規(guī)律從左向右逐一查找span(1,i)中的極值點(diǎn)，設(shè)小于d(注：d為常量經(jīng)驗(yàn)值)的極值點(diǎn)對(duì)應(yīng)的坐標(biāo)點(diǎn)為切分點(diǎn)，基于image1灰度位圖裁剪，最終切分成字符碎片，用最大類間方差算法生成二值化效果圖。

對(duì)字符碎片做輪廓臨界點(diǎn)裁剪，二次切分自適應(yīng)提取有效字符片位圖。首先，統(tǒng)計(jì)字符碎片高度、寬度，排序查找出現(xiàn)次數(shù)最多的高度、寬度分別記為h、w；其次，鑒于此時(shí)二值化位圖細(xì)節(jié)清晰，只需取上輪廓特征極值點(diǎn)，參考h、w及非有效字符的提取情況，自適應(yīng)的進(jìn)行二次切分，直至取到所有有效字符片存于數(shù)組矩陣digital_matrix中。

飛機(jī)起落架緩沖系統(tǒng)廣泛采用油氣式緩沖器[2]，主要由外筒、活塞桿、柱塞、油針和密封件等組成。當(dāng)起落架受到撞擊壓縮時(shí)，氣體的作用相當(dāng)于彈簧，吸收能量；油液通過(guò)限流孔使緩沖支柱阻力增大，并摩擦生熱消耗能量，使得作用到機(jī)體上的載荷減小，同時(shí)飛機(jī)撞擊后很快平穩(wěn)下來(lái)。

1.1.2 垂直投影

對(duì)經(jīng)過(guò)1.1.1中切分處理后仍然切分錯(cuò)誤的字符圖像，采用垂直投影[13]進(jìn)一步分析。對(duì)1.1.1中定位裁剪出的日期灰度圖image0，采用最大類間方差算法二值化記為I0，再以8領(lǐng)域連通域搜索消除孤立噪聲點(diǎn),并進(jìn)行邊緣清理。

將I0進(jìn)行垂直投影，投影累加值記錄在一維矩陣S(1,I0_x)中，如公式(3)所示。

(3)

式中，I0_x為I0的寬，I0_y為I0的高，I0(i,j)為坐標(biāo)(i,j)點(diǎn)的像素值(注：0為黑色像素點(diǎn)，1為白色像素點(diǎn))，S(1,i)為在橫坐標(biāo)為i下所有像素為0的點(diǎn)的個(gè)數(shù)。

基于空白間隔處進(jìn)行字符切分，得到字符碎片piece_matrix[sum](注：sum為碎片總數(shù))。對(duì)字符碎片做輪廓臨界點(diǎn)裁剪，二次切分自適應(yīng)提取有效字符片位圖。

1.2 算法流程圖

首先，將讀入的圖像進(jìn)行傾斜矯正；然后，從中定位出表格左上角的坐標(biāo)，從而定位出日期；最后，結(jié)合兩種策略對(duì)日期進(jìn)行單個(gè)字符的切分及提取。算法流程圖如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

2 實(shí)驗(yàn)分析

以?shī)W迪4S店實(shí)際的二手車售車發(fā)票為實(shí)驗(yàn)樣本進(jìn)行分析。圖2為發(fā)票源圖的灰度圖。

圖2 發(fā)票源圖的灰度圖Fig.2 The original invoice grayscale

步驟1：選取經(jīng)過(guò)加權(quán)平均法灰度化的灰度圖圖2作為源圖。初步裁剪出左上角位圖，并按固定比例進(jìn)行縮放,記錄此時(shí)高度h0=290(像素)、寬度w0=600(像素)，左上角位圖如圖3所示。

圖3 發(fā)票左上角圖Fig.3 The image of invoice upper left corner

步驟2：采用最大類間方差算法對(duì)圖3進(jìn)行二值化，利用霍夫變換檢測(cè)表格線和傾斜角度，定位出表格左上角及角度的矯正。以左上角為坐標(biāo)原點(diǎn)，檢測(cè)到表格左上角坐標(biāo)為(99,93)、角度為0°。

步驟3：位圖無(wú)傾斜，不需要矯正。

步驟4：以(99,93)為矩形左下角，按固定比例從原灰度圖中裁剪出目標(biāo)所在區(qū)域部分，記為image0，如圖4所示。

圖4 定位開(kāi)票日期頭位圖
Fig.4 The billing date bitmap head positioning

步驟5：采用簡(jiǎn)單統(tǒng)計(jì)法二值化image0，搜索8鄰域連通域消除孤立噪聲點(diǎn)，并進(jìn)行邊緣清理，記錄此時(shí)二值位圖為I1。

步驟6：在I1中用掃描像素的方法定位字符的上下輪廓特征，得到上下輪廓之間距離的離散值span(1,I1_x)，U(1,I1_x)、D(1,I1_x)分別記錄上下輪廓的縱坐標(biāo)點(diǎn)。自左向右分析span(1,i)空白間隔處，縮小目標(biāo)所在區(qū)域范圍,切除“開(kāi)票日期：”部分后的左下角坐標(biāo)為(80,0)，基于灰度位圖image0再次切割，記為image1，如圖5所示。

圖5 定位日期位圖Fig.5 Location date bitmap

步驟7：依據(jù)先遞減后遞增的規(guī)律從左向右逐一查找span(1,i)中的極值點(diǎn)(注：i從80開(kāi)始)，設(shè)小于d(d=7)的極值點(diǎn)對(duì)應(yīng)的坐標(biāo)點(diǎn)為切分點(diǎn)，其橫坐標(biāo)為：29、39、47、57、64、74、83、94、110?；诨叶任粓Dimage1裁剪，最終切分成字符碎片，并采用OTSU算法二值化。

步驟8：對(duì)字符碎片做輪廓臨界點(diǎn)裁剪如圖6所示，放大字符碎片效果如圖7所示。二次切分自適應(yīng)提取有效字符片位圖。首先，統(tǒng)計(jì)字符碎片高度、寬度，排序查找出現(xiàn)次數(shù)最多的高度、寬度分別記為h=13、w=8，其次，鑒于此時(shí)二值化位圖細(xì)節(jié)清晰，只需取上輪廓特征極值點(diǎn)，參考均值h、w以及非有效字符的情況，自適應(yīng)的進(jìn)行二次切分，從中提取8個(gè)數(shù)字片矩陣，分別考慮年、月、日、數(shù)的情況。依據(jù)均寬w、均高h(yuǎn)，分別對(duì)日期數(shù)、“日、月、年”的寬度、高度做一個(gè)大概定位，不在這個(gè)范圍內(nèi)的，自適應(yīng)的進(jìn)行二次切分或者向前選取新的矩陣進(jìn)行提取，最終只提取到8個(gè)數(shù)值矩陣存儲(chǔ)于digital_matrix矩陣數(shù)組中。提取出的8個(gè)數(shù)字片如圖8所示。

圖6 字符碎片位圖Fig.6 Character fragment bitmap

圖8 單個(gè)數(shù)字片位圖Fig.8 Single digital bitmap

圖7 字符碎片放大位圖
Fig.7 Character fragmentation bitmap

以上實(shí)驗(yàn)中提取的有效字符數(shù)量及切分結(jié)果說(shuō)明字符切分正確，無(wú)需再進(jìn)行垂直投影處理，而對(duì)有些發(fā)票，當(dāng)采用上下輪廓追蹤處理后有效字符數(shù)不為8或出現(xiàn)無(wú)法識(shí)別的字符時(shí)，需要采用垂直投影重新切分處理，以達(dá)到切分的最佳效果。運(yùn)用本文算法對(duì)100張不同時(shí)間日期的二手車發(fā)票進(jìn)行了日期字符的切分及提取，實(shí)現(xiàn)了對(duì)日期字符的精確定位、切分和提取，并且字符的邊界劃分較為清晰準(zhǔn)確，取得了比較滿意的結(jié)果，提取出的待識(shí)別數(shù)字正確率平均達(dá)到99%。

3 結(jié) 語(yǔ)

自適應(yīng)字符切分及提取方法，是將讀入的圖像進(jìn)行傾斜矯正，從中定位出發(fā)票表格左上角的坐標(biāo)(x0,y0)，并以此設(shè)置矩形框裁剪出圖像，最后進(jìn)行單個(gè)字符的切分及提取。本文結(jié)合多種二值化圖像的效果，采用垂直方向投影和輪廓特征兩種策略進(jìn)行自適應(yīng)字符切分及提取，提高了從圖像中定位出來(lái)的字符串的切分率，并保證了提取出的待識(shí)別數(shù)字的正確切分率。

[1]遲小君,孟慶春.基于投影特征值的車牌字符分割算法[J].計(jì)算機(jī)應(yīng)用研究,2006,32(7):256-257.

CHI Xiaojun,MENG Qingchun.Character segmentation of license plate based on projection and eigenvalue[J].Application Research of Computers,2006,32(7):256-257.

[2]STRATHY N W, SUEN C Y, KRZYZAK A.Segmentation of handwritten digits using contour features[C]//Document Analysis and Recognition,1993，Proceedings of the Second International Conference on, Tsukuba，1993：577-580.

[3]KHAN S A. Character segmentation heuristics for check amount verification[D].Cambridge：Massachusetts Institute of Technology, 1998.

[4]陳艷,孫羽菲,張玉志.基于連通域的漢字切分技術(shù)研究[J].計(jì)算機(jī)應(yīng)用研究,2005,22(6):246-248.

CHEN Yan, SUN Yufei, ZHANG Yuzhi. Research on Chinese character segmentation based on connected domain[J].Computer Application Research,2005,22(6):246-248.

[5]劉剛,丁曉青,彭良瑞,等.多知識(shí)綜合判決的字符切分算法[J].計(jì)算機(jī)工程與應(yīng)用,2002,38(17):59-62.

LIU Gang,DING Xiaoqing,PENG Liangrui,et al.A character segmentation algorithm based on synthetic decision[J].Computer Engineering and Applications,2002,38(17):59-62.

[6]王葉.車牌識(shí)別系統(tǒng)中字符切分和識(shí)別技術(shù)的研究[D].北京：北京郵電大學(xué),2009.

WANG Ye.Study of character recognition in vehicle license plate system[D].Beijing:Beijing University of Posts and Telecommunications,2009.

[7]童立靖,張艷,舒巍,等.幾種文本圖像二值化方法的對(duì)比分析[J].北方大學(xué)學(xué)報(bào),2011,23(1):25-33.

TONG Lijing, ZHANG Yan, SHU Wei, et al. Comparison and analysis of several document image binarization algorithm[J].Journal of North College,2011,23(1):25-33.

[8]李釗,李鴻.幾種去噪方法的比較與改進(jìn)[J].工業(yè)控制計(jì)算機(jī),2012,25(8):9-10.

LI Zhao, LI Hong. Comparison and several de-noising methods[J].Industrial Control Computer,2012,25(8):9-10.

[9]張雅蘭.掃描圖象二值化處理的研究[J].廣西光學(xué)院學(xué)報(bào),2002,13(3):26-28.

ZHANG Yalan. A study of binarization processing of scanning image[J].Journal of Guangxi Institute of Light,2002,13(3):26-28.

[10]陳杰,王振華，竇麗華.一種尺度自適應(yīng)Canny邊緣檢測(cè)方法[J].光電工程,2008,35(2):79-84.

CHEN Jie,WANG Zhenhua,Dou Lihua.Scale adaptive canny edge detection method[J].Opto-Electronic Engineering,2008,35(2):79-84.

[11]OHTSU N.A threshold selection method from gray-Level histograms[J]. Systems Man & Cybernetics IEEE Transactions on, 1979, 9(1):62-66.

[12]于亞龍,穆遠(yuǎn)彪. 插值算法的研究[J].現(xiàn)代計(jì)算機(jī),2014,007(05):32-35.

YU Yalong, MU Yuanbiao.Research on interpolation algorithms[J].Modern Computer ,2014,007(05): 32-35.

[13]毛永明,祁寧,張東偉,等. 智能交通系統(tǒng)車牌字符分割研究[C]//第十二屆沈陽(yáng)科學(xué)學(xué)術(shù)年會(huì)，第十二屆沈陽(yáng)科學(xué)學(xué)術(shù)年會(huì)論文集,沈陽(yáng),2015.

MAO Yongming,QI Ning,ZHANG Dongwei,et al.Intelligent transportation system character segmentation study [C]//The Twelfth Annual Conference of Science and Technology in Shenyang,Shenyang Science Twelfth Annual Conference Proceedings,Shenyang, 2015.

(責(zé)任編輯 周 蓓)

Study of adaptive character segmentation and extraction algorithm

JIN Haiyan, XIA Ting, WANG Bin

(School of Computer Science and Engineering, Xi’ an University of Technology, Xi’ an 710048, China)

In the current the situation of character recognition technology is becoming more and more mature, and the correct segmentation and extraction of single character has become a key factor to control the accuracy of character recognition. This paper focuses on second-hand car invoice printing of digital date (Arabic numerals), with both vertical projection and contour feature combination strategies for adaptive character segmentation and extraction being conducted after image binarization processing. Experimental results show that using the proposed method can improve the segmentation rate of the string from the image, ensuring that the average accuracy rate of the extracted image can reach 99%.

character segmentation and extraction； character recognition； image binarization

10.19322/j.cnki.issn.1006-4710.2016.04.004

2016-03-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61472204, 61272283)

金海燕，女，教授，博士，研究方向?yàn)閳D像處理，模式識(shí)別，智能信息處理。E-mail:jinhaiyan@xaut.edu.cn

TP391

A

1006-4710(2016)04-0399-04