(57)【要約】      （修正有）【課題】文書画像に適切に情報を埋め込むことができ、また、埋め込まれた情報を抽出できるようにする。【解決手段】文書画像に情報を埋め込む情報埋め込み装置であって、前記文書画像より行及び文字間隔を抽出する画像解析手段と、前記画像解析手段によって抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手段と、前記文字間隔長変更手段によって前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手段と、前記判定手段によって前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手段とを有する。【選択図】図２
2006191520.tif 000002
【特許請求の範囲】
【請求項１】
文書画像に情報を埋め込む情報埋め込み装置であって、
前記文書画像より行及び文字間隔を抽出する画像解析手段と、
前記画像解析手段によって抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手段と、
前記文字間隔長変更手段によって前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手段と、
前記判定手段によって前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手段とを有することを特徴とする情報埋め込み装置。
【請求項２】
前記第一の文字間隔長変更手段は、前記画像解析手段によって抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じた値に所定の定数を乗ずることにより得られる値のうち、当該文字間隔の文字間隔長に最も近い値に前記文字間隔長を変更することを特徴とする請求項１記載の情報埋め込み装置。
【請求項３】
前記判定手段は、前記行の長さの変化量が所定の閾値以下である場合に前記所定の基準を満たしていると判定することを特徴とする請求項１又は２記載の情報埋め込み装置。
【請求項４】
前記判定手段は、前記行の長さの変化量が前記所定の定数以下である場合に前記所定の基準を満たしていると判定することを特徴とする請求項２記載の情報埋め込み装置。
【請求項５】
前記第二の文字間隔長変更手段は、前記行の長さの変化量と同じ方向に前記文字間隔長が変更された前記文字間隔の前記文字間隔長を、前記行の長さの変化量を小さくする方向に変更することを特徴とする請求項１乃至４いずれか一項記載の情報埋め込み装置。
【請求項６】
前記第二の文字間隔長変更手段は、前記行の長さの変化量が前記所定の基準を満たすまで、複数の前記文字間隔について順番に前記文字間隔長を変更することを特徴とする請求項５記載の情報埋め込み装置。
【請求項７】
前記第二の文字間隔長変更手段は、前記文字間隔長の変化量が最も大きい前記文字間隔の前記文字間隔長を変更することを特徴とする請求項５又は６記載の情報埋め込み装置。
【請求項８】
前記第二の文字間隔長変更手段は、前記行の長さの変化量と同じ方向に前記文字間隔長が変更された全ての前記文字間隔の文字間隔長を変更しても前記行の長さの変化量が前記所定の基準を満たさない場合に、前記文字間隔長の変化量が最も小さい前記文字間隔の前記文字間隔長を、前記行の長さの変化量を小さくする方向に変更することを特徴とする請求項５乃至７いずれか一項記載の情報埋め込み装置。
【請求項９】
前記第二の文字間隔長変更手段は、前記行の長さの変化量が前記所定の基準を満たすまで、前記文字間隔長の変化量が最も小さい前記文字間隔の前記文字間隔長を繰り返し変更することを特徴とする請求項８記載の情報埋め込み装置。
【請求項１０】
前記文書画像に埋め込む情報をｎ進数に変換した場合の各桁を、前記文字間隔ごとに埋め込むことを特徴とする請求項１乃至９いずれか一項記載の情報埋め込み装置。
【請求項１１】
前記ｎ進数は、２進数であることを特徴とする請求項１０記載の情報埋め込み装置。
【請求項１２】
請求項１乃至１１いずれか一項記載の情報埋め込み装置によって情報を埋め込まれた文書画像より情報を抽出する情報抽出装置であって、
前記文書画像より行及び文字間隔を抽出する画像解析手段と、
前記画像解析手段によって抽出された前記文字間隔の文字間隔長に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手段とを有することを特徴とする情報抽出装置。
【請求項１３】
文書画像に情報を埋め込む情報埋め込み方法であって、
前記文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手順と、
前記文字間隔長変更手順において前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手順と、
前記判定手順において、前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手順とを有することを特徴とする情報埋め込み方法。
【請求項１４】
前記第一の文字間隔長変更手順は、前記画像解析手順において抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じた値に所定の定数を乗ずることにより得られる値のうち、当該文字間隔の文字間隔長に最も近い値に前記文字間隔長を変更することを特徴とする請求項１３記載の情報埋め込み方法。
【請求項１５】
前記判定手順は、前記行の長さの変化量が所定の閾値以下である場合に、前記所定の基準を満たしていると判定することを特徴とする請求項１３又は１４記載の情報埋め込み方法。
【請求項１６】
前記所定の閾値は前記所定の定数と同値であることを特徴とする請求項１５記載の情報埋め込み方法。
【請求項１７】
前記第二の文字間隔長変更手順は、前記行の長さの変化量と同じ方向に前記文字間隔長が変更された前記文字間隔の前記文字間隔長を、前記行の長さの変化量を小さくする方向に変更する第一の補正手順を有することを特徴とする請求項１３乃至１６いずれか一項記載の情報埋め込み方法。
【請求項１８】
前記第一の補正手順は、前記行の長さの変化量が前記所定の基準を満たすまで複数の前記文字間隔について順番に行われることを特徴とする請求項１７記載の情報埋め込み方法。
【請求項１９】
前記第一の補正手順は、前記文字間隔長の変化量が最も大きい前記文字間隔の前記文字間隔長を変更することを特徴とする請求項１７又は１８記載の情報埋め込み方法。
【請求項２０】
前記第二の文字間隔長変更手順は、前記第一の補正手順において前記行の長さの変化量と同じ方向に前記文字間隔長が変更された全ての前記文字間隔の文字間隔長を変更しても前記行の長さの変化量が前記所定の基準を満たさない場合に、前記文字間隔長の変化量が最も小さい前記文字間隔の前記文字間隔長を、前記行の長さの変化量を小さくする方向に変更する第二の補正手順を有することを特徴とする請求項１７乃至１９いずれか一項記載の情報埋め込み方法。
【請求項２１】
前記第二の補正手順は、前記行の長さの変化量が前記所定の基準を満たすまで繰り返し行われることを特徴とする請求項２０記載の情報埋め込み方法。
【請求項２２】
前記文書画像に埋め込む情報をｎ進数に変換した場合の各桁を、前記文字間隔ごとに埋め込むことを特徴とする請求項１３乃至２１いずれか一項記載の情報埋め込み方法。
【請求項２３】
前記ｎ進数は、２進数であることを特徴とする請求項２２記載の情報埋め込み方法。
【請求項２４】
請求項１３乃至２３いずれか一項記載の情報埋め込み方法によって情報を埋め込まれた文書画像より情報を抽出する情報抽出方法であって、
前記文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔の文字間隔長に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手順とを有することを特徴とする情報抽出方法。
【請求項２５】
情報が埋め込まれた文書画像を生成する文書画像生成方法であって、
情報が埋め込まれる前の文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手順と、
前記文字間隔長変更手順において前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手順と、
前記判定手順において、前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手順とを有することを特徴とする文書画像生成方法。
【請求項２６】
情報が埋め込まれた文書画像が印刷された印刷物を生成する印刷物生成方法であって、
情報が埋め込まれる前の文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手順と、
前記文字間隔長変更手順において前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手順と、
前記判定手順において、前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手順と、
少なくとも前記第一の文字間隔長変更手順において前記文字間隔長が変更された文書画像を印刷する印刷手順とを有することを特徴とする印刷物生成方法。
【請求項２７】
請求項１３乃至２３いずれか一項記載の情報埋め込み方法によって情報が埋め込まれた文書画像。
【請求項２８】
請求項１３乃至２３いずれか一項記載の情報埋め込み方法によって情報が埋め込まれた文書画像が印刷された印刷物。
【請求項２９】
コンピュータに、
文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手順と、
前記文字間隔長変更手順において前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手順と、
前記判定手順において、前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手順とを実行させるための情報埋め込みプログラム。
【請求項３０】
コンピュータに、
請求項２９記載の情報埋め込みプログラムによって情報を埋め込まれた文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔の文字間隔長に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手順とを実行させるための情報抽出プログラム。
【請求項３１】
請求項２９記載の情報埋め込みプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項３２】
請求項３０記載の情報抽出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項３３】
文書画像に情報を埋め込む情報埋め込み装置であって、
前記文書画像より行及び文字間隔を抽出する画像解析手段と、
前記画像解析手段によって抽出された前記文字間隔ごとに、それぞれの前記文字間隔に割り当てる情報に応じた値に所定の定数を乗じ、更に所定の値を加算した値をそれぞれの前記文字間隔の文字間隔長とする文字間隔長変更手段とを有することを特徴とする情報埋め込み装置。
【請求項３４】
前記文字間隔長変更手段は、それぞれの前記文字間隔に割り当てる情報に応じた値に所定の定数を乗じ、更に所定の乱数を加算することを特徴とする請求項３３記載の情報埋め込み装置。
【請求項３５】
前記文字間隔長変更手段は、それぞれの前記文字間隔に割り当てる情報に応じた値に所定の定数を乗じ、更に所定の単位で同一の値が繰り返される数列を構成する値を順番に加算することを特徴とする請求項３３記載の情報埋め込み装置。
【請求項３６】
請求項３３乃至３５いずれか一項記載の情報埋め込み装置によって情報を埋め込まれた文書画像より情報を抽出する情報抽出装置であって、
前記文書画像より行及び文字間隔を抽出する画像解析手段と、
前記画像解析手段によって抽出された前記文字間隔の文字間隔長より前記所定の値を減算し、更に前記所定の定数で除した値に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手段とを有することを特徴とする情報抽出装置。
【請求項３７】
前記情報抽出手段は、前記それぞれの文字間隔長より所定の乱数を減算することを特徴とする請求項３６記載の情報抽出装置。
【請求項３８】
前記情報抽出手段は、前記それぞれの文字間隔長より所定の単位で同一の値が繰り返される数列を構成する値を順番に減算することを特徴とする請求項３６記載の情報抽出装置。
【請求項３９】
前記情報抽出手段は、前記所定の値を減算する前に、前記画像解析手段によって抽出された前記文字間隔の文字間隔長を前記所定の定数で除した剰余の配列と、それぞれの前記文字間隔長より減算すべき前記所定の値の配列とに基づいて、それぞれの前記文字間隔より情報を抽出する順番を特定することを特徴とする請求項３６乃至３８いずれか一項記載の情報抽出装置。
【請求項４０】
文書画像に情報を埋め込む情報埋め込み方法であって、
前記文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔ごとに、それぞれの前記文字間隔に割り当てる情報に応じた値に所定の定数を乗じ、更に所定の値を加算した値をそれぞれの前記文字間隔の文字間隔長とする文字間隔長変更手順とを有することを特徴とする情報埋め込み方法。
【請求項４１】
請求項４０記載の情報埋め込み方法によって情報を埋め込まれた文書画像より情報を抽出する情報抽出方法であって、
前記文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔の文字間隔長より前記所定の値を減算し、更に前記所定の定数で除した値に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手順とを有することを特徴とする情報抽出方法。
【請求項４２】
コンピュータに、
文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔ごとに、それぞれの前記文字間隔に割り当てる情報に応じた値に所定の定数を乗じ、更に所定の値を加算した値をそれぞれの前記文字間隔の文字間隔長とする文字間隔長変更手順とを実行させるための情報埋め込みプログラム。
【請求項４３】
コンピュータに、
請求項４２記載の情報埋め込みプログラムによって情報を埋め込まれた文書画像より行及び文字間隔を抽出する画像解析手順と、
前記画像解析手順において抽出された前記文字間隔の文字間隔長より前記所定の値を減算し、更に前記所定の定数で除した値に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手順とを実行させるための情報抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報埋め込み装置、情報抽出装置、情報埋め込み方法、情報抽出方法、文書画像生成方法、印刷物生成方法、文書画像、印刷物、情報埋め込みプログラム、情報抽出プログラム及び記録媒体に関し、特に文書画像への情報の埋め込み、又は文書画像からの情報の抽出を行うための情報埋め込み装置、情報抽出装置、情報埋め込み方法、情報抽出方法、文書画像生成方法、印刷物生成方法、文書画像、印刷物、情報埋め込みプログラム、情報抽出プログラム及び記録媒体に関する。
【背景技術】
【０００２】
電子透かし技術に代表されるように、従来より、文書画像に任意の情報を人間が容易に視認できない形で埋め込む技術の検討が行われている。例えば、特許文献１には、単語の前後の空白の長さの組み合わせを１つの符号単位とし、前後の長さの比率を署名データのビット値に応じて変化させることで、著作権を保護するための証明データを埋め込む方法が示されている。
【０００３】
また、特許文献２には、前後の文字間隔Ｐ及びＳを用いて、Ｐ−ＳとＰ＋Ｓとの比を量子化することで情報を埋め込む方法が示されている。
【０００４】
更に、特許文献３には、所定数の空白の大小関係のパターンによって情報を埋め込む方法が示されている。
【特許文献１】特開平９−１８６６０３号公報
【特許文献２】特開２００２−２３２６７９号公報
【特許文献３】特開２００４−０２３５６３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１記載の方法は、英文のように単語間に大きな空白がある文書には有効であるが、和文には適用が難しい。また、特許文献１及び２記載の方法は、単語又は文字の前後の空白で一つの情報を表すため、埋め込み可能な情報量が少ないという問題がある。
【０００６】
一方、特許文献３記載の方法によれば、N個の空白を用いてlog2N!ビットという多くの情報を埋め込むことができる。しかしながら、空白の大小関係を変更するためには大きく文字を移動させる必要があり、人間の視覚に不自然さを感じさせる画像になり易いという問題がある。
【０００７】
本発明は、上記の点に鑑みてなされたものであって、文書画像に適切に情報を埋め込むことができ、また、埋め込まれた情報を抽出することができる情報埋め込み装置、情報抽出装置、情報埋め込み方法、情報抽出方法、文書画像生成方法、印刷物生成方法、文書画像、印刷物、情報埋め込みプログラム、情報抽出プログラム及び記録媒体の提供を目的とする。
【課題を解決するための手段】
【０００８】
そこで上記課題を解決するため、本発明は、文書画像に情報を埋め込む情報埋め込み装置であって、前記文書画像より行及び文字間隔を抽出する画像解析手段と、前記画像解析手段によって抽出された前記文字間隔ごとに、当該文字間隔に割り当てる情報に応じて文字間隔長を変更する第一の文字間隔長変更手段と、前記文字間隔長変更手段によって前記文字間隔長が変更された前記行の長さの変化量が所定の基準を満たしているかを判定する判定手段と、前記判定手段によって前記所定の基準を満たしていないと判定された場合に、前記変化量を小さくする方向に前記文字間隔長を変更する第二の文字間隔長変更手段とを有することを特徴とする。
【０００９】
このような情報埋め込み装置では、文字間隔ごとに情報を埋め込むことができるため、比較的多くの情報を埋め込むことができる。また、行の変化量を所定の基準が満たされるように調整するため、見た目の不自然さを小さくすることができる。
【００１０】
また、上記課題を解決するため、本発明は、請求項１１に記載されるように、請求項１乃至１０いずれか一項記載の情報埋め込み装置によって情報を埋め込まれた文書画像より情報を抽出する情報抽出装置であって、前記文書画像より行及び文字間隔を抽出する画像解析手段と、前記画像解析手段によって抽出された前記文字間隔の文字間隔長に基づいて当該文字間隔に埋め込まれた情報を抽出する情報抽出手段とを有することを特徴とする。
【００１１】
このような情報抽出装置では、請求項１乃至１０記載の情報埋め込み装置によって情報を埋め込まれた文書画像より情報を抽出することができる。
【００１２】
また、上記課題を解決するため、本発明は、上記情報埋め込み装置における情報埋め込み方法、文書画像生成方法、印刷物生成方法、前記情報埋め込み方法を前記情報埋め込み装置に実行させるための情報埋め込みプログラム、又は前記情報埋め込みプログラムを記録した記録媒体としてもよい。
【００１３】
更に、上記課題を解決するための、本発明は、上記情報抽出装置における情報抽出方法、前記情報抽出方法を前記情報抽出装置に実行させるための情報抽出プログラム、又は前記情報抽出プログラムを記録した記録媒体としてもよい。
【発明の効果】
【００１４】
本発明によれば、文書画像に適切に情報を埋め込むことができ、また、埋め込まれた情報を抽出することができる情報埋め込み装置、情報抽出装置、情報埋め込み方法、情報抽出方法、文書画像生成方法、印刷物生成方法、文書画像、印刷物、情報埋め込みプログラム、情報抽出プログラム及び記録媒体を提供することができる。
【発明を実施するための最良の形態】
【００１５】
以下、図面に基づいて本発明の実施の形態を説明する。まず、本実施の形態における、文字領域を有する画像（以下「文書画像」という。）への情報の埋め込み方法の概要について説明する。図１は、第一の実施の形態における文書画像への情報の埋め込み方法の概要を説明するための図である。第一の実施の形態においては、文書画像中の各文字間隔を変更する（量子化する）ことにより、それぞれの文字間隔に１ビットの情報を割り当てる。なお、図１において、文字間隔は文字と文字との間の空白部分といった程度の意味として説明するが、文字間隔の詳細については後述される。
【００１６】
図１は、２進数による「０１１」という情報を「文書画像」と記載された行に埋め込む例が示されている。情報を埋め込む前の初期状態として、「文」と「書」、「書」と「画」、「画」と「像」との文字間隔はそれぞれ、ｌ１、ｌ２、ｌ３であるとする（状態（Ａ））。なお、以下において、ｌ１、ｌ２、ｌ３は、各文字間隔の長さ（文字間隔長）を示すと共に、各文字間隔自体を特定する符号として利用する。
【００１７】
「０１１」を埋め込む場合、ｌ１には「０」が、ｌ２には「１」が、ｌ３には「１」が順番に割り当てられる。そして、各文字間隔長は、例えば、割り当てられた値が「０」である場合は、定数ｑの偶数倍に、「１」である場合は、定数ｑの奇数倍に量子化される（状態（Ｂ））。この際、元の文字間隔長に最も近い値に量子化される。すなわち、ｌ１であれば、ｑの偶数倍であってｌ１に最も近い値に量子化される。その結果、各文字間隔の量子化後の行の長さには、各文字間隔が量子化されることによる累積的な変化量（以下「累積誤差」という。）ｅが生じる。この累積誤差ｅは、見た目に不自然さを感じさせるため、所定の条件に合致する文字間隔を、累積誤差ｅを減らす方向に、２ｑ分だけ補正する（状態（Ｃ））。２ｑ分だけ変化させるのは、当該文字間隔とｑとの偶数倍又は奇数倍という関係を維持するためである。なお、図１においては、ｌ２が２ｑ分だけ増加された例が示されている。
【００１８】
次に、上述した方法を用いて文書画像への情報の埋め込みと、文書画像からの情報の抽出とを行う装置について説明する。図２は、本発明の実施の形態における情報埋め込み・抽出装置の機能構成例を示す図である。図２において、情報埋め込み・抽出装置１０は、画像解析部１１、情報埋め込み部１２、量子化部１３、補正部１４、累積誤差判定部１５、印刷部１６、情報抽出部１７、及びスキャン部１８等を有する。
【００１９】
画像解析部１１は、例えば、ＯＣＲ（Optical Character Recognition）の文字領域分割技術等を用いて、文書画像からの文字領域の抽出、抽出された文字領域からの行の抽出、及び抽出された行における文字間隔の抽出等を行う。文字領域分割技術等については、例えば、特許第３２７８４７１号公報及び特許第３２８５６８６号公報等に詳しく説明されている。
【００２０】
量子化部１３は、各文字間隔に埋め込む情報の値に応じて、各文字間隔長について量子化された値を算出する。累積誤差判定部１５は、各行における累積誤差が所定の基準を満たしているかを判定する。所定の基準とは、例えば、所定の閾値以下であること等が相当する。補正部１４は、累積誤差判定部１５によって累積誤差が所定の基準を満たしていないと判定された場合に、所定の条件に合致する文字間隔の文字間隔長を補正することにより、その累積誤差を小さくする。情報埋め込み部１２は、文書画像を操作して、量子化部１３によって算出された値、又は補正部１４によって補正された値に各文字間隔長を変更する。情報抽出部１７は、情報が埋め込まれた画像から当該情報を抽出する。印刷部１６及びスキャン部１８は、情報埋め込み・抽出装置１０に接続されるプリンタ２０やスキャナ３０のドライバソフト等を含む。
【００２１】
図３は、本発明の実施の形態における情報埋め込み・抽出装置のハードウェア構成例を示す図である。図３の情報埋め込み・抽出装置１０は、それぞれバスBで相互に接続されているドライブ装置１００と、補助記憶装置１０２と、メモリ装置１０３と、演算処理装置１０４と、表示装置１０５と、入力装置１０６と等を有するように構成される。
【００２２】
情報埋め込み・抽出装置１０での処理を実現するプログラムは、CD―ROM等の記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、処理対象とする画像データ等を格納する。
【００２３】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。演算処理装置１０４は、メモリ装置１０３に格納されたプログラムに従って情報埋め込み・抽出装置１０に係る機能を実行する。表示装置１０５はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１０６はキーボード及びマウス等で構成され、様々な操作指示を入力するために用いられる。
【００２４】
なお、情報埋め込み・抽出装置１０をネットワークに接続することにより、他の端末からリモートで操作を行ってもよい。この場合、ドライブ装置１００、表示装置１０５及び入力装置１０６等は、当該他の端末が有していればよく、情報埋め込み・抽出装置１０が必ずしも備えている必要はない。
【００２５】
以下、情報埋め込み・抽出装置１０の情報の埋め込み処理の詳細について説明する。図４は、第一の実施の形態における情報の埋め込み処理を説明するためのフローチャートである。
【００２６】
ユーザによって画像データの印刷指示がなされると（Ｓ１０１）、情報埋め込み抽出装置１０の画像解析部１１は、印刷指示の対象となった画像データ（以下「対象画像データ」という。）を読み込み、対象画像データの画像（以下「対象画像」という。）をメモリ装置１０３内に展開する（Ｓ１０２）。ステップＳ１０２に続いてステップＳ１０３に進み、画像解析部１１は、対象画像の文字領域を抽出する。ステップＳ１０３に続いてステップＳ１０４に進み、画像解析部１１は、抽出された文字領域より行を抽出する。なお、対象画像からの文字領域の抽出や、文字領域からの行の抽出は、例えば、ＯＣＲの文字領域分割技術等を用いて行われる。
【００２７】
ステップＳ１０４に続いてステップＳ１０５に進み、画像解析部１１は、各行について文字の高さ方向の黒画素の数の射影ヒストグラムを水平方向とり、黒画素の数が水平方向に連続して０となる区間を「文字間隔」として抽出する。なお、ここで文字間隔は、必ずしも文字と文字との間の空白に限られない。すなわち、黒画素の数が水平方向に連続して０になる区間であれば、例えば、一つの漢字の偏と作りとの間であっても、文字間隔として抽出される。また、対象画像に文字以外の要素、例えば、写真、図、又は表等をも含まれている場合は、これらの各要素間及び各要素内において射影ヒストグラムが連続して０となる区間を文字間隔として抽出してもよい。また、行と行との間も文字間隔として抽出してもよい。
【００２８】
ステップＳ１０５に続いてステップＳ１０６に進み、情報埋め込み部１２は、対象画像に埋め込む情報を、ユーザに入力させる。ここで、入力された情報を、以下「入力情報」という。入力情報は、例えば、テキスト入力領域を有したダイアログ等を表示させることにより入力させてもよい。また、予め、ファイル等に保存されている情報を入力情報としてもよく、この場合、ステップＳ１０６では、当該ファイル等より入力情報を読み込むこととなる。なお、入力情報の値は、２進数による数値を直接入力させてもよいが、例えば、文字列等、人間に理解可能な形式によって入力させてもよい。但し、入力情報の情報量の上限は、抽出された文字間隔の数と同数のビット数となる。
【００２９】
ステップＳ１０６に続いてステップＳ１０７に進み、情報埋め込み部１２は、入力情報の埋め込み対象とする行を一つ選択する。行の選択は、例えば、対象画像の左上からラスタ走査し、検出された順に埋め込み対象としてもよい。なお、選択された行を、以下「カレント行」という。
【００３０】
ステップＳ１０７に続いてステップＳ１０８に進み、量子化部１３等は、カレント行の各文字間隔の長さについて、それぞれの文字間隔に埋め込まれるビット値に応じて量子化又は補正された値（以下「丸め値」という。）を算出する。ステップＳ１０８に続いてステップＳ１０９に進み、情報埋め込み部１２は、対象画像のカレント行における各文字間隔を、量子化部１３等によって算出された丸め値に変更することにより、対象画像に入力情報を埋め込む。
【００３１】
ステップＳ１０９に続いてステップＳ１１０に進み、情報埋め込み部１２は、入力情報を構成する全てのビットが埋め込まれたか否かを判定する。全てのビットが埋め込まれていないと判定された場合、すなわち入力情報を構成するビットの数が、カレント行の文字間隔の数より多い場合は、余ったビットを対象として、ステップＳ１０７以降の処理が実行される。全てのビットが埋め込まれたと判定された場合は、ステップＳ１１１に進み、印刷部１６によって対象画像がプリンタ２０より印刷される。
【００３２】
次に、ステップＳ１０８における、文字間隔の丸め値の算出処理の詳細について説明する。図５は、第一の実施の形態におけるカレント行の各文字間隔の丸め値の算出処理を説明するためのフローチャートである。
【００３３】
量子化部１３は、入力情報を２進数にし（Ｓ１０８−１）、２進数にされた入力情報の各ビット値をカレント行の各文字間隔に１ビットずつ割り当てる（Ｓ１０８−２）。各ビット値の割り当ては、上位ビットから順に、左側の文字間隔から行えばよい。ステップＳ１０８−２に続いてステップＳ１０８−３に進み、量子化部１３は、ビット値が割り当てられた各文字間隔の文字間隔長を、そのビット値に応じて量子化する。すなわち、例えば、割り当てられたビット値が０である場合は、その文字間隔長を定数ｑの偶数倍、又は割り当てられたビット値が１である場合は、その文字間隔長を定数ｑの奇数倍であって、かつ、元の文字間隔長に最も近い値に量子化する。
【００３４】
ステップＳ１０８−３に続いてステップＳ１０８−４に進み、累積誤差判定部１５は、カレント行の累積誤差の絶対値が、閾値θ以下であるか否かを判定する。累積誤差の絶対値がθ以下である場合は、カレント行における処理を終了させる。
【００３５】
一方、累積誤差の絶対値がθより大きい場合は、ステップＳ１０８−５に進み、補正部１４は、累積誤差と同じ方向に量子化された文字間隔であって、これまで補正（後述される）の対象とされていない文字間隔の中で、量子化前の文字間隔長と量子化後の文字間隔長との差（以下「量子化誤差」という。）が最も大きなものの文字間隔長を補正する。ここで、「累積誤差と同じ方向に量子化された文字間隔」とは、量子化誤差の方向が、累積誤差の方向と同じ文字間隔をいい、例えば、累積誤差がマイナスの場合（文字間隔長の量子化によりカレント行全体の長さが小さくなった場合）は、文字間隔長が小さくなった文字間隔をいう。また、「補正」とは、量子化誤差と逆方向に２ｑ分だけ文字間隔長を変更することをいう。すなわち、量子化によって文字間隔長が小さくなった場合は、量子化後の文字間隔長を２ｑ分だけ大きくし、量子化によって文字間隔長が大きくなった場合は、量子化後の文字間隔長を２ｑ分だけ小さくする。
【００３６】
要するに、「累積誤差と同じ方向に量子化された文字間隔」を補正するということは、当該文字間隔について、量子化前後の差（量子化誤差）の拡大をできるだけ小さく抑えつつ、累積誤差を小さくするということになる。
【００３７】
ステップＳ１０８−５に続いてステップＳ１０８−６に進み、補正部１４は、累積誤差と同じ方向に量子化された文字間隔の全てについて補正が行われたか否かを判定する。まだ補正が行なわれていない文字間隔がある場合は、ステップＳ１０８−４以降の処理を繰り返す。一方、累積誤差と同じ方向に量子化された文字間隔の全てについて補正が行われている場合は、ステップＳ１０８−７に進み、累積誤差判定部１５は、補正の結果の累積誤差の絶対値が、θ以下であるか否かを判定する。累積誤差の絶対値がθ以下である場合は、カレント行における処理を終了させる。
【００３８】
一方、累積誤差と同じ方向に量子化された文字間隔の全てについて補正を行っても累積誤差の絶対値がθより大きい場合は、ステップＳ１０８−８に進み、量子化誤差が最小の文字間隔の文字間隔長を補正する。なお、ステップＳ１０８−８の処理は、累積誤差の絶対値がθ以下になるまで繰り返され（Ｓ１０８−７でＮｏの場合）、累積誤差の絶対値がθ以下になるとカレント行に対する丸め値の算出処理が終了する。
【００３９】
図５の処理の結果、カレント行の各文字間隔長について、量子化されたものは量子化後の値が、更に補正されたものは補正後の値が丸め値とされる。なお、上記の処理の結果、累積誤差は、行の右端に生じることになるが、例えば、図５の処理の終了後、行全体をセンタリングすることにより、累積誤差を行の左右に分散させてもよい。
【００４０】
なお、上記において、定数ｑの値は、大きくすると画像の劣化が大きくなり、小さくすると後述される情報の抽出時の抽出精度が劣化するところ、例えば、対象画像が６００ｄｐｉである場合は、７が望ましいことが経験的に知られており、解像度にほぼ比例する。また、奇数であることが望ましい。更に、閾値θは、ｑと同値であることが、画像の劣化を抑えるという観点より望ましい。
【００４１】
次に、図４の処理によって印刷された文書に埋め込まれた情報を抽出する処理について説明する。図６は、第一の実施の形態における情報抽出処理を説明するためのフローチャートである。
【００４２】
例えば、図４の処理によって印刷された文書がスキャナ３０に載置され、スキャンが指示されると、スキャン部１８は、スキャナ３０によって読み取られた文書の画像をメモリ装置１０３に読み込む（Ｓ２０１）。なお、本ステップの処理は、予めスキャンされて補助記憶装置１０２に保存されている画像データの画像をメモリ装置１０３に読み込むものであってもよい。なお、ここでメモリ装置１０３に読み込まれた画像を、以下「入力画像」という。
【００４３】
ステップＳ２０１に続いてステップＳ２０２に進み、画像解析部１１は、入力画像の文字領域を抽出する。ステップＳ２０２に続いてステップＳ２０３に進み、画像解析部１１は、抽出された文字領域より行を抽出する。なお、入力画像からの文字領域の抽出や、文字領域からの行の抽出は、例えば、ＯＣＲの文字領域分割技術等を用いて行われる。ステップＳ２０３に続いてステップＳ２０４に進み、画像解析部１１は、各行について文字の高さ方向の黒画素の数の射影ヒストグラムを水平方向にとり、黒画素の数が水平方向に連続して０となる区間を文字間隔として抽出する。なお、ここでの「文字間隔」は、情報を埋め込む際の文字間隔と同義である。
【００４４】
ステップＳ２０４に続いてステップＳ２０５に進み、情報抽出部１７は、文字間隔の一つを選択し、当該文字間隔を処理対象とする。文字間隔の選択は、例えば、入力画像の左上からラスタ走査し、検出された順に選択してもよい。なお、選択された文字間隔を、以下「カレント文字間隔」という。ステップＳ２０５に続いてステップＳ２０６に進み、情報抽出部１７は、カレント文字間隔の文字間隔長（以下「カレント文字間隔長」という。）から埋め込まれたビット値を判定する。すなわち、カレント文字間隔長を、情報埋め込み時と同じ値である定数ｑで除算し、その商を最も近い整数に丸める。丸められた値が偶数であるときはビット値は「０」、奇数であるときはビット値は「１」であると判定される。
【００４５】
ステップＳ２０６に続いてステップＳ２０７に進み、情報抽出部１７は、埋め込み情報の全てが抽出されたか否かを判定する。この判定は、予め決められた長さのビット列が抽出されたか、抽出されたビット列から終端パターンが検出されたか、又は全ての文字間隔について抽出処理が行われたか等によって行われる。情報の抽出が完了したと判定された場合は、ステップＳ２０５に進み、次の文字間隔を対象としてビット値の抽出が実行される。
【００４６】
一方、情報の抽出が完了したと判定された場合は、ステップＳ２０８に進み、情報抽出部１７は、抽出された情報を所定の出力先に出力する。所定の出力先への出力とは、例えば、表示装置１０５への表示、所定のファイルへの出力、又はプリンタ２０への出力等が相当する。
【００４７】
上述したように、第一の実施の形態における情報埋め込み・抽出装置１０によれば、文字領域を有する画像または文書に対して人間が視認できない、もしくは視認が困難な形で情報を埋め込むことができると共に埋め込まれた情報を抽出することができる。このとき文字間隔に１ビットの情報を割り当てることで、埋め込む情報量を増大させることができる。また、累積誤差を所定の値以下にすることにより、人間の視覚に対する不自然さを減少させることができる。
【００４８】
ところで、第一の実施の形態では、入力情報を２進数化し、各ビット（すなわち、各桁）を、各文字間隔に割り当てる例について説明したが、例えば、入力情報をｎ進数化し、その各桁を各文字間隔に割り当ててもよい。そこで、第二の実施の形態として、第一の実施の形態を一般化した例、すなわち、ｎ進数化された入力情報の各桁を各文字間隔に割り当てる例について説明する。第二の実施の形態において、第一の実施の形態における図４に相当する処理は第一の実施の形態とほぼ同様であり、その違いは自明であるため、以下では、第一の実施の形態における図５に相当する処理、すなわち、丸め値の算出処理について説明する。
【００４９】
図７は、第二の実施の形態におけるカレント行の各文字間隔の丸め値の算出処理を説明するためのフローチャートである。図７に示される処理手順は、図５において説明したものとほぼ同様である。
【００５０】
量子化部１３は、入力情報をｎ進数にし（Ｓ１０８−１１）、ｎ進数にされた入力情報の各桁値をカレント行の各文字間隔に１桁ずつ割り当てる（Ｓ１０８−１２）。各桁値の割り当ては、上位桁から順に、左側の文字間隔から行えばよい。ステップＳ１０８−１２に続いてステップＳ１０８−１３に進み、量子化部１３は、桁値が割り当てられた各文字間隔の長さを、その桁値に応じて量子化する。例えば、（ｎ・ｋ＋ｂ）×ｑで示される値であって、元の文字間隔長に最も近い値に量子化される。ここで、ｋは整数であり、ｂは、割り当てられた桁値である。例えば、ｎ＝３である場合（３進数の場合）は、０、１又は２が各文字間隔に割り当てられることになる。この場合、０が割り当てられた文字間隔長は、３ｋｑ、１が割り当てられた文字間隔長は、（３ｋ＋１）×ｑ、２が割り当てられた文字間隔長は、（３ｋ＋２）×ｑとされ、算出される値が元の文字間隔長に最も近くなるようにｋが定められる。
【００５１】
ステップＳ１０８−１３に続いてステップＳ１０８−１４に進み、累積誤差判定部１５は、カレント行の累積誤差の絶対値が、閾値θ以下であるか否かを判定する。累積誤差の絶対値がθ以下である場合は、カレント行における処理を終了させる。
【００５２】
一方、累積誤差の絶対値がθより大きい場合は、ステップＳ１０８−１５に進み、補正部１４は、累積誤差と同じ方向に量子化された文字間隔であって、これまで補正の対象とされていない文字間隔の中で、量子化誤差が最も大きなものの文字間隔長を補正する。ここで、「補正」とは、量子化誤差と逆方向にｎｑ分だけ文字間隔長を変更することをいう。すなわち、量子化によって文字間隔長が小さくなった場合は、量子化後の文字間隔長をｎｑ分だけ大きくし、量子化によって文字間隔長が大きくなった場合は、量子化後の文字間隔長をｎｑ分だけ小さくする。
【００５３】
ステップＳ１０８−１５に続いてステップＳ１０８−１６に進み、補正部１４は、累積誤差と同じ方向に量子化された文字間隔の全てについて補正が行われたか否かを判定する。まだ補正が行なわれていない文字間隔がある場合は、ステップＳ１０８−１４以降の処理を繰り返す。一方、累積誤差と同じ方向に量子化された文字間隔の全てについて補正が行われている場合は、ステップＳ１０８−１７に進み、累積誤差判定部１５は、補正の結果の累積誤差の絶対値が、θ以下であるか否かを判定する。累積誤差の絶対値がθ以下である場合は、カレント行における処理を終了させる。
【００５４】
一方、累積誤差と同じ方向に量子化された文字間隔の全てについて補正を行っても累積誤差の絶対値がθより大きい場合は、ステップＳ１０８−１８に進み、量子化誤差が最小の文字間隔の文字間隔長を補正する。なお、ステップＳ１０８−１８の処理は、累積誤差の絶対値がθ以下になるまで繰り返され（Ｓ１０８−１７でＮｏの場合）、累積誤差の絶対値がθ以下になるとカレント行に対する量子化処理が終了する。
【００５５】
図７の処理の結果、カレント行の各文字間隔長について、量子化されたものは量子化後の値が、更に補正されたものは補正後の値が丸め値とされる。なお、行全体をセンタリングすることにより、累積誤差を行の左右に分散させてもよいのは第一の実施の形態の場合と同様である。
【００５６】
次に第二の実施の形態における情報抽出処理について説明する。第二の実施の形態における情報抽出処理は、第一の実施の形態におけるもの（図６）とほぼ同様である。但し、ステップＳ２０６の処理が、以下のように異なる。
【００５７】
すなわち、情報抽出部１７は、カレント文字間隔長を、情報埋め込み時と同じ値である定数ｑで除算し、その商を最も近い整数に丸める。更に、丸められた値をｎで除算し、その剰余を埋め込まれた値（桁値）として抽出する。
【００５８】
上述したように、第二の実施の形態における情報埋め込み及び抽出方法によれば、第一の実施の形態に比べて、より多くの情報の埋め込み及び抽出を行うことができる。すなわち、第一の実施の形態における埋め込み方法では、各文字間隔に１ビットずつの情報を埋め込むことができたが、第二の実施の形態における埋め込み方法によれば、各文字間隔にｌｏｇ２ｎビットずつの情報を埋め込むことがでる。但し、ｎの値を大きくすると情報が埋め込まれた画像の視覚的な不自然さが増大する。したがって、ｎの値をユーザが自由に設定できるようにし、文書の性質等に合わせて画質と情報量とのバランスを調節できるようにしてもよい。なお、ｎ＝２とした場合は、第一の実施の形態における埋め込み方法そのものとなる。
【００５９】
ところで、上記においては、画像データに基づいて情報を埋め込む例を説明したが、ワープロソフト等のアプリケーションデータを印刷する際に、本発明に係る情報の埋め込み方法によって印刷物に情報を埋め込んでもよい。そこで、第三の実施の形態として、アプリケーションデータを印刷する際に、情報を埋め込む例について説明する。
【００６０】
図８は、第三の実施の形態における情報の埋め込み処理を説明するためのフローチャートである。図８の処理は、アプリケーションデータが、ワープロソフト等のアプリケーションに読み込まれた状態から開始される。
【００６１】
ユーザが、アプリケーションの印刷メニューを選択すると、印刷部１６におけるプリンタドライバのユーザインタフェース（以下「印刷ダイアログ」という。）が表示される（Ｓ３０１）。ユーザは、印刷ダイアログ上において各種印刷機能の設定を行うと共に、印刷物に情報を埋め込む場合は埋め込む情報を入力し（Ｓ３０２）、印刷の実行を指示する（Ｓ３０３）。なお、ここで埋め込む情報として入力された情報を、以下「入力情報」という。
【００６２】
ステップＳ３０３に続いてステップＳ３０４に進み、プリンタドライバは、アプリケーションデータを印刷先のプリンタ２０が解釈可能な印刷データに変換すると共に、例えば、印刷ダイアログ上で情報の埋め込みを行う旨の設定がされているか否かを判定する。情報の埋め込みを行う旨の設定とは、例えば、印刷ダイアログ上において入力情報が入力されている場合や、又は、情報の埋め込みを行う旨のチェックボタンがチェックされている場合等が相当する。当該設定がされていない場合は、ステップＳ３０６に進み、当該設定がされている場合は、ステップＳ３０５に進む。
【００６３】
ステップＳ３０５において、情報埋め込み部１２等は、プリンタドライバによって生成された印刷データに入力情報を埋め込む。印刷データへの入力情報の埋め込みは、例えば、以下のように行われる。情報埋め込み部１２は、印刷データの中からテキスト部分を抽出する。続いて、各文字の中心座標を抽出し、近傍の文字をまとめて行を生成する。続いて、各行の中で隣接する文字間隔を抽出する。続いて、量子化部１３等は、入力情報を２進数化又はｎ進数化し、第一又は第二の実施例において説明した処理によって各文字間隔の丸め値を算出する。情報埋め込み部１２は、量子化部１３等によって算出された丸め値を実現するように、印刷データ内の各文字の座標値を操作する。
【００６４】
ステップＳ３０５に続いてステップＳ３０６に進み、印刷部１６によって印刷データが印刷される。
【００６５】
上述したように、第三の実施の形態によれば、いわゆるイメージ情報としての画像データに限らず、アプリケーション固有の形式によるアプリケーションデータの印刷物に対しても、本発明に係る情報の埋め込み方法によって情報を埋め込むことができる。なお、図８の処理によって印刷された印刷物からの情報の抽出は、第一又は第二の実施の形態において説明した処理と同様の処理によって行えばよい。
【００６６】
ところで、情報埋め込み・抽出装置１０における機能を、例えば、コピー機等の画像形成装置に実装してもよい。そこで、第四の実施の形態として、画像形成装置に情報の埋め込み機能を実装した例について説明する。
【００６７】
図９は、第四の実施の形態における画像形成装置の機能構成例を示す図である。図９中、図２と同一部分には同一符号を付し、その説明は省略する。図９において、画像形成装置５０は、情報埋め込み・抽出装置１０に実装されているものと同様の画像解析部１１、情報埋め込み部１２、量子化部１３、補正部１４、及び累積誤差判定部１５等を有し、更に、原稿をスキャンし、画像データとして取り込むためのハードウェア（スキャナ５２）と、画像データを印刷するためのハードウェア（プリンタ５１）とを内蔵している。
【００６８】
図１０は、第四の実施の形態における画像形成装置による情報の埋め込み処理を説明するためのフローチャートである。
【００６９】
ステップＳ４０１において、ユーザは、画像形成装置１０のコンタクトガラス又はＡＤＦ（Auto Document Feeder）に原稿をセットする。ステップＳ４０１に続いてステップＳ４０２に進み、ユーザは、画像形成装置１０の操作パネル等において、各種の印刷機能の設定を行うと共に、原稿のコピーに情報を埋め込む場合は埋め込む情報を入力し（Ｓ４０２）、コピーの実行を指示する（Ｓ４０３）。なお、ここで埋め込む情報として入力された情報を、以下「入力情報」という。
【００７０】
ステップＳ４０３に続いてステップＳ４０４に進み、スキャン５２は、原稿をスキャンし、画像データとして読み込む。以下、読み込まれた画像データの画像を「入力画像」という。ステップＳ４０４に続いてステップＳ４０５に進み、画像解析部１１は、例えば、操作パネル上で情報の埋め込みを行う旨の設定がされているか否かを判定する。当該設定がされていない場合は、ステップＳ４０７に進み、当該設定がされている場合は、ステップＳ４０６に進む。
【００７１】
ステップＳ４０６において、情報埋め込み部１２等は、第一又は第二の実施の形態において説明した処理によって、入力情報を入力画像に埋め込む。なお、入力情報が埋め込まれた画像を、以下「情報埋め込み画像」という。ステップＳ４０７に続いてステップＳ４０８に進み、プリンタ５１は、情報埋め込み画像を印刷する。
【００７２】
上述したように、第四の実施の形態における画像形成装置１０によれば、原稿をコピーする際に、コピーとして出力される印刷物に本発明に係る情報の埋め込み方法によって情報を埋め込むことができる。なお、図１０の処理によって印刷された印刷物からの情報の抽出は、第一又は第二の実施の形態において説明した処理と同様の処理によって行えばよい。
【００７３】
なお、第一の実施の形態において説明した、丸め値を算出する手順（図５）は、次の最適化問題を解き、その解を用いて情報を埋め込むことに等しい。
【００７４】
【数１】
2006191520.tif 000003
ここで、nは対象とする行における文字間隔の総数、siはi番目の情報埋め込み後の文字間隔、
2006191520.tif 000004
はi番目の情報埋め込み前の文字間隔、qは量子化単位、biはi番目の埋め込むビット値(0または1)、Zは整数の集合である。
【００７５】
以下、にその解法を示す。
ステップ１：
次式が成り立つか否かを判定する。成り立てばステップ２へ進み、成り立たなければ、解なしで終了する。
【００７６】
【数２】
2006191520.tif 000005
ステップ２：
【００７７】
【数３】
2006191520.tif 000006
ステップ３：
以下の式が成り立つか否かを判定する。成り立てば終了し、成り立たなければステップ４へ進む。
【００７８】
【数４】
2006191520.tif 000007
ステップ４：
【００７９】
【数５】
2006191520.tif 000008
の正負を判定する。正ならばステップ５へ進み、負ならばステップ６へ進む。
ステップ５：
以下の操作を行いステップ３へ進む。
【００８０】
【数６】
2006191520.tif 000009
【００８１】
【数７】
2006191520.tif 000010
ステップ６：
以下の操作を行いステップ３へ進む。
【００８２】
【数８】
2006191520.tif 000011
【００８３】
【数９】
2006191520.tif 000012
閾値の取り方によっては解が存在しない場合が存在するが、その場合でも画像の生成は可能であるので、そのまま処理を進めても、エラー終了させても良い
なお、上記による情報の埋め込みは、情報の埋め込み前後の文字間隔長の差分の二乗和を、累積誤差が閾値以下になるという条件下で最小化することに等しい。以下、その証明を行う。
【００８４】
まず、解の有無の判定について説明する。式（１）の第二・第三の制約式よりsiの最小値は(2−bi)qである。また、siに最大値は存在しない。ところで、式（１）の第一の制約式は次の二つの式に分解できる。
【００８５】
【数１０】
2006191520.tif 000013
【００８６】
【数１１】
2006191520.tif 000014
siの存在域［(2−bi)qi ∞）でこれらの式が満たされれば解が存在する。siの存在域に上限がないことから式（９）が成り立つ。siの下限において式（１０）が成り立てば、解が存在することになる。すなわち、
【００８７】
【数１２】
2006191520.tif 000015
が成り立てば式（１）の最適化問題の解が存在する。
【００８８】
次に、求解法について説明する。制約条件の第一式を緩和すると最適解は、
【００８９】
【数１３】
2006191520.tif 000016
である。
【００９０】
【数１４】
2006191520.tif 000017
のとき、第二の制約式より、kiを１減少させるとsiは2q減少する。このことから、任意のiを選択し、
2006191520.tif 000018
を2q減少させる操作を有限回繰り返せば、第一の制約式を満たすことができる。この操作を行う回数は選択するiによらず一定である。ところで、siが2q減少したときのJ(s)の増分△si-2qJ(s)は、
【００９１】
【数１５】
2006191520.tif 000019
である。すなわち、
【００９２】
【数１６】
2006191520.tif 000020
が最大となるsiを2q減少させる操作を行ったとき、J(s)の増分は最も小さくなる。このことから、
【００９３】
【数１７】
2006191520.tif 000021
として、
【００９４】
【数１８】
2006191520.tif 000022
が最大となるsiに対し、
【００９５】
【数１９】
2006191520.tif 000023
とする操作を第二の制約式が満たされるまで繰り返し実行したとき、最適化問題（１）の最適解が求まる。
【００９６】
【数２０】
2006191520.tif 000024
のとき、第二の制約式より、kiを１増加させるとsiは2q増加する。このことから、任意のiを選択し、
2006191520.tif 000025
を2q増加させる操作を有限回繰り返せば、第一の制約式を満たすことができる。この操作を行う回数は選択するiによらず一定である。ところで、siが2q増加したときのJ(s)の増分△si+2qJ(s)は、
【００９７】
【数２１】
2006191520.tif 000026
である。すなわち、
【００９８】
【数２２】
2006191520.tif 000027
が最小となるsiを2q増加させる操作を行ったとき、J(s)の増分は最も小さくなる。このことから、
【００９９】
【数２３】
2006191520.tif 000028
として、
【０１００】
【数２４】
2006191520.tif 000029
が最小となるsiに対し、
【０１０１】
【数２５】
2006191520.tif 000030
とする操作を第二の制約式が満たされるまで繰り返し実行したとき、最適化問題（１）の最適解が求まる。
【０１０２】
なお、上記をふまえ、図５において説明した丸め値の算出処理は、図１１のように書き直すことができる。図１１は、第一の実施の形態におけるカレント行の各文字間隔の丸め値の算出処理を示す第二のフローチャートである。
【０１０３】
ます、入力情報が２進数にされ（Ｓ５０１）、２進数にされた入力情報の各ビット値がカレント行の各文字間隔に１ビットずつ割り当てられる（Ｓ５０２）。ステップＳ５０３では、式（２）を用いて解の有無が判定される（Ｓ５０３）。解が存在すればステップＳ５０４に進み、解が存在しなければ処理が終了する。
【０１０４】
ステップＳ５０４では、対応付けられたビット値が「０」のときは定数qの偶数倍、「１」のときは定数qの奇数倍で元の文字間隔長に最も近い値に文字間隔長が量子化される。ステップＳ５０４に続いてステップＳ５０５に進み、累積誤差の絶対値がq以下であるか否かが判定される。累積誤差の絶対値がq以下ならば処理が終了し、そうでなければステップＳ５０６へ進む。
【０１０５】
ステップＳ５０６では、累積誤差の正負が判定される。累積誤差が正ならばステップＳ５０７へ、負ならば処理ステップＳ５０８へ進む。ステップＳ５０７では、文字間隔長の符号付変化量が最大の文字間隔が選択され、当該文字間隔長が2q減少させられる。一方、処理ステップＳ５０８では、文字間隔長の符号付変化量が最小の文字間隔が選択され、当該文字間隔長が2q増加させられる。ステップＳ５０７又はＳ５０８に続いてステップＳ５０５以下の処理が繰り返される。
【０１０６】
次に、第五の実施の形態について説明する。第五の実施の形態においては、第一の実施の形態において説明した情報の埋め込み方法について、埋め込まれた情報及び情報が埋め込まれていること自体の秘匿性を向上させる技術について説明する。
【０１０７】
図１２は、第五の実施の形態における文書画像への情報の埋め込み方法の概要を説明するための図である。図１２では図１と同様、２進数による「０１１」という情報を「文書画像」と記載された行に埋め込む例が示されている。情報を埋め込む前の初期状態として、「文」と「書」、「書」と「画」、「画」と「像」との文字間隔はそれぞれ、ｌ１、ｌ２、ｌ３であるとする（状態（Ａ））。なお、ｌ１、ｌ２、ｌ３は、各文字間隔の長さ（文字間隔長）を示すと共に、各文字間隔自体を特定する符号として利用する。
【０１０８】
図１２において、（Ａ）及び（Ｂ）については、図１と同様である。すなわち、ｌ１には「０」が、ｌ２には「１」が、ｌ３には「１」が順番に割り当てられる。そして、各文字間隔長は、例えば、割り当てられた値が「０」である場合は、定数ｑの偶数倍に、「１」である場合は、定数ｑの奇数倍に量子化される（状態（Ｂ））。この際、元の文字間隔長に最も近い値に量子化される。第五の実施の形態では、量子化された文字間隔長のそれぞれに［-q/2,  q/2）の区間の値をとる擬似乱数εを加算する（状態（Ｃ））。図中では、ｌ１にε１が、ｌ２にε２が、ｌ３にε３がそれぞれ加算された例が示されている。各文字間隔長に加算される擬似乱数εの値は同じでもよいし、それぞれ異なっていても良い。情報の秘匿性の向上という観点からは後者の方が好ましい。なお、この後、第一の実施の形態におけるように、累積誤差の補正処理を行ってもよい。
【０１０９】
図１２に示される情報の埋め込み方法を実現する情報の埋め込み処理は、第一の実施の形態における図４及び図５と共通する点が多い。そこで、ここでは、図４及び図５との差分についてのみ説明する。第五の実施の形態では、図５のステップＳ１０８−３における処理が図１３に示される処理に置き換わる。
【０１１０】
図１３は、第五の実施の形態における情報の埋め込み処理を説明するためのフローチャートである。
【０１１１】
図５のステップＳ１０８−２に続いて、量子化部１３は、情報（ビット値）を埋め込む文字間隔を一つ選択する（Ｓ１０８−３ａ）。続いて、量子化部１３は、選択された文字間隔の文字間隔長（以下「カレント文字間隔長」という。）を当該文字間隔に埋め込むビット値に応じて量子化する（Ｓ１０８−３ｂ）。すなわち、例えば、割り当てられたビット値が０である場合は、カレント文字間隔長を定数ｑの偶数倍、又は割り当てられたビット値が１である場合は、カレント文字間隔長を定数ｑの奇数倍であって、かつ、元のカレント文字間隔長に最も近い値に量子化する。
【０１１２】
続いて、量子化部１３は、カレント文字間隔長に［-q/2,  q/2）の擬似乱数を加算する（Ｓ１０８−３ｃ）。続いて、量子化部１３は、カレント行に対する情報の埋め込みが完了したか否かを判定する（Ｓ１０８−３ｄ）。完了していない場合は、次の文字間隔長を処理対象としてステップＳ１０８−３ａ以降の処理が繰り返される。情報の埋め込みが完了した場合は、図５のステップＳ１０８−４以降の処理（累積誤差の補正等）が実行され、情報が埋め込まれた文書が印刷される。
【０１１３】
次に、上述の処理によって印刷された文書に埋め込まれた情報を抽出する方法について説明する。図１４は、第五の実施の形態における情報抽出方法の概要を説明するための図である。
【０１１４】
図１４において、状態（Ａ）は、情報が埋め込まれた状態を示す。状態（Ａ）における各文字間隔長よりビット値を抽出するには、まず、各文字間隔長より擬似乱数εを減算する（Ｂ）。続いて、各文字間隔長を定数ｑで除算することにより得られる商（Ｃ）が、偶数か奇数かによってビット値が判定される（Ｄ）。
【０１１５】
図１４に示される情報抽出方法を実現する情報抽出処理を図１５に示す。図１５は、第五の実施の形態における情報抽出処理を説明するためのフローチャートである。図１５中、図６（第一の実施の形態における情報抽出処理）と同一ステップには同一符号を付し、その説明は省略する。
【０１１６】
図１５では、図６に対してステップＳ２０５ａが追加されている。すなわち、文字間隔長を定数ｑによって除算することによりビット値を判定する（Ｓ２０６）前に、当該文字間隔長より当該文字間隔長に加算された擬似乱数を減算する（Ｓ２０５ａ）。
【０１１７】
上述したように、第五の実施の形態における情報埋め込み・抽出装置１０によれば、情報の埋め込みを行う側と情報抽出を行う側で、情報埋め込み時に各文字間隔長に加算される擬似乱数を秘密裏に共有することで、第三者に対して埋め込み情報の内容、及び情報埋め込みの有無の秘匿性を向上させることができる。
【０１１８】
ところで、印刷及びスキャンといったアナログ処理過程を経ることにより画像が劣化し、情報の埋め込み時に埋め込んだ順番通りに各文字間隔から情報が抽出できないということが考えられる。例えば、情報の埋め込み時には文字間隔として検出された部分が、印刷及びスキャンという処理過程を経ることにより潰れてしまい、情報抽出時に文字間隔として検出されないことにより、抽出されたビット列がずれてしまうといった場合が典型的な例である。
そこで、第六の実施の形態として、第五の実施の形態で用いた擬似乱数を利用して、抽出されたビット列の正当性の検証を行う例を説明する。なお、第六の実施の形態において、情報の埋め込み処理は第五の実施の形態において説明したもの（図１２、図１３）と同様であるとする。
【０１１９】
図１６は、第六の実施の形態における情報抽出処理を説明するためのフローチャートである。
【０１２０】
図１６において、ステップＳ６０１〜Ｓ６０４は、第一の実施の形態における情報抽出処理（図６）のステップＳ２０１〜Ｓ２０４と同じであるため、その説明は省略する。
【０１２１】
ステップＳ６０５において、情報抽出部１７は、抽出された各文字間隔長について、情報の埋め込み時に使用された定数ｑで除算した場合の剰余の列を得る。このとき剰余は［-q/2,  q/2)の区間の値として取る。
【０１２２】
続いて、情報抽出部１７は、各文字間隔長から得られた剰余の列と、情報の埋め込み時に当該各文字間隔長に加算された擬似乱数の列とのマッチングを取る（Ｓ６０６）。マッチングは、例えば、図１７に示される評価関数（１）を制約条件（２）の中で最小とする写像fを求める問題に帰着することができる。
【０１２３】
マッチングを取ることにより、埋め込んだi番目のビットは、f(i)番目として観測されたと判断することができる。このマッチングの問題は全探索で解くことができる。また、データ長が長い場合はメタヒューリスティクスを用いた探索で現実的な時間で解くことができる。なお、評価関数、制約条件の構成は図１７に示したものに限られない。例えば、評価関数については剰余の絶対誤差の和を用いてもよく、また、制約条件についてはレイアウトの状態に依存したもの等を用いてもよい。
【０１２４】
続いて、情報抽出部１７は、マッチングの結果に基づいて情報を抽出する文字間隔の順番を決定し、決定された順番で各文字間隔長に埋め込まれたビット値を判定する（Ｓ６０７）。ビット値の判定処理は、図１４及び図１５で説明した通りである。すなわち、文字間隔長より擬似乱数を減算し、その値を定数qで除算することで得られる商が偶数か奇数かによって判定される。
【０１２５】
ステップＳ６０８は、ステップＳ２０８と同じであるため説明は省略する。
【０１２６】
上述したように、第六の実施の形態における情報埋め込み・抽出装置１０によれば、画像に埋め込まれたビット列が 印刷及びスキャンなどのアナログ処理過程によって乱れた場合であっても、情報の埋め込み時の順番に復元することができる。
【０１２７】
次に、第七の実施の形態として、抽出されたビット列の順番のマッチングの別の例について説明する。
【０１２８】
第七の実施の形態では、情報埋め込み時に擬似乱数列ではなく一定の長さ（以下「単位長」という。）で同じ値が続く数列を用いる。例えば、単位長が４である{0, 0, 0, 0, q/2, q/2, q/2, q/2}を繰り返す数列を用いてもよい。かかる数列を用いて情報の埋め込みを行った場合、ビット列の順番のマッチングは次のように行う。
【０１２９】
まず、各文字間隔長について定数ｑによる剰余を算出する。その剰余の値εが-q/4以上、q/4未満である文字間隔にはラベルＡを、それ以外の文字間隔にはラベルＢを付ける。これを全ての文字間隔に対して行う。そして、抽出された順番に各文字間隔のラベルを調べていき、同じラベルが連続する区間を一つのブロックとする。このブロック単位で情報を抽出し、（１）ビット数が単位長に満たないブロック、又は（２）次のブロックのビット数が単位長と同じであるときに、当該ブロックのビット数が単位長より大きいブロックは誤りがあるものと判断する。なお、情報埋め込み時に誤り訂正符号を埋め込んでおくことにより、誤りのあるビット値を訂正できるようにしてもよい。
【０１３０】
図１８は、抽出されたビット値の誤り検出の具体例を概念的に示す図である。図１８は、量子化単位（定数ｑ）は６、単位長４ビットで各文字間隔にビット値を埋め込んだ画像に対しある種の画像変換（印刷及びスキャン等）を行った後、その画像より抽出された情報について誤り検出を行う例を示す。
【０１３１】
図中（Ａ）は、画像より抽出された各文字間隔の文字間隔長の配列を示す。図中（Ｂ）は、各文字間隔長についての定数ｑ（６）による剰余を示す。上述したように、剰余は［-q/2,  q/2）の区間の値として取られる。したがって、ここでは−３以上２以下の値となる。
【０１３２】
図中（Ｃ）は、剰余に基づいて各文字間隔に付けられたラベルを示す。ここでは、剰余が-6/4以上6/４未満である文字間隔に対してラベルＡが、それ以外に対してラベルＢが付けられる。
【０１３３】
図中（Ｄ）では、同じラベルが連続する区間をブロックとし、そのブロック内のビット数を単位長（４）と比較することにより、ラベルＢが３つしか連続していないブロックにおける誤りが検出されている。
【０１３４】
この方法によれば、（単位長−１）ビットまでの連続誤りに対してその誤り位置を判定することができる。例えば、単位長が４である場合は、３ビットまでの連続誤りに対し、誤り検出能力を有することになる。
【０１３５】
ところで、上記第五の実施の形態において説明した情報の埋め込み方法は、上記第三の実施の形態において説明した、アプリケーションデータを印刷する際の情報の埋め込み処理に適用してもよい。
【０１３６】
この場合、ステップＳ３０５（図８）においてプリンタドライバによって生成された印刷データに情報を埋め込む処理は、以下のように行われる。情報埋め込み部１２は、印刷データの中からテキスト部分を抽出する。続いて、各文字の中心座標を抽出し、近傍の文字をまとめて行を生成する。続いて、各行の中で隣接する文字間隔を抽出する。続いて、量子化部１３等は、入力情報を２進数化又はｎ進数化し、第五の実施の形態において説明した処理によって、擬似乱数εを各文字間隔長に加算することにより各文字間隔の丸め値を算出する。情報埋め込み部１２は、量子化部１３等によって算出された丸め値を実現するように、印刷データ内の各文字の座標値を操作する。
【０１３７】
こうすることで、いわゆるイメージ情報としての画像データに限らず、アプリケーション固有の形式によるアプリケーションデータの印刷物に対しても、第五の実施の形態に係る情報の埋め込み方法によって情報を埋め込むことができる。なお、この場合の情報の抽出及び乱れたビット列の復元等は、第五、六又は第七の実施の形態において説明した処理と同様の処理によって行えばよい。
【０１３８】
本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【図面の簡単な説明】
【０１３９】
【図１】第一の実施の形態における文書画像への情報の埋め込み方法の概要を説明するための図である。
【図２】本発明の実施の形態における情報埋め込み・抽出装置の機能構成例を示す図である。
【図３】本発明の実施の形態における情報埋め込み・抽出装置のハードウェア構成例を示す図である。
【図４】第一の実施の形態における情報の埋め込み処理を説明するためのフローチャートである。
【図５】第一の実施の形態におけるカレント行の各文字間隔の丸め値の算出処理を説明するためのフローチャートである。
【図６】第一の実施の形態における情報抽出処理を説明するためのフローチャートである。
【図７】第二の実施の形態におけるカレント行の各文字間隔の丸め値の算出処理を説明するためのフローチャートである。
【図８】第三の実施の形態における情報の埋め込み処理を説明するためのフローチャートである。
【図９】第四の実施の形態における画像形成装置の機能構成例を示す図である。
【図１０】第四の実施の形態における画像形成装置による情報の埋め込み処理を説明するためのフローチャートである。
【図１１】第一の実施の形態におけるカレント行の各文字間隔の丸め値の算出処理を示す第二のフローチャートである。
【図１２】第五の実施の形態における文書画像への情報の埋め込み方法の概要を説明するための図である。
【図１３】第五の実施の形態における情報の埋め込み処理を説明するためのフローチャートである。
【図１４】第五の実施の形態における情報抽出方法の概要を説明するための図である。
【図１５】第五の実施の形態における情報抽出処理を説明するためのフローチャートである。
【図１６】第六の実施の形態における情報抽出処理を説明するためのフローチャートである。
【図１７】マッチングに使用する評価関数を示す図である。
【図１８】抽出されたビット値の誤り検出の具体例を概念的に示す図である。
【符号の説明】
【０１４０】
１０          情報埋め込み・抽出装置
１１          画像解析部
１２          情報埋め込み部
１３          量子化部
１４          補正部
１５          累積誤差判定部
１６          印刷部
１７          情報抽出部
１８          スキャン部
２０、５１          プリンタ
３０、５２          スキャナ
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        演算処理装置
１０５        表示装置
１０６        入力装置
Ｂ            バス
【図１】
2006191520.tif 000031
【図２】
2006191520.tif 000032
【図３】
2006191520.tif 000033
【図４】
2006191520.tif 000034
【図５】
2006191520.tif 000035
【図６】
2006191520.tif 000036
【図７】
2006191520.tif 000037
【図８】
2006191520.tif 000038
【図９】
2006191520.tif 000039
【図１０】
2006191520.tif 000040
【図１１】
2006191520.tif 000041
【図１２】
2006191520.tif 000042
【図１３】
2006191520.tif 000043
【図１４】
2006191520.tif 000044
【図１５】
2006191520.tif 000045
【図１６】
2006191520.tif 000046
【図１７】
2006191520.tif 000047
【図１８】
2006191520.tif 000048