JP4887009B2 - ブロックセットの符号化のために動きベクトルを選択する方法及び装置 - Google Patents

Description

本発明は画像圧縮分野向けの階層型動き推定の方法に関する。本方法は、ブロックに分割されたいわゆる原解像度を示す画像内のブロックセットに関する動きベクトルの選択を可能にする。

本発明の分野は圧縮、とりわけ、ブロック単位での符号化スキームに基づいた、ＭＰＥＧ−２、ＭＰＥＧ−４、パート２又は１０のビデオ圧縮である。これらの圧縮スキームはマクロブロックと呼ばれる基本エンティティに対して作用する。以下では、ブロックという用語は、比較的小さな任意のサイズのブロックの集まりを指すことがあり、したがって特にマクロブロックを指す場合がある。しかし、本発明はブロックにより記述される動きベクトル場を使用するいずれのビデオ符号化スキームにおいても実施することができる。

画像圧縮の分野において、インター動きベクトルはビデオ信号を圧縮するためにビデオ信号の時間的冗長性を利用することを狙いとしている。したがって、その原理は画像内容を予測し、この予測において生じた誤差のみを符号化することである。ＭＰＥＧ規格は時間的冗長性の低下を最適化するために画像内で動き補償の技術を実施する。こうして、動き推定、動き補償、及び符号化といったいくつかのステップが区別される。上述のように、本発明は動き推定に関している。

原則として、ビデオシーケンス内の動きは単一のベクトルによってはモデル化できない。それゆえ、画像の各マクロブロックにモーションキューが割当てられる。動き推定演算は、参照画像内のマクロブロックで、符号化すべきマクロブロックに最も似たマクロブロックを決定することができるようにする。この探索アルゴリズムは標準化されておらず、その効率はコーダの性能及びその複雑さに根本的な影響を与える。

最も使用されるプロシージャはブロックマッチングである：マクロブロックは参照画像探索ゾーン内でテストされたベクトルによって指示されるマクロブロックと比較される。ベクトルは、ＭＰＥＧ−２規格の場合では、半ピクセルの精度で決定される。選択はピクセル値間の差分絶対和の観点からの差分と、場合によっては、ベクトル場の符号化コストをも最小化するマクロブロックで行われる。なお、ピクセル値間の差分絶対和を以下では歪みと呼ぶ。このようなプロシージャは、原解像度で画像全体にわたって探索を行うため、計算時間がかかる。さらに、推定のプロセスが単解像度によるものであるため、一般に、歪み／符号化コストの妥協であるベクトル場の局所的最小値に相当するベクトル場に収束する。

本発明の課題は上記の欠点を生じない動き推定の方法を提供することである。本発明による動き推定方法は、大域的最小値に近い最小値を達成することにより、より少ない所要計算時間とより少ない所要コストで動き推定を得ることを可能にする。

上記課題は、ブロックに分割された原画像のブロックセットに関する複数の動きベクトルの中から動きベクトルを選択するための階層型動き推定の方法において、前記動きベクトルの各々についてブロックセット上のエネルギー関数を計算するステップと、前記ブロックセット上のエネルギー関数を最小化する動きベクトルを選択するステップとを有しており、前記計算ステップがブロックセットのサイズに合わせたラグランジュ制約を計算するサブステップを実施するようにすることにより解決される。

本発明は、ブロックに分割された原画像のブロックセットに関する複数の動きベクトルの中から動きベクトルを選択するための階層型動き推定の方法に関するものであり、本方法は、前記動きベクトルの各々についてブロックセット上のエネルギー関数を計算するステップと、前記ブロックセット上のエネルギー関数を最小化する動きベクトルを選択するステップとを有しており、前記計算ステップはブロックセットのサイズに合わせたラグランジュ制約を計算するサブステップを実施する。

実際には、本発明が提案するアプローチは、ブロックセットに対して分析を行うことを可能にする。ブロックセットのサイズに合わせたラグランジュ制約の使用は計算量の低減を可能にする。

本発明の１つの実施形態によれば、計算ステップは、原画像を基にした解像度低減サブステップにより得られたブロックセットに対応する低解像度画像に関する歪みを計算する計算サブステップを実施する。

多重解像度アプローチで補ったラージスケールアプローチは計算をさらに減らすことができる。というのも、歪みは低解像度画像においてしか計算されないからである。

別の実施形態では、解像度低減サブステップにおいて使用した係数をラグランジュ制約を計算するサブステップにおいて使用する。

このケースでは、ラグランジュ制約は低解像度画像を生成するために使用されるフィルタの特性の関数として適合させられる。

本発明の１つの実施形態によれば、現在ブロックセットに隣接するブロックセットへの動きベクトルとして、隣接ブロックセットを含んだより大きなサイズのブロックセットでの前の反復において選択された動きベクトルを与えることにより、サイズの逓減する一連のブロックセットに対して上記方法を繰り返し実行する。

このマルチスケール反復階層型アプローチによれば、モノスケール及び／又は単解像度アプローチにより可能となる大域的最小値に近い局所的最小値に達すること、したがって、特に、ブロックセット上での符号化コストを最適化することが可能になる。実際、サイズがますます小さくなっていくブロックセットに対して本発明を反復することによって、画像全体にわたって最小値の決定を最適化することが可能になる。局所的最小値が得られる確率は低くなる。

本発明の１つの実施形態によれば、ブロックセットの逓減するサイズは、ｎ上での反復とともに２^ｎ＊２^ｎとなる。

この実施形態はＭＰＥＧ符号化にとって特に有効である。ＭＰＥＧ符号化では、ブロックは特にマクロブロックにグループ化され、マクロブロックもまた特に２^ｎ×２^ｎブロックのグループにまとめることができる。例えば、反復の開始ブロックセットは符号化すべき画像内のブロックの可能な最大サイズ２^ｎであることができ、一連のブロックセットの次のセットは２^ｎ−１のサイズであることができ、以下同様。本発明の方法によれば、動きベクトルはサイズ２^ｎのセットに関して選択される。なお、このセットは次の反復におけるサイズ２^ｎ−１の４つのセットに相当する。つづいて、本発明にしたがってサイズ２^ｎ−１の各セットに関して動きベクトルが決定される。これらのセットはそのあと従来式のスキャン、例えば左から右へ及び上から下へのスキャンによってトラバースされる。そして今度はサイズ２^ｎ−２の番になり、以下同様。

本発明の１つの実施形態によれば、解像度低減サブステップにより得られる画像のサイズは、一連のブロックセットにおける次のブロックセットのサイズである。

本発明はまた上記の方法を実施するための装置にも関する。

本発明はまた本発明による方法を実施することにより得られる圧縮画像にも関する。

本発明の他の特性及び利点は種々の実施形態の説明から明らかとなる。実施形態の説明は添付した図面を参照して行われる。

図１に示されているように、本発明による装置１００は、動きベクトルの各々について原画像１０１のブロックセット１０８上のエネルギー関数を計算する計算モジュール１０２を有している。エネルギー関数は簡明性の理由から単一の参照番号１０５で示されているが、同じ１つのブロックセットの複数の動きベクトルに関して計算される。したがって、参照番号１０５のエネルギー関数の値は、評価される動きベクトルと同じ数だけ格納される。

それゆえ、実際、動き推定値を算出するために、ブロックセット１０８ごとに動き場の識別が試みられる。現在画像の各ブロックセット１０８に関して、現在ブロックセット１０８の良好な予測を提供すると同時に符号化コストを制限する動きベクトルの識別が試みられる。これを行うために、エネルギー関数１０５が決定される。エネルギー関数は通常２つの項に分解される。１つは時間的予測の品質尺度に関する項であり、もう１つは動きの符号化のコストに関する項である。

通常、現在画像のブロックｂに関して、時間的予測の品質尺度に関するエネルギーは動き補償誤差に基づいている。我々はＳＡＤと呼ばれる差分絶対和を用いる。ＳＡＤは次のようにして計算される。

ここで、Ｉ_{ｃｕｒｒｅｎｔ}は現在画像であり、Ｉ_ｒｅｆは参照画像であり、（ｘ，ｙ）はピクセルのアドレスであり、（ｕ_ｘ，ｕ_ｙ）は動きベクトルｕの成分である。

符号化コストに関するエネルギーは、ＭＰＥＧ規格に従って、次式により決定される。
Ｃｂ（ｕ）＝λ．Ｒ（ｕ−ｍｂ）
ここで、λはラグランジュ重み係数であり、Ｒ（…）はベクトルの符号化費用関数であり、ｍｂはブロックｂのベクトルの符号化に関する予測として使用される動きベクトルである。ｍｂは、例えば、それを囲む３つのベクトルのメジアンベクトルとして計算することができる。

したがって、動き推定の問題は関数

を最小化する問題として扱われる。ブロック全体にわたる計算は多数の計算を必要とし、既に述べたように、とりわけ符号化コストに関して大域的最小値に近い最小値に達することができない。

これらの欠点を回避するため、本発明はマルチスケールアプローチを用いる。図２ｂ及び２ｃに示されているように、スケールｋ＞０では、ブロックセットＢはスケールｋ＝０の２^ｋ×２^ｋ個のＮ×Ｎブロックｂを含んでいる。

図３に示されているように、ブロックセットＢの近傍は所与のスケールｋにおいてＮ_ｉ（ｉ＝１，…，８）で表示されている。ブロックセットＢ及びＮ_ｉはそれぞれベクトルを有している。Ｂのスケール０におけるサイズＮ×Ｎのブロックはｂ_ｉで表示されており、スケール０におけるサイズＮ×Ｎの隣接ブロックはｎ_ｉで表示されている。

本発明によれば、最小化はブロックセットに対して行われ、有利にはその後により小さなスケールで動きベクトルの別の選択が続く。このように、エネルギー関数の最小化は最大スケールからスケール０まで行われる。所与のスケールで得られた動き場は次のスケールのための初期設定として使用される。所与のスケールの画像に対して最小化を行うための原理は、例えば左から右へ及び上から下へのスキャンによって、ブロックセットを１つずつ取り込み、各ブロックセットに関して、最小のエネルギー関数値を提供するベクトルを選択することである。

ブロックセットへのベクトルｕの割当てはブロックセット自体に影響を与えるだけでなく、隣接ブロックにも影響を与える。それは、隣接ブロックセットの動きベクトルが所与のブロックセットの動きベクトルの符号化に使用されるという理由からである。したがって、この影響を評価し、それを最小化することが、エネルギー関数の計算の役割である。

他方で、動きの符号化コストに相当するエネルギー関数の項は以下では文脈性エネルギーと呼ばれる。このエネルギーは考察されるブロックセット及びその近傍に関する符号化コストを考慮する。

したがって、図３を参照すると、ベクトルｕに対するブロックセットＢの文脈性エネルギーは

に等しい。ここで、Ｖ_ｎはブロックｎのベクトルであり、
Ｃ_ｂ（ｘ）はベクトルｘのブロックｂ⊂Ｂに関する符号化コストであり、Ｃ_ｂ（ｘ）＝λ．Ｒ（ｘ−ｍ_ｂ）の形で表され、
Ｃ_ｎ（ｘ／ｕ）は、ブロックセットＢのベクトルがｕであることを知った上でのベクトルｘのブロックｎ⊂Ｎに関する符号化コストであり、Ｃ_ｎ（ｘ／ｕ）＝λ．Ｒ（ｘ−ｍ_ｎ（ｕ））の形で表され、ｍ_ｎ（ｕ）はブロックセットＢのベクトルがｕであることを知った上でのブロックｎの予測動きベクトルである。

ブロックセットＢに含まれているブロックｂ_ｋ＋１ からｂ_Ｋ×Ｋに関しては、動きベクトルはｕである。したがって、これらのブロックについては、Ｃｂ（ｕ）＝λ．Ｒ（０）はｕに依存しない。

ブロックｎ_１〜ｎ_３Ｋ＋２及びｎ_４Ｋ＋４に関しては、動きベクトルはｕに依存しない。実際、規格で定義され、図５においてハッチングで表示されているように、ブロックｂの３つの隣接ブロックがｕを含まないか、又は、１つがｕを含み、他の２つが同一のベクトルｖを含むかである。したがって、３つのベクトルのメジアンは、動きベクトルの定義により、ｖに相当する。

我々はこうして次の結果を得る：

ただし、γはｕに依存しない。

この式の項は以下のように明示的にすることができる：

最終的にこれから次式が得られる：

このように、ブロックセットＢのスケールに関係なく、係数λの他には５つの値を計算するだけでよい。係数λはベクトルｕに依存しないので、各スケールについて一度だけ計算される。γを計算する必要はない。というのも、この項はｕに依存しないからである。したがって、テストされる動きベクトルに関係なく、上式の和の右側のみが変化する。こうして、本発明は実行すべき計算の量の低減を可能にする。したがって、動きベクトルの符号化に関するエネルギーの計算は、ブロックセットのサイズに対して決まるラグランジュ制約、すなわち、考察されるスケールにおけるラグランジュ制約λの計算を実施する。

単一ブロックに相当する最小スケール、すなわち、ｋ＝０に対しては、文脈性エネルギーは次の形で表される：

一方、理論上では、動き補償誤差に関するエネルギーはブロックセットＢのスケール０におけるすべてのブロックにわたるＳＡＤの和である。計算の負荷を低減するため、本発明は多重解像度アプローチを用いる。それゆえ、原解像度とは異なる解像度の画像が現在画像と参照画像とについて構成される。複数の解像度にわたって本発明を繰り返し実行すると、画像の多重解像度ピラミッドが構成されることが分かる。図４に示されているように、このピラミッドにおいて、図４ｂ又は図４ｃのレベルｋにおけるサイズＮ×Ｎのブロックは、図４ａのレベル０におけるサイズＮ×Ｎの２^ｋ×２^ｋ個のブロックのグループに相応している。したがって、スケールｋのＮ×Ｎブロックはスケール０のブロックセットとマッチする。

解像度の異なる画像にわたって歪みの計算を行うために、計算モジュール１０２は、ブロックセット１０８に対応する画像１０６の歪み１０４を計算する計算サブモジュールと連携する。なお、画像１０６は、原画像１０１に基づいて解像度を低減させるサブモジュール１０９の動作により得られたものである。

低解像度画像１０６は、例えば、原解像度画像１０１から生じる少なくともブロックセット１０８のローパスフィルタリングと、それに続く係数２でのサブサンプリングとによって得られる。したがって、例えば、低解像度画像内のサイズＮ×Ｎのブロックは原解像度画像１０１内のサイズＮ×Ｎのブロックセット１０８に相応する。

実際、図４に示されているように、このケースは、ブロックセット１０８のサイズがブロックセットのサイズ系列における次のサイズに等しくなるように解像度の低減によって減少するケースに相当する。このようなサイズ系列は本発明による方法を繰り返し実行するために用いられる。

本発明は、低解像度画像上での計算を原解像度での計算に使用できるようにするために、２つの解像度について独立に得られた歪みの間の関連性を解除することを提案する。

したがって、本発明によれば、差分絶対和に関して、原解像度画像内のブロックセットに相応するブロックである低解像度画像のサイズＮ×ＮのブロックにわたるＳＡＤと原解像度画像のサイズＮ×ＮのブロックのＳＡＤの和との間に近似関係が見いだされる。

ＳＡＤの計算において使用される画像信号ｘは正規分布に従う無相関の信号と見なされる。
ｘ〜Ｎ（μ，σ）
この信号のローパスフィルタリングとそれに続くサブサンプリングとにより得られる線形と想定される信号ｙは、以下の統計的特性を有する無相関の信号である：

ここで、α（ｉ，ｊ）は低解像度画像を構成するために使用されるローパスフィルタの係数を成している。例えば、フィルタは次のようなものとすることができる：
α（０，０）＝０．０６２５ α（０，１）＝０．１２５ α（０，２）＝０．０６２５
α（１，０）＝０．１２５ α（１，１）＝０．２５ α（０，２）＝０．１２５
α（２，０）＝０．０６２５ α（２，１）＝０．１２５ α（２，２）＝０．０６２５
したがって、所与の解像度ｋにおけるブロックのＳＡＤは、次式によって、より高い解像度ｋ−１における相応するブロックのＳＡＤと相関しているものと見なすことができる：

反復適用により、低解像度画像上のサイズＮ×ＮのブロックにわたるＳＡＤの計算は、以下の式にしたがって、原サイズの画像におけるサイズＮ×Ｎの相応するブロックのＳＡＤの和を近似することができる：

ここで、ＳＡＤ^０は原解像度画像上のブロックのＳＡＤである。係数４は、所与のレベルのブロックがより低いレベルにおいて相応する４つのブロックを有しているという事実に因る。

装置はエネルギー関数を最小化する第１の動きベクトルを選択するためのモジュールを有しており、この動きベクトルは動きの符号化コストに相応するエネルギーと前記ブロックセット上の動き補償誤差に相応するエネルギーとの和を計算することにより得られる。

ゆえに、ブロックセットＢに対するベクトルｕは関数

を最小化する動きベクトルである。

具体的には、最適なベクトルの探索は関数

を最小化するベクトルの探索である。ここで、

である。

λ_ｋに相当するラグランジュ制約１１３は、有利には低解像度画像１０６の生成に使用されるフィルタの係数１１２を受け取る計算サブモジュール１０３において計算される。ブロックセットのサイズに合わせたこの新しい形のラグランジュ制約１１３は計算を大いに簡略化すると同時に、大域的最小値に近い最小値に確実に達することができるようにする。というのも、本発明による方法をサイズの逓減するグリッドで複数のブロックセットにわたって繰り返し実行する場合、エネルギー関数の最小化は初め大きなスケールで実行することができるからである。本発明によれば、有利には、ブロックセットの各サイズについて、低解像度ブロックセットの画像上で歪みが計算される。

このように、本発明によれば、ブロックセットのサイズの下降列、例えば、ｎ上での反復とともに２^ｎ×２^ｎのサイズとなる下降列にわたって、本発明による方法を繰り返し実行することにより、最も粗いスケールに基づいて最適化を行うことが可能である。各セットをトラバースするためには、通常のスキャンが使用される。

本発明は説明した実施形態に限定されるものではなく、当業者は様々な択一的実施形態の存在に気付くであろう。

本発明による装置の線図を示す。 マルチスケール構造を示す。 ブロックセットＢに対する本発明の動作を図解したものである。 多重解像度構造を示す。 符号化コストの計算のためのブロックに隣接するブロックを示す。

符号の説明

１００ 動き推定装置
１０１ 原画像
１０２ 計算モジュール
１０３ 計算サブモジュール
１０４ 歪み
１０５ エネルギー関数
１０６ 低解像度画像
１０８ ブロックセット
１０９ 解像度低減サブモジュール
１１０ 計算サブモジュール
１１１ 動きベクトル

Claims (9)

1. ブロックに分割された原画像のブロックセットに関して与えられた複数の動きベクトルの中から動きベクトルを選択するための階層型動き推定の方法において、
   前記ブロックセットに所定の係数のフィルタを適用し、低解像度画像を得るステップと、
   前記適用したフィルタの係数を使用して、前記低解像度画像の解像度の関数であるラグランジュ制約を計算するステップと、
   前記ブロックセットに対応する前記低解像度画像のピクセル値間の差分絶対和である歪みを計算するステップと、
   前記計算されたラグランジュ制約および前記計算された歪みに基づいて、前記動きベクトルの各々について、ブロックセットのエネルギー関数を計算するステップと、
   前記ブロックセットに関するエネルギー関数を最小化する動きベクトルを選択するステップとを含むことを特徴とする階層型動き推定の方法。
2. 現在のブロックセットに隣接するブロックセットへの動きベクトルとして、隣接ブロックセットを含んだより大きなサイズのブロックセットでの前回の反復において選択された動きベクトルを与えることにより、サイズの逓減する一連のブロックセットに対して前記方法を繰り返し実行する、請求項１記載の方法。
3. 前記ブロックセットの逓減するサイズは、ｎ回の反復を伴う、２ⁿ＊２ⁿとなる、請求項２記載の方法。
4. 前記低解像度画像のサイズは、一連のブロックセットにおける次のブロックセットのサイズである、請求項２又は３記載の方法。
5. 請求項１記載の方法による階層型動き推定フェーズを含むことを特徴とする画像符号化方法。
6. ブロックに分割された原画像のブロックセットに関して与えられた複数の動きベクトルの中から動きベクトルを選択するための階層型動き推定の装置において、
   該装置は、
   前記ブロックセットに所定の係数のフィルタを適用し、低解像度画像を得るモジュールと、
   前記適用したフィルタの係数を使用して、前記低解像度画像の解像度の関数であるラグランジュ制約を計算するモジュールと、
   前記ブロックセットに対応する前記低解像度画像のピクセル値間の差分絶対和である歪みを計算するモジュールと、
   前記計算されたラグランジュ制約および前記計算された歪みに基づいて、前記動きベクトルの各々について、ブロックセットのエネルギー関数を計算する計算モジュールと、
   前記ブロックセットに関するエネルギー関数を最小化する動きベクトルを選択するモジュールとを備えることを特徴とする階層型動き推定の装置。
7. 現在のブロックセットに隣接するブロックセットへの動きベクトルとして、隣接ブロックセットを含んだより大きなサイズのブロックセットでの前回の反復において選択された動きベクトルを与えることにより、サイズの逓減する一連のブロックセットに対して動きベクトルの選択を繰り返し実行する手段を有している、請求項６記載の装置。
8. 前記ブロックセットの逓減するサイズは、ｎ回の反復を伴う、２ⁿ＊２ⁿとなる、請求項７記載の装置。
9. 前記低解像度画像のサイズは、一連のブロックセットにおける次のブロックセットのサイズである、請求項７又は８記載の装置。

Images