文章目录
  1. 1. EAN-13码
    1. 1.1. 简介
    2. 1.2. 编码表
    3. 1.3. 例子
  2. 2. Zbar EAN解码算法

Zbar是开源的条码解码库,类似的开源库有ZXing。zbar支持EAN/UPC码, Code128码, Code39, Code93, 交叉25码, QR码, PDF417码的解码。本文简单介绍EAN/UPC的编码原理,详述zbar中相应的解码算法,并简要分析它的代码实现。

EAN-13码

关于条码的相关知识除了wikipedia上面的介绍外,推荐几个不错的链接:
1.條碼編碼規則
2.barcode island

这些链接资料包含了条码的发展历程、解码规则以及应用领域。下面对EAN-13进行一个简单的介绍,这些介绍仅仅能够让读者对接下来的解码算法能够正常理解。

简介

EAN全称European Article Number,只能对数字进行编码,根据长度分为EAN-13, EAN-8两种编码方式(这两种码并不能相互转换),EAN-13码由13个数字组成。它的基本结构如下:




ean-13基本结构

Number System由2~3个数字组成,表示国家地区(注意第一位Number System并没有编码成条码,也就是说图片中第一个数字7没有对应的bar和space),Manufacture Code为厂商码,Product Code为产品码,最后一位是校验码。每个字元由2个bar, 2个space组成。1个字元由7个module宽度构成,每个module我们用0/1表示。其中1表示bar的module,0表示space的module。

一个EAN-13码的基本结构为:
-左护线(left-hand guard bars),编码为101
-左资料码
-中线(center guard pattern), 编码为01010
-右资料码
-右护线(right-hand guard bars)

编码表

下面给出最关键的编码规则(下面描述中称为表-1):

DIGIT LEFT-HAND ENCODING RIGHT-HAND ENCODING
ODD PARITY (A) EVEN PARITY (B) ALL CHARACTERS (C)
0 0001101 0100111 1110010
1 0011001 0110011 1100110
2 0010011 0011011 1101100
3 0111101 0100001 1000010
4 0100011 0011101 1011100
5 0110001 0111001 1001110
6 0101111 0000101 1010000
7 0111011 0010001 1000100
8 0110111 0001001 1001000
9 0001011 0010111 1110100

左编码区包含两种编码方式,Odd Parity(奇校验,bar的宽度相加是奇数)和Even Parity,左编码区的编码方式由第一位Number System数字确定。右编码区就一种编码方式。

每个bar和space的宽度不会超过4个module。同时可以注意到Type C的编码表为Type A的取反,Type C倒过来便是Type B。同时左编码区都是从”0”开始,右编码区都是从”1”开始。这个是由于左护线为”101”,中线为”01010”。

下面这张表就是关于左编码区如何根据第一位Number System数字进行编码的(下面描述中称为表-2):

FIRST NUMBER SYSTEM DIGIT SECOND NUMBER SYSTEM DIGIT 1 2 3 4 5
0(UPC-A) Odd Odd Odd Odd Odd Odd
1 Odd Odd Even Odd Even Even
2 Odd Odd Even Even Odd Even
3 Odd Odd Even Even Even Odd
4 Odd Even Odd Odd Even Even
5 Odd Even Even Odd Odd Even
6 Odd Even Even Even Odd Odd
7 Odd Even Odd Even Odd Even
8 Odd Even Odd Even Even Odd
9 Odd Even Even Odd Even Odd

例子

这里对上图中的”7-501031-311309”进行编码。

根据第二张表,第一位Number System为7,对应的左手编码方式为”Odd/Even/Odd/Even/Odd/Even”。每一位数字的编码为:

1.左护线 (总是相同的): 101.
2.第二位Number System[5]: 按照Type A进行编码, 0110001.
3.厂商码第1个位 [0]: 按照Type B进行编码, 0100111.
4.厂商码第2个位 [1]: 按照Type A进行编码, 0011001.
5.厂商码第3个位 [0]: 按照Type B进行编码, 0100111.
6.厂商码第4个位 [3]: 按照Type A进行编码, 0111101.
7.厂商码第5个位 [1]: 按照Type B进行编码, 0110011.
8.中线 (总是相同的): 01010.
9.产品码第1个位 [3]: 按照Type C进行编码, 1000010.
10.产品码第2个位 [1]: 按照Type C进行编码, 1100110.
11.产品码第3个位 [1]: 按照Type C进行编码, 1100110.
12.产品码第4个位 [3]: 按照Type C进行编码, 1000010.
13.产品码第5个位 [0]: 按照Type C进行编码, 1110010.
14.校验位 [9]: 按照Type C进行编码, 1110100.
15.右护线 (总是相同的): 101.

你可以和下图进行比对:




ean-13编码

Zbar EAN解码算法

事实上解码的过程主要依赖表-1,表-2只是起验证作用。表-1中每个编码方式都是不一样的,我们只要对扫描到的条码宽度按照上面的比例计算最接近的编码格式就好。

在Zbar中,具体是这么操作的:
1.首先我们先把表-1转换成宽度的格式进行编码;
2.然后对于左编码区,将最后3个宽度两两相加,对于右编码区,将前三个宽度两两相加(我们统一将中间两个宽度相加的结果放在最后)。以数字0为例,左编码区(奇校验)的宽度为3211, 后两个宽度相加为2,中间宽度相加为3,得到相加后的编码为23。

DIGIT LEFT-HAND ENCODING RIGHT-HAND ENCODING
ODD PARITY (A) EVEN PARITY (B) ALL CHARACTERS (C)
0 3211(23) 1123(53) 3211(53)
1 2221(34) 1222(44) 2221(44)
2 2122(43) 2212(33) 2122(33)
3 1411(25) 1141(55) 1411(55)
4 1132(54) 2311(24) 1132(24)
5 1231(45) 1321(35) 1231(35)
6 1114(52) 4111(22) 1114(22)
7 1312(34) 2131(44) 1312(44)
8 1213(43) 3121(33) 1213(33)
9 3112(32) 2113(42) 3112(42)

注意到上面的编码中,Type B和Type C转换后编码效果是一样的。在Type A中,34,44这两个编码重复了。在Type B中,44,33这两个编码重复了。对于重复的情况,比如Type A的34,对应2221及1312,我们考虑第二位及第四位的相加和,分别为3,5。通过这个进一步区分这些重复的编码。

在Zbar源码中,ean.c里面,压缩编码表后得到:

1
2
3
4
5
6
7
8
/* convert compact encoded D2E1E2 to character (bit4 is parity) */
static const unsigned char digits[] = { /* E1 E2 */
0x06, 0x10, 0x04, 0x13, /* 2 2-5 */
0x19, 0x08, 0x11, 0x05, /* 3 2-5 (d2 <= thr) */
0x09, 0x12, 0x07, 0x15, /* 4 2-5 (d2 <= thr) */
0x16, 0x00, 0x14, 0x03, /* 5 2-5 */
0x18, 0x01, 0x02, 0x17, /* E1E2=43,44,33,34 (d2 > thr) */
};

其中,第一个字节用来表示奇偶校验,第二个字节表示解码结果。

关于解码的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/* attempt to decode previous 4 widths (2 bars and 2 spaces) as a characterv*/
static __inline signed char decode4 (zbar_decoder_t *dcode)
{
signed char code;
/* calculate similar edge measurements */
unsigned e1 = ((get_color(dcode) == ZBAR_BAR)// 当前解码位置是条还是空,对于左编码区为101+sbsb;右编码区为:01010+bsbs(b表示bar,s表示space)
? get_width(dcode, 0) + get_width(dcode, 1)
: get_width(dcode, 2) + get_width(dcode, 3));
unsigned e2 = get_width(dcode, 1) + get_width(dcode, 2);
dbprintf(2, "\n e1=%d e2=%d", e1, e2);
if(dcode->ean.s4 < 6)//累计元素宽度太小就退出
return(-1);
/* create compacted encoding for direct lookup 将e1和e2压缩适应查表*/
code = ((decode_e(e1, dcode->ean.s4, 7) << 2) |
decode_e(e2, dcode->ean.s4, 7));//(e1<<2) | e2,其中e1,e2的值为1或2,其他值(负数)都是无效
if(code < 0)
return(-1);
dbprintf(2, " code=%x", code);
/* 4 combinations require additional determinant (D2)
E1E2 == 34 (0110) 6
E1E2 == 43 (1001) 9
E1E2 == 33 (0101) 5
E1E2 == 44 (1010) 10
*/
/* 0x0660 = 0000 0110 0110 0000 */
if((1 << code) & 0x0660) {//如果不为0,表示code落在E1 E2的码表里,因为1<<6,1<<9,1<<5,1<<10都是在码表里0x660=(1<<6 | 1<<5 | 1<<9 | 1<<10)
unsigned char mid, alt;
/* use sum of bar widths 计算2bar宽度和*/
unsigned d2 = ((get_color(dcode) == ZBAR_BAR)
? get_width(dcode, 0) + get_width(dcode, 2)
: get_width(dcode, 1) + get_width(dcode, 3));
d2 *= 7;//放大模块条数的倍数
/* 0x0420 = 0000 0100 0010 0000 */
mid = (((1 << code) & 0x0420)//code为5,10才为真,即33,44;其他时候6,9
? 3 /* E1E2 in 33,44; 如果为33, 44, d2的值是2或4*/
: 4); /* E1E2 in 34,43; 如果是34, 43, d2的值是3或5*/
alt = d2 > (mid * dcode->ean.s4);//阈值为mid*s4(2bar2space),d2为2bar*7
if(alt)
code = ((code >> 1) & 3) | 0x10; /* compress code space */
/* E1E2 = 0001 0011 (19)
* 0001 0000 (16)
* 0001 0010 (18)
* 0001 0001 (17)
*/
dbprintf(2, " (d2=%d(%d) alt=%d)", d2, mid * dcode->ean.s4, alt);
}
dbprintf(2, " char=%02x", digits[(unsigned char)code]);
zassert(code < 0x14, -1, "code=%02x e1=%x e2=%x s4=%x color=%x\n",
code, e1, e2, dcode->ean.s4, get_color(dcode));
return(code);
}

文章目录
  1. 1. EAN-13码
    1. 1.1. 简介
    2. 1.2. 编码表
    3. 1.3. 例子
  2. 2. Zbar EAN解码算法