(57)【特許請求の範囲】
【請求項１】
第１のディジタルデータに第２のディジタルデータを埋め込むデータ処理装置であって、
上記第１のディジタルデータ内の、所定数ビット数からなるターゲットデータをビットスワップするビットスワップ手段と、
上記ターゲットデータ周辺の周辺データに対応する値から上記ターゲットデータに対応する値を予測する予測値を出力する予測手段と、
上記予測手段により出力される予測値と、ビットスワップされた上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソート手段と、
上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータに応じて、補正コードを出力する補正コード出力手段と、
上記第２のディジタルデータに応じて、上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記第１のディジタルデータに上記第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力手段と
を備えることを特徴とするデータ処理装置。
【請求項２】
上記予測手段は、上記ターゲットデータ周辺の第１のコードである周辺データに対応する値をｎ進数（ｎ＞２の自然数）に変換した値から上記ターゲットデータに対応する値を予測する予測値を出力し、
上記ソート手段は、上記予測手段により出力される予測値と、ビットスワップされた第１のコードとしての上記ターゲットデータに対応する各値をｎ進数に変換した値との絶対値差分値を、予測誤差値として、ビットスワップされた上記ターゲットデータ毎に検出し、当該予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートする
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
上記予測手段は、上記ターゲットデータ周辺のバイナリコードである周辺データに対応する値を１０進数に変換した値から上記ターゲットデータに対応する値を予測する予測値を出力し、
上記ソート手段は、上記予測手段により出力される予測値と、ビットスワップされたバイナリコードとしての上記ターゲットデータに対応する各値を１０進数に変換した値との絶対値差分値を、予測誤差値として、ビットスワップされた上記ターゲットデータ毎に検出し、当該予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートする
ことを特徴とする請求項２に記載のデータ処理装置。
【請求項４】
上記第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードである新コードに、上記第１のディジタルデータを変換するコード変換手段をさらに備え、
上記予測手段は、上記ターゲットデータ周辺の上記新コードである周辺データに対応する値を１０進数に変換した値から上記ターゲットデータに対応する値を予測する予測値を出力し、
上記ソート手段は、上記予測手段により出力される予測値と、ビットスワップされた上記新コードとしての上記ターゲットデータに対応する各値を１０進数に変換した値との絶対値差分値を、予測誤差値として、ビットスワップされた上記ターゲットデータ毎に検出し、当該予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートする
ことを特徴とする請求項２に記載のデータ処理装置。
【請求項５】
上記ターゲットデータに埋め込み可能なビット数に相当する上記第２のディジタルデータを読み出す読出し手段をさらに備え、
上記埋め込みデータ出力手段は、上記読出し手段により読み出された上記第２のディジタルデータに応じて、上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記埋め込みデータとして出力する
ことを特徴とする請求項２に記載のデータ処理装置。
【請求項６】
補正コード出力手段は、上記予測誤差値が最小の、ビットスワップされた上記ターゲットデータと、上記ターゲットデータとの、上記ソート手段によりソートされた順位の差を上記補正コードとして出力する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項７】
上記補正コード出力手段により出力される補正コードを圧縮符号化する圧縮符号化手段をさらに備える
ことを特徴とする請求項６に記載のデータ処理装置。
【請求項８】
上記圧縮符号化手段は、上記補正コードをエントロピー符号化する
ことを特徴とする請求項７に記載のデータ処理装置。
【請求項９】
上記第１のディジタルデータは、画像データである
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項１０】
上記第１のディジタルデータは、音声データである
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項１１】
第１のディジタルデータに第２のディジタルデータを埋め込むデータ処理方法であって、
上記第１のディジタルデータ内の、所定数ビット数からなるターゲットデータをビットスワップするビットスワップステップと、
上記ターゲットデータ周辺の周辺データに対応する値から上記ターゲットデータに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップにより出力される予測値と、ビットスワップされた上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータに応じて、補正コードを出力する補正コード出力ステップと、
上記第２のディジタルデータに応じて、上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記第１のディジタルデータに上記第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップと
を備えることを特徴とするデータ処理方法。
【請求項１２】
第１のディジタルデータに第２のディジタルデータを埋め込むデータ処理プログラムが記録される記録媒体であって、
上記第１のディジタルデータ内の、所定数ビット数からなるターゲットデータをビットスワップするビットスワップステップと、
上記ターゲットデータ周辺の周辺データに対応する値から上記ターゲットデータに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップにより出力される予測値と、ビットスワップされた上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータに応じて、補正コードを出力する補正コード出力ステップと、
上記第２のディジタルデータに応じて、上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記第１のディジタルデータに上記第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップと
を含む処理を、コンピュータに実行させるデータ処理プログラムが記録されている
ことを特徴とする記録媒体。
【請求項１３】
第１のディジタルデータに第２のディジタルデータを埋め込むデータ処理装置であって、
上記第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードである新コードに、上記第１のディジタルデータを変換するコード変換手段と、
上記新コードに変換された第１のディジタルデータ内の、所定ビット数からなる上記ターゲットデータをビットスワップするビットスワップ手段と、
上記ターゲットデータ周辺の新コードである周辺データに対応する値から上記ターゲットデータに対応する値を予測する予測値を出力する予測手段と、
上記予測手段により出力される予測値と、ビットスワップされた新コードとしての上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソート手段と、
上記第２のディジタルデータに応じて、上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記第１のディジタルデータに上記第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力手段と
を備えることを特徴とするデータ処理装置。
【請求項１４】
第１のディジタルデータに第２のディジタルデータを埋め込むデータ処理方法であって、
上記第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードである新コードに、上記第１のディジタルデータを変換するコード変換ステップと、
上記新コードに変換された第１のディジタルデータ内の、所定ビット数からなる上記ターゲットデータをビットスワップするビットスワップステップと、
上記ターゲットデータ周辺の新コードである周辺データに対応する値から上記ターゲットデータに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップにより出力される予測値と、ビットスワップされた新コードとしての上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記第２のディジタルデータに応じて、上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記第１のディジタルデータに上記第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップと
を備えることを特徴とするデータ処理方法。
【請求項１５】
第１のディジタルデータに第２のディジタルデータを埋め込むデータ処理プログラムが記録される記録媒体であって、
上記第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードである新コードに、上記第１のディジタルデータを変換するコード変換ステップと、
上記新コードに変換された第１のディジタルデータ内の、所定ビット数からなる上記ターゲットデータをビットスワップするビットスワップステップと、
上記ターゲットデータ周辺の新コードである周辺データに対応する値から上記ターゲットデータに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップにより出力される予測値と、ビットスワップされた新コードとしての上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記第２のディジタルデータに応じて、上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの内の１つを、上記第１のディジタルデータに上記第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップと
を含む処理を、コンピュータに実行させるデータ処理プログラムが記録されている
ことを特徴とする記録媒体。
【請求項１６】
第１のディジタルデータに第２のディジタルデータが埋め込まれた埋め込みデータおよび補正コードから、上記第１のディジタルデータおよび上記第２のディジタルデータを復号する復号装置であって、
上記埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップ手段と、
上記ターゲットデータ周辺の既に復号されたデータである復号データに対応する値から上記ターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測手段と、
上記予測手段により出力される予測値と、上記ビットスワップ手段によりビットスワップされた上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソート手段と、
上記補正コードに応じて、上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータのうちの１つのコードを、上記ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する復号データ出力手段と、
上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記第２のディジタルデータを出力する第２のディジタルデータ出力手段と
を備えることを特徴とする復号装置。
【請求項１７】
上記予測手段は、第１のコードである既に復号された上記ターゲットデータ周辺の復号データに対応する値をｎ進数（ｎ＞２である自然数）に変換した値から上記ターゲットデータより復号される復号データに対応する値を予測する予測値を出力し、
上記ソート手段は、上記予測手段により出力される予測値と、上記ビットスワップ手段によりビットスワップされた第１のコードとしてのターゲットデータに対応する各値をｎ進数に変換した値との絶対値差分値を、予測誤差値として、ビットスワップされた上記ターゲットデータ毎に検出し、当該予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートする
ことを特徴とする請求項１６に記載の復号装置。
【請求項１８】
上記予測手段は、バイナリコードである既に復号された上記ターゲットデータ周辺の復号データに対応する値を１０進数に変換した値から上記ターゲットデータより復号される復号データに対応する値を予測する予測値を出力し、
上記ソート手段は、上記予測手段により出力される予測値と、上記ビットスワップ手段によりビットスワップされたバイナリコードとしての上記ターゲットデータに対応する各値を１０進数に変換した値との絶対値差分値を、予測誤差値として、ビットスワップされた上記ターゲットデータ毎に検出し、当該予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートする
ことを特徴とする請求項１７に記載の復号装置。
【請求項１９】
上記予測手段は、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する１０進数の値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードを表す新コードである既に復号された上記ターゲットデータ周辺の復号データに対応する値から上記ターゲットデータより復号される復号データに対応する値を予測する予測値を出力し、
上記ソート手段は、上記予測手段より出力される予測値と、上記ビットスワップ手段によりビットスワップされた新コードとしてのターゲットデータに対応する各値との絶対値差分値を、予測誤差値として、ビットスワップされた上記ターゲットデータ毎に検出し、当該予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートする
ことを特徴とする請求項１７に記載の復号装置。
【請求項２０】
上記復号データ出力手段は、上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータのうちの、上記補正コードに対応する順位のビットスワップされた上記ターゲットデータを、上記ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する
ことを特徴とする請求項１９に記載の復号装置。
【請求項２１】
上記復号データ出力手段により出力される上記新コードである復号データに対応する１０進数の値に相当するバイナリコードを出力するコード変換手段をさらに備える
ことを特徴とする請求項２０に記載の復号装置。
【請求項２２】
補正コードは圧縮符号化されており、
当該圧縮符号化されている補正コードを復号し補正コードを出力する復号手段をさらに備える
ことを特徴とする請求項１６に記載の復号装置。
【請求項２３】
補正コードはエントロピー符号化されており、
上記復号手段は、当該エントロピー符号化されている補正コードを復号し補正コードを出力する
ことを特徴とする請求項２２に記載の復号装置。
【請求項２４】
上記第１のディジタルデータは、画像データである
ことを特徴とする請求項１６に記載の復号装置。
【請求項２５】
上記第１のディジタルデータは、音声データである
ことを特徴とする請求項１６に記載の復号装置。
【請求項２６】
第１のディジタルデータに第２のディジタルデータが埋め込まれた埋め込みデータおよび補正コードから、上記第１のディジタルデータおよび上記第２のディジタルデータを復号する復号方法であって、
上記埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、
上記ターゲットデータ周辺の既に復号されたデータである復号データに対応する値から上記ターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップにより出力される予測値と、上記ビットスワップステップによりビットスワップされた上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記補正コードに応じて、上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータのうちの１つのコードを、上記ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する復号データ出力ステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記第２のディジタルデータを出力する第２のディジタルデータ出力ステップと
を備えることを特徴とする復号方法。
【請求項２７】
第１のディジタルデータに第２のディジタルデータが埋め込まれた埋め込みデータおよび補正コードから、上記第１のディジタルデータおよび上記第２のディジタルデータを復号する復号プログラムが記録される記録媒体であって、
上記埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、
上記ターゲットデータ周辺の既に復号されたデータである復号データに対応する値から上記ターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップにより出力される予測値と、上記ビットスワップステップによりビットスワップされた上記ターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記補正コードに応じて、上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータのうちの１つのコードを、上記ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する復号データ出力ステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記第２のディジタルデータを出力する第２のディジタルデータ出力ステップと
を含む処理を、コンピュータに実行させる復号プログラムが記録されている
ことを特徴とする記録媒体。
【請求項２８】
第１のディジタルデータに第２のディジタルデータが埋め込まれた埋め込みデータから、上記第１のディジタルデータおよび上記第２のディジタルデータを復号する復号装置であって、
上記埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップ手段と、
０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードを表す新コードであり、上記ターゲットデータ周辺の既に復号されたデータである復号データに対応する値から上記ターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測手段と、
上記予測手段より出力される予測値と、上記ビットスワップ手段によりビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソート手段と、
上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記第２のディジタルデータを出力する第２のディジタルデータ出力手段と、
上記ソート手段によりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記ターゲットデータを復号することにより得られる復号データを出力する復号データ出力手段と、
上記復号データ出力手段により出力される上記新コードである復号データに対応する元のコードを出力するコード変換手段と
を備えることを特徴とする復号装置。
【請求項２９】
第１のディジタルデータに第２のディジタルデータが埋め込まれた埋め込みデータから、上記第１のディジタルデータおよび上記第２のディジタルデータを復号する復号方法であって、
上記埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、
０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードを表す新コードであり、上記ターゲットデータ周辺の既に復号されたデータである復号データに対応する値から上記ターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップより出力される予測値と、上記ビットスワップステップによりビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記第２のディジタルデータを出力する第２のディジタルデータ出力ステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記ターゲットデータを復号することにより得られる復号データを出力する復号データ出力ステップと、
上記復号データ出力ステップにより出力される上記新コードである復号データに対応する元のコードを出力するコード変換ステップと
を備えることを特徴とする復号方法。
【請求項３０】
第１のディジタルデータに第２のディジタルデータが埋め込まれた埋め込みデータから、上記第１のディジタルデータおよび上記第２のディジタルデータを復号する復号プログラムが記録される記録媒体であって、
上記埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、
０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられる上記コードを表す新コードであり、上記ターゲットデータ周辺の既に復号されたデータである復号データに対応する値から上記ターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、
上記予測ステップより出力される予測値と、上記ビットスワップステップによりビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされた上記ターゲットデータをソートするソートステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記第２のディジタルデータを出力する第２のディジタルデータ出力ステップと、
上記ソートステップによりソートされた、ビットスワップされた上記ターゲットデータの順位に応じて、上記ターゲットデータを復号することにより得られる復号データを出力する復号データ出力ステップと、
上記復号データ出力ステップにより出力される上記新コードである復号データに対応する元のコードを出力するコード変換ステップと
を含む処理を、コンピュータに実行させる復号プログラムが記録されている
ことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ処理装置およびデータ処理方法、復号装置および復号方法、並びに記録媒体に関し、特に、例えば、復号精度が高いデータの埋め込みを行うことができるようにするデータ処理装置およびデータ処理方法、復号装置および復号方法、並びに記録媒体に関する。
【０００２】
【従来の技術】
図１は、画像を構成する画素（画素値）を表すビット列を構成する各ビットを入れ替えるビットスワップを行うことにより、その画素に、データを埋め込む従来の埋め込み符号化装置の一例の構成を示している。
【０００３】
画像データは、画像データ用メモリ１に供給され、画像データ用メモリ１は、そこに供給される画像データを一時記憶する。また、画像データに埋め込まれるデータ（以下、適宜、埋め込み対象データという）は、埋め込み対象データ用メモリ２に供給され、埋め込み対象データ用メモリ２は、そこに供給される埋め込み対象データを一時記憶する。
【０００４】
ビットスワップ埋め込み部３は、画像データ用メモリ１に記憶された画像データを構成する画素を、例えば、ラスタスキャン順で、順次、注目画素とし、その画素値を読み出すとともに、埋め込み対象データ用メモリ２に記憶された埋め込み対象データを読み出す。さらに、ビットスワップ埋め込み部３は、注目画素の画素値を表すビット列を構成する各ビットを、埋め込み対象データに応じてビットスワップすることにより、注目画素の画素値に埋め込み対象データを埋め込み、その埋め込みの結果得られる画素値（以下、適宜、埋め込み後画素値という）を、埋め込み後画像データ用メモリ４に供給する。
【０００５】
埋め込み後画像データ用メモリ４は、ビットスワップ埋め込み部３から供給される埋め込み後画素値を、注目画素の位置に対応するアドレスに記憶し、例えば、１フレーム分の埋め込み後画素値を記憶すると、その１フレーム分の埋め込み後画素値で構成される画像データ（以下、適宜、埋め込み後画像データという）を出力する。
【０００６】
次に、図２のフローチャートを参照して、図１の埋め込み符号化装置の処理（埋め込み符号化処理）について説明する。
【０００７】
埋め込み符号化装置に対して、例えば、１フレーム（またはフィールド）の画像データと、その１フレームの画像データに埋め込む埋め込み対象データが供給されると、ステップＳ１において、画像データ用メモリ１は、その画像データを記憶し、埋め込み対象データ用メモリ２は、埋め込み対象データを記憶する。
【０００８】
そして、ステップＳ２に進み、ビットスワップ埋め込み部３は、画像データ用メモリ１に記憶された画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素としていないものを注目画素とし、その画素値を読み出すとともに、その画素値に埋め込み可能なビット数分の埋め込み対象データを、埋め込み対象データ用メモリ２から読み出す。さらに、ステップＳ２では、ビットスワップ埋め込み部３は、注目画素の画素値を表すビット列を構成する各ビットを、埋め込み対象データに応じてビットスワップすることにより、注目画素の画素値に埋め込み対象データを埋め込み、その埋め込みの結果得られる埋め込み後画素値を、埋め込み後画像データ用メモリ４に供給して記憶させる。
【０００９】
その後、ステップＳ３に進み、ビットスワップ埋め込み部３は、画像データ用メモリ１に記憶された画像データを構成するすべての画素を注目画素として処理を行ったかどうかを判定し、まだ、すべての画素を注目画素として処理を行っていないと判定した場合、ステップＳ２に戻る。
【００１０】
また、ステップＳ３において、画像データ用メモリ１に記憶された画像データを構成するすべての画素を注目画素として処理を行ったと判定された場合、即ち、埋め込み後画像データ用メモリ４に、１フレーム分の埋め込み後画素値で構成される画像データ（埋め込み後画像データ）が記憶された場合、ステップＳ４に進み、埋め込み後画像データ用メモリ４は、記憶している埋め込み後画像データを出力し、処理を終了する。
【００１１】
なお、図２のフローチャートの処理は、埋め込み符号化装置に、１フレームの画像データが供給されるごとに、その１フレームの画像データについて行われる。
【００１２】
以上のような埋め込み符号化処理によれば、例えば、図３に示すように、埋め込み対象データが画素値に埋め込まれる。
【００１３】
即ち、図３は、注目画素の画素値が１６であり、その注目画素に、値が３の埋め込み対象データが埋め込まれる場合を示している。
【００１４】
例えば、いま、画素値に８ビットが割り当てられているとすると（以下においても、同様とする）、画素値「１６」は、一般に、バイナリコードで「０００１００００」と表される。従って、このバイナリコード「０００１００００」をビットスワップすることにより得られるビット列は、図３に示すような８パターンだけ存在する。ビットスワップ埋め込み部３は、画素値に対応するバイナリコードを構成するビット列について、そのビット列を構成するビットの入れ替えパターン（ビットスワップのパターン）と、埋め込み対象データとを対応付けて記憶しており、注目画素に埋め込む埋め込み対象データに対応付けられたパターンにしたがって、注目画素の画素値を表すバイナリコードをビットスワップする。
【００１５】
図３においては、画素値「１６」を表すバイナリコード「０００１００００」をビットスワップすることにより得られる８通りのビットスワップパターン「０００１００００」、「００１０００００」、「０１００００００」、「１０００００００」、「０００００００１」、「００００００１０」、「０００００１００」、「００００１０００」それぞれに対して、埋め込み対象データ「０」、「１」、「２」、「３」、「４」、「５」、「６」、「７」が対応付けられており、従って、埋め込み対象データが「３」である場合には、ビットスワップ埋め込み部３は、画素値「１６」を表すバイナリコード「０００１００００」を、「３」に対応付けられているバイナリコード「１０００００００」にビットスワップし、そのビットスワップの結果得られたバイナリコード「１０００００００」で表される画素値「１２８」を、埋め込み後画素値として出力する。
【００１６】
以上から、画素値に、埋め込み対象データを、ビットスワップによって埋め込む場合においては、画素値に、どの程度の埋め込み対象データを埋め込むことができるかは、画素値を表すバイナリコードを構成するビット列の０または１の数によって決まる。
【００１７】
即ち、画素値に埋め込むことのできる情報量は、その画素値を表すバイナリコードのビットスワップの全パターン数によって決まり、ビットスワップの全パターン数をＮとすれば、ｌｏｇ2Ｎビットが、画素値に埋め込むことのできる情報量となる。ここで、図４に、８ビットのバイナリコードについて、０または１の数と、埋め込むことのできる情報量との関係を示す。
【００１８】
次に、図５は、図１の埋め込み符号化装置が出力する埋め込み後画像データから、元の画素値と埋め込み対象データを復号する復号装置の一例の構成を示している。
【００１９】
埋め込み後画像データは、埋め込み後画像データ用メモリ１１に供給されるようになっており、埋め込み後画像データ用メモリ１１は、そこに供給される埋め込み後画像データを一時記憶する。
【００２０】
ビットスワップ戻し部１２は、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成する画素を、例えば、ラスタスキャン順に、順次、注目画素とし、その注目画素の埋め込み後画素値を、埋め込み後画像データ用メモリ１１から読み出すとともに、注目画素の画素値の予測値を、予測値取得部１５から受信する。さらに、ビットスワップ戻し部１２は、注目画素の埋め込み後画素値を表すビット列を構成する各ビットを、注目画素の予測値に応じてビットスワップすることにより、注目画素の画素値を復号するとともに、その注目画素に埋め込まれていた埋め込み対象データを復号する。なお、復号された注目画素の画素値は、ビットスワップ戻し部１２から画像データ用メモリ１３に供給され、埋め込み対象データは、ビットスワップ戻し部１２から埋め込み対象データ用メモリ１４に供給されるようになっている。
【００２１】
画像データ用メモリ１３は、ビットスワップ戻し部１２から供給される、復号された注目画素の画素値を、その注目画素の位置に対応するアドレスに一時記憶する。埋め込み対象データ用メモリ１４は、ビットスワップ戻し部１２から供給される、復号された埋め込み対象データを一時記憶する。
【００２２】
予測値取得部１５は、画像データ用メモリ１３に記憶された、既に復号された画素値に基づいて、注目画素の予測値を求め、ビットスワップ戻し部１２に供給する。
【００２３】
なお、予測値取得部１５においては、例えば、画像データ用メモリ１３に記憶された、既に復号された画素値のうちの、注目画素の左や上に隣接する画素の画素値を、そのまま予測値とすることができる。あるいは、また、予測値取得部１５においては、例えば、画像データ用メモリ１３に記憶された、既に復号された画素値のうちの、注目画素に空間的または時間的に近い位置にある画素の画素値の平均値を求め、これを、予測値とするようにすることも可能である。
【００２４】
次に、図６のフローチャートを参照して、図５の復号装置の処理（復号処理）について説明する。
【００２５】
復号装置に対して、例えば、１フレーム（またはフィールド）の埋め込み後画像データが供給されると、ステップＳ１１において、埋め込み後画像データ用メモリ１１は、その埋め込み後画像データを記憶する。
【００２６】
その後、ビットスワップ戻し部１２は、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素としていないものを注目画素とし、予測値取得部１５は、ステップＳ１２において、画像データ用メモリ１３に記憶された、既に復号された画素値に基づいて、注目画素の予測値を求め、ビットスワップ戻し部１２に供給する。
【００２７】
ビットスワップ戻し部１２は、注目画素の埋め込み後画素値を、埋め込み後画像データ用メモリ１１から読み出すとともに、注目画素の画素値の予測値を、予測値取得部１５から受信し、ステップＳ１３において、注目画素の埋め込み後画素値を表すビット列を構成する各ビットを、注目画素の予測値に応じてビットスワップすることにより、注目画素の画素値を復号するとともに、その注目画素に埋め込まれていた埋め込み対象データを復号して、ステップＳ１４に進む。
【００２８】
ステップＳ１４では、ビットスワップ戻し部１２は、注目画素の画素値の復号値を、画像データ用メモリ１３に供給して記憶させるとともに、埋め込み対象データの復号値を、埋め込み対象データ用メモリ１４に供給して記憶させ、ステップＳ１５に進む。
【００２９】
ステップＳ１５では、ビットスワップ戻し部１２は、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成するすべての画素を注目画素として処理を行ったかどうかを判定し、まだ、すべての画素を注目画素として処理を行っていないと判定した場合、ラインスキャン順で、まだ、注目画素としていない画素を、新たに注目画素として、ステップＳ１２に戻る。
【００３０】
また、ステップＳ１５において、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成するすべての画素を注目画素として処理を行ったと判定された場合、即ち、画像データ用メモリ１３に、１フレーム分の画素値で構成される画像データが記憶されるとともに、埋め込み対象データ用メモリ１４に、その画像データに埋め込まれていた埋め込み対象データが記憶された場合、ステップＳ１６に進み、画像データ用メモリ１３から、そこに記憶されている画像データ（の復号値）が出力されるとともに、埋め込み対象データ用メモリ１４から、そこに記憶されている埋め込み対象データ（の復号値）が出力され、処理を終了する。
【００３１】
なお、図６のフローチャートの処理は、復号装置に、１フレームの埋め込み後画像データが供給されるごとに、その１フレームの埋め込み後画像データについて行われる。
【００３２】
以上のような復号処理によれば、例えば、図７に示すように、埋め込み後画素値が、画素値と埋め込み対象データに復号される。
【００３３】
即ち、図７は、図３で説明したように、画素値「１６」に、値が３の埋め込み対象データを埋め込むことによって得られた埋め込み後画素値「１２８」を復号する場合を示している。
【００３４】
埋め込み後画素値「１２８」を表すバイナリコードは、「１０００００００」であるが、このバイナリコードは、元の画素値を表すバイナリコードをビットスワップすることにより得られたものであるから、元の画素値を表すバイナリコードは、埋め込み後画素値「１２８」を表すバイナリコード「１０００００００」をビットスワップすることにより得られる全パターンのビット列の中に存在する。従って、埋め込み後画素値「１２８」を表すバイナリコード「１０００００００」をビットスワップすることにより得られる全パターンのビット列の中から、元の画素値を表すバイナリコードを見つけ出すことが、元の画素値を復号することになる。
【００３５】
また、元の画素値に対応するバイナリコードは、その埋め込み対象データに対応するビットスワップのパターンにしたがってビットスワップされることにより、埋め込み後画素値とされるから、埋め込み後画素値を表すバイナリコードを、元の画素値を表すバイナリコードとするためのビットスワップのパターンが分かれば、埋め込み後画素値に埋め込まれている埋め込み対象データを復号することができる。
【００３６】
そこで、ビットスワップ戻し部１２は、まず、画素値を復号するために、埋め込み後画素値「１２８」を表すバイナリコード「１０００００００」をビットスワップすることにより、そのバイナリコードから得られる全パターンのビット列を求める。さらに、ビットスワップ戻し部１２は、各パターンのビット列が表す画素値に対して、予測値取得部１５からの注目画素の予測値の予測誤差が最も小さくなるパターンのビット列を見つけ出す。即ち、いま、予測値取得部１５が出力する注目画素の予測値が、例えば「１４」であったとすると、埋め込み後画素値「１２８」を表すバイナリコード「１０００００００」から得られる、図７の８パターンのビット列が表す画素値の中で、予測値「１４」との予測誤差が最も小さいのは、１６であり、この画素値「１６」が、元の画素値として復号される。
【００３７】
また、ビットスワップ戻し部１２は、ビットスワップ埋め込み部３における場合と同一の、ビットスワップのパターンと埋め込み対象データとの対応付け情報を記憶しており、この対応付け情報から、復号された画素値「１６」を表すバイナリコード「０００１０００」を、埋め込み後画素値「１２８」を表すバイナリコード「１０００００００」にビットスワップするビットスワップパターンに対応付けられている埋め込み対象データ「３」を、注目画素の画素値「１６」に埋め込まれていた埋め込み対象データとして復号する。
【００３８】
以上のようにして、埋め込み後画素値「１２８」は、元の画素値「１６」とそこに埋め込まれた埋め込み対象データ「３」に復号される。
【００３９】
なお、例えば、いま、埋め込み後画像データをラスタスキャン順に復号していった場合に、注目画素の左隣の画素の画素値を、注目画素の予測値として、そのまま用いるとすると、埋め込み後画像データの最も左の画素については、予測値となる画素値が存在しないことになる。そこで、埋め込み符号化時においては、例えば、画像データの最も左の画素には、埋め込み対象データを埋め込まないようにするとともに、復号時においては、埋め込み後画像データの最も左の画素より右側の画素を、復号対象とするようにすることができる。
【００４０】
【発明が解決しようとする課題】
ところで、図５の復号装置では、注目画素の画素値の予測値の予測誤差が小さいことを前提として、画素値と埋め込み対象データの復号を行っている。
【００４１】
従って、図７で説明したように、画素値「１６」に、値が３の埋め込み対象データを埋め込むことによって得られた埋め込み後画素値「１２８」を復号する場合において、元の画素値「１６」を比較的精度良く予測する予測値「１４」が得られたときには、埋め込み後画素値「１２８」を、正確に、元の画素値「１６」に復号することができる。
【００４２】
しかしながら、予測値の精度は比較的良い場合であっても、元の画素値の値が小さい場合には、埋め込み後画素値を、元の画素値に正確に復号することが困難なことがある。さらに、図５の復号装置では、画素値を正確に復号することができなければ、元の画素値を表すバイナリコードを、埋め込み後画素値を表すバイナリコードにビットスワップするビットスワップパターンに基づいて復号される埋め込み対象データも、正確に復号することができない。
【００４３】
具体的には、注目画素の画素値が、値の小さい、例えば２である場合は、その注目画素の予測値として、比較的正確な「１」が得られたとしても、正確に復号することができない。
【００４４】
即ち、注目画素の画素値「２」のバイナリコードは、「００００００１０」であるから、このバイナリコードのビットスワップパターンは、図７における場合と同様に、８パターンあり、埋め込み符号化によって、その８パターンのうちのいずれかのビット列を表す埋め込み後画素値とされる。そして、この埋め込み後画素値を復号する場合に、上述のように、比較的予測精度の高い予測値（元の画素値「２」に近い予測値）「１」が得られたとしても、図７に示した、「１」が１ビットだけの８パターンのビット列のうちの、予測値「１」の予測誤差を最小にするのは、「１」を表すバイナリコード「０００００００１」であり、従って、埋め込み後画素値「２」は、バイナリコード「０００００００１」が表す画素値「１」に復号され、元の画素値「２」には復号されない。
【００４５】
このように、値の小さな画素値について、比較的正確な予測値が得られても、正確に復号を行うことができないのは、画素値に割り当てられるバイナリコードに起因する。
【００４６】
即ち、８ビットのバイナリコードのうち、例えば、「１」が１ビットだけのもの（従って、「０」が７ビットあるもの）を考えると、そのようなバイナリコードのビットスワップパターンは、図７に示した８パターンであるが、この８パターンのバイナリコード「０００００００１」、「００００００１０」、「０００００１００」、「００００１０００」、「０００１００００」、「００１０００００」、「０１００００００」、「１０００００００」が表す画素値は、それぞれ、「１」、「２」、「４」、「８」、「１６」、「３２」、「６４」、「１２８」であり、この８パターンのバイナリコードに対応する画素値の間隔は、密のところもあれば、粗のところもある。即ち、画素値が小さい部分では、画素値どうしの間隔は密になり、画素値が大きい部分では、画素値どうしの間隔は粗になる。
【００４７】
このため、間隔が密になっている画素値である、例えば、「１」や、「２」、「４」等については、比較的精度の高い予測値が得られても、その画素値の予測値は、その画素値に近い他の画素値に対する予測誤差を最小にするものとなり、真の画素値に対する予測誤差を最小とするものにならないことが多くなる。その結果、上述したように、画素値を正確に復号することができないことになる。
【００４８】
本発明は、このような状況に鑑みてなされたものであり、復号精度が高いデータの埋め込みを行うことができるようにするものである。
【００４９】
本発明の第１のデータ処理装置は、第１のディジタルデータ内の、所定数ビット数からなるターゲットデータをビットスワップするビットスワップ手段と、ターゲットデータ周辺の周辺データに対応する値からターゲットデータに対応する値を予測する予測値を出力する予測手段と、予測手段により出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソート手段と、ソート手段によりソートされた、ビットスワップされたターゲットデータに応じて、補正コードを出力する補正コード出力手段と、第２のディジタルデータに応じて、ソート手段によりソートされた、ビットスワップされたターゲットデータの内の１つを、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力手段とを備えることを特徴とする。
【００５０】
本発明の第１のデータ処理方法は、第１のディジタルデータ内の、所定数ビット数からなるターゲットデータをビットスワップするビットスワップステップと、ターゲットデータ周辺の周辺データに対応する値からターゲットデータに対応する値を予測する予測値を出力する予測ステップと、予測ステップにより出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータに応じて、補正コードを出力する補正コード出力ステップと、第２のディジタルデータに応じて、ソートステップによりソートされた、ビットスワップされたターゲットデータの内の１つを、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップとを備えることを特徴とする。
【００５１】
本発明の第１の記録媒体は、第１のディジタルデータ内の、所定数ビット数からなるターゲットデータをビットスワップするビットスワップステップと、ターゲットデータ周辺の周辺データに対応する値からターゲットデータに対応する値を予測する予測値を出力する予測ステップと、予測ステップにより出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータに応じて、補正コードを出力する補正コード出力ステップと、第２のディジタルデータに応じて、ソートステップによりソートされた、ビットスワップされたターゲットデータの内の１つを、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップとを含む処理を、コンピュータに実行させるデータ処理プログラムが記録されていることを特徴とする。
【００５２】
本発明の第２のデータ処理装置は、第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードである新コードに、第１のディジタルデータを変換するコード変換手段と、新コードに変換された第１のディジタルデータ内の、所定ビット数からなるターゲットデータをビットスワップするビットスワップ手段と、ターゲットデータ周辺の新コードである周辺データに対応する値からターゲットデータに対応する値を予測する予測値を出力する予測手段と、予測手段により出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソート手段と、第２のディジタルデータに応じて、ソート手段によりソートされた、ビットスワップされたターゲットデータの内の１つを、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力手段とを備えることを特徴とする。
【００５３】
本発明の第２のデータ処理方法は、第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードである新コードに、第１のディジタルデータを変換するコード変換ステップと、新コードに変換された第１のディジタルデータ内の、所定ビット数からなるターゲットデータをビットスワップするビットスワップステップと、ターゲットデータ周辺の新コードである周辺データに対応する値からターゲットデータに対応する値を予測する予測値を出力する予測ステップと、予測ステップにより出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、第２のディジタルデータに応じて、ソートステップによりソートされた、ビットスワップされたターゲットデータの内の１つを、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップとを備えることを特徴とする。
【００５４】
本発明の第２の記録媒体は、第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードである新コードに、第１のディジタルデータを変換するコード変換ステップと、新コードに変換された第１のディジタルデータ内の、所定ビット数からなるターゲットデータをビットスワップするビットスワップステップと、ターゲットデータ周辺の新コードである周辺データに対応する値からターゲットデータに対応する値を予測する予測値を出力する予測ステップと、予測ステップにより出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、第２のディジタルデータに応じて、ソートステップによりソートされた、ビットスワップされたターゲットデータの内の１つを、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力する埋め込みデータ出力ステップとを含む処理を、コンピュータに実行させるデータ処理プログラムが記録されていることを特徴とする。
【００５５】
本発明の第１の復号装置は、埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップ手段と、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測手段と、予測手段により出力される予測値と、ビットスワップ手段によりビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソート手段と、補正コードに応じて、ソート手段によりソートされた、ビットスワップされたターゲットデータのうちの１つのコードを、ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する復号データ出力手段と、ソート手段によりソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータを出力する第２のディジタルデータ出力手段とを備えることを特徴とする。
【００５６】
本発明の第１の復号方法は、埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、予測ステップにより出力される予測値と、ビットスワップステップによりビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、補正コードに応じて、ソートステップによりソートされた、ビットスワップされたターゲットデータのうちの１つのコードを、ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する復号データ出力ステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータを出力する第２のディジタルデータ出力ステップとを備えることを特徴とする。
本発明の第３の記録媒体は、埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、予測ステップにより出力される予測値と、ビットスワップステップによりビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、補正コードに応じて、ソートステップによりソートされた、ビットスワップされたターゲットデータのうちの１つのコードを、ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力する復号データ出力ステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータを出力する第２のディジタルデータ出力ステップとを含む処理を、コンピュータに実行させる復号プログラムを記録していることを特徴とする。
本発明の第２の復号装置は、埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップ手段と、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードを表す新コードであり、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測手段と、予測手段より出力される予測値と、ビットスワップ手段によりビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソート手段と、ソート手段によりソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータを出力する第２のディジタルデータ出力手段と、ソート手段によりソートされた、ビットスワップされたターゲットデータの順位に応じて、ターゲットデータを復号することにより得られる復号データを出力する復号データ出力手段と、復号データ出力手段により出力される新コードである復号データに対応する元のコードを出力するコード変換手段とを備えることを特徴とする。
本発明の第２の復号方法は、埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードを表す新コードであり、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、予測ステップより出力される予測値と、ビットスワップステップによりビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータを出力する第２のディジタルデータ出力ステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータの順位に応じて、ターゲットデータを復号することにより得られる復号データを出力する復号データ出力ステップと、復号データ出力ステップにより出力される新コードである復号データに対応する元のコードを出力するコード変換ステップとを備えることを特徴とする。
本発明の第４の記録媒体は、埋め込みデータ内の、所定ビット数であるターゲットデータをビットスワップするビットスワップステップと、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードを表す新コードであり、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値を予測する予測値を出力する予測ステップと、予測ステップより出力される予測値と、ビットスワップステップによりビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータをソートするソートステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータを出力する第２のディジタルデータ出力ステップと、ソートステップによりソートされた、ビットスワップされたターゲットデータの順位に応じて、ターゲットデータを復号することにより得られる復号データを出力する復号データ出力ステップと、復号データ出力ステップにより出力される新コードである復号データに対応する元のコードを出力するコード変換ステップとを含む処理を、コンピュータに実行させる復号プログラムが記録されていることを特徴とする。
本発明の第１のデータ処理装置およびデータ処理方法、並びに記録媒体においては、第１のディジタルデータ内の、所定数ビット数からなるターゲットデータがビットスワップされ、ターゲットデータ周辺の周辺データに対応する値からターゲットデータに対応する値が予測され、その結果得られる予測値が出力される。そして、出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされ、ソートされた、ビットスワップされたターゲットデータに応じて、補正コードが出力される。また、第２のディジタルデータに応じて、ソートされた、ビットスワップされたターゲットデータの内の１つが、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力される。
本発明の第２のデータ処理装置およびデータ処理方法、並びに記録媒体においては、第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードである新コードに、第１のディジタルデータが変換され、新コードに変換された第１のディジタルデータ内の、所定ビット数からなるターゲットデータがビットスワップされる。そして、ターゲットデータ周辺の新コードである周辺データに対応する値からターゲットデータに対応する値が予測され、その結果得られる予測値が出力される。また、出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされ、第２のディジタルデータに応じて、ソートされた、ビットスワップされたターゲットデータの内の１つが、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力される。
本発明の第１の復号装置および復号方法、並びに第３の記録媒体においては、埋め込みデータ内の、所定ビット数であるターゲットデータがビットスワップされ、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値が予測され、その結果得られる予測値が出力される。出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされ、補正コードに応じて、ソートされた、ビットスワップされたターゲットデータのうちの１つのコードが、ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力される。また、ソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータが出力される。
本発明の第２の復号装置および復号方法、並びに第４の記録媒体においては、埋め込みデータ内の、所定ビット数であるターゲットデータがビットスワップされ、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードを表す新コードであり、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値が予測され、その結果得られる予測値が出力される。出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされる。また、ソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータが出力される。さらに、ソートされた、ビットスワップされたターゲットデータの順位に応じて、ターゲットデータを復号することにより得られる復号データが出力され、出力される新コードである復号データに対応する元のコードが出力される。
【００５７】
【発明の実施の形態】
以下、本発明の一実施の形態について説明するが、その前に、補正コードを用いた完全可逆の埋め込み符号化および復号について説明する。
【００５８】
図８は、補正コードを用いた完全可逆の埋め込み符号化を行う埋め込み符号化装置の一実施の形態の構成例を示している。なお、図中、図１における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図８の埋め込み符号化装置は、予測値取得部２１、補正コード用メモリ２３、圧縮部２４、およびＭＵＸ（マルチプレクサ）２５が新たに設けられているとともに、ビットスワップ埋め込み部３に替えて、ビットスワップ埋め込み部２２が設けられている他は、図１における場合と同様に構成されている。
【００５９】
予測値取得部２１は、画像データ用メモリ１に記憶された画像データに基づいて、注目画素の画素値の予測値を求め、ビットスワップ埋め込み部２２に供給する。
【００６０】
ここで、予測値取得部２１においては、前述の図５で説明した予測値取得部１５における場合と同様に、例えば、画像データ用メモリ１に記憶された注目画素の左や上に隣接する画素の画素値を、そのまま予測値としたり、あるいは、例えば、画像データ用メモリ１に記憶された注目画素に空間的または時間的に近い位置にある画素の画素値の平均値を求め、これを、予測値とするようにすることが可能である。なお、以下では、説明を簡単にするために、注目画素の左隣の画素の画素値を、そのまま、注目画素の予測値とするものとする。また、注目画素の予測値を求めるのに用いる画素は、特に限定されるものではないが、注目画素を復号するときに、既に復号されていなければ、予測値を算出に用いることができないため、符号化時においては、既に符号化された画素の画素値を、注目画素の予測値を算出するのに用いる必要がある。
【００６１】
ビットスワップ埋め込み部２２は、例えば、前述の図１におけるビットスワップ埋め込み部３と同様に、画像データ用メモリ１に記憶された画像データを構成する画素を、ラスタスキャン順で、順次、注目画素とし、その画素値を読み出すとともに、埋め込み対象データ用メモリ２に記憶された埋め込み対象データを読み出す。さらに、ビットスワップ埋め込み部２２は、注目画素の画素値を表すビット列を構成する各ビットを、埋め込み対象データに応じてビットスワップすることにより、注目画素の画素値に埋め込み対象データを埋め込み、その埋め込みの結果得られる画素値（埋め込み後画素値）を、埋め込み後画像データ用メモリ４に供給する。
【００６２】
即ち、ビットスワップ埋め込み部２２は、注目画素の画素値を表すバイナリコードをビットスワップすることにより、そのバイナリコードに対応するビット列から得られる全パターンのビット列としてのバイナリコードを求め、各パターンのバイナリコードを、そのバイナリコードが表す画素値に対する注目画素の予測値の予測誤差が小さい順に並べたときの、埋め込み対象データの値に対応する順番のバイナリコードを、埋め込み後画素値に対応するバイナリコードとして出力する。
【００６３】
さらに、ビットスワップ埋め込み部２２は、ビットスワップの結果得られた各パターンのバイナリコードを、そのバイナリコードが表す画素値に対する注目画素の予測値の予測誤差が小さい順に並べたときに、注目画素の画素値を表すバイナリコードの順位を表す情報を、補正コードとして、補正コード用メモリ２３に供給する。
【００６４】
ここで、補正コードがない場合には、ビットスワップ埋め込み部２２が出力する埋め込み後画素値については、図５乃至図７で説明したように、その埋め込み後画素値を表すバイナリコードをビットスワップすることにより得られるすべてのパターンのバイナリコードのうち、そのバイナリコードが表す値に対する予測値の予測誤差が最小のものが、画素値の復号結果とされるが、この場合は、前述したように、元の画素値に対する予測誤差が最小にならないときに、正確な復号を行うことができない。
【００６５】
一方、補正コードは、埋め込み後画素値を表すバイナリコードをビットスワップすることにより得られるすべてのパターンのバイナリコードを、そのバイナリコードが表す画素値に対する注目画素の予測値の予測誤差が小さい順に並べたときの、注目画素の画素値を表すバイナリコードの順位を表す。従って、補正コードによれば、予測誤差の大小にかかわらず、正確に、元の画素値を復号することができる。このことは、予測誤差が最小の画素値が、正確な復号結果でない場合に、その正確でない復号結果を、正確な復号結果に補正していると見ることもできるから、そのような補正を行うための情報を、「補正コード」と呼んでいる。
【００６６】
補正コード用メモリ２３は、ビットスワップ埋め込み部２２からの注目画素についての補正コードを、注目画素の位置に対応するアドレスに記憶する。
【００６７】
圧縮部２４は、補正コード用メモリ２３に記憶された補正コードを読み出し、例えば、ハフマン符号化等のエントロピー符号化処理等を施すことによって、補正コードを圧縮符号化し、その圧縮符号化結果（以下、適宜、符号化補正コードという）を、ＭＵＸ２５に出力する。
【００６８】
ＭＵＸ２５は、埋め込み後画像データ用メモリ４が出力する埋め込み後画像データと、圧縮部２４が出力する符号化補正コードとを多重化し、その結果得られる多重化データを出力する。この多重化データは、例えば、衛星回線や、ＣＡＴＶ(Cable Television)網、地上波回線、インターネット、公衆網等の伝送媒体を介して伝送される。あるいは、また、多重化データは、光ディスクや、磁気ディスク、相変化ディスク、半導体メモリ等の記録媒体に記録される。
【００６９】
次に、図９のフローチャートを参照して、図８の埋め込み符号化装置の処理（埋め込み符号化処理）について説明する。
【００７０】
埋め込み符号化装置に対して、例えば、１フレーム（またはフィールド）の画像データと、その１フレームの画像データに埋め込む埋め込み対象データが供給されると、ステップＳ２１において、画像データ用メモリ１は、その画像データを記憶し、埋め込み対象データ用メモリ２は、埋め込み対象データを記憶する。
【００７１】
そして、ビットスワップ埋め込み部２２は、画像データ用メモリ１に記憶された画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素としていないものを注目画素とし、予測値取得部２１は、ステップＳ２２において、注目画素の予測値を取得し、ビットスワップ埋め込み部２２に供給する。即ち、予測値取得部２１は、例えば、画像データ用メモリ１から、注目画素の左隣の画素値を読み出し、その画素値を、注目画素の予測値として、ビットスワップ埋め込み部２２に供給する。
【００７２】
ここで、補正コードを用いない場合には、前述したように、埋め込み後画像データをラスタスキャン順に復号していったときに、注目画素の左隣の画素の画素値を、注目画素の予測値として、そのまま用いると、埋め込み後画像データの最も左の画素については、予測値となる画素値が存在しないことになり、復号を行うことができないことから、埋め込み符号化時においては、画像データの最も左の画素には、埋め込み対象データを埋め込まないようにする必要があるが、補正コードを用いる場合には、予測値がどのような値であっても、補正コードにより、画素値の復号を行うことができる。従って、補正コードを用いる場合には、最も左の画素については、その左隣に、所定の画素値（例えば０など）の画素が存在するものとして、埋め込み対象データを埋め込むようにすることが可能である。
【００７３】
ビットスワップ埋め込み部２２は、予測値取得部２１から注目画素の予測値を受信すると、ステップＳ２３において、注目画素の画素値を、画像データ用メモリ１から読み出すとともに、その画素値に埋め込み可能なビット数分の埋め込み対象データを、埋め込み対象データ用メモリ２から読み出す。さらに、ステップＳ２３では、ビットスワップ埋め込み部２２は、注目画素の画素値を表すビット列を構成する各ビットを、予測値取得部２１からの注目画素の予測値、および埋め込み対象データ用メモリ２から読み出した埋め込み対象データに応じてビットスワップすることにより、注目画素の画素値に埋め込み対象データを埋め込み、その埋め込みの結果得られる埋め込み後画素値を、埋め込み後画像データ用メモリ４に供給して記憶させる。
【００７４】
そして、ステップＳ２４に進み、ビットスワップ埋め込み部２２は、注目画素についての補正コードを求め、補正コード用メモリ２３に供給して記憶させ、ステップＳ２５に進む。
【００７５】
ステップＳ２５では、ビットスワップ埋め込み部２２は、画像データ用メモリ１に記憶された画像データを構成するすべての画素を注目画素として処理を行ったかどうかを判定し、まだ、すべての画素を注目画素として処理を行っていないと判定した場合、ステップＳ２２に戻り、以下、同様の処理を繰り返す。
【００７６】
また、ステップＳ２５において、画像データ用メモリ１に記憶された画像データを構成するすべての画素を注目画素として処理を行ったと判定された場合、即ち、埋め込み後画像データ用メモリ４に、１フレーム分の埋め込み後画素値で構成される画像データ（埋め込み後画像データ）が記憶されるとともに、補正コード用メモリ２３にも、１フレーム分の画素についての補正コードが記憶された場合、ステップＳ２６に進み、圧縮部２４は、補正コード用メモリ２３に記憶された１フレーム分の補正コードをエントロピー符号化し、その結果得られる符号化補正コードを、ＭＵＸ２５に出力する。
【００７７】
ＭＵＸ２５は、ステップＳ２７において、埋め込み後画像データ用メモリ４に記憶された１フレームの埋め込み後画像データを読み出す。さらに、ＭＵＸ２５は、ステップＳ２７において、その埋め込み後画像データと、圧縮部２４からの符号化補正コードとを多重化し、その結果得られる多重化データを出力して、処理を終了する。
【００７８】
なお、図９のフローチャートの処理は、埋め込み符号化装置に、１フレームの画像データが供給されるごとに、その１フレームの画像データについて行われる。
【００７９】
以上のような埋め込み符号化処理によれば、例えば、図１０に示すように、埋め込み対象データが画素値に埋め込まれる。
【００８０】
即ち、図１０は、注目画素の画素値が１６であり、その注目画素に、値が３の埋め込み対象データが埋め込まれる場合を示している。また、図１０では、予測値取得部２１において、注目画素の予測値として、「１１」が求められている。
【００８１】
この場合、ビットスワップ埋め込み部２２は、画素値「１６」に対応するバイナリコード「０００１００００」を構成するビット列をビットスワップすることにより、そのバイナリコードに対応するビット列から得られる全パターンのビット列としてのバイナリコードを求める。従って、いまの場合、８通りのバイナリコード「０００００００１」、「００００００１０」、「０００００１００」、「００００１０００」、「０００１００００」、「００１０００００」、「０１００００００」、「１０００００００」が求められる。
【００８２】
さらに、ビットスワップ埋め込み部２２は、ビットスワップの結果得られるバイナリコードが表す画素値に対する、注目画素の予測値の予測誤差を求める。いまの場合、８通りのバイナリコード「０００００００１」、「００００００１０」、「０００００１００」、「００００１０００」、「０００１００００」、「００１０００００」、「０１００００００」、「１０００００００」が得られるが、これらのバイナリコードが表す画素値は、それぞれ「１」、「２」、「４」、「８」、「１６」、「３２」、「６４」、「１２８」であるから、これらの画素値に対する予測値「１１」の予測誤差（予測誤差の大きさ）は、それぞれ、１０、９、７、３、５、２１、５３、１１７となる。
【００８３】
ビットスワップ埋め込み部２２は、予測誤差を求めると、ビットスワップの結果得られたバイナリコードを、各バイナリコードについて得られた予測誤差が小さい順に並べたときの、埋め込み対象データの値に対応する順番のバイナリコードを、埋め込み後画素値に対応するバイナリコードとして出力する。
【００８４】
即ち、注目画素の画素値が「１６」で、その予測値が「１１」である場合には、ビットスワップの結果得られたバイナリコードを、予測誤差が小さい順に並べると、図１０に示すようになる。
【００８５】
さらに、図１０では、第ｉ＋１位に位置するバイナリコードに、埋め込み対象データ＃ｉが対応付けられており、従って、埋め込み対象データが「３」である場合には、第４（＝３＋１）位に位置するバイナリコード「００００００１０」が、埋め込み後画素値に対応するバイナリコードとして出力される。この場合、埋め込み後画素値は、「００００００１０」に対応する「２」となる。
【００８６】
なお、本実施の形態では、ビットスワップの結果得られたバイナリコードを、各バイナリコードについて得られた予測誤差が小さい順に並べたときに、第ｉ＋１位に位置するバイナリコードに、埋め込み対象データ＃ｉを対応付けるようにしているが、どの順位のバイナリコードに、値がいくつの埋め込み対象データを対応付けるかは、特に限定されるものではない。但し、どの順位のバイナリコードに、値がいくつの埋め込み対象データを対応付けるかは、埋め込み符号化装置と復号装置とで統一しておく必要がある。
【００８７】
また、あるバイナリコードと、他のバイナリコードについての予測誤差が同一の値になることがあり得るが、この場合、その２つのバイナリコードを、どのような順位付けにするかは、あらかじめ決めておくようにすれば良い。即ち、予測誤差が同一の２つのバイナリコードについては、例えば、対応する画素値が小さい方のバイナリコードを高い順位にするように決めておくことができる。
【００８８】
ビットスワップ埋め込み部２２は、埋め込み後画素値を求めた後（求める前でも、同時でも良い）、予測誤差が小さい順に並べたバイナリコードのうち、注目画素の画素値を表すバイナリコードの順位を表す情報を、補正コードとして出力する。
【００８９】
即ち、図１０では、第ｉ位に位置するバイナリコードに、補正コード＃ｉ−１が対応付けられており、従って、注目画素の画素値が「１６」である場合には、その「１６」に対応するバイナリコード「０００１００００」は第２位であるから、補正コードとしては、「１」（＝２−１）が出力される。
【００９０】
ここで、予測誤差が小さい順に並べたバイナリコードのうち、予測誤差が最も小さいバイナリコード（第１位のバイナリコード）を、基準コードというものとすると、補正コードは、基準コードに対する、注目画素の画素値が表すバイナリコードの相対位置を表す情報であるということができる。
【００９１】
なお、本実施の形態では、ビットスワップの結果得られたバイナリコードを、各バイナリコードについて得られた予測誤差が小さい順に並べたときに、第ｉ位に位置するバイナリコードに、補正コード＃ｉ−１を対応付けるようにしているが、どの順位のバイナリコードに、値がいくつの補正コードを対応付けるかは、特に限定されるものではない。但し、バイナリコードと埋め込み対象データとの対応付けと同様に、どの順位のバイナリコードに、値がいくつの補正コードを対応付けるかは、埋め込み符号化装置と復号装置とで統一しておく必要がある。
【００９２】
次に、図１１は、図８の埋め込み符号化装置が出力する多重化データから、元の画素値と埋め込み対象データを復号する復号装置の一実施の形態の構成例を示している。なお、図中、図５における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図１１の復号装置は、ＤＥＭＵＸ（デマルチプレクサ）３１、伸張部３２、および補正コード用メモリ３３が新たに設けられているとともに、ビットスワップ戻し部１２に替えて、ビットスワップ戻し部３４が設けられている他は、図５における場合と同様に構成されている。
【００９３】
ＤＥＭＵＸ３１には、図８の埋め込み符号化装置が出力する多重化データが、所定の伝送媒体または記録媒体を介して供給されるようになっており、ＤＥＭＵＸ３１は、多重化データを、埋め込み後画像データと符号化補正コードに分離する。埋め込み後画像データは、埋め込み後画像データ用メモリ１１に供給され、符号化補正コード３２は、伸張部３２に供給される。
【００９４】
伸張部３２は、ＤＥＭＵＸ３１からの符号化補正コードをエントロピー復号し、補正コードとして、補正コード用メモリ３３に供給する。補正コード用メモリ３３は、伸張部３２からの補正コードを一時記憶する。
【００９５】
ビットスワップ戻し部３４は、図５のビットスワップ戻し部１２における場合と同様に、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成する画素を、例えば、ラスタスキャン順に、順次、注目画素とし、その注目画素の埋め込み後画素値を、埋め込み後画像データ用メモリ１１から読み出すとともに、注目画素の画素値の予測値を、予測値取得部１５から受信する。さらに、ビットスワップ戻し部３４は、注目画素の埋め込み後画素値を表すビット列を構成する各ビットを、注目画素の予測値に応じてビットスワップし、そのビットスワップ結果に基づいて、注目画素に埋め込まれていた埋め込み対象データを復号する。また、ビットスワップ戻し部３４は、ビットスワップ結果と、補正コード用メモリ３３に記憶された注目画素についての補正コードに基づいて、注目画素の画素値を復号する。復号された注目画素の画素値は、ビットスワップ戻し部３４から画像データ用メモリ１３に供給され、埋め込み対象データは、ビットスワップ戻し部３４から埋め込み対象データ用メモリ１４に供給される。
【００９６】
次に、図１２のフローチャートを参照して、図１１の復号装置の処理（復号処理）について説明する。
【００９７】
復号装置に対して、例えば、１フレーム（またはフィールド）分の多重化データが供給されると、その多重化データは、ＤＥＭＵＸ３１において、埋め込み後画像データと符号化補正コードとに分離される。そして、ステップＳ３１において、埋め込み後画像データは、埋め込み後画像データ用メモリ１１に供給されて記憶される。さらに、ステップＳ３１では、伸張部３２において、符号化補正コードがエントロピー復号され、補正コード用メモリ３３に供給されて記憶される。
【００９８】
その後、ビットスワップ戻し部３４は、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素としていないものを注目画素とし、予測値取得部１５は、ステップＳ３２において、画像データ用メモリ１３に記憶された、既に復号された画素値に基づいて、注目画素の予測値を求め、ビットスワップ戻し部３４に供給する。即ち、予測値取得部１５は、図８の予測値取得部２１と同様に、注目画素の左隣の画素の画素値を、注目画素の予測値とし、ビットスワップ戻し部３４に供給する。
【００９９】
ビットスワップ戻し部３４は、注目画素の埋め込み後画素値を、埋め込み後画像データ用メモリ１１から読み出すとともに、注目画素についての補正コードを、補正コード用メモリ３３から読み出す。さらに、ビットスワップ戻し部３４は、注目画素の画素値の予測値を、予測値取得部１５から受信し、ステップＳ３３において、注目画素の埋め込み後画素値を表すビット列を構成する各ビットを、注目画素の予測値に応じてビットスワップし、そのビットスワップ結果と補正コードから、注目画素の画素値、およびそこに埋め込まれていた埋め込み対象データを復号して、ステップＳ３４に進む。
【０１００】
ステップＳ３４では、ビットスワップ戻し部３４は、注目画素の画素値の復号値を、画像データ用メモリ１３に供給して記憶させるとともに、埋め込み対象データの復号値を、埋め込み対象データ用メモリ１４に供給して記憶させる。
【０１０１】
以下、ステップＳ３５，Ｓ３６において、図６のステップＳ１５，Ｓ１６における場合とそれぞれ同様の処理が行われ、処理を終了する。
【０１０２】
なお、図１２のフローチャートの処理は、復号装置に、１フレーム分の多重化データが供給されるごとに、その１フレームの多重化データについて行われる。
【０１０３】
以上のような復号処理によれば、例えば、図１３に示すように、埋め込み後画素値が、画素値と埋め込み対象データに復号される。
【０１０４】
即ち、図１３は、図１０で説明したように、画素値「１６」に、値が３の埋め込み対象データを埋め込むことによって得られた埋め込み後画素値「２」を復号する場合を示している。なお、補正コードは、図１０で説明したように、「１」が得られているものとする。
【０１０５】
埋め込み後画素値「２」を表すバイナリコードは、「００００００１０」であるが、このバイナリコードは、元の画素値を表すバイナリコードをビットスワップすることにより得られたものであるから、元の画素値を表すバイナリコードは、埋め込み後画素値「２」を表すバイナリコード「００００００１０」をビットスワップすることにより得られる全パターンのビット列の中に存在する。従って、埋め込み後画素値「２」を表すバイナリコード「１０００００００」をビットスワップすることにより得られる全パターンのビット列の中から、元の画素値を表すバイナリコードを見つけ出すことが、元の画素値を復号することになる。
【０１０６】
また、図８の埋め込み符号化装置では、元の画素値は、その画素値に対応するバイナリコードのビットスワップの結果得られるバイナリコードを、予測値の予測誤差が小さい順に並べたときの、埋め込み対象データの値に対応する順位に位置するバイナリコードに対応する値の埋め込み後画素値に埋め込み符号化されるから、埋め込み後画素値を表すバイナリコードのビットスワップの結果得られるバイナリコードを、予測誤差が小さい順に並べたときの、埋め込み後画素値を表すバイナリコードの順位が分かれば、埋め込み後画素値に埋め込まれている埋め込み対象データを復号することができる。
【０１０７】
そこで、ビットスワップ戻し部３４は、まず、画素値を復号するために、埋め込み後画素値「２」を表すバイナリコード「１０００００００」をビットスワップすることにより、そのバイナリコードから得られる全パターンのビット列を求める。従って、いまの場合、８通りのバイナリコード「０００００００１」、「００００００１０」、「０００００１００」、「００００１０００」、「０００１００００」、「００１０００００」、「０１００００００」、「１０００００００」が求められる。
【０１０８】
さらに、ビットスワップ戻し部３４は、ビットスワップの結果得られるバイナリコードが表す画素値に対する、注目画素の予測値の予測誤差を求める。いまの場合、８通りのバイナリコード「０００００００１」、「００００００１０」、「０００００１００」、「００００１０００」、「０００１００００」、「００１０００００」、「０１００００００」、「１０００００００」が求められるが、これらのバイナリコードが表す画素値は、それぞれ「１」、「２」、「４」、「８」、「１６」、「３２」、「６４」、「１２８」であるから、これらの画素値に対する予測値「１１」の予測誤差（予測誤差の大きさ）は、それぞれ、１０、９、７、３、５、２１、５３、１１７となる。
【０１０９】
ビットスワップ戻し部３４は、予測誤差を求めると、ビットスワップの結果得られたバイナリコードを、各バイナリコードについて得られた予測誤差が小さい順に並べたときの、補正コードに対応する順番のバイナリコードを、元の画素値に対応するバイナリコードとして出力する。
【０１１０】
即ち、注目画素の埋め込み後画素値が「２」で、その予測値が「１１」である場合には、ビットスワップの結果得られたバイナリコードを、上述の予測誤差が小さい順に並べると、図１３に示すようになる。
【０１１１】
さらに、図１３では、図１０における場合と同様に、第ｉ位に位置するバイナリコードに、補正コード＃ｉ−１が対応付けられており、従って、補正コードが「１」である場合には、第２（＝１＋１）位に位置するバイナリコード「０００１００００」が表す値「１６」が元の画素値の復号結果となる。
【０１１２】
また、ビットスワップ戻し部３４は、ビットスワップの結果得られたバイナリコードを、各バイナリコードについて得られた予測誤差が小さい順に並べたときの、埋め込み後画素値に対応するバイナリコードの順位に対応する値を、埋め込み対象データの復号結果として出力する。
【０１１３】
即ち、図１３では、図１０における場合と同様に、第ｉ＋１位に位置するバイナリコードに、埋め込み対象データ＃ｉが対応付けられており、従って、埋め込み後画素値が「２」である場合には、対応するバイナリコード「００００００１０」は、第４位であるから、埋め込み対象データの復号結果は、「３」（＝４−１）となる。
【０１１４】
以上のようにして、埋め込み後画素値「２」は、元の画素値「１６」とそこに埋め込まれた埋め込み対象データ「３」に、正確に復号される。
【０１１５】
以上のように、補正コードを用いる場合には、画素値と埋め込み対象データとを、必ず正確に復号すること、即ち、完全可逆の埋め込み符号化および復号を行うことができる。
【０１１６】
ところで、補正コードを用いる場合においては、完全可逆の処理を実現することができるが、埋め込み符号化結果のデータ量は、補正コードを用いない場合に比較して、符号化補正コードのデータ量だけ増加する。従って、圧縮率の観点からは、符号化補正コードのデータ量をできるだけ少なくすることが要求される。
【０１１７】
そして、補正コードをエントロピー符号化等して、符号化補正コードとする場合、その符号化補正コードのデータ量を少なくするには、補正コードを、ある値に集中させることが必要となる。
【０１１８】
しかしながら、前述したように、画素値に割り当てられる従来のバイナリコード（以下、適宜、従来コードという）に対応する画素値の間隔は、密のところもあれば、粗のところもあるため、特に、間隔が密になっている画素値については、予測値として得られる値の変動（予測値の精度）によって、補正コードがばらつくことになる。
【０１１９】
即ち、図１４（Ａ）は、８ビットの従来コードのうち、「１」が１ビットだけのもののビットスワップ結果の全８パターンと、対応する画素値とを示している。
【０１２０】
例えば、いま、注目画素の画素値が、従来コード「０００１００００」に対応する値「１６」であるとし、その注目画素の予測値として、値「１７」が得られた場合に、従来コード「０００１００００」のビットスワップ結果としての８パターンの従来コードを、各従来コードに対応する画素値に対する、予測値「１７」の予測誤差の小さい順に並べると、図１４（Ｂ）に示すようになる。この場合、注目画素の画素値「１６」に対する予測値「１７」の予測誤差が「１」（＝｜１７−１６｜）で、最も小さいから、即ち、注目画素の画素値「１６」に対応する従来コード「０００１００００」の順位は、第１位であるから、補正コードは「０」となる。
【０１２１】
一方、注目画素の予測値として、例えば、値「８」が得られた場合に、従来コード「０００１００００」のビットスワップ結果としての８パターンの従来コードを、各従来コードに対応する画素値に対する、予測値「８」の予測誤差の小さい順に並べると、図１４（Ｃ）に示すようになる。この場合、注目画素の画素値「１６」に対する予測値「８」の予測誤差は「８」（＝｜８−１６｜）で、５番目に小さいから、即ち、注目画素の画素値「１６」に対応する従来コード「０００１００００」の順位は、第５位であるから、補正コードは「４」となる。
【０１２２】
このように、予測値によって、注目画素の画素値「１６」を表す従来コード「０００１００００」の順位が第１位から第４位に大きく変化するのは、注目画素の画素値「１６」以下の画素値「１」、「２」、「４」、「８」の間隔が、密であることに起因する。即ち、注目画素の画素値に対応する従来コードをビットスワップして得られるビットスワップ結果に対応する画素値の間隔が密であると、予測値が少し変化するだけで、ビットスワップ結果としての従来コードが表す画素値に対する予測誤差を小さくする従来コードの順位が大きく変動する。補正コードは、この順位に対応しているから、順位が大きく変動すれば、補正コードも大きく変動することとなる。
【０１２３】
従って、補正コードの変動を小さくして、ある値に集中させるには、注目画素の画素値に対応するビット列をビットスワップすることにより得られるビット列、即ち、０または１の数が同一のビット列をビットスワップすることにより得られるビット列に対して、できるだけ間隔が粗の画素値（間隔が広い）を割り当てる必要がある。
【０１２４】
一方、画素値として取り得る値の個数は、画素に割り当てられるビット数によって決まる有限の値となるから、０または１の数がある値のビット列をビットスワップすることにより得られるビット列に対して、非常に広い間隔の画素値を割り当てたのでは、０または１の数が他の値のビット列をビットスワップすることにより得られるビット列に対して割り当てることのできる画素値の間隔が密になる（狭くなる）。
【０１２５】
従って、０または１の数が同一のビット列に対して、各ビット列に対応する値どうしの間隔が、均一で、かつ、なるべく粗になるように、画素値を割り当てるようにすれば、補正コードの変動を小さくすることができる。
【０１２６】
そこで、８ビットのビット列に対して、例えば、図１５および図１６に示すように、画素値を割り当てることとする。
【０１２７】
なお、図１５および図１６において、codeの列は、８ビットのビット列を表し、oldの列は、codeの列におけるビット列を従来コードとして見た場合の、その従来コードに対応する画素値を表す。また、newの列は、codeの列におけるビット列を、画素値に割り当てる新たなコード（以下、適宜、新コードという）として見た場合の、その新コードに対応する画素値を表す。
【０１２８】
上述したように、新コードにおいては、０または１の数が同一の新コードに対して、各新コードに対応する画素値どうしの間隔が、均一で、かつ、なるべく粗になるように、画素値が割り当てられており、その結果、予測値として得られる値の変動（予測値の精度）に起因する補正コードのばらつきを低減することができる。
【０１２９】
即ち、図１７は、８ビットの新コードのうち、「１」が６ビットだけのもののビットスワップ結果の全２８パターンと、対応する画素値とを示している。
【０１３０】
例えば、いま、注目画素の画素値が、図１４で説明した場合の同一の「１６」であるとすると、画素値「１６」に対応する新コード（図１５および図１６において、newの列が「１６」になっているcodeの列のビット列）は、「０１０１１１１１」であり、この新コードをビットスワップして得られるビット列としての新コードは、図１７に示す２８パターン存在する。なお、図１７においては、新コードを、その新コードに対応する（割り当てられている）画素値とともに示してある。
【０１３１】
この場合、注目画素の予測値として、図１４（Ｂ）における場合と同様に、値「１７」が得られたとすると、新コード「０１０１１１１１」のビットスワップ結果としての２８パターンの新コードを、各新コードに対応する画素値に対する、予測値「１７」の予測誤差の小さい順に並べると、図１８に示すようになる。
【０１３２】
なお、予測誤差が同一の新コードについては、割り当てられている画素値が小さいものの方の順位を上位にしてある。
【０１３３】
図１８では、注目画素の画素値「１６」に対する予測値「１７」の予測誤差が「１」（＝｜１７−１６｜）で、最も小さいから、即ち、注目画素の画素値「１６」に対応する新コード「０００１００００」の順位は、第１位であるから、補正コードは「０」となる。
【０１３４】
一方、注目画素の予測値として、例えば、図１４（Ｃ）における場合と同様に、値「８」が得られたとすると、新コード「０１０１１１１１」のビットスワップ結果としての２８パターンの新コードを、各新コードに対応する画素値に対する、予測値「８」の予測誤差の小さい順に並べると、図１９に示すようになる。この場合、注目画素の画素値「１６」に対する予測値「８」の予測誤差は「８」（＝｜８−１６｜）で、２番目に小さいから、即ち、注目画素の画素値「１６」に対応する新コード「０１０１１１１１」の順位は、第２位であるから、補正コードは「１」となる。
【０１３５】
以上のように、新コードにおいては、０または１の数が同一の新コードに対して、各新コードに対応する画素値どうしの間隔が、均一で、かつ、なるべく粗になるように、画素値が割り当てられているため、予測値として得られる値が変動しても、予測誤差を小さくする新コードの順位の変動を小さく抑えることができ、その結果、補正コードの変動も小さく抑えることができる。従って、新コードを採用することにより、補正コードは、ある値付近、即ち、上述のように、予測誤差を小さくする新コードの順位にしたがって、０からの整数値の補正コードを割り当てる場合には、０付近に集中する。
【０１３６】
そして、このように、０付近に集中する補正コードをエントロピー符号化する場合には、値が大きくばらつく補正コードをエントロピー符号化する場合に比較して、圧縮率を向上させることができる。
【０１３７】
そこで、図２０は、以上のような新コードを利用して、埋め込み符号化処理を行う埋め込み符号化装置の一実施の形態の構成例を示している。なお、図中、図８における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図２０の埋め込み符号化装置は、コード変換部４１が新たに設けられているとともに、ビットスワップ埋め込み部２２に替えて、ビットスワップ埋め込み部４２が設けられている他は、図８における場合と同様に構成されている。
【０１３８】
コード変換部４１には、埋め込み符号化装置に入力される画像データが供給されるようになっており、コード変換部４１は、その画像データを構成する画素値を表すビット列を、従来コードから新コードに変換し、画像データ用メモリ１に供給する。
【０１３９】
ビットスワップ埋め込み部４２は、新コードで表される画素値を対象として、図８のビットスワップ埋め込み部２２における場合と同様の処理を行うことで、埋め込み後画素値と補正コードを求める。
【０１４０】
即ち、図２１は、図２０のビットスワップ埋め込み部４２の構成例を示している。
【０１４１】
図２０の予測値取得部２１が出力する注目画素の予測値は、予測誤差計算部５３に、画像データ用メモリ１が出力する注目画素の画素値は、ビットスワップコード生成部５１に、埋め込み対象データ用メモリ２が出力する埋め込み対象データは、ビットスワップコード決定部５５に、それぞれ供給されるようになっている。
【０１４２】
ビットスワップコード生成部５１は、そこに供給される注目画素の画素値を表す新コードをビットスワップすることにより、全パターンのビットスワップ結果を求め、各ビットスワップ結果が表す画素値（以下、適宜、ビットスワップ値という）を予測誤差計算部５３に供給する。さらに、ビットスワップコード生成部５１は、ビットスワップの結果得られた全パターンの新コードを、ビットスワップコード用メモリ５２に供給する。
【０１４３】
ビットスワップコード用メモリ５２は、ビットスワップコード生成部５１から供給されるビットスワップ結果としての新コードを一時記憶する。予測誤差計算部５３は、注目画素の予測値の、ビットスワップコード生成部５１からのビットスワップ値に対する予測誤差を計算し、予測誤差用メモリ５４に供給する。予測誤差用メモリ５４は、予測誤差計算部５３から供給される、各ビットスワップ結果に対応する新コードについての予測誤差を一時記憶する。
【０１４４】
ビットスワップコード決定部５５は、予測誤差用メモリ５４に記憶された予測誤差を読み出し、小さい順にソートする。さらに、ビットスワップコード決定部５５は、予測誤差のソート結果における、注目画素の画素値を表す新コードの順位を検出し、その順位に対応する値を、補正コードとして出力する。
【０１４５】
また、ビットスワップコード決定部５５は、予測誤差のソート結果における、埋め込み対象データの値に対応する順位を検出し、ビットスワップコード用メモリ７２を参照することで、その順位の新コードによって表される画素値を求め、埋め込み後画素値として出力する。
【０１４６】
次に、図２２のフローチャートを参照して、図２０の埋め込み符号化装置の処理（埋め込み符号化処理）について説明する。
【０１４７】
埋め込み符号化装置に対して、例えば、１フレーム（またはフィールド）の画像データと、その１フレームの画像データに埋め込む埋め込み対象データが供給されると、ステップＳ４１において、コード変換部４１は、その画像データを構成する画素値を表すビット列を、従来コードから新コードに変換し、その新コードで表される画素値を、画像データ用メモリ１に供給する。
【０１４８】
画像データ用メモリ１は、ステップＳ４２において、コード変換部４１から供給される画素値で構成される画像データを記憶する。さらに、ステップＳ４２では、埋め込み対象データ用メモリ２が、埋め込み対象データを記憶する。
【０１４９】
そして、ビットスワップ埋め込み部４２は、画像データ用メモリ１に記憶された画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素としていないものを注目画素とし、予測値取得部２１は、ステップＳ４３において、注目画素の予測値を取得して、ビットスワップ埋め込み部４２に供給する。即ち、予測値取得部２１は、例えば、画像データ用メモリ１から、注目画素の左隣の画素値を読み出し、その画素値を、注目画素の予測値として、ビットスワップ埋め込み部４２に供給する。
【０１５０】
ビットスワップ埋め込み部４２は、ステップＳ４４において、予測値取得部２１から注目画素の予測値を受信し、さらに、注目画素の画素値を、画像データ用メモリ１から読み出すとともに、その画素値に埋め込み可能なビット数分の埋め込み対象データを、埋め込み対象データ用メモリ２から読み出す。そして、ビットスワップ埋め込み部４２は、注目画素の予測値と埋め込み対象データに基づいて、注目画素の画素値を表す新コードをビットスワップすることにより、注目画素の画素値に埋め込み対象データを埋め込んだ埋め込み後画素値と、補正コードを求めるビットスワップ埋め込み処理を行う。
【０１５１】
即ち、ステップＳ４４では、例えば、図２３のフローチャートに示すように、ビットスワップ埋め込み部４２（図２１）は、ステップＳ５１において、注目画素の画素値、その予測値、注目画素に埋め込む埋め込み対象データを取得する。そして、注目画素の画素値は、ビットスワップコード生成部５１に、注目画素の予測値は、予測誤差計算部５３に、埋め込み対象データは、ビットスワップコード決定部５５に、それぞれ供給される。
【０１５２】
その後、ステップＳ５２に進み、ビットスワップコード生成部５１は、注目画素の画素値を表す新コードをビットスワップすることにより、全パターンのビットスワップ結果を求め、ビットスワップコード用メモリ５２に供給して記憶させる。また、ステップＳ５２では、ビットスワップコード生成部５１は、各ビットスワップ結果が表す画素値であるビットスワップ値を、予測誤差計算部５３に供給する。さらに、ステップＳ５２では、予測誤差計算部５３が、注目画素の予測値の、ビットスワップコード生成部５１からのビットスワップ値に対する予測誤差を計算し、予測誤差用メモリ５４に供給して記憶させる。
【０１５３】
そして、ステップＳ５３に進み、ビットスワップコード決定部５５は、予測誤差用メモリ５４に記憶された予測誤差を読み出し、小さい順にソートする。さらに、ビットスワップコード決定部５５は、予測誤差のソート結果における、注目画素の画素値を表す新コードの順位を検出し、その順位に対応する値を、補正コードとして求める。
【０１５４】
その後、ビットスワップコード決定部５５は、ステップＳ５４において、予測誤差のソート結果における、埋め込み対象データの値に対応する順位（予測誤差が最小のビットスワップ結果の順位を基準として、埋め込み対象データが表す順位）を検出し、その順位の新コードを、ビットスワップコード用メモリ７２から読み出す。さらに、ビットスワップコード決定部５５は、その新コードによって表される画素値を、埋め込み後画素値として求める。
【０１５５】
ビットスワップコード決定部５５は、以上のようにして、埋め込み後画素値と補正コードを求めると、ステップＳ５５において、その埋め込み後画素値と補正コードを、図２０の埋め込み後画像データ用メモリ４と補正コード用メモリ２３にそれぞれ供給して記憶させ、リターンする。
【０１５６】
図２２に戻り、ステップＳ４４の処理後は、ステップＳ４５に進み、以下、ステップＳ４５乃至Ｓ４７において、図９のステップＳ２５乃至Ｓ２７における場合とそれぞれ同様の処理が行われ、処理を終了する。
【０１５７】
従って、ステップＳ４６では、圧縮部２４において、補正コードがエントロピー符号化され、符号化補正コードとされるが、上述したように、新コードを採用した場合には、補正コードは０付近に集中するため、その圧縮率は高いものとなる。
【０１５８】
なお、図２２のフローチャートの処理は、埋め込み符号化装置に、１フレームの画像データが供給されるごとに、その１フレームの画像データについて行われる。
【０１５９】
次に、図２４は、図２０の埋め込み符号化装置が出力する多重化データから、元の画素値と埋め込み対象データを復号する復号装置の一実施の形態の構成例を示している。なお、図中、図１１における場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図２４の復号装置は、ビットスワップ戻し部３４に替えて、ビットスワップ戻し部６１が設けられているとともに、コード変換部６２が新たに設けられている他は、図１１における場合と同様に構成されている。
【０１６０】
ビットスワップ戻し部６１は、注目画素の埋め込み後画素値、およびその予測値に基づいて、埋め込み後画素値に埋め込まれていた埋め込み対象データを復号するとともに、さらに、補正コードにも基づいて、埋め込み後画素値を、新コードが割り当てられている画素値に復号する。
【０１６１】
コード変換部６２は、画像データ用メモリ１３から、復号された画素値を読み出し、その画素値を表すビット列を、新コードから従来コードに変換して出力する。
【０１６２】
次に、図２５は、図２４のビットスワップ戻し部６１の構成例を示している。
【０１６３】
図２４の予測値計算部１５が出力する注目画素の予測値は、予測誤差計算部７３に、埋め込み後画像データ用メモリ１１が出力する注目画素の埋め込み後画素値は、ビットスワップコード生成部７１に、補正コード用メモリ３３が出力する注目画素についての補正コードは、ビットスワップコード決定部７５に、それぞれ供給されるようになっている。
【０１６４】
ビットスワップコード生成部７１は、そこに供給される注目画素の埋め込み後画素値を表す新コードをビットスワップすることにより、全パターンのビットスワップ結果を求め、各ビットスワップ結果が表す画素値であるビットスワップ値を、予測誤差計算部７３に供給する。さらに、ビットスワップコード生成部７１は、ビットスワップの結果得られた全パターンの新コードを、ビットスワップコード用メモリ７２に供給する。
【０１６５】
ビットスワップコード用メモリ７２は、ビットスワップコード生成部７１から供給されるビットスワップ結果としての新コードを一時記憶する。予測誤差計算部７３は、注目画素の予測値の、ビットスワップコード生成部７１からのビットスワップ値に対する予測誤差を計算し、予測誤差用メモリ７４に供給する。予測誤差用メモリ７４は、予測誤差計算部７３から供給される、各ビットスワップ結果に対応する新コードについての予測誤差を一時記憶する。
【０１６６】
ビットスワップコード決定部７５は、予測誤差用メモリ７４に記憶された予測誤差を読み出し、小さい順にソートする。さらに、ビットスワップコード決定部７５は、予測誤差のソート結果における、補正コードに対応する順位の新コードの順位を、ビットスワップコード用メモリ７２を参照することで検出し、その新コードが表す画素値を、注目画素の復号結果として出力する。
【０１６７】
また、ビットスワップコード決定部７５は、予測誤差のソート結果における、注目画素の埋め込み画素値に対応する新コードの順位を検出し、その順位に対応する値を、その埋め込み画素値に埋め込まれていた埋め込み対象データの復号結果として出力する。
【０１６８】
次に、図２６のフローチャートを参照して、図２４の復号装置の処理（復号処理）について説明する。
【０１６９】
復号装置に対して、例えば、１フレーム（またはフィールド）分の多重化データが供給されると、その多重化データは、ＤＥＭＵＸ３１において、埋め込み後画像データと符号化補正コードとに分離される。そして、ステップＳ６１において、埋め込み後画像データは、埋め込み後画像データ用メモリ１１に供給されて記憶される。さらに、ステップＳ６１では、伸張部３２において、符号化補正コードがエントロピー復号され、補正コード用メモリ３３に供給されて記憶される。
【０１７０】
その後、ビットスワップ戻し部６１は、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成する画素のうち、ラスタスキャン順で、まだ注目画素としていないものを注目画素とし、予測値取得部１５は、ステップＳ６２において、画像データ用メモリ１３に記憶された、既に復号された画素値のうち、注目画素の左隣の画素の画素値を読み出し、注目画素の予測値として、ビットスワップ戻し部６１に供給する。
【０１７１】
ビットスワップ戻し部６１は、ステップＳ６３において、予測値取得部１５からの注目画素の予測値を受信し、さらに、注目画素の埋め込み後画素値を、埋め込み後画像データ用メモリ１１から読み出すとともに、注目画素についての補正コードを、補正コード用メモリ３３から読み出す。そして、ビットスワップ戻し部６１は、注目画素の予測値、補正コードに基づいて、注目画素の埋め込み画素値を表す新コードをビットスワップすることにより、注目画素の画素値と、そこに埋め込まれていた埋め込み対象データを復号するビットスワップ戻し処理を行う。
【０１７２】
即ち、ステップＳ６３では、例えば、図２７のフローチャートに示すように、ビットスワップ埋め込み部４２（図２５）は、ステップＳ７１において、注目画素の埋め込み後画素値、その予測値、注目画素についての補正コードを取得する。そして、注目画素の埋め込み画素値は、ビットスワップコード生成部７１に、注目画素の予測値は、予測誤差計算部７３に、補正コードは、ビットスワップコード決定部７５に、それぞれ供給される。
【０１７３】
その後、ステップＳ７２に進み、ビットスワップコード生成部７１は、注目画素の埋め込み後画素値を表す新コードをビットスワップすることにより、全パターンのビットスワップ結果を求め、ビットスワップコード用メモリ７２に供給して記憶させる。また、ステップＳ７２では、ビットスワップコード生成部７１は、各ビットスワップ結果が表す画素値であるビットスワップ値を、予測誤差計算部７３に供給する。さらに、ステップＳ７２では、予測誤差計算部７３が、注目画素の予測値の、ビットスワップコード生成部７１からのビットスワップ値に対する予測誤差を計算し、予測誤差用メモリ７４に供給して記憶させる。
【０１７４】
そして、ステップＳ７３に進み、ビットスワップコード決定部７５は、予測誤差用メモリ７４に記憶された予測誤差を読み出し、小さい順にソートする。さらに、ビットスワップコード決定部７５は、予測誤差のソート結果における、補正コードに対応する順位の新コードを、ビットスワップコード用メモリ７２を参照することで検出し、その新コードが表す画素値を、注目画素の復号結果として求める。
【０１７５】
その後、ビットスワップコード決定部７５は、ステップＳ７４において、予測誤差のソート結果における、注目画素の埋め込み画素値に対応する新コードの順位を検出し、その順位に対応する値を、その埋め込み画素値（または復号された画素値）に埋め込まれていた埋め込み対象データの復号結果として求める。
【０１７６】
ビットスワップコード決定部７５は、以上のようにして、注目画素の画素値と埋め込み対象データを復号すると、ステップＳ７５において、その注目画素の画素値と埋め込み対象データを、画像データ用メモリ１３と埋め込み対象データ用メモリ１４にそれぞれ供給して記憶させ、リターンする。
【０１７７】
図２６に戻り、ステップＳ６３の処理後は、ステップＳ６４に進み、ビットスワップ戻し部６１は、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成するすべての画素を注目画素として処理を行ったかどうかを判定し、まだ、すべての画素を注目画素として処理を行っていないと判定した場合、ラインスキャン順で、まだ、注目画素としていない画素を、新たに注目画素として、ステップＳ６２に戻る。
【０１７８】
また、ステップＳ６４において、埋め込み後画像データ用メモリ１１に記憶された埋め込み後画像データを構成するすべての画素を注目画素として処理を行ったと判定された場合、即ち、画像データ用メモリ１３に、１フレーム分の画素値で構成される画像データが記憶されるとともに、埋め込み対象データ用メモリ１４に、その画像データに埋め込まれていた埋め込み対象データが記憶された場合、ステップＳ６５に進み、コード変換部６２は、画像データ用メモリ１３から、復号された画素値を読み出し、その画素値を表すビット列を、新コードから従来コード（バイナリコード）に変換する。
【０１７９】
そして、ステップＳ６６に進み、コード変換部６２から、従来コードで表され画素値が出力されるとともに、埋め込み対象データ用メモリ１４から、そこに記憶されている埋め込み対象データ（の復号値）が出力され、処理を終了する。
【０１８０】
なお、図２６のフローチャートの処理は、復号装置に、１フレーム分の多重化データが供給されるごとに、その１フレームの多重化データについて行われる。
【０１８１】
次に、図２８は、本件発明者が行った埋め込み符号化処理のシミュレーション結果を示している。
【０１８２】
即ち、図２８（Ａ）は、従来コードを用いて埋め込み符号化処理を行った場合のシミュレーション結果を、図２８（Ｂ）は、新コードを用いて埋め込み符号化処理を行った場合のシミュレーション結果を、それぞれ示している。
【０１８３】
なお、シミュレーションにおいては、ＲＧＢ(Red, Green, Blue)の、横×縦が、１９２０×１０３５画素の静止画を用い、Ｒ，Ｇ，Ｂの各成分に、埋め込み対象データを埋め込んだ。
【０１８４】
図２８において、「埋め込める情報量」は、１画素当たりに埋め込むことのできた埋め込み対象データのビット数を表しており、これは、従来コードを用いる場合（図２８（Ａ））であっても、新コードを用いる場合（図２８（Ｂ））であっても、同一になる。
【０１８５】
また、「補正コードデータ量（圧縮後）」は、埋め込み符号化処理を行った結果得られる補正コードをハフマン符号化して得られる符号化補正コードの、１画素当たりのデータ量を示しており、図２８から、新コードを用いた場合の方が、従来コードを用いる場合に比較して、１画素当たりの符号化補正コードのデータ量が少なくなっていることが分かる。
【０１８６】
「差分」は、「埋め込める情報量」の値から、「補正コードデータ量（圧縮後）」の値を減算した差分値を示しており、いわば、１画素に埋め込むことのできる、実質的なデータ量を表す。ここで、図２８の各欄の値は、小数点以下第３位を四捨五入してある。
【０１８７】
なお、圧縮率は、画像データのデータ量をＡと、その画像データに埋め込むことのできる埋め込み対象データのデータ量をＢと、埋め込み符号化処理を行うことにより得られる符号化補正コードのデータ量をＣと、それぞれおくと、（Ａ＋Ｃ）／（Ａ＋Ｂ）となる。
【０１８８】
次に、上述の場合には、補正コードを用いることにより、完全可逆の埋め込み符号化および復号を実現するとともに、新コードを採用することで、圧縮率の向上を図ることとしたが、補正コードを用いずに、新コードだけを採用することが可能である。そして、新コードだけを採用する場合でも、従来コードを採用する場合に比較して、復号精度を向上させることができる。
【０１８９】
即ち、０または１の数が同一の従来コードについては、前述したように、小さな画素値において、間隔が密になっているため、比較的精度の高い予測値が得られても、その予測値は、真の画素値に近い他の画素値に対する予測誤差を最小にするものになりやすく、そのため、真の画素値を正確に復号することができない場合が多くなる。
【０１９０】
これに対して、０または１の数が同一の新コードについては、そのような新コードで表される画素値の間隔が、均一で、かつ、なるべく粗になるようになっているため、比較的精度の高い予測値が得られれば、その予測値は、真の画素値に対する予測誤差を最小にするものになりやすく、そのため、真の画素値が正確に復号されることになる。
【０１９１】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０１９２】
そこで、図２９は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０１９３】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク１０５やＲＯＭ１０３に予め記録しておくことができる。
【０１９４】
あるいはまた、プログラムは、フロッピーディスク、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，ｘ2，・・・の集合と、所定のタップ係数ｗ1，ｗ2，・・・の線形結合により規定される線形１次結合モデルにより求めることを考える。この場合、予測値Ｅ［ｙ］は、次式で表すことができる。
【０２０６】
Ｅ［ｙ］＝ｗ1ｘ1＋ｗ2ｘ2＋・・・・・・（１）
【０２０７】
式（１）を一般化するために、タップ係数ｗjの集合でなる行列Ｗ、生徒データｘijの集合でなる行列Ｘ、および予測値Ｅ［ｙj］の集合でなる行列Ｙ’を、
【数１】
0004235870.tif 000002
で定義すると、次のような観測方程式が成立する。
【０２０８】
ＸＷ＝Ｙ’・・・（２）
ここで、行列Ｘの成分ｘijは、ｉ件目の生徒データの集合（ｉ件目の教師データｙiの予測に用いる生徒データの集合）の中のｊ番目の生徒データを意味し、行列Ｗの成分ｗjは、生徒データの集合の中のｊ番目の生徒データとの積が演算されるタップ係数を表す。また、ｙiは、ｉ件目の教師データを表し、従って、Ｅ［ｙi］は、ｉ件目の教師データの予測値を表す。なお、式（１）の左辺におけるｙは、行列Ｙの成分ｙiのサフィックスｉを省略したものであり、また、式（１）の右辺におけるｘ1，ｘ2，・・・も、行列Ｘの成分ｘijのサフィックスｉを省略したものである。
【０２０９】
そして、この観測方程式に最小自乗法を適用して、注目画素の画素値ｙに近い予測値Ｅ［ｙ］を求めることを考える。この場合、教師データとなる注目画素の真の画素値ｙの集合でなる行列Ｙ、およびその画素値ｙに対する予測値Ｅ［ｙ］の残差ｅの集合でなる行列Ｅを、
【数２】
0004235870.tif 000003
で定義すると、式（２）から、次のような残差方程式が成立する。
【０２１０】
ＸＷ＝Ｙ＋Ｅ・・・（３）
【０２１１】
この場合、注目画素の画素値ｙに近い予測値Ｅ［ｙ］を求めるためのタップ係数ｗjは、自乗誤差
【数３】
0004235870.tif 000004
を最小にすることで求めることができる。
【０２１２】
従って、上述の自乗誤差をタップ係数ｗjで微分したものが０になる場合、即ち、次式を満たすタップ係数ｗjが、注目画素の画素値ｙに近い予測値Ｅ［ｙ］を求めるため最適値ということになる。
【０２１３】
【数４】
0004235870.tif 000005
0004235870.tif 000006
【０２１４】
そこで、まず、式（３）を、タップ係数ｗjで微分することにより、次式が成立する。
【０２１５】
【数５】
0004235870.tif 000007
0004235870.tif 000008
【０２１６】
式（４）および（５）より、式（６）が得られる。
【０２１７】
【数６】
0004235870.tif 000009
0004235870.tif 000010
【０２１８】
さらに、式（３）の残差方程式における生徒データｘij、タップ係数ｗj、教師データｙi、および残差ｅiの関係を考慮すると、式（６）から、次のような正規方程式を得ることができる。
【０２１９】
【数７】
0004235870.tif 000011
0004235870.tif 000012
【０２２０】
なお、式（７）に示した正規方程式は、行列（共分散行列）Ａおよびベクトルｖを、
【数８】
0004235870.tif 000013
で定義するとともに、ベクトルＷを、数１で示したように定義すると、式
ＡＷ＝ｖ・・・（８）
で表すことができる。
【０２２１】
式（７）における各正規方程式は、生徒データｘijおよび教師データｙiのセットを、ある程度の数だけ用意することで、求めるべきタップ係数ｗjの数Ｊと同じ数だけたてることができ、従って、式（８）を、ベクトルＷについて解くことで（但し、式（８）を解くには、式（８）における行列Ａが正則である必要がある）、最適なタップ係数ｗjを求めることができる。なお、式（８）を解くにあたっては、例えば、掃き出し法（Gauss-Jordanの消去法）などを用いることが可能である。
【０２２２】
以上のようにして、最適なタップ係数ｗjを求めておき、さらに、そのタップ係数ｗjを用い、式（１）により、注目画素の画素値ｙに近い予測値Ｅ［ｙ］を求めるのが適応処理である。
【０２２３】
注目画素の予測値は、以上のようなクラス分類適応処理によって求めることが可能である。
【０２２４】
【発明の効果】
本発明の第１のデータ処理装置およびデータ処理方法、並びに記録媒体によれば、第１のディジタルデータ内の、所定数ビット数からなるターゲットデータがビットスワップされ、ターゲットデータ周辺の周辺データに対応する値からターゲットデータに対応する値が予測され、その結果得られる予測値が出力される。そして、出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされ、ソートされた、ビットスワップされたターゲットデータに応じて、補正コードが出力される。また、第２のディジタルデータに応じて、ソートされた、ビットスワップされたターゲットデータの内の１つが、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力される。従って、復号精度が高いデータの埋め込みを行うことが可能となる。
本発明の第２のデータ処理装置およびデータ処理方法、並びに記録媒体によれば、第１のディジタルデータが第１のコードとして変換された値に基づいて、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードである新コードに、第１のディジタルデータが変換され、新コードに変換された第１のディジタルデータ内の、所定ビット数からなるターゲットデータがビットスワップされる。そして、ターゲットデータ周辺の新コードである周辺データに対応する値からターゲットデータに対応する値が予測され、その結果得られる予測値が出力される。また、出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされ、第２のディジタルデータに応じて、ソートされた、ビットスワップされたターゲットデータの内の１つが、第１のディジタルデータに第２のディジタルデータを埋め込んだ埋め込みデータとして出力される。従って、復号精度が高いデータの埋め込みを行うことが可能となる。
【０２２５】
本発明の第１の復号装置および復号方法、並びに第３の記録媒体によれば、埋め込みデータ内の、所定ビット数であるターゲットデータがビットスワップされ、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値が予測され、その結果得られる予測値が出力される。出力される予測値と、ビットスワップされたターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされ、補正コードに応じて、ソートされた、ビットスワップされたターゲットデータのうちの１つのコードが、ターゲットデータを復号することにより得られる第１のディジタルデータである復号データとして出力される。また、ソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータが出力される。従って、データを、精度良く復号することが可能となる。
本発明の第２の復号装置および復号方法、並びに第４の記録媒体によれば、埋め込みデータ内の、所定ビット数であるターゲットデータがビットスワップされ、０/１の数が同一であるビット列がビットスワップされることにより生成されるコードに対応する値同士の間隔が実質的に均一になるように、各コードに値が割り当てられるコードを表す新コードであり、ターゲットデータ周辺の既に復号されたデータである復号データに対応する値からターゲットデータを復号することにより得られる復号データに対応する値が予測され、その結果得られる予測値が出力される。出力される予測値と、ビットスワップされた新コードとしてのターゲットデータに対応する各値との予測誤差値に応じて、ビットスワップされたターゲットデータがソートされる。また、ソートされた、ビットスワップされたターゲットデータの順位に応じて、第２のディジタルデータが出力される。さらに、ソートされた、ビットスワップされたターゲットデータの順位に応じて、ターゲットデータを復号することにより得られる復号データが出力され、出力される新コードである復号データに対応する元のコードが出力される。従って、データを、精度良く復号することが可能となる。
【図面の簡単な説明】
【図１】従来の埋め込み符号化装置の一例の構成を示すブロック図である。
【図２】図１の埋め込み符号化装置の処理を説明するフローチャートである。
【図３】図１の埋め込み符号化装置の処理を説明する図である。
【図４】ビット列における０または１の数と、そのビット列に埋め込むことのできるデータ量との関係を説明する図である。
【図５】従来の復号装置の一例の構成を示すブロック図である。
【図６】図５の復号装置の処理を説明するフローチャートである。
【図７】図５の復号装置の処理を説明する図である。
【図８】補正コードを用いる埋め込み符号化装置の一実施の形態の構成例を示すブロック図である。
【図９】図８の埋め込み符号化装置の処理を説明するフローチャートである。
【図１０】図８の埋め込み符号化装置の処理を説明する図である。
【図１１】補正コードを用いる復号装置の一実施の形態の構成例を示すブロック図である。
【図１２】図１１の復号装置の処理を説明するフローチャートである。
【図１３】図１１の復号装置の処理を説明する図である。
【図１４】従来コードを用いた場合の埋め込み符号化結果を示す図である。
【図１５】新コードと画素値との対応関係を示す図である。
【図１６】新コードと画素値との対応関係を示す図である。
【図１７】１が６ビットある８ビットのビット列のビットスワップパターンを示す図である。
【図１８】新コードを用いた場合の埋め込み符号化結果を示す図である。
【図１９】新コードを用いた場合の埋め込み符号化結果を示す図である。
【図２０】本発明を適用した埋め込み符号化装置の一実施の形態の構成例を示すブロック図である。
【図２１】ビットスワップ埋め込み部４２の構成例を示すブロック図である。
【図２２】図２０の埋め込み符号化装置の処理を説明するフローチャートである。
【図２３】図２２のステップＳ４４の処理の詳細を説明するフローチャートである。
【図２４】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図２５】ビットスワップ戻し部６１の構成例を示すブロック図である。
【図２６】図２４の復号装置の処理を説明するフローチャートである。
【図２７】図２６のステップＳ６３の処理の詳細を説明するフローチャートである。
【図２８】本件発明者によるシミュレーション結果を示す図である。
【図２９】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
１  画像データ用メモリ，  ２  埋め込み対象データ用メモリ，  ４  埋め込み後画像データ用メモリ，  １１  埋め込み後画像データ用メモリ，  １３  画像データ用メモリ，  １４  埋め込み対象データ用メモリ，  １５  予測値取得部，  ２１  予測値取得部，  ２３  補正コード用メモリ，  ２４  圧縮部，  ２５  ＭＵＸ，  ３１  ＤＥＭＵＸ，  ３２  伸張部，  ３３  補正コード用メモリ，  ４１  コード変換部，  ４２  ビットスワップ埋め込み部，  ５１  ビットスワップコード生成部，  ５２  ビットスワップコード用メモリ，  ５３  予測誤差計算部，  ５４  予測誤差用メモリ，  ５５  ビットスワップコード決定部，  ６１  ビットスワップ戻し部，  ６２  コード変換部，  ７１  ビットスワップコード生成部，  ７２  ビットスワップコード用メモリ，  ７３  予測誤差計算部，  ７４  予測誤差用メモリ，  ７５  ビットスワップコード決定部，  １０１  バス，  １０２  CPU，  １０３  ROM，  １０４  RAM，  １０５ハードディスク，  １０６  出力部，  １０７  入力部，  １０８  通信部，１０９  ドライブ，  １１０  入出力インタフェース，  １１１  リムーバブル記録媒体
【図１】
0004235870.tif 000014
【図２】
0004235870.tif 000015
【図３】
0004235870.tif 000016
【図４】
0004235870.tif 000017
【図５】
0004235870.tif 000018
【図６】
0004235870.tif 000019
【図７】
0004235870.tif 000020
【図８】
0004235870.tif 000021
【図９】
0004235870.tif 000022
【図１０】
0004235870.tif 000023
【図１１】
0004235870.tif 000024
【図１２】
0004235870.tif 000025
【図１３】
0004235870.tif 000026
【図１４】
0004235870.tif 000027
【図１５】
0004235870.tif 000028
【図１６】
0004235870.tif 000029
【図１７】
0004235870.tif 000030
【図１８】
0004235870.tif 000031
【図１９】
0004235870.tif 000032
【図２０】
0004235870.tif 000033
【図２１】
0004235870.tif 000034
【図２２】
0004235870.tif 000035
【図２３】
0004235870.tif 000036
【図２４】
0004235870.tif 000037
【図２５】
0004235870.tif 000038
【図２６】
0004235870.tif 000039
【図２７】
0004235870.tif 000040
【図２８】
0004235870.tif 000041
【図２９】
0004235870.tif 000042