王 萍，徐 鵬，張藝凡

基于筆畫識別的視頻圖片文字提取方法

王 萍，徐 鵬，張藝凡

(天津大學(xué)電氣與自動化工程學(xué)院，天津 300072)

通過對筆畫的對稱邊緣特點(diǎn)與文字幾何特征的認(rèn)識，根據(jù)二階邊緣檢測算子捕捉邊緣點(diǎn)亮暗變化趨勢的能力，使用高斯型拉普拉斯算子尋找“邊緣點(diǎn)對”，并構(gòu)建來自筆畫等窄帶區(qū)域的“對稱邊緣點(diǎn)對”樣本集．從樣本集的分布規(guī)律中自適應(yīng)地定出文字筆畫搜索窗的尺度及方向．利用最小生成樹算法實(shí)現(xiàn)由系列搜索窗得到的所有筆畫子區(qū)域的關(guān)聯(lián)聚類，通過剪枝、偽區(qū)域鑒別和閾值分割，將文字以行(含非水平行)或列的形式提取出來．實(shí)驗(yàn)表明，該方法對復(fù)雜背景下不同的語言類型、亮暗類型、文字行方向及文字尺度具有適應(yīng)性，在ICDAR數(shù)據(jù)集上的查準(zhǔn)率和查全率分別達(dá)到76%和75%．

基于內(nèi)容圖像檢索；文字筆畫提??；高斯型拉普拉斯變換；最小生成樹

近些年，日益增長的多媒體視頻引起了人們對于視頻信息自動檢索問題的關(guān)注[1]．視頻圖像文字提取首先定位出文字區(qū)域的位置，再通過分割的方法提取出文字進(jìn)而進(jìn)行文字識別[2]．就視頻圖像中文字區(qū)域的定位問題而言，一般有基于邊緣的方法、基于紋理的方法和基于連通區(qū)域的方法[3]．

更一般地，視頻圖像中的文字在語種、字體、尺度、顏色、文字的間距、分布等方面差異較大，分辨率不一定很高，因而許多研究者為此做了大量工作[4]，并在提高對多方向、多尺度及復(fù)雜場景的文字區(qū)域定位的適用性方面取得進(jìn)展[5-8]．

通過分析容易發(fā)現(xiàn)，文字筆畫具有寬度的相對平穩(wěn)性、其雙邊緣的平行性和多方向性，這3個性質(zhì)幾乎不隨語種、文字的排列方向以及文字尺度發(fā)生變化．筆者從這一特點(diǎn)出發(fā)，結(jié)合關(guān)聯(lián)聚類和局部區(qū)域的自適應(yīng)分割技術(shù)實(shí)現(xiàn)視頻圖像中的文字提?。?/p>

1 文字筆畫識別

1.1 筆畫的雙邊緣特點(diǎn)

在掃描圖像時(shí)，一旦遇到亮背景下的暗文字筆畫，均將歷經(jīng)一個由亮→暗→亮的過程．如果將由亮背景進(jìn)入暗筆畫的點(diǎn)稱為正邊緣點(diǎn)，則沿特定方向一定會在筆畫寬度之后出現(xiàn)由暗筆畫回歸亮背景的負(fù)邊緣點(diǎn)．

圖1為一幅包含單個文字的圖像，該圖像在文字高度h處沿水平方向的二階邊緣變換結(jié)果，其中，淺色點(diǎn)是米字圖中的正邊緣點(diǎn)，被圖中的負(fù)-正峰所包圍，深色點(diǎn)是米字圖中的負(fù)邊緣點(diǎn)，被圖中的正-負(fù)峰所包圍．本文特稱由文字筆畫寬度所限定的一個正邊緣點(diǎn)和一個負(fù)邊緣點(diǎn)為一個“對稱邊緣點(diǎn)對”，依文字和背景之間亮暗關(guān)系的不同可細(xì)分為“正-負(fù)型對稱邊緣點(diǎn)對”或“負(fù)-正型對稱邊緣點(diǎn)對”．

一般地，一個幾乎等寬度的筆畫一定存在著若干個“對稱邊緣點(diǎn)對”．如果用“點(diǎn)對”的尺度反映筆畫的寬度，連同它的類型和方向構(gòu)建一個3分量的向量，可形成對“點(diǎn)對”的樣本化描述，即視圖中的一對過零點(diǎn)p1和p2(一個“點(diǎn)對”)為一個樣本，記為u(p1，p2)．

圖1 一個圖像行的二階邊緣提取示例Fig.1 A detection result of two-order edge for a row in image

1.2 “對稱邊緣點(diǎn)對”的樣本描述

設(shè)圖像F在點(diǎn)p(x，y)的取值為f(x,y)，經(jīng)高斯型拉普拉斯變換后成為L(x,y)．在二階邊緣變換圖中，對任意邊緣點(diǎn)p0(x0,y0)一定滿足L(x0,y0)=0，且在其鄰域同時(shí)存在波峰P與波谷T，使得?x∈[x0-δ,x0+δ]，有T≤L(x,y0)≤P ，且?x1∈[x0-δ,x0]及?x2∈(x0,x0+δ]，有L(x1,y0)L(x2,y0)〈0．

由p0組成邊緣點(diǎn)集E，并將E劃分成亮集B與暗集D．在B中，L(x0,y0-δ)〉0或L(x0-δ,y0)〉0．在D中，L(x0,y0-δ)〈0或L(x0-δ,y0)〈0．

筆畫沿適當(dāng)?shù)姆较虮赝瑫r(shí)存在2個邊緣點(diǎn)滿足p1∈B和p2=D，它們組合成一個“對稱邊緣點(diǎn)對”樣本u(p1，p2)，其組合順序與文字筆畫的亮、暗類型如下：

(1) 暗背景亮字的筆畫邊緣樣本：B→D；

(2) 亮背景暗字的筆畫邊緣樣本：D→B．

將樣本u(p1，p2)構(gòu)建成一個三維向量，用來表示筆畫的寬度、筆畫的亮暗性及筆畫的方向，即

其中

1.3 “對稱邊緣點(diǎn)對”樣本的搜集算法

樣本的搜集算法步驟如下．

步驟1 按照由左及右、自上而下順序搜索圖像.

步驟2 若點(diǎn)p∈B，則以p為原點(diǎn)，依次沿水平、垂直、45°～-135°和-45°～135°方向做4條直線li，i=1，2，3，4；用這4條直線去搜索點(diǎn)p∈D．

步驟3 設(shè)定閾值TD，若用搜索線li由p經(jīng)TD沒找到點(diǎn)pi∈D，則記di為100，否則記di=p-pi．

式中：u1=dk；u2∈{0,1}；u3∈{0,1,2,3}．

1.4 基于樣本分布的自適應(yīng)筆畫搜索窗

構(gòu)建樣本的分布直方圖如圖2所示．該直方圖實(shí)際反映的是原始圖像中包括筆畫在內(nèi)的各種寬度的帶狀區(qū)域的分布，圖2(a)中的文字主要由2種寬度的筆畫組成，來自它們的“對稱邊緣點(diǎn)對”樣本分別在圖2(b)所示直方圖的1w和2w處出現(xiàn)顯著峰值．

設(shè)直方圖上每一個峰值均由來自筆畫寬度相近的樣本聚集而成，則筆畫搜索窗的確定方法如下．

圖2 “對稱邊緣點(diǎn)對”樣本關(guān)于筆畫寬度u1的分布直方圖Fig.2 Histogram of ‘symmetrical edge point’ sample set on u1

1.5 文字筆畫提取

首先在原始圖像上僅保留形成“對稱邊緣點(diǎn)對”樣本的像素點(diǎn)，按類(亮/暗)形成樣本分布直方圖后，再用筆畫搜索窗展開筆畫的分級搜索，具體步驟如下.

步驟2 遍歷圖像，若遇到非空點(diǎn)p，則遵循p點(diǎn)所屬樣本的特征u3確定搜索窗方向．

步驟3 若窗Wi中存在點(diǎn)p，則保留該窗口覆蓋的區(qū)域；否則，繼續(xù)搜索至圖像結(jié)束．

步驟4 取出用Wi得到的所有區(qū)域，同時(shí)將原圖中這些區(qū)域置為候選文字區(qū)．

步驟5 i→i+1，若i＞n，結(jié)束；否則，返回步驟2．

2 基于筆畫的最小生成樹聚類

2.1 最小生成樹

最小生成樹是圖論中的重要方法，對于一個多頂點(diǎn)的集合N={ni,i=1,2,…}，該方法能夠找到一個連接所有頂點(diǎn)的無回路子集T，其連接權(quán)重

最小，其中，w(nk,nl)為連接頂點(diǎn)nk和頂點(diǎn)nl的代價(jià)．定義區(qū)域C的內(nèi)部差異int()C為其內(nèi)部點(diǎn)間的最大歐式距離，即

定義區(qū)域Ci和Cj之間的差異Dif(Ci,Cj)為兩者內(nèi)點(diǎn)間的最小歐式距離，即

定義反映區(qū)域自身差異的閾值函數(shù)為

式中τ(C)=k′/int(C)，用于平衡2個區(qū)域的內(nèi)部差異，k′為經(jīng)驗(yàn)數(shù)據(jù)．

只有區(qū)域Ci和區(qū)域Cj間的差異小于閾值函數(shù)，即Dif(Ci,Cj)〈mint(Ci,Cj)時(shí)，2區(qū)域才能產(chǎn)生連接．

在上述定義下可得到所有區(qū)域塊的最小生成樹.

2.2 剪枝

由于文字中小的獨(dú)立筆畫和多行(或多列)情況的存在，文本采用了如下的剪枝步驟．

步驟1 當(dāng)某節(jié)點(diǎn)的連枝數(shù)1M=時(shí)，若相鄰節(jié)點(diǎn)的連枝數(shù)2M=，則該節(jié)點(diǎn)為文字行的端點(diǎn)，否則為較小的獨(dú)立筆畫點(diǎn)，簡稱小筆畫節(jié)點(diǎn)或葉子節(jié)點(diǎn)，端點(diǎn)加以保留，臨時(shí)去掉小筆畫節(jié)點(diǎn)．

步驟2 當(dāng)某節(jié)點(diǎn)的連枝數(shù)2M=時(shí)，該節(jié)點(diǎn)為普通節(jié)點(diǎn)，保留所有的普通節(jié)點(diǎn)．

步驟3 當(dāng)某節(jié)點(diǎn)的連枝數(shù)2M〉時(shí)，該節(jié)點(diǎn)為粘連點(diǎn)．設(shè)3M=，選出具有最大權(quán)重的連枝，將其斷開．

步驟4 拾回小筆畫節(jié)點(diǎn)．

圖3為來自兩行文字區(qū)域塊的最小生成樹及剪枝結(jié)果示意．

圖3 最小生成樹與剪枝結(jié)果示意Fig.3 Sketch of MST and pruning result

2.3 剔除偽區(qū)域

經(jīng)剪枝處理，一顆最小生成樹被剪成多棵子樹，這棵子樹所連接的各區(qū)域的聯(lián)合域Ω應(yīng)該是平直、長寬差異明顯、邊緣密度較大的．設(shè)這一聯(lián)合域的面積、長度、遠(yuǎn)對邊距、近對邊距及邊緣長度分別為S、L、Dl、Ds和Le，定義曲直度α、長寬比β、邊緣密度η分別為

當(dāng)且僅當(dāng)聯(lián)合域Ω的曲直度、長寬比、邊緣密度同時(shí)滿足α〉Tα,β〉Tβ,η〉Tη時(shí)，則認(rèn)為該聯(lián)合域與一行(或列)文字相對應(yīng)．

3 文字提取

由于在提取文字筆畫的過程中，依次保留的是一系列滿足條件的筆畫搜索窗區(qū)域．因此，可利用二值化閾值分割進(jìn)行文字提取，搜索灰度直方圖中2個波峰之間的波谷值，將其作為二值化閾值δ，且若域內(nèi)樣本屬于亮字類型(即u2=1)，則保留域中灰度值大于閾值δ的像素點(diǎn)．即對像素點(diǎn)p∈Ω，令

類似地，對于暗字類型(即u2=0)，令

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

4.1 與現(xiàn)有方法的對比

本文將所提方法與基于邊緣的方法[9]、基于紋理的方法[10]和基于連通域的方法[11]進(jìn)行了對比實(shí)驗(yàn)．

基于邊緣的方法主要利用文字和背景之間具有高對比度的特點(diǎn)來尋找文字邊界，該方法定位速度快，但面對復(fù)雜背景時(shí)，隨之產(chǎn)生的偽區(qū)域也較多[9].基于紋理的方法通過提取圖像的紋理特征來判斷像素點(diǎn)或像素塊是否屬于文字區(qū)域[12]．該方法在面對復(fù)雜背景時(shí)穩(wěn)定性較差、計(jì)算時(shí)間較長．基于連通域的方法通過顏色歸類和區(qū)域生長不斷把小區(qū)域合并，再根據(jù)圖像各部分的空間排列情況去除非文字區(qū)域、標(biāo)記文字區(qū)域邊界[11]．這類方法在當(dāng)文字顏色不一致或圖像對比度較低時(shí)，不易保證文字區(qū)域的完整性.

圖4給出了多組對比實(shí)驗(yàn)中的一個示例．從圖4可知，邊緣方法檢出了大量的偽區(qū)域，紋理方法稍好但仍存少量的偽區(qū)域，連通域方法對于復(fù)雜背景的文字提取最差，而本文方法對于帶有復(fù)雜背景的文本檢測獲得了不錯的效果．

圖4 與3種常用方法的對比Fig.4 Comparison between the method in this paper and the three existing methods

4.2 公共數(shù)據(jù)庫的運(yùn)行結(jié)果

本文進(jìn)一步采用國際上廣泛使用的ICDAR數(shù)據(jù)庫進(jìn)行測試[13]．該數(shù)據(jù)庫包含各類場景文本圖片251張．

將圖像中實(shí)際包含的文字塊數(shù)定義為ATB，在所有檢出塊(TDB)中，包含F(xiàn)DB個誤檢塊；進(jìn)而定義查全率R、查準(zhǔn)率Pc和f度量分別為

包括本文方法在內(nèi)的4種方法對ICDAR數(shù)據(jù)庫的運(yùn)行結(jié)果列于表1，圖5為本文方法的運(yùn)行示例，其中，本文方法所用閾值Tα=0.55，Tβ=0.45，Tη=0.60，f度量中α=0.5．

由表1中4種方法所得結(jié)果可知，對于ICDAR數(shù)據(jù)集而言，本文方法在查準(zhǔn)率、查全率和f度量上均獲得最大值，且平均運(yùn)行速度較快．其原因是：第一，“點(diǎn)對”的使用在二階邊緣檢測的同時(shí)濾去了大部分非筆畫區(qū)域；第二，“點(diǎn)對”的三維樣本描述支撐了自適應(yīng)筆畫搜索窗的生成及其對筆畫的定向提取，簡化了生成區(qū)域的計(jì)算量；第三，基于MST和筆畫特點(diǎn)的偽區(qū)域去除過程提高了提取的準(zhǔn)確率．

表1 基于ICDAR數(shù)據(jù)庫的方法對比Tab.1 Comparison between results given by four methods on ICDAR dataset

圖5 ICDAR數(shù)據(jù)庫的本文方法運(yùn)行結(jié)果Fig.5 Results of ICDAR dataset with the method in this paper

5 結(jié) 語

本文抓住組成各種語言文字的筆畫的共性，即幾乎等寬的帶狀區(qū)域存在著眾多的“對稱邊緣點(diǎn)對”，形成反映寬度、方向、亮/暗特征的樣本集．通過樣本集的分布自適應(yīng)地定出筆畫搜索窗．通過啟發(fā)式分級定向搜索以及關(guān)聯(lián)聚類與剪枝等技術(shù)的使用，比較成功地解決了在較復(fù)雜背景下，不限尺度、方向的文字提取問題．

［1］ Zhang Jing，Kasturi R. Extraction of text objects in video documents：Recent progress[C] // IAPR International Workshop on Document Analysis Systems. Nara，Japan，2008：5-17.

［2］ Michael S L，Nicu S，Chabane D，et al. Content-based multimedia information retrieval：State of the art and challenges[J]. ACM Transactions on Multimedia Computing，Communications，and Applications，2006，2(1)：1-19.

［3］ Keechul J，Kwang I K，Anil K J. Text information extraction in images and video：A survey [J]. Pattern Recognition，2004，37(5)：977-997.

［4］ Li Huiping，David D，Omid K. Automatic text detection and tracking in digital video[J]. IEEE Transactions on Image Processing，2000，9(1)：147-156.

［5］ Trung Q P，Palaiahnakote S，Chew L T. A Laplacian method for video text detection[C] //IEEE International Conference on Document Analysis and Recognition. Singapore，2009：66-70.

［6］ Katherine L B，Golnaz A，Mireille B，et al. A low complexity sign detection and text localization method for mobile applications[J]. IEEE Transactions on Multimedia，2011，13(5)：147-156.

［7］ Kim Wonjun，Kim Changick. A new approach for overlay text detection and extraction from complex video scene[J]. IEEE Transactions on Image Processing，2009，18(2)：401-411.

［8］ Shivakumara P，Trung Q P，Chew L T. A Laplacian approach to multi-oriented text detection in video[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(2)：412-419.

［9］ Liu Chunmei，Wang Chunheng，Dai Ruwei. Text detection in images based on unsupervised classification of edge-based features[C] //IEEE International Conference on Document Analysis and Recognition. Seoul，Korea，2005：610-614.

［10］ Palaiahnakote S，Trung Q P，Chew L T. A robust wavelet transform based technique for video text detection[C] //IEEE International Conference on Document Analysis and Recognition. Singapore，2009：1285-1289.

［11］ Anil K J，Yu Bin. Automatic text location in images and video frames[J]. Pattern Recognition，1998，31(12)：2055-2076.

［12］ Ye Qixiang，Huang Qingming，Gao Wen，et al. Fast and robust text detection in images and video frames[J]. Image and Vision Computing，2005，23(6)：565-576.

［13］ Simon M L. ICDAR 2005 text locating competition results[C] //IEEE International Conference on Document Analysis and Recognition. Seoul，Korea，2005：80-84.

(責(zé)任編輯：孫立華)

Text Extraction Based on Stroke Recognition in Video

Wang Ping，Xu Peng，Zhang Yifan
(School of Electrical Engineering and Automation，Tianjin University，Tianjin 300072，China)

According to geometric features of texts and the fact that character strokes have symmetrical edges，Laplacian of a Gaussian(LoG)was employed for finding the ‘symmetrical edge-point pair’，then the ‘symmetrical edge-point pairs’ sample set was constructed，therefore the scale and orientation of the detect window were determined by analyzing the sample distribution. The relational cluster of all character sub-regions was obtained by using the minimum spanning tree(MST)algorithm，then the text lines(including non-horizontal)were extracted in the form of lines or rows after pruning，false positive elimination，and threshold segmentation. Experiments show that the proposed method is capable of handling multilingual，different orientation and multi-scale images under complex background with a 76% precision rate and a 75% recall rate on ICDAR dataset.

content-based image retrieval；text extraction；Laplacian of a Gaussian；minimal spanning tree

TP391

A

0493-2137(2014)03-0200-05

10.11784/tdxbz201208001

2012-08-01；

2012-10-22.

國家自然科學(xué)基金資助項(xiàng)目(60865001).

王 萍（1955— ），女，教授，wangps@tju.edu.cn.

徐 鵬，ixupeng@163.com.