一群の検出
【課題】画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別する方法を提供する。
【解決手段】配置マーク（１４０１〜１４０６）は、コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マーク（１４０７〜１４１０）はデータを符号化するために基準グリッドに関して変調される。方法は、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択し、選択したマークに関する回転の中心を判定する。選択した各マークを回転の中心に関して所定の角度だけ回転することにより選択したマークに対する回転位置を判定し、回転位置から所定の閾値未満の位置を有するマークの場所がマークの構成から特定され、選択したマーク及び場所を特定したマークは配置マークの一群として識別される。
【解決手段】配置マーク（１４０１〜１４０６）は、コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マーク（１４０７〜１４１０）はデータを符号化するために基準グリッドに関して変調される。方法は、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択し、選択したマークに関する回転の中心を判定する。選択した各マークを回転の中心に関して所定の角度だけ回転することにより選択したマークに対する回転位置を判定し、回転位置から所定の閾値未満の位置を有するマークの場所がマークの構成から特定され、選択したマーク及び場所を特定したマークは配置マークの一群として識別される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に印刷文書におけるマークを追跡することに関し、特に、グリッド状のパターンを形成する配置マークを追跡することに関する。更に本発明は、一般に誤り訂正符号を利用して透かしを検出することを含む透かし又は他のステガノグラフィパターンの向きを判定することに関する。また本発明は、一般に印刷文書上にグリッドの形式で存在している基本的な配置マークの一群を検出することに関する。
【背景技術】
【０００２】
印刷ページ上のコンピュータ読み取り可能なマークは普及しており、普通のバーコード等の種々のものが非常に広く使用されている。普通のバーコードが普及しているが、益々多くの別のコンピュータ読み取り可能なマークが市場に出ている。これらの新しい種々のマークの多くは、普通のバーコードより大きなデータ搬送能力を提供し、普通のバーコードに格納可能なデータが３０〜６０ビットであるという制限を伴う可能な応用例より更に広範の応用例を可能にする。他の種々のマークは、可視性を低減させて示すことで普通のバーコードを向上させ、人間が読み取り可能なコンテンツを含むように更に多くのページの部分が解放されているという利点を有する。低い可視性のマークの追加の利点は、情報がページに隠蔽されるため、ステガノグラフィ及び透かし等の応用例が可能になることである。
【０００３】
コンピュータ読み取り可能なマークが更に広く使用され、コンピュータ読み取り可能なマークに対する新しい応用例が見つけられるのと共に、ページの多くの領域を消費せずに大きいデータ容量を提供するマークの必要性が高まっている。そのようなマークにより、人間が読み取り可能なコンテンツを含むようにページの殆どが解放され、これは多くの応用例にとって望ましい。
【０００４】
画像から透かし又は他のステガノグラフを再生する場合、当然マークは見えず、無作為の向きで走査又はデジタル化されることが多いため、マークを読み取る正確な向きを判定するという課題が発生する。
【０００５】
ステガノグラフの正確な向きを判定する方法が多く開示されている。例えば、複数の１次元向き信号を画像に取り込み且つ後で検出するという方法である。豪州特許出願第２００２９５１８１５号（Canon Kabushiki Kaisha）において説明するように、それらの信号が人間の目に感知不能であるところまで弱く埋め込まれる場合でも、適切に配向された画像の投影は１次元キャリアの存在を示す。
【０００６】
豪州特許出願第２００５２０９７０９号（Canon Kabushiki Kaisha）において、向きの判定を助長するために所定の場所の固定ヘッダメッセージを使用するステガノグラフの別の形式が説明される。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
向き信号をステガノグラフに追加することは、可視性を増加する代わりに向きの迅速な判定を可能にする周知の技術である。可視性が最小限にされる必要があるステガノグラフを生成する場合、そのような向き信号の存在は望ましくない。
【０００８】
画像データの無許可のコピーを防止する方法がいくつか存在する。これらの方法は、通常、コピーされる画像において固定パターン又は印の場所を特定することに基づく。或いは、仮想グリッドに関してデータを符号化させる方法がいくつかある。固定の距離のグリッドを有する必要性をなくし、基準グリッドを検出し且つその基準グリッドをデータ搬送ドットと分離する更に高速な手法を提供する必要がある。更に、データ搬送マークを無視し且つグリッド状の基準パターンを形成するマークのみを選択的に評価することにより、基準グリッドを検出する更に高速な手法を提供する必要がある。
【課題を解決するための手段】
【０００９】
本明細書において、画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別する方法が開示される。一実施形態において、コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合である。
【００１０】
本開示の第１の態様によると、画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法が提供される。配置マークはコンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。方法は、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、選択したマークの各位置に関する回転の中心を判定するステップと、選択したマークの各々を回転の中心に関して所定の角度だけ回転することにより選択したマークに対する回転位置を判定するステップと、各回転位置に対して、回転位置から所定の閾値未満の位置を有するマークの場所をコンピュータ読み取り可能なマークの構成から特定するステップと、選択されたマーク及び場所を特定したマークを配置マークの一群として識別するステップとを含む。その後、方法は、データ搬送マークを復号化する際に使用するために識別された一群を格納する。
【００１１】
本開示の第２の態様によると、画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法であって、前記コンピュータ読み取り可能なマークの構成から選択される少なくとも２つのマークの少なくとも１つの組み合わせに対して、（ａ）前記組み合わせの前記選択されたマークの各位置に関する回転の中心を判定するステップと、（ｂ）前記選択されたマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記組み合わせの前記選択されたマークに対する回転位置を判定するステップと、（ｃ）各回転位置に対して、前記回転位置に最近接するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、（ｄ）前記回転位置のうち、少なくとも所定の割合の回転位置に対して前記回転位置に最近接する前記マークが前記回転位置から所定の閾値未満の位置にある場合、前記組み合わせの前記選択されたマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを含む。方法は、データ搬送マークを復号化する際に使用するために識別された一群を格納する。
【００１２】
本開示の第３の態様によると、走査済画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するように構成されたコピー機が提供される。配置マークはコンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。コピー機は、走査済画像を取得するスキャナと、コンピュータプログラムを格納する記憶装置と、コンピュータプログラムを実行するプロセッサとを含む。前記コンピュータプログラムは、前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、前記選択したマークの各位置に関する回転の中心を判定するステップと、前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを前記プロセッサに実行させる。
【００１３】
本開示の第４の態様によると、画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群が識別され、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法を実行するようにプロセッサに指示するためのコンピュータプログラムが提供される。方法は、前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、前記選択したマークの各位置に関する回転の中心を判定するステップと、前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有する。
【００１４】
本開示の別の態様によると、上述の方法のうち任意の１つを実現する装置が提供される。
【００１５】
本開示の別の態様によると、上述の方法のうち任意の１つを実現するコンピュータプログラムを記録したコンピュータ読み取り可能な媒体を含むコンピュータプログラム製品が提供される。
【００１６】
本開示の他の態様が更に開示される。
【００１７】
次に、図面を参照して、本発明の１つ以上の実施形態を説明する。
【発明を実施するための最良の形態】
【００１８】
任意の１つ以上の添付の図面において同一の図中符号を有するステップ及び／又は特徴を参照する場合、特に指示のない限り、それらのステップ及び／又は特徴は説明の目的で同一の機能又は動作を有する。
【００１９】
［概要］
本明細書において、画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するためのコンピュータにより実現される方法が開示される。例えば、画像は、スキャナ又はコピー機により取得される走査済画像又は印刷画像であっても良いが、それらに限定されない。一実施形態において、コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合である。例えばコンピュータ読み取り可能なマークは、ドット、円、正方形、三角形又は任意の所望の形状を形成するドット群を含んでも良い。コンピュータ読み取り可能なマークの構成は、配置マーク及びデータ搬送マークを含む。ここで、配置マークは、コンピュータ読み取り可能なマークの構成内で仮想基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。
【００２０】
方法は、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択し、選択したマークの各位置に関する回転の中心を判定する。選択した各マークを回転の中心に関して所定の角度だけ回転することにより、回転位置は選択したマークに対して判定される。方法は、各回転位置に対して、回転位置から所定の閾値未満の位置を有するマークの場所をコンピュータ読み取り可能なマークの構成から特定する。方法は、選択したマーク及び場所を特定したマークを配置マークの一群として識別し、データ搬送マークを復号化する際に使用するために識別された一群を格納する。一実施形態において、少なくとも２つのマークの更なる選択は、一群を識別するために行われる。
【００２１】
一実施形態において、方法は、識別された一群の間隔及び向きを判定することを含み、更に識別された一群の間隔及び向きに基づいて予想されるマークの場所の集合を判定することを含む。予想されるマークの場所のうち少なくとも所定の割合の場所がコンピュータ読み取り可能なマークの構成におけるマークの場所と一致すると、配置マークの識別一群が検証される。
【００２２】
別の実施形態において、配置マークによって規定される基準グリッドは矩形グリッドであり、２つのマークはコンピュータ読み取り可能なマークの構成から選択され、回転の中心を判定することは２つの選択したマークの間に位置付けられる点を識別することを含む。更なる実施形態において、基準グリッドは三角形グリッドであり、回転の中心を判定することは選択したマークのうちの１つを回転の中心として割り当てることを含む。更に、別の実施形態において、基準グリッドは六角形グリッド又は菱形グリッドである。
【００２３】
別の実施形態において、方法は、識別された一群を拡張して、判定した間隔及び向きに基づいてコンピュータ読み取り可能なマークの構成から追加のマークを組み込む。更に、別の実施形態において、方法は、識別された一群を利用して基準グリッドを識別し、識別した基準グリッドに基づいてコンピュータ読み取り可能なマークの構成においてデータ搬送マークを識別する。最後に方法は、識別したデータ搬送マークを復調し、データ搬送マークにより符号化されたデータを導出する。
【００２４】
本明細書において、画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するためのコンピュータにより実現される方法が更に開示される。例えば、画像は、スキャナ又はコピー機により取得される走査済画像又は印刷画像であっても良いが、それらに限定されない。一実施形態において、コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合である。例えばコンピュータ読み取り可能なマークは、ドット、円、正方形、三角形又は任意の所望の形状を形成するドット群を含んでも良い。コンピュータ読み取り可能なマークの構成は、位置決めマーク及びデータ搬送マークを含む。ここで、位置決めマークはコンピュータ読み取り可能なマークの構成内で仮想基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。
【００２５】
コンピュータ読み取り可能なマークの構成から選択される少なくとも２つのマークの少なくとも１つの組み合わせに対して、方法は、その組み合わせの選択されたマークの各位置に関する回転の中心を判定し、選択した各マークを回転の中心に関して所定の角度だけ回転することにより、その組合せの選択したマークに対する回転位置を判定する。方法は、各回転位置に対して、回転位置に最近接するマークの場所をコンピュータ読み取り可能なマークの構成から特定し、回転位置のうち少なくとも所定の割合の回転位置に対して、回転位置に最近接するマークが回転位置から所定の閾値未満の位置にある場合、組み合わせの選択したマーク及び場所を特定したマークを配置マークの一群として識別する。所定の閾値は、特定の応用例に依存する。方法は、データ搬送マークを復号化する際に使用するために識別された一群を格納する。
【００２６】
本明細書において、走査済画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するように構成されたコピー機が更に開示される。コンピュータ読み取り可能なマークの構成は、配置マーク及びデータ搬送マークを含む。ここで、配置マークはコンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。コピー機は、走査済画像を取得するスキャナと、コンピュータプログラムを格納する記憶装置と、プログラムを実行するプロセッサとを含む。コンピュータプログラムは、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するコードと、選択したマークの各位置に関する回転の中心を判定するコードと、選択した各マークを回転の中心に関して所定の角度だけ回転することにより選択したマークに対する回転位置を判定するコードと、各回転位置に対して、回転位置から所定の閾値未満の位置を有するマークの場所をコンピュータ読み取り可能なマークの構成から特定するコードと、選択したマーク及び場所を特定したマークを配置マークの一群として識別するコードとを含む。
【００２７】
本明細書において、上述の方法のうち、任意の１つを実行するようにプロセッサに指示するためのコンピュータプログラムを記録したコンピュータ読み取り可能な媒体を含むコンピュータプログラム製品が更に開示される。
【００２８】
［透かしの向きの判定］
本明細書においてＬＶＢＣと略される低可視バーコード（Low Visibility Bar Code）は、通常のプリンタ（レーザプリンタ又はインクジェットプリンタ等）を使用してページ上に印刷され且つ通常のデスクトップスキャナを使用してコンピュータにより読み取り可能な種々のコンピュータ読み取り可能なマークである。ＬＶＢＣマークは、１ページに数十、数百又は数千バイトものバイナリデータを含むために使用され、人間が読み取り可能なコンテンツを含むようにそのページの殆どを解放する。ＬＶＢＣマークは大量の冗長を含むように構成され、そのように構成された場合、ＬＶＢＣマークは折り曲げ、しわ、着色、破れ及び汚れに対して非常にロバストになる。
【００２９】
図１は、ＬＶＢＣを印刷するのに適する機器を示す概略ブロック図である。例えばMicrosoft Windows（登録商標）オペレーティングシステムを実行するＩＢＭ互換のＰＣであるパーソナルコンピュータ１０１は、通信ケーブル１０３を介してレーザプリンタ又はインクジェットプリンタ等のプリンタ１０２に結合される。プリンタ１０２は、１枚の紙１０７又は他の印刷媒体に印刷して、ハードコピー文書を提供できる。印刷されたデータはＬＶＢＣを含んでも良い。別の実施形態において、通信ケーブル１０３は、無線伝送リンクを使用して実現される。
【００３０】
図２は、ＬＶＢＣをコンピュータにより読み取るのに適する機器を示す概略ブロック図である。図２はCanon 9900Fデスクトップスキャナ等のスキャナ１０４を示し、スキャナ１０４は通信ケーブル１０５を介してパーソナルコンピュータ１０６に結合される。パーソナルコンピュータ１０６及び１０１は同一のコンピュータでも良く、或いは個別に動作可能であるか又は例えばコンピュータネットワークを介して接続される別個のコンピュータでも良い。機器は、例えばスキャナ１０４によりコンピュータ１０６に走査されたハードコピー文書上に存在するＬＶＢＣをコンピュータにより読み取るのに適する。別の実施形態において、通信ケーブル１０５は、無線伝送リンクを使用して実現される。
【００３１】
後述する符号化及び復号化の方法は、図１１に示すような汎用のコンピュータシステム１１００を使用して実現されるのが好ましい。ここで、図３〜図１０の処理は、コンピュータシステム１１００内で実行するアプリケーションプログラム等のソフトウェアとして実現されても良い。特に、符号化及び復号化のステップは、コンピュータにより実行されるソフトウェアの命令により行われる。命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されても良い。ソフトウェアは２つの別個の部分に分割されても良く、第１の部分は符号化及び／又は復号化方法を実行し、第２の部分は第１の部分とユーザとの間のユーザインタフェースを管理する。例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読み取り可能な媒体に格納されても良い。ソフトウェアは、コンピュータ読み取り可能な媒体からコンピュータにロードされ、コンピュータにより実行される。そのようなソフトウェア又はコンピュータプログラムを記録したコンピュータ読み取り可能な媒体はコンピュータプログラム製品である。コンピュータプログラム製品をコンピュータにおいて使用することにより、データを文書に取り込むための有利な装置を達成するのが好ましい。
【００３２】
コンピュータシステム１１００は、コンピュータモジュール１１０１と、キーボード１１０２、マウス１１０３及びスキャナ１１１８等の入力装置と、プリンタ１１１５、表示装置１１１４及びスピーカ１１１７を含む出力装置とにより形成される。変復調器（モデム）トランシーバ装置１１１６は、例えば電話回線１１２１又は他の機能媒体を介して接続可能な通信ネットワーク１１２０と通信するためにコンピュータモジュール１１０１により使用される。モデム１１１６は、インターネット並びにローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）等の他のネットワークシステムにアクセスするために使用され、いくつかの実現例においてはコンピュータモジュール１１０１に内蔵されても良い。
【００３３】
一般に、コンピュータモジュール１１０１は、少なくとも１つのプロセッサユニット１１０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されるメモリユニット１１０６とを含む。モジュール１１０１は、ビデオ表示装置１１１４及びスピーカ１１１７に結合するオーディオビデオインタフェース１１０７と、キーボード１１０２及びマウス１１０３及びオプションとしてジョイスティック（不図示）に対する入出力（Ｉ／Ｏ）インタフェース１１１３と、モデム１１１６、スキャナ１１８及びプリンタ１１１５に対するインタフェース１１０８とを含む多くのＩ／Ｏインタフェースを更に含む。いくつかの実現例において、モデム１１１６は、コンピュータモジュール１１０１内、例えばインタフェース１１０８内に内蔵されても良い。記憶装置１１０９が提供され、一般にハードディスクドライブ１１１０及びフロッピー（登録商標）ディスクドライブ１１１１を含む。磁気テープ装置（不図示）が更に使用されても良い。一般にＣＤ−ＲＯＭドライブ１１１２は、データの不揮発性ソースとして提供される。一般にコンピュータモジュール１１０１の構成要素１１０５〜１１１３は、当業者には周知のコンピュータシステム１１００の従来の動作モードを結果として与える方法で、相互接続バス１１０４を介して通信する。上述の構成が実現されるコンピュータの例として、ＩＢＭのＰＣ及びそれに互換性のある、Sun SPARCstation又はそれから進化した同様のコンピュータシステムがある。
【００３４】
一般に、アプリケーションプログラムは、ハードディスクドライブ１１１０に常駐し、プロセッサ１１０５による実行の際に読み出され且つ制御される。ネットワーク１１２０から取り出されるプログラム及び任意のデータの中間記憶装置は、ハードディスクドライブ１１１０と共に動作する可能性のある半導体メモリ１１０６を使用して達成されても良い。いくつかの例において、アプリケーションプログラムは、ＣＤ-ＲＯＭ又はフロッピー（登録商標）ディスク上で符号化されてユーザに供給され、対応するドライブ１１１２又は１１１１を介して読み出されても良い。或いは、アプリケーションプログラムは、ユーザによりモデム装置１１１６を介してネットワーク１１２０から読み出されても良い。また、ソフトウェアは、他のコンピュータ読み取り可能な媒体からコンピュータシステム１１００にロードできる。本明細書において使用される用語「コンピュータ読み取り可能な媒体」は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム１１００に提供することに関係する任意の記憶装置又は伝送媒体を示す。記憶媒体の例としては、装置がコンピュータモジュール１１０１の内部装置であるか又は外部装置であるかに関わらず、フロッピディスク、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、或いはＰＣＭＣＩＡカード等のコンピュータ読み取り可能なカード等がある。伝送媒体の例としては、別のコンピュータ又はネットワーク化装置に対するネットワーク接続、並びに電子メール送信及びウェブサイト等に記録された情報を含むインターネット又はイントラネットに加え、無線伝送チャネル又は赤外線伝送チャネルがある。
【００３５】
アプリケーションプログラムは、スキャナ１１１８からコンピュータ１１０１に情報を走査する場合及びプリンタ１１１５に印刷する場合に動作可能である。
【００３６】
［ＬＶＢＣの基本構造］
図３は、ＬＶＢＣ３００の外観を示す拡大図である。ＬＶＢＣ３００は、正方形グリッド３０１の交点３０３に近接する多くのドット３０２により形成される。尚、可視のＬＶＢＣ３００を形成するのはドット３０２のみである。グリッド３０１は、単にドット３０２の場所を説明するために示されるため、「仮想」と考えられても良い。ＬＶＢＣ３００の外観は、ドットの標準グリッドと類似するが同一ではない。
【００３７】
図４に、ドット４０２の標準グリッド４００の外観を示す。ここで、ドット４０２は標準正方形グリッド４０１の交点にある。正方形グリッド４０１はピッチ４０３を有し、これは本明細書では「gp」と呼ぶ。
【００３８】
ドットの標準配列４００とＬＶＢＣ３００との間の相違点は、ＬＶＢＣ３００のドット３０２の位置が、ドット３０２が実際の標準配列４００の一部であった場合にドット３０２が占有するグリッド位置から離れた位置に僅かに変調されていることである。この僅かな変調は２つの目的を満足する。第１の目的は、ＬＶＢＣドット３０２の可視性を標準グリッド４００のドット４０２より僅かに減少することである。これは、人間の視覚系が標準グリッドを認識することに非常に適しているからである。変調の第２の目的は、デジタルデータの形式のメッセージがドット４０２の変調に格納されることである。
【００３９】
図５に、ドットの変調を更に詳細に示す。ドット５０２は、標準グリッド５０１の交点上又は交点に近接し、各ドット５０２は、９つの可能な位置５０３のうちの１つに変調される。対応する交点に関して各ドット５０２の左右の横軸の場所である変調は、ドットにより形成されたパターンのデータを表す。グリッドが規定可能及び機械検出可能であり、変調が対応するマークに対して行われても良い基準の場所の集合を形成するという点において、グリッド５０１は標準である。図示するように、各ドットの９つの可能な位置は、関連するか又は対応するグリッド交点を中心とする３×３の配列で構成される。位置５０３の３×３の配列の中心位置は、グリッドの交点に位置付けられ、水平方向及び垂直方向の距離がゼロの変調に対応する。残りの８つの変調位置は、水平方向、垂直方向、或いは水平方向及び垂直方向の双方に対してグリッドの交点からオフセットされる。標準グリッド５０１は、変調されたドットに対する「キャリア」信号と考えられても良く、無線周波数通信における搬送波と同様に直接観測可能ではない。変調位置がオフセットされる水平及び垂直の距離は変調量子５０４であり、本明細書においては「mq」と略す。対応するグリッドの交点に対する９つの変調位置の場所は、（ｘ、ｙ）ベクトルのリストとして書ける。ここで、ｘは水平方向を示し、ｙは垂直方向を示す。また、ｘに関しては右向きのオフセットが正であり、ｙに関しては下向きのオフセットが正であるという規則を使用する。ベクトルは以下の通りである。
【００４０】
【数１】
【００４１】
図６に、ドット変調位置５０３を更に詳細に示す。位置５０３は、グリッド６０２のグリッド交点６０４を中心とし、位置６０１等の各変調位置は関連するデジタルコード値６０３を有する。位置６０１に対するデジタルコード値６０３は「０」である。９つの変調位置（位置６０１を含む）により、各ドットは９つの可能なデジタルコード値（位置６０１に対する値６０３を含む）のうちの１つを符号化できる。変調位置により、ＬＶＢＣはデジタルデータ記憶装置として動作でき、ＬＶＢＣの各ドットはデータの９を基数とする１つの数字を格納する。図７に示すように、デジタルデータ記憶装置の数字の好ましい順序付けは、ドットの矩形配列を使用することにより提供される順序付けである。この順序付けは、図７の一番上の最も左側のドット７０１から開始し、一番下の最も右側のドット７０３に到達するまで左から右及び上から下に連続的に進む。本開示の趣旨の範囲から逸脱せずに、他の順序付けが同様に利用されてもよいことは当業者には容易に理解されるだろう。
【００４２】
［符号器］
図８は、ＬＶＢＣを符号化する好適な方法８００を示すフローチャートである。一実現例において、符号化は、ＰＣ１０１又はコンピュータ１１０１内で実行可能なソフトウェアアプリケーションにより実行され、プリンタ１０２又は１１１５により媒体１０７上に印刷するためのＬＶＢＣを生成する。処理はステップ８０１で開始し、ＬＶＢＣに符号化されるバイナリメッセージを入力として受け付ける。このバイナリメッセージは、リードソロモン又は低密度パリティチェック（ＬＤＰＣ）等の誤り訂正符号（ＥＣＣ）を使用して冗長性を含んで符号化される。多くの場合、ＥＣＣを使用することにより、限定された伝送エラーがあってもＬＶＢＣが復号化される。ステップ８０２において、３つの変数Ｍ、Ｗ及びＨが計算される。Ｍはメッセージを表すのに必要とされる９を基数とするメッセージ記号数であり、ＷはＬＶＢＣの最小幅（ＬＶＢＣドットで表される）であり、ＨはＬＶＢＣの最小の高さ（ＬＶＢＣドットで表される）である。
【００４３】
ビット長ＢＬのメッセージの場合、Ｍは以下のように計算される。
【００４４】
【数２】
【００４５】
上記演算子は「天井関数」の演算子を表し、その引数の値以上の最小の整数を返す。
【００４６】
Ｗ及びＨは、以下の不等式により制限される。
【００４７】
【数３】
【００４８】
この不等式に対する整数解が使用されてもよいが、好ましい解は、ＷがＨと等しいことを要求することにより正方形ＬＶＢＣを作成することである。これは、Ｗ及びＨが以下のように計算されることを意味する。
【００４９】
【数４】
【００５０】
ステップ８０３において、３つの変数ｘ、ｙ及びｉがゼロに初期化される。
【００５１】
ステップ８０４において、ＬＶＢＣの構成ドットの１つが出力される。ドットはドットを配置できる任意の種類の２次元基板に出力できるが、この特定の例においては、ドットはプリンタ１０２により印刷される１枚の紙１０７に出力される。ドットは以下の位置に出力される。
【００５２】
【数５】
【００５３】
式中、「msg」はＬＶＢＣに格納される９を基数とするメッセージ記号又はデータ項目のシーケンスである。このシーケンスは、メッセージを１つの長い２進数として扱い、当業者には周知の単純な変換技術を使用してその数を９を基数とする表現に変換することにより、ステップ８０１において受け付けたメッセージのバイナリ表現から容易に形成される。msg[0]がシーケンスの開始であるという規則を使用すると、「msg[i]」はメッセージシーケンスのi番目の数字である。z ≧ Mの場合にmsg[z]はゼロとして規定される。
【００５４】
「Vec」は９つのオフセットベクトルの配列であり、以下の値を含む。
【００５５】
【数６】
【００５６】
式中、ｍｑは上述の変調量子５０４である。
【００５７】
ステップ８０５において、現在の水平位置ｘは、ｘを値ｇｐ４０１だけ増加することにより右に移動される。メッセージの添え字ｉは１だけ増加されるため、メッセージの添え字はメッセージの次の数字を参照する。
【００５８】
ステップ８０６において、変数ｘは変数Ｗと比較される。ｘがＷ以上である場合はステップ８０７に進み、Ｗ未満である場合はステップ８０５に戻る。
【００５９】
ステップ８０７において、現在の垂直位置ｙは、ｙを値ｇｐ４０１だけ増加することにより下方向に移動される。変数ｘはゼロに再設定される。その後、ステップ８０８に継続する。
【００６０】
ステップ８０８において、変数ｙは変数Ｈと比較される。ｙがＨ以上である場合、即ちＹｅｓの場合はステップ８０９に進み、Ｎｏの場合はステップ８０５に戻る。
【００６１】
この方法の処理はステップ８０９で終了する。
【００６２】
方法８００の最終的な結果はＬＶＢＣを形成するドットのパターンであり、各ドットはグリッドの対応する交点に対してデジタル位相変調された（ｘ、ｙ）座標を有する。グリッドは任意の原点Ｏ（０，０）を有する。印刷媒体１０７上で原点Ｏを特定の座標（ｘ，ｙ）に設定することにより、ＰＣ１０１は媒体１０７上にデータを印刷することを命令でき、その結果、ＬＶＢＣは複写され且つ場所（ｘ，ｙ）から開始する。
【００６３】
［復号器］
図９は、画像中の低可視バーコード（ＬＶＢＣ）を復号化する方法９００を示すフローチャートである。ここで、ＬＢＶＣは上述のように符号化されている。一実現例において、方法９００はスキャナ１０４を介して読み取られたＬＶＢＣを入力したＰＣ１０６内で実行可能なソフトウェアアプリケーションとして実行される。復号化方法の基本的な前提は、符号化ＬＶＢＣが形成される際に元になったグリッドの正確な向きを判定することである。グリッド自体の規則性を理解することは、グリッドが識別されると、ドットの場所の変調も理解できることを意味する。方法９００はステップ９０１で開始し、例えば印刷されるか又はページから機械により読み取り可能であるＬＶＢＣを組み込むページの走査済画像を入力として受け付ける。一実現例において、走査は６００ｄｐｉで走査された８ビット階調のＪＰＥＧ画像の形式をとる。ステップ９０３において、ＬＶＢＣを形成する複数のドットが検出され、その後ステップは座標データのリストに検出したドットと関連する位置／座標（ページ上の）を格納／記録する。ステップ９０３は、走査済画像の接続構成要素解析を使用して実行されても良い。そのような解析において、画像の個々の画素は検査され、空間的に隣接する画素を接続及びグループ化する。形状に関してそのグループを解析することにより、マーク（即ち、適切な予想される大きさの画素の一般に一様な斑点又は円形のドット）の存在が検出される。マークの重心は、検出したマーク（ドット）に対応する座標の場所を識別するために判定されても良い。
【００６４】
ステップ９０５において、ステップ９０３で取得されたドットの座標のリストが解析され、ＬＶＢＣのキャリア信号を形成する標準グリッドを検出／識別する。この処理は、標準グリッドのピッチ（ｇｐ４０１）、回転角度及び変調量子Ｍｑ（５０４）を返し、供給された座標データのリストを図７に示すように、順序付けされた座標データの矩形配列に変換する。符号化データを表す変調グリッドを提示されると、変調グリッドに対する向き及び間隔を判定することが有用である。ステップ９０５において、変調グリッドではドット間の平均間隔がグリッド間隔に等しいということに基づいてグリッド間隔が判定されても良い。変調グリッドの隣接するドット間の平均の方向が標準正方形グリッド（又は「キャリアグリッド」）の線に位置合わせされることに基づいてグリッドの向きが判定されても良い。
【００６５】
変調量子は、残りの変調位置が対応するキャリアグリッドの交点（図６の６０４）からオフセットされる水平及び垂直距離を示す。変調グリッドのドットは、キャリアグリッドの交点に近接する。一実現例において、変調グリッドの各ドットは、対応するキャリアグリッドの交点を中心とする３×３の配列で配置される９つの可能な位置のうちの１つに変調される。そのような３×３の配列の中心位置は、対応するキャリアグリッドの交点に位置付けられ、水平方向及び垂直方向の距離がゼロの変調に対応する。残りの８つの変調位置は、対応するキャリアグリッドの交点からのオフセットされる。
【００６６】
ステップ９０７において、各ドットの位置に格納された情報が復調される。図６を再度参照すると、復調は、標準グリッド６０２の最近接するキャリアグリッドの交点６０４から最近接又は略最近接するＬＶＢＣドットまでのベクトルを測定することにより達成される。測定されたベクトルは、交点６０４から図６に示す９つの変調位置までのベクトルと比較される。図６において、ベクトル６０５は点６０４から変調位置６０１まで延在する。同様のベクトルが他の各変調位置に対して存在する。ＬＶＢＣドットの測定ベクトルと相関するか又は最も一致する変調位置ベクトルは正確な位置として選択され、値６０３等の対応するデジタルデータ値はＬＶＢＣドットの正確なデータ値として選択される。一致度は、多くの方法で判定されても良い。第１の方法は、グリッドの交点から延在するベクトルのユークリッド比較を使用することである。例えば、ベクトルＶ１（ｘ１，ｙ１）及びＶ２（ｘ２，ｙ２）を使用すると、説明する構成における全ての可能な９つのベクトルの最短のユークリッド距離は以下を使用して計算されても良い。
【００６７】
【数７】
【００６８】
或いは、ベクトルの長さがゼロに近いために角度が不確かである場合に変調が交差位置まで縮退すると仮定すると、グリッドの交点に関する角度が使用されても良い。このように、ステップ９０５により返される全てのドットが処理される。処理は図７に示す順序で実行される。
【００６９】
この段階までに、ＬＶＢＣは、ＬＶＢＣが９を基数とするデータ記号の略矩形の配列の形式であるところまで復号化された。この配列はデータ記号の正確な順序付けを提供するための方法の一部であるが、依然としてメッセージの開始であるデータ記号を識別する必要がある。これは、ＬＶＢＣの回転がまだ完全に解決されていないためである。ステップ９０５は、９０度を法とする回転のみを検出する（即ち、９０度、１８０度又は２７０度の回転はまだ検出されていない）。この問題はステップ９０９において対処される。このステップは、図１０を参照して以下に詳細に説明する。
【００７０】
本開示の一実施形態によると、デジタルデータの保護のために使用されるＥＣＣ符号化デジタルデータに対して情報マークの正確な向きを判定する方法が提供される。方法は、情報マークの１つの可能な向きに対してＥＣＣ符号化データの復号化を試みるステップと、ＥＣＣ復号化が失敗した場合に情報マークの異なる可能な向きを採用し且つＥＣＣ符号化データの復号化を再度試みるステップとを含む。
【００７１】
図１０は、ＬＶＢＣのメッセージデータの開始を見つけるための図９のステップ９０９の方法を示すフローチャート１０００である。処理はステップ１００５で開始し、ステップ１０１０において、ステップ９０７で生成された復調データの正確度が検査される。この正確度の検査は、復調データのＥＣＣ符号化データのＥＣＣ復号化を試みることにより達成される。ＬＶＢＣが不適切に配向される（例えば、９０度、１８０度又は２７０度回転されている）場合、回転はメッセージデータの数字の場所をスクランブルし且つ変調値をスクランブルするため、ＥＣＣ復号化は失敗する。失敗したＥＣＣ復号化は、復調データが不適切に配向されることを示す。ステップ１０１０においてＥＣＣ復号化が失敗した場合、即ちＮｏの場合、ステップ１０１５に継続する。或いは、ステップ１０１０においてＥＣＣ復号化が成功した場合、即ちＹｅｓの場合、ステップ１０２５に進み、メッセージの開始が正確に検出される。その後、図９のステップ９１１に進む。
【００７２】
ステップ１０１０の検査は、完全なＥＣＣ復号化結果に対するものであっても良いが、一実施形態においては、検査は略完全なＥＣＣ復号化結果に対するものである。一実施形態においてＬＤＰＣがＥＣＣとして使用されるため、この方法が使用され、各繰返しが前の繰返しより少ないエラーを有する傾向にある繰返し復号化によりＬＤＰＣは動作する。完全なＬＤＰＣ復号化が実行可能であるが、多くの繰返しの後でもＬＤＰＣ復号化動作が正確な結果に収束できないためにＬＶＢＣが不適切に位置合わせされる場合、処理時間は過剰になる。
【００７３】
次に、ＬＤＰＣ復号化が略完全であるかを判断するために、ステップ１０１０において使用される基準について説明する。ＬＤＰＣ復号化は不完全な処理であり、この処理において、エラー数が制限される場合にのみ復号化が可能である。メッセージがこの制限を超える数のエラーを有する場合、ＬＤＰＣ復号化は実現不可能になる。この制限は、以下により実験的に正確に推定される。
・大量のメッセージを取り込む
・各メッセージをＬＤＰＣ符号化する
・メッセージ毎に符号化値の比率ｐｅ分を破損させる
・各メッセージの完全なＬＤＰＣ復号化を試みる。
【００７４】
完全なＬＤＰＣ復号化により一貫して且つ確実に訂正される最大破損比率ｐｅは、訂正されると適切に予想されるエラーの最大比率であるｌｐｅとして記録される。
【００７５】
第２の実験は以下により行われる。
・大量のメッセージを取り込む
・各メッセージをＬＤＰＣ符号化する
・メッセージ毎に符号化値のうちｌｐｅパーセント分を破損させる
・メッセージ毎にＬＤＰＣ復号化の繰返しを１度試み、失敗したＥＣＣチェックサムの数ｎｃｆを記録する。
【００７６】
最後に、この実験で記録されたｎｃｆの最大値は、ＬＤＰＣ復号化が十分に完全に近いかを判定するために閾値として使用される。ＬＤＰＣ復号化を１度繰り返した結果、ｎｃｆ以下の数の失敗したＬＤＰＣチェックサムが得られる場合、ＬＤＰＣ復号化は略完全であると考えられる（ステップ１０１０の「ＥＣＣは適切」）。
【００７７】
ステップ１０１５において、ＬＶＢＣの全ての可能な向きの正確度が検査されたか（即ち、最後の回転であるか？）に関するテストが行われる。ＬＶＢＣが正方形グリッドを使用するため、これは単に検査された向きの数が４未満であるかというテストである（三角形又は六角形グリッドに基づく別の種類のバーコードの場合、テストは検査された向きの数がそれぞれ３つ又は６つ未満であるかというテストになる）。全ての４つの向きが正常に検査されなかった場合、即ちＹｅｓの場合、データの正確な向きが見つけられなかったため、処理はステップ１０３０で異常終了する。Ｎｏの場合、ステップ１０２０に継続する。
【００７８】
ステップ１０２０において、グリッドは時計方向に９０度回転される。これは各ドットをグリッドの中心に関して９０度回転して移動し、その回転を補償するために各ドットの変調を再解釈することにより達成される。再解釈は、各変調値を以下の表１に示すルックアップテーブルで見つけられる対応する回転変調値と置換することにより達成される。
【００７９】
【表１】
【００８０】
ステップ１０２０の結果、マークのパターンの異なる向きに対するデータの再解釈が得られる。グリッドの回転に関してそのように説明されるが、マークのパターンはグリッド及びマーク毎に判定される新しい位置ベクトルに関して回転されても良く、対応する（回転）データ値はそのパターンから判定される。
【００８１】
ステップ１０２０の終了後、ステップ１０１０に戻る。その後、正確な向きに対する検査の処理が回転データに対して行われる。この手順は、正確な向きが見つけられ、処理がステップ１０２５で正常終了するか又はステップ１０３０で異常終了するまで継続する。異常終了は方法９００を終了させ、正常終了は、方法９００が図９のステップ９１１に進むことを可能にする。
【００８２】
別の実施形態は、回転毎にＥＣＣ復号化を実行し、失敗したＥＣＣチェックサムの数ncfを記録する。ncfの最小数を有する向きは、正確な向きとして返される。
【００８３】
図９を再度参照すると、ステップ９１１は、メッセージ開始が正確に配向されるグリッドの一番上の最も左側の位置に位置付けられるまでステップ９０９により処理された検出された９を基数とするデータ値の矩形グリッドを入力として受け付ける。ステップ９１１は、一番上の最も左側のデータ値から開始し、左から右及び上から下に進むことにより復号化メッセージをアセンブルし、その順番で９を基数とするデータ値を出力する。９を基数とするデータ値を処理する順序は図７により示される順序であり、これについては既に説明した。
【００８４】
ＥＣＣ符号化復調データはＬＶＢＣから抽出され、復号化処理はステップ９１３で終了する。その後、ＥＣＣ符号化復調データはＥＣＣ復号化により訂正される。一実施形態において、これは完全な（複数回繰り返される）ＬＤＰＣ復号化により達成される。
【００８５】
説明した構成は、文書中のデータパターンの形成及び読み取りを提供し、パターンは文書中に形成される複数のマークを有し、各マークは機械により読み取り可能であり且つパターンの不可視のキャリアを形成する仮想グリッドの対応する交差場所等の基準位置に対してデジタル位相変調された場所を有し、変調はそのパターンのデータを表す。
【００８６】
マークは、印刷することにより形成されるドットであるのが好ましく、文書の識別を可能にするコードを共に形成する。マークの大きさは、許容される可視性のレベル及び特定の応用に依存して異なる。その大きさは、文書の印刷解像度で１画素ほどの小ささでも良く、それにより人間の目に対して低い可視性を提供し、一方では電子機械読み取りのための走査を可能にする。マーク及びマークが搬送する識別データは、周知のバーコードに等しい汎関数を表し、「バー」が実際には形成されないが「バーコード」と呼ばれても良い。低い可視性の面と組み合わされる場合、マークはバーを有さず、いくつかの実現例においては人間の目に明らかに可視である可能性があるが、パターンは低可視バーコード（ＬＶＢＣ）と考えられても良い。
【００８７】
符号化の際、配列は所望のデータ量を搬送するのに十分な有用な大きさであっても良く、その一方で、配列が正確に検出されることを保証するために、復号化は実現可能な最小の配列サイズを必要とする。これは正確な復号化には不可欠である。１つの実現可能な最小グリッド／配列サイズは約８×８（即ち、６４個のマークを与える）であり、確実に実現可能なサイズは１０×１０又は１２×１２である。現在の９を基数とする構成において、８×８のグリッドサイズは約２０２（＝64（log29））ビットのデータを提供する。本開示の趣旨の範囲を逸脱せずに、他のグリッド／配列サイズが同様に実現可能であってもよいことは、当業者には理解されるだろう。
【００８８】
グリッドの交点毎に変調ドットが１つのみ存在するため、それがその交点に対して固有であることは、上記から明らかだろう。交点に関連するドットが２つ以上存在する場合、曖昧さが生じ、復号化は無意味な結果を生成する。従って、任意の実現可能な実現例の場合、任意の１つの交点の可能な変調ドットの場所は別の（例えば、隣接する）交点のドットの可能な変調場所とオーバラップすべきではない。
【００８９】
他のいくつかの方法は、標準（正方形）グリッドの交点に位置付けられるドットにより形成されるコンピュータ読み取り可能なマークを提供した。それらの例において、ドットは論理「１」を表すために交点において生成されても良く、ドットは論理「０」を表すために生成されない。その結果、ドットが生成されないことにより、論理「０」ではなくコンピュータ読み取り可能なマークがないと解釈されるという曖昧さが生じる。反対に、ここで開示される構成により、全てのデータ値はマークにより表現され、データ値を判定するのは仮想グリッドの対応する交点に対するマークの位置である。従って、曖昧さの尤度は減少する。マークはドットである必要はなく、最も単純なレンダリングでは紙上の１滴のインクであっても良く、これは小さな略円形のマークを示すだろう。いくつかの実現例において、例えばマークはドット群であっても良く、正方形又は三角形等の任意の所望の検出可能な形状を形成する。実現可能な大きなドットは、この分の末尾に現れるようなピリオドと等しくても良い。それは、フォントサイズに依存して多くの表示可能な画素又は印刷可能な画素を占有する可能性がある。
【００９０】
説明する構成は結果として電子ページデータを形成し、この形成の結果、プリンタ１０２、１１１５に出力される時、説明したように情報コンテンツ及び１つ以上のＬＶＢＣを有する可能性のあるページデータのハードコピーが複写される。電子データは、後続する複写のために格納されてもよい電子文書をビデオ表示装置１１１４又はプリンタ１０２、１１１５を介して電子的に形成する。同様に、説明したようにＬＶＢＣを組み込む文書の走査により、ページデータが１つ以上のＬＶＢＣを含む電子文書が生成される。複写及び／又は格納のモードに関係なく、そのような電子文書は印刷又は復号化のためにコンピュータ間で通信されてもよい（例えばネットワーク１１２０を介する）。
【００９１】
［ＬＶＢＣの背景］
更に本開示は、画像中のドットパターンを復号化することに関する。ドットパターンはドットの変調グリッドであり、これは少なくともデータメッセージを符号化する。尚、少なくとも１つの実現例において、ドットパターンは位置決めマーク又は同期マークを有する必要はない。しかし、本実現例は、位置決めマーク又は同期マークを含むドットパターンを検出できる。
【００９２】
本開示に係る一実施形態の一実現例は、コピー機に組み込まれたソフトウェア又はコピー機にリンクされるソフトウェアで実現される。コピー機を使用してドットパターンを含む画像をコピーしようとする場合、ドットパターンを検出するために画像は解析される。復号化メッセージは、画像の複写が許可されているか否かを判定する。例えば、入力画像から復号化された４つのメッセージのうち，３つのメッセージがコピーを許可し、１つのメッセージがコピーを禁止する場合、入力画像はコピーされない。更に、別の実施形態は、コピーを許可するドットパターン領域のみを複写し、コピーを禁止するドットパターン領域を省略しても良い。
【００９３】
別の実現例において、本実施形態により識別されたドットパターン領域及びそれらの関連する復号化メッセージをオペレータに対して視覚的に識別可能である。
【００９４】
本明細書において説明される方法は、図３８に示すようなコピー機３８１５に結合されるコンピュータシステム３８００を使用して実現されても良く、図１〜図１０、図１２〜図３７の処理は、コンピュータシステム３８００内で実行可能な１つ以上のアプリケーションプログラム等のソフトウェアとして実現されても良い。コンピュータシステム３８００は試みたコピー動作を検出でき、コピー処理においてコピー機３８１５を共に形成するスキャナ及びプリンタを制御できる。一実現例において、コンピュータシステム３８００は、画像中のコンピュータ読み取り可能なマークの構成内で位置決めマークの配置を識別する方法を実現する。コピー機３８１５は、コンピュータ読み取り可能なマークを含む画像を走査するために利用される。特に、配置の識別、バーコードの検出及びコピープロテクトの方法のステップは、コンピュータシステム３８００内で実行されるソフトウェアの命令により行われる。命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されても良い。ソフトウェアは２つの別個の部分に分割されても良く、第１の部分及び対応するコードモジュールは識別及び検出方法を実行し、第２の部分及び対応するコードモジュールは第１の部分とユーザとの間のユーザインタフェースを管理する。例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読み取り可能な媒体に格納されても良い。ソフトウェアは、コンピュータ読み取り可能な媒体からコンピュータシステム３８００にロードされ、コンピュータシステム３８００により実行される。そのようなソフトウェア又はコンピュータプログラムを記録したコンピュータ読み取り可能な媒体は、コンピュータプログラム製品である。コンピュータプログラム製品をコンピュータシステム３８００において使用することにより、バーコードを検出及び配置を検出するための有利な装置を達成するのが好ましい。
【００９５】
図３８に示すように、コンピュータシステム３８００は、コンピュータモジュール３８０１と、キーボード３８０２及びマウスポインタデバイス３８０３等の入力装置と、表示装置３８１４及びスピーカ３８１７を含む出力装置と、コピー機３８１５に対する接続とにより形成される。外部変復調器（モデム）トランシーバ装置３８１６は、接続３８２１を介して通信ネットワーク３８２０と通信するためにコンピュータモジュール３８０１により使用されても良い。ネットワーク３８２０は、インターネット又は専用ワイドエリアネットワーク（ＷＡＮ）等のＷＡＮであっても良い。接続３８２１が電話回線である場合、モデム３８１６は従来の「ダイヤルアップ」モデムであっても良い。あるいは、接続３８２１が大容量（例えば、ケーブル）接続である場合、モデム３８１６はブロードバンドモデムであっても良い。無線モデムは、ネットワーク３８２０に無線接続するために使用されても良い。ネットワーク３８２０及び３８２２は、同様に制御されるのが望ましい他のコピー機にアクセスできる。
【００９６】
一般に、コンピュータモジュール３８０１は、少なくとも１つのプロセッサユニット３８０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されるメモリユニット３８０６とを含む。モジュール３８０１は、ビデオ表示装置３８１４及びスピーカ３８１７に結合するオーディオビデオインタフェース３８０７と、キーボード３８０２及びマウス３８０３及びオプションとしてジョイスティック（不図示）に対する入出力（Ｉ／Ｏ）インタフェース３８１３と、外部モデム３８１６及びコピー機３８１５に対するインタフェース３８０８とを含む多くのＩ／Ｏインタフェースを更に含む。いくつかの実現例において、モデム３８１６は、コンピュータモジュール３８０１内、例えばインタフェース３８０８内に内蔵されても良い。コンピュータモジュール３８０１は、接続３８２３を介してコンピュータシステム３８００をローカルエリアネットワーク（ＬＡＮ）として周知のローカルコンピュータネットワーク３８２２に結合することを可能にするローカルネットワークインタフェース３８１１を更に有する。図示するように、ローカルネットワーク３８２２は、接続３８２４を介してワイドネットワーク３８２０に結合しても良く、一般に、所謂「ファイアウォール」装置又は同様の機能性を含む。インタフェース３８１１は、Ethernet（登録商標）回路カード、無線Bluetooth（登録商標）又はＩＥＥＥ８０２．１１無線構成により形成されても良い。
【００９７】
インタフェース３８０８及び３８１３は、直列接続性及び並列接続性の双方を提供でき、一般に直列接続性は、ユニバーサルシリアルバス（ＵＳＢ）規格に従って実現され、対応するＵＳＢ接続（不図示）を有する。記憶装置３８０９が提供され、一般にハードディスクドライブ（ＨＤＤ）３８１０を含む。フロッピー（登録商標）ディスクドライブ及び磁気テープ装置（不図示）等の他の装置が更に使用されても良い。一般に光ディスクドライブ３８１２は、データの不揮発性ソースとして動作するために提供される。光ディスク（例えば、ＣＤ−ＲＯＭ、ＤＶＤ）、ＵＳＢ−ＲＡＭ及びフロッピー（登録商標）ディスク等のポータブルメモリ素子は、システム３８００に対するデータの適切な供給元として使用されても良い。一実現例において、本開示の一実施形態に従って識別された一群は、１つ以上の記憶装置３８０９に格納される。格納された一群は、後でデータ搬送マークを復号化するために使用される。
【００９８】
一般に、コンピュータモジュール３８０１の構成要素３８０５〜３８１３は、当業者には周知のコンピュータシステム３８００の従来の動作モードを結果として与える方法で、相互接続バス３８０４を介して通信する。上述の構成が実現されるコンピュータの例として、ＩＢＭのＰＣ及びそれに互換性のある、Sun SPARCstation、Apple Mac（登録商標）又はそれから進化した同様のコンピュータシステムがある。
【００９９】
通常、上述のアプリケーションプログラムは、ハードディスクドライブ３８１０に常駐し、プロセッサ３８０５による実行の際に読み出され且つ制御される。ネットワーク３８２０及び３８２２から取り出されるプログラム及び任意のデータの中間記憶装置は、ハードディスクドライブ３８１０と共に動作する可能性のある半導体メモリ３８０６を使用して達成されても良い。いくつかの例において、アプリケーションプログラムは、１つ以上のＣＤ-ＲＯＭ上で符号化されてユーザに供給され、対応するドライブ３８１２を介して読み出されても良い。或いは、アプリケーションプログラムはユーザによりネットワーク３８２０又は３８２２から読み出されても良い。更にソフトウェアは、他のコンピュータ読み取り可能な媒体からコンピュータシステム３８００にロードできる。コンピュータ読み取り可能な媒体は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム３８００に提供することに関係する任意の記憶媒体を示す。そのような媒体の例としては、装置がコンピュータモジュール３８０１の内部装置であるか又は外部装置であるかに関わらず、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、或いはＰＣＭＣＩＡカード等のコンピュータ読み取り可能なカード等がある。命令及び／又はデータの提供に関係しても良いコンピュータ読み取り可能な伝送媒体の例としては、別のコンピュータ又はネットワーク化装置に対するネットワーク接続、並びに電子メール送信及びウェブサイト等に記録された情報を含むインターネット又はイントラネットに加え、無線伝送チャネル又は赤外線伝送チャネルがある。
【０１００】
アプリケーションプログラムの第２の部分及び上述の対応するコードモジュールは、表示装置３８１４上にレンダリングされるか又は表現される１つ以上のグラフィカルユーザインタフェース（ＧＵＩ）を実現するために実行されても良い。キーボード３８０２及びマウス３８０３を操作することにより、コンピュータシステム３８００のユーザ及びアプリケーションはインタフェースを操作し、ＧＵＩと関連するアプリケーションに対して制御コマンド及び／又は入力を提供しても良い。
【０１０１】
マークを検出する方法は、画像処理の機能又はサブ機能を実行する１つ以上の集積回路等の専用ハードウェアで実現されても良い。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ、或いは１つ以上のマイクロプロセッサ及び連想メモリを含んでも良い。更に、コピー機３８１５に結合されるコンピュータシステム３８００を参照して説明したが、コンピュータシステム３８００の説明した機能性の殆どはコピー機３８１５に内蔵され、特定の局所演算を可能にしても良い。
【０１０２】
［基本構造］
データは、変調グリッドを使用してバーコードに格納される。図２８は、変調グリッドの外観を示す拡大図である。変調グリッドは、正方形グリッド２８０１の交点２８０３に近接するドット２８０２及び２８０４の形式の大量のマークから形成される。尚、可視の変調グリッドを形成するのはドット２８０２及び２８０４のみであり、単にドット２８０２及び２８０４の場所を説明するためにグリッド２８０３を示す。
【０１０３】
変調グリッドは、２種類のドットから構成される。ドット２８０２は「データ」ドットの一例であり、このドットは交点２８０３に関して変調される。ドット２８０４は「配置」ドットの一例であり、このドットは交点２８０３の真上にある。図２８において、データ搬送ドット及び配置ドットを異なる陰影を使用して示すが、データ搬送ドット及び配置ドットは各変調以外は実際には同一であり、陰影は図示することを目的とする。図２８に図示する例において、バーコードは、データ搬送ドットが５０％及び配置ドットが５０％で構成される。当然、本開示の趣旨の範囲から逸脱せずに、最小限の変更を伴う他の構成が可能である。
【０１０４】
図２９に、バーコード復号化から発見されたグリッド２９０１を示す。データ搬送ドット２９０２をグリッド２９０１の正方形内に示し、配置ドット２９０４をグリッド２９０１の交点上に示す。配置ドットは、グリッド２９０１を構築するために使用され、各グリッド交点上に現れる。配置ドットが１つおきに位置付けされるため、発見されたグリッドは元の正方形グリッドから４５度オフセットされ、グリッドの間隔は√２倍大きい。この発見されたグリッド２９０１は、ページを２９０３で示される多くの正方形グリッドセルに分割する。各グリッドセルは、正確に１つのデータ搬送ドットを含む。グリッドセルは、バーコードデータの格納及び復号化に対して使用される基本単位である。
【０１０５】
図３０に、情報がグリッドセルのデータ搬送ドットに格納される方法を示す。ドット３００２は、グリッド３００１のグリッドセルのグリッドセル中心３００５に近接して存在し、各ドットは、８つの可能な位置３００３のうちの１つに変調される。各ドットに対する８つの可能な位置は、関連するグリッド交点を中心とする円に配置される。８つの変調位置は、グリッドの中心から水平に、垂直に又は対角線状にオフセットされる。変調位置がオフセットされる水平及び垂直距離は、本明細書では「Ｍｑ」と略される変調量子３００４である。Ｍｑは、グリッドセルの辺の長さの固定比率となるように選択される。Ｍｑの適切な選択肢は元の正方形グリッド間隔の４０％であるが、他の比率が同様に実現されても良い。
【０１０６】
図３１に、ドット変調位置３００３を更に詳細に示す。ドット変調位置３００３はグリッドセル中心３１０３を中心とし、３１０１等の各変調位置はそれに関連付けられる３１０２等のデジタルコード値を有する。８つの変調位置（３１０１を含む）は、各ドットが８つの可能なデジタルコード値（３１０１に対する３１０２を含む）のうちの１つを符号化することを可能にする。これにより、変調グリッドはデジタルデータ記憶装置として動作でき、変調グリッドの各ドットはデータの１つの８を基数とする数字を格納する。理想的には、各ドットはドットが円のグレイコードに配置されるようにコード値を符号化する。これにより、復号化中の誤り訂正が容易になる。図３１に、各ドットのデジタルコード値を２進数で示す。３１０２から時計回りに開始して、ドットは値５、７、６、２、３、１、０及び４を符号化する。本発明の範囲から逸脱せずに、他の変調技術が使用できる。例えば１６個の変調位置は、１６個の可能なデジタルコード値のうちの１つを符号化するために使用される。
【０１０７】
デジタルデータ記憶の数字の好適な順序付けは、図３２に示すようにドットの矩形配列を使用することにより提供される順序付けである。この順序付けは、一番上の最も左側のグリッドセル３２０１から開始し、一番下の最も右側のグリッドセル３２０２に到達するまで左から右及び上から下に進む。当然、他の順序付けが使用可能である。
【０１０８】
一実現例において、データの２つのチャネルが１つのバーコードに同時に格納される。データは、グリッド全体にわたり繰り返しタイリングされる。図３３に、単一の固有のタイル３３００及び使用されるタイリング構成を示す。バーコードは、冗長性のためにグリッド全体にわたり繰り返しタイリングされる。論理的には、各バーコードタイルは、高データ密度（本明細書では「ＨＤＤ」と呼ぶ）チャネル及び低データ密度（本明細書では「ＬＤＤ」と呼ぶ）チャネルの２つの別個のデータチャネルからのデータを表す。ＨＤＤチャネルは低いロバスト性を有し、ＬＤＤチャネルは高いロバスト性を有する。空間的には、バーコードタイル３３００は、本明細書ではＨＤＤチャネルタイルと呼ばれる４つのサブタイル３３０１、３３０２、３３０３及び３３０４から構成される。ＨＤＤチャネルタイルは、グリッドセル又はデータ搬送ドットの単位で３３１４（本明細書では「ＨＤＤタイルサイズ」と呼ばれる）の大きさを有する正方形グリッドである。各ＨＤＤチャネルタイルは、本明細書ではＬＤＤチャネルタイルと呼ばれる１つのより小さな埋め込みタイルを含む。バーコードタイルのＬＤＤチャネルタイルは、３３０５、３３０６、３３０７及び３３０８である。これは、バーコードタイル３３００がＬＤＤチャネルタイルの４つのコピーを含むことを意味する。
【０１０９】
各ＬＤＤチャネルタイルは、グリッドセル又はデータ搬送ドットの単位で３３１３（本明細書では「ＬＤＤタイルサイズ」と呼ばれる）の大きさを有する正方形グリッドである。更にＨＤＤチャネルは、ＬＤＤチャネルタイルを除く４つのＨＤＤチャネルタイルの領域全体を占有する。これは、バーコードタイルがＨＤＤチャネルの単一のコピーのみを含むことを意味する。例えば、領域３３０９、３３１０、３３１１及び３３１２は共にＨＤＤチャネルを構成する。ＨＤＤチャネルを格納するために使用されるＨＤＤチャネルタイルの数は、必要に応じて拡張可能である。現在、バーコードタイル３３００はＨＤＤチャネルタイルの２×２の構成を使用しているが、これを次に大きな構成、ＨＤＤチャネルタイルの３×３の構成に拡張可能である。尚、このタイリング方式は使用されるＨＤＤチャネル構成に依存しないＬＤＤチャネルタイルの一定の密度を維持し、それにより高い冗長性のロバストなＬＤＤチャネルを提供する。誤り訂正符合（ＥＣＣ）は、ＬＤＤチャネル及びＨＤＤチャネルの何れか又は双方のデータに適用される。一実施形態は、当該技術において周知の高性能ＥＣＣである低密度パリティチェック（ＬＤＰＣ）コードを使用する。
【０１１０】
［復号化処理］
図３４は、バーコード復号化のための方法の中間の段階を示すフローチャートである。復号化はステップ３４０１で開始する。第１段階「バーコードの走査」３４０２は、光学式スキャナを使用して紙のバーコードをデジタル走査済画像に変換する。尚、紙のバーコードは複数のバーコードを含むことができ、これは後の復号化段階により正確に処理される。３４０２の出力は走査済画像である。
【０１１１】
第２段階「ドットの検出」３４０３は、走査済画像においてバーコードのドットと考えられる全てのドットの場所を特定／検出するためにヒューリスティックを使用する。３４０３の出力は、場所が特定された大量のドットの中心の（ｘ、ｙ）画素座標のリストである。
【０１１２】
第３段階「一群の検出」３４０４は、ヒューリスティックアルゴリズムを使用して局所的なグリッド間隔及び向きを識別する（一群の検出）。
【０１１３】
第４段階「フラッドフィリング」３４０５は、優先度に基づくフラッドフィルアルゴリズムを使用して場所が特定されたドットのリストにわたり適切なグリッドを適合させる。一般的な例において、３４０４の出力は走査済画像を範囲に含む単一のグリッドである。特定の例において、種々の間隔及び向きの複数のグリッドが走査済画像を範囲に含むことが判明する。例えば、走査済画像が別個であり、異なる間隔又は異なる向きを有する２つ以上のバーコードを含む場合、検出されたバーコード毎に別個のグリッドが出力される。
【０１１４】
第５段階「領域の発見」３４０６は、段階３４０５からの各グリッドに対して動作し、セグメンテーションアルゴリズムを使用してデータ類似性に基づいてグリッドを別個の領域に分割する。一般に、３４０６の出力はグリッドを範囲に含む単一の領域である。特定の例において、複数の領域が発見される。例えばグリッドが「グリッドナビゲーション」により正常に分離されなかった２つのバーコードを含む場合、その２つのバーコードはこの段階で２つの領域に正確に分離され、２つの領域が出力される。
【０１１５】
第６段階「タイルの集約」３４０７は、各領域の繰り返しタイルを単一のタイルに圧縮する。繰り返しタイルのサイズ（図３３の３３１２）は自己相関により見つけられ、領域のタイルは単一のタイルにまとめられる。この集約されたタイルは３４０７の出力である。
【０１１６】
第７段階「ＥＣＣ復号化」３４０８は、集約タイルをＬＤＤチャネル及びＨＤＤチャネルに直列化することによりＥＣＣ復号化を実行し、誤り訂正符合を使用して任意のエラーを訂正し、バーコードデータを抽出する。３４０８の出力は、ＬＤＤデータ及びＨＤＤデータである。
【０１１７】
処理は３４０９で終了する。
【０１１８】
［一群の検出］
次に、図３４の一群の検出ステップ３４０４を更に詳細に説明する。図１２に、データ搬送ドット１２０１及び配置ドット１２０２の配列方法の一例を示す。基準グリッド１２０３は、基準グリッド交点に位置付けられる配置ドットの位置により規定される。データ搬送ドットは、基準グリッド１２０３に関して変調される。本開示は、本明細書では、「一群」と呼ばれる配置ドット間に所定の幾何学的関係を有する配置ドットの構成又は基本クラスタを見つける効率的な解決策を提供する。図１２に示すように、基準方向１２０６に対する基準グリッド間隔１２０４及び基準グリッド角度（向き）１２０５が判定される。
【０１１９】
図１３に、好適な実施形態において使用される別のバージョンの配置を示す。領域１３１０は、５つのドット１３０１〜１３０５から構成される１つの種類の一群を示し、領域１３１１は、４つのドット１３０６〜１３０９から構成される一群を示す。
【０１２０】
図２３は、一群を検出する方法を示すフローチャート２３００である。ステップ２３０１が方法の開始である。ステップ２３０２によると、画像において任意の座標が選択される。画像は一群の検出が実行される所望の頻度に依存して任意のサイズのタイルに分割される。一例として、３２０×３２０画素のタイルサイズは、１４画素のグリッド間隔を有する６００ｄｐｉのＡ４ページに対して有用である。ステップ２３０２において、それらのタイルのうちの１つの中心座標は、任意の座標として選択される。ステップ２３０３において、その任意の座標に最近接する複数のドット（この例においては、１０個のドット）が選択され、一群の検出を実行する。一例として、図１４において、任意の座標１４１１が画像において選択される。領域１４１２は、配置ドットであるか又はデータ搬送ドットであるかに関わらず点１４１１に最近接する１０個のドットを含む。この例において、ドット１４０１〜１４０６は配置ドットであり、ドット１４０７〜１４１０はデータ搬送ドットである。ステップ２３０４において、２つのドットの組合せが１０個の最近接するドットから任意に選択される。回転点は、２つの選択されたドットの座標の重心に設定される。２つの選択ドットの座標は、ステップ２３０５において回転点を中心に９０度回転され、２つの対応する回転座標又は回転位置を生成する。図１５に示すように、ドット１５０１及び１５０２に対応する座標は、回転点を中心に時計回りに９０度回転され、対応する回転座標１５０３及び１５０４をそれぞれ生成する。
【０１２１】
図２３を再度参照すると、判断２３０６において、回転座標１５０３及び１５０４に近接するドットの存在が検査される。それらの回転座標からの誤差範囲内でドットの場所が特定される場合、即ちＹｅｓの場合、２つの選択されたドット及び場所が特定された２つのドットは、共に可能な配置を構成すると考えられる。ステップ２３０８は、可能な配置を構成するそれらの４つのドットの選択を示す。一例として、適切な誤差範囲は、１４画素のグリッド間隔に対して水平及び／又は垂直方向に最大１画素である。判断２３０６において、誤差範囲内の回転座標でドットの場所が特定されない場合、即ちＮｏの場合、判断２３０７に進む。判断２３０７において、ドットの全ての対が使用された場合、即ちＹｅｓの場合、処理はステップ２３１２で終了する。あるいは、ドットの少なくとも１つの対が選択されてない場合、即ちＮｏの場合、ステップ２３０４においてドットの次の対を使用して処理が繰り返される。１０個のドットの場合、これは最大、行列式［１０ ２］又は４５回の可能な繰り返しが存在する。最近接する１０個のドットが選択されたが、本発明の趣旨から逸脱せずに異なる数の最近接するドットを使用できる。更に、ドットの対を選択する処理は任意である必要はない。最大数の繰り返しまで実行する必要がある計算時間を最小限にするために、一実現例において、任意の座標１４１１に近いドットが遠いドットより先に対にされる。
【０１２２】
一実施形態は、不適切な配置が検出されないことを保証するために更なる検査を利用する。不適切な配置が検出される可能性のある一般的な例を示すために、図１６を考慮する。ドット１６０１、１６０２、１６０３及び１６０４は不適切な配置を形成し、それらドットは不適切なグリッド間隔及び角度を結果として与える。ドット１６０１、１６０２、１６０３及び１６０４は、正確な配置より√２倍大きい不適切な配置を形成する。この無効な配置は、基準方向１６２０に対して４５度ではなく０度の角度を返す。正確な配置は、ドット１６０３、１６０４、１６０５及び１６０６から構成される配置である。図２３の判断２３０９において、ドット１６０５〜１６１３の存在は、対応するグリッド交点に近接して存在することを検査される。対応するグリッド交点から誤差範囲内で見つけられるドット数が第１の事前定義済み閾値カウントより少ない場合、即ちＹｅｓの場合、可能な配置を構成するドット１６０１〜１６０４は正確な配置を形成すると考えられ、ステップ２３１０が実行される。一例として、７つのドットの第１の閾値カウントは、可能な配置が正確であるか否かを判定する際に使用するのに適する。その結果、図２３のステップ２３１０は、ドット１６０３〜１６０６を選択することにより形成される正確な配置を見つける。
【０１２３】
ステップ２３０９が配置を検出できない場合、即ちＮｏの場合、ステップ２３１１が実行され、可能な配置を構成する４つのドットが正確な配置を実際に形成するかを更に検証する。図１７に示すように、ステップ２３０５からの可能な配置を構成するドットがドット１７０１〜１７０４である場合、ドット１７０５〜１７１３は、対応するグリッド交点に近接して存在するかが検査される。対応するグリッド交点から誤差範囲内で見つけられたドット数が第２の事前定義済み閾値カウントより少ない場合、即ちＮｏの場合、処理はステップ２３１２で終了する。第２の閾値カウントより多くのドットが存在する場合、即ちＹｅｓの場合、可能な配置を構成する４つのドット１７０１〜１７０４の集合は正確な配置を形成すると考えられ、ステップ２３１０が実行されて、ドット１７０１〜１７０４を正確な配置として選択する。処理は、ステップ２３１２で終了する。
【０１２４】
別の実施形態において、配置は、図１８に示される方法を使用して検出される。図１８に位置決めドット１８０１及びデータ搬送ドット１８０２を示す。この例において、方法は任意のドット１８０３を取得し、４つの最も近接する隣接ドット１８０４〜１８０７が選択される。回転点は、ドット１８０４〜１８０７に対して計算される。図１９に示すように、選択されたドット１８０４〜１８０７の重心である回転点１９０４が計算される。４つの選択されたドットの座標は、回転点１０９４を中心に９０度回転され、図１９の図１９０３に示すように４つの対応する回転座標１９０５〜１９０８を生成する。回転座標１９０５〜１９０８に近接するドットの存在が検査される。対応する回転座標から誤差範囲領域１９０９〜１９１１内でドットの場所が特定される場合、４つの選択されたドットは、可能な配置を構成すると考えられる。一般的な規則として、誤差範囲は、１４画素のグリッド間隔に対して水平及び／又は垂直方向に１画素の偏差と考えられる。可能な配置は、対応する回転座標の誤差範囲領域内にあることが判明した多くのドットに基づいて正確であると考えられる。一例として、４つのドットの場所が全ての４つの対応する回転座標から誤差範囲内で特定されるという厳密な検査が必要とされる。偽肯定的な例を減少するために、更なる検査がこれに追加される。実際に利用される検査数は、特定の応用例に依存する。
【０１２５】
別に実施形態において、図２０に示すように、任意のドット２００１が無作為に選択される。ドット２００１から８つの最近接する隣接ドット２００２〜２００９が選択され、ドットの集合を形成する。それら８つの最近接する隣接ドット２００２〜２００９の座標は、任意のドット２００１を中心に時計回り又は反時計回りに９０度回転され、回転座標２０１２〜２０１９の集合を形成する。回転座標２０１２〜２０１９に近接するドットの存在が検査される。ドットの場所が誤差範囲領域２１０１〜２１０４として図２１に示される対応する回転座標からの誤差範囲領域内で特定される場合、４つの隣接ドット２００３、２００５、２００７及び２００９、並びに任意に選択されたドット２００１は可能な一群を構成すると考えられる。可能な一群は、対応する回転座標の誤差範囲領域内にあることが判明した多くのドットに基づいて有効であると考えられる。一例として、検査は、４つのドットの場所が対応する回転座標から誤差範囲内で特定されることを要求する。図２０を再度参照すると、オーバラップするドットの数が４つである場合、５つのドット２００１、２００３、２００５、２００７及び２００９は、基準グリッドの基本的な一群と考えられる。一般に、データ搬送ドット２００２、２００４、２００６、及び２００８の位置は無作為に置かれるが、ドットの場所が誤差範囲又は回転座標内で特定されることが可能である。従って、９０度、１８０度及び２７０度を含む他の角度の回転により、更なる検査は必要とされても良い。
【０１２６】
別の実施形態として、図２２に、一群を形成するドット２２０３〜２２０６を含む標準三角形グリッドを示す。任意の点２２０９が画像において選択され、点２２０９に最近接する８つのドット２２０３〜２２１０が選択される。８つの選択されたドット２２０３〜２２１０のうち任意の２つのドット、例えば２２０３及び２２０４が選択される。ドット２２０３の座標は、座標２２０６を計算するためにドット２２０４の座標を中心に時計回りに６０度回転され、ドット２２０３の座標は、座標２２０５を計算するために時計回りに１２０度回転される。誤差範囲内にある座標２２０６及び２２０５におけるドットの存在が検査される。ドット２２０３〜２２０６から構成される可能な一群は、ドットが対応する回転座標２２０５及び２２０６の誤差範囲領域内にあると判明するかに基づいて正確であると考えられる。この処理は、一群が検出されるまで又は全てのドットの対が検査されるまで８つの選択されたドット２２０３〜２２１０のうち、ドットの全ての可能な対に対して繰り返される。偽肯定的な例を減少するために更なる検査がこれに追加されることは、当業者には理解されるだろう。利用される検査数は、実際の応用例に依存する。
【０１２７】
上述の実施形態は座標の９０度の回転を使用し、これは単純にｘ座標とｙ座標とを入れ替え、ｙ座標を反転することにより達成される。更に、所定の座標から誤差範囲内のドットの存在の検査は効率的な方法である。従って、この一群の検出方法は最小の計算能力を使用する。
【０１２８】
図３４のステップ３４０４において正確な一群を検出した場合、グリッド間隔及び角度、並びに一群を構成する座標又はドットは、配置ドットにより形成されるグリッド全体を検出するための開始点として使用される。これを行うことにより、全ての配置ドットはデータ搬送ドットから分離される。
【０１２９】
［フラッドフィルによるバーコードナビゲーション］
［グリッドナビゲーション方法の概要］
フラッドフィルによるグリッドナビゲーションの方法は、図３４のステップ３４０５において採用される。次に、このステップを更に詳細に説明する。
【０１３０】
グリッドナビゲーション方法の１つの面は、文書において検出された全ての印刷マークの集合の中で配置マークを識別し、配置マークを１つ以上の標準グリッド上に置くことである。正方形グリッドが一実施形態において使用されるが、方法は他の標準グリッドに対しても容易に適応可能である。
【０１３１】
本開示の１つの態様は、配置マーク及びデータマークから構成されるバーコードを印刷文書において検出する目的で基準グリッドを検出する方法を提供する。ここで、データマークは情報を符号化するために使用され、配置マークはデータマークの配列に対する基準グリッドを規定するために使用される。配置マーク及びデータマークは、そのように使用されない場合は視覚的に区別不可能である。方法は、印刷文書の少なくとも１つの場所において開始位置、間隔及び向きを推定することと、当業者には周知のフラッドフィル方法の変形した方法を使用して配置マークを追跡することとを含む。
【０１３２】
フラッドフィルによるグリッドナビゲーションの方法は、図３４のステップ３４０３及び３４０４の結果を使用する。特に、ステップ３４０３の結果は、特に配置マーク及び任意の他の検出マークを含む全ての検出マークの画像座標の集合である。配置パターンを形成するマークのみが本開示の方法により使用される。或いは、必要に応じて、提供される公称位置のすぐ近くにあるマークの存在を検出するための手段が提供される。
【０１３３】
ステップ３４０４の結果は、少なくとも１つのシード点の集合であり、各シード点に供給される情報は、ステップ３４０４において有効な配置マークとして識別された少なくとも１つのマークの画像座標と、それら画像座標におけるグリッド角度及び間隔の推定値とを含む。或いは、必要に応じてシード点を検出するための手段がステップ３４０４において提供される。シード点の数は、性能と正確度との間の妥協である。
【０１３４】
方法の結果は１つ以上のグリッドデータ構造の集合であり、各グリッドデータ構造はグリッドノードの集合を含む。各グリッドノードは、グリッドのノードの位置と関連付けられる画像座標を格納する。
【０１３５】
方法は２つの連続した段階で動作する。即ち、初期化段階の後にグリッド成長段階が続く。初期化段階中、グリッドデータ構造はステップ３４０４の結果を使用して初期化される。グリッド成長段階中、フラッドフィル又はシードフィル方式として当該業界において周知の方法と同様の方法で、配置マークは識別され、新しいグリッドノードは１つずつグリッドに追加される。新しいグリッドノードが評価及び追加される順序は、ノードが実際に有効な位置決めノードである信頼度の尺度により判定される。更に、新しいノードを追加することにより、２つのグリッドがオーバラップするかを確認するために検査が繰り返し毎に行われ、オーバラップしたグリッドを組み合わせる試みが行われる。
【０１３６】
［データ構造］
本開示の方法により使用されるデータ構造は、グリッドリスト、優先度キュー及び区域配列を含む。
【０１３７】
グリッドリストは、グリッドデータ構造の集合である。各グリッドデータ構造は、追跡される処理におけるグリッドの１つの接続部分を表す。各グリッドデータ構造と関連する情報は、グリッド角度及び間隔、並びにグリッド座標によりアクセス可能なグリッドノードの集合を含む。各グリッドノードと関連する情報は、ノードと関連する画像座標と、そのノードと関連する有効なマークが見つけられたことを示す指示と、ノードが優先度キューを介して処理されたことを示す別の指示とを含む。グリッドノードを親グリッドデータ構造と関連付けるための手段が更に提供される。
【０１３８】
優先度キューは、関連する信頼度値を伴うグリッドノードの集合である。優先度キューは、新しいノードを追加し且つ最も信頼度の高いノードを除去する効率的な動作をサポートする。
【０１３９】
区域配列は、オーバラップしたグリッドを検出する目的で画像上の特定の領域を占有しているグリッド（存在する場合は）を識別するために使用される補助データ構造である。画像は、同等のサイズのオーバラップしない矩形領域、即ち区域に論理的に分割される。各区域は、特定のグリッドにより請求されてもされなくても良い。各区域の大きさは、実現可能な限り小さい必要があるが、予想される最大のグリッドセルの大きさより小さくないのが好ましい。方法の本実施形態はサイズ３２×３２画素の区域を使用するが、他の区域が同様に実現されても良い。
【０１４０】
データ構造の選択は、単純さ、性能及びメモリの必要条件間の種々の妥協を反映する。他のデータ構造が同一の効果に対して使用されてもよいことは、当業者には認識されるだろう。
【０１４１】
［グリッドナビゲーション方法の詳細な説明］
図２４は、フラッドフィルによるグリッドナビゲーションの方法を示すフローチャート２４００である。まず初期化段階がステップ２４０１、２４０２及び２４０３で実行され、次にグリッド成長段階がステップ２４０４、２４０５、２４０６で実行される。
【０１４２】
ステップ２４０１において、内部データ構造は以下のように初期化される。即ち、グリッドリストは空に設定される。優先度キューは空に設定される。区域配列の各区域は未請求に設定される。
【０１４３】
ステップ２４０２において、以下に更に詳細に説明するように、シード点の向きが正規化される。
【０１４４】
ステップ２４０３において、初期グリッドはシード点から作成され、優先度キューが事前にポピュレートされる。以下の動作は各シード点に対して行われる。
【０１４５】
新しいグリッドデータ構造は作成され、グリッドリストに追加される。グリッドの向き及び間隔は、シード点の向き及び間隔から初期化される。
【０１４６】
新しいグリッドノードは、グリッドの原点において新しいグリッドデータ構造に追加される。グリッドノード画像座標は対応するシード点座標に設定され、ノードは関連するマークを有するものとして印をつけられる。本明細書において更に後述するように、新しく作成されたノードは評価され、優先度キューに条件付きで追加される。
【０１４７】
方法のメインループは、ステップ２４０４、２４０５及び２４０６により表される。ステップ２４０４において、方法は、キューが空であるかを検査する。キューが空である場合、即ちＹｅｓの場合、方法は終了ステップで終了する。キューが空でない場合、即ちＮｏの場合、ステップ２４０５に進み、最上部のノードを選択する。最も信頼度の高いノードは、ステップ２４０５においてキューから除去され、ステップ２４０６において処理される。その後ステップ２４０４に戻り、処理は、ステップ２４０４において判定されるようにキューが空になるまで繰り返す。
【０１４８】
［角度の正規化］
図３４のステップ３４０４において推定されるグリッドの角度は、グリッドの回転対称性のために固有の曖昧さを有する。性能の理由のために、角度差が同様に配向されるグリッドに対して小さくなるように角度を正規化するのが望ましい。特に、特定のANGLE_TOLERANCE定数は、同様であると考えられるグリッドに対する向きの角度差の上限を規定するために使用される。ANGLE_TOLERANCEの適切な値は、実験的に判定される。本実施形態のANGLE_TOLERANCEの値は０．０２ラジアンに設定される。
【０１４９】
角度の正規化の処理は、図２４のステップ２４０２で行われ、図２５を参照して更に詳細に示す。図２５は、グリッドの角度の正規化の方法を示すフローチャート２５００である。
【０１５０】
ステップ２５０１において、全てのシード点に対するグリッドの角度は、９０度を法とすることにより０〜９０度の範囲になる。
【０１５１】
ステップ２５０２において、グリッドの角度のヒストグラムは、全ての利用可能なシード点に対するデータを使用して作成／構築される。ヒストグラムビンの大きさは、ANGLE_TOLERANCE定数の値に設定される。
【０１５２】
ステップ２５０３において、境界の角度の値は、最小のカウントを有するビンの中心値であるとして判定／選択される。
【０１５３】
ステップ２５０４において、全てのシード点に対するグリッドの角度は、境界の角度から境界の角度＋９０度までの範囲になる。これは、向きの角度が境界の角度より小さい場合は常に前記角度に９０度を加算することにより達成される。
【０１５４】
角度の正規化のステップはオプションである。このステップが省略される場合、図２７のステップ２７０５においてオーバラップしたグリッドを検査する際にグリッドの向きが比較される時に曖昧さが解決される必要がある。
【０１５５】
［グリッドノードの評価］
グリッドノード評価ステップの間に、現在のノードの任意の欠落する隣接ノードが作成され、ノードの信頼度が計算され、ノードは優先度キューに条件付きで追加される。信頼度は、ノード自体及び現在のノードの全ての隣接ノードに対する距離計測値の合計として計算される。
【０１５６】
現在のノードに対して、距離計測値は、ノードが関連するマークを有する場合はMAX_DISTに設定され、有さない場合はゼロに設定される。隣接ノードに対しては、距離計測値は以下のように計算される。
【０１５７】
隣接ノードが関連するマークを有さない場合、計測値はゼロである。有する場合、計測値は、マークの実際の位置と予想される位置との距離の平方よりMAX_DIST少ない。結果が負数である場合、計測値はゼロに設定される。
【０１５８】
MAX_DIST定数は、マークの実際の位置と予想される位置との間で平方された最大許容距離を示す。一実施形態において、MAX_DISTの値は９であり、これは３画素の最大距離に対応する。
【０１５９】
信頼度を計算する他の方法が可能であることは、当業者には認識されるだろう。選択は、正確度と性能との間の技術的妥協により判定される。特に、計算はマークの大きさ及び形状、グリッドの他の位置決めマークの位置等に関する情報を含んでも良い。
【０１６０】
図２６は、グリッドノードの評価の方法を示すフローチャート２６００である。まずステップ２６０１において、信頼度値は、現在のノードが関連するマークを有さない場合はゼロに初期化され、有する場合はMAX_DISTの値に初期化される。その後ステップ２６０２〜２６１２は、全てのグリッド方向に対して繰り返される。矩形グリッドの場合、４つの方向、即ち上方向、下方向、左方向及び右方向が評価される。
【０１６１】
現在のグリッドの方向は、ステップ２６０２において選択される。ステップ２６０３において、マークの予想される位置は、現在のグリッド方向に従ってグリッド変位ベクトルを回転し、それを現在のノードの位置に追加することにより計算される。グリッド変位ベクトルは、グリッド間隔により乗算され且つグリッドの角度分回転される単位ベクトルとして計算される。効率化のために、グリッド変位ベクトルは事前に計算され、各グリッドデータ構造に格納されても良い。
【０１６２】
ステップ２６０４において、現在の方向の隣接ノードの存在に対する検査がグリッドデータ構造において行われる。隣接ノードが作成されていない場合、即ちＮｏの場合、ステップ２６０５〜ステップ２６０９において新しいノードを作成する試みが実行される。まずステップ２６０５において、予想されるノード座標が画像範囲と比較される。座標が画像範囲外である場合、現在の方向に対して更なる動作は実行されず、ステップ２６１２に進む。ステップ２６０５において、座標が画像範囲内にある場合、即ちＹｅｓの場合、ステップ２６０６において、新しいノードが作成され且つ予想される位置で初期化される。ステップ２６０７において、予想される位置に最近接するマークの場所が特定される。ステップ２６０８において、マークの距離計測値が検査される。計測値がゼロ以下である場合、即ちＹｅｓの場合、マークは遠すぎると考えられ、このノードに対して更なる動作は実行されず、ステップ２６１２に進む。距離計測値がゼロ以下でない場合、即ちＮｏの場合、ステップ２６０９において、ノードは関連するマークを有するものとして印がつけられ、ノードの位置は現在のマークの位置で更新される。ステップ２６１０において、信頼度は計測値分増加される。
【０１６３】
ステップ２６０４においてノードが見つけられる場合、即ちＹｅｓの場合、ステップ２６１１において、ノードは関連するマークの存在について更に検査される。存在する場合、即ちＹｅｓの場合、上述のように、ステップ２６１０において信頼度は更新される。ステップ２６１１において、ノードが関連するマークを有さないことが判明した場合、即ちＮｏの場合、ステップ２６１２に進む。
【０１６４】
ステップ２６１２は、全ての方向が処理されたかを判定する。全ての方向が処理されていない場合、即ちＮｏの場合、ステップ２６０２に戻る。ステップ２６１２において判定されるように、全てのグリッド方向が処理されると、即ちＹｅｓの場合、ステップ２６１３に進む。結果として得られる信頼度はステップ２６１３で検査される。信頼度がゼロより大きいことが判明した場合、即ちＹｅｓの場合、ステップ２６１４において、信頼度と共にノードは優先度キューに追加される。その後終了ステップに進み、方法は終了する。信頼度がゼロより大きくない場合、即ちＮｏの場合、終了ステップに進み、方法は終了する。
【０１６５】
［最も信頼度の高いノードの処理］
最も信頼度の高いノードの処理は、図２４のステップ２４０６において行われ、図２７に更に示される。図２７は、高信頼のグリッドノードの処理の方法を示すフローチャート２７００である。
【０１６６】
まずステップ２７０１、２７０２、２７０５及び２７０６において、グリッドをマージする特定の例が検査され、影響を受ける。ステップ２７０１において、区域配列は、現在のノードの位置において調査される。区域所有者が現在のグリッドと同一である場合、即ち「同一」の場合、特別な動作は行われず、ステップ２７０３に進む。ステップ２７０１において区域が請求されていない場合、即ち「未請求」の場合、ステップ２７０２において区域の所有者は現在のグリッドに設定され、ステップ２７０３に進む。ステップ２７０１において区域の所有者が現在のグリッドと異なる場合、即ち「相違」の場合、ステップ２７０５及び２７０６においてグリッドに参加する試みが実行される。
【０１６７】
ステップ２７０５において、２つのグリッド、即ち現在のノードのグリッド及び現在のノードの位置の区域所有者の互換性が検査される。向きの差がANGLE_TOLERANCEより小さく、間隔の差がSPACING_TOLERANCEより小さい場合、グリッドは互換性があると考えられる。SPACING_TOLERANCEは実験的に判定される定数であり、本実施形態において使用される値は１．５画素である。
【０１６８】
ステップ２７０５において否定的な結果である場合、即ちＮｏの場合、終了ステップに進み、方法は終了する。ステップ２７０５において肯定的な結果である場合、即ちＹｅｓの場合、以下のようにステップ２７０６において、グリッドはマージされる。
【０１６９】
まず、変位ベクトルは、第２のグリッドの原点から第１のグリッドの原点を減算することにより計算される。グリッド座標のオフセットは、前記変位ベクトルの座標を第１のグリッドの角度だけ回転し、その結果を第１のグリッドの間隔で除算し且つ結果を最も近い整数値に四捨五入することにより計算される。
【０１７０】
グリッドのオフセットが計算された後、第２のグリッドの全てのノードは第１のグリッドに転送され、第２のグリッドはグリッドリストから除去される。第１のグリッドのノードの位置は、第２のグリッドのノードの位置にグリッドのオフセットを加算することにより判定される。それと同時に、第２のグリッドにより所有されているとして区域配列において印をつけられた区域は、第１のグリッドにより所有されているとして再度ラベル付けされる。
【０１７１】
同一のノードの複製の作成を回避するために、現在のノードの更なる処理はスキップされる。ステップ２７０６から終了ステップに進み、方法は終了する。
【０１７２】
ステップ２７０３において、現在のノードの隣接ノードは、全てのグリッド方向に対して評価される。ノードが存在し、処理されたものとして印がつけられていない場合、そのノードは図２６に関して上述したように評価される。
【０１７３】
ステップ２７０３からステップ２７０４に進み、現在のノードは処理されたものとして印がつけられる。ステップ２７０４から終了ステップに進み、方法は終了する。
【０１７４】
［更なる実施形態］
本明細書において、デジタルデータ及びデジタルデータの保護のための関連する誤り訂正符号（ＥＣＣ）データを含む情報マークの正確な向きを判定する方法が開示される。ＥＣＣの復号化は情報マークの１つの可能な向きに対して試行され、ＥＣＣ復号化が失敗した場合、情報マークの異なる可能な向きが採用されて、ＥＣＣの復号化が再度試行される。
【０１７５】
本明細書において、画像中の位置決めマーク／ドットにより形成される基準グリッドの基本的な一群を検出する方法及びシステムが更に開示される。このグリッドは、間隔及び向きに対して種々の所定の値を有することができ、データ搬送ドットはグリッドに関して変調される。基本的な一群は、配置ドットのみを構成し、配置ドットはデータ搬送ドットと分離される必要がある。基本的な一群の検出により、グリッドの間隔及び向きが識別され、一実現例において、これは基準グリッド全体を拡張及び検出するための次の段階で使用される。
【０１７６】
本明細書において、印刷文書の配置マークを追跡する方法及びシステムが更に開示される。配置マークは、グリッド状のパターンを形成する。本開示の１つの態様によると、印刷文書の他のマークに関係なく基準グリッドを検出する方法が提供される。
【０１７７】
本開示の１つの態様によると、基準グリッドの部分であるドットの一群を検出する方法が提供される。方法は、画像において任意の座標を選択するステップと、選択した座標に最近接する複数のドットを選択するステップと、選択した最近接するドットから２つのドットを選択するステップと、選択した２つのドットを９０度回転して回転位置を判定するステップと、回転位置のドットを検査するステップと、回転位置周辺の誤差範囲内のドットを検査するステップと、複数のドットを一群として選択するステップとから成る。一実施形態において、選択した最近接するドットは８つ存在する。
【０１７８】
本開示の別の態様によると、基準グリッドの部分であるドットの一群を検出する方法が提供される。方法は、選択したドット及び選択したドットの４つの最近接する隣接ドットを含むドットの元の集合を選択するステップと、回転集合を生成するために回転の中心に関して４つのドットを回転するステップと、元の集合及び回転集合のオーバラップするドットを検査するステップと、複数のオーバラップするドットに基づいてドットの基本的な一群を選択するかを判定するステップとから成る。
【０１７９】
本開示の更なる態様によると、基準グリッドの部分であるドットの一群を検出する方法が提供される。方法は、ドットを選択し、ドットの元の集合を形成するために選択したドットの８つの最近接する隣接ドットを選択するステップと、ドットの回転集合を生成するために選択したドットを中心に８つの最近接する隣接ドットを回転するステップと、ドットの元の集合とドットの回転集合との間でオーバラップするドットを検査するステップと、オーバラップするドットの数に基づいてドットの基本的な一群を選択するかを判定するステップとから成る。一実施形態において、一群は基準グリッドの形状に依存する幾何学的形状である。別の実施形態において、グリッドは種々の所定のグリッド間の距離及び向きを有する。更なる実施形態において、一群のドット数は変動する。更に別の実施形態において、ドットの形状及び大きさのうち少なくとも一方は変動する。
【０１８０】
本開示の更に別の態様によると、ドットの回転集合を見つけるために、選択した位置を中心に事前定義済みの角度分複数のドットを回転する方法が提供される。方法は、画像において点を選択し、その点の周囲にあり且つドットの元の集合を形成する複数のドットを事前定義済みの規則に基づいて選択することと、事前定義済みの規則に従って回転の中心を計算することと、ドットの回転集合を形成するために回転の中心に関して選択したドットを回転することとから成る。一実施形態において、ドットの元の集合及びドットの回転集合は比較され、オーバラップするドットを見つけ、特定の幾何学的パターンを検出する。
【０１８１】
本開示の別の態様によると、配置マーク及びデータマークから構成されるバーコードを印刷文書において検出する目的で基準グリッドを検出する方法が提供される。データマークは情報を符号化するために使用され、配置マークはデータマークの配列に対して基準グリッドを規定するために使用される。配置マーク及びデータマークは、そのように使用されない場合は視覚的に区別不可能である。方法は、印刷文書の少なくとも１つの場所において開始位置、間隔及び向きを推定するステップと、フラッドフィル方法の変形した方法を使用して配置マークを追跡するステップとから成る。一実施形態において、マークが処理される順序は、マークが有効な配置マークである信頼度の尺度により影響を受ける。別の実施形態において、信頼度の尺度は、他の配置マークに対するマークの位置に基づいて計算される。更なる実施形態において、２つ以上のグリッドは２つ以上の開始位置を使用して同時に追跡され、同様に配向されたオーバラップしたグリッドはマージされる。
【０１８２】
本開示の更なる態様によると、デジタルデータ及びデジタルデータの保護のための関連するＥＣＣデータを含む情報マークの正確な向きを判定する方法が提供される。方法は、情報マークの１つの可能な向きに対してＥＣＣの復号化を試みるステップと、ＥＣＣ復号化が失敗した場合、情報マークの異なる可能な向きを採用して、ＥＣＣの復号化を再度試みるステップとから成る。
【０１８３】
本開示の更に別の態様によると、画像中の低可視バーコード（ＬＶＢＣ）を復号化する方法が提供される。方法は、低可視バーコードを形成する複数のドットを検出するステップと、検出した各ドットと関連付けられる座標を格納するステップと、低可視バーコードのキャリア信号を形成する標準グリッドを識別するために格納された座標を解析するステップと、変調グリッドに対して向き及び間隔を判定するステップと、各ドットの位置に格納された情報を復調するステップと、低可視バーコードのメッセージデータの開始を判定するステップと、復号化メッセージをアセンブルするステップとから成る。
【産業上の利用可能性】
【０１８４】
上記構成がコンピュータ産業、データ処理産業、印刷産業及びイメージング産業に適用可能であることは、上述から明らかである。
【０１８５】
上述において、本発明のいくつかの実施形態のみを説明したが、本発明の趣旨の範囲から逸脱せずに変形及び／又は変更が可能である。それら実施形態は単なる例示であり、限定するものではない。
【０１８６】
本明細書において、用語「具備する」は、「主に含むが、単独で必要ではない」、「有する」又は「含む」ことを意味し、「〜のみから構成される」ことではない。用語「具備する」の語形変化は、それに対応して意味の変化を示す。
【図面の簡単な説明】
【０１８７】
【図１】低可視バーコード（ＬＶＢＣ）を印刷するのに適した機器を示す概略ブロック図である。
【図２】ＬＶＢＣをコンピュータにより読み取るのに適する機器を示す概略ブロック図である。
【図３】ドットが全て標準グリッド上にないように位相変調されたドットの配列を示す図である。
【図４】標準グリッド上に位置するドットの標準配列を示す図である。
【図５】ドットの変調を更に詳細に示す図である。
【図６】ドットの変調を更により詳細に示す図である。
【図７】ＬＶＢＣの数字の順序付けを示す図である。
【図８】ＬＶＢＣデータを符号化する方法を示すフローチャートである。
【図９】ＬＶＢＣデータを復号化する方法を示すフローチャートである。
【図１０】ＬＶＢＣの正確な向きを判定する方法を示すフローチャートである。
【図１１】説明する構成が実現されるコンピュータシステムを示す概略ブロック図である。
【図１２】基準グリッド及びデータ搬送ドットを示す図である。
【図１３】２つの異なる種類の基本的な一群を示す図である。
【図１４】一実施形態に係る一群を示す図である。
【図１５】９０度回転させる技術を示す図である。
【図１６】不適切な一群が選択されないことを保証するための追加の検査を示す図である。
【図１７】不適切な一群が選択されないことを保証するための別の追加の検査を示す図である。
【図１８】基本的な一群の検出を示す図である。
【図１９】別の実施形態に対して、回転及びオーバラップするドットを更に詳細に示す図である。
【図２０】一群を検出する別の実施形態を示す図である。
【図２１】図２０を参照して説明する実施形態に対して、回転及びオーバラップするドットを更に詳細に示す図である。
【図２２】三角形グリッドを含む別の実施形態を示す図である。
【図２３】基本的な一群を検出する方法を示すフローチャートである。
【図２４】フラッドフィルによるグリッドナビゲーションの方法を示すフローチャートである。
【図２５】グリッドの角度の正規化の方法を示すフローチャートである。
【図２６】グリッドノードの評価の方法を示すフローチャートである。
【図２７】高信頼のグリッドノードの処理の方法を示すフローチャートである。
【図２８】本開示の一実施形態に従ってバーコードのデータを符号化するために使用されるドットの変調グリッドを示す図である。
【図２９】復号化の目的でドットの変調グリッドを示す概念図である。
【図３０】データを単一のドットの変調に符号化する方法を示す図である。
【図３１】データを単一のドットの変調に符号化するために使用される符号化方式を示す図である。
【図３２】データ搬送ドットの復号化順序を示す図である。
【図３３】本開示の一実施形態に従ってバーコードに対して使用されるタイリング方式を示す図である。
【図３４】バーコードの復号化のための方法の中間の段階を示すフローチャートである。
【図３５】「グリッドナビゲーション」バーコード復号化段階の出力を示す図である。
【図３６】「領域の発見」バーコード復号化段階の出力を示す図である。
【図３７】「タイルの集約」バーコード復号化段階の出力を示す図である。
【図３８】説明する構成が実現されるコンピュータシステムを示す概略ブロック図である。
【技術分野】
【０００１】
本発明は、一般に印刷文書におけるマークを追跡することに関し、特に、グリッド状のパターンを形成する配置マークを追跡することに関する。更に本発明は、一般に誤り訂正符号を利用して透かしを検出することを含む透かし又は他のステガノグラフィパターンの向きを判定することに関する。また本発明は、一般に印刷文書上にグリッドの形式で存在している基本的な配置マークの一群を検出することに関する。
【背景技術】
【０００２】
印刷ページ上のコンピュータ読み取り可能なマークは普及しており、普通のバーコード等の種々のものが非常に広く使用されている。普通のバーコードが普及しているが、益々多くの別のコンピュータ読み取り可能なマークが市場に出ている。これらの新しい種々のマークの多くは、普通のバーコードより大きなデータ搬送能力を提供し、普通のバーコードに格納可能なデータが３０〜６０ビットであるという制限を伴う可能な応用例より更に広範の応用例を可能にする。他の種々のマークは、可視性を低減させて示すことで普通のバーコードを向上させ、人間が読み取り可能なコンテンツを含むように更に多くのページの部分が解放されているという利点を有する。低い可視性のマークの追加の利点は、情報がページに隠蔽されるため、ステガノグラフィ及び透かし等の応用例が可能になることである。
【０００３】
コンピュータ読み取り可能なマークが更に広く使用され、コンピュータ読み取り可能なマークに対する新しい応用例が見つけられるのと共に、ページの多くの領域を消費せずに大きいデータ容量を提供するマークの必要性が高まっている。そのようなマークにより、人間が読み取り可能なコンテンツを含むようにページの殆どが解放され、これは多くの応用例にとって望ましい。
【０００４】
画像から透かし又は他のステガノグラフを再生する場合、当然マークは見えず、無作為の向きで走査又はデジタル化されることが多いため、マークを読み取る正確な向きを判定するという課題が発生する。
【０００５】
ステガノグラフの正確な向きを判定する方法が多く開示されている。例えば、複数の１次元向き信号を画像に取り込み且つ後で検出するという方法である。豪州特許出願第２００２９５１８１５号（Canon Kabushiki Kaisha）において説明するように、それらの信号が人間の目に感知不能であるところまで弱く埋め込まれる場合でも、適切に配向された画像の投影は１次元キャリアの存在を示す。
【０００６】
豪州特許出願第２００５２０９７０９号（Canon Kabushiki Kaisha）において、向きの判定を助長するために所定の場所の固定ヘッダメッセージを使用するステガノグラフの別の形式が説明される。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
向き信号をステガノグラフに追加することは、可視性を増加する代わりに向きの迅速な判定を可能にする周知の技術である。可視性が最小限にされる必要があるステガノグラフを生成する場合、そのような向き信号の存在は望ましくない。
【０００８】
画像データの無許可のコピーを防止する方法がいくつか存在する。これらの方法は、通常、コピーされる画像において固定パターン又は印の場所を特定することに基づく。或いは、仮想グリッドに関してデータを符号化させる方法がいくつかある。固定の距離のグリッドを有する必要性をなくし、基準グリッドを検出し且つその基準グリッドをデータ搬送ドットと分離する更に高速な手法を提供する必要がある。更に、データ搬送マークを無視し且つグリッド状の基準パターンを形成するマークのみを選択的に評価することにより、基準グリッドを検出する更に高速な手法を提供する必要がある。
【課題を解決するための手段】
【０００９】
本明細書において、画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別する方法が開示される。一実施形態において、コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合である。
【００１０】
本開示の第１の態様によると、画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法が提供される。配置マークはコンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。方法は、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、選択したマークの各位置に関する回転の中心を判定するステップと、選択したマークの各々を回転の中心に関して所定の角度だけ回転することにより選択したマークに対する回転位置を判定するステップと、各回転位置に対して、回転位置から所定の閾値未満の位置を有するマークの場所をコンピュータ読み取り可能なマークの構成から特定するステップと、選択されたマーク及び場所を特定したマークを配置マークの一群として識別するステップとを含む。その後、方法は、データ搬送マークを復号化する際に使用するために識別された一群を格納する。
【００１１】
本開示の第２の態様によると、画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法であって、前記コンピュータ読み取り可能なマークの構成から選択される少なくとも２つのマークの少なくとも１つの組み合わせに対して、（ａ）前記組み合わせの前記選択されたマークの各位置に関する回転の中心を判定するステップと、（ｂ）前記選択されたマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記組み合わせの前記選択されたマークに対する回転位置を判定するステップと、（ｃ）各回転位置に対して、前記回転位置に最近接するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、（ｄ）前記回転位置のうち、少なくとも所定の割合の回転位置に対して前記回転位置に最近接する前記マークが前記回転位置から所定の閾値未満の位置にある場合、前記組み合わせの前記選択されたマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを含む。方法は、データ搬送マークを復号化する際に使用するために識別された一群を格納する。
【００１２】
本開示の第３の態様によると、走査済画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するように構成されたコピー機が提供される。配置マークはコンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。コピー機は、走査済画像を取得するスキャナと、コンピュータプログラムを格納する記憶装置と、コンピュータプログラムを実行するプロセッサとを含む。前記コンピュータプログラムは、前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、前記選択したマークの各位置に関する回転の中心を判定するステップと、前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを前記プロセッサに実行させる。
【００１３】
本開示の第４の態様によると、画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群が識別され、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法を実行するようにプロセッサに指示するためのコンピュータプログラムが提供される。方法は、前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、前記選択したマークの各位置に関する回転の中心を判定するステップと、前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有する。
【００１４】
本開示の別の態様によると、上述の方法のうち任意の１つを実現する装置が提供される。
【００１５】
本開示の別の態様によると、上述の方法のうち任意の１つを実現するコンピュータプログラムを記録したコンピュータ読み取り可能な媒体を含むコンピュータプログラム製品が提供される。
【００１６】
本開示の他の態様が更に開示される。
【００１７】
次に、図面を参照して、本発明の１つ以上の実施形態を説明する。
【発明を実施するための最良の形態】
【００１８】
任意の１つ以上の添付の図面において同一の図中符号を有するステップ及び／又は特徴を参照する場合、特に指示のない限り、それらのステップ及び／又は特徴は説明の目的で同一の機能又は動作を有する。
【００１９】
［概要］
本明細書において、画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するためのコンピュータにより実現される方法が開示される。例えば、画像は、スキャナ又はコピー機により取得される走査済画像又は印刷画像であっても良いが、それらに限定されない。一実施形態において、コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合である。例えばコンピュータ読み取り可能なマークは、ドット、円、正方形、三角形又は任意の所望の形状を形成するドット群を含んでも良い。コンピュータ読み取り可能なマークの構成は、配置マーク及びデータ搬送マークを含む。ここで、配置マークは、コンピュータ読み取り可能なマークの構成内で仮想基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。
【００２０】
方法は、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択し、選択したマークの各位置に関する回転の中心を判定する。選択した各マークを回転の中心に関して所定の角度だけ回転することにより、回転位置は選択したマークに対して判定される。方法は、各回転位置に対して、回転位置から所定の閾値未満の位置を有するマークの場所をコンピュータ読み取り可能なマークの構成から特定する。方法は、選択したマーク及び場所を特定したマークを配置マークの一群として識別し、データ搬送マークを復号化する際に使用するために識別された一群を格納する。一実施形態において、少なくとも２つのマークの更なる選択は、一群を識別するために行われる。
【００２１】
一実施形態において、方法は、識別された一群の間隔及び向きを判定することを含み、更に識別された一群の間隔及び向きに基づいて予想されるマークの場所の集合を判定することを含む。予想されるマークの場所のうち少なくとも所定の割合の場所がコンピュータ読み取り可能なマークの構成におけるマークの場所と一致すると、配置マークの識別一群が検証される。
【００２２】
別の実施形態において、配置マークによって規定される基準グリッドは矩形グリッドであり、２つのマークはコンピュータ読み取り可能なマークの構成から選択され、回転の中心を判定することは２つの選択したマークの間に位置付けられる点を識別することを含む。更なる実施形態において、基準グリッドは三角形グリッドであり、回転の中心を判定することは選択したマークのうちの１つを回転の中心として割り当てることを含む。更に、別の実施形態において、基準グリッドは六角形グリッド又は菱形グリッドである。
【００２３】
別の実施形態において、方法は、識別された一群を拡張して、判定した間隔及び向きに基づいてコンピュータ読み取り可能なマークの構成から追加のマークを組み込む。更に、別の実施形態において、方法は、識別された一群を利用して基準グリッドを識別し、識別した基準グリッドに基づいてコンピュータ読み取り可能なマークの構成においてデータ搬送マークを識別する。最後に方法は、識別したデータ搬送マークを復調し、データ搬送マークにより符号化されたデータを導出する。
【００２４】
本明細書において、画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するためのコンピュータにより実現される方法が更に開示される。例えば、画像は、スキャナ又はコピー機により取得される走査済画像又は印刷画像であっても良いが、それらに限定されない。一実施形態において、コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合である。例えばコンピュータ読み取り可能なマークは、ドット、円、正方形、三角形又は任意の所望の形状を形成するドット群を含んでも良い。コンピュータ読み取り可能なマークの構成は、位置決めマーク及びデータ搬送マークを含む。ここで、位置決めマークはコンピュータ読み取り可能なマークの構成内で仮想基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。
【００２５】
コンピュータ読み取り可能なマークの構成から選択される少なくとも２つのマークの少なくとも１つの組み合わせに対して、方法は、その組み合わせの選択されたマークの各位置に関する回転の中心を判定し、選択した各マークを回転の中心に関して所定の角度だけ回転することにより、その組合せの選択したマークに対する回転位置を判定する。方法は、各回転位置に対して、回転位置に最近接するマークの場所をコンピュータ読み取り可能なマークの構成から特定し、回転位置のうち少なくとも所定の割合の回転位置に対して、回転位置に最近接するマークが回転位置から所定の閾値未満の位置にある場合、組み合わせの選択したマーク及び場所を特定したマークを配置マークの一群として識別する。所定の閾値は、特定の応用例に依存する。方法は、データ搬送マークを復号化する際に使用するために識別された一群を格納する。
【００２６】
本明細書において、走査済画像中のコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するように構成されたコピー機が更に開示される。コンピュータ読み取り可能なマークの構成は、配置マーク及びデータ搬送マークを含む。ここで、配置マークはコンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、データ搬送マークはデータを符号化するために基準グリッドに関して変調される。コピー機は、走査済画像を取得するスキャナと、コンピュータプログラムを格納する記憶装置と、プログラムを実行するプロセッサとを含む。コンピュータプログラムは、コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するコードと、選択したマークの各位置に関する回転の中心を判定するコードと、選択した各マークを回転の中心に関して所定の角度だけ回転することにより選択したマークに対する回転位置を判定するコードと、各回転位置に対して、回転位置から所定の閾値未満の位置を有するマークの場所をコンピュータ読み取り可能なマークの構成から特定するコードと、選択したマーク及び場所を特定したマークを配置マークの一群として識別するコードとを含む。
【００２７】
本明細書において、上述の方法のうち、任意の１つを実行するようにプロセッサに指示するためのコンピュータプログラムを記録したコンピュータ読み取り可能な媒体を含むコンピュータプログラム製品が更に開示される。
【００２８】
［透かしの向きの判定］
本明細書においてＬＶＢＣと略される低可視バーコード（Low Visibility Bar Code）は、通常のプリンタ（レーザプリンタ又はインクジェットプリンタ等）を使用してページ上に印刷され且つ通常のデスクトップスキャナを使用してコンピュータにより読み取り可能な種々のコンピュータ読み取り可能なマークである。ＬＶＢＣマークは、１ページに数十、数百又は数千バイトものバイナリデータを含むために使用され、人間が読み取り可能なコンテンツを含むようにそのページの殆どを解放する。ＬＶＢＣマークは大量の冗長を含むように構成され、そのように構成された場合、ＬＶＢＣマークは折り曲げ、しわ、着色、破れ及び汚れに対して非常にロバストになる。
【００２９】
図１は、ＬＶＢＣを印刷するのに適する機器を示す概略ブロック図である。例えばMicrosoft Windows（登録商標）オペレーティングシステムを実行するＩＢＭ互換のＰＣであるパーソナルコンピュータ１０１は、通信ケーブル１０３を介してレーザプリンタ又はインクジェットプリンタ等のプリンタ１０２に結合される。プリンタ１０２は、１枚の紙１０７又は他の印刷媒体に印刷して、ハードコピー文書を提供できる。印刷されたデータはＬＶＢＣを含んでも良い。別の実施形態において、通信ケーブル１０３は、無線伝送リンクを使用して実現される。
【００３０】
図２は、ＬＶＢＣをコンピュータにより読み取るのに適する機器を示す概略ブロック図である。図２はCanon 9900Fデスクトップスキャナ等のスキャナ１０４を示し、スキャナ１０４は通信ケーブル１０５を介してパーソナルコンピュータ１０６に結合される。パーソナルコンピュータ１０６及び１０１は同一のコンピュータでも良く、或いは個別に動作可能であるか又は例えばコンピュータネットワークを介して接続される別個のコンピュータでも良い。機器は、例えばスキャナ１０４によりコンピュータ１０６に走査されたハードコピー文書上に存在するＬＶＢＣをコンピュータにより読み取るのに適する。別の実施形態において、通信ケーブル１０５は、無線伝送リンクを使用して実現される。
【００３１】
後述する符号化及び復号化の方法は、図１１に示すような汎用のコンピュータシステム１１００を使用して実現されるのが好ましい。ここで、図３〜図１０の処理は、コンピュータシステム１１００内で実行するアプリケーションプログラム等のソフトウェアとして実現されても良い。特に、符号化及び復号化のステップは、コンピュータにより実行されるソフトウェアの命令により行われる。命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されても良い。ソフトウェアは２つの別個の部分に分割されても良く、第１の部分は符号化及び／又は復号化方法を実行し、第２の部分は第１の部分とユーザとの間のユーザインタフェースを管理する。例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読み取り可能な媒体に格納されても良い。ソフトウェアは、コンピュータ読み取り可能な媒体からコンピュータにロードされ、コンピュータにより実行される。そのようなソフトウェア又はコンピュータプログラムを記録したコンピュータ読み取り可能な媒体はコンピュータプログラム製品である。コンピュータプログラム製品をコンピュータにおいて使用することにより、データを文書に取り込むための有利な装置を達成するのが好ましい。
【００３２】
コンピュータシステム１１００は、コンピュータモジュール１１０１と、キーボード１１０２、マウス１１０３及びスキャナ１１１８等の入力装置と、プリンタ１１１５、表示装置１１１４及びスピーカ１１１７を含む出力装置とにより形成される。変復調器（モデム）トランシーバ装置１１１６は、例えば電話回線１１２１又は他の機能媒体を介して接続可能な通信ネットワーク１１２０と通信するためにコンピュータモジュール１１０１により使用される。モデム１１１６は、インターネット並びにローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）等の他のネットワークシステムにアクセスするために使用され、いくつかの実現例においてはコンピュータモジュール１１０１に内蔵されても良い。
【００３３】
一般に、コンピュータモジュール１１０１は、少なくとも１つのプロセッサユニット１１０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されるメモリユニット１１０６とを含む。モジュール１１０１は、ビデオ表示装置１１１４及びスピーカ１１１７に結合するオーディオビデオインタフェース１１０７と、キーボード１１０２及びマウス１１０３及びオプションとしてジョイスティック（不図示）に対する入出力（Ｉ／Ｏ）インタフェース１１１３と、モデム１１１６、スキャナ１１８及びプリンタ１１１５に対するインタフェース１１０８とを含む多くのＩ／Ｏインタフェースを更に含む。いくつかの実現例において、モデム１１１６は、コンピュータモジュール１１０１内、例えばインタフェース１１０８内に内蔵されても良い。記憶装置１１０９が提供され、一般にハードディスクドライブ１１１０及びフロッピー（登録商標）ディスクドライブ１１１１を含む。磁気テープ装置（不図示）が更に使用されても良い。一般にＣＤ−ＲＯＭドライブ１１１２は、データの不揮発性ソースとして提供される。一般にコンピュータモジュール１１０１の構成要素１１０５〜１１１３は、当業者には周知のコンピュータシステム１１００の従来の動作モードを結果として与える方法で、相互接続バス１１０４を介して通信する。上述の構成が実現されるコンピュータの例として、ＩＢＭのＰＣ及びそれに互換性のある、Sun SPARCstation又はそれから進化した同様のコンピュータシステムがある。
【００３４】
一般に、アプリケーションプログラムは、ハードディスクドライブ１１１０に常駐し、プロセッサ１１０５による実行の際に読み出され且つ制御される。ネットワーク１１２０から取り出されるプログラム及び任意のデータの中間記憶装置は、ハードディスクドライブ１１１０と共に動作する可能性のある半導体メモリ１１０６を使用して達成されても良い。いくつかの例において、アプリケーションプログラムは、ＣＤ-ＲＯＭ又はフロッピー（登録商標）ディスク上で符号化されてユーザに供給され、対応するドライブ１１１２又は１１１１を介して読み出されても良い。或いは、アプリケーションプログラムは、ユーザによりモデム装置１１１６を介してネットワーク１１２０から読み出されても良い。また、ソフトウェアは、他のコンピュータ読み取り可能な媒体からコンピュータシステム１１００にロードできる。本明細書において使用される用語「コンピュータ読み取り可能な媒体」は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム１１００に提供することに関係する任意の記憶装置又は伝送媒体を示す。記憶媒体の例としては、装置がコンピュータモジュール１１０１の内部装置であるか又は外部装置であるかに関わらず、フロッピディスク、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、或いはＰＣＭＣＩＡカード等のコンピュータ読み取り可能なカード等がある。伝送媒体の例としては、別のコンピュータ又はネットワーク化装置に対するネットワーク接続、並びに電子メール送信及びウェブサイト等に記録された情報を含むインターネット又はイントラネットに加え、無線伝送チャネル又は赤外線伝送チャネルがある。
【００３５】
アプリケーションプログラムは、スキャナ１１１８からコンピュータ１１０１に情報を走査する場合及びプリンタ１１１５に印刷する場合に動作可能である。
【００３６】
［ＬＶＢＣの基本構造］
図３は、ＬＶＢＣ３００の外観を示す拡大図である。ＬＶＢＣ３００は、正方形グリッド３０１の交点３０３に近接する多くのドット３０２により形成される。尚、可視のＬＶＢＣ３００を形成するのはドット３０２のみである。グリッド３０１は、単にドット３０２の場所を説明するために示されるため、「仮想」と考えられても良い。ＬＶＢＣ３００の外観は、ドットの標準グリッドと類似するが同一ではない。
【００３７】
図４に、ドット４０２の標準グリッド４００の外観を示す。ここで、ドット４０２は標準正方形グリッド４０１の交点にある。正方形グリッド４０１はピッチ４０３を有し、これは本明細書では「gp」と呼ぶ。
【００３８】
ドットの標準配列４００とＬＶＢＣ３００との間の相違点は、ＬＶＢＣ３００のドット３０２の位置が、ドット３０２が実際の標準配列４００の一部であった場合にドット３０２が占有するグリッド位置から離れた位置に僅かに変調されていることである。この僅かな変調は２つの目的を満足する。第１の目的は、ＬＶＢＣドット３０２の可視性を標準グリッド４００のドット４０２より僅かに減少することである。これは、人間の視覚系が標準グリッドを認識することに非常に適しているからである。変調の第２の目的は、デジタルデータの形式のメッセージがドット４０２の変調に格納されることである。
【００３９】
図５に、ドットの変調を更に詳細に示す。ドット５０２は、標準グリッド５０１の交点上又は交点に近接し、各ドット５０２は、９つの可能な位置５０３のうちの１つに変調される。対応する交点に関して各ドット５０２の左右の横軸の場所である変調は、ドットにより形成されたパターンのデータを表す。グリッドが規定可能及び機械検出可能であり、変調が対応するマークに対して行われても良い基準の場所の集合を形成するという点において、グリッド５０１は標準である。図示するように、各ドットの９つの可能な位置は、関連するか又は対応するグリッド交点を中心とする３×３の配列で構成される。位置５０３の３×３の配列の中心位置は、グリッドの交点に位置付けられ、水平方向及び垂直方向の距離がゼロの変調に対応する。残りの８つの変調位置は、水平方向、垂直方向、或いは水平方向及び垂直方向の双方に対してグリッドの交点からオフセットされる。標準グリッド５０１は、変調されたドットに対する「キャリア」信号と考えられても良く、無線周波数通信における搬送波と同様に直接観測可能ではない。変調位置がオフセットされる水平及び垂直の距離は変調量子５０４であり、本明細書においては「mq」と略す。対応するグリッドの交点に対する９つの変調位置の場所は、（ｘ、ｙ）ベクトルのリストとして書ける。ここで、ｘは水平方向を示し、ｙは垂直方向を示す。また、ｘに関しては右向きのオフセットが正であり、ｙに関しては下向きのオフセットが正であるという規則を使用する。ベクトルは以下の通りである。
【００４０】
【数１】
【００４１】
図６に、ドット変調位置５０３を更に詳細に示す。位置５０３は、グリッド６０２のグリッド交点６０４を中心とし、位置６０１等の各変調位置は関連するデジタルコード値６０３を有する。位置６０１に対するデジタルコード値６０３は「０」である。９つの変調位置（位置６０１を含む）により、各ドットは９つの可能なデジタルコード値（位置６０１に対する値６０３を含む）のうちの１つを符号化できる。変調位置により、ＬＶＢＣはデジタルデータ記憶装置として動作でき、ＬＶＢＣの各ドットはデータの９を基数とする１つの数字を格納する。図７に示すように、デジタルデータ記憶装置の数字の好ましい順序付けは、ドットの矩形配列を使用することにより提供される順序付けである。この順序付けは、図７の一番上の最も左側のドット７０１から開始し、一番下の最も右側のドット７０３に到達するまで左から右及び上から下に連続的に進む。本開示の趣旨の範囲から逸脱せずに、他の順序付けが同様に利用されてもよいことは当業者には容易に理解されるだろう。
【００４２】
［符号器］
図８は、ＬＶＢＣを符号化する好適な方法８００を示すフローチャートである。一実現例において、符号化は、ＰＣ１０１又はコンピュータ１１０１内で実行可能なソフトウェアアプリケーションにより実行され、プリンタ１０２又は１１１５により媒体１０７上に印刷するためのＬＶＢＣを生成する。処理はステップ８０１で開始し、ＬＶＢＣに符号化されるバイナリメッセージを入力として受け付ける。このバイナリメッセージは、リードソロモン又は低密度パリティチェック（ＬＤＰＣ）等の誤り訂正符号（ＥＣＣ）を使用して冗長性を含んで符号化される。多くの場合、ＥＣＣを使用することにより、限定された伝送エラーがあってもＬＶＢＣが復号化される。ステップ８０２において、３つの変数Ｍ、Ｗ及びＨが計算される。Ｍはメッセージを表すのに必要とされる９を基数とするメッセージ記号数であり、ＷはＬＶＢＣの最小幅（ＬＶＢＣドットで表される）であり、ＨはＬＶＢＣの最小の高さ（ＬＶＢＣドットで表される）である。
【００４３】
ビット長ＢＬのメッセージの場合、Ｍは以下のように計算される。
【００４４】
【数２】
【００４５】
上記演算子は「天井関数」の演算子を表し、その引数の値以上の最小の整数を返す。
【００４６】
Ｗ及びＨは、以下の不等式により制限される。
【００４７】
【数３】
【００４８】
この不等式に対する整数解が使用されてもよいが、好ましい解は、ＷがＨと等しいことを要求することにより正方形ＬＶＢＣを作成することである。これは、Ｗ及びＨが以下のように計算されることを意味する。
【００４９】
【数４】
【００５０】
ステップ８０３において、３つの変数ｘ、ｙ及びｉがゼロに初期化される。
【００５１】
ステップ８０４において、ＬＶＢＣの構成ドットの１つが出力される。ドットはドットを配置できる任意の種類の２次元基板に出力できるが、この特定の例においては、ドットはプリンタ１０２により印刷される１枚の紙１０７に出力される。ドットは以下の位置に出力される。
【００５２】
【数５】
【００５３】
式中、「msg」はＬＶＢＣに格納される９を基数とするメッセージ記号又はデータ項目のシーケンスである。このシーケンスは、メッセージを１つの長い２進数として扱い、当業者には周知の単純な変換技術を使用してその数を９を基数とする表現に変換することにより、ステップ８０１において受け付けたメッセージのバイナリ表現から容易に形成される。msg[0]がシーケンスの開始であるという規則を使用すると、「msg[i]」はメッセージシーケンスのi番目の数字である。z ≧ Mの場合にmsg[z]はゼロとして規定される。
【００５４】
「Vec」は９つのオフセットベクトルの配列であり、以下の値を含む。
【００５５】
【数６】
【００５６】
式中、ｍｑは上述の変調量子５０４である。
【００５７】
ステップ８０５において、現在の水平位置ｘは、ｘを値ｇｐ４０１だけ増加することにより右に移動される。メッセージの添え字ｉは１だけ増加されるため、メッセージの添え字はメッセージの次の数字を参照する。
【００５８】
ステップ８０６において、変数ｘは変数Ｗと比較される。ｘがＷ以上である場合はステップ８０７に進み、Ｗ未満である場合はステップ８０５に戻る。
【００５９】
ステップ８０７において、現在の垂直位置ｙは、ｙを値ｇｐ４０１だけ増加することにより下方向に移動される。変数ｘはゼロに再設定される。その後、ステップ８０８に継続する。
【００６０】
ステップ８０８において、変数ｙは変数Ｈと比較される。ｙがＨ以上である場合、即ちＹｅｓの場合はステップ８０９に進み、Ｎｏの場合はステップ８０５に戻る。
【００６１】
この方法の処理はステップ８０９で終了する。
【００６２】
方法８００の最終的な結果はＬＶＢＣを形成するドットのパターンであり、各ドットはグリッドの対応する交点に対してデジタル位相変調された（ｘ、ｙ）座標を有する。グリッドは任意の原点Ｏ（０，０）を有する。印刷媒体１０７上で原点Ｏを特定の座標（ｘ，ｙ）に設定することにより、ＰＣ１０１は媒体１０７上にデータを印刷することを命令でき、その結果、ＬＶＢＣは複写され且つ場所（ｘ，ｙ）から開始する。
【００６３】
［復号器］
図９は、画像中の低可視バーコード（ＬＶＢＣ）を復号化する方法９００を示すフローチャートである。ここで、ＬＢＶＣは上述のように符号化されている。一実現例において、方法９００はスキャナ１０４を介して読み取られたＬＶＢＣを入力したＰＣ１０６内で実行可能なソフトウェアアプリケーションとして実行される。復号化方法の基本的な前提は、符号化ＬＶＢＣが形成される際に元になったグリッドの正確な向きを判定することである。グリッド自体の規則性を理解することは、グリッドが識別されると、ドットの場所の変調も理解できることを意味する。方法９００はステップ９０１で開始し、例えば印刷されるか又はページから機械により読み取り可能であるＬＶＢＣを組み込むページの走査済画像を入力として受け付ける。一実現例において、走査は６００ｄｐｉで走査された８ビット階調のＪＰＥＧ画像の形式をとる。ステップ９０３において、ＬＶＢＣを形成する複数のドットが検出され、その後ステップは座標データのリストに検出したドットと関連する位置／座標（ページ上の）を格納／記録する。ステップ９０３は、走査済画像の接続構成要素解析を使用して実行されても良い。そのような解析において、画像の個々の画素は検査され、空間的に隣接する画素を接続及びグループ化する。形状に関してそのグループを解析することにより、マーク（即ち、適切な予想される大きさの画素の一般に一様な斑点又は円形のドット）の存在が検出される。マークの重心は、検出したマーク（ドット）に対応する座標の場所を識別するために判定されても良い。
【００６４】
ステップ９０５において、ステップ９０３で取得されたドットの座標のリストが解析され、ＬＶＢＣのキャリア信号を形成する標準グリッドを検出／識別する。この処理は、標準グリッドのピッチ（ｇｐ４０１）、回転角度及び変調量子Ｍｑ（５０４）を返し、供給された座標データのリストを図７に示すように、順序付けされた座標データの矩形配列に変換する。符号化データを表す変調グリッドを提示されると、変調グリッドに対する向き及び間隔を判定することが有用である。ステップ９０５において、変調グリッドではドット間の平均間隔がグリッド間隔に等しいということに基づいてグリッド間隔が判定されても良い。変調グリッドの隣接するドット間の平均の方向が標準正方形グリッド（又は「キャリアグリッド」）の線に位置合わせされることに基づいてグリッドの向きが判定されても良い。
【００６５】
変調量子は、残りの変調位置が対応するキャリアグリッドの交点（図６の６０４）からオフセットされる水平及び垂直距離を示す。変調グリッドのドットは、キャリアグリッドの交点に近接する。一実現例において、変調グリッドの各ドットは、対応するキャリアグリッドの交点を中心とする３×３の配列で配置される９つの可能な位置のうちの１つに変調される。そのような３×３の配列の中心位置は、対応するキャリアグリッドの交点に位置付けられ、水平方向及び垂直方向の距離がゼロの変調に対応する。残りの８つの変調位置は、対応するキャリアグリッドの交点からのオフセットされる。
【００６６】
ステップ９０７において、各ドットの位置に格納された情報が復調される。図６を再度参照すると、復調は、標準グリッド６０２の最近接するキャリアグリッドの交点６０４から最近接又は略最近接するＬＶＢＣドットまでのベクトルを測定することにより達成される。測定されたベクトルは、交点６０４から図６に示す９つの変調位置までのベクトルと比較される。図６において、ベクトル６０５は点６０４から変調位置６０１まで延在する。同様のベクトルが他の各変調位置に対して存在する。ＬＶＢＣドットの測定ベクトルと相関するか又は最も一致する変調位置ベクトルは正確な位置として選択され、値６０３等の対応するデジタルデータ値はＬＶＢＣドットの正確なデータ値として選択される。一致度は、多くの方法で判定されても良い。第１の方法は、グリッドの交点から延在するベクトルのユークリッド比較を使用することである。例えば、ベクトルＶ１（ｘ１，ｙ１）及びＶ２（ｘ２，ｙ２）を使用すると、説明する構成における全ての可能な９つのベクトルの最短のユークリッド距離は以下を使用して計算されても良い。
【００６７】
【数７】
【００６８】
或いは、ベクトルの長さがゼロに近いために角度が不確かである場合に変調が交差位置まで縮退すると仮定すると、グリッドの交点に関する角度が使用されても良い。このように、ステップ９０５により返される全てのドットが処理される。処理は図７に示す順序で実行される。
【００６９】
この段階までに、ＬＶＢＣは、ＬＶＢＣが９を基数とするデータ記号の略矩形の配列の形式であるところまで復号化された。この配列はデータ記号の正確な順序付けを提供するための方法の一部であるが、依然としてメッセージの開始であるデータ記号を識別する必要がある。これは、ＬＶＢＣの回転がまだ完全に解決されていないためである。ステップ９０５は、９０度を法とする回転のみを検出する（即ち、９０度、１８０度又は２７０度の回転はまだ検出されていない）。この問題はステップ９０９において対処される。このステップは、図１０を参照して以下に詳細に説明する。
【００７０】
本開示の一実施形態によると、デジタルデータの保護のために使用されるＥＣＣ符号化デジタルデータに対して情報マークの正確な向きを判定する方法が提供される。方法は、情報マークの１つの可能な向きに対してＥＣＣ符号化データの復号化を試みるステップと、ＥＣＣ復号化が失敗した場合に情報マークの異なる可能な向きを採用し且つＥＣＣ符号化データの復号化を再度試みるステップとを含む。
【００７１】
図１０は、ＬＶＢＣのメッセージデータの開始を見つけるための図９のステップ９０９の方法を示すフローチャート１０００である。処理はステップ１００５で開始し、ステップ１０１０において、ステップ９０７で生成された復調データの正確度が検査される。この正確度の検査は、復調データのＥＣＣ符号化データのＥＣＣ復号化を試みることにより達成される。ＬＶＢＣが不適切に配向される（例えば、９０度、１８０度又は２７０度回転されている）場合、回転はメッセージデータの数字の場所をスクランブルし且つ変調値をスクランブルするため、ＥＣＣ復号化は失敗する。失敗したＥＣＣ復号化は、復調データが不適切に配向されることを示す。ステップ１０１０においてＥＣＣ復号化が失敗した場合、即ちＮｏの場合、ステップ１０１５に継続する。或いは、ステップ１０１０においてＥＣＣ復号化が成功した場合、即ちＹｅｓの場合、ステップ１０２５に進み、メッセージの開始が正確に検出される。その後、図９のステップ９１１に進む。
【００７２】
ステップ１０１０の検査は、完全なＥＣＣ復号化結果に対するものであっても良いが、一実施形態においては、検査は略完全なＥＣＣ復号化結果に対するものである。一実施形態においてＬＤＰＣがＥＣＣとして使用されるため、この方法が使用され、各繰返しが前の繰返しより少ないエラーを有する傾向にある繰返し復号化によりＬＤＰＣは動作する。完全なＬＤＰＣ復号化が実行可能であるが、多くの繰返しの後でもＬＤＰＣ復号化動作が正確な結果に収束できないためにＬＶＢＣが不適切に位置合わせされる場合、処理時間は過剰になる。
【００７３】
次に、ＬＤＰＣ復号化が略完全であるかを判断するために、ステップ１０１０において使用される基準について説明する。ＬＤＰＣ復号化は不完全な処理であり、この処理において、エラー数が制限される場合にのみ復号化が可能である。メッセージがこの制限を超える数のエラーを有する場合、ＬＤＰＣ復号化は実現不可能になる。この制限は、以下により実験的に正確に推定される。
・大量のメッセージを取り込む
・各メッセージをＬＤＰＣ符号化する
・メッセージ毎に符号化値の比率ｐｅ分を破損させる
・各メッセージの完全なＬＤＰＣ復号化を試みる。
【００７４】
完全なＬＤＰＣ復号化により一貫して且つ確実に訂正される最大破損比率ｐｅは、訂正されると適切に予想されるエラーの最大比率であるｌｐｅとして記録される。
【００７５】
第２の実験は以下により行われる。
・大量のメッセージを取り込む
・各メッセージをＬＤＰＣ符号化する
・メッセージ毎に符号化値のうちｌｐｅパーセント分を破損させる
・メッセージ毎にＬＤＰＣ復号化の繰返しを１度試み、失敗したＥＣＣチェックサムの数ｎｃｆを記録する。
【００７６】
最後に、この実験で記録されたｎｃｆの最大値は、ＬＤＰＣ復号化が十分に完全に近いかを判定するために閾値として使用される。ＬＤＰＣ復号化を１度繰り返した結果、ｎｃｆ以下の数の失敗したＬＤＰＣチェックサムが得られる場合、ＬＤＰＣ復号化は略完全であると考えられる（ステップ１０１０の「ＥＣＣは適切」）。
【００７７】
ステップ１０１５において、ＬＶＢＣの全ての可能な向きの正確度が検査されたか（即ち、最後の回転であるか？）に関するテストが行われる。ＬＶＢＣが正方形グリッドを使用するため、これは単に検査された向きの数が４未満であるかというテストである（三角形又は六角形グリッドに基づく別の種類のバーコードの場合、テストは検査された向きの数がそれぞれ３つ又は６つ未満であるかというテストになる）。全ての４つの向きが正常に検査されなかった場合、即ちＹｅｓの場合、データの正確な向きが見つけられなかったため、処理はステップ１０３０で異常終了する。Ｎｏの場合、ステップ１０２０に継続する。
【００７８】
ステップ１０２０において、グリッドは時計方向に９０度回転される。これは各ドットをグリッドの中心に関して９０度回転して移動し、その回転を補償するために各ドットの変調を再解釈することにより達成される。再解釈は、各変調値を以下の表１に示すルックアップテーブルで見つけられる対応する回転変調値と置換することにより達成される。
【００７９】
【表１】
【００８０】
ステップ１０２０の結果、マークのパターンの異なる向きに対するデータの再解釈が得られる。グリッドの回転に関してそのように説明されるが、マークのパターンはグリッド及びマーク毎に判定される新しい位置ベクトルに関して回転されても良く、対応する（回転）データ値はそのパターンから判定される。
【００８１】
ステップ１０２０の終了後、ステップ１０１０に戻る。その後、正確な向きに対する検査の処理が回転データに対して行われる。この手順は、正確な向きが見つけられ、処理がステップ１０２５で正常終了するか又はステップ１０３０で異常終了するまで継続する。異常終了は方法９００を終了させ、正常終了は、方法９００が図９のステップ９１１に進むことを可能にする。
【００８２】
別の実施形態は、回転毎にＥＣＣ復号化を実行し、失敗したＥＣＣチェックサムの数ncfを記録する。ncfの最小数を有する向きは、正確な向きとして返される。
【００８３】
図９を再度参照すると、ステップ９１１は、メッセージ開始が正確に配向されるグリッドの一番上の最も左側の位置に位置付けられるまでステップ９０９により処理された検出された９を基数とするデータ値の矩形グリッドを入力として受け付ける。ステップ９１１は、一番上の最も左側のデータ値から開始し、左から右及び上から下に進むことにより復号化メッセージをアセンブルし、その順番で９を基数とするデータ値を出力する。９を基数とするデータ値を処理する順序は図７により示される順序であり、これについては既に説明した。
【００８４】
ＥＣＣ符号化復調データはＬＶＢＣから抽出され、復号化処理はステップ９１３で終了する。その後、ＥＣＣ符号化復調データはＥＣＣ復号化により訂正される。一実施形態において、これは完全な（複数回繰り返される）ＬＤＰＣ復号化により達成される。
【００８５】
説明した構成は、文書中のデータパターンの形成及び読み取りを提供し、パターンは文書中に形成される複数のマークを有し、各マークは機械により読み取り可能であり且つパターンの不可視のキャリアを形成する仮想グリッドの対応する交差場所等の基準位置に対してデジタル位相変調された場所を有し、変調はそのパターンのデータを表す。
【００８６】
マークは、印刷することにより形成されるドットであるのが好ましく、文書の識別を可能にするコードを共に形成する。マークの大きさは、許容される可視性のレベル及び特定の応用に依存して異なる。その大きさは、文書の印刷解像度で１画素ほどの小ささでも良く、それにより人間の目に対して低い可視性を提供し、一方では電子機械読み取りのための走査を可能にする。マーク及びマークが搬送する識別データは、周知のバーコードに等しい汎関数を表し、「バー」が実際には形成されないが「バーコード」と呼ばれても良い。低い可視性の面と組み合わされる場合、マークはバーを有さず、いくつかの実現例においては人間の目に明らかに可視である可能性があるが、パターンは低可視バーコード（ＬＶＢＣ）と考えられても良い。
【００８７】
符号化の際、配列は所望のデータ量を搬送するのに十分な有用な大きさであっても良く、その一方で、配列が正確に検出されることを保証するために、復号化は実現可能な最小の配列サイズを必要とする。これは正確な復号化には不可欠である。１つの実現可能な最小グリッド／配列サイズは約８×８（即ち、６４個のマークを与える）であり、確実に実現可能なサイズは１０×１０又は１２×１２である。現在の９を基数とする構成において、８×８のグリッドサイズは約２０２（＝64（log29））ビットのデータを提供する。本開示の趣旨の範囲を逸脱せずに、他のグリッド／配列サイズが同様に実現可能であってもよいことは、当業者には理解されるだろう。
【００８８】
グリッドの交点毎に変調ドットが１つのみ存在するため、それがその交点に対して固有であることは、上記から明らかだろう。交点に関連するドットが２つ以上存在する場合、曖昧さが生じ、復号化は無意味な結果を生成する。従って、任意の実現可能な実現例の場合、任意の１つの交点の可能な変調ドットの場所は別の（例えば、隣接する）交点のドットの可能な変調場所とオーバラップすべきではない。
【００８９】
他のいくつかの方法は、標準（正方形）グリッドの交点に位置付けられるドットにより形成されるコンピュータ読み取り可能なマークを提供した。それらの例において、ドットは論理「１」を表すために交点において生成されても良く、ドットは論理「０」を表すために生成されない。その結果、ドットが生成されないことにより、論理「０」ではなくコンピュータ読み取り可能なマークがないと解釈されるという曖昧さが生じる。反対に、ここで開示される構成により、全てのデータ値はマークにより表現され、データ値を判定するのは仮想グリッドの対応する交点に対するマークの位置である。従って、曖昧さの尤度は減少する。マークはドットである必要はなく、最も単純なレンダリングでは紙上の１滴のインクであっても良く、これは小さな略円形のマークを示すだろう。いくつかの実現例において、例えばマークはドット群であっても良く、正方形又は三角形等の任意の所望の検出可能な形状を形成する。実現可能な大きなドットは、この分の末尾に現れるようなピリオドと等しくても良い。それは、フォントサイズに依存して多くの表示可能な画素又は印刷可能な画素を占有する可能性がある。
【００９０】
説明する構成は結果として電子ページデータを形成し、この形成の結果、プリンタ１０２、１１１５に出力される時、説明したように情報コンテンツ及び１つ以上のＬＶＢＣを有する可能性のあるページデータのハードコピーが複写される。電子データは、後続する複写のために格納されてもよい電子文書をビデオ表示装置１１１４又はプリンタ１０２、１１１５を介して電子的に形成する。同様に、説明したようにＬＶＢＣを組み込む文書の走査により、ページデータが１つ以上のＬＶＢＣを含む電子文書が生成される。複写及び／又は格納のモードに関係なく、そのような電子文書は印刷又は復号化のためにコンピュータ間で通信されてもよい（例えばネットワーク１１２０を介する）。
【００９１】
［ＬＶＢＣの背景］
更に本開示は、画像中のドットパターンを復号化することに関する。ドットパターンはドットの変調グリッドであり、これは少なくともデータメッセージを符号化する。尚、少なくとも１つの実現例において、ドットパターンは位置決めマーク又は同期マークを有する必要はない。しかし、本実現例は、位置決めマーク又は同期マークを含むドットパターンを検出できる。
【００９２】
本開示に係る一実施形態の一実現例は、コピー機に組み込まれたソフトウェア又はコピー機にリンクされるソフトウェアで実現される。コピー機を使用してドットパターンを含む画像をコピーしようとする場合、ドットパターンを検出するために画像は解析される。復号化メッセージは、画像の複写が許可されているか否かを判定する。例えば、入力画像から復号化された４つのメッセージのうち，３つのメッセージがコピーを許可し、１つのメッセージがコピーを禁止する場合、入力画像はコピーされない。更に、別の実施形態は、コピーを許可するドットパターン領域のみを複写し、コピーを禁止するドットパターン領域を省略しても良い。
【００９３】
別の実現例において、本実施形態により識別されたドットパターン領域及びそれらの関連する復号化メッセージをオペレータに対して視覚的に識別可能である。
【００９４】
本明細書において説明される方法は、図３８に示すようなコピー機３８１５に結合されるコンピュータシステム３８００を使用して実現されても良く、図１〜図１０、図１２〜図３７の処理は、コンピュータシステム３８００内で実行可能な１つ以上のアプリケーションプログラム等のソフトウェアとして実現されても良い。コンピュータシステム３８００は試みたコピー動作を検出でき、コピー処理においてコピー機３８１５を共に形成するスキャナ及びプリンタを制御できる。一実現例において、コンピュータシステム３８００は、画像中のコンピュータ読み取り可能なマークの構成内で位置決めマークの配置を識別する方法を実現する。コピー機３８１５は、コンピュータ読み取り可能なマークを含む画像を走査するために利用される。特に、配置の識別、バーコードの検出及びコピープロテクトの方法のステップは、コンピュータシステム３８００内で実行されるソフトウェアの命令により行われる。命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されても良い。ソフトウェアは２つの別個の部分に分割されても良く、第１の部分及び対応するコードモジュールは識別及び検出方法を実行し、第２の部分及び対応するコードモジュールは第１の部分とユーザとの間のユーザインタフェースを管理する。例えばソフトウェアは、以下に説明する記憶装置を含むコンピュータ読み取り可能な媒体に格納されても良い。ソフトウェアは、コンピュータ読み取り可能な媒体からコンピュータシステム３８００にロードされ、コンピュータシステム３８００により実行される。そのようなソフトウェア又はコンピュータプログラムを記録したコンピュータ読み取り可能な媒体は、コンピュータプログラム製品である。コンピュータプログラム製品をコンピュータシステム３８００において使用することにより、バーコードを検出及び配置を検出するための有利な装置を達成するのが好ましい。
【００９５】
図３８に示すように、コンピュータシステム３８００は、コンピュータモジュール３８０１と、キーボード３８０２及びマウスポインタデバイス３８０３等の入力装置と、表示装置３８１４及びスピーカ３８１７を含む出力装置と、コピー機３８１５に対する接続とにより形成される。外部変復調器（モデム）トランシーバ装置３８１６は、接続３８２１を介して通信ネットワーク３８２０と通信するためにコンピュータモジュール３８０１により使用されても良い。ネットワーク３８２０は、インターネット又は専用ワイドエリアネットワーク（ＷＡＮ）等のＷＡＮであっても良い。接続３８２１が電話回線である場合、モデム３８１６は従来の「ダイヤルアップ」モデムであっても良い。あるいは、接続３８２１が大容量（例えば、ケーブル）接続である場合、モデム３８１６はブロードバンドモデムであっても良い。無線モデムは、ネットワーク３８２０に無線接続するために使用されても良い。ネットワーク３８２０及び３８２２は、同様に制御されるのが望ましい他のコピー機にアクセスできる。
【００９６】
一般に、コンピュータモジュール３８０１は、少なくとも１つのプロセッサユニット３８０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されるメモリユニット３８０６とを含む。モジュール３８０１は、ビデオ表示装置３８１４及びスピーカ３８１７に結合するオーディオビデオインタフェース３８０７と、キーボード３８０２及びマウス３８０３及びオプションとしてジョイスティック（不図示）に対する入出力（Ｉ／Ｏ）インタフェース３８１３と、外部モデム３８１６及びコピー機３８１５に対するインタフェース３８０８とを含む多くのＩ／Ｏインタフェースを更に含む。いくつかの実現例において、モデム３８１６は、コンピュータモジュール３８０１内、例えばインタフェース３８０８内に内蔵されても良い。コンピュータモジュール３８０１は、接続３８２３を介してコンピュータシステム３８００をローカルエリアネットワーク（ＬＡＮ）として周知のローカルコンピュータネットワーク３８２２に結合することを可能にするローカルネットワークインタフェース３８１１を更に有する。図示するように、ローカルネットワーク３８２２は、接続３８２４を介してワイドネットワーク３８２０に結合しても良く、一般に、所謂「ファイアウォール」装置又は同様の機能性を含む。インタフェース３８１１は、Ethernet（登録商標）回路カード、無線Bluetooth（登録商標）又はＩＥＥＥ８０２．１１無線構成により形成されても良い。
【００９７】
インタフェース３８０８及び３８１３は、直列接続性及び並列接続性の双方を提供でき、一般に直列接続性は、ユニバーサルシリアルバス（ＵＳＢ）規格に従って実現され、対応するＵＳＢ接続（不図示）を有する。記憶装置３８０９が提供され、一般にハードディスクドライブ（ＨＤＤ）３８１０を含む。フロッピー（登録商標）ディスクドライブ及び磁気テープ装置（不図示）等の他の装置が更に使用されても良い。一般に光ディスクドライブ３８１２は、データの不揮発性ソースとして動作するために提供される。光ディスク（例えば、ＣＤ−ＲＯＭ、ＤＶＤ）、ＵＳＢ−ＲＡＭ及びフロッピー（登録商標）ディスク等のポータブルメモリ素子は、システム３８００に対するデータの適切な供給元として使用されても良い。一実現例において、本開示の一実施形態に従って識別された一群は、１つ以上の記憶装置３８０９に格納される。格納された一群は、後でデータ搬送マークを復号化するために使用される。
【００９８】
一般に、コンピュータモジュール３８０１の構成要素３８０５〜３８１３は、当業者には周知のコンピュータシステム３８００の従来の動作モードを結果として与える方法で、相互接続バス３８０４を介して通信する。上述の構成が実現されるコンピュータの例として、ＩＢＭのＰＣ及びそれに互換性のある、Sun SPARCstation、Apple Mac（登録商標）又はそれから進化した同様のコンピュータシステムがある。
【００９９】
通常、上述のアプリケーションプログラムは、ハードディスクドライブ３８１０に常駐し、プロセッサ３８０５による実行の際に読み出され且つ制御される。ネットワーク３８２０及び３８２２から取り出されるプログラム及び任意のデータの中間記憶装置は、ハードディスクドライブ３８１０と共に動作する可能性のある半導体メモリ３８０６を使用して達成されても良い。いくつかの例において、アプリケーションプログラムは、１つ以上のＣＤ-ＲＯＭ上で符号化されてユーザに供給され、対応するドライブ３８１２を介して読み出されても良い。或いは、アプリケーションプログラムはユーザによりネットワーク３８２０又は３８２２から読み出されても良い。更にソフトウェアは、他のコンピュータ読み取り可能な媒体からコンピュータシステム３８００にロードできる。コンピュータ読み取り可能な媒体は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム３８００に提供することに関係する任意の記憶媒体を示す。そのような媒体の例としては、装置がコンピュータモジュール３８０１の内部装置であるか又は外部装置であるかに関わらず、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、或いはＰＣＭＣＩＡカード等のコンピュータ読み取り可能なカード等がある。命令及び／又はデータの提供に関係しても良いコンピュータ読み取り可能な伝送媒体の例としては、別のコンピュータ又はネットワーク化装置に対するネットワーク接続、並びに電子メール送信及びウェブサイト等に記録された情報を含むインターネット又はイントラネットに加え、無線伝送チャネル又は赤外線伝送チャネルがある。
【０１００】
アプリケーションプログラムの第２の部分及び上述の対応するコードモジュールは、表示装置３８１４上にレンダリングされるか又は表現される１つ以上のグラフィカルユーザインタフェース（ＧＵＩ）を実現するために実行されても良い。キーボード３８０２及びマウス３８０３を操作することにより、コンピュータシステム３８００のユーザ及びアプリケーションはインタフェースを操作し、ＧＵＩと関連するアプリケーションに対して制御コマンド及び／又は入力を提供しても良い。
【０１０１】
マークを検出する方法は、画像処理の機能又はサブ機能を実行する１つ以上の集積回路等の専用ハードウェアで実現されても良い。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ、或いは１つ以上のマイクロプロセッサ及び連想メモリを含んでも良い。更に、コピー機３８１５に結合されるコンピュータシステム３８００を参照して説明したが、コンピュータシステム３８００の説明した機能性の殆どはコピー機３８１５に内蔵され、特定の局所演算を可能にしても良い。
【０１０２】
［基本構造］
データは、変調グリッドを使用してバーコードに格納される。図２８は、変調グリッドの外観を示す拡大図である。変調グリッドは、正方形グリッド２８０１の交点２８０３に近接するドット２８０２及び２８０４の形式の大量のマークから形成される。尚、可視の変調グリッドを形成するのはドット２８０２及び２８０４のみであり、単にドット２８０２及び２８０４の場所を説明するためにグリッド２８０３を示す。
【０１０３】
変調グリッドは、２種類のドットから構成される。ドット２８０２は「データ」ドットの一例であり、このドットは交点２８０３に関して変調される。ドット２８０４は「配置」ドットの一例であり、このドットは交点２８０３の真上にある。図２８において、データ搬送ドット及び配置ドットを異なる陰影を使用して示すが、データ搬送ドット及び配置ドットは各変調以外は実際には同一であり、陰影は図示することを目的とする。図２８に図示する例において、バーコードは、データ搬送ドットが５０％及び配置ドットが５０％で構成される。当然、本開示の趣旨の範囲から逸脱せずに、最小限の変更を伴う他の構成が可能である。
【０１０４】
図２９に、バーコード復号化から発見されたグリッド２９０１を示す。データ搬送ドット２９０２をグリッド２９０１の正方形内に示し、配置ドット２９０４をグリッド２９０１の交点上に示す。配置ドットは、グリッド２９０１を構築するために使用され、各グリッド交点上に現れる。配置ドットが１つおきに位置付けされるため、発見されたグリッドは元の正方形グリッドから４５度オフセットされ、グリッドの間隔は√２倍大きい。この発見されたグリッド２９０１は、ページを２９０３で示される多くの正方形グリッドセルに分割する。各グリッドセルは、正確に１つのデータ搬送ドットを含む。グリッドセルは、バーコードデータの格納及び復号化に対して使用される基本単位である。
【０１０５】
図３０に、情報がグリッドセルのデータ搬送ドットに格納される方法を示す。ドット３００２は、グリッド３００１のグリッドセルのグリッドセル中心３００５に近接して存在し、各ドットは、８つの可能な位置３００３のうちの１つに変調される。各ドットに対する８つの可能な位置は、関連するグリッド交点を中心とする円に配置される。８つの変調位置は、グリッドの中心から水平に、垂直に又は対角線状にオフセットされる。変調位置がオフセットされる水平及び垂直距離は、本明細書では「Ｍｑ」と略される変調量子３００４である。Ｍｑは、グリッドセルの辺の長さの固定比率となるように選択される。Ｍｑの適切な選択肢は元の正方形グリッド間隔の４０％であるが、他の比率が同様に実現されても良い。
【０１０６】
図３１に、ドット変調位置３００３を更に詳細に示す。ドット変調位置３００３はグリッドセル中心３１０３を中心とし、３１０１等の各変調位置はそれに関連付けられる３１０２等のデジタルコード値を有する。８つの変調位置（３１０１を含む）は、各ドットが８つの可能なデジタルコード値（３１０１に対する３１０２を含む）のうちの１つを符号化することを可能にする。これにより、変調グリッドはデジタルデータ記憶装置として動作でき、変調グリッドの各ドットはデータの１つの８を基数とする数字を格納する。理想的には、各ドットはドットが円のグレイコードに配置されるようにコード値を符号化する。これにより、復号化中の誤り訂正が容易になる。図３１に、各ドットのデジタルコード値を２進数で示す。３１０２から時計回りに開始して、ドットは値５、７、６、２、３、１、０及び４を符号化する。本発明の範囲から逸脱せずに、他の変調技術が使用できる。例えば１６個の変調位置は、１６個の可能なデジタルコード値のうちの１つを符号化するために使用される。
【０１０７】
デジタルデータ記憶の数字の好適な順序付けは、図３２に示すようにドットの矩形配列を使用することにより提供される順序付けである。この順序付けは、一番上の最も左側のグリッドセル３２０１から開始し、一番下の最も右側のグリッドセル３２０２に到達するまで左から右及び上から下に進む。当然、他の順序付けが使用可能である。
【０１０８】
一実現例において、データの２つのチャネルが１つのバーコードに同時に格納される。データは、グリッド全体にわたり繰り返しタイリングされる。図３３に、単一の固有のタイル３３００及び使用されるタイリング構成を示す。バーコードは、冗長性のためにグリッド全体にわたり繰り返しタイリングされる。論理的には、各バーコードタイルは、高データ密度（本明細書では「ＨＤＤ」と呼ぶ）チャネル及び低データ密度（本明細書では「ＬＤＤ」と呼ぶ）チャネルの２つの別個のデータチャネルからのデータを表す。ＨＤＤチャネルは低いロバスト性を有し、ＬＤＤチャネルは高いロバスト性を有する。空間的には、バーコードタイル３３００は、本明細書ではＨＤＤチャネルタイルと呼ばれる４つのサブタイル３３０１、３３０２、３３０３及び３３０４から構成される。ＨＤＤチャネルタイルは、グリッドセル又はデータ搬送ドットの単位で３３１４（本明細書では「ＨＤＤタイルサイズ」と呼ばれる）の大きさを有する正方形グリッドである。各ＨＤＤチャネルタイルは、本明細書ではＬＤＤチャネルタイルと呼ばれる１つのより小さな埋め込みタイルを含む。バーコードタイルのＬＤＤチャネルタイルは、３３０５、３３０６、３３０７及び３３０８である。これは、バーコードタイル３３００がＬＤＤチャネルタイルの４つのコピーを含むことを意味する。
【０１０９】
各ＬＤＤチャネルタイルは、グリッドセル又はデータ搬送ドットの単位で３３１３（本明細書では「ＬＤＤタイルサイズ」と呼ばれる）の大きさを有する正方形グリッドである。更にＨＤＤチャネルは、ＬＤＤチャネルタイルを除く４つのＨＤＤチャネルタイルの領域全体を占有する。これは、バーコードタイルがＨＤＤチャネルの単一のコピーのみを含むことを意味する。例えば、領域３３０９、３３１０、３３１１及び３３１２は共にＨＤＤチャネルを構成する。ＨＤＤチャネルを格納するために使用されるＨＤＤチャネルタイルの数は、必要に応じて拡張可能である。現在、バーコードタイル３３００はＨＤＤチャネルタイルの２×２の構成を使用しているが、これを次に大きな構成、ＨＤＤチャネルタイルの３×３の構成に拡張可能である。尚、このタイリング方式は使用されるＨＤＤチャネル構成に依存しないＬＤＤチャネルタイルの一定の密度を維持し、それにより高い冗長性のロバストなＬＤＤチャネルを提供する。誤り訂正符合（ＥＣＣ）は、ＬＤＤチャネル及びＨＤＤチャネルの何れか又は双方のデータに適用される。一実施形態は、当該技術において周知の高性能ＥＣＣである低密度パリティチェック（ＬＤＰＣ）コードを使用する。
【０１１０】
［復号化処理］
図３４は、バーコード復号化のための方法の中間の段階を示すフローチャートである。復号化はステップ３４０１で開始する。第１段階「バーコードの走査」３４０２は、光学式スキャナを使用して紙のバーコードをデジタル走査済画像に変換する。尚、紙のバーコードは複数のバーコードを含むことができ、これは後の復号化段階により正確に処理される。３４０２の出力は走査済画像である。
【０１１１】
第２段階「ドットの検出」３４０３は、走査済画像においてバーコードのドットと考えられる全てのドットの場所を特定／検出するためにヒューリスティックを使用する。３４０３の出力は、場所が特定された大量のドットの中心の（ｘ、ｙ）画素座標のリストである。
【０１１２】
第３段階「一群の検出」３４０４は、ヒューリスティックアルゴリズムを使用して局所的なグリッド間隔及び向きを識別する（一群の検出）。
【０１１３】
第４段階「フラッドフィリング」３４０５は、優先度に基づくフラッドフィルアルゴリズムを使用して場所が特定されたドットのリストにわたり適切なグリッドを適合させる。一般的な例において、３４０４の出力は走査済画像を範囲に含む単一のグリッドである。特定の例において、種々の間隔及び向きの複数のグリッドが走査済画像を範囲に含むことが判明する。例えば、走査済画像が別個であり、異なる間隔又は異なる向きを有する２つ以上のバーコードを含む場合、検出されたバーコード毎に別個のグリッドが出力される。
【０１１４】
第５段階「領域の発見」３４０６は、段階３４０５からの各グリッドに対して動作し、セグメンテーションアルゴリズムを使用してデータ類似性に基づいてグリッドを別個の領域に分割する。一般に、３４０６の出力はグリッドを範囲に含む単一の領域である。特定の例において、複数の領域が発見される。例えばグリッドが「グリッドナビゲーション」により正常に分離されなかった２つのバーコードを含む場合、その２つのバーコードはこの段階で２つの領域に正確に分離され、２つの領域が出力される。
【０１１５】
第６段階「タイルの集約」３４０７は、各領域の繰り返しタイルを単一のタイルに圧縮する。繰り返しタイルのサイズ（図３３の３３１２）は自己相関により見つけられ、領域のタイルは単一のタイルにまとめられる。この集約されたタイルは３４０７の出力である。
【０１１６】
第７段階「ＥＣＣ復号化」３４０８は、集約タイルをＬＤＤチャネル及びＨＤＤチャネルに直列化することによりＥＣＣ復号化を実行し、誤り訂正符合を使用して任意のエラーを訂正し、バーコードデータを抽出する。３４０８の出力は、ＬＤＤデータ及びＨＤＤデータである。
【０１１７】
処理は３４０９で終了する。
【０１１８】
［一群の検出］
次に、図３４の一群の検出ステップ３４０４を更に詳細に説明する。図１２に、データ搬送ドット１２０１及び配置ドット１２０２の配列方法の一例を示す。基準グリッド１２０３は、基準グリッド交点に位置付けられる配置ドットの位置により規定される。データ搬送ドットは、基準グリッド１２０３に関して変調される。本開示は、本明細書では、「一群」と呼ばれる配置ドット間に所定の幾何学的関係を有する配置ドットの構成又は基本クラスタを見つける効率的な解決策を提供する。図１２に示すように、基準方向１２０６に対する基準グリッド間隔１２０４及び基準グリッド角度（向き）１２０５が判定される。
【０１１９】
図１３に、好適な実施形態において使用される別のバージョンの配置を示す。領域１３１０は、５つのドット１３０１〜１３０５から構成される１つの種類の一群を示し、領域１３１１は、４つのドット１３０６〜１３０９から構成される一群を示す。
【０１２０】
図２３は、一群を検出する方法を示すフローチャート２３００である。ステップ２３０１が方法の開始である。ステップ２３０２によると、画像において任意の座標が選択される。画像は一群の検出が実行される所望の頻度に依存して任意のサイズのタイルに分割される。一例として、３２０×３２０画素のタイルサイズは、１４画素のグリッド間隔を有する６００ｄｐｉのＡ４ページに対して有用である。ステップ２３０２において、それらのタイルのうちの１つの中心座標は、任意の座標として選択される。ステップ２３０３において、その任意の座標に最近接する複数のドット（この例においては、１０個のドット）が選択され、一群の検出を実行する。一例として、図１４において、任意の座標１４１１が画像において選択される。領域１４１２は、配置ドットであるか又はデータ搬送ドットであるかに関わらず点１４１１に最近接する１０個のドットを含む。この例において、ドット１４０１〜１４０６は配置ドットであり、ドット１４０７〜１４１０はデータ搬送ドットである。ステップ２３０４において、２つのドットの組合せが１０個の最近接するドットから任意に選択される。回転点は、２つの選択されたドットの座標の重心に設定される。２つの選択ドットの座標は、ステップ２３０５において回転点を中心に９０度回転され、２つの対応する回転座標又は回転位置を生成する。図１５に示すように、ドット１５０１及び１５０２に対応する座標は、回転点を中心に時計回りに９０度回転され、対応する回転座標１５０３及び１５０４をそれぞれ生成する。
【０１２１】
図２３を再度参照すると、判断２３０６において、回転座標１５０３及び１５０４に近接するドットの存在が検査される。それらの回転座標からの誤差範囲内でドットの場所が特定される場合、即ちＹｅｓの場合、２つの選択されたドット及び場所が特定された２つのドットは、共に可能な配置を構成すると考えられる。ステップ２３０８は、可能な配置を構成するそれらの４つのドットの選択を示す。一例として、適切な誤差範囲は、１４画素のグリッド間隔に対して水平及び／又は垂直方向に最大１画素である。判断２３０６において、誤差範囲内の回転座標でドットの場所が特定されない場合、即ちＮｏの場合、判断２３０７に進む。判断２３０７において、ドットの全ての対が使用された場合、即ちＹｅｓの場合、処理はステップ２３１２で終了する。あるいは、ドットの少なくとも１つの対が選択されてない場合、即ちＮｏの場合、ステップ２３０４においてドットの次の対を使用して処理が繰り返される。１０個のドットの場合、これは最大、行列式［１０ ２］又は４５回の可能な繰り返しが存在する。最近接する１０個のドットが選択されたが、本発明の趣旨から逸脱せずに異なる数の最近接するドットを使用できる。更に、ドットの対を選択する処理は任意である必要はない。最大数の繰り返しまで実行する必要がある計算時間を最小限にするために、一実現例において、任意の座標１４１１に近いドットが遠いドットより先に対にされる。
【０１２２】
一実施形態は、不適切な配置が検出されないことを保証するために更なる検査を利用する。不適切な配置が検出される可能性のある一般的な例を示すために、図１６を考慮する。ドット１６０１、１６０２、１６０３及び１６０４は不適切な配置を形成し、それらドットは不適切なグリッド間隔及び角度を結果として与える。ドット１６０１、１６０２、１６０３及び１６０４は、正確な配置より√２倍大きい不適切な配置を形成する。この無効な配置は、基準方向１６２０に対して４５度ではなく０度の角度を返す。正確な配置は、ドット１６０３、１６０４、１６０５及び１６０６から構成される配置である。図２３の判断２３０９において、ドット１６０５〜１６１３の存在は、対応するグリッド交点に近接して存在することを検査される。対応するグリッド交点から誤差範囲内で見つけられるドット数が第１の事前定義済み閾値カウントより少ない場合、即ちＹｅｓの場合、可能な配置を構成するドット１６０１〜１６０４は正確な配置を形成すると考えられ、ステップ２３１０が実行される。一例として、７つのドットの第１の閾値カウントは、可能な配置が正確であるか否かを判定する際に使用するのに適する。その結果、図２３のステップ２３１０は、ドット１６０３〜１６０６を選択することにより形成される正確な配置を見つける。
【０１２３】
ステップ２３０９が配置を検出できない場合、即ちＮｏの場合、ステップ２３１１が実行され、可能な配置を構成する４つのドットが正確な配置を実際に形成するかを更に検証する。図１７に示すように、ステップ２３０５からの可能な配置を構成するドットがドット１７０１〜１７０４である場合、ドット１７０５〜１７１３は、対応するグリッド交点に近接して存在するかが検査される。対応するグリッド交点から誤差範囲内で見つけられたドット数が第２の事前定義済み閾値カウントより少ない場合、即ちＮｏの場合、処理はステップ２３１２で終了する。第２の閾値カウントより多くのドットが存在する場合、即ちＹｅｓの場合、可能な配置を構成する４つのドット１７０１〜１７０４の集合は正確な配置を形成すると考えられ、ステップ２３１０が実行されて、ドット１７０１〜１７０４を正確な配置として選択する。処理は、ステップ２３１２で終了する。
【０１２４】
別の実施形態において、配置は、図１８に示される方法を使用して検出される。図１８に位置決めドット１８０１及びデータ搬送ドット１８０２を示す。この例において、方法は任意のドット１８０３を取得し、４つの最も近接する隣接ドット１８０４〜１８０７が選択される。回転点は、ドット１８０４〜１８０７に対して計算される。図１９に示すように、選択されたドット１８０４〜１８０７の重心である回転点１９０４が計算される。４つの選択されたドットの座標は、回転点１０９４を中心に９０度回転され、図１９の図１９０３に示すように４つの対応する回転座標１９０５〜１９０８を生成する。回転座標１９０５〜１９０８に近接するドットの存在が検査される。対応する回転座標から誤差範囲領域１９０９〜１９１１内でドットの場所が特定される場合、４つの選択されたドットは、可能な配置を構成すると考えられる。一般的な規則として、誤差範囲は、１４画素のグリッド間隔に対して水平及び／又は垂直方向に１画素の偏差と考えられる。可能な配置は、対応する回転座標の誤差範囲領域内にあることが判明した多くのドットに基づいて正確であると考えられる。一例として、４つのドットの場所が全ての４つの対応する回転座標から誤差範囲内で特定されるという厳密な検査が必要とされる。偽肯定的な例を減少するために、更なる検査がこれに追加される。実際に利用される検査数は、特定の応用例に依存する。
【０１２５】
別に実施形態において、図２０に示すように、任意のドット２００１が無作為に選択される。ドット２００１から８つの最近接する隣接ドット２００２〜２００９が選択され、ドットの集合を形成する。それら８つの最近接する隣接ドット２００２〜２００９の座標は、任意のドット２００１を中心に時計回り又は反時計回りに９０度回転され、回転座標２０１２〜２０１９の集合を形成する。回転座標２０１２〜２０１９に近接するドットの存在が検査される。ドットの場所が誤差範囲領域２１０１〜２１０４として図２１に示される対応する回転座標からの誤差範囲領域内で特定される場合、４つの隣接ドット２００３、２００５、２００７及び２００９、並びに任意に選択されたドット２００１は可能な一群を構成すると考えられる。可能な一群は、対応する回転座標の誤差範囲領域内にあることが判明した多くのドットに基づいて有効であると考えられる。一例として、検査は、４つのドットの場所が対応する回転座標から誤差範囲内で特定されることを要求する。図２０を再度参照すると、オーバラップするドットの数が４つである場合、５つのドット２００１、２００３、２００５、２００７及び２００９は、基準グリッドの基本的な一群と考えられる。一般に、データ搬送ドット２００２、２００４、２００６、及び２００８の位置は無作為に置かれるが、ドットの場所が誤差範囲又は回転座標内で特定されることが可能である。従って、９０度、１８０度及び２７０度を含む他の角度の回転により、更なる検査は必要とされても良い。
【０１２６】
別の実施形態として、図２２に、一群を形成するドット２２０３〜２２０６を含む標準三角形グリッドを示す。任意の点２２０９が画像において選択され、点２２０９に最近接する８つのドット２２０３〜２２１０が選択される。８つの選択されたドット２２０３〜２２１０のうち任意の２つのドット、例えば２２０３及び２２０４が選択される。ドット２２０３の座標は、座標２２０６を計算するためにドット２２０４の座標を中心に時計回りに６０度回転され、ドット２２０３の座標は、座標２２０５を計算するために時計回りに１２０度回転される。誤差範囲内にある座標２２０６及び２２０５におけるドットの存在が検査される。ドット２２０３〜２２０６から構成される可能な一群は、ドットが対応する回転座標２２０５及び２２０６の誤差範囲領域内にあると判明するかに基づいて正確であると考えられる。この処理は、一群が検出されるまで又は全てのドットの対が検査されるまで８つの選択されたドット２２０３〜２２１０のうち、ドットの全ての可能な対に対して繰り返される。偽肯定的な例を減少するために更なる検査がこれに追加されることは、当業者には理解されるだろう。利用される検査数は、実際の応用例に依存する。
【０１２７】
上述の実施形態は座標の９０度の回転を使用し、これは単純にｘ座標とｙ座標とを入れ替え、ｙ座標を反転することにより達成される。更に、所定の座標から誤差範囲内のドットの存在の検査は効率的な方法である。従って、この一群の検出方法は最小の計算能力を使用する。
【０１２８】
図３４のステップ３４０４において正確な一群を検出した場合、グリッド間隔及び角度、並びに一群を構成する座標又はドットは、配置ドットにより形成されるグリッド全体を検出するための開始点として使用される。これを行うことにより、全ての配置ドットはデータ搬送ドットから分離される。
【０１２９】
［フラッドフィルによるバーコードナビゲーション］
［グリッドナビゲーション方法の概要］
フラッドフィルによるグリッドナビゲーションの方法は、図３４のステップ３４０５において採用される。次に、このステップを更に詳細に説明する。
【０１３０】
グリッドナビゲーション方法の１つの面は、文書において検出された全ての印刷マークの集合の中で配置マークを識別し、配置マークを１つ以上の標準グリッド上に置くことである。正方形グリッドが一実施形態において使用されるが、方法は他の標準グリッドに対しても容易に適応可能である。
【０１３１】
本開示の１つの態様は、配置マーク及びデータマークから構成されるバーコードを印刷文書において検出する目的で基準グリッドを検出する方法を提供する。ここで、データマークは情報を符号化するために使用され、配置マークはデータマークの配列に対する基準グリッドを規定するために使用される。配置マーク及びデータマークは、そのように使用されない場合は視覚的に区別不可能である。方法は、印刷文書の少なくとも１つの場所において開始位置、間隔及び向きを推定することと、当業者には周知のフラッドフィル方法の変形した方法を使用して配置マークを追跡することとを含む。
【０１３２】
フラッドフィルによるグリッドナビゲーションの方法は、図３４のステップ３４０３及び３４０４の結果を使用する。特に、ステップ３４０３の結果は、特に配置マーク及び任意の他の検出マークを含む全ての検出マークの画像座標の集合である。配置パターンを形成するマークのみが本開示の方法により使用される。或いは、必要に応じて、提供される公称位置のすぐ近くにあるマークの存在を検出するための手段が提供される。
【０１３３】
ステップ３４０４の結果は、少なくとも１つのシード点の集合であり、各シード点に供給される情報は、ステップ３４０４において有効な配置マークとして識別された少なくとも１つのマークの画像座標と、それら画像座標におけるグリッド角度及び間隔の推定値とを含む。或いは、必要に応じてシード点を検出するための手段がステップ３４０４において提供される。シード点の数は、性能と正確度との間の妥協である。
【０１３４】
方法の結果は１つ以上のグリッドデータ構造の集合であり、各グリッドデータ構造はグリッドノードの集合を含む。各グリッドノードは、グリッドのノードの位置と関連付けられる画像座標を格納する。
【０１３５】
方法は２つの連続した段階で動作する。即ち、初期化段階の後にグリッド成長段階が続く。初期化段階中、グリッドデータ構造はステップ３４０４の結果を使用して初期化される。グリッド成長段階中、フラッドフィル又はシードフィル方式として当該業界において周知の方法と同様の方法で、配置マークは識別され、新しいグリッドノードは１つずつグリッドに追加される。新しいグリッドノードが評価及び追加される順序は、ノードが実際に有効な位置決めノードである信頼度の尺度により判定される。更に、新しいノードを追加することにより、２つのグリッドがオーバラップするかを確認するために検査が繰り返し毎に行われ、オーバラップしたグリッドを組み合わせる試みが行われる。
【０１３６】
［データ構造］
本開示の方法により使用されるデータ構造は、グリッドリスト、優先度キュー及び区域配列を含む。
【０１３７】
グリッドリストは、グリッドデータ構造の集合である。各グリッドデータ構造は、追跡される処理におけるグリッドの１つの接続部分を表す。各グリッドデータ構造と関連する情報は、グリッド角度及び間隔、並びにグリッド座標によりアクセス可能なグリッドノードの集合を含む。各グリッドノードと関連する情報は、ノードと関連する画像座標と、そのノードと関連する有効なマークが見つけられたことを示す指示と、ノードが優先度キューを介して処理されたことを示す別の指示とを含む。グリッドノードを親グリッドデータ構造と関連付けるための手段が更に提供される。
【０１３８】
優先度キューは、関連する信頼度値を伴うグリッドノードの集合である。優先度キューは、新しいノードを追加し且つ最も信頼度の高いノードを除去する効率的な動作をサポートする。
【０１３９】
区域配列は、オーバラップしたグリッドを検出する目的で画像上の特定の領域を占有しているグリッド（存在する場合は）を識別するために使用される補助データ構造である。画像は、同等のサイズのオーバラップしない矩形領域、即ち区域に論理的に分割される。各区域は、特定のグリッドにより請求されてもされなくても良い。各区域の大きさは、実現可能な限り小さい必要があるが、予想される最大のグリッドセルの大きさより小さくないのが好ましい。方法の本実施形態はサイズ３２×３２画素の区域を使用するが、他の区域が同様に実現されても良い。
【０１４０】
データ構造の選択は、単純さ、性能及びメモリの必要条件間の種々の妥協を反映する。他のデータ構造が同一の効果に対して使用されてもよいことは、当業者には認識されるだろう。
【０１４１】
［グリッドナビゲーション方法の詳細な説明］
図２４は、フラッドフィルによるグリッドナビゲーションの方法を示すフローチャート２４００である。まず初期化段階がステップ２４０１、２４０２及び２４０３で実行され、次にグリッド成長段階がステップ２４０４、２４０５、２４０６で実行される。
【０１４２】
ステップ２４０１において、内部データ構造は以下のように初期化される。即ち、グリッドリストは空に設定される。優先度キューは空に設定される。区域配列の各区域は未請求に設定される。
【０１４３】
ステップ２４０２において、以下に更に詳細に説明するように、シード点の向きが正規化される。
【０１４４】
ステップ２４０３において、初期グリッドはシード点から作成され、優先度キューが事前にポピュレートされる。以下の動作は各シード点に対して行われる。
【０１４５】
新しいグリッドデータ構造は作成され、グリッドリストに追加される。グリッドの向き及び間隔は、シード点の向き及び間隔から初期化される。
【０１４６】
新しいグリッドノードは、グリッドの原点において新しいグリッドデータ構造に追加される。グリッドノード画像座標は対応するシード点座標に設定され、ノードは関連するマークを有するものとして印をつけられる。本明細書において更に後述するように、新しく作成されたノードは評価され、優先度キューに条件付きで追加される。
【０１４７】
方法のメインループは、ステップ２４０４、２４０５及び２４０６により表される。ステップ２４０４において、方法は、キューが空であるかを検査する。キューが空である場合、即ちＹｅｓの場合、方法は終了ステップで終了する。キューが空でない場合、即ちＮｏの場合、ステップ２４０５に進み、最上部のノードを選択する。最も信頼度の高いノードは、ステップ２４０５においてキューから除去され、ステップ２４０６において処理される。その後ステップ２４０４に戻り、処理は、ステップ２４０４において判定されるようにキューが空になるまで繰り返す。
【０１４８】
［角度の正規化］
図３４のステップ３４０４において推定されるグリッドの角度は、グリッドの回転対称性のために固有の曖昧さを有する。性能の理由のために、角度差が同様に配向されるグリッドに対して小さくなるように角度を正規化するのが望ましい。特に、特定のANGLE_TOLERANCE定数は、同様であると考えられるグリッドに対する向きの角度差の上限を規定するために使用される。ANGLE_TOLERANCEの適切な値は、実験的に判定される。本実施形態のANGLE_TOLERANCEの値は０．０２ラジアンに設定される。
【０１４９】
角度の正規化の処理は、図２４のステップ２４０２で行われ、図２５を参照して更に詳細に示す。図２５は、グリッドの角度の正規化の方法を示すフローチャート２５００である。
【０１５０】
ステップ２５０１において、全てのシード点に対するグリッドの角度は、９０度を法とすることにより０〜９０度の範囲になる。
【０１５１】
ステップ２５０２において、グリッドの角度のヒストグラムは、全ての利用可能なシード点に対するデータを使用して作成／構築される。ヒストグラムビンの大きさは、ANGLE_TOLERANCE定数の値に設定される。
【０１５２】
ステップ２５０３において、境界の角度の値は、最小のカウントを有するビンの中心値であるとして判定／選択される。
【０１５３】
ステップ２５０４において、全てのシード点に対するグリッドの角度は、境界の角度から境界の角度＋９０度までの範囲になる。これは、向きの角度が境界の角度より小さい場合は常に前記角度に９０度を加算することにより達成される。
【０１５４】
角度の正規化のステップはオプションである。このステップが省略される場合、図２７のステップ２７０５においてオーバラップしたグリッドを検査する際にグリッドの向きが比較される時に曖昧さが解決される必要がある。
【０１５５】
［グリッドノードの評価］
グリッドノード評価ステップの間に、現在のノードの任意の欠落する隣接ノードが作成され、ノードの信頼度が計算され、ノードは優先度キューに条件付きで追加される。信頼度は、ノード自体及び現在のノードの全ての隣接ノードに対する距離計測値の合計として計算される。
【０１５６】
現在のノードに対して、距離計測値は、ノードが関連するマークを有する場合はMAX_DISTに設定され、有さない場合はゼロに設定される。隣接ノードに対しては、距離計測値は以下のように計算される。
【０１５７】
隣接ノードが関連するマークを有さない場合、計測値はゼロである。有する場合、計測値は、マークの実際の位置と予想される位置との距離の平方よりMAX_DIST少ない。結果が負数である場合、計測値はゼロに設定される。
【０１５８】
MAX_DIST定数は、マークの実際の位置と予想される位置との間で平方された最大許容距離を示す。一実施形態において、MAX_DISTの値は９であり、これは３画素の最大距離に対応する。
【０１５９】
信頼度を計算する他の方法が可能であることは、当業者には認識されるだろう。選択は、正確度と性能との間の技術的妥協により判定される。特に、計算はマークの大きさ及び形状、グリッドの他の位置決めマークの位置等に関する情報を含んでも良い。
【０１６０】
図２６は、グリッドノードの評価の方法を示すフローチャート２６００である。まずステップ２６０１において、信頼度値は、現在のノードが関連するマークを有さない場合はゼロに初期化され、有する場合はMAX_DISTの値に初期化される。その後ステップ２６０２〜２６１２は、全てのグリッド方向に対して繰り返される。矩形グリッドの場合、４つの方向、即ち上方向、下方向、左方向及び右方向が評価される。
【０１６１】
現在のグリッドの方向は、ステップ２６０２において選択される。ステップ２６０３において、マークの予想される位置は、現在のグリッド方向に従ってグリッド変位ベクトルを回転し、それを現在のノードの位置に追加することにより計算される。グリッド変位ベクトルは、グリッド間隔により乗算され且つグリッドの角度分回転される単位ベクトルとして計算される。効率化のために、グリッド変位ベクトルは事前に計算され、各グリッドデータ構造に格納されても良い。
【０１６２】
ステップ２６０４において、現在の方向の隣接ノードの存在に対する検査がグリッドデータ構造において行われる。隣接ノードが作成されていない場合、即ちＮｏの場合、ステップ２６０５〜ステップ２６０９において新しいノードを作成する試みが実行される。まずステップ２６０５において、予想されるノード座標が画像範囲と比較される。座標が画像範囲外である場合、現在の方向に対して更なる動作は実行されず、ステップ２６１２に進む。ステップ２６０５において、座標が画像範囲内にある場合、即ちＹｅｓの場合、ステップ２６０６において、新しいノードが作成され且つ予想される位置で初期化される。ステップ２６０７において、予想される位置に最近接するマークの場所が特定される。ステップ２６０８において、マークの距離計測値が検査される。計測値がゼロ以下である場合、即ちＹｅｓの場合、マークは遠すぎると考えられ、このノードに対して更なる動作は実行されず、ステップ２６１２に進む。距離計測値がゼロ以下でない場合、即ちＮｏの場合、ステップ２６０９において、ノードは関連するマークを有するものとして印がつけられ、ノードの位置は現在のマークの位置で更新される。ステップ２６１０において、信頼度は計測値分増加される。
【０１６３】
ステップ２６０４においてノードが見つけられる場合、即ちＹｅｓの場合、ステップ２６１１において、ノードは関連するマークの存在について更に検査される。存在する場合、即ちＹｅｓの場合、上述のように、ステップ２６１０において信頼度は更新される。ステップ２６１１において、ノードが関連するマークを有さないことが判明した場合、即ちＮｏの場合、ステップ２６１２に進む。
【０１６４】
ステップ２６１２は、全ての方向が処理されたかを判定する。全ての方向が処理されていない場合、即ちＮｏの場合、ステップ２６０２に戻る。ステップ２６１２において判定されるように、全てのグリッド方向が処理されると、即ちＹｅｓの場合、ステップ２６１３に進む。結果として得られる信頼度はステップ２６１３で検査される。信頼度がゼロより大きいことが判明した場合、即ちＹｅｓの場合、ステップ２６１４において、信頼度と共にノードは優先度キューに追加される。その後終了ステップに進み、方法は終了する。信頼度がゼロより大きくない場合、即ちＮｏの場合、終了ステップに進み、方法は終了する。
【０１６５】
［最も信頼度の高いノードの処理］
最も信頼度の高いノードの処理は、図２４のステップ２４０６において行われ、図２７に更に示される。図２７は、高信頼のグリッドノードの処理の方法を示すフローチャート２７００である。
【０１６６】
まずステップ２７０１、２７０２、２７０５及び２７０６において、グリッドをマージする特定の例が検査され、影響を受ける。ステップ２７０１において、区域配列は、現在のノードの位置において調査される。区域所有者が現在のグリッドと同一である場合、即ち「同一」の場合、特別な動作は行われず、ステップ２７０３に進む。ステップ２７０１において区域が請求されていない場合、即ち「未請求」の場合、ステップ２７０２において区域の所有者は現在のグリッドに設定され、ステップ２７０３に進む。ステップ２７０１において区域の所有者が現在のグリッドと異なる場合、即ち「相違」の場合、ステップ２７０５及び２７０６においてグリッドに参加する試みが実行される。
【０１６７】
ステップ２７０５において、２つのグリッド、即ち現在のノードのグリッド及び現在のノードの位置の区域所有者の互換性が検査される。向きの差がANGLE_TOLERANCEより小さく、間隔の差がSPACING_TOLERANCEより小さい場合、グリッドは互換性があると考えられる。SPACING_TOLERANCEは実験的に判定される定数であり、本実施形態において使用される値は１．５画素である。
【０１６８】
ステップ２７０５において否定的な結果である場合、即ちＮｏの場合、終了ステップに進み、方法は終了する。ステップ２７０５において肯定的な結果である場合、即ちＹｅｓの場合、以下のようにステップ２７０６において、グリッドはマージされる。
【０１６９】
まず、変位ベクトルは、第２のグリッドの原点から第１のグリッドの原点を減算することにより計算される。グリッド座標のオフセットは、前記変位ベクトルの座標を第１のグリッドの角度だけ回転し、その結果を第１のグリッドの間隔で除算し且つ結果を最も近い整数値に四捨五入することにより計算される。
【０１７０】
グリッドのオフセットが計算された後、第２のグリッドの全てのノードは第１のグリッドに転送され、第２のグリッドはグリッドリストから除去される。第１のグリッドのノードの位置は、第２のグリッドのノードの位置にグリッドのオフセットを加算することにより判定される。それと同時に、第２のグリッドにより所有されているとして区域配列において印をつけられた区域は、第１のグリッドにより所有されているとして再度ラベル付けされる。
【０１７１】
同一のノードの複製の作成を回避するために、現在のノードの更なる処理はスキップされる。ステップ２７０６から終了ステップに進み、方法は終了する。
【０１７２】
ステップ２７０３において、現在のノードの隣接ノードは、全てのグリッド方向に対して評価される。ノードが存在し、処理されたものとして印がつけられていない場合、そのノードは図２６に関して上述したように評価される。
【０１７３】
ステップ２７０３からステップ２７０４に進み、現在のノードは処理されたものとして印がつけられる。ステップ２７０４から終了ステップに進み、方法は終了する。
【０１７４】
［更なる実施形態］
本明細書において、デジタルデータ及びデジタルデータの保護のための関連する誤り訂正符号（ＥＣＣ）データを含む情報マークの正確な向きを判定する方法が開示される。ＥＣＣの復号化は情報マークの１つの可能な向きに対して試行され、ＥＣＣ復号化が失敗した場合、情報マークの異なる可能な向きが採用されて、ＥＣＣの復号化が再度試行される。
【０１７５】
本明細書において、画像中の位置決めマーク／ドットにより形成される基準グリッドの基本的な一群を検出する方法及びシステムが更に開示される。このグリッドは、間隔及び向きに対して種々の所定の値を有することができ、データ搬送ドットはグリッドに関して変調される。基本的な一群は、配置ドットのみを構成し、配置ドットはデータ搬送ドットと分離される必要がある。基本的な一群の検出により、グリッドの間隔及び向きが識別され、一実現例において、これは基準グリッド全体を拡張及び検出するための次の段階で使用される。
【０１７６】
本明細書において、印刷文書の配置マークを追跡する方法及びシステムが更に開示される。配置マークは、グリッド状のパターンを形成する。本開示の１つの態様によると、印刷文書の他のマークに関係なく基準グリッドを検出する方法が提供される。
【０１７７】
本開示の１つの態様によると、基準グリッドの部分であるドットの一群を検出する方法が提供される。方法は、画像において任意の座標を選択するステップと、選択した座標に最近接する複数のドットを選択するステップと、選択した最近接するドットから２つのドットを選択するステップと、選択した２つのドットを９０度回転して回転位置を判定するステップと、回転位置のドットを検査するステップと、回転位置周辺の誤差範囲内のドットを検査するステップと、複数のドットを一群として選択するステップとから成る。一実施形態において、選択した最近接するドットは８つ存在する。
【０１７８】
本開示の別の態様によると、基準グリッドの部分であるドットの一群を検出する方法が提供される。方法は、選択したドット及び選択したドットの４つの最近接する隣接ドットを含むドットの元の集合を選択するステップと、回転集合を生成するために回転の中心に関して４つのドットを回転するステップと、元の集合及び回転集合のオーバラップするドットを検査するステップと、複数のオーバラップするドットに基づいてドットの基本的な一群を選択するかを判定するステップとから成る。
【０１７９】
本開示の更なる態様によると、基準グリッドの部分であるドットの一群を検出する方法が提供される。方法は、ドットを選択し、ドットの元の集合を形成するために選択したドットの８つの最近接する隣接ドットを選択するステップと、ドットの回転集合を生成するために選択したドットを中心に８つの最近接する隣接ドットを回転するステップと、ドットの元の集合とドットの回転集合との間でオーバラップするドットを検査するステップと、オーバラップするドットの数に基づいてドットの基本的な一群を選択するかを判定するステップとから成る。一実施形態において、一群は基準グリッドの形状に依存する幾何学的形状である。別の実施形態において、グリッドは種々の所定のグリッド間の距離及び向きを有する。更なる実施形態において、一群のドット数は変動する。更に別の実施形態において、ドットの形状及び大きさのうち少なくとも一方は変動する。
【０１８０】
本開示の更に別の態様によると、ドットの回転集合を見つけるために、選択した位置を中心に事前定義済みの角度分複数のドットを回転する方法が提供される。方法は、画像において点を選択し、その点の周囲にあり且つドットの元の集合を形成する複数のドットを事前定義済みの規則に基づいて選択することと、事前定義済みの規則に従って回転の中心を計算することと、ドットの回転集合を形成するために回転の中心に関して選択したドットを回転することとから成る。一実施形態において、ドットの元の集合及びドットの回転集合は比較され、オーバラップするドットを見つけ、特定の幾何学的パターンを検出する。
【０１８１】
本開示の別の態様によると、配置マーク及びデータマークから構成されるバーコードを印刷文書において検出する目的で基準グリッドを検出する方法が提供される。データマークは情報を符号化するために使用され、配置マークはデータマークの配列に対して基準グリッドを規定するために使用される。配置マーク及びデータマークは、そのように使用されない場合は視覚的に区別不可能である。方法は、印刷文書の少なくとも１つの場所において開始位置、間隔及び向きを推定するステップと、フラッドフィル方法の変形した方法を使用して配置マークを追跡するステップとから成る。一実施形態において、マークが処理される順序は、マークが有効な配置マークである信頼度の尺度により影響を受ける。別の実施形態において、信頼度の尺度は、他の配置マークに対するマークの位置に基づいて計算される。更なる実施形態において、２つ以上のグリッドは２つ以上の開始位置を使用して同時に追跡され、同様に配向されたオーバラップしたグリッドはマージされる。
【０１８２】
本開示の更なる態様によると、デジタルデータ及びデジタルデータの保護のための関連するＥＣＣデータを含む情報マークの正確な向きを判定する方法が提供される。方法は、情報マークの１つの可能な向きに対してＥＣＣの復号化を試みるステップと、ＥＣＣ復号化が失敗した場合、情報マークの異なる可能な向きを採用して、ＥＣＣの復号化を再度試みるステップとから成る。
【０１８３】
本開示の更に別の態様によると、画像中の低可視バーコード（ＬＶＢＣ）を復号化する方法が提供される。方法は、低可視バーコードを形成する複数のドットを検出するステップと、検出した各ドットと関連付けられる座標を格納するステップと、低可視バーコードのキャリア信号を形成する標準グリッドを識別するために格納された座標を解析するステップと、変調グリッドに対して向き及び間隔を判定するステップと、各ドットの位置に格納された情報を復調するステップと、低可視バーコードのメッセージデータの開始を判定するステップと、復号化メッセージをアセンブルするステップとから成る。
【産業上の利用可能性】
【０１８４】
上記構成がコンピュータ産業、データ処理産業、印刷産業及びイメージング産業に適用可能であることは、上述から明らかである。
【０１８５】
上述において、本発明のいくつかの実施形態のみを説明したが、本発明の趣旨の範囲から逸脱せずに変形及び／又は変更が可能である。それら実施形態は単なる例示であり、限定するものではない。
【０１８６】
本明細書において、用語「具備する」は、「主に含むが、単独で必要ではない」、「有する」又は「含む」ことを意味し、「〜のみから構成される」ことではない。用語「具備する」の語形変化は、それに対応して意味の変化を示す。
【図面の簡単な説明】
【０１８７】
【図１】低可視バーコード（ＬＶＢＣ）を印刷するのに適した機器を示す概略ブロック図である。
【図２】ＬＶＢＣをコンピュータにより読み取るのに適する機器を示す概略ブロック図である。
【図３】ドットが全て標準グリッド上にないように位相変調されたドットの配列を示す図である。
【図４】標準グリッド上に位置するドットの標準配列を示す図である。
【図５】ドットの変調を更に詳細に示す図である。
【図６】ドットの変調を更により詳細に示す図である。
【図７】ＬＶＢＣの数字の順序付けを示す図である。
【図８】ＬＶＢＣデータを符号化する方法を示すフローチャートである。
【図９】ＬＶＢＣデータを復号化する方法を示すフローチャートである。
【図１０】ＬＶＢＣの正確な向きを判定する方法を示すフローチャートである。
【図１１】説明する構成が実現されるコンピュータシステムを示す概略ブロック図である。
【図１２】基準グリッド及びデータ搬送ドットを示す図である。
【図１３】２つの異なる種類の基本的な一群を示す図である。
【図１４】一実施形態に係る一群を示す図である。
【図１５】９０度回転させる技術を示す図である。
【図１６】不適切な一群が選択されないことを保証するための追加の検査を示す図である。
【図１７】不適切な一群が選択されないことを保証するための別の追加の検査を示す図である。
【図１８】基本的な一群の検出を示す図である。
【図１９】別の実施形態に対して、回転及びオーバラップするドットを更に詳細に示す図である。
【図２０】一群を検出する別の実施形態を示す図である。
【図２１】図２０を参照して説明する実施形態に対して、回転及びオーバラップするドットを更に詳細に示す図である。
【図２２】三角形グリッドを含む別の実施形態を示す図である。
【図２３】基本的な一群を検出する方法を示すフローチャートである。
【図２４】フラッドフィルによるグリッドナビゲーションの方法を示すフローチャートである。
【図２５】グリッドの角度の正規化の方法を示すフローチャートである。
【図２６】グリッドノードの評価の方法を示すフローチャートである。
【図２７】高信頼のグリッドノードの処理の方法を示すフローチャートである。
【図２８】本開示の一実施形態に従ってバーコードのデータを符号化するために使用されるドットの変調グリッドを示す図である。
【図２９】復号化の目的でドットの変調グリッドを示す概念図である。
【図３０】データを単一のドットの変調に符号化する方法を示す図である。
【図３１】データを単一のドットの変調に符号化するために使用される符号化方式を示す図である。
【図３２】データ搬送ドットの復号化順序を示す図である。
【図３３】本開示の一実施形態に従ってバーコードに対して使用されるタイリング方式を示す図である。
【図３４】バーコードの復号化のための方法の中間の段階を示すフローチャートである。
【図３５】「グリッドナビゲーション」バーコード復号化段階の出力を示す図である。
【図３６】「領域の発見」バーコード復号化段階の出力を示す図である。
【図３７】「タイルの集約」バーコード復号化段階の出力を示す図である。
【図３８】説明する構成が実現されるコンピュータシステムを示す概略ブロック図である。
【特許請求の範囲】
【請求項１】
画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法であって、
前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、
前記選択したマークの各位置に関する回転の中心を判定するステップと、
前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、
各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有することを特徴とする方法。
【請求項２】
前記識別された一群の間隔及び向きを判定するステップと、
前記識別された一群の前記間隔及び前記向きに基づいて予想されるマークの場所の集合を判定するステップと、
前記予想されるマークの場所のうち、少なくとも所定の割合の場所が前記コンピュータ読み取り可能なマークの構成におけるマークの場所と一致する場合、前記配置マークの識別された一群を検証するステップとを更に有することを特徴とする請求項１に記載の方法。
【請求項３】
前記コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合であることを特徴とする請求項１に記載の方法。
【請求項４】
前記コンピュータ読み取り可能なマークは、ドット、ドット群、円、正方形及び三角形から構成されるマーク群から選択されることを特徴とする請求項１に記載の方法。
【請求項５】
前記基準グリッドは矩形グリッドであり、２つのマークは前記コンピュータ読み取り可能なマークの構成から選択され、前記回転の中心を判定することは前記２つの選択したマーク間で場所を特定される点を識別することを特徴とする請求項１に記載の方法。
【請求項６】
前記基準グリッドは三角形グリッドであり、前記回転の中心を判定することは前記選択したマークのうちの一方を前記回転の中心として割り当てることを特徴とする請求項１に記載の方法。
【請求項７】
前記判定した間隔及び向きに基づいて、前記コンピュータ読み取り可能なマークの構成から追加のマークを組み込むために前記識別された一群を拡張するステップを更に有することを特徴とする請求項２に記載の方法。
【請求項８】
前記基準グリッドを識別するために前記識別された一群を利用するステップと、
前記識別された基準グリッドに基づいて前記コンピュータ読み取り可能なマークの構成において前記データ搬送マークを識別するステップと、
前記識別されたデータ搬送マークを復調するステップとを更に有することを特徴とする請求項１に記載の方法。
【請求項９】
画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法であって、
前記コンピュータ読み取り可能なマークの構成から選択される少なくとも２つのマークの少なくとも１つの組み合わせに対して、
（ａ）前記組み合わせの前記選択されたマークの各位置に関する回転の中心を判定するステップと、
（ｂ）前記選択されたマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記組み合わせの前記選択されたマークに対する回転位置を判定するステップと、
（ｃ）各回転位置に対して、前記回転位置に最近接するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
（ｄ）前記回転位置のうち、少なくとも所定の割合の回転位置に対して前記回転位置に最近接する前記マークが前記回転位置から所定の閾値未満の位置にある場合、前記組み合わせの前記選択されたマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有することを特徴とする方法。
【請求項１０】
前記コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合であることを特徴とする請求項９に記載の方法。
【請求項１１】
走査済画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するように構成されたコピー機であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調されるコピー機であって、
前記走査済画像を取得するスキャナと、
コンピュータプログラムを格納する記憶装置と、
前記コンピュータプログラムを実行するプロセッサとを有し、前記コンピュータプログラムは、
前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、
前記選択したマークの各位置に関する回転の中心を判定するステップと、
前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、
各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを前記プロセッサに実行させることを特徴とするコピー機。
【請求項１２】
前記コンピュータプログラムは、
前記識別された一群に基づいて前記基準グリッドを識別するステップと、
前記識別された基準グリッドに基づいて前記コンピュータ読み取り可能なマークの構成において前記データ搬送マークを識別するステップと、
前記識別されたデータ搬送マークを復調するステップとを更に前記プロセッサに実行させることを特徴とする請求項１１に記載のコピー機。
【請求項１３】
前記コンピュータプログラムは、前記復調したデータ搬送マークに基づいて前記走査済画像の複写を許可するステップを更に前記プロセッサに実行させることを特徴とする請求項１２に記載のコピー機。
【請求項１４】
画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群が識別され、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法を実行するようにプロセッサに指示するためのコンピュータプログラムであって、前記方法は、
前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、
前記選択したマークの各位置に関する回転の中心を判定するステップと、
前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、
各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有することを特徴とするコンピュータプログラム。
【請求項１】
画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法であって、
前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、
前記選択したマークの各位置に関する回転の中心を判定するステップと、
前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、
各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有することを特徴とする方法。
【請求項２】
前記識別された一群の間隔及び向きを判定するステップと、
前記識別された一群の前記間隔及び前記向きに基づいて予想されるマークの場所の集合を判定するステップと、
前記予想されるマークの場所のうち、少なくとも所定の割合の場所が前記コンピュータ読み取り可能なマークの構成におけるマークの場所と一致する場合、前記配置マークの識別された一群を検証するステップとを更に有することを特徴とする請求項１に記載の方法。
【請求項３】
前記コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合であることを特徴とする請求項１に記載の方法。
【請求項４】
前記コンピュータ読み取り可能なマークは、ドット、ドット群、円、正方形及び三角形から構成されるマーク群から選択されることを特徴とする請求項１に記載の方法。
【請求項５】
前記基準グリッドは矩形グリッドであり、２つのマークは前記コンピュータ読み取り可能なマークの構成から選択され、前記回転の中心を判定することは前記２つの選択したマーク間で場所を特定される点を識別することを特徴とする請求項１に記載の方法。
【請求項６】
前記基準グリッドは三角形グリッドであり、前記回転の中心を判定することは前記選択したマークのうちの一方を前記回転の中心として割り当てることを特徴とする請求項１に記載の方法。
【請求項７】
前記判定した間隔及び向きに基づいて、前記コンピュータ読み取り可能なマークの構成から追加のマークを組み込むために前記識別された一群を拡張するステップを更に有することを特徴とする請求項２に記載の方法。
【請求項８】
前記基準グリッドを識別するために前記識別された一群を利用するステップと、
前記識別された基準グリッドに基づいて前記コンピュータ読み取り可能なマークの構成において前記データ搬送マークを識別するステップと、
前記識別されたデータ搬送マークを復調するステップとを更に有することを特徴とする請求項１に記載の方法。
【請求項９】
画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するコンピュータにより実現される方法であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法であって、
前記コンピュータ読み取り可能なマークの構成から選択される少なくとも２つのマークの少なくとも１つの組み合わせに対して、
（ａ）前記組み合わせの前記選択されたマークの各位置に関する回転の中心を判定するステップと、
（ｂ）前記選択されたマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記組み合わせの前記選択されたマークに対する回転位置を判定するステップと、
（ｃ）各回転位置に対して、前記回転位置に最近接するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
（ｄ）前記回転位置のうち、少なくとも所定の割合の回転位置に対して前記回転位置に最近接する前記マークが前記回転位置から所定の閾値未満の位置にある場合、前記組み合わせの前記選択されたマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有することを特徴とする方法。
【請求項１０】
前記コンピュータ読み取り可能なマークの構成は、画像において低可視バーコードを形成するマークの部分集合であることを特徴とする請求項９に記載の方法。
【請求項１１】
走査済画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群を識別するように構成されたコピー機であり、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調されるコピー機であって、
前記走査済画像を取得するスキャナと、
コンピュータプログラムを格納する記憶装置と、
前記コンピュータプログラムを実行するプロセッサとを有し、前記コンピュータプログラムは、
前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、
前記選択したマークの各位置に関する回転の中心を判定するステップと、
前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、
各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを前記プロセッサに実行させることを特徴とするコピー機。
【請求項１２】
前記コンピュータプログラムは、
前記識別された一群に基づいて前記基準グリッドを識別するステップと、
前記識別された基準グリッドに基づいて前記コンピュータ読み取り可能なマークの構成において前記データ搬送マークを識別するステップと、
前記識別されたデータ搬送マークを復調するステップとを更に前記プロセッサに実行させることを特徴とする請求項１１に記載のコピー機。
【請求項１３】
前記コンピュータプログラムは、前記復調したデータ搬送マークに基づいて前記走査済画像の複写を許可するステップを更に前記プロセッサに実行させることを特徴とする請求項１２に記載のコピー機。
【請求項１４】
画像において配置マーク及びデータ搬送マークを含むコンピュータ読み取り可能なマークの構成内で配置マークの一群が識別され、前記配置マークが前記コンピュータ読み取り可能なマークの構成内で基準グリッドを規定し、前記データ搬送マークがデータを符号化するために前記基準グリッドに関して変調される方法を実行するようにプロセッサに指示するためのコンピュータプログラムであって、前記方法は、
前記コンピュータ読み取り可能なマークの構成から少なくとも２つのマークを選択するステップと、
前記選択したマークの各位置に関する回転の中心を判定するステップと、
前記選択したマークの各々を前記回転の中心に関して所定の角度だけ回転することにより前記選択したマークに対する回転位置を判定するステップと、
各回転位置に対して、前記回転位置から所定の閾値未満の位置を有するマークの場所を前記コンピュータ読み取り可能なマークの構成から特定するステップと、
前記選択したマーク及び前記場所を特定したマークを前記配置マークの一群として識別するステップと、
前記データ搬送マークを復号化する際に使用するために前記識別された一群を格納するステップとを有することを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図６】
【図１４】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図６】
【図１４】
【図２１】
【公開番号】特開２００９−１５３１２７（Ｐ２００９−１５３１２７Ａ）
【公開日】平成２１年７月９日（２００９．７．９）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−３２０１５７（Ｐ２００８−３２０１５７）
【出願日】平成２０年１２月１６日（２００８．１２．１６）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２１年７月９日（２００９．７．９）
【国際特許分類】
【出願番号】特願２００８−３２０１５７（Ｐ２００８−３２０１５７）
【出願日】平成２０年１２月１６日（２００８．１２．１６）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]