(57)【要約】【課題】大域的最小値に近い最小値を達成することにより、より少ない計算時間とより少ないコストで動き推定を得る。【解決手段】動きベクトルの各々についてブロックセット上のエネルギー関数を計算するステップと、ブロックセット上のエネルギー関数を最小化する動きベクトル選択するステップとを有しており、前記計算ステップがブロックセットのサイズに合わせたラグランジュ制約を計算するサブステップを実施する形の階層型動き推定の方法。【選択図】図１
2006025431.tif 000002
【特許請求の範囲】
【請求項１】
ブロックに分割された原画像（１０１）のブロックセット（１０８）に関する複数の動きベクトルの中から動きベクトル（１１１）を選択するための階層型動き推定の方法において、
前記動きベクトルの各々についてブロックセット（１０８）上のエネルギー関数を計算するステップ（１０２）と、
前記ブロックセット（１０８）上のエネルギー関数（１０５）を最小化する動きベクトル（１１１）を選択するステップ（１０７）とを有しており、
前記計算ステップ（１０２）はブロックセット（１０８）のサイズに合わせたラグランジュ制約（１１３）を計算するサブステップを実施する、ことを特徴とする階層型動き推定の方法。
【請求項２】
前記計算ステップ（１０２）は、原画像（１０１）を基にした解像度低減サブステップにより得られた、ブロックセット（１０８）に対応する低解像度画像上の歪み（１０４）を計算するサブステップ（１１０）を実施する、請求項１記載の方法。
【請求項３】
解像度低減サブステップにおいて使用した係数（１１２）をラグランジュ制約（１１３）を計算するサブステップ（１０３）において使用する、請求項２記載の方法。
【請求項４】
現在ブロックセットに隣接するブロックセットへの動きベクトルとして、隣接ブロックセットを含んだより大きなサイズのブロックセットでの前回の反復において選択された動きベクトルを与えることにより、サイズの逓減する一連のブロックセットに対して前記方法を繰り返し実行する、請求項１から３のいずれか１項記載の方法。
【請求項５】
前記ブロックセット（１０８）の逓減するサイズはｎ上での反復とともに２ｎ＊２ｎとなる、請求項４記載の方法。
【請求項６】
解像度逓減サブステップにより得られる画像（１０６）のサイズは、一連のブロックセットにおける次のブロックセットのサイズである、請求項４又は５記載の方法。
【請求項７】
請求項１記載の方法による階層型動き推定フェーズを含むことを特徴とする画像符号化方法。
【請求項８】
ブロックに分割された原画像（１０１）のブロックセット（１０８）に関する複数の動きベクトルの中から動きベクトル（１１１）を選択するための階層型動き推定の装置（１００）において、
該装置（１００）は、
前記動きベクトルの各々についてブロックセット（１０８）上のエネルギー関数を計算する計算モジュール（１０２）と、
前記ブロックセット（１０８）上のエネルギー関数（１０５）を最小化する動きベクトル（１１１）を選択するモジュール（１０７）とを有しており、
前記計算モジュール（１０２）はブロックセット（１０８）のサイズに合わせたラグランジュ制約（１１３）を計算するサブモジュールを実施する、ことを特徴とする階層型動き推定の装置（１００）。
【請求項９】
前記計算モジュール（１０２）は、原画像（１０１）を基にした解像度低減サブモジュールにより得られたブロックセット（１０８）に対応する低解像度画像上の歪み（１０４）を計算する計算サブモジュール（１１０）を実施する、請求項８記載の装置（１００）。
【請求項１０】
現在ブロックセットに隣接するブロックセットへの動きベクトルとして、隣接ブロックセットを含んだより大きなサイズのブロックセットでの前回の反復において選択された動きベクトルを与えることにより、サイズの逓減する一連のブロックセットに対して動きベクトル（１１１）の選択を繰り返し実行する手段を有している、請求項６又は７記載の装置。
【請求項１１】
前記ブロックセット（１０８）の逓減するサイズは、ｎ上での反復とともに２ｎ＊２ｎとなる、請求項１０記載の装置。
【請求項１２】
解像度逓減サブモジュールにより得られる画像（１０６）のサイズは、一連のブロックセットにおける次のブロックセットのサイズである、請求項１０又は１１記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像圧縮分野向けの階層型動き推定の方法に関する。本方法は、ブロックに分割されたいわゆる原解像度を示す画像内のブロックセットに関する動きベクトルの選択を可能にする。
【背景技術】
【０００２】
本発明の分野は圧縮、とりわけ、ブロック単位での符号化スキームに基づいた、ＭＰＥＧ−２、ＭＰＥＧ−４、パート２又は１０のビデオ圧縮である。これらの圧縮スキームはマクロブロックと呼ばれる基本エンティティに対して作用する。以下では、ブロックという用語は、比較的小さな任意のサイズのブロックの集まりを指すことがあり、したがって特にマクロブロックを指す場合がある。しかし、本発明はブロックにより記述される動きベクトル場を使用するいずれのビデオ符号化スキームにおいても実施することができる。
【０００３】
画像圧縮の分野において、インター動きベクトルはビデオ信号を圧縮するためにビデオ信号の時間的冗長性を利用することを狙いとしている。したがって、その原理は画像内容を予測し、この予測において生じた誤差のみを符号化することである。ＭＰＥＧ規格は時間的冗長性の低下を最適化するために画像内で動き補償の技術を実施する。こうして、動き推定、動き補償、及び符号化といったいくつかのステップが区別される。上述のように、本発明は動き推定に関している。
【０００４】
原則として、ビデオシーケンス内の動きは単一のベクトルによってはモデル化できない。それゆえ、画像の各マクロブロックにモーションキューが割当てられる。動き推定演算は、参照画像内のマクロブロックで、符号化すべきマクロブロックに最も似たマクロブロックを決定することができるようにする。この探索アルゴリズムは標準化されておらず、その効率はコーダの性能及びその複雑さに根本的な影響を与える。
【０００５】
最も使用されるプロシージャはブロックマッチングである：マクロブロックは参照画像探索ゾーン内でテストされたベクトルによって指示されるマクロブロックと比較される。ベクトルは、ＭＰＥＧ−２規格の場合では、半ピクセルの精度で決定される。選択はピクセル値間の差分絶対和の観点からの差分と、場合によっては、ベクトル場の符号化コストをも最小化するマクロブロックで行われる。なお、ピクセル値間の差分絶対和を以下では歪みと呼ぶ。このようなプロシージャは、原解像度で画像全体にわたって探索を行うため、計算時間がかかる。さらに、推定のプロセスが単解像度によるものであるため、一般に、歪み／符号化コストの妥協であるベクトル場の局所的最小値に相当するベクトル場に収束する。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の課題は上記の欠点を生じない動き推定の方法を提供することである。本発明による動き推定方法は、大域的最小値に近い最小値を達成することにより、より少ない所要計算時間とより少ない所要コストで動き推定を得ることを可能にする。
【課題を解決するための手段】
【０００７】
上記課題は、ブロックに分割された原画像のブロックセットに関する複数の動きベクトルの中から動きベクトルを選択するための階層型動き推定の方法において、前記動きベクトルの各々についてブロックセット上のエネルギー関数を計算するステップと、前記ブロックセット上のエネルギー関数を最小化する動きベクトルを選択するステップとを有しており、前記計算ステップがブロックセットのサイズに合わせたラグランジュ制約を計算するサブステップを実施するようにすることにより解決される。
【発明を実施するための最良の形態】
【０００８】
本発明は、ブロックに分割された原画像のブロックセットに関する複数の動きベクトルの中から動きベクトルを選択するための階層型動き推定の方法に関するものであり、本方法は、前記動きベクトルの各々についてブロックセット上のエネルギー関数を計算するステップと、前記ブロックセット上のエネルギー関数を最小化する動きベクトルを選択するステップとを有しており、前記計算ステップはブロックセットのサイズに合わせたラグランジュ制約を計算するサブステップを実施する。
【０００９】
実際には、本発明が提案するラージスケールアプローチは、ブロックセットに対して分析を行うことによって、より大域的な分析を可能にする。ブロックセットのサイズに合わせたラグランジュ制約の使用は計算量の低減を可能にする。
【００１０】
本発明の１つの実施形態によれば、計算ステップは、原画像を基にした解像度低減サブステップにより得られたブロックセットに対応する低解像度画像に関する歪みを計算する計算サブステップを実施する。
【００１１】
多重解像度アプローチで補ったラージスケールアプローチは計算をさらに減らすことができる。というのも、歪みは低解像度画像においてしか計算されないからである。
【００１２】
別の実施形態では、解像度低減サブステップにおいて使用した係数をラグランジュ制約を計算するサブステップにおいて使用する。
【００１３】
このケースでは、ラグランジュ制約は低解像度画像を生成するために使用されるフィルタの特性の関数として適合させられる。
【００１４】
本発明の１つの実施形態によれば、現在ブロックセットに隣接するブロックセットへの動きベクトルとして、隣接ブロックセットを含んだより大きなサイズのブロックセットでの前の反復において選択された動きベクトルを与えることにより、サイズの逓減する一連のブロックセットに対して上記方法を繰り返し実行する。
【００１５】
このマルチスケール反復階層型アプローチによれば、モノスケール及び／又は単解像度アプローチにより可能となる大域的最小値に近い局所的最小値に達すること、したがって、特に、ブロックセット上での符号化コストを最適化することが可能になる。実際、サイズがますます小さくなっていくブロックセットに対して本発明を反復することによって、画像全体にわたって最小値の決定を最適化することが可能になる。局所的最小値が得られる確率は低くなる。
【００１６】
本発明の１つの実施形態によれば、ブロックセットの逓減するサイズは、ｎ上での反復とともに２ｎ＊２ｎとなる。
【００１７】
この実施形態はＭＰＥＧ符号化にとって特に有効である。ＭＰＥＧ符号化では、ブロックは特にマクロブロックにグループ化され、マクロブロックもまた特に２ｎ×２ｎブロックのグループにまとめることができる。例えば、反復の開始ブロックセットは符号化すべき画像内のブロックの可能な最大サイズ２ｎであることができ、一連のブロックセットの次のセットは２ｎ−１のサイズであることができ、以下同様。本発明の方法によれば、動きベクトルはサイズ２ｎのセットに関して選択される。なお、このセットは次の反復におけるサイズ２ｎ−１の４つのセットに相当する。つづいて、本発明にしたがってサイズ２ｎ−１の各セットに関して動きベクトルが決定される。これらのセットはそのあと従来式のスキャン、例えば左から右へ及び上から下へのスキャンによってトラバースされる。そして今度はサイズ２ｎ−２の番になり、以下同様。
【００１８】
本発明の１つの実施形態によれば、解像度低減サブステップにより得られる画像のサイズは、一連のブロックセットにおける次のブロックセットのサイズである。
【００１９】
本発明はまた上記の方法を実施するための装置にも関する。
【００２０】
本発明はまた本発明による方法を実施することにより得られる圧縮画像にも関する。
【００２１】
本発明の他の特性及び利点は種々の実施形態の説明から明らかとなる。実施形態の説明は添付した図面を参照して行われる。
【実施例】
【００２２】
図１に示されているように、本発明による装置１００は、動きベクトルの各々について原画像１０１のブロックセット１０８上のエネルギー関数を計算する計算モジュール１０２を有している。エネルギー関数は簡明性の理由から単一の参照番号１０５で示されているが、同じ１つのブロックセットの複数の動きベクトルに関して計算される。したがって、参照番号１０５のエネルギー関数の値は、評価される動きベクトルと同じ数だけ格納される。
【００２３】
それゆえ、実際、動き推定値を算出するために、ブロックセット１０８ごとに動き場の識別が試みられる。現在画像の各ブロックセット１０８に関して、現在ブロックセット１０８の良好な予測を提供すると同時に符号化コストを制限する動きベクトルの識別が試みられる。これを行うために、エネルギー関数１０５が決定される。エネルギー関数は通常２つの項に分解される。１つは時間的予測の品質尺度に関する項であり、もう１つは動きの符号化のコストに関する項である。
【００２４】
通常、現在画像のブロックｂに関して、時間的予測の品質尺度に関するエネルギーは動き補償誤差に基づいている。我々はＳＡＤと呼ばれる差分絶対和を用いる。ＳＡＤは次のようにして計算される。
【００２５】
【数１】
2006025431.tif 000003
ここで、Ｉｃｕｒｒｅｎｔは現在画像であり、Ｉｒｅｆは参照画像であり、（ｘ，ｙ）はピクセルのアドレスであり、（ｕｘ，ｕｙ）は動きベクトルｕの成分である。
【００２６】
符号化コストに関するエネルギーは、ＭＰＥＧ規格に従って、次式により決定される。
Ｃｂ（ｕ）＝λ．Ｒ（ｕ−ｍｂ）
ここで、λはラグランジュ重み係数であり、Ｒ（…）はベクトルの符号化費用関数であり、ｍｂはブロックｂのベクトルの符号化に関する予測として使用される動きベクトルである。ｍｂは、例えば、それを囲む３つのベクトルのメジアンベクトルとして計算することができる。
【００２７】
したがって、動き推定の問題は関数
【００２８】
【数２】
2006025431.tif 000004
を最小化する問題として扱われる。ブロック全体にわたる計算は多数の計算を必要とし、既に述べたように、とりわけ符号化コストに関して大域的最小値に近い最小値に達することができない。
【００２９】
これらの欠点を回避するため、本発明はマルチスケールアプローチを用いる。図２ｂ及び２ｃに示されているように、スケールｋ＞０では、ブロックセットＢはスケールｋ＝０の２ｋ×２ｋ個のＮ×Ｎブロックｂを含んでいる。
【００３０】
図３に示されているように、ブロックセットＢの近傍は所与のスケールｋにおいてＮｉ（ｉ＝１，…，８）で表示されている。ブロックセットＢ及びＮｉはそれぞれベクトルを有している。Ｂのスケール０におけるサイズＮ×Ｎのブロックはｂｉで表示されており、スケール０におけるサイズＮ×Ｎの隣接ブロックはｎｉで表示されている。
【００３１】
本発明によれば、最小化はブロックセットに対して行われ、有利にはその後により小さなスケールで動きベクトルの別の選択が続く。このように、エネルギー関数の最小化は最大スケールからスケール０まで行われる。所与のスケールで得られた動き場は次のスケールのための初期設定として使用される。所与のスケールの画像に対して最小化を行うための原理は、例えば左から右へ及び上から下へのスキャンによって、ブロックセットを１つずつ取り込み、各ブロックセットに関して、最小のエネルギー関数値を提供するベクトルを選択することである。
【００３２】
ブロックセットへのベクトルｕの割当てはブロックセット自体に影響を与えるだけでなく、隣接ブロックにも影響を与える。それは、隣接ブロックセットの動きベクトルが所与のブロックセットの動きベクトルの符号化に使用されるという理由からである。したがって、この影響を評価し、それを最小化することが、エネルギー関数の計算の役割である。
【００３３】
他方で、動きの符号化コストに相当するエネルギー関数の項は以下では文脈性エネルギーと呼ばれる。このエネルギーは考察されるブロックセット及びその近傍に関する符号化コストを考慮する。
【００３４】
したがって、図３を参照すると、ベクトルｕに対するブロックセットＢの文脈性エネルギーは
【００３５】
【数３】
2006025431.tif 000005
に等しい。ここで、Ｖｎはブロックｎのベクトルであり、
Ｃｂ（ｘ）はベクトルｘのブロックｂ⊂Ｂに関する符号化コストであり、Ｃｂ（ｘ）＝λ．Ｒ（ｘ−ｍｂ）の形で表され、
Ｃｎ（ｘ／ｕ）は、ブロックセットＢのベクトルがｕであることを知った上でのベクトルｘのブロックｎ⊂Ｎに関する符号化コストであり、Ｃｎ（ｘ／ｕ）＝λ．Ｒ（ｘ−ｍｎ（ｕ））の形で表され、ｍｎ（ｕ）はブロックセットＢのベクトルがｕであることを知った上でのブロックｎの予測動きベクトルである。
【００３６】
ブロックセットＢに含まれているブロックｂＫ＋１及びｂＫ×Ｋに関しては、動きベクトルはｕである。したがって、これらのブロックについては、Ｃｂ（ｕ）＝λ．Ｒ（０）はｕに依存しない。
【００３７】
ブロックｎ１〜ｎ３Ｋ＋２及びｎ４Ｋ＋４に関しては、動きベクトルはｕに依存しない。実際、規格で定義され、図５においてハッチングで表示されているように、ブロックｂの３つの隣接ブロックがｕを含まないか、又は、１つがｕを含み、他の２つが同一のベクトルｖを含むかである。したがって、３つのベクトルのメジアンは、動きベクトルの定義により、ｖに相当する。
【００３８】
我々はこうして次の結果を得る：
【００３９】
【数４】
2006025431.tif 000006
ただし、γはｕに依存しない。
【００４０】
この式の項は以下のように明示的にすることができる：
【００４１】
【数５】
2006025431.tif 000007
最終的にこれから次式が得られる：
【００４２】
【数６】
2006025431.tif 000008
【００４３】
このように、ブロックセットＢのスケールに関係なく、係数λの他には５つの値を計算するだけでよい。係数λはベクトルｕに依存しないので、各スケールについて一度だけ計算される。γを計算する必要はない。というのも、この項はｕに依存しないからである。したがって、テストされる動きベクトルに関係なく、上式の和の右側のみが変化する。こうして、本発明は実行すべき計算の量の低減を可能にする。したがって、動きベクトルの符号化に関するエネルギーの計算は、ブロックセットのサイズに対して決まるラグランジュ制約、すなわち、考察されるスケールにおけるラグランジュ制約λの計算を実施する。
【００４４】
単一ブロックに相当する最小スケール、すなわち、ｋ＝０に対しては、文脈性エネルギーは次の形で表される：
【００４５】
【数７】
2006025431.tif 000009
一方、理論上では、動き補償誤差に関するエネルギーはブロックセットＢのスケール０におけるすべてのブロックにわたるＳＡＤの和である。計算の負荷を低減するため、本発明は多重解像度アプローチを用いる。それゆえ、原解像度とは異なる解像度の画像が現在画像と参照画像とについて構成される。複数の解像度にわたって本発明を繰り返し実行すると、画像の多重解像度ピラミッドが構成されることが分かる。図４に示されているように、このピラミッドにおいて、図４ｂ又は図４ｃのレベルｋにおけるサイズＮ×Ｎのブロックは、図４ａのレベル０におけるサイズＮ×Ｎの２ｋ×２ｋ個のブロックのグループに相応している。したがって、スケールｋのＮ×Ｎブロックはスケール０のブロックセットとマッチする。
【００４６】
解像度の異なる画像にわたって歪みの計算を行うために、計算モジュール１０２は、ブロックセット１０８に対応する画像１０６の歪み１０４を計算する計算サブモジュールと連携する。なお、画像１０６は、原画像１０１に基づいて解像度を低減させるサブモジュール１０９の動作により得られたものである。
【００４７】
低解像度画像１０６は、例えば、原解像度画像１０１から生じる少なくともブロックセット１０８のローパスフィルタリングと、それに続く係数２でのサブサンプリングとによって得られる。したがって、例えば、低解像度画像内のサイズＮ×Ｎのブロックは原解像度画像１０１内のサイズＮ×Ｎのブロックセット１０８に相応する。
【００４８】
実際、図４に示されているように、このケースは、ブロックセット１０８のサイズがブロックセットのサイズ系列における次のサイズに等しくなるように解像度の低減によって減少するケースに相当する。このようなサイズ系列は本発明による方法を繰り返し実行するために用いられる。
【００４９】
本発明は、低解像度画像上での計算を原解像度での計算に使用できるようにするために、２つの解像度について独立に得られた歪みの間の関連性を解除することを提案する。
【００５０】
したがって、本発明によれば、差分絶対和に関して、原解像度画像内のブロックセットに相応するブロックである低解像度画像のサイズＮ×ＮのブロックにわたるＳＡＤと原解像度画像のサイズＮ×ＮのブロックのＳＡＤの和との間に近似関係が見いだされる。
【００５１】
ＳＡＤの計算において使用される画像信号ｘは正規分布に従う無相関の信号と見なされる。
ｘ〜Ｎ（μ，σ）
この信号のローパスフィルタリングとそれに続くサブサンプリングとにより得られる線形と想定される信号ｙは、以下の統計的特性を有する無相関の信号である：
【００５２】
【数８】
2006025431.tif 000010
ここで、α（ｉ，ｊ）は低解像度画像を構成するために使用されるローパスフィルタの係数を成している。例えば、フィルタは次のようなものとすることができる：
α（０，０）＝０．０６２５  α（０，１）＝０．１２５  α（０，２）＝０．０６２５
α（１，０）＝０．１２５    α（１，１）＝０．２５    α（０，２）＝０．１２５
α（２，０）＝０．０６２５  α（２，１）＝０．１２５  α（２，２）＝０．０６２５
したがって、所与の解像度ｋにおけるブロックのＳＡＤは、次式によって、より高い解像度ｋ−１における相応するブロックのＳＡＤと相関しているものと見なすことができる：
【００５３】
【数９】
2006025431.tif 000011
【００５４】
反復適用により、低解像度画像上のサイズＮ×ＮのブロックにわたるＳＡＤの計算は、以下の式にしたがって、原サイズの画像におけるサイズＮ×Ｎの相応するブロックのＳＡＤの和を近似することができる：
【００５５】
【数１０】
2006025431.tif 000012
ここで、ＳＡＤ０は原解像度画像上のブロックのＳＡＤである。係数４は、所与のレベルのブロックがより低いレベルにおいて相応する４つのブロックを有しているという事実に因る。
【００５６】
装置はエネルギー関数を最小化する第１の動きベクトルを選択するためのモジュールを有しており、この動きベクトルは動きの符号化コストに相応するエネルギーと前記ブロックセット上の動き補償誤差に相応するエネルギーとの和を計算することにより得られる。
【００５７】
ゆえに、ブロックセットＢに対するベクトルｕは関数
【００５８】
【数１１】
2006025431.tif 000013
を最小化する動きベクトルである。
【００５９】
具体的には、最適なベクトルの探索は関数
【００６０】
【数１２】
2006025431.tif 000014
を最小化するベクトルの探索である。ここで、
【００６１】
【数１３】
2006025431.tif 000015
である。
【００６２】
λｋに相当するラグランジュ制約１１３は、有利には低解像度画像１０６の生成に使用されるフィルタの係数１１２を受け取る計算サブモジュール１０３において計算される。ブロックセットのサイズに合わせたこの新しい形のラグランジュ制約１１３は計算を大いに簡略化すると同時に、大域的最小値に近い最小値に確実に達することができるようにする。というのも、本発明による方法をサイズの逓減するグリッドで複数のブロックセットにわたって繰り返し実行する場合、エネルギー関数の最小化は初め大きなスケールで実行することができるからである。本発明によれば、有利には、ブロックセットの各サイズについて、低解像度ブロックセットの画像上で歪みが計算される。
【００６３】
このように、本発明によれば、ブロックセットのサイズの下降列、例えば、ｎ上での反復とともに２ｎ×２ｎのサイズとなる下降列にわたって、本発明による方法を繰り返し実行することにより、最も粗いスケールに基づいて最適化を行うことが可能である。各セットをトラバースするためには、通常のスキャンが使用される。
【００６４】
本発明は説明した実施形態に限定されるものではなく、当業者は様々な択一的実施形態の存在に気付くであろう。
【図面の簡単な説明】
【００６５】
【図１】本発明による装置の線図を示す。
【図２】マルチスケール構造を示す。
【図３】ブロックセットＢに対する本発明の動作を図解したものである。
【図４】多重解像度構造を示す。
【図５】符号化コストの計算のためのブロックに隣接するブロックを示す。
【符号の説明】
【００６６】
１００  動き推定装置
１０１  原画像
１０２  計算モジュール
１０３  計算サブモジュール
１０４  歪み
１０５  エネルギー関数
１０６  低解像度画像
１０８  ブロックセット
１０９  解像度低減サブモジュール
１１０  計算サブモジュール
１１１  動きベクトル
【図１】
2006025431.tif 000016
【図２】
2006025431.tif 000017
【図３】
2006025431.tif 000018
【図４】
2006025431.tif 000019
【図５】
2006025431.tif 000020