二維碼生成與識別原理_修訂版

1、QR二維碼的生成與識別原理一、 簡介二維碼 （2-dimensional bar code），是用某種特定的幾何圖形按一定規(guī)律在平面（二維方向上）分布的黑白相間的圖形記錄數(shù)據(jù)符號信息的。二維碼的種類包括：QR Code ,Data Matrix, Maxi Code, Aztec , Vericode, PDF417, Ultracode, Code 49, Code 16K等。其中QR Code是被廣泛使用的二維碼，QR全稱Quick Response，與其他編碼方式相比，QR二維碼具有存儲(chǔ)容量大、編碼速度快的特點(diǎn)，并且它也能表示更多的數(shù)據(jù)類型：比如：字符，數(shù)字，日文，中文等等。隨著近幾年智

2、能手機(jī)的迅猛發(fā)展，QR二維碼得到了廣泛的應(yīng)用。關(guān)于QR二維碼的標(biāo)準(zhǔn)，可參見標(biāo)準(zhǔn)文檔（QR Code Spec）：二、 應(yīng)用現(xiàn)狀隨著智能機(jī)的普及和手機(jī)攝像頭成像能力的提升，為了提高向機(jī)器內(nèi)輸入信息的速度，QR二維碼得到迅猛發(fā)展，在許多行業(yè)中得到應(yīng)用。在一維碼時(shí)代，“掃碼”主要應(yīng)用在超市或圖書館等場所，以獲取商品價(jià)格或圖書分類等有限的特定信息。二維碼可以存儲(chǔ)大容量數(shù)據(jù)，給人們的生活帶來巨大方便。從開始的掃描二維碼提取文字或網(wǎng)址，到后來“掃一掃”添加好友、關(guān)注個(gè)人或公司微信或微博，再到掃碼支付，二維碼的應(yīng)用已經(jīng)非常普遍。三、 基礎(chǔ)知識QR碼可分為不同的尺寸，或者叫版本Version。Version

3、1是21 x 21的矩陣，Version 2是 25 x 25的矩陣，Version 3是29的尺寸，每增加一個(gè)version，就會(huì)增加4的尺寸，公式是：(V-1)*4 + 21（V是版本號） 最高Version 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。樣例如下：定位圖案Position Detection Pattern是定位圖案，用于標(biāo)記二維碼的矩形大小。這三個(gè)定位圖案有白邊叫Separators for Postion Detection Patterns。之所以三個(gè)而不是四個(gè)意思就是三個(gè)就可以標(biāo)識一個(gè)矩形了。Timing Patterns也是用

4、于定位的。原因是二維碼有40種尺寸，尺寸過大了后需要有根標(biāo)準(zhǔn)線，不然掃描的時(shí)候可能會(huì)掃歪了。Alignment Patterns 只有Version 2以上（包括Version2）的二維碼需要這個(gè)東東，同樣是為了定位用的。功能性數(shù)據(jù)Format Information 存在于所有的尺寸中，用于存放一些格式化數(shù)據(jù)的。Version Information 在Version 7以上，需要預(yù)留兩塊3 x 6的區(qū)域存放一些版本信息。數(shù)據(jù)碼和糾錯(cuò)碼除了上述的那些地方，剩下的地方存放 Data Code 數(shù)據(jù)碼 和 Error Correction Code 糾錯(cuò)碼。四、 數(shù)據(jù)編碼QR碼支持如下的編碼：N

5、umeric mode：數(shù)字編碼，從0到9。如果需要編碼的數(shù)字的個(gè)數(shù)不是3的倍數(shù)，那么，最后剩下的1或2位數(shù)會(huì)被轉(zhuǎn)成4或7bits，則其它的每3位數(shù)字會(huì)被編成 10，12，14bits，編成多長還要看二維碼的尺寸。Alphanumeric mode：字符編碼，包括 0-9，大寫的A到Z（沒有小寫），以及符號$ % * + . / : 包括空格。這些字符會(huì)映射成一個(gè)字符索引表。如下所示：（其中的SP是空格，Char是字符，Value是其索引值） 編碼的過程是把字符兩兩分組，然后轉(zhuǎn)成下表的45進(jìn)制，然后轉(zhuǎn)成11bits的二進(jìn)制，如果最后有一個(gè)落單的，那就轉(zhuǎn)成6bits的二進(jìn)制。而編碼模式和字符的個(gè)

6、數(shù)需要根據(jù)不同的Version尺寸編成9, 11或13個(gè)二進(jìn)制（如下表中Table 3）Byte mode：字節(jié)編碼，可以是0-255的ISO-8859-1字符。有些二維碼的掃描器可以自動(dòng)檢測是否是UTF-8的編碼。Kanji mode：日文編碼，也是雙字節(jié)編碼。同樣，也可以用于中文編碼。Extended Channel Interpretation (ECI) mode：主要用于特殊的字符集。并不是所有的掃描器都支持這種編碼。Structured Append mode：用于混合編碼，也就是說，這個(gè)二維碼中包含了多種編碼格式。FNC1 mode：這種編碼方式主要是給一些特殊的工業(yè)或行業(yè)用的。

7、比如GS1條形碼之類的。這里我們主要介紹最常用的數(shù)字編碼和字符編碼。下面兩張表中，Table 2 是各個(gè)編碼格式的“編號”（注：中文是1101），編號要寫在Format Information中。Table 3 表示了不同版本（尺寸）的二維碼，對于數(shù)字、字符、字節(jié)和Kanji模式下，對于單個(gè)編碼的2進(jìn)制的位數(shù)。（編碼規(guī)范表可參見二維碼規(guī)格說明書）舉例說明：示例一：數(shù)字編碼例如，在Version 1的尺寸下，糾錯(cuò)級別為H的情況下，編碼： 01234567的編碼方式如下：1. 把上述數(shù)字分成三組: 012 345 672. 把他們轉(zhuǎn)成二進(jìn)制: 012 轉(zhuǎn)成 0000001100； 345 轉(zhuǎn)成 0

8、101011001； 67 轉(zhuǎn)成 1000011。3. 把這三個(gè)二進(jìn)制串起來: 0000001100 0101011001 10000114. 把數(shù)字的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (version 1-H是10 bits ): 8個(gè)數(shù)字的二進(jìn)制是 00000010005. 把數(shù)字編碼的標(biāo)志0001和第4步的編碼加到前面: 0001 0000001000 0000001100 0101011001 1000011示例二：字符編碼同樣，在Version 1的尺寸下，糾錯(cuò)級別為H的情況下，編碼: AC-42的編碼方式如下：1. 從字符索引表中找到 AC-42 這五個(gè)字條的索引 (10,12,41,4,2)2.

9、兩兩分組: (10,12) (41,4) (2)3. 把每一組轉(zhuǎn)成11bits的二進(jìn)制:(10,12) 10*45+12 等于 462 轉(zhuǎn)成 00111001110(41,4) 41*45+4 等于 1849 轉(zhuǎn)成 11100111001(2) 等于 2 轉(zhuǎn)成 0000104. 把這些二進(jìn)制連接起來：00111001110 11100111001 000010；5. 把字符的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (Version 1-H為9 bits ): 5個(gè)字符，5轉(zhuǎn)成 000000101；6. 在頭上加上編碼標(biāo)識 0010 和第5步的個(gè)數(shù)編碼: 0010 000000101 00111001110 11100

10、111001 000010；五、 結(jié)束符和補(bǔ)齊符假如我們有個(gè)HELLO WORLD的字符串要編碼，根據(jù)上面的示例二，我們可以得到下面的編碼編碼字符數(shù)HELLO WORLD的編碼001000000101101100001011 01111000110 10001011100 10110111000 10011010100 001101還要加上結(jié)束符：編碼字符數(shù)HELLO WORLD的編碼結(jié)束001000000101101100001011 01111000110 10001011100 10110111000 10011010100 0011010000按8bits重排如果所有的編碼加起來不是8

11、個(gè)倍數(shù)我們還要在后面加上足夠的0，比如上面一共有78個(gè)bits，所以還要加上2個(gè)0，然后按8個(gè)bits分好組：00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000補(bǔ)齊碼（Padding Bytes）最后，如果還沒有達(dá)到最大的bits數(shù)的限制，還要加一些補(bǔ)齊碼（Padding Bytes），Padding Bytes就是重復(fù)下面的兩個(gè)bytes：11101100 00010001 （這兩個(gè)二進(jìn)制轉(zhuǎn)成十進(jìn)制是236和17，關(guān)于每一個(gè)Version的每一種糾錯(cuò)級別的最大Bit

12、s限制，可以參看QR Code Spec）假設(shè)我們需要編碼的是Version 1的Q糾錯(cuò)級，那么，其最大需要104個(gè)bits，而我們上面只有80個(gè)bits，所以，還需要補(bǔ)24個(gè)bits，也就是需要3個(gè)Padding Bytes，我們就添加三個(gè)，于是得到下面的編碼：00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100上面的編碼就是數(shù)據(jù)碼了，叫Data Codewords，每一個(gè)8bits叫一個(gè)codeword，我們還要

13、對這些數(shù)據(jù)碼加上糾錯(cuò)信息。六、 糾錯(cuò)碼上面我們說到了一些糾錯(cuò)級別，Error Correction Code Level，二維碼中有四種級別的糾錯(cuò)，這就是為什么二維碼有殘缺還能掃出來，也就是為什么有人在二維碼的中心位置加入圖標(biāo)。錯(cuò)誤修正容量L水平7%的字碼可被修正M水平15%的字碼可被修正Q水平25%的字碼可被修正H水平30%的字碼可被修正那么，QR是怎么對數(shù)據(jù)碼加上糾錯(cuò)碼的？首先需要對數(shù)據(jù)碼進(jìn)行分組，也就是分成不同的Block，然后對各個(gè)Block進(jìn)行糾錯(cuò)編碼，對于如何分組，可以查看QR Code Spec的定義表。這里注意最后兩列：Number of Error Code Correcti

14、on Blocks ：需要分多少個(gè)塊。Error Correction Code Per Blocks：每一個(gè)塊中的code個(gè)數(shù)，所謂的code的個(gè)數(shù)，也就是有多少個(gè)8bits的字節(jié)。舉例說明：上述的Version 5 + Q糾錯(cuò)級：需要4個(gè)Blocks（2個(gè)Blocks為一組，共兩組），第一組的兩個(gè)Blocks中各15個(gè)bits數(shù)據(jù) + 各 9個(gè)bits的糾錯(cuò)碼（注：表中的codewords就是一個(gè)8bits的byte）（再注：最后一例中的（c, k, r ）的公式為：c = k + 2 * r，因?yàn)楹竽_注解釋了：糾錯(cuò)碼的容量小于糾錯(cuò)碼的一半）下圖給一個(gè)5-Q的示例（因?yàn)槎M(jìn)制寫起來會(huì)讓表格

15、太大，這里使用十進(jìn)制表示，可以看到每一塊的糾錯(cuò)碼有18個(gè)codewords，也就是18個(gè)8bits的二進(jìn)制數(shù)）組塊數(shù)據(jù)對每個(gè)塊的糾錯(cuò)碼1167 85 70 134 87 38 85 194 119 50 6 18 6 103 38213 199 11 45 115 247 241 223 229 248 154 117 154 111 86 161 111 392246 246 66 7 118 134 242 7 38 86 22 198 199 146 687 204 96 60 202 182 124 157 200 134 27 129 209 17 163 163 120 13321

16、182 230 247 119 50 7 118 134 87 38 82 6 134 151 50 7148 116 177 212 76 133 75 242 238 76 195 230 189 10 108 240 192 141270 247 118 86 194 6 151 50 16 236 17 236 17 236 17 236235 159 5 173 24 147 59 33 106 40 255 172 82 2 131 32 178 236（注：二維碼的糾錯(cuò)碼主要是通過Reed-Solomon error correction（里德-所羅門糾錯(cuò)算法）來實(shí)現(xiàn)的）。七、

17、最終編碼上述步驟完成之后，還要把數(shù)據(jù)碼和糾錯(cuò)碼的各個(gè)codewords交替放在一起。交替規(guī)則如下：對于數(shù)據(jù)碼：把每個(gè)塊的第一個(gè)codewords先拿出來按順度排列好，然后再取第一塊的第二個(gè)，如此類推。如上述示例中的Data Codewords如下：塊 167857013487388519411950618610338塊 224624666711813424273886221981991466塊 31822302471195071181348738826134151507塊 4702471188619461515016236172361723617236我們先取第一列的：67， 246， 182

18、， 70然后再取第二列的：67， 246， 182， 70， 85，246，230 ，247如此類推：67， 246， 182， 70， 85，246，230 ，247 ，38，6，50，17，7，236對于糾錯(cuò)碼，也是一樣：塊 121319911451152472412232292481541171541118616111139塊 28720496602021821241572001342712920917163163120133塊 314811617721276133752422387619523018910108240192141塊 423515951732414759331064025

19、517282213132178236和數(shù)據(jù)碼取的一樣，得到：213，87，148，235，199，204，116，159， 39，133，141，236然后，再把這兩組放在一起（糾錯(cuò)碼放在數(shù)據(jù)碼之后）得到：67, 246, 182, 70, 85, 246, 230, 247, 70, 66, 247, 118, 134, 7, 119, 86, 87, 118, 50, 194, 38, 134, 7, 6, 85, 242, 118, 151, 194, 7, 134, 50, 119, 38, 87, 16, 50, 86, 38, 236, 6, 22, 82, 17, 18, 198

20、, 6, 236, 6, 199, 134, 17, 103, 146, 151, 236, 38, 6, 50, 17, 7, 236, 213, 87, 148, 235, 199, 204, 116, 159, 11, 96, 177, 5, 45, 60, 212, 173, 115, 202, 76, 24, 247, 182, 133, 147, 241, 124, 75, 59, 223, 157, 242, 33, 229, 200, 238, 106, 248, 134, 76, 40, 154, 27, 195, 255, 117, 129, 230, 172, 154,

21、209, 189, 82, 111, 17, 10, 2, 86, 163, 108, 131, 161, 163, 240, 32, 111, 120, 192, 178, 39, 133, 141, 236這就是數(shù)據(jù)區(qū)。Remainder Bits最后再加上Reminder Bits，對于某些Version的QR，上面的還不夠長度，還要加上Remainder Bits，比如：上述的5Q版的二維碼，還要加上7個(gè)bits，Remainder Bits加零就好了。關(guān)于哪些Version需要多少個(gè)Remainder bit，可以參看QR Code Spec的第15頁的Table-1的定義表。八、

22、畫二維碼圖Position Detection Pattern首先，先把Position Detection圖案畫在三個(gè)角上。（無論Version如何，這個(gè)圖案的尺寸不變）Alignment Pattern然后，再把Alignment圖案畫上（無論Version如何，這個(gè)圖案的尺寸就是這么大）關(guān)于Alignment的位置，可以查看QR Code Spec的第81頁的Table-E.1的定義表（下表是不完全表格）下圖是根據(jù)上述表格中的Version8的一個(gè)例子（6，24，42）Timing Pattern接下來是Timing Pattern的線ormat Information再接下來是Form

23、ation Information，下圖中的藍(lán)色部分。Format Information是一個(gè)15個(gè)bits的信息，每一個(gè)bit的位置如下圖所示：（注意圖中的Dark Module，是永遠(yuǎn)出現(xiàn)的）這15個(gè)bits中包括：5個(gè)數(shù)據(jù)bits：其中，2個(gè)bits用于表示使用什么樣的Error Correction Level， 3個(gè)bits表示使用什么樣的Mask10個(gè)糾錯(cuò)bits。主要通過BCH Code來計(jì)算然后15個(gè)bits還要與101010000010010做XOR操作。這樣就保證不會(huì)因?yàn)槲覀冞x用了00的糾錯(cuò)級別和000的Mask，從而造成全部為白色，這會(huì)增加我們的掃描器的圖像識別的困難。

24、下面是一個(gè)示例：關(guān)于Error Correction Level如下表所示：關(guān)于Mask圖案如后面的Table 23所示。Version Information再接下來是Version Information（版本7以后需要這個(gè)編碼），下圖中的藍(lán)色部分。Version Information一共是18個(gè)bits，其中包括6個(gè)bits的版本號以及12個(gè)bits的糾錯(cuò)碼，下面是一個(gè)示例：而其填充位置如下：數(shù)據(jù)和數(shù)據(jù)糾錯(cuò)碼然后是填接我們的最終編碼，最終編碼的填充方式如下：從左下角開始沿著紅線填我們的各個(gè)bits，1是黑色，0是白色。如果遇到了上面的非數(shù)據(jù)區(qū)，則繞開或跳過。掩碼圖案這樣下來，圖基本填好

25、了，但是，也許那些點(diǎn)并不均衡，如果出現(xiàn)大面積的空白或黑塊，掃描識別會(huì)變得困難。所以，最后還要做Masking操作。QR的Spec中描述到，QR有8個(gè)Mask你可以使用，其中，各個(gè)mask的公式在各個(gè)圖下面。所謂mask，就是和上面生成的圖做XOR操作。Mask只會(huì)和數(shù)據(jù)區(qū)進(jìn)行XOR，不會(huì)影響功能區(qū)。（注：選擇一個(gè)合適的Mask也是有算法的）其Mask的標(biāo)識碼如下所示：（其中的i,j分別對應(yīng)于上圖的x,y）下面是Mask后的一些樣子，可以看到被某些Mask XOR了的數(shù)據(jù)變得比較零散了。Mask過后的二維碼就成最終的圖了。九、 識別：既然二維碼的生成搞懂了，那么識別就會(huì)變得簡單，基本上就是生成的

26、逆過程。對于手機(jī)端掃描QR二維碼的識別而言，重點(diǎn)在于攝像頭獲取數(shù)據(jù)后，對數(shù)據(jù)的最初處理，這里以Android手機(jī)識別QR二維碼為例、以源碼為主要依據(jù)進(jìn)行簡要說明。1、 獲取攝像頭原始數(shù)據(jù)。首先Android提供了PreviewCallback接口，只要在Activity里實(shí)現(xiàn)PreviewCallback接口后，就會(huì)自動(dòng)重載這個(gè)函數(shù)：public void onPreviewFrame(byte data, Camera camera) 這個(gè)函數(shù)里的data就是實(shí)時(shí)預(yù)覽幀視頻，也就是攝像頭返回的最原始的數(shù)據(jù)。這樣，就解決了如何獲取攝像頭數(shù)據(jù)的問題。一旦程序調(diào)用PreviewCallback接口

27、，就會(huì)自動(dòng)調(diào)用onPreviewFrame這個(gè)函數(shù)。調(diào)用PreviewCallback的方法有三種。分別是：setPreviewCallback, setOneShotPreviewCallback, setPreviewCallbackWithBuffer,程序中使用第二種方式，示例如下：至于何時(shí)觸發(fā)onPreviewFrame()這個(gè)函數(shù)來獲得攝像頭數(shù)據(jù)，一般選擇按一個(gè)按鍵觸發(fā)一次或者每隔一段時(shí)間觸發(fā)一次，無論如何，只要在該觸發(fā)的地方寫上Camera.setOneShotPreviewCallback(RectPhoto.this);便會(huì)自動(dòng)觸發(fā)一次。這樣我們就可以得到手機(jī)攝像頭實(shí)時(shí)預(yù)覽幀

28、視頻數(shù)據(jù)data。2、 解碼數(shù)據(jù)獲取該數(shù)據(jù)后，要對二維碼進(jìn)行解碼，我們在DecodeHandler類中定義了解碼方法：private void decode(byte data, int width, int height)我們重點(diǎn)對該方法進(jìn)行分析： 第78-82行代碼，最初的數(shù)據(jù)應(yīng)該被看成為一個(gè)矩陣數(shù)據(jù)，只是把它存放在一維數(shù)組byte中，這里是將其轉(zhuǎn)換成轉(zhuǎn)置矩陣，即aij與aji交換，因此在83-85行代碼中，對寬高也進(jìn)行了調(diào)換； 第88-95行代碼，這是解析數(shù)據(jù)最為關(guān)鍵的代碼，88行我們定義了PlanarYUVLuminanceSource類的對象，關(guān)于YUV數(shù)據(jù)格式以及該類的介紹參見后面

29、的附錄一。 最后，需要將PlanarYUVLuminanceSource類處理的數(shù)據(jù)轉(zhuǎn)化成Bitmap對象。代碼的第91行即為此操作。 至此，我們得到了二維碼圖片的Bitmap對象，就可以按照二維碼生成的逆過程運(yùn)算對數(shù)據(jù)進(jìn)行解析。 解碼示例：例如，程序在進(jìn)行解碼分析時(shí)，首先要根據(jù)版本信息和糾錯(cuò)級別進(jìn)行判斷，即讀取Version Information和Data and Error Correction Codewords處數(shù)據(jù)，若取得版本為1，接錯(cuò)級別為H，按照QR碼的規(guī)范，查下表：可知應(yīng)讀取數(shù)據(jù)區(qū)連續(xù)的72個(gè)bits作為一個(gè)整體，比如我們讀到如下數(shù)據(jù)： 00100000 00101001 1

30、1001110 11100111 00100001 00000000 11101100 00010001 11101100對于該數(shù)據(jù)，按照QR碼的規(guī)范，前四位為編碼格式編號，即0010對應(yīng)的是字符編號，說明后面的內(nèi)容為字符；根據(jù)QR碼編碼規(guī)范，版本為1、糾錯(cuò)級別為H的編碼，數(shù)字個(gè)數(shù)占九位，即取編碼格式編號的后九位：000000101，轉(zhuǎn)換成十進(jìn)制為5，即得知該數(shù)據(jù)包含5個(gè)字符。再次按照QR碼編碼規(guī)范，字符編碼過程中，每一組數(shù)據(jù)為11位，并且如果最后有一個(gè)落單的，那就轉(zhuǎn)成6bits的二進(jìn)制。那么根據(jù)有5個(gè)字符，我們?nèi)‰S后的28位數(shù)據(jù)，即為真正的數(shù)據(jù)編碼：00111001110 111001110

31、01 000010將上述三組數(shù)據(jù)轉(zhuǎn)換成十進(jìn)制即為(462,1849,2)，根據(jù)字符編碼的編碼規(guī)范，編碼的過程是把字符兩兩分組，然后轉(zhuǎn)成下表的45進(jìn)制。那么，分別將462、1849、2轉(zhuǎn)化為45進(jìn)制轉(zhuǎn)換之前的數(shù)據(jù)，得到(10,12) (41,4) (2)，查詢字符編碼表，得出對應(yīng)的字符分別為：A,C,-,4,2，即原始數(shù)據(jù)為AC-42，解碼結(jié)束。3、 將獲取數(shù)據(jù)與解碼關(guān)聯(lián)在實(shí)際的應(yīng)用中，因?yàn)閿?shù)據(jù)的識別解析過程比較慢，并且二維碼識別、解碼一次不一定能成功，那么要如何科學(xué)的把上述兩步（獲取數(shù)據(jù)與解碼）關(guān)聯(lián)在一起呢？首先，由于數(shù)據(jù)識別和解析是一個(gè)耗時(shí)操作，我們要利用線程機(jī)制，在一個(gè)線程中操作，這里我們定義了一個(gè)繼承Thread的DecodeThread類，該線程與DecodeHandler配合，完成解析數(shù)據(jù)的功能，由于一次識別不一定成功，那么就要在每次識別失敗之后，重新調(diào)用第一小節(jié)中提到的方法，重新獲取攝像頭數(shù)據(jù)進(jìn)行再一次的解析。如此反復(fù)直到成功。那么程序又是如何判定失敗的呢？在上面貼出的第95行代碼處，將最終的解析結(jié)果放置在rawResult變量中，后面對該變量就行判斷，若不為空，則表示解析成功，若為空表示解析失敗，程序會(huì)向主線程發(fā)送解析失敗的消息，來進(jìn)行再一次的解析過程。附錄一：YUV