文档布局分析 Document Layout Analysis

0x00

对文本进行OCR前,必须分析和定义文档的逻辑结构。 例如文本块、段落、行的位置;是否有应该重建的表格;是否有“图像”“条形码等”。

文档布局分析 (Document Layout Analysis) 是识别和分类文本文档的扫描图像中的感兴趣区域(RoI, Regions of Interest) 的过程。阅读系统需要从非文本区域分割文本区域,并按正确的阅读顺序排列。将文本正文,插图,数学符号和嵌入文档中的表格等不同区域(或块)的检测和标记称为几何布局分析。但文本区域在文档中扮演不同的逻辑角色(标题,标题,脚注等),这种语义标记是逻辑布局分析的范围。

文档布局分析是几何和逻辑标签的结合。它通常在将文档图像发送到OCR引擎之前执行,但也可用于检测大型存档中同一文档的重复副本,或者通过其结构或图示内容索引文档。

0x01 最早的算法实现 docstrum

1993年,O’ GormanTPAMI中发表了自下而上的文档布局分析算法docstrum,首先将文档解析为黑白连接区域,然后将这些区域分组为单词,然后分为文本行,最后分组为文本块。

简单翻译了一下它的算法(english version):

算法开始的字母代表着原始论文中每小节的标题序号。原始论文中,每个小节的标题如下:

  • B. Preprocessing
  • C. Nearest-Neighbor Clustering and Docstrum Plot
  • D. Spacing and Initial Orientation Estimation
  • E. Determination of Text Lines and Accurate Orientation Measurement
  • F. Structural Block Determination
  • G. Filtering
  • H. Global and Local Lay-out Analysis
  1. B 预处理图像以去除高斯噪声椒盐噪声(某些噪声消除滤波器可能会将逗号和句号视为噪声,因此必须小心谨慎)
  2. B 将图像二值化
  3. B 将图像分割为黑色像素的连通分量(下文称 Symbol)。对于每个Symbol,计算边框和质心(bounding box, centroid)。
  4. C 对于每个Symbol,确定其k近邻,且k>=4。( O’Gorman在他的论文中建议将k = 5作为鲁棒性和速度之间的良好折衷。使用至少k = 4的原因是对于文档中的符号,两个或三个最接近的符号是在相同文本行上紧邻的那些符号。第四最近的符号通常在正上方或下方的一条线上,并且在下面的最近邻居计算中包括这些符号是很重要的。)
  5. C 每个Symbol的近邻对与两者质心的向量相关。如果为每对最近邻Symbol绘制这些向量,则可以得到文档的docstrum(下图)。通过来自水平的角度θ和两个最近邻居符号之间的距离D,创建最近邻角最近邻距离直方图
  6. D 使用最近邻角度直方图,可以计算文档的歪斜。如果歪斜较小,则继续下一步。如果不是,旋转图像以消除歪斜并返回步骤3
  7. D 最近邻距离直方图具有若干峰值,并且这些峰值通常表示字符间间距字间间距行间间隔(between-character, between-word, between-line)。
  8. D 标记每个Symbol较远的邻居,该距离在between-characterbetween-word的某个容差内。对于标记的每个最近邻居符号,绘制连接其质心的线段。
  9. E 通过线段连接到其邻居的符号形成文本行。对于文本行中的所有质心,可以使用线性回归计算表示文本行的实际线段。(使用线性回归,是因为文本行中Symbol的所有质心都不太可能是共线的。)
  10. F 对于每对文本行,可以计算它们对应的线段之间的最小距离。如果该距离在步骤7中计算的行间间隔的某个容差内,则将两个文本行分组到相同的文本块中。
  11. 最后,可以为每个文本块计算边界框,并完成文档布局分析。
    docstrum