(57)【要約】【課題】バーコード識別の精度を向上させること。【解決手段】画像内のＱＲコードを識別するための方法は、画像を入力することと、１つまたは複数のコンピュータープロセッサーを使用して、画像内のエッジを検出し、エッジカウント画像を作成し、エッジカウント画像内の連結領域をラベリングし、候補領域リストを作成し、候補領域リスト内の各個々の候補について、個々の候補内の領域に重なる領域を見つけ、重なり合う領域をグループ化して重なり合う領域のグループにし、各グループについて、重なり合う領域を融合して融合領域にし、各融合域を候補領域リストに追加して新たな候補領域リストを形成し、そして、新たな候補領域リスト内の各領域内のＱＲコードの復号を実行することと、を含む。【選択図】図７
2013131212.tif 000002
【特許請求の範囲】
【請求項１】
画像内のマトリックス型二次元コードを識別する方法であって、
画像を入力すること、
プロセッサーを使用して、
前記画像内のエッジを識別し、
エッジカウント画像を作成し、
前記エッジカウント画像内の連結領域をラベリングし、
候補領域リストを作成し、
前記候補領域リスト内の各個々の候補について、
前記個々の候補内の前記領域に重なる領域を見つけ、
重なる領域をグループ化して重なり合う領域のグループにし、
各グループについて、
前記重なり合う領域を融合して融合領域にし、
各融合領域を前記候補領域リストに追加して新たな候補領域リストを形成し、そして
前記新たな候補領域リスト内の各領域内のマトリックス型二次元コードの復号を実行することを含む、方法。
【請求項２】
2013131212.tif 000013
【請求項３】
2013131212.tif 000014
【請求項４】
一方のバーコードがもう一方のバーコードに対して回転している、同じ画像内の少なくとも２つのバーコードを識別するための方法であって、
画像を入力すること、
プロセッサーを使用して、
前記画像内の水平または垂直バーコードを復号し、
次に、前記画像内の回転したバーコードを復号することを含み、前記回転したバーコードは前記水平または垂直バーコードに対して回転している、方法。
【請求項５】
水平または垂直バーコードを復号することは、ＰＤＦ４１７バーコードを復号することを含む、請求項４に記載の同じ画像内の少なくとも２つのバーコードを識別するための方法。
【請求項６】
前記画像内の前記回転したバーコードを復号した後に、次いで２Ｄバーコードを復号すること、
をさらに含む、請求項４に記載の同じ画像内の少なくとも２つのバーコードを識別するための方法。
【請求項７】
前記２Ｄバーコードはマトリックス型二次元コードであり、
前記プロセッサーを使用して、
前記画像内のエッジを識別し、
エッジカウント画像を作成し、
前記エッジカウント画像内の連結領域をラベリングし、
候補領域リストを作成し、
前記候補領域リスト内の各個々の候補について、
前記個々の候補内の前記領域に重なる領域を見つけ、
重なる領域をグループ化して重なり合う領域のグループにし、
各グループについて、
前記重なり合う領域を融合して融合領域にし、
各融合領域を前記候補領域リストに追加して新たな候補領域リストを形成し、そして
前記新たな候補領域リスト内の各領域内のマトリックス型二次元コードの復号を実行することをさらに含む、請求項６に記載の同じ画像内の少なくとも２つのバーコードを識別するための方法。
【請求項８】
画像内のマトリックス型二次元コードを識別するためのデバイスであって、
画像を入力するための装置、
プロセッサーであって、
前記画像内のエッジを識別し、
エッジカウント画像を作成し、
前記エッジカウント画像内の連結領域をラベリングし、
候補領域リストを作成し、
前記候補領域リスト内の各個々の候補について、
前記個々の候補内の前記領域に重なる領域を見つけ、
重なる領域をグループ化して重なり合う領域のグループにし、
各グループについて、
前記重なり合う領域を融合して融合領域にし、
各融合領域を前記候補領域リストに追加して新たな候補領域リストを形成し、そして
前記新たな候補領域リスト内の各領域内のマトリックス型二次元コードの復号を実行する、プロセッサーを備える、デバイス。
【請求項９】
2013131212.tif 000015
【請求項１０】
2013131212.tif 000016
【請求項１１】
画像を入力するための装置はスキャナーである、請求項８に記載の画像内のマトリックス型二次元コードを識別するためのデバイス。
【請求項１２】
前記画像を記憶するためのメモリーをさらに備える、請求項８に記載の画像内のマトリックス型二次元コードを識別するためのデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マトリックス型二次元コードを含むバーコードを位置特定するための方法および装置に関する。
【背景技術】
【０００２】
バーコードは４０年以上にわたって対象物の識別および価格決定に利用されてきた。バーコードはデータの光学的な機械可読表現である。このデータは、バーコードが付着されている対象物に関する情報（例えば、価格および名称に関連付けられるｉｄ）を表す。本来、バーコードは平行線の幅、およびそれらの間の間隔を変えることによってデータを表しており、線形または１次元（１Ｄ）のものであるとみなすこともできる。最近では、それらは２次元（２Ｄ）における長方形、ドット、六角形、および他の幾何パターンに発展している。２Ｄシステムはさまざまなシンボルを使用するが、それらも同様に一般的にバーコードと称される。バーコードは本来、バーコードスキャナーと称される専用の光学スキャナーによってスキャンされていたが、後に、スキャナーおよび解釈ソフトウェアはデスクトッププリンター、スマートフォンおよびスキャナーを含むデバイス上で利用可能になった。
【０００３】
いくつかの事例において、１つの画像が複数のバーコードを含む場合があり、それらのいくつかは水平または垂直であり、それらのいくつかは回転している。従来のバーコード識別方法は、水平または垂直バーコードを復号（識別）するのみであり、回転したものを復号することはできない。図１は１つのこのような例を示す。この画像上には２つのバーコードがあり、バーコード１は画像の右上にあり、バーコード２は画像の中央下部にある。バーコード１は回転したバーコードであり（回転角は約１０°である）、一方でバーコード２はほぼ水平である。従来のバーコード識別方法はバーコード２を正確に復号するが、一方でバーコード１の復号に失敗する。
【０００４】
従って、そのバーコードのうちの一方が他方に対して回転している、同じ画像内にある２つのバーコードを復号するための改善された方法が必要とされている。
【０００５】
ＱＲコード（登録商標）（クイックレスポンスコードの略称である）は、最初は自動車産業向けに設計されたタイプのマトリックスバーコード（または二次元コード）である。最近では、その高速の可読性および比較的大きな記憶容量に起因して、このシステムは当該産業以外で一般的になってきている。コードは白色背景上の正方形パターン内に配列される黒色の構成成分から成る。符号化される情報は、任意の種類のデータ（例えば、２値、英数字、または漢字の記号）から構成されることができる。ＥＰＳＯＮ社によって製造されるもののようないくつかの商用のスキャナーは、ＱＲコードを復号する機能を有する。
【０００６】
同一の所有者によって所有される、２００９年６月１６日に発行された米国特許第７，５４６，９５０号は、ＱＲコードを位置特定および復号するための方法を開示している。この方法は、最初に、いくつかのＱＲ候補領域を位置特定し、次いで各候補領域内のＱＲコードの復号を試みる。ＱＲ候補領域は、入力画像の縮小されたエッジマップから作成されるエッジカウント画像から連結領域を検出することによって位置特定される。この方法は、ＱＲ構成成分サイズがそれほど大きくない場合には良好に機能するが、ＱＲコードの構成成分のサイズが大きくなると限界がある。米国特許第７，５４６，９５０号は参照によりその全体が本明細書に組み込まれる。
【０００７】
従って、大きなマトリックス型二次元コード（ＱＲコード）を位置特定するための改善された方法が必要とされている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第７，５４６，９５０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、バーコード識別の精度を向上させることである。
【課題を解決するための手段】
【００１０】
具体的には、目的は、追加のバーコードも含む画像内の回転または傾斜したバーコードを識別することであり、この追加のバーコードは垂直の場合もあれば、水平の場合もある。
【００１１】
好ましい実施形態では、一方のバーコードがもう一方のバーコードに対して回転している、同じ画像内の少なくとも２つのバーコードを識別するための方法は、画像を入力することと、１つまたは複数のコンピュータープロセッサーを使用して、画像内の水平または垂直バーコードを復号し、次に、画像内の回転したバーコードを復号することとを含み、回転したバーコードは水平または垂直バーコードに対して回転している。
【００１２】
従って、本発明では、その少なくとも１つのバーコードが画像内の少なくとも１つの他のバーコードに関して異なる向きを有する（回転または傾斜している）、同じ画像内の２つ以上のバーコードを識別および／または復号するための精度を向上させるために、回転したバーコードを復号するためのモジュールが、水平または垂直バーコードを復号するためのモジュールに常に追従する。
【００１３】
別の目的は、マトリックス型二次元バーコード、特に大きなマトリックス型二次元バーコードの識別の精度を向上させることである。
【００１４】
好ましい実施形態では、画像内のマトリックス型二次元コードを識別するための方法は、画像を入力することと、１つまたは複数のコンピュータープロセッサーを使用して、画像内のエッジを識別し、エッジカウント画像を作成し、エッジカウント画像内の連結領域をラベリングし、候補領域リストを作成し、候補領域リスト内の各個々の候補について、個々の候補内の領域に重なる領域を見つけ、重なり合う領域をグループ化して重なり合う領域のグループにし、各グループについて、重なり合う領域を融合して融合領域にし、各融合領域を候補領域リストに追加して新たな候補領域リストを形成し、そして、新たな候補領域リスト内の各領域内のマトリックス型二次元コードの復号を実行することと、を含む。
【００１５】
別の実施形態では、個々の候補内の領域に重なる領域を見つけることは、
２つの領域、すなわち領域１と領域２との間の水平重なりを以下のようにして見つけることを含み、
2013131212.tif 000003
【００１６】
さらなる実施形態では、個々の候補内の領域に重なる領域を見つけることは、
２つの領域、領域１と領域２との間の垂直重なりを以下のようにして見つけることを含み、
2013131212.tif 000004
【００１７】
他の目的および達成ならびに、本発明のより完全な理解については、以下の記載および特許請求の範囲を添付の図面とともに参照することによって明らかとなり、理解される。
【図面の簡単な説明】
【００１８】
【図１】図１は、そのうちの一方が他方のバーコードに対して回転または傾斜している、複数のバーコードを有する画像を示す。
【図２】図２は、本発明を利用するための対象物処理デバイスおよびシステムの一般的なブロック図である。
【図３】図３Ａは、単一の画像内の複数のバーコードを復号するための従来の方法を示し、図３Ｂは、本発明の一般的なステップを示す。
【図４】図４は、画像内の１ＤバーコードおよびＰＤＦ４１７バーコードの両方を復号するための従来の方法を示す。
【図５】図５は、画像内の１ＤバーコードおよびＰＤＦ４１７バーコードの両方を復号するための本発明の方法を示す。
【図６】図６は、本発明の１つの態様の一般的なステップを示す流れ図である。
【図７】図７は、ＱＲバーコードを復号するための現行の（本発明に先立つ）方法の一般的なステップを示す流れ図である。
【図８】図８は、その構成成分のサイズが７ピクセルから１７ピクセルに及ぶ１１個のＱＲコードを有する２００ＤＰＩの入力画像を示す。
【図９】図９は図８から生成された縮小エッジカウント画像を示す。
【図１０】図１０は、入力画像内で検出された候補領域を示す。
【図１１】図１１は復号されたＱＲコードを示す。
【図１２】図１２は、ＱＲバーコードを復号するための本発明の方法の一般的なステップを示す流れ図である。
【図１３】図１３は、重なり合う領域のタイプを示す。
【図１４】図１４Ａは、水平に配列される２つの領域間の最小重なりを示し、図１４Ｂは、垂直に配列される２つの領域間の最小重なりを示す。
【図１５】図１５Ａは、単一の候補領域が大きなＱＲコード全体を覆っていない、ＱＲバーコードを復号するための現行の（本発明に先立つ）方法の結果を示し、図１５Ｂは、単一の融合した領域候補が大きなＱＲコード全体を覆っている、ＱＲバーコードを復号するための本発明の方法の結果を示す。
【図１６】図１６は、本発明の方法によって検出される候補領域を示す。
【図１７】図１７は、本発明の方法によって位置特定および復号されるＱＲコードを示す。
【発明を実施するための形態】
【００１９】
以下の詳細な説明において、説明として、本発明の例示的な実施形態を示す添付の図面を参照する。図面において、同様の参照符号はいくつかの図面全体を通じて実質的に類似の構成要素を説明する。これらの実施形態は、当業者が本発明を実施することを可能にするのに十分詳細に説明される。他の実施形態を利用することができ、本発明の範囲から逸脱することなく、構造的、論理的および電気的な変更を為すことができる。その上、本発明のさまざまな実施形態は、異なるけれども、必ずしも相互排他的ではないことが理解されるべきである。例えば、１つの実施形態において記載されている特定の特徴、構造、または特性が他の実施形態内に含まれてもよい。それゆえ、以下の詳細な説明は限定的な意味に解釈されるべきではなく、本発明の範囲は、添付の特許請求の範囲のみによって、このような特許請求の範囲が権利付与される均等物の全範囲とともに、画定される。
【００２０】
一般的に、例示的な実施形態は、バーコードを復号または認識するための方法、デバイス、およびコンピューター可読媒体に関する。
【００２１】
例示的な対象物処理デバイス１００の概略表現が図２に示されている。対象物処理デバイス１００は、介在するインターフェイス１０２を用いてホストコンピューター１５０とデータを交換する。ホストコンピューター１５０上でアクセスするためにアプリケーションプログラムおよび対象物処理デバイスドライバーも記憶されることができる。例えば、画像検索コマンドがアプリケーションプログラムから受け取られると、対象物処理デバイスドライバーは、コマンドデータの、対象物処理デバイス１００に適したフォーマットへの変換を制御し、変換されたコマンドデータを対象物処理デバイス１００に送信する。ドライバーは、対象物処理デバイス１００からさまざまな信号およびデータをも受け取って解釈し、ホストコンピューター１５０を用いて必要な情報をユーザーに提供する。
【００２２】
ホストコンピューター１５０によってデータが送信されると、インターフェイス１０２はデータを受け取り、それをＲＡＭ１０４の一部を形成する受信バッファー内に記憶する。ＲＡＭ１０４は、例えば、アドレス指定を通じて多数のセクションに分割され、受信バッファーまたは送信バッファーのような種々のバッファーとして割り当てられることができる。デジタル画像データのようなデータも、キャプチャ機構（複数の場合もあり）１１２、フラッシュＥＥＰＲＯＭ１１０、またはＲＯＭ１０８から対象物処理デバイス１００によって取得されることができる。キャプチャ機構（複数の場合もあり）１１２は、例えばスキャナーであることができ、プリンターのようなデバイスの製造および／または組み立てにおいて使用されるべき部品上のバーコードラベルのような１つまたは複数の対象物をスキャンすることによってデジタル画像を生成する。スキャナー１１２は、例えば、ロボット１１６もしくは人間によって操作されることができ、または、例えば、コンピューター１５０によって自動的に制御されることができる。対象物（複数の場合もあり）のデジタル画像はその後、ＲＡＭ１０４の受信バッファーまたは送信バッファー内に記憶されることができる。
【００２３】
プロセッサー１０６は、例えば、ＲＯＭ１０８上に、またはフラッシュＥＥＰＲＯＭ１１０上に記憶されているコンピューター実行可能命令を使用して、例えば、方法６００（図６）および方法１２００（図１２）のような特定の機能または一群の機能を実行する。方法６００および１２００は本明細書において後により詳細に説明されることになる。例えば、ＲＡＭ１０４の受信バッファー内のデータがデジタル画像である場合、プロセッサー１０６は方法６００または１２００の方法的行為をデジタル画像に対して実施する。その後、画像処理パイプラインにおけるさらなる処理がデジタル画像に対して実行されることができ、その後、画像が、例えばＬＣＤディスプレイのようなディスプレイ１１４上に表示されるか、または、例えば、プリンター１６２上で印刷するためにホストコンピューター１５０に転送されるか、プロジェクター１６４を用いて投影されるか、またはハードディスク１６０上に記憶される。
【００２４】
本明細書において開示される例示的な方法６００および１２００ならびにそれらの変形形態は、コンピューター実行可能命令を搬送するかもしくは有するための持続性コンピューター可読媒体またはその上に記憶されるデータ構造を使用して実施されることができる。このようなコンピューター可読媒体は、汎用または専用コンピューターのプロセッサーによってアクセスされることができる任意の利用可能な媒体であることができる。限定ではなく例として、このようなコンピューター可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気記憶デバイス、または、コンピューター実行可能命令もしくはデータ構造の形態のプログラムコードを搬送または記憶するために使用されることができるとともに、汎用または専用コンピューターのプロセッサーによってアクセスされることができる任意の他の媒体を含むことができる。上記の組み合わせもコンピューター可読媒体の範囲内に含まれるべきである。
【００２５】
コンピューター実行可能命令は、例えば、汎用コンピューターまたは専用コンピューターのプロセッサーが、特定の機能または一群の機能を実行するようにする命令およびデータを含む。本明細書では方法的行為に特有の文言において本主題が説明されているが、添付の特許請求の範囲において定義される本主題は必ずしも、本明細書に記載されている特定の行為に限定されないことが理解されるべきである。そうではなく、本明細書に記載されている特定の行為は、特許請求の範囲の実装の例示的な形態として開示されている。
【００２６】
一実施形態では、以下に記載される本発明の方法ステップは好ましくは、対象物処理デバイス１００および／もしくはコンピューター１５０内の、ならびに／または、アクセス可能な外部メモリー内に記憶されるかもしくはロード可能である、コンピューター実行可能命令、プログラム、ソフトウェア、ファームウェアを実行する、対象物処理デバイス１００および／またはコンピューター１５０内の１つまたは複数のプロセッサーによって実行される。コンピューター１５０のプロセッサーは、例えば、中央処理装置（ＣＰＵ）および１つまたは複数のグラフィック処理装置（ＧＰＵ）を含むことができる。内部メモリーは、例えば、ＲＡＭおよびＲＯＭを含むことができる。Ｉ／Ｏインターフェイスは、例えば、キーボード、マウス、および、ハードディスク１６０のような外部メモリーとの通信を可能にする。
【００２７】
専用コンピューターの例は、デジタルカメラ（その一例は、日本国長野県諏訪市大和に本社を置くセイコーエプソン社によって製造されるＥＰＳＯＮ  Ｒ−Ｄ１デジタルカメラを含むが、これには限定されない）、デジタルビデオカメラ、プロジェクター、プリンター、スキャナー、コピー機、ポータブルフォトビューワ（その例は、セイコーエプソン社によって製造されるＥＰＳＯＮ  Ｐ−３０００またはＰ−５０００ポータブルフォトビューワを含むが、これらには限定されない）、もしくはポータブル動画プレーヤー、またはプリンター／スキャナー／コピー機の組み合わせ（その例はセイコーエプソン社によって製造される、ＥＰＳＯＮ  Ｓｔｙｌｕｓ  Ｐｈｏｔｏ  ＲＸ５８０、ＲＸ５９５、もしくはＲＸ６８０、ＥＰＳＯＮ  Ｓｔｙｌｕｓ  ＣＸ４４００、ＣＸ７４００、ＣＸ８４００、もしくはＣＸ９４００Ｆａｘ、およびＥＰＳＯＮ  ＡｃｕＬａｓｅｒ（登録商標）ＣＸ１１ＮＦを含むがこれらには限定されない）、もしくはプリンター／スキャナーの組み合わせ（その例はすべてセイコーエプソン社によって製造される、ＥＰＳＯＮ  ＴＭ−Ｊ９０００、ＴＭ−Ｊ９１００、ＴＭ−Ｊ７０００、ＴＭ−Ｊ７１００、およびＴＭ−Ｈ６０００ＩＩＩを含むがこれらには限定されない）、もしくはデジタルカメラ／ビデオカメラの組み合わせのような、それらの何らかの組み合わせを含む。
【００２８】
本発明には、以下の２つのセクション、Ａ．一方のバーコードが他方に対して回転または傾斜している、同じ画像内の２つ以上のバーコードの識別、およびＢ．画像内の大きなＱＲバーコードの識別、において説明される２つの態様が存在する。
【００２９】
（Ａ．一方のバーコードが他方に対して回転または傾斜している、同じ画像内の２つ以上のバーコードの識別）
本発明のこの態様を理解するためには、バーコードを復号するための従来の方法を理解することが有用である。
【００３０】
従来のパイプラインでは、１Ｄ復号器および２Ｄ復号器は２つの別個のモジュールである。図１に示されるバーコード１のような回転したバーコードが復号されない理由は、図３Ａに示される従来のパイプラインの設計から説明されることができる。
【００３１】
図３Ａに示される従来のパイプラインでは、バーコードが「直立バーコード」モジュールによって復号される場合、「回転バーコード」モジュールはまったく作動しないことが分かる。ステップ３１０において、１Ｄ直立バーコードモジュールを用いて画像が処理されて、水平または垂直バーコードが復号される。バーコードが検出されると、ステップ３１２が「はい」を返し、次にプロセスはステップ３１６に移動し、画像が処理されて２Ｄバーコードが復号される。回転していないバーコードが検出されないと、ステップ３１２が「いいえ」を返し、次にプロセスはステップ３１４に移動し、１Ｄ回転バーコードモジュールを用いて画像が処理されて回転したバーコードが復号される。
【００３２】
通常、スキャンされた対象物のデジタル画像は単一の１Ｄバーコードのみを有する。そのため、ステップ３１２においてそれが識別される場合、プロセスは２Ｄバーコードを探すために先へ進む。換言すれば、「回転バーコード」モジュールは、「直立バーコード」モジュールから復号されるバーコードがない場合にのみ作動することになる。
【００３３】
本発明のこの態様は、特定の１Ｄまたは２Ｄバーコード復号器に限定されず、関連もしない。「１Ｄ直立バーコード」モジュールとは、一般的に、従来の水平または垂直バーコード復号器を指す。「１Ｄ回転バーコード」モジュールとは、一般的に、従来の傾斜バーコード読み取り／復号機能を指し、これは一般的に、回転／傾斜したバーコードの傾斜角を検出し、画像の傾斜をなくし、次いで従来の様式で水平または垂直バーコードを復号しようと試みる。
【００３４】
本発明は特定の１Ｄまたは２Ｄバーコード復号器に限定されず関連もしないが、同一の所有者によって所有される米国特許第８，１６２，２２３号および同一の所有者によって所有される米国特許出願公開第２０１１／０２１５１５１号は１Ｄバーコード復号方法を開示しており、同一の所有者によって所有される米国特許第７，５４６，９５０号は、傾斜したバーコードの検出を含む２Ｄバーコード方法を開示している。同一の所有者によって所有される米国特許第８，１６２，２２３号、米国特許出願公開第２０１１／０２１５１５１号、および米国特許第７，５４６，９５０号はこれによって参照によりその全体が組み込まれる。
【００３５】
回転していないバーコードおよび回転したバーコードの両方が１つの画像内に存在するときにその両方を復号するために、本発明は、従来のパイプラインを修正する。新規のパイプラインが図３Ｂに示されている。図示されるように、本発明では省かれているステップ３１２の結果にかかわらずステップ３１４が実行される。新規のパイプラインは「回転バーコード」モジュールが「直立バーコード」モジュールの後に作動することを保証する。
【００３６】
この改善によって、バーコードを有する画像のサンプルセットにおいて復号精度が、１１，６６６個のバーコードサンプルを有するデータセットにおいて６６．５１％から８０．０％へと、大幅に改善されている。
【００３７】
本発明の新規のパイプラインによって、異なる向きを有する複数のバーコードが復号されることができる。
【００３８】
１Ｄバーコードを復号するように設計された、いくつかの機能またはモジュールが２Ｄバーコードを復号するために再使用されることができることも確認された。例えば、従来のパイプラインではＰＤＦ４１７および１Ｄ「直立バーコード」モジュールは個別に同様の「トークン化」機能を実行し、１Ｄ「直立バーコード」モジュールおよびＰＤＦ４１７モジュールの両方が画像をスキャンし、これは、「トークン化」が重複しており、画像スキャンも同様に重複していることを意味する。重複した「トークン化」をおよび重複した画像スキャンステップを低減すれば、速度が向上される。ＰＤＦ４１７は、さまざまな用途、主として運送、識別カード、および在庫管理において使用される、直線バーコードを積み重ねたシンボルフォーマットである。ＰＤＦはポータブルデータファイルを表す。４１７は、コード内の各パターンが４つのバーおよび間隔から成ること、および、各パターンの長さが１７単位であることを意味する。
【００３９】
本発明では、「ＰＤＦ４１７」および「直立バーコード」復号モジュールが組み合わされて１つのモジュールになっており、トークン化結果が両方のモジュールによって再使用される。図４および図５は、速度が向上することができる理由を詳細に示す。図４に示されている従来のパイプラインでは、１Ｄ復号モジュール４１およびＰＤＦ４１７復号モジュール４２は分離している、すなわち、１Ｄトークン化機能「tokenizeRowPeakLeftToRight」が実行されて（ステップ４１０）１Ｄバーコードが復号され（ステップ４１２）、ＰＤＦ４１７トークン化機能「esdlTokenizev2」が実行されて（ステップ４２０）ＰＤＦ４１７バーコードが復号される（ステップ４２２）。その上、同じ画像が二回スキャンされることになる。ここで、本発明の新規のパイプライン（図５）では、２つのモジュールは１Ｄ・ＰＤＦ４１７複合モジュール５０として組み合わされている。１Ｄトークン化機能「tokenizeRowPeakLeftToRight」が最初に実行される（ステップ５１０）。次いで、その結果が１Ｄ復号（ステップ５１２）機能およびＰＤＦ４１７復号（ステップ５１４）機能の両方によって使用され、これは、「esdlTokenizev2」によって使用される時間が節約されることを意味する。その上、画像は一回だけスキャンされ、これも同様に時間を節約する。
【００４０】
この改善によって、速度が約１３％改善され、或るテスト条件において１９９ｍｓから１７４ｍｓへと低減された。その上、１Ｄトークン化機能の再使用に起因して、１Ｄトークン化機能はＰＤＦ４１７復号モジュールにおいて使用されるトークン化機能よりも良好な結果を与えるため、ＰＤＦ４１７復号精度が改善されている（ＰＤＦ４１７精度が９８．６８％から９９．０５％に改善されている）。
【００４１】
図６は、本発明の方法６００の一般的なステップを示す。
上記で説明されたように、ＰＤＦ４１７および１Ｄコードは、速度および精度を向上させるために同じモジュール５０内で復号される。
【００４２】
図６に示されるように、方法６００は、画像を複合モジュール５０に入力すること（ステップ６１２）によって開始し（ステップ６１０）、水平または垂直１ＤバーコードおよびＰＤＦ４１７バーコードが復号される（ステップ６１４）。画像はスキャナー１１２を使用して入力され得るか、または画像は、例えば、ＲＡＭ１０４もしくはハードディスク１６０内に既に記憶されていてもよい。その後、プロセスはステップ６１６に移動して、複合モジュール５０において検出（識別および、または復号）されることができる水平、または垂直バーコードに対して回転または傾斜している１Ｄ回転バーコードを復号する。その後、プロセスは同じ画像を、２Ｄバーコードを復号するためにモジュールに入力する（ステップ６１２）が、ＰＤＦ４１７バーコードは除外される（ステップ６１８）。その後、復号の結果が報告され（ステップ６２０）、プロセスは終了する（ステップ６２２）。
【００４３】
従って、本発明では、少なくとも１つのバーコードが画像内の少なくとも１つの他のバーコードに関して異なる向きを有する（回転または傾斜している）、同じ画像内の２つ以上のバーコードを識別および／または復号するための精度を向上させるために、１Ｄ回転バーコードモジュールが、複合１Ｄ直立バーコード・ＰＤＦ４１７コード復号器モジュール５０に常に追従する。
【００４４】
以下の表１において、従来の枠組みおよび本発明からの１０，０００を超えるバーコードについての評価結果がリストされている。
【００４５】
【表１】
2013131212.tif 000005
【００４６】
（Ｂ．画像内の大きなＱＲバーコードの識別）
本発明のこの態様を理解するためには、ＱＲバーコードを復号するための現行の（本発明に先立つ）方法を理解することが有用である。
【００４７】
現行のＱＲ候補領域位置特定方法の流れ図が図７に示される。
ステップ７１０において、デジタル画像が入力される。画像はスキャナー１１２を使用して入力され得るか、または画像は、例えば、ＲＡＭ１０４もしくはハードディスク１６０内に既に記憶されていてもよい。入力デジタル画像内で、あり得るＱＲ候補領域を位置特定するために、デジタル画像内のエッジが最初に識別される（ステップ７１２）。その後、上記で定義されるようにエッジを位置特定するためにデジタル画像をスキャンすること、および、エッジを新たな画像内のピクセル値として表すことによってエッジカウント画像が作成される（ステップ７１４）。
例えば、エッジカウント画像を作成するために、値七（７）のピクセルはデジタル画像内の対応する８×８領域内の七（７）つのエッジを表す。エッジカウント画像は入力デジタル画像の８分の１のサイズであり、これによって後続の処理が非常に高速に促進される。エッジカウント画像は通常複数の正方形を含む。エッジカウント画像内の隣接する「エッジの鋭い」正方形（すなわち、より高いピクセル値を有する）は共通の領域に関連付けられるものとしてラベリングされる。
【００４８】
並外れて大きな画像において、エッジは正確なシンボル含有領域を識別するのに十分に集まっていない場合がある。このような事例では、八（８）よりも高い縮小率が考慮される場合がある。
【００４９】
ラベリング（ステップ７１６）の間、画像は一度スキャンされ、連結領域が、例えば、２つの領域がそれらの根として共通の第３の領域を有することによって関連付けられることができるツリー構造を使用する関連表内にリストされる。
【００５０】
この時点で、所定値EDGE_AREA_THRESHOLDのサイズを下回るすべての領域は、小さすぎてＱＲシンボルになり得ないと想定され、誤検出として除外される（ステップ７１８）。残りの領域が候補領域リストを形成する（ステップ７２０）。
【００５１】
その後、各候補領域において復号が実行されることになる。候補領域がＱＲコード全体を含有する場合、この領域における復号は成功し得る。候補領域がＱＲコード全体をカバーしない場合、この領域における復号は当然ながら失敗することになる。
【００５２】
図７に示される現行の方法は、ＱＲコードが画像内でＮピクセル以下である場合には良好に機能する（Ｎは画像縮小率であり、２００ＤＰＩの画像に対して８である）。
【００５３】
図７に示される現行の実施態様によってサポートされる最大ＱＲ構成成分サイズは、上述のＱＲ候補領域位置特定方法に基づいて計算されることができる。
【００５４】
サポートされる最大ＱＲ構成成分サイズは、以下の係数の関数である。
エッジカウントマップを作成するのに使用される画像縮小率Ｎ、および
画像解像度ＤＰＩ。
【００５５】
エッジカウントマップ内の各ピクセルは、Ｎ×Ｎ領域内のエッジ点の数を表す。或るＱＲ構成成分のサイズがＮピクセルよりも大きい場合、Ｎ×Ｎ領域内で何らかのエッジ点が検出される可能性は低い。この事例において、エッジカウントマップはよりまばらに分散している傾向にあることになり、エッジ点が１つの領域に連結される可能性は低い。
【００５６】
現行の実施態様に基づくと、エッジ点連結にとって、および、バーコード候補領域位置特定にとっても、Ｎピクセルの最大構成成分サイズが最適ということになる。具体的には、最大ＱＲ構成成分サイズは以下によって与えられる。
Ｍａｘ_ＭＯＤＵＬＥ_ＳＩＺＥ＝Ｎ／ＤＰＩ．
【００５７】
２００ｄｐｉ、３００ｄｐｉおよび６００ｄｐｉの画像解像度に対して、それぞれ、８、１６および３２のスケール係数が使用される。この結果、２００ｄｐｉにおける最大構成成分サイズは０．０４’’となり、３００ｄｐｉにおいては０．０５’’となり、６００ｄｐｉにおいては０．０５’’となる。これらの結果から最小値を選択すると、０．０４’’の最大構成成分サイズがもたらされる。
【００５８】
図８は、その構成成分のサイズが７ピクセルから１７ピクセルに及ぶ１１個のＱＲコードを有する２００ＤＰＩの例示的な入力画像を示す。対応する縮小されたエッジカウント画像が図９に示される。候補領域が図１０に表示されており、実線の長方形の各々が１つの候補領域を含有する。
【００５９】
図１１には、復号に成功したＱＲコードがＱＲコードを囲む実線の長方形として表示されており、５つのＱＲコードが復号されている。それらが１、２、３、４、および６である。残りの６つのＱＲコードは復号できていない。
【００６０】
これらの６つのＱＲコードが失敗することになった理由は以下のとおりである。適切に復号された５つのＱＲコード（ＱＲコード１、２、３、４、６）に対して、ＱＲ全体をカバーする１つのＱＲ候補領域が存在する。より小さいＱＲコードに対しては、ＱＲコード全体をカバーする候補領域が１つしか存在しない。ＱＲコードがより大きくなると、同じＱＲコードエリア内により多くの候補領域が検出される。復号できていないＱＲコード（ＱＲコード５、７、８、９、１０、１１）に対しては、ＱＲコード全体をカバーする単一の候補領域は存在しない。代わりに、複数の小さな領域がＱＲコード領域内で検出されているが、これらのいずれもＱＲコード全体をカバーしてはいない。構成成分サイズが大きくなるとエッジカウントマップ内のエッジ点はすべて連結されるわけではないため、これは通常、大きなＱＲコードにおいて起こる。それゆえ、大きなＱＲコードの復号の失敗は、実際には位置特定問題に起因する。
【００６１】
本発明は、大きなＱＲコードの検出および復号のこの問題を克服する。
図８に示されているもののような大きなＱＲコードを復号するためには、ＱＲコード全体をカバーする候補領域が検出されなければならない。ここで、図１１内のＱＲコード１０を見ると、ＱＲコード１０全体をカバーする候補領域はないが、ＱＲコード１０のエリア内で検出されるいくつかの小さな候補領域はあり、これらの領域は重なり合っていることが分かる。これらの重なり合う領域が１つの大きな領域に融合されれば、この大きな領域はＱＲコード１０全体をカバーすることになる。この所見が、本発明の解決策をもたらした、すなわち、重なり合う領域を融合し、融合領域を候補領域リスト内に追加する。
【００６２】
本発明においては、図７に示される現行のＱＲ候補領域位置特定モジュールに新規のモジュールが追加。図１２は、大きなＱＲコードを位置特定するための本発明の新規の方法１２００の流れ図である。
【００６３】
新規のモジュール１２００の入力には、現行のＱＲ位置特定モジュール（図７）からのＱＲ候補領域７２０の出力をとる。各特定の候補領域について（ステップ１２１０は最初のまたは新たな候補領域を選択する）、新規のモジュール１２００は、その特定の候補領域に重なるすべての領域を見つけるよう試みる（ステップ１２１２）。次に、本方法は、すべての重なり合う領域をともにグループ化して１つのグループにする（ステップ１２１４）。ステップ１２１６は、リスト内にさらに見るべき候補領域があるか否かを判定する。ステップ１２１６が「はい」を返す場合、プロセスは折り返してステップ１２１０に戻って新たな候補領域を選択し、ステップ１２１２および１２１４が繰り返されて追加のグループが形成される。このプロセスはステップ１２１６が「いいえ」を返す、すなわち、リスト内にそれ以上の候補領域がなくなるまで反復する。ステップ１２１８において、最初のものまたは新たなグループが先行するステップにおいて形成されたグループから選択される。特定のグループについて、重なり合う領域は融合されて単一の融合領域になり、その融合領域は候補領域リスト７２０に追加される（ステップ１２２０）。ステップ１２２２は、見るべきグループがこれ以上あるか否かを判定する。ステップ１２２２が「はい」を返す場合、プロセスは折り返してステップ１２１８に戻って新たなグループを選択し、ステップ１２２０が反復して候補領域リストに追加される追加の融合領域を形成する。このプロセスはステップ１２２２が「いいえ」を返す、すなわち、それ以上のグループがなくなるまで反復する。その結果が、新たな候補領域リスト１２２４である。
【００６４】
新たな更新された候補領域リスト１２２４内の各候補領域において復号が実行されることになる。
【００６５】
図１２から、本発明の方法において３つの主要なモジュールが利用されることが分かる、すなわち、（１）すべての重なり合う領域を見つけるためのモジュール、（２）すべての対応する重なり合う領域を１つのグループ内に記録するためのモジュール、および（３）各グループ内の重なり合う領域を融合するとともに融合領域を候補領域リストに追加するモジュール。
【００６６】
図１３は、直接的に重なり合う領域および間接的に重なり合う領域を示す。図１３に示されるように、領域２は領域１に直接的に重なっており、これら２つの領域は本明細書においては「直接的に重なり合う領域」と称される。
【００６７】
図１３に示されるように、領域３は領域２に直接的に重なっており、図２は領域１に直接的に重なっている。領域３および１は本明細書においては「間接的に重なり合う領域」と称される。
【００６８】
本発明はすべての重なり合う領域を見つけるためのモジュールを含む。各特定の候補領域について、このモジュールは、その特定の候補領域に直接的にまたは間接的に重なる領域を求めて検索する。
【００６９】
基本的に、２つのタイプの重なりがある、すなわち、２つの領域は図１４Ａに示されるように水平に重なり合う、または、２つの領域は図１４Ｂに示されるように垂直に重なり合う。
【００７０】
水平に重なり合う領域の場合、ｘ方向におけるそれらの中心間の距離「ＤｉｓＣｘ」（ｃｘ１−ｃｘ２）は、幅の和「Ｗ１＋Ｗ２」に等しく、式中、Ｗ１＝（領域１の幅÷２）であり、Ｗ２＝（領域２の幅÷２）である。この例では、２つの重なり合う領域は、いずれか一方が水平方向において他方からたとえ１ピクセルであっても離れた場合には重ならなくなるという、極端な事例にある。それゆえ、「Ｗ１＋Ｗ２」は２つの領域が水平に重なるか否かを判定するためのしきい値とみなされることができる。水平に重なり合う領域を判定するために以下の式（１）が使用されることができる。
2013131212.tif 000006
【００７１】
同様に、図１４Ｂに示されるような垂直に重なり合う領域を判定するために以下の式（２）が使用されることができる。
2013131212.tif 000007
【００７２】
2013131212.tif 000008
【００７３】
2013131212.tif 000009
2013131212.tif 000010
【００７４】
本発明はすべての重なり合う領域をグループ化するためのモジュールを含む。このモジュールは、見つかったグループ、および各グループ内のすべての重なり合う領域の数を出力する。各領域について、これは「FindOverlappedRegions」を呼び出してすべての直接的に重なり合う領域および間接的に重なり合う領域を見つけ、重なり合う領域、ならびに各グループに関する領域の数およびグループの数を記録する。
【００７５】
グループ内に１つしか領域がない場合、これは、このグループについては重なり合う領域は見つからなかったことを意味する。２つ以上の重なり合う領域を有するグループに対して、重なり合う領域の融合が実行されることになる。関数「GroupOverlappedRegions」のための疑似コードが下記に示される。
2013131212.tif 000011
【００７６】
本発明はすべての重なり合う領域を融合するとともに候補領域リストを更新するためのモジュールを含む。このモジュールは同じグループ内のすべての重なり合う領域を融合し、融合領域を領域リスト内に追加する。「MergeOverlappedRegions」のための疑似コードが下記に示される。
2013131212.tif 000012
【００７７】
本発明の方法１２００の結果を図１５Ａの図１５Ｂに対する比較に見ることができる。
図１５Ａでは１つの大きなＱＲコード、および、現行の（本発明に先立つ）ＱＲ位置特定方法（図７）から検出された、その対応する候補領域が実線の長方形内に表示されており、いずれの単一の候補領域もＱＲコード全体をカバーしていない。これらの候補領域においては、ＱＲコードは復号されないことになる。本発明の新規のＱＲ位置特定モジュール、すなわち方法１２００は図１５Ｂにおける実線で囲む長方形である融合領域を出力し、ＱＲコードはこの領域から正確に復号される。
【００７８】
図８におけるＱＲコードについて、もともと現行の（本発明に先立つ）ＱＲ位置特定方法（図７）によって５つのＱＲコードが位置特定されているため、５つのＱＲコードしか復号されない。本発明の新規のＱＲ位置特定モジュール、すなわち、方法１２００によって、１１個のＱＲコードすべてが位置特定および復号されることができる。結果は、候補領域を実線の長方形として示す図１６、および、各ＱＲコードを囲む実線の長方形として融合領域を示す図１７に示されている。
【００７９】
いくつかの具体的な実施形態とともに本発明が記載されてきたが、さらに多くの代替形態、修正形態および変形形態が上記の記載に照らして明白であることは、当業者には明らかである。従って、本明細書に記載されている本発明は、添付の特許請求項の精神および範囲内に含まれ得るような、すべてのこのような代替形態、修正形態、応用形態および変形形態を包含するように意図される。
【図１】
2013131212.tif 000017
【図２】
2013131212.tif 000018
【図３】
2013131212.tif 000019
【図４】
2013131212.tif 000020
【図５】
2013131212.tif 000021
【図６】
2013131212.tif 000022
【図７】
2013131212.tif 000023
【図８】
2013131212.tif 000024
【図１１】
2013131212.tif 000025
【図１２】
2013131212.tif 000026
【図１３】
2013131212.tif 000027
【図１４】
2013131212.tif 000028
【図１７】
2013131212.tif 000029
【図９】
2013131212.tif 000030
【図１０】
2013131212.tif 000031
【図１５】
2013131212.tif 000032
【図１６】
2013131212.tif 000033