车牌识别及验证码识别的一般思路
本文源自我之前花了2天时间做的一个简单的车牌识别系统。那个项目，时间太紧，样本也有限，达不到对方要求的95%识别率（主要对于车牌来说，D,0，O，I，1等等太相似了。然后，汉字的识别难度也不小），因此未被对方接受。在此放出，同时描述一下思路及算法。
全文分两部分，第一部分讲车牌识别及普通验证码这一类识别的普通方法，第二部分讲对类似QQ验证码，Gmail验证码这一类变态验证码的识别方法和思路。
一、车牌/验证码识别的普通方法
车牌、验证码识别的普通方法为：
（1） 将图片灰度化与二值化
（2） 去噪，然后切割成一个一个的字符
（3） 提取每一个字符的特征，生成特征矢量或特征矩阵
（4） 分类与学习。将特征矢量或特征矩阵与样本库进行比对，挑选出相似的那类样本，将这类样本的值作为输出结果。
下面借着代码，描述一下上述过程。因为更新SVN Server，我以前以bdb储存的代码访问不了，因此部分代码是用Reflector反编译过来的，望见谅。
（1） 图片的灰度化与二值化
这样做的目的是将图片的每一个象素变成0或者255，以便以计算。同时，也可以去除部分噪音。
图片的灰度化与二值化的前提是bmp图片，如果不是，则需要首先转换为bmp图片。
用代码说话，我的将图片灰度化的代码（算法是在网上搜到的）：
Code1 protected static Color Gray(Color c)
2 {
3 int rgb = Convert.ToInt32((double) (((0.3 * c.R) + (0.59 * c.G)) + (0.11 * c.B)));
4 return Color.FromArgb(rgb, rgb, rgb);
5 }
6
通过将图片灰度化，每一个象素就变成了一个0-255的灰度值。
然后是将灰度值二值化为 0 或255。一般的处理方法是设定一个区间，比如，[a,b]，将[a,b]之间的灰度全部变成255，其它的变成0。这里我采用的是网上广为流行的自适应二值化算法。
Code1 public static void Binarizate(Bitmap map)
2 {
3 int tv = ComputeThresholdValue(map);
4 int x = map.Width;
5 int y = map.Height;
6 for (int i = 0; i < x; i++)
7 {
8 for (int j = 0; j < y; j++)
9 {
10 if (map.GetPixel(i, j).R >= tv)
11 {
12 map.SetPixel(i, j, Color.FromArgb(0xff, 0xff, 0xff));
13 }
14 else
15 {
16 map.SetPixel(i, j, Color.FromArgb(0, 0, 0));
17 }
18 }
19 }
20 }
21
22 private static int ComputeThresholdValue(Bitmap img)
23 {
24 int i;
25 int k;
26 double csum;
27 int thresholdValue = 1;
28 int[] ihist = new int[0x100];
29 for (i = 0; i < 0x100; i++)
30 {
31 ihist[i] = 0;
32 }
33 int gmin = 0xff;
34 int gmax = 0;
35 for (i = 1; i < (img.Width - 1); i++)
36 {
37 for (int j = 1; j < (img.Height - 1); j++)
38 {
39 int cn = img.GetPixel(i, j).R;
40 ihist[cn]++;
41 if (cn > gmax)
42 {
43 gmax = cn;
44 }
45 if (cn < gmin)
46 {
47 gmin = cn;
48 }
49 }
50 }
51 double sum = csum = 0.0;
52 int n = 0;
53 for (k = 0; k <= 0xff; k++)
54 {
55 sum += k * ihist[k];
56 n += ihist[k];
57 }
58 if (n == 0)
59 {
60 return 60;
61 }
62 double fmax = -1.0;
63 int n1 = 0;
64 for (k = 0; k < 0xff; k++)
65 {
66 n1 += ihist[k];
67 if (n1 != 0)
68 {
69 int n2 = n - n1;
70 if (n2 == 0)
71 {
72 return thresholdValue;
73 }
74 csum += k * ihist[k];
75 double m1 = csum / ((double) n1);
76 double m2 = (sum - csum) / ((double) n2);
77 double sb = ((n1 * n2) * (m1 - m2)) * (m1 - m2);
78 if (sb > fmax)
79 {
80 fmax = sb;
81 thresholdValue = k;
82 }
83 }
84 }
85 return thresholdValue;
86 }
87
88
灰度化与二值化之前的图片：
灰度化与二值化之后的图片：
注：对于车牌识别来说，这个算法还不错。对于验证码识别，可能需要针对特定的网站设计特殊的二值化算法，以过滤杂色。
（2） 去噪，然后切割成一个一个的字符
上面这张车牌切割是比较简单的，从左到右扫描一下，碰见空大的，咔嚓一刀，就解决了。但有一些车牌，比如这张：
简单的扫描就解决不了。因此需要一个比较通用的去噪和切割算法。这里我采用的是比较朴素的方法：
将上面的图片看成是一个平面。将图片向水平方向投影，这样有字的地方的投影值就高，没字的地方投影得到的值就低。这样会得到一根曲线，像一个又一个山头。下面是我手画示意图：
然后，用一根扫描线（上图中的S）从下向上扫描。这个扫描线会与图中曲线存在交点，这些交点会将山头分割成一个又一个区域。车牌图片一般是7个字符，因此，当扫描线将山头分割成七个区域时停止。然后根据这七个区域向水平线的投影的坐标就可以将图片中的七个字符分割出来。
但是，现实是复杂的。比如，“川”字，它的水平投影是三个山头。按上面这种扫描方法会将它切开。因此，对于上面的切割，需要加上约束条件：每个山头有一个中心线，山头与山头的中心线的距离必需在某一个值之上，否则，则需要将这两个山头进行合并。加上这个约束之后，便可以有效的切割了。
以上是水平投影。然后还需要做垂直投影与切割。这里的垂直投影与切割就一个山头，因此好处理一些。
切割结果如下：
水平投影及切割代码：
Code1 public static IList<Bitmap> Split(Bitmap map, int count)
2 {
3 if (count <= 0)
4 {
5 throw new ArgumentOutOfRangeException("Count 必须大于0.");
6 }
7 IList<Bitmap> resultList = new List<Bitmap>();
8 int x = map.Width;
9 int y = map.Height;
10 int splitBitmapMinWidth = 4;
11 int[] xNormal = new int[x];
12 for (int i = 0; i < x; i++)
13 {
14 for (int j = 0; j < y; j++)
15 {
16 if (map.GetPixel(i, j).R == CharGrayValue)
17 {
18 xNormal[i]++;
19 }
20 }
21 }
22 Pair pair = new Pair();
23 for (int i = 0; i < y; i++)
24 {
25 IList<Pair> pairList = new List<Pair>(count + 1);
26 for (int j = 0; j < x; j++)
27 {
28 if (xNormal[j] >= i)
29 {
30 if ((j == (x - 1)) && (pair.Status == PairStatus.Start))
31 {
32 pair.End = j;
33 pair.Status = PairStatus.End;
34 if ((pair.End - pair.Start) >= splitBitmapMinWidth)
35 {
36 pairList.Add(pair);
37 }
38 pair = new Pair();
39 }
40 else if (pair.Status == PairStatus.JustCreated)
41 {
42 pair.Start = j;
43 pair.Status = PairStatus.Start;
44 }
45 }
46 else if (pair.Status == PairStatus.Start)
47 {
48 pair.End = j;
49 pair.Status = PairStatus.End;
50 if ((pair.End - pair.Start) >= splitBitmapMinWidth)
51 {
52 pairList.Add(pair);
53 }
54 pair = new Pair();
55 }
56 if (pairList.Count > count)
57 {
58 break;
59 }
60 }
61 if (pairList.Count == count)
62 {
63 foreach (Pair p in pairList)
64 {
65 if (p.Width < (map.Width / 10))
66 {
67 int width = (map.Width / 10) - p.Width;
68 p.Start = Math.Max(0, p.Start - (width / 2));
69 p.End = Math.Min((int) (p.End + (width / 2)), (int) (map.Width - 1));
70 }
71 }
72 foreach (Pair p in pairList)
73 {
74 int newMapWidth = (p.End - p.Start) + 1;
75 Bitmap newMap = new Bitmap(newMapWidth, y);
76 for (int ni = p.Start; ni <= p.End; ni++)
77 {
78 for (int nj = 0; nj < y; nj++)
79 {
80 newMap.SetPixel(ni - p.Start, nj, map.GetPixel(ni, nj));
81 }
82 }
83 resultList.Add(newMap);
84 }
85 return resultList;
86 }
87 }
88 return resultList;
89 }
90
代码中的 Pair,代表扫描线与曲线的一对交点：
Code1 private class Pair
2 {
3 public Pair();
4 public int CharPixelCount { get; set; }
5 public int CharPixelXDensity { get; }
6 public int End { get; set; }
7 public int Start { get; set; }
8 public BitmapConverter.PairStatus Status { get; set; }
9 public int Width { get; }
10 }
11
PairStatus代表Pair的状态。具体哪个状态是什么意义，我已经忘了。
Code1 private enum PairStatus
2 {
3 JustCreated,
4 Start,
5 End
6 }
7
以上这一段代码写的很辛苦，因为要处理很多特殊情况。那个PairStatus 也是为处理特殊情况引进的。
垂直投影与切割的代码简单一些，不贴了，见附后的dll的BitmapConverter.TrimHeight方法。
以上用到的是朴素的去噪与切割方法。有些图片，尤其是验证码图片，需要特别的去噪处理。具体操作方法就是，打开CxImage（http://www.codeproject.com/KB/graphics/cximage.aspx），或者Paint.Net，用上面的那些图片处理方法，看看能否有效去噪。记住自己的操作步骤，然后翻他们的源代码，将其中的算法提取出来。还有什么细化啊，滤波啊，这些处理可以提高图片的质量。具体可参考ITK的代码或图像处理书籍。
（3） 提取每一个字符的特征，生成特征矢量或特征矩阵
将切割出来的字符，分割成一个一个的小块，比如3×3，5×5，或3×5，或10×8，然后统计一下每小块的值为255的像素数量，这样得到一个矩阵M，或者将这个矩阵简化为矢量V。
通过以上3步，就可以将一个车牌中的字符数值化为矢量了。
（1）-（3）步具体的代码流程如下：
Code1
2 BitmapConverter.ToGrayBmp(bitmap); // 图片灰度化
3 BitmapConverter.Binarizate(bitmap); // 图片二值化
4 IList<Bitmap> mapList = BitmapConverter.Split(bitmap, DefaultCharsCount); // 水平投影然后切割
5 Bitmap map0 = BitmapConverter.TrimHeight(mapList[0], DefaultHeightTrimThresholdValue); // 垂直投影然后切割
6 ImageSpliter spliter = new ImageSpliter(map0);
7 spliter.WidthSplitCount = DefaultWidthSplitCount;
8 spliter.HeightSplitCount = DefaultHeightSplitCount;
9 spliter.Init();
10
然后，通过spliter.ValueList就可以获得 Bitmap map0 的矢量表示。
（4） 分类
分类的原理很简单。用(Vij,Ci)表示一个样本。其中，Vij是样本图片经过上面过程数值化后的矢量。Ci是人肉眼识别这张图片，给出的结果。Vij表明，有多个样本，它们的数值化后的矢量不同，但是它们的结果都是Ci。假设待识别的图片矢量化后，得到的矢量是V’。
直观上，我们会有这样一个思路，就是这张待识别的图片，最像样本库中的某张图片，那么我们就将它当作那张图片，将它识别为样本库中那张图片事先指定的字符。
在我们眼睛里，判断一张图片和另一张图片是否相似很简单，但对于电脑来说，就很难判断了。我们前面已经将图片数值化为一个个维度一样的矢量，电脑是怎样判断一个矢量与另一个矢量相似的呢？
这里需要计算一个矢量与另一个矢量间的距离。这个距离越短，则认为这两个矢量越相似。
我用 SampleVector<T> 来代表矢量：
Code1 public class SampleVector<T>
2 {
3 protected T[] Vector { get; set; }
4 public Int32 Dimension { get { return Vector.Length; } }
5 ……
6 }
7
T代表数据类型，可以为Int32，也可以为Double等更精确的类型。
测量距离的公共接口为：IMetric
Code1 public interface IMetric<TElement,TReturn>
2 {
3 TReturn Compute(SampleVector<TElement> v1, SampleVector<TElement> v2);
4 }
5
常用的是MinkowskiMetric。
Code1 /// <summary>
2 /// Minkowski 测度。
3 /// </summary>
4 public class MinkowskiMetric<TElement> : IMetric<TElement, Double>
5 {
6 public Int32 Scale { get; private set; }
7 public MinkowskiMetric(Int32 scale)
8 { S