基于有向单连通链的表格框线检测算法A.pdf

1000-9825/2002/13(04)0790-07 ©2002 Journal of Software 软 件 学 报 Vol.13, No.4 基于有向单连通链的表格框线检测算法 郑冶枫, 刘长松, 丁晓青, 潘世言 (清华大学 电子工程系,北京 100084) E-mail: zhengyf@; lcs@; dingxq@ 摘要: 表格框线检测是表格识别的基础.现有的表格框线检测算法或者速度慢,或者鲁棒性差, 而且没有充分利用 表格框线之间的约束信息.提出了一种基于所定义的图像结构基元“有向单连通链” 的自底向上表格框线检测算 法.在此算法中,有向单连通链是一种黑像素游程序列,作为非常合适的矢量基元,在引入一定表格框线约束信息 的条件下合并单连通链,有效地去除伪框线,补全断裂的框线,提高了算法的鲁棒性,可以准确而快速地提取表格 框线.通过滤除噪声单连通链,加快单连通链的合并速度,算法速度提高了 3~ 10 倍,满足了实用要求.实验证明,该 算法具有速度较快、鲁棒性高、抗任意角度的倾斜、抗断裂等优点. 关 键 词: 表格识别; 图像分析;直线检测;OCR(光学字符识别);智能文档处理 中图法分类号: TP391 文献标识码: A 表格是一种很常见的文档形式.它作为一种高度精炼、集中的信息表达手段, 以其简明、规范、便于填写 和处理等特点,被广泛地应用在国民经济和日常生活的各个方面.表格的自动输入、存储、管理已经成为文档 智能处理领域的一个重要组成部分. 表格由一些有一定约束关系的横线、竖线和少量的斜线组成.为了构成表格单元,直线之间存在相互约束 关系.我们称表格中这种相互之间存在约束关系的直线为表格框线, 以区别一般的直线.直线检测是图像分析领 域中最基本的、不断研究探讨的问题之一.其中较为成熟的算法是 Hough 变换以及繁多的快速算法[1] .虽然 Hough 变换作为一种全局的检测方法,对线段的连通性没有要求,有利于检测虚线和断裂的直线.但由于难以确 定直线的起点和终点,运算量过大,它在具体的工程实践中的应用却受到了限制.表格中的框线绝大多数集中在 水平和垂直两个方向,这提示我们可以将Hough 变换中(ρ,θ)空间的θ分量的有哪些信誉好的足球投注网站范围大大地减小,从而大幅度地 减少运算量.这种特殊的 Hough 变换等效于实际中经常使用的投影算法[2].但投影法不能提取斜线,而且抗图像 倾斜的能力有限,当图像出现较大角度(大于5°) 的倾斜时,算法就会失效. 矢量化算法(vectorization)是另一类应用较广的直线检测算法[3~5] .直接对光栅图像的各个像素进行处理,存 储量大,而且因为不能利用像素间的位置关系,很不方便.而矢量化过程作为目标识别的预处理过程,将输入的 光栅图像转化成矢量基元( 比如直线段、圆弧段等等).它一方面使处理对象由像素变成矢量基元,数目下降一个 数量级,另一方面选择合适的矢量基元可以使后续的目标识别过程转化成较简单的矢量基元的生长、合并过 程,难度大大降低.因为矢量基元的选择决定了目标检测算法的性能,所以它必须容易提取,大小合适,反映待检 测目标的最本质的特性.我们构造了一种称为“有向单连通链” 的图像结构作为直线检测的矢量化基元,它具有 定义简单,物理意义明确,易于检测、存储和处理等优点.在一定约束条件下合并有向单连通链,可以快速、准确 收稿日期: 2000-05-11; 修改日期: 2000-10-09 基金项目: 国家自然科学基金资助项目; 863 高科技发展计划基金资助项目(863-306-ZT03-03-1) 作者简介: 郑冶枫(1975−),男,浙江江山人,硕士,主要研究领域为文本图像处理;刘长松(1969−),男, 山东文登人,讲师,主要研究 领域为图像处理,模式识别,智能信息处理;丁晓青(1939−),女,江苏雎宁人,教授,博士生导师,主要研究领域为图像处理,模式识别,智能 图文信息处理;潘世言(1973−),男,安徽桐城人,博士生,主要研究领域为图像处理,模式识别. 郑冶枫 等:基于有向单连通链的表格框线检测算法 791 地提取直线.单连通链的合并结果还有少量的错误.一类是字符笔划的误合并, 即存在“伪”直线;一类是直线断 裂.表格框线约束信息的引入可以帮助去除伪直线,补全断裂的直