リフティング係数変換方法およびリフティング係数変換装置
【課題】チェス盤歪みなどを回避し得る整数型リフティング係数を比較的低いビット精度で高精度に算出すること。
【解決手段】リフティング係数変換装置９０は、画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換する。次数決定手段９１は、変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する。探索範囲決定手段９２で決定された探索範囲において、前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値を最小とするように、前記整数型リフティング係数の分子Ｎが探索される。
【解決手段】リフティング係数変換装置９０は、画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換する。次数決定手段９１は、変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する。探索範囲決定手段９２で決定された探索範囲において、前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値を最小とするように、前記整数型リフティング係数の分子Ｎが探索される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ウェーブレット（wavelet）変換、特に離散ウェーブレット変換を用いた画像の圧縮伸長技術に関するものである。
【背景技術】
【０００２】
画像データの高能率符号化方式の一つとして、離散ウェーブレット変換（ＤＷＴ；Discrete wavelet transform）を用いた画像符号化方法およびその復号化方法が採用されている。このＤＷＴに基づいた符号化方式は、従来の離散コサイン変換（Discrete Cosine Transform；ＤＣＴ）に基づく方式に代替するものとして、ＩＳＯ（国際標準化機構）が策定するＪＰＥＧ２０００（Joint Photographic Experts Group 2000）方式で採用されるものである。ＤＷＴは、ＤＣＴと比べて、（１）ＤＣＴの変換基底の両端が収束しないため復号化画像に出現するブロック状の雑音（ブロック歪み）を回避できること、（２）画像信号の高帯域成分の量子化に起因して復号化画像の輪郭部分などに出現するノイズ（モスキート雑音）を回避できること、（３）高圧縮率に対して高画質の復元画像を得られること、などの多くの優れた利点を有している。
【０００３】
図２０は、そのＪＰＥＧ２０００方式に基づいた画像符号化装置１００の概略構成を示す機能ブロック図である。以下、この図２０を参照しつつ画像圧縮変換（順変換）の手順について概説する。先ず、画像符号化装置１００に入力する画像信号は、ＤＣレベルシフト部１０２で、各信号値からダイナミックレンジの半分を減算するレベルシフト演算を施される。尚、このレベルシフト演算は、入力信号がＲＧＢ信号のような正の整数からなる場合に実行されるが、その値がＹＣｂＣｒ信号における色差信号（Ｃｂ，Ｃｒ）のような符号付き整数からなる場合には省略される。
【０００４】
次に、カラー変換部１０３は、ＤＣレベルシフト部１０２からの入力データの色空間を、例えば、ＲＧＢ色空間からＹＣｂＣｒ色空間などへ変換する色空間変換処理を実行する。その色空間変換処理を施された画像データはタイリング部１０４に出力され、各フレームが複数の矩形状のブロック領域に分割される。分割後の各ブロック領域は「タイル」と呼ばれている。ＤＷＴ部１０５は、タイリング部１０４から入力する画像データに対して各タイル単位でＤＷＴを実行し、そのウェーブレット変換係数を量子化部１０６に出力する。尚、本例では、ＤＷＴがタイル単位で実行されるブロックベースの変換を採用しているが、その代わりに、入力データを複数ライン分バッファリングして垂直方向のフィルタリングを行い、その結果得られたデータ列に対して水平方向のフィルタリングを行うというラインベースのＤＷＴを採用してもよい。一般に、変換効率と画質を向上させる観点からはブロックベースＤＷＴの方が好ましく、メモリ使用量低減の観点からはラインベースＤＷＴの方が好ましい。
【０００５】
量子化部１０６は、入力するウェーブレット変換係数に対してスカラー量子化を実行し、その結果得られる量子化係数をエントロピー符号化器１０１に出力する。尚、ロスレス（可逆）符号化を行う場合にはスカラー量子化は行われず、後述するポスト量子化が採用される。また、量子化部１０６は、ＲＯＩ部１０７によって指定された特定領域（ＲＯＩ；Region Of Interest）を選択し、当該ＲＯＩに対する量子化処理を他の領域のそれと相違させ、特定領域の画質を選択的に向上させる機能を有する。
【０００６】
次に、エントロピー符号化器１０１は、入力する量子化係数の符号化順序の決定や情報源符号化などを行い、その結果得られる符号化データを出力する機能ブロックを有する。図２０には、ＥＢＣＯＴ（Embedded Block Coding with Optimized Truncation）と称するブロックベースのビットプレーン符号化を行う機能ブロックが示されている。すなわち、エントロピー符号化器１０１に入力する量子化係数は、係数ビットモデリング部１０８において後段の算術符号化部１０９での処理に適したビットモデルに変換され、算術符号化部１０９では算術符号化を施され、その後、ビット切り捨て部１１０でポスト量子化（truncation）を施される。
【０００７】
そして、ビットストリーム生成部１１１は、エントロピー符号化器１０１から入力する符号化データと付加情報（ヘッダ情報、レイヤー構成、スケーラビリティ、量子化テーブルなど）とを多重化したビットストリームを生成し、圧縮画像として出力する。
【０００８】
次に、図２１を参照しつつ上記圧縮画像の復号化手順について概説する。図２１は、圧縮画像を復号化する画像復号化装置１２０の概略構成を示す機能ブロック図である。ビットストリーム抽出部１２１は、入力する圧縮画像から、上記付加情報と符号化データとを分離し、抽出した符号化データをエントロピー復号化器１２２に出力する。エントロピー復号化器１２２において、算術復号化部１２３は入力データに対して送信側の算術復号化を行い、また、係数ビットモデリング部１２４は、入力データのビットモデルを元に戻して得られる量子化係数を出力する。次いで、逆量子化部１２５は、入力する量子化係数に対して逆量子化を施し、その結果得られるウェーブレット変換係数を出力する。
【０００９】
逆量子化部１２５が出力したウェーブレット変換係数は、ＩＤＷＴ部１２７でタイル単位の逆離散ウェーブレット変換（ＩＤＷＴ；Inverse DWT）を施され、タイル合成部１２８で１フレームに合成され、カラー変換部１２９で元の色空間に変換される。ＤＣレベルシフト部１３０は、カラー変換部１２９から入力する各信号値にダイナミックレンジの半分を加算するレベルシフト演算を実行し、その結果得られる復号化画像を出力する。
【００１０】
上記ＤＷＴを実現する具体的手段としては、（１）画像信号を高域成分と低域成分とに２分割する２分割フィルタバンクを繰り返し使用して低域成分を再帰的に２分割する方法と、（２）ポリフェーズ表現に基づくリフティング構成（Lifting Scheme）を利用する方法と、が公知である。以下、２分割フィルタバンクを使用したＤＷＴの実現方法を説明し、リフティング構成を用いたＤＷＴとＩＤＷＴの実現方法については後述する。
【００１１】
図２２は、１次元ＤＷＴ（順変換）を実現する２分割フィルタバンク群の構成例を示す模式図である。２分割フィルタバンクは、低域成分を通過させるローパスフィルタＨ0（ｚ）と、高域成分を通過させるハイパスフィルタＨ1（ｚ）と、ダウンサンプラ１４０Ｌ，…，１４２Ｌ，１４０Ｈ，…，または１４２Ｈとで構成される。１次元ＤＷＴは、この２分割フィルタバンクを繰り返し用いることで構成される。尚、ダウンサンプラ１４０Ｌ〜１４２Ｌ，１４０Ｈ〜１４２Ｈは入力信号を一つおきに間引き、信号長を半分にして出力するものである。入力画像は、分解レベル（decomposition level）１において高域成分（Ｈ）と低域成分（Ｌ）とに分解され、次の分解レベル２において当該低域成分（Ｌ）が更に高域成分（ＬＨ）と低域成分（ＬＬ）とに分解され、次の分解レベル３において当該低域成分（ＬＬ）が更に高域成分（ＬＬＨ）と低域成分（ＬＬＬ）とに分解される。このように低域成分を再帰的に帯域分割することで、最終的に４つの帯域成分（ＬＬＬ，ＬＬＨ，ＬＨ，Ｈ）が得られる。
【００１２】
一方、図２３は、１次元ＩＤＷＴ（逆変換）を実現する２分割フィルタバンク群の構成例を示す模式図である。２分割フィルタバンクは、低域成分を通過させるローパスフィルタＧ0（ｚ）と、高域成分を通過させるハイパスフィルタＧ1（ｚ）と、アップサンプラ１５０Ｌ，…，１５４Ｌ，１５０Ｈ，…，または１５４Ｈと、加算器１５１，１５３または１５５とで構成される。１次元ＩＤＷＴは、この２分割フィルタバンクを繰り返し適用することで構成される。尚、アップサンプラ１５０Ｌ〜１５４Ｌ，１５０Ｈ〜１５４Ｈは、各信号値間にゼロ値を一つ挿入して信号長を倍に増すものである。この２分割フィルタバンク群には、上記の４つの帯域成分（ＬＬＬ，ＬＬＨ，ＬＨ，Ｈ）が入力している。
【００１３】
合成レベル１では、第１成分（ＬＬＬ）はアップサンプラ１５０ＬとローパスフィルタＧ0（ｚ）を経て加算器１５１に入力し、第２成分（ＬＬＨ）はアップサンプラ１５０ＨとハイパスフィルタＧ1（ｚ）を経て前記加算器１５１に入力する。加算器１５１は、各フィルタＧ0（ｚ），Ｇ1（ｚ）から入力する成分を合成して帯域成分（ＬＬ）を生成する。次の合成レベル２では、前記加算器１５１が出力した帯域成分（ＬＬ）はアップサンプラ１５２ＬとローパスフィルタＧ0（ｚ）を経て加算器１５３に入力し、帯域成分（ＬＨ）はアップサンプラ１５２ＨとハイパスフィルタＧ1（ｚ）を経て前記加算器１５３に入力する。加算器１５３は、各フィルタＧ0（ｚ），Ｇ1（ｚ）から入力する成分を合成して帯域成分（Ｌ）を生成する。そして、合成レベル３では、前記加算器１５３が出力した帯域成分（Ｌ）はアップサンプラ１５４ＬとローパスフィルタＧ0（ｚ）を経て加算器１５５に入力し、帯域成分（Ｈ）はアップサンプラ１５４ＨとハイパスフィルタＧ1（ｚ）を経て前記加算器１５５に入力する。最終的に、加算器１５５は、各フィルタＧ0（ｚ），Ｇ1（ｚ）から入力する成分を合成して復号化画像を生成し出力する。
【００１４】
２次元画像に２次元ＤＷＴを施す場合は、各分解レベルにおいて、図２２に示した２分割フィルタバンクを水平方向と垂直方向とに適用することで、入力画像は垂直方向、水平方向の順でそれぞれ帯域分割を施される。図２４は、２次元ＤＷＴを施された画像データ１６０を模式的に示す図である。同図中の帯域成分ＨＨ１は、入力画像の水平方向の高域成分（Ｈ）と垂直方向の高域成分（Ｈ）とを含むもの、帯域成分ＨＬ１は、その水平方向の高域成分（Ｈ）と垂直方向の低域成分（Ｌ）とを含むもの、帯域成分ＬＨ１は、水平方向の低域成分（Ｌ）と垂直方向の高域成分（Ｈ）とを含むものである。水平方向と垂直方向の双方向の低域成分を含む帯域成分ＬＬ１（図示せず）は、更に分解レベル２において、４つの帯域成分ＨＨ２，ＨＬ２，ＬＨ２，ＬＬ２に分解され、次の分解レベル３において、その帯域成分ＬＬ２は、４つの帯域成分ＨＨ３，ＨＬ３，ＬＨ３，ＬＬ３に分解される。図２４では、３次の分解レベルの例が示されているが、ＪＰＥＧ２０００方式では、一般に、３次〜８次程度以上の分解レベルが採用されている。
【００１５】
なお、リフティング構成については例えば非特許文献１に既述されている。
【００１６】
【非特許文献１】W.Sweldens, I. Daubechies, "Factoring Wavelet Transforms into Lifting Steps", J. Fourier Anal., Vol.4, No.3, pp.247-269, 1998
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上記ＤＷＴとしては、ウェーブレット変換係数が実数で構成される実数型ＤＷＴと、ウェーブレット変換係数が整数で構成される整数型ＤＷＴとに大別される。実数型ＤＷＴは、ウェーブレット変換係数を浮動小数点演算で算出し、整数型ＤＷＴと比べると復号化画像の画質が良いという利点をもつ。
【００１８】
一方、整数型ＤＷＴでは、実数型ＤＷＴと比べると、ロスレス圧縮（可逆圧縮）が可能である。また整数型ＤＷＴでは、ウェーブレット変換係数を固定小数点演算で算出できるため、ソフトウェアやハードウェアで効率的な処理が可能である。具体的には、入出力ピンの数が少なく、回路構成が小規模な低価格の固定小数点プロセッサを実現できるという利点がある。一般に、図２２，図２３に示すデジタル・フィルタＨ0（ｚ），Ｈ1（ｚ），Ｇ0（ｚ），Ｇ1（ｚ）には、整数型ＤＷＴの場合は５×３タップのフィルタ、実数型ＤＷＴの場合は９×７タップのフィルタが採用される。
【００１９】
実数型ＤＷＴを高効率で行う一手法として、実数型のフィルタ係数を整数型のフィルタ係数に丸め込んで固定小数点演算を行う方法がある。この方法では、浮動小数点で表現されたフィルタ係数は２進表現のフィルタ係数に変換される（丸め込まれる）。しかしながら、実数型のフィルタ係数を、単に、当該フィルタ係数に最も近い２進表現の値に丸め込むと、当該値の精度が低い場合は、復号化画像にチェス盤歪み（checkerboard distortion）と称する碁盤目状の歪みが現れるという問題がある。かかる問題を避けるには、非常に高いビット精度で丸め込み処理を実行しなければならない。
【００２０】
ＤＷＴを実現するフィルタバンクは後述するリフティング構成で表現することも可能である。フィルタ係数は、後述するリフティング係数α，β，γ，δ，κ，１／κで構成することができる。リフティング構成のＤＷＴを固定小数点演算で行う場合、リフティング係数値を実数型の値から整数型の値へ変換しなければならないため、前述と同様の問題が発生する。
【００２１】
以上の問題などに鑑みて本発明が目的とするところは、チェス盤歪みなどを回避し得る整数型リフティング係数を、比較的低いビット精度で高精度に算出することが可能なリフティング係数変換方法およびリフティング係数変換装置を提供する点にある。
【課題を解決するための手段】
【００２２】
本願請求項１にかかる発明は、画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換方法である。そして（ａ）変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する工程と、（ｂ）前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値が最小となるように、前記整数型リフティング係数の分子Ｎを探索する工程と、を備える。
【００２３】
本願請求項２にかかる発明は、請求項１記載のリフティング係数変換方法であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である。
【００２４】
本願請求項３にかかる発明は、画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換装置である。そして変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する次数決定手段と、前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値を最小とするように、前記整数型リフティング係数の分子Ｎを探索する手段と、を備える。
【００２５】
本願請求項４にかかる発明は、請求項３記載のリフティング係数変換装置であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である。
【発明の効果】
【００２６】
本発明の請求項１に係るリフティング係数変換方法および請求項１３に係るリフティング係数変換装置によれば、合成側フィルタを構成する各ポリフェーズフィルタのインパルス応答の総和の絶対値が一致するようにリフティング係数が算出されるため（工程（ｂ））、チェス盤歪みを回避し得るような、比較的低いビット精度で高精度の整数型フィルタ係数を算出することが可能となる。従って、請求項１の効果と同様に、ソフトウェアまたはハードウェアで、ＤＷＴとＩＤＷＴとを固定小数点演算で効率良く実行することが可能となる。特に、固定小数点演算を行うハードウェアを採用する場合は、全ての整数型リフティング係数の分母が共通の２の巾乗をもつことから、除算処理を効率の良いビットシフト演算で行うことができる。従って、入出力ピンの数が少ない小規模な回路構成を実現することが可能である。
【００２７】
本発明の請求項２に係るリフティング係数変換方法および請求項４に係るリフティング係数変換装置によれば、ＦＩＲ型のドビシスフィルタと同じ働きをするリフティング構成を形成する整数型リフティング係数を提供できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の種々の実施の形態について説明する。
【００２９】
第１の実施の形態．
上述した通り、ＤＷＴとＩＤＷＴを実現する具体的手段としては、図２２，図２３に示した２分割フィルタバンクを使用する方法と、リフティング構成を使用する方法とがある。本実施の形態に係るフィルタ係数変換方法とその装置は、２分割フィルタバンクを使用したＤＷＴおよびＩＤＷＴに適用される方法と装置である。
【００３０】
以下、図２２に示した分解側フィルタＨ0（ｚ），Ｈ1（ｚ）と、図２３に示した合成側フィルタＧ0（ｚ），Ｇ1（ｚ）とは、共に、有限長インパルス応答（ＦＩＲ）型フィルタで構成されており、９×７タップの実数型のフィルタ係数をもつものとする。
【００３１】
ＦＩＲ型フィルタの構成．
先ず、ＤＷＴを実現するＦＩＲ型フィルタについて説明する。図２２に示す分解側フィルタバンクにおいて、一方のダウンサンプラ１４０Ｌ〜１４２Ｌは、各ローパスフィルタＨ0（ｚ）から出力されるデータ列のうち、偶数番目のサンプルだけを保持し、奇数番目のサンプルを破棄するという間引き処理を実行し、他方のダウンサンプラ１４０Ｈ〜１４２Ｈは、各ハイパスフィルタＨ1（ｚ）から出力されるデータ列のうち、奇数番目のサンプルだけを保持し、偶数番目のサンプルを破棄するという間引き処理を実行する。このように、各フィルタＨ0（ｚ），Ｈ1（ｚ）から出力されたデータは、偶数と奇数という２つのフェーズ（ポリフェーズ）に分離されて間引き処理を施される。しかし、このようにフィルタＨ0（ｚ），Ｈ1（ｚ）が、偶数番目と奇数番目とに関係無く全ての入力データに関してフィルタ処理を行うのは効率的では無い。本実施の形態では、ローパスフィルタＨ0（ｚ）は偶数番目のデータ列についてのみフィルタ処理を実行し、ハイパスフィルタＨ1（ｚ）は奇数番目のデータ列についてのみフィルタ処理を実行し、その結果、各フィルタＨ0（ｚ）、Ｈ1（ｚ）は、各フェーズ毎にフィルタ処理と間引き処理とを同時並行に実行することとする。
【００３２】
図１は、分解側のＦＩＲ型ローパスフィルタＨ0（ｚ）の構成を示す模式図、図２は、分解側のＦＩＲ型ハイパスフィルタＨ1（ｚ）の構成を示す模式図である。入力画像１０は、入力データ列…，Ｘ（２ｎ−４），Ｘ（２ｎ−３），…，Ｘ（２ｎ），…，Ｘ（２ｎ＋４），…（ｎ：整数）で構成されている。図１に示す通り、ローパスフィルタＨ0（ｚ）は、９タップに対応したフィルタ係数ｈ0（−４），ｈ0（−３），…，ｈ0（３），ｈ0（４）を有し、入力データ列とフィルタ係数ｈ0（−４）〜ｈ0（４）とを畳み込み演算する乗算器１１1〜１１9および加算器１２を有している。このローパスフィルタＨ0（ｚ）は、次式（１）に従って、偶数番目のデータＸ（２ｎ）に関して選択的に畳み込み演算を実行し、データＹ（２ｎ）を出力する。
【００３３】
【数１】
【００３４】
また、図２に示す通り、ハイパスフィルタＨ1（ｚ）は、７タップに対応したフィルタ係数ｈ1（−４），ｈ1（−３），…，ｈ1（１），ｈ1（２）を有し、入力データ列とフィルタ係数ｈ1（−４）〜ｈ1（２）とを畳み込み演算する乗算器１３1〜１３7および加算器１４を有している。このハイパスフィルタＨ1（ｚ）は、次式（２）に従って、奇数番目のデータＸ（２ｎ＋１）に関して選択的に畳み込み演算を実行し、データＹ（２ｎ＋１）を出力する。
【００３５】
【数２】
【００３６】
次に、ＩＤＷＴを実現するＦＩＲ型フィルタについて説明する。図２３に示した合成側のローパスフィルタＧ0（ｚ）と、ハイパスフィルタＧ1（ｚ）とをそれぞれｚ変換を用いて表現すると、次式（３），（４）のようになる。
【００３７】
【数３】
【００３８】
上式（３），（４）中、フィルタ係数ｇ0（ｋ）（ｋ＝−３〜３）とｇ1（ｋ）（ｋ＝−３〜５）とはインパルス応答を示し、また、ｚ-kはｋ次の遅延を示している。
【００３９】
図２３に示した合成側のフィルタバンクは、以下に説明するポリフェーズ分解により変形されることができる。図３に、アップサンプラ３０とフィルタＧ（ｚ）との組み合わせを模式的に示す。フィルタＧ（ｚ）は、フィルタ係数ｈ（ｋ）（ｋ：整数）を有するＦＩＲ型フィルタである。アップサンプラ３０は、入力信号ｙ（ｎ）の各値の間にゼロ値を挿入するアップサンプリング処理を行い、フィルタＧ（ｚ）は、そのアップサンプラ３０からの出力データを補間した信号ｘ（ｎ）を出力する。フィルタＧ（ｚ）は、ｚ変換を用いた伝達関数で、Ｇ（ｚ）＝Ｒ0（ｚ2）ｚ-1＋Ｒ1（ｚ2）の形に変形され得る。このような表現は「タイプ２のポリフェーズ分解」と呼ばれている。２フェーズに分解された各フィルタＲ0（ｚ2），Ｒ1（ｚ2）は、「ポリフェーズフィルタ」と呼ばれる。
【００４０】
以上のフィルタのポリフェーズ表現に基づくと、ＦＩＲ型フィルタＧ（ｚ）は、図４に示すように、２つのポリフェーズフィルタＲ0（ｚ2），Ｒ1（ｚ2）と遅延素子３２と加算器３３とで表現される。すなわち、第１のポリフェーズフィルタＲ0（ｚ2）の出力信号は、遅延素子３２で１周期遅延した後に、加算器３３において第２のポリフェーズフィルタＲ1（ｚ2）の出力信号と加算される。更に、図４のフィルタ構成は、図５に示すフィルタ構成と等価である。従って、出力信号ｘ（ｎ）は、各フィルタＲ0（ｚ），Ｒ1（ｚ）の出力信号を交互に出力したものといえる。
【００４１】
ところで、図２３に示した合成側のローパスフィルタＧ0（ｚ）とハイパスフィルタＧ1（ｚ）とは、ｚ変換を用いた伝達関数で次式（３Ａ），（４Ａ）のように変形され得る。
【００４２】
【数４】
【００４３】
上式（３Ａ）中、Ｒ0（ｚ2），Ｒ1（ｚ2）は、合成側ローパスフィルタＧ0（ｚ）を構成するポリフェーズフィルタを示し、上式（４Ａ）中、Ｋ0（ｚ2），Ｋ1（ｚ2）は、合成側ハイパスフィルタＧ1（ｚ）を構成するポリフェーズフィルタを示している。
【００４４】
よって、前述のポリフェーズ表現に基づくと、図６に示す合成側のフィルタバンクは、図７に示すフィルタ構成に変形され得る。図６，図７において、符号３４，３５，３４Ａ，３４Ｂ，３５Ａ，３５Ｂはアップサンプラを示しており、符号３６，３８，４０は加算器、３７，３９は遅延素子を示している。
【００４５】
従って、ローパスフィルタ側の加算器３８の出力信号ｘ0（ｎ）は、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）の出力信号ｒ0，ｒ1を交互に出力したものとなり、ハイパスフィルタ側の加算器４０の出力信号ｘ1（ｎ）は、各ポリフェーズフィルタＫ0（ｚ），Ｋ1（ｚ）の出力信号ｋ0，ｋ1を交互に出力したものとなる。この結果、加算器３６の出力信号ｘ（ｎ）のうち、偶数番目の出力信号ｘ（２ｋ）は、各ポリフェーズフィルタＲ0（ｚ），Ｋ0（ｚ）の出力信号の和ｒ0＋ｋ0とし、奇数番目の出力信号ｘ（２ｋ＋１）は、各ポリフェーズフィルタＲ1（ｚ），Ｋ1（ｚ）の出力信号の和ｒ1＋ｋ1とすることができる。
【００４６】
以上のポリフェーズ表現に従って、合成側のフィルタバンクを実現するＦＩＲ型フィルタを構成できる。図８および図９は、合成側のＦＩＲ型フィルタの構成を示す模式図である。これらＦＩＲ型フィルタは、フィルタ処理とアップサンプリング処理とを同時並行に実行する。また、これらＦＩＲ型フィルタには、圧縮画像２０を構成するデータ列…，Ｙ（２ｎ−３），Ｙ（２ｎ−２），…，Ｙ（２ｎ＋４），Ｙ（２ｎ＋５），…が入力している。
【００４７】
図８に示す７タップのＦＩＲ型フィルタは、上記各ポリフェーズフィルタＲ0（ｚ2），Ｋ0（ｚ2）のフィルタ係数ｇ0（−２），ｇ0（０），ｇ0（２），ｇ1（−２），ｇ1（０），ｇ1（２），ｇ1（４）を使用し、これらフィルタ係数と入力データ列とを畳み込み演算する乗算器２１0，２１1，…，２１6および加減算器２２を有している。このＦＩＲ型フィルタは、次式（５）に従って畳み込み演算を実行して偶数番目のデータＸ（２ｎ）を合成する。
【００４８】
【数５】
【００４９】
また、図９に示す９タップのＦＩＲ型フィルタは、上記各ポリフェーズフィルタＲ1（ｚ2），Ｋ1（ｚ2）のフィルタ係数ｇ0（−３），ｇ0（−１），ｇ0（１），ｇ0（３），ｇ1（−３），ｇ1（−１），ｇ1（１），ｇ1（３），ｇ1（５）を使用し、これらフィルタ係数と入力データ列とを畳み込み演算する乗算器２３1，…，２３9および加算器２４を有している。このＦＩＲ型フィルタは、次式（６）に従って畳み込み演算を実行して奇数番目のデータＸ（２ｎ＋１）を合成する。
【００５０】
【数６】
【００５１】
チェス盤歪みの回避条件．
次に、上記チェス盤歪みの回避条件について説明する。図３において、フィルタへの入力信号ｙ（ｎ）として単位ステップ信号が印加されるとき、出力信号ｘ（ｎ）は、フィルタＧ（ｚ）のインパルス応答ｈ（ｋ）の総和であり、この総和は時間経過と共に一定値に収束することが望ましい。一方、図５において、入力信号ｙ（ｎ）に対応する出力信号ｘ（ｎ）は、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）の出力信号を交互に出力したものに等しい。入力信号ｙ（ｎ）として単位ステップ信号が印加されるとき、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）のインパルス応答の総和が交互に出力される。従って、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）のインパルス応答の総和が相違する場合は、ｎの値に応じて交互に異なる値が出力され、一定値に収束しないという現象が起きる。チェス盤歪みはこの種の現象を表していると考えられる。
【００５２】
従って、チェス盤歪みの回避条件は、少なくとも、各ポリフェーズフィルタのＲ0（ｚ），Ｒ1（ｚ）のインパルス応答の総和が一致することである。
【００５３】
フィルタ係数変換処理．
次に、本発明の第１の実施の形態に係るフィルタ係数変換方法とその装置について説明する。図１０は、本実施の形態に係るフィルタ係数変換装置１の概略構成を示す機能ブロック図である。このフィルタ係数変換装置１は、外部から入力する実数型フィルタ係数５を分数に丸め込み表現した値（＝Ｎ／２M；Ｎ，Ｍは１以上の整数）の分母（＝２M）の次数Ｍを決定する次数決定手段２と、その分子Ｎの整数値を選択して分解側の整数型のフィルタ係数（丸め込み値）６を出力する丸め込み値選択手段３と、合成側の整数型フィルタ係数を算出する係数算出手段３Ａと、入力する分解側および合成側の整数型フィルタ係数が所定条件を満たすか否かを判定する条件判定手段４と、を備えて構成されている。尚、実数型フィルタ係数５を丸め込み表現した値（＝Ｎ／２M）は１０進表現の値であり、実際の処理では、当該値はデジタル値で表現される。
【００５４】
以上の構成を有するフィルタ係数変換装置１を用いた分解側フィルタ係数の変換処理を、図１１のフローチャートを参照しつつ以下に詳説する。この変換処理では、分解側ローパスフィルタＨ0（ｚ）のフィルタ係数が整数型の値に変換される。変換元の実数型フィルタとしては、９×７タップのドビシス（Daubechies）フィルタを採用することができる。以下の表１，表２に、ドビシスフィルタのフィルタ係数＜ｈ0（ｎ）＞，＜ｈ1（ｎ）＞，＜ｇ0（ｎ）＞，＜ｇ1（ｎ）＞を示す。＜ｈ＞は、フィルタ係数ｈが実数型係数であることを表す記号である。
【００５５】
【表１】
【００５６】
【表２】
【００５７】
ステップＳＴ１では、このフィルタ係数変換装置１に、実数型フィルタ係数＜ｈ0（ｎ）＞が入力する。入力したフィルタ係数＜ｈ0（ｎ）＞は、次数決定手段２と丸め込み値選択手段３とにそれぞれ伝達する。続くステップＳＴ２では、次数決定手段２は、入力した実数型フィルタ係数＜ｈ0（ｎ）＞を丸め込み表現した値（＝Ｎ0（ｎ）／２M＝ｈ0（ｎ））の分母（＝２M）の次数Ｍを決定し、その値Ｍを丸め込み値選択手段３に出力する。
【００５８】
丸め込み値選択手段３は、ｎ番目の丸め込み値（＝Ｎ0（ｎ）／２M）の番号ｎがゼロ値の場合は、ステップＳＴ３，ＳＴ４の処理を実行し、番号ｎがゼロ値以外の場合は、ステップＳＴ５，ＳＴ６の処理を実行する。ステップＳＴ３では、整数型フィルタ係数の系列のうち中央位置の丸め込み値ｈ0（０）に着目し、この丸め込み値ｈ0（０）の分子Ｎ0（０）が偶数であり、且つ、丸め込み値ｈ0（０）と当該実数型フィルタ係数＜ｈ0（０）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ0（０）を選択する。続くステップＳＴ４では、選択した分子Ｎ0（０）を当該分母２Mで除算した丸め込み値ｈ0（０）が算出される。
【００５９】
一方、ステップＳＴ５では、整数型フィルタ係数の系列のうち中央位置の丸め込み値ｈ0（ｎ）（ｎ：ゼロ以外の整数）に着目し、この丸め込み値ｈ0（ｎ）と当該実数型フィルタ係数＜ｈ0（ｎ）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ0（ｎ）を選択する。整数値Ｎ0（ｎ）は必ずしも偶数である必要はない。続くステップＳＴ６では、選択した分子Ｎ0（ｎ）を当該分母２Mで除算した丸め込み値ｈ0（ｎ）が算出される。
【００６０】
以上のようにステップＳＴ４，ＳＴ６において、丸め込み値選択手段３が整数型フィルタ係数ｈ0（ｎ）を条件判定手段４に出力した後、条件判定手段４は、ステップＳＴ７以後の処理を実行する。ステップＳＴ７では、分解側ローパスフィルタＨ0（ｚ）のインパルス応答ｈ0（ｎ）の総和の絶対値を示すＤＣ成分ＧDCを算出し、当該ＤＣ成分ＧDCが所定値に一致するという規格化条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用する場合、ＤＣ成分ＧDCの値は「１」に一致しなければならない。ＤＣ成分ＧDCの算出式は、次式（７）の通りである。
【００６１】
【数７】
【００６２】
前記ステップＳＴ７で規格化条件が満たされていた場合は、ステップＳＴ８に処理が移行し、規格化条件が満たされていなかった場合は、ステップＳＴ９で規格化条件を満たすように規格化が行われた後に、ステップＳＴ８に処理が移行する。
【００６３】
次のステップＳＴ８では、係数算出手段３Ａは、分解側フィルタと合成側フィルタとが双直交性を満たすという双直交条件を用いて、合成側のハイパスフィルタＧ1（ｚ）の整数型フィルタ係数ｇ1（ｎ）を算出し、条件判定手段４に出力する。その双直交条件は次式（８）の通りである。
【００６４】
【数８】
【００６５】
ステップＳＴ１０では、条件判定手段４において、前記ステップＳＴ８で算出された合成側フィルタ係数ｇ1（ｎ）を用いて、合成側のハイパスフィルタＧ1（ｚ）を構成する各ポリフェーズフィルタＫ0（ｚ2），Ｋ1（ｚ2）のインパルス応答の総和の絶対値が一致するという束縛条件が成立するか否かが判定される。この束縛条件は、ハイパスフィルタＧ1（ｚ）の偶数番目のフィルタ係数の総和の絶対値と奇数番目のフィルタ係数の総和の絶対値とが一致することと同じである。ＪＰＥＧ２０００方式を採用した場合は、当該束縛条件に、更に、その総和の絶対値が１／２になる条件が付加される。ＪＰＥＧ２０００方式を採用した場合の束縛条件は次式（９）の通りである。
【００６６】
【数９】
【００６７】
前記ステップＳＴ１０で束縛条件が成立していなかった場合は、条件判定手段４は、当該整数型フィルタ係数ｈ0（ｎ），ｇ1（ｎ）の算出に失敗したとみなし、本フィルタ係数変換処理は終了する。他方、前記ステップＳＴ１０で束縛条件が成立していた場合は、次のステップＳＴ１１に処理が移行し、条件判定手段４は、整数型フィルタ係数ｈ0（ｎ），ｇ1（ｎ）を確定して出力する。
【００６８】
以上のフィルタ係数変換処理により、９×７タップのドビシスフィルタのフィルタ係数を変換した係数値ｈ0（ｎ），ｇ1（ｎ）を、それぞれ以下の表３，表４に示す。
【００６９】
【表３】
【００７０】
【表４】
【００７１】
次に、分解側ハイパスフィルタＨ1（ｚ）のフィルタ係数の変換処理を、図１２のフローチャートを参照しつつ以下に詳説する。先ず、ステップＳＴ２０では、上記フィルタ係数変換装置１に、実数型フィルタ係数＜ｈ1（ｎ）＞が入力する。入力したフィルタ係数＜ｈ1（ｎ）＞は、次数決定手段２と丸め込み値選択手段３とにそれぞれ伝達する。続くステップＳＴ２１では、次数決定手段２は、入力した実数型フィルタ係数＜ｈ1（ｎ）＞を丸め込み表現した値（＝Ｎ1（ｎ）／２M＝ｈ1（ｎ））の分母（＝２M）の次数Ｍを決定し、その値Ｍを丸め込み値選択手段３に出力する。
【００７２】
丸め込み値選択手段３は、ｎ番目の丸め込み値（＝Ｎ1（ｎ）／２M）の番号ｎがゼロ値の場合は、ステップＳＴ２２，ＳＴ２３の処理を実行し、番号ｎがゼロ値以外の場合は、ステップＳＴ２４，ＳＴ２５の処理を実行する。ステップＳＴ２２では、丸め込み値ｈ1（ｎ）の分子Ｎ1（−１）が偶数であり、且つ、丸め込み値ｈ1（−１）と当該実数型フィルタ係数＜ｈ1（−１）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ1（−１）を選択する。続くステップＳＴ２３では、選択した分子Ｎ1（−１）を当該分母２Mで除算した丸め込み値ｈ1（−１）が算出される。
【００７３】
一方、ステップＳＴ２４では、丸め込み値ｈ1（ｎ）（ｎ：−１以外の整数）と当該実数型フィルタ係数＜ｈ1（ｎ）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ1（ｎ）を選択する。その整数値Ｎ1（ｎ）は必ずしも偶数である必要はない。続くステップＳＴ２５では、選択した分子Ｎ1（ｎ）を当該分母２Mで除算した丸め込み値ｈ1（ｎ）が算出される。
【００７４】
以上のようにステップＳＴ２３，ＳＴ２５において、丸め込み値選択手段３が整数型フィルタ係数ｈ1（ｎ）を条件判定手段４に出力した後、条件判定手段４は、ステップＳＴ２６以後の処理を実行する。ステップＳＴ２６では、プラスマイナス１の値を交互にとる交番信号が印加された場合の分解側ハイパスフィルタＨ1（ｚ）の応答の総和の絶対値（以下、ナイキスト成分ＤNyquistと呼ぶ。）を算出し、当該ナイキスト成分ＤNyquistが所定値に一致するという規格化条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用する場合は、ナイキスト成分ＤNyquistの値は「２」に一致しなければならない。このナイキスト成分ＤNyquistの算出式は、次式（１０）の通りである。
【００７５】
【数１０】
【００７６】
前記ステップＳＴ２６で規格化条件が満たされていた場合は、ステップＳＴ２７に処理が移行し、規格化条件が満たされていなかった場合は、ステップＳＴ２８で規格化条件を満たすように規格化が行われた後に、ステップＳＴ２７に処理が移行する。
【００７７】
次のステップＳＴ２７では、分解側フィルタと合成側フィルタとが双直交性を満たすという双直交条件（上式（８））を用いて、合成側のローパスフィルタＧ0（ｚ）の整数型フィルタ係数ｇ0（ｎ）が算出される。
【００７８】
次のステップＳＴ２９では、前記ステップＳＴ２７で算出された合成側フィルタ係数ｇ0（ｎ）を用いて、合成側のローパスフィルタＧ0（ｚ）を構成する各ポリフェーズフィルタＲ0（ｚ2），Ｒ1（ｚ2）のインパルス応答の総和が一致するという束縛条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用した場合は、当該束縛条件に、更に、その総和が「１」になる条件が付加される。ＪＰＥＧ２０００方式を採用した場合の束縛条件は次式（１１）の通りである。
【００７９】
【数１１】
【００８０】
この束縛条件が成立するとき、各ポリフェーズフィルタのインパルス応答の総和が一致するため、上述した通り、復号化画像中のチェス盤歪みを回避することが可能となる。
【００８１】
前記ステップＳＴ２９で束縛条件が成立していなかった場合は、条件判定手段４は、当該整数型フィルタ係数ｈ1（ｎ），ｇ0（ｎ）の算出に失敗したとみなし、本フィルタ係数変換処理は終了する。他方、前記ステップＳＴ２９で束縛条件が成立していた場合は、次のステップＳＴ３０に処理が移行し、条件判定手段４は、整数型フィルタ係数ｈ1（ｎ），ｇ0（ｎ）を確定して出力する。
【００８２】
以上のフィルタ係数変換処理に従って、９×７タップのドビシスフィルタのフィルタ係数を変換し、その結果得られた整数型の係数値ｈ1（ｎ），ｇ0（ｎ）を以下の表５，表６に示す。
【００８３】
【表５】
【００８４】
【表６】
【００８５】
以上の通り、この第１の実施の形態では、上記ステップＳＴ２９（図１２）で、ローパスフィルタを構成する各ポリフェーズフィルタのインパルス応答の総和が一致するという条件が成立するか否かの判定処理を行っている。このため、ＩＤＷＴで低域成分を合成する際に当該低域成分にチェス盤歪みが混入しないように、比較的低いビット精度で、高精度の整数型フィルタ係数を算出できる。
【００８６】
また、上記ステップＳＴ１０（図１１）では、ハイパスフィルタを構成する各ポリフェーズフィルタのインパルス応答の総和の絶対値が一致するという条件が成立するか否かの判定処理が行われている。このため、分解側と合成側の各フィルタの構成要件を満たしつつ、チェス盤歪みを回避できるように高精度の整数型フィルタ係数を算出できる。
【００８７】
更に、上記ステップＳＴ３（図１１）とステップＳＴ２２（図１２）とでは、整数型フィルタ係数の系列のうち、中央の値に相当するｈ0（０），ｈ1（−１）の分子が共に偶数に選択される。このため、整数型フィルタ係数をより高い精度で算出できる。
【００８８】
従って、ソフトウェアまたはハードウェアにおいて、上記整数型フィルタ係数を用いて固定小数点演算でＤＷＴとＩＤＷＴとを効率良く実行することが可能となる。特にハードウェアを採用する場合は、全ての整数型フィルタ係数の分母が共通の２の巾乗をもつことから、除算処理をビットシフト演算で効率良く行うことができる。従って、入出力ピンの数が少ない小回路規模のハードウェア構成を実現することが可能である。
【００８９】
第２の実施の形態．
次に、本発明の第２の実施の形態について説明する。本実施の形態に係るリフティング係数変換方法とその装置は、リフティング構成を使用したＤＷＴおよびＩＤＷＴに適用される方法と装置である。最初に、リフティング構成を概説した後に、本実施の形態に係るリフティング係数変換処理を説明する。
【００９０】
リフティング構成．
図１３は、１ステージのみ（１次の分解レベルのみ）のＤＷＴとＩＤＷＴとを実現するフィルタ構成を示す図である。このような構成によるＤＷＴはポリフェーズＤＷＴと呼ばれている。図１３中、符号４１，４６は遅延素子、４２，４３はダウンサンプラ、４４，４５はアップサンプラを示している。また、図中のＰc（ｚ），Ｐ（ｚ）-1はポリフェーズ行列と称されている。
【００９１】
順変換においては、入力データＸ（ｋ）（ｋ：整数）は、分岐してダウンサンプラ４２と遅延素子４１とに伝達し、ダウンサンプラ４２は偶数番目のデータＸ（２ｎ＋４）（ｎ：整数）を出力し、一方、遅延素子４１の出力信号をダウンサンプリングするダウンサンプラ４３は、奇数番目のデータＸ（２ｎ＋３）を出力する。すなわち、入力データＸ（ｋ）は、偶数番目のデータＸ（２ｎ＋４）と奇数番目のデータＸ（２ｎ＋３）とに分離されて、ポリフェーズ行列Ｐc（ｚ）に入力することになる。このポリフェーズ行列Ｐc（ｚ）からは、低域成分（ＬＰ）Ｙ（２ｎ）と高域成分（ＨＰ）Ｙ（２ｎ＋１）とが出力される。
【００９２】
他方、逆変換においては、ポリフェーズ行列Ｐ（ｚ）-1は、入力データＹ（２ｎ），Ｙ（２ｎ＋１）に対して、ポリフェーズ行列Ｐ（ｚ）の逆変換を実行し、データＸ（２ｎ−２），Ｘ（２ｎ−３）を復元して出力する。偶数番目のデータＸ（２ｎ−２）はアップサンプラ４４と遅延素子４６とを経て加算器４７に伝達し、奇数番目のデータＸ（２ｎ−３）はアップサンプラ４５を経て加算器４７に伝達し、加算器４７は元のデータＸ（ｋ）を合成する。
【００９３】
順変換のポリフェーズ行列Ｐc（ｚ）と逆変換のポリフェーズ行列Ｐ（ｚ）-1は、リフティング構成と称する手法で構築できる。
【００９４】
順変換は図１４に示すリフティング構成で実現され、逆変換は図１５に示すリフティング構成で実現される。図１４中、符号５１，５３，５８，５９はｚ変換形式の伝達関数で表される２タップのＦＩＲ型フィルタを示しており、符号５４，５６，６０は遅延素子、６２は入力信号に係数１／κを乗算して出力する乗算器、６３は入力信号に係数κを乗算して出力する乗算器、５２，５５，５７は加算器、を示している。
【００９５】
また、図１５中、符号７２，７５，７８，８１はｚ変換形式の伝達関数で表される２タップのＦＩＲ型フィルタを示しており、符号７０は入力信号に係数κを乗算して出力する乗算器、７１は入力信号に係数１／κを乗算して出力する乗算器、７４，７７，８０は遅延素子、７３，７６，７９，８２は減算器、を示している。
【００９６】
図１４と図１５に現れる係数α，β，γ，δ，κは、リフティング係数と呼ばれており、９×７タップのドビシスフィルタのリフティング構成では実数型の値をもつ。
【００９７】
また、図１４に示す分解側リフティング構成により、入力データＸ（ｋ）は、奇数番目のデータＸ（２ｎ＋３）と偶数番目のデータＸ（２ｎ＋４）とに分解される。また、中間データＹ’（２ｎ＋３），Ｙ’’（２ｎ＋２），Ｙ’’’（２ｎ＋１），Ｙ’’’’（２ｎ）が次々と生成されて、最終的にデータＹ（２ｎ），Ｙ（２ｎ＋１）が出力される。この分解側リフティング構成は、図１６に示すように、データを示す黒点と、各黒点間を結ぶ線分とからなるツリー図で表現することができる。各黒点近傍には、当該黒点を示すデータが表示されている。例えば、左端の各黒点に対応して、それぞれ、入力データ列Ｘ（２ｎ），Ｘ（２ｎ＋１），…，Ｘ（２ｎ＋４）が表示されている。また、各黒点間を結ぶ線分の近傍には係数が表示されている。例えば、データＸ（２ｎ）を示す黒点とデータＹ’（２ｎ＋１）を示す黒点との間の線分近傍には係数αが表示されている。
【００９８】
図１６に示す分解側リフティング構成は、次の規則（Ａ），（Ｂ），（Ｃ）に基づいて解釈されるものである。（Ａ）黒点を示すデータは、左方から右方へ延びる線分に沿って伝達する。（Ｂ）黒点間を結ぶ線分は、当該線分を伝達するデータに当該係数を乗算する。（Ｃ）黒点は、各線分に沿って左方から入力するデータを加算して右方へ延びる線分に出力する。従って、その分解側リフティング構成は次式（１２）と等価である。
【００９９】
【数１２】
【０１００】
また、図１５に示す合成側リフティング構成により、入力データ列Ｙ（２ｎ＋４），Ｙ（２ｎ＋５）に対して、中間データＸ’’’（２ｎ＋４），Ｘ’’（２ｎ＋５），…が次々と生成されて、最終的に合成データＸ（ｋ）が出力される。この合成側リフティング構成も、図１７に示す黒点と線分とからなるツリー図で表現することが可能であり、次式（１３）と等価である。
【０１０１】
【数１３】
【０１０２】
９×７タップのドビシスフィルタのリフティング構成を採用した場合のリフティング係数α，β，γ，δ，κの正確な値を次式（１４）に示す。
【０１０３】
【数１４】
【０１０４】
また、以下の表７に、ドビシスフィルタの分解側フィルタ係数ｈ0（ｎ），ｈ1（ｎ）をリフティング係数α，β，γ，δ，κ，１／κで構成したものを示し、以下の表８に、ドビシスフィルタの合成側フィルタ係数ｇ0（ｎ），ｇ1（ｎ）をリフティング係数α，β，γ，δ，κ，１／κで構成したものを示す。
【０１０５】
【表７】
【０１０６】
【表８】
【０１０７】
リフティング係数変換処理．
次に、本発明の第２の実施の形態に係るリフティング係数変換方法とその装置について説明する。図１８は、本実施の形態に係るリフティング係数変換装置９０の概略構成を示す機能ブロック図である。このリフティング係数変換装置９０は、外部から入力する実数型リフティング係数を分数に丸め込み表現した値（＝Ｎ／２M；Ｎ，Ｍは１以上の整数）の分母（＝２M）の次数Ｍを決定する次数決定手段９１と、後述する評価式に基づいてその分子Ｎの整数値を探索する係数評価手段９３と、この係数評価手段９３に対して探索範囲を指示する探索範囲決定手段９２と、係数評価手段９３から出力された整数型リフティング係数を抽出する係数抽出手段９４と、を備えて構成されている。
【０１０８】
以上の構成を有するリフティング係数変換装置９０を用いたリフティング係数の変換処理を、図１９のフローチャートを参照しつつ以下に詳説する。最初のステップＳＴ１では、変換元の実数型リフティング係数がリフティング係数変換装置９０に入力する。次数決定手段９１は、実数型リフティング係数α，β，γ，δ，κ，１／κの各々について丸め込み表現した値（＝Ｎ／２M）の分母（＝２M）の次数Ｍを決定し、その値Ｍを係数評価手段９３に出力する。併行して、探索範囲決定手段９２は、各実数型リフティング係数の探索範囲を決定して係数評価手段９３に出力する。
【０１０９】
次のステップＳＴ４１Ａ以後において、係数評価手段９３は、指定された探索範囲内で、後述する評価式の値（以下、評価値と呼ぶ。）と、この値に対応する整数型リフティング係数とを算出する。すなわち、ステップＳＴ４１Ａ〜ＳＴ４６Ａと、ステップＳＴ４１Ｂ〜４６Ｂとの間でループを形成し、指定された探索範囲で整数型リフティング係数α，β，γ，δ，κ，１／κの分子を小刻みに順次変化させる。そして、ステップＳＴ４７では、そのループにおいて変化させた整数型リフティング係数の全ての組み合わせについて、以下に説明する評価値が算出される。
【０１１０】
上記の表８，表９によれば、上式（９）は次式（１５）のように表される。
【０１１１】
【数１５】
【０１１２】
また、上式（１１）は次式（１６）のように表される。
【０１１３】
【数１６】
【０１１４】
前記評価式は、上式（１５）の中辺の値と右辺の値との差分絶対値の和と，（１６）の中辺の値と右辺の値との差分絶対値の和とを加算したものであり、次式（１７）で表現される。
【０１１５】
【数１７】
【０１１６】
次のステップＳＴ４８では、係数抽出手段９４は、前記係数評価手段９３から入力する評価値の組み合わせのうち、最小の評価値をとる整数型リフティング係数の組み合わせ（α，β，γ，δ，κ，１／κ）を確定して出力する。ここで、上記したＤＣ成分ＧDCおよびナイキスト成分ＤNyquistがそれぞれ所定値をとるという条件が成立するか否かを判定してもよい。
【０１１７】
以上のリフティング係数変換処理の計算結果の例を、以下の表９，表１０，表１１に示す。表９および表１１の中の「範囲」は、上記探索範囲の変動幅の上下限値を示している。すなわち、上記探索範囲は、実数型リフティング係数から下限値を引いた値から、同実数型リフティング係数に上限値を足した値までの範囲である。例えば、表９に示す次数Ｍ＝５に対応する変動幅の上下限値は「±１」であるから、係数αの探索範囲は、＜α＞−１から＜α＞＋１、となる（但し、＜α＞は実数型リフティング係数）。本例では、各分母の次数Ｍの値に応じて、全ての整数型リフティング係数に共通の探索範囲が設定されている。表９と表１０は分離して表示されているが、各次数Ｍに対応する探索範囲は同じである。また、表１１中の「評価式」の値は上記評価値を意味している。
【０１１８】
【表９】
【０１１９】
【表１０】
【０１２０】
【表１１】
【０１２１】
以上の通り、この第２の実施の形態では、評価値がゼロ値に近くなるように整数型フィルタ係数が選択されることで、比較的低いビット精度で、チェス盤歪みを低減し得る高精度の整数型フィルタ係数を算出することが可能となる。
【図面の簡単な説明】
【０１２２】
【図１】本発明の第１の実施の形態に係る分解側のＦＩＲ型ローパスフィルタの構成を示す模式図である。
【図２】本発明の第１の実施の形態に係る分解側のＦＩＲ型ハイパスフィルタの構成を示す模式図である。
【図３】アップサンプラとフィルタとの組み合わせを示す模式図である。
【図４】図３に示すフィルタ構成のポリフェーズ表現を示す模式図である。
【図５】図３に示すフィルタ構成の他のポリフェーズ表現を示す模式図である。
【図６】合成側のフィルタバンクを示す模式図である。
【図７】図６に示すフィルタバンクのポリフェーズ表現を示す模式図である。
【図８】合成側のＦＩＲ型フィルタの構成を示す模式図である。
【図９】合成側のＦＩＲ型フィルタの構成を示す模式図である。
【図１０】第１の実施の形態に係るフィルタ係数変換装置の概略構成を示す機能ブロック図である。
【図１１】第１の実施の形態に係るフィルタ係数変換方法を示すフローチャートである。
【図１２】第１の実施の形態に係るフィルタ係数変換方法を示すフローチャートである。
【図１３】１ステージのＤＷＴとＩＤＷＴとを実現するフィルタ構成を示す図である。
【図１４】分解側フィルタバンクのリフティング構成を示す模式図である。
【図１５】合成側フィルタバンクのリフティング構成を示す模式図である。
【図１６】分解側リフティング構成を示すツリー図である。
【図１７】合成側リフティング構成を示すツリー図である。
【図１８】本発明の第２の実施の形態に係るリフティング係数変換装置の概略構成を示す機能ブロック図である。
【図１９】第２の実施の形態に係るリフティング係数変換方法を示すフローチャートである。
【図２０】ＪＰＥＧ２０００方式に基づいた画像符号化装置の概略構成を示す機能ブロック図である。
【図２１】ＪＰＥＧ２０００方式に基づいた画像復号化装置の概略構成を示す機能ブロック図である。
【図２２】１次元ＤＷＴを実現する２分割フィルタバンク群の構成例を示す模式図である。
【図２３】１次元ＩＤＷＴを実現する２分割フィルタバンク群の構成例を示す模式図である。
【図２４】２次元ＤＷＴを施された画像データを模式的に示す図である。
【符号の説明】
【０１２３】
１ フィルタ係数変換装置
２ 次数決定手段
３ 丸め込み値選択手段
４ 条件判定手段
９０ リフティング係数変換装置
９１ 次数決定手段
９２ 探索範囲決定手段
９３ 係数評価手段
９４ 係数抽出手段
【技術分野】
【０００１】
本発明は、ウェーブレット（wavelet）変換、特に離散ウェーブレット変換を用いた画像の圧縮伸長技術に関するものである。
【背景技術】
【０００２】
画像データの高能率符号化方式の一つとして、離散ウェーブレット変換（ＤＷＴ；Discrete wavelet transform）を用いた画像符号化方法およびその復号化方法が採用されている。このＤＷＴに基づいた符号化方式は、従来の離散コサイン変換（Discrete Cosine Transform；ＤＣＴ）に基づく方式に代替するものとして、ＩＳＯ（国際標準化機構）が策定するＪＰＥＧ２０００（Joint Photographic Experts Group 2000）方式で採用されるものである。ＤＷＴは、ＤＣＴと比べて、（１）ＤＣＴの変換基底の両端が収束しないため復号化画像に出現するブロック状の雑音（ブロック歪み）を回避できること、（２）画像信号の高帯域成分の量子化に起因して復号化画像の輪郭部分などに出現するノイズ（モスキート雑音）を回避できること、（３）高圧縮率に対して高画質の復元画像を得られること、などの多くの優れた利点を有している。
【０００３】
図２０は、そのＪＰＥＧ２０００方式に基づいた画像符号化装置１００の概略構成を示す機能ブロック図である。以下、この図２０を参照しつつ画像圧縮変換（順変換）の手順について概説する。先ず、画像符号化装置１００に入力する画像信号は、ＤＣレベルシフト部１０２で、各信号値からダイナミックレンジの半分を減算するレベルシフト演算を施される。尚、このレベルシフト演算は、入力信号がＲＧＢ信号のような正の整数からなる場合に実行されるが、その値がＹＣｂＣｒ信号における色差信号（Ｃｂ，Ｃｒ）のような符号付き整数からなる場合には省略される。
【０００４】
次に、カラー変換部１０３は、ＤＣレベルシフト部１０２からの入力データの色空間を、例えば、ＲＧＢ色空間からＹＣｂＣｒ色空間などへ変換する色空間変換処理を実行する。その色空間変換処理を施された画像データはタイリング部１０４に出力され、各フレームが複数の矩形状のブロック領域に分割される。分割後の各ブロック領域は「タイル」と呼ばれている。ＤＷＴ部１０５は、タイリング部１０４から入力する画像データに対して各タイル単位でＤＷＴを実行し、そのウェーブレット変換係数を量子化部１０６に出力する。尚、本例では、ＤＷＴがタイル単位で実行されるブロックベースの変換を採用しているが、その代わりに、入力データを複数ライン分バッファリングして垂直方向のフィルタリングを行い、その結果得られたデータ列に対して水平方向のフィルタリングを行うというラインベースのＤＷＴを採用してもよい。一般に、変換効率と画質を向上させる観点からはブロックベースＤＷＴの方が好ましく、メモリ使用量低減の観点からはラインベースＤＷＴの方が好ましい。
【０００５】
量子化部１０６は、入力するウェーブレット変換係数に対してスカラー量子化を実行し、その結果得られる量子化係数をエントロピー符号化器１０１に出力する。尚、ロスレス（可逆）符号化を行う場合にはスカラー量子化は行われず、後述するポスト量子化が採用される。また、量子化部１０６は、ＲＯＩ部１０７によって指定された特定領域（ＲＯＩ；Region Of Interest）を選択し、当該ＲＯＩに対する量子化処理を他の領域のそれと相違させ、特定領域の画質を選択的に向上させる機能を有する。
【０００６】
次に、エントロピー符号化器１０１は、入力する量子化係数の符号化順序の決定や情報源符号化などを行い、その結果得られる符号化データを出力する機能ブロックを有する。図２０には、ＥＢＣＯＴ（Embedded Block Coding with Optimized Truncation）と称するブロックベースのビットプレーン符号化を行う機能ブロックが示されている。すなわち、エントロピー符号化器１０１に入力する量子化係数は、係数ビットモデリング部１０８において後段の算術符号化部１０９での処理に適したビットモデルに変換され、算術符号化部１０９では算術符号化を施され、その後、ビット切り捨て部１１０でポスト量子化（truncation）を施される。
【０００７】
そして、ビットストリーム生成部１１１は、エントロピー符号化器１０１から入力する符号化データと付加情報（ヘッダ情報、レイヤー構成、スケーラビリティ、量子化テーブルなど）とを多重化したビットストリームを生成し、圧縮画像として出力する。
【０００８】
次に、図２１を参照しつつ上記圧縮画像の復号化手順について概説する。図２１は、圧縮画像を復号化する画像復号化装置１２０の概略構成を示す機能ブロック図である。ビットストリーム抽出部１２１は、入力する圧縮画像から、上記付加情報と符号化データとを分離し、抽出した符号化データをエントロピー復号化器１２２に出力する。エントロピー復号化器１２２において、算術復号化部１２３は入力データに対して送信側の算術復号化を行い、また、係数ビットモデリング部１２４は、入力データのビットモデルを元に戻して得られる量子化係数を出力する。次いで、逆量子化部１２５は、入力する量子化係数に対して逆量子化を施し、その結果得られるウェーブレット変換係数を出力する。
【０００９】
逆量子化部１２５が出力したウェーブレット変換係数は、ＩＤＷＴ部１２７でタイル単位の逆離散ウェーブレット変換（ＩＤＷＴ；Inverse DWT）を施され、タイル合成部１２８で１フレームに合成され、カラー変換部１２９で元の色空間に変換される。ＤＣレベルシフト部１３０は、カラー変換部１２９から入力する各信号値にダイナミックレンジの半分を加算するレベルシフト演算を実行し、その結果得られる復号化画像を出力する。
【００１０】
上記ＤＷＴを実現する具体的手段としては、（１）画像信号を高域成分と低域成分とに２分割する２分割フィルタバンクを繰り返し使用して低域成分を再帰的に２分割する方法と、（２）ポリフェーズ表現に基づくリフティング構成（Lifting Scheme）を利用する方法と、が公知である。以下、２分割フィルタバンクを使用したＤＷＴの実現方法を説明し、リフティング構成を用いたＤＷＴとＩＤＷＴの実現方法については後述する。
【００１１】
図２２は、１次元ＤＷＴ（順変換）を実現する２分割フィルタバンク群の構成例を示す模式図である。２分割フィルタバンクは、低域成分を通過させるローパスフィルタＨ0（ｚ）と、高域成分を通過させるハイパスフィルタＨ1（ｚ）と、ダウンサンプラ１４０Ｌ，…，１４２Ｌ，１４０Ｈ，…，または１４２Ｈとで構成される。１次元ＤＷＴは、この２分割フィルタバンクを繰り返し用いることで構成される。尚、ダウンサンプラ１４０Ｌ〜１４２Ｌ，１４０Ｈ〜１４２Ｈは入力信号を一つおきに間引き、信号長を半分にして出力するものである。入力画像は、分解レベル（decomposition level）１において高域成分（Ｈ）と低域成分（Ｌ）とに分解され、次の分解レベル２において当該低域成分（Ｌ）が更に高域成分（ＬＨ）と低域成分（ＬＬ）とに分解され、次の分解レベル３において当該低域成分（ＬＬ）が更に高域成分（ＬＬＨ）と低域成分（ＬＬＬ）とに分解される。このように低域成分を再帰的に帯域分割することで、最終的に４つの帯域成分（ＬＬＬ，ＬＬＨ，ＬＨ，Ｈ）が得られる。
【００１２】
一方、図２３は、１次元ＩＤＷＴ（逆変換）を実現する２分割フィルタバンク群の構成例を示す模式図である。２分割フィルタバンクは、低域成分を通過させるローパスフィルタＧ0（ｚ）と、高域成分を通過させるハイパスフィルタＧ1（ｚ）と、アップサンプラ１５０Ｌ，…，１５４Ｌ，１５０Ｈ，…，または１５４Ｈと、加算器１５１，１５３または１５５とで構成される。１次元ＩＤＷＴは、この２分割フィルタバンクを繰り返し適用することで構成される。尚、アップサンプラ１５０Ｌ〜１５４Ｌ，１５０Ｈ〜１５４Ｈは、各信号値間にゼロ値を一つ挿入して信号長を倍に増すものである。この２分割フィルタバンク群には、上記の４つの帯域成分（ＬＬＬ，ＬＬＨ，ＬＨ，Ｈ）が入力している。
【００１３】
合成レベル１では、第１成分（ＬＬＬ）はアップサンプラ１５０ＬとローパスフィルタＧ0（ｚ）を経て加算器１５１に入力し、第２成分（ＬＬＨ）はアップサンプラ１５０ＨとハイパスフィルタＧ1（ｚ）を経て前記加算器１５１に入力する。加算器１５１は、各フィルタＧ0（ｚ），Ｇ1（ｚ）から入力する成分を合成して帯域成分（ＬＬ）を生成する。次の合成レベル２では、前記加算器１５１が出力した帯域成分（ＬＬ）はアップサンプラ１５２ＬとローパスフィルタＧ0（ｚ）を経て加算器１５３に入力し、帯域成分（ＬＨ）はアップサンプラ１５２ＨとハイパスフィルタＧ1（ｚ）を経て前記加算器１５３に入力する。加算器１５３は、各フィルタＧ0（ｚ），Ｇ1（ｚ）から入力する成分を合成して帯域成分（Ｌ）を生成する。そして、合成レベル３では、前記加算器１５３が出力した帯域成分（Ｌ）はアップサンプラ１５４ＬとローパスフィルタＧ0（ｚ）を経て加算器１５５に入力し、帯域成分（Ｈ）はアップサンプラ１５４ＨとハイパスフィルタＧ1（ｚ）を経て前記加算器１５５に入力する。最終的に、加算器１５５は、各フィルタＧ0（ｚ），Ｇ1（ｚ）から入力する成分を合成して復号化画像を生成し出力する。
【００１４】
２次元画像に２次元ＤＷＴを施す場合は、各分解レベルにおいて、図２２に示した２分割フィルタバンクを水平方向と垂直方向とに適用することで、入力画像は垂直方向、水平方向の順でそれぞれ帯域分割を施される。図２４は、２次元ＤＷＴを施された画像データ１６０を模式的に示す図である。同図中の帯域成分ＨＨ１は、入力画像の水平方向の高域成分（Ｈ）と垂直方向の高域成分（Ｈ）とを含むもの、帯域成分ＨＬ１は、その水平方向の高域成分（Ｈ）と垂直方向の低域成分（Ｌ）とを含むもの、帯域成分ＬＨ１は、水平方向の低域成分（Ｌ）と垂直方向の高域成分（Ｈ）とを含むものである。水平方向と垂直方向の双方向の低域成分を含む帯域成分ＬＬ１（図示せず）は、更に分解レベル２において、４つの帯域成分ＨＨ２，ＨＬ２，ＬＨ２，ＬＬ２に分解され、次の分解レベル３において、その帯域成分ＬＬ２は、４つの帯域成分ＨＨ３，ＨＬ３，ＬＨ３，ＬＬ３に分解される。図２４では、３次の分解レベルの例が示されているが、ＪＰＥＧ２０００方式では、一般に、３次〜８次程度以上の分解レベルが採用されている。
【００１５】
なお、リフティング構成については例えば非特許文献１に既述されている。
【００１６】
【非特許文献１】W.Sweldens, I. Daubechies, "Factoring Wavelet Transforms into Lifting Steps", J. Fourier Anal., Vol.4, No.3, pp.247-269, 1998
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上記ＤＷＴとしては、ウェーブレット変換係数が実数で構成される実数型ＤＷＴと、ウェーブレット変換係数が整数で構成される整数型ＤＷＴとに大別される。実数型ＤＷＴは、ウェーブレット変換係数を浮動小数点演算で算出し、整数型ＤＷＴと比べると復号化画像の画質が良いという利点をもつ。
【００１８】
一方、整数型ＤＷＴでは、実数型ＤＷＴと比べると、ロスレス圧縮（可逆圧縮）が可能である。また整数型ＤＷＴでは、ウェーブレット変換係数を固定小数点演算で算出できるため、ソフトウェアやハードウェアで効率的な処理が可能である。具体的には、入出力ピンの数が少なく、回路構成が小規模な低価格の固定小数点プロセッサを実現できるという利点がある。一般に、図２２，図２３に示すデジタル・フィルタＨ0（ｚ），Ｈ1（ｚ），Ｇ0（ｚ），Ｇ1（ｚ）には、整数型ＤＷＴの場合は５×３タップのフィルタ、実数型ＤＷＴの場合は９×７タップのフィルタが採用される。
【００１９】
実数型ＤＷＴを高効率で行う一手法として、実数型のフィルタ係数を整数型のフィルタ係数に丸め込んで固定小数点演算を行う方法がある。この方法では、浮動小数点で表現されたフィルタ係数は２進表現のフィルタ係数に変換される（丸め込まれる）。しかしながら、実数型のフィルタ係数を、単に、当該フィルタ係数に最も近い２進表現の値に丸め込むと、当該値の精度が低い場合は、復号化画像にチェス盤歪み（checkerboard distortion）と称する碁盤目状の歪みが現れるという問題がある。かかる問題を避けるには、非常に高いビット精度で丸め込み処理を実行しなければならない。
【００２０】
ＤＷＴを実現するフィルタバンクは後述するリフティング構成で表現することも可能である。フィルタ係数は、後述するリフティング係数α，β，γ，δ，κ，１／κで構成することができる。リフティング構成のＤＷＴを固定小数点演算で行う場合、リフティング係数値を実数型の値から整数型の値へ変換しなければならないため、前述と同様の問題が発生する。
【００２１】
以上の問題などに鑑みて本発明が目的とするところは、チェス盤歪みなどを回避し得る整数型リフティング係数を、比較的低いビット精度で高精度に算出することが可能なリフティング係数変換方法およびリフティング係数変換装置を提供する点にある。
【課題を解決するための手段】
【００２２】
本願請求項１にかかる発明は、画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換方法である。そして（ａ）変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する工程と、（ｂ）前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値が最小となるように、前記整数型リフティング係数の分子Ｎを探索する工程と、を備える。
【００２３】
本願請求項２にかかる発明は、請求項１記載のリフティング係数変換方法であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である。
【００２４】
本願請求項３にかかる発明は、画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換装置である。そして変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する次数決定手段と、前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値を最小とするように、前記整数型リフティング係数の分子Ｎを探索する手段と、を備える。
【００２５】
本願請求項４にかかる発明は、請求項３記載のリフティング係数変換装置であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である。
【発明の効果】
【００２６】
本発明の請求項１に係るリフティング係数変換方法および請求項１３に係るリフティング係数変換装置によれば、合成側フィルタを構成する各ポリフェーズフィルタのインパルス応答の総和の絶対値が一致するようにリフティング係数が算出されるため（工程（ｂ））、チェス盤歪みを回避し得るような、比較的低いビット精度で高精度の整数型フィルタ係数を算出することが可能となる。従って、請求項１の効果と同様に、ソフトウェアまたはハードウェアで、ＤＷＴとＩＤＷＴとを固定小数点演算で効率良く実行することが可能となる。特に、固定小数点演算を行うハードウェアを採用する場合は、全ての整数型リフティング係数の分母が共通の２の巾乗をもつことから、除算処理を効率の良いビットシフト演算で行うことができる。従って、入出力ピンの数が少ない小規模な回路構成を実現することが可能である。
【００２７】
本発明の請求項２に係るリフティング係数変換方法および請求項４に係るリフティング係数変換装置によれば、ＦＩＲ型のドビシスフィルタと同じ働きをするリフティング構成を形成する整数型リフティング係数を提供できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の種々の実施の形態について説明する。
【００２９】
第１の実施の形態．
上述した通り、ＤＷＴとＩＤＷＴを実現する具体的手段としては、図２２，図２３に示した２分割フィルタバンクを使用する方法と、リフティング構成を使用する方法とがある。本実施の形態に係るフィルタ係数変換方法とその装置は、２分割フィルタバンクを使用したＤＷＴおよびＩＤＷＴに適用される方法と装置である。
【００３０】
以下、図２２に示した分解側フィルタＨ0（ｚ），Ｈ1（ｚ）と、図２３に示した合成側フィルタＧ0（ｚ），Ｇ1（ｚ）とは、共に、有限長インパルス応答（ＦＩＲ）型フィルタで構成されており、９×７タップの実数型のフィルタ係数をもつものとする。
【００３１】
ＦＩＲ型フィルタの構成．
先ず、ＤＷＴを実現するＦＩＲ型フィルタについて説明する。図２２に示す分解側フィルタバンクにおいて、一方のダウンサンプラ１４０Ｌ〜１４２Ｌは、各ローパスフィルタＨ0（ｚ）から出力されるデータ列のうち、偶数番目のサンプルだけを保持し、奇数番目のサンプルを破棄するという間引き処理を実行し、他方のダウンサンプラ１４０Ｈ〜１４２Ｈは、各ハイパスフィルタＨ1（ｚ）から出力されるデータ列のうち、奇数番目のサンプルだけを保持し、偶数番目のサンプルを破棄するという間引き処理を実行する。このように、各フィルタＨ0（ｚ），Ｈ1（ｚ）から出力されたデータは、偶数と奇数という２つのフェーズ（ポリフェーズ）に分離されて間引き処理を施される。しかし、このようにフィルタＨ0（ｚ），Ｈ1（ｚ）が、偶数番目と奇数番目とに関係無く全ての入力データに関してフィルタ処理を行うのは効率的では無い。本実施の形態では、ローパスフィルタＨ0（ｚ）は偶数番目のデータ列についてのみフィルタ処理を実行し、ハイパスフィルタＨ1（ｚ）は奇数番目のデータ列についてのみフィルタ処理を実行し、その結果、各フィルタＨ0（ｚ）、Ｈ1（ｚ）は、各フェーズ毎にフィルタ処理と間引き処理とを同時並行に実行することとする。
【００３２】
図１は、分解側のＦＩＲ型ローパスフィルタＨ0（ｚ）の構成を示す模式図、図２は、分解側のＦＩＲ型ハイパスフィルタＨ1（ｚ）の構成を示す模式図である。入力画像１０は、入力データ列…，Ｘ（２ｎ−４），Ｘ（２ｎ−３），…，Ｘ（２ｎ），…，Ｘ（２ｎ＋４），…（ｎ：整数）で構成されている。図１に示す通り、ローパスフィルタＨ0（ｚ）は、９タップに対応したフィルタ係数ｈ0（−４），ｈ0（−３），…，ｈ0（３），ｈ0（４）を有し、入力データ列とフィルタ係数ｈ0（−４）〜ｈ0（４）とを畳み込み演算する乗算器１１1〜１１9および加算器１２を有している。このローパスフィルタＨ0（ｚ）は、次式（１）に従って、偶数番目のデータＸ（２ｎ）に関して選択的に畳み込み演算を実行し、データＹ（２ｎ）を出力する。
【００３３】
【数１】
【００３４】
また、図２に示す通り、ハイパスフィルタＨ1（ｚ）は、７タップに対応したフィルタ係数ｈ1（−４），ｈ1（−３），…，ｈ1（１），ｈ1（２）を有し、入力データ列とフィルタ係数ｈ1（−４）〜ｈ1（２）とを畳み込み演算する乗算器１３1〜１３7および加算器１４を有している。このハイパスフィルタＨ1（ｚ）は、次式（２）に従って、奇数番目のデータＸ（２ｎ＋１）に関して選択的に畳み込み演算を実行し、データＹ（２ｎ＋１）を出力する。
【００３５】
【数２】
【００３６】
次に、ＩＤＷＴを実現するＦＩＲ型フィルタについて説明する。図２３に示した合成側のローパスフィルタＧ0（ｚ）と、ハイパスフィルタＧ1（ｚ）とをそれぞれｚ変換を用いて表現すると、次式（３），（４）のようになる。
【００３７】
【数３】
【００３８】
上式（３），（４）中、フィルタ係数ｇ0（ｋ）（ｋ＝−３〜３）とｇ1（ｋ）（ｋ＝−３〜５）とはインパルス応答を示し、また、ｚ-kはｋ次の遅延を示している。
【００３９】
図２３に示した合成側のフィルタバンクは、以下に説明するポリフェーズ分解により変形されることができる。図３に、アップサンプラ３０とフィルタＧ（ｚ）との組み合わせを模式的に示す。フィルタＧ（ｚ）は、フィルタ係数ｈ（ｋ）（ｋ：整数）を有するＦＩＲ型フィルタである。アップサンプラ３０は、入力信号ｙ（ｎ）の各値の間にゼロ値を挿入するアップサンプリング処理を行い、フィルタＧ（ｚ）は、そのアップサンプラ３０からの出力データを補間した信号ｘ（ｎ）を出力する。フィルタＧ（ｚ）は、ｚ変換を用いた伝達関数で、Ｇ（ｚ）＝Ｒ0（ｚ2）ｚ-1＋Ｒ1（ｚ2）の形に変形され得る。このような表現は「タイプ２のポリフェーズ分解」と呼ばれている。２フェーズに分解された各フィルタＲ0（ｚ2），Ｒ1（ｚ2）は、「ポリフェーズフィルタ」と呼ばれる。
【００４０】
以上のフィルタのポリフェーズ表現に基づくと、ＦＩＲ型フィルタＧ（ｚ）は、図４に示すように、２つのポリフェーズフィルタＲ0（ｚ2），Ｒ1（ｚ2）と遅延素子３２と加算器３３とで表現される。すなわち、第１のポリフェーズフィルタＲ0（ｚ2）の出力信号は、遅延素子３２で１周期遅延した後に、加算器３３において第２のポリフェーズフィルタＲ1（ｚ2）の出力信号と加算される。更に、図４のフィルタ構成は、図５に示すフィルタ構成と等価である。従って、出力信号ｘ（ｎ）は、各フィルタＲ0（ｚ），Ｒ1（ｚ）の出力信号を交互に出力したものといえる。
【００４１】
ところで、図２３に示した合成側のローパスフィルタＧ0（ｚ）とハイパスフィルタＧ1（ｚ）とは、ｚ変換を用いた伝達関数で次式（３Ａ），（４Ａ）のように変形され得る。
【００４２】
【数４】
【００４３】
上式（３Ａ）中、Ｒ0（ｚ2），Ｒ1（ｚ2）は、合成側ローパスフィルタＧ0（ｚ）を構成するポリフェーズフィルタを示し、上式（４Ａ）中、Ｋ0（ｚ2），Ｋ1（ｚ2）は、合成側ハイパスフィルタＧ1（ｚ）を構成するポリフェーズフィルタを示している。
【００４４】
よって、前述のポリフェーズ表現に基づくと、図６に示す合成側のフィルタバンクは、図７に示すフィルタ構成に変形され得る。図６，図７において、符号３４，３５，３４Ａ，３４Ｂ，３５Ａ，３５Ｂはアップサンプラを示しており、符号３６，３８，４０は加算器、３７，３９は遅延素子を示している。
【００４５】
従って、ローパスフィルタ側の加算器３８の出力信号ｘ0（ｎ）は、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）の出力信号ｒ0，ｒ1を交互に出力したものとなり、ハイパスフィルタ側の加算器４０の出力信号ｘ1（ｎ）は、各ポリフェーズフィルタＫ0（ｚ），Ｋ1（ｚ）の出力信号ｋ0，ｋ1を交互に出力したものとなる。この結果、加算器３６の出力信号ｘ（ｎ）のうち、偶数番目の出力信号ｘ（２ｋ）は、各ポリフェーズフィルタＲ0（ｚ），Ｋ0（ｚ）の出力信号の和ｒ0＋ｋ0とし、奇数番目の出力信号ｘ（２ｋ＋１）は、各ポリフェーズフィルタＲ1（ｚ），Ｋ1（ｚ）の出力信号の和ｒ1＋ｋ1とすることができる。
【００４６】
以上のポリフェーズ表現に従って、合成側のフィルタバンクを実現するＦＩＲ型フィルタを構成できる。図８および図９は、合成側のＦＩＲ型フィルタの構成を示す模式図である。これらＦＩＲ型フィルタは、フィルタ処理とアップサンプリング処理とを同時並行に実行する。また、これらＦＩＲ型フィルタには、圧縮画像２０を構成するデータ列…，Ｙ（２ｎ−３），Ｙ（２ｎ−２），…，Ｙ（２ｎ＋４），Ｙ（２ｎ＋５），…が入力している。
【００４７】
図８に示す７タップのＦＩＲ型フィルタは、上記各ポリフェーズフィルタＲ0（ｚ2），Ｋ0（ｚ2）のフィルタ係数ｇ0（−２），ｇ0（０），ｇ0（２），ｇ1（−２），ｇ1（０），ｇ1（２），ｇ1（４）を使用し、これらフィルタ係数と入力データ列とを畳み込み演算する乗算器２１0，２１1，…，２１6および加減算器２２を有している。このＦＩＲ型フィルタは、次式（５）に従って畳み込み演算を実行して偶数番目のデータＸ（２ｎ）を合成する。
【００４８】
【数５】
【００４９】
また、図９に示す９タップのＦＩＲ型フィルタは、上記各ポリフェーズフィルタＲ1（ｚ2），Ｋ1（ｚ2）のフィルタ係数ｇ0（−３），ｇ0（−１），ｇ0（１），ｇ0（３），ｇ1（−３），ｇ1（−１），ｇ1（１），ｇ1（３），ｇ1（５）を使用し、これらフィルタ係数と入力データ列とを畳み込み演算する乗算器２３1，…，２３9および加算器２４を有している。このＦＩＲ型フィルタは、次式（６）に従って畳み込み演算を実行して奇数番目のデータＸ（２ｎ＋１）を合成する。
【００５０】
【数６】
【００５１】
チェス盤歪みの回避条件．
次に、上記チェス盤歪みの回避条件について説明する。図３において、フィルタへの入力信号ｙ（ｎ）として単位ステップ信号が印加されるとき、出力信号ｘ（ｎ）は、フィルタＧ（ｚ）のインパルス応答ｈ（ｋ）の総和であり、この総和は時間経過と共に一定値に収束することが望ましい。一方、図５において、入力信号ｙ（ｎ）に対応する出力信号ｘ（ｎ）は、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）の出力信号を交互に出力したものに等しい。入力信号ｙ（ｎ）として単位ステップ信号が印加されるとき、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）のインパルス応答の総和が交互に出力される。従って、各ポリフェーズフィルタＲ0（ｚ），Ｒ1（ｚ）のインパルス応答の総和が相違する場合は、ｎの値に応じて交互に異なる値が出力され、一定値に収束しないという現象が起きる。チェス盤歪みはこの種の現象を表していると考えられる。
【００５２】
従って、チェス盤歪みの回避条件は、少なくとも、各ポリフェーズフィルタのＲ0（ｚ），Ｒ1（ｚ）のインパルス応答の総和が一致することである。
【００５３】
フィルタ係数変換処理．
次に、本発明の第１の実施の形態に係るフィルタ係数変換方法とその装置について説明する。図１０は、本実施の形態に係るフィルタ係数変換装置１の概略構成を示す機能ブロック図である。このフィルタ係数変換装置１は、外部から入力する実数型フィルタ係数５を分数に丸め込み表現した値（＝Ｎ／２M；Ｎ，Ｍは１以上の整数）の分母（＝２M）の次数Ｍを決定する次数決定手段２と、その分子Ｎの整数値を選択して分解側の整数型のフィルタ係数（丸め込み値）６を出力する丸め込み値選択手段３と、合成側の整数型フィルタ係数を算出する係数算出手段３Ａと、入力する分解側および合成側の整数型フィルタ係数が所定条件を満たすか否かを判定する条件判定手段４と、を備えて構成されている。尚、実数型フィルタ係数５を丸め込み表現した値（＝Ｎ／２M）は１０進表現の値であり、実際の処理では、当該値はデジタル値で表現される。
【００５４】
以上の構成を有するフィルタ係数変換装置１を用いた分解側フィルタ係数の変換処理を、図１１のフローチャートを参照しつつ以下に詳説する。この変換処理では、分解側ローパスフィルタＨ0（ｚ）のフィルタ係数が整数型の値に変換される。変換元の実数型フィルタとしては、９×７タップのドビシス（Daubechies）フィルタを採用することができる。以下の表１，表２に、ドビシスフィルタのフィルタ係数＜ｈ0（ｎ）＞，＜ｈ1（ｎ）＞，＜ｇ0（ｎ）＞，＜ｇ1（ｎ）＞を示す。＜ｈ＞は、フィルタ係数ｈが実数型係数であることを表す記号である。
【００５５】
【表１】
【００５６】
【表２】
【００５７】
ステップＳＴ１では、このフィルタ係数変換装置１に、実数型フィルタ係数＜ｈ0（ｎ）＞が入力する。入力したフィルタ係数＜ｈ0（ｎ）＞は、次数決定手段２と丸め込み値選択手段３とにそれぞれ伝達する。続くステップＳＴ２では、次数決定手段２は、入力した実数型フィルタ係数＜ｈ0（ｎ）＞を丸め込み表現した値（＝Ｎ0（ｎ）／２M＝ｈ0（ｎ））の分母（＝２M）の次数Ｍを決定し、その値Ｍを丸め込み値選択手段３に出力する。
【００５８】
丸め込み値選択手段３は、ｎ番目の丸め込み値（＝Ｎ0（ｎ）／２M）の番号ｎがゼロ値の場合は、ステップＳＴ３，ＳＴ４の処理を実行し、番号ｎがゼロ値以外の場合は、ステップＳＴ５，ＳＴ６の処理を実行する。ステップＳＴ３では、整数型フィルタ係数の系列のうち中央位置の丸め込み値ｈ0（０）に着目し、この丸め込み値ｈ0（０）の分子Ｎ0（０）が偶数であり、且つ、丸め込み値ｈ0（０）と当該実数型フィルタ係数＜ｈ0（０）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ0（０）を選択する。続くステップＳＴ４では、選択した分子Ｎ0（０）を当該分母２Mで除算した丸め込み値ｈ0（０）が算出される。
【００５９】
一方、ステップＳＴ５では、整数型フィルタ係数の系列のうち中央位置の丸め込み値ｈ0（ｎ）（ｎ：ゼロ以外の整数）に着目し、この丸め込み値ｈ0（ｎ）と当該実数型フィルタ係数＜ｈ0（ｎ）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ0（ｎ）を選択する。整数値Ｎ0（ｎ）は必ずしも偶数である必要はない。続くステップＳＴ６では、選択した分子Ｎ0（ｎ）を当該分母２Mで除算した丸め込み値ｈ0（ｎ）が算出される。
【００６０】
以上のようにステップＳＴ４，ＳＴ６において、丸め込み値選択手段３が整数型フィルタ係数ｈ0（ｎ）を条件判定手段４に出力した後、条件判定手段４は、ステップＳＴ７以後の処理を実行する。ステップＳＴ７では、分解側ローパスフィルタＨ0（ｚ）のインパルス応答ｈ0（ｎ）の総和の絶対値を示すＤＣ成分ＧDCを算出し、当該ＤＣ成分ＧDCが所定値に一致するという規格化条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用する場合、ＤＣ成分ＧDCの値は「１」に一致しなければならない。ＤＣ成分ＧDCの算出式は、次式（７）の通りである。
【００６１】
【数７】
【００６２】
前記ステップＳＴ７で規格化条件が満たされていた場合は、ステップＳＴ８に処理が移行し、規格化条件が満たされていなかった場合は、ステップＳＴ９で規格化条件を満たすように規格化が行われた後に、ステップＳＴ８に処理が移行する。
【００６３】
次のステップＳＴ８では、係数算出手段３Ａは、分解側フィルタと合成側フィルタとが双直交性を満たすという双直交条件を用いて、合成側のハイパスフィルタＧ1（ｚ）の整数型フィルタ係数ｇ1（ｎ）を算出し、条件判定手段４に出力する。その双直交条件は次式（８）の通りである。
【００６４】
【数８】
【００６５】
ステップＳＴ１０では、条件判定手段４において、前記ステップＳＴ８で算出された合成側フィルタ係数ｇ1（ｎ）を用いて、合成側のハイパスフィルタＧ1（ｚ）を構成する各ポリフェーズフィルタＫ0（ｚ2），Ｋ1（ｚ2）のインパルス応答の総和の絶対値が一致するという束縛条件が成立するか否かが判定される。この束縛条件は、ハイパスフィルタＧ1（ｚ）の偶数番目のフィルタ係数の総和の絶対値と奇数番目のフィルタ係数の総和の絶対値とが一致することと同じである。ＪＰＥＧ２０００方式を採用した場合は、当該束縛条件に、更に、その総和の絶対値が１／２になる条件が付加される。ＪＰＥＧ２０００方式を採用した場合の束縛条件は次式（９）の通りである。
【００６６】
【数９】
【００６７】
前記ステップＳＴ１０で束縛条件が成立していなかった場合は、条件判定手段４は、当該整数型フィルタ係数ｈ0（ｎ），ｇ1（ｎ）の算出に失敗したとみなし、本フィルタ係数変換処理は終了する。他方、前記ステップＳＴ１０で束縛条件が成立していた場合は、次のステップＳＴ１１に処理が移行し、条件判定手段４は、整数型フィルタ係数ｈ0（ｎ），ｇ1（ｎ）を確定して出力する。
【００６８】
以上のフィルタ係数変換処理により、９×７タップのドビシスフィルタのフィルタ係数を変換した係数値ｈ0（ｎ），ｇ1（ｎ）を、それぞれ以下の表３，表４に示す。
【００６９】
【表３】
【００７０】
【表４】
【００７１】
次に、分解側ハイパスフィルタＨ1（ｚ）のフィルタ係数の変換処理を、図１２のフローチャートを参照しつつ以下に詳説する。先ず、ステップＳＴ２０では、上記フィルタ係数変換装置１に、実数型フィルタ係数＜ｈ1（ｎ）＞が入力する。入力したフィルタ係数＜ｈ1（ｎ）＞は、次数決定手段２と丸め込み値選択手段３とにそれぞれ伝達する。続くステップＳＴ２１では、次数決定手段２は、入力した実数型フィルタ係数＜ｈ1（ｎ）＞を丸め込み表現した値（＝Ｎ1（ｎ）／２M＝ｈ1（ｎ））の分母（＝２M）の次数Ｍを決定し、その値Ｍを丸め込み値選択手段３に出力する。
【００７２】
丸め込み値選択手段３は、ｎ番目の丸め込み値（＝Ｎ1（ｎ）／２M）の番号ｎがゼロ値の場合は、ステップＳＴ２２，ＳＴ２３の処理を実行し、番号ｎがゼロ値以外の場合は、ステップＳＴ２４，ＳＴ２５の処理を実行する。ステップＳＴ２２では、丸め込み値ｈ1（ｎ）の分子Ｎ1（−１）が偶数であり、且つ、丸め込み値ｈ1（−１）と当該実数型フィルタ係数＜ｈ1（−１）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ1（−１）を選択する。続くステップＳＴ２３では、選択した分子Ｎ1（−１）を当該分母２Mで除算した丸め込み値ｈ1（−１）が算出される。
【００７３】
一方、ステップＳＴ２４では、丸め込み値ｈ1（ｎ）（ｎ：−１以外の整数）と当該実数型フィルタ係数＜ｈ1（ｎ）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ1（ｎ）を選択する。その整数値Ｎ1（ｎ）は必ずしも偶数である必要はない。続くステップＳＴ２５では、選択した分子Ｎ1（ｎ）を当該分母２Mで除算した丸め込み値ｈ1（ｎ）が算出される。
【００７４】
以上のようにステップＳＴ２３，ＳＴ２５において、丸め込み値選択手段３が整数型フィルタ係数ｈ1（ｎ）を条件判定手段４に出力した後、条件判定手段４は、ステップＳＴ２６以後の処理を実行する。ステップＳＴ２６では、プラスマイナス１の値を交互にとる交番信号が印加された場合の分解側ハイパスフィルタＨ1（ｚ）の応答の総和の絶対値（以下、ナイキスト成分ＤNyquistと呼ぶ。）を算出し、当該ナイキスト成分ＤNyquistが所定値に一致するという規格化条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用する場合は、ナイキスト成分ＤNyquistの値は「２」に一致しなければならない。このナイキスト成分ＤNyquistの算出式は、次式（１０）の通りである。
【００７５】
【数１０】
【００７６】
前記ステップＳＴ２６で規格化条件が満たされていた場合は、ステップＳＴ２７に処理が移行し、規格化条件が満たされていなかった場合は、ステップＳＴ２８で規格化条件を満たすように規格化が行われた後に、ステップＳＴ２７に処理が移行する。
【００７７】
次のステップＳＴ２７では、分解側フィルタと合成側フィルタとが双直交性を満たすという双直交条件（上式（８））を用いて、合成側のローパスフィルタＧ0（ｚ）の整数型フィルタ係数ｇ0（ｎ）が算出される。
【００７８】
次のステップＳＴ２９では、前記ステップＳＴ２７で算出された合成側フィルタ係数ｇ0（ｎ）を用いて、合成側のローパスフィルタＧ0（ｚ）を構成する各ポリフェーズフィルタＲ0（ｚ2），Ｒ1（ｚ2）のインパルス応答の総和が一致するという束縛条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用した場合は、当該束縛条件に、更に、その総和が「１」になる条件が付加される。ＪＰＥＧ２０００方式を採用した場合の束縛条件は次式（１１）の通りである。
【００７９】
【数１１】
【００８０】
この束縛条件が成立するとき、各ポリフェーズフィルタのインパルス応答の総和が一致するため、上述した通り、復号化画像中のチェス盤歪みを回避することが可能となる。
【００８１】
前記ステップＳＴ２９で束縛条件が成立していなかった場合は、条件判定手段４は、当該整数型フィルタ係数ｈ1（ｎ），ｇ0（ｎ）の算出に失敗したとみなし、本フィルタ係数変換処理は終了する。他方、前記ステップＳＴ２９で束縛条件が成立していた場合は、次のステップＳＴ３０に処理が移行し、条件判定手段４は、整数型フィルタ係数ｈ1（ｎ），ｇ0（ｎ）を確定して出力する。
【００８２】
以上のフィルタ係数変換処理に従って、９×７タップのドビシスフィルタのフィルタ係数を変換し、その結果得られた整数型の係数値ｈ1（ｎ），ｇ0（ｎ）を以下の表５，表６に示す。
【００８３】
【表５】
【００８４】
【表６】
【００８５】
以上の通り、この第１の実施の形態では、上記ステップＳＴ２９（図１２）で、ローパスフィルタを構成する各ポリフェーズフィルタのインパルス応答の総和が一致するという条件が成立するか否かの判定処理を行っている。このため、ＩＤＷＴで低域成分を合成する際に当該低域成分にチェス盤歪みが混入しないように、比較的低いビット精度で、高精度の整数型フィルタ係数を算出できる。
【００８６】
また、上記ステップＳＴ１０（図１１）では、ハイパスフィルタを構成する各ポリフェーズフィルタのインパルス応答の総和の絶対値が一致するという条件が成立するか否かの判定処理が行われている。このため、分解側と合成側の各フィルタの構成要件を満たしつつ、チェス盤歪みを回避できるように高精度の整数型フィルタ係数を算出できる。
【００８７】
更に、上記ステップＳＴ３（図１１）とステップＳＴ２２（図１２）とでは、整数型フィルタ係数の系列のうち、中央の値に相当するｈ0（０），ｈ1（−１）の分子が共に偶数に選択される。このため、整数型フィルタ係数をより高い精度で算出できる。
【００８８】
従って、ソフトウェアまたはハードウェアにおいて、上記整数型フィルタ係数を用いて固定小数点演算でＤＷＴとＩＤＷＴとを効率良く実行することが可能となる。特にハードウェアを採用する場合は、全ての整数型フィルタ係数の分母が共通の２の巾乗をもつことから、除算処理をビットシフト演算で効率良く行うことができる。従って、入出力ピンの数が少ない小回路規模のハードウェア構成を実現することが可能である。
【００８９】
第２の実施の形態．
次に、本発明の第２の実施の形態について説明する。本実施の形態に係るリフティング係数変換方法とその装置は、リフティング構成を使用したＤＷＴおよびＩＤＷＴに適用される方法と装置である。最初に、リフティング構成を概説した後に、本実施の形態に係るリフティング係数変換処理を説明する。
【００９０】
リフティング構成．
図１３は、１ステージのみ（１次の分解レベルのみ）のＤＷＴとＩＤＷＴとを実現するフィルタ構成を示す図である。このような構成によるＤＷＴはポリフェーズＤＷＴと呼ばれている。図１３中、符号４１，４６は遅延素子、４２，４３はダウンサンプラ、４４，４５はアップサンプラを示している。また、図中のＰc（ｚ），Ｐ（ｚ）-1はポリフェーズ行列と称されている。
【００９１】
順変換においては、入力データＸ（ｋ）（ｋ：整数）は、分岐してダウンサンプラ４２と遅延素子４１とに伝達し、ダウンサンプラ４２は偶数番目のデータＸ（２ｎ＋４）（ｎ：整数）を出力し、一方、遅延素子４１の出力信号をダウンサンプリングするダウンサンプラ４３は、奇数番目のデータＸ（２ｎ＋３）を出力する。すなわち、入力データＸ（ｋ）は、偶数番目のデータＸ（２ｎ＋４）と奇数番目のデータＸ（２ｎ＋３）とに分離されて、ポリフェーズ行列Ｐc（ｚ）に入力することになる。このポリフェーズ行列Ｐc（ｚ）からは、低域成分（ＬＰ）Ｙ（２ｎ）と高域成分（ＨＰ）Ｙ（２ｎ＋１）とが出力される。
【００９２】
他方、逆変換においては、ポリフェーズ行列Ｐ（ｚ）-1は、入力データＹ（２ｎ），Ｙ（２ｎ＋１）に対して、ポリフェーズ行列Ｐ（ｚ）の逆変換を実行し、データＸ（２ｎ−２），Ｘ（２ｎ−３）を復元して出力する。偶数番目のデータＸ（２ｎ−２）はアップサンプラ４４と遅延素子４６とを経て加算器４７に伝達し、奇数番目のデータＸ（２ｎ−３）はアップサンプラ４５を経て加算器４７に伝達し、加算器４７は元のデータＸ（ｋ）を合成する。
【００９３】
順変換のポリフェーズ行列Ｐc（ｚ）と逆変換のポリフェーズ行列Ｐ（ｚ）-1は、リフティング構成と称する手法で構築できる。
【００９４】
順変換は図１４に示すリフティング構成で実現され、逆変換は図１５に示すリフティング構成で実現される。図１４中、符号５１，５３，５８，５９はｚ変換形式の伝達関数で表される２タップのＦＩＲ型フィルタを示しており、符号５４，５６，６０は遅延素子、６２は入力信号に係数１／κを乗算して出力する乗算器、６３は入力信号に係数κを乗算して出力する乗算器、５２，５５，５７は加算器、を示している。
【００９５】
また、図１５中、符号７２，７５，７８，８１はｚ変換形式の伝達関数で表される２タップのＦＩＲ型フィルタを示しており、符号７０は入力信号に係数κを乗算して出力する乗算器、７１は入力信号に係数１／κを乗算して出力する乗算器、７４，７７，８０は遅延素子、７３，７６，７９，８２は減算器、を示している。
【００９６】
図１４と図１５に現れる係数α，β，γ，δ，κは、リフティング係数と呼ばれており、９×７タップのドビシスフィルタのリフティング構成では実数型の値をもつ。
【００９７】
また、図１４に示す分解側リフティング構成により、入力データＸ（ｋ）は、奇数番目のデータＸ（２ｎ＋３）と偶数番目のデータＸ（２ｎ＋４）とに分解される。また、中間データＹ’（２ｎ＋３），Ｙ’’（２ｎ＋２），Ｙ’’’（２ｎ＋１），Ｙ’’’’（２ｎ）が次々と生成されて、最終的にデータＹ（２ｎ），Ｙ（２ｎ＋１）が出力される。この分解側リフティング構成は、図１６に示すように、データを示す黒点と、各黒点間を結ぶ線分とからなるツリー図で表現することができる。各黒点近傍には、当該黒点を示すデータが表示されている。例えば、左端の各黒点に対応して、それぞれ、入力データ列Ｘ（２ｎ），Ｘ（２ｎ＋１），…，Ｘ（２ｎ＋４）が表示されている。また、各黒点間を結ぶ線分の近傍には係数が表示されている。例えば、データＸ（２ｎ）を示す黒点とデータＹ’（２ｎ＋１）を示す黒点との間の線分近傍には係数αが表示されている。
【００９８】
図１６に示す分解側リフティング構成は、次の規則（Ａ），（Ｂ），（Ｃ）に基づいて解釈されるものである。（Ａ）黒点を示すデータは、左方から右方へ延びる線分に沿って伝達する。（Ｂ）黒点間を結ぶ線分は、当該線分を伝達するデータに当該係数を乗算する。（Ｃ）黒点は、各線分に沿って左方から入力するデータを加算して右方へ延びる線分に出力する。従って、その分解側リフティング構成は次式（１２）と等価である。
【００９９】
【数１２】
【０１００】
また、図１５に示す合成側リフティング構成により、入力データ列Ｙ（２ｎ＋４），Ｙ（２ｎ＋５）に対して、中間データＸ’’’（２ｎ＋４），Ｘ’’（２ｎ＋５），…が次々と生成されて、最終的に合成データＸ（ｋ）が出力される。この合成側リフティング構成も、図１７に示す黒点と線分とからなるツリー図で表現することが可能であり、次式（１３）と等価である。
【０１０１】
【数１３】
【０１０２】
９×７タップのドビシスフィルタのリフティング構成を採用した場合のリフティング係数α，β，γ，δ，κの正確な値を次式（１４）に示す。
【０１０３】
【数１４】
【０１０４】
また、以下の表７に、ドビシスフィルタの分解側フィルタ係数ｈ0（ｎ），ｈ1（ｎ）をリフティング係数α，β，γ，δ，κ，１／κで構成したものを示し、以下の表８に、ドビシスフィルタの合成側フィルタ係数ｇ0（ｎ），ｇ1（ｎ）をリフティング係数α，β，γ，δ，κ，１／κで構成したものを示す。
【０１０５】
【表７】
【０１０６】
【表８】
【０１０７】
リフティング係数変換処理．
次に、本発明の第２の実施の形態に係るリフティング係数変換方法とその装置について説明する。図１８は、本実施の形態に係るリフティング係数変換装置９０の概略構成を示す機能ブロック図である。このリフティング係数変換装置９０は、外部から入力する実数型リフティング係数を分数に丸め込み表現した値（＝Ｎ／２M；Ｎ，Ｍは１以上の整数）の分母（＝２M）の次数Ｍを決定する次数決定手段９１と、後述する評価式に基づいてその分子Ｎの整数値を探索する係数評価手段９３と、この係数評価手段９３に対して探索範囲を指示する探索範囲決定手段９２と、係数評価手段９３から出力された整数型リフティング係数を抽出する係数抽出手段９４と、を備えて構成されている。
【０１０８】
以上の構成を有するリフティング係数変換装置９０を用いたリフティング係数の変換処理を、図１９のフローチャートを参照しつつ以下に詳説する。最初のステップＳＴ１では、変換元の実数型リフティング係数がリフティング係数変換装置９０に入力する。次数決定手段９１は、実数型リフティング係数α，β，γ，δ，κ，１／κの各々について丸め込み表現した値（＝Ｎ／２M）の分母（＝２M）の次数Ｍを決定し、その値Ｍを係数評価手段９３に出力する。併行して、探索範囲決定手段９２は、各実数型リフティング係数の探索範囲を決定して係数評価手段９３に出力する。
【０１０９】
次のステップＳＴ４１Ａ以後において、係数評価手段９３は、指定された探索範囲内で、後述する評価式の値（以下、評価値と呼ぶ。）と、この値に対応する整数型リフティング係数とを算出する。すなわち、ステップＳＴ４１Ａ〜ＳＴ４６Ａと、ステップＳＴ４１Ｂ〜４６Ｂとの間でループを形成し、指定された探索範囲で整数型リフティング係数α，β，γ，δ，κ，１／κの分子を小刻みに順次変化させる。そして、ステップＳＴ４７では、そのループにおいて変化させた整数型リフティング係数の全ての組み合わせについて、以下に説明する評価値が算出される。
【０１１０】
上記の表８，表９によれば、上式（９）は次式（１５）のように表される。
【０１１１】
【数１５】
【０１１２】
また、上式（１１）は次式（１６）のように表される。
【０１１３】
【数１６】
【０１１４】
前記評価式は、上式（１５）の中辺の値と右辺の値との差分絶対値の和と，（１６）の中辺の値と右辺の値との差分絶対値の和とを加算したものであり、次式（１７）で表現される。
【０１１５】
【数１７】
【０１１６】
次のステップＳＴ４８では、係数抽出手段９４は、前記係数評価手段９３から入力する評価値の組み合わせのうち、最小の評価値をとる整数型リフティング係数の組み合わせ（α，β，γ，δ，κ，１／κ）を確定して出力する。ここで、上記したＤＣ成分ＧDCおよびナイキスト成分ＤNyquistがそれぞれ所定値をとるという条件が成立するか否かを判定してもよい。
【０１１７】
以上のリフティング係数変換処理の計算結果の例を、以下の表９，表１０，表１１に示す。表９および表１１の中の「範囲」は、上記探索範囲の変動幅の上下限値を示している。すなわち、上記探索範囲は、実数型リフティング係数から下限値を引いた値から、同実数型リフティング係数に上限値を足した値までの範囲である。例えば、表９に示す次数Ｍ＝５に対応する変動幅の上下限値は「±１」であるから、係数αの探索範囲は、＜α＞−１から＜α＞＋１、となる（但し、＜α＞は実数型リフティング係数）。本例では、各分母の次数Ｍの値に応じて、全ての整数型リフティング係数に共通の探索範囲が設定されている。表９と表１０は分離して表示されているが、各次数Ｍに対応する探索範囲は同じである。また、表１１中の「評価式」の値は上記評価値を意味している。
【０１１８】
【表９】
【０１１９】
【表１０】
【０１２０】
【表１１】
【０１２１】
以上の通り、この第２の実施の形態では、評価値がゼロ値に近くなるように整数型フィルタ係数が選択されることで、比較的低いビット精度で、チェス盤歪みを低減し得る高精度の整数型フィルタ係数を算出することが可能となる。
【図面の簡単な説明】
【０１２２】
【図１】本発明の第１の実施の形態に係る分解側のＦＩＲ型ローパスフィルタの構成を示す模式図である。
【図２】本発明の第１の実施の形態に係る分解側のＦＩＲ型ハイパスフィルタの構成を示す模式図である。
【図３】アップサンプラとフィルタとの組み合わせを示す模式図である。
【図４】図３に示すフィルタ構成のポリフェーズ表現を示す模式図である。
【図５】図３に示すフィルタ構成の他のポリフェーズ表現を示す模式図である。
【図６】合成側のフィルタバンクを示す模式図である。
【図７】図６に示すフィルタバンクのポリフェーズ表現を示す模式図である。
【図８】合成側のＦＩＲ型フィルタの構成を示す模式図である。
【図９】合成側のＦＩＲ型フィルタの構成を示す模式図である。
【図１０】第１の実施の形態に係るフィルタ係数変換装置の概略構成を示す機能ブロック図である。
【図１１】第１の実施の形態に係るフィルタ係数変換方法を示すフローチャートである。
【図１２】第１の実施の形態に係るフィルタ係数変換方法を示すフローチャートである。
【図１３】１ステージのＤＷＴとＩＤＷＴとを実現するフィルタ構成を示す図である。
【図１４】分解側フィルタバンクのリフティング構成を示す模式図である。
【図１５】合成側フィルタバンクのリフティング構成を示す模式図である。
【図１６】分解側リフティング構成を示すツリー図である。
【図１７】合成側リフティング構成を示すツリー図である。
【図１８】本発明の第２の実施の形態に係るリフティング係数変換装置の概略構成を示す機能ブロック図である。
【図１９】第２の実施の形態に係るリフティング係数変換方法を示すフローチャートである。
【図２０】ＪＰＥＧ２０００方式に基づいた画像符号化装置の概略構成を示す機能ブロック図である。
【図２１】ＪＰＥＧ２０００方式に基づいた画像復号化装置の概略構成を示す機能ブロック図である。
【図２２】１次元ＤＷＴを実現する２分割フィルタバンク群の構成例を示す模式図である。
【図２３】１次元ＩＤＷＴを実現する２分割フィルタバンク群の構成例を示す模式図である。
【図２４】２次元ＤＷＴを施された画像データを模式的に示す図である。
【符号の説明】
【０１２３】
１ フィルタ係数変換装置
２ 次数決定手段
３ 丸め込み値選択手段
４ 条件判定手段
９０ リフティング係数変換装置
９１ 次数決定手段
９２ 探索範囲決定手段
９３ 係数評価手段
９４ 係数抽出手段
【特許請求の範囲】
【請求項１】
画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換方法であって、
（ａ）変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する工程と、
（ｂ）前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値が最小となるように、前記整数型リフティング係数の分子Ｎを探索する工程と、
を備えることを特徴とするリフティング係数変換方法。
【請求項２】
請求項１記載のリフティング係数変換方法であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である、リフティング係数変換方法。
【請求項３】
画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換装置であって、
変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する次数決定手段と、
前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値を最小とするように、前記整数型リフティング係数の分子Ｎを探索する手段と、
を備えることを特徴とするリフティング係数変換装置。
【請求項４】
請求項３記載のリフティング係数変換装置であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である、リフティング係数変換装置。
【請求項１】
画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換方法であって、
（ａ）変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する工程と、
（ｂ）前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値が最小となるように、前記整数型リフティング係数の分子Ｎを探索する工程と、
を備えることを特徴とするリフティング係数変換方法。
【請求項２】
請求項１記載のリフティング係数変換方法であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である、リフティング係数変換方法。
【請求項３】
画像圧縮のための離散ウェーブレット変換および圧縮画像の復号のための離散逆ウェーブレット変換を実現する分解側フィルタおよび合成側フィルタの各リフティング構成で使用するリフティング係数を、実数型の係数から分数で表現される整数型リフティング係数へ変換するリフティング係数変換装置であって、
変換先の整数型リフティング係数Ｎ／２M（Ｎ，Ｍ：１以上の整数）の分母の次数Ｍを決定する次数決定手段と、
前記整数型リフティング係数で構成される前記合成側フィルタのフィルタ係数のうち、偶数番目の係数の総和の絶対値と奇数番目の係数の総和の絶対値との差分絶対値を最小とするように、前記整数型リフティング係数の分子Ｎを探索する手段と、
を備えることを特徴とするリフティング係数変換装置。
【請求項４】
請求項３記載のリフティング係数変換装置であって、前記リフティング構成は、９×７タップのドビシス（Daubechies）フィルタのリフティング構成である、リフティング係数変換装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【公開番号】特開２００７−１６６６４５（Ｐ２００７−１６６６４５Ａ）
【公開日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願番号】特願２００７−３８７（Ｐ２００７−３８７）
【出願日】平成１９年１月５日（２００７．１．５）
【分割の表示】特願２００２−４９７６０（Ｐ２００２−４９７６０）の分割
【原出願日】平成１４年２月２６日（２００２．２．２６）
【出願人】（５９１１２８４５３）株式会社メガチップス (322)
【Ｆターム（参考）】
【公開日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願日】平成１９年１月５日（２００７．１．５）
【分割の表示】特願２００２−４９７６０（Ｐ２００２−４９７６０）の分割
【原出願日】平成１４年２月２６日（２００２．２．２６）
【出願人】（５９１１２８４５３）株式会社メガチップス (322)
【Ｆターム（参考）】
[ Back to top ]