Fenrier Lab

如何检测出图片中的表格

通常,在我们使用 OCR 识别图片的时候,模型本身是无法知晓文档结构的,对于那些包含表格的文档,常出现的情况是识别出文字,但丢失了原有的表格结构。针对这一情况,我们来开发一个专门检测图片中表格的算法。

表格检测的具体思路很简单,考虑到表格是由多条线条构成的,因此我们可以首先把这些线条检测出来。在数字图像处理技术中,有一类比较经典的直线检测算法,被称为霍夫变换(Hough transform)。它的具体原理是利用直线极坐标方程

\[r = x \cos \theta + y \sin \theta\]

将 \(x-y\) 平面上的一个点 \((x_0, y_0)\) 变换成 \(\theta-r\) 平面上的曲线 \(r = x_0 \cos \theta + y_0 \sin \theta\)

也就是说,平面上的每个点,都对应着这样一条曲线。而我们知道,平面上的每个点有无数条直线穿过,那么也可以说,这些直线构成的簇对应着这样一条曲线。更进一步地说,由于这是 \(\theta-r\) 平面上的曲线,所以这条曲线上的每个点 \((\theta_0, r_0)\) 都对应着 \(x-y\) 平面上的一条直线

\[r_0 = x\cos \theta_0 + y \sin \theta_0\]

如果我们再在平面上找到另外一个点 \((x_1, y_1)\),然后画出它变换后的曲线

可以看到,这两个点的变换曲线有一个交点,显然,这个交点对应的直线就是经过 \((x_0, y_0)\) 和 \((x_1, y_1)\) 的直线。

现在,如果我们把 \(x-y\) 平面的一条直线上的所有点都变换到 \(\theta-r\) 平面上,则可以预见的是,这些曲线将全部相交于同一点。反过来想,假如我们把 \(x-y\) 平面上明显的点都不分青红皂白的全部映射到 \(\theta-r\) 平面上,然后找到这些曲线的所有交点,并统计相交的曲线数量,那么显然,有大量曲线相交的点对应的 \(x-y\) 平面上的直线就是我们要找的直线。

OpenCV 库为我们提供了 HoughLines 和 HoughLinesP 方法可以轻松实现直线检测。但距离我们的目标还差的远,以上图为例,我们使用如下代码检测图片上的直线,并绘制出来

img_canny = cv2.Canny(img, 50, 150)
lines = cv2.HoughLinesP(img_canny, 1, np.pi/180, 10, minLineLength=10, maxLineGap=2)

然而,该算法不仅检测出了表格线,还把部分文字中的线段也识别出来了,因此,接下来我们将想办法把这些误识别的线段给排除掉。

稍加观察可以发现,文字上的线段很多都是孤立的,另一部分是成团聚集在一个很小的区域,而表格线则阡陌交通,互相连接。也就是说,假如我们能将这些线段进行分类,把相互连接的线段归为同一组,那么就能根据每组线段的分布特征,来确定是不是表格线了。所以,现在的问题就变成了把相互连接的线段分到同一个组。如果大家熟悉图算法,可以立即联想到这其实是一个求图连通分量的问题。

将线段看作 Vertex,将相互连接的线段看作 Edge,那么这些线段就构成了一个 Graph。为了简单起见,我们使用邻接矩阵来表示此 Graph,生成邻接矩阵的方法很简单,对所有线段进行两两比较,如果两线段相连,则将矩阵的相应位置设为 1,至于如何判断两线段相连,我们后面再做介绍。

连通分量就是由所有能够相互连接的 Vertex 组成的子图,我们的任务就是找到所有的孤立子图,下面我们采用深度优先搜索来解决该问题:

  1. 初始化数组 visited,长度等于 Vertex 数量,全部设置为 0,标记所有访问过的节点;
  2. 初始化变量 compoent_id = 1,作为连通分量id;
  3. 声明一个空栈 stack 用于存储 Vertex id,然后将 0 入栈;
  4. 如果 stack 不为空,则循环: a. 将 stack 顶部的 Vertex id 出栈,然后查看邻接矩阵的相应行,如果该行的所有元素都为 0,则说明该 Vertex 是孤立的,将 visited 的相应位置标设为 component_id,然后 component_id 自增 1。如果该行含有非 0 元素,则将该行的所有非 0 位置入栈,并将 visited 的相应位置标设为 component_id,以表示它们属于同一个连通分量; b. 如果此时 stack 为空,则检查 visited 数组是否含有 0 元素,如果有,则将第一个 0 元素位置编号入栈,且 compoenent_id 自增 1。

下面给出算法伪码:

connect_components(neighbor_matrix):
  init: visited, compoent_id, stack = [0]
  loop while stack not empty:
   i = stack.pop()
   isconnect = neighbor_matrix[i]
   if isconnect all 0:
    visited[i] = component_id
    component_id += 1
   for j in position where isconnect != 0:
    visited[j] = component_id
   if stack is empty:
    push the first non-zero vistied index to stack
    component_id += 1

这样一来,visited 数组就包含了每个 Vertex 属于哪个连通分量的信息,对于每一个连通分量,我们找到它所占的矩形区域,然后计算该区域的面积,根据常识来看,表格的面积比其他区域的面积要大的多,因此可以将这些大面积的矩形区域作为表格位置。以10000作为面积阈值,检测的结果如下

最后,我们来看一下计算两条线段是否连接的方法,主要参考自该文档,该算法计算两条线段的最短距离,常用于碰撞检测,这里我们实现一个简化的版本就足够了。

我们令 \(p_0, p_1\) 为一条线段的起点和终点,\(q_0, q_1\) 为另一条线段的起点和终点,那么,这两条线段上的点的参数方程分别为

\[\begin{aligned} p = (1 - s) p_0 + s p_1\\ q = (1 - t) q_0 + t q_1 \end{aligned}\]

其中 \(s, t\) 为参数,取值范围为 \([0, 1]\)。这两个点间的距离可以表示为

\[r(s, t) = \|p-q\|^2\]

这里我们稍加变换

\[\begin{aligned} r(s, t) &= \|p_0 - q_0 + (p_1 - p_0)s - (q_1 - q_0) t\|^2\\ &=\|p_1 - p_0\|^2 s^2 +\|q_1 - q_0\| t^2 -2 (p_1 - p_0)\cdot (q_1 - q_0) st + 2(p_0 - q_0) \cdot (p_1 - p_0)s - 2(p_0 - q_0) \cdot (q_1 - q_0) t + \|p_0 - q_0\|^2\\ &= a s^2 + bt^2 - 2c st + 2ds - 2et + f \end{aligned}\]

其中

\[\begin{aligned} a &= \|p_1 - p_0\|^2\\ b &= \|q_1 - q_0\|^2\\ c &= (p_1 - p_0)\cdot (q_1 - q_0)\\ d &= (p_0 - q_0) \cdot (p_1 - p_0)\\ e &= (p_0 - q_0) \cdot (q_1 - q_0)\\ f &= \|p_0 - q_0\|^2 \end{aligned}\]

以上就是两条线段上任意两个点之间的距离公式,于是计算两条线段的最短距离问题就转化成了计算函数 \(r(s, t)\) 最小值的最优化问题

\[\min_{r, s \in [0, 1]} r(s, t)\]

现在,我们对 \(r(s, t)\) 求梯度,并令其为 0

\[\begin{aligned} &\nabla r = 0\\ \Rightarrow &\left( \frac{\partial r}{\partial s}, \frac{\partial r} {\partial t} \right) =0\\ \Rightarrow & (2as -2ct + 2d, 2bt -2cs -2e) = 0 \end{aligned}\]

求解可得

\[\hat{s} = -\frac{bd - ce}{ab - c^2}, \hat{t} = \frac{ae - cd} {ab - c^2}\]

首先容易看到,上述解没有考虑约束条件,如果最优解 \((\hat{s}, \hat{t})\) 位于 \([0, 1]\) 之外,那么就还需要考虑边界上的函数值,也就是以下几个函数的最优解

\[\begin{aligned} r(0, t) &= bt^2 -2et + f\\ r(1, t) &= b t^2 - (2c+2e) t + a + 2 d + f \\ r(s, 0) &= a s^2 + 2 d s+ f\\ r(s, 1) &= a s^2 + (2d -2c) s+ b - 2 e + f \end{aligned}\]

同样,对它们求导,并令其等于 0,可以得到最优解

\[\begin{aligned} t_0 &= \frac{e} {b}\\ t_1 &= \frac{c+e} {b}\\ s_0 &= -\frac{d}{a}\\ s_1 &= \frac{c -d} {a} \end{aligned}\]

这时,\(t_0, t_1, s_0, s_1\) 仍有可能落在约束区间之外,所以我们还需要计算曲线的最优边界值,即

\[r(0, 0), \quad r(1, 0), \quad r(0, 1), \quad r(1, 1)\]

另一方面可以看到,理论最优解 \(\hat{s}, \hat{t}\) 存在退化情况,即当 \(ab -c^2 =0\) 的时候失效。根据 \(a, b, c\) 的定义,也就是说

\[\|p_1 - p_0\|^2 \|q_1 - q_0\|^2 - ((p_1 - p_0)\cdot (q_1 - q_0))^2 = 0\]

根据拉格朗日恒等式

\[\|\mathbf{a}\|^2 \|\mathbf{b}\| - (\mathbf{a} \cdot \mathbf{b})^2 = \|\mathbf{a} \times \mathbf{b}\|\]

于是有

\[(p_1 - p_0)\times (q_1 - q_0) = 0\]

两条线段的方向向量叉积为 0,即两条线段平行。在这种情况下,无法得到 \(\hat{s}, \hat{t}\),只有通过边界上的函数值来求解。

总结来说,为了求解两条线段的最短距离,我们应该首先判断它们是不是平行线,如果不是,我们计算 \(\hat{s}, \hat{t}\),判断它们是否满足约束,如果满足,则最优解为 \(r(\hat{s}, \hat{t})\),否则,我们再计算后面的 \(t_0, t_1, s_0, s_1\) ,根据是否满足约束,分别计算 \(r(0, t_0), r(1, t_1), r(s_0, 0), r(s_1, 1)\),对于那些不满足约束的,再计算 \(r(0, 0), r(1, 0), r(0, 1), r(1, 1)\)。最后,比较所有满足约束的解,取最小值即可。而如果两条线是平行线,那么除了计算 \(r(\hat{s}, \hat{t})\) 外,按上述步骤也可以得到最优解。

本文遵守 CC-BY-NC-4.0 许可协议。

Creative Commons License

欢迎转载,转载需注明出处,且禁止用于商业目的。