文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.12.031
中文引用格式： 陳元枝，鄧艷，史紹亮，等. 基于Gzip壓縮算法的彩色QR碼生成與識別方法[J].電子技術應用，2015，41(12)：116-119，128.
英文引用格式： Chen Yuanzhi，Deng Yan，Shi Shaoliang，et al. Generation and recognition method of colorized QR codes based on Gzip compression algorithm[J].Application of Electronic Technique，2015，41(12)：116-119，128.
0 引言
傳統(tǒng)的黑白條碼由于其較強的解碼魯棒性和儲存容量，迅速成為自動識別領域的重要分支，國內(nèi)外學者為了提高條形碼的數(shù)據(jù)容量進行了大量的研究。在一個有限的空間內(nèi)增加信息密度的需求促進了彩色條碼的發(fā)展。ColorCode[1]首次使用顏色信息來提高數(shù)據(jù)容量，但ColorCode僅作為后臺數(shù)據(jù)庫的索引，不屬于信息攜帶型的條碼。內(nèi)存碼[2](Paper Memory，PM)通過同一空間位置疊加多層QR碼來提高數(shù)據(jù)容量，但對解碼軟件顏色識別的要求過高。高容量的彩色條碼[3](High Capacity Color Barcode，HCCB)通過編碼4色或8色的三角形符號集來提高數(shù)據(jù)容量，但HCCB碼掃描的魯棒性較差，缺乏明確的模式來支持檢測和定位過程。移動多彩色符合碼(Mobile Multi-Colour Composite，MMCC)[4]將編碼顏色增加為10種，數(shù)據(jù)容量增加至黑白QR碼的4倍，但MMCC碼無法正確解碼褶皺或邊緣彎曲的失真符號。Bulan[5]利用半色調(diào)點的方向模型在同一空間位置嵌入2種或3種不同顏色的獨立數(shù)據(jù)，再根據(jù)RGB和CMYK顏色空間光譜的互補特性將不同顏色的數(shù)據(jù)分離，數(shù)據(jù)容量為黑白QR碼的2倍或3倍。高容量的彩色二維條碼(High Capacity Colored Two Dimensional Codes，HCC2D)[6]在黑白QR碼的基礎上，利用Zxing[7]和Libqrencode[8]兩個開源的庫實現(xiàn)了4色、8色和16色的彩色QR碼，數(shù)據(jù)容量分別為黑白QR碼的2倍、3倍和4倍。
現(xiàn)存的彩色碼一般通過增加編碼顏色種類或在同一空間位置疊加多層彩色碼來提高數(shù)據(jù)容量，卻很少有彩色碼利用無損壓縮算法來提高數(shù)據(jù)容量。本文在Gzip壓縮算法的基礎上設計了一種彩色QR碼的生成和識別方法，通過增加編碼顏色種類和Gzip壓縮算法來提高數(shù)據(jù)容量。實驗證明了4色和16色QR碼在數(shù)據(jù)容量和計算復雜度方面的優(yōu)越性。
1 彩色QR碼的生成與識別
1.1 彩色QR碼的設計思路
每個模塊可容納的比特數(shù)取決于使用的編碼顏色種類，用4種顏色編碼信息時，一個顏色模塊可容納2 bit，用8種顏色編碼信息時，一個顏色模塊可容納3 bit。以此類推，當編碼顏色數(shù)為2k種時，每個顏色模塊可容納k bit，即碼字總數(shù)、剩余位、數(shù)據(jù)碼字數(shù)、糾錯碼字數(shù)、糾錯的塊數(shù)等均變?yōu)楹诎譗R碼的k倍。
1.2 彩色QR碼尋像圖形的定位
彩色QR碼解碼過程中，檢測并定位尋像圖形是最開始也是最關鍵的步驟。檢測尋像圖形時，隔行遍歷彩色QR碼圖像，先在水平方向上統(tǒng)計彩色QR碼圖像中5種顏色的相對寬度比例是否為1:1:3:1:1，此處比例允許小于50%的偏差；滿足上述比例條件后，再垂直檢測彩色QR碼圖像中5種顏色的相對寬度比例是否為1:1:3:1:1，此處比例允許小于40%的偏差；滿足上述兩個比例條件后，再次檢測水平方向上彩色QR碼圖像中5種顏色的相對寬度比例是否為1:1:3:1:1，此處比例允許小于20%的偏差。偏差的存在主要是為了檢測扭曲、變形等失真的彩色QR碼。
1.3 彩色QR碼編碼
彩色QR碼的主要編碼過程如下：(1)輸入待編碼數(shù)據(jù)，生成源數(shù)據(jù)信息流；(2)用Gzip壓縮算法對源數(shù)據(jù)信息流進行壓縮；(3)根據(jù)黑白QR碼的編碼規(guī)則進行數(shù)據(jù)分析，形成數(shù)據(jù)碼字流；(4)根據(jù)數(shù)據(jù)碼字流的字節(jié)數(shù)，利用最小尺寸原則初始化彩色QR碼；(5)在步驟(3)和步驟(4)的基礎上，用理德-所羅門碼(Reed-Solomon,RS)算法對數(shù)據(jù)碼字流進行分塊糾錯，形成糾錯碼字流；(6)將糾錯碼字流添加到數(shù)據(jù)碼字序列后，構成總碼字流；(7)填充尋像圖形、分隔符、定位圖形和校正圖形區(qū)域；(8)填充格式信息和版本信息區(qū)域；(9)用默認的掩膜圖形參考000對編碼區(qū)域的模塊圖形進行掩膜；(10)根據(jù)黑白QR碼符號字符的排列規(guī)則，在步驟(8)和步驟(9)的基礎上填充數(shù)據(jù)碼字和糾錯碼字區(qū)域；(11)根據(jù)預先設定的顏色映射表，將彩色QR碼保存為PNG格式。
1.4 彩色QR碼解碼
彩色QR碼的主要解碼過程如下：(1)加載并遍歷PNG格式的彩色QR碼圖像，獲得每個像素點的RGB值；(2)用尋像圖形的定位算法檢測3個位置探測圖形，若成功檢測到尋像圖形，則進入步驟(3)，否則進入步驟(11)；(3)返回3個位置探測圖形中心點的坐標值，若存在校正圖形，則返回校正圖形中心點的坐標值；(4)利用尋像圖形和校正圖形中心點的坐標，進行透視變換，柵格化彩色QR碼的顏色模塊；(5)根據(jù)預先設定的顏色映射表，識讀格式信息和版本信息；(6)去除掩膜，恢復數(shù)據(jù)碼字序列和糾錯碼字序列；(7)用RS算法進行錯誤檢查，若發(fā)現(xiàn)錯誤，則進入步驟(8)；否則進入步驟(9)；(8)用RS算法分塊糾錯；(9)將數(shù)據(jù)解壓縮，恢復源數(shù)據(jù)信息流；(10)根據(jù)模式指示符和字符計數(shù)指示符，進行數(shù)據(jù)碼字譯碼，恢復編碼數(shù)據(jù)；(11)結束本次解碼。
2 仿真實驗
文章中的實驗是基于C#版Zxing庫進行的，測試QR碼的數(shù)據(jù)容量時，數(shù)字模式采用的數(shù)據(jù)集為“0123456789”共10個數(shù)字，字母數(shù)字模式采用的數(shù)據(jù)集為26個大寫字母，8位字節(jié)模式采用的數(shù)據(jù)集為26個小寫字母，中國漢字采用的數(shù)據(jù)集為GB2312第16區(qū)的94個漢字。該仿真實驗主要分析比較了2色、4色和16色QR碼數(shù)據(jù)容量和計算復雜度。
2.1 數(shù)據(jù)容量
增加彩色條碼的數(shù)據(jù)容量主要有兩種方式：(1)增加顏色塊的密度；(2)增加顏色種類。這兩種方法都有其局限性。當顏色塊的密度超過相機分辨率的極限以后，相鄰的顏色塊就無法區(qū)分了；而當顏色種類過多時，某種顏色可由多種顏色混疊得到。相鄰顏色塊之間的顏色混疊改變了原始顏色塊的顏色，因此顏色聚類的方法在存在顏色混疊時效果不佳。為了提高彩色條碼單位面積的信息嵌入率和解碼魯棒性，本文設計的彩色QR碼不進行偏色處理，提高數(shù)據(jù)容量主要通過Gzip的壓縮算法。
圖1列出了數(shù)字模式、字母數(shù)字模式、8位字節(jié)模式和中國漢字模式2色、4色和16色QR碼壓縮前后數(shù)據(jù)容量的曲線圖。由圖1可知，壓縮后2色、4色、16色QR碼分別從版本8、版本5、版本3開始有值，這是因為Gzip在尋找匹配串時利用哈希表來減小壓縮時間，Gzip的最小匹配長度為3 B，如果匹配串小于3 B的話，使用（匹配長度，相隔距離）對進行替換，不但沒有壓縮，反而還會增大[9]。而隨著編碼顏色的增加，單位面積的數(shù)據(jù)嵌入率逐漸提高，而Gzip的最大匹配長度是恒定的，所以16色QR碼僅需3個版本就足以容納哈希表的表頭。從圖1的曲線趨勢可看出，隨著版本號逐漸增加，數(shù)據(jù)容量增加的速度顯著提高，且隨著編碼顏色的增加，壓縮算法的優(yōu)勢會更加明顯。
由表1可知，Gzip的壓縮算法是本文提高數(shù)據(jù)容量最有效、最直接的方法。當編碼顏色分別為4種、16種時，壓縮前4色、16色QR碼的數(shù)據(jù)容量為黑白QR碼的2倍、4倍。采用Gzip壓縮算法后，中國漢字模式2色、4色、16色的數(shù)據(jù)容量分別為85 081、191 775、405 149，與之對應的壓縮比分別為46.82、52.77、55.74。8位字節(jié)模式2色、4色、16色的數(shù)據(jù)容量分別為199 189、412 035、839 210，與之對應的壓縮比分別為67.45、69.77、71.05。充分說明了該壓縮算法的有效性，且隨著編碼顏色的增多，壓縮比逐漸增大，即彩色QR碼的數(shù)據(jù)容量逐漸增加。
由表2可知，常見黑白二維碼（Data Matrix、PDF417、QR碼）中QR碼的數(shù)據(jù)容量最大，而關濤[10]設計的4色、8色、16色彩色DM碼的數(shù)據(jù)容量分別是黑白DM碼的2倍、3倍、4倍，16色DM碼跟黑白QR碼相比較，字母數(shù)字模式的容量擴充倍數(shù)最大，為黑白QR碼的2.17倍，袁遠松[11]設計的6色DM碼采取漢字的編碼長度與使用頻率成反比的編碼規(guī)則，使得中國漢字的數(shù)據(jù)容量高于16色DM碼，但壓縮比例最大的中國漢字模式的數(shù)據(jù)容量也僅為黑白QR碼的1.76倍。HCCB碼由于利用調(diào)色板來糾正彩色碼的偏色問題，調(diào)色板作為彩色碼的組成部分卻不能用來編碼數(shù)據(jù)信息，因此4色、8色的HCCB碼的數(shù)據(jù)容量略小于黑白QR碼的2倍、3倍。10色MMCC碼的數(shù)據(jù)容量也僅為黑白QR碼的4倍。4色、8色、16色的HCC2D碼的數(shù)據(jù)容量分別是黑白QR碼的2倍、3倍、4倍。而本文經(jīng)過GZIP壓縮算法后4色QR碼的數(shù)據(jù)容量與黑白QR碼相比較，數(shù)字模式、字母數(shù)字模式、8位字節(jié)模式、中國漢字模式的數(shù)據(jù)容量分別擴充了58.38倍、95.83倍、139.53倍、105.54倍。16色QR碼的數(shù)據(jù)容量與黑白QR碼相比較，數(shù)字模式、字母數(shù)字模式、8位字節(jié)模式、中國漢字模式的數(shù)據(jù)容量分別擴充了118.57倍、195.16倍、284.19倍、222.98倍。
由此可見，本文設計的彩色QR碼的數(shù)據(jù)容量與同類型的彩色碼相比，數(shù)據(jù)容量有明顯的優(yōu)勢，且隨著顏色種類的增多，數(shù)據(jù)容量方面的優(yōu)勢會更加明顯。
2.2 計算復雜度
彩色條碼相同的顏色模塊在不同光照下呈現(xiàn)的顏色不一樣，主流的彩色條碼為了解決偏色問題，將包含所有編碼顏色的調(diào)色板嵌入到條碼本身，并假定調(diào)色板和顏色模塊在不同光照下的顏色變化是相對一致的，解碼時將每一個顏色模塊與調(diào)色板中的顏色相比較，將歐式距離最小的顏色值視為最終解碼的顏色值，因此計算復雜度大幅增加。當調(diào)色板出現(xiàn)損毀、調(diào)色板和顏色模塊處于不均勻的光照下時，均會導致解碼失敗。
為了降低計算復雜度，提高數(shù)據(jù)容量和解碼正確率，本文設計的彩色QR碼不進行偏色處理。將編碼后的彩色QR碼保存為PNG格式，無損壓縮的圖片格式才能確保遍歷彩色QR碼時，精確識別每一個顏色模塊的RGB值，也正是因為如此，編碼顏色可以任意選取，才能利用Gzip的無損壓縮算法來提高數(shù)據(jù)容量。主流的彩色碼為了支持紙質(zhì)檔的掃描，將編碼后的彩色碼保存為JPEG的有損壓縮格式，而壓縮算法在量化過程中會造成顏色信息的丟失，導致解碼魯棒性大幅降低。
3 總結
本文設計的彩色QR碼通過增加編碼顏色和Gzip的壓縮算法來提高數(shù)據(jù)容量，實驗表明，16色QR碼數(shù)字模式、字母數(shù)字模式、8位字節(jié)模式、中國漢字模式的數(shù)據(jù)容量分別為黑白QR碼的118.57倍、195.16倍、284.19倍、222.98倍，數(shù)據(jù)容量跟同類型的彩色碼相比有明顯的優(yōu)勢，且編碼顏色可以任意選取，解碼魯棒性不會隨著環(huán)境光照的變化而降低，省去了主流彩色碼的顏色糾正步驟，因此計算量大幅降低。
參考文獻
[1] CHEOL-HO C，EUN-DONG S，NAM-KYU L，et al．Machine readable code image and method of encoding and decoding the same：United States，7020327[P].2002-03-07.
[2] ONODA T，MIWA K.Hierarchised two-dimensional code，creation method thereof，and read method thereof[J].Available at Japan Patent Office，2005，213336.
[3] Microsoft Research.High Capacity Color Barcodes.[EB/OL].(2007-03-19)[2010-5-15].http：//research.microsoft.com/projects/hccb/.
[4] KATO H，TAN K T，CHAI D.Novel colour selection scheme for 2D barcode[C].Proceedings of the 2009 International Symposium on Intelligent Signal Processing and Communication Systems(ISPACS 2009).Kanazawa，2009：529-532.
[5] BULAN O，MONGA V，SHARMA G.High capacity color barcodes using dot orientation and color separability[C].Proceedings of SPIE on Media Forensics and Security.San Jose，2009：725417.
[6] QUERINI M，GRILLO A，LENTINI A，et al.2D color barcodes for mobile phones[J].International Journal of Computer Science and Applications(IJCSA)，2011，8(1)：136-155.
[7] CROSSING Z.Multi-format 1d/2d barcode image processing library with clients for android[EB/OL].[2012-03-21].http：//code.google.com/p/zxing/.
[8] FUKUCHI K.Libqrencode，a c library for encoding data in a qr code symbol[EB/OL].[2010-10-18].http：//megaui.net/fukuchi/works/qrencode/.
[9] 湯維.32位壓縮程序在64位平臺上優(yōu)化的研究與實現(xiàn)[D].西安：西安電子科技大學，2006.
[10] 關濤.彩色Data Matrix條碼的設計以及若干問題的研究[D].北京：清華大學，2007.
[11] 賈華國，袁遠松，劉志.一種面向漢字的高壓縮比彩色二維條碼的設計與實現(xiàn)[J].浙江工業(yè)大學學報，2010，38(05)：561-565.