(57)【特許請求の範囲】
【請求項１】
探索エリアのブロックと動き検出の対象となるブロックとの平均絶対差を用いた動き推定方法であって、
（ａ）探索ブロックの中心点及び周辺探索点に対して平均絶対差（ＭＡＤ）を計算する段階と、（ｂ）中心点でＭＡＤ値が最小である場合には中心点周辺に対して動き推定を行う段階と、（ｃ）中心点でＭＡＤ値が最小でない場合には周辺探索点間のＭＡＤ差異値による最小ＭＡＤをもつ探索点と周辺探索点との間の相関関係に基づき当該相関関係を用いて動き推定を行う段階とを含むことを特徴とする動き推定方法。
【請求項２】
前記（ａ）段階は、中心点でＭＡＤ値が最小であると判断することを含み、
前記（ｂ）段階は、（ｂ-１）前記（ａ）段階において、中心点でＭＡＤ値が最小であると判断されると、中心点から所定の予測距離だけ離れた新しい所定個数の探索点を追加する段階と、（ｂ-２）追加された探索点に対してＭＡＤ値を計算して最小のＭＡＤ値をもつ探索点の変位値を動きベクターとして決定する段階とを含むことを特徴とする請求項１に記載の動き推定方法。
【請求項３】
前記（ａ）段階は、中心点でＭＡＤ値が最小であると判断することを含み、
前記（ｃ）段階は、（ｃ-１）前記（ａ）段階において、中心点でＭＡＤ値が最小でないと判断されると、周辺探索点間の相関関係を用いて動きの方向を決定する段階を含むことを特徴とする請求項１に記載の動き推定方法。
【請求項４】
前記相関関係は、最小ＭＡＤ値をもつ探索点とその周辺探索点との間の相関には最小ＭＡＤ値をもつ探索点のＭＡＤ値と周辺探索点のＭＡＤ値との絶対差に基づくことを特徴とする請求項３に記載の動き推定方法。
【請求項５】
前記（ｃ）段階は、（ｃ-１）最小のＭＡＤ値が周辺探索点のうちどれか一つにある場合には周辺探索点間の相関関係に基づく第２段階のための新しい探索点を設定する段階と、（ｃ-２）前記（ｃ-１）段階で設定された探索点に対してＭＡＤ値を計算する段階と、（ｃ-３）前記（ｃ-２）段階で計算された結果で最小ＭＡＤ値をもつ探索点と周辺探索点との間の相関関係に基づき第３段階のための新しい探索中心点を設定する段階とを含むことを特徴とする請求項１に記載の動き推定方法。
【請求項６】
前記（ｃ-３）段階は、（ｃ-３-１）中心点と周辺探索点との間のＭＡＤ値の絶対差が小さい方向で中心点と周辺探索点との中間点を選択する段階と、（ｃ-３-２）前記中間点及び前記中心点に対してＭＡＤ値を計算してＭＡＤ値が小さい点を新しい探索点として設定する段階とを含むことを特徴とする請求項５に記載の動き推定方法。
【請求項７】
前記平均絶対差（ＭＡＤ）に替えて平均二乗誤差（ＭＳＤ）を用いることを特徴とする請求項１ないし６のいずれか一項に記載の動き推定方法。
【請求項８】
前記（ｃ-３）段階後に、（ｃ-４）新しく設定された探索中心点から所定の予測距離だけ離れた所定個数の探索点を追加する段階と、（ｃ-５）追加された探索点に対しＭＡＤ値を計算して最小のＭＡＤ値をもつ探索点の変位値を動きベクターとして決定する段階とをさらに含むことを特徴とする請求項５または６のいずれかに記載の動き推定方法。
【請求項９】
前記平均絶対差（ＭＡＤ）に替えて平均二乗誤差（ＭＳＤ）を用いることを特徴とする請求項８に記載の動き推定方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は動き推定方法に係り、より詳細には、計算量を減らした動き推定方法に関する。
【０００２】
【従来の技術】
動映像の高圧縮コーディングのために効率良く除去しなければならない４種の冗長度がある。第１番目は、信号成分中に存在する冗長度である。第２番目は、データの統計的な発生確率に起因する統計的な冗長度である。第３番目は、ピクチャー間の時間的な冗長度である。第４番目は、ピクチャー内の空間的な冗長度である。
【０００３】
信号成分中に存在する冗長度は色度に対する相対的な輝度の比率が２：１であるものを使って低減できる。統計的な冗長度はコーディング時にデータ発生の分布を用いて平均ビット数を減らす可変長コーディングによって低減できる。空間的な冗長度はＤＣＴ変換により低減できる。動映像で大いに発生する時間的な冗長度は動き推定（Ｍｏｔｉｏｎ  Ｅｓｔｉｍａｔｉｏｎ；ＭＥ）及び動き補償（Ｍｏｔｉｏｎ  Ｃｏｍｐｅｎｓａｔｉｏｎ；ＭＣ）により低減できる。
【０００４】
前記冗長度を減らすための従来の動き推定方法によれば、全域探索（ＦｕｌｌＳｅａｒｃｈ；ＦＳ）がブロック整合アルゴリズムとして用いられる。全域探索がブロック整合アルゴリズムとして用いられる場合、エンコーダの複雑性は動き推定のアルゴリズムに従属している。この方法は、動映像コーディングにおいて最も高い圧縮率を表わす。しかし、過度な計算量によりコーダの全体的な性能は低い。
【０００５】
前述のような問題点を解決するための他の動き推定方法によれば、よく知られている３−ステップ探索または４−ステップ探索に基づき計算量を減らしている。これらの方法は現在処理しようとするブロックと固定された探索領域内の全てのブロックとを比較することにより現在処理しようとするブロックと最も類似したブロックを探索する。３−ステップ探索方法は相対的に簡単でかつ正確に動き推定を行うことができる。
【０００６】
しかし、計算量を減らすことにより高速のブロック整合が行えるような動き推定方法への要求が依然として存在する。
【０００７】
【発明が解決しようとする課題】
本発明の目的は、計算量を減らすことにより高速のブロック整合が行えるような動き推定方法を提供するところにある。
【０００８】
【課題を解決するための手段】
前記目的を達成するために、本発明による動き推定方法は、（ａ）探索ブロックの中心点及び周辺探索点に対して平均絶対差（ＭＡＤ）を計算する段階と、（ｂ）中心点でＭＡＤ値が最小である場合には中心点周辺に対して動き推定を行う段階と、（ｃ）中心点でＭＡＤ値が最小でない場合には周辺探索点との相関関係を用いて動き推定を行う段階とを含むことを特徴とする。
【０００９】
また、前記（ｂ）段階は、（ｂ−１）前記（ａ）段階において、中心点でＭＡＤ値が最小であると判断されると、中心点から所定の予測距離だけ離れた新しい所定個数の探索点を追加する段階と、（ｂ−２）追加された探索点に対してＭＡＤ値を計算して最小のＭＡＤ値をもつ探索点の変位値を動きベクターとして決定する段階とを含むことが好ましい。
【００１０】
また、前記（ｃ）段階は、（ｃ−１）前記（ａ）段階において中心点でＭＡＤ値が最小でないと判断されると、周辺探索点間の相関関係を用いて動きの方向を決定する段階を含むことが好ましい。
【００１１】
また、前記相関関係は、最小ＭＡＤ値をもつ探索点とその周辺探索点との間の相関には最小ＭＡＤ値をもつ探索点のＭＡＤ値と周辺探索点のＭＡＤ値との絶対差に基づくことが可能である。
【００１２】
また、前記（ｃ）段階は、（ｃ−１）最小のＭＡＤ値が周辺探索点のうちどれか一つにある場合には周辺探索点間の相関関係に基づき第２段階のための新しい探索点を設定する段階と、（ｃ−２）前記（ｃ−１）段階で設定された探索点に対してＭＡＤ値を計算する段階と、（ｃ−３）前記（ｃ−２）段階で計算された結果で最小ＭＡＤ値をもつ探索点と周辺探索点との間の相関関係に基づき第３段階のための新しい探索中心点を設定する段階とを含むことが好ましい。
【００１３】
また、前記（ｃ−３）段階は、（ｃ−３−１）中心点と周辺探索点との間のＭＡＤ値の絶対差が小さい方向で中心点と周辺探索点との中間点を選択する段階と、（ｃ−３−２）前記中間点及び前記中心点に対してＭＡＤ値を計算してＭＡＤ値が小さい点を新しい探索点として設定する段階とを含むことが好ましい。
【００１４】
また、前記（ｃ−３）段階後に、（ｃ−４）新しく設定された探索中心点から所定の予測距離だけ離れた所定個数の探索点を追加する段階と、（ｃ−５）追加された探索点に対してＭＡＤ値を計算して最小のＭＡＤ値をもつ探索点の変位値を動きベクターとして決定する段階とをさらに含むことが好ましい。
【００１５】
また、代案的に、前記平均絶対差（ＭＡＤ）は、平均二乗誤差（Ｍｅａｎ  Ｓｑｕａｒｅ  Ｄｉｆｆｅｒｅｎｃｅ；ＭＳＤ）であることも可能である。
【００１６】
【発明の実施の形態】
以下、添付した図面に基づき、本発明の好ましい実施形態について詳細に説明する。
【００１７】
図１は、本発明の実施形態による動き推定方法の主な段階を示したフローチャートである。本実施形態では３段階の動き推定に基づく場合を例として説明する。
【００１８】
本発明による動き推定方法は、第一に、例えば、秒当たり２０ないし３０フレームの動映像内で統計的に動きベクターの約７０％は動きベクター座標（０，０）に集中しているということを用いる。図２（ａ）、図２（ｂ）、図２（ｃ）及び図２（ｄ）には”カーフォン（Ｃａｒｐｈｏｎｅ）”、”フォアマン（Ｆｏｒｅｍａｎ）”、”マムアンドドータ（Ｍｏｍ  ＆  Ｄａｕｇｈｔｅｒ）”、及び”スジー（Ｓｕｓｉｅ）”の４種のＱＣＩＦ（Ｑｕａｄｒａｔｕｒｅ  Ｃｏｍｍｏｎ  Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｆｏｒｍａｔ）映像シーケンスでの動きベクター分布が各々示されている。図２を参照すると、動きベクターの分布が（０，０）の周囲に集中しているということが分かる。
【００１９】
第二に、本発明による動き推定方法では、探索点間の相関関係を考慮する。詳細に、ほとんどの動きベクターは以前に決定された平均二乗誤差または平均絶対誤差（Ｍｅａｎ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ；ＭＡＤ）が最小となる方向に移動しようとする傾向があり、局部的な最小で探索が行われ易いという点を考慮する。このため、任意の探索点が局部的な最小として決定されると、その点を動きベクターを求める点として決定し、そうでない場合にはＭＡＤ値に基づく周辺探索点間の相関関係を用いることにより探索の計算量を減らす。本実施形態において、任意の一方向で周辺探索点とのＭＡＤ値の差が小さいということはその方向への動きが存在する可能性が高いということを表わす。このように本発明の実施形態では、周辺探索点とのＭＡＤ値の違いを、一つの探索点と周辺探索点との間の相関関係として用いる。
【００２０】
図３は、第１段階の処理過程を説明するための図である。図３に示されたように、探索中心点から±４予測距離をもつ４つの探索位置（ａ，ｂ，ｃ，ｄ）が新しい探索点として設定される。次に、第１段階において、設定された探索点に対してＭＡＤ値を計算する（ステップ１０２）。次に、中心点（ｏ）でＭＡＤ値が最小であるかを判断する（ステップ１０４）。ステップ１０４は、動きベクターの方向が中心にあるかどうかを決定するための段階として理解できる。もし、中心（ｏ）でＭＡＤが最小であれば±１の予測距離だけ離れた新しい８個の探索点を追加し（ステップ１１０）、追加された探索点に対してＭＡＤ値を計算して最小のＭＡＤ値をもつ探索点の変位値を動きベクターとして決定する（ステップ１１２）。
【００２１】
一方、ステップ１０４において、中心点（ｏ）でＭＡＤ値が最小でないと判断された場合、最小のＭＡＤ値が探索点（ａ，ｂ，ｃ，ｄ）にある場合には周辺探索点間の相関関係を用いて動きの方向を決定する。すなわち、最小のＭＡＤ値が探索点（ａ，ｂ，ｃ，ｄ）にある場合には周辺探索点間の相関関係に基づき第２段階のための新しい探索点を設定する（ステップ１２０）。
【００２２】
図４（ａ）は、最小探索点と周辺探索点との間の相関関係を調べるためにカーフォン及びマムアンドドータの各テスト映像の１００フレームに存在する全てのブロックに対して８個の探索点を設定した例を示したものであり、図４Ｂ及び図４（ｃ）は、該当探索点上での平均ＭＡＤ値を計算した結果を示したものである。図４Ｂを参照すると、探索点（ｄ）が最小ＭＡＤ点であり、│ＭＡＤ（ｄ）−ＭＡＤ（ｃ）│は２７であり、│ＭＡＤ（ｄ）−ＭＡＤ（ｂ）│は３１であって、│ＭＡＤ（ｄ）−ＭＡＤ（ｃ）│＜│ＭＡＤ（ｄ）−ＭＡＤ（ｂ）│の関係が成立つ。これは、（ｄ）点と（ｃ）点との間にある（ｄｃ）点のＭＡＤ値が（ｂ）と（ｄ）点との間にある（ｂｄ）点のＭＡＤ値よりは小さいということが分かる。このことから、差値が小さい方向により小さいＭＡＤ値が分布されることが分かる。
【００２３】
また、図４（ｃ）を参照すると、探索点（ａ）が中心点であり、│ＭＡＤ（ａ）−ＭＡＤ（ｂ）│は１７８であり、│ＭＡＤ（ａ）−ＭＡＤ（ｃ）│は２３であって、│ＭＡＤ（ａ）−ＭＡＤ（ｂ）│＞│ＭＡＤ（ａ）−ＭＡＤ（ｃ）│の関係が成立ち、（ｃａ）点のＭＡＤ値が（ａｂ）点のＭＡＤ値よりも小さいということが分かる。探索点間の相関は点ｂ、ｃ、またはｄが中心点である場合にも成立つ。
【００２４】
すなわち、本発明による動き推定方法は、第１段階でマクロブロックの中心（ｏ）に該当する探索点以外の探索点（ａ，ｂ，ｃ，ｄ）が最小ＭＡＤ値をもつ探索点として決定されると、動きベクター方向成分の推定に周辺探索点間の相関を用いる。本実施形態において、最小ＭＡＤ値をもつ探索点とその周辺探索点との間の相関には最小ＭＡＤ値をもつ探索点のＭＡＤ値と周辺探索点のＭＡＤ値との絶対差を用いる。すなわち、下記式による場合に対して次の段階での探索点及び動きを推定する。
（数１）
│ＭＡＤ（ａ）−ＭＡＤ（ｂ）│＝│ＭＡＤ（ａ）−ＭＡＤ（ｃ）│
（数２）
│ＭＡＤ（ａ）−ＭＡＤ（ｂ）│＞│ＭＡＤ（ａ）−ＭＡＤ（ｃ）│
（数３）
│ＭＡＤ（ａ）−ＭＡＤ（ｂ）│＜│ＭＡＤ（ａ）−ＭＡＤ（ｃ）│
【００２５】
図１には示されていないが、前式１の条件を満足する場合には探索点（ａ）上で±１の推定距離をもつ８個の探索点を設定し、最小ＭＡＤをもつ探索点の変位値を動きベクターとして決定する。
【００２６】
また、図４（ａ）に示されたように、前式２の条件に該当する場合には探索点（ａ）と探索点（ｃ）との間の中間点（ｃａ）が新しく設定され、各々の他の探索点に対して比較計算結果により第２段階が行われる。
（数４）
ＭＡＤ（ａ）＝ＭＡＤ（ｃａ）
（数５）
ＭＡＤ（ａ）＞ＭＡＤ（ｃａ）
（数６）
ＭＡＤ（ａ）＜ＭＡＤ（ｃａ）
【００２７】
前式４の条件を満足する場合には、探索点（ａ）と探索点（ａｃ）との中間点上で±１の推定距離をもつ８個の探索点を新しく設定し、最小ＭＡＤをもつ探索点の変位値を動きベクターとして決定する。また、前式５の条件を満足する場合には、点（ｃａ）を第２段階のための新しい探索中心点として設定する。次に、新しい探索中心点（ｃａ）から±２の推定距離をもつ４つの探索点を設定する。前式６の条件を満足する場合には、点（ａ）を第２段階のための新しい探索中心点として設定する。次に、新しい探索中心点（ａ）から±２の推定距離をもつ４つの探索点を設定する。すなわち、新しく設定された探索中心点から±２の予測距離だけ離れた４つの探索点を設定する（ステップ１２２）。
【００２８】
次に、ステップ１２２で設定された探索点に対してＭＡＤ値を計算する（ステップ１２４）。次に、ステップ１２４で計算された結果で最小ＭＡＤ値をもつ探索点と周辺探索点との間の相関関係に基づき第３段階のための新しい探索中心点を設定する（ステップ１２６）。次に、第３段階では設定された探索中心点から±１の予測距離だけ離れた８つの探索点を追加する（ステップ１２８）。次に、追加された探索点に対してＭＡＤ値を計算して最小のＭＡＤ値をもつ探索点の変位値を動きベクターとして決定する（ステップ１３０）。
【００２９】
図５は、動きベクター（７，１）を推定する過程の例を説明するための図である。図５を参照すると、第１段階において、最小ＭＡＤ値は探索点（ｏ）でない探索点（ｄ）の場合に該当する。本発明によれば、このような場合には、周辺探索点間の相関関係を用いる。相関関係を分析すると、│ＭＡＤ（ｄ）−ＭＡＤ（ｃ）│＞│ＭＡＤ（ｄ）−ＭＡＤ（ｂ）│の条件を満足するので、探索点（ｂ）と探索点（ｄ）との間の中間点（ｅ）のＭＡＤを計算する。探索点（ｂ）に対するＭＡＤは探索点（ｅ）に対するＭＡＤよりも大きいため、探索点（ｅ）を第２段階のための新しい探索点として設定し、探索中心（ｅ）から±２の推定距離をもつ４つの探索点（ｆ）、（ｇ）、（ｈ）及び（ｉ）を設定し、第２段階を行う。探索点（ｉ）が最小ＭＡＤをもち、│ＭＡＤ（ｉ）−ＭＡＤ（ｈ）│＞│ＭＡＤ（ｉ）−ＭＡＤ（ｇ）│の条件を満足する場合には、探索点（ｉ）と探索点（ｇ）との中間点（ｊ）に対してＭＡＤを計算する。ＭＡＤ（ｇ）はＭＡＤ（ｊ）よりも大きいため、第３段階では探索点（ｊ）を中心点とする±１の推定距離に位置する８個の探索点を追加で設定する。最後の段階では最適点（７，１）が与えられ、この点に対する距離を用いて動きベクターが決定される。
【００３０】
もし、第１段階で終了された場合には、最小探索点の数は最も小さい５＋８＝１３となる。全ての過程を経て動きベクターが決定された場合には最小探索点の数は最も大きい５＋１＋４＋１＋８＝１９となる。
【００３１】
従来の動き推定方法及び本発明の動き推定方法の性能を評価するために模擬実験を行った。比較の対象は最も正確に動きを推定する全域探索（ＦＳＭ）と比較的に速く動きを推定する３段階探索（３ＳＳ）及び最近良好な性能を示すと知られている４段階探索（４ＳＳ）である。計算量を比較するための項目はマクロブロック当たり平均探索点（Ａｖｅｒａｇｅ  Ｓｅａｒｃｈｉｎｇ  Ｐｏｉｎｔ；ＡＳＰ）を選択した。表１には、ＡＳＰの比較結果を示した。
【表１】
0003625771.tif 000002
【００３２】
表１を参照すると、本発明による動き推定方法は従来の技術の動き推定方法（ＦＳＭ、３ＳＳ、４ＳＳ）に比べてマクロブロック当たり平均探索点（ＡＳＰ）の数が低いということが分かる。すなわち、本発明による動き推定方法は、計算量を顕著に減らすことにより映像圧縮の速度を向上させる。
【００３３】
また、動き推定の精密度を比較するための項目はデシベル（ｄＢ）で表わされるＰＳＮＲを使用した。表２には、各テスト映像の１００フレームに対して平均ＰＳＮＲを測定した結果を示した。
【表２】
0003625771.tif 000003
【００３４】
表２を参照すると、本発明による動き推定方法は従来の技術の動き推定方法（ＦＳＭ、３ＳＳ、４ＳＳ）に比べて映像圧縮時に画質をあまり劣化させないということが分かる。
【００３５】
また、前述のように本発明による動き推定方法は、個人向けまたはサーバー級のコンピュータ内で実行されるプログラムにて作成可能である。前記プログラムを構成するプログラムコード及びコードセグメントは当該分野のコンピュータプログラマーによって容易に推論できる。また、前記プログラムはコンピュータにて読み取り可能な記録媒体に貯蔵できる。前記記録媒体は磁気記録媒体、光記録媒体、及び電波媒体を含む。
【００３６】
【発明の効果】
以上述べたように、本発明によれば、従来の技術の動き推定方法に比べて映像圧縮時に画質をあまり劣化させずに、計算量を顕著に減らすことによって映像圧縮の速度を向上させる。
【図面の簡単な説明】
【図１】本発明の実施形態による動き推定方法の主な段階を示したフローチャートである。
【図２】（ａ）”カーフォン（Ｃａｒｐｈｏｎｅ）”のＱＣＩＦ（Ｑｕａｄｒａｔｕｒｅ  Ｃｏｍｍｏｎ  Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｆｏｒｍａｔ）映像シーケンスでの動きベクター分布を各々示した図である。（ｂ）”フォアマン（Ｆｏｒｅｍａｎ）”のＱＣＩＦ映像シーケンスでの動きベクター分布を各々示した図である。（ｃ）”マムアンドドータ（Ｍｏｍ  ＆  Ｄａｕｇｈｔｅｒ）”のＱＣＩＦ映像シーケンスでの動きベクター分布を各々示した図である。（ｃ）”スジー（Ｓｕｓｉｅ）”のＱＣＩＦ映像シーケンスでの動きベクター分布を各々示した図である。
【図３】第１段階の処理過程を説明するための図である。
【図４】（ａ）最小探索点と周辺探索点との間の相関関係を調べるためにカーフォン及びマムアンドドータの各テスト映像の１００フレームに存在する全てのブロックに対して８個の探索点を設定した例を示した図である。（ｂ）該当探索点上での平均ＭＡＤ値を計算した結果を示した図である。（ｃ）該当探索点上での平均ＭＡＤ値を計算した結果を示した図である。
【図５】動きベクター（７，１）を推定する過程の例を説明するための図である。
【図１】
0003625771.tif 000004
【図２】
0003625771.tif 000005
0003625771.tif 000006
【図３】
0003625771.tif 000007
【図４】
0003625771.tif 000008
0003625771.tif 000009
【図５】
0003625771.tif 000010