(57)【要約】【課題】  文字間隔を操作し透かし情報を誤り訂正符号化し埋め込み、抽出際に印刷やスキャンなどで生じる誤りを考慮し、適切な誤り訂正符号を設定する。【解決手段】  誤り率算出部１０４は、電子文書を解析して得られた正確な文字数やその配置位置の情報と、電子文書から文書画像を生成し、その生成した文書画像から抽出した文字画像で示される文字の数や配置位置とから、その電子文書の誤り率を推定する。誤り訂正符号化パラメータ決定部１０７は、誤り率と透かし情報に基づき、誤り訂正符号化パラメータを決定する。そして、透かし情報埋め込み部１０８は、決定した誤り訂正符号化パラメータで生成した符号化データに従って、電子文書の文字の配置位置を示す記述を調整して、文字間を利用した埋め込み処理を行う。【選択図】  図１
2011023824.tif 000002
【特許請求の範囲】
【請求項１】
文字の間隔を調整することで、文書中に付加情報を埋め込む情報処理装置であって、
文字を文字コードとして記述された電子文書を入力する電子文書入力手段と、
埋め込む付加情報を入力する付加情報入力手段と、
前記電子文書の記述を解析し、当該電子文書の記述に従って文書画像を生成する文書画像生成手段と、
該文書画像生成手段で生成された文書画像を解析して、各文字画像の配置位置を示す情報を抽出し、当該抽出した配置位置情報と、前記電子文書の記述に従った各文字の配置位置情報とに基づき、前記文書画像から情報を抽出する際の誤り率を、推定する誤り率推定手段と、
該誤り率推定手段で推定された誤り率に従って、誤り訂正符号を生成する際のパラメータを決定する符号化パラメータ決定手段と、
該符号化パラメータ決定手段で決定した符号化パラメータに従い、前記付加情報入力手段により入力した前記付加情報から誤り訂正符号化データを生成する符号化データ生成手段と、
生成された符号化データの各ビットの値に従い、前記電子文書の文字の配置位置に関する記述を変更することで、埋め込み後の電子文書を生成する埋め込み手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記誤り率推定手段は、
前記電子文書を解析して得られる各行の文字数と、前記文書画像の各行から得られた文字画像の数とを比較する、或いは、
前記電子文書を解析して得られる各文字の座標と、前記文書画像の文字画像と判定された当該文字画像の座標とを比較する
ことで、前記誤り率を推定することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記符号化パラメータ決定手段における誤り率は、文字間隔が予め設定された閾値以下の既知のテスト文書の誤り率と、前記文書画像の文字間隔が前記閾値以下となる割合との乗算によって推定することを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
更に、前記符号化パラメータ決定手段で決定したパラメータが、誤り訂正能力を有するか否かを判定し、誤り訂正能力を有さない場合には、予め設定された最低限の誤り訂正能力を有するパラメータに変更する更新手段と、
更新後のパラメータによって前記付加情報から生成した符号化データの全てが、前記電子文書に埋め込める情報量を超える場合には、エラー報知する報知手段と
を備えることを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記符号化データ生成手段は、リードソロモン符号を生成することを特徴とする請求項１乃至４のいずれか１項に記載の記載の情報処理装置。
【請求項６】
前記埋め込み手段は、行ごとに、ビットの集まりのシンボルの埋め込み数を算出し、算出した埋め込み数を示す情報と前記付加情報を埋め込むことを特徴とする請求項５に記載の情報処理装置。
【請求項７】
文字の間隔を調整することで、文書中に付加情報を埋め込む情報処理装置の制御方法であって、
電子文書入力手段が、文字を文字コードとして記述された電子文書を入力する電子文書入力工程と、
付加情報入力手段が、埋め込む付加情報を入力する付加情報入力工程と、
文書画像生成手段が、前記電子文書の記述を解析し、当該電子文書の記述に従って文書画像を生成する文書画像生成工程と、
誤り率推定手段が、該文書画像生成工程で生成された文書画像を解析して、各文字画像の配置位置を示す情報を抽出し、当該抽出した配置位置情報と、前記電子文書の記述に従った各文字の配置位置情報とに基づき、前記文書画像から情報を抽出する際の誤り率を、推定する誤り率推定工程と、
符号化パラメータ決定手段が、該誤り率推定工程で推定された誤り率に従って、誤り訂正符号を生成する際のパラメータを決定する符号化パラメータ決定工程と、
符号化データ生成手段が、該符号化パラメータ決定工程で決定した符号化パラメータに従い、前記付加情報入力工程により入力した前記付加情報から誤り訂正符号化データを生成する符号化データ生成工程と、
埋め込み手段が、生成された符号化データの各ビットの値に従い、前記電子文書の文字の配置位置に関する記述を変更することで、埋め込み後の電子文書を生成する埋め込み工程と
を備えることを特徴とする情報処理装置の制御方法。
【請求項８】
コンピュータに読み込ませ実行させることで、前記コンピュータを、請求項１乃至６のいずれか１項に記載の情報処理装置として機能させることを特徴とするコンピュータプログラム。
【請求項９】
請求項８に記載のコンピュータプログラムを格納したことを特徴とするコンピュータが読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字間隔を調整することで文書に情報を埋め込む技術に関するものである。
【背景技術】
【０００２】
近年の電子化技術の発展に伴い、文書も電子化文書として管理され、そのセキュリティ技術が求められている。なかでも電子透かし情報（以下、透かし情報）の埋め込み、抽出する技術が注目されている。埋め込まれた情報は、当然、正しく抽出されなければならない。そこで、誤り訂正符号を用いて、通信路で発生するノイズによる誤りや印刷物の汚れで生じた誤りなどを訂正する方法がある。
【０００３】
例えば、電子文書を画像化した文書画像に対して、文字間隔を操作し透かし情報を埋め込み、抽出する際に誤り訂正符号を用いた方法などが知られている（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１０９１４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、文字間隔の数には限りがあるため、透かし情報の誤り訂正符号化した後の長さ（以下、符号長）を冗長に設定できない。一方で、印刷やスキャンなどで生じる誤りは確実に訂正できる符号長を設定する必要がある。
【０００６】
本発明では、以上の問題を考慮し、文字間隔を操作し透かし情報を誤り訂正符号化し埋め込み、抽出際に印刷やスキャンなどで生じる誤りを考慮し、適切な誤り訂正符号を設定する技術を提供する。
【課題を解決するための手段】
【０００７】
この課題を解決するため、例えば本発明の情報処理装置は以下の構成を備える。すなわち、
文書中の文字の間隔を調整することで、情報を埋め込む情報処理装置であって、
文字を文字コードとして記述された電子文書を入力する電子文書入力手段と、
埋め込む付加情報を入力する付加情報入力手段と、
前記電子文書の記述を解析し、当該電子文書の記述に従って文書画像を生成する文書画像生成手段と、
該文書画像生成手段で生成された文書画像を解析して、各文字画像の配置位置を示す情報を抽出し、当該抽出した配置位置情報と、前記電子文書の記述に従った各文字の配置位置情報とに基づき、前記文書画像から情報を抽出する際の誤り率を、推定する誤り率推定手段と、
該誤り率推定手段で推定された誤り率に従って、誤り訂正符号を生成する際のパラメータを決定する符号化パラメータ決定手段と、
該符号化パラメータ決定手段で決定した符号化パラメータに従い、前記付加情報入力手段により入力した前記付加情報から誤り訂正符号化データを生成する符号化データ生成手段と、
生成された符号化データの各ビットの値に従い、前記電子文書の文字の配置位置に関する記述を変更することで、埋め込み後の電子文書を生成する埋め込み手段とを備える。
【発明の効果】
【０００８】
本発明によれば、文字間隔を操作し透かし情報を誤り訂正符号化し埋め込み、抽出際に印刷やスキャンなどで生じる誤りを考慮し、適切な誤り訂正符号を設定できる。従って、限られた埋め込み箇所に無駄なく透かし情報を埋め込むことができる。
【図面の簡単な説明】
【０００９】
【図１】実施形態の透かし情報埋め込み装置のブロック構成図。
【図２】透かし埋め込み手順を示すフローチャート。
【図３】電子文書の文字数と文書画像の文字切りした数の比較処理を示す図。
【図４】誤り訂正符号化パラメータを決定する手順と具体的な演算内容を示す図。
【図５】透かし情報の埋め込む方法の例を示す図。
【図６】透かし情報の埋め込む方法の例を示す図。
【図７】透かし情報の埋め込む方法の例を示す図。
【図８】図７で埋め込んだ透かし情報を抽出する例を示す図。
【図９】透かし情報抽出装置のブロック構成図。
【図１０】透かし情報抽出手順を示すフローチャート。
【図１１】誤り訂正符号化パラメータを決定する他の手順を示すフローチャート。
【図１２】第３の実施形態が適用するコンピュータのブロック構成図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、本発明に関わる実施形態を詳細に説明する。
【００１１】
［第１の実施形態］
本第１の実施形態では、文書中に埋め込まれた付加情報の抽出時の誤り率を予測し、誤り訂正符号を設定した上でオリジナルとなる電子文書への付加情報を埋め込みを行なう。また、付加情報が埋め込まれた電子文書からその付加情報を抽出する。
【００１２】
＜透かし情報入り文書作成方法＞
図１は、第１の実施形態における透かし情報の埋め込み装置のブロック構成図である。図１に示すように、電子文書入力部１０１は埋め込み対象である電子文書１００を入力する。そして、文書画像生成部１０２は、入力した電子文書の記述を解析並びに解釈し、文書画像（イメージデータ）を生成する。このとき、文書画像生成部１０２は、入力した電子文書から、文字数や文字間隔の値など文字の配置位置に関する情報（配置位置情報）を抽出し、それを後段の誤り率算出部１０４に出力する。文書画像解析部１０３は、生成された文書画像を解析し、生成された文書画像から誤り率を算出するのに必要な情報である文字数や文字間隔の値など配置位置情報を取得する。誤り率算出部１０４は、電子文書１００および文書画像解析部１０３から得た情報から誤り率を推定（算出）する。誤り訂正符号化パラメータ決定部１０７は、透かし情報１０５を誤りなく抽出するために必要な誤り訂正符号のパラメータを決定する。パラメータは例えば、透かし情報の長さである情報長、符号化した後の長さである符号長、訂正能力である。誤り訂正符号化パラメータ決定部１０７は、算出された誤り率、及び、透かし情報入力部１０６より入力される透かし情報（付加情報）１０５に基づいてパラメータを決定する。透かし情報埋め込み部１０８は、決定した誤り訂正符号化パラメータで透かし情報１０５を誤り訂正符号化した誤り訂正符号化データを生成し、それを電子文書１００に埋め込む。最後に、出力部１０９において、透かし情報が埋め込まれた文書（透かし情報入り文書）１１０を出力する。なお、ここでは透かし情報埋め込み部１０８が誤り訂正符号化データ生成部としても機能するものとして説明したが、必ずしも透かし情報埋め込み部１０８と誤り訂正符号化データ生成部は一体である必要はない。
【００１３】
以下、透かし情報入り文書作成の具体的な処理内容を、図１を参照しつつ、図２のフローチャートに従って説明する。
【００１４】
まず、電子文書入力部１０１が、電子文書１００を入力する（Ｓ２０１）。電子文書のフォーマットとしては、テキストファイル、ＰＳ（Ｐｏｓｔ  Ｓｃｒｉｐｔ）やＰＤＦ（Ｐｏｒｔａｂｌｅ  Ｄｏｃｕｍｅｎｔ  Ｆｏｒｍａｔ）などが挙げられる。すなわち、実施形態で言う電子文書とは、少なくとも文字を文字コードで記述している文書である。次に、文書画像生成部１０２は、入力した電子文書１００を解析し、文書画像を生成する（Ｓ２０２）。文書画像を生成する際には、各文字のフォント名やサイズや位置などの記述に従って文書画像を生成することになるので、当然、その文書画像の行数、文字数、文字の間隔などの情報を得ることができる。そこで、後述するように、誤り率算出に必要な情報を、後段の誤り率算出部１０４に出力する。なお、文書画像生成部１０２は、例えばＰＳファイルからＢＭＰ（Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）  Ｂｉｔｍａｐ  Ｉｍａｇｅ）に変換する変換部とする。ただし、これは一例であり、他の形式でも構わない。特に、文書画像のフォーマットとしてはＢＭＰに限らず、ＴＩＦＦ（Ｔａｇｇｅｄ  Ｉｍａｇｅ  Ｆｉｌｅ  Ｆｏｒｍａｔ）などでも構わない。次に、文書画像解析部１０３は、生成された文書画像を解析する（Ｓ２０３）。具体的には、図３の参照符号３０１のように一つ一つの文字の外接矩形のサイズと位置を求めていく。なお、文書画像中の文字の外接矩形を求める技術は、文字認識分野で良く知られているものであり、垂直、又は、水平方向に文書画像を投影し、先ず、各行の位置と高さを判定する。そして、１つの行については、垂直又は水平方向に投影することで各文字の位置と幅を求め、この結果に基づいて文字画像の存在する領域（外接矩形）を切り出す（以下、この処理を文字切りと呼ぶ）。この結果、文書画像における行数、文字数および文字間隔などが算出できる。
【００１５】
誤り率算出部１０４は、文書画像生成部１０２からの電子文書１００の解析結果を示す情報と、文書画像解析部１０３からの文書画像の解析結果の情報を入力し、透かし情報抽出時に想定される誤り率を算出する（Ｓ２０４）。すなわち、誤り率算出部１０４は、埋め込み後の電子文書を印刷した印刷物から、埋め込まれた情報を抽出するたと仮定した場合の誤り率を推定する誤り率推定部として機能する。実施形態では、誤りとしては以下の２種類を考えている。
１．透かし情報が埋め込まれた電子文書で生じる文字切りの誤り。
２．印刷や複写によって発生するノイズや文字の太りによる誤り。
そこで、１．の文字切り誤りの確率は例えば、電子文書１００での文字数と文書画像解析部１０３での解析結果となる文書画像での文字切りした数を比較し、その差異から、[文字切り誤り率]を求める。また、２．のノイズや文字の太りによる誤りの確率は、あらかじめ誤りが発生しやすい文字間隔が狭い場所における誤り率のテストパターンを用いて求めておく。そして、テストパターンの誤り率と文書画像中の文字間隔の狭い箇所の占める割合から[テストデータによる誤り率]を求める。具体的な方法は以下に述べる。
【００１６】
［文字切り誤り率］
文字切り誤り率とは、透かし情報が埋め込まれた電子文書で例えば、図３の参照符号３０１のような「特」という字が「牛」と「寺」という２つの字に分かれて間違って認識される誤りの確率である。なお、誤りには上記とは逆に２つの字が１つの文字として間違って認識されるものも含まれる。この誤りが生じると、埋め込む前の電子文書には存在しなかった「牛」と「寺」の間の文字間隔が生じることになり、結果として透かし情報に誤りが生じる。
【００１７】
文書画像生成部１０２からの情報から、電子文書１００の各行の正確な文字数が得られるので、それを基本に設定する。次に文書画像（イメージデータ）からも各行の文字切りした数が得られ、それと基本設定とを比較することで埋め込みの文字切り誤り率に相当する誤り率を求める。
【００１８】
図３に例を示す。図の左側がＰＳファイルである電子文書であり、図の右側がＢＭＰファイルである文書画像である。全部で３６行あり、１行目から順に３６行目まで各行の文字数を比較する。比較方法は、次式（１）に従え良い。
｜電子文書の文字数−文書画像の文字切りされた文字数｜  …（１）
ここで、｜ｘ｜は実数ｘの絶対値を示している。
【００１９】
図３によると、文書の１行目は｜２０−２０｜＝０、２行目は｜２３−２４｜＝１となる。２行目は参照番号３０１に示す文字切り誤りがあるため、文字数が１個異なることが分かる。そして、全ての行を比較すると、８個異なる。また、電子文書の総文字数は１６００個であり、文書画像の総文字切りされた文字数は１６０４個である。ここで、文字数が異なった数と、電子文書の総文字数と文書画像の総文字切りされた文字数との差分の数が異なることが分かる。これは、１つの文字が２つの文字に分かれたことで１個文字数が増加した行と、２つの文字が１つの文字になったことで1個文字数が減少した行とが混在するためである。従って、文字切り誤り率char_err_rateは文字数の異なる数の合計と電子文書の総文字数を用いて、次式（２）で得られる。
char_err_rate  ＝  文字数の異なる数の合計÷電子文書の総文字数×１００  …（２）
式（２）を用いると、char_err_rate＝８÷１６００×１００＝０．５０％となる。
【００２０】
なお、以上の方法だと厳密な誤り率を算出できない場合がある。例えば、１行で１個文字数が増加する文字切り誤りと、１個文字数が減少する文字切り誤りが同時に発生する場合を想定すると分かりやすい。この場合、行の文字数自体は変化しないので、誤りの数としてカウントされない。
【００２１】
そこで、電子文書の各文字の座標と文書画像の各文字の座標が一致しない数の合計を文字数の異なる数の合計とし、厳密な誤り率を算出する。座標は例えば文字の外接矩形の左下隅の水平座標（Ｘ座標）値を用いる。以下に具体的な方法を説明する。
【００２２】
まず、電子文書には、文字の各座標を示す情報があるのでそれを取得する。例えば、ＰＳファイルなら最初の文字の座標と次の文字までの距離を示す情報があるので、それらを用いて取得する。一方、文書画像も文字切りした場所の画像上の座標を取得する。そして、電子文書の全ての文字で座標を比較し、同じ文字が存在するかを判定する。ここで、電子文書から文書画像を生成する時に発生する座標の誤差を考慮し、例えば、予め設定された画素数以内（例えば１０画素以内）なら同じ文字とする。最後に、一致しない数の合計を用いて、式（２）より文字切り誤り率char_err_rateを求める。
【００２３】
［テストデータによる誤り率］
テストデータによる誤り率を求めるには、先ずあらかじめ誤りが発生しやすい文字だけを使ったテストパターンを作成し、透かし情報の埋め込みおよび抽出を行い、抽出誤り率を算出する。そして、埋め込み対象となる電子文書を画像化した文書画像中の誤りが発生しやすい場所の占める割合と、求めたテストパターンの抽出誤り率とを乗算した結果が、テストデータによる誤りの確率である。
【００２４】
具体的な求め方としては、まずテストパターンでの誤り率を算出する。ここで、埋め込みは、連続する３文字を単位に１ビットを埋め込むものとする。具体的には、その３文字中の１文字目と２文字目の文字間隔Ｐと２文字目と３文字目の間隔Ｓの大小関係を利用して、透かし情報の１ビットを埋め込む。この場合、全てＰ＋Ｓで表わされる合算距離が予め設定した閾値以下（例えば、４画素以下）になる電子文書を作成する。そうすると、文字間隔が狭いと文字間隔の大小関係がつけにくいため、印刷と複写によって文字の太りやノイズが発生するので、簡単に大小関係が逆転して透かし情報に誤りが生じやすい。例えば、実際に埋め込みおよび抽出を行うと複写機を５回経由したテストパターンの抽出誤り率は１５％となる。
【００２５】
なお、この既知のテストパターン（テスト文書）の抽出誤り率や文字間隔の閾値（実施形態では４画素）は、例えば本装置の工場出荷時などの、検査過程でチェックし、それを装置内部に設けられた不揮発性メモリに格納させ保持させるものとする。
【００２６】
次に、埋め込み対象となる電子文書１００を画像化した文書画像中のＰ＋Ｓが閾値以下になる場所の占める割合を求める。図３の文書画像の場合、閾値以下になる箇所が５０個であり、総文字切り数は１６００個とすると、以下になる場所の占める割合は、（５０／１６００）＝０．０３１１となる。
【００２７】
最後に、文書画像中の誤りが発生しやすい場所の占める割合と、求めたテストパターンの抽出誤り率とを乗算するので、テストデータによる誤り率test_err_rateは次式（３）で得られる。
test_err_rate  ＝  テストパターンの抽出誤り率×文書画像中の誤りが発生しやすい場所の占める割合  …（３）
ここで上記例の場合の誤り率test_err_rateは、式（３）に従って、次のように算出される。
test_err_rate＝１５×０．０３１１＝０．４６６≒０．４７％
【００２８】
なお、句読点など文字間隔を変化させると可読性が低下する場所を除外する処理がある場合に、処理誤判定から発生する誤り率も考慮することができる。また、この他の誤り率として透かし情報入り文書を印刷するプリンタのトナーやインクの残量が少ない場合に発生する誤り率も考えられる。これは、例えばトナー残量が少ないと、十分に文字を描画しないことがあるので、文字がかすれてしまう。その結果、文字切り誤りなどが発生し、透かし情報の抽出が誤るというものである。この誤り率はトナー残量をプリンタ側から取得し算出することで可能である。
【００２９】
なお、誤り訂正符号化パラメータを決定する際に使用する誤り率err_rateは上記文字切り誤り率やテストデータによる誤り率など各誤り率一つのみを使用しても良いし、２つ以上を同時に使用しても良い。本実施形態では文字切り誤り率とテストデータによる誤り率の合計値を誤り率err_rateとした。
【００３０】
さて、本実施形態の場合、最終的な誤り率err_rateは次のようになる。
err_rate＝  ［文字切り誤り率］＋［テストデータによる誤り率］
＝  ０．５０＋０．４７＝０．９７≒１．００％
【００３１】
図２のフローチャートの説明に戻る。誤り訂正符号化パラメータ決定部１０７は、上記のようにして算出した誤り率err_rateと、付加情報入力手段としての透かし情報入力部１０６から入力される透かし情報１０５を用いて、誤り訂正符号化パラメータを決定する（Ｓ２０５）。本実施形態では、誤り訂正符号としてリードソロモン符号を用いる。リードソロモン符号は数ビットを一つのシンボルとして、シンボル単位で符号化および訂正を行う。従って、印刷や複写による文字間隔の変化などによる単独で誤りが発生するランダム誤りの他に、集中したノイズなどによる多数の誤りが集中するバースト誤りにも対応できる。リードソロモン符号のパラメータは符号化する前の情報の長さである情報長ｋ、符号化した後の符号の長さである符号長ｎ、訂正できるシンボル数を示す訂正能力ｔの３つである。なお、ｋおよびｎの単位はシンボルである。以下に、本実施形態における誤り訂正パラメータ決定の方法の例を説明する。
【００３２】
[誤り訂正符号化パラメータ決定]
埋め込み方法は、ステップＳ２０６で詳細を説明するが、透かし情報をリードソロモン符号で符号化して行ごとにシンボル単位で埋め込むことを前提とする。本実施形態では、リードソロモン符号のパラメータである情報長ｋ、訂正能力ｔ、符号長ｎを決定する。
【００３３】
まず、情報長ｋは、元の透かし情報量をシンボル内のビット数で割ることで求められる。次式（４）がその例である。
ｋ＝元の透かし情報量÷シンボル内のビット数  …（４）
【００３４】
次に、訂正能力ｔは透かし情報、誤り率err_rateや文字数などから、十分に想定される誤りを訂正でき、かつ符号長が冗長でないように適切に設定する。具体的には、情報量ｋを埋め込むのに必要な行数Ｌ、訂正に必要な行数ＣＬ、行単位の誤りの頻度Ａ、１行の平均シンボル数Ｓのそれぞれを算出し、これらの数値を用いて次式（５）で算出する。
ｔ＝（Ｌ＋ＣＬ）÷Ａ×Ｓ×０．５  …（５）
ここで、式の最後の「０．５倍」は図４（ｂ）の参照符号４０４のように誤る場所の平均は中心であることを考慮したものであり、十分な誤り訂正を考慮する場合は０．５を乗算しなくて良い。
【００３５】
最後に、符号長ｎは情報長ｋおよび訂正能力ｔを用いて、次式（６）で求める。
ｎ＝ｋ＋２×ｔ  …（６）
【００３６】
第１の実施形態における誤り訂正符号化パラメータを決定する手順を図４（ａ）のフローチャートと、その具体例である図４（ｂ）を参照して、誤り訂正符号化パラメータ決定する処理（Ｓ２０５の詳細）の流れを以下に説明する。
【００３７】
まず、誤り訂正符号化パラメータ決定部１０７は、元の透かし情報量が埋め込めるかを判断する（Ｓ２０５ａ）。連続する３文字中の２つの文字間隔の大小関係で１ビットの透かし情報を埋め込んだとき、その３文字の最後の文字を次のビットを埋め込む３文字の先頭文字とすると、文書全体で埋め込める情報量（ビット数）は文字数÷２と概算できる。図４（ｂ）では、文書４０１には１６００文字があるわけであるから、最大で８００ビットの情報が埋め込めることになるので、それを埋め込みたい透かし情報１０５のデータ量（ビット数）と比較する。比較して、文書の総埋め込みビット数が元の透かし情報量以上の場合（ＹＥＳ）は、処理はＳ２０５ｂに進む。このＳ２０５ｂでは、情報量ｋを式（４）に従って算出する。図４（ｂ）では元の透かし情報量が２４０ビットでシンボル内のビット数が８なので情報長ｋ＝２４０／８＝３０シンボルとなる。
【００３８】
一方、比較して、文書の総埋め込みビット数が元の透かし情報量未満の場合（ＮＯ）は、元の透かし情報量を埋め込めないことを示すエラー報知（エラー通知）して、透かし情報入り文書作成の処理をエラー終了する（Ｓ２０５ｃ）。
【００３９】
さて、Ｓ２０５ｄに処理が進んだ場合、情報量ｋを埋め込むのに必要な行数Ｌを、「元の透かし情報量」÷「行の平均の埋め込めるビット数」で算出する。図４（ｂ）では、元の透かし情報量を２４０ビット、行の平均の埋め込めるビット数を２３ビットとして、情報量ｋを埋め込むのに必要な行数Ｌ＝２４０／２３≒１０行となる。
【００４０】
Ｓ２０５ｅにおいて、行単位の誤りの頻度Ａを算出する。これは、何行に１行の誤りがあるかを示すものであり、「文書の全行数÷（総埋め込みビット数×誤り率）」で求める。図４（ｂ）では、全行数を３５行、総埋め込みビット数を８００ビット、誤り率を１．００％として行単位の誤りの頻度Ａ＝３５／（８００×０．０１）≒４となる。
【００４１】
Ｓ２０５ｆにおいて、訂正に必要な行数ＣＬを算出する。これは、埋め込みに必要な行数Ｌで発生する誤りを訂正するのに必要な行数を示すものであり、Ｌ÷行単位の誤りの頻度Ａで求める。図４（ｂ）では、参照符号４０３の黒く塗りつぶした行が訂正に必要な行に該当し、Ｌが１０、Ａが３なので訂正に必要な行数ＣＬ＝１０／３≒３行となる。
【００４２】
Ｓ２０５ｇにおいて、１行の平均シンボル数Ｓを求める。これは、行平均ビット数÷シンボル内のビット数で求める。図４（ｂ）では、１行のシンボル数Ｓ＝２３／８≒３シンボルとなる。
【００４３】
Ｓ２０５ｈにおいて、訂正能力ｔを式（５）で算出する。図４（ｂ）ではＬが１０、ＣＬが３、Ａが３．Ｓが３であるので、訂正能力ｔは次のようになる。
ｔ＝（（１０＋３）／４）×３×０．５≒５
【００４４】
最後のステップＳ２０５ｉにおいて、符号長ｎを式（６）で求める。図４（ｂ）では、情報長ｋが３０、訂正能力ｔが５だから、符号長ｔは次のようになる。
ｔ＝３０＋（２×５）＝４０シンボル
【００４５】
上記のようにして、誤り訂正符号化パラメータ決定部１０７が誤り訂正符号化パラメータを決定すると、透かし情報埋め込み部１０８は電子文書の文字間隔を調整して透かし情報と抽出時に必要な情報を埋め込む（Ｓ２０６）。抽出時に必要な情報とは、例えば訂正能力ｔであり、文書の先頭の箇所に埋め込んでおく。抽出時には、埋め込み時に用いた誤り訂正符号のパラメータがないと復号できないためである。また、誤り率を埋め込んでおき、抽出側でＳ２０５のように訂正能力ｔを求めても良い。これによって、復号に必要な訂正能力ｔを秘匿することができる。一つ一つの情報の埋め込み方法は例えば、隣接する２つの文字間隔ＰとＳの大小関係で透かし情報を埋め込む。透かし情報が０ならＰ＞Ｓになるようにし、透かし情報が１ならＰ＜Ｓとなるようにすれば良い。抽出時には、大小関係で埋め込んだ情報が分かる。
【００４６】
本実施形態では、透かし情報をリードソロモン符号で符号化して行ごとにシンボル単位で上記のようなルールで埋め込む。これによって、行ごとに同期がとれる。また、バースト誤りが行の途中で発生しても次の行には影響しない。具体的に行ごとにシンボル単位で上記のようなルールで埋め込む方法として、以下に[そのまま埋め込む方法]、[各行の初めに行に埋め込めるシンボル数を埋め込む方法]、[各行の余りビットを有効に使う方法]を示す。
【００４７】
［そのまま埋め込む方法］
行の先頭から埋め込めるシンボル数だけ埋め込む方法である。行端のシンボル内のビット数を満たさない場所には埋め込まない。
【００４８】
図５に例を示す。この場合は、透かし情報５０１は３シンボルであり、誤り訂正符号化すると、訂正符号５０２として２シンボル生成される。埋め込み順番は５０１ａ、５０１ｂ、５０１ｃ、５０２ａ、５０２ｂとなる。文書５０３の参照符号５０４で示される２行に埋め込むとすると、行端のシンボル内のビット数を満たさない５０４ｂや５０４ｃを除く、５０４ａのような場所に埋め込まれることが分かる。
【００４９】
［各行の初めに行に埋め込めるシンボル数を埋め込む方法］
行の初めに行に埋め込めるシンボル数を埋め込む方法である。例えば、シンボル数が偶数なら「０」、奇数なら「１」を示す１ビットの情報を埋め込む。これによって、文字切り誤りやノイズなどによるビット増減の発生で行のシンボル数が増減し抽出できなくことを防ぐ。なお、＜そのまま埋め込む方法＞と同様に行端のシンボル内のビット数を満たさない場所には埋め込まない。
【００５０】
図６に例を示す。参照符号６０２ａが示す行の先頭のような場所に行のシンボル数を埋め込む。今回はシンボル数が３なので、奇数を意味する「１」を埋め込む。そのあとは図５と同様に透かし情報５０１の５０１ａ、５０１ｂ、５０１ｃと訂正符号５０２の５０２ａ、５０２ｂが埋め込んでいく。
【００５１】
[各行の余りビットを有効に使う方法]
各行の最後でシンボルのビット数を満たせず余るビットを有効に使う方法である。例えば、数行にまたいで透かし情報を埋め込む場合に、余るビットを使うことで上記の２つの方法よりも１シンボル分多くの透かし情報を埋め込むことができる場合がある。
【００５２】
具体的にはシンボルになるために不足しているビット数を付ける。例えば、シンボルのビット数が４ビットの場合は２ビットを使用して０個なら「００」、１個なら「０１」、２個なら「１０」、３個なら「１１」と示す。そして、透かし情報、不足しているビット数の情報とパディングを加えた符号化用データから訂正符号を生成し、訂正符号を行端以外に埋め込む。
【００５３】
図７に例を示す。透かし情報７０１は３シンボルで構成される。また、埋め込む場所は参照番号７０５であり、１行目の行端はシンボルを構成するのであと２ビット不足している。これを考慮すると、透かし情報７０１ｃは透かし情報７０５ｂと７０５ｃに分けて埋め込む。ここで、透かし情報７０５ｃの後半の部分はパディングする。パディングは例えば、「０」で埋めれば良い。なお、パディングではなく、透かし情報７０１ａの先頭２ビットをもう一回埋め込むことで、透かし情報の抽出率を上げても良い。
【００５４】
符号化用データとしては参照番号７０２で示され、１シンボル目と２シンボル目は透かし情報７０１ａと７０１ｂがそのまま入る。３シンボル目は透かし情報７０１ｃの前半２ビットと１行目の行端の不足しているビット数を２進数にしたもので構成される。今回は２ビットなので「１０」である。４シンボル目は透かし情報７０１ｃの後半２ビットとパディング２ビットで構成される。
【００５５】
以上で説明した符号化データ７０２から誤り訂正符号化すると、訂正符号７０３を生成する。
【００５６】
最後に、生成した訂正符号７０３の７０３ａと７０３ｂが７０５ｃ以降の行端以外に埋め込まれることが分かる。
【００５７】
ここで上記方法を用いた場合の抽出方法も示す。抽出はまず符号長ｎシンボル×シンボル内のビット数を満たすまで情報を抽出する。次に、シンボル内のビット数を満たさない場所にパディングおよび行端の不足しているビット数の情報を付ける。そして、復号したのち、パディングおよび行端の不足しているビット数の情報を除いて透かし情報を抽出する。
【００５８】
図８に例を示す。図８は図７の参照番号７０５で示される２行に埋め込んだ情報を抽出する例である。ただし、１行目の行端のビットが文字切り誤りで１ビット減っている場合である。
【００５９】
まず、図示の参照番号８０１で示すのが抽出データである。そして、参照番号８０２が補正した抽出データである。ここで、３シンボル目の２ビット目がパディングになっている。また、３ビット目および４ビット目の値が３ビット不足していると認識して「１１」になっており、埋め込み時の符号化データ７０２と変化していることが分かる。そして、補正した抽出データ８０２に誤り訂正を行い復号すると、復号データ８０３が生成され、埋め込み時７０２と同じになることが分かる。最後に、復号データ８０３からパディングおよび行端の不足しているビット数の情報を除いて元の透かし情報８０４を抽出することが分かる。
【００６０】
最後に、出力部１０９が埋め込み済み電子文書１１０を出力する。なお、この電子文書１１０をプリンタなどで印刷出力しても良いし、可搬性の電子的記録媒体（ＣＤ−ＲＯＭなど）に格納し出力しても良い。
【００６１】
［透かし情報抽出］
図９は、第１の実施形態における透かし情報の抽出装置のブロック構成図である。図９に示すように、文書入力部９０１は透かし情報を抽出する対象である透かし情報入り文書９００を入力する。なお、情報入り文書９００が紙媒体である場合には、文書入力部９０１はイメージスキャナとなり、情報入り文書９００が電子文書である場合（例えばＰＳファイル）の場合には、その文書を解釈しラスターイメージデータに変換するレンダラで良い。いずれにしても、透かし情報入り文書９００は画像化され文書画像として以降扱われる。文書解析部９０２は、文書画像内の文字間隔や文字数などを取得する。次に、誤り訂正符号化パラメータ推定部９０３において、文書の先頭などに埋め込まれている訂正能力または誤り率や文字数などを用いて誤り訂正符号化パラメータを推定する。
【００６２】
最後に、透かし情報抽出部９０４は、推定された誤り訂正符号化パラメータを元に透かし情報９０５を抽出する。以下、透かし情報抽出方法の具体的な実現方法を、図１０のフローチャートに従って説明する。
【００６３】
まず、文書入力部９０１は透かし情報入り文書９００を入力する（Ｓ１００１）。このときに、文書の媒体が印刷物の場合はスキャナなどで入力され、電子文書ファイルの場合は画像ファイルに変換されるので、これ以降は文書画像として扱われる。次に、文書解析部９０２は、文書入力部９０１から得た文書画像から、その文書画像内の文字間隔や文字数などを取得する（Ｓ１００２）。次いで、誤り訂正符号化パラメータ推定部９０３が、誤り訂正符号化パラメータを推定する。情報長ｋは元の透かし情報量とシンボル内のビット数、符号長ｎは式（６）より情報長ｋと訂正能力ｔで求める。元の透かし情報量の値とシンボル内のビット数の値は透かし情報の抽出装置で保持する。そのため、本第１の実施形態では訂正能力ｔを推定すれば、誤り訂正に必要なパラメータが分かる。訂正能力ｔは例えば、文書の先頭に訂正能力ｔを埋め込まれている場合は訂正能力だけを抽出すれば良い。また、文書の先頭に埋め込み時に想定した誤り率が埋め込まれている場合は、先のステップＳ２０５と同様にして、訂正能力ｔを推定する。
【００６４】
最後に、透かし情報抽出部９０４が、文書画像に埋め込まれている情報を抽出し、誤り訂正符号化パラメータ推定部９０３で推定した誤り訂正符号のパラメータを元に誤り訂正をし、透かし情報９０５を抽出する。なお、誤り訂正できない場合は、推定した誤り訂正符号のパラメータが間違っていたと考え、パラメータの数値を前後に変化させて試すこともできる。例えば、訂正能力ｔが３の場合に訂正できなかったら、ｔを２または４に変更して再度誤り訂正してみる。
【００６５】
なお、本実施形態で述べている文字間隔の操作方法は一例であり、本発明は他の文字間隔を操作した方法でもかまわない。また、いくつかの文書サンプルを本実施形態を用いて埋め込み訂正能力の値に目安がつけることで、訂正能力の値を予め設定し埋め込んでも良い。これによって、誤り率算出および誤り訂正符号化パラメータ決定の大部分の処理を省略でき、埋め込み時の処理を効率化できる。さらに、本実施形態では誤り訂正符号としてリードソロモン符号を用いたが、他の誤り訂正符号を用いても良く、例えばＢＣＨ符号を用いることもできる。
【００６６】
［第２の実施形態］
第１の実施形態では、誤り訂正符号のパラメータを誤り率、元の透かし情報量や文字数などを用いて求めた。しかしながら、決定されたパラメータの一つである訂正能力ｔを用いると、抽出で発生した誤りが訂正できない場合や透かし情報の埋め込み自体ができない場合がある。例えば、算出した誤り率が０に近い場合は訂正能力が０になるので、誤り訂正がない元の透かし情報をそのまま埋め込むことになる。その結果、誤りを訂正できない。また、訂正能力ｔから算出した符号長ｎが文書の総埋め込みビット数を超えている場合は、誤り訂正符号が半端に埋め込まれるため、復号ができなくて透かし情報を抽出できない。
【００６７】
以上を考慮して本第２の実施形態では、決定した訂正能力ｔの値を判定し、訂正能力ｔが０の場合は１に再設定し、総埋め込みビット数を超えている場合は総埋め込みビット数に収まるように再計算する。これによって、最低限の誤り訂正を保証する。以下、具体的な実現方法について述べる。
【００６８】
第１の実施形態と異なるのは誤り訂正符号化パラメータ決定部１０７の誤り訂正符号化パラメータを決定する処理である。すなわち、図２でのステップＳ２０５の詳細が図４（ａ）ではなく、図１１となる点である。それ以外は第１の実施形態と同じであるので、以下では、図１１のフローチャートに従って、誤り訂正符号化パラメータ決定部１０７の処理内容を説明する。
【００６９】
まず、誤り訂正符号化パラメータ決定部１０７は、情報長ｋおよび訂正能力ｔを算出する（Ｓ２０５ｊ）。この処理は、図４（ａ）のＳ２０５ａ乃至Ｓ２０５ｈで表わされるＳ２０５ｊと同じである。訂正能力ｔが０であるかを判断する（Ｓ２０５ｋ）。そして、０の場合（ＹＥＳ）、訂正能力ｔを１に更新する（Ｓ２０５ｌ）。これによって、最低限の誤りを訂正することができる。
【００７０】
こうして、０以外の値を持つ更新後の訂正能力ｔが決定されると、情報長ｋと訂正能力ｔを用いて符号長ｎを算出する（Ｓ２０５ｍ）。この符号長ｎは、図４のＳ２０５ｉと同様に、式（４）に従って求める。
【００７１】
次に、誤り訂正符号化パラメータ決定部１０７は、総埋め込みビット数が符号長ｎ以上かを判断する（Ｓ２０５ｎ）。そして、符号長ｎ以上の場合（ＹＥＳ）は誤り訂正符号化した情報を最低一回は埋め込むことができるので、本処理（Ｓ２０５）を終了する。一方、総埋め込みビット数が符号長ｎより小さい場合（Ｓ２０５ｎがＮＯの場合）は、総埋め込みビット数に収まるように訂正能力ｔを再計算する（Ｓ２０５ｏ）。具体的には、１つのシンボルを訂正するのに２つのシンボルが追加で必要なことを考慮して、（総埋め込みビット数−元の透かし情報量）÷（シンボル内のビット数×２）で求める。ただし、小数点以下は切り捨てである。例えば、総埋め込みビット数が２６０ビット、元の透かし情報量２４０ビット、シンボル内のビット数８ビットならば、（２６０−２４０）÷（８×２）≒１となる。
【００７２】
誤り訂正符号化パラメータ決定部１０７は、再度算出した再度訂正能力ｔが０であるか判断する。そして、０の場合（ＹＥＳ）は、全く誤り訂正できないことを通知し（Ｓ２０５ｑ）、Ｓ２０５の処理を終了する。通知方法は例えば、ディスプレイに表示したり、音声で行う。一方、訂正能力ｔが０ではない場合は、設定よりも誤り訂正能力が低下していることを通知し（Ｓ２０５ｒ）、Ｓ２０５の処理を終了する。
【００７３】
［第３の実施形態］
第３の実施形態では、先に説明した第１の実施形態にかかる処理を、パーソナルコンピュータなどの汎用情報処理装置が実行するコンピュータプログラムで実現する例を説明する。図１２は、この場合のコンピュータの基本構成図である。
【００７４】
コンピュータは、ＣＰＵ１２０１、ＲＡＭ１２０２、ＲＯＭ１２０３、ディスプレイ制御装置１２０４、ディスプレイ１２０５、操作入力デバイス１２０６及びそれを接続するＩ／Ｏ１２０７、外部記憶装置１２０８及びそれを接続するＩ／Ｏ１２０９を有する。また、コンピュータは、プリンタ１２１０及びそれを接続するためのＩ／Ｏ１２１１、イメージスキャナ１２１２及びそれを接続するためのＩ／Ｏ１２１３、他のコンピュータシステム１２１４と接続するためのＩ／Ｏ（ネットワークインタフェース）を有する。そして、これらの構成はシステムバス１２１６を介して、ＣＰＵ１２０１に接続されている。
【００７５】
なお、外部記憶装置１２０８は、例えばハードディスク装置であり、ＯＳ（オペレーティングシステム）、透かし情報埋め込み／抽出にかかるアプリケーションプログラムが格納されている。また、外部記憶装置１２０８は、埋め込み対象の文書データを格納する装置としても利用される。また、プリンタ１２１０は、透かしを埋め込んだ文書を記録紙媒体として出力するために利用し、イメージスキャナ１２１２は透かし情報が埋め込まれた紙媒体の画像を入力するために利用される。
【００７６】
本装置に電源が投入されると、ＣＰＵ１２０１はＲＯＭ１２０３のブートプログラムに従って、外部記憶装置１２０８に格納されたＯＳ（オペレーティングシステム）をＲＡＭ１２０２にロードし、実行する。この結果、キーボードやマウスなどの操作入力デバイス１２０６による入力、並びに、ディスプレイ１２０５への表示が可能になり、本装置が情報処理装置とすて機能することになる。ここで、操作者が、埋め込みアプリケーション、或いは、抽出アプリケーションの起動を指示すると、ＣＰＵ１２０１は該当するアプリケーションプログラムを外部記憶装置１２０８からＲＡＭ１２０２にロードし実行する。この結果、本装置が透かし情報埋め込み装置や透かし情報抽出装置として機能することになる。例えば、透かし情報埋め込み装置として機能する場合、図１の各処理部は、ＣＰＵ１２０１が実行する関数やサブルーチンとして機能することになる。なお、透かし情報を埋め込む対象の電子文書は、ネットワークからダウンロードしても良いし、外部記憶装置１２０８に格納されているものでも構わない。なお、コンピュータプログラムで実現する場合、埋め込むべき付加情報（透かし情報）としては、そのアプリケーションプログラムの認証情報（ユーザ登録時に設定する情報）とすると都合が良い。
【００７７】
なお、上記各実施例は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【００７８】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2011023824.tif 000003
【図２】
2011023824.tif 000004
【図３】
2011023824.tif 000005
【図４】
2011023824.tif 000006
【図５】
2011023824.tif 000007
【図６】
2011023824.tif 000008
【図７】
2011023824.tif 000009
【図８】
2011023824.tif 000010
【図９】
2011023824.tif 000011
【図１０】
2011023824.tif 000012
【図１１】
2011023824.tif 000013
【図１２】
2011023824.tif 000014