(57)【要約】【課題】２値画像に埋め込まれた情報をより確実に抽出可能としながら、２値画像へ情報を埋め込むこと。【解決手段】オリジナル２値画像１０１にＮビットで表される埋め込みデータ１０９を埋め込む画像処理装置１００であって、入力したオリジナル２値画像１０１をスキャンし、黒画素の個数が等しくなる位置でオリジナル２値画像１０１を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまでオリジナル２値画像１０１を分割する分割部１０４と、各分割領域毎に、埋め込みデータ１０９の各ビットを埋め込む埋め込み部１０６と、を備えることを特徴とする。【選択図】図１
2009124511.tif 000002
【特許請求の範囲】
【請求項１】
２値画像にＮビットで表される情報を埋め込む画像処理装置であって、
入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割手段と、
各分割領域毎に、前記情報の各ビットを埋め込む埋め込み手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記分割手段は、再帰分割を行なう度に、水平分割、垂直分割を交互に切り替えることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記埋め込み手段は、予め用意された２種類のマスクパターンのうち、埋め込み対象にビットの値で決まる一方のマスクパターンを用いて、該当する分割領域をマスクすること  を特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記分割手段は、前記分割領域毎に含まれる黒画素の個数が、前記マスクパターンを構成する画素の個数以下である場合には、前記２値画像を分割することを禁止することを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記分割手段は、再帰分割を行う際に、水平分割又は垂直分割を一定して行うことを特徴とする請求項１に記載の画像処理装置。
【請求項６】
予め定められた個数の黒画素からなる矩形が前記分割領域毎に存在するか否かを判定する判定手段を更に備え、
前記埋め込み手段は、前記判定手段により、前記矩形が存在しないと判定された場合には、前記分割領域毎に前記情報を埋め込むことを禁止することを特徴とする請求項１に記載の画像処理装置。
【請求項７】
２値画像に埋め込まれたＮビットの情報を抽出する画像処理装置であって、
入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割手段と、
各分割領域毎に、使用されたマスクパターンが、予め設定された２種類のマスクパターンのいずれであるかを判定することで、各分割領域に埋め込まれたビットの値を判定する判定手段と、
該判定手段の判定結果を、埋め込まれた情報として出力する出力手段と、
を備えることを特徴とする画像処理装置。
【請求項８】
前記分割手段は、再帰分割を行なう毎に、水平分割、垂直分割を交互に切り替えることを特徴とする請求項７に記載の画像処理装置。
【請求項９】
前記２値画像に前記マスクパターンを埋め込むことで黒画素が消滅した部位を、前記分割手段により前記２値画像を分割する前に、黒画素に戻すフィルタ手段を更に備えることを特徴とする請求項８に記載の画像処理装置。
【請求項１０】
２値画像にＮビットで表される情報を埋め込む画像処理方法であって、
入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割工程と、
各分割領域毎に、前記情報の各ビットを埋め込む埋め込み工程と、
を有することを特徴とする画像処理方法。
【請求項１１】
２値画像に埋め込まれたＮビットの情報を抽出する画像処理方法であって、
入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割工程と、
各分割領域毎に、使用されたマスクパターンが、予め設定された２種類のマスクパターンのいずれであるかを判定することで、各分割領域に埋め込まれたビットの値を判定する判定工程と、
該判定工程の判定結果を、埋め込まれた情報として出力する出力工程と、
を有することを特徴とする画像処理方法。
【請求項１２】
コンピュータが読込み実行することで、前記コンピュータを、請求項１乃至９のいずれか１項に記載の画像処理装置として機能させることを特徴とするコンピュータプログラム。
【請求項１３】
請求項１２に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２値画像へ情報を埋め込む技術に関するものである。
【背景技術】
【０００２】
文書画像へ情報を埋め込む技術として、例えば、文書画像を等面積で複数の区画に分割し、分割された区画毎に輝度や画素数等の特徴量を変化させる技術がある（特許文献１）。また、文書画像を複数の小区画に分割し、更にその小区画を２つのグループに分割して、一方のグループの特徴量を増やし、他方のグループの特徴量を減らすことにより、透かし情報を埋め込む技術がある（特許文献２）。
【特許文献１】特開２００２−２３２６９８号公報
【特許文献２】特開２００１−７８００６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、特許文献１及び２で開示されている技術は、文書画像を等面積で分割し、その分割された区画に含まれる画素の輝度や数量を調整するため、分割された区画内に画素が存在しない場合がある。このような場合には、情報を埋め込むことができないという問題が生じる。一方、分割された区画内に画素が存在する場合であっても、微量の画素である場合には、情報を抽出可能に埋め込むことができないという問題が生じる。
【０００４】
従って、本発明の目的は、２値画像に埋め込まれた情報をより確実に抽出可能としながら、２値画像へ情報を埋め込むことにある。
【課題を解決するための手段】
【０００５】
本発明においては、２値画像にＮビットで表される情報を埋め込む画像処理装置であって、入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割手段と、各分割領域毎に、前記情報の各ビットを埋め込む埋め込み手段と、を備えることを特徴とする画像処理装置が提供される。
【０００６】
また、本発明においては、２値画像に埋め込まれたＮビットの情報を抽出する画像処理装置であって、入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割手段と、各分割領域毎に、使用されたマスクパターンが、予め設定された２種類のマスクパターンのいずれであるかを判定することで、各分割領域に埋め込まれたビットの値を判定する判定手段と、該判定手段の判定結果を、埋め込まれた情報として出力する出力手段と、を備えることを特徴とする画像処理装置が提供される。
【０００７】
また、本発明においては、２値画像にＮビットで表される情報を埋め込む画像処理方法であって、入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割工程と、各分割領域毎に、前記情報の各ビットを埋め込む埋め込み工程と、を有することを特徴とする画像処理方法が提供される。
【０００８】
また、本発明においては、２値画像に埋め込まれたＮビットの情報を抽出する画像処理方法であって、入力した２値画像をスキャンし、黒画素の個数が等しくなる位置で前記２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで前記２値画像を分割する分割工程と、各分割領域毎に、使用されたマスクパターンが、予め設定された２種類のマスクパターンのいずれであるかを判定することで、各分割領域に埋め込まれたビットの値を判定する判定工程と、該判定工程の判定結果を、埋め込まれた情報として出力する出力工程と、を有することを特徴とする画像処理方法が提供される。
【発明の効果】
【０００９】
本発明によれば、文書画像に埋め込まれた情報をより確実に抽出可能としながら、文書画像へ情報を埋め込むことができる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の好適な実施形態について、添付図面を参照して詳細に説明する。
【００１１】
＜第１の実施形態＞
画像処理装置は、２値画像にＮビットで表される情報を埋め込む情報埋め込み装置１００と、情報埋め込み装置１００によって２値画像に埋め込まれたＮビットの情報を抽出する情報抽出装置３００と、を備える。
【００１２】
［情報埋め込み装置１００について］
図１は、本発明の第１の実施形態に係る情報埋め込み装置１００の機能構成図である。図５（ａ）及び（ｂ）は、マスクパターンの一例を示す図である。
【００１３】
情報埋め込み装置１００は、画像入力部１０２、黒画素数集計部１０３、分割部１０４、埋め込み順序決定部１０５、埋め込み部１０６、最大埋め込み容量算出部１０７、埋め込み可能性判定部１０８、及び表示部１１１を備える。
【００１４】
画像入力部１０２は、各画素が２値（０又は１）のデジタル画像で表現されたオリジナル２値画像１０１を入力する。
【００１５】
黒画素数集計部１０３は、指定領域内の黒画素数を集計する。分割部１０４は、入力したオリジナル２値画像１０１をスキャンし、黒画素の個数が等しくなる位置で２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで２値画像を分割する。なお、黒画素数集計部１０３及び分割部１０４の詳細については後述する。
【００１６】
埋め込み順序決定部１０５は、分割された各領域について、ビット列の各ビットを埋め込む順序を決定する。埋め込み部１０６は、各分割領域毎に、埋め込むべき情報である埋め込みデータ１０９の各ビットを埋め込む。埋め込み部１０６は、本実施形態では、埋め込み部は、予め用意された２種類のマスクパターンのうち、埋め込み対象にビットの値で決まる一方のマスクパターンを用いて、該当する分割領域をマスクする。すなわち、埋め込みデータ１０９、分割された２値画像、及び各ビットの埋め込み順序に基づいて、分割された各領域の黒画素部分にマスクパターンを埋め込む。例えば、埋め込みデータ１０９が０の場合には、図５（ａ）で示すマスクパターンを埋め込み、埋め込みデータ１０９が１の場合には、図５（ｂ）で示すマスクパターンを埋め込むこととする。
【００１７】
更に、詳細に説明すれば、後述する３つの画像の論理積（ＡＮＤ）を算出した画像を生成し、生成された複数の画像の論理和（ＯＲ）を算出した画像を埋め込み済み画像１１０として出力する。ここで、３つの画像とは、図５で示すマスクパターンで形成した画像（透かし画像）、入力画像、及び埋め込み対象領域を表す画像（埋め込み対象領域の画素値が１で、それ以外が０である、入力画像と同一の大きさの画像）を言う。
【００１８】
なお、マスクパターンは、埋め込まれた情報が０又は１であることを判定できるものであれば足りるため、図５で示すマスクパターンに限定されるものではない。
【００１９】
最大埋め込み容量算出部１０７は、情報を埋め込み可能な最大容量（ビット長）を算出する。例えば、入力画像の黒画素数の合計値をマスクパターンで表現するために必要な画素数（図５で示すマスクパターンの場合には９）で割り、商ｘを求める。ここで算出された商ｘ（例えば、１０００）を埋め込み可能なビット数（最大埋め込み容量Ｃ）とする。なお、最大埋め込み容量Ｃは、分割回数をｎとすると、２ｎに制限されるため、ｘ＞＝２ｎを満たし、ｎの最大値を取る場合の２ｎビットとなる。
【００２０】
例えば、マスクパターンを図５（ａ）又は（ｂ）で示すものとした場合には、必要な画素数は９である。この場合において、入力画像の黒画素数の合計値を９０００とした場合には、商ｘが１０００となる。１０００＞＝２ｎを満たすｎの最大値は９であるため、最大埋め込み容量Ｃは、２９と算出することができる。
【００２１】
埋め込み可能性判定部１０８は、入力画像に対して、入力された埋め込みデータ１０９を埋め込み可能であるか否かを、最大埋め込み容量Ｃと、埋め込みデータ１０９のビット長とを比較することにより判定する。すなわち、最大埋め込み容量Ｃのビット長が埋め込みデータ１０９のビット長以上である場合には、埋め込み可能であると判定し、最大埋め込み容量のビット長が埋め込みデータ１０９のビット長未満である場合には、埋め込み不可能であると判定する。
【００２２】
表示部１１１は、本実施形態においては、埋め込み可能性判定部１０８での判定結果を表示し、ユーザに通知する。
【００２３】
（黒画素数集計部１０３及び分割部１０４の詳細について）
分割部１０４では、本実施形態では、再帰分割を行なう度に、水平分割、垂直分割を交互に切り替える。すなわち、再帰分割された各領域に含まれる黒画素の個数が等しくなるように、垂直線分又は水平線分を設定する。このような処理を複数回繰り返して、２値画像をＮ個の領域に分割する。なお、ここで言う線分とは、太さが０で、各ピクセル間を通過するものである。
【００２４】
すなわち、１回目の領域分割時には、１つの画像である入力画像全体を分割対象とするが、ｎ回目の領域分割時には、ｎ−１回目に分割された領域数（２ｎ−１個の領域）の画像を分割対象とする。
【００２５】
しかしながら、２つの領域に分割する際、１つの線分で左右又は上下の領域に含まれる黒画素の個数が完全に等しくなるように分割することが不可能である場合があり得る。このような場合、次のように、分割後の各領域に含まれる黒画素の個数の差が可能な限り小さくなるように線分を定める。すなわち、分割回数が奇数の場合には、垂直線分で左右に領域を分割し、分割回数が偶数の場合には、水平線分で上下に領域を分割する。
【００２６】
なお、垂直線分、水平線分のいずれの線分で領域を分割するかは、情報埋め込み装置１００と情報抽出装置３００との間で、共通の線分を用いればよいため、いずれの線分を選択しても構わない。
【００２７】
図６（ａ）及び（ｂ）は、黒画素数集計部１０３の処理手順を示す図である。まず、図６（ａ）で示すように、垂直線分で左右に領域を分割する場合には、黒画素数を集計する際に、左上の画素から下方へピクセル単位でスキャンする。その後、１列分のスキャンが終了した場合には、その列の右隣の列に移動して、再度下方へスキャンする。黒画素数集計部１０３は、係る処理を繰り返して分割された各領域に含まれる黒画素数を集計する。
【００２８】
集計された黒画素数が分割前の領域に含まれる黒画素数の半分に達した際に、その列にある黒画素数の半分以上にスキャンが進んでいる場合には、その列を含む左方の領域と、その列より右方の領域と、に分割する。一方、集計された黒画素数が分割前の領域に含まれる黒画素数の半分以上に達した際に、その列にある黒画素数の半分以上までスキャンが進んでいない場合には、その列を含む右方の領域と、その列より左方の領域と、に分割する。
【００２９】
また、水平線分で上下に領域を分割する際も同様に説明することができる。図６（ｂ）で示すように、黒画素数を集計する際には、先頭行の左上の画素からピクセル単位で左から右へスキャンする。その領域の右端まで達した場合には、１つ下の行に移って、左から右へスキャンするという処理を繰り返して２値画像全体に含まれる黒画素数を集計する。
【００３０】
集計された黒画素数が、分割前の領域に含まれる黒画素数の合計の半分に達した際に、その行にある黒画素数の半分以上にスキャンが進んでいる場合には、その行を含む上方の領域と、その行より下方の領域と、に分割する。一方、その行にある黒画素数の半分以上までスキャンが進んでいない場合には、その行より上方の領域と、その行を含む下方の領域と、に分割する。
【００３１】
このように、本実施形態では、分割された各領域に含まれる黒画素数の差が可能な限り小さくなるように、集計された黒画素数が集計する領域の黒画素数合計の半分に達した際における集計状態（スキャナの位置）に基づいて、分割境界線を定めることとする。
【００３２】
（領域分割の終了条件について）
領域分割処理は、本実施形態では、埋め込みデータ１０９のビット数の分だけ行う。すなわち、分割回数は、埋め込みデータ１０９のビット数をｎビットとした場合、２ｎ＞＝ｘ’（ｎは自然数)を満たすｎの最小値とする。例えば、埋め込みデータ１０９のビット数が８ビットである場合には、分割を３回行う。
【００３３】
（埋め込み順序決定部１０５の詳細について）
次に、上述の処理により、複数の領域に分割された各領域に、どのように埋め込みデータ１０９の各ビットを割り振るかについて説明する。
【００３４】
各領域が同一の形状・大きさで格子状に分割される場合には、単にラスタ走査の順序に応じて、ビット列の各ビットを埋め込む順序を決定すればよい。しかしながら、上述のように分割した場合には、分割された領域の位置関係が２値画像の内容により異なる。このため、入力された２値画像の内容に応じて、ビット列の各ビットを埋め込む順序を決定する必要がある。そこで、本実施形態では、図７で示すような樹形図を用いて、分割された各領域にビット列の各ビットを埋め込む順序を決定する。
【００３５】
図７は、樹形図の一例を示す図であり、図８は、埋め込み順序決定部１０５の処理手順の一例を示す図である。樹形図の各ノードは、２値画像の全体領域又は分割領域を表す。親ノードに対する子ノードは、親ノードが有する領域を分割した領域である。
【００３６】
１回目の分割の際には、上下方向に延びる線分により、２値画像全体を左右に２つの領域に分割する。この際、上下方向に延びる線分で分割された左右の領域内に含まれる黒画素数が略同一となるように分割する。分割された右側の領域を右側の子ノードで表し、左側の領域を左側の子ノードで表す。領域の分割が終了し、ビット列の各ビットを埋め込む場合には、各領域の順序は、子ノードを左から右へ手繰る順序で与えられる。なお、図８で示す矩形内の各番号は、ビット列の各ビットを埋め込む順序を意味する。
【００３７】
２回目の分割の際には、垂直線分により、１回目の分割により分割された２つの領域を更に上下に２つの領域に分割する。この際、垂直線分で分割された上下の領域内に含まれる黒画素の個数が等しくなるように分割する。
【００３８】
樹形図では、分割された上側の領域を右側の子ノードで示し、分割された下側の領域を左側の子ノードで示す。ここで、分割が終了して埋め込みデータ１０９の各ビットを埋め込む場合には、各領域への埋め込み順序は、前述と同様にノードを左から右へ手繰る順序で与えられる。
【００３９】
３回目以降の分割の際にも同様に、埋め込みデータ１０９の各ビットを埋め込むために各領域の埋め込み順序を決定する。
【００４０】
このような手順により、図８で示すように、埋め込みデータ１０９の各ビットを埋め込むために与えられる各領域の埋め込み順序を１通りに決定することができる。また、埋め込みデータ１０９の各ビットを埋め込む順序は、ＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）からＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）まで数えるものとし、各領域の埋め込み順序と対応付ける。
【００４１】
その際、埋め込みデータ１０９のビット数よりも分割により得られた領域の数（２ｎ（ｎは分割回数））が大きい場合には、埋め込みデータ１０９のビット列の各ビットが対応しない領域に０又は１を割り当てる。
【００４２】
（情報埋め込み装置１００の動作手順）
図２は、情報埋め込み装置１００の動作手順を示すフローチャートである。まず、ステップＳ２０１において、画像入力部１０２から２値画像が入力される。次に、ステップＳ２０２において、ビット列で表現される埋め込みデータ１０９を入力し、入力された埋め込みデータ１０９が埋め込み部１０６に送信される。なお、埋め込みデータ１０９は、ＲＯＭ、ＲＡＭ等に予め記憶されたものを用いてもよいし、入力された２値画像毎にユーザが入力してもよい。
【００４３】
次に、ステップＳ２０３において、最大埋め込み容量算出部１０７が、埋め込みデータ１０９に基づいて、最大埋め込み容量Ｃを算出する。その後、ステップＳ２０４において、埋め込み可能性判定部１０８が、埋め込みデータ１０９のビット列に含まれる全てのビットを２値画像に埋め込み可能であるか否かを判定する。すなわち、分割された領域数よりもビット列に含まれるビット数の方が大きいか否かを判定することとなる。
【００４４】
ステップＳ２０４で埋め込み可能であると判定された場合には、ステップＳ２０５において、分割部１０４が２値画像を複数の領域に分割する。次に、ステップＳ２０６において、埋め込み順序決定部１０５が、埋め込みデータ１０９の各ビットを分割された複数の領域に埋め込む順序を決定する。その後、ステップＳ２０７において、埋め込み部１０６が、埋め込み順序に従って、埋め込みデータ１０９の各ビットに対応するマスクパターンを分割された各領域に埋め込み、ステップＳ２０８において、埋め込み済み画像を出力して一連の処理を終了する。
【００４５】
一方、ステップＳ２０４で埋め込み不可能であると判定された場合には、埋め込み不可能である旨を表示部１１１に表示して、ユーザに通知した後、一連の処理を終了する。
【００４６】
［情報抽出装置３００について］
図３は、第１の実施形態に係る情報抽出装置３００の機能構成図である。情報抽出装置３００は、画像入力部３０２、黒画素数集計部３０３、分割部３０４、判定部３０５、埋め込み順序推定部３０６、及び出力部３０７を備える。
【００４７】
画像入力部３０２は、上述の情報埋め込み装置１００によって、情報が埋め込まれた埋め込み済み２値画像３０１を入力する。黒画素数集計部３０３は、指定領域内の黒画素数を集計する部分であり、上述した情報埋め込み装置１００と同様の構成である。
【００４８】
分割部３０４は、黒画素の個数が等しくなる位置で２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返し、少なくともＮ個の分割領域が確保されるまで２値画像を分割する部分であり、同様の構成である。また、分割部３０４は、再帰分割を行なう毎に、水平分割、垂直分割を交互に切り替える点も情報埋め込み装置１００と同様である。一方、分割回数は、埋め込みデータ１０９のビット長に応じて決定する点で情報埋め込み装置１００とは異なる。
【００４９】
このビット長は、情報埋め込み装置１００で埋め込まれた情報であるビット列の長さであり、情報抽出装置３００は、情報埋め込み装置１００で埋め込まれたビット数を共有する。例えば、情報埋め込み装置１００と同様、ビット長をｘとした場合には、２ｎ＞＝ｘを満たす自然数の最小値を分割回数とする。
【００５０】
判定部３０５は、各分割領域毎に、使用されたマスクパターンが、予め設定された２種類のマスクパターンのいずれであるかを判定することで、各分割領域に埋め込まれたビットの値を判定する。この際、最終的な分割結果である各領域毎に、図５（ａ）及び（ｂ）で示すマスクパターン間でコンボリューション（畳み込み）演算して、その結果得られた画像から所定の演算式により演算される値を類似度とする。所定の演算式としては、例えば、結果画像の画素値の平均値を算出する演算式が挙げられ、この場合には、結果画像の画素値の平均値が類似度となる。類似度が高いマスクパターンが示す情報（０又は１）を各領域に埋め込まれた情報として出力する。
【００５１】
埋め込み順序推定部３０６は、情報埋め込み装置１００で分割された各領域に情報が埋め込まれた順序を推定する。出力部３０７は、判定部３０５による判定結果をビット列で表現される埋め込まれた情報、すなわち、電子透かしデータ３０８として出力する。
【００５２】
（情報抽出装置３００の動作手順）
図４は、情報抽出装置３００の動作手順を示すフローチャートである。情報抽出装置３００は、ステップＳ４０１において、分割部３０４が２値画像を複数の領域に分割する。次に、ステップＳ４０２において、埋め込み順序推定部３０６が、情報埋め込み装置１００でマスクパターンが分割された各領域に埋め込まれた順序を推定する。
【００５３】
その後、ステップＳ４０３において、判定部３０５が分割された各領域に埋め込まれたマスクパターンを抽出する。すなわち、分割された各領域に埋め込まれたマスクパターンを識別することにより、各領域に割り当てられたビットをステップＳ４０２で推定された順序に従って抽出する。
【００５４】
次に、ステップＳ４０４において、出力部３０７が抽出された情報（０又は１で表現されたビット列）を出力する。
【００５５】
以上述べた通り、本実施形態によれば、情報埋め込み装置１００の分割部１０４が、黒画素の個数が等しくなる位置で２値画像を２分割し、２分割したそれぞれの画像についての分割処理を再帰的に繰り返す。このため、分割された領域に黒画素が含まれない状態を回避することができる。これにより、情報抽出装置３００では、２値画像に埋め込まれた情報をより確実に抽出することが可能となる。
【００５６】
また、本実施形態によれば、この再帰分割は、少なくとも埋め込みデータ１０９のビット数が確保されるまで行われるため、埋め込みデータ１０９の容量に限定されることなく、情報を確実に埋め込むことができる。
【００５７】
なお、本実施形態では、１度の分割につき、２つの領域に分割したため、各領域への埋め込み順序を決定する際には、２分木を用いることとしたが、１度の分割につき、ｍ（ｍは３以上の自然数）個の領域に分割する場合には、ｍ分木を用いることとしてもよい。この場合には、２値画像を１度の分割につき、ｍ個ずつ分割していき、二分木と同様にｍ分木を用いて、分割された各領域に情報を埋め込む順序を決定する。
【００５８】
＜第２の実施形態＞
上述の実施形態では、埋め込むビット数が予め定められていたが、本実施形態では、埋め込むビット数が予め定められていない点で異なる。すなわち、本実施形態では、分割対象領域に含まれる黒画素数に基づいて、埋め込み可能である最大容量を演算した後、ユーザに提示して、埋め込みデータ１０９の入力を促す。
【００５９】
なお、情報埋め込み装置１００及び情報抽出装置３００は、第１の実施形態とほぼ同様であるため、同一の符号を付し、説明を省略する。ただし、情報埋め込み装置１００は、本実施形態においては、表示部１１１が最大埋め込み容量をユーザに提示するものである点で異なる。また、情報抽出装置３００は、情報埋め込み装置１００で埋め込まれた情報のビット長を共有する点で異なる。
【００６０】
（情報埋め込み装置１００の動作手順）
図９は、第２の実施形態に係る情報埋め込み装置１００の動作手順を示すフローチャートである。まず、ステップＳ９０１において、画像入力部１０２から２値画像が入力される。次に、ステップＳ９０２において、入力された２値画像の黒画素数と抽出に必要な最小限の黒画素数（マスクパターンを構成する画素数）に基づいて、最大埋め込み容量算出部１０７が、最大埋め込み容量を算出する。例えば、入力された画像の黒画素数を抽出時に必要な最小限の黒画素数で割り、その商をｘとし、ｘ＞＝２ｎ（ｎは自然数）を満たすｎの最大値を算出する。この際の２ｎが最大埋め込み容量Ｃとなる。
【００６１】
次に、ステップＳ９０３において、表示部１１１が最大埋め込み容量Ｃを表示し、ユーザへ情報を提示する。その後、ステップＳ９０４において、埋め込みデータ１０９を入力する。次に、ステップＳ９０５において、分割領域毎に含まれる黒画素の個数が、閾値（マスクパターンを構成する画素の個数）より大きいか否かを判定する。ステップＳ９０５で複数の領域毎に含まれる黒画素数が閾値以下（予め定められた個数以下）であると判定された場合には、分割部１０４は、２値画像を複数の領域に分割することを禁止して、一連の処理を終了する。
【００６２】
一方、ステップＳ９０５で複数の領域毎に含まれる黒画素数が閾値より大きいと判定された場合には、分割部１０４は、２値画像を複数の領域に分割することを許可して、ステップＳ９０６において、２値画像を複数の領域に分割する。なお、分割回数は、入力された情報のビット長をｘ’とした時に、２ｎ＞＝ｘ’（ｎは自然数）を満たすｎの最小値とする。
【００６３】
次に、ステップＳ９０７において、埋め込み順序決定部１０５が、分割された各領域にビット列の各ビットを埋め込む順序を決定する。次に、ステップＳ９０８において、埋め込み部１０６が分割された領域毎にマスクパターンを埋め込み、ステップＳ９０９において、情報が埋め込まれた埋め込み済み画像を出力する。
【００６４】
本実施形態によれば、複数の領域毎に含まれる黒画素数がマスクパターンを構成する画素数以下である場合には、２値画像を複数の領域に分割することを禁止するため、分割後にマスクパターンを埋め込むことができない状態を回避することができる。また、情報の埋め込み対象である２値画像の内容（すなわち、領域の分割数）に応じて、埋め込みビット数を任意に決定することができる。これにより、分割数が多い２値画像には、多くの情報を埋め込むことが可能となる。
【００６５】
＜第３の実施形態＞
上述の第１及び第２の実施形態では、２値画像を複数の領域に分割する際に、交互に分割方向を変更したが、本実施形態では、垂直線分、水平線分のいずれか一方のみを用いて、常に一定の分割方向で分割する点で異なる。
【００６６】
なお、装置構成及び動作手順は、第１及び第２の実施形態と同様であるため、同一の符号を付し、説明を省略する。ただし、分割部１０４及び埋め込み順序決定部１０５が次のように異なる。
【００６７】
（分割部１０４の詳細について）
図１０は、第３の実施形態に係る分割部１０４の処理手順の一例を示す図である。分割された各領域の黒画素の個数が等しくなるように分割する点は、第１及び第２の実施形態と同様であるが、その分割方向が一定である点が異なる。黒画素数集計部１０３で黒画素の個数を集計する際には、上下方向へ射影を取って、分割時に黒画素数を集計する。
【００６８】
（埋め込み順序決定部１０５の詳細について）
本実施形態では、ｍ分木（例えば、ｍ＝２）を用いて、情報の埋め込み順序を定める必要はなく、埋め込み処理及び抽出処理で、予め分割方向を一定方向に定めておく。これにより、一意に情報の埋め込み順序を決定することができる。
【００６９】
本実施形態によれば、、列毎の黒画素数を記憶し、毎回の分割の際に再度利用することができるため、第１及び第２の実施形態に比べて、処理量を削減することができる。
【００７０】
なお、本実施形態では、垂直線分のみで２値画像を複数の領域に分割したが、水平線分のみで２値画像を複数の領域に分割しても構わない。また、垂直線分を用いる場合には、左から右、又は右から左と埋め込み順序を定めてもよいし、水平線分を用いる場合には、上から下、又は下から上へと埋め込み順序を定めてもよい。
【００７１】
＜第４の実施形態＞
上述の第１乃至第３の実施形態では、分割された各領域内でマスクパターンを埋め込むための最低限の黒画素数は満たすが、黒画素が分散して配置されている場合には、図５に示すマスクパターンに置き換えるための黒画素の矩形が存在しないことがあり得る。このような状態を回避するため、本実施形態では、次のような工夫を追加する。
【００７２】
図１１は、第４の実施形態に係る情報埋め込み装置１１００の機能構成図である。情報埋め込み装置１１００は、第１乃至第３の実施形態の情報埋め込み装置１００に比べて、分割された各領域に閾値以上の黒画素の矩形が有るか否かを判定する分割結果評価部１１１２を更に備える点で異なる。また、本実施形態の埋め込み可能性判定部１１０８は、分割結果評価部１１１２の評価結果を参照する点で異なる。他の構成については、上述の実施形態と同様であるため、説明を省略する。
【００７３】
図１２は、第４の実施形態に係る情報埋め込み装置１１００の動作手順を示すフローチャートである。本実施形態では、第１及び第２の実施形態の動作手順に、閾値以上の黒画素の矩形が有るか否かを判定する工程（ステップＳ１２０６）を追加する。
【００７４】
ステップＳ１２０１乃至ステップ１２０３の処理工程は、第１及び第２の実施形態と同様であるため、説明を省略する。ステップＳ１２０４において、２ｎ（ｎは分割回数）が最大埋め込み容量Ｃ以下であるか否かを判定する。すなわち、分割された各領域にビット列の各ビットを埋め込み可能であるか否かを判定する。
【００７５】
ステップＳ１２０４で２ｎ（ｎは分割回数）が最大埋め込み容量Ｃ以下でないと判定された場合には、ステップＳ１２１０に進む。一方、ステップＳ１２０４で２ｎ（ｎは分割回数）として与えられる領域分割数が最大埋め込み容量Ｃ以下であると判定された場合には、ステップＳ１２０５において、分割部１１０４が２値画像の領域を分割する。次に、ステップＳ１２０６において、分割された各領域に閾値以上の個数の黒画素からなる矩形が存在するか否かを判定する。すなわち、図５で示すマスクパターンを埋め込む場合には、黒画素が垂直方向と水平方向に３画素分並んで配された矩形が存在するか否かを判定する。
【００７６】
ステップＳ１２０６で黒画素の矩形が存在しないと判定された場合には、ステップＳ１２１０において、マスクパターンを埋め込むことができない旨を表示部１１１１に表示する。その後、分割領域毎に情報を埋め込むことを禁止するため、ユーザに警告して一連の処理を終了する。一方、ステップＳ１２０６で黒画素の矩形が存在すると判定された場合には、ステップＳ１２０７において、各分割領域へのビット列の各ビットの埋め込み順序を決定する。その後の処理に変更はない。
【００７７】
以上述べた通り、本実施形態によれば、表示部１１１１に表示された最大埋め込み容量Ｃに基づいて、ユーザに埋め込みデータ１１０９を入力させることにより、黒画素が分散配置されているような場合であっても、情報を埋め込むことが可能となる。
【００７８】
なお、本実施形態では、図１２で示すように、埋め込み可能であるか否かを２度判定した（ステップＳ１２０４及びステップＳ１２０６）が、変形例に示すように、１度だけ判定するようにしても構わない。
【００７９】
図１３は、第４の実施形態の変形例に係る情報埋め込み装置１１００の動作手順を示すフローチャートである。上述の実施形態では、第１及び第２の実施形態の動作手順に、閾値以上の黒画素の矩形が有るか否かを判定する工程（ステップＳ１３０６）及びそれに関連する工程（ステップＳ１３１０）を追加する。
【００８０】
まず、ステップＳ１２０１において、２値画像を入力する。次に、上述と同様の手順により、ステップＳ１３０２において、最大埋め込み容量Ｃを算出し、その算出結果を表示部１１１１に表示して（ステップＳ１３０３）、ユーザに埋め込みデータ１１０９の入力を促す（ステップＳ１３０４）。ここで、ユーザは、表示された最大埋め込み容量を超えない範囲で埋め込み情報を入力することが要求される。すなわち、表示された最大埋め込み容量以上の埋め込み情報を入力した場合には、表示部１１１１にエラーメッセージを表示して、再入力を促すようにしてもよい。
【００８１】
図１４は、分割結果評価部１１１２による評価処理（ステップＳ１３０６）の詳細な動作手順を示すフローチャートである。まず、ステップＳ１４０１において、分割された領域と黒画素矩形の畳み込み積分を演算し、ステップＳ１４０２において、演算された結果を２値化する。
【００８２】
次に、ステップＳ１４０３において、２値化により得られた黒画素数を集計し、ステップＳ１４０４において、黒画素数が閾値以上であるか否かを判定する。ここで、黒画素矩形とは、マスクパターンを埋め込み可能である最低限の黒画素数を含む矩形を意味する。
【００８３】
本変形例によれば、表示部１１１１に予め表示された最大埋め込み容量Ｃに基づいて、ユーザに埋め込み情報を入力させるため、埋め込みデータ１１０９が最大埋め込み容量Ｃを越えることでマスクパターンが埋め込み不可能となる状態を回避することができる。
【００８４】
＜第５の実施形態＞
上述の第１の実施形態では、情報抽出装置３００で埋め込みデータ１０９を抽出する際には、情報埋め込み装置１００で埋め込まれた情報のビット数が予め把握可能であることを前提として説明した。一方、本実施形態では、情報を埋め込む際に最低限必要な黒画素数を情報埋め込み装置１００と情報抽出装置１５００とで共有する。なお、情報埋め込み装置の構成は、第１の実施形態の情報埋め込み装置１００と同様であるため、同一の符号を付し、説明を省略する。また、本実施形態の情報抽出装置１５００は、第１の実施形態と比べて、次の構成が追加される。
【００８５】
図１５は、第５の実施形態に係る情報抽出装置１５００の機能構成図である。情報抽出装置１５００は、２値画像を複数の領域に分割する前に、２値画像にマスクパターンを埋め込むことで黒画素が消滅した部位を黒画素に戻すローパスフィルタ部１５０３と、マスクパターンを２値化する２値化処理部１５０４と、を更に備える。
【００８６】
また、上述の第１乃至第４の実施形態では、埋め込みデータ１０９のビット列がすべて埋め込み可能となるまで２値画像を分割することとした。一方、本実施形態では、各領域に含まれる黒画素数がマスクパターンを埋め込む際に最低限必要な黒画素の個数以下となるまで分割を繰り返す。この分割の終了条件は、情報埋め込み装置１００及び情報抽出装置１５００のいずれにも該当する。
【００８７】
本実施形態によれば、情報埋め込み装置１００で情報を埋め込む際に用いた最低限必要な黒画素数の情報を情報抽出装置１５００でも共用する。このため、情報を埋め込む際にも、埋め込まれた情報を抽出する際にも、２値画像を複数の領域に分割し、同一の分割結果を得ることができる。これにより、２値画像に埋め込まれた情報をより確実に抽出可能としながら、２値画像へ情報を埋め込むことができる。
【００８８】
＜その他の実施形態＞
なお、本実施形態は、複数の機器（例えば、ホストコンピュータ、インターフェース機器、リーダ、プリンタ等）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、複合機、ファクシミリ装置等）に適用してもよい。
【００８９】
また、本発明は、前述した実施形態の機能を実現するソフトウェアのコンピュータプログラムのコードを記憶したコンピュータ可読記憶媒体（又は記録媒体）を、システム又は装置に供給してもよい。また、そのシステム又は装置のコンピュータ（又はＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読込み実行することに適用してもよい。この場合、記録媒体から読込まれたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本実施形態を構成することになる。また、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）等が実際の処理の一部又は全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【００９０】
さらに、記録媒体から読込まれたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれる。その後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部又は全部を行い、その処理によって前述した実施形態の機能が実現される場合も本発明に含まれることは言うまでもない。
【００９１】
また、本実施形態を上述のコンピュータ可読記憶媒体に適用する場合、その記録媒体には、先に説明したフローチャートや機能構成に対応するコンピュータプログラムのコードが格納されることになる。
【図面の簡単な説明】
【００９２】
【図１】本発明の第１の実施形態に係る情報埋め込み装置１００の機能構成図である。
【図２】情報埋め込み装置１００の動作手順を示すフローチャートである。
【図３】第１の実施形態に係る情報抽出装置３００の機能構成図である。
【図４】情報抽出装置３００の動作手順を示すフローチャートである。
【図５】（ａ）及び（ｂ）は、マスクパターンの一例を示す図である。
【図６】（ａ）及び（ｂ）は、黒画素数集計部１０３の処理手順を示す図である。
【図７】樹形図の一例を示す図である。
【図８】埋め込み順序決定部１０５の処理手順の一例を示す図である。
【図９】第２の実施形態に係る情報埋め込み装置１００の動作手順を示すフローチャートである。
【図１０】第３の実施形態に係る分割部１０４の処理手順の一例を示す図である。
【図１１】第４の実施形態に係る情報埋め込み装置１１００の機能構成図である。
【図１２】第４の実施形態に係る情報埋め込み装置１１００の動作手順を示すフローチャートである。
【図１３】第４の実施形態に係る情報抽出装置３００の動作手順を示すフローチャートである。
【図１４】第４の実施形態に係る情報埋め込み装置１１００の動作手順を示すフローチャートである。
【図１５】第５の実施形態に係る情報抽出装置１５００の機能構成図である。
【符号の説明】
【００９３】
１００  画像処理装置
１０１  オリジナル２値画像
１０４  分割部
１０６  埋め込み部
１０９  埋め込みデータ
【図１】
2009124511.tif 000003
【図２】
2009124511.tif 000004
【図３】
2009124511.tif 000005
【図４】
2009124511.tif 000006
【図５】
2009124511.tif 000007
【図６】
2009124511.tif 000008
【図７】
2009124511.tif 000009
【図８】
2009124511.tif 000010
【図９】
2009124511.tif 000011
【図１０】
2009124511.tif 000012
【図１１】
2009124511.tif 000013
【図１２】
2009124511.tif 000014
【図１３】
2009124511.tif 000015
【図１４】
2009124511.tif 000016
【図１５】
2009124511.tif 000017