グリッド方位、変倍、平行移動及び変調の推定に関する処理方法、装置、プログラム、コンピュータ可読媒体
【課題】グリッドのグリッド方位、グリッド間隔及びグリッド平行移動を判定する計算費用の安価な改良された処理を提供する。
【解決手段】情報媒体上のドットは仮想グリッドからの変位により変調され変調グリッドとなっている。変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する処理７００が提供される。処理７００は、グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定する。処理７００は、仮想グリッドを判定するために、ベクトルを使用して変調を除去する。その後、処理７００は、判定したベクトルを使用してグリッドの向きを判定する。
【解決手段】情報媒体上のドットは仮想グリッドからの変位により変調され変調グリッドとなっている。変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する処理７００が提供される。処理７００は、グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定する。処理７００は、仮想グリッドを判定するために、ベクトルを使用して変調を除去する。その後、処理７００は、判定したベクトルを使用してグリッドの向きを判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に画像処理に関し、特にグリッド検出に関する。更に本発明は、グリッドの向き（以下、「グリッド方位」と呼ぶ）、間隔（以下、「グリッド間隔」と呼ぶ）及び平行移動（以下、「グリッド平行移動」と呼ぶ）を判定する処理及び装置に関し、また、グリッドに対するグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムを記録したコンピュータ可読媒体に関する。
【背景技術】
【０００２】
従来技術において、グリッド方位及びグリッド間隔を判定する方法が多く存在する。そのような方法は、通常、データがグリッドのような構成で格納される２次元バーコード又は透かしを位置合わせする処理の一部である。
【０００３】
従来技術の方法は、通常、自己相関(autocorrelation)又はペリオドグラム(periodogram)等の畳み込みに基づく方法(convolution-based method)を使用して、グリッド方位及びグリッド間隔を判定する。自己相関及びペリオドグラムの双方が、出力データではピークとして示される入力データの主周波数を判定する。それらピークは判定され、最大ピークの場所がグリッドの主周波数となる。グリッドのグリッド間隔及びグリッド方位は、その主周波数から判定される。
【０００４】
畳み込みに基づく方法の主な欠点は、それら方法が画像全体に対して畳み込みを実行するため、計算費用が高いことである。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、グリッドのグリッド方位、グリッド間隔及びグリッド平行移動を判定する計算費用の安価な改良された処理が必要とされる。
【課題を解決するための手段】
【０００６】
本発明の１つの面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する処理方法は、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するステップと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するステップと、
前記判定したベクトルを使用して前記グリッド方位を判定するステップとを備えることを特徴する。
【０００７】
本発明の別の面によると、符号化データに対するグリッドを判定する処理方法は、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するステップと、
前記統計平均に基づいて、前記データの角度方向を判定するステップと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するステップとを備えることを特徴する。
【０００８】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する処理方法は、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するステップと、
前記変位ベクトルを使用して前記グリッド方位を判定するステップと、
前記グリッド間隔を判定するステップと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するステップとを備えることを特徴する。
【０００９】
本発明の更に別の面によると、符号化データに対するグリッドを判定する処理方法は、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するステップと、
前記グリッドの隣接データ点の間隔を判定するステップと、
前記グリッドに関して、各データ点に対するオフセットを判定するステップとを備えることを特徴する。
【００１０】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する装置は、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するベクトル判定手段と、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去する変調除去手段と、
前記判定したベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段とを備えることを特徴する。
【００１１】
本発明の更に別の面によると、符号化データに対するグリッドを判定する装置は、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定する統計平均判定手段と、
前記統計平均に基づいて、前記データの角度方向を判定する角度方向判定手段と、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するグリッド判定手段とを備えることを特徴する。
【００１２】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する装置は、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定する変位ベクトル判定手段と、
前記変位ベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段と、
前記グリッド間隔を判定するグリッド間隔判定手段と、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するグリッド平行移動判定手段とを備えることを特徴する。
【００１３】
本発明の更に別の面によると、符号化データに対するグリッドを判定する装置は、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定する角度方向判定手段と、
前記グリッドの隣接データ点の間隔を判定する間隔判定手段と、
前記グリッドに関して、各データ点に対するオフセットを判定するオフセット判定手段とを備えることを特徴する。
【００１４】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムは、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコードとを備えることを特徴する。
【００１５】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムは、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコードとを備えることを特徴する。
【００１６】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムは、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコードと、
前記グリッド間隔を判定するコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコードとを備えることを特徴する。
【００１７】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムは、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコードと、
前記グリッドの隣接データ点の間隔を判定するコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコードとを備えることを特徴する。
【００１８】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコンピュータプログラムコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコンピュータプログラムコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードとを備えることを特徴する。
【００１９】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコンピュータプログラムコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコンピュータプログラムコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコンピュータプログラムコードとを備えることを特徴する。
【００２０】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコンピュータプログラムコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードと、
前記グリッド間隔を判定するコンピュータプログラムコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコンピュータプログラムコードとを備えることを特徴する。
【００２１】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコンピュータプログラムコードと、
前記グリッドの隣接データ点の間隔を判定するコンピュータプログラムコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコンピュータプログラムコードとを備えることを特徴する。
【発明を実施するための最良の形態】
【００２２】
（変調グリッド）
図２は、ドットの変調グリッド２００（以下、「変調グリッド２００」と呼ぶ）を形成するように位相変調(phase modulated)されたドット（例えば、２０２）の配列を示す拡大図である。変調グリッド２００は、標準正方形グリッド(square regular grid)２０１の交点（例えば、２０３）に近接する多数のドット２０２を含む。実際には、図２に示されるように、ドット２０２のみが変調グリッド２００を形成する。グリッド２０１及びその線は仮想のものであり、単にドット２０２の場所を説明するために図２に示される。
【００２３】
変調グリッド２００の外観は、ドットの標準グリッド(regular grid)３００（以下、「標準グリッド３００」と呼ぶ）を形成するように、図３に示されるような標準正方形グリッド３０１に従って配置されたドット（例えば、３０２）の外観に類似する。しかし、変調グリッド２００及び標準グリッド３００は同一のものではない。図３は、標準正方形グリッド３０１のグリッド間隔３０３を更に示す。
【００２４】
標準グリッド３００と変調グリッド２００との相違点は、変調グリッド２００におけるドット２０２の位置が、ドット２０２が標準グリッド２０１の交点２０３に従って配置される場合にドット２０２が占有するグリッド位置から離れた位置に僅かに変調されることである。この僅かな変調は、次の２つの目的を満足させる。第１に、変調により、変調グリッド２００のドット２０２は、標準グリッド３００のドット３０２よりも僅かに可視性が低くなる。これは、人間の視覚系が標準グリッドを認識することに非常に適しているからである。第２に、デジタルデータの形式のメッセージは、変調グリッド２００のようにドットを変調した際に格納される。
【００２５】
図４は、変調グリッド４００を形成するように位相変調されたドット（例えば、４０２）の別の配列を示す。ドット４０２は、標準正方形グリッド４０１の交点（例えば、４０７）に近接する。図４から分かるように、各ドット４０２は、９つの可能な位置のうち１つの位置（例えば、４０３）に変調される。各ドットの９つの可能な位置は、関連するグリッド交点４０７に集中する３×３の配列（例えば、４０５）で構成される。３×３の配列４０５の中心位置４０９は、グリッド交点４０７に位置付けられ、水平方向及び垂直方向の距離がゼロの変調に対応する。同様に、標準正方形グリッド４０１の他の交点も、交点の辺りに位置付けられる３×３の配列を有する。残りの８つの変調位置（例えば、４０３）は、水平方向、垂直方向、あるいは水平方向及び垂直方向の双方に対するグリッド交点４０７からのオフセットである。残りの変調位置のオフセットの距離である水平方向及び垂直方向の距離を「変調量子」(modulation quantum)４０４と呼ぶ。９つの変調位置(modulation positions)４０３の場所は、グリッド交点４０７を基準として(x, y)ベクトルのリストとして表すことができる。ここで、xは水平方向を示し、yは垂直方向を示す。また、xに関しては右向きのオフセットが正であり、yに関しては下向きのオフセットが正であるという規則を使用する。９つの変調位置４０３の場所を表すベクトルは、グリッド交点４０７を基準として、「mq」が変調量子を表す場合に以下のように表すことができる。
【００２６】
(-mq, -mq),
(0, -mq)
(+mq, -mq),
(-mq, +0),
(0, +0),
(+mq, +0),
(-mq, +mq),
(0, +mq),
(+mq, +mq)
図５は、標準正方形グリッド４０１に対するドット変調位置（例えば、４０３）を更に詳細に示す。ドット変調位置４０３は、グリッド４０１のグリッド交点４０７に集中しており、各変調位置、例えば、変調位置４０３は、変調位置４０３に関連するデジタルコード値（例えば、５０３）を有する。変調位置４０３等の９つの変調位置は、各ドット４０２が変調位置４０３に対するデジタルコード値５０３等の９つの可能なデジタルコード値のうち１つを符号化することを可能にする。これにより、変調グリッド４００はデジタルデータ記憶装置として動作でき、変調グリッド４００の各ドット４０２はデータの９を基数とする１つの数字を格納する。図６に示されるように、デジタルデータ記憶装置の数字の好ましい順序付けは、ドット６０１の矩形配列６００を使用することにより提供される順序付けである。この順序付けは、一番上の最も左側のドット６０１から開始し、一番下の最も右側のドット６０３に到達するまで、矢印（例えば、６０４）で表すように左から右及び上から下に進む。図６に示す以外のデジタルデータ記憶装置の数字の順序付けが使用されてもよい。
【００２７】
いくつかの例において、あるデータを含む変調グリッドが提供される際、その変調グリッドに対するグリッド方位、グリッド間隔及び変調量子を判定するのが有用である。グリッド方位、グリッド間隔及び変調量子の判定は、変調グリッド４００等の変調グリッドにおいて、複数のドット４０２間の平均間隔がグリッド間隔４１１に等しいということを利用して行なわれてもよい。しかし、ドット４０２間の間隔は、グリッド間隔４１１に常に等しいとは限らない。同様に、ドット４０２及びドット４１３等の隣接するドット間の平均方向は、標準正方形グリッド４０１の線に位置合わせされる。しかし、隣接するドット（４０２及び４１３）間の方向は、グリッド４０１の線に常に位置合わせされるとは限らない。
【００２８】
更に、特定のドット（例えば、４０２）に対して、それに対応して存在するグリッド点(grid-point)が位置付けられる場所を推定することは有用である。この問題は、グリッド平行移動の探索(finding the grid translation)と呼ばれる。ドットに対するグリッド点の場所は、ドットに最近接する交点の座標で表される。例えば、ドット４０２のグリッド点の場所は、交点４０７の座標である。
【００２９】
多くの応用例において、変調グリッド４００が作成される時と変調グリッド４００に関連するパラメータ（例えば、グリッド間隔、グリッド方位）が判定される時との間に、変調グリッド（例えば、４００）に対して変調が行なわれてもよい。例えば、変調グリッド４００は印刷及び走査され、且つドット検出が行なわれてもよい。そのような変更の間に、いくつかの追加のドットが導入されてもよく、又はいくつかのドットが消失してもよく、且ついくつかのドットが移動してもよい。グリッドパラメータの推定は、そのような変更が行なわれる場合であっても信頼性の高いものである必要がある。
【００３０】
（グリッドパラメータの判定）
次に、ドットのグリッドのグリッド方位、グリッド間隔（grid spacing)及びグリッド平行移動(grid translation)を判定する処理７００について、図７〜図１７を参照して説明する。処理７００は、図１に示すような汎用コンピュータシステム１００を使用して実現されてもよい。ここで、図７〜図１７の処理は、コンピュータシステム１００内で実行するアプリケーションプログラム等のソフトウェアとして実現されてもよい。特に、処理７００のステップは、コンピュータにより実行されるソフトウェアの命令により開始される。命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されてもよい。また、ソフトウェアは、２つの個別の部分に分割されてもよい。第１の部分は説明される処理を実行し、第２の部分は第１の部分とユーザとの間のユーザインタフェースを管理する。ソフトウェアは、例えば以下に説明する記憶装置等のコンピュータ可読媒体に格納されてもよい。ソフトウェアは、コンピュータ可読媒体からコンピュータにロードされ、コンピュータにより実行される。そのようなソフトウェア又はコンピュータプログラムを記録したコンピュータ可読媒体は、コンピュータプログラム製品である。コンピュータにおいてコンピュータプログラム製品を使用することにより、処理７００を実現する有利な装置を起動するのが好ましい。
【００３１】
コンピュータシステム１００は、コンピュータモジュール１０１と、キーボード１０２及びマウス１０３等の入力装置と、プリンタ１１５、表示装置１１４及びスピーカ１１７を含む出力装置とから形成される。変調器(Modulator)‐復調器(Demodulator)（モデム）トランシーバ装置１１６は、例えば電話回線１２１又は他の機能媒体を介して接続可能な通信ネットワーク１２０と通信するために、コンピュータモジュール１０１により使用される。モデム１１６は、インターネット、及びローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）等の他のネットワークシステムにアクセスするために使用され、また、いくつかの実現例において、コンピュータモジュール１０１に内蔵されてもよい。
【００３２】
コンピュータモジュール１０１は、通常、少なくとも１つのプロセッサユニット１０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されるメモリユニット１０６とを含む。モジュール１０１は、ビデオ表示装置１１４及びスピーカ１１７に結合するオーディオビデオインタフェース１０７、キーボード１０２及びマウス１０３及びオプションとしてのジョイスティック（不図示）に対する入出力（Ｉ／Ｏ）インタフェース１１３、並びにモデム１１６及びプリンタ１１５に対するインタフェース１０８を含む多くのＩ／Ｏインタフェースを更に含む。いくつかの実現例において、モデム１１６は、コンピュータモジュール１０１内、例えばインタフェース１０８内に内蔵されてもよい。記憶装置１０９が提供され、通常、それはハードディスクドライブ１１０及びフロッピー（登録商標）ディスク（登録商標）ドライブ１１１を含む。更に、磁気テープ装置（不図示）が使用されてもよい。ＣＤ-ＲＯＭドライブ１１２は、通常、不揮発性のデータソースとして提供される。コンピュータモジュール１０１の構成要素１０５〜１１３は、通常、当業者に周知のコンピュータシステム１００の従来の動作モードを結果として与える方法で、相互接続バス１０４を介して通信する。上述の構成が実現されるコンピュータの例として、ＩＢＭのＰＣ及びそれに互換性のあるもの、Sun SPARCstation又はそれから進化した同様のコンピュータシステムがある。
【００３３】
通常、アプリケーションプログラムは、ハードディスクドライブ１１０に常駐し、実行の際にはプロセッサ１０５により読み出され且つ制御される。ネットワーク１２０から取り出されるプログラム及び任意のデータの中間記憶装置は、ハードディスクドライブ１１０と共に動作する可能性のある半導体メモリ１０６を使用して達成されてもよい。いくつかの例において、アプリケーションプログラムは、ＣＤ-ＲＯＭ又はフロップディスク上で符号化されてユーザに供給され、対応するドライブ１１２又は１１１を介して読み出されてもよい。あるいは、アプリケーションプログラムは、ユーザによりモデム装置１１６を介してネットワーク１２０から読み出されてもよい。更に、ソフトウェアは、他のコンピュータ可読媒体からコンピュータシステム１００にロードできる。本明細書において使用される用語「コンピュータ可読媒体」は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム１００に提供することに関係する任意の記憶装置又は伝送媒体を示す。記憶媒体の例としては、装置がコンピュータモジュール１０１の内部装置であるか又は外部装置であるかに関わらず、フロッピー（登録商標）ディスク（登録商標）、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、あるいはＰＣＭＣＩＡカード等のコンピュータ可読カード等がある。伝送媒体の例としては、別のコンピュータ又はネットワーク化装置に対するネットワーク接続、並びに電子メール送信及びウェブサイト等に記録された情報を含むインターネット又はイントラネットに加え、無線伝送チャネル又は赤外線伝送チャネルがある。
【００３４】
あるいは、処理７００は、図７〜図１７の処理の機能又はサブ機能を実行する１つ以上の集積回路等の専用ハードウェアにおいて実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ、又は１つ以上のマイクロプロセッサ及び連想メモリを含んでもよい。
【００３５】
処理７００に対する入力は、グリッドのドットのドット座標(dot coordinates)であり、それらはメモリ１０６に格納されてもよい。処理７００は、ステップ７０３で開始する。ステップ７０３において、プロセッサ１０５は、グリッドのグリッド方位を表す角度を判定する。グリッド方位(grid orientation)は、メモリ１０６に格納されたグリッドのドットのドット座標から判定される。ステップ７０３で実行されるようなグリッドに対するグリッド方位を判定する処理９００については、図９を参照して以下に詳細に説明する。判定されたグリッド方位は、メモリ１０６に格納されてもよい。グリッド方位が判定されると、次のステップ７０５において、プロセッサ１０５は、グリッドの全てのドット座標に対して回転を適用する。その回転により、ドット座標がグリッド方位の角度分だけ回転され、その結果、回転されたドット座標は、ｘ軸及びｙ軸に対して位置合わせされたグリッド軸を有する。回転されたドット座標を仮定すると、次のステップ７０７において、プロセッサ１０５はグリッドのグリッド間隔を判定し、そのグリッド間隔はメモリ１０６に格納されてもよい。ステップ７０７で実行されるようなグリッドのグリッド間隔を検出する処理１０００については、図１０を参照して以下に詳細に説明する。次のステップ７０９において、プロセッサ１０５は、グリッド間隔及び回転されたドット座標を使用して、グリッド平行移動を判定する。グリッド平行移動は、メモリ１０６に格納されてもよい。グリッド平行移動を判定する処理１３００については、図１３を参照して以下に詳細に説明する。処理は、ステップ７０９の後に終了する。
【００３６】
図８は、変調グリッド(modulated grid)のグリッド方位(grid orientation)、グリッド間隔(grid spacing)、グリッド平行移動(grid translation)及び変調量子(modulation quantum)を判定する処理８００を示す。処理８００に対する入力は、変調グリッド上のドットの座標であり、それらはメモリ１０６に格納されてもよい。次のステップ８０３において、プロセッサ１０５は、処理７００を実行することにより、グリッド方位、グリッド間隔及びグリッド平行移動を判定する。その後、次のステップ８０５において、プロセッサ１０５は変調量子を判定する。ステップ８０５で実行されるような変調量子を判定する処理１５００については、図１５を参照して以下に詳細に説明する。判定された変調量子は、メモリ１０６に格納されてもよい。
【００３７】
（グリッド方位の判定）
次に、処理７００のステップ７０３で実行されるようなグリッド方位を判定する処理９００について、図９を参照して更に詳細に説明する。処理９００は、グリッドのドットのグリッド方位を判定する。
【００３８】
処理９００は、最初のステップ９０２で開始する。ステップ９０２において、プロセッサ１０５は、グリッドの各ドットに対して、そのドットに最近接する他のドットを判定する。ステップ９０２は、グリッドの全てのドットに対して実行される。特定のドットに対する最近接ドットを判定する周知の方法が、ステップ９０２において使用されてもよい。例えば、特定のドットに対する最近接ドットを判定する１つの処理においては、順番にドットを選択し、選択したドットから他の各ドットまでの距離を判定し、判定した距離が最短であるドットを選択する。特定のドットに対する最近接ドットを判定する好ましい処理は、グリッド空間(grid space)全体が多くの「バケット」（buckets)に分割される高速処理である。各ドットは、その特定のドットの場所を範囲に含むバケットに割り当てられる。特定のドットに対する最近接ドットを判定するために、プロセッサ１０５は、その特定のドットを範囲に含むバケットから開始し、その特定のドットの周囲にある各バケット中の全てのドットを調査し、特定のドットに最近接するドットを選択する。周囲のバケットの中にドットが存在しない場合、プロセッサ１０５は、半径方向外側の次に近接するバケットのセットに継続し、処理は同様の方法で継続する。特定のドットに対する最近接ドットを判定するこの好ましい処理は、最近接ドットであると考えられる候補ドットの数を大幅に減少する。
【００３９】
次のステップ９０３において、プロセッサ１０５は、各ドットからステップ９０２で発見された最近接ドットへの変位ベクトルを判定する。従って、グリッドの全てのドットは、そのドットに対して判定された対応する変位ベクトルを有する。
【００４０】
次のステップ９０４において、プロセッサ１０５は、ステップ９０３で判定された各変位ベクトルに対して、変位ベクトルの角度を判定する。ベクトルの角度θは、以下のように判定されてもよい。
【００４１】
θ= atan2(y, x)
式中、x及びyは、ベクトルの水平成分及び垂直成分である。
【００４２】
処理９００は、次のステップ９０５に続く。ステップ９０５において、プロセッサ１０５は、以下の式で定義される変数A及びBの値を判定する。
【００４３】
【数１】
【００４４】
式中、θiは、ステップ９０４で判定された変位ベクトルの角度である。和は、全ての変位ベクトルにわたり取得される。
【００４５】
処理９００の次のステップ９０６は、以下の式を使用して、グリッド方位を表すグリッド方位の角度φを判定する。
【００４６】
φ＝atan2（B,A)
処理９００は、ステップ９０６の後に終了する。
【００４７】
（グリッド間隔の判定）
次に、処理７００のステップ７０７で実行されるようなグリッドのグリッド間隔を判定する処理１０００について、図１０を参照して詳細に説明する。処理１０００は、最初のステップ１００２で開始する。ステップ１００２において、プロセッサ１０５は、入力としてグリッドのドットを取得する。グリッドの各ドット(x, y)に対して、水平方向の同一列においてドット(x, y)の右側の最隣接ドット(nearest neighbouring dot)が判定され、メモリ１０６に格納される。以下の解法(heuristic)が、ステップ１００２を実行するために使用されてもよい。(x, y)ではない全てのドット(a, b)が考慮され、(a, b)がドット(x, y)の右側の９０度の扇形の外側にある場合には(a, b)は拒否される。形式上、以下の場合、ドット(a, b)は拒否される。
【００４８】
【数２】
【００４９】
残されたドットに対して、以下の関数を最小にするドットが判定される。
【００５０】
【数３】
【００５１】
このドットは、(x, y)の右側のドットであると考えられ、メモリ１０６内に構成される右隣接ドット(right neighbour dots)のリストに格納される。
【００５２】
次のステップ１００３において、プロセッサ１０５は、ステップ１００２でメモリ１０６に格納された右隣接ドット(a, b)の各々を取得して、以下のように(x, y)からの差分ベクトル(difference vector)(dx, dy)を判定する。
【００５３】
(dx, dy) = (a, b) - (x, y)
式中、(dx, dy)は、メモリ１０６に構成される差分ベクトルのリストに格納される。例として、図１１は、差分ベクトルのリストのグラフ１１００を示す。グラフ１１００は、ｙ軸１１０１及びｘ軸１１０２を含む。グラフ１１００の円（例えば、１１０３）は、差分ベクトルの端点を表す。グリッドにおける雑音及び歪により、端点(terminal point)１１０４のような範囲外にある不適切な端点がいくつか存在する。
【００５４】
処理１０００は、次のステップ１００４に続く。ステップ１００４において、プロセッサ１０５は、ステップ１００３で判定された各差分ベクトルのｘ座標を取得して、ｘ座標の値の周波数ヒストグラム(frequency histogram)を生成する。図１２はヒストグラム１２００の一例を示す。軸１２０１は周波数軸(frequency axis)であり、軸１２０２はｘ座標軸である。周波数ヒストグラム１２００は、周波数バー(frequency bar)（例えば、１２０３）を更に含む。ｘ座標軸１２０２における各量子のサイズは、ドット座標(dot coordinates)の粒度(granularity)に関連付けられる。量子(quantum)は、０．５のグリッド座標軸系(grid co-ordinate axis system)になるように選択されるのが好ましい。しかし、任意の適切な値が量子に使用されてもよい。
【００５５】
処理１０００は、次のステップ１００５に続く。ステップ１００５において、プロセッサ１０５は、ヒストグラム１２００を使用してグリッド間隔を判定する。尚、右隣接ドットの殆どは、グリッドの間隔の辺りにクラスタ化(clustered)される。従って、グリッド間隔は、最も多く存在するｘ座標のｘ値を取得することにより判定され、図１２の例において、それは周波数バー１２０４で示される。
【００５６】
（グリッド平行移動の判定）
次に、処理７００のステップ７０９で実行されるようなグリッドのグリッド平行移動を判定する処理１３００について、図１３を参照して更に詳細に説明する。メモリ１０６に格納されたドット座標のリスト及びグリッド間隔は、処理１３００に対する入力として提供される。処理１３００は、グリッドの全てのドットに対するグリッド平行移動を判定する。すなわち、処理１３００は、全てのドットに対して、ドットのグリッド点の場所を推定する。
【００５７】
処理は、ステップ１３０３で開始する。ステップ１３０３において、プロセッサ１０５は、グリッドに対してメモリ１０６に格納されたドットのリストからまだ処理されていないドットを選択する。この選択されたドットを「現在のドット」(current dot)と呼ぶ。プロセッサ１０５は、現在のドットのローカルウィンドウ内に存在する全てのドットを判定し、そのドットをメモリ１０６内に構成されるローカルウィンドウドットのリストに配置する。例えば、図１４は、雑音のある環境において、グリッドのような構成１４００で配置されるドットを示す。グリッド１４００は現在のドット１４０２を含み、現在のドット１４０２のグリッド点の場所１４０３である。現在のドット１４０２のローカルウィンドウ１４０１が更に示される。ローカルウィンドウ１４０１は、図１４の例において、辺の長さ５を有する。ローカルウィンドウ１４０１のサイズは、グリッド環境に存在する雑音の種類及び大きさに依存する。ローカルウィンドウの好ましいサイズは３０である。
【００５８】
次のステップ１３０５において、プロセッサ１０５は、メモリ１０６からローカルウィンドウドット（例えば、１４０４）のリストを取得し、以下のように、グリッド間隔が２πとなるように各ドット(xk, yk)の座標を正規化する。
【００５９】
【数４】
【００６０】
処理１３００は、次のステップ１３０７に続く。ステップ１３０７において、プロセッサ１０５は、メモリ１０６に格納された正規化(normalised)されたローカルウィンドウドットのリストを取得し、２つのフェーザ(phasors)xOffset及びyOffsetを判定する。
【００６１】
【数５】
【００６２】
ステップ１３０７における加算は、正規化されたローカルウィンドウドットのリスト全体に対して行なわれる。xOffset及びyOffsetの位相は、それぞれ、現在のドットがグリッド点からｘ方向及びｙ方向に位相がずれている量を推定する。
【００６３】
次のステップ１３０９において、プロセッサ１０５は、現在のドットのグリッド点の場所を判定する。現在のドットを(xc, yc)で示す。現在のドットに対するグリッド点(xGrid, yGrid)は以下の式で与えられる。
【００６４】
【数６】
【００６５】
処理１３００は、次のステップ１３１１に続く。ステップ１３１１において、自身のグリッド点をまだ判定していないドットが存在するとプロセッサ１０５が判定した場合、処理１３００はステップ１３０３に戻る。存在すると判定しなかった場合、処理１３００は終了する。
【００６６】
（変調量子の判定）
次に、ステップ８０５で実行されるような変調量子を判定する処理１５００について、図１５を参照して詳細に説明する。処理１５００は、最初のステップ１５０２で開始する。ステップ１５０２において、プロセッサ１０５は、入力としてグリッドのドットを取得する。ステップ１００２について上述したように、グリッドの各ドット(x, y)に対して、水平方向の同一列においてドット(x, y)の右側の最隣接ドットが判定され、メモリ１０６に格納される。次のステップ１５０３において、プロセッサ１０５は、ステップ１００３について上述したように、ステップ１００２でメモリ１０６に格納された右隣接ドット(a, b)の各々を取得し、(x, y)からの差分ベクトル(dx, dy)を判定する。
【００６７】
次のステップ１５０４において、プロセッサ１０５は、ステップ１５０３で判定された各差分ベクトルのｙ値の周波数ヒストグラムを判定する。例として、図１６はヒストグラム１６００を示す。ヒストグラムは、周波数軸１６０１、ｙ座標軸１６０２及び複数の周波数バー（例えば、１６０３）を含む。ｙ座標軸における各量子のサイズは、ドット座標の粒度に関連付けられる。繰り返しになるが、量子は、０．５のグリッド座標軸系になるように選択されるのが好ましい。しかし、任意の適切な値が量子に使用されてもよい。
【００６８】
次のステップ１５０５において、プロセッサ１０５は、ヒストグラム１６００を使用して、グリッドの変調量子(modulation quantum)を判定する。ステップ１５０５において、プロセッサ１０５は、ゼロの近くでヒストグラム１６００のピークを判定する。ピークは、「ピークウィンドウ半径」(peak-window-radius)と呼ばれる特定の半径内の隣接するｙ値の全ての周波数バーより大きい関連する周波数バーを有するｙ値になるように規定される。ピークウィンドウ半径は、グリッド間隔に比例する。説明される処理において、ピークウィンドウ半径は、グリッド間隔の１／１０であるのが好ましい。そのようなピークの例は、図１６に示されるような１６０３である。ここで、ピークウィンドウ半径は１である。いくつかのピーク（例えば、５つのピーク）が原点１６０１の周囲で判定されると、変調量子は、隣接するピーク間の距離の平均を取得することにより判定される。処理１５００は、ステップ１５０５の後に終了する。
【００６９】
（変調量子を判定する別の方法）
方法８００のステップ８０５のような変調量子を判定する別の処理１７００を図１７に示す。処理１７００は、ステップ１７０２で開始する。ステップ１７０２において、プロセッサ１０５は、メモリ１０６内に構成されるドットのリスト中の全てのドットに対して、最近接グリッド点を推定する。すなわち、プロセッサ１０５は、グリッドのドットに対するグリッド平行移動を判定する。上述したように、最近接グリッド点は、ステップ１７０２において、図１３の処理１３００を使用して各ドットに対して判定される。
【００７０】
次のステップ１７０３において、プロセッサ１０５は、ステップ１７０２で判定されたドットの対応するグリッド点に対する各ドットからのオフセットベクトルを判定する。次のステップ１７０４において、プロセッサ１０５は、上述のように、ステップ１７０３で判定されたオフセットベクトルのｙ成分のヒストグラムを判定する。次のステップ１７０５において、プロセッサ１０５は、ステップ１７０４で判定されたヒストグラムの３つの最大ピークを判定する。それらピークのうち最小のピークと２番目に小さいピークとの距離及び２番目に小さいピークと最大ピークとの距離は、グリッドに対する変調量子にほぼ等しい。ステップ１７０６において、プロセッサ１０５はそれら２つの距離の平均を検出し、それを変調量子として使用する。
【００７１】
（別の構成）
図９のステップ９０２において、処理９００は、各ドットに対する最近接ドットを判定する。別の構成においては、最近接ドットが、グリッドのドットのサブセットに対してのみ判定されてもよい。この例において、最近接ドットが判定されるドットのサブセットは、例えばドットをランダムに選択したものでもよい。あるいは、最近接ドットは、グリッドの上部２５％内に存在するドットに対してのみ判定されてもよく、又はグリッドの所定の帯域に存在するドットに対してのみ判定されてもよい。この例において、処理９００の後続するステップ９０３及び９０４では、サブセット中のドットのみが考慮される。
【００７２】
更に別の構成において、１つの最近接ドットのみを使用するのではなく、Ｎ個の最近接ドットを使用して変位ベクトルを判定してもよい。例えば、Ｎは２又は４に等しくてもよい。この構成により、複雑性及び速度と引き換えに、雑音の多いグリッドにおいてグリッド方位をより正確に検出できる場合がある。
【００７３】
図９のステップ９０６において、処理９００は、先のステップ９０５で判定された変位ベクトルの角度からグリッド方位の角度φを判定する。ステップ９０６において多くの別の方法が使用されてもよいことは、当業者には理解されるだろう。例えば、変位ベクトルの角度のヒストグラムが判定されてもよい。この例において、多数の変位ベクトルの角度を含むヒストグラムビンは、グリッド方位の角度φに対応する。
【００７４】
図１０のステップ１００３において、差分ベクトルのセットが判定され、全ての差分ベクトルが後続するステップ１００４及び１００５において使用される。別の構成において、差分ベクトルのランダムなサブセットが、ステップ１００４及び１００５で使用されてもよく、グリッド間隔に対する値は、そのランダムなサブセットに基づいて判定される。この例において、ステップ１００４及び１００５の処理は、Ｎ回（例えば、３０回）繰り返され、繰り返す度に差分ベクトルの異なるランダムなサブセットが使用される。これにより、Ｎ＋１個の異なるグリッド間隔の値が得られる。実際のグリッド間隔は、それらＮ＋１個の値のモードになるように判定されてもよい。この別の構成により、複雑性及び速度と引き換えに、雑音の多いグリッドにおいてグリッド間隔をより正確に得られる場合がある。
【００７５】
同様に、差分ベクトルのランダムなサブセットが、複雑性及び速度と引き換えに変調量子をより正確に検出するために、処理１５００のステップ１５０３及び１５０４において使用されてもよい。
【００７６】
図１０のステップ１００４及び１００５において、グリッド間隔は、ステップ１００３で発見された差分ベクトルのｘ座標から判定される。グリッド間隔を判定するために、多くの別の処理が使用されてもよいことは、当業者には理解されるだろう。例えば、グリッド間隔は、ステップ１００３で判定された差分ベクトルのｘ座標の平均として判定されてもよい。
【００７７】
説明された構成は、コンピュータ産業及びデータ処理産業に適用可能であることは、上述から明らかである。
【００７８】
上述において、本発明のいくつかの実施形態のみを説明したが、本発明の趣旨の範囲から逸脱せずに変形及び／又は変更が可能である。それら実施形態は単なる例示であり、限定するものではない。
【図面の簡単な説明】
【００７９】
【図１】説明された構成が実現される汎用コンピュータを概略的に示すブロック図である。
【図２】位相変調されたドットの配列を示す図である。
【図３】標準グリッドに従って配置されたドットの別の配列を示す図である。
【図４】位相変調されたドットの更に別の配列を示す図である。
【図５】図４の標準正方形グリッドの交点に対するドット変調位置を示す図である。
【図６】デジタルデータ記憶装置の数字の順序付けを示す図である。
【図７】ドットのグリッドのグリッド方位、グリッド間隔及びグリッド平行移動を判定する処理を示すフローチャートである。
【図８】ドットの変調グリッドにおけるグリッド方位、グリッド間隔、グリッド平行移動及び変調量子を判定する処理を示すフローチャートである。
【図９】図７の処理において実行されるグリッド方位を判定する処理を示すフローチャートである。
【図１０】図７の処理において実行されるグリッドのグリッド間隔を判定する処理を示すフローチャートである。
【図１１】右隣接差分ベクトルのリストを示すグラフである。
【図１２】ｘ値を示す周波数ヒストグラムである。
【図１３】図７の処理において実行されるグリッドのグリッド平行移動を判定する処理を示すフローチャートである。
【図１４】グリッドのような構成で配置されるドットと、グリッドのグリッド平行移動を推定する際に使用されるローカルウィンドウとを示す図である。
【図１５】変調量子を判定する処理を示すフローチャートである。
【図１６】ｙ値を示す周波数ヒストグラムである。
【図１７】変調量子を判定する別の処理を示すフローチャートである。
【技術分野】
【０００１】
本発明は、一般に画像処理に関し、特にグリッド検出に関する。更に本発明は、グリッドの向き（以下、「グリッド方位」と呼ぶ）、間隔（以下、「グリッド間隔」と呼ぶ）及び平行移動（以下、「グリッド平行移動」と呼ぶ）を判定する処理及び装置に関し、また、グリッドに対するグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムを記録したコンピュータ可読媒体に関する。
【背景技術】
【０００２】
従来技術において、グリッド方位及びグリッド間隔を判定する方法が多く存在する。そのような方法は、通常、データがグリッドのような構成で格納される２次元バーコード又は透かしを位置合わせする処理の一部である。
【０００３】
従来技術の方法は、通常、自己相関(autocorrelation)又はペリオドグラム(periodogram)等の畳み込みに基づく方法(convolution-based method)を使用して、グリッド方位及びグリッド間隔を判定する。自己相関及びペリオドグラムの双方が、出力データではピークとして示される入力データの主周波数を判定する。それらピークは判定され、最大ピークの場所がグリッドの主周波数となる。グリッドのグリッド間隔及びグリッド方位は、その主周波数から判定される。
【０００４】
畳み込みに基づく方法の主な欠点は、それら方法が画像全体に対して畳み込みを実行するため、計算費用が高いことである。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、グリッドのグリッド方位、グリッド間隔及びグリッド平行移動を判定する計算費用の安価な改良された処理が必要とされる。
【課題を解決するための手段】
【０００６】
本発明の１つの面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する処理方法は、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するステップと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するステップと、
前記判定したベクトルを使用して前記グリッド方位を判定するステップとを備えることを特徴する。
【０００７】
本発明の別の面によると、符号化データに対するグリッドを判定する処理方法は、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するステップと、
前記統計平均に基づいて、前記データの角度方向を判定するステップと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するステップとを備えることを特徴する。
【０００８】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する処理方法は、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するステップと、
前記変位ベクトルを使用して前記グリッド方位を判定するステップと、
前記グリッド間隔を判定するステップと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するステップとを備えることを特徴する。
【０００９】
本発明の更に別の面によると、符号化データに対するグリッドを判定する処理方法は、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するステップと、
前記グリッドの隣接データ点の間隔を判定するステップと、
前記グリッドに関して、各データ点に対するオフセットを判定するステップとを備えることを特徴する。
【００１０】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する装置は、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するベクトル判定手段と、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去する変調除去手段と、
前記判定したベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段とを備えることを特徴する。
【００１１】
本発明の更に別の面によると、符号化データに対するグリッドを判定する装置は、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定する統計平均判定手段と、
前記統計平均に基づいて、前記データの角度方向を判定する角度方向判定手段と、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するグリッド判定手段とを備えることを特徴する。
【００１２】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する装置は、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定する変位ベクトル判定手段と、
前記変位ベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段と、
前記グリッド間隔を判定するグリッド間隔判定手段と、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するグリッド平行移動判定手段とを備えることを特徴する。
【００１３】
本発明の更に別の面によると、符号化データに対するグリッドを判定する装置は、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定する角度方向判定手段と、
前記グリッドの隣接データ点の間隔を判定する間隔判定手段と、
前記グリッドに関して、各データ点に対するオフセットを判定するオフセット判定手段とを備えることを特徴する。
【００１４】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムは、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコードとを備えることを特徴する。
【００１５】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムは、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコードとを備えることを特徴する。
【００１６】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムは、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコードと、
前記グリッド間隔を判定するコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコードとを備えることを特徴する。
【００１７】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムは、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコードと、
前記グリッドの隣接データ点の間隔を判定するコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコードとを備えることを特徴する。
【００１８】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコンピュータプログラムコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコンピュータプログラムコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードとを備えることを特徴する。
【００１９】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコンピュータプログラムコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコンピュータプログラムコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコンピュータプログラムコードとを備えることを特徴する。
【００２０】
本発明の更に別の面によると、ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコンピュータプログラムコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードと、
前記グリッド間隔を判定するコンピュータプログラムコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコンピュータプログラムコードとを備えることを特徴する。
【００２１】
本発明の更に別の面によると、符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体は、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコンピュータプログラムコードと、
前記グリッドの隣接データ点の間隔を判定するコンピュータプログラムコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコンピュータプログラムコードとを備えることを特徴する。
【発明を実施するための最良の形態】
【００２２】
（変調グリッド）
図２は、ドットの変調グリッド２００（以下、「変調グリッド２００」と呼ぶ）を形成するように位相変調(phase modulated)されたドット（例えば、２０２）の配列を示す拡大図である。変調グリッド２００は、標準正方形グリッド(square regular grid)２０１の交点（例えば、２０３）に近接する多数のドット２０２を含む。実際には、図２に示されるように、ドット２０２のみが変調グリッド２００を形成する。グリッド２０１及びその線は仮想のものであり、単にドット２０２の場所を説明するために図２に示される。
【００２３】
変調グリッド２００の外観は、ドットの標準グリッド(regular grid)３００（以下、「標準グリッド３００」と呼ぶ）を形成するように、図３に示されるような標準正方形グリッド３０１に従って配置されたドット（例えば、３０２）の外観に類似する。しかし、変調グリッド２００及び標準グリッド３００は同一のものではない。図３は、標準正方形グリッド３０１のグリッド間隔３０３を更に示す。
【００２４】
標準グリッド３００と変調グリッド２００との相違点は、変調グリッド２００におけるドット２０２の位置が、ドット２０２が標準グリッド２０１の交点２０３に従って配置される場合にドット２０２が占有するグリッド位置から離れた位置に僅かに変調されることである。この僅かな変調は、次の２つの目的を満足させる。第１に、変調により、変調グリッド２００のドット２０２は、標準グリッド３００のドット３０２よりも僅かに可視性が低くなる。これは、人間の視覚系が標準グリッドを認識することに非常に適しているからである。第２に、デジタルデータの形式のメッセージは、変調グリッド２００のようにドットを変調した際に格納される。
【００２５】
図４は、変調グリッド４００を形成するように位相変調されたドット（例えば、４０２）の別の配列を示す。ドット４０２は、標準正方形グリッド４０１の交点（例えば、４０７）に近接する。図４から分かるように、各ドット４０２は、９つの可能な位置のうち１つの位置（例えば、４０３）に変調される。各ドットの９つの可能な位置は、関連するグリッド交点４０７に集中する３×３の配列（例えば、４０５）で構成される。３×３の配列４０５の中心位置４０９は、グリッド交点４０７に位置付けられ、水平方向及び垂直方向の距離がゼロの変調に対応する。同様に、標準正方形グリッド４０１の他の交点も、交点の辺りに位置付けられる３×３の配列を有する。残りの８つの変調位置（例えば、４０３）は、水平方向、垂直方向、あるいは水平方向及び垂直方向の双方に対するグリッド交点４０７からのオフセットである。残りの変調位置のオフセットの距離である水平方向及び垂直方向の距離を「変調量子」(modulation quantum)４０４と呼ぶ。９つの変調位置(modulation positions)４０３の場所は、グリッド交点４０７を基準として(x, y)ベクトルのリストとして表すことができる。ここで、xは水平方向を示し、yは垂直方向を示す。また、xに関しては右向きのオフセットが正であり、yに関しては下向きのオフセットが正であるという規則を使用する。９つの変調位置４０３の場所を表すベクトルは、グリッド交点４０７を基準として、「mq」が変調量子を表す場合に以下のように表すことができる。
【００２６】
(-mq, -mq),
(0, -mq)
(+mq, -mq),
(-mq, +0),
(0, +0),
(+mq, +0),
(-mq, +mq),
(0, +mq),
(+mq, +mq)
図５は、標準正方形グリッド４０１に対するドット変調位置（例えば、４０３）を更に詳細に示す。ドット変調位置４０３は、グリッド４０１のグリッド交点４０７に集中しており、各変調位置、例えば、変調位置４０３は、変調位置４０３に関連するデジタルコード値（例えば、５０３）を有する。変調位置４０３等の９つの変調位置は、各ドット４０２が変調位置４０３に対するデジタルコード値５０３等の９つの可能なデジタルコード値のうち１つを符号化することを可能にする。これにより、変調グリッド４００はデジタルデータ記憶装置として動作でき、変調グリッド４００の各ドット４０２はデータの９を基数とする１つの数字を格納する。図６に示されるように、デジタルデータ記憶装置の数字の好ましい順序付けは、ドット６０１の矩形配列６００を使用することにより提供される順序付けである。この順序付けは、一番上の最も左側のドット６０１から開始し、一番下の最も右側のドット６０３に到達するまで、矢印（例えば、６０４）で表すように左から右及び上から下に進む。図６に示す以外のデジタルデータ記憶装置の数字の順序付けが使用されてもよい。
【００２７】
いくつかの例において、あるデータを含む変調グリッドが提供される際、その変調グリッドに対するグリッド方位、グリッド間隔及び変調量子を判定するのが有用である。グリッド方位、グリッド間隔及び変調量子の判定は、変調グリッド４００等の変調グリッドにおいて、複数のドット４０２間の平均間隔がグリッド間隔４１１に等しいということを利用して行なわれてもよい。しかし、ドット４０２間の間隔は、グリッド間隔４１１に常に等しいとは限らない。同様に、ドット４０２及びドット４１３等の隣接するドット間の平均方向は、標準正方形グリッド４０１の線に位置合わせされる。しかし、隣接するドット（４０２及び４１３）間の方向は、グリッド４０１の線に常に位置合わせされるとは限らない。
【００２８】
更に、特定のドット（例えば、４０２）に対して、それに対応して存在するグリッド点(grid-point)が位置付けられる場所を推定することは有用である。この問題は、グリッド平行移動の探索(finding the grid translation)と呼ばれる。ドットに対するグリッド点の場所は、ドットに最近接する交点の座標で表される。例えば、ドット４０２のグリッド点の場所は、交点４０７の座標である。
【００２９】
多くの応用例において、変調グリッド４００が作成される時と変調グリッド４００に関連するパラメータ（例えば、グリッド間隔、グリッド方位）が判定される時との間に、変調グリッド（例えば、４００）に対して変調が行なわれてもよい。例えば、変調グリッド４００は印刷及び走査され、且つドット検出が行なわれてもよい。そのような変更の間に、いくつかの追加のドットが導入されてもよく、又はいくつかのドットが消失してもよく、且ついくつかのドットが移動してもよい。グリッドパラメータの推定は、そのような変更が行なわれる場合であっても信頼性の高いものである必要がある。
【００３０】
（グリッドパラメータの判定）
次に、ドットのグリッドのグリッド方位、グリッド間隔（grid spacing)及びグリッド平行移動(grid translation)を判定する処理７００について、図７〜図１７を参照して説明する。処理７００は、図１に示すような汎用コンピュータシステム１００を使用して実現されてもよい。ここで、図７〜図１７の処理は、コンピュータシステム１００内で実行するアプリケーションプログラム等のソフトウェアとして実現されてもよい。特に、処理７００のステップは、コンピュータにより実行されるソフトウェアの命令により開始される。命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードモジュールとして形成されてもよい。また、ソフトウェアは、２つの個別の部分に分割されてもよい。第１の部分は説明される処理を実行し、第２の部分は第１の部分とユーザとの間のユーザインタフェースを管理する。ソフトウェアは、例えば以下に説明する記憶装置等のコンピュータ可読媒体に格納されてもよい。ソフトウェアは、コンピュータ可読媒体からコンピュータにロードされ、コンピュータにより実行される。そのようなソフトウェア又はコンピュータプログラムを記録したコンピュータ可読媒体は、コンピュータプログラム製品である。コンピュータにおいてコンピュータプログラム製品を使用することにより、処理７００を実現する有利な装置を起動するのが好ましい。
【００３１】
コンピュータシステム１００は、コンピュータモジュール１０１と、キーボード１０２及びマウス１０３等の入力装置と、プリンタ１１５、表示装置１１４及びスピーカ１１７を含む出力装置とから形成される。変調器(Modulator)‐復調器(Demodulator)（モデム）トランシーバ装置１１６は、例えば電話回線１２１又は他の機能媒体を介して接続可能な通信ネットワーク１２０と通信するために、コンピュータモジュール１０１により使用される。モデム１１６は、インターネット、及びローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）等の他のネットワークシステムにアクセスするために使用され、また、いくつかの実現例において、コンピュータモジュール１０１に内蔵されてもよい。
【００３２】
コンピュータモジュール１０１は、通常、少なくとも１つのプロセッサユニット１０５と、例えば半導体ランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）から形成されるメモリユニット１０６とを含む。モジュール１０１は、ビデオ表示装置１１４及びスピーカ１１７に結合するオーディオビデオインタフェース１０７、キーボード１０２及びマウス１０３及びオプションとしてのジョイスティック（不図示）に対する入出力（Ｉ／Ｏ）インタフェース１１３、並びにモデム１１６及びプリンタ１１５に対するインタフェース１０８を含む多くのＩ／Ｏインタフェースを更に含む。いくつかの実現例において、モデム１１６は、コンピュータモジュール１０１内、例えばインタフェース１０８内に内蔵されてもよい。記憶装置１０９が提供され、通常、それはハードディスクドライブ１１０及びフロッピー（登録商標）ディスク（登録商標）ドライブ１１１を含む。更に、磁気テープ装置（不図示）が使用されてもよい。ＣＤ-ＲＯＭドライブ１１２は、通常、不揮発性のデータソースとして提供される。コンピュータモジュール１０１の構成要素１０５〜１１３は、通常、当業者に周知のコンピュータシステム１００の従来の動作モードを結果として与える方法で、相互接続バス１０４を介して通信する。上述の構成が実現されるコンピュータの例として、ＩＢＭのＰＣ及びそれに互換性のあるもの、Sun SPARCstation又はそれから進化した同様のコンピュータシステムがある。
【００３３】
通常、アプリケーションプログラムは、ハードディスクドライブ１１０に常駐し、実行の際にはプロセッサ１０５により読み出され且つ制御される。ネットワーク１２０から取り出されるプログラム及び任意のデータの中間記憶装置は、ハードディスクドライブ１１０と共に動作する可能性のある半導体メモリ１０６を使用して達成されてもよい。いくつかの例において、アプリケーションプログラムは、ＣＤ-ＲＯＭ又はフロップディスク上で符号化されてユーザに供給され、対応するドライブ１１２又は１１１を介して読み出されてもよい。あるいは、アプリケーションプログラムは、ユーザによりモデム装置１１６を介してネットワーク１２０から読み出されてもよい。更に、ソフトウェアは、他のコンピュータ可読媒体からコンピュータシステム１００にロードできる。本明細書において使用される用語「コンピュータ可読媒体」は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム１００に提供することに関係する任意の記憶装置又は伝送媒体を示す。記憶媒体の例としては、装置がコンピュータモジュール１０１の内部装置であるか又は外部装置であるかに関わらず、フロッピー（登録商標）ディスク（登録商標）、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、あるいはＰＣＭＣＩＡカード等のコンピュータ可読カード等がある。伝送媒体の例としては、別のコンピュータ又はネットワーク化装置に対するネットワーク接続、並びに電子メール送信及びウェブサイト等に記録された情報を含むインターネット又はイントラネットに加え、無線伝送チャネル又は赤外線伝送チャネルがある。
【００３４】
あるいは、処理７００は、図７〜図１７の処理の機能又はサブ機能を実行する１つ以上の集積回路等の専用ハードウェアにおいて実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタル信号プロセッサ、又は１つ以上のマイクロプロセッサ及び連想メモリを含んでもよい。
【００３５】
処理７００に対する入力は、グリッドのドットのドット座標(dot coordinates)であり、それらはメモリ１０６に格納されてもよい。処理７００は、ステップ７０３で開始する。ステップ７０３において、プロセッサ１０５は、グリッドのグリッド方位を表す角度を判定する。グリッド方位(grid orientation)は、メモリ１０６に格納されたグリッドのドットのドット座標から判定される。ステップ７０３で実行されるようなグリッドに対するグリッド方位を判定する処理９００については、図９を参照して以下に詳細に説明する。判定されたグリッド方位は、メモリ１０６に格納されてもよい。グリッド方位が判定されると、次のステップ７０５において、プロセッサ１０５は、グリッドの全てのドット座標に対して回転を適用する。その回転により、ドット座標がグリッド方位の角度分だけ回転され、その結果、回転されたドット座標は、ｘ軸及びｙ軸に対して位置合わせされたグリッド軸を有する。回転されたドット座標を仮定すると、次のステップ７０７において、プロセッサ１０５はグリッドのグリッド間隔を判定し、そのグリッド間隔はメモリ１０６に格納されてもよい。ステップ７０７で実行されるようなグリッドのグリッド間隔を検出する処理１０００については、図１０を参照して以下に詳細に説明する。次のステップ７０９において、プロセッサ１０５は、グリッド間隔及び回転されたドット座標を使用して、グリッド平行移動を判定する。グリッド平行移動は、メモリ１０６に格納されてもよい。グリッド平行移動を判定する処理１３００については、図１３を参照して以下に詳細に説明する。処理は、ステップ７０９の後に終了する。
【００３６】
図８は、変調グリッド(modulated grid)のグリッド方位(grid orientation)、グリッド間隔(grid spacing)、グリッド平行移動(grid translation)及び変調量子(modulation quantum)を判定する処理８００を示す。処理８００に対する入力は、変調グリッド上のドットの座標であり、それらはメモリ１０６に格納されてもよい。次のステップ８０３において、プロセッサ１０５は、処理７００を実行することにより、グリッド方位、グリッド間隔及びグリッド平行移動を判定する。その後、次のステップ８０５において、プロセッサ１０５は変調量子を判定する。ステップ８０５で実行されるような変調量子を判定する処理１５００については、図１５を参照して以下に詳細に説明する。判定された変調量子は、メモリ１０６に格納されてもよい。
【００３７】
（グリッド方位の判定）
次に、処理７００のステップ７０３で実行されるようなグリッド方位を判定する処理９００について、図９を参照して更に詳細に説明する。処理９００は、グリッドのドットのグリッド方位を判定する。
【００３８】
処理９００は、最初のステップ９０２で開始する。ステップ９０２において、プロセッサ１０５は、グリッドの各ドットに対して、そのドットに最近接する他のドットを判定する。ステップ９０２は、グリッドの全てのドットに対して実行される。特定のドットに対する最近接ドットを判定する周知の方法が、ステップ９０２において使用されてもよい。例えば、特定のドットに対する最近接ドットを判定する１つの処理においては、順番にドットを選択し、選択したドットから他の各ドットまでの距離を判定し、判定した距離が最短であるドットを選択する。特定のドットに対する最近接ドットを判定する好ましい処理は、グリッド空間(grid space)全体が多くの「バケット」（buckets)に分割される高速処理である。各ドットは、その特定のドットの場所を範囲に含むバケットに割り当てられる。特定のドットに対する最近接ドットを判定するために、プロセッサ１０５は、その特定のドットを範囲に含むバケットから開始し、その特定のドットの周囲にある各バケット中の全てのドットを調査し、特定のドットに最近接するドットを選択する。周囲のバケットの中にドットが存在しない場合、プロセッサ１０５は、半径方向外側の次に近接するバケットのセットに継続し、処理は同様の方法で継続する。特定のドットに対する最近接ドットを判定するこの好ましい処理は、最近接ドットであると考えられる候補ドットの数を大幅に減少する。
【００３９】
次のステップ９０３において、プロセッサ１０５は、各ドットからステップ９０２で発見された最近接ドットへの変位ベクトルを判定する。従って、グリッドの全てのドットは、そのドットに対して判定された対応する変位ベクトルを有する。
【００４０】
次のステップ９０４において、プロセッサ１０５は、ステップ９０３で判定された各変位ベクトルに対して、変位ベクトルの角度を判定する。ベクトルの角度θは、以下のように判定されてもよい。
【００４１】
θ= atan2(y, x)
式中、x及びyは、ベクトルの水平成分及び垂直成分である。
【００４２】
処理９００は、次のステップ９０５に続く。ステップ９０５において、プロセッサ１０５は、以下の式で定義される変数A及びBの値を判定する。
【００４３】
【数１】
【００４４】
式中、θiは、ステップ９０４で判定された変位ベクトルの角度である。和は、全ての変位ベクトルにわたり取得される。
【００４５】
処理９００の次のステップ９０６は、以下の式を使用して、グリッド方位を表すグリッド方位の角度φを判定する。
【００４６】
φ＝atan2（B,A)
処理９００は、ステップ９０６の後に終了する。
【００４７】
（グリッド間隔の判定）
次に、処理７００のステップ７０７で実行されるようなグリッドのグリッド間隔を判定する処理１０００について、図１０を参照して詳細に説明する。処理１０００は、最初のステップ１００２で開始する。ステップ１００２において、プロセッサ１０５は、入力としてグリッドのドットを取得する。グリッドの各ドット(x, y)に対して、水平方向の同一列においてドット(x, y)の右側の最隣接ドット(nearest neighbouring dot)が判定され、メモリ１０６に格納される。以下の解法(heuristic)が、ステップ１００２を実行するために使用されてもよい。(x, y)ではない全てのドット(a, b)が考慮され、(a, b)がドット(x, y)の右側の９０度の扇形の外側にある場合には(a, b)は拒否される。形式上、以下の場合、ドット(a, b)は拒否される。
【００４８】
【数２】
【００４９】
残されたドットに対して、以下の関数を最小にするドットが判定される。
【００５０】
【数３】
【００５１】
このドットは、(x, y)の右側のドットであると考えられ、メモリ１０６内に構成される右隣接ドット(right neighbour dots)のリストに格納される。
【００５２】
次のステップ１００３において、プロセッサ１０５は、ステップ１００２でメモリ１０６に格納された右隣接ドット(a, b)の各々を取得して、以下のように(x, y)からの差分ベクトル(difference vector)(dx, dy)を判定する。
【００５３】
(dx, dy) = (a, b) - (x, y)
式中、(dx, dy)は、メモリ１０６に構成される差分ベクトルのリストに格納される。例として、図１１は、差分ベクトルのリストのグラフ１１００を示す。グラフ１１００は、ｙ軸１１０１及びｘ軸１１０２を含む。グラフ１１００の円（例えば、１１０３）は、差分ベクトルの端点を表す。グリッドにおける雑音及び歪により、端点(terminal point)１１０４のような範囲外にある不適切な端点がいくつか存在する。
【００５４】
処理１０００は、次のステップ１００４に続く。ステップ１００４において、プロセッサ１０５は、ステップ１００３で判定された各差分ベクトルのｘ座標を取得して、ｘ座標の値の周波数ヒストグラム(frequency histogram)を生成する。図１２はヒストグラム１２００の一例を示す。軸１２０１は周波数軸(frequency axis)であり、軸１２０２はｘ座標軸である。周波数ヒストグラム１２００は、周波数バー(frequency bar)（例えば、１２０３）を更に含む。ｘ座標軸１２０２における各量子のサイズは、ドット座標(dot coordinates)の粒度(granularity)に関連付けられる。量子(quantum)は、０．５のグリッド座標軸系(grid co-ordinate axis system)になるように選択されるのが好ましい。しかし、任意の適切な値が量子に使用されてもよい。
【００５５】
処理１０００は、次のステップ１００５に続く。ステップ１００５において、プロセッサ１０５は、ヒストグラム１２００を使用してグリッド間隔を判定する。尚、右隣接ドットの殆どは、グリッドの間隔の辺りにクラスタ化(clustered)される。従って、グリッド間隔は、最も多く存在するｘ座標のｘ値を取得することにより判定され、図１２の例において、それは周波数バー１２０４で示される。
【００５６】
（グリッド平行移動の判定）
次に、処理７００のステップ７０９で実行されるようなグリッドのグリッド平行移動を判定する処理１３００について、図１３を参照して更に詳細に説明する。メモリ１０６に格納されたドット座標のリスト及びグリッド間隔は、処理１３００に対する入力として提供される。処理１３００は、グリッドの全てのドットに対するグリッド平行移動を判定する。すなわち、処理１３００は、全てのドットに対して、ドットのグリッド点の場所を推定する。
【００５７】
処理は、ステップ１３０３で開始する。ステップ１３０３において、プロセッサ１０５は、グリッドに対してメモリ１０６に格納されたドットのリストからまだ処理されていないドットを選択する。この選択されたドットを「現在のドット」(current dot)と呼ぶ。プロセッサ１０５は、現在のドットのローカルウィンドウ内に存在する全てのドットを判定し、そのドットをメモリ１０６内に構成されるローカルウィンドウドットのリストに配置する。例えば、図１４は、雑音のある環境において、グリッドのような構成１４００で配置されるドットを示す。グリッド１４００は現在のドット１４０２を含み、現在のドット１４０２のグリッド点の場所１４０３である。現在のドット１４０２のローカルウィンドウ１４０１が更に示される。ローカルウィンドウ１４０１は、図１４の例において、辺の長さ５を有する。ローカルウィンドウ１４０１のサイズは、グリッド環境に存在する雑音の種類及び大きさに依存する。ローカルウィンドウの好ましいサイズは３０である。
【００５８】
次のステップ１３０５において、プロセッサ１０５は、メモリ１０６からローカルウィンドウドット（例えば、１４０４）のリストを取得し、以下のように、グリッド間隔が２πとなるように各ドット(xk, yk)の座標を正規化する。
【００５９】
【数４】
【００６０】
処理１３００は、次のステップ１３０７に続く。ステップ１３０７において、プロセッサ１０５は、メモリ１０６に格納された正規化(normalised)されたローカルウィンドウドットのリストを取得し、２つのフェーザ(phasors)xOffset及びyOffsetを判定する。
【００６１】
【数５】
【００６２】
ステップ１３０７における加算は、正規化されたローカルウィンドウドットのリスト全体に対して行なわれる。xOffset及びyOffsetの位相は、それぞれ、現在のドットがグリッド点からｘ方向及びｙ方向に位相がずれている量を推定する。
【００６３】
次のステップ１３０９において、プロセッサ１０５は、現在のドットのグリッド点の場所を判定する。現在のドットを(xc, yc)で示す。現在のドットに対するグリッド点(xGrid, yGrid)は以下の式で与えられる。
【００６４】
【数６】
【００６５】
処理１３００は、次のステップ１３１１に続く。ステップ１３１１において、自身のグリッド点をまだ判定していないドットが存在するとプロセッサ１０５が判定した場合、処理１３００はステップ１３０３に戻る。存在すると判定しなかった場合、処理１３００は終了する。
【００６６】
（変調量子の判定）
次に、ステップ８０５で実行されるような変調量子を判定する処理１５００について、図１５を参照して詳細に説明する。処理１５００は、最初のステップ１５０２で開始する。ステップ１５０２において、プロセッサ１０５は、入力としてグリッドのドットを取得する。ステップ１００２について上述したように、グリッドの各ドット(x, y)に対して、水平方向の同一列においてドット(x, y)の右側の最隣接ドットが判定され、メモリ１０６に格納される。次のステップ１５０３において、プロセッサ１０５は、ステップ１００３について上述したように、ステップ１００２でメモリ１０６に格納された右隣接ドット(a, b)の各々を取得し、(x, y)からの差分ベクトル(dx, dy)を判定する。
【００６７】
次のステップ１５０４において、プロセッサ１０５は、ステップ１５０３で判定された各差分ベクトルのｙ値の周波数ヒストグラムを判定する。例として、図１６はヒストグラム１６００を示す。ヒストグラムは、周波数軸１６０１、ｙ座標軸１６０２及び複数の周波数バー（例えば、１６０３）を含む。ｙ座標軸における各量子のサイズは、ドット座標の粒度に関連付けられる。繰り返しになるが、量子は、０．５のグリッド座標軸系になるように選択されるのが好ましい。しかし、任意の適切な値が量子に使用されてもよい。
【００６８】
次のステップ１５０５において、プロセッサ１０５は、ヒストグラム１６００を使用して、グリッドの変調量子(modulation quantum)を判定する。ステップ１５０５において、プロセッサ１０５は、ゼロの近くでヒストグラム１６００のピークを判定する。ピークは、「ピークウィンドウ半径」(peak-window-radius)と呼ばれる特定の半径内の隣接するｙ値の全ての周波数バーより大きい関連する周波数バーを有するｙ値になるように規定される。ピークウィンドウ半径は、グリッド間隔に比例する。説明される処理において、ピークウィンドウ半径は、グリッド間隔の１／１０であるのが好ましい。そのようなピークの例は、図１６に示されるような１６０３である。ここで、ピークウィンドウ半径は１である。いくつかのピーク（例えば、５つのピーク）が原点１６０１の周囲で判定されると、変調量子は、隣接するピーク間の距離の平均を取得することにより判定される。処理１５００は、ステップ１５０５の後に終了する。
【００６９】
（変調量子を判定する別の方法）
方法８００のステップ８０５のような変調量子を判定する別の処理１７００を図１７に示す。処理１７００は、ステップ１７０２で開始する。ステップ１７０２において、プロセッサ１０５は、メモリ１０６内に構成されるドットのリスト中の全てのドットに対して、最近接グリッド点を推定する。すなわち、プロセッサ１０５は、グリッドのドットに対するグリッド平行移動を判定する。上述したように、最近接グリッド点は、ステップ１７０２において、図１３の処理１３００を使用して各ドットに対して判定される。
【００７０】
次のステップ１７０３において、プロセッサ１０５は、ステップ１７０２で判定されたドットの対応するグリッド点に対する各ドットからのオフセットベクトルを判定する。次のステップ１７０４において、プロセッサ１０５は、上述のように、ステップ１７０３で判定されたオフセットベクトルのｙ成分のヒストグラムを判定する。次のステップ１７０５において、プロセッサ１０５は、ステップ１７０４で判定されたヒストグラムの３つの最大ピークを判定する。それらピークのうち最小のピークと２番目に小さいピークとの距離及び２番目に小さいピークと最大ピークとの距離は、グリッドに対する変調量子にほぼ等しい。ステップ１７０６において、プロセッサ１０５はそれら２つの距離の平均を検出し、それを変調量子として使用する。
【００７１】
（別の構成）
図９のステップ９０２において、処理９００は、各ドットに対する最近接ドットを判定する。別の構成においては、最近接ドットが、グリッドのドットのサブセットに対してのみ判定されてもよい。この例において、最近接ドットが判定されるドットのサブセットは、例えばドットをランダムに選択したものでもよい。あるいは、最近接ドットは、グリッドの上部２５％内に存在するドットに対してのみ判定されてもよく、又はグリッドの所定の帯域に存在するドットに対してのみ判定されてもよい。この例において、処理９００の後続するステップ９０３及び９０４では、サブセット中のドットのみが考慮される。
【００７２】
更に別の構成において、１つの最近接ドットのみを使用するのではなく、Ｎ個の最近接ドットを使用して変位ベクトルを判定してもよい。例えば、Ｎは２又は４に等しくてもよい。この構成により、複雑性及び速度と引き換えに、雑音の多いグリッドにおいてグリッド方位をより正確に検出できる場合がある。
【００７３】
図９のステップ９０６において、処理９００は、先のステップ９０５で判定された変位ベクトルの角度からグリッド方位の角度φを判定する。ステップ９０６において多くの別の方法が使用されてもよいことは、当業者には理解されるだろう。例えば、変位ベクトルの角度のヒストグラムが判定されてもよい。この例において、多数の変位ベクトルの角度を含むヒストグラムビンは、グリッド方位の角度φに対応する。
【００７４】
図１０のステップ１００３において、差分ベクトルのセットが判定され、全ての差分ベクトルが後続するステップ１００４及び１００５において使用される。別の構成において、差分ベクトルのランダムなサブセットが、ステップ１００４及び１００５で使用されてもよく、グリッド間隔に対する値は、そのランダムなサブセットに基づいて判定される。この例において、ステップ１００４及び１００５の処理は、Ｎ回（例えば、３０回）繰り返され、繰り返す度に差分ベクトルの異なるランダムなサブセットが使用される。これにより、Ｎ＋１個の異なるグリッド間隔の値が得られる。実際のグリッド間隔は、それらＮ＋１個の値のモードになるように判定されてもよい。この別の構成により、複雑性及び速度と引き換えに、雑音の多いグリッドにおいてグリッド間隔をより正確に得られる場合がある。
【００７５】
同様に、差分ベクトルのランダムなサブセットが、複雑性及び速度と引き換えに変調量子をより正確に検出するために、処理１５００のステップ１５０３及び１５０４において使用されてもよい。
【００７６】
図１０のステップ１００４及び１００５において、グリッド間隔は、ステップ１００３で発見された差分ベクトルのｘ座標から判定される。グリッド間隔を判定するために、多くの別の処理が使用されてもよいことは、当業者には理解されるだろう。例えば、グリッド間隔は、ステップ１００３で判定された差分ベクトルのｘ座標の平均として判定されてもよい。
【００７７】
説明された構成は、コンピュータ産業及びデータ処理産業に適用可能であることは、上述から明らかである。
【００７８】
上述において、本発明のいくつかの実施形態のみを説明したが、本発明の趣旨の範囲から逸脱せずに変形及び／又は変更が可能である。それら実施形態は単なる例示であり、限定するものではない。
【図面の簡単な説明】
【００７９】
【図１】説明された構成が実現される汎用コンピュータを概略的に示すブロック図である。
【図２】位相変調されたドットの配列を示す図である。
【図３】標準グリッドに従って配置されたドットの別の配列を示す図である。
【図４】位相変調されたドットの更に別の配列を示す図である。
【図５】図４の標準正方形グリッドの交点に対するドット変調位置を示す図である。
【図６】デジタルデータ記憶装置の数字の順序付けを示す図である。
【図７】ドットのグリッドのグリッド方位、グリッド間隔及びグリッド平行移動を判定する処理を示すフローチャートである。
【図８】ドットの変調グリッドにおけるグリッド方位、グリッド間隔、グリッド平行移動及び変調量子を判定する処理を示すフローチャートである。
【図９】図７の処理において実行されるグリッド方位を判定する処理を示すフローチャートである。
【図１０】図７の処理において実行されるグリッドのグリッド間隔を判定する処理を示すフローチャートである。
【図１１】右隣接差分ベクトルのリストを示すグラフである。
【図１２】ｘ値を示す周波数ヒストグラムである。
【図１３】図７の処理において実行されるグリッドのグリッド平行移動を判定する処理を示すフローチャートである。
【図１４】グリッドのような構成で配置されるドットと、グリッドのグリッド平行移動を推定する際に使用されるローカルウィンドウとを示す図である。
【図１５】変調量子を判定する処理を示すフローチャートである。
【図１６】ｙ値を示す周波数ヒストグラムである。
【図１７】変調量子を判定する別の処理を示すフローチャートである。
【特許請求の範囲】
【請求項１】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する処理方法であって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するステップと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するステップと、
前記判定したベクトルを使用して前記グリッド方位を判定するステップと
を備えることを特徴とする処理方法。
【請求項２】
前記ベクトルを使用してドットの前記グリッドに対する間隔の値を判定するステップを更に備えることを特徴とする請求項１に記載の処理方法。
【請求項３】
１つ以上の隣接する境界領域に基づいて、前記変調グリッドから前記ドットの少なくとも１つに対する前記仮想グリッドへの平行移動を判定するステップを更に備えることを特徴とする請求項１に記載の処理方法。
【請求項４】
前記ベクトルのうち少なくとも１つは変位ベクトルであることを特徴とする請求項１に記載の処理方法。
【請求項５】
前記ベクトルのうち少なくとも１つは差分ベクトルであることを特徴とする請求項１に記載の処理方法。
【請求項６】
ドットの前記グリッドは位相変調されることを特徴とする請求項１に記載の処理方法。
【請求項７】
符号化データに対するグリッドを判定する処理方法であって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するステップと、
前記統計平均に基づいて、前記データの角度方向を判定するステップと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するステップと
を備えることを特徴とする処理方法。
【請求項８】
前記グリッドにおける隣接データ点の間隔を判定するステップを更に備えることを特徴とする請求項６に記載の処理方法。
【請求項９】
前記グリッドに関して、各データ点に対するオフセットを判定するステップを更に備えることを特徴とする請求項６に記載の処理方法。
【請求項１０】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する処理方法であって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するステップと、
前記変位ベクトルを使用して前記グリッド方位を判定するステップと、
前記グリッド間隔を判定するステップと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するステップと
を備えることを特徴とする処理方法。
【請求項１１】
符号化データに対するグリッドを判定する処理方法であって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するステップと、
前記グリッドの隣接データ点の間隔を判定するステップと、
前記グリッドに関して、各データ点に対するオフセットを判定するステップと
を備えることを特徴とする処理方法。
【請求項１２】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する装置であって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するベクトル判定手段と、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去する変調除去手段と、
前記判定したベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段と
を備えることを特徴とする装置。
【請求項１３】
符号化データに対するグリッドを判定する装置であって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定する統計平均判定手段と、
前記統計平均に基づいて、前記データの角度方向を判定する角度方向判定手段と、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するグリッド判定手段と
を備えることを特徴とする装置。
【請求項１４】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する装置であって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定する変位ベクトル判定手段と、
前記変位ベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段と、
前記グリッド間隔を判定するグリッド間隔判定手段と、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するグリッド平行移動判定手段と
を備えることを特徴とする装置。
【請求項１５】
符号化データに対するグリッドを判定する装置であって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定する角度方向判定手段と、
前記グリッドの隣接データ点の間隔を判定する間隔判定手段と、
前記グリッドに関して、各データ点に対するオフセットを判定するオフセット判定手段とを具備する装置。
【請求項１６】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムであって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項１７】
符号化データに対するグリッドを判定するコンピュータプログラムであって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項１８】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムであって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコードと、
前記グリッド間隔を判定するコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項１９】
符号化データに対するグリッドを判定するコンピュータプログラムであって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコードと、
前記グリッドの隣接データ点の間隔を判定するコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項２０】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコンピュータプログラムコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコンピュータプログラムコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項２１】
符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコンピュータプログラムコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコンピュータプログラムコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項２２】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコンピュータプログラムコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードと、
前記グリッド間隔を判定するコンピュータプログラムコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項２３】
符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコンピュータプログラムコードと、
前記グリッドの隣接データ点の間隔を判定するコンピュータプログラムコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項１】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する処理方法であって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するステップと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するステップと、
前記判定したベクトルを使用して前記グリッド方位を判定するステップと
を備えることを特徴とする処理方法。
【請求項２】
前記ベクトルを使用してドットの前記グリッドに対する間隔の値を判定するステップを更に備えることを特徴とする請求項１に記載の処理方法。
【請求項３】
１つ以上の隣接する境界領域に基づいて、前記変調グリッドから前記ドットの少なくとも１つに対する前記仮想グリッドへの平行移動を判定するステップを更に備えることを特徴とする請求項１に記載の処理方法。
【請求項４】
前記ベクトルのうち少なくとも１つは変位ベクトルであることを特徴とする請求項１に記載の処理方法。
【請求項５】
前記ベクトルのうち少なくとも１つは差分ベクトルであることを特徴とする請求項１に記載の処理方法。
【請求項６】
ドットの前記グリッドは位相変調されることを特徴とする請求項１に記載の処理方法。
【請求項７】
符号化データに対するグリッドを判定する処理方法であって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するステップと、
前記統計平均に基づいて、前記データの角度方向を判定するステップと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するステップと
を備えることを特徴とする処理方法。
【請求項８】
前記グリッドにおける隣接データ点の間隔を判定するステップを更に備えることを特徴とする請求項６に記載の処理方法。
【請求項９】
前記グリッドに関して、各データ点に対するオフセットを判定するステップを更に備えることを特徴とする請求項６に記載の処理方法。
【請求項１０】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する処理方法であって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するステップと、
前記変位ベクトルを使用して前記グリッド方位を判定するステップと、
前記グリッド間隔を判定するステップと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するステップと
を備えることを特徴とする処理方法。
【請求項１１】
符号化データに対するグリッドを判定する処理方法であって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するステップと、
前記グリッドの隣接データ点の間隔を判定するステップと、
前記グリッドに関して、各データ点に対するオフセットを判定するステップと
を備えることを特徴とする処理方法。
【請求項１２】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定する装置であって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するベクトル判定手段と、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去する変調除去手段と、
前記判定したベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段と
を備えることを特徴とする装置。
【請求項１３】
符号化データに対するグリッドを判定する装置であって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定する統計平均判定手段と、
前記統計平均に基づいて、前記データの角度方向を判定する角度方向判定手段と、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するグリッド判定手段と
を備えることを特徴とする装置。
【請求項１４】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定する装置であって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定する変位ベクトル判定手段と、
前記変位ベクトルを使用して前記グリッド方位を判定するグリッド方位判定手段と、
前記グリッド間隔を判定するグリッド間隔判定手段と、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するグリッド平行移動判定手段と
を備えることを特徴とする装置。
【請求項１５】
符号化データに対するグリッドを判定する装置であって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定する角度方向判定手段と、
前記グリッドの隣接データ点の間隔を判定する間隔判定手段と、
前記グリッドに関して、各データ点に対するオフセットを判定するオフセット判定手段とを具備する装置。
【請求項１６】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムであって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項１７】
符号化データに対するグリッドを判定するコンピュータプログラムであって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項１８】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムであって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコードと、
前記グリッド間隔を判定するコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項１９】
符号化データに対するグリッドを判定するコンピュータプログラムであって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコードと、
前記グリッドの隣接データ点の間隔を判定するコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコードと
を備えることを特徴とするコンピュータプログラム。
【請求項２０】
ドットの変調グリッドにおいて符号化されたデータに対して１つ以上のパラメータを判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
前記ドットは仮想グリッドに関して変調され、前記グリッドの少なくとも１つのドットから最近接ドットへの１つ以上のベクトルを判定するコンピュータプログラムコードと、
前記仮想グリッドを判定するために、前記ベクトルを使用して前記変調を除去するコンピュータプログラムコードと、
前記判定したベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項２１】
符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
前記データの少なくとも１つの最隣接データ点に関して、前記データのデータ点の変位の方向の統計平均を判定するコンピュータプログラムコードと、
前記統計平均に基づいて、前記データの角度方向を判定するコンピュータプログラムコードと、
前記角度方向に基づいて、前記データに対する前記グリッドを判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項２２】
ドットの変調グリッドにおいて符号化されたデータに対してグリッド方位、グリッド間隔及びグリッド平行移動を判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
少なくとも１つのドットの各々から最近接ドットへの変位ベクトルを判定するコンピュータプログラムコードと、
前記変位ベクトルを使用して前記グリッド方位を判定するコンピュータプログラムコードと、
前記グリッド間隔を判定するコンピュータプログラムコードと、
近接する複数のドットのうち１つの隣接ドットを使用して、少なくとも１つのドットの前記グリッド平行移動を判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【請求項２３】
符号化データに対するグリッドを判定するコンピュータプログラムを記録したコンピュータ可読媒体であって、
データ点の変位の方向の統計平均及び最隣接データ点に基づいて判定される前記データの角度方向を判定するコンピュータプログラムコードと、
前記グリッドの隣接データ点の間隔を判定するコンピュータプログラムコードと、
前記グリッドに関して、各データ点に対するオフセットを判定するコンピュータプログラムコードと
を備えることを特徴とするコンピュータ可読媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００７−１５１０８２（Ｐ２００７−１５１０８２Ａ）
【公開日】平成１９年６月１４日（２００７．６．１４）
【国際特許分類】
【外国語出願】
【出願番号】特願２００６−２４８６１８（Ｐ２００６−２４８６１８）
【出願日】平成１８年９月１３日（２００６．９．１３）
【特許番号】特許第３９１９８０８号（Ｐ３９１９８０８）
【特許公報発行日】平成１９年５月３０日（２００７．５．３０）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成１９年６月１４日（２００７．６．１４）
【国際特許分類】
【出願番号】特願２００６−２４８６１８（Ｐ２００６−２４８６１８）
【出願日】平成１８年９月１３日（２００６．９．１３）
【特許番号】特許第３９１９８０８号（Ｐ３９１９８０８）
【特許公報発行日】平成１９年５月３０日（２００７．５．３０）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]