(57)【要約】【課題】  （１）密度関数の推定を解析的ではない方法で、ＦＦＴ（高速フーリエ変換）を用いて高速に行うこと、（２）密度関数を階段状でなく、なめらかな曲線として推定すること、および（３）カットオフ周波数を、密度関数と量子化した画像の濃度ヒストグラムとの類似性を尺度として決定することである。【解決手段】  画像を最適に量子化する方法において、画像の濃度ヒストグラムh(k)を作成する過程、濃度ヒストグラムh(k)にFFT（高速フーリエ変換）を適用して離散的フーリエ変換H*(u)を求める過程、濃度ヒストグラムの離散的フーリエ変換H*(u)に係数関数C(u)をかけて密度関数p(t)のフーリエ変換P(u)を推定する過程、密度関数のフーリエ変換P(u)からカットオフ周波数ucを求める過程、カットオフ周波数ucから量子化間隔Δtを求めて画像を量子化する。【選択図】図９
2005339110.tif 000002
【特許請求の範囲】
【請求項１】
画像を最適に量子化する方法において、
画像の濃度ヒストグラムh(k)を作成する過程、濃度ヒストグラムh(k)にFFT（高速フーリエ変換）を適用して離散的フーリエ変換H*(u)を求める過程、濃度ヒストグラムの離散的フーリエ変換H*(u)に係数関数C(u)をかけて密度関数p(t)のフーリエ変換P(u)を推定する過程、密度関数のフーリエ変換P(u)からカットオフ周波数ucを求める過程、カットオフ周波数ucから量子化間隔Δtを求めて画像を量子化することを特徴とする画像の量子化方法。
【請求項２】
係数関数C(u)にカーディナルスプライン基底関数のフーリエ変換を用いて、密度関数のフーリエ変換P(u)を推定することを特徴とする請求項１記載の画像の量子化方法。
【請求項３】
係数関数C(u)にRECT関数（矩形関数）を用いて密度関数のフーリエ変換P(u)を推定することを特徴とする請求項１記載の画像の量子化方法。
【請求項４】
密度関数のフーリエ変換P(u)のパワースペクトルの総和Sと、密度関数のフーリエ変換P(u)にsinc関数を乗じて得られるスペクトル成分H’(u)のパワースペクトルのうち、カットオフ波長uc 以下のみの総和S’(uc)を求め、S’(uc)≦βSとなるような最大のカットオフ周波数ucを求めることを特徴とする請求項１記載の画像の量子化方法。
【請求項５】
請求項１記載の画像の量子化方法を適用した画像に対し、標本化間引き方法を適用して、画像のデータ量を圧縮することを特徴とする画像圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を量子化または標本化するデジタル化手法および画像圧縮方法に関する。
【背景技術】
【０００２】
アナログ信号をデジタル化して１フレーム分の画像を作る際、水平垂直方向は1ピクセル分解能で標本化（サンプリング）され、濃度（階調)方向は8bitまたは16bitで量子化される。この標本化と量子化をあわせて、離散化またはデジタル化という。最適標本化間隔はシャノンの標本化定理によって決定されるが、最適量子化間隔は通常論議されることはなく、画像メモリのbit数の制約で決まるのが普通である。
【０００３】
これに対し、非特許文献１にあるように、すでに256階調に量子化されたデジタル画像（図1）の濃度ヒストグラム（図2)から、濃度ヒストグラムの連続的な密度関数を推定し（図3）、このフーリエ変換を解析的に求め、これからカットオフ周波数を算出し、このカットオフ周波数から最適量子化間隔を求める方法が提案されている。その方法によれば、256階調の画像を16階調や32階調で量子化しても画質の劣化がほとんどなく、画像圧縮に道を開く画期的な技術として注目されている。
【０００４】
ところが、その方法には以下の3つの問題がある。まず第1に、密度関数（※１)のフーリエ変換は非特許文献1のp4の式(20)で解析的に求めることができるが、これには通常、fmax=256回からなる式(20)の積和演算を各周波数成分毎に計算しなければならず（周波数成分は最大で256個）、最大で256×256回の積和演算が必要になるため、計算コストが大きくなる。第２に、濃度ヒストグラムから密度関数をRECT関数（矩形関数)を用いて推定しているが、この密度関数は階段状の形状（図4）であり、本来なめらかな曲線を描くと推定される密度関数の形状とはほど遠いことである。第3に非特許文献１の4.3節の「カットオフ周波数の推定と別名誤差」にカットオフ周波数の実用解を求める3つの方法が示されているが、3つの方法それぞれの結果が異なるため、どのカットオフ周波数を使えばよいかわからない。たとえば、非特許文献１の4.3節の(1),(2),(3)手法で得たカットオフ周波数を、図3にそれぞれ(1),(2),(3)として表示した。よって、これら3つの方法はあくまでもカットオフ周波数を求める単なる目安にすぎない。推定された連続的な濃度ヒストグラムである密度関数と、量子化した画像の濃度ヒストグラムとの類似性を尺度としていないことが問題である。
【０００５】
※１：非特許文献１ではp4の式(18)のように密度関数を正規化（総和が1になるようにすることを正規化という。)して確率密度関数としているが、この正規化条件は、その後のカットオフ周波数を求める際には何ら影響を与えていない。具体的には、非特許文献１のp4の式(20)で、確率密度関数のフーリエ変換を正規化するために総和Sで割っているが、このような正規化処理がカットオフ周波数を求めるための必要条件になっているわけではない。むしろ、計算コストが増大するだけで不要である。
【非特許文献１】輿水大和他著「量子化定理の提案  画像グレースケール離散化の数理的考察」VIEW2002, p1-6(2002年)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、発明の課題は、（１）密度関数の推定を解析的ではない方法で、ＦＦＴ（高速フーリエ変換）を用いて高速に行うこと、（２）密度関数を階段状でなく、なめらかな曲線として推定すること、および（３）カットオフ周波数を、密度関数と量子化した画像の濃度ヒストグラムとの類似性を尺度として決定することである。
【課題を解決するための手段】
【０００７】
第1の問題に対しては、画像の濃度ヒストグラムh(k)にFFT（高速フーリエ変換）を適用して離散的フーリエ変換H*(u)を求め、濃度ヒストグラムの離散的フーリエ変換H*(u)に係数関数C(u)をかけて密度関数p(t)のフーリエ変換P(u)を計算することにより、P(u)算出のための積和演算の計算回数を256×9回に削減する。
【０００８】
第２の問題については、カーディナルスプラインやSINC関数（標本化関数)を用いて、離散的な濃度ヒストグラムh(k)から、連続的でなめらかな密度関数p(t)を推定する。
【０００９】
第３の問題については、推定された連続的な濃度ヒストグラムである密度関数と量子化した画像の濃度ヒストグラムとの類似性を尺度とする、カットオフ周波数の実用的な決定方法を導入する。すなわち、密度関数のフーリエ変換P(u)のパワースペクトルの総和Sと、密度関数のフーリエ変換P(u)にsinc関数を乗じて得られるスペクトル成分H’(u)のパワースペクトルのうち、カットオフ波長uc以下のみの総和S’(uc)を求め、S’(uc)≦βSとなるような最大のカットオフ周波数ucを求めることによって解決できる。
【００１０】
具体的に記載すると、本発明の画像の量子化方法は、画像を最適に量子化する方法において、画像の濃度ヒストグラムh(k)を作成する過程、濃度ヒストグラムh(k)にFFT（高速フーリエ変換）を適用して離散的フーリエ変換H*(u)を求める過程、濃度ヒストグラムの離散的フーリエ変換H*(u)に係数関数C(u)をかけて密度関数p(t)のフーリエ変換P(u)を推定する過程、密度関数のフーリエ変換P(u)からカットオフ周波数ucを求める過程、カットオフ周波数ucから量子化間隔Δtを求めて画像を量子化することを特徴とする（請求項１）。
【００１１】
また、本発明の画像の量子化方法は、係数関数C(u)にカーディナルスプライン基底関数のフーリエ変換を用いて、密度関数のフーリエ変換P(u)を推定することを特徴とする（請求項２）。
【００１２】
さらに、本発明の画像の量子化方法は、係数関数C(u)にRECT関数（矩形関数）を用いて密度関数のフーリエ変換P(u)を推定することを特徴とする（請求項３）。
【００１３】
また、本発明の画像の量子化方法は、密度関数のフーリエ変換P(u)のパワースペクトルの総和Sと、密度関数のフーリエ変換P(u)にsinc関数を乗じて得られるスペクトル成分H’(u)のパワースペクトルのうち、カットオフ波長uc 以下のみの総和S’(uc)を求め、S’(uc) ≦βSとなるような最大のカットオフ周波数ucを求めることを特徴とする（請求項４）。
【００１４】
さらに、本発明の画像圧縮方法は、請求項１記載の画像の量子化方法を適用した画像に対し、DCT（離散的コサイン変換）やウェーブレット変換などの標本化間引き方法を適用して、画像のデータ量を圧縮することを特徴とする（請求項５）。
【発明の効果】
【００１５】
画像を量子化する際に、濃度ヒストグラムh(k)にFFTを施して離散的フーリエ変換H*(u)を求め、これに係数関数C(u)を掛けることにより、密度関数p(t)のフーリエ変換P(u)を簡単に求めることができる。従来は解析的に求めていたが、それによる欠点が解消される。また、密度関数を推定する基底関数として、カーディナルスプライン基底関数やSINC関数を用いるので、密度関数が階段状ではなくなめらかになる。また、カットオフ周波数ucを、単なる目安で算出するのではなく、推定された密度関数p(t)の自己相関値に対する、量子化された画像の濃度ヒストグラムh’(k)の自己相関値の比率を判定基準として算出することができるので、最適な量子化が可能になる。また、最適に量子化された画像に従来の圧縮技術を適用することで、従来よりも高く画像を圧縮できる。
【発明を実施するための最良の形態】
【００１６】
離散的なデータである濃度ヒストグラムh(k)から連続的な密度関数p(t)を推定するために、以下の式を用いる。
【００１７】
【数１】
2005339110.tif 000003
【００１８】
ここにcm(t)は、m次のカーディナルスプライン基底関数である。c0(t)はRECT関数と一致するので、式(1)は非特許文献1のp4の式(18)の拡張となっている。密度関数p(t)は、m = 0のときに図4のような階段状関数、m=1のときに図5のような折れ線関数となり、mが2以上でなめらかな曲線となる。図6は、m = 3の場合である。また、mが大きくなるにつれ密度関数p(t)のなめらかさが増大し、∞の場合にcm(t)は図７のようにSINC関数（標本化関数)となる。
【００１９】
式(1)の両辺をフーリエ変換して、
【００２０】
【数２】
2005339110.tif 000004
【００２１】
P(u)は密度関数p(t)のフーリエ変換、H*(u)は濃度ヒストグラムh(k)の離散的フーリエ変換、Cm(u)はm次のカーディナルスプライン基底関数 cm(t) のフーリエ変換である。H*(u)は濃度ヒストグラムh(k)に高速フーリエ変換FFTを適用して得られる。
【００２２】
表1に、係数関数Cm(u)を示す。
【００２３】
【表１】
2005339110.tif 000005
【００２４】
また、図8にカーディナルスプライン基底関数のフーリエ変換Cm(u)を示す。
【００２５】
式(2)で m = 0 のときが、非特許文献1のp4の式(20)に相当する。従来法では、非特許文献1のp4の式(20)を解析的に解いていたが、本発明では、カーディナルスプライン基底関数 cm(t) のフーリエ変換Cm(u)を、濃度ヒストグラムh(k)の離散的フーリエ変換H*(u)に乗じればよい。よって、密度関数のフーリエ変換P(u)を求めるのに必要な計算回数は、離散的フーリエ変換H*(u)を求めるFFTの計算回数が256 log2256=256×8回で、式(2)が256回であるから、全部で256×9回である。従来は、最大256×256回であったから、大幅に計算回数が削減されたことになる。
【００２６】
よって、画像の量子化は、図９に示すように画像の濃度ヒストグラムh(k)を作成する過程、濃度ヒストグラムh(k)にFFTを適用して離散的フーリエ変換H*(u)を求める過程、濃度ヒストグラムの離散的フーリエ変換H*(u)に係数関数C(u)をかけて密度関数p(t)のフーリエ変換P(u)を推定する過程、密度関数のフーリエ変換P(u)からカットオフ周波数ucを求める過程、カットオフ周波数ucから得られる量子化間隔Δt（Δt = 1/2 uc ）を求める過程により行える（請求項1）。
【００２７】
また、カーディナルスプライン基底関数 cm(t) のフーリエ変換Cm(u)を、濃度ヒストグラムh(k)の離散的フーリエ変換H*(u)に乗じる場合、密度関数p(t)は、m=0で階段状、m=1で折れ線状となるが、m=2以上で曲線となり、なめらかな密度関数が推定できる（請求項2）。また、m=∞とすることにより、カーディナルスプライン基底関数 cm(t)はSINC関数となり、最もなめらかな曲線となる。このときのフーリエ変換Cm(u)はRECT関数である（請求項3)。なお、SINC関数は、SIN(πx)/(πx)により定義される関数である。
【００２８】
さて、推定された密度関数p(t)の自己相関値をS、最適に量子化された画像の濃度ヒストグラムh’(k)の自己相関値をS’とする。
【００２９】
【数３】
2005339110.tif 000006
【００３０】
【数４】
2005339110.tif 000007
【００３１】
最適に量子化されるということは、量子化間隔Δtが大きく、かつ２つの自己相関値の比S’/S が1に近くないといけない。すなわち、あるパラメータβを指定し、
【００３２】
【数５】
2005339110.tif 000008
【００３３】
を満足する、最大の量子化間隔Δt、すなわち最小のカットオフ周波数ucを求めればよい。ところで、式( 5)を計算するには、量子化間隔Δtを仮に定め、これによって画像を量子化し、これから濃度ヒストグラムh’(t)を求め、これから式(4)を計算しなければならない。これが、式(5)を満足する最大の量子化間隔Δtとなるようにするため、以上の手順を繰り返さないといけない。これらの計算量は膨大である。
【００３４】
ところで、量子化された画像の濃度ヒストグラムh’(t)は、図１０のように、密度関数p(t)が幅（量子化間隔Δt）で階段状になったものであるから、次式が成立する。
【００３５】
【数６】
2005339110.tif 000009
【００３６】
これをフーリエ変換して、
【００３７】
【数７】
2005339110.tif 000010
【００３８】
このパワースペクトルの総和は式(4)の自己相関値S’と等しく、
【００３９】
【数８】
2005339110.tif 000011
【００４０】
となる。ここに、Δu=1/256である。
【００４１】
同様に、式(3)の自己相関値Sも密度関数p(t)のフーリエ変換P(u)のパワースペクトルの総和に等しいから、
【００４２】
【数９】
2005339110.tif 000012
【００４３】
式(5)の自己相関値S’を計算するためには、式(8)のカットオフ周波数ucを計算する必要がある。これは、多項式の中にカットオフ周波数ucが含まれるため、カットオフ周波数ucを変えるたびに式(8)の計算を新たにやり直す必要がある。実際の計算においては、
【００４４】
【数１０】
2005339110.tif 000013
【００４５】
であるから、まず、式(10)と式(5)とからカットオフ周波数ucを粗く見つけた後（カットオフ周波数ucを変えるたびに式(10)の計算を新たにやり直す必要がない。前の結果を用いて、|P(iΔu)|2 の増分だけを加えればよいからである。）、今度は式(8)と式(5)とから最適のカットオフ周波数ucを求めれば、少ない計算量でカットオフ周波数ucを決定できる（請求項4）。
【００４６】
図11に、図1の画像をm = 3のカーディナルスプライン基底関数で推定し、β= 99.5%でカットオフ周波数ucを求めた例を示す。uc = 0.145であった。図12に量子化間隔Δt = 1/2uc = 3.45で量子化した画像を示す。階調数は、256/Δt = 74階調である。見た目には図1の256階調（Δt =1）の画像とほとんど変わらない。
【００４７】
なお、画像を最適に量子化できるため、画像のデータ量が小さくなる。よって、最適に量子化された画像に対し、DCTやウェーブレット変換などの標本化間引き方法を適用して、画像サイズを圧縮できる（請求項5）。
【産業上の利用可能性】
【００４８】
本発明は、画像伝送や画像保存における画像データ圧縮に使える。
【図面の簡単な説明】
【００４９】
【図１】２５６階調に量子化されたデジタル画像である。
【図２】２５６階調に量子化されたデジタル画像の濃度ヒストグラムである。
【図３】濃度ヒストグラムの連続的な密度関数のグラフである。
【図４】従来法で推定された密度関数のグラフである。
【図５】カーディナルスプラインで推定される密度関数のグラフである。
【図６】カーディナルスプラインで推定される密度関数のグラフである。
【図７】SINC関数で推定される密度関数のグラフである。
【図８】カーディナルスプライン基底関数のフーリエ変換のグラフである。
【図９】画像の量子化手順の説明図である。
【図１０】量子化された画像の濃度ヒストグラムのグラフである。
【図１１】カットオフ周波数の算出例のグラフである。
【図１２】最適に量子化された画像である。
【符号の説明】
【００５０】
h(k)   画像の濃度ヒストグラム
H*(u)  離散的フーリエ変換
C(u)   係数関数
p(t)    密度関数
P(u)   フーリエ変換
uc     カットオフ周波数
Δt    量子化間隔
【図２】
2005339110.tif 000014
【図３】
2005339110.tif 000015
【図４】
2005339110.tif 000016
【図５】
2005339110.tif 000017
【図６】
2005339110.tif 000018
【図７】
2005339110.tif 000019
【図８】
2005339110.tif 000020
【図９】
2005339110.tif 000021
【図１０】
2005339110.tif 000022
【図１１】
2005339110.tif 000023
【図１】
2005339110.tif 000024
【図１２】
2005339110.tif 000025
【手続補正書】
【提出日】平成16年6月2日(2004.6.2)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2005339110.tif 000026
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図１２
【補正方法】変更
【補正の内容】
【図１２】
2005339110.tif 000027