分段Radon變換的彎曲文本基線提取

羅曉萍,朱金好

1(安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 蕪湖 241003)2(皖南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院,安徽 蕪湖 241002)

1 引 言

隨手照拍文檔圖像常因紙張彎曲不能正確有效分析理解,需進(jìn)行圖像幾何糾正預(yù)處理.糾正技術(shù)文檔圖像攤平(Document Image Dewarping)常用到文本基線[1-6].文本基線是指文檔中文本、圖片、表格的對齊線,常不顯現(xiàn)但平行.文本基線提取越準(zhǔn)確,圖像攤平效果越好.這并不容易實(shí)現(xiàn),因?yàn)橛卸囗?xiàng)因素影響:紙張彎曲破損、背景多變、圖像模糊、成像低分辨率、明暗不勻等.

文檔圖像基線提取技術(shù)分為2類:傾斜文本基線提取和彎曲文本基線提取.傾斜文本基線提取針對成像時(shí)文本紙張平整沒有彎曲或皺褶的圖像,主要方法有投影輪廓法(projection profile)、Hough變換、互相關(guān)、最近鄰聚類,其次還有基于小波分解、矩、形態(tài)學(xué)和傅里葉分析等[7].彎曲文本基線提取針對成像時(shí)紙張有卷曲、拱起或者扭曲的圖像,主要有以文本行特征為起點(diǎn)和以文字連通域特征為起點(diǎn)的方法.

以文本行特征為起點(diǎn)的彎曲文本基線提取方法將文本行作為整體來對待,提取特定特征來區(qū)別于其它元素.若特征區(qū)別力不強(qiáng),則會計(jì)算耗時(shí)或者產(chǎn)生誤差.文獻(xiàn)[1]根據(jù)文本行具有的自相似性,搜索文本行并采用優(yōu)化方法逐步求精.對于滿文文檔算法效果良好,但有文本行搜索步長必須設(shè)置較小否則會漏行,行基線優(yōu)化方法耗時(shí)問題.文獻(xiàn)[8]采用Seam Carving和優(yōu)化過程來分割文本行,但卻易于受噪聲影響和易在相鄰行間串走.文獻(xiàn)[9]將圖像分成條狀子圖,使用Radon變換結(jié)合動態(tài)規(guī)劃算法尋優(yōu)檢測出行基線,子圖行基線再連接使用3次B樣條曲線擬合.此方法所得行基線不能準(zhǔn)確貼合文本邊緣并且只適用于橫排文檔.

以文字連通域特征為起點(diǎn)的彎曲基線提取方法利用連通域分析、圖或者聚類技術(shù)區(qū)別出每行,由下而上分析文檔結(jié)構(gòu),思路簡潔,多受關(guān)注.此法需構(gòu)造合理的圖結(jié)點(diǎn)間度量權(quán)值,也容易陷入局部優(yōu)化狀態(tài).文獻(xiàn)[2]在二值化圖像連通域基礎(chǔ)上設(shè)計(jì)距離度量,構(gòu)造帶權(quán)圖,采用最小生成樹實(shí)現(xiàn)連通域聚類再剪枝優(yōu)化區(qū)別出每行,提取每行最低點(diǎn)來擬合曲線.其思路和文獻(xiàn)[10]相似.當(dāng)行連通域所含字符較少時(shí),連通域方向和其所在行方向有較大差異,給連通域間的距離度量帶來誤差,文獻(xiàn)[10]在圖像子塊上投影統(tǒng)計(jì)區(qū)域文本行方向作為連通域方向,避免連通域像素?cái)?shù)目較少引起的誤差.文獻(xiàn)[2]采用字符最低點(diǎn)來擬合曲線,對英文字符有效,對中文字符存有誤差[9].文獻(xiàn)[11]連通域間采用多維特征度量構(gòu)建超圖,文獻(xiàn)[12]采用間距檢測行,皆沒有充分考慮連通域之間的方向關(guān)系,當(dāng)文本行間距較小時(shí),相鄰行易于相互影響.

受文獻(xiàn)[9]啟發(fā),兼顧文檔整體版面和局部特征,利用整體曲線可由分割直線擬合近似替代理論,文中提出一種準(zhǔn)確提取彎曲文檔圖像基線的方法.首先根據(jù)文本排列方式將圖像分割成豎排區(qū)域和橫排區(qū)域,然后區(qū)域分成條狀子圖,對條狀子圖獲取基直線,再連接各子圖直線擬合得到彎曲基線.主要特點(diǎn)有:1)最近鄰尋找最近方向并統(tǒng)計(jì)出主要方向得到文本的排列方式,由文本排列方式將圖像分割再區(qū)別處理,適用較為復(fù)雜排版的文檔頁;2)使用連通域傾斜方向(Orientation)減少Radon變換次數(shù),降低計(jì)算量;3)使用Radon變換對連通域進(jìn)行分割和合并,綜合了字符間相對位置;4)同一條狀子圖各基直線傾斜角度區(qū)別開來,不使用相同角度近似,獲得更準(zhǔn)確的彎曲基線.

2 方法過程

方法分2步.第1步通過最近鄰尋找得到文本的排列方式,各局部排列方式可以不一樣;第2步為彎曲基線提取.

2.1 最近鄰尋找

一般情況下,印刷文本相鄰字符較近,字符間距比行間距窄.采用最近鄰聚類的傾斜方法檢測即基于此.字符間距不是一定比行間距窄,常有比行間距寬的情形,當(dāng)行末有標(biāo)點(diǎn)符號或者行中有阿拉伯?dāng)?shù)字時(shí),字符間距會比行間距寬,相機(jī)成像也會加劇這一情況,這使得通過分析行間距實(shí)現(xiàn)行間分割的方法失誤[1].綜合考慮,利用前一情況,本文根據(jù)連通域距離遠(yuǎn)近像素?cái)?shù)增加情況尋找最近鄰,避免后者干擾,在整體上統(tǒng)計(jì)確定區(qū)域主方向.

文中方法在二值化連通域上進(jìn)行.文檔圖像二值化效果影響文檔圖像進(jìn)一步的分析和識別[13,14].二值化易產(chǎn)生噪聲,因?yàn)樽址P畫有可能分?jǐn)?特別是圓形字母,且圖像偏暗部分影響被放大.圖像文檔中還常有插圖、表格、圖形、公式等,其連通域一般比文字要大.采用直方圖統(tǒng)計(jì)連通域?qū)捀?基于文字大小相近且量相對較多,分析出文字大小,剔除過濾較小的噪聲和較大的圖表、公式.

圖1 連通域四周方向編號Fig.1 Direction numbers around CC

統(tǒng)計(jì)連通域周圍相同距離內(nèi)分布鄰域像素?cái)?shù)目來獲得最近鄰.對每一連通域,將其上、左、下、右四個(gè)方向編號為1,2,3,4,如圖1所示.在四個(gè)方向分2次向外擴(kuò)展矩形區(qū)域,如圖2(b)(c)所示,計(jì)算矩形區(qū)域內(nèi)占有像素?cái)?shù)變化情況.若某方向在2次擴(kuò)展中落入的像素?cái)?shù)沒有增加或者增加較少,說明此方向附近沒有其它字符;若某方向在2次擴(kuò)展中囊括的像素?cái)?shù)明顯增加并且增加數(shù)量多于其它幾個(gè)方向,則說明該方向是字符行或列延伸方向,記錄該方向.擴(kuò)展矩形延伸寬度和前文所得文字寬高成比例.遍歷方式采用深度優(yōu)先方式,依據(jù)方向聚類結(jié)果見圖2(d).連通域四周方向還可細(xì)分成8方向.

用連通域近鄰方向編號取代連通域標(biāo)記,圖像自然分割成橫排區(qū)域和豎排區(qū)域.

2.2 彎曲基線提取

豎排區(qū)域在其主方向旋轉(zhuǎn),和橫排區(qū)域作相同處理.區(qū)域分成條狀子圖,獲取每個(gè)條狀子圖基直線,基直線連接、擬合出區(qū)域彎曲行基線.若條狀子圖基直線斜率相同,則基直線的獲取可以直接通過在條狀子圖上施加Radon變換獲得,不需要首先連通域重心合并分行.實(shí)際上條狀子圖基直線斜率并不總是相同,當(dāng)被拍紙張有圓弧隆起或下凹時(shí),會出現(xiàn)相鄰行斜率完全相反的情形,這時(shí)使用Radon變換找不出規(guī)律,連通域重心合并分行反而簡單有效.

圖2 連通域鄰近區(qū)域和近鄰聚類結(jié)果Fig.2 Neighbor regions of CCs and clusters

2.2.1 連通域重心排序和合并

計(jì)算連通域重心并在垂直方向上排序,重心相距在一定閾值內(nèi)的連通域合并.當(dāng)文本行間距比較大時(shí),此方法簡單有效;當(dāng)文本行間距較小時(shí),相鄰行或者其部分常被合并在一起.因?yàn)楹罄m(xù)基于連通域傾斜角度的Radon變換需要一定數(shù)據(jù)量才有效,所以合并閾值不妨大些,取數(shù)倍于文字連通域高度.

2.2.2 行連通域優(yōu)化

使用Radon變換分拆包含多行文字的連通域成單行連通域,合并分散連通域成行連通域.

Radon變換用來計(jì)算圖像矩陣在某方向的投影.設(shè)H和W為條狀子圖S的高度和寬度.投影坐標(biāo)系定義為原點(diǎn)位于圖像S中心,x、y軸平行于圖像坐標(biāo)系的x、y軸.圖像S在給定角度上Radon變換定義為沿公式(1)直線上積分[9,15].公式(1)稱為投影線.

xcosθ-ysinθ=ρ

(1)

圖3(a)為72×230像素的文本圖像,(b)(c)分別為θ是0°,90°時(shí)的Radon變換值曲線圖,θ=0°時(shí)投影線垂直水平軸,θ=90°時(shí)投影線平行水平軸,投影線傾斜角度為文本行傾斜角度.圖3(c)有很明顯山峰和低谷,低谷處反映出行間留白位置,低谷向山峰、山峰向低谷過渡處為虛擬基線位置.由此得出利用Radon變換的低谷可以檢測區(qū)域圖像文本行數(shù).見圖4所示,圖4(a)為區(qū)域圖像,(b)為其在76°時(shí)的Radon變換值曲線圖,低谷處即為行間留白投影.

圖3 無傾斜和彎曲文本圖像Radon變換Fig.3 Radon transform of document image without distortion

利用連通域的傾斜角度來減少Radon變換投影角度的范圍.圖4 Radon變換所用角度為連通域傾斜角度.連通域傾斜角度為囊括連通域像素且和連通域有相同二階矩的橢圓主軸和圖像水平軸的夾角.當(dāng)連通域圖像寬高比比值離1較遠(yuǎn)時(shí),行傾斜角度接近連通域傾斜角度,比值接近1時(shí),行傾斜角度和連通域傾斜角度之間誤差較大,見圖5.多行部分文字合并在一個(gè)連通域里、一行文本被拆成多個(gè)小連通域影響寬高比,連通域傾斜角度誤差可能會較大.考慮到條狀子圖里的行都是相鄰的行,即使在曲面情況下其相鄰行傾斜角度變化不會太大,因此排除離群點(diǎn)統(tǒng)計(jì)大部分傾斜角度變化規(guī)律擬合多項(xiàng)式,用擬合多項(xiàng)式值來替代遠(yuǎn)離的傾斜角度.優(yōu)化后的連通域傾斜角度被用來限制Radon變換范圍,有效減少0°-179°上投影引起的計(jì)算量.

圖4 輕微彎曲圖像Radon變換Fig.4 Radon transform of slightly warped document image

在完整圖像劃分條狀子圖時(shí),條狀子圖寬度設(shè)置需考慮圖像的彎曲度、連通域方向、Radon變換所需數(shù)據(jù)量.若寬度設(shè)置過寬,文本虛擬基線不是近似直線,則Radon變換不能很好地進(jìn)行行分割.若寬度設(shè)置過窄,后續(xù)Radon變換不能檢測出基線,見圖5所示.

圖5 小連通域引起的檢測錯(cuò)誤Fig.5 Error produced by small CC

使用Radon變換分拆多行連通域算法如下.

1.計(jì)算每個(gè)連通域相對于圖像水平軸的傾斜角度.

(2)

P=(HTWH)-1HTWA

(3)

(4)

3.對每個(gè)連通域i,若其寬度大于條狀子圖寬度一半,進(jìn)行如下操作,否則轉(zhuǎn)4.

2)在投影值零點(diǎn)最多的方向上,統(tǒng)計(jì)投影值間隔零點(diǎn)情況,有間隔零點(diǎn)則將連通域在間隔零點(diǎn)反映的位置進(jìn)行分拆,被分拆的新連通域添加在i+1位置,連通域總數(shù)作相應(yīng)增加.

3)計(jì)算行的上下邊虛擬基線上兩點(diǎn).

4.將連通域i記入待合并隊(duì)列.

待合并隊(duì)列連通域?qū)ふ宜谛?不同行區(qū)域之間交集為空,行區(qū)域和非本行文本連通域交集為空.若連通域和行區(qū)域交集非空,則說明連通域和行區(qū)域連通域在一行.

合并分行連通域成行連通域算法如下.

1.根據(jù)上述算法得到的行上下邊虛擬基線,計(jì)算其所圍區(qū)域得到行域.

2.對于每個(gè)待合并隊(duì)列連通域,計(jì)算其與每個(gè)行域交集所包含的像素?cái)?shù).若像素?cái)?shù)達(dá)到某閾值,則認(rèn)為它們是同屬一行.

2.2.3 基線點(diǎn)提取

對每個(gè)行連通域操作如下,圖6為算法所獲基線示意圖.

圖6 算法所獲基線示意圖Fig.6 Result images added baselines

1.形成行區(qū)域圖像.

2.在行連通域傾斜角度的垂直角度上進(jìn)行Radon變換.

3.計(jì)算非零區(qū)間寬度maxW,取前0.6maxW個(gè)最大值均值aver,獲得大于aver區(qū)間首元素和末元素ρ值.

4.在條狀子圖左右兩邊取2點(diǎn)x坐標(biāo),使用公式(5)(6)計(jì)算行上下邊基點(diǎn)的高度.

(5)

(6)

5.分上下2組記錄基點(diǎn)坐標(biāo).

2.2.4 各條狀子圖行基線點(diǎn)聚集并擬合

原區(qū)域劃分時(shí)要使相鄰條狀子圖有一定寬度的重合.在重合部分的中間線上計(jì)算基線點(diǎn)位置,方便行基點(diǎn)聚集.聚集后基點(diǎn)集合采用3次多項(xiàng)式擬合.

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

數(shù)據(jù)集為CBDAR2007 dewarping contest dataset[16]和自備圖像.前者為手持相機(jī)對科技類圖書在辦公環(huán)境下拍得,有灰度和二值圖像,主要是橫排文檔,有幾何和透視形變.

文中最近鄰尋找時(shí),探索矩形框?qū)挾葹?/5字符寬度像素.當(dāng)子圖行傾斜較大且行間距小時(shí),為防止鄰行影響,此值設(shè)置偏小,因后續(xù)連通域重心排序合并算法簡單,偏小不會增加運(yùn)行復(fù)雜度.合并時(shí)閾值為一個(gè)字高度.此閾值設(shè)置較小時(shí),連通域分散,可能因數(shù)據(jù)量較少而使連通域方向不能反映文本方向.條狀子圖設(shè)置為10倍字符寬度,重合寬度為3倍字符寬度,依從于圖像拼接技術(shù)中比例要求.

圖7(a)(b)(c)為部分實(shí)驗(yàn)結(jié)果圖,其寬高分別為1220×1084像素、685×458像素、800×600像素,皆為自備圖像.圖7為英文文檔,圖8為中文文檔,行基線皆準(zhǔn)確地檢測出.

圖7 部分實(shí)驗(yàn)結(jié)果Fig.7 Part of result images

分散的噪聲對本文方法影響小,因?yàn)橄袼仄俚倪B通域會被移除.文本筆畫斷筆對檢測方法無影響,因?yàn)榛€提取在像素累和基礎(chǔ)上進(jìn)行.圖6(d)的基線是(c)簡單閾值二值化下提取,二值化丟失了部分筆畫并沒有影響基線提取效果.

圖8(a)寬高為1072×1680像素,文檔里有大小不同文字.(b)為文獻(xiàn)[9]PDF文件“拍快照”所得圖,近景文本線準(zhǔn)確,遠(yuǎn)景標(biāo)題行不能正確檢出.文獻(xiàn)[9]方法在文本邊緣上進(jìn)行.邊緣檢測對噪聲敏感,為減弱噪聲影響,需要對圖像濾波,圖像模糊時(shí)需要對圖像作銳化處理,這些都增加方法時(shí)空復(fù)雜度,尤其圖像分辨率較大時(shí).

圖8 和文獻(xiàn)[9]結(jié)果比較Fig.8 Result compared with paper[9]

圖9、圖10(a)為原圖,寬高分別為2112×2816像素、2448×3264像素,來自CBDAR2007 dewarping contest dataset.(b)為文獻(xiàn)[8]方法所得圖,黑色線為檢測的文本中線,出現(xiàn)走行現(xiàn)象.(c)為本文方法結(jié)果圖,提取的曲線和文本行基線一致.(d)上、下圖分別為圖(b)(c)細(xì)節(jié).

在實(shí)驗(yàn)代碼沒有優(yōu)化的情況下,文中方法和文獻(xiàn)[8]方法都比較耗時(shí).實(shí)驗(yàn)條件為Intel(R) Core(TM) i3 CPU1.8GHz,4GB內(nèi)存,Windows8,MatlabR2015b編程實(shí)現(xiàn).文獻(xiàn)[9]比較快速,在其實(shí)驗(yàn)環(huán)境下圖像6M大小時(shí)僅需6-8秒.

文中方法將基線點(diǎn)提取、聚集擬合操作修改成文本行像素聚合操作,便能實(shí)現(xiàn)文本行檢測.文本行檢測的召回率(Recall Rate)和正確率(Precision Rate)在CBDAR2007 dewarping contest dataset上評估.此數(shù)據(jù)集共102張圖像約3119行文本.參照文獻(xiàn)[17],當(dāng)檢測到的行i和標(biāo)準(zhǔn)行j之間重合比例MatchScore(i,j)大于0.95時(shí),認(rèn)為行i為正確.MatchScore(i,j)見公式(7),其中Ri為行i的像素集,Gj為行j像素集.本文和其它三種方法的召回率和正確率見表1.

表1 四種文本行檢測方法性能評估
Table 1 Performance evaluation of four text line extraction methods

方法召回率正確率文中方法93.18%75.39%文獻(xiàn)[10]92.67%69.91%文獻(xiàn)[18]89.02%42.51%文獻(xiàn)[1]66.28%56.50%

圖9 和文獻(xiàn)[8]結(jié)果比較Fig.9 Result compared with paper[8]

圖10 和文獻(xiàn)[8]結(jié)果比較Fig.10 Result compared with paper[8]

(7)

4 結(jié)束語

連通域近鄰查找沒有根據(jù)連通域重心而是基于相鄰矩形區(qū)域像素分布情況,由像素標(biāo)記得到其所在連通域,前期已有去除噪聲步驟,所以部分像素?cái)?shù)即使受到噪聲干擾,也不會影響后期統(tǒng)計(jì)結(jié)果.Radon變換作用被充分應(yīng)用于分割文本行、合并同行文字、提取分段行基線,為文本基線精確提取提供穩(wěn)定支持.精確提取的文本基線為擬合文檔平面、獲取相機(jī)參數(shù)提供良好支持.

文中方法基于彎曲文本基線局部線性的假設(shè).當(dāng)此假設(shè)不成立時(shí),方法可能會失效.當(dāng)文檔紙質(zhì)有對折式彎曲時(shí),所拍圖像文本行在折痕處突然改變方向,折痕處文本行基線不能用直線近似,此時(shí)方法不適用.進(jìn)一步研究深度學(xué)習(xí)強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)更通用更魯棒的文本行檢測、彎曲文本圖像糾正.