(57)【要約】【課題】グラフィカルバーコード（１０）を自動的に生成し復号化するシステムを提供する。【解決手段】本発明においては、可逆グラフィックス演算が、基本画像（２６）の領域と予め定義されたテンプレートセットから選択される情報符号化グラフィックステンプレート（６６、７２）との間に適用され、グラフィカルバーコード領域と対応する基本画像領域との間に逆のグラフィックス演算を適用することによって、グラフィックステンプレート（６６、７２）を復元可能な領域を有するグラフィカルバーコード（１０）が生成される。【選択図】図３Ａ
2004533072.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他による「Fiducial Mark Patterns for Graphical Bar Codes」と題する本願と同日出願の米国特許出願第０９／８７７５１７号（代理人整理番号１００１６６８９−１）、およびJonathan Yen他による「Automatically Extracting Graphical Bar Codes」と題する本願と同日出願の米国特許出願第０９／８７７５８１号（代理人整理番号１００１５１９１−１）。
【背景技術】
【０００３】
［背景］
一般的なバーコードシンボルは、データ要素またはキャラクタを表す、様々な幅の棒と空間が並列になったパターンである。
棒はバイナリ１のストリングを表し、空間はバイナリ０のストリングを表す。
従来の「一次元」バーコードシンボルは、一次元においてのみ変化する一連の棒と空間を含む。
一次元バーコードシンボルは、比較的小さい情報記憶容量を有する。
「二次元」バーコードは、一次元バーコードシンボルよりも多くの情報を含む機械可読シンボルに対する増えつつあるニーズに応えるために開発された。
二次元バーコードシンボルの情報記憶容量は、バーコードパターンを二次元で変化させることによって一次元バーコードに比して増えている。
一般的な二次元バーコード規格としては、ＰＤＦ４１７、Ｃｏｄｅ１、およびＭａｘｉｃｏｄｅが挙げられる。
一次元および二次元バーコードシンボルは通常、プリントされているバーコードシンボルを電気信号に変換する光学走査技法によって（たとえば、機械的に走査されるレーザービームにより、または自己走査電荷結合素子（ＣＣＤ）により）読み取られる。
電気信号はデジタル化されて復号化され、プリントされているバーコードシンボルに符号化されたデータが復元される。
【０００４】
バーコードは、低情報コンテンツ用途（たとえば、自動価格タグ付けおよび在庫管理）および比較的高情報コンテンツの用途（たとえば、自動郵便読み取りおよび郵便分配システム用に郵便の住所および郵便料金を符号化すること、またプリントされたページの圧縮した内容を符号化すること）を含む様々な用途に使用することができる。
【特許文献１】
ＥＰ６７２９９４
【特許文献２】
米国特許第５７４５５８９号
【特許文献３】
ＷＯ  １１５９９
【発明の開示】
【０００５】
［概要］
本明細書で使用される場合、「グラフィカルバーコード」という用語は、埋め込み情報を符号化する、目立たないグラフィックス変調を含む画像を広く指す。
【０００６】
本発明は、比較的大きい情報容量と、各基本画像パターンに実質的に対応する満足のいく外観とを特徴とするグラフィカルバーコードを生成し復号化する本発明の方式（システムおよび方法）を特徴とする。
【０００７】
本発明の一態様では、可逆グラフィックス演算が、基本画像の領域と、予め定義されたテンプレートセットから選択される情報符号化グラフィックステンプレートとの間に適用されて、グラフィカルバーコード領域と対応する基本画像領域との間に逆のグラフィックス演算を適用することでグラフィックステンプレートを復元可能な領域を有するグラフィカルバーコードが生成される。
【０００８】
本発明のこの態様による実施形態は、以下の特徴の１つまたは複数を含みうる。
【０００９】
実施形態によっては、可逆グラフィックス演算が排他的論理和（ＸＯＲ）演算に対応するものもある。
これら実施形態では、ＸＯＲ演算がグラフィカルバーコード領域と対応する基本画像領域との間に適用されて、グラフィックステンプレートが生成される。
【００１０】
実施形態によっては、基本画像領域およびグラフィックステンプレートはそれぞれ同数のピクセルを有するものもある。
基本画像領域およびグラフィックステンプレートはそれぞれ、好ましくは、同じピクセルレイアウト（たとえば、矩形または非矩形ピクセルアレイ）を有する。
【００１１】
各グラフィックステンプレートは、好ましくは、明ピクセルおよび暗ピクセルのパターンを含む。
明ピクセルの数は、好ましくは暗ピクセルの数よりも多い。
好ましくは、予め定義されたテンプレートセット内の各ピクセル位置が暗ピクセルである確率は等しい。
【００１２】
実施形態によっては、グラフィックステンプレートは、不評のグラフィックステンプレートシーケンスに関連する１つまたは複数の予め定義された規則に従って適応的に順序付けることができるものもある。
【００１３】
本発明の別の態様では、可逆グラフィックス演算が、グラフィカルバーコードの領域と対応する基本画像の領域との間に適用されて、測定ブロックセットが生成され、また最も高い推定確率を有する測定ブロックセットに対応する情報符号化グラフィックステンプレートが、予め定義されたテンプレートセットから選択される。
【００１４】
本発明のこの態様による実施形態は、以下の特徴の１つまたは複数を含みうる。
【００１５】
可逆グラフィックス演算は、好ましくはＸＯＲ演算に対応する。
【００１６】
実施形態によっては、好ましくは、ピクセル値確率が測定ブロック毎に計算されるものもある。
ピクセル値確率は、所与の測定ブロックにわたるグレー値測定の加重平均に基づいて所与の測定ブロックについて計算することができる。
グレー値の加重平均は、所与の測定ブロックにわたるドット位置にマスク（たとえば、トランケートされたガウスプロファイルを有するマスク）を合わせることによって計算することができる。
グレー値測定の加重平均のヒストグラムに合う確率分布（たとえば、非対称ラプラス分布）のパラメータを推定することができる。
【００１７】
本発明の他の特徴および利点は、図面および特許請求の範囲を含む、以下の説明から明らかになろう。
【発明を実施するための最良の形態】
【００１８】
［詳細な説明］
以下の説明において、同様の参照番号を使用して同様の要素を識別する。
さらに、図面は例示的な実施形態の主な特徴を図で示すことを意図する。
図面は、実際の実施形態のあらゆる特徴を示すことも、また図示の要素の相対的な寸法を示すことも意図しておらず、一定の比率で描かれたものではない。
【００１９】
図１を参照すると、一実施形態では、グラフィカルバーコード１０を符号化モジュール１２で生成し、文書処理チャネル１４を通過させ、復号化モジュール１６で復号化することができる。
【００２０】
符号化モジュール１２は、符号化段階１８およびグラフィックス変調段階２０を含む。
符号化モジュール１２は、コンピュータまたは他のプログラム可能なプロセッサ上で実行可能な１つまたは複数のプログラムモジュールとして実施することができる。
動作にあたり、符号化モジュール１２は、情報２２を符号化メッセージ２４中に符号化する。
たとえば、情報２２は、従来の圧縮アルゴリズムに従って圧縮し、誤り修正コードを使用して符号化することができる。
誤り修正符号化は、文書処理チャネル１４によって導入される劣化による誤りに対する堅牢性を提供する。
誤り修正コードをインタリーブして、バーストエラーから守ることも可能である。
実施形態によっては、符号化モジュール１２は、Jonathan Yen他による「Authenticable Graphical Bar Codes」と題する２０００年１２月１日出願の米国特許出願第０９／７２８，２９２号に記載の符号化プロセスに従って、情報２２から確証となる署名付きメッセージを生成するようにプログラムすることができるものもある。
以下に詳細に説明するように、符号化段階１８の中で、圧縮され誤り修正符号化されたメッセージが、順序付きの情報符号化グラフィックステンプレートシーケンスに変換される。
グラフィックス変調段階２０の中で、基本画像２６が順序付きグラフィックステンプレートシーケンスに従って変調され、グラフィカルバーコード１０が生成される。
特に、可逆グラフィックス演算が、基本画像２６の領域と順序付き情報符号化グラフィックステンプレートシーケンスとの間に適用され、グラフィカルバーコード１０が生成される。
基本画像２６は、ロゴ（たとえば、企業ロゴ）、グラフィックス、ピクチャ、テキスト、画像、または視認性を有する任意のパターンを含む任意の２値離散グラフィックスパターンであることができる。
情報２２は、テキスト、ピクチャ、画像、ボーダーまたは基本画像２６の背景のグラフィカルデザイン中に埋め込み、グラフィカルバーコード１０を生成することが可能である。
情報２２は、２値画像（たとえば、明暗ドットパターン）、マルチレベル画像（たとえば、グレーレベル画像）またはマルチレベルカラー画像の形のグラフィカルバーコード１０に埋め込むことができる。
【００２１】
文書処理チャネル１４において、グラフィカルバーコード１０は、プリント段階２８によって１つまたは複数のハードコピー３０に変換することができる。
ハードコピー３０は、走査段階３４により電子走査画像３６に変換する前に、処理段階３２を通して処理することが可能である。
グラフィカルバーコード１０は、従来のプリンタ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＬａｓｅｒＪｅｔ（登録商標）プリンタ）または専用ラベルプリント装置によってプリントしうる。
ハードコピー３０は、預金引き出し認可署名のグラフィカルバーコードが記された銀行為替手形（または小切手）、認証証明書のグラフィカルバーコードが記された株券または債券、および料金別納郵便物の証印のグラフィカルバーコードが記された封筒を含む多種多様なプリントされた材料のいずれか１つの形であることができる。
ハードコピー３０は、従来のデスクトップ光学スキャナ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＳｃａｎＪｅｔ（登録商標）スキャナ）またはポータブルスキャナ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＣａｐＳｈａｒｅ（登録商標）ポータブルスキャナ）で走査することが可能である。
スキャナによって得られ、復号化モジュール１６に導入される走査画像３６は、元のグラフィカルバーコード１０を劣化させたものである。
こうした劣化は、プリント段階２８、処理段階３２（たとえば、コピー劣化、しみ、折り曲げ、ステープルおよびマーキング）および走査段階３４を含む文書処理チャネル段階の１つまたは複数で生じうる。
【００２２】
概して、復号化モジュール１６は、事前処理段階４０、位置合わせ段階４２、ジオメトリック修正段階４４、確率解析段階４６、グラフィックス復調段階４８および復号化段階５０を含む。
復号化モジュール１６は、コンピュータまたは他のプログラム可能なプロセッサ上で実行可能な１つまたは複数のプログラムモジュールとして実施することができる。
事前処理段階４０の中で、走査グラフィカルバーコード画像５２を走査画像３６上に配置することができ、非バーコード領域を走査画像３６からクロッピングし、かつトリミングすることができる。
位置合わせ段階４２の中で、走査バーコード画像５２中の基準目印が検出される。
検出された基準目印の構成により、文書処理チャネル１４を通してハードコピー３０の伝送中にグラフィカルバーコードに導入された可能性のある全体の変形のタイプが示される。
これら全体の変形（たとえば、平行移動、回転、アフィン、およびスキュー的な歪みをジオメトリック修正段階４４の中で修正することができ、これは、Doron Shaked他による「A Method and Apparatus for Generating and Decoding a Visually Significant Bar Code」と題する２０００年５月２５日出願の米国特許出願第０９／５７９，０７０号に記載されている。
確率解析段階４６の中で、確率モデルが、位置合わせされ幾何学的形状が修正された走査バーコード画像５３から得られるピクセル値測定に適用され、確率パラメータ５４のセットが生成される。
以下に詳細に説明するように、確率パラメータ５４は、グラフィックス変調段階４８の中で、基本画像２６中に最初に符号化されたグラフィックステンプレートシーケンスに対応する情報符号化グラフィックステンプレートの最も起こりうるシーケンスを選択するために使用される。
選択されたグラフィックステンプレートシーケンスが符号化メッセージ５６に変換され、符号化メッセージ５６が復号化段階５０によって情報２２に復号化される。
【００２３】
図２、図３Ａおよび図３Ｂを参照すると、以下のグラフィックス符号化方式に従って基本画像２６をグラフィックス変調することによって、グラフィカルバーコード１０を生成することができる。
基本画像２６は複数のサブマトリックス（またはサブ画像）に分割される（ステップ６０）。
たとえば、基本画像２６がＭ×Ｎピクセル画像の場合、規則正しい配列のＯＫ×Ｋピクセルサブマトリックスに分割することができる。
但し、Ｏ＝Ｍ×Ｎ／（Ｋ×Ｋ）である。
基本画像２６の中の１つまたは複数の領域が基準目印用に確保される（ステップ６２）。
一実施形態では、基本画像２６の４つの角を基準目印用に確保しうる。
他の実施形態では、基準目印は、Doron Shaked他による「Fiducial Mark Patterns for Graphical Bar Codes」と題する本願と同日出願の米国特許出願第    号（代理人整理番号１００１６６８９−１）に記載のように、基本画像２６に外接しうる。
残りの非確保サブマトリックスはラスタ走査順に並べられ、可逆グラフィックス演算（たとえば、ＸＯＲグラフィックス演算）を非確保サブマトリックスと、符号化すべき情報２２に従って順序付けられた情報符号化グラフィックステンプレートシーケンスとに適用することにより、２値バーコードマトリックスに変換される（ステップ６４）。
概して、可逆グラフィックス演算により、基本画像サブマトリックス（ＢＩi）およびグラフィックステンプレート（Ｔj）からグラフィカルバーコード領域（ＧＢＣi）へのマッピング（ｆ）が生成され、このグラフィカルバーコード領域は逆（ｆ）にすることができ、基本画像サブマトリックス（ＢＩi）およびグラフィカルバーコード領域（ＧＢＣi）からグラフィックステンプレート（Ｔｊ）を復元することができる。
すなわち、
【００２４】
ｆ（ＢＩi，Ｔj）→ＧＢＣi              式１
ｆ'（ＢＩi，ＧＢＣi）→Ｔj            式２
である。
一実施形態では、可逆グラフィックス演算は、一対の入力ピクセル値に対して演算を行い、以下のＸＯＲ関数に従って出力ピクセル値を生成するＸＯＲグラフィックス演算に対応する。
【００２５】
【表１】
2004533072.tif 000003
【００２６】
このＸＯＲグラフィックス演算は、以下の式３および式４に示すように、上記の可逆特徴を満たしている。
ＸＯＲ（ＢＩi，Ｔj）→ＧＢＣi          式３
ＸＯＲ（ＢＩi，ＧＢＣi）→Ｔj          式４
【００２７】
このグラフィックス符号化手法によれば、Ｋピクセルの基本画像サブマトリックスが、Ｋ×Ｋピクセルグラフィカルバーコード領域として変調されレンダリングされる。
言い換えれば、各基本画像ピクセルがグラフィカルバーコード１０中の単一ドットとしてレンダリングされるため、基本画像２６の元の解像度がグラフィカルバーコード１０において保存される。
さらに、２つの同一の基本画像領域があり、２つの異なるテンプレートを使用して符号化するものと想定する。
得られる符号化グラフィカルバーコード領域間の違いは、２つの対応するテンプレートパターン間の違いと同じである。
すなわち、ＸＯＲ出力パターン間のハミング距離は、対応するコード間の距離と同一である。
そのため、十分に異なるテンプレートパターンは、十分に異なるＸＯＲ出力パターンを生じさせる。
【００２８】
図３Ａに示すように、グラフィックス符号化の一実施形態では、情報２２を、グラフィックステンプレート６６（またはハーフトーンパターン）のセットに基づいて２値レベルグラフィックスバーコード画像に符号化することができる。
この実施形態では、基本画像２６から分割された非確保サブマトリックス６８が、ＸＯＲグラフィックス演算を基本画像サブマトリックス６８とグラフィックステンプレート６６との間に適用することによって変調される。
グラフィックステンプレート６６は、３×３パターン中の２つの暗ドットに可能な３６個の配置に対応する３×３ピクセルパターンである（３６個のグラフィックステンプレートのうちの５個のみを図３Ａに示す）。
実施形態によっては、３６個すべてのグラフィックステンプレートをメッセージ２４の符号化に使用しうる。
他の実施形態では、テンプレートパターンのうちの３２個のみを５ビットの符号化に使用しうる。
予め定義されたコードセットの選択によって偏りが生じないように、符号化に選択された特定のテンプレートは、３６個のテンプレートを通して循環しうる。
たとえば、コードＣ36（３６個のうちの１つ）を、式５に従って所望のコードＣ32（３２個のうちの１つ）から得ることができる。
Ｃ36＝ｍｏｄ36（Ｃ32＋カウンタ）      式５
式中、カウンタは各使用後に増分される。復号化中、Ｃ32が式６に従ってＣ36から復号化される。
Ｃ32＝ｍｏｄ32（Ｃ36−カウンタ）      式６
【００２９】
図３Ｂに示すように、テンプレートピクセルを規則正しい矩形アレイに配置する必要はない。
この実施形態では、グラフィックステンプレート７２は、スキューした４×２ピクセル配列中の１つあるいは２つの暗ドットの可能な３６個の配置のセットに対応する。
概して、グラフィックス符号化プロセスはｎビット符号化マッピングに拡張することが可能である。
但し、ｎは２以上の整数である。
この手法の情報密度は、ｌｏｇ２Ｌに従ってグラフィックステンプレートの数（Ｌ）とともに増大する。
したがって、図３Ａおよび図３Ｂの各テンプレートセットは、５ビットを越える情報密度を有する。
【００３０】
概して、グラフィカルバーコード１０の外観品質は、グラフィックステンプレートパターンのコントラストレベルとともに向上する。
真に暗い領域と真に明るい領域との間のコントラストが１であると仮定すると、暗と明のグラフィカルバーコード領域７０間の平均コントラスト（Ｃ）は、
Ｃ＝１−２・（Ｄ／Ｋ）                                  式７
によって与えられる。
式中、Ｄは各テンプレートパターン中の暗ドットの数であり、Ｋは各テンプレートパターン中のドット位置の総数である。
図３Ａおよび図３Ｂの実施形態では、コントラストレベルは５／９である。
比較的高いコントラストレベルを特徴とするテンプレートセットを構築することに加えて、グラフィックステンプレート１０の外観品質は、所与のテンプレートセット内の各ピクセル位置が暗ピクセルである確率が等しいテンプレートセットを構築することによって向上させることが可能である。
グラフィカルバーコード１０の外観品質は、暗ドットの局所密度が均一であるテンプレートを構築することによっても向上させることが可能である。
図３Ａおよび図３Ｂの実施形態では、実質的な局所暗密度均一性は、各テンプレートパターン中の暗ピクセルの数を、ピクセル総数の比較的小さい関数に制限することによって達成される。
実施形態によっては、局所暗密度均一性は、テンプレートコードブックの適応可能性を変更することによって向上させることができるものもある。
すなわち、グラフィックステンプレートは、不評なグラフィックステンプレートシーケンスに関連する１つまたは複数の予め定義された規則に従って適応的に順序付けることができる。
たとえば、この手法によれば、復号化プロセス中に、連結したときに局所暗ドット密度を増大させるパターンを有するグラフィックステンプレート対を適応的に回避することができる。
【００３１】
図４、図５、図６および図７を参照すると、一実施形態では、グラフィカルバーコード１０は以下のように復号化することができる。
【００３２】
まず図４を参照すると、走査しかつ位置合わせされたバーコード画像中のピクセルアレイが、元のバーコード画像１０中の個々のピクセルを識別する（ステップ８０）。
通常、グラフィカルバーコードが、元の各ピクセルがｒ×ｒ走査ピクセルアレイに対応するように高解像度で走査される。
文書処理チャネル１４のプリント、処理、および走査プロセスに起因する場合が多い外観の劣化により、得られる走査ピクセルアレイはもはや均質ではなく、その代わりに異なるグレーレベルの走査ピクセルを含む。
こういった状況下で、元のグラフィカルバーコード１０中の各ピクセルに対応する走査ピクセルアレイの境界は、Doron Shaked他による「Geometric Deformation Correction Method and System for Dot Pattern Images」と題する２０００年５月２５日出願の米国特許出願第０９／５７８，８４３号に記載の方法に従って識別される。
【００３３】
以下に詳細に説明するように、走査バーコード画像５２中の各ｒ×ｒピクセルアレイを、元の単一のグラフィカルバーコードピクセルで識別した後、アレイはマスクに関連し（ステップ８２）、確率密度関数パラメータが推定され（ステップ８３）、ピクセル値確率（すなわち、暗（または明）ピクセルである確率）が元の各ピクセル毎に求められる（ステップ８４）。
以下の説明において、ｓは元の１つのピクセルに対応する走査ピクセルアレイとして定義され、その走査ピクセルのグレーレベルはｓi,jで表される。
但し、ｉ、ｊ＝１，・・・、ｒである。
【００３４】
図５を参照すると、グレー値の加重平均が各測定ブロックのピクセル毎に計算される（ステップ８６）。
このため、元の暗ピクセルに対応するアレイと元の明ピクセルに対応するアレイとを判別するｓi,jの関数が、走査ピクセルアレイに適用される。
一実施形態では、式８の線形判別関数が走査ピクセルアレイに適用されて、暗ピクセルと明ピクセルとを判別する。
【００３５】
【数１】
2004533072.tif 000004
【００３６】
式中、係数ｃi,jは、式９の２次元のトランケートされたガウス形状表面の格子値として解釈される。
ｐｏｓ（ｅｘｐ（−（ｘ−ｃ）2／ｓ）−Δ）                式９
式中、ｘはマスク座標を示し、ｃはドットパターンの中心、Δはトランケーション係数、ｓはスカラー係数を示し、ｘ＞０の場合ｐｏｓ（ｘ）＝ｘであり、ｘ≦０の場合ｐｏｓ（ｘ）＝０である。
スカラーｓおよびΔは、走査解像度および期待される変形強度に従って調整される。
一実施形態では、ｓおよびΔは、幅が約１／３ドットサイズのバンドに沿ってマスクが０であり、中心から約１／３ドットサイズ離れたところではその大きさの半分に上がるようにセットされる。
【００３７】
測定を集めて解析して、測定パターンに対応する元のピクセルが暗かそれとも明かを示すしきい値を見つける。
このために、判別関数のヒストグラムが、走査されたハーフトーン画像中のピクセル毎に計算される（ステップ８８）。
ヒストグラム測定は、所与の画像にわたる、位置合わせされ幾何学的形状の修正が行われたドット位置のグレー値の加重平均である。
横軸はグレー値の加重平均の線形関数であり、縦軸はヒストグラム計数軸である。
右側の集団が「明」ピクセルに属し、また左側の集団が「暗」ピクセルに属する。
このようなヒストグラムの形状に基づいて、ｆ（ｓ）の分布を双峰非対称指数分布でモデリングすることができる。
たとえば、一実施形態では、暗（明）ピクセルｙ＝ｆ（ｓ）は、式１０の非対称ラプラス分布に従って分布するものと仮定することが可能である。
【００３８】
【数２】
2004533072.tif 000005
【００３９】
分布関数のパラメータが推定される（ステップ９０）。
パラメータαL、αLおよびμは暗ピクセル集団と明ピクセル集団とで異なるため、この確率手法で推定すべきパラメータの総数は６である。
以下の説明において表記を簡略化するため、暗ピクセルを０で示し、明ピクセルを１で示し、これに従ってパラメータにインデックスを付す。
【００４０】
図７に示すように、計算負荷を低減するために、パラメータ推定プロセス（ステップ９０）は２つのステップ、すなわち（１）μ0、μ1、α0Lおよびα1Rの推定と、（２）α1Lおよびα0Rの推定と、に分けられる。
【００４１】
まず、測定値ｙi＝ｆ（ｇi）が、「暗」ピクセル（Ｎ0）および「明」ピクセル（Ｎ1）の既知の期待数に基づいて２つの集団に分けられる（ステップ９２）。
「暗」集団は最も小さいＮ0測定値を含み、「明」集団は残り（最も大きなＮ1）を含む。
これら集団毎に、以下の最尤近似法（maximum likelihood approximated method）によって、最頻数（μ）が推定される。
μの最尤推定量を最大化するμの値（簡単にするために、０／１の下付きを無視する）が式１１から計算される。
【００４２】
【数３】
2004533072.tif 000006
【００４３】
式中、ＩLはμよりも小さな測定値のセットであり、ＩLはμよりも大きな測定値のセットである。
αLおよびαLの真の値はわからないため、式１２および式１３によるμの各テスト値毎に推定される（ステップ９４）。
【００４４】
【数４】
2004533072.tif 000007
【００４５】
【数５】
2004533072.tif 000008
【００４６】
式中、ＮL＝｜ＩL｜かつＮL＝｜ＩL｜である。
式１２および式１３を式１１に代入し、得られる式を簡単にした後、
【数６】
2004533072.tif 000009
を以下のように表すことができる。
【００４７】
【数７】
2004533072.tif 000010
【００４８】
（ＩLおよびＩL、ひいてはＮLおよびＮLがμの関数であることに留意する）
【００４９】
μの最尤値が式１４から計算される（ステップ９８）。
α0Lおよびα1Rの推定値は、μ0およびμ1に計算された推定値を使用して、式１２および式１３から直接導き出される（ステップ１００）。
【００５０】
μ0、μ1、α0Lおよびα1Rを推定した後、パラメータα1Lおよびα0Rを推定することができる（ステップ１０２）。
（以下、α1Lおよびα0Rそれぞれに表記α1およびα0を用いる）。
μ0よりも低く、μ1よりも高いすべての測定値は無視され、ＩMおよびＮMはＩM＝｛ｙ｜μ0≦ｙ≦μ1｝およびＮM＝｜ＩM｜と定義される。
測定値｛ｙ1：ｉ∈ＩM｝は、以下の分布を有するランダムベクトルからサンプリングされるべきである。
【００５１】
【数８】
2004533072.tif 000011
【００５２】
式中、ｘiは確率Ｐ0およびＰ1それぞれで値０または１をとる。
ＥＭパラダイムを使用してα1およびα0を推定する。
ＥＭアルゴリズムは、パラメータの初期値で開始され、平均最尤目的関数の（局所）極大に収束する一連の更新段階を実行する。
【００５３】
α1およびα0の値を推定するため、式１６の条件付き期待値がアルゴリズムの各段階で最大化される。
【００５４】
【数９】
2004533072.tif 000012
【００５５】
α1Lおよびα0Rの推定値は、最後の更新段階におけるα1およびα0の推定値である。
ＥＭアルゴリズムは、初期化ステップおよび更新ステップを含む。
初期化ステップ中、ｙi毎に、元のピクセルのグレーレベルがｇiで表される。
【００５６】
再び図４を参照すると、ＸＯＲ演算が、走査画像測定ブロックと対応する基本画像領域との間に適用されて、測定ブロックに埋め込まれたテンプレートを復元する（ステップ１０４）。
上に述べたＸＯＲ変調方式によれば、ｇiに対応するハーフトーンピクセルは、０である確率ｇiおよび１である確率（１−ｇi）を有する。
値ｐ0（０｜ｙi）＝ｇiが各ｉ∈ＩM毎に定義される。
更新ステップ中、式１７および式１８が計算される。
【００５７】
【数１０】
2004533072.tif 000013
【００５８】
【数１１】
2004533072.tif 000014
【００５９】
式中、ｐj（１＝ｙi）＝１−ｐj（０｜ｙi）である。
次に、α0（ｊ）、α1（ｊ）およびｐj+1（０｜ｙi）が式１９、式２０および式２１それぞれから計算される。
α0（ｊ）＝１／Ｅ0（ｊ）                        式１９
α1（ｊ）＝１／Ｅ1（ｊ）                        式２０
【００６０】
【数１２】
2004533072.tif 000015
【００６１】
次に、復元されたテンプレートシーケンスに対応する最尤テンプレートシーケンスが選択される（ステップ１０６）。
走査画像Ｓ中の各ピクセルが暗（明）ピクセルからのものである確率が与えられると、適切なコードワードを、以下の最尤アルゴリズムに従ってスコアを付けることができる。
ｗ＝（ｗ1，・・・，ｗL）をＩ中の所与のサブ画像ｐ＝（ｐ1，・・・，ｐL）のコードブックからのコードワードとする。
Ｓ中の対応する走査サブ画像が判別関数値ｙ＝（ｙ1，・・・，ｙL）を有するものと仮定する。
ｗの最尤スコアはｓ（ｗ）＝Ｐ（ｗ｜ｙ）によって与えられる。各コードワードは等しい事前確率を有するため、測定値は統計学的に独立しているという仮定の下で、このスコアは、
【００６２】
【数１３】
2004533072.tif 000016
【００６３】
に等しい。
対数尤度スコアは、
【００６４】
【数１４】
2004533072.tif 000017
【００６５】
により与えられる。
式中、
【数１５】
2004533072.tif 000018
はｗに依存しない定数まで等しいことを意味する。
上で推定した双峰非対称指数分布の式について、Ｐ（ｙi｜０）およびＰ（ｙi｜１）を式２２に代入すると、ｗのスコアは、
【数１６】
2004533072.tif 000019
になる。
式中、Ｆ（ｙi）は、
【００６６】
【数１７】
2004533072.tif 000020
【００６７】
により与えられる。
最高スコアｓｃｒ（ｗ）を達成するコードワードが、埋め込まれたメッセージの復号化に選ばれる（ステップ１０６）。
【００６８】
最後に、選択された順序のグラフィックステンプレートシーケンスが、適切なグラフィックステンプレートコードブックに従ってシンボルに変換される。
シンボルは、復号化モジュール１６の復号化段階５０により情報２２に復号化される。
【００６９】
要約すれば、上記実施形態は、高情報容量およびグラフィカルバーコードが生成される元の基本画像に実質的に対応する外観を特徴とするグラフィカルバーコードを生成し復号化する新規の手法を提供する。
【００７０】
本明細書に述べたシステムおよび方法は、任意の特定のハードウェア構成またはソフトウェア構成に限定されず、むしろ、デジタル電子回路内、またはコンピュータハードウェア、ファームウェア、またはソフトウェア内を含む、任意の計算または処理環境で実施することができる。
符号化および復号化モジュールは、部分的に、コンピュータプロセッサによる実行のために機械可読記憶装置に有形に具体化されたコンピュータプログラム製品に実施することができる。
実施形態によっては、これらモジュールは、好ましくは、高水準手続き型またはオブジェクト指向プログラミング言語で実施されるが、所望であれば、アルゴリズムはアセンブリ言語または機械語で実施してもよい。
いずれの場合でも、プログラミング言語はコンパイル言語またはインタープリタ言語であることができる。
本明細書に述べた符号化および復号化の方法は、たとえば、プログラムモジュールに編成された命令をコンピュータプロセッサが実行して、入力データに対して動作することによってこれら方法を実行し、出力を生成することによって行うことができる。
適切なプロセッサとしては、たとえば、汎用および専用マイクロプロセッサの両方が挙げられる。
概して、プロセッサは命令およびデータを読み取り専用メモリおよび／またはランダムアクセスメモリから受け取る。
コンピュータプログラム命令を有形に具体化するために適した記憶装置としては、たとえば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイス等の半導体メモリ素子を含むすべての形の不揮発性メモリ、すなわち内部ハードディスクおよび取り外し可能ディスク等の磁気ディスク、磁気光学ディスクおよびＣＤ−ＲＯＭが挙げられる。
上記技術はいずれも、特別に設計されたＡＳＩＣ（特性用途向け集積回路）によって捕捉するか、または組み込むことができる。
【００７１】
他の実施形態も特許請求の範囲内にある。
【図面の簡単な説明】
【００７２】
【図１】符号化モジュール、復号化モジュール、および１つまたは複数のグラフィカルバーコードを伝送可能な文書処理チャネルのブロック図である。
【図２】情報をグラフィックス符号化した基本画像をレンダリングする方法の流れ図である。
【図３Ａ】基本画像の領域と情報符号化グラフィックステンプレートのセットとの間に適用されるＸＯＲグラフィックス演算に従って、情報を２値レベルグラフィックスコードにマッピングするテーブルである。
【図３Ｂ】基本画像の領域と代替の情報符号化グラフィックステンプレートのセットとの間に適用されるＸＯＲグラフィックス演算に従って、情報を２値レベルグラフィックスコードにマッピングするテーブルである。
【図４】最尤原理の適用に基づいてグラフィカルバーコードを復号化するプロセスの流れ図である。
【図５】ピクセル値の確率関数パラメータを計算するプロセスのブロック図である。
【図６】図５のブロック８８において計算されるヒストグラムの一例である。
【図７】図６のヒストグラムに合う一対の確率分布関数のパラメータを推定する方法の流れ図である。
【符号の説明】
【００７３】
１０・・・グラフィカルバーコード、
１２・・・符号化モジュール、
１４・・・チャネル、
１６・・・復号化モジュール、
１８・・・符号化、
２０・・・グラフィックス変調、
２２・・・情報、
２６・・・基本画像、
２８・・・プリント、
３２・・・処理、
３４・・・走査、
４０・・・事前処理、
４２・・・位置合わせ、
４４・・・ジオメトリック修正、
４６・・・確率解析、
４８・・・グラフィックス復調、
５０・・・復号化、
６６・・・グラフィックステンプレート、
６８・・・非確保サブマトリックス、
７０・・・グラフィカルバーコード領域、
【図１】
2004533072.tif 000021
【図２】
2004533072.tif 000022
【図３Ａ】
2004533072.tif 000023
【図３Ｂ】
2004533072.tif 000024
【図４】
2004533072.tif 000025
【図５】
2004533072.tif 000026
【図６】
2004533072.tif 000027
【図７】
2004533072.tif 000028
【国際公開パンフレット】
2004533072.tif 000029
2004533072.tif 000030
2004533072.tif 000031
2004533072.tif 000032
2004533072.tif 000033
2004533072.tif 000034
2004533072.tif 000035
2004533072.tif 000036
2004533072.tif 000037
2004533072.tif 000038
2004533072.tif 000039
2004533072.tif 000040
2004533072.tif 000041
2004533072.tif 000042
2004533072.tif 000043
2004533072.tif 000044
2004533072.tif 000045
2004533072.tif 000046
2004533072.tif 000047
2004533072.tif 000048
2004533072.tif 000049
2004533072.tif 000050
2004533072.tif 000051
2004533072.tif 000052
2004533072.tif 000053
2004533072.tif 000054
【国際調査報告】
2004533072.tif 000055
2004533072.tif 000056
2004533072.tif 000057