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