学步园

本文源自我之前花了2天时间做的一个简单的车牌识别系统。那个项目，时间太紧，样本也有限，达不到对方要求的95%识别率（主要对于车牌来说，D,0，O，I，1等等太相似了。然后，汉字的识别难度也不小），因此未被对方接受。在此放出，同时描述一下思路及算法。

全文分两部分，第一部分讲车牌识别及普通验证码这一类识别的普通方法，第二部分讲对类似QQ验证码，Gmail验证码这一类变态验证码的识别方法和思路。

一、车牌/验证码识别的普通方法

车牌、验证码识别的普通方法为：

（1）       将图片灰度化与二值化

（2）       去噪，然后切割成一个一个的字符

（3）       提取每一个字符的特征，生成特征矢量或特征矩阵

（4）       分类与学习。将特征矢量或特征矩阵与样本库进行比对，挑选出相似的那类样本，将这类样本的值作为输出结果。

下面借着代码，描述一下上述过程。因为更新SVN Server，我以前以bdb储存的代码访问不了，因此部分代码是用Reflector反编译过来的，望见谅。

（1）       图片的灰度化与二值化

这样做的目的是将图片的每一个象素变成0或者255，以便以计算。同时，也可以去除部分噪音。

图片的灰度化与二值化的前提是bmp图片，如果不是，则需要首先转换为bmp图片。

用代码说话，我的将图片灰度化的代码（算法是在网上搜到的）：

Code
1 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。这里我采用的是网上广为流行的自适应二值化算法。

Code
 1 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 

灰度化与二值化之前的图片：

灰度化与二值化之后的图片：

     然后，用一根扫描线（上图中的S）从下向上扫描。这个扫描线会与图中曲线存在交点，这些交点会将山头分割成一个又一个区域。车牌图片一般是7个字符，因此，当扫描线将山头分割成七个区域时停止。然后根据这七个区域向水平线的投影的坐标就可以将图片中的七个字符分割出来。

     但是，现实是复杂的。比如，“川”字，它的水平投影是三个山头。按上面这种扫描方法会将它切开。因此，对于上面的切割，需要加上约束条件：每个山头有一个中心线，山头与山头的中心线的距离必需在某一个值之上，否则，则需要将这两个山头进行合并。加上这个约束之后，便可以有效的切割了。

以上是水平投影。然后还需要做垂直投影与切割。这里的垂直投影与切割就一个山头，因此好处理一些。

切割结果如下：

水平投影及切割代码：

Code
 1 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,代表扫描线与曲线的一对交点：

Code
 1 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的状态。具体哪个状态是什么意义，我已经忘了。

Code
1 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）       提取每一个字符的特征，生成特征矢量或特征矩阵