(57)【特許請求の範囲】
【請求項１】
第１のデータに、第２のデータを埋め込み、符号化データを出力する埋め込み装置であって、
前記第１のデータのうちの注目している注目データと、その予測に用いる前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの可否を判定する判定手段と、
前記注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式を、前記第２のデータに基づいて選択する選択手段と、
前記選択手段により選択された予測方式によって前記注目データを予測することにより、前記予測値を求めるとともに、前記注目データに、前記第２のデータを埋め込む予測／埋め込み手段と、
前記予測値の予測誤差を求め、前記符号化データとして出力する予測誤差演算手段と
を備え、
前記判定手段は、
前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係を判定し、
前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定し、
前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定する
埋め込み装置。
【請求項２】
前記予測／埋め込み手段は、前記注目データの周辺に位置する前記第１のデータを、前記注目データの予測値として求める
請求項１に記載の埋め込み装置。
【請求項３】
前記注目データに対する、前記第２のデータの埋め込みが可能でない場合において、
前記選択手段は、前記予測方式を、前記注目データおよびその予測に用いる前記第１のデータに基づいて選択し、
前記予測／埋め込み手段は、前記選択手段により選択された予測方式によって前記注目データを予測することにより、前記予測値を求めることのみを行う
請求項１に記載の埋め込み装置。
【請求項４】
前記選択手段は、前記第２のデータの埋め込みが可能な前記注目データについて、その予測に用いる２つの前記第１のデータそれぞれを前記予測値とする予測方式のうちの一方を、前記第２のデータに基づいて選択する
請求項１に記載の埋め込み装置。
【請求項５】
前記選択手段は、前記第２のデータの埋め込みが不可能な前記注目データについて、その予測に用いる２つの前記第１のデータそれぞれを前記予測値とする予測方式のうちの前記予測誤差が大きくなる方を選択する
請求項１に記載の埋め込み装置。
【請求項６】
前記第１のデータは、画像データである
請求項１に記載の埋め込み装置。
【請求項７】
前記第１と第２のデータは、画像データを２つの部分に分離した一方の部分と他方の部分である
請求項１に記載の埋め込み装置。
【請求項８】
前記一方の部分としての前記第１のデータに対して、前記他方の部分としての前記第２のデータを最適に埋め込むことができるように、前記画像データを２つの部分に分離する分離手段をさらに備える
請求項７に記載の埋め込み装置。
【請求項９】
第１のデータに、第２のデータを埋め込み、符号化データを出力する埋め込み方法であって、
前記第１のデータのうちの注目している注目データと、その予測に用いる前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの可否を判定する判定ステップと、
前記注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式を、前記第２のデータに基づいて選択する選択ステップと、
前記選択ステップにおいて選択された予測方式によって前記注目データを予測することにより、前記予測値を求めるとともに、前記注目データに、前記第２のデータを埋め込む予測／埋め込みステップと、
前記予測値の予測誤差を求め、前記符号化データとして出力する予測誤差演算ステップと
を備え、
前記判定ステップでは、
前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係を判定し、
前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定し、
前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定する
埋め込み方法。
【請求項１０】
第１のデータに、第２のデータを埋め込み、符号化データを出力する埋め込み処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、
前記第１のデータのうちの注目している注目データと、その予測に用いる前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの可否を判定する判定ステップと、
前記注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式を、前記第２のデータに基づいて選択する選択ステップと、
前記選択ステップにおいて選択された予測方式によって前記注目データを予測することにより、前記予測値を求めるとともに、前記注目データに、前記第２のデータを埋め込む予測／埋め込みステップと、
前記予測値の予測誤差を求め、前記符号化データとして出力する予測誤差演算ステップと
を備え、
前記判定ステップでは、
前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係を判定し、
前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定し、
前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定する
プログラムが記録されている記録媒体。
【請求項１１】
第１のデータに、第２のデータを埋め込むことにより得られた符号化データを、前記第１および第２のデータに復号する復号装置であって、
前記符号化データのうちの注目している注目データと、既に復号された前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの有無を判定する判定手段と、
前記注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式を認識する認識手段と、
前記認識手段により認識された前記予測方式に基づいて、前記注目データを、元の前記第１のデータに復号するとともに、前記注目データに埋め込まれていた前記第２のデータを復号する復号手段と
を備え、
前記判定手段は、
前記注目データと、既に復号された２つの前記第１のデータとの大小関係を判定し、
前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定し、
前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定する
復号装置。
【請求項１２】
前記注目データに対して、前記第２のデータが埋め込まれていない場合において、
前記認識手段は、前記予測方式を、前記注目データおよび既に復号された前記第１のデータに基づいて認識し、
前記復号手段は、前記認識手段により認識された予測方式に基づいて、前記注目データを、元の前記第１のデータに復号することのみを行う
請求項１１に記載の復号装置。
【請求項１３】
前記認識手段は、前記第２のデータが埋め込まれている前記注目データについて、既に復号された２つの前記第１のデータそれぞれを前記予測値とする予測方式のうち、前記注目データの復号結果が、その２つの前記第１のデータの範囲内になる方を、前記注目データに対応する前記第１のデータの予測に用いられたものとして認識する
請求項１１に記載の復号装置。
【請求項１４】
前記認識手段は、前記第２のデータが埋め込まれていない前記注目データについて、既に復号された２つの前記第１のデータそれぞれを前記予測値とする予測方式のうち、予測誤差が大きくなる方を、前記注目データに対応する前記第１のデータの予測に用いられたものとして認識する
請求項１１に記載の復号装置。
【請求項１５】
前記第１のデータは、画像データである
請求項１１に記載の復号装置。
【請求項１６】
前記第１と第２のデータは、画像データを２つの部分に分離した一方の部分と他方の部分である
請求項１１に記載の復号装置。
【請求項１７】
前記一方の部分としての、復号された前記第１のデータと、前記他方の部分としての、復号された前記第２のデータとを結合し、元の前記画像データを構成する結合手段をさらに備える
請求項１６に記載の復号装置。
【請求項１８】
第１のデータに、第２のデータを埋め込むことにより得られた符号化データを、前記第１および第２のデータに復号する復号方法であって、
前記符号化データのうちの注目している注目データと、既に復号された前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの有無を判定する判定ステップと、
前記注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式を認識する認識ステップと、
前記認識ステップにおいて認識された前記予測方式に基づいて、前記注目データを、元の前記第１のデータに復号するとともに、前記注目データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記判定ステップでは、
前記注目データと、既に復号された２つの前記第１のデータとの大小関係を判定し、
前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定し、
前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定する
復号方法。
【請求項１９】
第１のデータに、第２のデータを埋め込むことにより得られた符号化データを、前記第１および第２のデータに復号する復号処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、
前記符号化データのうちの注目している注目データと、既に復号された前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの有無を判定する判定ステップと、
前記注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式を認識する認識ステップと、
前記認識ステップにおいて認識された前記予測方式に基づいて、前記注目データを、元の前記第１のデータに復号するとともに、前記注目データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記判定ステップでは、
前記注目データと、既に復号された２つの前記第１のデータとの大小関係を判定し、
前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定し、
前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定する
プログラムが記録されている記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、埋め込み装置および埋め込み方法、復号装置および復号方法、並びに記録媒体に関し、特に、例えば、復号画像の画質を劣化させることなく、かつデータ量を増加せずに、画像に情報を埋め込むことができるようにする埋め込み装置および埋め込み方法、復号装置および復号方法、並びに記録媒体に関する。
【０００２】
【従来の技術】
データに対して、そのデータ量を増加させることなく、情報を埋め込む手法としては、例えば、ディジタルオーディオデータの最下位ビットや、下位２ビットなどを、埋め込む情報に変換するものなどがある。この手法は、ディジタルオーディオデータの下位ビットが、その音質にあまり影響を与えないことを利用し、その下位ビットを、単に、埋め込む情報に置き換えるものであり、従って、再生時には、情報が埋め込まれたディジタルオーディオデータは、その下位ビットを元に戻さずに、そのまま出力される。即ち、情報が埋め込まれた下位ビットを、元に戻すのは困難であり、また、下位ビットは、音質に、あまり影響を与えないことから、ディジタルオーディオデータは、情報が埋め込まれた状態で出力される。
【０００３】
【発明が解決しようとする課題】
しかしながら、以上のような手法では、本来のデータと異なるデータが出力される。従って、データがオーディオデータである場合には、その音質に、また、データがビデオデータである場合には、その画質に、少なからず影響がある。
【０００４】
本発明は、このような状況に鑑みてなされたものであり、例えば、画像の画質を劣化させることなく、かつデータ量を増加せずに、画像に情報を埋め込むこと等ができるようにするものである。
【０００５】
【課題を解決するための手段】
本発明の第１の側面の埋め込み装置は、第１のデータに、第２のデータを埋め込み、符号化データを出力する埋め込み装置であって、前記第１のデータのうちの注目している注目データと、その予測に用いる前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの可否を判定する判定手段と、前記注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式を、前記第２のデータに基づいて選択する選択手段と、前記選択手段により選択された予測方式によって前記注目データを予測することにより、前記予測値を求めるとともに、前記注目データに、前記第２のデータを埋め込む予測／埋め込み手段と、前記予測値の予測誤差を求め、前記符号化データとして出力する予測誤差演算手段とを備え、前記判定手段は、前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係を判定し、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定し、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定する埋め込み装置である。
【００１６】
本発明の第１の側面の埋め込み方法は、第１のデータに、第２のデータを埋め込み、符号化データを出力する埋め込み方法であって、前記第１のデータのうちの注目している注目データと、その予測に用いる前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの可否を判定する判定ステップと、前記注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式を、前記第２のデータに基づいて選択する選択ステップと、前記選択ステップにおいて選択された予測方式によって前記注目データを予測することにより、前記予測値を求めるとともに、前記注目データに、前記第２のデータを埋め込む予測／埋め込みステップと、前記予測値の予測誤差を求め、前記符号化データとして出力する予測誤差演算ステップとを備え、前記判定ステップでは、前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係を判定し、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定し、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定する埋め込み方法である。
【００１７】
本発明の第１の側面の記録媒体は、第１のデータに、第２のデータを埋め込み、符号化データを出力する埋め込み処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、前記第１のデータのうちの注目している注目データと、その予測に用いる前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの可否を判定する判定ステップと、前記注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式を、前記第２のデータに基づいて選択する選択ステップと、前記選択ステップにおいて選択された予測方式によって前記注目データを予測することにより、前記予測値を求めるとともに、前記注目データに、前記第２のデータを埋め込む予測／埋め込みステップと、前記予測値の予測誤差を求め、前記符号化データとして出力する予測誤差演算ステップとを備え、前記判定ステップでは、前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係を判定し、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定し、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定するプログラムが記録されている記録媒体である。
【００１８】
本発明の第２の側面の復号装置は、第１のデータに、第２のデータを埋め込むことにより得られた符号化データを、前記第１および第２のデータに復号する復号装置であって、前記符号化データのうちの注目している注目データと、既に復号された前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの有無を判定する判定手段と、前記注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式を認識する認識手段と、前記認識手段により認識された前記予測方式に基づいて、前記注目データを、元の前記第１のデータに復号するとともに、前記注目データに埋め込まれていた前記第２のデータを復号する復号手段とを備え、前記判定手段は、前記注目データと、既に復号された２つの前記第１のデータとの大小関係を判定し、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定し、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定する復号装置である。
【００２８】
本発明の第２の側面の復号方法は、第１のデータに、第２のデータを埋め込むことにより得られた符号化データを、前記第１および第２のデータに復号する復号方法であって、前記符号化データのうちの注目している注目データと、既に復号された前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの有無を判定する判定ステップと、前記注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式を認識する認識ステップと、前記認識ステップにおいて認識された前記予測方式に基づいて、前記注目データを、元の前記第１のデータに復号するとともに、前記注目データに埋め込まれていた前記第２のデータを復号する復号ステップとを備え、前記判定ステップでは、前記注目データと、既に復号された２つの前記第１のデータとの大小関係を判定し、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定し、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定する復号方法である。
【００２９】
本発明の第２の側面の記録媒体は、第１のデータに、第２のデータを埋め込むことにより得られた符号化データを、前記第１および第２のデータに復号する復号処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、前記符号化データのうちの注目している注目データと、既に復号された前記第１のデータとに基づいて、前記注目データに対する、前記第２のデータの埋め込みの有無を判定する判定ステップと、前記注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式を認識する認識ステップと、前記認識ステップにおいて認識された前記予測方式に基づいて、前記注目データを、元の前記第１のデータに復号するとともに、前記注目データに埋め込まれていた前記第２のデータを復号する復号ステップとを備え、前記判定ステップでは、前記注目データと、既に復号された２つの前記第１のデータとの大小関係を判定し、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定し、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定するプログラムが記録されている記録媒体である。
【００３０】
本発明の第１の側面においては、前記第１のデータのうちの注目している注目データ注目データに対する、前記第２のデータの埋め込みが可能である場合に、前記注目データの予測値を予測する予測方式が、前記第２のデータに基づいて選択され、その予測方式によって前記注目データを予測することにより、前記予測値が求められるとともに、前記注目データに、前記第２のデータが埋め込まれる。そして、前記予測値の予測誤差が求められ、前記符号化データとして出力される。前記注目データに対する、前記第２のデータの埋め込みの可否の判定では、前記注目データと、その予測に用いる２つの前記第１のデータとの大小関係が判定され、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値である場合に、前記注目データに対する、前記第２のデータの埋め込みが可能であると判定され、前記注目データが、その予測に用いる２つの前記第１のデータの範囲内の値でない場合に、前記注目データに対する、前記第２のデータの埋め込みが不可能であると判定される。
【００３１】
本発明の第２の側面においては、前記符号化データのうちの注目している注目データに、前記第２のデータが埋め込まれている場合に、前記注目データから、前記第１のデータの予測値の予測に用いられた予測方式が認識され、その予測方式に基づいて、前記注目データが、元の前記第１のデータに復号されるとともに、前記注目データに埋め込まれていた前記第２のデータが復号される。前記注目データに対する、前記第２のデータの埋め込みの有無の判定では、前記注目データと、既に復号された２つの前記第１のデータとの大小関係が判定され、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小である場合に、前記注目データに対して、前記第２のデータが埋め込まれていると判定され、前記注目データの大きさが、既に復号された２つの前記第１のデータどうしの差分の大きさより小でない場合に、前記注目データに対して、前記第２のデータが埋め込まれていないと判定される。
【００３２】
【発明の実施の形態】
図１は、本発明を適用した埋め込み圧縮／復号システム（システムとは、複数の装置が論理的に集合した物をいい、各構成の装置が同一筐体中にあるか否かは問わない）の一実施の形態の構成例を示している。
【００３３】
この埋め込み圧縮／復号システムは、符号化装置１および復号装置２で構成されており、符号化装置は、符号化対象としての、例えば、画像を符号化して符号化データを出力し、復号装置２は、その符号化データを、元の画像に復号するようになっている。
【００３４】
即ち、符号化装置１は、埋め込み圧縮符号化器１１で構成され、そこには、符号化対象としての画像と、その画像に埋め込まれる付加情報とが供給されるようになっている。そして、埋め込み圧縮符号化器１１は、画像（ディジタル画像データ）を圧縮符号化するのと同時に、付加情報（ディジタルデータ）を埋め込むことにより、符号化データを得て出力する。埋め込み圧縮符号化器１１が出力する符号化データは、例えば、半導体メモリ、光磁気ディスク、磁気ディスク、光ディスク、磁気テープ、相変化ディスクなどでなる記録媒体３に記録され、あるいは、また、例えば、地上波、衛星回線、ＣＡＴＶ（Cable Television）網、インターネット、公衆回線などでなる伝送媒体４を介して伝送され、復号装置２に提供される。
【００３５】
復号装置２は、復号器１２で構成され、そこでは、記録媒体３または伝送媒体４を介して提供される符号化データが受信される。そして、復号器１２は、その符号化データを、元の画像と、そこに埋め込まれている付加情報に復号する。復号された画像は、例えば、図示せぬモニタ等に供給されて表示される。
【００３６】
なお、付加情報としては、例えば、元の画像に関連するテキストデータや、音声データ、その画像を縮小した縮小画像等は勿論、元の画像に無関係なデータを用いることも可能である。即ち、付加情報としては、あらゆるデータ（プログラムも含む）を用いることが可能である。
【００３７】
次に、図２は、図１の埋め込み圧縮符号化器１１の構成例を示している。
【００３８】
符号化対象の画像データは、フレームメモリ２１に供給されるようになっており、その画像データに埋め込まれる付加情報は、予測器選択回路２３に供給されるようになっている。
【００３９】
フレームメモリ２１は、そこに供給される画像データを、例えば、１フレーム単位で記憶する。フレームメモリ２１に記憶された画像データは、必要に応じて、埋め込み判定回路２２、予測器選択回路２３、スイッチ２４、および予測誤差計算回路２６に供給されるようになっている。
【００４０】
埋め込み判定回路２２は、フレームメモリ２１に記憶された画像データを構成する画素を、例えば、ラスタスキャン順に、順次、注目画素とし、その注目画素に対する付加情報の埋め込みの可否を判定する。
【００４１】
即ち、例えば、いま、図３に示すように、画像データを構成する、ある画素Ｄが注目画素である場合には、埋め込み判定回路２２は、その注目画素Ｄの上に隣接する画素Ｂと、下に隣接する画素Ｃを、フレームメモリ２１から読み出す。そして、埋め込み判定回路２２は、画素Ｂの画素値（以下、適宜、画素値Ｂとも記述する）と、画素Ｃの画素値との間に、注目画素Ｄの画素値が存在するかどうかを判定し、存在する場合には、注目画素Ｄへの埋め込みが可能であると判定し、存在しない場合には、注目画素Ｄへの埋め込みが不可であると判定する。この埋め込み判定回路２２による注目画素への埋め込みの可否の判定結果は、埋め込み判定信号として、予測器選択回路２３に供給されるようになっている。
【００４２】
予測器選択回路２３は、埋め込み判定回路２２から、注目画素への埋め込みが可能な旨の埋め込み判定信号を受信した場合、注目画素を予測（予測符号化）する予測方式を、そこに供給される付加情報に基づいて選択し、その選択結果を表す予測器選択信号を、スイッチ２４に供給する。また、予測器選択回路２３は、埋め込み判定回路２２から、注目画素への埋め込みが不可である旨の埋め込み判定信号を受信した場合、注目画素を予測（予測符号化）する予測方式を、フレームメモリ２１に記憶された注目画素Ｄ、並びにその上に隣接する画素Ｂおよびその左に隣接する画素Ｃの画素値の大小関係に基づいて選択し、その選択結果を表す予測器選択信号を、スイッチ２４に供給する。
【００４３】
スイッチ２４は、予測器選択回路２３からの予測器選択信号にしたがって、端子２４Ａまたは２４Ｂのうちの一方を選択し、これにより、フレームメモリ２１に記憶された画像データを、予測器２５Ａまたは予測器２５Ｂに供給する。
【００４４】
予測器２５Ａおよび２５Ｂは、スイッチ２４を介して供給される画像データを用い、注目画素の予測値を、所定の予測方式で予測し、予測誤差計算回路２６に供給する。なお、予測器２５Ａと２５Ｂとは、異なる予測方式で、注目画素の予測値を予測するようになっている。
【００４５】
即ち、予測器２５Ａは、例えば、注目画素の上に隣接する画素を、注目画素の予測値とする予測方式で、注目画素を予測する。また、予測器２５Ｂは、例えば、注目画素の左に隣接する画素を、注目画素の予測値とする予測方式で、注目画素を予測する。従って、図３における画素Ｄを注目画素とする場合においては、予測器２５Ａでは、画素Ｂが、注目画素Ｄの予測値として求められ、予測器２５Ｂでは、画素Ｃが、注目画素Ｄの予測値として求められる。
【００４６】
予測誤差計算回路２６は、予測器２５Ａまたは２５Ｂが出力する注目画素の予測値の予測誤差を求め、予測誤差保存用メモリ２７に供給する。即ち、予測誤差計算回路２６は、フレームメモリ２１に記憶された注目画素から、予測器２５Ａまたは２５Ｂが出力する注目画素の予測値を減算することにより、その予測値の予測誤差を求め、予測誤差保存用メモリ２７に供給する。
【００４７】
予測誤差保存用メモリ２７は、予測誤差計算回路２６から供給される注目画素の予測値の予測誤差を、例えば、その注目画素の位置に対応するアドレスに記憶する。
【００４８】
エントロピー符号化回路２８は、予測誤差保存用メモリ２７に、例えば、１フレーム分の予測誤差が記憶されると、その１フレーム分の予測誤差を読み出して、例えば、ハフマン符号化等のエントロピー符号化し、その符号化結果を、符号化データとして出力する。
【００４９】
次に、注目画素への埋め込みの可否と、注目画素の予測方式の選択との関係について説明する。
【００５０】
上述したように、本実施の形態では、埋め込み判定回路２２において、注目画素Ｄの画素値が、その上に隣接する画素Ｂの画素値と、その左に隣接する画素Ｃの画素値との間に存在するかどうかが判定され、存在する場合には、注目画素Ｄへの埋め込みが可能であると判定され、存在しない場合には、注目画素Ｄへの埋め込みが不可であると判定される。
【００５１】
従って、図４（Ａ）に示すように、画素値ＢがＣより大である場合（画素値ＣがＢより小である場合）において、注目画素Ｄの画素値が、画素値Ｃよりも大きく、かつ画素値Ｂよりも小さいときには、注目画素Ｄへの埋め込みが可能であり、このように、埋め込みが可能である場合には、予測器選択回路２３において、上述したように、注目画素を予測する予測方式が、そこに埋め込む付加情報に基づいて選択される。即ち、この場合、注目画素の予測値を、予測器２４Ａまたは２５Ｂのうちのいずれで求めるかが、付加情報に基づいて選択される。
【００５２】
いま、１の画素に対して、１ビットの付加情報を埋め込むものとし、例えば、その１ビットの付加情報が０であるときには予測器２５Ａを、１であるときには予測器２５Ｂを、それぞれ選択するものとすると、予測器選択回路２３は、付加情報が０である場合には、予測器２５Ａが接続されている端子２４Ａの選択を指示する予測器選択信号を、スイッチ２４に出力する。
【００５３】
これにより、スイッチ２４は、端子２４Ａを選択し、予測器２５Ａは、スイッチ２４を介して、フレームメモリ２１から、注目画素Ｄの上に隣接する画素Ｂを読み出す。そして、予測器２５Ａは、この画素Ｂを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。その結果、予測誤差計算回路２６では、注目画素Ｄの画素値から、予測値Ｂを減算したＤ−Ｂが、予測誤差として求められ、予測誤差保存用メモリ２７に供給される。
【００５４】
一方、予測器選択回路２３は、付加情報が１である場合には、予測器２５Ｂが接続されている端子２４Ｂの選択を指示する予測器選択信号を、スイッチ２４に出力する。
【００５５】
これにより、スイッチ２４は、端子２４Ｂを選択し、予測器２５Ｂは、スイッチ２４を介して、フレームメモリ２１から、注目画素Ｄの左に隣接する画素Ｃを読み出す。そして、予測器２５Ｂは、この画素Ｃを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。その結果、予測誤差計算回路２６では、注目画素Ｄの画素値から、予測値Ｃを減算したＤ−Ｃが、予測誤差として求められ、予測誤差保存用メモリ２７に供給される。
【００５６】
また、図４（Ｂ）に示すように、画素値ＣがＢより大である場合（画素値ＢがＣより小である場合）において、注目画素Ｄの画素値が、画素値Ｂよりも大きく、かつ画素値Ｃよりも小さいときにも、注目画素Ｄへの埋め込みが可能であり、この場合も、上述した場合と同様の処理が行われる。
【００５７】
即ち、付加情報が０である場合には、予測器選択回路２３は、予測器２５Ａが接続されている端子２４Ａの選択を指示する予測器選択信号を、スイッチ２４に出力し、スイッチ２４に端子２４Ａを選択させる。この場合、予測器２５Ａは、スイッチ２４を介して、フレームメモリ２１から、注目画素Ｄの上に隣接する画素Ｂを読み出し、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。その結果、予測誤差計算回路２６では、注目画素Ｄの画素値から、予測値Ｂを減算したＤ−Ｂが、予測誤差として求められ、予測誤差保存用メモリ２７に供給される。
【００５８】
一方、付加情報が１である場合には、予測器選択回路２３は、予測器２５Ｂが接続されている端子２４Ｂの選択を指示する予測器選択信号を、スイッチ２４に出力し、スイッチ２４に端子２４Ｂを選択させる。この場合、予測器２５Ｂは、スイッチ２４を介して、フレームメモリ２１から、注目画素Ｄの左に隣接する画素Ｃを読み出し、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。その結果、予測誤差計算回路２６では、注目画素Ｄの画素値から、予測値Ｃを減算したＤ−Ｃが、予測誤差として求められ、予測誤差保存用メモリ２７に供給される。
【００５９】
以上は、注目画素への埋め込みが可能である場合の予測方式の選択方法であるが、注目画素への埋め込みが不可である場合には、予測方式は、次のように選択される。
【００６０】
即ち、注目画素Ｄの画素値が、その上に隣接する画素Ｂの画素値と、その左に隣接する画素Ｃの画素値との間に存在しない場合には、埋め込み判定回路２２において、注目画素Ｄへの埋め込みが不可であると判定される。従って、例えば、図５（Ａ）に示すように、画素値ＢがＣより大の場合において、注目画素Ｄの画素値がＢより大きいときや、図５（Ｂ）に示すように、画素値ＣがＢより大の場合において、注目画素Ｄの画素値がＣより大きいとき等には、埋め込み不可と判定される。
【００６１】
埋め込みが不可の場合には、予測器選択回路２３において、上述したように、注目画素を予測する予測方式が、フレームメモリ２１に記憶された注目画素Ｄ、並びにその上に隣接する画素Ｂおよびその左に隣接する画素Ｃの画素値の大小関係に基づいて選択される。即ち、この場合、予測器選択回路２３は、例えば、予測誤差（の大きさ）がより大きくなる予測方式を選択する。
【００６２】
従って、例えば、図５（Ａ）に示す場合においては、注目画素Ｄの予測値をＢとするよりも、Ｃとした方が、予測誤差が大きいので、予測器選択回路２３は、注目画素Ｄの予測値を、その左に隣接する画素Ｃとする予測方式を選択し、そのような予測方式で予測を行う予測器２５Ｂに接続されている端子２４Ｂの選択を指示する予測器選択信号を、スイッチ２４に出力する。
【００６３】
これにより、スイッチ２４は、端子２４Ｂを選択し、予測器２５Ｂは、スイッチ２４を介して、フレームメモリ２１から、注目画素Ｄの左に隣接する画素Ｃを読み出す。そして、予測器２５Ｂは、この画素Ｃを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。その結果、予測誤差計算回路２６では、注目画素Ｄの画素値から、予測値Ｃを減算したＤ−Ｃが、予測誤差として求められ、予測誤差保存用メモリ２７に供給される。
【００６４】
また、例えば、図５（Ｂ）に示す場合においては、注目画素Ｄの予測値をＣとするよりも、Ｂとした方が、予測誤差が大きいので、予測器選択回路２３は、注目画素Ｄの予測値を、その上に隣接する画素Ｂとする予測方式を選択し、そのような予測方式で予測を行う予測器２５Ａに接続されている端子２４Ａの選択を指示する予測器選択信号を、スイッチ２４に出力する。
【００６５】
これにより、スイッチ２４は、端子２４Ａを選択し、予測器２５Ａは、スイッチ２４を介して、フレームメモリ２１から、注目画素Ｄの上に隣接する画素Ｂを読み出す。そして、予測器２５Ａは、この画素Ｂを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。その結果、予測誤差計算回路２６では、注目画素Ｄの画素値から、予測値Ｂを減算したＤ−Ｂが、予測誤差として求められ、予測誤差保存用メモリ２７に供給される。
【００６６】
次に、図６のフローチャートを参照して、図２の埋め込み圧縮符号化器１１の処理について説明する。
【００６７】
符号化対象の画像データは、例えば、１フレーム単位で、フレームメモリ２１に、順次供給されて記憶される。
【００６８】
そして、ある１フレームの画像データが、フレームメモリ２１に記憶されると、ステップＳ１において、フレームメモリ２１に記憶された画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素とされていないものが、注目画素として選択される。
【００６９】
以上のようにして、注目画素が選択された後は、ステップＳ２に進み、埋め込み判定回路２２、予測器選択回路２３、予測器２５Ａ，２５Ｂ、および予測誤差計算回路２６において、注目画素を対象に、後述するような埋め込み圧縮処理が行われ、これにより得られる、注目画素についての予測誤差（注目画素の予測値の予測誤差）が、予測誤差計算回路２６から予測誤差保存用メモリ２７に供給されて記憶される。
【００７０】
そして、ステップＳ３に進み、フレームメモリ２１に記憶された１フレームの画像データを構成するすべての画素を注目画素として処理を行ったかどうかが判定される。ステップＳ３において、まだ、すべての画素を注目画素としていないと判定された場合、ステップＳ１に戻り、以下、同様の処理が繰り返される。
【００７１】
また、ステップＳ３において、すべての画素を注目画素としたと判定された場合、即ち、予測誤差保存用メモリ２７に、１フレーム分の予測誤差が記憶された場合、ステップＳ４に進み、エントロピー符号化回路２８は、予測誤差保存用メモリ２７に記憶された１フレーム分の予測誤差を読み出し、エントロピー符号化する。さらに、エントロピー符号化回路２８は、ステップＳ５において、その結果得られる符号化データを出力し、処理を終了する。
【００７２】
なお、図６の処理は、例えば、フレームメモリ２１に１フレームの画像データが記憶されるごとに行われる。
【００７３】
次に、図７のフローチャートを参照して、図６のステップＳ２における埋め込み圧縮処理について説明する。
【００７４】
埋め込み圧縮処理では、まず最初に、ステップＳ１１において、埋め込み判定回路２２は、注目画素への埋め込みの可否を判定する。ステップＳ１１において、注目画素への埋め込みが可能であると判定された場合、埋め込み判定回路２２は、その旨の埋め込み判定信号を、予測器選択回路２３に出力し、ステップＳ１２に進む。
【００７５】
ステップＳ１２では、予測器選択回路２３は、注目画素に埋め込む付加情報に基づいて、予測方式を選択し、その選択結果としての予測器選択信号を、スイッチ２４に出力する。これにより、スイッチ２４では、端子２４Ａまたは２４Ｂのうちの、選択された予測方式（以下、適宜、選択予測方式という）で予測を行う予測器が接続された方が選択される。
【００７６】
そして、ステップＳ１３に進み、予測器２５Ａまたは２５Ｂのうちの、選択予測方式で予測を行う予測器（以下、適宜、選択予測器という）において、注目画素の予測値が、選択予測方式にしたがって求められ、その予測値が、予測誤差計算回路２６に出力される。
【００７７】
予測誤差計算回路２６は、ステップＳ１４において、選択予測器からの予測値の予測誤差を求め、予測誤差保存用メモリ２７に供給して記憶させ、リターンする。
【００７８】
一方、ステップＳ１１において、注目画素への埋め込みが不可であると判定された場合、埋め込み判定回路２２は、その旨の埋め込み判定信号を、予測器選択回路２３に出力し、ステップＳ１５に進む。
【００７９】
ステップＳ１５では、予測器選択回路２３は、注目画素と、その予測に用いる画素に基づいて、注目画素を予測する予測方式を選択する。即ち、予測器選択回路２３は、図３に示したように、注目画素Ｄに対して、その上に隣接する画素Ｂ、またはその左に隣接する画素Ｃを予測値とする予測方式のうち、予測誤差が大きくなる方の予測方式を選択し、その選択結果としての予測器選択信号を、スイッチ２４に出力する。これにより、スイッチ２４では、端子２４Ａまたは２４Ｂのうちの、選択された予測方式（選択予測方式）で予測を行う予測器が接続された方が選択される。
【００８０】
そして、ステップＳ１６に進み、予測器２５Ａまたは２５Ｂのうちの、選択予測方式で予測を行う予測器（選択予測器）において、注目画素の予測値が、選択予測方式にしたがって求められ、その予測値が、予測誤差計算回路２６に出力される。
【００８１】
予測誤差計算回路２６は、ステップＳ１７において、選択予測器からの予測値の予測誤差を求め、予測誤差保存用メモリ２７に供給して記憶させ、リターンする。
【００８２】
次に、図８のフローチャートを参照して、図３における画素Ｄを注目画素とした場合の、図６のステップＳ２における埋め込み圧縮処理について、さらに説明する。
【００８３】
埋め込み圧縮処理では、まず最初に、ステップＳ２１において、埋め込み判定回路２２は、注目画素Ｄ、その上に隣接する画素Ｂ、その左に隣接する画素Ｃの大小関係を判定することにより、注目画素への埋め込みの可否を判定する。なお、ステップＳ２１の処理は、図７のステップＳ１１の処理に対応する。
【００８４】
ステップＳ１１において、画素値Ｂ，Ｃ，Ｄの大小関係として、式Ｂ＜Ｄ＜ＣまたはＣ＜Ｄ＜Ｂが成り立つと判定された場合、埋め込み判定回路２２は、注目画素Ｄへの埋め込みが可能である旨の埋め込み判定信号を、予測器選択回路２３に出力し、ステップＳ２２に進む。
【００８５】
ステップＳ２２では、予測器選択回路２３は、注目画素Ｄに埋め込む付加情報が０または１のうちのいずれであるかを判定し、１であると判定した場合、ステップＳ２３に進み、予測器選択回路２３は、画素Ｃを予測値とする予測方式を選択し、その旨の予測器選択信号を、スイッチ２４に出力する。即ち、本実施の形態では、画素Ｃを予測値とする予測方式による予測は、予測器２５Ｂにおいて行われるので、いまの場合、予測器選択回路２３からスイッチ２４に対しては、予測器２５Ｂに接続されている端子２４Ｂの選択を指令する予測器選択信号が供給される。なお、ステップＳ２２およびＳ２３の処理は、図７のステップＳ１２の処理に対応する。
【００８６】
スイッチ２４は、予測器選択回路２３からの予測器選択信号にしたがって、端子２４Ｂを選択し、これにより、予測器２５Ｂは、ステップＳ２４において、フレームメモリ２１から、スイッチ２４を介して、画素Ｃを読み出し、これを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。なお、ステップＳ２４の処理は、図７のステップＳ１３の処理に対応する。
【００８７】
予測誤差計算回路２６は、ステップＳ２５において、予測器２５Ｂからの予測値Ｃの予測誤差Ｄ−Ｃを求め、予測誤差保存用メモリ２７に供給し、リターンする。なお、ステップＳ２４の処理は、図７のステップＳ１４の処理に対応する。
【００８８】
一方、ステップＳ２２において、注目画素Ｄに埋め込む付加情報が０であると判定された場合、ステップＳ２６に進み、予測器選択回路２３は、画素Ｂを予測値とする予測方式を選択し、その旨の予測器選択信号を、スイッチ２４に出力する。即ち、本実施の形態では、画素Ｂを予測値とする予測方式による予測は、予測器２５Ａにおいて行われるので、いまの場合、予測器選択回路２３からスイッチ２４に対しては、予測器２５Ａに接続されている端子２４Ａの選択を指令する予測器選択信号が供給される。なお、ステップＳ２２およびＳ２６の処理は、図７のステップＳ１２の処理に対応する。
【００８９】
スイッチ２４は、予測器選択回路２３からの予測器選択信号にしたがって、端子２４Ａを選択し、これにより、予測器２５Ａは、ステップＳ２７において、フレームメモリ２１から、スイッチ２４を介して、画素Ｂを読み出し、これを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。なお、ステップＳ２７の処理は、図７のステップＳ１３の処理に対応する。
【００９０】
予測誤差計算回路２６は、ステップＳ２８において、予測器２５Ａからの予測値Ｂの予測誤差Ｄ−Ｂを求め、予測誤差保存用メモリ２７に供給し、リターンする。なお、ステップＳ２８の処理は、図７のステップＳ１４の処理に対応する。
【００９１】
一方、ステップＳ２１において、画素値Ｂ，Ｃ，Ｄの大小関係として、式Ｂ＜Ｄ＜ＣおよびＣ＜Ｄ＜Ｂのいずれも成り立たないと判定された場合、即ち、式Ｂ≦Ｃ≦Ｄ，Ｄ≦Ｃ≦Ｂ，Ｃ＜Ｂ≦Ｄ、またはＤ≦Ｂ＜Ｃのうちのいずれかが成り立つ場合、埋め込み判定回路２２は、注目画素Ｄへの埋め込みが不可である旨の埋め込み判定信号を、予測器選択回路２３に出力し、ステップＳ２９に進む。
【００９２】
ステップＳ２９では、予測器選択回路２３は、フレームメモリ２１から、画素Ｂ，Ｃ，Ｄを読み出し、それらの画素値の大小関係を判定する。
【００９３】
ステップＳ２９において、画素値Ｂ，Ｃ，Ｄの大小関係として、式Ｂ≦Ｃ≦ＤまたはＤ≦Ｃ≦Ｂが成り立つと判定された場合、ステップＳ３０に進み、予測器選択回路２３は、画素Ｂを予測値とする予測方式を選択し、その旨の予測器選択信号を、スイッチ２４に出力する。従って、この場合、ステップＳ２６における場合と同様に、スイッチ２４は、端子２４Ａを選択する。なお、ステップＳ２９およびＳ３０の処理は、図７のステップＳ１５の処理に対応する。
【００９４】
ここで、上述したように、注目画素への埋め込みが不可の場合には、注目画素の予測方式として、予測誤差を大きくするものが選択される。式Ｂ≦Ｃ≦ＤまたはＤ≦Ｃ≦Ｂが成り立つ場合には、画素ＢまたはＣをそれぞれ予測値とする予測方式のうち、予測誤差が大きくなるのは、画素Ｂを予測値とする予測方式であるから、ステップＳ３０では、そのような予測方式が選択される。
【００９５】
スイッチ２４が、端子２４Ａを選択すると、予測器２５Ａは、ステップＳ３１において、フレームメモリ２１から、スイッチ２４を介して、画素Ｂを読み出し、これを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。なお、ステップＳ３１の処理は、図７のステップＳ１６の処理に対応する。
【００９６】
予測誤差計算回路２６は、ステップＳ３２において、予測器２５Ａからの予測値Ｂの予測誤差Ｄ−Ｂを求め、予測誤差保存用メモリ２７に供給し、リターンする。なお、ステップＳ３２の処理は、図７のステップＳ１７の処理に対応する。
【００９７】
一方、ステップＳ２９において、画素値Ｂ，Ｃ，Ｄの大小関係として、式Ｃ＜Ｂ≦ＤまたはＤ≦Ｂ＜Ｃが成り立つと判定された場合、ステップＳ３３に進み、予測器選択回路２３は、画素Ｃを予測値とする予測方式を選択し、その旨の予測器選択信号を、スイッチ２４に出力する。従って、この場合、ステップＳ２３における場合と同様に、スイッチ２４は、端子２４Ｂを選択する。なお、ステップＳ２９およびＳ３３の処理は、図７のステップＳ１５の処理に対応する。
【００９８】
ここで、上述したように、注目画素への埋め込みが不可の場合には、注目画素の予測方式として、予測誤差を大きくするものが選択される。式Ｃ＜Ｂ≦ＤまたはＤ≦Ｂ＜Ｃが成り立つ場合には、画素ＢまたはＣをそれぞれ予測値とする予測方式のうち、予測誤差が大きくなるのは、画素Ｃを予測値とする予測方式であるから、ステップＳ３３では、そのような予測方式が選択される。
【００９９】
スイッチ２４が、端子２４Ｂを選択すると、予測器２５Ｂは、ステップＳ３４において、フレームメモリ２１から、スイッチ２４を介して、画素Ｃを読み出し、これを、注目画素Ｄの予測値として、予測誤差計算回路２６に出力する。なお、ステップＳ３４の処理は、図７のステップＳ１６の処理に対応する。
【０１００】
予測誤差計算回路２６は、ステップＳ３５において、予測器２５Ｂからの予測値Ｃの予測誤差Ｄ−Ｃを求め、予測誤差保存用メモリ２７に供給し、リターンする。なお、ステップＳ３５の処理は、図７のステップＳ１７の処理に対応する。
【０１０１】
ここで、図９に、画素値Ｂ，Ｃ，Ｄの大小関係に基づく、埋め込み圧縮処理のルールを示す。
【０１０２】
なお、上述の場合には、画素（の画素値）ＢとＣとが一致している場合には、埋め込みを行わないこととしたが、画素ＢとＣとが一致している場合には、図３に示すように、注目画素Ｄの左上の画素Ａを利用して、注目画素Ｄに、付加情報を埋め込むようにすることも可能である。この場合の埋め込み圧縮処理のルールを、図１０に示す。
【０１０３】
ここで、図１０では、Ｂ＝Ｃの場合に、画素ＡまたはＢを、注目画素Ｄの予測値として用いるようにしているが、ＢとＣとは等しいから、注目画素Ｄの予測としては、画素ＡまたはＣを用いることも可能である。
【０１０４】
次に、図１１は、図１の復号器１２の構成例を示している。
【０１０５】
埋め込み圧縮符号化器１１が出力し、記録媒体３または伝送媒体４を介して供給される符号化データは、フレームメモリ３１に入力され、フレームメモリ３１は、そこに入力される符号化データを、例えば、１フレーム単位で順次記憶する。
【０１０６】
エントロピー復号回路３２は、フレームメモリ３１に記憶された符号化データを、順次読み出してエントロピー復号し、これにより、符号化データを、予測誤差に復号する。この予測誤差は、埋め込み判定回路３３および画素値／付加情報計算回路３４に供給される。
【０１０７】
埋め込み判定回路３３は、エントロピー復号回路３２からの予測誤差を画素値とする画素に、付加情報が埋め込まれているかどうかを判定する。即ち、埋め込み判定回路３３は、エントロピー復号回路３２が出力する予測誤差でなる画像（以下、適宜、予測誤差画像という）を構成する画素を、例えば、ラスタスキャン順に、順次、注目画素とし、その注目画素に、付加情報が埋め込まれているかどうかを、その注目画素の画素値、および復号画像用メモリ３５に記憶された、既に復号された画素の画素値に基づいて判定する。
【０１０８】
具体的には、例えば、いま、図１２に示すように、予測誤差画像を構成する、ある画素ｄが注目画素である場合には、埋め込み判定回路３３は、その注目画素ｄの上に隣接する、既に復号された画素Ｂと、下に隣接する、既に復号された画素Ｃを、復号画像用メモリ３５から読み出す。なお、ここでは、ラスタスキャン順に、画素の復号が行われるので、注目画素の上や左にある画素は、既に復号されている。そして、埋め込み判定回路３３は、これらの画素値ＢおよびＣ、並びに注目画素の画素値ｄに基づいて、注目画素への付加情報の埋め込みの有無を判定する。
【０１０９】
即ち、注目画素の元の画素値をＤとすると、注目画素については、上述したように、その画素値Ｄが、その上に隣接する画素Ｂの画素値と、その左に隣接する画素Ｃの画素値との間に存在する場合に、付加情報の埋め込みが行われ、存在しない場合には、付加情報の埋め込みが行われない。
【０１１０】
従って、注目画素に付加情報が埋め込まれている場合には、その画素値ｄの大きさ｜ｄ｜が、画素値ＢとＣとの差分の大きさ｜Ｂ−Ｃ｜の範囲内にあるはずである。そこで、埋め込み判定回路３３は、画素値ｄの大きさ｜ｄ｜が、画素値ＢとＣとの差分の大きさ｜Ｂ−Ｃ｜の範囲内にあるかどうかを判定し、ある場合には、注目画素ｄへの埋め込みが行われていると判定し、ない場合には、注目画素ｄへの埋め込みが行われていないと判定する。この埋め込み判定回路３３による注目画素への埋め込みの有無の判定結果は、埋め込み判定信号として、画素値／付加情報計算回路３４に供給されるようになっている。
【０１１１】
画素値／付加情報計算回路３４は、埋め込み判定回路３３から、注目画素への埋め込みが行われている旨の埋め込み判定信号を受信した場合、その注目画素を予測した予測方式を、注目画素の画素値、および復号画像用メモリ３５に記憶された、既に復号された画素の画素値に基づいて判定するとともに、注目画素を復号する。
【０１１２】
即ち、画素値／付加情報計算回路３４は、注目画素（予測誤差）ｄの上に隣接する、既に復号された画素Ｂと、左に隣接する、既に復号された画素Ｃを、復号画像用メモリ３５から読み出し、それぞれを注目画素の予測値とする予測方式にしたがって、注目画素ｄを復号する。具体的には、画素値Ｂと、予測誤差である注目画素の画素値ｄとが加算されることにより、画素値Ｂを予測値とする予測方式による復号が行われるとともに、画素値Ｃと、予測誤差である注目画素の画素値ｄとが加算されることにより、画素値Ｃを予測値とする予測方式による復号が行われる。
【０１１３】
画素値／付加情報計算回路３４は、画素値Ｂと予測誤差ｄとの加算値Ｂ＋ｄ、および画素値Ｃと予測誤差ｄとの加算値Ｃ＋ｄを求めると、その２つの加算値Ｂ＋ｄとＣ＋ｄのうち、画素値ＢとＣとの間に存在する方を選択し、その選択した加算値を、注目画素の復号結果として、復号画像用メモリ３５に出力する。
【０１１４】
即ち、注目画素に付加情報が埋め込まれている場合には、上述したことから、注目画素の元の画素値が、画素値ＢとＣとの間に存在するはずであり、このため、画素値／付加情報計算回路３４は、加算値Ｂ＋ｄとＣ＋ｄのうち、画素値ＢとＣとの間に存在する方を選択し、その選択した加算値を、注目画素の復号結果とする。
【０１１５】
さらに、画素値／付加情報計算回路３４は、加算値Ｂ＋ｄとＣ＋ｄのうち、加算値Ｂ＋ｄを復号結果とした場合、予測方式が、画素値Ｂを予測値とするものであると認識する。また、画素値／付加情報計算回路３４は、加算値Ｂ＋ｄとＣ＋ｄのうち、加算値Ｃ＋ｄを復号結果とした場合、予測方式が、画素値Ｃを予測値とするものであると認識する。そして、画素値／付加情報計算回路３４は、予測方式の認識結果に基づいて、注目画素に埋め込まれていた付加情報を復号する。
【０１１６】
即ち、上述したように、埋め込み圧縮符号化器１１では、付加情報が０の場合には、画素Ｂを、注目画素の予測値とする予測方式が用いられ、付加情報が１の場合には、画素値Ｃを、注目画素の予測値とする予測方式が用いられる。そこで、画素値／付加情報計算回路３４は、予測方式が、画素値Ｂを予測値とするものである旨の認識結果が得られた場合には、付加情報として０を復号し、予測方式が、画素値Ｃを予測値とするものである旨の認識結果が得られた場合には、付加情報として１を復号して、付加情報用メモリ３６に供給する。
【０１１７】
従って、予測誤差ｄ、並びに画素値ＢおよびＣの関係が、例えば、図１３（Ａ）に示すように、式Ｃ＜Ｂ＋ｄ＜Ｂで表される場合には、Ｂ＋ｄが注目画素の画素値として復号されるとともに、付加情報として０が復号される。また、予測誤差ｄ、並びに画素値ＢおよびＣの関係が、例えば、図１３（Ｂ）に示すように、式Ｃ＜Ｃ＋ｄ＜Ｂで表される場合には、Ｃ＋ｄが注目画素の画素値として復号されるとともに、付加情報として１が復号される。
【０１１８】
一方、画素値／付加情報計算回路３４は、埋め込み判定回路３３から、注目画素への埋め込みが行われていない旨の埋め込み判定信号を受信した場合、その注目画素を、その画素値、および復号画像用メモリ３５に記憶された、既に復号された画素の画素値に基づいて復号する。
【０１１９】
即ち、上述したように、注目画素の画素値（予測誤差）ｄの大きさ｜ｄ｜が、画素値ＢとＣとの差分の大きさ｜Ｂ−Ｃ｜の範囲内にない場合には、その注目画素には、付加情報は埋め込まれていない。さらに、注目画素に付加情報が埋め込まれていない場合には、埋め込み圧縮符号化器１１において、その注目画素は、画素値ＢとＣをそれぞれ予測値とする予測方式のうち、予測誤差（の大きさ）がより大きくなる方で予測されているはずである。そこで、画素値／付加情報計算回路３４は、上述のような予測方式の選択条件に合致するように、注目画素を復号する。
【０１２０】
具体的には、例えば、図１４に示すように、式Ｃ＜Ｂ＜Ｃ＋ｄが成り立つ場合においては、注目画素ｄが、画素値Ｂを予測値として予測されているとすると、その復号結果は、Ｄ’＝Ｂ＋ｄとなる。しかしながら、Ｄ’が、注目画素の正しい復号結果であるとすると、画素値ＢとＣをそれぞれ予測値とする予測方式のうち、予測誤差がより大きくなる方で予測するという予測方式の選択条件に反する。即ち、Ｄ’を、注目画素の復号結果とするのであれば、注目画素は、予測誤差が大きくなる、画素値Ｃを予測値として予測されているはずであり、画素値Ｂを予測値として復号した復号結果Ｄ’は、正しい復号結果でないということになる。
【０１２１】
そこで、画素値／付加情報計算回路３４は、注目画素ｄが、画素値Ｃを予測値として予測されているとして、注目画素を、Ｄ＝Ｃ＋ｄに復号する。この場合、画素値ＢとＣをそれぞれ予測値とする予測方式のうち、予測誤差がより大きくなる方で予測するという予測方式の選択条件に合致するから、画素値／付加情報計算回路３４は、Ｄを、注目画素の復号結果として、復号画像用メモリ３５に出力する。
【０１２２】
復号画像用メモリ３５は、画素値／付加情報計算回路３４が出力する注目画素の復号結果（復号画素値）を、例えば、その注目画素の位置に対応するアドレスに一時記憶する。付加情報用メモリ３６は、画素値／付加情報計算回路３４が出力する付加情報の復号結果（復号付加情報）を一時記憶する。
【０１２３】
次に、図１５のフローチャートを参照して、図１１の復号器１２の処理について説明する。
【０１２４】
符号化データは、例えば、１フレーム単位で、フレームメモリ３１に、順次供給されて記憶される。
【０１２５】
そして、ある１フレームの符号化データが、フレームメモリ３１に記憶されると、ステップＳ４１において、エントロピー復号回路３２は、フレームメモリ４１に記憶された１フレームの符号化データをエントロピー復号し、予測誤差でなる予測誤差画像に変換する。さらに、ステップＳ４２に進み、予測誤差画像を構成する画素のうち、ラスタスキャン順で、まだ注目画素とされていないものが、注目画素として選択される。
【０１２６】
その後、ステップＳ４３に進み、埋め込み判定回路３３および画素値／付加情報計算回路３４において、注目画素を復号するとともに、その注目画素に付加情報が埋め込まれている場合には、その付加情報を復号（抽出）する付加情報抽出／画素復号処理が行われ、その結果得られる注目画素の復号結果が、画素値／付加情報計算回路３４から復号画像用メモリ３５に供給されて記憶される。さらに、ステップＳ４３において付加情報の復号結果が得られる場合には、その復号結果が、画素値／付加情報計算回路３４から付加情報用メモリ３６に供給されて記憶される。
【０１２７】
そして、ステップＳ４４に進み、エントロピー復号回路３２で復号された１フレームの予測誤差画像を構成するすべての画素を注目画素として処理を行ったかどうかが判定される。ステップＳ４４において、まだ、すべての画素を注目画素としていないと判定された場合、ステップＳ４２に戻り、以下、同様の処理が繰り返される。
【０１２８】
また、ステップＳ４４において、すべての画素を注目画素としたと判定された場合、即ち、復号画像用メモリ３５に、１フレームの復号画像が記憶されるとともに、付加情報用メモリ３６に、その１フレームの復号画像に埋め込まれていた付加情報が記憶された場合、ステップＳ４５に進み、復号画像用メモリ３５から復号画像が読み出されて出力されるとともに、付加情報用メモリ３６から付加情報が読み出されて出力され、処理を終了する。
【０１２９】
なお、図１５の処理は、例えば、フレームメモリ３１に１フレームの符号化データが記憶されるごとに行われる。
【０１３０】
次に、図１６のフローチャートを参照して、図１５のステップＳ４３における付加情報抽出／画素復号処理について説明する。
【０１３１】
付加情報抽出／画素復号処理では、まず最初に、ステップＳ５１において、埋め込み判定回路３３は、注目画素に対する付加情報の埋め込みの有無を判定する。ステップＳ５１において、注目画素に付加情報が埋め込まれていると判定された場合、埋め込み判定回路３３は、その旨の埋め込み判定信号を、画素値／付加情報計算回路３４に出力し、ステップＳ５２に進む。
【０１３２】
ステップＳ５２では、画素値／付加情報計算回路３４は、注目画素の画素値である予測誤差、およびその注目画素の左または上にそれぞれ隣接する、既に復号され、復号画像用メモリ３５に記憶されている画素の画素値に基づいて、注目画素の予測に用いられた予測方式を認識する。
【０１３３】
ここで、本実施の形態では、ラインスキャン順に処理を行うので、上述したように、注目画素の上や左にある画素は、既に復号されている。また、この場合、注目画素が、１フレームの最も上の行の画素であるときや、最も左の列の画素であるときには、その上や左に隣接する画素が存在しないこととなるが、このようなときは、復号器１２において、例えば、注目画素の上や左に、画素値が０の画素、あるいは注目画素と同一の画素が存在するものとして処理を行うこととする。埋め込み圧縮符号化器１１においても同様とする。
【０１３４】
画素値／付加情報計算回路３４は、予測方式を認識した後、ステップＳ５２からＳ５３に進み、その認識した予測方式（以下、適宜、認識予測方式という）に基づいて、注目画素を復号するとともに、そこに埋め込まれていた付加情報を復号し、リターンする。
【０１３５】
一方、ステップＳ５１において、注目画素に付加情報が埋め込まれていないと判定された場合、埋め込み判定回路３３は、その旨の埋め込み判定信号を、画素値／付加情報計算回路３４に出力し、ステップＳ５４に進む。
【０１３６】
ステップＳ５４では、画素値／付加情報計算回路３４は、注目画素の画素値である予測誤差、およびその注目画素の左または上にそれぞれ隣接する、既に復号され、復号画像用メモリ３５に記憶されている画素の画素値に基づいて、注目画素の予測に用いられた予測方式を認識し、ステップＳ５５に進む。
【０１３７】
ステップＳ５５では、画素値／付加情報計算回路３４は、ステップＳ５４で認識した予測方式（認識予測方式）に基づいて、注目画素を復号し、リターンする。
【０１３８】
次に、図１７のフローチャートを参照して、図１２における画素（予測誤差）ｄを注目画素とした場合の、図１５のステップＳ４３における付加情報抽出／画素復号処理について、さらに説明する。
【０１３９】
付加情報抽出／画素復号処理では、まず最初に、ステップＳ６１において、埋め込み判定回路３３は、注目画素ｄ、その上に隣接する、既に復号された画素Ｂ、その左に隣接する、既に復号された画素Ｃの大小関係を判定することにより、注目画素ｄへの埋め込みの有無を判定する。なお、ステップＳ６１の処理は、図１６のステップＳ５１の処理に対応する。
【０１４０】
ステップＳ６１において、画素値Ｂ，Ｃ，ｄの大小関係として、式Ｂ＜Ｂ＋ｄ＜Ｃ，Ｃ＜Ｂ＋ｄ＜Ｂ，Ｂ＜Ｃ＋ｄ＜Ｃ、またはＣ＜Ｃ＋ｄ＜Ｂのうちのいずれかが成り立つと判定された場合、埋め込み判定回路３３は、注目画素ｄへの埋め込みが行われている旨の埋め込み判定信号を、画素値／付加情報計算回路３４に出力し、ステップＳ６２に進む。
【０１４１】
ステップＳ６２では、画素値／付加情報計算回路３４は、画素値Ｂ，Ｃ，ｄの大小関係を判定し、これにより、注目画素の予測に用いられた予測方式を認識する。
【０１４２】
即ち、ステップＳ６２において、画素値Ｂ，Ｃ，ｄの大小関係として、式Ｂ＜Ｂ＋ｄ＜ＣまたはＣ＜Ｂ＋ｄ＜Ｂのうちのいずれかが成り立つと判定された場合、ステップＳ６３に進み、画素値／付加情報計算回路３４は、画素値Ｂを予測値とする予測方式が用いられたことを認識し、ステップＳ６４に進む。なお、ステップＳ６２およびＳ６３の処理は、図１５のステップＳ５２の処理に対応する。
【０１４３】
ステップＳ６４では、画素値／付加情報計算回路３４は、ステップＳ６３で認識された予測方式（認識予測方式）に基づき、その認識予測方式で予測値とされる画素値Ｂに、注目画素の画素値である予測誤差ｄを加算することで、注目画素の復号結果としての画素値Ｂ＋ｄを得て、復号画像用メモリ３５に出力する。さらに、画素値／付加情報計算回路３４は、認識予測方式に基づき、付加情報の復号結果として０を得て、付加情報用メモリ３６に出力し、リターンする。なお、ステップＳ６４の処理は、図１５のステップＳ５３の処理に対応する。
【０１４４】
また、ステップＳ６２において、画素値Ｂ，Ｃ，ｄの大小関係として、式Ｂ＜Ｃ＋ｄ＜ＣまたはＣ＜Ｃ＋ｄ＜Ｂのうちのいずれかが成り立つと判定された場合、ステップＳ６５に進み、画素値／付加情報計算回路３４は、画素値Ｃを予測値とする予測方式が用いられたことを認識し、ステップＳ６６に進む。なお、ステップＳ６２およびＳ６５の処理は、図１５のステップＳ５２の処理に対応する。
【０１４５】
ステップＳ６６では、画素値／付加情報計算回路３４は、ステップＳ６５で認識された予測方式（認識予測方式）に基づき、その認識予測方式で予測値とされる画素値Ｃに、注目画素の画素値である予測誤差ｄを加算することで、注目画素の復号結果としての画素値Ｃ＋ｄを得て、復号画像用メモリ３５に出力する。さらに、画素値／付加情報計算回路３４は、認識予測方式に基づき、付加情報の復号結果として１を得て、付加情報用メモリ３６に出力し、リターンする。なお、ステップＳ６６の処理は、図１５のステップＳ５３の処理に対応する。
【０１４６】
一方、ステップＳ６１において、画素値Ｂ，Ｃ，ｄの大小関係として、式Ｂ＜Ｂ＋ｄ＜Ｃ，Ｃ＜Ｂ＋ｄ＜Ｂ，Ｂ＜Ｃ＋ｄ＜Ｃ、およびＣ＜Ｃ＋ｄ＜Ｂのうちのいずれも成り立たないと判定された場合、即ち、式Ｂ≦Ｃ≦Ｂ＋ｄ，Ｂ＋ｄ≦Ｃ＜Ｂ，Ｃ＋ｄ≦Ｂ≦Ｃ、またはＣ＜Ｂ≦Ｂ＋ｄのうちのいずれかが成り立つ場合、埋め込み判定回路３３は、注目画素ｄへの埋め込みが行われていない旨の埋め込み判定信号を、画素値／付加情報計算回路３４に出力し、ステップＳ６７に進む。
【０１４７】
ステップＳ６７では、画素値／付加情報計算回路３４は、画素値Ｂ，Ｃ，ｄの大小関係を判定することにより、注目画素の予測に用いられた予測方式を認識する。
【０１４８】
ステップＳ６７において、画素値Ｂ，Ｃ，ｄの大小関係として、式Ｂ≦Ｃ≦Ｂ＋ｄまたはＢ＋ｄ≦Ｃ＜Ｂのうちのいずれかが成り立つと判定された場合、ステップＳ６８に進み、画素値／付加情報計算回路３４は、画素値Ｂを予測値とする予測方式が用いられたことを認識し、ステップＳ６９に進む。なお、ステップＳ６７およびＳ６８の処理は、図１５のステップＳ５４の処理に対応する。
【０１４９】
ステップＳ６９では、画素値／付加情報計算回路３４は、ステップＳ６８で認識された予測方式（認識予測方式）に基づき、その認識予測方式で予測値とされる画素値Ｂに、注目画素の画素値である予測誤差ｄを加算することで、注目画素の復号結果としての画素値Ｂ＋ｄを得て、復号画像用メモリ３５に出力し、リターンする。なお、ステップＳ６９の処理は、図１５のステップＳ５５の処理に対応する。
【０１５０】
また、ステップＳ６７において、画素値Ｂ，Ｃ，ｄの大小関係として、式Ｃ＋ｄ≦Ｂ≦Ｃ、またはＣ＜Ｂ≦Ｂ＋ｄのうちのいずれかが成り立つと判定された場合、ステップＳ７０に進み、画素値／付加情報計算回路３４は、画素値Ｃを予測値とする予測方式が用いられたことを認識し、ステップＳ７１に進む。なお、ステップＳ６７およびＳ７０の処理は、図１５のステップＳ５４の処理に対応する。
【０１５１】
ステップＳ７１では、画素値／付加情報計算回路３４は、ステップＳ７０で認識された予測方式（認識予測方式）に基づき、その認識予測方式で予測値とされる画素値Ｃに、注目画素の画素値である予測誤差ｄを加算することで、注目画素の復号結果としての画素値Ｃ＋ｄを得て、復号画像用メモリ３５に出力し、リターンする。なお、ステップＳ７１の処理は、図１５のステップＳ５５の処理に対応する。
【０１５２】
ここで、図１８に、画素値Ｂ，Ｃ，ｄの大小関係に基づく、符号化データの復号処理のルールを示す。
【０１５３】
なお、図１０に示したように、画素ＢとＣとが一致している場合において、注目画素の左上の画素Ａを利用して、注目画素に、付加情報を埋め込むようにしたときには、画素値および付加情報の復号は、やはり、その左上の画素Ａを利用して行うことができ、その場合の復号処理のルールを、図１９に示す。
【０１５４】
以上のように、注目画素の予測に用いる予測方式を、付加情報に基づいて選択し、その選択した予測方式に基づいて、注目画素を予測して、その予測値の予測誤差を得るようにしたので、その予測誤差は、上述のように、その予測に用いられた予測方式を認識することで、元の画素値と付加情報に復号することができる。即ち、復号器１２では、符号化データを、復号のためのオーバヘッドなしで、元の画像（画像の劣化のない画像）および付加情報に復号することができる。なお、このことは、埋め込み圧縮符号化器１１側からすれば、オーバヘッドなしで、完全可逆の圧縮符号化を行うことができることになる。
【０１５５】
ここで、上述の場合には、注目画素Ｄの予測値の予測誤差をｄとして、式｜Ｂ−Ｃ｜＞｜ｄ｜が成り立つ場合にのみ、注目画素Ｄに、付加情報を埋め込むようにしたが、式｜Ｂ−Ｃ｜＝｜ｄ｜が成り立つ場合にも、注目画素Ｄに、付加情報を埋め込むようにすることが可能である。但し、この場合、注目画素の画素値が、画素値ＢまたはＣと等しく、かつ、予測誤差ｄが０となるときには、復号器１２において、注目画素の予測値として、画素値ＢまたはＣのうちのいずれを用いたかの判定（用いられた予測方式の認識）が困難となる。そこで、本実施の形態では、式｜Ｂ−Ｃ｜＝｜ｄ｜が成り立つ場合には、注目画素への付加情報の埋め込みを行わないようにしている。
【０１５６】
また、本実施の形態では、注目画素Ｄに、付加情報を埋め込まない場合には、画素値ＢとＣのうち、予測誤差ｄが大きくなる方を、注目画素Ｄの予測値として用いるようにしたが、これは、次のような理由による。即ち、本実施の形態では、式｜Ｂ−Ｃ｜＞｜ｄ｜が成り立つ場合にのみ、注目画素Ｄに、付加情報を埋め込むようにしており、さらに、その埋め込みは、注目画素Ｄの予測に用いる予測方式を、付加情報に基づいて選択することによって行われる。従って、付加情報を埋め込まない場合において、画素値ＢとＣのうち、予測誤差ｄが小さくなる方を、注目画素Ｄの予測値として用いるようにすると、式｜Ｂ−Ｃ｜＞｜ｄ｜が成り立つようになり、復号器１２において、注目画に対する付加情報の埋め込みの有無の判定が困難となるからである。
【０１５７】
次に、上述の場合には、埋め込み圧縮符号化器１２において、符号化対象の画像に対して、何らかの付加情報を埋め込むようにしたが、埋め込み圧縮符号化器１２においては、図２０に示すように、符号化対象の画像を、付加情報が埋め込まれる画像（以下、適宜、基盤画像という）と、その基盤画像に埋め込む埋め込み対象画像とに分離し、その埋め込み対象画像を圧縮して付加情報とし、この付加情報を、基盤画像に埋め込んで、符号化データとするようにすることが可能である。そして、この場合、復号器１２においては、図２１に示すように、符号化データを、元の基盤画像と付加情報に復号し、さらに、付加情報を、元の埋め込み対象画像に復号（伸張）して、基盤画像と結合することにより、元の画像の復号を行うようにすることが可能である。
【０１５８】
そこで、図２２は、符号化対象の画像を、基盤画像と埋め込み対象画像とに分離して、基盤画像に、埋め込み対象画像を埋め込む場合の、図１の埋め込み圧縮符号化器１１の構成例を示している。
【０１５９】
なお、図中、図２における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図２２の埋め込み圧縮符号化器１１は、分離回路４１、圧縮器４２、および付加情報用メモリ４３が新たに設けられている他は、図２における場合と同様に構成されている。
【０１６０】
分離回路４１は、フレームメモリ２１に記憶された１フレームの画像を、基盤画像と埋め込み対象画像とに最適に分離する。即ち、分離回路４１は、基盤画像に対して、埋め込み対象画像を最適に埋め込むことができるように、フレームメモリ２１に記憶された画像を、圧縮器４２の出力に基づいて、基盤画像と埋め込み対象画像とに分離する。
【０１６１】
ここで、最適な埋め込みとは、基盤画像に対する、埋め込み対象画像の埋め込みが次のように行われることを意味する。即ち、基盤画像に埋め込むことのできるデータ量は、その基盤画像を構成する画素数によって異なる。また、基盤画像に埋め込む付加情報のデータ量は、埋め込み対象画像が、圧縮器４２で、どの程度圧縮されるかによって異なる。そこで、最適な埋め込みとは、基盤画像に対して、圧縮器４２で圧縮された埋め込み対象画像としての付加情報が、過不足なく埋め込まれた状態を意味する。なお、本来は、画像を、１画素単位で、基盤画像と埋め込み画像とに分離するのが望ましいが、ここでは、処理が煩雑になるのを避けるため、分離回路４１は、画像を、１水平ライン単位で、基盤画像と埋め込み画像とに分離するものとする。
【０１６２】
分離回路４１で得られた基盤画像を構成する各画素は、埋め込み判定回路２２、予測器選択回路２３、スイッチ２４，予測誤差計算回路２６に供給されるようになっており、また、埋め込み対象画像は、圧縮器４２に供給されるようになっている。
【０１６３】
圧縮器４２は、分離回路４１からの埋め込み対象画像を、例えば、隣接する画素どうしの差分をとり、その差分値をハフマン符号化すること等により圧縮し、付加情報とする。この付加情報は、付加情報用メモリ４３に供給されるようになっており、さらに、その付加情報のデータ量は、分離回路４１に供給されるようになっている。
【０１６４】
付加情報用メモリ４３は、圧縮器４２が出力する付加情報を、一時記憶するようになっており、この付加情報は、例えば、１ビット単位で、予測器選択回路２３に供給されるようになっている。
【０１６５】
次に、図２３のフローチャートを参照して、図２２の埋め込み圧縮符号化器１１の処理について説明する。
【０１６６】
符号化対象の画像データは、例えば、１フレーム単位で、フレームメモリ２１に、順次供給されて記憶される。
【０１６７】
そして、ある１フレームの画像データが、フレームメモリ２１に記憶されると、ステップＳ８１において、分離回路４１は、フレームメモリ２１に記憶された１フレームの画像を、例えば、最後の１水平ラインと、残りの部分とに分離し、最後の１水平ラインを埋め込み対象画像とするとともに、残りを、基盤画像として、埋め込み対象画像を、圧縮器４２に出力する。圧縮器４２は、ステップＳ８２において、分離回路４１からの埋め込み対象画像を圧縮し、付加情報とする。さらに、圧縮器４２は、その付加情報のデータ量を、分離回路４１に出力する。
【０１６８】
分離回路４１は、圧縮器４２から付加情報のデータ量を受信すると、基盤画像に対し、図９に示したようなルールで埋め込むことのできるデータ量（以下、適宜、埋め込みスペースという）を算出し、ステップＳ８３に進み、埋め込みスペースと、付加情報のデータ量との関係が最適かどうかを判定する。
【０１６９】
ステップＳ８３において、埋め込みスペースと、付加情報のデータ量との関係が最適でないと判定された場合、即ち、ここでは、埋め込みスペースが、付加情報のデータ量に対して大である場合、ステップＳ８４に進み、分離回路４１は、埋め込み対象画像の水平ライン数が、例えば、１水平ラインだけ増えるように、フレームメモリ２１に記憶された画像を分離する分離点を変更する。そして、ステップＳ８１に戻り、分離回路４１は、ステップＳ８４で変更された分離点で、フレームメモリ２１に記憶された画像を分離し、以下、同様の処理を繰り返す。
【０１７０】
一方、ステップＳ８３において、埋め込みスペースと、付加情報のデータ量との関係が最適であると判定された場合、即ち、ここでは、付加情報のデータ量が、埋め込みスペースを超えない範囲で最大となった場合、分離回路４１は、そのときの基盤画像を、埋め込み判定回路２２、予測器選択回路２３、スイッチ２４、および予測誤差計算回路２６に出力する。さらに、圧縮器４２は、付加情報を、付加情報用メモリ４３に供給して記憶させる。
【０１７１】
そして、ステップＳ８５乃至Ｓ８９に順次進み、図６のステップＳ１乃至Ｓ５における場合とそれぞれ同様の処理が行われ、処理を終了する。
【０１７２】
なお、図６のステップＳ３に対応する図２３のステップＳ８７では、フレームメモリ２１に記憶された画像を構成するすべての画素が注目画素とされたかどうかではなく、分離回路４１で得られた基盤画像を構成するすべての画素が注目画素とされたかどうかが判定される。また、図６のステップＳ１に対応する図２３のステップＳ８５では、基盤画像から注目画素が選択される。
【０１７３】
ここで、図２３の処理も、例えば、図６の処理と同様に、フレームメモリ２１に１フレームの画像データが記憶されるごとに行われる。
【０１７４】
次に、図２２の埋め込み圧縮符号化器１１には、図２３ではなく、図２４のフローチャートにしたがった処理を行わせることも可能である。
【０１７５】
即ち、この場合、ステップＳ９１において、分離回路４１は、フレームメモリ２１に記憶された１フレームの画像を、例えば、最後の１水平ラインと、残りの部分とに分離し、最後の１水平ラインを埋め込み対象画像とするとともに、残りを、基盤画像として、埋め込み対象画像を、圧縮器４２に出力する。圧縮器４２は、ステップＳ９２において、分離回路４１からの埋め込み対象画像を圧縮し、付加情報として、付加情報用メモリ４３に供給して記憶させる。
【０１７６】
そして、以下、ステップＳ９３乃至Ｓ９５に進み、図２３のステップＳ８５乃至Ｓ８７における場合とそれぞれ同様の処理が行われ、これにより、基盤画像に対して、付加情報用メモリ４３に記憶された付加情報すべてが埋め込まれ、予測誤差保存用メモリ２７には、基盤画像の予測値の予測誤差でなる予測誤差画像が記憶される。
【０１７７】
その後、ステップＳ９６に進み、予測誤差画像とされた基盤画像を構成する画素のうち、付加情報の埋め込みが可能なものが残っているかどうか、即ち、埋め込みスペースが余っているかどうかが判定される。ステップＳ９６において、埋め込みスペースが余っていると判定された場合、ステップＳ９７に進み、分離回路４１は、図２３のステップＳ８４における場合と同様に、埋め込み対象画像の水平ライン数が、例えば、１水平ラインだけ増えるように、フレームメモリ２１に記憶された画像を分離する分離点を変更する。そして、ステップＳ９１に戻り、分離回路４１は、ステップＳ９７で変更された分離点で、フレームメモリ２１に記憶された画像を分離し、以下、同様の処理を繰り返す。
【０１７８】
一方、ステップＳ９６において、埋め込みスペースが余っていないと判定された場合、即ち、埋め込みスペースが足りない場合、ステップＳ９８に進み、エントロピー符号化回路２８は、予測誤差保存用メモリ２７に記憶された、前回得られた予測誤差画像を読み出し、エントロピー符号化する。さらに、エントロピー符号化回路２８は、ステップＳ９９において、その結果得られる符号化データを出力し、処理を終了する。
【０１７９】
なお、図２４の処理も、例えば、フレームメモリ２１に１フレームの画像データが記憶されるごとに行われる。
【０１８０】
次に、図２５は、図２２の埋め込み圧縮符号化器１２が出力する符号化データを、元の画像データに復号する、図１の復号器１２の構成例を示している。
【０１８１】
なお、図中、図１１における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は適宜省略する。即ち、図２５の復号器１２は、伸張器５１および結合器５２が新たに設けられている他は、図１１における場合と同様に構成されている。
【０１８２】
伸張器５１は、付加情報用メモリ３６に記憶された付加情報を復号（伸張）し、元の埋め込み対象画像として、結合器５２に供給する。結合器５２は、伸張器５１からの埋め込み対象画像を、復号画像用メモリ３５に書き込み、これにより、復号画像用メモリ３５に記憶された、復号された基盤画像と埋め込み対象画像とを結合して、元の１フレームの画像を再構成する。
【０１８３】
次に、図２６のフローチャートを参照して、図２５の復号器１２の処理について説明する。
【０１８４】
ステップＳ１０１乃至Ｓ１０４では、図１５のステップＳ４１乃至Ｓ４４における場合とそれぞれ同様の処理が行われる。そして、ステップＳ１０４において、符号化データをエントロピー復号した予測誤差画像を構成する画素すべてを、注目画素としたと判定された場合、即ち、復号画像用メモリ３５に、復号された基盤画像が記憶されるとともに、付加情報用メモリ３６に、その基盤画像に埋め込まれていた付加情報が記憶された場合、ステップＳ１０５に進み、伸張器５１は、付加情報用メモリ３６に記憶された付加情報を、埋め込み対象画像に復号し、結合器５２に供給する。結合器５２は、ステップＳ１０６において、伸張器５１からの埋め込み対象画像を、復号画像用メモリ３５に書き込むことにより、復号された基盤画像と埋め込み対象画像とを結合して、元の１フレームの画像を、復号画像用メモリ３５の中に再構成する。そして、ステップＳ１０７に進み、復号画像用メモリ３５に記憶された、再構成された画像が読み出されて出力され、処理を終了する。
【０１８５】
ここで、本件発明者が行ったシミュレーションにより得られた、図２２の埋め込み圧縮符号化器１１により画像を処理した場合の圧縮率と、従来の予測符号化による圧縮率とを、図２７に示す。なお、従来の予測符号化による圧縮率とは、注目画素の左側に隣接する画素を予測値として予測誤差を求め、その予測誤差をハフマン符号化した場合の圧縮率である。
【０１８６】
図２７から、画像＃１および＃２のいずれついても、図２２の埋め込み圧縮符号化器１１により画像を処理した場合の方が、従来の予測符号化を行った場合に比較して、圧縮率が向上していることが分かる。
【０１８７】
なお、上述の場合には、埋め込み対象画像を圧縮して付加情報とし、基盤画像に埋め込むようにしたが、埋め込み対象画像は、そのまま付加情報として、基盤画像に埋め込むことも可能である。
【０１８８】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０１８９】
そこで、図２８は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０１９０】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク１０５やＲＯＭ１０３に予め記録しておくことができる。
【０１９１】
あるいはまた、プログラムは、フロッピーディスク、CD-ROM(Compact Disc Read Only Memory)，MO(Magneto optical)ディスク，DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体１１１に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体１１１は、いわゆるパッケージソフトウエアとして提供することができる。
【０１９２】
なお、プログラムは、上述したようなリムーバブル記録媒体１１１からコンピュータにインストールする他、ダウンロードサイトから、ディジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを、通信部１０８で受信し、内蔵するハードディスク１０５にインストールすることができる。
【０１９３】
コンピュータは、CPU(Central Processing Unit)１０２を内蔵している。CPU１０２には、バス１０１を介して、入出力インタフェース１１０が接続されており、CPU１０２は、入出力インタフェース１１０を介して、ユーザによって、キーボードやマウス等で構成される入力部１０７が操作されることにより指令が入力されると、それにしたがって、ROM(Read Only Memory)１０３に格納されているプログラムを実行する。あるいは、また、CPU１０２は、ハードディスク１０５に格納されているプログラム、衛星若しくはネットワークから転送され、通信部１０８で受信されてハードディスク１０５にインストールされたプログラム、またはドライブ１０９に装着されたリムーバブル記録媒体１１１から読み出されてハードディスク１０５にインストールされたプログラムを、RAM(Random Access Memory)１０４にロードして実行する。これにより、CPU１０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、CPU１０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース１１０を介して、LCD(Liquid CryStal Display)やスピーカ等で構成される出力部１０６から出力、あるいは、通信部１０８から送信、さらには、ハードディスク１０５に記録等させる。
【０１９４】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０１９５】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０１９６】
なお、本実施の形態では、注目画素の左や、上、左上に隣接する画素を、注目画素の予測値として用いるようにしたが、注目画素の予測値としては、その他の画素（例えば、注目画素に対して、空間的または時間的に近い位置にある画素）を用いることも可能である。
【０１９７】
さらに、注目画素の予測値としては、その左や、上、左上に隣接する画素そのものではなく、例えば、それらから線形予測を行うことにより得られる値等を用いることも可能である。
【０１９８】
また、本実施の形態では、２つの予測方式を用意し、付加情報によって、いずれの予測方式を用いるかを選択するようにしたが、予測方式は、３以上のＮ個用意することが可能であり、その場合には、１の画素に対して、付加情報を、ｌｏｇ2Ｎビット単位で埋め込むことが可能となる。
【０１９９】
さらに、本実施の形態では、画像に付加情報を埋め込むようにしたが、その他、例えば、オーディオデータやプログラム等に、付加情報を埋め込むようにすることも可能である。
【０２００】
【発明の効果】
本発明の第１の側面によれば、完全可逆の埋め込みの実現が可能となる。
【０２０１】
本発明の第２の側面によれば、符号化データを、オーバーヘッドなしで、第１および第２のデータに復号することが可能となる。
【図面の簡単な説明】
【図１】本発明を適用した埋め込み圧縮／復号システムの一実施の形態の構成例を示す図である。
【図２】図１の埋め込み圧縮符号化器１１の構成例を示すブロック図である。
【図３】図２の埋め込み判定回路２２の処理を説明するための図である。
【図４】注目画素への付加情報の埋め込みが可能な場合を示す図である。
【図５】注目画素への付加情報の埋め込みが付加の場合を示す図である。
【図６】図２の埋め込み圧縮符号化器１１の処理を説明するためのフローチャートである。
【図７】図６のステップＳ２の処理の詳細を説明するためのフローチャートである。
【図８】図６のステップＳ２の処理のより詳細を説明するためのフローチャートである。
【図９】図２の埋め込み圧縮符号化器１１の処理のルールを示す図である。
【図１０】図２の埋め込み圧縮符号化器１１の処理のルールを示す図である。
【図１１】図１の復号器１２の構成例を示すブロック図である。
【図１２】図１１の埋め込み判定回路３３の処理を説明するための図である。
【図１３】画素に付加情報が埋め込まれている場合の、その画素と付加情報の復号方法を説明するための図である。
【図１４】画素に付加情報が埋め込まれていない場合の、その画素の復号方法を説明するための図である。
【図１５】図１１の復号器１２の処理を説明するためのフローチャートである。
【図１６】図１５のステップＳ４３の処理の詳細を説明するためのフローチャートである。
【図１７】図１５のステップＳ４３の処理のより詳細を説明するためのフローチャートである。
【図１８】図１１の復号器１２の処理のルールを示す図である。
【図１９】図１１の復号器１２の処理のルールを示す図である。
【図２０】画像の一部に、その残りを埋め込む処理を説明するための図である。
【図２１】画像の一部に、その残りが埋め込まれたものを復号する処理を説明するための図である。
【図２２】図１の埋め込み圧縮符号化器１１の他の構成例を示すブロック図である。
【図２３】図２２の埋め込み圧縮符号化器１１の処理を説明するためのフローチャートである。
【図２４】図２２の埋め込み圧縮符号化器１１の処理を説明するためのフローチャートである。
【図２５】図１の復号器１２の他の構成例を示すブロック図である。
【図２６】図２５の復号器１２の処理を説明するためのフローチャートである。
【図２７】本件発明者によるシミュレーション結果を示す図である。
【図２８】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
１  符号化装置，  ２  復号装置，  ３  記録媒体，  ４  伝送媒体，  １１埋め込み圧縮符号化器，  １２  復号器，  ２１  フレームメモリ，  ２２  埋め込み判定回路，  ２３  予測器選択回路，  ２４  スイッチ，  ２４Ａ，２４Ｂ  端子，  ２５Ａ，２５Ｂ  予測器，  ２６  予測誤差計算回路，  ２７  予測誤差保存用メモリ，  ２８  エントロピー符号化回路，  ３１  フレームメモリ，  ３２  エントロピー復号回路，  ３３  埋め込み判定回路，  ３４  画素値／付加情報計算回路，  ３５  復号画像用メモリ，  ３６  付加情報用メモリ，  ４１  分離回路，  ４２  圧縮器，  ４３  付加情報用メモリ，  ５１  伸張器，  ５２  結合器，  １０１  バス，  １０２  CPU，  １０３  ROM，  １０４  RAM，  １０５  ハードディスク，  １０６  出力部，  １０７  入力部，  １０８  通信部，  １０９  ドライブ，  １１０  入出力インタフェース，  １１１  リムーバブル記録媒体
【図１】
0004254003.tif 000002
【図２】
0004254003.tif 000003
【図３】
0004254003.tif 000004
【図４】
0004254003.tif 000005
【図５】
0004254003.tif 000006
【図６】
0004254003.tif 000007
【図７】
0004254003.tif 000008
【図８】
0004254003.tif 000009
【図９】
0004254003.tif 000010
【図１０】
0004254003.tif 000011
【図１１】
0004254003.tif 000012
【図１２】
0004254003.tif 000013
【図１３】
0004254003.tif 000014
【図１４】
0004254003.tif 000015
【図１５】
0004254003.tif 000016
【図１６】
0004254003.tif 000017
【図１７】
0004254003.tif 000018
【図１８】
0004254003.tif 000019
【図１９】
0004254003.tif 000020
【図２０】
0004254003.tif 000021
【図２１】
0004254003.tif 000022
【図２２】
0004254003.tif 000023
【図２３】
0004254003.tif 000024
【図２４】
0004254003.tif 000025
【図２５】
0004254003.tif 000026
【図２６】
0004254003.tif 000027
【図２７】
0004254003.tif 000028
【図２８】
0004254003.tif 000029