(57)【要約】      （修正有）【課題】複数のバーコードを検出して復号する。【解決手段】グリッドに関して変調された複数のマークとしてデータを冗長に符号化したバーコードが印刷されたページ上の複数のバーコードを復号する装置。装置はグリッドに含まれる変調された複数のマークを使用してページ上の少なくとも一部のビットマップ表現からグリッドを推定する。そして、グリッドからバーコードの一部である領域を判別し、グリッドを使用して、判別された領域のバーコードを検出して復号する。【選択図】図８
2008159055.tif 000002
【特許請求の範囲】
【請求項１】
グリッドに関して変調された複数のマークとしてデータを冗長に符号化したバーコードが印刷されたページ上の複数のバーコードを復号する方法であって、
前記グリッドに含まれる変調された複数のマークを使用して前記ページ上の少なくとも一部のビットマップ表現から前記グリッドを推定する工程と、
前記グリッドから前記バーコードの一部である領域を判別する工程と、
前記グリッドを使用して前記判別された領域のバーコードを検出して復号する工程とを有することを特徴とする方法。
【請求項２】
前記複数のバーコードは、前記グリッドがそれぞれ異なることを特徴とする請求項１に記載の方法。
【請求項３】
前記変調は空間変調であることを特徴とする請求項１に記載の方法。
【請求項４】
前記複数のバーコードの２つは隣接することを特徴とする請求項２に記載の方法。
【請求項５】
前記推定する工程は、前記グリッドの冗長なグリッドに関連付けられた信頼度を使用して前記グリッドを推定することを特徴とする請求項１に記載の方法。
【請求項６】
前記推定する工程は、
前記グリッドの開始点を識別する工程と、
前記識別された開始点のグリッド間隔及び配向を検出する工程と、
前記信頼度を使用して前記グリッドを増大させる工程とを有することを特徴とする請求項５に記載の方法。
【請求項７】
前記増大させる工程は、
最小グリッド間隔よりも大きい寸法を有し、前記グリッドに関連付けられた少なくとも１つのテリトリを定義する工程と、
前記テリトリの内の規定のピクセル位置に最も近接するグリッド交点に関連付けられた前記開始点ごとに信頼値を計算する工程と、
前記信頼値のうちの最も高い値とのグリッド交点を選択する工程と、
前記選択されたグリッド交点に関連付けられたグリッドを識別する工程と、
前記識別されたグリッドの前記選択されたグリッド交点の近傍の信頼値を決定する工程と、
前記選択する工程から前記決定する工程までを繰り返して前記グリッドのグリッド交点を識別する工程とを有することを特徴とする請求項６に記載の方法。
【請求項８】
前記複数のバーコードから、少なくとも２つのバーコードを検出することを特徴とする請求項１乃至７の何れか１項に記載の方法。
【請求項９】
グリッドに関して変調された複数のマークとしてデータを冗長に符号化したバーコードが印刷されたページ上の複数のバーコードを復号する装置であって、
前記グリッドに含まれる変調された複数のマークを使用して前記ページ上の少なくとも一部のビットマップ表現から前記グリッドを推定する手段と、
前記グリッドから前記バーコードの一部である領域を判別する手段と、
前記グリッドを使用して前記判別された領域のバーコードを検出して復号する手段とを備えることを特徴とする装置。
【請求項１０】
画像をスキャンして前記ビットマップ表現を形成するスキャナを更に備えることを特徴とする請求項９に記載の装置。
【請求項１１】
請求項１０に記載の装置を備えることを特徴とする写真複写機。
【請求項１２】
複写機と、
請求項９に記載の装置とを備え、
前記複写機は、複写されるページに対応する前記ビットマップ表現を提供し、前記装置におけるバーコードの復号に応じて、前記ページを複写すること、又は前記ページを複写しないことの何れかを提供するように動作することを特徴とするシステム。
【請求項１３】
請求項１乃至８の何れか１項に記載の方法をコンピュータに実行させるためのプログラム。
【請求項１４】
請求項１３に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の符号化されたデータを検出することに関し、具体的には、画像の符号化されたデータの複数のセットを検出することに関する。
【背景技術】
【０００２】
画像データの無許可複写を防止するいくつかの方法が存在する。これらの方法は通常、複写される画像に固定パターン又は証印を位置付けることに基づいている。或いは、一部の従来技術はデータメッセージを符号化する証印を有し、証印はデコーダで検出するための位置合わせ又は同期化マークを有する。その他の従来技術では、ページ上の複数の１次元バーコードを検出する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
更に、画像の真正性を判別するために、画像に含まれる複数の電子透かしを埋め込み、検出するための方法が存在する。これらの方法は、様々な特徴を有する複数の電子透かしを画像に埋め込むことを必要とする。電子透かしの特徴は、画像がその後複写される場合に様々な方法で電子透かしが影響を受けるように選択される。この方法は、原稿と複写を区別することに限定され、コピー攻撃で一般に見られるような、画像上に任意に配置された電子透かしを検出することには役立たない。
【課題を解決するための手段】
【０００４】
本発明の１つの態様によれば、グリッドに関して変調された複数のマークとしてデータを冗長に符号化したバーコードが印刷されたページ上の複数のバーコードを復号する方法であって、
前記グリッドに含まれる変調された複数のマークを使用して前記ページ上の少なくとも一部のビットマップ表現から前記グリッドを推定する工程と、
前記グリッドから前記バーコードの一部である領域を判別する工程と、
前記グリッドを使用して前記判別された領域のバーコードを検出して復号する工程とを有する。
【０００５】
通常、複数のバーコードは、前記グリッドがそれぞれ異なる。また、変調は、望ましくは空間変調である。一般に、複数のバーコードの２つは隣接する。
【０００６】
好ましくは、推定する工程はそれぞれ、前記グリッドの冗長なグリッドに関連付けられた信頼度を使用して前記グリッドを推定する。
【０００７】
通常、推定する工程は、
前記グリッドの開始点を識別する工程と、
前記識別された開始点のグリッド間隔及び配向を検出する工程と、
前記信頼度を使用して前記グリッドを増大させる工程とを有する。
【０００８】
更に、増大させる工程は、
最小グリッド間隔よりも大きい寸法を有し、前記グリッドに関連付けられた少なくとも１つのテリトリを定義する工程と、
前記テリトリの内の規定のピクセル位置に最も近接するグリッド交点に関連付けられた前記開始点ごとに信頼値を計算する工程と、
前記信頼値のうちの最も高い値とのグリッド交点を選択する工程と、
前記選択されたグリッド交点に関連付けられたグリッドを識別する工程と、
前記識別されたグリッドの前記選択されたグリッド交点の近傍の信頼値を決定する工程と、
前記選択する工程から前記決定する工程までを繰り返して前記グリッドのグリッド交点を識別する工程とを有する。
【０００９】
その他の態様も開示される。
【００１０】
本発明の少なくとも１つの実施形態は、これ以降、図面を参照して説明される。
【発明の効果】
【００１１】
本発明によれば、複数のバーコードを検出して復号することができる。
【発明を実施するための最良の形態】
【００１２】
本開示は、画像内の複数のドットパターンを復号することに関する。各ドットパターンは、少なくとも１つのデータメッセージを符号化した変調されたドットのグリッドである。好ましい実施態様において、各ドットパターンは位置合わせ又は同期化マークを有する必要はないことに留意されたい。しかし、それにもかかわらず本実施態様は、位置合わせ又は同期化マークを実際に含む複数のドットパターンを検出することができる。
【００１３】
好ましい実施態様は、写真複写機に組み込まれているか、又は写真複写機にリンクされているソフトウェアにおいて実施される。ドットパターンを含む画像が写真複写機を使用して複写されようとしているとき、画像は複数のドットパターンを検出するために分析される。復号されたメッセージにより、画像が複製され得るか否かが判定される。例えば、入力画像から復号された４つのメッセージのうちの、３つのメッセージが複写を許可し、１つのメッセージが複写を禁止する場合、入力画像は複写されない。更に、代替実施形態は、複写を禁止するドットパターン領域を除外して、複写を許可するドットパターン領域のみを複製することができる。
【００１４】
代替の実施態様においては、本実施形態及びそれらの関連する復号されたメッセージによって識別されているドットパターン領域をオペレータが視覚的に識別することが可能である。
【００１５】
説明する方法は、図２３に示すような、写真複写機２３１５に結合されたコンピュータシステム２３００を使用して実施されても良い。図１〜図２２のプロセスは、コンピュータシステム２３００内で実行可能な１つ以上のアプリケーションプログラムなどのソフトウェアとして実施されても良い。したがって、コンピュータシステム２３００は、試行される複写操作を検出でき、そのため、複写プロセスにおいて写真複写機２３１５を集合的に形成するスキャナ及びプリンタを制御できる。特に、バーコード検出及びコピー防止の方法のステップは、コンピュータシステム２３００内で実行されるソフトウェアの命令によって達成される。命令は、各々１つ以上の特定のタスクを実行する、１つ以上のコードモジュールとして形成されても良い。また、ソフトウェアは、検出方法を実行する第１の部分及び対応するコードモジュールと、その第１の部分とユーザとの間のユーザインターフェイスを管理する第２の部分及び対応するコードモジュールの２つの別個の部分に分割されても良い。ソフトウェアは、例えば以下に説明する記憶装置を含むコンピュータ読み取り可能な記録媒体に格納されても良い。ソフトウェアは、コンピュータ読み取り可能な記録媒体からコンピュータシステム２３００にロードされ、その後コンピュータシステム２３００によって実行される。そのようなソフトウェア又はコンピュータプログラムが記録されたコンピュータ読み取り可能な記録媒体は、コンピュータプログラム製品である。コンピュータシステム２３００におけるコンピュータプログラム製品の使用は、好ましくはバーコード検出のための有利な装置を達成する。
【００１６】
図２３から分かるように、コンピュータ２３００は、コンピュータモジュール２３０１、入力装置、及び出力装置、更に写真複写機２３１５への接続によって形成される。入力装置はキーボード２３０２及びマウスポインタ装置２３０３などである。出力装置はディスプレイ装置２３１４及び拡声器２３１７を含む。外部変復調装置（モデム）送受信装置２３１６が、接続２３２１を介して通信ネットワーク２３２０との間で通信するために、コンピュータモジュール２３０１によって使用されても良い。ネットワーク２３２０は、インターネット又はプライベートＷＡＮなどの、ワイドエリアネットワーク（ＷＡＮ）であっても良い。ここで、接続２３２１は電話回線であり、モデム２３１６は従来の「ダイヤルアップ」モデムでも良い。或いは、接続２３２１は大容量（例えば、ケーブル）接続であり、モデム２３１６はブロードバンドモデムでも良い。また、無線モデムが、ネットワーク２３２０への無線接続に使用されても良い。ネットワーク２３２０及び２３２２は、望ましくは同様の方法で制御されるその他の写真複写機へのアクセスを提供することができる。
【００１７】
コンピュータモジュール２３０１は通常、少なくとも１つの処理装置２３０５と、例えば半導体のランダムアクセスメモリ（ＲＡＭ）及び読み取り専用メモリ（ＲＯＭ）などの記憶素子２３０６とを含む。また、モジュール２３０１は、オーディオ−ビデオインターフェイス２３０７、入出力インターフェイス２３１３、及びインターフェイス２３０８など、多くの入出力（Ｉ／Ｏ）インターフェイスも含む。オーディオ−ビデオインターフェイス２３０７はビデオディスプレイ２３１４及び拡声器２３１７を結合する。入出力インターフェイス２３１３はキーボード２３０２及びマウス２３０３とオプションのジョイスティック（不図示）用である。インターフェイス２３０８は外部モデム２３１６及び写真複写機２３１５用である。一部の実施態様において、モデム２３１６は、例えばインターフェイス２３０８内など、コンピュータモジュール２３０１内に組み入れられても良い。また、コンピュータモジュール２３０１は、接続２３２３を介してローカルコンピュータネットワーク２３２２へコンピュータシステム２３００を結合可能にするローカルネットワークインターフェイス２３１１も有する。ローカルコンピュータネットワーク２３２２はローカルアリアネットワーク（ＬＡＮ）として知られている。また、図示するように、ローカルネットワーク２３２２は通常、所謂「ファイヤウォール」装置又は同様の機能を含む接続２３２４を介してワイドネットワーク２３２０に結合することもできる。インターフェイス２３１１は、Ethernet（登録商標）回路カード、無線Bluetooth（登録商標）又はIEEE802.11無線配列によって形成されても良い。
【００１８】
インターフェイス２３０８及び２３１３は、シリアル及びパラレルの両接続を供給することができ、シリアル接続は通常、ユニバーサルシリアルバス（ＵＳＢ）規格に準拠して実施され、対応するＵＳＢコネクタ（不図示）を有する。記憶装置２３０９が提供され、通常はハードディスクドライブ（ＨＤＤ）２３１０を含む。フロッピー(登録商標)ディスクドライブ及び磁気テープドライブ（不図示）など、その他の装置が使用されても良い。光ディスクドライブ２３１２が通常、データの不揮発性ソースとしての役割を果たすために提供される。例えば、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、ＵＳＢ−ＲＡＭ、及びフロッピー（登録商標）ディスクのようなポータブルメモリデバイスがシステム２３００への適切なデータソースとして使用されても良い。
【００１９】
コンピュータモジュール２３０１のコンポーネント２３０５から２３１３は通常、相互接続バス２３０４を介して従来技術分野の当業者に既知のコンピュータシステム２３００の操作の標準的なモードをもたらす方法で通信する。説明されている配置が実施されうるコンピュータの例は、IBM-PC及び互換機、Sun Sparcstations、Apple Mac（登録商標）、又はそこから進化した同様のコンピュータシステムを含む。
【００２０】
通常、上述のアプリケーションプログラムは、ハードディスクドライブ２３１０に常駐し、プロセッサ２３０５によって読み取られて実行中に制御される。そのようなプログラムと、ネットワーク２３２０及び２３２２から取り出されたデータの中間ストレージは、おそらくはハードディスクドライブ２３１０と協調し、半導体メモリ２３０６を使用して達成される。一部の例において、アプリケーションプログラムは１つ以上のＣＤ−ＲＯＭに符号化されてユーザに供給され、対応するドライブ２３１２を介して読み取られるか、或いはネットワーク２３２０又は２３２２からユーザによって読み取られても良い。更に、ソフトウェアは、その他のコンピュータ可読媒体からコンピュータシステム２３００にロードされても良い。コンピュータ可読媒体とは、実行及び／又は処理のために命令及び／又はデータをコンピュータシステム２３００に提供することに関与する任意の記憶媒体を指す。そのような媒体の例は、そのようなデバイスがコンピュータモジュール２３０１の内部であるか外部であるかにかかわらず、コンピュータ可読カードを含む。コンピュータ可読カードは、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ−ＲＯＭ、ハードディスクドライブ、ＲＯＭ、又は集積回路、光磁気ディスク、又はＰＣＭＣＩＡカードなどである。更に、コンピュータ可読伝送媒体の例は、無線又は赤外線伝送チャネル及び他のコンピュータ又はネットワーク装置へのネットワーク接続及び電子メール伝送とＷｅｂサイトなどに記録される情報を含むインターネット又はイントラネットを含む。
【００２１】
前述したアプリケーションプログラムの第２の部分及び対応するコードモジュールは、ディスプレイ２３１４上に描写又は表現されるように１つ又は複数のグラフィカルユーザインターフェイス（ＧＵＩ）を実施するために実行されても良い。キーボード２３０２及びマウス２３０３の操作を通じ、コンピュータシステム２３００及びアプリケーションのユーザがインターフェイスを操作して、ＧＵＩに関連付けられているアプリケーションに制御コマンド及び／又は入力を供給することができる。
【００２２】
マーク検出の方法は、代替として、画像処理の機能又は副次機能を実行する１つ以上の集積回路などの専用ハードウェアにおいて実施されても良い。そのような専用ハードウェアは、グラフィックプロセッサ、デジタルシグナルプロセッサ、又は１つ以上のマイクロプロセッサ及び関連するメモリを含むことができる。更に、写真複写機２３１５に結合されたコンピュータシステム２３００を参照して説明したが、コンピュータシステム２３００の前述した機能の多くは、写真複写機２３１５に組み込まれても良いため、特定のローカル操作が可能になる。
【００２３】
１．基本構造
図１は、変調されたグリッド１００の外観を示す拡大図である。変調されたグリッド１００は、正方形グリッド１０１の交点１０３に近接して位置する多数のドット１０２で形成される。眼に見える変調されたグリッド１００を形成するのはドット１０２のみであること、及びグリッド１０１は単にドット１０２の位置を説明するために示されていることに留意されたい。変調されたグリッドの外観は、ドットの規則的なグリッドの外観と類似しているが、同一ではない。図２は、正方形グリッド２０１上に位置するドット２０２の規則的なグリッド２００の外観を示す図である。正方形グリッド２０１は、ここで「グリッド間隔」として参照するピッチ２０３を有する。
【００２４】
図２のドット２０２の規則的配列２００と、図１の変調されたグリッド１００との相異は、次のようである。図１における変調されたグリッド１００のドット１０２の位置が、図２の真に規則的な配列２００の一部であったならば占有するであろうグリッド位置からわずかに外れて変調されて（つまり、空間変調されて）いることである。この空間変調は２つの目的に適っているが、第１の目的は、変調されたグリッドのドット１０２を規則的グリッド２００のドット２０２よりもわずかに見えにくくすることである。これは、人間の視覚体系が規則的なグリッドに注目することに非常に熟達しているからである。交点に関する変調の第２の目的は、デジタルデータの形態のメッセージがドットの変調で格納されうることである。したがって、変調されたグリッドは、データのバーコード表現とみなすことができ、一旦印刷されると、スキャン可能な画像を形成し、符号化されたメッセージ又はバーコードがその画像から復調されうる。スキャンされた画像は通常、冗長に表現されたバーコードの符号化された情報を含む、ページのビットマップ表現を備える。
【００２５】
図３は、ドットの空間変調を詳細に示す図である。図３において、ドット３０２は規則的グリッド３０１の交点に近接して位置し、各ドット３０２は、グリッド交点に関して、８つの可能な位置のうちの１つ３０３に変調される。この特定の場合において、各ドットの８つの可能な位置は、当該のグリッド交点を中心にして円形に配置される。８つの変調位置は、グリッド交点からの水平方向、垂直方向、又は斜め方向のオフセットであり、斜め方向は、水平方向と垂直方向の組み合わせである。ドット３０２がそれぞれオフセットされる水平方向及び垂直方向の距離は、ここでは「ｍｑ」として省略された変調量３０４と称す。
【００２６】
図４は、８つのドット変調位置３０３を更に詳細に示す図である。位置３０３は、グリッド４０２のグリッド交点４０４を中心とし、位置４０１などの各変調位置は、値４０３などの関連付けられた３ビットのデジタルコード値を有する。８つの変調位置（４０１を含む）は、各ドットが８つの可能なデジタルコード値（位置４０１のコード値４０３を含む）のうちの１つを符号化できるようにする。これにより、変調されたグリッドは、変調されたグリッドの各ドットが１つの８進数のデータを格納する、デジタルデータストアとしての役割を果たしている。ドットが円内のグレーコードに配列されるように、各ドットがコード値を符号化することが理想的である。これは、復号中のエラー修正を容易にする。図４は、各ドットのデジタルコード値を２進法で示す図である。このように、コード値４０３から右回りに開始し、ドットは５、７、６、２、３、１、０、及び４の値を符号化する。
【００２７】
デジタルデータストアの数字の好ましい順序付けは、図５に示すようにドットの長方形配列を使用することにより提供される順序付けである。この順序付けは、最上部の左端のドット５０１から開始して、左から右へ、次いで上部から下部へと進み、最下部の右端のドット５０３に到達するまで行われる。当然ながら、他の順序付けを使用することも可能である。
【００２８】
２．符号化
図６は、タイル状に配置されたドキュメント６１０の符号化された部分を示す図である。ドキュメント６１０は、一連のタイル６８０からなる。タイル６８０は、グリッド正方形で測定された、予め定められた高さｔｙ６４０、及び幅ｔｘ６５０を有する。各タイル６８０は、構造内のデータメッセージを上述のように符号化する小データ部分６２０と、余剰部分６３０とを含む。グリッド正方形で測定された、予め定められた高さｃｙ６６０、及び幅ｃｘ６７０を有する小データ部分６２０は、ドキュメント６１０全体に渡り繰り返される。余剰部分６３０は、小データ部分６２０のタイル比率とは異なるタイル比率でドキュメント６１０全体に渡りタイル状に配置されても良い、符号化されたデータを含むことができる。代替として、余剰部分６３０は、タイル状ではないランダムデータを含むことができる。ドキュメント全体に渡り同じ情報がタイル状に配置されるように、ｃｘがｔｘに等しくなり、ｃｙがｔｙに等しくなることは可能である。タイル状の配置は、データ部分がドキュメント全体に渡りメッセージを冗長に符号化することを可能にする。これは、画像品質が異なることがあり、冗長符号化を必要とするので望ましい。更に、ドキュメントの全ての部分が複写されうるわけではないので、ドキュメントの全ての主要な印刷部分に渡り、そのようなマーク付けを有することが望ましい。
【００２９】
３．復号
図７Ａは、現在開示されている配置により復号されうる符号化されたドットパターンの組み合わせを含む画像７１０の例を示す図である。画像７１０は、印刷が実行された用紙をスキャンすることによって得られたビットマップ表現であっても良く、異なる配向及び／又はドット間隔を有するドットパターンを含む。図７Ａにおいて、全てのグリッドは同じドット間隔を有するが、グリッドパラメータは異なっている。この特定の場合、配向が異なるという点においてグリッドパラメータは異なっているが、間隔は同じである。更に、画像７１０は、位置がずれているが、その他の点では構造的に独立しながらも隣接するデータの部分の一部の冗長から生じたと見られるデータの３つの顕在的部分を有することが認められる。
【００３０】
図８は、少なくとも１つのドットパターンを含む入力画像を復号する方法８００を示す図である。ステップ８０５は、入力画像を取り込み、画像上のドットを検出する。ステップ８０５において、ドットパターンを備えるドットが検出され、ページ上のそれらの位置が座標データのリストに記録される。ステップ８０５は、スキャンされた画像の連結成分分析を使用して実行されても良い。そのような分析において、画像の個々のピクセルは、空間的に隣接するピクセルを連結してグループ化するように検査される。グループをその形状に関して分析することにより、マークの存在（つまり、円形ドット又は適切な予想されるサイズのピクセルの概ね均一のブロブ）が検出される。次いで、検出されたマーク（ドット）に対応する座標位置を識別するためにマークの重心が決定される。
【００３１】
次に、ステップ８１０は、画像内の各ドットパターンのグリッド交点を位置指定する。ステップ８１０によって識別された各グリッドは、１つ以上の領域を含むことができる。ステップ８２０は、各グリッド内の領域を識別する。図７Ａの例から、ステップ８２０は、図７Ｂに見られる領域７２０、７３０、及び７４０を識別する。図７Ｂは、水平配向を有するドットパターン７２０、垂直配向及びドットパターン７２０と同様の間隔を有するドットパターン７３０、及び斜め配向を有するドットパターン７４０を示す図である。
【００３２】
最後に、ステップ８３０は、識別された各領域を、その元のデータメッセージに復号し、その時点で方法８００は終了する。
【００３３】
３．１  グリッドナビゲーション
ここで、ステップ８１０を詳細に説明する。図９は、図８のステップ８１０に対応する信頼度を使用して画像のグリッドを位置指定する方法を示す図である。ステップ９１０で処理を開始し、複数の開始点を画像上で識別する。複数の開始点は、グリッドが増大を始める位置を指示する。各開始点は、対応するグリッドナビゲータを有する。開始点は、画像上の任意のランダムな位置に配置される。しかし、好ましい実施態様において、開始点は、画像全体に渡り、一定の間隔ｓｐをおいて配置される。
【００３４】
ｓｐ＝dp_size／２
ここで、dp_sizeは、特定の実施態様が検出可能なドットパターンの最小サイズである。例えば、好ましい実施態様において、方法は１インチ×１インチの最小サイズを備えるドットパターン領域を検出するように構成される。したがって、６００ｄｐｉの画像の場合、開始点は、３００ピクセル（つまり０．５インチ）の間隔をおいて配置される。即ち、dp_sizeは１インチであり、ｓｐは０．５インチである。
【００３５】
図１０Ａ及び図１０Ｂは、画像内の全てのドットパターンのグリッドを位置付ける方法を示す図である。図１０Ａはステップ９１０を示し、ここで１００２、１００４、１００６、１００８、１０１０、１０１２、１０１４、１０１６、１０１８、１０２０、１０２２、及び１０２４は、画像７１０全体に渡り一定間隔で配置された開始点を表す。
【００３６】
図９に戻ると、ステップ９１０において識別された各開始点について、ステップ９２０ではそのグリッド間隔及び配向を検出する。バーコード画像が近傍に区分され、各近傍がその中心に開始点を有するようになる。近傍は、好ましくは正方形の形状であるが、他の形状も可能である。これらの近傍の目的は、各開始点について、グリッド間隔及び配向を検出するために使用されるドットを定義することである。
【００３７】
各開始点について、次いでプロセス２４００は、その開始点に対応するグリッド間隔及び配向を、その近傍のドットを使用して検出する。ここで、図２４に関してプロセス２４００を詳細に説明する。プロセスは、初期のステップ２４０１で開始する。続くステップ２４０３において、グリッド配向を近傍のドットの座標から計算する。このステップは、後に詳細に説明する。グリッド配向を計算すると、続くステップ２４０５は、近傍の全てのドット座標に回転を適用する。回転は、グリッド配向角度だけ回転し、その結果、回転したドット座標がｘ軸及びｙ軸とそろったグリッド軸を有する。回転されたドット座標が与えられ、次のステップ２４０７はグリッド間隔を計算する。続くステップ２４１１は、プロセス２４００を終了する。
【００３８】
ここで、ステップ２４０３を詳細に説明する。図２５を参照すると、ステップ２４０３は、ドットのグリッド配向を検出するステップ２５００からなる。プロセスは、ステップ２５０１で開始する。
【００３９】
続くステップ２５０２は、ドット毎に他のどのドットが最も近接しているかを計算する。これは、近傍の全てのドットに対して行われる。所定のドットに最も近接するドットを見つける方法は当業者には既知であろう。１つの簡単な方法は、相互のドットを順に検討し、所定のドットまでその距離を計算し、計算された距離が最も小さいドットを取ることである。好ましい実施態様では、全近傍が多くの「バケット」に分割される、より迅速な方法を使用する。各ドットは、その位置を範囲に含むバケットに割り当てられる。所定のドットに最も近接するドットを見つけるために、所定のドットを範囲に含むバケットから始めて、その周囲にある各々のバケットにある全てのドットを調べ、所定のドットに最も近接するドットを取る。周囲のバケットの何れにもドットが存在しない場合、検索を半径方向に外向きに、その次に最も近接するバケットのセットへと引き続き行う。この方法は、最も近接するドットとして検討される候補のドットの数を大幅に削減する。
【００４０】
続くステップ２５０３は、各ドットから、ステップ２５０２において見い出されたその最も近接する他のドットへの変位ベクトルを計算する。したがって、全ドットは、それに対して計算された対応する変位ベクトルを有する。
【００４１】
続くステップ２５０４は、ステップ２５０３で計算された変位ベクトル毎に、その変位ベクトルの角度を計算する。ベクトルの角度θは、当業者には良く知られており、以下のように計算される。
【００４２】
θ＝atan2(y,x)
ここで、ｘ及びｙは、ベクトルの水平成分及び垂直成分である。続くステップ２５０５は、以下のように定義される、変数Ａ及びＢの値を計算する。
【００４３】
Ａ＝Σcos(4θi)
Ｂ＝Σsin(4θi)
ここで、θiは、ステップ２５０４で見い出された変位ベクトルの角度である。合計は、全ての変位ベクトルに渡って取られる。
【００４４】
次に、続くステップ２５０６は、式を使用してグリッド配向角度φを計算する。
【００４５】
φ=atan2(B,A)/4
したがって、ステップ２５０６で検出されたグリッド配向は、−４５度から４５度の範囲内にある。続くステップ２５０７は、プロセス２５００を終了する。
【００４６】
ここで、ステップ２４０７を詳細に考察する。ステップ２４０７は、図２６に示すプロセス２６００を実行する。プロセス２６００は、グリッド間隔を計算する。プロセスは、ステップ２６０１で開始する。
【００４７】
続くステップ２６０２は、入力としてステップ２４０５において検出された回転されたドットのリストを取得する。各ドット（ｘ，ｙ）について、同じ横の列でその右にある最も近接するドットが見い出される。これを行うために、以下のヒューリスティックが使用される。
【００４８】
（ｘ，ｙ）ではない全てのドット（ａ，ｂ）が検討され、（ａ，ｂ）が（ｘ，ｙ）の右の９０度セクターの外側である場合、（ａ，ｂ）は拒否される。形式的には、以下の場合、ドット（ａ，ｂ）は拒否される。
【００４９】
ａ−ｘ≦０又は｜ａ−ｘ｜≦｜ｂ−ｙ｜
残されたドットについて、以下の関数を最小化するドットが見い出される。このドットは、（ｘ，ｙ）の右側のドットとみなされ、右近傍ドットのリストに格納される。
【００５０】
ｄ（ａ，ｂ）＝｜ａ−ｘ｜＋２｜ｂ−ｙ｜
続くステップ２６０３は、見い出された右近傍ドット（ａ，ｂ）の各々を取り、（ｘ，ｙ）から差分ベクトル（ｄｘ，ｄｙ）を計算する。即ち、以下である。
【００５１】
（ｄｘ，ｄｙ）＝（ａ，ｂ）−（ｘ，ｙ）
（ｄｘ，ｄｙ）は、差分ベクトルのリストに格納される。結果の視覚化に役立てるため、図２７は差分ベクトルのリストのグラフを示す図である。２７０１はｙ軸、２７０２はｘ軸、そして円（例えば２７０３）は差分ベクトルの終点である。留意すべき１つの特徴は、ノイズ及びグリッドの歪みにより、２７０４のような配置を誤った範囲外の点もあることである。
【００５２】
続くステップ２６０４は、各差分ベクトルのｘ縦座標を取り、ｘ値の度数ヒストグラムを作成する。
【００５３】
図２８は、ヒストグラムを示す図である。２８０１は度数軸、２８０２はｘ縦座標軸であり、２８０３は度数バーである。ｘ縦座標軸の各量子のサイズは、ドット座標の細分性に関連すべきである。本体系において、量子は、グリッド座標軸系の０．５となるように選択される。
【００５４】
続くステップ２６０５は、このヒストグラムを使用してグリッド間隔を計算する。右近傍ドットの多くはグリッドの間隔周辺に群がり、そのため、２８０４に示されるように、グリッド間隔は最も度数の高いｘ縦座標のｘ値を取ることによって見い出されることに留意されたい。
【００５５】
続くステップ２６０６は、プロセス２６００を終了する。
【００５６】
図９に戻ると、ステップ９２０に続いて、ステップ９３０は、信頼度を使用して各開始点からグリッドを増大させる（ここでは「グリッドナビゲーション」と称す）。
【００５７】
図１１は、グリッドナビゲーションの方法であるステップ９３０を詳細に示す図である。最初に、ステップ１１１０で画像をテリトリに分割する。上述のグリッドは通常、複数のテリトリを含む。全てのグリッドナビゲータは、これらのテリトリを要求できる。テリトリが要求された後、テリトリが別のグリッドナビゲータによって使用されることはなくなる。各テリトリは小さく、最大グリッド間隔よりも大きい寸法を有することが理想的である。何れにしても、テリトリは最小グリッド間隔よりも大きい寸法を有する必要がある。好ましい実施態様において、各テリトリは幅及び高さが３２ピクセルである。
【００５８】
ステップ１１３０は、ローカルグリッドフィッティングを使用して各開始点に最も近接する信頼とグリッドの交点を計算する。グリッドフィッティングについては、以下の項で更に詳細に説明する。信頼度は、規定のピクセル位置に最も近接するグリッド交点の計算に対するアルゴリズム信頼の尺度である。推定した各グリッド交点及びその関連する信頼値は、信頼プールに追加される。好ましい実施態様では、信頼confは、以下の式によって測定される。
【００５９】
conf=min(|xOffset|,|yOffset|)
ここで、|xOffset|は、（以下の「ローカルグリッドフィッティング」の項で定義されるように）xOffsetの位相ベクトル（phasor）の長さであり、
|yOffset|は、（また以下の「ローカルグリッドフィッティング」の項で定義されるように）yOffsetの位相ベクトルの長さである。
【００６０】
次に、ステップ１１５０は、信頼プールから、最も高い信頼値を持つグリッド交点Ｘhを選択する。次いで、ステップ１１６０は、（Ｘhのグリッドナビゲータに基づいて）Ｘhが属するグリッドＧを識別し、ＸhをグリッドＧに追加して、信頼プールからＸhを除去する。ステップ１１７０は、（ステップ９２０で計算したグリッド間隔を使用して）Ｘhの４つの直接の近傍のおおよその位置を識別し、ローカルグリッドフィッティングを使用して各近傍の推定されたグリッド交点及びそれらの関連する信頼値を計算する。推定された各グリッド交点及びその関連する信頼値は、信頼プールに追加される。更に、グリッド交点に最も近接するドットが見い出され、グリッド交点からの最近接のドットの変位（ここでは「オフセットベクトル」として参照する）が格納される。グリッド交点に近接するドットがないことも考えられる。ステップ１１８０で、最小閾値を超えて信頼プール内に処理すべき多くのグリッド信頼がある場合、処理はステップ１１５０に進む。それ以外の場合、方法９３０は終了する。この段階で、入力画像のグリッドは識別されている。グリッドに関連するグリッド交点は、開始点からのグリッド交点の増大を通じて、及び信頼値の使用を通じて決定されている。
【００６１】
図１２は、グリッド交点Ｘhを含めるようにグリッドＧを更新する方法であるステップ１１６０の詳細フローチャートである。処理はステップ１２１０において開始し、Ｘhが属するテリトリＴxを識別する。ステップ１２２０において、Ｔxが要求されない場合、処理はステップ１２６０に進む。ステップ１２６０は、テリトリＴxがＧに属することを要求し、方法１１６０は終了する。
【００６２】
ステップ１２２０において、Ｔxが既に別のグリッドＨによって要求されている場合、処理はステップ１２３０に進む。ステップ１２３０は、グリッドＧ及びＨが既に結合されているか否かを検査する。結合されている場合、方法１１６０は終了する。それ以外の場合、処理はステップ１２４０に進み、そこでグリッドＧ及びＨは、同じ間隔及び配向を有するか否かが検査される。同じ間隔及び配向を有する場合、ステップ１２５０は、合流点におけるＧ及びＨの座標系を記録する。これはグリッドＧ及びＨを結合し、異なる座標系を、各グリッド内の領域を位置付けるためにステップ８２０によって使用される単一座標系に同期させる。例えば、グリッドＧの各グリッド交点は、ローカルグリッド座標を有する。例えば、グリッドＨの各グリッド交点は、ローカルグリッド座標を有する。グリッドＧとＨが合流するとき、グリッドＨのグリッド交点は、Ｈの新しいグリッド座標がグリッドＧにローカルであるように、再ラベル付けされる必要がある。グリッドＧ及びＨが異なる間隔又は配向を有する場合、方法１１６０は終了する。
【００６３】
図１０Ｂは、グリッドナビゲーションの方法の出力を示す図である。この方法は、２つのグリッド１０４０及び１０５０を識別する。図７Ｂを図１０Ｂと比較すると、グリッド１０４０は、相互に直角をなして配置される２つの隣接するドットパターン７２０及び７３０で構成される。しかし、図９のステップ９２０において検出されたグリッド配向は、０度から９０度の範囲内にあるので、グリッドナビゲーションは１０４０を単一のグリッドとしてしか識別することができない。
【００６４】
図８のステップ８２０は、グリッド１０４０の２つのドットパターン７２０及び７３０を識別するように動作する。
【００６５】
３．２  ローカルグリッドフィッティング
ここで、ローカルグリッドフィッティングの方法を詳細に説明する。グリッドフィッティングは、ここで説明するようにグリッド交点を見い出すプロセスである。グリッド交点は、ローカル領域を検査し、そのローカル領域内のドットに最も一致するグリッドの変換を見い出すことにより見い出される。次いで、入力点に最も近接するグリッド交点を判別する。
【００６６】
グリッドフィッティングにおいて、初期化のステップは、第１のグリッド交点が必要とされる前に実行される。この初期化のステップは、幾つかの数を事前計算する。グリッド交点を推定するステップは、事前計算された情報を使用する。
【００６７】
事前計算された情報は、グリッド間隔及びグリッドの配向に依存する。したがって、各グリッドナビゲータは、各自の事前計算された情報を有し、各自の初期化を実行する必要がある。
【００６８】
ここで、初期化ステップ１３００を詳細に説明する。図１３に示す初期化プロセス１３００は、ステップ１３２０で開始する。ステップ１３２０で、プロセス１３００は、バーコード画像の全てのドット（ｘk，ｙk）についてｘＮｅｗk及びｙＮｅｗkを計算する。グリッド間隔が２πになり、グリッド配向を明らかにするためには、以下の関係を満たす。
【００６９】
【数１】
2008159055.tif 000003
【００７０】
ここで、θは、ステップ１１１０において検出されたグリッド配向である。
【００７１】
ステップ１３３０において、プロセス１３００は、バーコード画像の全てのドットについてｘ及びｙフェーザ（位相ベクトル）を計算する。
【００７２】
ｘフェーザ＝ｃｏｓ（ｘＮｅｗk）＋ｊｓｉｎ（ｘＮｅｗk）
ｙフェーザ＝ｃｏｓ（ｙＮｅｗk）＋ｊｓｉｎ（ｙＮｅｗk）
ここで、ｊは、−１の平方根である。
【００７３】
ステップ１３４０で、バーコード画像はフェーザビンに分割される。好ましい実施態様では、フェーザビンは３２×３２ピクセルのサイズで、画像全体に渡り規則正しくタイル状になる。例えば、図１４は、フェーザビン（例えば１４２０）に分割されるバーコード画像１４１０を示す図である。フェーザビンは、垂直方向（ｙ）サイズ寸法１４４０及び水平方向（ｘ）サイズ寸法１４３０を有する。ステップ１３５０において、各ビン１４２０に対し、プロセス１３００は、ビン１４２０内のドットに対応するｘフェーザの合計を計算する。同様に、各ビン１４２０に対し、プロセスは、ｙフェーザの合計を計算する。これで、情報を事前計算する初期化ステップ１３００が終了する。
【００７４】
図１５は、事前計算された情報を使用してグリッド交点を計算するプロセス１５００を示す図である。最も近接するグリッド交点が点（ｘc，ｙc）において求められると仮定する。方法１５００は、入口ステップ１５１０を有し、実質的にステップ１５２０で開始し、ここで点（ｘc，ｙc）周辺のウィンドウが決定される。ウィンドウは、好ましくは４×４フェーザビンのサイズを有するが、他のウィンドウサイズが使用されても良い。ウィンドウは、中心に最も近接する点（ｘc，ｙc）を有する４×４フェーザビンのセットとなるよう決定される。第２に、ステップ１５３０で、xOffset及びyOffsetの値が決定される。xOffsetは、ウィンドウ内の４×４フェーザビンのｘフェーザ和の合計である。同様に、yOffsetは、ウィンドウ内の４×４フェーザビンのｙフェーザ和の合計である。
【００７５】
最後に、ステップ１５４０は、最も近接するグリッド交点の位置を推定する。現在のピクセル位置を（ｘc，ｙc）で表す。推定されたグリッド交点（xGrid，yGrid）は、以下の式により与えられる。
【００７６】
【数２】
2008159055.tif 000004
【００７７】
ここで、θは、ステップ１１１０において検出されたグリッド配向である。
【００７８】
ステップ１５４０の後、方法１５００は終了する。
【００７９】
３．３  領域検出
ここで、グリッドの複数の領域を識別する方法を、図１６を参照してステップ８２０を詳細に説明する。領域タイルを結合して領域を形成する方法８２０は、ステップ１６１０で開始し、ここで入力グリッドを領域タイルに分割する。図１７は、領域タイルに分割された入力グリッドを示す。各領域タイル（例えば、領域タイル１７０５、１７３０）は、符号化されたタイルのサイズである、ｔｘ×ｔｙの寸法を有する。各領域タイルは、多くとも４つの境界を有する。例えば、領域タイル１７０５は１７１０、１７１５、１７２０、及び１７２５の領域境界を有する。ステップ１６２０で、各領域境界の結合コストを計算する。
【００８０】
結合コストｍｃは、領域境界の２つの領域が結合された後の全体エラー測定の改良の尺度である。好ましくは、
ｍｃpq＝ｅｒｒｏｒpq−ｅｒｒｏｒp−ｅｒｒｏｒq
ここで、
ｍｃpqは領域ｐ及び領域ｑを結合するための結合コストであり、
ｅｒｒｏｒpqは領域ｐ及び領域ｑの組み合わせのエラーであり、
ｅｒｒｏｒpは領域ｐのエラーであり、
ｅｒｒｏｒqは領域ｑのエラーである。
【００８１】
エラーメトリックは、領域内の領域タイルが相互にどのように異なっているかに基づいて計算される。領域タイル間の類似は、各タイル内の繰り返し領域を識別することにより計算されることが理想的である。上述のように、各領域タイルは、符号化されたタイルと同じ寸法を有する。したがって、ｃｙ×ｃｘの寸法を備える小データ部分６２０（本明細書において「注目領域」と称す）は、各領域タイルのどこかに位置している。注目領域の位置は、集約及びボックスカーフィルタを使用して決定される。
【００８２】
エラー計算は、領域の領域タイルを共に集約することを伴う。つまり、領域タイルは、各領域タイル内の対応するドットを組み合わせることにより、１つの領域タイルに結合される。タイルのサイズはｔｘ×ｔｙであるので、ｔｘにｔｙを乗じた数のタイル位置がある。タイル集約中、４つの集約された値は集約された領域のタイル位置毎に計算される。第１の値agg_countは、所定のタイル位置におけるドットの数である。通常agg_countは、領域内の領域タイルの数と等しい。しかし、所定のグリッド交点において（ステップ１１７０により識別されたように）、対応するドットがない場合、agg_countは領域内の領域タイルの数よりも少なくなる。agg_xは、所定のタイル位置におけるオフセットベクトルのx-offset値の合計である。agg_yは、所定のタイル位置におけるオフセットベクトルのy-offset値の合計である。最後に、agg_sqlenは、所定のタイル位置におけるオフセットベクトルの長さの２乗の合計である。
【００８３】
ボックスカーフィルタが注目領域の位置を計算するために使用される。スコアは、以下の式に従って、タイル位置毎に計算される。
【００８４】
【数３】
2008159055.tif 000005
【００８５】
agg_sqlenが０である場合、そのタイル位置におけるスコアは０である。ボックスカーフィルタは、集約されたタイルの全てのｃｘ×ｃｙ領域のスコアを合計する。「注目領域」は、最大のスコア合計を備えるｃｘ×ｃｙ領域である。
【００８６】
各領域結合の後、スコア計算においてより多くのドットにより更に正確な位置が取得されるので、注目領域の位置を再計算することが必要になることがある。これには、新たに結合された領域の全てのタイル位置に対してagg_x及びagg_y値を更新することを伴う。
【００８７】
注目領域の位置を見い出すと、エラーメトリックは注目領域内のドットを使用して計算される。集約された領域内の各タイル位置について、エラーは以下のようになる。
【００８８】
【数４】
2008159055.tif 000006
【００８９】
したがって、集約領域タイル全体のエラーメトリックは（例えば、ｅｒｒｏｒp）、各タイル位置におけるエラー値の合計である。最初に、ステップ１６１０で、全ての領域はゼロのエラー値を有する。これは、方法８２０を開始したときに、各領域には１つの集約されたタイルしかないからである。
【００９０】
次に、ステップ１６２４は、２つの領域Ｒｘ及びＲｙの間に位置し、最低の結合コストｍｃxyを持つ、領域境界Ｂｘｙを識別する。ステップ１６２８は、ｍｃxyが閾値MC_THRESHOLDを下回る値を有するか否かを検査する。この最大閾値は、結合される全ての領域が、全体エラー測定を悪化させるのではなく、全体エラー測定を改善することを保証する。ｍｃxyが閾値を下回る場合、処理はステップ１６３０に進む。それ以外の場合、方法８２０は終了する。MC_THRESHOLDの値は、好ましくはゼロである。
【００９１】
ステップ１６３０は、Ｂxyの２つの領域（つまり、領域Ｒx及びＲy）を単一の領域Ｒxyに結合する。図１８は、結合された領域１８１０を備える入力グリッド１０４０の例を示す図である。図１７を参照すると、ステップ１６３０は、最低の結合コストを持つ境界Ｂxyとして、境界１７１５を識別した。したがって、領域Ｒx１７０５及びＲy１７３０は結合される。
【００９２】
次に、図１６に戻ると、ステップ１６４０は、結合された領域Ｒxyの全ての境界の新たな結合コストを計算する。再び図１８を参照すると、ステップ１６４０は、境界１７１０、１８２０、１８３０、１８４０、１７２０、及び１７２５の新たな結合コストを計算する。
【００９３】
ステップ１６５０において、処理すべき更に多くの領域境界がある場合、処理は、次の最低結合コスト境界を結合するためにステップ１６３０に進む。それ以外の場合、方法８２０は終了する。
【００９４】
図１９は、グリッドの複数の領域を検出する、図１６に示す方法８２０の出力を示す図である。グリッド１０４０は、領域１９１０及び領域１９２０の２つのドットパターンの領域で構成され、これらはデータが領域１９１０及び１９２０の同じ配向を使用して読み取られるときに、異なるデータを有すると認められる。
【００９５】
３．４  復号領域
識別された各領域は、各領域の領域タイルを集約し、注目領域の集約されたドット（ステップ１６２０及び１６４０で識別される）を使用して元のメッセージを復号することにより復号される。
【００９６】
集約された各オフセットベクトルをその対応するデジタルデータ値に変換するために、各グリッド正方形は、図２０に示すように、８つの等しいサイズのセクターに分割される。グリッド中心２０９５を持つグリッド２０９０は、８つのセクターを定義するが、ここで各セクターはデジタルデータ値を表す。集約されたオフセットベクトル２０１４は、集約されたドット２０１２を表すが、これはセクター２０１０の範囲内に入る。再び図４を参照すると、セクター２０１０は、値４０３を有するドット４０１に対応し、これは５のデジタルデータ（つまり、２進数値１０１）を有する。同様に、セクター２０２０、２０３０、２０４０、２０５０、２０６０、２０７０、又は２０８０の範囲内に入る集約されたオフセットベクトルは、それぞれ値７、６、２、３、１、０、又は４を有するドットに対応する。
【００９７】
集約された各オフセットベクトルがそのデジタルデータ値に変換されると、値の２進数表現は復号されたメッセージを形成するために（図５に示すように）付加される。
【００９８】
領域タイルの配向が、９０度の倍数だけ誤っている可能性がある。これは、グリッドが９０度回転された場合でも、依然としてグリッドのように見えるからである。したがって、グリッド配向を決定するステップ２５０６は、角度を−４５度から４５度の範囲の角度だけ戻す。復号されたメッセージが意味をなさないような場合には、配向が誤って検出された可能性もある（チェックサムの使用により、又はエラー修正ステップの使用により、誤ったメッセージを検出する可能性もある。その他の方法も可能である）。
【００９９】
配向が誤っている場合、デコーダは領域タイルを回転させ、オフセットベクトルをデジタルデータ値に再変換し、（図５に示すように）新しい順序で値を付加することができる。これは、正しい復号されたメッセージが検出されるまで、４つの全ての配向について、行われる。
【０１００】
４．拡張
４．１  タイル状ではないドットパターン
本実施形態は、タイル状のドットパターン領域を識別することに限定されない。また、タイル状でないドットパターン領域を識別することも可能である。タイル状でないドットパターンを識別するには、領域ファインダのエラーメトリックは同じパターンで配置されたドットを探すのではなく、ドットパターンの特徴を基にする。
【０１０１】
例えば、エラーメトリックは、輝度、サイズ、又は形状（或いは、パターン特徴の組み合わせ）に基づいていても良い。つまり、領域の結合コスト及びエラーメトリックを計算するために（ステップ１６２０及び１６４０において）領域タイルを集約するのではなく、代替の実施態様では、輝度、サイズ、又は形状（又は、それらの組み合わせ）の統計を集約することができる。これらの集約された統計は、領域タイル間の類似性を表し、領域のエラーメトリックを定義する。
【０１０２】
４．２  最適化グリッドナビゲーション
グリッドナビゲーション中は、ドットパターンの全てのグリッド交点を位置付けるためにグリッド転換を使用する必要がないこともある。その代わり、ドットパターンの４つのグリッド交点の１つを位置付けるためにグリッド転換を使用することで十分である。
【０１０３】
図２１Ａ、図２１Ｂ、及び図２１Ｃは、グリッドナビゲーション中に、グリッド転換計算の数を減少させた方法を示す図である。図２１Ａは、ステップ１１６０の後のグリッドナビゲータの例を示す。様々なドット２１０５、２１１０、２１１５は、ステップ８０５によって識別されており、ドット２１０５はグリッド交点２１２０に隣接している。ステップ１１７０の代わりに、最適化グリッドナビゲーションの方法が、現在のグリッド交点から離れた全ての近傍の２つのグリッド間隔の信頼を計算する。図２１Ａにおいて、点２１３０は、近傍グリッド交点の推定位置を表す。点２１３０とグリッド交点２１２０間の距離は、矢印２１２５で表されるが、これはグリッド間隔の値の２倍である。次に、図２１Ｂは、グリッド転換が点２１３０で実行された後の、ドット２１１５のグリッド交点を示す。次いで、グリッドナビゲーションの処理は、図１１のステップ１１８０に進む。
【０１０４】
最後に、処理すべきグリッド信頼がそれ以上ない場合、結果として生じたグリッドは、欠落しているグリッド交点で補間される。図２１Ｃは、ドット２１１０のグリッド交点２１４５の補間された位置を示す。
【０１０５】
４．３  代替グリッドナビゲーション
グリッドナビゲーションの方法の代替手法は、信頼を計算する場合に各グリッド交点のグリッドを常時更新することである。これには、最も高い信頼グリッド交点を処理するときに、全ての近傍のテリトリを常に要求するという効果がある。
【０１０６】
つまり、図１１において、ステップ１１６０は、この代替方法から除去されうる。その代わり、新たなステップが作成される。この新たなステップは、グリッド交点ＸnのグリッドＮ（Ｘnが属する）を、その信頼が計算されると更新する。更にもう１つの代替実施態様において、この追加のステップは、ステップ１１３０の後（またステップ１１５０の前）に実行される。また、追加のステップは、ステップ１１７０の後（またステップ１１８０の前）に実行される。
【０１０７】
４．４  領域検出における部分タイルの無視
グリッドで複数領域を検出するための方法８２０において、ステップ１６１０はグリッド内の領域を定義する。入力グリッドは、任意のサイズであっても良いので、ステップ１６１０中には部分タイル１７４０がある場合もある。代替の手法において、部分タイルは、領域ファインダの処理から除外されうる。更に、低いドット密度を備えるタイルは、ドットの誤った肯定的な検出を生じたその領域でノイズを多発する背景となることもあるので、除外されうる。
【０１０８】
４．５  領域検出における「注目領域」の識別
ステップ１６４０において結合された領域の領域境界毎に新たな結合コストを計算するとき、各領域境界に対して注目領域の位置を計算しなくても良い。例えば、広範な領域と非常に小さい領域との間の領域境界に対して注目領域の位置は再計算されることはない。その代わり、広範な領域の注目領域の既存の位置が結合コストを決定する際に使用される。
【０１０９】
更に、注目領域を識別する場合、集約された領域タイルのｃｘ×ｃｙドット領域毎に（つまり、集約された領域タイルの２倍サブサンプル）スコアを計算することが可能である。これは、まだ注目領域の正確な位置を取得する必要がない可能性があるためである。しかし、正確な位置が必要な場合は、サブサンプリングの出力は注目領域の位置の更に正確なスコア計算を行うために使用される。
【０１１０】
図２２は、この代替実施態様のサブサンプリング中に使用されるドットパターンのドットを示す図である。図２２に示すドットパターンは、図１に示すドットパターンと同じである。ドットパターンの注目領域を識別する場合、ドットの２倍サブサンプリングを使用する。つまり、黒いドット（例えば、２２１０）がボックスカー計算に使用される。このことには、ステップ１６４０中に実行される計算の数を減少させる効果がある。
【０１１１】
４．６  最適化ローカルグリッドフィッティング
代替の実施形態では、フェーザ合計が要求に応じて計算される。一般に、各グリッドナビゲータはページ全体のフェーザ情報を必要としない。特に、各グリッドナビゲータは、それが表すページの一部についてフェーザ情報を必要とするだけである。
【０１１２】
したがって、グリッドフィッティングの初期化の方法１３００は、バーコード画像を区分する、ステップ１３４０のような単一のステップに変更される。フェーザ合計を計算するステップであるステップ１３２０、１３３０、及び１３５０は、初期化中に実行されない。
【０１１３】
フェーザ合計は、ステップ１５３０において必要になる。ビンのフェーザ合計がまだ計算されていない場合は、ステップ１３２０、１３３０、及び１３５０がそのビンに対して実行される。結果として得られたフェーザ合計は、使用することが必要になるまで、例えばメモリ２３０６／２３０９に格納することにより、記憶される。将来そのビンのフェーザ合計が必要となった場合、その値は再計算されることはない。
【産業上の利用可能性】
【０１１４】
配列が説明されている本説明は、バーコード表現を有するドキュメントのセキュリティ保護された複写が必要とされるコンピュータ及びデータ処理業界に適用可能である。
【図面の簡単な説明】
【０１１５】
【図１】位相変調されて、もはや全体が規則的グリッド上に配置されてはいないドットの配列を示す図である。
【図２】規則的グリッド上に配置されたドットの規則的配列を示す図である。
【図３】ドットの変調を詳細に示す図である。
【図４】ドットの変調を更に詳細に示す図である。
【図５】変調されたグリッドのディジットの順序付けを示す図である。
【図６】ドットパターンのデータを符号化するためのタイリング配置を示す図である。
【図７Ａ】符号化されたデータの３つの領域を備える画像の例を示す図である。
【図７Ｂ】現在開示されている配置により検出される画像における符号化されたデータの領域の例を示す図である。
【図８】画像において符号化されたデータの複数の領域を検出するステップを示す流れ図である。
【図９】画像において符号化されたデータの複数のグリッドを位置付けるステップを示す流れ図である。
【図１０Ａ】画像例で開始点を定義するステップを示す図である。
【図１０Ｂ】画像例で識別されたグリッドを示す図である。
【図１１】信頼を使用して初期開始点からグリッドを増大させるステップを示す流れ図である。
【図１２】既存のグリッドにグリッド中心を追加するステップを示す流れ図である。
【図１３】グリッド転換のための初期化ステップを示す流れ図である。
【図１４】フェーザビンに分割されたバーコード画像を示す図である。
【図１５】グリッド転換のためのステップを示す流れ図である。
【図１６】グリッドにおいて複数の領域を検出するためのステップを示す流れ図である。
【図１７】領域に分割されたグリッドの例を示す図である。
【図１８】グリッドにおいて２つの領域を結合する例を示す図である。
【図１９】グリッドにおいて検出された領域の例を示す図である。
【図２０】集約されたオフセットベクトルのそのデジタルデータ値への変換を示す図である。
【図２１Ａ】グリッドナビゲーション及び近傍位置を推定する方法の改良を示す図である。
【図２１Ｂ】グリッドナビゲーション及び近傍位置を識別するためにグリッド転換を使用する方法の改良を示す図である。
【図２１Ｃ】グリッドナビゲーション及びグリッド交点位置を補間する方法の改良を示す図である。
【図２２】領域内のドットをサブサンプリングすることによる本発明の拡張を示す図である。
【図２３】望ましい配置が実施されうるコンピュータシステムを表現する概念ブロック図である。
【図２４】ドットのグリッドにおいてグリッドの配向、スケール、及び転換を検出するプロセスを示す図である。
【図２５】グリッド配向を計算するプロセスを示す図である。
【図２６】グリッドの間隔を検出するプロセスを示す図である。
【図２７】右近傍差分ベクトルのリストを示すグラフである。
【図２８】ｘ値の度数ヒストグラムを示す図である。
【図１】
2008159055.tif 000007
【図２】
2008159055.tif 000008
【図８】
2008159055.tif 000009
【図９】
2008159055.tif 000010
【図１０Ａ】
2008159055.tif 000011
【図１１】
2008159055.tif 000012
【図１２】
2008159055.tif 000013
【図１３】
2008159055.tif 000014
【図１４】
2008159055.tif 000015
【図１５】
2008159055.tif 000016
【図１６】
2008159055.tif 000017
【図１７】
2008159055.tif 000018
【図１８】
2008159055.tif 000019
【図１９】
2008159055.tif 000020
【図２１Ａ】
2008159055.tif 000021
【図２１Ｂ】
2008159055.tif 000022
【図２１Ｃ】
2008159055.tif 000023
【図２３】
2008159055.tif 000024
【図２４】
2008159055.tif 000025
【図２５】
2008159055.tif 000026
【図２６】
2008159055.tif 000027
【図２７】
2008159055.tif 000028
【図２８】
2008159055.tif 000029
【図３】
2008159055.tif 000030
【図４】
2008159055.tif 000031
【図５】
2008159055.tif 000032
【図６】
2008159055.tif 000033
【図７Ａ】
2008159055.tif 000034
【図７Ｂ】
2008159055.tif 000035
【図１０Ｂ】
2008159055.tif 000036
【図２０】
2008159055.tif 000037
【図２２】
2008159055.tif 000038