JP5426506B2 - 適応量子化方法，適応量子化装置および適応量子化プログラム - Google Patents

Description

本発明は，高能率画像信号符号化の技術に関し，特に符号化効率を向上させるための適応量子化技術に関する。

非可逆符号化において，量子化は必要不可欠な構成要素である。一般的な符号化方式においては，量子化は符号化データの表現精度を制御し，この制御過程において符号化歪みが発生する。基本的な量子化器の設計は，与えられた歪み量の評価尺度に対して，その評価尺度を最小化するための符号語（量子化インデックス）を求める最小化問題に帰着される。歪み量の評価尺度としては，二乗和，絶対値和が用いられる。

また，一般的な量子化器の設計においては，符号量に関する制約条件が課せられる。この場合，量子化器の設計は，符号量に関する一定の制約条件の下，与えられた歪み量の評価尺度に対して，その評価尺度を最小化するための符号語（量子化インデックス）を求める制約条件付きの最小化問題に帰着される。符号化対象信号の確率密度関数がパラメトリックに表現できる場合には，解析的に最適解を求める手法(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 を１ずつ増やしながら，ステップＳ２３までの処理を繰り返す（ステップＳ１３）。なお，Ｌ₀ は予め０に初期化しておく。

また，さらに量子化レベルｍを表す区間の区間幅Δ_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 はヒストグラムにおける第ｍ区間の上端であり，次式で定義されるものとする。

なお，量子化後の各階調が，少なくとも１つ以上，量子化前の階調を含む必要があることから，Ｌ_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 ）で近似した場合の代表値を表現するために必要な情報量として，次式で表されるｌ（Ｌ_m −（Δ_m −１），Ｌ_m ）を用いる。

ここで，ｐ（Ｌ_m , Δ_m ）は，ヒストグラムの区間［Ｌ_m −（Δ_m −１），Ｌ_m ］における頻度が全頻度に占める割合であり，次式で定義される。

ここで必要なことは，量子化の符号量が一定の閾値以下という条件下で歪み量を最小化することである。つまり，求めるべきパラメータ（Δ₀ ，…，Δ_M-1 ）は，

上式を満たす条件下において，次式を最小化するものである。

こうした制約条件付き最小化問題は，ラグランジュの未定乗数法により，未定乗数λを導入することで，制約条件のない最小化問題に変形できる。つまり，求めるべきパラメータは，次式を満たすＭ個のパラメータとなる。

ここで，ψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）は，次式で定義される評価尺度（ＲＤコストと呼ぶ）である。

ψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）
＝ｅ（Ｌ_m −（Δ_m −１），Ｌ_m ）＋λ・ｌ（Ｌ_m −（Δ_m −１），Ｌ_m ） (8)
Ｍ個のパラメータ（Δ₀ ，…，Δ_M-1 ）の取り得る組み合わせは，Ｍとともに指数関数的に増加するため，この中から最適な組み合わせ（Δ₀ ^* ，…，Δ_M-1 ^* ）を総当りで探索するのは，計算量的に困難である。

そこで，第ｍ量子化ビンのＲＤコストψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）が同ビンの上端Ｌ_m と同ビンの区間幅Δ_m に依存することに着目し，以下のように最適解を算出する。まず，ヒストグラムの区間［０, Ｌ_m ］をｍ＋１分割した際のＲＤコストの総和
Σ_i=0 ^m ψ（Ｌ_i −（Δ_i −１），Ｌ_i ，λ）
の最小値をＳ_m （Ｌ_m ）として定義する。つまり，最適なΔ_m ，…, Δ₀ を用いた場合のΣ_i=0 ^m ψ（Ｌ_i −（Δ_i −１），Ｌ_i ，λ）に対する最小値である。

ここで，ψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）が第ｍ量子化ビンの上端Ｌ_m と同ビンの区間幅Δ_m に依存することに着目すると，Ｓ_m （Ｌ_m ）はＳ_m-1 （Ｌ_m −Δ_m ）を用いて，次式のように表わされる。

なお，ｍ＝０，…，Ｍ−１である。また，Ｌ_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) の最小化問題は，次式のように表される。

式(9) および式(1) におけるＬ_M-1 ＝Ｋ−１を用いて，式(6) の最小化問題は，（Ｋ−Ｍ）×（１＋Ｋ−Ｍ）×（Ｍ−１）／２個の候補の中から最適解（Δ₀ ^* ，…，Δ_M-1 ^* ）を求める最適化問題に帰着される。このように，本方式による方法は，多項式時間での最適解の求解を可能とする。式(13)の
Ｓ_M-2 （Ｌ_M-1 −Δ_M-1 ）＋ψ（Ｌ_M-1 −（Δ_M-1 −１），Ｌ_M-1 ，λ）
の最小値を求めた後，最適解（Δ₀ ^* ，…，Δ_M-1 ^* ）は，バックトラック過程を通して，求めることができる。次式に示す通り，式(13)の最小化問題の解をΔ_M-1 ^* とおく。

このΔ_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 ^* ），…，Ｌ₁ ^* ＝＾Ｌ₁ （Ｌ₂ ^* ）
として繰り返し，得られた各ビンの上端値を用いて，
Δ_M-3 ^* ＝Ｌ_M-3 ^* −Ｌ_M-4 ^* ，…，Δ₁ ^* ＝Ｌ₁ ^* −Ｌ₀ ^* ，Δ₀ ^* ＝Ｌ₀ ^* ＋１
として求める。

［適応量子化アルゴリズム（基本形）］
以上の適応量子化の基本的な処理手順は，以下のとおりである。
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．量子化後のクラス数Ｍを読み込む。
３．Ｓ₀ （ｉ）←０（ｉ＝０，…，Ｋ−Ｍ）とする。
４．ｆｏｒ ｍ＝０，…，Ｍ−１ （処理４〜１２のループ）
５． ｆｏｒ Ｌ_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 ^*
１７．Δ₀ ^* ←Ｌ₀ ^* ＋１
以上により，区間幅Δ_m ^* （ｍ＝０，…，Ｍ−１）が定まり，クラス境界（量子化境界）が決定される。

［未定乗数の設定法］
未定乗数λの設定法について説明する。２つの未定乗数λ_l ，λ_u を準備する。なお，この未定乗数は，以下の条件を満たすように設定されるものとする。量子化ビン数をＭとし，未定乗数λ_u およびλ_l が与えられた場合，前述した適応量子化アルゴリズムにより生成されるパラメータの情報量和を各々，Ｒ（Δ_M ^* （λ_u ），λ_u ），Ｒ（Δ_M ^* （λ_l ），λ_l ）とすると，次式を満たす。

Ｒ（Δ_M ^* （λ_u ），λ_u ）≦Ｒ₀ ≦Ｒ（Δ_M ^* （λ_l ），λ_l ）
未定乗数として，
λ＝（λ_l ＋λ_u ）／２ (15)
を設定し，同未定乗数を用いて上記［適応量子化アルゴリズム（基本形）］を実行する。そこで生成されるパラメータの情報量和Ｒ（Δ_M ^* （λ），λ）を求める。

得られたＲ（Δ_M ^* （λ），λ）の値に基づき，以下のような処理を行う。
（ｉ）Ｒ₀ −ε≦Ｒ（Δ_M ^* （λ），λ）≦Ｒ₀ の場合：
λを未定乗数として設定する。εは十分小さな正の数である。Ｒ（Δ_M ^* （λ），λ）＝Ｒ₀ を評価したいのであるが，実数値の場合，等式の評価は計算精度の観点から難しいため，ここで用いるような不等式の評価を用いる。
（ii）Ｒ（Δ_M ^* （λ），λ）＞Ｒ₀ の場合：
λ_l ←λとして，式(15)以降の処理を繰り返す。

(iii) Ｒ（Δ_M ^* （λ），λ）＜Ｒ₀ −εの場合：
λ_u ←λとして，式(15)以降の処理を繰り返す。

［未定乗数の設定アルゴリズム］
以上の未定乗数の設定アルゴリズムをまとめると，以下のようになる。
１．量子化ビン数Ｍを読み込む。
２．情報量の上限Ｒ₀ を読み込む。
３．次式を満たす未定乗数λ_l , λ_u を準備する。

Ｒ（Δ_M ^* （λ_u ），λ_u ）≦Ｒ₀ ≦Ｒ（Δ_M ^* （λ_l ），λ_l ）
４．未定乗数として，λ＝（λ_l ＋λ_u ）／２を設定する。
５．未定乗数λを用いて，上記［適応量子化アルゴリズム（基本形）］を実行する。
６．前の処理５で生成されるパラメータの情報量和Ｒ（Δ_M ^* （λ），λ）を求める。
７．ｉｆ Ｒ₀ −ε≦Ｒ（Δ_M ^* （λ），λ）≦Ｒ₀ の場合：
λを未定乗数として設定する。
８．ｉｆ Ｒ（Δ_M ^* （λ），λ）＞Ｒ₀ の場合：
λ_l ←λとして，処理４へ戻る。
９．ｉｆ Ｒ（Δ_M ^* （λ），λ）＜Ｒ₀ −εの場合：
λ_u ←λとして，処理４へ戻る。

［量子化ビン数の設定法（基本解法）］
上記適応量子化の例では，量子化ビン数Ｍが外部から与えられるものとして説明したが，次に，量子化ビン数を可変とした場合の量子化ビン数Ｍの設定法について説明する。量子化ビン数Ｍが取り得る値をＢ_l ≦Ｍ≦Ｂ_u とし，量子化ビン数Ｍ（Ｂ_l ≦Ｍ≦Ｂ_u ）の各々について，前述した［未定乗数の設定アルゴリズム］に基づき，最適な未定乗数を求める。量子化ビン数がＭの場合に求まる未定乗数をλ_M ^* とおく。

Ｍ＝Ｂ_l ，…，Ｂ_u に対して，未定乗数λ_M ^* を用いた場合の近似誤差和Ｄ（Δ_Bl ^*（λ_Bl ^* ），λ_Bl ^* ），…，Ｄ（Δ_Bu ^* （λ_Bu ^* ），λ_Bu ^* ）を求め，近似誤差和が最小となる量子化ビン数を最適な量子化ビン数とする。つまり，次式を満たすＭ^* を求める。

Ｄ（Δ_M* ^*（λ_M* ^* ），λ_M* ^* ）＜Ｄ（Δ_M ^* （λ_M ^* ），λ_M ^* ）
ｆｏｒ ａｌｌ Ｍ≠Ｍ^*
［量子化ビン数の設定アルゴリズム］
量子化ビン数の設定アルゴリズムは，以下のとおりである。
１．情報量の上限Ｒ₀ を読み込む。
２．ｆｏｒ Ｍ＝Ｂ_l ，…，Ｂ_u （処理２−１〜２−２のループ）
２−１．［未定乗数の設定アルゴリズム］を実行し，最適な未定乗数λ_M ^* および同未定乗数に対する量子化パラメータΔ_M ^* （λ_M ^* ）を求める。
２−２．前の処理２−１で求めた量子化パラメータΔ_M ^* （λ_M ^* ）を用いた場合の近似誤差和Ｄ（Δ_M ^* （λ_M ^* ），λ_M ^* ）を＾Ｄ［Ｍ］に格納する。
３．＾Ｄ［Ｍ］（Ｍ＝Ｂ_l ，…，Ｂ_u ）の中で最小値を返すＭ^* を求め，このＭ^* に対する量子化パラメータΔ_M* ^* （λ_M* ^* ）を出力する。

［量子化ビン数の設定法（低演算量解法）］
量子化ビン数Ｍが取り得る値をＢ_l ≦Ｍ≦Ｂ_u とし，量子化ビン数Ｍ（Ｂ_l ≦Ｍ≦Ｂ_u ）が与えられた場合，最適な未定乗数の算出が不要となる量子化ビン数については，同算出処理を省略するアプローチを採る。

ここでは，量子化ビン数をＭとして，λを変化させた場合の発生符号量の上限値・下限値を考察する。式(7) をλの関数と見た場合，発生符号量の上限を与えるのは，λ＝０とした場合，つまり，コスト関数として歪み量のみを用いた場合である。これは，量子化ビン数をＭとして，以下の最小化問題を解いた場合に当たる。

一方，発生符号量の下限を与えるのは，λ＝＋∞とした場合，つまり，コスト関数として符号量のみを用いた場合である。量子化ビン数をＭとして，以下の最小化問題を解いた場合に当たる。

上記の最小化問題を解くことで求まる発生符号量の上限・下限を各々Ｒ_u （Ｍ），Ｒ_l （Ｍ）とおく。Ｒ_u （Ｍ），Ｒ_l （Ｍ）は，いずれも量子化ビン数Ｍに対する非減少関数である。これは，量子化ビン数として大きな値を設定すれば，発生符号量も増加するためである。また，上限・下限として設定したことから，Ｒ_l （Ｍ）≦Ｒ_u （Ｍ）である。

ここで，まず，Ｒ_l （Ｍ）≦Ｒ₀ を満たすＭの最大値をＭ_upper とする。Ｒ_l （Ｍ）のＭに対する非減少性から，Ｍ_upper ≦Ｍを満たすＭの場合，発生符号量がＲ₀ 以下となる制約条件を満たすことができない。このため，λの設定を含めた最適化の対象は，Ｍ≦Ｍ_upper を満たすＭに限定しても最適性は保証される。

次に，Ｒ_u （Ｍ）≦Ｒ₀ を満たすＭの最大値をＭ_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 ^* （０），０）≧Ｒ₀ であれば処理を終了する。そうでなければ，次の処理へ進む。
５．ｆｏｒ ＾Ｍ＝Ｂ_l ＋１，…，Ｂ_u （処理５〜９のループ）
６． Ｍ＝＾Ｍとして，ルックアップテーブルＴ［］およびルックアップテーブルΦ＾_M-1 ［］を読み込み，後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］の処理を実施する。
７． 生成されるパラメータの情報量の和Ｒ（Δ_M ^* （０），０）を求める。
８． Ｒ（Δ_M ^* （０），０）≧Ｒ₀ であれば，Ｍ_lower ←＾Ｍ−１として，処理を終了する。そうでなければ，次の処理９へ進む。
９． ルックアップテーブルＴ［］を更新し，ルックアップテーブルΦ＾_M ［］を出力する。

［Ｍ_upper の算出アルゴリズム］
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．Ｍ_upper ←Ｂ_u
３．λ＝λ_+max，Ｍ＝Ｂ_l として，［適応量子化アルゴリズム］の処理を行い，＾Ｌ_m-1 （Ｌ_m ）の値をルックアップテーブルＴ［ｍ，Ｌ_m ］に格納し，さらに，Ｓ_m （Ｌ_m ）の値を別のルックアップテーブルΦ_Bl［ｍ，Ｌ_m ］に格納する。ここで，λ_+maxは十分大きな値とする。
４．Ｒ（Δ_Bu ^* （λ_+max），λ_+max）≧Ｒ₀ であれば，処理を終了する。この場合，与えられた制約条件を満たす解がないことになる。そうでなければ，次の処理５へ進む。
５．ｆｏｒ ＾Ｍ＝Ｂ_l ＋１，…，Ｂ_u （処理５〜９のループ）
６． Ｍ＝＾Ｍとして，ルックアップテーブルＴ［］およびルックアップテーブルΦ＾_M-1 ［］を読み込み，後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］の処理を実施する。
７． 生成されるパラメータの情報量の和Ｒ（Δ_M ^* （λ_+max），λ_+max）を求める。
８． Ｒ（Δ_M ^* （λ_+max），λ_+max）≧Ｒ₀ であれば，Ｍ_upper ←＾Ｍ−１として，処理を終了する。そうでなければ，次の処理９へ進む。
９． ルックアップテーブルＴ［］を更新し，ルックアップテーブルΦ＾_M ［］を出力する。

＜最適ビン数の算出方法＞
Ｍ_upper の設定においては，コスト関数をｅ（）として，各量子化ビン数に対する最適コスト値を算出する。これは，式(8) のＲＤコストにおいて，λ＝０と設定した場合に相当する。一方，Ｍ_lower の設定においては，コスト関数をｌ（）として，各量子化ビン数に対する最適コスト値を算出する。これは，式(8) のＲＤコストにおいて，λとしては，λ＝＋∞と設定した場合に相当する。

［量子化ビン数の設定アルゴリズム（低演算量タイプ）］
低演算量タイプの量子化ビン数の設定アルゴリズムを，以下に示す。
１．情報量の上限Ｒ₀ を読み込む。
２．前述した［Ｍ_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* ^* ）を出力する。

［未定乗数の設定アルゴリズム（継承型）］
上記処理４−１で用いる未定乗数の設定アルゴリズム（継承型）の手順は，以下のとおりである。
１．量子化ビン数Ｍを読み込む。
２．情報量の上限Ｒ₀ を読み込む。
３．未定乗数λの初期値，および，その上限値λ_u を読み込む。
４．未定乗数として，λ＝（λ_l ＋λ_u ）／２を設定する。
５．未定乗数λを用いて後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］を実行する。
６．処理５で生成されるパラメータの情報量和Ｒ（Δ_M ^* （λ），λ）を求める。
７．ｉｆ Ｒ₀ −ε≦Ｒ（Δ_M ^* （λ），λ）≦Ｒ₀ の場合：
λ_u を未定乗数として設定する。
８．未定乗数λ_u を用いて，後述する［適応量子化アルゴリズム（Ｍ−１ビンの量子化結果利用形）］を実行する。
９．処理８で生成されるパラメータの情報量和Ｒ（Δ_M ^* （λ_u ），λ_u ）を求める。
１０． ｉｆ Ｒ₀ −ε≦Ｒ（Δ_M ^* （λ_u ），λ_u ）≦Ｒ₀ の場合：
λ_u を未定乗数として設定する。
１１． ｉｆ Ｒ（Δ_M ^* （λ_u ），λ_u ）＞Ｒ₀ の場合：
λ←２λ_u として，処理５へ戻る。
１２． ｉｆ Ｒ（Δ_M ^* （λ_u ），λ_u ）＜Ｒ₀ −εの場合：
λ_l ←λとして，処理４へ戻る。
１３． ｉｆ Ｒ₀ −ε≦Ｒ（Δ_M ^* （λ_l ），λ_l ）≦Ｒ₀ の場合：
λ_l を未定乗数として設定する。
１４． ｉｆ Ｒ（Δ_M ^* （λ_l ），λ_l ）＞Ｒ₀ の場合：
λ_u ←λとして，処理４へ戻る。
１５． ｉｆ Ｒ（Δ_M ^* （λ_l ），λ_l ）＜Ｒ₀ −εの場合：
λ←λ_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 ^*
２１． Δ₀ ^* ←Ｌ₀ ^* ＋１
［ルックアップテーブルを用いた演算量低減法］
上記の処理では，Ｌ_m とΔ_m の組み合わせによっては，ＲＤコストψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）が異なる量子化ビン（ｍの値が異なるという意味）において必要となる。その度に，ＲＤコストψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）を算出するのは，計算コストの観点から得策ではない。計算結果を格納し，必要に応じて格納結果を呼び出すことで，演算量を低減できる。そこで，ψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）として取り得る値をルックアップテーブル（（Ｋ−１）×Ｋ要素）に格納する。格納処理は，次のような手順になる。
１．ｆｏｒ ｍ＝０，…，Ｋ−２ （処理１〜３のループ）
２． ｆｏｒ ｋ＝１，…，Ｋ−ｍ−１ （処理２〜３のループ）
３． Ｅ［ｍ，ｍ＋ｋ］←ψ（ｍ，ｍ＋ｋ，λ）
なお，前記［量子化ビン数の設定法（基本解法）］，［量子化ビン数の設定法（低演算量解法）］において，本ルックアップテーブルを用いる場合，全ての量子化ビン数（［量子化ビン数の設定法（基本解法）］の場合，Ｂ_l ≦Ｍ≦Ｂ_u ，［量子化ビン数の設定法（低演算量解法）］の場合，Ｍ_lower ≦Ｍ≦Ｍ_upper ）に対して，全ての量子化ビン数で共有可能である。このため，対象とする量子化ビン数が増加しても，ルックアップテーブルを求める処理は増加することはない。

［ＲＤコスト計算の漸化関係を用いた演算量低減法］
上述のルックアップテーブル（（Ｋ−１）×Ｋ要素）Ｅ［ｍ，ｍ＋ｋ］へ格納するＲＤコストψ（Ｌ_m −Δ_m ，Ｌ_m-1 ，λ）の計算過程にも重複した計算が存在するため，そうした重複部分を省略することで，演算量の低減を図る。

まず，以下の値を定義する。

これらを用いて，重心位置ｃ（Ｌ_m −（Δ_m −１），Ｌ_m ），量子化誤差ｅ（Ｌ_m −（Δ_m −１），Ｌ_m ）を再定義すると，次のようになる。

これより，ｃ（Ｌ_m −（Δ_m −１），Ｌ_m ）およびｅ（Ｌ_m −（Δ_m −１），Ｌ_m ）が，以下の漸化関係を持つことが分かる。

さらに，情報量ｌ（Ｌ_m −（Δ_m −１），Ｌ_m ）が，以下の漸化関係を持つことが分かる。

ここで，Ｔは頻度の総和である。

Ｔ＝Σ_k=0 ^K-1 ｈ［ｋ］
上記の関係に基づきｅ（Ｌ_m −（Δ_m −１），Ｌ_m ），ｌ（Ｌ_m −（Δ_m −１），Ｌ_m ）を算出し，両者の加重和であるＲＤコストをルックアップテーブル（（Ｋ−１）×Ｋ要素）に格納する。格納処理は，以下に説明する［ＲＤコストの算出アルゴリズム（低減法）］のようになる。

なお，前記［量子化ビン数の設定法（基本解法）］，［量子化ビン数の設定法（低演算量解法）］において，本ルックアップテーブルを用いる場合，全ての量子化ビン数（［量子化ビン数の設定法（基本解法）］の場合，Ｂ_l ≦Ｍ≦Ｂ_u ，［量子化ビン数の設定法（低演算量解法）］の場合，Ｍ_lower ≦Ｍ≦Ｍ_upper ）に対して，全ての量子化ビン数で共有可能である。このため，対象とする量子化ビン数が増加しても，ルックアップテーブルを求める処理は増加することはない。

［ＲＤコストの算出アルゴリズム（低減法）］
１．ｆｏｒ ｋ＝０，…，Ｋ−１ （処理１〜４のループ）
２． ｑ₁ ［０，ｋ］←０
３． ｑ₂ ［０，ｋ］←０
４． ｑ₃ ［０，ｋ］←０
５．Ｔ←Σ_k=0 ^K-1 ｈ［ｋ］
６．ｆｏｒ ｍ＝０，…，Ｋ−２ （処理６〜１４のループ）
７． ｆｏｒ ｋ＝０，…，Ｋ−ｍ−１ （処理７〜１４のループ）
８． ｑ₁ ［ｍ，ｍ＋ｋ＋１］←ｑ₁ （ｍ，ｍ＋ｋ）＋ｈ［ｍ＋ｋ＋１］
９． ｑ₂ ［ｍ，ｍ＋ｋ＋１］←ｑ₂ （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）ｈ［ｍ＋ｋ＋１］
１０． ｑ₃ ［ｍ，ｍ＋ｋ＋１］←ｑ₃ （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）² ｈ［ｍ＋ｋ＋１］
１１． c［ｍ，ｍ＋ｋ＋１］←ｑ₂ （ｍ，ｍ＋ｋ＋１）／ｑ₁ （ｍ，ｍ＋ｋ＋１）
１２． e［ｍ，ｍ＋ｋ＋１］←ｑ₃ （ｍ，ｍ＋ｋ＋１）−２ｃ（ｍ，ｍ＋ｋ＋１）ｑ₂ （ｍ，ｍ＋ｋ＋１）＋ｃ（ｍ，ｍ＋ｋ＋１）² ｑ₁ （ｍ，ｍ＋ｋ＋１）
１３． ｌ（Ｌ_m −（Δ_m −１），Ｌ_m ）←−｛ｑ₁ （Ｌ_m −Δ_m −１），Ｌ_m ）／Ｔ｝｛ｌｏｇ₂ ｑ₁ （Ｌ_m −（Δ_m −１），Ｌ_m ）−ｌｏｇ₂ Ｔ｝
１４． Ｅ［ｍ，ｍ＋ｋ＋１］←ｅ［ｍ，ｍ＋ｋ＋１］＋λ・ｌ（Ｌ_m −（Δ_m −１），Ｌ_m ）
以上を踏まえ，ルックアップテーブルを参照する方式の場合の低演算量形の適応量子化アルゴリズムは，以下のようになる。

［適応量子化アルゴリズム（低演算量形）］
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．量子化後のクラス数Ｍを読み込む。
３．［ＲＤコストの算出アルゴリズム（低減法）］に基づくＲＤコスト算出，およびルックアップテーブルへの格納。
４．［適応量子化アルゴリズム（基本形）］におけるψ（Ｌ_m −（Δ_m −１），Ｌ_m , λ）への格納対象の算出処理をルックアップテーブルＥ［Ｌ_m （Δ_m −１），Ｌ_m , λ］からの読み出し処理に置き換えて，同アルゴリズムの処理３以降の処理を実施。

［視覚感度特性を考慮した重み付き歪み量の最小化］
視覚系は，低輝度の画素値の変化に比べて，高輝度の画素値の変化に鈍感である。そこで，こうした視覚特性を考慮して量子化を行う場合には，以下のように行う。まず，画素値ｋ（ｋ＝０，…，Ｋ−１）に対する重み係数として，ｗ［ｋ］を設定する。この重み係数は，外部から与えられるものとする。例えば，高輝度（大きなｋ）の重みを低輝度（小さなｋ）の重みより小さな値に設定すれば，上記の輝度差に対する視覚特性を量子化処理に組み込むことが可能になる。この重み係数を用いて，画素値ｋに対する頻度ｈ［ｋ］を，〜ｈ［ｋ］＝ｗ［ｋ］×ｈ［ｋ］（ただし，〜はｈの上に付く記号）として補正し，この補正後のヒストグラム〜ｈ［ｋ］に対して，前述の量子化処理を実施する。

以上の適応量子化の処理は，コンピュータとソフトウェアプログラムとによって実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。

１０ 適応量子化装置
１１ 入力信号レベル数記憶部
１２ 量子化後レベル数記憶部
１３ 未定乗数記憶部
１４ ヒストグラム生成部
１５ 近似誤差算出部
１６ 情報量算出部
１７ ＲＤコスト算出部
１８ ＲＤコスト最小値記憶部
１９ 区間上端最適値記憶部
２０ 区間上端最適値追跡部
２１ 量子化処理部

Claims (9)

1. クラス数がＫの入力信号を，Ｋより小さいＭのクラス数に量子化する適応量子化方法であって，
   入力信号についてクラス数Ｋのヒストグラムを生成するステップと，
   与えられたクラス数Ｍで前記ヒストグラムを近似する際に，第ｉ番目（ｉ＝１，２，…，Ｍ−１）のクラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する近似誤差と符号量とを算出し，第１番目のクラスから第ｉ番目のクラスまでの近似誤差と符号量の加重和を最小化する量子化値に対応するクラス境界情報およびそのときの前記加重和の最小値を算出し，メモリに格納するとともに，次の第ｉ＋１番目（ただし，ｉ＜Ｍ−１）のクラス境界の候補に対して前記加重和の最小値を算出する際に，前記格納した第ｉ番目までのクラスに対する最小値をメモリから読み出して前記加重和の最小値の計算に用い，最初のクラスから当該クラスまでの前記加重和を最小化するクラス境界を求める処理を，ｉ＝１からｉ＝Ｍ−１までｉを１ずつ増やしながら繰り返すステップと，
   前記メモリに格納された第１番目から第Ｍ−１番目までのクラス境界の候補に対するクラス境界情報および前記加重和の最小値に基づき，クラス境界の全候補に対して近似誤差と符号量の加重和を最小化するクラス境界を選択するステップと，
   最終的に選択したクラス境界を用いて入力信号を量子化するステップとを有する
   ことを特徴とする適応量子化方法。
2. 請求項１記載の適応量子化方法において，
   前記近似誤差として，クラス数Ｍの各クラスの代表値と当該各クラスにおける入力信号の値との誤差の絶対値和または二乗和，あるいは，クラス数Ｍの各クラスの代表値と当該各クラスにおける入力信号の値に対して視覚感度に基づき重み付けされた値との誤差の絶対値和または二乗和を算出する
   ことを特徴とする適応量子化方法。
3. 請求項１または請求項２記載の適応量子化方法において，
   前記近似誤差と符号量との加重和として取り得る値を予め算出してルックアップテーブルに格納し，前記ルックアップテーブルを参照して，前記クラス境界の候補に対する加重和を得る
   ことを特徴とする適応量子化方法。
4. クラス数がＫの入力信号を，別途，与えられたクラス数の候補から選択されたクラス数に量子化する適応量子化方法であって，
   設定された近似誤差と符号量の加重係数を用いて，前記与えられたクラス数の各候補値に対して，請求項１，請求項２または請求項３に記載された適応量子化方法により，量子化代表値およびクラス境界を求め，
   かつ，前記加重係数を変化させて前記適応量子化方法を繰り返すことにより，前記加重係数を最適化し，
   最適化した加重係数の下で前記適応量子化方法により求めた量子化代表値およびクラス境界を用いた場合の近似誤差を算出し，クラス数の各候補値を用いた場合の近似誤差の中から最小値を求め，
   その最小値を実現する量子化代表値およびクラス境界，並びに，その時のクラス数を同定する
   ことを特徴とする適応量子化方法。
5. 請求項４記載の適応量子化方法において，
   前記クラス数をＭとして前記近似誤差と符号量の加重係数を変化させた場合の発生符号量の上限値と下限値とから最適化の対象となるクラス数Ｍの上限値と下限値とを算出し，前記クラス数Ｍの上限値と下限値との範囲に限定して，前記クラス数の候補値に対する前記量子化代表値およびクラス境界を求める処理を行う
   ことを特徴とする適応量子化方法。
6. 請求項４または請求項５記載の適応量子化方法において，
   前記クラス数の各候補値に対する前記量子化代表値およびクラス境界を求める処理において，クラス数Ｍ−１として量子化代表値およびクラス境界を求めた結果を記憶し，クラス数Ｍの量子化代表値およびクラス境界を求める処理に利用することにより，クラス数Ｍ−１とクラス数Ｍとで重複する演算を省略する
   ことを特徴とする適応量子化方法。
7. クラス数がＫの入力信号を，Ｋより小さいＭのクラス数に量子化する適応量子化装置であって，
   入力信号についてクラス数Ｋのヒストグラムを生成するヒストグラム生成手段と，
   与えられたクラス数Ｍで前記ヒストグラムを近似する際に，ｉ＝１からｉ＝Ｍ−１までｉを１ずつ増やしながら順番に，第ｉ番目のクラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する近似誤差を算出する近似誤差算出手段と，
   前記クラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する符号量を算出する情報量算出手段と，
   第１番目のクラスから第ｉ番目のクラスまでの前記近似誤差と前記符号量との加重和を算出し，第ｉ番目のクラス境界の各候補の中で，算出された前記加重和が最小となるクラス境界情報および加重和の最小値を算出する加重和算出手段と，
   前記加重和算出手段によって算出された前記加重和が最小となるクラス境界情報および加重和の最小値を，前記第ｉ番目のクラス境界の各候補ごとに記憶する記憶手段と，
   前記記憶手段に記憶された第１番目から第Ｍ−１番目までのクラス境界の候補に対するクラス境界情報および加重和の最小値に基づき，クラス境界の全候補に対して前記加重和を最小化するクラス境界を選択する最適値追跡手段と，
   前記最適値追跡手段によって選択されたクラス境界を用いて入力信号を量子化する量子化処理手段とを備え，
   前記加重和算出手段は，第ｉ番目のクラス境界の候補に対して前記加重和の最小値を算出する際に，前記記憶手段に記憶された第ｉ−１番目（ただし，ｉ≧２）までのクラスに対する加重和の最小値を読み出し，前記加重和の最小値の計算に用いることで，最初のクラスから当該クラスまでの加重和を最小化するクラス境界を求める
   ことを特徴とする適応量子化装置。
8. クラス数がＫの入力信号を，別途，与えられたクラス数の候補から選択されたクラス数に量子化する適応量子化装置であって，
   入力信号についてクラス数Ｋのヒストグラムを生成するヒストグラム生成手段と，
   設定された近似誤差と符号量の加重係数を用いて，前記与えられたクラス数の各候補値Ｍに対して，前記ヒストグラムを近似する際に，ｉ＝１からｉ＝Ｍ−１までｉを１ずつ増やしながら順番に，第ｉ番目のクラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する近似誤差を算出する近似誤差算出手段と，
   前記クラス境界の各候補に対して，第ｉ番目のクラスにおける入力信号の量子化により発生する符号量を算出する情報量算出手段と，
   第１番目のクラスから第ｉ番目のクラスまでの前記近似誤差と前記符号量との加重和を算出し，第ｉ番目のクラス境界の各候補の中で，算出された前記加重和が最小となるクラス境界情報および加重和の最小値を算出する加重和算出手段と，
   前記加重和算出手段によって算出された前記加重和が最小となるクラス境界情報および加重和の最小値を，前記第ｉ番目のクラス境界の各候補ごとに記憶する記憶手段と，
   前記記憶手段に記憶された第１番目から第Ｍ−１番目までのクラス境界の候補に対するクラス境界情報および加重和の最小値に基づき，クラス境界の全候補に対して前記加重和を最小化するクラス境界を選択する最適値追跡手段と，
   前記最適値追跡手段によって選択されたクラス境界を用いて入力信号を量子化する量子化処理手段とを備え，
   前記加重和算出手段は，第ｉ番目のクラス境界の候補に対して前記加重和の最小値を算出する際に，前記記憶手段に記憶された第ｉ−１番目（ただし，ｉ≧２）までのクラスに対する加重和の最小値を読み出し，前記加重和の最小値の計算に用いることで，最初のクラスから当該クラスまでの加重和を最小化するクラス境界を求め，
   前記近似誤差算出手段と，前記情報量算出手段と，前記加重和算出手段と，前記記憶手段と，前記最適値追跡手段とにより，前記与えられたクラス数の各候補値Ｍに対して，前記近似誤差と前記符号量との加重和に用いる加重係数の最適化を行うとともに，最適化した加重係数の下で量子化代表値およびクラス境界を用いた場合の近似誤差を算出し，クラス数の各候補値を用いた場合の近似誤差の中から最小値を求め，その最小値を実現する量子化代表値およびクラス境界，並びに，その時のクラス数を同定する
   ことを特徴とする適応量子化装置。
9. 請求項１から請求項６までのいずれか１項に記載の適応量子化方法を，コンピュータに実行させるための適応量子化プログラム。
   

Images