(57)【要約】      （修正有）【課題】２次元コードの位置検出パターンの候補対を識別する方法を提供する。【解決手段】第１の位置検出パターンは、画像のエリアにおいて検出された複数の位置検出パターンから選択される。別の位置検出パターンは、残りの複数の検出された位置検出パターンから選択され、第１の位置検出パターン及び別の位置検出パターンを含む候補対を形成する。候補対について画像のエリア内の除外領域が判定される。別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対は除去される。除外領域に重なる許容ゾーン内の画像のエリアは、許容ゾーンから除去される。２次元コードの位置検出パターンの候補対を識別するために、１つ以上の更に別の位置検出パターンに対してステップを繰り返す。【選択図】図４
2012138079.tif 000002
【特許請求の範囲】
【請求項１】
２次元バーコードの位置検出パターンの候補対を識別する方法であって、
（ｉ）画像のエリアにおいて検出された複数の位置検出パターンから第１の位置検出パターンを選択する工程と、
（ｉｉ）前記検出された複数の位置検出パターンの残りから別の位置検出パターンを選択し、前記第１の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する工程と、
（ｉｉｉ）前記候補対について、前記画像のエリア内で除外領域を決定する工程と、
（ｉｖ）前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する工程と、
（ｖ）前記除外領域に重なっている前記許容ゾーン内のエリアを、前記許容ゾーンから除去する工程と、を有し、
（ｖｉ）前記２次元バーコードの位置検出パターンの前記候補対を識別するために、１つ以上のさらに別の位置検出パターンについて（ｉｉ）〜（ｖ）の工程を繰り返す、
ことを特徴とする方法。
【請求項２】
前記２次元バーコードはクイックレスポンスバーコードである、ことを特徴とする請求項１に記載の方法。
【請求項３】
位置検出パターンの前記候補対をトリプレットに合成する工程を、さらに有することを特徴とする請求項１又は２に記載の方法。
【請求項４】
バーコードの種類に従って前記許容ゾーンを変換する工程を、さらに有することを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記除外領域は、潜在的なクイックレスポンス領域の外部にある位置検出パターンに基づいて判定されることを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
２次元バーコードの位置検出パターンの候補対を識別する装置であって、
画像のエリアにおいて検出された複数の位置検出パターンから第１の位置検出パターンを選択する手段と、
前記複数の検出された位置検出パターンの残りから別の位置検出パターンを選択し、前記第１の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する手段と、
前記候補対について、前記画像のエリア内で除外領域を決定する手段と、
前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する手段と、
前記２次元バーコードの位置検出パターンの前記候補対を識別するために、前記除外領域に重なっている前記許容ゾーン内のエリアを、前記許容ゾーンから除去する手段と、
を備えることを特徴とする装置。
【請求項７】
データ及びコンピュータプログラムを格納するメモリと、前記コンピュータプログラムを実行する、前記メモリに結合されたプロセッサとを備えるコンピュータにおいて２次元バーコードの位置検出パターンの候補対を識別するためのコンピュータプログラムであって、
（ｉ）画像のエリアにおいて検出された複数の位置検出パターンから第１の位置検出パターンを選択する工程と、
（ｉｉ）前記複数の検出された位置検出パターンの残りから別の位置検出パターンを選択し、前記第１の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する工程と、
（ｉｉｉ）前記候補対について、前記画像のエリア内で除外領域を決定する工程と、
（ｉｖ）前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する工程と、
（ｖ）前記除外領域に重なる前記許容ゾーン内のエリアを、前記許容ゾーンから除去する工程と、としてコンピュータを動作させ、
（ｖｉ）前記２次元バーコードの位置検出パターンの前記候補対を識別するために、１つ以上のさらに別の位置検出パターンに対して（ｉｉ）〜（ｖ）の工程を繰り返す、
ことを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元バーコードに関し、特にバーコードの位置検出パターンの候補対を識別する方法及び装置に関する。更に本発明は、バーコードの位置検出パターンの候補対を識別するコンピュータプログラムが記録されたコンピュータ可読媒体を含むコンピュータプログラムに関する。
【背景技術】
【０００２】
２次元バーコードは、１次元バーコードと比較してデータ容量が大きく、且つそのようなバーコードに対する符号化デバイス及び復号化デバイスの利用可能性が高まってきているため、益々普及している。
【０００３】
「クイックレスポンス（ＱＲ）バーコード」として既知である２次元バーコードは、特に一般的な２次元バーコードである。図１は、クイックレスポンスバーコード１００の一例を示す。図１に示されるように、クイックレスポンスバーコード１００は、正方画素の正方配列である。各正方画素は、「モジュール」（例えば、白色モジュール１０１及び黒色モジュール１０２）と呼ばれる。モジュールは、データを符号化するために使用される。
【０００４】
データを符号化するために使用されるモジュールに加え、クイックレスポンスバーコード１００は、３つの場所・識別シンボル１０３を含む。３つの場所シンボル１０３は、それぞれ「位置検出バターン」（ＦＰ）として既知である。図１に示されるように、位置検出パターン１０３は、クイックレスポンスバーコード１００の左上の隅、右上の隅及び左下の隅に配置される。従って、クイックレスポンスバーコードにより占有された画像の２次元エリアは、３つの位置検出バターン１０３の場所により画設される。そのような２次元エリアは、「クイックレスポンスバーコード領域」としても既知である。
【０００５】
クイックレスポンスバーコード１００等のクイックレスポンスバーコードを復号化する第１のステップは、上述の位置検出パターン１０３を使用して入力画像中のバーコード１００を識別することである。
【０００６】
クイックレスポンスバーコードは、製品ラベル、広告掲示板及び名刺等の幅広い媒体上に頻繁に含まれる。従来、そのような媒体は、高品質の単一のクイックレスポンスバーコードのみを含んでいる（すなわち、元のクイックレスポンスバーコードのデジタル画像は、媒体上に正確に再現されている）。従って、クイックレスポンスバーコードが復号化される場合には、取得された画像に単一のクイックレスポンスバーコードのみがあり且つバーコードの品質が高いことが、相対的に単純な復号化処理の使用を容易にする。また、カメラ電話等の従来のクイックレスポンスバーコード撮像デバイスは、クイックレスポンスバーコードの画像が非常に少ない回転位置合わせ誤差で取得されるように、ユーザにより調整される場合がある。ユーザにより調整された撮像デバイスは更に、クイックレスポンスバーコード中のモジュール（例えば、白色モジュール１０１）のサイズが撮像デバイスに対して既知の範囲内にあるように、クイックレスポンスバーコードをフレーム化する。
【０００７】
最近、ドキュメントセキュリティ及びワークフロー管理を支援することにおいて、クイックレスポンスバーコードの活用に対する関心が高まってきている。そのようなアプリケーションの場合、取得された画像中に複数のクイックレスポンスバーコードがある場合がある。更に、画像中のクイックレスポンスバーコードのモジュールのサイズ及び向きは様々である場合が多い。更にクイックレスポンスバーコードは、何度も印刷、スキャン及び再印刷される場合があり、その度にクイックレスポンスバーコードの画像品質が低下する。特に、クイックレスポンスバーコードは、クイックレスポンスバーコード中の黒色モジュールのサイズと白色モジュールのサイズとの比が理想的な１：１から大幅にずれる「ドットゲイン」の影響を受ける可能性が高い。例えば、印刷及びスキャンの複数サイクルにより、位置検出パターン１０３と比較してクイックレスポンスバーコードの位置検出パターンの外観を更に変化させるような他の歪み及びノイズを更に招いてしまう。
【０００８】
クイックレスポンスバーコード復号器のリファレンス実装は、ＩＳＯ／ＩＥＣ１８００４規格で入手可能である。しかしながら、ＩＳＯ／ＩＥＣ１８００４規格におけるリファレンス実装は、画像中にクイックレスポンスバーコードが１つのみであることを仮定し、且つ、ちょうど３つの位置検出パターンが検出されることを仮定している。また、非検出位置検出パターン若しくは偽陽性位置検出パターンは、ＩＳＯ／ＩＥＣ１８００４規格では考慮されない。
【０００９】
非検出位置検出パターンは、ノイズ又は他の歪みの中においてはよく見かけられ、偽陽性位置検出パターンの検出は、特に日本語又は中国語のテキストにおいてはよく見かけられる。従って、位置検出パターンは一旦検出されると、クイックレスポンスバーコードの位置検出パターンを識別するために、「分割される」必要がある。従来、所定の許容範囲内で各々が同一の大きさ及び同一の角度を有する正方形の「Ｌ」字型を形成する位置検出パターンのトリプレットは、位置検出パターンがクイックレスポンスバーコードのものであることを識別するために、検出され且つ分割される必要がある。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】ＩＳＯ／ＩＥＣ１８００４規格
【発明の概要】
【発明が解決しようとする課題】
【００１１】
クイックレスポンスバーコードを識別するように位置検出パターンを分割する１つの方法には、クイックレスポンス規格に準拠するように検出された位置検出パターンの考えられるだけのトリプレットをテストすることが含まれる。そのような方法での実行時間は、解析される位置検出パターン数の三乗で増加するため、この方法は「Ｏ（ｎ３）方法」と呼ばれる。いくつかの応用例においては、Ｏ（ｎ３）方法が受け入れられるであろう。しかしながら、特にクイックレスポンスバーコードの復号化は、限られたメモリ及び処理能力を有する組込み型デバイス上で頻繁に要求されるので、検出された位置検出パターン数が増加するにつれて、Ｏ（ｎ３）方法は非実用的なものになってしまう。
【００１２】
本発明の目的は、既存の構成の１つ以上の欠点を実質的に克服するか、あるいは少なくとも改善することである。
【課題を解決するための手段】
【００１３】
本発明の一態様によると、２次元バーコードの位置検出パターンの候補対を識別する方法であって、
（ｉ）画像のエリアにおいて検出された複数の位置検出パターンから第１の位置検出パターンを選択する工程と、
（ｉｉ）残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第１の位置検出パターン及び別の位置検出パターンを含む候補対を形成する工程と、
（ｉｉｉ）候補対について、画像のエリア内で除外領域を決定する工程と、
（ｉｖ）別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する工程と、
（ｖ）除外領域に重なる許容ゾーン内のエリアを、許容ゾーンから除去する工程と、
（ｖｉ）２次元バーコードの位置検出パターンの候補対を識別するために、１つ以上の更に別の位置検出パターンについて、ステップ（ｉｉ）〜（ｖ）を繰り返す、ことを特徴とする方法が提供される。
【００１４】
本発明の別の態様によると、２次元バーコードの位置検出パターンの候補対を識別する装置であって、
画像のエリアにおいて検出された複数の位置検出パターンから第１の位置検出パターンを選択する手段と、
残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第１の位置検出パターン及び別の位置検出パターンを含む候補対を形成する手段と、
候補対について、画像のエリア内で除外領域を決定する手段と、
別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する手段と、
２次元バーコードの位置検出パターンの候補対を識別するために、除外領域に重なっている許容ゾーン内のエリアを、許容ゾーンから除去する手段とを備える装置が提供される。
【００１５】
本発明の更に別の態様によると、２次元バーコードの位置検出パターンの候補対を識別するシステムであって、
データ及びコンピュータプログラムを格納するメモリと、
コンピュータプログラムを実行するメモリに結合されたプロセッサとを備え、コンピュータプログラムが、
（ｉ）画像のエリアにおいて検出された複数の位置検出パターンから第１の位置検出パターンを選択する命令と、
（ｉｉ）残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第１の位置検出パターン及び別の位置検出パターンを含む候補対を形成する命令と、
（ｉｉｉ）候補対について、画像のエリア内で除外領域を決定する命令と、
（ｉｖ）別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する命令と、
（ｖ）除外領域に重なっている許容ゾーン内の画像のエリアを許容ゾーンから除去する命令と、
（ｖｉ）２次元バーコードの位置検出パターンの候補対を識別するために、１つ以上の更に別の位置検出パターンについて、ステップ（ｉｉ）〜（ｖ）を繰り返す命令とを含むシステムが提供される。
【００１６】
本発明の別の態様によると、上述した方法を実現するコンピュータプログラムを記録したコンピュータ読取可能な媒体を含むコンピュータプログラムが提供される。
【００１７】
本発明の他の態様が更に開示される。
【図面の簡単な説明】
【００１８】
次に、以下の図面を参照して、本発明の１つ以上の実施形態を説明する。
【図１】図１は、黒色モジュール及び白色モジュール、並びに位置検出パターンを含むクイックレスポンスバーコードの一例を示す図である。
【図２Ａ】、
【図２Ｂ】図２Ａ、図２Ｂは、説明される構成が実施される汎用コンピュータシステムの概略ブロック図である。
【図３Ａ】、
【図３Ｂ】、
【図３Ｃ】図３Ａ、３Ｂ、３Ｃは、クイックレスポンスバーコードに対する３つの可能な２／３領域構成を示す図である。
【図４】図４は、バーコードの位置検出パターンの候補対を識別する方法を概略的に示すフローチャートである。
【図５】図５は、各々がネットワークのノードにより表される位置検出パターンの例示的なネットワークの三角形分割を示す図である。
【図６Ａ】図６Ａは、「中心」位置検出パターンの周囲の標準的な許容ゾーンを示す図である。
【図６Ｂ】図６Ｂは、２／３＋許容ゾーンに変換された図６Ａの標準的な許容ゾーンを示す図である。
【図７】図７は、図４の方法で使用されるような中心位置検出パターン及び「候補」位置検出パターンを含む位置検出パターンの一対を解析する方法を概略的に示すフローチャートである。
【図８】図８は、解析される例示的な中心位置検出パターン及び候補位置検出パターンの角度及び大きさを示す図である。
【図９】図９は、候補位置検出パターンにより形成された除外領域に係る許容ゾーンの変形の一例を示す図である。
【図１０Ａ】、
【図１０Ｂ】、
【図１０Ｃ】図１０Ａ、１０Ｂ、１０Ｃは、候補位置検出パターンにより形成された図９の除外領域の変換の一例を示す図である。
【発明を実施するための形態】
【００１９】
添付の図面のうちのいずれか１つ以上において、同一の参照符号を有するステップ及び／又は特徴が参照される。逆の意図が示されない限り、これらのステップ及び／又は特徴は、本明細書の目的のために同一の機能又は動作を有する。
【００２０】
尚、「背景」の節に含まれる説明及び先行技術の構成に関連する上述のものは、それぞれの公表及び／又は用途を介して周知の知識を形成する文書又はデバイスの説明に関連している。そのようなものが本発明者又は本特許出願人により表現されたものとして解釈されるべきではなく、そのような文献又はデバイスは、当技術分野における一般常識の一部を何らかの形で形成するものである。
【００２１】
図４を参照して、バーコードの位置検出パターンの候補対を識別する方法４００を以下に説明する。方法４００は、画像中で検出された位置検出パターンを含む「入力」リストを解析し、一組の候補位置検出パターン対を出力する。出力された位置検出パターン対は、２次元バーコードの部分を形成するのに適した構成である。方法４００は、種々のサイズ又は角度を有する無効な空間関係にある位置検出パターン対を廃棄するステップを実行する。
【００２２】
方法４００は、一般的に２次元バーコードに適用可能である。しかしながら、説明を簡単にするために、クイックレスポンスバーコードを参照して方法４００のステップを説明する。本発明を説明する方法に限定されることを意図するものではない。例えば方法４００は、「ＰＤＦ４１７」バーコード及び「データマトリックス」バーコード等の他のあらゆる種類の２次元バーコードに適用されてもよい。
【００２３】
図２Ａ及び図２Ｂは、説明される種々の構成が実施される際の汎用的なコンピュータシステム２００を示す。
【００２４】
図２Ａに示されるように、コンピュータシステム２００は、コンピュータモジュール２０１、キーボード２０２、マウス・ポインティングデバイス２０３、スキャナ２２６、カメラ２２７及びマイク２８０等の入力デバイス、並びにプリンタ２１５、表示装置２１４及びスピーカ２１７を含む出力デバイスを含む。外部変復調器（モデム）送受信機デバイス２１６は、接続２２１を介して通信ネットワーク２２０と通信するためにコンピュータモジュール２０１により使用されてもよい。通信ネットワーク２２０は、インターネット、セルラ電気通信ネットワーク等のワイドエリアネットワーク（ＷＡＮ）又は専用ＷＡＮであってもよい。接続２２１が電話線である場合、モデム２１６は従来の「ダイヤルアップ」モデムであってもよい。あるいは、接続２２１が大容量（例えば、ケーブル）接続である場合、モデム２１６はブロードバンドモデムであってもよい。無線モデムは、通信ネットワーク２２０に無線接続するために更に使用されてもよい。
【００２５】
コンピュータモジュール２０１は、一般的に、少なくとも１つのプロセッサユニット２０５及びメモリユニット２０６を含む。例えばメモリユニット２０６は、半導体ランダムアクセスメモリ（ＲＡＭ）及び半導体読み出し専用メモリ（ＲＯＭ）を有してもよい。コンピュータモジュール２０１は、ビデオディスプレイ２１４に結合するオーディオ／ビデオインタフェース２０７、スピーカ２１７及びマイク２８０を含む多数の入出力（Ｉ／Ｏ）インタフェース、キーボード２０２、マウス・ポインティングデバイス２０３、スキャナ２２６、カメラ２２７及びオプションとしてジョイスティック又はヒューマンインタフェースデバイス（不図示）に結合するＩ／Ｏインタフェース２１３、並びに外部モデム２１６及びプリンタ２１５用のインタフェース２０８を更に含む。いくつかの実施例において、モデム２１６は、インタフェース２０８等のコンピュータモジュール２０１内に組み込まれてもよい。コンピュータモジュール２０１は、接続２２３を介してコンピュータシステム２００がローカルエリアネットワーク（ＬＡＮ）として既知であるローカルエリア通信ネットワーク２２２に接続できるようにするローカルネットワークインタフェース２１１を更に有する。図２Ａに示されるように、ローカル通信ネットワーク２２２は、一般的にいわゆる「ファイアウォール」デバイス又は同様の機能性を備えたデバイスを含むワイドネットワーク２２０に接続２２４を介して更に結合してもよい。ローカルネットワークインタフェース２１１は、Ｅｔｈｅｒｎｅｔ（登録商標）回路カード、Ｂｌｕｅｔｏｏｔｈ（登録商標）無線装置又はＩＥＥＥ８０２．１１無線装置を備えてもよいが、多数の他の種類のインタフェースがインタフェース２１１に対して実施されてもよい。
【００２６】
Ｉ／Ｏインタフェース２０８及び２１３は、直列接続性及び並列接続性のいずれか一方又は双方を提供してもよい。一般的に直列接続性は、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格に従って実現され且つ対応するＵＳＢコネクタ（不図示）を有する。記憶装置２０９が提供され、一般的に記憶装置２０９は、ハードディスクドライブ（ＨＤＤ）２１０を含む。フロッピディスクドライブ及び磁気テープドライブ（不図示）等の他の記憶装置が更に使用されてもよい。オプションのディスクドライブ２１２は、一般的に、データの不揮発性ソースとして動作するように提供される。例えば、光ディスク（例えば、ＣＤ−ＲＯＭ、ＤＶＤ、Ｂｌｕ−ｒａｙ  Ｄｉｓｃ（登録商標））、ＵＳＢ−ＲＡＭ、取り外し可能な外部ハードドライブ及びフロッピディスク等のポータブルメモリ装置は、システム２００に対する適切なデータソースとして使用されてもよい。
【００２７】
コンピュータモジュール２０１の構成要素２０５〜２１３は、一般的に、相互接続バス２０４を介して通信し、且つ結果として当業者に既知であるコンピュータシステム２００の動作の従来のモードから得られる方法で通信する。例えばプロセッサ２０５は、接続２１８を使用してシステムバス２０４に結合される。同様に、メモリ２０６及び光ディスクドライブ２１２は、接続２１９によりシステムバス２０４に結合される。説明する構成が実施されるコンピュータの例には、ＩＢＭ−ＰＣ’ｓ及び互換性のあるもの、Ｓｕｎ  Ｓｐａｒｃｓｔａｔｉｏｎｓ、Ａｐｐｌｅ  Ｍａｃ（登録商標）又は同様のコンピュータシステムが含まれる。
【００２８】
方法４００を含む以下に説明する方法は、コンピュータシステム２００を使用して実現されてもよい。方法において説明される図３Ａ〜図１０Ｃの処理は、コンピュータシステム２００内で実行可能な１つ以上のソフトウェアアプリケーションプログラム２３３として実現されてもよい。特に、説明される方法のステップは、コンピュータシステム２００内で実行されるソフトウェア２３３で命令２３１（図２Ｂを参照）により実施される。ソフトウェア命令２３１は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されてもよい。ソフトウェアは２つの別個の部分に更に分割されてもよく、第１の部分及び対応するコードモジュールは説明する方法を実行し、第２の部分及び対応するコードモジュールは、第１の部分とユーザとの間のユーザインタフェースを管理する。
【００２９】
例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読取可能な媒体に格納されてもよい。ソフトウェアは、コンピュータ読取可能な媒体からコンピュータシステム２００にロードされ、コンピュータシステム２００により実行される。そのようなソフトウェアを有するコンピュータ読取可能な媒体又はコンピュータ読取可能な媒体上に記録されたコンピュータプログラムは、コンピュータプログラム製品である。コンピュータシステム２００においてコンピュータプログラムを使用することにより、説明する方法を実現する有利な装置を実施するのが好ましい。
【００３０】
ソフトウェア２３３は、一般的にＨＤＤ２１０又はメモリ２０６に格納される。ソフトウェアは、コンピュータ読取可能な媒体からコンピュータシステム２００にロードされ、コンピュータシステム２００により実行される。従って、例えばソフトウェア２３３は、光ディスクドライブ２１２により読み出される光学的に読出可能なディスク記憶装置媒体（例えば、ＣＤ−ＲＯＭ）２２５上に格納されてもよい。そのようなソフトウェアを有するコンピュータ読取可能な媒体又はコンピュータ読取可能な媒体上に記録されたコンピュータプログラムは、コンピュータプログラム製品である。コンピュータシステム２００においてコンピュータプログラム製品を使用することにより、説明する方法を実現する装置を実施するのが好ましい。
【００３１】
いくつかの例において、アプリケーションプログラム２３３は、１つ以上のＣＤ−ＲＯＭ２２５上でユーザが符号化したものに供給され且つ対応するドライブ２１２を介して読み出されてもよく、あるいはユーザによりネットワーク２２０又は２２２から読み出されてもよい。更にソフトウェアは、他のコンピュータ読取可能な媒体からコンピュータシステム２００にロードされてもよい。コンピュータ読取可能な記憶媒体は、実行及び／又は処理するために、記録された命令及び／又はデータをコンピュータシステム２００に提供するあらゆる非一過性（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ）の有形（ｔａｎｇｉｂｌｅ）の記憶媒体を示す。そのような記憶媒体の例には、フロッピディスク、磁気テープ、ＣＤ−ＲＯＭ、ＤＶＤ、Ｂｌｕ−ｒａｙ  Ｄｉｓｃ、ハードディスクドライブ、ＲＯＭ又は集積回路、ＵＳＢメモリ、光磁気ディスク、あるいは例えばＰＣＭＣＩＡカード等のコンピュータ読取可能なカードが含まれ、そのようなデバイスは、コンピュータモジュール２０１の内部又は外部にある。ソフトウェア、アプリケーションプログラム、命令及び／又はデータをコンピュータモジュール１０１に提供することに更に関連してもよい一過性又は非一過性のコンピュータ読取可能な伝送媒体の例には、無線送信チャネル又は赤外線送信チャネル及び別のコンピュータ又はネットワーク化されたデバイスへのネットワーク接続、並びに電子メール送信及びウェブサイト上等に記録された情報を含むインターネット又はイントラネットが含まれる。
【００３２】
上述したアプリケーションプログラム２３３の第２の部分及び対応するコードモジュールは、ディスプレイ２１４上にレンダリングされるか若しくは表される１つ以上のグラフィカルユーザインタフェース（ＧＵＩ）を実現するように実行されてもよい。一般的にキーボード２０２及びマウス・ポインティングデバイス２０３を操作することにより、コンピュータシステム２００及びアプリケーションのユーザは、ＧＵＩと関連付けられたアプリケーションに制御コマンド及び／又は入力を提供するように機能的に適応可能な方法でインタフェースを操作してもよい。他の形式の機能的に適応可能なユーザインタフェース、例えばスピーカ２１７を介して出力された音声プロンプト及びマイク２８０を介して入力されたユーザ音声コマンドを利用するオーディオインタフェースが更に実現されてもよい。
【００３３】
図２Ｂは、プロセッサ２０５及び「メモリ」２３４を示す詳細な概略ブロック図である。メモリ２３４は、図２Ａのコンピュータモジュール２０１によりアクセスされる全てのメモリモジュール（ＨＤＤ２１０及び半導体メモリ２０６を含む）の論理的な集約を示す。
【００３４】
コンピュータモジュール２０１が最初に電源投入される場合、自己診断（ＰＯＳＴ）プログラム２５０が実行される。一般的にＰＯＳＴプログラム２５０は、図２Ａの半導体メモリ２０６のＲＯＭ２４９に格納される。ソフトウェアを格納するＲＯＭ２４９等のハードウェアデバイスは、ファームウェアと呼ばれる場合もある。ＰＯＳＴプログラム２５０は、コンピュータモジュール２０１内のハードウェアを調査して適切に機能することを保証し、一般的に、正しく動作するためにＲＯＭ２４９に更に格納されたプロセッサ２０５、メモリ２３４（２０９、２０６）及び基本入出力システム（ＢＩＯＳ）ソフトウェアモジュール２５１をチェックする。ＰＯＳＴプログラム２５０が正常に実行されると、ＢＩＯＳ２５１は図２Ａのハードディスクドライブ２１０を起動する。ハードディスクドライブ２１０を起動することにより、ハードディスクドライブ２１０上に常駐するブートストラップ・ローダプログラム２５２がプロセッサ２０５を介して実行される。これにより、オペレーティングシステム２５３は、ＲＡＭメモリ２０６にロードされると動作を開始する。オペレーティングシステム２５３は、プロセッサ２０５により実行可能なシステムレベルのアプリケーションであり、プロセッサ管理、メモリ管理、デバイス管理、ストレージ管理、ソフトウェアアプリケーションインタフェース及び汎用ユーザインタフェースを含む種々のハイレベルな機能を遂行する。
【００３５】
オペレーティングシステム２５３は、メモリ２３４（２０９、２０６）を管理し、コンピュータモジュール２０１上で実行する処理又はアプリケーションの各々が別の処理に割り当てられたメモリと衝突することなく実行するだけの十分なメモリを有することを保証する。また、図２Ａのシステム２００で使用可能な種々のメモリは、各処理が効率的に実行するように適切に使用される必要がある。従って、集約メモリ２３４は、メモリの特定の部分が割り当てられる方法を示すことを意図せず（明示的に記載されない限り）、コンピュータシステム２００によりアクセス可能なメモリの概略図及びそのようなメモリが使用される方法を提供する。
【００３６】
図２Ｂに示されるように、プロセッサ２０５は、制御ユニット２３９、演算論理装置（ＡＬＵ）２４０及びキャッシュメモリと呼ばれることもあるローカルメモリ又は内部メモリ２４８を含む多数の機能モジュールを含む。一般的にキャッシュメモリ２４８は、レジスタ部に複数の記憶レジスタ２４４〜２４６を含む。１つ以上の内部バス２４１は、これらの機能モジュールを機能的に相互接続する。一般的にプロセッサ２０５は、接続２１８を使用してシステムバス２０４を介して外部デバイスと通信する１つ以上のインタフェース２４２を更に有する。メモリ２３４は、接続２１９を使用してバス２０４に結合される。
【００３７】
アプリケーションプログラム２３３は、条件付き分岐命令及びループ命令を含んでもよい一連の命令２３１を含む。プログラム２３３は、プログラム２３３を実行するのに使用されるデータ２３２を更に含んでもよい。命令２３１及びデータ２３２は、それぞれ、記憶場所２２８、２２９、２３０及び２３５、２３６、２３７に格納される。命令２３１及びメモリの記憶場所２２８〜２３０の相対的なサイズに依存して、特定の命令は、記憶場所２３０に示された命令により描かれるように単一の記憶場所に格納されてもよい。あるいは、命令は、メモリの記憶場所２２８及び２２９に示される命令部分により描かれるように、各々が別個のメモリの記憶場所に格納される多数の部分に分割されてもよい。
【００３８】
一般的にプロセッサ２０５は、そこで実行される命令の集合を与えられる。プロセッサ２０５は、命令の別の集合を実行することによりプロセッサ２０５自身が反応する後続の入力を待つ。各入力は、入力デバイス２０２、２０３の１つ以上により生成されたデータ、ネットワーク２２０、２２２のうちの一方を介して外部ソースから受信したデータ、記憶装置２０６、２０９のうちの一方から検索したデータ又は対応する読取装置２１２に挿入された記憶媒体２２５から検索したデータを含む多数のソースのうちの１つ以上から提供されてもよく、その全てが図２Ａに示されたものである。いくつかの例において、命令の集合を実行した結果、データが出力されてもよい。実行することは、データ又は変数をメモリ２３４に格納することを更に含んでもよい。
【００３９】
説明する方法は、対応するメモリの記憶場所２５５、２５６、２５７においてメモリ２３４に格納される入力変数２５４を使用する。説明する方法は、対応するメモリの記憶場所２６２、２６３、２６４においてメモリ２３４に格納される出力変数２６１を生成する。中間変数２５８は、メモリの記憶場所２５９、２６０、２６６及び２６７に格納されてもよい。
【００４０】
図２Ｂのプロセッサ２０５を参照すると、レジスタ２４４、２４５、２４６、演算論理装置（ＡＬＵ）２４０及び制御ユニット２３９は、プログラム２３３を構成する命令集合において命令毎に「取り込み、復号化及び実行」サイクルを実行するのに必要なマイクロ動作のシーケンスを実行するように共に動作する。取り込み、復号化及び実行サイクルの各々は、
（ａ）メモリの記憶場所２２８、２２９、２３０からの命令２３１を取り込むかあるいは読み取る取り込み動作、
（ｂ）制御ユニット２３９が、取り込まれた命令を判定する復号化動作、並びに
（ｃ）制御ユニット２３９及び／又はＡＬＵ２４０が命令を実行する命令動作を含む。
【００４１】
その後、次の命令に対する更なる取り込み、復号化及び実行サイクルが実行されてもよい。同様に、制御ユニット２３９が値をメモリの記憶場所２３２に格納するかあるいは書き込むことにより、格納サイクルが実行されてもよい。
【００４２】
図４〜図１０の処理におけるステップ又はサブ処理の各々は、プログラム２３３の１つ以上の部分と関連付けられ、プログラム２３３の示された部分に対して命令集合の命令毎に取り込み、復号化及び実行サイクルを実行するようにプロセッサ２０５のレジスタ部２４４、２４５、２４７、ＡＬＵ２４０と制御ユニット２３９が共に動作することにより実行される。
【００４３】
あるいは、説明される方法は、説明される方法の機能又はサブ機能を実行する１つ以上の集積回路等の専用ハードウェアで実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ又は１つ以上のマイクロプロセッサ及び関連付けられたメモリを含んでもよい。
【００４４】
以下に詳細に説明するように、検出された位置検出パターンを可能な２次元バーコードに分割（ｒｅｓｏｌｖｅ）するＯ（ｎ３）方法は、位置検出パターンのトリプレットではなく、位置検出パターンの「候補対」を決定するように変更されてもよい。位置検出パターンの候補対の各々は、以下において「２／３領域」と呼ばれるものを形成する。対応するクイックレスポンスバーコードの３つの位置検出パターンのうちの２つが検出されるため、候補対は２／３領域と呼ばれる。
【００４５】
図３Ａ、図３Ｂ及び図３Ｃに示されるように、クイックレスポンスバーコード１００に対して３つの可能な２／３領域構成がある。図３Ａは、位置検出パターン１０３の第１の検出パターン３１０が位置検出パターン１０３の第２の位置検出パターン３２０とはす向かいの位置関係になっている場所に形成された「２／３／」領域３０１を示す。図３Ｂは、位置検出パターン１０３の２つの位置検出パターン３１０及び３３０が互いに隣接し、且つ対応するクイックレスポンスバーコード１００が第２の位置検出パターン３３０から時計回りの方向に形成された場合の「２／３＋」領域３０２を示す。図３Ｃは、位置検出パターン１０３の２つの位置検出パターン３１０及び３４０が互いに隣接し、且つクイックレスポンスバーコード１００が第２の位置検出パターン３４０から反時計回りの方向に形成された場合の「２／３−」領域３０３を示す。
【００４６】
図３Ｂ及び図３Ｃに示されるように、２／３＋領域３０２及び２／３−領域３０３は、それぞれ、位置検出パターンの同一の構成を有する。しかしながら、以下に詳細に説明するように、許容ゾーンに対して位置検出パターンの一対をテストする際に２／３＋領域の種類及び２／３−領域の種類のうちのいずれか一方又はその双方が適用可能であってもよく、あるいはそのいずれも適用可能でなくてもよいため、２／３＋領域３０２及び２／３−領域３０３は別個に考慮される。
【００４７】
以下に詳細に説明するように、重複する２／３領域同士が完全な３／３クイックレスポンス領域を形成するようにマージされる（あるいは、組み合わされる）場合、位置検出パターン（例えば、位置検出パターン３１０及び３３０）の候補対からのクイックレスポンスバーコード１００の方向は、更に重要である。説明するように、プロセッサ２０５は、位置検出パターンの候補対をトリプレットに合成するステップを実行してもよい。
【００４８】
図４を参照して、バーコードの位置検出パターンの候補対を識別する方法４００を以下に説明する。方法４００は、ハードディスクドライブ２１０上に常駐し且つ実行中にプロセッサ２０５により制御されるソフトウェアアプリケーションプログラム２３３のソフトウェアコードモジュールの１つとして実現されてもよい。画像の１つのエリアにおいて検出される位置検出パターンの「入力」リストが与えられたとすると、方法４００は、画像のエリアにおいて２／３領域（例えば、領域３０１、３０２、又は３０３）を識別する。位置検出パターンの入力リストは、画像のエリアにおいて検出される複数の位置検出パターンを含む。検出される位置検出パターンを含む入力リストは、メモリ２０６又はハードディスクドライブ２１０からアクセスされるようにしてもよい。図１のクイックレスポンスバーコード１００及び位置検出パターンのネットワーク５００（図５を参照）を参照しながら、方法４００を説明する。
【００４９】
第１の「リスト作成」ステップ４０５において、プロセッサ２０５は、メモリ２０６又はハードディスクドライブ２１０内に２／３領域の空リストを作成するステップを実行する。方法４００の後に続くステップ中で識別される全ての有効な２／３領域は、２／３領域のリストに連続して追加される。２／３領域のリストは、メモリ２０６又はハードディスクドライブ２１０からアクセスされるようにしてもよい。
【００５０】
「ネットワーク生成」ステップ４１０において、位置検出パターンのネットワーク５００（図５を参照）がプロセッサ２０５により生成される。図５の例における各位置検出パターン（例えば、位置検出パターン５１０）は、黒丸として示される。位置検出パターンのネットワーク５００は、メモリ２０６に格納されるようにしてもよい。生成されたネットワーク５００の各位置検出パターンは、直線「エッジ」（例えば、エッジ５２０）により結合される。
【００５１】
ネットワーク５００は、ドロネー三角形分割を使用してステップ４１０で生成される。あらゆる適切なＯ（ｎｌｏｇｎ）方法がドロネー三角形分割を実行するために使用されてもよい。
【００５２】
ドロネー三角形分割は、以下の望ましい特性を有する。
【００５３】
１．各ノード（即ち、位置検出パターンを表す）に接続されたエッジの平均数が６未満である。
【００５４】
２．位置検出パターンを表す各ノードが別の位置検出パターンを表す最も近接する隣接ノードに接続される。
【００５５】
３．一般的に、位置検出パターンを表す各ノードが、Ｏ（ｌｏｇｋ）エッジにより他の位置検出パターンを表すｋ番目に最も近接する隣接ノードに接続される。
【００５６】
位置検出パターンを表す所定のノードから開始するネットワーク５００のエッジを行き来することによって、ドロネー三角形分割は結果として、隣接位置検出パターンを表す隣接ノードを迅速に配置するために使用される場合がある。
【００５７】
ステップ４１０の後、方法４００の次のステップ４２０〜４９０は、可能な２／３領域（例えば、領域３０１、３０２、３０３）を繰り返して識別する。ステップ４２０〜４９０において、プロセッサ２０５は、順次、「中心」位置検出パターン（又はノード）としてメモリ２０６に格納された入力リストの位置検出パターンの各々を選択するステップを実行する。上述したように、位置検出パターンの入力リストは、画像のエリアにおいて検出された複数の位置検出パターンを含む。検出された位置検出パターンを含む入力リストは、メモリ２０６又はハードディスクドライブ２１０からアクセスされるようにしてもよい。
【００５８】
ステップ４２０〜４９０において、プロセッサ２０５は、解析するために位置検出パターンの候補対を決定するステップを更に実行する。位置検出パターンの候補対は、ネットワーク５００により示されるように、選択された中心位置検出パターンを、入力リストの残りの隣接位置検出パターンのうち少なくとも１つと連続して組み合わせることによって決定される。
【００５９】
「選択」ステップ４２０において、まだ考慮されていない入力リストの次の（又は方法４００の最初の繰り返しにおける第１の）位置検出パターンは、中心位置検出パターン（又は中心ノード）としてプロセッサ２０５により選択される。上述したように、選択された位置検出パターンは、画像のエリア（又は、第１のエリア）において検出された複数の位置検出パターンを含む位置検出パターンの入力リストから選択される。
【００６０】
中心位置検出パターンが与えられたとして、有効な２／３領域（例えば、領域３０１、３０２、３０３）を規定する位置検出パターンの一対を形成してもよい隣接位置検出パターンの識別は、「許容ゾーン」を使用することによって迅速化される。許容ゾーンは、隣接位置検出パターンがある画像の部分集合を規定しており、中心位置検出パターンと一対を成す有効な位置検出パターンを潜在的に形成する。
【００６１】
次に、図６Ａを参照する。次のステップ４３０において、中心位置検出パターン６３０と一対になって２／３／領域（例えば、領域３０１）を形成可能な隣接位置検出パターンが許容されるゾーン６００（即ち、「許容ゾーン」）は、プロセッサ２０５により初期化される。以下に説明するように、２／３＋領域の例及び２／３−領域の例について対応するエリアが２／３／領域の例から導出されてもよいので、２／３＋領域及び２／３−領域それぞれに対応する別個の許容ゾーンを必要としない。以下の説明において、２／３／領域許容ゾーン６００を「標準的な許容ゾーン」と呼ぶ。
【００６２】
一実施例において、標準的な許容ゾーン６００は、セクタの連結リストとしてメモリ２０６内に格納される。各セクタは、特定の角度範囲内で中心位置検出パターン６３０から隣接位置検出パターンの最長許容距離を規定している。セクタは、角度において単調に大きくなっており、０°〜３６０°の全角度に渡っている。
【００６３】
標準的な許容ゾーン６００は、８つのセクタとして初期化される。４つのセクタ（例えば、セクタ６１０）は、中心位置検出パターン６３０に関して対角線状に位置合わせされる。対角線状に位置合わせされたセクタ（例えば、セクタ６０１）の最大半径は、中心位置合わせパターン６３０のサイズ及び大きさの許容範囲を与えるクイックレスポンスバーコード（例えば、クイックレスポンスバーコード１００）の最大サイズにより規定される。例えば、適切な大きさの許容範囲は２０％である。４つのセクタ（例えば、セクタ６１０）の幅は、所定の角度の許容範囲により規定される。適切な角度の許容範囲は、例えば２０度である。
【００６４】
４つの対角線状に位置合わせされたセクタ（例えば、セクタ６１０）に加え、初期の標準的な許容ゾーン６００は、半径ゼロで介在する４つのセクタ（不図示）を含む。
【００６５】
再度図４に戻ると、ステップ４３０の後、方法４００は「リスト」ステップ４４０に進む。ステップ４４０において、位置検出パターンの「候補」リストは、プロセッサ２０５により確立されてメモリ２０６に格納される。以下に詳細に説明するように、候補リストにおける連続的な位置検出パターンは、選択された中心位置検出パターンと組み合わされる。例えば、結果として得られる位置検出パターンの一対は、結果として得られる位置検出パターンの一対がクイックレスポンスバーコード１００に対して有効な２／３領域を規定するかを決定するように評価される。
【００６６】
候補リストは、先に決定されたドロネー三角形分割に係る中心位置検出パターンの隣接位置検出パターンの各々を含んでいる。
【００６７】
候補リストにおいて各位置検出パターンの「親」位置検出パターンとして参照される位置検出パターンも、ステップ４４０においてメモリ２０６に格納される。特定の候補位置検出パターンの親は、候補位置検出パターンを候補リストに追加した位置検出パターンである。最初の、中心位置検出パターンは、位置検出パターンの候補リストにおいて全ての位置検出パターンの親である。
【００６８】
しかしながら、ステップ４７０で実行されるように、「他の」位置検出パターンの隣接位置検出パターンが候補リストに追加されるようにしてもよい。この例において、これらの「他の」位置検出パターンも親位置検出パターンになる。
【００６９】
「選択」ステップ４５０において、プロセッサ２０５は、メモリ２０６に格納された候補リストから任意の（又は第２の）位置検出パターンを「候補位置検出パターン」として選択するステップを実行する。ステップ４５０で選択された候補位置検出パターン及びステップ４２０で選択された中心位置検出パターンは、共に「候補対」を形成する。従って、位置検出パターンはステップ４５０で候補リストにおいて検出された残りの複数の位置検出パターンから選択され、ステップ４２０で選択された位置検出パターン及びステップ４５０で選択された位置検出パターンを含む候補対を形成する。
【００７０】
後続するステップ４６０及び４７０において、以下に説明するように、プロセッサ２０５は、２／３領域の種類毎に、ステップ４５０で選択した候補位置検出パターンが許容ゾーンにあるか、許容ゾーンにあるのであれば、位置検出パターンの候補対がそのような種類の有効な２／３領域を規定しているかを判定するステップを実行する。以下に更に詳細に説明するように、ステップ４７０において、プロセッサ２０５は、候補位置検出パターンを占めるように許容ゾーンを変更するステップを更に実行する。
【００７１】
特に、ステップ４５０の後、方法４００はステップ４６０に進み、プロセッサ２０５は、中心位置検出パターンと候補位置検出パターンを含む位置検出パターンの候補対を解析し、どのような有効な２／３領域の種類（例えば、領域３０１、３０２、３０３）が位置検出パターンの候補対から形成されるかを決定する。
【００７２】
図７を参照して、ステップ４６０で実行されたように位置検出パターンの一対を解析する方法７００を以下に詳細に説明する。方法７００は、ハードディスクドライブ２１０上に常駐し且つ実行中にプロセッサ２０５により制御されるソフトウェアアプリケーションプログラム２３３の１つ以上のコードモジュールとして実現されてもよい。
【００７３】
説明のために、図５の例示的なネットワーク５００を参照して方法７００を説明する。位置検出パターン５１０を中心位置検出パターンであるとすると、ステップ４６０の開始時の候補リストは、最初に候補リストに追加される隣接位置検出パターン５３０、５４０及び５５０を含み、位置検出パターン５３０が第１の候補位置検出パターンとして選択される。
【００７４】
図７のステップ７１０〜７７０は、クイックレスポンス２／３領域の３つの種類（すなわち、図３Ａ〜図３Ｃを参照して上述したような、２／３−領域３０３、２／３＋領域３０２及び２／３／領域３０１のそれぞれ）に渡って反復される。
【００７５】
「選択」ステップ７１０において、繰り返しの始めについて領域の種類（例えば、３０１、３０２、３０３）がプロセッサ２０５により選択される。選択された領域の種類の詳細は、メモリ２０６内に更に格納されてもよい。
【００７６】
「変換」ステップ７２０において、ステップ４３０で初期化された標準的な許容ゾーン６００は、選択された２／３クイックレスポンス領域の種類に従って変換される。特に、選択されたクイックレスポンス領域の種類が２／３／領域３０１である場合には、これが標準的な許容ゾーン６００であるため変換は必要ない。しかしながら、選択されたクイックレスポンス領域の種類が２／３＋領域３０２である場合には、標準的な許容ゾーン６００は、標準的な許容ゾーン６００を１／√２で変倍して４５°反時計回りに回転させることにより、２／３＋許容ゾーンに変換される。
【００７７】
図６Ｂは、初期の標準的な許容ゾーン６００の変形バージョン６２０を示す。図６Ｂに示されるように、標準的な許容ゾーン６００は、標準的な許容ゾーン６００を１／√２で変倍して４５°反時計回りに回転させることにより変換され、変形バージョン６２０を生成している。変換された後、位置検出パターンは、中心位置検出パターン６３０の主軸に近接することを許可されるのみである。
【００７８】
あるいは、選択されたクイックレスポンス領域の種類が２／３−領域３０３である場合には、標準的な許容ゾーン６００は、標準的な許容ゾーン６００を１／√２で変倍して４５°だけ時計回りに回転させることにより、２／３−許容ゾーンに変換される。
【００７９】
「決定」ステップ７３０において、プロセッサ２０５は、中心位置検出パターン（例えば、６３０）から候補位置検出パターンへのベクトルを決定する。決定されたベクトルは、候補位置検出パターンが中心ノード（例えば、中心位置検出パターン６３０）の変換された許容ゾーン（例えば、変形バージョン６２０）内にあるかを判定するために使用される。候補位置検出パターンが中心ノード（例えば、中心位置検出パターン６３０）の変換された許容ゾーン（例えば、変形バージョン６２０）内にあるとプロセッサ２０５が判定した場合、方法７００は「決定」ステップ７４０に継続する。そうでなければ、方法７００は「決定」ステップ７５０に進む。
【００８０】
「決定」ステップ７４０において、中心位置検出領域及び候補位置検出領域（即ち、候補対）が有効な２／３領域の一対を規定している（即ち、候補対はクイックレスポンスバーコードに対応している）とプロセッサ２０５が判定した場合、方法７００はステップ７６０に進む。さもなければ、方法７００はステップ７７０に進む。
【００８１】
位置検出パターンの候補対の有効性は、中心位置検出パターン及び候補位置検出パターンの角度及びサイズを調査することに基づいて判定される。図８は、例示的な中心位置検出パターン８１０及び候補位置検出パターン８２０を示す。図示されるように、位置検出パターン８１０及び８２０の角度は、それぞれ、θ１及びθ２である。位置検出パターン８１０及び８２０の幅は、それぞれ、Ｗ１及びＷ２である。２つの位置検出パターン８１０及び８２０の角度θ１及びθ２、並びに幅Ｗ１及びＷ２が、所定の許容範囲内で同一である場合には、２／３領域の一致が確立されており、位置検出パターン８１０及び８２０は、有効な一対を規定している（即ち、位置検出パターン８１０及び８２０は、潜在的なクイックレスポンスバーコードに対応している）。角度について適切な所定の許容範囲は１０度である。大きさについて適切な所定の許容範囲は２０％である。
【００８２】
位置検出パターン８１０及び８２０の一対が有効な２／３領域（例えば、領域３０１、３０２、３０３）を規定している場合、候補対及び領域の種類を含む潜在的な領域は、「追加」ステップ７６０において、先にステップ４５０で作成された２／３領域のリストに追加される。上述したように、２／３領域のリストは、メモリ２０６又はハードディスクドライブ２１０内に格納されるようにしてもよい。
【００８３】
「追加」ステップ７７０において、中心位置検出パターンではなく、候補リストになく、且つ以前に中心位置検出パターンに対する候補位置検出パターンではなかった候補位置検出パターンの全ての隣接位置検出パターンが、メモリ２０６内に格納された候補リストに追加される。候補位置検出パターンの隣接位置検出パターンが中心位置検出パターンと有効な２／３領域の一対を更に形成してもよいので、ステップ７７０が実行される。ステップ７７０において候補リストに追加される各位置検出パターンの親位置検出パターンとして、現在の候補位置検出パターンがメモリ２０６内に格納されている。
【００８４】
図５の先の例に戻ると、位置検出パターン５１０が中心位置検出パターンであり、且つ位置検出パターン５３０が候補位置検出パターンである場合、ステップ７７０において、位置検出パターン５６０及び５７０が候補リストに追加され、位置検出パターン５１０は中心位置検出パターンであり、位置検出パターン５４０及び５５０は既に候補リストに追加されている。
【００８５】
ステップ７７０の後、方法７００は「決定」ステップ７８０に進む。
【００８６】
ステップ７３０において候補位置検出パターンが中心ノード６３０の変換された許容ゾーン６２０内にないとプロセッサ２０５が判定した場合には、方法７００はステップ７５０に進む。ステップ７５０において、プロセッサ２０５は、候補位置検出パターンの隣接位置検出パターンがメモリ２０６内に構成された候補リストに追加されるべきであるかを判定する。特に、プロセッサ２０５は、現在の候補位置検出パターンの親位置検出パターンと候補位置検出パターンとの間のエッジ（境界）を、変換された許容ゾーン６２０により規定される許容領域の境界と比較するステップを実行する。変換された許容ゾーン６２０により規定される許容領域境界にエッジが交差する場合には、方法７００は上述したステップ７７０に進み、現在の候補位置検出パターンの隣接位置検出パターンが、メモリ２０６内に構成された候補リストに追加される。
【００８７】
また、変換された許容ゾーン６２０により規定される許容領域境界にエッジが交差しない場合には、処理はステップ７８０に進み、隣接位置検出パターンは候補リストに追加されない。
【００８８】
エッジが許容領域境界に交わる場合にのみ無効の位置検出パターンの隣接位置検出パターンを追加することは、変換された許容ゾーン６２０により規定される許容領域の外側で探索が２つのステップのみ進む以外は、許容領域の内側の全ての位置検出パターンが発見されることを保証する。
【００８９】
もう１度図５の例を考慮すると、位置検出パターン５１０が中心位置検出パターンである場合、位置検出パターン５７０は候補位置検出パターンであり且つ位置検出パターン５３０はその候補位置検出パターンの親であり、位置検出パターン５３０から位置検出パターン５７０へのパスが調べられる。親位置検出パターン５３０が位置検出パターン５１０の許容ゾーンにあり且つ候補位置検出パターン５７０が位置検出パターン５１０の許容ゾーンの外側にある場合、方法７００はステップ７８０に進む。そうでなければ、方法７００はステップ７７０に進む。
【００９０】
繰り返しの最後の「決定」ステップ７８０において、テストすべき更なる２／３領域の種類（例えば、領域３０１、３０２、３０３）があるとプロセッサ２０５が判定した場合には、方法７００はステップ７１０に戻る。そうでなければ、方法７００を終了する。
【００９１】
もう１度図４に戻ると、ステップ４６０に続いて、方法４００はステップ４７０に進む。ステップ４７０において、プロセッサ２０５は、ステップ４５０で選択された候補位置検出パターンの場所に基づいて、標準的な許容ゾーン（例えば、許容ゾーン６００）を変更するステップを実行する。例えば、標準的な許容ゾーン（例えば、許容ゾーン６００）を候補位置検出パターンの場所に基づいて縮小する。
【００９２】
クイックレスポンスコード規格は、位置検出パターンがクイックレスポンスバーコードの内側にあり得ないことを規定している。それゆえに、標準的な許容ゾーン（例えば、許容ゾーン６００）は、現在の候補位置検出パターンが標準的な許容ゾーン（例えば、許容ゾーン６００）内部にある（すなわち、候補位置検出パターンは内部位置検出パターンとして分類されてもよい）２／３クイックレスポンス領域を生じるあらゆる位置検出パターンを考慮から除外するように、ステップ４７０で変更されてもよい。
【００９３】
候補位置検出パターンが中心位置検出パターンとどのような２／３領域（例えば、領域３０１、３０２、３０３）を形成したかに関係なく、標準的な許容ゾーン（例えば、許容ゾーン６００）は変更される。しかしながら、位置検出パターンと関連付けられた信頼値を返す幾つかの位置検出パターンの検出方法がある。従って、いくつかの実現例において、候補位置検出パターンに対する信頼値が所定の閾値を下回る場合には、ステップ４７０はスキップされるようにしてもよい。
【００９４】
ステップ４７０において、プロセッサ２０５は、中心位置検出パターンから候補位置検出パターンまでの距離を決定するステップを実行する。その後、決定された距離は、１／√２で乗算されるが、中心位置検出パターンと２／３／領域を形成する候補位置検出パターンについては最終的な最長許容距離を形成している。特に、中心位置検出パターンから最終的な最長許容距離以上のところにあり且つ候補位置検出パターン９１０を中心とした９０°の弧内にあるあらゆる候補位置検出パターンは、内部位置検出パターン９１０と２／３／領域を規定するであろう。ステップ４７０において、標準的な許容ゾーンの距離は、先の許容距離が決定された距離を上回る場合には常に、結果として、決定された距離に対して９０°の弧内で減少（又は縮小）される。例えば、候補位置検出パターン９１０が与えられたとすると、陰影をつけたエリア９２０は、中心位置検出パターン６３０及び候補位置検出パターン９１０を含む候補対に対して決定された除外領域を表している。従って、ステップ４７０の結果、候補対に対して、画像のエリア内で除外領域が決定されることになる。元の標準的な許容ゾーン６００から、決定された除外領域９２０を除去することにより、より小さな許容ゾーン９３０が得られる。従って、プロセッサ２０５は、許容ゾーン９３０内にあり且つ除外領域９２０に重なる画像エリアを、元の標準的な許容ゾーン６００から除去するステップを実行する。
【００９５】
新しく、縮小されたより小さい標準的な許容ゾーン９３０は、方法７００のステップ７２０に関して上述した変換について有効である。標準的な許容ゾーン９３０により規定される縮小エリアは、２／３／領域が候補位置検出パターンを内部位置検出パターンとして有するのを防ぐ。標準的な許容ゾーン９３０により規定される同じ縮小エリアは、２／３−許容ゾーン及び２／３＋許容ゾーンを生成するようにステップ７２０で変換された場合に、２／３−領域３０３及び２／３＋領域３０２がそれぞれ、候補位置検出パターンを内部位置検出パターンとして有することも防ぐ。
【００９６】
図１０Ａ、図１０Ｂ及び図１０Ｃを参照して、ステップ４７０におけるような標準的な許容ゾーン６００の縮小（又は変形）を更に説明する。
【００９７】
図１０Ａに示されるように、領域１０１０は、図１０Ａに示された位置検出パターン１０１１及び１０１２の一対に対する標準的な除外領域である。例に従って、図１０Ｂに示されるように、領域１０２０は、２／３＋領域について変換された後の（ステップ７２０におけるように）標準的な除外領域１０１０を表す。
【００９８】
図１０Ｂに示されるように、除外領域１０２０において位置検出パターンと形成するあらゆる２／３＋領域は、その２／３＋領域の内側に候補位置検出パターン１０１２を有する。一対が２／３＋領域を規定する場合で、別の位置検出パターンが除外領域１０２０内にある場合には、プロセッサ２０５は、中心位置検出パターン１０１１及びその別の候補位置検出パターンを含む位置検出パターンの候補対を廃棄するステップを実行する。
【００９９】
同様に、図１０Ｃに示されるように、領域１０３０は、２／３−領域について変換された後の標準的な除外領域１０１０を表す。この場合も、ゾーン１０３０において位置検出パターンと形成するあらゆる２／３−領域は、除外領域１０３０の内側に候補位置検出パターン１０１２を有するので、上述したように、そのような２／３−領域を規定するあらゆるペアリング（一対化）は無効とされる。
【０１００】
「決定」ステップ４８０において、プロセッサ２０５は、メモリ２０６に格納された候補リストから現在の候補位置検出パターンを廃棄（又は削除）するステップを実行する。更にステップ４８０において、メモリ２０６に格納された候補リストに更なる候補位置検出パターンがあるとプロセッサ２０５が判定した場合には、方法４００はステップ４５０に戻る。そうでなければ、方法４００はステップ４９０に進む。
【０１０１】
次に、「決定」ステップ４９０において、中心位置検出パターン（又は中心ノード）として処理されていない何らかの位置検出パターンが候補リストにあるとプロセッサ２０５が判定した場合には、方法４００はステップ４２０に進む。そうでなければ、方法４００は最後のステップ４９５に進む。
【０１０２】
「出力」ステップ４９５において、ステップ７４０で識別された全ての有効な２／３領域を含む２／３領域のリストが出力される。例えば２／３領域のリストは、メモリ２０６又はハードディスクドライブ２１０に格納されるようにしてもよく、あるいはソフトウェアアプリケーション２３３の別のコードモジュールに渡されてもよい。
【０１０３】
一実現例において、プロセッサ２０５は、位置検出パターンの候補対をトリプレットに合成するステップを実行してもよい。また、２／３領域は、特定のクイックレスポンスバーコードの３つの位置検出パターンが全て存在する場合には、完全な３／３領域にマージされるようにしてもよい。候補対が解析されて許容領域が縮小（又は変形）する順序のために、３つの位置検出パターンが全て存在するのであれば、クイックレスポンスバーコード領域は、少なくとも１回２／３＋領域として及び少なくとも１回２／３−領域として識別される。従って、例えばプロセッサ２０５は、図３Ｂに示されたように各２／３＋領域の一対を調査し且つ位置検出パターン３３０が他の位置検出パターンと何らかの２／３−領域を形成するかを判定するステップを実行してもよい。位置検出パターン３３０が他の位置検出パターンと何らかの２／３−領域を形成するとプロセッサ２０５が判定した場合に、位置検出パターンのトリプレットは、位置検出パターンのトリプレットにより形成された「Ｌ」形状を確認し、且つ上述したような位置検出パターンの角度及び大きさを確認することにより、クイックレスポンス規格に準拠しているかをテストされるようにしてもよい。位置検出パターンのトリプレットが準拠する場合、位置検出パターンのトリプレットは、メモリ２０６内に構成された出力３／３領域リストに追加されてもよく、関連付けられた２／３領域は出力２／３領域リストから削除されてもよい。
【０１０４】
一実現例において、冗長化している２／３領域は、除外され且つ廃棄されてもよい。例えば、第１の位置検出パターンが中心位置検出パターンである場合に発見された２／３領域が、第２の位置検出パターンが中心位置検出パターンである場合に再度発見される場合があるので、幾つかの２／３領域は倍となる。更に、２／３−領域は二重の２／３＋領域を有し、２／３／領域は二重の２／３／領域を有する。従って、冗長化している２／３領域は、除外され且つ廃棄されるようにしてもよい。
【０１０５】
説明した方法に従って決定された３／３領域及び残りの２／３領域は、ＩＳＯ／ＩＥＣ１８００４において説明したようにその後クイックレスポンス復号器に入力され、領域内で符号化されたあらゆるデータを取得するようにしてもよい。
【産業上の利用可能性】
【０１０６】
説明された構成は、コンピュータ及びデータ処理業界、並びに特に処理バーコードに適用可能である。
【０１０７】
上記の記述は本発明のいくつかの実施形態のみを説明し、本発明の範囲及び趣旨から逸脱せずに、変形及び／又は変更がいくつかの実施形態に対して行なわれてもよい。実施形態は、限定するものではなく例示するものである。
【０１０８】
本明細書に関して、「備える」という言葉は、「主に含むが、単独で必要ではない」、あるいは「有する」又は「含む」ことを意味し、「のみから構成される」ことではない。「備える」の語形変化は、それに対応して意味の変化を示す。
【図１】
2012138079.tif 000003
【図２Ａ】
2012138079.tif 000004
【図２Ｂ】
2012138079.tif 000005
【図３Ａ】
2012138079.tif 000006
【図３Ｂ】
2012138079.tif 000007
【図３Ｃ】
2012138079.tif 000008
【図４】
2012138079.tif 000009
【図５】
2012138079.tif 000010
【図６Ａ】
2012138079.tif 000011
【図６Ｂ】
2012138079.tif 000012
【図７】
2012138079.tif 000013
【図８】
2012138079.tif 000014
【図９】
2012138079.tif 000015
【図１０Ａ】
2012138079.tif 000016
【図１０Ｂ】
2012138079.tif 000017
【図１０Ｃ】
2012138079.tif 000018