(57)【要約】本発明は、２次元フレーム・シーケンスに適用されるサブバンド符号化法に基づいた、ビデオ符号化方法に関する。この方法は、現フレーム（Ｆ２）のサブバンド分解工程と、前フレーム又は基準フレーム（Ｆ１）に対して実行される動き予測工程と、符号化工程とを有する。本発明によれば、動き予測工程は、以下の手順に従った基準フレームの冗長分解に基づく。近似サブバンドにおいて、動きは、現フレームの各ピクセルに適用される完全検索オペレーションによって推定される。残りのサブバンドについて、動きは、サブサンプリングされたサブバンドから再構築された基準冗長サブバンドを予測に用いる画素帰納的動き推定アルゴリズムを用いて推定される。この画素帰納的動き推定アルゴリズム自体は、初期化サブ工程と、更新サブ工程と、判定サブ工程とを有する。
2004531170.tif 000002
【特許請求の範囲】
【請求項１】
現フレーム（Ｆ２）のサブバンド分解工程と、前フレーム又は基準フレーム（Ｆ１）に対して実行される動き予測工程と、符号化工程とを有し、２次元フレーム・シーケンスに適用されるサブバンド符号化スキームに基づいた、ビデオ符号化方法であって、
前記動き予測工程は、
（１）前記分解の近似サブバンドにおいて、前記動きは、前記基準フレームを含み、現フレームの各画素（ピクセル）に適用される完全検索オペレーションによって推定され、
（２）残りのサブバンドについて、前記動きは、前記サブバンド分解によって生じたサブサンプリングされたサブバンドから再構築された基準冗長サブバンドを予測に用いるピクセル（又は画素）帰納的動き推定アルゴリズムによって推定される、
という手順に従って、前記基準フレームの冗長分解に基づくことを特徴とする方法。
【請求項２】
請求項１記載の符号化方法であって、
２つの連続したサブバンドを表す２つの行列Ａ及びＢの間のオプティック・フローを計算すること、すなわち、Ｂ（ｍ）＝Ａ（ｍ−ｄ）となるように各ピクセルについてその動きベクトルｄ（ｍ）を推定すること、が意図された前記画素機能的動き推定アルゴリズムは、それ自体が、
（ａ）反復アルゴリズムが因果近隣Ｓにおける動きベクトルの平均値ｄ０（ｍ）：
【数１】
2004531170.tif 000040
（ここで、ｍは動きが推定されるピクセルであり、ｄ（ｍ）はその動きベクトルである）で初期化される初期化サブ工程と、
（ｂ）ｄｉ＋１＝ｄｉ＋ｕｉ（ここで、各反復ｉにおいて決定されるｕｉは、
【数２】
2004531170.tif 000041
（ここで、∇Ａは点ｍ−ｄｉにおける画像の傾きであり、Ｅ（ｍ）＝Ｂ（ｍ）−Ａ（ｍ−ｄｉ）は現反復における予測エラーであり、λは規則化パラメータである）によって与えられる更新ベクトルである）という関係に従ってｄｉを更新する更新サブ工程と、
（ｃ）ブレーク・テストを実行し、ｄｉが十分にｄに近ければ本手順を終了させる判定サブ工程とを有する、ことを特徴とする符号化方法。
【請求項３】
請求項２記載の符号化方法であって、
４ピクセルの典型的な近隣が用いられる、ことを特徴とする符号化方法。
【請求項４】
請求項２又は３記載の符号化方法であって、
前記ブレーク・テストは、比：
【数３】
2004531170.tif 000042
の推定に基づき、
この比は、所定の閾値εより大きくなければならない、ことを特徴とする符号化方法。
【請求項５】
請求項４記載の符号化方法であって、
前記閾値εは、ベクトル決定精度と計算負荷とのバランスが取れるように変えられる、ことを特徴とする符号化方法。
【請求項６】
請求項４又は５記載の符号化方法であって、
前記ブレーク・テストは、最大反復数に課される追加的条件を含む、ことを特徴とする符号化方法。
【請求項７】
請求項４乃至６のいずれか一項記載の符号化方法であって、
前記更新ベクトルｕｉの決定は、Ｂ（ｍ）＝Ａ（ｍ−ｄｉ）−δｄＴ．∇Ａ（ここで、δｄＴ．∇Ａは、∇Ａとベクトルδｄ＝ｄ−ｄｉの内積）であることを知っていて、スクエア・エラーＪ：
Ｊ＝（Ｂ（ｍ）−Ａ（ｍ−ｄｉ）＋δｄＴ．∇Ａ）２＋λ‖δｄ‖２
（ここで、項λ‖δｄ‖２は、λが大きい値のときに結果として得られる動きベクトル・フィールドのスムーズさとλが小さい値のときの動きベクトルの精度との間のトレードオフの観点から提供される規則化項）をδｄに対して最小化するために、最小値は∂Ｊ／∂ｄ＝０のときに得られ、更新ベクトルは
【数４】
2004531170.tif 000043
となる、最小化オペレーションを含む計算工程に基づく、ことを特徴とする符号化方法。
【請求項８】
請求項７記載の符号化方法であって、
前記走査順序は、偶数行を左から右へ、奇数行を右から左へ、というように実行され、
その際、前記初期化近隣も、１番目の行については前のピクセルに対して減らされ、奇数行については因果性を保存するように逆行されるように、修正される、ことを特徴とする符号化方法。
【請求項９】
請求項７記載の符号化方法であって、
前記動き推定アルゴリズムは、ブレーク条件をテストすることによって、再初期化され、
このテストは、いくつかの公差、該テストについて動き推定を伴わない予測エラーと比較された推定された動きを用いたときの予測エラー、及び、閾値を用いる、ことを特徴とする符号化方法。
【請求項１０】
請求項２記載の符号化方法であって、
前記動きベクトルの初期化は、前記近隣Ｓ上の平均の一次結合を用いて行われ、
前記動きベクトルは、前の分解レベルにおいて、同じ方向性を有するサブバンドから得られる、ことを特徴とする符号化方法。
【請求項１１】
請求項１記載の符号化方法であって、
同じ分解レベルのサブバンド間に存在する相関性を用いること、すなわち、所定の分解レベルｊ∈｛１、２、・・・ｊｍａｘ｝について、ｓ＝｛０、・・・４｝についてＢｊ，ｓ（ｍ）＝Ａｊ，ｓ（ｍ−ｄｊ）（２つの行列Ａ及びＢは２つの連続したサブバンドを表す）となるように各ピクセルについてその動きベクトルｄｊ（ｍ）を推定すること、が意図された前記画素機能的動き推定アルゴリズムは、それ自体が、
（ａ）反復アルゴリズムが因果近隣Ｓにおける動きベクトルの平均値ｄｊ（ｍ）：
【数５】
2004531170.tif 000044
（ここで、ｋ∈ｓ（１〜４）、ｍは動きが推定されるピクセルであり、ｄｊ，０（ｍ）はその動きベクトルである）で初期化される初期化サブ工程と、
（ｂ）ｄｊ，ｉ＋１＝ｄｊ，ｉ＋ｕｊ，ｉ（ここで、各反復ｉにおいて決定されるｕｊ，ｉは、
【数６】
2004531170.tif 000045
（ここで、
【数７】
2004531170.tif 000046
は点ｍ−ｄｉにおける画像の傾きであり、
Ｅｊ，ｓ（ｍ）＝Ｂｊ，ｓ（ｍ）−Ａｊ，ｓ（ｍ−ｄｊ，ｉ）
である）によって与えられる更新ベクトルである）という関係に従ってｄｊ，ｉ＋１を更新する更新サブ工程と、
（ｃ）ブレーク・テストを実行し、ｄｊ，ｉが十分にｄｊに近ければ本手順を終了させる判定サブ工程と、を有することを特徴とする符号化方法。
【請求項１２】
請求項１１記載の符号化方法であって、
４ピクセルの典型的な近隣が用いられる、ことを特徴とする符号化方法。
【請求項１３】
請求項１１又は１２記載の符号化方法であって、
前記ブレーク・テストは、比：
【数８】
2004531170.tif 000047
の推定に基づき、
この比は、所定の閾値εより大きくなければならない、ことを特徴とする符号化方法。
【請求項１４】
請求項１３記載の符号化方法であって、
前記ブレーク・テストは、最大反復数に課される追加的条件を含む、ことを特徴とする符号化方法。
【請求項１５】
請求項１３又は１４記載の符号化方法であって、
前記更新ベクトルｕｉの決定は、
【数９】
2004531170.tif 000048
（ここで、δｄＴ．∇Ａは、∇Ａとベクトルδｄｊ＝ｄｊ−ｄｊ，ｉの内積）であることを知っていて、スクエア・エラーＪ：
【数１０】
2004531170.tif 000049
（ここで、項λ‖δｄｊ‖２は、λが大きい値のときに結果として得られる動きベクトル・フィールドのスムーズさとλが小さい値のときの動きベクトルの精度との間のトレードオフの観点から提供される規則化項）をδｄｊに対して最小化するために、最小値は∂Ｊｊ／∂δｄｊ＝０のときに得られる、最小化オペレーションを含む計算工程に基づく、ことを特徴とする符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、ビデオ圧縮の分野に係り、特に、現フレーム（Ｆ２）のサブバンド分解工程と、前のフレーム又は基準フレーム（Ｆ１）に対して実行される動き予測工程と、符号化工程とを有し、２次元フレーム・シーケンスに適用されるサブバンド符号化法に基づいた、ビデオ符号化方法に関する。
【背景技術】
【０００２】
マルチメディア分野では、インターネット・ビデオ・ストリーミング、ビデオ・データベース・ブラウジング、又は、マルチクオリティ・ビデオ・サービス、などの新しい双方向アプリケーションが広まってきている。この異質のネットワーク（インターネット、モバイル・ネット、家庭内ディジタル・ネットワーク）上でのビデオ・サービスの最近の発展は、トランスポート状態（帯域幅、誤り率、・・・）の変化や、消費者需要及び端末の復号化能力（ＣＰＵ、ディスプレイ・サイズ、アプリケーション、・・・）の変化について新たな問題を提起しており、これにより、新しいビデオ圧縮アルゴリズム、特にサブバンド分解に基づく方法、が研究されている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来のビデオ符号化アルゴリズムでは、より具体的には、ＭＰＥＧ−４規格のフレーム内では、いわゆるブロック・マッチング・アルゴリズム（ＢＭＡ）を用いて、処理されたビデオ・シーケンスの連続フレーム間での動き推定が行われる。ＢＭＡにおいて、基準フレームの定義されたエリア又は検索窓内から類似したブロックを検索することによって、（固定サイズのブロックに分解された）現フレームの画素（ピクセル）ブロックに動きベクトルが割り当てられ、エラー指標に従って候補を評価することによって（ブロックのシフトを表す）最も良いベクトルを見つける（最も良く対応するブロックは最小のエラーを与えるブロックである）。このＢＭＡは、残念ながら、動き補償フレームのブロック端に高周波アーティファクト（ブロッキング効果）を生成する。ＢＭＡがウェーブレット分解に基づく符号化法において用いられると、これらアーティファクトは、補償フレームのウェーブレット分解に高係数を生じさせることによって、符号化効率を低減する。
【０００４】
本発明の目的は、別の種類の動き推定及び補償を組み込み、符号化効率を向上させることができるビデオ符号化方法を提案することである。
【課題を解決するための手段】
【０００５】
このため、本発明は、本明細書の冒頭段落に定義したような方法であって、更に、上記動き予測工程が、以下の手順に従って、基準フレームの冗長分解に基づくことを特徴とする。
【０００６】
（１）上記分解の近似サブバンドにおいて、動きは、上記基準フレームを含み、現フレームの各画素（ピクセル）に適用される完全検索オペレーション（ｆｕｌｌ  ｓｅａｒｃｈ  ｏｐｅｒａｔｉｏｎ）によって推定される。
【０００７】
（２）残りのサブバンドについて、動きは、上記サブバンド分解によって生じたサブサンプリングされたサブバンドから再構築された基準冗長サブバンドを予測に用いるピクセル（又は画素）帰納的動き推定アルゴリズムによって推定される。
【０００８】
この技術的解決策案は、ウェーブレットを用いた画素帰納的動き推定アルゴリズム（ｐｅｌ−ｒｅｃｕｒｓｉｖｅ  ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ  ａｌｇｏｒｉｔｈｍ）の実施に基づく。ウェーブレット領域での動き推定は、トランスレーション不変性（ｔｒａｎｓｌａｔｉｏｎ  ｉｎｖａｒｉａｎｃｅ）の問題に対処しなければならない。その際、基準フレームの冗長分解を用いて、動きが予測されるため、最も細かい解像度グリル上で動きを考慮することができる。近似サブバンドにおいて、動きは、現フレームのすべてのピクセルに対して適用される完全検索アルゴリズムによって推定される。残りのサブバンドについて、予測に基準冗長サブバンドを用いる画素帰納的アルゴリズムが実施される。このアルゴリズムの初期化は、同じサブバンドにおいて空間的に隣接する動きベクトルと前の分解レベルにおいて同じ位置に対応する動きベクトルとの重み付けされた値を用いて、行われる。このアルゴリズムにより、良好な推定に向けて収束するのに失敗する位置において再初期化することが可能となる。また、サブバンドにおける走査順序も１行ごとの走査において発生し得るドリフトを最小化するために最適化される。
【０００９】
より具体的には、上記画素帰納的動き推定アルゴリズムは、
（ａ）反復アルゴリズムが因果近隣（ｃａｕｓａｌ  ｎｅｉｇｈｂｏｕｒｈｏｏｄ）Ｓにおける動きベクトルの平均値ｄ０（ｍ）：
【００１０】
【数１１】
2004531170.tif 000003
（ここで、ｍは動きが推定されるピクセルであり、ｄ（ｍ）はその動きベクトルである）で初期化される初期化サブ工程と、
（ｂ）ｄｉ＋１＝ｄｉ＋ｕｉ（ここで、各反復ｉにおいて決定されるｕｉは、
【００１１】
【数１２】
2004531170.tif 000004
（ここで、∇Ａは点ｍ−ｄｉにおける画像の傾きであり、Ｅ（ｍ）＝Ｂ（ｍ）−Ａ（ｍ−ｄｉ）は現反復における予測エラーであり、λは規則化パラメータである）によって与えられる更新ベクトルである）という関係に従ってｄｉを更新する更新サブ工程と、
（ｃ）ブレーク・テストを実行し、ｄｉが十分にｄに近ければ本手順を終了させる判定サブ工程と、を有し、４つのピクセルの典型的な近隣が好ましくは用いられる。
【００１２】
本発明の特定の実施例において、ブレーク・テストは、比
【００１３】
【数１３】
2004531170.tif 000005
の推定に基づいてもよい。この比は、所定の閾値εより大きくなければならない。
【００１４】
また、上記ブレーク・テストは、最大反復数に課される追加的条件を含み得る。
【００１５】
本発明の有益的な一実施形態によれば、上記更新ベクトルｕｉの決定は、以下の最小化オペレーションを含む計算工程に基づく。Ｂ（ｍ）＝Ａ（ｍ−ｄｉ）−δｄＴ．∇Ａ（ここで、δｄＴ．∇Ａは、∇Ａとベクトルδｄ＝ｄ−ｄｉの内積）であることを知っていて、スクエア・エラー（ｓｑｕａｒｅ  ｅｒｒｏｒ）Ｊ：
Ｊ＝（Ｂ（ｍ）−Ａ（ｍ−ｄｉ）＋δｄＴ．∇Ａ）２＋λ‖δｄ‖２
（ここで、項λ‖δｄ‖２は、λが大きい値のときに結果として得られる動きベクトル・フィールドのスムーズさとλが小さい値のときの動きベクトルの精度との間のトレードオフの観点から提供される規則化項）をδｄに対して最小化するために、最小値は∂Ｊ／∂ｄ＝０のときに得られ、更新ベクトルは
【００１６】
【数１４】
2004531170.tif 000006
となる。
【００１７】
本発明の別の実施形態において、動き推定アルゴリズムは、
（ａ）反復アルゴリズムが因果関係のある近隣Ｓにおける動きベクトルの平均値ｄｊ，０（ｍ）：
【００１８】
【数１５】
2004531170.tif 000007
（ここで、ｋ∈ｓ（１〜４）、ｍは動きが推定されるピクセルであり、ｄｊ，０（ｍ）はその動きベクトルである）で初期化される初期化サブ工程と、
（ｂ）ｄｉ，ｉ＋１＝ｄｊ，ｉ＋ｕｊ，ｉ（ここで、各反復ｉにおいて決定されるｕｊ，ｉは、
【００１９】
【数１６】
2004531170.tif 000008
（ここで、
【００２０】
【数１７】
2004531170.tif 000009
は点ｍ−ｄｊ，ｉにおける画像の傾きであり、Ｅｊ，ｓ（ｍ）＝Ｂｊ，ｓ（ｍ）−Ａｊ，ｓ（ｍ−ｄｊ，ｉ）によって与えられる更新ベクトルである）という関係に従ってｄｊ，ｉ＋１を更新する更新サブ工程と、
（ｃ）ブレーク・テストを実行し、ｄｊ，ｉが十分にｄｊに近ければ本手順を終了させる判定サブ工程と、を有する。
【発明を実施するための最良の形態】
【００２１】
ここで、添付図面を参照して、本発明の一例を説明する。
【００２２】
フレキシブルなビデオ符号化システムを取得し、様々な要件及び能力に対処できるようにするため、拡張性は期待された機能性である。サブバンドに基づくプログレッシブ符号化手法は、解決策となり得る。なぜなら、それらは完全なプログレッシブ送信を可能にするからである。特に、ウェーブレットは、拡大縮小可能な表現の点でプログレッシブな画像符号化において高い効率を有する。それらは、静止画についてナチュラル・マルチスケール表現を提供する。これは、分解内での時間次元などの３次元（２次元＋時間）ウェーブレット分析を用いて、ビデオ・データに拡張することができる。３次元サブバンド分解スキームにおける動き補償工程の導入により、動き補償を伴ったビデオ情報の時間的サブバウンド分解を示す図１に示すように、ビデオ信号の空間−時間多解像度（階層的な）表現が得られる。
【００２３】
図示した動き補償を伴った３次元ウェーブレット分解は、Ｆ１〜Ｆ８で示されるグループ・オブ・フレーム（ＧＯＦ）に適用される。この３次元サブバンド分解スキームにおいて、入力ビデオの各ＧＯＦは、まず、大きな動きを伴うシーケンスを処理するために、動き補償（ＭＣ）され、次いで、Ｈａａｒウェーブレットを用いて時間的にフィルタリング（ＴＦ）される。破線矢印は、高域通過時間フィルタリングに対応し、残りのものは、低域通過フィルタリングに対応し、分解の３つのステージが図示されている（Ｌ及びＨ＝第一ステージ；ＬＬ及びＬＨ＝第二ステージ；ＬＬＬ及びＬＬＨ＝第三ステージ）。
【００２４】
しかし、各サブバンドの係数について画素帰納的動き推定を実行するとき、トランスレーション（ｔｒａｎｓｌａｔｉｏｎ）が欠けていることが考慮されなければならない。ダイナミック・サブバンド分解（このような分解を示す図２参照。そこでは、３層について実行され、最下層にサブバンドＬＨ１、ＨＬ１、及びＨＨ１、中間層にサブバンドＬＨ２、ＨＬ２、及びＨＨ２、最上層にサブバンドＭ３、ＬＨ３、ＨＬ３、及びＨＨ３、の１０のサブバンドを生じる。図３は、入力信号ｆ［ｎ］からこの分解を得て、出力信号Ｌ１［ｎ］、Ｌ２［ｎ］、Ｌ３［ｎ］、Ｈ１［ｎ］、Ｈ２［ｎ］、及びＨ３［ｎ］を与えることが可能なバンク・フィルタを示す。）を用いた場合の主たる問題は、実際には、各フィルタリング・オペレーション（２１、２２、２３、２４、２５、２６）の後に適用されたサブサンプリング・オペレーション（３１、３２、３３、３４、３５、３６）は、トランスレーション不変性を保存しない（信号の冗長ウェーブレット・トランスフォームは時間不変性表現であるが、逆に、非冗長ウェーブレット分解はこの特性を欠く）。一例を図４及び５に示す。ここには、それぞれ、動いているオブジェクト（オリジナル信号ＯＲＳ）のエッジの第一の位置の場合、及び、該エッジの別の位置に対応したシフトされた入力（シフト入力ＳＨＦ）の場合の、低域通過フィルタ（Ｌ（ｚ））及び高域通過フィルタ（Ｈ（ｚ））及びサブサンプラ（ＴＭ２）の出力における高フィルタリング・ブランチと低フィルタリング・ブランチのサンプルが図示されている。各フィルタ及び各サブサンプラの直後に得られた信号が図示されている。各サブサンプリング・オペレーションは、偶数又は奇数いずれかのサンプルを保たなければならない。動いているエッジは、第一のケース（図４、高フィルタリング・ブランチ）において高周波係数ＨＦＣをもたらし、該エッジは第二のケース（図５）ではもはや検知できない。結果として、サブサンプリングされたサブバンド係数からは動きを推論できない。動き予測は、サンプリングされていないサブバンドから実行されなければならない。
【００２５】
１次元信号に対して、サブサンプリング・オペレーションは、２つの考え得る選択をもたらす。奇数又は偶数のサンプルを取ることができる。２次元信号（画像など）に対して、このオペレーションは４つの考え得る分解をもたらす。よって、信号フレームが３つのレベルに分解されると、情報量の点で等価な６４の考え得る分解が得られる。しかし、上述のように、動き推定は、それらに対して実行できない。なぜなら、それらは冗長ではないからである。図６（その図面に示す２つの表現（Ｌ（ｚ２）＋ＴＭ２）と（ＴＭ２＋Ｌ（ｚ））の間の同一性を示す）から観察されるように、冗長分解は分析の各レベルについて存在する。図３の低フィルタリング・ブランチ（２１、３１、２２、３２、２３、３３）に図６の等価性を導入すると、上記図７の下の部分と等価なスキームが得られる。ここで、最後のサブサンプリング・オペレーションの前に、オリジナル画像と同じサイズを持つ冗長サブバンドが得られ、それに対して妥当な動き推定を実行することができる（３つのレベル１、２、３における情報サブバンドＲＳＢ１、ＲＳＢ２、ＲＳＢ３は図７に示されている）。
【００２６】
例えば、図８（出力ｃ［ｎ］及びｄ［ｎ］を導く信号分解の場合）及び図９（上記信号ｃ［ｎ］及びｄ［ｎ］からの信号再構築の場合）に示すように、いわゆるリフティング・スキームを用いて、ウェーブレット分解自体は実行される（この実施は、予測フィルタＰ及び更新フィルタＵの選択に対する柔軟性のために選択されるが、考え得る１つだけのものではないことは明らかである）。各フィルタ・パスについて、図８及び９からわかるように、まず、奇数又は偶数のサンプル（それぞれ、ｘ１［ｎ］、ｘ０［ｎ］）を取ることができる。
−偶数サンプルが先？：
ｎ≧０で
ｘ０［ｎ］＝ｆ［２ｎ］
ｘ１［ｎ］＝ｆ［２ｎ＋１］
―奇数サンプルが先？：
ｎ≧０で、
ｘ０［ｎ］＝ｆ［２ｎ＋１］
ｘ１［ｎ］＝ｆ［２（ｎ＋１）］
次いで、図１０〜１２は、図６及び７の同一性を図３の各フィルタ・バンクに適用することによって得られた「従来の」ウェーブレット分解を示す。各レベルにおける縮小の直前で停止すること（図１０、１１、又は１２）が冗長サブバンドをもたらすことが明らかである。
【００２７】
問題は、リフティング・ウェーブレットは、本来、フィルタリングの前に縮小を用いることである。リフティング・バンク用入力信号がｘ０［ｎ］＝ｆ［２ｎ］．ｘ１［ｎ］＝ｆ［２ｎ＋１］又はｘ０［ｎ］＝ｆ［２ｎ＋１］．ｘ１［ｎ］＝ｆ［２（ｎ＋１）］である図８において、これら入力はオリジナル信号ｆ［ｎ］に対して縮小される。このように、縮小工程は、分解中、飛ばすことができず、冗長サブバンドはここに示す別の方法で取得することができる。
【００２８】
図８及び９に関連して、分解の各レベル及び各次元について、先に偶数サンプルか奇数サンプルかを選択することができることは明らかである。例えば、偶数選択を０で表し、奇数選択を１で表すものとすると、３つのレベルについての完全な分解は、図１３の例に示すように、６ビットで特徴付けられる。この例は、分解基礎の数字：０、０、１、０、０、１→基礎数字９の２進数分解として示すことができる。結果として、６４の考え得る分解基礎に対応する６４の考え得るサブサンプリング選択が存在する（図１４に示すように）。
【００２９】
次いで、厳密にサブサンプリングされたサブバンドを用いて、冗長サブバンドを構築する。分解基礎の数字は、そのサブバンドが長方形グリッド上におかれる位置をもたらす。例えば、ｘを表すビットが０１０（第三レベル、第二レベル、第一レベル）の場合、それらは数字２をもたらす。これは、そのサブバンドの最初のサンプルが冗長サブバンドにおいてどこに置かれるべきか、次にｘ方向、を示す再構築オフセットである。同じオペレーションがｙ方向にも適用される。サンプルは、次いで、間隔＝２ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｌｅｖｅｌの間隔長で配置される。オフセットと各サブサンプリングさえたサブバンドについての間隔とが判れば、図１５に示すように、それらをインターリーブして、冗長サブバンドを再構築することができる。この冗長サブバンドは、オリジナル画像と同じサイズを有する。分解の第一レベルにおいて、冗長サブバンドＨＬ、ＬＨ、及びＨＨのそれぞれは、４つのサブサンプリングされたサブバンドをインターリーブすることによって得られる。レベル２において、それらは、１６のサブサンプリングされたサブバンドをインターリーブすることによって得られる。レベル３において、冗長サブバンドを得るためには、６４のサブサンプリングされたサブバンドをインターリーブしなければならない（図１４参照）。結局、冗長分解は、図１６に示すように、１０の冗長サブバンドをもたらす。
【００３０】
ここで、画素帰納的動き推定について説明する。以下では、ベクトル（ｄ）に太字、傾き（ｇｒａｄｉｅｎｔ）に∇、転位（ｔｒａｎｓｐｏｓｉｔｉｏｎ）に（．）Ｔを用いる。以下のアルゴリズムは、２つの行列Ａ及びＢの間のオプティック・フロー（Ｏｐｔｉｃ  Ｆｌｏｗ）を計算することを意味する。これらはシーケンス中の２つの連続したフレームでもよく、或いは、（本ケースで考えるように）２つの連続したサブバンドでもよい。目的は、各ピクセルｍ＝（ｍ、ｎ）について動きベクトルｄ（ｍ）：
Ｂ（ｍ）＝Ａ（ｍ−ｄ）      （１）
を推定することである。ｄの帰納的既述を実行するために、ｄが画像面上にスムーズに分散されているものと仮定しなければならない。基本的に、ここに記載した方法は、Ｂの各基準ピクセルについて、基準ピクセルにより近いＡのピクセルを見つけるために、推定された位置（ｍ−ｄ）においてＡの傾きが計算される。これは、新しい位置ｍ−ｄをもたらす。これが同じ位置であれば、アルゴリズムは停止し、もう一度繰り返される。このように、本アルゴリズムは、右位置に達すると、収束し、停止する。この反復手順は、初期化工程、更新ベクトルの計算工程、動きベクトルの更新工程、及び、ブレーク・テスト工程から成る。
【００３１】
（１）反復手順は、因果近隣Ｓにおける動きベクトルの平均値によって初期化される。
【００３２】
【数１８】
2004531170.tif 000010
ここでは、４つのピクセルの典型的な近隣を用いることができる（動きベクトルは画像境界の外でゼロであるものとする）と考えている。
【００３３】
【数１９】
2004531170.tif 000011
（２）２番目の工程は、各反復ｉにおいて、更新ベクトルｕｉ：
【００３４】
【数２０】
2004531170.tif 000012
（ここで、
【００３５】
【数２１】
2004531170.tif 000013
は位置ｍ−ｄｉにおける画像の傾きであり、
Ｅ（ｍ）＝Ｂ（ｍ）−Ａ（ｍ−ｄｉ）      （５）
は現反復における予測エラーであり、λは規則化パラメータである）の判定である。
【００３６】
（３）３番目の工程において、ｄｉが更新される。
ｄｉ＋１＝ｄｉ＋ｕｉ      （６）
（４）ブレーク・テストはｄｉがｄに十分近づいた場合に本手順を終了させる。このテストは、例えば、比：
【００３７】
【数２２】
2004531170.tif 000014
の推定に基づくことができる。この比は、εより優越していなければならない（εは、ベクトル判断精度及び計算負荷をバランスさせるために変わり得る）。最大反復数に補助的条件を置いてもよい。
【００３８】
２番目の工程（式（３）によって記述された更新ベクトル計算）は詳述されることができる。関係（１）の１次近似は、
Ｂ（ｍ）＝Ａ（ｍ−ｄｉ）−δｄＴ．∇Ａ      （８）
を読む。ここで、∇Ａは式（４）からの傾きであり、δｄ＝ｄ−ｄｉである。スクエア・エラー：
【００３９】
【数２３】
2004531170.tif 000015
は最小にされなければならない（項λ‖δｄ‖２について後で説明する）。この最小値は、
【００４０】
【数２４】
2004531170.tif 000016
のとき、すなわち、
（Ｂ（ｍ）−Ａ（ｍ−ｄｉ）＋δｄＴ．∇Ａ）．∇Ａ＋λδｄ＝０      （１０）
のとき、得られる。δｄＴ．∇Ａは、ベクトルδｄと∇Ａの内積であるため、δｄＴ．∇Ａ＝∇ＡＴ．δｄとなり、関係（１０）は、
（∇Ａ．∇Ｔ＋λＩ）．δｄ＝−Ｅ（ｍ）．∇Ａ      （１１）
となる。ここで、λの有用性がわかる。行列∇Ａ∇ＡＴは逆行可能でない（ランク１）が、∇Ａ∇ＡＴ＋λＩは以下の補助命題を用いると逆行可能とすることができる。
【００４１】
【数２５】
2004531170.tif 000017
この補助命題は、ここで、ｕ＝∇Ａ、及び、Ｍ＝λＩに対して、
【００４２】
【数２６】
2004531170.tif 000018
をもたらし、最終的に、
【００４３】
【数２７】
2004531170.tif 000019
を導く。これは、関係（３）及び（６）で用いられる更新ベクトルｕｉである。この規則化は、結果として得られる動きベクトル・フィールドのスムーズさ（大きなλに対して）と動きベクトルの精度（小さいλに対して）の間のトレードオフを提供する。
【００４４】
関係（１１）において、∇Ａが計算されなければならないことは明らかである。傾き計算は、画像の離散フィルタリングによって近似することができる。線形フィルタリングで傾きの離散近似を実行するために、フィルタは以下に指摘するいくつかの条件を満たさなければならない。ｈがＦＩＲフィルタであるものとし、連続フィールドＦ（ｘ、ｙ）の長方形サンプリングを考えると、Ｆ［ｎ、ｍ］＝Ｆ（ｎＬ１、ｎＬ２）となる。ｘ方向に続く画像の傾きは
【００４５】
【数２８】
2004531170.tif 000020
である。ここで、Ｓは９ピクセルの近接近隣（中心ピクセルｍ及び８つの周囲のピクセル）として考えられる。他方、１次において、
【００４６】
【数２９】
2004531170.tif 000021
であり、関係（１４）及び（１５）を組み合わせると、
【００４７】
【数３０】
2004531170.tif 000022
が得られる。次いで、関係（１６）のメンバを識別することでｈについて３つの条件が得られる。
【００４８】
【数３１】
2004531170.tif 000023
これら条件を満たす選ばれたフィルタは、
（ａ）ｘ次元傾きフィルタ：
【００４９】
【数３２】
2004531170.tif 000024
（ｂ）ｙ次元傾きフィルタ：
【００５０】
【数３３】
2004531170.tif 000025
である。これらフィルタは、離散傾きの良好な近似をもたらす。
【００５１】
上記アルゴリズムの実施について、特に動きベクトルの精度及び速度の点から、様々な向上が提案され得る。アルゴリズムの速度は、より急速に収束するようにすることによって、増加させることができる。このように、初期化工程は、収束速度にとって重大である。良好な初期化は、以前に計算された動きベクトルをできる限り多く考慮に入れなければならない。しかし、画像平面上での動きベクトルの分散のスムーズさについての前提は、オブジェクトの境界ではあてはまらない場合もある（例えば、平面上のオブジェクトが異なる方向に動いているときなどの特定の種類の動きに対して）。アルゴリズムは、このイベントを検知し、動きベクトル・フィールドのスムーズさを壊すことによって、初期化を訂正することができなければならない。初期化工程の終わりにおいて（及び、動きベクトルの各更新の後でさえも）ブレーク・テストを導入することが可能である。２つのテスト値：
Ｅ０（ｍ）＝｜Ｂｊ，ｓ（ｍ）−Ａｊ，ｓ（ｆｍ）｜
Ｅｊ，ｓ（ｍ）＝｜Ｂｊ，ｓ（ｍ）−Ａｊ，ｓ（ｆｍ−ｆｄｉ）｜
が計算されなければならない。ここで、Ｅ０は動きがない場合（ｄｉ＝０）のエラーであり、Ｅｊ，ｓは計算された動きベクトルが考慮された場合のエラーである。原理は、Ｅｊ，ｓがＥ０より大きい場合、動きベクトルはゼロに再初期化されなければならないことである。しかし、過度に頻繁な再初期化はアルゴリズムの収束を妨げる。予測エラーが非常に小さいとき、このケースが非常に起きやすい。なぜなら、このテストにおける公差が導入されるからである。これは、不等式：
Ｅｊ，ｓ＞Ｅ０＋ＴＨＲ      （１７）
を通じて定義される。ここで、ＴＨＲはサブバンド係数の値に従って決定される閾値である。
【００５２】
別の向上は走査順序に関する。画像が表であるものとすると、それは、図１７に示すように、最初のアイテム（すなわち、ｍ＝（０、０））から最後のアイテム（ｍ＝ｘｍａｘ、ｙｍａｘ）まで走査される。この初期化順序は、初期化近隣と合成され、画像の左下隅に悪い動き推定をもたらす（なぜなら、画像の１列目について、初期化近隣は上記ピクセルにしか削減されないからである）。そのとき、本方法は、信頼性がなく、エラードリフトを導く。図１８に提示された走査順序は、より良い結果をもたらす。画像は、偶数行が左から右へ、奇数行が右から左へ、走査される。これにより、初期化における因果性（ｃａｕｓａｌｉｔｙ）が向上する。実際、各ピクセルがすべての前の走査されたピクセルに依存する。画像の左下隅で観察されたエラードリフトはこの方法を用いると存在しない。より良い初期化はアルゴリズムの収束をよい速くする。エラードリフトは、反復数が限定されているという事実によるものであったため、初期化が良好でなければ、アルゴリズムは正しい動きベクトルへ収束するのに十分な反復を持っていないことになる。この新しい走査順序を考えると、初期化近隣は変えられなければならない。１番目の行について、近隣は前のピクセル：
【００５３】
【数３４】
2004531170.tif 000026
に減らされる。偶数行に対して、近隣は、変わらないまま、残る。
【００５４】
【数３５】
2004531170.tif 000027
３番目の向上は、定義により、非常にわずかのディテールしか有しない画像の近似サブバンドＳＢ  Ａｊｍａｘ，０に関連する。したがって、画素帰納的動き推定は十分に精度が良くない場合もある。補償された近似にける小さいエラーは、補償されたサブバンドから再構築された画像について悪い結果をもたらす。より良い結果は、Ａｊｍａｘ，０の窓において、Ｂｊｍａｘ，０の各ピクセルについて完全な検索が実行された場合に、得られる。しかし、この方法は、画素帰納的アルゴリズムほど高速でない。検索窓のサイズは、図１９に示すように、
（２．（２ｊｍａｘ）＋１）×（２．（２ｊｍａｘ）＋１）
である。ＳＢ（３，０）が推定される場合、その動きベクトルを用いて、他のサブバンドＳＢを初期化することができる。ｄａｐｐｒｏｘｉｍａｔｉｏｎをピクセルｍ（ｍ，ｎ）におけるＳＢ（３，０）の動きベクトルと呼び、ｄ０を空間的近隣のみを考慮した初期化ベクトルと呼ぶ場合、新しい初期化ベクトルは、
Ｄ０＝α．ｄａｐｐｒｏｘｉｍａｔｉｏｎ＋（１−α）．ｄ０      （１８）
と計算することができる。ここで、αは定数であり、これにより初期化においてｄａｐｐｒｏｘｉｍａｔｉｏｎの影響を制御することができる。α＝０の場合、ｄａｐｐｒｏｘｉｍａｔｉｏｎは影響を全く与えない。同じ原理を残りのサブバンドに対して用いることができる。そのとき、より高いレベルの分解ｊにおいて、前に計算された動きベクトルを用いて、アルゴリズムを初期化することができる。ｄｊ＋１をレベルｊ＋１において推定された動きベクトルと呼ぶ場合、新しい初期化ベクトルは、Ｄ０＝α．ｄｊ＋１＋（１−α）．ｄ０となる。上記一般的なアルゴリズムは、２つのサブバンドの間に適用することができる。しかし、それが用いられると、同じ分解レベルのサブバンド間に存在する相関性が考慮されない。計算される動きベクトルは、３つのサブバンド（或いは、ＬＬサブバンドが考慮されるときは４つのサブバンド）の各ピクセルについて同じであるべきである。すると、所定の分解レベルｊ∈｛１、２、・・・ｊｍａｘ｝について、各ピクセルｍ＝（ｍ，ｎ）について、動きベクトルｄｊ（ｍ）：
Ｂｊ，ｓ（ｍ）＝Ａｊｓ（ｍ−ｄｊ）    ｓ∈｛０・・・４｝      （１９）
を推定することを決定することができる。ここで、Ａ０，０は１番目の画像を表し、Ｂ０，０は２番目の画像を表し、Ａｊ，ｓはフレームＡのｊ番目の分解レベルにおけるサブバンド番号ｓを表し、サブバンド０は近似サブバンド（ＳＢ）を表し、サブバンド１は水平方向ディテールＳＢを表し、サブバンド２は垂直方向ディテールＳＢを表し、サブバンド３は対角線方向のディテールＳＢを表す。
【００５５】
ｄがサブバンド平面上にスムーズに分散していると仮定することがちょうど前と同じように行われる。
【００５６】
前と同様に、各分解レベルｊ∈｛１、２、・・・ｊｍａｘ｝について実行される反復手順は、初期化工程、更新ベクトル計算工程、動きベクトル更新工程、及び、ブレーク・テスト工程を有するが、若干修正されている。反復手順は、因果近隣Ｓにおける動きベクトルの平均値：
【００５７】
【数３６】
2004531170.tif 000028
によって初期化される。ここで、例えば、典型的な近隣は４ピクセル：
【００５８】
【数３７】
2004531170.tif 000029
である（動きベクトルは、画像境界の外では０であるものとする）。
２．次いで、更新ベクトルｕｊ，ｉが決定される：
【００５９】
【数３８】
2004531170.tif 000030
ここで、
【００６０】
【数３９】
2004531170.tif 000031
は点ｍ−ｄｊ，ｉにおける画像の傾きであり、
Ｅｊ，ｓ（ｍ）＝Ｂｊ，ｉ（ｍ）−Ａｊ，ｓ（ｍ−ｄｊ，ｉ）      （２３）
であり、ｓは、考慮されなければならないサブバンド数（より深い分解レベルについては４、その他については３）に応じて、１〜３又は０〜３で変化する。
３．次いで、動きベクトルｄｊ，ｉ＋１が更新される。
ｄｊ，ｉ＋１＝ｄｊ，ｉ＋ｕｊ，ｉ      （２４）
４．ブレーク・テストは、ｄｉ，ｊが十分にｄｊに近い場合に、本手順を終了させる。このテストは、例えば、比：
【００６１】
【数４０】
2004531170.tif 000032
の推定である。この比は、（求められる）εより優越していなければならない。追加的条件が最大反復数上に置かれる。
【００６２】
更新ベクトル計算について、一次において、関係（１）は、すべてのｓについて、
【００６３】
【数４１】
2004531170.tif 000033
となる。ここで、∇Ａｊ，ｓは式（４）からの傾きであり、δｄｊ＝ｄｊ−ｄｊ，ｊである。
【００６４】
すべてのサブバンド上のスクエア・エラーを同時に最小化する：
【００６５】
【数４２】
2004531170.tif 000034
ことが望まれるとき、最小値は、
【００６６】
【数４３】
2004531170.tif 000035
のとき、すなわち、
【００６７】
【数４４】
2004531170.tif 000036
のときに得られる。
【００６８】
すると、関係（２８）は、
【００６９】
【数４５】
2004531170.tif 000037
となる。
【００７０】
規則化無しであっても、行列
【００７１】
【数４６】
2004531170.tif 000038
は、逆行可能となり得る。これは２×２行列であり、逆行列は、明確に計算することができる。この場合、規則化項λＩは、動きベクトル・フィールド干渉性の制御のためだけに要求される。
【００７２】
この画素帰納的動き推定アルゴリズムが冗長サブバンドに適用されるべきである場合、前のアルゴリズムが適合されなければならない。ｆを冗長サブバンドのサイズとサブサンプリングされたサブバンドのサイズとの間の比を特徴付ける倍率とする。
ｆ＝２ｊ
ここで、ｊは分解レベルである。
【００７３】
冗長サブバンドはラック・トランスレーション・インヴァクシアンス（ｌａｃｋ  ｔｒａｎｓｌａｔｉｏｎ  ｉｎｖａｘｉａｎｃｅ）を提示することが知られている。結果として、画素帰納的動き推定は、冗長サブバンド（基準フレーム）とサブサンプリングされたサブバンド（現フレーム）の間で実行することができる。次いで、動きベクトルは、
Ｂｊ，ｓ（ｍ）＝Ａｊ，ｓ（ｆｍ−ｆｄｊ）      （３０）
を用いて定義される（偶数サンプルがＢｊ，ｓのサブサンプリングされた分解に対して残されたとする）。
【００７４】
そのとき、反復手順は若干異なる。
１．ｄ０（ｍ）が関係（２０）を用いて初期化される。
２．更新ベクトルｕｉは変わらないまま、新しいエラー：
Ｅｊ，ｓ（ｍ）＝Ｂｊ，ｓ（ｍ）−Ａｊ，ｓ（ｆｍ−ｆｄｉ）      （３１）
及び、新しい傾き：
【００７５】
【数４７】
2004531170.tif 000039
を用いる。
３．更新式は変えない。
４．ブレーク・テストは変えないまま。
【図面の簡単な説明】
【００７６】
【図１】動き補償を伴ったビデオ・シーケンスのサブバンド分解を示す図である。
【図２】上記分解を取得可能にするダイナミック・サブバンド分解を示す図である。
【図３】上記分解を取得可能にするバンク・フィルタを示す図である。
【図４】このようなダイナミック・サブバンド分解のサブサンプリング・オペレーションはどのようにしてトランスレーション不変性を保存しないのかを示す図である。
【図５】このようなダイナミック・サブバンド分解のサブサンプリング・オペレーションはどのようにしてトランスレーション不変性を保存しないのかを示す図である。
【図６】冗長分解は各分析レベルについて存在することを示す表現間の同一性を示す図である。
【図７】冗長分解は各分析レベルについて存在することを示す表現間の同一性を示す図である。
【図８】信号分解の場合のいわゆるリフティング・スキームを示す図である。
【図９】信号再構築の場合のいわゆるリフティング・スキームを示す図である。
【図１０】図６及び７の同一性を図３の各バンク・フィルタに適用することによって得られた従来のウェーブレット分解の３つのレベルの１つを示す図である。
【図１１】図６及び７の同一性を図３の各バンク・フィルタに適用することによって得られたクラシカル・ウェーブレット分解の３つのレベルの１つを示す図である。
【図１２】図６及び７の同一性を図３の各バンク・フィルタに適用することによって得られた従来のウェーブレット分解の３つのレベルの１つを示す図である。
【図１３】３つのレベル上で一分解についてのサンプル（偶数には０、奇数には１）の選択を示す図である。
【図１４】６４の考え得る分解ベースに対応する６４の考え得るサブサンプリング選択を示す図である。
【図１５】サブサンプリングされたサブバンドをインターリーブすることによりどのようにして冗長サブバンドが生じるかを示す図である。
【図１６】１０の冗長サブバンドのそれぞれがオリジナル画像と同じサイズを有する、一フレームの冗長分解を示す図である。
【図１７】従来の線形走査順序を示す図である。
【図１８】上記画素帰納的アルゴリズムの初期化において改善された因果性を取得可能な因果走査順序を示す図である。
【図１９】ピクセル（ｍ，ｎ）についての冗長平面における完全検索窓を示す図である。
【図１０】
2004531170.tif 000050
【図１１】
2004531170.tif 000051
【図１２】
2004531170.tif 000052
【図１３】
2004531170.tif 000053
【図１４】
2004531170.tif 000054
【図１５】
2004531170.tif 000055
【図１６】
2004531170.tif 000056
【図１９】
2004531170.tif 000057
【国際公開パンフレット】
2004531170.tif 000058
2004531170.tif 000059
2004531170.tif 000060
2004531170.tif 000061
2004531170.tif 000062
2004531170.tif 000063
2004531170.tif 000064
2004531170.tif 000065
2004531170.tif 000066
2004531170.tif 000067
2004531170.tif 000068
2004531170.tif 000069
2004531170.tif 000070
2004531170.tif 000071
2004531170.tif 000072
2004531170.tif 000073
2004531170.tif 000074
2004531170.tif 000075
2004531170.tif 000076
2004531170.tif 000077
2004531170.tif 000078
2004531170.tif 000079
2004531170.tif 000080
2004531170.tif 000081
2004531170.tif 000082
2004531170.tif 000083
2004531170.tif 000084
2004531170.tif 000085
2004531170.tif 000086
2004531170.tif 000087
2004531170.tif 000088
2004531170.tif 000089
【国際調査報告】
2004531170.tif 000090
2004531170.tif 000091
2004531170.tif 000092