バーコードの位置検出パターンの候補対を識別する方法、装置及びシステム
【課題】2次元コードの位置検出パターンの候補対を識別する方法を提供する。
【解決手段】第1の位置検出パターンは、画像のエリアにおいて検出された複数の位置検出パターンから選択される。別の位置検出パターンは、残りの複数の検出された位置検出パターンから選択され、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する。候補対について画像のエリア内の除外領域が判定される。別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対は除去される。除外領域に重なる許容ゾーン内の画像のエリアは、許容ゾーンから除去される。2次元コードの位置検出パターンの候補対を識別するために、1つ以上の更に別の位置検出パターンに対してステップを繰り返す。
【解決手段】第1の位置検出パターンは、画像のエリアにおいて検出された複数の位置検出パターンから選択される。別の位置検出パターンは、残りの複数の検出された位置検出パターンから選択され、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する。候補対について画像のエリア内の除外領域が判定される。別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対は除去される。除外領域に重なる許容ゾーン内の画像のエリアは、許容ゾーンから除去される。2次元コードの位置検出パターンの候補対を識別するために、1つ以上の更に別の位置検出パターンに対してステップを繰り返す。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、2次元バーコードに関し、特にバーコードの位置検出パターンの候補対を識別する方法及び装置に関する。更に本発明は、バーコードの位置検出パターンの候補対を識別するコンピュータプログラムが記録されたコンピュータ可読媒体を含むコンピュータプログラムに関する。
【背景技術】
【0002】
2次元バーコードは、1次元バーコードと比較してデータ容量が大きく、且つそのようなバーコードに対する符号化デバイス及び復号化デバイスの利用可能性が高まってきているため、益々普及している。
【0003】
「クイックレスポンス(QR)バーコード」として既知である2次元バーコードは、特に一般的な2次元バーコードである。図1は、クイックレスポンスバーコード100の一例を示す。図1に示されるように、クイックレスポンスバーコード100は、正方画素の正方配列である。各正方画素は、「モジュール」(例えば、白色モジュール101及び黒色モジュール102)と呼ばれる。モジュールは、データを符号化するために使用される。
【0004】
データを符号化するために使用されるモジュールに加え、クイックレスポンスバーコード100は、3つの場所・識別シンボル103を含む。3つの場所シンボル103は、それぞれ「位置検出バターン」(FP)として既知である。図1に示されるように、位置検出パターン103は、クイックレスポンスバーコード100の左上の隅、右上の隅及び左下の隅に配置される。従って、クイックレスポンスバーコードにより占有された画像の2次元エリアは、3つの位置検出バターン103の場所により画設される。そのような2次元エリアは、「クイックレスポンスバーコード領域」としても既知である。
【0005】
クイックレスポンスバーコード100等のクイックレスポンスバーコードを復号化する第1のステップは、上述の位置検出パターン103を使用して入力画像中のバーコード100を識別することである。
【0006】
クイックレスポンスバーコードは、製品ラベル、広告掲示板及び名刺等の幅広い媒体上に頻繁に含まれる。従来、そのような媒体は、高品質の単一のクイックレスポンスバーコードのみを含んでいる(すなわち、元のクイックレスポンスバーコードのデジタル画像は、媒体上に正確に再現されている)。従って、クイックレスポンスバーコードが復号化される場合には、取得された画像に単一のクイックレスポンスバーコードのみがあり且つバーコードの品質が高いことが、相対的に単純な復号化処理の使用を容易にする。また、カメラ電話等の従来のクイックレスポンスバーコード撮像デバイスは、クイックレスポンスバーコードの画像が非常に少ない回転位置合わせ誤差で取得されるように、ユーザにより調整される場合がある。ユーザにより調整された撮像デバイスは更に、クイックレスポンスバーコード中のモジュール(例えば、白色モジュール101)のサイズが撮像デバイスに対して既知の範囲内にあるように、クイックレスポンスバーコードをフレーム化する。
【0007】
最近、ドキュメントセキュリティ及びワークフロー管理を支援することにおいて、クイックレスポンスバーコードの活用に対する関心が高まってきている。そのようなアプリケーションの場合、取得された画像中に複数のクイックレスポンスバーコードがある場合がある。更に、画像中のクイックレスポンスバーコードのモジュールのサイズ及び向きは様々である場合が多い。更にクイックレスポンスバーコードは、何度も印刷、スキャン及び再印刷される場合があり、その度にクイックレスポンスバーコードの画像品質が低下する。特に、クイックレスポンスバーコードは、クイックレスポンスバーコード中の黒色モジュールのサイズと白色モジュールのサイズとの比が理想的な1:1から大幅にずれる「ドットゲイン」の影響を受ける可能性が高い。例えば、印刷及びスキャンの複数サイクルにより、位置検出パターン103と比較してクイックレスポンスバーコードの位置検出パターンの外観を更に変化させるような他の歪み及びノイズを更に招いてしまう。
【0008】
クイックレスポンスバーコード復号器のリファレンス実装は、ISO/IEC18004規格で入手可能である。しかしながら、ISO/IEC18004規格におけるリファレンス実装は、画像中にクイックレスポンスバーコードが1つのみであることを仮定し、且つ、ちょうど3つの位置検出パターンが検出されることを仮定している。また、非検出位置検出パターン若しくは偽陽性位置検出パターンは、ISO/IEC18004規格では考慮されない。
【0009】
非検出位置検出パターンは、ノイズ又は他の歪みの中においてはよく見かけられ、偽陽性位置検出パターンの検出は、特に日本語又は中国語のテキストにおいてはよく見かけられる。従って、位置検出パターンは一旦検出されると、クイックレスポンスバーコードの位置検出パターンを識別するために、「分割される」必要がある。従来、所定の許容範囲内で各々が同一の大きさ及び同一の角度を有する正方形の「L」字型を形成する位置検出パターンのトリプレットは、位置検出パターンがクイックレスポンスバーコードのものであることを識別するために、検出され且つ分割される必要がある。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】ISO/IEC18004規格
【発明の概要】
【発明が解決しようとする課題】
【0011】
クイックレスポンスバーコードを識別するように位置検出パターンを分割する1つの方法には、クイックレスポンス規格に準拠するように検出された位置検出パターンの考えられるだけのトリプレットをテストすることが含まれる。そのような方法での実行時間は、解析される位置検出パターン数の三乗で増加するため、この方法は「O(n3)方法」と呼ばれる。いくつかの応用例においては、O(n3)方法が受け入れられるであろう。しかしながら、特にクイックレスポンスバーコードの復号化は、限られたメモリ及び処理能力を有する組込み型デバイス上で頻繁に要求されるので、検出された位置検出パターン数が増加するにつれて、O(n3)方法は非実用的なものになってしまう。
【0012】
本発明の目的は、既存の構成の1つ以上の欠点を実質的に克服するか、あるいは少なくとも改善することである。
【課題を解決するための手段】
【0013】
本発明の一態様によると、2次元バーコードの位置検出パターンの候補対を識別する方法であって、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する工程と、
(ii)残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する工程と、
(iii)候補対について、画像のエリア内で除外領域を決定する工程と、
(iv)別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する工程と、
(v)除外領域に重なる許容ゾーン内のエリアを、許容ゾーンから除去する工程と、
(vi)2次元バーコードの位置検出パターンの候補対を識別するために、1つ以上の更に別の位置検出パターンについて、ステップ(ii)〜(v)を繰り返す、ことを特徴とする方法が提供される。
【0014】
本発明の別の態様によると、2次元バーコードの位置検出パターンの候補対を識別する装置であって、
画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する手段と、
残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する手段と、
候補対について、画像のエリア内で除外領域を決定する手段と、
別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する手段と、
2次元バーコードの位置検出パターンの候補対を識別するために、除外領域に重なっている許容ゾーン内のエリアを、許容ゾーンから除去する手段とを備える装置が提供される。
【0015】
本発明の更に別の態様によると、2次元バーコードの位置検出パターンの候補対を識別するシステムであって、
データ及びコンピュータプログラムを格納するメモリと、
コンピュータプログラムを実行するメモリに結合されたプロセッサとを備え、コンピュータプログラムが、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する命令と、
(ii)残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する命令と、
(iii)候補対について、画像のエリア内で除外領域を決定する命令と、
(iv)別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する命令と、
(v)除外領域に重なっている許容ゾーン内の画像のエリアを許容ゾーンから除去する命令と、
(vi)2次元バーコードの位置検出パターンの候補対を識別するために、1つ以上の更に別の位置検出パターンについて、ステップ(ii)〜(v)を繰り返す命令とを含むシステムが提供される。
【0016】
本発明の別の態様によると、上述した方法を実現するコンピュータプログラムを記録したコンピュータ読取可能な媒体を含むコンピュータプログラムが提供される。
【0017】
本発明の他の態様が更に開示される。
【図面の簡単な説明】
【0018】
次に、以下の図面を参照して、本発明の1つ以上の実施形態を説明する。
【図1】図1は、黒色モジュール及び白色モジュール、並びに位置検出パターンを含むクイックレスポンスバーコードの一例を示す図である。
【図2A】、
【図2B】図2A、図2Bは、説明される構成が実施される汎用コンピュータシステムの概略ブロック図である。
【図3A】、
【図3B】、
【図3C】図3A、3B、3Cは、クイックレスポンスバーコードに対する3つの可能な2/3領域構成を示す図である。
【図4】図4は、バーコードの位置検出パターンの候補対を識別する方法を概略的に示すフローチャートである。
【図5】図5は、各々がネットワークのノードにより表される位置検出パターンの例示的なネットワークの三角形分割を示す図である。
【図6A】図6Aは、「中心」位置検出パターンの周囲の標準的な許容ゾーンを示す図である。
【図6B】図6Bは、2/3+許容ゾーンに変換された図6Aの標準的な許容ゾーンを示す図である。
【図7】図7は、図4の方法で使用されるような中心位置検出パターン及び「候補」位置検出パターンを含む位置検出パターンの一対を解析する方法を概略的に示すフローチャートである。
【図8】図8は、解析される例示的な中心位置検出パターン及び候補位置検出パターンの角度及び大きさを示す図である。
【図9】図9は、候補位置検出パターンにより形成された除外領域に係る許容ゾーンの変形の一例を示す図である。
【図10A】、
【図10B】、
【図10C】図10A、10B、10Cは、候補位置検出パターンにより形成された図9の除外領域の変換の一例を示す図である。
【発明を実施するための形態】
【0019】
添付の図面のうちのいずれか1つ以上において、同一の参照符号を有するステップ及び/又は特徴が参照される。逆の意図が示されない限り、これらのステップ及び/又は特徴は、本明細書の目的のために同一の機能又は動作を有する。
【0020】
尚、「背景」の節に含まれる説明及び先行技術の構成に関連する上述のものは、それぞれの公表及び/又は用途を介して周知の知識を形成する文書又はデバイスの説明に関連している。そのようなものが本発明者又は本特許出願人により表現されたものとして解釈されるべきではなく、そのような文献又はデバイスは、当技術分野における一般常識の一部を何らかの形で形成するものである。
【0021】
図4を参照して、バーコードの位置検出パターンの候補対を識別する方法400を以下に説明する。方法400は、画像中で検出された位置検出パターンを含む「入力」リストを解析し、一組の候補位置検出パターン対を出力する。出力された位置検出パターン対は、2次元バーコードの部分を形成するのに適した構成である。方法400は、種々のサイズ又は角度を有する無効な空間関係にある位置検出パターン対を廃棄するステップを実行する。
【0022】
方法400は、一般的に2次元バーコードに適用可能である。しかしながら、説明を簡単にするために、クイックレスポンスバーコードを参照して方法400のステップを説明する。本発明を説明する方法に限定されることを意図するものではない。例えば方法400は、「PDF417」バーコード及び「データマトリックス」バーコード等の他のあらゆる種類の2次元バーコードに適用されてもよい。
【0023】
図2A及び図2Bは、説明される種々の構成が実施される際の汎用的なコンピュータシステム200を示す。
【0024】
図2Aに示されるように、コンピュータシステム200は、コンピュータモジュール201、キーボード202、マウス・ポインティングデバイス203、スキャナ226、カメラ227及びマイク280等の入力デバイス、並びにプリンタ215、表示装置214及びスピーカ217を含む出力デバイスを含む。外部変復調器(モデム)送受信機デバイス216は、接続221を介して通信ネットワーク220と通信するためにコンピュータモジュール201により使用されてもよい。通信ネットワーク220は、インターネット、セルラ電気通信ネットワーク等のワイドエリアネットワーク(WAN)又は専用WANであってもよい。接続221が電話線である場合、モデム216は従来の「ダイヤルアップ」モデムであってもよい。あるいは、接続221が大容量(例えば、ケーブル)接続である場合、モデム216はブロードバンドモデムであってもよい。無線モデムは、通信ネットワーク220に無線接続するために更に使用されてもよい。
【0025】
コンピュータモジュール201は、一般的に、少なくとも1つのプロセッサユニット205及びメモリユニット206を含む。例えばメモリユニット206は、半導体ランダムアクセスメモリ(RAM)及び半導体読み出し専用メモリ(ROM)を有してもよい。コンピュータモジュール201は、ビデオディスプレイ214に結合するオーディオ/ビデオインタフェース207、スピーカ217及びマイク280を含む多数の入出力(I/O)インタフェース、キーボード202、マウス・ポインティングデバイス203、スキャナ226、カメラ227及びオプションとしてジョイスティック又はヒューマンインタフェースデバイス(不図示)に結合するI/Oインタフェース213、並びに外部モデム216及びプリンタ215用のインタフェース208を更に含む。いくつかの実施例において、モデム216は、インタフェース208等のコンピュータモジュール201内に組み込まれてもよい。コンピュータモジュール201は、接続223を介してコンピュータシステム200がローカルエリアネットワーク(LAN)として既知であるローカルエリア通信ネットワーク222に接続できるようにするローカルネットワークインタフェース211を更に有する。図2Aに示されるように、ローカル通信ネットワーク222は、一般的にいわゆる「ファイアウォール」デバイス又は同様の機能性を備えたデバイスを含むワイドネットワーク220に接続224を介して更に結合してもよい。ローカルネットワークインタフェース211は、Ethernet(登録商標)回路カード、Bluetooth(登録商標)無線装置又はIEEE802.11無線装置を備えてもよいが、多数の他の種類のインタフェースがインタフェース211に対して実施されてもよい。
【0026】
I/Oインタフェース208及び213は、直列接続性及び並列接続性のいずれか一方又は双方を提供してもよい。一般的に直列接続性は、USB(Universal Serial Bus)規格に従って実現され且つ対応するUSBコネクタ(不図示)を有する。記憶装置209が提供され、一般的に記憶装置209は、ハードディスクドライブ(HDD)210を含む。フロッピディスクドライブ及び磁気テープドライブ(不図示)等の他の記憶装置が更に使用されてもよい。オプションのディスクドライブ212は、一般的に、データの不揮発性ソースとして動作するように提供される。例えば、光ディスク(例えば、CD−ROM、DVD、Blu−ray Disc(登録商標))、USB−RAM、取り外し可能な外部ハードドライブ及びフロッピディスク等のポータブルメモリ装置は、システム200に対する適切なデータソースとして使用されてもよい。
【0027】
コンピュータモジュール201の構成要素205〜213は、一般的に、相互接続バス204を介して通信し、且つ結果として当業者に既知であるコンピュータシステム200の動作の従来のモードから得られる方法で通信する。例えばプロセッサ205は、接続218を使用してシステムバス204に結合される。同様に、メモリ206及び光ディスクドライブ212は、接続219によりシステムバス204に結合される。説明する構成が実施されるコンピュータの例には、IBM−PC’s及び互換性のあるもの、Sun Sparcstations、Apple Mac(登録商標)又は同様のコンピュータシステムが含まれる。
【0028】
方法400を含む以下に説明する方法は、コンピュータシステム200を使用して実現されてもよい。方法において説明される図3A〜図10Cの処理は、コンピュータシステム200内で実行可能な1つ以上のソフトウェアアプリケーションプログラム233として実現されてもよい。特に、説明される方法のステップは、コンピュータシステム200内で実行されるソフトウェア233で命令231(図2Bを参照)により実施される。ソフトウェア命令231は、各々が1つ以上の特定のタスクを実行する1つ以上のコードモジュールとして形成されてもよい。ソフトウェアは2つの別個の部分に更に分割されてもよく、第1の部分及び対応するコードモジュールは説明する方法を実行し、第2の部分及び対応するコードモジュールは、第1の部分とユーザとの間のユーザインタフェースを管理する。
【0029】
例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読取可能な媒体に格納されてもよい。ソフトウェアは、コンピュータ読取可能な媒体からコンピュータシステム200にロードされ、コンピュータシステム200により実行される。そのようなソフトウェアを有するコンピュータ読取可能な媒体又はコンピュータ読取可能な媒体上に記録されたコンピュータプログラムは、コンピュータプログラム製品である。コンピュータシステム200においてコンピュータプログラムを使用することにより、説明する方法を実現する有利な装置を実施するのが好ましい。
【0030】
ソフトウェア233は、一般的にHDD210又はメモリ206に格納される。ソフトウェアは、コンピュータ読取可能な媒体からコンピュータシステム200にロードされ、コンピュータシステム200により実行される。従って、例えばソフトウェア233は、光ディスクドライブ212により読み出される光学的に読出可能なディスク記憶装置媒体(例えば、CD−ROM)225上に格納されてもよい。そのようなソフトウェアを有するコンピュータ読取可能な媒体又はコンピュータ読取可能な媒体上に記録されたコンピュータプログラムは、コンピュータプログラム製品である。コンピュータシステム200においてコンピュータプログラム製品を使用することにより、説明する方法を実現する装置を実施するのが好ましい。
【0031】
いくつかの例において、アプリケーションプログラム233は、1つ以上のCD−ROM225上でユーザが符号化したものに供給され且つ対応するドライブ212を介して読み出されてもよく、あるいはユーザによりネットワーク220又は222から読み出されてもよい。更にソフトウェアは、他のコンピュータ読取可能な媒体からコンピュータシステム200にロードされてもよい。コンピュータ読取可能な記憶媒体は、実行及び/又は処理するために、記録された命令及び/又はデータをコンピュータシステム200に提供するあらゆる非一過性(non−transitory)の有形(tangible)の記憶媒体を示す。そのような記憶媒体の例には、フロッピディスク、磁気テープ、CD−ROM、DVD、Blu−ray Disc、ハードディスクドライブ、ROM又は集積回路、USBメモリ、光磁気ディスク、あるいは例えばPCMCIAカード等のコンピュータ読取可能なカードが含まれ、そのようなデバイスは、コンピュータモジュール201の内部又は外部にある。ソフトウェア、アプリケーションプログラム、命令及び/又はデータをコンピュータモジュール101に提供することに更に関連してもよい一過性又は非一過性のコンピュータ読取可能な伝送媒体の例には、無線送信チャネル又は赤外線送信チャネル及び別のコンピュータ又はネットワーク化されたデバイスへのネットワーク接続、並びに電子メール送信及びウェブサイト上等に記録された情報を含むインターネット又はイントラネットが含まれる。
【0032】
上述したアプリケーションプログラム233の第2の部分及び対応するコードモジュールは、ディスプレイ214上にレンダリングされるか若しくは表される1つ以上のグラフィカルユーザインタフェース(GUI)を実現するように実行されてもよい。一般的にキーボード202及びマウス・ポインティングデバイス203を操作することにより、コンピュータシステム200及びアプリケーションのユーザは、GUIと関連付けられたアプリケーションに制御コマンド及び/又は入力を提供するように機能的に適応可能な方法でインタフェースを操作してもよい。他の形式の機能的に適応可能なユーザインタフェース、例えばスピーカ217を介して出力された音声プロンプト及びマイク280を介して入力されたユーザ音声コマンドを利用するオーディオインタフェースが更に実現されてもよい。
【0033】
図2Bは、プロセッサ205及び「メモリ」234を示す詳細な概略ブロック図である。メモリ234は、図2Aのコンピュータモジュール201によりアクセスされる全てのメモリモジュール(HDD210及び半導体メモリ206を含む)の論理的な集約を示す。
【0034】
コンピュータモジュール201が最初に電源投入される場合、自己診断(POST)プログラム250が実行される。一般的にPOSTプログラム250は、図2Aの半導体メモリ206のROM249に格納される。ソフトウェアを格納するROM249等のハードウェアデバイスは、ファームウェアと呼ばれる場合もある。POSTプログラム250は、コンピュータモジュール201内のハードウェアを調査して適切に機能することを保証し、一般的に、正しく動作するためにROM249に更に格納されたプロセッサ205、メモリ234(209、206)及び基本入出力システム(BIOS)ソフトウェアモジュール251をチェックする。POSTプログラム250が正常に実行されると、BIOS251は図2Aのハードディスクドライブ210を起動する。ハードディスクドライブ210を起動することにより、ハードディスクドライブ210上に常駐するブートストラップ・ローダプログラム252がプロセッサ205を介して実行される。これにより、オペレーティングシステム253は、RAMメモリ206にロードされると動作を開始する。オペレーティングシステム253は、プロセッサ205により実行可能なシステムレベルのアプリケーションであり、プロセッサ管理、メモリ管理、デバイス管理、ストレージ管理、ソフトウェアアプリケーションインタフェース及び汎用ユーザインタフェースを含む種々のハイレベルな機能を遂行する。
【0035】
オペレーティングシステム253は、メモリ234(209、206)を管理し、コンピュータモジュール201上で実行する処理又はアプリケーションの各々が別の処理に割り当てられたメモリと衝突することなく実行するだけの十分なメモリを有することを保証する。また、図2Aのシステム200で使用可能な種々のメモリは、各処理が効率的に実行するように適切に使用される必要がある。従って、集約メモリ234は、メモリの特定の部分が割り当てられる方法を示すことを意図せず(明示的に記載されない限り)、コンピュータシステム200によりアクセス可能なメモリの概略図及びそのようなメモリが使用される方法を提供する。
【0036】
図2Bに示されるように、プロセッサ205は、制御ユニット239、演算論理装置(ALU)240及びキャッシュメモリと呼ばれることもあるローカルメモリ又は内部メモリ248を含む多数の機能モジュールを含む。一般的にキャッシュメモリ248は、レジスタ部に複数の記憶レジスタ244〜246を含む。1つ以上の内部バス241は、これらの機能モジュールを機能的に相互接続する。一般的にプロセッサ205は、接続218を使用してシステムバス204を介して外部デバイスと通信する1つ以上のインタフェース242を更に有する。メモリ234は、接続219を使用してバス204に結合される。
【0037】
アプリケーションプログラム233は、条件付き分岐命令及びループ命令を含んでもよい一連の命令231を含む。プログラム233は、プログラム233を実行するのに使用されるデータ232を更に含んでもよい。命令231及びデータ232は、それぞれ、記憶場所228、229、230及び235、236、237に格納される。命令231及びメモリの記憶場所228〜230の相対的なサイズに依存して、特定の命令は、記憶場所230に示された命令により描かれるように単一の記憶場所に格納されてもよい。あるいは、命令は、メモリの記憶場所228及び229に示される命令部分により描かれるように、各々が別個のメモリの記憶場所に格納される多数の部分に分割されてもよい。
【0038】
一般的にプロセッサ205は、そこで実行される命令の集合を与えられる。プロセッサ205は、命令の別の集合を実行することによりプロセッサ205自身が反応する後続の入力を待つ。各入力は、入力デバイス202、203の1つ以上により生成されたデータ、ネットワーク220、222のうちの一方を介して外部ソースから受信したデータ、記憶装置206、209のうちの一方から検索したデータ又は対応する読取装置212に挿入された記憶媒体225から検索したデータを含む多数のソースのうちの1つ以上から提供されてもよく、その全てが図2Aに示されたものである。いくつかの例において、命令の集合を実行した結果、データが出力されてもよい。実行することは、データ又は変数をメモリ234に格納することを更に含んでもよい。
【0039】
説明する方法は、対応するメモリの記憶場所255、256、257においてメモリ234に格納される入力変数254を使用する。説明する方法は、対応するメモリの記憶場所262、263、264においてメモリ234に格納される出力変数261を生成する。中間変数258は、メモリの記憶場所259、260、266及び267に格納されてもよい。
【0040】
図2Bのプロセッサ205を参照すると、レジスタ244、245、246、演算論理装置(ALU)240及び制御ユニット239は、プログラム233を構成する命令集合において命令毎に「取り込み、復号化及び実行」サイクルを実行するのに必要なマイクロ動作のシーケンスを実行するように共に動作する。取り込み、復号化及び実行サイクルの各々は、
(a)メモリの記憶場所228、229、230からの命令231を取り込むかあるいは読み取る取り込み動作、
(b)制御ユニット239が、取り込まれた命令を判定する復号化動作、並びに
(c)制御ユニット239及び/又はALU240が命令を実行する命令動作を含む。
【0041】
その後、次の命令に対する更なる取り込み、復号化及び実行サイクルが実行されてもよい。同様に、制御ユニット239が値をメモリの記憶場所232に格納するかあるいは書き込むことにより、格納サイクルが実行されてもよい。
【0042】
図4〜図10の処理におけるステップ又はサブ処理の各々は、プログラム233の1つ以上の部分と関連付けられ、プログラム233の示された部分に対して命令集合の命令毎に取り込み、復号化及び実行サイクルを実行するようにプロセッサ205のレジスタ部244、245、247、ALU240と制御ユニット239が共に動作することにより実行される。
【0043】
あるいは、説明される方法は、説明される方法の機能又はサブ機能を実行する1つ以上の集積回路等の専用ハードウェアで実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ又は1つ以上のマイクロプロセッサ及び関連付けられたメモリを含んでもよい。
【0044】
以下に詳細に説明するように、検出された位置検出パターンを可能な2次元バーコードに分割(resolve)するO(n3)方法は、位置検出パターンのトリプレットではなく、位置検出パターンの「候補対」を決定するように変更されてもよい。位置検出パターンの候補対の各々は、以下において「2/3領域」と呼ばれるものを形成する。対応するクイックレスポンスバーコードの3つの位置検出パターンのうちの2つが検出されるため、候補対は2/3領域と呼ばれる。
【0045】
図3A、図3B及び図3Cに示されるように、クイックレスポンスバーコード100に対して3つの可能な2/3領域構成がある。図3Aは、位置検出パターン103の第1の検出パターン310が位置検出パターン103の第2の位置検出パターン320とはす向かいの位置関係になっている場所に形成された「2/3/」領域301を示す。図3Bは、位置検出パターン103の2つの位置検出パターン310及び330が互いに隣接し、且つ対応するクイックレスポンスバーコード100が第2の位置検出パターン330から時計回りの方向に形成された場合の「2/3+」領域302を示す。図3Cは、位置検出パターン103の2つの位置検出パターン310及び340が互いに隣接し、且つクイックレスポンスバーコード100が第2の位置検出パターン340から反時計回りの方向に形成された場合の「2/3−」領域303を示す。
【0046】
図3B及び図3Cに示されるように、2/3+領域302及び2/3−領域303は、それぞれ、位置検出パターンの同一の構成を有する。しかしながら、以下に詳細に説明するように、許容ゾーンに対して位置検出パターンの一対をテストする際に2/3+領域の種類及び2/3−領域の種類のうちのいずれか一方又はその双方が適用可能であってもよく、あるいはそのいずれも適用可能でなくてもよいため、2/3+領域302及び2/3−領域303は別個に考慮される。
【0047】
以下に詳細に説明するように、重複する2/3領域同士が完全な3/3クイックレスポンス領域を形成するようにマージされる(あるいは、組み合わされる)場合、位置検出パターン(例えば、位置検出パターン310及び330)の候補対からのクイックレスポンスバーコード100の方向は、更に重要である。説明するように、プロセッサ205は、位置検出パターンの候補対をトリプレットに合成するステップを実行してもよい。
【0048】
図4を参照して、バーコードの位置検出パターンの候補対を識別する方法400を以下に説明する。方法400は、ハードディスクドライブ210上に常駐し且つ実行中にプロセッサ205により制御されるソフトウェアアプリケーションプログラム233のソフトウェアコードモジュールの1つとして実現されてもよい。画像の1つのエリアにおいて検出される位置検出パターンの「入力」リストが与えられたとすると、方法400は、画像のエリアにおいて2/3領域(例えば、領域301、302、又は303)を識別する。位置検出パターンの入力リストは、画像のエリアにおいて検出される複数の位置検出パターンを含む。検出される位置検出パターンを含む入力リストは、メモリ206又はハードディスクドライブ210からアクセスされるようにしてもよい。図1のクイックレスポンスバーコード100及び位置検出パターンのネットワーク500(図5を参照)を参照しながら、方法400を説明する。
【0049】
第1の「リスト作成」ステップ405において、プロセッサ205は、メモリ206又はハードディスクドライブ210内に2/3領域の空リストを作成するステップを実行する。方法400の後に続くステップ中で識別される全ての有効な2/3領域は、2/3領域のリストに連続して追加される。2/3領域のリストは、メモリ206又はハードディスクドライブ210からアクセスされるようにしてもよい。
【0050】
「ネットワーク生成」ステップ410において、位置検出パターンのネットワーク500(図5を参照)がプロセッサ205により生成される。図5の例における各位置検出パターン(例えば、位置検出パターン510)は、黒丸として示される。位置検出パターンのネットワーク500は、メモリ206に格納されるようにしてもよい。生成されたネットワーク500の各位置検出パターンは、直線「エッジ」(例えば、エッジ520)により結合される。
【0051】
ネットワーク500は、ドロネー三角形分割を使用してステップ410で生成される。あらゆる適切なO(nlogn)方法がドロネー三角形分割を実行するために使用されてもよい。
【0052】
ドロネー三角形分割は、以下の望ましい特性を有する。
【0053】
1.各ノード(即ち、位置検出パターンを表す)に接続されたエッジの平均数が6未満である。
【0054】
2.位置検出パターンを表す各ノードが別の位置検出パターンを表す最も近接する隣接ノードに接続される。
【0055】
3.一般的に、位置検出パターンを表す各ノードが、O(logk)エッジにより他の位置検出パターンを表すk番目に最も近接する隣接ノードに接続される。
【0056】
位置検出パターンを表す所定のノードから開始するネットワーク500のエッジを行き来することによって、ドロネー三角形分割は結果として、隣接位置検出パターンを表す隣接ノードを迅速に配置するために使用される場合がある。
【0057】
ステップ410の後、方法400の次のステップ420〜490は、可能な2/3領域(例えば、領域301、302、303)を繰り返して識別する。ステップ420〜490において、プロセッサ205は、順次、「中心」位置検出パターン(又はノード)としてメモリ206に格納された入力リストの位置検出パターンの各々を選択するステップを実行する。上述したように、位置検出パターンの入力リストは、画像のエリアにおいて検出された複数の位置検出パターンを含む。検出された位置検出パターンを含む入力リストは、メモリ206又はハードディスクドライブ210からアクセスされるようにしてもよい。
【0058】
ステップ420〜490において、プロセッサ205は、解析するために位置検出パターンの候補対を決定するステップを更に実行する。位置検出パターンの候補対は、ネットワーク500により示されるように、選択された中心位置検出パターンを、入力リストの残りの隣接位置検出パターンのうち少なくとも1つと連続して組み合わせることによって決定される。
【0059】
「選択」ステップ420において、まだ考慮されていない入力リストの次の(又は方法400の最初の繰り返しにおける第1の)位置検出パターンは、中心位置検出パターン(又は中心ノード)としてプロセッサ205により選択される。上述したように、選択された位置検出パターンは、画像のエリア(又は、第1のエリア)において検出された複数の位置検出パターンを含む位置検出パターンの入力リストから選択される。
【0060】
中心位置検出パターンが与えられたとして、有効な2/3領域(例えば、領域301、302、303)を規定する位置検出パターンの一対を形成してもよい隣接位置検出パターンの識別は、「許容ゾーン」を使用することによって迅速化される。許容ゾーンは、隣接位置検出パターンがある画像の部分集合を規定しており、中心位置検出パターンと一対を成す有効な位置検出パターンを潜在的に形成する。
【0061】
次に、図6Aを参照する。次のステップ430において、中心位置検出パターン630と一対になって2/3/領域(例えば、領域301)を形成可能な隣接位置検出パターンが許容されるゾーン600(即ち、「許容ゾーン」)は、プロセッサ205により初期化される。以下に説明するように、2/3+領域の例及び2/3−領域の例について対応するエリアが2/3/領域の例から導出されてもよいので、2/3+領域及び2/3−領域それぞれに対応する別個の許容ゾーンを必要としない。以下の説明において、2/3/領域許容ゾーン600を「標準的な許容ゾーン」と呼ぶ。
【0062】
一実施例において、標準的な許容ゾーン600は、セクタの連結リストとしてメモリ206内に格納される。各セクタは、特定の角度範囲内で中心位置検出パターン630から隣接位置検出パターンの最長許容距離を規定している。セクタは、角度において単調に大きくなっており、0°〜360°の全角度に渡っている。
【0063】
標準的な許容ゾーン600は、8つのセクタとして初期化される。4つのセクタ(例えば、セクタ610)は、中心位置検出パターン630に関して対角線状に位置合わせされる。対角線状に位置合わせされたセクタ(例えば、セクタ601)の最大半径は、中心位置合わせパターン630のサイズ及び大きさの許容範囲を与えるクイックレスポンスバーコード(例えば、クイックレスポンスバーコード100)の最大サイズにより規定される。例えば、適切な大きさの許容範囲は20%である。4つのセクタ(例えば、セクタ610)の幅は、所定の角度の許容範囲により規定される。適切な角度の許容範囲は、例えば20度である。
【0064】
4つの対角線状に位置合わせされたセクタ(例えば、セクタ610)に加え、初期の標準的な許容ゾーン600は、半径ゼロで介在する4つのセクタ(不図示)を含む。
【0065】
再度図4に戻ると、ステップ430の後、方法400は「リスト」ステップ440に進む。ステップ440において、位置検出パターンの「候補」リストは、プロセッサ205により確立されてメモリ206に格納される。以下に詳細に説明するように、候補リストにおける連続的な位置検出パターンは、選択された中心位置検出パターンと組み合わされる。例えば、結果として得られる位置検出パターンの一対は、結果として得られる位置検出パターンの一対がクイックレスポンスバーコード100に対して有効な2/3領域を規定するかを決定するように評価される。
【0066】
候補リストは、先に決定されたドロネー三角形分割に係る中心位置検出パターンの隣接位置検出パターンの各々を含んでいる。
【0067】
候補リストにおいて各位置検出パターンの「親」位置検出パターンとして参照される位置検出パターンも、ステップ440においてメモリ206に格納される。特定の候補位置検出パターンの親は、候補位置検出パターンを候補リストに追加した位置検出パターンである。最初の、中心位置検出パターンは、位置検出パターンの候補リストにおいて全ての位置検出パターンの親である。
【0068】
しかしながら、ステップ470で実行されるように、「他の」位置検出パターンの隣接位置検出パターンが候補リストに追加されるようにしてもよい。この例において、これらの「他の」位置検出パターンも親位置検出パターンになる。
【0069】
「選択」ステップ450において、プロセッサ205は、メモリ206に格納された候補リストから任意の(又は第2の)位置検出パターンを「候補位置検出パターン」として選択するステップを実行する。ステップ450で選択された候補位置検出パターン及びステップ420で選択された中心位置検出パターンは、共に「候補対」を形成する。従って、位置検出パターンはステップ450で候補リストにおいて検出された残りの複数の位置検出パターンから選択され、ステップ420で選択された位置検出パターン及びステップ450で選択された位置検出パターンを含む候補対を形成する。
【0070】
後続するステップ460及び470において、以下に説明するように、プロセッサ205は、2/3領域の種類毎に、ステップ450で選択した候補位置検出パターンが許容ゾーンにあるか、許容ゾーンにあるのであれば、位置検出パターンの候補対がそのような種類の有効な2/3領域を規定しているかを判定するステップを実行する。以下に更に詳細に説明するように、ステップ470において、プロセッサ205は、候補位置検出パターンを占めるように許容ゾーンを変更するステップを更に実行する。
【0071】
特に、ステップ450の後、方法400はステップ460に進み、プロセッサ205は、中心位置検出パターンと候補位置検出パターンを含む位置検出パターンの候補対を解析し、どのような有効な2/3領域の種類(例えば、領域301、302、303)が位置検出パターンの候補対から形成されるかを決定する。
【0072】
図7を参照して、ステップ460で実行されたように位置検出パターンの一対を解析する方法700を以下に詳細に説明する。方法700は、ハードディスクドライブ210上に常駐し且つ実行中にプロセッサ205により制御されるソフトウェアアプリケーションプログラム233の1つ以上のコードモジュールとして実現されてもよい。
【0073】
説明のために、図5の例示的なネットワーク500を参照して方法700を説明する。位置検出パターン510を中心位置検出パターンであるとすると、ステップ460の開始時の候補リストは、最初に候補リストに追加される隣接位置検出パターン530、540及び550を含み、位置検出パターン530が第1の候補位置検出パターンとして選択される。
【0074】
図7のステップ710〜770は、クイックレスポンス2/3領域の3つの種類(すなわち、図3A〜図3Cを参照して上述したような、2/3−領域303、2/3+領域302及び2/3/領域301のそれぞれ)に渡って反復される。
【0075】
「選択」ステップ710において、繰り返しの始めについて領域の種類(例えば、301、302、303)がプロセッサ205により選択される。選択された領域の種類の詳細は、メモリ206内に更に格納されてもよい。
【0076】
「変換」ステップ720において、ステップ430で初期化された標準的な許容ゾーン600は、選択された2/3クイックレスポンス領域の種類に従って変換される。特に、選択されたクイックレスポンス領域の種類が2/3/領域301である場合には、これが標準的な許容ゾーン600であるため変換は必要ない。しかしながら、選択されたクイックレスポンス領域の種類が2/3+領域302である場合には、標準的な許容ゾーン600は、標準的な許容ゾーン600を1/√2で変倍して45°反時計回りに回転させることにより、2/3+許容ゾーンに変換される。
【0077】
図6Bは、初期の標準的な許容ゾーン600の変形バージョン620を示す。図6Bに示されるように、標準的な許容ゾーン600は、標準的な許容ゾーン600を1/√2で変倍して45°反時計回りに回転させることにより変換され、変形バージョン620を生成している。変換された後、位置検出パターンは、中心位置検出パターン630の主軸に近接することを許可されるのみである。
【0078】
あるいは、選択されたクイックレスポンス領域の種類が2/3−領域303である場合には、標準的な許容ゾーン600は、標準的な許容ゾーン600を1/√2で変倍して45°だけ時計回りに回転させることにより、2/3−許容ゾーンに変換される。
【0079】
「決定」ステップ730において、プロセッサ205は、中心位置検出パターン(例えば、630)から候補位置検出パターンへのベクトルを決定する。決定されたベクトルは、候補位置検出パターンが中心ノード(例えば、中心位置検出パターン630)の変換された許容ゾーン(例えば、変形バージョン620)内にあるかを判定するために使用される。候補位置検出パターンが中心ノード(例えば、中心位置検出パターン630)の変換された許容ゾーン(例えば、変形バージョン620)内にあるとプロセッサ205が判定した場合、方法700は「決定」ステップ740に継続する。そうでなければ、方法700は「決定」ステップ750に進む。
【0080】
「決定」ステップ740において、中心位置検出領域及び候補位置検出領域(即ち、候補対)が有効な2/3領域の一対を規定している(即ち、候補対はクイックレスポンスバーコードに対応している)とプロセッサ205が判定した場合、方法700はステップ760に進む。さもなければ、方法700はステップ770に進む。
【0081】
位置検出パターンの候補対の有効性は、中心位置検出パターン及び候補位置検出パターンの角度及びサイズを調査することに基づいて判定される。図8は、例示的な中心位置検出パターン810及び候補位置検出パターン820を示す。図示されるように、位置検出パターン810及び820の角度は、それぞれ、θ1及びθ2である。位置検出パターン810及び820の幅は、それぞれ、W1及びW2である。2つの位置検出パターン810及び820の角度θ1及びθ2、並びに幅W1及びW2が、所定の許容範囲内で同一である場合には、2/3領域の一致が確立されており、位置検出パターン810及び820は、有効な一対を規定している(即ち、位置検出パターン810及び820は、潜在的なクイックレスポンスバーコードに対応している)。角度について適切な所定の許容範囲は10度である。大きさについて適切な所定の許容範囲は20%である。
【0082】
位置検出パターン810及び820の一対が有効な2/3領域(例えば、領域301、302、303)を規定している場合、候補対及び領域の種類を含む潜在的な領域は、「追加」ステップ760において、先にステップ450で作成された2/3領域のリストに追加される。上述したように、2/3領域のリストは、メモリ206又はハードディスクドライブ210内に格納されるようにしてもよい。
【0083】
「追加」ステップ770において、中心位置検出パターンではなく、候補リストになく、且つ以前に中心位置検出パターンに対する候補位置検出パターンではなかった候補位置検出パターンの全ての隣接位置検出パターンが、メモリ206内に格納された候補リストに追加される。候補位置検出パターンの隣接位置検出パターンが中心位置検出パターンと有効な2/3領域の一対を更に形成してもよいので、ステップ770が実行される。ステップ770において候補リストに追加される各位置検出パターンの親位置検出パターンとして、現在の候補位置検出パターンがメモリ206内に格納されている。
【0084】
図5の先の例に戻ると、位置検出パターン510が中心位置検出パターンであり、且つ位置検出パターン530が候補位置検出パターンである場合、ステップ770において、位置検出パターン560及び570が候補リストに追加され、位置検出パターン510は中心位置検出パターンであり、位置検出パターン540及び550は既に候補リストに追加されている。
【0085】
ステップ770の後、方法700は「決定」ステップ780に進む。
【0086】
ステップ730において候補位置検出パターンが中心ノード630の変換された許容ゾーン620内にないとプロセッサ205が判定した場合には、方法700はステップ750に進む。ステップ750において、プロセッサ205は、候補位置検出パターンの隣接位置検出パターンがメモリ206内に構成された候補リストに追加されるべきであるかを判定する。特に、プロセッサ205は、現在の候補位置検出パターンの親位置検出パターンと候補位置検出パターンとの間のエッジ(境界)を、変換された許容ゾーン620により規定される許容領域の境界と比較するステップを実行する。変換された許容ゾーン620により規定される許容領域境界にエッジが交差する場合には、方法700は上述したステップ770に進み、現在の候補位置検出パターンの隣接位置検出パターンが、メモリ206内に構成された候補リストに追加される。
【0087】
また、変換された許容ゾーン620により規定される許容領域境界にエッジが交差しない場合には、処理はステップ780に進み、隣接位置検出パターンは候補リストに追加されない。
【0088】
エッジが許容領域境界に交わる場合にのみ無効の位置検出パターンの隣接位置検出パターンを追加することは、変換された許容ゾーン620により規定される許容領域の外側で探索が2つのステップのみ進む以外は、許容領域の内側の全ての位置検出パターンが発見されることを保証する。
【0089】
もう1度図5の例を考慮すると、位置検出パターン510が中心位置検出パターンである場合、位置検出パターン570は候補位置検出パターンであり且つ位置検出パターン530はその候補位置検出パターンの親であり、位置検出パターン530から位置検出パターン570へのパスが調べられる。親位置検出パターン530が位置検出パターン510の許容ゾーンにあり且つ候補位置検出パターン570が位置検出パターン510の許容ゾーンの外側にある場合、方法700はステップ780に進む。そうでなければ、方法700はステップ770に進む。
【0090】
繰り返しの最後の「決定」ステップ780において、テストすべき更なる2/3領域の種類(例えば、領域301、302、303)があるとプロセッサ205が判定した場合には、方法700はステップ710に戻る。そうでなければ、方法700を終了する。
【0091】
もう1度図4に戻ると、ステップ460に続いて、方法400はステップ470に進む。ステップ470において、プロセッサ205は、ステップ450で選択された候補位置検出パターンの場所に基づいて、標準的な許容ゾーン(例えば、許容ゾーン600)を変更するステップを実行する。例えば、標準的な許容ゾーン(例えば、許容ゾーン600)を候補位置検出パターンの場所に基づいて縮小する。
【0092】
クイックレスポンスコード規格は、位置検出パターンがクイックレスポンスバーコードの内側にあり得ないことを規定している。それゆえに、標準的な許容ゾーン(例えば、許容ゾーン600)は、現在の候補位置検出パターンが標準的な許容ゾーン(例えば、許容ゾーン600)内部にある(すなわち、候補位置検出パターンは内部位置検出パターンとして分類されてもよい)2/3クイックレスポンス領域を生じるあらゆる位置検出パターンを考慮から除外するように、ステップ470で変更されてもよい。
【0093】
候補位置検出パターンが中心位置検出パターンとどのような2/3領域(例えば、領域301、302、303)を形成したかに関係なく、標準的な許容ゾーン(例えば、許容ゾーン600)は変更される。しかしながら、位置検出パターンと関連付けられた信頼値を返す幾つかの位置検出パターンの検出方法がある。従って、いくつかの実現例において、候補位置検出パターンに対する信頼値が所定の閾値を下回る場合には、ステップ470はスキップされるようにしてもよい。
【0094】
ステップ470において、プロセッサ205は、中心位置検出パターンから候補位置検出パターンまでの距離を決定するステップを実行する。その後、決定された距離は、1/√2で乗算されるが、中心位置検出パターンと2/3/領域を形成する候補位置検出パターンについては最終的な最長許容距離を形成している。特に、中心位置検出パターンから最終的な最長許容距離以上のところにあり且つ候補位置検出パターン910を中心とした90°の弧内にあるあらゆる候補位置検出パターンは、内部位置検出パターン910と2/3/領域を規定するであろう。ステップ470において、標準的な許容ゾーンの距離は、先の許容距離が決定された距離を上回る場合には常に、結果として、決定された距離に対して90°の弧内で減少(又は縮小)される。例えば、候補位置検出パターン910が与えられたとすると、陰影をつけたエリア920は、中心位置検出パターン630及び候補位置検出パターン910を含む候補対に対して決定された除外領域を表している。従って、ステップ470の結果、候補対に対して、画像のエリア内で除外領域が決定されることになる。元の標準的な許容ゾーン600から、決定された除外領域920を除去することにより、より小さな許容ゾーン930が得られる。従って、プロセッサ205は、許容ゾーン930内にあり且つ除外領域920に重なる画像エリアを、元の標準的な許容ゾーン600から除去するステップを実行する。
【0095】
新しく、縮小されたより小さい標準的な許容ゾーン930は、方法700のステップ720に関して上述した変換について有効である。標準的な許容ゾーン930により規定される縮小エリアは、2/3/領域が候補位置検出パターンを内部位置検出パターンとして有するのを防ぐ。標準的な許容ゾーン930により規定される同じ縮小エリアは、2/3−許容ゾーン及び2/3+許容ゾーンを生成するようにステップ720で変換された場合に、2/3−領域303及び2/3+領域302がそれぞれ、候補位置検出パターンを内部位置検出パターンとして有することも防ぐ。
【0096】
図10A、図10B及び図10Cを参照して、ステップ470におけるような標準的な許容ゾーン600の縮小(又は変形)を更に説明する。
【0097】
図10Aに示されるように、領域1010は、図10Aに示された位置検出パターン1011及び1012の一対に対する標準的な除外領域である。例に従って、図10Bに示されるように、領域1020は、2/3+領域について変換された後の(ステップ720におけるように)標準的な除外領域1010を表す。
【0098】
図10Bに示されるように、除外領域1020において位置検出パターンと形成するあらゆる2/3+領域は、その2/3+領域の内側に候補位置検出パターン1012を有する。一対が2/3+領域を規定する場合で、別の位置検出パターンが除外領域1020内にある場合には、プロセッサ205は、中心位置検出パターン1011及びその別の候補位置検出パターンを含む位置検出パターンの候補対を廃棄するステップを実行する。
【0099】
同様に、図10Cに示されるように、領域1030は、2/3−領域について変換された後の標準的な除外領域1010を表す。この場合も、ゾーン1030において位置検出パターンと形成するあらゆる2/3−領域は、除外領域1030の内側に候補位置検出パターン1012を有するので、上述したように、そのような2/3−領域を規定するあらゆるペアリング(一対化)は無効とされる。
【0100】
「決定」ステップ480において、プロセッサ205は、メモリ206に格納された候補リストから現在の候補位置検出パターンを廃棄(又は削除)するステップを実行する。更にステップ480において、メモリ206に格納された候補リストに更なる候補位置検出パターンがあるとプロセッサ205が判定した場合には、方法400はステップ450に戻る。そうでなければ、方法400はステップ490に進む。
【0101】
次に、「決定」ステップ490において、中心位置検出パターン(又は中心ノード)として処理されていない何らかの位置検出パターンが候補リストにあるとプロセッサ205が判定した場合には、方法400はステップ420に進む。そうでなければ、方法400は最後のステップ495に進む。
【0102】
「出力」ステップ495において、ステップ740で識別された全ての有効な2/3領域を含む2/3領域のリストが出力される。例えば2/3領域のリストは、メモリ206又はハードディスクドライブ210に格納されるようにしてもよく、あるいはソフトウェアアプリケーション233の別のコードモジュールに渡されてもよい。
【0103】
一実現例において、プロセッサ205は、位置検出パターンの候補対をトリプレットに合成するステップを実行してもよい。また、2/3領域は、特定のクイックレスポンスバーコードの3つの位置検出パターンが全て存在する場合には、完全な3/3領域にマージされるようにしてもよい。候補対が解析されて許容領域が縮小(又は変形)する順序のために、3つの位置検出パターンが全て存在するのであれば、クイックレスポンスバーコード領域は、少なくとも1回2/3+領域として及び少なくとも1回2/3−領域として識別される。従って、例えばプロセッサ205は、図3Bに示されたように各2/3+領域の一対を調査し且つ位置検出パターン330が他の位置検出パターンと何らかの2/3−領域を形成するかを判定するステップを実行してもよい。位置検出パターン330が他の位置検出パターンと何らかの2/3−領域を形成するとプロセッサ205が判定した場合に、位置検出パターンのトリプレットは、位置検出パターンのトリプレットにより形成された「L」形状を確認し、且つ上述したような位置検出パターンの角度及び大きさを確認することにより、クイックレスポンス規格に準拠しているかをテストされるようにしてもよい。位置検出パターンのトリプレットが準拠する場合、位置検出パターンのトリプレットは、メモリ206内に構成された出力3/3領域リストに追加されてもよく、関連付けられた2/3領域は出力2/3領域リストから削除されてもよい。
【0104】
一実現例において、冗長化している2/3領域は、除外され且つ廃棄されてもよい。例えば、第1の位置検出パターンが中心位置検出パターンである場合に発見された2/3領域が、第2の位置検出パターンが中心位置検出パターンである場合に再度発見される場合があるので、幾つかの2/3領域は倍となる。更に、2/3−領域は二重の2/3+領域を有し、2/3/領域は二重の2/3/領域を有する。従って、冗長化している2/3領域は、除外され且つ廃棄されるようにしてもよい。
【0105】
説明した方法に従って決定された3/3領域及び残りの2/3領域は、ISO/IEC18004において説明したようにその後クイックレスポンス復号器に入力され、領域内で符号化されたあらゆるデータを取得するようにしてもよい。
【産業上の利用可能性】
【0106】
説明された構成は、コンピュータ及びデータ処理業界、並びに特に処理バーコードに適用可能である。
【0107】
上記の記述は本発明のいくつかの実施形態のみを説明し、本発明の範囲及び趣旨から逸脱せずに、変形及び/又は変更がいくつかの実施形態に対して行なわれてもよい。実施形態は、限定するものではなく例示するものである。
【0108】
本明細書に関して、「備える」という言葉は、「主に含むが、単独で必要ではない」、あるいは「有する」又は「含む」ことを意味し、「のみから構成される」ことではない。「備える」の語形変化は、それに対応して意味の変化を示す。
【技術分野】
【0001】
本発明は、2次元バーコードに関し、特にバーコードの位置検出パターンの候補対を識別する方法及び装置に関する。更に本発明は、バーコードの位置検出パターンの候補対を識別するコンピュータプログラムが記録されたコンピュータ可読媒体を含むコンピュータプログラムに関する。
【背景技術】
【0002】
2次元バーコードは、1次元バーコードと比較してデータ容量が大きく、且つそのようなバーコードに対する符号化デバイス及び復号化デバイスの利用可能性が高まってきているため、益々普及している。
【0003】
「クイックレスポンス(QR)バーコード」として既知である2次元バーコードは、特に一般的な2次元バーコードである。図1は、クイックレスポンスバーコード100の一例を示す。図1に示されるように、クイックレスポンスバーコード100は、正方画素の正方配列である。各正方画素は、「モジュール」(例えば、白色モジュール101及び黒色モジュール102)と呼ばれる。モジュールは、データを符号化するために使用される。
【0004】
データを符号化するために使用されるモジュールに加え、クイックレスポンスバーコード100は、3つの場所・識別シンボル103を含む。3つの場所シンボル103は、それぞれ「位置検出バターン」(FP)として既知である。図1に示されるように、位置検出パターン103は、クイックレスポンスバーコード100の左上の隅、右上の隅及び左下の隅に配置される。従って、クイックレスポンスバーコードにより占有された画像の2次元エリアは、3つの位置検出バターン103の場所により画設される。そのような2次元エリアは、「クイックレスポンスバーコード領域」としても既知である。
【0005】
クイックレスポンスバーコード100等のクイックレスポンスバーコードを復号化する第1のステップは、上述の位置検出パターン103を使用して入力画像中のバーコード100を識別することである。
【0006】
クイックレスポンスバーコードは、製品ラベル、広告掲示板及び名刺等の幅広い媒体上に頻繁に含まれる。従来、そのような媒体は、高品質の単一のクイックレスポンスバーコードのみを含んでいる(すなわち、元のクイックレスポンスバーコードのデジタル画像は、媒体上に正確に再現されている)。従って、クイックレスポンスバーコードが復号化される場合には、取得された画像に単一のクイックレスポンスバーコードのみがあり且つバーコードの品質が高いことが、相対的に単純な復号化処理の使用を容易にする。また、カメラ電話等の従来のクイックレスポンスバーコード撮像デバイスは、クイックレスポンスバーコードの画像が非常に少ない回転位置合わせ誤差で取得されるように、ユーザにより調整される場合がある。ユーザにより調整された撮像デバイスは更に、クイックレスポンスバーコード中のモジュール(例えば、白色モジュール101)のサイズが撮像デバイスに対して既知の範囲内にあるように、クイックレスポンスバーコードをフレーム化する。
【0007】
最近、ドキュメントセキュリティ及びワークフロー管理を支援することにおいて、クイックレスポンスバーコードの活用に対する関心が高まってきている。そのようなアプリケーションの場合、取得された画像中に複数のクイックレスポンスバーコードがある場合がある。更に、画像中のクイックレスポンスバーコードのモジュールのサイズ及び向きは様々である場合が多い。更にクイックレスポンスバーコードは、何度も印刷、スキャン及び再印刷される場合があり、その度にクイックレスポンスバーコードの画像品質が低下する。特に、クイックレスポンスバーコードは、クイックレスポンスバーコード中の黒色モジュールのサイズと白色モジュールのサイズとの比が理想的な1:1から大幅にずれる「ドットゲイン」の影響を受ける可能性が高い。例えば、印刷及びスキャンの複数サイクルにより、位置検出パターン103と比較してクイックレスポンスバーコードの位置検出パターンの外観を更に変化させるような他の歪み及びノイズを更に招いてしまう。
【0008】
クイックレスポンスバーコード復号器のリファレンス実装は、ISO/IEC18004規格で入手可能である。しかしながら、ISO/IEC18004規格におけるリファレンス実装は、画像中にクイックレスポンスバーコードが1つのみであることを仮定し、且つ、ちょうど3つの位置検出パターンが検出されることを仮定している。また、非検出位置検出パターン若しくは偽陽性位置検出パターンは、ISO/IEC18004規格では考慮されない。
【0009】
非検出位置検出パターンは、ノイズ又は他の歪みの中においてはよく見かけられ、偽陽性位置検出パターンの検出は、特に日本語又は中国語のテキストにおいてはよく見かけられる。従って、位置検出パターンは一旦検出されると、クイックレスポンスバーコードの位置検出パターンを識別するために、「分割される」必要がある。従来、所定の許容範囲内で各々が同一の大きさ及び同一の角度を有する正方形の「L」字型を形成する位置検出パターンのトリプレットは、位置検出パターンがクイックレスポンスバーコードのものであることを識別するために、検出され且つ分割される必要がある。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】ISO/IEC18004規格
【発明の概要】
【発明が解決しようとする課題】
【0011】
クイックレスポンスバーコードを識別するように位置検出パターンを分割する1つの方法には、クイックレスポンス規格に準拠するように検出された位置検出パターンの考えられるだけのトリプレットをテストすることが含まれる。そのような方法での実行時間は、解析される位置検出パターン数の三乗で増加するため、この方法は「O(n3)方法」と呼ばれる。いくつかの応用例においては、O(n3)方法が受け入れられるであろう。しかしながら、特にクイックレスポンスバーコードの復号化は、限られたメモリ及び処理能力を有する組込み型デバイス上で頻繁に要求されるので、検出された位置検出パターン数が増加するにつれて、O(n3)方法は非実用的なものになってしまう。
【0012】
本発明の目的は、既存の構成の1つ以上の欠点を実質的に克服するか、あるいは少なくとも改善することである。
【課題を解決するための手段】
【0013】
本発明の一態様によると、2次元バーコードの位置検出パターンの候補対を識別する方法であって、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する工程と、
(ii)残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する工程と、
(iii)候補対について、画像のエリア内で除外領域を決定する工程と、
(iv)別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する工程と、
(v)除外領域に重なる許容ゾーン内のエリアを、許容ゾーンから除去する工程と、
(vi)2次元バーコードの位置検出パターンの候補対を識別するために、1つ以上の更に別の位置検出パターンについて、ステップ(ii)〜(v)を繰り返す、ことを特徴とする方法が提供される。
【0014】
本発明の別の態様によると、2次元バーコードの位置検出パターンの候補対を識別する装置であって、
画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する手段と、
残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する手段と、
候補対について、画像のエリア内で除外領域を決定する手段と、
別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する手段と、
2次元バーコードの位置検出パターンの候補対を識別するために、除外領域に重なっている許容ゾーン内のエリアを、許容ゾーンから除去する手段とを備える装置が提供される。
【0015】
本発明の更に別の態様によると、2次元バーコードの位置検出パターンの候補対を識別するシステムであって、
データ及びコンピュータプログラムを格納するメモリと、
コンピュータプログラムを実行するメモリに結合されたプロセッサとを備え、コンピュータプログラムが、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する命令と、
(ii)残りの複数の検出された位置検出パターンから別の位置検出パターンを選択し、第1の位置検出パターン及び別の位置検出パターンを含む候補対を形成する命令と、
(iii)候補対について、画像のエリア内で除外領域を決定する命令と、
(iv)別の位置検出パターンが画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの候補対を廃棄する命令と、
(v)除外領域に重なっている許容ゾーン内の画像のエリアを許容ゾーンから除去する命令と、
(vi)2次元バーコードの位置検出パターンの候補対を識別するために、1つ以上の更に別の位置検出パターンについて、ステップ(ii)〜(v)を繰り返す命令とを含むシステムが提供される。
【0016】
本発明の別の態様によると、上述した方法を実現するコンピュータプログラムを記録したコンピュータ読取可能な媒体を含むコンピュータプログラムが提供される。
【0017】
本発明の他の態様が更に開示される。
【図面の簡単な説明】
【0018】
次に、以下の図面を参照して、本発明の1つ以上の実施形態を説明する。
【図1】図1は、黒色モジュール及び白色モジュール、並びに位置検出パターンを含むクイックレスポンスバーコードの一例を示す図である。
【図2A】、
【図2B】図2A、図2Bは、説明される構成が実施される汎用コンピュータシステムの概略ブロック図である。
【図3A】、
【図3B】、
【図3C】図3A、3B、3Cは、クイックレスポンスバーコードに対する3つの可能な2/3領域構成を示す図である。
【図4】図4は、バーコードの位置検出パターンの候補対を識別する方法を概略的に示すフローチャートである。
【図5】図5は、各々がネットワークのノードにより表される位置検出パターンの例示的なネットワークの三角形分割を示す図である。
【図6A】図6Aは、「中心」位置検出パターンの周囲の標準的な許容ゾーンを示す図である。
【図6B】図6Bは、2/3+許容ゾーンに変換された図6Aの標準的な許容ゾーンを示す図である。
【図7】図7は、図4の方法で使用されるような中心位置検出パターン及び「候補」位置検出パターンを含む位置検出パターンの一対を解析する方法を概略的に示すフローチャートである。
【図8】図8は、解析される例示的な中心位置検出パターン及び候補位置検出パターンの角度及び大きさを示す図である。
【図9】図9は、候補位置検出パターンにより形成された除外領域に係る許容ゾーンの変形の一例を示す図である。
【図10A】、
【図10B】、
【図10C】図10A、10B、10Cは、候補位置検出パターンにより形成された図9の除外領域の変換の一例を示す図である。
【発明を実施するための形態】
【0019】
添付の図面のうちのいずれか1つ以上において、同一の参照符号を有するステップ及び/又は特徴が参照される。逆の意図が示されない限り、これらのステップ及び/又は特徴は、本明細書の目的のために同一の機能又は動作を有する。
【0020】
尚、「背景」の節に含まれる説明及び先行技術の構成に関連する上述のものは、それぞれの公表及び/又は用途を介して周知の知識を形成する文書又はデバイスの説明に関連している。そのようなものが本発明者又は本特許出願人により表現されたものとして解釈されるべきではなく、そのような文献又はデバイスは、当技術分野における一般常識の一部を何らかの形で形成するものである。
【0021】
図4を参照して、バーコードの位置検出パターンの候補対を識別する方法400を以下に説明する。方法400は、画像中で検出された位置検出パターンを含む「入力」リストを解析し、一組の候補位置検出パターン対を出力する。出力された位置検出パターン対は、2次元バーコードの部分を形成するのに適した構成である。方法400は、種々のサイズ又は角度を有する無効な空間関係にある位置検出パターン対を廃棄するステップを実行する。
【0022】
方法400は、一般的に2次元バーコードに適用可能である。しかしながら、説明を簡単にするために、クイックレスポンスバーコードを参照して方法400のステップを説明する。本発明を説明する方法に限定されることを意図するものではない。例えば方法400は、「PDF417」バーコード及び「データマトリックス」バーコード等の他のあらゆる種類の2次元バーコードに適用されてもよい。
【0023】
図2A及び図2Bは、説明される種々の構成が実施される際の汎用的なコンピュータシステム200を示す。
【0024】
図2Aに示されるように、コンピュータシステム200は、コンピュータモジュール201、キーボード202、マウス・ポインティングデバイス203、スキャナ226、カメラ227及びマイク280等の入力デバイス、並びにプリンタ215、表示装置214及びスピーカ217を含む出力デバイスを含む。外部変復調器(モデム)送受信機デバイス216は、接続221を介して通信ネットワーク220と通信するためにコンピュータモジュール201により使用されてもよい。通信ネットワーク220は、インターネット、セルラ電気通信ネットワーク等のワイドエリアネットワーク(WAN)又は専用WANであってもよい。接続221が電話線である場合、モデム216は従来の「ダイヤルアップ」モデムであってもよい。あるいは、接続221が大容量(例えば、ケーブル)接続である場合、モデム216はブロードバンドモデムであってもよい。無線モデムは、通信ネットワーク220に無線接続するために更に使用されてもよい。
【0025】
コンピュータモジュール201は、一般的に、少なくとも1つのプロセッサユニット205及びメモリユニット206を含む。例えばメモリユニット206は、半導体ランダムアクセスメモリ(RAM)及び半導体読み出し専用メモリ(ROM)を有してもよい。コンピュータモジュール201は、ビデオディスプレイ214に結合するオーディオ/ビデオインタフェース207、スピーカ217及びマイク280を含む多数の入出力(I/O)インタフェース、キーボード202、マウス・ポインティングデバイス203、スキャナ226、カメラ227及びオプションとしてジョイスティック又はヒューマンインタフェースデバイス(不図示)に結合するI/Oインタフェース213、並びに外部モデム216及びプリンタ215用のインタフェース208を更に含む。いくつかの実施例において、モデム216は、インタフェース208等のコンピュータモジュール201内に組み込まれてもよい。コンピュータモジュール201は、接続223を介してコンピュータシステム200がローカルエリアネットワーク(LAN)として既知であるローカルエリア通信ネットワーク222に接続できるようにするローカルネットワークインタフェース211を更に有する。図2Aに示されるように、ローカル通信ネットワーク222は、一般的にいわゆる「ファイアウォール」デバイス又は同様の機能性を備えたデバイスを含むワイドネットワーク220に接続224を介して更に結合してもよい。ローカルネットワークインタフェース211は、Ethernet(登録商標)回路カード、Bluetooth(登録商標)無線装置又はIEEE802.11無線装置を備えてもよいが、多数の他の種類のインタフェースがインタフェース211に対して実施されてもよい。
【0026】
I/Oインタフェース208及び213は、直列接続性及び並列接続性のいずれか一方又は双方を提供してもよい。一般的に直列接続性は、USB(Universal Serial Bus)規格に従って実現され且つ対応するUSBコネクタ(不図示)を有する。記憶装置209が提供され、一般的に記憶装置209は、ハードディスクドライブ(HDD)210を含む。フロッピディスクドライブ及び磁気テープドライブ(不図示)等の他の記憶装置が更に使用されてもよい。オプションのディスクドライブ212は、一般的に、データの不揮発性ソースとして動作するように提供される。例えば、光ディスク(例えば、CD−ROM、DVD、Blu−ray Disc(登録商標))、USB−RAM、取り外し可能な外部ハードドライブ及びフロッピディスク等のポータブルメモリ装置は、システム200に対する適切なデータソースとして使用されてもよい。
【0027】
コンピュータモジュール201の構成要素205〜213は、一般的に、相互接続バス204を介して通信し、且つ結果として当業者に既知であるコンピュータシステム200の動作の従来のモードから得られる方法で通信する。例えばプロセッサ205は、接続218を使用してシステムバス204に結合される。同様に、メモリ206及び光ディスクドライブ212は、接続219によりシステムバス204に結合される。説明する構成が実施されるコンピュータの例には、IBM−PC’s及び互換性のあるもの、Sun Sparcstations、Apple Mac(登録商標)又は同様のコンピュータシステムが含まれる。
【0028】
方法400を含む以下に説明する方法は、コンピュータシステム200を使用して実現されてもよい。方法において説明される図3A〜図10Cの処理は、コンピュータシステム200内で実行可能な1つ以上のソフトウェアアプリケーションプログラム233として実現されてもよい。特に、説明される方法のステップは、コンピュータシステム200内で実行されるソフトウェア233で命令231(図2Bを参照)により実施される。ソフトウェア命令231は、各々が1つ以上の特定のタスクを実行する1つ以上のコードモジュールとして形成されてもよい。ソフトウェアは2つの別個の部分に更に分割されてもよく、第1の部分及び対応するコードモジュールは説明する方法を実行し、第2の部分及び対応するコードモジュールは、第1の部分とユーザとの間のユーザインタフェースを管理する。
【0029】
例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読取可能な媒体に格納されてもよい。ソフトウェアは、コンピュータ読取可能な媒体からコンピュータシステム200にロードされ、コンピュータシステム200により実行される。そのようなソフトウェアを有するコンピュータ読取可能な媒体又はコンピュータ読取可能な媒体上に記録されたコンピュータプログラムは、コンピュータプログラム製品である。コンピュータシステム200においてコンピュータプログラムを使用することにより、説明する方法を実現する有利な装置を実施するのが好ましい。
【0030】
ソフトウェア233は、一般的にHDD210又はメモリ206に格納される。ソフトウェアは、コンピュータ読取可能な媒体からコンピュータシステム200にロードされ、コンピュータシステム200により実行される。従って、例えばソフトウェア233は、光ディスクドライブ212により読み出される光学的に読出可能なディスク記憶装置媒体(例えば、CD−ROM)225上に格納されてもよい。そのようなソフトウェアを有するコンピュータ読取可能な媒体又はコンピュータ読取可能な媒体上に記録されたコンピュータプログラムは、コンピュータプログラム製品である。コンピュータシステム200においてコンピュータプログラム製品を使用することにより、説明する方法を実現する装置を実施するのが好ましい。
【0031】
いくつかの例において、アプリケーションプログラム233は、1つ以上のCD−ROM225上でユーザが符号化したものに供給され且つ対応するドライブ212を介して読み出されてもよく、あるいはユーザによりネットワーク220又は222から読み出されてもよい。更にソフトウェアは、他のコンピュータ読取可能な媒体からコンピュータシステム200にロードされてもよい。コンピュータ読取可能な記憶媒体は、実行及び/又は処理するために、記録された命令及び/又はデータをコンピュータシステム200に提供するあらゆる非一過性(non−transitory)の有形(tangible)の記憶媒体を示す。そのような記憶媒体の例には、フロッピディスク、磁気テープ、CD−ROM、DVD、Blu−ray Disc、ハードディスクドライブ、ROM又は集積回路、USBメモリ、光磁気ディスク、あるいは例えばPCMCIAカード等のコンピュータ読取可能なカードが含まれ、そのようなデバイスは、コンピュータモジュール201の内部又は外部にある。ソフトウェア、アプリケーションプログラム、命令及び/又はデータをコンピュータモジュール101に提供することに更に関連してもよい一過性又は非一過性のコンピュータ読取可能な伝送媒体の例には、無線送信チャネル又は赤外線送信チャネル及び別のコンピュータ又はネットワーク化されたデバイスへのネットワーク接続、並びに電子メール送信及びウェブサイト上等に記録された情報を含むインターネット又はイントラネットが含まれる。
【0032】
上述したアプリケーションプログラム233の第2の部分及び対応するコードモジュールは、ディスプレイ214上にレンダリングされるか若しくは表される1つ以上のグラフィカルユーザインタフェース(GUI)を実現するように実行されてもよい。一般的にキーボード202及びマウス・ポインティングデバイス203を操作することにより、コンピュータシステム200及びアプリケーションのユーザは、GUIと関連付けられたアプリケーションに制御コマンド及び/又は入力を提供するように機能的に適応可能な方法でインタフェースを操作してもよい。他の形式の機能的に適応可能なユーザインタフェース、例えばスピーカ217を介して出力された音声プロンプト及びマイク280を介して入力されたユーザ音声コマンドを利用するオーディオインタフェースが更に実現されてもよい。
【0033】
図2Bは、プロセッサ205及び「メモリ」234を示す詳細な概略ブロック図である。メモリ234は、図2Aのコンピュータモジュール201によりアクセスされる全てのメモリモジュール(HDD210及び半導体メモリ206を含む)の論理的な集約を示す。
【0034】
コンピュータモジュール201が最初に電源投入される場合、自己診断(POST)プログラム250が実行される。一般的にPOSTプログラム250は、図2Aの半導体メモリ206のROM249に格納される。ソフトウェアを格納するROM249等のハードウェアデバイスは、ファームウェアと呼ばれる場合もある。POSTプログラム250は、コンピュータモジュール201内のハードウェアを調査して適切に機能することを保証し、一般的に、正しく動作するためにROM249に更に格納されたプロセッサ205、メモリ234(209、206)及び基本入出力システム(BIOS)ソフトウェアモジュール251をチェックする。POSTプログラム250が正常に実行されると、BIOS251は図2Aのハードディスクドライブ210を起動する。ハードディスクドライブ210を起動することにより、ハードディスクドライブ210上に常駐するブートストラップ・ローダプログラム252がプロセッサ205を介して実行される。これにより、オペレーティングシステム253は、RAMメモリ206にロードされると動作を開始する。オペレーティングシステム253は、プロセッサ205により実行可能なシステムレベルのアプリケーションであり、プロセッサ管理、メモリ管理、デバイス管理、ストレージ管理、ソフトウェアアプリケーションインタフェース及び汎用ユーザインタフェースを含む種々のハイレベルな機能を遂行する。
【0035】
オペレーティングシステム253は、メモリ234(209、206)を管理し、コンピュータモジュール201上で実行する処理又はアプリケーションの各々が別の処理に割り当てられたメモリと衝突することなく実行するだけの十分なメモリを有することを保証する。また、図2Aのシステム200で使用可能な種々のメモリは、各処理が効率的に実行するように適切に使用される必要がある。従って、集約メモリ234は、メモリの特定の部分が割り当てられる方法を示すことを意図せず(明示的に記載されない限り)、コンピュータシステム200によりアクセス可能なメモリの概略図及びそのようなメモリが使用される方法を提供する。
【0036】
図2Bに示されるように、プロセッサ205は、制御ユニット239、演算論理装置(ALU)240及びキャッシュメモリと呼ばれることもあるローカルメモリ又は内部メモリ248を含む多数の機能モジュールを含む。一般的にキャッシュメモリ248は、レジスタ部に複数の記憶レジスタ244〜246を含む。1つ以上の内部バス241は、これらの機能モジュールを機能的に相互接続する。一般的にプロセッサ205は、接続218を使用してシステムバス204を介して外部デバイスと通信する1つ以上のインタフェース242を更に有する。メモリ234は、接続219を使用してバス204に結合される。
【0037】
アプリケーションプログラム233は、条件付き分岐命令及びループ命令を含んでもよい一連の命令231を含む。プログラム233は、プログラム233を実行するのに使用されるデータ232を更に含んでもよい。命令231及びデータ232は、それぞれ、記憶場所228、229、230及び235、236、237に格納される。命令231及びメモリの記憶場所228〜230の相対的なサイズに依存して、特定の命令は、記憶場所230に示された命令により描かれるように単一の記憶場所に格納されてもよい。あるいは、命令は、メモリの記憶場所228及び229に示される命令部分により描かれるように、各々が別個のメモリの記憶場所に格納される多数の部分に分割されてもよい。
【0038】
一般的にプロセッサ205は、そこで実行される命令の集合を与えられる。プロセッサ205は、命令の別の集合を実行することによりプロセッサ205自身が反応する後続の入力を待つ。各入力は、入力デバイス202、203の1つ以上により生成されたデータ、ネットワーク220、222のうちの一方を介して外部ソースから受信したデータ、記憶装置206、209のうちの一方から検索したデータ又は対応する読取装置212に挿入された記憶媒体225から検索したデータを含む多数のソースのうちの1つ以上から提供されてもよく、その全てが図2Aに示されたものである。いくつかの例において、命令の集合を実行した結果、データが出力されてもよい。実行することは、データ又は変数をメモリ234に格納することを更に含んでもよい。
【0039】
説明する方法は、対応するメモリの記憶場所255、256、257においてメモリ234に格納される入力変数254を使用する。説明する方法は、対応するメモリの記憶場所262、263、264においてメモリ234に格納される出力変数261を生成する。中間変数258は、メモリの記憶場所259、260、266及び267に格納されてもよい。
【0040】
図2Bのプロセッサ205を参照すると、レジスタ244、245、246、演算論理装置(ALU)240及び制御ユニット239は、プログラム233を構成する命令集合において命令毎に「取り込み、復号化及び実行」サイクルを実行するのに必要なマイクロ動作のシーケンスを実行するように共に動作する。取り込み、復号化及び実行サイクルの各々は、
(a)メモリの記憶場所228、229、230からの命令231を取り込むかあるいは読み取る取り込み動作、
(b)制御ユニット239が、取り込まれた命令を判定する復号化動作、並びに
(c)制御ユニット239及び/又はALU240が命令を実行する命令動作を含む。
【0041】
その後、次の命令に対する更なる取り込み、復号化及び実行サイクルが実行されてもよい。同様に、制御ユニット239が値をメモリの記憶場所232に格納するかあるいは書き込むことにより、格納サイクルが実行されてもよい。
【0042】
図4〜図10の処理におけるステップ又はサブ処理の各々は、プログラム233の1つ以上の部分と関連付けられ、プログラム233の示された部分に対して命令集合の命令毎に取り込み、復号化及び実行サイクルを実行するようにプロセッサ205のレジスタ部244、245、247、ALU240と制御ユニット239が共に動作することにより実行される。
【0043】
あるいは、説明される方法は、説明される方法の機能又はサブ機能を実行する1つ以上の集積回路等の専用ハードウェアで実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ又は1つ以上のマイクロプロセッサ及び関連付けられたメモリを含んでもよい。
【0044】
以下に詳細に説明するように、検出された位置検出パターンを可能な2次元バーコードに分割(resolve)するO(n3)方法は、位置検出パターンのトリプレットではなく、位置検出パターンの「候補対」を決定するように変更されてもよい。位置検出パターンの候補対の各々は、以下において「2/3領域」と呼ばれるものを形成する。対応するクイックレスポンスバーコードの3つの位置検出パターンのうちの2つが検出されるため、候補対は2/3領域と呼ばれる。
【0045】
図3A、図3B及び図3Cに示されるように、クイックレスポンスバーコード100に対して3つの可能な2/3領域構成がある。図3Aは、位置検出パターン103の第1の検出パターン310が位置検出パターン103の第2の位置検出パターン320とはす向かいの位置関係になっている場所に形成された「2/3/」領域301を示す。図3Bは、位置検出パターン103の2つの位置検出パターン310及び330が互いに隣接し、且つ対応するクイックレスポンスバーコード100が第2の位置検出パターン330から時計回りの方向に形成された場合の「2/3+」領域302を示す。図3Cは、位置検出パターン103の2つの位置検出パターン310及び340が互いに隣接し、且つクイックレスポンスバーコード100が第2の位置検出パターン340から反時計回りの方向に形成された場合の「2/3−」領域303を示す。
【0046】
図3B及び図3Cに示されるように、2/3+領域302及び2/3−領域303は、それぞれ、位置検出パターンの同一の構成を有する。しかしながら、以下に詳細に説明するように、許容ゾーンに対して位置検出パターンの一対をテストする際に2/3+領域の種類及び2/3−領域の種類のうちのいずれか一方又はその双方が適用可能であってもよく、あるいはそのいずれも適用可能でなくてもよいため、2/3+領域302及び2/3−領域303は別個に考慮される。
【0047】
以下に詳細に説明するように、重複する2/3領域同士が完全な3/3クイックレスポンス領域を形成するようにマージされる(あるいは、組み合わされる)場合、位置検出パターン(例えば、位置検出パターン310及び330)の候補対からのクイックレスポンスバーコード100の方向は、更に重要である。説明するように、プロセッサ205は、位置検出パターンの候補対をトリプレットに合成するステップを実行してもよい。
【0048】
図4を参照して、バーコードの位置検出パターンの候補対を識別する方法400を以下に説明する。方法400は、ハードディスクドライブ210上に常駐し且つ実行中にプロセッサ205により制御されるソフトウェアアプリケーションプログラム233のソフトウェアコードモジュールの1つとして実現されてもよい。画像の1つのエリアにおいて検出される位置検出パターンの「入力」リストが与えられたとすると、方法400は、画像のエリアにおいて2/3領域(例えば、領域301、302、又は303)を識別する。位置検出パターンの入力リストは、画像のエリアにおいて検出される複数の位置検出パターンを含む。検出される位置検出パターンを含む入力リストは、メモリ206又はハードディスクドライブ210からアクセスされるようにしてもよい。図1のクイックレスポンスバーコード100及び位置検出パターンのネットワーク500(図5を参照)を参照しながら、方法400を説明する。
【0049】
第1の「リスト作成」ステップ405において、プロセッサ205は、メモリ206又はハードディスクドライブ210内に2/3領域の空リストを作成するステップを実行する。方法400の後に続くステップ中で識別される全ての有効な2/3領域は、2/3領域のリストに連続して追加される。2/3領域のリストは、メモリ206又はハードディスクドライブ210からアクセスされるようにしてもよい。
【0050】
「ネットワーク生成」ステップ410において、位置検出パターンのネットワーク500(図5を参照)がプロセッサ205により生成される。図5の例における各位置検出パターン(例えば、位置検出パターン510)は、黒丸として示される。位置検出パターンのネットワーク500は、メモリ206に格納されるようにしてもよい。生成されたネットワーク500の各位置検出パターンは、直線「エッジ」(例えば、エッジ520)により結合される。
【0051】
ネットワーク500は、ドロネー三角形分割を使用してステップ410で生成される。あらゆる適切なO(nlogn)方法がドロネー三角形分割を実行するために使用されてもよい。
【0052】
ドロネー三角形分割は、以下の望ましい特性を有する。
【0053】
1.各ノード(即ち、位置検出パターンを表す)に接続されたエッジの平均数が6未満である。
【0054】
2.位置検出パターンを表す各ノードが別の位置検出パターンを表す最も近接する隣接ノードに接続される。
【0055】
3.一般的に、位置検出パターンを表す各ノードが、O(logk)エッジにより他の位置検出パターンを表すk番目に最も近接する隣接ノードに接続される。
【0056】
位置検出パターンを表す所定のノードから開始するネットワーク500のエッジを行き来することによって、ドロネー三角形分割は結果として、隣接位置検出パターンを表す隣接ノードを迅速に配置するために使用される場合がある。
【0057】
ステップ410の後、方法400の次のステップ420〜490は、可能な2/3領域(例えば、領域301、302、303)を繰り返して識別する。ステップ420〜490において、プロセッサ205は、順次、「中心」位置検出パターン(又はノード)としてメモリ206に格納された入力リストの位置検出パターンの各々を選択するステップを実行する。上述したように、位置検出パターンの入力リストは、画像のエリアにおいて検出された複数の位置検出パターンを含む。検出された位置検出パターンを含む入力リストは、メモリ206又はハードディスクドライブ210からアクセスされるようにしてもよい。
【0058】
ステップ420〜490において、プロセッサ205は、解析するために位置検出パターンの候補対を決定するステップを更に実行する。位置検出パターンの候補対は、ネットワーク500により示されるように、選択された中心位置検出パターンを、入力リストの残りの隣接位置検出パターンのうち少なくとも1つと連続して組み合わせることによって決定される。
【0059】
「選択」ステップ420において、まだ考慮されていない入力リストの次の(又は方法400の最初の繰り返しにおける第1の)位置検出パターンは、中心位置検出パターン(又は中心ノード)としてプロセッサ205により選択される。上述したように、選択された位置検出パターンは、画像のエリア(又は、第1のエリア)において検出された複数の位置検出パターンを含む位置検出パターンの入力リストから選択される。
【0060】
中心位置検出パターンが与えられたとして、有効な2/3領域(例えば、領域301、302、303)を規定する位置検出パターンの一対を形成してもよい隣接位置検出パターンの識別は、「許容ゾーン」を使用することによって迅速化される。許容ゾーンは、隣接位置検出パターンがある画像の部分集合を規定しており、中心位置検出パターンと一対を成す有効な位置検出パターンを潜在的に形成する。
【0061】
次に、図6Aを参照する。次のステップ430において、中心位置検出パターン630と一対になって2/3/領域(例えば、領域301)を形成可能な隣接位置検出パターンが許容されるゾーン600(即ち、「許容ゾーン」)は、プロセッサ205により初期化される。以下に説明するように、2/3+領域の例及び2/3−領域の例について対応するエリアが2/3/領域の例から導出されてもよいので、2/3+領域及び2/3−領域それぞれに対応する別個の許容ゾーンを必要としない。以下の説明において、2/3/領域許容ゾーン600を「標準的な許容ゾーン」と呼ぶ。
【0062】
一実施例において、標準的な許容ゾーン600は、セクタの連結リストとしてメモリ206内に格納される。各セクタは、特定の角度範囲内で中心位置検出パターン630から隣接位置検出パターンの最長許容距離を規定している。セクタは、角度において単調に大きくなっており、0°〜360°の全角度に渡っている。
【0063】
標準的な許容ゾーン600は、8つのセクタとして初期化される。4つのセクタ(例えば、セクタ610)は、中心位置検出パターン630に関して対角線状に位置合わせされる。対角線状に位置合わせされたセクタ(例えば、セクタ601)の最大半径は、中心位置合わせパターン630のサイズ及び大きさの許容範囲を与えるクイックレスポンスバーコード(例えば、クイックレスポンスバーコード100)の最大サイズにより規定される。例えば、適切な大きさの許容範囲は20%である。4つのセクタ(例えば、セクタ610)の幅は、所定の角度の許容範囲により規定される。適切な角度の許容範囲は、例えば20度である。
【0064】
4つの対角線状に位置合わせされたセクタ(例えば、セクタ610)に加え、初期の標準的な許容ゾーン600は、半径ゼロで介在する4つのセクタ(不図示)を含む。
【0065】
再度図4に戻ると、ステップ430の後、方法400は「リスト」ステップ440に進む。ステップ440において、位置検出パターンの「候補」リストは、プロセッサ205により確立されてメモリ206に格納される。以下に詳細に説明するように、候補リストにおける連続的な位置検出パターンは、選択された中心位置検出パターンと組み合わされる。例えば、結果として得られる位置検出パターンの一対は、結果として得られる位置検出パターンの一対がクイックレスポンスバーコード100に対して有効な2/3領域を規定するかを決定するように評価される。
【0066】
候補リストは、先に決定されたドロネー三角形分割に係る中心位置検出パターンの隣接位置検出パターンの各々を含んでいる。
【0067】
候補リストにおいて各位置検出パターンの「親」位置検出パターンとして参照される位置検出パターンも、ステップ440においてメモリ206に格納される。特定の候補位置検出パターンの親は、候補位置検出パターンを候補リストに追加した位置検出パターンである。最初の、中心位置検出パターンは、位置検出パターンの候補リストにおいて全ての位置検出パターンの親である。
【0068】
しかしながら、ステップ470で実行されるように、「他の」位置検出パターンの隣接位置検出パターンが候補リストに追加されるようにしてもよい。この例において、これらの「他の」位置検出パターンも親位置検出パターンになる。
【0069】
「選択」ステップ450において、プロセッサ205は、メモリ206に格納された候補リストから任意の(又は第2の)位置検出パターンを「候補位置検出パターン」として選択するステップを実行する。ステップ450で選択された候補位置検出パターン及びステップ420で選択された中心位置検出パターンは、共に「候補対」を形成する。従って、位置検出パターンはステップ450で候補リストにおいて検出された残りの複数の位置検出パターンから選択され、ステップ420で選択された位置検出パターン及びステップ450で選択された位置検出パターンを含む候補対を形成する。
【0070】
後続するステップ460及び470において、以下に説明するように、プロセッサ205は、2/3領域の種類毎に、ステップ450で選択した候補位置検出パターンが許容ゾーンにあるか、許容ゾーンにあるのであれば、位置検出パターンの候補対がそのような種類の有効な2/3領域を規定しているかを判定するステップを実行する。以下に更に詳細に説明するように、ステップ470において、プロセッサ205は、候補位置検出パターンを占めるように許容ゾーンを変更するステップを更に実行する。
【0071】
特に、ステップ450の後、方法400はステップ460に進み、プロセッサ205は、中心位置検出パターンと候補位置検出パターンを含む位置検出パターンの候補対を解析し、どのような有効な2/3領域の種類(例えば、領域301、302、303)が位置検出パターンの候補対から形成されるかを決定する。
【0072】
図7を参照して、ステップ460で実行されたように位置検出パターンの一対を解析する方法700を以下に詳細に説明する。方法700は、ハードディスクドライブ210上に常駐し且つ実行中にプロセッサ205により制御されるソフトウェアアプリケーションプログラム233の1つ以上のコードモジュールとして実現されてもよい。
【0073】
説明のために、図5の例示的なネットワーク500を参照して方法700を説明する。位置検出パターン510を中心位置検出パターンであるとすると、ステップ460の開始時の候補リストは、最初に候補リストに追加される隣接位置検出パターン530、540及び550を含み、位置検出パターン530が第1の候補位置検出パターンとして選択される。
【0074】
図7のステップ710〜770は、クイックレスポンス2/3領域の3つの種類(すなわち、図3A〜図3Cを参照して上述したような、2/3−領域303、2/3+領域302及び2/3/領域301のそれぞれ)に渡って反復される。
【0075】
「選択」ステップ710において、繰り返しの始めについて領域の種類(例えば、301、302、303)がプロセッサ205により選択される。選択された領域の種類の詳細は、メモリ206内に更に格納されてもよい。
【0076】
「変換」ステップ720において、ステップ430で初期化された標準的な許容ゾーン600は、選択された2/3クイックレスポンス領域の種類に従って変換される。特に、選択されたクイックレスポンス領域の種類が2/3/領域301である場合には、これが標準的な許容ゾーン600であるため変換は必要ない。しかしながら、選択されたクイックレスポンス領域の種類が2/3+領域302である場合には、標準的な許容ゾーン600は、標準的な許容ゾーン600を1/√2で変倍して45°反時計回りに回転させることにより、2/3+許容ゾーンに変換される。
【0077】
図6Bは、初期の標準的な許容ゾーン600の変形バージョン620を示す。図6Bに示されるように、標準的な許容ゾーン600は、標準的な許容ゾーン600を1/√2で変倍して45°反時計回りに回転させることにより変換され、変形バージョン620を生成している。変換された後、位置検出パターンは、中心位置検出パターン630の主軸に近接することを許可されるのみである。
【0078】
あるいは、選択されたクイックレスポンス領域の種類が2/3−領域303である場合には、標準的な許容ゾーン600は、標準的な許容ゾーン600を1/√2で変倍して45°だけ時計回りに回転させることにより、2/3−許容ゾーンに変換される。
【0079】
「決定」ステップ730において、プロセッサ205は、中心位置検出パターン(例えば、630)から候補位置検出パターンへのベクトルを決定する。決定されたベクトルは、候補位置検出パターンが中心ノード(例えば、中心位置検出パターン630)の変換された許容ゾーン(例えば、変形バージョン620)内にあるかを判定するために使用される。候補位置検出パターンが中心ノード(例えば、中心位置検出パターン630)の変換された許容ゾーン(例えば、変形バージョン620)内にあるとプロセッサ205が判定した場合、方法700は「決定」ステップ740に継続する。そうでなければ、方法700は「決定」ステップ750に進む。
【0080】
「決定」ステップ740において、中心位置検出領域及び候補位置検出領域(即ち、候補対)が有効な2/3領域の一対を規定している(即ち、候補対はクイックレスポンスバーコードに対応している)とプロセッサ205が判定した場合、方法700はステップ760に進む。さもなければ、方法700はステップ770に進む。
【0081】
位置検出パターンの候補対の有効性は、中心位置検出パターン及び候補位置検出パターンの角度及びサイズを調査することに基づいて判定される。図8は、例示的な中心位置検出パターン810及び候補位置検出パターン820を示す。図示されるように、位置検出パターン810及び820の角度は、それぞれ、θ1及びθ2である。位置検出パターン810及び820の幅は、それぞれ、W1及びW2である。2つの位置検出パターン810及び820の角度θ1及びθ2、並びに幅W1及びW2が、所定の許容範囲内で同一である場合には、2/3領域の一致が確立されており、位置検出パターン810及び820は、有効な一対を規定している(即ち、位置検出パターン810及び820は、潜在的なクイックレスポンスバーコードに対応している)。角度について適切な所定の許容範囲は10度である。大きさについて適切な所定の許容範囲は20%である。
【0082】
位置検出パターン810及び820の一対が有効な2/3領域(例えば、領域301、302、303)を規定している場合、候補対及び領域の種類を含む潜在的な領域は、「追加」ステップ760において、先にステップ450で作成された2/3領域のリストに追加される。上述したように、2/3領域のリストは、メモリ206又はハードディスクドライブ210内に格納されるようにしてもよい。
【0083】
「追加」ステップ770において、中心位置検出パターンではなく、候補リストになく、且つ以前に中心位置検出パターンに対する候補位置検出パターンではなかった候補位置検出パターンの全ての隣接位置検出パターンが、メモリ206内に格納された候補リストに追加される。候補位置検出パターンの隣接位置検出パターンが中心位置検出パターンと有効な2/3領域の一対を更に形成してもよいので、ステップ770が実行される。ステップ770において候補リストに追加される各位置検出パターンの親位置検出パターンとして、現在の候補位置検出パターンがメモリ206内に格納されている。
【0084】
図5の先の例に戻ると、位置検出パターン510が中心位置検出パターンであり、且つ位置検出パターン530が候補位置検出パターンである場合、ステップ770において、位置検出パターン560及び570が候補リストに追加され、位置検出パターン510は中心位置検出パターンであり、位置検出パターン540及び550は既に候補リストに追加されている。
【0085】
ステップ770の後、方法700は「決定」ステップ780に進む。
【0086】
ステップ730において候補位置検出パターンが中心ノード630の変換された許容ゾーン620内にないとプロセッサ205が判定した場合には、方法700はステップ750に進む。ステップ750において、プロセッサ205は、候補位置検出パターンの隣接位置検出パターンがメモリ206内に構成された候補リストに追加されるべきであるかを判定する。特に、プロセッサ205は、現在の候補位置検出パターンの親位置検出パターンと候補位置検出パターンとの間のエッジ(境界)を、変換された許容ゾーン620により規定される許容領域の境界と比較するステップを実行する。変換された許容ゾーン620により規定される許容領域境界にエッジが交差する場合には、方法700は上述したステップ770に進み、現在の候補位置検出パターンの隣接位置検出パターンが、メモリ206内に構成された候補リストに追加される。
【0087】
また、変換された許容ゾーン620により規定される許容領域境界にエッジが交差しない場合には、処理はステップ780に進み、隣接位置検出パターンは候補リストに追加されない。
【0088】
エッジが許容領域境界に交わる場合にのみ無効の位置検出パターンの隣接位置検出パターンを追加することは、変換された許容ゾーン620により規定される許容領域の外側で探索が2つのステップのみ進む以外は、許容領域の内側の全ての位置検出パターンが発見されることを保証する。
【0089】
もう1度図5の例を考慮すると、位置検出パターン510が中心位置検出パターンである場合、位置検出パターン570は候補位置検出パターンであり且つ位置検出パターン530はその候補位置検出パターンの親であり、位置検出パターン530から位置検出パターン570へのパスが調べられる。親位置検出パターン530が位置検出パターン510の許容ゾーンにあり且つ候補位置検出パターン570が位置検出パターン510の許容ゾーンの外側にある場合、方法700はステップ780に進む。そうでなければ、方法700はステップ770に進む。
【0090】
繰り返しの最後の「決定」ステップ780において、テストすべき更なる2/3領域の種類(例えば、領域301、302、303)があるとプロセッサ205が判定した場合には、方法700はステップ710に戻る。そうでなければ、方法700を終了する。
【0091】
もう1度図4に戻ると、ステップ460に続いて、方法400はステップ470に進む。ステップ470において、プロセッサ205は、ステップ450で選択された候補位置検出パターンの場所に基づいて、標準的な許容ゾーン(例えば、許容ゾーン600)を変更するステップを実行する。例えば、標準的な許容ゾーン(例えば、許容ゾーン600)を候補位置検出パターンの場所に基づいて縮小する。
【0092】
クイックレスポンスコード規格は、位置検出パターンがクイックレスポンスバーコードの内側にあり得ないことを規定している。それゆえに、標準的な許容ゾーン(例えば、許容ゾーン600)は、現在の候補位置検出パターンが標準的な許容ゾーン(例えば、許容ゾーン600)内部にある(すなわち、候補位置検出パターンは内部位置検出パターンとして分類されてもよい)2/3クイックレスポンス領域を生じるあらゆる位置検出パターンを考慮から除外するように、ステップ470で変更されてもよい。
【0093】
候補位置検出パターンが中心位置検出パターンとどのような2/3領域(例えば、領域301、302、303)を形成したかに関係なく、標準的な許容ゾーン(例えば、許容ゾーン600)は変更される。しかしながら、位置検出パターンと関連付けられた信頼値を返す幾つかの位置検出パターンの検出方法がある。従って、いくつかの実現例において、候補位置検出パターンに対する信頼値が所定の閾値を下回る場合には、ステップ470はスキップされるようにしてもよい。
【0094】
ステップ470において、プロセッサ205は、中心位置検出パターンから候補位置検出パターンまでの距離を決定するステップを実行する。その後、決定された距離は、1/√2で乗算されるが、中心位置検出パターンと2/3/領域を形成する候補位置検出パターンについては最終的な最長許容距離を形成している。特に、中心位置検出パターンから最終的な最長許容距離以上のところにあり且つ候補位置検出パターン910を中心とした90°の弧内にあるあらゆる候補位置検出パターンは、内部位置検出パターン910と2/3/領域を規定するであろう。ステップ470において、標準的な許容ゾーンの距離は、先の許容距離が決定された距離を上回る場合には常に、結果として、決定された距離に対して90°の弧内で減少(又は縮小)される。例えば、候補位置検出パターン910が与えられたとすると、陰影をつけたエリア920は、中心位置検出パターン630及び候補位置検出パターン910を含む候補対に対して決定された除外領域を表している。従って、ステップ470の結果、候補対に対して、画像のエリア内で除外領域が決定されることになる。元の標準的な許容ゾーン600から、決定された除外領域920を除去することにより、より小さな許容ゾーン930が得られる。従って、プロセッサ205は、許容ゾーン930内にあり且つ除外領域920に重なる画像エリアを、元の標準的な許容ゾーン600から除去するステップを実行する。
【0095】
新しく、縮小されたより小さい標準的な許容ゾーン930は、方法700のステップ720に関して上述した変換について有効である。標準的な許容ゾーン930により規定される縮小エリアは、2/3/領域が候補位置検出パターンを内部位置検出パターンとして有するのを防ぐ。標準的な許容ゾーン930により規定される同じ縮小エリアは、2/3−許容ゾーン及び2/3+許容ゾーンを生成するようにステップ720で変換された場合に、2/3−領域303及び2/3+領域302がそれぞれ、候補位置検出パターンを内部位置検出パターンとして有することも防ぐ。
【0096】
図10A、図10B及び図10Cを参照して、ステップ470におけるような標準的な許容ゾーン600の縮小(又は変形)を更に説明する。
【0097】
図10Aに示されるように、領域1010は、図10Aに示された位置検出パターン1011及び1012の一対に対する標準的な除外領域である。例に従って、図10Bに示されるように、領域1020は、2/3+領域について変換された後の(ステップ720におけるように)標準的な除外領域1010を表す。
【0098】
図10Bに示されるように、除外領域1020において位置検出パターンと形成するあらゆる2/3+領域は、その2/3+領域の内側に候補位置検出パターン1012を有する。一対が2/3+領域を規定する場合で、別の位置検出パターンが除外領域1020内にある場合には、プロセッサ205は、中心位置検出パターン1011及びその別の候補位置検出パターンを含む位置検出パターンの候補対を廃棄するステップを実行する。
【0099】
同様に、図10Cに示されるように、領域1030は、2/3−領域について変換された後の標準的な除外領域1010を表す。この場合も、ゾーン1030において位置検出パターンと形成するあらゆる2/3−領域は、除外領域1030の内側に候補位置検出パターン1012を有するので、上述したように、そのような2/3−領域を規定するあらゆるペアリング(一対化)は無効とされる。
【0100】
「決定」ステップ480において、プロセッサ205は、メモリ206に格納された候補リストから現在の候補位置検出パターンを廃棄(又は削除)するステップを実行する。更にステップ480において、メモリ206に格納された候補リストに更なる候補位置検出パターンがあるとプロセッサ205が判定した場合には、方法400はステップ450に戻る。そうでなければ、方法400はステップ490に進む。
【0101】
次に、「決定」ステップ490において、中心位置検出パターン(又は中心ノード)として処理されていない何らかの位置検出パターンが候補リストにあるとプロセッサ205が判定した場合には、方法400はステップ420に進む。そうでなければ、方法400は最後のステップ495に進む。
【0102】
「出力」ステップ495において、ステップ740で識別された全ての有効な2/3領域を含む2/3領域のリストが出力される。例えば2/3領域のリストは、メモリ206又はハードディスクドライブ210に格納されるようにしてもよく、あるいはソフトウェアアプリケーション233の別のコードモジュールに渡されてもよい。
【0103】
一実現例において、プロセッサ205は、位置検出パターンの候補対をトリプレットに合成するステップを実行してもよい。また、2/3領域は、特定のクイックレスポンスバーコードの3つの位置検出パターンが全て存在する場合には、完全な3/3領域にマージされるようにしてもよい。候補対が解析されて許容領域が縮小(又は変形)する順序のために、3つの位置検出パターンが全て存在するのであれば、クイックレスポンスバーコード領域は、少なくとも1回2/3+領域として及び少なくとも1回2/3−領域として識別される。従って、例えばプロセッサ205は、図3Bに示されたように各2/3+領域の一対を調査し且つ位置検出パターン330が他の位置検出パターンと何らかの2/3−領域を形成するかを判定するステップを実行してもよい。位置検出パターン330が他の位置検出パターンと何らかの2/3−領域を形成するとプロセッサ205が判定した場合に、位置検出パターンのトリプレットは、位置検出パターンのトリプレットにより形成された「L」形状を確認し、且つ上述したような位置検出パターンの角度及び大きさを確認することにより、クイックレスポンス規格に準拠しているかをテストされるようにしてもよい。位置検出パターンのトリプレットが準拠する場合、位置検出パターンのトリプレットは、メモリ206内に構成された出力3/3領域リストに追加されてもよく、関連付けられた2/3領域は出力2/3領域リストから削除されてもよい。
【0104】
一実現例において、冗長化している2/3領域は、除外され且つ廃棄されてもよい。例えば、第1の位置検出パターンが中心位置検出パターンである場合に発見された2/3領域が、第2の位置検出パターンが中心位置検出パターンである場合に再度発見される場合があるので、幾つかの2/3領域は倍となる。更に、2/3−領域は二重の2/3+領域を有し、2/3/領域は二重の2/3/領域を有する。従って、冗長化している2/3領域は、除外され且つ廃棄されるようにしてもよい。
【0105】
説明した方法に従って決定された3/3領域及び残りの2/3領域は、ISO/IEC18004において説明したようにその後クイックレスポンス復号器に入力され、領域内で符号化されたあらゆるデータを取得するようにしてもよい。
【産業上の利用可能性】
【0106】
説明された構成は、コンピュータ及びデータ処理業界、並びに特に処理バーコードに適用可能である。
【0107】
上記の記述は本発明のいくつかの実施形態のみを説明し、本発明の範囲及び趣旨から逸脱せずに、変形及び/又は変更がいくつかの実施形態に対して行なわれてもよい。実施形態は、限定するものではなく例示するものである。
【0108】
本明細書に関して、「備える」という言葉は、「主に含むが、単独で必要ではない」、あるいは「有する」又は「含む」ことを意味し、「のみから構成される」ことではない。「備える」の語形変化は、それに対応して意味の変化を示す。
【特許請求の範囲】
【請求項1】
2次元バーコードの位置検出パターンの候補対を識別する方法であって、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する工程と、
(ii)前記検出された複数の位置検出パターンの残りから別の位置検出パターンを選択し、前記第1の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する工程と、
(iii)前記候補対について、前記画像のエリア内で除外領域を決定する工程と、
(iv)前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する工程と、
(v)前記除外領域に重なっている前記許容ゾーン内のエリアを、前記許容ゾーンから除去する工程と、を有し、
(vi)前記2次元バーコードの位置検出パターンの前記候補対を識別するために、1つ以上のさらに別の位置検出パターンについて(ii)〜(v)の工程を繰り返す、
ことを特徴とする方法。
【請求項2】
前記2次元バーコードはクイックレスポンスバーコードである、ことを特徴とする請求項1に記載の方法。
【請求項3】
位置検出パターンの前記候補対をトリプレットに合成する工程を、さらに有することを特徴とする請求項1又は2に記載の方法。
【請求項4】
バーコードの種類に従って前記許容ゾーンを変換する工程を、さらに有することを特徴とする請求項1乃至3のいずれか1項に記載の方法。
【請求項5】
前記除外領域は、潜在的なクイックレスポンス領域の外部にある位置検出パターンに基づいて判定されることを特徴とする請求項1乃至4のいずれか1項に記載の方法。
【請求項6】
2次元バーコードの位置検出パターンの候補対を識別する装置であって、
画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する手段と、
前記複数の検出された位置検出パターンの残りから別の位置検出パターンを選択し、前記第1の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する手段と、
前記候補対について、前記画像のエリア内で除外領域を決定する手段と、
前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する手段と、
前記2次元バーコードの位置検出パターンの前記候補対を識別するために、前記除外領域に重なっている前記許容ゾーン内のエリアを、前記許容ゾーンから除去する手段と、
を備えることを特徴とする装置。
【請求項7】
データ及びコンピュータプログラムを格納するメモリと、前記コンピュータプログラムを実行する、前記メモリに結合されたプロセッサとを備えるコンピュータにおいて2次元バーコードの位置検出パターンの候補対を識別するためのコンピュータプログラムであって、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する工程と、
(ii)前記複数の検出された位置検出パターンの残りから別の位置検出パターンを選択し、前記第1の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する工程と、
(iii)前記候補対について、前記画像のエリア内で除外領域を決定する工程と、
(iv)前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する工程と、
(v)前記除外領域に重なる前記許容ゾーン内のエリアを、前記許容ゾーンから除去する工程と、としてコンピュータを動作させ、
(vi)前記2次元バーコードの位置検出パターンの前記候補対を識別するために、1つ以上のさらに別の位置検出パターンに対して(ii)〜(v)の工程を繰り返す、
ことを特徴とするコンピュータプログラム。
【請求項1】
2次元バーコードの位置検出パターンの候補対を識別する方法であって、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する工程と、
(ii)前記検出された複数の位置検出パターンの残りから別の位置検出パターンを選択し、前記第1の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する工程と、
(iii)前記候補対について、前記画像のエリア内で除外領域を決定する工程と、
(iv)前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する工程と、
(v)前記除外領域に重なっている前記許容ゾーン内のエリアを、前記許容ゾーンから除去する工程と、を有し、
(vi)前記2次元バーコードの位置検出パターンの前記候補対を識別するために、1つ以上のさらに別の位置検出パターンについて(ii)〜(v)の工程を繰り返す、
ことを特徴とする方法。
【請求項2】
前記2次元バーコードはクイックレスポンスバーコードである、ことを特徴とする請求項1に記載の方法。
【請求項3】
位置検出パターンの前記候補対をトリプレットに合成する工程を、さらに有することを特徴とする請求項1又は2に記載の方法。
【請求項4】
バーコードの種類に従って前記許容ゾーンを変換する工程を、さらに有することを特徴とする請求項1乃至3のいずれか1項に記載の方法。
【請求項5】
前記除外領域は、潜在的なクイックレスポンス領域の外部にある位置検出パターンに基づいて判定されることを特徴とする請求項1乃至4のいずれか1項に記載の方法。
【請求項6】
2次元バーコードの位置検出パターンの候補対を識別する装置であって、
画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する手段と、
前記複数の検出された位置検出パターンの残りから別の位置検出パターンを選択し、前記第1の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する手段と、
前記候補対について、前記画像のエリア内で除外領域を決定する手段と、
前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する手段と、
前記2次元バーコードの位置検出パターンの前記候補対を識別するために、前記除外領域に重なっている前記許容ゾーン内のエリアを、前記許容ゾーンから除去する手段と、
を備えることを特徴とする装置。
【請求項7】
データ及びコンピュータプログラムを格納するメモリと、前記コンピュータプログラムを実行する、前記メモリに結合されたプロセッサとを備えるコンピュータにおいて2次元バーコードの位置検出パターンの候補対を識別するためのコンピュータプログラムであって、
(i)画像のエリアにおいて検出された複数の位置検出パターンから第1の位置検出パターンを選択する工程と、
(ii)前記複数の検出された位置検出パターンの残りから別の位置検出パターンを選択し、前記第1の位置検出パターン及び前記別の位置検出パターンを含む候補対を形成する工程と、
(iii)前記候補対について、前記画像のエリア内で除外領域を決定する工程と、
(iv)前記別の位置検出パターンが前記画像のエリアの許容ゾーンの外側にある場合に、位置検出パターンの前記候補対を廃棄する工程と、
(v)前記除外領域に重なる前記許容ゾーン内のエリアを、前記許容ゾーンから除去する工程と、としてコンピュータを動作させ、
(vi)前記2次元バーコードの位置検出パターンの前記候補対を識別するために、1つ以上のさらに別の位置検出パターンに対して(ii)〜(v)の工程を繰り返す、
ことを特徴とするコンピュータプログラム。
【図1】
【図2A】
【図2B】
【図3A】
【図3B】
【図3C】
【図4】
【図5】
【図6A】
【図6B】
【図7】
【図8】
【図9】
【図10A】
【図10B】
【図10C】
【図2A】
【図2B】
【図3A】
【図3B】
【図3C】
【図4】
【図5】
【図6A】
【図6B】
【図7】
【図8】
【図9】
【図10A】
【図10B】
【図10C】
【公開番号】特開2012−138079(P2012−138079A)
【公開日】平成24年7月19日(2012.7.19)
【国際特許分類】
【出願番号】特願2011−258177(P2011−258177)
【出願日】平成23年11月25日(2011.11.25)
【出願人】(000001007)キヤノン株式会社 (59,756)
【Fターム(参考)】
【公開日】平成24年7月19日(2012.7.19)
【国際特許分類】
【出願日】平成23年11月25日(2011.11.25)
【出願人】(000001007)キヤノン株式会社 (59,756)
【Fターム(参考)】
[ Back to top ]