張 倩,陳其浩,楊 碩
(山東科技大學(xué)測(cè)繪與空間信息學(xué)院,山東青島 266590)
紙質(zhì)檔案數(shù)字化對(duì)歷史文檔數(shù)據(jù)的保存和綜合分析至關(guān)重要,表格字符定位技術(shù)是文檔分析與字符識(shí)別領(lǐng)域的重要分支[1]。從表格框線中準(zhǔn)確定位字符區(qū)域是字符分割的關(guān)鍵,故重點(diǎn)在于表格線的檢測(cè)問(wèn)題[2],因此高效準(zhǔn)確地定位到表格信息至關(guān)重要。
早期的表格識(shí)別技術(shù)主要是基于啟發(fā)式規(guī)則對(duì)表格進(jìn)行識(shí)別,Chandran 等[3]根據(jù)水平或垂直方向的投影,提出以樹(shù)的形式表示表格結(jié)構(gòu)的表格提取系統(tǒng),此方法能夠快速完成對(duì)表格的識(shí)別,但不能生成表格的邏輯結(jié)構(gòu);Yildlz等[4]提出的Pdf2table 方法通過(guò)候選表格的絕對(duì)位置檢測(cè)和合并文本段提取表格信息,但無(wú)法準(zhǔn)確定位不規(guī)則表格;Koci 等[5]利用遺傳算法將表格視為子圖識(shí)別出來(lái),基于啟發(fā)式規(guī)則的表格識(shí)別方法設(shè)計(jì)較為復(fù)雜,準(zhǔn)確度及適應(yīng)性較差;Fan 等[6]利用表格模板進(jìn)行識(shí)別的表格識(shí)別系統(tǒng),將表格識(shí)別問(wèn)題轉(zhuǎn)為矩陣匹配問(wèn)題,識(shí)別效率較高,但對(duì)表格模型的表達(dá)能力要求較高。針對(duì)識(shí)別算法,張艷等[7]用鏈碼法對(duì)票據(jù)表格框線中的信息進(jìn)行提取,但是該方法對(duì)于噪聲較大的情況不具有魯棒性;張國(guó)鋒等[8]提出基于梯度霍夫變換的藏文手寫(xiě)采樣表格檢測(cè),該方法由于表格線被多次檢測(cè),造成部分表格線重疊;張國(guó)福等[9]通過(guò)改進(jìn)概率霍夫變換算法提取直線特征,從而實(shí)現(xiàn)對(duì)電梯門(mén)狀態(tài)的實(shí)時(shí)監(jiān)測(cè),在時(shí)間和準(zhǔn)確率上均有較大提升;邱東等[10]通過(guò)改進(jìn)概率霍夫變換算法,添加約束條件加以改進(jìn),擬合出正確車(chē)道線,以實(shí)現(xiàn)對(duì)車(chē)道線的快速檢測(cè)。
部分低質(zhì)量文檔圖像中存在表格線變形、不清晰等情況,導(dǎo)致表格字符定位的魯棒性較差[11]。針對(duì)表格字符定位技術(shù)中存在字符定位適應(yīng)性較差、識(shí)別方法較復(fù)雜以及對(duì)表格字符信息的提取不完全等問(wèn)題,本文結(jié)合霍夫變換算法提取直線的思想,提出一種基于改進(jìn)概率霍夫變換的表格字符提取算法。該算法首先通過(guò)四鄰域灰度差異閾值法對(duì)圖像進(jìn)行二值化處理,再對(duì)傳統(tǒng)概率霍夫變換進(jìn)行改進(jìn),實(shí)現(xiàn)表格線的精確檢測(cè),進(jìn)而確定字符所在表格框的位置,最后基于投影法實(shí)現(xiàn)表格字符的精確定位。針對(duì)低質(zhì)量表格數(shù)據(jù)圖像,本文算法可實(shí)現(xiàn)表格內(nèi)字符的精確定位。
低質(zhì)量表格圖像的分析與識(shí)別首先需要對(duì)圖像進(jìn)行預(yù)處理,二值化處理是圖像預(yù)處理的關(guān)鍵技術(shù),直接影響字符定位精度。目前,主要的二值化方法有全局閾值法和局部閾值法[12],基于全局固定閾值法的最大類(lèi)間方差法(OTSU 算法)[13]可以快速有效地確定類(lèi)間分割閾值,但對(duì)于目標(biāo)灰度范圍分布較大的圖像,存在直線斷裂現(xiàn)象,分割質(zhì)量沒(méi)有保障。基于局部閾值法的Sauvola 算法[14]可以進(jìn)行局部閾值多目標(biāo)分割,在圖像光照不均勻的情況下,具有較好的分割效果,但存在運(yùn)算速度慢、偽影現(xiàn)象,嚴(yán)重影響到字符的精確定位與分割。因此,本文針對(duì)低質(zhì)量表格圖像提出了一種四鄰域灰度差異閾值法二值化算法。
圖像進(jìn)行去噪處理后,目標(biāo)區(qū)域與背景區(qū)域灰度差異較大,因此本文提出一種基于直線灰度差異特征的二值化算法。該算法的主要思想是:根據(jù)圖像的灰度差異,設(shè)置固定的閾值及窗口半徑,對(duì)圖像進(jìn)行滑窗處理,選取四鄰域方向半徑為R 的像素點(diǎn),將其灰度值與中心像素灰度值作差,并與閾值進(jìn)行比較,以確定前景和背景。具體步驟如下:①取窗口中心像素的灰度值P;②對(duì)表格中的字符進(jìn)行投影,根據(jù)每行白色像素的個(gè)數(shù)獲取閾值,取閾值的平均值T;③根據(jù)閾值T,取中心像素四鄰域方向上半徑為R的像素灰度值P1、P2、P3、P4,本文R 取值為3;④計(jì)算4 個(gè)像素點(diǎn)與中心像素灰度值的差值di;⑤通過(guò)式(1)對(duì)整張表格圖像進(jìn)行逐像素處理,得到最終二值結(jié)果。
di的計(jì)算示意圖如圖1 所示。
本文將傳統(tǒng)二值化算法與四鄰域灰度差異閾值法進(jìn)行實(shí)驗(yàn)對(duì)比。各類(lèi)算法的二值化輸出結(jié)果如圖2 所示,其中圖2(a)為低質(zhì)量的表格圖像,圖2(b)、圖2(c)分別為OT?SU 算法及Sauvola 算法得到的二值圖像,在兩種算法二值結(jié)果圖中,直線斷裂現(xiàn)象較為嚴(yán)重,存在字符不連續(xù)現(xiàn)象,圖2(d)為本文四鄰域灰度差異閾值法得到的二值圖像。從直觀視覺(jué)角度看,該算法對(duì)表格線的識(shí)別效果較好,基本保留了圖像的表格線及字符信息,取得了較好的二值效果。
Fig.1 Calculation diagram of di圖1 di計(jì)算示意圖
Fig.2 Comparison of binary results圖2 二值結(jié)果對(duì)比
表格線的檢測(cè)精度直接影響到后期字符定位結(jié)果[15]。由于概率霍夫變換算法中霍夫空間的投票方式會(huì)造成直線的錯(cuò)誤檢測(cè),本文采用改進(jìn)概率霍夫變換算法檢測(cè)表格線,在直線融合及去除誤提直線兩個(gè)方面添加約束條件,以獲得較準(zhǔn)確的表格線。算法原理如圖3 所示。
Fig.3 Algorithm flow圖3 算法流程
標(biāo)準(zhǔn)霍夫變換檢測(cè)直線[16-17]的基本原理是:利用點(diǎn)和線在不同參數(shù)空間中的對(duì)偶性,將圖像空間中的直線轉(zhuǎn)換為參數(shù)空間中的點(diǎn),進(jìn)而對(duì)參數(shù)空間中的點(diǎn)進(jìn)行投票,根據(jù)設(shè)定的閾值確定曲線,從而將檢測(cè)任意形狀的問(wèn)題轉(zhuǎn)化為統(tǒng)計(jì)峰值問(wèn)題。
將笛卡爾坐標(biāo)系下的直線映射到參數(shù)空間中,直線上所有的點(diǎn)在參數(shù)空間中都有一條直線與之對(duì)應(yīng)。如圖4(a)所示,笛卡爾坐標(biāo)系下存在直線y=kx+b,直線上存在兩點(diǎn)(x1,y1)(x2,y2),在參數(shù)坐標(biāo)系中有兩條直線與之對(duì)應(yīng),且兩直線相交于一點(diǎn)(k0,b0);如圖4(b)所示,將直線映射到極坐標(biāo)系中,直線上的點(diǎn)在極坐標(biāo)系中都有一條曲線與之對(duì)應(yīng),曲線相交于一點(diǎn)(ρ,θ)。通過(guò)統(tǒng)計(jì)參數(shù)空間中交點(diǎn)的個(gè)數(shù)確定直線位置,達(dá)到檢測(cè)直線的目的。
Fig.4 Principle of Hough transform圖4 霍夫變換原理
經(jīng)典的霍夫變換算法檢測(cè)直線時(shí),時(shí)間和空間復(fù)雜度較高,在直線檢測(cè)過(guò)程中只能確定直線方向,并且檢測(cè)直線時(shí)進(jìn)行了離散化處理,檢測(cè)精度受參數(shù)離散間隔制約,嚴(yán)重影響到字符的精確定位。因此,本文采用概率霍夫變換算法(Progressive Probabilistic Hough Transform,PPHT)[18]提取表格線。PPHT 算法是在標(biāo)準(zhǔn)霍夫變換的基礎(chǔ)上加以改進(jìn)的直線提取算法,此算法無(wú)需對(duì)邊緣像素點(diǎn)逐一進(jìn)行檢測(cè),而是隨機(jī)選取少量邊緣點(diǎn)轉(zhuǎn)換到參數(shù)空間下進(jìn)行小范圍的投票,從而提高運(yùn)算效率。PPHT 算法檢測(cè)直線的具體步驟如下:①將直線檢測(cè)獲取的邊緣圖像的前景點(diǎn)放入待選邊緣點(diǎn)集P;②將參數(shù)空間分為n 個(gè)小區(qū)間,對(duì)應(yīng)n個(gè)二維累加器acc(ρ,θ),其中ρ 為直線到原點(diǎn)的距離,θ 為直線的角度,ρ 和θ 的初值均為0;③隨機(jī)從待處理邊緣點(diǎn)集P中選取某一像素點(diǎn),將此點(diǎn)投射在霍夫空間中,計(jì)算該像素點(diǎn)在霍夫空間中各θ 值下對(duì)應(yīng)的ρ 值,并將對(duì)應(yīng)的累加器acc(ρ,θ)投票數(shù)加1;④從點(diǎn)集中刪除已處理過(guò)的點(diǎn)并更新累加器;⑤更新后累加器的值與閾值比較,若大于閾值,則完成一次直線擬合,刪除直線上所有的點(diǎn),若不滿(mǎn)足返回步驟③;⑥根據(jù)線段的長(zhǎng)度及方向的線段排序,得到表格線位置信息。
針對(duì)表格圖像,概率霍夫變換算法能確定直線的方向信息,且能夠檢測(cè)出圖像中直線的兩個(gè)端點(diǎn),精確定位圖像中的直線[19]。但由于概率霍夫變換算法投票機(jī)制的局限性以及噪聲干擾,檢測(cè)出的直線會(huì)出現(xiàn)斷裂現(xiàn)象,且檢測(cè)直線時(shí)對(duì)與直線共存的非直線結(jié)構(gòu)不敏感,會(huì)造成字符上直線特征誤檢。為獲得較準(zhǔn)確的表格線,本文進(jìn)行以下改進(jìn):
(1)直線融合。概率霍夫變換算法通過(guò)檢測(cè)直線確定直線方向,卻丟失了線段的長(zhǎng)度信息,本文根據(jù)PPHT 算法檢測(cè)出來(lái)的直線,篩選出線段的兩個(gè)端點(diǎn),以直線長(zhǎng)度和相鄰直線間的距離為約束條件,在一定的范圍內(nèi)進(jìn)行直線融合,恢復(fù)表格直線的長(zhǎng)度信息,修補(bǔ)缺失的表格線。如圖5 所示,其中圖5(a)為PPHT 算法檢測(cè)出來(lái)的表格線,圖5(b)為直線融合后的表格線。
Fig.5 Straight line fusion圖5 直線融合
(2)誤提字符干擾線去除。由于PPHT 算法提取直線是根據(jù)直線特征而進(jìn)行,部分表格圖像中字符之間間隔較小,具有直線特征的字符會(huì)連接在一起,粘連字符易被識(shí)別成直線,造成直線誤提現(xiàn)象。字符上誤檢的直線,豎直方向上存在一定寬度的字符,因此根據(jù)直線周?chē)袼靥卣魅コ`提直線。如圖6 所示,其中圖6(a)為PPHT 算法誤提字符直線圖,具有直線特征的字符被識(shí)別成直線,圖6(b)為誤提直線去除后的結(jié)果圖,可有效去除誤提字符干擾線。
Fig.6 Removing interference line圖6 去除誤提直線
對(duì)表格圖像進(jìn)行光學(xué)掃描時(shí),由于硬件設(shè)備人為擺放等原因,表格會(huì)存在一定程度上的傾斜,造成圖像像素點(diǎn)的定位偏差[20],從而嚴(yán)重影響后續(xù)的表格字符分割。表格圖像中表格均由水平方向和豎直方向的線段構(gòu)成,表格線與表格圖像具有大致相同的傾角,根據(jù)表格線的傾角即可得到表格的傾角。為降低傾斜圖像在字符識(shí)別過(guò)程中產(chǎn)生的影響,本文通過(guò)改進(jìn)的概率霍夫變換算法對(duì)圖像進(jìn)行傾斜校正[21]。
表格校正算法的主要思想是通過(guò)改進(jìn)的概率霍夫變換算法檢測(cè)出的直線傾角確定圖像的傾角。在笛卡爾坐標(biāo)系中,過(guò)(x1,y1)(x2,y2)的直線y=kx+b在參數(shù)空間中所對(duì)應(yīng)的坐標(biāo)系可以表示為ρ=xcosθ+ysinθ。利用式(3)可得到直線的傾斜角度。
通過(guò)改進(jìn)的概率霍夫變換算法獲取表格線信息,分別得到橫線和豎線的傾斜角度。
(1)以橫線為例,通過(guò)改進(jìn)的概率霍夫變換算法得到橫線的傾斜角度θ1、θ2、θ3…θn,利用式(4)對(duì)所有橫線的傾斜角度取平均值θ。
(2)對(duì)圖像旋轉(zhuǎn)θ 度,得到校正后的圖像。
如圖7 所示,其中圖7(a)為原始圖像,圖7(b)為改進(jìn)的概率霍夫變換算法校正后的圖像。實(shí)驗(yàn)結(jié)果表明,該方法能從復(fù)雜圖像中實(shí)現(xiàn)表格線傾斜校正。
通過(guò)前期對(duì)表格圖像的預(yù)處理、對(duì)表格線的提取以及對(duì)表格圖像的傾斜校正,可精確定位表格線。為了有效地提取表格字符,還需要對(duì)表格字符進(jìn)行粗定位和精確定位。
根據(jù)表格的橫線與豎線的交點(diǎn)位置信息確定字符所在矩形框的4 個(gè)交點(diǎn)坐標(biāo),即可粗略定位到表格字符的位置,如圖8 所示。
Fig.7 Table line tilt correction圖7 表格線傾斜校正
Fig.8 Rough positioning of characters圖8 字符粗定位
為了提高字符識(shí)別精度,在粗定位的基礎(chǔ)上進(jìn)行精確定位,本文通過(guò)投影法對(duì)字符進(jìn)行定位,以獲得字符的精確位置。
首先,對(duì)圖像從左到右及從上到下進(jìn)行遍歷,若滿(mǎn)足式(5),即得到字符的左邊界及上邊界。其中Cn為第n行白色像素個(gè)數(shù),Cn+1 為第n+1 行的白色像素個(gè)數(shù)。
其次,對(duì)圖像從右到左及從下到上進(jìn)行遍歷,若滿(mǎn)足式(6),即得到字符的右邊界及下邊界。其中Cn為第n行白色像素個(gè)數(shù),Cn-1 為第n-1 行的白色像素個(gè)數(shù)。
如圖9 所示,其中圖9(a)為原圖,圖9(b)、圖9(e)分別為水平及豎直方向上白色像素的一維投影圖,圖9(c)、(f)為二值圖像上定位到字符的左右及上下邊界,圖9(c)為字符定位結(jié)果。
Fig.9 Precise positioning of characters圖9 字符精確定位
為充分驗(yàn)證基于改進(jìn)概率霍夫變換的字符定位算法的可行性和有效性,實(shí)驗(yàn)設(shè)計(jì)使用PaddleOCR 深度學(xué)習(xí)字符定位方法以及傳統(tǒng)的霍夫變換算法與本文算法進(jìn)行比較,實(shí)驗(yàn)對(duì)20 張低質(zhì)量表格圖像中2 460 個(gè)字符進(jìn)行字符定位,針對(duì)兩種算法的提取結(jié)果在字符定位精度和算法準(zhǔn)確率兩個(gè)方面進(jìn)行分析。
如圖10 所示,圖10(a)為原圖,圖10(b)為概率霍夫變換算法結(jié)合投影定位效果,部分表格框內(nèi)字符無(wú)法定位到,圖10(c)為PaddleOCR 文本檢測(cè)算法定位到的字符結(jié)果。由圖可知,當(dāng)表格框內(nèi)存在不清晰的字符或表格框內(nèi)字符之間間隔較大時(shí),無(wú)法準(zhǔn)確獲得字符位置,圖10(d)為本文算法定位到的字符結(jié)果,基本可以精確定位到全部字符。實(shí)驗(yàn)結(jié)果表明,本文算法對(duì)字符在低質(zhì)量表格圖像上的定位效果優(yōu)于PaddleOCR 文本識(shí)別算法。
Fig.10 Character positioning results圖10 字符定位結(jié)果
如表1 所示,概率霍夫變換算法定位到正確字符2 252個(gè),錯(cuò)誤字符108 個(gè),準(zhǔn)確率為91.5%;PaddleOCR 文本字符定位算法共檢測(cè)到正確字符2 398 個(gè),錯(cuò)誤字符62 個(gè),準(zhǔn)確率為97.4%;本文算法能定位到正確字符2 443 個(gè),錯(cuò)誤字符17 個(gè),準(zhǔn)確率達(dá)99.3%。實(shí)驗(yàn)結(jié)果證明,本文算法可以有效定位到表格字符,實(shí)現(xiàn)表格字符的精確提取。
Table 1 Comparison of accuracy of different algorithms in different images表1 不同算法在不同圖像上的準(zhǔn)確率比較
本文針對(duì)低質(zhì)量的表格文檔圖像字符提取問(wèn)題,設(shè)計(jì)了一種基于改進(jìn)概率霍夫變換算法的字符定位算法。本文提出的四鄰域灰度差異閾值法,相比于其他算法,能夠達(dá)到較好的二值效果。本文的字符提取算法在傾斜的圖像上校正效果較好。并且,該算法可以精確地定位到字符的位置,相比于PaddleOCR 檢測(cè)算法,字符提取準(zhǔn)確率達(dá)99.3%,且本文算法無(wú)需大量數(shù)據(jù)集訓(xùn)練模型,減少了算法的復(fù)雜度,提高了字符提取效率。由于本文算法是基于直線定位表格字符,針對(duì)直線定位效果不好的圖像,字符定位容易出現(xiàn)錯(cuò)誤,有待進(jìn)一步研究。