(57)【要約】【課題】ウェーブレット変換処理のメモリ使用量を低減させることができるようにする。【解決手段】スケジューラ１１１は、水平分析フィルタリングにおける画像左端の場合や、垂直分析フィルタリングにおける画像上端の場合のように、利用可能な演算用係数が存在しない状態を「非定常状態」とする。また、スケジューラ１１１は、水平分析フィルタリングにおける画像左端以外の場合や、垂直分析フィルタリングにおける画像上端以外の場合のように、利用可能な演算用係数が存在する状態を「定常状態」とする。そして、スケジューラ１１１は、水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、各状態において必要なコラム分のデータが入力される度に分析フィルタリングを実行させる。本発明は、例えば、ウェーブレット変換装置に適用することができる。【選択図】図１
2010136154.tif 000002
【特許請求の範囲】
【請求項１】
画像信号に対してウェーブレット変換を行う情報処理装置であって、
前記画像信号の周波数成分を、水平方向に、低域成分および高域成分に分割する水平分析フィルタリングを行う水平分析フィルタ手段と、
前記水平分析フィルタ手段による前記水平分析フィルタリングにより分割された前記低域成分および前記高域成分を、それぞれ、垂直方向に、低域成分および高域成分に分割する垂直分析フィルタリングを行う垂直分析フィルタ手段と、
水平分析フィルタリングに利用可能な係数である第１の演算係数が存在しない非定常状態である場合に第１の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせ、
前記第１の演算係数が存在する定常状態である場合に前記第１の演算係数を用いて第２の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせる水平制御手段と、
前記水平制御手段による制御を、処理対象ラインの全てのコラムについて前記水平分析フィルタリングが行われるまで繰り返し行わせる第１の制御手段と、
垂直分析フィルタリングに利用可能な係数である第２の演算係数が存在しない非定常状態である場合に第３の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせ、
前記第２の演算係数が存在する定常状態である場合に前記第２の演算係数を用いて第４の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせる垂直制御手段と、
前記垂直制御手段による制御を、全てのラインについて前記垂直分析フィルタリングが行われるまで繰り返し行わせる第２の制御手段と
を備える情報処理装置。
【請求項２】
前記水平制御手段は、前記非定常状態である場合、画像左端から２コラム目のサンプルを対称拡張することで画像最左端のサンプルを補充する
請求項１に記載の情報処理装置。
【請求項３】
前記垂直制御手段は、前記非定常状態である場合、画像上端から２ライン目のサンプルを対称拡張することで画像最上端のサンプルを補充する
請求項１に記載の情報処理装置。
【請求項４】
前記水平分析フィルタ手段は、所定のフィルタを用いたリフティング演算により、前記水平分析フィルタリングを行う
請求項１に記載の情報処理装置。
【請求項５】
前記水平分析フィルタ手段は、前記リフティング演算により得られる係数の一部を前記第１の演算用係数としてラッチし、
前記水平制御手段は、前記第１の演算係数がラッチされているか否かによって、前記非定常状態であるか前記定常状態であるかを判断し、制御を行う
請求項４に記載の情報処理装置。
【請求項６】
前記垂直分析フィルタ手段は、所定のフィルタを用いたリフティング演算により、前記垂直分析フィルタリングを行う
請求項１に記載の情報処理装置。
【請求項７】
前記垂直分析フィルタリングにおける前記リフティング演算により得られる係数の一部を保持する保持手段をさらに備え、
前記垂直分析フィルタ手段は、前記リフティング演算により得られる前記係数の一部を前記第２の演算用係数として前記保持手段に保持させ、
前記垂直制御手段は、前記保持手段に前記第２の演算係数が保持されているか否かによって、前記非定常状態であるか前記定常状態であるかを判断し、制御を行う
請求項６に記載の情報処理装置。
【請求項８】
前記第１の情報量は５カラムであり、前記第２の情報量は２カラムである
請求項１に記載の情報処理装置。
【請求項９】
前記第３の情報量は５ラインであり、前記第４の情報量は２ラインである
請求項１に記載の情報処理装置。
【請求項１０】
前記第１の情報量は３カラムであり、前記第２の情報量は２カラムである
請求項１に記載の情報処理装置。
【請求項１１】
前記第３の情報量は３ラインであり、前記第４の情報量は２ラインである
請求項１に記載の情報処理装置。
【請求項１２】
画像信号に対してウェーブレット変換を行う情報処理装置の情報処理方法であって、
前記情報処理装置は、
前記画像信号の周波数成分を、水平方向に、低域成分および高域成分に分割する水平分析フィルタリングを行う水平分析フィルタ手段と、
前記水平分析フィルタ手段による前記水平分析フィルタリングにより分割された前記低域成分および前記高域成分を、それぞれ、垂直方向に、低域成分および高域成分に分割する垂直分析フィルタリングを行う垂直分析フィルタ手段と
を備え、
水平制御手段が、水平分析フィルタリングに利用可能な係数である第１の演算係数が存在しない非定常状態である場合に第１の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせ、前記第１の演算係数が存在する定常状態である場合に前記第１の演算係数を用いて第２の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせ、
第１の制御手段が、前記水平制御手段による制御を、処理対象ラインの全てのコラムについて前記水平分析フィルタリングが行われるまで繰り返し行わせ、
垂直制御手段が、垂直分析フィルタリングに利用可能な係数である第２の演算係数が存在しない非定常状態である場合に第３の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせ、前記第２の演算係数が存在する定常状態である場合に前記第２の演算係数を用いて第４の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせ、
第２の制御手段が、前記垂直制御手段による制御を、全てのラインについて前記垂直分析フィルタリングが行われるまで繰り返し行わせる
情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および方法に関し、特に、ウェーブレット変換処理のメモリ使用量を低減させることができるようにした情報処理装置および方法に関する。
【背景技術】
【０００２】
従来の代表的な画像圧縮方式として、ISO（International Standards Organization）によって標準化されたJPEG（Joint Photographic Experts Group）やJPEG2000がある。
【０００３】
近年では画像をフィルタバンクと呼ばれるハイパス・フィルタとローパス・フィルタとを組み合わせたフィルタによって複数の帯域に分割し、帯域毎に符号化を行う方式の研究が盛んになっている。その中でも、ウェーブレット変換符号化は、DCT（Discrete Cosine Transform）変換で問題になる高圧縮でのブロック歪みが無いことから、DCTに代わる新たな技術として有力視されている。
【０００４】
JPEG2000は、このウェーブレット変換に高能率なエントロピ符号化（ビットプレーン単位のビット・モデリングと算術符号化）を組み合わせた方式を採用しており、JPEGに比べて符号化効率の大きな改善を実現している。
【０００５】
ウェーブレット変換は基本的に画像データを入力して、水平方向のフィルタリングと垂直方向のフィルタリングを行いながら、低域成分を階層的に分割する手段を用いる。この際、画像データの読み出し、フィルタリングの結果生成された周波数係数のメモリへの書き込み、周波数係数の再度の読み出し等、データの読み出しと書き込みが高頻度で必要になる（例えば、特許文献１参照）。
【０００６】
【特許文献１】特開２００８−０２２４０３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、画像信号の場合大量のデータを処理する必要があり、ウェーブレット変換時にメモリの容量が不足してしまう恐れがあった。そこで、ウェーブレット変換をなるべく少ない記憶容量のメモリで実行する事ができるようにする方法が考えられてきた。例えば、JPEG2000のPart-1では128x128のタイルベースでウェーブレット変換を行う方式が採用されている。この範囲内でウェーブレット変換を行えば非常にメモリを節約することができる。
【０００８】
しかしながら、この方法の場合、タイル間の隣接境界が不連続になるので、ウェーブレット変換を利用した画像圧縮で圧縮率が高くなると、境界部が顕著になる視覚的に問題になる恐れがあった。また、これを防ぐために、SSOWT（Spatial Segmented Overlapped Wavelet Transform）という境界部のフィルタリングで、タイル境界をはみ出る部分を隣接ブロックから参照する方式も提案された。
【０００９】
しかしながら、この方式ではウェーブレット変換の分解数が多くなると、必要なメモリが急増する恐れがあった。
【００１０】
本発明はこのような問題を解決するためのものであり、画像信号を、少ないメモリ量でウェーブレット変換することができ、しかも画面全体をウェーブレット変換した結果と同じウェーブレット変換係数を生成することができるようにするものである。
【課題を解決するための手段】
【００１１】
本発明の一側面は、画像信号に対してウェーブレット変換を行う情報処理装置であって、前記画像信号の周波数成分を、水平方向に、低域成分および高域成分に分割する水平分析フィルタリングを行う水平分析フィルタ手段と、前記水平分析フィルタ手段による前記水平分析フィルタリングにより分割された前記低域成分および前記高域成分を、それぞれ、垂直方向に、低域成分および高域成分に分割する垂直分析フィルタリングを行う垂直分析フィルタ手段と、水平分析フィルタリングに利用可能な係数である第１の演算係数が存在しない非定常状態である場合に第１の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせ、前記第１の演算係数が存在する定常状態である場合に前記第１の演算係数を用いて第２の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせる水平制御手段と、前記水平制御手段による制御を、処理対象ラインの全てのコラムについて前記水平分析フィルタリングが行われるまで繰り返し行わせる第１の制御手段と、垂直分析フィルタリングに利用可能な係数である第２の演算係数が存在しない非定常状態である場合に第３の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせ、前記第２の演算係数が存在する定常状態である場合に前記第２の演算係数を用いて第４の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせる垂直制御手段と、前記垂直制御手段による制御を、全てのラインについて前記垂直分析フィルタリングが行われるまで繰り返し行わせる第２の制御手段とを備える。
【００１２】
前記水平制御手段は、前記非定常状態である場合、画像左端から２コラム目のサンプルを対称拡張することで画像最左端のサンプルを補充することができる。
【００１３】
前記垂直制御手段は、前記非定常状態である場合、画像上端から２ライン目のサンプルを対称拡張することで画像最上端のサンプルを補充することができる。
【００１４】
前記水平分析フィルタ手段は、所定のフィルタを用いたリフティング演算により、前記水平分析フィルタリングを行うことができる。
【００１５】
前記水平分析フィルタ手段は、前記リフティング演算により得られる係数の一部を前記第１の演算用係数としてラッチし、前記水平制御手段は、前記第１の演算係数がラッチされているか否かによって、前記非定常状態であるか前記定常状態であるかを判断し、制御を行うことができる。
【００１６】
前記垂直分析フィルタ手段は、所定のフィルタを用いたリフティング演算により、前記垂直分析フィルタリングを行うことができる。
【００１７】
前記垂直分析フィルタリングにおける前記リフティング演算により得られる係数の一部を保持する保持手段をさらに備え、前記垂直分析フィルタ手段は、前記リフティング演算により得られる前記係数の一部を前記第２の演算用係数として前記保持手段に保持させ、前記垂直制御手段は、前記保持手段に前記第２の演算係数が保持されているか否かによって、前記非定常状態であるか前記定常状態であるかを判断し、制御を行うことができる。
【００１８】
前記第１の情報量は５カラムであり、前記第２の情報量は２カラムであるようにすることができる。
【００１９】
前記第３の情報量は５ラインであり、前記第４の情報量は２ラインであるようにすることができる。
【００２０】
前記第１の情報量は３カラムであり、前記第２の情報量は２カラムであるようにすることができる。
【００２１】
前記第３の情報量は３ラインであり、前記第４の情報量は２ラインであるようにすることができる。
【００２２】
本発明の一側面は、また、画像信号に対してウェーブレット変換を行う情報処理装置の情報処理方法であって、前記情報処理装置は、前記画像信号の周波数成分を、水平方向に、低域成分および高域成分に分割する水平分析フィルタリングを行う水平分析フィルタ手段と、前記水平分析フィルタ手段による前記水平分析フィルタリングにより分割された前記低域成分および前記高域成分を、それぞれ、垂直方向に、低域成分および高域成分に分割する垂直分析フィルタリングを行う垂直分析フィルタ手段とを備え、水平制御手段が、水平分析フィルタリングに利用可能な係数である第１の演算係数が存在しない非定常状態である場合に第１の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせ、前記第１の演算係数が存在する定常状態である場合に前記第１の演算係数を用いて第２の情報量の前記周波数成分に対して前記水平分析フィルタリングを行わせ、第１の制御手段が、前記水平制御手段による制御を、処理対象ラインの全てのコラムについて前記水平分析フィルタリングが行われるまで繰り返し行わせ、垂直制御手段が、垂直分析フィルタリングに利用可能な係数である第２の演算係数が存在しない非定常状態である場合に第３の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせ、前記第２の演算係数が存在する定常状態である場合に前記第２の演算係数を用いて第４の情報量の前記低域成分および前記高域成分に対して前記垂直分析フィルタリングを行わせ、第２の制御手段が、前記垂直制御手段による制御を、全てのラインについて前記垂直分析フィルタリングが行われるまで繰り返し行わせる。
【００２３】
本発明の一側面においては、水平分析フィルタリングに利用可能な係数である第１の演算係数が存在しない非定常状態である場合に第１の情報量の周波数成分に対して水平分析フィルタリングが行われ、第１の演算係数が存在する定常状態である場合に第１の演算係数が用いられて第２の情報量の周波数成分に対して水平分析フィルタリングが行われ、処理対象ラインの全てのコラムについて水平分析フィルタリングが繰り返し行われ、垂直分析フィルタリングに利用可能な係数である第２の演算係数が存在しない非定常状態である場合に第３の情報量の低域成分および高域成分に対して垂直分析フィルタリングが行われ、第２の演算係数が存在する定常状態である場合に第２の演算係数が用いられて第４の情報量の低域成分および高域成分に対して垂直分析フィルタリングが行われ、全てのラインについて垂直分析フィルタリングが繰り返し行われる。
【発明の効果】
【００２４】
本発明によれば、ウェーブレット変換を行うことができる。特に、ウェーブレット変換処理に必要な記憶容量を低減させることができる。
【発明を実施するための最良の形態】
【００２５】
以下、発明を実施するための最良の形態（以下実施の形態とする）について説明する。なお、説明は以下の順序で行う。
１．第１の実施の形態（ウェーブレット変換処理：フィルタ処理をより詳細に制御する例）
２．第２の実施の形態（フィルタ：５×３フィルタを適用する例）
３．第３の実施の形態（応用例：符号化装置に適用する例）
【００２６】
＜１．第１の実施の形態＞
［ウェーブレット変換装置の構成例］
図１は、本発明を適用したウェーブレット変換装置の構成例を示すブロック図である。図１においてウェーブレット変換装置１００は、入力される画像信号に対して、入力データを低域成分と高域成分に分割する分析フィルタ処理を画面水平方向および画面垂直方向の両方に対して行うウェーブレット変換処理を行う。
【００２７】
つまり、ウェーブレット変換処理により入力データは、４つの成分（サブバンド）に分割される。１つは、水平方向および垂直方向に低域な成分（ＬＬ成分）である。他の１つは、水平方向に高域で垂直方向に低域な成分（ＨＬ成分）である。さらに他の１つは、水平方向に低域で垂直方向に高域な成分（ＬＨ成分）である。最後の１つは、水平方向および垂直方向に高域な成分（ＨＨ成分）である。
【００２８】
ウェーブレット変換装置１００は、このようなウェーブレット変換処理を、所定回数、フィルタ処理により得られる水平方向および垂直方向に低域な成分（ＬＬ成分）に対して再帰的に繰り返す。
【００２９】
ウェーブレット変換装置１００は、図１に示されるように、スケジューラ１１１、水平分析フィルタ部１１２、ラインバッファ１１３、垂直分析フィルタ部１１４、および係数バッファ１１５を有する。
【００３０】
スケジューラ１１１は、主に水平分析フィルタ部１１２および垂直分析フィルタ部１１４の動作のタイミング制御を行う。この制御については後述する。
【００３１】
水平分析フィルタ部１１２は、スケジューラ１１１に制御され（Ｄ１６）、外部より入力される画像信号（Ｄ１０）、または、垂直分析フィルタ部１１４より供給されるＬＬ成分（Ｄ１８）に対して、水平方向に分析フィルタリングを行う。
【００３２】
分析フィルタリングは、詳細については後述するが、リフティング演算を用いて行われる。したがって、水平方向の分析フィルタリング（水平分析フィルタリング）は、１ラインの係数のうち所定のコラム数分のサンプルを用いて行われる。
【００３３】
１ピクチャ分の画像信号（Ｄ１０）は、画像の上から下に向かう順に１ラインずつ入力される。また各ラインの画像信号（Ｄ１０）は、画像左から右に向かう順に１サンプル（１コラム）ずつ入力される。この順はＬＬ成分（Ｄ１８）の場合も同様である。つまり、データの入力順と処理順が一致する。
【００３４】
従って、水平分析フィルタ部１１２は、分析フィルタリングを実行可能なサンプル数のデータを入手する毎に（入手次第）、そのデータに対して水平分析フィルタリングを実行する。
【００３５】
このように水平分析フィルタリングが行われると、例えば、図２の左に示されるベースバンドの画像データ２０１は、図２の右に示されるように、水平方向に低域な成分（Ｌ）と高域な成分（Ｈ）に分割される（水平分析フィルタ処理結果２０２）。水平分析フィルタリングは、各ラインについて行われる。
【００３６】
水平分析フィルタ部１１２は、分析フィルタリングの結果の係数（Ｄ１２）を、ラインバッファ１１３を介して垂直分析フィルタ部１１４に供給する。ラインバッファ１１３は、水平方向の分析フィルタリングの結果の係数（Ｄ１２）を一時的に保持し、垂直分析フィルタ部１１４に供給する（Ｄ１３）。ラインバッファ１１３は、少なくとも、垂直方向の分析フィルタリングに必要なライン数の係数を保持する事ができる記憶容量を有する。
【００３７】
垂直分析フィルタ部１１４は、スケジューラ１１１に制御され（Ｄ１７）、水平方向の分析フィルタ結果に対して、垂直方向に分析フィルタリング（垂直分析フィルタリング）を行う。垂直方向の場合も分析フィルタリングは、リフティング演算を用いて行われる。
【００３８】
したがって、垂直分析フィルタ部１１４は、垂直分析フィルタリングに必要な垂直ライン分のデータ（Ｄ１３）をラインバッファ１１３から読み出しながら、読み出した係数に対して垂直分析フィルタリングを行う。垂直分析フィルタ部１１４は、ラインバッファ１１３に、垂直分析フィルタリングに必要なライン数のデータが保持され次第、そのデータを読み出し、垂直分析フィルタリングを行う。例えば、垂直分析フィルタ部１１４は、図２の右に示される水平分析フィルタ処理結果２０２がラインバッファ１１３に保持される度に、そのデータを読み出し、垂直分析フィルタリングを行う。
【００３９】
その結果、水平分析フィルタ処理結果は、図３の左に示されるように、４つの成分のウェーブレット変換係数（以下、係数と称する）に分割される（分割レベル１の係数２０３）。つまり、水平方向に低域な成分は、水平方向および垂直方向の両方に低域な成分（ＬＬ成分）と水平方向に低域で垂直方向に高域な成分（ＬＨ成分）に分割される。また、水平方向に高域な成分は、水平方向に高域で垂直方向に低域な成分（ＨＬ成分）と水平方向および垂直方向の両方に高域な成分（ＨＨ成分）に分割される。
【００４０】
垂直分析フィルタ部１１４は、所定の分割レベルの係数が得られるまで、得られた分析フィルタリングの結果のうち、ＨＬ成分、ＬＨ成分、ＨＨ成分を外部に出力する（Ｄ１９）。また、それととともに、垂直分析フィルタ部１１４は、ＬＬ成分を水平分析フィルタ部１１２に戻し（Ｄ１８）、再度分析フィルタリングを行わせる。
【００４１】
つまり、水平分析フィルタ部１１２および垂直分析フィルタ部１１４は、例えば、図３左の分割レベル１の係数２０３の、水平方向および垂直方向の低域成分（ＬＬ成分）に対して、上述したのと同様に分析フィルタ処理を行う。分割レベル２の係数（ＬＬＬＬ成分、ＬＬＨＬ成分、ＬＬＬＨ成分、ＬＬＨＨ成分）を生成する。
【００４２】
図３の右は、分割レベル２まで分割された係数２０４を示す。係数２０４においては、係数２０３のＬＬ成分が分割され、ＬＬＬＬ成分、ＬＬＨＬ成分、ＬＬＬＨ成分、ＬＬＨＨ成分が形成されている。これらの成分は、分割レベル２の係数である。水平分析フィルタ部１１２および垂直分析フィルタ部１１４は、このように、水平方向および垂直方向の両方に低域なＬＬ成分に対して分析フィルタ処理を再帰的に繰り返し、原画像２０１を所望の分割レベルまで分割する。
【００４３】
図４は、分割レベル３まで分割した場合の係数の例を示す図である。図４において、分割レベル３まで分割された係数２０５は、分割レベル１のサブバンドとして、１ＨＬ成分、１ＬＨ成分、および１ＨＨ成分を有する。また、係数２０５は、分割レベル２のサブバンドとして、２ＨＬ成分、２ＬＨ成分、および２ＨＨ成分を有する。さらに、係数２０５は、分割レベル３のサブバンドとして、３ＬＬ成分、３ＨＬ成分、３ＬＨ成分、および３ＨＨ成分を有する。
【００４４】
ウェーブレット変換処理では、フィルタリング処理を繰り返す毎に（分割レベルの階層が１つ進む毎に）、生成されるライン数は２のべき乗分の１の大きさで小さくなっていく。最終分割レベルの係数を１ライン生成するために必要なベースバンドのライン数は、そのフィルタリング処理を何回繰り返すか（最終分割レベルの階層数）によって決められる。通常、この階層数は予め定められる。
【００４５】
この、最終分割レベルの係数を１ライン生成するために必要なベースバンドの画像データ（複数ライン分の画像データ）、または、各階層の係数をまとめてラインブロック（またはプレシンクト）と称する。
【００４６】
図４において斜線で示される部分が１ラインブロックを構成する係数である。図４に示されるように、ラインブロックは、最終分割レベルである分割レベル３の各成分の１ライン分の係数、分割レベル２の各成分の２ライン分の係数、並びに、分割レベル１の各成分の４ライン分の係数により構成される。
【００４７】
使用するメモリ量を低減するためには、より少ないデータ量毎にフィルタ処理を行うのが望ましい。そこで、ウェーブレット変換装置１００は、このラインブロック単位にウェーブレット変換処理を行う。
【００４８】
垂直分析フィルタ部１１４は、所望の分割レベルまで分割を行うと、その所望の分割レベルの係数の各成分（ＬＬ成分、ＨＬ成分、ＬＨ成分、およびＨＨ成分）を外部に出力する。画像圧縮の場合、外部に出力された係数は、後段において、例えば、量子化されたり、符号化されたりする。
【００４９】
なお、垂直分析フィルタ部１１４は、係数バッファ１１５を用いて垂直分析フィルタリングを行う。係数バッファ１１５は、その垂直分析フィルタリング中に生成される演算途中の係数を一時的に保持し（Ｄ１４）、必要に応じてその係数を垂直分析フィルタ部１１４に提供する（Ｄ１５）。
【００５０】
詳細については後述するが、リフティング演算においては、演算結果の係数（低域成分または高域成分）とともに、演算途中の係数が得られる。この演算途中の係数や演算結果の係数の一部は、次回のリフティング演算に利用される。このような次回のリフティング演算に使用される係数（演算用係数）は、係数バッファ１１５に一時的に保持される。
【００５１】
以上のような構成により、ウェーブレット変換装置１００は、水平分析フィルタリングを行いながらフィルタリングの結果をラインバッファ１１３に記憶させることができる。さらに、ウェーブレット変換装置１００は、上記のフィルタリングの結果をラインバッファ１１３から読み出しながら垂直分析フィルタリングを行うことができる。
【００５２】
したがって、ウェーブレット変換装置１００は、水平方向と垂直方向の分析フィルタリングを同時並行的に行うことができる。従って、ウェーブレット変換装置１００は、動画や解像度が大きい画像に対しても、高速にウェーブレット変換を実行することができる。
【００５３】
また、また垂直分析フィルタリングに対して係数バッファ１１５を配置し、垂直分析フィルタリングを実行するのに最低限必要な係数がその係数バッファ１１５に記憶され、次の垂直分析フィルタリングの際にその係数が読み出されて使用されるようになされている。従ってこの係数バッファ１１５は、容量が小さいが、情報の読み出しや書き込みの速度（アクセス速度）が高速な内部メモリによって実現することができ、大容量だがアクセス速度が遅い外部メモリを用いる必要がない。
【００５４】
［リフティング演算］
分析フィルタリングで、最も一般的な演算方法は、畳み込み演算と言われる手段である。これは、デジタルフィルタの最も基本的な実現手段で、フィルタのタップ係数に、実際の入力データを畳み込み乗算するものである。しかしこの欠点は、タップ長が長いと、その分、計算負荷が増えることである。
【００５５】
これを解決する手段として、W.Swelden氏が１９９６年にApplied and Computational Harmonic Analysis 3, 186-200に論文掲載した”The Lifting Scheme : A Custom Design Construction of Biorthogonal Wavelets“で紹介された、ウェーブレット変換のリフティング手段がある。
【００５６】
水平分析フィルタ部１１２および垂直分析フィルタ部１１４は、フィルタリング演算を効率よく行うために、実際にはこのリフティング演算を用いる。図５はJPEG2000 Part-1でも採用されているドビッシー型の９×７実数精度フィルタをリフティング表現した図である。図中、最上部の一列が入力信号列である。データ処理は画面上から下方向に流れ、以下の４つのステップを経由して、Step３において高域係数（高域成分の係数）、Step４において低域係数（低域成分の係数）が出力される。
【００５７】
step１：ｄi1＝ｄi0＋α（ｓi0＋ｓi+10）  ・・・（１）
step２：ｓi1＝ｓi0＋β（ｄi-11＋ｄi1）  ・・・（２）
step３：ｄi2＝ｄi1＋γ（ｓi1＋ｓi+11）  ・・・（３）
step４：ｓi2＝ｓi1＋δ（ｄi-12＋ｄi2）  ・・・（４）
（α＝-1.586134342，β＝-0.0529801185，γ＝0.8829110755，δ＝0.4435068520）
【００５８】
図６は、垂直方向の係数群に対して、垂直分析フィルタリングを実行する様子の例を図示したものである。図６は垂直方向の係数に対して、式（１）乃至式（４）で示される４つのStepを経て、高域係数と低域係数を生成する様子を示している。図６に示されるように、１組の高域係数と低域係数を求めるためには、ライン１からライン６までの６ラインが必要になる。
【００５９】
またリフティング演算の過程で生成される係数の一部は、次のリフティング演算で必要になる係数（演算用係数）なので、これをラッチ（記憶）しておく必要がある。図６では楕円で囲んだ点線の領域が１つ前の垂直リフティング演算で記憶保持される３個の演算用係数で、その下の実線の楕円で囲んだ領域は現在の垂直リフティング演算で記憶保持される３個の演算用係数である。図６に示されるように、演算用係数は、２個の演算途中の係数と、１個の高域係数よりなる。
【００６０】
図６に示されるように、リフティング演算の特徴から１ラインが追加入力されても垂直分析フィルタリングは実行不可能である。図７の左に示される時刻１は、前回垂直分析フィルタリングが行われた時の状態を示し、図７の右に示される時刻２は、その次の垂直分析フィルタリングが行われる時の状態を示している。
【００６１】
このように、垂直分析フィルタリングを行うためには２ライン追加する必要がある。その結果、１組の低域成分と高域成分が生成される。以後、同様にして、順次２ラインが追加入力される度に、１組の低域成分と高域成分が生成される。
【００６２】
以上においては、垂直方向の分析フィルタリングについて説明したが、水平分析フィルタリングの場合も同様であり、ラインをコラムに置き換えれば、上述した説明を水平分析フィルタリングの場合に適用することができる。
【００６３】
なお、水平分析フィルタリングは、１ライン単位で独立して行われる。つまり、各リフティング演算においてラッチする必要のある演算用係数は高々３個であるので、水平分析フィルタ部１１２内に設けたフリップフロップ等、小容量の記憶領域により容易に保持することができる。なお、実際には、この演算用係数の他に最後に入力されたコラム（垂直方向の場合、ライン）の係数も必要になる。この係数はラッチしてもよいし、再度入力するようにしてもよい。
【００６４】
これに対して、垂直分析フィルタリングは、上述した処理を各コラムに対して並列的に行う必要がある。つまり、ラッチすべき演算用係数もそのコラム数分増大する。したがって、垂直分析フィルタ部１１４は、演算用係数を係数バッファ１１５に保持させる。ただし、この場合もラッチする演算用係数の容量も、せいぜい数キロバイト程度であるので、例えばSRAM（Static Random Access Memory）のような高速に動作可能なメモリにより実現することができる。
【００６５】
［動作説明］
次に、図１に示されるウェーブレット変換装置１００の動作について説明する。図８は、水平分析フィルタリングの様子を説明する図である。各ラインの画像データ（Ｄ１０）は、図８の上段に示される入力データ２５１の各四角内の数字（１、２、・・・、１０、・・・）のように、画像左側から右側に向かう順に１サンプルずつ供給される。
【００６６】
水平分析フィルタ部１１２は、スケジューラ１１１に制御されて（Ｄ１６）、画像データ（Ｄ１０）が必要なサンプル数入力される毎に水平分析フィルタリングを行う。上述したように、水平分析フィルタリングには６コラム分の入力データが必要である。水平分析フィルタ部１１２は、画像左端について、矢印２４１に示されるように、左から２コラム目（コラム２）の入力データを用いて対称拡張し、１サンプル（コラム０）補足する（［処理１］）。
【００６７】
つまり、５コラムの入力データが入力されると、水平分析フィルタ部１１２は、対象拡張した分も含めた６サンプルの入力データに対して水平分析フィルタリングを行う（［処理２］）。これにより、図８の下段に示される係数２５２のように、水平方向に低域な係数（Ｌ）と高域な係数（Ｈ）が生成される。水平分析フィルタ部１１２は、生成した水平方向に低域な係数（Ｌ）と高域な係数（Ｈ）をラインバッファ１１３に供給して（Ｄ１２）蓄積させる。
【００６８】
この水平分析フィルタリングにより演算用係数が生成されるので、次の水平分析フィルタリングは、この演算用係数を用いて行うことができる。つまり、２コラム分のデータを追加するだけでよい。水平分析フィルタ部１１２は、２コラムの入力データが追加入力されると、ラッチした演算用係数（前回得られた演算用係数）も含めた６サンプルの入力データに対して水平分析フィルタリングを行う（［処理３］）。
【００６９】
なお、実際には、前回入力された最後のコラムの係数（入力係数）も必要になるので、水平分析フィルタ部１１２は、その入力係数を演算用係数とともにラッチするようにしてもよい。
【００７０】
以上のようにして、図８の下段に示される係数２５２のように、水平方向に低域な係数（Ｌ）と高域な係数（Ｈ）が生成される。水平分析フィルタ部１１２は、この場合も、生成した水平方向に低域な係数（Ｌ）と高域な係数（Ｈ）をラインバッファ１１３に供給して（Ｄ１２）蓄積させる。
【００７１】
また、このとき新たな演算用係数が得られる（ラッチする演算用係数が更新される）。同様にして、次の２コラムの入力データが追加入力されると、水平分析フィルタ部１１２は、ラッチした演算用係数（前回得られた演算用係数）も含めた６サンプルの入力データに対して水平分析フィルタリングを行う（［処理４］）。
【００７２】
以降、ラインの右端まで同様の処理が繰り返される。このようにして、１ライン分の水平方向に低域な係数（Ｌ）と高域な係数（Ｈ）が生成され、ラインバッファ１１３に蓄積される。
【００７３】
上述したように、垂直分析フィルタリングを行うには６ライン分の係数が必要であるので、水平分析フィルタ部１１２は、上述したように水平分析フィルタリングを５ライン分行う。つまり、例えば、図９の上段に示される５ライン分の入力データ２５３が、図９の下段に示される５ライン分の係数２５４に変換される。
【００７４】
水平分析フィルタ部１１２は、例えば、１ライン分の係数をラインバッファ１１３に蓄積させる毎に垂直分析フィルタ部１１４にその旨を通知する（Ｄ１１）。スケジューラ１１１に制御される（Ｄ１７）垂直分析フィルタ部１１４は、ラインバッファ１１３に５ライン分の係数２５４が蓄積されると、それを読み出す（Ｄ１３）。
【００７５】
垂直分析フィルタ部１１４は、さらに、画像の上端について、矢印２４２に示されるように上から２ライン目の係数を用いて対称拡張し、１ライン分の係数２５５を補足する。つまり、垂直分析フィルタ部１１４は、５ラインの係数を取得すると、対象拡張した分も含めた６ラインの係数に対して垂直分析フィルタリングを行う。
【００７６】
この垂直分析フィルタリングは、図１０の上段の枠２４３に示されるように、コラム毎に、全コラムについて行われる。これにより、各コラムの係数が垂直方向に低域な成分と高域な成分に分割される。
【００７７】
つまり、図１０の下段に示されるように、水平方向に低域な成分は、水平方向および垂直方向に低域な成分（ＬＬ成分）２６１と水平方向に低域で垂直方向に高域な成分（ＬＨ成分）２６３に分割される。
【００７８】
また、図１０の下段に示されるように、水平方向に高域な成分は、水平方向に高域で垂直方向に低域な成分（ＨＬ成分）２６２と水平方向および垂直方向に高域な成分（ＨＨ成分）２６４に分割される。
【００７９】
つまり、図１１の上段に示されるように、画像上端においては、５ライン分の入力データから、水平方向および垂直方向に低域な成分（ＬＬ成分）２６１−１が１ライン生成される。同様に、水平方向に高域で垂直方向に低域な成分（ＨＬ成分）２６２−１も１ライン生成される。さらに同様に、水平方向に低域で垂直方向に高域な成分（ＬＨ成分）２６３−１も１ライン生成される。さらに同様に、水平方向および垂直方向に高域な成分（ＨＨ成分）２６４−１も１ライン生成される。
【００８０】
このとき、垂直分析フィルタリングにおいても演算用係数が生成されるので、水平分析フィルタリングの場合と同様に、その次の垂直分析フィルタリングは、２ライン追加入力するだけで実行することができる。
【００８１】
垂直分析フィルタ部１１４は、生成した演算用係数を係数バッファ１１５に供給し（Ｄ１４）、保持させる。そして、係数バッファ１１５に演算用係数が保持されている場合、垂直分析フィルタ部１１４は、係数バッファ１１５よりその演算用係数を読み出し（Ｄ１５）、入力された係数と、その演算用係数を用いて垂直分析フィルタリングを行う。なお、実際には、前回入力された最後のラインの係数（入力係数）も必要になるので、垂直分析フィルタ部１１４は、その入力係数を演算用係数とともに係数バッファ１１５に保持させるようにしてもよい。
【００８２】
例えば、図１１の上段に示されるように、２ライン分の入力データが追加入力されると、水平方向および垂直方向に低域な成分（ＬＬ成分）２６１−２が１ライン生成される。同様に、水平方向に高域で垂直方向に低域な成分（ＨＬ成分）２６２−２も１ライン生成される。さらに同様に、水平方向に低域で垂直方向に高域な成分（ＬＨ成分）２６３−２も１ライン生成される。さらに同様に、水平方向および垂直方向に高域な成分（ＨＨ成分）２６４−２も１ライン生成される。
【００８３】
それ以降、演算用係数は毎回得られるので、２ライン毎に分析フィルタリング可能であり、その度に１ライン分の各成分が生成される。
【００８４】
垂直分析フィルタ部１１４は、演算結果の係数が最終分割レベルで無い場合、演算結果のうち、ＨＬ成分、ＬＨ成分、およびＨＨ成分の各成分の係数を外部に出力する（Ｄ１９）。また、垂直分析フィルタ部１１４は、ＬＬ成分の係数を水平分析フィルタ部１１２に供給し（Ｄ１８）、再度分析フィルタリングを行わせる。
【００８５】
なお、演算結果の係数が最終分割レベルの場合、垂直分析フィルタ部１１４は、全ての演算結果を（ＬＬ成分の係数も）外部に出力する（Ｄ１９）。
【００８６】
以上のように、水平分析フィルタリングと垂直分析フィルタリングにおいては、今回のフィルタリング演算に利用可能な係数である演算用係数が存在するか否かによって、必要な入力データの量が異なる。つまり、分析フィルタリングにより生成される演算用係数を利用して次の分析フィルタリングを行う場合、より少ない入力データ毎に分析フィルタリングを実行させることができる。
【００８７】
スケジューラ１１１は、水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、このような演算用係数を利用して、より少ない入力データに対して分析フィルタリングを実行させるようにする。
【００８８】
より具体的には、スケジューラ１１１は、水平分析フィルタリングにおける画像左端の場合や、垂直分析フィルタリングにおける画像上端の場合のように、利用可能な演算用係数が存在しない状態を「非定常状態」とする。また、スケジューラ１１１は、水平分析フィルタリングにおける画像左端以外の場合や、垂直分析フィルタリングにおける画像上端以外の場合のように、利用可能な演算用係数が存在する状態を「定常状態」とする。
【００８９】
そして、スケジューラ１１１は、水平分析フィルタ部１１２を制御し、各状態において必要なコラム分のデータが入力される度に水平分析フィルタリングを実行させる。例えば、９×７フィルタを用いて分析フィルタリングを行う場合、スケジューラ１１１は、水平分析フィルタ部１１２を制御し、非定常状態の場合、５コラム分のデータが入力されると水平分析フィルタリングを実行させる。また、定常状態の場合、スケジューラ１１１は、２コラム分のデータが入力される度に水平分析フィルタリングを実行させる。
【００９０】
また、スケジューラ１１１は、垂直分析フィルタ部１１４を制御し、各状態において必要なライン分のデータが入力される度に垂直分析フィルタリングを実行させる。例えば、９×７フィルタを用いて分析フィルタリングを行う場合、スケジューラ１１１は、水平分析フィルタ部１１２を制御し、非定常状態の場合、５ライン分のデータが入力されると垂直分析フィルタリングを実行させる。また、定常状態の場合、スケジューラ１１１は、２ライン分のデータが入力される度に垂直分析フィルタリングを実行させる。
【００９１】
つまり、スケジューラ１１１は、水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、定常状態・非定常状態のそれぞれにおいて、必要な（適切な）情報量の画像信号の周波数成分に対して分析フィルタリングを実行させる。
【００９２】
このように制御することにより、スケジューラ１１１は、同時期に保持される必要のあるデータ量を低減させることができ、ウェーブレット変換処理におけるメモリの使用量、つまり、ウェーブレット変換処理に必要な記憶容量を低減させることができる。これにより、ウェーブレット変換装置１００に必要なメモリ容量を低減させることができ、コストを低減させることができる。
【００９３】
なお、以上のような分析フィルタリングを複数回繰り返す（分割レベル２以上に分割させる）場合、スケジューラ１１１は、水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、図１２に示されるように分析フィルタリングを実行させる。
【００９４】
つまり、ウェーブレット変換装置１００は、スケジューラ１１１の制御により、５ライン分の原画像（Source画像）が入力されると、１ライン分の分割レベル１の係数を生成する。
【００９５】
非定常状態および定常状態についてこの処理が繰り返し実行され、１３ライン分の原画像から５ライン分の分割レベル１の係数が生成される。ウェーブレット変換装置１００は、この５ライン分の分割レベル１の係数から１ライン分の分割レベル２の係数を生成する。
【００９６】
同様に、各状態についてこのような処理が繰り返し実行され、２９ライン分の原画像から１３ライン分の分割レベル１の係数が生成される。さらに、その１３ライン分の分割レベル１の係数から５ライン分の分割レベル２の係数が生成される。ウェーブレット変換装置１００は、この５ライン分の分割レベル２の係数から１ライン分の分割レベル３の係数を生成する。
【００９７】
さらに同様に、各状態についてこのような処理が繰り返し実行され、６１ライン分の原画像から２９ライン分の分割レベル１の係数が生成される。さらに、その２９ライン分の分割レベル１の係数から１３ライン分の分割レベル２の係数が生成される。さらに、その１３ライン分の分割レベル２の係数から５ライン分の分割レベル３の係数が生成される。ウェーブレット変換装置１００は、この５ライン分の分割レベル３の係数から１ライン分の分割レベル４の係数を生成する。
【００９８】
スケジューラ１１１は、このような制御を繰り返し、ピクチャの全ラインについて分析フィルタリングを実行させる。このように制御することにより、スケジューラ１１１は、ウェーブレット変換処理におけるメモリの使用量を低減させることができる。
【００９９】
［処理の流れの説明］
次に以上のようなウェーブレット変換処理の流れの例を、図１３のフローチャートを参照して説明する。図１のウェーブレット変換装置１００は、このウェーブレット変換処理を、分割レベル毎に実行する。なお、ウェーブレット変換処理開始時は、演算用係数が存在しないので、スケジューラ１１１は、水平分析フィルタリングおよび垂直分析フィルタリングの両方について、非定常状態とする。
【０１００】
ウェーブレット変換処理が開始されると、スケジューラ１１１に制御される水平分析フィルタ部１１２は、１ライン分の係数に対して水平分析フィルタリングを行う水平分析フィルタ処理を実行する。
【０１０１】
垂直分析フィルタリングが非定常状態であるので、スケジューラ１１１は、ステップＳ１０２において、水平分析フィルタ部１１２が水平分析フィルタ処理を５ライン分行ったか否かを判定する。スケジューラ１１１は、水平分析フィルタ部１１２が５ライン処理したと判定するまで、処理をステップＳ１０１に戻し、水平分析フィルタ処理を繰り返し実行させる。
【０１０２】
ステップＳ１０２において５ライン処理されたと判定された場合、処理はステップＳ１０３に進む。垂直分析フィルタリングが非定常状態であるので、スケジューラ１１１に制御される垂直分析フィルタ部１１４は、ステップＳ１０３において、対象拡張で１ライン補足する。
【０１０３】
ステップＳ１０４において、垂直分析フィルタ部１１４は、水平分析フィルタ処理により得られた５ライン分の係数に対して垂直分析フィルタリングを行う。ステップＳ１０５において、垂直分析フィルタ部１１４は、出力成分を装置外部に出力する。例えば、最下層の分割レベルでない場合、垂直分析フィルタ部１１４は、分析フィルタリングにより得られたＨＬ成分、ＬＨ成分、ＨＨ成分を装置外部に出力する。また、例えば、最下層の分割レベルの場合、垂直分析フィルタ部１１４は、分析フィルタリングにより得られた全成分を装置外部に出力する。
【０１０４】
ステップＳ１０６において、垂直分析フィルタ部１１４は、ステップＳ１０４の処理により得られた演算用係数を係数バッファ１１５に記憶させる。このとき、入力された最後のラインの係数（入力係数）も演算用係数とともに係数バッファ１１５に記憶させる。もちろん、この入力係数は記憶させずに、再度入力させるようにしてもよい。
【０１０５】
演算用係数が生成されたので、スケジューラ１１１は、垂直分析フィルタリングの状態を定常状態とする。ステップＳ１０７において、スケジューラ１１１は、垂直分析フィルタ部１１４が画像（ピクチャ）の最下位ラインまで処理したか否かを判定する。
【０１０６】
スケジューラ１１１は、例えば入力される画像信号に含まれる同期情報や処理実行回数等に基づいて処理されたライン数をカウントしており、どのラインまで処理が進んだかを常に把握している。スケジューラ１１１はそのカウント値に基づいて、最下位ラインまで処理されたか否かの判定を行う。まだ、画像の途中のラインまでしか処理していないと判定された場合、処理はステップＳ１０８に進む。
【０１０７】
ステップＳ１０８において、スケジューラ１１１に制御される水平分析フィルタ部１１２は、ステップＳ１０１の場合と同様の水平分析フィルタ処理を実行する。垂直分析フィルタリングが定常状態であるので、スケジューラ１１１は、ステップＳ１０９において、水平分析フィルタ部１１２が水平分析フィルタ処理を２ライン分行ったか否かを判定する。スケジューラ１１１は、水平分析フィルタ部１１２が２ライン処理したと判定するまで、処理をステップＳ１０８に戻し、水平分析フィルタ処理を繰り返し実行させる。
【０１０８】
ステップＳ１０９において２ライン処理されたと判定された場合、処理はステップＳ１１０に進む。垂直分析フィルタリングが定常状態であるので、スケジューラ１１１に制御される垂直分析フィルタ部１１４は、ステップＳ１１０において、係数バッファ１１５より演算係数および入力係数を読み出す。
【０１０９】
ステップＳ１１１において、垂直分析フィルタ部１１４は、水平分析フィルタ処理により得られた２ライン分の係数、演算係数、および入力係数に対して垂直分析フィルタリングを行う。ステップＳ１１２において、垂直分析フィルタ部１１４は、出力成分を装置外部に出力する。例えば、最下層の分割レベルでない場合、垂直分析フィルタ部１１４は、分析フィルタリングにより得られたＨＬ成分、ＬＨ成分、ＨＨ成分を装置外部に出力する。また、例えば、最下層の分割レベルの場合、垂直分析フィルタ部１１４は、分析フィルタリングにより得られた全成分を装置外部に出力する。
【０１１０】
ステップＳ１１３において、垂直分析フィルタ部１１４は、ステップＳ１１１の処理により得られた演算用係数を係数バッファ１１５に記憶させる。このとき、入力された最後のラインの係数（入力係数）も演算用係数とともに係数バッファ１１５に記憶させる。もちろん、この入力係数は記憶させずに、再度入力させるようにしてもよい。
【０１１１】
ステップＳ１１５の処理が終了すると、処理は、ステップＳ１０７に戻り、それ以降の処理が繰り返される。以上のように、画像の最下位ラインに至るまで、ステップＳ１０７乃至ステップＳ１１３の処理が繰り返し実行される。ステップＳ１０７において、最下位ラインまで処理したと判定された場合、ウェーブレット変換処理が終了される。
【０１１２】
次に、図１４のフローチャートを参照して、図１３のステップＳ１０１またはステップＳ１０８において実行される水平分析フィルタ処理の流れの例を説明する。なお、水平分析フィルタ処理開始時は、演算用係数が存在しないので、スケジューラ１１１は、水平分析フィルタリングの状態を非定常状態とする。
【０１１３】
水平分析フィルタ処理が開始されると、水平分析フィルタリングが非定常状態であるので、スケジューラ１１１に制御される水平分析フィルタ部１１２は、ステップＳ１３１において、５サンプルの係数入力を受け付ける。
【０１１４】
ステップＳ１３２において、水平分析フィルタ部１１２は、対称拡張で係数を１コラム補足する。ステップＳ１３３において、水平分析フィルタ部１１２は、ステップＳ１３１およびステップＳ１３２の処理により得られた６サンプルについて水平分析フィルタリングを行う。ステップＳ１３４において、水平分析フィルタ部１１２は、演算結果の係数（演算結果係数）をラインバッファ１１３に記憶させる。
【０１１５】
このとき、水平分析フィルタ部１１２は、ステップＳ１３３の処理により得られた演算用係数を保持する。また、水平分析フィルタ部１１２は、入力された最後のコラムの係数（入力係数）も演算用係数とともに保持する。もちろん、この入力係数は保持せずに、再度入力させるようにしてもよい。
【０１１６】
演算用係数が生成されたので、スケジューラ１１１は、水平分析フィルタリングの状態を定常状態とする。ステップＳ１３５において、スケジューラ１１１は、水平分析フィルタ部１１２が画像（ピクチャ）の右端まで処理したか否かを判定する。
【０１１７】
スケジューラ１１１は、例えば入力される画像信号に含まれる同期情報や処理実行回数等に基づいて処理されたコラム数をカウントしており、どのコラムまで処理が進んだかを常に把握している。スケジューラ１１１はそのカウント値に基づいて、画像右端まで処理されたか否かの判定を行う。まだ、画像の途中のコラムまでしか処理していないと判定された場合、処理はステップＳ１３６に進む。
【０１１８】
ステップＳ１３６において、スケジューラ１１１に制御される水平分析フィルタ部１１２は、水平分析フィルタリングが定常状態であるので、２サンプルの係数入力を受け付ける。ステップＳ１３７において、水平分析フィルタ部１１２は、ステップＳ１３６の処理により受け付けられた係数、並びに、ラッチしている演算用係数および入力係数の６サンプルについて水平分析フィルタリングを行う。
【０１１９】
ステップＳ１３８において、水平分析フィルタ部１１２は、演算結果係数をラインバッファ１１３に記憶させる。このとき、水平分析フィルタ部１１２は、ステップＳ１３７の処理により得られた演算用係数を保持する。また、水平分析フィルタ部１１２は、入力された最後のコラムの係数（入力係数）も演算用係数とともに保持する。もちろん、この入力係数は保持せずに、再度入力させるようにしてもよい。
【０１２０】
ステップＳ１３８の処理が終了すると、処理は、ステップＳ１３５に戻り、それ以降の処理が繰り返される。以上のように、画像の右端に至るまで、ステップＳ１３５乃至ステップＳ１３８の処理が繰り返し実行される。ステップＳ１３５において、画像右端まで処理したと判定された場合、水平分析フィルタ処理が終了される。
【０１２１】
以上のように各処理を実行することにより、ウェーブレット変換装置１００は、同時期に保持される必要のあるデータ量を低減させることができる。すなわち、ウェーブレット変換装置１００は、ウェーブレット変換処理におけるメモリの使用量、つまり、ウェーブレット変換処理に必要な記憶容量を低減させることができる。これにより、ウェーブレット変換装置１００に必要なメモリ容量を低減させることができ、コストを低減させることができる。
【０１２２】
また、メモリ使用量が少ないので、SRAM等の高速にアクセス可能なメモリを用いて各種バッファを実現することができる。例えば、LSIなどに実装する場合、他の回路を含むチップの中にウェーブレット変換装置１００を同梱することができる。その場合、メモリ使用量が少ないので、ラインバッファ１１３や係数バッファ１１５等の記憶領域として、LSI（Large Scale Integration）の内部メモリのみを使用するウェーブレット変換装置１００を実現することができる。
【０１２３】
また、外部メモリが不要なので、チップサイズを小さくすることもできる。さらに、チップサイズが小さければその分コストが減らせるという効果もある。
【０１２４】
さらに、使用するメモリを内蔵化にする（外部メモリを使用せずにウェーブレット変換装置１００を実現する）ことでウェーブレット変換部とメモリ部との間のデータ伝送を高速化することができる。従って、ウェーブレット変換処理をより高速に行うことができ、例えばHDTV（High Definition TeleVision）動画をリアルタイムにウェーブレット変換することができる。
【０１２５】
なお、スケジューラ１１１が、分析フィルタリングの度に定常状態であるか非定常状態であるかを判定し、その判定結果に基づいて処理を行うようにしてもよい。この場合も各状態において実行する処理は、上述した通りである。また、この定常状態・非定常状態の判定が、フィルタリング対象の位置で行われるようにしてもよいし、必要な演算用係数や入力係数が保持されているか否かによって行われるようにしてもよい。
【０１２６】
＜２．第２の実施の形態＞
［５×３フィルタを適用する場合の説明］
以上においては、９×７フィルタを用いてリフティング演算を行う場合について説明したが、リフティング演算は、どのようなフィルタを使用して行うようにしてもよい。例えば、５×３フィルタを用いるようにしてもよい。
【０１２７】
図１５は、５×３フィルタをリフティング表現した図である。図中、最上部の一列が入力信号列である。データ処理は画面上から下方向に流れ、以下の式（５）および式（６）により、高域係数および低域係数が出力される。
【０１２８】
ｄi1＝ｄi0−１／２（ｓi0＋ｓi+10）  ・・・（５）
ｓi1＝ｓi0＋１／４（ｄi-11＋ｄi1）  ・・・（６）
【０１２９】
図１６は、この５×３フィルタの場合の、垂直方向の係数群に対して、垂直分析フィルタリングを実行する様子の例を図示したものである。図１６に示されるように、１組の高域係数と低域係数を求めるためには、ライン１からライン４までの４ラインが必要になる。
【０１３０】
またリフティング演算の過程で生成される係数の一部は、次のリフティング演算で必要になる係数（演算用係数）なので、これをラッチ（記憶）しておく必要がある。図１６では楕円で囲んだ点線の領域が１つ前の垂直リフティング演算で生成される２個の演算結果の係数で、その下の実線の楕円で囲んだ領域は現在の垂直リフティング演算で生成される２個の演算結果の係数である。
【０１３１】
つまり、演算用係数は、１個の高域係数よりなる。つまり、この５×３フィルタの場合、１個の演算用係数と、最後のラインの入力係数が次のリフティング演算に利用される（つまり、これらの係数がラッチされる）。
【０１３２】
図１６に示されるように、５×３フィルタの場合も、リフティング演算の特徴から１ラインが追加入力されても垂直分析フィルタリングは実行不可能である。図１７の左に示される時刻１は、前回垂直分析フィルタリングが行われた時の状態を示し、図１７の右に示される時刻２は、その次の垂直分析フィルタリングが行われる時の状態を示している。
【０１３３】
このように、垂直分析フィルタリングを行うためには、９×７フィルタの場合と同様に２ライン追加する必要がある。その結果、１組の低域成分と高域成分が生成される。以後、同様にして、順次２ラインが追加入力される度に、１組の低域成分と高域成分が生成される。
【０１３４】
以上においては、垂直方向の分析フィルタリングについて説明したが、水平分析フィルタリングの場合も同様であり、ラインをコラムに置き換えれば、上述した説明を水平分析フィルタリングの場合に適用することができる。
【０１３５】
５×３フィルタの場合も、非定常状態においては、対象拡張が行われる。したがって、５×３フィルタの場合、非定常状態のときは、３ライン（３コラム）の入力データが必要であり、定常状態のときは、２ライン（２コラム）の入力データが必要である。
【０１３６】
このようにフィルタによって分析フィルタリングに必要な入力データのライン（コラム）数は変化するが、処理の実行方法は基本的に９×７フィルタの場合と同様である。つまり、フィルタの種類によらず、スケジューラ１１１は、定常状態と非定常状態に分けて水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、それぞれの状態において適切な間隔で分析フィルタリングを実行させることができる。
【０１３７】
これにより、スケジューラ１１１は、ウェーブレット変換処理のメモリ使用量を低減させることができる。
【０１３８】
具体的には、５×３フィルタを用いる場合、スケジューラ１１１は、水平分析フィルタ部１１２を制御し、非定常状態のとき、３コラム分の入力データに対して水平分析フィルタリングを実行させる。また、スケジューラ１１１は、水平分析フィルタ部１１２を制御し、定常状態のとき、２コラム分、入力データが入力される毎に水平分析フィルタリングを実行させる。
【０１３９】
さらに、スケジューラ１１１は、垂直分析フィルタ部１１４を制御し、非定常状態のとき、３ライン分の係数に対して垂直分析フィルタリングを実行させる。また、スケジューラ１１１は、垂直分析フィルタ部１１４を制御し、定常状態のとき、２ライン分の係数が取得する毎に垂直分析フィルタリングを実行させる。
【０１４０】
なお、以上のような、５×３フィルタを用いて分割レベル２以上に分割させる場合、スケジューラ１１１は、水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、図１８に示されるように分析フィルタリングを複数回繰り返し実行させる。
【０１４１】
つまり、ウェーブレット変換装置１００は、スケジューラ１１１の制御により、３ライン分の原画像（Source画像）が入力されると、１ライン分の分割レベル１の係数を生成する。
【０１４２】
非定常状態および定常状態についてこの処理が繰り返し実行され、７ライン分の原画像から３ライン分の分割レベル１の係数が生成される。ウェーブレット変換装置１００は、この３ライン分の分割レベル１の係数から１ライン分の分割レベル２の係数を生成する。
【０１４３】
同様に、各状態についてこのような処理が繰り返し実行され、１５ライン分の原画像から７ライン分の分割レベル１の係数が生成される。さらに、その７ライン分の分割レベル１の係数から３ライン分の分割レベル２の係数が生成される。ウェーブレット変換装置１００は、この３ライン分の分割レベル２の係数から１ライン分の分割レベル３の係数を生成する。
【０１４４】
さらに同様に、各状態についてこのような処理が繰り返し実行され、３１ライン分の原画像から１５ライン分の分割レベル１の係数が生成される。さらに、その１５ライン分の分割レベル１の係数から７ライン分の分割レベル２の係数が生成される。さらに、その７ライン分の分割レベル２の係数から３ライン分の分割レベル３の係数が生成される。ウェーブレット変換装置１００は、この３ライン分の分割レベル３の係数から１ライン分の分割レベル４の係数を生成する。
【０１４５】
スケジューラ１１１は、このような制御を繰り返し、ピクチャの全ラインについて分析フィルタリングを実行させる。このように制御することにより、スケジューラ１１１は、ウェーブレット変換処理におけるメモリの使用量を低減させることができる。
【０１４６】
＜３．第３の実施の形態＞
［エンコーダの構成例］
図１に示されるウェーブレット変換装置１００は、処理部として構成されるようにし、他の処理部と組み合わせることにより他の装置として構成されるようにしてもよい。例えば、符号化装置として構成されるようにしてもよい。
【０１４７】
図１９は、図１のウェーブレット変換装置１００を処理部として用いた符号化装置の構成例を示すブロック図である。図１９において、符号化装置３００は、入力される画像信号を符号化する装置である。符号化装置３００は、ウェーブレット変換部３０１、量子化部３０２、エントロピ符号化部３０３、およびレート制御部３０４を有する。
【０１４８】
ウェーブレット変換部３０１は、図１のウェーブレット変換装置１００と基本的に同様の構成とされる。ウェーブレット変換部３０１は、スケジューラ１１１が水平分析フィルタ部１１２および垂直分析フィルタ部１１４を制御し、所定の間隔で分析フィルタリングを実行させる。
【０１４９】
このとき、スケジューラ１１１は、状態を非定常状態と定常状態に分け、メモリ使用量を低減するように、それぞれの状態に適した間隔で分析フィルタリングを実行させる。ウェーブレット変換部３０１は、このように制御された分析フィルタリングを所定の分割レベルまで繰り返し、分析後の係数データを量子化部３０２に供給する。
【０１５０】
量子化部３０２は、ウェーブレット変換部３０１により生成される各成分の係数を、例えば量子化ステップサイズで除算することにより量子化し、量子化係数を生成する。
【０１５１】
この際、量子化部３０２は、ラインブロック毎に量子化ステップサイズを設定することができる。このラインブロックは、ある画像領域のすべての周波数成分（図４の場合、３ＬＬ乃至１ＨＨまでの１０個の周波数成分）の係数を包含しているため、ラインブロック毎に量子化を行えば、ウェーブレット変換の特徴である多重解像度分析の利点を活かすことができる。また、全画面でラインブロック数だけを決めればよいため、符号化装置３００の負荷も小さくて済む。
【０１５２】
さらに、画像信号のエネルギは一般的に低域成分に集中しており、また、人間の視覚上、低域成分の劣化が目立ちやすいという特性がある。そのため、量子化に際しては、低域成分のサブバンドでの量子化ステップサイズが結果的に小さな値になるように、重み付けを行うことが有効である。この重み付けにより、低域成分には相対的に多くの情報量が割り当てられるようになり、全体の主観的な画質が向上する。
【０１５３】
エントロピ符号化部３０３は、量子化部３０２で生成された量子化係数を情報源符号化し、圧縮された符号化コードストリームを生成する。情報源符号化としては、例えばJPEG方式やMPEG（Moving Picture Experts Group）方式で用いられているハフマン符号化や、JPEG2000方式で用いられているさらに高精度な算術符号化を用いることができる。
【０１５４】
ここで、エントロピ符号化をどの範囲の係数に対して行うかは、圧縮効率に直接関係する非常に重要な要素になる。例えば、JPEG方式やMPEG方式では、８×８のブロックに対してDCT変換を施し、生成された６４個のDCT変換係数に対してハフマン符号化を行うことで、情報を圧縮している。すなわち、６４個のDCT変換係数がエントロピ符号化の範囲になる。
【０１５５】
ウェーブレット変換部３０１では、８×８ブロックに対するDCT変換とは異なり、ライン単位でウェーブレット変換を施しているため、エントロピ符号化部３０３では、各周波数帯域独立に、且つ各周波数帯域内をＰライン毎に情報源符号化する。
【０１５６】
Ｐは１ラインが最低であるが、ライン数が少ない場合には参照情報が少なくて済み、メモリ容量を減らすことができる。逆に、ライン数が多い場合には情報量がその分増えるため、符号化効率が向上させることができる。
【０１５７】
しかしながら、Ｐが各周波数帯域内のラインブロックのライン数を超えた値になると、次のラインブロックのラインまで必要になる。このため、このラインブロックの量子化係数データがウェーブレット変換及び量子化によって生成されるまで待たなければならず、この時間が遅延時間となってしまう。
【０１５８】
したがって、低遅延のためには、Ｐはラインブロックのライン数以下である必要がある。例えば、図４の例では、３ＬＬ，３ＨＬ，３ＬＨ，３ＨＨの周波数帯域については、ラインブロックのライン数＝１ラインであるためＰ＝１となる。また、２ＨＬ，２ＬＨ，２ＨＨのサブバンドについては、ラインブロックのライン数＝２ラインであるためＰ＝１または２となる。
【０１５９】
レート制御部３０４は、最終的に目標のビットレート又は圧縮率に合わせるための制御を行い、レート制御後の符号化コードストリームを外部に出力する。例えば、このレート制御部３０４は、ビットレートを上げる場合には量子化ステップサイズを小さくし、ビットレートを下げる場合には量子化ステップサイズを大きくするように、量子化部３０２に対して制御信号を送信する。
【０１６０】
上述したように、ウェーブレット変換部３０１がウェーブレット変換のメモリ使用量を低減させることができるので、符号化装置３００は、符号化処理に必要なメモリの容量を低減させることができる。これにより、コストを低減させることができる。
【０１６１】
このような符号化装置３００は、例えば、画像信号やビデオ信号や画像を圧縮して伝送、受信して伸長して画像を出力する装置やシステムに適用することができる。
【０１６２】
具体的には、例えば、モバイル通信機、動画像録画機能付きカメラ、またはデジタルカメラに適用することができる。また、例えば、TV会議システム、監視カメラ・レコーダシステム、医用遠隔医療診断システム、放送局内のビデオ圧縮・伝送システム、またはライブ映像の配信システムにも適用することができる。
【０１６３】
さらに、例えば、生徒と教師間のインタラクティブ通信や無線での画像伝送にも適用することができる。また、例えば、対話型ゲームアプリケーションにも適用することができる。
【０１６４】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、図２０に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０１６５】
図２０において、パーソナルコンピュータ４００のCPU（Central Processing Unit）４０１は、ROM（Read Only Memory）４０２に記憶されているプログラム、または記憶部４１３からRAM（Random Access Memory）４０３にロードされたプログラムに従って各種の処理を実行する。RAM４０３にはまた、CPU４０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１６６】
CPU４０１、ROM４０２、およびRAM４０３は、バス４０４を介して相互に接続されている。このバス４０４にはまた、入出力インタフェース４１０も接続されている。
【０１６７】
入出力インタフェース４１０には、キーボードやマウスなどよりなる入力部４１１が接続される。また、入出力インタフェース４１０には、CRT（Cathode Ray Tube）、LCD（Liquid Crystal Display）、若しくは有機ELディスプレイ（Organic ElectroLuminescence Display）などよりなるディスプレイ、並びにスピーカなどよりなる出力部４１２も接続される。
【０１６８】
さらに、入出力インタフェース４１０には、ハードディスクやSSD（Solid State Drive）などより構成される記憶部４１３も接続される。また、入出力インタフェース４１０には、通信部４１４も接続される。
【０１６９】
通信部４１４は、例えば、モデム、LAN（Local Area Network）インタフェース、またはUSB（Universal Serial Bus）インタフェース等により構成される。また、通信部４１４は、例えば、IEEE（Institute of Electrical and Electronic Engineers）１３９４インタフェースにより構成されてもよい。さらに、通信部４１４は、例えば、ブルートゥースインタフェースまたは無線LANインタフェースなどにより構成される。通信部４１４は、インターネットを含むネットワークを介しての通信処理を行う。
【０１７０】
入出力インタフェース４１０にはまた、必要に応じてドライブ４１５が接続される。そのドライブ４１５には、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア４２１が適宜装着される。そのリムーバブルメディア４２１から読み出されたコンピュータプログラムが、必要に応じて記憶部４１３にインストールされる。
【０１７１】
上述した一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０１７２】
この記録媒体は、例えば、図２０に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布されるリムーバブルメディア４２１により構成される。
【０１７３】
このリムーバブルメディア４２１は、例えば、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）である。また、リムーバブルメディア４２１は、例えば、光ディスク（CD-ROM（Compact Disc - Read Only Memory）,DVD（Digital Versatile Disc）を含む）であってもよい。
【０１７４】
また、リムーバブルメディア４２１は、例えば、光磁気ディスク（MD（Mini Disc）を含む）であってもよい。さらに、リムーバブルメディア４２１は、例えば、半導体メモリであってもよい。
【０１７５】
なお、記録媒体は、このリムーバブルメディア４２１以外にも、例えば、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM４０２や、記憶部４１３に含まれるハードディスクであってもよい。
【０１７６】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７７】
また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表わすものである。
【０１７８】
なお、以上において、１つの装置（または処理部）として説明した構成を分割し、複数の装置（または処理部）として構成するようにしてもよい。逆に、以上において複数の装置（または処理部）として説明した構成をまとめて１つの装置（または処理部）として構成されるようにしてもよい。また、各装置（または各処理部）の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置（または処理部）の構成の一部を他の装置（または他の処理部）の構成に含めるようにしてもよい。つまり、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１７９】
【図１】本発明を適用したウェーブレット変換装置の主な構成例を示すブロック図である。
【図２】分析フィルタリングの概要を説明する図である。
【図３】分析フィルタリングの概要を説明する図２に続く図である。
【図４】ラインブロックを説明する図である。
【図５】９×７フィルタの例を示す図である。
【図６】リフティング演算例を説明する図である。
【図７】リフティング演算例を説明する図である。
【図８】分析フィルタリングの処理の様子を説明する図である。
【図９】分析フィルタリングの処理の様子を説明する図である。
【図１０】分析フィルタリングの処理の様子を説明する図である。
【図１１】分析フィルタリングの処理の様子を説明する図である。
【図１２】分析フィルタリングの処理の様子を説明する図である。
【図１３】ウェーブレット変換処理の流れの例を説明するフローチャートである。
【図１４】水平分析フィルタ処理の流れの例を説明するフローチャートである。
【図１５】５×３フィルタの例を示す図である。
【図１６】リフティング演算例を説明する図である。
【図１７】リフティング演算例を説明する図である。
【図１８】分析フィルタリングの処理の様子を説明する図である。
【図１９】本発明を適用した符号化装置の主な構成例を示すブロック図である。
【図２０】本発明を適用したパーソナルコンピュータの主な構成例を示すブロック図である。
【符号の説明】
【０１８０】
１００  ウェーブレット変換装置，  １１１  スケジューラ，  １１２  水平分析フィルタ部，  １１３  ラインバッファ，  １１４  垂直分析フィルタ部，  １１５  係数バッファ，  ３００  符号化装置，  ３０１  ウェーブレット変換部，  ３０２  量子化部，  ３０３  エントロピ符号化部，  ３０４  レート制御部
【図１】
2010136154.tif 000003
【図２】
2010136154.tif 000004
【図３】
2010136154.tif 000005
【図４】
2010136154.tif 000006
【図５】
2010136154.tif 000007
【図６】
2010136154.tif 000008
【図７】
2010136154.tif 000009
【図８】
2010136154.tif 000010
【図９】
2010136154.tif 000011
【図１０】
2010136154.tif 000012
【図１１】
2010136154.tif 000013
【図１２】
2010136154.tif 000014
【図１３】
2010136154.tif 000015
【図１４】
2010136154.tif 000016
【図１５】
2010136154.tif 000017
【図１６】
2010136154.tif 000018
【図１７】
2010136154.tif 000019
【図１８】
2010136154.tif 000020
【図１９】
2010136154.tif 000021
【図２０】
2010136154.tif 000022
【手続補正書】
【提出日】平成21年12月28日(2009.12.28)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
また、垂直分析フィルタリングに対して係数バッファ１１５を配置し、垂直分析フィルタリングを実行するのに最低限必要な係数がその係数バッファ１１５に記憶され、次の垂直分析フィルタリングの際にその係数が読み出されて使用されるようになされている。従ってこの係数バッファ１１５は、容量が小さいが、情報の読み出しや書き込みの速度（アクセス速度）が高速な内部メモリによって実現することができ、大容量だがアクセス速度が遅い外部メモリを用いる必要がない。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
step１：ｄi1＝ｄi0＋α（ｓi0＋ｓi+10）  ・・・（１）
step２：ｓi1＝ｓi0＋β（ｄi-11＋ｄi1）  ・・・（２）
step３：ｄi2＝ｄi1＋γ（ｓi1＋ｓi+11）  ・・・（３）
step４：ｓi2＝ｓi1＋δ（ｄi-12＋ｄi2）  ・・・（４）
（α＝-1.586134342，β＝-0.05298011857，γ＝0.8829110755，δ＝0.4435068520）
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2010136154.tif 000023