Go で QR コード生成を自作する

はじめに

みなさん QR コードを利用する機会が多いかと思うのですが、どうやってエンコードしているのか気になったことはありませんか？　私は気になって自作してみたので、処理の流れを本記事でまとめてみました。

https://github.com/ksrnnb/qrcode

そもそも QR コードってどういうもの？

QR コードは、文字列を単純に画像化したものではなく、文字列を符号化してから画像化しています。符号化によって、一部のデータが欠損してしまっても誤りを検出して訂正することができるようになっています。つまり、 QR コードは汚れなどでデータが一部欠損してしまっても元のデータを読み取ることができます。このようにデータの誤りを検出して訂正することを誤り訂正と呼びます。

以下のページは誤り訂正がイメージしやすいのでオススメです。
https://b.qrqrq.com/2018/10/31/qr-code_scanpoint#i

エンコード手順

試しに、Hello, World! でエンコードした結果がこちらの画像になります。

この QR コードを生成するために、以下のような操作が必要となります。本来はもう少し処理が必要なのですが、今回は簡単な場合のみ考えます。

• 入力文字とエラー訂正レベルから QR コードの大きさを決める
• QR コード構造体の生成
• クワイエットゾーンの設定
• 位置検出パターンの設定
• 分離パターンの設定
• タイミングパターンの設定
• 形式情報の符号化・設定
• 入力文字の符号化・設定
• マスク処理
• マスク評価
• 画像化

入力文字と誤り訂正レベルから QR コードの大きさを決める

QR コードの誤り訂正レベルは以下のように定義されています。これは QR コードを生成するクライアントが自由に決めます。この誤り訂正レベルと、入力文字の長さから、QR コードの型番（大きさ）を決定します。

誤り訂正レベル	復元可能な割合
L	7%
M	15%
Q	25%
H	30%

コードは以下のようになります。今回は、簡単のため入力文字数が一番少ない1型 version: 1 のみサポートするようにしました。さらに入力文字は ASCII コードの文字に限定する8ビットバイトモードと呼ばれるモード mode: EightBits のみ対象としました。

ここでは型番、誤り訂正レベルに応じて、入力可能な文字数が決められているのでそれらの値を一緒に構造体にまとめて返すようにしています。例えば、1型で誤り訂正レベルが L の場合、最大入力文字は17バイトまでで、符号化して得られるデータの容量は26バイトとなります。

func newQRInfo(ecl ErrorCorrectionLevel, src string) qrInfo {
	// supports only version 1
	switch ecl {
	case ECL_Low:
		return qrInfo{
			version:            1,
			ecl:                ecl,
			mode:               EightBits,
			dataCap:            26,
			countDataCodeWords: 19,
			srcCap:             17,
			src:                src,
		}
	case ECL_Medium:
		...
	}
}

QR コード構造体の生成

構造体生成のコードは以下のようになっています。ここで重要なのは modules フィールドと dirties フィールドになります。これらに QR コード画像の情報を入れていきます。ここでモジュールとは、ドット1個分のことを指し、true であれば暗モジュール、false であれば明モジュールとします。暗モジュールとは黒色、明モジュールとは白色のモジュールと考えて OK です。

なぜ modules と同じ大きさのスライス dirties を用意するのか気になるかと思うのですが、のちに出てくるマスク処理のときに、マスク処理を施すべき位置かどうかを判定するために使います。

スライスのサイズが size+2*quietZoneSize となっているのは、縦と横ともにクワイエットゾーンと呼ばれる領域が 2*クワイエットゾーン幅 あるので、このようなサイズになっています。

func newQRCode(ecl ErrorCorrectionLevel, mask uint8, data *bitset.BitSet) *QRCode {
	// version1: module size per line is 21
	size := 21

	q := &QRCode{
		ecl:     ecl,
		mask:    mask,
		data:    data,
		modules: make([][]bool, size+2*quietZoneSize),
		dirties: make([][]bool, size+2*quietZoneSize),
		size:    size,
	}

	for i := range q.modules {
		q.modules[i] = make([]bool, size+2*quietZoneSize)
		q.dirties[i] = make([]bool, size+2*quietZoneSize)
	}

	q.build()

	return q
}

クワイエットゾーン

クワイエットゾーンは QR コードのまわりの白色の領域です。背景に色をつけると分かりやすいのですが、QR コードの周りには4モジュール分の幅のクワイエットゾーンが設けられます。

実際にデータを代入する際に、 dirties を true にしています。これは先ほど述べましたが、マスク処理の判定時に使います。また、クワイエットゾーンは意識しないで済むように、クワイエットゾーンよりも内側の座標を指定するようにしました。

func (q *QRCode) add(x int, y int, v bool) {
	q.modules[y+quietZoneSize][x+quietZoneSize] = v
	q.dirties[y+quietZoneSize][x+quietZoneSize] = true
}

位置検出パターン

左上、右上、左下にある3個の同心正方形は、位置検出パターンと呼ばれます。この3個の位置検出パターンによって、 QR コードの大きさや、回転方向などを認識することができます。

コードは以下のようになります。 add2dPattern という汎用的なメソッドを用意して、2次元スライスを渡すと、指定した位置に暗・明モジュールを配置するようになります。

var (
	finderPattern = [][]bool{
		{true, true, true, true, true, true, true},
		{true, false, false, false, false, false, true},
		{true, false, true, true, true, false, true},
		{true, false, true, true, true, false, true},
		{true, false, true, true, true, false, true},
		{true, false, false, false, false, false, true},
		{true, true, true, true, true, true, true},
	}
)
	
func (q *QRCode) addFinderPatterns() {
	// top left
	q.add2dPattern(0, 0, finderPattern)

	// top right
	q.add2dPattern(q.size-finderPatternSize, 0, finderPattern)

	// bottom left
	q.add2dPattern(0, q.size-finderPatternSize, finderPattern)
}

func (q *QRCode) add2dPattern(x int, y int, pattern [][]bool) {
	for dy, row := range pattern {
		for dx, v := range row {
			q.add(x+dx, y+dy, v)
		}
	}
}

分離パターン

位置検出パターンのまわりは、必ず明モジュールで囲まれます。これを分離パターンと呼んでいます。位置検出パターンと符号化領域を区別するために設けられています。

コードでは以下のようになります。

var (
	separatorHorizontalPattern = [][]bool{
		{false, false, false, false, false, false, false, false},
	}
	separatorVerticalPattern = [][]bool{
		{false},
		{false},
		{false},
		{false},
		{false},
		{false},
		{false},
		{false},
	}
)

func (q *QRCode) addSeparatorPattern() {
	// top left vertical
	q.add2dPattern(finderPatternSize, 0, separatorVerticalPattern)
	// top left horizontal
	q.add2dPattern(0, finderPatternSize, separatorHorizontalPattern)

	// top right vertical
	q.add2dPattern(q.size-finderPatternSize-1, 0, separatorVerticalPattern)
	// top right horizontal
	q.add2dPattern(q.size-finderPatternSize-1, finderPatternSize, separatorHorizontalPattern)

	// bottom left vertical
	q.add2dPattern(finderPatternSize, q.size-finderPatternSize-1, separatorVerticalPattern)
	// bottom left horizontal
	q.add2dPattern(0, q.size-finderPatternSize-1, separatorHorizontalPattern)
}

タイミングパターン

水平方向は上から6行目、垂直方向は左から６列目で、各位置検出パターンの間は、暗と明の交互のパターンになります。これはタイミングパターンと呼ばれています。

コードでは以下のようになります。暗モジュールから始めて、暗・明・暗・明・・・と繰り返していきます。

func (q *QRCode) addTimingPatterns() {
	// timing pattern starts with true
	v := true

	// start of timing pattern: finder pattern size + separator size (1)
	for i := finderPatternSize + 1; i < q.size-finderPatternSize-1; i++ {
		// horizontal direction
		q.add(i, finderPatternSize-1, v)
		// vertical direction
		q.add(finderPatternSize-1, i, v)
		// next module is inverse boolean
		v = !v
	}
}

形式情報の符号化

QR コードの誤り訂正レベルとマスクパターン参照子（後述）を符号化したデータを形式情報と呼んでいます。この形式情報は15ビットからなり、最上位ビットが14、最下位ビットが0となるように、下図の 0 ~ 14 の位置に描画されます。つまり、形式情報は同じ情報が2個分描画されます。

まず、誤り訂正レベル2ビット、マスクパターン参照子3ビットを合わせて計5ビットが得られます。この5ビットを15ビットになるように BCH 符号化します。 これは符号理論の知識が必要となるので詳細は省略します。その後、101010000010010 と XOR 演算した結果が形式情報となります。

実際には、符号化前のデータが5ビットしかないので 2^5 通りのパターンを網羅することで符号化処理を書く必要はなくなります。JIS にも全てのケースを網羅した表が記載されているので今回はそれを利用しました。

例として、誤り訂正レベルが M とすると、誤り訂正レベル指定子は以下の表から 00 となります。

誤り訂正レベル	誤り訂正レベル指定子
L	01
M	00
Q	11
H	10

さらにマスクパターン参照子を 011 とすると、得られる5ビットの値は 00011 となります。これを BCH 符号化すると以下の値が得られます。

10110110 1001011

コードでは以下のようになります。

// maskedBitSequence means masking (5, 15, 7) BCH code
// reference: JIS X0510 : 2018 (ISO/IEC 18004 : 2015) Table C.1
var maskedBitSequence = []uint16{
	0x5412,
	0x5125,
	0x5E7C,
	0x5B4B,
	0x45F9,
	0x40CE,
	0x4F97,
	...
}

func (q *QRCode) addFormatInfo() {
	fi := FormatInfo(q.ecl, q.mask)
	q.addVerticalFormatInfo(fi)
	q.addHorizontalFormatInfo(fi)
}

func FormatInfo(ecl ErrorCorrectionLevel, mask uint8) *bitset.BitSet {
	formatBitSequence := (uint8(ecl) << 3) | mask

	fi := maskedBitSequence[formatBitSequence]

	// convert uint16 to bitset
	bs := bitset.NewBitSet(formatInfoLength)
	for i := formatInfoLength - 1; i >= 0; i-- {
		bs.SetBool((fi >> i & 1) == 1)
	}

	return bs
}

入力文字の符号化

上記を除いた箇所に、入力文字を符号化した情報を描画していきます。

下図は 1-M 型の QR コードの配置になります。D1 から D16 までは入力文字、E1 から E10 までは入力文字を符号化して得られた誤り訂正コードを描画します。

処理の流れは以下の通りです。

• 符号化のためのデータ構造準備
• モード指定子の追加
• 文字数指定子の追加
• 入力文字の追加
• 終端パターンの追加
• 埋め草コードの追加
• 上記で作成したデータを RS 符号化

符号化のためのデータ構造準備

符号化するにあたり、今回は符号化するデータを保持するスライス []bool をフィールドに持つ BitSet 型を定義しました。1ビットずつ値を設定したり、int 型の値をまとめて設定したりすることができるようにしています。

func NewBitSet(length int) *BitSet {
	return &BitSet{
		length: length,
		value:  make([]bool, length),
		pos:    0,
	}
}

func (bs *BitSet) SetInt(v int, length int) {
	bs.ensureCapacity(length)
	for i := 0; i < length; i++ {
		bs.value[bs.pos+i] = GetBit(v, length-1-i)
	}
	bs.pos += length
}

func (bs *BitSet) SetBool(v bool) {
	bs.ensureCapacity(1)
	bs.value[bs.pos] = v
	bs.pos++
}

ここで、 QR コードのデータコード語数 qrInfo.countDataCodeWords 分の大きさの BitSet 型構造体を用意します。今回は8ビットバイトモードのみ扱うので、1文字は8ビット固定となります。したがって、ビット配列の大きさは データコード語数 * 8 で得られます。

codeLength := info.countDataCodeWords * 8
bs := bitset.NewBitSet(codeLength)

モード指定子の追加

次に、モード指定子を追加します。モード指定子は長さ4ビット以下のように定義されています。

モード	モード指定子
数字モード	0001
英数字モード	0010
8ビットバイトモード	0100
漢字モード	1000

コードは以下のようになります。

addModeIndicator(bs, info.mode)

func addModeIndicator(bs *bitset.BitSet, mode ModeIndicator) {
	// modeCharCount = 4
	bs.SetInt(int(mode), modeCharCount)
}

今回は8ビットバイトモードのみ扱っているので、0100 を設定します。この時点でのデータは以下の通りになります。

0100

文字数指定子の追加

次に、文字数指定子を追加します。文字数指定子は入力文字数を、定義された文字数指定子のビット数で表現してデータに追加します。文字数指定子のビット数は以下のように定義されています。

型番	数字モード	英数字モード	8ビットバイトモード	漢字モード
1~9	10	9	8	8
10~26	12	11	16	10
27~40	14	13	16	12

コードは以下のようになります。

bitCount := characterCountIndicatorBits(info.version, info.mode)
charCount := utf8.RuneCountInString(info.src)
addCharacterCountIndicator(bs, bitCount, charCount)

func addCharacterCountIndicator(bs *bitset.BitSet, bitCount int, charCount int) {
	bs.SetInt(charCount, bitCount)
}

今回は、型番は1型で、8ビットバイトモードのみ扱うので、文字数指定子のビット数は8となります。ここで Hello, World! を入力とすると、13文字となります。13を8ビットで表現すると 0000 1101 となりますので、この時点でのデータは以下のようになります。

01000000 1101

入力文字の追加

続いて入力文字を追加していきます。8ビットバイトモードの場合は、入力文字のバイト値をそのまま設定すればいいので、以下のように簡単に値を追加できます。

func addSrcData(bs *bitset.BitSet, src string) {
	// supports only 8 bit byte mode
	for _, c := range src {
		bs.SetByte(byte(c))
	}
}

入力を Hello, World とすると、この時点でのデータは以下のようになります。

01000000 11010100 10000110 01010110 11000110 11000110 11110010 11000010
00000101 01110110 11110111 00100110 11000110 01000010 0001

終端パターンの追加

終端パターン 0000 を末尾に追加します。ただし、データコード語数の容量を満たす場合は、終端パターンは短縮します。

func addTerminator(bs *bitset.BitSet) {
	if bs.Position() == bs.Length() {
		return
	}

	if bs.Position() <= bs.Length()-4 {
		bs.SetInt(0, 4)
		return
	}

	nextPos := bs.Position()
	for i := nextPos; i < bs.Length(); i++ {
		bs.SetBool(false)
	}
}

今回は、まだデータコード語数を満たしていないので、 0000 を追加します。

01000000 11010100 10000110 01010110 11000110 11000110 11110010 11000010
00000101 01110110 11110111 00100110 11000110 01000010 00010000

埋め草コードの追加

この時点でコード語の境界（今回は8ビットの区切り）に達していない場合は、境界に達するまで0を追加します。今回はちょうど境界に達しているので、0の追加はしません。その後、データ容量を満たすまで 11101100 および 00010001 を交互に追加します。今回はエラー訂正レベルを M とすると、残り8ビットで容量を満たすので 11101100 のみ追加します。

01000000 11010100 10000110 01010110 11000110 11000110 11110010 11000010
00000101 01110110 11110111 00100110 11000110 01000010 00010000 11101100

上記で作成したデータを RS 符号化

ここまでで符号化前のデータが準備できました。RS 符号化すると、以下のデータが得られます。これが QR コードのデータ符号化領域に描画するデータになります。

01000000 11010100 10000110 01010110 11000110 11000110 11110010 11000010
00000101 01110110 11110111 00100110 11000110 01000010 00010000 11101100
11010111 01011100 11110111 00110111 10011011 10011000 00111011 11110110
01010111 01111100

ちなみに、RS 符号化も符号理論の知識が必要になり、複雑となるので、ここでは省略します。
これで入力文字の符号化が完了しました。

マスク処理

データの準備ができたので、マスク処理を施します。この目的は、暗モジュールや明モジュールに偏りができてしまったり、位置検出パターンと同じパターンができてしまったりしないようにするためです。今回はデータ計算量を減らすために、 modules フィールドにデータを追加するときにマスク処理を施すことにしました。

マスクパターンは以下の表のとおりになります。 $i$, $j$ はそれぞれ行番号、列番号になります。

マスクパターン参照子	条件
000	$(i+j) \bmod 2 = 0$
001	$i \bmod 2 = 0$
010	$j \bmod 3 = 0$
011	$(i + j) \bmod 3 = 0$
100	$(i / 2 + j / 3) \bmod 2 = 0$
101	$(i * j) \bmod 2 + (i * j) \bmod 3 = 0$
110	$((i * j) \bmod 2 + (i * j) \bmod 3) \bmod 2 = 0$
111	$((i + j) \bmod 2 + (i * j) \bmod 3) \bmod 2 = 0$

例えば、マスクパターン参照子 000 の場合、以下のようなパターンになります。位置検出パターンや形式情報などの領域にはマスク処理しないので、黒色の部分がマスク処理される箇所になります。

マスク処理した後のデータの追加方法が少し癖のある方法になります。

まず、QR コードの右下からスタートして、矢印の方向に向かってデータを入れていきます。次に折り返していくと向きが変わって、データを配置位置が変わります。この向きによってデータを配置する位置が異なってくるので注意が必要です。

コードで見ると以下のようになります。ここでは座標を移動しながらマスク処理した値を代入していきます。形式情報や位置検出パターンなどのように、ここまでに既に値を代入してある座標は dirties が true になっています。そのため、まだ既に値が代入されていない座標のみ考慮して、マスク処理しています。

func (q *QRCode) addData() {
	// when dx is  0, position is right
	// when dx is -1, position is left
	dx := 0

	// start from bottom right
	x := q.size - 1
	y := q.size - 1

	// direction
	direction := up

	for i := 0; i < q.data.Length(); i++ {
		mask := calculateMask(x+dx, y, q.mask)
		// != is equivalent to XOR.
		q.add(x+dx, y, mask != q.data.GetValue(i))

		if i == q.data.Length()-1 {
			break
		}

		for {
			// 次の描画位置を計算
			...

			// 形式情報などは isDirty=true となる
			if !q.isDirty(x+dx, y) {
				// break if next position is not dirty
				break
			}
			// if next position is dirty, tries to find next not dirty position
		}
	}
}

func (q *QRCode) isDirty(x, y int) bool {
	return q.dirties[y+quietZoneSize][x+quietZoneSize]
}

マスク評価

マスク処理が終わったら、マスクが妥当かどうかを評価する必要があります。以下の4項目を評価して、失点の和を計算して最も失点が小さいマスクを採用します。

正直なところ、かなり分かりにくいと思うので、ここはあまり理解しようとしなくても大丈夫です。偏りがあったり、位置検出パターンに近いパターンがあると失点が増えるんだな、くらいの理解があれば十分です。

• 同色の行または同色の列の隣接モジュール
  • 5個連続するブロック1個につき、3点の失点とする。6個連続する場合は4点、7個連続する場合は5点、というように (5+i)個の連続するブロックがある場合、(3+i)点の失点とする。
• 同色のモジュールブロック
  • 2 x 2 の同色ブロックの個数 * 3点の失点とする。例えば 3 x 3 の同色ブロックがあった場合は、2 x 2 の同色ブロックが4個とみなし、3 * 4 = 12点の失点とする。
• 1:1:3:1:1 の比率の「暗:明:暗:明:暗」のパターン
  • 1:1:3:1:1 の比率の「暗:明:暗:明:暗」パターンに続いて比率4の幅以上の明パターンが存在する場合、40点の失点とする
• 全体に対する暗モジュールの占める割合
  • 全体に対する暗モジュールの占める割合が50%から5%増減するたびに10点の失点とする。暗モジュールの比率を $x$ とすると、 $45 \% \leq x \leq 55 \%$ であれば0点、 $40 \% \leq x \lt 45 \%$ または $55 \% \lt x \leq 60 \%$ の場合は10点の失点となる。

例として、2つ目の失点計算のコードを以下に示します。ある座標 (x, y) を起点として左、上、左上の3点のモジュールの色を取得して、 2 x 2 のブロックが同色であれば個数をインクリメントして次の座標へと移動していきます。最後に 2 x 2 の同色ブロックの個数 * 3 を計算して失点としています。
このように他の失点も計算して、それぞれの和が最も小さいマスクを採用します。

func (q *QRCode) penalty2() int {
	count := 0
	penaltyWeight2 := 3

	for y := 1; y < q.size; y++ {
		for x := 1; x < q.size; x++ {
			topLeft := q.get(x-1, y-1)
			above := q.get(x, y-1)
			left := q.get(x-1, y)
			current := q.get(x, y)

			if current == left && current == above && current == topLeft {
				count++
			}
		}
	}
	return count * penaltyWeight2
}

画像化

ここまででデータ作成が完了したので、あとは値に応じて画像を出力するだけになります。今回は画像化は本質的ではないので省略します。

まとめ

QR コードをエンコードする流れは以上になります。 文字数が多くなったり、他の文字種も考慮する場合などはさらに処理は複雑となってきます。詳細が気になった方は JIS や ISO などをみてみるといいかもしれません。

また、 BCH 符号や RS 符号の詳細が気になった方には、『例題で学ぶ符号理論入門』がオススメです。最低限必要な数学だけを学んで、これらの符号化を勉強することができます。

参考

• https://github.com/skip2/go-qrcode
  • 既存の QR コード実装。ガロア拡大体上の多項式はかなり参考になりました
  • https://www.jisc.go.jp/app/jis/general/GnrJISNumberNameSearchList?toGnrJISStandardDetailList (only view)
• ＱＲコードをつくってみる
• 例題で学ぶ符号理論入門
  • 符号理論に必要な最低限の数学も学ぶことができるので入門にオススメ
• 例題が語る符号理論 BCH符号・RS符号・QRコード
  • 最後の方に記述のある QR コードの解説は JIS よりも分かりやすい