JP4793320B2 - 情報処理装置および方法 - Google Patents

Description

本発明は、情報処理装置および方法に関し、特に、ウェーブレット変換処理および符号化処理を効率よく行うようにし、負荷をより低減させることができるようにした情報処理装置および方法に関する。

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

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

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

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

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

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

このような画像伝送システムにおいては、画像データの伝送を低遅延で行うことが望ましい場合が多く、ウェーブレット変換処理、エントロピ符号化、ウェーブレット逆変換処理、エントロピ復号処理等の各処理に対して遅延時間の低減が求められる。

ところで、ウェーブレット変換処理およびエントロピ符号化処理を行うエンコーダをソフトウェアプログラムにより実現するソフトウェアエンコーダや、エントロピ復号処理やウェーブレット逆変換処理を行うデコーダをソフトウェアプログラムにより実現するソフトウェアデコーダがある。

これらのソフトウェアエンコーダやソフトウェアデコーダは、そのソフトウェアプログラムがパーソナルコンピュータ等の情報処理装置において実行されることにより、エンコーダやデコーダとしての機能が実現される。

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

しかしながら、通常の場合、エンコーダには多様な処理が含まれており、その処理の数は、ソフトウェアプログラムを実行するCPU（Central Processing Unit）の数よりも多い。つまり、ソフトウェアエンコーダの場合、１つのCPUにおいて多様な処理を実行することになる。換言すれば１つの演算処理部を複数の処理で共有することになる。

従って、エンコーダ機能を実現する各処理を効率よく行うように適切に実行させなければ、CPUの使用効率が低下したり、処理に必要なメモリ容量が増大したりして、負荷が増大してしまう恐れがあった。負荷の増大は、コストや遅延時間の増大に繋がる恐れもある。

本発明は、このような従来の実情に鑑みて提案されたものであり、ウェーブレット変換処理および符号化処理をより効率よく実行させることにより、ハードウェアに負荷をより低減させることができるようにするものである。

本発明の第１の側面は、画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理手段と、前記分析フィルタ処理手段により、帯域毎に分割された前記周波数成分を可変長符号化する符号化手段と、前記分析フィルタ処理手段を制御し、画像データが２ライン入力される毎に、前記リフティング演算の、実行可能な演算を実行させ、さらに、前記符号化手段を制御し、前記演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させる制御手段とを備える情報処理装置である。

前記制御手段は、前記分析フィルタ処理手段に、実行可能な演算のうち、より高域の周波数成分を生成する演算を、より先に実行させ、前記符号化手段に、符号化可能な周波数成分のうち、より低域の周波数成分であり、かつ、同じ帯域の中では、より先に生成された周波数成分を、より先に可変長符号化させることができる。

前記制御手段は、前記符号化手段に、常に、前記リフティング演算により直前に生成された最低域の周波数成分より先に生成された周波数成分を可変長符号化させることができる。

前記符号化手段により前記周波数成分が符号化されて得られた符号化データを保持する符号化データ保持手段をさらに備え、前記制御手段は、前記リフティング演算により最低域の周波数成分が生成されるよりも先に、前記最低域の周波数成分に対応する、前記最低域の周波数成分よりも高域の周波数成分を符号化させ、得られた符号化データを前記符号化データ保持手段に保持させ、前記最低域の周波数成分が生成され符号化され出力された後に、前記符号化データ保持手段に保持されている前記符号化データを所定の順に出力させることができる。
前記分析フィルタ処理手段により帯域毎に分割された周波数成分を保持する周波数成分保持手段をさらに備え、前記符号化手段は、前記周波数成分保持手段に保持されている前記周波数成分を可変長符号化することができる。

本発明の第１の側面はまた、情報処理装置の情報処理方法であって、画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理部を制御し、前記画像データが２ライン入力される毎に、前記リフティング演算の、実行可能な演算を実行させ、帯域毎に分割された前記周波数成分を可変長符号化する符号化部を制御し、前記演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させるステップを含む情報処理方法である。

本発明の第２の側面は、画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理手段と、前記分析フィルタ処理手段により、帯域毎に分割された前記周波数成分を可変長符号化する符号化手段と、前記符号化手段を制御し、入力された複数ラインの画像データを用いて行われた、前記リフティング演算の実行可能な演算が終了してから、次の画像データの複数ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させる制御手段とを備える情報処理装置である。
本発明の第２の側面はまた、情報処理装置の情報処理方法であって、リフティング演算によって帯域毎に分割された画像データの周波数成分を可変長符号化する符号化部を制御し、分析フィルタ処理部において前記画像データが２ライン入力される毎に行われる、前記リフティング演算の、実行可能な演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させるステップを含む情報処理方法である。

本発明の第１の側面においては、画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理部が制御され、画像データが２ライン入力される毎に、リフティング演算の、実行可能な演算が実行され、帯域毎に分割された周波数成分を可変長符号化する符号化部が制御され、演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分が可変長符号化される。

本発明の第２の側面においては、リフティング演算によって帯域毎に分割された画像データの周波数成分を可変長符号化する符号化部が制御され、分析フィルタ処理部において画像データが２ライン入力される毎に行われる、リフティング演算の、実行可能な演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分が可変長符号化される。

本発明によれば、ウェーブレット変換処理および符号化処理を行うことができる。特に、より高効率にウェーブレット変換処理および符号化処理を行うことができ、ハードウェアにかかる負荷をより低減させることができる。

以下、本発明の実施の形態について説明する。まず、符号化側の構成および動作について説明する。

以下、本発明の実施の形態について説明する。まず、本発明に用いるウェーブレット変換およびウェーブレット逆変換を利用した符号化・復号システムの構成および動作について説明する。

図１は、ソフトウェアプログラムにより構成され、画像データを符号化するソフトウェアエンコーダが有する機能を模式的に示した機能ブロック図である。図１に示される符号化部１０は、ソフトウェアエンコーダであり、ソフトウェアプログラムがCPU（Central Processing Unit）により実行されることにより、ウェーブレット変換部１１、途中計算用バッファ部１２、係数並び替え用バッファ部１３、係数並び替え部１４、およびエントロピ符号化部１５の機能を有する。

ウェーブレット変換部１１は、符号化部１０に入力された画像データに対して、画像データの周波数成分をその帯域毎に分離させるウェーブレット変換処理を行う。詳細については後述するが、ウェーブレット変換部１１は、分析フィルタ処理により、周波数成分を低域成分と高域成分に分離する。また、ウェーブレット変換部１１は、得られた低域成分に対して分析フィルタ処理を再帰的に繰り返し行うことにより、周波数成分を帯域毎に階層的に分割する。なお、以下において、この周波数成分を、ウェーブレット係数、ウェーブレット係数データ、係数データ、または係数と称する。また、以下において、周波数成分分割の階層を分割レベルと称する。

分析フィルタ処理を繰り返す際において、ウェーブレット変換部１１は、次回の分析フィルタ処理に利用する係数データや画像データを途中計算用データとして途中計算用バッファ部１２に保持させる。つまり、ウェーブレット変換部１１は、途中計算用バッファ部１２に保持させている途中計算用データ（画像データや係数データ）を読み出し、その途中計算用データを用いて、外部より入力された画像データに対してウェーブレット変換処理を行う。

ウェーブレット変換部１１は、各分割レベルにおいて得られた高域成分（係数データ）、および、予め定められた最終的な分割レベル（最上位レベル）の低域成分（係数データ）を、係数並び替え用バッファ部１３に書き込む。

係数並び替え部１４は、係数並び替え用バッファ部１３に書き込まれた係数データを所定の順序で読み出し、エントロピ符号化部１５に供給する。詳細については後述するが、係数データは、ウェーブレット変換処理における生成順と、ウェーブレット逆変換処理における利用順とが異なる。そこで、係数並び替え部１４は、係数並び替え用バッファ部１３より係数データを、ウェーブレット逆変換処理において利用される順に読み出すことにより、係数データの並び替えを行う。

エントロピ符号化部１５は、供給された係数データを、所定の方法で量子化し、例えばハフマン符号化や算術符号化といった所定のエントロピ符号化方式で符号化する。つまり、エントロピ符号化部１５は、係数データを、ウェーブレット逆変換処理において利用される順に符号化する。エントロピ符号化部１５は、生成した符号化データを符号化部１０の外部に出力する。

図２は、ソフトウェアプログラムにより構成され、図１の符号化部１０に対応するソフトウェアデコーダが有する機能を模式的に示した機能ブロック図である。この復号部２０は、符号化部１０において画像データが符号化されて得られた符号化データを復号し、画像データを復元する処理部であり、エントロピ復号部２１、係数バッファ部２２、およびウェーブレット逆変換部２３の機能を有する。

符号化データが入力されると、エントロピ復号部２１は、その符号化データに対して、図１のエントロピ符号化部１５に対応する方法でエントロピ復号を行い、係数データを復元する。エントロピ復号部２１は、得られた係数データを係数バッファ部２２に保持させる。ウェーブレット逆変換部２３は、係数バッファ部２２に保持されている係数データに対して、図１のウェーブレット変換部１１が行ったウェーブレット変換処理の逆変換処理を行い、元の画像データを復元する。

つまり、ウェーブレット逆変換部２３は、ウェーブレット変換部１１により階層的に分割された周波数成分に対して、最上位の分割レベルから順に、低域成分と高域成分を合成する合成フィルタ処理を行い、周波数成分の分割レベルを１つずつ下げていき、最終的にベースバンドの画像データを復元する。ウェーブレット逆変換部２３は、生成した画像データを復号部２０の外部に出力する。

次に、このような符号化部１０および復号部２０を用いるシステムにおいて利用されるウェーブレット変換処理について説明する。画像データに対するウェーブレット変換では、図３に概略的に示されるように、画像データを空間周波数の高い帯域と低い帯域とに分割する処理を、分割の結果得られる空間周波数の低い帯域のデータに対して再帰的に繰り返す。

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

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

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

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

このように、低域成分に対して繰り返し変換および分割を行うのは、図４に示されるように、より上位（低域成分）のサブバンドほど、画像のエネルギが低域成分に集中しているためである。このように分析フィルタ処理を再帰的に処理を行い、階層的なサブバンドを生成し、空間周波数の低い帯域のデータをより小さな領域に追い込んでいくことで、エントロピ符号化を行う際に効率的な圧縮符号化を可能とする。

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

このようなウェーブレット変換処理をピクチャ全体に対してまとめて行う方法もあるが、１ピクチャの画像データを数ライン毎に分割し、それぞれについてウェーブレット変換処理を互いに独立して行う方法もある。前者の場合よりも後者の場合の方が、１回のウェーブレット変換処理で処理される画像データのデータ量が少ないので、ウェーブレット変換処理の処理結果の出力開始タイミングをより早くすることができる。つまり、ウェーブレット変換処理による負荷や遅延時間を低減させることができる。

なお、この場合のウェーブレット変換処理の処理単位となるライン数は、ウェーブレット変換処理の、予め定められた分割レベルにおいて、最上位レベルのサブバンドの係数データ１ラインを得るために必要なライン数に基づく。

分析フィルタ処理により、データは４分割されるので、図４に示されるように、分割レベル１では４ラインであったものが、分割レベル２では２ラインとなり、分割レベル３では１ラインとなる。つまり、分割レベルが１つ上がるとともにライン数は半減する。換言すると、分割レベル３のウェーブレット変換処理の場合、最上位レベルのサブバンド（３ＬＬ、３ＬＨ、３ＨＬ、および３ＨＨ）の係数データを１ライン得るためには、８ラインのベースバンドの画像データが必要になる。従ってこの場合、ウェーブレット変換処理は、ベースバンドの画像データ８ライン以上を処理単位としてウェーブレット変換処理が行われる。

このように、最上位レベルの低域サブバンド「ＬＬ」の係数データを１ライン生成するために必要なベースバンドの画素データの集合、若しくは、その画像データより得られる係数データの集合をプレシンクト（Precinct）（またはラインブロック）と称する。

なお、図４に示されるように、水平方向のデータ数は、分割レベルが１つ上がるとともに半減する。つまり、ベースバンドの画像データの水平方向の画素数が１９２０画素の場合、分割レベル１の係数データの水平方向のデータ数は９６０となり、分割レベル２の係数データの水平方向のデータ数は４８０となり、分割レベル３の係数データの水平方向のデータ数は２４０となる。

ウェーブレット変換処理およびウェーブレット逆変換処理は、基本的に、ピクチャ全体ではなく、このプレシンクトを単位として行われる。つまり、１ピクチャの画像データは、それぞれが複数ラインからなる複数のプレシンクトに分割され、そのプレシンクト毎に複数回に分けて処理される。従って、基本的にはウェーブレット変換処理およびウェーブレット逆変換処理は、そのプレシンクト毎に完結する。例えば、１プレシンクトのベースバンドの画像データに対してウェーブレット変換処理が行われると、最低域成分（最上位の分割レベルの係数データ）が少なくとも１ライン以上からなる、周波数帯域毎に階層的に分割された係数データ群が得られ、その係数データ群に対してウェーブレット逆変換処理が行われると、元の１プレシンクト分のベースバンドの画像データが得られる。

このように、ピクチャよりも細かいプレシンクトを単位としてウェーブレット変換処理やウェーブレット逆変換処理を行うことにより、ウェーブレット変換処理やウェーブレット逆変換処理を行うために蓄積させる画像データや係数データのデータ量（蓄積量）を低減させることができる。つまり、より早いタイミングで変換後の係数データや画像データを出力させることができ、ウェーブレット変換処理やウェーブレット逆変換処理による負荷や遅延時間を低減させることができる。

なお、さらに画像データの各ラインを複数に分割したブロックを処理単位としてウェーブレット変換処理やウェーブレット逆変換処理を行う方法も考えられるが、その場合、水平同期タイミング以上に細かい単位で制御を行わなければならず、プレシンクトを処理単位とする場合よりも、制御が高速かつ複雑になり負荷が増大する恐れがある。また、ブロックを構成するライン数の最小数は、プレシンクトと同様に分割レベルにより制限される。１ピクチャの画像データは、ライン毎に、画面上のラインから順に供給されるので、ブロックを処理単位とする場合も、プレシンクトを処理単位とする場合と略同程度の画像データや係数データを蓄積させる必要がある。従って、ウェーブレット変換処理やウェーブレット逆変換処理の遅延時間は、どちらの場合もほとんど変化しない。

なお、１プレシンクトのライン数はピクチャ内において、各プレシンクトで互いに同一でなくてもよい。

ウェーブレット変換には例えば５×３フィルタや９×７フィルタ等の分析フィルタが用いられる。５×３フィルタを用いた方法は、JPEG２０００規格でも採用されており、少ないフィルタタップ数でウェーブレット変換を行うことができる点で、優れた方法である。

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

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

これら式（１）および式（２）によれば、低域成分および高域成分の係数を、直接的に算出することができる。このようなフィルタを用いる分析フィルタ処理における演算方法で最も一般的な演算方法は、畳み込み演算と呼ばれる方法である。この畳み込み演算は、デジタルフィルタの最も基本的な実現手段であり、フィルタのタップ係数に実際の入力データを畳み込み乗算するものである。しかしながら、この畳み込み演算ではタップ長に応じて計算負荷が増大するので、論文「W.Swelden,“The lifting scheme :A custom-design construction of Biorthogonal wavelets.”, Appl. Comput. Harmon. Anal., vol3, no.2, pp.186-200, 1996」で紹介されたリフティング技術を用いてフィルタ処理の演算を行う方法がある。

図５は、ウェーブレット変換処理およびウェーブレット逆変換処理によるデータの変化の様子の例を示す模式図である。図５Ａは、ウェーブレット変換されるベースバンドの画像データを模式的に示し、図５Ｂは、図５Ａの画像データが分割レベル３でウェーブレット変換されて得られる係数データを模式的に示し、図５Ｃは、図５Ｂの係数データがウェーブレット逆変換されて得られるベースバンドの画像データを模式的に示している。

図５において、各模様で示される領域はそれぞれプレシンクトを示している。また、図５Ａ乃至図５Ｃにおいて同じ模様のプレシンクトは、互いに対応するプレシンクトを示している。例えば、図５Ａにおいて右上左下の斜め線で示されるベースバンドの画像データがウェーブレット変換されると、図５Ｂにおいて右上左下の斜め線で示される、帯域毎に階層的に分割された係数データが生成され、さらにそれらの係数データがウェーブレット逆変換されると、図５Ｃにおいて右上左下の斜め線で示されるベースバンドの画像データが生成される。なお、説明の簡略化のため、図５においては、１ピクチャのライン数を３１ラインとする。

詳細については後述するが、図５Ａに示されるように、リフティング技術を用いてフィルタ処理の演算を行う場合、一般的に、ピクチャの一番上のプレシンクトは、上から２番目以降のプレシンクトよりも多くのライン数を必要とする。また、図５Ｂに示されるように、リフティング技術を用いてフィルタ処理の演算を行う場合、一般的に、ピクチャの一番上のプレシンクトと一番下のプレシンクトは、各分割レベルにおける係数データのライン数が他のプレシンクトと異なる。

さらに、リフティング技術を用いてフィルタ処理の演算を行う場合、図５Ａおよび図５Ｃに示されるように、あるプレシンクトについて、ベースバンドの画像データをウェーブレット変換し、さらにウェーブレット逆変換すると、変換前のライン番号と異なるライン番号のベースバンドの画像データが復元される。つまり、ウェーブレット変換時のプレシンクトと、そのプレシンクトに対応するウェーブレット逆変換時のプレシンクトとでは、ベースバンドの画像データのライン番号が互いに異なる。

また、ピクチャの一番上のプレシンクトの場合、ウェーブレット変換前のベースバンドの画像データと、ウェーブレット逆変換後に得られるベースバンドの画像データとでライン数が異なる。従って、図５Ａおよび図５Ｃに示されるように、ベースバンドの画像データをウェーブレット変換し、さらにウェーブレット逆変換するとライン数が減少する。従って、図５Ｃに示されるように３１ラインの画像データを復元するためには、図５Ａに示されるように３１ラインより多くのラインの画像データをウェーブレット変換する必要がある。つまり、ウェーブレット変換時にはベースバンドの画像データにダミーデータが付加される。なお、図５Ｃに示されるピクチャの一番下のプレシンクトの画像データを復元するために、ウェーブレット逆変換処理においてもダミーデータが利用される。

次に、リフティング技術について説明する。

図６は、５×３フィルタのリフティングを用いた例を示したものである。以下、このフィルタリング方法について説明する。

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

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

ｄ_i ¹＝ｄ_i ⁰−１／２（ｓ_i ⁰＋ｓ_i+1 ⁰） ・・・（３）

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

ｓ_i ¹＝ｓ_i ⁰＋１／４（ｄ_i-1 ¹＋ｄ_i ¹） ・・・（４）

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

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

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

ｓ_i ⁰＝ｓ_i ¹−１／４（ｄ_i-1 ¹＋ｄ_i ¹） ・・・（５）

次に第２段階として、次式（６）に従い、上述の第１段階で生成された偶数番目の係数ｓ_i ⁰と、入力された高域成分の係数ｄ_i ¹から、奇数番目の係数ｄ_i ⁰が生成される。

ｄ_i ⁰＝ｄ_i ¹＋１／２（ｓ_i ⁰＋ｓ_i+1 ⁰） ・・・（６）

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

図８は、５×３フィルタのリフティングによるフィルタリングを分解レベル３まで実行したときの分析フィルタ処理および合成フィルタ処理の様子の例を示す模式図である。図８の左側は分析フィルタ処理におけるリフティング演算の様子の例を示しており、図８の右側は合成フィルタ処理におけるリフティング演算の様子の例を示している。

より具体的に説明すると、図８の丸や四角は、画像データまたは係数データを示しており、それらを結ぶ直線は、リフティング演算における画像データや係数データの関係を示している。つまり、図８においては、丸や四角の３列毎に１つのリフティング演算が示されており、各３列のうち、最も左の列の丸や四角がリフティング演算の入力データを示し、中央の列および最も右の列の丸や四角がリフティング演算の出力データを示している。各入力データがリフティング演算されることにより、その入力データと直線で結ばれる出力データが生成される。換言すれば、各出力データは、その出力データと直線で結ばれる入力データを用いて生成される。

図８の中央縦方向の点線の左側において、左から１列目乃至３列目の丸、四角、およびそれらを結ぶ直線は分割レベル１の分析フィルタ処理のリフティング演算の様子を示し、左から４列目乃至６列目の丸、四角、およびそれらを結ぶ直線は分割レベル２の分析フィルタ処理のリフティング演算の様子を示し、左から７列目乃至９列目の丸、四角、およびそれらを結ぶ直線は分割レベル３の分析フィルタ処理のリフティング演算の様子を示している。また、図８の中央縦方向の点線の右側において、左から１列目乃至３列目の丸、四角、およびそれらを結ぶ直線は分割レベル３の合成フィルタ処理のリフティング演算の様子を示し、左から４列目乃至６列目の丸、四角、およびそれらを結ぶ直線は分割レベル２の合成フィルタ処理のリフティング演算の様子を示し、左から７列目乃至９列目の丸、四角、およびそれらを結ぶ直線は分割レベル１の合成フィルタ処理のリフティング演算の様子を示している。

図８において、左上右下の斜め線模様で示される丸は、ベースバンドの画像データの、ライン番号が奇数のライン（奇数ライン）を示し、左上右下の斜め線模様で示される四角は、ベースバンドの画像データの、ライン番号が偶数のライン（偶数ライン）を示している。なお、ライン番号は、画像の一番上のラインを「０」とし、上から下に向かう順にインクリメントされる。

また図８において、左下右上の斜め線模様で示される丸と四角は、それぞれ、リフティング演算の途中の計算に利用される途中計算用の奇数番目の係数と偶数番目の係数を示しており、図８において黒丸（●）と黒四角（■）は、それぞれ、リフティング演算結果として得られる高域成分と低域成分（周波数成分）を示している。

なお、図８では、説明の簡略化のため、垂直方向についてのフィルタ処理のみ説明しており、水平方向の分析フィルタ処理および合成フィルタ処理については省略している。

より具体的に説明する。図８の中央縦方向の点線の左側において、左から１列目に示される画像データが入力されると、ウェーブレット変換部１１は、それらの画像データに対して分割レベル１の分析フィルタ処理（リフティング演算）を行い、左から２列目に示される分割レベル１の高域成分と、左から３列目に示される分割レベル１の低域成分を生成する。この左から２列目に示される分割レベル１の高域成分は、これ以上分析フィルタ処理が行われず、係数並び替え用バッファ部１３に供給されて保持される。また、左から３列目に示される分割レベル１の低域成分は、再度分析フィルタ処理を行うために、途中計算用データとして途中計算用バッファ部１２に供給されて保持される。

次に、ウェーブレット変換部１１は、途中計算用バッファ部１２に保持させた途中計算用データに対して、図８の中央縦方向の点線の左側において、左から４列目乃至６列目に示されるように、分割レベル２の分析フィルタ処理（リフティング演算）を行う。左から４列目の丸および四角は、それぞれ、左から３列目の同じ行の四角と同じ係数データを示しており、丸が奇数ラインの係数データを示し、四角が偶数ラインの係数データを示している。

ウェーブレット変換部１１は、左から４列目に示される係数データに対して分割レベル２の分析フィルタ処理（リフティング演算）を行い、左から５列目に示される分割レベル２の高域成分と、左から６列目に示される分割レベル２の低域成分を生成する。この左から５列目に示される分割レベル２の高域成分は、これ以上分析フィルタ処理が行われず、係数並び替え用バッファ部１３に供給されて保持される。また、左から６列目に示される分割レベル２の低域成分は、再度分析フィルタ処理を行うために、途中計算用データとして途中計算用バッファ部１２に供給されて保持される。

次に、ウェーブレット変換部１１は、途中計算用バッファ部１２に保持させた途中計算用データに対して、図８の中央縦方向の点線の左側において、左から７列目乃至９列目に示されるように、分割レベル３の分析フィルタ処理（リフティング演算）を行う。左から７列目の丸および四角は、それぞれ、左から６列目の同じ行の四角と同じ係数データを示しており、丸が奇数ラインの係数データを示し、四角が偶数ラインの係数データを示している。

ウェーブレット変換部１１は、左から７列目に示される係数データに対して分割レベル３の分析フィルタ処理（リフティング演算）を行い、左から８列目に示される分割レベル３の高域成分と、左から９列目に示される分割レベル３の低域成分を生成する。分割レベル３は、予め最上位レベルとして設定されており、これ以上分析フィルタ処理は行われない。従って、左から８列目に示される分割レベル３の高域成分も、左から９列目に示される分割レベル３の低域成分も、係数並び替え用バッファ部１３に供給されて保持される。

つまり、図８の中央縦方向の点線の左側において、左から３列目および４列目の係数データを囲む点線の角丸四角、並びに、左から５列目および６列目の係数データを囲む点線の角丸四角は、途中計算用バッファ部１２を示しており、左から２列目、５列目、８列目、および９列目の係数データをそれぞれ囲む実線の角丸四角は、係数並び替え用バッファ部１３を示している。

以上のように、ウェーブレット変換部１１は、ウェーブレット変換処理により、分割レベル１から分割レベル３に向かう順にリフティング演算を行うことにより、高域から低域に向かう順に各分割レベルの係数データを生成する。ただし、詳細については後述するが、実際には、画像データは１ラインずつ入力されるので、ウェーブレット変換部１１は、画像データが２ライン入力される毎にリフティング演算を行うことができる。つまり、入力された画像データや、係数並び替え用バッファ部１３に保持させる係数データも、次のリフティング演算に利用する場合がある。従って、そのような画像データは、入力されたときのリフティング演算に使用されるだけでなく、途中計算用データとして途中計算用バッファ部１２に保持され、次のラインが入力されたときに行われるリフティング演算にも利用される。係数データも同様に、係数並び替え用バッファ部１３に保持されるだけでなく、途中計算用データとして途中計算用バッファ部１２に保持され、後に行われるリフティング演算にも利用される。

ウェーブレット変換部１１は、上述したリフティング演算により、リフティング演算結果の係数データ（黒丸（●）と黒四角（■））を、それぞれの左側に付した番号順に生成する。

これに対して、図８中央縦方向の点線の右側には、ウェーブレット逆変換部２３による合成フィルタ処理におけるリフティング演算の様子が示される。

図８の中央縦方向の点線の右側において、左から１列目に示される係数データ（黒丸（●）と黒四角（■））は、それぞれ、自分自身と同じ行の、図８の中央縦方向の点線の左側の左から８列目または９列目の係数データと同じデータである。つまり、ウェーブレット逆変換部２３は、図８の中央縦方向の点線の右側において左から１列目に示される分割レベル３の低域成分（黒四角（■））と高域成分（黒丸（●））を合成する、分割レベル３の合成フィルタ処理（リフティング演算）を行い、左から２列目に示される分割レベル２の低域成分の偶数ラインの係数データと、左から３列目に示される分割レベル２の低域成分の奇数ラインの係数データを生成する。

この左から２列目および３列目に示される分割レベル２の低域成分と、新たに供給された分割レベル２の高域成分に対して、ウェーブレット逆変換部２３は、再度リフティング演算（分割レベル２の合成フィルタ処理）を行う（左から４列目乃至６列目）。左から４列目の左下右上の斜線模様の四角は、それぞれ自分自身と同じ行の、左から２列目の四角または左から３列目の丸と同じ係数データを示している。また、左から４列目の黒丸（●）は、それぞれ自分自身と同じ行の、図８の中央縦方向の点線の左側において左から５列目の黒丸（●）と同じ係数データ、すなわち、新たに供給された分割レベル２の高域成分を示している。

ウェーブレット逆変換部２３は、図８の中央縦方向の点線の右側において左から４列目に示される分割レベル２の低域成分と高域成分を合成する、分割レベル２の合成フィルタ処理（リフティング演算）を行い、左から５列目に示される分割レベル１の低域成分の偶数ラインの係数データと、左から６列目に示される分割レベル１の低域成分の奇数ラインの係数データを生成する。

この左から５列目および６列目に示される分割レベル１の低域成分と、新たに供給された分割レベル１の高域成分に対して、ウェーブレット逆変換部２３は、再度リフティング演算（分割レベル１の合成フィルタ処理）を行う（左から７列目乃至９列目）。左から７列目の左下右上の斜線模様の四角は、それぞれ自分自身と同じ行の、左から５列目の四角または左から６列目の丸と同じ係数データを示している。また、左から７列目の黒丸（●）は、それぞれ自分自身と同じ行の、図８の中央縦方向の点線の左側において左から２列目の黒丸（●）と同じ係数データ、すなわち、新たに供給された分割レベル１の高域成分を示している。

ウェーブレット逆変換部２３は、図８の中央縦方向の点線の右側において左から７列目に示される分割レベル１の低域成分と高域成分を合成する、分割レベル１の合成フィルタ処理（リフティング演算）を行い、左から８列目に示されるベースバンドの画像データの偶数ラインと、左から９列目に示されるベースバンドの画像データの奇数ラインを生成する。

以上のような分析フィルタ処理および合成フィルタ処理のリフティング演算の関係から、プレシンクトは、曲線５１および曲線５２に示されるように区切られる。つまり、ウェーブレット変換時においては、ピクチャの一番上のプレシンクトである第１プレシンクトの画像データは、ライン番号０乃至ライン番号１４の１５ラインが必要であり、ピクチャの上から２番目のプレシンクトである第２プレシンクトの画像データは、ライン番号１５乃至ライン番号２２の８ラインが必要である。なお図８に示されるように実際には、第２プレシンクトの分析フィルタ処理において、第１プレシンクトの画像データや係数データも利用される。

また、ウェーブレット逆変換時においては、第１プレシンクトの係数データより、ライン番号０の１ラインの画像データが生成され、第２プレシンクトの係数データより、ライン番号１乃至ライン番号８の８ラインの画像データが生成される。なお図８に示されるように実際には、第２プレシンクトの合成フィルタ処理において、第１プレシンクトの画像データや係数データも利用される。

図８の中央縦方向の点線の右側において、黒丸（●）および黒四角（■）の左側に付した番号は、それぞれの係数データが合成フィルタ処理において利用される順序を示している。また、その数字の横に示される括弧内の数字は、その係数データが分析フィルタ処理において生成された順序を示している。つまり、図８の中央縦方向の点線の右側において示される括弧内の数字は、図８の中央縦方向の点線の左側に示される数字と対応する。

つまり、分析フィルタにおける係数データの生成順と、合成フィルタにおける係数データの利用順は互いに異なる。従って図８の中央において白抜き矢印で示されるように、分析フィルタ処理において生成された係数データは、合成フィルタ処理が行われる前に、その順序を並び替えられる必要がある。

係数並び替え部１４は、係数並び替え用バッファ部１３に保持された係数データを、合成フィルタ処理における利用順に読み出すことにより、この係数データの並び替えを行う。つまり、エントロピ符号化部１５は、合成フィルタ処理における利用順に係数データを符号化する。

符号化部１０および復号部２０の各部は、それぞれの処理を、図９に模式的に示されるように、互いに並列的に実行する。つまり、符号化部１０による、画像データの入力、ウェーブレット変換（DWT）、係数の並び替え、およびエントロピ符号化（VLC）の各処理と、復号部２０による、エントロピ復号（VLD）、ウェーブレット逆変換（IDWT）、および画像データ出力の各処理は、図９の矢印に示されるように、互いに並行して実行される。各矢印は１プレシンクトに対する処理を示しており、各矢印の下に付された数字は、その矢印において処理されるライン数を示している。例えば、各処理において一番左の矢印で示される第１プレシンクトの場合、１５ラインの画像データが入力され、４ラインの係数データにウェーブレット変換されて符号化され、さらに復号された後ウェーブレット逆変換されて１ラインの画像データとして出力される。これは図８を参照して行った説明と一致する。

このように並行して処理を行うことにより、入力から出力までの遅延時間を、図９において白抜き矢印に示されるように、１５ライン分の時間と各処理の処理時間の合計にすることができる。これに対して例えば１ピクチャ全体を対象としてウェーブレット変換する場合、１ピクチャ分以上の遅延時間が発生する。従って、プレシンクト単位で各処理を行い、かつ、図９に示されるように各処理を互いに並行して実行させることにより、入力から出力までの遅延時間を大幅に低減させることができる。

しかしながら、ソフトウェアエンコーダやソフトウェアデコーダの場合、図１０に示されるようなパーソナルコンピュータにおいてソフトウェアプログラムが実行されることにより実現される。

図１０は、パーソナルコンピュータの構成例を示すブロック図である。

図１０において、パーソナルコンピュータ１００のCPU１０１は、ソフトウェアプログラムを実行することにより、各種の処理を実行する演算処理部である。CPU１０１は、共有バスであるバス１０４を介してROM（Read Only Memory）１０２およびRAM（Random Access Memory）１０３と相互に接続されている。ROM１０２には予めソフトウェアプログラムやデータが格納されている。RAM１０３には、ROM１０２や記憶部１１３に格納されているソフトウェアプログラムやデータがロードされる。RAM１０３にはまた、CPU１０１が各種の処理を実行する上において必要なデータなども適宜記憶される。

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

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

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

なお、図示は省略するが、CPU１０１の内部には、キャッシュメモリが設けられている。このキャッシュメモリは、RAM１０３に比べて高速に動作するものの、RAM１０３に比べて容量が小さい。つまり、このキャッシュメモリには、一度に格納可能なデータ量が制限される。従って、CPU１０１は、使用頻度の高いデータや、近いうちに使用する予定のあるデータをこのキャッシュメモリに格納し、使用頻度が少ないデータや当面利用する予定の無いデータ等をRAM１０３に保持させる。

図１０に示されるように、パーソナルコンピュータ１００には、演算処理部はCPU１０１の１つしか存在しない。従って、図１に示される符号化部１０のようなソフトウェアエンコーダの各処理を図９に示されるように、実際に並列に実行させることはできない。そのため、各処理が擬似的に並列に実行されているようにするためには、CPU１０１を時分割して各処理に割り当てる必要がある。その場合、時分割の単位として、プレシンクトを用いる方法が考えられる。

つまり、図１に示されるように、供給される画像データに対して、１プレシンクトを対象としてウェーブレット変換処理を行い、係数を並び替え、エントロピ符号化処理を施すようにする。これをプレシンクト毎に複数回繰り返すことにより、１ピクチャの画像データを処理するようにする。このようにすることにより、ピクチャ全体を対象としてウェーブレット変換する場合よりも、ウェーブレット変換処理の負荷や遅延時間を低減させることができる。

しかしながら、単純に１プレシンクト全体を対象としてウェーブレット変換処理を行う場合、入力される画像データを１プレシンクト分蓄積しなければならず、メモリ量が増大し、回路規模やコストが増大するだけでなく、負荷や遅延時間も増大してしまう恐れがある。

そこで、上述したようにウェーブレット変換部１１がリフティング演算を用いてウェーブレット変換処理を行うことに着目し、１プレシンクトの画像データに対して行うウェーブレット変換処理を効率よく行うことにより、この画像データの蓄積量を低減させるようにする。

図１１にウェーブレット変換処理におけるリフティング演算の手順の例を示す。図１１においては、ピクチャの上から２番目のプレシンクトである第２プレシンクトを例に説明する。第１プレシンクトや第３プレシンクト以降のプレシンクトの場合も基本的には同様である。

図１１は、基本的に図８と同様の図であり、分析フィルタ処理として５×３フィルタを用いたときのリフティング演算の様子の例を示す図である。従って図１１の詳細についての説明は省略する。なお、黒丸（●）と黒四角（■）の右横または下に付された番号は、各係数データの合成フィルタ処理される順序を示している。

図１１において、曲線１５１により囲まれる部分が符号化部１０における第２プレシンクト（第２プレシンクトに対するリフティング演算の様子）を示している。図８を参照して説明したように、リフティング演算は、白抜き矢印で示されるように、図中左から右へ、すなわち、より高域の周波数成分を生成するリフティング演算をより先に実行するように進む。従って、第２プレシンクトに対するリフティング演算は、画像データが２ライン入力される度に、曲線１６１乃至曲線１６４に示されるように行うことができる。つまり、ウェーブレット変換部１１は、ライン番号１５および１６の画像データが入力されると、曲線１６１に囲まれる部分のリフティング演算を行い、１９番目に合成フィルタ処理される係数データを生成し、ライン番号１７および１８の画像データが入力されると、曲線１６２に囲まれる部分のリフティング演算を行い、２０番目に合成フィルタ処理される係数データを生成し、さらに、１５番目に合成フィルタ処理される係数データを生成する。

続いて、ウェーブレット変換部１１は、ライン番号１９および２０の画像データが入力されると、曲線１６３に囲まれる部分のリフティング演算を行い、２４番目に合成フィルタ処理される係数データを生成し、ライン番号２１および２２の画像データが入力されると、曲線１６４に囲まれる部分のリフティング演算を行い、２５番目に合成フィルタ処理される係数データを生成し、さらに、１８番目に合成フィルタ処理される係数データを生成し、最後に、６番目に合成フィルタ処理される係数データと５番目に合成フィルタ処理される係数データを生成する。

このように、２ライン画像データが入力される毎に、実行可能なリフティング演算を順次行うことにより、ウェーブレット変換部１１は、１プレシンクト分の画像データを蓄積する必要がなくなり、必要なメモリ容量を低減させ、回路規模や製造コストを低減させることができるだけでなく、ウェーブレット変換処理の負荷や遅延時間を低減させることができる。

なお、この符号化部１０における第２プレシンクトに対応する、復号部２０における第２プレシンクトは、図１１の曲線１５２により囲まれる部分に示されており、係数データに付された番号で示されるように、合成フィルタ処理は、白抜き矢印で示されるように、図中右から左に向かう向き、すなわち、分析フィルタ処理により帯域毎に分割された各周波数成分のうち、より低域の周波数成分であり、かつ、同じ帯域の中では、より先に生成された周波数成分を、より先に処理するように進められる。符号化部１０において、エントロピ符号化の処理順は、上述したように、ウェーブレット逆変換（合成フィルタ処理）の処理順と同じである。つまり、このエントロピ符号化も、分析フィルタ処理により帯域毎に分割された各周波数成分のうち、より低域の周波数成分であり、かつ、同じ帯域の中では、より先に生成された周波数成分を、より先に処理するように進められる。

黒丸や黒四角で示される、ウェーブレット変換部１１より出力される係数データは、係数並び替え部１４により、その番号順にエントロピ符号化部１５に供給される。エントロピ符号化部１５は、その供給順に各係数データに対してエントロピ符号化を行い、それぞれの符号化データを得る。つまり、エントロピ符号化部１５は、ウェーブレット変換処理により、図１１において点線の楕円で囲まれた、５番目に合成フィルタ処理される係数データと６番目に合成フィルタ処理される係数データが生成されるまで、復号部２０における第２プレシンクトの係数データに対してエントロピ符号化を開始することができない。

従って、CPU１０１においては、図１２に示されるように符号化部１０の各処理が進められる。図１２において、CPU１０１は、ソフトウェアプログラムを実行することにより符号化部１０の機能を実現する。なお、そのCPU１０１に対して符号化される画像データが、通常再生の速度、つまりビデオ信号の同期タイミングに合わせて入力される。つまり、CPU１０１には画像データが１ラインずつ、ビデオ信号の水平同期タイミングに合わせて略一定の間隔で供給される。

CPU１０１は、符号化部１０における第２プレシンクトについて、画像データが２ライン入力される毎に実行可能なリフティング演算（分析フィルタ処理）を行う（DWT（Lev１）乃至DWT（Lev３））。

図１２において、「DWT（Lev１）」と記述された四角は、CPU１０１に分割レベル１の合成フィルタ処理が割り当てられる時間の例を示しており、「DWT（Lev２）」と記述された四角は、CPU１０１に分割レベル２の合成フィルタ処理が割り当てられる時間の例を示しており、「DWT（Lev３）」と記述された四角は、CPU１０１に分割レベル３の合成フィルタ処理が割り当てられる時間の例を示している。つまり、図中、一番上の段の四角（DWT（Lev１））に示される時間（ライン番号１６（および１５）の画像データが入力されてから、ライン番号１８（および１７）の画像データが入力されるまでの間）において、CPU１０１が図１１の曲線１６１に囲まれた部分のリフティング演算を行い、上から２段目の四角（DWT（Lev１））と３段目の四角（DWT（Lev２））に示される時間（ライン番号１８（および１７）の画像データが入力されてから、ライン番号２０（および１９）の画像データが入力されるまでの間）において、CPU１０１が図１１の曲線１６２に囲まれた部分のリフティング演算を行い、上から４段目の四角（DWT（Lev１））に示される時間（ライン番号２０（および１９）の画像データが入力されてから、ライン番号２２（および２１）の画像データが入力されるまでの間）において、CPU１０１が図１１の曲線１６３に囲まれた部分のリフティング演算を行い、上から５段目の四角（DWT（Lev１））と６段目の四角（DWT（Lev２））と７段目の四角（DWT（Lev３））に示される時間（ライン番号２２（および２１）の画像データが入力た後の時間）において、CPU１０１が図１１の曲線１６４に囲まれた部分のリフティング演算を行うことが示されている。

CPU１０１は、各リフティング演算において、符号化する係数データを生成すると、それを順次係数並び替え用バッファ部１３に保持させる。この係数並び替え用バッファ部１３は、例えば、CPU１０１内のキャッシュメモリやRAM１０３により構成される。

そして、５番目に合成フィルタ処理される係数データと６番目に合成フィルタ処理される係数データを生成すると、CPU１０１は、復号部２０における第２プレシンクトの係数データに対してエントロピ符号化を開始する。なお、このとき最後に生成された、５番目に合成フィルタ処理される係数データと６番目に合成フィルタ処理される係数データは、データ量も少なく、かつ直ぐに使用するので、CPU１０１において保持したまま、係数並び替え用バッファ部１３に保持させずに、エントロピ符号化処理を開始する。

このように、最後に生成された係数データを最初に符号化するという、係数並び替えの特徴を利用して、５番目に合成フィルタ処理される係数データと６番目に合成フィルタ処理される係数データの、係数並び替え用バッファ部１３への保持を省略することにより、係数並び替え用バッファ部１３として必要なメモリ容量を低減させることができる。これにより、回路規模および製造コストを低減させることができるだけでなく、係数並び替え用バッファ部１３への書き込みおよび読み出しの回数が低減されるので、ウェーブレット変換処理および符号化の負荷や遅延時間を低減させることができる。

エントロピ符号化を開始したCPU１０１は、５番目乃至１２番目に合成フィルタ処理される係数データをその番号順に１ラインずつ符号化し、得られた符号化データを順次出力する。

図１２において、「VLC５」と記述された四角は、CPU１０１に、５番目に合成フィルタ処理される係数データを符号化するエントロピ符号化処理が割り当てられる時間の例を示している。「VLC６」乃至「VLC１２」も同様に、６番目乃至１２番目に合成フィルタ処理される係数データを符号化するエントロピ符号化処理が、それぞれ割り当てられる時間の例を示している。

なお、図１２において、図中縦方向上から下に向かう向きに時間の流れを示しているが、その縦方向の長さ（スケール）が、時間の長さを正確に示しているわけではない。例えば、図１２において、画像データの入力が２ラインずつ入力され、さらに、各入力の間隔が一定でないように示されているが、実際には、画像データはビデオ信号の水平同期タイミングに合わせた略一定の周期で１ラインずつ入力される。

また、上述したように、図１２に示される各四角（係数並び替え用バッファ部１３を除く）は、リフティング演算やエントロピ符号化等の処理がCPU１０１に割り当てられる時間を示しているが、これは、CPU１０１がその四角に示される時間において割り当てられた処理を行うことを示すものであり、CPU１０１による各処理の処理時間を示すものではない。つまり、CPU１０１が四角に示される時間のうち一部の時間で処理を終了させる場合もある。また、上述したように図１２において縦方向の長さが時間の長さを示しているわけではなく、四角の縦方向の長さも処理の割り当て時間を正確に示すものではない。

図１２のような処理の流れの場合、ウェーブレット変換処理（DWT）を行っている期間中に入力される画像データに対しては、CPU１０１は、分析フィルタ処理をリアルタイム（即時的）に行うことができるが、エントロピ符号化処理（VLC）を行っている期間に入力される入力される画像データに対しては、分析フィルタ処理をリアルタイム（即時的）に行うことができない。

つまり、図１３に示されるように、通常の再生速度のビデオ信号のように、所定の速度で入力される画像データは、そのビデオ信号の垂直同期信号（vsync）の同期タイミングに同期してピクチャ毎に入力される。各ピクチャの画像データは、ビデオ信号の水平同期信号（hsync）の同期タイミングに同期してライン毎に入力される。つまり、画像データは略定期的に（略一定のペースで）１ラインずつ入力される。これに対して、CPU１０１は、図１３に示されるようにプレシンクト毎にウェーブレット変換処理（DWT）とエントロピ符号化処理（VLC）を交互に実行する。

従って、例えば、図１３において点線の楕円１７１に囲まれる矢印のように、CPU１０１が第１プレシンクトの係数データを符号化中（P1VLC）に発生する水平同期タイミングに合わせて入力される画像データに対して、CPU１０１はリアルタイム（即時的）にウェーブレット変換処理（DWT）を行うことができない（符号化（VLC）中なので）。そこで、その画像データについては、CPU１０１が次の第２プレシンクトに対するウェーブレット変換処理（P2DWT）を開始するまでバッファする（保持しておく）必要がある。

仮に、水平同期タイミング間に１プレシンクト分の符号化処理を全て終了させることができるのであれば、CPU１０１は、画像データのバッファリングを不要とし、リアルタイムにウェーブレット変換処理を行うことができる。しかしながら、このような方法の場合、CPU１０１にかかる負荷が極めて大きく、このような方法を実現するためには、CPU１０１の動作周波数を非常に高くする必要があり、コストが増大してしまう恐れがあるので現実的ではない。現実的なコストで調達可能なCPUの処理速度で画像データを処理するためには、上述したように入力画像データのバッファリングが必要になる。

なお、図１３は、画像データ入力とCPU１０１において実行される処理のタイミングの関係を模式的に示す図であり、図１３に示される水平同期信号（hsync）の矢印は、説明にのための代表的な水平同期タイミングを概略的に示したものであり、全ての水平同期タイミングを正確に示すものではない。また、図１３においても、図１２の場合と同様に、縦方向上から下向きに時間の流れが示されているが、その縦方向の長さが時間の長さを正確に示しているわけではない。

次に、このような流れで処理を実行する符号化部１０の実現化について、より具体的に説明する。図１４は、上述した流れで処理を実行する符号化部１０を実現するソフトウェアプログラムを実行するCPU１０１が有する機能を示す機能ブロック図である。

図１４において、CPU１０１は、制御部２０１、分析フィルタ処理実行部２１１、係数並び替え処理実行部２１２、エントロピ符号化処理実行部２１３、途中計算用データ読み出し部２１４、途中計算用データ書き込み部２１５、出力係数書き込み部２１６、および出力係数読み出し部２１７を有する。

制御部２０１は、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７の各部の動作を制御することにより、符号化部１０の各処理の流れを制御する。また、制御部２０１は、後述する画像データバッファ部２２１のデータ入出力も制御する。

分析フィルタ処理実行部２１１は、制御部２０１に制御されて、入力される画像データに対して分析フィルタ処理（リフティング演算）を行う、図１のウェーブレット変換部１１の機能を実現する分析フィルタ処理を実行する。その分析フィルタ処理を実行する際、分析フィルタ処理実行部２１１は、次のリフティング演算に必要な途中計算用データ（画像データや係数データ）を、途中計算用データ読み出し部２１４を介して途中計算用バッファ部１２より取得する。また、分析フィルタ処理実行部２１１は、リフティング演算により得られた途中計算用データを、途中計算用データ書き込み部２１５を介して途中計算用バッファ部１２に供給し、保持させる。さらに、分析フィルタ処理実行部２１１は、リフティング演算により得られた、分析フィルタ処理をこれ以上行わない係数データ（最上位の分割レベルの低域成分および高域成分、並びに、最上位以外の分割レベルの高域成分）を、出力係数として、出力係数書き込み部２１６を介して係数並び替え用バッファ部１３に供給し、保持させる。

係数並び替え処理実行部２１２は、制御部２０１に制御されて、係数並び替え用バッファ部１３に保持されている出力係数を読み出してエントロピ符号化部１５に供給する、図１の係数並び替え部１４の機能を実現する係数並び替え処理を実行する。係数並び替え処理実行部２１２は、係数並び替え用バッファ部１３に保持されている出力係数を、符号化順（合成フィルタ処理順）に、出力係数読み出し部２１７を介して取得し、それをエントロピ符号化処理実行部２１３に供給することにより、係数の並び替えを行う。

エントロピ符号化処理実行部２１３は、制御部２０１に制御されて、係数並び替え部１４より供給される係数データをその供給順に符号化する図１のエントロピ符号化部１５の機能を実現するエントロピ符号化処理を実行する。エントロピ符号化処理実行部２１３は、係数並び替え処理実行部２１２より供給された係数データ（出力係数）を、その供給順に符号化し、得られた符号化データを、RAM１０３、出力部１１２、記憶部１１３、通信部１１４、またはリムーバブルメディア１２１等のCPU１０１の外部に出力する。

途中計算用データ読み出し部２１４および途中計算用データ書き込み部２１５は、制御部２０１に制御されて、キャッシュメモリ（図示せず）またはRAM１０３等に対して、途中計算用データの読み出しや書き込みを行うことにより、図１の途中計算用バッファ部１２を、キャッシュメモリ（図示せず）またはRAM１０３等の記憶領域に形成させる。途中計算用データ読み出し部２１４は、途中計算用バッファ部１２に保持されている途中計算用データ群の中から必要なものを読み出して分析フィルタ処理実行部２１１に供給する。途中計算用データ書き込み部２１５は、分析フィルタ処理実行部２１１より供給される途中計算用データを途中計算用バッファ部１２に書き込む（保持させる）。

出力係数書き込み部２１６および出力係数読み出し部２１７は、制御部２０１に制御されて、キャッシュメモリ（図示せず）またはRAM１０３等に対して、出力係数の読み出しや書き込みを行うことにより、図１の係数並び替え用バッファ部１３を、キャッシュメモリ（図示せず）またはRAM１０３等の記憶領域に形成させる。出力係数書き込み部２１６は、分析フィルタ処理実行部２１１より供給される出力係数を係数並び替え用バッファ部１３に書き込む（保持させる）。出力係数読み出し部２１７は、係数並び替え用バッファ部１３に保持されている出力係数を、係数並び替え処理実行部２１２に指定された順に読み出して係数並び替え処理実行部２１２に供給する。

画像データバッファ部２２１は、入力される画像データを一時的に保持するバッファ部であり、制御部２０１の制御により、例えばRAM１０３に形成される。画像データバッファ部２２１は、制御部２０１の制御されて、略定期的に１ラインずつ供給される画像データを一時的に保持し、所定のタイミングに合わせて、その保持している画像データを１ラインずつ分析フィルタ処理実行部２１１に供給する。

なお、図１４においては、途中計算用バッファ部１２と係数並び替え用バッファ部１３をCPU１０１内部のキャッシュメモリ（図示せず）に形成し、画像データバッファ部２２１をRAM１０３に形成しているが、これは一例であり、途中計算用バッファ部１２、係数並び替え用バッファ部１３、および画像データバッファ部２２１は、いずれも、任意の記憶領域に形成することができる。ただし、上述したようにキャッシュメモリは、高速にアクセス可能であるものの、容量がRAM１０３に比べて小さいので、不要な負荷や遅延時間の増大を招く恐れのあるバッファ溢れ等を生じさせないようにするために、高頻度で読み書きされるデータや、近い将来に使用予定のあるデータのみを記憶させるようにするのが望ましい。例えば、アクセス頻度の多い途中計算用バッファ部１２は、キャッシュメモリに形成し、アクセス頻度の少ない画像データバッファ部２２１や係数並び替え用バッファ部１３は、RAM１０３に形成するようにしてもよい。

図１４の制御部２０１は、図１の符号化部１０を実現するために、各部を制御する制御処理を実行する。図１５および図１６のフローチャートを参照して、その制御処理の流れの例を説明する。

制御処理が開始されると、制御部２０１は、ステップＳ１０１において、画像データバッファ部２２１を、例えばRAM１０３に形成させ、供給される画像データの蓄積を開始させる。このように制御された画像データバッファ部２２１は、これ以降、制御処理が終了されるまで、１ラインずつ供給される画像データを一時的に保持する。

ステップＳ１０２において、制御部２０１は、画像データバッファ部２２１に、所定ライン数分の画像データが蓄積されたか否かを判定し、蓄積されたと判定するまで待機する。分析フィルタ処理実行部２１１においてリフティング演算が可能な程度、画像データが蓄積されたと判定した場合、制御部２０１は、処理をステップＳ１０３に進める。

ステップＳ１０３において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、画像データバッファ部２２１より、最下位レベルのリフティング演算１回、つまり、分割レベル１の分析フィルタ処理のリフティング演算１回に必要なライン数（例えば、２ラインまたは３ライン）の画像データを取得させる。この制御により、分析フィルタ処理実行部２１１は、画像データバッファ部２２１より、最下位レベルのリフティング演算１回に必要なライン数の画像データを、ライン番号順に取得する。

ステップＳ１０４において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、途中計算用バッファ部１２より、これから行うリフティング演算に必要な途中計算用データを取得させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ読み出し部２１４を制御して、これから行うリフティング演算に必要な途中計算用データを、途中計算用バッファ部１２より読み出させ、供給させる（つまり、途中計算用データを取得する）。この制御により、途中計算用データ読み出し部２１４は、要求された途中計算用データを途中計算用バッファ部１２より読み出し、分析フィルタ処理実行部２１１に供給する。

ステップＳ１０５において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、リフティング演算１回分の分析フィルタ処理を実行させる。この制御により、分析フィルタ処理実行部２１１は、図１１を参照して説明したように、実行可能な分析フィルタ処理のリフティング演算（曲線で囲まれた部分の演算）を１回分実行する。

リフティング演算が行われると、制御部２０１は、ステップＳ１０６において、分析フィルタ処理実行部２１１を制御し、リフティング演算に用いられた画像データや係数データ、およびリフティング演算により得られた係数データのうち、次回以降のリフティング演算に利用するデータを途中計算用データとして途中計算用バッファ部１２に保持させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ書き込み部２１５に途中計算用データを供給するとともに、その途中計算用データ書き込み部２１５を制御し、供給した途中計算用データを途中計算用バッファ部１２に書き込ませる。この制御により、途中計算用データ書き込み部２１５は、分析フィルタ処理実行部２１１より供給された途中計算用データを、途中計算用バッファ部１２に書き込み、保持させる。

ステップＳ１０７において、制御部２０１は、新たな画像データの入力無しに、さらにリフティング演算が可能であるか否かを判定する。可能であると判定した場合、制御部２０１は、処理をステップＳ１０８に進め、分析フィルタ処理実行部２１１を制御し、リフティング演算により得られた出力係数を、係数並び替え用バッファ部１３に保持させる。この制御により、分析フィルタ処理実行部２１１は、出力係数書き込み部２１６に出力係数を供給するとともに、その出力係数書き込み部２１６を制御し、供給した出力係数を係数並び替え用バッファ部１３に書き込ませる。この制御により、出力係数書き込み部２１６は、分析フィルタ処理実行部２１１より供給された出力係数を、係数並び替え用バッファ部１３に書き込み、保持させる。

ステップＳ１０８の処理が終了すると、制御部２０１は、処理をステップＳ１０４に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ１０４乃至ステップＳ１０８の処理を繰り返すことにより、図１１を参照して説明したように、入力された画像データに対応する、実行可能なリフティング演算を全て行わせる。

そして、ステップＳ１０７において、実行可能なリフティング演算が無くなったと判定した場合、制御部２０１は、処理をステップＳ１０９に進める。

ステップＳ１０９において、制御部２０１は、１プレシンクト分のフィルタ処理が終了したか否かを判定し、終了していないと判定した場合、処理をステップＳ１１０に進め、ステップＳ１０８の場合と同様に、分析フィルタ処理実行部２１１を制御し、リフティング演算により得られた出力係数を係数並び替え用バッファ部１３に保持させる。ステップＳ１１０の処理が終了すると、制御部２０１は、処理をステップＳ１０３に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ１０３乃至ステップＳ１１０の処理を繰り返すことにより、図１１を参照して説明したように、リフティング演算を１プレシンクト分実行させる。

そして、ステップＳ１０９において、１プレシンクト分のフィルタ処理が終了したと判定した場合、制御部２０１は、処理を図１６のステップＳ１２１に進める。図１６のステップＳ１２１において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、最後のリフティング演算の出力係数をエントロピ符号化させる。「最後のリフティング演算の出力係数」とは、上述した図１１の説明において５番目に合成フィルタ処理される係数データおよび６番目に合成フィルタ処理される係数データに相当する。つまり、この最後のリフティング演算の出力係数は、係数並び替え用バッファ部１３を介さずにエントロピ符号化させる。制御部２０１がこのように制御することにより、係数並び替え用バッファ部１３として必要なメモリ量を低減させることができるとともに、負荷や遅延時間を低減させることができる。

ステップＳ１２１の制御により、エントロピ符号化処理実行部２１３は、５番目に合成フィルタ処理される係数データおよび６番目に合成フィルタ処理される係数データを順に符号化し、得られた符号化データを順次出力する。

その符号化処理が終了すると、制御部２０１は、ステップＳ１２２において、係数並び替え処理実行部２１２を制御し、係数並び替え用バッファ部１３の出力係数を所定順に読み出させる。この制御により、係数並び替え処理実行部２１２は、出力係数読み出し部２１７を制御し、係数並び替え用バッファ部１３に保持されている係数データを、合成フィルタ処理を行う順に読み出させて供給させる。この制御により、出力係数読み出し部２１７は、係数並び替え用バッファ部１３に保持されている係数データを、合成フィルタ処理を行う順に読み出し、読み出した係数データを係数並び替え処理実行部２１２に供給させる。係数並び替え処理実行部２１２は、供給された係数データを順次エントロピ符号化処理実行部２１３に供給する。

ステップＳ１２３において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、係数並び替え用バッファ部１３より読み出された係数データをエントロピ符号化させる。この制御により、エントロピ符号化処理実行部２１３は、読み出された係数データを符号化し、得られた符号化データを出力する。

ステップＳ１２４において、制御部２０１は、係数並び替え用バッファ部１３に、符号化処理していない出力係数が存在するか否かを判定し、存在すると判定した場合、処理をステップＳ１２２に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ１２２乃至ステップＳ１２４の処理を繰り返すことにより、係数並び替え用バッファ部１３に保持されている全ての出力係数に対して符号化処理を実行させる。ステップＳ１２１の処理が開始された時点において、係数並び替え用バッファ部１３には、１プレシンクト分の出力係数（最後のリフティング演算の出力係数は除く）が蓄積されている。制御部２０１は、この出力係数全てについて符号化処理を実行させる。

ステップＳ１２４において、係数並び替え用バッファ部１３に未処理の出力係数が存在しないと判定した場合、制御部２０１は、処理をステップＳ１２５に進める。

ステップＳ１２５において、制御部２０１は、１ピクチャ分の分析フィルタ処理が終了したか否かを判定する。つまり、制御部２０１は、ピクチャ内の全てのプレシンクトについて分析フィルタ処理（およびエントロピ符号化処理）を行ったか否かを判定する。未処理のプレシンクトが存在すると判定した場合、制御部２０１は、処理を図１５のステップＳ１０２に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ１０２乃至ステップＳ１２５の各処理を繰り返し実行することにより、全てのプレシンクトに対して上述したような制御処理を行う。

そして、ステップＳ１２５において、１ピクチャ分の分析フィルタ処理が終了したと判定した場合、制御部２０１は、制御処理を終了する。なお、この制御処理は、画像データのピクチャ毎に繰り返し実行される。

以上のように制御処理を行うことにより、制御部２０１は、分析フィルタ処理を効率よく行い、画像データバッファ部２２１として必要なメモリ容量を低減させる。また、制御部２０１は、最後のリフティング演算の出力係数を係数並び替え用バッファ部１３に蓄積させないようにすることにより、係数並び替え用バッファ部１３として必要なメモリ量を低減させるとともに、負荷や遅延時間を低減させることができる。

なお、図１５および図１６においては、制御処理の流れの例を説明したが、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７は、上述したように、この制御処理の各ステップに対応して制御部２０１の制御に対応する処理を実行する。従って、図１５および図１６のフローチャートに示される制御処理の各ステップは、上述したとおりに、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７のそれぞれが実行する処理も表しているものとし、各部が実行する処理の図示は省略する。

次に、他の処理進行方法について説明する。

図１１を参照して説明したように、復号部２０における第２プレシンクトに対する符号化処理は、符号化部１０における第２プレシンクトに対するウェーブレット変換処理が終了するまで開始することができない。そのため、図１２を参照して説明したように、CPU１０１は、ウェーブレット変換処理とエントロピ符号化処理をプレシンクト単位で交互に実行することになる。しかしながら、例えば、CPU１０１が各分析フィルタ処理をより高速に処理し、画像データ入力タイミング（水平同期タイミング）の間隔よりも早く終了させることができる場合、次の水平同期タイミング（分析フィルタ処理開始タイミング）まで待機時間が生じてしまい、CPU１０１の使用効率が低下してしまう。

例えば、図１２においても、ライン番号２１（およびライン番号２０）の画像データが入力されてから、分析フィルタ処理は３回行われるのに対し、ライン番号１６（およびライン番号１５）の画像データが入力されたときは、分析フィルタ処理は１回しか行われない。つまり、次のライン番号１８（およびライン番号１７）の画像データが入力されるまでに待機時間が生じる。このような待機時間が生じると、CPU１０１の使用効率が低下することになり、その効率が低い分だけ、処理実行時のCPU１０１にかかる負荷が増大することになる。従って、その分高性能なCPUを用いなければならず、製造コストや消費電力の増大にも繋がる。つまり、CPU１０１にかかる負荷を低減させるためには、CPU１０１の使用効率をより向上させる（より効率よくCPU１０１を動作させる）ことが求められる。

そこで、このような待機時間の発生を抑制し、CPU１０１の使用効率を向上させるために、図１７に示されるように、エントロピ符号化処理を行うプレシンクトを、ウェーブレット変換処理を行うプレシンクトよりも１つ遅延させる。換言すれば、符号化処理が、常に、リフティング演算により最後に生成された最低域の周波数成分よりも先に生成された周波数成分を符号化するようにする。さらに換言すれば、符号化処理の進行に対してウェーブレット変換処理の進行を、図１１を参照して説明した例の場合よりも早めるようにし、符号化処理が最低域の周波数成分を符号化する前に、ウェーブレット変換処理がその最低域の周波数成分を生成しているようにし、符号化処理が常に次の周波数成分を符号化することができるようにする。

図１７の例においては、符号化部１０における第３プレシンクトに対してウェーブレット変換処理を行いながら、復号部２０における第２プレシンクトに対して符号化処理を行う様子を示している。もちろん、他のプレシンクトについても同様であるのでその説明は省略する。

なお、図１７は、図１１に対応する図であるので、その詳細についての説明は省略する。図１７において、曲線２５１は、符号化部１０における第１プレシンクト（ライン番号０乃至ライン番号１４）と第２プレシンクト（ライン番号１５乃至ライン番号２２）との境界を示し、曲線２５２は、符号化部１０における第２プレシンクト（ライン番号１５乃至ライン番号２２）と第３プレシンクト（ライン番号２３乃至ライン番号３０）との境界を示している。

図１７に示されるように、符号化部１０における第３プレシンクトに対するウェーブレット変換処理により生成される出力係数（曲線２６１において囲まれる部分の黒丸（●）や黒四角（■））と、復号部２０における第２プレシンクトに対するエントロピ符号化において処理される出力係数（曲線１５２において囲まれる部分の黒丸（●）や黒四角（■））とは、互いに重複しない。従って、符号化部１０における第３プレシンクトに対するウェーブレット変換処理と、復号部２０における第２プレシンクトに対するエントロピ符号化を同時並行的に行うことができる。なお、CPU１０１は１つの演算処理部であるため、ここでいう「同時並行的」とは、２つの処理を実際に同時に並行して行うことではなく、２つの処理の開始から終了までの時間が互いに重複することを示す。より具体的に説明すると、CPU１０１を時分割して、ウェーブレット変換処理とエントロピ符号化処理のそれぞれを、より細かい処理単位で交互に実行させる。このようにすることにより、ウェーブレット変換処理の開始から終了までの時間と、エントロピ符号化処理の開始から終了までの時間が互いに重複するので、CPU１０１は、見かけ上、２つの処理を「同時並行的に」実行することができる。

つまり、図１７の例においては、CPU１０１は、符号化部１０における第３プレシンクトに対するウェーブレット変換処理として、ライン番号２３およびライン番号２４の画像データが入力されると、曲線２７１により囲まれるリフティング演算を行い、ライン番号２５およびライン番号２６の画像データが入力されると、曲線２７２により囲まれるリフティング演算を行い、ライン番号２７およびライン番号２８の画像データが入力されると、曲線２７３により囲まれるリフティング演算を行い、ライン番号２９およびライン番号３０の画像データが入力されると、曲線２７４により囲まれるリフティング演算を行う。これらの各処理の間に発生するCPU１０１の待機時間中に、曲線１５２により囲まれる部分の、復号部２０における第２プレシンクトに対するエントロピ符号化処理を、処理可能なライン数分だけCPU１０１に実行させるようにする。

図１８に、この場合の、CPU１０１において実行される処理の流れを模式的に示す。図１８は、図１２に対応する図であり、基本的には図１２と同様の構成であるので、その詳細についての説明は省略する。

図１８においても、CPU１０１は、図１２の場合と同様に、符号化部１０における第３プレシンクトについて、画像データが２ライン入力される毎に実行可能なリフティング演算（分析フィルタ処理）を行う（DWT（Lev１）乃至DWT（Lev３））。ただし、図１８の場合、CPU１０１は、リフティング演算終了後、次の２ラインが入力されるまでの間に（次のリフティング演算実行開始タイミングまでの間に）、復号部２０における第２プレシンクトに対するエントロピ符号化処理を、係数データのライン単位で実行する。

つまり、図１８において、ライン番号２４（および２３）の画像データが入力されると、CPU１０１は、図１７の曲線２７１に囲まれた部分のリフティング演算DWT（Lev１）を行い、２７番目に合成フィルタ処理される係数データを生成し、それを係数並び替え用バッファ部１３に保持させる。この後、CPU１０１は、次のリフティング演算実行開始タイミングまでの時間を利用して、５番目および６番目に合成フィルタ処理される係数データを順次エントロピ符号化し（VLC５およびVLC６）、それぞれの処理において得られた符号化データを順次出力する。

そして、ライン番号２６（および２５）の画像データが入力されると、CPU１０１は、図１７の曲線２７２に囲まれた部分のリフティング演算DWT（Lev１）およびDWT（Lev２）を行い、それぞれの処理において２８番目に合成フィルタ処理される係数データと２３番目に合成フィルタ処理される係数データを生成し、それらを順次係数並び替え用バッファ部１３に保持させる。その後、CPU１０１は、次のリフティング演算実行開始タイミングまでの時間を利用して、７番目乃至９番目に合成フィルタ処理される係数データを順次エントロピ符号化し（VLC７、VLC８、およびVLC９）、それぞれの処理において得られた符号化データを順次出力する。

次に、ライン番号２８（および２７）の画像データが入力されると、CPU１０１は、図１７の曲線２７３に囲まれた部分のリフティング演算DWT（Lev１）を行い、３１番目に合成フィルタ処理される係数データを生成し、それを係数並び替え用バッファ部１３に保持させる。その後、CPU１０１は、次のリフティング演算実行開始タイミングまでの時間を利用して、１０番目乃至１２番目に合成フィルタ処理される係数データを順次エントロピ符号化し（VLC１０、VLC１１、およびVLC１２）、それぞれの処理において得られた符号化データを順次出力する。

そして、ライン番号３０（および２９）の画像データが入力されると、CPU１０１は、図１７の曲線２７４に囲まれた部分のリフティング演算DWT（Lev１）、DWT（Lev２）、およびDWT（Lev３）を行い、それぞれの処理において２５番目に合成フィルタ処理される係数データ、１８番目に合成フィルタ処理される係数データ、２１番目に合成フィルタ処理される係数データ、および２２番目に合成フィルタ処理される係数データを生成し、それらを順次係数並び替え用バッファ部１３に保持させる。

このように、エントロピ符号化処理の処理対象プレシンクトを、ウェーブレット変換処理の処理対象プレシンクトに対して１つ遅らせる、すなわち、符号化処理が、常に、リフティング演算により最後に生成された最低域の周波数成分より先に生成された周波数成分を符号化するようにすることにより、CPU１０１は、ウェーブレット変換処理の空き時間を利用して、エントロピ符号化処理を実行することができ、見かけ上、ウェーブレット変換処理とエントロピ符号化処理を同時並行的に実行することができる。このようにすることにより、CPU１０１の待機時間を低減させることができ、CPU１０１の使用効率を向上させることができる。

また、これにより、CPU１０１は、容易に分析フィルタ処理をリアルタイム（即時的）に行うことができる。図１９に示されるように、CPU１０１は、２ライン分の画像データの入力タイミング（hsync）に合わせて、１プレシンクトに対するウェーブレット変換処理を複数回に分けて実行する（P１DWT、P２DWT、P３DWT、・・・、PｎDWT）。CPU１０１は、これらのウェーブレット変換処理の空き時間に、各出力係数に対する符号化処理を全て行う（P１VLC、P２VLC、・・・、Pｎ−１VLC、PｎVLC）。このようにエントロピ符号化処理を、各出力係数に対する処理を処理単位として、ウェーブレット変換処理の空き時間に行うことにより、高性能なCPU１０１でなくても、容易にウェーブレット変換をリアルタイム（即時的）に行うことができる。

従って、この場合、入力される画像データをバッファする必要が無く、画像データバッファ部２２１が不要になる。従って、図１２乃至図１６を参照して説明した方法の場合よりも、符号化部１０が行う処理に必要なメモリ量を低減させることができるだけでなく、画像データをバッファする時間を省略することができるので、ウェーブレット変換処理およびエントロピ符号化処理の負荷や遅延時間を低減させることができる。

なお、図１２の場合と図１８の場合を比較すると、図１８の場合の方が、ライン番号２４（および２３）の画像データが入力された後に行われるリフティング演算DWT（Lev１）の分だけ、５番目に合成フィルタ処理される係数データを符号化して得られる符号化データの出力タイミングが遅く、また、５番目、６番目、および２７番目に合成フィルタ処理される係数データの分だけ、係数並び替え用バッファ部１３に蓄積されるデータ量が多い。しかしながら、このリフティング演算DWT（Lev１）は、分割レベル１のリフティング演算１回分の遅延時間であり、図１８に示されるように２ライン分の画像データの入力タイミング（hsync）の間隔よりは短い。また、係数並び替え用バッファ部１３に蓄積される５番目に合成フィルタ処理される係数データは分割レベル３の低域成分１ライン分であり、６番目に合成フィルタ処理される係数データは分割レベル３の高域成分１ライン分であり、２７番目に合成フィルタ処理される係数データは分割レベル１の高域成分１ライン分であるので、そのデータ量は画像データ１ライン分より少ない（図４参照）。

図１２の方法において、エントロピ符号化によりウェーブレット変換処理をリアルタイムに行うことができない場合、１プレシンクト分のエントロピ符号化処理の処理時間は、２ライン分の画像データの入力タイミング（hsync）の間隔より長い。また、そのときの画像データバッファ部２２１に蓄積される画像データのデータ量は、画像データ２ライン分以上である。

従って、この入力画像データのバッファ分まで含めて比較すると、図１８の場合の方が、図１２の場合よりも、必要とするメモリ容量が少なく、かつ、遅延時間が短い。また、図１２の場合よりもCPU１０１の使用効率が高いため、より小さな負荷で、所定の速度で入力される画像データをリアルタイムに処理することができる。

なお、図１８の例の場合、５番目と６番目に合成フィルタ処理される係数データを係数並び替え用バッファ部１３に蓄積するように説明したが、図１２の場合と同様に、これらの係数データを係数並び替え用バッファ部１３に蓄積させずにエントロピ符号化処理するようにしてもよい。つまり、この場合、CPU１０１は、符号化部１０における第２プレシンクトの最後のリフティング演算終了後、第３プレシンクトに対するウェーブレット変換を開始する前に、復号部２０における第２プレシンクトに対するエントロピ符号化処理を開始することができる。このようにすることにより、CPU１０１は、５番目に合成フィルタ処理される係数データを符号化して得られる符号化データの出力タイミングをさらに早くすることができ、また、係数並び替え用バッファ部１３として必要なメモリ容量をさらに低減させることができる。

また、図１８の例の場合、図１９に示されるように符号化データの出力タイミングが分散される。従って、後段の処理の負荷を均一化させることができるので、再生ビデオ信号のように略一定の速度で入力される画像データ（１ラインずつ所定の間隔で入力される画像データ）に対してリアルタイムに処理を行うことが容易になる。例えば、符号化部１０の後段の処理として符号化データをパケット化する場合、図１８の例のように符号化データの生成レートが略一定であると、そのパケット化処理の負荷の変化量が低減されるので、パケット処理が容易になる。これに対して、図１２の例の場合、符号化データの出力タイミングは、エントロピ符号化処理が行われている期間に集中し、ムラが生じる。従って、パケット化処理の負荷の変化量が増大し、負荷がピークのときにオーバーフローしないようにパケット化処理を高速に実行するようにしたり、符号化データをバッファしたりする必要が生じ、それによりコスト、負荷、および遅延時間の増大を招く恐れがある。

なお、図１８の例は一例であり、エントロピ符号化処理は、リフティング処理の空き時間であれば任意に割り当てることができる。例えば、図１８においては、ライン番号２４（および２３）の画像データが入力された後に実行されるリフティング演算DWT（Lev１）の後の空き時間に、５番目と６番目に合成フィルタ処理される係数データの符号化（VLC５およびVLC６）を割り当てるように説明したが、さらに７番目以降に合成フィルタ処理される係数データの符号化（VLC７乃至VLC１２）を割り当てるようにしてもよい。また、ライン番号３０（および２９）の画像データが入力された後に実行されるリフティング演算DWT（Lev１）、DWT（Lev２）、およびDWT（Lev３）の後の空き時間に符号化を割り当てるようにしてもよい。

次に、このような流れで処理を実行する符号化部１０の実現化について、より具体的に説明する。図２０は、上述した流れで処理を実行する符号化部１０を実現するソフトウェアプログラムを実行するCPU１０１が有する機能を示す機能ブロック図である。

図２０は、図１４に対応する図であり、図１４に示されるブロックと対応するブロックには同一の番号を付してある。図２０の場合、図１４の場合より画像データバッファ部２２１が省略されるのみであり、CPU１０１が有する機能ブロックは基本的に図１４の場合と同様であり、制御部２０１、分析フィルタ処理実行部２１１、係数並び替え処理実行部２１２、エントロピ符号化処理実行部２１３、途中計算用データ読み出し部２１４、途中計算用データ書き込み部２１５、出力係数書き込み部２１６、および出力係数読み出し部２１７を有する。ただし、図２０の場合、制御部２０１は、画像データバッファ部２２１に関する制御は行わない。

図２０の制御部２０１は、図１の符号化部１０を実現するために、各部を制御する制御処理を実行する。図２１のフローチャートを参照して、その制御処理の流れの例を説明する。なお、この制御処理は、画像データのピクチャ毎に繰り返し実行される。

制御処理が開始されると、制御部２０１は、ステップＳ２０１において、所定ライン数（例えば２ラインまたは３ライン）分の画像データが入力されたか否かを判定し、入力されたと判定するまで待機する。そして、入力されたと判定した場合、制御部２０１は、処理をステップＳ２０２に進める。

ステップＳ２０２において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、途中計算用バッファ部１２より、これから行うリフティング演算に必要な途中計算用データを取得させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ読み出し部２１４を制御して、これから行うリフティング演算に必要な途中計算用データを、途中計算用バッファ部１２より読み出させ、供給させる（つまり、途中計算用データを取得する）。この制御により、途中計算用データ読み出し部２１４は、要求された途中計算用データを途中計算用バッファ部１２より読み出し、分析フィルタ処理実行部２１１に供給する。

ステップＳ２０３において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、リフティング演算１回分の分析フィルタ処理を実行させる。この制御により、分析フィルタ処理実行部２１１は、図１８を参照して説明したように、実行可能な分析フィルタ処理のリフティング演算を１回分実行する。

リフティング演算が行われると、制御部２０１は、ステップＳ２０４において、分析フィルタ処理実行部２１１を制御し、リフティング演算に用いられた画像データや係数データ、およびリフティング演算により得られた係数データのうち、次回以降のリフティング演算に利用するデータを途中計算用データとして途中計算用バッファ部１２に保持させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ書き込み部２１５に途中計算用データを供給するとともに、その途中計算用データ書き込み部２１５を制御し、供給した途中計算用データを途中計算用バッファ部１２に書き込ませる。この制御により、途中計算用データ書き込み部２１５は、分析フィルタ処理実行部２１１より供給された途中計算用データを、途中計算用バッファ部１２に書き込み、保持させる。

ステップＳ２０５において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、リフティング演算により得られた出力係数を、係数並び替え用バッファ部１３に保持させる。この制御により、分析フィルタ処理実行部２１１は、出力係数書き込み部２１６に出力係数を供給するとともに、その出力係数書き込み部２１６を制御し、供給した出力係数を係数並び替え用バッファ部１３に書き込ませる。この制御により、出力係数書き込み部２１６は、分析フィルタ処理実行部２１１より供給された出力係数を、係数並び替え用バッファ部１３に書き込み、保持させる。

ステップＳ２０６において、制御部２０１は、新たな画像データの入力無しに、さらにリフティング演算が可能であるか否かを判定し、可能であると判定した場合、処理をステップＳ２０２に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ２０２乃至ステップＳ２０６の処理を繰り返すことにより、図１８を参照して説明したように、入力された画像データに対応する、実行可能なリフティング演算を全て行わせる。

そして、ステップＳ２０６において、実行可能なリフティング演算が無くなったと判定した場合、制御部２０１は、処理をステップＳ２０７に進める。

ステップＳ２０７において、制御部２０１は、１ピクチャ分のフィルタ処理が終了したか否かを判定し、終了していないと判定した場合、処理をステップＳ２０８に進め、係数並び替え用バッファ部１３に保持されている、１つ前のプレシンクトより処理対象出力係数群を特定する。つまり、制御部２０１は、次のリフティング演算開始タイミングまでの空き時間に符号化する出力係数を、リフティング演算により最後に生成された最低域の周波数成分より先に生成された周波数成分の中から特定する。なお、分析フィルタ処理されたのが第１プレシンクトである場合、制御部２０１は、１つ前のピクチャの最後のプレシンクトを１つ前のプレシンクトとし、処理対象出力係数群を特定する。また、分析フィルタ処理されたのが先頭のピクチャの第１プレシンクトである場合、制御部２０１は、ステップＳ２０８乃至ステップＳ２１１の処理を省略し、処理をステップＳ２０１に戻し、それ以降の処理を実行させる。

ステップＳ２０９において、制御部２０１は、係数並び替え処理実行部２１２を制御し、処理対象出力係数として指定された係数データを所定順に読み出させる。この制御により、係数並び替え処理実行部２１２は、出力係数読み出し部２１７を制御し、係数並び替え用バッファ部１３に保持されている係数データ（処理対象出力係数）を、合成フィルタ処理を行う順に読み出させて供給させる。この制御により、出力係数読み出し部２１７は、係数並び替え用バッファ部１３に保持されている係数データを、合成フィルタ処理を行う順に読み出し、読み出した係数データを係数並び替え処理実行部２１２に供給させる。係数並び替え処理実行部２１２は、供給された係数データを順次エントロピ符号化処理実行部２１３に供給する。

ステップＳ２１０において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、係数並び替え用バッファ部１３より読み出された係数データをエントロピ符号化させる。この制御により、エントロピ符号化処理実行部２１３は、読み出された係数データを符号化し、得られた符号化データを出力する。

ステップＳ２１１において、制御部２０１は、係数並び替え用バッファ部１３に、符号化処理していない処理対象出力係数が存在するか否かを判定し、存在すると判定した場合、処理をステップＳ２０９に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ２０９乃至ステップＳ２１１の処理を繰り返すことにより、係数並び替え用バッファ部１３に保持されている全ての処理対象出力係数に対して符号化処理を実行させる。

ステップＳ２１１において、係数並び替え用バッファ部１３に未処理の処理対象出力係数が存在しないと判定した場合、制御部２０１は、処理をステップＳ２０１に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ２０１乃至ステップＳ２１１の処理を繰り返すことにより、ピクチャ内の全プレシンクトについて、ウェーブレット変換処理を実行させ、さらにその空き時間にエントロピ符号化処理を実行させることにより、ウェーブレット変換処理とエントロピ符号化処理を見かけ上、同時並行的に実行させる。

ステップＳ２０７において、１ピクチャ分のフィルタ処理が終了したと判定した場合、制御部２０１は、制御処理を終了する。なお、この制御処理が、画像データの最後のピクチャに対するものである場合、制御部２０１は、係数並び替え用バッファ部１３に保持されている残りの出力係数全てを処理対象出力係数群として特定し、ステップＳ２０９およびステップＳ２１１と同様の処理を行い、全出力係数を符号化し、その符号化データを出力してから制御処理を終了する。

以上のように制御処理を行うことにより、制御部２０１は、容易に、ウェーブレット変換処理とエントロピ符号化処理を同時並列的に実行し、所定の速度で入力される画像データよりリアルタイムに符号化データを生成して出力することができる。また、これにより、入力画像データの保持が不要になる。このように、ウェーブレット変換処理および符号化処理の負荷を低減させることができる。

なお、図２１においては、制御処理の流れの例を説明したが、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７は、上述したように、この制御処理の各ステップに対応して制御部２０１の制御に対応する処理を実行する。従って、図２１のフローチャートに示される制御処理の各ステップは、上述したとおりに、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７のそれぞれが実行する処理も表しているものとし、各部が実行する処理の図示は省略する。

次に、他の処理進行方法について説明する。

図１１を参照して説明したように、復号部２０における第２プレシンクトに対する符号化処理は、符号化部１０における第２プレシンクトに対するウェーブレット変換処理が終了するまで開始することができない。そこで、図２２に示されるように、符号化データを保持するコードバッファ部３１１を設け、符号化部１０における第２プレシンクトに対するウェーブレット変換処理の最後のリフティング演算よりも前に、それ以前に生成される係数データを符号化するようにしてもよい。つまり、この場合、CPU１０１は、合成フィルタ処理の処理順と異なる順序でエントロピ符号化処理を先に行い、得られた符号化データを保持することにより、符号化データを合成フィルタ処理の処理順に出力させる。

図２２に、この場合の、CPU１０１において実行される処理の流れを模式的に示す。図２２は、図１２に対応する図であり、基本的には図１２と同様の構成であるので、その詳細についての説明は省略する。

図２２においても、CPU１０１は、図１２の場合と同様に、符号化部１０における第２プレシンクトについて、画像データが２ライン入力される毎に実行可能なリフティング演算（分析フィルタ処理）を行う（DWT（Lev１）乃至DWT（Lev３））。ただし、図２２の場合、CPU１０１は、図１８の場合と同様に、リフティング演算終了後、次の２ラインが入力されるまでの間に（次のリフティング演算実行開始タイミングまでの間に）、復号部２０における第２プレシンクトに対するエントロピ符号化処理を、係数データのライン単位で実行する。

ただし、図２２の場合、このエントロピ符号化処理を、ウェーブレット変換の処理対象プレシンクトと同じプレシンクトに対して行う。すなわち、この場合のウェーブレット変換とエントロピ符号化処理の関係は、図１７ではなく図１１に示される例のようになる。つまり、上述したように、第２プレシンクトに対する分析フィルタ処理が開始された時点では、５番目および６番目に合成フィルタ処理される係数データは生成されていない。図２２の場合、CPU１０１は、これらの係数データの符号化よりも先に、既に生成され、係数並び替え用バッファ部１３に保持されている、復号部２０における第２プレシンクトの他の係数データ（すなわち、５番目および６番目に合成フィルタ処理される係数データに対応し、それらよりも高域成分である、７番目乃至１２番目に合成フィルタ処理される係数データ）の符号化を行う。

図２２の場合、これまでの例と異なり、符号化データを保持するコードバッファ部３１１が設けられている。処理対象プレシンクトの最後のリフティング演算により生成される係数データよりも先に符号化された、処理対象プレシンクトの他の係数データは、このコードバッファ部３１１に一旦保持される。そして、処理対象プレシンクトの最後のリフティング演算により生成される係数データが符号化されて出力されると、コードバッファ部３１１に保持されている符号化データが、合成フィルタ処理が行われる順に読み出されて出力される。

より具体的に説明すると、図２２の例の場合、ライン番号１６（および１５）の画像データが入力されると、CPU１０１は、図１１の曲線１６１に囲まれた部分のリフティング演算DWT（Lev１）を行い、１９番目に合成フィルタ処理される係数データを生成し、それを係数並び替え用バッファ部１３に保持させる。この後、CPU１０１は、次のリフティング演算実行開始タイミングまでの時間を利用して、７番目乃至９番目に合成フィルタ処理される係数データを順次エントロピ符号化し（VLC７、VLC８、およびVLC９）、それぞれの処理において得られた符号化データをコードバッファ部３１１に保持させる。

そして、ライン番号１８（および１７）の画像データが入力されると、CPU１０１は、図１１の曲線１６２に囲まれた部分のリフティング演算DWT（Lev１）およびDWT（Lev２）を行い、２０番目および１５番目に合成フィルタ処理される係数データを生成し、それらを順次係数並び替え用バッファ部１３に保持させる。

さらに、ライン番号２０（および１９）の画像データが入力されると、CPU１０１は、図１１の曲線１６３に囲まれた部分のリフティング演算DWT（Lev１）を行い、２４番目に合成フィルタ処理される係数データを生成し、それを係数並び替え用バッファ部１３に保持させる。この後、CPU１０１は、次のリフティング演算実行開始タイミングまでの時間を利用して、１０番目乃至１２番目に合成フィルタ処理される係数データを順次エントロピ符号化し（VLC１０、VLC１１、およびVLC１２）、それぞれの処理において得られた符号化データをコードバッファ部３１１に保持させる。

また、ライン番号２２（および２１）の画像データが入力されると、CPU１０１は、図１１の曲線１６４に囲まれた部分のリフティング演算DWT（Lev１）、DWT（Lev２）、およびDWT（Lev３）を行い、２５番目、１８番目、５番目、および６番目に合成フィルタ処理される係数データを生成し、２５番目および１８番目に合成フィルタ処理される係数データを順次係数並び替え用バッファ部１３に保持させる。この後、CPU１０１は、次のリフティング演算実行開始タイミングまでの時間を利用して、５番目および６番目に合成フィルタ処理される係数データを順次エントロピ符号化し（VLC５およびVLC６）、それぞれの処理において得られた符号化データを出力する。そして、CPU１０１は、コードバッファ部３１１に保持させた７番目乃至１２番目に合成フィルタ処理される係数データの符号化データを合成フィルタ処理順に読み出し、５番目および６番目に合成フィルタ処理される係数データの符号化データに続けて出力する。

つまり、図２３に示されるように、所定の速度で入力される画像データに対して、ウェーブレット変換処理とエントロピ符号化処理を、プレシンクトをずらすことなく、リアルタイムに実行することができる。このようにすることにより、CPU１０１は、生成した符号化データを、次のプレシンクトに対する分析フィルタ処理が開始される前に出力することができ、各符号化データの出力タイミングを、図１２の場合と同じままCPU１０１の使用効率を向上させることができる。さらに、図２２の例の場合、画像データバッファ部２２１を省略することができる。

ただし、図２２の例の場合、コードバッファ部３１１が必要になるので、その分、必要なメモリ容量が図１８の例の場合よりも増大する。ただし、コードバッファ部３１１においては、符号化データを蓄積するため、画像データを蓄積する場合よりもそのデータ量が低減される。すなわち、図１２の場合よりも、データのバッファに必要なメモリ容量を低減させることができる。

図１８の場合と比較すると、最初のピクチャの先頭のプレシンクトよりエントロピ符号化処理を行うことができるので、CPU１０１の使用効率は図２２の場合の方が高い。ただし、コードバッファ部３１１の分、必要なメモリ容量が増大する。また、符号化データの出力タイミングにムラがあるので、符号化部１０の後段の処理が図２２の場合の方が困難になる（負荷が大きくなる恐れがある）。

次に、このような流れで処理を実行する符号化部１０の実現化について、より具体的に説明する。図２４は、上述した流れで処理を実行する符号化部１０を実現するソフトウェアプログラムを実行するCPU１０１が有する機能を示す機能ブロック図である。

図２４も、図１４に対応する図であり、図１４に示されるブロックと対応するブロックには同一の番号を付してある。図２４の場合、CPU１０１は、図２０の場合と基本的に同様の機能ブロックを有するが、さらに、コードバッファ部３１１、符号化データ書き込み部３１２、および符号化データ読み出し部３１３を有する。

符号化データ書き込み部３１２および符号化データ読み出し部３１３は、制御部２０１に制御されて、キャッシュメモリ（図示せず）またはRAM１０３等に対して、エントロピ符号化処理において生成された符号化データの読み出しや書き込みを行うことにより、図２２のコードバッファ部３１１を、キャッシュメモリ（図示せず）またはRAM１０３等の記憶領域に形成させる。符号化データ書き込み部３１２は、エントロピ符号化処理実行部２１３より供給される符号化データをコードバッファ部３１１に書き込む（保持させる）。よび符号化データ読み出し部３１３は、コードバッファ部３１１に保持されている符号化データを、合成フィルタ処理の順に読み出してエントロピ符号化処理実行部２１３に供給する。

図２４の制御部２０１は、図１の符号化部１０を実現するために、各部を制御する制御処理を実行する。図２５および図２６のフローチャートを参照して、その制御処理の流れの例を説明する。なお、この制御処理は、画像データのピクチャ毎に繰り返し実行される。

制御処理が開始されると、制御部２０１は、ステップＳ３０１において、所定ライン数（例えば２ラインまたは３ライン）分の画像データが入力されたか否かを判定し、入力されたと判定するまで待機する。そして、入力されたと判定した場合、制御部２０１は、処理をステップＳ３０２に進める。

ステップＳ３０２において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、途中計算用バッファ部１２より、これから行うリフティング演算に必要な途中計算用データを取得させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ読み出し部２１４を制御して、これから行うリフティング演算に必要な途中計算用データを、途中計算用バッファ部１２より読み出させ、供給させる（つまり、途中計算用データを取得する）。この制御により、途中計算用データ読み出し部２１４は、要求された途中計算用データを途中計算用バッファ部１２より読み出し、分析フィルタ処理実行部２１１に供給する。

ステップＳ３０３において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、リフティング演算１回分の分析フィルタ処理を実行させる。この制御により、分析フィルタ処理実行部２１１は、図２２を参照して説明したように、実行可能な分析フィルタ処理のリフティング演算を１回分実行する。

リフティング演算が行われると、制御部２０１は、ステップＳ３０４において、分析フィルタ処理実行部２１１を制御し、リフティング演算に用いられた画像データや係数データ、およびリフティング演算により得られた係数データのうち、次回以降のリフティング演算に利用するデータを途中計算用データとして途中計算用バッファ部１２に保持させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ書き込み部２１５に途中計算用データを供給するとともに、その途中計算用データ書き込み部２１５を制御し、供給した途中計算用データを途中計算用バッファ部１２に書き込ませる。この制御により、途中計算用データ書き込み部２１５は、分析フィルタ処理実行部２１１より供給された途中計算用データを、途中計算用バッファ部１２に書き込み、保持させる。

ステップＳ３０５において、制御部２０１は、新たな画像データの入力無しに、さらにリフティング演算が可能であるか否かを判定し、可能であると判定した場合、処理をステップＳ３０６に進める。

ステップＳ３０６において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、リフティング演算により得られた出力係数を、係数並び替え用バッファ部１３に保持させる。この制御により、分析フィルタ処理実行部２１１は、出力係数書き込み部２１６に出力係数を供給するとともに、その出力係数書き込み部２１６を制御し、供給した出力係数を係数並び替え用バッファ部１３に書き込ませる。この制御により、出力係数書き込み部２１６は、分析フィルタ処理実行部２１１より供給された出力係数を、係数並び替え用バッファ部１３に書き込み、保持させる。

ステップＳ３０６の処理が終了すると、制御部２０１は、処理をステップＳ３０２に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ３０２乃至ステップＳ３０６の処理を繰り返すことにより、図２２を参照して説明したように、入力された画像データに対応する、実行可能なリフティング演算を全て行わせる。

そして、ステップＳ３０５において、実行可能なリフティング演算が無くなったと判定した場合、制御部２０１は、処理をステップＳ３０７に進める。ステップＳ３０７において、制御部２０１は、１プレシンクト分のフィルタ処理が終了したか否かを判定し、終了していないと判定した場合、処理をステップＳ３０８に進める。

ステップＳ３０８において、制御部２０１は、分析フィルタ処理実行部２１１を制御し、リフティング演算により得られた出力係数を、係数並び替え用バッファ部１３に保持させる。この制御により、分析フィルタ処理実行部２１１は、出力係数書き込み部２１６に出力係数を供給するとともに、その出力係数書き込み部２１６を制御し、供給した出力係数を係数並び替え用バッファ部１３に書き込ませる。この制御により、出力係数書き込み部２１６は、分析フィルタ処理実行部２１１より供給された出力係数を、係数並び替え用バッファ部１３に書き込み、保持させる。

ステップＳ３０９において、制御部２０１は、係数並び替え用バッファ部１３に保持されている現在の処理対象プレシンクトの係数データより、処理対象出力係数群を特定する。つまり、制御部２０１は、次のリフティング演算開始タイミングまでの空き時間に符号化する出力係数を特定する。

ステップＳ３１０において、制御部２０１は、係数並び替え処理実行部２１２を制御し、処理対象出力係数として指定された係数データを所定順に読み出させる。この制御により、係数並び替え処理実行部２１２は、出力係数読み出し部２１７を制御し、係数並び替え用バッファ部１３に保持されている係数データ（処理対象出力係数）を、合成フィルタ処理を行う順に読み出させて供給させる。この制御により、出力係数読み出し部２１７は、係数並び替え用バッファ部１３に保持されている係数データを、合成フィルタ処理を行う順に読み出し、読み出した係数データを係数並び替え処理実行部２１２に供給させる。係数並び替え処理実行部２１２は、供給された係数データを順次エントロピ符号化処理実行部２１３に供給する。

ステップＳ３１１において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、係数並び替え用バッファ部１３より読み出された係数データをエントロピ符号化させる。この制御により、エントロピ符号化処理実行部２１３は、読み出された係数データを符号化する。

ステップＳ３１２において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、ステップＳ３１１において生成された符号化データをコードバッファ部３１１に保持させる。この制御により、エントロピ符号化処理実行部２１３は、符号化データ書き込み部３１２に符号化データを供給するとともに、符号化データ書き込み部３１２を制御し、供給した符号化データをコードバッファ部３１１に書き込ませる。この制御により、符号化データ書き込み部３１２は、エントロピ符号化処理実行部２１３より供給された出力係数を、コードバッファ部３１１に書き込み、保持させる。

ステップＳ３１３において、制御部２０１は、係数並び替え用バッファ部１３に、符号化処理していない処理対象出力係数が存在するか否かを判定し、存在すると判定した場合、処理をステップＳ３１０に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ３１０乃至ステップＳ３１３の処理を繰り返すことにより、係数並び替え用バッファ部１３に保持されている全ての処理対象出力係数に対して符号化処理を実行させる。

ステップＳ３１３において、係数並び替え用バッファ部１３に未処理の処理対象出力係数が存在しないと判定した場合、制御部２０１は、処理をステップＳ３０１に戻し、それ以降の処理を繰り返す。つまり、制御部２０１は、ステップＳ３０１乃至ステップＳ３１３の処理を繰り返すことにより、ピクチャ内の全プレシンクトについて、ウェーブレット変換処理を実行させ、さらにその空き時間にエントロピ符号化処理を実行させることにより、ウェーブレット変換処理とエントロピ符号化処理を見かけ上同時並行的に実行させる。

ステップＳ３０７において、１プレシンクト分のフィルタ処理が終了したと判定した場合、制御部２０１は、処理を図２６のステップＳ３２１に進める。

図２６のステップＳ３２１において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、最後のリフティング演算の出力係数をエントロピ符号化させる。つまり、この最後のリフティング演算の出力係数は、係数並び替え用バッファ部１３を介さずにエントロピ符号化させる。

ステップＳ３２１の制御により、エントロピ符号化処理実行部２１３は、例えば５番目に合成フィルタ処理される係数データおよび６番目に合成フィルタ処理される係数データを順に符号化し、得られた符号化データを順次出力する。

その符号化処理が終了すると、制御部２０１は、ステップＳ３２２において、符号化データ読み出し部３１３を制御し、コードバッファ部３１１より符号化データを所定順に読み出させる。この制御により、符号化データ読み出し部３１３は、コードバッファ部３１１に保持されている符号化データを、例えば合成フィルタ処理順に読み出し、それをエントロピ符号化処理実行部２１３に供給する。エントロピ符号化処理実行部２１３は、その供給された符号化データを、ステップＳ３２１において符号化して出力した符号化データに続けて出力する。

ステップＳ３２３において、制御部２０１は、１ピクチャ分のフィルタ処理が終了したか否かを判定し、１ピクチャ分のフィルタ処理が終了して無いと判定した場合、処理を図２５のステップＳ３０１に戻し、それ以降の処理を繰り返す。

また、ステップＳ３２３において、１ピクチャ分のフィルタ処理が終了したと判定された場合、制御部２０１は、処理をステップＳ３２４に進め、係数並び替え用バッファ部１３に保持されている残りの出力係数を処理対象出力係数群に設定する。

制御部２０１は、ステップＳ３２５において、係数並び替え処理実行部２１２を制御し、処理対象出力係数として指定された係数データを所定順に読み出させる。この制御により、係数並び替え処理実行部２１２は、出力係数読み出し部２１７を制御し、係数並び替え用バッファ部１３に保持されている係数データ（処理対象出力係数）を、合成フィルタ処理を行う順に読み出させて供給させる。この制御により、出力係数読み出し部２１７は、係数並び替え用バッファ部１３に保持されている係数データを、合成フィルタ処理を行う順に読み出し、読み出した係数データを係数並び替え処理実行部２１２に供給させる。係数並び替え処理実行部２１２は、供給された係数データを順次エントロピ符号化処理実行部２１３に供給する。

ステップＳ３２６において、制御部２０１は、エントロピ符号化処理実行部２１３を制御し、係数並び替え用バッファ部１３より読み出された係数データをエントロピ符号化させる。この制御により、エントロピ符号化処理実行部２１３は、読み出された係数データを符号化し、得られた符号化データを出力する。

ステップＳ３２７において、制御部２０１は、係数並び替え用バッファ部１３に、符号化処理していない処理対象出力係数が存在するか否かを判定し、存在すると判定した場合、処理をステップＳ３２５に戻し、それ以降の処理を繰り返す。

ステップＳ３２７において、係数並び替え用バッファ部１３に未処理の処理対象出力係数が存在しないと判定した場合、制御部２０１は、制御処理を終了する。

以上のように制御処理を行うことにより、制御部２０１は、ウェーブレット変換処理とエントロピ符号化処理を同時並列的に実行し、より容易に、所定の速度で入力される画像データよりリアルタイムに符号化データを生成して出力することができる。また、これにより、保持するデータを符号化データにすることができるので、処理に必要なメモリ量を低減させ、ウェーブレット変換処理および符号化処理の負荷を低減させることができる。

なお、図２５および図２６においては、制御処理の流れの例を説明したが、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７は、上述したように、この制御処理の各ステップに対応して制御部２０１の制御に対応する処理を実行する。従って、図２５および図２６のフローチャートに示される制御処理の各ステップは、上述したとおりに、分析フィルタ処理実行部２１１乃至符号化データ読み出し部３１３のそれぞれが実行する処理も表しているものとし、各部が実行する処理の図示は省略する。

以上においては、図１０を参照して説明したように、処理演算部としてのCPUが１つであるパーソナルコンピュータ１００においてソフトウェアプログラムを実行する場合について説明したが、近年においては、CPUを複数有する情報処理装置も多く存在する。また、情報処理装置がCPUを１つしか有していなくても、そのCPUが、互いに独立して動作することができるコアを複数有する場合もある。このように、互いに独立して動作する複数の演算処理部を有する情報処理装置は、複数の処理を互いに並行して実行することができる。以下においては、このような互いに独立して動作する複数の演算処理部を有する情報処理装置を用いて、上述したようなソフトウェアエンコーダを実現させる場合について説明する。

図２７は、パーソナルコンピュータの他の構成例を示すブロック図である。図２７に示されるパーソナルコンピュータ４００は、基本的に図１０に示されるパーソナルコンピュータ１００と同様の構成を有する。すなわち、パーソナルコンピュータ４００は、パーソナルコンピュータ１００のROM１０２と同様のROM４０３、パーソナルコンピュータ１００のRAM１０３と同様のRAM４０４、パーソナルコンピュータ１００のバス１０４と同様のバス４０５、パーソナルコンピュータ１００の入出力インタフェース１１０と同様の入出力インタフェース４１０、パーソナルコンピュータ１００の入力部１１１と同様の入力部４１１、パーソナルコンピュータ１００の出力部１１２と同様の出力部４１２、パーソナルコンピュータ１００の記憶部１１３と同様の記憶部４１３、パーソナルコンピュータ１００の通信部１１４と同様の通信部４１４、および、パーソナルコンピュータ１００のドライブ１１５と同様のドライブ４１５を有する。ドライブ４１５には、パーソナルコンピュータ１００のリムーバブルメディア１２１と同様のリムーバブルメディア４２１が適宜装着される。

しかしながら、パーソナルコンピュータ４００は、パーソナルコンピュータ１００が１つのCPU１０１を有するのと異なり、CPU４０１およびCPU４０２を有する。CPU４０１およびCPU４０２のそれぞれは、基本的にCPU１０１と同様である。CPU４０１とCPU４０２は、互いに独立して処理を実行することができる。すなわち、パーソナルコンピュータ４００は、互いに独立して動作する２つの演算処理部（CPU４０１およびCPU４０２）を有する。

このようなパーソナルコンピュータ４００において図１の符号化部１０を実現させる場合、CPU４０１とCPU４０２とを使用して、図２８のように処理が実行される。図２８に、CPU４０１およびCPU４０２において実行される処理の流れを模式的に示す。図２８は、図１２に対応する図であり、基本的には図１２と同様の構成であるので、その詳細についての説明は省略する。

図２８の例の場合、互いに独立して動作する２つの演算処理部（CPU４０１およびCPU４０２）が存在するので、一方の演算処理部であるCPU４０１において、ウェーブレット変換処理を実行させ、他方の演算処理部であるCPU４０２において、エントロピ符号化処理を実行させる。このようにすることにより、ウェーブレット変換処理とエントロピ符号化処理を互いに並行して実行することができる。図２８の例の場合、上述した例と異なり、時分割による見かけ上の並列化ではなく、２つの演算処理部を用いて２つの処理を実際に並行して動作させる。

上述した他の例と同様に、一方のCPU４０１は、画像データが２ライン入力される毎に実行可能なリフティング演算（DWT）を行い、出力係数を生成して係数並び替え用バッファ部１３に保持させる。この分析フィルタ処理の実行中に、他方のCPU４０２は、この分析フィルタ処理と並行して、係数並び替え用バッファ部１３に蓄積されている出力係数を、合成フィルタ処理を行う順に読み出してエントロピ符号化（VLC）し、得られた符号化データを順次出力する。

このように２つの演算処理部を用いることにより、各CPUの負荷が低減される。従って、上述した他の例の場合よりも低速に動作するCPUであってもオーバーフローせずに、所定の速度で入力される画像データに対して、ウェーブレット変換処理とエントロピ符号化処理を容易にリアルタイムに実行することができる。

また、図２９に示されるように、この場合、CPU４０１が第２プレシンクトに対してウェーブレット変換（P２DWT）を行っているのと並行して、CPU４０２が第１プレシンクトに対してエントロピ符号化を行う（P１VLC）。従って、この場合の遅延時間は、上述した他の例と略同じである。また、CPU４０２は、符号化処理のみを行うので、符号化データの出力タイミングを適宜分散させることができる。従って、符号化部１０の後段の処理が容易になる。

また、図２８に示されるように、CPU４０１が、出力係数を係数並び替え用バッファ部１３に保持させるのと並行してCPU４０２が出力係数を読み出す。従って、係数並び替え用バッファ部１３に同時に保持されるデータ量は、上述した他の例より少なくなる。つまり、この場合、係数並び替え用バッファ部１３として必要なメモリ容量を低減させることができる。

ただし、この場合、CPU４０１とCPU４０２とで動作を連携させる必要があり、CPU４０１において実行される処理と、CPU４０２において実行される処理の両方を制御する仕組みが必要になる。

図３０は、上述した流れで処理を実行する符号化部１０を実現するソフトウェアプログラムを実行するCPU４０１およびCPU４０２が有する機能を示す機能ブロック図である。

図３０も、図１４に対応する図であり、図１４に示されるブロックと対応するブロックには同一の番号を付してある。図３０の場合、図１４や図２０に示される分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７の各処理部は、CPU４０１またはCPU４０２に割り当てられる。

CPU４０１は、分析フィルタ処理に関する機能を有しており、分析フィルタ処理実行部２１１、途中計算用データ読み出し部２１４、途中計算用データ書き込み部２１５、および出力係数書き込み部２１６を有する。CPU４０２は、係数並び替えおよびエントロピ符号化に関する機能を有しており、係数並び替え処理実行部２１２、エントロピ符号化処理実行部２１３、および出力係数読み出し部２１７を有する。

なお、図３０の例においては、途中計算用バッファ部１２がCPU４０１のキャッシュメモリ（図示せず）に形成され、係数並び替え用バッファ部１３がRAM４０４に形成されるものとして説明を行うが、上述したように、途中計算用バッファ部１２および係数並び替え用バッファ部１３は、任意の記憶領域に形成することができる。ただし、アクセス頻度の高い途中計算用バッファ部１２は、負荷や遅延時間を低減させるために、分析フィルタ処理が行われるCPU４０１のキャッシュメモリに形成させるのが望ましい。

図３０に示されるように、CPU４０１およびCPU４０２の両方の機能ブロックにより、上述した他の例のCPU１０１と同様に、図１の符号化部１０を実現する。つまり、CPU４０１において、画像データに対して分析フィルタ処理が行われ、その出力係数が係数並び替え用バッファ部１３に保持され、CPU４０２において、その出力係数を合成フィルタ処理を行う順に読み出し、各係数に対して符号化処理を行い、符号化データを生成して出力する。

CPU４０１は、さらに、制御部５１１および分析フィルタ制御部５１２を有し、CPU４０２は、さらに、並び替え符号化制御部５１３を有する。

制御部５１１は、CPU４０１の分析フィルタ制御部５１２およびCPU４０２の並び替え符号化制御部５１３の動作を制御する。分析フィルタ制御部５１２は、CPU４０１が有する各機能ブロックの動作を制御し、CPU４０１において実行される分析フィルタ処理に関する制御を行う。並び替え符号化制御部５１３は、CPU４０２が有する各機能ブロックの動作を制御し、CPU４０２において実行される係数の並び替えやエントロピ符号化に関する制御を行う。

図３１のフローチャートを参照して、制御部５１１が実行する制御処理の流れの例を説明する。なお、この制御処理は、入力される画像データのピクチャ毎に実行される。

制御処理が開始されると、制御部５１１は、ステップＳ４０１において、分析フィルタ制御部５１２を制御し、分析フィルタ制御処理を開始させる。この制御により、分析フィルタ制御部５１２は、分析フィルタ制御処理を開始する。分析フィルタ制御処理については後述する。ステップＳ４０２において、制御部５１１は、並び替え符号化制御部５１３を制御し、並び替え符号化制御処理を開始させる。この制御により、並び替え符号化制御部５１３は、並び替え符号化制御処理を開始する。並び替え符号化制御処理については後述する。

図３２のフローチャートを参照して、分析フィルタ制御部５１２が実行する分析フィルタ制御処理の流れの例を説明する。

分析フィルタ制御処理が開始されると、分析フィルタ制御部５１２は、ステップＳ４１１において、所定ライン数（例えば２ラインまたは３ライン）分の画像データが入力されたか否かを判定し、入力されたと判定するまで待機する。そして、入力されたと判定した場合、分析フィルタ制御部５１２は、処理をステップＳ４１２に進める。

ステップＳ４１２において、分析フィルタ制御部５１２は、分析フィルタ処理実行部２１１を制御し、途中計算用バッファ部１２より、これから行うリフティング演算に必要な途中計算用データを取得させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ読み出し部２１４を制御して、これから行うリフティング演算に必要な途中計算用データを、途中計算用バッファ部１２より読み出させ、供給させる（つまり、途中計算用データを取得する）。この制御により、途中計算用データ読み出し部２１４は、要求された途中計算用データを途中計算用バッファ部１２より読み出し、分析フィルタ処理実行部２１１に供給する。

ステップＳ４１３において、分析フィルタ制御部５１２は、分析フィルタ処理実行部２１１を制御し、リフティング演算１回分の分析フィルタ処理を実行させる。この制御により、分析フィルタ処理実行部２１１は、図２８を参照して説明したように、実行可能な分析フィルタ処理のリフティング演算を１回分実行する。

リフティング演算が行われると、分析フィルタ制御部５１２は、ステップＳ４１４において、分析フィルタ処理実行部２１１を制御し、リフティング演算に用いられた画像データや係数データ、およびリフティング演算により得られた係数データのうち、次回以降のリフティング演算に利用するデータを途中計算用データとして途中計算用バッファ部１２に保持させる。この制御により、分析フィルタ処理実行部２１１は、途中計算用データ書き込み部２１５に途中計算用データを供給するとともに、その途中計算用データ書き込み部２１５を制御し、供給した途中計算用データを途中計算用バッファ部１２に書き込ませる。この制御により、途中計算用データ書き込み部２１５は、分析フィルタ処理実行部２１１より供給された途中計算用データを、途中計算用バッファ部１２に書き込み、保持させる。

ステップＳ４１５において、分析フィルタ制御部５１２は、分析フィルタ処理実行部２１１を制御し、リフティング演算により得られた出力係数を、係数並び替え用バッファ部１３に保持させる。この制御により、分析フィルタ処理実行部２１１は、出力係数書き込み部２１６に出力係数を供給するとともに、その出力係数書き込み部２１６を制御し、供給した出力係数を係数並び替え用バッファ部１３に書き込ませる。この制御により、出力係数書き込み部２１６は、分析フィルタ処理実行部２１１より供給された出力係数を、係数並び替え用バッファ部１３に書き込み、保持させる。

ステップＳ４１６において、分析フィルタ制御部５１２は、新たな画像データの入力無しに、さらにリフティング演算が可能であるか否かを判定し、可能であると判定した場合、処理をステップＳ４１２に戻し、それ以降の処理を繰り返す。つまり、分析フィルタ制御部５１２は、ステップＳ４１２乃至ステップＳ４１６の処理を繰り返すことにより、図２８を参照して説明したように、入力された画像データに対応する、実行可能なリフティング演算を全て行わせる。

そして、ステップＳ４１６において、実行可能なリフティング演算が無くなったと判定した場合、分析フィルタ制御部５１２は、処理をステップＳ４１７に進める。ステップＳ４１７において、分析フィルタ制御部５１２は、１ピクチャ分のフィルタ処理が終了したか否かを判定し、１ピクチャ分のフィルタ処理が終了して無いと判定した場合、処理をステップＳ４１１に戻し、それ以降の処理を繰り返す。

また、ステップＳ４１７において、１ピクチャ分のフィルタ処理が終了したと判定された場合、分析フィルタ制御部５１２は、分析フィルタ制御処理を終了する。

次に、図３３のフローチャートを参照して、並び替え符号化制御部５１３が実行する並び替え符号化制御処理の流れの例を説明する。

並び替え符号化制御処理が開始されると、並び替え符号化制御部５１３は、ステップＳ４２１において、係数並び替え用バッファ部１３に、符号化処理していない出力係数が存在するか否かを判定し、存在すると判定した場合、処理をステップＳ４２２に進める。ステップＳ４２２において、並び替え符号化制御部５１３は、係数並び替え処理実行部２１２を制御し、係数並び替え用バッファ部１３に保持されている出力係数を所定順に読み出させる。この制御により、係数並び替え処理実行部２１２は、出力係数読み出し部２１７を制御し、係数並び替え用バッファ部１３に保持されている係数データ（出力係数）を、合成フィルタ処理を行う順に読み出させて供給させる。この制御により、出力係数読み出し部２１７は、係数並び替え用バッファ部１３に保持されている係数データを、合成フィルタ処理を行う順に読み出し、読み出した係数データを係数並び替え処理実行部２１２に供給させる。係数並び替え処理実行部２１２は、供給された係数データを順次エントロピ符号化処理実行部２１３に供給する。

ステップＳ４２３において、並び替え符号化制御部５１３は、エントロピ符号化処理実行部２１３を制御し、係数並び替え用バッファ部１３より読み出された係数データをエントロピ符号化させる。この制御により、エントロピ符号化処理実行部２１３は、読み出された係数データを符号化し、得られた符号化データを出力する。

ステップＳ４２３の処理を終了すると、並び替え符号化制御部５１３は、処理をステップＳ４２４に進める。また、ステップＳ４２１において、未処理の出力係数が存在しないと判定した場合、並び替え符号化制御部５１３は、ステップＳ４２２およびステップＳ４２３の処理を省略し、処理をステップＳ４２４に進める。

ステップＳ４２４において、並び替え符号化制御部５１３は、１ピクチャ分のフィルタ処理が終了したか否かを判定し、１ピクチャ分のフィルタ処理が終了していないと判定した場合、処理をステップＳ４２１に戻し、それ以降の処理を繰り返す。

また、ステップＳ４２４において、１ピクチャ分のフィルタ処理が終了したと判定された場合、並び替え符号化制御部５１３は、並び替え符号化制御処理を終了する。

以上のように各制御処理を行うことにより、制御部５１１、分析フィルタ制御部５１２、および並び替え符号化制御部５１３は、ウェーブレット変換処理とエントロピ符号化処理を、２つの演算処理部を利用して実際に並行して実行し、容易に、所定の速度で入力される画像データよりリアルタイムに符号化データを生成して出力することができる。

なお、図２７においては、CPUの個数が２つであるように説明したが、上述した処理は、３つ以上のCPUを有するパーソナルコンピュータにおいても実行可能である。また、図２６より前の図面を参照して説明した他の制御方法を、図２７に示されるパーソナルコンピュータ４００のように複数の演算処理部を有する情報処理装置において実行することもできる。

また、以上に説明した各実施の形態においては、それぞれの制御部が、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７等の各処理部を制御するように説明したが、上述した制御処理は、分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７等の各処理部において行われるようにしてもよい。つまり、制御部を別途設けずに、実際にデータを処理する分析フィルタ処理実行部２１１乃至出力係数読み出し部２１７等の各処理部が適宜互いを制御しあうようにしてもよい。

以上においては、ウェーブレット変換処理をリフティング演算処理１回分毎に制御し、また、符号化処理を各係数データに対する処理毎に制御するように説明したが、ウェーブレット変換処理および符号化処理のそれぞれを複数の工程に分割する処理単位であれば、どの様な処理単位で制御するようにしてもよい。例えば、ウェーブレット変換処理をリフティング演算処理１回分よりもさらに細かい処理単位で制御するようにし、より細かな制御を行いCPUの使用効率をさらに向上させることができるようにしてもよいし、複数のリフティング演算処理を処理単位とし、制御処理をより簡易化するようにしてもよい。また、例えば、符号化処理を係数データ毎の処理よりさらに細かい処理単位で制御するようにし、より細かな制御を行いCPUの使用効率をさらに向上させることができるようにしてもよいし、複数の係数データに対する処理を処理単位とし、制御処理をより簡易化するようにしてもよい。

また、以上においては分析フィルタ処理に５×３フィルタを用いるように説明したが、フィルタ処理に使用されるフィルタはどの様なフィルタを用いてもよく、例えば、９×７フィルタを用いるようにしてもよい。

上述した一連の処理は、ソフトウェアにより実行させることもできるが、ハードウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータ、または、複数の装置よりなる情報処理システムの情報処理装置などに、プログラム記録媒体からインストールされる。

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

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

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

なお、以上において、１つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて１つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。つまり、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。

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

符号化部の構成例を示す図である。 復号部の構成例を示す図である。 ウェーブレット変換について概略的に説明するための略線図である。 ウェーブレット変換について概略的に説明するための略線図である。 ウェーブレット変換について概略的に説明するための略線図である。 ５×３分析フィルタのリフティング構成の例を説明する図である。 ５×３合成フィルタのリフティング構成の例を説明する図である。 分析フィルタ処理および合成フィルタ処理の流れの例を説明する図である。 符号化側および復号側の各処理が並列的に実行される様子を説明するための略線図である。 パーソナルコンピュータの主な構成例を示すブロック図である。 ウェーブレット変換処理とエントロピ符号化処理の流れの関係の例を説明する図である。 CPUにおいて実行される処理の流れの例を説明する模式図である。 CPUにおいて実行される処理の流れの例を説明する模式図である。 CPUが有する機能の構成例を説明する機能ブロック図である。 制御処理の流れの例を説明するフローチャートである。 制御処理の流れの例を説明する、図１５に続くフローチャートである。 ウェーブレット変換処理とエントロピ符号化処理の流れの関係の他の例を説明する図である。 CPUにおいて実行される処理の流れの、他の例を説明する模式図である。 CPUにおいて実行される処理の流れの、他の例を説明する模式図である。 CPUが有する機能の、他の構成例を説明する機能ブロック図である。 制御処理の流れの、他の例を説明するフローチャートである。 CPUにおいて実行される処理の流れの、さらに他の例を説明する模式図である。 CPUにおいて実行される処理の流れの、さらに他の例を説明する模式図である。 CPUが有する機能の、さらに他の構成例を説明する機能ブロック図である。 制御処理の流れの、さらに他の例を説明するフローチャートである。 制御処理の流れの、さらに他の例を説明する、図２５に続くフローチャートである。 パーソナルコンピュータの、他の主な構成例を示すブロック図である。 CPUにおいて実行される処理の流れの、さらに他の例を説明する模式図である。 CPUにおいて実行される処理の流れの、さらに他の例を説明する模式図である。 CPUが有する機能の、さらに他の構成例を説明する機能ブロック図である。 制御処理の流れの、さらに他の例を説明するフローチャートである。 分析フィルタ制御制御処理の流れの例を説明するフローチャートである。 並び替え符号化制御処理の流れの例を説明するフローチャートである。

符号の説明

１０ 符号化部， １１ ウェーブレット変換部， １２ 途中計算用バッファ部， １３ 係数並び替え用バッファ部， １４ 係数並び替え部， １５ エントロピ符号化部， １００ パーソナルコンピュータ， １０１ CPU， ２０１ 制御部， ２１１ 分析フィルタ処理実行部， ２１２ 係数並び替え処理実行部， ２１３ エントロピ符号化処理実行部， ２１４ 途中計算用データ読み出し部， ２１５ 途中計算用データ書き込み部， ２１６ 出力係数書き込み部， ２１７ 出力係数読み出し部， ２２１ 画像データバッファ部， ３１１ コードバッファ部， ３１２ 符号化データ書き込み部， ３１３ 符号化データ読み出し部， ４０１および４０２ CPU， ５１１ 制御部， ５１２ 分析フィルタ制御部， ５１３ 並び替え符号化制御部

Claims (8)

1. 画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理手段と、
   前記分析フィルタ処理手段により、帯域毎に分割された前記周波数成分を可変長符号化する符号化手段と、
   前記分析フィルタ処理手段を制御し、画像データが２ライン入力される毎に、前記リフティング演算の、実行可能な演算を実行させ、さらに、前記符号化手段を制御し、前記演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させる制御手段と
   を備える情報処理装置。
2. 前記制御手段は、
   前記分析フィルタ処理手段に、実行可能な演算のうち、より高域の周波数成分を生成する演算を、より先に実行させ、
   前記符号化手段に、符号化可能な周波数成分のうち、より低域の周波数成分であり、かつ、同じ帯域の中では、より先に生成された周波数成分を、より先に可変長符号化させる
   請求項１に記載の情報処理装置。
3. 前記制御手段は、前記符号化手段に、常に、前記リフティング演算により直前に生成された最低域の周波数成分より先に生成された周波数成分を可変長符号化させる
   請求項２に記載の情報処理装置。
4. 前記符号化手段により前記周波数成分が符号化されて得られた符号化データを保持する符号化データ保持手段をさらに備え、
   前記制御手段は、前記リフティング演算により最低域の周波数成分が生成されるよりも先に、前記最低域の周波数成分に対応する、前記最低域の周波数成分よりも高域の周波数成分を符号化させ、得られた符号化データを前記符号化データ保持手段に保持させ、前記最低域の周波数成分が生成され符号化され出力された後に、前記符号化データ保持手段に保持されている前記符号化データを所定の順に出力させる
   請求項２に記載の情報処理装置。
5. 前記分析フィルタ処理手段により帯域毎に分割された周波数成分を保持する周波数成分保持手段をさらに備え、
   前記符号化手段は、前記周波数成分保持手段に保持されている前記周波数成分を可変長符号化する
   請求項１に記載の画像処理装置。
6. 情報処理装置の情報処理方法であって、
   画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理部を制御し、前記画像データが２ライン入力される毎に、前記リフティング演算の、実行可能な演算を実行させ、
   帯域毎に分割された前記周波数成分を可変長符号化する符号化部を制御し、前記演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させる
   ステップを含む情報処理方法。
7. 画像データの周波数成分をリフティング演算により帯域毎に分割する分析フィルタ処理手段と、
   前記分析フィルタ処理手段により、帯域毎に分割された前記周波数成分を可変長符号化する符号化手段と、
   前記符号化手段を制御し、入力された複数ラインの画像データを用いて行われた、前記リフティング演算の実行可能な演算が終了してから、次の画像データの複数ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させる制御手段と
   を備える情報処理装置。
8. 情報処理装置の情報処理方法であって、
   リフティング演算によって帯域毎に分割された画像データの周波数成分を可変長符号化する符号化部を制御し、分析フィルタ処理部において前記画像データが２ライン入力される毎に行われる、前記リフティング演算の、実行可能な演算が終了してから、次の画像データ２ラインが入力されるまでの間に、符号化可能な周波数成分を可変長符号化させる
   ステップを含む情報処理方法。

Images