多维连续型矩阵式条码的编码理论与系统设计.pdf

1多维连续型矩阵式条码的编码理论与系统设计∗裴颂文1+, 吴百锋1 1(复旦大学 计算机科学技术学院, 上海 200433) 摘 要: 现有的多维条码技术大多以单个码字为信息记录体,无论其密度多少,都以承载固定容量信息为基本特点.这种结构不适宜承载大容量信息,尤其是容量不确定的多媒体信息,阻碍了这种方便、 实用、 成本低廉的自动识别技术的广泛应用.提出一种新型的多维连续型矩阵式条码(C-Matrix),以连续分布、个数可变的图形矩阵码作为条码的基本结构,理论上具有存储无限容量的数据并支持快速实时译码的特点.为实现多维连续型矩阵式条码译码的实时性,还提出了基于动态扫描线的快速定位点检测算法、双交叉动态扫描识别算法、快速的RS(Reed-Solomon)译码算法和统一的条码识别框架.最后完成了原型系统设计,并通过实验证明了该系统的正确性和实用性. 关键词: 连续型矩阵式条码; 快速定位点检测算法; 双交叉动态扫描识别算法; 里德-索罗蒙码 中图法分类号: TP391 Encoding Theory and System Design of Multi-dimensional Continuous Matrix Barcode PEI Song-Wen1+, WU Bai-Feng 1(School of Computer Science, Fudan University, Shanghai 200433) Abstract: Most of multi-dimensional barcodes currently use single block as their basic carrier, no matter how high density of them, they just carry information with fixed capacity. However, it’s not suitable to carry large capacity of information, especially multi-media information without fixed capacity, and thus stunts the development of automatic identification technology. So, a kind of novel multi-dimensional continuous matrix barcode(C-Matrix) of which is comprised continuous and variable matrix blocks is proposed. C-Matrix is able to carry unlimited data theoretically and can be recognized and decoded in real-time. For the sake of recognizing C-Matrix in real-time, a fast fiducial points detection algorithm based on dynamic scan lines, double cross dynamic scanning algorithm, fast algorithm of decoding RS code and a uniform framework of recognizing barcode are proposed. Finally, a prototyping system for C-Matrix is implemented and examined effectively and practically. Key words: continuous matrix barcode (C-Matrix); fast fiducial points detection (FFPD); double cross dynamic scanning (DCDS); Reed-Solomon (RS). 条码成为近年来计算机自动识别领域内的一个研究重点和热点,条码技术的应用正逐渐融 入到出版、交通运输、商贸、制造业、医疗卫生和物流等领域.但是,目前国内外研究机构对于 条码在多媒体数据领域的研究和应用尚不成熟.近年来,在多媒体条码方面的初步应用有承载简 短视频的条码、彩信条码、彩铃条码和条码式电子客票等.这些多媒体条码基本实现了存储较*本课题的研究受到上海市科委重点科技攻关项目(045115015),上海市重点学科建设项目(B114)和超微半导体(中国)有限公司大学合作计划基金的资助(080318-3).裴颂文(1981－),男,湖南邵东人,博士,主要研究领域为嵌入式系统设计,计算机系统结构; 吴百锋(1964－),男,硕士,教授,博士生导师,主要研究领域为嵌入式系统设计,纠错编码理论,计算机系统结构. 2大容量数据的目的.但是,这类条码目前还缺乏存储不确定的大容量数据的能力.特别是针对盲 人的有声电子读物出版行业、语言不通的出境旅游宣传、电子商务、电子票务和音像出版行业 等领域,多媒体条码的研究和应用尚处于起步阶段. 1 条码的现状和最新研究进展 条码的种类繁多,呈现形式各异.按存储方式划分主要有一维条码、 二维条码和三维条码等; 按外观形状划分主要有线性码、堆积码和矩阵码或棋盘码等;按色彩划分主要有黑白条码和彩 色条码.最常见的一维条码 UPC/EAN 码是黑白条状码.由于一维条码只在条码的水平方向存储 数据,所以其存储容量低、条码的空间利用率不高. 二维条码除了在条码的水平方向上存储数据外,还在垂直方向上存储数据.目前二维条码主 要有两类,一类是在一维条码的基础上向二维条码方向发展的堆积型.典型的堆积型二维条码是 Symbol 公司研制的 PDF417 码.另一类是矩阵型二维图形编码.典型的矩阵型二维条码是 Denso 公司于1994年9月研制的矩阵二维条码QR Code.除此之外,比较常见的二维条码还有CiMatrix 公司研制的 Data Matrix 码.United Parcel Service(UPS)公司推出的 Maxi Code. Zebra Technologies 研制的 UltraCode 码,该码字有黑白和彩色两种形式. 三维条码除了在水平、垂直两个空间方向上存储数据外,还将色彩作为第三维向量来提高 条码的存储密度.比如,HP 实验室研究一种高保真的图形编码符号以及一套可靠的编码解码系 统[1].Rutgers大学研究适用于多频率多信道超带宽解码系统的树形三重正交二维码[2].Guelph等 大学研究基于二维条码的视力受损者辨别及导引协助系统[3][4].NEC 实验室研究二维条码在手 机摄像头下的应用等[5].Microsoft公司2007年研究成功的高容量彩色条码HCCB,应用在光盘盘 面上①.Imageid 公司研究了彩色条码系统的色彩稳定性和色彩分类方法[6].ColorZip 公司研制的 彩色条码 ColorCode 并提供了相关的多媒体服务②.刘宁钟等[7]对三维 PDF417 条码的理论做了 初步的研究与设计等. 图 1 典型条码: (a)PDF417, (b)QR code, (c)Data Matrix, (d)Maxi Code, (e)2-D UltraCode, (f)3-D UltraCode, (g) HCCB, (h)ColorCode (i) 2-D C-Matrix, (j) 3-D C-Matrix(4 色层), (k) 3-D C-Matrix(8 色层)③ 图1所示的(a)~(e)是典型的二维条码,(f)~(h)是典型的三维条码.但是,这几种典型条码均不 支持存储不确定容量的信息及以快速扫划的扫描方式.在多媒体条码应用领域,音频、视频的容 量要远远大于字符等信息.通常情况下,一块单独的堆积码或者矩阵码码块是无法承载的;同时, 由于各种多媒体数据容量大小各异,就很难确定需要多少块码字组合来存储这些数据.而上述条 码的编码方式大多数是面向单个图形矩阵码的,在用多个单独的条码来表达不确定容量的多媒① ② 3体数据时其空间利用率会很低;另一方面,这种简单的组合方式使得在纠错编码、识别速度方面 存在局限性.使用微型化的手持扫描设备,以快速划扫方式完成大容量信息的实时识别,要求编 码方式能适应因快速移动而造成的条码图像扭曲、 变形等失真.尤其是普通图像传感器(CCD 或 CMOS)因各扫描线扫描时间的差异而产生的非线性失真,而上述条码的编码方式均不具备这种 纠正图形矩阵码非线性失真的机制.此外,快速划扫方式很容易引起光照不均的现象,增加了实 时译码,特别是对三维条码实时译码的复杂性. 因此,对于当前条码在多媒体应用方面,特别是存储不确定容量的多媒体信息上的劣势,我 们提出了多维连续型矩阵式条码(continuous matrix barcode, C-Matrix barcode),如图 1 (i)~(k)所 示.其中图 1(i)是二维连续型矩阵式条码,图 1(j)和(k)分别是 4 色三维连续型矩阵式条码和 8 色 三维连续型矩阵式条码. 2 二维连续型矩阵码 2.1 条码的编码理论 堆积式二维条码是通过设置条码中条、空的编码规则以及二进制逻辑表示方式进行编码 的,其常见的编码方式有模块组配法和宽度调节法两种.然而,矩阵式条码的编码是通过设置固 定矩阵块的大小,点空比和点的散布规则以及二进制逻辑表示方式完成编码的.为了成功设计出 符合要求的多维连续型矩阵式条码,我们总结了设计连续型条码的 4 项基本编码准则: 准则 1 (易识别准则).编码后的条码要求便于快速完成条码定位、校正、纠错、识别四个基 本过程. 准则 2 (抗干扰准则).条码具备抗污损、抗失真、抗形变的要求,设计不同的纠错编码等级, 具备较强的纠错能力. 准则 3 (不定长准则).码字结构不限定长度,理论上能保证由无限个码块组成连续性条码. 准则 4 (掩模准则).在外观表现上,码字中的信息点要求服从 Pasion 分布原则,同类码字采用 统一的掩模标准. 2.2 二维连续型矩阵码的设计 2.2.1 二维连续型矩阵码的结构 考虑到需要增强条码的容错能力,把连续型条码设计成并行的三行连续性矩形,每行矩形图 块均由方形码块组成,如图2所示.条码中的最底一行是最顶一行的冗余复制,顶行或者底行与中 间行组合,就能完整恢复出编码前的数据.基于基本准则3的要求,条码的长度可以根据印刷材料 的宽度自动设置.每个方形码块由四个圆形定位点,两排各八个校验点以及散布其中的信息点组 成.两排校验点主要是为了消除快速扫划过程中图像的非线性失真及辅助纠正定位点圆心,这种 特殊的设计提高了条码的抗干扰能力和条码识别的速度,满足了准则 1 和准则 2 的要求.在二维 码字结构中,信息点中的黑点表示二进制数值”1”,白点表示二进制数值”0”.条码的外观形状来 看,各码块中信息点的分布比较均匀,码块间的形状比较相似,符合准则 4 的基本要求. 该码字用分辨率为 96dpi 的通用打印设备印刷后,三行码块的总高度占 360 个像素,约为 95mm.考虑到以手动设备快速划扫方式识别条码会引起图像失真,我们没有采用类似 QR 码中 的矩形定位点,而设计了圆形定位点.圆形定位点对于扫读过程中的抖动和失真具有很好的抗干 扰性.纠错编码采用了 RS 码,这些特征都符合准则 1 和准则 2 的要求.条码的占空比除了跟条码 的编码方式有关外,还跟打印设备、扫描设备和信息压缩速率有关. 4图 2 二维连续型矩阵码结构图 2.。