(57)【特許請求の範囲】
【請求項１】
第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、
前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の上限に対して、前記選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の上限に最も近い前記有意要素の位置とを比較し、相対的に小さな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな上限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するステップと、
前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するステップと、
を含む量子化方法。
【請求項２】
第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、
前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の下限に対して、前記選択可能範囲の下限を上端とする各区間内における非有意要素の連続数の最大値を加算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の下限に最も近い前記有意要素の位置とを比較し、相対的に大きな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな下限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するステップと、
前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するステップと、
を含む量子化方法。
【請求項３】
第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置であって、
前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の上限に対して、前記選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の上限に最も近い前記有意要素の位置とを比較し、相対的に小さな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな上限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納する近似誤差最小値決定部と、
前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択する上端追跡部と、
を備える量子化装置。
【請求項４】
第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置のコンピュータに、
前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の上限に対して、前記選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の上限に最も近い前記有意要素の位置とを比較し、相対的に小さな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな上限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納する手順と、
前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択する手順と、
を実行させるための量子化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子化方法、量子化装置及び量子化プログラムに関する。
【背景技術】
【０００２】
近年、画像の高品質化に伴い、広ダイナミックレンジ映像への期待が高まっている。広ダイナミックレンジを有する画像信号に対する高いビット深度を用いた表現が検討されている。従来の８ビットから１０ビット以上に拡張した高ビット深度信号を取得可能なデバイスが登場している。
【０００３】
画像の符号量は、画像信号の高ビット深度化に応じて増大する。このため、効率的な符号化方法が求められている。図１８は、従来の高ビット深度信号の第１の符号化方法を示す図である。従来の高ビット深度信号の第１の符号化方法では、符号化装置は、高ビット深度信号の画像信号にビット深度変換処理を施すことで、画像信号を低ビット深度信号に変換して符号化及び復号処理を行う。さらに、符号化装置は、復号画像に対して逆ビット深度変換処理を行い、高ビット深度画像を生成する。最後に、符号化装置は、高ビット深度画像と入力信号との差分信号を符号化する。符号化装置の出力は、差分信号の符号化ストリームと、低ビット深度信号の符号化ストリームとである。このように、従来の高ビット深度信号の第１の符号化方法は、ビット深度のスケーラブル符号化に対応した方法である。
【０００４】
図１９は、従来の高ビット深度信号の第２の符号化方法を示す図である。図１９では、符号化装置は、差分信号の符号化ストリームを出力しない。符号化装置は、取得した画像信号にビット深度変換処理を施すことで、画像信号を復号信号に変換して符号化及び復号処理を行う。その後、符号化装置は、低ビット深度画像の復号信号に逆ビット深度変換処理を施し、高ビット深度画像の復号信号を出力する。
【０００５】
図１８に示す従来の高ビット深度信号の第１の符号化方法における符号化効率は、ビット深度変換処理に大きく依存する。従来の高ビット深度信号の第１の符号化方法においては、入力信号と逆ビット深度変換処理後の復号信号との差分値の二乗和（以下、「ビット深度変換誤差」という。）を抑えることで、符号化器の出力信号の符号量を抑えることができる。ビット深度変換処理において、いくつかのトーンマッピング（Tone Mapping）を用いた方法が非特許文献１に開示されている。符号化効率を向上させるためには、ビット深度変換誤差を最小化するようにビット深度変換が設計される必要がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
画素値の振幅方向の疎性に着目すると、画像によっては、与えられたビット深度によって表現可能な値を全て含まない場合がある。例えば、１０ビット信号の場合、０から１０２３までの１０２４種類の値を表現できる。振幅方向の疎性とは、画素値として画像内に含まれる値の種類が１０２４通り未満となる性質を指す。つまり、そうした画像では、画素値の頻度をヒストグラムとして表現した場合、頻度が零値になる画素値が存在する。なお、前述のビット深度変化処理は、ヒストグラムに対する一種の量子化処理とみなせる。
【０００８】
頻度が零値になる画素値は、ビット深度変換誤差に影響を与えない。しかしながら、従来の量子化方法は、信号の階調変換を行う際に発生する変換誤差を最小化する場合、量子化に要する演算量を低減することができないという問題がある。
【０００９】
上記事情に鑑み、本発明は、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能となる量子化方法、量子化装置及び量子化プログラムを提供することを目的としている。
【課題を解決するための手段】
【００１０】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の上限に対して、前記選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の上限に最も近い前記有意要素の位置とを比較し、相対的に小さな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな上限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するステップと、前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するステップと、を含む量子化方法である。
【００１１】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の下限に対して、前記選択可能範囲の下限を上端とする各区間内における非有意要素の連続数の最大値を加算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の下限に最も近い前記有意要素の位置とを比較し、相対的に大きな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな下限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納するステップと、前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するステップと、を含む量子化方法である。
【００１２】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置であって、前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の上限に対して、前記選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の上限に最も近い前記有意要素の位置とを比較し、相対的に小さな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな上限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納する近似誤差最小値決定部と、前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択する上端追跡部と、を備える量子化装置である。
【００１３】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置のコンピュータに、前記入力信号のヒストグラムの要素の集合であるクラスを定め、前記クラスの境界であるクラス境界の候補を有意要素に制限し、前記クラス境界となり得る前記有意要素に上限及び下限を定め、前記上限から前記下限までの範囲に含まれる前記有意要素を前記クラス境界の候補と定め、前記クラス境界の選択可能範囲の上限に対して、前記選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する前記有意要素の位置と、前記クラスの上限として取りうる前記有意要素のうち前記選択可能範囲の上限に最も近い前記有意要素の位置とを比較し、相対的に小さな値を示す前記有意要素を前記クラス境界の選択可能範囲の新たな上限と定め、前記クラス境界までの近似誤差の累積値を最小化する量子化値と前記近似誤差の累積値の最小値とをメモリに格納する手順と、前記クラス境界を選択する際、前記非有意要素を前記近似誤差の累積値の計算から除外し、格納した前記最小値を前記メモリから取得し、前記クラス境界の選択における前記近似誤差の計算に前記最小値を用いることで、前記クラス境界の全ての要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択する手順と、を実行させるための量子化プログラムである。
【発明の効果】
【００１４】
本発明により、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】実施形態における、参照テーブルρｕ［ｍ］を生成する処理の例を示す図である。
【図２】実施形態における、参照テーブルρｌ［ｍ］を生成する処理の例を示す図である。
【図３】実施形態における、ルックアップテーブルに格納する処理の例を示す図である。
【図４】実施形態における、適応量子化処理の例を示すフローチャートである。
【図５】実施形態における、要素インデックスと有意要素インデックスとの対応関係を格納した参照テーブルを生成する処理の例を示す図である。
【図６】実施形態における、非有意要素の個数を格納した参照テーブルを生成する処理の例を示す図である。
【図７】実施形態における、演算量低減型適応量子化処理の例を示すフローチャートである。
【図８】実施形態における、近似誤差参照テーブルを生成する処理（ステップＳ２０５）の例を示すフローチャートである。
【図９】実施形態における、ステップＳ１０４−２及びステップＳ２０４−２での上界用の参照テーブルを生成する処理の例を示すフローチャートである。
【図１０】実施形態における、ステップＳ１０４−２及びステップＳ２０４−２での下界用の参照テーブルを生成する処理の例を示すフローチャートである。
【図１１】実施形態における、ステップＳ４０１での参照テーブルを生成する処理の例を示すフローチャートである。
【図１２】実施形態における、ステップＳ５０１での参照テーブルを生成する処理の例を示すフローチャートである。
【図１３】実施形態における、量子化装置の構成の第１例を示す図である。
【図１４】実施形態における、量子化装置の構成の第２例を示す図である。
【図１５】実施形態における、適応量子化処理の基本処理の例を示す図である。
【図１６】実施形態における、適応量子化処理の演算量低減処理の例を示す図である。
【図１７】実施形態における、近似誤差参照テーブルを生成する処理の例を示す図である。
【図１８】従来の高ビット深度信号の第１の符号化方法を示す図である。
【図１９】従来の高ビット深度信号の第２の符号化方法を示す図である。
【発明を実施するための形態】
【００１６】
本発明の実施形態について、図面を参照して詳細に説明する。
以下、図又は式において変数等の上に付された記号（＾：ハット、〜：チルダ）は、変数の前に記載する。例えば、「＾」が上に付されたｃは、「＾ｃ」と表記する。以下、図又は式において変数又は記号の下付きの記号等と上付きの記号等とでは、下付きの記号等を先に記載する。例えば、下付き「１」と上付き「＊」とが付された変数Δは、「Δ１＊」と表記する。例えば、下付き「ｉ＝０」と上付き「ｍ」とが付された記号Σは、「Σｉ＝０ｍ」と表記する。
【００１７】
以下、Ｋは、入力信号のレベル数（以下、「入力レベル数」という。）を示す。Ｍ（Ｍ＜Ｋ）は、量子化された入力信号に基づく出力信号のレベル数（以下、「量子化レベル数」という。）を示す。画素値ｋのヒストグラム（頻度）をｈ［ｋ］（ｋ＝０，…，Ｋ−１）と表記する。
【００１８】
[量子化器の設計]
画像信号（輝度信号）が８ビットである場合、画素値ｋの取り得る範囲は、０から「入力レベル数−１」までの整数、すなわち、０から２５５の値となる。入力レベル数Ｋの画像信号を量子化レベル数の画像信号に量子化する場合を考える。求めるべきパラメータは、式（１）を満たすＭ個のパラメータである。
【００１９】
【数１】
0006538572.tif 000002
【００２０】
ここで、Ｌｍは、ヒストグラムにおける第ｍ区間の上端であり、式（２）によって表される。
【００２１】
【数２】
0006538572.tif 000003
【００２２】
ここで、Δｍは、ヒストグラムの第ｍ区間の区間幅を表す。また、量子化後の各階調が、少なくとも１個以上、量子化前の階調を含む必要があることから、Ｌｍ（０≦ｍ≦Ｍ−２）は、ｍ≦Ｌｍ≦Ｋ−（Ｍ−ｍ）の範囲に制限される。ＬＭ−１はＬＭ−１＝Ｋ−１に固定されているので、Ｌｍについては、ｍ＝Ｍ−１を省略し、ｍ≦Ｍ−２を考えれば良い。
【００２３】
ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）は次式で求まる値であり、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］を代表値ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）で近似した場合の近似誤差である。
【００２４】
【数３】
0006538572.tif 000004
【００２５】
さらに、＾ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）は、式（４）で求まる実数値ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）を四捨五入して整数化した値である。
【００２６】
【数４】
0006538572.tif 000005
【００２７】
ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）は、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］における重心位置を表す。以下、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］を第ｍ量子化クラスと呼ぶ。Ｍ個のパラメータ（Δ１，…，Δｍ）の取り得る組み合わせは、Ｍとともに指数関数的に増加するため、この中から最適な組み合わせ(Δ１，…，Δｍ)を総当りで探索するのは、計算量的に困難である。
【００２８】
そこで、第ｍ量子化クラスの量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が同クラスの上端Ｌｍと同クラスの区間幅Δｍに依存することに着目し、以下のように最適解を算出する。さらに、その際、ヒストグラムの非有意要素に基づく演算量削減を行う。
【００２９】
[基本解法]
まず、ヒストグラムの区間［０，Ｌｍ］をｍ＋１分割した際の近似誤差和Σｉ＝０ｍｅ（Ｌｉ−（Δｉ−１），Ｌｉ）の最小値をＳｍ（Ｌｍ）として定義する。つまり、最適なΔｍ，…，Δ０を用いた場合のΣｉ＝０ｍｅ（Ｌｉ−（Δｉ−１），Ｌｉ）に対する最小値である。ここで、ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が第ｍ量子化クラスの上端Lmと同クラスの区間幅Δｍに依存することに着目すると、Ｓｍ（Ｌｍ）はＳｍ−１（Ｌｍ−Δｍ）を用いて、式（５）のように表わされる。
【００３０】
【数５】
0006538572.tif 000006
【００３１】
なお、ｍ＝１，…，Ｍ−１である。また、Ｌｍ＝ｍ，…，Ｋ−（Ｍ−ｍ）である。
Δｍの範囲は、次のようになる。Ｌｍ−１＝Ｌｍ−Δｍであることから、Ｌｍ−Δｍの範囲は、ｍ−１≦Ｌｍ−Δｍ≦Ｋ−（Ｍ−ｍ＋１）となる。このため、Δｍの範囲は、与えられたＬｍを用いて式（６）のように表わされる。
【００３２】
【数６】
0006538572.tif 000007
【００３３】
さらに、Δｍ≧１であることを考慮すると、式（７）を得る。
【００３４】
【数７】
0006538572.tif 000008
【００３５】
ここで、算出したＳｍ（Ｌｍ）を格納しておき、Ｓｍ＋１（Ｌｍ＋１）の計算で用いるものとする。さらに、式（５）の右辺を最小化するΔｍの値をΔｍ（Ｌｍ）として、各Ｌｍ（＝ｍ，…，Ｋ−Ｍ＋ｍ）に対して＾Ｌｍ−１［Ｌｍ］＝Ｌｍ−Δｍ（Ｌｍ）を格納する。式（１）の最小化問題は、式（８）のように表される。
【００３６】
【数８】
0006538572.tif 000009
【００３７】
式（８）を最小化するΔＭ−１をΔＭ−１＊と表記する。ΔＭ−１＊は、式（９）によって表される。
【００３８】
【数９】
0006538572.tif 000010
【００３９】
ΔＭ−１＊を用いて、第Ｍ−２クラスの上端の最適値はＬＭ−２＝ＬＭ−１−ΔＭ−１＊＝Ｋ−１−ΔＭ−１＊と求まる。第Ｍ−３クラスの上端の最適値は、ＬＭ−２に対する最適解として、＾ＬＭ−３［ＬＭ−２］として格納されているので、該当する値を参照し、ＬＭ−３＝＾ＬＭ−３［ＬＭ−２］とする。この結果、第Ｍ−２クラスの区間幅は、ΔＭ−２＊＝ＬＭ−２＊−ＬＭ−３＊と求まる。以下、同様の参照処理をＬＭ−４＊＝＾ＬＭ−４［ＬＭ−３＊］,…,Ｌ０＊＝＾Ｌ０［Ｌ１＊］として繰り返し、得られた各クラスの上端値を用いて、ΔＭ−３＊＝ＬＭ−３＊−ＬＭ−４＊,…,Δ０＊＝Ｌ０＊−Ｌ−１＊として求める。なお、Ｌ−１＊＝−１である。
【００４０】
[ヒストグラムの非有意要素に基づく演算量削減]
ヒストグラムの非有意要素（頻度値が零値となる要素）に着目し、演算量を削減する方法を導入する。以下、ヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）について、要素を指定するインデックスｋを「要素インデックス」という。以下、ヒストグラムｈ［ｋ］について、有意要素(〜Ｋ個)を指定するインデックス〜ｋ(〜ｋ＝０，…，〜Ｋ−１)を「有意要素インデックス」という。
【００４１】
画素値Ｌｍ＋１における頻度値ｈ［Ｌｍ＋１］が零値である場合、即ち、ｈ［Ｌｍ＋１］＝０の場合、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ＋１］に対する近似誤差は、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］に対する近似誤差と等しい。ｈ［Ｌｍ＋１］＝０であることから、量子化の対象となる区間にｈ［Ｌｍ＋１］を加えたとしても、量子化による近似には影響を与えないためである。従って、ｈ［Ｌｍ＋１］＝０の場合、式（５）に基づくＳ（Ｌｍ＋１）の算出は省略することが可能となる。
【００４２】
ヒストグラムの非有意要素に着目した適応処理の準備として、以下の参照テーブルを用意する。Ｚ［ｋ］（ｋ＝０，…，Ｋ−１）は、ヒストグラムの区間［０，ｋ］に含まれる非有意要素の個数を格納する。Ｆ［〜Ｋ］は、第〜Ｋ番目の有意要素（非有意要素ではなく有意要素）に対応する要素インデックスを格納する。一方、Ｆ−１［ｋ］は、第k番目の要素に対応する有意要素インデックスを格納する。なお、第ｋ要素が非有意要素の場合、Ｆ−１［Ｋ］には“ｄｏｎ’ｔ  ｃａｒｅ”を表す値を代入する。
【００４３】
Ψｕ［ｍ］（ｍ＝０，…，Ｍ−１）は第ｍビンの上端となりうる有意要素インデックスの最大値を格納する。Ψｌ［ｍ］（ｍ＝０，…，Ｍ−１）は第ｍビンの上端となりうる有意要素インデックスの最小値を格納する。ここで、Ψｕ［ｍ］,Ψｌ［ｍ］（ｍ＝０，…，Ｍ−１）は各々、次のように設定される。以下は参照テーブルＺ［］を用いた場合のΨｕ［ｍ］,Ψｌ［ｍ］（ｍ＝０，…，Ｍ−１）の計算方法である。
【００４４】
【数１０】
0006538572.tif 000011
【００４５】
【数１１】
0006538572.tif 000012
【００４６】
以下は参照テーブルＦ−１［］を用いた場合のΨｕ［ｍ］,Ψｌ［ｍ］（ｍ＝０，…，Ｍ−１）の計算方法である。
【００４７】
【数１２】
0006538572.tif 000013
【００４８】
【数１３】
0006538572.tif 000014
【００４９】
ここで、〜Ｋ−１は有意要素インデックスの最大値を表している。Ｋ−１−Ｚ［Ｋ−１］は〜Ｋ−１と表される。ψｕ［ｍ−Ｍ＋Ｋ］は、ヒストグラムの区間［ｍ,ｍ−Ｍ＋Ｋ］における有意要素の要素インデックスの最大値であり、ψｌ［ｍ］は、ヒストグラムの区間［ｍ,ｍ−Ｍ＋Ｋ］における有意要素の要素インデックスの最小値である。つまり、ψｕ［ｍ−Ｍ＋Ｋ］は、第ｍビンの上端として取りうる有意要素の中で、選択可能範囲の上限に最も近い有意要素であり、ψｌ［ｍ］は、第ｍビンの上端として取りうる有意要素の中で、選択可能範囲の下限に最も近い有意要素である。
【００５０】
図１は、参照テーブルρｕ［ｍ］を生成する処理の例を示す図である。図２は、参照テーブルρｌ［ｍ］を生成する処理の例を示す図である。式（１０）から式（１３）までは、一定の条件を満たす場合、ψｕ［ｍ−Ｍ＋Ｋ］およびψｌ［ｍ］の指す有意要素が最適解の候補とはなりえず、最適解の探索候補から除外可能であることを示している。その条件とは、ψｕ［ｍ−Ｍ＋Ｋ］の場合は、ρｕ［ｍ］で定まるインデックス値ｍ−Ｍ＋Ｋ−ρｕ［ｍ］が、ψｕ［ｍ−Ｍ＋Ｋ］が表す要素インデックスよりも小さな値をとることであり、ψｌ［ｍ］の場合は、ρｌ［ｍ］で定まるインデックス値ｍ＋ρｌ［ｍ］が、ψｌ［ｍ］が表す要素インデックスよりも大きな値をとることである。ここで、ρｕ［ｍ］は、ヒストグラムの区間［ｍ−Ｍ＋Ｋ,Ｋ−１］における非有意要素のみからなる部分区間の区間幅の最大値を表し、ρｌ［ｍ］はヒストグラムの区間［０,ｍ］における非有意要素のみからなる部分区間の区間幅の最大値を表す。つまり、ρｕ［ｍ］およびρｌ［ｍ］は、指定された各区間内における非有意要素の連続数の最大値を表している。各々、図１及び図２に示すように定まる。
【００５１】
[最適解の求解]
非有意要素に対する不要な演算を省略し、演算量を低減するために、有意要素インデックスを用いた最適解の求解アルゴリズムを以下に示す。
【００５２】
〜Ｌｍ番目の有意要素を上端とするヒストグラムの区間［０，Ｆ［〜Ｌｍ］］をｍ＋１分割した場合を考える。同区間の分割により得られる部分区間［Ｆ［〜Ｌｉ−（〜Δｉ−１）］，Ｆ［〜Ｌｉ］］(ここで、ｉ＝０，…，ｍ)を第ｉビンとする。第ｉビンに対して、重心で近似した場合の量子化誤差ｅ（Ｆ［〜Ｌｉ−（〜Δｉ−１）］，Ｆ［〜Ｌｉ］）を算出する。ここで、〜Ｌｉは第iビンの上端にあたる有意要素インデックスであり、〜Δｉは第ｉビン内の有意要素数である。さらに、量子化誤差和Σｉ＝０ｍｅ［〜Ｌｉ−（〜Δｉ−１），〜Ｌｉ］の最小値を格納する参照テーブルを〜Ｓｍ［〜Ｌｍ］として定義する。つまり、最適な〜Δｍ，…，〜Δ０を用いた場合のσｉ＝０ｍｅ［〜Ｌｉ−（〜Δｉ−１），〜Ｌｉ］に対する最小値である。なお、〜Ｓｍ［〜Ｌｍ］はＳｍ［Ｆ［〜Ｌｍ］］と等しい。
【００５３】
ここで、〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）が第ｍ量子化クラスの上端の有意要素インデックス〜Ｌｍと同クラスの区間幅内の有意要素数〜Δｍに依存することに着目すると、〜Ｓｍ（〜Ｌｍ）は〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）を用いて、式（１４）のように表される。
【００５４】
【数１４】
0006538572.tif 000015
【００５５】
なお、ｍ＝０，…，Ｍ−１である。また、〜Ｌｍ＝Ψｌ［ｍ］，…，Ψｕ［ｍ］である。〜Δｍの範囲は、次のようになる。〜Ｌｍ−１＝〜Ｌｍ−〜Δｍであることから、〜Ｌｍ−〜Δｍの範囲は、Ψｌ［ｍ−１］≦〜Ｌｍ−〜Δｍ≦Ψｕ［ｍ−１］となる。このため、〜Δｍの範囲は、与えられた〜Ｌｍを用いて式（１５）のよう表される。
【００５６】
【数１５】
0006538572.tif 000016
【００５７】
さらに、〜Δｍ≧１であることを考慮すると、式（１６）を得る。
【００５８】
【数１６】
0006538572.tif 000017
【００５９】
ここで、算出した〜Ｓｍ（〜Ｌｍ）を格納しておき、〜Ｓｍ＋１（〜Ｌｍ＋１）の計算で用いるものとする。さらに、式（１４）の右辺を最小値化する〜Δｍを〜Δｍ（〜Ｌｍ）とし、第ｍビンの上端を〜Ｌｍとした場合の最適な第ｍ−１ビンの上端として、＾Ｌｍ−１［〜Ｌｍ］＝〜Ｌｍ−〜Δｍ（〜Ｌｍ）を各〜Ｌｍ（＝Ψｌ［ｍ］，…，Ψｕ［ｍ］）に対して格納しておくものとする。式（１）の最小化問題は、式（１７）のように表される。
【００６０】
【数１７】
0006538572.tif 000018
【００６１】
ここで、〜Ｋ＝Ｋ−Ｚ［Ｋ−１］である。式（１７）を最小化する〜ΔＭ−１を〜ΔＭ−１＊とおく。ΔＭ−１＊は、式（１８）によって表される。
【００６２】
【数１８】
0006538572.tif 000019
【００６３】
〜ＬＭ−１の取り得る値はＫ−Ｚ［Ｋ−１］−１のみであることから、〜ＬＭ−１＝Ｋ−Ｚ［Ｋ−１］−１となる。〜ＬＭ−１及び〜ΔＭ−１＊を用いて、第Ｍ−２クラスの上端の有意要素インデックスの最適値は〜ＬＭ−２＊＝〜ＬＭ−１−〜ΔＭ−１＊＝Ｋ−Ｚ［Ｋ−１］−１−〜ΔＭ−１＊と求まる。第Ｍ−３クラスの上端の有意要素インデックスの最適値は、〜ＬＭ−２＊に対する最適解として、＾ＬＭ−３［〜ＬＭ−２＊］として格納されているので、該当する値を参照し、〜ＬＭ−３＊＝＾ＬＭ−３［〜ＬＭ−２＊］とする。この結果、第Ｍ−２クラスの区間幅内の有意要素数は、〜ΔＭ−２＊＝〜ＬＭ−２−〜ＬＭ−３と求まる。以下、同様の参照処理を〜ＬＭ−４＊＝＾ＬＭ−４［〜ＬＭ−３＊］,…,〜Ｌ０＊＝＾Ｌ０［〜Ｌ１＊］として繰り返し、得られた各クラスの上端の有意要素インデックスを用いて、〜ΔＭ−３＊＝〜ＬＭ−３＊−〜ＬＭ−４＊,…,〜Δ０＊＝〜Ｌ０＊−〜Ｌ−１＊として求める。なお、〜Ｌ−１＊＝−１である。
【００６４】
各クラスの上端の有意要素インデックス〜ＬＭ−１,〜ＬＭ−２＊,…,〜Ｌ０＊から、Ｆ［〜ＬＭ−１］,Ｆ［〜ＬＭ−２＊］,…,Ｆ［〜Ｌ０＊］により、各クラスの上端が求まる。
【００６５】
[量子化誤差のルックアップテーブルへの格納]
ＬｍとΔｍの組み合わせによっては、異なる量子化クラス(ｍの値が異なるという意味)において、量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が必要となる。その度に、量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）を算出するのは、計算コストの観点から得策ではない。計算結果を格納し、必要に応じて格納結果を呼び出すことで、演算量を低減できる。そこで、ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）として取りうる値をルックアップテーブル(Ｍ×Ｋ要素)に格納する。
【００６６】
図３は、ルックアップテーブルに格納する処理（格納処理）の例を示す図である。上述のルックアップテーブル（（Ｋ−Ｚ［Ｋ−１］−１）×（Ｋ−Ｚ［Ｋ−１］）要素）Ｅ［〜ｉｓ，〜ｉｅ］へ格納する量子化誤差ｅ（Ｆ［〜ｉｓ］，Ｆ［〜ｉｅ］）の計算過程にも重複した計算が存在するため、そうした重複部分を省略することで、演算量の低減を図る。まず、以下の値を定義する。
【００６７】
【数１９】
0006538572.tif 000020
【００６８】
【数２０】
0006538572.tif 000021
【００６９】
【数２１】
0006538572.tif 000022
【００７０】
【数２２】
0006538572.tif 000023
【００７１】
【数２３】
0006538572.tif 000024
【００７２】
これより、ｃ（〜ｉｓ，〜ｉｅ）およびｅ（〜ｉｓ，〜ｉｅ）が以下の漸化関係を持つことが分かる。
【００７３】
【数２４】
0006538572.tif 000025
【００７４】
【数２５】
0006538572.tif 000026
【００７５】
漸化関係に基づきｅ（〜ｉｓ，〜ｉｅ）を算出し、算出結果をルックアップテーブル（（Ｋ−Ｚ［Ｋ−１］−１）×（Ｋ−Ｚ［Ｋ−１］）要素）に格納する。
【００７６】
[フローチャート：適応量子化処理]
適応量子化処理の実施形態について図面を参照して説明する。
図４は、適応量子化処理の例を示すフローチャートである。入力信号を読み込み、入力信号値のヒストグラムを生成する（ステップＳ１０１）。ヒストグラムの要素インデックスをｋ、ヒストグラムの有意要素インデックスを〜ｋとし、このｋと〜ｋの対応関係を格納した参照テーブルとして、Ｆ［〜ｋ］を生成する（ステップＳ１０２）。
【００７７】
図５は、要素インデックスと有意要素インデックスとの対応関係を格納した参照テーブルを生成する処理の例を示す図である。Ｆ［〜ｋ］の具体的な生成方法は、図５に示す通りである。ヒストグラムの区間［０，ｋ］に含まれる非有意要素の個数を格納した参照テーブルとして、Ｚ［ｋ］を生成する（ステップＳ１０３）。
【００７８】
図６は、非有意要素の個数を格納した参照テーブルを生成する処理の例を示す図である。Ｚ［ｋ］の具体的な生成方法は、図６に示す通りである。
【００７９】
図４に示すように、ヒストグラムを入力として読み込み、ｍ＝０，…，Ｍ−１に対して、ヒストグラムの区間［ｍ，ｍ−Ｍ＋Ｋ］における有意要素の要素インデックスの最大値および最小値を各々、参照テーブルΨｕ［ｍ−Ｍ＋Ｋ］および参照テーブルΨｌ［ｍ］に格納する（ステップＳ１０４−１）。非有意係数をスキップすることに伴うＬｍの最大値を格納した参照テーブルとして、Ψｕ［ｍ］（ｍ＝０，…，Ｍ−１）を生成する。具体的には、式（２６）及び式（２７）により設定する（ステップＳ１０４−２）。
【００８０】
【数２６】
0006538572.tif 000027
【００８１】
【数２７】
0006538572.tif 000028
【００８２】
ステップＳ１０７までの処理をｊ＝１，…，Ｋ−Ｍ−１−Ｚ［Ｋ−Ｍ−１］として繰り返す（ステップＳ１０５）。
ヒストグラムの区間［０,Ｆ［ｊ］］を代表値（式（４）により求まる重心）で近似した場合の近似誤差〜ｅ［０，ｊ］を求め、同近似誤差をＳ０（ｊ）に格納する（ステップＳ１０６）。
ステップＳ１１８までの処理をｍ＝１，…，Ｍ−１として繰り返す（ステップＳ１０８）。
【００８３】
ステップＳ１１７までの処理を〜Ｌｍ＝Ψｌ［ｍ］，…，Ψｕ［ｍ］として繰り返す（ステップＳ１０９）。
ステップＳ１１４までの以下の処理を〜Δｍ＝１，…，〜Ｌｍ−Ψｌ（ｍ−１）として繰り返す（ステップＳ１１０）。
ヒトグラムの区間［Ｆ［〜Ｌｍ−（〜Δｍ−１）］，Ｆ［〜Ｌｍ］］の代表値を式（４）により求める（ステップＳ１１１）。
【００８４】
ヒストグラムの区間［Ｆ［〜Ｌｍ−（〜Δｍ−１）］，Ｆ［〜Ｌｍ］］を代表値（ステップＳ１１１で求めた値）で近似した場合の近似誤差を式（３）より求める。同近似誤差を〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）とする（ステップＳ１１２）。
〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）の値を計算する（ステップＳ１１３）。
【００８５】
〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）（〜Δｍ＝１，…，〜Ｌｍ−（ｍ−１））の中での最小値を〜Ｓｍ（〜Ｌｍ）に格納する（ステップＳ１１５）。
〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）（〜Δｍ＝１，…，〜Ｌｍ−（ｍ−１））を最小化する〜Δｍを用いて、〜Ｌｍ−〜Δｍを＾Ｌｍ−１（〜Ｌｍ）に格納する。以下、＾Ｌｍ−１（〜Ｌｍ）を「最適パス追跡用参照テーブル」という（ステップＳ１１６）。
【００８６】
ＬＭ−１＊にＫ−１を代入する。〜ＬＭ−１＊にＫ−Ｚ［ｋ−１］−１を代入する（ステップＳ１１９）。
ステップＳ１２２までの処理をｍ＝Ｍ−１，…，１として繰り返す（ステップＳ１２０）。
＾Ｌｍ−１（〜Ｌｍ＊）を読み込み、〜Ｌｍ−１＊に代入する。Ｆ［〜Ｌｍ−１＊］を読み込み、Ｌｍ−１＊に代入する（ステップＳ１２１）。
【００８７】
[フローチャート：演算量低減型適応量子化処理]
近似誤差を参照テーブルに格納し、適宜、同参照テーブルから近似誤差を読み込む形に拡張した適応量子化処理の実施形態について図面を参照して説明する。
【００８８】
図７は、演算量低減型適応量子化処理の例を示すフローチャートである。
ステップＳ２０１〜ステップＳ２０４−２は、ステップＳ１０１〜ステップＳ１０４と同じである。
ヒストグラムの各区間を代表値で近似した際の近似誤差を格納した参照テーブルを生成する（ステップＳ２０５）。
ステップＳ２０６〜ステップＳ２１２は、ステップＳ１０５〜ステップＳ１１１と同じである。
【００８９】
ヒストグラムの区間［Ｆ［〜Ｌｍ−（〜Δｍ−１）］，Ｆ［〜Ｌｍ］］を代表値で近似した場合の近似誤差を参照テーブルＥ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）から読み込む（ステップＳ２１３）。
〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋Ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）の値を計算する（ステップＳ２１４）。
【００９０】
〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋Ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）（〜Δｍ＝１，…，〜Ｌｍ−（ｍ−１））の中での最小値を〜Ｓｍ（〜Ｌｍ）に格納する（ステップＳ２１６）。
〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋Ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）（〜Δｍ＝１，…，〜Ｌｍ−（ｍ−１））を最小化する〜Δｍを用いて、〜Ｌｍ−〜Δｍを＾Ｌｍ−１（〜Ｌｍ）に格納する（ステップＳ２１７）。
ステップＳ２２０〜ステップＳ２２３は、ステップＳ１１９〜ステップＳ１２２と同じである。
【００９１】
図８は、近似誤差参照テーブルを生成する処理（ステップＳ２０５）の例を示すフローチャートである。入力信号のヒストグラムを読み込む（ステップＳ３０１）。
参照テーブルＺ［ｋ］（ｋ＝０，…，ｋ−１）,Ｆ［〜ｋ］（〜ｋ＝０，…，Ｋ−Ｚ［Ｋ−１］−１）を読み込む（ステップＳ３０２）。
ステップＳ３０５までの処理を〜ｋ＝１，…，Ｋ−Ｚ［Ｋ−１］−１として繰り返す（ステップＳ３０３）。
ｑ１［０，〜ｋ］,ｑ２［０，〜ｋ］,ｑ３［０，〜ｋ］に０を格納する（ステップＳ３０４）。
ステップＳ３１６までの処理を〜ｉｓ＝０，…，Ｋ−Ｚ［Ｋ−１］−２として繰り返す（ステップＳ３０６）。
〜ｉｓ＋Ｋ−Ｚ［Ｋ−１］−Ｍ−１とＫ−Ｚ［Ｋ−１］−１を比較して、小さい方の値を変数Ｕに格納する（ステップＳ３０７）。
【００９２】
ステップＳ３１５までの処理を〜ｉｅ＝〜ｉｓ＋１，…，Ｕとして繰り返す（ステップＳ３０８）。
参照テーブルＦ［〜ｉｅ］を読み込み、ｉｅにＦ［〜ｉｅ］を代入する。参照テーブルＦ［〜ｉｓ］を読み込み、ｉｓにＦ［〜ｉｓ］を代入する（ステップＳ３０９）。
ｑ１［ｉｓ，ｉｅ−１］、ｈ［ｉｅ］を読み込み、ｑ１［ｉｓ，ｉｅ−１］＋ｈ［ｉｅ］を算出し、算出結果をｑ１［ｉｓ，ｉｅ］に格納する（ステップＳ３１０）。
【００９３】
ｑ２［ｉｓ，ｉｅ−１］、ｈ［ｉｅ］、ｉｅを読み込み、ｑ２［ｉｓ，ｉｅ−１］＋ｉｅｈ［ｉｅ］を算出し、算出結果をｑ２［ｉｓ，ｉｅ］に格納する（ステップＳ３１１）。
ｑ３［ｉｓ，ｉｅ−１］、ｈ［ｉｅ］、ｉｅを読み込み、ｑ３［ｉｓ，ｉｅ−１］＋ｉｅ２ｈ［ｉｅ］を算出し、算出結果をｑ３［ｉｓ，ｉｅ］に格納する（ステップＳ３１２）。
【００９４】
ｑ２［ｉｓ，ｉｅ−１］、ｑ３［ｉｓ，ｉｅ−１］を読み込み、ｑ２［ｉｓ，ｉｅ］ｑ１［ｉｓ，ｉｅ］を算出し、算出結果をｃ［ｉｓ，ｉｅ］に格納する（ステップＳ３１３）。
ｑ１［ｉｓ，ｉｅ−１］、ｑ２［ｉｓ，ｉｅ−１］、ｑ３［ｉｓ，ｉｅ−１］、ｃ［ｉｓ，ｉｅ］を読み込み、ｑ３［ｉｓ，ｉｅ］−２ｃ［ｉｓ，ｉｅ］ｑ２［ｉｓ，ｉｅ］＋ｃ［ｉｓ，ｉｅ］２ｑ１［ｉｓ，ｉｅ］を算出し、算出結果をＥ［〜ｉｓ，〜ｉｅ］に格納する（ステップＳ３１４）。
【００９５】
[参照テーブル生成処理の流れ]
図９は、ステップＳ１０４−２及びステップＳ２０４−２での上界用の参照テーブルを生成する処理の例を示すフローチャートである。
ヒストグラムを入力として読み込み、ヒストグラムの区間［ｍ−Ｍ＋Ｋ，Ｋ−１］における非有意要素のみからなる部分区間の区間幅の最大値を求め、参照テーブルρｕ［ｍ］、ρｌ［ｍ］（ｍ＝０，…，Ｍ−１に格納する（ステップＳ４０１）。具体的な処理の流れは、図１１に示される。
ｍ＝０，…，Ｍ−１に対して、ステップＳ４０３〜ステップＳ４０８の処理を繰り返す（ステップＳ４０２）。
ヒストグラムを入力として読み込み、ヒストグラムの区間［ｍ，ｍ−Ｍ＋Ｋ］における有意要素の要素インデックスの最大値を参照テーブルΨｕ［ｍ−Ｍ＋Ｋ］から読み込む。同参照テーブルは、図２のステップＳ１０４−１及び図７のステップＳ２０４−１で出力されたものである（ステップＳ４０３）。
ヒストグラムの区間［ｍ−Ｍ＋Ｋ,Ｋ−１］における非有意要素のみからなる部分区間の区間幅の最大値として、ステップＳ４０１で出力した参照テーブルψｕ［ｍ］の値を読み出す（ステップＳ４０４）。
選択可能範囲の上限にあたる要素インデックスｍ−Ｍ＋Ｋから、ステップＳ４０４で読み込んだ区間幅ρｕ［ｍ］を減算した値として、ｍ−Ｍ＋Ｋ−ρｕ［ｍ］の値を求める（ステップＳ４０５）。
ステップＳ４０３及びステップＳ４０５で求めた値を入力として読み込み、小さい方の値をｍｉｎ（ψｕ［ｍ−Ｍ＋Ｋ］，ｍ−Ｍ＋Ｋ−ρｕ［ｍ］）として求め、この値を選択可能範囲の新たな上限にあたる要素インデックスとする（ステップＳ４０６）。
ステップＳ４０６で求めた要素インデックスを入力として読み込み、同要素インデックスに対する有意要素インデックスを求める（ステップＳ４０７）。参照テーブルに格納する上記有意要素インデックスの算出に際しては、式（１０）又は式（１２）に従う。
有意要素インデックスを格納したテーブルΨｌ［ｍ］（ｍ＝０，…，Ｍ−１）を出力する（ステップＳ４０９）。
【００９６】
図１０は、ステップＳ１０４−２及びステップＳ２０４−２での下界用の参照テーブルを生成する処理の例を示すフローチャートである。ヒストグラムを読み込み、ヒストグラムの区間［０，ｍ］における非有意要素のみからなる部分区間の区間幅の最大値を求め、参照テーブルρｌ［ｍ］、ρｌ［ｍ］（ｍ＝０，…，Ｍ−１に格納する（ステップＳ５０１）。具体的な処理の流れは、図１２に示される。ｍ＝０，…，Ｍ−２に対して、ステップＳ５０３〜ステップＳ５０８の処理を繰り返す（ステップＳ５０２）。
【００９７】
ヒストグラムを読み込み、ヒストグラムの区間［ｍ，ｍ−Ｍ＋Ｋ］における有意要素の要素インデックスの最小値を参照テーブルΨｌ［ｍ］から読み込む（ステップＳ５０３）。同参照テーブルは、図４のステップＳ１０４−１及び図７のステップＳ２０４−１で出力されたものである。
【００９８】
ヒストグラムの区間［０，ｍ］における非有意要素のみからなる部分区間の区間幅の最大値として、ステップＳ５０１で出力した参照テーブルρｌ［ｍ］の値を読み出す（ステップＳ５０４）。選択可能範囲の下限にあたる要素インデックスｍから、ステップＳ５０４で読み込んだ区間幅ρｌ［ｍ］を加算した値として、ｍ＋ρｌ［ｍ］の値を求める（ステップＳ５０５）。
【００９９】
ステップＳ５０３及びステップＳ５０５で求めた値を読み込み、大きい方の値をｍａｘ（ψｌ［ｍ］，ｍ＋ρｌ［ｍ］）として求め、この値を選択可能範囲の新たな下限にあたる要素インデックスとする（ステップＳ５０６）。ステップＳ５０６で求めた要素インデックスを読み込み、同要素インデックスに対する有意要素インデックスを求める（ステップＳ５０７）。参照テーブルに格納する上記有意要素インデックスの算出に際しては、式（１０）又は式（１２）に従う。
【０１００】
有意要素インデックスの最大値〜Ｋ−１をΨｌ［Ｍ−１］の値として、参照テーブルΨｌ［Ｍ−１］に格納する（ステップＳ５０９）。有意要素インデックスを格納したテーブルΨｕ［ｍ］（ｍ＝０，…，Ｍ−１）を出力する（ステップＳ５１０）。
【０１０１】
図１１は、ステップＳ４０１での参照テーブルを生成する処理の例を示すフローチャートである。ヒストグラムの要素ｈ［Ｋ−１］を読み込み（ステップＳ６０１）、同要素値が零値でなければ、ステップＳ６０２に進み、それ以外の場合は、ステップＳ６０４に進む。変数ｃを０に設定する（ステップＳ６０２）。参照テーブルの要素ρｕ［Ｍ−１］を０に設定する（ステップＳ６０３）。変数ｃを１に設定する（ステップＳ６０４）。参照テーブルの要素ρｕ［Ｍ−１］を１に設定する（ステップＳ６０５）。
【０１０２】
ｍ＝Ｍ−２，…，０として、ステップＳ６０７からステップＳ６１３の処理を繰り返す（ステップＳ６０６）。ヒストグラムの要素ｈ［ｍ−Ｍ＋Ｋ］を読み込み（ステップＳ６０７）、同要素値が零値でなければ、ステップＳ６０８に進み、それ以外の場合は、ステップＳ６０９に進む。変数ｃを０に設定する（ステップＳ６０８）。変数ｃの値をインクリメントする（ステップＳ６０９）。
【０１０３】
変数ｃの値が参照テーブルの第ｍ＋１要素ρｕ［ｍ＋１］よりも大きいか否かを判定する（ステップＳ６１０）。変数ｃの値が参照テーブルの第ｍ＋１要素ρｕ［ｍ＋１］よりも大きい場合、ステップＳ６１１に進み、それ以外の場合は、ステップＳ６１２に進む。参照テーブルの第ｍ要素ρｕ［ｍ］に変数cの値を設定する（ステップＳ６１１）。参照テーブルの第ｍ要素ρｕ［ｍ］に参照テーブルの第ｍ＋１要素ρｕ［ｍ＋１］の値を設定する（ステップＳ６１２）。参照テーブルρｕ［ｍ］（ｍ＝０，…，Ｍ−１）を出力する（ステップＳ６１３）。
【０１０４】
図１２は、ステップＳ５０１での参照テーブルを生成する処理の例を示すフローチャートである。ヒストグラムの要素ｈ［０］を読み込み、同要素値が零値でなければ、ステップＳ７０２に進み、それ以外の場合は、ステップＳ７０４に進む（ステップＳ７０１）。変数ｃを０に設定する（ステップＳ７０２）。参照テーブルの要素ρｌ［０］を０に設定する（ステップＳ７０３）。変数ｃを１に設定する（ステップＳ７０４）。参照テーブルの要素ρｌ［０］を１に設定する（ステップＳ７０５）。ｍ＝１，…，Ｍ−１として、ステップＳ７０７〜ステップＳ７１３の処理を繰り返す（ステップＳ７０６）。
【０１０５】
ヒストグラムの要素ｈ［ｍ］を読み込み（ステップＳ７０７）、同要素値が零値でなければ、ステップＳ７０８に進み、それ以外の場合は、ステップＳ７０９に進む。変数ｃを０に設定する（ステップＳ７０８）。変数ｃの値をインクリメントする（ステップＳ７０９）。変数ｃの値が参照テーブルの第ｍ−１要素ρｌ［ｍ−１］よりも大きいか否かを判定する（ステップＳ７１０）。
【０１０６】
変数ｃの値が参照テーブルの第ｍ−１要素ρｌ［ｍ−１］よりも大きい場合、ステップＳ７１１に進み、それ以外の場合は、ステップＳ７１２に進む。参照テーブルの第ｍ要素ρｌ［ｍ］に変数ｃの値を設定する（ステップＳ７１１）。参照テーブルの第ｍ要素ρｌ［ｍ］に参照テーブルの第ｍ−１要素ρｌ［ｍ−１］の値を設定する（ステップＳ７１２）。参照テーブルρｌ［ｍ］（ｍ＝０，…，Ｍ−１）を出力する（ステップＳ７１３）。
【０１０７】
[適応量子化装置]
図１３は、量子化装置１ａ（適応量子化装置）の構成の例を示す図である。量子化装置１ａは、パーソナルコンピュータ、タブレット端末、スマートフォン端末、サーバ装置等の情報処理装置である。量子化装置１ａは、第１のレベル数（階調数）で範囲を表現する値を表す入力信号のヒストグラムを、第２のレベル数で範囲を表現する値を表す出力信号のヒストグラムで近似する量子化処理（適応量子化）を実行する。
【０１０８】
量子化装置１ａは、ヒストグラム生成部１０と、第１要素数記憶部１１と、クラス数記憶部１２と、インデックス参照テーブル生成部１３と、インデックス記憶部１４と、要素数参照テーブル生成部１５と、第２要素数記憶部１６と、上界値参照テーブル生成部１７と、上界値記憶部１８と、下界値参照テーブル生成部１９と、下界値記憶部２０と、近似誤差最小値決定部２１と、近似誤差最小値記憶部２２と、上端記憶部２３と、上端追跡部２４とを備える。
【０１０９】
ヒストグラム生成部１０と、インデックス参照テーブル生成部１３と、要素数参照テーブル生成部１５と、上界値参照テーブル生成部１７と、下界値参照テーブル生成部１９と、近似誤差最小値決定部２１と、上端追跡部２４との一部または全部は、例えば、ＣＰＵ（Central Processing Unit）等のプロセッサが、記憶部に記憶されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部のうち一部または全部は、ＬＳＩ（Large Scale Integration）やＡＳＩＣ（Application Specific Integrated Circuit）等のハードウェア機能部であってもよい。
【０１１０】
第１要素数記憶部１１と、クラス数記憶部１２と、インデックス記憶部１４と、第２要素数記憶部１６と、上界値記憶部１８と、下界値記憶部２０と、近似誤差最小値記憶部２２と、上端記憶部２３との一部または全部は、例えば、磁気ハードディスク装置や半導体記憶装置等の不揮発性の記憶媒体（非一時的な記録媒体）を有する記憶装置を用いて構成される。各記憶部は、例えば、ＲＡＭ（Random Access Memory）やレジスタなどの揮発性の記憶媒体を有していてもよい。
【０１１１】
ヒストグラム生成部１０は、入力信号を読み込む。ヒストグラム生成部１０は、入力信号のヒストグラムを生成する。ヒストグラム生成部１０は、入力信号のヒストグラムと入力信号のレベル数Ｋとを、第１要素数記憶部１１に記憶させる。
第１要素数記憶部１１（ヒストグラム・入力信号要素数記憶部）は、入力信号のヒストグラムと入力信号のレベル数Ｋとを記憶（格納）する。
クラス数記憶部１２は、量子化クラス数Ｍを記憶する。
【０１１２】
インデックス参照テーブル生成部１３は、ヒストグラムの要素インデックスをｋ、ヒストグラムの有意要素インデックスを〜ｋとし、ヒストグラムの要素インデックスｋとヒストグラムの有意要素インデックス〜ｋとの対応関係を格納した参照テーブルとして、Ｆ［〜ｋ］を生成する。インデックス参照テーブル生成部１３は、ｋと〜ｋの対応関係を格納した参照テーブルを、インデックス記憶部１４に格納する。参照テーブルＦ［〜ｋ］の具体的な生成方法は、図４のステップＳ１０２に示す通りである。
インデックス記憶部１４は、ヒストグラムの要素インデックスｋとヒストグラムの有意要素インデックス〜ｋとの対応関係を格納した参照テーブルを記憶する。
【０１１３】
要素数参照テーブル生成部１５は、ヒストグラムの区間［０，Ｋ］に含まれる非有意要素の個数を格納した参照テーブルとして、Ｚ［ｋ］を生成する。参照テーブルを第２要素数記憶部１６に格納する。参照テーブルＺ［ｋ］の具体的な生成方法は、図４のステップＳ１０３に示す通りである。
第２要素数記憶部１６（非有意要素数記憶部）は、参照テーブルＺ［ｋ］を記憶する。
【０１１４】
上界値参照テーブル生成部１７は、第ｍクラスの有意要素インデックスの最大値を格納した参照テーブルとして、Ψｕ［ｍ］（ｍ＝０，…，Ｍ−１）を生成する。上界値参照テーブル生成部１７は、参照テーブルΨｕ［ｍ］を上界値記憶部１８に格納する。参照テーブルΨｕ［ｍ］の具体的な生成方法は、図４のステップＳ１０４に示す通りである。
上界値記憶部１８は、参照テーブルΨｕ［ｍ］を記憶する。
【０１１５】
下界値参照テーブル生成部１９は、第ｍクラスの有意要素インデックスの最小値を格納した参照テーブルとして、Ψｌ［ｍ］（ｍ＝０，…，Ｍ−１）を生成する。下界値参照テーブル生成部１９は、参照テーブルΨｌ［ｍ］を下界値記憶部２０に格納する。参照テーブルΨｌ［ｍ］の具体的な生成方法は、図４のステップＳ１０４に示す通りである。
下界値記憶部２０は、参照テーブルΨｌ［ｍ］を記憶する。
【０１１６】
近似誤差最小値決定部２１は、入力信号のヒストグラムと、入力信号のレベル数と、量子化クラス数と、要素インデックスの参照テーブルと、非有意要素数の参照テーブルと、量子化クラスの上界値の参照テーブルと、量子化クラスの下界値の参照テーブルとを取得する。
【０１１７】
近似誤差最小値決定部２１は、ヒストグラムを量子化クラス数で指定されたクラス数に分割した場合の近似誤差の最小値を算出する。近似誤差最小値決定部２１は、ヒストグラムを量子化クラス数で指定されたクラス数に分割した場合の近似誤差の最小値を、近似誤差最小値記憶部２２に格納する。近似誤差最小値決定部２１は、各量子化クラスにおいて近似誤差の累積値を最小化するクラスの上端を表す有意要素インデックスを、最適パス追跡用参照テーブルとして、上端記憶部２３に格納する。具体的な処理は、図４に示すステップＳ１０５からステップＳ１１８までに示す通りである。近似誤差最小値記憶部２２は、ヒストグラムを量子化クラス数で指定されたクラス数に分割した場合の近似誤差の最小値を記憶する。上端記憶部２３は、最適パス追跡用参照テーブルを記憶する。
【０１１８】
上端追跡部２４は、入力信号のレベル数と、量子化クラス数と、要素インデックス参照テーブルと、有意要素数参照テーブルと、最適パス追跡用参照テーブルとを取得する。上端追跡部２４は、近似誤差の最小値を実現する際のクラスの上端を表す要素インデックスを算出する。具体的な処理は、図４に示すステップＳ１１９からステップ１２２までに示す通りである。
【０１１９】
[演算量低減型適応量子化装置]
近似誤差を参照テーブルに格納し、近似誤差を格納した参照テーブルから近似誤差を適宜に読み込む形に拡張した演算量低減型適応量子化装置の構成を説明する。
【０１２０】
図１４は、量子化装置１ｂ（演算量低減型適応量子化装置）の構成の例を示す図である。量子化装置１ｂは、パーソナルコンピュータ、タブレット端末、スマートフォン端末、サーバ装置等の情報処理装置である。量子化装置１ｂは、第１のレベル数（階調数）で範囲を表現する値を表す入力信号のヒストグラムを、第２のレベル数で範囲を表現する値を表す出力信号のヒストグラムで近似する量子化処理（適応量子化）を実行する。
【０１２１】
量子化装置１ｂは、ヒストグラム生成部１０と、第１要素数記憶部１１と、クラス数記憶部１２と、インデックス参照テーブル生成部１３と、インデックス記憶部１４と、要素数参照テーブル生成部１５と、第２要素数記憶部１６と、上界値参照テーブル生成部１７と、上界値記憶部１８と、下界値参照テーブル生成部１９と、下界値記憶部２０と、近似誤差最小値決定部２１と、近似誤差最小値記憶部２２と、上端記憶部２３と、上端追跡部２４と、近似誤差決定部２５と、近似誤差記憶部２６とを備える。
【０１２２】
ヒストグラム生成部１０と、インデックス参照テーブル生成部１３と、要素数参照テーブル生成部１５と、上界値参照テーブル生成部１７と、下界値参照テーブル生成部１９と、近似誤差最小値決定部２１と、上端追跡部２４と、近似誤差決定部２５との一部または全部は、例えば、ＣＰＵ等のプロセッサが、記憶部に記憶されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部のうち一部または全部は、ＬＳＩやＡＳＩＣ等のハードウェア機能部であってもよい。
【０１２３】
第１要素数記憶部１１と、クラス数記憶部１２と、インデックス記憶部１４と、第２要素数記憶部１６と、上界値記憶部１８と、下界値記憶部２０と、近似誤差最小値記憶部２２と、上端記憶部２３と、近似誤差記憶部２６との一部または全部は、例えば、磁気ハードディスク装置や半導体記憶装置等の不揮発性の記憶媒体（非一時的な記録媒体）を有する記憶装置を用いて構成される。各記憶部は、例えば、ＲＡＭやレジスタなどの揮発性の記憶媒体を有していてもよい。
【０１２４】
近似誤差最小値決定部２１は、入力信号のヒストグラムと、入力信号のレベル数と、量子化クラス数と、要素インデックスの参照テーブルと、非有意要素数の参照テーブルと、量子化クラスの上界値の参照テーブルと、量子化クラスの下界値の参照テーブル近似誤差の参照テーブルとを取得する。
【０１２５】
近似誤差最小値決定部２１は、入力信号のヒストグラムと、入力信号のレベル数と、量子化クラス数と、要素インデックスの参照テーブルと、非有意要素数の参照テーブルと、量子化クラスの上界値の参照テーブルと、量子化クラスの下界値の参照テーブル近似誤差の参照テーブルとに基づいて、量子化クラス数で指定されたクラス数にヒストグラムを分割した場合の近似誤差の最小値を算出する。近似誤差最小値決定部２１は、近似誤差の最小値を近似誤差最小値記憶部２２に格納する。近似誤差最小値決定部２１は、各量子化クラスにおいて近似誤差の累積値を最小化するクラスの上端を表す有意要素インデックスを、最適パス追跡用参照テーブルとして、上端記憶部２３に格納する。具体的な処理は、図７のステップＳ２０６からステップＳ２１９までに示す通りである。
近似誤差最小値記憶部２２は、近似誤差の最小値を記憶する。
上端記憶部２３は、最適パス追跡用参照テーブルを記憶する。
【０１２６】
上端追跡部２４は、入力信号のレベル数と、量子化クラス数と、要素インデックス参照テーブルと、有意要素数参照テーブルと、最適パス追跡用参照テーブルとを取得する。上端追跡部２４は、入力信号のレベル数と、量子化クラス数と、要素インデックス参照テーブルと、有意要素数参照テーブルと、最適パス追跡用参照テーブルとに基づいて、近似誤差の最小値を実現する際のクラスの上端を表す要素インデックスを算出する。具体的な処理は、図７のステップＳ２２０からステップＳ２２３までに示す通りである。
【０１２７】
近似誤差決定部２５は、入力信号のヒストグラムと、入力信号のレベル数と、量子化クラス数と、要素インデックスの参照テーブルと、非有意要素数の参照テーブルとを取得する。近似誤差決定部２５は、入力信号のヒストグラムと、入力信号のレベル数と、量子化クラス数と、要素インデックスの参照テーブルと、非有意要素数の参照テーブルとに基づいて、近似誤差を算出する。近似誤差決定部２５は、算出した近似誤差を、近似誤差の参照テーブルとして近似誤差記憶部２６に格納する。具体的な処理は、図８に示す通りである。
近似誤差記憶部２６は、近似誤差の参照テーブルを記憶する。
【０１２８】
図１５は、適応量子化処理の基本処理の例を示す図である。非有意係数に対する不要な処理を削除した適応量子化処理の基本処理の流れを説明する。なお、処理の繰り返し（ｆｏｒ文）の条件は、図１５に示す通りである。
【０１２９】
ヒストグラム生成部１０は、入力信号のヒストグラム(クラス数Ｋ) を生成する。クラス数記憶部１２は、量子化後のクラス数Ｍを読み込む。参照テーブルＺ［ｋ］（ｋ＝０，…，Ｋ−１）,Ψｌ［ｍ］,Ψｕ［ｍ］（ｍ＝０，…，Ｍ−１）,Ｆ［〜ｋ］（〜ｋ＝０，…，Ｋ−Ｚ［Ｋ−１］−１）を生成する。
【０１３０】
ヒストグラムの区間［０,Ｆ［ｊ］］を代表値（式（４）により求まる重心）で近似した場合の近似誤差を求め、近似した場合の近似誤差をＳ０（ｊ）に格納する。以下、近似した場合の近似誤差をＳ０（ｊ）に格納する処理を「第１格納処理」という。
【０１３１】
ヒストグラムの区間［Ｆ［〜Ｌｍ−（〜Δｍ−１）］，Ｆ［〜Ｌｍ］］を代表値で近似した場合の近似誤差を求める。代表値は式（４）により求め、同近似誤差は式（３）より求める。同近似誤差を〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）とする。〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）の値を計算する。〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）（〜Δｍ＝１，…，〜Ｌｍ−（ｍ−１））の中での最小値を〜Ｓｍ（〜Ｌｍ）に格納する。〜Ｓｍ−１（〜Ｌｍ−〜Δｍ）＋〜ｅ（〜Ｌｍ−（〜Δｍ−１），〜Ｌｍ）（〜Δｍ＝１，…，〜Ｌｍ−（ｍ−１））を最小化する〜Δｍを用いて、〜Ｌｍ−〜Δｍを＾Ｌｍ−１（〜Ｌｍ）に格納する。
【０１３２】
Ｋ−１をＬＭ−１＊に格納する。Ｋ−Ｚ［Ｋ−１］−１を〜ＬＭ−１＊に格納する。＾Ｌｍ−１（〜Ｌｍ＊）を読み込む。＾Ｌｍ−１（〜Ｌｍ＊）を〜Ｌｍ−１＊に格納する。Ｆ［〜Ｌｍ−１＊］をＬｍ−１＊に格納する。
【０１３３】
図１６は、適応量子化処理の演算量低減処理の例を示す図である。前述のルックアップテーブルを参照する方式の場合における、演算量低減処理を実行する適応量子化処理の例を説明する。なお、処理の繰り返し（ｆｏｒ文）の条件は、図１６に示す通りである。
【０１３４】
ヒストグラム生成部１０は、入力信号のヒストグラム(クラス数Ｋ) を生成する。クラス数記憶部１２は、量子化後のクラス数Ｍを読み込む。参照テーブルＺ［ｋ］（ｋ＝０，…，Ｋ−１）,Ψｌ［ｍ］,Ψｕ［ｍ］（ｍ＝０，…，Ｍ−１）,Ｆ［〜ｋ］（〜ｋ＝０，…，Ｋ−Ｚ［Ｋ−１］−１）を生成する。
【０１３５】
図１７に示す処理（近似誤差参照テーブル生成処理の流れ）に基づき、近似誤差を格納した参照テーブルＥ［〜ｉｓ，〜ｉｅ］を生成する。Ｅ［０，ｊ］をＳ０（ｊ）に格納する。図１５に示す処理（適応量子化処理の基本処理の流れ）における、第１格納処理よりも後の処理を実行する。
【０１３６】
図１７は、近似誤差参照テーブルを生成する処理の例を示す図である。なお、処理の繰り返し（ｆｏｒ文）の条件は、図１７に示す通りである。
【０１３７】
ｑ１［０，〜ｋ］に０を格納する。ｑ２［０，〜ｋ］に０を格納する。ｑ３［０，〜ｋ］に０を格納する。ｉｅにＦ［〜ｉｅ］を代入する。ｉｓにＦ［〜ｉｓ］を代入する。
ｑ１［ｉｓ，ｉｅ］にｑ１［ｉｓ，ｉｅ−１］＋ｈ［ｉｅ］を格納する。ｑ２［ｉｓ，ｉｅ］にｑ２［ｉｓ，ｉｅ−１］＋ｉｅｈ［ｉｅ］を格納する。ｑ３［ｉｓ，ｉｅ］にｑ３［ｉｓ，ｉｅ−１］＋ｉｅ２ｈ［ｉｅ］を格納する。ｃ［ｉｓ，ｉｅ］にｑ２［ｉｓ，ｉｅ］／ｑ１［ｉｓ，ｉｅ］を格納する。Ｅ［〜ｉｓ，〜ｉｅ］にｑ３［ｉｓ，ｉｅ］−２ｃ［ｉｓ，ｉｅ］ｑ２［ｉｓ，ｉｅ]＋ｃ［ｉｓ，ｉｅ］２ｑ１［ｉｓ，ｉｅ］を格納する。
【０１３８】
以上のように、量子化方法は、第１のレベル数（入力信号レベル数）で表現される範囲を取り得る値を表す入力信号のヒストグラムを、第１のレベル数よりも少ない第２のレベル数（量子化レベル数）で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、格納するステップと、選択するステップとを含む。近似誤差最小値決定部２１は、入力信号のヒストグラムの要素の集合であるクラスを定め、クラスの境界であるクラス境界の候補を有意要素に制限し、クラス境界となり得る有意要素に上限及び下限を定め、上限から下限までの範囲に含まれる有意要素をクラス境界の候補と定め、クラス境界の選択可能範囲の上限に対して、選択可能範囲の上限を下端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する有意要素の位置と、クラスの上限として取りうる有意要素のうち選択可能範囲の上限に最も近い有意要素の位置とを比較し、相対的に大きな値を示す有意要素をクラス境界の選択可能範囲の新たな上限と定め、クラス境界までの近似誤差の累積値を最小化する量子化値と近似誤差の累積値の最小値とをメモリに格納する。上端追跡部２４は、クラス境界を選択する際、非有意要素を近似誤差の累積値の計算から除外し、格納した最小値をメモリから取得し、クラス境界の選択における近似誤差の計算に最小値を用いることで、クラス境界の全ての要素に対して近似誤差の総和を最小化するクラス境界を選択する。
【０１３９】
これによって、量子化方法は、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能となる。すなわち、量子化方法は、画素値の疎性を考慮することで、ビット深度変換誤差の最適性を保持しつつ、演算量を低減することが可能となる。
【０１４０】
量子化方法は、第１のレベル数（入力信号レベル数）で表現される範囲を取り得る値を表す入力信号のヒストグラムを、第１のレベル数よりも少ない第２のレベル数（量子化レベル数）で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、格納するステップと、選択するステップとを含む。近似誤差最小値決定部２１は、入力信号のヒストグラムの要素の集合であるクラスを定め、クラスの境界であるクラス境界の候補を有意要素に制限し、クラス境界となり得る有意要素に上限及び下限を定め、上限から下限までの範囲に含まれる有意要素をクラス境界の候補と定め、クラス境界の選択可能範囲の下限に対して、選択可能範囲の下限を上端とする各区間内における非有意要素の連続数の最大値を減算した値に対応する有意要素の位置と、クラスの上限として取りうる有意要素のうち選択可能範囲の上限に最も近い有意要素の位置とを比較し、相対的に小さな値を示す有意要素をクラス境界の選択可能範囲の新たな下限と定め、クラス境界までの近似誤差の累積値を最小化する量子化値と近似誤差の累積値の最小値とをメモリに格納する。上端追跡部２４は、クラス境界を選択する際、非有意要素を近似誤差の累積値の計算から除外し、格納した最小値をメモリから取得し、クラス境界の選択における近似誤差の計算に最小値を用いることで、クラス境界の全ての要素に対して近似誤差の総和を最小化するクラス境界を選択する。
【０１４１】
これによって、量子化方法は、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能となる。すなわち、量子化方法は、画素値の疎性を考慮することで、ビット深度変換誤差の最適性を保持しつつ、演算量を低減することが可能となる。
【０１４２】
上述した実施形態における量子化装置の少なくとも一部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【０１４３】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１４４】
１ａ…量子化装置、１ｂ…量子化装置、１０…ヒストグラム生成部、１１…第１要素数記憶部、１２…クラス数記憶部、１３…インデックス参照テーブル生成部、１４…インデックス記憶部、１５…要素数参照テーブル生成部、１６…第２要素数記憶部、１７…上界値参照テーブル生成部、１８…上界値記憶部、１９…下界値参照テーブル生成部、２０…下界値記憶部、２１…近似誤差最小値決定部、２２…近似誤差最小値記憶部、２３…上端記憶部、２４…上端追跡部、２５…近似誤差決定部、２６…近似誤差記憶部
【図１】
0006538572.tif 000029
【図２】
0006538572.tif 000030
【図３】
0006538572.tif 000031
【図４】
0006538572.tif 000032
【図５】
0006538572.tif 000033
【図６】
0006538572.tif 000034
【図７】
0006538572.tif 000035
【図８】
0006538572.tif 000036
【図９】
0006538572.tif 000037
【図１０】
0006538572.tif 000038
【図１１】
0006538572.tif 000039
【図１２】
0006538572.tif 000040
【図１３】
0006538572.tif 000041
【図１４】
0006538572.tif 000042
【図１５】
0006538572.tif 000043
【図１６】
0006538572.tif 000044
【図１７】
0006538572.tif 000045
【図１８】
0006538572.tif 000046
【図１９】
0006538572.tif 000047