(57)【要約】【課題】リフティング構成に基づくウェーブレット変換を短時間で効率良く実行すること。【解決手段】対象領域Ａ１内の２点の入力データＸ（２ｎ＋４），Ｘ（２ｎ＋５）を用いて、奇数番目の入力データＸ（２ｎ＋５）を始点とする系列上の第１段階の一時データ（Ｄ１ｎ＋２）が算出される。また、対象領域Ａ２内の最終段階（第２段階）の計算済みの中間データＳ２ｎを規格化して出力データＹ（２ｎ）が算出される。一時データ（Ｄ１ｎ＋２）を算出する処理と出力データＹ（２ｎ）を算出する規格化処理とは並列に同時実行されるため、２点のデータ（Ｄ１ｎ＋２），Ｙ（２ｎ）が、画素クロック信号ＰＣＬＫの１周期（１クロック周期）内に同時に算出される。【選択図】        図３
2004165907.tif 000002
【特許請求の範囲】
【請求項１】
リフティング構成に基づいて、入力データ列を高域成分と低域成分とに帯域分割するウェーブレット変換装置であって、
制御部と、
メモリ管理部と、
前記メモリ管理部の制御によりデータを一時記憶するメモリと、
偶数番目の入力データおよび奇数番目の入力データの一方からなる第１データ列とその他方からなる第２データ列とで構成される前記入力データ列を取り込んで該入力データ列の前記高域成分および前記低域成分を算出するフィルタリング部と、
を備えて構成されており、
前記フィルタリング部は、
前記入力データ列を選択的に取り込むデータ・セレクタと、
前記データ・セレクタで取り込まれた入力データの各々を単数または複数の段階に亘る一系列の中間データへ１点当たり１クロック周期内に変換する単数または複数の変換処理を実行する中間データ算出手段と、
前記各入力データを始点とする系列上の最終段階の前記中間データに所定の規格化係数を乗算することで、前記高域成分および前記低域成分の出力データを１点当たり１クロック周期内に算出する単数または複数の規格化処理を実行する規格化手段と、
を備えており、
前記制御部は、
前記中間データ算出手段および前記規格化手段に、前記単数または複数の変換処理および前記単数または複数の規格化処理を、全ての点の前記出力データが算出されるまで繰り返し実行させ、且つ、繰り返し実行される前記単数または複数の変換処理および前記単数または複数の規格化処理のうち少なくとも２個の処理を１クロック周期内に並列に実行させるように制御する、
ことを特徴とするウェーブレット変換装置。
【請求項２】
請求項１記載のウェーブレット変換装置であって、前記中間データ算出手段および前記規格化手段は、前記変換処理および前記規格化処理を並列に実行する、ウェーブレット変換装置。
【請求項３】
請求項１または請求項２記載のウェーブレット変換装置であって、
前記中間データ算出手段は、
前記データ・セレクタで選択的に取り込まれた２点の入力データの一方に所定のリフティング係数を乗算する係数乗算器と、該係数乗算器から出力されたデータと前記２点の入力データの他方とを加算する加算器とからなる２点演算部と、前記２点演算部から出力されたデータを取り込んで前記制御部から指定された出力先に出力する出力先選択部と、
を備えると共に、
前記規格化手段は、
前記出力先選択部から出力された前記最終段階の前記中間データを遅延させる遅延器と、
該遅延器から出力された前記中間データに前記規格化係数を乗算することで前記高域成分および前記低域成分の出力データを算出する係数乗算器と、
を備えており、
前記メモリ管理部は、前記出力先選択部から出力された前記データを前記メモリに転送し記憶させるように制御する、
ウェーブレット変換装置。
【請求項４】
請求項３記載のウェーブレット変換装置であって、
前記制御部は、前記変換処理として、
前記第２データ列に属する入力データと、該入力データに対して１点前の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを起点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する第１の変換処理と、
前記第１の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第２の変換処理と、
前記第１データ列に属する入力データと、該入力データに対して１点前の前記第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する第３の変換処理と、
前記第３の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第４の変換処理と、
前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する第５の変換処理と、
前記第５の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する第６の変換処理と、
前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列を始点とする系列上の第Ｌ＋１段階の一時データを１点当たり１クロック周期内に算出する第７の変換処理と、
前記第７の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する第８の変換処理と、
を全ての点の前記最終段階の前記中間データが算出されるまで前記２点演算部に繰り返し実行させるように制御する、ウェーブレット変換装置。
【請求項５】
請求項４記載のウェーブレット変換装置であって、
前記制御部は、前記第１の変換処理および前記第３の変換処理を実行した後に、前記第５の変換処理および前記第７の変換処理を、前記最終段階の前記一時データが算出されるまで前記２点演算部に実行させ、その後、前記第２の変換処理および前記第４の変換処理を実行した後に、前記第６の変換処理および前記第８の変換処理を、前記最終段階の前記中間データが算出されるまで前記２点演算部に実行させるように制御する、
ウェーブレット変換装置。
【請求項６】
請求項４記載のウェーブレット変換装置であって、
互いに独立に動作する４個の前記２点演算部を備え、
前記制御部は、前記変換処理として、
前記第２データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記一時データを算出する前記第１の変換処理と、
Ｐ−４番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記第５の変換処理と、
Ｐ−３番目の入力データを始点とする系列上の第１段階の前記中間データを算出する前記第４の変換処理と、
Ｐ−７番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第８の変換処理と、
の４工程を前記各２点演算部に並列に実行させると共に、
前記Ｐ番目の入力データを始点とする系列上の前記中間データを算出する前記第２の変換処理と、
前記Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第６の変換処理と、
Ｐ−１番目の入力データを始点とする系列上の前記一時データを算出する前記第３の変換処理と、
Ｐ−５番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記第７の変換処理と、
の４個の処理をそれぞれ前記各２点演算部に並列に実行させるように制御する、ウェーブレット変換装置。
【請求項７】
請求項１または請求項２記載のウェーブレット変換装置であって、
前記中間データ算出手段は、
前記データ・セレクタで選択的に取り込まれた３点の入力データの中で第１および第２の前記入力データを加算する第１加算器と、該第１加算器から出力されたデータに所定のリフティング係数を乗算する係数乗算器と、該係数乗算器から出力されたデータと第３の前記入力データとを加算することで前記中間データを算出する第２加算器とからなる３点演算部と、
前記３点演算部から出力された前記中間データを取り込んで前記制御部から指定された出力先に出力する出力先選択部と、
を備えると共に、
前記規格化手段は、
前記出力先選択部から出力された前記最終段階の前記中間データを遅延させる遅延器と、
該遅延器から出力された前記中間データに前記規格化係数を乗算することで前記高域成分および前記低域成分の出力データを算出する係数乗算器と、
を備えており、
前記メモリ管理部は、前記出力先選択部から出力された前記中間データを前記メモリに転送し記憶させるように制御する、
ウェーブレット変換装置。
【請求項８】
請求項７記載のウェーブレット変換装置であって、
前記制御部は、前記変換処理として、
前記第２データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の前記第１データ列に属する２点の入力データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第１の変換処理と、
前記第１データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の第１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、前記第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第２の変換処理と、
前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｍ段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の前記中間データを１点当たり１クロック周期内に算出する第３の変換処理と、
前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｌ＋１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する第４の変換処理と、
を全ての点の前記最終段階の前記中間データが算出されるまで前記３点演算部に繰り返し実行させるように制御する、ウェーブレット変換装置。
【請求項９】
請求項８記載のウェーブレット変換装置であって、
互いに独立に動作する２個の前記３点演算部を備え、
前記制御部は、
前記第１データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記第２の変換処理と、
Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第４の変換処理と、
の２個の処理をそれぞれ前記各３点演算部に並列に実行させるように制御する、ウェーブレット変換装置。
【請求項１０】
請求項８または請求項９記載のウェーブレット変換装置であって、
前記制御部は、
前記入力データ列の中でＰ＋３番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記第１の変換処理と、
Ｐ−１番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第３の変換処理と、
の２個の処理をそれぞれ前記各３点演算部に並列に実行させるように制御する、ウェーブレット変換装置。
【請求項１１】
請求項８記載のウェーブレット変換装置であって、前記制御部は、前記第１の変換処理〜前記第４の変換処理を並列にさせるように制御する、ウェーブレット変換装置。
【請求項１２】
請求項１〜請求項１１の何れか１項に記載のウェーブレット変換装置であって、
前記フィルタリング部は、直列に接続される第１フィルタリング部と第２フィルタリング部とから構成されており、
前記第１フィルタリング部は、入力する２次元画像データの水平方向および垂直方向のうちの一方向の前記高域成分および前記低域成分をライン単位で算出し、
前記第２フィルタリング部は、前記第１フィルタリング部で算出された前記高域成分および前記低域成分の各々に対して処理を実行することで、前記水平方向および前記垂直方向のうちの他方向の前記高域成分および前記低域成分を算出する、
ウェーブレット変換装置。
【請求項１３】
リフティング構成に基づいて、入力データ列を高域成分と低域成分とに帯域分割するウェーブレット変換方法であって、
（ａ）偶数番目の入力データおよび奇数番目の入力データの一方からなる第１データ列とその他方からなる第２データ列とで構成される前記入力データ列から、前記入力データを選択的に取り込む工程と、
（ｂ）前記工程（ａ）で取り込まれた前記入力データの各々を単数または複数の段階に亘る一系列の中間データへ１点当たり１クロック周期内に変換する工程と、
（ｃ）前記第１データ列に属する入力データを始点とする系列上の最終段階の前記中間データに所定の規格化係数を乗算することで、前記低域成分の出力データを１点当たり１クロック周期内に算出する工程と、
（ｄ）前記第２データ列に属する入力データを始点とする系列上の最終段階の前記中間データに所定の規格化係数を乗算することで、前記高域成分の出力データを１点当たり１クロック周期内に算出する工程と、
を備え、
前記工程（ｂ）〜工程（ｄ）を、全ての点の前記出力データが算出されるまで繰り返し実行し、且つ、繰り返し実行される前記工程（ｂ）〜工程（ｄ）のうち少なくとも２工程を１クロック周期内に並列に実行することを特徴とするウェーブレット変換方法。
【請求項１４】
請求項１３記載のウェーブレット変換方法であって、前記工程（ｃ）および前記工程（ｄ）の少なくとも一方を、前記工程（ｂ）と共に並列に実行する、ウェーブレット変換方法。
【請求項１５】
請求項１３または請求項１４記載のウェーブレット変換方法であって、
前記工程（ｂ）は、
（ｂ−１）前記第２データ列に属する入力データと、該入力データに対して１点前の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する工程と、
（ｂ−２）前記工程（ｂ−１）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
（ｂ−３）前記第１データ列に属する入力データと、該入力データに対して１点前の前記第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、前記第１データ列に属する入力データを始点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する工程と、
（ｂ−４）前記工程（ｂ−３）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
（ｂ−５）前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する工程と、
（ｂ−６）前記工程（ｂ−５）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する工程と、
（ｂ−７）前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の一時データを１点当たり１クロック周期内に算出する工程と、
（ｂ−８）前記工程（ｂ−７）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
を備え、
前記工程（ｂ−１）〜工程（ｂ−８）を、全ての点の前記最終段階の前記中間データが算出されるまで繰り返し実行するウェーブレット変換方法。
【請求項１６】
請求項１５記載のウェーブレット変換方法であって、
前記工程（ｂ−１）および前記工程（ｂ−３）を実行した後に、前記工程（ｂ−５）および前記工程（ｂ−７）を、前記最終段階の前記一時データが算出されるまで実行し、
その後、前記工程（ｂ−２）および前記工程（ｂ−４）を実行した後に、前記工程（ｂ−６）および前記工程（ｂ−８）を、前記最終段階の前記中間データが算出されるまで実行する、
ウェーブレット変換方法。
【請求項１７】
請求項１５記載のウェーブレット変換方法であって、
前記第２データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記一時データを算出する前記工程（ｂ−１）と、
Ｐ−４番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記工程（ｂ−５）と、
Ｐ−３番目の入力データを始点とする系列上の第１段階の前記中間データを算出する前記工程（ｂ−４）と、
Ｐ−７番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−８）と、
の４工程を並列に実行すると共に、
前記Ｐ番目の入力データを始点とする系列上の前記中間データを算出する前記工程（ｂ−２）と、
前記Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−６）と、
Ｐ−１番目の入力データを始点とする系列上の前記一時データを算出する前記工程（ｂ−３）と、
Ｐ−５番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記工程（ｂ−７）と、
の４工程を並列に実行する、
ウェーブレット変換方法。
（第２、第４の実施形態）
【請求項１８】
請求項１３または請求項１４記載のウェーブレット変換方法であって、
前記工程（ｂ）は、
（ｂ−１）前記第２データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の前記第１データ列に属する２点の入力データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、前記第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
（ｂ−２）前記第１データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の第１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、前記第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
（ｂ−３）前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｍ段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
（ｂ−４）前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｌ＋１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、
を備え、
前記工程（ｂ−１）〜工程（ｂ−４）を、全ての点の前記最終段階の前記中間データが算出されるまで繰り返し実行するウェーブレット変換方法。
【請求項１９】
請求項１８記載のウェーブレット変換方法であって、
前記第１データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記工程（ｂ−２）と、
Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−４）と、
の２工程を並列に実行する、
ウェーブレット変換方法。
【請求項２０】
請求項１８または請求項１９記載のウェーブレット変換方法であって、
前記入力データ列の中でＰ＋３番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記工程（ｂ−１）と、
Ｐ−１番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−３）と、
の２工程を並列に実行する、
ウェーブレット変換方法。
【請求項２１】
請求項１８記載のウェーブレット変換方法であって、前記工程（ｂ−１）〜工程（ｂ−４）を並列に実行する、ウェーブレット変換方法。
【請求項２２】
請求項１３〜請求項２１の何れか１項に記載のウェーブレット変換方法であって、
２次元画像データに対して、当該２次元画像データの水平方向および垂直方向のうちの一方向にライン単位で前記工程（ａ）〜工程（ｄ）を適用した後に、当該工程（ｃ）および工程（ｄ）で算出された前記高域成分および前記低域成分の各々に対して、前記水平方向および前記垂直方向のうちの他方向に前記工程（ａ）〜工程（ｄ）を適用する、ウェーブレット変換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ウェーブレット変換を用いた圧縮伸長技術に関する。
【０００２】
【従来の技術】
画像データの高能率符号化方式として、離散ウェーブレット変換（Ｄｉｓｃｒｅｔｅ  Ｗａｖｅｌｅｔ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ、以下「ＤＷＴ」と呼ぶ。）に基づく画像の圧縮伸長方法が知られており、これはＩＳＯ（国際標準化機構）が策定するＪＰＥＧ２０００（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ  ２０００）方式で採用されている。ＤＷＴの演算方法としては、畳み込み演算方法とリフティング構成（ｌｉｆｔｉｎｇ  ｓｃｈｅｍｅ）に基づく演算方法とが知られており、両者は同一結果を出力するが、後者のリフティング構成に基づく演算方法の方が、前者の畳み込み演算方法と比べて、少ないメモリ使用量で高速演算が可能なことや、ロスレス（可逆）圧縮に適することなどの利点を有している。
【０００３】
一般に、ＤＷＴは、原信号を高域成分（高周波数成分）と低域成分（低周波数成分）とに帯域分割するフィルタバンクを用いて構成することが可能である。図４２に、ＤＷＴとその逆変換（逆ＤＷＴ）で用いるフィルタバンク２００Ｓ，２００Ａを模式的に示す。入力信号ｘ（ｎ）を低域成分と高域成分との２帯域に分解する分解側フィルタバンク２００Ｓは、低域成分を通過させるローパスフィルタ２０１Ｌと、高域成分を通過させるハイパスフィルタ２０１Ｈと、第１および第２ダウンサンプラー２０２，２０３とで構成されている。ローパスフィルタ２０１Ｌとハイパスフィルタ２０１Ｈは、畳み込み演算を実行するＦＩＲフィルタによって構成される。また、第１および第２ダウンサンプラー２０２，２０３は、それぞれ、フィルタ２０１Ｌ，２０１Ｈからの入力信号を１点おきに間引き、信号長を半分にして出力するものである。ＪＰＥＧ２０００の規格では、第１ダウンサンプラー２０２は奇数番目の信号を間引いて偶数番目の信号（低域成分）を出力し、第２ダウンサンプラー２０３は偶数番目の信号を間引いて奇数番目の信号（高域成分）を出力する。
【０００４】
他方、入力信号（低域成分，高域成分）を合成する合成側フィルタバンク２００Ａは、第１および第２アップサンプラー２０４，２０５と、ローパスフィルタ２０６Ｌと、ハイパスフィルタ２０６Ｈと、加算器２０７とで構成されている。ローパスフィルタ２０６Ｌとハイパスフィルタ２０６Ｈは、畳み込み演算を実行するＦＩＲフィルタによって構成されており、一般に、これら合成側フィルタ２０６Ｌ，２０６Ｈと分解側フィルタ２０１Ｌ，２０１Ｈとは完全再構成条件を満たすように構成される。また、第１および第２アップサンプラー２０４，２０５は、各点間にゼロ値を挿入し信号長を倍にして出力する。そして、加算器２０７は、各合成側フィルタ２０６Ｌ，２０６Ｈから出力された信号を加算し、合成信号ｘ’（ｎ）を出力する。ここで、完全再構成条件を満たす場合はｘ（ｎ）＝ｘ’（ｎ）が成立する。
【０００５】
２次元ＤＷＴは、２次元画像データに対して分解側フィルタバンク２００Ｓを、その２次元画像データの垂直方向，水平方向の順に繰り返し適用することで実行できる。図４３は、３次の分解レベル（ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｌｅｖｅｌ）でＤＷＴを施された２次元画像データ２１０を模式的に示す帯域分割図である。２次元画像データ２１０中の各ブロックがサブバンド（帯域成分）を表している。例えば、サブバンドＨＨ１は、分解レベル１における垂直方向の高域成分（Ｈ）と水平方向の高域成分（Ｈ）とからなり、サブバンドＬＨ２は、分解レベル２における垂直方向の高域成分（Ｈ）と水平方向の低域成分（Ｌ）とからなる。一般に、サブバンドＸＹｎ（Ｘ，Ｙは「Ｈ」または「Ｌ」の何れか、ｎは分解レベルの次数）は、分解レベルｎにおける垂直方向の成分Ｙと水平方向の成分Ｘとからなるものである。分解レベル３のＤＷＴの処理手順は次の通りである。先ず、２次元画像全体に、上記分解側フィルタバンク２００Ｓを２回適用することで、分解レベル１のサブバンドＨＨ１，ＨＬ１，ＬＨ１，ＬＬ１（図示せず）が生成される。次に、分解レベル１の最低域のサブバンドＬＬ１に、分解側フィルタバンク２００Ｓを２回適用することで、分解レベル２のサブバンドＨＨ２，ＨＬ２，ＬＨ２，ＬＬ２（図示せず）が生成される。そして、分解レベル２の最低域のサブバンドＬＬ２に、分解側フィルタバンク２００Ｓを２回適用することで、分解レベル３のサブバンドＨＨ３，ＨＬ３，ＬＨ３，ＬＬ３が生成される。以上、３次の分解レベルの例を示したが、ＪＰＥＧ２０００方式では、一般に、３次〜８次以上の分解レベルが採用される。また、本例では、１枚の静止画像全体に一括してＤＷＴを施したが、実際には、実装メモリ容量などの関係上、１枚の静止画像を複数の矩形状の「タイル」と称する領域に分割し、各タイル単位でＤＷＴを実行することも行われている。
【０００６】
一方、ＤＷＴはリフティング構成で実現することも可能である。公知の９×７タップのＤａｕｂｅｃｈｉｅｓフィルタの場合、入力データＸ（２ｎ），Ｘ（２ｎ＋１），Ｘ（２ｎ＋２）（ｎ：整数）などと、出力データＹ（２ｎ），Ｙ（２ｎ＋１）との間の関係式は、次式（１）で規定するリフティング構成で表現できる。
【０００７】
【数１】
2004165907.tif 000003
【０００８】
上式（１）中、奇数番目の出力データＹ（２ｎ＋１）は高域成分を示し、偶数番目の出力データＹ（２ｎ）は低域成分を示している。また、係数α，β，γ，δはリフティング係数と呼ばれ、係数κ，１／κは規格化係数と呼ばれており、これら係数α，β，γ，δ，κ，１／κは、９×７タップのＤａｕｂｅｃｈｉｅｓフィルタのフィルタ係数によって一意に導出される。
【０００９】
上式（１）で規定されるリフティング構成は、図４４に示す格子構造で表現することが可能である。図４４の左端の縦一列に並ぶ格子点は、それぞれ、入力データ…，Ｘ（２ｎ−１），Ｘ（２ｎ），…，Ｘ（２ｎ＋９），Ｘ（２ｎ＋１０），…（ｎ：整数）を表している。また、これら入力データから水平方向右方に延びる線分の右端の格子点は、それぞれ、出力データ…，Ｙ（２ｎ−１），Ｙ（２ｎ），…，Ｙ（２ｎ＋９），Ｙ（２ｎ＋１０），…を表している。
【００１０】
また、各入力データＸ（ｋ）（ｋ：整数）を示す格子点から、出力データＹ（ｋ）を示す格子点まで延びる線分上の複数の格子点は、一系列の中間データを表している。例えば、入力データＸ（２ｎ）と出力データＹ（２ｎ）との間の線分上には、入力データＸ（２ｎ）を始点として生成された中間データＳ１ｎ，Ｓ２ｎを表す格子点が存在している。
【００１１】
この格子構造に基づく演算は次の（Ａ）〜（Ｃ）の規則に従って行われる。（Ａ）格子点を表すデータは、当該格子点から右方へ延びる線分に沿って移動する。（Ｂ）各線分を移動するデータは、当該線分に付した係数を乗算される（係数乗算処理）。（Ｃ）各格子点では、線分に沿って左方から移動してきたデータが加算される（加算処理）。例えば、入出力データＸ（２ｎ），Ｙ（２ｎ）間の線分上の中間データＳ１ｎは、Ｓ１ｎ＝１×Ｘ（２ｎ）＋β×Ｄ１ｎ−１＋β×Ｄ１ｎ、のように算出される。この式は、上式（１）中の［ｓｔｅｐ２］に相当するものである。
【００１２】
図４４に示すように、例えば、中間データＳ１ｎは、図面左方の３つの格子点Ｄ１ｎ−１，Ｘ（２ｎ），Ｄ１ｎから遷移したデータを加算したものである。全ての中間データが、当該中間データよりも左方の３つの格子点から遷移した３点のデータを加算することで算出されることが分かる。ＪＰＥＧ２０００方式は、１点の中間データの算出処理を２工程に分けて行うことを推奨している（”Ｍａｔｈｉａｓ  Ｌａｒｓｓｏｎ  Ｃａｒｌａｎｄｅｒ，  Ｍｅｄｉａ  Ｌａｂ，  Ｅｒｉｃｓｓｏｎ  Ｒｅｓｅａｒｃｈ，  Ｓｗｅｄｅｎ，  ＪＰＥＧ２０００  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｍｏｄｅｌ  ９．１  （Ｔｅｃｈｎｉｃａｌ  ｄｅｓｃｒｉｐｔｉｏｎ）  ＷＧ１  Ｎ２１６５，  ２８  Ｊｕｎｅ，  ２００１”の非特許文献１を参照）。図４５は、そのＪＰＥＧ２０００方式が推奨する算出方法を模式的に示す図である。格子点ｘ１，ｘ２，ｘ３，ｙがデータを表しており、α，β，γは、各格子点間を結ぶ線分に付した係数を表している。図示するように、データｙは、ステップａで一時データｚを算出した後に、ステップｂで算出されることが分かる。
【００１３】
【非特許文献１】
マシアス・ラーソン・カーランダー（Ｍａｔｈｉａｓ  Ｌａｒｓｓｏｎ  Ｃａｒｌａｎｄｅｒ）著，メディアラボ，エリクソン研究所，スエーデン（Ｍｅｄｉａ  Ｌａｂ，  Ｅｒｉｃｓｓｏｎ  Ｒｅｓｅａｒｃｈ，  Ｓｗｅｄｅｎ），「ＪＰＥＧ２０００  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｍｏｄｅｌ  ９．１  （Ｔｅｃｈｎｉｃａｌ  ｄｅｓｃｒｉｐｔｉｏｎ）  ＷＧ１  Ｎ２１６５」，２００１年６月２８日。
【００１４】
【発明が解決しようとする課題】
しかしながら、前述のＪＰＥＧ２０００方式が推奨するリフティング演算では、以下に説明するように、１点の出力データを算出するために要する処理時間が長いという問題がある。
【００１５】
図４６〜図５６は、リフティング構成による順変換の処理手順の例を説明するための格子図である。なお、図示しないが、各格子点間を結ぶ全ての線分には、図４４に示した係数が対応付けされているものとする。また、図４６〜図５６では、黒く塗りつぶした格子点は、入力済み或いは計算済みのデータ点を表し、上半分だけ塗りつぶした格子点は、上記ステップａの処理だけが終了した一時データの点を表し、空白の格子点は、ステップａとステップｂの何れの処理もなされていない未計算の点を表している。これら各図に示す処理は、何れも、１クロック周期内に実行される。
【００１６】
図４６〜図４９に示すＮ回目（Ｎ：整数）〜Ｎ＋３回目の処理では、全て、上記ステップａが実行される。Ｎ回目（Ｎ：整数）処理（図４６）では、対象領域Ａ１内の２点の入力データＸ（２ｎ＋４），Ｘ（２ｎ＋５）を用いた処理により、奇数番目の入力データＸ（２ｎ＋５）を始点とする第１段階の一時データ（Ｄ１ｎ＋２）が算出される。次のＮ＋１回目処理（図４７）では、対象領域Ａ２内の２点のデータＸ（２ｎ＋４），Ｄ１ｎ＋１を用いた処理により、偶数番目の入力データＸ（２ｎ＋４）を始点とする第１段階の一時データ（Ｓ１ｎ＋２）が算出される。次のＮ＋２回目処理（図４８）では、対象領域Ａ３内の２点のデータＤ１ｎ＋１，Ｓ１ｎ＋１を用いた処理により、奇数番目の入力データＸ（２ｎ＋３）を始点とする系列上の第２段階の一時データ（Ｄ２ｎ＋１）が算出される。そして、Ｎ＋３回目処理（図４９）では、対象領域Ａ４内の２点のデータＳ１ｎ＋１，Ｄ２ｎを用いた処理により、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の最終段階（第２段階）の一時データ（Ｓ２ｎ＋１）が算出される。
【００１７】
次のＮ＋４回目の処理（図５０）では、対象領域Ａ５内の中間データＤ２ｎを規格化することで、奇数番目の入力データＸ（２ｎ＋１）を始点とする系列上の高域成分の出力データＹ（２ｎ＋１）が算出される。
【００１８】
次に、図５１〜図５４に示すＮ＋５回目〜Ｎ＋８回目の処理では、全て、上記ステップｂが実行される。Ｎ＋５回目処理（図５１）では、対象領域Ｂ１内の入力データＸ（２ｎ＋６）と、上記Ｎ回目処理で算出した一時データ（Ｄ１ｎ＋２）とを用いた処理により、中間データＤ１ｎ＋２が算出される。次のＮ＋６回目処理（図５２）では、対象領域Ｂ２内の前記Ｎ＋５回目処理で算出した中間データＤ１ｎ＋２と、上記Ｎ＋１回目処理で算出した一時データ（Ｓ１ｎ＋２）とを用いた処理により、中間データＳ１ｎ＋２が算出される。次のＮ＋７回目処理（図５３）では、対象領域Ｂ３内の前記Ｎ＋６回目処理で算出した中間データＳ１ｎ＋２と、上記Ｎ＋２回目処理で算出した一時データ（Ｄ２ｎ＋１）とを用いた処理により、中間データＤ２ｎ＋１が算出される。そして、Ｎ＋８回目処理（図５４）では、対象領域Ｂ４内の前記Ｎ＋７回目処理で算出した中間データＤ２ｎ＋１と、上記Ｎ＋３回目処理で算出した一時データ（Ｓ２ｎ＋１）とを用いた処理により、中間データＳ２ｎ＋１が算出される。
【００１９】
次に、Ｎ＋９回目処理（図５５）では、対象領域Ｂ５内の中間データＳ２ｎ＋１を規格化することで、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の低域成分の出力データＹ（２ｎ＋２）が算出される。
【００２０】
次に、Ｎ＋１０回目処理（図５６）では、上記Ｎ回目処理と同様に、対象領域Ａ１０内の２点の入力データＸ（２ｎ＋６），Ｘ（２ｎ＋７）を用いた上記ステップａの処理により、一時データ（Ｄ１ｎ＋３）が算出される。この後は、上記Ｎ＋１回目〜Ｎ＋９回目処理と同様の処理が繰り返し実行される。
【００２１】
このように、高域成分Ｙ（２ｎ＋１）と低域成分Ｙ（２ｎ＋２）の２点の出力データを算出するために、Ｎ回目〜Ｎ＋９回目の１０クロック周期が必要であることが分かる。したがって、１点の出力データを算出するために平均して５クロック周期が必要となる。この５クロック周期を更に短縮することでＤＷＴ演算を高速に実行し得る処理方法が求められている。
【００２２】
以上の問題などに鑑みて本発明が解決しようとするところは、リフティング構成に基づくウェーブレット変換を短時間で効率良く実行し得るウェーブレット変換装置およびウェーブレット変換方法を提供する点にある。
【００２３】
【課題を解決するための手段】
上記課題を解決するため、請求項１記載の発明は、リフティング構成に基づいて、入力データ列を高域成分と低域成分とに帯域分割するウェーブレット変換装置であって、制御部と、メモリ管理部と、前記メモリ管理部の制御によりデータを一時記憶するメモリと、偶数番目の入力データおよび奇数番目の入力データの一方からなる第１データ列とその他方からなる第２データ列とで構成される前記入力データ列を取り込んで該入力データ列の前記高域成分および前記低域成分を算出するフィルタリング部と、を備えて構成されており、前記フィルタリング部は、前記入力データ列を選択的に取り込むデータ・セレクタと、前記データ・セレクタで取り込まれた入力データの各々を単数または複数の段階に亘る一系列の中間データへ１点当たり１クロック周期内に変換する単数または複数の変換処理を実行する中間データ算出手段と、前記各入力データを始点とする系列上の最終段階の前記中間データに所定の規格化係数を乗算することで、前記高域成分および前記低域成分の出力データを１点当たり１クロック周期内に算出する単数または複数の規格化処理を実行する規格化手段と、を備えており、前記制御部は、前記中間データ算出手段および前記規格化手段に、前記単数または複数の変換処理および前記単数または複数の規格化処理を、全ての点の前記出力データが算出されるまで繰り返し実行させ、且つ、繰り返し実行される前記単数または複数の変換処理および前記単数または複数の規格化処理のうち少なくとも２個の処理を１クロック周期内に並列に実行させるように制御することを特徴としている。
【００２４】
請求項２記載の発明は、請求項１記載のウェーブレット変換装置であって、前記中間データ算出手段および前記規格化手段は、前記変換処理および前記規格化処理を並列に実行するものである。
【００２５】
請求項３記載の発明は、請求項１または請求項２記載のウェーブレット変換装置であって、前記中間データ算出手段は、前記データ・セレクタで選択的に取り込まれた２点の入力データの一方に所定のリフティング係数を乗算する係数乗算器と、該係数乗算器から出力されたデータと前記２点の入力データの他方とを加算する加算器とからなる２点演算部と、前記２点演算部から出力されたデータを取り込んで前記制御部から指定された出力先に出力する出力先選択部と、を備えると共に、前記規格化手段は、前記出力先選択部から出力された前記最終段階の前記中間データを遅延させる遅延器と、該遅延器から出力された前記中間データに前記規格化係数を乗算することで前記高域成分および前記低域成分の出力データを算出する係数乗算器と、を備えており、前記メモリ管理部は、前記出力先選択部から出力された前記データを前記メモリに転送し記憶させるように制御するものである。
【００２６】
請求項４記載の発明は、請求項３記載のウェーブレット変換装置であって、前記制御部は、前記変換処理として、前記第２データ列に属する入力データと、該入力データに対して１点前の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを起点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する第１の変換処理と、前記第１の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第２の変換処理と、前記第１データ列に属する入力データと、該入力データに対して１点前の前記第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する第３の変換処理と、前記第３の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第４の変換処理と、前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する第５の変換処理と、前記第５の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する第６の変換処理と、前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列を始点とする系列上の第Ｌ＋１段階の一時データを１点当たり１クロック周期内に算出する第７の変換処理と、前記第７の変換処理で算出され前記メモリに記憶された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する第８の変換処理と、を全ての点の前記最終段階の前記中間データが算出されるまで前記２点演算部に繰り返し実行させるように制御するものである。
【００２７】
請求項５記載の発明は、請求項４記載のウェーブレット変換装置であって、前記制御部は、前記第１の変換処理および前記第３の変換処理を実行した後に、前記第５の変換処理および前記第７の変換処理を、前記最終段階の前記一時データが算出されるまで前記２点演算部に実行させ、その後、前記第２の変換処理および前記第４の変換処理を実行した後に、前記第６の変換処理および前記第８の変換処理を、前記最終段階の前記中間データが算出されるまで前記２点演算部に実行させるように制御するものである。
【００２８】
請求項６記載の発明は、請求項４記載のウェーブレット変換装置であって、互いに独立に動作する４個の前記２点演算部を備え、前記制御部は、前記変換処理として、前記第２データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記一時データを算出する前記第１の変換処理と、Ｐ−４番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記第５の変換処理と、Ｐ−３番目の入力データを始点とする系列上の第１段階の前記中間データを算出する前記第４の変換処理と、Ｐ−７番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第８の変換処理と、の４工程を前記各２点演算部に並列に実行させると共に、前記Ｐ番目の入力データを始点とする系列上の前記中間データを算出する前記第２の変換処理と、前記Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第６の変換処理と、Ｐ−１番目の入力データを始点とする系列上の前記一時データを算出する前記第３の変換処理と、Ｐ−５番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記第７の変換処理と、の４個の処理をそれぞれ前記各２点演算部に並列に実行させるように制御するものである。
【００２９】
請求項７記載の発明は、請求項１または請求項２記載のウェーブレット変換装置であって、前記中間データ算出手段は、前記データ・セレクタで選択的に取り込まれた３点の入力データの中で第１および第２の前記入力データを加算する第１加算器と、該第１加算器から出力されたデータに所定のリフティング係数を乗算する係数乗算器と、該係数乗算器から出力されたデータと第３の前記入力データとを加算することで前記中間データを算出する第２加算器とからなる３点演算部と、前記３点演算部から出力された前記中間データを取り込んで前記制御部から指定された出力先に出力する出力先選択部と、を備えると共に、前記規格化手段は、前記出力先選択部から出力された前記最終段階の前記中間データを遅延させる遅延器と、該遅延器から出力された前記中間データに前記規格化係数を乗算することで前記高域成分および前記低域成分の出力データを算出する係数乗算器と、を備えており、前記メモリ管理部は、前記出力先選択部から出力された前記中間データを前記メモリに転送し記憶させるように制御するものである。
【００３０】
請求項８記載の発明は、請求項７記載のウェーブレット変換装置であって、前記制御部は、前記変換処理として、前記第２データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の前記第１データ列に属する２点の入力データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第１の変換処理と、前記第１データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の第１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、前記第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する第２の変換処理と、前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｍ段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の前記中間データを１点当たり１クロック周期内に算出する第３の変換処理と、前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｌ＋１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する第４の変換処理と、を全ての点の前記最終段階の前記中間データが算出されるまで前記３点演算部に繰り返し実行させるように制御するものである。
【００３１】
請求項９記載の発明は、請求項８記載のウェーブレット変換装置であって、互いに独立に動作する２個の前記３点演算部を備え、前記制御部は、前記第１データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記第２の変換処理と、Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第４の変換処理と、の２個の処理をそれぞれ前記各３点演算部に並列に実行させるように制御するものである。
【００３２】
請求項１０記載の発明は、請求項８または請求項９記載のウェーブレット変換装置であって、前記制御部は、前記入力データ列の中でＰ＋３番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記第１の変換処理と、Ｐ−１番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記第３の変換処理と、の２個の処理をそれぞれ前記各３点演算部に並列に実行させるように制御するものである。
【００３３】
請求項１１記載の発明は、請求項８記載のウェーブレット変換装置であって、前記制御部は、前記第１の変換処理〜前記第４の変換処理を並列にさせるように制御するものである。
【００３４】
請求項１２記載の発明は、請求項１〜請求項１１の何れか１項に記載のウェーブレット変換装置であって、前記フィルタリング部は、直列に接続される第１フィルタリング部と第２フィルタリング部とから構成されており、前記第１フィルタリング部は、入力する２次元画像データの水平方向および垂直方向のうちの一方向の前記高域成分および前記低域成分をライン単位で算出し、前記第２フィルタリング部は、前記第１フィルタリング部で算出された前記高域成分および前記低域成分の各々に対して処理を実行することで、前記水平方向および前記垂直方向のうちの他方向の前記高域成分および前記低域成分を算出するものである。
【００３５】
次に、請求項１３記載の発明は、リフティング構成に基づいて、入力データ列を高域成分と低域成分とに帯域分割するウェーブレット変換方法であって、（ａ）偶数番目の入力データおよび奇数番目の入力データの一方からなる第１データ列とその他方からなる第２データ列とで構成される前記入力データ列から、前記入力データを選択的に取り込む工程と、（ｂ）前記工程（ａ）で取り込まれた前記入力データの各々を単数または複数の段階に亘る一系列の中間データへ１点当たり１クロック周期内に変換する工程と、（ｃ）前記第１データ列に属する入力データを始点とする系列上の最終段階の前記中間データに所定の規格化係数を乗算することで、前記低域成分の出力データを１点当たり１クロック周期内に算出する工程と、（ｄ）前記第２データ列に属する入力データを始点とする系列上の最終段階の前記中間データに所定の規格化係数を乗算することで、前記高域成分の出力データを１点当たり１クロック周期内に算出する工程と、を備え、前記工程（ｂ）〜工程（ｄ）を、全ての点の前記出力データが算出されるまで繰り返し実行し、且つ、繰り返し実行される前記工程（ｂ）〜工程（ｄ）のうち少なくとも２工程を１クロック周期内に並列に実行することを特徴としている。
【００３６】
請求項１４記載の発明は、請求項１３記載のウェーブレット変換方法であって、前記工程（ｃ）および前記工程（ｄ）の少なくとも一方を、前記工程（ｂ）と共に並列に実行するものである。
【００３７】
請求項１５記載の発明は、請求項１３または請求項１４記載のウェーブレット変換方法であって、前記工程（ｂ）は、（ｂ−１）前記第２データ列に属する入力データと、該入力データに対して１点前の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する工程と、（ｂ−２）前記工程（ｂ−１）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の前記第１データ列に属する入力データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、（ｂ−３）前記第１データ列に属する入力データと、該入力データに対して１点前の前記第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、前記第１データ列に属する入力データを始点とする系列上の第１段階の一時データを１点当たり１クロック周期内に算出する工程と、（ｂ−４）前記工程（ｂ−３）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の第１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、（ｂ−５）前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する工程と、（ｂ−６）前記工程（ｂ−５）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｍ段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の一時データを１点当たり１クロック周期内に算出する工程と、（ｂ−７）前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の一時データを１点当たり１クロック周期内に算出する工程と、（ｂ−８）前記工程（ｂ−７）で算出された前記一時データと、該一時データの系列に対して１点後の系列上の第Ｌ＋１段階の前記中間データに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、を備え、前記工程（ｂ−１）〜工程（ｂ−８）を、全ての点の前記最終段階の前記中間データが算出されるまで繰り返し実行するものである。
【００３８】
請求項１６記載の発明は、請求項１５記載のウェーブレット変換方法であって、前記工程（ｂ−１）および前記工程（ｂ−３）を実行した後に、前記工程（ｂ−５）および前記工程（ｂ−７）を、前記最終段階の前記一時データが算出されるまで実行し、その後、前記工程（ｂ−２）および前記工程（ｂ−４）を実行した後に、前記工程（ｂ−６）および前記工程（ｂ−８）を、前記最終段階の前記中間データが算出されるまで実行するものである。
【００３９】
請求項１７記載の発明は、請求項１５記載のウェーブレット変換方法であって、前記第２データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記一時データを算出する前記工程（ｂ−１）と、Ｐ−４番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記工程（ｂ−５）と、Ｐ−３番目の入力データを始点とする系列上の第１段階の前記中間データを算出する前記工程（ｂ−４）と、Ｐ−７番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−８）と、の４工程を並列に実行すると共に、前記Ｐ番目の入力データを始点とする系列上の前記中間データを算出する前記工程（ｂ−２）と、前記Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−６）と、Ｐ−１番目の入力データを始点とする系列上の前記一時データを算出する前記工程（ｂ−３）と、Ｐ−５番目の入力データを始点とする系列上の第２段階の前記一時データを算出する前記工程（ｂ−７）と、の４工程を並列に実行するものである。
【００４０】
請求項１８記載の発明は、請求項１３または請求項１４記載のウェーブレット変換方法であって、前記工程（ｂ）は、（ｂ−１）前記第２データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の前記第１データ列に属する２点の入力データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、前記第２データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、（ｂ−２）前記第１データ列に属する入力データと、該入力データの系列に対して１点前後する２系列上の第１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、前記第１データ列に属する入力データを始点とする系列上の第１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、（ｂ−３）前記第２データ列に属する入力データを始点とする系列上の第Ｍ段階（段階数Ｍは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｍ段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第２データ列に属する入力データを始点とする系列上の第Ｍ＋１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、（ｂ−４）前記第１データ列に属する入力データを始点とする系列上の第Ｌ段階（段階数Ｌは１以上の整数）の前記中間データと、該中間データの系列に対して１点前後する２系列上の第Ｌ＋１段階の２点の前記中間データを加算したデータに所定のリフティング係数を乗算して得たデータとを加算することで、当該第１データ列に属する入力データを始点とする系列上の第Ｌ＋１段階の前記中間データを１点当たり１クロック周期内に算出する工程と、を備え、前記工程（ｂ−１）〜工程（ｂ−４）を、全ての点の前記最終段階の前記中間データが算出されるまで繰り返し実行するものである。
【００４１】
請求項１９記載の発明は、請求項１８記載のウェーブレット変換方法であって、前記第１データ列に属し且つ前記入力データ列の中でＰ番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記工程（ｂ−２）と、Ｐ−４番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−４）と、の２工程を並列に実行するものである。
【００４２】
請求項２０記載の発明は、請求項１８または請求項１９記載のウェーブレット変換方法であって、前記入力データ列の中でＰ＋３番目（データ番号Ｐは整数）の入力データを始点とする系列上の前記中間データを算出する前記工程（ｂ−１）と、Ｐ−１番目の入力データを始点とする系列上の第２段階の前記中間データを算出する前記工程（ｂ−３）と、の２工程を並列に実行するものである。
【００４３】
請求項２１記載の発明は、請求項１８記載のウェーブレット変換方法であって、前記工程（ｂ−１）〜工程（ｂ−４）を並列に実行するものである。
【００４４】
そして、請求項２２記載の発明は、請求項１３〜請求項２１の何れか１項に記載のウェーブレット変換方法であって、２次元画像データに対して、当該２次元画像データの水平方向および垂直方向のうちの一方向にライン単位で前記工程（ａ）〜工程（ｄ）を適用した後に、当該工程（ｃ）および工程（ｄ）で算出された前記高域成分および前記低域成分の各々に対して、前記水平方向および前記垂直方向のうちの他方向に前記工程（ａ）〜工程（ｄ）を適用するものである。
【００４５】
【発明の実施の形態】
＜第１の実施形態＞
以下、本発明の第１の実施形態に係るウェーブレット変換装置およびウェーブレット変換方法について説明する。図１は、第１の実施形態に係るウェーブレット変換装置１の概略構成を示す図である。このウェーブレット変換装置１は、画素単位で入力する２次元画像データｘ（ｎ）（ｎは整数）を一時的に保持するバッファ８、外部供給のクロック信号ＣＬＫと同期して動作するＭＭＵ（メモリ管理部）２、第１リングメモリ３Ａ、垂直フィルタリング部４Ａ、ラインバッファ回路５、第２リングメモリ３Ｂおよび水平フィルタリング部４Ｂを備えて構成されている。ここで、第１リングメモリ３Ａ、垂直フィルタリング部４Ａ、ラインバッファ回路５、第２リングメモリ３Ｂおよび水平フィルタリング部４Ｂは、外部供給の画素クロック信号ＰＣＬＫと同期して動作する。
【００４６】
本実施形態では、ＭＭＵ２、垂直フィルタリング部４Ａおよび水平フィルタリング部４Ｂはハードウェアで構成されるが、この代わりに、マイクロプロセッサで実行する命令群を含むコンピュータ・プログラムで構成されてもよい。
【００４７】
このウェーブレット変換装置１に入力した２次元画像データｘ（ｎ）はバッファ８に一時的に記憶される。ウェーブレット変換装置１は、２次元画像データにラインベースの２次元ＤＷＴを１回施す機能を有している。垂直フィルタリング部４Ａと水平フィルタリング部４Ｂとは、ラインバッファ回路５と第２リングメモリ３Ｂとを介して直列に接続されている。後述するように、２次元画像データは、垂直フィルタリング部４Ａで垂直方向にフィルタリングされた後に、水平フィルタリング部４Ｂで水平方向にフィルタリングされる。２次以上の分解レベルの２次元ＤＷＴを実行する場合、このウェーブレット変換装置１を２回以上繰り返し利用すればよい。
【００４８】
ＭＭＵ２は、バッファ８と第１リングメモリ３Ａと第２リングメモリ３Ｂとのデータ入出力を制御する機能を有しており、バッファ８から読出した２次元画像データを第１リングメモリ３Ａに転送し記憶させることができる。垂直フィルタリング部４Ａは、第１リングメモリ３Ａから入力したデータに対して２次元画像の垂直方向にフィルタリングを実行することで、画素クロック信号ＰＣＬＫの８クロック周期で、その垂直方向の高域成分と同方向の低域成分とをそれぞれ１点ずつ算出してラインバッファ回路５に出力できる。よって、１点の出力データを算出するのに要する平均周期は４クロック周期である。
【００４９】
ラインバッファ回路５から出力されたデータは、第２リングメモリ３Ｂに記憶される。ＭＭＵ２は、この第２リングメモリ３Ｂから水平フィルタリング部４Ｂに入データを入力させる。水平フィルタリング部４Ｂは、入力データに対して２次元画像の水平方向にフィルタリングを実行することで、画素クロック信号ＰＣＬＫの８周期で、その水平方向の高域成分と同方向の低域成分とをそれぞれ１点ずつ算出し、出力データＹ（ｋ）として出力する。
【００５０】
垂直フィルタリング部４Ａの構成と水平フィルタリング部４Ｂの構成は互いに同一である。図２に、フィルタリング部４（垂直フィルタリング部４Ａまたは水平フィルタリング部４Ｂ）の概略構成を示す。図２に示すリングメモリ３は、図１に示した第１リングメモリ３Ａと第２リングメモリ３Ｂとの何れか一方を表すものとする。
【００５１】
このフィルタリング部４は、入力データを選択的に取り込むデータ・セレクタ１１、第１係数乗算器１２、加算器１５、出力先選択部（ＤＭＵＸ）１６、遅延レジスタ１７、第２係数乗算器１８および制御部２１を備えて構成される。制御部２１は、画素クロック信号ＰＣＬＫと同期して動作する。データ・セレクタ１１は、この制御部２１から供給される選択制御信号ＳＥＬ０の値に応じて、リングメモリ３で取り込んだ入力データをそれぞれ第１端子Ｓ０と第２端子Ｓ１とに出力する。また、第１係数乗算器１２は、制御部２１から供給される制御信号Ｃ０に応じて、前記第１端子Ｓ０から出力されたデータにリフティング係数α，β，γ，δの何れかを乗算して出力する（係数乗算処理）。加算器１５は、この第１係数乗算器１２から出力されたデータと、データ・セレクタ１１の第２端子Ｓ１から出力されたデータとを加算して出力先選択部１６に出力する（加算処理）。また、出力先選択部１６は、制御部２１から供給される選択制御信号ＳＥＬ１の値に応じて、加算器１５から入力するデータを第１端子Ｋ０と第２端子Ｋ１との一方から出力する。第１係数乗算器１２と加算器１５での係数乗算処理と加算処理は、１点当たり１クロック周期内に実行される。したがって、１点の入力データにリフティング係数を乗算し加算するのに要する期間は、画素クロック信号ＰＣＬＫの１周期である。
【００５２】
なお、係数レジスタ１３と加算器１５とはデータ・セレクタ１１から２点の入力データを取り込んで演算する２点演算部を構成する。また、この２点演算部と出力先選択部１６とで中間データ算出手段が構成される。
【００５３】
出力先選択部１６の第１端子Ｋ０から出力されたデータは、遅延レジスタ１７で画素クロック信号ＰＣＬＫの１クロック周期遅延した後に第２係数乗算器１８に入力する。第２係数乗算器１８は、制御部２１から供給される制御信号Ｃ１の値に応じて、入力データに規格化係数κ，１／κの何れか一方を乗算する規格化処理を１クロック周期内に実行し、その結果得た低域成分或いは高域成分の出力データＹ（ｋ）を外部へ出力する。なお、遅延レジスタ１７と第２係数乗算器１８とで本発明の規格化手段が構成される。
【００５４】
また、出力先選択部１６の第１端子Ｋ０から出力されたデータは分岐して外部のＭＭＵ２にも出力される。また、第２端子Ｋ１から出力されるデータは外部のＭＭＵ２に出力される。ＭＭＵ２は、第１端子Ｋ０と第２端子Ｋ１からそれぞれ外部へ出力されたデータをリングメモリ３に転送し記憶させることができる。
【００５５】
次に、以上のフィルタリング部４を用いたリフティング演算の代表例を、図３〜図１１を参照しつつ以下に説明する。図３〜図１１は、９×７タップのＤａｕｂｅｃｈｉｅｓフィルタのリフティング構成を模式的に示す格子図である。この格子図の演算は、図４４の場合と同様に行われる。なお、図３〜図１１では、説明の便宜上、各格子点間を結ぶ線分に対応するリフティング係数α，β，γ，δと規格化係数κ，１／κとを表示していない。
【００５６】
図３〜図１１に示す通り、入力データ…，Ｘ（２ｎ−１），Ｘ（２ｎ），…，Ｘ（２ｎ＋９），Ｘ（２ｎ＋１０），…は、それぞれ、複数の段階に亘る一系列の格子点（中間データ）に変換された後に規格化され、出力データ…，Ｙ（２ｎ−１），Ｙ（２ｎ），…，Ｙ（２ｎ＋９），Ｙ（２ｎ＋１０），…として出力される。例えば、入力データＸ（２ｎ）は、２段階の中間データ（格子点）に変換された後に出力データＹ（２ｎ）に規格化される。以下、中間データを算出する処理を変換処理と呼び、中間データを規格化する処理を規格化処理と呼ぶ。なお、本実施形態や後述する他の実施形態では、各系列で２段階の中間データが算出されるが、本発明ではこれに限らず、１段階だけの中間データを算出するリフティング構成もあり得る。実際に、５×３タップや１３×７タップのフィルタの場合、１段階だけの中間データを算出するリフティング構成が可能である。
【００５７】
図３〜図１１は、本実施形態でのＮ回目（Ｎは整数）〜Ｎ＋８回目の処理の内容を示している。Ｎ回目処理（図３）では、対象領域Ａ１内の２点の入力データＸ（２ｎ＋４），Ｘ（２ｎ＋５）を用いた上記ステップａ（図４５）の２点演算を画素クロック信号ＰＣＬＫの１周期（１クロック周期）内に実行して、奇数番目の入力データＸ（２ｎ＋５）を始点とする系列上の第１段階の一時データ（Ｄ１ｎ＋２）を算出する。すなわち、奇数番目の入力データＸ（２ｎ＋５）と、この入力データＸ（２ｎ＋５）に対して１点前の系列上の偶数番目の入力データＸ（２ｎ＋４）とを用いて上記ステップａの処理が実行される。
【００５８】
このＮ回目の具体的な処理の内容は次の通りである。図２に示すリングメモリ３は、入力データや中間データや一時データを格納する５ライン（系列）の記憶領域を備えており、参照済みの古いデータを格納する記憶領域に新たなデータを順番に上書きする構造を持つ。ＭＭＵ２は、このリングメモリ３に一時記憶された２点の入力データＸ（２ｎ＋４），Ｘ（２ｎ＋５）をデータ・セレクタ１１に出力させる。制御部２１は、選択制御信号ＳＥＬ０をデータ・セレクタ１１に供給して、入力データＸ（２ｎ＋４），Ｘ（２ｎ＋５）のうち一方の入力データＸ（２ｎ＋４）を第１係数乗算器１２に出力させ、他方の入力データＸ（２ｎ＋５）を加算器１５に出力させる。第１係数乗算器１２は、制御部２１から供給された制御信号Ｃ０に従って選択したリフティング係数αを乗算器１４に出力し、乗算器１４は、入力データＸ（２ｎ＋４）にリフティング係数αを乗算して得たデータα×Ｘ（２ｎ＋４）を加算器１５に出力する。そして、加算器１５は、２点のデータα×Ｘ（２ｎ＋４）とＸ（２ｎ＋５）を加算することで一時データ（Ｄ１ｎ＋２）を算出し、出力先選択部１６に出力する。この一時データ（Ｄ１ｎ＋２）の算出処理は１クロック周期内に実行される。
【００５９】
出力先選択部１６は、制御部２１から供給された選択制御信号ＳＥＬ１の値に従って選択した第２端子Ｋ１から、外部のＭＭＵ２に一時データ（Ｄ１ｎ＋２）を出力する。ＭＭＵ２は、その一時データ（Ｄ１ｎ＋２）をリングメモリ３に転送し、演算に使用した入力データＸ（２ｎ＋５）を二度と使用することはないので、参照済みの入力データＸ（２ｎ＋５）が格納されていた記憶領域に上書きさせる。
【００６０】
次の第Ｎ＋１回目処理（図４）では、対象領域Ａ２内の２点の入力データＸ（２ｎ＋４）と中間データＤ１ｎ＋１とを用いた上記ステップａの２点演算を１クロック周期内に実行して、偶数番目の入力データＸ（２ｎ＋４）を始点とする系列上の第１段階の一時データ（Ｓ１ｎ＋２）を算出する。中間データＤ１ｎ＋１は、入力データＸ（２ｎ＋４）に対して１点前の入力データＸ（２ｎ＋３）を始点とする系列上の第１段階のデータである。具体的には、ＭＭＵ２は、リングメモリ３から、入力データＸ（２ｎ＋４）と計算済みの中間データＤ１ｎ＋１とをデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、入力データＸ（２ｎ＋４）を第２端子Ｓ１から加算器１５に出力し、中間データＤ１ｎ＋１を第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、中間データＤ１ｎ＋１にリフティング係数βを乗算して加算器１５に出力し、加算器１５は、リフティング係数βを重み付けされた中間データβ×Ｄ１ｎ＋１と入力データＸ（２ｎ＋４）とを加算して一時データ（Ｓ１ｎ＋２）を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その一時データ（Ｓ１ｎ＋２）を第２端子Ｋ１から外部のＭＭＵ２に出力し、ＭＭＵ２は、その一時データ（Ｓ１ｎ＋２）をリングメモリ３に転送し、参照済みの入力データＸ（２ｎ＋４）が格納されていた記憶領域に上書きさせる。
【００６１】
次のＮ＋２回目処理（図５）では、対象領域Ａ３内の２点の中間データＤ１ｎ＋１，Ｓ１ｎ＋１を用いた上記ステップａの２点演算を１クロック周期内に実行して、奇数番目の入力データＸ（２ｎ＋３）を始点とする系列上の第２段階の一時データ（Ｄ２ｎ＋１）を算出する。中間データＳ１ｎ＋１は、入力データＸ（２ｎ＋３）に対して１点前の入力データＸ（２ｎ＋２）を始点とする系列上の第１段階のデータである。具体的には、ＭＭＵ２は、リングメモリ３から、計算済みの２点の中間データＤ１ｎ＋１，Ｓ１ｎ＋１をデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、中間データＤ１ｎ＋１を第２端子Ｓ１から加算器１５に出力し、中間データＳ１ｎ＋１を第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、中間データＳ１ｎ＋１にリフティング係数γを乗算して加算器１５に出力し、加算器１５は、リフティング係数γを重み付けされた中間データγ×Ｓ１ｎ＋１と中間データＤ１ｎ＋１とを加算して一時データ（Ｄ２ｎ＋１）を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その一時データ（Ｄ２ｎ＋１）を第２端子Ｋ１から外部のＭＭＵ２に出力し、ＭＭＵ２は、その一時データ（Ｄ２ｎ＋１）をリングメモリ３に転送し、参照済みの中間データＤ１ｎ＋１が格納されていた記憶領域に上書きさせる。
【００６２】
次のＮ＋３回目処理（図６）では、対象領域Ａ４内の２点の中間データＳ１ｎ＋１とＤ２ｎとを用いた上記ステップａの２点演算を１クロック周期内に実行して、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の第２段階の一時データ（Ｓ２ｎ＋１）を算出する。中間データＤ２ｎは、入力データＸ（２ｎ＋２）に対して１点前の入力データＸ（２ｎ＋１）を始点とする系列上の第２段階のデータである。具体的には、ＭＭＵ２は、リングメモリ３から、計算済みの２点の中間データＳ１ｎ＋１とＤ２ｎとをデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、中間データＳ１ｎ＋１を第２端子Ｓ１から加算器１５に出力し、中間データＤ２ｎを第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、中間データＤ２ｎにリフティング係数δを乗算して加算器１５に出力し、加算器１５は、リフティング係数δを重み付けされた中間データδ×Ｄ２ｎと中間データＳ１ｎ＋１とを加算して一時データ（Ｓ２ｎ＋１）を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その一時データ（Ｓ２ｎ＋１）を第２端子Ｋ１から外部のＭＭＵ２に出力し、ＭＭＵ２は、その一時データ（Ｓ２ｎ＋１）をリングメモリ３に転送し、参照済みの中間データＳ１ｎ＋１が格納されていた記憶領域に上書きさせる。
【００６３】
次のＮ＋４回目処理（図７）では、上記Ｎ回目処理（図３）で算出した一時データ（Ｄ１ｎ＋２）と対象領域Ａ５内の偶数番目の入力データＸ（２ｎ＋６）とを用いた上記ステップｂ（図４５）の２点演算を１クロック周期内に実行して、奇数番目の入力データＸ（２ｎ＋５）を始点とする系列上の第１段階の中間データＤ１ｎ＋２を算出する。入力データＸ（２ｎ＋６）は、一時データ（Ｄ１ｎ＋２）の系列に対して１点後の系列上のデータである。具体的には、ＭＭＵ２は、リングメモリ３から、入力データＸ（２ｎ＋６）と一時データ（Ｄ１ｎ＋２）とをデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、一時データ（Ｄ１ｎ＋２）を第２端子Ｓ１から加算器１５に出力し、入力データＸ（２ｎ＋６）を第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、入力データＸ（２ｎ＋６）にリフティング係数αを乗算して加算器１５に出力し、加算器１５は、リフティング係数αを重み付けされた入力データα×Ｘ（２ｎ＋６）と一時データ（Ｄ１ｎ＋２）とを加算して中間データＤ１ｎ＋２を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その中間データＤ１ｎ＋２を第２端子Ｋ１から外部のＭＭＵ２に出力し、ＭＭＵ２は、その中間データＤ１ｎ＋２をリングメモリ３に転送し、参照済みの一時データ（Ｄ１ｎ＋２）が格納されていた記憶領域に上書きさせる。
【００６４】
次のＮ＋５回目処理（図８）では、上記Ｎ＋１回目処理（図４）で算出した一時データ（Ｓ１ｎ＋２）と、前記Ｎ＋４回目処理（図７）で算出した対象領域Ａ６内の中間データＤ１ｎ＋２とを用いた上記ステップｂの２点演算を１クロック周期内に実行して、偶数番目の入力データＸ（２ｎ＋４）を始点とする系列上の第１段階の中間データＳ１ｎ＋２を算出する。なお、中間データＤ１ｎ＋２は、一時データ（Ｓ１ｎ＋２）の系列に対して１点後の系列上の第１段階のデータである。具体的には、ＭＭＵ２は、リングメモリ３から、一時データ（Ｓ１ｎ＋２）と中間データＤ１ｎ＋２とをデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、一時データ（Ｓ１ｎ＋２）を第２端子Ｓ１から加算器１５に出力し、中間データＤ１ｎ＋２を第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、中間データＤ１ｎ＋２にリフティング係数βを乗算して加算器１５に出力し、加算器１５は、リフティング係数βを重み付けされた中間データβ×Ｄ１ｎ＋２と一時データ（Ｓ１ｎ＋２）とを加算して中間データＳ１ｎ＋２を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その中間データＳ１ｎ＋２を第２端子Ｋ１から外部のＭＭＵ２に出力し、ＭＭＵ２は、その中間データＳ１ｎ＋２をリングメモリ３に転送し、参照済みの一時データ（Ｓ１ｎ＋２）が格納されていた記憶領域に上書きさせる。
【００６５】
次のＮ＋６回目処理（図９）では、上記Ｎ＋２回目処理（図５）で算出した一時データ（Ｄ２ｎ＋１）と、前記Ｎ＋５回目処理（図８）で算出した対象領域Ａ７内の中間データＳ１ｎ＋２とを用いた上記ステップｂの２点演算を１クロック周期内に実行して、奇数番目の入力データＸ（２ｎ＋３）を始点とする第２段階の中間データＤ２ｎ＋１を算出する。なお、中間データＳ１ｎ＋２は、一時データ（Ｄ２ｎ＋１）の系列に対して１点後の系列上の第１段階のデータである。また、対象領域Ｎ１において、前記中間データＤ２ｎ＋１を算出した時から１クロック周期の後に、前記中間データＤ２ｎ＋１に規格化係数κを乗算する規格化処理を実行して、高域成分である奇数番目の出力データＹ（２ｎ＋３）を算出する。
【００６６】
このＮ＋６回目の具体的な処理内容は次の通りである。ＭＭＵ２は、リングメモリ３から、一時データ（Ｄ２ｎ＋１）と中間データＳ１ｎ＋２とをデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、一時データ（Ｄ２ｎ＋１）を第２端子Ｓ１から加算器１５に出力し、中間データＳ１ｎ＋２を第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、中間データＳ１ｎ＋２にリフティング係数γを乗算して加算器１５に出力し、加算器１５は、リフティング係数γを重み付けされた中間データγ×Ｓ１ｎ＋２と一時データ（Ｄ２ｎ＋１）とを加算して中間データＤ２ｎ＋１を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その中間データＤ２ｎ＋１を第１端子Ｋ０から出力する。この結果、その中間データＤ２ｎ＋１は、遅延レジスタ１７に出力され保持される一方、外部のＭＭＵ２にも出力される。ＭＭＵ２はその中間データＤ２ｎ＋１をリングメモリ３に転送し、参照済みの一時データ（Ｄ２ｎ＋１）が格納されていた記憶領域に上書きさせる。
【００６７】
また、出力先選択部１６の第１端子Ｋ０から出力された中間データＤ２ｎ＋１は、遅延レジスタ１７で１クロック周期遅延した後に第２係数乗算器１８に入力する。第２係数乗算器１８において、係数レジスタ１９は、制御部２１から供給された制御信号Ｃ１に従って選択した規格化係数κを乗算器２０に出力し、乗算器２０は入力する中間データＤ２ｎ＋１に規格化係数κを乗算する。この結果、第２係数乗算器１８は、高域成分である奇数番目の出力データＹ（２ｎ＋３）（＝κ×Ｄ２ｎ＋１）を算出する。この第２係数乗算器１８での係数乗算処理は１クロック周期内に実行される。
【００６８】
次のＮ＋７回目処理（図１０）における変換処理は、前記Ｎ＋６回目処理（図９）における対象領域Ｎ１内の規格化処理と並行して行うことができる。変換処理では、上記Ｎ＋３回目処理（図６）で算出した一時データ（Ｓ２ｎ＋１）と、前記Ｎ＋６回目処理（図９）で算出した対象領域Ａ８内の中間データＤ２ｎ＋１とを用いた上記ステップｂの処理を１クロック周期内に実行して、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の第２段階の中間データＳ２ｎ＋１を算出する。なお、中間データＤ２ｎ＋１は、一時データ（Ｓ２ｎ＋１）の系列に対して１点後の系列上の第２段階のデータである。この中間データＳ２ｎ＋１を算出する変換処理と、上記Ｎ＋６回目処理（図９）において出力データＹ（２ｎ＋３）を算出する規格化処理とを並列に同時実行することが可能である。また、対象領域Ｎ２においては、前記中間データＳ２ｎ＋１を算出した時から１クロック周期の後に、前記中間データＳ２ｎ＋１に規格化係数１／κを乗算する規格化処理を実行して、低域成分である偶数番目の出力データＹ（２ｎ＋２）を算出する。
【００６９】
具体的には、このＮ＋７回目処理では、ＭＭＵ２は、リングメモリ３から、一時データ（Ｓ２ｎ＋１）と中間データＤ２ｎ＋１とをデータ・セレクタ１１に出力させる。次に、制御部２１の制御により、データ・セレクタ１１は、一時データ（Ｓ２ｎ＋１）を第２端子Ｓ１から加算器１５に出力し、中間データＤ２ｎ＋１を第１端子Ｓ０から第１係数乗算器１２に出力する。第１係数乗算器１２は、中間データＤ２ｎ＋１にリフティング係数δを乗算して加算器１５に出力し、加算器１５は、リフティング係数δを重み付けされた中間データδ×Ｄ２ｎ＋１と一時データ（Ｓ２ｎ＋１）とを加算して中間データＳ２ｎ＋１を算出し、出力先選択部１６に出力する。出力先選択部１６は、制御部２１の制御により、その中間データＳ２ｎ＋１を第１端子Ｋ０から出力する。この結果、その中間データＳ２ｎ＋１は、遅延レジスタ１７に出力され保持される。以上の変換処理と並列に、第２係数乗算器１８においては出力データＹ（２ｎ＋３）を算出する規格化処理が実行される。
【００７０】
また、出力先選択部１６の第１端子Ｋ０から出力された中間データＳ２ｎ＋１は、遅延レジスタ１７で１クロック周期遅延した後に第２係数乗算器１８に入力する。第２係数乗算器１８において、係数レジスタ１９は、制御部２１から供給された制御信号Ｃ１に従って選択した規格化係数１／κを乗算器２０に出力し、乗算器２０は入力する中間データＳ２ｎ＋１に規格化係数１／κを乗算する。この結果、第２係数乗算器１８は、低域成分である偶数番目の出力データＹ（２ｎ＋２）（＝（１／κ）×Ｓ２ｎ＋１）を算出する。この第２係数乗算器１８での係数乗算処理は１クロック周期内に実行される。
【００７１】
次のＮ＋８回目処理（図１１）では、対象領域を除いて上記Ｎ回目処理（図３）と同様の処理が行われる。このＮ＋８回目処理の対象領域Ａ９は、上記Ｎ回目処理の対象領域Ａ１から２系列後方に移動した領域である。すなわち、対象領域Ａ９内の２点の入力データＸ（２ｎ＋６），Ｘ（２ｎ＋７）を用いた上記ステップａの２点演算を実行して、奇数番目の入力データＸ（２ｎ＋７）を始点とする系列上の第１段階の一時データ（Ｄ１ｎ＋３）が算出される。
【００７２】
以上のように、上記Ｎ回目処理（図３）〜上記Ｎ＋７回目処理（図１０）と同様の処理が、全ての点の出力データ…，Ｙ（２ｎ−１），Ｙ（２ｎ），…が算出されるまで対象領域を移動させつつ実行される。
【００７３】
また、本実施形態では、上記Ｎ回目〜Ｎ＋３回目の処理で示したように、最終段階の一時データ（Ｓ２ｎ＋１）が算出されるまで上記ステップａの２点演算が実行され、その後、上記Ｎ＋４回目〜Ｎ＋７回目の処理で示したように、上記Ｎ回目〜Ｎ＋３回目の処理で算出した全ての一時データを中間データに変換する上記ステップｂの２点演算が行われている。
【００７４】
以上のように、本実施形態に係るウェーブレット変換方法では、入力データ…，Ｘ（２ｎ），Ｘ（２ｎ＋１），…を中間データに変換する変換処理と、最終段階の中間データを規格化する規格化処理とを１クロック周期内に並列に同時実行するため、１点の出力データを算出するのに要する平均周期を４クロック周期とすることができ、出力データの算出周期を短縮化できる。
【００７５】
次に、上記ウェーブレット変換装置１を用いたラインベースの２次元ＤＷＴ処理を以下に説明する。
【００７６】
垂直フィルタリング部４Ａに入力する２次元画像データ２３は、図１２に示すように水平画素数Ｗを有する矩形状のデータであって、図１３に模式的に示すように、垂直方向に配列するデータ列…，Ｘｉ（２ｎ），Ｘｉ（２ｎ＋１），Ｘｉ（２ｎ＋２）…として入力させられる。入力データＸｉ（ｋ）の添字ｉは、当該入力データＸｉ（ｋ）が所属する画素列の番号を示すものとする。画素列の番号ｉは、ｉ＝０，１，…，Ｗ−１（Ｗ：水平画素数）の値をとる。
【００７７】
第１リングメモリ３Ａと垂直フィルタリング部４Ａとは、画像データ２３を垂直方向に帯域分割して、図１４の模式図に示すように高域成分Ｈと低域成分Ｌとを生成する。次いで、第２リングメモリ３Ｂと水平フィルタリング部４Ｂとは、垂直フィルタリング部４Ａから出力された高域成分Ｈと低域成分Ｌとをそれぞれ帯域分割して、図１５の模式図に示すように４つの帯域成分ＬＬ，ＨＬ，ＬＨ，ＨＨとを生成し外部に出力することになる。
【００７８】
具体的には、第１リングメモリ３Ａと垂直フィルタリング部４Ａは、上記Ｎ回目処理（図３）〜上記Ｎ＋８回目処理（図１１）を含む各回の処理を、各画素列について水平ライン単位で繰り返し実行する。例えば、上記Ｎ回目処理（図３）が、０番目の画素列に対して実行された後に、１番目の画素列に対して実行され、次に、２番目の画素列に対して実行され、・・・、最終的に、Ｗ−１番目の画素列に対して実行される。次に、上記Ｎ＋１回目処理（図４）が、０番目の画素列に対して実行された後に、１番目の画素列に対して実行され、更に、２番目の画素列に対して実行され、・・・、最終的に、Ｗ−１番目の画素列に対して実行される。このようにして、各回の処理が全ての画素列について順次実行される。なお、第１リングメモリ３Ａは、図１３に模式的に示すように、入力データ列に対応する５×Ｗ点（５ライン）のデータを保持する記憶領域２４を有しており、上記一時データや中間データを保持することができる。
【００７９】
この結果、垂直フィルタリング部４Ａからは、高域成分Ｈのデータと低域成分Ｌのデータとが各水平ライン単位で連続的に出力され、ラインバッファ回路５でバッファリングされる。例えば、上記Ｎ＋７回目処理（図１０）が０番目〜Ｗ−１番目の各画素列に対して連続的に実行された結果、２ｎ＋３番目の水平ラインの高域成分ＨのデータＹ０（２ｎ＋３），Ｙ１（２ｎ＋３），…，Ｙｊ（２ｎ＋３），…，ＹＷ−１（２ｎ＋３）が連続的に出力され、ラインバッファ回路５でバッファリングされる。また、上記Ｎ＋８回目処理（図１１）が０番目〜Ｗ−１番目の画素列に対して連続的に実行された結果、２ｎ＋２番目の水平ラインの低域成分ＬのデータＹ０（２ｎ＋２），Ｙ１（２ｎ＋２），…，Ｙｊ（２ｎ＋２），…，ＹＷ−１（２ｎ＋２）が連続的に出力され、ラインバッファ回路５でバッファリングされる。
【００８０】
ラインバッファ回路５は、ＭＭＵ２の制御により、１水平ラインの高域成分Ｈと１水平ラインの低域成分Ｌとを交互に第２リングメモリ３Ｂに供給する。例えば、上記Ｎ＋７回目処理（図１０）で算出された１水平ラインの高域成分ＨのデータＹ０（２ｎ＋３），Ｙ１（２ｎ＋３），…，Ｙｊ（２ｎ＋３），…，ＹＷ−１（２ｎ＋３）が第２リングメモリ３Ｂに出力され水平フィルタリング部４Ｂで処理された後に、上記Ｎ＋８回目処理（図１１）で算出された１水平ラインの低域成分ＬのデータＹ０（２ｎ＋２），Ｙ１（２ｎ＋２），…，Ｙｊ（２ｎ＋２），…，ＹＷ−１（２ｎ＋２）が第２リングメモリ３Ｂに出力される。
【００８１】
第２リングメモリ３Ｂと水平フィルタリング部４Ｂは、上記Ｎ回目処理（図３）〜上記Ｎ＋８回目処理（図１１）を含む各回の処理を画素単位で実行する。例えば、上記Ｎ回目処理（図３）が１回実行された後に、上記Ｎ＋１回目処理（図４）が１回実行され、更に、上記Ｎ＋２回目処理（図５）が１回実行され、・・・といった処理が行われる。なお、第２リングメモリ３Ｂは、図１６に模式的に示すように、入力データ…，Ｙｊ（ｋ），Ｙｊ＋１（ｋ），…に対応する５点（５画素）のデータを保持する記憶領域２６を有しており、上記一時データや中間データを保持することができる。
【００８２】
この結果、水平フィルタリング部４Ｂは、水平ライン単位で入力する高域成分Ｈと低域成分Ｌのデータ列に対して、４つの帯域成分ＨＨ，ＨＬ，ＬＨ，ＬＬのデータを算出する。
【００８３】
以上の処理を再帰的に実行させることで、任意次数の分解レベルの帯域成分を算出することができる。すなわち、ｋ−１次（ｋは２以上の整数）の分解レベルにおける水平方向と垂直方向の低域成分ＬＬ（ｋ−１）を、ウェーブレット変換装置１に再帰的に入力させることで、ｋ次の分解レベルにおける帯域成分ＨＨｋ，ＨＬｋ，ＬＨｋ，ＬＬｋを得ることが可能である。
【００８４】
以上のように、本実施形態に係るウェーブレット変換装置１では、図２に示す構成を有する垂直フィルタリング部４Ａと水平フィルタリング部４Ｂとを備えるため、高域成分と低域成分の出力データの算出周期を短縮化できる。したがって、ラインベースの２次元ウェーブレット変換を短時間で高速で行うことが可能である。
【００８５】
＜第２の実施形態＞
次に、本発明の第２の実施形態に係るウェーブレット変換装置およびウェーブレット変換方法について説明する。図１７は、第２の実施形態に係るウェーブレット変換装置３０の概略構成を示す図である。このウェーブレット変換装置３０は、画素単位で入力する２次元画像データｘ（ｎ）（ｎは整数）を一時的に保持するバッファ３４、外部供給のクロック信号ＣＬＫと同期して動作するＭＭＵ（メモリ管理部）３１、第１リングメモリ３２Ａ、垂直フィルタリング部３３Ａ、第２リングメモリ３２Ｂおよび水平フィルタリング部３３Ｂを備えて構成されている。ここで、第１リングメモリ３２Ａ、垂直フィルタリング部３３Ａ、第２リングメモリ３２Ｂおよび水平フィルタリング部３３Ｂは、外部供給の画素クロック信号ＰＣＬＫと同期して動作する。
【００８６】
本実施形態では、ＭＭＵ３１、垂直フィルタリング部３３Ａおよび水平フィルタリング部３３Ｂはハードウェアで構成されるが、この代わりに、マイクロプロセッサで実行する命令群を含むコンピュータ・プログラムで構成されてもよい。
【００８７】
このウェーブレット変換装置３０に入力した２次元画像データｘ（ｎ）はバッファ３４に一時的に記憶される。ウェーブレット変換装置３０は、２次元画像データにラインベースの２次元ＤＷＴを１回施す機能を有している。垂直フィルタリング部３３Ａと水平フィルタリング部３３Ｂとは、第２リングメモリ３２Ｂを介して直列に接続されている。２次元画像データは、垂直フィルタリング部３３Ａで垂直方向にフィルタリングされた後に、水平フィルタリング部３３Ｂで水平方向にフィルタリングされる。２次以上の分解レベルの２次元ＤＷＴを実行する場合、このウェーブレット変換装置３０を２回以上繰り返し利用すればよい。
【００８８】
ＭＭＵ３１は、バッファ３４と第１リングメモリ３２Ａと第２リングメモリ３２Ｂとのデータ入出力を制御する機能を有しており、バッファ３４から読出した２次元画像データを第１リングメモリ３２Ａに転送し記憶させることができる。垂直フィルタリング部３３Ａは、第１リングメモリ３２Ａから入力したデータに対して２次元画像の垂直方向にフィルタリングを実行することで、画素クロック信号ＰＣＬＫの２クロック周期で、その垂直方向の高域成分と同方向の低域成分とをそれぞれ１点ずつ算出して第２リングメモリ３２Ｂに出力できる。よって、１点の出力データを算出するのに要する平均周期は１クロック周期である。
【００８９】
第２リングメモリ３２Ｂは、垂直フィルタリング部３３Ａから出力された入力データを記憶する。ＭＭＵ３１は、この第２リングメモリ３２Ｂから水平フィルタリング部３３Ｂにデータを入力させる。水平フィルタリング部３３Ｂは、入力データに対して２次元画像の水平方向にフィルタリングを実行することで、画素クロック信号ＰＣＬＫの２クロック周期で、その水平方向の高域成分と低域成分とをそれぞれ１点ずつ算出し、出力データＹ（ｋ）として出力する。
【００９０】
垂直フィルタリング部３３Ａの構成と水平フィルタリング部３３Ｂの構成とは互いに同一である。図１８に、フィルタリング部３３（垂直フィルタリング部３３Ａまたは水平フィルタリング部３３Ｂ）の概略構成を示す。図１８に示すリングメモリ３２は、図１７に示した第１リングメモリ３２Ａと第２リングメモリ３２Ｂとの何れか一方を表すものとする。
【００９１】
このフィルタリング部３３は、入力データを選択的に取り込むデータ・セレクタ３５、加算器３６，４１，４０，４５、第１および第２係数乗算器３７，４２、出力先選択部（ＤＭＵＸ）４６、遅延レジスタ４８、第３係数乗算器４９および制御部４７を備えて構成される。これら構成要素のうち、２個の加算器３６，４０と第１係数乗算器３７からなる組は、３点のデータを１クロック周期内に処理する３点演算部を構成する。また、２個の加算器４１，４５と第２係数乗算器４２からなる組も同様に３点演算部を構成する。また、これら２組の３点演算部と出力先選択部４６とで中間データ算出手段が構成される。
【００９２】
制御部４７は、画素クロック信号ＰＣＬＫと同期して動作する。データ・セレクタ３５は、この制御部４７から供給される選択制御信号ＳＥＬ０の値に応じて、リングメモリ３２で取り込んだデータを第１端子Ｓ０〜第６端子Ｓ５の何れかから選択的に出力する。３点演算部においては、加算器３６は、データ・セレクタ３５の第１端子Ｓ０と第２端子Ｓ１とから出力された２点のデータを加算して第１係数乗算器３７に出力する。第１係数乗算器３７では、係数レジスタ３８は、制御部４７から供給される制御信号Ｃ０の値に応じて、リフティング係数δ，αの何れか一方を入力データに乗算して加算器４０に出力する。そして、加算器４０は、データ・セレクタ３５の第３端子Ｓ２から入力したデータと、第１係数乗算器３７から入力したデータとを加算して出力先選択部４６に出力する。
【００９３】
また、加算器４１は、データ・セレクタ３５の第５端子Ｓ４と第６端子Ｓ５とから出力された２点のデータを加算して第２係数乗算器４２に出力する。第２係数乗算器４２では、係数レジスタ４３は、制御部４７から供給される制御信号Ｃ１の値に応じて、リフティング係数β，γの何れか一方を入力データに乗算して加算器４５に出力する。加算器４５は、データ・セレクタ３５の第４端子Ｓ３から入力したデータと、第２係数乗算器４２から入力したデータとを加算して出力先選択部４６に出力する。
【００９４】
出力先選択部４６は、制御部４７から供給される選択制御信号ＳＥＬ１の値に応じて、加算器４０，４５から並列に入力する２点のデータの一方を第１端子Ｋ０と第２端子Ｋ１との一方から出力すると共に、２点のデータの他方を端子Ｋ０，Ｋ１の他方から出力する。
【００９５】
出力先選択部４６の第１端子Ｋ０から出力されたデータは、遅延レジスタ４８で画素クロック信号ＰＣＬＫの１クロック周期遅延した後に第３係数乗算器４９に入力する。第３係数乗算器４９では、係数レジスタ５０は、制御部４７から供給される制御信号Ｃ２の値に応じて、規格化係数κ，１／κの何れか一方を乗算器５１に出力し、乗算器５１は、入力データにその規格化係数を乗算する規格化処理を１クロック周期内に実行する。これにより、第３係数乗算器４９は、低域成分或いは高域成分の出力データＹ（ｋ）を外部へ出力する。なお、遅延レジスタ４８と第３係数乗算器４９とで本発明の規格化手段が構成される。
【００９６】
また、出力先選択部４６の第１端子Ｋ０から出力されたデータは分岐して外部のＭＭＵ２にも出力され、第２端子Ｋ１から出力されるデータは外部のＭＭＵ２に出力される。ＭＭＵ２は、第１端子Ｋ０と第２端子Ｋ１からそれぞれ外部へ出力されたデータをリングメモリ３２に転送し記憶させることができる。
【００９７】
次に、以上のフィルタリング部３３を用いたリフティング演算の代表例を、図１９〜図２３を参照しつつ以下に説明する。図１９〜図２３は、９×７タップのＤａｕｂｅｃｈｉｅｓフィルタのリフティング構成を模式的に示す格子図である。この格子図の演算は、図４４の場合と同様に行われる。なお、図１９〜図２３は、説明の便宜上、各格子点間を結ぶ線分に対応するリフティング係数α，β，γ，δと規格化係数κ，１／κとを表示していない。
【００９８】
図１９〜図２３は、本実施形態でのＮ回目（Ｎは整数）〜Ｎ＋４回目の処理を模式的に示している。Ｎ回目処理（図１９）では、対象領域Ｃ１，Ｃ２の２個の変換処理が１クロック周期内に並列に同時実行される。対象領域Ｃ２では、２点の中間データＤ２ｎ，Ｄ２ｎ＋１を加算したデータにリフティング係数δを乗算することで乗算値を算出した後、この乗算値と中間データＳ１ｎ＋１とを加算するという３点演算が実行される。この結果、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の最終段階（第２段階）の中間データＳ２ｎ＋１が算出される。２点の中間データＤ２ｎ，Ｄ２ｎ＋１は、中間データＳ１ｎ＋１の系列に対して１点前後する２系列上のデータである。また、対象領域Ｃ１では、２点の中間データＤ１ｎ＋２，Ｄ１ｎ＋３を加算したデータにリフティング係数βを乗算することで乗算値を算出した後、この乗算値と偶数番目の入力データＸ（２ｎ＋６）とを加算するという３点演算が実行される。この結果、偶数番目の入力データＸ（２ｎ＋６）を始点とする系列上の第１段階の中間データＳ１ｎ＋３が算出される。ここで、２点の中間データＤ１ｎ＋２，Ｄ１ｎ＋３は、入力データＸ（２ｎ＋６）の系列に対して１点前後する２系列上のデータである。また、対象領域Ｎ１においては、最終段階の前記中間データＳ２ｎ＋１を算出した時から１クロック周期の後に、前記中間データＳ２ｎ＋１に規格化係数１／κを乗算する規格化処理を実行して、低域成分である偶数番目の出力データＹ（２ｎ＋２）を算出する。
【００９９】
このＮ回目の具体的な処理の内容は次の通りである。図１８に示すリングメモリ３２は、入力データや中間データや一時データを格納する８ライン（系列）の記憶領域を備えており、参照済みの古いデータを格納する記憶領域に新たなデータを順番に上書きする構造を持つ。ＭＭＵ３１は、このリングメモリ３２に一時記憶された６点のデータＸ（２ｎ＋６），Ｄ１ｎ＋２，Ｄ１ｎ＋３，Ｓ１ｎ＋１，Ｄ２ｎ，Ｄ２ｎ＋１をデータ・セレクタ３５に出力させる。データ・セレクタ３５は、制御部４７から供給される選択制御信号ＳＥＬ０の値に応じて、前記６点のデータのうち対象領域Ｃ２内の３点のデータＳ１ｎ＋１，Ｄ２ｎ，Ｄ２ｎ＋１を選択して第１端子Ｓ０〜第３端子Ｓ２から出力し、前記６点のデータのうち対象領域Ｃ１内の３点のデータＸ（２ｎ＋６），Ｄ１ｎ＋２，Ｄ１ｎ＋３を選択して第４端子Ｓ３〜第６端子Ｓ５から出力する。
【０１００】
上方の加算器３６は、データ・セレクタ３５の第１端子Ｓ０と第２端子Ｓ１から入力した２点の中間データＤ２ｎ、Ｄ２ｎ＋１を加算したデータを第１係数乗算器３７に出力する。第１係数乗算器３７において、係数レジスタ３８は、制御部４７から供給される制御信号Ｃ０に従って、２個のリフティング係数α，δのうち前半の係数δを選択して乗算器３９に供給し、乗算器３９は、入力データとリフティング係数δとを乗算した乗算値（＝δ×（Ｄ２ｎ＋Ｄ２ｎ＋１））を加算器４０に出力する。そして、加算器４０は、第１係数乗算器３７から入力する乗算値と、データ・セレクタ３５の第３端子Ｓ２から入力した中間データＳ１ｎ＋１とを加算することで、対象領域Ｃ２内の中間データＳ２ｎ＋１を算出し、出力先選択部４６に出力する。この中間データＳ２ｎ＋１の算出処理は１クロック周期内に実行される。
【０１０１】
一方、下方の加算器４１は、データ・セレクタ３５の第５端子Ｓ４と第６端子Ｓ５とから入力した２点の中間データＤ１ｎ＋２，Ｄ１ｎ＋３を加算したデータを第２係数乗算器４２に出力する。第２係数乗算器４２では、係数レジスタ４３は、制御部４７から供給される制御信号Ｃ１に従って、２個のリフティング係数β，γのうち前半の係数βを選択して乗算器４４に供給し、乗算器４４は、入力データとリフティング係数βとを乗算した乗算値（＝β×（Ｄ１ｎ＋２＋Ｄ１ｎ＋３））を加算器４５に出力する。そして、加算器４５は、第２係数乗算器４２から入力する乗算値と、データ・セレクタ３５の第４端子Ｓ３から入力したデータＸ（２ｎ＋６）とを加算することで、対象領域Ｃ１内の中間データＳ１ｎ＋３を算出し、出力先選択部４６に出力する。
【０１０２】
出力先選択部４６は、制御部４７から供給された選択制御信号ＳＥＬ１の値に従って、加算器４０から入力した最終段階（第２段階）の中間データＳ２ｎ＋１を第１端子Ｋ０から出力し、他方の加算器４５から入力した中間データＳ１ｎ＋３を第２端子Ｋ１から出力する。第１端子Ｋ０から出力された最終段階の中間データＳ２ｎ＋１は、遅延レジスタ４８で１クロック周期遅延した後に第３係数乗算器４９に入力する。また、第２端子Ｋ１から出力された中間データＳ１ｎ＋３は、外部のＭＭＵ３１に出力される。ＭＭＵ３１は、中間データＳ１ｎ＋３をリングメモリ３２に転送し、参照済みの入力データＸ（２ｎ＋６）が格納されていた記憶領域に上書きさせる。
【０１０３】
また、出力先選択部４６の第１端子Ｋ０から出力された中間データＳ２ｎ＋１は、遅延レジスタ４８で１クロック周期遅延した後に第３係数乗算器４９に入力する。第３係数乗算器４９において、係数レジスタ５０は、制御部２１から供給された制御信号Ｃ１に従って、２個の規格化係数κ，１／κのうち後半の規格化係数１／κを乗算器５１に出力し、乗算器５１は入力する中間データＳ２ｎ＋１に規格化係数１／κを乗算する。この結果、第３係数乗算器４９は、低域成分である偶数番目の出力データＹ（２ｎ＋２）（＝（１／κ）×Ｓ２ｎ＋１）を１クロック周期内に算出する。
【０１０４】
次に、Ｎ＋１回目処理（図２０）における対象領域Ｃ３，Ｃ４の２個の変換処理が、上記Ｎ回目処理（図１９）における対象領域Ｎ１の規格化処理とともに１クロック周期内に並列に同時実行される。対象領域Ｃ３では、偶数番目の２点の入力データＸ（２ｎ＋８），Ｘ（２ｎ＋１０）を加算したデータにリフティング係数αを乗算することで乗算値を算出した後、この乗算値と奇数番目の入力データＸ（２ｎ＋９）とを加算するという３点演算が実行される。この結果、奇数番目の入力データＸ（２ｎ＋９）を始点とする系列上の第１段階の中間データＤ１ｎ＋４が算出される。ここで、偶数番目の２点の入力データＸ（２ｎ＋８），Ｘ（２ｎ＋１０）は、奇数番目の入力データＸ（２ｎ＋９）に対して１点前後するデータである。また、対象領域Ｃ４では、２点の中間データＳ１ｎ＋２，Ｓ１ｎ＋３を加算したデータにリフティング係数γを乗算することで乗算値を算出した後、この乗算値と中間データＤ１ｎ＋２とを加算するという３点演算が実行される。この結果、奇数番目の入力データＸ（２ｎ＋５）を始点とする系列上の最終段階の中間データＤ２ｎ＋２が算出される。ここで、２点の中間データＳ１ｎ＋２，Ｓ１ｎ＋３は、中間データＤ１ｎ＋２の系列に対して１点前後する２系列上のデータである。また、対象領域Ｎ２において、最終段階の前記中間データＤ２ｎ＋２を算出した時から１クロック周期の後に、前記中間データＤ２ｎ＋２に規格化係数κを乗算する規格化処理を実行して、高域成分である奇数番目の出力データＹ（２ｎ＋５）を算出する。
【０１０５】
このＮ＋１回目の具体的な処理内容は次の通りである。ＭＭＵ３１は、リングメモリ３２に一時記憶された６点のデータＳ１ｎ＋２，Ｓ１ｎ＋３，Ｄ１ｎ＋２，Ｘ（２ｎ＋８），Ｘ（２ｎ＋９），Ｘ（２ｎ＋１０）をデータ・セレクタ３５に出力させる。データ・セレクタ３５は、制御部４７から供給された選択制御信号ＳＥＬ０の値に応じて、前記６点のデータのうち対象領域Ｃ３内の３点の入力データＸ（２ｎ＋８），Ｘ（２ｎ＋９），Ｘ（２ｎ＋１０）を選択して第１端子Ｓ０〜第３端子Ｓ２から出力し、前記６点のデータのうち対象領域Ｃ４内の３点のデータＤ１ｎ＋２，Ｓ１ｎ＋２，Ｓ１ｎ＋３を選択して第４端子Ｓ３〜第６端子Ｓ５から出力する。
【０１０６】
上方の加算器３６は、データ・セレクタ３５の第１端子Ｓ０と第２端子Ｓ１から入力した２点のデータＸ（２ｎ＋８），Ｘ（２ｎ＋１０）を加算したデータを第１係数乗算器３７に出力する。第１係数乗算器３７において、係数レジスタ３８は、制御部４７から供給される制御信号Ｃ０に従って、２個のリフティング係数α，δのうち後半の係数αを選択して乗算器３９に供給し、乗算器３９は、入力データとリフティング係数αとを乗算した乗算値（＝α×（Ｘ（２ｎ＋８）＋Ｘ（２ｎ＋１０）））を加算器４０に出力する。そして、加算器４０は、第１係数乗算器３７から入力する乗算値と、データ・セレクタ３５の第３端子Ｓ２から入力したデータＸ（２ｎ＋９）とを加算することで、対象領域Ｃ３内の中間データＤ１ｎ＋４を算出し、出力先選択部４６に出力する。この中間データＤ１ｎ＋４の算出処理は１クロック周期内に実行される。
【０１０７】
一方、下方の加算器４１は、データ・セレクタ３５の第５端子Ｓ４と第６端子Ｓ５とから入力した２点の中間データＳ１ｎ＋２，Ｓ１ｎ＋３を加算したデータを第２係数乗算器４２に出力する。第２係数乗算器４２では、係数レジスタ４３は、制御部４７から供給される制御信号Ｃ１に従って、２個のリフティング係数β，γのうち後半の係数γを選択して乗算器４４に供給し、乗算器４４は、入力データとリフティング係数γとを乗算した乗算値（＝γ×（Ｓ１ｎ＋２＋Ｓ１ｎ＋３））を加算器４５に出力する。そして、加算器４５は、第２係数乗算器４２から入力する乗算値と、データ・セレクタ３５の第４端子Ｓ３から入力したデータＤ１ｎ＋２とを加算することで、対象領域Ｃ４内の中間データＤ２ｎ＋２を算出し、出力先選択部４６に出力する。
【０１０８】
出力先選択部４６は、制御部４７から供給された選択制御信号ＳＥＬ１の値に従って、加算器４５から入力した最終段階（第２段階）の中間データＤ２ｎ＋２を第１端子Ｋ０から出力し、他方の加算器４０から入力した中間データＤ１ｎ＋４を第２端子Ｋ１から出力する。第１端子Ｋ０から出力された最終段階の中間データＤ２ｎ＋２は、分岐して外部のＭＭＵ３１に出力されると共に、遅延レジスタ４８で１クロック周期遅延した後に第３係数乗算器４９に入力する。また、第２端子Ｋ１から出力された中間データＤ１ｎ＋４は、外部のＭＭＵ３１に出力される。ＭＭＵ３１は、それら２個の中間データＤ２ｎ＋２，Ｄ１ｎ＋４をリングメモリ３２に転送し、参照済みの中間データＤ１ｎ＋２と参照済みの入力データＸ（２ｎ＋９）とが格納されていた記憶領域に上書きさせる。
【０１０９】
また、出力先選択部４６の第１端子Ｋ０から出力された中間データＤ２ｎ＋２は、遅延レジスタ４８で１クロック周期遅延した後に第３係数乗算器４９に入力する。第３係数乗算器４９において、係数レジスタ５０は、制御部４７から供給された制御信号Ｃ１に従って選択した前半の規格化係数κを乗算器５１に出力し、乗算器５１は入力する中間データＤ２ｎ＋２に規格化係数κを乗算する。この結果、第３係数乗算器４９は、高域成分である奇数番目の出力データＹ（２ｎ＋５）（＝κ×Ｄ２ｎ＋２）を１クロック周期内に算出する。
【０１１０】
次に、Ｎ＋２回目処理（図２１）における対象領域Ｃ５，Ｃ６の２個の変換処理が、上記Ｎ＋１回目処理（図２０）における対象領域Ｎ２の規格化処理とともに１クロック周期内に並列に同時実行される。また、対象領域Ｃ５，Ｃ６の変換処理が終了した時から１クロック周期の後に、対象領域Ｎ３の規格化処理が実行される。ここで、対象領域Ｃ５，Ｃ６，Ｎ３は、それぞれ、上記Ｎ回目処理（図１９）の対象領域Ｃ１，Ｃ２，Ｎ１を２系列（２点）後方に移動した領域である。これら対象領域Ｃ５，Ｃ６，Ｎ３では、対象領域Ｃ１，Ｃ２，Ｎ１での処理と同様の処理が実行される。したがって、対象領域Ｃ５では、２点の中間データＤ１ｎ＋３，Ｄ１ｎ＋４を加算したデータにリフティング係数βを乗算することで乗算値を算出した後、この乗算値と入力データＸ（２ｎ＋８）とを加算するという３点演算が実行される。この結果、偶数番目の入力データＸ（２ｎ＋８）を始点とする系列上の第１段階の中間データＳ１ｎ＋４が算出される。また、対象領域Ｃ６では、２点の中間データＤ２ｎ＋１，Ｄ２ｎ＋２を加算したデータにリフティング係数δを乗算することで乗算値を算出した後、この乗算値と中間データＳ１ｎ＋２とを加算するという３点演算が実行される。この結果、偶数番目の入力データＸ（２ｎ＋４）を始点とする系列上の最終段階（第２段階）の中間データＳ２ｎ＋２が算出される。そして、１クロック周期の後に、対象領域Ｎ３では、偶数番目の入力データＸ（２ｎ＋４）を始点とする系列上の最終段階の中間データＳ２ｎ＋２に規格化係数１／κを乗算する規格化処理を実行して、偶数番目の出力データＹ（２ｎ＋４）を算出する。
【０１１１】
次に、Ｎ＋３回目処理（図２２）における対象領域Ｃ７，Ｃ８の２個の変換処理が、上記Ｎ＋２回目処理（図２１）における対象領域Ｎ３の規格化処理とともに１クロック周期内に並列に同時実行される。また、対象領域Ｃ７，Ｃ８の変換処理が終了した時から１クロック周期の後に、対象領域Ｎ４の規格化処理が実行される。ここで、対象領域Ｃ７，Ｃ８，Ｎ４は、それぞれ、上記Ｎ＋１回目処理（図２０）の対象領域Ｃ３，Ｃ４，Ｎ２を２系列（２点）後方に移動した領域である。これら対象領域Ｃ７，Ｃ８，Ｎ４では、対象領域Ｃ３，Ｃ４，Ｎ２での処理と同様の処理が実行される。したがって、対象領域Ｃ７では、偶数番目の２点の入力データＸ（２ｎ＋１０），Ｘ（２ｎ＋１２）を加算したデータにリフティング係数αを乗算することで乗算値を算出した後、この乗算値と奇数番目の入力データＸ（２ｎ＋１１）とを加算するという３点演算が実行される。この結果、奇数番目の入力データＸ（２ｎ＋１１）を始点とする系列上の第１段階の中間データＤ１ｎ＋５が算出される。また、対象領域Ｃ８では、２点の中間データＳ１ｎ＋３，Ｓ１ｎ＋４を加算したデータにリフティング係数γを乗算して乗算値を算出した後、この乗算値と中間データＤ１ｎ＋３とを加算するという３点演算が実行される。この結果、奇数番目の入力データＸ（２ｎ＋７）を始点とする系列上の最終段階の中間データＤ２ｎ＋３が算出される。そして、１クロック周期の後に、対象領域Ｎ４では、上記Ｎ＋３回目処理で算出した第２段階の中間データＤ２ｎ＋３に規格化係数κを乗算する規格化処理を実行して、奇数番目の出力データＹ（２ｎ＋７）を算出する。
【０１１２】
次のＮ＋４回目処理（図２３）では、上記Ｎ＋２回目処理（図２１）の対象領域Ｃ５，Ｃ６，Ｎ３を２系列（２点）後方に移動した対象領域Ｃ９，Ｃ１０，Ｎ５の３個の処理が実行される。これらの処理は、参照する対象領域のデータを除いて上記Ｎ＋２回目処理と同じであるため、その詳細な説明を省略する。
【０１１３】
以上のように、上記Ｎ回目処理（図１９）およびＮ＋１回目処理（図２０）と同様の処理が、全ての点の出力データが算出されるまで対象領域を移動させつつ繰り返し実行される。これにより、偶数番目或いは奇数番目の１点の出力データを算出するのに要する平均周期を１クロック周期とすることができ、出力データの算出周期を大幅に短縮化できる。
【０１１４】
次に、上記ウェーブレット変換装置３０を用いたラインベースの２次元ＤＷＴ処理を以下に説明する。
【０１１５】
垂直フィルタリング部３３Ａに入力するデータは、図１２と図１３に示したように水平画素数Ｗの矩形状の画像データ２３とする。第１リングメモリ３２Ａと垂直フィルタリング部３３Ａとは、画像データ２３を垂直方向に帯域分割して、図１４に示したように高域成分Ｈと低域成分Ｌとを生成する。次いで、第２リングメモリ３２Ｂと水平フィルタリング部３３Ｂとは、垂直フィルタリング部３３Ａから出力された高域成分Ｈと低域成分Ｌとをそれぞれ帯域分割して、図１５に示したように４つの帯域成分ＬＬ，ＨＬ，ＬＨ，ＨＨとを生成し外部に出力することになる。
【０１１６】
具体的には、第１リングメモリ３２Ａと垂直フィルタリング部３３Ａは、上記Ｎ回目処理（図１９）〜上記Ｎ＋４回目処理（図２３）を含む各回の処理を、各画素列について水平ライン単位で繰り返し実行する。例えば、上記Ｎ回目処理（図１９）が、０番目の画素列に対して実行された後に、１番目の画素列に対して実行され、次に、２番目の画素列に対して実行され、・・・、最終的に、Ｗ−１番目の画素列に対して実行される。その後、上記Ｎ＋１回目処理（図２０）が、０番目の画素列に対して実行された後に、１番目の画素列に対して実行され、次に、２番目の画素列に対して実行され、・・・、最終的に、Ｗ−１番目の画素列に対して実行される。このように各回の処理が全ての画素列について繰り返し実行される。
【０１１７】
なお、第１リングメモリ３２Ａは、図２４に模式的に示すように、各入力データに対応する８×Ｗ点（８ライン）のデータを保持する記憶領域５３を有しており、上記一時データや中間データを一時的に保持することができる。この記憶領域５３は、垂直方向に８点のデータを保持する列領域の集合体である。一つの列領域によって、１回の処理で参照される入力データや一時データや中間データが保持される。例えば、Ｎ回目処理（図１９）では、或る列領域において、データ列｛Ｄ２ｎ，Ｓ１ｎ＋１，Ｄ２ｎ＋１，Ｓ１ｎ＋２，Ｄ１ｎ＋２，Ｘ（２ｎ＋６），Ｄ１ｎ＋３，Ｘ（２ｎ＋８）｝から、データ列｛Ｄ２ｎ，Ｓ１ｎ＋１，Ｄ２ｎ＋１，Ｓ１ｎ＋２，Ｄ１ｎ＋２，Ｓ１ｎ＋３，Ｄ１ｎ＋３，Ｘ（２ｎ＋８）｝へ記憶内容が変化する（データＸ（２ｎ＋６）が中間データＳ１ｎ＋３に上書きされる）。
【０１１８】
結果として、垂直フィルタリング部３３Ａからは、高域成分Ｈのデータと低域成分Ｌのデータとが各水平ライン単位で連続的に出力される。例えば、上記Ｎ回目処理（図１９）を０番目〜Ｗ−１番目の画素列に対して連続的に実行した結果、２ｎ＋２番目の水平ラインの低域成分ＬのデータＹ０（２ｎ＋２），Ｙ１（２ｎ＋２），…，Ｙｊ（２ｎ＋２），…，ＹＷ−１（２ｎ＋２）が連続的に出力される。続けて、上記Ｎ＋１回目処理（図２０）を０番目〜Ｗ−１番目の画素列に対して連続的に実行した結果、２ｎ＋５番目の水平ラインの高域成分ＨのデータＹ０（２ｎ＋５），Ｙ１（２ｎ＋５），…，Ｙｊ（２ｎ＋５），…，ＹＷ−１（２ｎ＋５）が連続的に出力される。
【０１１９】
第２リングメモリ３２Ｂと水平フィルタリング部３３Ｂは、上記Ｎ回目処理（図１９）〜上記Ｎ＋４回目処理（図２３）を含む各回の処理を、画素単位で実行する。例えば、上記Ｎ回目処理（図１９）が１回実行された後に、上記Ｎ＋１回目処理（図２０）が１回実行され、更に、上記Ｎ＋２回目処理（図２１）が１回実行され、・・・といった処理が行われる。なお、第２リングメモリ３２Ｂは、図２５に模式的に示すように、入力データ…，Ｙｊ（ｋ），Ｙｊ＋１（ｋ），…に対応する８点（８画素）のデータを保持する記憶領域（列領域）５５を有しており、上記一時データや中間データを保持することができる。
【０１２０】
この結果、水平フィルタリング部３３Ｂは、水平ライン単位で入力する高域成分Ｈと低域成分Ｌのデータ列に対して、４つの帯域成分ＨＨ，ＨＬ，ＬＨ，ＬＬのデータを算出する。
【０１２１】
以上の処理を再帰的に実行させることで、任意次数の分解レベルの帯域成分を算出することができる。すなわち、ｋ−１次（ｋは２以上の整数）の分解レベルにおける水平方向と垂直方向の低域成分ＬＬ（ｋ−１）を、ウェーブレット変換装置３０に再帰的に入力させることで、ｋ次の分解レベルにおける帯域成分ＨＨｋ，ＨＬｋ，ＬＨｋ，ＬＬｋを得ることが可能である。
【０１２２】
このように、本実施形態に係るウェーブレット変換装置３０では、図１８に示す構成を有する垂直フィルタリング部３３Ａと水平フィルタリング部３３Ｂとを備えるため、複数点の中間データを算出する変換処理と中間データを規格化する規格化処理とを１クロック周期内に並列に同時実行できる。したがって、出力データの算出周期を大幅に短縮化でき、ウェーブレット変換を極めて短時間で高速に行うことが可能になる。
【０１２３】
また、本実施形態に係るウェーブレット変換装置３０では、水平フィルタリング部３３Ｂは１点のデータを出力するのに平均して１クロック周期しか要しないため、上記第１の実施形態に係るウェーブレット変換装置１のようにラインバッファ回路５を必要としない。したがって、小回路規模で、低消費電力で動作する廉価なウェーブレット変換装置３０の実現が可能である。
【０１２４】
＜第３の実施形態＞
次に、本発明の第３の実施形態に係るウェーブレット変換装置およびウェーブレット変換方法について説明する。本実施形態に係るウェーブレット変換装置は、垂直フィルタリング部と水平フィルタリング部を除いて、上記第２の実施形態に係るウェーブレット変換装置３０（図１７）の構成と同じ構成を有する。図２６は、第３の実施形態に係るフィルタリング部３３ｓの概略構成を示す図である。このフィルタリング部３３ｓは、垂直フィルタリング部または水平フィルタリング部を示し、また、リングメモリ３２ｓは、図１７に示した第１リングメモリ３２Ａまたは第２リングメモリ３２Ｂの何れかを示すものとする。
【０１２５】
このフィルタリング部３３ｓは、リングメモリ３２ｓから入力データを選択的に取り込むデータ・セレクタ６０、第１〜第４係数乗算器６１〜６４、第１〜第４加算器８３〜８６、出力先選択部（ＤＭＵＸ）７４、遅延レジスタ７５、第５係数乗算器７６および制御部７３を備えて構成される。これら構成要素のうち、第１係数乗算器６１と第１加算器８３の組は、２点のデータを上記ステップａ或いはステップｂ（図４５）の方法で処理する２点演算部を構成する。その他、第２係数乗算器６２と第２加算器８４の組、第３係数乗算器６３と第３加算器８５の組、および第４係数乗算器６４と第４加算器８６の組も同様に２点演算部を構成している。また、これら２点演算部と出力先選択部７４とで中間データ算出手段が構成される。
【０１２６】
制御部７３は、画素クロック信号ＰＣＬＫと同期して動作する。データ・セレクタ６０は、この制御部７３から供給される選択制御信号ＳＥＬ０の値に応じて、リングメモリ３２ｓから取り込んだデータを第１端子Ｓ０〜第８端子Ｓ７の何れかから選択的に出力する。第１係数乗算器６１〜第４係数乗算器６４は、それぞれ、制御信号Ｃ０〜Ｃ３に従って入力データにリフティング係数α，β，γ，δを乗算する回路である。係数レジスタ６５，６７，６９，７１は、制御信号Ｃ０〜Ｃ３を受けて、リフティング係数α，β，γ，δをそれぞれ乗算器６６，６８，７０，７２に出力する。乗算器６６，６８，７０，７２は、それぞれ、データ・セレクタ６０から入力するデータにリフティング係数α，β，γ，δを乗算して出力する。第１加算器８３〜第４加算器８６は、それぞれ、第１係数乗算器６１〜第４係数乗算器６４から入力したデータと、データ・セレクタ６０の出力端子Ｓ１，Ｓ３，Ｓ５，Ｓ７から入力したデータとを加算して出力先選択部７４に出力する。
【０１２７】
出力先選択部７４は、制御部７３から供給される選択制御信号ＳＥＬ１の値に応じて、第１加算器８３〜第４加算器８６から並列に入力する４点のデータを第１端子Ｋ０〜第４端子Ｋ３から出力する。
【０１２８】
出力先選択部７４の第１端子Ｋ０から出力されたデータは、遅延レジスタ７５で画素クロック信号ＰＣＬＫの１クロック周期遅延した後に第５係数乗算器７６に入力する。第５係数乗算器７６では、制御部７３から供給される制御信号Ｃ４の値に応じて、規格化係数κ，１／κの何れか一方を乗算器７８に出力し、乗算器７８は、入力データにその規格化係数を乗算する規格化処理を１クロック周期内に実行する。これにより、第５係数乗算器７６は、低域成分或いは高域成分の出力データＹ（ｋ）を外部へ出力する。なお、遅延レジスタ７５と第５係数乗算器７６とで規格化手段が構成される。
【０１２９】
また、出力先選択部７４の第１端子Ｋ０から出力されたデータは分岐して外部のＭＭＵ３１にも出力される。また、第２端子Ｋ１〜第４端子Ｋ３から出力されたデータはそれぞれ外部のＭＭＵ３１に出力される。ＭＭＵ３１は、これら第１端子Ｋ０〜第４端子Ｋ３から外部へ出力されたデータをリングメモリ３２ｓに転送し記憶させることができる。
【０１３０】
次に、図２６に示すフィルタリング部３３ｓを用いたリフティング演算の代表例を、図２７〜図３２を参照しつつ以下に説明する。この格子図の演算は、図４４の場合と同様に行われる。なお、図２７〜図３２では、説明の便宜上、各格子点間を結ぶ線分に対応するリフティング係数α，β，γ，δと規格化係数κ，１／κとを表示していない。
【０１３１】
図２７は、Ｎ−１回目処理（Ｎ：整数）が終了した時点の格子図を示し、図２８〜図３２は、Ｎ回目〜Ｎ＋４回目の処理を模式的に示している。Ｎ回目処理（図２８）では、対象領域Ａ１，Ａ２，Ｂ１，Ｂ２の４個の変換処理が１クロック周期内に並列に同時実行される。対象領域Ａ１では、２点の中間データＳ１ｎ＋１，Ｄ１ｎ＋１を用いた上記ステップａ（図４５）の２点演算を実行して、奇数番目の入力データＸ（２ｎ＋３）を始点とする系列上の第２段階（最終段階）の一時データ（Ｄ２ｎ＋１）を算出する。ここで、中間データＳ１ｎ＋１は、中間データＤ１ｎ＋１の系列に対して１点前の系列上のデータである。また、対象領域Ａ２では、連続する２点の入力データＸ（２ｎ＋６），Ｘ（２ｎ＋７）を用いた上記ステップａの２点演算を実行して、奇数番目の入力データＸ（２ｎ＋７）を始点とする系列上の第１段階の一時データ（Ｄ１ｎ＋３）を算出する。また、対象領域Ｂ１では、Ｎ−１回目処理（図２７）の終了時に計算済みの一時データ（Ｓ２ｎ）と中間データＤ２ｎとを用いた上記ステップｂ（図４５）の２点演算を実行して、偶数番目の入力データＸ（２ｎ）を始点とする系列上の第２段階（最終段階）の中間データＳ２ｎを算出する。ここで、中間データＤ２ｎは、一時データ（Ｓ２ｎ）の系列に対して１点後の系列上のデータである。また、対象領域Ｂ２では、Ｎ−１回目処理（図２７）の終了時に計算済みの一時データ（Ｓ１ｎ＋２）と中間データＤ１ｎ＋２とを用いた上記ステップｂの２点演算を実行して、偶数番目の入力データＸ（２ｎ＋４）を始点とする系列上の第１段階の中間データＳ１ｎ＋２を算出する。また、対象領域Ｎ１において、最終段階の前記中間データＳ２ｎを算出した時から１クロック周期の後に、前記中間データＳ２ｎに規格化係数１／κを乗算する規格化処理を実行して、低域成分である偶数番目の出力データＹ（２ｎ）を算出する。
【０１３２】
このＮ回目の具体的な処理の内容は次の通りである。リングメモリ３２ｓは８ライン（系列）の記憶領域を備えている。ＭＭＵ３１は、このリングメモリ３２ｓに一時記憶された８点のデータＸ（２ｎ＋６），Ｘ（２ｎ＋７），Ｄ１ｎ＋２，（Ｓ１ｎ＋２），Ｓ１ｎ＋１，Ｄ１ｎ＋１，（Ｓ２ｎ），Ｄ２ｎをデータ・セレクタ６０に出力させる。データ・セレクタ６０は、制御部７３から供給される選択制御信号ＳＥＬ０の値に応じて、前記６点のデータのうち対象領域Ａ２内の２点の入力データＸ（２ｎ＋６），Ｘ（２ｎ＋７）を選択して第１端子Ｓ０と第２端子Ｓ１とに出力し、対象領域Ｂ２内の中間データＤ１ｎ＋２と一時データ（Ｓ１ｎ＋２）とを第３端子Ｓ２と第４端子Ｓ３とから出力し、対象領域Ａ１内の中間データＳ１ｎ＋１とＤ１ｎ＋１とを第５端子Ｓ４と第６端子Ｓ５とから出力し、対象領域Ｂ１内の中間データＤ２ｎと一時データ（Ｓ２ｎ）とを第７端子Ｓ６と第８端子Ｓ７とから出力する。
【０１３３】
第１係数乗算器６１において、係数レジスタ６５は、制御部７３から供給された制御信号Ｃ０に応じてリフティング係数αを乗算器６６に出力し、乗算器６６は、第１端子Ｓ０から入力したデータＸ（２ｎ＋６）にリフティング係数αを乗算して得たデータα×Ｘ（２ｎ＋６）を第１加算器８３に出力する。そして、第１加算器８３は、第１係数乗算器６１から入力したデータα×Ｘ（２ｎ＋６）と、データ・セレクタ６０の第２端子Ｓ１から入力したデータＸ（２ｎ＋７）とを加算することで対象領域Ａ２内の一時データ（Ｄ１ｎ＋３）を算出し、出力先選択部７４に出力する。
【０１３４】
また、第２係数乗算器６２では、係数レジスタ６７は、制御部７３から供給された制御信号Ｃ１に応じてリフティング係数βを乗算器６８に出力し、乗算器６８は、第３端子Ｓ２から入力した中間データＤ１ｎ＋２にリフティング係数βを乗算して得たデータβ×Ｄ１ｎ＋２を第２加算器８４に出力する。そして、第２加算器８４は、第２係数乗算器６２から入力したデータβ×Ｄ１ｎ＋２と、データ・セレクタ６０の第４端子Ｓ３から入力した一時データ（Ｓ１ｎ＋２）とを加算することで、対象領域Ｂ２内の中間データＳ１ｎ＋２を算出し、出力先選択部７４に出力する。
【０１３５】
また、第３係数乗算器６３では、係数レジスタ６９は、制御部７３から供給された制御信号Ｃ２に応じてリフティング係数γを乗算器７０に出力し、乗算器７０は、第５端子Ｓ４から入力した中間データＳ１ｎ＋１にリフティング係数γを乗算して得たデータγ×Ｓ１ｎ＋１を第３加算器８５に出力する。そして、第３加算器８５は、第３係数乗算器６３から入力したデータγ×Ｓ１ｎ＋１と、データ・セレクタ６０の第６端子Ｓ５から入力したデータＤ１ｎ＋１とを加算することで、対象領域Ａ１内の一時データ（Ｄ２ｎ＋１）を算出し、出力先選択部７４に出力する。
【０１３６】
また、第４係数乗算器６４では、係数レジスタ７１は、制御部７３から供給された制御信号Ｃ４に応じてリフティング係数δを乗算器７２に出力し、乗算器７２は、第７端子Ｓ６から入力した中間データＤ２ｎにリフティング係数δを乗算して得たデータδ×Ｄ２ｎを第４加算器８６に出力する。そして、第４加算器８６は、第４係数乗算器６４から入力したデータδ×Ｄ２ｎと、データ・セレクタ６０の第８端子Ｓ７から入力した一時データ（Ｓ２ｎ）とを加算することで、対象領域Ｂ１内の最終段階の中間データＳ２ｎを算出し、出力先選択部７４に出力する。
【０１３７】
出力先選択部１６は、制御部２１から供給された選択制御信号ＳＥＬ１の値に従って、第４加算器８６から入力した最終段階の中間データＳ２ｎを第１端子Ｋ０から出力する。第１端子Ｋ０から出力された中間データＳ２ｎは遅延レジスタ７５に入力して保持される。また、出力先選択部１６は、前記選択制御信号ＳＥＬ１に従って、第１加算器８３〜第３加算器８５から入力した３点のデータ（Ｄ１ｎ＋３），Ｓ１ｎ＋２，（Ｄ２ｎ＋１）を第２端子Ｋ１〜第４端子Ｋ３から外部のＭＭＵ２に出力する。ＭＭＵ２は、フィルタリング部３３ｓから外部に出力された４点のデータのうち３点のデータ（Ｄ１ｎ＋３），Ｓ１ｎ＋２，（Ｄ２ｎ＋１）をリングメモリ３２ｓに転送し、参照済みのＸ（２ｎ＋７）、（Ｓ１ｎ＋２）、Ｄ１ｎ＋１が格納されていた記憶領域に上書きさせる。
【０１３８】
また、出力先選択部７４の第１端子Ｋ０から出力された中間データＳ２ｎは、遅延レジスタ７５で１クロック周期遅延した後に第５係数乗算器７６に入力する。第５係数乗算器７６において、係数レジスタ７７は、制御部２１から供給された制御信号Ｃ４に従って、２個の規格化係数κ，１／κのうち規格化係数１／κを乗算器７８に出力し、乗算器７８は入力する中間データＳ２ｎに規格化係数１／κを乗算する。この結果、第５係数乗算器７６は、低域成分である偶数番目の出力データＹ（２ｎ）（＝（１／κ）×Ｓ２ｎ）を１クロック周期内に算出する。
【０１３９】
次に、Ｎ＋１回目処理（図２９）における対象領域Ａ３，Ａ４，Ｂ３，Ｂ４の４個の変換処理が、上記Ｎ回目処理（図２８）における対象領域Ｎ１の規格化処理とともに１クロック周期内に並列に同時実行される。対象領域Ａ３では、２点の中間データＤ２ｎ，Ｓ１ｎ＋１を用いた上記ステップａ（図４５）の２点演算を実行して、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の第２段階の一時データ（Ｓ２ｎ＋１）を算出する。ここで、中間データＤ２ｎは、中間データＳ１ｎ＋１の系列に対して１点前の系列上のデータである。また、対象領域Ａ４では、入力データＸ（２ｎ＋６）と中間データＤ１ｎ＋２とを用いた上記ステップａの２点演算を実行して、偶数番目の入力データ（２ｎ＋６）を始点とする系列上の第１段階の一時データ（Ｓ１ｎ＋３）を算出する。また、対象領域Ｂ３では、上記Ｎ回目処理（図２８）で算出した一時データ（Ｄ２ｎ＋１）と中間データＳ１ｎ＋２とを用いた上記ステップｂ（図４５）の２点演算を実行して、奇数番目の入力データＸ（２ｎ＋３）を始点とする系列上の最終段階（第２段階）の中間データＤ２ｎ＋１を算出する。また、対象領域Ｂ４では、上記Ｎ回目処理で算出した一時データ（Ｄ１ｎ＋３）と入力データＸ（２ｎ＋８）とを用いた上記ステップｂの２点演算を実行して、奇数番目の入力データＸ（２ｎ＋７）を始点とする系列上の第１段階の中間データＤ１ｎ＋３を算出する。また、対象領域Ｎ２においては、最終段階の前記中間データＤ２ｎ＋１を算出した時から１クロック周期の後に、前記中間データＤ２ｎ＋１に規格化係数κを乗算する規格化処理を実行して、高域成分である奇数番目の出力データＹ（２ｎ＋３）を算出する。
【０１４０】
このＮ＋１回目の具体的な処理の内容は次の通りである。ＭＭＵ３１は、リングメモリ３２ｓに一時記憶された８点のデータＸ（２ｎ＋８），（Ｄ１ｎ＋３），Ｄ１ｎ＋２，Ｘ（２ｎ＋６），Ｓ１ｎ＋２，（Ｄ２ｎ＋１），Ｄ２ｎ，Ｓ１ｎ＋１をデータ・セレクタ６０に出力させる。データ・セレクタ６０は、制御部７３から供給された選択制御信号ＳＥＬ０の値に応じて、前記８点のデータのうち対象領域Ｂ４内の２点のデータＸ（２ｎ＋８），（Ｄ１ｎ＋３）を第１端子Ｓ０と第２端子Ｓ１とから出力し、対象領域Ａ４内の２点のデータＸ（２ｎ＋６），Ｄ１ｎ＋２を第３端子Ｓ２と第４端子Ｓ３とから出力し、対象領域Ｂ３内の２点のデータＳ１ｎ＋２，（Ｄ２ｎ＋１）を第５端子Ｓ４と第６端子Ｓ５とから出力し、対象領域Ａ３内の２点のデータＤ２ｎ，Ｓ１ｎ＋１を第７端子Ｓ６と第８端子Ｓ７とから出力する。
【０１４１】
第１係数乗算器６１では、係数レジスタ６５は、制御部７３から供給された制御信号Ｃ０に応じてリフティング係数αを乗算器６６に出力し、乗算器６６は、第１端子Ｓ０から入力したデータＸ（２ｎ＋８）にリフティング係数αを乗算して得たデータα×Ｘ（２ｎ＋８）を第１加算器８３に出力する。そして、第１加算器８３は、第１係数乗算器６１から入力したデータα×Ｘ（２ｎ＋８）と、データ・セレクタ６０の第２端子Ｓ１から入力した一時データＤ１ｎ＋３とを加算することで対象領域Ｂ４内の中間データＤ１ｎ＋３を算出し、出力先選択部７４に出力する。
【０１４２】
また、第２係数乗算器６２では、係数レジスタ６７は、制御部７３から供給された制御信号Ｃ１に応じてリフティング係数βを乗算器６８に出力し、乗算器６８は、第３端子Ｓ２から入力した中間データＤ１ｎ＋２にリフティング係数βを乗算して得たデータβ×Ｄ１ｎ＋２を第２加算器８４に出力する。そして、第２加算器８４は、第２係数乗算器６２から入力したデータβ×Ｄ１ｎ＋２と、データ・セレクタ６０の第４端子Ｓ３から入力した入力データＸ（２ｎ＋６）とを加算することで、対象領域Ａ４内の一時データ（Ｓ１ｎ＋３）を算出し、出力先選択部７４に出力する。
【０１４３】
また、第３係数乗算器６３では、係数レジスタ６９は、制御部７３から供給された制御信号Ｃ２に応じてリフティング係数γを乗算器７０に出力し、乗算器７０は、第５端子Ｓ４から入力した中間データＳ１ｎ＋２にリフティング係数γを乗算して得たデータγ×Ｓ１ｎ＋２を第３加算器８５に出力する。そして、第３加算器８５は、第３係数乗算器６３から入力したデータγ×Ｓ１ｎ＋２と、データ・セレクタ６０の第６端子Ｓ５から入力した一時データ（Ｄ２ｎ＋１）とを加算することで、対象領域Ｂ３内の中間データＤ２ｎ＋１を算出し、出力先選択部７４に出力する。
【０１４４】
また、第４係数乗算器６４では、係数レジスタ７１は、制御部７３から供給された制御信号Ｃ４に応じてリフティング係数δを乗算器７２に出力し、乗算器７２は、第７端子Ｓ６から入力した中間データＤ２ｎにリフティング係数δを乗算して得たデータδ×Ｄ２ｎを第４加算器８６に出力する。そして、第４加算器８６は、第４係数乗算器６４から入力したデータδ×Ｄ２ｎと、データ・セレクタ６０の第８端子Ｓ７から入力した中間データＳ１ｎ＋１とを加算することで、対象領域Ａ３内の最終段階の中間データ（Ｓ２ｎ＋１）を算出し、出力先選択部７４に出力する。
【０１４５】
出力先選択部７４は、制御部７３から供給された選択制御信号ＳＥＬ１の値に従って、第３加算器８５から入力した最終段階の中間データＤ２ｎ＋１を第１端子Ｋ０から出力する。第１端子Ｋ０から出力された中間データＤ２ｎ＋１は遅延レジスタ７５に入力して保持される一方、外部のＭＭＵ２にも出力される。また、出力先選択部１６は、前記選択制御信号ＳＥＬ１に従って、第１加算器８３〜第４加算器８６から入力した３点のデータＤ１ｎ＋３，（Ｓ１ｎ＋３），（Ｓ２ｎ＋１）を第２端子Ｋ１，第３端子Ｋ２および第４端子Ｋ３から外部のＭＭＵ２に出力する。ＭＭＵ２は、フィルタリング部３３ｓから外部に出力された４点のデータＤ１ｎ＋３，（Ｓ１ｎ＋３），Ｄ２ｎ＋１，（Ｓ２ｎ＋１）をリングメモリ３２ｓに転送し、参照済みのデータＸ（２ｎ＋７），Ｘ（２ｎ＋６），Ｄ１ｎ＋１，Ｓ１ｎ＋１が格納されていた記憶領域に上書きさせる。
【０１４６】
また、出力先選択部７４の第１端子Ｋ０から出力された中間データＤ２ｎ＋１は、遅延レジスタ７５で１クロック周期遅延した後に第５係数乗算器７６に入力する。第５係数乗算器７６において、係数レジスタ７７は、制御部７３から供給された制御信号Ｃ４に従って、２個の規格化係数κ，１／κのうち規格化係数κを乗算器７８に出力し、乗算器７８は入力する中間データＤ２ｎ＋１に規格化係数κを乗算する。この結果、第５係数乗算器７６は、高域成分である奇数番目の出力データＹ（２ｎ＋３）（＝κ×Ｄ２ｎ＋１）を１クロック周期内に算出する。
【０１４７】
次に、Ｎ＋２回目処理（図３０）における対象領域Ａ６，Ｂ６，Ａ５，Ｂ５の４個の変換処理が、上記Ｎ＋１回目処理（図２９）における対象領域Ｎ２の規格化処理とともに１クロック周期内に並列に同時実行される。また、１クロック周期の後に、対象領域Ｎ３において、対象領域Ｎ３の規格化処理が実行される。対象領域Ａ６，Ｂ６，Ａ５，Ｂ５，Ｎ３は、それぞれ、上記Ｎ回目処理（図２８）の対象領域Ａ２，Ｂ２，Ａ１，Ｂ１，Ｎ１を２系列（２点）後方に移動した領域である。これら対象領域Ａ６，Ｂ６，Ａ５，Ｂ５，Ｎ３では、それぞれ、対象領域Ａ２，Ｂ２，Ａ１，Ｂ１，Ｎ１における処理と同様の処理が実行される。この結果として、対象領域Ａ６では一時データ（Ｄ１ｎ＋４）が、対象領域Ｂ６では中間データＳ１ｎ＋３が、対象領域Ａ５では一時データ（Ｄ２ｎ＋２）が、対象領域Ｂ５では中間データＳ２ｎ＋１が、対象領域Ｎ３では偶数番目の出力データＹ（２ｎ＋２）がそれぞれ算出される。
【０１４８】
次に、Ｎ＋３回目処理（図３１）における対象領域Ｂ８，Ａ８，Ｂ７，Ａ７の４個の変換処理が、上記Ｎ＋２回目処理における対象領域Ｎ３の規格化処理とともに１クロック周期内に並列に同時実行される。対象領域Ｂ８，Ａ８，Ｂ７，Ａ７，Ｎ４は、それぞれ、上記Ｎ＋１回目処理（図２９）の対象領域Ｂ４，Ａ４，Ｂ３，Ａ３，Ｎ２を２系列（２点）後方に移動した領域である。これら対象領域Ｂ８，Ａ８，Ｂ７，Ａ７，Ｎ４では、それぞれ、対象領域Ｂ４，Ａ４，Ｂ３，Ａ３，Ｎ２における処理と同様の処理が実行される。この結果として、対象領域Ｂ８では中間データＤ１ｎ＋４が、対象領域Ａ８では一時データ（Ｓ１ｎ＋４）が、対象領域Ｂ７では中間データＤ２ｎ＋２が、対象領域Ａ７では一時データ（Ｓ２ｎ＋２）が、対象領域Ｎ４では奇数番目の出力データＹ（２ｎ＋５）がそれぞれ算出される。
【０１４９】
次に、Ｎ＋４回目処理（図３２）では、対象領域Ａ１０，Ｂ１０，Ａ９，Ｂ９の４個の変換処理と対象領域Ｎ５の規格化処理とが実行される。対象領域Ａ１０，Ｂ１０，Ａ９，Ｂ９，Ｎ５は、上記Ｎ＋２回目処理（図３０）の対象領域Ａ６，Ｂ６，Ａ５，Ｂ５，Ｎ３を２系列（２点）後方に移動した領域である。これら対象領域では、上記Ｎ回目処理（図２８）と同様の処理が実行されるため、その詳細な説明を省略する。
【０１５０】
以上のように、上記Ｎ回目処理（図２８）および上記Ｎ＋１回目処理（図２９）と同様の処理が、全ての出力データが算出されるまで対象領域を移動させつつ繰り返し実行される。これにより、偶数番目或いは奇数番目の１点の出力データを算出するのに要する平均周期を１クロック周期とすることができ、出力データの算出周期を大幅に短縮化できる。
【０１５１】
本実施形態に係るウェーブレット変換装置は、図２６に示す構成を有する垂直フィルタリング部と水平フィルタリング部とを備えるため、上記第２の実施形態の場合と同じラインベースの２次元ＤＷＴ処理を実行することが可能である。したがって、ウェーブレット変換を極めて短時間で高速に行うことが可能である。また、上記したフィルタリング部３３ｓは１点のデータを出力するのに平均して１クロック周期しか要しないため、上記第１の実施形態に係るウェーブレット変換装置１のようにラインバッファ回路５を必要としない。したがって、小回路規模で、低消費電力で動作する廉価なウェーブレット変換装置の実現が可能である。
【０１５２】
＜変形例＞
図３３は、上記した第２および第３の実施形態の変形例に係る２次元ウェーブレット変換装置８０の概略構成を示す図である。このウェーブレット変換装置８０は、画素単位で入力する２次元画像データｘ（ｎ）を一時的に保持するバッファ８１、外部供給のクロック信号ＣＬＫと同期して動作するＭＭＵ（メモリ管理部）８２、第１リングメモリ３、垂直フィルタリング部４、第２リングメモリ３２または３２ｓ、水平フィルタリング部３３または３３ｓを備えて構成されている。
【０１５３】
ここで、第１リングメモリ３と垂直フィルタリング部４とＭＭＵ８２は、上記第１の実施形態に係るリングメモリ３とフィルタリング部４とＭＭＵ２（図２）と同じ構成を有する。よって、本変形例の第１リングメモリ３と垂直フィルタリング部４は４クロック周期で１点の出力データを算出できる。
【０１５４】
また、第２リングメモリ３２または３２ｓと水平フィルタリング部３３または３３ｓとＭＭＵ８２は、上記第２の実施形態に係るリングメモリ３２とフィルタリング部３３とＭＭＵ３１（図１８）、若しくは上記第３の実施形態に係るリングメモリ３２ｓとフィルタリング部３３ｓとＭＭＵ３１（図２６）と同じ構成を有する。よって、本変形例の第２リングメモリ３２または３２ｓと水平フィルタリング部３３または３３ｓは１クロック周期で１点の出力データを算出できる。
【０１５５】
このように、第２リングメモリ３２または３２ｓと水平フィルタリング部３３または３３ｓは１点の出力データを平均して１クロック周期で算出できるため、上記第１の実施形態に係るウェーブレット変換装置１（図１）のようにラインバッファ回路５を必要としない。したがって、メモリ使用量が少ない、小回路規模で低廉なウェーブレット変換装置の実現が可能となる。
【０１５６】
なお、本変形例では、第１リングメモリ１と垂直フィルタリング部４として第１の実施形態に係る構成を採用したが、この代わりに、平均５クロック周期で１点の出力データを算出する構成を採用した場合も、ラインバッファ回路５を必要としない観点から好ましい。
【０１５７】
＜第４の実施形態＞
次に、本発明の第４の実施形態に係るウェーブレット変換装置およびウェーブレット変換方法について説明する。図３４は、第４の実施形態に係るウェーブレット変換装置９０の概略構成を示す図である。このウェーブレット変換装置９０は、画素単位で入力する２次元画像データｘ（ｎ）（ｎは整数）を一時的に保持するバッファ９１、外部供給のクロック信号ＣＬＫと同期して動作するＭＭＵ（メモリ管理部）９２、第１リングメモリ９３、垂直フィルタリング部９４、第２リングメモリ３２Ｈ、第１水平フィルタリング部３３Ｈ、第３リングメモリ３２Ｌおよび第２水平フィルタリング部３３Ｌを備えて構成されている。ここで、第１リングメモリ９３、垂直フィルタリング部９４、第２リングメモリ３２Ｈ、第１水平フィルタリング部３３Ｈ、第３リングメモリ３２Ｌおよび第２水平フィルタリング部３３Ｌは、外部供給の画素クロック信号ＰＣＬＫと同期して動作する。
【０１５８】
本実施形態では、ＭＭＵ９２、垂直フィルタリング部９４、第１水平フィルタリング部３３Ｈおよび第２水平フィルタリング部３３Ｌはハードウェアで構成されるが、この代わりに、マイクロプロセッサで実行する命令群を含むコンピュータ・プログラムで構成されてもよい。
【０１５９】
このウェーブレット変換装置９０は、２次元画像データにラインベースの２次元ＤＷＴを１回施す機能を有している。垂直フィルタリング部９４と第１水平フィルタリング部３３Ｈとは、第２リングメモリ３２Ｈを介して直列に接続されており、垂直フィルタリング部９４と第２水平フィルタリング部３３Ｌとは第３リングメモリ３２Ｌを介して直列に接続されている。
【０１６０】
ＭＭＵ９２は、バッファ９１、第１リングメモリ９３、第２リングメモリ３２Ｈおよび第３リングメモリ３２Ｌのデータ入出力を制御する機能を有しており、バッファ９１から読出した２次元画像データを第１リングメモリ９３に転送し記憶させることができる。垂直フィルタリング部９４は、第１リングメモリ９３から入力したデータに対して２次元画像の垂直方向にフィルタリングを実行することで、画素クロック信号ＰＣＬＫの１クロック周期で、その垂直方向の高域成分と同方向の低域成分とをそれぞれ１点ずつ算出できる。よって、２点の出力データを算出するのに要する平均周期は１クロック周期である。よって、垂直フィルタリング部９４は、垂直方向の高域成分のデータＹＨ（ｋ）と垂直方向の低域成分のデータＹＬ（ｋ）とをそれぞれ第２リングメモリ３２Ｈと第３リングメモリ３２Ｌとに出力する。
【０１６１】
第１水平フィルタリング部３３Ｈと第２水平フィルタリング部３３Ｌは、ＭＭＵ９２と連携して動作し、それぞれ、入力データＹＨ（ｋ）とＹＬ（ｋ）とを１点当たり１クロック周期でフィルタリングして、水平方向の高域成分と低域成分のデータを出力する。これら第１水平フィルタリング部３３Ｈと第２水平フィルタリング部３３Ｌとしては、上記第２または第３の実施形態に係るフィルタリング部３３または３３ｓと同じ構成を採用すればよい。
【０１６２】
図３５に、本実施形態に係る垂直フィルタリング部９４の概略構成を示す。この垂直フィルタリング部９４は、入力データを選択的に取り込むデータ・セレクタ９５、加算器１２０，１２１，１２２，１２３、第１〜第４係数乗算器９６〜９９、出力先選択部（ＤＭＵＸ）１０９、第１および第２遅延レジスタ１１０，１１４、第５および第６係数乗算器１１１，１１５および制御部１０８を備えて構成される。これら構成要素のうち、２個の加算器１２０，１２４と第１係数乗算器９６からなる組は３点のデータを１クロック周期内に処理するため、３点演算部を構成する。また、２個の加算器１２１，１２５と第２係数乗算器９７からなる組、２個の加算器１２２，１２６と第３係数乗算器９８からなる組、および２個の加算器１２３，１２７と第４係数乗算器９９からなる組も、それぞれ、３点のデータを１クロック周期内に処理するため、３点演算部を構成する。また、これら４組の３点演算部と出力先選択部１０９とで中間データ算出手段が構成される。
【０１６３】
制御部１０８は、画素クロック信号ＰＣＬＫと同期して動作する。データ・セレクタ９５は、この制御部１０８から供給される選択制御信号ＳＥＬ０の値に応じて、第１リングメモリ９３から取り込んだデータを第１端子Ｓ０〜第１２端子Ｓ１１の何れかから選択的に出力する。
【０１６４】
また、４組の３点演算部は並列に処理を実行する。前段の第１の加算器１２０は、データ・セレクタ９５の第１端子Ｓ０と第２端子Ｓ１とから出力された２点のデータを加算して第１係数乗算器９６に出力する。第１係数乗算器９６では、係数レジスタ１００は、制御部１０８から供給される制御信号Ｃ０に応じて、リフティング係数αを乗算器１０１に出力し、乗算器１０１は、加算器１２０から入力したデータにリフティング係数αを乗算して後段の加算器１２４に出力する。そして、後段の加算器１２４は、第１係数乗算器９６から入力したデータと、データ・セレクタ９５の第３端子Ｓ２から入力したデータとを加算して出力先選択部１０９に出力する。
【０１６５】
また、前段の第２の加算器１２１は、データ・セレクタ９５の第４端子Ｓ３と第５端子Ｓ４とから出力された２点のデータを加算して第２係数乗算器９７に出力する。第２係数乗算器９７では、係数レジスタ１０２は、制御部１０８から供給される制御信号Ｃ１に応じて、リフティング係数βを乗算器１０３に出力し、乗算器１０３は、加算器１２１から入力したデータにリフティング係数βを乗算して後段の加算器１２５に出力する。後段の加算器１２５は、第２係数乗算器９７から入力したデータと、データ・セレクタ９５の第６端子Ｓ５から入力したデータとを加算して出力先選択部１０９に出力する。
【０１６６】
また、前段の第３の加算器１２２は、データ・セレクタ９５の第７端子Ｓ６と第８端子Ｓ７とから出力された２点のデータを加算して第３係数乗算器９８に出力する。第３係数乗算器９８では、係数レジスタ１０４は、制御部１０８から供給される制御信号Ｃ２に応じて、リフティング係数γを乗算器１０５に出力し、乗算器１０５は、加算器１２２から入力したデータにリフティング係数γを乗算して後段の加算器１２６に出力する。後段の加算器１２６は、第３係数乗算器９８から入力したデータと、データ・セレクタ９５の第９端子Ｓ８から入力したデータとを加算して出力先選択部１０９に出力する。
【０１６７】
そして、前段の第４の加算器１２３は、データ・セレクタ９５の第１０端子Ｓ９と第１１端子Ｓ１０とから出力された２点のデータを加算して第４係数乗算器９９に出力する。第４係数乗算器９９では、係数レジスタ１０６は、制御部１０８から供給される制御信号Ｃ３に応じて、リフティング係数δを乗算器１０７に出力し、乗算器１０７は、加算器１２３から入力したデータにリフティング係数δを乗算して後段の加算器１２７に出力する。後段の加算器１２７は、第４係数乗算器９９から入力したデータと、データ・セレクタ９５の第１２端子Ｓ１１から入力したデータとを加算して出力先選択部１０９に出力する。
【０１６８】
出力先選択部１０９は、制御部１０８から供給される選択制御信号ＳＥＬ１の値に応じて、後段の第１〜第４の加算器１２４〜１２７から並列に入力する４点のデータを第１端子Ｋ０〜第４端子Ｋ３の何れかから選択的に出力する。
【０１６９】
出力先選択部１０９の第１端子Ｋ０と第２端子Ｋ１から出力されたデータは、それぞれ、第１遅延レジスタ１１０と第２遅延レジスタ１１４とに入力し、画素クロック信号ＰＣＬＫの１クロック周期遅延した後に、第５係数乗算器１１１と第６係数乗算器１１５とに入力する。第５係数乗算器１１１では、係数レジスタ１１２は、制御部１０８から供給される制御信号Ｃ４に応じて、第１規格化係数κを乗算器１１３に出力し、乗算器１１３は、入力データに第１規格化係数κを乗算することで高域成分の出力データＹＨ（ｋ）を算出する。また、第６係数乗算器１１５では、係数レジスタ１１６は、制御部１０８から供給される制御信号Ｃ５に応じて、第２規格化係数１／κを乗算器１１７に出力し、乗算器１１７は、入力データに第２規格化係数１／κを乗算することで低域成分の出力データＹＬ（ｋ）を算出する。なお、第１遅延レジスタ１１０と第５係数乗算器１１１の組、第２遅延レジスタ１１４と第６係数乗算器１１５の組で、それぞれ、本発明の規格化手段が構成される。
【０１７０】
また、出力先選択部１０９の第１端子Ｋ０〜第４端子Ｋ３から出力されたデータは外部のＭＭＵ９２にも出力される。ＭＭＵ９２は、第１端子Ｋ０〜第４端子Ｋ３から出力されたデータを第１リングメモリ９３に転送し記憶させることができる。
【０１７１】
次に、以上の垂直フィルタリング部９４を用いたリフティング演算の代表例を、図３６〜図３８を参照しつつ以下に説明する。図３６〜図３８は、９×７タップのＤａｕｂｅｃｈｉｅｓフィルタのリフティング構成を模式的に示す格子図である。この格子図の演算は、図４４の場合と同様に行われる。なお、図３６〜図３８は、説明の便宜上、各格子点間を結ぶ線分に対応するリフティング係数α，β，γ，δと規格化係数κ，１／κとを表示していない。
【０１７２】
図３６〜図３８は、本実施形態でのＮ−１回目（Ｎは整数）〜Ｎ＋２回目の処理を模式的に示している。図３６は、Ｎ−１回目処理が終了した状態を示している。
【０１７３】
Ｎ回目処理（図３７）では、対象領域Ｄ１，Ｄ２，Ｄ３，Ｄ４の４個の変換処理が１クロック周期内に並列に同時実行される。対象領域Ｄ１では、偶数番目の２点の入力データＸ（２ｎ＋１０），Ｘ（２ｎ＋１２）を加算したデータにリフティング係数αを乗算することで乗算値を算出した後、この乗算値と奇数番目の入力データＸ（２ｎ＋１１）とを加算するという３点演算が実行される。この結果、入力データＸ（２ｎ＋１１）を始点とする系列上の第１段階の中間データＤ１ｎ＋５が算出される。ここで、偶数番目の２点の入力データＸ（２ｎ＋１０），Ｘ（２ｎ＋１２）は、前記入力データＸ（２ｎ＋１１）に対して１点前後するデータである。また、対象領域Ｄ２では、２点の中間データＤ１ｎ＋３，Ｄ１ｎ＋４を加算したデータにリフティング係数βを乗算することで乗算値を算出した後、この乗算値と偶数番目の入力データＸ（２ｎ＋８）とを加算するという３点演算が実行される。この結果、前記入力データＸ（２ｎ＋８）を始点とする系列上の第１段階の中間データＳ１ｎ＋４が算出される。また、対象領域Ｄ３では、２点の中間データＳ１ｎ＋２，Ｓ１ｎ＋３を加算したデータにリフティング係数γを乗算した後、この乗算値と中間データＤ１ｎ＋２とを加算するという３点演算が実行される。この結果、奇数番目の入力データＸ（２ｎ＋５）を始点とする系列上の第２段階（最終段階）の中間データＤ２ｎ＋２が算出される。ここで、２点の中間データＳ１ｎ＋２，Ｓ１ｎ＋３は、中間データＤ１ｎ＋２の系列に対して１点前後する系列上のデータである。また、対象領域Ｄ４では、２点の中間データＤ２ｎ，Ｄ２ｎ＋１を加算したデータにリフティング係数δを乗算することで乗算値を算出した後、この乗算値と中間データＳ１ｎ＋１とを加算するという３点演算が実行される。この結果、偶数番目の入力データＸ（２ｎ＋２）を始点とする系列上の第２段階（最終段階）の中間データＳ２ｎ＋１が算出される。
【０１７４】
また、対象領域Ｎ１においては、最終段階の前記中間データＳ２ｎ＋１を算出した時から１クロック周期の後に、前記中間データＳ２ｎ＋１に規格化係数１／κを乗算する規格化処理を実行して、低域成分である偶数番目の出力データＹ（２ｎ＋２）を算出する。更に、対象領域Ｎ２においては、最終段階の前記中間データＤ２ｎ＋２を算出した時から１クロック周期の後に、前記中間データＤ２ｎ＋２に規格化係数κを乗算する規格化処理を実行して、高域成分である奇数番目の出力データＹ（２ｎ＋５）を算出する。
【０１７５】
このＮ回目の具体的な処理の内容は次の通りである。ＭＭＵ９２は、リングメモリ９３に一時記憶された１２点のデータＸ（２ｎ＋１０），Ｘ（２ｎ＋１１），Ｘ（２ｎ＋１２），Ｄ１ｎ＋３，Ｘ（２ｎ＋８），Ｄ１ｎ＋４，Ｓ１ｎ＋２，Ｄ１ｎ＋２，Ｓ１ｎ＋３，Ｄ２ｎ，Ｓ１ｎ＋１，Ｄ２ｎ＋１をデータ・セレクタ９５に出力させる。データ・セレクタ９５は、制御部１０８から供給された選択制御信号ＳＥＬ０の値に応じて、前記１２点のデータの中から、対象領域Ｄ１内の３点の入力データＸ（２ｎ＋１０），Ｘ（２ｎ＋１１），Ｘ（２ｎ＋１２）を選択して第１端子Ｓ０〜第３端子Ｓ２から出力し、対象領域Ｄ２内の３点のデータＤ１ｎ＋３，Ｘ（２ｎ＋８），Ｄ１ｎ＋４を選択して第４端子Ｓ３〜第６端子Ｓ５から出力し、対象領域Ｄ３内の３点のデータＳ１ｎ＋２，Ｄ１ｎ＋２，Ｓ１ｎ＋３を選択して第７端子Ｓ６〜第９端子Ｓ８から出力し、対象領域Ｄ４内の３点のデータＤ２ｎ，Ｓ１ｎ＋１，Ｄ２ｎ＋１を選択して第１０端子Ｓ９〜第１２端子Ｓ１１から出力する。
【０１７６】
前段の第１の加算器１２０は、データ・セレクタ９５の第１端子Ｓ０と第２端子Ｓ１から入力した対象領域Ｄ１内の２点のデータＸ（２ｎ＋１０），Ｘ（２ｎ＋１２）を加算したデータを第１係数乗算器９６に出力する。第１係数乗算器９６では、係数レジスタ１００は制御信号Ｃ０に従ってリフティング係数αを乗算器１０１に供給し、乗算器１０１は、入力データとリフティング係数αとを乗算した乗算値（＝α×（Ｘ（２ｎ＋１０）＋Ｘ（２ｎ＋１２）））を後段の加算器１２４に出力する。そして、後段の加算器１２４は、第１係数乗算器９６から入力する乗算値と、データ・セレクタ９５の第３端子Ｓ２から入力したデータＸ（２ｎ＋１１）とを加算することで、対象領域Ｄ１内の中間データＤ１ｎ＋５を算出し、出力先選択部１０９に出力する。
【０１７７】
また、前段の第２の加算器１２１は、データ・セレクタ９５の第４端子Ｓ３と第５端子Ｓ４から入力した対象領域Ｄ２内の２点のデータＤ１ｎ＋３，Ｄ１ｎ＋４を加算したデータを第２係数乗算器９７に出力する。第２係数乗算器９７では、係数レジスタ１０２は制御信号Ｃ１に従ってリフティング係数βを乗算器１０３に供給し、乗算器１０３は、入力データとリフティング係数βとを乗算した乗算値（＝β×（Ｄ１ｎ＋３＋Ｄ１ｎ＋４））を後段の加算器１２５に出力する。そして、後段の加算器１２５は、第２係数乗算器９７から入力する乗算値と、データ・セレクタ９５の第６端子Ｓ５から入力したデータＸ（２ｎ＋８）とを加算することで、対象領域Ｄ２内の中間データＳ１ｎ＋４を算出し、出力先選択部１０９に出力する。
【０１７８】
また、前段の第３の加算器１２２は、データ・セレクタ９５の第７端子Ｓ６と第８端子Ｓ７から入力した対象領域Ｄ３内の２点のデータＳ１ｎ＋２，Ｓ１ｎ＋３を加算したデータを第３係数乗算器９８に出力する。第３係数乗算器９８では、係数レジスタ１０４は制御信号Ｃ２に従ってリフティング係数γを乗算器１０５に供給し、乗算器１０５は、入力データとリフティング係数γとを乗算した乗算値（＝γ×（Ｓ１ｎ＋２＋Ｓ１ｎ＋３））を後段の加算器１２６に出力する。そして、後段の加算器１２６は、第３係数乗算器９８から入力する乗算値と、データ・セレクタ９５の第９端子Ｓ８から入力したデータＤ１ｎ＋２とを加算することで、対象領域Ｄ３内の中間データＤ２ｎ＋２を算出し、出力先選択部１０９に出力する。
【０１７９】
また、前段の第４の加算器１２３は、データ・セレクタ９５の第１０端子Ｓ９と第１１端子Ｓ１０から入力した対象領域Ｄ４内の２点のデータＤ２ｎ，Ｄ２ｎ＋１を加算したデータを第４係数乗算器９９に出力する。第４係数乗算器９９では、係数レジスタ１０６は制御信号Ｃ３に従ってリフティング係数δを乗算器１０７に供給し、乗算器１０７は、入力データとリフティング係数δとを乗算した乗算値（＝δ×（Ｄ２ｎ＋Ｄ２ｎ＋１））を後段の加算器１２７に出力する。そして、後段の加算器１２７は、第４係数乗算器９９から入力する乗算値と、データ・セレクタ９５の第１２端子Ｓ１１から入力した中間データＳ１ｎ＋１とを加算することで、対象領域Ｄ４内の中間データＳ２ｎ＋１を算出し、出力先選択部１０９に出力する。
【０１８０】
出力先選択部１０９は、選択制御信号ＳＥＬ１の値に従って、後段の第１および第２の加算器１２４，１２５から入力した２点の中間データＤ１ｎ＋５，Ｓ１ｎ＋４を第３端子Ｋ２と第４端子Ｋ３とから外部のＭＭＵ９２へ出力すると同時に、後段の第３の加算器１２６から入力した中間データＤ２ｎ＋２を第１端子Ｋ０から出力し、後段の第４の加算器１２７から入力した中間データＳ２ｎ＋１を第２端子Ｋ１から出力する。第１端子Ｋ０から出力された最終段階の中間データＤ２ｎ＋２は、外部のＭＭＵ９２に出力されると共に、第１遅延レジスタ１１０で１クロック周期遅延した後に第５係数乗算器１１１に入力する。また、第２端子Ｋ１から出力された中間データＳ２ｎ＋１は、第２遅延レジスタ１１４で１クロック周期遅延した後に第６係数乗算器１１５に入力する。ＭＭＵ９２は、外部へ出力された中間データＤ１ｎ＋５，Ｓ１ｎ＋４，Ｄ２ｎ＋２をリングメモリ９３に転送し、参照済みのデータＸ（２ｎ＋１１），Ｘ（２ｎ＋８），Ｄ１ｎ＋２が格納されていた記憶領域に上書きさせる。
【０１８１】
また、出力先選択部１０９の第１端子Ｋ０から出力された中間データＤ２ｎ＋２は、第１遅延レジスタ１１０で１クロック周期遅延した後に第５係数乗算器１１１に入力する。第５係数乗算器１１１において、係数レジスタ１１２は、制御部２１から供給された制御信号Ｃ４に従って規格化係数κを乗算器１１３に出力し、乗算器１１３は入力する中間データＤ２ｎ＋２に規格化係数κを乗算する。この結果、第５係数乗算器１１１は、高域成分である奇数番目の出力データＹ（２ｎ＋５）（＝κ×Ｄ２ｎ＋２）を１クロック周期内に算出する。
【０１８２】
また、出力先選択部１０９の第２端子Ｋ１から出力された中間データＳ２ｎ＋１は、第２遅延レジスタ１１４で１クロック周期遅延した後に第６係数乗算器１１５に入力する。第６係数乗算器１１５において、係数レジスタ１１６は、制御部２１から供給された制御信号Ｃ５に従って規格化係数１／κを乗算器１１７に出力し、乗算器１１７は入力する中間データＳ２ｎ＋１に規格化係数１／κを乗算する。この結果、第６係数乗算器１１５は、低域成分である偶数番目の出力データＹ（２ｎ＋２）（＝（１／κ）×Ｓ２ｎ＋１）を１クロック周期内に算出する。
【０１８３】
次のＮ＋１回目処理（図３８）では、対象領域Ｄ５，Ｄ６，Ｄ７，Ｄ８の変換処理と対象領域Ｎ３，Ｎ４の２個の規格化処理とが実行される。対象領域Ｄ５，Ｄ６，Ｄ７，Ｄ８，Ｎ３，Ｎ４は、上記Ｎ回目処理（図３７）の対象領域Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｎ１，Ｎ２を２系列（２点）後方に移動した領域である。これら対象領域Ｄ５，Ｄ６，Ｄ７，Ｄ８，Ｎ３，Ｎ４では、それぞれ、対象領域Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｎ１，Ｎ２での処理と同様の処理が実行される。したがって、対象領域Ｄ５では、奇数番目の入力データＸ（２ｎ＋１３）を始点とする系列上の第１段階の中間データＤ１ｎ＋６が算出され、対象領域Ｄ６では、偶数番目の入力データＸ（２ｎ＋１０）を始点とする系列上の第１段階の中間データＳ１ｎ＋５が算出され、対象領域Ｄ７では、奇数番目の入力データＸ（２ｎ＋７）を始点とする系列上の第２段階（最終段階）の中間データＤ２ｎ＋３が算出され、対象領域Ｄ８では、偶数番目の入力データＸ（２ｎ＋４）を始点とする系列上の第２段階（最終段階）の中間データＳ２ｎ＋２が算出される。また、１クロック周期の後に、対象領域Ｎ３では、低域成分である偶数番目の出力データＹ（２ｎ＋２）が算出され、対象領域Ｎ４では、高域成分である奇数番目の出力データＹ（２ｎ＋７）が算出される。
【０１８４】
以上のように、上記Ｎ回目処理（図３７）と同様の処理が、全ての点の出力データが算出されるまで対象領域を移動させつつ繰り返し実行される。これにより、偶数番目および奇数番目の２点の出力データを算出するのに要する平均周期を１クロック周期とすることができ、出力データの算出周期を大幅に短縮化できる。
【０１８５】
次に、上記ウェーブレット変換装置９０を用いたラインベースの２次元ＤＷＴ処理を以下に説明する。
【０１８６】
垂直フィルタリング部９４に入力するデータは、図１２と図１３に示したように水平画素数Ｗの矩形状の画像データ２３とする。第１リングメモリ９３と垂直フィルタリング部９４とは、画像データ２３を垂直方向に帯域分割して、図１４に示したように高域成分Ｈと低域成分Ｌとを生成し、高域成分ＨのデータＹＨ（ｋ）を第２リングメモリ３２Ｈに出力し、低域成分ＬのデータＹＬ（ｋ）を第３リングメモリ３３Ｌに出力する。次いで、第２リングメモリ３２Ｈと第１水平フィルタリング部３３Ｈとは、入力する高域成分Ｈを水平方向に帯域分割して、図１５に示したように２つの帯域成分ＬＨ，ＨＨを生成して出力する。これと並行して、第３リングメモリ３３Ｌと第２水平フィルタリング部３３Ｌとは、入力する低域成分Ｌを水平方向に帯域分割して、図１５に示したような２つの帯域成分ＬＬ，ＨＬを生成して出力することになる。
【０１８７】
具体的には、第１リングメモリ９３と垂直フィルタリング部９４は、上記Ｎ回目処理（図３７）と上記Ｎ＋１回目処理（図３８）を含む各回の処理を、各画素列について水平ライン単位で繰り返し実行する。例えば、上記Ｎ回目処理（図３７）が、０番目の画素列に対して実行された後に、１番目の画素列に対して実行され、次に、２番目の画素列に対して実行され、・・・、最終的に、Ｗ−１番目の画素列に対して実行される。その後、上記Ｎ＋１回目処理（図３８）が、０番目の画素列に対して実行された後に、１番目の画素列に対して実行され、更に、２番目の画素列に対して実行され、・・・、最終的に、Ｗ−１番目の画素列に対して実行される。このようにして、各回の処理が全ての画素列について繰り返し実行される。
【０１８８】
この結果、垂直フィルタリング部９４からは、高域成分ＨのデータＹＨ（ｋ）と低域成分ＬのデータＹＬ（ｋ）とが各水平ライン単位で並列に出力される。例えば、上記Ｎ回目処理（図３７）を０番目〜Ｗ−１番目の画素列に対して連続的に実行した結果、２ｎ番目の水平ラインの低域成分ＬのデータＹ０（２ｎ），Ｙ１（２ｎ），…，Ｙｊ（２ｎ），…，ＹＷ−１（２ｎ）が連続的に出力される。これと並行して、２ｎ＋３番目の水平ラインの高域成分ＨのデータＹ０（２ｎ＋３），Ｙ１（２ｎ＋３），…，Ｙｊ（２ｎ＋３），…，ＹＷ−１（２ｎ＋３）が連続的に出力される。
【０１８９】
次いで、第２リングメモリ３３Ｈと第１水平フィルタリング部３３Ｈは、水平ライン単位で入力する高域成分ＨのデータＹＨ（ｋ）を１点当たり１クロック周期でフィルタリングすることで帯域成分ＨＨ，ＬＨのデータを出力し、また、第３リングメモリ３２Ｌと第２水平フィルタリング部３３Ｌは、水平ライン単位で入力する低域成分ＬのデータＹＬ（ｋ）を１点当たり１クロック周期でフィルタリングすることで帯域成分ＨＬ，ＬＬのデータを出力する。なお、第２リングメモリ３２Ｈと第３リングメモリ３３Ｌは、図４０に示すように、入力データ…，Ｙｊ（ｋ），Ｙｊ＋１（ｋ），…に対応する８点（８画素）のデータを保持する記憶領域１４１を有し、上記一時データや中間データを保持することができる。
【０１９０】
以上の処理を再帰的に実行させることで、任意次数の分解レベルの帯域成分を算出することができる。すなわち、ｋ−１次（ｋは２以上の整数）の分解レベルにおける水平方向と垂直方向の低域成分ＬＬ（ｋ−１）を、ウェーブレット変換装置３０に再帰的に入力させることで、ｋ次の分解レベルにおける帯域成分ＨＨｋ，ＨＬｋ，ＬＨｋ，ＬＬｋを得ることが可能である。
【０１９１】
なお、第１リングメモリ９３は、図３９に模式的に示すように、入力データ列に対応する１２×Ｗ点（１２ライン）のデータを保持する記憶領域１４０を有しており、上記一時データや中間データを保持することができる。この記憶領域１４０は、垂直方向に１２点のデータを保持する列領域の集合体である。一つの列領域によって、１回の処理で参照される入力データや中間データが保持される。例えば、Ｎ回目処理（図３７）では、或る列領域において、データ列｛Ｄ２ｎ，Ｓ１ｎ＋１，Ｄ２ｎ＋１，Ｓ１ｎ＋２，Ｄ１ｎ＋２，Ｓ１ｎ＋３，Ｄ１ｎ＋３，Ｘ（２ｎ＋８），Ｄ１ｎ＋４，Ｘ（２ｎ＋１０），Ｘ（２ｎ＋１１），Ｘ（２ｎ＋１２）｝から、データ列｛Ｄ２ｎ，Ｓ１ｎ＋１，Ｄ２ｎ＋１，Ｓ１ｎ＋２，Ｄ２ｎ＋２，Ｓ１ｎ＋３，Ｄ１ｎ＋３，Ｓ１ｎ＋４，Ｄ１ｎ＋４，Ｘ（２ｎ＋１０），Ｄ１ｎ＋５，Ｘ（２ｎ＋１２）｝へ記憶内容が変化する（データＤ１ｎ＋２，Ｘ（２ｎ＋８），Ｘ（２ｎ＋１１）が、それぞれ、データＤ２ｎ＋２，Ｓ１ｎ＋４，Ｄ１ｎ＋５に上書きされる）。
【０１９２】
本実施形態に係るリフティング演算では、図３７に示すように、第１リングメモリ９３から、上位２系列のデータＤ２ｎ，Ｓ１ｎ＋１を一度参照した後は、これらデータＤ２ｎ，Ｓ１ｎ＋１は二度と参照されないため、上位２系列のデータＤ２ｎ，Ｓ１ｎ＋１を下位２系列のデータＤ１ｎ＋５，Ｘ（２ｎ＋１２）で上書きすることができる。このように、各回の処理で上位２系列のデータを下位２系列のデータで上書きさせることで、図３９に示す記憶領域１４０を１０×Ｗ点（１０ライン）の領域に削減し、メモリ使用量を節減することが可能である。
【０１９３】
このように、本実施形態に係るウェーブレット変換装置９０とウェーブレット変換方法では、４点の中間データを算出する４個の変換処理と２点の中間データを規格化する２個の規格化処理とを１クロック周期内に並列に同時実行するため、出力データの算出周期を大幅に短縮化できる。したがって、ウェーブレット変換を極めて短時間で高速に実行することが可能である。
【０１９４】
また、ウェーブレット変換装置９０は、１クロック周期内で２点のデータを算出する垂直フィルタリング部９４と、１クロック周期内に１点のデータを算出する第１および第２水平フィルタリング部３３Ｈ，３３Ｌとを備えるため、１クロック周期内に高域成分のデータと低域成分のデータとを並列に算出できる。したがって、ラインベースの２次元ＤＷＴ演算を極めて高速に実行することが可能である。
【０１９５】
＜変形例＞
図４１は、上記した第４の実施形態の変形例に係る２次元ウェーブレット変換装置１３０の概略構成を示す図である。このウェーブレット変換装置１３０は、２次元画像データｘ（ｎ）を一時的に保持するバッファ９１、外部供給のクロック信号ＣＬＫと同期して動作するＭＭＵ（メモリ管理部）９２Ａ、第１リングメモリ９３Ａ、垂直フィルタリング部９４Ａ、ラインバッファ回路１３１、第２リングメモリ９３Ｂおよび水平フィルタリング部９４Ｂを備えて構成されている。
【０１９６】
ここで、垂直フィルタリング部９４Ａと水平フィルタリング部９４Ｂは、上記第４の実施形態に係る垂直フィルタリング部９４（図３５）の構成と同じ構成を有し、図３７〜図３８で示したリフティング演算を実行するように、データを与えられ且つ制御される。
【０１９７】
垂直フィルタリング部９４Ａからは、高域成分ＨのデータＹＨ（ｋ）と低域成分ＬのデータＹＬ（ｋ）とが各水平ライン単位で出力される。言い換えれば、垂直フィルタリング部９４Ａは２本のデータＹＨ（ｋ），ＹＬ（ｋ）を水平ライン単位で並列に出力する。ラインバッファ回路１３１においては、第１ラインバッファ１３３と第２ラインバッファ１３４は、それぞれ、水平ライン２本分のバッファを備えている。セレクタ１３２が、入力する２本のデータを第１ラインバッファ１３３と第２ラインバッファ１３４の何れか一方に記憶させる期間、デマルチプレクサ１３５は、その他方に記憶済みの２本のデータを読み出して第２リングメモリ９３Ｂに出力する。
【０１９８】
このように本変形例の構成によっても、１クロック周期内に高域成分のデータと低域成分のデータとを並列に算出できることから、ラインベースの２次元ＤＷＴ演算を極めて高速に実行することが可能である。
【０１９９】
【発明の効果】
以上の如く、本発明に係るウェーブレット変換装置によれば、各入力データを一系列の中間データに変換する変換処理と、低域成分および高域成分の出力データを算出する規格化処理とを繰り返し実行し、繰り返し実行される複数の処理のうち少なくとも２個の処理を１クロック周期内に並列に実行するため、出力データの算出周期を短縮化でき、ウェーブレット変換を短時間で高速に実行することが可能になる。
【０２００】
また、本発明に係るウェーブレット変換方法によれば、入力データを一系列の中間データに変換する工程（ｂ）と、低域成分および高域成分の出力データを算出する工程（ｃ），（ｄ）とは繰り返し実行されるが、繰り返し実行する複数の工程のうち少なくとも２工程を１クロック周期内に並列に実行するため、入力データ列から出力データを算出する周期を短縮化でき、ウェーブレット変換を短時間で高速に行うことが可能になる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係るウェーブレット変換装置の概略構成を示す図である。
【図２】第１の実施形態に係るフィルタリング部の概略構成図である。
【図３】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図４】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図５】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図６】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図７】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図８】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図９】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図１０】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図１１】第１の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図１２】２次元画像データを示す図である。
【図１３】２次元画像データとリングメモリの記憶領域とを模式的に示す図である。
【図１４】２次元画像データの帯域分割図である。
【図１５】２次元画像データの帯域分割図である。
【図１６】リングメモリの記憶領域を模式的に示す図である。
【図１７】本発明の第２の実施形態に係るウェーブレット変換装置の概略構成を示す図である。
【図１８】第２の実施形態に係るフィルタリング部の概略構成図である。
【図１９】第２の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２０】第２の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２１】第２の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２２】第２の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２３】第２の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２４】２次元画像データとリングメモリの記憶領域とを模式的に示す図である。
【図２５】リングメモリの記憶領域を模式的に示す図である。
【図２６】本発明の第３の実施形態に係るフィルタリング部の概略構成を示す図である。
【図２７】第３の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２８】第３の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図２９】第３の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３０】第３の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３１】第３の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３２】第３の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３３】第２および第３の実施形態の変形例に係るウェーブレット変換装置の概略構成を示す図である。
【図３４】本発明の第４の実施形態に係るウェーブレット変換装置の概略構成を示す図である。
【図３５】第４の実施形態に係る垂直フィルタリング部の概略構成図である。
【図３６】第４の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３７】第４の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３８】第４の実施形態に係るリフティング演算の工程を模式的に示す図である。
【図３９】２次元画像データとリングメモリの記憶領域とを模式的に示す図である。
【図４０】リングメモリの記憶領域を模式的に示す図である。
【図４１】第４の実施形態の変形例に係るウェーブレット変換装置の概略構成を示す図である。
【図４２】ＤＷＴと逆ＤＷＴで用いるフィルタバンクを模式的に示す図である。
【図４３】３次の分解レベルで２次元ＤＷＴを施された画像データを模式的に示す図である。
【図４４】分解側のリフティング構成を模式的に示す格子図である。
【図４５】ＪＰＥＧ２０００方式が推奨する算出方法を模式的に示す図である。
【図４６】リフティング演算の工程を模式的に示す図である。
【図４７】リフティング演算の工程を模式的に示す図である。
【図４８】リフティング演算の工程を模式的に示す図である。
【図４９】リフティング演算の工程を模式的に示す図である。
【図５０】リフティング演算の工程を模式的に示す図である。
【図５１】リフティング演算の工程を模式的に示す図である。
【図５２】リフティング演算の工程を模式的に示す図である。
【図５３】リフティング演算の工程を模式的に示す図である。
【図５４】リフティング演算の工程を模式的に示す図である。
【図５５】リフティング演算の工程を模式的に示す図である。
【図５６】リフティング演算の工程を模式的に示す図である。
【符号の説明】
１  ウェーブレット変換装置
２  ＭＭＵ（メモリ管理部）
３Ａ，３Ｂ  リングメモリ
４Ａ，４Ｂ  フィルタリング部
５  ラインバッファ回路
【図１】
2004165907.tif 000004
【図２】
2004165907.tif 000005
【図３】
2004165907.tif 000006
【図４】
2004165907.tif 000007
【図５】
2004165907.tif 000008
【図６】
2004165907.tif 000009
【図７】
2004165907.tif 000010
【図８】
2004165907.tif 000011
【図９】
2004165907.tif 000012
【図１０】
2004165907.tif 000013
【図１１】
2004165907.tif 000014
【図１２】
2004165907.tif 000015
【図１３】
2004165907.tif 000016
【図１４】
2004165907.tif 000017
【図１５】
2004165907.tif 000018
【図１６】
2004165907.tif 000019
【図１７】
2004165907.tif 000020
【図１８】
2004165907.tif 000021
【図１９】
2004165907.tif 000022
【図２０】
2004165907.tif 000023
【図２１】
2004165907.tif 000024
【図２２】
2004165907.tif 000025
【図２３】
2004165907.tif 000026
【図２４】
2004165907.tif 000027
【図２５】
2004165907.tif 000028
【図２６】
2004165907.tif 000029
【図２７】
2004165907.tif 000030
【図２８】
2004165907.tif 000031
【図２９】
2004165907.tif 000032
【図３０】
2004165907.tif 000033
【図３１】
2004165907.tif 000034
【図３２】
2004165907.tif 000035
【図３３】
2004165907.tif 000036
【図３４】
2004165907.tif 000037
【図３５】
2004165907.tif 000038
【図３６】
2004165907.tif 000039
【図３７】
2004165907.tif 000040
【図３８】
2004165907.tif 000041
【図３９】
2004165907.tif 000042
【図４０】
2004165907.tif 000043
【図４１】
2004165907.tif 000044
【図４２】
2004165907.tif 000045
【図４３】
2004165907.tif 000046
【図４４】
2004165907.tif 000047
【図４５】
2004165907.tif 000048
【図４６】
2004165907.tif 000049
【図４７】
2004165907.tif 000050
【図４８】
2004165907.tif 000051
【図４９】
2004165907.tif 000052
【図５０】
2004165907.tif 000053
【図５１】
2004165907.tif 000054
【図５２】
2004165907.tif 000055
【図５３】
2004165907.tif 000056
【図５４】
2004165907.tif 000057
【図５５】
2004165907.tif 000058
【図５６】
2004165907.tif 000059