JP2008181501A - バーコードパターン - Google Patents

Abstract

【課題】複数のマークを使用して文書内の情報を符号化する方法を提供する。
【解決手段】文書内の情報は第１のデータおよび第２のデータを備え、その方法は、第１の繰り返し率６６０で互いに離間された対応する第１の複数のタイル６１０内に配置された第１の複数の変調されたマークの配列を使用して第１のデータを符号化するステップと、第２の繰り返し率６７０で互いに離間された対応する第２の複数のタイル６８０内に配置された第２の複数の変調されたマークの配列を使用して第２のデータを符号化するステップとを備え、第２の繰り返し率は第１の繰り返し率と異なり、第２の複数のタイルは第１の複数のタイル内に組み込まれている。
【選択図】図６

Description

本発明は、印刷ページ上のコンピュータ可読マークに関し、具体的には、高いデータ密度を有し、人間の目に対して低い可視性を有するコンピュータ可読マークに関する。

印刷ページ上のコンピュータ可読マークは一般的であり、一般的なバーコードなどのいくつかの種類が広く使用されており、この手法は３０〜６０ビットのデータ記憶を提供する。一般的なバーコードは、文書ページ上で少なくない量のスペースも費やす。さらに、典型的には一般的なバーコードはページを見る人にはっきり見える。

本発明の目的は、既存の構成の１つまたは複数の欠点を実質的に克服するまたは少なくとも改善することである。

多重チャネル変調型マーク符号化構成（または単にＭＣＭＭＥ構成）と呼ばれる構成が開示されている。

１つの例ではＭＣＭＭＥ構成は、「ＭＣＭＭＥバーコード」（単に「バーコード」とも呼ばれる）を使用して、ページの大きな場所を費やすことなく有用な量のデータ内容を搬送することをサポートする。これは、より多くのページを、人が読める内容のために空けておく。ＭＣＭＭＥ構成は、折り畳み、しわ寄せ、しみ、引き裂きを含めて、印刷ページが一般的に受ける扱いに対してかなり堅牢でもある。さらに、ＭＣＭＭＥ構成は、様々なレベルの堅牢さを有することができる複数のデータメッセージストリームをサポートする。

本発明の第１の態様により、複数のマークを使用して文書内の情報を符号化する方法が提供されており、前記情報は第１のデータおよび第２のデータを備え、その方法は、
第１の繰り返し率で互いに離間された対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して第１のデータを符号化するステップと、
第２の繰り返し率で互いに離間された対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して第２のデータを符号化するステップと
を備え、
第２の繰り返し率は第１の繰り返し率と異なり、
第２の複数のタイルは第１の複数のタイル内に組み込まれていることを特徴とする。

本発明の他の態様により、複数のマークを使用して文書内で符号化された情報を復号する方法が提供されており、前記情報は第１のデータおよび第２のデータを備え、第１のデータは第１の繰り返し率で互いに離間された対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して符号化されており、第２のデータは第２の繰り返し率で互いに離間された対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して符号化されており、第２の繰り返し率は第１の繰り返し率と異なり、第２の複数のタイルは第１の複数のタイル内に組み込まれている、その方法は、
グリッド交点が第１のデータを符号化する複数のマークの名目上の位置を表すグリッドの位置および方向を第１の繰り返し率を使用して決定するステップと、
グリッド交点が第２のデータを符号化する複数のマークの名目上の位置を表すグリッドの位置および方向を第２の繰り返し率を使用して決定するステップと、
第１のデータを符号化する複数のマークおよび第２のデータを符号化する複数のマークを復調し、それによって情報を再生するステップと
を備えることを特徴とする。

本発明の他の態様により、複数のマークを使用して文書内の情報を符号化するための装置が提供されており、前記情報は第１のデータおよび第２のデータを備え、前記装置は、
プログラムを格納するメモリと、
プログラムを実行するプロセッサと
を備え、前記プログラムは、
第１の繰り返し率で互いに離間された対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して第１のデータを符号化するコードと、
第２の繰り返し率で互いに離間された対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して第２のデータを符号化するコードと
を備え、
第２の繰り返し率は第１の繰り返し率と異なり、
第２の複数のタイルは第１の複数のタイル内に組み込まれていることを特徴とする。

本発明の他の態様により、複数のマークを使用して文書内で符号化された情報を復号する装置が提供されており、前記情報は第１のデータおよび第２のデータを備え、第１のデータは、第１の繰り返し率で互いに離間された対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して符号化されており、第２のデータは、第２の繰り返し率で互いに離間された対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して符号化されており、第２の繰り返し率は第１の繰り返し率と異なり、第２の複数のタイルは第１の複数のタイル内に組み込まれている、前記装置は、
プログラムを格納するメモリと、
プログラムを実行するプロセッサと
を備え、前記プログラムは、
グリッド交点が第１のデータを符号化する複数のマークの名目上の位置を表すグリッドの位置および方向を第１の繰り返し率を使用して決定するコードと、
グリッド交点が第２のデータを符号化する複数のマークの名目上の位置を表すグリッドの位置および方向を第２の繰り返し率を使用して決定するコードと、
第１のデータを符号化する複数のマークおよび第２のデータを符号化する複数のマークを復調し、それによって情報を再生するコードと
を備えることを特徴とする。

本発明の他の態様により、上記の方法のうちのいずれか１つを実行するコンピュータプログラムを記録したコンピュータ可読媒体を含むコンピュータプログラム製品が提供されている。

本発明の他の態様も開示されている。

添付図面のうちのいずれか１つまたは複数において同一の参照番号を有するステップおよび／または特徴が参照される場合、この説明の目的のためにそれらのステップおよび／または形状は、反対の意図が明白でない限り同一の機能または動作を有する。

開示されたＭＣＭＭＥ構成は、２つのデータチャネルを単一のドットパターンに符号化することに関し、ここでドットパターンは変調型のドットグリッドである。第１の構成では、ドットパターンはいかなる位置合せマークも同期化マークも有しない。

１．基本構造
図１は、基準グリッド１０５に対する保護マークの変調型配列１０４の図を示す。保護マークの変調型配列１０４は、重心が（正方形）グリッド１０５の対応する交点１０６（単にグリッド交点とも呼ばれる）に近接して位置する多数のマーク（開示された例では１０２などのドットである）から成る。それが当該のページ上に組み込まれるのはドット１０２の配列１０４だけであり、グリッド１０５はドット１０２の配置を説明するためにだけ示されている。したがって、グリッドは「仮想グリッド」と見なされることができる。変調型配列１０４の外観は、変調されていないドットの配列の外観と類似しているがそれと同一ではない。

図２は、変調されていないドットの配列２０４の外観を示す。変調されていない配列２０４内でドット２０２、２０５（例えば）の各重心は規則的なグリッドを形成し、これらの重心は（仮想）グリッド２０６の各交点２０８、２０７上に位置する。これらのグリッドの交点はドットの名目上の（変調されていない）位置を表す。本明細書では「グリッド間隔（grid spacing）」と呼ばれる正方形グリッド２０６のピッチが矢印２０３によって示されている。グリッド２０６は、２０９などのグリッド正方形を説明する。

図２に示されるように、ドットが変調されていない配列内に形成される場合、図２の変調されていないドットの配列２０４と、図１の変調型のドットの配列１０４と、の差異は、変調型の配列１０４のドットの位置が、ドットが占めるであろう各グリッド交点の位置から変調される（すなわち、空間的に変調される、または図示の例では空間的に移動される）ことである。この変調はいくつかの目的にかなう。１つの目的は、変調型のドット１０２の配列１０４を規則的な配列２０４のドットより人間にわずかに見えにくくすることである。これは、人間の視覚系が規則的な配列を認識することに長けているためである。変調の他の目的は、メッセージをデジタルデータの形式でドットの変調に格納することを可能にすることである。

図３は、図１でのドットの変調をより詳細に示す。３０２などのドットは、規則的なグリッド３０６の対応する交点３０５に近接して位置し、各ドットは、３０３などの８つの可能な位置のうちの１つに変調される。この例では、各ドットに関する８つの可能な変調位置は関連のグリッド交点３０５を中心とした円に配置される。８つの変調位置は、グリッド交点３０５から水平に、垂直に、または対角線上にオフセットされる。ドットがオフセットされる水平距離および垂直距離は、変調量子３０４と呼ばれ、本明細書では「ｍｑ」と略される。

図４は、ドットの変調位置をより詳細に示す。ドットの変調位置は、グリッド４０２のグリッド交点４０４を中心とし、４０１などの各変調位置はそれに関連したデジタルコード値４０３を有する。したがって、８つの変調位置（４０１を含む）により、各ドットは８つの可能なデジタルコード値（４０１に対する４０３を含む）のうちの１つを符号化することができる。この構成によって、変調型のマークの配列はデジタルデータ記憶として動作することができ、変調型配列の各ドットは例示の例では１つの８進数字のデータを格納する。１つの構成では各ドットは、ドットがグレイコードで円に配置されるようにコード値を符号化する。これは、ドットに符号化された情報が復調およびデータ復旧によって再生される復号中の誤り訂正を容易にする。図４は、グリッド交点４０４に関連した各変調位置に関連するデジタルコード値をバイナリ形式で示す。したがって、４０３から時計回りに開始するとドットは１０進値の５、７、６、２、３、１、０、および４を符号化する。

図５は、開示されたＭＣＭＭＥ構成を使用してデジタルデータ記憶の数字を配列するための１つの構成を示す。説明された例では、配列は図示された長方形のドットの配列を使用することによって提供される。この配列は、最上端で最左端のドット５０１で開始し、最下端で最右端のドット５０３に達するまで左から右に進み、次いで上から下へ進む。もちろん、他の配列を使用することが可能である。他のグリッドの構成（図１および図２に示された通常の正方形以外）を使用することも可能である。他の空間的な変調位置の構成（図３および図４に示された円形以外）を使用することもできる。

符号器
図６は、繰り返しのタイル型の方法で配置された符号化されたＭＣＭＭＥバーコード（単に、バーコードとも呼ばれる）を示す。図６に示されるバーコードは、バーコードパターンとも呼ばれる。ＭＣＭＭＥバーコードは、「ＭＣＭＭＥタイル」または単に「タイル」と呼ばれる正方形タイル６９０、６９２、６９４および６９６から構成される。ＭＣＭＭＥバーコードでの各タイルは、２つのデータチャネル、すなわち高データ密度（本明細書では「ＨＤＤ」と呼ばれる）チャネルおよび低データ密度（本明細書では「ＬＤＤ」と呼ばれる）チャネルに関するデータを搬送する。前述のデータは、変調されたマークをタイルの中に適切に配置することによってタイルに組み込まれる。他のチャネル数がＭＣＭＭＥ手法を使用してサポートされてもよい。説明された例では、ＬＤＤおよびＨＤＤチャネルに関するページ上でのドット密度（すなわち平方ｃｍあたりのドット）は同一である。しかし、ＬＤＤおよびＨＤＤチャネルに関する情報量は、使用されるタイルの相対的サイズにより異なる。

説明された例では、ＨＤＤチャネルは低い堅牢性（robustness）を有するが、ＬＤＤチャネルは高い堅牢性を有する。

バーコード内で６９０などの各タイルは、単に「ＬＤＤタイル」と呼ばれる小さいＬＤＤの正方形タイル６１０のいくつかのコピーを含む。例えば、６１０、６３０および６５０はＬＤＤタイルの同一のコピーである。各（正方形）ＬＤＤタイルは６６５のサイズ（本明細書では「ＬＤＤタイルサイズ」と呼ばれる）を有する。さらに、バーコード内で各タイルは、タイル内での残りの部分（すなわち、ＭＣＭＭＥタイル内でＬＤＤタイルの部分より少ないＭＣＭＭＥタイルの部分）を備える大きいＨＤＤタイルの単一のコピーを含む。例えば、６２０、６４０および６８０はＨＤＤタイルの同一のコピーである。したがって、ＨＤＤタイルはＬＤＤタイルの上部に「オーバレイ」される、または代替としてＬＤＤタイルはＨＤＤタイルと重なる、または代替としてＬＤＤタイルはＨＤＤタイル内に組み込まれる。

要約すると、各ＭＣＭＭＥタイル（６９０など）はいくつかのＬＤＤタイル（６１０など）を含む。タイル内で含まれるＬＤＤタイルの部分の合計よりも小さいＭＣＭＭＥタイル６９０の残りの部分は、当該のＭＣＭＭＥタイルに関連するＨＤＤタイルを構成する。データ搬送波の観点から、図６に示されるバーコードの例ですべてのＬＤＤタイルは同一データを搬送し、それによってＬＤＤデータチャネルの破損に対する冗長性をもたらす。さらに、図６に示されるバーコードの例ですべてのＨＤＤタイルは同一データを搬送し、それによってＨＤＤデータチャネルの破損に対する冗長性をもたらす。

特定の形状のタイルがこの例で説明されているが、他の形状がＭＣＭＭＥタイル、ＬＤＤタイル、およびＨＤＤタイルのために使用されることができる。

第１の構成ではバーコードは、人間にドットパターンとして見える各ドットの配列の形式でＬＤＤチャネルおよびＨＤＤチャネルを符号化する。グリッド正方形の整数倍で測定された連続したＬＤＤタイル間の距離（すなわち、タイルが離間されている距離）が６６０である（本明細書では「ＬＤＤステップサイズ」と呼ばれる）。距離６６０はＬＤＤ繰り返し率とも呼ばれる。ＬＤＤステップサイズの倍数で測定された連続したＨＤＤタイル間の距離（ＨＤＤタイルサイズがＬＤＤステップサイズでない場合、異なる間隔が調査される必要があるので複数のより多くの処理が必要とされる）は６７０である（本明細書では「ＨＤＤタイルサイズ」と呼ばれる）。距離６７０はＨＤＤ繰り返し率とも呼ばれ、すなわちタイルが離間されている距離である。図６に示されるバーコードの例は、２ＬＤＤステップサイズ×２ＬＤＤステップサイズのＨＤＤタイルサイズを有し、ここでＨＤＤタイルはＨＤＤタイルサイズの距離だけ離れており、各タイル内で各ＬＤＤタイルは「ＬＤＤステップサイズ」の距離だけ離れている。

開示されたＭＣＭＭＥ構成のこの例により、図６に示されたバーコードはいくつかのＭＣＭＭＥタイルを含み、それぞれは１つのＨＤＤタイルといくつかのＬＤＤタイルを含む。

図７は、各ＬＤＤメッセージおよびＨＤＤメッセージに関連するＬＤＤデータおよびＨＤＤデータを単一のＭＣＭＭＥバーコードに符号化する方法７００を示す。その方法はステップ７１０で始まり、ここでＬＤＤステップサイズおよびＨＤＤタイルサイズが計算される。ＬＤＤタイルサイズは一定である。第１の構成は１０のＬＤＤタイルサイズを有する。ステップ７１０は、符号化されるべきＬＤＤメッセージおよびＨＤＤメッセージのサイズに基づいて最適のＬＤＤステップサイズおよびＨＤＤタイルサイズを決定する。ＬＤＤステップサイズおよびＨＤＤタイルサイズが、ＬＤＤタイルの冗長度を最大限にし、ＨＤＤタイル内の未使用データを最小限に抑えるように計算されることが理想的である。グリッド正方形で測定されたＬＤＤステップサイズ用に設定した最小値および最大値があり、ＬＤＤステップサイズで測定されたＨＤＤタイルサイズ用に設定した最小値および最大値がある。範囲は、ＭＣＭＭＥバーコードを復号するためにＬＤＤステップサイズおよびＨＤＤタイルサイズを計算するときに調査区域を狭くするために使用される。第１の構成では範囲は、
１６≦ＬＤＤステップサイズ≦３０
２≦ＨＤＤタイルサイズ≦７
である。

リードソロモンまたは低密度パリティ検査（ＬＤＰＣ）などの誤り訂正符号（ＥＣＣ）が、ＬＤＤメッセージおよびＨＤＤメッセージの符号化中に使用されることができる。ＥＣＣは、符号化段階と復号段階との間でもたらされるチャネルエラーを克服するためにデジタル通信システムで使用される。強いＥＣＣを使用すると、バーコードを有する文書の折り畳み、しわ寄せ、しみ、引き裂きおよび汚損によってもたらされうる誤りに対してバーコードを極めて堅牢にすることができる。第１の構成ではＬＤＰＣは、その反復誤り訂正の特性により符号化中に使用されている。

符号化中のＥＣＣの使用はＭＣＭＭＥ符号化プロセスに対して任意選択である。符号化中にＥＣＣを使用するためには、ＥＣＣ符号化が元のＬＤＤメッセージに適用されて最終の（符号化された）ＬＤＤメッセージを得る。

次に、ステップ７２０はＬＤＤメッセージを３ビットのデジタルコード値（「間隔」とも呼ばれる）に変換する。これは、最終の（符号化された）ＬＤＤメッセージを３ビットのグループに分割し、各３ビットのグループをその対応するデジタルコード値に変換する必要がある。

後続のステップ７３０は、同一の方法でＨＤＤメッセージをデジタルコード値に変換する。ＥＣＣが符号化のために使用される場合、ＨＤＤメッセージは、最終の（符号化された）ＨＤＤメッセージを得るためにＥＣＣを使用して符号化される。次いで、最終のＨＤＤメッセージは３ビットのグループに変換され、各３ビットのグループはその対応するデジタルコード値に変換される。

後続のステップ７４０は、ステップ７２０および７３０からの各ＬＤＤデジタルコード値およびＨＤＤデジタルコード値を単一のバーコードに配置する。単一のバーコードは、ステップ７１０で計算されたＬＤＤステップサイズおよびＨＤＤタイルサイズを使用して、図６に示される形式と類似した一般的な形式を有する。

最後に、後続のステップ７５０は、バーコード内のすべてのデジタルコード値を同一のグリッド間隔およびｍｑを有するグリッドに関連する配列内での各変調型ドットに変換する。第１の構成では、バーコードタイルは低い可視性のバーコードを形成するようにページにわたって繰り返される。しかし、バーコードは、ページの全体部分を包含する必要はなく、バーコードの一部の部分を包含するテキスト情報または他の情報を有することができる。
復号器
図８は、入力画像に符号化されたＭＣＭＭＥバーコードを復号する方法８００の一例を示す。ステップ８１０は、入力画像を取り込み、ＭＣＭＭＥ符号化手法を使用して画像上に符号化されたドットを検出する。後続のステップ８１０では、バーコードを備える検出されたドットの位置が座標データのリスト内に記録される。したがって、ステップ８１０は、バーコードを備えるドットについての情報を抽出する。ステップ８１０は、走査された画像の結合した成分解析を使用して実行されることができる。この種の解析では、画像の個々の画素は、空間的に隣接しているそれらの画素を結合しグループ化するために調査される。その形状に関して一群の画素を解析することによって、マークの存在（すなわち、円形ドットまたは適切な予想されるサイズの画素の概して一様なブロブ）が検出されることができる。次いで、マークの重心は、検出されたマーク（ドット）に対応する座標位置を識別するために決定されることができる。

次に、図８に戻って参照すると、後続のステップ８２０は、画像内にステップ８１０で検出されたドットの配列用のグリッド交点を配置する。基本的グリッドが配置されると、後続のステップ８３０はＬＤＤメッセージを復号し、ステップ８４０はバーコード内に符号化されているＨＤＤメッセージを復号する。

２．ナビゲーション
図９は、ステップ８２０（図８参照）をより詳細に示す。図９は、信頼性示度を使用してバーコード内に基本的グリッドを配置する方法（本明細書では「グリッドナビゲーション」と呼ばれる）を示す。処理は、グリッドを伸ばし始める開始点を識別するステップ９０５で始まる。開始点は、入力画像上でバーコード内のどこかであってよい。しかし、第１の構成では開始点はバ−コードの中心であるように選択される。次に、ステップ９１０は、グリッド間隔およびグリッドの方向を決定する。

ステップ９１０で、グリッド間隔およびグリッドの方向は下記のように決定される。開始点からプロセス２５００は次いで、画像内のドットを使用して開始点に対応するグリッド間隔および方向を検出する。プロセス２５００は、図２５に対してここでより詳細に説明される。プロセスは最初のステップ２５０１で始まる。後続のステップ２５０３では、グリッド方向が画像内のドットの座標から計算される。このステップは、後でより詳細に説明される。グリッド方向が計算されると後続のステップ２５０５は、画像内ですべてのドットの座標に対して回転を加える。回転はグリッド方向の角度だけ回転され、それによって回転されたドットの座標は、ｘ軸およびｙ軸と位置合せされたグリッド軸を有することになる。回転されたドットの座標を考慮に入れて後続のステップ２５０７はグリッド間隔を計算する。後続のステップ２５１１はプロセス２５００を終了する。

ステップ２５０３がここでより詳細に議論される。図２６を参照して、ステップ２５０３はドットのグリッド方向を検出するプロセス２６００から成る。プロセスはステップ２６０１で始まる。

後続のステップ２６０２は、ドットごとにどの他のドットがそれに最も近いかを計算する。これは、画像内のすべてのドットに対してなされる。所与のドットに対して最も近いドットを見いだす方法は当業者には明らかである。１つの簡単な方法は、他のドットそれぞれを順に考慮し、所与のドットに対するその距離を計算し、次いで計算された距離が最も小さかったドットを取ることである。好ましい実装形態ではより高速の方法が、全体の画像が多くの「バケット」に分割される場合に使用される。各ドットは、その位置を包含するバケットに割り当てられる。所与のドットに最も近いドットを見いだすために、所与のドットを包含するバケットで開始し、その周りの各バケット内のすべてのドットを見て、所与のドットに最も近いドットを取る。ドットが周りのバケットのいずれにも存在しない場合、調査は、放射状の外向きに次に最も近いバケットの組などに対して継続される。この方法は、最も近いドットを求めて考慮される候補のドット数を非常に低減する。

後続のステップ２６０３は、ステップ２６０２で見いだされた各ドットからその最も近い他のドットへの変位ベクトルを計算する。したがって、あらゆるドットは、それ向けに計算された対応する変位ベクトルを有する。

後続のステップ２６０４は、ステップ２６０３で計算された変位ベクトルごとにその変位ベクトルの角度を計算する。ベクトルの角度θは当業者にはよく知られており、次のように計算されることができる。

θ＝ａｔａｎ２（ｙ，ｘ）
ここで、ｘおよびｙはベクトルの水平成分および垂直成分である。後続のステップ２６０５は、以下のように定義される変数ＡおよびＢの値を計算する。

ここでθ_ｉは、ステップ２６０４で見いだされた変位ベクトルの角度である。和がすべての変位ベクトルにわたって取られる。

次いで、後続のステップ２６０６が式を使用してグリッド方向の角度φを計算する。すなわち、
φ＝ａｔａｎ２（Ｂ，Ａ）／４
したがって、ステップ２６０６で検出されたグリッド方向は−４５度〜４５度の範囲内にある。後続のステップ２６０７はプロセス２６００を終了する。

ステップ２５０７がここでより詳細に考慮される。ステップ２５０７は、図２７に示されるようにプロセス２７００を実行する。プロセス２７００はグリッド間隔を計算する。プロセスはステップ２７０１で始まる。

後続のステップ２７０２は、ステップ２５０５で検出された回転されたドットのリストを入力として取り込む。ドット（ｘ、ｙ）ごとに、同一の水平行上でその右側にある最も近い隣接ドットが見いだされる。これを行うために下記の試行錯誤（heuristic）法が使用される。(ｘ、ｙ)ではないあらゆるドット（ａ、ｂ）が考慮され、（ａ、ｂ）が、（ｘ、ｙ）の右側にある９０度の扇形外にある場合、（ａ、ｂ）は拒否される。正式には、
ａ−ｘ≦０、または ｜ａ−ｘ｜≦｜ｂ−ｙ｜
である場合、ドット（ａ、ｂ）は拒否される。残されているドットについて、下記の関数を最小限に抑えるドットが見いだされる。

ｄ（ａ，ｂ）＝｜ａ−ｘ｜＋２｜ｂ−ｙ｜
このドットは、（ｘ、ｙ）の右側にあるドットであると取られ、右側の隣接ドットのリストに格納される。

後続のステップ２７０３は、見いだされた右側の隣接ドット（ａ、ｂ）のそれぞれを取り込み、（ｘ、ｙ）から差分ベクトル（ｄｘ、ｄｙ）を計算する。すなわち、
（ｄｘ，ｄｙ）＝（ａ，ｂ）−（ｘ，ｙ）
（ｄｘ，ｄｙ）は差分ベクトルのリスト内に格納される。結果を視覚化する助けをするために、図２８は差分ベクトルのリストのグラフを示す。２８０１はｙ軸であり、２８０２はｘ軸であり、円（例えば、２８０３）は差分ベクトルの終点である。通知すべき重要な特徴は、グリッドでの雑音および歪みにより２８０４などのいくつかの誤って配置された範囲外の点があることになる。

後続のステップ２７０４は、各差分ベクトルのｘ縦座標を取り、ｘ値の周波数ヒストグラムを生成する。図２９はヒストグラムを示す。２９０１は周波数軸であり、２９０２はｘ縦座標軸であり、２９０３は周波数バーである。ｘ縦座標軸で各量子のサイズはドット座標の細分度に関係すべきである。我々のシステムでは、量子はグリッド座標軸システムの０．５であるように選択されている。

後続のステップ２７０５は、グリッド間隔を計算するためにこのヒストグラムを使用する。右側の隣接ドットの大部分は、グリッドの間隔のまわりに密集されることは留意されたい。したがって、グリッド間隔は、２９０４として示される最も頻度の高いｘ縦座標のｘ値を取ることによって見いだされる。

後続のステップ２７０６はプロセス２７００を終了する。

図９を参照すると、ステップ９１０の後、ステップ９２０はグリッドフィッティングを使用して開始点に最も近いグリッド交点Ｘ_ｓｐを識別する。グリッドフィッティング(grid-fittin)g)は図１０に関してさらに詳細に説明される。

後続のステップ９３０は、開始グリッド交点のすべての隣接点の信頼性を計算する。つまり、Ｘ_ｓｐの４つの直近の隣接するグリッド交点の近似の位置が決定される（ステップ９１０で計算されたグリッド間隔を使用して）。次いで、グリッドフィッティング（図１０参照）が、各隣接点の推定されたグリッド交点および関連した信頼性示度を計算するために使用される。各推定されたグリッド交点およびその関連した信頼性示度は信頼性プール(confidence pool)に追加される。信頼性示度(confidence measure)は、所与の画素位置に最も近いグリッド交点の計算に対するアルゴリズムの信頼性の示度である。第１の構成では、信頼性（ｃｏｎｆ）は以下により測定される。

ｃｏｎｆ＝ｍｉｎ（｜ｘＯｆｆｓｅｔ｜，｜ｙＯｆｆｓｅｔ｜）
ここで、｜ｘＯｆｆｓｅｔ｜はｘＯｆｆｓｅｔのフェーザ(phasor)の長さであり（「グリッドフィッティング」の項で定義されるように）、
｜ｙＯｆｆｓｅｔ｜はｙＯｆｆｓｅｔのフェーザ(phasor)の長さである（「グリッドフィッティング」の項で定義されるように）。

次に、ステップ９４０は、最も高い信頼性示度を有するグリッド交点Ｘ_ｈを選択する。後続のステップ９５０は、処理されたグリッド交点のリスト内にＸ_ｈを記録し、信頼性プールからＸ_ｈを除去する。各グリッド交点は関連したグリッド座標を有する。さらに、グリッド交点に最も近いドットが見いだされ、グリッド交点からのその変位（本明細書では「オフセットベクトル」と呼ばれる）が格納される。グリッド交点に近いドットがないことが可能である。

次に、ステップ９６０は、Ｘ_ｈのすべての隣接点に対する信頼性を計算する。つまり、ステップ９３０と同様に、Ｘ_ｈの４つの直近の隣接点の近似位置が決定される（ステップ９１０で計算されたグリッド間隔を使用して）。処理されたグリッド交点のリスト内に既に存在しないＸ_ｈの隣接点だけがステップ９６０で処理されることを留意されたい。次いで、グリッドフィッティング（図１０参照）が、各隣接点の推定されたグリッド交点および関連した信頼性の値を計算するために使用される。各推定されたグリッド交点およびその関連した信頼性の値が信頼性プールに追加される。後続のステップ９７０で、処理すべき信頼性プール内により多くのグリッド信頼性がある場合（グリッド信頼性が最低閾値を超えている場合）、処理はステップ９４０に進む。そうでない場合、方法は終了する。

３．局部のグリッドフィッティング
局部のグリッドフィッティングのための方法がここでより詳細に説明される。本明細書で説明されるグリッドフィッティングは、グリッド交点が見いだされるプロセスである。グリッド交点は、局部の領域を調査し、局部の領域内でドットに最適であるグリッドの変換を見いだすことによって見いだされる。次いで、入力点に最も近いグリッド交点が決定される。

グリッドフィッティングでは初期化ステップは、第１のグリッド交点が必要とされる前に実行される。この初期化ステップはいくつかの数字を事前に計算する。グリッド交点を推定するステップは事前に計算した情報を使用する。

事前に計算した情報は、グリッド間隔およびグリッドの方向に依存する。したがって、各グリッドナビゲータは、事前に計算した情報をそれ自体で格納し、それ自体の初期化を実行しなければならない。

初期化プロセス１０００はここでより詳細に説明される。図１０に示される初期化プロセス１０００はステップ１０２０で始まる。ステップ１０２０でプロセス１０００は、バーコード画像内のあらゆるドット（ｘ_ｋ，ｙ_ｋ）に対してｘＮｅｗ_ｋおよびｙＮｅｗ_ｋを計算する。グリッド間隔が２πになり、グリッド方向が計算されるために下記の関係が満足される。

ここで、θはステップ９１０で検出されたグリッド方向である。

ステップ１０３０ではプロセス１０００は、バーコード画像内のあらゆるドットに対してｘ−ｐｈａｓｏｒおよびｙ−ｐｈａｓｏｒを計算する。すなわち、
ｘＰｈａｓｏｒ＝ｃｏｓ（ｘＮｅｗ_ｋ）＋ｊｓｉｎ（ｘＮｅｗ_ｋ）
ｙＰｈａｓｏｒ＝ｃｏｓ（ｙＮｅｗ_ｋ）＋ｊｓｉｎ（ｙＮｅｗ_ｋ）
ここで、ｊは−１の平方根である。

ステップ１０４０で、バーコード画像がフェーザビン（phasor bins）に分割される。好ましい実施形態ではフェーザビンは、３２×３２画素の大きさであり、画像にわたって規則的にタイル化されている。例えば、図１１は、フェーザビン（例えば、１１２０）に分割されているバーコード画像１１１０を示す。フェーザビンは、垂直（ｙ）サイズ寸法１１４０および水平（ｘ）サイズ寸法１１３０を有する。ステップ１０５０では、ビン１１２０ごとにプロセス１０００は、ビン１１２０内のドットに対応するｘ−ｐｈａｓｏｒの和を計算する。同様に、ビン１１２０ごとにプロセスはｙ−ｐｈａｓｏｒの和を計算する。これは、情報を事前に計算する初期化プロセス１０００を終了する。

図１３は、事前に計算された情報を使用してグリッド交点を計算するプロセス１３００を示す。最も近いグリッド交点が点（ｘ_ｃ，ｙ_ｃ）で求められると仮定する。方法１３００は、開始ステップ１３１０を有し、点（ｘ_ｃ，ｙ_ｃ）の周りで窓(window)が決定されるステップ１３２０で実質的に開始する。好ましくは、窓は４×４のフェーザビンのサイズを有するが他の窓のサイズが使用されてよい。窓は、中心に最も近い点（ｘ_ｃ，ｙ_ｃ）を有する４×４のフェーザビンの組であるように決定される。次に、ステップ１３３０で、ｘＯｆｆｓｅｔおよびｙＯｆｆｓｅｔの値が決定される。ｘＯｆｆｓｅｔは、窓内での４×４のフェーザビンのｘ−ｐｈａｓｏｒの和の総計である。同様に、ｙＯｆｆｓｅｔは、窓内での４×４のフェーザビンのｙ−ｐｈａｓｏｒの和の総計である。

最後に、ステップ１３４０が最も近いグリッド交点の位置を推定する。現在の画素位置を（ｘ_ｃ，ｙ_ｃ）によって示す。推定されたグリッド交点（ｘＧｒｉｄ，ｙＧｒｉｄ）は以下によって与えられる。

ここで、θはステップ９１０で検出されたグリッド方向である。

ステップ１３４０の後に方法１３００は終了する。

４．ＬＤＤ復号
図１６は、図８のステップ８３０をより詳細に示す。図１６は、バーコード内でのＬＤＤメッセージを復号する方法を示す。プロセス８３０は、ＬＤＤステップサイズを決定するステップ１６１０で始まる。これを行うために自己相関と同様の計算が、ステップ９５０で計算されるオフセットベクトルで行われる。これは、可能なステップオフセットごとに一致値を計算することから成る。ステップオフセット値は、符号器によって事前に決定された最小のＬＤＤステップサイズから最大のＬＤＤステップサイズまでの範囲に及ぶ。ステップオフセットがＬＤＤステップサイズと等しいとき、一致値は大きいことになる。

第１の構成では、所与のステップオフセットで一致値を計算する方法が図１７に示されている。他の自己相関の計算は、一致値を計算するために使用されてもよい。ステップオフセットは図１７の方法に対する入力であり、ここでステップオフセットはオフセット値である。処理は、ここで説明される内積を決定するステップ１７２０で始まる。

２つのベクトル（ｘ１，ｙ１）および（ｘ２，ｙ２）の内積が下記によって与えられる。すなわち、
（ｘ１×ｘ２）＋（ｙ１×ｙ２）
つまり、内積値は、２つのベクトルのｘ成分の積とｙ成分の積との和である。２つのベクトルの内積はスカラである。

ステップ１７２０では、いくつかの内積が計算される。初めに、バーコード内での各グリッド交点で、（ａ）グリッド交点でのオフセットベクトルと、（ｂ）「ステップオフセット」のグリッド点だけ右側に移動された後のグリッド交点でのオフセットベクトルとの内積が決定される。「ステップオフセット」グリッド点を右に移動されるオフセットベクトルがない場合、内積は計算されない。

次に、ステップ１７３０は、ステップ１７２０で計算されたすべての内積の和を計算する。ステップ１７３０で計算された和が、入力ステップオフセットに関する一致値である。

図１８は、一例のバーコードのＬＤＤステップサイズを見いだすために使用される一致値のグラフを示す。軸１８２０はステップオフセット軸であり、軸１８１０は一致値軸であり、曲線１８３０はステップオフセットに対する一致値のプロットである。グラフから、点１８４０は符号器によって使用される最小ＬＤＤステップサイズを示し、点１８５０は符号器によって使用される最大ＬＤＤステップサイズを示す。第１の構成では、以前に議論された範囲によって定義されたように１８４０は１６のグリッド正方形であり、１８５０は３０のグリッド正方形である。１８６０でのピークは１８７０によって示されるステップオフセットに対応する。したがって、１８７０は例のバーコードのＬＤＤステップサイズである。

図１６に戻ると、ＬＤＤステップサイズがステップ１６１０で計算されていると後続のステップ１６２０は、ドットオフセットベクトルをデジタルコード値に変換する。各オフセットベクトルをその対応するデジタルコード値に変換するために各交点の周りの領域は、図１９に示されるように８つの同じ大きさの角度をなす扇形に分割される。

図１９は、グリッド交点１９９５を有するグリッド１９９０がどのように８つの角度をなす扇形に分割されることができるかを示し、ここで各扇形は間隔値を表す。ドット１９１２を特徴づけるオフセットベクトル１９１４は、扇形１９１０に分類される。図４を参照すると扇形１９１０は、実際の値が５である４０３によって示されるデジタルコード値に対応する変調位置４０１に対応する。同様に、扇形１９２０、１９３０、１９４０、１９５０、１９６０、１９７０または１９８０にそれぞれ分類されるオフセットベクトルは、値７、６、２、３、１、０または４にそれぞれ対応する。

図１６に戻ると後続のステップ１６３０は、バーコードをサイズ「ＬＤＤステップサイズ」×「ＬＤＤステップサイズ」の領域に分割し、これらの領域を共に統合する。領域を共に統合するために、初めに、各デジタルコード値がその３ビット表現に変換される。次に、領域は、各領域での対応するデジタルコード値の対応するビットを結合することによって１つの統合領域に併合される。これは、領域内でデジタルコード値のビット位置ごとに統合ビット数を維持することによって行われる。統合ビット数は、統合タイル内の各位置でデジタルコード値の３ビットのそれぞれに関して維持される。統合ビット数は、そのビット位置でデジタルコード値のビットが１である総回数からそのビット位置でデジタルコード値のビットが０である総回数を引いたものに等しい。例えば、４つの領域内で対応する位置でのデジタルコード値が００１、１０１、１１１、および１０１であった場合、統合ビット数は、３つのビット位置に対応して２、−２、および４であろう。

図２０は、寸法２０５０×２０６０を有する統合領域２０１０の一例を示す。ＬＤＤステップサイズは、寸法２０５０および２０６０によって特徴づけられる。

図１６に戻ると、後続のステップ１６４０は、ステップ１６３０で得られた統合領域を使用してＬＤＤタイルの位置を見いだす。バーコードは、「ＬＤＤステップサイズ」の周期で繰り返すＬＤＤタイルの多くのコピーから成る。長さ「ＬＤＤステップサイズ」の領域を共に統合することによって、類似している統合領域の各領域内の小区域がＬＤＤタイルに対応する。類似していない他の小区域は、ＨＤＤタイルを含むバーコードの領域に対応する。言い換えれば、ビット位置の統合ビット数に関して大きい正値または大きい負値を有するビット位置が最も類似しているビット位置を示す。低い統合ビット数を有するビット位置は類似していない。したがって、ＬＤＤタイルの可能な位置ごとに、統合領域内でのＬＤＤタイルサイズ領域の統合ビット数の絶対値の和が計算される。最大の和を有する位置がＬＤＤタイルの位置である。

図２０を参照すると、統合領域内で一致するデジタルコード値を含むＬＤＤタイル２０３０（ＬＤＤタイルサイズである参照番号２０８０×２０７０によって示される一定サイズを有する）がある。つまり、２０２０で左上隅を有するＬＤＤタイルサイズ領域の統合ビット数の絶対値の和が最大の和である。したがって、ＬＤＤの左上隅が２０２０である。

ＬＤＤ位置が見いだされると統合タイルは、ＨＤＤデータを破棄するために切り取られる。図１６でプロセス８３０でのすべてのさらなるステップは切り取られた統合タイルだけに関し、切り取られた統合タイルはＬＤＤタイルだけを含む。

後続のステップ１６４５で、統合タイルは０度、９０度、１８０度および２７０度（４つの可能な方向を表す）だけ回転される。統合タイルを回転する方法が、ここで詳細に議論される。最初に、統合ビット数はそれらの回転後の位置に移動される。これは図２１に示される。

図２１は、回転していない統合タイルである２１１０と、反時計回りに９０度回転後の統合タイルである２１２０とを示す。２１２０での統合ビット数は２１４０に移動される。

次に、統合ビット数の値はそれらの回転後の値を表すように変更される。上述のように、１つの構成ではグレイ符号化がＬＤＤメッセージおよびＨＤＤメッセージを符号化するために使用される。下記のリストは、３ビット値を反時計回りに９０度だけ回転する影響を示す（ここで、ビットは最上位ビットから最下位ビットへ記載されている）。

０００→０１１
００１→０１０
０１１→１１０
０１０→１１１
１１０→１０１
１１１→１００
１０１→０００
１００→００１
例えば、１１０（すなわち、デジタルコード値「６」）が９０度だけ回転されるとき、その新しい値は１０１（すなわち、デジタルコード値「５」）である。したがって、統合ビット数をそれらの３ビットグレイコード（bit grey code）に対応するように３のグループ内にグループ化することによって、統合ビット数は下記のように回転されることができる。

ここで、
ａｇｇ＿ｂｉｔ＿ｃｏｕｎｔ_０は、間隔の最下位ビット（すなわち、第０位ビット）に対する統合ビット数であり、
ａｇｇ＿ｂｉｔ＿ｃｏｕｎｔ_１は、間隔の第１位ビットに対する統合ビット数であり、
ａｇｇ＿ｂｉｔ＿ｃｏｕｎｔ_２は、間隔の最上位ビット（すなわち、第２位ビット）に対する統合ビット数であり、
プライム値が新しいａｇｇ＿ｂｉｔ＿ｃｏｕｎｔ値である。

したがって、統合ビット数を１８０度だけ回転するために上記の式は、元の統合ビット数に２回適用される。同様に、統合ビット数を２７０度だけ回転するために上記の式は、元の統合ビット数に３回適用される。

４つの回転された統合タイルが生成されると後続のステップ１６５０は、正しいＬＤＤ方向を決定し、ＬＤＤメッセージを復号する。ステップ１６５０で決定されたＬＤＤ方向は、図９のステップ９１０で計算された方向と異なる。ステップ９１０での方向は、０度から９０度までの範囲内である。しかし、図１６のステップ１６５０でのＬＤＤ方向は、グリッドに対してドットパターンの０、９０、１８０または２７０度の方向である。

ステップ１６５０で、方向ごとに可能な符号化されたＬＤＤメッセージが決定される。具体的には、所与のビット位置に関する（回転された）統合ビット数が正である場合、ビット値は１である。そうでない場合、ビット値は０である。方向のうちの１つだけが目的にかなった復号されたメッセージを生成することになる。これは、ユーザによって決定されることができる。

あるいは、ステップ１６５０では、反復ＥＣＣ復号アルゴリズム（例えば、ＬＤＰＣまたはターボ符号の復号）が使用される場合、ＬＤＤ方向は、ＬＤＤタイルのすべての４つの方向に対してＥＣＣ復号の１つの反復を行うことによって決定される。最も少ない誤りを有する方向が正しい方向である。第１の構成では、ＬＤＰＣがＥＣＣ符号化のために使用される場合、ステップ１６４５で計算された統合ビット数が、ビット位置ごとに見込みを計算するために使用される。これらの見込み値がＬＤＰＣ復号によって使用される。ビット位置ごとの見込みは下記のように計算される。

ｌｉｋｅｌｉｈｏｏｄ＝ｂａｓｅ^{ａｇｇ＿ｂｉｔ＿ｃｏｕｎｔ}
ここで、
ｂａｓｅは定数値であり（例えば、ｂａｓｅの値は２でありうる）、
ａｇｇ＿ｂｉｔ＿ｃｏｕｎｔは所与のビット位置に関する統合ビット数である。
ＬＤＰＣの特性により、ＬＤＤタイルの正しい方向は、正しいパリティ検査の最大数を有するものである。次いで、ＬＤＤメッセージは、正しい方向に対するＬＤＰＣ復号を使用して復号されることができる。

５．ＨＤＤ復号
図２２は、ステップ８４０（図８を参照）をより詳細に示す。図２２は、ＭＣＭＭＥバーコードでのＨＤＤメッセージを復号する方法を示す。処理はステップ２２１０で始まり、ここでＨＤＤタイルサイズが計算される。ＨＤＤタイルサイズは、バーコードで自己相関を行うことによって計算され、その自己相関は様々なオフセット値に関する一致値を計算することから成る。オフセット値は、符号器によって事前に決定された最小のＨＤＤタイルサイズから最大のＨＤＤタイルサイズまでの範囲に及ぶ。最大の一致値を有するオフセットがＨＤＤタイルのサイズである。第１の構成では、各オフセット値で一致値を計算する方法は、図１７での方法に関して説明されている。他の自己相関計算が一致値を計算するために使用されてもよいことは留意されたい。

図２３は、ＨＤＤタイルサイズを計算するための一致値のグラフを示す。軸２３１０は一致値を表し、軸２３２０は様々なオフセット値を表す。点２３３０は、所与のオフセット値のプロットされた一致値である。点２３４０は符号器によって使用された最小のＨＤＤタイルサイズであり、点２３５０は符号器によって使用された最大のＨＤＤタイルサイズである。第１の構成では、点２３４０は２ＬＤＤステップであり、点２３５０は７ＬＤＤステップである。オフセット値２３７０に対応するピーク値２３６０はＨＤＤタイルサイズを表す。つまり、図２３でのＨＤＤタイルサイズは２３７０である。

図２２に戻ると、ＨＤＤタイルサイズが決定されると後続のステップ２２２０は、ＨＤＤタイル内でのオフセットベクトルをそれらの対応するデジタルコード値に変換する。ステップ２２２０は、図１６でのステップ１６２０と同様である。次に、ステップ２２３０はＨＤＤタイルを統合する（ステップ２２１０で識別されたＨＤＤタイルサイズを使用して）。ステップ２２３０は、バーコード画像を長さ「ＨＤＤタイルサイズ」の領域に分割し、これらの領域を共に統合する。領域を共に統合するために、最初に、各デジタルコード値がその３ビット表現に変換される。次に、領域は、各領域で対応するビットを結合することによって１つの統合領域に併合される。統合ビット数が、ＨＤＤタイルでのビット位置ごとに計算される。統合ビット数は、図１６でのステップ１６３０で説明されたものと同一の方法を使用して計算される。さらに、ステップ１６５０で検出された方向により統合ビット数は、図１６でのステップ１６４５で説明されたものと同一の方法を使用して回転される。

次いで、後続のステップ２２４０は、ＨＤＤ位置を見いだすために統合ＨＤＤタイルを使用する。ステップ２２１０がＨＤＤタイルサイズを識別したが、ＨＤＤタイルの開始位置は依然として知られていない。

図２４は、統合ＨＤＤタイル２４８５の一例を示す。ＨＤＤタイル２４８５は、関連した参照番号２４０５〜２４８０を有するＬＤＤタイルと２４９０と呼ばれるＨＤＤタイルから構成されている。図２４でのＨＤＤタイルサイズは４である。ＨＤＤタイルの開始位置はＬＤＤタイル２４０５〜２４８０のうちの１つで開始されるが、代替の開始位置も可能である。図２２のステップ２２４０で、反復ＥＣＣ復号が使用される場合、ＨＤＤ位置は、ＨＤＤタイルのすべての可能な開始位置に対してＥＣＣ復号の１つの反復を行うことによって決定される（図１６でのステップ１６５０と同様）。ＨＤＤタイルの開始位置は、誤りの最小数を有するものである。次いで、ＨＤＤメッセージが、正しい開始位置からＥＣＣ復号を使用して復号されることができる。

あるいは、ＥＣＣが使用されない場合、ＨＤＤ符号化ビットメッセージは、可能な復号メッセージを得るためにすべての可能な開始位置で決定されることができる。具体的には、図２２でのステップ２２３０で計算された統合ビット数を使用して、所与のビット位置に関する統合ビット数が正である場合にビット値は１である。そうでない場合、ビット値は０である。開始位置のうちの１つだけが目的にかなった復号メッセージを生成することになる。

６．拡張機能
パターン方向
このＭＣＭＭＥ構成に対する拡張機能として、符号化中にバーコードを１つの角度で回転することが可能である。理想的には、回転の角度は４５度である。バーコードが１つの角度で配置されるとき、バーコードは人間の目に見にくい。

符号化中に１つの角度で配置されているバーコードを復号するステップ８１０（図８を参照）は、１つの角度で配置されていないバーコードに対するものと同一のままである。つまり、バーコードを復号する方法は、グリッドナビゲーションのために使用される堅牢なプロセス８２０によりバーコードのすべての方向を処理することができる。

事前に定義されたＬＤＤステップサイズ
１つの代替構成では、ＬＤＤステップサイズが符号化中に事前に定義されることができる。これは符号化中に必要とされる計算量を低減する。具体的には、ステップ７１０（図７参照）中になされるべき計算がより少ない。

復号中に、ＬＤＤステップサイズが固定されている場合になされるべき計算もより少ない。つまり、ＬＤＤメッセージを復号するとき、ステップ１６１０（図１６参照）は除外されることができる。これは、復号方法の複雑さを低減する。

平衡変調（BALANCED MODULATION）
適切な平衡変調が復号器の正しい動作のために望ましい（例えば、図８参照）。図８で示される搬送波信号（すなわち、グリッド）を検出するプロセス８００は、変調がよく平衡のとれているときに最も良く動作し、変調が極めて不平衡である場合に故障しうる。ほとんどの任意に選択されたデータ内容は、適度によく平衡のとれた変調になるが、８進表現が９進数字にわたって極めて不規則に分配されているデータ内容は不規則な変調を生じることになる。

適切な平衡変調は、よく平衡のとれた固定雑音信号を用いてメッセージデータをＸＯＲ（バイナリ排他的ＯＲ）し、その後、復号した後に同一のよく平衡のとれた固定雑音信号を用いて符号化しＸＯＲすることによって保証されることができる。もちろん、固定信号を用いて元のメッセージを２回ＸＯＲすることによって、その元のメッセージに対して最終的な変化をもたらさない。よく平衡のとれた固定雑音信号を用いて元のメッセージを１回ＸＯＲすると、よく平衡のとれた固定雑音信号が元のメッセージデータと相互に関係していない限りよく平衡のとれている変更された伝送可能メッセージをもたらす。よく平衡のとれた固定雑音信号と元のメッセージデータとの間での著しい相関関係を回避すると、バイアスされていない（平衡のとれた）乱数生成器からよく平衡のとれた固定雑音信号を生成し、意図しない相関関係の可能性が無視できるほど小さいように２つの信号の長さを十分に長く選択することによって実際には容易に実現される。

チェックサム
代替構成では、チェックサム（例えば、巡回冗長検査（ＣＲＣ））が符号化中に使用されることができる。ＣＲＣは、伝送中に誤りを検出するために１つのブロックのデータに対して計算される。符号化中にチェックサムが、ＬＤＤメッセージおよびＨＤＤメッセージのために計算されることができる。各チェックサムは、それらの対応するメッセージに付加されることができる。このステップは、図７でのステップ７１０の前に実行されることができる。チェックサムは、ＥＣＣ方法（例えば、ＬＤＰＣまたはリードソロモン）に加えてまたは代わりに使用されることができる。

ＬＤＤ復号中、ステップ１６５０で（図１６参照）正しいＬＤＤ方向は、ＬＤＤチェックサムと一致する復号されたメッセージを生成する方向である。同様に、ＨＤＤ復号中、ステップ２２４０で（図２２参照）正しいＨＤＤ位置は、ＨＤＤチェックサムと一致する復号されたメッセージを生成する位置である。

説明されたＭＣＭＭＥ構成がコンピュータ業界およびデータ処理業界に適用可能であることは上記から明らかである。

前述のことは、本発明のいくつかの実施形態だけを説明し、実施形態は例示であり、限定されるものではないので修正および／または変更が本発明の範囲および精神から逸脱することなくそれらになされてよい。

ドットが規則的なグリッド上にもはや完全に配置されないように位相変調されているドットの配列を示す図である。 規則的なグリッド上に配置される規則的なドットの配列を示す図である。 ドットの変調をより詳細に示す図である。 ドットの変調をさらにより詳細に示す図である。 変調型グリッドの数字の配列を示す図である。 ＭＣＭＭＥバーコードの一例を示す図である。 ２つのデータチャネルを有するバーコードパターンを符号化するステップを示す流れ図である。 高データ密度メッセージおよび低データ密度メッセージを含むバーコードパターンを復号するステップを示す流れ図である。 バーコードパターンのグリッドを識別するステップを示す流れ図である。 グリッドフィッティングのための初期化ステップを示す流れ図である。 フェーザビンに分割したバーコード画像を示す図である。 意図的に空白である。 グリッドフィッティングするステップを示す流れ図である。 意図的に空白である。 意図的に空白である。 低データ密度メッセージを復号するステップを示す流れ図である。 所与の低データ密度ステップサイズまたは高データ密度タイルサイズに関する一致値を計算するステップを示す流れ図である。 低データ密度ステップサイズを見いだすときの一致値のグラフの一例を示す図である。 ドットオフセットベクトルのその間隔値への変換を示す図である。 低データ密度の位置を見いだすための統合領域を示す図である。 統合ビット数の反時計回りの９０度回転を示す図である。 高データ密度メッセージを復号するステップを示す流れ図である。 高データ密度タイルサイズを見いだすときの一致値のグラフの一例を示す図である。 高データ密度タイルの統合領域を示す図である。 ドットのグリッドでグリッド方向、スケールおよび変換を検出するプロセスを示す図である。 グリッド方向を計算するプロセスを示す図である。 グリッド間隔を検出するプロセスを示す図である。 右側の隣接差分ベクトルのリストのグラフを示す図である。 ｘ値の周波数ヒストグラムを示す図である。

Claims (9)

1. 複数のマークを使用して文書内の情報を符号化する方法であって、前記情報は第１のデータおよび第２のデータを備え、当該方法が、
   第１の繰り返し率で互いに離間された対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して前記第１のデータを符号化するステップと、
   第２の繰り返し率で互いに離間された対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して前記第２のデータを符号化するステップと
   を備え、
   前記第２の繰り返し率は前記第１の繰り返し率と異なり、
   前記第２の複数のタイルは前記第１の複数のタイル内に組み込まれていることを特徴とする方法。
2. 前記第１のデータを符号化する前記ステップは、前記第１の複数のタイルのそれぞれの中の前記第１のデータのすべてを符号化するステップを備え、
   前記第２のデータを符号化する前記ステップは、前記第２の複数のタイルのそれぞれの中の前記第２のデータのすべてを符号化するステップを備えることを特徴とする請求項１に記載の方法。
3. 前記第１のデータを符号化する前記ステップは、前記第１のデータに依存するそれらの名目上の位置から第１のマークの配列を空間的に移動するステップを備え、
   前記第２のデータを符号化する前記ステップは、前記第２のデータに依存するそれらの名目上の位置から第２のマークの配列を空間的に移動するステップを備えることを特徴とする請求項１に記載の方法。
4. 前記第１のマークの配列の前記名目上の位置は規則的な正方形グリッドのグリッド交点であり、
   前記第２のマークの配列の前記名目上の位置は規則的な正方形グリッドのグリッド交点であることを特徴とする請求項３に記載の方法。
5. 複数のマークを使用して文書内で符号化された情報を復号する方法であって、前記情報が第１のデータおよび第２のデータを備え、前記第１のデータは第１の繰り返し率で互いに離間した対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して符号化されており、前記第２のデータは第２の繰り返し率で互いに離間した対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して符号化されており、前記第２の繰り返し率は前記第１の繰り返し率と異なり、前記第２の複数のタイルは前記第１の複数のタイル内に組み込まれている、当該方法は、
   グリッド交点が前記第１のデータを符号化する前記複数のマークの名目上の位置を表すグリッドの位置および方向を前記第１の繰り返し率を使用して決定するステップと、
   グリッド交点が前記第２のデータを符号化する前記複数のマークの名目上の位置を表すグリッドの位置および方向を前記第２の繰り返し率を使用して決定するステップと、
   前記第１のデータを符号化する前記複数のマークおよび前記第２のデータを符号化する前記複数のマークを復調し、それによって前記情報を再生するステップと
   を備えることを特徴とする方法。
6. 複数のマークを使用して文書内の情報を符号化する装置であって、前記情報は第１のデータおよび第２のデータを備え、
   プログラムを格納するメモリと、
   前記プログラムを実行するプロセッサと
   を備え、前記プログラムは
   第１の繰り返し率で互いに離間した対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して前記第１のデータを符号化するコードと、
   第２の繰り返し率で互いに離間した対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して前記第２のデータを符号化するコードと
   を備え、
   前記第２の繰り返し率は前記第１の繰り返し率と異なり、
   前記第２の複数のタイルは前記第１の複数のタイル内に組み込まれている
   ことを特徴とする装置。
7. 複数のマークを使用して文書内で符号化された情報を復号する装置であって、前記情報が第１のデータおよび第２のデータを備え、前記第１のデータは第１の繰り返し率で互いに離間した対応する第１の複数のタイル内で配置された第１の複数の変調されたマークの配列を使用して符号化されており、前記第２のデータは第２の繰り返し率で互いに離間した対応する第２の複数のタイル内で配置された第２の複数の変調されたマークの配列を使用して符号化されており、前記第２の繰り返し率は前記第１の繰り返し率と異なり、前記第２の複数のタイルは前記第１の複数のタイル内に組み込まれている、当該装置が、
   プログラムを格納するメモリと、
   前記プログラムを実行するプロセッサと
   を備え、前記プログラムは
   グリッド交点が前記第１のデータを符号化する前記複数のマークの名目上の位置を表すグリッドの位置および方向を前記第１の繰り返し率を使用して決定するコードと、
   グリッド交点が前記第２のデータを符号化する前記複数のマークの名目上の位置を表すグリッドの位置および方向を前記第２の繰り返し率を使用して決定するコードと、
   前記第１のデータを符号化する前記複数のマークおよび前記第２のデータを符号化する前記複数のマークを復調し、それによって前記情報を再生するコードと
   を備えることを特徴とする装置。
8. 複数のマークを使用して文書内の情報を符号化する方法を実行するようにプロセッサに命令するコンピュータプログラムを記憶したコンピュータ可読の記憶媒体であって、前記情報は第１のデータおよび第２のデータを備え、前記プログラムは、
   第１の繰り返し率で互いに離間した対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して前記第１のデータを符号化するコードと、
   第２の繰り返し率で互いに離間した対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して前記第２のデータを符号化するコードと
   を備え、
   前記第２の繰り返し率は前記第１の繰り返し率と異なり、
   前記第２の複数のタイルは前記第１の複数のタイル内に組み込まれていることを特徴とする記憶媒体。
9. 複数のマークを使用して文書内で符号化された情報を復号する方法を実行するようにプロセッサに命令するコンピュータプログラムを記憶したコンピュータ可読の記憶媒体であって、前記情報は第１のデータおよび第２のデータを備え、前記第１のデータは第１の繰り返し率で互いに離間した対応する第１の複数のタイル内に配置された第１の複数の変調されたマークの配列を使用して符号化されており、前記第２のデータは第２の繰り返し率で互いに離間した対応する第２の複数のタイル内に配置された第２の複数の変調されたマークの配列を使用して符号化されており、前記第２の繰り返し率は前記第１の繰り返し率と異なり、前記第２の複数のタイルは前記第１の複数のタイル内に組み込まれている、前記プログラムは、
   グリッド交点が前記第１のデータを符号化する前記複数のマークの名目上の位置を表すグリッドの位置および方向を前記第１の繰り返し率を使用して決定するコードと、
   グリッド交点が前記第２のデータを符号化する前記複数のマークの名目上の位置を表すグリッドの位置および方向を前記第２の繰り返し率を使用して決定するコードと、
   前記第１のデータを符号化する前記複数のマークおよび前記第２のデータを符号化する前記複数のマークを復調し、それによって前記情報を再生するコードと
   を備えることを特徴とする記憶媒体。

Images