转载

QR code 金庸小说体(二)

  • 传说

在二维码世纪,流传着这样一个传说,long long ago,武林一片混乱,这时魔教二长老创立了一门绝世武功——QR code,随后称霸武林。但同时也遭到武林中人的觊觎和反抗,各大武林正派掌门人一起修炼了一套对付二长老的神功。终于经历了七天七夜昏天地暗的恶战后,联盟取得了胜利,但二长老和各大掌门们却从此失踪,也在没有人知道他们的绝世武学。魔教因此隐匿,从此与武林井水不犯河水,武林风平浪静。直到互联网(没错,玩的就是穿越)的出现……

  • 屌丝遇难

由于互联网的出现,武林中便又开始传起了关于武功秘籍的各种谣言,一场腥风血雨即将来临。各派各路人马以及魔教因此大打出手。此时各方势力同时盯上了谣言中当日恶战附近的小镇。整个小镇惨遭屠杀,一夜之间变成了废墟(果然谣言害死人)。唯独镇上一屌丝(一块”白布“啦)晕倒掉进溪流冲上了某个神秘的小岛……

  • 口诀

幸存下来的屌丝在岛上活了下来,几个月后屌丝意外发现了一出秘密洞穴。找到了长老们留下的口诀(放心绝不会有”欲练此功……“):

1 校正图形(Alignment Pattern)用于确立矩阵符号位置的一个固定的参照图形,解码译码软件可以通过它在图象有中等程度损坏的情况下,再同步图像模块的坐标映象。

2 字符计数指示符(Character Count Indicator)定义某一模式下的数据串长度的位序列。

3 ECI 指示符(ECI designator)6 位数字,用于标识具体的 ECI 任务。

4 编码区域(encoding region)在符号中没有被功能图形占用,可以对数据或错误纠正纠错码字进行编码的区域。 

6 扩展图形(Extension Pattern)

模式 1 中,不表示数据的一种功能图形。

7 格式信息(Format Information)一种功能图形,它包含符号使用的错误纠正纠错等级以及使用的掩模图形的信息,以便对编码区域的剩余部分进行译码。

8 功能图形(function pattern)包含帮助译码的符号定位或者它的特征识别信息的符号附加成分,。符号中用于符号定位与特征识别的特定图形。

9 掩模图形参考(Mask Pattern Reference)用于符号中的三位三位掩模图形标识符。

10 掩模(masking)在城内编码区域内,用掩模图形对在城内编码区的位图进行 XOR 操作,其目的是使符号中深色与浅色模块数的比例均衡,并且减少影响图像快速处理的图形出现。

11 模式(mode)将特定的字符集表示成位串的方法。

12 模式指示符(Mode Indicator)4 位标识符,指示随后的数据序列所用的编码模式。

13 填充位(Padding Bit)值为 0,不表示数据,用于填充数据位流最后一个码字中终止符后面的空位。

14 位置探测图形(Position Detection Pattern)组成寻象图形的三个相同的图形之一。

15 剩余位(Remainder Bit)值为 0,不表示数据,当编码区域不能正好被 8 位的码字填满时,用于填充最后一个码字后的空位。

16 剩余码字(Remainder Codeword)一种填充码字,当所有的数据码字和错误纠正纠错码字不能正好填满符号的容量时,用于填充一种填充码字所空码字位置,它们紧跟在最后一个错误纠正纠错码字之后。

17 段(segment)以同一 ECI 或编码模式编码的数据序列。

18 分隔符(Separator)全部由浅色模块组成的功能图形,宽度为一个模块,用于将位置探测图形与符号的其余部分分开。

19 终止符(Terminator)用于结束表示数据位流的位图 0000。

20 定位图形(Timing Pattern)深色与浅色模块交错的图形,便于决定符号中模块的坐标。

21 版本(Version)用于表示符号规格的系列。某一特定版本是根据它在所允许的规格系列中的位置来确定的。QR 码所允许规格系列为 21×21 模块(版本 1)~177×177 模块(版本40)。它也可同时指示符号所应用的纠错等级。

22 版本信息(Version Information)在模式 2 符号中,包含符号版本的信息及该数据错误纠正纠错位的功能图形。

(再次说明,口诀什么的可都是来自 上一篇的给出的链接文档 中)

  • 招式

说到口诀,都是为招式做铺垫。不知道口诀,可不好理解招式 。

看看什么地方该干嘛:

QR code 金庸小说体(二)

1. 3个黑色和黄色同心的正方块 ——Position Detection Pattern  位置探测图形(7*7,5*5,3*3) 

坐标:{(0,0)(7,7)},{((21+(version-1)*4)-7,0),(21+(version-1)*4-1,7)}{(0,(21+(version-1)*4)-7),(7,21+(version-1)*4-1)}

2. 3个绿色直角 ——Separator  分隔符(1*8,8*1)

3. 蓝、白色正方块 ——Alignment Pattern  校正图形(5*5,3*3,1*1)

坐标:{((21+(version-1)*4)-9,(21+(version-1)*4)-9),((21+(version-1)*4)-4,(21+(version-1)*4)-4)}

4. 2条橙、灰色相间条 ——Timing Pattren  定位图形

作用:便于定位坐标

5. 品红和红色条 ——都是Format Information  格式信息(各15位)

由于格式信息和版本信息(图中没有,版本7以上有)很重要,因此都存储了两次,也就是品红条和红色条存储的15位是相同数据。

品红条上的黑点也属于格式模块,位置(4v+9,8),总是深色。其中v是版本号,4是每个版本增加的模块数。

15位中,前五位为数据位,分别为

第1、2位为纠错等级(L——01,M——00,Q——11,H——10)

第3~5位为掩模图形参数Mask Pattern Reference(选值下面介绍)

后10位为纠错数据(以上15位将是原始数据而不是最终存储数据)

6. 所有剩下白色区域 ——存放数据和纠错码字的区域

说明:上图只适用于版本2~6(7及以上都有两块存放版本信息的模块)

版本1——无版本信息、校正图形 版本7~13——3^2-3=6校正图形 版本21~27——5^2-3=22校正图形

版本2~6——与图中一样 版本14~20 ——4^2-3=13校正图形 版本28~34——6^2-3=33校正图形

版本35~41——7^2-3=46校正图形

  • 入门内功

第一层(步): 数据分析分析所输入的数据流, 确定要进行编码的字符的类型 。QR 码支持扩充解释,可以对与缺省的字符集不同的数据进行编码。QR 码包括几种不同的模式,以便高效的地将不同的字符子集转换为符号字符。必要时可以进行模式之间的转换更高效地将数据转换,以便为二进制串。 选择所需的错误检测和纠正等级 。如果用户没有指定所采用的符号版本,则 选择与数据相适应的最小的版本

第二层:数据编码对于采用的模式按照 定义的规则, 将数据字符转换为位流 。在当需要进行模式转换时,在新的模式段开始前加入模式指示符进行模式转换。在数据序列后面 加入终止符 。将产生的位流分为每 8 位一个码字。必要时加入 填充字符 以填满按照版本要求的数据码字数。

第三层:纠错编码按需要 将码字序列分块 ,以便按块 生成相应的错误纠正纠错码字 ,并将其 加入到相应的数据码字序列的后面

第四层: 构造最终信息 按 第三步的描述,在每一块中置入数据和纠错码字,必要时加剩余位

第五层:在矩阵中布置模块将寻象图形、分隔符、定位图形、校正图形与码字模块一起放入矩阵。

第六层:掩模依次将掩模图形用于符号的编码区域。评价结果,并 选择 其中使深色浅色模块比率 最优 且使不希望出现的 图形 最少化的结果。

第七步:格式和版本信息生成格式和版本信息(如果用到时),形成符号。

结论:前面的每一层都将成为后面操作的基础。

  • 内功外传——格式信息和数据编码

(上次给的那篇链接文档少了附录,找了很久才找到搭配的附录文档————> 这是链接 )

…………………………格式信息………………………………………………

第1、2位为纠错等级(L——01,M——00,Q——11,H——10)

第3~5位为掩模图形参数Mask Pattern Reference

000——(x+y)%2=0 011——(x+y)%3=3 110——((x*y)%2+(x*y)%3)%2=0

001——x%2=0 100——((x/2)+(y/3))%2=0

010——y%3=0   101——(x*y)%2+(x*y)%3=0

以011为例:

QR code 金庸小说体(二)

当然,从入门内功中可以看到,这三位可不是好确定的,是需要大量运算后对比确定的(看入门内功)。下面介绍后十位的原始数据(最终数据是掩摸后的)计算方法——

BCH(15,5)   (声明下面将会用到很多带次方的多项式,为了方便书写,因此“x"后面的数字就是次数)

BCH(15,5)码用于纠错。以数据位串为系数的多项式被生成多项式 G(x)(至于G(x)怎么求再说) 除,所得剩余多项式的系数串应追加到数据位串上形(15,5)BCH 码字符串。最后,通过与掩摸图形对位串进行异或(XOR)运算进行掩模,来保证掩模图形和纠错等级的任意组合的格式信息位图不全为 0。

附录中例子是这样的——

BCH(15,5)码用于纠错。以数据位串为系数的多项式被生成多项式 G(x) =X10+X8+X5+X4+X2+X+1 除,所得剩余多项式的系数串应追加到数据位串上形(15,5)BCH 码字符串。

例:纠错等级 M;掩模图形 101

二进制字符串: 00101

生成多项式: X2+1

将次数升至(15-5): X12+X10

被 G(X)除后得   = (x10 + x8 + x5 + x4 + x2 + x + 1)x2 + (x7 + x6 + x4 + x3 + x2)

把上面的剩余多项式的系数字符串附加至格式信息数据串。

00101+0011011100      → 001010011011100

那么从上面的例子中有这些疑问:

1. G(x)怎么来的?

2. 为什么要提升次数?

3. 怎么除?

下面将一一解决这些问题:

1. BCH(n,k)中

G(x)——生成多项式

C(x)——数据码生成多项式

R(x)——为C(x)/G(x)余式

三者关系:

R(x)={x^(n-k)*C(x)}/G(x)——————这就是为什么提升次数的原因,乘了x^(n-k),BCH(15,5)中乘x10。

2. G(x)的计算

循环码中定理:G(x)是(n,k)循环码的生成多项式当且仅当G(x)是x^n-1的r=n-k次因式。而BCH码是循环码的子类。

如:

(x15+1) = (x10+x8+x5+x4+x2+x+1)(x5+x3+x+1)……………………因此BCH(15,5)的G(x)=x10+x8+x5+x4+x2+x+1(101001101011)

(x15+1) = (x4+x+1)(x11+x8+x7+x5+x3+x2+x+1)……………………因此BCH(15,11)的G(x)=x4+x+1  (010011)

3. 模2多项式除法

{x^(n-k)*C(x)}/G(x)采用的是模2多项式除法——长除, 整式除法

多项式除以多项式一般用竖式进行演算

(1)把被 除式 、除式按某个字母作 降幂 排列,并把所缺的项用零补齐.

(2)用被除式的第一项除以除式第一项,得到商式的第一项.

(3)用 商式 的第一项去乘除式,把积写在被除式下面(同类项对齐),消去相等项,把不相等的项结合起来.

(4)把减得的差当作新的被除式,再按照上面的方法继续演算,直到余式为零或余式的次数低于除式的次数时为止

……………………………… 数据编码 ……………………………………………………

(以数字模式,模式1、2-L为例)

1 输入数据: 15162100138

2 分为三位一组: 151、621、001、38

3 转换为二进制(10位):   151——0010010111

621——1001100011

001——0000000001

38——0100110(最后一组1位用4bit,2位用7bit,3位用10bit)

4 Character Count Indicator字数计数指示符(10bit): 有11位 编码为 0000001011

5 模式指示符(4bit):数字模式的模式指示符为 0001

6 按模式指示符+字数计数指示符+数据+终止符0000(如果前面四项已经填满容量可缺省1,2,3,4位终止符)

0001 0000001011 0010010111 1001100011 0000000001 0100110 0000

7 分成8bit一段

0001 0000 001011 00 10010111 10011000 11 000000 0001 0100 110 0000 0 (最后一bit为填充位)

8 总量34,故需34-7=27填充码字(显然不科学,所以第一步是数据分析呢)

填充码字为 11101100  00010001交替填充

9 纠错编码

这是最蛋疼的事了,应该是计算量最大的部分了。用Seed-Solomon算法计算。具体可参照纠错码计算然后查表吧。

…………

神功已成

  • 那你就错了

然而并没有什么卵用,屌丝仍然是屌丝。你都看到了,最困难的就是内功(算法)了。没有内功(算法)技能(二维码图)打出来没伤害(扫不出来),”白布“上就是一堆乱码。

当然剧本不可能就这么完了……

预知后事如何,请自个儿修炼(下回分解?别逗了,好难写了,草人桌子上两罐饮料了……)

附:草人写这博文时的代码(没什么用,除了关键地方没实现,代码也只是为了生成上面的图便于写文)

QR code 金庸小说体(二)
package zry.QRcode; import java.awt.Color; import java.awt.Graphics2D; import java.awt.image.BufferedImage; import java.io.FileOutputStream; import java.io.IOException; import javax.imageio.ImageIO; import spoofQRcode.CreatQRImage2; public class CreateQRcodeImage {  private FileOutputStream fos = null;  private BufferedImage buffImg = null;  private Graphics2D gs = null;  private Color m_deepColor = Color.black;  private Color m_lightColor = Color.white;  /** 构造函数,创建一块画布(“白布”)   * @throws IOException */  public CreateQRcodeImage(int imgSize) throws IOException{   // TODO Auto-generated constructor stub   buffImg = new BufferedImage(imgSize, imgSize, BufferedImage.TYPE_INT_RGB);    gs = buffImg.createGraphics();    gs.setBackground(Color.WHITE);     gs.clearRect(0, 0, imgSize, imgSize);   System.out.println("画布已经被创建");   //drawMaskPattern(2,m_deepColor,8,"011");   //drawPatternBoundary(2,Color.black,8);   //drawSeparator(2,Color.green,8);   //drawPositionDetectionPattern(2,Color.black,8);   //drawAlignmentPattern(2,Color.blue,8);   //drawTimingPattern(2,Color.orange,8);   //drawFormatInformation1(2,Color.magenta,8);   //drawFormatInformation2(2,Color.red,8);   drawPositionDetectionPattern(2,m_deepColor,8);   drawAlignmentPattern(2,m_deepColor,8);   drawTimingPattern(2,m_deepColor,8);   gs.dispose();     buffImg.flush();   fos=new FileOutputStream("F:/zzzzzz027.png");   ImageIO.write(buffImg, "png", fos);   } /*  public void drawPatternBoundary(int version,    Color patternColor,int patternSize){   gs.setColor(patternColor);   for(int i = 0;i < 21+(version-1)*4;i++)    for(int j = 0;j < 21+(version-1)*4;j++)     gs.fillRect(i*patternSize,j*patternSize,1,1);  } */   /**   * 填充指定区域(x*width,y*height)   * @param x 起始行坐标   * @param y 起始纵坐标   * @param width 行长度(长)   * @param height 列长度(宽)   * @param patternColor 填充颜色   * @param patternSize 每个块单位大小   */  public void drawPattern(int x,int y,int width,int height,    Color patternColor,int patternSize){   gs.setColor(patternColor);   for(int i = x;i < width+x;i++)    for(int j = y;j < height+y;j++)     gs.fillRect(i*patternSize,j*patternSize,patternSize,patternSize);  }  /**   * 填充分隔符域,用浅色   * @param version   * @param patternColor   * @param patternSize   */  public void drawSeparator(int version,    Color patternColor,int patternSize){   drawPattern(0,0,8,8,patternColor,patternSize);   drawPattern((21+(version-1)*4)-8,0,8,8,patternColor,patternSize);   drawPattern(0,(21+(version-1)*4)-8,8,8,patternColor,patternSize);  }  /**   * 填充位置探测图形   * @param version 版本   * @param patternColor 填充颜色   * @param patternSize 每个块单位大小   */  public void drawPositionDetectionPattern(int version,    Color patternColor,int patternSize){   /**左上角*/   drawPattern(0,0,7,7,patternColor,patternSize);   drawPattern(1,1,5,5,m_lightColor,patternSize);   drawPattern(2,2,3,3,patternColor,patternSize);   /**右上角*/   drawPattern((21+(version-1)*4)-7,0,7,7,patternColor,patternSize);   drawPattern((21+(version-1)*4)-7+1,1,5,5,m_lightColor,patternSize);   drawPattern((21+(version-1)*4)-7+2,2,3,3,patternColor,patternSize);   /**左下角*/   drawPattern(0,(21+(version-1)*4)-7,7,7,patternColor,patternSize);   drawPattern(1,(21+(version-1)*4)-7+1,5,5,m_lightColor,patternSize);   drawPattern(2,(21+(version-1)*4)-7+2,3,3,patternColor,patternSize);   }  /**   * 填充校正图形(校正图形需要版本来确定数量和位置的,这儿只写出了2-6版本,用到的每块单位大小也   * 要由版本和画布大小计算出,patternSize=imgSize/(21+(version-1)*4)   * @param version 版本   * @param patternColor 填充颜色   * @param patternSize 每个块单位大小   */  public void drawAlignmentPattern(int version,    Color patternColor,int patternSize){   drawPattern((21+(version-1)*4)-9,(21+(version-1)*4)-9,5,5,patternColor,patternSize);   drawPattern((21+(version-1)*4)-8,(21+(version-1)*4)-8,3,3,m_lightColor,patternSize);   drawPattern((21+(version-1)*4)-7,(21+(version-1)*4)-7,1,1,patternColor,patternSize);  }  /**   * 填充定位图形   * @param version   * @param patternColor   * @param patternSize   */  public void drawTimingPattern(int version,    Color patternColor,int patternSize){   for(int x = 8;x < (21+(version-1)*4)-8; x++){    if(x%2==0)     drawPattern(x,6,1,1,patternColor,patternSize);    else      drawPattern(x,6,1,1,m_lightColor,patternSize);   }   for(int y = 8;y < (21+(version-1)*4)-8; y++){    if(y%2==0)     drawPattern(6,y,1,1,patternColor,patternSize);    else      drawPattern(6,y,1,1,m_lightColor,patternSize);   }  }  /*************************以上是功能图形************************/  /**   * 填充格式信息,为了好看图写   * @param version   * @param patternColor   * @param patternSize   */  public void drawFormatInformation1(int version,    Color patternColor,int patternSize){   for(int y = 0;y < 21+(version-1)*4;y++){    if(y!=6&&y<9||y>(21+(version-1)*4-8)){     drawPattern(8,y,1,1,patternColor,patternSize);    }   }   drawPattern(8,(21+(version-1)*4-8),1,1,m_deepColor,patternSize);  }  /**   * 填充格式信息,为了好看图写   * @param version   * @param patternColor   * @param patternSize   */  public void drawFormatInformation2(int version,    Color patternColor,int patternSize){   for(int x = 0;x < 21+(version-1)*4;x++){    if(x!=6&&x<8||x>(21+(version-1)*4-9)){     drawPattern(x,8,1,1,patternColor,patternSize);    }   }  }  public void drawMaskPattern(int version,    Color patternColor,int patternSize,String maskPatternReference){   if(maskPatternReference == "000"){   }   if(maskPatternReference == "001"){   }   if(maskPatternReference == "010"){   }   if(maskPatternReference == "011"){    for(int x = 0;x < 21+(version-1)*4;x++)     for(int y = 0;y < 21+(version-1)*4;y++)      if((x+y)%3 == 0){       //System.out.print(x);       //System.out.println(y);       gs.setColor(patternColor);       gs.fillRect(x*patternSize,y*patternSize,patternSize,patternSize);       //System.out.println("ok");      }   }   if(maskPatternReference == "100"){   }   if(maskPatternReference == "101"){    for(int x = 0;x < 21+(version-1)*4-1;x++)     for(int y = 0;y < 21+(version-1)*4-1;y++)      if((x*y)%2+(x*y)%3 == 0){       //System.out.print(x);       //System.out.println(y);       gs.setColor(patternColor);       gs.fillRect(x*patternSize,y*patternSize,patternSize,patternSize);       //System.out.println("ok");      }   }   if(maskPatternReference == "110"){   }  }  public static void main(String[] args) throws IOException{   int imgSize = 200;   CreateQRcodeImage obj = new CreateQRcodeImage(imgSize);  } } 
View Code
正文到此结束
Loading...