(57)【特許請求の範囲】
【請求項１】
第１のデータを、第２のデータにしたがって符号化する符号化装置であって、
前記第１のデータの少なくとも一部のデータを記憶する記憶手段と、
前記第２のデータにしたがって、前記記憶手段に記憶された前記一部のデータを入れ替えることにより、前記第１のデータに、前記第２のデータに関連するデータを埋め込む符号化手段と
を備え、
前記第１のデータの一部は、前記符号化手段による入れ替えが禁止されている
符号化装置。
【請求項２】
前記第１および第２のデータを入力する入力手段をさらに備える
請求項１に記載の符号化装置。
【請求項３】
前記第１のデータは、複数の画素データから構成される画像データであり、
前記記憶手段は、前記画像データを記憶し、
前記符号化手段は、前記記憶手段に記憶された前記画像データを構成する１以上の画素データの集合の位置を、前記第２のデータにしたがって入れ替えることにより、前記画像データに、前記第２のデータに関連するデータを埋め込む
請求項１に記載の符号化装置。
【請求項４】
前記符号化手段は、前記画像データの画枠内にある１以上の前記画素データの集合の位置を、前記第２のデータにしたがって入れ替える
請求項３に記載の符号化装置。
【請求項５】
前記符号化手段は、前記画像データを構成する画素データの位置を、１行または１列単位で入れ替える
請求項３に記載の符号化装置。
【請求項６】
前記符号化手段は、前記画像データを構成する１以上の画素データの集合の位置を、前記第２のデータの値に相当する画素数に応じて入れ替える
請求項３に記載の符号化装置。
【請求項７】
第１のデータを、第２のデータにしたがって符号化する符号化方法であって、
前記第１のデータの少なくとも一部のデータを記憶する記憶ステップと、
前記第２のデータにしたがって、前記記憶ステップで記憶された前記一部のデータを入れ替えることにより、前記第１のデータに、前記第２のデータに関連するデータを埋め込む符号化ステップと
を備え、
前記第１のデータの一部は、前記符号化ステップによる入れ替えが禁止されている
符号化方法。
【請求項８】
第１のデータを、第２のデータにしたがって符号化する符号化処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、
前記第１のデータの少なくとも一部のデータを記憶する記憶ステップと、
前記第２のデータにしたがって、前記記憶ステップで記憶された前記一部のデータを入れ替えることにより、前記第１のデータに、前記第２のデータに関連するデータを埋め込む符号化ステップと
を備え、
前記第１のデータの一部は、前記符号化ステップによる入れ替えが禁止されている
プログラムが記録されている記録媒体。
【請求項９】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号装置であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、
前記関係値計算手段によって求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号手段と
を備え、
前記関係値計算手段は、前記一部のデータと他の一部のデータとの連続性を表す前記関係値を計算する
復号装置。
【請求項１０】
前記第１のデータは、複数の画素データから構成される画像データであり、
前記復号手段は、前記符号化データを構成する前記画素データの位置を、１行または１列単位で入れ替える
請求項９に記載の復号装置。
【請求項１１】
前記復号手段は、前記一部のデータと他の一部のデータとの位置の入れ替えパターンに相当する値を、前記第２のデータとして復号する
請求項９に記載の復号装置。
【請求項１２】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号方法であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、
前記関係値計算ステップにおいて求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記関係値計算ステップでは、前記一部のデータと他の一部のデータとの連続性を表す前記関係値を計算する
復号方法。
【請求項１３】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、
前記関係値計算ステップにおいて求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記関係値計算ステップでは、前記一部のデータと他の一部のデータとの連続性を表す前記関係値を計算する
プログラムが記録されている記録媒体。
【請求項１４】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号装置であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、
前記関係値計算手段によって求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号手段と
を備え、
前記復号手段は、前記一部のデータとの前記関係値を最大にする前記他の一部のデータと、前記一部のデータとが隣接するように入れ替えを行う
復号装置。
【請求項１５】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号方法であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、
前記関係値計算ステップにおいて求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記復号ステップでは、前記一部のデータとの前記関係値を最大にする前記他の一部のデータと、前記一部のデータとが隣接するように入れ替えを行う
復号方法。
【請求項１６】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、
前記関係値計算ステップにおいて求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記復号ステップでは、前記一部のデータとの前記関係値を最大にする前記他の一部のデータと、前記一部のデータとが隣接するように入れ替えを行う
プログラムが記録されている記録媒体。
【請求項１７】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号装置であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、
前記関係値計算手段によって求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号手段と
を備え、
前記符号化データの一部は、前記復号手段による入れ替えが禁止されている
復号装置。
【請求項１８】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号方法であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、
前記関係値計算ステップにおいて求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記符号化データの一部は、前記復号ステップによる入れ替えが禁止されている
復号方法。
【請求項１９】
第１のデータを、第２のデータにしたがって符号化した符号化データを復号する復号処理を、コンピュータに行わせるプログラムが記録されている記録媒体であって、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、
前記関係値計算ステップにおいて求められた前記関係値に基づいて、前記一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号ステップと
を備え、
前記符号化データの一部は、前記復号ステップによる入れ替えが禁止されている
プログラムが記録されている記録媒体。
【請求項２０】
第１のデータを、第２のデータにしたがって符号化して符号化データとし、その符号化データを復号するデータ処理装置であって、
前記第１のデータの少なくとも一部のデータを記憶する記憶手段と、
前記第２のデータにしたがって、前記記憶手段に記憶された前記第１のデータの一部のデータを入れ替えることにより、前記第１のデータに、前記第２のデータに関連するデータを埋め込み、前記符号化データとする符号化手段と、
前記符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、
前記関係値計算手段によって求められた前記関係値に基づいて、前記符号化データの一部のデータと他の一部のデータとの位置を入れ替えることにより、前記符号化データを、前記第１のデータに復号するとともに、その位置の入れ替えに応じて、前記符号化データに埋め込まれていた前記第２のデータを復号する復号手段と
を備え、
前記第１のデータの一部は、前記符号化手段による入れ替えが禁止され、その入れ替えが禁止されている前記第１のデータの一部に対応する、前記符号化データの一部は、前記復号手段による入れ替えが禁止されている
データ処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、符号化装置および符号化方法、復号装置および復号方法、記録媒体、並びにデータ処理装置に関し、特に、例えば、復号画像の画質の劣化を極力なくし、かつデータ量を増加せずに、画像に情報を埋め込むことができるようにする符号化装置および符号化方法、復号装置および復号方法、記録媒体、並びにデータ処理装置に関する。
【０００２】
【従来の技術】
信号に対して、そのデータ量を増加させることなく、情報を埋め込む手法としては、例えば、ディジタルオーディオデータの最下位ビットや、下位２ビットなどを、埋め込む情報に変換するものなどがある。この手法は、ディジタルオーディオデータの下位ビットが、その音質にあまり影響を与えないことを利用し、その下位ビットを、単に、埋め込む情報に置き換えるものであり、従って、再生時には、情報が埋め込まれたディジタルオーディオデータは、その下位ビットを元に戻さずに、そのまま出力される。即ち、情報が埋め込まれた下位ビットを、元に戻すのは困難であり、また、下位ビットは、音質に、あまり影響を与えないことから、ディジタルオーディオデータは、情報が埋め込まれた状態で出力される。
【０００３】
【発明が解決しようとする課題】
しかしながら、以上のような手法では、本来の信号と異なる信号が出力される。従って、信号がオーディオデータである場合には、その音質に、また、信号がビデオデータである場合には、その画質に、少なからず影響がある。
【０００４】
本発明は、このような状況に鑑みてなされたものであり、画像の画質の劣化を極力なくし、かつデータ量を増加せずに、画像に情報を埋め込むことができるようにするものである。
【０００５】
【課題を解決するための手段】
本発明の第１の側面の符号化装置は、第１のデータの少なくとも一部のデータを記憶する記憶手段と、第２のデータにしたがって、記憶手段に記憶された一部のデータを入れ替えることにより、第１のデータに、第２のデータに関連するデータを埋め込む符号化手段とを備え、第１のデータの一部は、符号化手段による入れ替えが禁止されている符号化装置である。
【００１２】
本発明の第１の側面の符号化方法は、第１のデータの少なくとも一部のデータを記憶する記憶ステップと、第２のデータにしたがって、記憶ステップで記憶された一部のデータを入れ替えることにより、第１のデータに、第２のデータに関連するデータを埋め込む符号化ステップとを備え、第１のデータの一部は、符号化ステップによる入れ替えが禁止されている符号化方法である。
【００１３】
本発明の第１の側面の記録媒体は、第１のデータの少なくとも一部のデータを記憶する記憶ステップと、第２のデータにしたがって、記憶ステップで記憶された一部のデータを入れ替えることにより、第１のデータに、第２のデータに関連するデータを埋め込む符号化ステップとを備え、第１のデータの一部は、符号化ステップによる入れ替えが禁止されているプログラムが記録されている記録媒体である。
【００１４】
本発明の第２の側面の復号装置は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、関係値計算手段によって求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号手段とを備え、関係値計算手段は、一部のデータと他の一部のデータとの連続性を表す関係値を計算する復号装置である。
【００２０】
本発明の第２の側面の復号方法は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、関係値計算ステップにおいて求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号ステップとを備え、関係値計算ステップでは、一部のデータと他の一部のデータとの連続性を表す関係値を計算する復号方法である。
【００２１】
本発明の第２の側面の記録媒体は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、関係値計算ステップにおいて求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号ステップとを備え、関係値計算ステップでは、一部のデータと他の一部のデータとの連続性を表す関係値を計算するプログラムが記録されている記録媒体である。
本発明の第３の側面の復号装置は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、関係値計算手段によって求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号手段とを備え、復号手段は、一部のデータとの関係値を最大にする他の一部のデータと、一部のデータとが隣接するように入れ替えを行う復号装置である。
本発明の第３の側面の復号方法は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、関係値計算ステップにおいて求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号ステップとを備え、復号ステップでは、一部のデータとの関係値を最大にする他の一部のデータと、一部のデータとが隣接するように入れ替えを行う復号方法である。
本発明の第３の側面の記録媒体は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、関係値計算ステップにおいて求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号ステップとを備え、復号ステップでは、一部のデータとの関係値を最大にする他の一部のデータと、一部のデータとが隣接するように入れ替えを行うプログラムが記録されている記録媒体である。
本発明の第４の側面の復号装置は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、関係値計算手段によって求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号手段とを備え、符号化データの一部は、復号手段による入れ替えが禁止されている復号装置である。
本発明の第４の側面の復号方法は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、関係値計算ステップにおいて求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号ステップとを備え、符号化データの一部は、復号ステップによる入れ替えが禁止されている復号方法である。
本発明の第４の側面の記録媒体は、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算ステップと、関係値計算ステップにおいて求められた関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号ステップとを備え、符号化データの一部は、復号ステップによる入れ替えが禁止されているプログラムが記録されている記録媒体である。
【００２２】
本発明の第５の側面のデータ処理装置は、第１のデータの少なくとも一部のデータを記憶する記憶手段と、第２のデータにしたがって、記憶手段に記憶された第１のデータの一部のデータを入れ替えることにより、第１のデータに、第２のデータに関連するデータを埋め込み、符号化データとする符号化手段と、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値を計算する関係値計算手段と、関係値計算手段によって求められた関係値に基づいて、符号化データの一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データを、第１のデータに復号するとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータを復号する復号手段とを備え、第１のデータの一部は、符号化手段による入れ替えが禁止され、その入れ替えが禁止されている第１のデータの一部に対応する、符号化データの一部は、復号手段による入れ替えが禁止されているデータ処理装置である。
【００２３】
本発明の第１の側面においては、第１のデータの少なくとも一部のデータが記憶され、第２のデータにしたがって、記憶された一部のデータを入れ替えることにより、第１のデータに、第２のデータに関連するデータが埋め込まれる。但し、第１のデータの一部は、入れ替えが禁止されている。
【００２４】
本発明の第２ないし第４の側面においては、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値が計算され、その関係値に基づいて、一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データが、第１のデータに復号されるとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータが復号される。
そして、第２の側面では、関係値として、一部のデータと他の一部のデータとの連続性を表す値が計算される。
第３の側面では、一部のデータとの関係値を最大にする他の一部のデータと、一部のデータとが隣接するように入れ替えが行われる。
第４の側面では、符号化データの一部は、入れ替えが禁止されている。
【００２５】
本発明の第５の側面においては、第１のデータの少なくとも一部のデータが記憶され、第２のデータにしたがって、記憶された第１のデータの一部のデータを入れ替えることにより、第１のデータに、第２のデータに関連するデータが埋め込まれ、符号化データとされる。一方、符号化データの一部のデータと、他の一部のデータとの関係を表す関係値が計算され、その関係値に基づいて、符号化データの一部のデータと他の一部のデータとの位置を入れ替えることにより、符号化データが、第１のデータに復号されるとともに、その位置の入れ替えに応じて、符号化データに埋め込まれていた第２のデータが復号される。但し、第１のデータの一部は、入れ替えが禁止され、その入れ替えが禁止されている第１のデータの一部に対応する、符号化データの一部も、入れ替えが禁止されている。
【００２６】
【発明の実施の形態】
図１は、本発明を適用した画像伝送システム（システムとは、複数の装置が論理的に集合した物をいい、各構成の装置が同一筐体中にあるか否かは問わない）の一実施の形態の構成例を示している。
【００２７】
この画像伝送システムは、符号化装置１０および復号装置２０で構成されており、符号化装置１０は、符号化対象としての、例えば、画像を符号化して符号化データを出力し、復号装置２０は、その符号化データを、元の画像に復号するようになされている。
【００２８】
即ち、画像データベース１は、符号化すべき画像（例えば、ディジタル画像）を記憶している。そして、画像データベース１からは、そこに記憶されている画像が読み出され、埋め込み符号化器３に供給される。
【００２９】
また、付加情報データベース２は、符号化対象の画像に埋め込むべき情報としての付加情報（ディジタルデータ）を記憶している。そして、付加情報データベース２からも、そこに記憶されている付加情報が読み出され、埋め込み符号化器３に供給される。
【００３０】
埋め込み符号化器３では、画像データベース１からの画像、および付加情報データベース２からの付加情報が受信される。さらに、埋め込み符号化器３は、画像データベース１からの画像が有するエネルギの偏りを利用して復号を行うことができるように、その画像を、付加情報データベース２からの付加情報にしたがって符号化して出力する。即ち、埋め込み符号化器３は、画像が有するエネルギの偏りを利用して復号を行うことができるように、画像に付加情報を埋め込むことで、その画像を符号化し、符号化データを出力する。埋め込み符号化器３が出力する符号化データは、例えば、半導体メモリ、光磁気ディスク、磁気ディスク、光ディスク、磁気テープ、相変化ディスクなどでなる記録媒体４に記録され、あるいは、また、例えば、地上波、衛星回線、ＣＡＴＶ（Cable Television）網、インターネット、公衆回線などでなる伝送媒体５を介して伝送され、復号装置２０に提供される。
【００３１】
復号装置２０は、埋め込み復号器６で構成され、そこでは、記録媒体４または伝送媒体５を介して提供される符号化データが受信される。さらに、埋め込み復号器６は、その符号化データを、画像が有するエネルギの偏りを利用して、元の画像および付加情報に復号する。復号された画像は、例えば、図示せぬモニタに供給されて表示される。
【００３２】
なお、付加情報としては、例えば、元の画像に関連するテキストデータや、音声データ、その画像を縮小した縮小画像等は勿論、元の画像に無関係なデータも用いることができる。
【００３３】
次に、図１の埋め込み符号化器３における符号化（埋め込み符号化）、および埋め込み復号器６における復号（埋め込み復号）の原理について説明する。
【００３４】
一般に、情報と呼ばれるものは、エネルギ（エントロピー）の偏り（普遍性）を有し、この偏りが、情報（価値ある情報）として認識される。即ち、例えば、ある風景を撮影して得られる画像が、そのような風景の画像であると人によって認識されるのは、画像（画像を構成する各画素の画素値など）が、その風景に対応したエネルギの偏りを有するからであり、エネルギの偏りがない画像は、雑音等にすぎず、情報としての利用価値はない。
【００３５】
従って、価値ある情報に対して、何らかの操作を施し、その情報が有する本来のエネルギの偏りを、いわば破壊した場合でも、その破壊されたエネルギの偏りを元に戻すことで、何らかの操作が施された情報も、元の情報に戻すことができる。即ち、情報を符号化して得られる符号化データは、その情報が有する本来のエネルギの偏りを利用して、元の価値ある情報に復号することができる。
【００３６】
ここで、情報が有するエネルギ（の偏り）を表すものとしては、例えば、相関性、連続性、相似性などがある。
【００３７】
情報の相関性とは、その情報の構成要素（例えば、画像であれば、その画像を構成する画素やラインなど）どうしの相関（例えば、自己相関や、ある構成要素と他の構成要素との距離など）を意味する。例えば、画像の相関性を表すものとしては、画像のライン間の相関があり、この相関を表す相関値としては、例えば、２つのラインにおける、対応する各画素値の差分の２乗和等を用いることができる（この場合、相関値が小さいことは、ライン間の相関が大きいことを表し、相関値が大きいことは、ライン間の相関が小さいことを表す）。
【００３８】
即ち、例えば、いま、図２に示すようなＨライン１０２を有する画像１０１があった場合に、その上から１行目のライン（第１ライン）１０３と、他のラインとの相関は、一般に、図３（Ａ）に示すように、第１ライン１０３との距離が近いライン（図２における画像１０１の上側のライン）ほど、第Ｍライン１０４についての相関２０１として示すように大きくなり、第１ライン１０３との距離が遠いライン（図２における画像の下側のライン）ほど、第Ｎライン１０５についての相関２０２として示すように小さくなる。従って、第１ライン１０３から近いほど、第１ライン１０３との相関が大きくなり、遠いほど相関が小さくなるという相関の偏りがある。
【００３９】
そこで、いま、図２の画像１０１において、第１ライン１０３から比較的近い第Ｍライン１０４と、第１ライン１０３から比較的遠い第Ｎライン１０５との画素値を入れ替える操作を行い（１＜Ｍ＜Ｎ≦Ｈ）、その入れ替え後の画像１０１について、第１ライン１０３と、他のラインとの相関を計算値すると、それは、例えば、図３（Ｂ）に示すようになる。
【００４０】
即ち、入れ替え後の画像１０１では、第１ライン１０３から近い第Ｍライン（入れ替え前の第Ｎライン１０５）との相関２０３が小さくなり、第１ライン１０３から遠い第Ｎライン（入れ替え前の第Ｍライン１０４）との相関２０４が大きくなる。
【００４１】
従って、図３（Ｂ）では、第１ライン１０３から近いほど相関が大きくなり、遠いほど相関が小さくなるという相関性の偏りが破壊されている。しかしながら、画像については、一般に、第１ライン１０３から近いほど相関が大きくなり、遠いほど相関が小さくなるという相関性の偏りを利用することにより、破壊された相関性の偏りを復元することができる。即ち、図３（Ｂ）において、第１ライン１０３から近い第Ｍラインとの相関２０３が小さく、第１ライン１０３から遠い第Ｎラインとの相関２０４が大きいのは、画像１０１が有する本来の相関性の偏りからすれば、明らかに不自然であり（おかしく）、第Ｍラインと第Ｎラインとは入れ替えるべきである。そして、図３（Ｂ）における第Ｍラインと第Ｎラインとを入れ替えることで、図３（Ａ）に示すような本来の相関性の偏りを有する画像、即ち、元の画像１０１を復号することができる。
【００４２】
ここで、図２および図３で説明した場合においては、ラインの入れ替えが、画像の符号化を行うこととなる。また、その符号化に際し、埋め込み符号化器３では、例えば、何ライン目を移動するかや、どのラインどうしを入れ替えるかなどが、付加情報にしたがって決定されることになる。一方、埋め込み復号器６では、符号化後の画像、即ち、ラインの入れ替えられた画像を、その相関を利用して、ラインを元の位置に入れ替えることにより、元の画像に戻すことが、画像を復号することとなる。さらに、その復号に際し、埋め込み復号器６において、例えば、何ライン目を移動したかや、どのラインどうしを入れ替えたかなどを検出することが、画像に埋め込まれた付加情報を復号することになる。
【００４３】
次に、情報の連続性についてであるが、例えば、画像のある１ラインについて注目した場合に、その注目ラインにおいて、図４（Ａ）に示すような、画素値の変化パターンが連続している波形３０１が観察されたとすると、その注目ラインと離れた他のラインでは、注目ラインとは異なる画素値の変化パターンが観察される。従って、注目ラインと、その注目ラインと離れた他のラインとにおいては、画素値の変化パターンが異なり、連続性においても偏りがある。即ち、画像のある部分の画素値の変化パターンに注目すると、その注目部分に隣接する部分には、同様の画素値の変化パターンが存在し、注目部分から離れるにつれて、異なる画素値の変化パターンが存在するという連続性の偏りがある。
【００４４】
そこで、いま、図４（Ａ）に示した、画像のあるラインにおける、画素値の変化パターンが連続している波形３０１の一部を、例えば、図４（Ｂ）に示すように、離れたラインにおける波形３０２と入れ替える。
【００４５】
この場合、画像の連続性の偏りが破壊される。しかしながら、近接する部分の画素値の変化パターンは連続しており、離れるほど、画素値の変化パターンが異なるという連続性の偏りを利用することにより、破壊された連続性の偏りを復元することができる。即ち、図４（Ｂ）において、波形の一部３０２の画素値の変化パターンが、他の部分の画素値の変化パターンに比較して大きく異なっているのは、波形が有する本来の連続性の偏りからすれば、明らかに不自然であり、他の部分の画素値の変化パターンと異なっている部分３０２は、他の部分の画素値の変化パターンと同様の波形に入れ替えるべきである。そして、そのような入れ替えを行うことで、連続性の偏りが復元され、これにより、図４（Ｂ）に示した波形から、図４（Ａ）に示した元の波形を復号することができる。
【００４６】
ここで、図４で説明した場合においては、波形の一部を、その周辺の画素値の変化パターンとは大きく異なる画素値の変化パターンの波形に入れ替えることが、画像の符号化を行うこととなる。また、その符号化に際し、埋め込み符号化器３では、例えば、波形のどの部分の画素値の変化パターンを入れ替えるのかや、画素値の変化パターンをどの程度大きく変化させるのかなどが、付加情報にしたがって決定されることになる。一方、埋め込み復号器６では、符号化後の信号、即ち、大きく異なる画素値の変化パターンを一部に有する波形を、周辺の画素値の変化パターンは連続しており、離れるほど、画素値の変化パターンが異なるという連続性の偏りを利用して、元の波形に戻すことが、その元の波形を復号することとなる。さらに、その復号に際し、埋め込み復号器６において、例えば、波形のどの部分の画素値の変化パターンが大きく変化していたのかや、画素値の変化パターンがどの程度大きく変化していたのかなどを検出することが、埋め込まれた付加情報を復号することになる。
【００４７】
次に、情報の相似性についてであるが、例えば、風景を撮影した画像等の一部は、画像のフラクタル性（自己相似性）を利用して生成することができることが知られている。即ち、例えば、図５（Ａ）に示すような、海４０１と森４０２を撮影した画像においては、海４０１全体の画素値の変化パターンと、その海４０１の一部の画素値の変化パターンとの相似性は高いが、それらの変化パターンと、海４０１から離れた森４０２の画素値の変化パターンとの相似性は低いという相似性の偏りがある。ここで、画像の相似性は、上述のように画素値の変化パターンを比較して考えるのではなく、エッジ形状を比較して考えても良い。
【００４８】
そこで、いま、図５（Ａ）に示した海４０１の一部４０３と、森４０２の一部４０４とを入れ替える。
【００４９】
この場合、画像の相似性の偏りが破壊され、図５（Ｂ）に示すような画像が得られる。しかしながら、近接する部分の画素値の変化パターンは相似性が高く、離れるほど、画素値の変化パターンの相似性が低くなるという相似性の偏りを利用することにより、破壊された相似性の偏りを復元することができる。即ち、図５（Ｂ）において、海４０１の画像の一部が、海４０１と相似性の低い森４０２の画像の一部４０４になっていること、および森４０２の画像の一部が、森４０２と相似性の低い海４０１の画像の一部４０３となっていることは、画像が有する本来の相似性の偏りからすれば、明らかに不自然である。具体的には、図５（Ｂ）において、海４０１の画像の中の、森４０２の画像の一部４０４についての相似性は、海４０１の他の部分についての相似性に比較して極端に低くなっており、また、森４０２の画像の中の、海４０１の画像の一部４０３についての相似性も、森４０２の他の部分についての相似性に比較して極端に低くなっている。
【００５０】
従って、画像が本来有する相似性の偏りからすれば、海４０１の画像の一部となっている、森４０２の画像の一部４０４と、森４０２の画像の一部となっている、海４０１の画像の一部４０３とは入れ替えるべきである。そして、そのような入れ替えを行うことで、画像の相似性の偏りが復元され、これにより、図５（Ｂ）に示した画像から、図５（Ａ）に示した元の画像を復号することができる。
【００５１】
ここで、図５で説明した場合においては、海４０１の画像の一部４０３と、森４０２の画像の一部４０４とを入れ替えることが、画像の符号化を行うこととなる。また、その符号化に際し、埋め込み符号化器３では、例えば、海４０１の画像のどの部分（画面上の位置）と、森４０２の画像のどの部分とを入れ替えるのかなどが、付加情報にしたがって決定されることになる。一方、埋め込み復号器６では、符号化後の信号、即ち、海４０１の一部が、森４０２の一部４０４となっているとともに、森４０２の一部が、海４０１の一部４０３となっている画像を、周辺の画素値の変化パターンの相似性は高く、離れるほど、画素値の変化パターンの相似性が低くなっていくという相似性の偏りを利用して、元の画像に戻すことが、その元の画像を復号することとなる。さらに、その復号に際し、埋め込み復号器６において、例えば、海の画像のどの部分と、森の画像のどの部分とが入れ替えられていたのかなどを検出することが、埋め込まれた付加情報を復号することになる。
【００５２】
以上のように、埋め込み符号化器３において、符号化対象の画像が有するエネルギの偏りを利用して復号を行うことができるように、その画像を、付加情報にしたがって符号化して、符号化データを出力する場合には、埋め込み復号器６では、その符号化データを、画像が有するエネルギの偏りを利用することにより、復号のためのオーバヘッドなしで、元の画像および付加情報に復号することができる。
【００５３】
また、符号化対象の画像には、付加情報が埋め込まれることで、その埋め込みの結果得られる画像は、元の画像と異なる画像とされ、人が価値ある情報として認識することのできる画像ではなくなることから、符号化対象の画像については、オーバヘッドなしの暗号化を実現することができる。
【００５４】
さらに、完全可逆の電子透かしを実現することができる。即ち、従来の電子透かしでは、例えば、画質にあまり影響のない画素値の下位ビットが、電子透かしに対応する値に、単に変更されていたが、この場合、その下位ビットを、元の値に戻すことは困難である。従って、復号画像の画質は、電子透かしとしての下位ビットの変更により、少なからず劣化する。これに対して、符号化データを、元の画像が有するエネルギの偏りを利用して復号する場合には、劣化のない元の画像および付加情報を得ることができ、従って、付加情報を電子透かしとして用いることで、電子透かしに起因して復号画像の画質が劣化することはない。
【００５５】
また、埋め込まれた付加情報は、符号化データから画像を復号することで取り出すことができるので、画像の符号化結果とともに、オーバヘッドなしでサイドインフォメーションを提供することができる。言い換えれば、付加情報を取り出すためのオーバヘッドなしで、その付加情報を画像に埋め込むことができるので、その埋め込みの結果得られる符号化データは、付加情報の分だけ圧縮（埋め込み圧縮）されているということができる。従って、例えば、ある画像の半分を符号化対象とするとともに、残りの半分を付加情報とすれば、符号化対象である半分の画像に、残りの半分の画像を埋め込むことができるから、この場合、画像は、単純には、１／２に圧縮されることになる。
【００５６】
さらに、符号化データは、元の画像が有するエネルギの偏りという、いわば統計量を利用して復号されるため、誤りに対する耐性の強いものとなる。即ち、ロバスト性の高い符号化であるロバスト符号化（統計的符号化）を実現することができる。
【００５７】
また、符号化データは、元の画像が有するエネルギの偏りを利用して復号されるため、そのエネルギの偏りに特徴があるほど、即ち、例えば、画像については、そのアクティビティが高いほど、あるいは、冗長性が低いほど、多くの付加情報を埋め込むことができる。ここで、上述したように、付加情報の埋め込みの結果得られる符号化データは、付加情報の分だけ圧縮されているということができるが、この圧縮という観点からすれば、符号化対象の情報が有するエネルギの偏りを利用して復号を行うことができるように、その情報を、付加情報にしたがって符号化する方式（埋め込み符号化方式）によれば、画像のアクティビティが高いほど、あるいは、画像の冗長性が低いほど、圧縮率が高くなる。この点、埋め込み符号化方式は、従来の符号化方式と大きく異なる（従来の符号化方式である、例えばＭＰＥＧ（Moving Picture Experts Group）方式などでは、基本的に、画像のアクティビティが高いほど、あるいは、画像の冗長性が低いほど、圧縮率は低くなる）。
【００５８】
さらに、例えば、上述したように、画像を符号化対象とする一方、付加情報として、画像とは異なるメディアの、例えば、音声を用いるようにすることで、音声をキーとして、画像の提供を行うようなことが可能となる。即ち、符号化装置１０側において、例えば、契約者が発話した音声「開けゴマ」など付加情報として画像に埋め込んでおき、復号装置２０側では、ユーザに、音声「開けゴマ」を発話してもらい、その音声と、画像に埋め込まれた音声とを用いて話者認識を行うようにする。このようにすることで、例えば、話者認識の結果、ユーザが契約者である場合にのみ、自動的に、画像を提示するようなことが可能となる。なお、この場合、付加情報としての音声は、いわゆる特徴パラメータではなく、音声波形そのものを用いることが可能である。
【００５９】
また、例えば、音声を符号化対象とする一方、付加情報として、音声とは異なるメディアの、例えば、画像を用いるようにすることで、画像をキーとして、音声の提供を行うようなこと（例えば、顔認識後の音声応答）が可能となる。即ち、符号化装置１０側において、例えば、ユーザへの応答としての音声に、そのユーザの顔の画像を埋め込み、復号装置２０側では、ユーザの顔を撮影し、その結果得られる画像とマッチングする顔画像が埋め込まれている音声を出力するようにすることで、ユーザごとに異なる音声応答を行う音声応答システムを実現することが可能となる。
【００６０】
さらに、音声に、音声を埋め込んだり、画像に、画像を埋め込んだりするような、あるメディアの情報に、それと同一メディアの情報を埋め込むようなことも可能である。あるいは、また、画像に、契約者の音声と顔画像を埋め込んでおけば、ユーザの音声と顔画像とが、画像に埋め込まれているものと一致するときのみ、その画像を提示するようにする、いわば二重鍵システムなどの実現も可能となる。
【００６１】
また、例えば、テレビジョン放送信号を構成する、いわば同期した画像と音声のうちのいずれか一方に、他方を埋め込むようなことも可能であり、この場合、異なるメディアの情報どうしを統合した、いわば統合符号化を実現することができる。
【００６２】
さらに、埋め込み符号化方式では、上述したように、情報には、そのエネルギの偏りに特徴があるほど、多くの付加情報を埋め込むことができる。従って、例えば、ある２つの情報について、エネルギの偏りに特徴がある方を適応的に選択し、その選択した方に、他方を埋め込むようにすることで、全体のデータ量を制御することが可能となる。即ち、２つの情報どうしの間で、一方の情報によって、他方の情報量を、いわば吸収するようなことが可能となる。そして、このように全体のデータ量を制御することができる結果、伝送路の伝送帯域や使用状況、その他の伝送環境にあったデータ量による情報伝送（環境対応ネットワーク伝送）が可能となる。
【００６３】
また、例えば、画像に、その画像を縮小した画像を埋め込むことで（あるいは、音声に、その音声を間引いたものを埋め込むことで）、データ量を増加することなく、いわゆる階層符号化（下位階層の情報を少なくすることにより、上位階層の情報を生成する符号化）を実現することができる。
【００６４】
さらに、例えば、画像に、その画像を検索するためのキーとなる画像を埋め込んでおくことで、そのキーとなる画像に基づいて、画像の検索を行うデータベースを実現することが可能となる。
【００６５】
次に、図６は、画像の相関性を利用して元に戻すことができるように、画像に付加情報を埋め込む埋め込み符号化を行う場合の図１の埋め込み符号化器３のハードウェアの構成例を示している。
【００６６】
画像データベース１から供給される画像は、フレームメモリ３１に供給されるようになされており、フレームメモリ３１は、画像データベース１からの画像を、例えば、フレーム単位で一時記憶するようになされている。
【００６７】
ＣＰＵ（Central Processing Unit）３２は、プログラムメモリ３３に記憶されたプログラムを実行することで、後述する埋め込み符号化処理を行うようになされている。即ち、ＣＰＵ３２は、プログラムメモリ３３に記憶されたプログラムにしたがって、付加情報データベース２から供給される付加情報を受信し、その付加情報を、フレームメモリ３１に記憶された画像に埋め込むようになされている。具体的には、ＣＰＵ３２は、フレームメモリ３１に記憶された画像を構成する画素の位置を、例えば、１列（垂直方向に並ぶ画素列）単位で、付加情報に基づいて入れ替える（スワップする）ことで、各列に、付加情報を埋め込むようになされている。この付加情報が埋め込まれた画像は、符号化データとして出力されるようになされている。
【００６８】
プログラムメモリ３３は、例えば、ＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）などで構成され、ＣＰＵ３２に、埋め込み符号化処理を行わせるためのコンピュータプログラムを記憶している。
【００６９】
なお、フレームメモリ３１は、複数のフレームを記憶することのできるように、複数バンクで構成されており、バンク切り替えを行うことで、フレームメモリ３１では、画像データベース１から供給される画像の記憶、ＣＰＵ３２による埋め込み符号化処理の対象となっている画像の記憶、および埋め込み符号化処理後の画像（符号化データ）の出力を、同時に行うことができるようになされている。これにより、画像データベース１から供給される画像が、動画であっても、符号化データのリアルタイム出力を行うことができるようになされている。
【００７０】
次に、図７は、図６の埋め込み符号化器３の機能的な構成例を示している。なお、この図７に示した機能的な構成は、ＣＰＵ３２がプログラムメモリ３３に記憶されたコンピュータプログラムを実行することで実現されるようになされている。
【００７１】
フレームメモリ３１は、図６で説明したように、画像データベース１から供給される画像を一時記憶するようになされている。
【００７２】
スワップ情報生成部３６は、付加情報データベース２から付加情報を読み出し、その付加情報に基づいて、フレームメモリ３１に記憶された１フレームの画像の各列の位置を、どのように入れ替えるかを表すスワップ情報を生成するようになされている。即ち、フレームメモリ３１に記憶された１フレームの画像が、Ｍ行Ｎ列の画素で構成される場合において、その画像の第ｎ列（左からｎ番目の列）を、第ｎ’列に入れ替えるときには、スワップ情報生成部３６において、ｎとｎ’とが対応付けられたスワップ情報が生成される（ｎ，ｎ’は、１以上Ｎ以下の整数）。
【００７３】
ここで、１フレームの画像の列数がＮ列である場合、その入れ替え方は、そのすべての列を入れ替えの対象とすると、Ｎ！（！は、階乗を表す）通りだけある。従って、この場合、１フレームには、最大で、ｌｏｇ2（Ｎ！）ビットの付加情報の埋め込みが可能となる。
【００７４】
スワップ情報生成部３６で生成されたスワップ情報は、スワッピング部３７に供給されるようになされている。スワッピング部３７は、スワップ情報生成部３６から供給されるスワップ情報にしたがって、フレームメモリ３１に記憶された１フレームの画像の各列の位置を入れ替えるようになされている。
【００７５】
次に、図８のフローチャートを参照して、図７の埋め込み符号化器３において行われる埋め込み符号化処理について説明する。
【００７６】
画像データベース１からは、そこに記憶されている画像が読み出され、フレームメモリ３１に、順次供給されて記憶される。
【００７７】
一方、スワップ情報生成部３６では、ステップＳ１において、１フレームの画像に埋め込み可能なデータ量の付加情報が、付加情報データベース２から読み出される。即ち、例えば、上述したように、１フレームの画像の列数がＮ列であり、そのすべての列を入れ替えの対象とする場合には、１フレームには、最大で、ｌｏｇ2（Ｎ！）ビットの付加情報の埋め込みが可能であるから、そのようなビット数（以下）の付加情報が、付加情報データベース２から読み出される。
【００７８】
そして、スワップ情報生成部３６は、ステップＳ２に進み、ステップＳ１で読み出した付加情報に基づいて、スワップ情報を生成する。即ち、スワップ情報生成部３６は、付加情報に基づき、フレームメモリ３１に記憶された処理対象のフレームの第１列乃至第Ｎ列のうちの、例えば、第１列を除く第２列乃至第Ｎ列それぞれを、第何列に入れ替えるかを表すスワップ情報を生成する。このスワップ情報は、スワッピング部３７に供給される。
【００７９】
スワッピング部３７は、スワップ情報生成部３６からスワップ情報を受信すると、ステップＳ３に進み、そのスワップ情報にしたがって、フレームメモリ３１に記憶された処理対象のフレームの各列の位置を入れ替える。そして、列の位置の入れ替えが行われたフレームは、フレームメモリ３１から読み出され、符号化データとして出力される。
【００８０】
なお、フレームの各列の位置の入れ替えは、フレームメモリ３１における画像データ（を構成する画素）の記憶位置を変更することで行うことができるが、その他、例えば、フレームメモリ３１からフレームを読み出すときのアドレスを制御することによって、結果として、列の位置の入れ替えが行われたフレームが、フレームメモリ３１から読み出されるようにしても良い。
【００８１】
また、本実施の形態では、上述したように、スワップ情報には、第２列乃至第Ｎ列それぞれを、第何列に入れ替えるかを表す情報が含まれているが、第１列を、第何列に入れ替えるかを表す情報は含まれていない。従って、スワッピング部３７では、第２列乃至第Ｎ列それぞれの入れ替えは行われるが、第１列の入れ替えは行われない。
【００８２】
処理対象のフレームの第２列乃至第Ｎ列すべての入れ替えが終了すると、ステップＳ４に進み、フレームメモリ３１に、まだ処理の対象とされていないフレームが記憶されているかどうかが判定され、記憶されていると判定された場合、ステップＳ１に戻り、まだ処理されていないフレームを対象に、同様の処理が繰り返される。
【００８３】
また、ステップＳ４において、フレームメモリ３１に、まだ処理の対象とされていないフレームが記憶されていないと判定された場合、埋め込み符号化処理を終了する。
【００８４】
以上のような埋め込み符号化処理によれば、ある１フレームの画像は、次のような符号化データに符号化される。
【００８５】
即ち、いま、付加情報が、例えば、図９に示すように、Ｎ列（図９（Ａ））の処理対象フレームの第２列を第６列に（図９（Ｂ））、第３列を第９列に（図９（Ｃ））、第４列を第７列に（図９（Ｄ））、第５列を第３列に（図９（Ｅ））、第６列を第８列に（図９（Ｆ））、第７列を第４列に（図９（Ｇ））、第８列を第５列に（図９（Ｈ））、第９列を第２列に（図９（Ｉ））、・・・、第Ｎ列を第Ｎ列に、それぞれ入れ替えるものに対応するとすると、そのような入れ替えを表すスワップ情報が、スワップ情報生成部３６において生成される。そして、スワッピング部３７では、例えば、図９（Ｊ）に示すようなフレームが、上述のようなスワップ情報にしたがい、第２列が第６列に、第３列が第９列に、第４列が第７列に、第５列が第３列に、第６列が第８列に、第７列が第４列に、第８列を第５列に、第９列が第２列に、・・・、第Ｎ列が第Ｎ列に、それぞれ入れ替えられる。その結果、図９（Ｊ）の画像は、図９（Ｋ）に示すような画像に符号化される。
【００８６】
ここで、図９における第１列乃至第９列に注目して、埋め込み符号化処理について、さらに説明する。
【００８７】
本実施の形態では、第１列は入れ替えの対象になっていない（禁止されている）ので、まず、第２列については、第１列乃至第９列のうちの第１列を除く第２列乃至第９列の合計８列の中から入れ替え先が決定される。この場合、第２列の入れ替え先は８通り存在するので、付加情報として、例えば、０乃至７の８通りの値のうちのいずれかを埋め込むことが可能である。いま、第２列乃至第８列への入れ替えに、それぞれ０乃至７の付加情報を割り当てると、図９（Ｂ）に示したように、第２列が第６列に入れ替えられる場合は、第６列への入れ替えに割り当てられた４が、付加情報として埋め込まれることになる。
【００８８】
第２列が第６列に入れ替えられると、残りの入れ替え先は第２列乃至第５列および第７列乃至第９列の合計７列となり、第３列については、この７列の中から入れ替え先が決定される。従って、この場合、付加情報として、例えば、０乃至６の７通りの値のうちのいずれかを埋め込むことが可能である。いま、上述した場合と同様に、第２列乃至第５列、第７列乃至第９列への入れ替えに、それぞれ０乃至６の付加情報を割り当てると、図９（Ｃ）に示したように、第３列が第９列に入れ替えられる場合は、第９列への入れ替えに割り当てられた６が、付加情報として埋め込まれることになる。
【００８９】
以下、同様にして、画像に付加情報が埋め込まれるが、このような埋め込み手法による場合には、付加情報の埋め込みが進行するほど、埋め込み可能な付加情報のビット数が減少していくことになる。
【００９０】
以上のように、フレームメモリ３１に記憶された画像を構成する１以上の画素の集合としての、各列の画素の位置を、付加情報に対応して入れ替えることにより、各列に、付加情報を埋め込む場合には、その逆の入れ替えを行うことで、元の画像を復号することができ、さらに、どのような入れ替えを行ったかということが付加情報となる。従って、画像の画質の劣化を極力なくし、かつデータ量を増加せずに、画像に付加情報を埋め込むことができる。
【００９１】
即ち、付加情報が埋め込まれた画像である、列の位置の入れ替えが行われた画像の各列は、その画像の相関性、即ち、ここでは、元の画像と同様の正しい位置にある列との間の相関を利用することにより、オーバヘッドなしで、元の位置に入れ替えることができ、さらに、その入れ替え方により、付加情報を復号ことができる。従って、その結果得られる復号画像（再生画像）には、基本的に、付加情報を埋め込むことによる画質の劣化は生じない。
【００９２】
なお、符号化データに、正しい位置にある列が存在しない場合には、上述のように画像の相関性を利用して、画像と付加情報を復号するのは困難である。そこで、ここでは、図８の埋め込み符号化処理において、各フレームの第１列は、入れ替えを行わないで、そのまま、符号化データとして出力するようにしている。
【００９３】
但し、第１列を含むすべての列を入れ替えの対象として、埋め込み符号化を行うことも可能であり、この場合、入れ替え後の列の少なくとも１以上の元の位置を、オーバヘッドとして、符号化データに含めることで、画像と付加情報の復号が容易に可能となる。
【００９４】
また、付加情報は、上述のように、列を、順次入れ替えることにより、画像に埋め込んでいく他、すべての列を一度に入れ替えることにより、画像に埋め込むことも可能である。この場合、すべての列を一度に入れ替えるときの場合の数は、その列数の階乗通りだけあるが、その階乗通りの中から、どのような入れ替えパターンを選択するかが、付加情報によって決定される。また、その復号は、付加情報が埋め込まれた画像について、すべての列の階乗通りの入れ替えが行われ、その階乗通りの入れ替えパターンの中から、相関に基づいて、１つの入れ替えパターンが決定されることにより行われる。
【００９５】
さらに、ここでは、画像の列を、付加情報そのものにしたがって入れ替えるようにしたが、列の入れ替えは、その他、例えば、付加情報の特徴量（例えば、付加情報のヒストグラムや、分散、ダイナミックレンジ等）に応じて行うようにすることも可能である。
【００９６】
次に、図１０は、図７の埋め込み符号化器３が出力する符号化データを、画像の相関性を利用して元の画像と付加情報に復号する図１の埋め込み復号器６のハードウェアの構成例を示している。
【００９７】
符号化データ、即ち、付加情報が埋め込まれた画像（以下、適宜、埋め込み画像ともいう）は、フレームメモリ４１に供給されるようになされており、フレームメモリ４１は、埋め込み画像を、例えば、フレーム単位で一時記憶するようになされている。なお、フレームメモリ４１も、図６のフレームメモリ３１と同様に構成され、バンク切り替えを行うことにより、埋め込み画像が、動画であっても、そのリアルタイム処理が可能となっている。
【００９８】
ＣＰＵ４２は、プログラムメモリ４３に記憶されたプログラムを実行することで、埋め込み復号処理を行うようになされている。即ち、ＣＰＵ４２は、フレームメモリ４１に記憶された埋め込み画像を、画像の相関性を利用して元の画像と付加情報に復号するようになされている。具体的には、ＣＰＵ４２は、埋め込み画像を構成する列のうち、既に復号した最新の列と、他の列との相関を計算する。そして、既に復号した列との相関を最大にする列を、その既に復号した列の右隣の位置に入れ替えることを、埋め込み画像を構成するすべての列について行うことで、元の画像を復号し、さらに、埋め込み画像を元の画像に復号する際の、埋め込み画像の各列の位置の入れ替え方に基づいて、付加情報を復号する。
【００９９】
プログラムメモリ４３は、例えば、図６のプログラムメモリ３３と同様に構成され、ＣＰＵ４２に、埋め込み復号処理を行わせるためのコンピュータプログラムを記憶している。
【０１００】
次に、図１１は、図１０の埋め込み復号器６の機能的な構成例を示している。なお、この図１１に示した機能的な構成は、ＣＰＵ４２がプログラムメモリ４３に記憶されたコンピュータプログラムを実行することで実現されるようになされている。
【０１０１】
フレームメモリ４１は、図１０で説明したように、埋め込み画像を一時記憶するようになされている。
【０１０２】
スワッピング部４６は、フレームメモリ４１に記憶された処理対象のフレームの、既に元の位置に入れ替えられた最新の列と、他の列（まだ、元の位置に戻されていない列）との相関を計算し、その相関に基づいて、処理対象のフレームの中の、まだ元の位置に戻されていない列の位置を入れ替えることで元に戻す（列の位置を復号する）ようになされている。さらに、スワッピング部４６は、フレームの各列をどのように入れ替えたかを表すスワップ情報を、スワップ情報変換部４７に供給するようにもなされている。
【０１０３】
スワップ情報変換部４７は、スワッピング部４６からのスワップ情報、即ち、処理対象のフレームの各列の、入れ替え前の位置と、入れ替え後の位置との対応関係に基づいて、埋め込み画像に埋め込まれた付加情報を復号するようになされている。
【０１０４】
次に、図１２のフローチャートを参照して、図１１の埋め込み復号器６において行われる埋め込み復号処理について説明する。
【０１０５】
フレームメモリ４１では、そこに供給される埋め込み画像（符号化データ）が、例えば、１フレーム単位で順次記憶される。
【０１０６】
一方、スワッピング部４６では、ステップＳ１１において、フレームの列数をカウントするための変数ｎに、初期値としての、例えば、１がセットされ、ステップＳ１２に進み、変数ｎが、フレームの列数であるＮから１を減算したＮ−１以下であるかどうかが判定される。
【０１０７】
ステップＳ１２において、変数ｎがＮ−１以下であると判定された場合、ステップＳ１３に進み、スワッピング部４６は、フレームメモリ４１に記憶された処理対象のフレームから、第ｎ列の画素（画素列）を読み出し、その第ｎ列の各画素（の画素値）を要素として並べたベクトル（以下、適宜、列ベクトルという）ｖnを生成する。ここで、本実施の形態では、上述したように、フレームがＭ行の画素で構成されるから、列ベクトルｖn（後述する列ベクトルｖkも同様）は、Ｍ次元のベクトルとなる。
【０１０８】
その後、ステップＳ１４において、第ｎ列より右側にある列をカウントするための変数ｋに、初期値としてのｎ＋１がセットされ、ステップＳ１５に進み、スワッピング部４６は、第ｋ列の画素を読み出し、その第ｋ列の画素を要素とする列ベクトルｖkを生成して、ステップＳ１６に進む。
【０１０９】
ステップＳ１６では、スワッピング部４６において、列ベクトルｖnおよびｖkを用いて、第ｎ列と第ｋ列との相関が求められる。
【０１１０】
即ち、スワッピング部４６では、列ベクトルｖnとｖkとの距離ｄ（ｎ，ｋ）が、次式にしたがって計算される。
【０１１１】
0004182603.tif 000002
但し、上式において、Σは、ｍを、１からＭに変化させてのサメーションを表す。また、また、Ａ（ｉ，ｊ）は、処理対象になっているフレームの第ｉ行第ｊ列の画素（画素値）を表す。
【０１１２】
そして、スワッピング部４６では、列ベクトルｖnとｖkとの距離ｄ（ｎ，ｋ）の逆数１／ｄ（ｎ，ｋ）が、第ｎ列と第ｋ列との相関（を表す相関値）として求められる。
【０１１３】
第ｎ列と第ｋ列との相関の算出後は、ステップＳ１７に進み、変数ｋが、フレームの列数であるＮから１を減算したＮ−１以下であるかどうかが判定される。ステップＳ１７において、変数ｋがＮ−１以下であると判定された場合、ステップＳ１８に進み、変数ｋが１だけインクリメントされ、ステップＳ１５に戻り、以下、ステップＳ１７において、変数ｋがＮ−１以下でないと判定されるまで、ステップＳ１５乃至Ｓ１８の処理を繰り返す。即ち、これにより、第ｎ列と、それより右側にある埋め込み画像の列それぞれとの相関が求められる。
【０１１４】
その後、ステップＳ１７において、変数ｋがＮ−１以下でないと判定されると、ステップＳ１８に進み、スワッピング部４６において、第ｎ列との相関を最大にするｋが求められる。そして、第ｎ列との相関を最大にするｋを、例えばＫと表すと、スワッピング部４６は、ステップＳ２０において、フレームメモリ４１に記憶された処理対象のフレームの第ｎ＋１列と第Ｋ列とをスワッピング、即ち、第Ｋ列を、第ｎ列の右隣の第ｎ＋１列に入れ替える。
【０１１５】
その後、ステップＳ２１において、変数ｎが１だけインクリメントされ、ステップＳ１２に戻り、以下、ステップＳ１２において、変数ｎがＮ−１以下でないと判定されるまで、ステップＳ１２乃至Ｓ２１の処理を繰り返す。
【０１１６】
ここで、本実施の形態では、埋め込み画像の第１列は、元の画像の第１列のままであるから、変数ｎが、初期値である１のときは、第１列との相関が最も高い埋め込み画像の列が、第１列の右隣の第２列に入れ替えられる。第１列との相関が最も高い列は、画像の相関性から、基本的に、元の画像の第２列であるから、この場合、埋め込み符号化処理において、埋め込み画像のどこかの列に入れ替えられた元の画像の第２列は、元の位置に戻される（復号される）ことになる。
【０１１７】
そして、変数ｎが２となると、上述したようにして元の位置に入れ替えられた第２列との相関が最も高い埋め込み画像の列が、その第２列の右隣の第３列に入れ替えられる。第２列との相関が最も高い列は、やはり、画像の相関性から、基本的に、元の画像の第３列であるから、この場合、埋め込み符号化処理において、埋め込み画像のどこかの列に入れ替えられた元の画像の第３列は、元の位置に戻されることになる。
【０１１８】
以下、同様にして、フレームメモリ４１に記憶された埋め込み画像は、元の画像に復号されていく。
【０１１９】
そして、ステップＳ１２において、変数ｎがＮ−１以下でないと判定された場合、即ち、埋め込み画像を構成する第２列乃至第Ｎ列すべてが、画像の相関性を利用して元の位置に戻され、これにより、フレームメモリ４１に記憶された埋め込み画像が、元の画像が復号された場合、ステップＳ２２に進み、その復号された画像が、フレームメモリ４１から読み出される。さらに、ステップＳ２２では、スワッピング部４６が、埋め込み画像を元の画像に復号した際の、埋め込み画像の第２列乃至第Ｎ列それぞれの入れ替え方を表すスワップ情報が、スワップ情報変換部４７に出力される。そして、スワップ情報変換部４７では、スワッピング部４６からのスワップ情報に基づいて、埋め込み画像に埋め込まれていた付加情報が復号されて出力される。
【０１２０】
その後、ステップＳ２３に進み、フレームメモリ４１に、まだ処理の対象とされていない埋め込み画像のフレームが記憶されているかどうかが判定され、記憶されていると判定された場合、ステップＳ１１に戻り、まだ処理の対象とされていない埋め込み画像のフレームを対象に、同様の処理が繰り返される。
【０１２１】
また、ステップＳ２３において、フレームメモリ４１に、まだ処理の対象とされていないフレームが記憶されていないと判定された場合、埋め込み復号処理を終了する。
【０１２２】
以上のように、付加情報が埋め込まれた画像である符号化データを、画像の相関性を利用して、元の画像と付加情報に復号するようにしたので、その復号のためのオーバヘッドがなくても、符号化データを、元の画像と付加情報に復号することができる。従って、その復号画像には、基本的に、付加情報を埋め込むことによる画質の劣化は生じない。
【０１２３】
なお、図１２の埋め込み復号処理においては、既に復号された最新の列（ｎ＝１の場合においては、埋め込み符号化時に入れ替えられていない第１列）と、まだ復号されていない列との相関を求め、その相関に基づいて、既に復号された最新の列の右隣の位置に入れ替えられるべき列を検出するようにしたが、その他、例えば、既に復号された複数の列と、まだ復号されていない列との相関を演算することにより、既に復号された最新の列の右隣に入れ替えられるべき列を検出するようにすることも可能である。
【０１２４】
ここで、図１３乃至図１５に、以上のような埋め込み符号化処理および復号化処理のシミュレーション結果を示す。
【０１２５】
図１３は、埋め込み符号化処理の対象とした画像（原画像）で、長手方向を縦にして見た場合に、横×縦が５１２画素×８３２画素で構成されている。
【０１２６】
図１４は、図１３の画像に対して、埋め込み符号化処理を施した処理結果を示している。図１４の画像（埋め込み画像）には、ｌｏｇ2（５１２！）ビットの付加情報が埋め込まれている。なお、同図からも明らかなように、埋め込み符号化は、上述したように、画像の暗号化という機能
（効果）を有する。
【０１２７】
図１５は、図１４の埋め込み符号化処理の結果を、埋め込み復号処理により復号した復号画像を示している。図１３と図１５とを比較することにより、画質の劣化なく、元の画像に復号されていることが分かる。なお、埋め込み復号処理により、埋め込み画像が元の画像に正確に復号されれば、その復号の際の、埋め込み画像の各列の入れ替え方に基づいて、付加情報も、正確に復号される。
【０１２８】
次に、上述の場合においては、埋め込み符号化器３には、例えば、図１６に示すような、Ｎ列でなる画像を符号化対象とし、第１列は固定して、第２乃至第Ｎ列を、付加情報にしたがって入れ替えることにより埋め込み符号化を行わせ、埋め込み復号器６には、その埋め込み符号化結果を、画像の相関性を利用して、元の画像と付加情報に復号させるようにしたが、埋め込み復号器６には、画像の相関性の他、以下のような連続性をも利用して、埋め込み符号化結果の復号を行わせることが可能である。
【０１２９】
即ち、図１２における場合には、図１６の画像の各列について、その列を構成する画素の画素値を要素とする列ベクトルｖnを用い、その列ベクトルどうしの距離の逆数を、相関として定義し、この相関のみを利用して、符号化データの復号を行うようにしたが、この場合、埋め込み復号器６では、まず、符号化データから、第１列（第１列は、上述したように固定）の列ベクトルと最も距離の近い列ベクトルが検出され、その列ベクトルに対応する列が、第２列とされる。さらに、埋め込み復号器６では、符号化データから、第２列の列ベクトルと最も距離の近い列ベクトルが検出され、その列ベクトルに対応する列が、第３列とされる。以下、同様にして、符号化データから、第Ｎ列までが検出され、これにより、元の画像が復号されるとともに、第２乃至第Ｎ列が、どのように入れ替えられていたかが、埋め込まれた付加情報として復号される。
【０１３０】
一方、図１６の画像の第ｎ列（ｎ＝１，２，・・・，Ｎ）の列ベクトルｖ1，ｖ2，・・・、ｖNが列ベクトル空間内に描く軌跡が、例えば、図１７に、細い点線で示すようであったとする。
【０１３１】
この場合、上述したように、第１列から、最も距離の近い列ベクトルを順次検出していくと、図１７に太い点線で示す軌跡が描かれる。即ち、ｖ1，ｖ2，ｖ13，ｖ3，ｖ14，ｖ15，ｖ4，ｖ5，ｖ6，・・・といった順番で、列ベクトルが検出されていく。従って、図１７の実施の形態においては、相関（ここでは、列ベクトルどうしの距離）だけでは、列ベクトルは、正しい順序で検出されず、その結果、画像および付加情報も正しく復号することができないことになる。
【０１３２】
そこで、第１列の列ベクトルｖ1と最も距離の近い列ベクトルを検出し、その列ベクトルに対応する列を、第２列とした後は、例えば、図１８に示すように、第２列の列ベクトルｖ2と、第１列の列ベクトルｖ1との差分ベクトル△ｖ12を求める。そして、列ベクトルｖ2に、その差分ベクトル△ｖ12を加算したベクトルによって表される点Ｐ12に最も近い列ベクトルを検出し、その列ベクトルに対応する列を第３列とする。
【０１３３】
さらに、第４列については、第３列の列ベクトルｖ3と、第２列の列ベクトルｖ2との差分ベクトルを求めて、その差分ベクトルを、列ベクトルｖ3に加算したベクトルによって表される点に最も近い列ベクトルを検出し、その列ベクトルに対応する列を第４列とする。以下、同様にして、第Ｎ列までを求めていくようにする。
【０１３４】
以上のように、第ｎ列と第ｎ＋１列との間の相関性だけでなく、第ｎ列の列ベクトルｖnと、第ｎ＋１列の列ベクトルｖn+1との間の連続性、即ち、ここでは、差分ベクトルｖn+1−ｖnの変化が連続しているということをも利用することで、図１７において、細い点線で示した軌跡が描かれるような正しい順番で、列ベクトルが検出され、その結果、画像および付加情報を正しく復号することができる。
【０１３５】
次に、図９の実施の形態においては、符号化対象の画像の画素（但し、第１列の画素を除く）を、列単位で、付加情報に基づいて入れ替えることで、付加情報の、画像への埋め込み、即ち、埋め込み符号化を行うようにしたが、埋め込み符号化は、例えば、符号化対象の画像の画素を、行単位で入れ替えたり、また、時間方向に並ぶ所定数のフレームの同一位置にある画素列の位置を入れ替えたりすることで行うことも可能である。
【０１３６】
さらに、埋め込み符号化は、例えば、符号化対象の画像の画素を、列単位で入れ替え、さらに、その入れ替え後の画像の画素を、行単位で入れ替えることにより行うことも可能である。
【０１３７】
即ち、例えば、図１９に示すような、横×縦がＮ×Ｍ画素でなる画像の列を、付加情報に基づいて入れ替え、例えば、図２０（Ａ）に示すような埋め込み画像とする。ここで、図２０（Ａ）においては、図１９の画像の第１列が第５列に、第２列が第Ｎ列に、第３列が第１列に、第４列が第２列に、第５列が第４列に、第６列が第３列に、・・・、第Ｎ列が第６列に、それぞれ入れ替えられている。
【０１３８】
そして、図２０（Ａ）の画像の行を、付加情報に基づいて入れ替え、例えば、図２０（Ｂ）に示すような埋め込み画像とする。ここで、図２０（Ｂ）においては、図２０（Ａ）の画像の第１行が第３行に、第２行が第５行に、第３行が第２行に、第４行が第Ｍ行に、第５行が第１行に、・・・、第Ｍ行が第４行に、それぞれ入れ替えられている。
【０１３９】
図２０（Ｂ）に示した埋め込み画像は、例えば、その第１列の左側に、入れ替えを行っていない列があるとすれば、その列を第１列として、図１２で説明した埋め込み復号処理を行うことにより、図１９に示した元の画像に復号することができる。即ち、列方向と行方向の両方向の入れ替えを行った埋め込み画像については、式（１）におけるΣにおいて加算される項の順番が変化するだけで、加算される項自体は変化しない。従って、式（１）によって求められる距離ｄ（ｎ，ｋ）は、埋め込み符号化された画像が同一であれば、列だけ入れ替えた場合と、列と行の両方を入れ替えた場合とで変化しないため、列と行の両方を入れ替えた埋め込み画像も、列だけ入れ替えた埋め込み画像と同様に、図１２の埋め込み復号処理によって、元の画像と付加情報に復号することができる。
【０１４０】
以上から、列と行の両方を入れ替える場合には、行と列のうち、いずれの入れ替えを先または後に行うかは、埋め込み復号処理に影響を与えない。従って、埋め込み符号化処理においては、行と列の入れ替えのうちのいずれを先または後に行っても良いし、埋め込み復号処理においても、行と列の入れ替えのうちのいずれを先または後に行っても良い。また、行と列の入れ替えを、交互に行うようなことも可能である。
【０１４１】
なお、埋め込み符号化処理において、列だけの入れ替えを行う場合には、埋め込み画像を元の画像に復号した際の、埋め込み画像の列の入れ替え方が、付加情報の復号結果となるが、行と列の両方の入れ替えを行う場合には、埋め込み画像の第ｍ行ｎ列の位置（ｍ，ｎ）にある画素が、復号画像のどの位置（ｍ’，ｎ’）に入れ替えられたかが、付加情報の復号結果となる。
【０１４２】
次に、図８の埋め込み符号化処理では、符号化対象の画像の第１列だけを固定にし、埋め込み復号器６では、この第１列を、いわば復号の基準として、埋め込み画像の他の列の入れ替えを行うようにしたが、復号の基準は、第１列でなくても、あらかじめ、埋め込み符号化器３と埋め込み復号器６に設定されていれば、最後の第Ｎ列であっても良いし、その他の任意の列でも良い。さらに、復号の基準は、１列の画素である必要はなく、極端には、１画素であっても良い。
【０１４３】
ところで、例えば、第１列を、いわば復号の基準とし、画像の相関を利用して、埋め込み画像の他の列の入れ替えを行う場合には、１の列の入れ替えを誤ると、その後の列（本実施の形態では、入れ替えを誤った列の右側にある列）の入れ替えも誤る可能性が高くなる。この場合、元の画像を復号することができないから、正しい付加情報を復号することもできなくなる。
【０１４４】
そこで、埋め込み符号化処理においては、複数の列を、復号の基準として残しておく（入れ替えの対象としない）（入れ替えを禁止する）ようにすることが可能である。
【０１４５】
即ち、例えば、画像の列方向に並ぶ画素の集合を１の入れ替え単位として入れ替えを行う場合においては、例えば、図２１に斜線を付して示すように、１列おきの列を、復号の基準とし、残りの列（図２１において、白抜きで示す部分）を、入れ替えの対象とすることが可能である。
【０１４６】
なお、図２１に示した場合において、画像の列数が２Ｎ列であれば、その画像に埋め込むことのできる付加情報のデータ量は、最大で、ｌｏｇ2（Ｎ！）ビットとなる
。
【０１４７】
次に、埋め込み符号化は、列や行単位より細かい単位で、１以上の画素の集合を入れ替えることで行うことが可能である。
【０１４８】
即ち、例えば、図２２に示すように、画像の各列を、５画素などの１以上の連続して並ぶ画素の集合に分け、その集合を１の入れ替え単位として入れ替えを行うことが可能である。さらに、この場合、図２２に示すように、入れ替え単位を市松模様状に２つに分類し、一方（例えば、図２２において白抜きの部分）を入れ替え対象とし、他方（例えば、図２２において斜線を付してある部分）を復号の基準とすることが可能である。なお、このようにした場合において、画像の行数が、入れ替え単位がＭ個だけ並ぶ画素数で構成され、列数が２Ｎ列であれば、その画像に埋め込むことのできる付加情報のデータ量は、最大で、ｌｏｇ2（（Ｍ×Ｎ）！）ビットとなる。
【０１４９】
また、例えば、図２３に示すように、画像の各列の画素を、６画素などの所定の画素数おきに抽出し、その抽出した画素の集合（図２３において、○を付してある画素の集合や、×を付してある画素の集合、△を付してある画素の集合など）を、１の入れ替え単位として入れ替えを行うことが可能である。さらに、この場合、図２３に示すように、画像を構成する各画素を市松模様状に２つに分類し、一方（例えば、図２３において白抜きの部分）を入れ替え対象とし、他方（例えば、図２３において斜線を付してある部分）を復号の基準とすることが可能である。なお、このようにした場合において、画像の各列から２Ｍ画素おき（図２３の実施の形態では、６画素おき）に抽出した画素の集合を１の入れ替え単位とし、画像の列数がＮ列であれば、その画像に埋め込むことのできる付加情報のデータ量は、最大で、ｌｏｇ2（（Ｍ×Ｎ）！）ビットとなる。即ち、例えば、図２３において○印で示す入れ替え単位は、同図において、４２０や、４２１、４２２で示すように、各列に存在し、従って、各列における○印で示す入れ替え単位のみに注目すれば、Ｎ！通りの入れ替えが可能である。よって、画像の各列から２Ｍ画素おきに抽出した画素の集合を１の入れ替え単位とする場合には、各列には、Ｍ個の入れ替え単位が存在するから、図２３に示した画像全体では、最大で、（Ｍ×Ｎ）！通りの入れ替えが可能であり、その結果、画像に埋め込むことのできる付加情報のデータ量は、ｌｏｇ2（（Ｍ×Ｎ）！）ビットとなる。
【０１５０】
ここで、図２１乃至図２３に示した場合においては、入れ替え対象の画素（図２１乃至図２３において白抜きの部分）の集合が、複数の復号の基準（図２１乃至図２３において斜線を付してある部分）に隣接している。このような場合においては、例えば、その複数の復号の基準それぞれと、入れ替え対象の画素の集合との距離の自乗和の逆数などを相関として利用することができる。
【０１５１】
以上のように、埋め込み符号化時および埋め込み復号時における入れ替え単位は、特に限定されるものではない。
【０１５２】
また、復号の基準とする画素の集合も特に限定されるものではない。
【０１５３】
なお、復号の正確さの観点からすれば、入れ替え対象の画素が、より多数の、復号の基準とされている画素に隣接しているのが好ましく、従って、図２３に示した場合が最も好ましい。さらに、復号の正確さの観点からすれば、復号の基準とする画素が多い方が好ましい。
【０１５４】
但し、復号の基準とする画素は入れ替えの対象とされないから、その数が多い場合には、画像に埋め込むことのできる付加情報のデータ量が少なくなる。さらに、復号の基準とする画素が多い場合や、入れ替え対象の画素が、より多数の、復号の基準とされている画素に隣接している場合には、暗号化の効果が弱まる。
【０１５５】
従って、復号の基準とする画素の数やその配置パターンは、復号の正確さと、埋め込む付加情報のデータ量および暗号化の効果とを考慮し、埋め込み符号化および埋め込み復号の用途に応じて設定するのが望ましい。
【０１５６】
また、ある列が、それに近い列に入れ替えられたり、あるいは、近い位置にある列どうしが、同様の位置関係のまま入れ替えられたりする場合には、やはり、暗号化の効果が弱まるので、そのような入れ替えが行われないように、埋め込み符号化処理において、各列は、元の位置より、所定距離以上離れた位置の列に入れ替えるといった制限や、近い位置にある列どうしは、所定距離以上離れた位置の列に入れ替えるといった制限を付すことが可能である。
【０１５７】
さらに、埋め込み符号化の対象とする画像が、例えば、ＲＧＢコンポーネント信号で構成されるカラー画像である場合には、ＲＧＢのすべてを同一位置に入れ替えても良いし、ＲＧＢの各コンポーネントを、独立に入れ替えても良い。ＲＧＢのすべてを同一位置に入れ替える場合には、ＲＧＢの各コンポーネントを、独立に入れ替える場合に比較して、埋め込むことのできる付加情報のデータ量は少なくなるが、埋め込み復号時における復号精度を向上させることができる。一方、ＲＧＢの各コンポーネントを、独立に入れ替える場合には、ＲＧＢのすべてを同一位置に入れ替える場合に比較して、埋め込み復号時における復号精度は劣化するが、埋め込むことのできる付加情報のデータ量を多くすることができる。
【０１５８】
また、付加情報として用いる情報は、特に限定されるものではなく、例えば、画像や、音声、テキスト、コンピュータプログラム、制御信号、その他のデータを付加情報として用いることが可能である。なお、画像データベース１の画像の一部を付加情報とし、残りを、フレームメモリ３１への供給対象とすれば、その残りの部分に、付加情報とされた画像の一部分が埋め込まれるから、画像の圧縮が実現されることになる。
【０１５９】
さらに、本実施の形態では、付加情報を、画像に埋め込むようにしたが、付加情報は、その他、例えば、音声に埋め込むことも可能である。即ち、例えば、時系列の音声データを、適当なフレームに区切り、各フレームの音声データを、付加情報にしたがって入れ替えることで、付加情報を、音声に埋め込むことが可能である。
【０１６０】
また、本実施の形態では、付加情報が埋め込まれた埋め込み画像を、画像の相関性、さらには必要に応じて連続性に基づいて、付加情報と元の画像に復号するようにしたが、埋め込み画像は、その他、上述の相似性に基づいて復号することも可能である。即ち、埋め込み画像の復号は、既に復号された列と、まだ復号されていない列との相似性の関係を表す値を求め、その値に基づいて行うことが可能である。
【０１６１】
さらに、本実施の形態では、ＣＰＵ３２または４２に、コンピュータプログラムを実行させることで、埋め込み符号化処理または埋め込み復号処理をそれぞれ行うようにしたが、これらの処理は、それ専用のハードウェアによって行うことも可能である。
【０１６２】
また、本実施の形態では、ＣＰＵ３２または４２に実行させるコンピュータプログラムを、プログラムメモリ３３または４３にそれぞれ記憶させておくようにしたが、このコンピュータプログラムは、例えば、半導体メモリ、磁気テープ、磁気ディスク、光ディスク、光磁気ディスク、相変化ディスクなどの記録媒体や、インターネット、地上波、衛星回線、公衆網、ＣＡＴＶ（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６４２は、ハードディスク６０２に格納されているプログラム、衛星６２２若しくはネットワーク６３１から転送され、通信部６４８で受信されてハードディスク６０２にインストールされたプログラム、ドライブ６４９に装着されたフロッピディスク６１１、CD-ROM６１２、MOディスク６１３、DVD６１４、若しくは磁気ディスク６１５から読み出されてハードディスク６０２にインストールされたプログラム、または半導体メモリ６１６から読み出されたプログラムを、RAM(Random Access Memory)６４４にロードして実行する。これにより、図８や図１２に示したフローチャートにしたがった処理が行われる。そして、CPU６４２は、その処理結果を、必要に応じて、例えば、入出力インタフェース６４５を介して、LCD(Liquid CryStal Display)等で構成される表示部６４６に出力し、あるいは通信部６４８から送信する。
【０１７４】
【発明の効果】
本発明の第１ないし第５の側面によれば、例えば、相関性等を利用することで、元の第１および第２のデータを復号すること、すなわち、劣化のない第１および第２のデータを得ることが可能となる。
【図面の簡単な説明】
【図１】本発明を適用した画像伝送システムの一実施の形態の構成例を示すブロック図である。
【図２】符号化対象の画像を示す図である。
【図３】相関性を利用した符号化／復号を説明するための図である。
【図４】連続性を利用した符号化／復号を説明するための図である。
【図５】相似性を利用した符号化／復号を説明するための図である。
【図６】図１の埋め込み符号化器３のハードウェアの構成例を示すブロック図である。
【図７】図６の埋め込み符号化器３の機能的構成例を示すブロック図である。
【図８】埋め込み符号化処理を説明するためのフローチャートである。
【図９】埋め込み符号化処理の結果を説明するための図である。
【図１０】図１の埋め込み復号器６のハードウェアの構成例を示すブロック図である。
【図１１】図１０の埋め込み復号器６の機能的構成例を示すブロック図である。
【図１２】埋め込み復号処理を説明するためのフローチャートである。
【図１３】埋め込み符号化のシミュレーションに用いた原画像を示すディスプレイ上に表示された中間階調の写真である。
【図１４】埋め込み符号化のシミュレーション結果を示すディスプレイ上に表示された中間階調の写真である。
【図１５】埋め込み復号のシミュレーション結果を示すディスプレイ上に表示された中間階調の写真である。
【図１６】列ベクトルを説明するための図である。
【図１７】列ベクトル空間を示す図である。
【図１８】列ベクトル空間を示す図である。
【図１９】行と列の両方向の入れ替えを説明するための図である。
【図２０】行と列の両方向の入れ替えを説明するための図である。
【図２１】復号の基準とする画素を示す図である。
【図２２】復号の基準とする画素を示す図である。
【図２３】復号の基準とする画素を示す図である。
【図２４】本発明を適用した記録媒体を説明するための図である。
【図２５】図２４のコンピュータ６０１の構成例を示すブロック図である。
【符号の説明】
１  画像データベース，  ２  付加情報データベース，  ３  埋め込み符号化器，  ４  記録媒体，  ５  伝送媒体，  ６  埋め込み復号器，  １０  符号化装置，  ２０  復号装置，  ３１  フレームメモリ，  ３２  ＣＰＵ，  ３３  プログラムメモリ，  ３６  スワップ情報生成部，  ３７  スワッピング部，  ４１  フレームメモリ，  ４２  ＣＰＵ，  ４３  プログラムメモリ，  ４６  スワッピング部，  ４７  スワップ情報変換部，  ６０１  コンピュータ，  ６０２  ハードディスク，  ６０３  半導体メモリ，  ６１１  フロッピーディスク，  ６１２  CD-ROM，  ６１３  MOディスク，  ６１４  DVD，  ６１５  磁気ディスク，  ６１６  半導体メモリ，  ６２１  ダウンロードサイト，  ６２２  衛星，  ６３１  ネットワーク，  ６４１  バス，  ６４２  CPU，  ６４３  ROM，  ６４４  RAM，  ６４５  入出力インタフェース，  ６４６  表示部，  ６４７  入力部，  ６４８  通信部，  ６４９  ドライブ
【図１】
0004182603.tif 000003
【図２】
0004182603.tif 000004
【図３】
0004182603.tif 000005
【図４】
0004182603.tif 000006
【図５】
0004182603.tif 000007
【図６】
0004182603.tif 000008
【図７】
0004182603.tif 000009
【図８】
0004182603.tif 000010
【図９】
0004182603.tif 000011
【図１０】
0004182603.tif 000012
【図１１】
0004182603.tif 000013
【図１２】
0004182603.tif 000014
【図１３】
0004182603.tif 000015
【図１４】
0004182603.tif 000016
【図１５】
0004182603.tif 000017
【図１６】
0004182603.tif 000018
【図１７】
0004182603.tif 000019
【図１８】
0004182603.tif 000020
【図１９】
0004182603.tif 000021
【図２０】
0004182603.tif 000022
【図２１】
0004182603.tif 000023
【図２２】
0004182603.tif 000024
【図２３】
0004182603.tif 000025
【図２４】
0004182603.tif 000026
【図２５】
0004182603.tif 000027