(57)【要約】【課題】第１のデータを符号化した符号化データのデータ量を増加させることなく、第２のデータを埋め込むとともに、第１及び第２のデータを、正確に復号する。【解決手段】符号化器１１は、第１のデータを量子化することで得られる量子化コードと量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、第２のデータが埋め込まれた埋め込み符号化データを生成する。復号器１２は、埋め込み符号化データの量子化コードと量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データを復号し、その仮の符号化データから、仮の復号データを復号する。そして、仮の符号化データが正しいか否かが判定され、その判定結果に基づき、第１及び第２のデータが復号される。本発明は、第１のデータを符号化した符号化データのデータ量を増加させることなく、第２のデータを埋め込む場合等に適用できる。【選択図】図１
2008283701.tif 000002
【特許請求の範囲】
【請求項１】
第１のデータを、量子化し、その結果得られる量子化コードと量子化誤差を、符号化データとして出力する符号化手段と、
前記符号化データとしての量子化コードの各値と量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、前記第２のデータが埋め込まれた埋め込み符号化データを生成する埋め込み手段と
を備えるデータ処理装置。
【請求項２】
データ処理装置が、
第１のデータを、量子化し、その結果得られる量子化コードと量子化誤差を、符号化データとして出力し、
前記符号化データとしての量子化コードの各値と量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、前記第２のデータが埋め込まれた埋め込み符号化データを生成する
ステップを含むデータ処理方法。
【請求項３】
第１のデータを、量子化し、その結果得られる量子化コードと量子化誤差を、符号化データとして出力する符号化手段と、
前記符号化データとしての量子化コードの各値と量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、前記第２のデータが埋め込まれた埋め込み符号化データを生成する埋め込み手段と
して、コンピュータを機能させるためのプログラムが記録された記録媒体。
【請求項４】
第１のデータを量子化することにより得られる量子化コードと量子化誤差を含む符号化データに第２のデータが埋め込まれた埋め込み符号化データにおける、前記量子化コードの各値と量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データを復号する仮符号化データ復号手段と、
所定のコードブックに応じて、前記仮の符号化データから、仮の復号データを復号する仮復号データ復号手段と、
前記量子化コードと量子化誤差と、前記仮復号データ復号手段により復号された仮の復号データを再度符号化することにより得られた量子化コードと量子化誤差とを比較することにより、前記仮の符号化データが正しいか否かを判定する判定手段と
を備え、
前記仮符号化データ復号手段は、前記判定手段による判定結果に応じて前記操作量を変更して再び仮の符号化データを復号し、
前記判定手段は、前記仮の符号化データが正しいと判定したとき、前記操作量に対応するデータを前記第２のデータとして出力し、前記仮復号データ復号手段からの仮の復号データを真の復号データとして出力する
データ処理装置。
【請求項５】
前記第１のデータは、画像データである
請求項４に記載のデータ処理装置。
【請求項６】
データ処理装置が、
第１のデータを量子化することにより得られる量子化コードと量子化誤差を含む符号化データに第２のデータが埋め込まれた埋め込み符号化データにおける、前記量子化コードの各値と量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データを復号する仮符号化データ復号ステップと、
所定のコードブックに応じて、前記仮の符号化データから、仮の復号データを復号する仮復号データ復号ステップと、
前記量子化コードと量子化誤差と、前記仮復号データ復号ステップにより復号された仮の復号データを再度符号化することにより得られた量子化コードと量子化誤差とを比較することにより、前記仮の符号化データが正しいか否かを判定する判定ステップと
を含み、
前記仮符号化データ復号ステップにおいて、前記判定ステップによる判定結果に応じて前記操作量を変更して再び仮の符号化データを復号し、
前記判定ステップにおいて、前記仮の符号化データが正しいと判定したとき、前記操作量に対応するデータを前記第２のデータとして出力し、前記仮復号データ復号ステップで復号した仮の復号データを真の復号データとして出力する
データ処理方法。
【請求項７】
第１のデータを量子化することにより得られる量子化コードと量子化誤差を含む符号化データに第２のデータが埋め込まれた埋め込み符号化データにおける、前記量子化コードの各値と量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データを復号する仮符号化データ復号手段と、
所定のコードブックに応じて、前記仮の符号化データから、仮の復号データを復号する仮復号データ復号手段と、
前記量子化コードと量子化誤差と、前記仮復号データ復号手段により復号された仮の復号データを再度符号化することにより得られた量子化コードと量子化誤差とを比較することにより、前記仮の符号化データが正しいか否かを判定する判定手段と
を備え、
前記仮符号化データ復号手段は、前記判定手段による判定結果に応じて前記操作量を変更して再び仮の符号化データを復号し、
前記判定手段は、前記仮の符号化データが正しいと判定したとき、前記操作量に対応するデータを前記第２のデータとして出力し、前記仮復号データ復号手段からの仮の復号データを真の復号データとして出力する
データ処理装置として、コンピュータを機能させるためのプログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置およびデータ処理方法、並びに記録媒体に関し、特に、例えば、復号画像の画質を劣化させることなく、かつデータ量を増加せずに、画像に情報を埋め込むことができるようにするデータ処理装置およびデータ処理方法、並びに記録媒体に関する。
【背景技術】
【０００２】
データに対して、そのデータ量を増加させることなく、情報を埋め込む手法としては、例えば、ディジタルオーディオデータの最下位ビットや、下位２ビットなどを、埋め込む情報に変換するものなどがある。この手法は、ディジタルオーディオデータの下位ビットが、その音質にあまり影響を与えないことを利用し、その下位ビットを、単に、埋め込む情報に置き換えるものであり、従って、再生時には、情報が埋め込まれたディジタルオーディオデータは、その下位ビットを元に戻さずに、そのまま出力される。即ち、情報が埋め込まれた下位ビットを、元に戻すのは困難であり、また、下位ビットは、音質に、あまり影響を与えないことから、ディジタルオーディオデータは、情報が埋め込まれた状態で出力される。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上述のような手法では、本来のデータと異なるデータが出力される。従って、データがオーディオデータである場合には、その音質に、また、データがビデオデータである場合には、その画質に、少なからず影響がある。
【０００４】
本発明は、このような状況に鑑みてなされたものであり、例えば、画像の画質を劣化させることなく、かつデータ量を増加せずに、画像に情報を埋め込むこと等ができるようにするものである。
【課題を解決するための手段】
【０００５】
本発明の第１の側面のデータ処理装置、又は、記録媒体は、第１のデータを、量子化し、その結果得られる量子化コードと量子化誤差を、符号化データとして出力する符号化手段と、前記符号化データとしての量子化コードの各値と量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、前記第２のデータが埋め込まれた埋め込み符号化データを生成する埋め込み手段とを備えるデータ処理装置、又は、データ処理装置として、コンピュータを機能させるためのプログラムが記録された記録媒体である。
【０００６】
本発明の第１のデータ処理方法は、データ処理装置が、第１のデータを、量子化し、その結果得られる量子化コードと量子化誤差を、符号化データとして出力し、前記符号化データとしての量子化コードの各値と量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、前記第２のデータが埋め込まれた埋め込み符号化データを生成するステップを含むデータ処理方法である。
【０００７】
本発明の第１の側面においては、第１のデータが、量子化され、その結果得られる量子化コードと量子化誤差が、符号化データとして出力される。さらに、前記符号化データとしての量子化コードの各値と量子化誤差との対応関係を、第２のデータに対応する操作量でシフトすることにより、前記第２のデータが埋め込まれた埋め込み符号化データが生成される。
【０００８】
本発明の第２の側面のデータ処理装置、又は、記録媒体は、第１のデータを量子化することにより得られる量子化コードと量子化誤差を含む符号化データに第２のデータが埋め込まれた埋め込み符号化データにおける、前記量子化コードの各値と量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データを復号する仮符号化データ復号手段と、所定のコードブックに応じて、前記仮の符号化データから、仮の復号データを復号する仮復号データ復号手段と、前記量子化コードと量子化誤差と、前記仮復号データ復号手段により復号された仮の復号データを再度符号化することにより得られた量子化コードと量子化誤差とを比較することにより、前記仮の符号化データが正しいか否かを判定する判定手段とを備え、前記仮符号化データ復号手段は、前記判定手段による判定結果に応じて前記操作量を変更して再び仮の符号化データを復号し、前記判定手段は、前記仮の符号化データが正しいと判定したとき、前記操作量に対応するデータを前記第２のデータとして出力し、前記仮復号データ復号手段からの仮の復号データを真の復号データとして出力するデータ処理装置、又は、データ処理装置として、コンピュータを機能させるためのプログラムが記録された記録媒体である。
【０００９】
本発明の第２の側面のデータ処理方法は、データ処理装置が、第１のデータを量子化することにより得られる量子化コードと量子化誤差を含む符号化データに第２のデータが埋め込まれた埋め込み符号化データにおける、前記量子化コードの各値と量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データを復号する仮符号化データ復号ステップと、所定のコードブックに応じて、前記仮の符号化データから、仮の復号データを復号する仮復号データ復号ステップと、前記量子化コードと量子化誤差と、前記仮復号データ復号ステップにより復号された仮の復号データを再度符号化することにより得られた量子化コードと量子化誤差とを比較することにより、前記仮の符号化データが正しいか否かを判定する判定ステップとを含み、前記仮符号化データ復号ステップにおいて、前記判定ステップによる判定結果に応じて前記操作量を変更して再び仮の符号化データを復号し、前記判定ステップにおいて、前記仮の符号化データが正しいと判定したとき、前記操作量に対応するデータを前記第２のデータとして出力し、前記仮復号データ復号ステップで復号した仮の復号データを真の復号データとして出力するデータ処理方法である。
【００１０】
本発明の第２の側面においては、第１のデータを量子化することにより得られる量子化コードと量子化誤差を含む符号化データに第２のデータが埋め込まれた埋め込み符号化データにおける、前記量子化コードの各値と量子化誤差との対応関係を、特定の操作量でシフトすることにより、仮の符号化データが復号される。また、所定のコードブックに応じて、前記仮の符号化データから、仮の復号データが復号され、前記量子化コードと量子化誤差と、仮の復号データを再度符号化することにより得られた量子化コードと量子化誤差とを比較することにより、前記仮の符号化データが正しいか否かが判定される。この場合において、前記仮の符号化データが正しいか否かの判定結果に応じて前記操作量が変更されて再び仮の符号化データが復号され、前記仮の符号化データが正しいと判定されたとき、前記操作量に対応するデータが前記第２のデータとして出力され、仮の復号データが真の復号データとして出力される。
【発明の効果】
【００１１】
本発明の第１及び第２の側面によれば、第１のデータを符号化した符号化データのデータ量を増加させることなく、第２のデータを埋め込むことができ、さらに、そのような第２のデータを埋め込んだデータから、第１および第２のデータを、正確に復号することが可能となる。
【発明を実施するための最良の形態】
【００１２】
図１は、本発明を適用した埋め込み圧縮／復号システム（システムとは、複数の装置が論理的に集合した物をいい、各構成の装置が同一筐体中にあるか否かは問わない）の一実施の形態の構成例を示している。
【００１３】
この埋め込み圧縮／復号システムは、符号化装置１および復号装置２で構成されており、符号化装置は、符号化対象としての、例えば、画像を符号化し、復号装置２は、その符号化結果を、元の画像に復号するようになっている。
【００１４】
即ち、符号化装置１は、埋め込み圧縮符号化器１１で構成され、そこには、符号化対象としての画像と、その画像に埋め込まれる情報（以下、適宜、付加情報という）とが供給されるようになっている。そして、埋め込み圧縮符号化器１１は、画像（ディジタル画像データ）を、所定の符号化ルールにしたがって圧縮符号化するとともに、その符号化ルールを、付加情報（ディジタルデータ）に基づいて破壊することにより、その付加情報を埋め込み、埋め込み符号化データを得て出力する。埋め込み圧縮符号化器１１が出力する埋め込み符号化データは、例えば、半導体メモリ、光磁気ディスク、磁気ディスク、光ディスク、磁気テープ、相変化ディスクなどでなる記録媒体３に記録され、あるいは、また、例えば、地上波、衛星回線、ＣＡＴＶ（Cable Television）網、インターネット、公衆回線などでなる伝送媒体４を介して伝送され、復号装置２に提供される。
【００１５】
復号装置２は、復号器１２で構成され、そこでは、記録媒体３または伝送媒体４を介して提供される埋め込み符号化データが受信される。そして、復号器１２は、その埋め込み符号化データを、所定の符号化ルールにしたがって符号化された符号化データに復元することにより、そこに埋め込まれている付加情報を復号し、さらに、符号化データを、元の画像に復号する。復号された画像は、例えば、図示せぬモニタ等に供給されて表示される。
【００１６】
なお、付加情報としては、例えば、元の画像に関連するテキストデータや、音声データ、その画像を縮小した縮小画像等は勿論、元の画像に無関係なデータを用いることも可能である。即ち、付加情報としては、あらゆるデータ（プログラムも含む）を用いることが可能である。
【００１７】
また、付加情報としては、埋め込み圧縮符号化器１１に供給する符号化対象としての画像の一部を用いることも可能である。即ち、埋め込み圧縮符号化器１１には、画像の一部を付加情報として供給するとともに、残りの画像を符号化対象として供給することが可能である。
【００１８】
次に、図２は、図１の埋め込み圧縮符号化器１１の構成例を示している。
【００１９】
フレームメモリ２１は、埋め込み圧縮符号化器１１に供給される画像データを、例えば、フレーム単位で記憶する。付加情報メモリ２２は、埋め込み圧縮符号化器１１に供給される付加情報を記憶する。
【００２０】
可変長符号化部２３は、フレームメモリ２１に記憶された画像データを、可変長符号化としての、例えば、ハフマン符号化し、その結果得られる符号化データを、符号化ルール破壊部２５に供給する。また、可変長符号化部２３は、ハフマン符号化の際、後述するようにして、ハフマンテーブルを作成するが、そのハフマンテーブルを、変換テーブル作成部２４に供給する。さらに、可変長符号化部２３は、変換テーブル作成部２４に出力したハフマンテーブルを得るのに必要な情報としてのハフマンテーブル関連情報を、ＭＵＸ（マルチプレクサ）２６に供給する。
【００２１】
変換テーブル作成部２４は、可変長符号化部２３から供給されるハフマンテーブルにおける符号を変換するための変換テーブルを、付加情報メモリ２２に記憶された付加情報に基づいて作成する。即ち、ハフマンテーブルは、ハフマン符号化する対象の値（ここでは、画像の画素値）と、各符号長の符号（符号化データ）との対応関係を記述したものであるが、変換テーブル作成部２４は、そのようなハフマンテーブルにおける符号を、付加情報に基づく符号に変換するための変換テーブルを作成する。変換テーブル作成部２４で作成された変換テーブルは、符号化ルール破壊部２５に供給される。
【００２２】
符号化ルール破壊部２５は、付加情報に基づき、可変長符号化部２３における符号化ルールを破壊することにより、その付加情報を埋め込む。即ち、符号化ルール破壊部２５は、変換テーブル作成部２４が付加情報に基づき作成した変換テーブルにしたがって、可変長符号化部２３が出力する符号化データ（符号）を変換（操作）し、可変長符号化部２３における符号化ルールを破壊した符号化ルールにより符号化された符号化データを得る。この破壊された符号化ルールにより符号化された符号化データは、元の符号化データに、付加情報が埋め込まれた埋め込み符号化データとして、符号化ルール破壊部２５からＭＵＸ２６に供給される。
【００２３】
ＭＵＸ２６は、符号化ルール破壊部２５からの埋め込み符号化データと、可変長符号化部２３からのハフマンテーブル関連情報とを多重化し、多重化データとして出力する。この多重化データが、図１で説明したように、記録媒体３または伝送媒体４を介して、復号装置２に提供される。
【００２４】
次に、図３は、図２の可変長符号化部２３の構成例を示している。
【００２５】
図２のフレームメモリ２１においては、そこに記憶された画像データの各フレームが、例えば、時間順に、順次、注目フレームとされ、その注目フレームの画像データが読み出される。この注目フレームの画像データは、頻度テーブル作成部３１と符号化部３４に供給される。
【００２６】
頻度テーブル作成部３１は、そこに供給される注目フレームを構成する画素について、各画素値と、その出現頻度とを対応付けた頻度テーブルを作成し、ハフマン木作成部３２に供給する。また、頻度テーブルは、ハフマンテーブル関連情報として、頻度テーブル作成部３１から、図３のＭＵＸ２６に供給される。
【００２７】
ここで、図３の実施の形態では、頻度テーブルを、ハフマンテーブル関連情報として用いるようにしたが、ハフマンテーブル関連情報は、後述するハフマンテーブル作成部３３が作成するハフマンテーブルを得ることができるような情報であれば、特に限定されるものではなく、従って、ハフマンテーブル関連情報としては、頻度テーブルの他、例えば、ハフマンテーブル作成部３３が作成するハフマンテーブルそのもの等を用いることが可能である。
【００２８】
ハフマン木作成部３２は、頻度テーブル作成部３１から供給される頻度テーブルに基づいて、いわゆるハフマン木を作成し、ハフマンテーブル作成部３３に供給する。ハフマンテーブル作成部３３は、ハフマン木作成部３２からのハフマン木に基づき、ハフマンテーブルを作成する。即ち、ハフマンテーブル作成部３３は、注目フレームにおける各画素値に対して、その画素値の出現頻度が高いほど、短い符号長の符号（出現頻度が低いほど長い符号長の符号）が割り当てられたハフマンテーブルを作成する。このハフマンテーブルは、符号化部３４に供給されるとともに、図２の変換テーブル作成部２４に供給される。
【００２９】
符号化部３４は、そこに供給される注目フレームの画素を、例えば、ラスタスキャン順に、順次、注目画素とし、その注目画素の画素値を、ハフマンテーブル作成部３３からのハフマンテーブルにおいて対応付けられている符号に変換し、符号化データとして出力する。
【００３０】
以上のように構成される可変長符号化部２３では、頻度テーブル作成部３１において、注目フレームについて頻度テーブルが作成され、ハフマン木作成部３２に供給される。ハフマン木作成部３２では、頻度テーブル作成部３１からの頻度テーブルに基づいて、ハフマン木が作成され、ハフマンテーブル作成部３３に供給される。ハフマンテーブル作成部３３では、ハフマン木作成部３２からのハフマン木に基づき、ハフマンテーブルが作成され、符号化部３４に供給される。符号化部３４では、注目フレームの各画素値が、ハフマンテーブルにおいて、その画素値に対応付けられている符号に変換され、符号化データとして出力される。
【００３１】
次に、図４を参照して、可変長符号化部２３における可変長符号化処理について、さらに説明する。
【００３２】
いま、頻度テーブル作成部３１において、例えば、図４（Ａ）に示すような頻度テーブルが作成されたとする。ここで、図４（Ａ）は、注目フレームにおいて、画素値「0」、「1」、「2」、「3」、「4」が、それぞれ、5,4,3,2,1回ずつ現れていることを表している。
【００３３】
図４（Ａ）の頻度テーブルについては、ハフマン木作成部３２において、例えば、図４（Ｂ）乃至図４（Ｅ）に示すように、各画素値の出現頻度に基づき、いわばボトムアップ式に、ハフマン木が作成される。
【００３４】
即ち、ハフマン木作成部３２は、頻度テーブルにおける画素値の中から、出現頻度が最も低いものを２つ選択し、１つの接点を構成する。さらに、ハフマン木作成部３２は、選択した２つの画素値のうちの、出現頻度が低い方に、ビット"0"または"1"のうちの、例えば、"0"を割り当て、他方に、"1"を割り当てる。そして、ハフマン木作成部３２は、選択した２つの画素値によって構成した接点に対して、その選択した２つの画素値の出現頻度の加算値を、その接点の出現頻度として割り当てる。
【００３５】
従って、図４（Ａ）に示した頻度テーブルにおいては、図４（Ｂ）に示すように、出現頻度が１の画素値「4」と、出現頻度が２の画素値「3」が選択され、接点#1が構成されるとともに、その接点#1の出現頻度として、３（＝１＋２）が割り当てられる。さらに、選択された２つの画素値「4」と「3」のうち、出現頻度が低い方の画素値「4」に、ビット"0"が割り当てられるとともに、出現頻度が高い方の画素値「3」に、ビット"1"が割り当てられる。
【００３６】
ここで、図４（Ｂ）乃至図４（Ｅ）では、出現頻度を表す数字を、カッコ()で囲って表してある。
【００３７】
なお、選択された２つの画素値の出現頻度が同一の場合には、いずれの画素値に、ビット"0"または"1"を割り当てても良い。但し、例えば、画素値が小さい方に、ビット"0"を割り当てるといったように、どちらの画素値に、ビット"0"または"1"を割り当てるかを、あらかじめ決めておく必要がある。
【００３８】
ハフマン木作成部３２では、以下、同様の処理が、接点が１つ収束するまで繰り返される。
【００３９】
従って、図４（Ｂ）の状態からは、図４（Ｃ）に示すように、出現頻度がいずれも３の接点#1と画素値「2」が選択され、その接点#1と画素値「2」が、１つの接点#2とされる。さらに、接点#2の出現頻度が６（＝３＋３）とされ、接点#1と画素値「2」には、それぞれビット"0"と"1"が割り当てられる。
【００４０】
図４（Ｃ）の状態からは、図４（Ｄ）に示すように、出現頻度が４の画素値「1」と、出現頻度が５の画素値「0」が選択され、その画素値「1」と「0」が、１つの接点#3とされる。さらに、接点#3の出現頻度が９（＝４＋５）とされ、画素値「1」と「0」には、それぞれビット"0"と"1"が割り当てられる。
【００４１】
図４（Ｄ）の状態からは、図４（Ｅ）に示すように、出現頻度が６の接点#2と、出現頻度が９の接点#3が選択され、その接点#2と#3が、１つの接点#4とされる。さらに、接点#4の出現頻度が１５（＝６＋９）とされ、接点#2と#3には、それぞれビット"0"と"1"が割り当てられる。
【００４２】
図４（Ｅ）の状態では、接点が、１つの接点#4に収束しているので、ハフマン木の完成となり、ハフマン木作成部３２は、このハフマン木を、ハフマンテーブル作成部３３に供給する。
【００４３】
ハフマンテーブル作成部３３は、ハフマン木を、収束した接点から、画素値の方向に辿っていくことで、各画素値に割り当てられた符号を認識する。
【００４４】
即ち、例えば、図４（Ｅ）に示したハフマン木を、接点#4から、画素値「0」の方向に辿っていき、各接点（または画素値）に割り当てられたビットを並べると、"0"→"0"→"0"となる。これにより、ハフマンテーブル作成部３３は、画素値「0」に対して、符号"000"が割り当てられたことを認識する。また、図４（Ｅ）に示したハフマン木を、接点#4から、画素値「1」の方向に辿っていき、各接点に割り当てられたビットを並べると、"0"→"0"→"1"となる。これにより、ハフマンテーブル作成部３３は、画素値「1」に対して、符号"001"が割り当てられたことを認識する。
【００４５】
以下、同様にして、ハフマンテーブル３３は、各画素値に割り当てられた符号を認識し、画素値と符号との対応関係を表すハフマンテーブルを作成する。従って、図４（Ｅ）に示したハフマン木からは、図４（Ｆ）に示すようなハフマンテーブルが作成されることになる。
【００４６】
なお、可変長符号化部２３には、その他、例えば、特許第2977570号に記載されている方法等によって、可変長符号化を行わせることが可能である。
【００４７】
図４（Ｅ）に示したハフマンテーブルにおいては、出現頻度が5,4,3,2,1回の画素値「0」、「1」、「2」、「3」、「4」それぞれに、符号"11","10","01","001","000"が割り当てられており、従って、基本的に、出現頻度が高いほど、符号長の短い符号が割り当てられている。
【００４８】
ところで、図４（Ｅ）のハフマンテーブルにおいては、画素値「0」、「1」、「2」、「3」、「4」の出現頻度は異なるが、出現頻度が比較的高い画素値「0」、「1」、「2」には、２ビットの符号が割り当てられており、出現頻度が比較的低い画素値「3」、「4」には、３ビットの符号が割り当てられている。
【００４９】
このように、ハフマンテーブルにおいては、出現頻度が異なっていても、同一の符号長の符号が割り当てられる場合があり、画素値の出現頻度と、その画素値に割り当てられる符号の符号長との関係は、一般に、図５に示すようになる。
【００５０】
いま、図５において、ｎビットの符号が割り当てられる画素値がｘ個あるとすると（但し、ｘは２n以下の整数）、そのｘ個の画素値に対するｎビットの符号の割り当てパターンは、ｘ！パターンだけ存在するが（！は階乗を表す）、ハフマンテーブルにおいては、そのｘ！パターンのうちの１つだけが、上述したハフマン木を作成する際のルールに基づいて採用されているにすぎない。
【００５１】
一方、ハフマンテーブルにおける、ｘ個の画素値に対するｎビットの符号の割り当てパターンを変更しても、符号量は増加しない。即ち、ハフマンテーブルにおいて、ｎビットのある符号が割り当てられるある画素値に、他のｎビットの符号を割り当てても、割り当てられる符号長は、ｎビットのままであるから、符号量は増加しない。
【００５２】
さらに、ハフマンテーブルにおける、ｘ個の画素値に対するｎビットの符号の割り当てパターンを変更しても、例えば、そのｘ個の画素値の出現頻度に基づいて、符号の割り当てパターンは、元に戻すことができる。
【００５３】
以上から、ハフマンテーブルにおいて同一の符号長の符号が割り当てられている画素値に対する符号の割り当てパターンを変更しても、即ち、可変長符号化の符号化ルールを破壊しても、符号量は増加せず、さらに、変更後の割り当てパターンは、元に戻すことができる。
【００５４】
このことは、画素値に対する符号の割り当てパターンの変更を、何らかの情報に基づいて行うことで、全体のデータ量を増加させずに、情報を埋め込むことができ、かつ、その埋め込んだ情報を、オーバヘッドなしで復号することができることを意味する。
【００５５】
即ち、図６は、８ビットで表される画素値（０乃至２５５）について作成されたハフマンテーブルの例を示している。なお、図６においては、画素値と、その画素値に割り当てられた符号（符号化データ）の他、各画素値の出現頻度も示してある。
【００５６】
図６において、例えば、画素値「12」乃至「18」の７つの画素値に注目すると、これらの７つの画素値には、いずれも、９ビットの符号が割り当てられており、この７つの画素値に対する９ビットの符号の割り当て方は、７！パターンだけ存在する。従って、この７つの画素値に対する９ビットの符号の割り当てパターンを変更することで、int[log27!]ビットの情報を埋め込むことができる。なお、int[]は、[]内の値以下の最大の整数値を意味する。
【００５７】
ここで、図７（Ａ）は、図６における画素値「12」乃至「18」それぞれの出現頻度をグラフによって表したものであり、図７（Ｂ）は、図６において、画素値「12」乃至「18」それぞれに割り当てられた９ビットの符号を表している。
【００５８】
いま、図７（Ｂ）に示した符号の割り当てを、int[log27!]ビット以下の付加情報に基づいて、例えば、図７（Ｃ）に示すように変更したとする。
【００５９】
即ち、図７（Ｂ）においては、画素値「12」乃至「18」に対して、符号"110111111","110111010","110100001","110011001"，"11011000","011101011","010001010"が、それぞれ割り当てられており、図７（Ｃ）では、画素値「12」に割り当てられていた符号"110111111"が画素値「15」に、画素値「15」に割り当てられていた符号"110011001"が画素値「12」に、画素値「16」に割り当てられていた符号"11011000"が顔値「17」に、画素値「17」に割り当てられていた符号"011101011"が画素値「18」に、画素値「18」に割り当てられていた符号"010001010"が画素値「16」に、それぞれ割り当て変更されている。なお、図７では、他の画素値に対する符号の割り当ては、変更されていない。
【００６０】
ここで、他の符号長の符号が割り当てられた画素値についても、符号の割り当てパターンを、付加情報に基づいて変更することができる。図８に、付加情報に基づいて、図６における符号の割り当てパターンを変更した符号化データとしての埋め込み符号化データの例を示す。なお、図８には、埋め込み符号化データとともに、その埋め込み符号化データを、図６に示したハフマンテーブルにしたがって可変長復号を行うことにより得られる復号画素値（埋め込み符号化データを、符号化データを得るときに用いたハフマンテーブルによって復号した画素値）も示してある。
【００６１】
図８において、例えば、画素値「12」乃至「18」の７つの画素値に注目し、埋め込み符号化データを、図６のハフマンテーブルにしたがって復号すると、図９（Ａ）に示すような復号画素値が得られる。即ち、埋め込み符号化データを、符号化時に用いたハフマンテーブルにしたがって復号した画素値を、埋め込み復号画素値というものとすると、符号"110011001"，"110111010","110100001","110111111","010001010","11011000","011101011"は、埋め込み復号画素値「15」、「13」、「14」、「12」、「18」、「16」、「17」に、それぞれ可変長復号される。
【００６２】
この埋め込み復号画素値「12」乃至「18」について、その出現頻度をカウントすると、図９（Ｂ）に示すようになる。即ち、図６のハフマンテーブルにおいて、画素値「12」乃至「18」に対して割り当てられた符号を、図７（Ｂ）および図７（Ｃ）に示したように変更したことから、画素値「12」、「15」、「16」乃至「18」については、その出現頻度が、図７（Ａ）に示したものに一致せず、具体的には、可変長符号化前の画素値「15」、「12」、「18」、「16」、「17」の出現頻度にそれぞれ一致したものとなる。
【００６３】
しかしながら、元（可変長符号化前）の画素値「12」乃至「18」それぞれの出現頻度と、可変長復号の結果得られる画素値「12」乃至「18」それぞれの出現頻度とは一致するはずであるから、上述のように、画素値の出現頻度が、可変長符号化前と、可変長復号後とで異なるのはおかしい。
【００６４】
そこで、図７（Ａ）に示した元の画素値の出現頻度と、図９（Ｂ）に示した埋め込み復号画素値の出現頻度とを比較し、一致する出現頻度を検出することで、付加情報に基づいて変更された符号（可変長符号）の割り当てパターンを元に戻すことができる。即ち、埋め込み符号化データを、ハフマンテーブルに基づいて符号化された符号化データに戻すことができる。そして、埋め込み符号化データを符号化データに戻すときの符号の割り当てパターンの変更の仕方から、埋め込まれた付加情報を復号することができ、また、元に戻した符号化データを可変長復号することで、元の画素値を復号することができる。
【００６５】
具体的には、図７（Ａ）に示した元の画素値の出現頻度と、図９（Ｂ）に示した埋め込み復号画素値の出現頻度とを比較することで、埋め込み復号画素値「15」、「13」、「14」、「12」、「17」、「18」、「16」の出現頻度が、元の画素値「12」乃至「18」の出現頻度とそれぞれ一致することを検出することができる。
【００６６】
これにより、埋め込み復号画素値「15」、「13」、「14」、「12」、「17」、「18」、「16」が得られた埋め込み符号化データ"110011001"，"110111010","110100001","110111111","010001010","11011000","011101011"は、付加情報が埋め込まれる前は、図６のハフマンテーブルにおいて、元の画素値「12」乃至「18」に割り当てられている符号"110111111","110111010","110100001","110011001"，"11011000","011101011","010001010"であったことが分かる。
【００６７】
従って、図９（Ｃ）に示すように、図７（Ａ）に示した元の画素値の出現頻度と、図９（Ｂ）に示した埋め込み復号画素値の出現頻度が一致するように、埋め込み符号化データを変換することにより、図６に示したハフマンテーブルにしたがって符号化された符号化データを復元するとともに、埋め込み符号化データと、復元された符号化データとの対応関係から、付加情報を復号することができる。さらに、復元された符号化データを可変長復号することで、図９（Ｄ）に示すように、元の画素値を復号することができる。
【００６８】
図２の埋め込み圧縮符号化器１１では、以上のように、データ量を増加させずに、オーバヘッドなしの復号が可能な埋め込み符号化処理が行われるようになっている。
【００６９】
次に、図１０のフローチャートを参照して、図２の埋め込み圧縮符号化器１１が行う埋め込み符号化処理について、さらに説明する。
【００７０】
可変長符号化部２３は、ステップＳ１において、フレームメモリ２１から供給される注目フレームの各画素の画素値を可変長符号化し、その結果得られる符号化データを、符号化ルール破壊部２５に出力する。また、可変長符号化部２３（図３）は、ステップＳ１における可変長符号化において、その頻度テーブル作成部３１で作成される頻度テーブルを、ハフマンテーブル関連情報として、ＭＵＸ２６に出力するとともに、ハフマンテーブル作成部３３で作成されるハフマンテーブルを、変換テーブル作成部２４に出力する。
【００７１】
そして、ステップＳ２において、変換テーブル作成部２４が、可変長符号化部２３からのハフマンテーブルにおける同一符号長の符号の割り当てパターンを、付加情報メモリ２２から供給される付加情報に基づいて変更し、その変更前の符号と変更後の符号とを対応付けた変換テーブルを作成する変換テーブル作成処理を行う。この変換テーブルは、変換テーブル作成部２４から符号化ルール破壊部２５に供給される。
【００７２】
符号化ルール破壊部２５は、ステップＳ３において、可変長符号化部２３からの符号化データを、変換テーブル作成部２４からの変換テーブルにしたがって埋め込み符号化データに変換する符号化データ変換処理を行い、その結果得られる埋め込み符号化データを、ＭＵＸ２６に供給する。
【００７３】
ＭＵＸ２６は、ステップＳ４において、符号化ルール破壊部２５からの注目フレームの埋め込み符号化データと、可変長符号化部２３からのハフマンテーブル関連情報とを多重化して出力し、ステップＳ５に進む。
【００７４】
ステップＳ５では、フレームメモリ２１に、注目フレームの次のフレームが記憶されているかどうかが判定される。ステップＳ５において、フレームメモリ２１に、次のフレームが記憶されていると判定された場合、その、次のフレームが、新たに注目フレームとされ、ステップＳ１に戻り、以下、同様の処理が繰り返される。
【００７５】
また、ステップＳ５において、フレームメモリ２１に、次のフレームが記憶されていないと判定された場合、埋め込み符号化処理を終了する。
【００７６】
次に、図１１のフローチャートを参照して、図２の変換テーブル作成部２４が図１０のステップＳ２で行う変換テーブル作成処理について、さらに説明する。
【００７７】
変換テーブル作成処理では、まず最初に、ステップＳ１１において、変換テーブル作成部２４は、可変長符号化部２３からのハフマンテーブルにおける符号の、ある符号長に注目し、その注目符号長の符号の数を認識する。即ち、変換テーブル作成部２４は、注目符号長と同一の符号長を有する符号の数を認識する。
【００７８】
さらに、変換テーブル作成部２４は、ステップＳ１２において、ステップＳ１１で認識した注目符号長の符号の数に基づいて、その注目符号長の符号に埋め込むことのできる付加情報のビット数を算出する。即ち、注目符号長の符号の数をｘとすると、変換テーブル作成部２４は、y=int[log2(x!)]を演算することにより、埋め込み可能な付加情報のビット数ｙを求める。
【００７９】
そして、ステップＳ１３に進み、変換テーブル作成部２４は、ステップＳ１２で求めたビット数ｙ分の付加情報を、付加情報メモリ２２から読み出し、ステップＳ１４に進む。ステップＳ１４では、変換テーブル作成部２４は、注目符号長の符号について、ステップＳ１３で付加情報メモリ２２から読み出した付加情報に基づいて、変換テーブルを作成する。即ち、変換テーブル作成部２４は、ハフマンテーブルにおいて、各画素値に割り当てられている注目符号長のｘ個の符号の割り当てパターンを、ｙビットの付加情報に基づいて変更し、その変更前の符号と、変更後の符号とを対応付けた変換テーブルを、注目符号長の符号についての変換テーブルとして作成する。
【００８０】
その後、変換テーブル作成部２４は、ステップＳ１５において、付加情報が、付加情報メモリ２２に、まだ記憶されているかどうかを判定し、記憶されていないと判定した場合、それまでに、注目フレームについて作成した変換テーブルを、符号化ルール破壊部２５（図２）に出力して、変換テーブル作成処理を終了する。
【００８１】
また、ステップＳ１５において、付加情報が、付加情報メモリ２２に、まだ記憶されていると判定された場合、ステップＳ１６に進み、変換テーブル作成部２４は、ハフマンテーブルにおけるすべての符号長の符号について変換テーブルを作成したかどうかを判定し、まだ作成していないと判定した場合、ステップＳ１１に戻る。この場合、ステップＳ１１では、変換テーブルを作成していない符号長のうちのいずれかが、新たに注目符号長とされ、以下、同様の処理が繰り返される。
【００８２】
一方、ステップＳ１６において、ハフマンテーブルにおけるすべての符号長の符号について変換テーブルを作成したと判定された場合、変換テーブル作成処理を終了する。
【００８３】
次に、図１２のフローチャートを参照して、図２の符号化ルール破壊部２５が図１０のステップＳ３で行う符号化データ変換処理について、さらに説明する。
【００８４】
可変長符号化部２３は、上述したように、注目フレームにおける各画素を、ラスタスキャン順に、注目画素として、その注目画素の画素値を可変長符号化し、その結果得られる符号化データを、順次出力する。いま、可変長符号化部２３が注目画素について出力した符号化データを、注目符号化データというものとすると、符号化ルール破壊部２５は、まず最初に、ステップＳ２１において、注目符号化データの符号長を認識し、ステップＳ２２に進む。
【００８５】
ステップＳ２２では、符号化ルール破壊部２５は、ステップＳ２１で認識した注目符号化データの符号長についての変換テーブルにしたがって、注目符号化データを変換し、埋め込み符号化データとして、ＭＵＸ２６（図２）に出力する。
【００８６】
そして、ステップＳ２３に進み、符号化ルール破壊部２５は、可変長符号化部２３からの次の符号化データがあるかどうかを判定し、あると判定した場合、その、次の符号化データを、新たに注目符号化データとして、ステップＳ２１に戻り、以下、同様の処理を繰り返す。
【００８７】
また、ステップＳ２３において、次の符号化データがないと判定された場合、符号化データ変換処理を終了する。
【００８８】
次に、図２の埋め込み圧縮符号化器１１では、可変長符号化部２３における可変長符号化により得られた符号化データを、変換テーブルにしたがって変換することにより、付加情報が埋め込まれた埋め込み符号化データを得るようにしたが、その他、例えば、可変長符号化部２３において、画素値と符号との対応関係を変更したハフマンテーブル（以下、適宜、変更ハフマンテーブルという）を作成し、その変更ハフマンテーブルを用いることで、可変長符号化と付加情報の埋め込みとを同時に行う、即ち、破壊した符号化ルールに基づく可変長符号化を行うようにすることが可能である。
【００８９】
即ち、図１３は、そのような埋め込み符号化処理を行う埋め込み圧縮符号化器１１の構成例を示している。なお、図中、図２または図３における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図１３の埋め込み圧縮符号化器１１は、符号化ルール破壊部２５が設けられておらず、その替わりに、可変長符号化部２３が符号化ルール破壊部４１を内蔵している他は、図２における場合と同様に構成されている。
【００９０】
符号化ルール破壊部４１には、ハフマンテーブル作成部３３が出力するハフマンテーブルと、変換テーブル作成部２４が出力する変換テーブルが供給されるようになっている。
【００９１】
符号化ルール破壊部４１は、ハフマンテーブルにおいて各画素値に対応付けられている符号（符号化データ）を、変換テーブルにおいて、その符号に対応付けられている埋め込み符号化データに変更し、これにより、ハフマンテーブル作成部３３からのハフマンテーブルを、画素値と埋め込み符号化データとが対応付けられたハフマンテーブルである変更ハフマンテーブルに変更する。この変更ハフマンテーブルは、符号化部３４に供給され、符号化部３４は、変更ハフマンテーブルにしたがって、画素値を変換する。
【００９２】
従って、図１３においては、符号化部３４からは、埋め込み符号化データが出力される。
【００９３】
次に、図１４は、埋め込み圧縮符号化器１１が、図２または図１３に示したように構成される場合の、図１の復号器１２の構成例を示している。
【００９４】
ＤＥＭＵＸ（デマルチプレクサ）５１は、図２または図１３の埋め込み圧縮符号化器１１から提供されるデータを、埋め込み符号化データとハフマンテーブル関連情報とに、フレーム単位で分離し、各フレームについての埋め込み符号化データを、可変長復号部５２および符号化ルール復元部５５に供給するとともに、ハフマンテーブル関連情報を、可変長復号部５２、逆変換テーブル作成部５４、および可変長復号部５６に供給する。
【００９５】
可変長復号部５２は、ＤＥＭＵＸ５１が出力する埋め込み符号化データおよびハフマン関連情報のフレームを、順次、注目フレームとし、注目フレームについてのハフマンテーブル関連情報としての頻度テーブルから、図３の可変長符号化部２３における場合と同様にして、ハフマンテーブルを作成して、逆変換テーブル作成部５４に供給する。
【００９６】
ここで、ハフマンテーブル関連情報としての頻度テーブルから作成されるハフマンテーブルは、可変長符号化部２３での可変長符号化に用いられるものと同一のものであり、以下、適宜、正ハフマンテーブルという。また、正ハフマンテーブルを得るのに用いられるハフマンテーブル関連情報としての頻度テーブルを、以下、適宜、正頻度テーブルという。
【００９７】
可変長復号部５２は、さらに、注目フレームについての埋め込み符号化データを、正ハフマンテーブルにしたがって可変長復号し、その結果得られる画素値の復号値、即ち、埋め込み復号画素値を、ハフマンテーブル生成部５３に供給する。
【００９８】
ハフマンテーブル生成部５３は、可変長復号部５２から供給される注目フレームについての埋め込み復号画素値を可変長符号化するハフマンテーブルを作成し、そのハフマンテーブルと、そのハフマンテーブルを作成する過程で作成される頻度テーブルを、逆変換テーブル作成部５４に供給する。
【００９９】
ここで、ハフマンテーブル生成部５３が作成するハフマンテーブルは、埋め込み復号画素値（埋め込み符号化データを、正ハフマンテーブルによって可変長復号したもの）を可変長符号化するものであり、基本的に、符号化データを正しく復号することができるものではない。そこで、この埋め込み復号画素値から得られるハフマンテーブルを、以下、適宜、正ハフマンテーブルに対して、誤ハフマンテーブルという。また、誤ハフマンテーブルを得るのに用いられる頻度テーブルを、以下、適宜、正頻度テーブルに対して、誤頻度テーブルという。
【０１００】
逆変換テーブル作成部５４は、可変長復号部５２からの正ハフマンテーブル、ＤＥＭＵＸ５１からのハフマンテーブル関連情報としての正頻度テーブル、ハフマンテーブル生成部５３からの誤ハフマンテーブルおよび誤頻度テーブルに基づいて、埋め込み符号化データを、元の符号化データに変換するための逆変換テーブルを作成する。即ち、逆変換テーブル作成部５４は、図２（または図１３）の変換テーブル作成部２４が作成する変換テーブルと同一の逆変換テーブルを作成する。この逆変換テーブルは、符号化ルール復元部５５に供給される。
【０１０１】
符号化ルール復元部５５は、逆変換テーブル作成部５４から供給される逆変換テーブルに基づき、ＤＥＭＵＸ５１からの埋め込み符号化データを、符号化ルールとしての正ハフマンテーブルにしたがって符号化された符号化データに復元する。さらに、符号化ルール復元部５５は、埋め込み符号化データと、復元した符号化データとの対応関係、即ち、逆変換テーブルに基づいて、埋め込み符号化データに埋め込まれていた付加情報を復号する。そして、符号化ルール復元部５５は、復元した符号化データを、可変長復号部５６に出力するとともに、復号した付加情報を、復号付加情報として出力する。
【０１０２】
可変長復号部５６は、ＤＥＭＵＸ５１から供給されるハフマン関連情報から、正ハフマンテーブルを作成し、その正ハフマンテーブルに基づいて、符号化ルール復元部５５から供給される符号化データを可変長復号して、その結果得られる復号画素値を出力する。
【０１０３】
次に、図１５は、図１４の可変長復号部５２の構成例を示している。
【０１０４】
ＤＥＭＵＸ５１が出力する埋め込み符号化データは、復号部６３に供給されるようになっており、同じく、ＤＥＭＵＸ５１が出力するハフマンテーブル関連情報としての頻度テーブルは、ハフマン木作成部６１に供給されるようになっている。
【０１０５】
ハフマン木作成部６１は、図３のハフマン木作成部３２と同様に、注目フレームについての頻度テーブルから、ハフマン木を作成し、ハフマンテーブル作成部６２に供給する。
【０１０６】
ハフマンテーブル作成部６２は、図３のハフマンテーブル作成部３３と同様に、ハフマン木作成部６１からのハフマン木に基づいて、ハフマンテーブルを作成し、復号部６３に供給する。
【０１０７】
復号部６３は、ハフマンテーブル作成部６２からのハフマンテーブルにしたがい、そこに供給される埋め込み符号化データを、画素値（埋め込み復号画素値）に復号して出力する。
【０１０８】
なお、図１４の可変長復号部５６も、図１５に示した可変長復号部５２と同様に構成される。
【０１０９】
次に、図１６は、図１４のハフマンテーブル生成部５３の構成例を示している。
【０１１０】
ハフマンテーブル生成部５３において、可変長復号部５２が出力する埋め込み復号画素値は、頻度テーブル７１に供給される。頻度テーブル７１、ハフマン木作成部７２、またはハフマンテーブルテーブル作成部７３は、図３の頻度テーブル作成部３１、ハフマン木作成部３２、またはハフマンテーブル作成部３３における場合とそれぞれ同様の処理を行う。
【０１１１】
これにより、頻度テーブル作成部７１では、注目フレームの埋め込み復号画素値についての頻度テーブルである誤頻度テーブル（元の画素値についての頻度テーブルではない）が作成され、逆変換テーブル作成部５４（図１４）に供給される。また、ハフマンテーブル作成部７３では、注目フレームの埋め込み復号画素値を、その出現頻度に応じた符号長の符号に変換するためのハフマンテーブルである誤ハフマンテーブル（元の画素値についてのハフマンテーブルではない）が作成され、逆変換テーブル作成部５４に供給される。
【０１１２】
次に、図１７は、図１４の逆変換テーブル作成部５４の構成例を示している。
【０１１３】
逆変換テーブル作成部５４には、上述したように、正ハフマンテーブル、正頻度テーブル、誤ハフマンテーブル、および誤頻度テーブルが供給されるようになっており、逆変換テーブル作成部５４では、これらのテーブルに基づき、図６乃至図９で説明したようにして、埋め込み符号化データと、正ハフマンテーブルによって符号化された符号化データとの対応関係が認識され、その対応関係が記述された逆変換テーブルが作成される。
【０１１４】
即ち、正ハフマンテーブルおよび誤ハフマンテーブルは、符号対応付け部８２に供給され、正頻度テーブルおよび誤頻度テーブルは、比較部８１に供給される。
【０１１５】
そして、比較部８１は、正頻度テーブルと誤頻度テーブルとを比較し、各符号長の符号ごとに、正頻度テーブルと誤頻度テーブルにおいて、同一の頻度となっている画素値を検出する。さらに、比較部８１は、正頻度テーブルと誤頻度テーブルにおいて、同一の頻度となっている画素値を対応付けた対応画素値テーブルを作成し、符号対応付け部８２に供給する。
【０１１６】
符号対応付け部８２は、比較部８１からの対応画素値テーブルにおいて対応付けられている画素値を、正ハフマンテーブルと誤ハフマンテーブルから検索し、その検索した画素値に対応付けられている符号どうしを対応付けることにより、逆変換テーブルを作成する。この逆変換テーブルは、符号化ルール復元部５５に供給される。
【０１１７】
次に、図１８のフローチャートを参照して、図１４の復号器１２による復号処理について説明する。
【０１１８】
ＤＥＭＵＸ（デマルチプレクサ）５１は、そこに供給されるデータを、埋め込み符号化データとハフマンテーブル関連情報とに分離し、各フレームについての埋め込み符号化データを、可変長復号部５２および符号化ルール復元部５５に供給するとともに、ハフマンテーブル関連情報を、可変長復号部５２、逆変換テーブル作成部５４、および可変長復号部５６に供給する。
【０１１９】
可変長復号部５２は、ステップＳ３１において、ＤＥＭＵＸ５１が出力する埋め込み符号化データおよびハフマン関連情報のフレームを、順次、注目フレームとし、注目フレームについての埋め込み符号化データを可変長復号する。
【０１２０】
即ち、可変長復号部５２は、注目フレームについてのハフマンテーブル関連情報としての頻度テーブル（正頻度テーブル）から、ハフマンテーブル（正ハフマンテーブル）を作成し、逆変換テーブル作成部５４に供給する。さらに、可変長復号部５２は、注目フレームについての埋め込み符号化データを、正ハフマンテーブルにしたがって可変長復号し、その結果得られる埋め込み復号画素値を、ハフマンテーブル生成部５３に供給する。
【０１２１】
そして、ステップＳ３２に進み、ハフマンテーブル生成部５３は、可変長復号部５２から供給される注目フレームについての埋め込み復号画素値から、頻度テーブル（誤頻度テーブル）を作成し、さらに、その誤頻度テーブルから、誤ハフマンテーブルを作成する。この誤頻度テーブルおよび誤ハフマンテーブルは、逆変換テーブル作成部５４に供給される。
【０１２２】
逆変換テーブル作成部５４は、ステップＳ３３において、正ハフマンテーブル、ハフマンテーブル関連情報としての正頻度テーブル、誤ハフマンテーブル、および誤頻度テーブルに基づいて、図１７で説明したように、逆変換テーブルを作成し、符号化ルール復元部５５に供給する。
【０１２３】
符号化ルール復元部５５は、ステップＳ３４において、逆変換テーブル作成部５４から供給される逆変換テーブルにおける各符号長ごとの埋め込み符号化データと符号化データとの対応関係を参照することにより、埋め込み符号化データに埋め込まれていた付加情報を復号し、その結果得られる復号付加情報を出力する。
【０１２４】
さらに、符号化ルール復元部５５は、ステップＳ３５に進み、逆変換テーブルを参照することにより、ＤＥＭＵＸ５１からの埋め込み符号化データを、符号化データに変換し、可変長復号部５６に供給する。
【０１２５】
可変長復号部５６は、ＤＥＭＵＸ５１から供給されるハフマン関連情報から、正ハフマンテーブルを作成し、その正ハフマンテーブルに基づいて、符号化ルール復元部５５から供給される符号化データを可変長復号して、その結果得られる復号画素値を出力する。
【０１２６】
その後、ステップＳ３７に進み、次のフレームについての埋め込み符号化データおよびハフマンテーブル関連情報が、ＤＥＭＵＸ５１から出力されているかどうかが判定され、出力されていると判定された場合、その、次のフレームが、新たに注目フレームとされ、ステップＳ３１に戻り、以下、同様の処理が繰り返される。
【０１２７】
また、ステップＳ３７において、次のフレームについての埋め込み符号化データおよびハフマンテーブル関連情報が、ＤＥＭＵＸ５１から出力されていないと判定された場合、復号処理を終了する。
【０１２８】
なお、上述したように、ハフマンテーブル関連情報としては、頻度テーブルではなく、ハフマンテーブルそのものを用いることが可能である。但し、この場合には、ハフマンテーブル関連情報としてのハフマンテーブルは、そのハフマンテーブルを参照することで、同一符号長の符号（符号化データ）が割り当てられる画素値の出現頻度の高低を認識することができるように（認識できるようなルールで）作成する必要がある。
【０１２９】
また、上述の場合には、フレーム単位で、ハフマンテーブルを作成するようにしたが、ハフマンテーブルは、その他、例えば、フィールド単位や、２フレーム以上の単位で作成するようにすることも可能である。
【０１３０】
さらに、ハフマンテーブルは、例えば、所定の画像データを用いて、あらかじめ作成しておき、埋め込み圧縮符号化器１１と復号器１２には、そのあらかじめ作成されたハフマンテーブルによって処理を行わせるようにすることも可能である。但し、この場合、処理する画像データからハフマンテーブルを作成したときに、そのハフマンテーブルが、所定の画像データから作成されたハフマンテーブルと一致していないと、復号器１２において、埋め込み符号化データを符号化データに復元することが困難となるため、付加情報は、所定の画像データから作成されたハフマンテーブルと同一のハフマンテーブルが得られる画像データだけを対象に埋め込むようにする必要がある。
【０１３１】
次に、図１９は、図１の埋め込み圧縮符号化器１１の他の構成例を示している。
【０１３２】
符号化部９１には、符号化対象としての画像データが供給されるようになっており、符号化部９１は、画像データを、所定の符号化ルールにしたがって符号化し、その結果得られる符号化データを、埋め込み部９２に出力する。
【０１３３】
埋め込み部９２には、付加情報が供給されるようになっており、埋め込み部９２は、符号化部９１から供給される符号化データを、付加情報に基づいて操作して、破壊された符号化ルールにしたがって符号化された符号化データとすることにより、その付加情報を、符号化データに埋め込む。
【０１３４】
次に、図２０のフローチャートを参照して、図１９の埋め込み圧縮符号化器１１の処理（埋め込み符号化処理）について説明する。
【０１３５】
符号化部９１には、符号化対象としての画像データが、例えば、フレーム単位で供給され、符号化部９１は、各フレームを、順次、注目フレームとし、ステップＳ４１において、注目フレームの画像データを、所定の符号化ルールにしたがって符号化する。そして、符号化部９１は、その結果得られる符号化データを、埋め込み部９２に出力する。
【０１３６】
埋め込み部９２は、ステップＳ４２において、符号化部９１における符号化ルールを、付加情報に基づいて破壊することにより、その付加情報を埋め込む。即ち、埋め込み部９２は、符号化部９１から供給される符号化データを、付加情報に基づいて操作し、これにより、その付加情報を符号化データに埋め込む。さらに、埋め込み部９２は、符号化データに付加情報を埋め込むことにより得られる埋め込み符号化データを出力し、ステップＳ４３に進む。
【０１３７】
ステップＳ４３では、符号化部９１が、次に符号化すべきフレームがあるかどうかを判定し、あると判定した場合、その、次のフレームが、新たに注目フレームとされ、ステップＳ４１に戻り、以下、同様の処理が繰り返される。
【０１３８】
また、ステップＳ４３において、次に符号化すべきフレームがないと判定された場合、埋め込み符号化処理を終了する。
【０１３９】
次に、図２１は、図１９の符号化部９１の構成例を示している。
【０１４０】
図２１の符号化部９１においては、例えば、画像データを構成する画素値が、ＲＧＢ(Red,Green,Blue)で表現されるものとして、各画素値が、ＲＧＢの色空間においてベクトル量子化され、セントロイドベクトルを表すコード（以下、適宜、ＶＱコードという）、そのコードに対応するセントロイドベクトルで表される画素値の、元の画素値に対する誤差（以下、適宜、ＶＱ残差という）、およびベクトル量子化に用いられたコードブックが、符号化データとして出力されるようになっている。
【０１４１】
即ち、符号化対象の画像データは、フレームメモリ１０１に供給され、フレームメモリ１０１は、そこに供給される画像データを、例えば、フレーム単位で、順次記憶する。
【０１４２】
コードブック作成部１０２は、フレームメモリ１０１に記憶された画像データのフレームを、順次、注目フレームとし、その注目フレームを構成する各画素の画素値から、その色空間におけるベクトル量子化に用いるコードブックを、例えば、いわゆるＬＢＧアルゴリズムによって作成する。このコードブックは、ベクトル量子化部１０３に供給されるとともに、符号化データ（の一部）として出力される。
【０１４３】
ベクトル量子化部１０３は、フレームメモリ１０１から注目フレームを読み出し、その注目フレームを構成する各画素を、例えば、ラスタスキャン順に、順次、注目画素とする。そして、ベクトル量子化部１０３は、注目画素の画素値を、コードブック作成部１０２からのコードブックを用いてベクトル量子化し、その結果得られるＶＱコードおよびＶＱ残差を、符号化データ（の一部）として出力する。
【０１４４】
以上のように構成される符号化部９１では、図２２に示すように、コードブック作成部１０２において、注目フレームを構成する各画素の画素値から、コードブックが作成され、ベクトル量子化部１０３に供給される。ベクトル量子化部１０３は、注目画素の画素値を、コードブック作成部１０２からのコードブックを用いてベクトル量子化する。
【０１４５】
即ち、ベクトル量子化部１０３は、注目画素の画素値によって表されるＲＧＢ空間上の点との距離が最も短い点を表すセントロイドベクトルを、コードブックから検出し、そのセントロイドベクトルを表すＶＱコードを出力する。さらに、ベクトル量子化部１０３は、そのＶＱコードが表すセントロイドベクトルと、注目画素の画素値によって表されるＲＧＢ空間上の点に対応するベクトルとの差分を求め、その結果得られる差分ベクトルを、ＶＱ残差として出力する。
【０１４６】
そして、符号化部９１では、以上のようにして得られるコードブック、並びに注目フレームの各画素についてのＶＱコードおよびＶＱ残差を、注目フレームについての符号化データとして出力する。
【０１４７】
次に、図２３は、符号化部９１が図２１に示したように構成される場合の、図１９の埋め込み部９２の構成例を示している。
【０１４８】
符号化部９１が出力する注目フレームのＶＱコード、ＶＱ残差、コードブックは、ＶＱコードメモリ１１１、ＶＱ残差メモリ１１２、コードブックメモリ１１３に、それぞれ供給されて記憶される。
【０１４９】
ＶＱコードメモリ１１１とコードブックメモリ１１３にそれぞれ記憶されたＶＱコードとコードブックは、そこから読み出され、圧縮部１１５に供給される。
【０１５０】
一方、ラインシフト部１１４は、注目フレームの各ライン（水平ライン）を、例えば、上から下方向に、順次、注目ラインとし、その注目ラインについて、ＶＱ残差メモリ１１２に記憶されたＶＱ残差を読み出す。さらに、ラインシフト部１１４は、注目ラインを構成する画素数を、ｘとすると、int[log2x]で表されるビット数の付加情報を受信し、例えば、図２４に示すように、その付加情報に対応する画素数だけ、注目ラインのＶＱ残差を右シフトすることにより、その付加情報を、注目ラインに埋め込む。即ち、このラインシフトにより、注目ライン上のある画素に注目すれば、基本的に、その画素についてのＶＱ残差は、ベクトル量子化により得られるものとは異なるものとなり、ベクトル量子化の符号化ルールが破壊される。そして、符号化ルールが破壊されることにより、付加情報が埋め込まれる。
【０１５１】
その後、ラインシフト部１１４は、付加情報を埋め込んだ注目ラインのＶＱ残差を、圧縮部１１５に供給する。
【０１５２】
ここで、注目ラインのＶＱ残差を右シフトする場合、注目ラインの右端の画素のＶＱ残差は、注目ラインの左端の画素にシフトされるものとする。同様に、注目ラインのＶＱ残差を左シフトする場合、左端の画素のＶＱ残差は、右端の画素にシフトされるものとする。
【０１５３】
圧縮部１１５は、そこに供給されるＶＱコード、ＶＱ残差、コードブックを、例えば、空間相関やエントロピーの偏り等を利用して圧縮し、その圧縮結果を、ＭＵＸ１１６に出力する。ＭＵＸ１１６は、圧縮部１１５からのＶＱコード、ＶＱ残差、コードブックそれぞれの圧縮結果を多重化して出力する。
【０１５４】
次に、図２５のフローチャートを参照して、符号化部９１が図２１に示したように構成され、埋め込み部９２が図２３に示したように構成される場合の、図１９の埋め込み圧縮符号化器１１の処理（埋め込み符号化処理）について説明する。
【０１５５】
符号化部９１（図２１）では、フレームメモリ１０１に記憶された所定のフレームが注目フレームとされ、ステップＳ５１において、その注目フレームの各画素が、上述したように、ベクトル量子化されることにより符号化される。注目フレームのベクトル量子化の結果得られる符号化データとしてのＶＱコード、ＶＱ残差、およびコードブックは、埋め込み部９２に供給される。
【０１５６】
埋め込み部９２（図２３）では、符号化部９１からの注目フレームについてのＶＱコード、ＶＱ残差、コードブックが、ＶＱコードメモリ１１１、ＶＱ残差メモリ１１２、コードブックメモリ１１３に、それぞれ供給されて記憶される。そして、ラインシフト部１１４は、ステップＳ５２において、ＶＱ残差メモリ１１２にＶＱ残差が記憶された注目フレームのすべてのラインを処理したかどうかを判定する。
【０１５７】
ステップＳ５２において、ＶＱ残差メモリ１１２にＶＱ残差が記憶された注目フレームのすべてのラインを、まだ処理していないと判定された場合、ラインシフト部１１４は、注目フレームにおいて、まだ処理してないラインのうちの最も上部に位置するものを、新たに注目ラインとし、ステップＳ５３に進む。
【０１５８】
ステップＳ５３では、ラインシフト部１１４は、注目ラインの、ＶＱ残差を画素値とする各画素を、付加情報に対応する画素数だけ右シフトし、これにより、注目ラインに付加情報を埋め込んで、圧縮部１１５に供給する。その後は、ステップＳ５２に戻り、以下、同様の処理が繰り返される。
【０１５９】
そして、ステップＳ５２において、ＶＱ残差メモリ１１２にＶＱ残差が記憶された注目フレームのすべてのラインを処理したと判定された場合、ステップＳ５４に進み、圧縮部１１５は、ＶＱコードメモリ１１１に記憶された注目フレームについてのＶＱコードを読み出すとともに、コードブックメモリ１１３に記憶された注目フレームについてのコードブックを読み出す。そして、圧縮部１１５は、そのＶＱコードおよびコードブック、さらには、ラインシフト部１１４からの付加情報が埋め込まれたＶＱ残差を圧縮し、ＭＵＸ１１６に供給する。
【０１６０】
ＭＵＸ１１６は、ステップＳ５５において、圧縮部１１５からのＶＱコード、ＶＱ残差、およびコードブックを多重化して出力し、ステップＳ５６に進む。
【０１６１】
ステップＳ５６では、符号化部９１において、次に符号化すべきフレームがあるかどうかがが判定され、あると判定された場合、その、次に符号化すべきフレームが、新たに注目フレームとされ、ステップＳ５１に戻り、以下、同様の処理が繰り返される。
【０１６２】
また、ステップＳ５６において、次に符号化すべきフレームがないと判定された場合、埋め込み符号化処理を終了する。
【０１６３】
次に、図２６は、埋め込み圧縮符号化器１１が図１９に示したように構成される場合の、図１の復号器１２の構成例を示している。
【０１６４】
図１９の埋め込み部９２が出力する埋め込み符号化データは、符号化ルール復元部１２１に供給される。
【０１６５】
符号化ルール復元部１２１は、埋め込み符号化データを、図１９の符号化部９１における符号化ルールにしたがって符号化された符号化データに復元し、これにより、埋め込み符号化データに埋め込まれていた付加情報を復号する。
【０１６６】
即ち、符号化ルール復元部１２１は、埋め込み符号化データに対して、パラメータコントローラ１２４から供給されるパラメータに基づく操作を施すことにより、符号化データの候補（以下、適宜、仮符号化データという）を求める。さらに、符号化ルール復元部１２１は、埋め込み符号化データを仮符号化データに復元する操作に基づいて、埋め込み符号化データに埋め込まれていた付加情報の候補（以下、仮復号付加情報という）を復号する。そして、仮符号化データは、復号部１２２および判定部１２３に、仮復号付加情報は、判定部１２３に供給される。
【０１６７】
復号部１２２は、符号化ルール復元部１２１からの仮符号化データに対して、図１９の符号化部９１における符号化ルールに基づく復号処理を施すことにより、元の画素値の候補（以下、適宜、仮復号画素値という）を復号する。この仮復号画素値は、判定部１２３に供給される。
【０１６８】
判定部１２３は、パラメータコントローラ１２４を制御することにより、１つ以上の値のパラメータを、符号化ルール復元部１２１に供給させ、その１つ以上の値のパラメータそれぞれに対応して得られる１つ以上の仮復号画素値の中から、正しい（元の画素値に一致する）仮復号画素値を判定する。さらに、判定部１２３は、１つ以上の仮復号画素値それぞれに付随して、符号化ルール復元部１２１から供給される１つ以上の仮復号付加情報の中から、正しい復号画素値が得られたときのものを、正しい復号付加情報として選択し、正しい仮復号画素値と仮復号付加情報を、画素値と付加情報の最終的な復号結果（復号画素値と復号付加情報）として、それぞれ出力する。
【０１６９】
パラメータコントローラ１２４は、判定部１２３の制御にしたがい、埋め込み符号化データを操作するための所定のパラメータを、符号化ルール復元部１２１に供給する。
【０１７０】
次に、図２７のフローチャートを参照して、図２６の復号器１２の処理（復号処理）について説明する。
【０１７１】
判定部１２３は、まず最初に、ステップＳ６１において、パラメータコントローラ１２４を制御することにより、符号化ルール復元部１２１に与えるパラメータを設定する。これにより、パラメータコントローラ１２６は、判定部１２３の制御にしたがったパラメータを、符号化ルール復元部１２１に供給する。
【０１７２】
符号化ルール復元部１２１は、ステップＳ６２において、埋め込み符号化データに対して、パラメータコントローラ１２４から供給されるパラメータに基づく操作を施すことにより、仮符号化データに変換し、復号部１２２および判定部１２３に供給する。さらに、符号化ルール復元部１２１は、埋め込み符号化データを仮符号化データに復元する操作、つまりは、パラメータコントローラ１２４からのパラメータに基づいて、埋め込み符号化データに埋め込まれていた付加情報を復号し、仮復号付加情報として、判定部１２３に供給する。
【０１７３】
復号部１２２は、ステップＳ６３において、符号化ルール復元部１２１からの仮符号化データを、図１９の符号化部９１における符号化ルールに基づいて復号し、その復号の結果得られる画素値を、仮復号画素値として、判定部１２３に供給する。
【０１７４】
判定部１２３は、ステップＳ６４において、復号部１２２からの仮復号画素値が、正しい復号結果であるかどうか（元の画素値に一致しているかどうか）を判定し、一致していないと判定した場合、ステップＳ６１に戻る。この場合、判定部１２３は、ステップＳ６１において、パラメータコントローラ１２４に出力させるパラメータとして、新たな値を設定し、以下、同様の処理を繰り返す。
【０１７５】
一方、ステップＳ６４において、復号部１２２からの仮復号画素値が、正しい復号結果であると判定された場合、ステップＳ６５に進み、判定部１２３は、その仮復号画素値を、元の画素値の復号結果である復号画素値として出力する。さらに、判定部１２３は、その復号画素値が得られたときの仮復号付加情報を、埋め込まれていた付加情報の復号結果である復号付加情報として出力し、ステップＳ６６に進む。
【０１７６】
ステップＳ６６では、まだ復号すべき埋め込み符号化データがあるかどうかが判定され、あると判定された場合、ステップＳ６１に戻り、その復号すべき埋め込み符号化データを対象に、以下、同様の処理が繰り返される。
【０１７７】
また、ステップＳ６６において、復号すべき埋め込み符号化データがないと判定された場合、復号処理を終了する。
【０１７８】
次に、図２８は、図１９の埋め込み部９２が図２３に示したように構成される場合の、図２６の符号化ルール復元部１２１の構成例を示している。
【０１７９】
図２３のＭＵＸ１１６が出力するデータは、ＤＥＭＵＸ１３１に供給され、ＤＥＭＵＸ１３１は、そこに供給されるデータを、圧縮されたＶＱコード、ＶＱ残差、およびコードブックに分離し、伸張部１３２に供給する。伸張部１３２は、ＤＥＭＵＸ１３１からの、圧縮されたＶＱコード、ＶＱ残差、コードブックを伸張し、その伸張後のＶＱコード、ＶＱ残差、コードブックを、ＶＱコードメモリ１３３、ＶＱ残差メモリ１３４、コードブックメモリ１３５にそれぞれ供給する。
【０１８０】
ＶＱコードメモリ１３３、ＶＱ残差メモリ１３４、コードブックメモリ１３５は、伸張部１３２からのＶＱコード、ＶＱ残差、コードブックを、それぞれ、フレーム単位で記憶する。
【０１８１】
ラインシフト部１３６は、ＶＱ残差メモリ１３４に記憶されたフレームの各ラインを、例えば、上から下方向に、順次、注目ラインとし、その注目ラインについて、ＶＱ残差メモリ１３４に記憶されたＶＱ残差を読み出す。さらに、ラインシフト部１３６は、注目ラインを構成する画素数を、ｘとすると、０乃至ｘの範囲の整数値を、パラメータコントローラ１２４（図２６）から、パラメータとして受信し、そのパラメータに対応する画素数だけ、注目ラインのＶＱ残差を左シフトする。そして、ラインシフト部１３６は、そのシフト後の各ラインのＶＱ残差を、ＶＱコードメモリ１３３に記憶されたＶＱコード、およびコードブックメモリ１３５に記憶されたコードブックとともに、仮符号化データとして出力する。
【０１８２】
さらに、ラインシフト部１３６は、パラメータコントローラ１２４からのパラメータの値を、仮復号付加情報として出力する。
【０１８３】
次に、図２９は、図１９の符号化部９１が図２１に示したように構成される場合の、図２６の復号部１２２の構成例を示している。
【０１８４】
復号部１２２は、符号化ルール復元部１２１から供給される符号化データとしての１フレームのＶＱコード、ＶＱ残差、およびコードブックに基づき、ベクトル逆量子化を行うことにより、画素値を復号する。
【０１８５】
即ち、ベクトル逆量子化部１４１には、ＶＱコードおよびコードブックが供給されるようになっており、ベクトル逆量子化部１４１は、ＶＱコードに対応するセントロイドベクトルを、コードブックから検出し、そのセントロイドベクトルを、加算部１４２に供給する。加算部１４２には、ベクトル逆量子化部１４１からセントロイドベクトルが供給される他、ＶＱ残差としての差分ベクトルも供給されるようになっており、加算部１４２は、セントロイドベクトルと差分ベクトルとを加算する。そして、加算部１４２は、その加算の結果得られるベクトルの各成分を、Ｒ，Ｇ，Ｂ値とする画素値を、仮復号画素値として出力する。
【０１８６】
次に、図３０は、符号化ルール復元部１２１と復号部１２２が、図２８と図２９に示したようにそれぞれ構成される場合の、図２６の判定部１２３の構成例を示している。
【０１８７】
メモリ１５１には、符号化ルール復元部１２１からの仮復号付加情報と、復号部１２２からの仮復号画素値が供給されるようになっており、メモリ１５１は、その仮復号付加情報と仮復号画素値を一時記憶するとともに、正誤判定部１５４の制御にしたがい、記憶した仮復号付加情報と仮復号画素値を読み出し、それぞれを、復号付加情報と復号画素値として出力する。
【０１８８】
符号化部１５２には、符号化ルール復元部１２１が出力する仮符号化データのうちのコードブックと、復号部１２２が出力する仮復号画素値が供給されるようになっており、符号化部１５２は、仮復号画素値を、図１９の符号化部９１と同様に符号化する。即ち、符号化部１５２は、仮復号画素値を、符号化ルール復元部１２１からのコードブックを用いてベクトル量子化し、その結果得られるＶＱコードとＶＱ残差を、比較部１５３に供給する。ここで、以下、適宜、仮復号画素値をベクトル量子化して得られるＶＱコードとＶＱ残差を、それぞれ、仮ＶＱコードと仮ＶＱ残差という。
【０１８９】
比較部１５３には、符号化部１５２が出力する仮ＶＱコードおよび仮ＶＱ残差の他、復号部１２２が出力する仮符号化データのうちのＶＱコードおよびＶＱ残差が供給されるようになっている。比較部１５３は、仮ＶＱコードと、仮符号化データのＶＱコードとを比較するとともに、仮ＶＱ残差と、仮符号化データのＶＱ残差とを比較し、それぞれの比較結果を、正誤判定部１５４に供給する。
【０１９０】
正誤判定部１５４は、パラメータコントローラ１２４を制御することにより、パラメータコントローラ１２４に、ラインシフトを行うビット数を、パラメータとして、符号化ルール復元部１２１に供給させる。また、正誤判定部１５４は、比較部１５３からの仮ＶＱコードと仮符号化データのＶＱコードとの比較結果、および仮ＶＱ残差と仮符号化データのＶＱ残差との比較結果に基づいて、仮復号画素値が復号結果として正しいかどうかを判定し、その判定結果に基づき、メモリ１５１からの仮復号画素値および仮復号付加情報の読み出しを制御する。
【０１９１】
次に、図３１を参照して、図３０の正誤判定部１５４が、仮復号画素値が復号結果として正しいかどうかを判定する判定原理について説明する。
【０１９２】
符号化部９１（図１９）では、ＲＧＢ空間においてベクトル量子化が行われるから、そのベクトル量子化に用いられるセントロイドベクトルは、Ｒ成分、Ｂ成分、およびＧ成分の３つの成分から構成される。いま、このＲ成分、Ｂ成分、およびＧ成分からなるセントロイドベクトルを、（Ｒ，Ｇ，Ｂ）と表すとともに、説明を簡単にするために、コードブックにおけるセントロイドベクトルのＲ成分、Ｂ成分、およびＧ成分が、いずれも１０の倍数で表されるものとすると、Ｒ，Ｂ，Ｇ成分が、例えば、それぞれ１０２，１０３，９９の画素値（以下、適宜、画素値（１０２，１０３，９９）と表す）は、セントロイドベクトル（１００，１００，１００）との距離を最も短くするから、セントロイドベクトル（１００，１００，１００）に対応するＶＱコードにベクトル量子化される。ここで、セントロイドベクトル（１００，１００，１００）に対応するＶＱコードを、例えば、０とする。
【０１９３】
この場合、ＶＱ残差は、画素値（１０２，１０３，９９）から、セントロイドベクトル（１００，１００，１００）を減算して、（２，３，−１）となる。従って、画素値（１０２，１０３，９９）は、ＶＱコード０と、ＶＱ残差（２，３，−１）に符号化される。
【０１９４】
そして、このようにして符号化部９１で得られる符号化データとしてのＶＱコード０と、ＶＱ残差（２，３，−１）をベクトル逆量子化すると、図３１（Ａ）に示すように、ＶＱコード０に対応するセントロイドベクトル（１００，１００，１００）と、ＶＱ残差（２，３，−１）とを加算することにより、画素値（１０２，１０３，９９）が得られ、従って、元の画素値に正しく復号される。
【０１９５】
さらに、この復号された画素値（１０２，１０３，９９）を、再度ベクトル量子化すると、図３１（Ａ）に示すように、やはり、ＶＱコード０と、ＶＱ残差（２，３，−１）が得られる。
【０１９６】
以上から、符号化データとしてのＶＱコードとＶＱ残差を復号し、正しい復号結果を得て、その復号結果を再度符号化（ここでは、ベクトル量子化）すると、その符号化の結果得られるＶＱコードとＶＱ残差は、符号化データとしてのＶＱコードとＶＱ残差に、それぞれ一致する。
【０１９７】
一方、符号化部９１で得られる符号化データとしてのＶＱコード０と、ＶＱ残差（２，３，−１）のうちの、ＶＱ残差（２，３，−１）について、上述したようにラインシフトが行われることにより付加情報が埋め込まれると、ＶＱコード０と、ＶＱ残差（２，３，−１）に対応する画素のＶＱ残差には、他の画素について得られたＶＱ残差が割り当てられる。いま、この、他の画素のＶＱ残差が、例えば、図３１（Ｂ）に示すように、（１０，１１，１２）であったとすると、ＶＱコード０と、ＶＱ残差（１０，１１，１２）は、図３１（Ｂ）に示すように、ＶＱコード０に対応するセントロイドベクトル（１００，１００，１００）と、ＶＱ残差（１０，１１，１２）とを加算することにより、画素値（１１０，１１１，１１２）に復号され、従って、元の画素値（１０２，１０３，９９）には、正しく復号されない。
【０１９８】
従って、この正しく復号されない画素値（１１０，１１１，１１２）を、再度ベクトル量子化しても、図３１（Ｂ）に示すように、符号化データとしてのＶＱコード０またはＶＱ残差（２，３，−１）と一致するＶＱコードまたはＶＱ残差は得られない。
【０１９９】
即ち、いまの場合、コードブックにおけるセントロイドベクトルのＲ成分、Ｂ成分、およびＧ成分は、いずれも１０の倍数で表されるものとしてあるから、画素値（１１０，１１１，１１２）との距離を最も短くするセントロイドベクトルは、（１１０，１１０，１１０）となる。従って、セントロイドベクトル（１１０，１１０，１１０）を表すＶＱコードを、例えば、１とすると、画素値（１１０，１１１，１１２）は、ＶＱコード１と、ＶＱ残差（０，１，２）（＝（１１０，１１１，１１２）−（１１０，１１０，１１０））にベクトル量子化され、この場合、ＶＱコードも、また、ＶＱ残差も、元の符号化データであるＶＱコード０またはＶＱ残差（１０，１１，１２）に一致しない。
【０２００】
以上から、図２８のラインシフト部１３６で、パラメータにしたがってシフトされる画素数が、付加情報に一致していない場合、即ち、仮符号化データが、付加情報が埋め込まれる前の符号化データに一致していない場合には、そのような仮符号化データから得られる仮復号画素値を再度符号化して得られるＶＱコードとＶＱ残差が、仮符号化データとしてのＶＱコードとＶＱ残差に、それぞれ一致せず、これにより、仮符号化データを復号して得られる仮復号画素値が、正しい復号結果でないことを判定することができる。
【０２０１】
一方、図２８のラインシフト部１３６で、パラメータにしたがってシフトされる画素数が、付加情報に一致している場合、即ち、仮符号化データが、付加情報が埋め込まれる前の符号化データに一致している場合には、そのような仮符号化データから得られる仮復号画素値を再度符号化して得られるＶＱコードとＶＱ残差が、仮符号化データとしてのＶＱコードとＶＱ残差に、それぞれ一致し、これにより、仮符号化データを復号して得られる仮復号画素値が、正しい復号結果であることを判定することができる。
【０２０２】
次に、図３２のフローチャートを参照して、符号化ルール復元部１２１、復号部１２２、判定部１２３が、図２８乃至図３０にそれぞれ示したように構成される場合の、図２６の復号器１２の復号処理について説明する。
【０２０３】
復号処理では、符号化ルール復元部１２１のＤＥＭＵＸ１３１が、そこに供給されるデータを、圧縮されたＶＱコード、ＶＱ残差、およびコードブックに分離し、伸張部１３２に供給する。伸張部１３２は、ステップＳ７１において、ＤＥＭＵＸ１３１からの、圧縮されたＶＱコード、ＶＱ残差、コードブックを伸張し、その伸張後のＶＱコード、ＶＱ残差、コードブックを、ＶＱコードメモリ１３３、ＶＱ残差メモリ１３４、コードブックメモリ１３５にそれぞれ供給して記憶させる。
【０２０４】
その後、ステップＳ７２において、判定部１２３（図３０）の正誤判定部１５４は、パラメータコントローラ１２４（図２６）を制御することにより、所定の値のパラメータを設定し、そのパラメータを、符号化ルール復元部１２１に供給させる。
【０２０５】
ここで、正誤判定部１５４は、例えば、各フレームの各ラインについて、ステップＳ７２の処理が行われるごとに、０から、１ラインの画素数までの範囲の整数値を、順次、パラメータの値として設定する。
【０２０６】
符号化ルール復元部１２１は、パラメータコントローラ１２４から、パラメータを受信すると、ステップＳ７３において、ラインシフト部１３６が、そのパラメータに対応する画素数だけ、注目ラインのＶＱ残差を左シフトし、その左シフト後のＶＱ残差を、ＶＱコードメモリ１３３に記憶された注目ラインのＶＱコード、およびコードブックメモリ１３５に記憶されたコードブックとともに、仮符号化データとして、復号部１２２に供給する。さらに、ラインシフト部１３６は、注目ラインをシフトした画素数を、仮復号付加情報として、判定部１２３に供給する。
【０２０７】
復号部１２２は、ステップＳ７４において、符号化ルール復元部１２１からの仮符号化データとしてのＶＱコード、ＶＱ残差、およびコードブックに基づいて、ベクトル逆量子化を行うことにより、注目ラインの画素値の復号を行い、その復号の結果得られる仮復号画素値を、判定部１２３に供給する。
【０２０８】
判定部１２３（図３０）では、符号化ルール復元部１２１が出力する仮復号付加情報と、復号部１２２が出力する仮復号画素値が、メモリ１５１に記憶される。さらに、判定部１２３では、ステップＳ７５において、符号化部１５２が、復号部１２２からの仮復号画素値をベクトル量子化し、その結果得られる仮ＶＱコードと仮ＶＱ残差を、比較部１５３に供給する。
【０２０９】
比較部１５３は、注目ラインについて、符号化部１５２からの仮ＶＱコードと、仮符号化データとしてのＶＱコードとを比較するとともに、符号化部１５２からの仮ＶＱ残差と、仮符号化データとしてのＶＱ残差とを比較し、それぞれの比較結果を、正誤判定部１５４に供給する。正誤判定部１５４は、ステップＳ７６において、注目ラインについて、仮ＶＱコードと、仮符号化データとしてのＶＱコードとが一致し、かつ仮ＶＱ残差と、仮符号化データとしてのＶＱ残差とが一致しているかどうかを判定し、いずれかが、または両方が一致していないと判定した場合、即ち、直前のステップＳ７２で設定したパラメータの値が、付加情報に一致していない場合、ステップＳ７２に戻り、新たな値のパラメータが設定され、以下、同様の処理が繰り返される。
【０２１０】
また、ステップＳ７６において、仮ＶＱコードと、仮符号化データとしてのＶＱコードとが一致し、かつ仮ＶＱ残差と、仮符号化データとしてのＶＱ残差とが一致していると判定された場合、即ち、直前のステップＳ７２で設定したパラメータの値が、付加情報に一致しており、従って、符号化データが復元されるとともに、仮復号付加情報として、元の付加情報が正しく復号された場合、ステップＳ７７に進み、正誤判定部１５４は、メモリ１５１を制御することにより、そこに記憶された注目ラインの各画素の仮復号画素値と、仮復号付加情報を、正しい復号結果である復号画素値と復号付加情報として、それぞれ出力させ、ステップＳ７８に進む。
【０２１１】
ステップＳ７８では、次に復号すべきラインがあるかどうかが判定され、あると判定された場合、ステップＳ７２に戻り、その、次に復号すべきラインを、新たに注目ラインとして、以下、同様の処理が繰り返される。
【０２１２】
また、ステップＳ７８において、次に復号すべきラインがないと判定された場合、復号処理を終了する。
【０２１３】
なお、図３２の復号処理は、各フレームについて行われる。
【０２１４】
以上のように、符号化データを得るための符号化ルールを、付加情報に基づいて破壊し、その破壊した符号化ルールによって符号化された埋め込み符号化データに対して、所定の操作を施すことにより、仮符号化データを得て、その仮符号化データを復号し、その復号結果を符号化して得られるものが、仮符号化データに一致するかどうかを判定することによって、符号化ルールが破壊される前の符号化データを復元するようにしたので、この符号化ルールの破壊および復元を利用して、符号化データのデータ量を増加させることなく、付加情報を埋め込むとともに、復号を行うことができる。
【０２１５】
ここで、本件出願人は、例えば、画像の相関性等を利用して、付加情報を画像に埋め込む手法を先に提案している。即ち、先に提案した方法は、例えば、フレームを構成するラインを、付加情報に基づいて入れ替え、その入れ替え後のフレームのラインを、元のフレームにおいて近接しているラインどうしの相関が高いことを利用して、元の位置に戻すものであるが、この相関を利用した方法では、場合によって、付加情報を埋め込むことが困難であることがあった。即ち、相関を利用した方法は、簡単には、付加情報が埋め込まれたフレームのあるラインに注目して、その注目ラインとの相関が最も高いラインを、注目ラインの隣に入れ替えることにより、ラインを、すべて、元の位置に戻すものであるが、画像によっては、注目ラインとの相関が最も高いラインが、注目ラインの隣に位置すべきラインではないことがあり、このようなラインについては、付加情報を埋め込むことにより、ラインを入れ替えてしまうと、相関を利用して、元の位置に戻すことができないため、付加情報を埋め込むことが困難であった。
【０２１６】
これに対して、上述した手法では、そのような復号の失敗がない。
【０２１７】
なお、図２６の実施の形態では、復号器１２を、符号化ルール復元部１２２と復号部１２２との組を１系統だけ設けて構成し、パラメータコントローラ１２４から出力するパラメータを順次変えることにより、各値のパラメータに対応する仮符号化データを順次得るようにしたが、復号器１２は、例えば、図３３に示すように、Ｍ系統の符号化ルール復元部１２１1乃至１２１Mと復号部１２２1乃至１２２Mを設けて構成し、各系統の符号化ルール復元部１２１m（ｍ＝１，２，・・・，Ｍ）に、異なる値のパラメータを与えて、各値のパラメータに対応する仮符号化データを同時に得るようにすることが可能である。
【０２１８】
また、上述の場合には、図１９の符号化部９１に、ベクトル量子化を行わせるようにしたが、符号化部９１には、ベクトル量子化以外の、例えば、予測符号化等を行わせることが可能である。そして、この場合、埋め込み部９２では、予測符号化による予測残差を、付加情報に基づいて操作することにより、付加情報を埋め込むようにすることが可能である。
【０２１９】
さらに、上述の場合には、各ラインのＶＱ残差を、付加情報に基づいてシフトすることにより、その付加情報を埋め込むようにしたが、付加情報は、その他、例えば、ＶＱ残差を表す値のビット列をシフトしたりすること等によって埋め込むことが可能である。
【０２２０】
また、上述の場合には、フレームごとに、コードブックを作成し、符号化データに含めるようにしたが、コードブックは、あらかじめ作成しておき、埋め込み圧縮符号化器１１と復号器１２それぞれにおいて記憶しておくようにすることが可能である。さらに、コードブックは、複数フレームごとや、１フレームの所定の領域ごとに作成することも可能である。
【０２２１】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０２２２】
そこで、図３４は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０２２３】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク２０５やＲＯＭ２０３に予め記録しておくことができる。
【０２２４】
あるいはまた、プログラムは、フロッピー（登録商標）ディスク、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)やスピーカ等で構成される出力部２０６から出力、あるいは、通信部２０８から送信、さらには、ハードディスク２０５に記録等させる。
【０２２７】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０２２８】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０２２９】
なお、本実施の形態では、画像データを符号化の対象としたが、符号化の対象とするデータは、画像データに限定されるものではなく、音声データ（オーディオデータ）や、コンピュータのプログラム等の各種のデータを採用することが可能である。
【図面の簡単な説明】
【０２３０】
【図１】本発明を適用した埋め込み圧縮／復号システムの一実施の形態の構成例を示す図である。
【図２】埋め込み圧縮符号化器１１の第１の構成例を示すブロック図である。
【図３】可変長符号化部２３の構成例を示すブロック図である。
【図４】可変長符号化を説明するための図である。
【図５】画素値の出現頻度と、画素値に割り当てられる符号の符号長との関係を示す図である。
【図６】ハフマンテーブルの例を示す図である。
【図７】画素値の出現頻度に応じて割り当てられた符号と、その符号の変換を説明する図である。
【図８】埋め込み符号化データの例を示す図である。
【図９】埋め込み符号化データを、元の符号化データに復元する方法を説明する図である。
【図１０】埋め込み符号化処理を説明するフローチャートである。
【図１１】変換テーブル作成処理を説明するフローチャートである。
【図１２】符号化データ変換処理を説明するフローチャートである。
【図１３】埋め込み圧縮符号化器１１の第２の構成例を示すブロック図である。
【図１４】復号器１２の第１の構成例を示すブロック図である。
【図１５】可変長復号部５２および５６の構成例を示すブロック図である。
【図１６】ハフマンテーブル生成部５３の構成例を示すブロック図である。
【図１７】逆変換テーブル作成部５４の構成例を示すブロック図である。
【図１８】復号処理を説明するフローチャートである。
【図１９】埋め込み圧縮符号化器１１の第３の構成例を示すブロック図である。
【図２０】埋め込み符号化処理を説明するフローチャートである。
【図２１】符号化部９１の構成例を示すブロック図である。
【図２２】ベクトル量子化による符号化を説明する図である。
【図２３】埋め込み部９２の構成例を示すブロック図である。
【図２４】ラインをシフトすることによる付加情報の埋め込みを説明する図である。
【図２５】埋め込み符号化処理を説明するフローチャートである。
【図２６】復号器１２の第２の構成例を示すブロック図である。
【図２７】復号処理を説明するフローチャートである。
【図２８】符号化ルール復元部１２１の構成例を示すブロック図である。
【図２９】復号部１２２の構成例を示すブロック図である。
【図３０】判定部１２３の構成例を示すブロック図である。
【図３１】判定部１２３の処理を説明する図である。
【図３２】復号処理を説明するフローチャートである。
【図３３】復号器１２の第３の構成例を示すブロック図である。
【図３４】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
【０２３１】
１  符号化装置，  ２  復号装置，  ３  記録媒体，  ４  伝送媒体，  １１
埋め込み圧縮符号化器，  １２  復号器，  ２１  フレームメモリ，  ２２  付加情報メモリ，  ２３  可変長符号化部，  ２４  変換テーブル作成部，  ２５  符号化ルール破壊部，  ２６  ＭＵＸ，  ３１  頻度テーブル作成部，  ３２  ハフマン木作成部，  ３３  ハフマンテーブル作成部，  ３４  符号化部，
４１  符号化ルール破壊部，  ５１  ＤＥＭＵＸ，  ５２  可変長復号部，  ５３  ハフマンテーブル生成部，  ５４  逆変換テーブル作成部，  ５５  符号化ルール復元部，  ５６  可変長復号部，  ６１  ハフマン木作成部，  ６２  ハフマンテーブル作成部，  ６３  復号部，  ７１  頻度テーブル作成部，  ７２  ハフマン木作成部，  ７３  ハフマンテーブル作成部，  ８１  比較部，  ８２  符号対応付け部，  ９１  符号化部，  ９２  埋め込み部，  １０１  フレームメモリ，  １０２  コードブック作成部，  １０３  ベクトル量子化部，  １１１  ＶＱコードメモリ，  １１２  ＶＱ残差メモリ，  １１３  コードブックメモリ，  １１４  ラインシフト部，  １１５  圧縮部，  １１６  ＭＵＸ，  １２１，１２１1乃至１２１M  符号化ルール復元部，  １２２，１２２1乃至１２２M  復号部，  １２３  判定部，  １２４  パラメータコントローラ，
１３１  ＤＥＭＵＸ，  １３２  伸張部，  １３３  ＶＱコードメモリ，  １３４  ＶＱ残差メモリ，  １３５  コードブックメモリ，  １３６  ラインシフト部，  １４１  ベクトル逆量子化部，  １４２  加算部，  １５１  メモリ，
１５２  符号化部，  １５３  比較部，  １５４  正誤判定部，  ２０１  バス，  ２０２  CPU，  ２０３  ROM，  ２０４  RAM，  ２０５  ハードディスク，  ２０６  出力部，  ２０７  入力部，  ２０８  通信部，  ２０９  ドライブ，  ２１０  入出力インタフェース，  ２１１  リムーバブル記録媒体
【図１】
2008283701.tif 000003
【図２】
2008283701.tif 000004
【図３】
2008283701.tif 000005
【図４】
2008283701.tif 000006
【図５】
2008283701.tif 000007
【図６】
2008283701.tif 000008
【図７】
2008283701.tif 000009
【図８】
2008283701.tif 000010
【図９】
2008283701.tif 000011
【図１０】
2008283701.tif 000012
【図１１】
2008283701.tif 000013
【図１２】
2008283701.tif 000014
【図１３】
2008283701.tif 000015
【図１４】
2008283701.tif 000016
【図１５】
2008283701.tif 000017
【図１６】
2008283701.tif 000018
【図１７】
2008283701.tif 000019
【図１８】
2008283701.tif 000020
【図１９】
2008283701.tif 000021
【図２０】
2008283701.tif 000022
【図２１】
2008283701.tif 000023
【図２２】
2008283701.tif 000024
【図２３】
2008283701.tif 000025
【図２４】
2008283701.tif 000026
【図２５】
2008283701.tif 000027
【図２６】
2008283701.tif 000028
【図２７】
2008283701.tif 000029
【図２８】
2008283701.tif 000030
【図２９】
2008283701.tif 000031
【図３０】
2008283701.tif 000032
【図３１】
2008283701.tif 000033
【図３２】
2008283701.tif 000034
【図３３】
2008283701.tif 000035
【図３４】
2008283701.tif 000036