(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.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従来のビット深度変化処理は、画像信号のヒストグラムに対する一種の量子化処理とみなせる。符号化効率向上のためには、ビット深度変換誤差を最小化するようにビット深度変換を設計する必要がある。しかしながら、ビット深度変換誤差を最小化するようにビット深度変換を設計すると演算量が増加してしまうという問題がある。すなわち、従来の量子化方法は、信号の階調変換を行う際に発生する変換誤差を最小化する場合、量子化に要する演算量を低減することができないという問題がある。
【０００８】
上記事情に鑑み、本発明は、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能である量子化方法、量子化装置及び量子化プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００９】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置における量子化方法であって、前記入力信号のヒストグラム内の要素の集合である複合要素を構成するステップと、複数の前記複合要素に含まれる一つ以上の値を代表値で近似した場合の近似誤差を、前記複合要素の集合であるクラスの最下端の前記複合要素内の要素を下端とし、前記クラスの最上端の前記複合要素内の要素を上端として構成される前記入力信号のヒストグラムの区間に対する近似誤差の下限値として定義して、前記クラスの境界であるクラス境界の候補を前記複合要素に制限し、前記クラス境界までの前記近似誤差の累積値を最小化する量子化値と、前記近似誤差の累積値の最小値とをメモリに格納するステップと、前記クラス境界を選択する際、格納した前記最小値を前記メモリから呼び出し、前記メモリから呼び出した前記最小値を前記クラス境界の選択における前記近似誤差の計算に用いることで、前記クラス境界の全ての前記複合要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択処理を行うステップと、前記クラス境界として選択された前記複合要素が複数の要素を含む場合、選択された前記複合要素を上部分集合と下部分集合とに分割し、分割により得られた前記上部分集合と前記下部分集合を新たに部分集合複合要素に加え、前記クラス境界選択処理を行い、前記クラス境界として選択された前記複合要素の要素数が一つになるまで繰り返すステップと、を含む量子化方法である。
【００１０】
本発明の一態様は、上記の量子化方法であって、複数の前記複合要素を代表値で近似した場合の前記近似誤差として、前記最下端の前記複合要素の最大レベル値の要素を下端とし、前記最上端の前記複合要素の最小レベル値の要素を上端として構成される前記入力信号のヒストグラムの区間に対する前記近似誤差として定義するステップを更に含む量子化方法である。
【００１１】
本発明の一態様は、上記の量子化方法であって、前記クラス境界として選択された前記複合要素を前記上部分集合と前記下部分集合に分割した場合、前記上部分集合と前記上部分集合のクラスの一段上のクラスの前記クラス境界の前記複合要素を分割して得た前記上部分集合により定まる前記複合要素の集合に対する前記近似誤差を算出するステップと、前記上部分集合に分割前の前記複合要素とその他の前記複合要素の集合に対する前記近似誤差を再利用して、後段の前記クラス境界を選択する処理を行った結果に基づいて、前記上部分集合とその他の前記複合要素により定まる前記複合要素の集合に対する前記近似誤差を算出するステップと、を更に含む量子化方法である。
【００１２】
本発明の一態様は、上記の量子化方法であって、前記クラス境界として選択された前記複合要素を前記上部分集合と前記下部分集合に分割した場合、前記下部分集合とその他の前記複合要素により定まる前記複合要素の集合に対する前記近似誤差を算出し、後段の前記クラス境界を選択する処理を行うステップを更に含む量子化方法である。
【００１３】
本発明の一態様は、上記の量子化方法であって、前記複合要素の集合は、前記最下端の前記複合要素の要素である値の最小レベル値が前記最上端の前記複合要素の要素である値の最大レベル値よりも小さい前記複合要素により構成されるステップを更に含む量子化方法である。
【００１４】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置であって、前記入力信号のヒストグラム内の要素の集合である複合要素を構成するヒストグラム生成部と、複数の前記複合要素に含まれる一つ以上の値を代表値で近似した場合の近似誤差を、前記複合要素の集合であるクラスの最下端の前記複合要素内の要素を下端とし、前記クラスの最上端の前記複合要素内の要素を上端として構成される前記入力信号のヒストグラムの区間に対する近似誤差の下限値として定義して、前記クラスの境界であるクラス境界の候補を前記複合要素に制限し、前記クラス境界までの前記近似誤差の累積値を最小化する量子化値と、前記近似誤差の累積値の最小値とをメモリに格納する最小値決定部と、前記クラス境界を選択する際、格納した前記最小値を前記メモリから呼び出し、前記メモリから呼び出した前記最小値を前記クラス境界の選択における前記近似誤差の計算に用いることで、前記クラス境界の全ての前記複合要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択処理を行い、前記クラス境界として選択された前記複合要素が複数の要素を含む場合、選択された前記複合要素を上部分集合と下部分集合とに分割し、分割により得られた前記上部分集合と前記下部分集合を新たに部分集合複合要素に加え、前記クラス境界選択処理を行い、前記クラス境界として選択された前記複合要素の要素数が一つになるまで繰り返す上端追跡部と、を備える量子化装置である。
【００１５】
本発明の一態様は、第１のレベル数で表現される範囲を取り得る値を表す入力信号のヒストグラムを、前記第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化装置のコンピュータに、前記入力信号のヒストグラム内の要素の集合である複合要素を構成する手順と、複数の前記複合要素に含まれる一つ以上の値を代表値で近似した場合の近似誤差を、前記複合要素の集合であるクラスの最下端の前記複合要素内の要素を下端とし、前記クラスの最上端の前記複合要素内の要素を上端として構成される前記入力信号のヒストグラムの区間に対する近似誤差の下限値として定義して、前記クラスの境界であるクラス境界の候補を前記複合要素に制限し、前記クラス境界までの前記近似誤差の累積値を最小化する量子化値と、前記近似誤差の累積値の最小値とをメモリに格納する手順と、前記クラス境界を選択する際、格納した前記最小値を前記メモリから呼び出し、前記メモリから呼び出した前記最小値を前記クラス境界の選択における前記近似誤差の計算に用いることで、前記クラス境界の全ての前記複合要素に対して前記近似誤差の総和を最小化する前記クラス境界を選択するクラス境界選択処理を行う手順と、前記クラス境界として選択された前記複合要素が複数の要素を含む場合、選択された前記複合要素を上部分集合と下部分集合とに分割し、分割により得られた前記上部分集合と前記下部分集合を新たに部分集合複合要素に加え、前記クラス境界選択処理を行い、前記クラス境界として選択された前記複合要素の要素数が一つになるまで繰り返す手順と、を実行させるための量子化プログラムである。
【発明の効果】
【００１６】
本発明により、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】実施形態における、量子化装置の構成の例を示す図である。
【図２】実施形態における、第ｍ段における複合要素内の要素の下限及び上限を定める処理の手順を示す図である。
【図３】実施形態における、適応量子化処理を示すフローチャートである。
【図４】実施形態における、ステップＳ２０５の詳細を示すフローチャートである。
【図５】従来の高ビット深度信号の第１の符号化方法を示す図である。
【図６】従来の高ビット深度信号の第２の符号化方法を示す図である。
【発明を実施するための形態】
【００１８】
本発明の実施形態について、図面を参照して詳細に説明する。
以下、図又は式において変数等の上に付された記号（＾：ハット、〜：チルダ）は、変数の前に記載する。例えば、「＾」が上に付されたｃは、「＾ｃ」と表記する。以下、図又は式において変数又は記号の下付きの記号等と上付きの記号等とでは、下付きの記号等を先に記載する。例えば、下付き「１」と上付き「＊」とが付された変数Δは、「Δ１＊」と表記する。例えば、下付き「ｉ＝０」と上付き「ｍ」とが付された記号Σは、「Σｉ＝０ｍ」と表記する。
【００１９】
[適応量子化装置]
図１は、量子化装置１の構成の例を示す図である。量子化装置１は、パーソナルコンピュータ、タブレット端末、スマートフォン端末、サーバ装置等の情報処理装置である。量子化装置１は、第１のレベル数（階調数）で表現される範囲を取り得る値を表す入力信号のヒストグラムを、第１のレベル数よりも少ない第２のレベル数で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する量子化処理（適応量子化）を実行する。
【００２０】
量子化装置１は、ヒストグラム生成部１１と、要素数記憶部１２と、クラス数記憶部１３と、近似誤差決定部１４と、近似誤差記憶部１５と、初期化部１６と、複合要素記憶部１７と、最小値決定部１８と、最小記憶部１９と、上端追跡部２０と、上端記憶部２１と、更新判定部２２と、要素更新部２３と、インデックス変換部２４と、切替部２５とを備える。
【００２１】
ヒストグラム生成部１１と、近似誤差決定部１４と、初期化部１６と、最小値決定部１８と、上端追跡部２０と、更新判定部２２と、要素更新部２３と、インデックス変換部２４と、切替部２５との一部または全部は、例えば、ＣＰＵ（Central Processing Unit）等のプロセッサが、記憶部に記憶されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部のうち一部または全部は、ＬＳＩ（Large Scale Integration）やＡＳＩＣ（Application Specific Integrated Circuit）等のハードウェア機能部であってもよい。
【００２２】
要素数記憶部１２と、クラス数記憶部１３と、近似誤差記憶部１５と、複合要素記憶部１７と、最小記憶部１９と、上端記憶部２１との一部または全部は、例えば、磁気ハードディスク装置や半導体記憶装置等の不揮発性の記憶媒体（非一時的な記録媒体）を有する記憶装置を用いて構成される。各記憶部は、例えば、ＲＡＭ（Random Access Memory）やレジスタなどの揮発性の記憶媒体を有していてもよい。
【００２３】
ヒストグラム生成部１１は、入力信号を取得する。ヒストグラム生成部１１は、入力信号のヒストグラムを生成する。ヒストグラム生成部１１は、入力信号のヒストグラム及び入力信号のレベル数Ｋを、要素数記憶部１２に記憶させる。
要素数記憶部１２は、入力信号のヒストグラムと、入力信号のレベル数Ｋとを記憶する。
クラス数記憶部１３は、量子化クラス数Ｍを記憶する。
【００２４】
近似誤差決定部１４は、入力信号のヒストグラムと、入力信号のレベル数Ｋとを、要素数記憶部１２から取得する。近似誤差決定部１４は、量子化クラス数Ｍをクラス数記憶部１３から取得する。近似誤差決定部１４は、ヒストグラム内の区間を代表値で近似した場合の近似誤差を算出する。
近似誤差記憶部１５は、ヒストグラム内の区間を代表値で近似した場合の近似誤差を記憶する。
【００２５】
以下、Ｋは、入力信号のレベル数（以下、「入力レベル数」という。）を示す。Ｍ（Ｍ＜Ｋ）は、量子化された入力信号に基づく出力信号のレベル数（以下、「量子化レベル数」という。）を示す。画素値ｋのヒストグラム（頻度）をｈ［ｋ］（ｋ＝０，…，Ｋ−１）と表記する。
【００２６】
初期化部１６は、ヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）を要素数記憶部１２から取得する。初期化部１６は、入力信号値のヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）を、Ｇ（ｎ）＝｛ｇ（ｎ）［〜ｋ］｜〜ｋ＝０，…，〜Ｋ（ｎ）−１｝にグループ化する。ｎは、後述するアルゴリズムのループ回数（更新回数）を表すインデックスである。初期化部１６は、ヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）の複合要素ｇ（ｎ）［〜ｋ］の初期値を、Ｇ（０）＝｛ｇ（０）［〜ｋ］｜〜ｋ＝０，…，〜Ｋ（０）−１｝と定める。
【００２７】
複合要素記憶部１７は、ヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）の複合要素を記憶する。以下、代表値を付与して近似を行う複合要素の集合を、「複合量子化クラス」という。
【００２８】
最小値決定部１８は、遷移先の複合要素内の最大要素と遷移元の複合要素内の最小要素を両端点とするヒストグラム内の区間に対して、同区間の重心で近似した場合の複合量子化クラスの近似誤差を算出する。最小値決定部１８は、近似誤差記憶部１５に記憶されている近似誤差の値を、必要な近似誤差の値として扱う。
【００２９】
最小値決定部１８は、複合要素の最適な複合量子化クラスを決定する。最小値決定部１８は、複合要素の最適な複合量子化クラスに対応する近似誤差を、最小値記憶部１９に記憶させる。最小値記憶部１９は、複合要素の最適な複合量子化クラスに対応する近似誤差を記憶する。
【００３０】
上端追跡部２０は、最小値決定部１８が算出した複合要素の最適な複合量子化クラスを表す複合量子化クラスの上端にあたる複合要素のインデックスを、上端記憶部２１に記憶させる。
【００３１】
更新判定部２２は、最適な複合量子化クラスの上端に相当する全ての複合要素内の要素数を取得する。更新判定部２２は、全ての要素数が１である場合、最適な複合量子化クラスの上端に相当する複合要素を、切替部２５を介して要素更新部２３に送信する。更新判定部２２は、要素数のいずれかが１でない場合、トリガー信号を、切替部２５を介してインデックス変換部２４に送信する。
【００３２】
要素更新部２３は、最適な複合量子化クラスの上端に相当する複合要素を取得する。要素更新部２３は、要素数が２以上となる複合要素を、上部分集合と下部分集合に分解する。要素更新部２３は、上部分集合と下部分集合との頻度値の差がなるべく小さくなるように、要素数が２以上となる複合要素を分割する。要素更新部２３は、分割により得られた上部分集合と下部分集合を、新たな複合要素として、複合要素記憶部１７に記憶させる。
【００３３】
要素更新部２３は、分割により得られた上部分集合を、複合量子化クラスの上端の候補として複合要素記憶部１７に記憶させる。要素更新部２３は、分割により得られた下部分集合を、複合量子化クラスの下端の候補として複合要素記憶部１７に記憶させる。
【００３４】
インデックス変換部２４は、トリガー信号を更新判定部２２から取得した場合、上端記憶部２１に記憶されている複合量子化クラスの上端にあたるＭ個の複合要素のインデックスを取得する。インデックス変換部２４は、上記の各複合要素に含まれる要素に対する要素インデックスを、最適な量子化クラスの上端を表す情報として各々出力する。
切替部２５は、更新判定部２２による制御に応じて、信号の経路を切り替える。
【００３５】
[量子化器の設計]
画像信号（輝度信号）が８ビットである場合、画素値ｋの取り得る範囲は、０から「入力レベル数−１」までの整数、すなわち、０から２５５の値となる。入力レベル数Ｋの画像信号を量子化レベル数の画像信号に量子化する場合を考える。求めるべきパラメータは、式（１）を満たすＭ個のパラメータである。
【００３６】
【数１】
0006441833.tif 000002
【００３７】
ここで、Ｌｍは、ヒストグラムにおける第ｍ区間の上端であり、式（２）で定義される。
【００３８】
【数２】
0006441833.tif 000003
【００３９】
ここで、Δｍはヒストグラムの第ｍ区間の区間幅を表す。また、量子化後の各階調が、少なくとも一つ以上、量子化前の階調を含む必要があることから、Ｌｍ(０≦ｍ≦Ｍ−２）は、ｍ≦Ｌｍ≦Ｋ−（Ｍ−ｍ）の範囲に制限される。ＬＭ−１がＬＭ−１＝Ｋ−１に固定されているので、Ｌｍについては、ｍ＝Ｍ−１を省略し、ｍ≦Ｍ−２を考えれば良い。
【００４０】
ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）は、式（３）によって表される。式（３）は、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］を代表値ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）で近似した場合の近似誤差である。
【００４１】
【数３】
0006441833.tif 000004
【００４２】
さらに、＾ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）は、式（４）によって求まる実数値ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）を四捨五入して整数化した値である。
【００４３】
【数４】
0006441833.tif 000005
【００４４】
ｃ（Ｌｍ−（Δｍ−１），Ｌｍ）は、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］における重心位置を表す。以下、ヒストグラムの区間［Ｌｍ−（Δｍ−１），Ｌｍ］ を、「第ｍ量子化クラス」という。
【００４５】
Ｍ個のパラメータ(Δ１，…，ΔＭ)の取り得る組み合わせは、Ｍとともに指数関数的に増加するため、この中から最適な組み合わせ(Δ１＊，…，ΔＭ＊）を総当りで探索するのは、計算量的に困難である。そこで、第ｍ量子化クラスの量子化誤差ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が同クラスの上端Ｌｍと同クラスの区間幅Δｍに依存することに着目し、以下のように最適解を算出する。さらに、その際、ヒストグラムの非有意要素に基づく演算量削減を行う。
【００４６】
[基本解法]
まず、ヒストグラムの区間［０，Ｌｍ］を（ｍ＋１）分割した際の近似誤差和Σｉ＝０ｍｅ（Ｌｉ−（Δｉ−１），Ｌｉ）の最小値を、Ｓｍ（Ｌｍ）と表記する。つまり、最適なΔｍ，…，Δ０を用いた場合のΣｉ＝０ｍｅ（Ｌｉ−（Δｉ−１），Ｌｉ）に対する最小値である。ここで、ｅ（Ｌｍ−（Δｍ−１），Ｌｍ）が第ｍ量子化クラスの上端Ｌｍと同クラスの区間幅Δm に依存することに着目すると、Ｓｍ（Ｌｍ）は、Ｓｍ−１（Ｌｍ−Δｍ）を用いて、式（５）によって表わされる。
【００４７】
【数５】
0006441833.tif 000006
【００４８】
なお、ｍ＝１，…，Ｍ−１である。また、Ｌｍ＝ｍ，…，Ｋ−（Ｍ−ｍ）である。Δｍ の範囲は、式（６）のようになる。Ｌｍ−１＝Ｌｍ−Δｍであることから、Ｌｍ−Δｍの範囲は、ｍ−１≦Ｌｍ−Δｍ≦Ｋ−（Ｍ−ｍ＋１）となる。このため、Δｍの範囲は、与えられたＬｍを用いて、式（６）によって表わされる。
【００４９】
【数６】
0006441833.tif 000007
【００５０】
さらに、Δｍ≧１であることを考慮すると、式（７）を得る。
【００５１】
【数７】
0006441833.tif 000008
【００５２】
ここで、算出したＳｍ（Ｌｍ）を格納しておき、Ｓｍ＋１（Ｌｍ＋１）の計算で用いる。さらに、式(１３)の右辺を最小化するΔｍの値をΔｍ(Ｌｍ)として、各Ｌｍ（＝ｍ，…，ｋ−Ｍ＋ｍ）に対して＾Ｌｍ−１［Ｌｍ］＝Ｌｍ−Δｍ（Ｌｍ）を格納する。式（１）の最小化問題は、式（８）のように表わされる。
【００５３】
【数８】
0006441833.tif 000009
【００５４】
式（８）を最小化するΔＭ−１を、式（９）に示すようにΔＭ−１＊と表記する。
【００５５】
【数９】
0006441833.tif 000010
【００５６】
このΔＭ−１＊を用いて、第Ｍ−２クラスの上端の最適値は、ＬＭ−２＊＝ＬＭ−１ −ΔＭ−１＊＝Ｋ−１−ΔＭ−１＊と求まる。第Ｍ−３クラスの上端の最適値は、ＬＭ−２＊に対する最適解として、＾ＬＭ−３[ＬＭ−２＊]として格納されているので、該当する値を参照し、ＬＭ−３＊＝^ＬＭ−３［ＬＭ−２］となる。この結果、第Ｍ−２クラスの区間幅は、ΔＭ−２＊＝ＬＭ−２＊−ＬＭ−３＊と求まる。
【００５７】
以下、同様の参照処理をＬＭ−４＊＝＾ＬＭ−４［ＬＭ−３＊］,…,Ｌ０＊＝^Ｌ０［Ｌ１＊］として繰り返し、得られた各クラスの上端値を用いて、ΔＭ−３＊＝ＬＭ−３＊−ＬＭ−４＊,…,Δ０＊＝Ｌ０＊−Ｌ−１＊として求める。なお、Ｌ−１＝−１である。
【００５８】
視覚系は、低輝度の画素値の変化に比べて、高輝度の画素値の変化に鈍感である。そこで、こうした視覚特性を考慮して量子化を行う場合は、以下のように行う。以下、ｗ［ｋ］は、画素値ｋ（ｋ＝０，…，Ｋ−１）に対する重み係数を示す。重み係数ｗ［ｋ］は、予め定められる。例えば、高輝度(大きなｋ)の重みを低輝度(小さなｋ)の重みより小さな値に設定すれば、高輝度と低輝度との差（輝度差）に対する視覚特性を量子化処理に組み込むことが可能になる。重み係数ｗ［ｋ］を用いて、画素値ｋに対する頻度ｈ［ｋ］を〜ｈ［ｋ］＝ｗ［ｋ］ｈ［ｋ］として補正し、この補正後のヒストグラム〜ｈ［ｋ］に対して、前述の量子化処理を実施する。
【００５９】
［クラスの統合及び分割に基づく演算量削減］
初期化部１６は、入力信号値のヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）を、Ｇ（ｎ）＝｛ｇ（ｎ）［〜ｋ］｜〜ｋ＝０，…，〜Ｋ（ｎ）−１｝にグループ化する。ここで、複合要素ｇ（ｎ）［〜ｋ］は、第〜ｋ番目のグループとして、ヒストグラムの第ｌ［〜ｋ］（ｎ）要素から第ｕ［〜ｋ］（ｎ）要素までをグループ化したヒストグラムの要素の集合である。ｇ（ｎ）［〜ｋ］は、ｇ（ｎ）［〜ｋ］＝｛ｈ［ｋ］｜ｋ＝ｌ［〜ｋ］（ｎ），…，ｕ［〜ｋ］（ｎ）｝のように表される。
【００６０】
また、第〜ｋグループ内のヒストグラムの要素数を、「｜｜ｇ（ｎ）［〜ｋ］｜｜＝ｕ［〜ｋ］（ｎ）−ｌ［〜ｋ］（ｎ）＋１」と表す。なお、ｌ［０］（ｎ）＝０であり、ｕ［〜Ｋ］（ｎ）＝Ｋ−１である。複合要素ｇ（ｎ）［〜ｋ］におけるｌ［〜ｋ］（ｎ）要素（最下端の要素）を、「最下位要素インデックス」という。また、複合要素ｇ（ｎ）［〜ｋ］におけるｕ［〜ｋ］（ｎ）要素（最上端の要素）を、「最上位要素インデックス」という。
【００６１】
[グループ化されたヒストグラムに対する量子化]
複合要素の集合｛ｇ（ｎ）［〜ｋ］｜〜ｋ＝０，…，Ｌ〜ｍ｝を（〜ｍ＋１）個の部分集合に分割し、部分集合ごとに代表値でヒストグラムを近似することを考える。複合量子化クラス近似に対して、対応するヒストグラムの区間の近似誤差の下限値を用いて評価する。
【００６２】
このとき、求めるべきパラメータは、式（１０）を満たす〜Ｍ個のパラメータである。
【００６３】
【数１０】
0006441833.tif 000011
【００６４】
ここで、Ｌ〜ｍは、複合要素の集合における第〜ｍ部分集合の上端であり、式（１１）によって表される。
【００６５】
【数１１】
0006441833.tif 000012
【００６６】
ここで、Δ〜ｍは、複合要素の第〜ｍ部分集合の複合要素数を表す。〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）は、式（１２）によって求まる値である。〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）は、第Ｌ〜ｍ−(Δ〜ｍ−１)番目の複合要素内の最大要素と第Ｌ〜ｍ番目の複合要素内の最小要素を両端点とするヒストグラム内の区間に対して、同区間の重心で近似した場合の近似誤差である。
【００６７】
【数１２】
0006441833.tif 000013
【００６８】
式（１２）の値は、複合要素の部分集合［Ｌ〜ｍ−Δ〜ｍ−１），Ｌ〜ｍ］に対して、第Ｌ〜ｍ−(Δ〜ｍ−１)番目の複合要素内のいずれかの要素と第Ｌ〜ｍ番目の複合要素内のいずれかの要素とを両端点とするヒストグラム内の区間に対して、同区間の重心で近似した場合の近似誤差の下限値として導入した値である。以下、複合要素の部分集合［Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ］を、「第〜ｍ複合量子化クラス」という。
【００６９】
上記の近似誤差の下限値の和Σｉ＝０〜ｍ〜ｅ（Ｌｉ−（Δｉ−１），Ｌｉ）の最小値を、Ｓ〜ｍ（Ｌ〜ｍ）と表記する。つまり、最適なΔ〜ｍ，…，Δ０を用いた場合のΣｉ＝０〜ｍ〜ｅ（Ｌｉ−（Δｉ−１），Ｌｉ）に対する最小値である。ここで、〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）が第〜ｍ複合量子化クラスの上端Ｌ〜ｍと同クラスの区間幅Δ〜ｍに依存することに着目すると、Ｓ〜ｍ（Ｌ〜ｍ）は、Ｓ〜ｍ−１（Ｌ〜ｍ−Δ〜ｍ）を用いて、式（１３）によって表わされる。
【００７０】
【数１３】
0006441833.tif 000014
【００７１】
なお、〜ｍ＝１，…，〜Ｍ−１である。また、Ｌ〜ｍ＝〜ｍ，…，〜Ｋ−（〜Ｍ−〜ｍ）である。
【００７２】
Δ〜ｍの範囲は、次のようになる。Ｌ〜ｍ−１＝Ｌ〜ｍ−Δ〜ｍであることから、Ｌ〜ｍ−Δ〜ｍの範囲は、〜ｍ−１≦Ｌ〜ｍ−Δ〜ｍ≦〜Ｋ−（〜Ｍ−〜ｍ＋１）となる。このため、Δ〜ｍの範囲は、与えられたＬ〜ｍを用いて式（１４）によって表される。
【００７３】
【数１４】
0006441833.tif 000015
【００７４】
さらに、Δ〜ｍ≧１であることを考慮すると、式（１５）を得る。
【００７５】
【数１５】
0006441833.tif 000016
【００７６】
ここで、算出したＳ〜ｍ（Ｌ〜ｍ）を格納しておき、Ｓ〜ｍ＋１（Ｌ〜ｍ＋１）の計算で用いるものとする。さらに、式(１３) の右辺を最小化するΔ〜ｍの値をΔ〜ｍ（Ｌ〜ｍ）として、各Ｌ〜ｍ（＝〜ｍ，…，〜Ｋ−〜Ｍ＋〜ｍ）に対して＾Ｌ〜ｍ−１［Ｌ〜ｍ］＝Ｌ〜ｍ−Δ〜ｍ（Ｌ〜ｍ）を格納しておくものとする。式（１）の最小化問題は、式（１６）によって表される。
【００７７】
【数１６】
0006441833.tif 000017
【００７８】
以下、式（１６）を最小化するΔ〜Ｍ−１を、「Δ〜Ｍ−１＊」と表記する。Δ〜Ｍ−１＊は、式（１７）によって表される。
【００７９】
【数１７】
0006441833.tif 000018
【００８０】
第〜Ｍ−２複合量子化クラスの上端の最適値は、Ｌ〜Ｍ−２＊＝Ｌ〜Ｍ−１−Δ〜Ｍ−１＊＝〜Ｋ−１−Δ〜Ｍ−１＊と定まる。第〜Ｍ−３複合量子化クラスの上端の最適値は、Ｌ〜Ｍ−２＊に対する最適解＾Ｌ〜Ｍ−３［Ｌ〜Ｍ−２＊］として格納されている。第〜Ｍ−３複合量子化クラスの上端の最適値は、格納されている値に基づいて、Ｌ〜Ｍ−３＊＝＾Ｌ〜Ｍ−３［Ｌ〜Ｍ−２＊］と定まる。第〜Ｍ−２複合量子化クラスの区間幅は、Δ〜Ｍ−２＊＝Ｌ〜Ｍ−２＊−Ｌ〜Ｍ−３＊と定まる。
【００８１】
以下、同様の参照処理をＬ〜Ｍ−４＊＝＾Ｌ〜Ｍ−４＊［Ｌ〜Ｍ−３＊］,…,Ｌ０＊＝＾Ｌ０＊［Ｌ１＊］として繰り返し、得られた各複合量子化クラスの上端値を用いて、Δ〜Ｍ−３＊＝Ｌ〜Ｍ−３＊−Ｌ〜Ｍ−４＊,…,Δ０＊＝Ｌ０＊−Ｌ−１＊として求める。なお、Ｌ−１＊＝−１である。
【００８２】
上記の処理で得られたｇ（ｎ）［Ｌ〜ｍ＊］（〜ｍ＝０，…，〜Ｍ）に対して、終了条件の判定を行う。終了条件は、最適解として得られた全ての複合要素が単一の要素のみから構成されるようになること、すなわち、｜｜ｇ（ｎ）［Ｌ〜ｍ＊］｜｜＝１（〜ｍ＝０，…，〜Ｍ）を満たすことである。
【００８３】
上記の条件を満たさない場合、つまり、｜｜ｇ（ｎ）［Ｌ〜ｍ＊］｜｜＞１を満たす複合要素が存在する場合、同要素を分割して、分割により得られた複合要素の集合に対して、上記と同様の量子化処理を行う。この反復を上述の終了条件を満たすまで繰り返す。なお、この複合要素の分割方法は後述する。
【００８４】
[複合要素の構成方法]
図２は、第ｍ段における複合要素内の要素の下限及び上限を定める処理の手順を示す図である。複合要素内の頻度値和は、図２に示す処理の手順によって、可能な範囲で均等になる。図２に示す処理の手順を以下に説明する。複合要素のインデックスに初期値０を代入する（ステップＳ１０１）。
【００８５】
後段の処理で用いる変数を０に初期化する（ステップＳ１０２）。
第ｍ段におけるｌ［０］はｌ［０］＝ｍに設定される（ステップＳ１０３）。これは、第ｍ段における選択可能なヒストグラムの要素は、ｍ≦ｋ≦ｍ−Ｍ＋Ｋであるためである。
不等式「ｍ≦ｋ≦ｍ−Ｍ＋Ｋ」が示すヒストグラムの区間に対して、ステップＳ１０５〜Ｓ１１０を繰り返す(ステップＳ１０４)。
【００８６】
ヒストグラムの区間の累積頻度値和を変数ｓに格納する（ステップＳ１０５）。変数ｓの累積頻度値和が閾値θを超えた場合（ステップＳ１０６）、そのときのインデックスｋを複合要素の上限とする（ステップＳ１０７）。
複合要素のインデックス〜ｋをインクリメントする（ステップＳ１０８）。
次の複合要素の下限値としてインデックス〜ｋを格納する（ステップＳ１０９）。
ヒストグラムの区間の累積頻度値和を格納するための変数sを０に初期化する（ステップＳ１１０）。上記で用いた閾値θは、式（１８）によって表される。式（１８）に示す閾値θは、実数「Σｋ＝０Ｋ−１ｈ［ｋ］／〜Ｋ（ｎ）」を超えない最大の整数である。
【００８７】
【数１８】
0006441833.tif 000019
【００８８】
あるいは、複合要素の別の構成例として、複合要素内の要素数が均等になるように、同要素数として固定値Ｂを与えることも可能である。複合要素に対するトレリス遷移図は、複合要素間のパスに関する以下の条件を満たすように設定する。
【００８９】
[複合要素の分割方法]
最適な複合量子化クラスの上端にあたる複合要素が、複数の要素から構成されている場合、同複合要素を２個の部分集合に分割する。具体的な分割は、分割対象となる複合要素に対して、分割後の複合要素内の頻度値和がなるべく均等になるように実施する。以下、分割により得られる２個の部分集合のうち大きな要素インデックスを含む部分集合を、「上部分集合」という。以下、分割により得られる２個の部分集合のうち小さな要素インデックスを含む部分集合を、「下部分集合」という。
【００９０】
最適な第ｍ−１番目の複合量子化クラスの上端にあたる複合要素を分割して得た下部分集合に対して、同下部分集合を複合量子化クラスの下端の候補として追加する。なお、このとき、複合量子化クラスの上端として設定可能な複合要素の条件は、複合量子化クラスの上端となる複合要素内の最上位要素インデックスが前述の下部分集合に対応する複合量子化クラスの下端となる複合要素内の最下位要素インデックスよりも大きな値となることである。
【００９１】
第ｍ段における遷移可能な複合要素（上記の分割により生成された上部分集合と、下部分集合とを含む）に対して、新しい遷移パスを追加する。また、追加した遷移パスに対するコスト値もあわせて算出する。
【００９２】
最適な第ｍ−１番目の複合量子化クラスの上端にあたる複合要素を分割して得た上部分集合に対して、同上部分集合を複合量子化クラスの上端の候補として追加する。なお、このとき、複合量子化クラスの上端として設定可能な複合要素の条件は、複合量子化クラスの上端となる複合要素内の最上位要素インデックスが前述の上部分集合に対応する複合量子化クラスの下端となる複合要素内の最下位要素インデックスよりも大きな値となることである。
【００９３】
同上部分集合を下端とする複合量子化クラスの上端として、最適な第ｍ番目の複合量子化クラスの上端にあたる複合要素を分割して得た上部分集合を用いる場合、同複合量子化クラスの近似誤差は、新たに参照テーブルから取得される。一方、同複合量子化クラスの上端として、上記以外の複合要素を用いる場合、同複合量子化クラスの近似誤差は、同上部分集合の分割前の複合量子化クラスの上端にあたる複合要素を同複合量子化クラスの下端とした場合の近似誤差と同一である。これは、同上部分集合の分割前の複合量子化クラスの上端にあたる複合要素を同上部分集合の上端にあたる複合要素は同一である為である。
【００９４】
第ｍ段における最適パス上の複合要素が複数の要素から構成されており、同複合要素が下部分集合と上部分集合に分割された場合、第ｍ−１段における上部分集合から第ｍ段における分割後の上部分集合に対して新たしい遷移パスを追加する。この追加した遷移パス以外は、第ｍ−１段の分割前の複合要素から第ｍ段における分割前の複合要素に対する遷移コストと同一である。なお、第ｍ段における最適パス上の複合要素が単一要素で構成されており、同複合要素に対する分割がなされない場合は、新たな遷移パスの追加は行われない。
【００９５】
第ｍ−１段における複合要素から遷移可能な第ｍ段における複合要素とは、第ｍ段における複合要素の最上位要素インデックスが第ｍ−１段における複合要素の最下位要素インデックスよりも大きな値となる複合要素である。
【００９６】
なお、別の分割方法として、複合要素内の要素数が均等になるように、分割することも可能である。複合要素内の要素間に遷移可能なパスがある場合は、複合要素間のパスを設けるものとする。複合要素間のパスが有する遷移コストは複合要素内の要素間のパスの遷移コストの最小値とする。
【００９７】
[適応量子化処理]
図３は、適応量子化処理を示すフローチャートである。
ヒストグラム生成部１１は、入力信号を取得する。ヒストグラム生成部１１は、入力信号値のヒストグラムｈ［Ｋ］（ｋ＝０，…，Ｋ−１）を生成する（ステップＳ２０１）。
近似誤差決定部１４は、入力信号値のヒストグラムを取得する。近似誤差決定部１４は、ヒストグラム内の区間を代表値で近似した場合の近似誤差を、式（３）に基づいて算出する。近似誤差決定部１４は、算出した近似誤差を近似誤差記憶部１５の参照テーブルに格納する（ステップＳ２０２）。
【００９８】
初期化部１６は、ステップＳ２０１で生成したヒストグラムを取得する。初期化部１６は、ヒストグラムを複合要素に分割する。すなわち、初期化部１６は、取得したヒストグラムｈ［ｋ］（ｋ＝０，…，Ｋ−１）の複合要素を、図２に示す処理手順に基づいて、Ｇ（０）＝｛ｇ（０）［〜ｋ］｜〜ｋ＝０，…，〜Ｋ（０）−１｝と定める（ステップＳ２０３）。
【００９９】
最小値決定部１８は、ヒストグラムと、各複合要素の上端及び下端とを取得する。最小値決定部１８は、ヒストグラム内の区間を代表値で近似した場合の近似誤差を、式（１２）に基づいて算出する。最小値決定部１８は、算出した近似誤差を各複合量子化クラスの近似誤差として、最小値記憶部１９の参照テーブルに格納する。最小値決定部１８は、遷移先の複合要素内の最大要素と遷移元の複合要素内の最小要素を両端点とするヒストグラム内の区間に対して、同区間の重心で近似した場合の近似誤差として設定する。最小値決定部１８は、ステップＳ２０２で生成した参照テーブルを参照することで、近似誤差を定める（ステップＳ２０４）。
【０１００】
最小値決定部１８は、複合要素の最適な複合量子化クラスを決定する（ステップＳ２０５）。最適な複合量子化クラスの上端に相当する全ての複合要素内の要素数を取得する。最小値決定部１８は、全ての要素数が１であるか否かを判定する（ステップＳ２０６）。
【０１０１】
最小値決定部１８は、最適な複合量子化クラスの上端に相当する複合要素を取得する。最小値決定部１８は、要素数が２以上となる複合要素を上部分集合と下部分集合とに分解する。最小値決定部１８は、上部分集合と下部分集合との頻度値の差がなるべく小さくなるように、要素数が２以上となる複合要素を分割する（ステップＳ２０７）。
【０１０２】
要素更新部２３は、量子化後のクラスｍ＝１，…，Ｍ−１について、ステップＳ２０９及びステップＳ２１０を繰り返す（ステップＳ２０８）。
要素更新部２３は、最適な第ｍ−１番目の複合量子化クラスの上端にあたる複合要素を分割して得た下部分集合に対して、同下部分集合を複合量子化クラスの下端の候補として追加する。なお、このとき、複合量子化クラスの上端として設定可能な複合要素の条件は、複合量子化クラスの上端となる複合要素内の最上位要素インデックスが前述の下部分集合に対応する複合量子化クラスの下端となる複合要素内の最下位要素インデックスよりも大きな値となることである（ステップＳ２０９）。
【０１０３】
要素更新部２３は、最適な第ｍ−１番目の複合量子化クラスの上端にあたる複合要素を分割して得た上部分集合に対して、同上部分集合を複合量子化クラスの上端の候補として追加する。なお、このとき、複合量子化クラスの上端として設定可能な複合要素の条件は、複合量子化クラスの上端となる複合要素内の最上位要素インデックスが前述の上部分集合に対応する複合量子化クラスの下端となる複合要素内の最下位要素インデックスよりも大きな値となることである。
【０１０４】
要素更新部２３は、同上部分集合を下端とする複合量子化クラスの上端として、最適な第ｍ番目の複合量子化クラスの上端にあたる複合要素を分割して得た上部分集合を用いる場合、同複合量子化クラスの近似誤差を、新たに参照テーブルから取得する。一方、同複合量子化クラスの上端として、上記以外の複合要素を用いる場合、同複合量子化クラスの近似誤差は、同上部分集合の分割前の複合量子化クラスの上端にあたる複合要素を同複合量子化クラスの下端とした場合の近似誤差と同一である（ステップＳ２１０）。
【０１０５】
要素更新部２３は、量子化後のクラスｍがＭ未満であるか否かを判定する（ステップＳ２１１）。量子化後のクラスｍがＭである場合、ステップＳ２０８に処理を戻す。量子化後のクラスｍがＭ未満である場合、ステップＳ２０５に処理を戻す。
【０１０６】
インデックス変換部２４は、最適な複合量子化クラスの上端にあたるＭ個の複合要素の要素インデックスを出力する。同複合要素はいずれも要素を１個しか含まないため、同複合要素の要素としては一意に同定できる（ステップＳ２１２）。
【０１０７】
図４は、図３に示すステップＳ２０５の詳細を示すフローチャートである。なお、図４では、〜ｍをｍと表記する。〜ＭをＭと表記する。〜ｋをｋと表記する。Ｌ０をＬ＿０と表記する。Ｌ〜ｍをＬ＿ｍと表記する。
【０１０８】
最小値決定部１８は、入力信号のヒストグラムを取得する（ステップＳ３０１）。
最小値決定部１８は、Ｌ０を０に初期化する（ステップＳ３０２）。
最小値決定部１８は、ｉ＝１，…，〜Ｋ−〜Ｍ＋１について、Ｓ０（ｉ）を０に初期化する（ステップＳ３０３）。
最小値決定部１８は、量子化後のレベル〜ｍ＝１，…，〜Ｍ−１について、ステップＳ３０５からステップＳ３１３を繰り返す（ステップＳ３０４）。
【０１０９】
最小値決定部１８は、上端Ｌ〜ｍ＝〜ｍ，…，〜Ｋ−（〜Ｍ−〜ｍ）−１について、ステップＳ３０６からステップＳ３１２を繰り返す。Ｌ〜ｍは、〜ｍ番目の量子化レベルに対応するヒストグラムの区間の上端を表す（ステップＳ３０５）。
最小値決定部１８は、区間幅Δ〜ｍ＝１，…，Ｌ〜ｍ−（〜ｍ−１）−１について、ステップＳ３０７からステップＳ３０９を繰り返す。Δ〜ｍは、ｍ番目の量子化レベルに対応するヒストグラムの区間の区間幅を示す（ステップＳ３０６）。
【０１１０】
最小値決定部１８は、第Ｌ〜ｍ＝（Δ〜ｍ−１）番目の複合要素内の最大の要素インデックスと、第Ｌ〜ｍ番目の複合要素内の最小の要素インデックスと、近似誤差を格納したテーブルとを取得する。最小値決定部１８は、複合要素の部分集合［Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ］に対する近似誤差の下限値〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ］を、式（１２）に基づいて算出する（ステップＳ３０７）。
【０１１１】
最小値決定部１８は、Ｓ〜ｍ−１（Ｌ〜ｍ−Δ〜ｍ）及び〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）を取得する。最小値決定部１８は、Ｓ〜ｍ−１（Ｌ〜ｍ−Δ〜ｍ）＋〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）を算出する（ステップＳ３０８）。
最小値決定部１８は、区間幅Δ〜ｍがＬｍ−（ｍ−１）未満であるか否かを判定する（ステップＳ３０９）。最小値決定部１８は、区間幅Δ〜ｍがＬｍ−（ｍ−１）未満である場合、ステップＳ３０６に処理を戻す。
【０１１２】
最小値決定部１８は、区間幅Δ〜ｍがＬｍ−（ｍ−１）である場合、Δ〜ｍ＝１，…，Ｌｍ−（ｍ−１）について、Ｓ〜ｍ−１（Ｌ〜ｍ−Δ〜ｍ）＋〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）の最小値を算出し、変数Ｓ〜ｍ（Ｌ〜ｍ）に格納する（ステップＳ３１０）。
【０１１３】
最小値決定部１８は、Ｓ〜ｍ−１（Ｌ〜ｍ−Δ〜ｍ）＋〜ｅ（Ｌ〜ｍ−（Δ〜ｍ−１），Ｌ〜ｍ）を最小化するΔ〜ｍの値を、Δ〜ｍ（Ｌ〜ｍ）と定める。最小値決定部１８は、各Ｌ〜ｍについて、＾Ｌ〜ｍ−１［Ｌ〜ｍ］＝Ｌ〜ｍ−Δ〜ｍ（Ｌ〜ｍ）を格納する（ステップＳ３１１）。
【０１１４】
最小値決定部１８は、上端Ｌ〜ｍが〜Ｋ−（〜Ｍ−〜ｍ）未満であるか否かを判定する（ステップＳ３１２）。最小値決定部１８は、上端Ｌ〜ｍが〜Ｋ−（〜Ｍ−〜ｍ）未満である場合、ステップＳ３０５に処理を戻す。
最小値決定部１８は、上端Ｌ〜ｍが〜Ｋ−（〜Ｍ−〜ｍ）である場合、量子化後のレベル〜ｍが〜Ｍ未満であるか否かを判定する（ステップＳ３１３）。
【０１１５】
上端追跡部２０（上端決定部）は、量子化後のレベル〜ｍが〜Ｍ未満である場合、第〜Ｍ−１複合量子化クラスの最適化区間幅を式（１７）に従って算出し、変数Δ〜Ｍ−１＊に格納する。上端追跡部２０は、第〜Ｍ−２複合量子化クラスの上端の最適値〜ｋ−１−Δ〜Ｍ−１＊を算出し、変数Ｌ〜Ｍ−２＊に格納する（ステップＳ３１４）。
上端追跡部２０は、量子化後のレベル〜ｍ＝〜Ｍ−２，…，０について、〜ｍの増分を−１にして、ステップＳ３１６を繰り返す（ステップＳ３１５）。
【０１１６】
上端追跡部２０は、複合量子化クラスの上端値Ｌ〜ｍ＝＾Ｌ〜ｍ［Ｌ〜ｍ＋１＊］を算出する（ステップＳ３１６）。
上端追跡部２０は、量子化後のレベル〜ｍが０以上であるか否かを判定する。上端追跡部２０は、量子化後のレベル〜ｍが０以上である場合、ステップＳ３１５に処理を戻す。上端追跡部２０は、量子化後のレベル〜ｍが−１である場合、図３に示すステップＳ２０５を終了する。
【０１１７】
以上のように、量子化装置１は、第１のレベル数（入力レベル数）で表現される範囲を取り得る値を表す入力信号のヒストグラムを、第１のレベル数よりも少ない第２のレベル数（量子化レベル数）で表現される範囲を取り得る値を表す出力信号のヒストグラムで近似する。量子化装置１は、ヒストグラム生成部１１と、最小値決定部１８と、上端追跡部２０とを備える。ヒストグラム生成部１１は、入力信号のヒストグラム内の要素の集合である複合要素を構成（生成）する。最小値決定部１８は、複数の複合要素に含まれる一つ以上の値を代表値で近似した場合の近似誤差を、複合要素の集合であるクラスの最下端の複合要素内の要素を下端とし、クラスの最上端の複合要素内の要素を上端として構成される入力信号のヒストグラムの区間に対する近似誤差の下限値として定義して、クラスの境界であるクラス境界の候補を複合要素に制限し、クラス境界までの近似誤差の累積値を最小化する量子化値と、近似誤差の累積値の最小値とをメモリに格納する。上端追跡部２０は、クラス境界を選択する際、格納した最小値をメモリから呼び出し、メモリから呼び出した最小値をクラス境界の選択における近似誤差の計算に用いることで、クラス境界の全ての複合要素に対して近似誤差の総和を最小化するクラス境界を選択するクラス境界選択処理を行い、クラス境界として選択された複合要素が複数の要素を含む場合、選択された複合要素を上部分集合と下部分集合とに分割し、分割により得られた上部分集合と下部分集合を新たに部分集合複合要素に加え、クラス境界選択処理を行い、クラス境界として選択された複合要素の要素数が一つになるまで繰り返す。
【０１１８】
これによって、量子化装置１は、信号の階調変換を行う際に発生する変換誤差を最小化する場合でも、量子化に要する演算量を低減することが可能である。
【０１１９】
量子化方法は、複数の複合要素を代表値で近似した場合の近似誤差として、最下端の複合要素の最大レベル値の要素を下端とし、最上端の複合要素の最小レベル値の要素を上端として構成（生成）される入力信号のヒストグラムの区間に対する近似誤差として定義するステップ
を更に含む。
【０１２０】
量子化方法は、クラス境界として選択された複合要素を上部分集合と下部分集合に分割した場合、上部分集合と上部分集合のクラスの一段上のクラスのクラス境界の複合要素を分割して得た上部分集合により定まる複合要素の集合に対する近似誤差を算出するステップと、上部分集合に分割前の複合要素とその他の複合要素の集合に対する近似誤差を再利用して、後段のクラス境界を選択する処理を行った結果に基づいて、上部分集合とその他の複合要素により定まる複合要素の集合に対する近似誤差を算出するステップとを更に含む。
【０１２１】
量子化方法は、クラス境界として選択された複合要素を上部分集合と下部分集合に分割した場合、下部分集合とその他の複合要素により定まる複合要素の集合に対する近似誤差を算出し、後段のクラス境界を選択する処理を行うステップを更に含む。
【０１２２】
量子化方法は、複合要素の集合は、最下端の複合要素の要素である値の最小レベル値が最上端の複合要素の要素である値の最大レベル値よりも小さい複合要素により構成されるステップを更に含む。
【０１２３】
上述した実施形態における量子化装置の少なくとも一部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【０１２４】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１２５】
１…量子化装置、１１…ヒストグラム生成部、１２…要素数記憶部、１３…クラス数記憶部、１４…近似誤差決定部、１５…近似誤差記憶部、１６…初期化部、１７…複合要素記憶部、１８…最小値決定部、１９…最小値記憶部、２０…上端追跡部、２１…上端記憶部、２２…更新判定部、２３…要素更新部、２４…インデックス変換部、２５…切替部
【図１】
0006441833.tif 000020
【図２】
0006441833.tif 000021
【図３】
0006441833.tif 000022
【図４】
0006441833.tif 000023
【図５】
0006441833.tif 000024
【図６】
0006441833.tif 000025