开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2015.05.18
简单、直观的实现优于复杂、难懂的实现，最近开发扑克识别过程的总结
最近开发了款通用的扑克识别程序，本文谈下心得。最开始是准备使用ShapeContext或Zernike矩来识别的，写出了ShapeContext，发现识别率达不到理想状态。接着准备用Zernike矩实现，查找文献发现，Zernike矩虽然理论上对旋转是不变的，但实际上，图像的旋转会导致识别率降低，加上样本不多，就放弃了这两种方法。最后，还是用最基本的模板匹配和Blob分析来解决的，在只有单一的样本的情况下，对不同字体不同印刷的扑克，对有扭曲、旋转以及轻微模糊的扑克，达到了99.9%的识别率（这0.1%还没出现，也就是说，理论上达到了100%）。由于是商业性开发，代码就不贴了，只谈原理。
（1）Blob特征识别，将图像分为几大组。
（2）对每一组使用模板匹配，进行识别。
（3）对于（2）中一些易混淆结果，再使用Blob特征，进行识别。
一、Blob特征识别
本文中的Blob指的是连通的黑色像素块。比如：
这就是一个Blob。
将这个Blob图像的颜色取反，也就是黑变成白，白变成黑，颠倒黑白，指鹿为马，得到这样一个图：
数一下是几块？——8块！
不过，这里的8块这个特征是不稳定的，因为图像可能会旋转变形。为了得到稳定的特征，将这个图像向上、下、左、右分别扩张几个像素，得到这样一个图像：
这个图像有几块？——3块！这个3块的特征非常稳定，不受旋转及字体的影响。
这样一来，根据图像的反色->扩大->Blob计数就可以将它分成几组：
A组：有1个块的——2，3，5……
B组：有2个块的——4，6……
C组：有3个块的——8，Q（有时）……
二、对每一组进行模板匹配
详细就不讲了，网上一搜一大堆。
三、对易混淆结果，再使用Blob特征进行识别。
一些易混淆的字符，如3和5等…黑桃和草花…，再使用Blob特征进行识别。这里识别的方式五花八门，略举一二典型的。
拿3和5来说，首先将它们取反，再扩张几个像素，再从中线劈开：3和5就变成了：
数一下几个Blob？3是1个，5是2个。
再拿黑桃和草花来说：
分别取它们最左上的块。黑桃的左上块比较规则，一般都是近似三角形，而草花的就不规则，尤其是当图比较模糊时，会近似矩形：
怎么分辨这两类呢？我定义了个对称因子:以该Blob所属矩形的中心为对称中心，对矩形中的某一点A（x，y），找到它的对称点A’（w-x,h-y）。由于图像中像素是离散的，实际对称点是A’（w-x-1,h-y-1）。
计算对称点的颜色相同的点的个数，然后用这个个数除以总的像素数量，就得到Blob的对称因子。这个定义简单、直接，方便计算。黑桃左上块的对称因子很小，而草花的左上块对称因子较大，两个就识别开了。当然，这里还辅助了其它的Blob特征，就不详述了。
小结：
简单的好啊。但由于简单的东西很多时候上不了台面，所以书上啊，论文上啊，很少谈。书上、论文上都喜欢谈些复杂的牛逼的东东。具体到开发项目上来说，还是能简单就简单最好。本文使用的就是最基本的模板匹配、最简单的Blob分析及最初级的决策树模型，在最少样本的情况下，达到了最高的识别率。
一、车牌/验证码识别的普通方法
车牌、验证码识别的普通方法为：
（1）将图片灰度化与二值化
（2）去噪，然后切割成一个一个的字符
（3）提取每一个字符的特征，生成特征矢量或特征矩阵
（4）分类与学习。将特征矢量或特征矩阵与样本库进行比对，挑选出相似的那类样本，将这类样本的值作为输出结果。
下面借着代码，描述一下上述过程。因为更新SVNServer，我以前以bdb储存的代码访问不了，因此部分代码是用Reflector反编译过来的，望见谅。
（1）图片的灰度化与二值化
这样做的目的是将图片的每一个象素变成0或者255，以便以计算。同时，也可以去除部分噪音。
图片的灰度化与二值化的前提是bmp图片，如果不是，则需要首先转换为bmp图片。
用代码说话，我的将图片灰度化的代码（算法是在网上搜到的）：
通过将图片灰度化，每一个象素就变成了一个0-255的灰度值。
然后是将灰度值二值化为0或255。一般的处理方法是设定一个区间，比如，[a,b]，将[a,b]之间的灰度全部变成255，其它的变成0。这里我采用的是网上广为流行的自适应二值化算法。
灰度化与二值化之前的图片：
灰度化与二值化之后的图片：
注：对于车牌识别来说，这个算法还不错。对于验证码识别，可能需要针对特定的网站设计特殊的二值化算法，以过滤杂色。
上面这张车牌切割是比较简单的，从左到右扫描一下，碰见空大的，咔嚓一刀，就解决了。但有一些车牌，比如这张：
简单的扫描就解决不了。因此需要一个比较通用的去噪和切割算法。这里我采用的是比较朴素的方法：
将上面的图片看成是一个平面。将图片向水平方向投影，这样有字的地方的投影值就高，没字的地方投影得到的值就低。这样会得到一根曲线，像一个又一个山头。下面是我手画示意图：
然后，用一根扫描线（上图中的S）从下向上扫描。这个扫描线会与图中曲线存在交点，这些交点会将山头分割成一个又一个区域。车牌图片一般是7个字符，因此，当扫描线将山头分割成七个区域时停止。然后根据这七个区域向水平线的投影的坐标就可以将图片中的七个字符分割出来。
但是，现实是复杂的。比如，“川”字，它的水平投影是三个山头。按上面这种扫描方法会将它切开。因此，对于上面的切割，需要加上约束条件：每个山头有一个中心线，山头与山头的中心线的距离必需在某一个值之上，否则，则需要将这两个山头进行合并。加上这个约束之后，便可以有效的切割了。
以上是水平投影。然后还需要做垂直投影与切割。这里的垂直投影与切割就一个山头，因此好处理一些。
切割结果如下：
水平投影及切割代码：
代码中的Pair,代表扫描线与曲线的一对交点：
PairStatus代表Pair的状态。具体哪个状态是什么意义，我已经忘了。
以上这一段代码写的很辛苦，因为要处理很多特殊情况。那个PairStatus也是为处理特殊情况引进的。
垂直投影与切割的代码简单一些，不贴了，见附后的dll的BitmapConverter.TrimHeight方法。
将切割出来的字符，分割成一个一个的小块，比如3×3，5×5，或3×5，或10×8，然后统计一下每小块的值为255的像素数量，这样得到一个矩阵M，或者将这个矩阵简化为矢量V。
通过以上3步，就可以将一个车牌中的字符数值化为矢量了。
（1）-（3）步具体的代码流程如下：
然后，通过spliter.ValueList就可以获得Bitmapmap0的矢量表示。
（4）分类
分类的原理很简单。用(Vij,Ci)表示一个样本。其中，Vij是样本图片经过上面过程数值化后的矢量。Ci是人肉眼识别这张图片，给出的结果。Vij表明，有多个样本，它们的数值化后的矢量不同，但是它们的结果都是Ci。假设待识别的图片矢量化后，得到的矢量是V’。
直观上，我们会有这样一个思路，就是这张待识别的图片，最像样本库中的某张图片，那么我们就将它当作那张图片，将它识别为样本库中那张图片事先指定的字符。
在我们眼睛里，判断一张图片和另一张图片是否相似很简单，但对于电脑来说，就很难判断了。我们前面已经将图片数值化为一个个维度一样的矢量，电脑是怎样判断一个矢量与另一个矢量相似的呢？
这里需要计算一个矢量与另一个矢量间的距离。这个距离越短，则认为这两个矢量越相似。
我用SampleVector
T代表数据类型，可以为Int32，也可以为Double等更精确的类型。
测量距离的公共接口为：IMetric
常用的是MinkowskiMetric。
我的代码中，只实现了哪个最近，就选哪个。更好的方案是用K近邻分类器或神经网络分类器。K近邻的原理是，找出和待识别的图片（矢量）距离最近的K个样本，然后让这K个样本使用某种规则计算（投票），这个新图片属于哪个类别（C）；神经网络则将测量的过程和投票判决的过程参数化，使它可以随着样本的增加而改变，是这样的一种学习机。有兴趣的可以去看《模式分类》一书的第三章和第四章。
二、变态字符的识别
有些字符变形很严重，有的字符连在一起互相交叉，有的字符被掩盖在一堆噪音海之中。对这类字符的识别需要用上特殊的手段。
下面介绍几种几个经典的处理方法，这些方法都是被证实对某些问题很有效的方法：
（1）切线距离（TangentDistance）：可用于处理字符的各种变形，OCR的核心技术之一。
（2）霍夫变换（HoughTransform）：对噪音极其不敏感，常用于从图片中提取各种形状。图像识别中最基本的方法之一。
（3）形状上下文（ShapeContext）：将特征高维化，对形变不很敏感，对噪音也不很敏感。新世纪出现的新方法。
因为这几种方法我均未编码实现过，因此只简单介绍下原理及主要应用场景。
（1）切线距离
前面介绍了MinkowskiMetric。这里我们看看下面这张图：一个正写的1与一个歪着的1.
用MinkowskiMetric计算的话，两者的MinkowskiMetric很大。
然而，在图像识别中，形状形变是常事。理论上，为了更好地识别，我们需要对每一种形变都采足够的样，这样一来，会发现样本数几乎无穷无尽，计算量越来越大。
怎么办呢？那就是通过计算切线距离，来代替直接距离。切线距离比较抽象，我们将问题简化为二维空间，以便以理解。
上图有两条曲线。分别是两个字符经过某一形变后所产生的轨迹。V1和V2是2个样本。V’是待识别图片。如果用样本之间的直接距离，比较哪个样本离V’最近，就将V’当作哪一类，这样的话，就要把V’分给V1了。理论上，如果我们无限取样的话，下面那一条曲线上的某个样本离V’最近，V’应该归类为V2。不过，无限取样不现实，于是就引出了切线距离：在样本V1，V2处做切线，然后计算V’离这两条切线的距离，哪个最近就算哪一类。这样一来，每一个样本，就可以代表它附近的一个样本区域，不需要海量的样本，也能有效的计算不同形状间的相似性。
（2）霍夫变换
霍夫变换出自1962年的一篇专利。它的原理非常简单：就是坐标变换的问题。
如，上图中左图中的直线，对应着有图中k-b坐标系中的一个点。通过坐标变换，可以将直线的识别转换为点的识别。点的识别就比直线识别简单的多。为了避免无限大无限小问题，常用的是如下变换公式：
下面这张图是wikipedia上一张霍夫变换的示意图。左图中的两条直线变换后正对应着右图中的两个亮点。
通过霍夫变换原理可以看出，它的抗干扰性极强极强：如果直线不是连续的，是断断续续的，变换之后仍然是一个点，只是这个点的强度要低一些。如果一个直线被一个矩形遮盖住了，同样不影响识别。因为这个特征，它的应用性非常广泛。
对于直线，圆这样容易被参数化的图像，霍夫变换是最擅长处理的。对于一般的曲线，可通过广义霍夫变换进行处理。感兴趣的可以google之，全是数学公式，看的人头疼。
（3）形状上下文
图像中的像素点不是孤立的，每个像素点，处于一个形状背景之下，因此，在提取特征时，需要将像素点的背景也作为该像素点的特征提取出来，数值化。
形状上下文（ShapeContext，形状背景）就是这样一种方法：假定要提取像素点O的特征，采用上图（c）中的坐标系，以O点作为坐标系的圆心。这个坐标系将O点的上下左右切割成了12×5=60小块，然后统计这60小块之内的像素的特征，将其数值化为12×5的矩阵，上图中的（d），（e），（f）便分别是三个像素点的ShapeContext数值化后的结果。如此一来，提取的每一个点的特征便包括了形状特征，加以计算，威力甚大。来看看ShapeContext的威力：
上图中的验证码，对ShapeContext来说只是小Case。
看看这几张图。嘿嘿，硬是给识别出来了。
===========================================================
这三个dll可以直接用在车牌识别上。用于车牌识别，对易混淆的那几个字符识别率较差，需要补充几个分类器，现有分类器识别结果为D,O,0,I,1等时，用新分类器识别。用于识别验证码需要改一改。
有个asp.net的调用例子可实现在线上传图片识别，因为其中包含多张车牌信息，不方便放出来。我贴部分代码出来：