(57)【特許請求の範囲】
【請求項１】
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成手段と、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成手段に指示する符号種適応制御手段とを有し、
各符号化時点において前記符号生成手段は符号化対象データの事象に対し前記符号種適応制御手段により指示された符号種の符号を生成して出力し、
前記符号種適応制御手段は、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
現在又は近接した将来の複数の符号化時点で、前記２符号種中の各符号種を、前記選択確率取得手段により取得された選択確率に応じた割合で、どのような順番で適用するかを決定するための鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率及び前記鍵情報記憶手段に記憶されている鍵情報に基づき、現在又は近接した将来の複数の符号化時点で適用する符号種類を決定する符号種決定手段とを有し、前記符号種決定手段により決定された符号種を前記符号生成手段に指示することを特徴とする符号化装置。
【請求項２】
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成手段と、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成手段に指示する符号種適応制御手段とを有し、
各符号化時点において、前記符号生成手段は符号化対象データの事象に対し前記符号種適応制御手段により指示された符号種の符号を生成して出力し、
前記符号種適応制御手段は、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから現在の符号化時点における前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
拡散値を一時的に記憶するための拡散値記憶手段と、
鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率に、前記拡散値記憶手段に記憶されている現在の符号化時点に対する拡散値を加算し、加算後の選択確率の値が所定値以上であるか否かによって、前記２符号種中の特定符号種又は他方の符号種を現在の符号化時点で適用する符号種として選択し、該符号種の選択で生じた確率差分に前記鍵情報記憶手段に鍵情報として記憶されている重み係数を乗じることによって近接した将来の符号化時点に対する拡散値を求め、求めた拡散値を前記拡散値記憶手段に一時的に記憶させる符号種決定手段とを有し、前記符号種決定手段で決定された符号種を前記符号生成手段に指示することを特徴する符号化装置。
【請求項３】
請求項１に記載の符号化装置により符号化された符号が順次入力する復号化装置であって、
各復号化時点において入力符号を相異なる符号空間を有する２つの符号種の符号として復号化可能なデータ生成手段と、
各復号化時点において前記２符号種中のいずれの符号種を適用するかを前記データ生成手段に指示する符号種適応制御手段とを有し、
各復号化時点において前記データ生成手段は入力符号を前記符号種適応制御手段により指示された符号種の符号として復号化したデータを生成して出力し、
前記符号種適応制御手段は、
前記データ生成手段より出力された近接した過去の復号化データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
現在又は近接した将来の複数の復号化時点で、前記２符号種中の各符号種が、前記選択確率取得手段により取得された選択確率に応じた割合で、どのような順番で適用されるかを決定するための鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率及び前記鍵情報記憶手段に記憶されている鍵情報に基づき、現在又は近接した将来の複数の復号化時点で適用する符号種を決定する符号種決定手段とを有し、前記符号種決定手段で決定された符号種を前記データ生成手段に指示することを特徴とする復号化装置。
【請求項４】
請求項２に記載の符号化装置により符号化された符号が順次入力する復号化装置であって、
各復号化時点において入力符号を相異なる符号空間を有する２つの符号種の符号として復号化可能なデータ生成手段と、
各復号化時点において前記２符号種中のいずれの符号種を適用するかを前記データ生成手段に指示する符号種適応制御手段とを有し、
各復号化時点において前記データ生成手段は入力符号を前記符号種適応制御手段により指示された符号種の符号として復号化したデータを生成して出力し、
前記符号種適応制御手段は、
前記データ生成手段より出力された近接した過去の復号化データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
拡散値を一時的に記憶するための拡散値記憶手段と、
鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率に、前記拡散値記憶手段に記憶されている現在の符号化時点に対する拡散値を加算し、加算後の選択確率の値が所定値以上であるか否かによって、前記２符号種中の特定符号種又は他方の符号種を現在の復号化時点で適用する符号種として選択し、該符号種の選択で生じた確率差分に前記鍵情報記憶手段に鍵情報として記憶されている重み係数を乗じることによって近接した将来の復号化時点に対する拡散値を求め、求めた拡散値を前記拡散値記憶手段に一時的に記憶させる符号種決定手段とを有し、前記符号種決定手段で決定された符号種を前記データ生成手段に指示することを特徴する復号化装置。
【請求項５】
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成ステップと、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成ステップに指示する符号種適応制御ステップとを有し、
各符号化時点において前記符号生成ステップは符号化対象データの事象に対し前記符号種適応制御ステップにより指示された符号種の符号を生成して出力し、
前記符号種適応制御ステップは、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得ステップと、
前記生起回数取得ステップにより求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得ステップと、
前記エントロピー取得ステップにより求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得ステップと、
現在又は近接した将来の複数の符号化時点で、前記２符号種中の各符号種を、前記選択確率取得ステップにより取得された選択確率に応じた割合で、どのような順番で適用するかを決定するための記憶手段に記憶されている鍵情報と、前記選択確率取得ステップにより取得された選択確率とに基づき、現在又は近接した将来の複数の符号化時点で適用する符号種類を決定する符号種決定ステップとを有し、前記符号種決定ステップにより決定された符号種を前記符号生成ステップに指示することを特徴とする符号化方法。
【請求項６】
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成ステップと、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成ステップに指示する符号種適応制御ステップとを有し、
各符号化時点において、前記符号生成ステップは符号化対象データの事象に対し前記符号種適応制御ステップにより指示された符号種の符号を生成して出力し、
前記符号種適応制御ステップは、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得ステップと、
前記生起回数取得ステップにより求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得ステップと、
前記エントロピー取得ステップにより求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから現在の符号化時点における前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得ステップと、
前記選択確率取得ステップにより取得された選択確率に、拡散値記憶手段に記憶されている現在の符号化時点に対する拡散値を加算し、加算後の選択確率の値が所定値以上であるか否かによって、前記２符号種中の特定符号種又は他方の符号種を現在の符号化時点で適用する符号種として選択し、該符号種の選択で生じた確率差分に鍵情報記憶手段に鍵情報として記憶されている重み係数を乗じることによって近接した将来の符号化時点に対する拡散値を求め、求めた拡散値を前記拡散値記憶手段に一時的に記憶させる符号種決定ステップとを有し、前記符号種決定ステップで決定された符号種を前記符号生成ステップに指示することを特徴する符号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、デジタルデータの符号化／復号化の分野に係り、特に、データの秘匿性を保持可能な符号化装置及び復号化装置に関する。
【０００２】
【従来の技術】
デジタルデータを圧縮し、かつ秘匿性を持たせる技術が、従来いくつか提案されている。圧縮のアルゴリズムを公開しなければ、圧縮することである程度の秘匿性が得られるが、アルゴリズムを公開し、そのパラメータを鍵データとする方式が現実的である。この種の方式としては、複数種のハフマン符号を所定の順番（これが鍵データ）で使う方式（特開平７−１３１７７７）や、１種類のハフマン符号表中で等しい符号長の符号間で置換（この置換方法が鍵データ）を行う方式（特許第２９０７４２８号）が知られており、いずれも簡易な構成で秘匿性を持った圧縮が行うことができる。
【０００３】
【発明が解決しようとする課題】
単純な２値画像データのランレングス符号化を例にして説明する。これは、白か黒かの１bitデータの連なりを、同じ色の連続数（ラン長）に置き換え、ラン長を事象ととらえ、それぞれに符号を割り当てる符号化方式である。ラン長の生起確率は圧縮対象画像によって大きく異なるため、各ラン長に割り当てる符号を固定化していると、高い符号化効率を常には得ることができない。
【０００４】
前述の特開平７−１３１７７７の方式では、符号の種類とその選択規則（鍵データ）が固定化されているため符号化効率が悪い。符号化効率を高めようとすれば、圧縮対象データごとに異なる複数の符号および鍵データを準備しなければならないが、これは、圧縮側、伸張側にとって大きな負担となってしまうため非現実的である。特許第２９０７４２８号の方式も同様に、符号は固定化されているので、高い符号化効率は望めない。さらに両方式とも、１つの圧縮対象データ中で各事象の生起確率分布に変動があった場合に、これに追従した高効率圧縮を行うことができない。
【０００５】
本発明は、上記問題点に鑑み、符号化対象データにおける各事象の生起確率分布によらずに高い符号化効率が得られ、かつデータの秘匿性を保持できる、簡易な構成の符号化装置及び方法と、その符号化データから元のデータを復元するための復号化装置を提供することにある。
【０００６】
【課題を解決するための手段】
請求項１記載の発明は、
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成手段と、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成手段に指示する符号種適応制御手段とを有し、
各符号化時点において前記符号生成手段は符号化対象データの事象に対し前記符号種適応制御手段により指示された符号種の符号を生成して出力し、
前記符号種適応制御手段は、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
現在又は近接した将来の複数の符号化時点で、前記２符号種中の各符号種を、前記選択確率取得手段により取得された選択確率に応じた割合で、どのような順番で適用するかを決定するための鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率及び前記鍵情報記憶手段に記憶されている鍵情報に基づき、現在又は近接した将来の複数の符号化時点で適用する符号種類を決定する符号種決定手段とを有し、前記符号種決定手段により決定された符号種を前記符号生成手段に指示することを特徴とする符号化装置である。
【０００７】
請求項２の発明は、
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成手段と、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成手段に指示する符号種適応制御手段とを有し、
各符号化時点において、前記符号生成手段は符号化対象データの事象に対し前記符号種適応制御手段により指示された符号種の符号を生成して出力し、
前記符号種適応制御手段は、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから現在の符号化時点における前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
拡散値を一時的に記憶するための拡散値記憶手段と、
鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率に、前記拡散値記憶手段に記憶されている現在の符号化時点に対する拡散値を加算し、加算後の選択確率の値が所定値以上であるか否かによって、前記２符号種中の特定符号種又は他方の符号種を現在の符号化時点で適用する符号種として選択し、該符号種の選択で生じた確率差分に前記鍵情報記憶手段に鍵情報として記憶されている重み係数を乗じることによって近接した将来の符号化時点に対する拡散値を求め、求めた拡散値を前記拡散値記憶手段に一時的に記憶させる符号種決定手段とを有し、前記符号種決定手段で決定された符号種を前記符号生成手段に指示することを特徴する符号化装置である。
【０００８】
請求項３記載の発明は、請求項１に記載の符号化装置により符号化された符号が順次入力する復号化装置であって、
各復号化時点において入力符号を相異なる符号空間を有する２つの符号種の符号として復号化可能なデータ生成手段と、
各復号化時点において前記２符号種中のいずれの符号種を適用するかを前記データ生成手段に指示する符号種適応制御手段とを有し、
各復号化時点において前記データ生成手段は入力符号を前記符号種適応制御手段により指示された符号種の符号として復号化したデータを生成して出力し、
前記符号種適応制御手段は、
前記データ生成手段より出力された近接した過去の復号化データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
現在又は近接した将来の複数の復号化時点で、前記２符号種中の各符号種が、前記選択確率取得手段により取得された選択確率に応じた割合で、どのような順番で適用されるかを決定するための鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率及び前記鍵情報記憶手段に記憶されている鍵情報に基づき、現在又は近接した将来の複数の復号化時点で適用する符号種を決定する符号種決定手段とを有し、前記符号種決定手段で決定された符号種を前記データ生成手段に指示することを特徴とする復号化装置である。
【０００９】
請求項４記載の発明は、請求項２に記載の符号化装置により符号化された符号が順次入力する復号化装置であって、
各復号化時点において入力符号を相異なる符号空間を有する２つの符号種の符号として復号化可能なデータ生成手段と、
各復号化時点において前記２符号種中のいずれの符号種を適用するかを前記データ生成手段に指示する符号種適応制御手段とを有し、
各復号化時点において前記データ生成手段は入力符号を前記符号種適応制御手段により指示された符号種の符号として復号化したデータを生成して出力し、
前記符号種適応制御手段は、
前記データ生成手段より出力された近接した過去の復号化データより複数の特定事象の生起回数を求める生起回数取得手段と、
前記生起回数取得手段により求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得手段と、
前記エントロピー取得手段により求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得手段と、
拡散値を一時的に記憶するための拡散値記憶手段と、
鍵情報を記憶する鍵情報記憶手段と、
前記選択確率取得手段により取得された選択確率に、前記拡散値記憶手段に記憶されている現在の符号化時点に対する拡散値を加算し、加算後の選択確率の値が所定値以上であるか否かによって、前記２符号種中の特定符号種又は他方の符号種を現在の復号化時点で適用する符号種として選択し、該符号種の選択で生じた確率差分に前記鍵情報記憶手段に鍵情報として記憶されている重み係数を乗じることによって近接した将来の復号化時点に対する拡散値を求め、求めた拡散値を前記拡散値記憶手段に一時的に記憶させる符号種決定手段とを有し、前記符号種決定手段で決定された符号種を前記データ生成手段に指示することを特徴する復号化装置である。
【００１０】
請求項５記載の発明は、
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成ステップと、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成ステップに指示する符号種適応制御ステップとを有し、
各符号化時点において前記符号生成ステップは符号化対象データの事象に対し前記符号種適応制御ステップにより指示された符号種の符号を生成して出力し、
前記符号種適応制御ステップは、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得ステップと、
前記生起回数取得ステップにより求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得ステップと、
前記エントロピー取得ステップにより求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得ステップと、
現在又は近接した将来の複数の符号化時点で、前記２符号種中の各符号種を、前記選択確率取得ステップにより取得された選択確率に応じた割合で、どのような順番で適用するかを決定するための記憶手段に記憶されている鍵情報と、前記選択確率取得ステップにより取得された選択確率とに基づき、現在又は近接した将来の複数の符号化時点で適用する符号種類を決定する符号種決定ステップとを有し、前記符号種決定ステップにより決定された符号種を前記符号生成ステップに指示することを特徴とする符号化方法である。
【００１１】
請求項６記載の発明は、
各符号化時点において符号化対象データの事象に対し相異なる符号空間を有する２つの符号種の符号を生成可能な符号生成ステップと、
各符号化時点において前記２符号種中のいずれの符号種を適用するかを前記符号生成ステップに指示する符号種適応制御ステップとを有し、
各符号化時点において、前記符号生成ステップは符号化対象データの事象に対し前記符号種適応制御ステップにより指示された符号種の符号を生成して出力し、
前記符号種適応制御ステップは、
近接した過去の符号化対象データより複数の特定事象の生起回数を求める生起回数取得ステップと、
前記生起回数取得ステップにより求められた各特定事象の生起回数より各特定事象のエントロピーを求めるエントロピー取得ステップと、
前記エントロピー取得ステップにより求められた各特定事象のエントロピーと各特定事象に対する前記２符号種中の各符号種の符号長とから現在の符号化時点における前記２符号種中の一方の符号種（以下、特定符号種と記す）の選択確率を求め、求めた各特定事象に関する特定符号種の選択確率の平均をとって最終的な選択確率を取得する選択確率取得ステップと、
前記選択確率取得ステップにより取得された選択確率に、拡散値記憶手段に記憶されている現在の符号化時点に対する拡散値を加算し、加算後の選択確率の値が所定値以上であるか否かによって、前記２符号種中の特定符号種又は他方の符号種を現在の符号化時点で適用する符号種として選択し、該符号種の選択で生じた確率差分に鍵情報記憶手段に鍵情報として記憶されている重み係数を乗じることによって近接した将来の符号化時点に対する拡散値を求め、求めた拡散値を前記拡散値記憶手段に一時的に記憶させる符号種決定ステップとを有し、前記符号種決定ステップで決定された符号種を前記符号生成ステップに指示することを特徴する符号化方法である。
【００２１】
【発明の実施の形態】
以下、添付図面を参照して説明するが、説明の重複を避けるため、複数の図において同一部分もしくは対応部分には同一もしくは類似の参照番号を用いる。
【００２２】
本発明による符号化装置は、概念的には、図１に示すように符号生成部１００と符号種適応制御部２００とからなる構成である。符号生成部１００は、相異なる符号空間を有する複数種類の符号を生成可能であり、各符号化時点において、符号種適応制御部２００により指定された１つの符号種の符号を選択して出力する。符号種適応制御部２００は、符号生成部１００によって符号を生成済みの、つまり符号化済みのデータから、現在又は近接する将来の１つ以上の符号化時点における符号種を選択するための情報を求め、この情報と、復号化側と秘匿的に共有している鍵情報とから、現在又は近接する将来の１つ以上の符号化時点で使用される符号種を決定して符号生成部１００に指示する。このように複数の符号種を適応的かつ動的に選択して用いる構成によれば、符号化対象データにおける各事象の生起確率分布によらず、常に高い符号化効率を得ることができ、かつ、秘匿性を確保することができる。
【００２３】
以下に説明する本発明の符号化装置の実施例においては、２値データのランレングス符号化が行われるが、これのみに限定されるわけではない。また、各実施例で用い得る符号の例を図２に示す。図２においては、Golomb符号とS-S-S(Start-Step-Stop)符号が生起確率の大きい順に並べて示されている。Golomb符号は各事象（ラン長）の生起確率順ｎと符号長Ｌとが比例するタイプの符号であり、S-S-S符号は各事象の生起確率順ｎの対数と符号長Ｌとが比例するタイプの符号である。それぞれ２次/８次、（1,2,∞）/（2,1,∞）などのパラメータで、その比例係数が異なる２種類の符号を示している。Golomb符号は、各事象の生起確率分布が負の指数分布（Pｎ=C−ｎ）であるデータに対し最も高い符号化効率を得られる。S-S-S符号は、各事象の生起確率分布が負のべき乗分布（Pｎ=n−ｃ）であるデータに対し、最も高い符号化効率が得られる。また、どちらも組織的ハフマン符号と呼ばれる符号である。このタイプの符号は、図２のような表を用いなくても、事象番号/符号間の変換を演算で行えるため、回路規模を小さくできる特徴がある。
【００２４】
参考のために、２次のGolomb符号（Ｇ２）と８次のGolomb符号（Ｇ８）を用いる場合の、特開平７−１３１７７７の方式による符号化例を図３に示す。図３において、ａは圧縮対象のデータであり、ｂは同データの同値連続区間（ラン）の長さ（ラン長）である。それぞれのラン長（事象）に対し、ｃ及びｄに示すようなＧ２符号及びＧ８符号を発生し、それらを交互に選択することにより、ｅに示すような符号列を出力する。この「交互に選択する」ことが鍵情報である。この例から明らかなように、従来の方式では、事象の生起確率分布を考慮に入れないため高い符号化効率を達成することは困難であった。
【００２５】
《符号化装置の実施例１》
図４に、本発明の符号化装置の実施例１のブロック構成を示す。本実施例及び後記各実施例においては、符号化対象の２値データのランレングス符号化を行うため、符号化対象の２値データを０又は１の連続したランの長さ（ラン長）に変換するためのモデル化部１０１が設けられている。そして、符号生成部１００及び符号種適応制御部２００には、符号化対象の２値データではなく、モデル化部１０１により変換されたラン長が入力される。
【００２６】
符号生成部１００は、符号化部１１０と選択部１１１とから構成される。符号化部１１０は、符号化対象データの各事象（ここではラン長）に対し２種類の圧縮符号を割り当てる処理を行う。生起確率の高い事象には長さの短い符号、低い事象には長い符号を割り当てることで、データ圧縮がなされる。ここでは、図２に示した２種類のGolomb符号（Ｇ２符号，Ｇ８符号）を用いるものととして説明するが（他の実施例も同様）、２種類のS-S-S符号あるいは他の複数種類の符号を用いることも可能である。符号化部１１０は、各事象に割当てたＧ２符号、Ｇ８符号を両方とも選択部１１１に出力する。選択部１１１は、各符号化時点において、符号種適応制御部２００からの指示に従って、符号化部１１０より出力されたＧ２符号，Ｇ８符号の一方を選択して出力する。なお、破線１１２に示すように符号種選択指示を符号化部１１０に与え、符号化部１１０では各事象に対し指示された一方の種類の符号（Ｇ２符号又はＧ８符号）だけを割当て、それを破線１１３に示すように直接外部に出力する構成とすることもでき、この場合は選択部１１１は不要である。
【００２７】
符号種適応制御部２００は、近接する将来の符号化時点における符号種を選択するための情報を求めるための手段として、事象カウント部２０１、エントロピー計算部２０２及び選択確率計算部２０３を有する。事象カウント部２０１は、符号化済みの過去６４事象（ラン長）において、短い符号が割り当たられる特定の事象ごとの発生回数をカウントする。ここでは、図２に示す事象番号１から事象番号８までの各事象ごとの回数をカウントするものとして説明する。エントロピー計算部２０２は、事象カウント部２０１による各事象のカウント結果から、特定の各事象の局所的なエントロピーを計算する。選択確率計算部２０３は、特定の各事象ごとに、求められたエントロピーと、その事象の符号長とに基づいて、近接する将来の符号化時点で、Ｇ２符号（又はＧ８符号）をどの割合で選択するかの指標（選択確率と呼ぶ）を計算する。
【００２８】
例えば、ある６４事象における各事象の発生回数が図７に示すような回数であったとする。この例で、エントロピーと選択確率の求め方を説明する。エントロピー計算部２０２は、各事象の生起回数からその生起確率を求め、エントロピーを計算する。例えば、事象番号１は、過去６４事象中で８回生起しているので、その生起確率は8/64である。そして、その生起確率からエントロピーは、
-log2 (8/64)＝ 3.0 bit  と計算される。選択確率計算部２０３は、事象番号１のＧ８符号長は4.0  bit、Ｇ２符号長は2.0 bitであり、エントロピー3.0 bit  は、ちょうどその中間に位置するため、Ｇ２符号の選択確率を0.5 と計算する（Ｇ８符号の選択確率は、１-0.5＝0.5）。同様の手順で事象番号２〜８の各事象のエントロピー及び選択確率は図７のように求まる。選択確率計算部２０３は、事象番号１〜８の選択確率の平均値を最終的な選択確率として出力する。ただし、この例では、事象番号５，６はＧ８符号，Ｇ２符号の符号長が同一であるため、それらは計算対象から除外し、６個の事象の選択確率の平均をとる。図７に示す例では、最終的にＧ２符号の選択確率＝0.4 が得られる。
【００２９】
図８は、事象番号１乃至１４の符号長と、前述のようにして過去６４事象より求められたエントロピーをプロットしたグラフである。このグラフを見ると、エントロピーのカーブは、Ｇ８符号のカーブに幾分近く、Ｇ２符号よりＧ８符号を幾分多く選択したほうが符号化効率が良いことが分かる。このことは、Ｇ２符号の選択確率が0.4となったことと合致する。つまり、Ｇ２符号の選択確率は、過去の事象から求めたエントロピーのカーブがＧ２符号のカーブにどれくらい近いかを０〜１の範囲で表した１つの指標と言うことができる。
【００３０】
符号種適応制御部２００は、さらに符号種決定部２１０と鍵情報記憶部２１１を有する。鍵情報記憶部２１１は、復号化側と秘匿的に共有する鍵情報を記憶する手段である。符号種決定部２１０は選択確率と鍵情報に基づき使用する符号の種類を決定して符号生成部１００に指示する手段である。
【００３１】
本実施例においては、図６に略示するように、連続した５つの事象▲１▼〜▲５▼に対し、その前の６４事象から求めた選択確率を適用する。符号種決定部２１０は、５事象▲１▼〜▲５▼におけるＧ２符号、Ｇ８符号の使用割合を選択確率に応じて決定し、さらに、その割合で選択したＧ２符号，Ｇ８符号をどのような順番で選択するかを鍵情報に基づいて決定する。つまり、Ｇ２符号の選択確率が0.4なら、１０回の符号化時点中、Ｇ２符号を４回、Ｇ８符号を６回、選択することになるが、その選択の順番には自由度がある。この選択順番を秘密の鍵情報で決定することにより、選択確率を利用するアルゴリズムが公開されたとしても、鍵情報さえ非公開にしておけば符号化データの秘匿性が保たれるようにしている。
【００３２】
このような符号の使用割合と選択順番を一括して決定できるようにするため、本実施例においては、例えば、図９に示すようなテーブル形式の鍵情報が鍵情報記憶部２１１に格納されている。図中の０，１，２，．．．がキー値であり、キー値とＧ２符号選択確率とで、連続した５事象中の各事象に対し使用される符号種が決まる。例えば、キー値が０でＧ２選択確率が０．４ならば、連続した５事象において、Ｇ８，Ｇ２，Ｇ２，Ｇ８，Ｇ８の順に選択されることになる。連続した５×４事象でのＧ２選択確率の遷移と符号選択結果の例を図１０に示す。この例からも理解されるように、鍵情報の使用順序、つまりキー値の選択順序をランダムにすると（復号化側と同期させる必要がある）、秘匿性がより高まる。
【００３３】
なお、鍵情報を全て秘密にするのではなく、各キー値に対応したテーブルを符号種決定部２１０に持たせるか、その内容をアルゴリズムとして持たせ、キー値（及びその使用順）だけを鍵情報として鍵情報記憶部２１１に記憶する形態も可能である。この場合でも、鍵情報を秘密にすれば秘匿性は保たれることは明らかである。
【００３４】
符号種適応制御部２００の処理フローの概略を図５に示す。ステップＳ１は、連続した５事象の切れ目であるか否かを判定するステップである。図６の事象▲１▼の直前事象の符号化が終わった時点Ｑで判定結果はＹｅｓとなり、それ以外ではＮｏとなる。判定結果がＹｅｓの場合には、図６に示すように過去の６４事象に基づいて前述のようしてＧ２符号の選択確率を求める処理を行い（ステップＳ２）、符号種決定部２１０において事象▲１▼〜▲５▼の各事象に対して選択する符号種を前述のようにして決定し、その内容を符号種選択データとして内部に保存する（ステップＳ３）。ステップＳ１の判定結果かＮｏならばステップＳ２，Ｓ３の処理は行われない。そして、符号種決定部２１０は、符号種選択データに従って、各事象▲１▼〜▲５▼に対し使用する符号種の選択指示を選択部１１１に送る（ステップＳ４）。
【００３５】
なお、符号化対象データの最初の部分、例えば６４個のラン（事象）までは、トレーニング期間として、Ｇ２符号又はＧ８符号を連続して使用するか、予め定義した順番で切り替えて使用する。これは下記実施例においても同様である。
【００３６】
《符号化装置の実施例２》
図１１に、本発明の符号化装置の実施例２のブロック構成を示す。本実施例において、符号種適応制御部２００は、近接する将来の符号化時点における符号種を選択するための情報を求めるための手段として事象カウント部２０１ａだけを具備した簡略な構成とされている。この事象カウント部２０１ａは、例えば、過去６４事象中で事象番号１，２，３の発生回数をカウントし、その合計カウント値を出力する。符号種決定部２１０は、その合計カウント値もしくは、それを正規化した値を、前記Ｇ２符号選択確率に相当する情報として利用する。この例では、その合計カウント値が大きいほど（短いランが多いほど）、Ｇ２符号の選択割合を高める。符号選択順番は、前記実施例１と同様に、図９に示したようなテーブル形式の鍵情報を利用して決定する。ただし、図９中の「Ｇ２選択確率」は、上記合計カウント値もしくはその正規化値で置き換えられる。これ以外は前記実施例１と同様の構成である。
【００３７】
このように本実施例は簡略な構成であるが、前記実施例１に近い高い符号化効率を期待でき、秘匿性については前記実施例１と同等である。なお、事象カウント部２０１ａでカウントの対象とする事象は、使用される符号の特性などに応じて適宜変更し得ることは当然である。
【００３８】
《符号化装置の実施例３》
図１２に、本発明の符号化装置の実施例３のブロック構成を示す。本実施例は、前記実施例１，２と異なり、各事象の符号化時点で、符号種適応制御部２００において選択確率を求め直して符号種を選択する処理を行う。この処理の流れを図１３により説明する。
【００３９】
各符号化時点において、前記実施例１と同様に、過去６４事象における事象番号１〜８の生起回数を事象カウント部２０１でカウントし、そのカウント値を用いてエントロピー計算部２０２で各事象番号ごとにエントロピーを計算し、選択確率計算部２０３で、エントロピーと符号長から各事象番号ごとのＧ２符号の選択確率を計算し、その平均をとることによりＧ２符号の選択確率を求める（ステップＳ１１）。符号種決定部２１０ａにおいて、そのＧ２符号選択確率に、近接した過去の符号化時点からの拡散値（後述、拡散値記憶部２１２に記憶されている）を加算し（ステップＳ１２）、加算後の選択確率が０．５以上ならＧ２符号を、そうでなければＧ８符号を選択し、選択した符号種を符号生成部１００の選択部１１１に指示する（ステップＳ１３）。最後に、符号種決定部２１０ａは、符号種の選択により発生した確率の差分（後述）の、近接した将来の１つ以上の符号化時点への拡散値を計算し、それを拡散値記憶部２１２に保存する。この拡散値の計算に用いる重み係数が鍵情報であり、これが鍵情報記憶部２１１に記憶されている。
【００４０】
以下、図１４を参照して符号種決定部２１０ａの作用について説明する。図１４（ａ）は、確率差分の拡散値を計算する際に用いられる重み係数（鍵情報）の説明図である。ここに示す例では、現在の符号化時点で＋0.4の確率差分が生じ、次の符号化時点への拡散値が＋0.4と重み係数0.75の積＋0.3となり、その１つ次の符号化時点への拡散値が＋0.4と重み係数0.25の積＋0.1となる。この拡散計算に用いられる重み係数（鍵情報）は、１組だけ用意することもできるが、複数組用意し、それを選択的に用いることもできる。後者はより高い秘匿性を得ることができる。
【００４１】
図１４（ｂ）は、過去６４事象に基づいて計算されたＧ２符号選択確率の遷移と、各符号化時点での確率差分の拡散値、拡散値を加算後の選択確率及び選択される符号種を例示している。ただし、ここでは説明を簡略にするため、鍵情報の切り替えは行わず、同図（ａ）に示した鍵情報（重み係数）を連続して使用するものとしている。符号化時点Ｐでは、計算されたＧ２符号の選択確率は0.4であるが、直前及びその前の符号化時点からの拡散値−0.2，＋0.1を加算後の選択確率は0.3となるため、Ｇ８符号が選択される。Ｇ８符号を選んだということは、Ｇ２符号の拡散値加算後の選択確率0.3を0.0にしたということであるので0.3−0.0＝＋0.3の確率差分が生じる。したがって、次の符号化時点への拡散値は＋0.3×0.75＝＋0.2、その次の符号化時点への拡散値は＋0.3×0.25＝0.1となる。符号化時点Ｐの次の次の符号化時点では、拡散値加算後のＧ２符号選択確率は0.9であるのでＧ２符号が選択される。したがって、0.9−1.0＝−0.1の確率差分が生じ、これが次の符号化時点とその次の符号化時点に同様に拡散される。
【００４２】
ここまでの説明から明らかなように、確率差分の拡散値を計算するための重み係数である鍵情報が異なると、最終的に選択される符号種が大きく異なってくる。したがって、符号種決定のアルゴリズムが公開されたとしても、鍵情報を秘密にするならば符号化データに秘匿性を持たせることができる。特に、鍵情報を切り替えて使用すると、極めて高い秘匿性を得られる。また、本実施例においても、近い過去における特定の事象の生起確率分布をベースにして符号種を適応的、動的に選択するため、符号化対象データにおける各事象の生起確率分布が変動しても高い符号化効率を達成できる。
【００４３】
以上説明した各実施例においては、２種類の符号（Ｇ２，Ｇ８）を選択する構成であったが、３種類以上の符号を選択するように拡張することも可能である。
例えば、前記実施例３において、２群以上の事象について生起回数をカウントすることにより、２つ以上の符号種についての選択確率を求め、確率差分の拡散値を加算後の選択確率が最も高い符号種を選択し、この選択で生じた確率差分を２つ以上の各符号種に同様に拡散させるような構成とすることも可能である。前記実施例１，２においても同様に、２群以上の事象の生起回数をベースにして３種以上の符号の選択を行う構成とすることも可能である。なお、符号を２種類に限定すると、装置の回路規模を小さくできる利点がある。
【００４４】
以上に説明した符号化装置により符号化されたデータを復元するための、本発明の復号化装置は、概念的には、図１５に示すようにデータ生成部３００と符号種適応制御部４００とからなる構成である。データ生成部３００は、相異なる符号空間を有する複数種類の符号から基のデータを復元することが可能であり、各復号化時点における符号を、符号種適応制御部４００により指定された符号種の符号として復号化したデータを出力する。符号種適応制御部４００は、データ生成部３００より出力された復号化データから、現在又は近接する将来の１つ以上の復号化時点における符号種を選択するための情報を求め、この情報と、符号化側と秘匿的に共有している鍵情報とから、現在又は近接する将来の１つ以上の復号化時点で使用される符号種を決定してデータ生成部３００に指示する。以下、前記の符号化装置の各実施例に対応した復号化装置の実施例を説明する。
【００４５】
《復号化装置の実施例１》
図１６に、本発明の復号化装置の実施例１のブロック構成を示す。本実施例の復号化装置は、図４に関連して説明した符号化装置の実施例１と丁度逆の動作を行うものである。
【００４６】
データ生成部３００は、復号化部３１０と選択部３１１とから構成される。復号化部３１０は、入力する符号をＧ２符号、Ｇ８符号とみなして復号化し、その両方の復号化データを選択部３１１へ出力する。復号化データは、ここではラン長である。選択部３１１は、２つの復号化データより、符号種適応制御部４００より指示された符号種の復号化データを選択して出力する。なお、破線３１２に示すように符号種選択指示を復号化部３１０に与え、復号化部３１０では指示された一方の種類の符号（Ｇ２符号又はＧ８符号）としての復号化だけを行って、復号データを破線３１３に示すように直接外部に出力する構成とすることもでき、この場合は選択部３１１は不要である。復号化データはラン長であるので、逆モデル化部３０１によって２値のビットデータに戻される。
【００４７】
符号種適応制御部４００は、入力データがデータ生成部３００より出力されたラン長であること以外は、前記の符号化装置の実施例１の符号種適応制御部２００と同一の構成である。したがって、その説明は省略する。
【００４８】
なお、符号化装置の説明において述べたように、入力する符号列の最初の部分、例えば６４符号までは、トレーニング期間として、Ｇ２符号又はＧ８符号を連続して使用するか、予め定義した順番で切り替えて使用する。これは下記実施例においても同様である。
【００４９】
《復号化装置の実施例２》
図１７に、本発明の復号化装置の実施例２のブロック構成を示す。本実施例の復号化装置は、図１１に関連して説明した符号化装置の実施例２と丁度逆の動作を行うものである。符号種適応制御部４００は、入力データがデータ生成部３００より出力されたラン長であること以外は、前記の符号化装置の実施例２の符号種適応制御部２００と同一の構成である。したがって、その説明は省略する。
【００５０】
《復号化装置の実施例３》
図１８に、本発明の復号化装置の実施例３のブロック構成を示す。本実施例の復号化装置は、図１２に関連して説明した符号化装置の実施例３と丁度逆の動作を行うものである。符号種適応制御部４００は、入力データがデータ生成部３００より出力されたラン長であること以外は、前記の符号化装置の実施例３の符号種適応制御部２００と同一の構成である。したがって、その説明は省略する。
【００５１】
以上説明した本発明の符号化装置及び復号化装置は、その全体もしくは一部をコンピュータ・プログラムにより実現することも可能であることは明らかである。そのようなコンピュータ・プログラムと、それを記録した各種記録媒体も本発明に包含される。
【００５２】
【発明の効果】
以上の説明から明らかなように、（１）請求項１，２，５，６に記載の発明によれば、近接した過去の符号化対象データにおける各事象の生起確率分布を現在又は近接した将来の符号化時点で使用される符号種の選択に反映させることができ、また、使用させる符号種の決定に鍵情報を利用するため、各事象の生起確率分布の異なる符号化対象データでも、また、符号化対象データ中で各事象の生起確率分布が変動しても、高い符号化効率を得ることができるととも、鍵情報を秘密にしておけば、符号種選択のアルゴリズムが公開されたとしても符号化データの高い秘匿性を得ることができ、また符号化装置の構成も簡易なものにすることができる。（２）請求項３，４に記載の発明によれば、請求項１，２もしくは請求項５，６に記載の符号化装置もしくは方法による符号化データを比較的簡易な装置構成にて復号化することができ、請求項１，２に記載の符号化装置とともに秘匿性のある高効率な符号化・復号化システムを構築できる、等々の効果を得られる。
【図面の簡単な説明】
【図１】本発明による符号化装置の基本的構成を示すブロック図である。
【図２】符号例を示す図である。
【図３】従来技術による符号化例を示す図である。
【図４】本発明による符号化装置の実施例１のブロック図である。
【図５】符号化装置の実施例１における符号種制御のための処理の概要を説明するためのフローチャートである。
【図６】符号化装置の実施例１における符号種制御のタイミングを説明するためのタイムチャートである。
【図７】エントロピーとＧ２選択確率の決定例を示す図である。
【図８】Ｇ符号及びＧ８符号の各事象の符号長と測定したエントロピーを示すグラフである。
【図９】鍵情報の一例を示す図である。
【図１０】符号種の選択例を示す図である。
【図１１】本発明による符号化装置の実施例２のブロック図である。
【図１２】本発明による符号化装置の実施例３のブロック図である。
【図１３】符号化装置の実施例３における符号種制御のための処理の概要を説明するためのフローチャートである。
【図１４】（ａ）鍵情報（重み係数）の例を示す。（ｂ）Ｇ２符号選択確率の推移、各符号化時点での確率差分の拡散値、拡散値を加算後の選択確率、選択された符号種の例を示す。
【図１５】本発明による復号化装置の基本的構成を示すブロック図である。
【図１６】本発明による復号化装置の実施例１のブロック図である。
【図１７】本発明による復号化装置の実施例２のブロック図である。
【図１８】本発明による復号化装置の実施例３のブロック図である。
【符号の説明】
１００  符号生成部
１０１  モデル化部
１１０  符号化部
１１１  選択部
２００  符号種適応制御部
２０１  事象カウント部
２０１ａ  事象カウント部
２０２  エントロピー計算部
２０３  選択確率計算部
２１０  符号種決定部
２１０ａ  符号種決定部
２１１  鍵情報記憶部
２１２  拡散値記憶部
３００  データ生成部
３０１  逆モデル化部
３１０  復号化部
３１１  選択部
４００  符号種適応制御部
【図１】
0004570006.tif 000002
【図２】
0004570006.tif 000003
【図３】
0004570006.tif 000004
【図４】
0004570006.tif 000005
【図５】
0004570006.tif 000006
【図６】
0004570006.tif 000007
【図７】
0004570006.tif 000008
【図８】
0004570006.tif 000009
【図９】
0004570006.tif 000010
【図１０】
0004570006.tif 000011
【図１１】
0004570006.tif 000012
【図１２】
0004570006.tif 000013
【図１３】
0004570006.tif 000014
【図１４】
0004570006.tif 000015
【図１５】
0004570006.tif 000016
【図１６】
0004570006.tif 000017
【図１７】
0004570006.tif 000018
【図１８】
0004570006.tif 000019