JP5233839B2 - 情報抽出装置、情報抽出方法、情報抽出プログラム、及び記憶媒体 - Google Patents

Description

本発明は、情報抽出装置、情報抽出方法、情報抽出プログラム、及び記憶媒体に関する。

従来から、文書画像などの画像データを印刷する際に、印刷対象の画像データとは別に何らかの情報を埋め込む情報埋込技術が知られており、このような情報埋込技術の１つに、ドットパターンを用いるものがある。

ドットパターンを用いる方式には、例えば、情報の最小単位であるドットパターンを印刷物の背景に格子状に印刷することで任意の情報を埋め込み、埋め込まれた情報を抽出する場合には、この印刷物をスキャナ等で読み取り、読み取られた読取画像の中からドットパターン一つひとつを識別して情報を復元するものがある（例えば、特許文献１参照）。

このような方式においてドットパターンを識別するためには、まずドットパターンの位置を特定する必要があり、特許文献１に開示されているように、水平方向のドットパターンの並び及び垂直方向のドットパターンの並びをそれぞれ直線に近似し、近似した直線間の交点を算出する手法がある。

また、特許文献１に開示されているように、スキャナ等のメカ的な要因で読取画像に生じる歪みを考慮して、水平方向のドットパターンの並び及び垂直方向のドットパターンの並びをそれぞれ区分直線或いは曲線に近似し、近似した区分直線或いは曲線間の交点を算出する手法もある。

そして、曲線間の交点を算出する手法には、例えば特許文献２に記載の方法がある。

しかしながら、ドットパターンの並びを曲線に近似し、特許文献２に記載されたような手法で曲線間の交点を算出すると、直線間の交点を算出する場合に比べ処理負荷が大きくなり、情報の抽出に時間がかかってしまう可能性がある。

また、ドットパターンの並びの近似は、通常、検索用のドットパターンとのテンプレートマッチングにより探索された一部のドットパターンを用いて行われる。このため、ドットパターンの並びを曲線に近似する場合、探索されたドットパターンの間隔が大きくなるほど、実際のドットパターンの並びと近似された曲線との間の誤差が大きくなってしまう。

本発明は、上記事情に鑑みてなされたものであり、パターンの並びが歪んだ場合であっても、パターン一つひとつの位置を簡易かつ正確に特定して、埋め込まれた情報を抽出することができる情報抽出装置、情報抽出方法、情報抽出プログラム、及び記憶媒体を提供することを目的とする。

上述した課題を解決し、目的を達成するために、本発明の一態様にかかる情報抽出装置は、複数種別のパターンを格子状に印刷することで情報が埋め込まれた印刷物の画像データを取得する取得手段と、前記画像データの中の略垂直方向のパターン列を線分で結んだ略垂直線分列を複数算出するとともに、前記画像データの中の略水平方向のパターン列を線分で結んだ略水平線分列を複数算出する線分列算出手段と、前記略垂直線分列と前記略水平線分列との組み合わせ毎に、当該略垂直線分列を構成する略垂直線分及び当該略水平線分列を構成する略水平線分の中から、互いに交差する略垂直線分及び略水平線分を探索する探索手段と、探索された前記略垂直線分と前記略水平線分との交点をパターンの位置として算出する交点算出手段と、算出された位置のパターンの種別を識別し、前記印刷物に埋め込まれた情報を抽出する抽出手段と、を備えることを特徴とする。

また、本発明の別の態様にかかる情報抽出方法は、取得手段が、複数種別のパターンを格子状に印刷することで情報が埋め込まれた印刷物の画像データを取得する取得ステップと、線分列算出手段が、前記画像データの中の略垂直方向のパターン列を線分で結んだ略垂直線分列を複数算出するとともに、前記画像データの中の略水平方向のパターン列を線分で結んだ略水平線分列を複数算出する線分列算出ステップと、探索手段が、前記略垂直線分列と前記略水平線分列との組み合わせ毎に、当該略垂直線分列を構成する略垂直線分及び当該略水平線分列を構成する略水平線分の中から、互いに交差する略垂直線分及び略水平線分を探索する探索ステップと、交点算出手段が、探索された前記略垂直線分と前記略水平線分との交点をパターンの位置として算出する交点算出ステップと、抽出手段が、算出された位置のパターンの種別を識別し、前記印刷物に埋め込まれた情報を抽出する抽出ステップと、を含むことを特徴とする。

また、本発明の別の態様にかかる情報抽出プログラムは、上記情報抽出方法をコンピュータに実行させるためのものである。

また、本発明の別の態様にかかるコンピュータ読み取り可能な記憶媒体は、上記情報抽出プログラムを記憶したものである。

本発明によれば、パターンの並びが歪んだ場合であっても、パターン一つひとつの位置を簡易かつ正確に特定して、埋め込まれた情報を抽出することができるという効果を奏する。

図１は、第１実施形態の複合機の構成例を示すブロック図である。 図２は、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物の一例を示す図である。 図３は、略垂直線分列及び略水平線分列の算出手法例の説明図である。 図４は、略垂直線分列及び略水平線分列の算出手法例の説明図である。 図５は、略垂直線分及び略水平線分の交差性の判定手法例の説明図である。 図６は、略垂直線分と略水平線分とが交差するか否かの判定条件例を示す図である。 図７は、交差性を判定する略垂直線分及び略水平線分の選択手法の一例を説明するための説明図である。 図８は、第１実施形態の複合機で行われる処理例を示すフローチャートである。 図９は、第１実施形態の複合機で行われる探索処理例を示すフローチャートである。 図１０は、第２実施形態の複合機の構成例を示すブロック図である。 図１１は、第２実施形態の複合機で行われる探索処理例を示すフローチャートである。 図１２は、第１、２実施形態の複合機のハードウェア構成例を示すブロック図である。 図１３は、変形例のサーバを含む情報抽出システムの構成例を示すブロック図である。

以下、添付図面を参照しながら、本発明にかかる情報抽出装置、情報抽出方法、情報抽出プログラム、及び記憶媒体の実施の形態を詳細に説明する。なお、以下の実施の形態では、情報抽出装置として、コピー機能、プリンタ機能、スキャナ機能、及びファクシミリ機能のうち、少なくともスキャナ機能、及びプリンタ機能を備える複合機（ＭＦＰ：Multifunction Printer）を例にとり説明する。

（第１の実施の形態）
第１の実施の形態では、ドットパターンの並びを近似する略垂直線分列、略水平線分列を、それぞれ構成する略垂直線分、略水平線分の中から、交差性を判定する略垂直線分、及び略水平線分を順次探索して、互いに交差する略垂直線分及び略水平線分を探索する例について説明する。

まず、第１の実施の形態の複合機の構成について説明する。

図１は、第１の実施の形態の複合機１の構成の一例を示すブロック図である。図１に示すように、複合機１は、読取部１０と、操作部１２と、表示部１４と、記憶部１６と、印刷部１８と、通信部２０と、制御部３０とを備える。

読取部１０は、印刷物を画像データとして電気的に読み取るものであり、スキャナなどの既存の読取装置により実現できる。特に本実施形態では、読取部１０は、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物を、画像データとして電気的に読み取る。なお本実施の形態では、情報の埋め込みに使用するパターンとしてドットパターンを例にとり説明するが、これに限定されるものではなく、他のパターンを用いて情報を埋め込むようにしてもよい。

図２は、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物の一例を示す図である。図２に示す例では、文書画像とともに、当該文書画像の背景にビット０とビット１を表す２種類のドットパターン(「：」と「‥」)が格子状に印刷されており、文書画像とは別に情報が埋め込まれている。なお、印刷物に埋め込まれる情報としては、例えば、印刷物のセキュリティやコンテンツを保護するための情報、印刷元の画像データやＷｅｂページを関連付けるための情報などが挙げられる。

図１に戻り、操作部１２は、印刷物の読み取りを指示する読取操作など各種操作の入力を行うものであり、キースイッチやタッチパネルなどの既存の入力装置により実現できる。

表示部１４は、読取操作など各種操作を行うためのメニュー画像、複合機１の処理経過や処理結果などを表示するものであり、タッチパネル式ディスプレイや液晶ディスプレイなどの既存の表示装置により実現できる。なお、操作部１２及び表示部１４は、タッチパネル式ディスプレイなどにより一体的に実現してもよい。

記憶部１６は、複合機１で実行される各種プログラムや複合機１で行われる各種処理に使用される各種情報などを記憶するものあり、例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、メモリカード、光ディスク、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）などの磁気的、光学的、又は電気的に記憶可能な既存の記憶装置により実現できる。

印刷部１８は、文書画像などの画像データを転写紙などの記録紙に印刷するものであり、プリンタなどの既存の印刷装置により実現できる。

通信部２０は、ネットワーク５を介して、パーソナルコンピュータ（ＰＣ：Personal Computer）などの図示せぬ外部機器との間で通信を行うものであり、通信インターフェースなどの既存の通信装置により実現できる。なお、ネットワーク５は、有線若しくは無線、またＬＡＮ(Local Area Network)や公衆通信回線を問わず、どのようなネットワークであってもよい。

制御部３０は、複合機１の各部を制御するものであり、ＣＰＵ（Central Processing Unit）などにより実現できる。そして、制御部３０は、操作受付部３２と、読取制御部３４と、線分列算出部３６と、探索部３８と、交点算出部４０と、抽出部４２と、表示制御部４４と、通信制御部４６と、印刷制御部４８とを含む。

操作受付部３２は、操作部１２により入力された読取操作など各種操作の入力を受け付ける。

読取制御部３４（取得手段の一例）は、操作受付部３２により読取操作の入力が受け付けられると、読取部１０を制御して印刷物を画像データとして読み取らせ、当該画像データを取得する。特に本実施の形態では、読取制御部３４は、読取部１０を制御して、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物（例えば、図２参照）を画像データとして読み取らせ、当該画像データを取得する。

線分列算出部３６は、読取制御部３４により取得された画像データの中の略垂直方向のドットパターン列を線分で結んだ略垂直線分列を複数算出するとともに、画像データの中の略水平方向のドットパターン列を線分で結んだ略水平線分列を複数算出する。

具体的には、線分列算出部３６は、読取制御部３４により取得された画像データの中の略垂直方向のドットパターンのいくつかをテンプレートマッチングで識別し、識別したドットパターン列から略垂直線分列を算出する。同様に、線分列算出部３６は、読取制御部３４により取得された画像データの中の略水平方向のドットパターンのいくつかをテンプレートマッチングで識別し、識別したドットパターン列から略水平線分列を算出する。

なお、略垂直線分列は、ドットパターン列を垂直方向の座標成分の順に線分で結んだ線分列となっており、略水平線分列は、ドットパターン列を水平方向の座標成分の順に線分で結んだ線分列となっている。また、略垂直線分列及び略水平線分列は、両端の線分列を半直線としてもよい。

図３及び図４は、略垂直線分列及び略水平線分列の算出手法の一例を説明するための説明図であり、読取制御部３４により取得された図２に示す印刷物の画像データを示している。

図３に示す例では、線分列算出部３６は、テンプレートマッチングにより、画像データの中の略垂直方向のドットパターン１１１、１１２、１１３、…を識別しており、識別したドットパターンそれぞれの中心をＹ座標の小さい順（ドットパターン１１１、１１２、１１３、…の順）に線分で結んで略垂直線分列１２１を算出している。同様に、線分列算出部３６は、テンプレートマッチングにより、画像データの中の略水平方向のドットパターン１１１、１１４、１１５、…を識別しており、識別したドットパターンそれぞれの中心をＸ座標の小さい順（ドットパターン１１１、１１４、１１５、…の順）に線分で結んで略水平線分列１３１を算出している。

なお本実施の形態では、図３に示すように、読取部１０のメカ的な要因による歪みが画像データに生じる場合を考慮して、線分列算出部３６により算出される線分列を略垂直線分列や略水平線分列としているが、略垂直線分列、略水平線分列は、それぞれ垂直線分列、水平線分列であってもよい。つまり、線分列算出部３６により算出される略垂直線分列、略水平線分列には、それぞれ垂直線分列、水平線分列も含まれる。

線分列算出部３６は、このような処理を行うことにより、図４に示すように、格子状に配置されたドットパターンの略垂直方向の並びを近似する複数の略垂直線分列１２１、１２２、１２３、…、及び略水平方向の並びを近似する複数の略水平線分列１３１、１３２、１３３、…を算出する。

なお、テンプレートマッチングにより識別した略垂直方向のドットパターン列をＰ_ｍ（ｍ＝１、…、Ｍ）とすると、略垂直線分列Ｓ_ｐは、以下の数式（１）により表され、テンプレートマッチングにより識別した略水平方向のドットパターン列をＱ_ｎ（ｎ＝１、…、Ｎ）とすると、略水平線分列Ｓ_Ｑは、以下の数式（２）により表される（Ｍ≧３、Ｎ≧３）。

図１に戻り、探索部３８は、線分列算出部３６により算出された略垂直線分列と略水平線分列との組み合わせ毎に、当該略垂直線分列を構成する略垂直線分及び当該略水平線分列を構成する略水平線分の中から、互いに交差する略垂直線分及び略水平線分を探索する。

具体的には、探索部３８は、略垂直線分列を構成する略垂直線分及び略水平線分列を構成する略水平線分の中から、交差性を判定する略垂直線分及び略水平線分を選択し、選択した略垂直線分又はその延長線と選択した略水平線分又はその延長線との交点を媒介変数を用いて算出し、媒介変数の値を用いて略垂直線分と略水平線分とが交差するか否かを判定する。

図５は、略垂直線分及び略水平線分の交差性の判定手法の一例を説明するための説明図であり、図６は、略垂直線分と略水平線分とが交差するか否かを判定する判定条件の一例を示す図であり、図７は、交差性を判定する略垂直線分及び略水平線分の選択手法の一例を説明するための説明図である。

探索部３８は、図５に示すように、略垂直線分列Ｓ_ｐを構成する略垂直線分Ｐ_ｉＰ_ｉ＋１（１≦ｉ≦Ｍ−１）と略水平線分列Ｓ_Ｑを構成する略水平線分Ｑ_ｊＱ_ｊ＋１（１≦ｊ≦Ｎ−１）との交差性を判定する場合、略垂直線分Ｐ_ｉＰ_ｉ＋１上の任意の点Ｐ’、略水平線分Ｑ_ｊＱ_ｊ＋１上の任意の点Ｑ’を、それぞれ媒介変数ｓ、ｔを用いて算出する。なお、点Ｐ’、点Ｑ’の値は、それぞれ以下の数式（３）、（４）により表される。

さらに、探索部３８は、点Ｐ’及び点Ｑ’の値（ｘ座標及びｙ座標）が同一になる場合の媒介変数ｓ、ｔの値を算出し、算出した媒介変数ｓ、ｔの値を用いて、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１とが交差するか否かを判定する。なお、媒介変数ｓ、ｔの値は、それぞれ以下の数式（５）、（６）により表される。

そして、探索部３８は、図６に示すように、媒介変数ｓ、ｔの値が、それぞれ０以上かつ１以下である場合に、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１とが交差すると判定し、それ以外の場合には、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１とが交差しないと判定する。

従って、図７に示す例においては、略垂直線分Ｐ_３Ｐ_４と略水平線分Ｑ_３Ｑ_４との交差性を判定する場合に、媒介変数ｓ、ｔの値が、それぞれ０以上かつ１以下となり、略垂直線分Ｐ_３Ｐ_４と略水平線分Ｑ_３Ｑ_４とが交差すると判定され、探索が終了する。

一方、探索部３８は、媒介変数の値から略垂直線分と略水平線分とが交差しないと判定した場合には、媒介変数の値を参照して次に交差性を判定する略垂直線分及び略水平線分を選択する。

具体的には、探索部３８は、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１との交差性を判定した結果、媒介変数ｓの値が０未満である場合には、図６に示すように、点Ｐ’は略垂直線分Ｐ_ｉＰ_ｉ＋１をＰ_ｉ側に延長した半直線上にあるため、略垂直線分列Ｓ_ｐの中から略垂直線分Ｐ_１Ｐ_２〜Ｐ_ｉ−１Ｐ_ｉのいずれかを選択する。

また、媒介変数ｓの値が１より大きい場合には、図６に示すように、点Ｐ’は略垂直線分Ｐ_ｉＰ_ｉ＋１をＰ_ｉ＋１側に延長した半直線上にあるため、探索部３８は、略垂直線分列Ｓ_ｐの中から略垂直線分Ｐ_ｉ＋１Ｐ_ｉ＋２〜Ｐ_Ｍ−１Ｐ_Ｍのいずれかを選択する。

また、媒介変数ｔの値が０未満である場合には、図６に示すように、点Ｑ’は略水平線分Ｑ_ｊＱ_ｊ＋１をＱ_ｊ側に延長した半直線上にあるため、探索部３８は、略水平線分列Ｓ_Ｑの中から略水平線分Ｑ_１Ｑ_２〜Ｑ_ｊ−１Ｑ_ｊのいずれかを選択する。

また、探索部３８は、媒介変数ｔの値が１より大きい場合には、図６に示すように、点Ｑ’は略水平線分Ｑ_ｊＱ_ｊ＋１をＱ_ｊ＋１側に延長した半直線上にあるため、探索部３８は、略水平線分列Ｓ_Ｑの中から略水平線分Ｑ_ｊ＋１Ｑ_ｊ＋２〜Ｑ_Ｎ−１Ｑ_Ｎのいずれかを選択する。

特に本実施の形態では、探索部３８は、媒介変数の値を参照して、交差しないと判定した略垂直線分に接続された略垂直線分、及び交差しないと判定した略水平線分に接続された略水平線分の中から、次に交差性を判定する略垂直線分及び略水平線分を選択する。

従って、探索部３８は、媒介変数ｓの値が０未満である場合には、略垂直線分列Ｓ_ｐの中から略垂直線分Ｐ_ｉ−１Ｐ_ｉを選択し、媒介変数ｓの値が１より大きい場合には、略垂直線分列Ｓ_ｐの中から略垂直線分Ｐ_ｉ＋１Ｐ_ｉ＋２を選択する。同様に、探索部３８は、媒介変数ｔの値が０未満である場合には、略水平線分列Ｓ_Ｑの中から略水平線分Ｑ_ｊ−１Ｑ_ｊを選択し、媒介変数ｔの値が１より大きい場合には、略水平線分列Ｓ_Ｑの中から略水平線分Ｑ_ｊ＋１Ｑ_ｊ＋２を選択する。

例えば、探索部３８は、図７に示す略垂直線分Ｐ_４Ｐ_５と略水平線分Ｑ_４Ｑ_５との交差性を判定すると、媒介変数ｓ、ｔの値がいずれも０未満となるので、略垂直線分列Ｓ_ｐ、略水平線分列Ｓ_Ｑの中から、それぞれ略垂直線分Ｐ_３Ｐ_４、略水平線分Ｑ_３Ｑ_４を選択する。また例えば、探索部３８は、図７に示す略垂直線分Ｐ_２Ｐ_３と略水平線分Ｑ_２Ｑ_３との交差性を判定すると、媒介変数ｓ、ｔの値がいずれも１より大きくなるので、略垂直線分列Ｓ_ｐ、略水平線分列Ｓ_Ｑの中から、それぞれ略垂直線分Ｐ_３Ｐ_４、略水平線分Ｑ_３Ｑ_４を選択する。

なお本実施の形態では、探索部３８は、最初に交差性を判定する略垂直線分及び略水平線分として、略垂直線分列の略中央に位置する略垂直線分及び略水平線分列の略中央に位置する略水平線分を選択する。

具体的には、探索部３８は、略垂直線分列Ｓ_ｐ及び略水平線分列Ｓ_Ｑの中から略垂直線分Ｐ_Ｍ／２Ｐ_{（Ｍ／２）＋１}、及び略水平線分Ｑ_Ｎ／２Ｑ_{（Ｎ／２）＋１}を最初に選択して、交差性を判定する。Ｍ／２及びＮ／２の端数は、切り捨てても切り上げてもどちらでもよい。

探索部３８は、このような処理を行うことにより、線分列算出部３６により算出された略垂直線分列と略水平線分列との組み合わせ毎に、互いに交差する略垂直線分及び略水平線分を探索する。

図１に戻り、交点算出部４０は、探索部３８により探索された略垂直線分と略水平線分との交点をドットパターンの位置として算出する。具体的には、交点算出部４０は、探索部３８により略垂直線分と略水平線分とが交差すると判定された場合には、この判定に用いた媒介変数ｓ、ｔの値を数式（５）又は（６）に代入して、略垂直線分と略水平線分との交点の座標を算出する。

抽出部４２は、交点算出部４０により算出された位置のドットパターンの種別を識別し、印刷物に埋め込まれた情報を抽出する。具体的には、抽出部４２は、交点算出部４０により算出された位置毎に、テンプレートマッチングを行ってドットパターンの種別を識別し、印刷物に埋め込まれた情報を抽出する。

そして、抽出部４２により抽出された情報を用いた処理が制御部３０により行われる。例えば、抽出部４２により抽出された情報が印刷物のセキュリティやコンテンツを保護するための情報である場合には、記憶部１６に記憶されている認証情報などを用いた改ざん検出が行われる。

表示制御部４４は、読取操作など各種操作を行うためのメニュー画像、複合機１の処理経過や処理結果などを表示部１４に表示させる。例えば、表示制御部４４は、情報抽出の処理経過、情報抽出の処理結果、改ざん検出結果などを表示部１４に表示させる。

通信制御部４６は、図示せぬ外部機器への情報の送信を通信部２０に指示したり、外部機器から送信される情報を通信部２０に受信させる。例えば、通信制御部４６は、外部機器から送信される画像データであって、背景に複数種別のドットパターンが格子状に描画された画像データを通信部２０に受信させる。

印刷制御部４８は、印刷部１８を制御して、文書画像などの画像データを転写紙などの記録紙に印刷させる。例えば、印刷制御部４８は、通信部２０により画像データが受信されると、印刷部１８を制御して、受信された画像データを記録紙に印刷させる。

なお、複合機１は、上述した各部の全てを必須の構成とする必要はなく、その一部を省略した構成としてもよい。

次に、第１の実施の形態の複合機の動作について説明する。

図８は、第１の実施の形態の複合機１で行われる処理の手順の流れの一例を示すフローチャートである。

まず、操作受付部３２は、操作部１２により入力された読取操作の入力を受け付ける（ステップＳ１２）。

続いて、読取制御部３４は、操作受付部３２により読取操作の入力が受け付けられると、読取部１０を制御して、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物を画像データとして読み取らせ、当該画像データを取得する（ステップＳ１４）。

続いて、線分列算出部３６は、読取制御部３４により取得された画像データの中の略垂直方向のドットパターン列を線分で結んだ略垂直線分列を複数算出するとともに、画像データの中の略水平方向のドットパターン列を線分で結んだ略水平線分列を複数算出する（ステップＳ１６）。

続いて、探索部３８は、線分列算出部３６により算出された略垂直線分列と略水平線分列との組み合わせ毎に、当該略垂直線分列を構成する略垂直線分及び当該略水平線分列を構成する略水平線分の中から、互いに交差する略垂直線分及び略水平線分を探索する探索処理を行う（ステップＳ１８）。なお、探索処理の詳細については後述する。

続いて、交点算出部４０は、探索部３８により探索された略垂直線分と略水平線分との交点をドットパターンの位置として算出する（ステップＳ２０）。

続いて、抽出部４２は、交点算出部４０により算出された位置のドットパターンの種別を識別し、印刷物に埋め込まれた情報を抽出する（ステップＳ２２）。

図９は、図８のステップＳ１８に示す探索処理の手順の流れの一例を示すフローチャートである。

まず、探索部３８は、変数ｉの値をＭ／２に初期化するとともに、変数ｊの値をＮ／２に初期化する（ステップＳ３０）。

続いて、探索部３８は、略垂直線分列Ｓ_ｐ、略水平線分列Ｓ_Ｑの中から、それぞれ略垂直線分Ｐ_ｉＰ_ｉ＋１、略水平線分Ｑ_ｊＱ_ｊ＋１を選択する（ステップＳ３２）。

続いて、探索部３８は、略垂直線分Ｐ_ｉＰ_ｉ＋１上の任意の点Ｐ’、略水平線分Ｑ_ｊＱ_ｊ＋１上の任意の点Ｑ’を、それぞれ媒介変数ｓ、ｔを用いて算出する（ステップＳ３４）。

続いて、探索部３８は、点Ｐ’及び点Ｑ’の値が同一になる場合の媒介変数ｓ、ｔの値を算出する（ステップＳ３６）。

続いて、探索部３８は、媒介変数ｓの値が０未満であるか否かを判定し（ステップＳ３８）、０未満である場合には、変数ｉの値をデクリメントする（ステップＳ３８でＹｅｓ、ステップＳ４０）。

一方、探索部３８は、媒介変数ｓの値が０未満でない場合には（ステップＳ３８でＮｏ）、更に媒介変数ｓの値が１より大きいか否かを判定し（ステップＳ４２）、１より大きい場合には、変数ｉの値をインクリメントする（ステップＳ４２でＹｅｓ、ステップＳ４４）。

なお、媒介変数ｓの値が０未満でも１より大きくもない場合には（ステップＳ３８でＮｏ、ステップＳ４２でＮｏ）、変数ｉの値はそのままとなる。

続いて、探索部３８は、媒介変数ｔの値が０未満であるか否かを判定し（ステップＳ４６）、０未満である場合には、変数ｊの値をデクリメントする（ステップＳ４６でＹｅｓ、ステップＳ４８）。

一方、探索部３８は、媒介変数ｔの値が０未満でない場合には（ステップＳ４６でＮｏ）、更に媒介変数ｔの値が１より大きいか否かを判定し（ステップＳ５０）、１より大きい場合には、変数ｊの値をインクリメントする（ステップＳ５０でＹｅｓ、ステップＳ５２）。

なお、媒介変数ｔの値が０未満でも１より大きくもない場合には（ステップＳ４６でＮｏ、ステップＳ５０でＮｏ）、変数ｊの値はそのままとなる。

続いて、探索部３８は、媒介変数ｓ、ｔの値がそれぞれ０以上かつ１以下であるか否かを判定し（ステップＳ５４）、それぞれ０以上かつ１以下である場合には、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１とが交差すると判定し、探索処理を終了する（ステップＳ５４でＹｅｓ）。

一方、媒介変数ｓ、ｔの値がそれぞれ０以上かつ１以下でない場合には（ステップＳ５４でＮｏ）、ステップＳ３２に戻り、探索部３８は、新たな略垂直線分Ｐ_ｉＰ_ｉ＋１、及び略水平線分Ｑ_ｊＱ_ｊ＋１を選択する。

このように第１の実施の形態によれば、ドットパターンの並びを略垂直線分列、略水平線分列により近似するため、実際のドットパターンの並びと近似された各線分列との間の誤差を小さくすることができる。従って、ドットパターンの並びが歪んだ場合であっても、ドットパターン一つひとつの位置を正確に特定して、埋め込まれた情報を抽出することができる。

特に第１の実施の形態によれば、略垂直線分列を構成する略垂直線分及び略水平線分列を構成する略水平線分の中から、交差性を判定する略垂直線分及び略水平線分を選択して判定するため、直線間の交点算出を繰り返すことにより線分列間の交点を算出でき、処理負荷を抑えることができる。従って、ドットパターンの並びが歪んだ場合であっても、ドットパターン一つひとつの位置を簡易に特定して、埋め込まれた情報を抽出することができる。

また第１の実施の形態では、略垂直線分列の略中央に位置する略垂直線分及び略水平線分列の略中央に位置する略水平線分の交差性を最初に判定する。そして、交差しないと判定した場合には、媒介変数の値を参照して、交差しないと判定した略垂直線分に接続された略垂直線分、及び交差しないと判定した略水平線分に接続された略水平線分の中から、次に交差性を判定する略垂直線分及び略水平線分を選択する。従って第１の実施の形態によれば、交差の可能性のある略垂直線分及び略水平線分を順番に探索でき、探索の回数をＭ／２又はＮ／２回以下に抑えることができるので、探索効率を高めることができる。

（第２の実施の形態）
次に、第２の実施の形態では、互いに交差する略垂直線分及び略水平線分を探索する探索効率を第１の実施の形態よりも更に高める例について説明する。なお、以下では、第１の実施の形態との相違点の説明を主に行い、第１の実施の形態と同様の機能を有する構成要素については、第１の実施の形態と同様の名称・符号を付し、その説明を省略する。

まず、第２の実施の形態の複合機の構成について説明する。

図１０は、第２の実施の形態の複合機２０１の構成の一例を示すブロック図である。なお、複合機２０１の構成は、制御部２３０の探索部２３８を除き複合機１の構成と同様であるため、以下では、第１の実施の形態と第２の実施の形態の主要な相違点である探索部２３８の構成について説明する。

探索部２３８は、まず、略垂直線分列の中から略水平線分と交差の可能性がある線分列である略垂直部分線分列を設定するとともに、略水平線分列の中から略垂直線分と交差の可能性がある線分列である略水平部分線分列を設定する。なお、探索部２３８により設定される略垂直部分線分列Ｓ’_ｐ、略水平部分線分列Ｓ’_Ｑは、それぞれ以下の数式（７）、（８）により表される（１≦Ｐｓ≦Ｍ−２、２≦Ｐｅ≦Ｍ−１、１≦Ｑｓ≦Ｎ−２、２≦Ｑｅ≦Ｎ−２）。

続いて、探索部２３８は、略垂直部分線分列Ｓ’_ｐを構成する略垂直線分Ｐ_ＰｓＰ_Ｐｓ＋１〜Ｐ_ＰｅＰ_Ｐｅ＋１、略水平部分線分列Ｓ’_Ｑを構成する略水平線分Ｑ_ＱｓＱ_Ｑｓ＋１〜Ｑ_ＱｅＱ_Ｑｅ＋１の中から、それぞれ略垂直線分Ｐ_ｉＰ_ｉ＋１（Ｐｓ≦ｉ≦Ｐｅ）、略水平線分Ｑ_ｊＱ_ｊ＋１（Ｑｓ≦ｊ≦Ｑｅ）を選択して交差性を判定する。なお、この処理は第１の実施の形態と同様であるため説明を省略する。

そして、探索部２３８は、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１とが交差しないと判定した場合には、媒介変数の値を参照して、略垂直部分線分列及び略水平部分線分列を設定（再設定）し、設定後の略垂直部分線分列及び略水平部分線分列の中から、次に交差性を判定する略垂直線分及び略水平線分を選択する。

具体的には、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１との交差性を判定した結果、媒介変数ｓの値が０未満である場合には、図６に示すように、点Ｐ’は略垂直線分Ｐ_ｉＰ_ｉ＋１をＰ_ｉ側に延長した半直線上にある。このため、探索部２３８は、略垂直部分線分列Ｓ’_ｐの最後尾の線分を略垂直線分Ｐ_ｉＰ_ｉ＋１に設定し（Ｐｅ＝ｉ）、設定後の略垂直部分線分列Ｓ’_ｐである略垂直線分Ｐ_ＰｓＰ_Ｐｓ＋１〜Ｐ_ｉＰ_ｉ＋１の中から略垂直線分を選択する。

また、媒介変数ｓの値が１より大きい場合には、図６に示すように、点Ｐ’は略垂直線分Ｐ_ｉＰ_ｉ＋１をＰ_ｉ＋１側に延長した半直線上にある。このため、探索部２３８は、略垂直部分線分列Ｓ’_ｐの先頭の線分を略垂直線分Ｐ_ｉＰ_ｉ＋１に設定し（Ｐｓ＝ｉ）、設定後の略垂直部分線分列Ｓ’_ｐである略垂直線分Ｐ_ｉＰ_ｉ＋１〜Ｐ_ＰｅＰ_Ｐｅ＋１の中から略垂直線分を選択する。

また、媒介変数ｔの値が０未満である場合には、図６に示すように、点Ｑ’は略水平線分Ｑ_ｊＱ_ｊ＋１をＱ_ｊ側に延長した半直線上にある。このため、探索部２３８は、略水平部分線分列Ｓ’_Ｑの最後尾の線分を略水平線分Ｑ_ｊＱ_ｊ＋１に設定し（Ｑｅ＝ｊ）、設定後の略水平部分線分列Ｓ’_Ｑである略水平線分Ｑ_ＱｓＱ_Ｑｓ＋１〜Ｑ_ｊＱ_ｊ＋１の中から略水平線分を選択する。

また、媒介変数ｔの値が１より大きい場合には、図６に示すように、点Ｑ’は略水平線分Ｑ_ｊＱ_ｊ＋１をＱ_ｊ＋１側に延長した半直線上にある。このため、探索部２３８は、略水平部分線分列Ｓ’_Ｑの先頭の線分を略水平線分Ｑ_ｊＱ_ｊ＋１に設定し（Ｑｓ＝ｊ）、設定後の略水平部分線分列Ｓ’_Ｑである略水平線分Ｑ_ｊＱ_ｊ＋１〜Ｑ_ＱｅＱ_Ｑｅ＋１の中から略水平線分を選択する。

特に本実施の形態では、探索部２３８は、次に交差性を判定する略垂直線分及び略水平線分として、略垂直部分線分列の略中央に位置する略垂直線分及び略水平部分線分列の略中央に位置する略水平線分を選択する。

従って、探索部２３８は、略垂直部分線分列Ｓ’_ｐの範囲が略垂直線分Ｐ_ＰｓＰ_Ｐｓ＋１〜Ｐ_ｉＰ_ｉ＋１である場合には、略垂直線分Ｐ_{（Ｐｓ＋ｉ）／２}Ｐ_{（（Ｐｓ＋ｉ）／２）＋１}を選択し、略垂直部分線分列Ｓ’_ｐの範囲が略垂直線分Ｐ_ｉＰ_ｉ＋１〜Ｐ_ＰｅＰ_Ｐｅ＋１である場合には、略垂直線分Ｐ_{（ｉ＋Ｐｅ）／２}Ｐ_{（（ｉ＋Ｐｅ）／２）＋１}を選択する。（Ｐｓ＋ｉ）／２及び（ｉ＋Ｐｅ）／２の端数は、切り捨てても切り上げてもどちらでもよい。

同様に、探索部２３８は、略水平部分線分列Ｓ’_Ｑの範囲が略水平線分Ｑ_ＱｓＱ_Ｑｓ＋１〜Ｑ_ｊＱ_ｊ＋１である場合には、略水平線分Ｑ_{（Ｑｓ＋ｊ）／２}Ｑ_{（（Ｑｓ＋ｊ）／２）＋１}を選択し、略水平部分線分列Ｓ’_Ｑの範囲が略水平線分Ｑ_ｊＱ_ｊ＋１〜Ｑ_ＱｅＱ_Ｑｅ＋１である場合には、略水平線分Ｑ_{（ｊ＋Ｑｅ）／２}Ｑ_{（（ｊ＋Ｑｅ）／２）＋１}を選択する。（Ｑｓ＋ｊ）／２及び（ｊ＋Ｑｅ）／２の端数は、切り捨てても切り上げてもどちらでもよい。

なお本実施の形態では、探索部２３８は、探索開始時には、略垂直部分線分列Ｓ’_ｐ、略水平部分線分列Ｓ’_Ｑを、それぞれ略垂直線分列Ｓ_ｐ、略水平線分列Ｓ_Ｑと同一の線分列に設定する。つまり、探索部２３８は、略垂直部分線分列Ｓ’_ｐの先頭の線分を略垂直線分Ｐ_１Ｐ_２に設定し、最後尾の線分を略垂直線分Ｐ_Ｍ−１Ｐ_Ｍに設定する（Ｐｓ＝１、Ｐｅ＝Ｍ−１）。同様に、探索部２３８は、略水平部分線分列Ｓ’_Ｑの先頭の線分を略水平線分Ｑ_１Ｑ_２に設定し、最後尾の線分を略水平線分Ｑ_Ｎ−１Ｑ_Ｎに設定する（Ｑｓ＝１、Ｑｅ＝Ｎ−１）。

そして、探索部２３８は、最初に交差性を判定する略垂直線分及び略水平線分として、略垂直部分線分列Ｓ’_ｐ（略垂直線分列Ｓ_ｐ）の略中央に位置する略垂直線分及び略水平部分線分列Ｓ’_Ｑ（略水平線分列Ｓ_Ｑ）の略中央に位置する略水平線分を選択する。具体的には、探索部２３８は、略垂直部分線分列Ｓ’_ｐ及び略水平部分線分列Ｓ’_Ｑの中から略垂直線分Ｐ_{（Ｐｓ＋Ｐｅ）／２}Ｐ_{（（Ｐｓ＋Ｐｅ）／２）＋１}、及び略水平線分Ｑ_{（Ｑｓ＋Ｑｅ）／２}Ｑ_{（（Ｑｓ＋Ｑｅ）／２）＋１}を最初に選択して、交差性を判定する。ここで、探索開始時には、Ｐｓ＝Ｑｓ＝１、Ｐｅ＝Ｍ−１、Ｑｅ＝Ｎ−１となっているため、探索部２３８は、第１の実施形態同様、略垂直線分Ｐ_Ｍ／２Ｐ_{（Ｍ／２）＋１}、及び略水平線分Ｑ_Ｎ／２Ｑ_{（Ｎ／２）＋１}を最初に選択して、交差性を判定する。

探索部２３８は、このような処理を行うことにより、線分列算出部３６により算出された略垂直線分列と略水平線分列との組み合わせ毎に、互いに交差する略垂直線分及び略水平線分を探索する。

次に、第２の実施の形態の複合機の動作について説明する。なお、第２の実施の形態の複合機２０１で行われる処理の手順の流れは、第１の実施の形態と同様であるため（図８参照）、説明を省略する。

図１１は、図８のステップＳ１８に示す探索処理の手順の流れの一例を示すフローチャートである。

まず、探索部２３８は、略垂直部分線分列Ｓ’_ｐの変数Ｐｓ、Ｐｅの値を、それぞれ１、Ｍ−１に設定するとともに、略水平部分線分列Ｓ’_Ｑの変数Ｑｓ、Ｑｅの値を、それぞれ１、Ｎ−１に設定する（ステップＳ６０）。

続いて、探索部２３８は、変数ｉの値を（Ｐｓ＋Ｐｅ）／２に設定するとともに、変数ｊの値を（Ｑｓ＋Ｑｅ）／２に設定する（ステップＳ６２）。

続いて、探索部２３８は、略垂直部分線分列Ｓ’_ｐ、略水平部分線分列Ｓ’_Ｑの中から、それぞれ略垂直線分Ｐ_ｉＰ_ｉ＋１、略水平線分Ｑ_ｊＱ_ｊ＋１を選択する（ステップＳ６４）。

続いて、探索部２３８は、略垂直線分Ｐ_ｉＰ_ｉ＋１上の任意の点Ｐ’、略水平線分Ｑ_ｊＱ_ｊ＋１上の任意の点Ｑ’を、それぞれ媒介変数ｓ、ｔを用いて算出する（ステップＳ６６）。

続いて、探索部２３８は、点Ｐ’及び点Ｑ’の値が同一になる場合の媒介変数ｓ、ｔの値を算出する（ステップＳ６８）。

続いて、探索部２３８は、媒介変数ｓの値が０未満であるか否かを判定し（ステップＳ７０）、０未満である場合には、変数Ｐｅの値をｉに設定する（ステップＳ７０でＹｅｓ、ステップＳ７２）。

一方、探索部２３８は、媒介変数ｓの値が０未満でない場合には（ステップＳ７０でＮｏ）、更に媒介変数ｓの値が１より大きいか否かを判定し（ステップＳ７４）、１より大きい場合には、変数Ｐｓの値をｉに設定する（ステップＳ７４でＹｅｓ、ステップＳ７６）。

なお、媒介変数ｓの値が０以上かつ１以下である場合には（ステップＳ７０でＮｏ、ステップＳ７４でＮｏ）、変数ｉの値はそのままとなる。

続いて、探索部２３８は、媒介変数ｔの値が０未満であるか否かを判定し（ステップＳ７８）、０未満である場合には、変数Ｑｅの値をｊに設定する（ステップＳ７８でＹｅｓ、ステップＳ８０）。

一方、探索部２３８は、媒介変数ｔの値が０未満でない場合には（ステップＳ７８でＮｏ）、更に媒介変数ｔの値が１より大きいか否かを判定し（ステップＳ８２）、１より大きい場合には、変数Ｑｓの値をｊに設定する（ステップＳ８２でＹｅｓ、ステップＳ８４）。

なお、媒介変数ｔの値が０以上かつ１以下である場合には（ステップＳ７８でＮｏ、ステップＳ８２でＮｏ）、変数ｊの値はそのままとなる。

続いて、探索部２３８は、媒介変数ｓ、ｔの値がそれぞれ０以上かつ１以下であるか否かを判定し（ステップＳ８６）、媒介変数ｓ、ｔの値がそれぞれ０以上かつ１以下である場合には、略垂直線分Ｐ_ｉＰ_ｉ＋１と略水平線分Ｑ_ｊＱ_ｊ＋１とが交差すると判定し、探索処理を終了する（ステップＳ８６でＹｅｓ）。

一方、媒介変数ｓ、ｔの値がそれぞれ０以上かつ１以下でない場合には（ステップＳ８６でＮｏ）、ステップＳ６２に戻り、探索部２３８は、変数ｉ、ｊの値を新たな値に設定し、新たな略垂直部分線分列Ｓ’_ｐ、略水平部分線分列Ｓ’_Ｑの中から、それぞれ新たな略垂直線分Ｐ_ｉＰ_ｉ＋１、略水平線分Ｑ_ｊＱ_ｊ＋１を選択する。

このように第２の実施の形態では、媒介変数の値を参照して、略水平線分と交差の可能性がある線分列である略垂直部分線分列を設定するとともに、略垂直線分と交差の可能性がある線分列である略水平部分線分列を設定する。そして、略垂直部分線分列の略中央に位置する略垂直線分及び略水平部分線分列の略中央に位置する略水平線分を次に交差性を判定する略垂直線分及び略水平線分として選択する。従って第２の実施の形態によれば、探索の回数をｌｏｇ_２Ｍ又はｌｏｇ_２Ｎ回以下に抑えることができるので、探索効率を更に高めることができる。

（第１〜２の実施の形態の複合機のハードウェア構成）
図１２は、第１〜２の実施の形態の複合機１、２０１のハードウェア構成の一例を示すブロック図である。

図１２に示すように、複合機１、２０１は、コントローラ３１０とエンジン部（Engine）３６０とをＰＣＩ（Peripheral Component Interconnect）バスで接続した構成となる。コントローラ３１０は、複合機１、２０１全体の制御、描画、通信、及び操作表示部３２０からの入力を制御するコントローラである。エンジン部３６０は、ＰＣＩバスに接続可能なプリンタエンジンなどであり、たとえば白黒プロッタ、１ドラムカラープロッタ、４ドラムカラープロッタ、スキャナまたはファックスユニットなどである。なお、このエンジン部３６０には、プロッタなどのいわゆるエンジン部分に加えて、誤差拡散やガンマ変換などの画像処理部分が含まれる。

コントローラ３１０は、ＣＰＵ３１１と、ノースブリッジ（ＮＢ）３１３と、システムメモリ（ＭＥＭ−Ｐ）３１２と、サウスブリッジ（ＳＢ）３１４と、ローカルメモリ（ＭＥＭ−Ｃ）３１７と、ＡＳＩＣ（Application Specific Integrated Circuit）３１６と、ハードディスクドライブ（ＨＤＤ）３１８とを有し、ノースブリッジ（ＮＢ）３１３とＡＳＩＣ３１６との間をＡＧＰ（Accelerated Graphics Port）バス３１５で接続した構成となる。また、ＭＥＭ−Ｐ３１２は、ＲＯＭ３１２ａと、ＲＡＭ３１２ｂとをさらに有する。

ＣＰＵ３１１は、複合機１、２０１の全体制御をおこなうものであり、ＮＢ３１３、ＭＥＭ−Ｐ３１２およびＳＢ３１４からなるチップセットを有し、このチップセットを介して他の機器と接続される。

ＮＢ３１３は、ＣＰＵ３１１とＭＥＭ−Ｐ３１２、ＳＢ３１４、ＡＧＰ３１５とを接続するためのブリッジであり、ＭＥＭ−Ｐ３１２に対する読み書きなどを制御するメモリコントローラと、ＰＣＩマスタおよびＡＧＰターゲットとを有する。

ＭＥＭ−Ｐ３１２は、プログラムやデータの格納用メモリ、プログラムやデータの展開用メモリ、プリンタの描画用メモリなどとして用いるシステムメモリであり、ＲＯＭ３１２ａとＲＡＭ３１２ｂとからなる。ＲＯＭ３１２ａは、プログラムやデータの格納用メモリとして用いる読み出し専用のメモリであり、ＲＡＭ３１２ｂは、プログラムやデータの展開用メモリ、プリンタの描画用メモリなどとして用いる書き込みおよび読み出し可能なメモリである。

ＳＢ３１４は、ＮＢ３１３とＰＣＩデバイス、周辺デバイスとを接続するためのブリッジである。このＳＢ３１４は、ＰＣＩバスを介してＮＢ３１３と接続されており、このＰＣＩバスには、ネットワークインターフェース（Ｉ／Ｆ）部なども接続される。

ＡＳＩＣ３１６は、画像処理用のハードウェア要素を有する画像処理用途向けのＩＣ（Integrated Circuit）であり、ＡＧＰ３１５、ＰＣＩバス、ＨＤＤ３１８およびＭＥＭ−Ｃ３１７をそれぞれ接続するブリッジの役割を有する。このＡＳＩＣ３１６は、ＰＣＩターゲットおよびＡＧＰマスタと、ＡＳＩＣ３１６の中核をなすアービタ（ＡＲＢ）と、ＭＥＭ−Ｃ３１７を制御するメモリコントローラと、ハードウェアロジックなどにより画像データの回転などをおこなう複数のＤＭＡＣ（Direct Memory Access Controller）と、エンジン部３６０との間でＰＣＩバスを介したデータ転送をおこなうＰＣＩユニットとからなる。このＡＳＩＣ３１６には、ＰＣＩバスを介してＦＣＵ（Fax Control Unit）３３０、ＵＳＢ（Universal Serial Bus）３４０、ＩＥＥＥ１３９４（the Institute of Electrical and Electronics Engineers 1394）インターフェース３５０が接続される。操作表示部３２０はＡＳＩＣ３１６に直接接続されている。

ＭＥＭ−Ｃ３１７は、コピー用画像バッファ、符号バッファとして用いるローカルメモリであり、ＨＤＤ（Hard Disk Drive）３１８は、画像データの蓄積、プログラムの蓄積、フォントデータの蓄積、フォームの蓄積を行うためのストレージである。

ＡＧＰ３１５は、グラフィック処理を高速化するために提案されたグラフィックスアクセラレーターカード用のバスインターフェースであり、ＭＥＭ−Ｐ３１２に高スループットで直接アクセスすることにより、グラフィックスアクセラレーターカードを高速にするものである。

なお、本実施の形態の複合機１、２０１で実行される情報抽出プログラムは、ＲＯＭ等に予め組み込まれて提供される。

本実施の形態の複合機１、２０１で実行される情報抽出プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記憶媒体に記録して提供するように構成してもよい。

さらに、本実施の形態の複合機１、２０１で実行される情報抽出プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、本実施の形態の複合機１、２０１で実行される情報抽出プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。

本実施の形態の複合機１、２０１で実行される情報抽出プログラムは、上述した各部（操作受付部、読取制御部、線分列算出部、探索部、交点算出部、抽出部、表示制御部、通信制御部、印刷制御部など）をコンピュータ上で実現させるためのモジュール構成となっている。実際のハードウェアとしてはＣＰＵ３１１がＲＯＭ３１２ａから情報抽出プログラムをＲＡＭ３１２ｂ上に読み出して実行することにより、上記各部（操作受付部、読取制御部、線分列算出部、探索部、交点算出部、抽出部、表示制御部、通信制御部、印刷制御部など）がコンピュータ上で実現されるようになっている。

（変形例）
なお、本発明は、上記各実施の形態に限定されるものではなく、種々の変形が可能である。

例えば、上記各実施の形態では、情報抽出装置を複合機に適用した例について説明したが、サーバ装置やパーソナルコンピュータに適用することもできる。

図１３は、変形例の情報抽出システムの構成の一例を示すブロック図であり、サーバ４０１と、画像読取装置４０８とを含む。

画像読取装置４０８は、印刷物（例えば、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物）を画像データとして電気的に読み取るものであり、複合機やスキャナなどにより実現できる。そして、画像読取装置４０８は、読み取った画像データをサーバ４０１にネットワーク４０５を介して送信し、埋め込まれた情報の抽出結果や、埋め込まれた情報を用いた改ざん検出結果などをネットワーク４０５を介して受信する。

サーバ４０１は、図１３に示すように、操作部４１２と、表示部４１４と、記憶部４１６と、通信部４２０と、制御部４３０とを備え、制御部４３０は、通信制御部４３４と、線分列算出部４３６と、探索部４３８と、交点算出部４４０と、抽出部４４２と、表示制御部４４４と、操作受付部４４６とを含む。なお、サーバ４０１と、上記各実施の形態の複合機１、２０１との主要な相違は、通信部４２０、及び通信制御部４３４にあるため、以下では、通信部４２０、及び通信制御部４３４の構成について説明し、その他の構成については、上記各実施の形態と同様なものとして、説明を省略する。

通信部４２０は、印刷物を画像データとして電気的に読み取る複合機やスキャナなどの画像読取装置４０８から、ネットワーク４０５を介して、複数種別のドットパターンを格子状に印刷することで情報が埋め込まれた印刷物の画像データを受信する。また、通信部４２０は、画像データ（印刷物）に埋め込まれた情報の抽出結果や、埋め込まれた情報を用いた改ざん検出結果などをネットワーク４０５を介して画像読取装置４０８に送信する。

通信制御部４３４（取得手段の一例）は、画像読取装置４０８への情報の送信を通信部４２０に指示したり、画像読取装置４０８から送信される情報を通信部４２０に受信させる。例えば、通信制御部４３４は、画像読取装置４０８から送信される画像データであって、背景に複数種別のドットパターンが格子状に描画された画像データを通信部４２０に受信させ、当該画像データを取得する。

そして、線分列算出部４３６、探索部４３８、交点算出部４４０、抽出部４４２などが、通信制御部４３４により取得された画像データを用いて上述の各実施の形態で説明した処理を行い、画像データ（印刷物）に埋め込まれた情報を抽出する。

このように、本発明の情報抽出装置は、サーバ装置やパーソナルコンピュータに適用することもできる。

１，２０１ 複合機
５ ネットワーク
１０ 読取部
１２ 操作部
１４ 表示部
１６ 記憶部
１８ 印刷部
２０ 通信部
３０，２３０ 制御部
３２ 操作受付部
３４ 読取制御部
３６ 線分列算出部
３８，２３８ 探索部
４０ 交点算出部
４２ 抽出部
４４ 表示制御部
４６ 通信制御部
４８ 印刷制御部
１１１〜１１５ ドットパターン
１２１〜１２３ 略垂直線分列
１３１〜１３３ 略水平線分列
３１０ コントローラ
３１１ ＣＰＵ
３１２ システムメモリ
３１２ａ ＲＯＭ
３１２ｂ ＲＡＭ
３１３ ノースブリッジ
３１４ サウスブリッジ
３１５ ＡＧＰバス
３１６ ＡＳＩＣ
３１７ ローカルメモリ
３１８ ハードディスクドライブ
３２０ 操作表示部
３３０ ＦＣＵ
３４０ ＵＳＢ
３５０ ＩＥＥＥ１３９４インターフェース
３６０ エンジン部
４０１ サーバ
４０５ ネットワーク
４０８ 画像読取装置
４１２ 操作部
４１４ 表示部
４１６ 記憶部
４２０ 通信部
４３０ 制御部
４３４ 通信制御部
４３６ 線分列算出部
４３８ 探索部
４４０ 交点算出部
４４２ 抽出部
４４４ 表示制御部
４４６ 操作受付部

特開２００６−２３８１１９号公報 特許第２７３４６４３号公報

Claims (13)

1. 複数種別のパターンを格子状に印刷することで情報が埋め込まれた印刷物の画像データを取得する取得手段と、
   前記画像データの中の略垂直方向のパターン列を線分で結んだ略垂直線分列を複数算出するとともに、前記画像データの中の略水平方向のパターン列を線分で結んだ略水平線分列を複数算出する線分列算出手段と、
   前記略垂直線分列と前記略水平線分列との組み合わせ毎に、当該略垂直線分列を構成する略垂直線分及び当該略水平線分列を構成する略水平線分の中から、互いに交差する略垂直線分及び略水平線分を探索する探索手段と、
   探索された前記略垂直線分と前記略水平線分との交点をパターンの位置として算出する交点算出手段と、
   算出された位置のパターンの種別を識別し、前記印刷物に埋め込まれた情報を抽出する抽出手段と、
   を備えることを特徴とする情報抽出装置。
2. 前記探索手段は、交差性を判定する略垂直線分及び略水平線分を選択し、選択した前記略垂直線分又はその延長線と選択した前記略水平線分又はその延長線との交点を媒介変数を用いて算出し、前記媒介変数の値を用いて前記略垂直線分と前記略水平線分とが交差するか否かを判定することを特徴とする請求項１に記載の情報抽出装置。
3. 前記探索手段は、前記媒介変数の値から前記略垂直線分と前記略水平線分とが交差しないと判定した場合には、前記媒介変数の値を参照して次に交差性を判定する略垂直線分及び略水平線分を選択することを特徴とする請求項２に記載の情報抽出装置。
4. 前記探索手段は、前記媒介変数の値を参照して、交差しないと判定した前記略垂直線分に接続された略垂直線分、及び交差しないと判定した前記略水平線分に接続された略水平線分の中から、次に交差性を判定する略垂直線分及び略水平線分を選択することを特徴とする請求項３に記載の情報抽出装置。
5. 前記探索手段は、前記媒介変数の値を参照して、略水平線分と交差の可能性がある線分列である略垂直部分線分列を設定するとともに、略垂直線分と交差の可能性がある線分列である略水平部分線分列を設定し、前記略垂直部分線分列及び前記略水平部分線分列の中から、次に交差性を判定する略垂直線分及び略水平線分を選択することを特徴とする請求項３に記載の情報抽出装置。
6. 前記探索手段は、次に交差性を判定する略垂直線分及び略水平線分として、前記略垂直部分線分列の略中央に位置する略垂直線分及び前記略水平部分線分列の略中央に位置する略水平線分を選択することを特徴とする請求項５に記載の情報抽出装置。
7. 前記探索手段は、最初に交差性を判定する略垂直線分及び略水平線分として、前記略垂直線分列の略中央に位置する略垂直線分及び前記略水平線分列の略中央に位置する略水平線分を選択することを特徴とする請求項２〜６のいずれか１つに記載の情報抽出装置。
8. 前記略垂直線分列は、前記画像データの中の略垂直方向のパターン列を垂直方向の座標成分の順に線分で結んだ線分列であり、
   前記略水平線分列は、前記画像データの中の略水平方向のパターン列を水平方向の座標成分の順に線分で結んだ線分列であることを特徴とする請求項１〜７のいずれか１つに記載の情報抽出装置。
9. 前記取得手段は、読取手段を制御して前記印刷物を前記画像データとして読み取らせ、当該画像データを取得することを特徴とする請求項１〜８のいずれか１つに記載の情報抽出装置。
10. 前記取得手段は、前記印刷物を前記画像データとして読み取る読取装置から、ネットワークを介して前記画像データを取得することを特徴とする請求項１〜８のいずれか１つに記載の情報抽出装置。
11. 取得手段が、複数種別のパターンを格子状に印刷することで情報が埋め込まれた印刷物の画像データを取得する取得ステップと、
    線分列算出手段が、前記画像データの中の略垂直方向のパターン列を線分で結んだ略垂直線分列を複数算出するとともに、前記画像データの中の略水平方向のパターン列を線分で結んだ略水平線分列を複数算出する線分列算出ステップと、
    探索手段が、前記略垂直線分列と前記略水平線分列との組み合わせ毎に、当該略垂直線分列を構成する略垂直線分及び当該略水平線分列を構成する略水平線分の中から、互いに交差する略垂直線分及び略水平線分を探索する探索ステップと、
    交点算出手段が、探索された前記略垂直線分と前記略水平線分との交点をパターンの位置として算出する交点算出ステップと、
    抽出手段が、算出された位置のパターンの種別を識別し、前記印刷物に埋め込まれた情報を抽出する抽出ステップと、
    を含むことを特徴とする情報抽出方法。
12. 請求項１１に記載の情報抽出方法をコンピュータに実行させるための情報抽出プログラム。
13. 請求項１２に記載の情報抽出プログラムを記憶したコンピュータ読み取り可能な記憶媒体。

Images