(57)【要約】【課題】機械読み取り可能な二次元符号の位置確認および復号化の方法および装置。【解決手段】デジタル画像内の二次元の機械読み取り可能な符号の位置を確認に復号化する方法で、符号は符号の各々の角に隣接する３つのファインダ・パターンを有し、方法はデジタル画像内で符号の輪郭を描く際にスキュー・縦揺れの可能性を考慮に入れ符号の既知のエッジ点を通る線に基づき未知の第４の角を推定する。輪郭を描くことに基づき、基準グリッドがデジタル画像にマッピングされ、マッピングに基づきビット・ストリームが抽出される。【選択図】図７
2007265407.tif 000002
【特許請求の範囲】
【請求項１】
画像内の機械読み取り可能な符号からビット・ストリームを抽出する方法で、符号は符
号の各々の角に隣接し、直角三角形の角を定義する３つのファインダ・パターンを含み、
前記方法は、
符号のファインダ・パターンを特定するステップと、
ファインダ・パターンを用いて符号を配向させるステップで、
前記配向ステップは、３つのファインダ・パターンの内どれが三角形の斜辺に対向して
位置するか（「左上のファインダ・パターン」）を判定するステップと、残りの２つのフ
ァインダ・パターンの内１つを左上のファインダ・パターンを軸に１８０度未満回転させ
た場合にもたらされる残りの２つのファインダ・パターンの相対的距離に基づき残りの２
つのファインダ・パターンのラベル付けをするステップとを含むものであり、
前記配向に基づき、符号の輪郭を描くステップと、
前記輪郭が描かれた符号に復号化グリッドをマッピングするステップと、
マッピングされた符号からビット値を抽出するステップとを含む方法。
【請求項２】
前記ラベル付けステップは、
最初に残り２つのファインダ・パターンを各々右上および左下のファインダ・パターン
とラベル付けするステップと、
右上および左下のファインダ・パターンの内選ばれたものを左上のファインダ・パター
ンを軸に回転させるステップと、
回転後、右上および左下のファインダ・パターンの回転前および後の相対的距離を比較
して最初のラベル付けを確認するステップと
を含む、請求項１に記載される方法。
【請求項３】
前記ラベル付けの際、前記右上のファインダ・パターンは前記左上のファインダ・パタ
ーンを軸に左回りに回転させられ、前記右上のファインダ・パターンが前記左下のファイ
ンダ・パターンから遠くなったかその位置を調べ、前記右上のファインダ・パターンが前
記左下のファインダ・パターンから遠くなった場合、残り２つのファインダ・パターンは
正しくラベル付けされたとみなされる、請求項２に記載される方法。
【請求項４】
ラベル付けの際、前記左下のファインダ・パターンは前記左上のファインダ・パターン
を軸に左回りに回転させられ、前記左下のファインダ・パターンが前記右上のファインダ
・パターンに近くなったかその位置を調べ、前記左下のファインダ・パターンが右上のフ
ァインダ・パターンに近くなった場合、残り２つのファインダ・パターンは正しくラベル
付けされたとみなされる、請求項２に記載される方法。
【請求項５】
前記ラベル付けの際、前記左下のファインダ・パターンは前記左上のファインダ・パタ
ーンを軸に右回りに回転させられ、前記左下のファインダ・パターンが前記右上のファイ
ンダ・パターンから遠くなったかその位置を調べ、前記左下のファインダ・パターンが前
記右上のファインダ・パターンから遠くなった場合、残り２つのファインダ・パターンは
正しくラベル付けされたとみなされる、請求項２に記載される方法。
【請求項６】
前記ラベル付けの際、前記右上のファインダ・パターンは前記左上のファインダ・パタ
ーンを軸に右回りに回転させられ、前記右上のファインダ・パターンが前記左下のファイ
ンダ・パターンに近くなったかその位置を調べ、前記右上のファインダ・パターンが前記
左下のファインダ・パターンに近くなった場合、残り２つのファインダ・パターンは正し
くラベル付けされたとみなされる、請求項２に記載される方法。
【請求項７】
さらに比較により最初のラベル付けが確認されない場合にラベル付けを逆にするステッ
プを含む、請求項２に記載される方法。
【請求項８】
前記判定ステップは、
各ファインダ・パターンの対応点の間に延びる複数の線分を確立するステップと、白の
ピクセル上のみに延びる線分を有する対応点に共通するファインダ・パターンとして前記
左上のファインダ・パターンを特定するステップとを含む、請求項１に記載される方法。
【請求項９】
画像が黒または白のトークンにトークン化され、１つの白トークンのみを通る２つの線
分に共通するファインダ・パターンが左上のファインダ・パターンとして特定される、請
求項８に記載される方法。
【請求項１０】
前記点はファインダ・パターンのエッジの中点である、請求項８に記載される方法。
【請求項１１】
前記判定ステップは、
３つのファインダ・パターン各々の中点間に延びる線分の各々の長さを計算するステッ
プと、
二乗された長さの合計が３つ目の線分の長さの二乗に等しくなる２つの線分に共通する
ファインダ・パターンとして前記左上のファインダ・パターンを特定するステップと
を含む、請求項１に記載される方法。
【請求項１２】
前記輪郭を描くステップが、
左上、左下、および右上のファインダ・パターンに基づき、符号の左上、左下、および
右上の角を判定するステップと、
右上および左下のファインダ・パターンに基づきスキュー・縦揺れに感応する技法を用
いて符号の右下の角を判定するステップと、
を含む、請求項２に記載される方法。
【請求項１３】
前記スキュー・縦揺れに感応する技法は、
前記左下のファインダ・パターンで前記左上のファインダ・パターンに向かい合った内
側エッジと一直線上にある第１の内側エッジ線を判定するステップと、
前記右上のファインダ・パターンで前記左上のファインダ・パターンに向かい合った内
側エッジと一直線上にある第２の内側エッジ線を判定するステップと、
前記左下のファインダ・パターンで内側エッジに向かい合った外側エッジの第１の中点
を判定するステップと、
前記右上のファインダ・パターンで内側エッジに向かい合った外側エッジの第２の中点
を判定するステップと、
第１の内側エッジ線に沿って符号の外側エッジと一致する第１の外側エッジ点を判定す
るステップと、
第２の内側エッジ線に沿って符号の外側エッジと一致する第２の外側エッジ点を判定す
るステップと、
第１の中点と第２の外側エッジ点を通る第１の外側エッジ線を判定するステップと、
第２の中点と第１の外側エッジ点を通る第２の外側エッジ線を判定するステップと、
第１の外側エッジ線と第２の外側エッジ線との交点を右下の角とするステップと
を含む、請求項１２に記載される方法。
【請求項１４】
第１の外側エッジ点の判定は、
第１の内側エッジ線に沿って、第１の内側エッジ線と第２の内側エッジ線との交点およ
び符号の外にある任意を点の間にテスト・ポイントの第１の組を定義するステップと、
交点に最も近いテスト・ポイントから始め、第２の中点からテスト・ポイントに延びる
線分を定義するステップと、
線分が白ピクセルのみを通るか確認するステップと、
線分が白ピクセルのみを通る場合、テスト・ポイントを第１の外側エッジ点とみなし、
それ以外の場合は次のテスト・ポイントを選んで線分の定義と確認を繰り返すステップ
を含む、請求項１３に記載される方法。
【請求項１５】
第２の外側エッジ点の判定は、
第２の内側エッジ線に沿って、第１の内側エッジ線と第２の内側エッジ線との交点およ
び符号の外にある任意を点の間にテスト・ポイントの第２の組を定義するステップと、
交点に最も近いテスト・ポイントから始め、第１の中点からテスト・ポイントに延びる
線分を定義するステップと、
線分が白ピクセルのみを通るか確認するステップと、
線分が白ピクセルのみを通る場合、テスト・ポイントを第２の外側エッジ点とみなし、そ
れ以外の場合は次のテスト・ポイントを選んで線分の定義と確認を繰り返すステップ
を含む、請求項１４に記載される方法。
【請求項１６】
前記スキュー・縦揺れに感応する技法は、
前記符号の右下の角に隣接して該符号の下側および右側エッジ点を判定するステップと
、
左下のファインダ・パターンから延び符号の下側エッジ点を通る線と右上のファインダ
・パターンから延び符号の右側エッジ点を通る線との交点を判定し、それにより符号の右
下の角を判定するステップ
を含む、請求項１２に記載される方法。
【請求項１７】
二次元の機械読み取り可能な符号はＱＲコード符号である、請求項１に記載される方法
。
【請求項１８】
請求項１に記載される方法を実施するためにコンピュータで実行可能なコンピュータ・
プログラムを具現するコンピュータ読み取り可能な媒体。
【請求項１９】
画像内の機械読み取り可能な符号の配向を判定する方法で、符号は符号の各々の角に隣
接し、直角三角形の角を定義する３つのファインダ・パターンを含み、前記方法は、
三角形の斜辺に対向する角に位置するファインダ・パターンを特定する（「左上のファ
インダ・パターン」）ステップと、
残りの２つのファインダ・パターンの内１つを左上のファインダ・パターンを軸に１８
０度未満回転させた場合にもたらされる残りの２つのファインダ・パターンの相対的距離
に基づき残りの２つのファインダ・パターンのラベル付けをするステップを含む方法。
【請求項２０】
画像内の機械読み取り可能な符号からビット・ストリームを抽出する装置で、符号は符
号の各々の角に隣接し、直角三角形の角を定義する３つのファインダ・パターンを含み、
前記装置は、
符号内のファインダ・パターンを特定するファインダ・パターン特定要素と、
ファインダ・パターンを用いて符号を配向させる符号配向要素で、配向は３つのファイ
ンダ・パターンの内どれが三角形の斜辺に対向する角に位置しているか判定し（「左上フ
ァインダ・パターン」）、残り２つのファインダ・パターンの１つが左上ファインダ・パ
ターンを軸に１８０度未満回転させられた場合にもたらされる残り２つのファインダ・パ
ターン間の相対距離に基づいて残り２つのファインダ・パターンにラベル付けをすること
を含む要素と、
配向に基づき符号の輪郭を描く符号輪郭描き要素と、
輪郭が描かれた符号に復号化のグリッドをマッピングする基準グリッド計算要素と、
マッピングされた符号からビット値を抽出するビット抽出要素と
を含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書において開示される方法およびシステムは一般的に符号認識に関し、より具体
的にはデジタル画像における機械読み取り可能な二次元符号の位置確認および復号化の方
法、装置、およびコンピュータ・プログラムに関する。
【背景技術】
【０００２】
文字認識システムを用いて文書の自動認識を容易にするために文書に機械読み取り可能
な文字で印をつけることは技術的に良く知られている。多くの業界ではラベルが、しばし
ばバーコードと呼ばれる機械読み取り可能な符号で印刷され、包装や小包に貼られる。ラ
ベル上の機械読み取り可能な符号は通常包装や小包自体からは明白でない、包装や小包に
関する情報を含んでいる。
【０００３】
例えば、統一コード協議会が統括する周知の万国製品コード（ＵＰＣ）規格による一次
元バーコード符号は、その簡単さから広く機械読み取り可能なラベルに使用される。例え
ばＺＩＰコード（郵便番号）を表すために用いられるＰＯＳＴＮＥＴなど、他の一次元バ
ーコード符号規格もいくつか提案されている。いずれの場合もこれらの規格に規定される
一次元バーコード符号はそれらの特定用途に適した最適状態を有する。これら一次元バー
コード符号は簡単にスキャンして復号化できるが、限られた情報量しか暗号化できないと
いう点で不利である。
【０００４】
一次元バーコード符号に関わる不利を克服するために、機械読み取り可能な二次元符号
が開発され、より大量の情報が暗号化できるようになった。例えば、ＰＤＦ４１７用ＡＩ
Ｍ統一コード規格は各バーコード符号が１１０８バイトまでの情報を暗号化し、圧縮でき
る二次元バーコード符号フォーマットを定義している。各バーコード符号に暗号化・圧縮
される情報は両端をスタートおよびストップ・パターンで挟まれた３から９０行のデータ
を含む二次元のデータ・マトリクスにまとめられる。例えばＡＺＴＥＣ、ＱＲコード、お
よびＭａｘｉＣｏｄｅなどその他機械読み取り可能な二次元符号フォーマットも検討され
ている。
【０００５】
機械読み取り可能な二次元符号はより大量の情報が暗号化できるが、このような二次元
符号を読み取り、復号化するためにより高度化が必要となる。事実、二次元符号のデコー
ドはしばしば比較的大量の演算を必要とする。その結果、復号化処理が開始される前に二
次元符号が正しく読み取られたことを確実にすることが望ましい。これは多量の環境にお
いて特に重要である。
【０００６】
二次元符号が実際に正しく読まれることを保証するために、通常ファインダ・パターン
が機械読み取り可能な二次元符号に埋め込まれる。ファイダ・パターンにより二次元符号
の輪郭が描かれ、配向されるので、二次元符号に暗号化されたデータを正しく抽出し復号
化することができる。例えば、ＱＲコードは各々黒または白の正方形モジュールの格子を
含み、左下、左上、および右上の隅の各々のモジュールに３つの正方形ファインダ・パタ
ーンを有する正方形符号を利用している。黒いモジュールを含む正方形囲いの外側向きの
側面が符号の角を形成する。さらに白いモジュールを含む線が黒いモジュールを含む正方
形囲いの内側向きの側面に面し、ファインダ・パターンを符号に埋め込まれたデータから
隔離している。
【０００７】
環境により、また読み取られる二次元符号の画像を取り込むために用いられる走査装置
により、取り込み画像内におけるファインダ・パターンの位置の確認し易さはかなり変わ
り得る。その結果、ファインダ・パターンの位置を確認し二次元符号を復号化する方法が
いくつか検討されている。
【０００８】
例えばムラマツの米国特許出願第２００４／００２０９８９号明細書はＱＲコード符号
を読み取る方法を開示している。この方法によると、読み取られた各ＱＲコード符号は水
平、垂直、および斜め方向に「約１、１、３、１、１」の黒および白の連が検索され、フ
ァインダ・パターン候補の基点には各々評価値が与えられる。ファインダ・パターン候補
の連続の長さが計算され、「１、１、３、１、１」の標準連との誤差が計算される。所定
の閾値を越えた誤差を有する連は候補から削除される。最も小さい誤差の連にはより高い
評価値が与えられる。評価ファインダ・パターンの中心座標は近似のファインダ・パター
ン候補の幅と中心を比較することによって判定される。これらの比較から最高評価のファ
インダ・パターンの所在位置が確認され、その中心座標が判定される。セル・サイズは平
均ファインダ・パターン幅を「７」で割ることにより、ファインダ・パターンから判定さ
れる。
【０００９】
ＱＲコード符号の配向はまずファインダ・パターンの中心座標をつないで三角形を形成
し、三角形の最長辺にない座標を左上のファインダ・パターンとみなすことにより判定さ
れる。左下および右上のファインダ・パターンは左上のファインダ・パターン周囲の空間
を四分円に分け、左上のファインダ・パターンに対し他の２つのファインダ・パターンが
どの隣接四分円に位置するかを判定して位置が確認される。
【００１０】
位置合わせパターンはまずファインダ・パターンからＱＲコード符号の回転角を検出し
符号のエッジ各々に平行した右上および左下のファインダ・パターンの中心から引かれる
線の交点を見出すことにより位置確認される。位置合わせパターンの中心は交点から内部
方向（すなわち左上のファインダ・パターン方向）に３個目のセルとみなされる。位置合
わせパターンを確認するために、みなされた位置合わせパターンの中心に中心を有する検
索範囲に対し５×５のテンプレートが比較される。突合せはテンプレートを構成するすべ
てのピクセルのピクセル値と検索範囲にあるピクセルのピクセル値との差の絶対値を合計
することにより行なわれる。１つにピクセルを検索範囲にあるすべてのピクセル上に順に
移してピクセル値の最小値を判定すると位置合わせパターンの中心をより正確に判定する
ことができる。
【００１１】
ＱＲコードのバージョンはファインダ・パターン間のセル数を計算することにより判定
される。ファインダ・パターン間の距離の平均を上述のごとくパターン幅から判定された
セル・サイズで割ると商が得られる。明・暗の閾値は右上および左下をつなぐ線に沿って
最大および最小ピクセル値を見出し、その２つを平均することにより計算される。次に標
準ＱＲコード符号からの点を入力画像に変換するために変換係数が計算される。モジュー
ル中心のピクセル値を計算するためにセルの判定された中心に隣接する４つのピクセルの
直線補間が行なわれる。
【００１２】
Ｂｒｕｎｅｌｌｉ他の米国特許第６７５８３９９号明細書はＱＲコード符号などの光学
コードを検出し歪みの補正をする方法が開示される。方法はまず２値閾値を判定し、高輝
度変化のある区域を見つけることにより関心領域を見出す。符号の配向は知られており、
頂点はＱＲコード用にＡＩＭ統一コード規格でまとめられた方法を用いて見つけられると
仮定される。見つけられた頂点を用い、光学コードがさらに処理するためにローカライズ
され、抽出される。この時点でタイミング・パターンおよび符号成分数が光学コード内に
見つけられる。符号成分数に基づき、理想的なグリッドが生成され、理想的なグリッドと
入力符号間での変換が計算される。閾値を用い、理想的グリッドの変換頂点の位置から輝
度値が取得され２値化される。
【００１３】
【特許文献１】米国特許出願公開第２００３／００７２４８９号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１４】
上述の引用はデジタル画像におけるＱＲコード符号からデータを見つけ、抽出する方法
を開示しているが、符号の配向は当然とみなされるか、演算上高価になる。さらに、これ
ら開示された方法は符号がデジタル画像内でスキューされ、または縦揺れしている状況に
対応していない。従って発明の一目的はデジタル画像内の二次元符号を見つけ、復号化す
る新規方法および装置を提供することにある。
【課題を解決するための手段】
【００１５】
一態様により、画像内の機械読み取り可能な符号からビット・ストリームを抽出する方
法で、符号は符号の各々の角に隣接し、直角三角形の角を定義する３つのファインダ・パ
ターンを含み、前記方法は、符号のファインダ・パターンを特定するステップと、ファイ
ンダ・パターンを用いて符号を配向させるステップで、前記配向ステップは、３つのファ
インダ・パターンの内どれが三角形の斜辺に対向して位置するか（「左上のファインダ・
パターン」）を判定するステップと、残りの２つのファインダ・パターンの内１つを左上
のファインダ・パターンを軸に１８０度未満回転させた場合にもたらされる残りの２つの
ファインダ・パターンの相対的距離に基づき残りの２つのファインダ・パターンのラベル
付けをするステップとを含むものであり、前記配向に基づき、符号の輪郭を描くステップ
と、前記輪郭が描かれた符号に復号化グリッドをマッピングするステップと、マッピング
された符号からビット値を抽出するステップとを含む。
【００１６】
ラベル付けの際、残り２つのファインダ・パターンは最初各々右上および左下のファイ
ンダ・パターンとラベル付けされる。右上および左下のいずれかが左上のファインダ・パ
ターンを軸に回転させられる。回転後、回転前後の右上および左下のファインダ・パター
ン間の相対距離を比較して最初のラベル付けを確認する。比較において最初のラベル付け
が確認されない場合、残り２つのファインダ・パターンのラベル付けを逆にする。
【００１７】
一実施形態で、判定は各ファインダ・パターンの対応する点の間に各々延びる複数の線
分を確立するステップを含む。左上のファインダ・パターンが白いピクセル上にのみ延び
る対応点に共通するファインダ・パターンとして特定される。画像は黒または白のトーク
ンにトークン化して、１つのみの白トークンを通る線分の２つに共通するファインダ・パ
ターンを左上のファインダ・パターンと特定することができる。
【００１８】
輪郭を描くステップは、左上、左下、および右上のファインダ・パターンに基づき左上
、左下、および右上の角を判定し、右上および左下のファインダ・パターンに基づきスキ
ュー・縦揺れに感応する技法を用いて符号の右下の角を判定するステップを含むことがで
きる。
【００１９】
スキュー・縦揺れに感応する技法は符号の右下角に隣接する符号の下側および右側エッ
ジ点を判定するステップを含むことができる。その際左下のファインダ・パターンから符
号の下側エッジ点まで延びる線と右上のファインダ・パターンから符号の右側エッジ点ま
で延びる線の交点が判定され、符号の右下の角が判定される。
【００２０】
別の態様により、画像内の機会読み取り可能な符号の配向を判定する方法が提供され、
符号は各々の角に隣接する３つのファインダ・パターンを含み、全般的に直角三角形の角
を定義し、方法は、三角形の斜辺に対向する角（「左上のファインダ・パターン」）に位
置するファインダ・パターンを特定するステップ、および残りの２つのファインダ・パタ
ーンの１つが左上ファインダ・パターンを軸に１８０度未満回転させられた場合にもたら
される残りの２つのファインダ・パターン間の相対距離に基づいて残りの２つのファイン
ダ・パターンにラベル付けをするステップ、を含む。
【００２１】
さらに別の態様により、画像内の機械読み取り可能な符号の配向を判定する方法が提供
され、符号は各々の角に隣接する３つのファインダ・パターンを含み、方法は、３つのフ
ァインダ・パターン各々の中心点間に延びる線分の各々の長さを計算するステップ、２つ
の線分の長さの二乗された合計が第３線分の長さの二乗に等しい２つの線分に共通するフ
ァインダ・パターンを左上のファインダ・パターンとしてラベル付けするステップ、およ
び残り２つのファインダ・パターンの１つが左上ファインダ・パターンを軸に１８０度未
満回転させられた場合にもたらされる残り２つのファインダ・パターン間の相対距離に基
づいて残り２つのファインダ・パターンにラベル付けをするステップ、を含む。
【００２２】
さらに別の態様により、画像内の機械読み取り可能な二次元符号の第４の角の位置を推
定する方法が提供され、符号は符号の左上、右上、および左下の角に隣接する左上、右上
、および左下のファインダ・パターンを含み、方法は、左上のファインダ・パターンに対
向する左下のファインダ・パターンの内側エッジと一直線上にある第１の内側エッジ線を
判定するステップ、左上のファインダ・パターンに対向する右上のファインダ・パターン
の内側エッジと一直線上にある第２の内側エッジ線を判定するステップ、左下のファイン
ダ・パターンにおける内側エッジの向かい側にある左下のファインダ・パターンにおける
外側エッジの第１の中間点を判定するステップ、右上のファインダ・パターンにおける内
側エッジの向かい側にある右上のファインダ・パターンにおける外側エッジの第２の中間
点を判定するステップ、符号の外側エッジと一致する第１の内側エッジ線に沿った第１の
外側エッジ点を判定するステップ、符号の外側エッジと一致する第２の内側エッジ線に沿
った第２の外側エッジ点を判定するステップ、第１の中間点と第２の外側エッジ点とを通
る第１の外側エッジ線を判定するステップ、第２の中間点と第１の外側エッジ点とを通る
第２の外側エッジ線を判定するステップ、および第１の外側エッジ線と第２の外側エッジ
線との交点を右下の角と宣言するステップ、を含む。
【００２３】
さらに別の態様により、画像内における機械読み取り可能なビット・ストリームを抽出
する装置が提供され、符号は各々の角に隣接する３つの四角形ファインダ・パターンを含
み、全般的に直角三角形の角を定義し、装置は、符号内のファインダ・パターンを特定す
るファインダ・パターン特定要素と、ファインダ・パターンを用いて符号を配向させる符
号配向要素で、配向は３つのファインダ・パターンの内どれが三角形の斜辺に対向する角
に位置しているか判定し（「左上ファインダ・パターン」）、残り２つのファインダ・パ
ターンの１つが左上ファインダ・パターンを軸に１８０度未満回転させられた場合にもた
らされる残り２つのファインダ・パターン間の相対距離に基づいて残り２つのファインダ
・パターンにラベル付けをするステップを含む要素と、配向に基づき符号の輪郭を描く符
号輪郭描き要素と、輪郭が描かれた符号に復号化のグリッドをマッピングする基準グリッ
ド計算要素と、マッピングされた符号からビット値を抽出するビット抽出要素とを含む。
【００２４】
さらに別の態様により画像内の機械読み取り可能な符号の配向を判定する装置が提供さ
れ、符号は各々の角に隣接する３つのファインダ・パターンを含み、全般的に直角三角形
の角を定義し、装置は、各ファインダ・パターン上の対応する点の間に各々延びる複数の
線分を確立する線分生成要素と、三角形の斜辺に対向する角に位置するファインダ・パタ
ーン（「左上ファインダ・パターン」）を特定する符号配向要素で、符号配向要素はさら
に残り２つのファインダ・パターンの１つが左上ファインダ・パターンを軸に１８０度未
満回転させられた場合にもたらされる残り２つのファインダ・パターン間の相対距離に基
づいて残り２つのファインダ・パターンのラベル付けする要素とを含む。
【００２５】
さらに別の態様により、画像における機械読み取り可能な符号からビット・ストリーム
を抽出するコンピュータ・プログラムを具現するコンピュータ読み取り可能な媒体が提供
され、符号は各々の角に隣接する３つのファインダ・パターンを含み、全般的に直角三角
形の角を定義し、コンピュータ・プログラムは、符号内のファインダ・パターンを特定す
るコンピュータ・プログラムのコードと、ファインダ・パターンを用いて符号を配向させ
るコンピュータ・プログラムのコードで、配向は３つのファインダ・パターンの内どれが
三角形の斜辺に対向する角に位置しているか判定し（「左上ファインダ・パターン」）、
残り２つのファインダ・パターンの１つが左上ファインダ・パターンを軸に１８０度未満
回転させられた場合にもたらされる残り２つのファインダ・パターン間の相対距離に基づ
いて残り２つのファインダ・パターンにラベル付けをするステップを含むコードと、配向
に基づいて符号の輪郭を描くコンピュータ・プログラムのコードと、輪郭が描かれた符号
に復号化のグリッドをマッピングするコンピュータ・プログラムのコードと、マッピング
された符号からビット値を抽出するコードと、を含む。
【００２６】
さらに別の態様により、画像における機械読み取り可能な符号の配向を判定するコンピ
ュータ・プログラムを具現するコンピュータ読み取り可能な媒体が提供され、符号は各々
の角に隣接する３つのファインダ・パターンを含み、全般的に直角三角形の角を定義し、
コンピュータ・プログラムは、三角形の斜辺に対向する角（「左上のファインダ・パター
ン」）に位置するファインダ・パターンを特定するコンピュータ・プログラムのコードと
、残りの２つのファインダ・パターンの１つが左上ファインダ・パターンを軸に１８０度
未満回転させられた場合にもたらされる残りの２つのファインダ・パターン間の相対距離
に基づいて残りの２つのファインダ・パターンにラベル付けをするコンピュータ・プログ
ラムのコードと、を含む。
【００２７】
本明細書で説明される方法および装置は機械読み取り可能な二次元符号を配向する簡単
で演算上複雑でない方法を提供し、また符号の角を推定する際符号のスキューや縦揺れを
考慮に入れることにより入力範囲が理想的でない場合にも入力符号に対する基準グリッド
の正確なマッピングを提供する。
【発明を実施するための最良の形態】
【００２８】
添付図面を参照して実施形態をより詳細に説明する。以下の説明においてデジタル画像
内の機械読み取り可能な二次元符号の位置確認および復号化の方法、装置、およびコンピ
ュータ・プログラムを具現するコンピュータ読み取り可能な媒体が提供される。方法の際
、機械読み取り可能な二次元符号のファインダ・パターンが特定され、符号が配向される
。符号の一バージョンの推定に基づき基準グリッドが符号にマッピングされ、マッピング
されたグリッドからビット・ストリームが抽出され復号化される。
【００２９】
二次元符号の位置確認および復号化の方法および装置はパソコンまたは他のコンピュー
タ・システム環境などの処理装置により実行されるコンピュータ実行可能な滅入れを含む
ソフトウェア・アプリケーションに具現され得る。ソフトウェア・アプリケーションはル
ーチン、プログラム、オブジェクト・コンポーネント、データ構造等々を含むプログラム
・モジュールを含むことができ、コンピュータ読み取り可能な媒体に格納されるコンピュ
ータ読み取り可能なプログラム・コードとして具現されることができる。コンピュータ読
み取り可能な媒体は後にコンピュータ・システムで読み取られるデータを格納できる任意
のデータ格納装置である。コンピュータ読み取り可能な媒体は例えば読み込み専用メモリ
、ランダムアクセス・メモリ、ＣＤ−ＲＯＭ、磁気テープ、および光学的データ記憶装置
を含む。コンピュータ読み取り可能なプログラム・コードを、連結コンピュータ・システ
ムを含むネットワーク上に分散することができ、この場合コンピュータ読み取り可能なプ
ログラム・コードは分散的に格納され、実行される。
【００３０】
例示を容易にするために符号の位置確認および復号化方法および装置はＱＲコード符号
に関連して説明される。しかし当業者は本明細書で説明される原理は他の機械読み取り可
能な二次元コードの位置確認および復号化にも適用できることを理解しよう。
【００３１】
図１はモデル１ ＱＲコード符号２の構造を示し、図２はモデル２ ＱＲコード符号１６
の構造を示す。ＱＲコード符号２，１６は各々規則的な四角形のアレーに配列された名目
的に四角形のモジュールで構成される。符号２，１６は各々暗号化領域１２，２８および
機能パターンを含む。機能パターンは符号の３つの角におけるファインダ・パターン８，
３０、各ファインダ・パターンを符号の残部から分離するセパレータ４，２２、およびタ
イミング・パターン６，２４を含む。モデル１ ＱＲコード符号２のみ拡張パターン１４
を含み、モデル２ ＱＲコード符号１６のみ位置合わせパターン２６を含む。ファインダ
・パターンは直角三角形の角を定義する。三角形の斜辺に対向するファインダ・パターン
は通常符号の左上の角に隣接して位置する。しかし符号の配向によってこのファインダ・
パターンは符号の別の角に隣接して現れることができる。参照し易くするため、三角形の
斜辺に対向するファインダ・パターンは符号の異なった角に隣接して位置していても「左
上ファインダ」パターンとラベル付けすることにする。
【００３２】
図３はＱＲコード符号のファインダ・パターンの構造をより良く示す。図に示されるよ
うに、ファインダ・パターンは黒いモジュールを含む３×３のブロックが１モジュール厚
の白いモジュールの四角い囲みに囲まれたものを含む。白いモジュールの四角い囲みは同
様にそれ自体１モジュール厚の黒いモジュールの四角い囲みに囲まれている。ＱＲコード
符号および復号化に関するさらなる詳細はＱＲコードに関するＡＩＭ（自動認識モビリテ
ィ協会）統一コード規格（ＩＳＳ ＱＲコード）にあり、その内容は引用により本明細書
に組み入れられる。
【００３３】
図４に移ると、デジタル画像においてＱＲコードなどの機械読み取り可能な二次元符号
の位置確認および復号化をするために実施する全般的な工程を呈示するフローチャートが
示される。これらの工程は全般的に符号９０を用いて参照される。方法において、デジタ
ル画像を調べて中に符号が存在するか判定する（工程１００）。デジタル画像に符号が位
置確認されると、位置確認された符号において符号のファインダ・パターンが特定される
（工程２００）。次にファインダ・パターンを用いて符号が配向され（工程３００）、符
号のバージョンが推定される（工程４００）。推定された符号バージョンに従い、基準グ
リッドが符号にマッピングされ（工程５００）、それにより符号に暗号化されるデータが
マッピングされた基準グリッド上の点から抽出される（工程６００）。
【００３４】
図５は符号の位置確認のためにデジタル画像を調べる際（工程１００）実施される工程
をより良く示すフローチャートである。入力されたデジタル画像で符号を含む可能性のあ
る領域の位置を確認するために、デジタル画像のエッジが最初に特定される（工程１１０
）。デジタル画像におけるエッジは１ピクセルを間にした１対のピクセルで、輝度（スケ
ール０−２５５）で「３２」を超える差があるものと定義される。エッジ特定の際、デジ
タル画像は最初に水平方向に、次に垂直方向にスキャンされエッジが特定される。このプ
ロセスにおいて以下が仮定される。
（１）デジタル画像は白および黒の領域を区別するために少なくとも輝度量８０のコン
トラストがある。輝度差が８０未満でも認識できる画像は得られるが、このような場合ノ
イズの扱いが困難である可能性がある。
（２）黒および白領域間の不鮮明な灰色の区域は最大４ピクセルである。
（３）１つ置きのピクセルをスキャンできるよういずれの重要な成分も１ピクセルの幅
ではない。
【００３５】
上記によれば、任意の符号のエッジにおいて１ピクセル離れると少なくとも「４０」の
差をもたらすので殆どの符号のエッジが特定される。
【００３６】
次にデジタル画像をスキャンして上記に定義したごとくエッジの位置確認をし、新しい
画像でエッジをピクセル値で表すことによりエッジ・カウント画像が作成される（工程１
１２）。例えば、エッジ・カウント画像を作成するために、値が「７」のピクセルはデジ
タル画像で対応する８×８領域において７つのエッジを表す。エッジ・カウント画像は入
力画像の１／８のサイズとなり、その後の処理が非常に速くできる。
【００３７】
エッジ・カウント画像は通常複数の四角形を含む。エッジ・カウント画像において隣接
する「エッジっぽい」四角形（すなわちより高いピクセル値を有する）は共通領域に関連
付けられるとしてラベル付けされる（工程１１４）。黒から白への一回限りの移行（例え
ば図１１の画像で白い紙から黒の背景へで、これは値が４である）以外の殆どのエッジを
特定するように黒−白閾値が「５」に設定される。この場合閾値化はラベル付けと統合さ
れる。
【００３８】
格別に大きい画像ではエッジが充分に集中しておらず、正しく符号を含む領域を特定で
きない可能性がある。そのような場合、より高い縮小率（「８」でなく「１６」）を考慮
しても良い。
【００３９】
ラベル付けの際、画像は１回スキャンされ、連結された領域はツリー構造を用いる関連
表に記載され、例えば２つの領域は３つ目の領域を根として共通に有することで関連して
いても良い。
【００４０】
この時点で、１００未満の領域はすべて機械読み取り可能な二次元符号としては小さ過
ぎると仮定され、偽陽性として除去される（工程１１６）。
【００４１】
次に、関連付けされたエッジ四角形の領域を囲む最小四辺形の角が判定される（工程１
１８）。関連付けされたエッジ四角形は任意の恣意的な角度に傾斜していることができる
が、演算を削減するために４５度の角度倍数で傾斜している四辺形のみ考慮される。エッ
ジ・カウント画像は１回スキャンされ、極値点（例えば最小ｘ値を有する最も左の点、ま
たは傾斜四辺形の場合最小ｘ＋ｙ値を有する最も左上の点等々）が捕らえられる。ある領
域は左端、右端、上端、および下端境界点を有する非傾斜の四辺形または左上端、右上端
、左下端、右下端の境界点を有する傾斜四辺形で囲まれ得ることが理解されよう。上述の
ように、最小の囲み面積を有する囲み四辺形が選択される。この段階で、境界点は入力デ
ジタル画像の元のサイズに再度拡大される。
【００４２】
図１２は再度拡大された囲み四辺形を図１１の入力デジタル画像に重ね合わせたところ
を示す。図示されるように、いくつかの領域がＱＲコード符号の候補を含むものとして特
定されている。２つの符号候補が特定されているが、その内１つだけが実際にＱＲコード
符号である。各特定領域はＱＲコード符号が含まれているか判定するために処理されるが
、最も高いエッジ・カウントを含む領域が最初に処理される。
【００４３】
符号候補を含む領域が特定されると、まず閾値を計算し、次にその閾値に対する値に基
づきすべてのピクセル黒または白に変化することにより入力画像に対応する閾値画像が得
られる（工程１２０）。
閾値は入力デジタル画像の１０ピクセルを行および列のステップ・サイズ（Row Step S
ize、Column Step Size）としてそれに対するピクセル輝度値の合計（Pixel Sum）を形成
し、合計されたピクセル値の数（Num Pixel）で合計を割ることにより計算される。入力
デジタル画像の閾値を計算するための擬似コードを表１に示す。
【００４４】
【表１】
2007265407.tif 000003
【００４５】
図１１における入力画像の閾値は「１１６」である。閾値画像の寸法は入力デジタル画
像のそれと等しいことが理解されよう。
【００４６】
図６は領域内で符号のファインダ・パターンを特定（工程２００）するために実行する
肯定をより良く示している。まず、閾値化された画像の各領域は行方向にトークン化され
（工程２１０）、列方向にトークン化される（工程２１２）。トークン化は同色ピクセル
の連を１つの単位として処理し易くするために黒および白のピクセルの同じ連を各々黒お
よび白のトークンに変換する。
【００４７】
１つの領域におけるファインダ・パターンをみつけるために（もしある場合）、その領
域におけるすべてのＱＲコードファインダ・パターン候補が特定され（工程２１４）、確
信レベルが与えられる。ファインダ・パターン候補が３つを越える場合（工程２１６）、
最も高い確信レベルが与えられた３つのファインダ・パターン候補がその領域のファイン
ダ・パターン候補として選択される（工程２２０）。ファインダ・パターン候補が３つ未
満の場合（工程２１６）、その領域はＱＲコード符号を含まないとみなされ無視される（
工程２１８）。
【００４８】
【表２】
2007265407.tif 000004
表２に示されるように、ファインダ・パターン候補の特定および確信レベルの付与は閾
値化された画像の各行を最初から最後（Height）までスキャンし、行方向にトークンを形
成し（Row Wise Tokenize）トークンをアレー（Token Array）に加えることにより実行さ
れる。少なくとも５つのトークンが一旦形成されると、行方向の黒トークンのパターンが
トークン幅を用いて「１、１、３、１、１」のパターンを提供すると（Token Array[nTok
Idx].width、Token Array[nTokIdx+1].width等々）、行方向のパターンの中央は列（col
）として特定される。次に行を中心とした１、１、３、１、１パターンが列（col）に沿
ってみつかるか特定される。パターンが列の中に特定されると、行方向パターンの中央が
ファインダ・パターン候補の中心のＸ座標（ｒｃ）とみなされ、列方向パターンの中央が
ファインダ・パターン候補の中心のＹ座標（ｃｃ）とみなされる。ファインダ・パターン
候補の中心は次に候補リストに加えられる（Candidate List）。ファインダ・パターン候
補の中心（ｒｅ，ｃｃ）が既に候補リスト（Candidate List）に存在する場合その確信レ
ベルは増分される。
【００４９】
図７は一旦ファインダ・パターンが特定された場合ＱＲコード符号を配向させる工程（
工程３００）をより良く示している。この処理において、以下が仮定される。
１．ファインダ・パターンの位置が正しく特定されたこと。
２．ＱＲコード符号の３つのファインダ・パターンの位置が確認されていること。
３．ＱＲコード符号のクワイエット・ゾーンは他のマーキングが全くないこと。
４．ＱＲコード符号全体が入力デジタル画像内に存在していること。
【００５０】
図１１の入力デジタル画像にとって、配向は図１３に示すようにＱＲコード符号を含む
領域の右下にあるファインダ・パターンをファインダ・パターンＡ、領域の左下にあるフ
ァインダ・パターンをファインダ・パターンＢ、および領域の右上にあるファインダ・パ
ターンをファインダ・パターンＣとして確定する。
【００５１】
配向は３つのファインダ・パターン各々の各エッジの中点をみつけることから始まる（
工程３１０）。これらの中点は図１３において点ａから「１」とラベル付けされる。ファ
インダ・パターンの各ペアの対応する中点間に延びる線分に沿ってトークンが数えられる
（工程３１２）。この場合の対応する中点とは｛ａからｅ｝、｛ａからｉ｝、｛ｅからｉ
｝、｛ｃからｇ｝、｛ｃからｋ｝、｛ｇからｋ｝、｛ｂからｆ｝、｛ｂからｊ｝、｛ｊか
らｆ｝、｛ｄからｊ｝、｛ｄからｌ｝、および｛ｊからｌ｝である。間に１つのみの白ト
ークンを有する中点のペアが得られる。これらの中点のペアは図１３において｛ｃからｇ
｝と｛ａからｉ｝である。
【００５２】
１つのみの白トークンを有する中点のペアに共通するファインダ・パターンはこの場合
ファインダ・パターンＡであるが、これが左上のファインダ・パターンと宣言される（工
程３１６）。この時点で、一般的にＱＲコード符号の向かい合った角にある残りの２つの
ファインダ・パターンは一時的に各々左下および右上パターンとラベル付けされる（工程
３３６および工程３３８）。
【００５３】
左下および右上パターンとラベル付けされるファインダ・パターン間の距離が次に見出
される（工程３４０）。これらのファインダ・パターンに割り当てられたラベルが正しい
かを判定するために、一時的に右上とラベル付けされたファインダ・パターンは左上のフ
ァインダ・パターンの周りを９０度左回りに回転される（工程３４２）。回転後、一時的
に右上とラベル付けされたファインダ・パターンが工程３４０における回転前の左下ファ
インダ・パターンにより距離的に近くなった場合（工程３４４）、これらのファインダ・
パターンに割り当てられたラベルを逆にする（工程３４８）。回転後、一時的に右上とラ
ベル付けされたファインダ・パターンが工程３４０における回転前の左下ファインダ・パ
ターンにより距離的に遠くなった場合（工程３４４）、これらのファインダ・パターンに
割り当てられたラベルは正しいとみなされる（工程３４６）。
【００５４】
左回りに９０度の回転が指定されたが、ラベルが付けられた右上のフィンダ・パターン
を１度以上１８０度未満の範囲で左上のファインダ・パターンを軸に回転させることによ
り右上および左下のファインダ・パターンのラベル付けを確認できることが理解されよう
。
【００５５】
一旦ファインダ・パターンが正しくラベル付けされ、ＱＲコード符号の配向が判定され
ると、ＱＲコード符号の復号化に用いられる基準グリッドの構成を決めるために符号バー
ジョンが推定される（工程４００）。ＱＲコード符号バージョンの推定には、ＱＲコード
符号の行および列のセル数が判定される。特に、再度図１３を参照すると、点｛ｎとｍ｝
および点｛ｏとｐ｝の間のトークン数（Number Tokens Between）が判定される。図１３
に示されるＱＲコード符号に関しては点｛ｏとｐ｝間で判定されたトークン数は点｛ｎと
ｍ｝間のトークン数と同じで、数は「１３」である。ＱＲコード符号のバージョン番号（
Version Number）を推定するために下記の方程式（１）を用いる。
【００５６】
【数１】
2007265407.tif 000005
【００５７】
方程式（１）に基づき、図１３におけるＱＲコード符号のバージョンは「２」である。
符号の１行にあるモジュール数（Number Of Modules）を推定するために下記の方程式（
２）を用いる。
【００５８】
【数２】
2007265407.tif 000006
方程式（２）を並べ替えると、バージョン番号は下記の方程式（３）により計算するこ
とができる。
【００５９】
【数３】
2007265407.tif 000007
【００６０】
図１１に示す入力デジタル画像におけるＱＲコード符号の場合、Timing-PatternMods＝
１７で、その符号のバージョン番号は「３」であるので１行のモジュール数は「３３」で
ある。
【００６１】
図９は入力デジタル画像におけるＱＲコード符号に基準グリッドをマッピングする工程
をより良く示している。ＱＲコード符号と基準グリッドとの間の変換を作成するために充
分な数の座標を得るにはＱＲコード符号の４つの角の位置を確認する必要がある。図１５
に示す符号の角Ａco，Ｂco、および角Ｃcoを推定するために左上、右上、および左下のフ
ァインダ・パターンが用いられる。
【００６２】
一般的に符号の角を推定する際、図１６に示すように３つの位置確認されたファインダ
・パターンＡ，Ｂ，Ｃの外側のエッジにある点をみつけ、それらを用いて最小二乗近似法
により左線、右線、上線および下線を形成する。図１７に示されるように、各線を用いて
符号の角Ａco，Ｂco、および角Ｃcoを特定する。詳しくは、符号の角Ａcoは上線と左線の
交点にあり、符号の角Ｂcoは上線と右線の交点にあり、符号の角Ｃcoは下線と左線の交点
にある。４つ目の符号の角Ｄco（即ちファインダ・パターンのない角）は後述のように別
の方法で推定される。
【００６３】
最小二乗近似法は任意の種類の最良適合曲線ｆ（ｘ）は与えられたデータのセットから
偏差ｄの二乗（最小二乗エラー）の最小合計を有する曲線であるということに基づき、各
点を通るように曲線を合わせる。最小二乗近似法によると、最良適合曲線は以下の特性を
有する。
【００６４】
【数４】
2007265407.tif 000008
最小二乗線は直線で、
【００６５】
【数５】
2007265407.tif 000009
ｎ＝２として（ｘ1，ｙ1）、（ｘ2，ｙ2）、…、（ｘnｙn）、である与えられたデータ
のセットに近似する。最良適合曲線ｆ（ｘ）は最小二乗エラーを有し、すなわち、
【００６６】
【数６】
2007265407.tif 000010
ここでａとｂは未知の係数で、ｘiとｙiは既知の座標であることが特記される。最小二
乗エラーを得るためには未知の係数ａとｂは以下の方程式で表現されるようにゼロの一次
導関数が得られなければならない。
【００６７】
【数７】
2007265407.tif 000011
上記を展開させると以下が得られる。
【００６８】
【数８】
2007265407.tif 000012
従って未知の係数ａとｂは以下のように解くことによって得られる。
【００６９】
【数９】
2007265407.tif 000013
上述の方法は符号の角Ａco，Ｂco、および角Ｃcoに対する推定として充分である。しか
し、入力デジタル画像におけるＱＲコード符号のスキューまたは縦揺れにより、下線およ
び右線の交点は符号の角Ｄcoの充分に正確な推定を可能にしないかもしれない。逆にこれ
らの線の交点はＱＲコード符号のかなり中側または外側にある点を示す可能性がある。そ
のため、符号のスキュー・縦揺れの可能性を考慮した角推定法が符号の角Ｄcoを推定する
ために用いられる。
【００７０】
ここで図１８から図２１を参照しながら符号の４つ目の角Ｄcoを推定する方法を説明す
る。ファインダ・パターンＡに対向するファインダ・パターンＢの内側のエッジＥBと同
一線上にある線ＬBとファインダ・パターンＡに対向するファインダ・パターンＣの内側
のエッジＥCと同一線上にある線ＬCとの交点として点Ｐiが定義される（図１８および図
１９参照）。線ＬCおよび線ＬB各々上の狭い間隔のテスト・ポイントの組が点Ｐiと各々
の符号の外にある任意の点Ｑ，Ｒとの間に定義される（図２０参照）。
【００７１】
ファインダ・パターンＢのエッジＥBの反対側にある外側エッジに沿った中点Ｆおよび
ファインダ・パターンＣのエッジＥCの反対側にある外側エッジに沿った中点Ｇが定義さ
れる。中点Ｆから線ＬCに沿った各テスト・ポイントに延びる線分が交点の点Ｐiに最も近
いテスト・ポイントから始まり順に定義される。各線分が定義される際その線分が白ピク
セルのみを通るか判定するために調べられる。白ピクセルのみを通る線分が判定されると
、プロセスは停止され、そのテスト・ポイントは符号の外側エッジと一致する線ＬCの上
の点Ｑ'と指定される。同様に、中点Ｇから線ＬBに沿った各テスト・ポイントに延びる線
分が交点の点Ｐiに最も近いテスト・ポイントから始まり順に定義される。各線分が定義
される際その線分が白ピクセルのみを通るか判定するために調べられる。白ピクセルのみ
を通る線分が判定されると、プロセスは停止され、そのテスト・ポイントは符号の外側エ
ッジと一致する線ＬBの上の点Ｒ'と指定される。線分（Ｆ→Ｑ'）および（Ｇ→Ｒ'）の方
程式が次に判定され、それにより交点の点が計算され、符号の４つ目の角Ｄcoの位置が得
られる（図２１参照）。
【００７２】
符号の４つ目の角Ｄcoの位置を確認する上記方法は実際の符号の角に近い符号のエッジ
の点を利用するので、単に図１７の下線と右線の交点を用いて符号の４つ目の角Ｄcoを定
義する場合より正確な結果が得られる。
【００７３】
ＱＲコード符号の角を得た後、符号平面から基準グリッド平面への変換が判定される（
工程５１２）。一般的に１つの射影平面（Ｘ）から別の射影平面（ｘ）への射影変換は、
変換マトリクスを用いて以下のように表される。
【００７４】
【数１０】
2007265407.tif 000014
【００７５】
このような変換がデカルト座標で表されると、射影変換の非直線性はユークリッド法で
以下のように表される。
【００７６】
【数１１】
2007265407.tif 000015
【００７７】
示されるとおり、射影変換マトリクスＴは一意的なマッピングを定義するために８つの
独立したパラメータを必要とする。平面上の各点は２つのデカルト座標方程式を提供する
ので、変換マトリクスを一意的に定義するためには２つの射影変換された平面間で４つの
対応点を見出す必要がある。変換マトリクスＴの全体的な尺度は任意であるため、「ｔ33
＝１」と設定できる。対応する４点をと表すと（λiｘi，λiｙi，λi）t＝Ｔ（Ｘi，Ｙi
，１）t、その結果の線形方程式は以下のとおりになる。
【００７８】
【数１２】
2007265407.tif 000016
【００７９】
この線形方程式を解くことにより変換マトリクスＴが得られる。逆変換マトリクス（In
verse Matrix）Ｔinverseを得るためには以下の線形方程式を解く。
【００８０】
【数１３】
2007265407.tif 000017
【００８１】
ＱＲコード符号の復号化の場合、位置が確認された符号の４つの角（Corner）Ａco，Ｂ
co，Ｃco、および角Ｄcoを入力デジタル画像平面における４点として用いることができる
。変換マトリクスＴを見出すために、以下に示す線形方程式を解く。
【００８２】
【数１４】
2007265407.tif 000018
【００８３】
変換マトリクスＴは入力符号を基準グリッド（Reference Grid）にマッピングし、逆変
換マトリクスＴinverseは基準グリッドを入力符号にマッピングする。逆変換マトリクス
Ｔinverseを得るには（工程５１４）以下の線形方程式を解く。
【００８４】
【数１５】
2007265407.tif 000019
【００８５】
基準グリッドをＱＲコード符号にマッピングする逆変換マトリクスＴinverseを得た後
、ＱＲコード符号からビットを抽出するためのグリッドが形成される（工程５１８）。す
なわち、基準グリッド上の点が判定され、ＱＲコード符号上の対応点にマッピングされる
。ＱＲコード符号内のモジュールの幅（Width of the Module）は５ピクセルとの仮定の
下で、第１行の第１のモジュールの中心は点（３，３）にあり、同じ行の次のモジュール
では点（８，３）にあり、以下同様である。一旦これらの点が各々逆変換マトリクスＴin
verseを用いて変換されると、入力画像空間におけるｘおよびｙ値のグリッドが得られる
。以下の方程式は基準グリッドにおける点（Ｘ，Ｙ）の入力画像空間における点（ｘ，ｙ
）への変換を例示する。
【００８６】
【数１６】
2007265407.tif 000020
【００８７】
一旦任意のグリッド点（Ｘ，Ｙ）のｘ値およびｙ値が得られると、入力画像における与
えられた位置のピクセル値を読み取ることができる。ピクセル値が黒である場合ビット値
は「１」に設定され、それ以外の場合ビット値は「０」に設定される。
【００８８】
図１０は符号から暗号化されたデータを抽出する工程をより良く示している（工程６０
０）。まず、グリッドからフォーマット情報（Format information）が得られ（工程６１
０）、誤り訂正を用いて復号化される（工程６１２）。フォーマット情報（図１、符号１
０および図２、符号２０）は５個のデータ・ビットおよび１０個のBose-Chaudhuri-Hocqu
engem（ＢＣＨ）誤り訂正ビットを含む。
【００８９】
フォーマット情報を復号化するために、フォーマット情報のビット・パターンが全部ゼ
ロでないことを保証すべく１５ビット・シーケンスをモデル２マスク・パターン「101010
000010010」で排他論理和（ＸＯＲ）演算することによりフォーマット情報のマスクを解
除する。マスク解除されたシーケンスの誤りは周知のＢＣＨ（１５，５）誤り訂正方法を
用いて判定される。この方法では、係数をマスク解除シーケンスとする多項式（Polynomi
al）をジェネレータ多項式Ｇ（ｘ）＝ｘ10＋ｘ8＋ｘ5＋ｘ4＋ｘ2＋ｘ＋１で割る。余りの
多項式の係数ストリング（coefficient string of above remainder polynomial）はデー
タ・ビット・ストリングに付加されＢＣＨ（１５，５）暗号ストリングを形成する。
【００９０】
誤りが見出されない場合、モデル・タイプは「２」、マスク解除されたシーケンスの最
初の２つ最上位ビット（ＭＳＢ）は誤り訂正レベル（Error Correction Level）で、次の
３つのＭＳＢはマスキング・パターン基準であると判定される。
【００９１】
マスク解除されたシーケンスに誤りが見出された場合、モデル１マスク・パターン「01
0100000100101」を用いてビット・シーケンスをＸＯＲ演算することによりフォーマット
情報のマスクを解除する。マスク解除されたシーケンスにおける誤りはＢＣＨ（１５，５
）誤り訂正方法を用いて判定され、誤りがない場合、モデル・タイプは「１」、マスク解
除されたシーケンスの最初の２つ最上位ビット（ＭＳＢ）は誤り訂正レベルで、次の３つ
のＭＳＢはマスキング・パターン基準であると判定される。次の例はフォーマット情報の
マスクを解除する方法を示す。
【００９２】
2007265407.tif 000021
【００９３】
以下はさらにビット・シーケンスをモデル２のマスク・パターン「101010000010010」
によりＸＯＲ演算してフォーマット情報モジュールのマスクを解除した後、誤り訂正がＢ
ＣＨアルゴリズムに従ってどのように進むかを説明する。多項式Ｒ（ｘ）の係数のベクト
ルＲは以下のとおり得られる。
Ｒ＝（ｒ０，ｒ１，ｒ２，…，ｒ１４）
または、
Ｒ（ｘ）＝ｒ0＋ｒ1ｘ＋ｒ2ｘ2＋…＋ｒ14ｘ14・・・・・（２１）
但し、ｒi（ｉ＝０〜ｉ＝１４）は「０」または「１」である。
【００９４】
次に、ベクトルＲのシンドロームＳi（ｉ＝１，３，５）が計算される。
Ｓ１＝Ｒ（α）＝ｒ0＋ｒ1α＋ｒ2α2＋…ｒ14α14・・・・・（２２）
Ｓ３＝Ｒ（α）＝ｒ0＋ｒ1α3＋ｒ2α6＋…ｒ14α42・・・・・（２３）
Ｓ５＝Ｒ（α）＝ｒ0＋ｒ1α5＋ｒ2α10＋…ｒ14α70・・・・・（２４）
但し、
αはフィールドＧＦ（２4）の原始成分である。
【００９５】
次に、方程式の根を得ることによって誤り位置が見出される。
Ｓ1＋α1＝０・・・・・（２５）
Ｓ3＋Ｓ2α1＋Ｓ1α2＋α3＝０・・・・・（２６）
Ｓ5＋Ｓ4α1＋Ｓ3α2＋Ｓ2α3＝０・・・・・（２７）
但し、
Ｓ2＝Ｓ1の二乗、
Ｓ4＝Ｓ2の二乗である。
【００９６】
上記の方程式を解くことにより誤り位置各々に対する変数αi（ｉ＝１−３）が見出さ
れる。次に変数を以下の多項式に置き換えＧＦ（２4）の成分が１つずつ置き換えられる
。
α（ｘ）＝ｘ3＋α1ｘ2＋α2ｘ＋α3・・・・・（２８）
【００９７】
α（αｊ）＝０をなす成分αｊのｊ桁目（０桁から数え）に誤りが見つかった場合、誤
りは各誤り位置のビット値を逆転することにより訂正される。
【００９８】
ＱＲコード符号がモデル２のタイプで（工程６１４）、そのバージョンが（工程４００
において）「７」以上と推定された場合（工程６１６）、バージョン番号は正しく推定さ
れたことを保証するために確認される。バージョン情報（図２、符号１８）は６つのデー
タ・ビットを含む１８ビット・シーケンス、拡大ＢＣＨ（１８，６）誤り訂正コードを用
いて１２個の誤り訂正ビットが計算されている。
【００９９】
この場合に用いられるジェネレータ多項式は以下のとおりである。
Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ5＋ｘ2＋１・・・・・（２９）
【０１００】
2007265407.tif 000022
【０１０１】
バージョン番号はＱＲコード符号の左下にあるバージョン情報に誤りがあるか調べるこ
とによって得られる。エラーがない場合、バージョン番号は左下のバージョン情報ビット
の内最上位ビット６個によって表される。エラーがある場合、ＱＲコード符号の右上にあ
るバージョン情報に誤りがあるか調べる。エラーがない場合、バージョン番号は右上のバ
ージョン情報ビットの内最上位ビット６個によって表される。
【０１０２】
ＱＲコードの性格上、バージョン情報内の誤りをみつけ、訂正するのに数式を用いるこ
とができない。代わりに、バージョン情報ビットを符号から読み取り（工程６１８）、そ
れを用いて以下の表からバージョン情報を調べる必要がある。ＱＲコード符号から読み取
られたバージョン・ビットと差が最小数のビットを有する行が正しいバージョン番号とみ
なされる。
【０１０３】
【表３】
2007265407.tif 000023
【０１０４】
上記表３からバージョン番号を検索して、推定されたバージョン番号が検索バージョン
番号と同じでない場合（工程６２０）、グリッドは正しいバージョン番号に基づいて再形
成される（工程６２２）。
【０１０５】
一旦グリッドが正しく形成されたと判定されると、ビット・ストリームが利用できるよ
うになる。しかし、ビット・ストリームはフォーマット情報において指定されるマスク条
件を用いて生成されたマスク符号によってマスクされている。従って、フォーマット情報
から検索されたマスク条件を用いてマスク符号を作成する必要がある（工程６２４）。マ
スクを解除するために、入力符号ビット・ストリームを用いてマスク符号をＸＯＲ演算す
ることにより実際のビット・ストリームを検索する（工程６２６）。
【０１０６】
上述され、引用により本明細書に組み入れられるＡＩＭ ＩＳＳ ＱＲコード規格に指定
されるグリッドのレイアウトを用いビット・ストリームから８ビットの符号語が形成され
る（工程６２８）。
【０１０７】
ＱＲコード符号内の誤りは信頼できない伝送またはスキャン中のラベルの誤読を含み各
種の要因があり得る。しかし、ＱＲコード符号のデータに内蔵される冗長により、誤り検
出・訂正手法を用い、形成された符号語からある程度行方不明または誤ったデータを回復
することが可能である（工程６３０）。
【０１０８】
最も一般的に用いられる誤り検出・訂正手法はReed Solomonアルゴリズムで、これは上
述のBose-Chaudhuri-Hocquenghem（ＢＣＨ）手法のサブセットである。この手法では、誤
り訂正符号語が以下の形のジェネレータ多項式により生成される。
【０１０９】
【数１７】
2007265407.tif 000024
【０１１０】
算法はある値ｍに対しｍを法として行なわれる。従ってｍを法とした場合可能なｇi（
ｉ＝１−ｋ）の値は０，１，２，…，ｍ−１である。
【０１１１】
αは多項式の原始成分で、多数のユニークな特性を有する。例えば、α，α2，α3，…
，αm-1はすべてｍを法とした時ユニークであり、ｍを法とした場合ｍ−１数の値しかな
いので、セット｛α，α2，α3，…，αm-1｝と｛１，２，３，…，ｍ−１｝との間には
ユニークな１対１の対応がある。さらに、αkの逆数はαm-kで、逆数の計算が非常に簡単
になる。それ以外は逆数を計算するために拡大ユークリッド・アルゴリズムを用いること
ができる。原始成分を用いた掛け算は指数の合計がαの累乗となる。割り算は指数の差が
αの累乗となる。例えば、α5・α3＝α8で、α7／α3＝α4である。最後に、αm-1＝α0
＝１ ｍｏｄ ｍとなる。
【０１１２】
αの特性は法ｍが素数であるか否かにより挙動が異なる。ｍが素数の場合、対数および
真数表は単に原始多項式を特定の指数に累乗し、その法を取ることにより生成することが
できる。例えばｍが９２９（素数）で原始成分αは３のＰＤＦ４１７の場合（別の２次元
符号）、α7は単に３7（ｍｏｄ ９２９）＝３２９である。さらに、加算および除算は通
常の数学的規則に従う。
【０１１３】
ｍが素数でない場合、原始多項式を判定しなければならない。次数ｑの既約多項式ｐ（
ｘ）はｐ（ｘ）がｘn＋１を割った場合の最小自然数ｎがｎ＝２q−１であれば原始多項式
である。この場合、対数および真数表はこの原始多項式を用いて構成される。例えば、Ｑ
Ｒコードの場合原始多項式はｐ（ｘ）＝ｘ8＋ｘ4＋ｘ3＋ｘ2＋１でαは「２」であるので
、α8＝α4＋α3＋α2＋１＝０００１１１０１＝２９である（注記、αは多項式ｐ（ｘ）
の根である）。別の例ではα10＝α2α8＝α2（α4＋α3＋α2＋１）＝α6＋α5＋α4＋
α2＝01110100＝１１６となる。加算および除算は２つのパラメータに対しＸＯＲ演算を
行なった結果である。
【０１１４】
任意のＱＲコード符号において特定数の誤り訂正符号語が組み入れられている。用いら
れた誤り訂正符号語アルゴリズムは２種類の誤り、すなわち既知の位置における行方不明
または複合不能な符号語である消去、および未知の位置において誤って復号化された符号
語である置換エラーである。
【０１１５】
誤り訂正の仕組みは消去を修正するのに１つの誤り訂正符号語を必要とし、置換エラー
を回復するのに２つの誤り訂正符号語を必要とする。従って、任意数の誤り訂正符号語に
より次の方程式を満足する置換エラーおよび消去の任意の組み合わせを修正することがで
きる。
【０１１６】
【数１８】
2007265407.tif 000025
未知の符号語はゼロで置換され、ｌ番目の未知の符号語の位置はｌ＝１，２，…，ｖに
対しｊlである。
符号文字多項式は次のように構成される。
【０１１７】
【数１９】
2007265407.tif 000026
【０１１８】
ｋシンドローム値Ｓ1からＳkは次を評価することにより計算される。
【０１１９】
【数２０】
2007265407.tif 000027
符号内における未知の符号語の位置はｌ＝１，２，…，ｖに対するｊlから知られてい
るので、これらの知られた位置に対する誤り位置の多項式は演算することができる。
【０１２０】
【数２１】
2007265407.tif 000028
誤り位置の多項式、σ（ｘ）、は誤りの位置を含むように更新することができる。これ
は、当業者であれば理解するであろうように、Berlekamp-Masseyアルゴリズムを用いて行
なうことができる。
この時点で、消去および置換エラーは以前に計算したしかるべき誤り訂正容量を満足す
ることを保証するために確認される。
Solving σ（ｘ）＝０を解くと誤りｔの位置が得られ、ここでｔ＞＝０であり、ｔ＝０
の場合は誤りがない。位置ｊl，１＝１，…，ｖ＋ｔに対する誤り値は演算されなければ
ならない。誤り値を演算するには次で定義される１つの補助多項式が必要である。
【０１２１】
【数２２】
2007265407.tif 000029
位置ｊlにおける誤り値は従って以下により与えられる。
【０１２２】
【数２３】
2007265407.tif 000030
誤り値を得るために解いた後、誤り値の補数が対応位置の符号語に加えられる。
誤りを検出し訂正すると、データビット・ストリームはセグメントに細分化され、各々
のセグメントはモード・インジケータ（４ビットの識別子で次のデータ・シーケンスがど
のモード、すなわち英数文字、数字、バイト、で符号化されているかを示す）で始まり、
モード・インジケータに続く文字カウント・インジケータ（あるモードでデータ・ストリ
ングの長さを定義するビット・シーケンス）で判定される長さを有する（工程６３２）。
各セグメントは次に、当業者であれば容易に理解するであろうように、判定されたモード
に従い復号化される（工程６３４）。
【０１２３】
［復号化例］
上述の方法は図２２に示すデジタル画像のサンプルに適用された。画像は１８０度回転
され、３０度のスキュー・縦揺れを有するＱＲコード符号を含む。入力デジタル画像はＱ
Ｒコード符号から５０ｍｍ離れたカメラで取り込まれた。
【０１２４】
図２３は上述のエッジ・カウント位置確認方法を用いて判定された、ＱＲコード符号を
形成するエッジ・カウント四角形の領域を囲む四辺形を示す。
【０１２５】
図２４は囲まれた領域の閾画像を示す。入力領域の閾値は「８６」であると判定された
。
【０１２６】
図２３において囲まれた領域で５つのファインダ・パターン候補が特定された。以下の
表４は見出された５つのファインダ・パターン候補の中心およびそれらの計算された確信
レベルを含む。
【０１２７】
【表４】
2007265407.tif 000031
【０１２８】
図２５に示すように、上位３つの候補が選ばれた。
入力符号は１行に３７モジュールを有すると判定することによりタイミング・パターン
内のモジュール数が計算され、バージョンはバージョン５であると判定された。
【０１２９】
図２６は配向前のファインダ・パターンＡ，Ｂ，Ｃの初期割り当てを示す。上述のよう
な配向後、ファインダ・パターンＡ，Ｂ，Ｃの割り当ては調節され、図２７に示すように
Ａが左上のファインダ・パターンであると特定された。
【０１３０】
ＱＲコード符号の４つの角Ａco，Ｂco，Ｃco，Ｄcoを推定するために、ファインダ・パ
ターンＡ，Ｃのエッジを用いて左線が形成され、ファインダ・パターンＡ，Ｂのエッジを
用いて上線が、ファインダ・パターンＢのエッジを用いて右線が、ファインダ・パターン
Ｃのエッジを用いて下線が形成された。
【０１３１】
図２８は左、上、右、および下の線を判定するために用いられたファインダ・パターン
Ａ，Ｂ，Ｃの各々の点を示す。
左線について、次の６つのエッジ点が特定された｛(241,202)，(239,193)，(237,182)
，(207,44)，(204,33)，(202,21)｝。最小二乗線合わせ法を用い、左線（Left Line）の
方程式は以下のように判定された。
Left Line、ｙ＝４．６０６９４７ｘ−９０８．７０６５４３
上線（Top Line）について、次の６つのエッジ点が特定された｛(235,210)，(222,209)
，(214,209)，(91,203)，(81,202)，(74,202)｝。最小二乗線合わせ法を用い、上線の方
程式は以下のように判定された。
Top Line、ｙ＝０．０４９４７８ｘ＋１９８．２７１４５４
右線（Right Line）について、次の３つのエッジ点が特定された｛(67,195)，(64,187)
，(61,178)｝。最小二乗線合わせ法を用い、右線の方程式は以下のように判定された。
Right Line、２．８３３３３３ｘ＋５．３３３３３８
下線（Bottom Line）について、次の３つのエッジ点が特定された｛(189,10)，(177,11
)，(167,12)｝。最小二乗線合わせ法を用い、下線の方程式は以下のように判定された。
Bottom Line、−０．０９０６５９ｘ＋２７．１０７１４３
【０１３２】
次に上、左、および下の線の交点を見出すことにより符号の角の位置が判定された。特
に、上線と左線との交点は（242,210）であった。上線と右線との交点は（69,201）であ
った。下線と左線との交点は（199,9）であった。下線と右線との交点は（7,26）であっ
た。
【０１３３】
すべての線を用いれば、図２９に示すように４つの角が特定され得たであろう。図２９
に示されるように、線を用いて符合の角Ｄcoを特定すると誤った結果をもたらす。スキュ
ー・縦揺れにより、最小二乗で合わされた下線および右線は入力ＱＲコード符号の右下の
角で交差しない。しかし４つ目の角を得る上述の方法はこのスキューと縦揺れを考慮に入
れており、４つ目の角を図３０に示すように位置を（10,30）と確認した。
【０１３４】
変換マトリクスを推定するために、入力画像符号の４つの頂点｛(242,210)，(69,201)
，(10,30)，(199,9)｝が用いられた。基準グリッドの行き先の頂点は｛(0,0)，(555,0)，
(555,555)，(0,555)｝であった。変換マトリクスを推定するために以下の線形方程式が解
かれた。
【０１３５】
2007265407.tif 000032
【０１３６】
2007265407.tif 000033
【０１３７】
2007265407.tif 000034
【０１３８】
2007265407.tif 000035
【０１３９】
ＱＲコード符号の上に基準グリッドを形成するためにはまず基準グリッドにおけるモジ
ュールのサイズが知られていなければならない。変換された符号の幅は「５５５」であっ
たので、モジュールの幅は５５５／３７＝１５ピクセルであった。この値を用い、基準グ
リッドが図３２に示されるように形成された。基準グリッドを用いて入力画像空間にグリ
ッドを形成するために、基準グリッドのすべての点（Ｘ，Ｙ）に対し方程式（１４）およ
び方程式（１５）に従って計算が実施された。
【０１４０】
図３３はＱＲコード符号の入力画像上における変換された点を示す。
【０１４１】
基準グリッドの変換された各点においてピクセル値が読み取られグリッド・アレーに格
納された。黒ピクセルは「１」のビット値をもたらし、白ピクセルはゼロのビット値をも
たらした。ビット・ストリームを含んでいたグリッド・アレーを図３４に示す。
【０１４２】
入力画像について、フォーマット情報は「010010010110100」であった。モデル２のマ
スク・パターン「101010000010010」でＸＯＲ演算することにより、「111000010100110」
のパターンが得られた。誤りはなかったため、誤り訂正レベルは「１１」でマスク・パタ
ーン基準は「１００」であり、それにより条件（２ｉ＋３ｊ）ｍｏｄ ２＝０が得られた
。
【０１４３】
モデル２のマスク・パターンが用いられたので、ＱＲコード符号のモデルは「２」であ
った。
【０１４４】
前に推定した１行のモジュール数は「３７」であった。従って、バージョン番号は「５
」であった。バージョン番号が「７」未満であったので、バージョン情報は符号に含まれ
ないと判定された。
【０１４５】
グリッドのマスクを解除するために、条件（２ｉ＋ｊ）ｍｏｄ ２＝０を用いてマスク
解除グリッドが生成された。
【０１４６】
入力画像に対し使用されたマスク解除グリッド・アレーを図３５に示す。図３４にのグ
リッド・アレーにおけるビットを図３５からのマスク解除グリッド・アレーでＸＯＲ演算
することにより、図３６に示すマスク解除されたグリッド・アレーが得られた。
【０１４７】
図３７はバージョン５、モデル２の２ ＱＲコード符号に対する符号語の部分的グリッ
ドを示す。図３７のグリッドにおいて、小数点の前の値は符号語のインデクスを示し、小
数点の後の値は符号語内のビット・インデクスを示す。例えば、１．７はビット値が第１
の符号語と符号語の７つ目のビット（最上位ビット）から来ていることを示す。次の表５
は第１の符号語の形成を示し、これはデシマル値が「６７」であると判定された。
【０１４８】
【表５】
2007265407.tif 000036
【０１４９】
説明されたように符号語の形成を進めた結果、マスク解除されたグリッドから検索され
た符号語は次のとおりであった｛67,194,68,53,4,5,194,53,197,4,194,68,101,52,4,192,
69,146,117,236,68,194,68,17,194,5,197,236,194,4,2,17,4,52,194,236,197,146,4,17,1
00,213,133,236,52,130,53,17,212,194,68,236,245,4,194,17,50,117,194,236,5,17,76,8
2,188,92,188,250,221,21,57,239,36,72,174,202,225,42,241,61,228,222,148,91,224,35
,49,38,43,53,142,234,44,77,111,61,38,150,177,187,207,137,150,250,162,57,138,163,
130,96,157,32,233,190,230,125,138,221,218,94,233,237,78,2,114,224,179,69,194,92,
71,88,213,94｝。
【０１５０】
前記に特定されたＡＩＭ ＱＲコード規格文書によると、誤り訂正レベル１１を有する
バージョン５モデル２のＱＲコードについて符号語は次のように４つのブロックに分けら
れる。
ブロック１データ符号語｛67,4,197,101,69,68,194,194,4,197,100,52,212,245,50｝
ブロック１誤り訂正符号語｛76,188,57,174,241,148,49,142,111,177,150,138,157,230
,218,78,179,71｝
ブロック２データ符号語｛194,5,4,52,146,194,5,4,52,146,213,130,194,4,117｝
ブロック２誤り訂正符号語｛82,250,239,202,61,91,38,234,61,187,250,163,32,125,94
,2,69,88｝
ブロック３データ符号語｛68,194,194,4,117,68,197,2,194,4,133,53,68,194,194,5｝
ブロック３誤り訂正符号語｛188,221,36,225,228,224,43,44,38,207,162,130,233,138,
233,114,194,213｝
ブロック４データ符号語｛53,53,68,192,236,17,236,17,236,17,236,17,236,17,236,17
｝
ブロック４誤り訂正符号語｛92,21,72,42,222,35,53,77,150,137,57,96,190,221,237,2
24,92,94｝
【０１５１】
2007265407.tif 000037
【０１５２】
2007265407.tif 000038
【０１５３】
2007265407.tif 000039
【０１５４】
残りの演算されたシンドロームはＳ1＝Ｓ2＝…＝Ｓ18＝０であった。演算されたシンド
ロームはすべてゼロに等しかったので、ブロックに誤りはなかった。
【０１５５】
2007265407.tif 000040
【０１５６】
2007265407.tif 000041
【０１５７】
演算されたシンドロームは以下となったであろう。
｛Ｓ1，Ｓ2，…，Ｓ18｝＝｛82，26，…，93｝
最終的な誤り位置確認多項式は次のようになったであろう。
σ（ｘ）＝１＋１６０ｘ＋１１１ｘ2
多項式σ（ｘ）の根を見出すにはσ（ｘ）を０に設定して２つの別個の根α224＝１８
およびα225＝３６を得たであろう。このように、２つの誤りが符号語シケンスの３０番
目および３１番目の位置に検出されたことになる。
【０１５８】
誤り値は補助多項式を用いて見出されたであろう。
Ω（ｘ）＝α183ｘ＋α210
補助多項式と誤り位置確認多項式の根を用い、誤り値はｅ30＝１９７およびｅ31＝４と
なったであろう。
誤りは次に符号語シーケンスにおいて訂正されたであろう。
誤り訂正アルゴリズムが符号語の４ブロックすべてに適用された後、図３８に示される
ビット・ストリームが得られた。ビット・ストリームは図３９に示されるように復号化さ
れ、最終的に以下の復号化メッセージが得られた。
「LVTTL，LVCMOS，PCI，PCI-X，GTL，GTLP，HSTL，SSTL」
【０１５９】
図を参照して特定の実施形態が上記に説明された。当業者であれば変更が可能であるこ
とを理解しよう。例えば、図８は左上のファインダ・パターンを特定する別の方法を例示
しており、図７のフローチャートにおいて工程３１０から工程３１６の代わりに用いるこ
とができる。この方法は、図１４に示すとおり３つのファインダ・パターンを結ぶ線が直
角三角形を形成することを活用し、ピタゴラスの定理を用いる。この別の方法の際、各フ
ァインダ・パターンの中心が位置確認され、各々Ａc、Ｂc、およびＣcとラベル付けされ
る（工程３１８）。中心Ａc，Ｂc，Ｃc各々を結ぶ線が次に作成され（工程３２０）、各
線の長さが得られる。中心Ａcと中心Ｂcおよび中心Ａcと中心Ｃcの間に延びる線の長さを
二乗した合計が中心Ｂcと中心Ｃcの間に延びる線の長さを二乗したものに等しい場合（工
程３２２）、中心Ａcは三角形の斜辺に対向する頂点にあるので中心Ａcが左上のファイン
ダ・パターンの中心となる（工程３２４）。等しくない場合、中心Ｂcと中心Ｃcおよび中
心Ａcと中心Ｃcの間に延びる線の長さを二乗した合計が中心Ａcと中心Ｂcの間に延びる線
の長さを二乗したものに等しければ（工程３２６）、中心Ｃcは三角形の斜辺に対向する
頂点にあるので中心Ｃcが左上のファインダ・パターンの中心となる（工程３２８）。等
しくない場合、中心Ｂcと中心Ｃcおよび中心Ａcと中心Ｂcの間に延びる線の長さを二乗し
た合計が中心Ａcと中心Ｃcの間に延びる線の長さを二乗したものに等しければ（工程３２
２）、中心Ｂcは三角形の斜辺に対向する頂点にあるので中心Ｂcが左上のファインダ・パ
ターンの中心となる（工程３２４）。等しくない場合、中心は直角三角形を形成するよう
に配置されていないので、誤りがあることになる。
【０１６０】
上記に説明した実施形態において、ファインダ・パターンＢ，Ｃのラベル付けの確認は
左上のファインダ・パターンを軸に左回りに右上のファインダ・パターンを回転させ、左
下のファインダ・パターンにより近くなったか判定することによって達成される。しかし
当業者は回転の方向は任意であることを理解しよう。右上のファインダ・パターンを右回
りに回転させ、左下のファインダ・パターンより遠くなったか判定するために調べること
ができる。同様に左下のファインダ・パターンを左上のファインダ・パターンを軸に回転
し右上のファインダ・パターンに対するその相対距離を調べてファインダ・パターンのラ
ベル付けを確認することができる。
【０１６１】
実施形態が説明されたが、当業者は添付請求項に定義されるその精神と範囲を逸脱せず
に変更および修正がなされ得る。
【図面の簡単な説明】
【０１６２】
【図１】モデル１ ＱＲコード符号の構造を示す図。
【図２】モデル２ ＱＲコード符号の構造を示す図。
【図３】ＱＲコード符号のファインダ・パターンの詳細構造を示す図。
【図４】デジタル画像におけるＱＲコード符号の位置確認および復号化の際実施される一般的工程を示すフローチャート。
【図５】デジタル画像においてＱＲコード符号の位置確認をする工程を示すフローチャート。
【図６】ＱＲコード符号におけるファインダ・パターンを特定する工程を示すフローチャート。
【図７】ＱＲコード符号を配向する工程を示すフローチャート。
【図８】ＱＲコード符号を配向する別の工程を示すフローチャート。
【図９】ＱＲコード符号を復号化の基準グリッドにマッピングする工程を示すフローチャート。
【図１０】ＱＲコード符号から暗号化されたデータを抽出する工程を示すフローチャート。
【図１１】ＱＲコード符号を含む場面のデジタル画像である。
【図１２】図１１のデジタル画像においてＱＲコード符号の候補である領域の特定を示すデジタル画像である。
【図１３】符号の配向を判定するために選択されたＱＲコード符号のファインダ・パターン点を示す図。
【図１４】ＱＲコード符号のファインダ・パターンにおける中心点を結ぶ線分を示す図。
【図１５】ＱＲコード符号の角を示す図。
【図１６】符号の角の内３つを判定するために選択されたＱＲコード符号のファインダ・パターンのエッジ点を示す図。
【図１７】図１６におけるエッジ点を通り、その交点がＱＲコード符号の左上、左下、および右上の角に生じる線を示す図。
【図１８】ＱＲコード符号の第４の角を判定するために選択されたＱＲコード符号のファインダ・パターンのエッジ点を示す図。
【図１９】図１８のエッジ点を通る線の交点を示す図。
【図２０】ＱＲコード符号の第４の角を判定するために選択された右上および左下各々のファインダ・パターン上のエッジ点を示す図。
【図２１】図２０における点を用いて形成された２つの線の交点を示す図。
【図２２】ＱＲコード符号のファインダ・パターンを含む別の場面のデジタル画像である。
【図２３】図２におけるデジタル画像におけるＱＲコード符号候補の特定を示す。
【図２４】隔離されたＱＲコード符号候補を示す。
【図２５】図２４の隔離されたＱＲコード符号候補における上位３つの候補ファインダ・パターンの中心点を示す。
【図２６】図２５の隔離されたＱＲコード符号におけるファインダ・パターンの最初のラベル付けを示す。
【図２７】図２６のＱＲコード符号におけるファインダ・パターンの配向後の最終ラベル付けを示す。
【図２８】ＱＲコード符号の最初の３つの角を位置確認するために用いるＱＲコード符号の３つのファインダ・パターン上の点を示す。
【図２９】ＱＲコード符号の推定角および不正確な第４の角を示す。
【図３０】ＱＲコード符号の推定角および第４角推定アルゴリズムを用いて得たより正確な第４の角を示す。
【図３１】基準グリッド画像空間に変換されたＱＲコード符号を示す。
【図３２】基準グリッド画像空間における基準グリッドを示す。
【図３３】入力ＱＲコード符号画像空間に変換された基準グリッドを示す。
【図３４】変換されたグリッド点から読み取られたＱＲコード符号のビットのシーケンスを示す。
【図３５】脱マスキング・ビットを示す。
【図３６】図３５の脱マスキング・ビットを用いて脱マスキングされた図３４のビットのシーケンスを示す。
【図３７】バージョン５、モデル２ ＱＲコードの部分的コードワード配置グリッドを示す。
【図３８】ＱＲコード符号のビットの出力シーケンスを示す。
【図３９】図３８のビットの出力シーケンスの復号化の結果を示す。
【図４０】誤り検出および訂正に用いられるログ表の例を示す。
【符号の説明】
【０１６３】
２，１６…ＱＲコード符号、４，２２…セパレータ、６，２４…タイミング・パターン
、８，３０，Ａ，Ｂ，Ｃ…ファインダ・パターン、１２，２８…暗号化領域、１４…拡張
パターン、２６…位置合わせパターン、Ａc，Ｂc…中心、Ａco，Ｂco，Ｃco，Ｄco…角、
ＥB，ＥC…エッジ、ｆ（ｘ）…最良適合曲線、Ｆ，Ｇ…中点、ＬB，ＬC…線、Ｐi…交点
、Ｔ…変換マトリクス、Ｔinverse…逆変換マトリクス。
【図１】
2007265407.tif 000042
【図２】
2007265407.tif 000043
【図３】
2007265407.tif 000044
【図４】
2007265407.tif 000045
【図５】
2007265407.tif 000046
【図６】
2007265407.tif 000047
【図７】
2007265407.tif 000048
【図８】
2007265407.tif 000049
【図９】
2007265407.tif 000050
【図１０】
2007265407.tif 000051
【図１３】
2007265407.tif 000052
【図１４】
2007265407.tif 000053
【図１５】
2007265407.tif 000054
【図１６】
2007265407.tif 000055
【図１７】
2007265407.tif 000056
【図１８】
2007265407.tif 000057
【図１９】
2007265407.tif 000058
【図２０】
2007265407.tif 000059
【図２１】
2007265407.tif 000060
【図２４】
2007265407.tif 000061
【図２５】
2007265407.tif 000062
【図２６】
2007265407.tif 000063
【図２７】
2007265407.tif 000064
【図２８】
2007265407.tif 000065
【図２９】
2007265407.tif 000066
【図３０】
2007265407.tif 000067
【図３１】
2007265407.tif 000068
【図３２】
2007265407.tif 000069
【図３３】
2007265407.tif 000070
【図３４】
2007265407.tif 000071
【図３５】
2007265407.tif 000072
【図３６】
2007265407.tif 000073
【図３７】
2007265407.tif 000074
【図３８】
2007265407.tif 000075
【図３９】
2007265407.tif 000076
【図４０】
2007265407.tif 000077
【図１１】
2007265407.tif 000078
【図１２】
2007265407.tif 000079
【図２２】
2007265407.tif 000080
【図２３】
2007265407.tif 000081