由 hiroi-sora 个人开发的，基于文本位置的版面分析/文本排序算法。适用于将OCR得到的文本块，按人类阅读顺序进行排序。特别针对多栏布局的报刊型排版。可能也适用于PDF解析等依赖版面分析的领域。
已内置于 Umi-OCR ，为文档识别等功能提供后处理支持。
演示效果：请查看下方大图。图中从左到右有四个部分：
- 原始OCR结果，存在一些错误排序，特别是无法区分不同列。
- 经过本算法，大部分文本块得以正确排序。
- 算法找出的竖切线（间隙）。
- 算法找出的区块，顺序为布局树的前序遍历。
“文本块”指的是包含空间坐标的一行文本的信息。如：
{
"bbox": (x0, y0, x1, y1), # 左上角、右下角坐标
"text": "这是一行文本",
}
通过OCR（光学字符识别）可以从图片中识别出大量文本块。但是OCR原始输出的文本块列表，往往只是按简单的规则进行排序（从上到下）。如果图片中存在多列文本，则在OCR结果中，不同列的块会交叉混杂在一起，与人类阅读顺序不符。
PDF解析也有类似的问题。PDF是固定布局，所有元素（如图片、表格、文本块）的位置被嵌入到文档中。同一段落之内，不同的行往往被分为不同的文本块。这使得难以编辑或提取连续的文本流，或者提取的文本块存在顺序错乱的情况。
因此，我们需要一种版面分析手段，将离散的文本块重新组织回 行、列、小节 的版面结构。或者至少按正确的顺序串联起文本块，将其恢复为连续的文本流。
版面分析是指对文档页面中的内容进行结构化分析的过程，其目的是识别和分类页面上的不同区域，如标题、列、行、图像、表格等。通过版面分析，我们能得到文本块之间的关联，从而进行排序或排版重建。
目前已有的版面分析技术，主要分为 图像分析 和 位置分析 。
先对文档的图片进行版面分析，将原始图片拆分为 [标题, 正文, 表格] 不同区块，再对每个区块进行提取文字。
可能包括使用边缘检测、纹理分析、连通区域分析、颜色分析等方法来区分文本和非文本元素，以及进一步识别出标题、段落、图表、图片等不同类型的内容区块。
现有基于图像的版面分析库，往往结合了深度学习，如 PP-Structure 。
优点：
- 经过充分训练的模型库，可以很好的理解图片中各个区块的逻辑关系，准确度高。
- 可以获取不同区块的类型（标题、正文、表格）。
缺点：
- 训练成本高：需要大量标注样本。
- 使用成本高：神经网络推理的性能开销较高，模型库、推理库占用空间大。
- 输入必须为图片。如果手上没有文档图片，只有文本块，则无法使用该方案。
先通过OCR或PDF，得到一组文本块。再根据文本块的包围盒位置信息，分析出布局或顺序。
一些PDF解析库，涉及了基于元素位置的规则匹配算法。如 pdf2docx 。
优点：
- 使用成本低：开销远比图像处理要小。
- 兼容性强：可以用在不同的任务流程中，比如不同的OCR组件、PDF提取等。
缺点：
- 如果没有额外信息，难以从位置中推断区块类型。
- 程序难以理解各个区块的逻辑关系，准确度低，或者容易出现误划分的情况。
这是一种对文本块位置进行规则匹配的版面分析算法。
简而言之：它搜索每一水平线上的文本块间隙，拼接为竖切线，将页面切割为不同的区块，将区块组织为布局树。最后，前序遍历布局树，即可得到符合人类阅读习惯的文本块排序。
优点：
- 支持 任意列数。
- 支持 列宽不一致。
- 支持 跨列区块。（如横跨左右两列的标题行）
- 在使用预处理器时，支持图片按任意角度旋转，支持竖排（视为90°旋转）。
- 参数极少，仅需提供文本块位置即可，无需额外的信息。
- 没有超参数（需要人工设定的阈值等），可自适应不同的情况。
- 对于区块数较少的常见布局，如1 ~ 2列：此时理想情况下能够接近线性时间复杂度O(n)。n为总文本块数。本文后面有证明。
- 鲁棒性强，即使因为噪声（OCR误划分）导致部分区块的排序错误，也能保证大部分文本块的排序是正确的。
- 实验代码
gap_tree.py中，仅使用了Python标准库，可以方便的用其它语言重写。
限制：
- 目前仅适用于标准横排或标准竖排阅读习惯，即：横排从左到右、从上到下；竖排从上到下、从右到左。
- 无法判断区块的类型，所有元素均视为正文。
- 算法中仅有“行”和“列”（即区块）的排版成分，无法辨别“章节”的成分。（章节指水平方向上多个列的组合）。如果章节存在跨列的标题行，则算法可以构建正确的布局树；否则可能构建出错。
- 同理，算法无法辨别表格。表格会被当成多个列来处理。
- 对于非标准排版（尤其是交错列，上下方的列不对齐），布局树构建错误的几率高。
不过，算法考虑到了即使在布局树构建不合理的情况下，排序依然有很大几率是正确的。原理
git clone 本仓库。
test.py 为测试入口，其中的 test_image 为测试图片路径。本仓库提供了一些测试样例（包括原图片和OCR结果json），可以直接使用。
- 如果你想用自己的样例，需要导入 RapidOCR-json ，或者用其它方式获取文本块。结果可视化工具可能不兼容你的块格式，如有报错请留意。
gap_tree.py 为主要算法模块。
preprocessing.py 是预处理器，让算法能够支持旋转、竖排等情况。
paragraph_parse.py 是一个简单的段内分析器。OCR后处理步骤之一，但不属于主要算法的范畴。
visualize.py 为结果可视化工具，需要Pillow库。
我用一个简单的案例来介绍本算法。实际的算法流程中，可能与下方步骤略有不同。实际可能将多个步骤压缩为一个以提高性能。
假设对一个带标题栏的双列布局图片进行OCR，拿到了原始结果：
① 设计模式在团队中的作用 |
|
② 从设计模式和面向 ③ 计，可以避免你的团队 |
④ 对象原则的视角讨论设 ⑤ 很快陷入实现的细节。 |
显然，文本块 ①~⑤ 只是按从上到下排序，不符合双栏布局的顺序。
将文本块按从上到下的顺序进行排序。（考虑到OCR结果本身已经从上到下排序，此步骤只需接近 O(n) 的时间开销）
然后从上到下遍历所有文本块，划分出不同行。划分依据可以是 两个文本块的水平投影有重叠。
注，划分行的策略，对总体结果有一定影响。目前实验代码中的划分策略可能不是最优的，待后续优化。
如下，划分出三行。【-->】
① ---------------> 设计模式在团队中的作用 |
|
② -------> 从设计模式和面向 ---> 计，可以避免你的团队 |
③ ---> 对象原则的视角讨论设 ---> 很快陷入实现的细节。 |
对于每一行，视为一个一维数轴，文本块是其中的线段。
求该行的“间隙”，即没有被线段覆盖到的地方。【==】
================设计模式在团队中的作用===============|
|
========从设计模式和面向=====计，可以避免你的团队=====|
====对象原则的视角讨论设======很快陷入实现的细节。====|
对当前在考虑的每一个间隙，检查与下一行的间隙的线段交集。
如果下一行的间隙与当前间隙不完全一致，那么要更新当前间隙，包括缩短、分裂、结束 等。例如：
当前间隙：| ================= ==== |
下行间隙：| ----- --------- |
更新后： | ===== ==== |
说明： ↑缩短 ↑分裂 ↑结束
记录经过每一行更新的间隙，我们可以得到“竖切线”。一条竖切线由多个连续行的、同一位置的间隙所组成，能“切分”不同列。【##】
#### 设计模式在团队中的作用 ##|
#### ##|
#### 从设计模式和面向#####计，可以避免你的团队 ##|
####对象原则的视角讨论设##### 很快陷入实现的细节。##|
根据所有竖切线，我们再次遍历每一行，将文本块划分到不同区块中。
每个区块可包含多个行的文本块。划分完成后，对每个区块内的文本块，从上到下进行排序。
如下，划分出 A B C 三个区块
#### AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ##|
#### AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ##|
#### BBBBBBBBBBBBBBBB ##### CCCCCCCCCCCCCCCCCC ##|
#### BBBBBBBBBBBBBBBB ##### CCCCCCCCCCCCCCCCCC ##|
将每个区块，作为树的一个节点。我们有了很多个节点，下面将这些节点连接成树。
遍历每个节点A，找父节点F，规则为：
- A 的右边界，必须包含在 F 的左右边界之内。
- A 顶部，低于 F 的底部。
- F 与 A 的垂直距离（行数）最近。
- 可能有多个F满足3的条件（底部在同一行），取最右的一个F作为父节点。
- 如果没有节点满足上述，则 A 的父节点为根。
节点均连接到父节点后，我们再遍历一次所有节点，将它的子节点按从左到右的顺序排序。
例如：
#### AAAAAAAAAAAAAAA【父：根】AAAAAAAAAAAAAAAAA ##|
#### AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ##|
#### BBBB【父：A】BBBB ##### CCCCC【父：A】CCCC ##|
#### BBBBBBBBBBBBBBBB ##### CCCCCCCCCCCCCCCCCC ##|
对于上述样例的树，前序遍历得到的节点序列为： L = [A, B, C]
遍历节点序列L，对每个序列，从上到下输出文本块，顺序为：
① 设计模式在团队中的作用 |
|
② 从设计模式和面向 ④ 计，可以避免你的团队 |
③ 对象原则的视角讨论设 ⑤ 很快陷入实现的细节。 |
显然，排序后的文本块 ①~⑤ 符合双栏布局的阅读顺序。
对于多栏布局或更复杂的非固定列布局，本算法也有较好的效果。
本算法是根据本人经验制定的一套规则，所以可能不是数学意义上的最优策略。但是，算法的部分环节仍然能解释其优越性。
对于多列布局，列（或者说，区块）的左右两侧必然存在空隙，区块的内部必然不存在空隙（不然就是两列了）。
竖切线的作用有两个：其一，从水平方向上约束一个区块的左右边缘。其二，从垂直方向上约束区块的上下边缘（上下边缘必然伴随着某条竖切线的开始或结束）。
因此，仅通过查找竖切线，无需其它信息，我们就能判断所有区块的上下左右边缘。
再看一遍规则：
- 子节点 A 的右边界，必须包含在父节点 F 的左右边界之内。
- A 顶部，低于 F 的底部。
- F 与 A 的垂直距离（行数）最近。
- 可能有多个F满足3的条件（底部在同一行），取最右的一个F作为父节点。
- 如果没有节点满足上述，则 A 的父节点为根。
按照人类阅读顺序，我们在读完一个列F后，首先向右寻找下一个列A。如果右侧存在列A，说明 F、A 是平行关系，属于同一个“章节”。因此，在布局树中，它们是兄弟节点，F不可能是A的父节点。
如果列F的右侧没有列，说明读完了当前章节，需要跳到下方，去下一个章节寻找新列。此时 F 可以下一个章节的列 A 的父节点。下一个章节中的列 A1,A2... 也是兄弟关系。将它们挂到F的子节点下，可以在前序遍历时，保证它们的顺序都晚于父节点F。
同时，对于 F→A1, F→A2... 来说，F永远在A的上方的最右侧。
部分情况下，布局树的节点可能位置不正确。比如：构建布局树中，节点B搜索父节点时，误没有匹配到应有的父节点A，而向上匹配到祖先节点F（因为匹配规则是向上兼容的）。如下所示。
F | F
↙ | ↙ ↘
A | A B
↙ |
B 正确匹配到父节点A | 错误，匹配到祖先节点F
但是，节点总体的顺序是正确的。与树的性质有关：上述两棵树的前序遍历顺序相同，都是F→A→B，因此B挂到A下 或挂到F下 是不会改变顺序的。
如果 B 节点下面也有子树，那么子树在全局的顺序也正确。
这个性质为本算法提供了很强的鲁棒性。即使OCR文本块划分出错，比方说没有识别到破折号，而将一行文本错误的划分为两行。这会导致布局树构建出错，原本的一个区块被划分为2 ~ 4个。但是这不会影响输出顺序，因为划分后的2 ~ 4个区块，在前序遍历中是紧密相连的，不会被别的区块所隔开。从顺序上看，划分后的2 ~ 4个区块依然表现为“1个区块”。
设文本块数量为n。通过下述的分析，我们得知：
极端情况下（每个文本块是一个单独节点），最坏时间复杂度为 O(n^2) 。
对于常见布局，时间复杂度为 O(n) 。
排序消耗 O(nlogn) 。考虑到OCR文本本身从上到下有序，则排序仅消耗 O(n) 检查一遍。
遍历文本块划分行，消耗 O(n) 。
主要开销是遍历所有行的单层循环。
假设有m行（必然有m<=n），则遍历所有行的开销 <= O(n) 。
这一步要遍历行及所有间隙。假设所有间隙数量为k（k<n）。
不管嵌套了多少层循环，总共考察了m行和k个间隙（不重复考察），总体复杂度 O(n) 。
实际上，第2、3步可以合并为一步。
遍历所有行的开销 <= O(n) 。
假设节点数为s（s<=n）。
两层循环，依次考察所有的节点对。最坏情况下s=n（每个文本块都是一个单独节点），复杂度为 O(n^2) 。
但是对于常见布局，我们可以认为节点数 s 是常数。比如对于标准双栏布局，不管n多大，布局树中都只有根节点+左右2个子节点。因此平均复杂度为 O(1) 。
同上，最坏为O(n)，平均为 O(1) 。
与第1步类似，由于每个节点内的文本块基本有序（从上到下），因此排序最坏消耗 O(nlogn) ，平均消耗 O(n) 。