Date: 2020/09/30
Coder: CW
Foreword:
该项目来自于一个初创公司的需求，业务场景是自动检测学生在格子作业本上写的字是否越界超出了格子，他们自己的团队已经实现了OCR算法可以定位和识别字体，因此我这边需要做的是定位出每个格子的位置，最终结合起来从而满足他们的业务需求。
如今项目已交付，CW打算对项目进行复盘，目的是通过回顾整个开发过程，总结下本次经验，对之后的开发工作起借鉴作用。同时，揪出其中做得不足的地方，记录下来方便日后深入研究以提升自己。
项目背景
相信大家在学生时代（没上过学的就自觉飘过吧~）都有在格子作业本上写过作业，格子作业本即每张作业纸都是由一个个格子组成的，你要把每个字写在格子里，但很可能一不小心就容易将有些字的笔画写出了格子外（和格子的边框有交点）。现在老师们需要检查学生写的每个字是否有超出格子的现象，可想而知，这人力成本也太高了（估计老师眼都要瞎了..）因此客户希望能通过自动化方式完成这项任务。
资源
数据：客户提供10张左右的学生作业样例图片；
开发人员：孤独的CW；
其它：开发过程中客户可配合测试
观察数据
真够“节俭”的，在大数据时代仅有10张照片作为开发资源，也是醉了。但作为堂堂大丈夫的CW，不能娇气，10张就10张吧，把它的作用发挥到极致！
观察下照片，我觉得是用户用手机拍的，和客户确认过确实是，拍摄角度任意、照片质量不一、格子大小、宽高比、颜色都不统一，而且格子和字体混在一起，没有纯空白格子的照片：
构思
刚接到项目需求时，我第一反应是将其看作深度学习的detection任务，可使用监督学习，基于大量的格子图片来训练模型，从而让它学会甄别格子的特征并且定位出位置。但是，现实是残酷的，我仅有10张照片，于是这个想法应该是行不通了。
既然Deep Learning的方式不行，那么就只有使用杠杠滴传统图像算法了。怎么做呢？首先，我的目标是定位格子的位置，照片中的字体是我不关心的，所以我希望把它们区分开；接着，由于格子都是由横线和竖线构成的，那么我应该要实现横竖线的检测；然后，综合这些线的交点就是格子的顶点；最后将这些顶点按坐标位置排序，组合成一个个格子的位置。
在正式开工前，我对这个项目的实现思路大致如上。
实现方案
统计灰度直方图
我期望能够通过像素值区分不同的目标，理想状态下，我认为格子线在一个分布，字体和其它无关因素在另一个分布中，为了验证我的猜想，于是我进行了灰度直方图统计。
然而，可以看到结果并不如我所期待的那样，因为如果格子线和字体的像素差异大，那么直方图应该至少是呈双峰分布。
二值化
虽然我不能通过像素值分布很好地区分开字体和格子，但是对图像进行二值化还是有必要的，毕竟除字体外，图像本身也会有一些杂质干扰。
二值化的方式也有多种，由于灰度直方图分布不是呈双峰，因此大津法（OSTU）的效果通常不好（我也实验过，确实是）。先是尝试了基于全局二值化，也就是全局都使用同一个灰度阀值，但是这种规则过于hard，如果将图像分成一个个小块(patch)，很难使用一个阀值使得每个patch都有很好的二值化效果。因此经过对比实验，最终使用了自适应局部二值化，这种方法能够基于每个局部窗口内的像素自动计算出阀值，从而使每个局部块都达到二值化效果。
你可能会吐槽我这二值化效果做了好像等于没做，很多空格子内部还残留有白色噪声，是的，仅仅基于二值化这个维度来评估确实是这样，但是我实验过，如果你对某张图做到了完美二值化，那么在其它图像上的表现可能就不好，会“误杀”掉其它图像中的格子线，即便这里使用的是自适应局部二值化，但还是有其固定的参数，这个参数对于各张图像都是共用的。因此，为了尽可能召回更多的格子线，在二值化这个维度上只能有所牺牲。
边缘检测
如上所述，从二值化这个维度上来看，效果并不好，于是我还尝试了边缘检测，直觉地看来，边缘检测貌似更有可能将字体与横竖线分开。经过实验，边缘检测很难在所有图片中都达到鲁棒的效果，有些图片可能好，而其它可能很差（有些格子线检测不出来）。另外，进一步在边缘检测后的图像上做横竖线的检测，效果也没有在二值化的基础上好，于是也就放弃了这个做法。当然，我这里使用的是Canny边缘检测，没有尝试过其它方法，所以这条思路日后还是可以再尝试下的。
直线检测
顺着之前构思的方案，我需要在二值化图像中检测横线和竖线。如何实现呢？利用形态学方法，进行开运算，也就是先腐蚀后膨胀，先腐蚀能够过滤掉直线以外的无关因素，后膨胀是为了还原出被误腐蚀的直线部分。当然，这么想来闭运算也是有可行性的，即先膨胀再腐蚀，我也尝试了，经过实验对比，发现还是开运算的效果好。
另外，在开运算的基础上，我还额外增加了一次膨胀，这在视觉效果上就是加粗了直线，这样做是因为用户拍摄的照片质量不佳，有些格子线会显得比较浅。经过实验，这个操作确实能够召回更多的格子。
检测横线和竖线的原理相同，但是实现方式有点小差别。检测横线的时候，将腐蚀用的核高设为1；而检测竖线时则将核宽设为1。分别获得横线和竖线的二值图后，将两者相加，综合起来得到格子线。
可以看到，效果并不完美，部分格子内的笔画也被保留了下来。是的，这个一方面是因为先前二值化的效果就不好，而这个检测是在二值化的基础上做的，因此这样的效果也有一定必然性。另一方面，虽然通过调整形态学的参数可以达到较好的效果，但是效果不鲁棒，换一幅图这个参数就可能不适用了，同时也有可能误杀格子线。而我的目的是，在不误杀格子线的前提下尽可能的过滤掉无关因素，而没被滤掉的无关因素我后续再用别的招对付它们。
轮廓检测
先前构思实现方案时，我预期是直线检测后能够完美过滤掉格子线意外的因素，但是从现在的效果看来是做不到了。由于直线检测后我获取到的不仅仅是格子顶点，还包含了部分字体的笔画，因此这部分我一定要干掉它！既然在像素值层面上无法实现，那么从几何图形学上去入手是否可行呢？毕竟我的目标，也就是格子，是一个个矩形，而这些笔画是构不成规则图形的，它们是散乱的，不封闭的曲线。因此，在直线检测之后，我对图像进行了轮廓检测。
我要找的是格子，那么它是怎样的轮廓呢？首先，它是封闭的矩形，有4个顶点；其次，它的尺寸和宽高比都有一定规律，格子大小通常不会占整幅图太大的比例，宽高比接近1:1，也就是方形。基于这些先验知识，我检测出了一些矩形轮廓，但是同时很多格子没被检测出来，通过调试我发现限制目标轮廓一定要4个顶点这个要求太“苛刻”了，导致很多格子都无法被召回。于是我放宽了限制，把顶点数不超过8个的封闭曲线轮廓都保留了下来。
现在，我几乎检测出所有格子了，但比起缺漏的格子，还是有其它毛病更令我不舒服。比如在大格子内的一些小格子和形状大小明显不“合群”的小格子，这些格子通常是由于字体笔画构成的，它们并不是真正的格子；还有一些“离群”的误检，比如上图偏右下角的那位“靓仔”..
它们令我十分不爽，于是下一步我决定要3杀！
NMS（非极大值抑制）
要干掉大格子内的小格子，第一反应就是NMS了，简单易实现。但是，NMS有个重要前提就是要将这些格子基于一定规则进行排序，让格子之间有优先级，每次选取优先级最高的保留下来，然后剔除和这个格子重叠度高的其它格子。于是问题就来了，如果你的排序算法设计得不好，使得那些误检的小格子排在真格子前面，那么真格子反而就被无情地干掉了..因此，NMS这部分效果的关键在于格子排序算法的设计。
那么如何设计呢？从目标出发，我们希望越靠左上方的格子排在越前面，并且位置相近（有重叠部分）时，大格子要排在小格子前。我总结为：行优先，列其次，最后看规格。
具体来说，我是这么做的：在对两个格子进行比较时，我先统计了它们的宽、高均值，这里分别记为w、h。如果它们左上角的纵坐标之差在一个单位h内，则认为它们在同一行；否则，纵坐标小的就可以排在前面了，因为上一行当然在下一行格子前面嘛~
若它们被认为是同一行，那么接着比较左上角的横坐标，如果差距超过半个单位w，则认为它们处于不同的列，那么横坐标小的排前面；否则，认为它们相互重叠；
最后，如果它们被认为是相互重叠的，那么面积大的排前面，以便NMS时剔除的是误检的小格子。
另外，相比标准的NMS，我还做了些改动，就是在计算IoU时将并集的面积改为两两比较时较小的格子的面积，这样分母就会变小，导致IoU变大，在同等阀值下相当于加大了惩罚力度，对“重叠度”的要求更苛刻。之所以这样改是通过实验发现这种做法能够清除更多的误检小格子。
基于统计值的排除法
经过前面那步，我把大格子内冗余的小格子干掉了，但是不在大格子内的、离群的误检小格子还在，因此，这一步我需要将它们一并扫掉。
怎么做呢？我就想啊，经过我前面的一系列处理，在所有格子中，这些小格子相比于真格子来说是占少数的，它们的大小、宽高比以及所在位置相对于对应的全局统计均值肯定会偏离得较远。于是，在上一步的基础上，我统计了所有格子宽、高的均值，若某个格子的宽、高与对应的均值相差超过一定阀值，我就认为它是误检，从而排除了部分小格子。
可以看到，经过以上操作，我几乎把所有误检的小格子都扫除了。
另外，还剩有部分“离群”的格子，它们的大小和宽高比和真格子十分接近，唉，真是讨厌！于是，我们只能基于位置信息来干掉它们。
首先，我重新统计了下所有格子的宽、高均值（因为刚排除了一部分，重新统计后会更接近真值），分别记为w、h。若某个格子在左右两边半个单位w内都没有其它格子或者在上下两边1个单位h内也没有其它格子，那么就认为它是离群的。之所以宽度是半个而高度是一个单位，是因为同一行的格子通常是依次相接的，所以半个宽度足以判断出是否离群。
可以看到，那个离群的“靓仔”终于消失在这条街上了！
就以上这幅图，总共20x20=400个真实格子，从轮廓检测初步检测出格子至今排除误检，统计了检测出的格子数变化如下：
i). 轮廓检测：421；
ii). NMS后：404；
iii). 排除大小和形状奇葩的格子后：333；
iv). 剔除离群的“靓仔”后：332
看到以上格子数的变化你可能会感到奇怪，第ii)步之后格子数明明已经非常接近真值了，怎么之后反而偏离那么多了呢？但是你要知道，ii)之后其实有很多都是误检的格子在其中充数，它们并不是真正的格子，也就是说还有许多真格子未被检测出来（如上最后一幅图所示）。
目前我已经排除了异常，于是接下来要做的当然就是想办法把缺失的格子补齐咯！
行归并
如何补齐格子呢？我当时看着图片久久发呆..片刻后，我观察到格子缺失的情况几乎都是这样：每行都检测出有格子，但是同一行的两个格子之间缺了几个格子，那么我好像可以基于格子的大小以及这两个格子的位置将中间缺失的部分补齐。我决定顺着这条思路走下去，但是在这之前我需要将格子归并成不同行，然后基于每行去操作。
首先将目前检测出来的格子进行排序，排序的优先级是左上角纵坐标（决定了所在行）>左上角横坐标（决定了所在列），这样排序之后，上一行就会排在下一行前，前一列会排在后一列前。
接着，由于照片拍摄角度的原因，成像后同一行的纵坐标并不是相等的，通常会相差几个像素，但也不至于差距太大。于是，若相邻两个格子的左上角和右下角纵坐标均相差不超过半个单位的格子高度（这个高度我使用的是这两个格子的均值），则认为它们在同一行；否则，就说明到了下一行，将当前行的格子保留起来，使用一个新的序列来准备保存下一行格子。
这样之后，我就区分出了各行格子（以下是输出的相关日志）：
Total 20 rows of 332 grids
补齐各行中间的格子
分出各行格子后，是时候实现我的想法了。首先，我将各行格子按左上角横坐标（决定所在列）进行排序，使得前一列排在后一列前。接着我统计了格子宽度的全局均值，记为w；然后递归处理各行格子，若前后两个格子之间的距离超过了半个单位w，那么就认为中间漏检了格子，需要补齐。最后，结合前后两个格子的位置使用插值的方法进行补齐，但是注意有可能会“补过头”，也就是补的最后一个格子越界到后一个格子了，于是在补齐时需要对格子右边的横坐标进行限制，最大不能超过后一个格子左边的横坐标。
After padded in the middle, there are 387 grids
可以看到，各行中间漏检的格子都被补上了。通知打印的日志可知，总共补了387-332=55个格子。
补齐各行首尾的格子
各行中间的已补齐，那么接下来理所当然就是要补齐首尾缺失的格子了。怎么做呢？每行缺的格子数不同，各行该补多少？补的话行首补多少？行尾又补多少？要确定这些因素，我必须以一行作为参考，该行不作改动，其它行以它为参考进行补齐。
那么如何选取这个作为参考的行呢？我使用了以下2个标准：
1). 该行格子数最多；
2). 在满足1)的同时该行格子的横坐标范围最“宽”
对于第2)点，也就是在所有行中，这行行首格子的左边横坐标最小、行尾格子的右边横坐标最大。
基于以上标准选出作为参考系的行后，对各行依次进行补齐，具体做法是：先计算该行格子数与参考行的格子数之差，得出要补齐的总格子数；然后，先往行首方向补，直至补到行首左边横坐标与参考行行首左边横坐标相近（我这里设置为半个格子均值宽度内），每补齐一个记录下目前补的个数，这样行首补完后剩下的就是往行尾方向需要补的个数；最后，往行尾方向补，直至行尾右边的横坐标与参考行行尾右边的横坐标相近（我同样设置为半个格子均值宽度内）。这整个过程都是使用插值的方法来计算要补的格子的位置（坐标）。
另外，为了避免一时兴起“补过头”，在所有行都补完后我还进行了一次NMS，滤除冗余框。
After padded at the edge, there are 400 grids
NICE! 可以看到，缺失的格子都补齐了，也就是说，我已经将所有的格子都检测出来了！不多不少，恰到好处。
校正横坐标
虽然目前已经检测出了所有格子，但是还不完善，我在测试中发现基于以上步骤检测出来的格子位置不太准确，有时候相邻格子之间会出现小间隙，然而真实的情况是，相邻格子间依次紧密相接，也就是说同一行中，前一个格子的右边和后一个格子的左边是重合的。
基于上述事实，我觉得必须做优化——对检测出来的各行格子进行横坐标调整，使得相邻格子间紧密相接。那么在调整的时候，我应该调整前一个格子的坐标还是后一个呢？考虑了片刻，我决定调整形状与标准格子相差较大的那个格子，这里的形状用宽高比来作衡量（通常格子是方形，宽高比接近1）。但是，通过实验发现，直接这样做效果并不好，调整后的格子的宽度可能会与标准宽度（可用该行格子宽度的众数或所有格子宽度的均值替代）相差太大。于是，在调整前，我加入“预览”功能，即先试着计算调整后格子的宽度，若与标准值相差太大，那么我就不仅仅调整这个格子，而是对相邻的两个格子都进行调整，调整的幅度为两者间隙的一半。
透视变换
在前文“观察数据”那部分我已阐述过，提供的数据是用户随意用手机拍摄的照片，有不同程度的倾斜现象，因此，实际上我要检测的格子并非由标准的水平线和竖直线构成，也就是说照片中的格子会是形状各异的四边形，那么基于我上述的步骤实现的检测效果就不会太好。然而，如果我重构整个方案，再去想一套逻辑来覆盖这个场景未免成本太高。
经过测试，我发现我的方案对于正常不倾斜扭曲的照片效果还是不错的，那么我可以在进行格子检测前先对图片做校正，使用透视变换的方法将倾斜扭曲的图片校正为水平和竖直对齐的标准照片。
但是，透视变换需要有先验的四个对点坐标，利用它们之间的映射关系计算出转换矩阵，最终才能实现透视变换。经过和客户的协商，他们同意这种做法，至于点的坐标，到时候他们会设计个交互界面由用户给出，我这边只负责实现透视变换即可。
使用和不使用透视变换的效果对比如下：
可看到，不使用透视变换的话，检测出来的格子位置会有偏差，而先进行透视变换再做检测效果就会好很多。至此，我整套方案的实现已经阐述完毕，当然其中还有些细节我就不在此处披露了。
思考
整套方案看下来，你可以发现，各个步骤之间的耦合性有点强，也就是下一步的效果很大程度上依赖于上一步的效果。
补齐格子
最明显的当属补齐格子这个流程，这个流程先补齐各行中间的格子，后补齐行首和行尾的格子。若有其中一行在前面的步骤中没有检测出任何格子，那么就不会对该行进行补格子。另外，在补齐行首、行尾的格子前，需要选取一个“参考行”，其它行以该行为标准来进行补齐，若在前面的步骤中没有一行是将其所在行的所有格子都检测出来的话，则选取的“参考行”本身就是没有检测完全，这样其它行也就补不齐了。因此，如果是在基于前面步骤的检测效果上进行格子补齐，那么它的效果有个“上限”，除非加入先验知识（比如通过交互的方式告知程序一行中实际有多少个格子、或者行宽、行的横坐标取值范围等）。
轮廓检测
继续往前看，我的格子是通过轮廓检测的方式检测出来的，这部分如果做得好，也就是说召回达到100%，那么就无需后续的补齐操作了。而这部分我是直接调用OpenCV大法的，因此上限在于参数的选取及其算法本身。我也做了不少实验，认为从调参这个方向去优化的话，能取得的进步效果应该不大，那么更有提升空间的就是自己去实现了。但是由于项目开发时间有限，因此就没有往这个方向走，日后可以仔细研究下。
排除误检
在整套方案里，我多次使用了全局（所有格子）或局部（各行）统计值（宽度、宽高比这些），之所以这样做是因为仅仅基于现有的算法鲁棒性不好，往往是对一幅图像效果好，而另一幅效果就不行了，因此我只能将这些统计值作为先验知识，以进行不同维度的校正，使得最终效果更接近真实情况。
特别是在排除误检的环节，也就是使用轮廓检测后排除掉那些形状大小奇葩和“离群”的格子，完全依赖的就是统计值。若经过轮廓检测得到的格子很少、或者本身其检测出的格子就“不对劲”，那么统计值（和真值）的偏差就非常大，这个先验就起了误导作用，后面的步骤也就几乎失去了意义...
因此，这个环节对于轮廓检测也有强依赖性，看来日后真的可以好好研究下轮廓检测这方面的实现。
直线检测
轮廓检测是在什么基础上做的呢，是在直线检测的基础上，我是在横纵直线交错的图像上进行轮廓检测的。如果说，我的直线检测效果十分完美，检测后全图都仅剩下格子线，字体笔画和其余干扰因素都被排除了，那么我觉得OpenCV大法应该还是能够检测出所有格子轮廓的。直线检测我使用的是形态学的方法，霍夫变换的方法我实验过一版，效果真的难看..也许是我没有调得很好的参数，还有霍夫变换的一些变种我没尝试过，这也是一个可能值得努力的方向。
二值化
直线检测是在二值图上做的，前面也阐述过，单单从二值化这个维度来评估，我的二值化做得真不太好，但是没办法，为了不“误杀”格子线，召回更多的格子，我只能将一些字体笔画也保留下来，其中还附带一些白色噪声。
通过灰度直方图统计可以知道，很多都是呈单峰状，不好用阀值达到很好的二值化效果。另外，在二值化后使用滤波的方法将白色噪声去除后效果是否更好，这点我也没有充分实验过，之前匆忙地试了下滤波，发现效果差不多就没继续耐心调参了。
一直觉得，二值化是我整套方案中做得最不好的地方之一，太多干扰因素被保留了下来，但是如果做得太“干净”，又会误杀掉格子线，真心虐...
这个方向日后有必要去深入研究下，特别是针对这种灰度直方图呈单峰状的情况。
其它
在开工前，我也请教过一些童鞋，有的给我建议使用模版匹配之类的方法，但是没有找到很好的参考实现，之前对这个方向也不太熟悉，因此就放弃了。
所以，还是得keep learning，虽说学习不能仅限于知识，但是只有知识量足够庞大，你才能有更多的思路，解决问题时也就更加高效。
