(57)【要約】【課題】画質劣化を抑えながら、デジタル画像のトポロジ保存則によって電子透かしを埋め込む。【解決手段】（ｂ）はトポロジが保存された透かし埋め込み画像であり、（ｄ）、（ｆ）はトポロジが保存されない透かし埋め込み画像である。（ｂ）では、原画像のランレングスａの５画素を４画素に縮め、原画像のランレングスｂの１画素を２画素に伸ばし、原画像のランレングスｃの５画素を６画素に伸ばし、ランレングスｄの２画素を１画素に縮め、ランレングスの奇偶値により、透かし情報（０００１）が埋め込まれた画像（ｂ）が生成される。【選択図】図４
2005269617.tif 000002
【特許請求の範囲】
【請求項１】
画像等のデジタルコンテンツを、同一色の画素が連続するランレングスに分解する工程と、前記ランレングスに、トポロジを保存して（以下、第１のトポロジ保存則）電子透かし情報を埋込む工程とを含むことを特徴とする画像処理方法。
【請求項２】
前記第１のトポロジ保存則は、「前記ランレングスの色とは異なる１個以上の色画素を、前記ランレングス中に挿入することによって前記ランレングスを分割」させず、かつ前記ランレングスを消滅させない規則であることを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記デジタルコンテンツをブロックに分割する工程と、前記分割されたブロックの境界部に前記ランレングスがある場合、前記ランレングスに、トポロジを保存して（以下、第２のトポロジ保存則）電子透かし情報を埋込む工程とを含むことを特徴とする請求項１記載の画像処理方法。
【請求項４】
前記第２のトポロジ保存則は、前記ランレングスが前記ブロック境界部をまたぐとき境界部でランレングスの連続性を有効にしない規則であることを特徴とする請求項３記載の画像処理方法。
【請求項５】
前記デジタルコンテンツをブロックに分割する工程と、前記分割されたブロックの境界部に前記ランレングスがある場合、前記ランレングスに、トポロジを保存して（以下、第３のトポロジ保存則）電子透かし情報を埋込む工程とを含むことを特徴とする請求項１記載の画像処理方法。
【請求項６】
前記第３のトポロジ保存則は、前記ランレングスが前記ブロック境界部をまたぐとき境界部でランレングスの連続性を有効にする規則であることを特徴とする請求項５記載の画像処理方法。
【請求項７】
前記デジタルコンテンツの上下方向に隣接するランレングスに、トポロジを保存して（以下、第４のトポロジ保存則）電子透かし情報を埋込む工程を含むことを特徴とする請求項１記載の画像処理方法。
【請求項８】
前記第４のトポロジ保存則は、「新たに１個以上の別色画素を、横方向、縦方向に挿入することによって前記ランレングスを分割」させず、かつ前記ランレングスを消滅させない規則であることを特徴とする請求項７記載の画像処理方法。
【請求項９】
前記上下方向に隣接するランレングスに、トポロジを保存して電子透かし情報を埋込むとき、原画像の特徴を保存するように埋め込む工程を含むことを特徴とする請求項７記載の画像処理方法。
【請求項１０】
前記埋め込む工程は、上下のランレングス間の縦線を保存して埋め込むことを特徴とする請求項９記載の画像処理方法。
【請求項１１】
前記埋め込む工程は、上下のランレングス間の階段形状を保存して埋め込むことを特徴とする請求項９記載の画像処理方法。
【請求項１２】
画像等のデジタルコンテンツをブロックに分割する工程と、分割された同一色の画素からなるブロック領域中に存在する、透かし埋め込み対象画素領域に対して、前記ブロック領域の境界線を変えることなく、トポロジを保存して電子透かし情報を埋込む工程とを含むことを特徴とする画像処理方法。
【請求項１３】
画像等のデジタルコンテンツをブロックに分割する工程と、分割された同一色の画素からなるブロック領域中に存在する、透かし埋め込み対象画素領域に対して、前記ブロック領域の境界線の変更を許可し、トポロジを保存して電子透かし情報を埋込む工程とを含むことを特徴とする画像処理方法。
【請求項１４】
画像等のデジタルコンテンツをブロックに分割する工程と、分割された同一色の画素からなるブロック領域中に存在する、透かし埋め込み対象画素領域に対してトポロジを保存して電子透かし情報を埋込むとき、埋め込み後の領域の形状が、埋め込み前の領域の形状を保存するように埋め込む工程とを含むことを特徴とする画像処理方法。
【請求項１５】
請求項１乃至１４のいずれか一つに記載の各工程によって電子透かし情報が埋め込まれた画像から、電子透かし情報を抽出する工程を含むことを特徴とする画像処理方法。
【請求項１６】
前記電子透かし情報は、ランレングスの奇偶値により表現することを特徴とする請求項１、３、５、７、９、１２〜１５のいずれか一つに記載の画像処理方法。
【請求項１７】
画像等のデジタルコンテンツを、同一色の画素が連続するランレングスに分解する手段と、前記ランレングスに、トポロジを保存して（以下、第１のトポロジ保存則）電子透かし情報を埋込む手段とを備えたことを特徴とする画像処理装置。
【請求項１８】
前記第１のトポロジ保存則は、「前記ランレングスの色とは異なる１個以上の色画素を、前記ランレングス中に挿入することによって前記ランレングスを分割」させず、かつ前記ランレングスを消滅させない規則であることを特徴とする請求項１７記載の画像処理装置。
【請求項１９】
前記デジタルコンテンツをブロックに分割する手段と、前記分割されたブロックの境界部に前記ランレングスがある場合、前記ランレングスに、トポロジを保存して（以下、第２のトポロジ保存則）電子透かし情報を埋込む手段とを備えたことを特徴とする請求項１７記載の画像処理装置。
【請求項２０】
前記第２のトポロジ保存則は、前記ランレングスが前記ブロック境界部をまたぐとき境界部でランレングスの連続性を有効にしない規則であることを特徴とする請求項１９記載の画像処理装置。
【請求項２１】
前記デジタルコンテンツをブロックに分割する手段と、前記分割されたブロックの境界部に前記ランレングスがある場合、前記ランレングスに、トポロジを保存して（以下、第３のトポロジ保存則）電子透かし情報を埋込む手段とを備えたことを特徴とする請求項１７記載の画像処理装置。
【請求項２２】
前記第３のトポロジ保存則は、前記ランレングスが前記ブロック境界部をまたぐとき境界部でランレングスの連続性を有効にする規則であることを特徴とする請求項２１記載の画像処理装置。
【請求項２３】
前記デジタルコンテンツの上下方向に隣接するランレングスに、トポロジを保存して（以下、第４のトポロジ保存則）電子透かし情報を埋込む手段を備えたことを特徴とする請求項１７記載の画像処理装置。
【請求項２４】
前記第４のトポロジ保存則は、「新たに１個以上の別色画素を、横方向、縦方向に挿入することによって前記ランレングスを分割」させず、かつ前記ランレングスを消滅させない規則であることを特徴とする請求項２３記載の画像処理装置。
【請求項２５】
前記上下方向に隣接するランレングスに、トポロジを保存して電子透かし情報を埋込むとき、原画像の特徴を保存するように埋め込む手段を備えたことを特徴とする請求項２３記載の画像処理装置。
【請求項２６】
前記埋め込む手段は、上下のランレングス間の縦線を保存して埋め込むことを特徴とする請求項２５記載の画像処理装置。
【請求項２７】
前記埋め込む手段は、上下のランレングス間の階段形状を保存して埋め込むことを特徴とする請求項２５記載の画像処理装置。
【請求項２８】
画像等のデジタルコンテンツをブロックに分割する手段と、分割された同一色の画素からなるブロック領域中に存在する、透かし埋め込み対象画素領域に対して、前記ブロック領域の境界線を変えることなく、トポロジを保存して電子透かし情報を埋込む手段とを備えたことを特徴とする画像処理装置。
【請求項２９】
画像等のデジタルコンテンツをブロックに分割する手段と、分割された同一色の画素からなるブロック領域中に存在する、透かし埋め込み対象画素領域に対して、前記ブロック領域の境界線の変更を許可し、トポロジを保存して電子透かし情報を埋込む手段とを備えたことを特徴とする画像処理装置。
【請求項３０】
画像等のデジタルコンテンツをブロックに分割する手段と、分割された同一色の画素からなるブロック領域中に存在する、透かし埋め込み対象画素領域に対してトポロジを保存して電子透かし情報を埋込むとき、埋め込み後の領域の形状が、埋め込み前の領域の形状を保存するように埋め込む手段とを備えたことを特徴とする画像処理装置。
【請求項３１】
請求項１７乃至３０のいずれか一つに記載の各手段によって電子透かし情報が埋め込まれた画像から、電子透かし情報を抽出する手段を備えたことを特徴とする画像処理装置。
【請求項３２】
前記電子透かし情報は、ランレングスの奇偶値により表現することを特徴とする請求項１７、１９、２１、２３、２５、２８〜３１のいずれか一つに記載の画像処理装置。
【請求項３３】
請求項１乃至１６のいずれか一つに記載の各工程をコンピュータに実現させるためのプログラム。
【請求項３４】
請求項１乃至１６のいずれか一つに記載の各工程をコンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化によりデジタルコンテンツに電子透かしを埋込み、また、デジタルコンテンツに埋め込まれた電子透かしを復元する過程で著作権情報や改ざんなどを検出する画像処理方法、装置、プログラムおよび記録媒体に関する。
【０００２】
本発明の対象となるデジタルコンテンツは、静止画像、動画像、コンピュータプログラム及びコンピュータデータの情報などであり、特に、人工画像など特定色（例えば、２５６色で表現する：限定色、インデックスカラーともいう）しか使用できないカラー画像や２値画像など、グラデーション表現しにくいデータ形式で保存される場合の電子透かし埋込み処理に有効な技術である。
【背景技術】
【０００３】
デジタル情報は、劣化させることなくコンピュータなどで簡単にコピーでき、逆に、書換えなど改ざんすることが容易であるという特徴がある。このため、デジタル情報は簡単な処理や操作によって、不正にコピーされて勝手に再利用されたり、一部を改ざんして証拠写真に使用出来ないようにされやすい。
【０００４】
これを防止する手法として、電子透かしやデータハイディングなどと呼ばれる方法がある。電子透かしは、デジタル画像などのデジタルコンテンツを普通に再生した場合には、視覚できない情報を付加する手法である。
電子透かしを埋込む方法は、次の二つに大きく分類できる。すなわち、
（１）内容データの標本値に直接埋込む方法
（２）周波数成分に埋込む方法
（１）の方法は、加工や圧縮などの処理が行なわれると、埋込んだデータが失われやすいが処理は軽い。一方、（２）の方法は、加工や圧縮などの処理には強いが、埋込みや抽出の処理が重いという特性がある。
【０００５】
本発明が対象とする、特定色しか使用できないカラー画像や２値画像など、グラデーション表現しにくいデータ形式で保存される場合の電子透かしは、（２）の方法の適用が難しく、（１）の方法を用いるのが一般的である。後述するように、本発明は（１）の方法で実現する。
【０００６】
電子透かしをデジタルコンテンツに付加する用途としては、著作権情報の記録、違法コピー者情報の追跡、ＩＰアドレスの履歴記録、違法コピーの防止（不可視・高耐性型）、改ざん防止への応用（不可視・低耐性）、認証、秘密通信、デジタルコンテンツの注釈やラベルを埋込む（可視・不可逆型、所有権者表示）、透かし除去可能化（可視・可逆型、コンテンツ配布）などがある。
【０００７】
その中で、例えば、デジタルカメラへの用途として、写真撮影時にカメラの製造番号、日時等を撮影画像に透かし埋込むと同時にその電子署名を作成する機構をカメラに設ける方法が提案されている（非特許文献１、２を参照）。これにより、証明写真の改ざん検知に加え、撮影カメラの特定や撮影日時の確認が可能となる。改ざん検知は電子署名技術だけで可能であるが、透かし技術を活用することで撮影カメラや撮影日時の特定化が可能になり、改ざん抑止により効果的に作用する。更に、電子透かしの埋込み情報量を多くすることによって、改ざん場所を特定化する精度が向上する。また、著作権保護のためにも多くの情報を透かし埋込みできる方が、埋込み情報の解析時に情報が抽出しやすくなり、有効性が高くなる。
【０００８】
【非特許文献１】電子透かし技術に関する調査報告書、１９９９年３月、日本電子工業振興協会編
【非特許文献２】日経ビジネス、電子情報の不正コピー防止、１９９８年２月２３日号  ｐｐ．６８−７０（１９９８）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、電子透かしを埋込むことによって、埋込み対象のデジタルコンテンツ・データが劣化するので、埋込みデータ量を増やしてもその影響による画質劣化が出来るだけ少なくすることが重要である。
【００１０】
ところで、「人間の眼は、画像平坦部に存在するノイズを感知する能力よりもエッジ部に存在するノイズを感知する能力の方が低い」という特性を利用して、電子透かしを画像へ直接埋込む場合は、一般に画像エッジ部に透かしを埋込む。しかし、画像領域の中で、通常、エッジ部は平坦部よりも領域が狭く、埋込む透かし量が多い場合には、著しく画質が劣化する。特に、帳票、図面、地図など人工的に作成された画像の輪郭線を過度に侵食したり、あるいは画像の骨格線を分断させたり消去するような画質の劣化は、元画像の持つ情報や意味を失ってしまう。
【００１１】
つまり、透かし情報埋込みは、改ざん検知や著作権情報抽出の性能を上げるため、画質劣化を極力抑えるつつ、埋込む透かし情報量を出来るだけ多くすることが望ましいが、埋込む透かし量が多くなるほど、画質劣化の程度が増すという、埋込む透かし量と画質劣化レベルとにはトレードオフ関係がある。
【００１２】
本発明は上記した問題点に鑑みてなされたもので、
本発明の目的は、画質劣化を抑えながら、デジタル画像のトポロジ保存則によって電子透かしを埋め込むことができる画像処理方法、装置、プログラムおよび記録媒体を提供することにある。
【課題を解決するための手段】
【００１３】
本発明は、デジタル画像のトポロジ性の保存、及び顕著なエッジ形状を保存する符号生成方法（トポロジ不変規則）を適用して実現することを最も主要な特徴とする。
【００１４】
本発明に係る電子透かし情報値の表現方法を説明する。ランレングスで電子透かし情報値を表現するが、例えば、横ランレングスの偶奇性で電子透かし情報を表現（例えば、ランレングスが偶数値の場合は電子透かし１ビット情報オフを表し、ランレングスが奇数値の場合には、電子透かし１ビット情報オンを表す）する場合は、透かし埋込みによるランレングスの変更が発生するサイズは、元のランレングス−１〜＋１画素になる。それぞれの変更値を決定する条件を以下のＡ．〜Ｃ．に示す。
Ａ．元のランレングス−１の変更を適用する条件：
「埋込もうとしている１ビット情報値と元のランレングスの偶奇性が一致しない」時に、一致させることを目的に適用する。但し、元のランレングス値が１の場合には、適用できず、下記Ｃ．の方法を適用する。
Ｂ．元のランレングス±０に変更（これは変更無しの意味）する条件：
「埋込もうとしている１ビット情報値と元のランレングスの偶奇性が一致しているので、元のランレングスを変更する必要がない」時に適用する。
Ｃ．元のランレングス＋１の変更を適用する条件：
「埋込もうとしている１ビット情報値と元のランレングスの偶奇性が一致しない」時に、一致させることを目的に適用する。但し、左右両隣のランレングス値が共に１の場合には適用できず、上記Ａ．の方法を適用する。
上記Ａ．とＣ．の“但し”書き以外の場合では、Ａ．とＣ．のどちらでも適用可能であるが、画像形状の劣化を出来るだけ避けるため、以下の（Ａ）、（Ｂ）方法で使い分ける。
【００１５】
なお、この判断方法は、「特定（以下、該当ランと呼ぶ）のランレングス値を変更した場合でも画質の劣化量を少なくする必要から、変更する側（該当ランの左右どちらか）に隣合うランレングスも変更（該当ランの変更値と符合を逆にする増減値によるよる変更）が必要になる」という特徴に基づく。
（Ａ）元のランレングス値が、その両隣のランレングス値に比べて大きい値の場合（左右両隣のランレングスを合せた三つの中で、最大値である場合）、上記Ａ．を適用する。かつ、変更する１画素は、隣合う左右のランレングス値が大きい方の境界部（境界部の１画素を隣のランの画素値に変更する）である。
これは、元画像のランレングスの並びに於いて、
・Ｌl‥‥現在注目しているランの左隣のランレングス（l：leftの意味）
・Ｌt‥‥現在注目しているランのランレングス（t：targetの意味）
・Ｌr‥‥現在注目しているランの右隣のランレングス（r：rightの意味）
とすると、
（Ｌl＜Ｌt）かつ（Ｌr＜Ｌt）の場合に、Ｌtを−１して、Ｌl又はＬrを＋１することを表す。電子透かしは、Ｌtの偶奇性で表現し、Ｌl又はＬrは、（Ｌl＋Ｌt）＝一定、又は（Ｌt＋Ｌr）＝一定となるように、調整用に使用する。
（Ｂ）上記（Ａ）以外の場合（左右両隣のランレングスを合せた三つの中で、最大値にならない場合）、上記Ｃ．を適用する。かつ、変更する１画素は、隣合う左右のランレングス値が大きい方の境界部（隣のランの境界部１画素を該当ランの画素値に変更する）である。
これは、（Ｌt＜Ｌl）又は（Ｌt＜Ｌr）の場合に、Ｌtを＋１して、Ｌl又はＬrを−１することを表す。
【００１６】
なお、電子透かし埋込み対象となる画素の連なり（連続する同一色毎にまとめられるランレングス）についての極端なケースとして、次の二つのケースでは、変更可能な電子透かし情報を１ビットも埋込むことが出来ない。
（１）総てのランレングス値が１であるケース（多くの自然画像（写真）が該当する）。
（２）総ての画素が同一色（一組のランレングスだけの構成）であるケース。
【００１７】
本発明に係る、デジタル画像のトポロジ性を保存する方法は、画像をブロックに分割し、ブロック毎に固有のトポロジ保存機能を実現する。
【００１８】
トポロジ保存（不変規則）の基本的な考え方は、「同一色画素が連続することにより形成される同一色画素領域（ランレングス）は、１個以上の別色画素が間に挟まれることによってランレングスが分割されることを禁止し、また、中に埋込む入れ子領域を新たに形成することを禁止し、さらにランレングスの消滅も禁止する」。
【００１９】
画像をブロックに分割する利点は、情報の埋込み場所を分割することによってブロック単位の管理が簡単になり、透かし埋込み処理と抽出処理において、並列処理が可能な実行環境では、ブロック別に並列に実行でき、処理が高速化される。
【００２０】
ブロックの分割方法は、次の３通りである。
（１）（１×ｎ）画素上の直線型（１次元空間）ブロック；
同一色が連続する画素を、ランレングスと呼ばれるデータでつないだものである。横長や縦長のランレングスがあるが、以下では、横長で直線状のランレングスを前提に説明する。この場合は、左右方向にランレングスを変更し、値の偶奇性などで透かし値を表現する。なお、ｎは２のべき乗である。以下、同様である。
【００２１】
左隣りや右隣りブロックとのブロック境界部をトポロジ保存する場合に、境界部が隣りのブロック境界と同一色の場合は、当該ブロック境界に存在するランレングスを０にすることができる。ただし、隣りの側の境界部の同一色のランレングスも同時に０にすることは出来ない（ブロック境界を跨ったトポロジ保存のため）。
（２）（ｎ×ｎ）矩形ブロック；
この場合は、上記ランレングスの保存を前提にする場合と、ランレングスの保存とは直接関係なく、２次元の領域でトポロジを保存する場合とがある。
（３）同一色画素で囲まれた、同一色の独立領域；
同一色の輪郭線などで囲まれた領域毎に管理できるので、トポロジ保存による画質劣化を抑える効果が大きい。ただし、境界部の形状が不定形である場合には処理が複雑になり、高速処理が難しい。
【００２２】
トポロジ保存機能のブロック境界での扱い方は、次の２通りである。
（１）それぞれのブロック内の画素に限定してトポロジを保存する方法；この方法は、ブロック毎に独立した処理になるので、ブロック単位処理の並列化が行える。ただし、ブロック境界部での画質が若干劣化する。
（２）ブロック境界部は、境界外部との画素値の連続性を考慮してトポロジを保存する方法；この方法は、ブロック毎に独立した処理が一部規制されるので、ブロック単位処理の並列化が出来ないこともあるが、ブロック境界部の画質劣化を抑える効果がある。
（３）デジタル画像中の顕著なエッジ形状を保存する方法；
帳票、図面、地図などの人工画像では、水平線、垂直線、斜め直線が、その画像内で重要度の高い線として多用されている。また、撮影装置の画素に当たるＣＣＤや表示装置の画素の並びが水平、垂直線方向に整列している。そこで、これらの特徴が重要であると判断し、同一色の連続する画素の並びが、水平線、垂直線、或は斜め線（画像を拡大すると階段状）の特徴を損なわない範囲内で、画素値を変更することによって電子透かしを埋込む。
【発明の効果】
【００２３】
本発明によって、画像中の全ての画素色に対し、同一色画素が連続する個所に、画質劣化を抑えながら、電子透かしを埋込むことが出来る。
【発明を実施するための最良の形態】
【００２４】
以下、発明の実施の形態について図面により詳細に説明する。
【実施例１】
【００２５】
図１は、本発明の実施例のシステム構成を示す。図１は、デジタル画像の符号（電子透かしの埋込み）生成および復号（電子透かしを解読し、改ざんを検出する）方法を実施する符号生成及び解析復号装置の構成例を示す。
【００２６】
本発明は、全体制御部１、操作入力（キーボード、マウス）部２、外部記憶装置３、メモリ４、画像撮影部５、表示部６、外部からの任意データ入力部７、電子透かし埋込み用ソースデータ生成部８、トポロジ保存処理部９、電子透かし埋込み部１０、画像再生部１１、電子透かし解読部１２、検出した改ざん部の（反転）表示部１３、バス１４などから構成される。なお、これらの各部（又は装置）とバス１４との間に必要なインタフェース部は図示を省略している。
【００２７】
全体制御部１は、装置全体の動作及び機能を制御するマイクロコンピュータ（ＣＰＵ，ＲＯＭ，ＲＡＭ等から構成されるがＣＰＵと略称）であり、画像撮影側処理の画像撮影部５、外部からの任意データ入力部７、電子透かし埋込み用ソースデータ生成部８、トポロジ保存処理部９、電子透かし埋込み部１０、画像再生側処理の画像再生部１１、電子透かし解読部１２、検出した改ざん部の（反転）表示部１３の各機能も、上記ＣＰＵのソフト処理によって実現できる。
【００２８】
操作入力部２は、各種操作指示や機能選択指令、編集データ等を入力するためのものであり、キーボードやマウスあるいはタッチパネル等である。特に、電子透かしデータを埋込んだ画像データを暗号化するときに、また暗号化された電子透かしを解読するときに、秘密キーの入力機能として使用する。
【００２９】
操作入力部２は、表示選定手段としての機能も有し、表示部６の表示状態を操作者の所望の表示状態に変更することができる。例えばキー操作により、電子透かし解読結果を入力イメージ画像データと重ね合わせて表示させたり、どちらか一方のみを選択して表示させたりすることができる。
【００３０】
外部記憶装置３は、画像撮影部５で撮影した画像データや電子透かし埋込み部１０によって電子透かしが埋込まれた圧縮データ、及び電子透かし解読部１２によって検出した改ざん部のデータ等をフロッピディスク（ＦＤ）や光磁気ディスク（ＯＭＤ）等の外部へ取り出し可能な記憶媒体に記憶させる記憶装置である。また、外部記憶装置３は、全体制御部１で実行するプログラムソフトを記録する媒体としても機能する。
【００３１】
メモリ４は、画像撮影部５によって読み取ったイメージ画像データ、電子透かしが埋め込まれて一旦保存されたデータを、逆に画像再生部１１によって読出し伸張された画像データ等を格納する大容量のＲＡＭあるいはハードディスク等によるメモリである。
【００３２】
画像撮影部５は、セットされた写真や帳票等をスキャンしてその画像を読み取ってイメージ画像データを入力する画像データ入力手段であり、スキャン光学系及びＣＣＤなどのイメージセンサとその駆動回路等からなる公知のイメージスキャナやデジタルカメラである。
【００３３】
外部からの任意データ入力部７は、デジタルコンテンツへの補足情報を電子透かしとして埋込むためのソース情報、及び、改ざん検知や著作権保護用の埋込み情報を入力する手段である。入力されたデータは、電子透かし埋込み用ソースデータ生成部８に送るために、メモリ４に格納する。
【００３４】
電子透かし埋込み用ソースデータ生成部８は、外部からの任意データ入力部７で入力されたデータを、暗号化または符号化する。処理後、電子透かし埋込み部１０に送るためにメモリ４に格納する。
【００３５】
電子透かし埋込み部１０は、外部データからの任意データ入力部７で処理されたデータを電子透かし埋込み用ソースデータ生成部８で暗号化など符号化されて、メモリ４に格納されたものを電子透かしとして埋込む処理を施す。
【００３６】
また、電子透かし埋込み部１０では、電子透かし埋込み時に、原画像をブロックに分割し、また連続した（横方向や縦方向など）同一色画素の並びを一つのラン（ランレングス）の単位で処理する方法によって画像全体をランの並びに変換する処理も施す。図２は、後述するように、画像撮影時の電子透かし情報の埋込み処理のフローチャートを示す。
【００３７】
トポロジ保存処理部９は、電子透かし埋込み部１０において、画質劣化を極力抑えるように、電子透かし埋込み用ソースデータ生成部８で生成されたデータのデジタルコンテンツへの埋込み場所を制御する手段である。
【００３８】
例えば、文書、製図、イラスト漫画、及び地図など主に人工画像で使用できる色数が制限され、中間色（グラデーションなど色目のファジー化）が表現できない条件の下で、電子透かしを埋込む場合に、選ばれたトポロジ保存性のある埋込み方法によって、画質の劣化の抑制に適した個所だけに電子透かしを埋込むことができる。トポロジ保存処理部９の処理は、図４〜図１０で詳述する。
【００３９】
画像再生部１１は、電子透かし埋込み部１０で電子透かしが埋込まれて外部記憶装置３などに保存されたデータを読み取るための制御を行う。読み取られた画像は、メモリ４に格納する。
【００４０】
電子透かし解読部１２は、画像再生部１１によりメモリ４から再生された電子透かしが埋込まれた画像データ中から、電子透かしを解読し、解読可能か否かによって、画像の改ざん性や著作権保護情報が有効か否かを判断する。
【００４１】
また、電子透かし解読部１２では、電子透かし解読処理に先立って、電子透かしが埋込まれている画像をブロックに分割し、また連続した（横方向や縦方向など）同一色画素の並びを一つのラン（ランレングス）の単位で処理する方法によって画像全体をランの並びに変換する処理も施す。図３は、後述するように、画像再生時の電子透かし情報の抽出処理のフローチャートを示す。
【００４２】
検出した改ざん部の（反転）表示部１３は、電子透かし解読部１２で解読した結果、改ざん有りと判断できる場合は、該当する領域を反転表示や、黒色による塗潰し表示などで表示する機能を有する。
【００４３】
図４は、本発明の電子透かし埋込みの第１の例を説明する図である。図４を参照して、同一行内に透かしを埋込む場合のトポロジ保存規則を説明する。
【００４４】
図４（ａ）の原画像は、例えば８ビットで量子化した一行の画像データの一部のランレングスを示す。すなわち、図のランレングスは、ランレングスａ（例えば各画素値が１００でその長さは５画素）と、ランレングスｂ（例えば各画素値が０でその長さは１画素）と、ランレングスｃ（例えば各画素値が２５５でその長さは５画素）と、ランレングスｄ（例えば各画素値が５０でその長さは２画素）の４種類の色のランレングスからなっている。なお、ランレングス情報を保存している場所は、図示しないブロック内にある。
【００４５】
図４の例（ａ），（ｂ）は、同一行内のトポロジが変化しないように、ランレングスの削除（ランレングスを０にすることと同等）又は新たな追加（１以上の値のランレングス情報を新たに作ること）をしない範囲で、電子透かし埋込みしたものである。
また、偶数長のランレングスに例えばビット０を割り当て、奇数長のランレングスにビット１を割り当てると、
この例は、埋込みたい透かし情報が、“０００１”に対して、原画像のランレングスの並びが、“５：奇数”→“１：奇数”→“５：奇数”→“２：偶数”であるので、電子透かし情報の埋込みによって、注目したランの並びがたまたま４個連続してランレングスを変更する例となっている。
すなわち、図４（ｂ）では、５画素長のランレングスａを１画素縮めて、４画素長のランレングスａ’とし、１画素長のランレングスｂを１画素伸ばして、２画素長のランレングスｂ’とし、５画素長のランレングスｃを１画素伸ばして、６画素長のランレングスｃ’とし、２画素長のランレングスｄを１画素縮めて、１画素長のランレングスｄ’とする。これにより、原画像（ａ）からトポロジが保存された画像（ｂ）が生成される。画像（ｂ）のランレングスは、ａ’＝４、ｂ’＝２、ｃ’＝６、ｄ’＝１となる。偶数長のランレングスに例えばビット０を割り当て、奇数長のランレングスにビット１を割り当てると、”０００１”という透かし情報が埋め込まれた画像（ｂ）が生成される。なお、上記した伸縮の画素数は画質の劣化を抑えるため最大１画素とする。
【００４６】
図４（ｃ）、（ｄ）は、トポロジが保存されない例を示す。この例では、同一行内で同一色のランレングスの過不足がある場合である。図４（ｃ）の原画像のランレングスは、図４（ａ）のそれと同じ（“奇数”→“奇数”→“奇数”→“偶数”の順のとおり、偶奇性の左から右への並びが同じである意味）である。図４（ｄ）は、ランレングスａを１画素伸ばし、ランレングスｃを１画素縮めて透かしを埋め込んだ画像であるが、ランレングスｂが消失し、ランレングスｅ’が新たに生成された結果、トポロジが保存されず、図４（ｄ）の透かし埋め込み画像は無効と判定される。
ここで、“同一行内で同一色のランレングスの過不足がある場合”とは、
図４の(c)原画像と(d)透かし埋込み画像のランの対応関係について言えば、不一致（図中の“×”で示した箇所）が生じていることを表す。また、図４の(e)原画像と(f)透かし埋込み画像のランの対応関係も不一致が生じているので、これも“同一行内で同一色のランレングスの過不足がある場合”のもう一つの例である。
これに対し、図４の（ａ）原画像と（ｂ）透かし埋込み画像のランの対応関係は、総て一致（図中に“○”で示したように、ランが示す色の左右並びが同じでかつラン数の増減がない：個々のランの長さに変化があるだけ）していることを表している。
“同一行内で同一色のランレングスの過不足がある場合である”が、どのようにして分かるのかについて、
電子透かしを埋込んだ画像を生成したら、原画像は廃棄（削除）されることが多く、同一色ランが過不足になっているかどうかが確実に分かるのは電子透かし埋込み時だけである。この場合は、通常、電子透かしを埋込んだ画像を新たな原画像として使用することになる。正確には、元の画像とは異なるが、元の画像本来の機能を保ったままで、付加情報が隠れ情報として備わるものである。
電子透かし埋込み時の処理方法は、図２中のステップ９の処理が該当し、その実現方法の詳細は、例えば、以下の処理方式が考えらる。
処理方式；
画素並びの処理順は、左端画素から１画素ずつ右に向かって、原画像を分析しながら、進めて行く。
ｉ）ランの切れ目の判断方法
同一行内に於いて、電子透かしを埋込もうとして注目している１画素位置の画素値が左隣の画素値と、
（１）同じであれば、その画素と左隣の画素の間はランの途中であると判断
（２）異なれば、その画素と左隣の画素の間が、ランの切れ(変り)目であると判断
ii）ランの長さ調整方法
上記ｉ）（２）記載のランの切れ目の位置を移動することになる。例えば、注目しているランの右端を左に１画素短くするのは、図４(a)，(b)で示すランａ⇒ａ’の変更に該当し、ランａを形成していたａの右端１画素を右隣のランｂを形成する画素値に変更するものである。
この場合、切れ目の１箇所を移動（例えば、左右に１画素）すると、切れ目の両側のランレングスを両方同時に変更する（図４（ａ），（ｂ）では、a⇒ａ’，かつｂ⇒ｂ’）ことになる。
以上の処理方式の更なる詳細説明は後述する。
【００４７】
図４（ｅ）、（ｆ）もトポロジが保存されない例を示す。この例では、同一行内で同一色のランレングス中に新たなランレングスが挿入されたり、あるいは削除される場合である。
【００４８】
図４（ｆ）において、透かしを埋め込むことにより、ランレングスｆが新たに生成（挿入）され、ランレングスｇが削除された結果、トポロジが保存されず、図４（ｆ）の透かし埋め込み画像は無効と判定される。
【００４９】
図５は、透かし埋込みの第２の例を説明する図である。図５を参照して、ブロック境界部でトポロジを保存した埋め込み方法を説明する。
【００５０】
原画像のライン１のランレングスＣとＣ’（共に１画素長）との間にブロック境界部がある場合に、ランレングスＣとＣ’は同一色であるので、いずれか一方のランレングスＣまたはＣ’が削除されてもトポロジが保存され、有効な埋め込み処理となる。ランレングスＣまたはＣ’の削除は、ランレングスＢを１画素伸ばしてランレングスＣを削除するか、あるいはランレングスＤを１画素伸ばしてランレングスＣ’を削除する。あるいは、ランレングスＣとＣ’が同一色であっても、同一色とせずに（連続性を有効にしない）、上記したＣまたはＣ’の削除を行わずに、ＣまたはＣ’の１画素の伸張を許すという処理にしてもよい。
【００５１】
原画像のライン２のランレングスｃとｄ（共に１画素長）との間にブロック境界部がある場合に、ランレングスｃとｄは同一色でないので、どちらも削除が禁止される。ランレングスｃはランレングスｂ側に１画素伸ばすことが許され、ランレングスｄはランレングスｅ側に１画素伸ばすことが許される。
【００５２】
図６は、透かし埋込みの第３の例を説明する図である。図６を参照して、上下方向に隣接する行間でトポロジを保存した埋め込み方法を説明する。（ａ）は２ラインの原画像を示す。（ｂ）は埋め込みが有効な例を示す。ライン１のランレングスＣを１画素伸ばしているが、ライン１のランレングスＣとライン２のランレングスｄの連続性が保持（トポロジが保存）されている（図では説明を簡単にするため、ランレングスＡ、Ｂ、ａ、ｂ、ｃ，ｅの長さを変えていない）。
【００５３】
これに対して、（ｃ）では、ライン２のランレングスｃと、ライン１のランレングスＤを共に１画素伸ばしたが、ランレングスＣとｄが原画像と異なり連続していないので、トポロジが保存されず、無効な処理と判定される。
【００５４】
図７は、透かし埋込みの第４の例を説明する図である。図７を参照して、上下方向に隣接する行間でトポロジを保存した埋め込み方法を説明する。図７は、４ラインが隣接している例であるが、ライン２のランレングスＢが１画素伸びた結果、ランレングスＣが原画像と異なり、ランレングスＣがライン２によって連続性が絶たれ、トポロジが保存されず、無効な処理と判定される。
【００５５】
図８は、透かし埋込みの第５の例を説明する図である。図８を参照して、埋め込み対象ブロック中に埋め込み対象画素を、トポロジを保存して埋め込む方法を説明する。
【００５６】
図８（ａ）の原画像において、Ｄは同一色の画素からなるブロックであり、ＡはブロックＤ内にある透かし埋め込み対象画素の領域である。図８（ｂ）の透かし埋め込み画像において、Ｂは透かし埋め込み時に領域Ａと同一色の画素（１画素）を追加した画素を示し、Ｃは透かし埋め込み時に領域Ａと同一色の画素（１画素）を削除し、削除した画素をブロックＤの画素で置き換えたことを示す。
【００５７】
なお、上記した例で例えば画素Ｂの埋め込み時にブロックＤの輪郭線と接する場合には、トポロジが保存されず、無効な処理と判定される。ただし、画素Ｂの埋め込み時にブロックＤの輪郭線と接する場合には、トポロジを保存するためにブロックＤの輪郭線を画素Ｂと接しないように移動すること（輪郭線の変更）を許す。
【００５８】
図９は、透かし埋込みの第６の例を説明する図である。図９を参照して、画質劣化を防止するために、透かし埋め込み対象領域の形状を変えることなく透かしを埋め込む第１の方法を説明する。
【００５９】
図９（ａ）の原画像において、Ａは埋め込み対象ブロック、Ｂは透かし埋め込み対象画素の領域である。領域Ｂは階段状の形状となっている。図９（ｂ）の透かし埋め込み画像において、領域Ｂの各ランレングスを１画素伸ばして領域ａ、ｂとして透かし埋め込む。これにより、原画像の領域Ｂと透かし埋め込んだ領域Ｂ’とは、その形状が相似形となり、画質劣化が目立ち難くなる。例えば、領域ａのみに透かしを埋め込んだ場合には、領域Ｂと領域Ｂ’の形状（凸凹）が変化し、これが画質の劣化となる。
【００６０】
図１０は、透かし埋込みの第７の例を説明する図である。図１０を参照して、画質劣化を防止するために、透かし埋め込み対象領域の形状を変えることなく透かしを埋め込む第２の方法を説明する。
【００６１】
図１０（ａ）の原画像は、ライン１、２のランレングスを示す。（ｂ）は、透かし埋込み処理が有効である例を示し、（ｃ）は透かし埋込み処理が無効である例を示す。
【００６２】
（ｂ）において、ライン２のランレングスｂを１画素伸ばし、ライン１のランレングスＣを１画素伸ばして、透かしを埋め込んだものである。画像（ａ）と（ｂ）の埋め込み箇所を比べると、原画像の特徴（ライン１と２（Ａとａ、Ｂとｂ）間の段差）が保持されていることが分かる。
【００６３】
これに対して、（ｃ）では、ランレングスＡとａ間で、原画像の段差がなくなり、また、ランレングスＢとｂ間、ランレングスＣとｃ間で、原画像にない段差が生成され、原画像の特徴が失われている。
【００６４】
図１１は、本発明の電子透かし埋込みの他の例である。
即ち、原画像は、図４(a)と全く同じ画素配置であり、従って、ランレングスも同じ“５：奇数”→“１：奇数”→“５：奇数”→“２：偶数”で並んでいる。
これに対し、電子透かし埋込みしたい情報が、“０１００”であるので、同一行内のトポロジが変化しないように、ランレングスの削除や新たな追加をしないように、ランレングスを“４：偶数”→“１：奇数”→“６：偶数”→“２：偶数”と、先頭と３番目のランレングスの偶奇性を変更することによって、電子透かし埋込みを表現したものである。図４の例(a),(b)が、たまたま総てのランレングスの偶奇性を変更した例であったので、ここでは、一部のランレングスの変更だけで済む例を示した。
【００６５】
次に、図２を参照して、画像撮影時の電子透かし情報の埋込み処理を説明する。ステップ１では、選択機能を決定するためにキー入力（キーボード等で入力）し、以下の処理のために、その内容をメモリに保存する。
（１）電子透かしで埋込む情報を、秘密キー（パスワードなど）によって予め暗号化してから電子透かしで埋込み、埋込み情報の解読をより困難にする。ただし、常に暗号化してから電子透かしを埋込むのは必須ではなく、暗号化するか否かは選択可能である。
（２）ブロック分割方法ＤｅｖＶａｒ設定のための入力は、以下の処理の流れを分けるために指示を与える。ＤｅｖＶａｒ＝０（矩形）を指示された場合は、以下のステップ３で、透かし埋込み対象を矩形ブロックで処理する（ステップ４）。また、ＤｅｖＶａｒ＝１（同一色輪郭変更可）を指示された場合は、ステップ３で、透かし埋込み対象を同一色による輪郭線で囲まれたブロックで処理し（ステップ５）、かつ以下のステップ１５で、ステップ１６処理に進む。更に、ＤｅｖＶａｒ＝２（同一色輪郭変更不可）を指示された場合は、ステップ３で、透かし埋込み対象を同一色による輪郭線で囲まれたブロックで処理し（ステップ５）、かつ以下のステップ１５で、ステップ１６の処理を行わない。
（３）ブロック境界部の画素連続性に依存した実行有無ＢｄｒＷＭ設定のための入力は、以下のステップ１３の処理を分けるために指示を与える。すなわち、ＢｄｒＷＭ＝１の場合、ステップ１４のブロック境界部の同一色画素の連続性に依存した透かし埋込み処理を行い、かつ、同一色の輪郭線によるブロック境界線を変更するか否かの判定と必要ならその処理を行う。
（４）埋込み同期合せ方法ＳｙｎＭｅｓｈ設定のための入力は、以下のステップ８〜１２判定及び処理の流れを分けるために指示を与える。
（５）ランレングスの足並み合せの透かし埋込み実行有無ＨａｒｍＷＭ設定のための入力は、以下のステップ１７での判定結果を分けるために指示を与える。
【００６６】
これは、原画像に於いて、縦方向に連続して始点又は終点が同一値を取る同一色の横方向ランが並んでいる箇所へ電子透かしを埋込む場合、横ランレングス値の変更量（±１又は０）を同じ値（同期合せした内容）にするかどうか、についての選択機能である。足並み（同期）合せするランの塊の箇所へ埋め込む、電子透かし情報量は、その塊の箇所毎に１ビットしか埋込まないが、これは画質劣化を抑えるためである。
【００６７】
ステップ２では、電子透かしを埋込む原画像として、被写体を多値画像で読取り、メモリ４上に記憶する。この画像は２値画像でも良い。
【００６８】
ステップ３では、ステップ１によって設定されているブロック分割方法ＤｅｖＶａｒに従って、以下の流れを決定する。ＤｅｖＶａｒ＝０の時は、ステップ４の矩形ブロック分割に進む。また、ＤｅｖＶａｒ≠０の時は、ステップ５の矩形以外の形によるブロック分割に進む。
【００６９】
ステップ４の矩形ブロック分割は、画像内の画素値に影響されない内容による固定ブロックサイズで分割する。
【００７０】
ステップ５は、電子透かし埋込み対象画像を同一色による輪郭線でブロック分割する。分割した一つのブロック及びその中に電子透かしを埋込む例を図８に示す。ブロック分割方法は公知の方法を用いる。
【００７１】
ステップ６は、ブロック単位の電子透かし埋込み処理全体の終りを判定する。上記ステップ４又はステップ５で分割されたブロック毎の処理（以下のステップ８〜ステップ１９）について、総て終了していればステップ７に制御を移行する。また、ブロック毎の総ての処理が終了していなければ、ステップ８に制御を移行する。
【００７２】
ステップ７は、電子透かし埋込み処理が終わった後の処理に当たり、電子透かし埋込み画像をファイル保存する。保存先はメモリ４上又は外部記憶装置３である。
【００７３】
ステップ８は、電子透かし埋込み処理のブロック毎の内容で、ブロック内部の電子透かし埋込み方法について、最初の識別を、ステップ１で設定された埋込み同期合せ方法ＳｙｎＭｅｓｈを基に行う。埋込み同期合せ方法が「行毎に独立して行う（ＳｙｎＭｅｓｈ＝０）」を選択の場合は、ステップ９に制御を移す。また、そうでない場合は、ステップ１０の次の識別処理に制御を移す。
【００７４】
ステップ９は、埋込み同期合せ方法が「行毎に独立して行う（ＳｙｎＭｅｓｈ＝０）」であることを基に、電子透かし埋込み処理を行う（図４、図１１を参照）。また、図１０の制限を加えれば（フローチャート上での図示は省略）、画質劣化を抑えることが出来る。
図４及び図１１に関連する電子透かしを埋込む処理フローについて説明する。
画像の行単位に、左座標から右方向の画素ラン順にランレングスを透かし情報にする場合の処理手順は、次の通りである。
ここで、C．は、トポロジ保存則と、画像の行幅変更不可則を両立させる為に、設けた規則である。
A．左端のランから右方向にランレングスを決める。
B．電子透かし情報１bitを埋込む時、電子透かしを埋込もうとして注目している当該ランレングス＝Ｌt，その右隣のランレングス＝Ｌr  とすると、
(A)  埋込み情報１bitの偶奇値＝Ｌtの偶奇値の時、Ｌt及びＬr変更なし
(B)  埋込み情報１bitの偶奇値≠Ｌtの偶奇値の時、
a．Ｌt≦Ｌrの時、
Ｌtを＋１し、かつ  Ｌrを−１する
b．Ｌt＞Ｌrの時、
Ｌtを−１し、かつ  Ｌrを＋１する
C．Ｌt＝１は透かし情報とみなさない‥‥下例では１＾で表現する
例えば、電子透かしとして埋込みたい情報と、原画像のランレングスが、以下の場合で記述する。（関連箇所を で強調する）
・埋込み情報bit並び  ：  １  ０  １  １  １  ０  ‥‥埋込み順
・埋込み先の原画像のランレングスの並び
：  ４  １  ３  １  ２  ３  ４  ２  ３
ｉ）埋込み情報の先頭bit値を埋込んだ後の埋込み画像の状態：
３ ２  ３  １  ２  ３  ４  ２  ３
ii）埋込み情報の２bit目の値を埋込んだ後の埋込み画像の状態：変更無し
３  ２  ３  １  ２  ３  ４  ２  ３
iii）埋込み情報の３bit目の値を埋込んだ後の埋込み画像の状態：変更無し
３  ２  ３  １  ２  ３  ４  ２  ３
iv）埋込み情報の４bit目の値を埋込んだ後の埋込み画像の状態：
３  ２  ３  １＾３ ２  ４  ２  ３
ｖ）埋込み情報の５bit目の値を埋込んだ後の埋込み画像の状態：
３  ２  ３  １＾３  ３ ３  ２  ３
vi）埋込み情報の６bit目の値を埋込んだ後の埋込み画像の状態：
３  ２  ３  １＾３  ３  ２ ３  ３
図１０に関連する電子透かしを埋込む処理方法について説明する。
画像の行単位の画素の並びをランレングスで表現し、上記図４及び図１１で説明したように、隣合うランレングスを、該当ランレングス＝Ｌt，その右隣のランレングス＝Ｌrとする。電子透かしは、Ｌtの偶奇性で表現し、Ｌrは（Ｌt＋Ｌr）＝一定となるように、調整用に使用する。
これを画素単位で表現すると、Ｌtの偶奇性が電子透かしの意図したビット値に一致しない場合は、Ｌtの右端の画素ＩteをＬrの左端の画素Ｉrsの値（もちろんＩteの値≠Ｉrsの値）に変更、又は、ＩrsをＩteの画素の値に変更することを表す。
今注目している画素Ｉte，Ｉrsの上下行の近接画素を次のように表現する。
・１行上の画素の並び  Ｉu-，Ｉu0，Ｉu1，Ｉu2‥‥それぞれ１画素を表す
・当該行の画素の並び  Ｉt-，Ｉte，Ｉrs，Ｉr2‥‥それぞれ１画素を表す
・１行下の画素の並び  Ｉd-，Ｉd0，Ｉd1，Ｉd2‥‥それぞれ１画素を表す
以上のことを前提に、図１０を満たす条件を整理すると、以下の２ケースの何れかになる。
A．画像内のエッジ部が縦線を形成する以下の４ケースの場合、
何れの場合も変更不可である。（エッジ部の縦線を損なわせることになる為）
a．Ｉu1＝ＩrsかつＩu0≠Ｉrsの時
b．Ｉd1＝ＩrsかつＩd0≠Ｉrsの時
c．Ｉu0＝ＩteかつＩu1≠Ｉteの時
d．Ｉd0＝ＩteかつＩd1≠Ｉteの時
B．画像内のエッジ部が階段形状である以下の８ケースの場合、
何れの場合も変更可能である。（エッジ部の階段形状を保てることになる為）
(A)  右上から左下への階段形状の場合
a．ＩteをＩrsの値に変更する場合（Ｉt-＝Ｉteが前提）
(a)Ｉte＝Ｉu-＝Ｉu0＝Ｉu1かつＩte≠Ｉd-かつＩte≠Ｉd0の時
(b)Ｉrs＝Ｉd-＝Ｉd0＝Ｉd1かつＩrs≠Ｉu0かつＩrs≠Ｉu1の時
b．ＩrsをＩteの値に変更する場合（Ｉrs＝Ｉr2が前提）
(a)Ｉte＝Ｉu0＝Ｉu1＝Ｉu2かつＩte≠Ｉd0かつＩte≠Ｉd1の時
(b)Ｉrs＝Ｉd0＝Ｉd1＝Ｉd2かつＩrs≠Ｉu1かつＩrs≠Ｉu2の時
(B)  左上から右下への階段形状の場合
a．ＩteをＩrsの値に変更する場合（Ｉt-＝Ｉteが前提）
(a)Ｉte＝Ｉd-＝Ｉd0＝Ｉd1かつＩte≠Ｉu-かつＩte≠Ｉu0の時
(b)Ｉrs＝Ｉu-＝Ｉu0＝Ｉu1かつＩrs≠Ｉd0かつＩrs≠Ｉd1の時
b．ＩrsをＩteの値に変更する場合（Ｉrs＝Ｉr2が前提）
(a)Ｉte＝Ｉd0＝Ｉd1＝Ｉd2かつＩte≠Ｉu0かつＩte≠Ｉu1の時
(b)Ｉrs＝Ｉu0＝Ｉu1＝Ｉu2かつＩrs≠Ｉd1かつＩrs≠Ｉd2 の時
【００７５】
ステップ１０は、電子透かし埋込み処理のブロック毎の内容で、ブロック内部の電子透かし埋込み方法について、次の識別を、ステップ１で設定された埋込み同期合せ方法ＳｙｎＭｅｓｈを基に行う。埋込み同期合せ方法が「上下行の画素値状態に依存して行う（ＳｙｎＭｅｓｈ＝１）」を選択の場合は、ステップ１１に制御を移す。また、そうでない場合は、埋込み同期合せ方法が「２次元平面に於ける同一画素値の連続性に依存して行う（ＳｙｎＭｅｓｈ＝２）」を選択したとみなし、ステップ１２の処理に制御を移す。
【００７６】
ステップ１１は、埋込み同期合せ方法が「上下行の画素値状態に依存して行う（ＳｙｎＭｅｓｈ＝１）」であることを基に、電子透かし埋込み処理を行う（図６を参照）。また、図１０の制限を加えれば（フローチャート上での図示は省略）、画質劣化を抑えることが出来る。
図６に関連する電子透かしを埋込む処理方法について説明する。
画像の行単位の画素の並びをランレングスで表現し、上記ステップ９で説明したように、隣合うランレングスを、該当ランレングス＝Ｌt，その右隣のランレングス＝Ｌrとする。電子透かしは、Ｌtの偶奇性で表現し、Ｌrは（Ｌt＋Ｌr）＝一定となるように、調整用に使用する。
これを画素単位で表現すると、Ｌtの偶奇性が電子透かしの意図したビット値に一致しない場合は、Ｌtの右端の画素ＩteをＬrの左端の画素Ｉrsの値（もちろんＩteの値≠Ｉrsの値）に変更、又は、ＩrsをＩteの画素の値に変更することを表す。
今注目している画素Ｉte，Ｉrsの上下行の近接画素を次のように表現する。
・１行上の画素の並び  Ｉu-，Ｉu0，Ｉu1，Ｉu2‥‥それぞれ１画素を表す
・当該行の画素の並び  ‥‥Ｉte，Ｉrs‥‥  ‥‥それぞれ１画素を表す
・１行下の画素の並び  Ｉd-，Ｉd0，Ｉd1，Ｉd2‥‥それぞれ１画素を表す
以上のことを前提に、図６を満たす条件を整理すると、以下の２ケースの何れかになる。
A．Ｌtを-1してＬrを+1（Ｉteの値をＩrsの値に変更）できるかどうかについて、
これができない条件は、次の通り。
Ｌt≦１
or（Ｉu0＝Ｉte  and  Ｉu-≠Ｉte）or（Ｉd0＝Ｉte  and  Ｉd-≠Ｉte）
or（Ｉu0＝Ｉrs  and  Ｉu1≠Ｉrs）or（Ｉd0＝Ｉrs  and  Ｉd1≠Ｉrs）
B．Ｌtを+1してＬrを-1（Ｉrsの値をＩteの値に変更）できるかどうかについて、
これができない条件は、次の通り。
Ｌr≦１
or（Ｉu1＝Ｉte  and  Ｉu0≠Ｉte）or（Ｉd1＝Ｉte  and  Ｉd0≠Ｉte）
or（Ｉu1＝Ｉrs  and  Ｉu2≠Ｉrs）or（Ｉd1＝Ｉrs  and  Ｉd2≠Ｉrs）
【００７７】
ステップ１２は、埋込み同期合せ方法が「２次元平面に於ける同一画素値の連続性に依存して行う（ＳｙｎＭｅｓｈ＝２）」であることを基に、電子透かし埋込み処理を行う（図７を参照）。
図７に関連する電子透かしを埋込む処理方法について説明する。
画像の行単位の画素の並びをランレングスで表現し、上記ステップ９で説明したように、隣合うランレングスを、該当ランレングス＝Ｌt，その右隣のランレングス＝Ｌrとする。電子透かしは、Ｌtの偶奇性で表現し、Ｌrは（Ｌt＋Ｌr）＝一定となるように、調整用に使用する。
これを画素単位で表現すると、Ｌtの偶奇性が電子透かしの意図したビット値に一致しない場合は、Ｌtの右端の画素ＩteをＬrの左端の画素Ｉrsの値（もちろんＩteの値≠Ｉrsの値）に変更、又は、ＩrsをＩteの画素の値に変更することを表す。
今注目している画素Ｉte，Ｉrsの上下行の近接画素を次のように表現する。
・１行上の画素の並び  Ｉu-，Ｉu0，Ｉu1，Ｉu2‥‥それぞれ１画素を表す
・当該行の画素の並び  Ｉt-，Ｉte，Ｉrs，Ｉr2‥‥それぞれ１画素を表す
・１行下の画素の並び  Ｉd-，Ｉd0，Ｉd1，Ｉd2‥‥それぞれ１画素を表す
以上のことを前提に、図７を満たす条件を、Ｌtを-1し、かつＬrを+1（Ｉteの値をＩrsの値に変更）できるかどうかに限定して整理すると、以下の５ケースの何れかの場合には、変更できないと判断することになる。
A．Ｉt-≠Ｉteの場合、以下のいずれかの時
(A)  Ｉteが、その４近傍（Ｉu0，Ｉt-，Ｉd0，Ｉrs）総てと異なる値となる時
(B)  Ｉu0＝Ｉte＝Ｉd0となる時
B．Ｉt-＝Ｉteの場合、以下のいずれかの時
(A)  Ｉu0＝ＩteかつＩu-≠Ｉteの時
(B)  Ｉd0＝ＩteかつＩd-≠Ｉteの時
C．Ｉu1≠Ｉrsの場合、Ｉu0＝Ｉrsの時
D．Ｉd1≠Ｉrsの場合、Ｉd0＝Ｉrsの時
E．Ｉt-＝Ｉrsの場合、以下の両方共に満たさない時
(A)  Ｉrs＝Ｉu1＝Ｉu0＝Ｉu-の時
(B)  Ｉrs＝Ｉd1＝Ｉd0＝Ｉd-の時
【００７８】
ステップ１３は、上記ステップ９〜１２で行うブロック内部の電子透かし埋込み処理に引き続いて、隣合うブロック同士の境界部の電子透かし埋込み処理に於いて、ブロック境界部の同一色画素の連続性に依存した電子透かし埋込み処理を行うか否かの判定を、ステップ１で設定されたＢｄｒＷＭを基に行う。ブロック境界部の画素連続性に依存した実行有無の識別子が「有り（ＢｄｒＷＭ＝１）」を選択の場合は、ステップ１４に制御を移す。また、そうでない場合は、ステップ１７の判定処理に制御を移す。
【００７９】
ステップ１４は、ブロック境界部の画素連続性に依存した実行有無の識別子が「有り（ＢｄｒＷＭ＝１）」であることを基に、ブロック境界部の電子透かし埋込み処理を行う（図５を参照）。
【００８０】
ステップ１５は、ブロック分割方法が同一色輪郭線を使用して行われる場合に於いて、ブロック境界線が変更可能かどうかの判定を、ステップ１で設定されたＤｅｖＶａｒを基に行っている。ブロック境界線は、同一色輪郭線で変更可能かどうかについて、「同一色輪郭変更可（ＤｅｖＶａｒ＝１）」を選択の場合は、ステップ１６に制御を移す。また、そうでない場合は、ステップ１７の判定処理に制御を移す。
【００８１】
ステップ１６は、ブロック分割方法が同一色輪郭線を使用して行われる場合に限定できる。その中で、ブロック内部のブロック輪郭部の画素と異なる画素値による電子透かし埋込み（ランの伸張）で、ブロック境界線が同一色による輪郭線で形成できない（内部の別画素値ランによって侵食される）時には、電子透かし埋込み後も同一色による輪郭線を保つために、このブロックの外側に輪郭部の同一色画素を拡大する変更を行う（図８を参照）。
【００８２】
ステップ１７は、行の垂直方向に足並みを合せた透かし埋込みを行うか否かの判定を、ステップ１で設定されたＨａｍＷＭを基に行う。ランレングスの足並み合せの電子透かし埋込み実行有無が「有り（ＨａｍＷＭ＝１）」を選択の場合は、ステップ１８に制御を移す。また、そうでない場合は、ステップ１９に制御を移す。
【００８３】
ステップ１８は、ランレングスの足並み合せの電子透かし埋込み実行有無が「有り（ＨａｍＷＭ＝１）」であることを基に、ブロック内部に於いて、行の垂直方向に連続して並んでいる横方向ランの足並みを合せた（原画像の横方向ランの始点又は終点位置の横方向座標が同一値の場合は同一値のまま：平行移動する）電子透かし埋込み処理を行う（図９を参照）。
【００８４】
ステップ１９は、当該ブロックの処理を終わったとみなし、電子透かし埋込み対象を次のブロックに移し、ステップ６の判定処理に制御を移行する。
【００８５】
次に、図３を参照して、画像再生時の電子透かし情報抽出処理を説明する。画像再生時に電子透かしを抽出する処理（図３）は、画像撮影時に電子透かしを埋込む処理（図２）と、多くの点で同一の処理を行う。異なる点は、電子透かし埋込み処理では、電子透かし情報を有効にするために、原画像に変更を加えているのに対し、電子透かし抽出処理では、読取り対象の画像に変更を加えることなく、画像を解析することによって、埋込まれている電子透かし情報を抽出している点である。従って、電子透かし埋込み処理（図２）では、ブロック分割機能として、ＤｅｖＶａｒによる選択肢の中に“同一色輪郭変更可”機能があるが、抽出処理（図３）には存在しない。
【００８６】
ステップ３１によって、選択機能を決定するためにキー入力（キーボード等で入力）し、以下の処理のために、その内容をメモリに保存する。
【００８７】
ここで指定する（１）〜（５）の選択機能は、電子透かし埋込み時と同一内容を設定する必要がある。同一の設定でなければ、抽出対象画像に埋込まれている電子透かしが抽出できないことになる。ただし、（２）で説明する“ブロックの分割方法ＤｅｖＶａｒ”は、電子透かし埋込み時の設定が、“１：同一色輪郭変更可”又は“２：同一色輪郭変更不可”の場合、抽出時には、“１：同一色輪郭”を設定することで、同じ選択内容とみなす。
（１）電子透かし情報を、秘密キー（パスワードなど）によって予め暗号化してから電子透かし情報が埋込まれている画像を対象に、電子透かし情報を抽出する場合に、この秘密キーが必要になる。
（２）ブロック分割方法ＤｅｖＶａｒ設定のための入力は、以下の処理を分けるために指示を与える。ＤｅｖＶａｒ＝０（矩形）を指示された場合は、以下のステップ３３で、電子透かし抽出対象を矩形ブロックで処理する（ステップ３４）。また、ＤｅｖＶａｒ＝１（同一色輪郭）を指示された場合は、ステップ３３で、透かし抽出対象を同一色による輪郭線で囲まれたブロックで処理する（ステップ３５）。
（３）ブロック境界部の画素連続性に依存した実行有無ＢｄｒＷＭ設定のための入力は、以下のステップ４３での処理を分けるために指示を与える。すなわち、ＢｄｒＷＭ＝１の場合、ステップ４４のブロック境界部の同一色画素の連続性に依存した透かし抽出処理を行い、かつ、同一色の輪郭線によるブロック境界線を変更するか否かの判定と必要ならその処理を行う。
（４）埋込み同期合せ方法ＳｙｎＭｅｓｈ設定のための入力は、以下のステップ３８〜４２判定及び処理を分けるために指示を与える。
（５）ランレングスの足並み合せの透かし埋込み実行有無ＨａｒｍＷＭ設定のための入力は、以下のステップ４５判定結果を分けるために指示を与える。これは、電子透かし埋込み処理時の原画像に於いて、縦方向に連続して始点又は終点が同一値を取る同一色の横方向ランが並んでいる箇所へ電子透かしを埋込む場合、横ランレングス値の変更量（±１又は０）を同じ値（同期合せした内容）にするかどうか、についての選択機能である。
【００８８】
ステップ３２では、電子透かしを解読する対象画像として読取り、メモリ上に記憶する。この画像は、多値画像、２値画像の何れでも良い。
【００８９】
ステップ３３では、ステップ３１によって設定されているブロック分割方法ＤｅｖＶａｒに従って、以下の流れを決定する。ＤｅｖＶａｒ＝０の時は、ステップ３４の矩形ブロック分割に進む。また、ＤｅｖＶａｒ≠０の時は、ステップ３５の矩形以外の形によるブロック分割に進む。
【００９０】
ステップ３４の矩形ブロック分割は、画像内の画素値に影響されない内容による固定ブロックサイズで分割する。
【００９１】
ステップ３５は、電子透かし抽出対象画像を同一色による輪郭線でブロック分割する。分割した一つのブロック及びその中に電子透かしが埋込まれている例を図８に示す。ブロック分割方法は、公知の方法を用いる。
【００９２】
ステップ３６は、ブロック単位の電子透かし抽出処理全体の終りを判定する。上記ステップ３４又はステップ３５で分割されたブロック毎の処理（以下のステップ３８〜ステップ４７）について、総て終了していれば、ステップ３７に制御を移行する。また、ブロック毎の総ての処理が終了していなければ、ステップ３８に制御を移行する。
【００９３】
ステップ３７は、電子透かし抽出処理が終了した後の処理に当たり、抽出した電子透かし情報を保存する。保存先はメモリ４上又は外部記憶装置３である。
【００９４】
ステップ３８は、電子透かし抽出処理のブロック毎の内容で、ブロック内部の電子透かし抽出方法について、最初の識別を、ステップ３１で設定された埋込み同期合せ方法ＳｙｎＭｅｓｈを基に行う。埋込み同期合せ方法が「行毎に独立して行う（ＳｙｎＭｅｓｈ＝０）」を選択の場合は、ステップ３９に制御を移す。また、そうでない場合は、ステップ４０の次の識別処理に制御を移す。
【００９５】
ステップ３９は、埋込み同期合せ方法が「行毎に独立して行う（ＳｙｎＭｅｓｈ＝０）」であることを基に、電子透かし抽出処理を行う（図４、図１１を参照）。また、電子透かし埋込み時に、図１０の制限を加えていれば（フローチャート上での図示は省略）、抽出時も同じ制限付きの条件下で、電子透かしを抽出することが出来る。
【００９６】
ステップ４０は、電子透かし抽出処理のブロック毎の内容で、ブロック内部の電子透かし抽出方法について、次の識別を、ステップ３１で設定された埋込み同期合せ方法ＳｙｎＭｅｓｈを基に行う。埋込み同期合せ方法が「上下行の画素値状態に依存して行う（ＳｙｎＭｅｓｈ＝１）」を選択の場合は、ステップ４１に制御を移す。また、そうでない場合は、埋込み同期合せ方法が「２次元平面に於ける同一画素値の連続性に依存して行う（ＳｙｎＭｅｓｈ＝２）」を選択したとみなし、ステップ４２の処理に制御を移す。
【００９７】
ステップ４１は、埋込み同期合せ方法が「上下行の画素値状態に依存して行う（ＳｙｎＭｅｓｈ＝１）」であることを基に、電子透かし抽出処理を行う（図６を参照）。また、電子透かし埋込み時に、図１０の制限を加えていれば（フローチャート上での図示は省略）、抽出時も同じ制限付きの条件下で、電子透かしを抽出することが出来る。
【００９８】
ステップ４２は、埋込み同期合せ方法が「２次元平面に於ける同一画素値の連続性に依存して行う（ＳｙｎＭｅｓｈ＝２）」であることを基に、電子透かし抽出処理を行う（図７を参照）。
【００９９】
ステップ４３は、上記ステップ３９〜４２で行うブロック内部の電子透かし抽出処理に引き続いて、隣合うブロック同士の境界部の電子透かし抽出処理に於いて、ブロック境界部の同一色画素の連続性に依存した電子透かし抽出処理を行うか否かの判定を、ステップ３１で設定されたＢｄｒＷＭを基に行う。ブロック境界部の画素連続性に依存した実行有無の識別子が「有り（ＢｄｒＷＭ＝１）」を選択の場合は、ステップ４４に制御を移す。また、そうでない場合は、ステップ４５の判定処理に制御を移す。
【０１００】
ステップ４４は、ブロック境界部の画素連続性に依存した実行有無の識別子が「有り（ＢｄｒＷＭ＝１）」であることを基に、ブロック境界部の電子透かし抽出処理を行う（図５を参照）。
【０１０１】
ステップ４５は、行の垂直方向に足並みを合せた電子透かし埋込み処理が行われているものとみなすか否かの判定を、ステップ１で設定されたＨａｍＷＭを基に行う。ランレングスの足並み合せの電子透かし埋込み実行有無が「有り（ＨａｍＷＭ＝１）」を選択の場合は、ステップ４６に制御を移す。また、そうでない場合は、ステップ４７に制御を移す。
【０１０２】
ステップ４６は、ランレングスの足並み合せの電子透かし埋込み実行有無が「有り（ＨａｍＷＭ＝１）」であることを基に、ブロック内部に於いて、行の垂直方向に連続して並んでいる横方向ランの足並みを合せた（原画像の横方向ランの始点又は終点位置の横方向座標が同一値の場合は同一値のまま：平行移動しているとみなす）電子透かし抽出処理（足並みを合せた電子透かし埋込み１塊には、１ビットの電子透かし情報しかないことになる）を行う（図９を参照）。
【０１０３】
ステップ４７は、当該ブロックの処理が終了したとみなし、電子透かし抽出対象を次のブロックに移し、ステップ３６の判定処理に制御を移行する。
【０１０４】
なお、本発明は、前述した実施例の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（ＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても達成される。この場合、記憶媒体から読出されたプログラムコード自体が前述した実施例の機能を実現することになる。プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。また、コンピュータが読出したプログラムコードを実行することにより、前述した実施例の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれる。さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれる。
【図面の簡単な説明】
【０１０５】
【図１】本発明の実施例の構成を示す。
【図２】電子透かし情報の埋込み処理のフローチャートを示す。
【図３】電子透かし情報の抽出処理のフローチャートを示す。
【図４】透かし埋込みの第１の例を説明する図である。
【図５】透かし埋込みの第２の例を説明する図である。
【図６】透かし埋込みの第３の例を説明する図である。
【図７】透かし埋込みの第４の例を説明する図である。
【図８】透かし埋込みの第５の例を説明する図である。
【図９】透かし埋込みの第６の例を説明する図である。
【図１０】透かし埋込みの第７の例を説明する図である。
【図１１】透かし埋込みの第８の例を説明する図である。
【符号の説明】
【０１０６】
１  全体制御部
２  操作入力部
３  外部記憶装置
４  メモリ
５  画像撮影部
６  表示部
７  外部からの任意データ入力部
８  電子透かし埋込み用ソースデータ生成部
９  トポロジ保存処理部
１０  電子透かし埋込み部
１１  画像再生部
１２  電子透かし解読部
１３  検出した改ざん部の（反転）表示部
１４  バス
【図１】
2005269617.tif 000003
【図２】
2005269617.tif 000004
【図３】
2005269617.tif 000005
【図４】
2005269617.tif 000006
【図５】
2005269617.tif 000007
【図６】
2005269617.tif 000008
【図７】
2005269617.tif 000009
【図８】
2005269617.tif 000010
【図９】
2005269617.tif 000011
【図１０】
2005269617.tif 000012
【図１１】
2005269617.tif 000013