（通信与信息系统专业论文）高速二维条码识别算法研究.pdf

高速= 维条码识别算法研究 摘要 摘要 本论文研究的目的：从大容量图像中快速识别二维条码m a x i c o d e 的各种算 法，该识别过程将包括定位、解码和纠错。 本文所讨论的算法是基于图像方式工作的。用摄像头采集含有条码的图像 后，在计算机上用软件实现的特定算法对该图像进行分析，识别其中的条码。基 于图像方式的条码识别方法特别适用于二维条码，尤其是矩阵式二维条码的识 别，在自动化领域得到广泛的应用。 本文提出了一种新的基于边缘检测的方法，能实现对m a x i c o d e 边界的精确 定位，该算法不需要对图像进行复杂的计算，如傅立叶变换，图像旋转( 坐标映 射1 ，矩不变等，它充分利用了m a x i c o d e 本身的特点，包括其中心定位标志、方 向模块、条码四周的静区等，用相对简单的计算来实现对m a x i c o d e 的定位。在 准确定位的基础上参考m a x i c o d e 的编码规则，用不同的方法对m a x i c o d e 的不同 信息进行解码，包括结构化收件人信息的解码和普通信息的解码。识别的最后本 文采用p e t e r s o n g o r e n s t e i n - z i e r l e r 纠错算法实现对解码得到的m a x i c o d e 信息进 行纠错。 整个识别过程简单易行，容易理解，大大节省了图像处理的时间，符合识别 系统实时性的要求，并具有一定的鲁棒性，可对不同大小和角度或受到一定程度 破坏的条码进行快速的识别，经实际检验基本满足技术要求。 关键词：二维条码m a x i c o d e r e e d s o l o m o n 码 p e t e r s o n g o r e n s t e i n z i e r l e r 纠错算法 作者：冯宇梁 指导教师：施国梁 a b s t r a c t s t u d i e di nt h i st h e s i sa r eas e to ff a s tr e c o g n i t i o na l g o r i t h m sf o ra2 d b a r c o d e ， m a x i c o d e ，e x i s t i n gi nab i gi m a g et h o s ea l g o r i t h m sa r er e l a t e dt ot h r e er e c o g n i t i o n s t a g e s ，i e ，l o c a t i o n ，d e c o d i n g ，a n de r r o rc o r r e c t i o n t h e a l g o r i t h m sp r o p o s e di nt h i st h e s i sa r eb a s e do ni m a g ep r o c e s s i n gt e c h n i q u e s a f t e ra ni m a g ei sc a p t u r e dv i ac a m e r as y s t e m ，i ti s p r o c e s s e dw i t ht h ea l g o r i t h m so n p ct op e r f o r mi m a g ea n a l y s i st od e t e c tt h el o c a t i o n so fb a r c o d e sa n dd e c o d et h e m s u c hai m a g eb a s e d a p p r o a c hi sm o s ts u i t a b l ef o rr e c o g n i z i n g2 d b a r c o d e s ，e s p e c i a l l y m a t r i xs y m b o l s ，w h i c hc a nb ef o u n de x t e n s i v ea p p l i c a t i o n si na u t o m a t i o n s p r o p o s e di nt h i st h e s i si san e w a c c u r a t em a x i c o d eb o u n d a r yl o c a t i o na l g o r i t m ， w h i c hi sb a s e do n e d g e d e t e c t i o n i tt a k e s a d v a n t a g e s o fm a x i c o d ei n h e r e n t c h a r a c t e r i s t i c s ，i n c l u d i n gi t sf i n d e rp a t t e r n ，o r i e n t a t i o np a t t e r n s ，a n dq u i e tz o n e s ，t o l o c a t et h eb a r c o d e si na n i m a g e w i t h r e l a t i v e l ys i m p l ec o m p u t a t i o n s n o t i m e c o n s u m i n gc o m p l i c a t e di m a g ep r o c e s s i n ga l g o r i t h m s ，s u c h a sf o u r i e r t r a n s f o r m a t i o n ,i m a g e r o t a t i o n ( c o o r d i n a t ec o n v e r s i o n ) ， m o m e n t u mi n v a r i a n t c o m p u t a t i o n s ，e ta 1 ，a r e n e e d e d a f t e rb a r c o d e sa r e l o c a t e d ，t h e y a r ed e c o d e d a c c o r d i n gt om a x i c o d e se n c o d i n gr u l e s t h em e s s a g e sd e c o d e di n c l u d eb o t hn o r m a l m e s s a g ea n ds t r u c t u r e dc a r r i e rm e s s a g e i no r d e rt od e a lw i t ha n yp o t e n t i a ld a m a g e s t ot h eb a r c o d e sa n do t h e r p o s s i b l e e r r o r s ，a p e t e r s o n - g o r e n s t e i n - z i e r l e re r r o r c o r r e c t i o n a l g o r i t h m i s e m p l o y e dt o f i n da n dc o r r e c t a n ye r r o r s i nt h ed e c o d e d m e s s a g e t h ec o m p l e t er e c o g n i t i o np r o c e d u r ei s s i m p l ea n de a s yt ou n d e r s t a n d i t si m a g e p r o c e s s i n ga l g o r i t h m s a r er o b u s ta n dt i m e e f f i c i e n t ，t h u s c a nm e e tr e a l - t i m e r e q u i r e m e n t si nr e a l l i f ei n d u s t r ya p p l i c a t o n s t e s tr u n ss h o wt h a tt h ea l g o r i t h m sa r e f a s ta n dn o ts e n s i t i v et oi m a g ea n db a r c o d es i z eo ro r i e n t a t i o n k e y w o r d s ：2 d b a r c o d e s ；m a x i c o d e ；r e e d s o l o m o nc o d e s p e t e r s o n - g o r e n s t e i n - z i e r l e r a l g o r i t h m 1 1 1 a b s t r a c t s t u d i e so nt h eh i g h - s p e e dr e c o g n i t i o na l g o r i t h m sf o r2 - db a r c o d e s w r i t t e nb y f e n gy u l i a n g s u p e r v i s e db y s h ig u o l i a n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已 经发表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书 而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确 觚删一膈猕醐的篙名：滔宇哭同期： p研究生签名：彤1 刀同期： 。7o ” 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学沦文合作部、 中国社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以 公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大 学学位办办理。 研究生签名： 导师签名： 邀日期：4 3 0 日期： 高速二维条码识别算法研究第一章引言 1 1 二维条码概述： 第一章引言 条形码技术是在计算机技术与信息技术基础上发展起来的一门集编码、印 刷、识别、数据采集和处理于一体的新兴技术，是自动识别和数据采集技术 a i d c ( a u t o m a t i ci d e n t i f i c a t i o na n d d a t ac a p t u r e ) 的一个重要组成部分【1 1 1 2 。条码技 术最早产生于上世纪4 0 年代，自7 0 年代起发展迅速，在交通运输、医疗卫生、 仓储、邮电、公共安全及生产自动化等方面得到广泛的应用，极大地提高了数据 采集和信息处理速度，改善了人们工作和生活环境，提高了工作效率，并为管理 的科学化和现代化做出了很大的贡献。 随着科技的发展，传统的一维条码在某些领域已经不能满足社会的需要。传 统的一维条码仅仅是对“物品”的标识，而不是对“物品”的描述，因此信息容 量较小，对数据库过度依赖，在没有数据库和联网不方便的情况下受到限制。于 是二维条码应运而生。 作为一种新兴的信息存储方式，二维条码除了具有一维条码制作简单、成本 低、信息采集速度快等优点外，还有以下几个主要的优点【3 】【4 】： 高密度：二维条码通过利用垂直方向的尺寸来提高条形码的信息密度，通常 情况下其密度是一维条码的几十到几百倍。 具有纠错功能：一维条码信息量较小，其校验信息一般只能用来检查是否出 现错误，而不能纠正条码中的错误，当条码损坏较为严重时，一维条码采取的拒 绝读取的方式避免条码被错误地读取。二维条码一般都含有比一维条码多得多的 信息量，比一维条码更容易受到损坏，因此二维条码引入错误纠正机制保证信息 正确读取。 可表示多种语言文字：多数二维条码具有字节表示模式，这样就可设法将各 种语言文字信息转换成字节流，然后再将字节流用二维条形码表示。 安全性强：二维条码具有很强的错误修正能力，在加上其防伪功能，大大增 加了数据的安全性。 可表示图像数据：二维条码可以表示字节数据，而图像多以字节形式存储， 第一章引言高速二维条码识别算法研究 因此使图像的条码表示成为可能。 可引入加密机制：二维条码在保存图像信息时可进行加密，识别时，再加以 解密恢复原始图像，这样可防止证件、卡片等的伪造。 由于二维条码上述优点，可以利用它来解决以下几个传统一维条码不能很好 解决的问题： 1 1 对“物品”进行精确描述。 2 ) 在远离数据库和不便联网的地方实现数据采集。 3 1 表示包括汉字在内的小型数据文件。 4 ) 在有限的面积上( 如电子芯片上) 表示大量信息。 5 1 防止各种证件、卡片及单证的伪造。 与一维条码一样，二维条码也有许多不同的编码方法或称码制。就这些码制 的编码原理而言，通常可分为线性堆叠式二维条码、矩阵式二维条码和邮政码三 大类 4 】【5 1 。 堆叠式二维条码形态上是由多行截短的一维条码在纵向堆叠而成的，其数据 以成串的数据行来显示。这类二维条码在校验原理，识读方式等方面继承了一维 码的特点，识读设备与条码印制兼容一维条码技术。但由于行数的增加，每行相 对一维条码较小，在行的鉴别，译校算法等方面不完全相同于一维条码。有代表 性的堆叠式二维条码有p d f 4 1 7 ，c o d e l 6 k 和c o d e4 9 码等。 矩阵式二维条码与堆叠式二维条码明显不同，它是在一个矩阵空间中通过黑 白象素在矩阵中的不同分布进行编码，其数据是以二维空间的形态编码的，是建 立在计算机图像处理技术及组合编码原理等基础上的一种新型图形符号自动识 读处理码制。矩阵式二维条码具有很高的信息密度，可以作为包装箱的信息表达 符号。它可被二维的c c d 图像式阅读器识读，并能以全向的方式扫描。典型的 矩阵式二维条码有d a t am a t r i x ，m a x i c o d e ，q rc o d e 等。 邮政码相对应用较为专门，它是通过不同长度的条进行编码，主要用于邮件 编码，如：p o s m e t 、b p o4 s t a t e 。 图1 1 给出了典型的堆叠式二维条码和矩阵式二维条码的图形，左边的是 p d f 4 1 7 条码，它是目前使用最为广泛的堆叠式二维条码，同时也是壤常见的二 维条码；右边的是d a t am a t r i x 条码，它是一种典型的矩阵式二维条码，主要用 2 亘垄兰丝墨塑望型兰堇堑塞蔓二童! ! 点 于电子行业小零件的标识。 础 图1 - 1 典型二维条码 箧 1 2 国内外二维条码发展现状及发展前景州嘲嘲 d a t a 崔a t r i x 国外对二维条码的研究始于8 0 年代末，已经研制出p d f 4 1 7 、c o d e1 6 k 、 m a x i c o d e 、d a t am a t r i x 等多种二维条码，目前已进入应用阶段。美国等发达国家 已经在身份证、驾驶证等证件、车辆管理、邮件分拣及税务报关等许多领域使用 了二维条码。一些政府机关和工业团体也使用二维条码来提高工作效率。 另外，在国外二维条码的标准化也已经开始了十几年，象p d f 4 1 7 、c o d e1 6 k 、 c o d e 4 9 、m a x i c o d e 与d a t a m a t r i x 等二维条码已成为国际自动识别设各制造商协 会( a i m ) 与美国标准协会( a n s d 的符合标准。欧洲标准化协会( c e n ) 也起草了 p d f 4 1 7 等条码的欧洲标准。新成立的i s o i e c j t c i s c 3 l ( 国家标准化组织与国 际电工委员会的第一联合委员会的第三十一分委员会) 也起草了p d f 4 1 7 、c o d e 1 6 k 、m a x i c o d e 及d a t am a t r i x 四种二维条码的i s o 标准，并于1 9 9 7 年6 月完成。 我国是一个幅员辽阏，人口众多的国家，是一个潜力巨大的新兴市场。有关 二维条码的研究和应用起步相对一些发达国家较晚，大部分技术及设备目前仍是 从国外引进，进口的条码识读设备必须和与它对应的编解码软件配套使用，导致 二维条码使用成本较高，实际应用范围很小。随着我国社会和科技的进步，尤其 是加入世贸进程的不断深入。二维条码的优势越来越突出，因此己受到我国条形 码管理部门和有关政府部门的重视。中国物品编码中心自1 9 9 3 年便开始了对二 维条码技术的探索和研究，现己出版了我国第一本有关二维条码技术的专著二 维条形码技术。另外，许多科研单位、开发公司、大专院校也已开始着手进行 第一章引言高速二维条码识别算法研究 二维条形码技术的应用开发。 目前，许多部门已有使用二维条码用于人员管理和物品管理的愿望，如：公 安部门欲将二维条形码应用于身份证和流动人员管理上，进出境管理部门正在探 讨将二维条形码应用于护照上，海关也尝试将其用在报关单上。根据目前状况， 预计未来五年内，二维条形码在我国将有较大的发展。 1 二维条形码将首先在我国的人员管理中得到广泛应用 随着我国社会和科技的进步，对人员进行现代化管理的需要与日俱增，这就 需要在证件上对管理对象进行精确的描述。二维条形码这种成本优势较大的自动 技术较易被各个管理部门所接受。在我国的入口管理综合数据库较难建立的情况 下，一个随身携带的身份证卡上的二维条形码便可包括其身份的全部信息，并还 可包括其照片信息。这种技术的推广将比在发达国家更具优势。 2 二维条形码亦将在物流管理中得到较大发展 用二维条码描述物品是二维条码应用的又一方面。在货物的存储、运输中对 其进行描述必不可少。现在的情况大多是用自然语言描述，这大大影响了信息的 采集速度和精度。将二维条形码应用于物流，即将二维条形码制作在货物的包装 上，这是其它自动技术( 如i c 卡) 无法做到的。二维条码在物流的应用必将加快 物流管理现代化的进程。 总之，二维条码的应用深度和广度将在条形码技术发展中起着重要的更新换 代作用，是条码发展史上的里程碑。二维条码技术的成功应用，必定会极大地推 动我国乃至世界的信息化水平，提高社会管理效率和经济效益。因此对二维条码 的研究有着重要的意义和实用价值。 由于二维条码有着传统一维条码无法比拟的众多优势，近几年国内外许多学 者、科研人员对二维条码进行了广泛深入的研究，发表了许多有关二维条码的论 文，对二维条码的发展前景、应用领域、编解码以及识别方法进行了讨论和研究 【9 】1 1 0 】1 1 1 m 1 2 】【1 3 1 。其中有关二维条码识别方法的文献有刘宁钟，杨静宇提出的基于 傅立叶变换的二维条码识别技术以及基于投影算法的二维条码识别技术， 这两种技术可以有效地去除几种常见的图像噪声对条码识别的影响。甘岚等提出 了一种基于亚像素边缘检测的二维条码识别算法【1 6 】，能有效地解决边缘模糊对条 码识别的影响，郑河荣等提出基于h o u g h 变换的图象矫正方法”7 j 结合条码自 4 高速二维条码识跳算法研究第一章引言 身的特征，通过一定的预处理，实现二维条码图象的快速矫正。 1 3 二维条码m a x i c o d e l l 8 】【1 9 】【2 0 】 m a x i c o d e 也有人称u s s m a x i c o d e n i f o r ms y m b o l o g ys p e c i f i c a t i o n m a x i c o d e ) 是由美国联合包裹服务公司u p s ( u n i t e dp a r c e ls e r v i c e ) 研制的一种中 等容量、尺寸固定的矩阵式二维条码 2 l 】1 2 2 1 ，用于存放较为详细的包裹资料，方 便包裹搜寻和追踪。 作为世界上最大的快递承运商与包裹递送公司，u p s 物料搬运系统每天要处 理成千上万件货物，且货品种类繁多，信息量大，包装规格不一，条码标签的方 向具有随机性，货品通过扫描器速度较快，一般可达2 5 米以上。要快速准确地 读取货品信息，传统的一维条码已不能很好的满足要求，因此u p s 从1 9 8 7 年就 开始研究设计一种新型的二维条码，并于1 9 9 2 年成功研制出m a x i c o d e 这种矩阵 式二维条码。它除了具有传统二维条码的优点外，其中心定位标志与方向无关， 因此能够更好地适应传送带系统环境的要求。 从外观来看m a x i c o d e 由位于符号中央的三个等间距同心圆环( 或称公牛眼 b u l le y e ) 定位图形( f i n d e rp a t t e r n ) 及其周围六边形蜂巢式结构的模块组所组成， 这种排列方式使得m a x i c o d e 可以从任意方向快速扫描。每个m a x i c o d e 共有8 8 4 个六边形模块，分成3 3 层围绕着中央定位图形，每一层交替由3 0 个或2 9 个模 块组成。总共8 8 4 个模块中有1 8 个模块作为方向标志，分成6 组，位于中心定 位图形的附近，主要作用是确定条码的方向，另有2 个模块未使用，其余8 6 4 个 模块保存信息( 包括实际数据和纠错字符) 。每个m a x i c o d e 符号四周有空白的静 区，包括空白静区在内，m a x i c o d e 尺寸固定为2 8 1 4 m m 2 6 9 1 m m ，约1 平方英 寸。其外观与中心放大图如图1 2 所示。 第一章引言 高速二维条码识别算法研究 m a x ie o d e 中心敲大围 从信息存储来看，m a x i c o d e 将其存储的信息分为两个部分。主要信息 ( p r i m a r y m e s s a g e s ) $ 口次要信息( s e c o n d a r y m e s s a g e ) ，主要信息包含的资料较少。 主要用来储存高安全性的资料，包括2 0 个字符( c o d ec h a r a c t e r ) 。次要信息用于 存放额外的信息，如来源地、目的地等人工分类时所需的重要资讯，可存放1 2 4 个字符。m a x i c o d e 资料容量最大为9 3 个字符，若全部存放数字字符，则可存放 1 3 8 个。 m a x i c o d e 的8 6 4 个信息模块构成1 4 4 个字符，每佃字符由6 个模块组成， 每个模块表示一个二进制位，黑色模块表示“1 ”，白色模块表示0 。因此字 码集共有6 4 个，范围为0 - - 6 3 ，二进制表示为0 0 0 0 0 0 1 1 1 1 1 l 。通常六个模块排 成3 层，顺序为右上至左下，如图1 3 所示，少数字符( 1 - - 9 、1 3 7 - - 1 4 4 ) 模块由 于受m a x i c o d e 整个符号的影响采用特殊的排列方式，详细情形参见m a x i c o d e 规范 2 0 】。 1 证3 b = 最高有效使元 l 岛= 最低有效位元 图卜3m a x i c o d e 符号模块排列 u p s 于1 9 9 2 年在新泽西对m a x i c o d e 进行小型的测试。1 9 9 3 年首先在密歇 6 高速二维条码识别算法研究 第一章引言 根州建立全自动的流水线，运用m a x i c o d e 实现对货物分类和跟踪，当时传送带 宽度为4 2 英寸，速度为3 5 0 英尺分钟。目前u p s 运用m a x i c o d e 能够实现对速 度高达5 5 0 英尺分钟的传送带上的货物进行实时的分析处理，实现对物品的分 类跟踪。 m a x i c o d e 读取设备同视频摄像机一样是基于电荷耦合器件c c d ( c h a r g e c o u p l e dd e v i c e ) 技术的。通常由c c d 读取设备获取条码的图片，然后解码软件 进行图像处理。对于传送带一级的系统，通常采用固定的摄像机对传送带进行图 像捕捉，获取传送带上指定区域的图像( 一般较大) ，然后再由计算机端解码软件 分析图像，定位其中条码，并进行解码，输出结果，此类系统实时性的要求较高。 本文所讨论的算法是针对后一种系统来设计的。 目前m a x i c o d e 已被选定为国际自动识别制造商协会( a i m ) 标准，汽车工业行 动组a i a g ( a u t o m o t i v ei n d u s t r ya c t i o ng r o u p ) 也选定它作为产品分类和跟踪的标 准，美国国家标准学会在其m h l 0 8 3 中推荐m a x i c o d e 为最适合用于物料搬运业 务分类和跟踪的条码，另外美国国防部也推荐m a x i c o d e 实现物品的分类和跟踪。 m a x i e o d e 的i s o 标准也于1 9 9 7 年6 月完成。 1 4 课题研究的内容和目的 经过查阅大量的论文资料发现，国内对于二维条码的研究主要是针对 p d f 4 1 7 这种二维条码进行的，对于其它的二维条码研究较少【1 3 1 【1 4 】1 1 5 】。本课题主 要研究m a x i c o d e 这种二维条码的识别，包括定位、解码、纠错等各个部分。由 于m a x i c o d e 是矩阵式的二维条码，它只能被二维的c c d 图像式阅读器识读，因 此识别是基于图像的，这能够很好的克服传统的条码扫描仪直接采用模拟电路探 测条码，使条空分界线钝化，降低以后操作中对信号检测的准确性的缺点【“】。就 应用领域来看m a x i c o d e 的主要应用领域是物流方面，用来实现物品的分类和跟 踪，因此其采集得到的含条码的图像较大，一般为2 0 4 8 4 0 9 6 象素以上，容量 可达8 兆以上，另一方面识别m a x i c o d e 条码的实时性要求却很高，对于一个速 度高达2 5 米秒的传送带，若相邻货品间隔至少为3 0 厘米，货品本身大小为2 0 厘米以上，则条码识别时间只有约2 0 0 毫秒，对于如此大的图像，如此短的处理 时间，依靠传统的方法很难实现，因此我们提出采用一种基于边缘检测的新方法， 第一章引言高速二维条码识别算法研究 实现对条码的快速准确识别。该方法并没有象传统的条码处理方法一样，对图像 进行复杂的计算，如傅立叶变换，图像旋转( 坐标映射) ，矩不变等【12 】【2 3 1 1 2 4 1 ，而是 充分利用了m a x i c o d e 本身的特点，包括其中心定位标志、方向模块、条码四周 的静区等，根据这些特点设计识别方法，以期达到对m a x i c o d e 这种二维条码的 快速识别。 下面简要介绍本文所描述的m a x i c o d e 识别过程： 1 对整个图像进行预处理，找出r o i ( r e g i o n so f i n t e r e s t ) 。预处理对整个图 像进行，将图像分为相同大小的子块，采用一定方法检测图像水平和垂 直方向的边缘，记录各个图像子块内边缘的个数，与预先定义的阈值相 比较，大于阈值的即r o i 。 2 用8 连通方法对上述得到的r o i 进行聚类，找出可能含有m a x i e o d e 的 区域。 3 在聚类后的区域内查找条码，定位条码的边界。大致过程如下：用本文 所提出的中心定位算法查找m a x i e o d e 条码的中心，用双平行线边界定位算法定 位条码边界；然后判断条码方向；最后用抽样边界修正算法校正边界。 4 根据边界读取条码各模块信息，参考m a x i e o d e 编码的方法，解码获取条 码所含的信息。解码时针对m a x i c o d e 不同的模式，采取不同的解码方案读取条 码中的信息，包括普通信息和可能含有的结构化收件人讯息。 5 用p e t e r s o n - g o r e n s t e i n - z i e r l e r 算法检查并纠正解码获取信息中可能含有 的错误。m a x i c o d e 的纠错码采用r e e d - s o l o m o n 码，而用 p e t e r s o n g o r e n s t e i n - z i e r l e r 算法是比较常用的r s 码解码算法，该算法简单易行， 在错误码数较少的情形下可以达到很好的效果。 8 高速二维条码识别算法研究第二章基于边缘检测的m 8 x i c o d c 定位 第二章基于边缘检测的m a x i c o d e 定位 2 1 边缘检测算法概述 边缘检测在图像分析和处理中占有十分重要的位置 2 5 】【2 6 】。常用的边缘检测 算法以及波形分析方法等2 6 【2 7 】。 是边缘。以上得到的边缘位置成带状，因此还需进一步细化【2 6 】，细化后得到宽度 有s o b e 算子，它是x ，y 轴向的2 个模板f 立立三。 三 i 却，将模板置 i 1 ：三 ，模板的使用方法与梯度方法基本相同。 9 第二章基于边缘检测的m a x i c o d e 定位 高速二维条码识别算法研究 很好地识别条码内部的边缘。 二维条码中存在许多边缘，一个适当的边沿检测算法对于本文所述的算法 有重要意义。经过比较，本文介绍的算法采用波形峰值检测法来检测边缘。边 缘检测在下面m a x i c o d e 定位的各个步骤都有涉及。 2 2m a x i c o d e 定位过程 本文所述的m a x i c o d e 识别方法主要建立在其边界的准确定位的基础上，边 界的准确定位在整个识别过程中占相当重要的地位，是后面m a x i c o d e 正确解码 和纠错的基础，试验证明边界定位所花费的时间一般占整个识别过程的8 0 以 上，因此边界定位算法的优劣直接影响整个条码识别的结果。 本文所采用的m a x i c o d e 定位过程大致如下：首先对图像进行预处理，即 特征提取，找出r o i ( r e g i o n so f i n t e r e s t ) ；第二步，用8 连通方法聚类r o i ；第 三步，用中心定位算法查找m a x i e o d e 条码可能的中心位置：第四，用双平行线 边界定位算法定位条码较为精确的边界；第五，定位m a x i c o d e 方向模块，判断 条码方向；最后，根据抽样边界修正算法校正边界。 2 2 1 图像预处理 图像预处理在图像分析系统中被广泛应用，主要进行一些简单的特征分析， 方便后续处理【2 7 】嘲。本文所涉及的图像来自c c d 摄像机对传送带上包裹的图 像捕捉，按照系统要求一般为2 0 4 8 4 0 9 6 象素，图像文件大小可达8 m 。对于 这样大的图像文件，若对每个象素都进行分析处理，必然要花费太多的时间， 不能满足系统实时性的要求。因此有必要对图像进行一定的预处理。预处理可 在扫描图像的同时进行的，这样就利用了扫描图像的时间，它对图像进行简单 的运算，分析结果找出r o i ，并作标记。后续处理只需对r o i 进行，这样货物 间隔的时间可全部用来处理图像中的r o i 。 预处理方法如下：对整个图像进行扫描，记录水平和垂直方向边缘( 本文所 指的边缘都是指从黑到白的边缘，以后不再进行说明) 的位置。将整个图像分成 若干个a x 口的图像块，根据边缘的位置，统计每个图形块内水平和垂直方向边 缘的总数m 。条码一般由许多黑白成分构成，因此条码出现的位置边缘个数较 1 0 高速二维条码识别算法研究第二章基于边缘检测的m 酞i c o d e 定位 多。选取适当的阈值，比较m 。，h o ，若埘， h o ，该图形块可能含有部分条码， 对该数据块作标记。具体实现时建立二维数组b l o c k e d g e ，每个数组成员对应 一个图像块，将r o i 对应的成员置1 ，其余置0 。 预处理中，参数日和h 。的选择至关重要。若过大，图像块过大，不能起到 很好的筛选作用：口过小，每个图形块内边缘数目较少，不能很好的区分条码和 非条码区域。若h 。选择过大，实际的条码有可能被忽略；h 。过小，同样不能区 分条码和非条码区域。经过实际的试验，选取口= 5 6 ，h o = 2 4 ，可以达到较为满 意的结果，可疑的图像块一般只有原图像的5 左右。图2 1 是对一张实际拍摄 的包裹图像进行预处理后的结果，图中每个小方格代表5 6 x5 6 的图像块，左上角 有1 ”标记的为r o i 。 2 2 2 r o i 聚类 图2 - l 图像顸处理 经过上述预处理得到一组r o i ，用8 连通方法对r o i 进行聚类，具体实现 过程如下： 1 初始化变量。图形块类的总数c l a s s n u m = 0 ，二维数组b l o c k c l a s s n o 】 用于保存图形块对应类的序号，每个成员对应一个图形块，初始值为2 5 5 ，表示未 第= 章基于边缘检测的m a x i c o d c 定位 高速二维条码识别算法研究 归类。 2 正向扫描，从上到下从左到右依次查询对应图像块的b l o c k e d g e i j ，若 值为0 略过，为1 则根据图形块位置进行下列相应处理： ( 1 ) 若为第一行第一列图形块，图形块类的总数加1 ，当前图形块属于新类。 ( 2 ) 若为第一行非第一列图形块，根据其左面一个图形块是否属于r o i 做如 下处理： 左面一个图形块属于r o i ，当前图形块与左面图形块属于同一类。 左面一个图形块不属于r o i ，图形块类总数加l ，当前图形块属于新类。 ( 3 ) 若为第一列非第一行图形块，根据其正上方一个图形块是否属于r o i 做如下处理： 上面一个图形块属于r o i ，当前图形块与上面图形块属于同一类。 上面一个图形块不属于r o i ，图形块类总数加1 ，当前图形块属于新类。 ( 4 ) 若为最后一列非第一行图形块，根据其左、左上、上图形块是否属于 r o i 做如下处理： 左、左上、上图形块均不属于r o i ，图形块类总数加1 ，当前图形块属于新 类。 左、左上、上、右上图形块至少有一个属于r o i ，找出属于r o i 图形块对 应的类序号的最小值，当前图形块属于该类。 ( 5 ) 图形块既不属于第一行又不属于第一列、最后一列，根据其左、左上、 上、右上图形块是否属于r o i 做如下处理： a ) 左、左上、上、右上图形块均不属于r o i ，图形块类总数加1 ，当前图 形块属于新类。 b ) 左、左上、上、右上图形块至少有一个属于r o i ，找出属于r o i 图形 块对应的类序号的最小值，当前图形块属于该类。 3 从下到上从右到左反相扫描，过程与2 类似。 4 重复进行正相和反相扫描，直到有一次扫描后，聚类结果与前一次扫描 的聚类结果相同，聚类结束。 图2 2 下面给出上述8 连通r o i 聚类正向扫描的流程图，其中c u r c l a s s n o 用于存放当前图形块所属类的序号，从1 开始计数；n o l 、n 0 2 、n 0 3 、n 0 4 对 应某图形块左、左上、上、右上图形块的类序号，如果相应图形块不存在或不 1 2 高速二维条码识别算法研究 第= 章基于边缘检测的m a x i c o d e 定位 属于r o i ，对应值为2 5 5 。 图2 28 连通r o i 聚类正向扫描的流程图 3 第二章基于边缘检测的m a x i e e d e 定位高速二维条码识别算法研究 对于聚类的结果，为方便后续处理，对每个类创建一个矩形r e c t i 】，要求 矩形包括该类所有图形块。由于r o i 并不包括条码全部，故在不超出图像边界 的情况下，将矩形适当扩张，得到e x t e n t r e c t i 。e x t e n t r e c t i 为需要进行后续 处理的图像。 2 2 3m a x i c o d e 中心定位算法 查找中心定位标志比较传统的方法是模板 匹配法( 如图2 3 ) ，图中用方波构建一个一维 定长模板，长度为k 。对于灰度图像方波高电 平用p 个2 5 5 组成，低电平用q 个0 组成，因圆 环宽和环间间隔几乎相等，故p = q 。例如取 p = q = 2 得到模板序歹f j ( 2 5 5 、2 5 5 、0 、0 、2 5 5 、 r m 厂 广 图2 - 3 方波模板 2 5 5 、0 、0 、2 5 5 、2 5 5 、0 、0 、2 5 5 、2 5 5 、0 、0 、2 5 5 、2 5 5 ) 。取图像的行，求 模板与该行开始的k 个象素值的互相关值，然后依次移动模板，记录互相关值并 与预先定义好的阈值比较，如大于阈值，则记录模板中心的位置。然后用同样的 方法在模板中心所在的列进行匹配。如行列都匹配，就认为找到m a x i c o d e 的中 心。模板匹配法容易理解和实现，但存在明显缺陷。当处理的图像分辨率不同时， 就应改变模板大小，即p 和q 的值。对于一幅未知的图像，需要用不同大小的模 板去匹配，并从中选择合适的模板。 本文采用一种简化的算法定位m a x i c o d e 中心定位标志，这种简化的算法充 分利用了m a x i c o d e 中心圆环的环间间距几乎相等这一特点。 实现过程：用边缘检测算法对r o i 聚类后的若干个e x t e n t r e c t 的各行分 别从左到右扫描，记录边缘的位置。然后对得到的边缘位置进行检查，寻找六 个几乎等间隔的边缘。由于其它一些字符和图案也可能包含六个等间隔的边缘， 这样的简化算法将造成大量“虚警”，为了降低虚警概率，将上述过程在水平、 垂直、4 5 度、1 3 5 度四个方向上进行，若以某点为中心四个方向都检测到等间 隔边缘，就认为找到一个m a x i c o d e 条码中心定位标志。其余三个方向的搜索范 围由水平方向的六个等间隔估计，因为条码中心标志由于拍摄角度等不同会产 生形变，为避免将定位标志周围的模块误认为圆环，搜索范围相对较小，因此 高速二维条码识别算法研究 第二章基于边缘检测的m a x i c o d e 定位 某些方向上可能找不到六个等间隔边缘， 方向的六个边缘的平均值，联合纵坐标， 流程图如图2 - 4 所示。 只能找到五个甚至四个边缘。求水平 得到条码中心的位置。中心定位算法 图2 4 中心定位算法流程图 用这种简化的中心定位方法找到的中心位置并不十分精确，偏差在几个象 素以内，但并不影响后面m a x i c o d e 边界的精确定位。图2 - 5 ( a ) 、( b ) 给出了中心 定位算法在实际图像上运行的两个例子，图中白色的点表示四个方向找到的等 间隔边缘，中心的自点为估计出的条码中心。 第= 章基于边缘检测的m a x i c o d e 定位 高速= 维条码识别算法研究 ( a ) ( b ) 图2 - 5 中心定位算法运行结果 2 2 4 双平行线边界定位算法 一旦找到了m a x i c o d e 的中心，接下来需要查找它的四条边界。我们所采用 的双平行线定位算法首先估计条码的大小，进一步估计可能出现边界的范围( 搜 索范围) ，然后用一种方法从中心产生双平行线对，当某一对平行线满足特定要 求时认为找到条码的边界，四个方向都找到边界后，延长平行线求得交点，连接 四个交点便得到条码的边界。 1 估计条码大小 利用上述中心定位方法得到六等间隔可以粗略估计条码的大小。假设六等间 隔的平均值为，个象素，根据m a x m o d e 标准规定，这个间隔的理论值为0 6 7 r a m ， 条码长边理论值为2 8 1 4 r a m ，因此可估计条码长边x = 4 2 t 个象素，为保守起见， 估计条码长边i i n e l e n g t hz4 4 t 个象素。 2 双平行线的产生方法 如图2 - 6 所示，从条码中心出发以一定的角度口( d 为半径与水平线的夹角 的弧度值) ，半径r 取一点p ，再以该点为中心，在垂直于半径的方向作一条线 段a b ，线段长度为工。在第一条线段外侧，作与a b 平行的线段c d ，长度也为 x ，两平行线间隔尽可能小，一般取1 。 高速二维条码识别算法研究 第二章基于边缘检测的m a x i c o d e 定位 图2 6 双平行线的产生 用双平行线定位m a x i c o d e 边界 首先检测右上边界。按照前面平行线产生方法，角度a 取值范围o 。9 0 。， 以4 5 0 为中心每次调整0 5 。，角度依次为4 5 0 、“5 。、4 5 5 0 、4 4 。、4 6 0 ，对于每个 角度r 取值范围o 4 l i n e l e n g t h o 6 l i n e l e n g t h ，与角度的调整方法相同，是以中 心向两边交替调整。当内侧平行线段上检测到边缘数大于某一阈值( 经过试验， 取5 比较适合检测m a x i c o d e ) ，而外侧平行线上没有检测到边缘对( 为增强鲁棒 性可允许第二条平行线上检测到一个边缘) ，认为找到条码的边界。 选择不同的角度范围：对于右下边界，d 取一n 2 0 ；对于左下边界，a 取 一石z c 2 ；对于左上边界，a 取，r 2 玎。用几乎与检测右上边界同样的方法 可检测到其余三条边界。将获得的四条平行线段适当延长，求四个交点，即条码 的四个顶角坐标。 我们利用m a x i e o d e 的对称特性，大大减少循环的次数，节省边界查找的时 闾。假设找到右上边界时，半径为r ，角度为。则其余三个边界的半径可估 计为民，右下边界角度可估计为d 。一疗2 ，左下边界角度估计值为a 。一万，左 上边界角度估计值为+ z r 2 。然后只需在估计值附近的小范围内循环搜索符合 条件的边界即可。由于m a x i c o d