(57)【要約】      （修正有）【課題】  ウェーブレット符号化において、画像およびビデオを符合化する効率的な方式を備えるシステムおよび方法を提供すること。【解決手段】  ２次元信号を入力し、画像内のエッジの空間相関および少なくとも一つのリフテイング・ウェーブレットに基づく方向予測を使用して変換し、変換した結果、エッジに基づく方向角度、およびブロックサイズを表すモードをエントロピー符号化する技術の組合せを採用することによって、画像内の空間相関を活用する。【選択図】  図３
2006074733.tif 000002
【特許請求の範囲】
【請求項１】
２次元（２Ｄ）信号を符号化するシステムにおいて、
汎用コンピューティング・デバイス、および
前記汎用コンピューティング・デバイスによって実行可能なプログラム・モジュールを備えたコンピュータ・プログラムであって、
２次元（２Ｄ）信号を入力し、
前記２次元信号を、画像内のエッジの空間相関および少なくとも１つのリフテイング・ウェーブレットに基づく方向予測を使用して変換し、前記２次元信号を表す出力係数群、前記画像の前記エッジに基づく方向角度、および画像ブロックのサイズを表すモードを獲得し、
前記出力係数、方向角度、およびモードをエントロピー符号化することによって、入力した前記２次元信号の被符号化バージョンを生成する
前記プログラム・モジュール群を備えた前記コンピュータ・プログラムと
を備え
前記汎用コンピューティング・デバイスは、前記コンピュータ・プログラムのプログラム・モジュール群によって命令されることを特徴とするシステム。
【請求項２】
前記２次元信号を変換するプログラム・モジュールは、サブモジュール群を備え、前記サブモジュール群は、
垂直方向における第一の１次元ウェーブレット変換を、  前記垂直方向の前記第一の１次元ウェーブレット変換を、偶数および奇数のポリフェーズ・サンプルに分割し、
近傍の偶数のポリフェーズ・サンプルから奇数のポリフェーズ・サンプルを、予測信号を前記画像内のエッジに沿った角度に方向選択して、予測し、
前記予測した前記奇数のポリフェーズ・サンプルを使用し、更新信号を前記画像内のエッジに沿った角度に方向選択して、偶数のポリフェーズ・サンプルを、更新し、および
前記予測された偶数のポリフェーズ・サンプルの係数を出力する
サブモジュール群を使用して、実行し、
水平方向における第二の１次元ウェーブレット変換を、
前記水平方向の第二の１次ウェーブレット変換を偶数および奇数のポリフェーズ・サンプルに分割し、
近傍の偶数ポリフェーズ・サンプルから奇数ポリフェーズ・サンプルを、予測信号を前記画像内のエッジに沿った角度に方向選択して、予測し、
前記予測した奇数のポリフェーズ・サンプルを使用し、偶数のポリフェーズ・サンプルを、更新信号を前記画像内のエッジに沿った角度に方向選択して、更新し、および
予測した偶数のポリフェーズ・サンプルの係数を出力する
サブモジュール群を使用して実行することを特徴とする請求項１に記載のシステム。
【請求項３】
前記垂直方向における前記第一の１次元ウェーブレット変換および前記水平方向における前記第二の１次元ウェーブレットに関し、前記偶数のポリフェーズ・サンプルは、前記予測した奇数のポリフェーズ・サンプルを使用し、更新信号を前記予測した奇数のポリフェーズ・サンプルと前記同じ方向の角度にそって選択して、更新されることを特徴とする請求項２に記載のシステム。
【請求項４】
エントロピー被符号化係数、方向角度およびモードをビットストリームへ出力するプログラム・モジュールをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項５】
前記第一の１次元変換の前記角度が第二の１次元変換の角度に対して垂直でないことを特徴とする請求項２に記載のシステム。
【請求項６】
前記入力信号についてのエントロピー被符号化バージョンは、
前記入力信号の前記エントロピー被符号化バージョン、方向角度、およびモードをエントロピー復号化すること、
前記入力信号を２つの１次元信号に分割すること、
各１次元信号に対して、
前記予測した奇数ポリフェーズ・サンプルおよび更新される偶数ポリフェーズ・サンプルの前記係数群を抽出すること、
前記予測した奇数のポリフェーズ・サンプルを角度とモードの復号にしたがって使用し、および更新される偶数のポリフェーズ・サンプルを使用して元の偶数のポリフェーズ・サンプルを抽出すること、
前記元の偶数のポリフェーズ・サンプルを角度およびモードの復号にしたがって使用し、および予測された奇数のポリフェーズ・サンプルを使用して前記元の奇数のポリフェーズ・サンプルを抽出すること
によって前記信号を復号し、
前記偶数および奇数のポリフェーズ・サンプルを組み合わせて１次元ウェーブレット変換を作成すること、および
前記復号化された１次元信号に基づいて画像を作成すること、
により復号化されることを特徴とする請求項２に記載のシステム。
【請求項７】
前記予測信号は、方向角度およびモードにより定義される偶数ポリフェーズ・サンプルから選択されることを特徴とする請求項２に記載のシステム。
【請求項８】
前記方向角度は、前記偶数ポリフェーズ・サンプルの更新で使用され、前記角度データを符号化するために必要なビット数を最小にすることを特徴とする請求項７に記載のシステム。
【請求項９】
前記予測信号または前記更新信号は、端数サンプルから生ずることを特徴とする請求項２に記載のシステム。
【請求項１０】
前記端数サンプルは、補間アプローチで計算されることを特徴とする請求項９に記載のシステム。
【請求項１１】
2006074733.tif 000027
【数１】
2006074733.tif 000028
と記述されることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記予測および更新されるサンプルは、整数として表されることを特徴とする請求項２に記載のシステム。
【請求項１３】
前記方向データは、前記画像の画素のブロックを使用する方向角度を採用することにより推定されることを特徴とする請求項２に記載のシステム。
【請求項１４】
前記方向データは、
１つの画像ブロックを、ブロックモードのブロックが次第に小さくなる３つの組、すなわち、第一のブロックモードは、画素群からなる大きなブロックであり、第二のブロックモードは、画素群からなる前記第一のブロックより小さく、および第三のブロックモードは、画素群からなる前記第二の画素のブロックのサブセットであり、また、前記第一のブロックモードにおける全画素は同じ方向角度を有し、前記第三のブロックモードの各ブロックは１６の方向角度を有し、前記第三のブロックモードの全画素は同じ方向角度を共有する、３つの組に区分すること、
前記垂直方向におけるウェーブレット変換のための前記方向角度を、ｈ（ｍ，ｎ）が垂直方向に前記ウェーブレット変換後の高域通過係数、Ｒνが前記ブロックモードおよび方向角度を符合化するビット数、λνが最適化係数、および（ｍ0，ｎ0）がｈ（ｍ，ｎ）の左上画素の座標であるとして、
【数２】
2006074733.tif 000029
によって推定すること、
前記水平方向におけるウェーブレット変換のための前記方向角度を、ｌｈ（ｍ，ｎ）が低高サブバンドの係数、Ｒhが前記モードおよび方向角度を符合化するビット数、λhが最適化係数、および（ｍ1，ｎ1）がｌｈ（ｍ，ｎ）の左上画素の座標であるとして
【数３】
2006074733.tif 000030
によって推定すること
ここでこと、
を特徴とする請求項１３に記載のシステム。
【請求項１５】
前記第一ブロックモードのブロックのサイズは１６ｘ１６画素であること、前記第二ブロックモードのブロックのサイズは８ｘ８画素であること、および前記第三ブロックモードのブロック・サイズは４ｘ４画素であることを特徴とする請求項１４に記載のシステム。
【請求項１６】
ブロックの前記方向角度は、隣接ブロックの前記方向角度を使用することによって符号化され、それぞれ角度ｂおよび角度ｄを持つ２つのブロックの第一の列を第二の列の上に、前記第一の列の下に角度ａおよび角度ｃを持つその２つのブロックの前記第二列を与えられて、角度ｂとｄとの間の絶対差が角度ｂとａとの間の絶対差より大きい場合には、角度ａを予測値として使用するか、そうでない場合には、角度ｄを予測値として使用することを特徴とする請求項１３に記載のシステム。
【請求項１７】
前記入力信号はビデオ信号を備えたことを特徴とする請求項１に記載のシステム。
【請求項１８】
画像データを符号化するコンピュータ実装プロセスであって、入力信号を受信し、その入力信号に対応した量子化係数の出力の少なくとも一部が、マトリックス・リフティングおよび前記画像のエッジに対応する方向予測を介して得られる可逆変換に基づく、量子化係数の出力を提供する可逆変換構成要素を使用するプロセス・アクションを備えることを特徴とするプロセス。
【請求項１９】
入力信号を受信し、入力信号に対応する量子化係数の出力の少なくとも一部が、マトリクスリフテイングおよび前記画像のエッジに対応する方向予測を介して得られた可逆変換に基づく量子化係数の出力を提供する可逆変換構成要素を使用するプロセス・アクションは、
２次元（２Ｄ）信号を入力すること、および
前記２次元信号の変換を実行することであって、方向予測および少なくとも１つのリフテイング・ウェーブレットを使用して、
垂直方向に１次元（１Ｄ）ウェーブレット変換を行うこと、
水平方向に１次元ウェーブレット変換を行うこと、
を備え、
各１次元ウェーブレット変換は、
前記垂直方向の前記１次元ウェーブレット変換を偶数および奇数のポリフェーズ・サンプルに分割すること、
近傍の偶数ポリフェーズ・サンプルから奇数ポリフェーズ・サンプルを、予測信号を前記画像内のエッジに沿った角度に方向選択して、予測すること、および
前記予測した前記奇数ポリフェーズ・サンプルを使用し、更新信号を前記画像内のエッジに沿った角度に方向選択して偶数ポリフェーズ・サンプルを更新すること、
前記予測したおよび偶数のポリフェーズ・サンプルの前記係数を出力すること
を備えた前記２次元信号の変換を実行すること、および
前記出力係数および前記画像のエッジを表す角度をエントロピー符号化し、それによって入力信号の被符号化バージョンを整数形式で生成すること
を備えることを特徴とする請求項１８に記載のコンピュータ実装プロセス。
【請求項２０】
前記画像の前記エッジを表す前記角度は、画像データのブロックを使用して計算されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２１】
画像データの前記ブロックを表すモードは、前記出力された係数および前記画像の前記エッジを表す角度に関してエントロピー符号化されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２２】
前記プロセス・アクションは、コンピュータ可読媒体に格納されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２３】
前記入力信号は画像信号を備えることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２４】
前記入力信号はビデオ信号を備えることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２５】
前記垂直方向または前記水平方向のいずれかで１次元ウェーブレット変換を行う際に、ハール（Haar）フィルタが使用されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２６】
前記垂直方向または前記水平方向のいずれかで１次元ウェーブレット変換を行う際に、５／３フィルタが使用されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２７】
前記垂直方向または前記水平方向のいずれかで１次元ウェーブレット変換を行う際に、９／７フィルタが使用されることを特徴とする請求項１９に記載のコンピュータ実施プロセス。
【請求項２８】
前記偶数ポリフェーズ・サンプルから得られるｘ（ｍ，２ｎ＋１）の前記予測は、ｔｇ()＝ｓｉｎ()／ｃｏｓ()であるとすると、
【数４】
2006074733.tif 000031
により計算されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項２９】
前記偶数ポリフェーズ・サンプルの前記予測は、
【数５】
2006074733.tif 000032
として与えられることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項３０】
前記画像の前記エッジを表す前記角度は、
画像データの複数のブロックからなる１組の各ブロックに対して、
前記垂直方向の複数の候補角度および複数の画像ブロックサイズモードからなる１組から最良の予測角度および画像ブロック・サイズを見つけること、
１次元垂直変換の実行時に、前記垂直方向の最良の予測および画像ブロックモードを使用すること、
前記水平方向の一組の候補角度および画像ブロックサイズモードから最良の予測角度および画像ブロック・サイズを見つけること、および
前記１次元水平変換の実行時、前記水平方向の最良の予測および画像ブロックモードを使用すること
の各プロセス・アクションにより推定されることを特徴とする請求項１９に記載のコンピュータ実装プロセス。
【請求項３１】
画像内のエッジの空間相関を表す角度に基づく方向予測、少なくともひとつのリフテイング・ウェーブレット、および画像ブロックのサイズを表すモードを使用して得られた入力信号のエントロピー被符号化バージョンを復号するコンピュータ実装プロセスであって、
前記入力信号、方向角度、およびモードからなる前記エントロピー被符号化バージョンをエントロピー復号し、
前記入力信号を２つの１次元信号に分割し、
各１次元信号に対して、
予測した奇数ポリフェーズ・サンプルおよび更新される偶数ポリフェーズ・サンプルの係数を抽出すること、
予測した奇数ポリフェーズ・サンプルを復号角度およびモードにしたがって使用し、および更新される偶数ポリフェーズ・サンプルを使用して元の偶数ポリフェーズ・サンプルを抽出すること、
元の偶数ポリフェーズ・サンプルを角度およびモードの復号に準じて使用し、および予測した奇数ポリフェーズ・サンプルを使用して元の奇数ポリフェーズ・サンプルを抽出すること、
によって前記信号を復号し、
偶数および奇数ポリフェーズ・サンプルを組み合わせて１次元ウェーブレット変換を作成し、かつ
復号された１次元信号に基づいて画像を作成する
プロセス・アクションを備えるコンピュータ実装プロセス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像データを符号化および復号化するシステムおよび方法に関する。より詳細には、ハイブリッド方向予測およびリフテイング・ウェーブレット技術の使用により画像内の空間相関を利用する改良された符号化および復号化方法に関する。この符号化方法は、ビデオ・シーケンスのフレーム内符号化を行うのに使用できる。
【背景技術】
【０００２】
画像圧縮はデジタルカメラの数の急速な増大とともに現代生活で重要な役割を果たしつつある。多くの圧縮スキームが過去数10年間に開発されてきた。これらは初期には、差分パルス符号変調（ＤＰＣＭ）をベースにしたもの（参照資料[１]）、離散コサイン変換（ＤＣＴ）をベースにした圧縮スキーム（参照資料［１］〜［４］）、およびウェーブレットをベースにした圧縮技術（参照資料［５］〜［２０］）を含む。ＪＰＥＧ（参照資料［１］）のようなＤＣＴをベースにしたスキームは通常、低計算ソリューション（low computational solution）を提供するが、それらには所望のスケーラビリティを実現する上で困難性がある。
【０００３】
ＤＣＴをベースにした圧縮スキームと比較して、ウェーブレットをベースにしたスキームにはより大きな計算能力が、通常、必要とされる。他方、ウェーブレット変換（参照資料［２１］）は空間周波数ドメインにおける画像のマルチスケール表現を提供する。圧縮を容易にするエネルギー圧縮および非相関特性を別にして、ウェーブレット変換の主要な利点は、その固有のスケーラビリティである。たとえば、ウェーブレットをベースにしたＪＰＥＧ２０００標準（参照資料［７］）は、ＤＣＴをベースにしたＪＰＥＧ標準以上のより優れた圧縮性能を提供するだけでなく、速度のスケーラビリティ、民生用アプリケーションおよびネットワーク・アプリケーションに対して非常に望ましい品質および分解能（resolution）を提供する。
【０００４】
しかし実際のところ、自然の画像は、ローカル・レベルで通常は線形エッジ（linear edge）に近似することができる方向属性を豊富に含んでいる。これらのエッジは垂直でも水平でもない可能性がある。ただし、最も主流の画像符号化スキームはそのような事実を考慮に入れていない（参照資料［１］、［５］〜［７］）。２次元（２Ｄ）ＤＣＴまたはウェーブレット変換は常に水平および垂直方向で行われる。これは高周波係数に大きな重要性をもたらす。さらに、低ビットレートで、周知のギブス（Ｇｉｂｂｓ）のアーティファクトのように、画像エッジで量子化効果を明瞭に観察できる。この問題は、多くの研究者によって明確に理解されている（参照資料［３］、［４］、［８］〜［２０］）。Ｆｅｉｇ他は、フラクタルをベースにした画像圧縮と同様の方法のＪＰＥＧ風のコードに空間予測を導入した（参照資料［３］）。その方法は、ＰＳＮＲ／ビットレートのトレードオフの観点では、純粋なＤＣＴをベースにした方法より性能が優れているわけではない。しかしながら、非常に低いビットレートでは、その方法ははるかに少ないブロック・アーティファクトおよび著しく良好な視覚的品質をもたらす。Ｋｏｎｄｏ他は、４つの符号化された隣接するＤＣＴブロックのうちの１つから予測することができる、ＤＣＴブロックに関する方向予測を行った（参照資料［４］）。新しいビデオ符号化標準Ｈ．２６４では、ブロックをベースにした空間予測技術をフレーム内符号化にうまく適用した。それは、空間予測の無い場合のコーディング効率を越えた、符号化効率上の著しく進歩を示した（参照資料［２２］）。
【０００５】
ウェーブレット／サブバンド符号化スキームにおけるこの問題を調査した多くの人々が存在する。Ｉｋｏｎｏｍｏｐｏuｌｏｓ他は異なる方向でのテクスチャ相関に適合させる、複数の方向フィルタからなる固定された一組を提案した（参照資料［８］）。Ｌｉ他はサブバンド分解をＩｋｏｎｏｍｏｐｏuｌｏｓのスキームに組み込んだ（参照資料［９］）。Ｂａｍｂｅｒｇｅｒ他は、矩形画像サンプリングに基づいたフィルタ・バンクを使用した（参照資料［１０］〜 ［１２］）。それにより画像を多くの様々な方向成分に分解できる。Ｃａｎｄｅｓ他により最近開発されたＲｉｄｇｅｌｅｔおよびＣｕｒｖｅｌｅｔは極性サンプリング（polar sampling）による別の種類の変換である（参照資料［１３］、［１４］）。Ｍａｈｅｓｈ他は六角形状にサンプリングされた画像を周波数および向き（orientation）の両方で選択するサブバンドに分解した（参照資料［１５］）。Ｔａｕｂｍａｎ他は、入力された画像がウェーブレット変換前に最初にリサンプリングされるスキームを提案した（参照資料［１６］）。このリサンプリング・プロセスでは水平または垂直方向に画像エッジを回転できる。Ｗａｎｇ他はＴａｕｂｍａｎ他からの同様の構想を使用したが、さらに、様々な方向領域の境界周囲のアーティファクトを符号化するのを防止するために、重複した拡張（overlapped extension）を提案した（参照資料［１７］）。ウェーブレットパケットに関する同様の研究が、参照資料［１８］および［１９］に報告されている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、リフティングをベースにしたウェーブレット変換における方向予測の使用を提案した著者はほとんどいない。ウェーブレット変換では２つの方法、すなわち、畳み込みをベースにした方法およびリフティングをベースにした方法が実行できる。リフティングの実装は、Ｄａｕｂｅｃｈｉｅｓによって提案されたた。Ｄａｕｂｅｃｈｉｅｓ他が開発したリフティング構造は、効率的でよく知られているウェーブレット変換の実行であり、ここでは、あらゆる有限インパルス応答（ＦＩＲ）ウェーブレット・フィルタをいくつかのリフティング段階に分解できる（参照資料［２３］）。ウェーブレット変換の畳み込みを実装することにより空間予測が大幅な困難をともなうことになる一方で、ウェーブレット技術は空間予測の組み込みを可能にする可能性を秘めている。しかしながら、Ｄａｕｂｅｃｈｉｅｓが提案した技術は空間的な方向情報をいずれも使用していない。Ｂｏｕｌｇｏｕｒｉｓ他は予測された誤差変動を最小にする適応性のあるリフティング技術を提案した（参照資料［２０］）。Ｉｋｏｎｏｍｏｐｏuｌｏｓからの構想と同様に、この技術では、ｑｕｉｎｃｕｎｘ  ｓａｍｐｌｉｎｇからいくつかの方向フィルタを導出し、中央操作（median operation）によりそれらの１つを選択する。しかし、可逆の画像符号化（lossless image coding）において著しい進歩を示してはいない。
【０００７】
従って、必要とされるものは、たとえば、画像内の空間相関を活用しかつ高い周波係数において大きな係数値をもたらさない方法を使用してビットストリームが符号化される、ビデオ・データなどの画像データを符号化または復号化するシステムおよび方法である。このシステムおよび方法は、計算処理上効率的なものでなければならない。
【課題を解決するための手段】
【０００８】
本発明は画像データを符号化する、及び/または復号化するコーデックに使用するシステムおよび方法に関する。本発明のシステムおよび方法では、方向空間予測を従来のリフティングをベースにしたウェーブレット変換に組み込む。本発明のシステムおよび方法は、新規の効率的かつ柔軟性のあるデジタル信号処理（ＤＳＰ）リフティング技術を備える。本発明のシステムおよび方法のＤＳＰリフティングはよく知られているハール（Haar）、５／３および９／７フィルタを使用することができるが、他のリフティング・スキームにはない特性をいくつか有する。たとえば、各リフティング段階での予測または更新信号は、それらが他のリフティング・スキームで通常行われるような水平または垂直のサンプルから必ずしも生ずるわけではない。予測または更新信号は高域係数（high-pass coefficients）の大きさを縮小することができるようにするために、画像の線形エッジに沿って選択できる。さらに、正確な空間予測の目的のため、予測または更新信号は、いずれかの補間的アプローチにより計算できる端数サンプル（fractional samples）から生成することもできる。即ち、本発明のＤＳＰリフティング技術には補間のアプローチに関する制約はない。さらに、完全な再構成を保証するため、予測かつ更新されたサンプルは整数として表される。２次元変換を２つの１次元変換に分割する場合、２つの１次元変換は、ＤＳＰリフティングでは必ずしも垂直である必要はない。しかし、４つの矩形サブバンドを生成することができるように、その分割は水平および垂直方向で行われる。
【０００９】
本発明の符号化システムの１つの実施形態は、次のように機能する。システムに２次元（２Ｄ）信号を入力する。次に、この２次元信号を方向予測およびリフテイング・ウェーブレットを使用して変換する。さらに詳細には、方向予測およびリフテイング・ウェーブレットを使用する２次元信号の変換は、垂直方向に１次元ウェーブレット変換を行うこと、および水平方向に１次元ウェーブレット変換を行うことを含む。次に、各１次元の垂直および水平ウェーブレット変換を偶数および奇数のポリフェーズ・サンプルに分割する。奇数のポリフェーズ・サンプルを、画像のエッジに沿って選択される予測信号を使用することにより、隣接する偶数のポリフェーズ・サンプルから予測する。次に、偶数のポリフェーズ・サンプルを、予測された奇数のポリフェーズ・サンプル（予測された残差とも呼ばれる）および予測した奇数のポリフェーズ・サンプル（例えば、残差）の係数を使用して更新し、更新された偶数のポリフェーズ・サンプルを出力してエントロピー符号化する。このエントロピー被符号化係数をビットストリームへ出力することができる。
【００１０】
本発明のシステムおよび方法は方向データを効率的に推測しかつ符号化する技術を使用し、それ故、空間予測の精度を向上させ、かつオーバヘッドのビット数を低減する。このことは、本発明のＤＳＰリフティング・スキームの高性能を達成するキー・ポイントである。本発明の１つの実施形態で、この符号化／復号化スキームは、ＪＰＥＧ２０００のようなコーデックに実装され、ＤＳＰリフティングが従来のリフティングの代わりをする。
【００１１】
上記で説明した利点に加え、本明細書に添付する図面を参照すると、以下に記載の詳細な説明から本発明の他の利点が明らかになるだろう。
【発明を実施するための最良の形態】
【００１２】
本発明の特定の特性、態様、および利点は以下の明細書本文、添付された特許請求の範囲、および添付図面を参照することにより、より良く理解できるであろう。
【００１３】
本発明の好ましい実施形態の以下の説明では、本明細書の一部を形成しかつ本発明が実施される特定の実施形態を図示することにより示される添付図面を参照する。他の実施形態を使用することもあり、本発明の範囲から逸脱することなく構造が変化する場合もあることとする。
【００１４】
本明細書の残り部分における説明に関しては、一対の括弧内に含まれた数値の指示子により特定された各種の個別刊行物を参照することとする。たとえば、このような参照資料は「参照資料［１］」または単に「［１］」を挙げることにより特定できる。各数値の指示子に対応する刊行物の一覧表を「発明の詳細な説明」部分の最終部に示す。
【００１５】
１．０  例示的なオペレーティング環境
図１は本発明が実行されるのに適当なコンピューティング・システム環境１００の実施例を示す。コンピューティング・システム環境１００は適当なコンピューティング環境の１つの実施例にすぎず、本発明の用途または機能性の適用範囲に関する何らかの制限を示唆するように意図されるものではない。コンピューティング・システム環境１００は、例示的なオペレーティング環境１００に示したコンポーネントのいずれか１つ又は組合せに関する何らかの依存性または要件を有するものとして解釈されるべきではない。
【００１６】
本発明は他の多数の汎用または特別目的のコンピューティング・システム環境または構成で動作する。本発明とともに使用するのに適当な周知のコンピューティング・システム、環境、及びまたは構成の実施例は、パーソナル・コンピュータ、サーバ・コンピュータ、ハンドヘルドまたはラップトップ・デバイス、マルチ・プロセッサ・システム、マイクロ・プロセッサをベースにしたシステム、セットトップボックス、プログラム可能なコンシューマ・エレクトロニクス、ネットワークＰＣ、ミニ・コンピュータ、メインフレーム・コンピュータ、上記システムまたは装置などのいずれかを含む分散コンピューティング環境などを含むが、これらに制限されるものではない。
【００１７】
本発明をコンピュータにより実行されるプログラム・モジュールなどのコンピュータ実行可能命令の一般的な文脈で説明してもよい。一般的に、プログラム・モジュールは特定タスクを実行するか、または特定抽象データ型を実行するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。通信ネットワークを通して連結されるリモート処理装置によりタスクを行う分散コンピューティング環境で本発明を実行してもよい。分散コンピューティング環境では、メモリ・ストレージ・デバイスを含むローカルおよびリモート・コンピュータ・ストレージ媒体にプログラム・モジュールを配置してもよい。
【００１８】
図１において、本発明を実行する例示的なシステムはコンピュータ１１０の形の汎用コンピューティング・デバイスを含む。コンピュータ１１０のコンポーネントは、処理ユニット１２０、システム・メモリ１３０、およびシステム・メモリを含む各種システム・コンポーネントを処理ユニット１２０に結合するシステム・バス１２１を含んでもよいが、これらに制限されるものではない。システム・バス１２１はメモリ・バスまたはメモリ・コントローラ、周辺バス、および多様なバス・アーキテクチャのいずれかを使用するローカル・バスを含む数種類のバス構造のいずれでもよい。一例として、このようなアーキテクチャはインダストリアル・スタンダード・アーキテクチャ（ＩＳＡ）バス、マイクロ・チャネル・アーキテクチャ（ＭＣＡ）バス、エンハンストＩＳＡ（ＥＩＳＡ）バス、ビデオ・エレクトロニクス・スタンダーズ・アソシエーション（ＶＥＳＡ）ローカル・バス、およびメザニ・ンバスとして公知のペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バスを含むが、これらに制限されるものではない。
【００１９】
コンピュータ１１０は典型的に多様なコンピュータ可読媒体を含む。コンピュータ可読媒体はコンピュータ１１０によりアクセス可能であり、かつ揮発性および不揮発性媒体、取り外し可能かつ取り外し不可能な媒体の両方を含む、利用可能な媒体である。実施例として、コンピュータ可読媒体はコンピュータ・ストレージ媒体および通信媒体を含んでもよいが、これらに制限されるものではない。コンピュータ・ストレージ媒体はコンピュータ可読命令、データ構造、プログラム・モジュールまたは他のデータなどの情報のストレージ方法または技術により実行された揮発性および不揮発性媒体、取り外し可能かつ取り外し不可能な媒体の両方を含む。コンピュータ・ストレージ媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ディスク装置、磁気カセット、磁気テープ、磁気ディスク・ストレージまたは他の磁気ストレージ・デバイス、または所望の情報を格納するため使用されかつコンピュータ１１０によりアクセスされる他の媒体を含むが、これらに制限されるものではない。通信媒体は、コンピュータ可読命令、データ構造、プログラム・モジュール、または搬送波または他のトランスポート機構などの変調データ信号における他のデータを具体化し、かついずれかの情報配信媒体を含むのが典型的である。「変調データ信号（modulated data signal）」という用語は、信号の情報を符号化するような方法で設定または変更された１つまたは複数の特性を有する信号を意味する。実施例として、通信媒体は有線ネットワークまたは直接有線接続などの有線媒体、および音波、ＲＦ、赤外線および他の無線媒体などのような無線媒体を含むが、これらに制限されるものではない。上記のいずれの組合せもコンピュータ可読媒体の範囲内に含まれなければならない。
【００２０】
システム・メモリ１３０はリード・オンリ・メモリ（ＲＯＭ）１３１およびランダム・アクセス・メモリ（ＲＡＭ）１３２などの揮発性及び/または不揮発性メモリの形のコンピュータ・ストレージ媒体を含む。起動中などの、コンピュータ１１０内の要素間の情報伝送を支援する基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ）は、ＲＯＭ１３１に格納するのが典型的である。ＲＡＭ１３２は、直ちにアクセス可能な及び/または処理装置１２０により現在動作しているデータ及び/またはプログラム・モジュールを含むのが典型的である。実施例として、図１はオペレーティング・システム１３４、アプリケーション・プログラム１３５、他のプログラム・モジュール１３６、およびプログラム・データ１３７を示すが、これらに制限されるものではない。
【００２１】
コンピュータ１１０は他の取り外し可能／取り外し不可能な、揮発性／不揮発性のコンピュータ・ストレージ媒体も含む。一例として、図１は取り外し不可能な不揮発性の磁性媒体から読み取りかつそれに書き込みのできるハードディスク・ドライブ１４１、取り外し可能な不揮発性の磁気ディスク１５２から読み取りかつそれに書き込みのできる磁気ディスク・ドライブ１５１、およびＣＤ−ＲＯＭまたは他の光媒体などのような取り外し可能な不揮発性の光ディスク１５６から読み取りかつそれに書き込みのできる光ディスク・ドライブ１５５を示す。例示的なオペレーティング環境で使用できるその他の取り外し可能／取り外し不可能で、揮発性／不揮発性のコンピュータ・ストレージ媒体は、磁気テープ・カセット、フラッシュ・メモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどを含むが、これらに制限されるものではない。ハードディスク・ドライブ１４１に関しては、インターフェース１４０などの取り外し不可能なメモリ・インターフェースを通してシステム・バス１２１へ接続するのが典型的であり、かつ磁気ディスク・ドライブ１５１および光ディスク・ドライブ１５５に関しては、インターフェース１５０などの取り外し可能なメモリ・インターフェースによりシステム・バス１２１へ接続するのが典型的である。
【００２２】
ドライブ、および上記で考察しかつ図１に示したドライブの関連コンピュータ・ストレージ媒体は、コンピュータ可読命令、データ構造、プログラム・モジュールおよびコンピュータ１１０用の他のデータのストレージを提供する。たとえば、図１では、ハードディスク・ドライブ１４１はオペレーティング・システム１４４、アプリケーション・プログラム１４５、他のプログラム・モジュール１４６、およびプログラム・データ１４７を格納するものとして示される。これらのコンポーネントはオペレーティング・システム１３４、アプリケーション・プログラム１３５、他のプログラム・モジュール１３６、およびプログラム・データ１３７と同じか、またはそれとは異なるということに留意する。本明細書において、 オペレーティング・システム１４４、アプリケーション・プログラム１４５、他のプログラム・モジュール１４６、およびプログラム・データ１４７は異なる番号が与えられ少なくともそれらが異なる複製品であることを示している。ユーザはコマンドおよび情報をキーボード１６２および通常はマウス、トラック・ボールまたはタッチ・パッドと呼ばれるポインティング・デバイス１６１などの入力装置を通してコンピュータ１１０に入力してもよい。その他の入力装置（図示せず）にはマイクロフォン、ジョイスティック、ゲームパッド、サテライト・ディッシュ、スキャナなどを含んでよい。上記の、またその他の入力装置を、システム・バス１２１に結合されるユーザ入力インターフェース１６０を通して処理装置１２０へ接続する場合が多いが、パラレル・ポート、ゲーム・ポートまたはユニバーサル・シリアル・バス（ＵＳＢ）などのその他のインターフェースおよびバス構造により接続することもある。モニタ１９１または他の形式の表示装置もビデオ・インターフェース１９０のようなインターフェースを介してシステム・バス１２１へ接続する。モニタの他に、コンピュータは出力周辺インターフェース１９５を通して接続されるスピーカ１９７およびプリンタ１９６などの他の周辺出力装置も含んでもよい。本発明にとって特に重要なことは、一連の画像１６４を取り込むことができるカメラ１６３（デジタル／電子式スチルまたはビデオ・カメラ、またはフィルム／写真スキャナなど）がパーソナル・コンピュータ１１０に入力装置として含まれることである。さらに、ただ１つのカメラが示されるが、複数のカメラをパーソナル・コンピュータ１１０に入力装置として含むことができる。１つまたは複数のカメラからの画像１６４が適切なカメラ・インターフェース１６５を介してコンピュータ１１０に入力される。このインターフェース１６５をシステム・バス１２１へ接続し、それによって画像をＲＡＭ１３２、またはコンピュータ１１０に接続された他のデータ・ストレージ・デバイスの１つに送り、かつ格納する。しかしながら、カメラ１６３を使用する必要なく、上述のコンピュータ可読媒体のいずれかから画像データをコンピュータ１１０に入力できるということに留意する。
【００２３】
コンピュータ１１０はリモート・コンピュータ１８０などの１つまたは複数のリモート・コンピュータへの論理接続を使用してネットワーク化された環境で動作してもよい。リモート・コンピュータ１８０はパーソナル・コンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア・デバイスまたは他の共通ネットワーク・ノードでもよく、図１にはメモリ・ストレージ・デバイス１８１のみが示されているが、コンピュータ１１０に関連する上記に説明した要素の多くまたはすべてを含むのが典型的である。図１に示した論理接続はローカル・エリア・ネットワーク（ＬＡＮ）１７１およびワイド・エリア・ネットワーク（ＷＡＮ）１７３を含むが、その他のネットワークも含む。このようなネットワーク環境はオフィス、企業規模のコンピュータ・ネットワーク、イントラネット、およびインターネットでは一般的である。
【００２４】
ＬＡＮネットワーク環境で使用される場合、コンピュータ１１０がネットワーク・インターフェースまたはアダプタ１７０を通してＬＡＮ１７１へ接続される。ＷＡＮネットワーク環境で使用される場合、コンピュータ１１０はモデム１７２またはインターネットなどのＷＡＮ１７３上に通信を設定するための他の手段を含むのが典型的である。内部または外部のモデム１７２をユーザ入力インターフェース１６０、または他の適切な機構を介してシステム・バス１２１へ接続してもよい。ネットワーク化された環境では、コンピュータ１１０またはその一部に対して示したプログラム・モジュールをリモート・メモリ・ストレージ・デバイスに格納してもよい。一例として、図１はメモリ装置１８１に備わっているようなリモート・アプリケーション・プログラム１８５を示すが、これに制限されるものではない。上記のネットワーク接続は例示的なものであり、コンピュータ間の通信リンクを設定する他の手段を使用してもよい。
【００２５】
ここでは例示的なオペレーティング環境を考察してきたが、本明細書部分の残りの部分は本発明を具体化するプログラム・モジュールの説明に専念する。
【００２６】
２．０  ハイブリッド方向予測およびリフテイング・ウェーブレットを使用して画像符号化するシステムおよび方法
本発明の画像符号化システムおよび方法を以下の段落でより詳細に考察する。本発明の概要は、従来のリフティング技術の概要に沿って提供される。本発明の方向予測およびリフティング技術を従来のリフティングに対して対比かつ詳述する。補間方法、予測角度推測、および符号化も考察する。最後に、本発明の例示的な、正常に機能する実施形態も考察する。
【００２７】
２．１  発明の概要
本発明のシステムおよび方法の概要を図２に示す。プロセス・アクション２０２に示すように、画像を表す２次元（２Ｄ）信号をシステムに入力する。次に、プロセス・アクション２０４に示しかつ図３に詳述するように、画像内のエッジに基づく方向予測、およびリフテイング・ウェーブレットを使用して、この２次元信号を変換する。次に、この変換の係数を出力し（プロセス・アクション２０６）、エントロピー符号化する（プロセス・アクション２０８）。その後、プロセス・アクション２１０に示すようにエントロピー被符号化係数をビットストリームへ出力する。
【００２８】
図３に示すように、方向予測およびリフテイング・ウェーブレットを使用する２次元信号の変換は、垂直方向の１次元ウェーブレット変換を行うステップ（プロセス・アクション３０２）および水平方向の１次元ウェーブレット変換を行うステップ（プロセスアクション３０４）を含む。これらの２つのプロセス・アクションの順序を上下しても構わないものとする。
【００２９】
プロセス・アクション３０２および３０４の詳細は次の通りである。プロセス・アクション３０６に示すように、第一の１次元ウェーブレット変換を垂直方向に沿って偶数および奇数のポリフェーズ・サンプルに分割する（プロセス・アクション３０６）。「予測された残差」または奇数のポリフェーズ・サンプルを、画像のエッジに沿って選択される予測信号を使用することにより、隣接する偶数のポリフェーズ・サンプルから予測する（プロセス・アクション３０８）。次に、予測された奇数のポリフェーズ・サンプルを使用して、偶数のポリフェーズ・サンプルを更新する。ここでは、更新信号が前記の予測ステップと同じ方向に沿って選択される（プロセス・アクション３１０）。
【００３０】
同様に、第二の１次元ウェーブレット変換を水平方向に沿って偶数および奇数のポリフェーズ・サンプルに分割する（プロセス・アクション３１２）。画像のエッジに沿って選択される予測信号を使用することにより、隣接する偶数のポリフェーズ・サンプルから、「予測された残差」または奇数のポリフェーズ・サンプルを予測する（プロセス・アクション３１４）。その後、予測された奇数のポリフェーズ・サンプルを使用して、偶数のポリフェーズ・サンプルを更新する、ここでは、更新信号が前記の予測ステップと同じ方向に沿って選択される、（プロセス・アクション３１６）。次に、「予測された残差」および更新された偶数のポリフェーズ・サンプルの係数を図２に示すように出力する。
【００３１】
本発明のシステムおよび方法は、効率的かつ柔軟性のあるＤＳＰリフティングの画像符号化技術を提供するために、従来のリフティングをベースにしたウェーブレット変換に方向空間予測を組み込む。本発明のいくつかの実施形態では、よく知られているハール、５／３および９／７フィルタを使用する。しかしながら、本発明のシステムおよび方法は他のリフティング・スキームで以前使用されなかった次の特徴を有する。
【００３２】
●各リフティング段階で、予測または更新信号が必ずしも水平および垂直のサンプルから生ずるとは限らない。高域係数（high-pass coefficients）の大きさを縮小することができるように、画像の線形エッジに沿ってそれらの信号を選択する。  
●正確な空間予測の目的のため、予測または更新信号は、既存の補間技術で計算される端数サンプル（fractional sample）から生成することができる。本発明のリフティング方法には補間的アプローチに関する制約はない。  
●完全な再構成を保証するため、予測または更新されたサンプルは常に整数位置にある。  
●２次元変換を２つの１次元変換に分離する場合、２つの１次元変換は本発明のＤＳＰリフティングでは必ずしも垂直である必要はない。たとえば、従来のリフティングでは、２つの１次元変換を常に水平および垂直方向で行う。デフォルトは、第二の１次元変換が第一の１次元変換に対して垂直方向である。しかし、多くの場合、第一の１次元変換をある一定の方向に沿って行う場合には、第二の１次元変換における垂直方向は最良の予測ではなくなる。本発明によるシステムおよび方法では、第二変換は最良の予測方向を自由に選択し、かつ第一の１次元変換の方向によって制限されない。しかし、サンプルの奇数および偶数のポリフェーズ・サンプルへの分割は水平および垂直方向で行い、その結果、４つの矩形サブバンドを発生させる。
【００３３】
さらに、本発明のシステムおよび方法は方向データを効率的に推測し、かつ符号化する技術を使用し、それ故、空間予測の精度を向上させ、かつオーバヘッドのビット数を低減する。これは本発明のＤＳＰリフティング・スキームにおける高性能を達成するキー・ポイントである。本発明の１つの実施形態は、ＤＳＰリフティングが従来のリフティングの代わりをするＪＰＥＧ２０００のようなコーデックで実行される。
【００３４】
本発明と従来のリフティング技術との間の相違を完全に理解するため、以下に従来のリフティングの概要を説明しかつ対比する。
【００３５】
２．２  従来のリフティングの概要
参照資料［２３］におけるＤａｕｂｅｃｈｉｅｓ他により提案された従来のリフティングを本発明によるシステムおよび方法を考察する開始位置として再考する。特別な画像が先行技術のウェーブレット／サブバンド画像符号化スキームにおける既存の問題を明瞭に示すために使用される。ウェーブレット変換の基本構想はわずかな近似を構築するための最も現実的な信号に存在する相関構造を活用することである。隣接するサンプルおよび周波数は遠く離れたサンプルおよび周波数よりも大きく相関する。
【００３６】
ｘ（ｍ，ｎ）m,nεZを２次元信号とする。一般性を失うことなく、この信号を最初に垂直方向に１次元ウェーブレット変換で動作され（たとえば、垂直ウェーブレット分解が画像の各横列に関して行われる）、次に、水平方向に動作される（たとえば、水平ウェーブレット分解が画像の各縦列に関して行われる）と仮定する。参照資料［２３］における技術にしたがって、各１次元ウェーブレット変換を１つまたは複数のリフティング段階に分解する。リフティングは、空間ドメイン技術を使用して与えられた信号を分析かつ合成する方法と考えられる。一般に、典型的なリフティング段階は３段階、即ち、分割、予測、および更新から成る。分割段階では、入力信号を２つの互いに素な集合、奇数および偶数のサンプルに分割する。予測段階では、偶数のサンプルを使用して奇数の係数を予測する。この予測値が奇数の係数から減算され、予測に誤差が生じる。更新ステップでは、更新関数を通して渡される偶数の係数の更新を行う予測における誤差と、偶数の係数とが組み合わされる。リフティングステップの順序は容易に逆になる。即ち、誤差予測の係数および偶数の係数の更新からの元信号を再構成することができる。
【００３７】
より正確にいえば、リフティング段階を垂直の１次元ウェーブレット変換に対して以下により詳細に説明する。
【００３８】
最初に、垂直の１次元ウェーブレット変換のすべてのサンプルを２つの部分、即ち、偶数のポリフェーズ・サンプルおよび奇数のポリフェーズ・サンプル
【００３９】
【数１】
2006074733.tif 000003
【００４０】
に分割する。
【００４１】
予測ステップでは、隣接する偶数のポリフェーズ・サンプルから奇数のポリフェーズ・サンプルを予測する。予測された残差ｈ（ｍ，ｎ）を次の方程式により計算する。
【００４２】
【数２】
2006074733.tif 000004
【００４３】
ここでは垂直変換を考察しているため、各ｘp（ｍ，ｎ）の予測はｍ番目の縦列において隣接する偶数の係数の線形結合である。
【００４４】
【数３】
2006074733.tif 000005
【００４５】
ｐiが従来のリフティングでは変数ｍと無関係であることは留意に値する。従って、方程式（３）のインパルス応答関数は１次元形式として簡略化できる、即ち、
【００４６】
【数４】
2006074733.tif 000006
【００４７】
となる。ここで、ｚはＺドメインの変数、ｐiはウェーブレット・フィルタにより決定される予測パラメータである。一般に、係数の有限数ｐiがゼロでない場合のみＦＩＲウェーブレット・フィルタは考慮される。ここで、ｉbおよびｉeをそれぞれ最小および最大の整数ｉとする。ここで、ｐiはゼロでない。方程式（２）の計算後、ｘ（ｍ，ｎ）の新しい表現は、各ｘo（ｍ，ｎ）を予測された残差ｈ（ｍ，ｎ）で置き換えることにより得られる。それはｘ（ｍ，ｎ）と同等である。奇数のポリフェーズ・サンプルの予測および予測された残差が与えられると、方程式（２）により元の奇数のポリフェーズ・サンプルを完全に再構成できる。
【００４８】
更新ステップでは、偶数のポリフェーズ・サンプルが
【００４９】
【数５】
2006074733.tif 000007
【００５０】
で置き換えられる。
ここで、Ｕh（ｍ，ｎ）はｍ番目の縦列において隣接する予測された残差の線形結合
【００５１】
【数６】
2006074733.tif 000008
【００５２】
である。
同様に、方程式（６）の有限インパルス応答関数は以下の通りである。
【００５３】
【数７】
2006074733.tif 000009
【００５４】
ここで、ｊbおよびｊeはそれぞれ最小および最大整数ｊである。ここで、ｕjはゼロではない。ｕjはウェーブレット・フィルタにより決定される更新パラメータである。このステップの場合も先と同様に、自明に順序の変更が可能である。ｌ（ｍ，ｎ）およびｈ（ｍ，ｎ）があれば、偶数のポリフェーズ・サンプルを完全に再構成できる。
【００５５】
変数ｐiおよびｕjはフィルタリング・パラメータである。ゼロでないフィルタリング・パラメータの数およびそれらの大きさは通常、使用されるウェーブレット・フィルタにより変化する。しかしながら、異なるフィルタを備えた１次元リフティングをベースにした変換は普通、図４に示すようにフレームワークにより説明できる。図４ａは順方向リフティングをベースにした変換である。図４ｂは逆方向リフティングをベースにした変換である。変数ｋはリフティング段階の数である（ハールおよび５／３フィルタに対してはｋ＝１、９／７フィルタに対してはｋ＝２）。フィルタはリニア・タイムの不変量オペレータであり、そのインパルス応答により完全に決定される。有限インパルス応答フィルタ（ＦＩＲ）はフィルタ係数の有限数のみがゼロでない場合である。本発明のＤＳＰリフティング技術を従来のリフティングと比較する便宜上、ハール、５／３、および９／７のフィルタのＦＩＲ関数を以下のように一覧にする。
【００５６】
【数８】
2006074733.tif 000010
【００５７】
【数９】
2006074733.tif 000011
【００５８】
【数１０】
2006074733.tif 000012
【００５９】
水平の１次元リフティング変換は垂直のリフティング変換に対して上記に考察したのと同じ方法で行われるが、それはディメンションｍで動作する。上記考察から、方程式（３）および（６）の予測は常に隣接する整数サンプルの組み合わせ、または水平または垂直方向での高域係数（high-pass coefficients）の組み合わせである。符号化された画像が水平でも垂直でもない多くのエッジを有する場合、下記に考察される問題が生ずる。
【００６０】
問題を明瞭に説明するため、図５Ａに示すように、特別な画像を２次元ウェーブレット変換に対して使用する。それは４つの横列ブロック、即ち、第一の横列に水平の縞模様を有する４つの正方形ブロック、第二および第四の横列に傾斜した縞模様を有する４つの正方形ブロック、および第三の横列に垂直の縞模様を有する４つの正方形ブロックから成る。従来の２次元リフティング変換の後、図５Ｂ、５Ｃ、５Ｄ、および５Ｅに示される４つのサブバンドが得られる。これらのサブバンドは２次元ウェーブレットを低域通過フィルタおよび高域通過フィルタの両方を通過させることにより得られる。最初に、低域通過係数により特定された画像および高域係数により特定された画像を生ずる垂直の１次元変換により、２次元ウェーブレットを動作する。次に、低域通過係数および高域係数により特定された画像を生ずる水平の１次元変換により、２次元ウェーブレットを動作する。その後、これらの４つの画像を４つのサブバンドに組み合わせる。低高（ＬＨ）サブバンドにおいて、第一の横列だけを水平変換により完全に除去する。高低（ＨＬ）サブバンドにおいて、第三の横列だけを垂直変換により完全に除去する。高高（ＨＨ）サブバンドにおいて、水平および垂直の両変換後も傾斜した縞模様を有する横列が残る。それらの高域通過サブバンドが多くのテクスチャ情報を含むことが明瞭に観察される。このことは、低ビットレート時に、低符号化効率および不十分な視覚的品質をもたらすことになる。
【００６１】
２．３  本発明のハイブリッド方向予測およびリフテイング・ウェーブレットを使用した画像符号化するシステムおよび方法のリフティング構造
従来のリフティングと本発明によるシステムおよび方法のＤＳＰリフティングとの間にある基本的な相違は方程式（３）および（７）にある。従来のリフティングで行われる際、水平または垂直方向において常に予測を生成する代わりに、本発明のＤＳＰリフティング技術は局所的な空間相関を使用する。図６に示すように、画素は角度θνで強い相関を有すると仮定する。ここで、整数画素がマーカ「〇」により、半画素はマーカ「ｘ」により、かつ四分の一画素はマーカ「＋」により表される。本発明のＤＳＰリフティング・システムおよび方法では、ｘ（ｍ，２ｎ＋１）の予測は図６の矢印により指示された偶数のポリフェーズ・サンプルから得られる。これらは次のように計算される。
【００６２】
【数１１】
2006074733.tif 000013
【００６３】
ここで、ｔｇ()＝ｓｉｎ()／ｃｏｓ()である。
対応する有限インパルス応答関数は
【００６４】
【数１２】
2006074733.tif 000014
【００６５】
である。
常に偶数のポリフェーズ・サンプルから予測を計算するため、方向角度が既知の場合、ＤＳＰリフティングは方程式（２）により奇数のポリフェーズ・サンプルを完全に再構成できる。
【００６６】
更新ステップでは、本発明のＤＳＰリフティング技術は予測ステップにおける方向角度と同じ方向角度を使用して、角度データを符号化するため必要なビット数を最小にする。従って、偶数のポリフェーズ・サンプルの予測は
【００６７】
【数１３】
2006074733.tif 000015
【００６８】
である。
対応する有限インパルス応答関数は
【００６９】
【数１４】
2006074733.tif 000016
【００７０】
である。
明らかに、それは完全な再構成も保証する。
【００７１】
本発明のＤＳＰリフティング・システムおよび方法は、図６に示すようなフレームワークで同様に説明される様々なウェーブレット・フィルタで使用できる。ハール、５／３、および９／７についてのフィルタの提案されたＦＩＲ関数は以下の通りである。
【００７２】
【数１５】
2006074733.tif 000017
【００７３】
【数１６】
2006074733.tif 000018
【００７４】
【数１７】
2006074733.tif 000019
【００７５】
方程式（８）、（９）および（１０）と比較して、従来のリフティングは、本発明のＤＳＰリフティングの特別な場合と考察でき、この場合、θνはゼロに等しい。より詳細には、１次元ウェーブレット変換を、第一のリフティング段階以外のリフティング段階（たとえば、９／７フィルタ）以上に分解する場合、その前のリフティング段階が方向相関を除去しているためにθνをゼロに設定することにより、空間予測は、他の段階では無効にされることになる。
【００７６】
上記考察は本発明のＤＳＰリフティングにおける垂直の１次元変換に関連する。ディメンションｍにおける方法と同様の方法で水平変換が行われる。水平変換の方向角度θhはθνに対して垂直である必要はなく、その結果、水平変換は、分解に対する最良の方向を見出すことができることは留意に値する。
【００７７】
図８は本発明のＤＳＰリフティングの分解後の結果を示す。ＨＬサブバンドでは、垂直変換後に水平の縞模様を有する横列だけが残る。垂直および水平変換後、ＨＨサブバンドにはいかなる横列も残らない。垂直変換後のダウン・サンプリング・プロセスのため、本発明のＤＳＰリフティング技術は正確な予測方向を見つけることはできない。しかし、この場合でも、ＬＨサブバンドのエネルギーは従来のリフティング分解のエネルギーよりはるかに少ない。
【００７８】
２．４  補間
正確な空間予測目的のため、本発明のＤＳＰリフティングは、方向角度が端数画素（fractional pixels）を指し示すことが可能になる。言い換えれば、方程式（１２）および（１３）で使用されたｔｇ（θ）は整数ではない。従って、この場合は補間技術が必要とされる。
【００７９】
図６に示すように、ｘ（ｍ，２ｎ＋１）の予測ではｘ（ｍ−１，２ｎ＋２）およびｘ（ｍ，２ｎ＋２）間、およびｘ（ｍ，２ｎ）およびｘ（ｍ＋１，２ｎ）間の半画素（複数）（half pixels）が使用される。一般に、それらの半画素（half pixels）の値は利用不可能である。補間は端数画素の値を計算する方法である。多くの方法があり、たとえば、直線補間は
y=(x(m-1,2n+2)+x(m,2n+2)+1)>>1.
である。
【００８０】
サンプルとして方程式（１２）を使用することにより補間技術を考察する。
最初に、完全な再構成のため、端数画素を補間するため使用される整数画素はｘe（ｍ，ｎ）に属する必要がある。この技術はｘ0（ｍ，ｎ）からのいかなる整数画素も使用できない。一般に、補間は
【００８１】
【数１８】
2006074733.tif 000020
【００８２】
と書ける。
ここで、ｋはおおよそｓｉｇｎ（ｉ−１）ｔｇ（θ）の整数で、かつαkは補間フィルタのパラメータである。
方程式（１８）のｚ変換後、
【００８３】
【数１９】
2006074733.tif 000021
【００８４】
が得られる。
パラメータαkは有限数のゼロでない係数を有する。この実施形態では、値αkを決定するよく知られているＳｉｎｃ補間が採用される。方程式（１４）の補間は同じ方法で行われる。
【００８５】
２．５  方向推定
各サンプルの方向角度θνおよびθkは所定ブロック寸法、たとえば、１６ｘ１６ブロックで局所的に推定される。図８に示すように、１６ｘ１６ブロックは３つのモード、即ち、１６ｘ１６（図９Ａ）、８ｘ８（図９Ｂ）、４ｘ４（図９Ｃ）に区分される。１６ｘ１６モードでは、すべての画素が同じ方向角度を有する。４ｘ４モードでは、各ブロックが１６の方向角度を有し、４ｘ４サブブロック内のすべての画素は同じ角度を共有する。さらに、予測された角度がより精密であるほど、空間予測はより正確になる。ビデオ符合化における動き補償の知識から、この発明のこの実施形態は、その予測精度を４分の１画素までにすることが好ましい。
【００８６】
一般に、画像の角度推定プロセスを図１０に示す。プロセス・アクション１００２、１００４および１００６に示すように、画像の各マクロブロックに対して、最良の予測角度およびモードが、様々なブロック・サイズおよび垂直方向の候補角度から見付け出される。次に、１次元垂直変換が行われる（プロセス・アクション１００８）。プロセス・アクション１０１０、１０１２および１０１４に示すように、画像の各マクロブロックに対して、最良の予測角度およびモードは、様々なブロック・サイズおよび水平方向の候補角度から見付け出される。次に、プロセス・アクション１０１６に示すように、１次元垂直変換が行われる。
【００８７】
図１１はマクロブロックでの角度およびモードの推定プロセスを示す。プロセス・アクション１１０２、１１０４および１１０６に示すように、１６ｘ１６マクロブロックでの最良角度、８ｘ８マクロブロックでの最良角度、および４ｘ４サブブロックでの最良角度が見付け出される。次に、最良モードがブロック・モード・レベルでのこれらの３つの最良角度群に基づいて見出される（プロセス・アクション１１０８）。最良角度およびモードを決定する基準は垂直および水平変換に対する方程式（２０）および（２１）で与えられる。
【００８８】
各１６ｘ１６ブロックの予測されたモードおよび方向角度を判定するＲ−Ｄアルゴリズムが提案される。垂直リフティング変換では、モードおよび方向角度を推定する基準は、次のように与えられる。
【００８９】
【数２０】
2006074733.tif 000022
【００９０】
ここで、ｈ（ｍ，ｎ）は方程式（２）により計算される垂直変換後の高域係数（high-pass coefficients）である。Ｒνはモードおよび方向角度を符合化するビットである。λνはラグランジュ（Lagrangian）係数、および（ｍ0，ｎ0）はｈ（ｍ，ｎ）の左上画素の座標である。
【００９１】
推定された方向データによる垂直リフティング変換後、低域信号（low-pass signal）ｌ（ｍ，ｎ）および高域信号（high-pass signal）ｈ（ｍ，ｎ）が得られる。それらは水平変換により連続して処理される。一般に、ｈ（ｍ，ｎ）はエネルギーがより少ない。垂直分解後、高域サブバンドを水平方向に変換するために、予測されたモードおよび角度の別の組を使用することは何の価値もない。従って、ｈ（ｍ，ｎ）は水平方向に分解される。
【００９２】
垂直分解で使用された１組の予測されたモードおよび角度とは異なる、ｌ（ｍ，ｎ）を分解する別の組の予測されたモードおよび角度が存在する。新しい基準は次のように与えられる。
【００９３】
【数２１】
2006074733.tif 000023
【００９４】
ここで、ｌｈ（ｍ，ｎ）はＬＨサブバンドの係数である。Ｒhはモードおよび方向角度を符合化するビットである。λhはラグランジュ係数である。（ｍ1，ｎ1）はｌｈ（ｍ，ｎ）の左上画素の座標である。
【００９５】
２．６  方向角度符合化
方向角度は、固定された可変長符合化（ＶＬＣ）テーブルを使用して、ただし適応マッピングを使用して符号化される。図１２に示すように、現在ブロックの角度ｃが符合化されると仮定する。隣接するブロックの角度ａ、ｂおよびdは符合化された角度を予測する状態にある。どの角度が予測値として使用されるかを選択するため、次の基準が使用される。
【００９６】
【数２２】
2006074733.tif 000024
【００９７】
言い換えれば、角度ｂおよびｄがより大きな差を有する場合、角度ａは予測値として使用される。さもなければ、角度ｄが予測値として使用される。
【００９８】
ＶＬＣテーブルの記号が、予測された角度にしたがってＲ、適応的に割り当てられる。予測された角度は最短記号として与えられ、他の角度はこれらの角度と予測された角度間の絶対差により短い記号から長い記号まで割り当てられる。その後、現在角度ｃが所定テーブルにより符合化される。
【００９９】
２．７  この発明によるシステムおよび方法の模範的適用
画像符合化に加えて、提案されたＤＳＰリフティングは多くの他の分野にも適用可能である。ここで、この発明のシステムおよび方法の２つの模範的適用、即ち、空間スケーラブル・ビデオ符合化および低遅延ウェーブレット・ビデオ符合化を考察する。
【０１００】
２．７．１  スケーラブル・ビデオ符合化
空間スケーラビリティは、無線ネットワークおよびポータブル・デバイスの増大とともに、ビデオ符合化において非常に望ましい機能である。解決するのは難問である。多くの研究により、空間スケーラビリティはかなり符合化効率を損なうことが示されている。空間スケーラビリティを実現する解決策の１つは、最初に、ビデオ・シーケンスをいくつかの４つの低分解能シーケンスに分解し、かつ次に、それらを共にまたは別々に符合化する。ただし、それらのシーケンスのうちの高域シーケンス（high-pass sequences）は、既存の動き補償スキームで圧縮するのは困難である。本発明のＤＳＰリフティング技術の助力があれば、高域シーケンスは、画素間の相関が方向空間変換により大幅に取り除かれるため、非常に少ないエネルギーを有することになる。その高域シーケンスの各々はイントラ符合化で圧縮される。
【０１０１】
２．７．２  低遅延3次元ウェーブレット・ビデオ符合化
ＭＰＥＧはスケーラブル・ビデオ符合化に関する提案を要求していた。提案されたスキームのほとんどは、時間ウェーブレット分解（temporal wavelet decomposition）を使用する。これらのスキームの大きな問題は、複数の層の時間な分解のため遅延が相当大きいことである。それは低遅延かつリアルタイムのアプリケーションによる要件を満足できない。この発明の提案されたＤＳＰリフティングを使用すると、その３次元ウェーブレット・ビデオ符合化スキームは、時間的な分解の数を減らすことが可能である。低帯域フレーム間の相関が方向空間予測により取り除かれる。
【０１０２】
この発明の前述の説明は図示および説明の目的のため提供されてきた。開示された精密な形態に、本発明の全体を網羅するか、または制限するように意図するものではない。多くの変形および変更が上記教示を受けて可能である。この発明の範囲は詳細説明により制限されるものではなく、むしろ特許請求の範囲により制限されるように意図されている。
【０１０３】
参考文献
【０１０４】
2006074733.tif 000025
【０１０５】
2006074733.tif 000026
【図面の簡単な説明】
【０１０６】
【図１】本発明を実装する例示的なシステムを構成する汎用コンピューティング・デバイスを示す図である。
【図２】本発明の符号化方法の概要流れ図を示す図である。
【図３】２次元の方向空間予測のリフティングの例示的な流れ図を示す図である。
【図４】一般的な１次元の従来のリフティング変換、（ａ）分析側および（Ｂ）合成側の簡略化したブロック図を示す図である。
【図５Ａ】範例となる原画像を表す図である。
【図５Ｂ】従来のリフティング分解により結果として得られた低低（ＬＬ）サブバンドを表す図である。
【図５Ｃ】従来のリフティング分解により結果として得られた低高（ＬＨ）サブバンドを表す図である。
【図５Ｄ】従来のリフティング分解により結果として得られた高低（ＨＬ）サブバンドを表す図である。
【図５Ｅ】従来のリフティング分解により結果として得られた高高（ＨＨ）サブバンドを表す図である。
【図６】本発明のシステムおよび方法によるＤＳＰリフティング・スキームにおける垂直変換の角度を示す図である。
【図７】一般的な１次元のＤＳＰリフティング変換、（ａ）分析側および（Ｂ）合成側を示す図である。
【図８Ａ】本発明のＤＳＰリフティング分解により結果として得られた低低（ＬＬ）サブバンドを表す図である。
【図８Ｂ】本発明のＤＳＰリフティング分解により結果として得られた低高（ＬＨ）サブバンドを表す図である。
【図８Ｃ】本発明のＤＳＰリフティング分解により結果として得られた高低（ＨＬ）サブバンドを表す図である。
【図８Ｄ】本発明のＤＳＰリフティング分解により結果として得られた高高（ＨＨ）サブバンドを表す図である。
【図９Ａ】本発明のシステムおよび方法の方向角度を推測する３つの区分モードのうちの１６ｘ１６画素ブロック区分を表す図である。
【図９Ｂ】本発明のシステムおよび方法の方向角度を推測する３つの区分モードのうちの８ｘ８画素ブロック区分を表す図である。
【図９Ｃ】本発明のシステムおよび方法の方向角度を推測する３つの区分モードのうちの４ｘ４画素ブロック区分を表す図である。
【図１０】本発明によるシステムおよび方法の画像における角度推測のプロセスの流れ図である。
【図１１】本発明によるシステムおよび方法のマクロブロックでの角度およびモード推定の流れ図である。
【図１２】本発明によるシステムおよび方法の方向角度の予測を示す図である。
【符号の説明】
【０１０７】
１２０  処理ユニット
１２１  システム・バス
１３０  システム・メモリ
１３１  ＲＯＭ  
１３２  ＲＡＭ
１３３  ＢＩＯＳ
１３４  オペレーティング・システム
１３５  アプリケーション・プログラム
１３６  他のプログラム・モジュール
１３７  プログラム・データ
１４０  取り外し不可能な不揮発性メモリ・インターフェース
１４４  オペレーティング・システム
１４５  アプリケーション・プログラム
１４６  他のプログラム・モジュール
１４７  プログラム・データ
１５０  取り外し可能な不揮発性メモリ・インターフェース
１６０  ユーザ入力インターフェース
１６１  マウス
１６２  キーボード
１６３  カメラ
１６５  カメラ・マイクロフォン・インターフェース
１６８  マイクロフォン
１７０  ネットワーク・インターフェース
１７１  ローカル・エリア・ネットワーク
１７２  モデム
１７３  ワイド・エリア・ネットワーク
１８０  リモート・コンピュータ
１８５  リモート・アプリケーション・プログラム
１９０  ビデオ・インターフェース
１９１  モニタ
１９５  出力周辺インターフェース
１９６  プリンタ
１９７  スピーカ
【図１】
2006074733.tif 000033
【図２】
2006074733.tif 000034
【図３】
2006074733.tif 000035
【図４】
2006074733.tif 000036
【図５Ａ】
2006074733.tif 000037
【図５Ｂ】
2006074733.tif 000038
【図５Ｃ】
2006074733.tif 000039
【図５Ｄ】
2006074733.tif 000040
【図５Ｅ】
2006074733.tif 000041
【図６】
2006074733.tif 000042
【図７】
2006074733.tif 000043
【図８Ａ】
2006074733.tif 000044
【図８Ｂ】
2006074733.tif 000045
【図８Ｃ】
2006074733.tif 000046
【図８Ｄ】
2006074733.tif 000047
【図９Ａ】
2006074733.tif 000048
【図９Ｂ】
2006074733.tif 000049
【図９Ｃ】
2006074733.tif 000050
【図１０】
2006074733.tif 000051
【図１１】
2006074733.tif 000052
【図１２】
2006074733.tif 000053
【外国語明細書】
2006074733000001.pdf