【算法】自动识别128条形码  

2009-07-20 11:28:13|  分类： 默认分类 |  标签：设计  算法   |举报 |字号 订阅

本来不想自己写的。想着玩意网上不是多的去了，随便DOWN个开源的用用就是了。

结果就是不省心。我朋友帮我找了2天，也没找到合适的。

不是识别率差就是收费版本。

逼我，自己写了一个。

今天 的目的就是编写一段程序能够自动识别图片上的条形码。

本文是基于前一篇，你会手工去识别CODE128的基础上的。如果你还不知道128码是如何编制的，请看前一篇文章： 

http://blog.163.com/lava_hammer/blog/static/38716716200961753422130/

其实这个程序分成2个部分：

第一个部分是从图片上把条码给找到，我使用了一些只能在特定环境下使用的特殊手段来定位条码，算法不具备通用性，这不是我们的主题，所以暂不讨论，朋友们可以轻松地使用各种手段对图片进行区域筛选，找到条形码。然后我们就以这样的输入开始我们的程序：

第二部分是我们的重点，那就是如何将这样一个图片转换成结果字符串：50090500019191

这里提供我的方法，由于没有接受过任何图形学的知识，所以我的言语中没有多少术语。方法也有可能有一定的局限性。仅供参考，欢迎讨论。

1）首先，我们要对图片进行处理。把它转换成黑白图，仅有黑白两种颜色，而不是灰度图。

我使用了一种业余而且简单的方法：

Y=0.299*r+0.587*g+0.114*b 这个公式是RGB色彩中亮度的贡献参数计算方法。也是常用的RGB转灰度图片的计算公式。我们定义一个阈值来判定到底是黑还是白。经过实践发现192，这个值比较合适。所有Y小于192的判断为黑，其余为白。

【Java小窍门】Java里存储图片所使用的BufferedImage类型获取某一个像素的色彩时是使用getRGB(int x,int y)。

这个方法返回出来的是一个int类型。默认情况下是ARGB格式。我们可以采用位运算的方法从当中提取出RGB的分量：

c=source.getRGB(i%mWidth, i/mWidth);

r=(c>>16)&255;

g=(c>>8)&255;

b=c&255;

2）获取条形码的粗细信息。一个纵向的循环，计算出每一条竖线到底是黑线还是白线，同时记录出连续有多少黑线和白线，单位是像素。我的判断方法是如果一条竖线上有50%以上是黑或者白，那这条线就是黑的或者是白的。这个很容易就做到了。最后我们得到一个数组的结果类似这样：

5 2 2 4 6 4 5 5 3 1 7 2 4 4 2 4 3 5 3 6 2 3 5 4 5 1 5 3 5 4 5 3 5 1 5 4 9 1 5 1 5 1 10 1 5 1 5 1 3 6 5 1 3 5 5 6 6 2 3 1 5

至此，我们终于把图像转换成我们需要的特征数据了。这些数字就是我们要处理的数据了。这些数字的含义是连续黑或白的像素个数。比如开头的5 2 2 4就代表：一开始是有5个像素宽的黑条，然后是2个像素宽的白空，接着再是2个像素的黑条最后是4个像素宽的白空。我的算法是从第一个黑条开始算起的，所以第一组数据总是能正确表示出黑条的起始和宽度。然而最后却不一样，它可能包含了一些冗余数据，基本上是因为它还测量了最后一个黑条后面的空白宽度，我们只需要将数字截取前N位有效位数即可，例如我们这里的条码是61位数据，所以我们只要前61位即可。

3）下面我们的主要问题就是如何将这些数据转成匹配成我们要的结果。需要注意的是这些长度并非正好是1-4。最早我曾想过等比转换的方法，那就是找到这些数字中最大的数，将它除以4得到一个系数。然后我们只要将每个数字除以这个系数就可以得到一个按照原来的比例缩小到1-4范围的整数（中间牵涉到一些浮点运算，四舍五入之类的东西）。但是结果不理想。原因很简单，这种算法容错性太差。就拿我们的这组数据来看，StartC是211232。我们截获的数据是522464。大约是2倍的关系。但是按照这个系数配下去，553172应该是221131，而正确的结果因该是231131。看到第二个数字，原来是5，但是实际应该转换成3而不是2。但是之前的5却应该是转换成2的。这样看来即便是同一个数字也可能应该转换成不同的结果。这使得等比压缩的方法彻底无法起效果了。因为等比压缩无论如何优化，同样的输入必定是同样的输出。

这样的话，我们就要另想办法了。出路有2条：1）提高采样的精确度 2）改善匹配算法。我一开始是考虑的第一条路，如何改善采样的精确度。我曾考虑用浮点来表示采样的结果，但是最后还是通过第二条路解决了问题。原因就是要提高采样的精确度是很复杂的事情，可能要从灰度转换开始。而每次转换都会导致一些误差，这些误差是无法避免的，最后就很难保证能够将精度提高到符合等比压缩的要求。

经过一番考虑，我最后采取了一种基于对比的匹配算法。这种方法可以容许较大的误差。思路类似于，我们将采样到的结果和标准表对比，采样结果最像那个标准表，那么结果就应该是谁。这样的算法可以包容很大的误差，只要误差没有达到使采样的结果更像另外一个值，那么它的结果就不会有误。请注意，这个方法让我们对采样的误差的要求从绝对的量转换到了相对的量。这意味着，只要采样的结果是人肉眼能识别的，那么我的算法也一样可以识别。但是也请注意，是采样结果肉眼可识别，而不是扫描的结果，这意味着不包含那些在第1）步和第2）步中出现的误差。

那么，怎么样才算是“最像”呢？具体的来说就是怎样判断522464最像211232？好的，可以明确，要是没有误差，从纯粹的数学角度来说，完美的匹配应该是这样的：每一个对应的数字相除所得的结果都是一致的。这反映的是采样结果应该是标准的K倍缩放。若211232是我们要的结果，采样结果是a1 a2 a3 a4 a5 a6，那么a1=k*2 a2=k*1 a3=k*1 a4=k*2 a5=k*3 a6=k*2 其中k属于实数。但是结果不是那么完美，实际情况是522464，我们分别算出来的k是2.5 2 2 2 2 2，并不是全部相等。但是“最像”已经被我们量化的定义出来了，那就是这6个系数有多一致。聪明的你，一定已经想到，在数学上表示一堆数字的“稳定性”的量就是 方差 或者是 标准差 。标准差是方差的开根。是的，我们只要将采用的结果和标准表进行对比，取方差最小的为结果就可以了。这样的话，所以问题就都解决了。

经过实践证明，此算法的确有较高的识别能力。

【计算窍门】方差的计算式是 s=[(a1-a)^2+(a2-a)^2+...]/n。我们只需要比较方差就可以了，并不需要知道确切的方差值，所以那个/n对我们来说是多余的运算。因为我们的数据都是6个为一组的。没有必要都去除以6再来进行比较。

4）最后，我们还可以通过计算校验位来建议自己的识别是否正确，这个很简单，只要知道校验算法就是了。通常校验算法就是将条码的 各位进行加权求和然后取余所得的。具体算法可以参考具体的条码编码标准。这里不作详细说明。

这个算法识别率还行，但是计算量比较大。Code128的标准表有106个值（除去STOP），每一位的比对都要比较106次，但是最后综合的速度还是可以的。（一个条形码我用java写的，好像消耗了7个毫秒）应该还是可以优化的，但是对于我的应用来说，速度足够了。

写在最后的话，其实我原本以为条码识别很麻烦，很高深。其实自己去做了才发现也不过如此。所以啊，只要肯思考，我们的实力其实远比自己以为的要强大。