(57)【特許請求の範囲】
【請求項１】
クラス数がＫの入力信号を，Ｋより小さいＭのクラス数に量子化する適応量子化方法であって，
入力信号についてクラス数Ｋのヒストグラムを生成するステップと，
与えられたクラス数Ｍで前記ヒストグラムを近似する際に，第ｉ番目（ｉ＝１，２，…，Ｍ−１）のクラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する近似誤差と符号量とを算出し，第１番目のクラスから第ｉ番目のクラスまでの近似誤差と符号量の加重和を最小化する量子化値に対応するクラス境界情報およびそのときの前記加重和の最小値を算出し，メモリに格納するとともに，次の第ｉ＋１番目（ただし，ｉ＜Ｍ−１）のクラス境界の候補に対して前記加重和の最小値を算出する際に，前記格納した第ｉ番目までのクラスに対する最小値をメモリから読み出して前記加重和の最小値の計算に用い，最初のクラスから当該クラスまでの前記加重和を最小化するクラス境界を求める処理を，ｉ＝１からｉ＝Ｍ−１までｉを１ずつ増やしながら繰り返すステップと，
前記メモリに格納された第１番目から第Ｍ−１番目までのクラス境界の候補に対するクラス境界情報および前記加重和の最小値に基づき，クラス境界の全候補に対して近似誤差と符号量の加重和を最小化するクラス境界を選択するステップと，
最終的に選択したクラス境界を用いて入力信号を量子化するステップとを有する
ことを特徴とする適応量子化方法。
【請求項２】
請求項１記載の適応量子化方法において，
前記近似誤差として，クラス数Ｍの各クラスの代表値と当該各クラスにおける入力信号の値との誤差の絶対値和または二乗和，あるいは，クラス数Ｍの各クラスの代表値と当該各クラスにおける入力信号の値に対して視覚感度に基づき重み付けされた値との誤差の絶対値和または二乗和を算出する
ことを特徴とする適応量子化方法。
【請求項３】
請求項１または請求項２記載の適応量子化方法において，
前記近似誤差と符号量との加重和として取り得る値を予め算出してルックアップテーブルに格納し，前記ルックアップテーブルを参照して，前記クラス境界の候補に対する加重和を得る
ことを特徴とする適応量子化方法。
【請求項４】
クラス数がＫの入力信号を，別途，与えられたクラス数の候補から選択されたクラス数に量子化する適応量子化方法であって，
設定された近似誤差と符号量の加重係数を用いて，前記与えられたクラス数の各候補値に対して，請求項１，請求項２または請求項３に記載された適応量子化方法により，量子化代表値およびクラス境界を求め，
かつ，前記加重係数を変化させて前記適応量子化方法を繰り返すことにより，前記加重係数を最適化し，
最適化した加重係数の下で前記適応量子化方法により求めた量子化代表値およびクラス境界を用いた場合の近似誤差を算出し，クラス数の各候補値を用いた場合の近似誤差の中から最小値を求め，
その最小値を実現する量子化代表値およびクラス境界，並びに，その時のクラス数を同定する
ことを特徴とする適応量子化方法。
【請求項５】
請求項４記載の適応量子化方法において，
前記クラス数をＭとして前記近似誤差と符号量の加重係数を変化させた場合の発生符号量の上限値と下限値とから最適化の対象となるクラス数Ｍの上限値と下限値とを算出し，前記クラス数Ｍの上限値と下限値との範囲に限定して，前記クラス数の候補値に対する前記量子化代表値およびクラス境界を求める処理を行う
ことを特徴とする適応量子化方法。
【請求項６】
請求項４または請求項５記載の適応量子化方法において，
前記クラス数の各候補値に対する前記量子化代表値およびクラス境界を求める処理において，クラス数Ｍ−１として量子化代表値およびクラス境界を求めた結果を記憶し，クラス数Ｍの量子化代表値およびクラス境界を求める処理に利用することにより，クラス数Ｍ−１とクラス数Ｍとで重複する演算を省略する
ことを特徴とする適応量子化方法。
【請求項７】
クラス数がＫの入力信号を，Ｋより小さいＭのクラス数に量子化する適応量子化装置であって，
入力信号についてクラス数Ｋのヒストグラムを生成するヒストグラム生成手段と，
与えられたクラス数Ｍで前記ヒストグラムを近似する際に，ｉ＝１からｉ＝Ｍ−１までｉを１ずつ増やしながら順番に，第ｉ番目のクラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する近似誤差を算出する近似誤差算出手段と，
前記クラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する符号量を算出する情報量算出手段と，
第１番目のクラスから第ｉ番目のクラスまでの前記近似誤差と前記符号量との加重和を算出し，第ｉ番目のクラス境界の各候補の中で，算出された前記加重和が最小となるクラス境界情報および加重和の最小値を算出する加重和算出手段と，
前記加重和算出手段によって算出された前記加重和が最小となるクラス境界情報および加重和の最小値を，前記第ｉ番目のクラス境界の各候補ごとに記憶する記憶手段と，
前記記憶手段に記憶された第１番目から第Ｍ−１番目までのクラス境界の候補に対するクラス境界情報および加重和の最小値に基づき，クラス境界の全候補に対して前記加重和を最小化するクラス境界を選択する最適値追跡手段と，
前記最適値追跡手段によって選択されたクラス境界を用いて入力信号を量子化する量子化処理手段とを備え，
前記加重和算出手段は，第ｉ番目のクラス境界の候補に対して前記加重和の最小値を算出する際に，前記記憶手段に記憶された第ｉ−１番目（ただし，ｉ≧２）までのクラスに対する加重和の最小値を読み出し，前記加重和の最小値の計算に用いることで，最初のクラスから当該クラスまでの加重和を最小化するクラス境界を求める
ことを特徴とする適応量子化装置。
【請求項８】
クラス数がＫの入力信号を，別途，与えられたクラス数の候補から選択されたクラス数に量子化する適応量子化装置であって，
入力信号についてクラス数Ｋのヒストグラムを生成するヒストグラム生成手段と，
設定された近似誤差と符号量の加重係数を用いて，前記与えられたクラス数の各候補値Ｍに対して，前記ヒストグラムを近似する際に，ｉ＝１からｉ＝Ｍ−１までｉを１ずつ増やしながら順番に，第ｉ番目のクラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する近似誤差を算出する近似誤差算出手段と，
前記クラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する符号量を算出する情報量算出手段と，
第１番目のクラスから第ｉ番目のクラスまでの前記近似誤差と前記符号量との加重和を算出し，第ｉ番目のクラス境界の各候補の中で，算出された前記加重和が最小となるクラス境界情報および加重和の最小値を算出する加重和算出手段と，
前記加重和算出手段によって算出された前記加重和が最小となるクラス境界情報および加重和の最小値を，前記第ｉ番目のクラス境界の各候補ごとに記憶する記憶手段と，
前記記憶手段に記憶された第１番目から第Ｍ−１番目までのクラス境界の候補に対するクラス境界情報および加重和の最小値に基づき，クラス境界の全候補に対して前記加重和を最小化するクラス境界を選択する最適値追跡手段と，
前記最適値追跡手段によって選択されたクラス境界を用いて入力信号を量子化する量子化処理手段とを備え，
前記加重和算出手段は，第ｉ番目のクラス境界の候補に対して前記加重和の最小値を算出する際に，前記記憶手段に記憶された第ｉ−１番目（ただし，ｉ≧２）までのクラスに対する加重和の最小値を読み出し，前記加重和の最小値の計算に用いることで，最初のクラスから当該クラスまでの加重和を最小化するクラス境界を求め，
前記近似誤差算出手段と，前記情報量算出手段と，前記加重和算出手段と，前記記憶手段と，前記最適値追跡手段とにより，前記与えられたクラス数の各候補値Ｍに対して，前記近似誤差と前記符号量との加重和に用いる加重係数の最適化を行うとともに，最適化した加重係数の下で量子化代表値およびクラス境界を用いた場合の近似誤差を算出し，クラス数の各候補値を用いた場合の近似誤差の中から最小値を求め，その最小値を実現する量子化代表値およびクラス境界，並びに，その時のクラス数を同定する
ことを特徴とする適応量子化装置。
【請求項９】
請求項１から請求項６までのいずれか１項に記載の適応量子化方法を，コンピュータに実行させるための適応量子化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，高能率画像信号符号化の技術に関し，特に符号化効率を向上させるための適応量子化技術に関する。
【背景技術】
【０００２】
非可逆符号化において，量子化は必要不可欠な構成要素である。一般的な符号化方式においては，量子化は符号化データの表現精度を制御し，この制御過程において符号化歪みが発生する。基本的な量子化器の設計は，与えられた歪み量の評価尺度に対して，その評価尺度を最小化するための符号語（量子化インデックス）を求める最小化問題に帰着される。歪み量の評価尺度としては，二乗和，絶対値和が用いられる。
【０００３】
また，一般的な量子化器の設計においては，符号量に関する制約条件が課せられる。この場合，量子化器の設計は，符号量に関する一定の制約条件の下，与えられた歪み量の評価尺度に対して，その評価尺度を最小化するための符号語（量子化インデックス）を求める制約条件付きの最小化問題に帰着される。符号化対象信号の確率密度関数がパラメトリックに表現できる場合には，解析的に最適解を求める手法(analitical optimization) が可能な場合もある。例えば，確率密度関数が，一様分布，ガウス分布，ラプラス分布に従う場合がそれに当たる。しかし，一般的に符号化対象データに対して，そうしたパラメトリックな表現は成立しない。
【０００４】
そこで，計算機上での離散数値演算に基づく最適化手法（operational optimization）が用いられる。代表的な手法が，Ｌｌｏｙｄ−Ｍａｘ量子化法（非特許文献１参照）である。これは，量子化代表値の算出と量子化ビン境界の算出を一定の収束条件まで繰り返す処理である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】S. P. Lloyd,“Least Squares Quantization in PCM ”, IEEE Trans. on Information Theory, Vol. IT-28, No.2, pp.129-136, Mar. 1982
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし，Ｌｌｏｙｄ−Ｍａｘ量子化法は，最適解を得られることが必ずしも保証されていないという問題が指摘されている。これは，Ｌｌｏｙｄ−Ｍａｘ量子化法が，最適量子化の必要条件のみを考慮して設計された手法であることに起因する。このため，繰り返し処理において用いる初期データに依存して，局所解に陥る可能性を含んでいる。
【０００７】
本発明はかかる事情に鑑みてなされたものであって，符号量に関する一定の制約条件が課せられた場合に量子化により発生する近似誤差を最小化する量子化方法を確立することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の適応量子化方法は，上記課題を解決するため，入力信号のヒストグラムに対して，別途，与えられたクラス数で，同ヒストグラムを近似する際に，クラス境界の全候補に対して，近似誤差と符号量の加重和を最小化する量子化値，および，そのときの前記加重和の最小値をメモリに格納し，次のクラスでのクラス境界を選択する際，上記格納した最小値をメモリから呼び出し，その時点でのクラス境界選択における加重和の計算に用いることで，クラス境界の全候補に対して加重和を最小化するクラス境界を選択する。これにより，符号量に関する一定の制約条件の下，量子化により発生する近似誤差を最小化する量子化代表値およびクラス境界（量子化境界）を求めることを特徴とする。
【０００９】
以上により，符号量に関する一定の制約条件が課せられた場合において，量子化により発生する近似誤差の最小化を実現することができる。
【００１０】
また，本発明の適応量子化方法は，入力信号のヒストグラムに対して，別途，与えられたクラス数で，同ヒストグラムを近似する際に，クラス境界の全候補に対して，視覚感度に基づき重み付けされた近似誤差（視覚的近似誤差）と符号量の加重和を最小化する量子化値，および，そのときの前記加重和の最小値をメモリに格納し，次のクラスでのクラス境界を選択する際，上記格納した最小値をメモリから呼び出し，その時点でのクラス境界選択における加重和の計算に用いることで，クラス境界の全候補に対して加重和を最小化するクラス境界を選択する。これにより，符号量に関する一定の制約条件の下，量子化により発生する視覚的近似誤差を最小化する量子化代表値およびクラス境界（量子化境界）を求めることを特徴とする。
【００１１】
以上により，符号量に関する一定の制約条件が課せられた場合において，量子化により発生する視覚的な近似誤差の最小化を実現することができる。
【００１２】
また，本発明の適応量子化方法は，別途，クラス数の候補が与えられた状態で，入力信号のヒストグラムに対して，同ヒストグラムを近似する際に，クラス数の各候補値に対して，適切に設定された近似誤差と情報量の加重係数を用いて，前述した方法により量子化代表値・クラス境界を求め，その量子化代表値・クラス境界を用いた場合の近似誤差を算出し，クラス数の各候補値を用いた場合の近似誤差の中から最小値を求め，その最小値を実現する量子化代表値・クラス境界，および，その時のクラス数を同定することを特徴とする。
【００１３】
以上により，符号量に関する一定の制約条件が課せられた場合において，最適なクラス数を選択し，量子化により発生する近似誤差の最小化を実現することができる。
【００１４】
さらに，クラス数Ｍの最適化において，クラス数をＭとして近似誤差と符号量の加重係数を変化させた場合の発生符号量の上限値と下限値とから最適化の対象となるクラス数Ｍの上限値と下限値とを算出し，クラス数Ｍの上限値と下限値との範囲に限定して，クラス数の候補値に対する量子化代表値およびクラス境界を求める処理を行うことにより，演算量の削減が可能になる。
【００１５】
また，前記クラス数の各候補値に対する量子化代表値およびクラス境界を求める処理において，クラス数Ｍ−１として量子化代表値およびクラス境界を求めた結果を記憶し，クラス数Ｍの量子化代表値およびクラス境界を求める処理に利用することにより，クラス数Ｍ−１とクラス数Ｍとで重複する演算を省略することにより，演算量を削減することができる。
【発明の効果】
【００１６】
本発明により，入力信号の分布に依存することなく，与えられた符号量の制約条件のもとにおいて近似誤差を最小化することが可能となり，量子化を伴う非可逆符号化において，符号化効率を向上させることが可能となる。また，画像信号の階調変換を行う際に発生する変換誤差を最小化することも可能となるため，ビット深度変換を用いた画像符号化器における符号化効率の向上も可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態に係る装置構成例を示す図である。
【図２】本発明の一実施形態に係る適応量子化処理のフローチャートである。
【図３】本発明の一実施形態に係る適応量子化処理のフローチャートである。
【発明を実施するための形態】
【００１８】
以下，本発明の実施の形態について，図面を用いて説明する。
【００１９】
［適応量子化装置の構成例］
図１は，本発明の一実施形態に係る装置構成例を示す図である。
【００２０】
適応量子化装置１０は，レベル数（クラス数ともいう）Ｋの入力信号を入力し，レベル数Ｍ（Ｍ＜Ｋ）に適応的に量子化して，量子化結果の値を出力する装置である。適応量子化装置１０は，入力信号のレベル数Ｋを記憶する入力信号レベル数記憶部１１，量子化後のレベル数Ｍを記憶する量子化後レベル数記憶部１２，与えられた未定乗数λを記憶する未定乗数記憶部１３を備える。
【００２１】
ヒストグラム生成部１４は，入力信号における画素値ｋの頻度をｈ［ｋ］（ｋ＝０，…，Ｋ−１）として格納する。近似誤差算出部１５は，入力信号のヒストグラムｈ［ｋ］に対して，量子化後レベル数記憶部１２に格納されているレベル数Ｍ（クラス数）で，同ヒストグラムを近似するにあたって，ヒストグラムの全区間［０，Ｋ］をＭ個の区間に分割し，各区間を重心（代表値）で近似した場合の近似誤差を，区間幅を変えた各区間の候補について算出する。また，情報量算出部１６は，ヒストグラムの全区間［０，Ｋ］をＭ個の区間に分割し，各区間を重心（代表値）で近似した場合の量子化結果の情報量（符号量）を算出する。
【００２２】
ＲＤコスト算出部１７は，近似誤差算出部１５が算出した近似誤差と，情報量算出部１６が算出した符号量と，未定乗数記憶部１３に記憶されている未定乗数λとから，近似誤差と符号量との加重和（ＲＤコスト）を算出し，先頭の区間から第ｉ番目の区間までの区間の候補の中で，ＲＤコストが最小値となるものをＲＤコスト最小値記憶部１８に記憶する。このとき，第ｉ番目までの区間のＲＤコストの最小値の算出では，第ｉ−１番目までの区間のＲＤコストの最小値を利用する。また，ＲＤコスト算出部１７は，区間上端最適値記憶部１９にＲＤコストが最小となる区間の上端（クラス境界）の値を記憶する。
【００２３】
区間上端最適値追跡部２０は，区間上端最適値記憶部１９に記憶された区間の上端の値から，クラス境界の全候補に対してＲＤコストを最小化するクラス境界を選択する。量子化処理部２１は，区間上端最適値追跡部２０が選択したクラス境界をもとに，入力信号を量子化レベル数Ｍで量子化し，量子化結果の量子化値を出力する。
【００２４】
［適応量子化処理の流れ（基本処理）］
図２および図３は，本発明の一実施形態に係る適応量子化処理のフローチャートである。
【００２５】
まず，適応量子化装置１０は，量子化後のクラス数Ｍを入力し，量子化後レベル数記憶部１２に記憶し，また，未定乗数λを未定乗数記憶部１３に記憶する。ヒストグラム生成部１４は，入力信号レベル数記憶部１１に記憶されているクラス数Ｋに従って，入力信号のヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）を算出する（ステップＳ１０）。ＲＤコスト算出部１７は，ＲＤコスト最小値記憶部１８の近似誤差と符号量の加重和（ＲＤコスト）の最小値を０に初期化する（ステップＳ１１）。
【００２６】
その後，量子化後のレベルｍについて，ｍ＝１からｍ＝Ｍ−１まで，ｍの値を１ずつ増やしながら，近似誤差算出部１５，情報量算出部１６およびＲＤコスト算出部１７により，ステップＳ２４までの処理を繰り返す（ステップＳ１２）。この処理のループでは，さらに量子化レベルｍを表す区間の上端Ｌm の各候補に対して，Ｌm ＝ｍからＬm ＝Ｋ−（Ｍ−ｍ）まで，Ｌm を１ずつ増やしながら，ステップＳ２３までの処理を繰り返す（ステップＳ１３）。なお，Ｌ0 は予め０に初期化しておく。
【００２７】
また，さらに量子化レベルｍを表す区間の区間幅Δm の各候補に対して，Δm ＝１からΔm ＝Ｌm −（ｍ−１）まで，Δm を１ずつ増やしながら，ステップＳ２０までの処理を繰り返す（ステップＳ１４）。
【００２８】
近似誤差算出部１５は，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］の代表値を算出し（ステップＳ１５），そのヒストグラムの区間を代表値で近似した場合の近似誤差を算出する（ステップＳ１６）。一方，情報量算出部１６は，そのヒストグラムの区間を代表値で近似した場合に発生する符号量を算出する（ステップＳ１７）。
【００２９】
ＲＤコスト算出部１７は，近似誤差算出部１５が算出した近似誤差と，情報量算出部１６が算出した符号量と，未定乗数記憶部１３に記憶されている未定乗数とから，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値で近似した場合の近似誤差と符号量との加重和（ＲＤコスト）を算出する（ステップＳ１８）。続いて，ＲＤコスト算出部１７は，一つ前の区間までに算出されたＲＤコスト最小値記憶部１８に記憶されているＲＤコストの最小値と，ステップＳ１８で算出した現在の区間のＲＤコストの和を算出して記憶する（ステップＳ１９）。次にステップ１４に戻り，区間幅Δm の最終の候補の処理が終えるまで，ステップＳ１４〜Ｓ２０の処理を繰り返す。
【００３０】
区間幅Δm の全候補について処理したならば，区間幅Δm の候補の中で，現在の区間までのＲＤコストが最小となる値をＲＤコスト最小値記憶部１８に記憶する（ステップＳ２１）。また，区間の上端Ｌm に対してＲＤコストを最小化する区間情報（区間幅Δm ，区間の上端Ｌm など）を区間上端最適値記憶部１９に記憶する（ステップＳ２２）。
【００３１】
以上の処理を上端Ｌm のすべての候補に対して行い（ステップＳ２３），また，全レベルｍ（ｍ＝Ｍ−１まで）について繰り返す（ステップＳ２４）。以上の処理が終了したならば，区間上端最適値追跡部２０は，全体の近似誤差を最小化する区間情報（クラス境界）を区間上端最適値記憶部１９から選出し，選出したクラス境界の情報を量子化処理部２１に出力する（ステップＳ２５）。
【００３２】
量子化処理部２１は，区間上端最適値追跡部２０が出力したクラス境界に従って，入力信号を量子化することにより，近似誤差（変換誤差）と符号量の加重和が最小となる量子化値を出力することができる。
【００３３】
以上の処理において，視覚感度特性を考慮した重み付き歪み量の最小化を図る実施例も好適である。視覚感度特性を考慮した重み付き歪み量の最小化を図る場合，ステップＳ１６における近似誤差の算出では，視覚感度に基づき重み付けされた近似誤差を計算する。例えば，画素値ｋ（ｋ＝０，…，Ｋ−１）に対して，輝度差に対する視覚特性に基づく重み係数ｗ［ｋ］を設定し，画素値ｋに対する頻度ｈ［ｋ］に重み係数ｗ［ｋ］を乗算した値を用いて，近似誤差（視覚的近似誤差）を算出する。
【００３４】
また，区間幅Δm の範囲を制限した準最適化法を適用する場合には，ステップＳ１４において，各Δm を変化させる場合に，予め設定された最大値Ａの範囲内で，すなわち，１≦Δm ≦Ａの範囲内で各Δm に対する近似誤差の最小値を計算することにより本発明を実施することもできる。
【００３５】
図１の例では，量子化レベル数（クラス数）Ｍが予め定められているとしたが，このクラス数を可変として，本発明による適応量子化を行うこともできる。この場合，別途与えられたクラス数の各候補値に対して，適切に設定された近似誤差と情報量の加重係数を用いて，図２および図３で説明した処理により，量子化代表値・クラス境界を求め，その量子化代表値およびクラス境界を用いた場合の近似誤差を算出し，クラス数の各候補値を用いた場合の近似誤差の中から最小値を求め，その最小値を実現する量子化代表値・クラス境界，および，その時のクラス数を同定する。
【００３６】
さらに詳しく，本発明の実施の形態について説明する。
【００３７】
［基本解法］
画素値ｋの頻度をｈ［ｋ］（ｋ＝０，…，Ｋ−１）として格納する。例えば，８ビットの輝度信号の場合，ｋの取り得る範囲は０から２５５の値となる。このＫ階調の信号をＭ階調（Ｍ＜Ｋ）に量子化する場合を考える。
【００３８】
ヒストグラムの量子化を表現するパラメータとして，次の２種類（Δm とＬm ）を導入する。Δm はヒストグラムの第ｍ区間の区間幅を表す。さらに，Ｌm はヒストグラムにおける第ｍ区間の上端であり，次式で定義されるものとする。  
【００３９】
【数１】
0005426506.tif 000002
【００４０】
なお，量子化後の各階調が，少なくとも１つ以上，量子化前の階調を含む必要があることから，Ｌm （０≦ｍ≦Ｍ−２）は以下の範囲に制限される。
【００４１】
ｍ≦Ｌm ≦Ｋ−（Ｍ−ｍ）
以下，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を第ｍ量子化ビンと呼ぶ。
【００４２】
量子化においては，歪み量と符号量の２種類を考慮する必要がある。まず，歪み量としては，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値ｃ（Ｌm −（Δm −１），Ｌm ）で近似した場合の近似誤差として，次式で表されるｅ（Ｌm −（Δm −１），Ｌm ）を用いる。
【００４３】
【数２】
0005426506.tif 000003
【００４４】
ｃ（Ｌm −（Δm −１），Ｌm ）は，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］における重心位置を表し，次式で定まる。
【００４５】
【数３】
0005426506.tif 000004
【００４６】
次に，符号量としては，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値ｃ（Ｌm −（Δm −１），Ｌm ）で近似した場合の代表値を表現するために必要な情報量として，次式で表されるｌ（Ｌm −（Δm −１），Ｌm ）を用いる。
【００４７】
【数４】
0005426506.tif 000005
【００４８】
ここで，ｐ（Ｌm , Δm ）は，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］における頻度が全頻度に占める割合であり，次式で定義される。
【００４９】
【数５】
0005426506.tif 000006
【００５０】
ここで必要なことは，量子化の符号量が一定の閾値以下という条件下で歪み量を最小化することである。つまり，求めるべきパラメータ（Δ0 ，…，ΔM-1 ）は，
【００５１】
【数６】
0005426506.tif 000007
【００５２】
上式を満たす条件下において，次式を最小化するものである。
【００５３】
【数７】
0005426506.tif 000008
【００５４】
こうした制約条件付き最小化問題は，ラグランジュの未定乗数法により，未定乗数λを導入することで，制約条件のない最小化問題に変形できる。つまり，求めるべきパラメータは，次式を満たすＭ個のパラメータとなる。
【００５５】
【数８】
0005426506.tif 000009
【００５６】
ここで，ψ（Ｌm −（Δm −１），Ｌm , λ）は，次式で定義される評価尺度（ＲＤコストと呼ぶ）である。
【００５７】
ψ（Ｌm −（Δm −１），Ｌm , λ）
＝ｅ（Ｌm −（Δm −１），Ｌm ）＋λ・ｌ（Ｌm −（Δm −１），Ｌm ）    (8) 
Ｍ個のパラメータ（Δ0 ，…，ΔM-1 ）の取り得る組み合わせは，Ｍとともに指数関数的に増加するため，この中から最適な組み合わせ（Δ0 * ，…，ΔM-1 * ）を総当りで探索するのは，計算量的に困難である。
【００５８】
そこで，第ｍ量子化ビンのＲＤコストψ（Ｌm −（Δm −１），Ｌm , λ）が同ビンの上端Ｌm と同ビンの区間幅Δm に依存することに着目し，以下のように最適解を算出する。まず，ヒストグラムの区間［０, Ｌm ］をｍ＋１分割した際のＲＤコストの総和
Σi=0 m ψ（Ｌi −（Δi −１），Ｌi ，λ）
の最小値をＳm （Ｌm ）として定義する。つまり，最適なΔm ，…, Δ0 を用いた場合のΣi=0 m ψ（Ｌi −（Δi −１），Ｌi ，λ）に対する最小値である。
【００５９】
ここで，ψ（Ｌm −（Δm −１），Ｌm , λ）が第ｍ量子化ビンの上端Ｌm と同ビンの区間幅Δm に依存することに着目すると，Ｓm （Ｌm ）はＳm-1 （Ｌm −Δm ）を用いて，次式のように表わされる。
【００６０】
【数９】
0005426506.tif 000010
【００６１】
なお，ｍ＝０，…，Ｍ−１である。また，Ｌm ＝ｍ，…，Ｋ−（Ｍ−ｍ）である。
【００６２】
Δm の取り得る範囲について考察する。Ｌm-1 ＝Ｌm −Δm であることから，Ｌm −Δm の範囲は，ｍ−１≦Ｌm −Δm ≦Ｋ−（Ｍ−ｍ＋１）となる。このため，Δm の範囲  は，与えられたＬm を用いて次式のように表される。
【００６３】
Ｌm −Ｋ＋（Ｍ−ｍ＋１）≦Δm ≦Ｌm −ｍ＋１                (10)
さらに，Δm ≧１であることを考慮すると，次式を得る。
【００６４】
１≦Δm ≦Ｌm −ｍ＋１                                      (11)
次式のように，Δm の最大値をＡに制限することで，演算量の削減を図るアプローチも採ることができる。ただし，この場合，解の最適性は保証されない。
【００６５】
１≦Δm ≦Ａ                                                (12)
ここで，算出したＳm （Ｌm ）を格納しておき，Ｓm+1 （Ｌm+1 ）の計算で用いるものとする。さらに，式(9) の最小値を与えるＬm-1 を＾Ｌm-1 （Ｌm ）とおく（なお，＾はＬの上に付く記号。他も同様）。この＾Ｌm-1 （Ｌm ）（ｍ≦Ｌm ≦Ｋ−（Ｍ−ｍ））も，全て格納しておくものとする。
【００６６】
Ｓm-1 （Ｌm-1 ）（Ｌm-1 ＝ｍ−１，…，Ｋ−Ｍ＋ｍ−１）は，同様の漸化式を用いて算出可能であり，その算出値は，Ｓm （Ｌm ）の計算に用いられる。漸化式(9) を用いることで，Ｓm （Ｌm ）の計算は，Δm ＝１，…，Ｌm −ｍ＋１からの最適なパラメータ選択問題に帰着させられる。式(9) の右辺を最小化するΔm の値を＾Δm （Ｌm ）として，各Ｌm （＝ｍ，…，Ｋ−Ｍ＋ｍ）に対して，＾Ｌm-1 （Ｌm ）＝Ｌm −＾Δm （Ｌm ）をメモリに格納しておくものとする。
【００６７】
式(6) の最小化問題は，次式のように表される。
【００６８】
【数１０】
0005426506.tif 000011
【００６９】
式(9) および式(1) におけるＬM-1 ＝Ｋ−１を用いて，式(6) の最小化問題は，（Ｋ−Ｍ）×（１＋Ｋ−Ｍ）×（Ｍ−１）／２個の候補の中から最適解（Δ0 * ，…，ΔM-1 * ）を求める最適化問題に帰着される。このように，本方式による方法は，多項式時間での最適解の求解を可能とする。式(13)の
ＳM-2 （ＬM-1 −ΔM-1 ）＋ψ（ＬM-1 −（ΔM-1 −１），ＬM-1 ，λ）
の最小値を求めた後，最適解（Δ0 * ，…，ΔM-1 * ）は，バックトラック過程を通して，求めることができる。次式に示す通り，式(13)の最小化問題の解をΔM-1 * とおく。
【００７０】
【数１１】
0005426506.tif 000012
【００７１】
このΔM-1 * を用いて，第Ｍ−２ビンの上端の最適値は，
ＬM-2 * ＝ＬM-1 −ΔM-1 * ＝Ｋ−１−ΔM-1 * 
と求まる。第Ｍ−３ビンの上端の最適値は，ＬM-2 * に対する最適解として，＾ＬM-3 （ＬM-2 * ）として格納されているので，該当する値を参照し，ＬM-3 * ＝＾ＬM-3 （ＬM-2 * ）とする。この結果，第Ｍ−２ビンの区間幅は，ΔM-2 * ＝ＬM-2 * −ＬM-3 * と求まる。以下，同様の参照処理を
ＬM-4 * ＝＾ＬM-4 （ＬM-3 * ），…，Ｌ1 * ＝＾Ｌ1 （Ｌ2 * ）
として繰り返し，得られた各ビンの上端値を用いて，
ΔM-3 * ＝ＬM-3 * −ＬM-4 * ，…，Δ1 * ＝Ｌ1 * −Ｌ0 * ，Δ0 * ＝Ｌ0 * ＋１
として求める。
【００７２】
［適応量子化アルゴリズム（基本形）］
以上の適応量子化の基本的な処理手順は，以下のとおりである。
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．量子化後のクラス数Ｍを読み込む。
３．Ｓ0 （ｉ）←０（ｉ＝０，…，Ｋ−Ｍ）とする。
４．ｆｏｒ  ｍ＝０，…，Ｍ−１    （処理４〜１２のループ）
５．  ｆｏｒ  ＬM ＝ｍ，…，Ｋ−（Ｍ−ｍ）    （処理５〜１２のループ）
６．  ただし，ｍ＝Ｍ−１の場合には，Ｌm ＝Ｋ−１に限定
７．    ｆｏｒ  Δm ＝１，…，Ｌm −（ｍ−１）    （処理７〜１０のループ）
８．    ただし，ｍ＝０の場合には，Δm ＝Ｌm ＋１に限定
９．      ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値で近似した場合のＲＤコストを求める。ＲＤコストは式(8) により求め，そのＲＤコストをψ（Ｌm −（Δm −１），Ｌm ，λ）に格納する。
１０．      Ｓm-1 （Ｌm −Δm ）＋ψ（Ｌm −（Δm −１），Ｌm , λ）の値を計算する。
１１．      Ｓm-1 （Ｌm −Δm ）＋ψ（Ｌm −（Δm −１），Ｌm , λ）（Δm ＝１，…，Ｌm −（ｍ−１））の中での最小値をＳm （Ｌm ）に格納する。
１２．      Ｓm-1 （Ｌm −Δm ）＋ψ（Ｌm −（Δm −１），Ｌm , λ）（Δm ＝１，…，Ｌm −（ｍ−１））を最小化するΔm を用いて，Ｌm −Δm を＾Ｌm-1 （Ｌm ）に格納する。
１３．ＬM-1 * ←Ｋ−１
１４．ｆｏｒ  ｍ＝Ｍ−１，…，１    （処理１４〜１６のループ）
１５．  ＾Ｌm-1 （Ｌm * ）を読み込み，Ｌm-1 * ←＾Ｌm-1 （Ｌm * ）とする。
１６．  Δm * ←Ｌm * −Ｌm-1 * 
１７．Δ0 * ←Ｌ0 * ＋１
以上により，区間幅Δm * （ｍ＝０，…，Ｍ−１）が定まり，クラス境界（量子化境界）が決定される。
【００７３】
［未定乗数の設定法］
未定乗数λの設定法について説明する。２つの未定乗数λl ，λu を準備する。なお，この未定乗数は，以下の条件を満たすように設定されるものとする。量子化ビン数をＭとし，未定乗数λu およびλl が与えられた場合，前述した適応量子化アルゴリズムにより生成されるパラメータの情報量和を各々，Ｒ（ΔM * （λu ），λu ），Ｒ（ΔM * （λl ），λl ）とすると，次式を満たす。
【００７４】
Ｒ（ΔM * （λu ），λu ）≦Ｒ0 ≦Ｒ（ΔM * （λl ），λl ）
未定乗数として，
λ＝（λl ＋λu ）／２                            (15)
を設定し，同未定乗数を用いて上記［適応量子化アルゴリズム（基本形）］を実行する。そこで生成されるパラメータの情報量和Ｒ（ΔM * （λ），λ）を求める。
【００７５】
得られたＲ（ΔM * （λ），λ）の値に基づき，以下のような処理を行う。
（ｉ）Ｒ0 −ε≦Ｒ（ΔM * （λ），λ）≦Ｒ0 の場合：
λを未定乗数として設定する。εは十分小さな正の数である。Ｒ（ΔM * （λ），λ）＝Ｒ0 を評価したいのであるが，実数値の場合，等式の評価は計算精度の観点から難しいため，ここで用いるような不等式の評価を用いる。
（ii）Ｒ（ΔM * （λ），λ）＞Ｒ0 の場合：
λl ←λとして，式(15)以降の処理を繰り返す。
【００７６】
(iii)  Ｒ（ΔM * （λ），λ）＜Ｒ0 −εの場合：
λu ←λとして，式(15)以降の処理を繰り返す。
【００７７】
［未定乗数の設定アルゴリズム］
以上の未定乗数の設定アルゴリズムをまとめると，以下のようになる。
１．量子化ビン数Ｍを読み込む。
２．情報量の上限Ｒ0 を読み込む。
３．次式を満たす未定乗数λl , λu を準備する。
【００７８】
Ｒ（ΔM * （λu ），λu ）≦Ｒ0 ≦Ｒ（ΔM * （λl ），λl ）
４．未定乗数として，λ＝（λl ＋λu ）／２を設定する。
５．未定乗数λを用いて，上記［適応量子化アルゴリズム（基本形）］を実行する。
６．前の処理５で生成されるパラメータの情報量和Ｒ（ΔM * （λ），λ）を求める。
７．ｉｆ  Ｒ0 −ε≦Ｒ（ΔM * （λ），λ）≦Ｒ0 の場合：
λを未定乗数として設定する。
８．ｉｆ  Ｒ（ΔM * （λ），λ）＞Ｒ0 の場合：
λl ←λとして，処理４へ戻る。
９．ｉｆ  Ｒ（ΔM * （λ），λ）＜Ｒ0 −εの場合：
λu ←λとして，処理４へ戻る。
【００７９】
［量子化ビン数の設定法（基本解法）］
上記適応量子化の例では，量子化ビン数Ｍが外部から与えられるものとして説明したが，次に，量子化ビン数を可変とした場合の量子化ビン数Ｍの設定法について説明する。量子化ビン数Ｍが取り得る値をＢl ≦Ｍ≦Ｂu とし，量子化ビン数Ｍ（Ｂl ≦Ｍ≦Ｂu ）の各々について，前述した［未定乗数の設定アルゴリズム］に基づき，最適な未定乗数を求める。量子化ビン数がＭの場合に求まる未定乗数をλM * とおく。
【００８０】
Ｍ＝Ｂl ，…，Ｂu に対して，未定乗数λM * を用いた場合の近似誤差和Ｄ（ΔBl *（λBl* ），λBl* ），…，Ｄ（ΔBu* （λBu* ），λBu* ）を求め，近似誤差和が最小となる量子化ビン数を最適な量子化ビン数とする。つまり，次式を満たすＭ* を求める。
【００８１】
Ｄ（ΔM* *（λM** ），λM** ）＜Ｄ（ΔM * （λM * ），λM * ）
ｆｏｒ  ａｌｌ  Ｍ≠Ｍ* 
［量子化ビン数の設定アルゴリズム］
量子化ビン数の設定アルゴリズムは，以下のとおりである。
１．情報量の上限Ｒ0 を読み込む。
２．ｆｏｒ  Ｍ＝Ｂl ，…，Ｂu   （処理２−１〜２−２のループ）
２−１．［未定乗数の設定アルゴリズム］を実行し，最適な未定乗数λM * および同未定乗数に対する量子化パラメータΔM * （λM * ）を求める。
２−２．前の処理２−１で求めた量子化パラメータΔM * （λM * ）を用いた場合の近似誤差和Ｄ（ΔM * （λM * ），λM * ）を＾Ｄ［Ｍ］に格納する。
３．＾Ｄ［Ｍ］（Ｍ＝Ｂl ，…，Ｂu ）の中で最小値を返すＭ* を求め，このＭ* に対する量子化パラメータΔM** （λM** ）を出力する。
【００８２】
［量子化ビン数の設定法（低演算量解法）］
量子化ビン数Ｍが取り得る値をＢl ≦Ｍ≦Ｂu とし，量子化ビン数Ｍ（Ｂl ≦Ｍ≦Ｂu ）が与えられた場合，最適な未定乗数の算出が不要となる量子化ビン数については，同算出処理を省略するアプローチを採る。
【００８３】
ここでは，量子化ビン数をＭとして，λを変化させた場合の発生符号量の上限値・下限値を考察する。式(7) をλの関数と見た場合，発生符号量の上限を与えるのは，λ＝０とした場合，つまり，コスト関数として歪み量のみを用いた場合である。これは，量子化ビン数をＭとして，以下の最小化問題を解いた場合に当たる。
【００８４】
【数１２】
0005426506.tif 000013
【００８５】
一方，発生符号量の下限を与えるのは，λ＝＋∞とした場合，つまり，コスト関数として符号量のみを用いた場合である。量子化ビン数をＭとして，以下の最小化問題を解いた場合に当たる。
【００８６】
【数１３】
0005426506.tif 000014
【００８７】
上記の最小化問題を解くことで求まる発生符号量の上限・下限を各々Ｒu （Ｍ），Ｒl （Ｍ）とおく。Ｒu （Ｍ），Ｒl （Ｍ）は，いずれも量子化ビン数Ｍに対する非減少関数である。これは，量子化ビン数として大きな値を設定すれば，発生符号量も増加するためである。また，上限・下限として設定したことから，Ｒl （Ｍ）≦Ｒu （Ｍ）である。
【００８８】
ここで，まず，Ｒl （Ｍ）≦Ｒ0 を満たすＭの最大値をＭupper とする。Ｒl （Ｍ）のＭに対する非減少性から，Ｍupper ≦Ｍを満たすＭの場合，発生符号量がＲ0 以下となる制約条件を満たすことができない。このため，λの設定を含めた最適化の対象は，Ｍ≦Ｍupper を満たすＭに限定しても最適性は保証される。
【００８９】
次に，Ｒu （Ｍ）≦Ｒ0 を満たすＭの最大値をＭlower とする。発生符号量のＭに対する非減少性から，Ｍ＜Ｍlower を満たすＭの場合，制約条件は必ず満足する。一方，量子化歪みのＭに対する非増加性から，Ｍ＜Ｍlower を満たすＭの場合，Ｍ＝Ｍlower の場合以上に，符号化歪みを低減できない。このため，λの設定を含めた最適化の対象は，Ｍlower ≦Ｍを満たすＭに限定しても最適性は保証される。そこで，
ｍａｘ（Ｂl ，Ｍlower ）≦Ｍ≦ｍｉｎ（Ｂu ，Ｍupper ）
を満たすＭに限定して，前述した未定乗数の設定のアルゴリズムに基づき，最適な未定乗数を求める。ここで，ｍａｘ（）は２つの引数のうち，大きい方の値を返す関数であり，ｍｉｎ（）は２つの引数のうち，小さい方の値を返す関数である。
【００９０】
量子化ビン数がＭの場合に求まる未定乗数をλM * とおく。Ｍ＝Ｂl ，…，Ｂu に対して，未定乗数λM * を用いた場合の近似誤差和Ｄ（ΔBl *（λBl* ），λBl* ），…，Ｄ（ΔBu* （λBu* ），λBu* ）を求め，近似誤差和が最小となる量子化ビン数を最適な量子化ビン数とする。つまり，次式を満たすＭを求める。
【００９１】
Ｄ（ΔM* *（λM** ），λM** ）＜Ｄ（ΔM * （λM * ），λM * ）
ｆｏｒ  ａｌｌ  Ｍ≠Ｍ* 
＜Ｍupper , Ｍlower の設定に際しての演算量低減法＞
Ｍupper の設定においては，コスト関数をｅ（）として，各量子化ビン数に対する最適コスト値を算出する。これは，式(8) のＲＤコストにおいて，λ＝０と設定した場合に相当する。一方，Ｍlower の設定においては，コスト関数をｌ（）として，各量子化ビン数に対する最適コスト値を算出する。これは，式(8) のＲＤコストにおいて，λとしては，λ＝＋∞と設定した場合に相当する。
【００９２】
上記はいずれも共通のλを用いた場合に，異なる量子化ビン数に対する最適化を行う問題といえる。この場合，異なる量子化ビン数で重複した計算過程があることに着目することで，演算量を低減可能である。Ｍlower およびＭupper の具体的な処理手順を，以下に示す。
【００９３】
［Ｍlower の算出アルゴリズム］
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．Ｍlower ←Ｂl 
３．λ＝０，Ｍ＝Ｂl として，［適応量子化アルゴリズム］の処理を行い，＾Ｌm-1 （Ｌm ）の値をルックアップテーブルＴ［ｍ，Ｌm ］に格納し，さらに，Ｓm （Ｌm ）の値を別のルックアップテーブルΦBl［ｍ, Ｌm ］に格納する。
４．Ｒ（ΔBl* （０），０）≧Ｒ0 であれば処理を終了する。そうでなければ，次の処理へ進む。
５．ｆｏｒ  ＾Ｍ＝Ｂl ＋１，…，Ｂu     （処理５〜９のループ）
６．  Ｍ＝＾Ｍとして，ルックアップテーブルＴ［］およびルックアップテーブルΦ＾M-1 ［］を読み込み，後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］の処理を実施する。
７．  生成されるパラメータの情報量の和Ｒ（ΔM * （０），０）を求める。
８．  Ｒ（ΔM * （０），０）≧Ｒ0 であれば，Ｍlower ←＾Ｍ−１として，処理を終了する。そうでなければ，次の処理９へ進む。
９．  ルックアップテーブルＴ［］を更新し，ルックアップテーブルΦ＾M ［］を出力する。
【００９４】
［Ｍupper の算出アルゴリズム］
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．Ｍupper ←Ｂu 
３．λ＝λ+max，Ｍ＝Ｂl として，［適応量子化アルゴリズム］の処理を行い，＾Ｌm-1 （Ｌm ）の値をルックアップテーブルＴ［ｍ，Ｌm ］に格納し，さらに，Ｓm （Ｌm ）の値を別のルックアップテーブルΦBl［ｍ，Ｌm ］に格納する。ここで，λ+maxは十分大きな値とする。
４．Ｒ（ΔBu* （λ+max），λ+max）≧Ｒ0 であれば，処理を終了する。この場合，与えられた制約条件を満たす解がないことになる。そうでなければ，次の処理５へ進む。
５．ｆｏｒ  ＾Ｍ＝Ｂl ＋１，…，Ｂu     （処理５〜９のループ）
６．  Ｍ＝＾Ｍとして，ルックアップテーブルＴ［］およびルックアップテーブルΦ＾M-1 ［］を読み込み，後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］の処理を実施する。
７．  生成されるパラメータの情報量の和Ｒ（ΔM * （λ+max），λ+max）を求める。
８．  Ｒ（ΔM * （λ+max），λ+max）≧Ｒ0 であれば，Ｍupper ←＾Ｍ−１として，処理を終了する。そうでなければ，次の処理９へ進む。
９．  ルックアップテーブルＴ［］を更新し，ルックアップテーブルΦ＾M ［］を出力する。
【００９５】
＜最適ビン数の算出方法＞
Ｍupper の設定においては，コスト関数をｅ（）として，各量子化ビン数に対する最適コスト値を算出する。これは，式(8) のＲＤコストにおいて，λ＝０と設定した場合に相当する。一方，Ｍlower の設定においては，コスト関数をｌ（）として，各量子化ビン数に対する最適コスト値を算出する。これは，式(8) のＲＤコストにおいて，λとしては，λ＝＋∞と設定した場合に相当する。
【００９６】
［量子化ビン数の設定アルゴリズム（低演算量タイプ）］
低演算量タイプの量子化ビン数の設定アルゴリズムを，以下に示す。
１．情報量の上限Ｒ0 を読み込む。
２．前述した［Ｍlower の算出アルゴリズム］によりＭlower を求める。
３．前述した［Ｍupper の算出アルゴリズム］によりＭupper を求める。
４．ｆｏｒ  Ｍ＝ｍａｘ（Ｂl ，Ｍlower ），…，ｍｉｎ（Ｂu ，Ｍupper ）
（処理４−１〜４−２の繰り返し）
４−１．Ｍ＞ｍａｘ（Ｂl ，Ｍlower ）の場合には，λM-1 * を未定乗数の初期値として入力して，下記に示す［未定乗数の設定アルゴリズム（継承型）］を実行し，最適な未定乗数λM * および同未定乗数に対する量子化パラメータΔM * （λM * ）を求める。
【００９７】
Ｍ＝ｍａｘ（Ｂl ，Ｍlower ）の場合には，［未定乗数の設定アルゴリズム］を実行し，最適な未定乗数λM * および同未定乗数に対する量子化パラメータΔM * （λM * ）を求める。
４−２．前の処理４−１で求めた量子化パラメータΔM * （λM * ）を用いた場合の近似誤差和Ｄ（ΔM * （λM * ），λM * ）を，＾Ｄ［Ｍ］に格納する。
５．＾Ｄ［Ｍ］（Ｍ＝Ｂl ，…，Ｂu ）の中で最小値を返すＭを求め，このＭに対する量子化パラメータΔM** （λM** ）を出力する。
【００９８】
［未定乗数の設定アルゴリズム（継承型）］
上記処理４−１で用いる未定乗数の設定アルゴリズム（継承型）の手順は，以下のとおりである。
１．量子化ビン数Ｍを読み込む。
２．情報量の上限Ｒ0 を読み込む。
３．未定乗数λの初期値，および，その上限値λu を読み込む。
４．未定乗数として，λ＝（λl ＋λu ）／２を設定する。
５．未定乗数λを用いて後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］を実行する。
６．処理５で生成されるパラメータの情報量和Ｒ（ΔM * （λ），λ）を求める。
７．ｉｆ  Ｒ0 −ε≦Ｒ（ΔM * （λ），λ）≦Ｒ0 の場合：
λu を未定乗数として設定する。
８．未定乗数λu を用いて，後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］を実行する。
９．処理８で生成されるパラメータの情報量和Ｒ（ΔM * （λu ），λu ）を求める。
１０．  ｉｆ  Ｒ0 −ε≦Ｒ（ΔM * （λu ），λu ）≦Ｒ0 の場合：
λu を未定乗数として設定する。
１１．  ｉｆ  Ｒ（ΔM * （λu ），λu ）＞Ｒ0 の場合：
λ←２λu として，処理５へ戻る。
１２．  ｉｆ  Ｒ（ΔM * （λu ），λu ）＜Ｒ0 −εの場合：
λl ←λとして，処理４へ戻る。
１３．  ｉｆ  Ｒ0 −ε≦Ｒ（ΔM * （λl ），λl ）≦Ｒ0 の場合：
λl を未定乗数として設定する。
１４．  ｉｆ  Ｒ（ΔM * （λl ），λl ）＞Ｒ0 の場合：
λu ←λとして，処理４へ戻る。
１５．  ｉｆ  Ｒ（ΔM * （λl ），λl ）＜Ｒ0 −εの場合：
λ←λu ／２として，処理５へ戻る。
【００９９】
以上が未定乗数の設定アルゴリズム（継承型）である。
【０１００】
上記はいずれも共通のλを用いた場合に，異なる量子化ビン数に対する最適化を行う問題といえる。この場合，異なる量子化ビン数で重複した計算過程があることに着目することで，演算量を低減可能である。その具体的な処理手順を以下に示す。
【０１０１】
［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］
以下の適応量子化アルゴリズムでは，Ｍ−１ビンの量子化の結果を用いて，Ｍビンの量子化を算出する場合の例である。なお，ここで説明を簡単にするために，３≦Ｍを対象とする。
１．入力信号のヒストグラム（クラス数Ｋ）を読み込む。
２．量子化後のクラス数Ｍを読み込む。
３．ｆｏｒ  ｍ＝０，…，Ｍ−３    （処理３〜６のループ）
４．  ｆｏｒ  Ｌm ＝ｍ，…，Ｋ−（Ｍ−ｍ）    （処理４〜６のループ）
５．  ΦM ［ｍ，Ｌm ］←ΦM-1 ［ｍ，Ｌm ］
６．  Ｌm −Δm を＾Ｌm-1 （Ｌm ）に格納する。
７．ｆｏｒ  ｍ＝Ｍ−２，Ｍ−１    （処理７〜１６のループ）
８．  ｆｏｒ  Ｌm ＝ｍ，…，Ｋ−（Ｍ＋１−ｍ）    （処理８〜１６ループ）
９．ただし，ｍ＝Ｍ−１の場合には，Ｌm ＝Ｋ−１に限定
１０．  ｆｏｒ  Δm ＝１，…，Ｌm −（ｍ−１）    （処理１０〜１６のループ）
１１．    ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値で近似した場合のＲＤコストを求める。ＲＤコストは式(8) により求め，そのＲＤコストをψ（Ｌm −（Δm −１），Ｌm , λ）に格納する。
１２．    Φm-1 （Ｌm −Δm ）＋ψ（Ｌm −（Δm −１），Ｌm , λ）の値を計算する。
１３．    Φm-1 （Ｌm −Δm ）＋ψ（Ｌm −（Δm −１），Ｌm , λ）（Δm ＝１，…，Ｌm −（ｍ−１））の中での最小値をＳm （Ｌm ）に格納する。
１４．    ΦM+1 ［ｍ，Ｌm ］←Φm （Ｌm ）（ｍ＝Ｍ−１の場合には，省略）
１５．    Φm-1 （Ｌm −Δm ）＋ψ（Ｌm −（Δm −１），Ｌm , λ）（Δm ＝１，…，Ｌm −（ｍ−１））を最小化するΔm を用いて，Ｌm −Δm を＾Ｌm-1 （Ｌm ）に格納する。
１６．    Ｔ［ｍ，Ｌm ］←＾Ｌm-1 （Ｌm ）
１７．ＬM * ←Ｋ−１
１８．ｆｏｒ  ｍ＝Ｍ−１，…，１    （処理１８〜２１のループ）
１９．  ＾Ｌm-1 （Ｌm * ）を読み込み，Ｌm-1 * ←＾Ｌm-1 （Ｌm * ）とする。
２０．  Δm * ←Ｌm * −Ｌm-1 * 
２１．  Δ0 * ←Ｌ0 * ＋１
［ルックアップテーブルを用いた演算量低減法］
上記の処理では，Ｌm とΔm の組み合わせによっては，ＲＤコストψ（Ｌm −（Δm −１），Ｌm , λ）が異なる量子化ビン（ｍの値が異なるという意味）において必要となる。その度に，ＲＤコストψ（Ｌm −（Δm −１），Ｌm , λ）を算出するのは，計算コストの観点から得策ではない。計算結果を格納し，必要に応じて格納結果を呼び出すことで，演算量を低減できる。そこで，ψ（Ｌm −（Δm −１），Ｌm , λ）として取り得る値をルックアップテーブル（（Ｋ−１）×Ｋ要素）に格納する。格納処理は，次のような手順になる。
１．ｆｏｒ  ｍ＝０，…，Ｋ−２  （処理１〜３のループ）
２．  ｆｏｒ  ｋ＝１，…，Ｋ−ｍ−１  （処理２〜３のループ）
３．      Ｅ［ｍ，ｍ＋ｋ］←ψ（ｍ，ｍ＋ｋ，λ）
なお，前記［量子化ビン数の設定法（基本解法）］，［量子化ビン数の設定法（低演算量解法）］において，本ルックアップテーブルを用いる場合，全ての量子化ビン数（［量子化ビン数の設定法（基本解法）］の場合，Ｂl ≦Ｍ≦Ｂu ，［量子化ビン数の設定法（低演算量解法）］の場合，Ｍlower ≦Ｍ≦Ｍupper ）に対して，全ての量子化ビン数で共有可能である。このため，対象とする量子化ビン数が増加しても，ルックアップテーブルを求める処理は増加することはない。
【０１０２】
［ＲＤコスト計算の漸化関係を用いた演算量低減法］
上述のルックアップテーブル（（Ｋ−１）×Ｋ要素）Ｅ［ｍ，ｍ＋ｋ］へ格納するＲＤコストψ（Ｌm −Δm ，Ｌm-1 ，λ）の計算過程にも重複した計算が存在するため，そうした重複部分を省略することで，演算量の低減を図る。
【０１０３】
まず，以下の値を定義する。
【０１０４】
【数１４】
0005426506.tif 000015
【０１０５】
これらを用いて，重心位置ｃ（Ｌm −（Δm −１），Ｌm ），量子化誤差ｅ（Ｌm −（Δm −１），Ｌm ）を再定義すると，次のようになる。
【０１０６】
【数１５】
0005426506.tif 000016
【０１０７】
これより，ｃ（Ｌm −（Δm −１），Ｌm ）およびｅ（Ｌm −（Δm −１），Ｌm ）が，以下の漸化関係を持つことが分かる。
【０１０８】
【数１６】
0005426506.tif 000017
【０１０９】
【数１７】
0005426506.tif 000018
【０１１０】
さらに，情報量ｌ（Ｌm −（Δm −１），Ｌm ）が，以下の漸化関係を持つことが分かる。
【０１１１】
【数１８】
0005426506.tif 000019
【０１１２】
ここで，Ｔは頻度の総和である。
【０１１３】
Ｔ＝Σk=0 K-1 ｈ［ｋ］
上記の関係に基づきｅ（Ｌm −（Δm −１），Ｌm ），ｌ（Ｌm −（Δm −１），Ｌm ）を算出し，両者の加重和であるＲＤコストをルックアップテーブル（（Ｋ−１）×Ｋ要素）に格納する。格納処理は，以下に説明する［ＲＤコストの算出アルゴリズム（低減法）］のようになる。
【０１１４】
なお，前記［量子化ビン数の設定法（基本解法）］，［量子化ビン数の設定法（低演算量解法）］において，本ルックアップテーブルを用いる場合，全ての量子化ビン数（［量子化ビン数の設定法（基本解法）］の場合，Ｂl ≦Ｍ≦Ｂu ，［量子化ビン数の設定法（低演算量解法）］の場合，Ｍlower ≦Ｍ≦Ｍupper ）に対して，全ての量子化ビン数で共有可能である。このため，対象とする量子化ビン数が増加しても，ルックアップテーブルを求める処理は増加することはない。
【０１１５】
［ＲＤコストの算出アルゴリズム（低減法）］
１．ｆｏｒ  ｋ＝０，…，Ｋ−１    （処理１〜４のループ）
２．  ｑ1 ［０，ｋ］←０
３．  ｑ2 ［０，ｋ］←０
４．  ｑ3 ［０，ｋ］←０
５．Ｔ←Σk=0 K-1 ｈ［ｋ］
６．ｆｏｒ  ｍ＝０，…，Ｋ−２    （処理６〜１４のループ）
７．  ｆｏｒ  ｋ＝０，…，Ｋ−ｍ−１    （処理７〜１４のループ）
８．    ｑ1 ［ｍ，ｍ＋ｋ＋１］←ｑ1 （ｍ，ｍ＋ｋ）＋ｈ［ｍ＋ｋ＋１］
９．    ｑ2 ［ｍ，ｍ＋ｋ＋１］←ｑ2 （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）ｈ［ｍ＋ｋ＋１］  
１０．  ｑ3 ［ｍ，ｍ＋ｋ＋１］←ｑ3 （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）2 ｈ［ｍ＋ｋ＋１］
１１．   c［ｍ，ｍ＋ｋ＋１］←ｑ2 （ｍ，ｍ＋ｋ＋１）／ｑ1 （ｍ，ｍ＋ｋ＋１）
１２．   e［ｍ，ｍ＋ｋ＋１］←ｑ3 （ｍ，ｍ＋ｋ＋１）−２ｃ（ｍ，ｍ＋ｋ＋１）ｑ2 （ｍ，ｍ＋ｋ＋１）＋ｃ（ｍ，ｍ＋ｋ＋１）2 ｑ1 （ｍ，ｍ＋ｋ＋１）
１３．  ｌ（Ｌm −（Δm −１），Ｌm ）←−｛ｑ1 （Ｌm −Δm −１），Ｌm ）／Ｔ｝｛ｌｏｇ2 ｑ1 （Ｌm −（Δm −１），Ｌm ）−ｌｏｇ2 Ｔ｝
１４．  Ｅ［ｍ，ｍ＋ｋ＋１］←ｅ［ｍ，ｍ＋ｋ＋１］＋λ・ｌ（Ｌm −（Δm −１），Ｌm ）
以上を踏まえ，ルックアップテーブルを参照する方式の場合の低演算量形の適応量子化アルゴリズムは，以下のようになる。
【０１１６】
［適応量子化アルゴリズム（低演算量形）］
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．量子化後のクラス数Ｍを読み込む。
３．［ＲＤコストの算出アルゴリズム（低減法）］に基づくＲＤコスト算出，およびルックアップテーブルへの格納。
４．［適応量子化アルゴリズム（基本形）］におけるψ（Ｌm −（Δm −１），Ｌm , λ）への格納対象の算出処理をルックアップテーブルＥ［Ｌm （Δm −１），Ｌm , λ］からの読み出し処理に置き換えて，同アルゴリズムの処理３以降の処理を実施。
【０１１７】
［視覚感度特性を考慮した重み付き歪み量の最小化］
視覚系は，低輝度の画素値の変化に比べて，高輝度の画素値の変化に鈍感である。そこで，こうした視覚特性を考慮して量子化を行う場合には，以下のように行う。まず，画素値ｋ（ｋ＝０，…，Ｋ−１）に対する重み係数として，ｗ［ｋ］を設定する。この重み係数は，外部から与えられるものとする。例えば，高輝度（大きなｋ）の重みを低輝度（小さなｋ）の重みより小さな値に設定すれば，上記の輝度差に対する視覚特性を量子化処理に組み込むことが可能になる。この重み係数を用いて，画素値ｋに対する頻度ｈ［ｋ］を，〜ｈ［ｋ］＝ｗ［ｋ］×ｈ［ｋ］（ただし，〜はｈの上に付く記号）として補正し，この補正後のヒストグラム〜ｈ［ｋ］に対して，前述の量子化処理を実施する。
【０１１８】
以上の適応量子化の処理は，コンピュータとソフトウェアプログラムとによって実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。
【符号の説明】
【０１１９】
１０  適応量子化装置
１１  入力信号レベル数記憶部
１２  量子化後レベル数記憶部
１３  未定乗数記憶部
１４  ヒストグラム生成部
１５  近似誤差算出部
１６  情報量算出部
１７  ＲＤコスト算出部
１８  ＲＤコスト最小値記憶部
１９  区間上端最適値記憶部
２０  区間上端最適値追跡部
２１  量子化処理部
【図１】
0005426506.tif 000020
【図２】
0005426506.tif 000021
【図３】
0005426506.tif 000022