二维条码QR的纠错改进研究
摘要
二维条码与一维条码相比,它不需要依赖数据库,存储信息量大,可以表达多种多媒体及文字信息,同时它还可以嵌入加密机制,具有纠错能力。快速响应矩阵码(QR码)是一种矩阵二维条码,它能够全方位的识别和有效的表达汉字,目前在我国有着广泛的应用。针对传统的QR码的纠错能力有限,本文提出了一种将纠错码LDPC码替换RS码运用到QR图像中的方案,并利用图形预处理技术对摄取到的有噪声和倾斜的图形进行处理,最后通过分割处理以及译码流程对QR码进行识别,从而得到我们想要的信息。目的是在采用纠错码LDPC的编译码的基础上,提高QR码的纠错能力,改进了QR码的识别效果。在使用方面由于纠错能力提高了,那么它的使用范围也就可以扩展了。
本文通过分析国内外的二维条码技术的发展现状,然后对QR码的符号特征以及编译码原理进行了研究,提出了一种新的QR生成方案。通过对纠错码LDPC码的编译码思想以及性能仿真进行研究,然后把它与RS码进行仿真对比。同时对生成的新的QR码的图像预处理过程进行了详细的研究,包括图像的灰度化处理、中值滤波、二值化处理、图形的分割等。对于新的QR码,在生成的过程中需要注意里面纠错码的构成,它的结构直接影响了最后QR码的纠错能力。
通过理论研究之后,本文设计了QR码的编译码处理的流程,并且进行了相关的实验检测和分析。实验结果表明,新的QR码的译码能力提高了,在污损程度很大的时候也能够提取出正确的信息,相对于原来的QR来讲,纠错能力提高了,同时算法复杂度降低了。该技术不仅能够解决现有的二维条码QR码所遇到的问题,它还可以运用到其他的二维条码的系统中。
经过对本文的工作的总结,文中的创新工作有：
1)提出了一种新的QR码生成方案,把LDPC码代替RS码运用到QR码中。
2)针对采集到的QR图像,采用了图像中值滤波和二值化处理,用新的纠错码算法译码,把纠错能力从30%提高到50%。
3)在不改变原来的QR码的编解码机制的基础上,扩展了QR码的应用,降低算法复杂度。
Compared two dimensional barcode with one dimensional barcode the former does not need to rely on database, and it can store large amount of information and express a variety of multimedia and text information, at the same time it also can be embedded encryption system, having error correction ability. Quick response matrix codes (QR code) is a kind of matrix two dimensional barcode, it can be a full range of recognition and effectively express Chinese characters, at present it has been widely applied in our country. For traditional QR code the error correction ability is limited, this paper proposes a solution that error correcting codes LDPC codes will replace RS code to the QR image, and graphics pretreatment is used to deal with obtained noise and tilted graphics, finally through the segmentation processing and decode process QR code is identified, so the information what we want is gotten. The purpose is that on the basis of error-correcting codes LDPC encoding and decoding QR Code error correction ability is improved and the QR code recognition effect is also better. Due to the improved error correction ability, the use scope of QR code is also can be extended.
Through the analysis of the two-dimensional barcode technology's development status at home and abroad, and then the QR code symbols characteristics and encoding and decoding principles are studied, the paper puts forward a kind of new QR generation scheme. First it gives a study of the error correction code LDPC codes encoding and decoding thinking and performance simulation, and then puts it with the RS code simulation contrast. At the same time a detailed study is carried for the generated QR code image preprocessing, including image graying, median filtering, binarization, image segmentation and so on. For new QR code in the process of generation error-correcting codes composition need attention, because its structure directly affect the final QR code of error correction ability.
After theoretical study, this paper introduces the design processing of QR encoding and decoding, and some experimental detection and analysis. The experimental results show that the new QR code decoding ability has been improved, and it can extract the correct information in the large degree fouling, when compared to the original QR, the error correction ability is improved, and the complexity of the algorithm is reduced. This technology can not only solve the existing two dimensional barcode QR code with problem, it also can be applied to other two dimensional bar code system.
Pass by a summary of the present work, the innovations in the text are as follows:
1) A new QR code generation scheme is proposed that the LDPC codes are applied to the QR code instead of the RS Code.
2) For the collected QR image, the images median filter and binary processing are used, and with new error decoding algorithm the error correction ability is increased from30%to50%.
3) On the basis of not changing the coding scheme of the QR code, the QR code application is extended and the complexity of the algorithm is reduced.
本文通过分析国内外的二维条码技术的发展现状,然后对QR码的符号特征以及编译码原理进行了研究,提出了一种新的QR生成方案。通过对纠错码LDPC码的编译码思想以及性能仿真进行研究,然后把它与RS码进行仿真对比。同时对生成的新的QR码的图像预处理过程进行了详细的研究,包括图像的灰度化处理、中值滤波、二值化处理、图形的分割等。对于新的QR码,在生成的过程中需要注意里面纠错码的构成,它的结构直接影响了最后QR码的纠错能力。
通过理论研究之后,本文设计了QR码的编译码处理的流程,并且进行了相关的实验检测和分析。实验结果表明,新的QR码的译码能力提高了,在污损程度很大的时候也能够提取出正确的信息,相对于原来的QR来讲,纠错能力提高了,同时算法复杂度降低了。该技术不仅能够解决现有的二维条码QR码所遇到的问题,它还可以运用到其他的二维条码的系统中。
经过对本文的工作的总结,文中的创新工作有：
1)提出了一种新的QR码生成方案,把LDPC码代替RS码运用到QR码中。
2)针对采集到的QR图像,采用了图像中值滤波和二值化处理,用新的纠错码算法译码,把纠错能力从30%提高到50%。
3)在不改变原来的QR码的编解码机制的基础上,扩展了QR码的应用,降低算法复杂度。
Compared two dimensional barcode with one dimensional barcode the former does not need to rely on database, and it can store large amount of information and express a variety of multimedia and text information, at the same time it also can be embedded encryption system, having error correction ability. Quick response matrix codes (QR code) is a kind of matrix two dimensional barcode, it can be a full range of recognition and effectively express Chinese characters, at present it has been widely applied in our country. For traditional QR code the error correction ability is limited, this paper proposes a solution that error correcting codes LDPC codes will replace RS code to the QR image, and graphics pretreatment is used to deal with obtained noise and tilted graphics, finally through the segmentation processing and decode process QR code is identified, so the information what we want is gotten. The purpose is that on the basis of error-correcting codes LDPC encoding and decoding QR Code error correction ability is improved and the QR code recognition effect is also better. Due to the improved error correction ability, the use scope of QR code is also can be extended.
Through the analysis of the two-dimensional barcode technology's development status at home and abroad, and then the QR code symbols characteristics and encoding and decoding principles are studied, the paper puts forward a kind of new QR generation scheme. First it gives a study of the error correction code LDPC codes encoding and decoding thinking and performance simulation, and then puts it with the RS code simulation contrast. At the same time a detailed study is carried for the generated QR code image preprocessing, including image graying, median filtering, binarization, image segmentation and so on. For new QR code in the process of generation error-correcting codes composition need attention, because its structure directly affect the final QR code of error correction ability.
After theoretical study, this paper introduces the design processing of QR encoding and decoding, and some experimental detection and analysis. The experimental results show that the new QR code decoding ability has been improved, and it can extract the correct information in the large degree fouling, when compared to the original QR, the error correction ability is improved, and the complexity of the algorithm is reduced. This technology can not only solve the existing two dimensional barcode QR code with problem, it also can be applied to other two dimensional bar code system.
Pass by a summary of the present work, the innovations in the text are as follows:
1) A new QR code generation scheme is proposed that the LDPC codes are applied to the QR code instead of the RS Code.
2) For the collected QR image, the images median filter and binary processing are used, and with new error decoding algorithm the error correction ability is increased from30%to50%.
3) On the basis of not changing the coding scheme of the QR code, the QR code application is extended and the complexity of the algorithm is reduced.
引文
[1]中国物品编码中心.条码技术与应用[M].北京：清华大学出版社,2003：128-139.
[2]中国物品编码中心.二维条码技术与应用[M].北京：中国计量出版社,2007：1-26.
[3]吴佳鹏.二维条码识读技术及其应用研究[D].天津：天津大学,2010.
[4]曾子剑.基于QR二维码编解码技术的研究与实现[D].成都：电子科技大学,2010.
[5]徐辉.QR Code二维条码编解码系统的应用研究[D].南京：南京邮电大学,2011.
[6]Jiejing Zhou, Yunfei Liu, Peng Li."Research on Binarization of QR Code Image"[C].In Proceedings of the IEEE International Conference on Multimedia Technology (ICMT), 2010,2(1):1-4.
[7]Zou Xiong, He Cuiqun,Liu Guodong."A Binarization Method of Quick Response Code Image" [J].International Conference on Signal Processing Systems,2010,23(3):317-320.
[8]WANG Liang,LIU Xiaodan."An Improved Two-dimensional Code Encoding Approach for Publications"[C].International Conference on Signal Processing Systems,2010,23(2):33-36.
[9]Yu Fang, Yue Peng."The design and implementation of two-dimensional Barcode identification in smartphone"[C].In Proceedings of the IEEE. International Conference on Computer Application and System Modeling (ICCASM),2010,7(2):635-637.
[10]郭琳.QR Code二维条码编译码及自动识别技术的研究[D].昆明：昆明理工大学,2008.
[11]Shiyang Liu. "Anti-counterfeit System Based on Mobile Phone QR Code and Fingerprint"[C].In Proceedings of the IEEE International Conference on Intelligent Human-Machine Systems and Cybernetics(IHMSC),2010,2(1):236-240.
[12]张立信,陶学恒,里红杰.QR Code二维条码在纸币防伪技术中应用[J].机电产品开发与创新,2012,25(1)：25-27.
[13]张兴华.矩阵式快速QR码的研究和应用[D].成都：电子科技大学,2009.
[14]黄宏博.QR二维条码的纠错编码算法研究及实现[J].微计算机信息,2010,26(13)：36-38.
[15]Mehdi Karimi, and Amir H. Banihashemi."Counting Short Cycles of Quasi Cyclic Photograph LDPC Codes"[J].IEEE COMMUNICATIONS LETTERS,2012,12(1):1-4.
[16]吴祖义.RS码软判译码技术的研究[D].南京：南京邮电大学,2010.
[17]王锋.RS译码器算法研究与实现[D].苏州：苏州大学,2010.
[18]于湘珍,刘军,王秋娟.RS码在汉信码中的纠错性能分析及仿真[J].南京理工大学学报,2011,35(2)：42-46.
[19]R.G Gallager."Low density parity-check codes"[J].Ire Transactions on Information Theory.1962,13(3):21-28.
[20]R.G Gallager."Low density parity-check codes"[J].Cambridge,Mass:MIT Press, 1963,23-29.
[21]M.Ivkovic, S.K.Chilappagari, B.Vasic, "Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers," IEEE Trans Inform.Theory,2008,54(1), 3763-3774.
[22]袁东风等.LDPC码理论与应用[M].北京：人民邮电出版社,2008.
[23]Jui-Hui Hung, Jin-Shun Shyu, Sau-Gee Chen."A New High-Performance and Low-complexity Turbo-LDPC Code"[C].International Conference on Multimedia and Signal Processing,2011,13(1):68-72.
[24]张丽丽.LDPC码构造及其应用研究[D].杭州：杭州电子科技大学,2011.
[25]贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社,2009.
[26]David Munoz-Mejias, Ivan Gonzalez-Diaz, Fernando Diaz-de-Maria." A Low-Complexity Pre-Processing System for Restoring Low-Quality QR Code Images"[J]. IEEE Transactions on Consumer Electronics,2011,57(3):1320-1328.
[27]Pavel Rybin, Victor Zyablov."Asymptotic estimation of error fraction corrected by binary LDPC code"[J].IEEE International Symposium on Information Theory Proceedings, 2011, 2(2):351-355.
[28]Yeong-Luh Ueng, Chen-Yap Leong, et al."An Efficient Layered Decoding Architecture for Nonbinary QC-LDPC Codes. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS"[J]. 2012,59(2):385-389.
[29]杨雪飞,李瑞.低复杂度多进制LDPC码译码算法研究[J].舰船电子工程,2011,31(10)：75-78.
[30]刘原华.LDPC码的代数构造及译码算法研究[D].西安：西安电子科技大学,2009.
[31]Liu Hai-yang, et al. "Novel modified min-sum decoding algorithm for low-density parity-check codes".www.sciencedirect.com/science/journal/10058885.2010,17(4):1-5.
[32]陈旭灿.改进的LDPC译码算法研究[J].电子科技大学学报,2010,39(2)：219-222.
[33]吴湛击.LDPC码的高效译码算法研究[J].系统工程与电子技术,2010：32(3)：603-608.
[34]宋珍珍.LDPC码译码方法及性能分析研究[D].山东：山东大学,2011.
[35]张仲明,许拔.信噪比失配对LDPC码译码影响的分析[J].计算机工程与科学,2011,33(3)：167-171.
[36]张小花,李艳萍.改进的LDPC码Normalized BP- Based泽码算法[J].计算机应用,2012,32(1)：150-152.
[37]Youan Xiao, Chunling Luo, Chao Yang."The Comparative Analysis of LDPC and RS Code".In the International Conference on Consumer Electronics, Communications and Networks (CECNet 2011),2011,30(9):4510-4513.
[38]Luiz F. F. Belussi, Nina S. T. Hirata."Fast QR Code Detection in Arbitrarily Acquired Images"[C].SIBGRAPI Conference on Graphics, Patterns and Images,2011,24(1):281-288.
[39]Dong Han, Jianfu Teng, Zhaoxuan Yang."2D barcode image binarization based on wavelet analysis and Otsu's method"[C].In Proceedings of the IEEE International Conference on Computer Application and System Modeling (ICCASM),2010,5(1):30-33.
[40]Yuji Katol, Daisuke Deguchi, Hiroshi Murasel."Low resolution QR-code recognition by applying super-resolution using the property of QR-codes"[J].International Conference on Document Analysis and Recognition,2011,34(1):992-996.
[41]Wakahara, T.Yamamoto, N.Ochi,H."Image Processing of Dotted Picture in the QR Code of Cellular Phone"[C].In Proceedings of the IEEE International Conference on P2P.Parallel,Grid, Cloud and Internet Computing (3PGCIC),2010,3(2):454- 458.
[42]王晓凯,李锋.改进的自适应中值滤波[J].计算机工程与应用,2010,46(3)：175-177.
[43]邹雄,刘国栋,曾文平.QR码图像预处理中的滤波研究[J].应用光学,2010,31(3)：413-417.
[44]Dong Han, Jianfu Teng, Zhaoxuan Yang."2D barcode image binarization based on wavelet analysis and Otsu's method"[C].In Proceedings of the IEEE International Conference on Computer Application and System Modeling (ICCASM),2010,5(1):30-33.
[45]Liao Zhao-lai, Huang Ting-lei,Wang Rui."A method of image analysis for QR code recognition"[C].In Proceedings of the IEEE International Conference on Intelligent Computing and Integrated Systems (ICISS),2010,4(1):250-253.
[46]Ming Sun, Zhenkun Fang, Longsheng Fu."Identification of QR codes based on pattern recognition"[C].In Proceedings of the IEEE International Conference on World Automation Congress (WAC),2010,2(1):397-401.
[47]冯源.二维条码QR码的图像检测技术研究[D].长春：长春工业大学,2011.
[48]李军.QR码的图像恢复和识别技术研究与实现[D].苏州：苏州大学,2010.
[49]Xiong Zou, Guo-dong Liu, Jian-min Wang,"Application and study of wavelet transform in the QR code image preprocessing"[C].In Proceedings of the IEEE International Conference on Future Computer and Communication (ICFCC),2010,3(1):450-453.
[50]Hsiang-Cheh Huang, Feng-Cheng Chang, Wai-Chi Fang."Reversible Data Hiding with Histogram-Based Difference Expansion for QR Code Applications"[J].IEEE Transactions on Consumer Electronics,2011,57(2):779-787.
[2]中国物品编码中心.二维条码技术与应用[M].北京：中国计量出版社,2007：1-26.
[3]吴佳鹏.二维条码识读技术及其应用研究[D].天津：天津大学,2010.
[4]曾子剑.基于QR二维码编解码技术的研究与实现[D].成都：电子科技大学,2010.
[5]徐辉.QR Code二维条码编解码系统的应用研究[D].南京：南京邮电大学,2011.
[6]Jiejing Zhou, Yunfei Liu, Peng Li."Research on Binarization of QR Code Image"[C].In Proceedings of the IEEE International Conference on Multimedia Technology (ICMT), 2010,2(1):1-4.
[7]Zou Xiong, He Cuiqun,Liu Guodong."A Binarization Method of Quick Response Code Image" [J].International Conference on Signal Processing Systems,2010,23(3):317-320.
[8]WANG Liang,LIU Xiaodan."An Improved Two-dimensional Code Encoding Approach for Publications"[C].International Conference on Signal Processing Systems,2010,23(2):33-36.
[9]Yu Fang, Yue Peng."The design and implementation of two-dimensional Barcode identification in smartphone"[C].In Proceedings of the IEEE. International Conference on Computer Application and System Modeling (ICCASM),2010,7(2):635-637.
[10]郭琳.QR Code二维条码编译码及自动识别技术的研究[D].昆明：昆明理工大学,2008.
[11]Shiyang Liu. "Anti-counterfeit System Based on Mobile Phone QR Code and Fingerprint"[C].In Proceedings of the IEEE International Conference on Intelligent Human-Machine Systems and Cybernetics(IHMSC),2010,2(1):236-240.
[12]张立信,陶学恒,里红杰.QR Code二维条码在纸币防伪技术中应用[J].机电产品开发与创新,2012,25(1)：25-27.
[13]张兴华.矩阵式快速QR码的研究和应用[D].成都：电子科技大学,2009.
[14]黄宏博.QR二维条码的纠错编码算法研究及实现[J].微计算机信息,2010,26(13)：36-38.
[15]Mehdi Karimi, and Amir H. Banihashemi."Counting Short Cycles of Quasi Cyclic Photograph LDPC Codes"[J].IEEE COMMUNICATIONS LETTERS,2012,12(1):1-4.
[16]吴祖义.RS码软判译码技术的研究[D].南京：南京邮电大学,2010.
[17]王锋.RS译码器算法研究与实现[D].苏州：苏州大学,2010.
[18]于湘珍,刘军,王秋娟.RS码在汉信码中的纠错性能分析及仿真[J].南京理工大学学报,2011,35(2)：42-46.
[19]R.G Gallager."Low density parity-check codes"[J].Ire Transactions on Information Theory.1962,13(3):21-28.
[20]R.G Gallager."Low density parity-check codes"[J].Cambridge,Mass:MIT Press, 1963,23-29.
[21]M.Ivkovic, S.K.Chilappagari, B.Vasic, "Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers," IEEE Trans Inform.Theory,2008,54(1), 3763-3774.
[22]袁东风等.LDPC码理论与应用[M].北京：人民邮电出版社,2008.
[23]Jui-Hui Hung, Jin-Shun Shyu, Sau-Gee Chen."A New High-Performance and Low-complexity Turbo-LDPC Code"[C].International Conference on Multimedia and Signal Processing,2011,13(1):68-72.
[24]张丽丽.LDPC码构造及其应用研究[D].杭州：杭州电子科技大学,2011.
[25]贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社,2009.
[26]David Munoz-Mejias, Ivan Gonzalez-Diaz, Fernando Diaz-de-Maria." A Low-Complexity Pre-Processing System for Restoring Low-Quality QR Code Images"[J]. IEEE Transactions on Consumer Electronics,2011,57(3):1320-1328.
[27]Pavel Rybin, Victor Zyablov."Asymptotic estimation of error fraction corrected by binary LDPC code"[J].IEEE International Symposium on Information Theory Proceedings, 2011, 2(2):351-355.
[28]Yeong-Luh Ueng, Chen-Yap Leong, et al."An Efficient Layered Decoding Architecture for Nonbinary QC-LDPC Codes. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS"[J]. 2012,59(2):385-389.
[29]杨雪飞,李瑞.低复杂度多进制LDPC码译码算法研究[J].舰船电子工程,2011,31(10)：75-78.
[30]刘原华.LDPC码的代数构造及译码算法研究[D].西安：西安电子科技大学,2009.
[31]Liu Hai-yang, et al. "Novel modified min-sum decoding algorithm for low-density parity-check codes".www.sciencedirect.com/science/journal/10058885.2010,17(4):1-5.
[32]陈旭灿.改进的LDPC译码算法研究[J].电子科技大学学报,2010,39(2)：219-222.
[33]吴湛击.LDPC码的高效译码算法研究[J].系统工程与电子技术,2010：32(3)：603-608.
[34]宋珍珍.LDPC码译码方法及性能分析研究[D].山东：山东大学,2011.
[35]张仲明,许拔.信噪比失配对LDPC码译码影响的分析[J].计算机工程与科学,2011,33(3)：167-171.
[36]张小花,李艳萍.改进的LDPC码Normalized BP- Based泽码算法[J].计算机应用,2012,32(1)：150-152.
[37]Youan Xiao, Chunling Luo, Chao Yang."The Comparative Analysis of LDPC and RS Code".In the International Conference on Consumer Electronics, Communications and Networks (CECNet 2011),2011,30(9):4510-4513.
[38]Luiz F. F. Belussi, Nina S. T. Hirata."Fast QR Code Detection in Arbitrarily Acquired Images"[C].SIBGRAPI Conference on Graphics, Patterns and Images,2011,24(1):281-288.
[39]Dong Han, Jianfu Teng, Zhaoxuan Yang."2D barcode image binarization based on wavelet analysis and Otsu's method"[C].In Proceedings of the IEEE International Conference on Computer Application and System Modeling (ICCASM),2010,5(1):30-33.
[40]Yuji Katol, Daisuke Deguchi, Hiroshi Murasel."Low resolution QR-code recognition by applying super-resolution using the property of QR-codes"[J].International Conference on Document Analysis and Recognition,2011,34(1):992-996.
[41]Wakahara, T.Yamamoto, N.Ochi,H."Image Processing of Dotted Picture in the QR Code of Cellular Phone"[C].In Proceedings of the IEEE International Conference on P2P.Parallel,Grid, Cloud and Internet Computing (3PGCIC),2010,3(2):454- 458.
[42]王晓凯,李锋.改进的自适应中值滤波[J].计算机工程与应用,2010,46(3)：175-177.
[43]邹雄,刘国栋,曾文平.QR码图像预处理中的滤波研究[J].应用光学,2010,31(3)：413-417.
[44]Dong Han, Jianfu Teng, Zhaoxuan Yang."2D barcode image binarization based on wavelet analysis and Otsu's method"[C].In Proceedings of the IEEE International Conference on Computer Application and System Modeling (ICCASM),2010,5(1):30-33.
[45]Liao Zhao-lai, Huang Ting-lei,Wang Rui."A method of image analysis for QR code recognition"[C].In Proceedings of the IEEE International Conference on Intelligent Computing and Integrated Systems (ICISS),2010,4(1):250-253.
[46]Ming Sun, Zhenkun Fang, Longsheng Fu."Identification of QR codes based on pattern recognition"[C].In Proceedings of the IEEE International Conference on World Automation Congress (WAC),2010,2(1):397-401.
[47]冯源.二维条码QR码的图像检测技术研究[D].长春：长春工业大学,2011.
[48]李军.QR码的图像恢复和识别技术研究与实现[D].苏州：苏州大学,2010.
[49]Xiong Zou, Guo-dong Liu, Jian-min Wang,"Application and study of wavelet transform in the QR code image preprocessing"[C].In Proceedings of the IEEE International Conference on Future Computer and Communication (ICFCC),2010,3(1):450-453.
[50]Hsiang-Cheh Huang, Feng-Cheng Chang, Wai-Chi Fang."Reversible Data Hiding with Histogram-Based Difference Expansion for QR Code Applications"[J].IEEE Transactions on Consumer Electronics,2011,57(2):779-787.