基于改進(jìn)概率霍夫變換的表格字符定位算法

張 倩，陳其浩，楊 碩

（山東科技大學(xué)測(cè)繪與空間信息學(xué)院，山東青島 266590）

0 引言

紙質(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ù)水平或垂直方向的投影，提出以樹的形式表示表格結(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］提出基于梯度霍夫變換的藏文手寫采樣表格檢測(cè)，該方法由于表格線被多次檢測(cè)，造成部分表格線重疊；張國(guó)福等［9］通過(guò)改進(jìn)概率霍夫變換算法提取直線特征，從而實(shí)現(xiàn)對(duì)電梯門狀態(tài)的實(shí)時(shí)監(jiān)測(cè)，在時(shí)間和準(zhǔn)確率上均有較大提升；邱東等［10］通過(guò)改進(jìn)概率霍夫變換算法，添加約束條件加以改進(jìn)，擬合出正確車道線，以實(shí)現(xiàn)對(duì)車道線的快速檢測(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)字符的精確定位。

1 圖像預(yù)處理

低質(zhì)量表格圖像的分析與識(shí)別首先需要對(duì)圖像進(jìn)行預(yù)處理，二值化處理是圖像預(yù)處理的關(guān)鍵技術(shù)，直接影響字符定位精度。目前，主要的二值化方法有全局閾值法和局部閾值法［12］，基于全局固定閾值法的最大類間方差法（OTSU 算法）［13］可以快速有效地確定類間分割閾值，但對(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ì)比。各類算法的二值化輸出結(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ì)比

2 基于改進(jìn)概率霍夫變換的表格線檢測(cè)

表格線的檢測(cè)精度直接影響到后期字符定位結(jié)果［15］。由于概率霍夫變換算法中霍夫空間的投票方式會(huì)造成直線的錯(cuò)誤檢測(cè)，本文采用改進(jìn)概率霍夫變換算法檢測(cè)表格線，在直線融合及去除誤提直線兩個(gè)方面添加約束條件，以獲得較準(zhǔn)確的表格線。算法原理如圖3 所示。

Fig.3 Algorithm flow圖3 算法流程

2.1 霍夫變換檢測(cè)直線原理

標(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 霍夫變換原理

2.2 概率霍夫變換直線檢測(cè)

經(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)，若不滿足返回步驟③；⑥根據(jù)線段的長(zhǎng)度及方向的線段排序，得到表格線位置信息。

2.3 概率霍夫變換改進(jìn)

針對(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ù)直線周圍像素特征去除誤提直線。如圖6 所示，其中圖6（a）為PPHT 算法誤提字符直線圖，具有直線特征的字符被識(shí)別成直線，圖6（b）為誤提直線去除后的結(jié)果圖，可有效去除誤提字符干擾線。

Fig.6 Removing interference line圖6 去除誤提直線

3 表格校正

對(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)表格線傾斜校正。

4 字符定位

通過(guò)前期對(duì)表格圖像的預(yù)處理、對(duì)表格線的提取以及對(duì)表格圖像的傾斜校正，可精確定位表格線。為了有效地提取表格字符，還需要對(duì)表格字符進(jìn)行粗定位和精確定位。

4.1 粗定位

根據(jù)表格的橫線與豎線的交點(diǎn)位置信息確定字符所在矩形框的4 個(gè)交點(diǎn)坐標(biāo)，即可粗略定位到表格字符的位置，如圖8 所示。

Fig.7 Table line tilt correction圖7 表格線傾斜校正

Fig.8 Rough positioning of characters圖8 字符粗定位

4.2 投影法精確定位

為了提高字符識(shí)別精度，在粗定位的基礎(chǔ)上進(jìn)行精確定位，本文通過(guò)投影法對(duì)字符進(jìn)行定位，以獲得字符的精確位置。

首先，對(duì)圖像從左到右及從上到下進(jìn)行遍歷，若滿足式（5），即得到字符的左邊界及上邊界。其中Cn為第n行白色像素個(gè)數(shù)，Cn+1 為第n+1 行的白色像素個(gè)數(shù)。

其次，對(duì)圖像從右到左及從下到上進(jì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 字符精確定位

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

為充分驗(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)確率比較

6 結(jié)語(yǔ)

本文針對(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)一步研究。