一種面向漢字的高壓縮比彩色二維條碼的設(shè)計(jì)與實(shí)現(xiàn)

賈華國(guó),袁遠(yuǎn)松,劉 志

(浙江工業(yè)大學(xué)軟件學(xué)院,浙江 杭州 310032)

條碼技術(shù)是集編碼、印刷、識(shí)別、數(shù)據(jù)采集和處理于一體的綜合技術(shù).目前,黑白二維條碼技術(shù)發(fā)展已經(jīng)趨于成熟,美國(guó)國(guó)家標(biāo)準(zhǔn)協(xié)會(huì)(ANSI)制定了二維條碼國(guó)際標(biāo)準(zhǔn)[1-2],包括 Data Matrix,PDF417,QR碼等.但隨著社會(huì)信息量增加以及條碼應(yīng)用領(lǐng)域的拓寬,需要條碼能表示更多信息,而當(dāng)前黑白二維條碼只使用兩種顏色,較大程度上限制了條碼信息容量的提高,此背景下,人們開(kāi)始展開(kāi)對(duì)彩色二維條碼的研究[3-4].目前,彩碼的研究工作屬于起步階段.微軟研究院在自主研發(fā)一款彩色二維條碼,發(fā)明人是Gavin Jancke,有四色和八色兩種版本,其最小單元是三角形,相對(duì)于黑白二維條碼,大約可以提高2～3倍的數(shù)據(jù)密度.韓國(guó)ColorZip公司也正在推出“彩色條碼”業(yè)務(wù).但我國(guó)表達(dá)信息的語(yǔ)言為中文,當(dāng)前流行的二維條碼包括微軟等在研發(fā)的彩色二維條碼,主要是針對(duì)英文字母與數(shù)字編碼,對(duì)中文漢字則使用漢字內(nèi)碼來(lái)表示,對(duì)中文文本來(lái)說(shuō),這種編碼方式效率偏低.再次,使用國(guó)外標(biāo)準(zhǔn)還存在專利許可權(quán)等問(wèn)題.針對(duì)以上情況,筆者在參照了Data Matrix碼國(guó)際標(biāo)準(zhǔn)后,設(shè)計(jì)一種具有較高容量且適合漢字編碼的彩色二維條碼,并將其實(shí)現(xiàn).

1 彩色二維條碼原理

1.1 信息容量

因黑白二維條碼通過(guò)將數(shù)據(jù)轉(zhuǎn)化成二進(jìn)制流,而后根據(jù)0,1值進(jìn)行黑白符號(hào)表示.所以,具有n個(gè)模塊的黑白二維條碼,每個(gè)模塊可表示0或者1,即每個(gè)模塊能表示2種可能,n個(gè)模塊的信息容量為2n.對(duì)于彩色條碼,假設(shè)顏色總數(shù)為k,通過(guò)擴(kuò)展黑白二維條碼的符號(hào)化表示方式,使用不同顏色的模塊標(biāo)識(shí)k進(jìn)制數(shù)中各個(gè)對(duì)應(yīng)的0,1,2,…,k-1,k.此時(shí),具有n個(gè)模塊的彩色二維條碼能表示的信息容量為kn.故只要彩色條碼中選取的顏色總數(shù)大于2種,通過(guò)一定的編碼規(guī)則,可較大提高二維條碼信息容量.因考慮選取相互之間對(duì)比較明顯的顏色有助于提高識(shí)別效率,根據(jù)RGB彩色空間模型,其中黑,白 ,紅 ,綠 ,黃 ,藍(lán) ,青 ,品紅等 8 種顏色之間的對(duì)比最明顯,故選取其中的前6種作為彩色條碼的顏色值,漢字庫(kù)編碼模式小節(jié)中將對(duì)此進(jìn)行分析.

1.2 條碼結(jié)構(gòu)

彩色二維條碼結(jié)構(gòu)可分為兩部分:功能圖像和數(shù)據(jù)圖像(見(jiàn)圖1).功能圖像用于條碼的定位、校正.數(shù)據(jù)圖像則用來(lái)表示編碼后具體的數(shù)據(jù)信息.彩碼圖像由各個(gè)規(guī)則排列的正方形模塊組成,其空白處即為數(shù)據(jù)圖像區(qū)域.該功能圖像可更準(zhǔn)確、有效的對(duì)條碼進(jìn)行定位,解碼階段將對(duì)此進(jìn)行具體分析.

圖1 彩色二維條碼結(jié)構(gòu)Fig.1 Structure of color two-dimensional barcode

2 編碼原理

彩色二維條碼編碼過(guò)程分為三個(gè)順序步驟:數(shù)據(jù)信息編碼,糾錯(cuò)碼生成,符號(hào)化過(guò)程.首先根據(jù)數(shù)據(jù)信息編碼模式將數(shù)據(jù)信息轉(zhuǎn)化為數(shù)據(jù)位流,并在開(kāi)始處添加表示數(shù)據(jù)位流長(zhǎng)度數(shù)構(gòu)成新數(shù)據(jù)流.其次,將形成的數(shù)據(jù)流按4位組成碼字由Reed-Solomon糾錯(cuò)算法生成糾錯(cuò)碼字[5],添加到數(shù)據(jù)碼字之后形成總的數(shù)據(jù)碼字.最后,對(duì)總的數(shù)據(jù)碼字進(jìn)行符號(hào)化,同時(shí)添加功能圖像,生成彩色條碼圖像.因糾錯(cuò)碼Reed-Solomon糾錯(cuò)算法已是成熟算法,故在編碼原理中只對(duì)彩色條碼數(shù)據(jù)信息編碼模式及符號(hào)化過(guò)程進(jìn)行介紹.編碼流程見(jiàn)圖2.

圖2 編碼流程圖Fig.2 Encoding flow diagram

2.1 數(shù)據(jù)信息編碼模式

(1)漢字庫(kù)編碼模式

國(guó)標(biāo)字符集中共有6 763個(gè)漢字和682個(gè)非漢字圖形符號(hào).但教育部、國(guó)家語(yǔ)委通過(guò)統(tǒng)計(jì)和分析漢字使用情況可知,日常生活中常用的漢字?jǐn)?shù)只有3 500個(gè)左右,最常用的600個(gè)漢字就可以覆蓋語(yǔ)料的80%,通過(guò)計(jì)算可知5進(jìn)制數(shù)中5位最大數(shù)為44 4445對(duì)應(yīng)于十進(jìn)制的3 12410,通過(guò)使用兩位標(biāo)識(shí)符可將漢字庫(kù)容量擴(kuò)充至15 624,但3 124個(gè)漢字已覆蓋日常生活中99%的漢字,故其容量為3 124,且需加一位作為標(biāo)識(shí),所以最終將采用6進(jìn)制,對(duì)應(yīng)與彩色條碼顏色,即需采用6種顏色.

編碼規(guī)則:據(jù)清華大學(xué)統(tǒng)計(jì)的漢字頻度表建立漢字編碼庫(kù),見(jiàn)表1.

表1 漢字庫(kù)編碼規(guī)則Table 1 Chinese Character Encoding Rules

(2)內(nèi)碼編碼模式

內(nèi)碼編碼模式是對(duì)漢字庫(kù)編碼模式的補(bǔ)充.針對(duì)漢字庫(kù)外的低頻漢字以及不常用的標(biāo)點(diǎn)符號(hào),使用漢字內(nèi)碼進(jìn)行編碼.

(3)單個(gè)ASCII編碼模式

針對(duì)單個(gè)ASCII進(jìn)行編碼,模式標(biāo)識(shí)符‘50',長(zhǎng)度為6位.

(4)連續(xù)數(shù)字編碼模式

針對(duì)數(shù)字編碼,處理完畢后,在開(kāi)始處加模式指示符‘515',結(jié)尾加結(jié)束模式指示符‘5',見(jiàn)表2.

表2 編碼模式規(guī)則表Table 2 Encoding rules

(5)連續(xù)ASCII編碼模式

編碼規(guī)則:將ASCII分為兩個(gè)集合S與R,見(jiàn)表3.

表3 集合S與R中的元素Table 3 Elements in set S and R

如:對(duì)連續(xù)字符‘AB'進(jìn)行編碼,設(shè)碼值分別為a,b,見(jiàn)表4.

表4 連續(xù)ASCII編碼規(guī)則Table 4 Continuous ASCII encoding rules

處理完畢后,在開(kāi)始與結(jié)尾處分別加入模式指示符‘505'與結(jié)束模式指示符‘505'.

2.2 符號(hào)化

數(shù)字轉(zhuǎn)化為顏色值時(shí)遵循映射關(guān)系,見(jiàn)表5.

表5 數(shù)字-顏色對(duì)應(yīng)表Table 5 Digital-color mapping table

且對(duì)于整個(gè)彩色圖像來(lái)講,符號(hào)化的過(guò)程為從左到右,從下到上.并且在每個(gè)數(shù)據(jù)區(qū)域,也遵循從左到右,從下到上的順序.該順序如圖3所示.

圖3 ‘3205'符號(hào)化與符號(hào)化順序圖Fig.3 Symbolic and the symbolic sequence diagram

2.3 性能對(duì)比

相比與黑白二色條碼,設(shè)計(jì)的彩色二維條碼主要在數(shù)據(jù)容量與數(shù)據(jù)信息壓縮比上有所提高.

對(duì)于數(shù)據(jù)容量,通過(guò)前文設(shè)計(jì)原理部分已知:假設(shè)顏色總數(shù)為k,具有n個(gè)模塊的彩色二維條碼能表示的信息容量為kn,故對(duì)于黑白條碼來(lái)說(shuō),其信息容量為2n,對(duì)于設(shè)計(jì)的彩色二維條碼,因其使用6種顏色,故信息容量為 6n,當(dāng)n＞=1時(shí),6n＞2n,故在理論上,彩色二維條碼在信息容量上對(duì)比與黑白二色條碼有較大優(yōu)勢(shì).

對(duì)于數(shù)據(jù)信息壓縮比,下面通過(guò)對(duì)一段新聞進(jìn)行不同編碼來(lái)比較:“12月13日(北京時(shí)間9時(shí)00分左右),全國(guó)第二屆省級(jí)示范性軟件學(xué)院院長(zhǎng)聯(lián)席會(huì)在我校舉行.”

此新聞中漢字和中文標(biāo)點(diǎn)一共36個(gè),ASCII碼字字符:8個(gè),根據(jù)彩色條碼數(shù)據(jù)信息編碼規(guī)則,編碼后總的碼字位數(shù)為194位,各種編碼模式統(tǒng)計(jì)如表6所示,表中只顯示其中需要用到的編碼模式.

表6 編碼模式統(tǒng)計(jì)Table 6 Encoding mode statistics

若采用Data Matrix進(jìn)行編碼,按照其編碼模式計(jì)算編碼長(zhǎng)度:漢字和中文標(biāo)點(diǎn)一共36個(gè),需采用Base 256編碼模式,每個(gè)字符編碼需占用16位,再加上兩個(gè)碼字的長(zhǎng)度計(jì)數(shù),漢字的編碼長(zhǎng)度需36×16+16=592位,對(duì)數(shù)字、ASCII的編碼,只計(jì)算其最優(yōu)編碼情況下的編碼長(zhǎng)度,不考慮模式切換所需要的碼字耗費(fèi),也需要40位:2×4+5.33×6≈40位,總共需要632位,兩者所需位數(shù)-相差632÷194≈3.25倍,故可知彩色條碼編碼效率即信息壓縮比更高.

圖4是對(duì)該段新聞進(jìn)行編碼形成的圖片,分別使用彩色條碼編碼與Data Matrix編碼.通過(guò)對(duì)比兩張圖片可知.相同模塊下,彩色二維條碼的信息數(shù)據(jù)容量近似3.5倍于黑白二色的二維條碼.其中,有彩色條碼具有6種顏色所帶來(lái)的信息容量?jī)?yōu)勢(shì),也有采取多種編碼方式來(lái)提高信息的壓縮比所帶來(lái)的信息容量?jī)?yōu)勢(shì),特別是彩色條碼編碼階段加入漢字庫(kù),通過(guò)獨(dú)有的漢字庫(kù)編碼來(lái)專門(mén)對(duì)漢字進(jìn)行處理,取得對(duì)中文漢字的高壓縮比而獲得的信息容量?jī)?yōu)勢(shì).

圖4 彩色條碼圖與Data Matrix圖片F(xiàn)ig.4 Color barcode and data matrix barcode

3 解碼原理

前文已將彩色條碼設(shè)計(jì)及編碼原理介紹完畢,經(jīng)對(duì)比,可知彩色二維條碼在數(shù)據(jù)信息容量以及漢字壓縮比上有較大優(yōu)勢(shì).但同時(shí)因條碼圖像中含有多種顏色,也提高了條碼圖像的復(fù)雜度,對(duì)解碼過(guò)程各步驟的準(zhǔn)確性提出更高要求.解碼過(guò)程見(jiàn)圖5,將圖中解碼過(guò)程分為3個(gè)主要步驟.

圖5 解碼流程圖Fig.5 Decoding flow diagram

3.1 定 位

解碼過(guò)程中定位是非常重要的一步,只有定位準(zhǔn)確,才能為順利讀取條碼信息創(chuàng)造先決條件,若無(wú)法準(zhǔn)確定位條碼圖像,則無(wú)法進(jìn)行條碼的解碼步驟.為準(zhǔn)確定位圖中彩色條碼的位置,可通過(guò)功能圖像來(lái)實(shí)現(xiàn)此功能,如圖6所示.

圖6 功能圖像Fig.6 Function image

因彩色條碼圖像中復(fù)雜度有所增加,故設(shè)計(jì)的功能圖像需具有較強(qiáng)的定位能力.以上圖片分別為功能圖像以及其在不同顏色通道下的顯示.其中,紅色通道下的功能圖像與Data Matrix編碼中的功能圖像基本一致,可參照該編碼標(biāo)準(zhǔn)中的定位算法.從理論上說(shuō),通過(guò)對(duì)紅色通道下的功能圖像進(jìn)行Hough直線檢測(cè)已可進(jìn)行準(zhǔn)確定位,對(duì)于綠色通道與藍(lán)色通道的功能圖像,可在通過(guò)紅色通道下功能圖像無(wú)法實(shí)現(xiàn)準(zhǔn)確定位時(shí)候,將其加入到定位步驟中,是對(duì)Data Matrix編碼定位的一種改進(jìn)與補(bǔ)充.

3.2 顏色信息轉(zhuǎn)化數(shù)據(jù)位流信息

此步驟需完成兩個(gè)功能:檢測(cè)條碼規(guī)格即行列數(shù)目以及通過(guò)轉(zhuǎn)換算法將顏色信息轉(zhuǎn)換為數(shù)據(jù)位流信息.條碼規(guī)格檢測(cè)可通過(guò)計(jì)算定位坐標(biāo)內(nèi)一行圖像中像素的變化次數(shù)來(lái)得到,因條碼設(shè)計(jì)時(shí)呈正方形排列,故對(duì)于行列數(shù)目只要計(jì)算其中一項(xiàng)即可.得到條碼規(guī)格后,通過(guò)如下方法將顏色信息進(jìn)行轉(zhuǎn)化,見(jiàn)圖7.

圖7 顏色轉(zhuǎn)化數(shù)字流程圖Fig.7 Flow diagram of color translating into digital

假設(shè)定位過(guò)程中得到的頂點(diǎn)坐標(biāo),因彩色條碼圖像為正方形,可設(shè)各頂點(diǎn)坐標(biāo)為左上角P1(x1,y1),右上角 P2(x2,y1),左下角P3(x1,y2),右下角P4(x2,y2),且條碼規(guī)格為n.

則各個(gè)模塊大小為:

e=(x2-x1)/n或e=(y2-y1)/n,對(duì)位于第 I行第J列的模塊來(lái)講,其邊界坐標(biāo):

X軸方向?yàn)?/p>

Y軸方向?yàn)?/p>

統(tǒng)計(jì)該模塊邊界范圍內(nèi)各像素的個(gè)數(shù),并取其中像素值最多的顏色值作為該模塊的顏色值,將該顏色轉(zhuǎn)化成對(duì)應(yīng)的數(shù)字,這是為提高讀取顏色信息的正確率采取的措施,若對(duì)效率要求較高,則可直接取各模塊中心點(diǎn)像素值作為該模塊的顏色值,但相比與統(tǒng)計(jì)的方法,正確率較低,故還是采用統(tǒng)計(jì)像素個(gè)數(shù)的方法.因符號(hào)化過(guò)程中,數(shù)據(jù)是由倒正方形方式進(jìn)行排放,將圖像信息轉(zhuǎn)成數(shù)據(jù)矩陣后,需按照符號(hào)化時(shí)順序?qū)仃囍袛?shù)字進(jìn)行讀取排列,組成數(shù)據(jù)位流信息.

3.3 數(shù)據(jù)信息進(jìn)行解碼

經(jīng)糾錯(cuò)碼運(yùn)算無(wú)誤后,首先讀取數(shù)據(jù)信息前5位數(shù)據(jù),將其轉(zhuǎn)成十進(jìn)制數(shù)后可知數(shù)據(jù)信息長(zhǎng)度.此時(shí),可根據(jù)不同識(shí)別符,確定使用的編碼規(guī)則,對(duì)其進(jìn)行逆操作完成對(duì)數(shù)據(jù)的解碼.表7為各模式下的指示符.

表7 數(shù)據(jù)信息編碼模式識(shí)別符Table 7 Identifier of data coding mode

4 實(shí)驗(yàn)結(jié)果

因前文編碼原理階段已將彩色條碼性能進(jìn)行說(shuō)明,故這里只是對(duì)編解碼結(jié)果進(jìn)行顯示.以下為對(duì)浙江工業(yè)大學(xué)網(wǎng)址“http://www.zjut.edu.cn:80”及名稱“浙江工業(yè)大學(xué)”進(jìn)行編解碼,見(jiàn)圖8,9.

從圖中可知,彩色二維條碼編解碼已成功實(shí)現(xiàn),并且通過(guò)編碼原理中性能對(duì)比可知彩碼在信息容量與壓縮比上具有較大優(yōu)勢(shì),特別是對(duì)漢字信息的壓縮比,相比于其他條碼標(biāo)準(zhǔn),有了大幅度的提升.

5 結(jié) 論

筆者設(shè)計(jì)了一種彩色二維條碼,介紹了該條碼的編碼原理及解碼方法,在與Data Matrix碼的性能對(duì)比中,得到了相當(dāng)好的效果.目前,解碼過(guò)程只是針對(duì)計(jì)算機(jī)生成的標(biāo)準(zhǔn)圖像進(jìn)行處理,對(duì)實(shí)際拍攝中,圖像中可能存在的變形和偏色以及提高定位效率等方面還有待進(jìn)一步研究,同時(shí),對(duì)編碼和解碼的速度也需進(jìn)一步提升,以適應(yīng)實(shí)際應(yīng)用.

[1] International Organization for Standardization.ISO/IEC16022—2000 Information technology international symbology speciation-data matrix[S].Switzerland:ISO,2004.

[2] PAVLIDIS T,SWARTZ J.Fundamentals of barcode information theory[J].IEEE Computer,1990,23(4):74-86.

[3] STEPHEN B.Reed-solomon codes and applications[M].New York:IEEE Press,1994.

[4] 關(guān)濤.彩色Data Matrix條碼的設(shè)計(jì)及其若干問(wèn)題的研究[D].北京:清華大學(xué),2006.

[5] 劉寧鐘,楊靜宇.三維條碼的編碼理論和設(shè)計(jì)[J].計(jì)算機(jī)學(xué)報(bào),2007,30(4):686-687.