基于文本行基線的傾斜角檢測(cè)算法

巨志勇，何曉蕾，王超男

(上海理工大學(xué) 上海現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

?

基于文本行基線的傾斜角檢測(cè)算法

巨志勇，何曉蕾，王超男

(上海理工大學(xué) 上?，F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

針對(duì)文本圖像傾斜檢測(cè)問(wèn)題，提出了一種新的基于文本行基線的傾斜角檢測(cè)算法。該算法用邊界標(biāo)記自動(dòng)機(jī)對(duì)一組同行的字符進(jìn)行輪廓(外邊界)跟蹤，并標(biāo)記出字符的最小外接矩形(MER)和字符的邊框。在此基礎(chǔ)上通過(guò)相鄰字符間的行高差和字符區(qū)域的面積來(lái)剔除字符的冗余部分，最后用剩余部分的字符邊框底邊中點(diǎn)來(lái)擬合一條直線，即行文本的基線，并確定文本的傾斜角度。實(shí)驗(yàn)結(jié)果表明，該方法有效，同時(shí)傾斜角檢測(cè)的精確性得到了優(yōu)化。

文本圖像；傾斜檢測(cè)；邊界標(biāo)定；直線擬合

JU Zhiyong, HE Xiaolei, WANG Chaonan

(Shanghai Key Laboratory of Modern Optical System, University of Shanghai for Science & Technology,Shanghai 200093, China)

文本圖像的傾斜是文本數(shù)字化工程中不可避免的問(wèn)題，掃描時(shí)即使再仔細(xì)地?cái)[放也會(huì)存在小角度的傾斜[1]。因此，在光學(xué)字符識(shí)別(OCR)系統(tǒng)中，文本圖像的傾斜角檢測(cè)與矯正是字符預(yù)處理中的重要一步。現(xiàn)在多數(shù)的光學(xué)字符識(shí)別(OCR)系統(tǒng)都采用串行分立字符識(shí)別框架，通用模型如圖1所示[2]。

圖1 OCR系統(tǒng)的通用模型

目前存在的傾斜角檢測(cè)算法主要有以下幾類：一是基于投影[3]的方法，這種方法只適用于純文本圖像。隨著圖像變大以及版面復(fù)雜度的增加，出錯(cuò)幾率和計(jì)算量會(huì)大幅增加；二是基于Hough變換[4]的方法，Hough變換精度較高，但時(shí)間開銷和存儲(chǔ)開銷都比較大；三是基于最近鄰簇法[5]，耗時(shí)較多，而且精度有待提高；四是基于Fourier變換的方法，F(xiàn)ourier變換的運(yùn)算量較大，所以在實(shí)際中較少使用。雖然后續(xù)有這些算法的眾多改進(jìn)，但均存在或多或少的限制條件，影響算法效果。

本文提出了一種基于文本行基線的傾斜角檢測(cè)算法。利用字符本身的結(jié)構(gòu)特點(diǎn)，選取文本圖像中的一部分，有效剔除了排版和要求純文本圖像的限制條件。本文算法的核心是以字符邊框底邊的中點(diǎn)為特征點(diǎn)，通過(guò)字符的行高和聯(lián)通區(qū)域面積來(lái)剔除文本的冗余，根據(jù)剩余字符的特征點(diǎn)來(lái)擬合行文本的基線，最后確定文本的傾斜角度。

1 最小外接矩形的確定

圖像的外接矩形是圖像的一個(gè)幾何特征[6-9]。在圖像處理與分析的過(guò)程中，幾何特征具有重要的意義。本文使用最小外接矩形[10]。將圖像定義在二維坐標(biāo)X軸與Y軸上，因此文本圖像的每一個(gè)像素點(diǎn)在坐標(biāo)軸上都有對(duì)應(yīng)的坐標(biāo)[11]。利用邊界標(biāo)定自動(dòng)機(jī)對(duì)字符的輪廓進(jìn)行跟蹤，以某一像素點(diǎn)為起始點(diǎn)，起動(dòng)邊界標(biāo)定自動(dòng)機(jī)，逆時(shí)針?lè)较蜻M(jìn)行跟蹤，跟蹤邊界像素點(diǎn)的同時(shí)記錄該像素的坐標(biāo)，跟蹤檢測(cè)到起始點(diǎn)表明該字符的輪廓檢測(cè)完畢。循環(huán)比較這一坐標(biāo)數(shù)組，分別得到X軸與Y軸上的最大與最小的坐標(biāo)值 (ymax,ymin,xmax,xmin)。則以(ymax,xmax),(ymax,xmin),(ymin,xmax),(ymin,xmin)這4個(gè)坐標(biāo)為頂點(diǎn)的矩形就是字符圖像的最小外接矩形(MER)[12-13]，那么字符區(qū)域MER的面積為

A=(xmax-xmin)×(ymax-ymin)

(1)

圖2 字符最小外接矩形

2 基線的檢測(cè)定位

2.1 特征點(diǎn)的選擇

設(shè)一行文本圖像T由n個(gè)字符Ci組成，字符按照從左向右的順序排列，即T={C1,C2,…,Cn}。設(shè)Pi=(xi,yi)是字符Ci邊框底邊中點(diǎn)，而P={p1,p2,…,pn}表示這些邊框底邊中點(diǎn)的集合。由于文本中大多數(shù)字符為上行字符和中行字符，其均以基線為基準(zhǔn)，所以集合P為基線的基礎(chǔ)。此時(shí)的集合P只是初始字符的集合。由圖3可知，行文本中可能出現(xiàn)“a”、“o”等在中上基線內(nèi)的字符，也有“T”、“h”等最高點(diǎn)超出上基線的字符，以及“p”、“g”等最低點(diǎn)低于基線的字符。不剔除這些最低點(diǎn)低于基線的字符，將會(huì)影響基線檢測(cè)的可信度，也會(huì)對(duì)后續(xù)傾斜角的檢測(cè)產(chǎn)生嚴(yán)重的誤導(dǎo)。

根據(jù)字符的書寫格式，筆者對(duì)文本行進(jìn)行了切分，如圖3所示。設(shè)中線和上基線之間的距離為h，則字符的行高為H1=3h或者H2=2h。由字符的邊框可得到字符的高度，則h=H1-H2，規(guī)定以h作為剔除的依據(jù)。若相鄰字符的邊框底邊中點(diǎn)的縱坐標(biāo)差Δy≥h，則剔除行高大的那個(gè)字符。

圖3 字符的書寫格式和行高參考

除了刪除像“p”“g”這種最低點(diǎn)低于基線的字符，本文還要?jiǎng)h除像“i”“j”這種由多個(gè)非連通區(qū)域組成的字符。因非連通，自動(dòng)機(jī)跟蹤時(shí)會(huì)分別標(biāo)記，并不會(huì)識(shí)別出這些部分屬于同一個(gè)字符，而標(biāo)記出的“i”“j”上的點(diǎn)同樣會(huì)給基線檢測(cè)產(chǎn)生較大的干擾。在標(biāo)記出字符的最小外接矩形后，通過(guò)比較這些區(qū)域的面積，剔除區(qū)域面積格外小的區(qū)域。刪除完冗余部分，剩下的點(diǎn)用‘﹒’標(biāo)記。

2.2 基線定位

確定了集合P，本文用最小二乘法進(jìn)行直線擬合[14]。

設(shè)基線方程

(2)

其中，pi=(xi,yi)∈p；k代表直線的斜率；b代表直線在y軸上的截距；k′和b′分別為其近似值；ε為權(quán)值。

根據(jù)最小二乘法的定義

(3)

設(shè)誤差方程

(4)

文中將這一誤差方程寫成矩陣形式

AεX=L+V

(5)

式中

VTV=min

(6)

即

(7)

其最小二乘解為

(8)

由此即可求出k和b，即求出了直線方程?；€確定后，通過(guò)基線方程f(xi)=k×xi+b,(i=1,2,…,n)可知基線的傾斜角即與坐標(biāo)軸的夾角，設(shè)基線與x軸正向的夾角為α

(9)

3 實(shí)驗(yàn)結(jié)果分析

為證明算法的有效性，實(shí)驗(yàn)分別對(duì)印刷體(新羅馬體)和手寫體進(jìn)行測(cè)試。

實(shí)驗(yàn)結(jié)果以圖4(a)中的傾斜行文本為例，字符的最小外接矩形用大小為一個(gè)像素的邊框標(biāo)記出，字符邊框用綠色的標(biāo)記，如圖4(c)中所示的行文本，圖中標(biāo)記的點(diǎn)即為所需字符的邊框底邊的中點(diǎn)，下劃線即為擬合基線。

圖4 文本行基線的檢測(cè)

圖5 手寫體行文本的基線

除了印刷字體，對(duì)于書寫清晰、連筆不多的手寫體文本，依據(jù)本文的算法基線也能檢測(cè)出。如圖5中的“ase”和“ete”，對(duì)于連筆書寫或產(chǎn)生粘連的多個(gè)字符，自動(dòng)機(jī)會(huì)識(shí)別成一個(gè)字符，因此只能標(biāo)記出一個(gè)中點(diǎn)，但文本整體書寫工整，所以并不影響基線的檢測(cè)。由此可見(jiàn)，本文的算法對(duì)于書寫工整、連筆較少的手寫文本也可進(jìn)行傾斜角檢測(cè)。

將本算法應(yīng)用于兩種不同的文本，如圖6和圖7所示，實(shí)驗(yàn)證明，本文的算法對(duì)于帶圖的文本和純文本同樣可行，且不受排版的局限。

圖6 帶圖文本校正前和校正后的二值圖像

圖7 純文本圖像矯正前和矯正后的二值圖像

4 結(jié)束語(yǔ)

本文提出了一種基于文本行基線的文本圖像傾斜角檢測(cè)算法，第3部分的實(shí)驗(yàn)結(jié)果分析已證實(shí)了本文算法對(duì)于傾斜角檢測(cè)的有效性。通過(guò)10組不同角度的對(duì)比實(shí)驗(yàn)可知，實(shí)驗(yàn)數(shù)據(jù)如表1所示，本文算法的平均誤差為0.028，低于輪廓投影法和文獻(xiàn)[1]的算法;輪廓投影法的最大絕對(duì)誤差0.08，文獻(xiàn)[1]算法的最大絕對(duì)誤差為0.11，而本文算法的最大絕對(duì)誤差為0.07；輪廓投影法的誤差標(biāo)準(zhǔn)偏差為0.174 50，文獻(xiàn)[1]算法的誤差標(biāo)準(zhǔn)偏差為0.075 43，而本文算法的誤差標(biāo)準(zhǔn)偏差為0.046 90(標(biāo)準(zhǔn)偏差反映算法的精確度，值越小代表偏差越小，說(shuō)明精確度越高)。本文算法無(wú)需計(jì)算整個(gè)文本圖像，只需選取一行即可對(duì)整個(gè)文本進(jìn)行傾斜角的檢測(cè)，這在某種程度上也提高了執(zhí)行效率。而且對(duì)于工整的手寫體文本也可以進(jìn)行傾斜角的檢測(cè)。本文算法清晰，操作方便，但對(duì)于中文及其他語(yǔ)言的檢測(cè)仍有待改進(jìn)，另外在噪聲情況下也需要優(yōu)化。

表1 傾斜角檢測(cè)算法實(shí)驗(yàn)結(jié)果對(duì)比

[1] 巨志勇,王平殿.基于幾何約束的文本圖像傾斜角檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(3):950-952.

[2] 顧國(guó)慶,許彥冰.數(shù)字圖像區(qū)域標(biāo)定的方法[J].上海理工大學(xué)學(xué)報(bào),2001,23(4):295-299.

[3] 吳曉光,王滌瓊,盛慧.一種獲取圖像區(qū)域最小外接矩形的算法及實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2004,30(12):124-125.

[4] Gu Guoqing,Chen Ke. Region-labeling-automata for images in square,triangular and hexagonal lattice [J].Journal of Three Dimensional Images,2003,17(1):161-165.

[5] 盧達(dá),謝銘培.文本行字符基線的精確測(cè)定算法[J].小型微型計(jì)算機(jī)系統(tǒng),2000, 21(7):726-728.

[6] 王滌瓊,張薇,顧國(guó)慶.用頂點(diǎn)鏈編碼計(jì)算圖像區(qū)域密集度和體態(tài)比[J].華東師范大學(xué)學(xué)報(bào):自然科學(xué)版,2005(1):59-62.

[7] 丁克良,沈云中,歐吉坤.整體最小二乘法直線擬合[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào):自然科學(xué)版,2010,29(1):44-47.

[8] Golub G H,Van Loan C F.An analysis of the total least squares problem[J].SIAM Journal Numer Anal,1980,17(6):883-893.

[9] Van Huffel S,Vandewalle J.The total least squares problem computational aspects and analysis[M].USA:SIAM Philadelphia,1991.

[10] 曾接賢,張桂梅,儲(chǔ)珺,等.霍夫變換與最小二乘法相結(jié)合的直線擬合[J].南昌航空大學(xué)學(xué)報(bào):自然科學(xué)版,2003,17(4):9-13.

[11] Mehdi F,Nicolas B,Salvatore T.A robust skew detection method based on maximum gradient difference and R-signature[C].Washington DC:Proceedings of the 18th IEEE International Conference on Image Processing,2011.

[12] Lu Y,Tan C L.Improced nearest neighbor based approach to accurate document skew estimation[C].Washington DC:Proceedings of 7th International Conference on Document Analysis and Recognition,2003.

[13] Yu B,Jain A K.A robust and fast skew detection algorithm for generic documents[J].Pattern Recognition,1996,29(10):1599-1629.

A Skew Detection Algorithm Based on the Baseline of Document

For the problem, this paper proposed a new skew detection algorithm based on the baseline of document for detecting the angle of the document image. The algorithm obtains the minimum external rectangles and the frames of the characters by the region-labeling-automata, and eliminates the redundancy of characters based on the areas of the parts and the line height difference of the adjacent characters. A straight line is fitted as the baseline based on the frame of rest characters, and the skew angle is evaluated by the moment calculation. The experimental results show that this algorithm is effective and can improve the accuracy.

document image; skew detection; boundary demarcation; linear fitting

2016- 01- 12

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

巨志勇(1975-)，男，博士，講師。研究方向：圖像處理和模式識(shí)別。何曉蕾(1991-)，女，碩士研究生。研究方向：圖像處理和模式識(shí)別。王超男(1992-)，女，碩士研究生。研究方向：圖像處理和模式識(shí)別。

10.16180/j.cnki.issn1007-7820.2016.10.012

TP391.41

A

1007-7820(2016)10-039-04