(57)【要約】【課題】グローバル動き推定技法は、高度なビデオ符号化において重要な役割を演じる。グローバル動き推定は符号化効率を上げるために有用であるが、複数パラメータモデルおよび反復的処理を使用するため、非常に複雑である。【解決手段】本発明は４パラメータの線形グローバル動き推定モデルに基づいている。フレームの特定のブロック動きベクトルから、一組のグローバル動きパラメータが反復的な処理において計算される。反復ループごとに、対称的な動きベクトルブロックにおける突出した動きベクトルが所与の規則セットに従って処理され、それにより反復プロセスの間、対称構造が維持される。【選択図】図１
2007053767.tif 000002
【特許請求の範囲】
【請求項１】
画像（FR）または画像シーケンスについて、各画像を分割したブロックまたはマクロブロックに割り当てられる動きベクトル（mv）からグローバル動きパラメータ（a1、a2、a3、a4）の集合を反復的に計算する方法であって、前記グローバル動きパラメータの計算のために画像のすべてのブロックまたはマクロブロック動きベクトルが使われるのではなく、前記画像（FR）の境界に近いが境界上ではない環（G2、G3）内に位置するブロックまたはマクロブロックの動きベクトルだけしか使われず、各反復ループについて、以下のステップ、すなわち：
・ブロックまたはマクロブロックの前記環内で所定数のブロックまたはマクロブロックに関係している各対称ブロックグループについて、動き量の値または動き成分量の値が候補グローバル動きパラメータの最新セットからの対応するブロックまたはマクロブロック位置について計算された対応する動きベクトルと比べたときに突出している動きベクトルの量を検査し（１５）、
・所与の規則セットに従って、実行されるべき現在およびさらなる反復ループについて、対応する対称ブロックグループの一つまたは複数のもともとの動きベクトル値が修正されて維持されるか、あるいは対応する対称ブロックグループの該動きベクトル値がもはや使われないかを決定し（１５）、
・結果として得られる動きベクトル値から、候補グローバル動きパラメータの更新された集合（a1、a2、a3、a4）を計算し（１３）、
・前記集合の所望のまたは十分な精度が達成されるか、あるいは所与の反復ループ回数に達するかしているかどうかを検査し（１４）、真であれば、対応するグローバル動きパラメータの集合を出力し（１６）、真でなければ、次の反復ループに続く、
ステップが実行されることを特徴とする方法。
【請求項２】
画像（FR）または画像シーケンスについて、各画像を分割したブロックまたはマクロブロックに割り当てられる動きベクトル（mv）からグローバル動きパラメータ（a1、a2、a3、a4）の集合を反復的に計算する装置であって、前記グローバル動きパラメータの計算のために画像のすべてのブロックまたはマクロブロック動きベクトルが使われるのではなく、前記画像の境界に近いが境界上ではない環（G2、G3）内に位置するブロックまたはマクロブロックの動きベクトルだけしか使われず、当該装置が：
・各反復ループにおいて、所定数のブロックまたはマクロブロックに関係している各対称ブロックグループについて、ブロックまたはマクロブロックの前記環内で、動き量の値または動き成分量の値が候補グローバル動きパラメータの最新セットからの対応するブロックまたはマクロブロック位置について計算された対応する動きベクトルと比べたときに突出している動きベクトルの量を検査するよう適応されている手段（６０）と、
・所与の規則セットに従って、実行されるべき現在およびさらなる反復ループについて、対応する対称ブロックグループの一つまたは複数のもともとの動きベクトル値が修正されて維持されるか、あるいは対応する対称ブロックグループの該動きベクトル値がもはや使われないかを決定するよう適応されている手段（６５）と、
・結果として得られる動きベクトル値から、候補グローバル動きパラメータの更新された集合（a1、a2、a3、a4）を計算するよう適応されている手段（６３）と、
・前記集合の所望のまたは十分な精度が達成されるか、あるいは所与の反復ループ回数に達するかしているかどうかを検査し、真であれば、対応するグローバル動きパラメータの集合を出力し、真でなければ、次の反復ループに続くよう適応されている手段（６４）、
とを含むことを特徴とする装置。
【請求項３】
前記対称ブロックグループがそれぞれ４つの動きベクトルについての値を含むことを特徴とする、請求項１記載の方法または請求項２記載の装置。
【請求項４】
請求項３記載の方法または装置であって、前記規則セットが次のようなもの、すなわち：
・対称ブロックグループ中の４つの動き量の値または動き成分量の値のうちの一つが対応するブロックまたはマクロブロック位置について計算された最新の候補グローバル動きに対して突出値である場合、この突出値の位置は現在およびさらなる反復ループについて維持されるが、そのもともとすなわち現在の動きベクトルは最新の候補グローバル動きパラメータの集合を使って対応するブロックまたはマクロブロック位置について計算された動きベクトルによって置き換えられ、
・現在の対称ブロックグループ中の４つの動き量の値または動き成分量の値のうちの二つが対応するブロックまたはマクロブロック位置について計算された最新の候補グローバル動きに対して突出値である場合、このブロックグループの４つのすべての動き量の値または動き成分量の値を除去した後に残る有用ブロックの動き量の値または動き成分量の値が所定の閾値（Tvalid）と比較され、この閾値が前記残りの有用ブロックの動き量の値または動き成分量の値より大きい場合には、前記現在のブロックグループの前記４つのすべての動き量の値または動き成分量の値は突出値を表していると見なされ、対応するブロックの動きベクトルまたは動き成分の値は次の反復ループについては消去され、
そうでない場合には、前記二つの突出値の位置は次の反復ループについては維持されるが、その現在の動きベクトルは最新の候補グローバル動きパラメータの集合からそのブロックまたはマクロブロック位置について計算された動きベクトルによって置き換えられ、
・対称ブロックグループ中の４つの動き量の値または動き成分量の値のうちの三つが対応するブロックまたはマクロブロック位置について計算された最新の候補グローバル動きに対して突出値である場合、その対称ブロックグループ中の突出ブロックまたはマクロブロックのすべての動きベクトルの動き量の値または動き成分量の値は現在およびさらなる反復ループにおける処理から消去される、
というものであることを特徴とする方法または装置。
【請求項５】
ブロックまたはマクロブロックの信頼性のない零動きベクトルが突出であると見なされることを特徴とする、請求項４記載の方法または装置。
【請求項６】
零動きをもつブロックまたはマクロブロックの量がフレームごとに数字Nzeroに蓄積され、前記数字Nzeroが所定の閾値（Tstill）より大きければ、そのフレーム中の場面はグローバル動きがないと考えられることを特徴とする、請求項１、３、４，５のうちいずれか一項記載の方法または請求項２、３，４，５のうちいずれか一項記載の装置。
【請求項７】
前記グローバル動きパラメータの集合がグローバル動きモデル：
【数１】
2007053767.tif 000010
ただし
a1＝zx        a2＝f1(px,zx)
a2＝zy        a4＝f2(py,zy)
に割り当てられる値a1、a2、a3、a4を含んでおり、mvx(k)およびmvy(k)は中心ピクセルのフレーム中心を基準とした座標がx(k),y(k)であるブロックまたはマクロブロックk（k＝0,  1,  ...,  N−1）についての動きベクトルの水平および垂直方向成分であり、Nはフレームごとの、該フレームのグローバル動きを計算するのに動きベクトルを使用しているブロックまたはマクロブロックの数であり、kは一フレーム内を走るブロックまたはマクロブロック番号であり、zxはk番目のマクロブロックのズーム因子水平方向成分、zyはk番目のマクロブロックのズーム因子垂直方向成分であり、pxはパン因子水平方向成分、pyはパン因子垂直方向成分であることを特徴とする、請求項１、３、４，５、６のうちいずれか一項記載の方法または請求項２、３，４，５、６のうちいずれか一項記載の装置。
【請求項８】
前記グローバル動きパラメータ値a1、a2、a3、a4が：
【数２】
2007053767.tif 000011
に従って計算されることを特徴とする、請求項７記載の方法または装置。
【請求項９】
請求項１、３、４、５、６、７、８のうちいずれか一項記載の方法に従って計算された、少なくとも一つのグローバル動きパラメータの集合（a1、a2、a3、a4）を使ってエンコードされ、前記少なくとも一つのグローバル動きパラメータの集合を含んでいるデジタルビデオ信号を含み、または保存し、または記録しているたとえば光ディスクのような記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像または画像シーケンスについて、各画像を分割したブロックに割り当てられる動きベクトルからグローバル動きパラメータの集合を反復的に計算する方法および装置であって、グローバル動きパラメータの計算のために画像のすべてのブロック動きベクトルが使われるのではないものに関する。
【背景技術】
【０００２】
グローバル動き推定（GME:  global  motion  estimation）技法は、MPEG-4ビジュアル・ビデオ符号化規格における「スプライト」ビデオ符号化技法およびH.263+ビデオ符号化規格の付属書Pにおける「参照画像再サンプリング」技法のような、高度なビデオ符号化において重要な役割を演じる。グローバル動き推定は、（特に低ビットレート符号化のための）符号化効率を上げるため、最適化されたビット割り当て、異なる動き属性を調べることで前景コンテンツと背景コンテンツのような低レベルのコンテンツ解析情報を得る際の粗いビデオセグメント化のために有用であり、とりわけ上空飛行監視のようないくつかの特殊な場面をエンコードするために有用である。
【０００３】
図１は、グローバル動き推定を実行するための一般的なフローチャートを示している。参照フレームおよび現在フレームが入力され、続いて使用されるべきグローバル動きモデルが選択される。その後、反復的な処理（たとえばガウス・ニュートン、ガウス・ラフソン、マルカート・レーベンバーグまたは反復的最小二乗）が候補グローバル動きパラメータを推定するために使われる。各反復ループののち、ブロック動きベクトルのいくつかの突出動きベクトルが同定され、次の反復ループの開始前に除去される。これは最適なパラメータ、すなわち十分精確な動きパラメータが受け取られるまで続く。
【０００４】
しかし、GMEは、複数パラメータモデル（４パラメータ、６パラメータあるいは８パラメータモデルさえある）および反復処理を使うことのため、非常に複雑である。この問題を解決することにおいては、非特許文献［１］〜［４］に挙げたような若干の高速GMEアルゴリズムが提案されている。
【０００５】
以下の記述では、ほかに非特許文献［５］〜［７］も参照する。
【０００６】
従来技術においては、グローバル動き推定の方法は大まかに２つの範疇に分類できる：空間領域GMEと周波数領域GMEである。
【非特許文献１】Tuan-Kiang  Chiew,  James  T.  H.  Chung-How  et  al.,  “Rapid  Block-Based  Global  Motion  Estimation  and  its  Applications”,  ICCE,  June  2002
【非特許文献２】Gagan  B.  Rath,  Anamitra  Makur,  “Iterative  Least  Squares  and  Compression  Based  Estimations  for  a  Four-Parameter  Linear  Global  Motion  Model  and  Global  Motion  Compensation”,  IEEE  Transactions  on  Circuits  and  Systems  for  Video  Technology,  volume  9,  number  7,  October  1999,  pp.  1075-1099
【非特許文献３】G.  Sorwar,  M.  M.  Murshed  and  L.  S.  Dooley,  “Fast  Global  Motion  Estimation  using  Iterative  Least-Square  Estimation  Technique”,  2003  Joint  Conference  of  the  Fourth  International  Conference  on  Information,  Communications  and  Signal  Processing  and  Fourth  Pacific-Rim  Conference  on  Multimedia,  ICICS-PCM,  Singapore,  15-18  December  2003
【非特許文献４】Sanjeev  Kumar,  Mainak  Biswas  and  Truong  Q  Nguyen,  “GLOBAL  MOTION  ESTIMATION  IN  FREQUENCY  AND  SPATIAL  DOMAIN”,  ICASSP,  May  2004
【非特許文献５】Yuwen  He,  Bo  Feng,  Shinqiang  Yang,  et  al.,  “Fast  Global  Motion  Estimation  for  Global  Motion  Compensation  Coding”,  ISCSA,  May  2001
【非特許文献６】Yeping  Su,  Ming-Ting  Sun,  Vincent  Hsu,  “Global  Motion  Estimation  From  Coarsely  Sampled  Motion  Vector  Field  And  the  Applications”,  ISCSA,  May  2003
【非特許文献７】Joerg  Heuer,  Andre  Kaup,  “Global  Motion  Estimation  in  Image  Sequences  Using  Robust  Motion  Vector  Field  Segmentation”,  ACM  international  conference  on  Multimedia,  Nov.  1999
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は空間領域でのグローバル動き推定処理を扱う。
【０００８】
計算量〔計算の複雑さ〕と動き推定の精度はGME処理を設計する際の二つの主要な関心事である。GMEのパフォーマンスはより高精度のモデル（すなわち動きパラメータが多いモデル）を使うことによって向上するが、それに伴う処理の複雑さもそれに応じて増加する。
【０００９】
既知のGMEアルゴリズムは計算量と精度の間で非最適なトレードオフを実現しようとする。
【００１０】
いくつかの方法（非特許文献［１］［２］［３］［５］［６］参照）は単純なモデルを使う、すなわち計算量を減らすためにサブサンプリングと階層構造を使う。その際、通例は誤差計量としてSSD（sum  of  squared  differences［差分二乗和］）またはSAD（sum  of  absolute  differences［差分絶対値和］）が使われる。SSD最小化は典型的にはガウス・ニュートン法、ガウス・ラフソン法、マルカート・レーベンバーグ法および反復的最小二乗法といった勾配降下反復法によって達成される。独立した運動オブジェクトおよび不一致運動（miss-matching  motion）の擾乱のため、真のグローバル動き推定に一致しないブロック動きベクトル突出値が消去されないと推定精度は低い。したがって、これらのアルゴリズムは反復の間に精度を改善するために突出値を除去する種々の戦略を使う。
【００１１】
しかし、精度の劣化がなくて計算量が少ないGME処理が必要とされている。非特許文献［２］および［３］に記載されているアルゴリズムに基づいて、そしていくつかの追加的な想定および改良された対称構造に基づいて、より少ない計算量でグローバル動きパラメータを計算するが、動きパラメータの精度または確度は維持する発明的な反復的最小二乗動き推定が記載される。
【００１２】
本発明によって解決されるべき問題は、計算量の少ない処理を用いて精確なグローバル動きパラメータを提供することである。この問題は、請求項１において開示される方法によって解決される。対応する記憶媒体は請求項９において開示される。この方法を利用する装置は請求項２において開示される。
【課題を解決するための手段】
【００１３】
本発明は、４パラメータの線形グローバル動き推定モデルに基づいて反復的最小二乗推定（ILSE:  iterative  least  square  estimation）を用いる、高速なグローバル動きパラメータ推定処理を使用する。
【００１４】
基本的には、フレーム中の各ブロックまたはマクロブロックについて、動きベクトルは前もって計算される、あるいは計算されてある。画像ごとに、そのフレームの関係するすべてのブロックまたはマクロブロック動きベクトルから、グローバル動きパラメータの単一の集合あるいは単一のグローバル動きベクトルが計算される。
【００１５】
反復ループの第一のステップでは、突出点（すなわち突出したブロックまたはマクロブロック動きベクトル）の除去が、オブジェクトの動きはたいてい画像の中心に焦点がある、いくつかの運動オブジェクトは外から画像内部にはいってくる動きをするという推定、そして事前解析に基づいて行われる（事前解析とはたとえば、ローカルな動きベクトル情報であり、弱いテクスチャー情報しか含んでおらず、画像内容中のエッジのところに位置していないブロックについての信頼性のない零動きベクトルなどである）。さらに、反復プロセスの間、対称構造を維持するために、いくつかの改良のための規則が確立される。この維持により、計算負荷削減のためになる、最小二乗推定の結果の簡略化された表式が導出できる。各反復ループにおいて、残った動きベクトル値および残った補正動きベクトル値から、更新された候補グローバル動き推定パラメータが計算される。反復は、所望の、あるいは十分な精度が達成されるまで、あるいは所与のループ回数に達するまで継続される。本発明を使うことにより、計算負荷は最初の反復でざっと68%削減され、その後の反復ではパラメータa1およびa3の計算の間、加算演算の50%が、そしてパラメータa2およびa4の計算の間、乗算演算の100%および加算演算の75%が消去される。このことはのちに詳述する。
【００１６】
本発明は、ビデオ符号化およびセグメント化における最適化された処理のために使用されることができる。
【００１７】
原理的には、本発明の方法は、画像または画像シーケンスについて、各画像を分割したブロックまたはマクロブロックに割り当てられる動きベクトルからグローバル動きパラメータの集合を反復的に計算することであって、前記グローバル動きパラメータの計算のために画像のすべてのブロックまたはマクロブロック動きベクトルは使われず、前記画像の境界に近いが境界上ではない環内に位置するブロックまたはマクロブロックの動きベクトルだけしか使われず、各反復ループについて、以下のステップ、すなわち：
・ブロックまたはマクロブロックの前記環内で所定数のブロックまたはマクロブロックに関係している各対称ブロックグループについて、動き量の値または動き成分量の値が候補グローバル動きパラメータの最新セットからの対応するブロックまたはマクロブロック位置について計算された対応する動きベクトルと比べたときに突出している動きベクトルの量を検査し、
・所与の規則セットに従って、実行されるべき現在およびさらなる反復ループについて、対応する対称ブロックグループの一つまたは複数のもともとの動きベクトル値が修正されて維持されるか、あるいは対応する対称ブロックグループの該動きベクトル値がもはや使われないかを決定し、
・結果として得られる動きベクトル値から、候補グローバル動きパラメータの更新された集合を計算し、
・前記集合の所望のまたは十分な精度が達成されるか、あるいは所与の反復ループ回数に達するかしているかどうかを検査し、真であれば、対応するグローバル動きパラメータの集合を出力し、真でなければ、次の反復ループに続く、
ステップが実行されるものに適合している。
【００１８】
原理的には、本発明の装置は、画像または画像シーケンスについて、各画像を分割したブロックまたはマクロブロックに割り当てられる動きベクトルからグローバル動きパラメータの集合を反復的に計算することであって、前記グローバル動きパラメータの計算のために画像のすべてのブロックまたはマクロブロック動きベクトルは使われず、前記画像の境界に近いが境界上ではない環内に位置するブロックまたはマクロブロックの動きベクトルだけしか使われず：
・各反復ループにおいて、所定数のブロックまたはマクロブロックに関係している各対称ブロックグループについて、ブロックまたはマクロブロックの前記環内で、動き量の値または動き成分量の値が候補グローバル動きパラメータの最新セットからの対応するブロックまたはマクロブロック位置について計算された対応する動きベクトルと比べたときに突出している動きベクトルの量を検査するよう適応されている手段と、
・所与の規則セットに従って、実行されるべき現在およびさらなる反復ループについて、対応する対称ブロックグループの一つまたは複数のもともとの動きベクトル値が修正されて維持されるか、あるいは対応する対称ブロックグループの該動きベクトル値がもはや使われないかを決定するよう適応されている手段と、
・結果として得られる動きベクトル値から、候補グローバル動きパラメータの更新された集合を計算するよう適応されている手段と、
・前記集合の所望のまたは十分な精度が達成されるか、あるいは所与の反復ループ回数に達するかしているかどうかを検査し、真であれば、対応するグローバル動きパラメータの集合を出力し、真でなければ、次の反復ループに続くよう適応されている手段、
とを有するものに適合している。
【００１９】
本発明の追加的な有利な実施形態はそれぞれの従属請求項において開示される。
【００２０】
本発明の例示的な実施形態について付属の図面を参照しつつ述べる。
【発明を実施するための最良の形態】
【００２１】
〈グローバル動きモデル化〉
グローバル動きモデルとしては、２パラメータ並進モデル、４パラメータ回転‐縮尺‐並進（RST:  rotation-scale-translation）モデル、６パラメータ・アフィンモデル、８パラメータ投影モデルといったものがある。一般に、多くのパラメータを使うモデルほどグローバル動きをより正確に記述できるが、同時に計算量が著しく増すのはもちろんである。
【００２２】
しかし、一般にカメラ回転が起こるのはズームやパンよりずっと少ないため、文献［２］はグローバル動きについての一般化された４パラメータモデルを提案している。このモデルはカメラ動きに起因する動きばかりではなく、グローバルオブジェクトに起因する動き、すなわちオブジェクト占有（objects  occupying）をも含んでいる。
【００２３】
ズームおよびパン・モデルは次の二つのモデルに分けられる。GMEパラメータを計算するために使用されるビデオフレーム中にN個のブロックがあるとし、ブロックの動きベクトルはそのブロックの中心のピクセルの動きベクトルであると想定する。(mvx(k),mvy(k))を、中心ピクセルのフレーム中心を基準とした座標が（x(k),y(k)）であるブロックk（k＝0,  1,  ...,  N−1）のローカルな動きベクトル（motion  vector）であるとする。これに監視、カメラ動きモデルは次のように表現できる。ズームとそれに続くパン：
【００２４】
【数３】
2007053767.tif 000003
ここで、kは一フレーム内を走るブロック番号、mvxはk番目のブロックの動きベクトル水平方向x成分値、mvyはk番目のブロックの動きベクトル垂直方向y成分値、zxはk番目のブロックのズーム因子水平方向成分、zyはk番目のブロックのズーム因子垂直方向成分、pxはパン因子水平方向成分、pyはパン因子垂直方向成分である。
パンとそれに続くズーム：
【００２５】
【数４】
2007053767.tif 000004
これら２つのモデルは、本発明で使われる単一のモデルに一般化できる：
【００２６】
【数５】
2007053767.tif 000005
ここで、
a1＝zx        a2＝f1(px,zx)
a2＝zy        a4＝f2(py,zy)
であり、a1、a2、a3、a4がグローバル動きパラメータである。
【００２７】
この処理は図１のステップ１２に対応する。
【００２８】
〈反復的最小二乗推定（ILSE）処理〉
非特許文献［１］で使われている反復的最小二乗推定処理を考えると、グローバル動きパラメータa1、a2、a3、a4についての最適値は次の基準を使うことによって定められる。
【００２９】
【数６】
2007053767.tif 000006
ここで、Nは計算に関わってくるブロックの総数、すなわちフレームあたりのブロック数であり、それらのブロックの動きベクトルがそのフレームのグローバル動きを計算するために使われる。
【００３０】
式（４）および（５）はそれぞれグローバル動きパラメータのxおよびyの値を求めるために使われる。
【００３１】
式（４）および（５）をパラメータa1、a2、a3、a4で微分して微分を０とおく（それにより最小値を求める）ことにより、次の式が定められる。
【００３２】
【数７】
2007053767.tif 000007
局所的な動きがあることによる影響を消去するために上記の手続きは反復的に実行され、反復ごとに現在のグローバル動き場と合わないブロック動きベクトル（よって突出した動きベクトル）が消去される。本発明によれば、特別な突出値消去処理が使用され、それによりこれらの反復の間、対称的な構造が保持される。
【００３３】
〈最適化ILSE処理――標本選択〉
非特許文献［２］および［７］で提案されているアルゴリズムはGMEを行うためにフレームの全ピクセルブロック（すなわち全ブロックの動きベクトル）を使う。これは画像中の動いているオブジェクトの擾乱影響のため、計算量を増し、予言精度を低下させる。
【００３４】
本発明によるグローバル動き推定は、グローバル動きのあるたいていのビデオシーケンスにおいて、動いているオブジェクトによって隠蔽されるのは若干のブロックだけであり、これらのオブジェクトはたいていフレームの中央またはその付近に位置しておりフレームの境界付近にくることはめったにないという想定に基づいている。したがって、全ブロックの動きベクトルを使う代わりに、若干のブロック、特に当該フレームの境界付近のブロック（図２との関連で説明する）の動きベクトルだけでグローバル動きパラメータの計算を可能にするには十分である。
【００３５】
非特許文献［３］において開示されているアルゴリズムは、計算負荷を減らすために当該フレームの境界付近の格子ブロックを使うサンプル方法を提案しており、グローバル動きパラメータの精度を維持することを意図している。
【００３６】
図２は、ピクセルのブロックまたはマクロブロックの格子をもつフレームすなわち画像FRを示している。各ブロックまたはマクロブロックにはそれぞれローカルな動きベクトルが属している。しかし、当該フレームの最外周のピクセルブロック格子G1によって表現される画像領域においては、動いているオブジェクトがはいってきたり動いているオブジェクトが見えなくなったりすること、あるいはその他の境界乱れのため、測定される動きベクトルは通例現実の動きベクトルとは一致しない。
【００３７】
したがって、本発明によれば、フレームの境界に位置するブロックまたはマクロブロックの動きベクトルはグローバル動きパラメータの計算のために考慮に入れられず、たとえばピクセルブロック格子G2（網掛け円を含むブロックで表される、最外周から２番目の格子環）およびG3（黒丸を含むブロックで表される最外周から３番目の格子環）によって表現される画像領域のみがGMEのために使われる。すなわち、格子G2およびG3の各ブロックについて以前に（たとえばよく知られたブロック一致法［block  matching  technique］を使って）計算されているローカルな動きベクトルがそのフレームについてのグローバル動きパラメータを計算するために使用される。つまり、領域G2およびG3内に位置する参照ブロックについてのローカル動きベクトルのみが図１のステップ１３で使用されるのである。
【００３８】
代替としては、たとえばG2領域の動きベクトルは考慮されなかったり、および／または領域G3よりも内側に位置するブロックまたはマクロブロックの一つまたは複数の環の動きベクトルが考慮されたりする。
【００３９】
〈最適化ILSE処理――対称的サンプル〉
以下の記述では、計算における対称的な構造を維持するために対称ブロックグループという概念が使われる。領域G2またはG3にある任意のブロック（「サンプル」）がそれに対応する３つの対称位置のブロックとともに構成する４ブロックを対称ブロックグループとする。一つはx軸に関して対称的な位置にあり、さらなるものはy軸に関して対称的な位置にあり（x軸とy軸はフレーム中心で交わる）、第三のものはフレーム中心に関して対称的な位置にある。このことは図２における３つの例示的なブロックグループによって示される：
一つのブロックグループは「＋」の印が付けられ、もう一つは「×」印が付けられ、第三のものは「◇」印が付けられている。
【００４０】
上記のILSEの反復処理の最初のステップにおいて、測定された動きベクトルの対称的な構造のため、有利には、上記の式（６）から（９）はそれぞれ式（１０）から（１３）によって簡略化できる。
【００４１】
【数８】
2007053767.tif 000008
初期には突出した動きベクトルをもつブロックまたはマクロブロックもすべて考慮に入れられるので、候補グローバル推定パラメータ集合は動いているオブジェクトの局所的な動きによって影響されることになる。各反復後、計算された候補グローバル動きパラメータがそのような局所的な動きの影響を消去するために使われる。これは以下に説明する規則を使うことによって実行される。
【００４２】
通常は、最初の反復後に突出値を除去したのちの非対称なサンプル構造のため、単純化された式（１０）から（１３）はもはや有効ではない。しかし、本発明によれば、対称構造を維持し、単純化された式（１０）から（１３）が相変わらず使用できて計算負荷が削減されるようにするために、改良のための以下の規則が使われる。各反復ステップに続いて、有用なブロック動きベクトルは、この節で先に説明したような対称ブロックグループに再編成される。本発明の規則を適用することによって、突出値が除去されたのちにも、利用可能な点（すなわちブロック位置）の対称的な構造が次の反復についても維持できる。
【００４３】
〈対称構造を維持するために適用される規則〉
初期に、反復ループにはいる前には、候補グローバル動きパラメータは領域G2およびG3内に位置しているブロックの全動きベクトルから計算されることができる。
【００４４】
次の反復について利用可能な点の対称構造を維持するために、以下の規則が使用される。
【００４５】
図３から図５は図２で描かれた完全な格子に対応する部分格子を表している。
Ａ）図３で白丸によって描かれるように、４つの対称点のうちの一つが突出値である場合、すなわちそのブロック位置のブロックの動きベクトルが、そのブロック位置について計算された現在の候補グローバル動きに対して、動き量の突出値をもつか、あるいはxまたはyの少なくとも一つの動き成分量の突出値をもつ場合：
この突出値の位置は現在および次の反復ステップについては維持されるが、その現在の動きベクトルは最新のグローバル動きパラメータを使ってそのブロック位置について計算された動きベクトルによって置き換えられる。
Ｂ）図４で白丸によって描かれるように、４つの対称点のうちの二つが突出値である場合：
このブロックグループの４つのすべての動き量の値または動き成分量の値を除去した後に残る有用ブロックの動き量の値または動き成分量の値が所定の閾値Tvalidと比較され、この閾値が前記残りの有用ブロックの動き量の値または動き成分量の値より大きい場合には、この現在のブロックグループの４つのすべての動き量の値または動き成分量の値は突出値を表していると見なされ、対応するブロックの動きベクトルまたは動き成分の値は次の反復ループについては消去され、
そうでない場合には、前記二つの突出値の位置は次の反復ループについては維持されるが、その現在の動きベクトルは最新の候補グローバル動きパラメータの集合からそのブロックまたはマクロブロック位置について計算された動きベクトルによって置き換えられる。
Ｃ）図５で白丸によって描かれるように、４つの対称点のうちの三つが突出値である場合：
これら４つのすべての点は突出値を表していると見なされ、対応するブロックの動きベクトルは現在および次の反復のグローバル動き推定処理から消去される。
【００４６】
格子領域G2およびG3の現在残っている全ブロックグループのブロック／マクロブロック動きベクトルは、各グローバル動き推定処理反復ステップにおいて規則Ａ）からＣ）のもとで検査される。代替としては、ブロックグループは４つ以外の数、たとえば８個または１２個の対称的な諸ブロックを含んでいてもよい。そのような場合には、上記の規則はしかるべく適応される。
【００４７】
〈最適化ILSE処理――信頼性のない零動きベクトルの消去〉
動きベクトルの探索において、誤差計量として通例SSD（差分二乗和）およびSAD（差分絶対値和）が使われる（すなわち動きベクトル誤差計算のために）ため、結果として得られる動きベクトルは現実のカメラ動きを表さない。特に背景において大きななめらかな画像内容領域が存在する場合にはそうである。したがって、カメラ動きのあるビデオシーケンスにおいては一般に、信頼性のない零動きベクトル（0,0）は場面の現実の動きを表していない。さらに、式（１０）ないし（１３）からは、信頼性のない零動きベクトルは計算に擾乱を持ち込むことが見て取れる。したがって、さらに以下の規則を適用することによって、信頼性のない零動きベクトルの影響が低減あるいは消去さえされる：
Ｄ）ブロックの信頼性のない零動きベクトルは突出であると見なされる。
Ｅ）候補の零動きを有するブロックの量がフレームごとに数字Nzeroに蓄積される。Nzeroが所定の閾値Tstillより大きければ、その場面はカメラ動きのないスチール場面であると考えられ、そのフレームについてのさらなるグローバル動きベクトル推定の必要はない。すなわち、そのフレーム内の場面はグローバル動きはないと考えられる。
【００４８】
上述した最適化ILSE処理は図１のステップ１３から１５に対応する。
【００４９】
〈パフォーマンス解析――最初の反復における計算負荷の削減〉
図２が示すように、フレームの全ブロックではなくG2およびG3領域のブロックのみが使用されるため、演算数はずっと少なくなる。ピクセル単位のフレームサイズが［幅，高さ］＝［352,288］であり、マクロブロックが処理単位として選ばれ、したがってブロックサイズが［N,N］＝［16,16］であるとすると、フレームごとのブロック総数は（幅×高さ）／（N×N）＝396となる。本発明によればG2およびG3格子ブロックのみが使用されるので、フレームごとに使用されるブロック総数は(352/16−3)×2＋(288/16−3)×2＋(352/16−5)×2＋(288/16−5)×2＝128にまで削減される。したがって、反復処理の最初のステップにおいては、計算量は非特許文献［２］で記述されている処理に比較して約68%削減される。
【００５０】
〈パフォーマンス解析――後続の反復における計算負荷の削減〉
上述したように、最初の反復後は、非対称的なサンプル（すなわち動きベクトル位置）構造のため、通常は式（１０）から（１３）はもはや有効ではなくなる。しかし、規則Ａ）からＣ）の適用により、対称構造が維持され、これらの単純化された式が使用でき、精度を失うことなく計算負荷を削減できる。
【００５１】
下記の表においてnおよびバー付きのnは、対称構造を維持するためのこの改良がそれぞれない場合とある場合の反復についての、ブロック動きベクトルの量である。
【００５２】
たいていのフレームにおいて、nとバー付きのnの間には突出値選択の改良のため小さな差があるが、その差はおおざっぱな計算量比較にはさほど影響しないであろう。下記の表から、パラメータa1およびa3の計算の間、加算演算のざっと50%が、そしてパラメータa2およびa4の計算の間、加算演算のざっと75%および乗算演算の100%もが消去されることが結論できる。
【００５３】
表：計算負荷削減の比較
【００５４】
【表１】
2007053767.tif 000009
図６におけるグローバル動き推定器について、段６１で諸ブロックの動きベクトルが計算および／または保存または収集される。段６０は、グローバル動き推定の各反復ループにおいて、ブロックからなる一つまたは複数の環（たとえば領域G2およびG3）において各対称ブロックグループについて、動き量の値または動き成分量の値が候補グローバル動きパラメータの最新セットからの対応するブロック位置について計算された対応する動きベクトルと比べたときに突出している動きベクトルの量を検査する。段６５は、所与の規則セットに従って、実行されるべき現在およびさらなる反復ループについて、対応する対称ブロックグループの一つまたは複数のもともとの動きベクトル値が修正されて維持されるか、あるいは対応する対称ブロックグループの該動きベクトル値がもはや使われないかを決定する。段６３は、結果として得られる動きベクトル値から、候補グローバル動きパラメータの更新された集合を計算する。段６４は、前記集合の所望のまたは十分な精度が達成されるか、あるいは所与の反復ループ回数に達するかしているかどうかを検査し、真であれば、対応するグローバル動きパラメータの集合を出力し、真でなければ、次の反復ループが段６０における処理で続くようにする。
【００５５】
上述したグローバル動きパラメータを使ってエンコードされたデジタルビデオ信号が、たとえば光記憶媒体のような記憶媒体上に含まれ、または保存され、または記録されていることができる。再生の際、その記憶媒体からのグローバル動きパラメータは、エンコードされたビデオ信号を復号するための対応するビデオ信号デコーダにおいて使用される
【図面の簡単な説明】
【００５６】
【図１】グローバル動き推定のためのフローチャートである。
【図２】グローバル動き推定についての動きベクトルサンプルの選択を示す図である。
【図３】４つの対称点のうちの一つが突出である様子を示す図である。
【図４】４つの対称点のうちの二つが突出である様子を示す図である。
【図５】４つの対称点のうちの三つが突出である様子を示す図である。
【図６】本発明のグローバル動き推定器を示す図である。
【符号の説明】
【００５７】
１１  現在のフレームおよび参照フレームを入力
１２  グローバル動きモデル選択
１３  反復的パラメータ推定
１４  精度は十分？
１５  突出を除去
１６  グローバル動きパラメータを得る
【図１】
2007053767.tif 000012
【図２】
2007053767.tif 000013
【図３】
2007053767.tif 000014
【図４】
2007053767.tif 000015
【図５】
2007053767.tif 000016
【図６】
2007053767.tif 000017