二维条形码编译码原理与应用研究
|
摘要
本文简要介绍了二维条形码的特点和编码规则，详细阐述用计算机实现其编码的原理和方法，采用具体实例介绍设计步骤，并给出可同时实现中英文编码的程序设计方法。另外，二维条形码具有一维条码不具备的纠错功能。本文简要介绍了Reed-Solomon纠错码(RS码)原理，重点分析研究它在PDF417二维条形码中的应用方法，并详尽地推导了在迦罗华域GF(929)域内RS码的编译码方法。同时提出一种适用于PDF417纠错编码和译码的查表方法，可以简单确定任意码字在GF(929)内所对应的本原元的幂次。运用该方法可以快速而准确地计算出纠错码生成多项式的系数列以及差错伴随式。显著提高纠错效率。在译码方面本文探讨了一种采用CCD整图读取条码图像的方法，用计算机进行图像分析，特征提取，完成译码的实现方法。还给出了一种基于PDF417二维条码结构特性的算法，该方法设计滤波器滤除噪声部分，再采用点搜索法进一步去除不符合条码边界特点的孤立的点和容易与边界混淆的竖直划痕，最后对条码图像进行复原。实验证明可以有效去除滤波对有效条码边缘的影响，同时保证图像可靠恢复。对于恢复后的条码图像采用改进的边缘检测投影方法译码，降低了对条码纠错等级的要求，大大提高了译码的效率和准确率。
This paper covers the characteristics and basic principles of the design of two-dimensional bar code and detailed examples of its application, including an encoding method for both English and Chinese characters. Two-dimensional bar code possesses the capability of error-correcting which one-dimensional bar code doesn't. So, besides a brief introduction of Reed-Solomon error-correcting code (RS code), this paper also gives a thorough analysis of RS code's application in two-dimensional bar code PDF417, giving detailed error-correcting principles in GF(929). Meanwhile, a looking-up database method used for yielding PDF47 error correcting codes has been developed, which makes it easier and more accurate to compute the coefficients of the generating polynomial and results of syndrome polynomials. The efficiency of PDF417 error-correcting function is therefore highly improved. As for the decoding process, this paper describes a solution based on whole bar code picking up by CCD vision system, and computer proces
sing to detect the edges of the barcodes. An algorithm is also designed here based on PDF417 two-dimensional barcodes' structure. It first proposes a filter to eliminate noise, then deals with vertical scratches and those points that do not comply with the bar codes' boundary characteristics by a point-search strategy. Later, during process of restoring the bar coded pictures, the contaminations will not be restored due to that fact that their seeds for restoration have been cleaned beforehand. Experiments have proved that this algorithm can effectively eliminate the negative smooth of the bar code caused by filtering. The restored pictures will then be decoded by an improved edge-detecting projection method which can lead to efficiency and accuracy of the decoding process while demanding a lower error correcting level.
This paper covers the characteristics and basic principles of the design of two-dimensional bar code and detailed examples of its application, including an encoding method for both English and Chinese characters. Two-dimensional bar code possesses the capability of error-correcting which one-dimensional bar code doesn't. So, besides a brief introduction of Reed-Solomon error-correcting code (RS code), this paper also gives a thorough analysis of RS code's application in two-dimensional bar code PDF417, giving detailed error-correcting principles in GF(929). Meanwhile, a looking-up database method used for yielding PDF47 error correcting codes has been developed, which makes it easier and more accurate to compute the coefficients of the generating polynomial and results of syndrome polynomials. The efficiency of PDF417 error-correcting function is therefore highly improved. As for the decoding process, this paper describes a solution based on whole bar code picking up by CCD vision system, and computer proces
sing to detect the edges of the barcodes. An algorithm is also designed here based on PDF417 two-dimensional barcodes' structure. It first proposes a filter to eliminate noise, then deals with vertical scratches and those points that do not comply with the bar codes' boundary characteristics by a point-search strategy. Later, during process of restoring the bar coded pictures, the contaminations will not be restored due to that fact that their seeds for restoration have been cleaned beforehand. Experiments have proved that this algorithm can effectively eliminate the negative smooth of the bar code caused by filtering. The restored pictures will then be decoded by an improved edge-detecting projection method which can lead to efficiency and accuracy of the decoding process while demanding a lower error correcting level.
引文
[1]陈晓平 条码印制技术 北京：清华大学出版社，1995
[2]T. Pavlidis "A New Paper/Computer Interface: Two-Dimensional Symbologies" IEEE Computer Magazine, 2000 pp. 145-150
[3]朱卫东 张艳树“二维条码技术与应用”，北方交通大学学报，21(3)，1999．6
[4]S. Itkin and J. Martell, A PDF417 Primer. Bohemia, NY: Symbol Technologies, 1992
[5]Robert B. Johnston and Alvin Khin Choy Yap," Electronic Data Interchange using Two Dimensional Bar Code", HICSS(4) 1998:83-91
[6]J. Piatek, "Automative Industry Recommend 2-D Standards," Automatic I.D. News, No. August, pp. 54-56, 1994
[7]R. B. Johnston, Electronic Commerce: An Operational View. Melbourne: Department of Business Systems, 1997
[8]陶德元，何小海，吴志华“RS码编译码算法的实现”，四川大学学报(自然科学版)，Vol．37(6)，pp．868-872，2000，12
[9]Anil K. Jain and Yao Chen "Bar Code Localization Using Texture Analysis", Advance Program, ICDAR'93,Second International Conference on Document,Analysis and Recognition,Japan.
[10]S. J. Shellhammer, D. P. Goren, and T. Pavlids, "Novel Signal-Processing Techniques in Barcode Scanning", IEEE Robotic & Automation Magazine, vol. 1070, pp.57-65, March 1999
[11]N. Normand, C. Viard-Gaudin, "A Two-Dimensional Bar Code Reader" IEEE, Image Processing, vol37, 1994, pp.201-203
[12]Christian VIARD-GAUDIN, Nicolas NORMAND, Dominique BARBA "A Bar Code Location Algorithm Using a Two-Dimensional Approach" 0-8186-4960-7/93 IEEE, 1993
[13]T. Pavlidis, J. Swartz, and Y. P. Wang "Information Encoding with Two-Dimensional Bar Codes" IEEE Computer Magazine, 25(June 1992), pp. 18-28
[14]T. Pavlidis, J. Swartz, and Y. P. Wang, "Fundamentals of Bar Code Information Theory," IEEE Computer Magazine, Vol. 23, No. 4, pp. 74-86, 1990
[15]中华人民共和国国家标准四一七条码GB／T 17172-1997四一七条码 国家技术监督局1997-12-25批准，1998-08-01实施
[16]R．E．Blahut著 徐秉铮，欧阳景正，冯贵良 译《差错控制码的理论与实践》华南理工大学出版社
[17]A. E. Blahut, "Theory and Practice of Error Control Codes." Reading, MA: Addison-Wesley, 1984
[18]朱起悦，“RS码编码和译码算法”电讯技术，vol．39，No．2，pp．63-67，Apr,1999
[19]Trieu-Kien Truong, Senior Member, IEEE, J. H. Jeng, King-Chu Hung, "Inversionless Decoding of Both Errors and Erasures of Reed-Sololmon Code" IEEE Transactions on Communications, Vol. 46, No. 8, pp. 973-976, August, 1998
[20]Jyh-Horng, Jeng and Trien-Kien Truong, Fellow, IEEE, "On Decoding of Both Errors and Erasures of a Reed-Solomon Code Using an Iverse-Free Berlekamp-Massey Algorithm", IEEE Transactions on Communications, Vol. 47, 10, pp. 1488-1494, October, 1999
[21]田宝玉，吴伟陵，王大庆，宋继昌，“RS码的一种简化译码方法”，北京邮电大学学报，Vol．22，No．3，pp．78-81，Sep．1999
[22]曾晓洋，郝志航，魏仲慧，“RS码时域编码算法及其计算机模拟”系统工程与电子技术 Vol．23，No．3，PP．16-18，2001
[23]Maltsey, United States Patent, June 2, 1998, 5,761,219
[24]王新梅 肖国镇 编著《纠错码原理与方法》西安电子科技大学出版社
[25]裴定一，祝跃飞 编著《算法数论》科学出版社
[26]何军，康景利“条形码的计算机编码与识别”，计算机测量与控制2002．10(4)pp．263-266
[27]刘宁钟，杨靖宇“基于投影算法的二维条码识别”。计算机工程，vol28(9)，2002．9，pp．32-34
[28]N. Otsu,"A Threshold Selection Method from Gray-Level Histograms", IEEE transactions Systems, Man and Cybernetics, vol.9, pp.62-66, January 1979.
[29]郎瑞 《数字图像处理学 Visual C++实现》，M，北京希望电子出版社
[30]孙兆林《MATLAB 6．x图像处理》，M，清华大学出版社
[31]张基宏，肖薇薇，纪震“基于二维条码PDF417的数字图像水印算法”深圳大学学报(理工版) Vol．19，No．1，pp．3-6 Mar．2002
[32]塔建庆，陈恩红，“PDF417二维条形码肖像图片压缩编码的优化算法研究”，计算机工程，Vol．29，No．1，pp．185-187，January，2001
[2]T. Pavlidis "A New Paper/Computer Interface: Two-Dimensional Symbologies" IEEE Computer Magazine, 2000 pp. 145-150
[3]朱卫东 张艳树“二维条码技术与应用”，北方交通大学学报，21(3)，1999．6
[4]S. Itkin and J. Martell, A PDF417 Primer. Bohemia, NY: Symbol Technologies, 1992
[5]Robert B. Johnston and Alvin Khin Choy Yap," Electronic Data Interchange using Two Dimensional Bar Code", HICSS(4) 1998:83-91
[6]J. Piatek, "Automative Industry Recommend 2-D Standards," Automatic I.D. News, No. August, pp. 54-56, 1994
[7]R. B. Johnston, Electronic Commerce: An Operational View. Melbourne: Department of Business Systems, 1997
[8]陶德元，何小海，吴志华“RS码编译码算法的实现”，四川大学学报(自然科学版)，Vol．37(6)，pp．868-872，2000，12
[9]Anil K. Jain and Yao Chen "Bar Code Localization Using Texture Analysis", Advance Program, ICDAR'93,Second International Conference on Document,Analysis and Recognition,Japan.
[10]S. J. Shellhammer, D. P. Goren, and T. Pavlids, "Novel Signal-Processing Techniques in Barcode Scanning", IEEE Robotic & Automation Magazine, vol. 1070, pp.57-65, March 1999
[11]N. Normand, C. Viard-Gaudin, "A Two-Dimensional Bar Code Reader" IEEE, Image Processing, vol37, 1994, pp.201-203
[12]Christian VIARD-GAUDIN, Nicolas NORMAND, Dominique BARBA "A Bar Code Location Algorithm Using a Two-Dimensional Approach" 0-8186-4960-7/93 IEEE, 1993
[13]T. Pavlidis, J. Swartz, and Y. P. Wang "Information Encoding with Two-Dimensional Bar Codes" IEEE Computer Magazine, 25(June 1992), pp. 18-28
[14]T. Pavlidis, J. Swartz, and Y. P. Wang, "Fundamentals of Bar Code Information Theory," IEEE Computer Magazine, Vol. 23, No. 4, pp. 74-86, 1990
[15]中华人民共和国国家标准四一七条码GB／T 17172-1997四一七条码 国家技术监督局1997-12-25批准，1998-08-01实施
[16]R．E．Blahut著 徐秉铮，欧阳景正，冯贵良 译《差错控制码的理论与实践》华南理工大学出版社
[17]A. E. Blahut, "Theory and Practice of Error Control Codes." Reading, MA: Addison-Wesley, 1984
[18]朱起悦，“RS码编码和译码算法”电讯技术，vol．39，No．2，pp．63-67，Apr,1999
[19]Trieu-Kien Truong, Senior Member, IEEE, J. H. Jeng, King-Chu Hung, "Inversionless Decoding of Both Errors and Erasures of Reed-Sololmon Code" IEEE Transactions on Communications, Vol. 46, No. 8, pp. 973-976, August, 1998
[20]Jyh-Horng, Jeng and Trien-Kien Truong, Fellow, IEEE, "On Decoding of Both Errors and Erasures of a Reed-Solomon Code Using an Iverse-Free Berlekamp-Massey Algorithm", IEEE Transactions on Communications, Vol. 47, 10, pp. 1488-1494, October, 1999
[21]田宝玉，吴伟陵，王大庆，宋继昌，“RS码的一种简化译码方法”，北京邮电大学学报，Vol．22，No．3，pp．78-81，Sep．1999
[22]曾晓洋，郝志航，魏仲慧，“RS码时域编码算法及其计算机模拟”系统工程与电子技术 Vol．23，No．3，PP．16-18，2001
[23]Maltsey, United States Patent, June 2, 1998, 5,761,219
[24]王新梅 肖国镇 编著《纠错码原理与方法》西安电子科技大学出版社
[25]裴定一，祝跃飞 编著《算法数论》科学出版社
[26]何军，康景利“条形码的计算机编码与识别”，计算机测量与控制2002．10(4)pp．263-266
[27]刘宁钟，杨靖宇“基于投影算法的二维条码识别”。计算机工程，vol28(9)，2002．9，pp．32-34
[28]N. Otsu,"A Threshold Selection Method from Gray-Level Histograms", IEEE transactions Systems, Man and Cybernetics, vol.9, pp.62-66, January 1979.
[29]郎瑞 《数字图像处理学 Visual C++实现》，M，北京希望电子出版社
[30]孙兆林《MATLAB 6．x图像处理》，M，清华大学出版社
[31]张基宏，肖薇薇，纪震“基于二维条码PDF417的数字图像水印算法”深圳大学学报(理工版) Vol．19，No．1，pp．3-6 Mar．2002
[32]塔建庆，陈恩红，“PDF417二维条形码肖像图片压缩编码的优化算法研究”，计算机工程，Vol．29，No．1，pp．185-187，January，2001