一种面向汉字的高压缩比彩色二维条码的设计与实现

贾华国,袁远松,刘 志

(浙江工业大学软件学院,浙江 杭州 310032)

条码技术是集编码、印刷、识别、数据采集和处理于一体的综合技术.目前,黑白二维条码技术发展已经趋于成熟,美国国家标准协会(ANSI)制定了二维条码国际标准[1-2],包括 Data Matrix,PDF417,QR码等.但随着社会信息量增加以及条码应用领域的拓宽,需要条码能表示更多信息,而当前黑白二维条码只使用两种颜色,较大程度上限制了条码信息容量的提高,此背景下,人们开始展开对彩色二维条码的研究[3-4].目前,彩码的研究工作属于起步阶段.微软研究院在自主研发一款彩色二维条码,发明人是Gavin Jancke,有四色和八色两种版本,其最小单元是三角形,相对于黑白二维条码,大约可以提高2～3倍的数据密度.韩国ColorZip公司也正在推出“彩色条码”业务.但我国表达信息的语言为中文,当前流行的二维条码包括微软等在研发的彩色二维条码,主要是针对英文字母与数字编码,对中文汉字则使用汉字内码来表示,对中文文本来说,这种编码方式效率偏低.再次,使用国外标准还存在专利许可权等问题.针对以上情况,笔者在参照了Data Matrix码国际标准后,设计一种具有较高容量且适合汉字编码的彩色二维条码,并将其实现.

1 彩色二维条码原理

1.1 信息容量

因黑白二维条码通过将数据转化成二进制流,而后根据0,1值进行黑白符号表示.所以,具有n个模块的黑白二维条码,每个模块可表示0或者1,即每个模块能表示2种可能,n个模块的信息容量为2n.对于彩色条码,假设颜色总数为k,通过扩展黑白二维条码的符号化表示方式,使用不同颜色的模块标识k进制数中各个对应的0,1,2,…,k-1,k.此时,具有n个模块的彩色二维条码能表示的信息容量为kn.故只要彩色条码中选取的颜色总数大于2种,通过一定的编码规则,可较大提高二维条码信息容量.因考虑选取相互之间对比较明显的颜色有助于提高识别效率,根据RGB彩色空间模型,其中黑,白 ,红 ,绿 ,黄 ,蓝 ,青 ,品红等 8 种颜色之间的对比最明显,故选取其中的前6种作为彩色条码的颜色值,汉字库编码模式小节中将对此进行分析.

1.2 条码结构

彩色二维条码结构可分为两部分:功能图像和数据图像(见图1).功能图像用于条码的定位、校正.数据图像则用来表示编码后具体的数据信息.彩码图像由各个规则排列的正方形模块组成,其空白处即为数据图像区域.该功能图像可更准确、有效的对条码进行定位,解码阶段将对此进行具体分析.

图1 彩色二维条码结构Fig.1 Structure of color two-dimensional barcode

2 编码原理

彩色二维条码编码过程分为三个顺序步骤:数据信息编码,纠错码生成,符号化过程.首先根据数据信息编码模式将数据信息转化为数据位流,并在开始处添加表示数据位流长度数构成新数据流.其次,将形成的数据流按4位组成码字由Reed-Solomon纠错算法生成纠错码字[5],添加到数据码字之后形成总的数据码字.最后,对总的数据码字进行符号化,同时添加功能图像,生成彩色条码图像.因纠错码Reed-Solomon纠错算法已是成熟算法,故在编码原理中只对彩色条码数据信息编码模式及符号化过程进行介绍.编码流程见图2.

图2 编码流程图Fig.2 Encoding flow diagram

2.1 数据信息编码模式

(1)汉字库编码模式

国标字符集中共有6 763个汉字和682个非汉字图形符号.但教育部、国家语委通过统计和分析汉字使用情况可知,日常生活中常用的汉字数只有3 500个左右,最常用的600个汉字就可以覆盖语料的80%,通过计算可知5进制数中5位最大数为44 4445对应于十进制的3 12410,通过使用两位标识符可将汉字库容量扩充至15 624,但3 124个汉字已覆盖日常生活中99%的汉字,故其容量为3 124,且需加一位作为标识,所以最终将采用6进制,对应与彩色条码颜色,即需采用6种颜色.

编码规则:据清华大学统计的汉字频度表建立汉字编码库,见表1.

表1 汉字库编码规则Table 1 Chinese Character Encoding Rules

(2)内码编码模式

内码编码模式是对汉字库编码模式的补充.针对汉字库外的低频汉字以及不常用的标点符号,使用汉字内码进行编码.

(3)单个ASCII编码模式

针对单个ASCII进行编码,模式标识符‘50',长度为6位.

(4)连续数字编码模式

针对数字编码,处理完毕后,在开始处加模式指示符‘515',结尾加结束模式指示符‘5',见表2.

表2 编码模式规则表Table 2 Encoding rules

(5)连续ASCII编码模式

编码规则:将ASCII分为两个集合S与R,见表3.

表3 集合S与R中的元素Table 3 Elements in set S and R

如:对连续字符‘AB'进行编码,设码值分别为a,b,见表4.

表4 连续ASCII编码规则Table 4 Continuous ASCII encoding rules

处理完毕后,在开始与结尾处分别加入模式指示符‘505'与结束模式指示符‘505'.

2.2 符号化

数字转化为颜色值时遵循映射关系,见表5.

表5 数字-颜色对应表Table 5 Digital-color mapping table

且对于整个彩色图像来讲,符号化的过程为从左到右,从下到上.并且在每个数据区域,也遵循从左到右,从下到上的顺序.该顺序如图3所示.

图3 ‘3205'符号化与符号化顺序图Fig.3 Symbolic and the symbolic sequence diagram

2.3 性能对比

相比与黑白二色条码,设计的彩色二维条码主要在数据容量与数据信息压缩比上有所提高.

对于数据容量,通过前文设计原理部分已知:假设颜色总数为k,具有n个模块的彩色二维条码能表示的信息容量为kn,故对于黑白条码来说,其信息容量为2n,对于设计的彩色二维条码,因其使用6种颜色,故信息容量为 6n,当n＞=1时,6n＞2n,故在理论上,彩色二维条码在信息容量上对比与黑白二色条码有较大优势.

对于数据信息压缩比,下面通过对一段新闻进行不同编码来比较:“12月13日(北京时间9时00分左右),全国第二届省级示范性软件学院院长联席会在我校举行.”

此新闻中汉字和中文标点一共36个,ASCII码字字符:8个,根据彩色条码数据信息编码规则,编码后总的码字位数为194位,各种编码模式统计如表6所示,表中只显示其中需要用到的编码模式.

表6 编码模式统计Table 6 Encoding mode statistics

若采用Data Matrix进行编码,按照其编码模式计算编码长度:汉字和中文标点一共36个,需采用Base 256编码模式,每个字符编码需占用16位,再加上两个码字的长度计数,汉字的编码长度需36×16+16=592位,对数字、ASCII的编码,只计算其最优编码情况下的编码长度,不考虑模式切换所需要的码字耗费,也需要40位:2×4+5.33×6≈40位,总共需要632位,两者所需位数-相差632÷194≈3.25倍,故可知彩色条码编码效率即信息压缩比更高.

图4是对该段新闻进行编码形成的图片,分别使用彩色条码编码与Data Matrix编码.通过对比两张图片可知.相同模块下,彩色二维条码的信息数据容量近似3.5倍于黑白二色的二维条码.其中,有彩色条码具有6种颜色所带来的信息容量优势,也有采取多种编码方式来提高信息的压缩比所带来的信息容量优势,特别是彩色条码编码阶段加入汉字库,通过独有的汉字库编码来专门对汉字进行处理,取得对中文汉字的高压缩比而获得的信息容量优势.

图4 彩色条码图与Data Matrix图片Fig.4 Color barcode and data matrix barcode

3 解码原理

前文已将彩色条码设计及编码原理介绍完毕,经对比,可知彩色二维条码在数据信息容量以及汉字压缩比上有较大优势.但同时因条码图像中含有多种颜色,也提高了条码图像的复杂度,对解码过程各步骤的准确性提出更高要求.解码过程见图5,将图中解码过程分为3个主要步骤.

图5 解码流程图Fig.5 Decoding flow diagram

3.1 定 位

解码过程中定位是非常重要的一步,只有定位准确,才能为顺利读取条码信息创造先决条件,若无法准确定位条码图像,则无法进行条码的解码步骤.为准确定位图中彩色条码的位置,可通过功能图像来实现此功能,如图6所示.

图6 功能图像Fig.6 Function image

因彩色条码图像中复杂度有所增加,故设计的功能图像需具有较强的定位能力.以上图片分别为功能图像以及其在不同颜色通道下的显示.其中,红色通道下的功能图像与Data Matrix编码中的功能图像基本一致,可参照该编码标准中的定位算法.从理论上说,通过对红色通道下的功能图像进行Hough直线检测已可进行准确定位,对于绿色通道与蓝色通道的功能图像,可在通过红色通道下功能图像无法实现准确定位时候,将其加入到定位步骤中,是对Data Matrix编码定位的一种改进与补充.

3.2 颜色信息转化数据位流信息

此步骤需完成两个功能:检测条码规格即行列数目以及通过转换算法将颜色信息转换为数据位流信息.条码规格检测可通过计算定位坐标内一行图像中像素的变化次数来得到,因条码设计时呈正方形排列,故对于行列数目只要计算其中一项即可.得到条码规格后,通过如下方法将颜色信息进行转化,见图7.

图7 颜色转化数字流程图Fig.7 Flow diagram of color translating into digital

假设定位过程中得到的顶点坐标,因彩色条码图像为正方形,可设各顶点坐标为左上角P1(x1,y1),右上角 P2(x2,y1),左下角P3(x1,y2),右下角P4(x2,y2),且条码规格为n.

则各个模块大小为:

e=(x2-x1)/n或e=(y2-y1)/n,对位于第 I行第J列的模块来讲,其边界坐标:

X轴方向为

Y轴方向为

统计该模块边界范围内各像素的个数,并取其中像素值最多的颜色值作为该模块的颜色值,将该颜色转化成对应的数字,这是为提高读取颜色信息的正确率采取的措施,若对效率要求较高,则可直接取各模块中心点像素值作为该模块的颜色值,但相比与统计的方法,正确率较低,故还是采用统计像素个数的方法.因符号化过程中,数据是由倒正方形方式进行排放,将图像信息转成数据矩阵后,需按照符号化时顺序对矩阵中数字进行读取排列,组成数据位流信息.

3.3 数据信息进行解码

经纠错码运算无误后,首先读取数据信息前5位数据,将其转成十进制数后可知数据信息长度.此时,可根据不同识别符,确定使用的编码规则,对其进行逆操作完成对数据的解码.表7为各模式下的指示符.

表7 数据信息编码模式识别符Table 7 Identifier of data coding mode

4 实验结果

因前文编码原理阶段已将彩色条码性能进行说明,故这里只是对编解码结果进行显示.以下为对浙江工业大学网址“http://www.zjut.edu.cn:80”及名称“浙江工业大学”进行编解码,见图8,9.

从图中可知,彩色二维条码编解码已成功实现,并且通过编码原理中性能对比可知彩码在信息容量与压缩比上具有较大优势,特别是对汉字信息的压缩比,相比于其他条码标准,有了大幅度的提升.

5 结 论

笔者设计了一种彩色二维条码,介绍了该条码的编码原理及解码方法,在与Data Matrix码的性能对比中,得到了相当好的效果.目前,解码过程只是针对计算机生成的标准图像进行处理,对实际拍摄中,图像中可能存在的变形和偏色以及提高定位效率等方面还有待进一步研究,同时,对编码和解码的速度也需进一步提升,以适应实际应用.

[1] International Organization for Standardization.ISO/IEC16022—2000 Information technology international symbology speciation-data matrix[S].Switzerland:ISO,2004.

[2] PAVLIDIS T,SWARTZ J.Fundamentals of barcode information theory[J].IEEE Computer,1990,23(4):74-86.

[3] STEPHEN B.Reed-solomon codes and applications[M].New York:IEEE Press,1994.

[4] 关涛.彩色Data Matrix条码的设计及其若干问题的研究[D].北京:清华大学,2006.

[5] 刘宁钟,杨静宇.三维条码的编码理论和设计[J].计算机学报,2007,30(4):686-687.