位置同定機能付き印刷物、２次元座標同定装置、画像形成装置及びその方法
【課題】 広大な面積の符号化が可能であって、位置検出精度を向上させた２次元座標同定装置を提供する。
【解決手段】 印刷物上の符号化領域が複数の符号化単位に分割され、符号化単位ごとに、印刷物上での位置を示す座標値のコード情報と、印刷物を識別する識別番号のコード情報とが記録された印刷物の所定範囲の画像を読み込む画像読み取り部２１と、読み込まれた所定範囲の画像から識別番号と、印刷ページ上の座標値とを示すコード情報を検出する識別番号符号検出部２７、Ｘ座標符号検出部３２、Ｙ座標符号検出部３６と、コード情報を復号化し、識別番号と座標値とを出力する識別番号符号復号部２９、Ｘ座標復号部３３、Ｙ座標復号部３７とを有している。
【解決手段】 印刷物上の符号化領域が複数の符号化単位に分割され、符号化単位ごとに、印刷物上での位置を示す座標値のコード情報と、印刷物を識別する識別番号のコード情報とが記録された印刷物の所定範囲の画像を読み込む画像読み取り部２１と、読み込まれた所定範囲の画像から識別番号と、印刷ページ上の座標値とを示すコード情報を検出する識別番号符号検出部２７、Ｘ座標符号検出部３２、Ｙ座標符号検出部３６と、コード情報を復号化し、識別番号と座標値とを出力する識別番号符号復号部２９、Ｘ座標復号部３３、Ｙ座標復号部３７とを有している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元表面上に一様に配置されたシンボルの一部を読み込み、２次元表面上の読み込み位置を同定する技術に関する。
【背景技術】
【０００２】
近年、２次元表面上にシンボルを一様に配置し、シンボルを読み込むことで２次元表面上の位置を同定する技術が提案されている。例えば、紙等に印刷されたテスト問題上に、一様にシンボルを印刷しておき、解答者が、選択した解答位置をスキャナ等でなぞることで、選択された解答が通信事業者などに送られるといったシステムが提案されている（例えば、図１８参照）。
【０００３】
この２次元平面の符号化に、Ｍ系列の符号が使用されることが多い。Ｍ系列の符号は、「長さ２ｍ−１のＭ系列符号から、長さｍの部分系列を切り出したときに、いずれの２つの部分系列の並びも決して一致しない」という性質を持つ。この性質を利用して平面を符号化する技術が種々提案されている。
【０００４】
Ｍ系列符号は、以下に示すｐ次の漸化式から生成される系列のうちで周期が最大（２ｐ−１）のものをいう（疑似ランダム系列とも呼ばれる）。
【０００５】
【数１】
【０００６】
例えば、ｐ＝５、Ｃ１＝１，Ｃ２＝１，Ｃ３＝１，Ｃ４＝０，Ｃ５＝１の場合、図１９に示すＭ系列（長さ２５−１＝３１）が生成される。図１９に示すようにＭ系列の異なる位置から取り出した長さｐの部分系列Ａ，Ｂ，Ｃは、決して一致しない。この性質を利用して、平面上の座標を１ビットの精度で位置決めすることができる。
【０００７】
例えば、１ビットを０．３ｍｍのシンボルで表現すると、Ａ４長手方向の２９７ｍｍを表現するためには、以下に示すように１０次のＭ系列で符号化可能である。
（２１０−１）×０．３ｍｍ＝１０２３×０．３ｍｍ＝３０６．９ｍｍ
しかしながら、これではＡ４を１枚しか符号化できない。広大な面積を符号化しようとすると、もっと高次のＭ系列が必要になる。このため、平面上の位置を同定する時に、読み込む面積を大きくしなければならず、さらに、復号が複雑になるという問題が生じてしまう。
【０００８】
特許文献１では、座標位置を表すために、図２０に示すように平面上のＹ軸方向に平行に、同じＭ系列符号を配置している。Ｙ軸方向に平行に並べられたＭ系列符号は、Ｘ軸方向には適当に位相をずらして配置している。例えば、図２０では左から第２列目と第３列目では２ビットずらしており、第３列目と４列目では９ビットずらしており、第４列目と第５列目では２４ビットずらしており、第５列目と第６列目では１０ビットずらしている。これらの差は、同じＸ座標上の位置であれば一致する。これらの差をもとにＸ座標を表現する。Ｙ座標の表現についてもＸ軸の表現と同様に、Ｘ軸方向に平行に並べられたＭ系列符号を、Ｙ軸方向に適当に位相をずらして配置している。なお、ここでは、簡単のために同期方法を省略して説明した。
【０００９】
【特許文献１】特表２００３−５１１７６２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１では、Ａ４などの実用的な大きさで利用する場合に、紙面の端を特定するための工夫が必要となる。すなわち、図２１に示すように全符号化領域上での位置は同定できるが、利用面（ページ）の位置を同定するためには、図２１に示すように符号化領域上でのページの位置を獲得する必要がある。また、複数のＭ系列符号を区切るための工夫により、符号化の冗長度が大きくなるという欠点を有している。さらに符号化及び復号化のアルゴリズムが複雑で計算負荷が高くなるという欠点を有している。
【００１１】
本発明は上記事情に鑑みてなされたものであり、広大な面積の符号化が可能であると共に、位置検出精度を向上させた位置同定機能付き印刷物、２次元座標同定装置、画像形成装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の位置同定機能付き印刷物は、印刷物上の符号化領域を複数の符号化単位に分割し、前記符号化単位ごとに、前記印刷物上での位置を示す座標値のコード情報と、前記印刷物を識別する識別番号のコード情報とを記録した構成を備えている。このように本発明は、印刷物上での位置を示す座標値と、印刷物を識別する識別番号とを別々にコード化して記録しているので、広大な面積の符号化が可能となる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。さらに、各印刷物に、印刷物上の座標値を示すコード情報を記録しているので、位置検出精度を高めることができる。
【００１３】
上記位置同定機能付き印刷物において、前記座標値を表すコード情報は、Ｍ系列符号によって符号化されているとよい。座標値を表すコード情報が、Ｍ系列符号によって符号化されているので、印刷物上のどの位置を読み込んでも座標を特定することができる。
【００１４】
上記位置同定機能付き印刷物において、前記複数の符号化単位間は、同期符号によって区切られているとよい。印刷物上に記録された情報を読み込んだ時に、読み込み位置を簡単に特定することができる。
【００１５】
上記位置同定機能付き印刷物において、前記コード情報は、１つで多ビットを表現可能なシンボルで表現されているとよい。コード情報が、１つで多ビットを表現可能なシンボルで表現されているので、印刷物の表面に印刷するシンボル数を削減することができる。
【００１６】
上記位置同定機能付き印刷物において、前記コード情報及び前記同期符号は、シンボルによって表現され、前記同期符号を表すシンボルによって、前記コード情報を表すシンボルの向きを特定可能であるとよい。コード情報を表すシンボルの向きを特定し、正確に情報を取り出すことができる。
【００１７】
上記位置同定機能付き印刷物において、前記識別番号を示すコード情報は、前記符号化単位ごとに繰り返し記録されているとよい。識別番号が、符号化単位ごとに繰り返し記録されているので、どこを読み出しても再現し復号化可能となる。
【００１８】
上記位置同定機能付き印刷物において、符号化する印刷物のページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更するとよい。従って、印刷物のページ数が増えても、符号化することが可能となる。
【００１９】
上記位置同定機能付き印刷物において、前記符号化領域の大きさに応じて、前記座標値を表す前記コード情報のコード長を変更するとよい。従って、印刷物の大きさが変更になっても、符号化することができる。
【００２０】
本発明の２次元座標同定装置は、印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込む読込手段と、読み込まれた前記所定範囲の画像から前記識別番号と、前記符号化単位の位置を示す座標値とを示す前記コード情報を検出する検出手段と、前記コード情報を復号化し、前記識別番号と前記座標値とを出力する復号化手段とを有する構成としている。このように本発明は、印刷物上の位置を示す座標値のコード情報と、印刷物の識別番号を示すコード情報とがそれぞれ記録された印刷物から所定範囲の画像を読み込んで、コード情報の検出、復号化を行なっているので、印刷物の識別番号と、印刷物上の座標との特定を精度よく行なうことができる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。
【００２１】
上記２次元座標同定装置において、前記検出手段は、複数の前記符号化単位から前記コード情報を読み込んで、１つの前記識別情報を表す前記コード情報を検出するとよい。読み込み範囲が符号化単位に一致しなくても、複数の符号化単位からのコード情報によって１つの識別情報を表すコード情報として検出するので、画像の読み込み位置を意識する必要がなく、どの位置で読み込んでも精度よく識別番号と座標を得ることができる。
【００２２】
上記２次元座標同定装置において、前記コード情報は、１つで多ビットを表現可能なシンボルで表現され、前記複数の符号化単位間には、前記コード情報を表す前記シンボルの向きを特定可能なシンボルが形成されており、前記検出手段は、前記シンボルの向きを特定して前記コード情報を特定するとよい。シンボルの向きを特定し、正確に情報を取り出すことができる。
【００２３】
上記２次元座標同定装置において、前記座標値の前記コード情報と、その前又は後の所定ビットとから前記座標値の前記コード情報の誤りを検出する誤り検出手段を有するとよい。検出した座標値に誤りがあるか否かを判定することができる。
【００２４】
上記２次元座標同定装置において、前記座標値のコード情報は、Ｍ系列符号からなり、前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出する誤り検出手段を有するとよい。座標値の誤りを正確に検出することができる。
【００２５】
上記２次元座標同定装置において、前記検出した誤りが、その誤りから正しいビット列を推定することのできる誤りであった場合に、前記誤りを訂正する訂正手段を有するとよい。訂正できる誤りであった場合に、誤りを訂正して正しい座標値に復号することができる。
【００２６】
本発明の画像形成装置は、印刷物を識別する識別番号をコード化する識別番号コード化手段と、前記印刷物上の位置を示す座標値をコード化する座標値コード化手段と、前記識別番号と前記座標値とのコードに従って、前記識別番号と前記座標値とをシンボル化するシンボル化手段と、印刷画像と、前記シンボル化された前記識別番号と前記座標値とを合成する合成手段と、前記印刷物上の符号化領域を複数の符号化単位に分割し、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録し、前記コード情報上に前記印刷画像が形成された前記印刷物を形成する画像形成手段と、を有する構成としている。このように本発明は、印刷物上での位置を示す座標値と、印刷物を識別する識別番号とを別々にコード化して記録しているので、広大な面積の符号化が可能となる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。さらに、各印刷物に、印刷物上の座標値を示すコード情報を記録しているので、位置検出精度を高めることができる。
【００２７】
上記画像形成装置において、前記位置を示す座標値は、Ｍ系列符号によって符号化されているとよい。座標値を表すコード情報が、Ｍ系列符号によって符号化されているので、印刷物上のどの位置を読み込んでも座標を特定することができる。
【００２８】
上記画像形成装置において、前記識別番号コード化手段は、符号化するページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更するとよい。従って、印刷物のページ数が増えても、符号化することが可能となる。
【００２９】
上記画像形成装置において、前記座標値コード化手段は、前記符号化領域の面積に応じて、前記座標値を表す前記コード情報の大きさを変更するとよい。従って、印刷物の大きさが変更になっても、符号化することができる。
【００３０】
本発明の２次元座標同定方法は、印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込むステップと、読み込んだ前記所定範囲の画像から前記識別番号と、前記印刷ページ上の座標値とを示す前記コード情報を検出するステップと、前記コード情報を復号化し、前記識別番号と前記座標値とを出力するステップとを有している。このように本発明は、印刷物上の位置を示す座標値のコード情報と、印刷物の識別番号を示すコード情報とがそれぞれ記録された印刷物から所定範囲の画像を読み込んで、コード情報の検出、復号化を行なっているので、印刷物の識別番号と、印刷物上の座標との特定を精度よく行なうことができる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。
【００３１】
上記２次元座標同定方法において、前記座標値の前記コード情報と、その前又は後の所定ビットとから前記コード情報の誤りを検出するステップを有しているとよい。検出した座標値に誤りがあるか否かを判定することができる。
【００３２】
上記２次元座標同定方法において、前記座標値のコード情報は、Ｍ系列符号からなり、前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出するステップを有しているとよい。座標値の誤りを正確に検出することができる。
【発明の効果】
【００３３】
本発明は、広大な面積の符号化が可能であると共に、位置検出精度を向上させることができる。
【発明を実施するための最良の形態】
【００３４】
添付図面を参照しながら本発明の好適な実施例を説明する。
【実施例】
【００３５】
［位置同定機能付き印刷物］
まず、位置同定機能付き印刷物の構成について説明する。
本実施例では、符号化する全面積を、実用的な大きさの平面（例えば、Ａ３，Ａ４）に分割し、この平面を符号化領域とする。なお、以下では、説明の簡略化のため符号化領域をページと呼ぶ。各ページには、ページを識別する識別番号と、ページ上での位置を表す座標（Ｘ，Ｙ）を分けて符号化する。各ページは、図１に示すように複数の符号化単位に分割され、各符号化単位に所定の情報が記録される。１つの符号化単位は、縦６個、横７個の長方形で表される。長方形の１マスに１つのシンボルが形成される。シンボルとは、符号化されたコードをページ上に表示するためのものであり、例えば、図２（Ａ）に示すような非対称のシンボルや、図２（Ｂ）に示すような対称シンボルが用いられる。図２に示すシンボルは、所定角度回転させることによって１シンボルで４つの情報、すなわち２ビットを表すことができる。１つのシンボルは、例えば６００ｄｐｉで２ドット、シンボル間の間隔は０．３ｍｍで形成される。これ以外にも、利用する平面と利用方法に応じて、他の形状や、異なる大きさのシンボルが利用できる。符号化単位も、表現するページ数と面積とに応じて、より多くのあるいは少ないシンボル数で表現してもよい。
【００３６】
１つの符号化単位には、図１に示すように識別番号を表示するシンボルと、ページ上のＸ座標とＹ座標を表示するシンボルと、他の符号化領域との区切りを示すシンボル（以下、同期符号と呼ぶ）とが記録される。配置の一例として、図１に示すように符号化単位の左辺と底辺とに同期符号のシンボルを配置し、その内側のＹ方向にＹ座標を示すシンボルを５つと、同じく内側のＸ方向にＸ座標を示すシンボルを５つとを配置している。Ｘ座標、Ｙ座標を表示するシンボルの内側には、識別番号を表示するシンボルが２０配置される。
【００３７】
識別番号は、図１に示すように２０シンボルで表現される。１シンボルで２ビットの情報を表現することができるので、２０シンボルの場合、２４０＝１．１×１０１２、約１兆枚を符号化することができる。同じ用紙上の複数の符号化領域には、同じ識別番号を示すシンボルが書き込まれる。ここでは２０シンボルで説明しているが、表現するページ数に応じて、より多くのあるいは少ないシンボル数で表現してもよい。
【００３８】
Ｘ座標又はＹ座標は、Ｍ系列符号によって表現される。１符号化単位では、Ｘ座標，Ｙ座標ともに１０ビット（５シンボル）で表現され、Ｍ系列符号長は、２１０−１＝１０２３ビットである。ここでは５シンボルで説明しているが、表現する面積に応じて、より多くのあるいは少ないシンボル数で表現してもよい。
【００３９】
なお、１シンボルで２ビットを表す場合、１０２３ビットは５１１．５シンボルで表現され、図３に示すようにＡ４長手方向のサイズの半分にしかならない。しかしながら、周期が奇数であることから、次の周期では１ビットずれで表現される。このことから２周期でＡ４長手方向を符号化することができる。
【００４０】
符号化単位を区切る同期符号は、１シンボルの２ビット分のうちの１ビットで表現される。図１に示すように複数の符号化単位は、同期符号によって区切られている。同期符号を設けることによって、印刷物上に記録された情報を読み込んだ時に、読み込み位置を簡単に特定することができる。この同期符号は、例えば、全て「０」や「１」で揃える。これによって読み込んだ際に、連続する値を検出することで符号化単位の境界と認識することができる。残りの１ビットは、識別番号あるいは誤り検出符号に利用する。
【００４１】
また、この同期符号として書き込む値を予め決めておけば、その他の識別番号、Ｘ座標やＹ座標の値を示すシンボルの向きを判定することができる。例えば、同期符号として書き込んだ値が「１」で、ページ上をスキャンした時に得られた値が「２」であった場合、図２に示すようにページは９０度回転しているので、９０度逆方向に回転させることで、識別番号、Ｘ座標やＹ座標の値を示すシンボルを正しく読み取ることができる。
【００４２】
このように配置された紙面上を、予め設定された所定の大きさ（符号化単位の大きさ）で読み込むことで、図４に示すように読み込み範囲が複数の符号化単位にまたがっても、その他の符号化単位からの情報で識別番号、Ｘ座標やＹ座標の値を補完することができる。
【００４３】
［画像形成装置の構成］
このような印刷物を印刷する画像形成装置１の構成を図５に示す。図５に示す画像形成装置１は、ページ座標情報入力部２と、識別番号符号化部３と、Ｘ座標符号化部４と、Ｙ座標符号化部５と、識別番号符号パターン化部６と、座標符号パターン化部７と、同期符号パターン化部８と、パターン合成部９と、画像合成部１０と、文書画像生成部１１と、画像生成部１２とを備えている。
【００４４】
ページ座標情報入力部２は、印刷する用紙のサイズ及び印刷向きと、識別番号とを入力する。識別番号符号化部３は、入力した識別番号を符号化すると共に、符号化した識別番号を配置する位置情報を識別番号符号パターン化部６に出力する。符号化の方法は、特に限定しないが、本実施例では、ページ数の表示に４０ビットが使用できる。
【００４５】
Ｘ座標符号化部４は、入力した用紙サイズ及び印刷向きに従って、Ｘ方向の座標値データを書き込む位置を求める。次に、Ｘ方向の座標値をＭ系列符号によって符号化し、符号化データと位置情報とを座標符号パターン化部７に出力する。同様に、Ｙ座標符号化部５は、入力した用紙サイズ及び印刷向きに従って、Ｙ方向の座標データを書き込む位置を求める。Ｙ方向の座標値をＭ系列符号によって符号化し、符号化データと位置情報とを座標符号パターン化部７に出力する。
【００４６】
識別番号符号パターン化部６は、符号化された識別番号を、その符号を表すシンボルのパターンに変換し、位置情報に従って識別番号配置位置にシンボル化された識別番号を配置する。座標符号パターン化部７は、Ｍ系列符号によって符号化されたＸ座標とＹ座標とを、その符号を表すシンボルのパターンに変換し、位置情報に従って、座標値の配置位置に該当するシンボル化された座標値を配置する。
【００４７】
同期符号パターン化部８は、入力した用紙サイズに従って、同期符号の配置位置を求める。次に、同期符号をその符号を表すシンボルのパターンに変換し、位置情報に従って同期符号配置位置にシンボル化された同期符号を配置する。
【００４８】
パターン合成部９は、シンボル化された識別番号と、シンボル化された座標値と、シンボル化された同期符号とを重ね合わせ、一つのシンボルパターンを形成する。
【００４９】
文書画像生成部１１は、用紙に印刷する文書や画像を生成する。また、文書画像生成部１１は、パーソナルコンピュータ（以下、ＰＣと呼ぶ）等と接続し、このＰＣで作成した文書や画像を取り込むものであってもよい。さらに、スキャナ等によって読み込んだ文書や画像を取り込むものであってもよい。
【００５０】
画像合成部１０は、パターン合成部９で合成したシンボルパターンに、文書画像生成部１１から取得した文書や画像を重ね合わせ、一つの印刷画像を形成する。画像合成部１０で合成された印刷画像は、画像生成部１２から印刷出力される。
【００５１】
次に、図１に示す位置同定機能付き印刷物を読み込んで、印刷物上の位置を同定する２次元座標同定装置２０について説明する。図６に示す２次元座標同定装置２０は、画像読み取り部２１と、パターン検出部２２と、ビット情報変換部２３と、同期符号検出部２４と、画像回転判定部２５と、ビット情報回転変換部２６と、識別番号符号検出部２７と、識別番号符号復元部２８と、識別番号符号復号部２９と、識別番号符号誤り検出部３０と、識別番号符号誤り訂正部３１と、Ｘ座標符号検出部３２と、Ｘ座標復号部３３と、Ｘ座標符号誤り検出部３４と、Ｘ座標符号誤り訂正部３５と、Ｙ座標符号検出部３６と、Ｙ座標復号部３７と、Ｙ座標符号誤り検出部３８と、Ｙ座標符号誤り訂正部３９と、ページ座標情報出力部４０とを備えている。
【００５２】
画像読み取り部２１は、ページと座標を同定すべき領域の画像を読み込む。パターン検出部２２は、読み込んだ画像からシンボルを検出する。ビット情報変換部２３は、パターン検出部２２で検出されたシンボルをビット行列に変換する。同期符号検出部２４は、ビット行列をスキャンし、同期符号のビット列を検出する。画像回転判定部２５は、検出した同期符号のビット列から画像の回転を判定する。ビット情報回転変換部２６は、画像回転判定部２５によって判定された回転角度で画像を逆回転させ、画像の向きを正規の向きに変換する。
【００５３】
識別番号符号検出部２７は、図４に示すように同期符号のビット列で分けられた４つの領域から識別番号を示すシンボルを検出する。読み込み範囲が符号化単位に一致しない場合、図４に示すように同期符号のビット列で分けられた４つの領域から識別番号を示すシンボルが取り出される。
【００５４】
識別番号符号復元部２８は、最大４つの領域から取り出されたシンボルを並び替えたり、同一シンボルを削除したりして、１符号化単位に書き込まれた図１に示す識別番号のシンボル（Ｐ１１〜Ｐ１５，Ｐ２１〜Ｐ２５，Ｐ３１〜Ｐ３５，Ｐ４１〜Ｐ４５）に変換する（これを、ビット行列と呼ぶ）。また、ビット行列をスキャンして、識別番号を表す並びのビット列に変換する。
【００５５】
識別番号復号部２９は、識別番号符号を復号する。識別番号符号誤り検出部３０は、識別番号を表す並びのビット列に、ノイズ等によって誤りが生じているか否かを判定する。識別番号符号誤り訂正部３１は、識別番号を表す並びのビット列に誤りがあると判定されると、その誤りを訂正する。
【００５６】
識別番号を表す符号の誤り検出には、パリティチェック符号などが用いられる。パリティチェック符号は、図７（Ａ）に示すように情報符号の和が偶数の場合には「０」を、情報符号の和が奇数の場合には「１」をチェック符号としておくものであり、図７（Ｂ）に示すように識別番号の符号の行方向のチェック符号と、列方向のチェック符号とを配置する。パリティチェック符号は、上述した同期符号の残り１ビットに含ませても良い。また誤り検出には、同一の最小ハミング距離を持つ線形符号の中で検査記号数が最小となるＲＳ符号（リードソロモン）を用いることもできる。例えば、４０ビットで符号化する場合、ブロックビット長を４ビットとし、符号ブロック数を１０、情報ブロック数を６としたＲＳ（１０，６）符号を使用すると、符号化効率は０．６程度となり、約６０００万枚を符号化できる。この符号化は、２ブロックまでの訂正が可能である。さらに、これ以外の誤り訂正方式も利用可能である。
【００５７】
Ｘ座標符号検出部３２は、Ｘ座標の座標値を表すシンボルを検出し、符号化されたＸ座標を表すビット列に変換する。Ｘ座標復号部３３は、符号化されたＸ座標を表すビット列を復号し、Ｘ座標を求める。なお、復号部３３の詳細な動作については後述する。
【００５８】
Ｘ座標符号誤り検出部３４は、符号化されたＸ座標を表すビット列に誤りが含まれているかを検出する。Ｘ座標符号誤り訂正部３５は、誤りを検出し、その誤りが訂正可能な誤りであった場合に、誤りを訂正する。これらの機能部の詳細な動作についても後述する。
【００５９】
Ｙ座標符号検出部３６は、Ｙ座標の座標値を表すシンボルを検出し、符号化されたＹ座標を表すビット列に変換する。Ｙ座標復号部３７は、符号化されたＹ座標を表すビット列を復号し、Ｙ座標を求める。復号部３７の詳細な動作についても後述する。
【００６０】
Ｙ座標符号誤り検出部３８は、符号化されたＹ座標を表すビット列に誤りが含まれているかを検出する。Ｙ座標符号誤り訂正部３９は、誤りを検出し、その誤りが訂正可能な誤りであった場合に、誤りを訂正する。これらの機能部の詳細な動作についても後述する。
【００６１】
ページ座標情報出力部４０は、復号された識別番号、Ｘ方向座標値、Ｙ軸方向座標値を出力する。
【００６２】
ここで、符号化された座標値の誤りを検出する方法について説明する。
従来、符号化されたビット列の誤りを検出するために、図８に示すようにパリティチェックビットが付加されている。パリティチェックビットは、図８（Ａ）に示すように各部分系列ごとに配置する方法と、図８（Ｂ）に示すように次数間隔ごとにパリティチェックビットを配置する方法とがある。図８（Ａ）に示すように各部分系列ごとに配置する場合、位置決め精度を１ビットにできるが、情報と同じ数のチェックビットとなるため冗長度が大きすぎるという問題が生じる。また、図８（Ｂ）に示す次数間隔ごとにチェックビットを配置する方法では、冗長度は小さいが、検査のために２倍の長さの読み込みが必要となる。
【００６３】
そこで、本実施例ではＭ系列符号の特性を利用した誤り検出を行なっている。ページ上の位置を表示するＸ、Ｙの座標値には、Ｍ系列符号を使用している。上述したようにＭ系列符号は、数１に示す漸化式を使用して算出される。このため、（ｐ＋１）の部分系列は、Ｍ系列符号を生成した漸化式を利用して、矛盾がないかを判定することができる。例えば、図９に示すように任意に取り出した５ビットに、Ｃ１〜Ｃ５の係数を掛け合わせて生成した符号と、取り出した５ビットの次のビットとが一致しているか否かを判定することで、符号の誤りを検出することができる。図９（Ａ）に誤りがなかった場合を示し、図９（Ｂ）に誤りがあった場合を示す。
【００６４】
しかしながら、図１０（Ａ）に示すように係数Ｃ１〜Ｃ５に「０」が含まれていると、「０」の位置の符号を検査することができない。そのため、係数に含まれる「０」の個数と、取り出した部分系列に含まれる「０」の数が一致してしまうと、誤りを検出することができない。
【００６５】
そこで、本実施例は、検査対象となるビット列の誤り検出を行なうと共に、図１０（Ｂ）に示すように対象となるビット列を前後にずらして、誤りがあるか否かを判定している。例えば、図１０（Ｂ）に示すように対象となるビット列を前に１ビットずらすことで、誤りがあった場合、前回の検査で係数「０」に該当するビットに誤りがあることが分かる。
【００６６】
符号化された座標値の誤りを検出する方法として、上述した以外に、次の方法も用いることができる。この方法は、連続した長さｐビットの部分系列間の最小ハミング距離は１以上であるが、ｎビット余分に取った長さ（ｐ＋ｎ）ビットの部分系列間の最小ハミング距離は２以上であるようなＭ系列符号を利用する。図１１にｐ＝５の部分系列の場合を示す。１ビットの誤りがあった場合、図１１（Ｂ）に示すように他の部分系列と一致することがあり、誤りを検出することができない。これに対し、図１１（Ｃ）に示すように２ビット余分に見て７ビットを見ると、１ビットの誤りで一致する部分系列は、このＭ系列符号には存在しない。このようにしてビット誤りを検出することができる。
【００６７】
例えば、Ｍ系列符号のｐ＝１０でｎが４の場合、（ｐ＋ｎ）部分系列のハミング距離が２以上となるＭ系列を生成する漸化式の係数には、以下の数２に示すものがある。
【００６８】
【数２】
【００６９】
このＭ系列の（１０＋４）部分系列のハミング距離は３であり、２つ以上の誤りを検出することができ、１つの誤りを訂正することができる。
【００７０】
図１２に誤り数と、その誤りの検出確率とを示す。この検出確率で、ビットエラー率が４％のとき、検出失敗が発生する確率は０．１２８％となる。ビットエラー率が３％のとき、検出失敗が発生する確率は、０．０５９％である。
【００７１】
またＭ系列符号のｐ＝１１でｎが５の場合、（ｐ＋ｎ）部分系列のハミング距離が２以上となるＭ系列を生成する漸化式の係数には、以下の数３に示すものがある。
【００７２】
【数３】
【００７３】
このＭ系列の（１１＋５）部分系列のハミング距離は３であり、２つ以上の誤りを検出することができ、１つの誤りを訂正することができる。
【００７４】
図１３に誤り数と、その誤りの検出確率とを示す。この検出確率で、ビットエラー率が４％のとき、検出失敗が発生する確率は０．０７８％となる。ビットエラー率が３％のとき、検出失敗が発生する確率は、０．０３７％である。
【００７５】
２次元座標同定装置２０の動作手順を図１４〜図１７に示すフローチャートを参照しながら説明する。まず、図１４を参照しながら全体の動作を説明する。
まず、ページと座標を同定すべき領域の画像を読み込む（ステップＳ１）。次に、読み込んだ画像からシンボルを検出し、ビット行列に変換する（ステップＳ２）。次に変換したビット行列をスキャンし同期符号のビット列を検出する（ステップＳ３）。検出した同期符号のビット列から画像を回転させる必要があるか否かを判定する（ステップＳ４）。回転の必要がある場合には（ステップＳ４／ＹＥＳ）、ビット行列を検出した回転角度とは逆に回転させる（ステップＳ５）。
【００７６】
次に、図１に示すように交差するＸ方向の同期符号のビット列と、Ｙ方向の同期符号のビット列で分割される４つの領域のビット行列を検出する（ステップＳ６）。次に、Ｘ座標を符号化するビット列を検出する（ステップＳ７）。Ｘ座標を符号化するビット列を検出すると、検出したビット列を用いてＸ座標の復号を行なう（ステップＳ８）。
【００７７】
次に、Ｙ座標を符号化するビット列を検出し（ステップＳ９）、検出したビット列からＹ座標の復号を行なう（ステップＳ１０）。
【００７８】
次に、識別番号を符号化するビット列を検出し（ステップＳ１１）、このビット列から識別番号を復号する（ステップＳ１２）。
【００７９】
以上の処理によって求められた識別番号、Ｘ座標値、Ｙ座標値をページ座標情報出力部４０から出力する。
【００８０】
次に、図１５に示すフローチャートを参照しながらＸ座標値を復号化する手順を説明する。
まず、Ｘ座標を符号化するビット列（以下、Ｘ座標符号化ビット列と呼ぶ）の左端又は右端のビットをＴＸ＝１に設定する（ステップＳ２０）。なお、ＴＸは、処理対象のビットを識別するパラメータである。次に、ＴＸ番目から（ＴＸ＋ＰＸ−１）番目までのビット列を取り出す（ステップＳ２１）。なおＰＸは、Ｘ座標を符号化するＭ系列符号の次数を表す。次に、ＴＸから（ＴＸ＋ＰＸ−１）までのビット列と、Ｍ系列符号の漸化式から（ＴＸ＋ＰＸ）の予測値ＱＸを求め（ステップＳ２２）、これを取り出した（ＴＸ＋ＰＸ）と比較する（ステップＳ２３）。両者が位置していない場合には（ステップＳ２３／ＮＯ）、全ビット列を訂正可能ビット列パターンと比較する（ステップＳ２９）。訂正可能ビット列パターンとは、誤ったパターンから正常なビット列を推定できるパターンである。検出したビット列と、訂正可能ビット列パターンとが一致している場合には（ステップＳ３０／ＹＥＳ）、訂正可能ビット列パターンによりビット列を訂正する（ステップＳ３１）。また訂正可能ビット列パターンと一致していない場合には（ステップＳ３０／ＮＯ）、Ｎ／Ａ（not applicable：適用不可）を代入する（ステップＳ３２）。
【００８１】
また、取り出した（ＴＸ＋ＰＸ）と、漸化式から求めたＱＸとが一致した場合には（ステップＳ２３／ＹＥＳ）、ＴＸがＮＸに一致しているか否かを判定する（ステップＳ２４）。ＮＸは、付加的読み込みビット数と呼び、ステップＳ２２、Ｓ２３の判定を行なうＴＸの範囲を示す。このＮＸが、図１０に示す対象となるビット列を前後にずらして、誤りがあるか否かを判定する範囲に該当する。図１０（Ｂ）に示すように対象となるビット列を前又は後ろに所定数ずらすことで、前回の検査で係数「０」に該当するビットに誤りがあるか否かを判定することができる。ＴＸがＮＸに一致していない場合には（ステップＳ２４／ＮＯ）、ＴＸの値を１インクリメントし（ステップＳ２５）ステップＳ２１からの処理手順を繰り返す。また、ＴＸとＮＸとが一致した場合には（ステップＳ２４／ＹＥＳ）、検出した全ビット列を誤りビット列パターンと比較する（ステップＳ２６）。誤りビット列パターンとは、Ｘ座標の符号化に使用したＭ系列符号の他の部分系列を指し、検出したビット列がＭ系列符号の他の部分系列と一致していると（ステップＳ２７／ＹＥＳ）、検出したビット列は誤りであると判定できる。
【００８２】
検出したビット列が誤りビット列パターンに一致していた場合には（ステップＳ２７／ＹＥＳ）、全ビット列を訂正可能ビット列パターンと比較する（ステップＳ２９）。この後、上述したように検出したビット列と、訂正可能ビット列パターンとが一致している場合には（ステップＳ３０／ＹＥＳ）、訂正可能ビット列パターンによりビット列を訂正する（ステップＳ３１）。また訂正可能ビット列パターンと一致していない場合には（ステップＳ３０／ＮＯ）、Ｎ／Ａ（not applicable：適用不可）を代入する。また、全ビット列と誤りビット列パターンとが一致していなかった場合（ステップＳ２７／ＮＯ）、またはステップＳ３１でビット列を訂正した場合には、ＴＸが１番目からＰＸ番目までのビット列からＸ座標を復号する（ステップＳ２８）。
【００８３】
なお、Ｙ座標の復号化は図１６に示すフローチャートに従って行なわれるが、Ｘ座標の復号化と同様であるため、詳細な説明は省略する。
【００８４】
次に、図１７に示すフローチャートを参照しながら識別番号の復号処理手順について説明する。
まず、図１に示すようにＸ座標を表す符号化ビット列と、Ｙ座標を表す符号化ビット列とで分割される４つの領域にまたがっているビット行列を並び替えて、識別番号を表すビット行列に復元する（ステップＳ６１）。次に、復元したビット行列をスキャンし、識別番号を表すビット列に変換する（ステップＳ６２）。次に、変換したビット列に誤りがあるか否かを検出する（ステップＳ６３）。誤りがあった場合には（ステップＳ６４／ＹＥＳ）、訂正可能な誤りか否かを判定する（ステップＳ６５）。訂正可能であった場合には（ステップＳ６６／ＹＥＳ）、誤りを訂正して（ステップＳ６７）、ページを復号する（ステップＳ６９）。また、訂正可能な誤りではなかった場合には（ステップＳ６６／ＮＯ）、識別番号にＮ／Ａを代入して（ステップＳ６８）、処理を終了する。また復元したビット列に誤りがなかった場合には（ステップＳ６４／ＮＯ）、識別番号を復号する（ステップＳ６９）。
【００８５】
このように本実施例は、ページ上の位置を示す座標値のコード情報と、ページの識別番号を示すコード情報とがそれぞれ記録された印刷物から所定範囲の画像を読み込んで、コード情報の検出、復号化を行なっているので、印刷物の識別番号と、印刷物上の座標との特定を精度よく行なうことができる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、ページ上の位置と、ページの識別番号を取り出すことができる。
【００８６】
なお、上述した印刷物は、図２１に示すようなテスト問題以外に、カレンダー、紙に印刷されたキーボード、申し込み書や申請書などへの適用が可能である。テスト問題を印刷した印刷物の場合には、印刷された問題に対する解答を、解答者が選択すると、選択された解答が通信回線で接続されたセンタに送られ、問題の点数が集計されたり、解答するためのアドバイスが解答者の端末に送信されたりする。また、カレンダーの場合、入力ペンで日付を選択すると、この日付の印刷された領域に記録された符号を２次元座標同定符号化装置によって読み取り、該当する日付のスケジュールを表示装置に表示させることもできる。
【００８７】
上述した実施例は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【図面の簡単な説明】
【００８８】
【図１】本発明の符号化方法を説明するための図である。
【図２】シンボルの構成を示す図である。
【図３】Ａ４長手方向の符号化例を示す図である。
【図４】読み込み範囲の一例を示す図である。
【図５】画像形成装置の構成を示す図である。
【図６】２次元座標同定装置の構成を示す図である。
【図７】パリティチェック符号について説明するための図である。
【図８】従来の誤り検査方法を説明するための図である。
【図９】本発明の誤り検査方法を説明するための図である。
【図１０】本発明の誤り検査方法を説明するための図である。
【図１１】本発明の誤り検査方法を説明するための図である。
【図１２】本発明の誤り検査方法での誤り検出確率を示す図である。
【図１３】本発明の誤り検査方法での誤り検出確率を示す図である。
【図１４】２次元座標同定装置の動作手順を示すフローチャートである。
【図１５】Ｘ座標の復号化の手順を示すフローチャートである。
【図１６】Ｙ座標の符号化の手順を示すフローチャートである。
【図１７】識別番号の復号化の手順を示すフローチャートである。
【図１８】２次元表面上の読み込み位置を同定する技術の利用例を示す図である。
【図１９】Ｍ系列符号について説明するための図である。
【図２０】従来の符号化方法を説明するための図である。
【図２１】従来技術の問題点を説明するための図である。
【符号の説明】
【００８９】
１ 画像形成装置 ２ ページ座標情報入力部
３ 識別番号符号化部 ４ Ｘ座標符号化部
５ Ｙ座標符号化部 ６ 識別番号符号パターン化部
７ 座標符号パターン化部 ８ 同期符号パターン化部
９ パターン合成部 １０ 画像合成部
１１ 文書画像生成部 １２ 画像生成部
２０ ２次元座標同定装置 ２１ 画像読み取り部
２２ パターン検出部 ２３ ビット情報変換部
２４ 同期符号検出部 ２５ 画像回転判定部
２６ ビット情報回転変換部 ２７ 識別番号符号化検出部
２８ 識別番号符号復元部 ２９ 識別番号符号復号部
３０ 識別番号符号誤り検出部 ３１ 識別番号符号誤り訂正部
３２ Ｘ座標符号検出部 ３３ Ｘ座標復号部
３４ Ｘ座標符号誤り検出部 ３５ Ｘ座標符号誤り訂正部
３６ Ｙ座標符号検出部 ３７ Ｙ座標復号部
３８ Ｙ座標符号誤り検出部 ３９ Ｙ座標符号誤り訂正部
４０ ページ座標情報出力部
【技術分野】
【０００１】
本発明は、２次元表面上に一様に配置されたシンボルの一部を読み込み、２次元表面上の読み込み位置を同定する技術に関する。
【背景技術】
【０００２】
近年、２次元表面上にシンボルを一様に配置し、シンボルを読み込むことで２次元表面上の位置を同定する技術が提案されている。例えば、紙等に印刷されたテスト問題上に、一様にシンボルを印刷しておき、解答者が、選択した解答位置をスキャナ等でなぞることで、選択された解答が通信事業者などに送られるといったシステムが提案されている（例えば、図１８参照）。
【０００３】
この２次元平面の符号化に、Ｍ系列の符号が使用されることが多い。Ｍ系列の符号は、「長さ２ｍ−１のＭ系列符号から、長さｍの部分系列を切り出したときに、いずれの２つの部分系列の並びも決して一致しない」という性質を持つ。この性質を利用して平面を符号化する技術が種々提案されている。
【０００４】
Ｍ系列符号は、以下に示すｐ次の漸化式から生成される系列のうちで周期が最大（２ｐ−１）のものをいう（疑似ランダム系列とも呼ばれる）。
【０００５】
【数１】
【０００６】
例えば、ｐ＝５、Ｃ１＝１，Ｃ２＝１，Ｃ３＝１，Ｃ４＝０，Ｃ５＝１の場合、図１９に示すＭ系列（長さ２５−１＝３１）が生成される。図１９に示すようにＭ系列の異なる位置から取り出した長さｐの部分系列Ａ，Ｂ，Ｃは、決して一致しない。この性質を利用して、平面上の座標を１ビットの精度で位置決めすることができる。
【０００７】
例えば、１ビットを０．３ｍｍのシンボルで表現すると、Ａ４長手方向の２９７ｍｍを表現するためには、以下に示すように１０次のＭ系列で符号化可能である。
（２１０−１）×０．３ｍｍ＝１０２３×０．３ｍｍ＝３０６．９ｍｍ
しかしながら、これではＡ４を１枚しか符号化できない。広大な面積を符号化しようとすると、もっと高次のＭ系列が必要になる。このため、平面上の位置を同定する時に、読み込む面積を大きくしなければならず、さらに、復号が複雑になるという問題が生じてしまう。
【０００８】
特許文献１では、座標位置を表すために、図２０に示すように平面上のＹ軸方向に平行に、同じＭ系列符号を配置している。Ｙ軸方向に平行に並べられたＭ系列符号は、Ｘ軸方向には適当に位相をずらして配置している。例えば、図２０では左から第２列目と第３列目では２ビットずらしており、第３列目と４列目では９ビットずらしており、第４列目と第５列目では２４ビットずらしており、第５列目と第６列目では１０ビットずらしている。これらの差は、同じＸ座標上の位置であれば一致する。これらの差をもとにＸ座標を表現する。Ｙ座標の表現についてもＸ軸の表現と同様に、Ｘ軸方向に平行に並べられたＭ系列符号を、Ｙ軸方向に適当に位相をずらして配置している。なお、ここでは、簡単のために同期方法を省略して説明した。
【０００９】
【特許文献１】特表２００３−５１１７６２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１では、Ａ４などの実用的な大きさで利用する場合に、紙面の端を特定するための工夫が必要となる。すなわち、図２１に示すように全符号化領域上での位置は同定できるが、利用面（ページ）の位置を同定するためには、図２１に示すように符号化領域上でのページの位置を獲得する必要がある。また、複数のＭ系列符号を区切るための工夫により、符号化の冗長度が大きくなるという欠点を有している。さらに符号化及び復号化のアルゴリズムが複雑で計算負荷が高くなるという欠点を有している。
【００１１】
本発明は上記事情に鑑みてなされたものであり、広大な面積の符号化が可能であると共に、位置検出精度を向上させた位置同定機能付き印刷物、２次元座標同定装置、画像形成装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の位置同定機能付き印刷物は、印刷物上の符号化領域を複数の符号化単位に分割し、前記符号化単位ごとに、前記印刷物上での位置を示す座標値のコード情報と、前記印刷物を識別する識別番号のコード情報とを記録した構成を備えている。このように本発明は、印刷物上での位置を示す座標値と、印刷物を識別する識別番号とを別々にコード化して記録しているので、広大な面積の符号化が可能となる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。さらに、各印刷物に、印刷物上の座標値を示すコード情報を記録しているので、位置検出精度を高めることができる。
【００１３】
上記位置同定機能付き印刷物において、前記座標値を表すコード情報は、Ｍ系列符号によって符号化されているとよい。座標値を表すコード情報が、Ｍ系列符号によって符号化されているので、印刷物上のどの位置を読み込んでも座標を特定することができる。
【００１４】
上記位置同定機能付き印刷物において、前記複数の符号化単位間は、同期符号によって区切られているとよい。印刷物上に記録された情報を読み込んだ時に、読み込み位置を簡単に特定することができる。
【００１５】
上記位置同定機能付き印刷物において、前記コード情報は、１つで多ビットを表現可能なシンボルで表現されているとよい。コード情報が、１つで多ビットを表現可能なシンボルで表現されているので、印刷物の表面に印刷するシンボル数を削減することができる。
【００１６】
上記位置同定機能付き印刷物において、前記コード情報及び前記同期符号は、シンボルによって表現され、前記同期符号を表すシンボルによって、前記コード情報を表すシンボルの向きを特定可能であるとよい。コード情報を表すシンボルの向きを特定し、正確に情報を取り出すことができる。
【００１７】
上記位置同定機能付き印刷物において、前記識別番号を示すコード情報は、前記符号化単位ごとに繰り返し記録されているとよい。識別番号が、符号化単位ごとに繰り返し記録されているので、どこを読み出しても再現し復号化可能となる。
【００１８】
上記位置同定機能付き印刷物において、符号化する印刷物のページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更するとよい。従って、印刷物のページ数が増えても、符号化することが可能となる。
【００１９】
上記位置同定機能付き印刷物において、前記符号化領域の大きさに応じて、前記座標値を表す前記コード情報のコード長を変更するとよい。従って、印刷物の大きさが変更になっても、符号化することができる。
【００２０】
本発明の２次元座標同定装置は、印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込む読込手段と、読み込まれた前記所定範囲の画像から前記識別番号と、前記符号化単位の位置を示す座標値とを示す前記コード情報を検出する検出手段と、前記コード情報を復号化し、前記識別番号と前記座標値とを出力する復号化手段とを有する構成としている。このように本発明は、印刷物上の位置を示す座標値のコード情報と、印刷物の識別番号を示すコード情報とがそれぞれ記録された印刷物から所定範囲の画像を読み込んで、コード情報の検出、復号化を行なっているので、印刷物の識別番号と、印刷物上の座標との特定を精度よく行なうことができる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。
【００２１】
上記２次元座標同定装置において、前記検出手段は、複数の前記符号化単位から前記コード情報を読み込んで、１つの前記識別情報を表す前記コード情報を検出するとよい。読み込み範囲が符号化単位に一致しなくても、複数の符号化単位からのコード情報によって１つの識別情報を表すコード情報として検出するので、画像の読み込み位置を意識する必要がなく、どの位置で読み込んでも精度よく識別番号と座標を得ることができる。
【００２２】
上記２次元座標同定装置において、前記コード情報は、１つで多ビットを表現可能なシンボルで表現され、前記複数の符号化単位間には、前記コード情報を表す前記シンボルの向きを特定可能なシンボルが形成されており、前記検出手段は、前記シンボルの向きを特定して前記コード情報を特定するとよい。シンボルの向きを特定し、正確に情報を取り出すことができる。
【００２３】
上記２次元座標同定装置において、前記座標値の前記コード情報と、その前又は後の所定ビットとから前記座標値の前記コード情報の誤りを検出する誤り検出手段を有するとよい。検出した座標値に誤りがあるか否かを判定することができる。
【００２４】
上記２次元座標同定装置において、前記座標値のコード情報は、Ｍ系列符号からなり、前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出する誤り検出手段を有するとよい。座標値の誤りを正確に検出することができる。
【００２５】
上記２次元座標同定装置において、前記検出した誤りが、その誤りから正しいビット列を推定することのできる誤りであった場合に、前記誤りを訂正する訂正手段を有するとよい。訂正できる誤りであった場合に、誤りを訂正して正しい座標値に復号することができる。
【００２６】
本発明の画像形成装置は、印刷物を識別する識別番号をコード化する識別番号コード化手段と、前記印刷物上の位置を示す座標値をコード化する座標値コード化手段と、前記識別番号と前記座標値とのコードに従って、前記識別番号と前記座標値とをシンボル化するシンボル化手段と、印刷画像と、前記シンボル化された前記識別番号と前記座標値とを合成する合成手段と、前記印刷物上の符号化領域を複数の符号化単位に分割し、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録し、前記コード情報上に前記印刷画像が形成された前記印刷物を形成する画像形成手段と、を有する構成としている。このように本発明は、印刷物上での位置を示す座標値と、印刷物を識別する識別番号とを別々にコード化して記録しているので、広大な面積の符号化が可能となる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。さらに、各印刷物に、印刷物上の座標値を示すコード情報を記録しているので、位置検出精度を高めることができる。
【００２７】
上記画像形成装置において、前記位置を示す座標値は、Ｍ系列符号によって符号化されているとよい。座標値を表すコード情報が、Ｍ系列符号によって符号化されているので、印刷物上のどの位置を読み込んでも座標を特定することができる。
【００２８】
上記画像形成装置において、前記識別番号コード化手段は、符号化するページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更するとよい。従って、印刷物のページ数が増えても、符号化することが可能となる。
【００２９】
上記画像形成装置において、前記座標値コード化手段は、前記符号化領域の面積に応じて、前記座標値を表す前記コード情報の大きさを変更するとよい。従って、印刷物の大きさが変更になっても、符号化することができる。
【００３０】
本発明の２次元座標同定方法は、印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込むステップと、読み込んだ前記所定範囲の画像から前記識別番号と、前記印刷ページ上の座標値とを示す前記コード情報を検出するステップと、前記コード情報を復号化し、前記識別番号と前記座標値とを出力するステップとを有している。このように本発明は、印刷物上の位置を示す座標値のコード情報と、印刷物の識別番号を示すコード情報とがそれぞれ記録された印刷物から所定範囲の画像を読み込んで、コード情報の検出、復号化を行なっているので、印刷物の識別番号と、印刷物上の座標との特定を精度よく行なうことができる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、印刷物上の位置と、印刷物の識別番号を取り出すことができる。
【００３１】
上記２次元座標同定方法において、前記座標値の前記コード情報と、その前又は後の所定ビットとから前記コード情報の誤りを検出するステップを有しているとよい。検出した座標値に誤りがあるか否かを判定することができる。
【００３２】
上記２次元座標同定方法において、前記座標値のコード情報は、Ｍ系列符号からなり、前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出するステップを有しているとよい。座標値の誤りを正確に検出することができる。
【発明の効果】
【００３３】
本発明は、広大な面積の符号化が可能であると共に、位置検出精度を向上させることができる。
【発明を実施するための最良の形態】
【００３４】
添付図面を参照しながら本発明の好適な実施例を説明する。
【実施例】
【００３５】
［位置同定機能付き印刷物］
まず、位置同定機能付き印刷物の構成について説明する。
本実施例では、符号化する全面積を、実用的な大きさの平面（例えば、Ａ３，Ａ４）に分割し、この平面を符号化領域とする。なお、以下では、説明の簡略化のため符号化領域をページと呼ぶ。各ページには、ページを識別する識別番号と、ページ上での位置を表す座標（Ｘ，Ｙ）を分けて符号化する。各ページは、図１に示すように複数の符号化単位に分割され、各符号化単位に所定の情報が記録される。１つの符号化単位は、縦６個、横７個の長方形で表される。長方形の１マスに１つのシンボルが形成される。シンボルとは、符号化されたコードをページ上に表示するためのものであり、例えば、図２（Ａ）に示すような非対称のシンボルや、図２（Ｂ）に示すような対称シンボルが用いられる。図２に示すシンボルは、所定角度回転させることによって１シンボルで４つの情報、すなわち２ビットを表すことができる。１つのシンボルは、例えば６００ｄｐｉで２ドット、シンボル間の間隔は０．３ｍｍで形成される。これ以外にも、利用する平面と利用方法に応じて、他の形状や、異なる大きさのシンボルが利用できる。符号化単位も、表現するページ数と面積とに応じて、より多くのあるいは少ないシンボル数で表現してもよい。
【００３６】
１つの符号化単位には、図１に示すように識別番号を表示するシンボルと、ページ上のＸ座標とＹ座標を表示するシンボルと、他の符号化領域との区切りを示すシンボル（以下、同期符号と呼ぶ）とが記録される。配置の一例として、図１に示すように符号化単位の左辺と底辺とに同期符号のシンボルを配置し、その内側のＹ方向にＹ座標を示すシンボルを５つと、同じく内側のＸ方向にＸ座標を示すシンボルを５つとを配置している。Ｘ座標、Ｙ座標を表示するシンボルの内側には、識別番号を表示するシンボルが２０配置される。
【００３７】
識別番号は、図１に示すように２０シンボルで表現される。１シンボルで２ビットの情報を表現することができるので、２０シンボルの場合、２４０＝１．１×１０１２、約１兆枚を符号化することができる。同じ用紙上の複数の符号化領域には、同じ識別番号を示すシンボルが書き込まれる。ここでは２０シンボルで説明しているが、表現するページ数に応じて、より多くのあるいは少ないシンボル数で表現してもよい。
【００３８】
Ｘ座標又はＹ座標は、Ｍ系列符号によって表現される。１符号化単位では、Ｘ座標，Ｙ座標ともに１０ビット（５シンボル）で表現され、Ｍ系列符号長は、２１０−１＝１０２３ビットである。ここでは５シンボルで説明しているが、表現する面積に応じて、より多くのあるいは少ないシンボル数で表現してもよい。
【００３９】
なお、１シンボルで２ビットを表す場合、１０２３ビットは５１１．５シンボルで表現され、図３に示すようにＡ４長手方向のサイズの半分にしかならない。しかしながら、周期が奇数であることから、次の周期では１ビットずれで表現される。このことから２周期でＡ４長手方向を符号化することができる。
【００４０】
符号化単位を区切る同期符号は、１シンボルの２ビット分のうちの１ビットで表現される。図１に示すように複数の符号化単位は、同期符号によって区切られている。同期符号を設けることによって、印刷物上に記録された情報を読み込んだ時に、読み込み位置を簡単に特定することができる。この同期符号は、例えば、全て「０」や「１」で揃える。これによって読み込んだ際に、連続する値を検出することで符号化単位の境界と認識することができる。残りの１ビットは、識別番号あるいは誤り検出符号に利用する。
【００４１】
また、この同期符号として書き込む値を予め決めておけば、その他の識別番号、Ｘ座標やＹ座標の値を示すシンボルの向きを判定することができる。例えば、同期符号として書き込んだ値が「１」で、ページ上をスキャンした時に得られた値が「２」であった場合、図２に示すようにページは９０度回転しているので、９０度逆方向に回転させることで、識別番号、Ｘ座標やＹ座標の値を示すシンボルを正しく読み取ることができる。
【００４２】
このように配置された紙面上を、予め設定された所定の大きさ（符号化単位の大きさ）で読み込むことで、図４に示すように読み込み範囲が複数の符号化単位にまたがっても、その他の符号化単位からの情報で識別番号、Ｘ座標やＹ座標の値を補完することができる。
【００４３】
［画像形成装置の構成］
このような印刷物を印刷する画像形成装置１の構成を図５に示す。図５に示す画像形成装置１は、ページ座標情報入力部２と、識別番号符号化部３と、Ｘ座標符号化部４と、Ｙ座標符号化部５と、識別番号符号パターン化部６と、座標符号パターン化部７と、同期符号パターン化部８と、パターン合成部９と、画像合成部１０と、文書画像生成部１１と、画像生成部１２とを備えている。
【００４４】
ページ座標情報入力部２は、印刷する用紙のサイズ及び印刷向きと、識別番号とを入力する。識別番号符号化部３は、入力した識別番号を符号化すると共に、符号化した識別番号を配置する位置情報を識別番号符号パターン化部６に出力する。符号化の方法は、特に限定しないが、本実施例では、ページ数の表示に４０ビットが使用できる。
【００４５】
Ｘ座標符号化部４は、入力した用紙サイズ及び印刷向きに従って、Ｘ方向の座標値データを書き込む位置を求める。次に、Ｘ方向の座標値をＭ系列符号によって符号化し、符号化データと位置情報とを座標符号パターン化部７に出力する。同様に、Ｙ座標符号化部５は、入力した用紙サイズ及び印刷向きに従って、Ｙ方向の座標データを書き込む位置を求める。Ｙ方向の座標値をＭ系列符号によって符号化し、符号化データと位置情報とを座標符号パターン化部７に出力する。
【００４６】
識別番号符号パターン化部６は、符号化された識別番号を、その符号を表すシンボルのパターンに変換し、位置情報に従って識別番号配置位置にシンボル化された識別番号を配置する。座標符号パターン化部７は、Ｍ系列符号によって符号化されたＸ座標とＹ座標とを、その符号を表すシンボルのパターンに変換し、位置情報に従って、座標値の配置位置に該当するシンボル化された座標値を配置する。
【００４７】
同期符号パターン化部８は、入力した用紙サイズに従って、同期符号の配置位置を求める。次に、同期符号をその符号を表すシンボルのパターンに変換し、位置情報に従って同期符号配置位置にシンボル化された同期符号を配置する。
【００４８】
パターン合成部９は、シンボル化された識別番号と、シンボル化された座標値と、シンボル化された同期符号とを重ね合わせ、一つのシンボルパターンを形成する。
【００４９】
文書画像生成部１１は、用紙に印刷する文書や画像を生成する。また、文書画像生成部１１は、パーソナルコンピュータ（以下、ＰＣと呼ぶ）等と接続し、このＰＣで作成した文書や画像を取り込むものであってもよい。さらに、スキャナ等によって読み込んだ文書や画像を取り込むものであってもよい。
【００５０】
画像合成部１０は、パターン合成部９で合成したシンボルパターンに、文書画像生成部１１から取得した文書や画像を重ね合わせ、一つの印刷画像を形成する。画像合成部１０で合成された印刷画像は、画像生成部１２から印刷出力される。
【００５１】
次に、図１に示す位置同定機能付き印刷物を読み込んで、印刷物上の位置を同定する２次元座標同定装置２０について説明する。図６に示す２次元座標同定装置２０は、画像読み取り部２１と、パターン検出部２２と、ビット情報変換部２３と、同期符号検出部２４と、画像回転判定部２５と、ビット情報回転変換部２６と、識別番号符号検出部２７と、識別番号符号復元部２８と、識別番号符号復号部２９と、識別番号符号誤り検出部３０と、識別番号符号誤り訂正部３１と、Ｘ座標符号検出部３２と、Ｘ座標復号部３３と、Ｘ座標符号誤り検出部３４と、Ｘ座標符号誤り訂正部３５と、Ｙ座標符号検出部３６と、Ｙ座標復号部３７と、Ｙ座標符号誤り検出部３８と、Ｙ座標符号誤り訂正部３９と、ページ座標情報出力部４０とを備えている。
【００５２】
画像読み取り部２１は、ページと座標を同定すべき領域の画像を読み込む。パターン検出部２２は、読み込んだ画像からシンボルを検出する。ビット情報変換部２３は、パターン検出部２２で検出されたシンボルをビット行列に変換する。同期符号検出部２４は、ビット行列をスキャンし、同期符号のビット列を検出する。画像回転判定部２５は、検出した同期符号のビット列から画像の回転を判定する。ビット情報回転変換部２６は、画像回転判定部２５によって判定された回転角度で画像を逆回転させ、画像の向きを正規の向きに変換する。
【００５３】
識別番号符号検出部２７は、図４に示すように同期符号のビット列で分けられた４つの領域から識別番号を示すシンボルを検出する。読み込み範囲が符号化単位に一致しない場合、図４に示すように同期符号のビット列で分けられた４つの領域から識別番号を示すシンボルが取り出される。
【００５４】
識別番号符号復元部２８は、最大４つの領域から取り出されたシンボルを並び替えたり、同一シンボルを削除したりして、１符号化単位に書き込まれた図１に示す識別番号のシンボル（Ｐ１１〜Ｐ１５，Ｐ２１〜Ｐ２５，Ｐ３１〜Ｐ３５，Ｐ４１〜Ｐ４５）に変換する（これを、ビット行列と呼ぶ）。また、ビット行列をスキャンして、識別番号を表す並びのビット列に変換する。
【００５５】
識別番号復号部２９は、識別番号符号を復号する。識別番号符号誤り検出部３０は、識別番号を表す並びのビット列に、ノイズ等によって誤りが生じているか否かを判定する。識別番号符号誤り訂正部３１は、識別番号を表す並びのビット列に誤りがあると判定されると、その誤りを訂正する。
【００５６】
識別番号を表す符号の誤り検出には、パリティチェック符号などが用いられる。パリティチェック符号は、図７（Ａ）に示すように情報符号の和が偶数の場合には「０」を、情報符号の和が奇数の場合には「１」をチェック符号としておくものであり、図７（Ｂ）に示すように識別番号の符号の行方向のチェック符号と、列方向のチェック符号とを配置する。パリティチェック符号は、上述した同期符号の残り１ビットに含ませても良い。また誤り検出には、同一の最小ハミング距離を持つ線形符号の中で検査記号数が最小となるＲＳ符号（リードソロモン）を用いることもできる。例えば、４０ビットで符号化する場合、ブロックビット長を４ビットとし、符号ブロック数を１０、情報ブロック数を６としたＲＳ（１０，６）符号を使用すると、符号化効率は０．６程度となり、約６０００万枚を符号化できる。この符号化は、２ブロックまでの訂正が可能である。さらに、これ以外の誤り訂正方式も利用可能である。
【００５７】
Ｘ座標符号検出部３２は、Ｘ座標の座標値を表すシンボルを検出し、符号化されたＸ座標を表すビット列に変換する。Ｘ座標復号部３３は、符号化されたＸ座標を表すビット列を復号し、Ｘ座標を求める。なお、復号部３３の詳細な動作については後述する。
【００５８】
Ｘ座標符号誤り検出部３４は、符号化されたＸ座標を表すビット列に誤りが含まれているかを検出する。Ｘ座標符号誤り訂正部３５は、誤りを検出し、その誤りが訂正可能な誤りであった場合に、誤りを訂正する。これらの機能部の詳細な動作についても後述する。
【００５９】
Ｙ座標符号検出部３６は、Ｙ座標の座標値を表すシンボルを検出し、符号化されたＹ座標を表すビット列に変換する。Ｙ座標復号部３７は、符号化されたＹ座標を表すビット列を復号し、Ｙ座標を求める。復号部３７の詳細な動作についても後述する。
【００６０】
Ｙ座標符号誤り検出部３８は、符号化されたＹ座標を表すビット列に誤りが含まれているかを検出する。Ｙ座標符号誤り訂正部３９は、誤りを検出し、その誤りが訂正可能な誤りであった場合に、誤りを訂正する。これらの機能部の詳細な動作についても後述する。
【００６１】
ページ座標情報出力部４０は、復号された識別番号、Ｘ方向座標値、Ｙ軸方向座標値を出力する。
【００６２】
ここで、符号化された座標値の誤りを検出する方法について説明する。
従来、符号化されたビット列の誤りを検出するために、図８に示すようにパリティチェックビットが付加されている。パリティチェックビットは、図８（Ａ）に示すように各部分系列ごとに配置する方法と、図８（Ｂ）に示すように次数間隔ごとにパリティチェックビットを配置する方法とがある。図８（Ａ）に示すように各部分系列ごとに配置する場合、位置決め精度を１ビットにできるが、情報と同じ数のチェックビットとなるため冗長度が大きすぎるという問題が生じる。また、図８（Ｂ）に示す次数間隔ごとにチェックビットを配置する方法では、冗長度は小さいが、検査のために２倍の長さの読み込みが必要となる。
【００６３】
そこで、本実施例ではＭ系列符号の特性を利用した誤り検出を行なっている。ページ上の位置を表示するＸ、Ｙの座標値には、Ｍ系列符号を使用している。上述したようにＭ系列符号は、数１に示す漸化式を使用して算出される。このため、（ｐ＋１）の部分系列は、Ｍ系列符号を生成した漸化式を利用して、矛盾がないかを判定することができる。例えば、図９に示すように任意に取り出した５ビットに、Ｃ１〜Ｃ５の係数を掛け合わせて生成した符号と、取り出した５ビットの次のビットとが一致しているか否かを判定することで、符号の誤りを検出することができる。図９（Ａ）に誤りがなかった場合を示し、図９（Ｂ）に誤りがあった場合を示す。
【００６４】
しかしながら、図１０（Ａ）に示すように係数Ｃ１〜Ｃ５に「０」が含まれていると、「０」の位置の符号を検査することができない。そのため、係数に含まれる「０」の個数と、取り出した部分系列に含まれる「０」の数が一致してしまうと、誤りを検出することができない。
【００６５】
そこで、本実施例は、検査対象となるビット列の誤り検出を行なうと共に、図１０（Ｂ）に示すように対象となるビット列を前後にずらして、誤りがあるか否かを判定している。例えば、図１０（Ｂ）に示すように対象となるビット列を前に１ビットずらすことで、誤りがあった場合、前回の検査で係数「０」に該当するビットに誤りがあることが分かる。
【００６６】
符号化された座標値の誤りを検出する方法として、上述した以外に、次の方法も用いることができる。この方法は、連続した長さｐビットの部分系列間の最小ハミング距離は１以上であるが、ｎビット余分に取った長さ（ｐ＋ｎ）ビットの部分系列間の最小ハミング距離は２以上であるようなＭ系列符号を利用する。図１１にｐ＝５の部分系列の場合を示す。１ビットの誤りがあった場合、図１１（Ｂ）に示すように他の部分系列と一致することがあり、誤りを検出することができない。これに対し、図１１（Ｃ）に示すように２ビット余分に見て７ビットを見ると、１ビットの誤りで一致する部分系列は、このＭ系列符号には存在しない。このようにしてビット誤りを検出することができる。
【００６７】
例えば、Ｍ系列符号のｐ＝１０でｎが４の場合、（ｐ＋ｎ）部分系列のハミング距離が２以上となるＭ系列を生成する漸化式の係数には、以下の数２に示すものがある。
【００６８】
【数２】
【００６９】
このＭ系列の（１０＋４）部分系列のハミング距離は３であり、２つ以上の誤りを検出することができ、１つの誤りを訂正することができる。
【００７０】
図１２に誤り数と、その誤りの検出確率とを示す。この検出確率で、ビットエラー率が４％のとき、検出失敗が発生する確率は０．１２８％となる。ビットエラー率が３％のとき、検出失敗が発生する確率は、０．０５９％である。
【００７１】
またＭ系列符号のｐ＝１１でｎが５の場合、（ｐ＋ｎ）部分系列のハミング距離が２以上となるＭ系列を生成する漸化式の係数には、以下の数３に示すものがある。
【００７２】
【数３】
【００７３】
このＭ系列の（１１＋５）部分系列のハミング距離は３であり、２つ以上の誤りを検出することができ、１つの誤りを訂正することができる。
【００７４】
図１３に誤り数と、その誤りの検出確率とを示す。この検出確率で、ビットエラー率が４％のとき、検出失敗が発生する確率は０．０７８％となる。ビットエラー率が３％のとき、検出失敗が発生する確率は、０．０３７％である。
【００７５】
２次元座標同定装置２０の動作手順を図１４〜図１７に示すフローチャートを参照しながら説明する。まず、図１４を参照しながら全体の動作を説明する。
まず、ページと座標を同定すべき領域の画像を読み込む（ステップＳ１）。次に、読み込んだ画像からシンボルを検出し、ビット行列に変換する（ステップＳ２）。次に変換したビット行列をスキャンし同期符号のビット列を検出する（ステップＳ３）。検出した同期符号のビット列から画像を回転させる必要があるか否かを判定する（ステップＳ４）。回転の必要がある場合には（ステップＳ４／ＹＥＳ）、ビット行列を検出した回転角度とは逆に回転させる（ステップＳ５）。
【００７６】
次に、図１に示すように交差するＸ方向の同期符号のビット列と、Ｙ方向の同期符号のビット列で分割される４つの領域のビット行列を検出する（ステップＳ６）。次に、Ｘ座標を符号化するビット列を検出する（ステップＳ７）。Ｘ座標を符号化するビット列を検出すると、検出したビット列を用いてＸ座標の復号を行なう（ステップＳ８）。
【００７７】
次に、Ｙ座標を符号化するビット列を検出し（ステップＳ９）、検出したビット列からＹ座標の復号を行なう（ステップＳ１０）。
【００７８】
次に、識別番号を符号化するビット列を検出し（ステップＳ１１）、このビット列から識別番号を復号する（ステップＳ１２）。
【００７９】
以上の処理によって求められた識別番号、Ｘ座標値、Ｙ座標値をページ座標情報出力部４０から出力する。
【００８０】
次に、図１５に示すフローチャートを参照しながらＸ座標値を復号化する手順を説明する。
まず、Ｘ座標を符号化するビット列（以下、Ｘ座標符号化ビット列と呼ぶ）の左端又は右端のビットをＴＸ＝１に設定する（ステップＳ２０）。なお、ＴＸは、処理対象のビットを識別するパラメータである。次に、ＴＸ番目から（ＴＸ＋ＰＸ−１）番目までのビット列を取り出す（ステップＳ２１）。なおＰＸは、Ｘ座標を符号化するＭ系列符号の次数を表す。次に、ＴＸから（ＴＸ＋ＰＸ−１）までのビット列と、Ｍ系列符号の漸化式から（ＴＸ＋ＰＸ）の予測値ＱＸを求め（ステップＳ２２）、これを取り出した（ＴＸ＋ＰＸ）と比較する（ステップＳ２３）。両者が位置していない場合には（ステップＳ２３／ＮＯ）、全ビット列を訂正可能ビット列パターンと比較する（ステップＳ２９）。訂正可能ビット列パターンとは、誤ったパターンから正常なビット列を推定できるパターンである。検出したビット列と、訂正可能ビット列パターンとが一致している場合には（ステップＳ３０／ＹＥＳ）、訂正可能ビット列パターンによりビット列を訂正する（ステップＳ３１）。また訂正可能ビット列パターンと一致していない場合には（ステップＳ３０／ＮＯ）、Ｎ／Ａ（not applicable：適用不可）を代入する（ステップＳ３２）。
【００８１】
また、取り出した（ＴＸ＋ＰＸ）と、漸化式から求めたＱＸとが一致した場合には（ステップＳ２３／ＹＥＳ）、ＴＸがＮＸに一致しているか否かを判定する（ステップＳ２４）。ＮＸは、付加的読み込みビット数と呼び、ステップＳ２２、Ｓ２３の判定を行なうＴＸの範囲を示す。このＮＸが、図１０に示す対象となるビット列を前後にずらして、誤りがあるか否かを判定する範囲に該当する。図１０（Ｂ）に示すように対象となるビット列を前又は後ろに所定数ずらすことで、前回の検査で係数「０」に該当するビットに誤りがあるか否かを判定することができる。ＴＸがＮＸに一致していない場合には（ステップＳ２４／ＮＯ）、ＴＸの値を１インクリメントし（ステップＳ２５）ステップＳ２１からの処理手順を繰り返す。また、ＴＸとＮＸとが一致した場合には（ステップＳ２４／ＹＥＳ）、検出した全ビット列を誤りビット列パターンと比較する（ステップＳ２６）。誤りビット列パターンとは、Ｘ座標の符号化に使用したＭ系列符号の他の部分系列を指し、検出したビット列がＭ系列符号の他の部分系列と一致していると（ステップＳ２７／ＹＥＳ）、検出したビット列は誤りであると判定できる。
【００８２】
検出したビット列が誤りビット列パターンに一致していた場合には（ステップＳ２７／ＹＥＳ）、全ビット列を訂正可能ビット列パターンと比較する（ステップＳ２９）。この後、上述したように検出したビット列と、訂正可能ビット列パターンとが一致している場合には（ステップＳ３０／ＹＥＳ）、訂正可能ビット列パターンによりビット列を訂正する（ステップＳ３１）。また訂正可能ビット列パターンと一致していない場合には（ステップＳ３０／ＮＯ）、Ｎ／Ａ（not applicable：適用不可）を代入する。また、全ビット列と誤りビット列パターンとが一致していなかった場合（ステップＳ２７／ＮＯ）、またはステップＳ３１でビット列を訂正した場合には、ＴＸが１番目からＰＸ番目までのビット列からＸ座標を復号する（ステップＳ２８）。
【００８３】
なお、Ｙ座標の復号化は図１６に示すフローチャートに従って行なわれるが、Ｘ座標の復号化と同様であるため、詳細な説明は省略する。
【００８４】
次に、図１７に示すフローチャートを参照しながら識別番号の復号処理手順について説明する。
まず、図１に示すようにＸ座標を表す符号化ビット列と、Ｙ座標を表す符号化ビット列とで分割される４つの領域にまたがっているビット行列を並び替えて、識別番号を表すビット行列に復元する（ステップＳ６１）。次に、復元したビット行列をスキャンし、識別番号を表すビット列に変換する（ステップＳ６２）。次に、変換したビット列に誤りがあるか否かを検出する（ステップＳ６３）。誤りがあった場合には（ステップＳ６４／ＹＥＳ）、訂正可能な誤りか否かを判定する（ステップＳ６５）。訂正可能であった場合には（ステップＳ６６／ＹＥＳ）、誤りを訂正して（ステップＳ６７）、ページを復号する（ステップＳ６９）。また、訂正可能な誤りではなかった場合には（ステップＳ６６／ＮＯ）、識別番号にＮ／Ａを代入して（ステップＳ６８）、処理を終了する。また復元したビット列に誤りがなかった場合には（ステップＳ６４／ＮＯ）、識別番号を復号する（ステップＳ６９）。
【００８５】
このように本実施例は、ページ上の位置を示す座標値のコード情報と、ページの識別番号を示すコード情報とがそれぞれ記録された印刷物から所定範囲の画像を読み込んで、コード情報の検出、復号化を行なっているので、印刷物の識別番号と、印刷物上の座標との特定を精度よく行なうことができる。また符号化単位ごとに座標値と識別番号とが記録されているので、符号化単位を読み出すだけで、ページ上の位置と、ページの識別番号を取り出すことができる。
【００８６】
なお、上述した印刷物は、図２１に示すようなテスト問題以外に、カレンダー、紙に印刷されたキーボード、申し込み書や申請書などへの適用が可能である。テスト問題を印刷した印刷物の場合には、印刷された問題に対する解答を、解答者が選択すると、選択された解答が通信回線で接続されたセンタに送られ、問題の点数が集計されたり、解答するためのアドバイスが解答者の端末に送信されたりする。また、カレンダーの場合、入力ペンで日付を選択すると、この日付の印刷された領域に記録された符号を２次元座標同定符号化装置によって読み取り、該当する日付のスケジュールを表示装置に表示させることもできる。
【００８７】
上述した実施例は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【図面の簡単な説明】
【００８８】
【図１】本発明の符号化方法を説明するための図である。
【図２】シンボルの構成を示す図である。
【図３】Ａ４長手方向の符号化例を示す図である。
【図４】読み込み範囲の一例を示す図である。
【図５】画像形成装置の構成を示す図である。
【図６】２次元座標同定装置の構成を示す図である。
【図７】パリティチェック符号について説明するための図である。
【図８】従来の誤り検査方法を説明するための図である。
【図９】本発明の誤り検査方法を説明するための図である。
【図１０】本発明の誤り検査方法を説明するための図である。
【図１１】本発明の誤り検査方法を説明するための図である。
【図１２】本発明の誤り検査方法での誤り検出確率を示す図である。
【図１３】本発明の誤り検査方法での誤り検出確率を示す図である。
【図１４】２次元座標同定装置の動作手順を示すフローチャートである。
【図１５】Ｘ座標の復号化の手順を示すフローチャートである。
【図１６】Ｙ座標の符号化の手順を示すフローチャートである。
【図１７】識別番号の復号化の手順を示すフローチャートである。
【図１８】２次元表面上の読み込み位置を同定する技術の利用例を示す図である。
【図１９】Ｍ系列符号について説明するための図である。
【図２０】従来の符号化方法を説明するための図である。
【図２１】従来技術の問題点を説明するための図である。
【符号の説明】
【００８９】
１ 画像形成装置 ２ ページ座標情報入力部
３ 識別番号符号化部 ４ Ｘ座標符号化部
５ Ｙ座標符号化部 ６ 識別番号符号パターン化部
７ 座標符号パターン化部 ８ 同期符号パターン化部
９ パターン合成部 １０ 画像合成部
１１ 文書画像生成部 １２ 画像生成部
２０ ２次元座標同定装置 ２１ 画像読み取り部
２２ パターン検出部 ２３ ビット情報変換部
２４ 同期符号検出部 ２５ 画像回転判定部
２６ ビット情報回転変換部 ２７ 識別番号符号化検出部
２８ 識別番号符号復元部 ２９ 識別番号符号復号部
３０ 識別番号符号誤り検出部 ３１ 識別番号符号誤り訂正部
３２ Ｘ座標符号検出部 ３３ Ｘ座標復号部
３４ Ｘ座標符号誤り検出部 ３５ Ｘ座標符号誤り訂正部
３６ Ｙ座標符号検出部 ３７ Ｙ座標復号部
３８ Ｙ座標符号誤り検出部 ３９ Ｙ座標符号誤り訂正部
４０ ページ座標情報出力部
【特許請求の範囲】
【請求項１】
印刷物上の符号化領域を複数の符号化単位に分割し、前記符号化単位ごとに、前記印刷物上での位置を示す座標値のコード情報と、前記印刷物を識別する識別番号のコード情報とを記録したことを特徴とする位置同定機能付き印刷物。
【請求項２】
前記座標値を表すコード情報は、Ｍ系列符号によって符号化されていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項３】
前記複数の符号化単位間は、同期符号によって区切られていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項４】
前記コード情報は、１つで多ビットを表現可能なシンボルで表現されていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項５】
前記コード情報及び前記同期符号は、シンボルによって表現され、前記同期符号を表すシンボルによって、前記コード情報を表すシンボルの向きを特定可能であることを特徴とする請求項３記載の位置同定機能付き印刷物。
【請求項６】
前記識別番号を示すコード情報は、前記符号化単位ごとに繰り返し記録されていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項７】
符号化する印刷物のページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更することを特徴とする請求項１から６のいずれか１項記載の位置同定機能付き印刷物。
【請求項８】
前記符号化領域の大きさに応じて、前記座標値を表す前記コード情報のコード長を変更することを特徴とする請求項１から７のいずれか１項記載の位置同定機能付き印刷物。
【請求項９】
印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込む読込手段と、
読み込まれた前記所定範囲の画像から前記識別番号と、前記符号化単位の位置を示す座標値とを示す前記コード情報を検出する検出手段と、
前記コード情報を復号化し、前記識別番号と前記座標値とを出力する復号化手段とを有することを特徴とする２次元座標同定装置。
【請求項１０】
前記検出手段は、複数の前記符号化単位から前記コード情報を読み込んで、１つの前記識別情報を表す前記コード情報を検出することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１１】
前記コード情報は、１つで多ビットを表現可能なシンボルで表現され、前記複数の符号化単位間には、前記コード情報を表す前記シンボルの向きを特定可能なシンボルが形成されており、
前記検出手段は、前記シンボルの向きを特定して前記コード情報を特定することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１２】
前記座標値の前記コード情報と、その前又は後の所定ビットとから前記座標値の前記コード情報の誤りを検出する誤り検出手段を有することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１３】
前記座標値のコード情報は、Ｍ系列符号からなり、
前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出する誤り検出手段を有することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１４】
前記検出した誤りが、その誤りから正しいビット列を推定することのできる誤りであった場合に、前記誤りを訂正する訂正手段を有することを特徴とする請求項１２又は１３記載の２次元座標同定装置。
【請求項１５】
印刷物を識別する識別番号をコード化する識別番号コード化手段と、
前記印刷物上の位置を示す座標値をコード化する座標値コード化手段と、
前記識別番号と前記座標値とのコードに従って、前記識別番号と前記座標値とをシンボル化するシンボル化手段と、
印刷画像と、前記シンボル化された前記識別番号と前記座標値とを合成する合成手段と、
前記印刷物上の符号化領域を複数の符号化単位に分割し、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録し、前記コード情報上に前記印刷画像が形成された前記印刷物を形成する画像形成手段と、を有することを特徴とする画像形成装置。
【請求項１６】
前記位置を示す座標値は、Ｍ系列符号によって符号化されていることを特徴とする請求項１５記載の画像形成装置。
【請求項１７】
前記識別番号コード化手段は、符号化するページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更することを特徴とする請求項１５又は１６記載の画像形成装置。
【請求項１８】
前記座標値コード化手段は、前記符号化領域の面積に応じて、前記座標値を表す前記コード情報の大きさを変更することを特徴とする請求項１５から１７のいずれか１項記載の画像形成装置。
【請求項１９】
印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込むステップと、
読み込んだ前記所定範囲の画像から前記識別番号と、前記印刷ページ上の座標値とを示す前記コード情報を検出するステップと、
前記コード情報を復号化し、前記識別番号と前記座標値とを出力するステップとを有することを特徴とする２次元座標同定方法。
【請求項２０】
前記座標値の前記コード情報と、その前又は後の所定ビットとから前記コード情報の誤りを検出するステップを有することを特徴とする請求項１９記載の２次元座標同定方法。
【請求項２１】
前記座標値のコード情報は、Ｍ系列符号からなり、
前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出するステップを有することを特徴とする請求項１９記載の２次元座標同定方法。
【請求項１】
印刷物上の符号化領域を複数の符号化単位に分割し、前記符号化単位ごとに、前記印刷物上での位置を示す座標値のコード情報と、前記印刷物を識別する識別番号のコード情報とを記録したことを特徴とする位置同定機能付き印刷物。
【請求項２】
前記座標値を表すコード情報は、Ｍ系列符号によって符号化されていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項３】
前記複数の符号化単位間は、同期符号によって区切られていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項４】
前記コード情報は、１つで多ビットを表現可能なシンボルで表現されていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項５】
前記コード情報及び前記同期符号は、シンボルによって表現され、前記同期符号を表すシンボルによって、前記コード情報を表すシンボルの向きを特定可能であることを特徴とする請求項３記載の位置同定機能付き印刷物。
【請求項６】
前記識別番号を示すコード情報は、前記符号化単位ごとに繰り返し記録されていることを特徴とする請求項１記載の位置同定機能付き印刷物。
【請求項７】
符号化する印刷物のページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更することを特徴とする請求項１から６のいずれか１項記載の位置同定機能付き印刷物。
【請求項８】
前記符号化領域の大きさに応じて、前記座標値を表す前記コード情報のコード長を変更することを特徴とする請求項１から７のいずれか１項記載の位置同定機能付き印刷物。
【請求項９】
印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込む読込手段と、
読み込まれた前記所定範囲の画像から前記識別番号と、前記符号化単位の位置を示す座標値とを示す前記コード情報を検出する検出手段と、
前記コード情報を復号化し、前記識別番号と前記座標値とを出力する復号化手段とを有することを特徴とする２次元座標同定装置。
【請求項１０】
前記検出手段は、複数の前記符号化単位から前記コード情報を読み込んで、１つの前記識別情報を表す前記コード情報を検出することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１１】
前記コード情報は、１つで多ビットを表現可能なシンボルで表現され、前記複数の符号化単位間には、前記コード情報を表す前記シンボルの向きを特定可能なシンボルが形成されており、
前記検出手段は、前記シンボルの向きを特定して前記コード情報を特定することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１２】
前記座標値の前記コード情報と、その前又は後の所定ビットとから前記座標値の前記コード情報の誤りを検出する誤り検出手段を有することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１３】
前記座標値のコード情報は、Ｍ系列符号からなり、
前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出する誤り検出手段を有することを特徴とする請求項９記載の２次元座標同定装置。
【請求項１４】
前記検出した誤りが、その誤りから正しいビット列を推定することのできる誤りであった場合に、前記誤りを訂正する訂正手段を有することを特徴とする請求項１２又は１３記載の２次元座標同定装置。
【請求項１５】
印刷物を識別する識別番号をコード化する識別番号コード化手段と、
前記印刷物上の位置を示す座標値をコード化する座標値コード化手段と、
前記識別番号と前記座標値とのコードに従って、前記識別番号と前記座標値とをシンボル化するシンボル化手段と、
印刷画像と、前記シンボル化された前記識別番号と前記座標値とを合成する合成手段と、
前記印刷物上の符号化領域を複数の符号化単位に分割し、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録し、前記コード情報上に前記印刷画像が形成された前記印刷物を形成する画像形成手段と、を有することを特徴とする画像形成装置。
【請求項１６】
前記位置を示す座標値は、Ｍ系列符号によって符号化されていることを特徴とする請求項１５記載の画像形成装置。
【請求項１７】
前記識別番号コード化手段は、符号化するページ数に応じて、前記識別番号を表す前記コード情報の大きさを変更することを特徴とする請求項１５又は１６記載の画像形成装置。
【請求項１８】
前記座標値コード化手段は、前記符号化領域の面積に応じて、前記座標値を表す前記コード情報の大きさを変更することを特徴とする請求項１５から１７のいずれか１項記載の画像形成装置。
【請求項１９】
印刷物上の符号化領域が複数の符号化単位に分割され、該符号化単位ごとに、前記印刷物上での位置を示す座標値と、前記印刷物を識別する識別番号とを示すコード情報をそれぞれ記録した前記印刷物の所定範囲の画像を読み込むステップと、
読み込んだ前記所定範囲の画像から前記識別番号と、前記印刷ページ上の座標値とを示す前記コード情報を検出するステップと、
前記コード情報を復号化し、前記識別番号と前記座標値とを出力するステップとを有することを特徴とする２次元座標同定方法。
【請求項２０】
前記座標値の前記コード情報と、その前又は後の所定ビットとから前記コード情報の誤りを検出するステップを有することを特徴とする請求項１９記載の２次元座標同定方法。
【請求項２１】
前記座標値のコード情報は、Ｍ系列符号からなり、
前記座標値を示す、前記Ｍ系列符号の一部からなる部分系列が、他の部分系列と一致しているか否かを判定して前記コード情報の誤りを検出するステップを有することを特徴とする請求項１９記載の２次元座標同定方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２００６−２４３８１８（Ｐ２００６−２４３８１８Ａ）
【公開日】平成１８年９月１４日（２００６．９．１４）
【国際特許分類】
【出願番号】特願２００５−５４７１３（Ｐ２００５−５４７１３）
【出願日】平成１７年２月２８日（２００５．２．２８）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成１８年９月１４日（２００６．９．１４）
【国際特許分類】
【出願日】平成１７年２月２８日（２００５．２．２８）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]