(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．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前記のビット深度変換処理は，一種の量子化処理とみなせる。従来手法では，ビット深度変換処理後の画像に対する主観画質の保持が目的であり，ビット深度変換誤差が最小となる保証はない。符号化効率向上のためには，ビット深度変換誤差を最小化するようにビット深度変換を設計する必要がある。
【０００８】
本発明はかかる事情に鑑みてなされたものであって，画像信号の階調変換を行う際に発生する変換誤差を最小化する量子化方法を確立することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の適応量子化方法は，前記課題を解決するため，クラス数がＫの入力信号を，Ｋより小さいＭのクラス数に量子化する適応量子化方法であって，入力信号についてクラス数Ｋのヒストグラムを生成するステップと，与えられたクラス数Ｍで前記ヒストグラムを近似する際に，最初のクラスに対するクラス境界の候補の中から近似誤差を最小化する量子化値に対応するクラス境界およびそのときの近似誤差の最小値を算出し，メモリに格納するとともに，前記最小値を算出済みの第ｍ−１番目（ｍ＝１，２，…，Ｍ−２）のクラス境界の次の第ｍ番目のクラスでのクラス境界を算出する際，前記格納した最小値をメモリから読み出し，前記最小値を前記第ｍ番目のクラス境界の算出における近似誤差の計算に用いて，最初のクラスから前記第ｍ番目のクラスまでの近似誤差を最小化するクラス境界を算出し，そのときのクラス境界と近似誤差の最小値とをメモリに格納するステップと，前記メモリに格納するステップを，最終のクラス境界まで前記ｍを１ずつ増やしながら順番に繰り返すことにより，クラス境界の全候補に対して近似誤差を最小化するクラス境界を算出するステップと，最終的に算出したクラス境界を用いて入力信号を量子化するステップとを有することを特徴とする。
【００１０】
前記発明において，前記近似誤差として，クラス数Ｍの各クラスの代表値と当該各クラスにおける入力信号の値との誤差の絶対値和または二乗和を算出することができる。
また，前記発明において，前記近似誤差として，クラス数Ｍの各クラスの代表値と当該各クラスにおける入力信号の値に対して視覚感度に基づき重み付けされた値との誤差の絶対値和または二乗和を算出することも好適である。
さらに，前記いずれかの発明において，前記クラス数Ｍのクラス境界の幅を予め定められた閾値以下の範囲内でクラス境界を設定し，前記近似誤差の最小値を探索するようにしてもよい。
さらに，前記いずれかの発明において，前記近似誤差として取り得る値を予め算出してルックアップテーブルに格納し，前記ルックアップテーブルを参照して，前記クラス境界の候補に対する近似誤差を得ることができる。このとき，前記ルックアップテーブルに格納する近似誤差の算出において近似誤差計算の漸化関係により重複した演算を省略することもできる。
【発明の効果】
【００１１】
本発明により，画像信号の階調変換を行う際に発生する変換誤差を最小化することが可能となり，ビット深度変換を用いた画像符号化器における符号化効率の向上が可能となる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に係る装置構成例を示す図である。
【図２】本発明の一実施形態に係る量子化フローチャートである。
【図３】従来の高ビット深度信号の符号化手法の例を示す図である。
【図４】従来の他の高ビット深度信号の符号化手法の例を示す図である。
【発明を実施するための形態】
【００１３】
以下，本発明による手法を，以下の１〜４の項目の順番で説明し，その後に具体的な実施例について，図面を用いて詳細に説明する。
１．基本解法
２．区間幅Δの範囲を制限した準最適化法
３．高速算法
・ルックアップテーブルを用いた演算量低減法
・近似誤差計算の漸化関係を用いた演算量低減法
４．輝度の視覚感度特性を考慮した重み付き歪み量の最小化
なお，「区間幅Δの範囲を制限した準最適化法」とは，式（８）に示すように，Δの範囲を制限することで，探索範囲を限定し，演算量の削減を図ることを指す。
【００１４】
［基本解法，および，区間幅Δの範囲を制限した準最適化法］
画素値ｋの頻度をｈ［ｋ］（ｋ＝０，…，Ｋ−１）として格納する。例えば，8 ビットの輝度信号の場合，ｋの取り得る範囲は０から２５５の値となる。このＫ階調の信号をＭ階調（Ｍ＜Ｋ）に量子化する場合を考える。
【００１５】
求めるべきパラメータは，次の式（１）を満たすＭ個のパラメータである。次の式（１）は，入力信号のヒストグラムの全区間［０，Ｋ］をＭ個の区間に分割し，各区間を重心で近似した場合の近似誤差の総和の最小化を目的として，同最小化を実現する各区間の幅Δm （第ｍ区間の区間幅）を求めることを表している。
【００１６】
【数１】
0005345977.tif 000002
【００１７】
ここで，Ｌm は，ヒストグラムにおける第ｍ区間の上端であり，次式で定義されるものとする。
【００１８】
【数２】
0005345977.tif 000003
【００１９】
ここで，Δm はヒストグラムの第ｍ区間の区間幅を表す。また，量子化後の各階調が，少なくとも１つ以上，量子化前の階調を含む必要があることから，Ｌm （０≦ｍ≦Ｍ−２）は，以下の範囲に制限される。
【００２０】
ｍ≦Ｌm ≦Ｋ−（Ｍ−ｍ）
ｅ（Ｌm −（Δm −１），Ｌm ）は次式で求まる値であり，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値＾ｃ（Ｌm −（Δm −１），Ｌm ）で近似した場合の近似誤差である。なお，「＾ｘ」の表記における「＾」は，「ｘ」の上に付く記号である（以下，同様）。
【００２１】
【数３】
0005345977.tif 000004
【００２２】
さらに，＾ｃ（Ｌm −（Δm −１），Ｌm ）は，次式で求まる実数値ｃ（Ｌm −（Δm −１），Ｌm ）を四捨五入して整数化した値である。
【００２３】
【数４】
0005345977.tif 000005
【００２４】
ｃ（Ｌm −（Δm −１），Ｌm ）は，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］における重心位置を表す。以下，ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を第ｍ量子化ビンと呼ぶ。なお，近似誤差として，クラスの代表値と入力信号の値との誤差の二乗和を用いるのではなく，絶対値和を用いてもよい。
【００２５】
Ｍ個のパラメータ（Δ1 ，…，ΔM ）の取り得る組み合わせは，Ｍとともに指数関数的に増加するため，この中から最適な組み合わせ（Δ* 1 ，…，Δ* M ）を総当りで探索するのは，計算量的に困難である。
【００２６】
そこで，本発明では，第ｍ量子化ビンの量子化誤差ｅ（Ｌm −（Δm −１），Ｌm ）が同ビンの上端Ｌm と同ビンの区間幅Δm に依存することに着目し，以下のように最適解を算出する。まず，ヒストグラムの区間［０，Ｌm ］をｍ＋１分割した際の近似誤差和の最小値をＳm （Ｌm ）として定義する。
【００２７】
Ｓm （Ｌm ）＝Σi=0 m ｅ（Ｌi −（Δi −１），Ｌi ）
つまり，最適なΔm ，…，Δ0 を用いた場合の，Σi=0 m ｅ（Ｌi −（Δi −１），Ｌi ）に対する最小値である。ここで，ｅ（Ｌm −（Δm −１），Ｌm ）が第ｍ量子化ビンの上端Ｌm と同ビンの区間幅Δm に依存することに着目すると，Ｓm （Ｌm ）は，Ｓm-1 （Ｌm-1 −Δm ）を用いて，次式のように表される。
【００２８】
【数５】
0005345977.tif 000006
【００２９】
なお，ｍ＝０，…，Ｍ−１である。また，Ｌm ＝ｍ，…，Ｋ−（Ｍ−ｍ）である。  
【００３０】
区間幅Δm の範囲は，次のようになる。Ｌm-1 ＝Ｌm −Δm であることから，Ｌm −Δm の範囲は，ｍ−１≦Ｌm −Δm ≦Ｋ−（Ｍ−ｍ＋１）となる。このため，Δm の範囲は，与えられたＬm を用いて，次式のように表される。
【００３１】
Ｌm −Ｋ＋（Ｍ−ｍ＋１）≦Δm ≦Ｌm −ｍ＋１                      （６）
さらに，Δm ≧１であることを考慮すると，次式を得る。
【００３２】
１≦Δm ≦Ｌm −ｍ＋１                                            （７）
次式のように，Δm の最大値をＡに制限することで，演算量の削減を図るアプローチもとれる。ただし，この場合，解の最適性は保証されない。
【００３３】
１≦Δm ≦Ａ                                                      （８）
ここで，算出したＳm （Ｌm ）を格納しておき，Ｓm+1 （Ｌm+1 ）の計算で用いるものとする。さらに，式（５）の最小値を与えるＬm-1 を＾Ｌm-1 （Ｌm ）とおく。この＾Ｌm-1 （Ｌm ）（ｍ≦Ｌm ≦Ｋ−（Ｍ−ｍ））も，全て格納しておくものとする。
【００３４】
式（１）の最小化問題は，次式のように表される。
【００３５】
【数６】
0005345977.tif 000007
【００３６】
上式を最小化するΔM-1 をΔ* M-1 とおく（次式の通り）。
【００３７】
【数７】
0005345977.tif 000008
【００３８】
このΔ* M-1 を用いて，第Ｍ−２ビンの上端の最適値はＬ* M-2 ＝Ｋ−Δ* 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 ，…，Δ* 0 ＝Ｌ* 0 −Ｌ* -1として求める。なお，Ｌ* -1＝−１である。
【００４０】
［ルックアップテーブルを用いた演算量低減法］
上記の処理では，Ｌm とΔm の組み合わせによっては，量子化誤差ｅ（Ｌm −（Δm −１），Ｌm ）が異なる量子化ビン（ｍの値が異なるという意味）において必要となる。その度に，量子化誤差ｅ（Ｌm −（Δm −１），Ｌm ）を算出するのは，計算コストの観点から得策ではない。計算結果を格納し，必要に応じて格納結果を呼び出すことで，演算量を低減できる。そこで，ｅ（Ｌm −（Δm −１），Ｌm ）として取り得る値をルックアップテーブル（Ｍ×Ｋ要素）に格納する。格納処理は，以下のようになる。
１．ｆｏｒ  ｍ＝０，…，Ｍ−１（処理１〜４のループ）
２．    Ｅ［ｍ，ｍ］←０
３．    ｆｏｒ  ｋ＝１，…，Ｋ−Ｍ（処理３〜４のループ）
４．        Ｅ［ｍ，ｍ＋ｋ］←ｅ（ｍ，ｍ＋ｋ）
［近似誤差計算の漸化関係を用いた演算量低減法］
上述のルックアップテーブル（Ｍ×Ｋ要素）Ｅ［ｍ，ｍ＋ｋ］へ格納する量子化誤差ｅ（Ｌm −Δm ，Ｌm-1 ）の計算過程にも重複した計算が存在するため，そうした重複部分を省略することで，演算量の低減を図る。
【００４１】
まず，以下の値を定義する。
【００４２】
【数８】
0005345977.tif 000009
【００４３】
これらを用いて，重心位置＾ｃ（Ｌm −（Δm −１），Ｌm ），量子化誤差ｅ（Ｌm −（Δm −１），Ｌm ）を再定義すると，次のようになる。
【００４４】
【数９】
0005345977.tif 000010
【００４５】
ここで，右辺の“Ｌ字型の記号”と“左右反転Ｌ字型の記号”は，その記号の間に挟まれる値を整数化する演算を表す。
【００４６】
ｅ（Ｌm −（Δm −１），Ｌm ）＝ｑ3 （Ｌm −（Δm −１），Ｌm ）＋２×＾ｃ（Ｌm −（Δm −１），Ｌm ）ｑ2 （Ｌm −（Δm −１），Ｌm ）＋＾ｃ（Ｌm −（Δm −１），Ｌm ）2 ｑ1 （Ｌm −（Δm −１），Ｌm ）                      …（１５）
これより，＾ｃ（Ｌm −（Δm −１），Ｌm ）およびｅ（Ｌm −（Δm −１），Ｌm ）が，以下の漸化関係を持つことが分かる。
【００４７】
【数１０】
0005345977.tif 000011
【００４８】
ｅ（Ｌm −（Δm −１），Ｌm ＋１）＝ｑ3 （Ｌm −（Δm −１），Ｌm ）＋ｋ2 ｈ［ｋ］｜k=Lm+1−２×＾ｃ（Ｌm −（Δm −１），Ｌm ＋１）｛ｑ2 （Ｌm −（Δm −１），Ｌm ）＋ｋｈ［ｋ］｜k=Lm+1｝＋＾ｃ（Ｌm −（Δm −１），Ｌm ＋１）2 ｛ｑ1 （Ｌm −（Δm −１），Ｌm ）ｈ［ｋ］｜k=Lm+1｝                      …（１７）
上記の関係に基づきｅ（Ｌm −（Δm −１），Ｌm ）を算出し，算出結果をルックアップテーブル（Ｍ×Ｋ要素）に格納する。格納処理は，以下のようになる：
１．ｆｏｒ  ｋ＝０，…，Ｋ−Ｍ（処理１〜４のループ）
２．  ｑ1 ［０，ｋ］←０
３．  ｑ2 ［０，ｋ］←０
４．  ｑ3 ［０，ｋ］←０
５．ｆｏｒ  ｍ＝０，…，Ｍ−１（処理５〜１３のループ）
６．  Ｅ［ｍ，ｍ］←０
７．  ｆｏｒ  ｋ＝０，…，Ｋ−Ｍ−１（処理７〜１３のループ）
８．    ｑ1 ［ｍ，ｍ＋ｋ＋１］←ｑ1 （ｍ，ｍ＋ｋ）＋ｈ［ｍ＋ｋ＋１］
９．    ｑ2 ［ｍ，ｍ＋ｋ＋１］←ｑ2 （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）ｈ［ｍ＋ｋ＋１］
１０．  ｑ3 ［ｍ，ｍ＋ｋ＋１］←ｑ3 （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）2 ｈ［ｍ＋ｋ＋１］
１１．  ＾ｃ［ｍ，ｍ＋ｋ＋１］←〔ｑ2 （ｍ，ｍ＋ｋ＋１）／ｑ1 （ｍ，ｍ＋ｋ＋１）〕の整数部分（四捨五入）
１２．  ｅ［ｍ，ｍ＋ｋ＋１］←ｑ3 （ｍ，ｍ＋ｋ＋１）−２×＾ｃ（ｍ，ｍ＋ｋ＋１）ｑ2 （ｍ，ｍ＋ｋ＋１）＋＾ｃ（ｍ，ｍ＋ｋ＋１）2 ｑ1 （ｍ，ｍ＋ｋ＋１）
１３．  Ｅ［ｍ，ｍ＋ｋ＋１］←ｅ［ｍ，ｍ＋ｋ＋１］
［視覚感度特性を考慮した重み付き歪み量の最小化］
視覚系は，低輝度の画素値の変化に比べて，高輝度の画素値の変化に鈍感である。そこで，このような視覚特性を考慮して量子化を行う場合には，以下のように行う。まず，画素値ｋ（ｋ＝０，…，Ｋ−１）に対する重み係数として，ｗ［ｋ］を設定する。この重み係数は，外部から与えられるものとする。例えば，高輝度（大きなｋ）の重みを低輝度（小さなｋ）の重みより小さな値に設定すれば，上記の輝度差に対する視覚特性を量子化処理に組み込むことが可能になる。この重み係数を用いて，画素値ｋに対する頻度ｈ［ｋ］を次のように補正する。
【００４９】
〜ｈ［ｋ］＝ｗ［ｋ］ｈ［ｋ］  
この補正後のヒストグラム〜ｈ［ｋ］に対して，前述の量子化処理を実施する。ここで，「〜ｘ」の表記における「〜」は，「ｘ」の上に付く記号である。
【００５０】
［適応量子化装置の構成例］
図１は，本発明の一実施形態に係る装置構成例を示す図である。
【００５１】
適応量子化装置１０は，入力信号のレベル数（クラス数ともいう）を記憶する入力信号レベル数記憶部１１，量子化後のレベル数を記憶する量子化後レベル数記憶部１２を備える。入力信号レベル数はＫ，量子化後レベル数はＭ（Ｍ＜Ｋ）とする。
【００５２】
ヒストグラム生成部１３は，入力信号における画素値ｋの頻度をｈ［ｋ］（ｋ＝０，…，Ｋ−１）として格納する。近似誤差算出部１４は，入力信号のヒストグラムｈ［ｋ］に対して，量子化後レベル数記憶部１２に格納されているレベル数Ｍ（クラス数）で，同ヒストグラムを近似するにあたって，ヒストグラムの全区間［０，Ｋ］をＭ個の区間に分割し，各区間を重心で近似した場合の近似誤差を，区間幅を変えた各区間の候補について算出する。近似誤差最小値記憶部１５は，各区間の候補について算出された近似誤差の最小値を記憶する。また，区間上端最適値記憶部１６は，近似誤差が最小となる区間の上端（クラス境界）の値を記憶する。
【００５３】
区間上端最適値追跡部１７は，区間上端最適値記憶部１６に記憶された区間の上端の値から，クラス境界の全候補に対して近似誤差を最小化するクラス境界を選択する。量子化処理部１８は，区間上端最適値追跡部１７が選択したクラス境界をもとに，入力信号を量子化レベル数Ｍで量子化し，量子化結果を出力する。
【００５４】
［適応量子化処理の流れ（基本処理）］
図２は，本発明の一実施形態に係る適応量子化処理のフローチャートである。
【００５５】
まず，適応量子化装置１０は，量子化後のクラス数Ｍを入力し，量子化後レベル数記憶部１２に記憶する（ステップＳ１０）。ヒストグラム生成部１３は，入力信号レベル数記憶部１１に記憶されているクラス数Ｋに従って，入力信号のヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）を算出する（ステップＳ１１）。
【００５６】
次に，近似誤差算出部１４は，近似誤差最小値記憶部１５の最小値を０に初期化する（ステップＳ１２）。その後，近似誤差算出部１４は，量子化後のレベルｍについて，ｍ＝０からｍ＝Ｍ−１まで，ｍの値を１ずつ増やしながら，ステップＳ１８までの処理を繰り返す（ステップＳ１３）。この処理のループでは，さらに量子化レベルｍを表す区間の上端Ｌm の各候補について，Ｌm ＝ｍからＬm ＝Ｋ−（Ｍ−ｍ）まで，Ｌm を１ずつ増やしながら，ステップＳ１７までの処理を繰り返す（ステップＳ１４）。
【００５７】
このループ内処理で，近似誤差算出部１４は，区間幅Δm をΔm ＝１からΔm ＝Ｌm −（ｍ−１）まで，Δm の値を１ずつ増やしながら，Δm の値によって定まるヒストグラムの区間を代表値で近似した場合の近似誤差を算出し，前の区間までの近似誤差最小値記憶部１５に記憶されている最小値に加算し，その値を各Δm に対して記憶する（ステップＳ１５）。
【００５８】
続いて，区間の上端Ｌm に対して，ステップＳ１５で算出した近似誤差の値を最小化する区間情報（区間幅Δm ，区間の上端Ｌm など）を区間上端最適値記憶部１６に記憶し，また，近似誤差の最小値を近似誤差最小値記憶部１５に記憶する（ステップＳ１６）。
【００５９】
以上の処理を上端Ｌm のすべての候補に対して行い，また，全レベルｍ（ｍ＝Ｍ−１まで）について終了したならば（ステップＳ１７，Ｓ１８），区間上端最適値追跡部１７は，全体の近似誤差を最小化する区間情報（クラス境界）を区間上端最適値記憶部１６から選出し，選出したクラス境界の情報を量子化処理部１８に出力する（ステップＳ１９）。
【００６０】
量子化処理部１８は，区間上端最適値追跡部１７が出力したクラス境界に従って，入力信号を量子化することにより，近似誤差（変換誤差）が最小となる量子化値を出力することができる。
【００６１】
以上の処理において，視覚感度特性を考慮した重み付き歪み量の最小化を図る場合，ステップＳ１５における近似誤差の算出では，視覚感度に基づき重み付けされた近似誤差を計算する。例えば，画素値ｋ（ｋ＝０，…，Ｋ−１）に対して，輝度差に対する視覚特性に基づく重み係数ｗ［ｋ］を設定し，画素値ｋに対する頻度ｈ［ｋ］に重み係数ｗ［ｋ］を乗算した値を用いて，近似誤差（視覚的近似誤差）を算出する。
【００６２】
また，区間幅Δm の範囲を制限した準最適化法を適用する場合には，ステップＳ１５において，各Δm を変化させる場合に，予め設定された最大値Ａの範囲内で，すなわち，１≦Δm ≦Ａの範囲内で各Δm に対する近似誤差の最小値を計算する。
【００６３】
次に，さらに具体的な処理の詳細について説明する。
【００６４】
［適応量子化処理の流れ（具体例）］
以下の実施例では，量子化値の選択基準として，選択基準１にあたる予測誤差（近似誤差）を用いた場合を示すが，選択基準２（視覚的近似誤差）を用いる場合も処理は同様である。
１．量子化後のクラス数Ｍを読み込む。
２．入力信号のヒストグラム（クラス数Ｋ）を生成する。
３．Ｓ0 （ｉ）←０（ｉ＝０，…，Ｋ−Ｍ）とする。
４．ｆｏｒ  ｍ＝０，…，Ｍ−１（処理４〜１０のループ）
５．  ｆｏｒ  Ｌm ＝ｍ，…，Ｋ−（Ｍ−ｍ）（処理５〜１０のループ）
６．    ｆｏｒ  Δm ＝１，…，Ｌm −（ｍ−１）（処理６〜８のループ）
７．        ヒストグラムの区間［Ｌm −（Δm −１），Ｌm ］を代表値で近似した場合の近似誤差を求める。代表値は，式（４）により求め，同近似誤差は式（３）により求める。同近似誤差をｅ（Ｌ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 ［０，ｋ］←０
５．  ｑ2 ［０，ｋ］←０
６．  ｑ3 ［０，ｋ］←０
７．ｆｏｒ  ｍ＝０，…，Ｍ−１（処理７〜１５のループ）
８．  Ｅ［ｍ，ｍ］←０
９．  ｆｏｒ  ｋ＝０，…，Ｋ−Ｍ−１（処理９〜１５のループ）
１０．  ｑ1 ［ｍ，ｍ＋ｋ＋１］←ｑ1 （ｍ，ｍ＋ｋ）＋ｈ［ｍ＋ｋ＋１］
１１．  ｑ2 ［ｍ，ｍ＋ｋ＋１］←ｑ2 （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）ｈ［ｍ＋ｋ＋１］
１２．  ｑ3 ［ｍ，ｍ＋ｋ＋１］←ｑ3 （ｍ，ｍ＋ｋ）＋（ｍ＋ｋ＋１）2 ｈ［ｍ＋ｋ＋１］
１３．  ＾ｃ［ｍ，ｍ＋ｋ＋１］←〔ｑ2 （ｍ，ｍ＋ｋ＋１）／ｑ1 （ｍ，ｍ＋ｋ＋１）〕の整数部分（小数点以下切捨て）
１４．  ｅ［ｍ，ｍ＋ｋ＋１］←ｑ3 （ｍ，ｍ＋ｋ＋１）−２×＾ｃ（ｍ，ｍ＋ｋ＋１）ｑ2 （ｍ，ｍ＋ｋ＋１）＋＾ｃ（ｍ，ｍ＋ｋ＋１）2 ｑ1 （ｍ，ｍ＋ｋ＋１）
１５．  Ｅ［ｍ，ｍ＋ｋ＋１］←ｅ［ｍ，ｍ＋ｋ＋１］
１６．［適応量子化処理の流れ（具体例）] の３．以降の処理を実行
以上説明した適応量子化の処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。
【符号の説明】
【００６７】
１０  適応量子化装置
１１  入力信号レベル数記憶部
１２  量子化後レベル数記憶部
１３  ヒストグラム生成部
１４  近似誤差算出部
１５  近似誤差最小値記憶部
１６  区間上端最適値記憶部
１７  区間上端最適値追跡部
１８  量子化処理部
【図１】
0005345977.tif 000012
【図２】
0005345977.tif 000013
【図３】
0005345977.tif 000014
【図４】
0005345977.tif 000015