二维图像分割之分式分割
从上周开始研究各种数学式子的切割，包括分式，竖式和脱式。本着由易到难的原则，开始做分式切割的调研。除了做PPT，写文档外，也将部分调研的结果整理成博文。
图像数学公式定位的关键问题
一般地，公式定位流程如下：
- 预处理：包括灰度化、二值化、去除噪声和倾斜矫正等步骤
- 统计版面参数：包括字符的位置、字符的尺寸和相邻字符间的间隔等
- 版面分析：标注出字符域、图像域、表格域和图形域等
- 行提取：对字符域以行为单位进行划分
- 定位孤立数学公式：从提取的行中区分孤立数学公式行
- 定位内嵌公式：从非孤立数学公式行中区分出含数学公式的文本行
公式定位基本算法
- 预处理：对图像灰度化、二值化、倾斜校正、去噪等处理，使其更有利于数学公式定位
数学公式字符块提取
1.行提取- 进行联通区域搜索，得到图片中所有连通区域
- 合并具有相交或包含关系的连通区域
- 根据连通区域宽高度统计直方图得到版面的字符宽、高度阈值
threshold_w和threshold_h，据此去除图片中的无关信息，得到公式的候选区域 - 根据候选字符的连通区域的位置关系，合并候选字符连通区域，提取本文行及相应参数：行间距
Line_d，行内相邻连通区域水平间隔平均值threshold_d
2.行内字符块提取:行内字符块提取是根据
threshold_d将文本中的字符连通区域合并成字符块
3.后处理：数学公式字符块合并。对于分式，若将分数线与分子分母分别切割，可以根据其上下相邻行为单字符或行内字符均处于具有二维运算结构的运算符作用范围内，且两者之间的垂直距离小于行距Line_d的特点将其合并。
图像倾斜的影响：当倾斜角增加时，数学公式定位准确率急剧下降。这是由于在数学公式定位算法采用连通区域空间位置关系特征提取文本行，很容易受到倾斜影响，进而影响公式定位准确性，因此首先需要对拍照图片进行测斜和校正处理，以确保公式定位算法的鲁棒性。
公式定位错误的校正方法
- 考虑根据图片中印刷体字符的大小，近似判断拍照的远近，从而确定各个阈值的大小
- 影响最大的参数有行内相邻连通区域的水平间隔
Character_dist,可以考虑将行内连通区域按从左到右排列，然后计算版面中相邻连通区域的间隔，取数量最多的连通区域间隔座位阈值Character_dist。对与行间距阈值Line_d也可以用类似方法
分式分割的难点
印刷体
对于印刷体分式，如下图，如同印刷体文本的字符分割算法一样。采取水平投影的方式即可找到分割线。
手写体
分式分割的难点主要集中再手写体分式上。手写体的格式没有印刷体那么规范，分子与分母经常会出现粘合，带分式中也会出现整数与分数线、分数粘合在一起的情况，因此无法直接通过投影拆分分式。
分式分割的处理思路
分式分割的关键点是找到分数线，分数线能作为带分数中整数与分数分割的参考，且能作为分数部分的分割线。因此分数线具有重要的参考价值。
考虑到手写体中分数线扭曲，各部分粘合的情况调研了许多直线检测的算法。有时间会做系统的整理。在这里线整理几种常用的直线检测算法。
霍夫变换
Hough是最经典也是应用最广泛的直线检测算法，hough使用极坐标的方式表示直线。极坐标下，直线的表达式可定义为：$\left(-\frac{cos\theta}{sin\theta}\right)x+\left(\frac{r}{sin\theta}\right)$，化简可得到$r=xcos\theta+ysin\theta$。对于每一点$(x_0,y_0)$，可以将通过该点的直线定义为$r_\theta=x_0cos\theta+y_0sin\theta$。
通过以上的推导，意味着每一对极坐标的参数$(r_\theta, \theta)$代表着一条通过$(x_0,y_0)$的直线。对于每个定点$(x_0,y_0)$，画出通过该点的所有直线并以极坐标表示，会得到一条正弦曲线。因此越多的点具有所描绘的正弦曲线相交，意为着这些点能组成平面内的一条直线。
如下图所示，点$x_1=9$,$y_1=4$，点$x_1=12$，$y_1=$以及$x_1=8$,$y_1=6$所描绘的通过它们的所有直线的正弦曲线。
hough的做法是追踪图像中每个点对应曲线间的交点，如果这些交点的数量超过了一点的阈值，即认为交点的参数$(r_\theta, \theta)$在原图像中为一条直线。
Hough变换的基本思想是利用图像的全局特征将特定形状的边缘连接起来，Hough通过点线的对偶性，将原图像中的点映射到用于累加的参数空间，将在原图像中寻找特定曲线的检测转化为寻找参数空间中的峰值问题。Hough的优点和缺点都来源于全局特征，因为全局特征，Hough提取的曲线受噪声和边界的影响较小，具有较好的鲁棒性，但也会带来效率低的缺点
LSD算法
LSD发表于2012年，算是较新的直线检测算法。与Hough利用全局特征不同，LSD是一种局部提取直线的算法，在线性时间(liner-time)内能得到亚像素级准确度的直线。
LSD算法的流程如下图，LSD算法的核心思想是合并像素生成直线，合并的规则是根据每个像素点的梯度值建立状态列表，并将所有点设置为NOT USED。然后去除列表中梯度最大的点作为直线的第一个点，并将对应的状态设置为USED。再基于区域生长算法，得到line support region。
上面说了Hough由于全局的属性带来的优缺点，下面也说说LSD这种算法因为局部提取直线带来的缺点。
LSD号称是一种无需设置任何参数的算法，但在实际使用中，需要设置采样率，并且区域生长算法中，需要设置梯度角度变化的容忍（tolerance ）值。
- 由于LSD算法的每个点都有状态值“NOT USED”和“USED”。因此每个点都智能属于一条直线，遇到相交直线时会出现至少一条直线被分割成多条直线的情况。
- LSD算法在找寻line support region时，用了区域生长算法的思想。会由于线段间的遮挡和局部模糊导致一条直线被割裂成多条。
由于是做手写分式分割中的分数线检测，直线往往弯曲而且易被其他线“切断”。因此做实验时，尝试将采样率与区域生长的容忍值调大了不少，让我困惑的是，在我将采样率和容忍值调大后，LSD算法的耗时呈大幅增长，失去了LSD算法的效率优势，这里暂时还不知道是我自己写算法的问题，还是LSD在增大局部搜索范围后效率会显著下降的原因。日后有了确切的结论会来更新，也欢迎大家指正。
下面贴几张LSD算法在分数检测的效果图，不同颜色的线段代表检测出的不同直线。可以看到对于扭曲小且没相交直线的情况下，LSD有较好的效果，而一旦干扰多了，一条直线会被分割成多条直线。
关于直线的论文有很多，还有使用图像分割或提取边缘算法得到图像边缘后，使用动态聚类算法聚合线段，再用直线拟合同一聚类中图像。
实验与结论
不得不说，手写分式可能出现各种各样的情况。例如无法有效判断检测到的那条直线为分数线，对于带分式中整数与分子分母贴合紧密的情况，也暂时没有有效的解决思路。
最近看了很多图像处理的论文以及思路，很多棘手的任务，论文作者都巧妙的用图像处理的算法解决了。相信关于分式分割的处理，也会有相应的解决办法。事情总是要一步一个脚印的处理。先贴一个图，下图是这周做的真分式和假分式的切割算法，在525张手写分式图片中，正确分割了512张，也算是达到了预期的效果。
参考文献
[1] 毛星云. OpenCV3编程入门[M]. 电子工业出版社, 2015.
[2] Gioi R G V, Jakubowicz J, Morel J M, et al. LSD: A line segment detector[J]. Image Processing on Line, 2012, 2(4):35-55.
欢迎关注我的公众号
