(57)【特許請求の範囲】
【請求項１】
フレームメモリからブロック単位でデータを読み込み、ｎレベル（ｎは３以上の整数）のウェーブレット変換処理を行い、得られたｎレベルのウェーブレット変換係数の周波数帯信号を前記フレームメモリに書き戻すウェーブレット変換装置であって、
前記フレームメモリから読み込まれたデータを一時的に記憶するメモリと、
少なくとも一つの第１演算要素及び複数の第２演算要素からなる演算部とを具備し、
前記複数の第２演算要素は、前記フレームメモリから読み込まれた注目ブロックの周囲のブロックのデータからそれぞれレベル（ｎ−１）のウェーブレット変換係数中の低周波数帯信号を計算し、
前記第１演算要素は、前記フレームメモリから読み込まれた前記注目ブロックのデータに対するｎレベルのウェーブレット変換処理を実行し、その際にレベルｎのウェーブレット変換処理は、該第１演算要素で得られたレベル（ｎ−１）の低周波数帯信号と前記複数の第２演算要素によって計算されたレベル（ｎ−１）の低周波数帯信号とを用いて行って、ｎレベルのウェーブレット変換係数の全周波数帯信号を計算し、
前記第１演算要素のウェーブレット変換処理で得られたｎレベルの全周波数帯信号がブロック単位で前記フレームメモリに書き戻されることを特徴とするウェーブレット変換装置。
【請求項２】
前記第１演算要素が各レベル対応のワークメモリを２面ずつ具備し、前記第２演算要素がワークメモリを２面具備し、前記フレームメモリの隣接する２ブロックのデータに対するウェーブレット変換処理が連続的に実行され、かつ、ウェーブレット変換処理と前記フレームメモリからのデータの読み込み及び前記フレームメモリへの周波数帯信号の書き戻が並行して行われることを特徴とする請求項１記載のウェーブレット変換装置。
【請求項３】
前記第１演算要素が、レベル１のウェーブレット変換処理に使用される第１フィルタとレベル２〜ｎのウェーブレット変換処理に使用される第２フィルタを具備するとともに各レベルの低周波数帯信号を計算するための手段を具備し、前記第１演算要素において、注目ブロックのデータに対するレベル１のウェーブレット変換処理とレベル２〜ｎのウェーブレット変換処理が並行して実行されることを特徴とする請求項２記載のウェーブレット変換装置。
【請求項４】
前記第１演算要素の各レベル対応のワークメモリが独立にアクセス可能な４個のメモリに分割されるとともに、前記第１演算要素がレベル１のウェーブレット変換処理に使用される第１フィルタとレベル２〜ｎのウェーブレット変換処理に使用される第２フィルタを具備し、ウェーブレット変換処理が前記２個のフィルタを使用して並列処理により実行されることを特徴とする請求項２記載のウェーブレット変換装置。
【請求項５】
前記第１演算要素のウェーブレット変換処理によって得られた周波数帯信号の一部を一時的に記憶するためのバッファメモリをさらに具備し、このバッファメモリは外部からアクセス可能であることを特徴とする請求項１、２又は３記載のウェーブレット変換装置。
【請求項６】
フレームメモリと、このフレームメモリにアクセス可能な請求項１、２、３又は４記載のウェーブレット変換装置と、前記フレームメモリにアクセス可能な符号化復号化器とを具備する符号化復号化装置。
【請求項７】
フレームメモリと、このフレームメモリにアクセス可能な請求項５記載のウェーブレット変換装置と、前記フレームメモリ及び前記ウェーブレット変換装置のバッファメモリにアクセス可能な符号化復号化器とを具備する符号化復号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にはウェーブレット変換を利用するシステム全般に係り、特に、画像データ等の圧縮・伸長システムに用いられるウェーブレット変換装置と符号化復号化装置に関する。
【０００２】
【従来の技術】
ウェーブレット変換は、周波数領域と時間領域を同時に表現できるという、フーリエ変換等には無い特長を有することで注目され、近年応用分野が広がりつつある。特に、データ圧縮ヘの応用は、大量のデータの蓄積及び伝送のために非常に有用である。例えば、文書のファクシミリ伝送、あるいはワールドワイドウエブのような画像の伝送に要する時間は、圧縮を使ってその画像の再生に必要とされるビット数を滅らすと、飛躍的に短縮される。
【０００３】
従来より、多くの様々なデ−タ圧縮手法が存在している。最も広く普及している圧縮方式としてＪＰＥＧ（Joint Photographic Experts Group）がある。ＪＰＥＧにおいては、入力シンボルまたは輝度データは量子化されてから出力符号語ヘ変換される。量子化は、データの重要な特徴量を保存する一方、重要でない特徴量を除去することを目的としている。量子化に先立ち、エネルギー集中のために変換が用いられるが、この変換として採用されているのがＤＣＴ（Discrete Cosine Transform）である。ところが、このＤＣＴを用いているＪＰＥＧに対して、さまざまな欠点が指摘されている。例えば、ブロックノイズやモスキートノイズが発生する問題である。画像信号処理の応用においては、これらの欠点を解消できる、効率的かつ高精度のデータ圧縮符号化方式を追求することに関心が集中している。その方式の中に、ウェーブレット（wavelet）処理方式がある。
【０００４】
２次元信号にウェーブレット変換を適用する場合には、水平方向低域通過型フィルタＨＬ（Horizontal Low）及び水平方向高域通過型フィルタＨＨ（Horizon−tal High）を使用して水平方向低域信号（Ｓ（Smooth）係数）及び水平方向高域信号（Ｄ(Detail)係数）に分離し、さらに各々のＳ係数及びＤ係数に対して垂直方向低域通過型フィルタＶＬ（Vertical Low）及び垂直方向高域通過型フィルタＶＨ（Vertical High）を使用して水平方向低域−垂直方向低域信号（ＳＳ係数）、水平方向低域−垂直方向高域信号（ＳＤ係数）、水平方向高域−垂直方向低域言号（ＤＳ係数）、及び水平方向高域−垂直方向高域信号（ＤＤ係数）に分離する。水平処理と垂直処理を１回行った出力をレべル１の出力と呼ぶ。また、上記の４種類の信号を周波数帯信号と呼ぶ。レべル２以上の出カを希望するのであれば、この処理をＳＳ係数に対して再帰的に行えばよい。レべル２ではＳＳ係数と、１ＳＤ係数及び２ＳＤ係数、１ＤＳ係数及び２ＤＳ係数、１ＤＤ係数及び２ＤＤ係数、の７つの周波数帯信号が得られる。最初に水平方向にフィルタを用い、次に垂直方向にフィルタを用いる場合について説明したが、この順序は逆でもよい。
【０００５】
ウェーブレット変換を利用する符号化復号化装置においては、以上の過程を経て得られた各周波数帯信号が符号化復号化部で圧縮される。圧縮は周波数帯信号毎にビット単位で行われる。ある周波数帯信号の、一番最初の画素のＭＳＢが処理の対象となる。この画素自体の状態と、周辺の画素の状態及び１つ上のレべルの状態が参照され、出カが決定される。次は、２番目の画素のＭＳＢが処理の対象となるのであるが、この際に一番最初に処理された画素の状態も参照される。以下、符号化されるべき領域に対しての一達の処理が終了すると、一番最初の画素の１つ下位の（ＭＳＢ―１）ビットが処理の対象となる。この際は同じビット深さの周辺画素の状態に加えて、ＭＳＢの状態も参照される。このようにして、符号化されるべき領域に対してＬＳＢまで符号化が行われる。復号化もほぼ同じ手順を経て行われる。
【０００６】
図３７は、従来のウェーブレット変換装置の一般的な構成であり、フレームメモリ４００、制御部４０１及びフィルタ４０２から構成される。フィルタ４０２にはどのような構成のものを用いてもよいが、ここでは低域通過型フィルタとしては２組のデータを用いて演算を行う２タップのフィルタを使用するものとする。高域通過型フィルタとしては、低域通過型フィルタの出力であるＳ係数のうち、現在の位置と１つ前及び１つ後の合計３組のデータを用いて演算を行う、６タップのフィルタを使用するものとする。
【０００７】
図３８に、上記フィルタを用いた場合のウェーブレット変換の処理の例を示す。（ａ）が水平方向の処理を示し、（ｂ）が垂直方向の処理を示す。同図（ａ）において、例えば００は０ライン目の０画素目のデータを意味し、１２は１ライン目の２画素目のデ−タを意味する（ライン、画素とも０番目から数えるものとする）。水平処理においては、同図（ａ）に示すように、水平方向低域通通型フィルタＨＬの０画素目の出力Ｓ００は、データ００と０１から求められ、１画素目の出力Ｓ０１はデータ０２と０８から求められる。また、水平方向高城通通型フィルタＨＨの０画素目の出力Ｈ００は、データ００の２つ前と１つ前のデータ（実在しない）、デ−タ００と０１、デ‐タ０２と０３から求められる。また、垂直処理においては、同図（ｂ）に示すように、垂直方向低域通過型フィルタＶＬの出力ＳＳ００は、データＳ００とＳ１０から求められる。垂直方向高域通過型フィルタＶＨの出力ＳＤ００は、データＳ００の２つ前と１つ前のデータ（実在しない）、データＳ００とＳ１０、データＳ２０とＳ３０から求められる。
【０００８】
図３９はウェーブレット変換が施される前のフレームメモリ上のデータを示している。このデータに対し、初めに水平方向の処理が施され、得られたＳ係数及びＤ係数が図４０のようなマッピングでフレームメモリに書き込まれる。図４０中、例えば１Ｓ００はレべル１のアドレス００のＳ係数を意味する。図４１は垂直処理を行った後の各係数を書き込む際のマッピングの例である。ここまでがレべル１の各係数の格納方法である。図４２はレべル２の水平方向の各係数の格納方法の例である。レべル２の処理は１ＳＳ係数に対してのみ行われるため、斜線で示した部分のデ‐タは用いられないことに注意されたい。次いで図４３に示すようなマッピングでレべル２の各係数が格納され、レべル２の処理が終了する。以下、所望のレべルの周波数帯信号が得られるまで順次処理が施される。
【０００９】
図４４に、従来の一般的なウェーブレット変換装置のタイミングチャートを示す。データのサイズを、画素方向サイズＸが１０２４、ライン方向サイズＹが１０２４、トー夕ル１ＭＢとし、レべル４までの処理を行う場合の処理時間について説明する。
【００１０】
時刻ｔ０からｔ１で、フレームメモリの全データに対してレべル１の処理を行い、時刻ｔ１からｔ２でレべル２の処理を行い、時刻ｔ２からｔ３でレべル３の処理を行い、時刻ｔ３からｔ４でレべル４の処理を行う。処理時間は、Ｘ＝Ｙ＝１０２４であるから、レべル１で１０２４×１０２４×４（４の内訳：画素方向の読み出し、画素方向の書き込み、ライン方向の読み出し、及びライン方向の書き込み）、レべル２で５１２×５１２×４、レべル３で２５６×２５６×４、そしてレべル４で１２８×１２８×４であり、トータルでは５４４０ｋクロック（１ｋ＝１０２４）となる。
【００１１】
ただし、この数値は、フレームメモリに対するライン方向の読み出し／書き込みのレイテンシが０の場合の最小の時間である。ＳＤＲＡＭ等の最近のメモリではバースト転送が行われるのが普通であり、画素方向のデータ転送は高速で行えるが、ライン方向のデータ転送はセンスアンプヘのプリチャージが必要となるためレイテンシ（遅れ）が発生する。これを回避するためにバンク切り替え等の手法が用いられることがあるが、ウェーブレット変換のように続けてライン方向のアクセスが発生するような場合には効果は期待できない。仮にレイテンシが２であった場合、処理時間は１０８８０ｋクロックに増加する。このレイテンシは前述の理由から回避するのは非常に困難であった。
【００１２】
符号化復号化装置においては、ウェーブレット変換の終了後、フレームメモリに書込まれた各周波数帯信号が符号化復号化器によって符号化される。画像信号は、隣接画素の相関、特に同一ビットプレーン内での相関が高いという特性を活かして圧縮率を上げている。このため、符号化の際には、あるまとまった領域のデータをビット単位（ある画素のデ‐タの、任意の１ビット）で扱っている。復号化は以上述べた動作のほぼ逆順で得られる。
【００１３】
なお、本発明に関連する符号化復号化装置、ウェーブレット変換装置、ウェーブレット変換のためのフィル夕に関するより詳細な情報は、特開平８−１３９９３５号公報などに見られる。また、符号化復号化器については、特開平９‐１２１１６８号公報に詳しい。更に、類似のウェーブレット変換装置に関する公知文献としては、特開平３‐２７６８７号公報、特開平５‐１６７９９７号公報、特開平５−１８３８８６号公報などがある。
【００１４】
【発明が解決しようとする課題】
従来、フレームメモリを介してウェーブレット変換を行う場合、前述のように、画素（水平）方向の処理は比較的高速に行うことができるが、ライン（垂直）方向の処理はフレームメモリのアクセス時にレイテンシが発生し、トータルの処理時間が非常に大きくなってしまうという問題があった。また、処理がレべル順で行われるため、高レべルの周波数帯信号が得られるまで時間がかかり、それまで符号化復号化処理を開始できないという問題があった。
【００１５】
よって、本発明の目的は、フレームメモリにＳＤＲＡＭのようなメモリが使用された場合にも、レイテンシの問題を解決し高速なウェーブレット変換処理が可能なウェーブレット変換装置を提供することにある。本発明のもう一つの目的は、全レベルの周波数帯信号をほぼ同時刻に得られる高速なウェーブレット変換装置を提供することにある。本発明の他の目的は、ウェーブレット変換を利用する高速な符号化復号化装置を提供することにある。
【００１６】
【課題を解決するための手段】
請求項１の発明は、フレームメモリからブロック単位でデータを読み込み、ｎレベル（ｎは３以上の整数）のウェーブレット変換処理を行い、得られたｎレベルのウェーブレット変換係数の周波数帯信号を前記フレームメモリに書き戻すウェーブレット変換装置であって、前記フレームメモリから読み込まれたデータを一時的に記憶するメモリと、少なくとも一つの第１演算要素及び複数の第２演算要素からなる演算部とを具備し、前記複数の第２演算要素は、前記フレームメモリから読み込まれた注目ブロックの周囲のブロックのデータからそれぞれレベル（ｎ−１）のウェーブレット変換係数中の低周波数帯信号を計算し、前記第１演算要素は、前記フレームメモリから読み込まれた前記注目ブロックのデータに対するｎレベルのウェーブレット変換処理を実行し、その際にレベルｎのウェーブレット変換処理は、該第１演算要素で得られたレベル（ｎ−１）の低周波数帯信号と前記複数の第２演算要素によって計算されたレベル（ｎ−１）の低周波数帯信号とを用いて行って、ｎレベルのウェーブレット変換係数の全周波数帯信号を計算し、前記第１演算要素のウェーブレット変換処理で得られたｎレベルの全周波数帯信号がブロック単位で前記フレームメモリに書き戻されることを特徴とする。
【００１７】
請求項２の発明は、請求項１記載のウェーブレット変換装置において、前記第１演算要素が各レベル対応のワークメモリを２面ずつ具備し、前記第２演算要素がワークメモリを２面具備し、前記フレームメモリの隣接する２ブロックのデータに対するウェーブレット変換処理が連続的に実行され、かつ、ウェーブレット変換処理と前記フレームメモリからのデータの読み込み及び前記フレームメモリへの周波数帯信号の書き戻が並行して行われることを特徴とする。
【００１８】
請求項３の発明は、請求項２記載のウェーブレット変換装置において、前記第１演算要素が、レベル１のウェーブレット変換処理に使用される第１フィルタとレベル２〜ｎのウェーブレット変換処理に使用される第２フィルタを具備するとともに各レベルの低周波数帯信号を計算するための手段を具備し、前記第１演算要素において、注目ブロックのデータに対するレベル１のウェーブレット変換処理とレベル２〜ｎのウェーブレット変換処理が並行して実行されることを特徴とする。
【００１９】
請求項４の発明は、請求項２記載のウェーブレット変換装置において、前記第１演算要素の各レベル対応のワークメモリが独立にアクセス可能な４個のメモリに分割されるとともに、前記第１演算要素がレベル１のウェーブレット変換処理に使用される第１フィルタとレベル２〜ｎのウェーブレット変換処理に使用される第２フィルタを具備し、ウェーブレット変換処理が前記２個のフィルタを使用して並列処理により実行されることを特徴とする。
【００２０】
請求項５の発明は、請求項１、２又は３記載のウェーブレット変換装置において、前記第１演算要素のウェーブレット変換処理によって得られた周波数帯信号の一部を一時的に記憶するためのバッファメモリをさらに具備し、このバッファメモリは外部からアクセス可能であることを特徴とする。
【００２１】
請求項６の発明は、フレームメモリと、このフレームメモリにアクセス可能な請求項１、２、３又は４記載のウェーブレット変換装置と、前記フレームメモリにアクセス可能な符号化復号化器とを具備する符号化復号化装置を特徴とする。
【００２２】
請求項７の発明は、フレームメモリと、このフレームメモリにアクセス可能な請求項５記載のウェーブレット変換装置と、前記フレームメモリ及び前記ウェーブレット変換装置のバッファメモリにアクセス可能な符号化復号化器とを具備する符号化復号化装置を特徴とする。
【００２３】
【発明の実施の形態】
以下、添付図面を参照し本発明の実施の形態について説明するが、説明を簡略にするため、添付図面中の複数の図面において同一部分又は対応部分には同一又は同様の参照番号を用いる。
【００２４】
なお、ウェーブレット変換の水平処理及び垂直処理のためのフィルタとして、２タップの低域通過型フィルタと、６タップの高域通過型フィルタをそれぞれ用いるものとする。また、ウェーブレット変換はレベル４まで行うものとする。すなわち、ｎ＝４とする。もちろん、レベル数はｎ＝３以上いくつに設定しても構わない。本発明は、レベル数が増えるほど大きな効果を発揮する。
【００２５】
図１は、本発明による符号化復号化装置の全体構成の一例を示す。符号化時には、フレームメモリ１００に外部からデータｄａｔａが書き込まれる。データがブロック単位で本発明によるウェーブレット変換装置１０１に読み込まれてブロック単位でウェーブレット変換処理が施され、得られた全ウェーブレット・レベルの周波数帯信号がブロック単位でフレームメモリ１００に書き戻される。この周波数帯信号を符号化復号化器１０２により符号化し、コードストリームｃｏｄｅとして外部に出力する。復号化時には、外部から入力されるコードストリームｃｏｄｅを符号化復号化器１０２で復号化して、ウェーブレット変換の各周波数帯信号をフレームメモリ１００上に復元する。これら周波数帯信号に対しウェーブレット変換装置１０１によって逆ウェーブレット変換が施され、元データがフレームメモリ１００上に復元され、それがｄａｔａとして外部に出力される。
【００２６】
本発明によるウェーブレット変換装置１０１は、ブロック単位でウェーブレット変換処理を行い、ブロック単位で全ウェーブレット・レベルの周波数帯信号をフレームメモリ１００に書き戻す。したがって、符号化復号化器１０２は、ウェーブレット変換処理を開始後すぐに符号化処理を開始し、ウェーブレット変換処理と並行して符号化処理を実行することができ、従来のように最高レベルの周波数帯信号が得られるまで符号化処理の開始を待たされることはない。したがって、後述のように本発明によるウェーブレット変換装置１０１が高速であることと相俟って、本発明の符号化復号化装置は従来よりはるかに高速な動作が可能である。
【００２７】
本発明による第１の実施例によれば、ウェーブレット変換装置１０１は図２に示すような内部構成を有する。このウェーブレット変換装置１０１は、演算部２００と、フレームメモリ１００から読み込まれたデータを一時的に記憶するためのカレントメモリ２０２及びキャッシュメモリ（ＣＭ１，ＣＭ２，ＣＭ３，ＣＭ４）２０３，２０４，２０５，２０６、装置全体のタイミング制御や装置内部及び外部とのデータ転送の制御などを行う主制御部２０７で構成される。演算部２００は、３×３個の演算要素（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ）２０１ａ，２０１ｂ，２０１ｃ，２０１ｄ，２０１ｅ，２０１ｆ，２０１ｇ，２０１ｈ，２０１ｉからなる。
【００２８】
本発明の第１の実施例によれば、演算要素（Ｅ）２０１ｅは図３に示すような構成とされる。図３に見られるように、演算要素（Ｅ）２０１ｅは、ＳＳ計算部２１０を含む制御部２１１、レベル１の水平処理及び垂直処理に使用されるフィルタ（１）２１３、レベル２，３，４の水平処理及び垂直処理に使用されるフィルタ（２）２１４を具備し、さらに、各レベルに対応したワークメモリを２面ずつ具備する。すなわち、レベル１対応のワークメモリとして、第０面のワークメモリ（Ｌ１＿０）２１６と第１面のワークメモリ（Ｌ１＿１）２１７、レベル２対応のワークメモリとして、第０面のワークメモリ（Ｌ２＿０）２１８と第１面のワークメモリ（Ｌ２＿１２１９）、レベル３対応のワークメモリとして、第０面のワークメモリ（Ｌ３＿０）２２０と第１面のワークメモリ（Ｌ３＿１）２２１、レベル４対応のワークメモリとして、第０面のワークメモリ（Ｌ４＿０）２２２と第１面のワークメモリ（Ｌ４＿１）２２３を備えている。制御部２１１は、演算要素（Ｅ）２０１ｅの内部のデータの転送、ＳＳ計算部２１０の動作タイミングの制御、主制御部２０７との間でデータの受け渡し等を行う部分である。ＳＳ計算部２１０は、レベル１，２，３のＳＳデータの計算を行う部分である。
【００２９】
本発明の第１の実施例によれば、レベル１対応のワークメモリ（Ｌ１＿０，Ｌ１＿１）２１６，２１７、キャッシュメモリ（ＣＭ１，ＣＭ３，ＣＭ４）２０３，２０５，２０６は、図４に示すように、ａ（画素方向）×ａ（ライン方向）のサイズを持つメモリである。キャッシュメモリ（ＣＭ２）２０４は図５に示すようなサイズのメモリである。レベル２対応のワ―クメモリ（Ｌ２＿０，Ｌ２＿１）２１８，２１９は、図６に示すように、ａ／２×ａ／２のサイズを持つメモリである。レベル３対応のワークメモリ（Ｌ３＿０、Ｌ３＿１）２２０，２２１は、図７に示すように、ａ／４×ａ／４のサイズである。レベル４対応のワークメモリ（Ｌ４＿０、Ｌ４＿１）２２２，２２３のサイズは、図８に示すように、画素方向、ライン方向共にａ／８である。図９はフレームメモリ１００のサイズを表す図であり、画素方向のサイズがＸ、ライン方向のサイズがＹである。図１０はカレントメモリ２０２のサイズを表す図であり、画素方向のサイズがＸ、ライン方向のサイズがａである。
【００３０】
本発明の第１の実施例によれば、演算要素（Ｅ）２０１ｅ以外の演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉはそれぞれ図１１に示すように、ＳＳ計算部２３０を含む制御部２３１と、ａ／８×ａ／８のサイズの２面のワークメモリ、すなわち第０面のワークメモリ（Ｌ４＿０）２３３及び第１面のワークメモリ（Ｌ４＿１）２３４から構成される。ＳＳ計算部２３０は、ウェーブレット・レベル３のＳＳデータの計算を行う部分である。制御部２３１は、演算要素内部のデータ転送の制御、ＳＳ計算部２３０の動作タイミングの制御、主制御部２０７との間でデータの受け渡し等を行う部分である。ＳＳ計算部２３０によって計算されたＳＳデータはワークメモリ（ｌ４＿０，Ｌ４＿１）２３３，２３４に格納される。
【００３１】
このような構成の本発明によるウェーブレット変換装置１０１は、ａ×ａのサイズのブロックを単位として処理を行う。この基本サイズの“ａ”はウェーブレット変換に用いるフィルタのタップ数と所望するウェーブレット・レべル数に基づいて決定される。ａが小さいほど、ウェーブレット変換装置１０１内部の各メモリのサイズを小さくすることができるというメリットがあるが、ａを決定する際には処理速度も考慮しなければならない。具体的には、以下で述べるような考え方で決定するのが良いであろう。
【００３２】
所望する最高のウェーブレット・レべルが４であり、かつ高域通過型フィルタが６タップであることから、レべル３のＳＳデータが６個あれば、レべル４のＳＳ、ＳＤ、ＤＳ、ＤＤデータを１個ずつ得られる。このための元データの最小サイズは４８×４８（１６×１６のサイズのブロックが３×３個）となる。すなわち、ａ＝１６が最小サイズである。以下、ａ＝１６として説明する。なお、仮に高域通過型フィルタが１０タップ、所望する最高レべルが５であれば、元データの最小サイズは１６０×１６０（３２×３２のサイズのブロックが５×５個）となり、ａ＝３２となる。
【００３３】
さて、ａ＝１６とした場合、Ｘ＝Ｙ＝１０２４であると、ウェーブレット変換装置１０１内部のメモリのワード数（ビット深さはフィルタの構成により異なる）は、次の通りである。まず、演算要素（Ｅ）２０１ｅにおいては、
ワークメモリ（Ｌ１＿０，Ｌ１＿１）で１６×１６×２＝５１２ワード
ワークメモリ（Ｌ２＿０，Ｌ２＿１）で８×８×２＝１２８ワード
ワークメモリ（Ｌ３＿０，Ｌ３＿１）で４×４×２＝３２ワード
ワークメモリ（Ｌ４＿０，Ｌ４＿１）で２×２×２＝８ワード
となる。それ以外の演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉのそれぞれにおいては、ワークメモリ（Ｌ４＿０，Ｌ４＿１）で２×２×２＝８ワードである。したがって、全演算部のワークメモリの合計ワード数は７４４ワードとなる。キャッシュメモリ（ＣＭ１，ＣＭ３，ＣＭ４）２０３，２０５，２０６で１６×１６×８＝７６８ワード、キャッシュメモリ（ＣＭ２）２０４で３２×６４−（１６×１６）＝１７９２ワード、したがってキャッシュメモリ全体で２５６０ワードとなる。カレントメモリ２０２は１０２４×１６＝１６３８４ワードである。よって、ウェーブレット変換装置１０１内部のトータルのメモリ・ワード数は１９６８８ワードとなり、１ｋ＝１０２４とすると１９ｋワード強と非常に小さいメモリ量で済む。また、この数値はフレームメモリ１００のライン方向のサイズとは無関係で、画素方向のサイズのみに依存する。
【００３４】
このウェーブレット変換装置１０１の動作の概略は次の通りである。フレームメモリ１００上のデータを１６×１６（ａ×ａ）のサイズのブロックに分割し、３×３個のブロック中の中央ブロックに対するウェーブレット変換処理を演算要素（Ｅ）２０１ｅで実行するとともに、周囲の８個のブロックに対するレベル３のＳＳデータの計算を演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉで行う。演算要素（Ｅ）２０１ｅは、レベル３までは対応ブロックの元データのみを用いてウェーブレット変換処理を行うことができるが、元データのサイズは１６×１６であるため、レベル３では２×２個のＳＳデータしか得られない（図１２に、１６×１６のサイズのブロック１個あたりのレベル３までの周波数帯信号のマッピングの一例を示した。この中に、ＳＳデータが２×２個含まれているのが解る）。６タップの高域通過型フィルタを用いる関係から、レベル４の変換のためにはレベル３のＳＳデータを少なくとも６×６個必要とする。演算要素（Ｅ）２０１ｅは、その不足したレベル３のＳＳデータとして、演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉの内部のワークメモリ（Ｌ４＿０又はＬ４＿１）２３３又は２３４に得られたＳＳデータを用いることにより、レベル４の変換処理を実行する。このようにして演算要素（Ｅ）２０１ｅの内部のワークメモリに得らる１ブロック分のレベル１からベル４までの周波数帯信号は、フレームメモリ１００の対応領域に書き戻される。
【００３５】
本実施例においては、このような演算要素（Ｅ）２０１ｅによるレベル４までのウェーブレット変換処理を、横方向に隣接した２ブロックに対して連続的に実行できるようにするため、前述のように、演算要素（Ｅ）２０１ｅは各レベル対応のワークメモリを２面ずつ持ち、それ以外の各演算要素も２×２のサイズのワークメモリを２面備えている。また、演算要素（Ｅ）２０１ｅは、レベル１の変換と他のレベルの変換を並列処理によって高速に実行するため、かつ、レベル２からレベル４の各レベルの変換を任意の順序で実行できるようにするため、前述のように、水平処理及び垂直処理用の２つの独立して動作するフィルタ２１３，２１４を備えるとともに、レベル１，２，３のＳＳデータの計算を行うＳＳ計算部２１０を備えている。
【００３６】
演算要素（Ｅ）２０１ｅの内部のワークメモリに得られた変換データは逐次、ブロック単位でフレームメモリ１００に書き戻されるので、他のブロックの処理のために各演算要素が必要とする一部の元データが書き換えられてしまう。このような書き換えられてしまう元データの一時記憶、及び、読み込んだデータの再読込みを回避するため、前述のようなカレントメモリ２０２とキャッシュメモリ（ＣＭ１〜ＣＭ４）２０３〜２０６が利用される。主制御部２０７は、３×３ブロック分の元データを（実在しないデータについてはミラーリングにより）常に準備するように動作し、また、それらメモリ及びフレームメモリ１００のデータを演算要素２０１ａ〜２０１ｉに対し振り分ける働きをする。この振り分け方は、以下に述べるように、フレームメモリ１００のどのブロックのデータを処理するかによって異なる。
【００３７】
図１３乃至図２１は、処理の進行の様子を説明するための図である。前述のように、演算要素（Ｅ）２０１ｅにはレベル対応のワークメモリが２面ずつ、その他の演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉの内部にはワークメモリが２面用意されている。図１３乃至図２１中の３×３の実線の格子は、第０面側のワークメモリを使用した処理に関連する演算要素（Ａ〜Ｉ）２０１ａ〜２０１ｉに対応した３×３個のブロックの位置を示し、３×３の点線の格子は、第１面側のワークメモリを使用した処理の際の演算要素（Ａ〜Ｉ）２０１ａ〜２０１ｉに対応したブロックの位置を示している。また、図１３乃至図２１において、０＿０，１＿０などはブロック名であり、ブロック名の前側の数字はライン方向（縦方向）のブロック・アドレス、後側の数字は画素方向（横方向）のブロック・アドレスを示している。
【００３８】
図２２は、演算要素（Ａ〜Ｉ）２０１ａ〜２０１ｉに必要な元データのキャッシュのためにキャッシュメモリ（ＣＭ１〜ＣＭ４）２０３〜２０６がどのようにの割り当てられるかを示している。なお、Ａ０〜Ｉ０は演算要素（Ａ〜Ｉ）２０１ａ〜２０１ｉが第０面のワークメモリを使用する場合に必要となるデータを意味し、Ａ１〜Ｉ１は演算要素（Ａ〜Ｉ）２０１ａ〜２０１ｉが第１面のワークメモリを使用する場合に必要なデータを意味する。
【００３９】
図２３乃至図２５は、ウェーブレット変換装置１０１のタイミングチャートである。図２３乃至図２５において、例えば０＿０などのブロック名のみが記してある部分あるいはＲが記してある部分はフレームメモリ１００、カレントメモリ２０２又はキャッシュメモリ２０３〜２０６からの読み込み（ＲＥＡＤ）を表し、ブロック名の上にＷが記して部分は書き込み（ＷＲＩＴＥ）を表し、ＯＷが記してある部分は上書き（ＯＶＥＲＷＲＩＴＥ）を表している。以下、図１３乃至図２１とタイミングチャートを参照しながら順を追って動作を説明する。
【００４０】
《図１３》  最初のブロック行の左端の２ブロックの処理である。図２３の時刻ｔ０からｔ２の間に、フレームメモリ１００から０＿０ブロックのデータが読み込まれて演算要素（Ｅ，Ｄ）２０１ｅ，２０１ｄに送られ、かつカレントメモリ２０２に書き込まれる。演算要素（Ｅ）２０１ｅにおいては、その０−０ブロックのデータをワークメモリ（Ｌ１＿０）２１６に読み込む。演算要素（Ｄ）２０１ｄにおいては、ＳＳ計算部２３０で０−０ブロックのデータを用いてレベル３のＳＳデータを計算し、得られた２×２のＳＳデータをワークメモリ（４Ｌ＿１）２３４に格納する。なお、タイミングチャートにおいて、「Ａ０〜Ｉ０」は元データが演算要素の第０面のワークメモリに書き込まれるか、計算したＳＳデータが第０面のワークメモリに書き込まれるタイミングを表し、「Ａ１〜Ｉ１」は元データが演算要素の第１面のワークメモリに書き込まれるか、計算したＳＳデータが第１面のワークメモリに書き込まれるタイミングを表している。
【００４１】
次に、フレームメモリから０＿１ブロックのデータが読み込まれ、演算要素
（Ｆ）２０１ｆ及び演算要素（Ｅ）２０１ｅへ送られ、かつ、カレントメモリ２０２及びキャッシュメモリ（ＣＭ２）２０４に書き込まれる。演算要素（Ｅ）２０１ｅでは、そのデータをワークメモリ（Ｌ１＿１）２１７に読み込む。演算要素（Ｆ）２０１ｆでは、ＳＳ計算部２３０で０＿１データからレベル３のＳＳデータを計算し、それをワークメモリ（Ｌ４＿０）２３３に記憶する。
【００４２】
次に、フレームメモリ１００から１＿０ブロックのデータが読み込まれ、演算要素（Ｇ）２０１ｇ及び演算要素（Ｈ）２０１ｈに送られる。演算要素（Ｇ）２０１ｇではレベル３のＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｈ）２０１ｈではレベル３のデータを計算してワークメモリ（Ｌ４＿０）２３３に格納する。
【００４３】
次に、フレームメモリ１００から１＿１ブロックのデータが読み込まれ、演算要素（Ｉ）２０１ｉと演算要素（Ｈ）２０１ｈへ送られ、かつ、キャッシュメモリ（ＣＭ２）２０４に書き込まれる。演算要素（Ｉ）２０１ｉではレベル３のＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納し、また演算要素（Ｈ）２０１ｈではＳＳデータを計算してワークメモリ（Ｌ１＿１）２３４に格納する。
【００４４】
タイミングチャートには明示されていないが、以上の４ブロックのデータの読み込みと並行して、主制御部２０７の制御により、演算要素（Ａ〜Ｄ，Ｇ）２０１ａ〜２０１ｄ，２０１ｇの第０面のワークメモリ（Ｌ１＿０）２３３と、演算要素（Ａ，Ｂ）２０１ａ，２０１ｂの第１面のワークメモリ（Ｌ１＿１）２３４に、実在しない対応ブロックのミラーリング・データが書き込まれる。
【００４５】
このようにして、０＿０ブロック及び０＿１ブロックの処理のためのデータの用意が完了すると、まず演算要素（Ｅ）２０１ｅが第０面のワークメモリを使用して０＿０ブロックに対するウェーブレット変換処理を開始する。図２３における「Ｃａｌ＿０」がそのタイミングを表しているが処理の詳細は後述する。
【００４６】
０＿０ブロックのウェーブレット変換が終了すると、演算要素（Ｅ）２０１ｅの第０面のワークメモリ（Ｌ１＿０，Ｌ２＿０，Ｌ３＿０，Ｌ４＿０）２１６，２１８，２２０，２２２に得られたデータが直ちにフレームメモリ１００に書き戻される。それらワークメモリと、他の演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉ内の第０面のワークメモリ（Ｌ４＿０）２３３のデータは破棄される。
【００４７】
０＿０ブロックのウェーブレット変換と並行して、フレームメモリ１００から０＿２ブロックのデー夕が読み込まれ、演算要素（Ｆ）２０１ｆへ送られるとともに、カレントメモリ２０２及びキャッシュメモリ（ＣＭ２）２０４に書き込まれる。演算要素（Ｆ）２０１ｆでは、ＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納する。
【００４８】
続いて、フレームメモリ１００から１＿２ブロックのデータが読み込まれ、演算要素（Ｉ）２０１ｉへ送られ、同演算要素（Ｉ）２０１ｉでＳＳデータが計算されてそのワークメモリ（Ｌ４＿１）２３４に書き込まれ、同時に、１＿２ブロックのデータはキャッシュメモリ（ＣＭ２）２０４に書込まれる。図示されていなが、０＿２ブロックの読み込み時に、演算要素（Ｃ）２０１ｃに対応する実在しないブロックのミラーリング・データが、同演算要素に与えられてＳＳデータが計算され、その第１面のワークメモリ（Ｌ４＿１）２３４に格納される。
【００４９】
そして、０＿０ブロックに対するウェーブレット変換が終了した時点で、演算要素（Ｅ）２０１ｅは第１面のワークメモリ（Ｌ１＿１，Ｌ２＿１，Ｌ３＿１，Ｌ４＿１）２１７，２１９，２２１，２２３を使用し、０＿１ブロックに対するウェーブレット変換を開始する。図２３中の「Ｃａｌ＿１」がそのタイミングを示している。０＿１ブロックのウェーブレット変換が終了した時点で、演算要素（Ｅ）２０１ｅの第１面のワークメモリ（Ｌ１＿１，Ｌ２＿１，Ｌ３＿１，Ｌ４＿１）２１７，２１９，２２１，２２３に得られたデータが直ちにフレームメモリ１００に書き戻される。他の演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉ内の第１面のワークメモリ（Ｌ４＿１）２３４のデータは破棄される。
【００５０】
また、０＿１ブロックのウェーブレット変換と並行して、次の０＿２ブロックのウェーブレット変換のために、０＿１ブロックと１＿１ブロックのデータがキャッシュメモリ（ＣＭ２）２０４より読み出されて、演算要素（Ｄ，Ｇ）２０１ｄ，２０１ｇへそれぞれ転送され、また、０＿１ブロックのミラーリング・データが演算要素（Ａ）２０１ａへ転送される。演算要素（Ｄ）２０１ｄは０＿１ブロックのデータからレベル３のＳＳデータを計算して内部のワークメモリ（Ｌ４＿０）２３４に格納し、演算要素（Ｇ）２０１ｇは１＿１ブロックのデータからＳＳデータを計算して内部のワークメモリ（Ｌ４＿０）２３４に格納する。演算要素（Ａ）２０１ａはミラーリング・データのレベル３のＳＳデータを計算して、そのワークメモリＬ４＿０）２３４に格納する。
【００５１】
０＿１ブロックのウェーブレット変換が終了すると、０＿２ブロック及び０＿３ブロックのウェーブレット変換のために、０＿２ブロックと１＿２ブロックのデータがキャッシュメモリ（ＣＭ２）２０４より読み出されて演算要素（Ｅ，Ｄ）２０１ｅ，２０１ｄと演算要素（Ｈ，Ｇ）２０１ｈ，２０１ｇへそれぞれ転送される。また、０＿２ブロックのミラーリング・データが演算要素（Ａ，Ｂ）２０１ａ，２０１ｂへ転送される。演算要素（Ｅ）２０１ｅは０＿２ブロックのデータをワークメモリ（Ｌ１＿０）２１６に読み込み、演算要素（Ｄ）２０１ｄは０＿２ブロックのデータからＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｈ）２０１ｈは１＿２ブロックのデータからＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納し、演算要素（Ｇ）２０１ｇは１＿２ブロックのＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納する。演算要素（Ｂ）２０１ｂはミラーリング・データのＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納し、また、演算要素（Ａ）２０１ａはミラーリング・データのＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納する。ここまでが時刻ｔ３の処理であり、フレームメモリ１００上に０＿０ブロックと０＿１ブロックのレベル４までのウェーブレット変換データが得られた。
【００５２】
《図１４》  ２ブロック右の０＿２ブロック、０＿３ブロックの処理である。既に処理が終了し、フレームメモリ１００のデータが書き換えられているブロックは図１４中に網掛けして示されている（図１５乃至図２１においても同様である）。
【００５３】
時刻ｔ３から、フレームメモリ１００より０＿３ブロックのデータが読み出され、演算要素（Ｅ，Ｆ）２０１ｅ，２０１ｆへ転送されるとともに、キャッシュメモリ（ＣＭ２）２０４及びカレントメモリ２０２に書き込まれる。０＿３ブロックのミラーリング・データも演算要素（Ｂ，Ｃ）２０１ｂ，２０１ｃへ転送される。演算要素（Ｃ，Ｆ）２０１ｃ，２０１ｆは入力データから計算したＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納し、演算要素（Ｅ）２０１ｅは入力データをワークメモリ（Ｌ１＿１）２１７に格納し、演算要素（Ｂ）２０１ｂは入力データから計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。続いて、１＿３ブロックのデータがフレームメモリ１００より読み込まれ、演算要素（Ｈ，Ｉ）ｈ，ｉへ転送されるとともにキャッシュメモリ（ＣＭ２）２０４に書き込まれる。演算要素（Ｈ）２０１ｈは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｉ）２０１ｉは計算したＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納する。
【００５４】
この時点で、０＿２ブロックのウェーブレット変換が開始する。それと並行して、フレームメモリ１００から０＿４ブロックと１＿４ブロックのデータが読み込まれ、また、０＿４ブロックのミラーリング・データの演算要素（Ｃ）２０１ｃへの転送も行われる。
【００５５】
０＿２ブロックのウェーブレット変換が終了すると、０＿３ブロックのウェーブレット変換が開始し、また０＿２ブロックの変換データがフレームメモリ１００に書き戻される。０＿３ブロックの処理と並行して、次のブロックの処理のために、０＿１ブロックの処理の場合と同様なデータ転送が行われる。時刻ｔ４までに０＿３ブロックの変換データのフレームメモリ１００への書き戻しが終了する。時刻ｔ４からｔ５の間に、０＿４ブロックと０＿５ブロックが同様に処理される。
【００５６】
《図１５》  最初のブロック行の右端の２ブロックの処理である。動作は図１３及び図１４とほぼ同様であるので、詳細は省略する。ただし、図２４に示すタイミングチャートの時刻ｔ７からｔ８に示すように、０＿６３ブロックの処理のための演算要素（Ｆ，Ｉ）２０１ｆ，２０１ｉに対応したデータは実在せず、そのミラー処理が行われるので、フレームメモリ１００から読み込まれるデータは少ない。
【００５７】
《図１６》  次のブロック行の先頭の２ブロックの処理である。これは図２４のタイミングチャートでは時刻ｔ８からｔ９の期間に対応する。フレームメモリ１００から１＿０ブロックのデータが読み込まれ、演算要素（Ｅ）２０１ｅのワークメモリ（Ｌ１＿０）２１６及びキャッシュメモリ（ＣＭ３）２０５に書き込まれ、また、演算要素（Ｄ）２０１ｄへも送られてＳＳデータが計算され、そのワークメモリ（Ｌ４＿０）２３３に格納される。これと並行して、カレントメモリ２０２から０＿０ブロックのデータが読み出されて演算要素（Ａ，Ｂ）２０１ａ，２０１ｂへ送られてＳＳデータが計算され、演算要素（Ａ）２０１ａはＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｂ）２０１ｂはＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納する。また、０＿０ブロックのミラーリング・データも演算要素（Ａ）２０１ａへ送られてＳＳデータが計算され、そのワークメモリ（Ｌ４＿０）２３３に格納される。
【００５８】
次に、フレームメモリ１００より１＿１ブロックのデータが読み込まれて演算要素（Ｅ，Ｆ）２０１ｅ，２０１ｆへ送られるとともに、キャッシュメモリ（ＣＭ２，ＣＭ４）２０４，２０６へ書き込まれる。演算要素（Ｅ）２０１ｅはそのデータをワークメモリ（Ｌ１＿１）２１７に格納し、演算要素（Ｆ）２０１ｆはそのデータのＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納する。これと並行して、カレントメモリ２０２より０＿１ブロックのデータが読み出されてキャッシュメモリ（ＣＭ２）２０４に書き込まれ、かつ、演算要素（Ｂ，Ｃ）２０１ｂ，２０１ｃへ送られる。演算要素（Ｂ）２０１ｂはＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｃ）２０１ｃはＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納する。
【００５９】
次に、フレームメモリ１００より２＿０ブロックのデータが読み出されて演算要素（Ｇ，Ｈ）２０１ｇ，２０１ｈへ送られるとともにキャッシュメモリ（ＣＭ２）２０４に書き込まれ、また、カレントメモリ２０２より０＿２ブロックのデータが読み出されて演算要素（Ｃ）２０１ｃへ送られるとともにキャッシュメモリ（ＣＭ２）２０４に書き込まれる。演算要素（Ｃ，Ｇ）２０１ｃ，２０１ｇはそれぞれ入力データのＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｈ）２０１ｈは入力データのＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納する。演算要素（Ｇ）２０１ｇには２＿０ブロックのミラーリング・データも送られ、そのＳＳデータがワークメモリ（Ｌ４＿０）２３３に格納される。
【００６０】
次に、フレームメモリ１００より２＿１ブロックのデータが読み込まれ、キャッシュメモリ（ＣＭ２）２０４に書き込まれるとともに、演算要素（Ｈ，Ｉ）２０１ｈ，２０１ｉへ送られる。また、キャッシュメモリ（ＣＭ３）２０５より１＿０ブロックのデータが読み出されてカレントメモリ２０２に上書きされるとともに、そのミラーリング・データが演算要素（Ｄ）２０１ｄへ送られる。演算要素（Ｄ，Ｉ）２０１ｄ，２０１ｉはそれぞれの入力データのＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納し、演算要素（Ｈ）２０１ｈはその入力データのＳＳデータを計算しワークメモリ（Ｌ４＿１）２３４に格納する。
【００６１】
この時点から、演算要素（Ｅ）２０１ｅは、第０面のワークメモリ（Ｌ１＿０，Ｌ２＿０，Ｌ３＿０，Ｌ４＿０）２１６，２１８，２２０，２２２を使用して１＿０ブロックのウェーブレット変換を開始する。これと並行して、フレームメモリ１００より１＿２ブロックのデータが読み込まれてキャッシュメモリ（ＣＭ２）２０４及びカレントメモリ２０２に書き込まれるともに、演算要素（Ｆ）２０１ｆへ送られる。演算要素（Ｆ）２０１ｆは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。続いて、フレームメモリ１００より２＿２ブロックのデータが読み込まれてキャッシュメモリ（ＣＭ２）２０４に書き込まれるとともに演算要素（Ｉ）２０１ｉへ送られ、また、キャッシュメモリ（ＣＭ４）２０６より１＿１ブロックのデータが読み出されてカレントメモリ２０２に上書きされる。演算要素（Ｉ）２０１ｉは入力データのＳＳデータを計算してワークメモリ（Ｌ４＿１）２３４に格納する。
【００６２】
１＿０ブロックのウェーブレット変換が終了すると、その変換データがフレームメモリ１００へ書き戻されるとともに、演算要素（Ｅ）２０１ｅで第１面のワークメモリ（Ｌ１＿１，Ｌ２＿１，Ｌ３＿１，Ｌ４＿１）２１７，２１９，２２１，２２３を使用して１＿１ブロックのウェーブレット変換を開始する。この変換処理と並行して、次の１＿２ブロックのための準備が行われる。すなわち、キャッシュメモリ（ＣＭ２）２０４より０＿１ブロック，１＿１ブロック，２＿１ブロックが順次読み出され、演算要素（Ａ，Ｄ，Ｇ）２０１ａ，２０１ｄ，２０１ｇへそれぞれ送られる。これら演算要素は、それぞれの入力データのてＳＳデータを計算してワークメモリ（Ｌ４＿０）２３３に格納する。そして、１＿１ブロックの変換データがフレームメモリ１００に書き戻されることにより、１＿０ブロックと１＿１ブロックに対する処理が完了する。
【００６３】
《図１７》  図１６の位置から２ブロック分右側に移動した位置で処理である。これは図２５のタイミングテャートでは時刻ｔ９からｔ１０に相当する。この処理パターンが全体の処理の大部分（約８８％）を占める。
【００６４】
まず、キャッシュメモリ（ＣＭ２）２０４より０＿２ブロックのデータが読み出されて演算要素（Ｂ，Ａ）２０１ｂ，２０１ａへ送られ、演算要素（Ｂ）２０１ｂでは計算したＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納し、演算要素（Ａ）２０１ａでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。次に、キャッシュメモリ（ＣＭ２）２０４より１＿２ブロックのデータが読み出され、演算要素（Ｅ）２０１ｅのワークメモリ（Ｌ１＿０）２１６に書き込まれるとともに、演算要素（Ｄ）２０１ｄへ送られる。この演算要素（Ｄ）２０１ｄでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。次に、キャッシュメモリ（ＣＭ２）２０４より２＿２ブロックのデータが読み出されて、演算要素（Ｇ，Ｈ）２０１ｇ，２０１ｈへ送られ、演算要素（Ｈ）２０１ｈでは計算したＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納し、演算要素（Ｇ）２０１ｇでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。次に、カレントメモリ２０２より０＿３ブロックのデータが読み出され、キャッシュメモリ（ＣＭ２）２０４に書き込まれるとともに演算要素（Ｂ，Ｃ）２０１ｂ，２０１ｃに送られ、演算要素（Ｂ）２０１ｂでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納し、演算要素（Ｃ）２０１ｃでは計算したＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納する。
【００６５】
次に、フレームメモリ１００より１＿３ブロックのデータが読み込まれ、カレントメモリ２０２、キャッシュメモリ（ＣＭ２）２０４及び演算要素（Ｅ）２０１ｅのワークメモリ（Ｌ１＿１）２１７に書き込まれるとともに、演算要素（Ｆ）２０１ｆへ送られる。演算要素（Ｆ）２０１ｆでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。
【００６６】
次にフレームメモリ１００より２＿３ブロックが読み込まれて、キャッシュメモリ（ＣＭ２）２０４に書き込まれるとともに演算要素（Ｈ，Ｉ）２０１ｈ，２０１ｉへ送られる。演算要素（Ｉ）２０１ｉでは計算したＳＳデータをワークメモリ（Ｌ４＿０）２３３に格納し、演算要素（Ｈ）２０１ｈでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。
【００６７】
このような処理が終わった時点から、演算要素（Ｅ）２０１ｅは第０面のワークメモリ（Ｌ１＿０，Ｌ２＿０，Ｌ３＿０，Ｌ４＿０）２１６，２１８，２２０，２２２を使用し、１＿２ブロックのウェーブレット変換を開始する。このウェーブレット変換と並行して、フレームメモリ１００より１＿４ブロックのデータが読み出され、キャッシュメモリ（ＣＭ２，ＣＭ３）２０４，２０５に書き込まれるとともに、演算要素（Ｆ）２０１ｆへ送られてＳＳデータが計算され、そのワークメモリ（Ｌ４＿１）２３４に格納される。次にフレームメモリ１００より２＿４ブロックのデータが読み込まれ、演算要素（Ｉ）２０１ｉへ送られるとともにキャッシュメモリ（ＣＭ２）２０４に書き込まれる。演算要素（Ｉ）２０１ｉでは計算したＳＳデータをワークメモリ（Ｌ４＿１）２３４に格納する。
【００６８】
そして、１＿２ブロックに対するウェーブレット変換が終了し、その変換データがフレームメモリ１００に書き戻されるが、これと並行して、カレントメモリ２０２より０＿４ブロックのデータが読み出され、キャッシュメモリ（ＣＭ２）２０４に書き込まれるとともに演算要素（Ｃ）２０１ｃへ送られ、そのＳＳデータが計算されてワークメモリ（Ｌ４＿１）２３４に格納される。続いて、キャッシュメモリ（ＣＭ３）２０５より１＿４データが読み出されてカレントメモリ２０２に書き込まれる。
【００６９】
演算要素（Ｅ）２０１ｅが第１面のワークメモリ（Ｌ１＿１，Ｌ２＿１，Ｌ３＿１，Ｌ４＿１）２１７，２１９，２２１，２２３を使用して１＿３ブロックに対するウェーブレット変換を開始するが、この変換処理と並行して次の１＿４ブロックに対する処理の準備のための操作が行われる。すなわち、キャッシュメモリ（ＣＭ２）２０４より０＿３ブロック、１＿３ブロック、２＿３ブロックのデータが順次読み出され、演算要素（Ａ，Ｄ，Ｇ）２０１ａ，２０１ｄ，２０１ｇへそれぞれ送られてＳＳデータが計算される。計算されたＳＳデータは演算要素（Ａ，Ｄ，Ｇ）２０１ａ，２０１ｄ，２０１ｇのワークメモリ（Ｌ４＿０）２３３にそれぞれ格納される。そして、１＿３ブロックに対するウェーブレット変換処理が終了し、その変換データがフレームメモリ１００に書き戻される。
【００７０】
《図１８》  ２番目のブロック行の右端の２ブロックに対する処理である。この場合の動作は、ここまでの説明から明らかであろうから、説明を割愛する。
【００７１】
以上の図１６乃至図１８に対応した処理が、最終ブロック行の１つ前のブロック行まで繰り返される。
【００７２】
《図１９》  最終ブロック行の左端の２ブロックに対する処理である。この場合の動作は図１３の場合とほぼ同じであるので、その説明及びタイミングチャートは割愛する。
【００７３】
《図２０》  次の２ブロックに対する処理の様子を示している。この場合の動作は図１４の場合とほぼ同じであるので、その説明及びタイミングチャートは割愛する。
【００７４】
《図２１》  右端の２ブロックに対する処理であるが、この場合の動作は図１５の場合とほぼ同じであるので、その説明とタイミングチャートは割愛する。
【００７５】
図２６は、演算要素（Ｅ）２０１ｅにおけるウェーブレット変換処理のタイミングチャートである。時刻ｔ０からｔ１の期間に、フィルタ（１）２１３を利用して、ワークメモリ（Ｌ１＿０又はＬ１＿１）２１６又は２１７に書き込まれたデータに対するレべル１の水平処理が行われる。この水平処理と並行して、ＳＳ計算部２１０を利用してレベル１，２，３のＳＳデータが計算され、得られたレベル１，２，３のＳＳデータはワークメモリ（Ｌ２＿０又はＬ２＿１）２１８又は２１９，ワークメモリ（Ｌ３＿０又はＬ３＿１）２２０又は２２１，ワークメモリ（Ｌ４＿０又はＬ４＿１）２２２又は２２３にそれぞれ書き込まれる。
【００７６】
レベル１のＳＳデータは、水平方向に隣接する２個の元データの平均値を計算してＳデータを求め、次に垂直方向に隣接する２個のＳデータの平均値を計算することによって得られる。すなわち、２×２個の元データの平均値を計算することになる。レベル２のＳＳデータは、水平方向に隣接する２個のレベル１のＳＳデータの平均値を計算してＳデータを求め、次に、垂直方向に隣接する２個のＳデータの平均値を計算することによって得られる。すなわち、４×４個の元データの平均値を計算することになる。レベル３のＳＳデータは、水平方向に隣接する２個のレベル２のＳＳデータの平均値を計算してＳデータを求め、次に、垂直方向に隣接する２個のＳデータの平均値を計算することによって得られる。すなわち、８×８個の元データの平均値を計算することになる。１６×１６のサイズのブロックの場合、レベル３のＳＳデータが２×２個得られる。
【００７７】
レベル１の水平及び垂直処理のためのフィルタ（１）２１３とは別に、レベル２，３，４の水平及び垂直処理のためのフィルタ（２）２１４が用意されているため、レベル２，３，４の変換は、そのためのＳＳデータが用意できた時点から、任意の順番で、レベル１の変換と並行して行うことができる。
【００７８】
図２６のタイミングチャートでは、時刻ｔ１から、レベル１の垂直処理が開始し、同時にレベル２の水平処理が開始する。レベル２の水平処理は、フィルタ（２）２１４を使用して、ワークメモリ（Ｌ２＿０又はＬ２＿１）２１８又は２１９にあるレベル１のＳＳデータに対して実行される。得られたＳデータ及びＤデータはワークメモリ（Ｌ２＿０又はＬ２＿１）２１８又は２１９に書き戻される。次に、このＳデータ及びＤデータに対し、フィルタ（２）２１４を用いて垂直処理が実行され、レベル２の変換データがワークメモリ（Ｌ２＿０又はＬ２＿１）２１８又は２１９に得られる。
【００７９】
時刻ｔ２から、フィルタ（２）２１４を利用して、ワークメモリ（Ｌ３＿０又はＬ３＿１）２２０又は２２１にあるレベル２のＳＳデータに対する水平処理、垂直処理が順に実行され、レベル３の変換データがワークメモリ（Ｌ３＿０又はＬ３＿１）２２０又は２２１に得られる。時刻ｔ３から、演算要素（Ｅ）２０１ｅの内部のワークメモリ（Ｌ４＿０又はＬ４＿１）２２２又は２２３にあるレベル３のＳＳデータと、他の演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）２０１ａ〜２０１ｄ，２０１ｆ〜２０１ｉの内部の（Ｌ４＿０又はＬ４＿１）２３３又は２３４に得られているＳＳデータ（全体で６×６個のＳＳデータ）に対し、フィルタ（２）２１４を用いて水平処理と垂直処理が順次実行され、レベル４の変換データが演算要素（Ｅ）２０１ｅのワークメモリ（Ｌ４＿０又はＬ４＿１）２２２又は２２３に得られる。
【００８０】
レベル１はデータ数が多いため、レベル２，３，４の処理に要する時間を合計しても、レベル１の水平処理もしくは垂直処理に要する時間より少ないため、レベル１の垂直処理が終了する時刻ｔ５より前の時刻ｔ４でレベル２，３，４の変換は完了する。
【００８１】
図２７は、フレームメモリ１００を処理の内容が同じ部分毎に分割し、それぞれの部分に１から１５の識別番号を付けたものである。図１３乃至２５を用いて説明したように、フレームメモリ１００に対する読み出し／書き込みに関しては、１と１３の部分、２と１４の部分、３と１５の部分でほぼ同様の処理が行われる。同様に、４、７、１０の部分、５、８、１１の部分、６、９、１２の部分もほぼ同様の処理が行われる。一方、ウェーブレット変換はこれとは異なり、処理されるブロック数が各部分で異なる。１、３、１３、１５の部分では、演算要素の第０面（又は第１面）のワークメモリを利用して処理されるブロック数が２×２ブロックで、第１面（又は第０面）を利用して処理されるブロック数は３×２ブロックとなる。２、１４の部分では、いずれも処理されるブロック数は３×２ブロックである。４、７、１０、６、９、１２の部分では、第０面（又は第１面）のワークメモリを利用して処理されるブロック数が２×３ブロックで、第１面（又は第０面）のワークメモリを利用して処理されるブロック数が３×３ブロックとなる。５、８、１１の部分では処理されるブロック数はいずれも３×３ブロックとなる。
【００８２】
そこで、簡単のため、またタイミングチャートとの比較を容易にするため、１６×１６のサイズのブロックを時間単位として処理時間を計算する。ウェーブレット変換は、図１３乃至図２１に示す３×３の実線格子又は点線格子の中央のブロックのデータを対象にして行われるため、対象外のブロックに対しては各メモリはフリーとなり、ウェーブレット変換と並行してデータをフレームメモリに書込む、あるいは予め読み出しておくことができる。以上を考慮して、図２７における１から１５の各部分での処理時間を求めると、１の部分は１０ブロック、２の部分は１２ブロック、３の部分は８ブロック、４の部分は１０ブロック、５の部分は２０ブロック、６の部分は８ブロック、７の部分は１０ブロック、８の部分は２０ブロック、９の部分は８ブロック、１０の部分は１０ブロック、１１の部分は２０ブロック、１２の部分は８ブロック、１３の部分は１０ブロック、１４の部分は１２ブロック、１５の部分は８ブロックとなる。処理時間の合計は（Ｘ＝Ｙ＝１０２４としたとき）、最上段と最下段のブロックでは１０＋１２×３０＋８＝３７８ブロック、それ以外では（１０＋２０×３０＋８）×６２＝３８３１６ブロックとなり、合計で３９０７２ブロックとなる。
【００８３】
これをクロック数に換算すると、１ブロックのサイズが１６×１６であるから、９７６８ｋクロック（１ｋ＝１０２４）となる。このクロック数は、ウェーブレット変換とフレームメモリに対する読み出し／書き込みのスピードを同一とした場合であり、通常は内部動作は容易に高速化が可能であるから、この数値はワーストケースである。例えば、ウェーブレット変換に最も長い時間を要する５、８、１１の部分（８の部分が全体の８８％を占める）のウェーブレット変換に要する時間が半分になったとすると、処理時間は（２０−９）＋９／２＝１５．５ブロックとなり、全体での処理時間は３０７０２ブロックとなる。これはクロック数に換算すると７６７５．５ｋクロックとなり、ワーストケースに比較して約７９％の時間で全ての処理を終了することができる。
【００８４】
従来技術で問題となっていたライン方向のメモリアクセス時に生じるレイテンシは、本発明ではブロック単位でデータを転送をすることで回避することができる。具体的には、読み出し／書き込みは全て画素方向のデータ転送となり、画素方向のデータ転送時にメモリのセンスアンプをプリチャージする時間を充分確保することができる。すなわち、バンク切り替え等の手法を用いてレイテンシの問題を解決できるようになる。
【００８５】
さて、演算要素（Ｅ）２０１ｅの内部の各ワークメモリには、各レベルのＳＳ，ＤＳ，ＳＤ，ＤＤのデータが図２８のようなマッピングで記憶される。ｘはレベルを示す数字を意味する。ただし、レベル１、２，３のＳＳデータは、その上位レベルのデータで置き換えられるため意味を持たない。このような各レベルのデータは、従来と同様に、図４５に示すようなマッピングでフレームメモリ１００に書き戻すことも可能である。しかし、符号化復号化器１０２においては、重要度の高いレベル及び周波数帯信号からビットプレーン単位で符号化又は復号化を行うため、その処理順序を考慮して、周波数帯信号の配列を予めソートした形でフレームメモリ１００に書き戻すのが有利である。以下、これについて説明する。
【００８６】
図２９は、ウェーブレット変換により得られた各レべルの各周波数帯信号が重要度により並べ替えらる「アライメント（ａｌｉｇｎｍｅｎｔ）」と呼ばれる概念を表している。図２９において、１つの長方形が、あるレべルのある周波数帯信号を示し、その長さがビット深さを表している。ビット深さは、使用するフィルタの構成により異なってくるが、ここではＳＤ係数及びＤＳ係数が同じビット深さを有し、ＤＤ係数はＳＤ係数及ぴＤＳ係数より１ビットだけビット深さが深いものとして描かれている。符号化復号化器１０２においては、例えば画像を扱うような場合は、圧縮率を上げるためにデータの切り捨てを行う場合がある。アライメントは、その切り捨て方を決めるための１つの手段として用いられ、重要度の低いビットのデータが切り捨てられる。
【００８７】
図３０はビットプレーンという概念を説明する図である。データが例えば画像データであれば、ある画素（ｐｉｘｅｌ）は（ｘ、ｙ）で表されるアドレス空間と、ビット深さを持っている。図中、斜線で示した部分（例えば、ＭＳＢの部分）をビットプレーンと呼ぶ。符号化復号化器１０２では、処理はビットプレーン単位で、何画素かの塊で行われる。画像データは、ある画素に着目した場合、その周辺の画素との相関が高いことを利用して圧縮率を高めるためである。
【００８８】
符号化又は復号化は、ビットプレーン単位で重要度の高い方の、左から右に向かって実行されていく（ただし、ＳＳ係数は除外）。図２９のようなアライメントの場合、レベル４のＳＤ係数の最上位ビット（ＭＳＢ）、ＤＳ係数の最上位ビット、ＤＤ係数の最上位ビット、ＳＤ係数の１つ下位の（ＭＳＢ−１）ビット、．．．という順になる。したがって、図４５に示すようなマッピングで周波数帯信号がフレームメモリ１００に書き戻された場合には、符号化復号化器１０２でフレームメモリ１００に対し飛び飛びのアドレッシングが必要になることは明白であり、フレームメモリ１００がＳＤＲＡＭのようなバースト転送を行うメモリであるとレイテンシの関係から処理速度が上がらない。
【００８９】
これを回避するために、本実施例においては、レベル毎及び周波数帯毎に連続してアクセスすることが可能な配列となるように、周波数帯信号をその重要度の高い順に予めソートしてからフレームメモリ１００に書き戻す。すなわち、図２９のようなアライメントの場合、１６×１６の領域のデータを、図４６に示すように、フレームメモリ１００の左上から４ＳＳ，４ＳＤ，４ＤＳ，４ＤＤ，次に、３ＤＳ×２，３ＳＤ×２，３ＤＤ×２，．．．というような重要度の高い順で書き戻し、最後にレベル１のデータ（１ＤＳ，１ＳＤ，１ＤＤ）を書き戻す（レベル１のデータが領域の４分の３を占める）。このような周波数帯信号のソーティングは、例えば、制御部２１１において各ワークメモリから周波数帯信号を読み出す順序を制御することによって行われる。
【００９０】
このようにソートされた状態で書き戻されたならば、符号化復号化部器１０２において、切り捨てを行う場合にも行わない場合にも、フレームメモリ１００に対するアドレッシングが容易になり、かつ、レイテンシが発生しにくいので、符号化復号化器１０２からのフレームメモリ１００に対する読み出し／書き込みを高速化することができる。
【００９１】
本発明の第２の実施例によれば、図２に示した全体構成のウェーブレット変換装置１０１において、演算要素（Ｅ）２０１ｅの構成が図３１に示すように一部変更される。すなわち、各ワークメモリ２１６〜２２３が、ＳＳ，ＳＤ，ＤＳ，ＤＤの各データに割り当てられる、独立した４つのメモリ（ＳＳメモリ，ＳＤメモリ，ＤＳメモリ，ＤＤメモリと呼ぶことがある）に分割された構成とされる。制御部２１１はＳＳ計算部２１０を具備しない。また、フィルタ（１）２１３とフィルタ（２）２１４は、特定のレベルの処理専用に割り当てられるものではなく、各レベルの水平処理時と垂直処理時に制御部２１１によって入出力を切り替えて使用される。
【００９２】
本実施例のウェーブレット変換装置１０１の全体的動作は前記第１実施例と同様であり、演算要素（Ｅ）２０１ｅに関する動作のみが前記第１実施例と一部相違する。以下、演算要素（Ｅ）２０１ｅの動作を、図３２のメモリマップ、図３３及び図３４の接続図、図３５のタイミングチャートを参照して説明する。
【００９３】
フレームメモリ１００のデータが演算要素（Ｅ）２０１ｅのワークメモリ（Ｌ１＿０又はＬ１＿１）２１６又は２１７に転送される際に、制御部２１１により、データは図３２のメモリマップに示すような規則に従って、同ワークメモリを構成するＳＳメモリ，ＳＤメモリ，ＤＳメモリ，ＤＤメモリに振り分けて書き込まれる。この振り分けの規則は次の通りである。ＳＳメモリの０ライン目の０画素目にはフレームメモリ１００のブロックの０ライン目の０画素目のデータが格納され、ＳＤメモリの０ライン目の０画素目にはブロックの０ライン目の１画素目のデータが格納される。また、ＤＳメモリの０ライン目の０画素目にはブロックの１ライン目の０画素目のデータが格納され、ＤＤメモリの０ライン目の０画素目にはブロックの１ライン目の１画素目が格納される。すなわち、偶数ライン目（０ライン目も偶数ライン目と数える）の偶数画素目（０画素目も偶数画素目と数える）がＳＳメモリに格納され、偶数ライン目の奇数画素目がＳＤメモリに格納され、奇数ライン目の偶数画素目がＤＳメモリに格納され、奇数ライン目の奇数画素目がＤＤメモリに格納されるのである。
【００９４】
図３５のタイミングチャートの時刻ｔ０までに、上に述べたような形でワークメモリ（Ｌ１＿０又はＬ１＿０）２１６又は２１７にデータが格納されると、レベル１の水平処理が開始する。この時には、フィルタ（１）２１３及びフィルタ（２）２１４の入出力は、図３３に示すように、ワークメモリ（Ｌ１＿０又はＬ１＿０）２１６又は２１７のＳＳメモリ，ＳＤメモリ，ＤＳメモリ，ＤＤメモリと接続される。これら４つのメモリは独立しているため、同時刻に読み出し／書き込みを行うことができる。すなわち、偶数ライン目をフィルタ（１）２１３で、奇数ライン目をフィルタ（２）２１４で、並列に処理し、その結果を同時に書き込むのである。この水平処理が終わると、次にレベル１の垂直処理が開始する。この時には、フィルタ（１）２１３及びフィルタ（２）２１４の入出力は、図３４のように接続が変更される。すなわち、偶数画素目をフィルタ（１）２１３で、奇数画素目をフィルタ（２）２１４で、並列に処理し、結果を同時に書き込むのである。垂直処理で得られるレベル１のＳＳデータは、ＳＳメモリに書き込まれるとともに、制御部２１１により図３２に関連して説明した規則と同様の規則に従ってワークメモリ（Ｌ２＿０又はＬ２＿１）２１８又は２１９を構成する４つのメモリに振り分けて書き込まれる。
【００９５】
そして、時刻ｔ１からレベル２の処理が開始する。まず、フィルタ（１，２）２１３，２１４の入出力が、図３３に示すように、ワークメモリ（Ｌ２＿０又はＬ２＿１）２１８又は２１９を構成する４つのメモリに接続され、水平処理が実行される。水平処理が終わると、フィルタ（１，２）２１３，２１４の入出力が、図３４に示すような接続に切り替えられ、垂直処理が実行される。得られたレベル２のＳＳデータは、図３２に関連して説明したと同様の規則に従って、ワークメモリ（Ｌ３＿０又はＬ３＿１）２２０又は２２１を構成する４つのメモリに振り分けて書き込まれる。ここまでが時刻ｔ２である。以下、同様にしてレベル４まで処理が実行され、時刻ｔ４で処理が完了する。ただし、レベル４の処理の際には、他の演算要素で得られたレベル３のＳＳデータも利用されることは前記第１実施例の場合と同様である。
【００９６】
このように、本実施例においては、レベル１，２，３，４の処理をシーケンシャルに実行するが、各レベルの処理に要する時間は、前記第１実施例に比べて４分の１で済む。これは、各ワークメモリを構成する４つのメモリを同時にアクセスすることが可能であるためである。
【００９７】
本実施例における処理時間は次の通りである。図２７における１から１５の各部分での処理時間をブロツク単位で求めると、１の部分は４．６５６２５ブロック、２の部分は３．９８４３７５ブロック、３の部分は２．６５６２５ブロック、４の部分は４．６５６２５ブロック、５の部分は７．９７６５６２５ブロック、６の部分は２．６５６２５ブロック、７の部分は４．６５６２５ブロック、８の部分は７．９７６５６２５ブロック、９の部分は２．６５６２５ブロック、１０の部分は４．６５６２５ブロック、１１の部分は７．９７６５６２５ブロック、１２の部分は２．６５６２５ブロック、１３の部分は４．６５６２５ブロック、１４の部分は７．９７６５６２５ブロック、１５の部分は２．６５６２５ブロックとなる。図３５に示したように、ウェ‐ブレット変換の時間はブロックを単位とすると、レべル１では０．２５×２ブロック、レべル２では０．０６２５×２ブロック、レべル３では０．０１５６２５×２ブロック、そしてレべル４では０．０Ｏ３９０６２５×２ブロック、というように小数点以下の数が発生するが、ここでは省略せず計算を行っている。処理時間の合計は（Ｘ＝Ｙ＝１０２４としたとき）、最上段及び最下段のブロックでは４．６５６２５＋３．９８４３７５×３０＋２．６５６２５＝１２６．８４３７５ブロック、それ以外では（４．６５６２５＋７．９７６５６２５×３０＋２．６５６２５）×６０＝１４７９６．５６２５ブロックとなり、合計で１５０５０．２５ブロックとなる。クロック数に換算すると、１ブロックが１６×１６であるから、３７６２．５６２５ｋクロック（１ｋ＝１０２４）となる。このクロック数は、ウェーレット変換とフレームメモリに対する読み出し／書き込みのスピードを同一とした場合である。この処理速度は、前記第１実施例の７６７５．５ｋクロックに比べても４９％の処理時間で済み、従来技術と比べるとレイテンシが２の場合では３５％の処理時間で済むから、非常に高速な処理が可能であることが理解されよう。
【００９８】
さて、前述のように、符号化復号化器１０２ではビット単位で処理が行われるため、ウェーブレット変換に比べて数倍から１０数倍の処理時間がかかることは明らかである。データの読み出し／書き込みをフレームメモリ１００に対して行えば、その処理時間はさらに長くなる。また、前述のように、符号化復号化は重要度が高い周波数帯信号から順に行われるが、一般に高いレベルの周波数帯信号ほど重要度が高い。しかるに、従来はウェーブレット変換がレベル１から順次高いレベルへと行われたため、高レベルの周波数帯信号を得るにはウェーブレット変換の終了を待たなければならなかった。これに対し、本発明では、ウェーブレット変換が小さなブロックの単位で行われ、しかもブロックの全レベルの周波数帯信号がほぼ同時に得られる。
【００９９】
このような本発明のウェーブレット変換装置の特質に鑑み、本発明の第３の実施例によれば、ウェーブレット変換と符号化復号化処理との処理時間の差を吸収するために、図３６に簡略化して示すように、フレームメモリ１００のキャッシュメモリとして動作するバッファメモリ２５０が、前記第１実施例又は第２実施例と同様な構成のウェーブレット変換装置１０１内の主制御部２０７に付加される。このバッファメモリ２５０は符号化復号化器１０２によってアクセス可能とされる。本実施例のウェーブレット変換装置１０１では、ブロック単位のウェーブレット変換を実行して一部の周波数帯信号データ（例えば高レベルの周波数帯信号データ）をバッファメモリ２５０に書き込む。このウェーブレット変換と並行して、符号化復号化器１０２ではバッファメモリ２５０から取得できるデータはバッファメモリ２５０から読み込み、それ以外のデータはフレームメモリ１００から読み込みながら、符号化復号化処理を実行する。
【０１００】
例えば、フレームメモリ１００のサイズをＸ＝Ｙ＝１０２４とし、バッファメモリ２５０にレべル３とレべル４のデータを全て書込むとものとする。この場合、バッファメモリ２５０の必要サイズは、［１２８×１２８（レべル３分）＋６４×６４（レべル４分）］×３（ＳＳ係数は符号化復号化されないため、除かれる）＝６０ｋＢ（１ｋ＝１０２４）にすぎない。
【０１０１】
この場合の処理時間について述べる。従来技術ではウェーブレット変換に１０８８０ｋクロック（レイテンシ２の場合）かかり、符号化復号化器で処理するデータ数が１０２４ｋ−１６ｋ（ＳＳデータ分）＝１００８ｋであるので、１データの符号化復号化に要する時間を１０クロックとすると、符号化復号化器での処理時間は１００８０ｋクロックとなる。したがって、ウェーブレット変換と符号化復号化処理のトータル時間は２０９６０ｋクロックとなる。
【０１０２】
これに対し、本実施例においては、ウェーブレット変換装置１０１が前記第２実施例の構成であるとすると、ウェーブレット変換の処理時間は３７６２．５６２５ｋクロックとなる。前述のように、レべル３及びレべル４のサイズに対応したバッファメモリ２５０を用意した場合、そのデータ数は２４０ｋＢであるので、その符号化復号化処理にかかる時間は２４００ｋクロックとなるが、符号化復号化処理はウェーブレット変換と並列に行われるから、この２４００ｋクロックはウェーブレット変換のための時間に包含される。レべル１及びレべル２で処理すべきデータ数は９６０ｋＢであるので、その符号化復号化処理にかかる時間は９６００ｋクロックとなる。したがって、トータルの処理時間は、この９６００ｋクロックにウェーブレット変換の処理時間３７６２．５６２５ｋクロックを加えた１３３６２．５６２５ｋクロックとなり、従来技術に比べて約６４％まで短縮される。このように、処理全体を大幅に高速化できる。
【０１０３】
【発明の効果】
請求項１乃至５の各項記載の発明によるウェーブレット変換装置は、複数の演算要素を利用してブロック単位で所望レベルまでのウェーブレット変換処理を高速に行うことができるとともに、フレームメモリからのデータの読み込みもフレームメモリへの周波数帯信号の書き戻しもブロック単位で行うためレイテンシの影響を回避することができるため、フレームメモリに対するメモリアクセスも含めた処理全体を従来より大幅に高速化することができ、またブロック単位で全ウェーブレット・レベルの周波数帯信号がほぼ同時に得られる。請求項２記載の発明によるウェーブレット変換装置は、２つの隣接ブロックを連続的に処理しながらフレームメモリに対する読み書きを並行して行うことにより、処理速度をさらに高速化することができる。請求項３又は４記載の発明によるウェーブレット変換装置は、第１演算要素におけるウェーブレット変換処理を高速化することができるため、処理速度の一層の高速化が可能である。請求項６又は７記載の発明による符号化復号化装置は、ウェーブレット変換処理が高速化されるとともに、ブロック単位で全ウェーブレット・レベルの周波数帯信号が同時にフレームメモリ上に得られるため、符号化処理をウェーブレット変換処理の開始後すぐに開始しウェーブレット変換処理と並行して実行可能であり、したがって従来よりもはるかに高速な動作が可能である。特に、ウェーブレット変換装置によって周波数帯信号が重要度順にソートされた状態でフレームメモリに書き戻される場合には、符号化復号化器のフレームメモリへのアクセスを高速化できるため、非常に高速な処理が可能である。また、請求項７記載の発明による符号化復号化装置は、バッファメモリより取得可能なデータについてはフレームメモリをアクセスする必要がなくなるため、さらに高速な動作が可能である、等々の効果を得られる。
【図面の簡単な説明】
【図１】本発明による符号化復号化装置の全体構成の一例を示す図である。
【図２】本発明の第１の実施例によるウェーブレット変換装置の内部構成を示すブロック図である。
【図３】本発明の第１の実施例による演算要素（Ｅ）の内部構成を示すブロック図である。
【図４】ワークメモリ（Ｌ１＿０，Ｌ１＿１）、キャッシュメモリ（ＣＭ１，ＣＭ３，ＣＭ４）のサイズの説明図である。
【図５】キャッシュメモリ（ＣＭ２）のサイズの説明図である。
【図６】ワークメモリ（Ｌ２＿０，Ｌ２＿１）のサイズの説明図である。
【図７】ワークメモリ（Ｌ３＿０，Ｌ３＿１）のサイズの説明図である。
【図８】ワークメモリ（Ｌ４＿０，Ｌ４＿１）のサイズの説明図である。
【図９】フレームメモリのサイズの説明図である。
【図１０】カレントメモリのサイズの説明図である。
【図１１】本発明の第１の実施例による演算要素（Ａ〜Ｄ，Ｆ〜Ｉ）の内部構成を示すブロック図である。
【図１２】１６×１６サイズのブロック１個あたりのレベル３までの周波数帯信号のマッピングの一例を示す図である。
【図１３】最初のブロック行の左端の２ブロックの処理を説明するための図である。
【図１４】最初のブロック行の次の２ブロックの処理を説明するための図である。
【図１５】最初のブロック行の右端の２ブロックの処理を説明するための図である。
【図１６】２番目のブロック行の左端の２ブロックの処理を説明するための図である。
【図１７】２番目のブロック行の次の２ブロックの処理を説明するための図である。
【図１８】２番目のブロック行の右端の２ブロックの処理を説明するための図である。
【図１９】最後のブロック行の左端の２ブロックの処理を説明するための図である。
【図２０】最後のブロック行の次の２ブロックの処理を説明するための図である。
【図２１】最後のブロック行の右端の２ブロックの処理を説明するための図である。
【図２２】キャッシュメモリ（ＣＭ１〜ＣＭ４）によるデータのキャッシュを説明するための図である。
【図２３】ウェーブレット変換装置のタイミングチャートである。
【図２４】ウェーブレット変換装置のタイミングチャートである。
【図２５】ウェーブレット変換装置のタイミングチャートである。
【図２６】本発明の第１の実施例における演算要素（Ｅ）のタイミングチャートである。
【図２７】処理時間を説明するためにフレームメモリを複数の部分に分割した図である。
【図２８】演算要素（Ｅ）の各ワークメモリに得られる周波数帯信号のマッピングを示す図である。
【図２９】周波数帯信号のアライメントの説明図である。
【図３０】ビットプレーンの説明図である。
【図３１】本発明の第２の実施例における演算要素（Ｅ）の内部構成を示すブロック図である。
【図３２】本発明の第２の実施例における演算要素（Ｅ）内のワークメモリを構成するＳＳ，ＤＳ，ＳＤ，ＤＤメモリへのデータの振り分け方を示す図である。
【図３３】水平処理時のフィルタの入出力の接続方法を示す図である。
【図３４】垂直処理時のフィルタの入出力の接続方法を示す図である。
【図３５】本発明の第２の実施例における演算要素（Ｅ）のタイミングチャートである。
【図３６】本発明の第３の実施例による符号化復号化装置及びウェーブレット変換装置の構成を示す図である。
【図３７】従来のウェーブレット変換装置の一般的構成を示す図である。
【図３８】ウェーブレット変換の水平処理及び垂直処理のためのフィルタ演算の説明図である。
【図３９】ウェーブレット変換前のイメージデータのメモリマップの一例を示す図である。
【図４０】１Ｓ係数及び１Ｄ係数のためのメモリマップの一例を示す図である。
【図４１】１ＳＳ係数、１ＳＤ係数、１ＤＳ係数及び１ＤＤ係数のためのメモリマップの一例を示す図である。
【図４２】２Ｓ係数及び２Ｄ係数のためのメモリマップの一例を示す図である。
【図４３】２ＳＳ係数、２ＳＤ係数、２ＤＳ係数及び２ＤＤ係数のためのメモリマップの一例を示す図である。
【図４４】従来の一般的なウェーブレット変換装置のタイミングチャートである。
【図４５】レベル４までの周波数帯信号の一般的なメモリマップを示す図である。
【図４６】レベル４までの周波数帯信号を重要度の高い順に書き戻した場合のメモリマップの一例を示す図である。
【符号の説明】
１００  フレームメモリ
１０１  ウェーブレット変換装置
１０２  符号化復号化器
２００  演算部
２０１ａ〜２０１ｉ  演算要素（Ａ〜Ｉ）
２０２  カレントメモリ
２０３  キャッシュメモリ（ＣＭ１）
２０４  キャッシュメモリ（ＣＭ２）
２０５  キャッシュメモリ（ＣＭ３）
２０６  キャッシュメモリ（ＣＭ４）
２０７  主制御部
２１０  ＳＳ計算部
２１１  制御部
２１３  フィルタ（１）
２１４  フィルタ（２）
２１６  ワークメモリ（Ｌ１＿０）
２１７  ワークメモリ（Ｌ１＿１）
２１８  ワークメモリ（Ｌ２＿０）
２１９  ワークメモリ（Ｌ２＿１）
２２０  ワークメモリ（Ｌ３＿０）
２２１  ワークメモリ（Ｌ３＿１）
２２２  ワークメモリ（Ｌ４＿０）
２２３  ワークメモリ（Ｌ４＿１）
２３０  ＳＳ計算部
２３１  制御部
２３３  ワークメモリ（Ｌ４＿０）
２３４  ワークメモリ（Ｌ４＿１）
２５０  バッファメモリ
【図１】
0004117866.tif 000002
【図２】
0004117866.tif 000003
【図３】
0004117866.tif 000004
【図４】
0004117866.tif 000005
【図５】
0004117866.tif 000006
【図６】
0004117866.tif 000007
【図７】
0004117866.tif 000008
【図８】
0004117866.tif 000009
【図９】
0004117866.tif 000010
【図１０】
0004117866.tif 000011
【図１１】
0004117866.tif 000012
【図１２】
0004117866.tif 000013
【図１３】
0004117866.tif 000014
【図１４】
0004117866.tif 000015
【図１５】
0004117866.tif 000016
【図１６】
0004117866.tif 000017
【図１７】
0004117866.tif 000018
【図１８】
0004117866.tif 000019
【図１９】
0004117866.tif 000020
【図２０】
0004117866.tif 000021
【図２１】
0004117866.tif 000022
【図２２】
0004117866.tif 000023
【図２３】
0004117866.tif 000024
【図２４】
0004117866.tif 000025
【図２５】
0004117866.tif 000026
【図２６】
0004117866.tif 000027
【図２７】
0004117866.tif 000028
【図２８】
0004117866.tif 000029
【図２９】
0004117866.tif 000030
【図３０】
0004117866.tif 000031
【図３１】
0004117866.tif 000032
【図３２】
0004117866.tif 000033
【図３３】
0004117866.tif 000034
【図３４】
0004117866.tif 000035
【図３５】
0004117866.tif 000036
【図３６】
0004117866.tif 000037
【図３７】
0004117866.tif 000038
【図３８】
0004117866.tif 000039
【図３９】
0004117866.tif 000040
【図４０】
0004117866.tif 000041
【図４１】
0004117866.tif 000042
【図４２】
0004117866.tif 000043
【図４３】
0004117866.tif 000044
【図４４】
0004117866.tif 000045
【図４５】
0004117866.tif 000046
【図４６】
0004117866.tif 000047