(57)【要約】【課題】高い検出堅牢性および良好な局所変形トラッキングを特徴とする、グラフィカルバーコード（１０）用の基準目印パターン（７２、７４、１２０）を提供する。【解決手段】一バーコード化方法では、基本画像（２６）がメッセージ（２４）をグラフィックス符号化したものとともに変調されて、グラフィカルバーコード（１０）が生成（prioduce)され、また、１つまたは複数の基準位置およびグラフィカルバーコード（１０）にわたる局所変形をトラッキングするように構成された複数のドットを含む基準目印パターン（７２、７４、１２０）が生成される。別のバーコード化方法では、基準目印候補が基準目印パターン（７２、７４、１２０）中で識別され、識別された基準目印候補の１つまたは複数に基づいて基準目印パスが計算され、計算された基準目印パスに基づいて１つまたは複数の基準位置が識別される。
2004530227.tif 000002
【特許請求の範囲】
【請求項１】
メッセージ（２４）をグラフィックス符号化したものとともに基本画像（２６）を変調することであって、それによってグラフィカルバーコード（１０）が生成される、変調すること、
１つまたは複数の基準位置および前記グラフィカルバーコード（１０）にわたる局所変形をトラッキングするように構成された複数のドットを含む基準目印パターン（７２、７４、１２０）を生成することと
を含むバーコード化方法。
【請求項２】
前記基準目印パターン（７２、７４、１２０）は前記グラフィカルバーコード（１０）を取り囲む
請求項１記載のバーコード化方法。
【請求項３】
前記基準目印パターン（７２、７４、１２０）は基準カラードットおよび背景カラードットを含む
請求項１記載のバーコード化方法。
【請求項４】
前記基準カラードットおよび前記背景カラードットは、特徴的な周期を有するとともに、１つの基準カラードットおよび１つまたは複数の背景カラードットを含む反復パターン（７２、７４、１２０）で配置される
請求項３記載のバーコード化方法。
【請求項５】
前記基準カラードットは、前記グラフィカルバーコード（１０）を取り囲む矩形基準目印パスに沿って配置される
請求項４記載のバーコード化方法。
【請求項６】
前記矩形基準目印パスは、高さ寸法１＋ＨＴおよび幅寸法１＋ＷＴを有し、ＨおよびＷは１以上の整数値を有し、Ｔは特徴的な基準目印パターン周期である
請求項５記載のバーコード化方法。
【請求項７】
前記グラフィカルバーコード（１０）は高さ寸法ＨＴ−２Δ−１および幅寸法ＷＴ−２Ｔ−１を有し、Δは前記グラフィカルバーコード（１０）と前記基準目印パターン（７２、７４、１２０）との間のドット間隔である
請求項６記載のバーコード化方法。
【請求項８】
同じサイズのドットを用いて前記グラフィカルバーコード（１０）および前記基準目印パターン（７２、７４、１２０）をレンダリングすることをさらに含む
請求項１記載のバーコード化方法。
【請求項９】
前記基準目印パターン（１２０）は少なくとも１つの向き目印（１２２）を含む
請求項１記載のバーコード化方法。
【請求項１０】
前記向き目印（１２２）は前記基準目印パターン（１２０）の角位置に配置される
請求項９記載のバーコード化方法。
【請求項１１】
前記向き目印（１２２）は前記基準目印パターン（１２０）の他の目印と異なる
請求項９記載のバーコード化方法。
【請求項１２】
コンピュータ可読媒体上に存在し、コンピュータ可読命令を含むコンピュータプログラムであって、前記コンピュータ可読命令はコンピュータに、
メッセージ（２４）をグラフィックス符号化したものとともに基本画像（２６）を変調し、それによってグラフィカルバーコード（１０）が生成されること、
１つまたは複数の基準位置および前記グラフィカルバーコード（１０）にわたる局所変形をトラッキングするように構成された複数のドットを含む基準目印パターン（７２、７４、１２０）を生成することと
を実行させるコンピュータプログラム。
【請求項１３】
基準目印パターン（７２、７４、１２０）中の基準目印候補を識別すること、
該識別された基準目印候補の１つまたは複数に基づいて基準目印パスを計算すること、
該計算された基準目印パスに基づいて１つまたは複数の基準位置を識別することと
を含むバーコード化方法。
【請求項１４】
前記１つまたは複数の基準位置に基づいて前記グラフィカルバーコード（１０）中の広域変形を補正することをさらに含む
請求項１３記載のバーコード化方法。
【請求項１５】
基準目印候補を識別することは、前記基準目印パターン（７２、７４、１２０）中の基準カラードットの中心を識別することを含む
請求項１３記載のバーコード化方法。
【請求項１６】
識別された基準目印候補の中で、選択されたドットサイズよりも大きなドットサイズを有する前記基準目印候補を破棄することをさらに含む
請求項１３記載のバーコード化方法。
【請求項１７】
識別された基準目印候補の中で、選択された距離よりも長く、前記計算された基準目印パスから離れている前記基準目印候補を破棄することをさらに含む
請求項１３記載のバーコード化方法。
【請求項１８】
前記識別された基準位置の１つから選択された範囲内のところに配置されている基準目印候補は有効基準目印として識別され、その位置は近傍の基準目印候補の基準位置として識別される
請求項１３記載のバーコード化方法。
【請求項１９】
識別された基準位置から選択された範囲外に離間されている基準目印候補を破棄することをさらに含む
請求項１８記載のバーコード化方法。
【請求項２０】
前記基準目印パターン（７２、７４、１２０）中の非対称基準目印候補に基づいて、前記グラフィカルバーコード（１０）の向きを識別することをさらに含む
請求項１３記載のバーコード化方法。
【請求項２１】
コンピュータ可読媒体上に存在し、コンピュータ可読命令を含むコンピュータプログラムであって、前記コンピュータ可読命令はコンピュータに、
基準目印パターン（７２、７４、１２０）中の基準目印候補を識別すること、
該識別された基準目印候補の１つまたは複数に基づいて基準目印パスを計算すること、
該計算された境界パスに基づいて１つまたは複数の基準位置を識別すること、
とを実行させる
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフィカルバーコードの基準目印パターンに関するものである。
【０００２】
［関連出願の相互参照］
本願は、参照により本明細書にそれぞれ援用される以下の同時係属中の出願に関連する。
Doron Shaked他による「A Method and Apparatus for Generating and Decoding a Visually Significant Bar Code」と題する２０００年５月２５日出願の米国特許出願第０９／５７９，０１０号、Renato Kresch他による「System and Method for Counterfeit Protection」と題する１９９９年１０月２８日出願の米国特許出願第０９／４２９，５１５号、Jonathan Yen他による「Authenticable Graphical Bar Codes」と題する２０００年１２月１日出願の米国特許出願第０９／７２８，２９２号、Doron Shaked他による「Geometric Deformation Correction Method and System for Dot Pattern Images」と題する２０００年５月２５日出願の米国特許出願第０９／５７８，８４３号、Doron Shaked他による「Generating and Decoding Graphical Bar Codes」と題する本願と同日出願の米国特許出願第    号（代理人整理番号１００１６６５６−１）、およびJonathan Yen他による「Automatically Extracting Graphical Bar Codes」と題する本願と同日出願の米国特許出願第    号（代理人整理番号１００１５１９１−１）。
【背景技術】
【０００３】
一般的なバーコードシンボルは、データ要素またはキャラクタを表す、様々な幅の棒と空間が並列になったパターンである。
棒はバイナリ１のストリングを表し、空間はバイナリ０のストリングを表す。
従来の「一次元」バーコードシンボルは、一次元においてのみ変化する一連の棒と空間を含む。
一次元バーコードシンボルは、比較的小さい情報記憶容量を有する。
「二次元」バーコードは、一次元バーコードシンボルよりも多くの情報を含む機械可読シンボルに対する増えつつあるニーズに応えるために開発された。
二次元バーコードシンボルの情報記憶容量は、バーコードパターンを二次元で変化させることによって一次元バーコードに比して増えている。
一般的な二次元バーコード規格としては、ＰＤＦ４１７、Ｃｏｄｅ１、およびＭａｘｉｃｏｄｅが挙げられる。
一次元および二次元バーコードシンボルは通常、プリントされているバーコードシンボルを電気信号に変換する光学走査技法によって（たとえば、機械的に走査されるレーザービームにより、または自己走査電荷結合素子（ＣＣＤ）により）読み取られる。
電気信号はデジタル化されて復号化され、プリントされているバーコードシンボルに符号化されたデータが復元される。
【０００４】
バーコードは、低情報コンテンツ用途（たとえば、自動価格タグ付けおよび在庫管理）および比較的高情報コンテンツの用途（たとえば、自動郵便読み取りおよび郵便分配システム用に郵便の住所および郵便料金を符号化すること、またプリントされたページの圧縮した内容を符号化すること）を含む様々な用途に使用することができる。
【特許文献１】
米国特許第５３３７３６１号
【特許文献１】
米国特許第４７７７３５７号
【特許文献１】
米国特許第５５９１９５６号
【発明の開示】
【０００５】
［概要］
本明細書で使用される場合、「グラフィカルバーコード」という用語は、埋め込み情報を符号化する、目立たないグラフィックス変調を含む画像を広く指す。
本発明は、高い検出堅牢性および良好な局所変形トラッキングを特徴とする、グラフィカルバーコード用の基準目印パターンを特徴とする。
【０００６】
本発明の一態様では、基本画像がメッセージをグラフィックス符号化したものとともに変調されて、グラフィカルバーコードが生成され、また、１つまたは複数の基準位置およびグラフィカルバーコードにわたる局所変形をトラッキングするように構成された複数のドットを含む基準目印パターンが生成される。
【０００７】
本発明のこの態様による実施形態は以下の特徴の１つまたは複数を含みうる。
【０００８】
基準目印パターンは前記グラフィカルバーコードを取り囲むことができる。
【０００９】
基準目印パターンは、好ましくは、基準カラードットおよび背景カラードットを含む。
基準カラードットおよび背景カラードットは、特徴的な周期を有するとともに、１つの基準カラードットおよび１つまたは複数の背景カラードットを含む反復パターンで配置することができる。
【００１０】
実施形態によっては、基準カラードットは、グラフィカルバーコードを取り囲む矩形基準目印パスに沿って配置されるものもある。
矩形基準目印パスは、高さ寸法１＋ＨＴおよび幅寸法１＋ＷＴを有し、ＨおよびＷは１以上の整数値を有し、Ｔは特徴的な基準目印パターン周期である。
グラフィカルバーコードは、高さ寸法ＨＴ−２Δ−１および幅寸法ＷＴ−２Ｔ−１を有し、Δはグラフィカルバーコードと基準目印パターンとの間のドット間隔である。
【００１１】
グラフィカルバーコードおよび基準目印パターンは、同じサイズのドットを用いてレンダリングすることができる。
【００１２】
実施形態によっては、基準目印パターンは少なくとも１つの向き目印を含むものもある。
向き目印は、基準目印パターンの角位置に配置することができる。
向き目印は、好ましくは、基準目印パターンの他の目印と異なる。
【００１３】
本発明の別の態様では、基準目印候補が基準目印パターン中で識別され、識別された基準目印候補の１つまたは複数に基づいて基準目印パスが計算され、計算された基準目印パスに基づいて１つまたは複数の基準位置が識別される。
【００１４】
本発明のこの態様による実施形態は、以下の特徴の１つまたは複数を含みうる。
【００１５】
グラフィカルバーコード中の広域変形を、１つまたは複数の基準位置に基づいて補正することができる。
【００１６】
基準目印候補は、基準目印パターン中の基準カラードットの中心を識別することによって識別することが可能である。
識別された基準目印候補の中で、選択されたドットサイズよりも大きなドットサイズを有する基準目印候補を破棄することができる。
識別された基準目印候補の中で、選択された距離よりも長く、前記計算された基準目印パスから離れている基準目印候補も破棄することが可能である。
【００１７】
識別された基準位置の１つから選択された範囲内のところに配置されている基準目印候補は、有効基準目印として識別されることが好ましく、その位置は近傍の基準目印候補の基準位置として識別されることが好ましい。
識別された基準位置から選択された範囲外に離間されている基準目印候補は、破棄することができる。
【００１８】
実施形態によっては、グラフィカルバーコードの向きを、基準目印パターン中の非対称基準目印候補に基づいて識別することが可能であるものもある。
【００１９】
本発明の他の特徴および利点は、図面および特許請求の範囲を含む、以下の説明から明らかになろう。
【発明を実施するための最良の形態】
【００２０】
［詳細な説明］
以下の説明において、同様の参照番号を使用して同様の要素を識別する。
さらに、図面は例示的な実施形態の主な特徴を図で示すことを意図する。
図面は、実際の実施形態のあらゆる特徴を示すことも、また図示の要素の相対的な寸法を示すことも意図しておらず、一定の比率で描かれたものではない。
【００２１】
図１を参照すると、一実施形態では、グラフィカルバーコード１０を符号化モジュール１２で生成し、文書処理チャネル１４を通して処理し、復号化モジュール１６で復号化することができる。
【００２２】
符号化モジュール１２は、符号化段階１８およびグラフィックス変調段階２０を含む。
符号化モジュール１２は、コンピュータまたは他のプログラム可能なプロセッサ上で実行可能な１つまたは複数のプログラムモジュールとして実施することができる。
動作にあたり、符号化モジュール１２は、情報２２を符号化メッセージ２４中に符号化する。
たとえば、情報２２は、従来の圧縮アルゴリズムに従って圧縮し、誤り修正コードを使用して符号化することができる。
誤り修正符号化は、文書処理チャネル１４によって導入される劣化による誤りに対する堅牢性を提供する。
誤り修正コードをインタリーブして、バーストエラーから守ることも可能である。
実施形態によっては、符号化モジュール１２は、Jonathan Yen他による「Authenticable Graphical Bar Codes」と題する２０００年１２月１日出願の米国特許出願第０９／７２８，２９２号に記載の符号化プロセスに従って、情報２２から確証となる署名付きメッセージを生成するようにプログラムすることができる。
符号化段階１８の中で、圧縮され誤り修正符号化されたメッセージが、順序付きの情報符号化グラフィックステンプレートシーケンスに変換される。
グラフィックス変調段階２０の中で、基本画像２６が順序付きグラフィックステンプレートシーケンスに従って変調され、グラフィカルバーコード１０が生成される。
基本画像２６は、ロゴ（たとえば、企業ロゴ）、グラフィックス、ピクチャ、テキスト、画像、または視認性を有する任意のパターンを含む任意のグラフィックスパターンであることができる。
情報２２は、テキスト、ピクチャ、画像、ボーダーまたは基本画像２６の背景のグラフィカルデザイン中に埋め込み、グラフィカルバーコード１０を生成することが可能である。
情報２２は、２値画像（たとえば、明暗ドットパターン）、マルチレベル画像（たとえば、グレーレベル画像）、またはマルチレベルカラー画像の形のグラフィカルバーコード１０に埋め込むことができる。
【００２３】
文書処理チャネル１４において、グラフィカルバーコード１０は、プリント段階２８によって１つまたは複数のハードコピー３０に変換することができる。
ハードコピー３０は、走査段階３４により電子走査画像３６に変換する前に、処理段階３２を通して処理することが可能である。
グラフィカルバーコード１０は、従来のプリンタ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＬａｓｅｒＪｅｔ（登録商標）プリンタ）または専用ラベルプリント装置によってプリントしうる。
ハードコピー３０は、預金引き出し認可署名のグラフィカルバーコードが記された銀行為替手形（または小切手）、認証証明書のグラフィカルバーコードが記された株券または債券、および料金別納郵便物の証印のグラフィカルバーコードが記された封筒を含む多種多様なプリントされた材料のいずれか１つの形であることができる。
ハードコピー３０は、従来のデスクトップ光学スキャナ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＳｃａｎＪｅｔ（登録商標）スキャナ）またはポータブルスキャナ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＣａｐＳｈａｒｅ（登録商標）ポータブルスキャナ）で走査することが可能である。
スキャナによって得られ、復号化モジュール１６に導入される走査画像３６は、元のグラフィカルバーコード１０を劣化させたものである。
こうした劣化は、プリント段階２８、処理段階３２（たとえば、コピー劣化、しみ、折り曲げ、ステープルおよびマーキング）および走査段階３４を含む文書処理チャネル段階の１つまたは複数で生じうる。
【００２４】
概して、復号化モジュール１６は、事前処理段階４０、位置合わせ段階４２、ジオメトリック修正段階４４、オプションの確率解析段階４６、グラフィックス復調段階４８および復号化段階５０を含む。
復号化モジュール１６は、コンピュータまたは他のプログラム可能なプロセッサ上で実行可能な１つまたは複数のプログラムモジュールとして実施することができる。
事前処理段階４０の中で、走査グラフィカルバーコード画像５２を走査画像３６内に配置することができ、非バーコード領域を走査画像３６からクロッピングしトリミングすることができ、これは、Jonathan Yen他による「Automatically Extracting Graphical Bar Codes」と題する本願と同日出願の米国特許出願第    号（代理人整理番号１００１５１９１−１）に記載されている。
位置合わせ段階４２の中で、走査バーコード画像５２中の基準目印が検出される。
検出された基準目印の構成により、文書処理チャネル１４を通してのグラフィカルバーコード１０の伝送中にグラフィカルバーコードに導入された可能性のある広域変形のタイプが示される。
これら広域変形（たとえば、平行移動、回転、アフィンおよびスキュー的な歪み）をジオメトリック修正段階４４の中で修正することができ、これは、Doron Shaked他による「Geometric Deformation Correction Method and System for Dot Pattern Images」と題する２０００年５月２５日出願の米国特許出願第０９／５７８，８４３号に記載されている。
確率解析段階４６の中で、一実施形態では、確率モデルが、位置合わせされ幾何学的形状が修正された走査バーコード画像５３から得られるピクセル値測定に適用され、確率パラメータ５４のセットが生成される。
Doron Shaked他による「Generating and Decoding Graphical Bar Codes」と題する、本願と同日出願の米国特許出願第    号（代理人整理番号１００１６６５６−１）に説明されているように、確率パラメータ５４はグラフィックス復調段階４８の中で使用され、基本画像２６中に最初符号化されたグラフィックステンプレートシーケンスに最も対応しそうな情報符号化グラフィックステンプレートシーケンスを選択する。
選択されたグラフィックステンプレートシーケンスが符号化メッセージ５６に変換され、符号化メッセージ５６が復号化段階５０によって情報２２に復号化される。
【００２５】
図２を参照すると、以下のグラフィックス符号化プロセスに従って基本画像２６をグラフィックス変調することによってグラフィカルバーコード１０を生成することができる。
基本画像２６は複数のサブマトリックス（またはサブ画像）に分割される（ステップ６０）。
たとえば、基本画像２６がＭ×Ｎピクセル画像の場合、規則正しい配列のＯＫ×Ｋピクセルサブマトリックスに分割することができる。
但し、Ｏ＝Ｍ×Ｎ／（Ｋ×Ｋ）である。
任意選択で、基本画像の１つまたは複数のサブマトリックスを基準目印用に確保することができる（ステップ６２）。
非確保サブマトリックスは、選択されたグラフィックス符号化プロセスに基づいて２値バーコードマトリックスに変換される（ステップ６４）。
たとえば、１つのグラフィックス符号化実施形態では、Doron Shaked他による「A METHOD and Apparatus for Generating and Decoding a Visually Significant Bar Code」と題する２０００年５月２５日出願の米国特許出願第０９／５７９，０１０号に記載の２×２ハーフトーンパターン（すなわちマトリックス）に基づく２ビット符号化プロセスにより、情報２２を２値レベル画像に符号化することができる。
別のグラフィックス符号化実施形態では、非確保サブマトリックスと符号化すべき情報２２に従って順序付けられた情報符号化グラフィックステンプレートシーケンスとの間に可逆グラフィックス演算（たとえば、ＸＯＲグラフィックス演算）を適用することにより、非確保サブマトリックスを２値バーコードマトリックスに変換することができ、これは、Doron Shaked他による「Generating and Decoding Graphical Bar Codes」と題する本願と同日出願の米国特許出願第    号（代理人整理番号１００１６６５６−１）に記載されている。
以下に詳細に説明するように、基準目印パターンは、１つまたは複数の基準位置および得られるグラフィカルバーコードにわたる局所変形をトラッキングするために生成される（ステップ６６）。
【００２６】
図３を参照すると、一実施形態では、グラフィカルバーコード１０（たとえば、米国郵便サービスのロゴを表す）が、グラフィカルバーコード１０に関して配置されて、１つまたは複数の基準位置およびグラフィカルバーコードにわたる局所変形をトラッキングする複数のドットを含む基準目印パターン７２で取り囲まれる。
本明細書で使用される場合、「ドット」という用語は、グラフィカルバーコードまたは基準目印パターンを形状に関わりなくレンダリングするために使用される任意のマークを指す。
たとえば、ドットは矩形形状または他の任意の幾何学的形状を有しうる。
概して、基準目印パターンは、有効基準目印と無効基準目印とを判別可能であるとともに、欠けている基準目印を有効基準目印から補間することが可能な、容易に検出可能な信号パターンを特徴とする。
得られる有効基準目印および補間された基準目印の組み合わせが、基準位置およびグラフィカルバーコード１０にわたる局所変形の信頼性のある印を提供する。
基準目印パターン７２は、グラフィカルバーコード寸法の実質的な部分をカバーする多種多様なパスに沿って配置された２つ以上の異なるカラードットから形成しうる。
基準目印パスは湾曲しても、または直線であってもよく、グラフィカルバーコード１０を取り囲んでもよく、または通り抜けてもよい。
グラフィカルバーコード１０および基準目印パターン７２は、同じサイズのドットまたは異なるサイズのドットを用いてレンダリングすることができる。
【００２７】
図４を参照すると、一実施形態では、基準目印パターン７４は、グラフィカルバーコード１０を取り囲む矩形基準目印パスに沿って配置された複数の基準カラードット（たとえば、暗ドット７６）および背景カラードット（たとえば、アウトラインに示される明ドット７８）を含む。
基準カラードット７６および背景カラードット７８は、１つの基準カラードットおよび４つの背景カラードットを含み、ドット５個分の周期（Ｔ）を有する反復信号パターンで配置される。
矩形基準目印パスは、１＋７Ｔ（すなわち３６）ドットの幅寸法８０および１＋２Ｔ（すなわち１１）ドットの高さ寸法を有する。
概して、特徴的な信号パターンを繰り返すために、矩形基準目印パスは、１＋ＷＴによって与えられる幅寸法および１＋ＨＴの高さ寸法を有する。
但し、ＷおよびＨは１以上の整数値を有し、基準目印パスの幅寸法８０および高さ寸法８２それぞれに沿って配置された反復信号パターンの数に対応する。
実施形態によっては、グラフィカルバーコード１０および基準目印パターン７４のドット位置間の容易に検出可能な空間関係を提供するために、グラフィカルバーコード１０が、グラフィカルバーコード１０の外縁と基準目印パターン７４の内縁との間のドット個数に対応する整数のドット数Δ分、基準目印パターン７４から離れているものもある。
したがって、上に定義した基準目印パス寸法に関して、グラフィカルバーコード１０は幅寸法ＷＴ−２Δ−１および高さ寸法ＨＴ−２Δ−１を有しうる。
【００２８】
図５を参照すると、一実施形態では、有効基準目印を走査画像３６中の無効基準目印から判別することができ、欠けている基準目印を有効基準目印から補間して情報を得ることができ、この情報から、以下のように走査グラフィカルバーコード中の局所変形を補正することができる。
【００２９】
まず、基準目印候補が識別される（ステップ９０）。
一実施形態では、基準カラードット７６のドット中心を検出することによって基準目印候補が識別される。
検出プロセス中に、基準目印パターン７４の左上の角から開始されるジグザグ走査を使用しうる。
各走査の最初に検出された（しきい値を要する）基準カラーピクセルが、対応する基準目印候補の一部であるとみなされ、その目印のアンカーピクセルとして使用される。
次に、従来のフラッドフィル（flood-fill）アルゴリズムを使用して、アンカーピクセルに結びついた基準カラーピクセルがすべて見つけられる。
基準目印候補の中心は、各目印のピクセルの質量中心にある。
基準目印候補を識別するプロセスに関するさらなる詳細は、Doron Shaked他による「A Method and Apparatus for Generating and Decoding a Visually Significant Bar Code」と題する２０００年５月２５日出願の米国特許出願第０９／５７９，０１０号から得ることができる。
次に、（期待ドットカウントに相対して）面積の大きな基準目印候補は異常値として破棄される（ステップ９２）。
検出された残りの基準目印候補は、期待基準目印パスに近似される（ステップ９４）。
線形パスセグメントから形成される基準目印パス（たとえば、矩形基準目印パス）を有する実施形態では、従来の最小二乗線近似（least squares line fitting)プロセスまたは従来のロバスト線形近似(robust linear fitting)プロセスを使用して、基準目印パスの線形パスセグメントを計算することができる。
選択された距離よりも長く、計算された基準目印パスから離れたドット中心を有する基準目印候補が破棄される（ステップ９６）。
計算された基準目印パスに基づいて、１つまたは複数の基準位置が識別される（ステップ９８）。
たとえば、線形パスセグメントから形成される基準目印パスを有する実施形態では、基準目印パスの計算された線形パスセグメントの交点を基準角位置として識別することができる。
識別された基準角位置を使用して、グラフィカルバーコード１０にわたる広域変形を補正することができ、これは、Doron Shaked他による「A Method and Apparatus for Generating and Decoding a Visually Significant Bar Code」と題する２０００年５月２５日出願の米国特許出願第０９／５７９，０１０号に記載されている。
【００３０】
次に、残りの基準目印候補を、計算された基準目印パス上に並べる（ステップ１００）。
他の基準目印候補から実質的に同期ずれしている基準目印候補は、異常値として破棄される（ステップ１０２）。
上で説明したように、元々生成された基準目印信号パターンは、１つの基準カラードットおよび１つまたは複数の背景カラードットの反復パターンを含みうる。
したがって、各有効基準目印の中心は、他の有効基準目印の選択された範囲（すなわち、信号周期の整数倍に、選択された変形しきい値を加算または減算したもの）内にあるものと予期される。
たとえば、一実施形態では、同期プロセスは、識別された基準位置（たとえば、角基準位置）から開始される。
計算された基準角位置の選択された範囲内にある最初の基準目印候補が有効基準目印として識別され、その位置が次の基準目印候補の基準位置として識別される。
最初の有効基準目印が最初の期待基準目印位置に対応する場合があり、この場合、基準目印候補は、Ｔ＋−δドットの距離分、計算された基準角位置から離れているものと予期される（但し、δはドット間隔の何分の一かでありうる）。
計算された角位置の近傍の基準目印候補の１つまたは複数が欠けている場合（たとえば、検出されなかったか、または異常値として破棄されたことにより）、最初の有効基準目印は、Ｎ（Ｔ＋−δドット）分、計算された基準角位置から離れているものと予期される（但し、Ｎは１以上の整数値を有する）。
残りの有効基準目印の期待される位置は同様にして、更新された基準位置に基づいて計算することができる。
【００３１】
有効基準目印のドット境界面位置が識別される（ステップ１０４）。
ドット境界面位置は、Doron Shaked他による「Geometric Deformation Correction Method and System for Dot Pattern Images」と題する２０００年５月２５日出願の米国特許出願第０９／５７８，８４３号に記載のように計算することができる。
たとえば、従来の補間プロセスを使用して、欠けている基準目印のドット境界面位置を、計算された有効ドット境界面位置から補間することができる（ステップ１０６）。
次に、ドット境界面位置をグラフィックス復調段階４８に送ることができる（ステップ１０８）。
計算されたドット境界面位置は新しい非デカルト座標系を提供し、グラフィックス復調段階４８は、この非デカルト座標系をグラフィカルバーコード１０にわたる空間の変形を補正するために使用することができる。
【００３２】
図６に示すように、実施形態によっては、基準目印パターン１２０は、その他の基準目印と異なる（または非対称な）少なくとも１つの向き目印１２２を含みうる。
向き目印は容易に検出することが可能であり、それぞれの位置を用いて、復号化プロセス開始前にグラフィカルバーコード１０の適当な向きを決定することができる。
このようにして、回転対称なグラフィカルバーコードの適当な向きを決定することに関連する問題を回避することができる。
向き目印は、その他の基準目印と異なるサイズを有しうる。
たとえば、図６の実施形態では、向き目印１２２は、基準目印パターン１２０のその他の各基準目印の面積サイズの２倍の面積を有する。
他の実施形態では、向き目印は、その他の基準目印と異なる形状を有しうる。
円形形状、正方形形状、十字形状、六角形形状および矩形形状を含む多種多様な異なるドット形状のうちのいずれか２つを、向き目印および他の基準目印のレンダリングに使用しうる。
好ましくは、向き目印は基準目印パターンの角位置に配置されるが、基準目印パスの片側に沿った他の位置（たとえば、中心位置）に配置してもよい。
【００３３】
本明細書に述べたシステムおよび方法は、任意の特定のハードウェア構成またはソフトウェア構成に限定されず、むしろ、デジタル電子回路内、またはコンピュータハードウェア、ファームウェア、またはソフトウェア内を含む、任意の計算または処理環境で実施することができる。
符号化および復号化モジュールは、部分的に、コンピュータプロセッサによる実行のために機械可読記憶装置に有形に具体化されたコンピュータプログラム製品に実施することができる。
実施形態によっては、これらモジュールは、好ましくは、高水準手続き型またはオブジェクト指向プログラミング言語で実施されるが、所望であれば、アルゴリズムはアセンブリ言語または機械語で実施してもよい。
いずれの場合でも、プログラミング言語はコンパイル言語またはインタープリタ言語であることができる。
本明細書に述べた符号化および復号化の方法は、たとえば、プログラムモジュールに編成された命令をコンピュータプロセッサが実行して、入力データに対して動作することによってこれら方法を実行し、出力を生成することによって行うことができる。
適切なプロセッサとしては、たとえば、汎用および専用マイクロプロセッサの両方が挙げられる。
概して、プロセッサは命令およびデータを読み取り専用メモリおよび／またはランダムアクセスメモリから受け取る。
コンピュータプログラム命令を有形に具体化するために適した記憶装置としては、たとえば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイス等の半導体メモリ素子を含むすべての形の不揮発性メモリ、すなわち内部ハードディスクおよび取り外し可能ディスク等の磁気ディスク、磁気光学ディスクおよびＣＤ−ＲＯＭが挙げられる。
上記技術はいずれも、特別に設計されたＡＳＩＣ（特性用途向け集積回路）によって捕捉するか、または組み込むことができる。
【００３４】
他の実施形態も特許請求の範囲内にある。
【図面の簡単な説明】
【００３５】
【図１】１つまたは複数のグラフィカルバーコードを伝送することが可能な符号化モジュール、復号化モジュールおよび文書処理チャネルのブロック図である。
【図２】基本画像を情報をグラフィックス符号化したものとともにレンダリングし、１つまたは複数の基準位置および得られるグラフィカルバーコードにわたる局所変形をトラッキングするように設計された基準目印パターンを生成する方法の流れ図である。
【図３】グラフィカルバーコードを取り囲む基準目印パターンの線図である。
【図４】１つの基準カラードットおよび４つの背景カラードットの反復パターンから形成された基準目印パターンの線図である。
【図５】走査画像中の有効基準目印と無効基準目印とを判別し、欠けている基準目印を補間して、走査グラフィカルバーコード画像中の局所変形を補正することができる情報を得る方法の流れ図である。
【図６】非対称向き目印を含む基準目印パターンの線図である。
【符号の説明】
【００３６】
１０・・・グラフィカルバーコード、
１２・・・符号化モジュール、
１４・・・チャネル、
１６・・・復号化モジュール、
１８・・・符号化、
２０・・・グラフィックス変調、
２２・・・情報、
２６・・・基本画像、
２８・・・プリント、
３２・・・処理、
３４・・・走査、
４０・・・事前処理、
４２・・・位置合わせ、
４４・・・ジオメトリック修正、
４６・・・確率解析、
４８・・・グラフィックス復調、
５０・・・復号化、
【図１】
2004530227.tif 000003
【図２】
2004530227.tif 000004
【図３】
2004530227.tif 000005
【図４】
2004530227.tif 000006
【図５】
2004530227.tif 000007
【図６】
2004530227.tif 000008
【国際公開パンフレット】
2004530227.tif 000009
2004530227.tif 000010
2004530227.tif 000011
2004530227.tif 000012
2004530227.tif 000013
2004530227.tif 000014
2004530227.tif 000015
2004530227.tif 000016
2004530227.tif 000017
2004530227.tif 000018
2004530227.tif 000019
2004530227.tif 000020
2004530227.tif 000021
2004530227.tif 000022
2004530227.tif 000023
2004530227.tif 000024
2004530227.tif 000025
2004530227.tif 000026
2004530227.tif 000027
【国際調査報告】
2004530227.tif 000028
2004530227.tif 000029
2004530227.tif 000030
2004530227.tif 000031