(57)【特許請求の範囲】
【請求項１】
入力信号のヒストグラムに対して、与えられたヒストグラムの区間の数を示すレベル数で前記ヒストグラムを近似する量子化処理を行う適応量子化装置が行う適応量子化方法であって、
前記区間の境界を示すクラス境界の候補を有意要素に制限する制限ステップと、
前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するメモリ格納ステップと、
次のクラスでの前記クラス境界を選択する際、非有意要素を前記近似誤差の累積値計算から除外し、前記メモリに格納した最小値を読み出す最小値読み出しステップと、
前記最小値を現時点での前記クラス境界の選択における前記近似誤差の累積値計算に用いることで、前記クラス境界の全要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択ステップと
を有する適応量子化方法。
【請求項２】
前記非有意要素を前記クラス境界の候補から除外して前記有意要素をクラス境界の候補とする際に、前記クラス境界となり得ない前記有意要素を候補から除外するための前記クラス境界となり得る前記有意要素の上限及び下限を設ける上下限設定ステップと、
前記上限及び前記下限の範囲に含まれる前記有意要素を前記クラス境界の候補とする請求項１に記載の適応量子化方法。
【請求項３】
各クラスの境界が前記有意要素となる場合の近似誤差のみを参照テーブルに格納するテーブル格納ステップと、
前記参照テーブルを参照して前記近似誤差の累積値の算出に用いる各クラス内の近似誤差を取得する請求項１または２に記載の適応量子化方法。
【請求項４】
入力信号のヒストグラムに対して、与えられたヒストグラムの区間の数を示すレベル数で前記ヒストグラムを近似する量子化処理を行う適応量子化装置であって、
前記区間の境界を示すクラス境界の候補を有意要素に制限する制限手段と、
前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するメモリ格納手段と、
次のクラスでの前記クラス境界を選択する際、非有意要素を前記近似誤差の累積値計算から除外し、前記メモリに格納した最小値を読み出す最小値読み出し手段と、
前記最小値を現時点での前記クラス境界の選択における前記近似誤差の累積値計算に用いることで、前記クラス境界の全要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択手段と
を備える適応量子化装置。
【請求項５】
コンピュータに、請求項１から３のいずれか１項に記載の適応量子化方法を実行させるための適応量子化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、適応量子化方法、適応量子化装置及び適応量子化プログラムに関する。
【背景技術】
【０００２】
近年、画像の高品質化に伴い、広ダイナミックレンジ映像への期待が高まっている。これを受けて、広ダイナミックレンジを有する画像信号に対する高いビット深度を用いた表現が検討されている。これに伴い、取得する信号のビット深度を従来の８ビットから１０ビット以上へと拡張した高ビット深度信号を取得可能なデバイスが登場してきている。
【０００３】
一方、画像信号の高ビット深度化により、画像の符号量が増大するため効率的な符号化手法が必要である。高ビット深度信号の符号化手法として、図６に示すような手法が提案されている。図６は、従来手法を用いた符号化装置の構成を示すブロック図である。図６に示す符号化装置においては、画像信号（Ｎｂｉｔ信号）を入力とし、ビット深度変換処理部１によってビット深度変換処理を行うことで低ビット深度信号に変換し、符号化処理部２、復号処理部３によって符号化・復号処理を行う。さらに、その復号画像に対し、逆ビット深度変換処理部４によって逆ビット深度変換処理を行い、高ビット深度画像を生成する。最後に、この高ビット深度画像と入力信号との差分信号を符号化器５によって符号化する。出力は、差分信号の符号化ストリームと、低ビット深度信号の符号化ストリーム（Ｎ−Δｂｉｔ符号化ストリーム）となる。このように従来手法は、ビット深度のスケーラブル符号化に対応した手法である。
【０００４】
図７は、図６に示す符号化装置を変形した構成を示すブロック図である。図７に示すような差分を出力しない方法もある。これは、画像信号（Ｎｂｉｔ信号）を入力とし、ビット深度変換処理部１によりビット深度変換処理を行うことで復号信号に変換する。そして、符号化処理部２、復号処理部３によって符号化・復号処理を行う。その後、低ビット深度画像に対し、逆ビット深度変換処理部４によって逆ビット深度変換処理を行い、高ビット深度画像を出力する。
【０００５】
図６に示す手法における符号化効率はビット深度変換処理に大きく依存する。同手法においては、入力信号と逆ビット深度変換処理後の信号の差分値の二乗和（以下、ビット深度変換誤差という）を抑えることで、出力信号の符号量を抑えることができる。ビット深度変換処理において、いくつかのＴｏｎｅ  Ｍａｐｐｉｎｇを用いた手法（例えば、非特許文献１参照）が提案されている。符号化効率向上のためには、ビット深度変換誤差を最小化するようにビット深度変換を設計する必要がある。
【０００６】
画素値の振幅方向の疎性に着目すると、画像によっては、与えられたビット深度によって表現可能な値を全て含まない場合がある。例えば、１０ビット信号の場合、０から１０２３までの１０２４種類の値を表現できる。振幅方向の疎性とは、画素値として画像内に含まれる値の種類が１０２４通り未満となる性質を指す。つまり、そうした画像では、画素値の頻度をヒストグラムとして表現した場合、頻度が零値になる画素値が存在する。なお、前述のビット深度変化処理は、ヒストグラムに対する一種の量子化処理とみなせる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】E. Reinhard, M. Stark, P. Shirley, and J. Ferwerda, "Photographic Tone Reproduction for Digital Images", In SIGGRAPH 2002 Conference Proceeding, ACM SIGGRAPH, Addison Wesley, pp. 267-277, August 2002
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前述したように、頻度が零値になる画素値は、ビット深度変換誤差に影響を与えない。しかし、従来手法では、上述の画素値の疎性に基づいた設計がなされておらず、計算量の低減に改善の余地を残しているという問題がある。
【０００９】
本発明は、このような事情に鑑みてなされたもので、ビット深度変換誤差の最適性を保持しつつ、演算量を低減することができる適応量子化方法、適応量子化装置及び適応量子化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の一態様は、入力信号のヒストグラムに対して、与えられたヒストグラムの区間の数を示すレベル数で前記ヒストグラムを近似する量子化処理を行う適応量子化装置が行う適応量子化方法であって、前記区間の境界を示すクラス境界の候補を有意要素に制限する制限ステップと、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するメモリ格納ステップと、次のクラスでの前記クラス境界を選択する際、非有意要素を前記近似誤差の累積値計算から除外し、前記メモリに格納した最小値を読み出す最小値読み出しステップと、前記最小値を現時点での前記クラス境界の選択における前記近似誤差の累積値計算に用いることで、前記クラス境界の全要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択ステップとを有する適応量子化方法である。
【００１１】
本発明の一態様は、前記適応量子化方法であって、前記非有意要素を前記クラス境界の候補から除外して前記有意要素をクラス境界の候補とする際に、前記クラス境界となり得ない前記有意要素を候補から除外するための前記クラス境界となり得る前記有意要素の上限及び下限を設ける上下限設定ステップと、前記上限及び前記下限の範囲に含まれる前記有意要素を前記クラス境界の候補とする。
【００１２】
本発明の一態様は、前記適応量子化方法であって、各クラスの境界が前記有意要素となる場合の近似誤差のみを参照テーブルに格納するテーブル格納ステップと、前記参照テーブルを参照して前記近似誤差の累積値の算出に用いる各クラス内の近似誤差を取得する。
【００１３】
本発明の一態様は、入力信号のヒストグラムに対して、与えられたヒストグラムの区間の数を示すレベル数で前記ヒストグラムを近似する量子化処理を行う適応量子化装置であって、前記区間の境界を示すクラス境界の候補を有意要素に制限する制限手段と、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するメモリ格納手段と、次のクラスでの前記クラス境界を選択する際、非有意要素を前記近似誤差の累積値計算から除外し、前記メモリに格納した最小値を読み出す最小値読み出し手段と、前記最小値を現時点での前記クラス境界の選択における前記近似誤差の累積値計算に用いることで、前記クラス境界の全要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択手段とを備える適応量子化装置である。
【００１４】
本発明の一態様は、コンピュータに、前記適応量子化方法を実行させるための適応量子化プログラムである。
【発明の効果】
【００１５】
本発明によれば、ビット深度変換誤差の最適性を保持しつつ、演算量を低減することができるという効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態による適応量子化処理の動作を示すフローチャートである。
【図２】演算量低減型適応量子化処理の動作を示すフローチャートである。
【図３】図２に示すステップＳ２０５について詳細な処理動作を示すフローチャートである。
【図４】適応量子化装置の構成を示すブロック図である。
【図５】演算量低減型適応量子化装置の構成を示すブロック図である。
【図６】従来手法を用いた符号化装置の構成を示すブロック図である。
【図７】図６に示す符号化装置を変形した構成を示すブロック図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して、本発明の一実施形態による適応量子化方法及び適応量子化装置を説明する。まず、適応量子化装置の基本動作原理について説明する。画素値ｋの頻度をｈ［ｋ］（ｋ＝０，・・・，Ｋ−１）として格納する。例えば、８ビットの輝度信号場合、ｋの取り得る範囲は０から２５５の値となる。このＫレベルの信号をＭレベル（Ｍ＜Ｋ）に量子化する場合を考える。以下、Ｋを入力レベル数、Ｍを量子化レベル数と呼ぶ。
【００１８】
求めるべきパラメータは、次式を満たすＭ個のパラメータである。
【数１】
0006368287.tif 000002
ここで、Ｌｍは、ヒストグラムにおける第ｍ区間の上端であり、次式で定義されるものとする。
【数２】
0006368287.tif 000003
ここで、Δｍはヒストグラムの第ｍ区間の区間幅を表す。また、量子化後の各階調が、少なくとも１つ以上、量子化前の階調を含む必要があることから、Ｌｍ（０≦ｍ≦Ｍ−２）はｍ≦Ｌｍ≦Ｋ−（Ｍ−ｍ）の範囲に制限される。ここで、ＬＭ−１はＬＭ−１＝Ｋ−１に固定されているので、Ｌｍについては、ｍ＝Ｍ−１を省略し、ｍ≦Ｍ−２を考えればよい。
【００１９】
ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）は次式で求まる値であり、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］を代表値ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）で近似した場合の近似誤差である。
【数３】
0006368287.tif 000004
【００２０】
さらに、＾ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）（＾は続く文字の上に付く、以下同様）は、次式で求まる実数値ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）を四捨五入して整数化した値である。
【数４】
0006368287.tif 000005
【００２１】
ｃ（Ｌｍ−１（Δｍ−１），Ｌｍ）は、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］における重心位置を表す。以下、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］を第ｍ量子化クラスと呼ぶ。
【００２２】
Ｍ個のパラメータ（Δ１，・・・，ΔＭ）の取り得る組み合わせは、Ｍとともに指数関数的に増加するため、この中から最適な組み合わせ（Δ＊１，・・・，Δ＊Ｍ）を総当りで探索するのは、計算量的に困難である。
【００２３】
そこで、本実施形態では、第ｍ量子化クラスの量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が同クラスの上端Ｌｍと同クラスの区間幅Δｍに依存することに着目し、以下のように最適解を算出する。さらに、その際、ヒストグラムの非有意要素に基づく演算量削減を行う。
【００２４】
次に、基本解法について説明する。まず、ヒストグラムの区間［０，Ｌｍ］をｍ＋１分割した際の近似誤差和Σｍｉ＝０ｅ（Ｌｉ−（Δｉ−１），Ｌｉ）の最小値をＳｍ（Ｌｍ）として定義する。つまり、最適なΔｍ，・・・，Δ０を用いた場合のΣｍｉ＝０ｅ（Ｌｉ−（Δｉ−１），Ｌｉ）に対する最小値である。ここで、ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が第ｍ量子化クラスの上端Ｌｍと同クラスの区間幅Δｍに依存することに着目すると、Ｓｍ（Ｌｍ）はＳｍ−１（Ｌｍ−Δｍ）を用いて、次式のように表わせる。
【数５】
0006368287.tif 000006
なお、ｍ＝０，・・・，Ｍ−１である。また、Ｌｍ＝ｍ，・・・，Ｋ−（Ｍ−ｍ）である。
【００２５】
Δｍの範囲は、次のようになる。Ｌｍ−１＝Ｌｍ−Δｍであることから、Ｌｍ−Δｍの範囲は、ｍ−１≦Ｌｍ−Δｍ≦Ｋ−（Ｍ−ｍ＋１）となる。このため、Δｍの範囲は、与えられたＬｍを用いて次式のよう表せる。
【数６】
0006368287.tif 000007
【００２６】
さらに、Δｍ≧１であることを考慮すると、次式を得る。
【数７】
0006368287.tif 000008
【００２７】
ここで、算出したＳｍ（Ｌｍ）を格納しておき、Ｓｍ＋１（Ｌｍ＋１）の計算で用いるものとする。さらに、式（５）の右辺を最小化するΔｍの値をΔｍ（Ｌｍ）として、各Ｌｍ（＝ｍ，・・・，Ｋ−Ｍ＋ｍ）に対して、＾Ｌｍ−１［Ｌｍ］＝Ｌｍ−Δｍ（Ｌｍ）を格納しておくものとする。
【００２８】
式（１）の最小化問題は、次式のように表せる。
【数８】
0006368287.tif 000009
上式を最小化するΔＭ−１をΔ＊Ｍ−１とおく（次式の通り）。
【数９】
0006368287.tif 000010
【００２９】
このΔ＊Ｍ−１を用いて、第Ｍ−２クラスの上端の最適値はＬ＊Ｍ−２＝ＬＭ−１−Δ＊Ｍ−１＝Ｋ−１−Δ＊Ｍ−１と求まる。第Ｍ−３クラスの上端の最適値は、Ｌ＊Ｍ−２に対する最適解として、＾ＬＭ−３［Ｌ＊Ｍ−２］として格納されているので、該当する値を参照し、Ｌ＊Ｍ−３＝＾ＬＭ−３［Ｌ＊Ｍ−２］とする。この結果、第Ｍ−２クラスの区間幅は、Δ＊Ｍ−２＝Ｌ＊Ｍ−２−Ｌ＊Ｍ−３と求まる。以下、同様の参照処理をＬ＊Ｍ−４＝＾ＬＭ−４［Ｌ＊Ｍ−３］，・・・，Ｌ＊０＝＾Ｌ０［Ｌ＊１］として繰り返し、得られた各クラスの上端値を用いて、Δ＊Ｍ−３＝Ｌ＊Ｍ−３−Ｌ＊Ｍ−４，・・・，Δ＊０＝Ｌ＊０−Ｌ＊−１として求める。なお、Ｌ＊−１＝−１である。
【００３０】
次に、視覚感度特性を考慮した重み付き歪み量の最小化について説明する。視覚系は、低輝度の画素値の変化に比べて、高輝度の画素値の変化に鈍感である。そこで、こうした視覚特性を考慮して量子化を行う場合は、以下のように行う。まず、画素値ｋ（ｋ＝０，・・・，Ｋ−１）に対する重み係数として、ｗ［ｋ］を設定する。この重み係数は、外部から与えられるものとする。例えば、高輝度（大きなｋ）の重みを低輝度（小さなｋ）の重みより小さな値に設定すれば、上記の輝度差に対する視覚特性を量子化処理に組み込むことが可能になる。この重み係数を用いて、画素値ｋに対する頻度ｈ［ｋ］を~ｈ［ｋ］＝ｗ［ｋ］ｈ［ｋ］（~は続く文字の上に付く、以下同様）として補正し、この補正後のヒストグラム~ｈ［ｋ］に対して、前述の量子化処理を実施する。
【００３１】
次に、ヒストグラムの非有意要素に基づく演算量削減について説明する。ヒストグラムの非有意要素（頻度値が零値となる要素）に着目した演算量削減手法を導入する。なお、以下では、ヒストグラムｈ［ｋ］（ｋ＝０，・・・，Ｋ−１）の要素を指定するインデックスｋを当該ヒストグラムの要素インデックスと呼び、ヒストグラムｈ［ｋ］の有意要素（~Ｋ個）を指定するインデックス~ｋ（~ｋ＝０，・・・，~Ｋ−１）を当該ヒストグラムの有意要素インデックスと呼ぶ。
【００３２】
画素値Ｌｍ＋１における頻度値ｈ［Ｌｍ＋１］が零値である場合、即ち、ｈ［Ｌｍ＋１］＝０の場合、ヒストグラムの区間［Ｌｍ−（Δｍ−１，Ｌｍ＋１］に対する近似誤差は、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］に対する近似誤差と等しい。ｈ［Ｌｍ＋１］＝０であることから、量子化の対象となる区間にｈ［Ｌｍ＋１］を加えたとしても、量子化による近似には影響を与えないためである。従って、ｈ［Ｌｍ＋１］＝０の場合、前述の式（５）に基づくＳ（Ｌｍ＋１）の算出は省略することが可能となる。
【００３３】
ヒストグラムの非有意要素に着目した適応処理の準備として、以下の参照テーブルを用意する。Ｚ［ｋ］（ｋ＝０，・・・，Ｋ−１）は、ヒストグラムの区間［０，ｋ］に含まれる非有意要素の個数を格納する。Ｆ［~ｋ］は、第~ｋ番目の非有意要素に対応する要素インデックスを格納する。Ψｕ［ｍ］（ｍ＝０，・・・，Ｍ−１）は第ｍビンの上端となりうる有意要素インデックスの最大値を格納する。
【００３４】
Ψｌ［ｍ］（ｍ＝０，・・・，Ｍ−１）は第ｍビンの上端となりうる有意要素インデックスの最小値を格納する。ここで、Ψｕ［ｍ］、Ψｌ［ｍ］（ｍ＝０，・・・，Ｍ−１）は各々、次のように設定される。
【数１０】
0006368287.tif 000011
【数１１】
0006368287.tif 000012
【００３５】
次に、最適解の求解について説明する。非有意要素に対する不要な演算を省略し、演算量を低減するために、有意要素インデックスを用いた最適解の求解アルゴリズムを以下に示す。以下では、Ｆ［~Ｌｍ］＝Ｌｍ，Ｆ［~Δｍ］＝Δｍとする。
【００３６】
ヒストグラムの区間［０，Ｆ［~Ｌｍ］］をｍ＋１分割した場合を考え、近似誤差ｅ（Ｆ［~Ｌｉ−（~Δｉ−１）］，Ｆ［~Ｌｉ］）を~ｅ（~Ｌｉ−（~Δｉ−１），~Ｌｉ）と定義し、近似誤差和Σｍｉ＝０~ｅ（~Ｌｉ−（~Δｉ−１），~Ｌｉ）の最小値を~Ｓｍ（~Ｌｍ）として定義する。つまり、最適な~Δｍ，・・・，~Δ０を用いた場合のΣｍｉ＝０~ｅ（~Ｌｉ−（~Δｉ−１），~Ｌｉ）に対する最小値である。なお、~Ｓｍ（~Ｌｍ）はＳｍ（Ｆ［~Ｌｍ］）と等しい。ここで、~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）が第ｍ量子化クラスの上端の有意要素インデックス~Ｌｍと同クラスの区間幅内の有意要素数~Δｍに依存することに着目すると、~Ｓｍ（~Ｌｍ）は~Ｓｍ−１（~Ｌｍ−~Δｍ）を用いて、次式のように表わせる。
【数１２】
0006368287.tif 000013
なお、ｍ＝０，・・・，Ｍ−１である。また、~Ｌｍ＝Ψｌ［ｍ］，・・・，Ψｕ［ｍ］である。
【００３７】
~Δｍの範囲は、次のようになる。~Ｌｍ−１＝~Ｌｍ−~Δｍであることから、~Ｌｍ−~Δｍの範囲は、Ψｌ［ｍ−１］≦~Ｌｍ−~Δｍ≦Ψｕ［ｍ−１］となる。このため、~Δｍの範囲は、与えられた~Ｌｍを用いて次式のよう表せる。
【数１３】
0006368287.tif 000014
【００３８】
さらに、~Δｍ≧１であることを考慮すると、次式を得る。
【数１４】
0006368287.tif 000015
ここで、算出した~Ｓｍ（~Ｌｍ）を格納しておき、~Ｓｍ＋１（~Ｌｍ＋１）の計算で用いるものとする。さらに、式（１２）の右辺を最小化する~Δｍを~Δｍ（~Ｌｍ）  とし、第ｍビンの上端を~Ｌｍとした場合の最適な第ｍ−１ビンの上端として、~Ｌｍ−１［~Ｌｍ］＝~Ｌｍ−~Δｍ（~Ｌｍ）を各~Ｌｍ（＝Ψｌ［ｍ］，・・，Ψｕ［ｍ］）に対して格納しておくものとする。
【００３９】
式（１）の最小化問題は、次式のように表せる。
【数１５】
0006368287.tif 000016
ここで、~Ｋ＝Ｋ−Ｚ［Ｋ−１］である。上式を最小化する~ΔＭ−１を~Δ＊Ｍ−１
とおく（次式の通り）。
【数１６】
0006368287.tif 000017
【００４０】
~ＬＭ−１の取り得る値は、Ｋ−Ｚ［Ｋ−１］−１のみであることから、~ＬＭ−１＝Ｋ−Ｚ［Ｋ−１］−１となる。~ＬＭ−１及び~Δ＊Ｍ−１を用いて、第Ｍ−２クラスの上端の有意要素インデックスの最適値は~Ｌ＊Ｍ−２＝＝ＬＭ−１−~Δ＊Ｍ−１＝Ｋ−Ｚ［Ｋ−１］−１−~Δ＊Ｍ−１と求まる。第Ｍ−３クラスの上端の有意要素インデックスの最適値は、~Ｌ＊Ｍ−２に対する最適解として、＾ＬＭ−３［~Ｌ＊Ｍ−２］として格納されているので、該当する値を参照し、~Ｌ＊Ｍ−３＝＾ＬＭ−３［~Ｌ＊Ｍ−２］とする。この結果、第Ｍ−２クラスの区間幅内の有意要素数は、~Δ＊Ｍ−２＝~Ｌ＊Ｍ−２−~Ｌ＊Ｍ−３と求まる。
【００４１】
以下、同様の参照処理を~Ｌ＊Ｍ−４＝＾ＬＭ−４［~Ｌ＊Ｍ−３］，・・・，~Ｌ＊０＝＾Ｌ０［~Ｌ＊１］として繰り返し、得られた各クラスの上端の有意要素インデックスを用いて、~Δ＊Ｍ−３＝~Ｌ＊Ｍ−３−~Ｌ＊Ｍ−４，・・・，~Δ＊０＝~Ｌ＊０−~Ｌ＊−１として求める。なお、~Ｌ＊−１＝−１である。各クラスの上端の有意要素インデックス~ＬＭ−１，~Ｌ＊Ｍ−２，・・・，~Ｌ＊０から、Ｆ［~ＬＭ−１］，Ｆ［~ＬＭ−１］，Ｆ［~Ｌ＊Ｍ−２］，・・・，Ｆ［~Ｌ＊０］により、各クラスの上端が求まる。
【００４２】
次に、量子化誤差のルックアップテーブルへの格納について説明する。ＬｍとΔｍの組み合わせによっては、異なる量子化クラス（ｍの値が異なるという意味）において、量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が必要となる。その度に、量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）を算出するのは、計算コストの観点から得策ではない。計算結果を格納し、必要に応じて格納結果を呼び出すことで、演算量を低減できる。
【００４３】
そこで、ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）として取りうる値をルックアップテーブル（Ｍ×Ｋ要素）に格納する。格納処理は、以下のようになる。
１．ｆｏｒ  ~ｉｓ＝０，・・・，Ｋ−Ｚ［Ｋ−１］−２
２．    ｆｏｒ  ~ｉｅ＝~ｉｓ＋１，・・・，ｍｉｎ（~ｉｓ＋Ｋ−Ｚ［Ｋ−１］−Ｍ−１，Ｋ−Ｚ［Ｋ−１］−１）  
３．        Ｅ［~ｉｓ，~ｉｅ］←ｅ（Ｆ［~ｉｓ］，Ｆ［~ｉｅ］）
ここで、←は値の代入を表す。
【００４４】
上述のルックアップテーブル（（Ｋ−Ｚ［Ｋ−１］−１）×（Ｋ−Ｚ［Ｋ−１］）要素）Ｅ［~ｉｓ，~ｉｅ］へ格納する量子化誤差ｅ（Ｆ［~ｉｓ］，Ｆ［~ｉｅ］）の計算過程にも重複した計算が存在するため、そうした重複部分を省略することで、演算量の低減を図る。
【００４５】
まず、以下の値を定義する。
【数１７】
0006368287.tif 000018
【数１８】
0006368287.tif 000019
【数１９】
0006368287.tif 000020
【００４６】
これらを用いて、重心位置ｃ（~ｉｓ，Ｌｍ）、量子化誤差ｅ（~ｉｓ，Ｌｍ）を再定義すると、次のようになる。
【数２０】
0006368287.tif 000021
【数２１】
0006368287.tif 000022
【００４７】
これより、ｃ（~ｉｓ，~ｉｅ）及びｅ（~ｉｓ，~ｉｅ）が以下の漸化関係を持つことが分かる。
【数２２】
0006368287.tif 000023
【数２３】
0006368287.tif 000024
【００４８】
上記の関係に基づきｅ（~ｉｓ，~ｉｅ）を算出し、算出結果をルックアップテーブル（（Ｋ−Ｚ［Ｋ−１］−１）×（Ｋ−Ｚ［Ｋ−１］）要素）に格納する。
【００４９】
次に、図１を参照して、前述した基本原理に基づく適応量子化処理の動作を説明する。図１は、適応量子化処理の動作を示すフローチャートである。この適応量子化処理は、コンピュータ装置が行う処理である。まず、入力信号を読み込み、入力信号値のヒストグラムを生成する（ステップＳ１０１）。
【００５０】
次に、ヒストグラムの要素インデックスをｋ、ヒストグラムの有意要素インデックスを~ｋとし、このｋと~ｋの対応関係を格納した参照テーブルとして、Ｆ［~ｋ］を生成する（ステップＳ１０２）。具体的な生成方法は、以下の通りである。
１．~ｋ←０
２．ｆｏｒ  ｋ＝０，・・・，Ｋ−１  
３．    ｉｆ  ｈ［ｋ］≠０  
４．        Ｆ［~ｋ］←ｋ  
５．        ~ｋ←~ｋ＋１  
４．、５．の処理は、３．の判定式が真の時に実行する。
【００５１】
次に、ヒストグラムの区間［０，ｋ］に含まれる非有意要素の個数を格納した参照テーブルとして、Ｚ［ｋ］を生成する（ステップＳ１０３）。具体的な生成方法は、以下の通りである。
１．ｊ←０  
２．ｆｏｒ  ｋ＝０，・・・，Ｋ−１  
３．    ｉｆ  ｈ［ｋ］＝０  
４．        ｊ←ｊ＋１  
５．        Ｚ［ｋ］←ｊ  
【００５２】
次に、非有意係数をスキップすることに伴うＬｍの最大値を格納した参照テーブルとして、Ψｕ［ｍ］（ｍ＝０，・・・，Ｍ−１）を生成する。具体的には、ヒストグラムの第ｋ要素までに含まれる非有意要素の個数Ｚ［ｋ］を用いて、次式により設定する（ステップＳ１０４）。
Ψｕ［ｍ］＝  ｍ−Ｍ＋Ｋ−Ｚ［ｍ−Ｍ＋Ｋ］（ｍ＝０，・・・，Ｍ−１）
【００５３】
また、非有意係数をスキップすることに伴うＬｍの最小値を格納した参照テーブルとして、Ψｌ［ｍ］（ｍ＝０，・・・，Ｍ−１）を生成する。具体的には、次式により設定する。
【数２４】
0006368287.tif 000025
【００５４】
次に、ステップＳ１０７までの処理をｊ＝１，・・・，Ｋ−Ｍ−１−Ｚ［Ｋ−Ｍ−１］として繰り返す（ステップＳ１０５）。そして、ヒストグラムの区間［０、Ｆ［ｊ］］を代表値（式（４）により求まる重心）で近似した場合の近似誤差~ｅ［０，ｊ］を求め、同近似誤差をＳ０（ｊ）に格納する（ステップＳ１０６）。
【００５５】
次に、ステップＳ１１８までの処理をｍ＝１，・・・，Ｍ−１として繰り返す（ステップＳ１０８）。そして、ステップＳ１１７までの処理を~Ｌｍ＝Ψｌ［ｍ］，・・・，Ψｕ［ｍ］として繰り返す（ステップＳ１０９）。さらに、ステップＳ１１４までの処理を~Δｍ＝１，・・・，~Ｌｍ−Ψｌ（ｍ−１）として繰り返す（ステップＳ１１０）。
【００５６】
次に、ヒストグラムの区間［Ｆ［~Ｌｍ−（~Δｍ−１）］，Ｆ［~Ｌｍ］］の代表値を式（４）により求める（ステップＳ１１１）。続いて、ヒストグラムの区間［Ｆ［~Ｌｍ−（~Δｍ−１）］，Ｆ［~Ｌｍ］］を代表値（ステップＳ１１１で求めた値）で近似した場合の近似誤差を式（３）より求める（ステップＳ１１２）。同近似誤差を~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）とする。
【００５７】
次に、~Ｓｍ−１（~Ｌｍ−~Δｍ）＋~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）の値を計算する（ステップＳ１１３）。続いて、~Ｓｍ−１（~Ｌｍ−~Δｍ）＋~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）（~Δｍ＝１，・・・，~Ｌｍ−（ｍ−１））の中での最小値を~Ｓｍ（~Ｌｍ）に格納する（ステップＳ１１５）。
【００５８】
次に、~Ｓｍ−１（~Ｌｍ−~Δｍ）＋~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）（~Δｍ＝１，・・・，~Ｌｍ−（ｍ−１））を最小化する~Δｍを用いて、~Ｌｍ−~Δｍを＾Ｌｍ−１（~Ｌｍ）に格納する（ステップＳ１１６）。＾Ｌｍ−１（~Ｌｍ）を最適パス追跡用参照テーブルと呼ぶ。
【００５９】
次に、Ｌ＊Ｍ−１にＫ−１を代入する。また、~Ｌ＊Ｍ−１にＫ−Ｚ［Ｋ−１］−１を代入する（ステップＳ１１９）。
【００６０】
次に、ステップＳ１２２までの処理をｍ＝Ｍ−１、・・・，１として繰り返す（ステップＳ１２０）。そして、＾Ｌｍ−１（~Ｌ＊ｍ）を読み込み、~Ｌ＊ｍ−１に代入する。また、Ｆ［~Ｌ＊ｍ−１］を読み込み、Ｌ＊ｍ−１に代入する（ステップＳ１２１）。
【００６１】
次に、図２を参照して、演算量低減型適応量子化処理の動作を説明する。図２は、演算量低減型適応量子化処理の動作を示すフローチャートである。図２に示す処理動作は、コンピュータ装置において、近似誤差を参照テーブルに格納し、適宜、同参照テーブルから近似誤差を読み込む形に拡張した適応量子化処理の動作である。
【００６２】
ステップＳ２０１−Ｓ２０４の処理動作は、図１に示すステップＳ１０１−Ｓ１０４と同じであるため、ここでは説明を省略する。
【００６３】
次に、ヒストグラムの各区間を代表値で近似した際の近似誤差を格納した参照テーブルを生成する（ステップＳ２０５）。なお、ステップＳ２０５の処理については、後で詳述する。
【００６４】
ステップＳ２０６−Ｓ２１２の処理動作は、図１に示すステップＳ１０５−Ｓ１１１と同じであるため、ここでは説明を省略する。
【００６５】
次に、ヒストグラムの区間［Ｆ［~Ｌｍ−（~Δｍ−１）］，Ｆ［~Ｌｍ］］を代表値で近似した場合の近似誤差を参照テーブルＥ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）から読み込む（ステップＳ２１３）。
【００６６】
次に、~Ｓｍ−１（~Ｌｍ−~Δｍ）＋Ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）の値を計算する（ステップＳ２１４）。
【００６７】
次に、~Ｓｍ−１（~Ｌｍ−~Δｍ）＋Ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）（~Δｍ＝１，・・・，~Ｌｍ−（ｍ−１））の中での最小値を~Ｓｍ（~Ｌｍ）に格納する（ステップＳ２１６）。
次に、~Ｓｍ−１（~Ｌｍ−~Δｍ）＋Ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）（~Δｍ＝１，・・・，~Ｌｍ−（ｍ−１））を最小化する~Δｍを用いて、~Ｌｍ−~Δｍを＾Ｌｍ−１（~Ｌｍ）に格納する（ステップＳ２１７）。
【００６８】
ステップＳ２２０−Ｓ２２３は、図１に示すステップＳ１１９−Ｓ１２２と同じであるため、ここでは説明を省略する。
【００６９】
次に、図３を参照して、図２に示すステップＳ２０５について詳細な処理動作を説明する。図３は、図２に示すステップＳ２０５について詳細な処理動作を示すフローチャートである。
【００７０】
まず、入力信号のヒストグラムを読み込む（ステップＳ３０１）。そして、参照テーブルＺ［ｋ］（ｋ＝０，・・・，Ｋ−１）、Ｆ［~ｋ］（~ｋ＝０，・・・，Ｋ−Ｚ［Ｋ−１］−１）を読み込む（ステップＳ３０２）。
【００７１】
次に、ステップＳ３０５までの処理を~ｋ＝１，・・・，Ｋ−Ｚ［Ｋ−１］−１として繰り返す（ステップＳ３０３）。そして、ｑ１［０，~ｋ］，ｑ２［０，~ｋ］，ｑ３［０，~ｋ］に０を格納する（ステップＳ３０４）。
【００７２】
次に、ステップＳ３１６までの処理を~ｉｓ＝０，・・・，Ｋ−Ｚ［Ｋ−１］−２として繰り返す（ステップＳ３０６）。そして、~ｉｓ＋Ｋ−Ｚ［Ｋ−１］−Ｍ−１とＫ−Ｚ［Ｋ−１］−１を比較して、小さい方の値を変数Ｕに格納する（ステップＳ３０７）。
【００７３】
次に、ステップＳ３１５までの処理を~ｉ＝~ｉ＋１，・・・，Ｕとして繰り返す（ステップＳ３０８）。そして、参照テーブルＦ［~ｉｅ］を読み込み、ｉｅにＦ［~ｉｅ］を代入する。また、参照テーブルＦ［~ｉｓ］を読み込み、ｉｓにＦ［~ｉｓ］を代入する（ステップＳ３０９）。
【００７４】
次に、ｑ１［ｉｓ，ｉｅ−１］、ｈ［ｉｅ］を読み込み、ｑ１［ｉｓ，ｉｅ−１］＋ｈ［ｉｅ］を算出し、算出結果をｑ１［ｉｓ，ｉｅ］に格納する（ステップＳ３１０）。続いて、ｑ２［ｉｓ，ｉｅ−１］，ｈ［ｉｅ］，ｉｅを読み込み、ｑ２［ｉｓ，ｉｅ−１］＋ｉｅｈ［ｉｅ］を算出し、算出結果をｑ２［ｉｓ，ｉｅ］に格納する（ステップＳ３１１）。
【００７５】
次に、ｑ３［ｉｓ，ｉｅ−１］、ｈ［ｉｅ］、ｉｅを読み込み、ｑ３［ｉｓ，ｉｅ−１］＋ｉ２ｅｈ［ｉｅ］を算出し、算出結果をｑ３［ｉｓ，ｉｅ］に格納する（ステップＳ３１２）。続いて、ｑ２［ｉｓ，ｉｅ−１］、ｑ３［ｉｓ，ｉｅ−１］を読み込み、ｑ２［ｉｓ，ｉｅ］／ｑ１［ｉｓ，ｉｅ］を算出し、算出結果をｃ［ｉｓ，ｉｅ］に格納する（ステップＳ３１３）。
【００７６】
次に、ｑ１［ｉｓ，ｉｅ−１］，ｑ２［ｉｓ，ｉｅ−１］，ｑ３［ｉｓ，ｉｅ−１］，ｃ［ｉｓ，ｉｅ］を読み込み、ｑ３［ｉｓ，ｉｅ］−２ｃ［ｉｓ，ｉｅ］ｑ２［ｉｓ，ｉｅ］＋ｃ［ｉｓ，ｉｅ］２ｑ１［ｉｓ，ｉｅ］を算出し、算出結果をＥ［~ｉｓ，~ｉｅ］に格納する（ステップＳ３１４）。
【００７７】
次に、図４を参照して、適応量子化装置の構成について説明する。図４は、適応量子化装置の構成を示すブロック図である。ヒストグラム生成部４００は、入力信号を入力として読み込み、入力信号のヒストグラムを生成し、入力信号のヒストグラム及び入力信号のレベル数Ｋをヒストグラム・入力信号素数記憶部４０１に格納する。量子化クラス数記憶部４０２は、量子化クラス数Ｍを格納する。
【００７８】
要素インデックス参照テーブル生成部４０３は、ヒストグラムの要素インデックスをｋ、ヒストグラムの有意要素インデックスを~ｋとし、このｋと~ｋの対応関係を格納した参照テーブルとして、Ｆ［~ｋ］を生成する。そして、この参照テーブルを要素インデックス記憶部４０４に格納する。具体的な参照テーブルの生成方法は、図１に示すステップＳ１０２の通りである。
【００７９】
非有意要素数参照テーブル生成部４０５は、ヒストグラムの区間［０，ｋ］に含まれる非有意要素の個数を格納した参照テーブルとして、Ｚ［ｋ］を生成する。そして、この参照テーブルを非有意要素数記憶部４０６に格納する。具体的な参照テーブルの生成方法は、図１に示すステップＳ１０３の通りである。
【００８０】
量子化クラス上界値参照テーブル生成部４０７は、第ｍクラスの有意要素インデックスの最大値を格納した参照テーブルとして、Ψｕ［ｍ］（ｍ＝０，・・・，Ｍ−１）を生成する。そして、この参照テーブルを量子化クラス上界値記憶部４０８に格納する。具体的な参照テーブルの生成方法は、図１に示すステップＳ１０４の通りである。
【００８１】
量子化クラス下界値参照テーブル生成部４０９は、第ｍクラスの有意要素インデックスの最小値を格納した参照テーブルとして、Ψｌ［ｍ］（ｍ＝０，・・・，Ｍ−１）を生成する。そして、この参照テーブルを量子化クラス下界値記憶部４１０に格納する。具体的な参照テーブルの生成方法は、図１に示すステップＳ１０４の通りである。
【００８２】
近似誤差算出部４１１は、入力信号のヒストグラム、入力信号のレベル数、量子化クラス数、要素インデックスの参照テーブル、非有意要素数の参照テーブル、量子化クラスの上界値の参照テーブル、量子化クラスの下界値の参照テーブルを入力として、ヒストグラムを量子化クラス数で指定されたクラス数に分割した場合の近似誤差の最小値を算出し、この最小値を近似誤差最小値記憶部４１２に格納する。また、各量子化クラスにおいて近似誤差の累積値を最小化するクラスの上端を表す有意要素インデックスを、最適パス追跡用参照テーブルとして、量子化クラス上端最適値記憶部４１３に格納する。具体的な処理は、図１に示すステップＳ１０５〜Ｓ１１８の通りである。
【００８３】
量子化クラス上端最適値追跡部４１４は、入力信号のレベル数、量子化クラス数、要素インデックス参照テーブル、有意要素数参照テーブル、最適パス追跡用参照テーブルを入力として、近似誤差の最小値を実現する際のクラスの上端を表す要素インデックスを算出する。具体的な処理は、図１に示すステップＳ１１９〜Ｓ１２２の通りである。
【００８４】
次に、図５を参照して、近似誤差を参照テーブルに格納し、適宜、同参照テーブルから近似誤差を読み込む形に拡張した演算量低減型適応量子化装置の構成を説明する。図５は、演算量低減型適応量子化装置の構成を示すブロック図である。図５において、図４に示す装置と同一の部分には同一の符号を付し、その説明を省略する。図５に示す装置が図４に示す装置と異なる点は、近似誤差最小値算出部５１１、量子化クラス上端最適値追跡部５１４、近似誤差算出部５１５、近似誤差記憶部５１６が設けられている点である。
【００８５】
近似誤差最小値算出部５１１は、入力信号のヒストグラム、入力信号のレベル数、量子化クラス数、要素インデックスの参照テーブル、非有意要素数の参照テーブル、量子化クラスの上界値の参照テーブル、量子化クラスの下界値の参照テーブル近似誤差の参照テーブルを入力として、ヒストグラムを量子化クラス数で指定されたクラス数に分割した場合の近似誤差の最小値を算出し、この最小値を近似誤差最小値記憶部４１２に格納する。また、各量子化クラスにおいて近似誤差の累積値を最小化するクラスの上端を表す有意要素インデックスを、最適パス追跡用参照テーブルとして、量子化クラス上端最適値記憶部４１３に格納する。具体的な処理は、図２に示すステップＳ２０６〜Ｓ２１９の通りである。
【００８６】
量子化クラス上端最適値追跡部５１４は、入力信号のレベル数、量子化クラス数、要素インデックス参照テーブル、有意要素数参照テーブル、最適パス追跡用参照テーブルを入力として、近似誤差の最小値を実現する際のクラスの上端を表す要素インデックスを算出する。具体的な処理は、図２に示すステップＳ２２０〜Ｓ２２３の通りである。
【００８７】
近似誤差算出部５１５は、入力信号のヒストグラム、入力信号のレベル数、量子化クラス数、要素インデックスの参照テーブル、非有意要素数の参照テーブルを入力として、近似誤差を算出し、近似誤差の参照テーブルとして、算出して近似誤差を近似誤差記憶部５１６に格納する。具体的な処理は、図３に示す通りである。
【００８８】
次に、適応量子化処理の基本処理について説明する。非有意係数に対する不要な処理を削除した適応量子化処理は以下のようになる。
【００８９】
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．量子化後のクラス数Ｍを読み込む。
３．参照テーブルＺ［ｋ］（ｋ＝０，・・・，Ｋ−１）、Ψｌ［ｍ］，Ψｕ［ｍ］（ｍ＝０，・・・，Ｍ−１），Ｆ［~ｋ］（~ｋ＝０，・・・，Ｋ−Ｚ［Ｋ−１］−１）を生成する。
４．ｆｏｒ  ｊ＝０，・・・，Ｋ−Ｍ−１−Ｚ［Ｋ−Ｍ−１］  
５．    ヒストグラムの区間［０，Ｆ［ｊ］］を代表値（式（４）により求まる重心）で近似した場合の近似誤差を求め、同近似誤差をＳ０（ｊ）に格納する。
【００９０】
６．ｆｏｒ  ｍ＝１，・・・，Ｍ−１  
７．    ｆｏｒ  ~Ｌｍ＝Ψｌ［ｍ］，・・・，Ψｕ［ｍ］  
８．        ｆｏｒ  ~Δｍ＝１，・・・，~Ｌｍ−Ψｌ（ｍ−１）  
９．            ヒストグラムの区間［Ｆ［~Ｌｍ−（~Δｍ−１）］，Ｆ［~Ｌｍ］］を代表値で近似した場合の近似誤差を求める。代表値は式（４）により求め、同近似誤差は式（３）より求める。同近似誤差を~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）とする。
１０．          ~Ｓｍ−１（~Ｌｍ−~Δｍ）＋~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）の値を計算する。
１１．  ~Ｓｍ−１（~Ｌｍ−~Δｍ）＋~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）（~Δｍ＝１，・・・，~Ｌｍ−（ｍ−１））の中での最小値を~Ｓｍ（~Ｌｍ）に格納する。
１２．  ~Ｓｍ−１（~Ｌｍ−~Δｍ）＋~ｅ（~Ｌｍ−（~Δｍ−１），~Ｌｍ）（~Δｍ＝１，・・・，~Ｌｍ−（ｍ−１））を最小化する~Δｍを用いて、~Ｌｍ−~Δｍを＾Ｌｍ−１（~Ｌｍ）に格納する。
【００９１】
１３．Ｌ＊Ｍ−１←Ｋ−１
１４．~Ｌ＊Ｍ−１←Ｋ−Ｚ［Ｋ−１］−１
１５．ｆｏｒ  ｍ＝Ｍ−１，・・・，１  
１６．    ＾Ｌｍ−１（~Ｌ＊ｍ）を読み込み、~Ｌ＊ｍ−１←＾Ｌｍ−１（~Ｌ＊ｍ）とする。
１７．    Ｌ＊ｍ−１←Ｆ［~Ｌ＊ｍ−１］  
【００９２】
次に、演算量低減処理を伴う適応量子化処理の動作を説明する。前述のルックアップテーブルを参照する方式の場合は、以下のようになる。
【００９３】
１．入力信号のヒストグラム（クラス数Ｋ）を生成する。
２．量子化後のクラス数Ｍを読み込む。
３．参照テーブルＺ［ｋ］（ｋ＝０，・・・，Ｋ−１），Ψｌ［ｍ］，Ψｕ［ｍ］（ｍ＝０，・・・，Ｍ−１），Ｆ［~ｋ］（~ｋ＝０，・・・，Ｋ−Ｚ［Ｋ−１］−１）を生成する。
４．後述する「近似誤差参照テーブル生成処理」に基づき、近似誤差を格納した参照テーブルＥ［~ｉｓ，~ｉｅ］を生成する。
５．ｆｏｒ  ｊ＝０，・・・，Ｋ−Ｍ−１−Ｚ［Ｋ−Ｍ−１］  
６．    Ｓ０（ｊ）←Ｅ［０，ｊ］
７．適応量子化処理の基本処理の６．以降の処理を実施する。
【００９４】
次に、近似誤差参照テーブル生成処理について説明する。  
１．ｆｏｒ  ~ｋ＝０，・・・，Ｋ−Ｚ［Ｋ−１］−１
２．ｑ１［０，~ｋ］←０
３．ｑ２［０，~ｋ］←０
４．ｑ３［０，~ｋ］←０
５．ｆｏｒ  ~ｉｓ＝０，・・・，Ｋ．Ｚ［Ｋ−１］−２
６．    ｆｏｒ  ~ｉｅ＝ｉｓ＋１，・・・，ｍｉｎ（ｉｓ＋Ｋ．Ｚ［Ｋ−１］−Ｍ−１，Ｋ−Ｚ［Ｋ−１］−１）
７．        ｉｅ＝Ｆ［~ｉｅ］
８．        ｉｓ＝Ｆ［~ｉｓ］
９．        ｑ１［ｉｓ，ｉｅ］←ｑ１［ｉｓ，ｉｅ−１］＋ｈ［ｉｅ］
１０．      ｑ２［ｉｓ，ｉｅ］←ｑ２［ｉｓ，ｉｅ−１］＋ｉｅｈ［ｉｅ］
１１．      ｑ３［ｉｓ，ｉｅ］←ｑ３［ｉｓ，ｉｅ−１］＋ｉ２ｅｈ［ｉｅ］
１２．      ｃ［ｉｓ，ｉｅ］←ｑ２［ｉｓ，ｉｅ］／ｑ１［ｉｓ，ｉｅ］
１３．      Ｅ［~ｉｓ，~ｉｅ］←ｑ３［ｉｓ，ｉｅ］−２ｃ［ｉｓ，ｉｅ］ｑ２［ｉｓ，ｉｅ］＋ｃ［ｉｓ，ｉｅ］２ｑ１［ｉｓ，ｉｅ］  
【００９５】
以上説明したように、画像信号符号化の際のビット深度変換技術のうち、画素値の出現頻度を示すヒストグラムの量子化としてビット深度を変換する（画素値の出現範囲を０〜Ｋ−１から０〜Ｍ−１に減少させることにより（Ｋ：入力レベル数＞Ｍ：量子化レベル数）、ビット深度を低くする）ようにした。このように、出現頻度がゼロとなる画素値を考慮してヒストグラムの区間分割を決定することにより、ビット深度変換に伴う誤差の最適性を維持しつつもビット深度変換に伴う演算量を低減することができる。そのため、階調変換に伴う変換誤差の最小化を維持しつつ、階調変換を実現するための演算量を低減することが可能となる。
【００９６】
前述した実施形態における適応量子化装置の全部または一部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＰＬＤ（Programmable Logic Device）やＦＰＧＡ（Field Programmable Gate Array）等のハードウェアを用いて実現されるものであってもよい。
【００９７】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。したがって、本発明の技術思想及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行ってもよい。
【産業上の利用可能性】
【００９８】
ビット深度変換誤差の最適性を保持しつつ、演算量を低減することが不可欠な用途に適用できる。
【符号の説明】
【００９９】
４００・・・ヒストグラム生成部、４０１・・・ヒストグラム・入力信号要素数記憶部、４０２・・・量子化クラス数記憶部、４０３・・・要素インデックス参照テーブル生成部、４０４・・・要素インデックス記憶部、４０５・・・非有意要素数参照テーブル生成部、４０６・・・非有意要素数記憶部、４０７・・・量子化クラス上界値参照テーブル生成部、４０８・・・量子化クラス上界値記憶部、４０９・・・量子化クラス下界値参照テーブル生成部、４１０・・・量子化クラス下界値記憶部、４１１・・・近似誤差算出部、４１２・・・近似誤差最小値記憶部、４１３・・・量子化クラス上端最適値記憶部、４１４・・・量子化クラス上端最適値追跡部、５１１・・・近似誤差最小値算出部、５１４・・・量子化クラス上端最適値追跡部、５１５・・・近似誤差算出部、５１６・・・近似誤差記憶部
【図１】
0006368287.tif 000026
【図２】
0006368287.tif 000027
【図３】
0006368287.tif 000028
【図４】
0006368287.tif 000029
【図５】
0006368287.tif 000030
【図６】
0006368287.tif 000031
【図７】
0006368287.tif 000032