(57)【要約】【課題】リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法及びそのハードウエア構造の提供。【解決手段】リフト式構造を出発点とし、基本演算ユニットの間の乗算器を通過するカットセットの辺全部に乗法係数の逆数を乗じ、これにより時間遅延累積効果を切断し、その後、該基本演算ユニット中の演算ノードを二つの加算器に分け、フリップ式構造を利用してその臨界経路が長すぎる欠点を改善し、これによりリフト式構造のハードウエア需要量方面の優勢を保有できるようにし、大量に臨界経路を短縮し、最良のハードウエア構造を達成する。【選択図】　　　　図６
2004072494.tif 000002
【特許請求の範囲】
【請求項１】
リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、
リフト式ハードウエア構造を骨格とし、それは複数の基本演算ユニットを含むものとし、且つ各一つの基本演算ユニット中の演算ノードの出力を次の一つの基本演算ユニットの入力ノードに連接させるステップと、
フリッピングステップとされ、相互に連接された基本演算ユニットの間の乗算器を除去することにより時間遅延累積効果を切断し、且つ該乗算器を除去する方法として、１条の該乗算器を通過するカットセットに沿って、各カットセット上の辺全部にその乗法係数の逆数を乗じる、上記フリッピングステップと、
該基本演算ユニット中の演算ノードを二つの加算器に分け、そのうち一つの加算器がその他の基本演算ユニットと同時に動作するようにし、もう一つの加算器が時間遅延累積の経路にあるようにするステップと、
を具えたことを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法。
【請求項２】
請求項１に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、リフト式ハードウエア構造に対して、更にパイプライン化方法を利用して臨界経路を短縮することを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法。
【請求項３】
請求項１に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、リフト式ハードウエア構造の演算法は、複数のリフティングステップと一つの正規化ステップに分けられ、且つ全てのフリップ後の乗法は該正規化ステップに加入され、これにより取得するローバンドパス係数とハイバンドパス係数の正確性を確保することを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法。
【請求項４】
請求項１に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、リフト式ハードウエア構造中、少なくとも一つの基本演算ユニットをフリップさせることを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法。
【請求項５】
リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、複数の基本演算ユニットを具え、各一つの基本演算ユニット中の演算ノードの出力が次の一つの基本演算ユニットの入力ノードに連接され、且つ該基本演算ユニットの演算ノード及び入力ノードの間の乗算器が乗法係数の逆数を乗じ、並びに各演算ノードが二つの加算器に分けられたことを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造。
【請求項６】
請求項５に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、少なくとも一つの演算ノードがフリップされて該乗算器にその乗法係数の逆数を乗じさせることを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造。
【請求項７】
請求項５に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、二つの加算器のうちの一つがその他の基本演算ユニットと同時に動作し、もう一つの加算器が時間遅延累積の経路にあることを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造。
【請求項８】
請求項５に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、各基本演算ユニットが一つのレジスタ、二つの加算器及び一つの乗算器で組成されたことを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一種の画像圧縮標準の離散ウェーブレット変換（ＤｉｓｃｒｅｔｅＷａｖｅｌｅｔ　Ｔｒａｎｓｆｏｒｍ；ＤＷＴ）技術に係り、特に、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法及びそのハードウエア構造に関する。
【０００２】
【従来の技術】
離散ウェーブレット変換（ＤＷＴ）は良好な時間−周波数分解効果を有するため、多くのウェーブレット変換を基礎とする信号分析及び圧縮の研究で極めて多くの豊富な成果を獲得しており、さらに、新時代の静態画像圧縮標準、例えばＪＰＥＧ２０００　ｓｔｉｌｌ　ｉｍａｇｅ　ｃｏｄｉｎｇ及び　ＭＰＥＧ−４
ｓｔｉｌｌ　ｔｅｘｔｕｒｅ　ｃｏｄｉｎｇは、いずれもＤＷＴをその核心演算法としている。しかし、それ以前の変換方法、例えば離散コサイン変換（Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ；ＤＣＴ）に較べ、ＤＷＴは比較的多くの演算量を必要とし、このほか、ＤＣＴのブロック処理方式に較べ、基本的にＤＷＴは全体画像を一緒に処理する必要があり、膨大なメモリと大量のアクセス周波数幅を必要とすることが、二次元離散ウェーブレット変換（２−Ｄ
ＤＷＴ）のハードウエア実現上のネックとなっている。
【０００３】
ＤＷＴ自身は一対のウェーブレットフィルタセットの演算とされ、重畳（Ｃｏｎｖｏｌｕｔｉｏｎ）を利用して実現するのは最も直接的方式であり、その数学式は以下のように示される。
【数１】
2004072494.tif 000003
そのうち、ＸＬ　（ｎ）とＸＨ　（ｎ）はそれぞれ低周波及び高周波信号とされ、ｈ（ｎ）とｇ（ｎ）はそれぞれローバンドパスとハイバンドパスフィルタ係数とされる。図１に示されるように、重畳を基礎とする離散ウェーブレット変換ハードウエア構造は信号発生率が一つのクロックサイクル中の入力の二つの信号点と出力の二つ信号点に固定され、並びに最小出力遅延と最少のレジスタを要求する。ここで、Ｔｍ　は乗算器の時間遅延、Ｔａ　は加算器の時間遅延、Ｃｍ　は乗算器のハードウエアコスト、Ｃａ　は加算器のハードウエアコスト、及びＫはフィルタの長さと定義され、図１の臨界経路はＴｍ　＋（Ｋ−１）Ｔａ　とされ、且つ必要なハードウエアサイズは、２Ｋ・Ｃｍ　＋２（Ｋ−１）Ｃａ　とされ、加算器ツリー（Ａｄｄｅｒ　Ｔｒｅｅ）を利用すればさらに該臨界経路を
【数２】
2004072494.tif 000004
に下げることができる。しかし重畳の必要とする演算量は多く、且つ境界延伸（Ｂｏｕｎｄａｒｙ　ｅｘｔｅｎｓｉｏｎ）の制御回路は十分に複雑である。このため、リフト式構造（Ｌｉｆｔｉｎｇ　ｓｃｈｅｍｅ）がすでに提出され、ＤＷＴの演算量を減少すると共に境界延伸と記憶量アクセスの操作制御の複雑度を減らすのに用いられ、その後、さらに、完全な多項式マトリクス（Ｐｏｌｙ−ｐｈａｓｅ　ｍａｔｒｉｘ）に分解してリフト式構造を得る方法がすでに提出され、これによりリフト式構造は広くＤＷＴのハードウエアとソフトウエアの実現に応用されるようになった。リフト式構造は任意の、完全再建（Ｐｅｒｆｅｃｔ　Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ）可能な離散ウェーブレット変換フィルタセットにおいて、一連のリフティングステップに分解でき、この分解方法は、一つの離散ウェーブレット変換の多項式マトリクスを分解してなる一連の上三角と下三角マトリクス及び一つの常数対角マトリクスに対応する。その数式は以下のとおりである。
【数３】
2004072494.tif 000005
そのうち、ｈ（ｚ）とｇ（ｚ）はそれぞれロー及びハイバンドパスフィルタとされ、Ｐ（ｚ）は相互に対応する多項式マトリクスとされる。ＪＰＥＧ２０００に設けられた（９，７）フィルタセットを例として説明すると、（９，７）フィルタセットは四つのリフティングステップと一つの正規化ステップ（Ｎｏｍａｌｉｚａｔｉｏｎ　ｓｔｅｐ）に分解され、これは以下の数式で示されるとおりである。
【数４】
2004072494.tif 000006
並びに図２の信号流向図に示されるように、そのうち黒点は演算ノード（Ｃｏｍｐｕｔａｔｉｏｎ　ｎｏｄｅ）を、グレーポイントはレジスタノードを、白点は入力ノードを代表し、且つ該演算ノードは全ての入力の総和を計算でき、正規化ステップ中のＫと１／Ｋがリフティングステップ以外で独立して実現されるか、或いはリフティングステップの後がデータ圧縮であれば、正規化ステップと量子化（Ｑｕａｎｔｉｚａｔｉｏｎ）ステップが一緒に実行され、ゆえにここではわずかにリフティングステップの実現について討論する。
【０００４】
もし重畳をベースとする離散ウェーブレット変換構造で（９，７）フィルタセットを実現し、さらに加算器ツリーとその係数の対称性を使用すると、全部で９個の乗算器と１４個の加算器及び７個のレジスタが必要である。しかし、図２に示されるように、リフト式構造で実現した（９，７）フィルタセットはわずかに４個の乗算器、８個の加算器と４個のレジスタ（この部分にＫと１／Ｋの実現は含まれない）しか必要とせず、重畳を基礎とする構造の臨界経路はＴｍ　＋４Ｔａ　で、図２の輪形経路は４Ｔｍ　＋８Ｔａ　である。リフト式ハードウエア構造をパイプライン化すると、有効に臨界経路を短縮できるが、これによってレジスタの数が急速に増加しうる。例えば、もし図２を四つのパイプライン化ステージに切断し、図３に示されるように、臨界経路をＴｍ　＋２Ｔａ　とすると、６個のレジスタが増加する。パイプライン化によりもたらされるレジスタ数の増加は、条状式二次元離散ウェーブレット変換を実現する時の極めて厳重な問題となる。これは一つの離散ウェーブレット変換構造中のレジスト数が、条状式二次元離散ウェーブレット変換のハードウエア構造中の内部メモリの数量に正比例することによる。
【０００５】
一方で、条状式方法（Ｌｉｎｅ−ｂａｓｅｄ　ｍｅｔｈｏｄ）も提出されて二次元ＤＷＴのメモリ要求を減少するのに用いられ、それはまず全体のフレームサイズのメモリを数条のフレーム幅サイズのメモリに縮減し、わずかにある適当な記憶量アクセス管理を透過することのみ必要である。別の角度から見ると、条状式方法はまた、外部フレームメモリ（Ｅｘｔｅｒｎａｌ　ｆｒａｍｅ　ｍｅｍｏｒｙ）に対するアクセス回数を減少するのに用いられ、一つだけの内部条状メモリを増加することにより、必要な内部レジスタメモリの量と採用する一次元離散ウェーブレット変換ハードウエアモジュール内のレジスタ数を正比例させる。図４、５は一次元構造中のレジスタを内部レジスタメモリに変換する表示図である。図４はもとの一次元変換ハードウエア構造中の回路とされ、そのうち、Ｒはレジスタとされ、Ｋ０　は一次元変換ハードウエア中のレジスタの数とされ、Ｎはフレームの幅とされる。これから分かるように、レジスタメモリのサイズは確実に、一次元構造中のレジスタ数と正比例をなす。ゆえに固定されたハードウエア速度制限下で、いかにレジスタメモリを最小化するかが、条状式二次元離散ウェーブレット変換のハードウエア実現で第１に考慮しなければならないことである。しかし、ＤＷＴハードウエア実現は臨界経路（Ｃｒｉｔｉｃａｌ　ｐａｔｈ）と条状メモリの数量の間の考察（Ｔｒａｄｅ−ｏｆｆ）に関しては、いまだいかなる文献上においても討論はなされていない。
【０００６】
【発明が解決しようとする課題】
前述したように、リフト式構造により実現したＤＷＴハードウエア構造は重畳に較べて多くの長所を有している。このほか、その必要とする条状メモリ数もまた重畳に較べて少ない。しかし、その有する臨界経路は本質的に重畳より非常に大きくなり、パイプライン化方法を使用して臨界経路を減少することもできるが、必要とする条状メモリは却って大量に増加してしまう。ゆえに、二次元ＤＷＴの条状式ハードウエア実現上、リフト式構造を用いて実現するのは相当に大きな困難を伴う。これにより、本発明は全く新しいフリップ式演算法によりこの問題を解決し、リフト式構造を出発点とし、あるリフティングステップをフリップさせて大量に臨界経路を短縮すると共に、リフト式構造の全ての長所を保留し、ゆえにフリップ式構造を使用してＤＷＴを実現し、どのような方面でも周知のリフト式構造と重畳を基礎とする構造に較べて高い効率を有することができるようにし、有効に周知の欠点を解決する。
【０００７】
本発明の主要な目的は、一種のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法及びそのハードウエア構造を提供することにあり、それは、離散ウェーブレット変換演算量を減らすと共に、境界延伸と記憶量アクセスの操作制御の複雑度を減らす長所を有するほか、大量に臨界経路を短縮できる効果を有するものとする。
【０００８】
本発明の別の目的は、一種のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法及びそのハードウエア構造を提供することにあり、それは、固定されたハードウエア規格と応用制限の下で、内部メモリ量を最低にまで減らすと共に、最小のハードウエア要求と良好な臨界経路の効果を有するものとする。
【０００９】
本発明のさらに別の目的は、臨界経路、ハードウエア要求或いはレジスタ使用量の方面のいずれにおいても、更に高い機能を有するフリップ式演算法及びそのハードウエア構造を提供することにある。
【００１０】
【課題を解決するための手段】
請求項１の発明は、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、
リフト式ハードウエア構造を骨格とし、それは複数の基本演算ユニットを含むものとし、且つ各一つの基本演算ユニット中の演算ノードの出力を次の一つの基本演算ユニットの入力ノードに連接させるステップと、
フリッピングステップとされ、相互に連接された基本演算ユニットの間の乗算器を除去することにより時間遅延累積効果を切断し、且つ該乗算器を除去する方法として、１条の該乗算器を通過するカットセットに沿って、各カットセット上の辺全部にその乗法係数の逆数を乗じる、上記フリッピングステップと、
該基本演算ユニット中の演算ノードを二つの加算器に分け、そのうち一つの加算器がその他の基本演算ユニットと同時に動作するようにし、もう一つの加算器が時間遅延累積の経路にあるようにするステップと、
を具えたことを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法としている。
請求項２の発明は、請求項１に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、リフト式ハードウエア構造に対して、更にパイプライン化方法を利用して臨界経路を短縮することを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法としている。
請求項３の発明は、請求項１に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、リフト式ハードウエア構造の演算法は、複数のリフティングステップと一つの正規化ステップに分けられ、且つ全てのフリップ後の乗法は該正規化ステップに加入され、これにより取得するローバンドパス係数とハイバンドパス係数の正確性を確保することを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法としている。
請求項４の発明は、請求項１に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法において、リフト式ハードウエア構造中、少なくとも一つの基本演算ユニットをフリップさせることを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法としている。
請求項５の発明は、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、複数の基本演算ユニットを具え、各一つの基本演算ユニット中の演算ノードの出力が次の一つの基本演算ユニットの入力ノードに連接され、且つ該基本演算ユニットの演算ノード及び入力ノードの間の乗算器が乗法係数の逆数を乗じ、並びに各演算ノードが二つの加算器に分けられたことを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造としている。
請求項６の発明は、請求項５に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、少なくとも一つの演算ノードがフリップされて該乗算器にその乗法係数の逆数を乗じさせることを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造としている。
請求項７の発明は、請求項５に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、二つの加算器のうちの一つがその他の基本演算ユニットと同時に動作し、もう一つの加算器が時間遅延累積の経路にあることを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造としている。
請求項８の発明は、請求項５に記載のリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造において、各基本演算ユニットが一つのレジスタ、二つの加算器及び一つの乗算器で組成されたことを特徴とする、リフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式ハードウエア構造としている。
【００１１】
【発明の実施の形態】
上述の目的を達成するため、本発明はまずリフト式ハードウエア構造を骨格とし、その後、フリップステップを実行し、それは相互に連接する基本演算ユニットの間の乗算器を除去することにより、時間遅延累積効果を切断し、且つ該乗算器を除去する方法は、１条の乗算器を通過するカットセットに沿って、各カットセット上の辺全部にこの乗法係数の逆数を乗じ、最後に基本演算ユニット中の演算ノードを二つの加算器に分け、そのうち一つのア加算器とその他の基本演算ユニットを同時に動作させ、もう一つの加算器がこの時間遅延累積の経路上にあるようにする。
【００１２】
【実施例】
周知のリフト式ハードウエア構造は、比較的少量の算術演算により、比較的少ないハードウエア資源を使用するが、しかし、重畳ハードウエア構造に較べて長い臨界経路を必要とし、もしパイプライン化方式により臨界経路をガン宿すれば、レジスタの数が増加する。これにより、本発明の提出するフリップ式演算法及びそのハードウエア構造は、フリップ法によりリフト式構造の臨界経路を短縮する。
【００１３】
前述の数式３より分かるように、リフト式構造自身は、一連のリフティングステップにより組成され、ゆえにその臨界経路は各リフティングステップの総和に等しく、ここにリフト式構造の遭遇する困難の原因がある。既知のリフト式分解法（例えばＣ．−Ｔ．Ｈｕａｎｇ，Ｐ．−Ｃ．Ｔｓｅｎｇ，及びＬ．−Ｇ．Ｃｈｅｎ氏等により２００２年にＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｉｒｃｕｉｔｓ　ａｎｄ　Ｓｙｓｔｅｍｓにおいて発表された「Ｅｆｆｉｃｉｅｎｔ　ＶＬＳＩ　ａｒｃｈｉｔｅｃｔｕｒｅｓ　ｏｆ　ｌｉｆｔｉｎｇ−ｂａｓｅｄ　ｄｉｓｃｒｅｔｅ　ｗａｖｅｌｅｔ　ｔｒａｎｓｆｏｒｍ　ｂｙ　ｓｙｓｔｅｍａｔｉｃ　ｄｅｓｉｇｎ　ｍｅｔｈｏｄ」）は、任意のウェーブレットフィルタセットに対して、一つの有効なリフト式ハードウエア構造を得ることができ、この構造は図６に示される基本演算ユニットを連接して組成され、未パイプライン化の状態で、臨界経路は基本演算ユニットの時間遅延の総和に等しく、この時間遅延累積効果は各基本演算ユニットにあって演算ノードの出力が次の基本演算ユニットの入力ノードに連接するためであり、この時間遅延の累積効果を切断するため、本発明ではもとの基本演算ユニット中の入力ノードから演算ノードの間の乗算器を除去する。除去する方法は、図７に示されるように、基本演算ユニットを乗法係数の逆数を利用してフリップの動作を行い、即ち、１条の該乗算器を通過するカットセット（Ｃｕｔｓｅｔ）に沿って、各カットセット上のエッジすべてにこの乗法係数の逆数を乗じ、続いて、各演算ノードについて、図８に示されるように、基本演算ユニット中の演算ノードを二つの加算器に分ける。そのうち一つの加算器はその他の基本演算ユニット中の対応する加算器と同時に動作でき、もう一つの加算器は時間遅延累積の経路上にある。こうして、乗算器の時間遅延が累積経路上にないものとする。これにより、もとの厳重な時間遅延累積効果を有するリフト式ハードウエア構造は、本発明のフリップ法によりフリップ式構造とすることにより、累積効果を大幅に軽減することができる。
【００１４】
フリップ式演算法のもう一つの特徴は、全ての基本演算ユニットをフリップさせたとしても、いかなる乗算器をも増加させないことである。このほか、全てのフリップされた乗法係数は正規化ステップ中に入る時に、得られたローバンドパス係数とハイバンドパス係数を正確に確保でき、（９，７）フィルタを例に挙げると、全ての基本演算ユニットをすべてフリップさせる場合、以下の多項式マトリクスの変化により表示できる。
【数５】
2004072494.tif 000007
【００１５】
続いて、具体的実施例により本発明の技術原理を説明する。図９に示されるのは、本発明の（９，７）フィルタのフリップ式詳細構造表示図であり、そのうち、点線以上は正規化部分とされ、並びに本発明で討論する構造には含まれず、全体構造は合計４個のレジスタ、８個の加算器、及び４個の乗算器を具え、且つ一つのクロックサイクル中に二つの信号入力と二つの信号出力を必要とする。（そのうち、シフタと乗算器の係数は関係するが、ここでは説明を省略する。）
【００１６】
図示されるように、二つの入力ノードのコードはそれぞれｉ１とｉ２とされ、レジスタコードはｒ１〜ｒ４とされ、乗算器コードはｍ１〜ｍ４とされ、且つ各一つの乗算器はいずれもフリップされ、乗算器ｍ１〜ｍ４はそれぞれ乗法係数の逆数１／ａ、１／ａｂ’、１／ｂ’ｃ及び１／ｃｄ’を乗じる。詳細な動作について以下に説明する。レジスタｒ１、ｒ２、ｒ３、ｒ４の入力はそれぞれｉ２、ａ２の出力、ａ４の出力及びａ６の出力とされる。乗算器ｍ１、ｍ２、ｍ３及びｍ４の入力はそれぞれｉ１、ｒ１の出力、ｒ２の出力及びｒ３の出力とされる。加算器ａ１の入力はｍ１の出力とｒ１の出力とされる。加算器ａ２の入力はａ１の出力とｉ２の出力とされ。加算器ａ３の入力はｍ２の出力とｒ２の出力とされる。加算器ａ４の入力はａ３の出力とａ２の出力とされる。加算器ａ５の入力はｍ３の出力とｒ３の出力とされる。加算器ａ６の入力はａ５の出力とａ４の出力とされる。加算器ａ７の入力はｒ４の出力とｍ４の出力とされる。加算器ａ８の入力はａ７の出力とａ６の出力とされる。最後にａ６とａ８の出力は本構造の二つの出力信号、ハイバンドパス信号及びローバンドパス信号とされる。これによ、十分に明らかに全体のフリップ式ハードウエア構造の詳細なフローが了解される。
【００１７】
実際には、フリップ式構造は多彩な変化が可能であり、いくつの、およびどの基本演算ユニットをフリップさせるかは、フィルタセットの選択とハードウエアの制限により決定される。フリップ式構造の機能は臨界経路を短縮するだけではなく、離散ウェーブレット変換ハードウエア設計の多くに、一つの最適化の選択を提供する。同様に証明されるように、本発明のフリップ式演算法及びその構造は逆離散ウェーブレット変換（Ｉｎｖｅｒｓｅ　ＤＷＴ）に応用でき、これはリフト式分解後、発生する基本演算ユニットとハードウエア構造がいずれも離散ウェーブレット変換と全く同じである。
【００１８】
以上は、本発明の精神の説明であるが、以下に、特に具体的な実験凡例により上述の原理と機能を検証、説明する。本発明の提出するフリップ式演算法及びハードウエア構造の機能を分析するため、本発明を周知の技術構造と比較した。比較過程と結果は後述するとおりである。
【００１９】
ＪＰＥＧ２０００　ｄｅｆａｕｌｔｅｄ（９，７）フィルタセットのリフト式構造は非常に規則的で典型的であり、且つ該（９，７）フィルタセットは画像圧縮及び分析上の効果が十分に良好であり、ゆえにそのウェーブレット変換ハードウエア実現を行う凡例は非常に有意義であり、続いてそれを重畳を基礎とするハードウエア構造、伝統的なリフト式構造及び本発明のフリップ式構造の間に利用し、ハードウエア要求、臨界経路及びレジスタ数の方面で比較を行う。まず、前述した重畳構造は９個の乗算器、１４個の加算器及び７個のレジスタを必要とし、この時臨界経路はＴｍ　＋４Ｔａ　であり、三級パイプライン化の後、臨界経路はＴｍ　に減少するが、レジスタ数は２３個に増加する。伝統的なリフト式構造は、図２に示されるように４個の乗算器、８個の加算器、及び４個のレジスタを必要とするが、臨界経路は４Ｔｍ　＋８Ｔａ　であり、四級パイプライン化の後、図３に示される臨界経路はＴｍ　＋２Ｔａ　に減少する。しかしレジスタは１０個に増加する。さらに、もし臨界経路をＴｍ　に縮減する必要があれば、全部で３４個のレジスタが必要となる。
【００２０】
実際にリフト式構造をフリップさせる時、注意深くその正確度を処理しなければならず、これはそのうちに乗法係数の逆数が出現しうるためである。本発明は（９，７）フィルタセットに対して一つのフリップ式構造を設計し、それは図１０に示されるように、全ての基本演算ユニットがフリップされ、且つ正確度が注意深く処理されている。その必要な乗算器、加算器とレジスタ数は図２と同じであるが、この時の臨界経路はすでにＴｍ　＋５Ｔａ　に減っている。当然パイプライン化もまたフリップ式構造の臨界経路を短縮するのに使用でき、図１０に示される三級パイプライン化の後、さらに一つの乗算器と加算器を新たに組み合わせて、図１１に示される構造を得ることができる。このとき臨界経路がＴｍ　＋Ｔａ　に減らされると共に、３個のレジスタだけが増加する。最後に図１２に示されるように、五級パイプライン化により、臨界経路が最小化されＴｍ　にまで縮減され、且つ全部でわずかに１１個のレジスタだけが必要である。
【００２１】
さらに真実の比較結果を得るため、本実験凡例の発明の上述の多くの構造に対してハードウエア検証を行う。その方法は、まず検査ログコード（Ｖｅｒｉｌｏｇ　ｃｏｄｅ）を書き込み、さらにＡｖａｎｔ！０．３５−μｍ　ｓｔａｎｄａｒｄ　ｃｅｌｌ　ｌｉｂｒａｒｙを使用し、シノプシスデザインコンパイラ（Ｓｙｎｏｐｓｙｓ　Ｄｅｓｉｇｎ　Ｃｏｍｐｉｌｅｒ）により回路合成し、回路合成中の時間制限は最も緊迫するようにして比較に便利とした。検証した結果は先に推論した比較結果に十分接近し、最後に全ての推論比較とハードウエア検証結果をすべて表１にまとめた。そのうち、本実施凡例はレジスタメモリサイズを使用してレジスタ数の重要性を表示し、Ｌはフレーム幅とされる。
【表１】
2004072494.tif 000008
表１から分かるように、本発明の提出するリフト式離散ウェーブレット変換ハードウエア実現に使用されるフリップ式演算法及びそのハードウエア構造は、固定されたハードウエア規格と応用制限の下で、内部メモリ量を最低にまで減らすと共に、最小ハードウエア要求と良好な臨界経路の効果を有し、このフリップ式構造は臨界経路、ハードウエア要求或いはレジスタ使用量方面のいずれにおいても高い効果を達成できる。
【００２２】
このほか、リフト式構造はハードウエアとソフトウエア実現上、よい所を有している以外に、それはウエーブレット類似（Ｗａｖｅｌｅｔ−ｌｉｋｅ）フィルタセットを設計するための良好な構造を提供し、これは、Ｄａｖｉｄ　Ｂ．Ｈ．Ｔａｙ氏によるＰｒｏｃ．　Ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，２００１，ｖｏｌ．１，第６０２−６０５頁の「Ａ　ｃｌａｓｓ　ｏｆ　ｌｉｆｔｉｎｇ　ｂａｓｅｄｉｎｔｅｇｅｒ　ｗａｖｅｌｅｔ　ｔｒａｎｓｆｏｒｍ」及び、Ｚ．Ｇｕａｎｇｊｕｎ，Ｃ．Ｌｉｚｈｉ，及びＣ．Ｈｕｏｗａｎｇ氏によるＰｒｏｃ．　ＯｆＩｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，２００１，ｖｏｌ．２，第２４９−２５２頁の「Ａ　ｓｉｍｐｌｅ　９／７−ｔａｐ　ｗａｖｅｌｅｔ　ｆｉｌｔｅｒ　ｂａｓｅｄ　ｏｎｌｉｆｔｉｎｇ　ｓｃｈｅｍｅ」に提示されるとおりであり、同一の検討会中でそれぞれ一組の、（９，７）フィルタセットのリフト式構造をフレームとする整数ウエーブレットフィルタセットが提出され、且つこれら二組の整数フィルタセットの結果は実際には同じであり、また、一つの効果が十分にもとの（９，７）フィルタセットに近い整数フィルタセットを得ており、そのリフト式構造の係数はａ＝−３／２、ｂ＝−１／１６、ｃ＝４／５、ｄ＝１５／３２、Ｋ＝４√２／５であり、そのうち、ａ、ｂ、ｃ、ｄの乗法はいずれも少数のシフタ（Ｓｈｉｆｔｅｒ）と加算器を用いて実現されるが、ｃは浮動少数点の演算を必要とし、もし１２ビットの正確度を使用してこの浮動小数点乗法を実現するなら、図１３に示されるような構造によりこの浮動小数点乗法を完成する。図１３は合計１４個の加算器と４個のシフタを必要とし、これにより、もし伝統的なリフト式構造を使用してこの整数フィルタセットを完成するなら、合計１４個の加算器といくつかのシフタを必要とし、この時の臨界経路は１４Ｔａ　とされる。
【００２３】
しかし、もし本発明の方法を利用し、ｃの基本演算ユニットを加えて図１４と同様にフリップさせると、このハードウエア構造はわずかに１３個の加算器しか必要とせず、且つ図１１中の加算器の新たなレイアウト後に、臨界経路は７Ｔａ　に減る。このほか、図１４中はすでにいかなる浮動小数点演算も含まず、ゆえにこの構造中の全てのレジスタデータの正確度はいずれも小さくすることがけいる。
【００２４】
【発明の効果】
本発明は一般のリフト式構造を出発点とし、フリップ式構造を利用してその臨界経路が長すぎる欠点を改善し、こうしてリフト式構造のハードウエア要求量方面での優勢を保有し、また大量に臨界経路を短縮し、最良のハードウエア構造を達成する。このほか、条状式方法（Ｌｉｎｅ−ｂａｓｅｄ　Ｍｅｔｈｏｄ）で二次元離散ウェーブレット変換を実現する時、必要な内部メモリの量は採用する一次元離散ウェーブレット変換ハードウエアモジュール内のレジスタ数と正比例をなし、フリップ式構造は固定されたハードウエア規格と応用制限の下で、内部メモリの量を最低まで減らすと共に、最小ハードウエア要求と良好な臨界経路の長所を有する。上述の二つの離散ウェーブレット変換フィルタの実施凡例より、ＪＰＥＧ２０００に設けられている（９，７）フィルタセットと一つの対応する整数係数（９，７）フィルタセットが、本発明が周知のハードウエア実現に較べての優勢を表示する。
【００２５】
これにより、離散ウェーブレット変換演算量を減らし、境界延伸と記憶量アクセスの操作制御の複雑度を減らす長所のほか、大量に臨界経路を短縮する機能を有し、ゆえに有効に周知の技術に存在する各欠点を解決する。
【００２６】
以上に述べた実施例は本発明の技術思想と特徴を説明するものであり、その目的は、この発明の属する技術の分野における通常の知識を有する者が本発明の内容を了解し、それにより実施できるようにすることにあり、本発明の請求範囲を限定するものではなく、本発明に提示された精神に基づきなしうる均等の修飾或いは変化は、いずれも本発明の請求範囲に属するものとする。
【図面の簡単な説明】
【図１】周知の重畳を基礎とする離散ウェーブレット変換ハードウエア構造表示図である。
【図２】周知の（９，７）フィルタセットのリフト式ハードウエア構造の信号流向図である。
【図３】図２を四つのパイプライン化ステージに切断する表示図である。
【図４】もとの一次元変換ハードウエア構造中の回路表示図である。
【図５】図４に示される回路を条状式二次元変換ハードウエア構造に変換後の回路表示図である。
【図６】本発明の基本演算ユニット表示図である。
【図７】本発明の二つの基本演算ユニットをフリップさせる表示図である。
【図８】本発明のフリップ後の演算ノードを二つの加算器に分けた後の、乗算器と加算器の位置の調整表示図である。
【図９】本発明の、（９，７）フィルタに応用したフリップ式構造の詳細な表示図である。
【図１０】本発明の、（９，７）フィルタセットに対するフリップ式ハードウエア構造表示図である。
【図１１】本発明の、三層パイプライン化のハードウエア構造図である。
【図１２】本発明の、五層パイプライン化のハードウエア構造図である。
【図１３】本発明の、乗法係数４／５の１２ビット正確度に対する設計のハードウエア構造表示図である。
【図１４】本発明の、整数（９，７）フィルタセット中の基本演算ユニットフリップ後の信号流向図である。
【符号の説明】
ｉ１、ｉ２　入力ノード
ｒ１〜ｒ４　レジスタ
ｍ１〜ｍ４　乗算器
ａ１〜ａ８　加算器
【図１】
2004072494.tif 000009
【図２】
2004072494.tif 000010
【図３】
2004072494.tif 000011
【図４】
2004072494.tif 000012
【図５】
2004072494.tif 000013
【図６】
2004072494.tif 000014
【図７】
2004072494.tif 000015
【図８】
2004072494.tif 000016
【図９】
2004072494.tif 000017
【図１０】
2004072494.tif 000018
【図１１】
2004072494.tif 000019
【図１２】
2004072494.tif 000020
【図１３】
2004072494.tif 000021
【図１４】
2004072494.tif 000022