JP4525704B2 - 符号化装置および方法、記録媒体、並びにプログラム。 - Google Patents

Description

本発明は、符号化装置および方法、記録媒体、並びにプログラムに関し、特に、符号化処理による遅延時間を短縮させることができるようにした符号化装置および方法、記録媒体、並びにプログラムに関する。

従来の代表的な画像圧縮方式として、ISO（International Standards Organization）によって標準化されたJPEG(Joint Photographic Experts Group)がある。これは離散コサイン変換(Discrete Cosine Transform ; DCT)を用い、比較的高いビットが割り当てられる場合には、良好な符号化画像および復号画像を供することが知られている。

近年では画像をフィルタバンクと呼ばれるハイパス・フィルタとローパス・フィルタとを組み合わせたフィルタによって複数の帯域に分解し、帯域毎に符号化を行う方式の研究が盛んになっている。その中でも、ウェーブレット変換符号化は、DCT変換で問題になる高圧縮でのブロック歪みが無いことから、DCTに代わる新たな技術として有力視されている。

２００１年１月に国際標準化が完了したJPEG２０００は、このウェーブレット変換に高能率なエントロピ符号化（ビットプレーン単位のビット・モデリングと算術符号化）を組み合わせた方式を採用しており、JPEGに比べて符号化効率の大きな改善を実現している。

ウェーブレット変換処理（例えば特許文献１参照）は基本的に画像データを入力して、水平方向のフィルタリングと垂直方向のフィルタリングを行いながら、低域成分を階層的に分解する手段を用いる。

このウェーブレット変換処理により画像データが変換された係数データ（周波数成分）を、元の画像データに変換するウェーブレット逆変換処理は、最上位の分解レベルから最下位の分解レベルまで高域成分と低域成分を合成フィルタ処理しながら、最終的に画像を復元する処理を行う。

このようなウェーブレット変換・ウェーブレット逆変換を利用した符号化システムは、例えばTV会議システムやビデオゲームシステム等のように、画像データの伝送を行うシステムに利用されることが多い。つまり、送信側において、画像データがウェーブレット変換され、得られた係数データがエントロピ復号されて符号化データとして受信側に伝送される。受信側においては、取得した符号化データがエントロピ復号されて、得られた係数データがウェーブレット逆変換されて元の画像データが復元される。このような処理の流れが一般的である。

特開平１０−２８３３４２号公報

しかしながら、上述したような、例えばTV会議システムやビデオゲームシステム等のような画像伝送システムにおいては、画像データの伝送を低遅延で行うことが望ましい場合が多い。

従って、符号化処理による遅延時間のさらなる短縮も求められる。

本発明は、このような従来の実情に鑑みて提案されたものであり、符号化処理による遅延時間をより短縮させることができるようにするものである。

本発明の一側面の符号化装置は、画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行うフィルタ手段と、前記係数データを格納する係数格納手段と、前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて前記係数格納手段に書き込む書き込み手段と、前記係数格納手段の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出す読み出し手段と、前記読み出し手段により前記係数格納手段から前記所定順に読み出された前記係数データをエントロピ符号化するエントロピ符号化手段とを備える。

前記書き込み手段は、前記係数データを前記サブバンド毎に領域を分けて格納する書き込みバッファを介して、前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを前記係数格納手段に書き込み、前記読み出し手段は、前記係数データを前記サブバンド毎に領域を分けて格納する読み出しバッファを介して、前記係数格納手段から前記係数データを前記所定順に読み出すことができる。

前記書き込み手段および前記読み出し手段は、前記書き込み手段による前記書き込みバッファの各領域と前記係数格納手段の各領域との間のデータ転送、並びに、前記読み出し手段による前記読み出しバッファの各領域と前記係数格納手段の各領域との間のデータ転送を互いに異なるチャンネルにおいて行うことができる。

前記読み出し手段は、前記エントロピ符号化手段により次に前記エントロピ符号化される前記係数データを、前記係数データに対する前記エントロピ符号化が開始される前に、前記係数格納手段から先読みし、前記読み出しバッファに転送することができる。

前記フィルタ手段は、リフティング演算を用いて前記分析フィルタ処理を行うことができる。

前記書き込み手段は、前記フィルタ手段による最終の分解レベルの前記分析フィルタ処理により生成された前記係数データを、前記係数格納手段に書き込まずに前記エントロピ符号化手段に供給することができる。

前記フィルタ手段による前記分析フィルタ処理の途中で発生する中間データを格納する、前記係数格納手段よりもアクセス速度が速い中間データ格納手段をさらに備えることができる。

本発明の一側面の符号化方法は、画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行い、前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて係数格納部に書き込み、前記係数格納部の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出し、前記係数格納部から前記所定順に読み出された前記係数データをエントロピ符号化するステップを含む。
本発明の一側面の記録媒体は、コンピュータを、画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行うフィルタ手段と、前記係数データを格納する係数格納手段と、前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて前記係数格納手段に書き込む書き込み手段と、前記係数格納手段の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出す読み出し手段と、前記読み出し手段により前記係数格納手段から前記所定順に読み出された前記係数データをエントロピ符号化するエントロピ符号化手段として機能させるためのプログラムを記録する。
本発明の一側面のプログラムは、コンピュータを、画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行うフィルタ手段と、前記係数データを格納する係数格納手段と、前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて前記係数格納手段に書き込む書き込み手段と、前記係数格納手段の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出す読み出し手段と、前記読み出し手段により前記係数格納手段から前記所定順に読み出された前記係数データをエントロピ符号化するエントロピ符号化手段として機能させる。

本発明の一側面においては、画像データに対して、画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理が、その生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行われ、分析フィルタ処理により生成された係数データが、サブバンド毎に領域を分けて係数格納部に書き込まれ、係数格納部の各領域から、サブバンド毎に分けられた係数データが所定順に読み出され、係数格納部から所定順に読み出された係数データがエントロピ符号化される。

本発明の一側面によれば、画像データが周波数帯域毎に分解された係数データを所定の順番に並び替えることができる。特に、本発明の一側面によれば、復号処理による遅延時間をより短縮させることができる。

以下、図面を参照して本発明を適用した実施の形態について説明する。最初に符号化部の構成について説明する。

図１は、本発明を適用した符号化部の構成例を示すブロック図である。図１に示される符号化部１０は、ソフトウェアプログラムにより構成され、画像データを符号化して符号化データを生成するソフトウェアエンコーダが所定の情報処理装置のCPU（Central Processing Unit）またはSPU（Synergistic Processing Unit）などにより実行されることにより実現される機能を模式的に示したものである。図１に示されるように符号化部１０は、ウェーブレット変換部２１、係数並び替え部２２、エントロピ符号化部２３、途中計算用バッファ部２４、および、係数並び替え用バッファ部２５の機能を有する。

符号化部１０に入力された画像データ（以下、入力画像データとも称する）は、ウェーブレット変換部２１を介して途中計算用バッファ部２４に一時的に格納される。ウェーブレット変換部２１は、途中計算用バッファ部２４に格納された画像データに対してウェーブレット変換を施す。すなわち、ウェーブレット変換部２１は、途中計算用バッファ部２４から画像データを読み出して分析フィルタによりフィルタ処理（以下、分析フィルタ処理または分析フィルタリングとも称する）を施して低域成分および高域成分の係数のデータを生成し、生成された係数データを途中計算用バッファ部２４に格納する。ウェーブレット変換部２１は、水平分析フィルタと垂直分析フィルタとを有し、画像データ群に対して、画面水平方向と画面垂直方向の両方について分析フィルタ処理を行う。ウェーブレット変換部２１は、途中計算用バッファ部２４に格納された低域成分の係数データを再度読み出し、読み出した係数データに対して分析フィルタによるフィルタ処理を施して、高域成分および低域成分の係数のデータをさらに生成する。生成された係数データは、途中計算用バッファ部２４に格納される。

ウェーブレット変換部２１は、分解レベルが所定レベル（以下、最終レベルとも称する）に達するまでこの処理を繰り返しながら、適宜途中計算用バッファ部２４から係数データを読み出し、読み出された係数データを係数並び替え用バッファ部２５に書き込む。なお、ウェーブレット変換部２１は、最終レベルの分析フィルタ処理により生成した係数データについては、係数並び替え用バッファ部２５に書き込まずに、係数並び替え部２２に直接供給する。

係数並び替え部２２は、ウェーブレット変換部２１から供給された係数データをエントロピ符号化部２３に供給する。また、係数並び替え部２２は、係数並び替え用バッファ部２５に書き込まれた係数データを所定の順序で読み出し、エントロピ符号化部２３に供給する。

エントロピ符号化部２３は、供給された係数データを、所定の方法で量子化し、例えばハフマン符号化や算術符号化といった所定のエントロピ符号化方式で符号化する。エントロピ符号化部２３は、生成した符号化データを符号化部１０の外部に出力する。

次に、図１のウェーブレット変換部２１で行われる処理について、より詳細に説明する。先ず、ウェーブレット変換について、概略的に説明する。画像データに対するウェーブレット変換では、図２に概略的に示されるように、画像データを空間周波数の高い帯域と低い帯域とに分解する処理を、分解の結果得られる空間周波数の低い帯域のデータに対して再帰的に繰り返す。

上述したように、分析フィルタには、画像データに対して画面水平方向に分析フィルタ処理を行う水平分析フィルタと、画面垂直方向に分析フィルタ処理を行う垂直分析フィルタとがあり、各方向に対して１回ずつ分析フィルタ処理が行われることにより、画像データは４つの帯域（サブバンド）に分解される。ウェーブレット変換部１１は、分析フィルタ処理結果の、水平方向および垂直方向のいずれにおいても空間周波数の低い帯域に対して、上述した水平方向および垂直方向の分析フィルタ処理を再帰的に繰り返す（つまり階層的に繰り返す）。

図２は、分析フィルタ処理が４回繰り返された場合の例を概略的に示す図である。図２の例では、水平方向および垂直方向の分析フィルタ処理が再帰的に４回繰り替えされることにより、１ピクチャの画像データの周波数成分が、１３個の階層的なサブバンドに分解されている。このときの各サブバンドのデータ、つまり、ベースバンドの画像データが周波数帯域毎に分解された各周波数成分が係数データ（以下、単に係数と称する場合もある）である。

図２において、実線の四角および点線の角丸四角のそれぞれは、分析フィルタ処理により生成されるサブバンドを示しており、各サブバンドに表記される数字は、そのサブバンドの階層のレベルを示す。つまり、ベースバンドの画像データに対して何回分析フィルタ処理することにより得られるサブバンドであるかを示している。また、各サブバンドに表記される「Ｌ」および「Ｈ」は、それぞれ低域成分および高域成分を表しており、左側が水平方向の分析フィルタ処理結果、右側が垂直方向の分析フィルタ処理結果を示している。

図２の例では、ベースバンドの画像データに対して１回目の分析フィルタ処理が行われて、分解レベル１の４つのサブバンド（１ＬＬ、１ＬＨ、１ＨＬ、および１ＨＨ）が生成され、そのサブバンドのうち、水平方向および垂直方向の両方に対して低域成分であるサブバンド「１ＬＬ」に対して２回目の分析フィルタ処理が行われ、分解レベル２の４つのサブバンド（２ＬＬ、２ＬＨ、２ＨＬ、および２ＨＨ）が生成され、その水平方向および垂直方向の両方に対して低域成分であるサブバンド「２ＬＬ」に対して３回目の分析フィルタ処理が行われ、分解レベル３の４つのサブバンド（３ＬＬ、３ＬＨ、３ＨＬ、および３ＨＨ）が生成され、その水平方向および垂直方向の両方に対して低域成分であるサブバンド「３ＬＬ」に対して、４回目の分析フィルタ処理が行われ、分解レベル４の４つのサブバンド（４ＬＬ、４ＬＨ、４ＨＬ、および４ＨＨ）が生成されている。

このように、低域成分に対して繰り返し変換および分解を行うのは、画像のエネルギが低域成分に集中しているためである。このことは、図３Ａに一例が示される分解レベル＝１の状態から、図３Ｂに一例が示される分解レベル＝３の状態のように分解レベルを進めていくに従って、図３Ｂに示されるようにしてサブバンドが形成されていくことからも、理解される。このように分析フィルタ処理を再帰的に処理を行い、階層的なサブバンドを生成し、空間周波数の低い帯域のデータをより小さな領域に追い込んでいくことで、エントロピ符号化を行う際に効率的な圧縮符号化を可能とする。

なお、以下において、分析フィルタ処理により生成される４つのサブバンドのうち、再度分析フィルタ処理が行われる、水平方向および垂直方向の両方に対して低域成分であるサブバンド「ＬＬ」を低域サブバンドと称し、それ以上分析フィルタ処理が行われないその他のサブバンド「ＬＨ」、「ＨＬ」、および「ＨＨ」を高域サブバンドと称する。

ウェーブレット変換部１１は、通常、低域フィルタと高域フィルタとから構成されるフィルタバンクを用いて、上述のような処理を行う。なお、デジタルフィルタは、通常、複数タップ長のインパルス応答すなわちフィルタ係数を持っているため、フィルタ処理を行えるだけのベースバンドの画像データ（入力画像データ）または係数データを予めバッファリングしておく必要がある。また、ウェーブレット変換を多段にわたって行う場合も同様に、前段で生成したウェーブレット変換係数を、フィルタ処理が行える数だけバッファリングしておく必要がある。

このウェーブレット変換の具体的な例として、５×３フィルタを用いた方法について説明する。この５×３フィルタを用いた方法は、JPEG２０００規格でも採用されており、少ないフィルタタップ数でウェーブレット変換を行うことができる点で、優れた方法である。

５×３フィルタのインパルス応答（Ｚ変換表現）は、次の式（１）および式（２）に示すように、低域フィルタＨ₀（ｚ）と、高域フィルタＨ₁（ｚ）とから構成される。

Ｈ₀（ｚ）＝（−１＋２ｚ^-1＋６ｚ^-2＋２ｚ^-3−ｚ^-4）／８ ・・・（１）
Ｈ₁（ｚ）＝（−１＋２ｚ^-1−ｚ^-2）／２ ・・・（２）

これら式（１）および式（２）によれば、低域成分および高域成分の係数を、直接的に算出することができる。ここで、リフティング(Lifting)技術を用いることで、フィルタ処理の計算を減らすことができる。

図４を用いて、５×３フィルタに対してリフティング技術を適用した場合の、ウェーブレット変換を行う分析フィルタ側の処理について、概略的に説明する。

図４において、最上段部、中段部および最下段部は、それぞれ入力画像の画素列、高域成分出力および低域成分出力を示す。最上段は、入力画像の画素列に限らず、先のフィルタ処理で得られた係数でもよい。ここでは、最上段部が入力画像で画素列であるものとし、黒の四角印（■）が偶数番目（最初を0番目とする）の画素またはライン、黒丸印（●）が奇数番目の画素またはラインとする。

先ず第1段階として、次式（3）により入力画素列から高域成分の係数d_i ¹を生成する。

d_i ¹＝d_i ⁰-1/2(s_i ⁰+s_i+1 ⁰) ・・・（3）

次に第2段階として、この生成された高域成分の係数と、入力画像の奇数番目の画素とを用いて、次式（4）により低域成分の係数s_i ¹を生成する。

s_i ¹＝s_i ⁰+1/4(d_i-1 ¹＋d_i ¹） ・・・（4）

分析フィルタ側では、このようにして、フィルタリング処理により入力画像の画素データを低域成分と高域成分とに分解する。

図５を用いて、ウェーブレット変換により生成された係数を復元するウェーブレット逆変換を行う合成フィルタ側の処理（以下、合成フィルタ処理、合成フィルタリング、または、合成処理とも称する）について、概略的に説明する。この図5は、上述の図4と対応し、５×３フィルタを用い、リフティング技術を適用した例を示す。図5において、最上段部は、ウェーブレット変換により生成された入力係数を示し、黒丸印（●）が高域成分の係数、黒の四角印（■）が低域成分の係数をそれぞれ示す。

先ず第1段階として、次式（5）に従い、入力された低域成分および高域成分の係数から、偶数番目（最初を0番目とする）の係数s_i ⁰が生成される。

s_i ⁰＝s_i ¹-1/4(d_i-1 ¹＋d_i ¹) ・・・（5）

次に第2段階として、次式（6）に従い、上述の第1段階で生成された偶数番目の係数s_i ⁰と、入力された高域成分の係数d_i ¹とから、奇数番目の係数d_i ⁰が生成される。

d_i ⁰＝d_i ¹+1/2(s_i ⁰＋s_i+1 ⁰) ・・・（6）

合成フィルタ側では、このようにして、フィルタリング処理により低域成分および高域成分の係数を合成し、ウェーブレット逆変換を行う。

次に、このウェーブレット変換方法について、さらに具体的に説明する。図６は、５×３フィルタのリフティングによるフィルタ処理を、分解レベル＝２まで実行した例を示している。なお、図６において、図の左側に分析フィルタとして示される部分は、図１のウェーブレット変換部２１のフィルタである。また、図の右側に合成フィルタとして示される部分は、後述するウェーブレット逆変換部のフィルタである。

なお、図６では、説明の簡略化のため、実際の画像データは二次元の情報であるが、図の奥行き方向に水平方向の画素が存在するものとして一次元により表し、さらに、水平方向の分析フィルタ処理および合成フィルタ処理についての記載は省略している。

図６において、左端列は、原画像データのライン上の対応する位置にある画素データが縦方向に並べられて示されている。すなわち、ウェーブレット変換部２１におけるフィルタ処理は、垂直フィルタを用いて画面上を画素が縦に走査されて行われる。左端から１列目乃至３列目が分解レベル＝１のフィルタ処理を示し、４列目乃至６列目が分解レベル＝２のフィルタ処理を示す。左端から２列目は、左端の原画像データの画素に基づく高域成分出力、左端から３列目は、原画像データおよび高域成分出力に基づく低域成分出力を示す。分解レベル＝２のフィルタ処理は、左端から４列目乃至６列目に示されるように、分解レベル＝１のフィルタ処理の出力に対して処理がなされる。

分解レベル＝１のフィルタ処理において、第１段階のフィルタ処理として、原画像データの画素に基づき高域成分の係数データが算出され、第２段階のフィルタ処理として、第１段階のフィルタ処理で算出された高域成分の係数データと、原画像データの画素とに基づき低域成分の係数データが算出される。分解レベル＝１の一例のフィルタ処理を、図６における左側（分析フィルタ側）の第１列目乃至第３列目に示す。算出された高域成分の係数データは、図１の係数並び替え用バッファ部２５に格納される。また、算出された低域成分の係数データは、図１の途中計算用バッファ部２４に格納される。

図６においては、係数並び替え用バッファ部２５は、一点鎖線で囲まれた部分として示し、途中計算用バッファ部２４は、点線で囲まれた部分として示す。

途中計算用バッファ部２４に保持された分解レベル＝１のフィルタ処理の結果に基づき、分解レベル＝２のフィルタ処理が行われる。分解レベル＝２のフィルタ処理では、分解レベル＝１のフィルタ処理において低域成分の係数として算出された係数データを、低域成分および高域成分を含んだ係数データと見做して、分解レベル＝１と同様のフィルタ処理を行う。分解レベル＝２のフィルタ処理により算出された、高域成分の係数データおよび低域成分の係数データは、係数並び替え用バッファ部２５には格納されずに、係数並び替え部２２に供給される。また、算出された高域成分の係数データは、図１の途中計算用バッファ部２４に格納される。

ウェーブレット変換部２１では、上述したようなフィルタ処理を、画面の水平方向および垂直方向にそれぞれ行う。例えば、先ず、分解レベル＝１のフィルタ処理を水平方向に行い、生成された高域成分および低域成分の係数データを途中計算用バッファ部２４に格納する。次に、途中計算用バッファ部２４に格納された係数データに対して、垂直方向に分解レベル＝１のフィルタ処理を行う。この分解レベル＝１の水平および垂直方向の処理により、高域成分をさらに高域成分および低域成分に分解した係数データのそれぞれによる領域ＨＨおよび領域ＨＬと、低域成分をさらに高域成分および低域成分に分解した係数データのそれぞれによる領域ＬＨおよび領域ＬＬとの４領域が形成される。

そして、分解レベル＝２では、水平方向および垂直方向のそれぞれについて、分解レベル＝１で生成された低域成分の係数データに対してフィルタ処理が行われる。すなわち、分解レベル＝２では、分解レベル＝１で分解されて形成された領域ＬＬがさらに４つに分解され、領域ＬＬ内にさらに領域ＨＨ、領域ＨＬ、領域ＬＨおよび領域ＬＬが形成される。

ウェーブレット変換部２１は、ウェーブレット変換によるフィルタ処理を、画面の縦方向について、数ライン毎の処理に分割して、複数回に分けて段階的に行うようにしている。図６の例では、画面上の第１ラインからの処理になる１回目の処理は、７ラインについてフィルタ処理を行い、８ライン目からの処理になる２回目以降の処理は、４ライン毎にフィルタ処理を行っている。このライン数は、高域成分と低域成分とに２分解した後に、１ライン分の最低域成分が生成されるために必要なライン数に基づく。

なお、以下、符号化側（分析フィルタ側）において、この最低域成分の１ライン分（最低域成分のサブバンドの１ライン分の係数データ）を生成するために必要な、他のサブバンドも含めたラインの集まりを、プレシンクト（またはラインブロック）と称する。ここでラインとは、ウェーブレット変換前の画像データに対応するピクチャ若しくはフィールド内、または各サブバンド内において形成される１行分の画素データ若しくは係数データのことを示す。すなわち、符号化側において、プレシンクト（ラインブロック）とは、ウェーブレット変換前の元の画像データにおける、ウェーブレット変換後の最低域成分のサブバンド１ライン分の係数データを生成するために必要なライン数分の画素データ群、または、その画素データ群をウェーブレット変換して得られる各サブバンドの係数データ群のことを示す。

図６によれば、分解レベル＝２のフィルタ処理結果で得られる係数Ｃ５は、係数Ｃ４および途中計算用バッファ部２４に格納された係数Ｃ_aに基づき算出され、係数Ｃ４は、途中計算用バッファ部２４に格納された係数Ｃ_a、係数Ｃ_bおよび係数Ｃ_cに基づき算出される。さらに、係数Ｃ_cは、係数並び替え用バッファ部２５に格納される係数Ｃ２および係数Ｃ３、並びに、第５ラインの画素データに基づき算出される。また、係数Ｃ３は、第５ライン乃至第７ラインの画素データに基づき算出される。このように、分解レベル＝２における低域成分の係数Ｃ５を得るためには、第１ライン乃至第７ラインの画素データが必要とされる。

これに対して、２回目以降のフィルタ処理においては、前回までのフィルタ処理で既に算出され途中計算用バッファ部２４または係数並び替え用バッファ部２５に格納されている係数データを用いることができるので、必要なライン数が少なくて済む。

すなわち、図６によれば、分解レベル＝２のフィルタ処理結果で得られる低域成分の係数のうち、係数Ｃ５の次の係数である係数Ｃ９は、係数Ｃ４および係数Ｃ８、並びに、途中計算用バッファ部２４に格納された係数Ｃ_cに基づき算出される。係数Ｃ４は、上述した１回目のフィルタ処理により既に算出され、途中計算用バッファ部２４に格納されている。同様に、係数Ｃ_cは、上述の１回目のフィルタ処理により既に算出され、途中計算用バッファ部２４に格納されている。したがって、この２回目のフィルタ処理においては、係数Ｃ８を算出するためのフィルタ処理のみが、新たになされることになる。この新たなフィルタ処理は、第８ライン乃至第１１ラインがさらに用いられてなされる。

このように、２回目以降のフィルタ処理は、前回までのフィルタ処理により算出され途中計算用バッファ部２４および係数並び替え用バッファ部２５に格納されたデータを用いることができるので、それぞれ４ライン毎の処理で済むことになる。

なお、画面上のライン数が符号化のライン数と合致しない場合は、原画像データのラインを所定の方法で複製してライン数を符号化のライン数と合わせて、フィルタ処理を行う。

このように、最低域成分１ライン分の係数データが得られるだけのフィルタ処理を段階的に、画面全体のラインに対して複数回に分けて（プレシンクト単位で）行うことで、符号化データを伝送した際に低遅延で復号画像を得ることを可能としている。

ウェーブレット変換を行うためには、ウェーブレット変換そのものを実行するために用いられる第１のバッファと、所定の分解レベルまで処理を実行する間に生成される係数を格納するための第２のバッファとが必要とされる。第１のバッファは、途中計算用バッファ部２４に対応し、図６においては点線で囲まれて示されている。また、第２のバッファは、係数並び替え用バッファ部２５に対応し、図６においては一点鎖線に囲まれて示されている。第２のバッファに格納された係数は、復号の際に用いられるため、後段のエントロピ符号化処理の対象とされる。

次に、図１の係数並び替え部２２の処理について説明する。係数並び替え部２２は、ウェーブレット変換部２１で生成された係数データを、合成処理において処理される順に並び替えて、エントロピ符号化部２３に供給する。

既に説明したように、ウェーブレット変換においては、高域成分側から低域成分側へと係数が生成されていく。図６の例では、１回目において、原画像の画素データにより、分解レベル＝１のフィルタ処理で、高域成分の係数Ｃ１、係数Ｃ２および係数Ｃ３が順次生成される。そして、分解レベル＝１のフィルタ処理で得られた低域成分の係数データに対して分解レベル＝２のフィルタ処理を行い、低域成分の係数Ｃ４および係数Ｃ５が順次生成される。すなわち、第１回目では、係数Ｃ１、係数Ｃ２、係数Ｃ３、係数Ｃ４、係数Ｃ５の順に、係数データが生成される。この係数データの生成順は、ウェーブレット変換の原理上、必ずこの順序（高域から低域の順）になる。

これに対して、復号側（合成フィルタ側）では、低遅延で即座に復号を行うためには低域成分から画像の生成および出力を行う必要がある。そのため、符号化側で生成された係数データを最低域成分側から高域成分側に向けて並び替えて復号側に供給することが望ましい。

図６の例を用いて、より具体的に説明する。図６の右側は、逆ウェーブレット変換を行う合成フィルタ側を示す。復号側の、出力画像データの第１ライン目を含む１回目の合成処理（逆ウェーブレット変換処理）は、符号化側の１回目のフィルタ処理で生成された最低域成分の係数Ｃ４および係数Ｃ５と、係数Ｃ１とを用いて行われる。

すなわち、１回目の合成処理においては、係数Ｃ５、係数Ｃ４、係数Ｃ１の順に符号化側から復号側に係数データを供給し、復号側では、分解レベル＝２に対応する合成処理である合成レベル＝２の処理で、係数Ｃ５および係数Ｃ４に対して合成処理を行って係数Ｃ_fを生成し、バッファに格納する。そして、分解レベル＝１に対応する合成処理である合成レベル＝１の処理で、この係数Ｃ_fと係数Ｃ１に対して合成処理を行って、第１ラインを出力する。

このように、１回目の合成処理においては、符号化側で係数Ｃ１、係数Ｃ２、係数Ｃ３、係数Ｃ４、係数Ｃ５の順に生成された係数データが、係数Ｃ５、係数Ｃ４、係数Ｃ１、・・・の順に並び替えられて復号側に供給される。

なお、図６の右側に示す合成フィルタ側では、符号化側から供給される係数について、括弧内に符号化側での係数の番号を記し、括弧外に合成フィルタのライン順を記す。例えば係数Ｃ１（５）は、図６の左側の分析フィルタ側では係数Ｃ５であって、合成フィルタ側では第１ライン目であることを示す。

符号化側の２回目以降のフィルタ処理で生成された係数データによる復号側の合成処理は、前回の合成処理の際に合成あるいは符号化側から供給された係数データを用いて行うことができる。図６の例では、符号化側の２回目のフィルタ処理で生成された低域成分の係数Ｃ８および係数Ｃ９を用いて行う、復号側の２回目の合成処理は、符号化側の１回目のフィルタ処理で生成された係数Ｃ２および係数Ｃ３がさらに必要とされ、第２ライン乃至第５ラインが復号される。

すなわち、２回目の合成処理においては、係数Ｃ９、係数Ｃ８、係数Ｃ２、係数Ｃ３の順に符号化側から復号側に係数データを供給する。復号側では、合成レベル＝２の処理において、係数Ｃ８および係数Ｃ９と、１回目の合成処理の際に符号化側から供給された係数Ｃ４とを用いて係数Ｃ_gを生成し、バッファに格納する。この係数Ｃ_gと、上述の係数Ｃ４と、１回目の合成処理により生成されバッファに格納された係数Ｃ_fとを用いて係数Ｃ_hを生成し、バッファに格納する。

そして、合成レベル＝１の処理において、合成レベル＝２の処理で生成されバッファに格納された係数Ｃ_gおよび係数Ｃ_hと、符号化側から供給された係数Ｃ２（合成フィルタでは係数Ｃ６（２）と示されている）および係数Ｃ３（合成フィルタでは係数Ｃ７（３）と示されている）とを用いて合成処理が行われ、第２ライン乃至第５ラインが復号される。

このように、２回目の合成処理においては、符号化側で係数Ｃ２、係数Ｃ３、（係数Ｃ４、係数Ｃ５）、係数Ｃ６、係数Ｃ７、係数Ｃ８、係数Ｃ９の順に生成された係数データが、係数Ｃ９、係数Ｃ８、係数Ｃ２、係数Ｃ３、・・・の順に並び替えられて復号側に供給される。

３回目以降の合成処理においても、同様にして、係数並び替え用バッファ部２５に格納された係数データが所定の順序に並び替えられて復号側に供給され、４ラインずつ、ラインが復号される。

なお、符号化側において画面の下端のラインを含むフィルタ処理（以下、最後の回と呼ぶ）に対応する復号側の合成処理では、それまでの処理で生成されバッファに格納された係数データを全て出力することになるため、出力ライン数が多くなる。図６の例では、最後の回に８ラインが出力される。

なお、係数並び替え部２２による係数データの並び替え処理は、例えば、係数並び替え用バッファ部２５に格納された係数データを読み出す際の読み出しアドレスを、所定の順序に設定することでなされる。

なお、以下、復号側において、１回の合成処理で新たに必要となる係数データ群、すなわち、その回の合成処理で必要な係数データのうち前回までの合成処理において使用された係数データを除く係数データ群、および、１回の合成処理で復号される画素データ群の集まりをプレシンクトと称する。図６の例においては、二重鎖線で区切られた領域が、それぞれ、符号化側のプレシンクトおよび復号側のプレシンクトを示しており、符号化側のｎ番目のプレシンクトと復号側のｎ番目のプレシンクトの範囲は、必ずしも一致しない。

図７を用いて、上述までの処理をより具体的に説明する。図７は、５×３フィルタを用いて、分解レベル＝２までウェーブレット変換によるフィルタ処理を施した例である。ウェーブレット変換部２１において、図７Ａに一例が示されるように、入力画像データの第１ラインから第７ラインに対して１回目のフィルタ処理が水平および垂直方向にそれぞれ行われる（図７ＡのＩｎ−１）。

１回目のフィルタ処理の分解レベル＝１の処理において、係数Ｃ１、係数Ｃ２、および係数Ｃ３の３ライン分の係数データが生成され、図７Ｂに一例が示されるように、分解レベル＝１で形成される領域ＨＨ、領域ＨＬおよび領域ＬＨのそれぞれに配置される（図７ＢのＷＴ−１）。

また、分解レベル＝１で形成される領域ＬＬは、分解レベル＝２による水平および垂直方向のフィルタ処理でさらに４分解される。分解レベル＝２で生成される係数Ｃ５および係数Ｃ４は、分解レベル＝１による領域ＬＬ内において、領域ＬＬに係数Ｃ５による１ラインが配置され、領域ＨＨ、領域ＨＬおよび領域ＬＨのそれぞれに、係数Ｃ４による１ラインが配置される。

ウェーブレット変換部２１による２回目以降のフィルタ処理では、４ライン毎にフィルタ処理が行われ（図７ＡのＩｎ−２・・・）、分解レベル＝１で２ラインずつの係数データが生成され（図７ＢのＷＴ−２）、分解レベル＝２で１ラインずつの係数データが生成される。

図６の２回目の例では、分解レベル＝１のフィルタ処理で係数Ｃ６および係数Ｃ７の２ライン分の係数データが生成され、図７Ｂに一例が示されるように、分解レベル１で形成される領域ＨＨ、領域ＨＬおよび領域ＬＨの、１回目のフィルタ処理で生成された係数データの次から配置される。同様に、分解レベル＝１による領域ＬＬ内において、分解レベル＝２のフィルタ処理で生成された１ライン分の係数Ｃ９が領域ＬＬに配置され、１ライン分の係数Ｃ８が領域ＨＨ、領域ＨＬおよび領域ＬＨにそれぞれ配置される。

図７Ｂのようにウェーブレット変換されたデータを復号した際には、図７Ｃに一例が示されるように、符号化側の第１ライン乃至第７ラインによる１回目のフィルタ処理に対して、復号側の１回目の合成処理による第１ラインが出力される（図７ＣのＯｕｔ−１）。以降、符号化側の２回目から最後の回の前までのフィルタ処理に対して、復号側で４ラインずつが出力される（図７ＣのＯｕｔ−２・・・）。そして、符号化側の最後の回のフィルタ処理に対して、復号側で８ラインが出力される。

ウェーブレット変換部２１で高域成分側から低域成分側へと生成された係数データは、最終レベルの分析フィルタ処理により生成された係数データを除いて、係数並び替え用バッファ部２５に順次格納される。係数並び替え部２２は、上述した係数データの並び替えが可能となるまで係数並び替え用バッファ部２５に係数データが蓄積されると、合成処理において処理される順に並び替えながら係数データを係数並び替え用バッファ部２５から読み出す。読み出された係数データは、エントロピ符号化部２３に順次、供給される。

次に、９×７フィルタに対してリフティング技術を適用した場合の、ウェーブレット変換を行う分析フィルタ側の処理について、概略的に説明する。

図８は、９×７フィルタのリフティング構成を示している。図８の例において、１段目（最上段）は、入力画像のサンプル群（画素列）を示し、２，３段目は、それぞれステップＡ１およびステップＡ２の処理で生成される成分（係数）を示す。また、４段目は、ステップＡ３の処理で生成される高域成分出力を示し、５段目は、ステップＡ４の処理で生成される低域成分出力を示している。最上段部は、入力画像のサンプル群に限らず、前の分析フィルタリングで得られた係数であってもよい。ここでは、最上段部が入力画像のサンプル群であるものとし、四角印（■）が偶数番目のサンプルまたはライン、丸印（●）が奇数番目のサンプルまたはラインとする。

９×７フィルタに対してリフティング技術を適用した分析フィルタリングにおいては、ステップＡ３の処理で高域成分が得られ、ステップＡ４の処理で低域成分が得られる。なお、ステップＡ１乃至ステップＡ４の処理は、次の式（７）乃至式（１０）で表される。

このように、リフティング技術を適用した分析フィルタリングにおいては、ステップＡ１およびＡ２の処理が行われ、ステップＡ３で、高域成分の係数が生成された後に、ステップＡ４で、低域成分の係数が生成される。

図９は、水平方向の係数群に対しての水平分析フィルタリングを、図８のリフティング構成により実行する場合の例を示している。

図９の例においては、入力される水平方向の係数に対して、図８で上述した４つのステップ（ステップＡ１乃至Ａ４）の処理を経て、高域成分の係数（以下、高域係数とも称する）と低域成分の係数（以下、低域係数とも称する）が生成される例が示されており、リフティングのステップの方向は、図中上から下に進む。また、水平方向の係数の上に示される数字は、列（コラム）番号を示している。

さらに、上から１段目の丸および四角は、それぞれ、入力される高域係数および低域係数を表しており、２段目以降の丸および四角は、それぞれ、リフティング演算の過程で生成される高域係数および低域係数を表しており、その中でも、ハッチが付された丸および四角は、それぞれ、リフティング演算の結果である高域係数および低域係数を表している。

以下、動作について上から順に説明する。図９の上段には、水平方向にコラム番号４乃至６の３コラムの係数が入力されて、水平方向のリフティング構成による演算（以下、水平リフティング演算と称する）が行われる場合の例が示されている。

この水平リフティング演算のステップＡ３において１番目の高域係数を求め、ステップＡ４において１番目の低域係数を求めるためには、コラム番号０乃至４の４コラムの係数の入力が必要である。

その後、２番目の高域係数と低域係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるコラム番号５および６の２コラムの係数が必要であり、さらに、ステップＡ２のＰ１が示される係数を算出するためには、丸数字で示されるコラム番号４の係数も必要である。

太線実線で示される３つの係数は、１番目の高域係数および低域係数を求めるための水平リフティング演算（以下、１番目の水平リフティング演算とも称する）の過程で生成される係数のうちの一部である。

すなわち、２番目の高域係数と低域係数を求めるためには、結局、丸数字で示されるコラム番号４乃至６の３コラムの係数の入力が必要であり、さらに、１番目の水平リフティング演算の過程において生成される太線実線で示される３つの係数を、途中演算用の係数として、途中計算用バッファ部２４に格納しておく必要がある。

したがって、１番目の水平リフティング演算において途中計算用バッファ部２４に格納されていた太線実線で示される３つの係数と、入力されたコラム番号４乃至６の３コラムの係数が用いられて水平リフティング演算が行われることにより、その演算過程および終了時においては、２番目の高域係数と低域係数を含めた４つの係数（太線点線で示される）が生成される。これらのうち、一点鎖線で示される３つの係数は、３番目の高域係数と低域係数を求めるために必要な係数であるので、途中演算用の係数として、途中計算用バッファ部２４に格納される。

コラム番号６の係数の入力の後、水平方向に２コラムの係数が追加入力される場合、すなわち、水平方向にコラム番号６乃至８の３コラムの係数が入力されて、水平リフティング演算が行われる場合の例が、図９の下段に示されている。

２番目の場合と同様に、３番目の高域係数と低域係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるコラム番号７および８の２コラムの係数が必要であり、さらに、ステップＡ２のＰ２が示される係数を算出するためには、丸数字で示されるコラム番号６の係数も必要であることがわかる。

なお、下段の太線実線で示される３つの係数は、上段の一点鎖線で示されるように、２番目の水平リフティング演算で途中計算用バッファ部２４に格納されている。

したがって、２番目の水平リフティング演算で途中計算用バッファ部２４に格納されていた太線実線で示される３つの係数と、入力されたコラム番号６乃至８の３コラムの係数が用いられて水平リフティング演算が行われることにより、３番目の高域係数と低域係数を含めた４つの係数（太線点線で示される）が生成される。これらのうち、一点鎖線で示される３つの係数は、４番目の高域係数と低域係数を求めるために必要な係数であるので、途中計算用バッファ部２４に格納される。

以上のようにして、３コラム分の係数を順次入力しながら、途中演算用の３つの係数を保持しながら、水平リフティング演算が、画面の最右端のコラムまで実行されることで、水平方向の分析フィルタリングが完了される。

なお、以上においては、リフティング構成による１ライン分の水平分析フィルタリングの例を説明したが、上述した動作によって、係数のラインを上から下方向に順次入力しながら、リフティング構成により垂直分析フィルタリングを行う動作を、図１０を参照して説明する。なお、図１０において、図８および図９と対応する係数については同様に図示されており、その詳細な説明は繰り返しになるので省略する。

図１０の左側には、各入力ラインに対して、水平リフティング演算が行われる例が示されており、右側には、上から下の垂直方向に順に展開されていく各入力ラインの水平リフティング演算の結果の係数に対して、垂直リフティング演算が行われる例が概念的に示されている。

図中左から順に説明すると、先頭の入力ライン０における係数に対して、４つのステップからなる水平リフティング演算を経て１乃至１１の数字が付されている低域係数および高域係数が生成されている。このうち、奇数番目の数字（１，３，５，７，９，１１）が付されている係数は低域係数で、偶数番目の数字（２，４，６，８，１０）が付されている係数は高域係数である。

入力ライン１しか図示されていないが、入力ライン１乃至入力ラインｎに関しても同様である。すなわち、先頭の入力ライン１における係数に対して、４つのステップからなる水平リフティング演算を経て１乃至１１の数字が付されている低域係数および高域係数が生成されており、このうち、奇数番目の数字（１，３，５，７，９，１１）が付されている係数は低域係数で、偶数番目の数字（２，４，６，８，１０）が付されている係数は高域係数である。

そして、図１０の右側に示すように、入力ライン０の水平フィルタリングの結果の１乃至１１が付された係数は、上から１段目に、手前から奥への水平方向に並べて展開される。入力ライン１の水平フィルタリングの結果の１乃至１１が付された係数は、上から２段目に、手前から奥への水平方向に並べて展開される。入力ライン２の水平フィルタリングの結果の係数は、上から３段目に、手前から奥への水平方向に並べて展開される。

以上のように、各入力ライン０乃至入力ラインｎに対しての水平フィルタリングの結果の係数が、図１０の右側に示すように、上から下の垂直方向に順番に展開されていく。なお、実際には、各入力ラインの水平フィルタリングの結果の１乃至１１が付された係数は、手前から奥への水平方向に低域と高域が交互に並んでいる。

そして、垂直方向の係数が所定数集まり次第、すなわち、所定ライン数集まり次第、右側のリフティングのステップの方向に示されるように、左から右へと、垂直方向のリフティング構成による演算（すなわち、垂直リフティング演算）が行われる。

次に、垂直分析フィルタリングについて具体的に説明する。図１１は、水平分析フィルタリングの結果の係数を垂直方向に並べ、垂直方向の分析フィルタリングを、図８のリフティング構成により実行する場合の例を示している。

なお、この図は、図１０の右側に概念的に示した水平方向に展開されて並ぶ係数１つに着目したものであり、実際の２次元のウェーブレット変換では、ウェーブレット変換の過程で生成される周波数成分（サブバンド）の水平方向の係数の個数だけ、垂直方向の分析フィルタリングの計算が必要になることは自明である。

図１１の例においては、垂直方向の係数に対して、図８で上述した４つのステップ（ステップＡ１乃至Ａ４）の処理を経て、高域係数と低域係数が生成される例が示されており、リフティングのステップの方向は、図中左から右に進む。また、垂直方向の係数の左に示される数字は、ライン番号を示している。

さらに、左から１列目の丸および四角は、それぞれ、入力される高域係数および低域係数を表しており、２列目以降の丸および四角は、それぞれ、リフティング演算の過程で生成される高域係数および低域係数を表しており、その中でも、ハッチが付された丸および四角は、それぞれ、リフティング演算の結果である高域係数および低域係数を表している。

以下、動作について左から順に説明する。図１１の左側には、垂直方向にライン番号４乃至６の３ラインの係数が入力されて、垂直リフティング演算が行われる場合の例が示されている。

この垂直リフティング演算のステップＡ３において１番目の高域係数を求め、ステップＡ４において１番目の低域係数を求めるためには、ライン番号０乃至４の４ラインの係数が必要である。

その後、２番目の高域係数と低域係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるライン番号５および６の２ラインの係数が必要であり、さらに、ステップＡ２のＰ１が示される係数を算出するためには、丸数字で示されるライン番号４の係数も必要である。

太線実線で示される３つの係数は、１番目の高域係数および低域係数を求めるための垂直リフティング演算（以下、１番目の垂直リフティング演算と称する）の過程で生成される係数のうちの一部である。

すなわち、２番目の高域係数と低域係数を求めるためには、結局、丸数字で示されるライン番号４乃至６の３ラインの係数の入力が必要であり、さらに、１番目の垂直リフティング演算の過程において生成される太線実線で示される３つの係数を、途中演算用の係数として、途中計算用バッファ部２４に格納しておく必要がある。

したがって、１番目の垂直リフティング演算で途中計算用バッファ部２４に格納されていた太線実線で示される３つの係数と、対応するレベルのバッファから読み出され入力されるライン番号４乃至６の３ラインの係数が用いられて垂直リフティング演算が行われることにより、２番目の高域係数と低域係数を含めた４つの係数（太線点線で示される）が得られる。これらのうち、一点鎖線で示される３つの係数は、３番目の高域係数と低域係数を求めるために必要な係数であるので、途中計算用バッファ部２４に格納される。

ライン番号６の係数の読み出しの後、２ラインの係数が追加して読み出される場合、すなわち、垂直方向にライン番号６乃至８の３ラインの係数が入力されて、垂直リフティング演算が行われる場合の例が、図１１の右側に示されている。

２番目の場合と同様に、３番目の高域係数と低域係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるライン番号７および８の２ラインの係数が必要であり、さらに、ステップＡ２のＰ２が示される係数を算出するためには、丸数字で示されるライン番号６の係数も必要であることがわかる。

なお、右側の太線実線で示される３つの係数は、左側の一点鎖線で示されるように、２番目の垂直リフティング演算で途中計算用バッファ部２４に格納されている。

したがって、２番目の垂直リフティング演算で記憶されていた太線実線で示される３つの係数と、対応するレベルのバッファから読み出されて入力されるライン番号６乃至８の３ラインの係数が用いられて垂直リフティング演算が行われることにより、３番目の高域係数と低域係数を含めた４つの係数（太線点線で示される）が得られる。これらのうち、一点鎖線で示される３つの係数は、４番目の高域係数と低域係数を求めるために必要な係数であるので、途中計算用バッファ部２４に格納される。

以上のようにして、３ライン分の係数を順次入力しながら、途中演算用の３つの係数を保持しながら、垂直リフティング演算が、画面の最下位のラインまで実行されることで、垂直方向の分析フィルタリングが完了される。

次に、図１２乃至図１４を用いて、９×７フィルタを用いたリフティング技術を適用して、ウェーブレット変換により生成された係数を復元するウェーブレット逆変換を行う合成フィルタ側の処理について説明する。

図１２は、９×７フィルタのリフティング構成を示している。この９×７フィルタに対してリフティング技術を適用したときの合成フィルタリングについて説明する。

図１２の例において、１段目（最上段）は、ウェーブレット変換により生成された係数であり、丸印（●）が高域成分の係数を示し、四角印（■）が低域成分の係数を示す。２，３段目は、それぞれステップＢ１およびステップＢ２の処理で生成される成分（係数）を示す。また、４段目は、ステップＢ３の処理で生成される偶数成分出力を示し、５段目は、ステップＢ４の処理で生成される奇数成分出力を示している。

９×７フィルタに対してリフティング技術を適用した合成フィルタリングにおいては、ステップＢ３の処理で偶数成分が得られ、ステップＢ４の処理で奇数成分が得られる。なお、ステップＢ１乃至ステップＢ４の処理は、次の式（１１）乃至式（１４）で表される。

このように、リフティング技術を適用した合成フィルタリングにおいては、ステップＢ１およびＢ２の処理が行われ、ステップＢ３で、偶数成分の係数が生成された後に、ステップＢ４で、奇数成分の係数が生成される。

次に、垂直合成フィルタリングおよび水平合成フィルタリングの処理について、さらに詳細に説明する。まず、図１３を用いて、垂直合成フィルタリングの処理について具体的に説明する。図１３は、垂直方向の係数群に対しての垂直合成フィルタリングを、図１２のリフティング構成により実行する場合の例を示している。

図１３の例においては、垂直方向の係数に対して、図１２で上述した４つのステップ（ステップＢ１乃至Ｂ４）の処理を経て、偶数番目の係数（偶数係数）と奇数番目の係数（奇数係数）が生成される例が示されており、リフティングのステップの方向は、図中左から右に進む。

また、垂直方向の係数の左側に示される数字は、ライン番号を示しており、左から１列目のハッチが付された丸および四角は、それぞれ、高域入力および低域入力を表している。さらに、２列目以降の丸および四角は、それぞれ、リフティング演算の過程で生成される高域係数および低域係数を表しており、その中でも、黒丸および黒四角は、それぞれ、リフティング演算の結果である奇数係数および偶数係数を表している。

以下、動作について左から順に説明する。図１３の左側には、垂直方向にライン番号４乃至６の３ラインの係数が入力されて、垂直方向のリフティング構成による演算（すなわち、垂直リフティング演算）が行われる場合の例が示されている。なお、いまの場合、最上段の偶数係数は、奇数係数と組みになっていないのでその説明を省略する。

この垂直リフティング演算のステップＢ３において１番目の偶数係数を求め、ステップＢ４において１番目の奇数係数を求めるためには、ライン番号０乃至５の６ラインの係数が必要である。

その後、２番目の偶数係数と奇数係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるライン番号６および７の２ラインの係数が必要であり、さらに、ステップＢ２のＱ１が示される係数を算出するためには、丸数字で示されるライン番号５の係数も必要である。

太線実線で示される３つの係数は、１番目の偶数係数および奇数係数を求めるための垂直リフティング演算（以下、１番目の垂直リフティング演算と称する）の過程で生成される係数のうちの一部である。

したがって、１番目の垂直リフティング演算で生成された太線実線で示される３つの係数と、ライン番号５乃至７の３ラインの係数が用いられて垂直リフティング演算が行われることにより、２番目の偶数係数と奇数係数を含めた４つの係数（太線点線で示される）が得られる。

ライン番号７の係数の読み出しの後、２ラインの係数が追加して読み出される場合、すなわち、垂直方向にライン番号７乃至９の３ラインの係数が入力されて、垂直リフティング演算が行われる場合の例が、図１３の右側に示されている。

２番目の場合と同様に、３番目の偶数係数と奇数係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるライン番号８および９の２ラインの係数が必要であり、さらに、ステップＢ２のＱ２が示される係数を算出するためには、丸数字で示されるライン番号７の係数も必要である。

したがって、２番目の垂直リフティング演算で生成された太線実線で示される３つの係数と、ライン番号７乃至９の３ラインの係数が用いられて垂直リフティング演算が行われることにより、３番目の偶数係数と奇数係数を含めた４つの係数（太線点線で示される）が得られる。

以上のようにして、３ライン分の係数を順次入力しながら、途中演算用の３つの係数を保持しながら、垂直リフティング演算が、画面の最下位のラインまで実行されることで、垂直方向の合成フィルタリングが完了される。

次に、水平合成フィルタリングについて具体的に説明する。図１４は、垂直方向の合成フィルタリングの結果を水平方向に並べて、水平合成フィルタリングを、図１２のリフティング構成により実行する場合の例を示している。

図１４の例においては、水平方向の係数に対して、図１２で上述した４つのステップ（ステップＢ１乃至Ｂ４）の処理を経て、奇数係数と偶数係数が生成される例が示されており、リフティングのステップの方向は、図中上から下に進む。

また、水平方向の係数の上に示される数字は、列（コラム）番号を示しており、上から１段目のハッチが付された丸および四角は、それぞれ、高域入力および低域入力を表しており、２段目以降の丸および四角は、それぞれ、リフティング演算の過程で生成される高域係数および低域係数を表しており、その中でも、黒丸および黒四角は、それぞれ、リフティング演算の結果である奇数係数および偶数係数を表している。

以下、動作について上から順に説明する。図１４の上段には、水平方向にコラム番号５乃至７の３コラムの係数が入力されて水平方向のリフティング構成による演算（以下、水平リフティング演算と称する）が行われる場合の例が示されている。なお、いまの場合、最左側の偶数係数は奇数係数と組みになっていないのでその説明を省略する。

この水平リフティング演算のステップＢ３において１番目の偶数係数を求め、ステップＢ４において１番目の奇数係数を求めるためには、コラム番号０乃至５の６コラムの係数が必要である。

その後、２番目の奇数係数と偶数係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるコラム番号６および７の２コラムの係数が必要であり、さらに、ステップＢ２のＱ１が示される係数を算出するためには、丸数字で示されるコラム番号５の係数も必要である。

太線実線で示される３つの係数は、１番目の奇数係数および偶数係数を求めるための水平リフティング演算（以下、１番目の水平リフティング演算とも称する）の過程で生成される係数のうちの一部である。

したがって、１番目の水平リフティング演算で生成された太線実線で示される３つの係数と、コラム番号５乃至７の３コラムの係数が用いられて水平リフティング演算が行われることにより、その演算過程および終了時においては、２番目の奇数係数と偶数係数を含めた４つの係数（太線点線で示される）が得られる。

コラム番号７の係数の入力の後、水平方向に２コラムの係数が追加入力される場合、すなわち、水平方向にコラム番号７乃至９の３コラムの係数が入力されて、水平リフティング演算が行われる場合の例が、図１４の下段に示されている。

２番目の場合と同様に、３番目の奇数係数と偶数係数を求めるためには、太線実線で示される３つの係数と、丸数字で示されるコラム番号８および９の２コラムの係数が必要であり、さらに、ステップＢ２のＱ２が示される係数を算出するためには、丸数字で示されるコラム番号７の係数も必要である。

したがって、２番目の水平リフティング演算で生成された太線実線で示される３つの係数と、コラム番号７乃至９の３コラムの係数が用いられて水平リフティング演算が行われることにより、３番目の奇数係数と偶数係数を含めた４つの係数（太線点線で示される）が得られる。

以上のようにして、３コラム分の係数を順次入力しながら、途中演算用の３つの係数を保持しながら、水平リフティング演算が、画面の最右端のコラムまで実行されることで、水平方向の合成フィルタリングが完了される。

ところで、符号化部１０においては、メモリアクセスにより生じるレイテンシを抑え、処理を高速化するために、途中計算用バッファ部２４および係数並び替え用バッファ部２５を、アクセス速度の速いメモリ、例えば、ウェーブレット変換部２１、係数並び替え部２２、および、エントロピ符号化部２３を実現するプロセッサに内蔵されているローカルストアに配置することが望ましい。しかし、入力画像データのサイズ、フィルタの種類、分解レベル数、ローカルストアの容量などの条件によっては、係数データがローカルストアに収まらず、外部メモリに配置する必要が生じる場合がある。

ここで、途中計算用バッファ部２４と係数並び替え用バッファ部２５のアクセス回数と必要な容量について考える。

図１５および図１６は、符号化部１０の符号化処理において、入力画像データの１ピクセル当たりに、途中計算用バッファ部２４および係数並び替え用バッファ部２５にアクセスする回数を示している。図１５は、ウェーブレット変換に上述した９×７フィルタを用いた場合のアクセス回数を示し、図１６は、ウェーブレット変換に上述した５×３フィルタを用いた場合のアクセス回数を示している。なお、図１５および図１６のアクセス回数は、各バッファに対する書き込みと読み出しの１セットの処理を１回としてカウントしている。

途中計算用バッファ部２４に対しては、各分解レベルの低域サブバンド（ＬＬ）の各ピクセルについて、リフティング１段につき１回アクセスが行われる。従って、入力画像データ１ピクセル当たりの途中計算用バッファ部２４へのアクセス回数は、以下の式（１５）により求められる。

従って、図１５に示されるように、１分解レベル当たりのリフティング段数が４段である９×７フィルタを用いてウェーブレット変換を行った場合の、入力画像データ１ピクセル当たりの途中計算用バッファ部２４へのアクセス回数は、ウェーブレット変換の分解レベル数が１のとき4となり、分解レベル数が２のとき5となり、分解レベル数が３のとき5.25となり、分解レベル数が４のとき5.31となる。

また、図１６に示されるように、１分解レベル当たりのリフティング段数が２段である５×３フィルタを用いてウェーブレット変換を行った場合の、入力画像データ１ピクセル当たりの途中計算用バッファ部２４へのアクセス回数は、ウェーブレット変換の分解レベル数が１のとき2となり、分解レベル数が２のとき2.5となり、分解レベル数が３のとき2.62となり、分解レベル数が４のとき2.65となる。

また、係数並び替え用バッファ部２５へのアクセス回数は、分析フィルタ処理により生成される係数データのうち、最終レベルの分析フィルタ処理により生成される係数データ以外の係数データの個数と等しくなるので、入力画像データ１ピクセル当たりの係数並び替え用バッファ部２５へのアクセス回数は、以下の式（１６）により表される。

アクセス回数＝1−0.25^n-1 ・・・（１６）
ｎ：ウェーブレット変換の分解レベル数

従って、図１５および図１６に示されるように、９×７フィルタを用いてウェーブレット変換を行った場合も５×３フィルタを用いてウェーブレット変換を行った場合も同様に、入力画像データ１ピクセル当たりの係数並び替え用バッファ部２５へのアクセス回数は、ウェーブレット変換の分解レベル数が１のとき0となり、分解レベル数が２のとき0.75となり、分解レベル数が３のとき0.938となり、分解レベル数が４のとき0.984となる。

図１７および図１８は、符号化部１０の符号化処理において必要となる途中計算用バッファ部２４と係数並び替え用バッファ部２５の容量を、入力画像データの横方向のラインを基準にした値を示している。図１７は、ウェーブレット変換に９×７フィルタを用いた場合の必要容量を示し、図１８は、ウェーブレット変換に５×３フィルタを用いた場合の必要容量を示している。

途中計算用バッファ部２４の必要容量は、９×７フィルタを用いた場合、各分解レベルにおける低域サブバンド（ＬＬ）あたり、その低域サブバンドの横方向のラインを基準にして６ライン分必要となり、５×３フィルタを用いた場合、各分解レベルにおける低域サブバンド（ＬＬ）あたり、その低域サブバンドの横方向のラインを基準にして４ライン分必要となる。従って、入力画像データの水平方向のラインのサイズに対する分解レベルkの低域サブバンドの水平方向のラインのサイズは1／2^kとなるので、途中計算用バッファ部２４の必要容量を、入力画像データの横方向のラインを基準にした値は、以下の式（１７）により求められる。

従って、図１７に示されるように、９×７フィルタを用いてウェーブレット変換を行った場合の途中計算用バッファ部２４の必要容量は、分解レベル数が１のとき入力画像データの横方向の6ライン分となり、分解レベル数が2のとき9ライン分となり、分解レベル数が3のとき10.5ライン分となり、分解レベル数が4のとき11.25ライン分となる。

また、図１８に示されるように、５×３フィルタを用いてウェーブレット変換を行った場合の途中計算用バッファ部２４の必要容量は、分解レベル数が１のとき入力画像データの横方向の4ライン分となり、分解レベル数が2のとき6ライン分となり、分解レベル数が3のとき7ライン分となり、分解レベル数が4のとき7.5ライン分となる。

また、ある分解レベルｋにおいて、低域サブバンド以外のサブバンド1つ当たりに必要となる係数並び替え用バッファ部２５の容量s(k)は、そのサブバンドの横方向のラインを基準にして、以下の式（１８）により求められる。

上述したように、入力画像データの水平方向のラインのサイズに対する分解レベルkの低域サブバンドの水平方向のラインのサイズは1／2^kとなるので、分解レベルkにおいて必要となる係数並び替え用バッファ部２５の容量は、入力画像データの横方向のラインを基準にして、以下の式（１９）により求められる。

必要容量＝s(k)×1／2^k×低域サブバンド以外のサブバンドの数
＝s(k)×1／2^k×3 ・・・（１９）

従って、最終レベルの分析フィルタ処理により生成された係数データは係数並び替え用バッファ部２５に格納されないので、係数並び替え用バッファ部２５の必要容量は、式（１９）をk＝1からｎ-1まで合計した値となる。

すなわち、図１７に示されるように、９×７フィルタを用いてウェーブレット変換を行った場合の係数並び替え用バッファ部２５の必要容量は、ウェーブレット変換の分解レベル数が１のとき入力画像データの横方向の0ライン分となり、分解レベル数が２のとき12ライン分となり、分解レベル数が３のとき39ライン分となり、分解レベル数が４のとき94.5ライン分となる。

また、図１８に示されるように、５×３フィルタを用いてウェーブレット変換を行った場合の係数並び替え用バッファ部２５の必要容量は、ウェーブレット変換の分解レベル数が１のとき入力画像データの横方向の0ライン分となり、分解レベル数が2のとき6ライン分となり、分解レベル数が3のとき18ライン分となり、分解レベル数が4のとき42ライン分となる。

以上のように、途中計算用バッファ部２４の方が、係数並び替え用バッファ部２５と比較して、アクセス回数が多く、ウェーブレット変換の分解レベル数が１の場合を除いて、必要容量が小さい。従って、途中計算用バッファ部２４と係数並び替え用バッファ部２５の必要容量の合計がローカルストアにおいて割り当て可能な容量を超え、外部メモリに一部を配置する必要がある場合、途中計算用バッファ部２４を優先してローカルストアに残し、係数並び替え用バッファ部を外部メモリに配置するようにした方が、処理速度の低下を抑制できるとともに、容量の削減効果が大きいことが分かる。

図１９は、図１の符号化部１０を実現するとともに、途中計算用バッファ部をローカルストアに配置し、係数並び替え用バッファ部を外部メモリに配置するようにした符号化装置の一実施の形態を示すブロック図である。なお、図中、図１と対応する部分の一部については下２桁が同じ符号を付してあり、処理が同じ部分に関しては、その説明は繰り返しになるので省略する。

この符号化装置１０１は、SPU（Synergistic Processing Unit）１１１、ローカルストア１１２、メインメモリ１１３、および、メモリコントローラ１１４により構成される。

SPU１１１は、所定のプログラムを実行することにより、図１のウェーブレット変換部２１に相当するウェーブレット変換部１２１、係数並び替え部２２に相当する係数並び替え部１２２、および、エントロピ符号化部２３に相当するエントロピ符号化部１２３の機能を実現する。

ローカルストア１１２は、例えば、SPU１１１と同じハードウェアパッケージ内に内蔵されているキャッシュメモリ等により構成され、メインメモリ１１３と比較して、SPU１１１からのアクセス速度が速い。

ローカルストア１１２には、リードバッファ１３１、図１の途中計算用バッファ部２４に相当する途中計算用バッファ部１３２、ライトバッファ１３３、リードバッファ１３４、および、ライトバッファ１３５が配置される。リードバッファ１３１、ライトバッファ１３４、リードバッファ１３４、および、ライトバッファ１３５は、例えば、FIFO（First In, First Out）バッファ、または、単純なダブルバッファにより構成される。

メインメモリ１１３は、例えば、RAM（Random Access Memory）により構成され、係数並び替え用バッファ部１４１が配置される。係数並び替え用バッファ部１４１は、例えば、FIFO構造、かつ、バッファの終端の番地の次の番地を先頭の番地とするリング構造のバッファとされる。

メモリコントローラ１１４は、SPU１１１の各部からの指示の基に、SPU１１１の処理とは独立して、すなわち、SPU１１１の処理と並行して、ローカルストア１１２とメインメモリ１１３間のデータ転送を制御する。また、メモリコントローラ１１４は、メインメモリ１１３の状態等をSPU１１１の各部に通知する。

なお、図中、SPU１１１内部、および、SPU１１１とローカルストア１１２との間の方が、ローカルストア１１２とメインメモリ１１３との間よりも、データ転送が高速に行われ、レイテンシが短いことを示し、ローカルストア１１２とメインメモリ１１３との間の方が、SPU１１１内部、および、SPU１１１とローカルストア１１２との間よりも、データ転送の速度が低速かつ不安定で、レイテンシが長いことを示すために、SPU１１１内部、および、SPU１１１とローカルストア１１２との間の矢印の線が、ローカルストア１１２とメインメモリ１１３との間の矢印の線より太く示されている。

次に、図２０のフローチャートを参照して、符号化装置１０１により実行される符号化処理の流れの例を説明する。

ステップＳ１において、ウェーブレット変換部１２１は、処理対象プレシンクトの番号Ａを初期設定にする。通常の場合、番号Ａは「１」に設定される。

ステップＳ２において、ウェーブレット変換部１２１は、最低域サブバンドにおいて上からＡ番目の１ラインを生成するのに必要なライン数（すなわち、１プレシンクト）の画像データを取得する。具体的には、ウェーブレット変換部１２１は、１番目のプレシンクトの入力画像データのラインをメインメモリ１１３から途中計算用バッファ部１３２に転送するようにメモリコントローラ１１４に要求する。メモリコントローラ１１４は、転送が要求された入力画像データのラインをメインメモリ１１３から途中計算用バッファ部１３２に転送する。ウェーブレット変換部１２１は、途中計算用バッファ部１３２に転送された入力画像データを必要に応じて読み出す。

また、ウェーブレット変換部１２１は、２番目のプレシンクトの入力画像データの一部または全部をメインメモリ１１３からリードバッファ１３１に転送するようにメモリコントローラ１１４に要求する。メモリコントローラ１１４は、転送が要求された入力画像データのラインをメインメモリ１１３からリードバッファ１３１に転送する。すなわち、次のプレシンクトの処理で必要となる入力画像データのラインが、メインメモリ１１３からリードバッファ１３１に先読みされる。

このように、２番目以降のプレシンクトの処理では、処理対象の入力画像データのラインがリードバッファ１３１から途中計算用バッファ部１３２に転送されるとともに、次のプレシンクトの処理で必要となる入力画像データのラインが、ライン順にメインメモリ１１３からリードバッファ１３１に先読みされる。

ステップＳ３において、ウェーブレット変換部１２１は、取得した画像データに対して、画面垂直方向に並ぶ画像データに対して分析フィルタリングを行う垂直分析フィルタリングを行う。

ステップＳ４において、ウェーブレット変換部１２１は、画面水平方向に並ぶ画像データに対して分析フィルタリングを行う水平分析フィルタリングを行う。

ステップＳ５において、ウェーブレット変換部１２１は、分析フィルタリングが最終レベルまで終了したかを判定する。分析フィルタリングが最終レベルまで終了していないと判定された場合、処理はステップＳ６に進む。

ステップＳ６において、ウェーブレット変換部１２１は、高域サブバンドの係数データを生成順にバッファに書き込む。具体的には、ウェーブレット変換部１２１は、現在の分解レベルの高域サブバンド（ＨＬ,ＬＨ,ＨＨ）の係数データを生成順にライトバッファ１３３に書き込み、ライトバッファ１３３に書き込んだ係数データを、すでに係数並び替え用バッファ部１４１に格納されている係数データの後ろに続けて書き込むようにメモリコントローラ１１４に要求する。メモリコントローラ１１４は、ライトバッファ１３３に書き込まれた係数データを、そのままの順番で、すでに係数並び替え用バッファ部１４１に格納されている係数データの後ろに続けて書き込むように制御する。

これにより、係数データが生成順に並べられて係数並び替え用バッファ部１４１に書き込まれる。また、ライトバッファ１３３から係数並び替え用バッファ部１４１へのデータ転送により生じるSPU１１１の待ち時間を短縮することができる。

メモリコントローラ１１４は、係数並び替え用バッファ部１４１に格納された各係数データの格納位置を示す情報を係数並び替え部１２２に供給する。係数並び替え部１２２は、各係数データの格納位置を記憶する。メモリコントローラ１１４は、係数並び替え用バッファ部１４１に転送された係数データをライトバッファ１３３から消去する。

その後、処理はステップＳ３に戻り、ステップＳ５において、分析フィルタリングが最終レベルまで終了したと判定されるまで、ステップＳ３乃至Ｓ６の処理が繰り返し実行される。すなわち、現在の分解レベルに対して、分析フィルタリングが繰り返され、得られた高域サブバンドの係数データが、生成順に係数並び替え用バッファ部１４１に書き込まれる。

一方、ステップＳ５において、分析フィルタリングが最終レベルまで終了したと判定された場合、処理はステップＳ７に進む。

ステップＳ７において、ウェーブレット変換部１２１は、最終レベルの係数データを供給する。すなわち、ウェーブレット変換部１２１は、最終レベルの分析フィルタリングにより生成された係数データを、係数並び替え用バッファ部１４１に書き込まずに、係数並び替え部１２２に直接供給する。係数並び替え部１２２は、取得した係数データをそのままエントロピ符号化部１２３に供給する。これにより、係数並び替え用バッファ部１４１の容量、および、係数並び替え用バッファ部１４１へのアクセス回数を削減することができる。

なお、最終レベルの係数データのうち高域の係数データは、後のプレシンクト処理において使用されるため、途中計算用バッファ部１３２に格納される。

ステップＳ８において、エントロピ符号化部１２３は、供給された係数データを、ライン毎にエントロピ符号化する。

ステップＳ９において、エントロピ符号化部１２３は、符号化データを送出する。具体的には、エントロピ符号化部１２３は、エントロピ符号化により得られた符号化データをライトバッファ１３５に書き込み、メインメモリ１１３に転送するようにメモリコントローラ１１４に要求する。メモリコントローラ１１４は、ライトバッファ１３５に書き込まれた符号化データをメインメモリ１１３に転送する。メインメモリ１１３に転送された符号化データは、例えば、図示せぬ通信装置などにより、後述する復号部に送出される。

ステップＳ１０において、エントロピ符号化部１２３は、Ａ番目のプレシンクトの符号化が終了したか否かを判定する。エントロピ符号化部１２３は、Ａ番目の合成処理において必要となる係数データのエントロピ符号化が全て終了していない場合、Ａ番目のプレシンクトの符号化が終了していないと判定し、処理はステップＳ１１に進む。

ステップＳ１１において、係数並び替え部１２２は、次に処理する係数データを読み出す。具体的には、係数並び替え部１２２は、直前に符号化された係数データの次に合成処理において処理される係数データの係数並び替え用バッファ部１４１上の格納位置を求め、求めた位置に格納されている係数データを係数並び替え用バッファ部１４１からリードバッファ１３４に転送するようにメモリコントローラ１１４に要求する。メモリコントローラ１１４は、要求された係数データを係数並び替え用バッファ部１４１からリードバッファ１３４に転送し、転送した係数データを係数並び替え用バッファ部１４１から消去する。係数並び替え部１２２は、リードバッファ１３４に格納された係数データを読み出し、エントロピ符号化部１２３に供給する。

さらに、係数並び替え部１２２は、今回読み出した係数データの次に合成処理において処理される係数データの係数並び替え用バッファ部１４１上の格納位置を求め、求めた位置に格納されている係数データを係数並び替え用バッファ部１４１からリードバッファ１３４に転送するようにメモリコントローラ１１４に要求する。メモリコントローラ１１４は、要求された係数データを係数並び替え用バッファ部１４１からリードバッファ１３４に転送し、転送した係数データを係数並び替え用バッファ部１４１から消去する。すなわち、次にエントロピ符号化される係数データが係数並び替え用バッファ部１４１からリードバッファ１３４に先読みされる。

以降、ステップＳ１１において、係数並び替え部１２２により、次にエントロピ符号化される係数データがリードバッファ１３４から読み出されるとともに、その次にエントロピ符号化される係数データが係数並び替え用バッファ部１４１からリードバッファ１３４に先読みされる。これにより、係数並び替え用バッファ部１４１からリードバッファ１３４へのデータ転送により生じるSPU１１１の待ち時間を短縮することができる。

その後、ステップＳ１０において、Ａ番目のプレシンクトの符号化が終了したと判定されるまで、ステップＳ８乃至Ｓ１１の処理が繰り返し実行され、合成処理において処理される順に係数データが係数並び替え用バッファ部１４１から読み出され、エントロピ符号化され、その結果得られた符号化データが送出される。

一方、ステップＳ１０において、エントロピ符号化部１２３は、Ａ番目の合成処理において必要となる係数データのエントロピ符号化が全て終了している場合、Ａ番目のプレシンクトの符号化が終了したと判定し、処理はステップＳ１２に進む。

ステップＳ１２において、ウェーブレット変換部１２１は、番号Ａの値を「１」インクリメントして次のプレシンクトを処理対象とする。

ステップＳ１３において、ウェーブレット変換部１２１は、処理対象のピクチャ（フレームまたはフィールド）について、未処理の画像入力ラインが存在するか否かを判定する。未処理の画像入力ラインが存在すると判定された場合、処理は、ステップＳ２に戻り、新たな処理対象のプレシンクトに対してそれ以降の処理が繰り返される。

以上のように、ステップＳ２乃至ステップＳ１３の処理が繰り返し実行され、各プレシンクトが符号化される。そして、ステップＳ１３において、未処理の画像入力ラインが存在しないと判定された場合、そのピクチャに対する符号化処理が終了される。次のピクチャに対しては新たに符号化処理が開始される。

ここで、図２１乃至図２４を参照して、符号化装置１０１により係数データが並び替えられる様子を、５×３フィルタのリフティングによるフィルタ処理を分解レベル＝3まで実行した場合を具体例に挙げて説明する。

図２１は、５×３フィルタのリフティングによるフィルタ処理を分解レベル＝３まで実行した例を、図６と同様の図で示している。また、図２２は、図２１の点線より左側の分析フィルタ側の図に、合成フィルタ側の２番目のプレシンクトに対応する部分を重ねて示した図である。

なお、図２１および図２２においては、説明を分かりやすくするために、各係数の番号は、図６とは異なり、分析フィルタ側および合成フィルタ側とも、合成処理において処理される順番により示されている。また、図２１および図２２においては、図６と同様に、説明の簡略化のため、実際の画像データは二次元の情報であるが、図の奥行き方向に水平方向の画素が存在するものとして一次元により表し、さらに、水平方向の分析フィルタ処理および合成フィルタ処理についての記載は省略している。

基本的な動作は、図６の分解レベル２の分析フィルタ処理の場合と同じであるが、図２１の場合、ウェーブレット変換により分解レベル３の低域サブバンドの係数データ１ラインを得るために必要なライン数は、最初のプレシンクトでは１５ラインであり、２番目以降のプレシンクトでは８ラインになる。また合成側の出力は、最初のプレシンクトが１ライン、以降が８ラインとなる。

５×３フィルタのリフティングによる分析フィルタ処理を分解レベル＝３まで実行した場合、１回目の分析フィルタ処理により、係数Ｃ４，係数Ｃ８，係数Ｃ９，係数Ｃ３，係数Ｃ１１，係数Ｃ１２，係数Ｃ７，係数Ｃ１６，係数Ｃ１７，係数Ｃ１０，係数Ｃ２，係数Ｃ１の順に係数データが生成され、２回目の分析フィルタ処理により、係数Ｃ１９，係数Ｃ２０，係数Ｃ１５，係数Ｃ２４，係数Ｃ２５，係数Ｃ１８，係数Ｃ６，係数Ｃ５の順に係数データが生成される。一方、１回目の合成フィルタ処理において、係数Ｃ１，係数Ｃ２，係数Ｃ３，係数Ｃ４の順に係数データが処理され、２回目の合成フィルタ処理において、係数Ｃ５，係数Ｃ６，係数Ｃ７，係数Ｃ８，係数Ｃ９，係数Ｃ１０，係数Ｃ１１，係数Ｃ１２の順に係数データが処理される。

ここで、２番目のプレシンクトに対する符号化処理に注目して、係数データの並び替えについて説明する。

図２３は、２番目のプレシンクトに対する符号化処理の流れを示す図である。なお、図２３では、図２１および図２２と同様に、説明の簡略化のため、水平方向の分析フィルタ処理についての記載は省略している。

図２３に示されるように、２番目のプレシンクトに対する符号化処理においては、最初に、入力画像データの１５および１６ライン目がウェーブレット変換部１２１に入力され、２番目のプレシンクトの領域Ｄ１１（図２１）内の分解レベル１の分析フィルタ処理（ウェーブレット変換）が行われ、係数Ｃ１９が生成され、係数並び替え用バッファ部１４１に書き込まれる。

２番目に、入力画像データの１７および１８ライン目がウェーブレット変換部１２１に入力され、領域Ｄ１２内の分解レベル１の分析フィルタ処理が行われ、係数Ｃ２０が生成され、係数並び替え用バッファ部１４１に書き込まれる。次に、領域Ｄ１２内の分解レベル２の分析フィルタ処理が行われ、係数Ｃ１５が生成され、係数並び替え用バッファ部１４１に書き込まれる。

３番目に、入力画像データの１９および２０ライン目がウェーブレット変換部１２１に入力され、領域Ｄ１３内の分解レベル１の分析フィルタ処理が行われ、係数Ｃ２４が生成され、係数並び替え用バッファ部１４１に書き込まれる。

４番目に、入力画像データの２１および２２ライン目がウェーブレット変換部１２１に入力され、領域Ｄ１４内の分解レベル１の分析フィルタ処理が行われ、係数Ｃ２５が生成され、係数並び替え用バッファ部１４１に書き込まれる。次に、領域Ｄ１４内の分解レベル２の分析フィルタ処理が行われ、係数Ｃ１８が生成され、係数並び替え用バッファ部１４１に書き込まれる。最後に、領域Ｄ１４内の分解レベル３の分析フィルタ処理が行われ、係数Ｃ５および係数Ｃ６が生成される。係数Ｃ５および係数Ｃ６は、係数並び替え用バッファ部１４１に書き込まれずに、係数並び替え部１２２を介して、エントロピ符号化部１２３に直接供給される。

なお、図２３において、内部にDWTの文字が書かれた四角の縦方向の長さが分解レベルにより異なっているのは、分解レベルによって処理する画素数が異なり（具体的には、水平方向の画素数は、分解レベル２では分解レベル１の半分となり、分解レベル３では分解レベル２の半分となり）、処理時間が異なることを表している。

２番目のプレシンクトに対する分析フィルタ処理が終了した時点で、図２１および図２２の一点鎖線で囲まれている領域内の係数Ｃ７乃至Ｃ１２、Ｃ１５乃至Ｃ２０、Ｃ２４、および、Ｃ２５が係数並び替え用バッファ部１４１に格納され、点線で囲まれている領域内の係数Ｃ５およびＣ６が、エントロピ符号化部１２３に供給された状態となる。

図２４は、２番目のプレシンクトに対する分析フィルタ処理が終了した時点の係数並び替え用バッファ部１４１の状態を模式的に示している。２番目のプレシンクトに対する分析フィルタ処理が終了した時点で、１番目のプレシンクトに対する分析フィルタ処理において生成された係数データのうち、１回目の合成フィルタ処理において処理対象とならない係数データ、および、２番目のプレシンクトに対する分析フィルタ処理において生成された係数データが、生成された順に係数並び替え用バッファ部１４１に格納される。具体的には、係数Ｃ８，係数Ｃ９，係数Ｃ１１，係数Ｃ１２，係数Ｃ７，係数Ｃ１６，係数Ｃ１７，係数Ｃ１０，係数Ｃ１９，係数Ｃ２０，係数Ｃ１５，係数Ｃ２４，係数Ｃ２５，係数Ｃ１８の順に係数並び替え用バッファ部１４１に格納される。なお、係数Ｃ３は、１番目のプレシンクトに対する符号化処理においてエントロピ符号化され、係数並び替え用バッファ部１４１から消去されるが、未処理の係数Ｃ８およびＣ９より生成された順序が遅いため、係数並べ替え用バッファ部１４１に領域だけが確保された状態となる。

エントロピ符号化は、２回目の合成フィルタ処理において処理される係数データに対して処理される順に行われるため、係数Ｃ７乃至Ｃ１２の順に係数並び替え用バッファ部１４１から係数データが読み出され、エントロピ符号化部１２３に供給される。そして、係数Ｃ５乃至Ｃ１２に対して順番にエントロピ符号化が行われ、符号化データVLC５乃至VLC１２が生成され、コードストリームとして復号部に送出される。

このようにして、合成処理（逆ウェーブレット変換処理）において処理される順に係数データを並び替えて符号化し、復号側に供給することができ、復号処理による遅延時間を短縮することができる。

また、生成順に係数データを係数並び替え用バッファ部１４１に書き込めばよいため、書込み処理を単純化することができる。

以上の説明では、係数並び替え用バッファ部から読み出すときに係数データの並び替えを行うようにしたが、係数並び替え用バッファ部に書き込むときに係数データを並び替えるようにしてもよい。

図２５は、係数並び替え用バッファ部に書き込むときに係数データを並び替えるようにした場合の符号化装置の一実施の形態を示すブロック図である。なお、図中、図１９と対応する部分については下２桁が同じ符号を付してあり、処理が同じ部分に関しては、その説明は繰り返しになるので省略する。また、図中、図１９と同様に、SPU２１１内部、および、SPU２１１とローカルストア２１２との間の方が、ローカルストア２１２とメインメモリ２１３との間よりも、データ転送が高速に行われ、レイテンシが短いことを示すために、SPU２１１内部、および、SPU２１１とローカルストア２１２との間の矢印の線が、ローカルストア２１２とメインメモリ２１３との間の矢印の線より太く示されている。

この符号化装置２０１は、SPU２１１、ローカルストア２１２、メインメモリ２１３、および、メモリコントローラ２１４により構成される。

SPU２１１は、所定のプログラムを実行することにより、ウェーブレット変換部２２１、係数並び替え部２２２、および、エントロピ符号化部２２３の機能を実現する。

ウェーブレット変換部２２１は、図１９のウェーブレット変換部１２１と異なり、生成した係数データを係数並び替え部２２２に供給する。

係数並び替え部２２２は、図２６を参照して後述するように、最終レベルの分析フィルタ処理により生成された係数データを除いて、合成処理において処理される順に係数データを並び替えて、ライトバッファ２３３を介して、係数並び替え用バッファ部２４１に書き込む。また、係数並び替え部２２２は、最終レベルの分析フィルタ処理により生成された係数データを、係数並び替え用バッファ部２４１に書き込まずにエントロピ符号化部２２３に供給する。

エントロピ符号化部２２３は、図２６を参照して後述するように、リードバッファ２３４を介して、係数並び替え用バッファ部２４１に格納されている係数データを格納順に読み出す。エントロピ符号化部２２３は、取得した係数データをエントロピ符号化し、その結果得られた符号化データを、ライトバッファ２３５を介して、メインメモリ２１３に書き込む。

ローカルストア２１２には、図１９のローカルストア１１２と同様に、リードバッファ２３１、途中計算用バッファ部２３２、ライトバッファ２３３、リードバッファ２３４、および、ライトバッファ２３５が配置される。

メインメモリ２１３には、図１９のメインメモリ１１３と同様に、係数並び替え用バッファ部２４１が配置される。

次に、図２６のフローチャートを参照して、符号化装置２０１により実行される符号化処理の流れの例を説明する。

ステップＳ３１乃至Ｓ３４の処理は、上述した図２０のステップＳ１乃至Ｓ４の処理と同様であり、その説明は繰り返しになるので省略する。

ステップＳ３５において、分析フィルタリングが最終レベルまで終了していないと判定された場合、処理はステップＳ３６に進む。

ステップＳ３６において、係数並び替え部２２２は、高域サブバンドの係数データを合成処理を行う順に並び替えながらバッファに書き込む。具体的には、ウェーブレット変換部２２１は、現在の分解レベルの高域サブバンド（ＨＬ,ＬＨ,ＨＨ）の係数データを係数並び替え部２２２に供給する。係数並び替え部２２２は、取得した高域サブバンドの各係数データについて、合成処理において処理される順に配置するための係数並び替え用バッファ部２４１の格納位置を算出する。係数並び替え部２２２は、取得した高域サブバンドの係数データを生成順にライトバッファ２３３に書き込み、ライトバッファ２３３に書き込んだ係数データを、算出した係数並び替え用バッファ部２４１の格納位置に書き込むようにメモリコントローラ２１４に要求する。

メモリコントローラ２１４は、ライトバッファ２３３に書き込まれた各係数データを、指示された係数並び替え用バッファ部２４１の格納位置に書き込むように制御する。すなわち、合成処理において処理される順に係数データが並び替えられて係数並び替え用バッファ部２４１に書き込まれる。メモリコントローラ２１４は、係数並び替え用バッファ部２４１に書き込まれた各係数データの格納位置を示す情報をエントロピ符号化部２２３に供給する。エントロピ符号化部２２３は、各係数データの格納位置を記憶する。メモリコントローラ２１４は、係数並び替え用バッファ部２４１に転送された係数データをライトバッファ２３３から消去する。

その後、処理はステップＳ３３に戻り、ステップＳ３５において、分析フィルタリングが最終レベルまで終了したと判定されるまで、ステップＳ３３乃至Ｓ３６の処理が繰り返し実行される。すなわち、現在の分解レベルに対して、分析フィルタリングが繰り返され、得られた高域サブバンドの係数データが、合成処理において処理される順に並び替えられて係数並び替え用バッファ部２４１に書き込まれる。

一方、ステップＳ３５において、分析フィルタリングが最終レベルまで終了したと判定された場合、処理はステップＳ３７に進む。

ステップＳ３７において、上述した図２３のステップＳ７の処理と同様に、最終レベルの係数データが、ウェーブレット変換部２２１から、係数並び替え部２２２を介してエントロピ符号化部２２３に供給される。

ステップＳ３８において、エントロピ符号化部２２３は、供給された係数データを、ライン毎にエントロピ符号化する。

ステップＳ３９において、上述した図２０のステップＳ９の処理と同様に、符号化データが送出される。

ステップＳ４０において、上述した図２０のステップＳ１０の処理と同様に、Ａ番目のプレシンクトの符号化が終了したかが判定され、Ａ番目のプレシンクトの符号化が終了していないと判定された場合、処理はステップＳ４１に進む。

ステップＳ４１において、エントロピ符号化部２２３は、次に処理する係数データを読み出す。具体的には、エントロピ符号化部２２３は、係数並び替え用バッファ部２４１の先頭に配置されている係数データをリードバッファ２３４に転送するようにメモリコントローラ２１４に要求する。メモリコントローラ２１４は、要求された係数データを係数並び替え用バッファ部２４１からリードバッファ２３４に転送し、転送した係数データを係数並び替え用バッファ部２４１から消去する。エントロピ符号化部２２３は、リードバッファ２３４に格納された係数データを読み出す。

さらに、エントロピ符号化部２２３は、係数並び替え用バッファ部２４１において今回読み出した係数データの次に配置されている係数データを、係数並び替え用バッファ部２４１からリードバッファ２３４に転送するようにメモリコントローラ２１４に要求する。メモリコントローラ２１４は、要求された係数データを係数並び替え用バッファ部２４１からリードバッファ２３４に転送し、転送した係数データを係数並び替え用バッファ部２４１から消去する。すなわち、次にエントロピ符号化される係数データが係数並び替え用バッファ部１４１からリードバッファ１３４に先読みされる。

以降、ステップＳ４１において、エントロピ符号化部２２３により、次にエントロピ符号化される係数データがリードバッファ２３４から読み出されるとともに、その次にエントロピ符号化される係数データが係数並び替え用バッファ部２４１からリードバッファ２３４に先読みされる。これにより、係数並び替え用バッファ部２４１からリードバッファ２３４へのデータ転送により生じるSPU２１１の待ち時間を短縮することができる。

その後、ステップＳ４０において、Ａ番目のプレシンクトの符号化が終了したと判定されるまで、ステップＳ３８乃至Ｓ４１の処理が繰り返し実行され、合成処理において処理される順に係数データがエントロピ符号化され、その結果得られた符号化データが送出される。

一方、ステップＳ４０において、Ａ番目のプレシンクトの符号化が終了したと判定された場合、処理はステップＳ４２に進む。

ステップＳ４２以降の処理は、上述した図２０のステップＳ２２以降の処理と同様であり、その説明は繰り返しになるので省略する。

図２７は、図２４と同様に、５×３フィルタのリフティングによるフィルタ処理を分解レベル＝３まで実行した場合の、２番目のプレシンクトに対する分析フィルタ処理が終了した時点の係数並び替え用バッファ部２４１の状態を模式的に示している。

２番目のプレシンクトに対する分析フィルタ処理が終了した時点で、係数並び替え用バッファ部２４１には、係数Ｃ７乃至Ｃ１２、係数Ｃ１５乃至Ｃ２０、係数Ｃ２４および係数Ｃ２５が、合成処理において処理される順に格納されている。なお、係数Ｃ２３は、３番目のプレシンクトに対する分析フィルタ処理で生成されるため、その領域だけが確保されている。

このようにして、合成処理（逆ウェーブレット変換処理）において処理される順に係数データを並び替えて符号化し、復号側に供給することができ、復号側に供給することができ、復号処理による遅延時間を短縮することができる。

また、係数データを格納されている順に係数並び替え用バッファ部２４１から読み込めばよいため、読み出し処理を単純化することができ、係数データの先読み処理等が容易になる。

ところで、符号化装置１０１においては、係数並び替え用バッファ部１４１から係数データを読み出すとき、合成処理において処理される順に読み出すために、読み出し位置が不連続となり、例えば、各係数データの格納位置を管理したり、次に読み出す係数データの格納位置を求めたりするための演算処理により、SPU１１１の負荷が増大し、処理速度が遅くなる。また、係数データの水平方向のサイズは分解レベルによって異なるため、係数データを不連続に読み出し消去する処理が繰り返されることにより、係数並び替え用バッファ部１４１においてフラグメントが発生してしまう場合がある。

また、符号化装置２０１においては、係数並び替え用バッファ部２４１に係数データを書き込むとき、合成処理において処理される順に書き込むために、書き込み位置が不連続となり、各係数データの書き込み位置を求めるための演算処理により、SPU２１１の負荷が増大し、処理速度が遅くなる。また、係数データの水平方向のサイズは分解レベルによって異なるため、係数データを不連続に書き込み消去する処理が繰り返されることにより、係数並び替え用バッファ部２４１においてフラグメントが発生してしまう場合がある。

さらに、以上の説明では、簡単のため５×３フィルタを用いて分解レベル＝３まで分析フィルタ処理を行う例を示したが、例えば、９×７フィルタを用いて分解レベル＝４まで分析フィルタ処理を行うなど、フィルタのサイズを大きくしたり、分解レベル数を増やしたりすると、並び替えの処理はより複雑になり、さらにSPU１１１またはSPU２１１の負荷が増大し、処理時間が長くなる。

また、入力画像データのサイズ、フィルタの種類、分解レベル数を可変とした場合、その組み合わせによって係数データの並び替えのパターンが異なるため、全てのパターンに対応した係数並び替え部１２２または係数並び替え部２２２のプログラムのサイズは大きくなってしまう。

ここで、図２３に戻り、分析フィルタ処理において生成される係数データを分解レベルごとに分けて見た場合、分解レベル１では、係数Ｃ１９、係数Ｃ２０、係数Ｃ２４、係数Ｃ２５の順に係数データが生成され、分解レベル２では、係数Ｃ１５、係数Ｃ１８の順に係数データが生成されている。すなわち、分解レベル単位では、合成フィルタ処理において処理される順に係数データが生成される。

このように、分析フィルタ処理においては、画像サイズ、フィルタの種類、分解レベル数等の条件に関わらず、サブバンド単位では、分析フィルタ処理において生成される係数データの順序と、合成フィルタ処理において処理される係数データの順序とが逆転することがないという特徴を有する。

図２８は、この特徴を利用して、係数並び替え用バッファ部に係数データをサブバンド毎に分割して書き込むようにした場合の符号化装置の一実施の形態を示すブロック図である。なお、図中、図１９と対応する部分については下２桁が同じ符号を付してあり、処理が同じ部分に関しては、その説明は繰り返しになるので省略する。また、図中、図１９および図２５と同様に、SPU３１１内部、および、SPU３１１とローカルストア３１２との間の方が、ローカルストア３１２とメインメモリ３１３との間よりも、データ転送が高速に行われ、レイテンシが短いことを示すために、SPU３１１内部、および、SPU３１１とローカルストア３１２との間の矢印の線が、ローカルストア３１２とメインメモリ３１３との間の矢印の線より太く示されている。

この符号化装置３０１は、SPU３１１、ローカルストア３１２、メインメモリ３１３、および、メモリコントローラ３１４により構成される。

SPU３１１は、所定のプログラムを実行することにより、ウェーブレット変換部３２１、および、エントロピ符号化部３２３の機能を実現する。

ウェーブレット変換部３２１は、図１９のウェーブレット変換部１２１と異なり、図３０などを参照して後述するように、ライトバッファ３３３−１乃至３３３−ｍを介して、生成した係数データをサブバンド毎に領域を分けて係数並び替え用バッファ部３４１に書き込む。また、ウェーブレット変換部３２１は、最終レベルの分析フィルタ処理により生成した係数データを、係数並び替え用バッファ部３４１に書き込まずに、エントロピ符号化部３２３に直接供給する。

エントロピ符号化部３２３は、図３０などを参照して後述するように、リードバッファ３３４−１乃至３３４−mを介して、サブバンド毎に領域が分かれて格納されている係数データを係数並び替え用バッファ部３４１から読み出す。エントロピ符号化部３２３は、取得した係数データをエントロピ符号化し、その結果得られた符号化データを、ライトバッファ３３５を介して、メインメモリ３１３に書き込む。

ローカルストア３１２には、図１９のローカルストア１１２と同様に、リードバッファ３３１、途中計算用バッファ部３３２、および、ライトバッファ３３５が配置され、ライトバッファ２３３の代わりにライトバッファ３３３−１乃至３３３−ｍが配置され、リードバッファ２３４の代わりにリードバッファ３３４−１乃至３３４−ｍが配置される。なお、以下、ライトバッファ３３３−１乃至３３３−ｍを個々に区別する必要がない場合、単にライトバッファ３３３と称し、リードバッファ３３４−１乃至３３４−ｍを個々に区別する必要がない場合、単にリードバッファ３３４と称する。

メインメモリ３１３には、図１９のメインメモリ１１３と同様に、係数並び替え用バッファ部３４１が配置される。係数並び替え用バッファ部３４１には、図２９に示されるように、ライトバッファ３３３およびリードバッファ３３４と同じ数のリングバッファ３５１−１乃至３５１−mが配置される。なお、以下、リングバッファ３５１−１乃至３５１−ｍを個々に区別する必要がない場合、単にリングバッファ３５１と称する。

リングバッファ３５１は、FIFO構造、かつ、バッファの終端の番地の次の番地を先頭の番地とするリング構造のバッファとされる。従って、各リングバッファ３５１の領域をリング状に繰り返し再利用することができ、メモリサイズを必要最小限に抑えることができる。なお、各リングバッファ３５１に必要な容量は、図１７および図１８を参照して上述した算出方法により容易に算出することができる。

ライトバッファ３３３、リードバッファ３３４、および、リングバッファ３５１は、最終レベル以外の各分解レベルにおける各高域サブバンド（ＨＬ,ＬＨ,ＨＨ）について１つずつ設けられる。例えば、分解レベル数が３の場合、最終レベルである分解レベル３以外の分解レベル１および２において生成される合計６個の高域サブバンドについて、それぞれ１つずつライトバッファ３３３、リードバッファ３３４、および、リングバッファ３５１が設けられる。

ウェーブレット変換部３２１は、各リングバッファ３５１について、直前に書き込んだ最新の係数データの終端の位置を示す終端Ｅへのポインタを管理している。ウェーブレット変換部３２１は、リングバッファ３５１に係数データを書き込む場合、その係数データが属するサブバンドに対応するライトバッファ３３３に係数データを書き込み、ライトバッファ３３３に書き込んだ係数データを対応するリングバッファ３５１の終端Ｅの次の領域ＥＮに書き込むようにメモリコントローラ３１４要求する。メモリコントローラ３１４は、ライトバッファ３３３に書き込まれた係数データを、指示されたリングバッファ３５１の領域ＥＮに書き込むように制御する。メモリコントローラ３１４は、係数データを書き込んだリングバッファ３５１の領域ＥＮの終端の位置をウェーブレット変換部３２１およびエントロピ符号化部３２３に通知する。ウェーブレット変換部３２１は、リングバッファ３５１の終端Ｅへのポインタを領域ＥＮの終端に移動する。

また、エントロピ符号化部３２３は、各リングバッファ３５１について、最も過去に書き込まれた最古の係数データの先頭の位置を示す先頭Ｈへのポインタを管理している。エントロピ符号化部３２３は、リングバッファ３５１から係数データを読み出す場合、リングバッファ３５１の先頭Ｈに格納されている係数データの転送をメモリコントローラ３１４に要求する。メモリコントローラ３１４は、要求された係数データをリングバッファ３５１の先頭Hから読み出し、対応するリードバッファ３３４に転送し、転送した係数データをリングバッファ３５１から消去するように制御する。エントロピ符号化部３２３は、転送された係数データをリードバッファ３３４から読み出す。メモリコントローラ３１４は、転送した係数データの次の係数データが格納されている領域ＨＮの先頭の位置をエントロピ符号化部３２３に通知する。エントロピ符号化部３２３は、リングバッファ３５１の先頭Ｈへのポインタを領域ＨＮの先頭に移動する。

なお、先頭Ｈおよび終端Ｅの位置は、リングバッファ３５１の末尾まで移動した後、リングバッファ３５１の先頭に移動する。

次に、図３０のフローチャートを参照して、符号化装置３０１により実行される符号化処理の流れについて説明する。

ステップＳ６１乃至Ｓ６４の処理は、上述した図２０のステップＳ１乃至Ｓ４の処理と同様であり、その説明は繰り返しになるので省略する。

ステップＳ６５において、分析フィルタリングが最終レベルまで終了していないと判定された場合、処理はステップＳ６６に進む。

ステップＳ６６において、ウェーブレット変換部３２１は、高域サブバンドの係数データをサブバンド毎に分けてバッファに書き込む。具体的には、ウェーブレット変換部３２１は、現在の分解レベルの高域サブバンド（ＨＬ,ＬＨ,ＨＨ）の係数データを、各係数データが属するサブバンドに対応するライトバッファ３３３に書き込む。ウェーブレット変換部３２１は、ライトバッファ３３３に書き込んだ係数データを、対応するリングバッファ３５１の終端Ｅの次の領域ＥＮに書き込むようにメモリコントローラ３１４に要求する。メモリコントローラ３１４は、ライトバッファ３３３に書き込まれた係数データを、指示されたリングバッファ３５１の領域ＥＮに書き込むように制御する。メモリコントローラ３１４は、係数データを書き込んだリングバッファ３５１の領域ＥＮの終端の位置をウェーブレット変換部３２１およびエントロピ符号化部３２３に通知する。ウェーブレット変換部３２１は、リングバッファ３５１の終端Ｅへのポインタを領域ＥＮの終端に移動する。

これにより、係数データが、サブバンド毎に分けられて、生成順に並べられて各リングバッファ３５１に書き込まれる。また、ライトバッファ１３３からリングバッファ３５１へのデータ転送により生じるSPU３１１の待ち時間を短縮することができる。

その後、処理はステップＳ６３に戻り、ステップＳ６５において、分析フィルタリングが最終レベルまで終了したと判定されるまで、ステップＳ６３乃至Ｓ６６の処理が繰り返し実行される。これにより、現在の分解レベルに対して、分析フィルタリングが繰り返され、得られた高域サブバンドの係数データが、サブバンド毎に分けられて、生成順に係数並び替え用バッファ部３４１のリングバッファ３５１に書き込まれる。すなわち、高域サブバンドの係数データが、サブバンド毎に領域が分かれて係数並び替え用バッファ部３４１に格納される。

一方、ステップＳ６５において、分析フィルタリングが最終レベルまで終了したと判定された場合、処理はステップＳ６７に進む。

ステップＳ６７において、ウェーブレット変換部３２１は、最終レベルの係数データを供給する。すなわち、ウェーブレット変換部３２１は、最終レベルの分析フィルタリングにより生成された係数データを、係数並び替え用バッファ部３４１に書き込まずに、エントロピ符号化部３２３に直接供給する。

なお、最終レベルの係数データのうち高域の係数データは、後のプレシンクト処理において使用されるため、途中計算用バッファ部３３２に格納される。

ステップＳ６８において、エントロピ符号化部３２３は、供給された係数データを、ライン毎にエントロピ符号化する。

ステップＳ６９において、上述した図２０のステップＳ９の処理と同様に、符号化データが送出される。

ステップＳ７０において、上述した図２０のステップＳ１０の処理と同様に、Ａ番目のプレシンクトの符号化が終了したかが判定され、Ａ番目のプレシンクトの符号化が終了していないと判定された場合、処理はステップＳ７１に進む。

ステップＳ７１において、エントロピ符号化部３２３は、次に処理する係数データを読み出す。具体的には、エントロピ符号化部３２３は、直前に符号化された係数データの次に合成処理において処理される係数データを、その係数データが属するサブバンドに対応するリングバッファ３５１の先頭Ｈから読み出し、リードバッファ３３４に転送するようにメモリコントローラ３１４に要求する。メモリコントローラ３１４は、要求された係数データをリングバッファ３５１から対応するリードバッファ３３４に転送し、転送した係数データをリングバッファ３５１から消去するように制御する。エントロピ符号化部３２３は、転送された係数データをリードバッファ３３４から読み出す。メモリコントローラ３１４は、転送した係数データの次の係数データが格納されている領域ＨＮの先頭の位置をエントロピ符号化部３２３に通知する。エントロピ符号化部３２３は、リングバッファ３５１の先頭Ｈへのポインタを領域ＨＮの先頭に移動する。

さらに、エントロピ符号化部３２３は、ポインタを移動したリングバッファ３５１の先頭Ｈに格納されている係数データの転送をメモリコントローラ３１４に要求する。メモリコントローラ３１４は、要求された係数データをリングバッファ３５１から対応するリードバッファ３３４に転送し、転送した係数データをリングバッファ３５１から消去するように制御する。これにより、サブバンド毎に、次にエントロピ符号化される係数データがリングバッファ３５１からリードバッファ３３４に先読みされる。メモリコントローラ３１４は、転送した係数データの次の係数データが格納されている領域ＨＮの先頭の位置をエントロピ符号化部３２３に通知する。エントロピ符号化部３２３は、リングバッファ３５１の先頭Ｈへのポインタを領域ＨＮの先頭に移動する。

以降、ステップＳ７１において、エントロピ符号化部３２３により、次にエントロピ符号化される係数データがリードバッファ３３４から読み出されるとともに、読み出された係数データと同じサブバンドに属する係数データであって、読み出された係数データの次に生成された係数データ、すなわち、そのサブバンド内において次にエントロピ符号化される係数データがリングバッファ３５１からリードバッファ３３４に先読みされる。これにより、リングバッファ３５１からリードバッファ３３４へのデータ転送により生じるSPU３１１の待ち時間を短縮することができる。

その後、ステップＳ７０において、Ａ番目のプレシンクトの符号化が終了したと判定されるまで、ステップＳ６８乃至Ｓ７１の処理が繰り返し実行され、合成処理において処理される順に係数データが係数並び替え用バッファ部３４１から読み出され、エントロピ符号化され、その結果得られた符号化データが送出される。

一方、ステップＳ７０において、Ａ番目のプレシンクトの符号化が終了したと判定された場合、処理はステップＳ７２に進む。

ステップＳ７２以降の処理は、上述した図２０のステップＳ２２以降の処理と同様であり、その説明は繰り返しになるので省略する。

図３１は、図２４および図２７と同様に、５×３フィルタのリフティングによるフィルタ処理を分解レベル＝３まで実行した場合の、２番目のプレシンクトに対する分析フィルタ処理が終了した時点の係数並び替え用バッファ部３４１の状態を模式的に示している。なお、図３１では、図２４および図２７と同様に、説明の簡略化のため、水平方向の分析フィルタ処理についての記載は省略している。従って、分解レベル数が３の場合、実際には、上述したように６個のリングバッファが係数並び替え用バッファ部３４１に設けられるが、図３１では、そのうちの分解レベル１の高域サブバンドの１つに対応するリングバッファＡ、および、分解レベル２の高域サブバンドの１つに対応するリングバッファＢのみが図示されている。

２番目のプレシンクトに対する分析フィルタ処理が終了した時点で、分解レベル１のウェーブレット変換より生成された係数データが、係数Ｃ８，係数Ｃ９，係数Ｃ１１，係数Ｃ１２，係数Ｃ１６，係数Ｃ１７，係数Ｃ１９，係数Ｃ２０，係数Ｃ２４，係数Ｃ２５の順にリングバッファＡに格納され、分解レベル２のウェーブレット変換より生成された係数データが、係数Ｃ７，係数Ｃ１０，係数Ｃ１５，係数Ｃ１８の順にリングバッファＢに格納されている。

図３２は、図２１乃至図２３および図３１に対応して、５×３フィルタのリフティングによるフィルタ処理を分解レベル＝３まで実行した場合の、２番目のプレシンクトに対する符号化処理の流れを模式的に示した図である。

なお、図３２は、図２１の領域Ｄ１４内のリフティング演算以降の処理について示している。また、図内中央の右向きの矢印は時間軸を表している。さらに、実線の下向きの矢印は、SPU３１１とローカルストア３１２との間で行われるデータ転送（一部、SPU３１１内のデータ転送を含む）であるローカルストア転送を示し、点線の右斜め下向きの矢印は、ローカルストア３１２とメインメモリ３１３との間で行われるデータ転送であるメインメモリ転送を示している。なお、ローカルストア転送とメインメモリ転送の転送時間の差を強調するために、ローカルストア転送は、転送時間がほぼ０となるように時間軸に対してほぼ垂直な矢印により表され、メインメモリ転送は、ローカルストア転送より転送時間を要することを表すように右斜め下向きの矢印により表されている。

また、ライトバッファＡ、リングバッファＡ、リードバッファＡは、分解レベル１の分析フィルタ処理により生成される係数データが格納され、ライトバッファＢ、リングバッファＢ、リードバッファＢは、分解レベル２の分析フィルタ処理により生成される係数データが格納されるものとする。

時間軸に沿って処理の流れを説明すると、まず、ウェーブレット変換部３２１は、領域Ｄ１４内の分解レベル１の分析フィルタ処理を行い、係数Ｃ２５を生成し、ライトバッファＡに書き込み、リングバッファＡへの転送をメモリコントローラ３１４に要求する。次に、ウェーブレット変換部３２１は、メモリコントローラ３１４によりライトバッファＡからリングバッファＡに係数Ｃ２５が転送されるのに並行して、領域Ｄ１４内の分解レベル２の分析フィルタ処理を行い、係数Ｃ１８を生成し、ライトバッファＢに書き込み、リングバッファＢへの転送をメモリコントローラ３１４に要求する。そして、ウェーブレット変換部３２１は、メモリコントローラ３１４によりライトバッファＢからリングバッファＢに係数Ｃ１８が転送されるのに並行して、領域Ｄ１４内の分解レベル３の分析フィルタ処理を行い、係数Ｃ５およびＣ６を生成し、エントロピ符号化部３２３に供給する。

エントロピ符号化部３２３は、係数Ｃ５およびＣ６をエントロピ符号化し、その結果得られた符号化データVLC５およびVLC６を送出する。

次に、エントロピ符号化部３２３は、１番目のプレシンクトに対する分析フィルタ処理においてリードバッファＢに格納されている係数データＣ７を読み出し、リングバッファＢの先頭Ｈに格納されている係数Ｃ１０の転送をメモリコントローラ３１４に要求する。エントロピ符号化部３２３は、メモリコントローラ３１４によりリングバッファＢからリードバッファＢに係数Ｃ１０が転送されるのに並行して、係数Ｃ７をエントロピ符号化し、その結果得られた符号化データVLC７を送出する。

次に、エントロピ符号化部３２３は、１番目のプレシンクトに対する分析フィルタ処理においてリードバッファＡに格納されている係数Ｃ８を読み出し、リングバッファＡの先頭Ｈに格納されている係数Ｃ９の転送をメモリコントローラ３１４に要求する。エントロピ符号化部３２３は、メモリコントローラ３１４によりリングバッファＡからリードバッファＡに係数Ｃ９が転送されるのに並行して、係数Ｃ８をエントロピ符号化し、その結果得られた符号化データVLC８を送出する。

次に、エントロピ符号化部３２３は、係数Ｃ９をリードバッファＡから読み出し、リングバッファＡにおいて係数Ｃ９が格納されていた位置の次の位置に格納されている係数Ｃ１１の転送をメモリコントローラ３１４に要求する。エントロピ符号化部３２３は、メモリコントローラ３１４によりリングバッファＡからリードバッファＡに係数Ｃ１１が転送されるのに並行して、係数Ｃ９をエントロピ符号化し、その結果得られた符号化データVLC９を送出する。

次に、エントロピ符号化部３２３は、係数Ｃ１０をリードバッファＢから読み出し、リングバッファＢにおいて係数Ｃ１０が格納されていた位置の次の位置に格納されている係数Ｃ１５の転送をメモリコントローラ３１４に要求する。エントロピ符号化部３２３は、メモリコントローラ３１４によりリングバッファＢからリードバッファＢに係数Ｃ１５が転送されるのに並行して、係数Ｃ１０をエントロピ符号化し、その結果得られた符号化データVLC１０を送出する。

次に、エントロピ符号化部３２３は、係数Ｃ１１をリードバッファＡから読み出し、リングバッファＡにおいて係数Ｃ１１が格納されていた位置の次の位置に格納されている係数Ｃ１２の転送をメモリコントローラ３１４に要求する。エントロピ符号化部３２３は、メモリコントローラ３１４によりリングバッファＡからリードバッファＡに係数Ｃ１２が転送されるのに並行して、係数Ｃ１１をエントロピ符号化し、その結果得られた符号化データVLC１１を送出する。

次に、エントロピ符号化部３２３は、係数Ｃ１２をリードバッファＡから読み出し、リングバッファＡにおいて係数Ｃ１２が格納されていた位置の次の位置に格納されている係数Ｃ１３の転送をメモリコントローラ３１４に指示する。エントロピ符号化部３２３は、メモリコントローラ３１４によりリングバッファＡからリードバッファＡに係数Ｃ１３が転送されるのに並行して、係数Ｃ１２をエントロピ符号化し、その結果得られた符号化データVLC１２を送出し、２番目のプレシンクトに対する符号化処理が終了する。

このようにして、合成処理（逆ウェーブレット変換処理）において処理される順に係数データを並び替えて符号化し、復号側に供給することができ、復号処理による遅延時間を短縮することができる。

また、サブバンド毎に分けて各リングバッファ３５１に生成された順に係数データを書き込み、リングバッファ３５１を選択しながら書き込まれた順に係数データを読み出すだけで、合成処理において処理される順に係数データを並び替えることができるので、係数データの書き込み位置または読み出し位置の演算処理を軽減することができる。その結果、SPU３１１の負荷を軽減し、処理速度を早くすることができ、符号化処理による遅延時間を短縮することができる。

さらに、係数データがサブバンド毎に各リングバッファ３５１に分かれて格納されるので、各リングバッファ３５１内に格納される係数データの水平方向のサイズが統一され、係数並び替え用バッファ部３４１においてフラグメントの発生を抑制することができ、メモリの使用効率を向上させることができる。

また、図３２を参照して上述したように、ローカルストア３１２とメインメモリ３１３との間のデータ転送により生じるSPU３１１の待ち時間を短縮することができ、処理時間を短縮することができ、符号化処理による遅延時間を短縮することができる。

なお、ライトバッファ３３３−１乃至３３３−ｍとリングバッファ３５１−１乃至３５１−ｍ間のデータ転送、および、リードバッファ３３４−１乃至３３４−ｍとリングバッファ３５１−１乃至３５１−ｍ間のデータ転送、換言すれば、同じサブバンドに対応するライトバッファ３３３とリングバッファ３５１間のデータ転送、および、同じサブバンドに対応するリングバッファ３５１とリードバッファ３３４間のデータ転送を、それぞれ別のチャンネルを利用して並行して実行できるようにすることが望ましい。これにより、各サブバンドの係数データの転送が並列に行われるようになり、係数データの転送により生じるSPU３１１の待ち時間をより短縮することができる。

次に、図１の符号化部１０に対応する復号部について説明する。図３３は、復号部の一実施の形態を示すブロック図である。図３３に示される復号部４０１は、ソフトウェアプログラムにより構成され、画像データが符号化された符号化データを復号して画像データを復元するソフトウェアデコーダが所定の情報処理装置のCPUにより実行されることにより実現される機能を模式的に示したものである。図３３に示されるように、復号部４０１は、エントロピ復号部４１１、係数バッファ部４１２、およびウェーブレット逆変換部４１３の機能を有する。

エントロピ復号部４１１は、供給された符号化データをエントロピ符号化部２３による符号化方法に対応する復号方法で復号し、係数データを得る。その係数データは、係数バッファ部４１２に格納される。ウェーブレット逆変換部４１３は、係数バッファ部４１２に格納された係数データを用いて、合成フィルタによる合成フィルタ処理（ウェーブレット逆変換）を行い、合成フィルタ処理の結果を再び係数バッファ部４１２に格納する。ウェーブレット逆変換部４１３は、この処理を分解レベルに応じて繰り返して、復号された画像データ（出力画像データ）を得ると、それを外部に出力する。

次に、図３４のフローチャートを参照して、復号部４０１により実行される復号処理の流れの例を説明する。

復号処理が開始されると、エントロピ復号部４１１は、ステップＳ１０１において、復号部４０１の外部より供給される符号化データを取得し、ステップＳ１０２において、ライン毎に符号化データをエントロピ復号する。

ステップＳ１０３において、係数バッファ部４１２は、復号された係数データを保持する。

ステップＳ１０４において、ウェーブレット逆変換部４１３は、係数バッファ部４１２に１プレシンクト分の係数データが蓄積されたか否かを判定する。１プレシンクト分の係数データが蓄積されていないと判定された場合、処理は、ステップＳ１０１に戻り、それ以降の処理が実行される。つまり、ウェーブレット逆変換部４１３は、係数バッファ部４１２に１プレシンクト分の係数データが蓄積されるまで待機する。

ステップＳ１０４において、１プレシンクト分の係数データが蓄積されたと判定された場合、処理はステップＳ１０５に進む。

なお、上述したように、符号化部１０（または、符号化装置１０１、符号化装置２０１、もしくは、符号化装置３０１）からは係数データが逆ウェーブレット変換において処理される順に並び替えられて復号部４０１に供給されるので、係数バッファ部４１２には、１プレシンクト分の係数データが逆ウェーブレット変換において処理される順に並べられて格納される。

ステップＳ１０５において、ウェーブレット逆変換部４１３は、係数バッファ部４１２に保持されている係数データを１プレシンクト分読み出し、ステップＳ１０６において、その読み出した係数データに対して、画面垂直方向に並ぶ係数データに対して合成フィルタリング処理を行う垂直合成フィルタリング処理を行い、ステップＳ１０７において、画面水平方向に並ぶ係数データに対して合成フィルタリング処理を行う水平合成フィルタリング処理を行う。

なお、上述したように、係数バッファ部４１２には、１プレシンクト分の係数データが逆ウェーブレット変換において処理される順に並べられて格納されており、ウェーブレット逆変換部４１３は、係数データを格納されている順に係数バッファ部４１２から読み出せばよく、係数データの並び替えを行う必要がないため、ウェーブレット逆変換処理による遅延時間を短縮することができる。

ステップＳ１０８において、ウェーブレット逆変換部４１３は、合成フィルタリング処理がレベル１（分解レベルの値が「１」のレベル）まで終了したか否か、すなわち、ウェーブレット変換前の状態まで逆変換したか否かを判定する。レベル１まで達していないと判定された場合、処理はステップＳ１０６に戻り、ステップＳ１０６およびステップＳ１０７のフィルタリング処理が繰り返される。

ステップＳ１０８において、レベル１までウェーブレット逆変換処理が終了されたと判定した場合、処理はステップＳ１０９に進む。

ステップＳ１０９において、ウェーブレット逆変換部４１３は、ウェーブレット逆変換処理により得られた画像データを外部に出力する。

ステップＳ１１０において、エントロピ復号部４１１は、復号処理を終了するか否かを判定する。復号処理を終了しないと判定された場合、処理はステップＳ１０１に戻り、それ以降の処理が繰り返される。また、ステップＳ１１０において、プレシンクトが終了するなどして復号処理が終了されると判定した場合、復号処理は終了される。

このようにして、復号処理による遅延時間を短縮することができる。

上述した一連の処理は、ソフトウェアにより実行させることもできるが、ハードウェアにより実行させることもできる。上述したソフトウェアプログラムは、実行可能な装置であればどのような装置において実行させるようにしてもよく、例えば、図３５に示されるようなパーソナルコンピュータにおいて実行させるようにしてもよい。

図３５において、パーソナルコンピュータ５００のCPU５０１は、ROM（Read Only Memory）５０２に記憶されているプログラム、または記憶部５１３からRAM（Random Access Memory）５０３にロードされたプログラムに従って各種の処理を実行する。RAM５０３にはまた、CPU５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。

CPU５０１、ROM５０２、およびRAM５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５１０も接続されている。

入出力インタフェース５１０には、キーボード、マウスなどよりなる入力部５１１、CRT（Cathode Ray Tube）、LCD（Liquid Crystal Display）などよりなるディスプレイ、並びにスピーカなどよりなる出力部５１２、ハードディスクなどより構成される記憶部５１３、モデムなどより構成される通信部５１４が接続されている。通信部５１４は、例えばインターネットに代表されるネットワークを介しての通信処理を行う。

入出力インタフェース５１０にはまた、必要に応じてドライブ５１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア５２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５１３にインストールされる。

上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、ネットワークや記録媒体からインストールされる。

この記録媒体は、例えば、図３５に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）（登録商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM５０２や、記憶部５１３に含まれるハードディスクなどで構成される。

なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。

また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表すものである。

なお、以上において、１つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて１つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。

以上説明した本発明は、複数の端末間で画像を圧縮して伝送、受信して伸長して画像を出力するシステム、特に低遅延で実現する必要性が高いプロダクツ・アプリケーションに好適である。具体的には、放送局で多用するデジタルトライアックスシステム、ライブ映像配信システム、TV会議システム、監視カメラ・レコーダシステム、医用遠隔医療診断、生徒と教師間のインタラクティブ通信、ビデオゲーム等に応用が可能である。

本発明を適用した符号化部の一実施の形態を示すブロック図である。 ウェーブレット変換について概略的に説明するための略線図である。 ウェーブレット変換について概略的に説明するための略線図である。 ５×３分析フィルタのリフティング構成の例を説明する図である。 ５×３合成フィルタのリフティング構成の例を説明する図である。 ５×３フィルタのリフティングによるフィルタリングを分解レベル＝２まで実行した例を示す図である。 この発明によるウェーブレット変換およびウェーブレット逆変換の流れを概略的に示す図である。 ９×７分析フィルタのリフティング構成の例を説明する図である。 水平方向の係数群に対しての水平分析フィルタリングを、図８のリフティング構成により実行する場合を説明する図である。 係数のラインを上から下方向に順次入力しながら、リフティング構成により水平分析フィルタリングを行う動作を説明する図である。 垂直方向の係数群に対しての垂直分析フィルタリングを、図８のリフティング構成により実行する場合を説明するを示す図である。 ９×７分析フィルタのリフティング構成の他の例を説明する図である。 垂直方向の係数群に対しての垂直合成フィルタリングを、図１２のリフティング構成により実行する場合を説明するを示す図である。 水平方向の係数群に対しての水平合成フィルタリングを、図１２のリフティング構成により実行する場合を説明する図である。 ウェーブレット変換に９×７フィルタを用いた場合の途中計算用バッファ部と係数並び替え用バッファ部のアクセス回数を示す図である。 ウェーブレット変換に５×３フィルタを用いた場合の途中計算用バッファ部と係数並び替え用バッファ部のアクセス回数を示す図である。 ウェーブレット変換に９×７フィルタを用いた場合の途中計算用バッファ部と係数並び替え用バッファ部の必要容量を示す図である。 ウェーブレット変換に５×３フィルタを用いた場合の途中計算用バッファ部と係数並び替え用バッファ部の必要容量を示す図である。 本発明を適用した符号化装置の第１の実施の形態を示すブロック図である。 図１９の符号化装置により実行される符号化処理を説明するためのフローチャートである。 ５×３フィルタのリフティングによるフィルタリングを分解レベル＝３まで実行した例を示す略線図である。 図２１の左側の分析フィルタ側の図に、合成フィルタ側の２番目のプレシンクトに対応する部分を重ねて示した図である。 ２番目のプレシンクトに対する符号化処理の流れを示す図である。 係数並び替え用バッファ部の状態を模式的に示した図である。 本発明を適用した符号化装置の第２の実施の形態を示すブロック図である。 図２５の符号化装置により実行される符号化処理を説明するためのフローチャートである。 係数並び替え用バッファ部の状態を模式的に示した図である。 本発明を適用した符号化装置の第３の実施の形態を示すブロック図である。 図２８の係数並び替え用バッファ部のメモリ構成の例を示す図である。 図２８の符号化装置により実行される符号化処理を説明するためのフローチャートである。 係数並び替え用バッファ部の状態を模式的に示した図である。 ２番目のプレシンクトに対する符号化処理の流れを模式的に示した図である。 復号部の構成例を示すブロック図である。 図３３の復号部により実行される復号処理を説明するためのフローチャートである。 パーソナルコンピュータの構成例を示す図である。

符号の説明

１０ 符号化部， ２１ ウェーブレット変換部， ２２ 係数並び替え部， ２３ エントロピ符号化部， ２４ 途中計算用バッファ部， ２５ 係数並び替え用バッファ部， １０１ 符号化装置， １１１ SPU， １１２ ローカルストア， １１３ メインメモリ， １１４ メモリコントローラ， １２１ ウェーブレット変換部， １２２ 係数並び替え部， １２３ エントロピ符号化部， １３２ 途中計算用バッファ部， １３３ ライトバッファ， １３４ リードバッファ， １４１ 係数並び替え用バッファ部， ２０１ 符号化装置， ２１１ SPU， ２１２ ローカルストア， ２１３ メインメモリ， ２１４ メモリコントローラ， ２２１ ウェーブレット変換部， ２２２ 係数並び替え部， ２２３ エントロピ符号化部， ２３２ 途中計算用バッファ部， ２３３ ライトバッファ， ２３４ リードバッファ， ２４１ 係数並び替え用バッファ部， ３０１ 符号化装置， ３１１ SPU， ３１２ ローカルストア， ３１３ メインメモリ， ３１４ メモリコントローラ， ３２１ ウェーブレット変換部， ３２３ エントロピ符号化部， ３３２ 途中計算用バッファ部， ３３３ ライトバッファ， ３３４ リードバッファ， ３４１ 係数並び替え用バッファ部， ３５１ リングバッファ

Claims (10)

1. 画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行うフィルタ手段と、
   前記係数データを格納する係数格納手段と、
   前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて前記係数格納手段に書き込む書き込み手段と、
   前記係数格納手段の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出す読み出し手段と、
   前記読み出し手段により前記係数格納手段から前記所定順に読み出された前記係数データをエントロピ符号化するエントロピ符号化手段と
   を備える符号化装置。
2. 前記書き込み手段は、前記係数データを前記サブバンド毎に領域を分けて格納する書き込みバッファを介して、前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを前記係数格納手段に書き込み、
   前記読み出し手段は、前記係数データを前記サブバンド毎に領域を分けて格納する読み出しバッファを介して、前記係数格納手段から前記係数データを前記所定順に読み出す
   請求項１に記載の符号化装置。
3. 前記書き込み手段および前記読み出し手段は、前記書き込み手段による前記書き込みバッファの各領域と前記係数格納手段の各領域との間のデータ転送、並びに、前記読み出し手段による前記読み出しバッファの各領域と前記係数格納手段の各領域との間のデータ転送を互いに異なるチャンネルにおいて行う
   請求項２に記載の符号化装置。
4. 前記読み出し手段は、前記エントロピ符号化手段により次に前記エントロピ符号化される前記係数データを、前記係数データに対する前記エントロピ符号化が開始される前に、前記係数格納手段から先読みし、前記読み出しバッファに転送する
   請求項２に記載の符号化装置。
5. 前記フィルタ手段は、リフティング演算を用いて前記分析フィルタ処理を行う
   請求項１に記載の符号化装置。
6. 前記書き込み手段は、前記フィルタ手段による最終の分解レベルの前記分析フィルタ処理により生成された前記係数データを、前記係数格納手段に書き込まずに前記エントロピ符号化手段に供給する
   請求項１に記載の符号化装置。
7. 前記フィルタ手段による前記分析フィルタ処理の途中で発生する中間データを格納する、前記係数格納手段よりもアクセス速度が速い中間データ格納手段をさらに備える
   請求項１に記載の符号化装置。
8. 画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行い、
   前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて係数格納部に書き込み、
   前記係数格納部の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出し、
   前記係数格納部から前記所定順に読み出された前記係数データをエントロピ符号化する
   ステップを含む符号化方法。
9. コンピュータを、
   画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行うフィルタ手段と、
   前記係数データを格納する係数格納手段と、
   前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて前記係数格納手段に書き込む書き込み手段と、
   前記係数格納手段の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出す読み出し手段と、
   前記読み出し手段により前記係数格納手段から前記所定順に読み出された前記係数データをエントロピ符号化するエントロピ符号化手段
   として機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
10. コンピュータを、
    画像データに対して、前記画像データの周波数成分を高域成分と低域成分に分解する分析フィルタ処理を階層的に行い、周波数帯域毎に分解された係数データからなる複数のサブバンドを生成する生成処理を、前記生成処理によって最低域成分のサブバンドを少なくとも１ライン生成するのに必要なライン数分の画像データであるラインブロック毎に行うフィルタ手段と、
    前記係数データを格納する係数格納手段と、
    前記フィルタ手段による前記分析フィルタ処理により生成された前記係数データを、前記サブバンド毎に領域を分けて前記係数格納手段に書き込む書き込み手段と、
    前記係数格納手段の各領域から、前記サブバンド毎に分けられた前記係数データを所定順に読み出す読み出し手段と、
    前記読み出し手段により前記係数格納手段から前記所定順に読み出された前記係数データをエントロピ符号化するエントロピ符号化手段
    として機能させるためのプログラム。

Images