更新于：2024-12-17
一、背景
当使用 layout 算法分析出版面区域时，识别的区域如果按从上到下、从左到右排序的话，可能会出现与人类阅读顺序不符的场景。以论文这类多栏文档为例，简单的排序会导致不同列的区域混合在一起，导致提取出来的文本内容出现上下文不对应问题。
因此需要一种版面区域排序算法，将离散的元素区域组织成 行、列、页 的版面结构。保证元素间的文本内容连续。
二、区域排序算法
这里介绍一个 github 上面开源的工具 GapTree_Sort_Algorithm ，这是一种对文本块位置进行规则匹配的版面分析算法，它搜索每一水平线上的文本块间隙，拼接为竖切线，将页面切割为不同的区块，将区块组织为布局树。最后，前序遍历布局树，即可得到符合人类阅读习惯的文本块排序。
该算法可以帮我们解决上面章节提出的问题，另外个人测试在多栏文档类型上效果很好。
from gap_tree import GapTree
text_blocks = [{"bbox": [235.44, 73.77, 359.76, 85.77], "score": 0.95, "text": "像环境配置 。如果条件"}, ...]
gtree = GapTree(lambda tb: tb["bbox"])
sorted_text_blocks = gtree.sort(text_blocks)
nodes_text_blocks = gtree.get_nodes_text_blocks()
上面提供简单的样例，使用起来非常方便，接下来我们通过仓库的 README 描述来讲解一下算法的逻辑步骤。
- 1.划分行：将元素区域按从上到下的进行排序，并遍历所有区域，划分出不同行；划分依据是基于两个文本块的水平投影有重叠。
- 2.求间隙：对于每一行，视为一个一维数轴，元素区域是其中的线段，并求出该行的间隙（即没有被线段覆盖到的地方）。
- 3.求竖切线：对当前在考虑的每一个间隙，检查与下一行的间隙的线段交集；如果下一行的间隙与当前间隙不完全一致，那么要更新当前间隙（包括缩短、分裂、结束等）。
- 4.求区块：根据所有竖切线，再次遍历每一行，将元素区域划分到不同区块中；每个区块可包含多个元素区域，划分完成后，对每个区块内的元素区域从上到下进行排序。
- 5.生成布局树：将每个区块，作为树的一个节点，基于相关规则，将所有节点构建成一颗多叉树。
遍历每个节点A，找父节点F，规则为： 1. A 的右边界，必须包含在 F 的左右边界之内。 2. A 顶部，低于 F 的底部。 3. F 与 A 的垂直距离（行数）最近。 4. 可能有多个F满足3的条件（底部在同一行），取最右的一个F作为父节点。 5. 如果没有节点满足上述，则 A 的父节点为根。 6. 节点均连接到父节点后，我们再遍历一次所有节点，将它的子节点按从左到右的顺序排序。 - 6.前序遍历布局树：基于前序遍历，得到数节点序列。
- 7.整理文本块排序：遍历节点序列，得到按人类阅读顺序的元素区域排序。
三、总结
在文档解析中，通过版面区域排序算法解决多栏文档文本提取时的上下文不连贯问题，通过开源的GapTree_Sort_Algorithm的排序算法来解决这类问题，确保阅读顺序符合人类习惯。
