QRコードは今や至るところにあり、携帯電話には必ずと言っていいほどQRコードを読み取る機能がついています。QRコードは、皆さんにとって身近な存在でしょう。

※QRコードは株式会社デンソーウェーブの登録商標です

Web上でも、携帯サイトへアクセスしやすいように、携帯サイトのURLなどの情報を埋め込んだQRコードをWebページに貼り付けているサイトをよく見かけます。こうしたQRコードを作成するには、QRコード作成用のエンコーダを使います。エンコード用のライブラリは豊富にあり、Flash用のライブラリもあります。ところが、逆にFlashでQRコードを読み取るためのライブラリはなく、FlashでQRコードを読み取ることは不可能でした。

先日、ある制作案件でFlashからQRコードを読み取る方法を採用する可能性があったため、オリジナルのFlash用QRコード読み取り機能「QR Code Reader」を実装しました。そして、私が所属するロゴスウェア株式会社ではオープンソース活動を行っており、その一環としてQR Code ReaderのソースコードをSpark Projectで公開することにしました。その経緯については、弊社ラボサイトも参照してください。

QR Code Readerは、主に2つのクラスに分かれています。

1. 画像ソースを解析してQRコードのビット列を生成するクラス
2. QRコードのビット列から文字列にデコードするクラス

本記事では、1を使った処理にについて紹介します。2も面白いトピックですが、数学的な側面が強くなるので詳細については割愛します。

QRコードの特徴

QRコードの画像解析を行うには、まず、Webカメラ映像内からQRコード部分だけを抽出しなければなりません。以下に、抽出上必要となるQRコードの特徴を挙げておきます。

【モジュール】

QRコード上にある黒や白の最小単位（点一個）を「1モジュール」と呼びます。

【バージョン】

QRコードの情報量のサイズ（縦横にいくつのモジュールが並んでいるか）を「バージョン」と呼びます。一番小さいものがバージョン1で、縦横のモジュールが４個増えるごとにバージョンの数字が上がり、バージョン40まであります。

【切り出しシンボル】

QRコードを見たとき真っ先に目に付くのがこの「切り出しシンボル」でしょう。これはQRコードの右下を除く３隅に存在し、これによってQRコードの位置、向き、大きさが分かります。切り出しシンボルの周りは、必ず白いモジュールで囲まれています。

また、シンボルの中央を通る線に沿って黒と白の長さの比を見ると、次の画像のようにどの方向の線上でも必ず「1：1：3：1：1」の割合になるという特徴があり、これを手がかりに切り出しシンボルを抽出することができます。

【タイミングパターン】

QRコードの左上を原点として数えると、7列目と7行目にそれぞれ「タイミングパターン」が配置されています。これはシンボル同士の間にあり、白と黒のモジュールが交互に並んでいます。タイミングパターン内のモジュールの数を数えることによって、QRコードのバージョンを判別できます。

【位置合わせパターン】

バージョンが上がるごとにQRコードの大きさが増し、カメラで捕らえたときの歪みも大きくなっていきます。これを補正するために配置してあるのが「位置合わせパターン」です。

QRコード抽出手順

以上の特徴を踏まえて、Webカメラ映像からQRコードを抽出する手順は以下のようになります。

• STEP１ カメラから画像を読み込む。
  →画像ソースを取り込む
• STEP２ 切り出しシンボルを探すため、画像を白か黒かの２色にする。
  →グレー化、二値化
• STEP３ 切り出しシンボルを探すため、連続した黒色の画素をグループ分けする。
  →ラベリング
• STEP４ 「1：1：3：1：1」の比率を探して切り出しシンボルを探す。
  →切り出しシンボル検出
• STEP５ QRコードの位置が分かったところで、背景と分離する。
  →回転・移動
• STEP６ QRコードのバージョンを調べる。
  →タイミングパターン検出
• STEP７ QRコードのゆがみを補正するために位置合わせパターンを探す。
  →位置あわせパターン検出
• STEP８ ゆがみを考慮して各モジュールを抽出する。
  →読み込みグリッド作成

それでは、各項目について説明していきましょう。

STEP1　画像ソースの取り込み

解析対象の画像は、Webカメラあるいは静止画像などから取り込むことになります。Webカメラの場合はCameraをアタッチしたVideoクラス、静止画像の場合はLoaderクラスをそれぞれBitmapDataに書き込むことによって編集が行えるようになります。

もう少し詳しく説明すると、両クラスともIBitmapDrawableインターフェイスを実装したDisplayObjectクラスを継承しているため、drawメソッドを用いてBitmapDataに描画することが可能になっています。

320x320の正方形画像をWebカメラから取り込むコード例：

var camera:Camera = Camera.getCamera();
var video:Video = new Video(320, 320);
var bitmapData:BitmapData = new BitmapData(320, 320, true);

if (camera != null) {
	camera.setQuality(0, 100);
	camera.setMode(320, 320, 24, true);
	video.attachCamera(camera);
	addEventlistener(Event.ENTER_FRAME, onEnterFrame); // 毎フレーム更新
} else {
	textArea.text = "no camera detected";
}
// コールバック関数
function onEnterFrame(e:Event):void{
	bitmapData.draw(video);
	// ここでカメラ映像をBitmapDataとして処理できる
}

Webカメラから取得した生の画像

STEP2-1　グレー化（明るさ抽出）

Webカメラから画像を取得したら、次は画像を白黒２色にして切り出しシンボルを探します。しかし、カラー画像をそのまま二値化するのは、RGBの各色をどのように考慮すればよいのか分かりません。そこでまずは、画像を明るさに応じてグレー化します。

BitmapDataをグレー化するには、ColorMatrixFilterフィルタとapplyFilterメソッドを使います。ColorMatrixFilterは、画像中の各画素を(赤, 緑, 青, アルファ, 1)のベクトルとみなし、それに5x4行列を作用させて(赤, 緑, 青, アルファ)のベクトルを得て画素に戻す働きをするBitmapFilterを継承したクラスです。applyFilterはBitmapDataにBitmapFilterを適用するメソッドです。

ColorMatrixFilterフィルタとapplyFilterメソッドのコード例：

// bmp_src:BitmapData 適用元画像
// bmp_dst:BitmapData 適用先画像
// cValue:Number 明度補正用
var gray:Array = [cValue*0.3, cValue*0.59, cValue*0.11];
var cmf:ColorMatrixFilter = new ColorMatrixFilter([
	gray[0], gray[1], gray[2], 0, 0,
	gray[0], gray[1], gray[2], 0, 0,
	gray[0], gray[1], gray[2], 0, 0,
	0, 0, 0, 0, 255
]);
bmp_dst.applyFilter(bmp_src, bmp_src.rect, new Point(0, 0), cmf);

cValueは通常のグレー化では「1.0」ですが、これを変えることによって全体の明度を一度の計算で補正することができます。Webカメラだと暗く映りがちなので、私の経験的に「1.125」程度の値をcValueに渡しています。「0.3」「0.59」「0.11」というマジックナンバーは、NTSC系加重平均法という方法に由来するものです。3つの数字がRGB各色に対する明るさの重み付けの値となっています。この操作の結果、画素中の赤、緑、青の値はすべて等しくなります。

Webカメラから取得した画像（左）、グレー化した画像（右）

STEP2-2　二値化

グレー画像はRGBの値が揃っているので、閾値が一つあれば簡単に二値化できます。BitmapDataを二値化するには、thresholdメソッドを使います。thresholdは、BitmapDataの各画素について閾値との比較（大小判定など）を行い、結果に応じて指定色で置き換えるメソッドです。

二値化するコード例：

// bmp_src:BitmapData 適用元画像
// bmp_dst:BitmapData 適用先画像
// threshold:uint 閾値
bmp_dst.threshold(bmp_src, bmp_src.rect, new Point(0, 0), "<", threshold, 0xFF000000, 0xFFFFFFFF );
bmp_dst.threshold(bmp_src, bmp_src.rect, new Point(0, 0), ">=", threshold, 0xFFFFFFFF, 0xFFFFFFFF );

この操作の結果、BitmapDataの画素はthresholdの値を閾値として黒(0xFF000000)または白(0xFFFFFFFF)に塗りつぶされ、どちらか2つの値しか持たなくなります。

二値化の結果、白と黒だけになった画像

STEP3　ラベリング

二値化によって情報量はかなり削減できましたが、全体をやみくもにスキャンするにはまだ早すぎます。ここで切り出しシンボルの形を思い出すと、「周りが白い、一繋がりの黒い四角」という特徴を持っていました。このような画像を処理するには、「ラベリング」という手法が有用です。これは画像中で隣り合った同じ色の画素を一塊とみなしてグループ分けする処理です。

ラベリングを行うには、該当する色を素早く探す必要があります。そのためには、BitmapDataのgetColorBoundRectメソッドが有用です。これはBitmapData中の指定色が存在する矩形領域、または存在しない矩形領域のどちらかを選択して取得できるメソッドです。

今回は上記メソッドを用いてラベリングを行い、その結果を保持するクラス LabelingClass を作成しました。ソースコードはSpark project内にあります。

LabelingClassを使ったコード例：

// bmp:BitmapData 処理するBitmapData
var LabelingObj:LabelingClass = new LabelingClass(); 
LabelingObj.Labeling( bmp, 10, 0xFF88FFFE, true ); // ラベリング実行。引数は処理対象、保持する矩形の幅/高さの最小値、 塗り開始色、元画像を実際に塗るかどうかの4つ。
var pickedRects:Array = LabelingObj.getRects(); // 該当した矩形の配列
var pickedColor:Array = LabelingObj.getColors(); // 矩形に塗った色の配列

この操作の結果、画像中にある黒領域がグループ分けされ、処理しやすくなります。

ラベリングの結果、まとまった黒色がグループ分けされ、それが上から下に向けて薄い青～薄い緑で塗り分けられた画像となります

STEP4　ドット走査して切り出しシンボル検出

次に、切り出しシンボルでは黒白黒白黒が「1：1：3：1：1」の比率で並んで現れるという特徴を利用し、切り出しシンボルを抽出します。具体的には、ラベリングして抽出された各矩形の中央を通るラインの端から1画素ずつ色を取得し、連続した黒と白の長さを配列に格納します。その結果、たとえば、[4,4,12,4,4]といった配列ができあがるので、その割合が「1：1：3：1：1」に近いかどうかを判定します。これにはgetPixelメソッドを使います。getPixelは、BitmapDataの指定した画素のRGB値を取得するメソッドです。

横方向走査のコード例：

// rect:Rectangle ラベリング結果の矩形
var countArray:Array = [0, 0, 0, 0, 0];
var index:int = -1;
var oldFlg:Boolean = false;
for ( j = 0; j < rect.width; j++ ){
	var tempFlg:Boolean = (bmp.getPixel( rect.topLeft.x + j, constNum ) == 0xFFFFFF)?false:true;
	if( (index == -1) && (!tempFlg) ){
		// 最初の黒の前に白が紛れ込んでいたら無視する
	} else {
		if( tempFlg != oldFlg ){
			index++;
			oldFlg = tempFlg;
			if( index >= 5 ){ // 黒白黒白黒と検出したら終了する
				break;
			}
		} 
		countArray[index]++;
	}
}
// 「1：1：3：1：1」の関係にあるかどうか判定
target = 0.25 * (countArray[0] + countArray[1] + countArray[3] + countArray[4]);if ( ( countArray[2] > (target*2.5) ) && ( countArray[2] < (target*3.5) ) ) {
	// このrectは切り出しシンボル！
}

最後の判定は、かなり計算量の少ない、手を抜いた式になっていますが、同じ領域について縦横と２度判定するため、結構いい精度で切り出しシンボルを認識できます。このステップですべての矩形をチェックして、シンボルが３つ見つかった時のみ次のステップへ進みます。なお、getPixelメソッドは、後述するタイミングパターンの検出にも使います。

シンボルを抽出した画像。赤で囲まれているのが検出された切り出しシンボル。青と緑の線にそって「1：1：3：1：1」のパターンを確認します

STEP5　回転と移動

次に紹介するのは、傾いた画像を回転・移動させる手法です。コンピュータにとっては、回転や移動によって情報量は変わらないので、その後の解析に影響はありません。しかし、人間が目で見てチェックする時に多少見やすくなるのでデバッグしやすくなります。また、QRコードの存在する範囲を正方形に近い形で再配置できるので、簡単に背景から切り抜くことができます。

回転・移動などの制御はMath.atan2、Matrixクラスとそのメソッドtranslateやrotateなどを使って行い、Bitmapdata.drawメソッドで書き込みます。今回やりたいことは、次のようなステップとなります。

1. 現在の傾きを取得
2. 回転の中心を決定
3. 傾きを打ち消すように逆回転
4. 適切な位置へ再配置

これをコードで書くと次のようになります。

回転・移動などの制御するコード例：

// bmp_src:BitmapData 元の画像
// bmp_dst:BitmapData 変形後の画像
// xVector:Point 傾いたx方向ベクトル
// matrix:Matrix 変形操作の内容を保持する行列
// center:Point 任意に選んだ回転の中心
// dst:Point 回転後の中心を配置する座標

// １ 傾いたx方向ベクトルのx, y成分を使って次のように取得できます。
var theta:Number = Math.atan2( xVector.y, xVector.x ); // 平面上の回転角

// ２ 任意の点を選び、回転中心とするためにを原点に移動します
matrix.translate( -center.x, -center.y );

// ３ 原点中心に回転します。
matrix.rotate( -theta );

// ４ 回転中心を配置したい任意の座標に移動します。
matrix.translate( dst.x, dst.y );

bmp_dst.draw( bmp_src, matrix );

変形後の画像は、移動先や回転角によって元画像と異なるサイズになります。その点に注意して、bmp_dstのサイズを決定してください。この処理の結果、適切な範囲に正方形に近い形で画像がおさまり、見やすくなります。

回転・再配置し、背景を取り除いて切り出した画像

NOTE:WebカメラがQRコードに対して垂直に向いていないと、上辺が真っ直ぐでも左辺が斜めになるなどの歪みが残ります。この点を回避するために画面に読み込みガイド枠を表示することで、ユーザーがカメラを垂直に向けやすくするなどの工夫を行います。

STEP6　タイミングパターン検出

次に、QRコードのタイミングパターンを検出します。処理としては、左上にある切り出しシンボルの右下の座標から横と縦に引いたライン上で、切り出しシンボル検出のとき同様にgetPixelメソッドを使いながら走査します。このラインは実際のタイミングパターンが存在する位置より多少ずれていることが考えられるので、少しずらしながら何度か走査します。

タイミングパターン検出ラインを図示したところ。画像中の赤い線、青い線に沿って、各5回の走査を行っています

STEP7　位置合わせパターン検出

本来QRコードには方眼紙のようにモジュールが正確に配置され、全体で正方形になっています。しかし、Webカメラを通すと、どうしても歪んでしまうので、どのくらい歪んでいるのかを検出する必要があります。ある程度大きいバージョンのQRコードでは歪み検出／訂正用に位置合わせパターンが配置されています。

右下の位置合わせパターンの位置は固定で、左下の切り出しシンボルの上辺を右側に延長した直線と、右上の切り出しシンボルの左辺を下側に延長した直線との交点上にその中央があります。これを利用して座標の検討をつけ、1ドットずつ斜めに走査して位置合わせパターンの白い画素を探します。白い画素が見つかったら、floodFillメソッドを使ってユニークな色に塗り、getBoundsRectメソッドを使って矩形を取得します。

右下の位置合わせパターンを検出するコード例：

// thisColor:int 抽出した色を保持
// i:int 走査用にインクリメントする値
// bmpData:BitmapData QRコード画像
// target:Point 目星をつけた座標
while ( thisColor != 0xFFFFFF ) {
	i++;
	thisColor = bmpData.getPixel( target.x + i, target.y + i );
}
bmpData.floodFill( target.x + i, target.y + i, 0xFFCCFFFF );
var patternRect:Rectangle = bmpData.getColorBoundsRect( 0xFFFFFFFF, 0xFFCCFFFF )

こうして得られた矩形領域の中心を現在の位置検出パターンの中心とみなします。

位置合わせパターンを抽出した画像。画像中の青い枠が位置合わせパターンの白領域の境界線。赤いドットが「見当を付けた」検出パターンが存在しそうな位置。全体にかかっている薄い赤線は次項で説明するグリッド

STEP8　読み込みグリッド作成

位置合わせパターンを使って、正方形からの歪みがどの程度かわかったので、これを補正しつつ各モジュールを読み込みます。この方法として、正確なグリッドを用意して画像に重ね、それを画像の歪みに合わせて変形させます。変形後のグリッド交点の下にある画像の色を取っていくことで元のQRコードのパターンを復元できます。

今回の実装では歪みが小さいものとして、最も単純な補間を行いました。つまり傾きによる遠近法を無視して、単純に縦横ｎマスのものをｎ個に均等に分割する方法です。これを実現するコードは次のようなものになります。

読み込みグリッド作成のコード例：

// point1:Point 左上の点の座標
// point2:Point 左下の点の座標
// vector1:Point 左上の点から右上の点を指すベクトル
// vector2:Point 左下の点から右下の点を指すベクトル

var vector3:Point = vector2.subtract(vector1);
// 横n,縦nのグリッドで左からi,上からj個目の位置を補正した座標を取得
function getPoint(i:int, j:int):Point{
	var tempPoint:Point = point2.subtract(point1);
	tempPoint.x += vector3.x * i / n;
	tempPoint.y += vector3.y * i / n;
	return new Point( point1.x + vector1.x * i / n + tempPoint.x * j / n, point1.y + vector1.y * i / n + tempPoint.y * j / n);
}

こうして補正したグリッド上でgetPixelメソッドを行うことで、QRコードのビット配列を得ることができます。あとはデコーダの仕事になり、ここまでの読み取り精度次第で文字列が取得できます。

グリッド化の画素からビット配列を作成し、そこから再生成したQRコード画像

デコードについて

ここまででQRコードのビット配列が完成しましたので、その後はその配列をデコードクラスQRdecodeに渡してやれば文字列が得られます。

デコードのコード例：

// e:QRreaderEvent カスタムイベント
var qrDecode:QRdecode = new QRdecode();
qrDecode.setQR(e.data); // QRreaderEvent.data: QRコードを表す2次元ビット配列
qrDecode.startDecode(); // デコード開始。

デコードが完了するとQRdecoderEvent.QR_DECODE_COMPLETEイベントが送出され、QRdecodeEvent.dataに結果文字列が格納されます。詳しくは、サンプルのコードを見て下さい。

まとめ

次の手段を全て使って、QRコードを画像から抽出しました。

• グレー化
• 二値化
• ラベリング
• 走査
• 回転／移動
• 歪み補正

今回はWebカメラから読み込んだ画像のため、明るさや歪みを補正する必要がありました。どのような方法で何を解析するかにより手段は変わってきますが、上記のような手段を探し出して、工夫を加えて適用すれば大抵のことはできると思います。

改良点

処理内容が多いだけに、QRコードを読み込むためにさらに改良できる点は無数にあります。たとえば、

• グレー化＆二値化の精度向上（部分的に閾値を変えるなど）
• 速度のボトルネックになっているラベリング手法の改善または代替手段
• 走査の効率化
• 回転走査の除去
• パースを考慮した歪み補正

これらは改良が済み次第、Spark Project上のコードを更新していく予定です。

QRコード読み込み機能について今後の発展

PC+Flash+Webカメラと、すでにある素材で非常に安価にQRコードを読み込めるようになり、いろいろな可能性が広がったと思います。たとえば、

• これまで面倒だったQRコード付名刺→PCの情報入力を改善
• QRコードをかざすだけで勤怠管理
• PSPや携帯から情報をQRコード経由でPCに送る

みなさんも、いろいろと試してみてください。

サンプル＆リソース

QR Code Readerのクラスやサンプルコードなどは、Spark Projectからダウンロードすることが可能です。
また、実際に動作するプログラムは、弊社ラボサイトに設置してあります。

※次のような場合はうまく読み込めないことがあります。
・QRコードが曲面上に印刷されている。
・部屋の照明などでQRコードの一部だけが明るく光っている。
・QRコードが小さく、Webカメラが接写に対応していない。

参考サイト

二次元コードシンボル－QRコード－基本仕様：JISC 日本工業標準調査会
http://www.jisc.go.jp/

ラベリング機能の開発：void element blog/munegon
http://void.heteml.jp/blog/archives/2007/10/as3_labeling.html

著者について