(57)【特許請求の範囲】
【請求項１】
動映像を圧縮するためにブロック整合を使用する動き推定方法において、
（ａ）  入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備し、階層１の解像度を低めて階層２を具備する段階と、
（ｂ）  階層２の探索領域に対して平均絶対誤差を計算する段階と、
（ｃ）  前記（ｂ）段階で計算された平均絶対誤差が最小になる二つ以上の位置を階層１における初期探索中心点として選択する段階と、
（ｄ）  現在ブロックの周辺ブロックの動きベクトル相関性を用いて階層１における１つ以上の初期探索中心点をさらに選択する段階と、
（ｅ）  前記（ｃ）段階及び（ｄ）段階で選択された前記階層１での初期探索中心点を中心とする探索領域に対して平均絶対誤差を計算する段階と、
（ｆ）  前記（ｅ）段階で計算された平均絶対誤差が最小になる位置を階層０における探索中心点として選択する段階と、
（ｇ）  前記（ｆ）段階で選択された初期探索中心点を中心とする階層０での探索領域に対して平均絶対誤差を計算する段階と、
（ｈ）  前記（ｇ）段階で計算された平均絶対誤差が最小になる位置情報と原点との距離情報より最終動きベクトルを決定する段階とを含んで成り、
前記（ｄ）段階は周辺ブロック間の動きベクトルの差の絶対値が所定の臨界値以下のブロックの動きベクトル平均値を計算して、前記動きベクトル平均値が最小になる位置を階層１における初期探索中心点として選択することを特徴とする動き推定方法。
【請求項２】
動映像を圧縮するためにブロック整合を使用する動き推定方法において、
（ａ）  入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備し、階層１の解像度を低めて階層２を具備する段階と、
（ｂ）  階層２の探索領域に対して平均絶対誤差を計算する段階と、
（ｃ）  前記（ｂ）段階で計算された平均絶対誤差値が最小になる二つの位置を階層１における初期探索中心点として選択する段階と、
（ｄ）  現在ブロックの周辺ブロックの相関性を用いて一つの初期探索中心点をさらに選択する段階と、
（ｅ）  階層１で３つの初期探索中心点を探索中心とする探索領域に対して平均絶対誤差を計算する段階と、
（ｆ）  前記（ｅ）段階で計算された平均絶対誤差値が最小になる位置を階層における初期探索中心点として選択する段階と、
（ｇ）  階層０の探索領域に対して平均絶対誤差を計算する段階と、
（ｈ）  前記（ｇ）段階で計算された平均絶対誤差値が最小になる位置データと原点との距離情報より最終動きベクトルを決定する段階とを含んで成り、
前記（ｄ）段階は周辺ブロック間の動きベクトルの差の絶対値が所定の臨界値以下のブロックの動きベクトル平均値を計算して、前記動きベクトル平均値が最小になる位置を階層１における初期探索中心点として選択することを特徴とする動き推定方法。
【請求項３】
前記（ａ）段階は入力された階層０の解像度を水平及び垂直方向に各々１／２と１／４に低めて各々階層１と階層２を具備することを特徴とする請求項２に記載の動き推定方法。
【請求項４】
前記（ｅ）段階と前記（ｇ）段階における探索領域は５×５画素よりなることを特徴とする請求項２に記載の動き推定方法。
【請求項５】
動映像を圧縮するためにブロック整合を使用する動き推定装置において、
入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備し、階層１の解像度を低めて階層２を具備する解像度調整手段と、
階層２の探索領域に対する第１平均絶対誤差と、階層１で動きベクトル候補に対応する位置を探索中心点とする探索領域に対する第２平均絶対誤差、及び階層０で前記第２平均絶対誤差値が最小になる位置を階層０の探索中心点とした探索領域に対して第３平均絶対誤差を計算する平均絶対誤差計算手段と、
前記第１平均絶対誤差値が最小になる少なくとも二つ以上の位置を階層１における初期探索中心点として選択し、一つ以上の初期探索中心点をさらに選択する初期探索点選択手段と、
前記第３平均絶対誤差値が最小になる位置と原点との距離情報を用いて最終動きベクトルを決定する最終動きベクトル決定手段とを含んでなり、
前記初期探索点の選択手段は、周辺ブロック間の動きベクトルの差の絶対値が所定の臨界値以下のブロックの動きベクトル平均値を計算して、その動きベクトル平均値が最小になる位置を階層１における初期探索中心点として選択することを特徴とする動き推定装置。
【請求項６】
前記解像度調整手段は入力された階層０の解像度を１／２と１／４に低めて各々階層１と階層２を具備することを特徴とする請求項５に記載の動き推定装置。
【請求項７】
前記探索領域は５×５画素よりなることを特徴とする請求項２に記載の動き推定装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はリアルタイム動映像符号化のための超高速動き推定方法に係り、より詳細にはＭＰＥＧ−２のような動映像符号化のための動き推定において解像度を低めて複数個の動きベクトル候補を決定し、周辺ブロックの動きベクトル相関性を用いて動きベクトル候補を決定した後、複数個の動きベクトル候補を中心として探索領域を選定して動きベクトルを計算することによって、動きベクトルの計算時間を縮める動き推定方法に関する。
【０００２】
【従来の技術】
動映像の符号化としては、高いデータ圧縮率を得るために時間的に重複性を除去する動き補償符号化が広く使われているとともに、ＭＰＥＧ−１、２、４及びＨ−２６３のような国際映像符号化標準で重要な位置を占めている。
【０００３】
動き補償符号化は動き推定を通じて以前フレームの情報より入力映像と最も類似の映像を予測し、予測した映像と入力映像の差映像を変換符号化することを称する。
【０００４】
このような動映像の符号化のための一般の装置を図１に示した。図１を参照すれば、一般の動映像符号化装置はフレームメモリ１０２、動き推定部１０４、１０６、動き補償部１０８、減算部１１０、離散コサイン変換部１１２、量子化部１１４、逆離散コサイン変換部１１８、加算部１２０、フレーム遅延部１２２、順方向分解及びコーディング率制御器１２４、可変長符号化部１２６及びバッファ１２８を具備する。
【０００５】
フレーム単位で入力される映像はフレームメモリ１０２に貯蔵され、第１動き推定部１０４は整数画素単位の映像に対する動きベクトルを計算する。第２動き推定部１０６は、第１動き推定部１０６から入力された動きベクトルとフレームメモリ１０２から入力された映像信号とフレーム遅延部１２２から入力された以前フレームの情報を用いて、現在入力された映像に対する半画素単位の動きベクトルを計算する。
【０００６】
動き補償部１０８は、第２動き推定部１０６から入力された動きベクトルとフレーム遅延部１２２から入力された以前フレームの情報に基づいて動き補償を遂行して現在フレームに対する予測映像を出力する。このように動き補償された予測映像は、減算部１１０によってフレームメモリ１０２から入力された現在映像と減算されて現在映像との差映像を得ることによって、動映像の時間的な重複性がなくなる。このような動き推定及び補償過程は１６×１６ブロック単位で遂行され、一般にこのブロックはマクロブロックといわれる。次に、動き推定及び補償後得られた差映像は、離散コサイン変換部１１２と量子化部１１４によって離散コサイン変換及び量子化されることによって差映像の残っている空間的な重複性がなくなる。最後に、動きベクトルと量子化した差映像は、可変長符号化部１２６によって符号化した後バッファ１２８を通じてビット列形態に伝送される。
【０００７】
一方、順方向分解及びコーディング率制御部１２４は可変長符号化部１２６の符号化率を制御し、量子化した映像信号は再び逆量子化部１１６と逆離散コサイン変換部１１８により補間及び復元された後、加算部１２０によって動き補償された映像信号に加わってフレーム遅延部１２２に貯蔵される。フレーム遅延部１２２に貯蔵される映像フレームは１フレーム以前の映像フレームに当る。フレーム遅延部１２２に貯蔵された以前映像フレーム情報は第２動き推定部１０６と動き補償部１０８に入力される。
【０００８】
動映像を処理するための動き推定及び補償方法としては、一般にフレーム単位の動き推定及び補償方法とフィールド単位の動き推定及び補償方法があるが、これは当業者に知られているので本明細書では説明を省略する。
【０００９】
一方、従来に使われている全域探索法による動き推定方法は、現在のフレームを一定の大きさのブロック単位で分割した後、各ブロックを与えられた整合基準に従って基準フレームの探索領域内にある全てのブロックと比較して最適の整合ブロックの位置を探すことによって、各ブロックの二次元動きベクトルを推定する方法である。このような従来のブロック整合法で最適の整合ブロックを探すための整合基準として、比較的計算が簡単な平均絶対誤差（ＭＡＤ：  Ｍｅａｎ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）を用いる。このような平均絶対誤差値は、
【００１０】
【数１】
0003615963.tif 000002
【００１１】
を用いて計算される。前記式１で  ｆｔ（ｋ，ｌ）  は現在フレームの  （ｋ，ｌ）  位置にある画素の輝度値であり、ｆｔ−１（ｋ＋ｉ，ｌ＋ｊ）  は以前フレームの  （ｋ，ｌ）  位置から  （ｉ，ｊ）  位置だけ移動した位置にある画素の輝度値である。
【００１２】
一方、このようなブロック整合法で符号化する時は実際映像の動きを考慮して最大動き推定範囲を決定する。このように決定された動き推定範囲内の全てのブロックと現在ブロックを比較して、動きベクトルを推定する全域探索方式は予測利得の側面では最も高い性能を有するが、過度に多くの計算量が要求される短所がある。例えば、Ｍ×Ｎの大きさのブロックに対してフレーム当り最大移動変位を±ｐ（パルス／フレーム）とする場合、基準フレームで探索領域の大きさは（Ｍ＋２ｐ）×（Ｎ＋２ｐ）になる。即ち、整合基準に従って比較すべき候補ブロックの数が（２ｐ＋１）２になるため、ｐが大きいほど動映像符号化器のリアルタイム具現が難しくなる問題点がある。
【００１３】
このような問題点を解決するための他の従来技術が技術資料“平均ピラミッドを用いた高速階層的動きベクトル推定アルゴリズム。ＮＡＭ、Ｋ．Ｍ．、Ｋｉｍ、Ｊ．Ｓ．、Ｐａｒｋ、Ｒ．Ｈ．、Ｓｈｉｍ、Ｙ．Ｓ．、ＩＥＥＥ  Ｔｒａｎｓ．ｏｆ  Ｃｉｒｃ．＆  Ｓｙｓｔ．  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈ、１９９５、５、（４）、ｐｐ．３４４〜３５１”と、“映像符号化のための３段階検索ブロック整合アルゴリズムの精密度改善及び費用節減、ＩＥＥＥ  Ｔｒａｎｓ．Ｃｉｒｃ．＆  Ｓｙｓｔ．  ｆｏｒ．Ｖｉｄｅｏ  Ｔｅｃｈ、１９９４、４、（１）、ｐｐ．８８〜９０）”に示されている。前記資料によれば、全域探索技法を代えるべき複数の候補を用いた高速階層的探索技法が提案された。
【００１４】
しかし、前記方法のような複数候補を使用する戦略は、階層的な探索のせいで発生する局所最小値の問題を縮めうるが、全域探索法に次ぐ性能を達成するために相変らず多くの計算量を要する問題点がある。また、前記方法は三段探索技法を基礎とするため広い探索領域における動き推定には望ましくない短所がある。
【００１５】
【発明が解決しようとする課題】
本発明が達成しようとする技術的課題は、動きベクトルを計算するための計算量を減らして高速で動きベクトルが推定できる動き推定方法を提供することである。
【００１６】
本発明が達成しようとする他の技術的課題は、前記動きベクトル推定方法によって具現される動き推定装置を提供することである。
【００１７】
【課題を解決するための手段】
前記課題を達成するために本発明の一態様に従う動き推定方法は、（ａ）入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備し、階層１の解像度を低めて階層２を具備する段階と、（ｂ）階層２の探索領域に対して平均絶対誤差を計算する段階と、（ｃ）前記（ｂ）段階で計算された平均絶対誤差値が最小になる少なくとも二つ以上の位置を階層１における初期探索点として選択する段階と、（ｄ）現在ブロックの周辺ブロックの相関性を用いて一つ以上の階層１における初期探索点をさらに選択する段階と、（ｅ）階層１で初期探索中心点を中心とする探索領域に対して平均絶対誤差を計算する段階と、（ｆ）前記（ｅ）段階で計算された平均絶対誤差値が最小になる位置を階層０における探索中心点として選択する段階と、（ｇ）階層０で、前記（ｆ）段階で選択された初期探索中心点を中心とする探索領域に対して平均絶対誤差を計算する段階と、（ｈ）前記（ｇ）段階で計算された平均絶対誤差値が最小になる位置情報と原点との距離情報より最終動きベクトルを決定する段階とを含むことを特徴とする。
【００１８】
また、前記課題を達成するために本発明の他態様に従う動き推定方法は、（ａ）入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備し、階層１の解像度を低めて階層２を具備する段階と、（ｂ）階層２の探索領域に対して平均絶対誤差を計算する段階と、（ｃ）前記（ｂ）段階で計算された平均絶対誤差値が最小になる二つの位置を階層１における初期探索中心点として選択する段階と、（ｄ）現在ブロックの周辺ブロックの相関性を用いて一つの初期探索中心点をさらに選択する段階と、（ｅ）階層１で３つの初期探索中心点を探索中心とする探索領域に対して平均絶対誤差を計算する段階と、（ｆ）前記（ｅ）段階で計算された平均絶対誤差値が最小になる位置を階層における初期探索中心点として選択する段階と、（ｇ）階層０の探索領域に対して平均絶対誤差を計算する段階と、（ｈ）前記（ｇ）段階で計算された平均絶対誤差値が最小になる位置データと原点との距離情報より最終動きベクトルを決定する段階とを含むことを特徴とする。
【００１９】
また、前記（ａ）段階は入力された階層０の解像度を水平及び垂直方向に各々１／２と１／４に低めて各々階層１と階層２を具備することが望ましい。
【００２０】
また、前記（ｄ）段階は周辺ブロック間の動きベクトルの差の絶対値が所定の臨界値以下のブロックの動きベクトル平均値を計算して、前記動きベクトル平均値が最小になる位置を階層１における初期探索中心点として選択することが望ましい。
【００２１】
また、前記（ｅ）段階と前記（ｇ）段階における探索領域は５×５画素よりなることが望ましい。
【００２２】
前記他の課題を達成するために本発明に係る動き推定方法は、入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備し、階層１の解像度を低めて階層２を具備する解像度調整手段と、階層２の探索領域に対する第１平均絶対誤差ＭＡＤと、階層１で動きベクトル候補に対応する位置を探索中心点とする探索領域に対する第２平均絶対誤差、及び階層０で前記第２平均絶対誤差値が最小になる位置を階層０の探索中心点とした探索領域に対して第３平均絶対誤差を計算する平均絶対誤差計算手段と、前記第１平均絶対誤差値が最小になる少なくとも二つ以上の位置を階層１における初期探索中心点として選択し、現在ブロックの周辺ブロックの相関性を用いて一つ以上の初期探索中心点をさらに選択する初期探索点選択手段と、前記第３平均絶対誤差値が最小になる位置と原点との距離情報を用いて最終動きベクトルを決定する最終動きベクトル決定手段とを含むことを特徴とする。
【００２３】
【発明の実施の形態】
以下、添付した図面を参照して本発明に係るリアルタイム動映像符号化のための超高速動き推定方法及びその装置の望ましい実施形態を詳細に説明する。
図２には本発明の実施形態に係る動き推定方法の主要段階をフローチャートで示し、図３には前記動き推定方法によって階層別探索を遂行する時各階層別探索位置を説明するための図面を示した。図３は以下で頻繁に参照される。図２を参照すれば、本発明に係る動き推定方法は、まず、入力された映像フレーム（階層０）の解像度を水平、垂直方向に１／２と１／４に低めて各々階層１と階層２を具備する（段階２０２）。このように解像度を低める理由は、探索領域を縮めて動きベクトルを計算するための計算量を減らすためのことである。例えば、全体探索領域の大きさがＲ×Ｒであれば本実施形態で探索領域の範囲は（Ｒ／４）×（Ｒ／４）になる。
【００２４】
次に、階層２の探索領域（ＳＲ（２）：図３）に対して平均絶対誤差（ＭＡＤ）を計算する（段階２０４）。階層２の探索領域（ＳＲ（２）：図３）はＮＳを所定の正の整数とする時、横と縦で−ＮＳから＋ＮＳ−１までの領域に決定されるので各々０を含んで横、縦各々２ＮＳの領域になり、探索位置の数は（２ＮＳ×２ＮＳ）／１６、即ち、（ＮＳ×ＮＳ）／４になる。
【００２５】
次は、前記段階２０４で計算された平均絶対誤差値が最小になる、即ち、予測エラーが最も小さな二つの位置を次の段階（階層１）の初期探索中心点として選択する（段階２０６）。
【００２６】
二つの初期探索中心点と共に一つの初期探索中心点をさらに選択するが、その過程を図４（Ａ）乃至図４（Ｆ）を参照して説明する。デジタル動映像の圧縮はマクロブロックと同じブロック単位で遂行される。ブロックの処理順序としては行別に順次に処理されることを例として挙げられる。
【００２７】
本発明で用いられる周辺ブロックは、図４（Ａ）乃至図４（Ｆ）に示したように相互関連される三つのブロックが使われる。また、動きベクトル間の相関性を考慮して示したように５つのグループに分けられる。例えば、周辺ブロックの動きベクトルＭＶｓが図４（Ａ）と同一だとする時、周辺ブロック間の動きベクトルの差の絶対値を、
【００２８】
【数２】
0003615963.tif 000003
【００２９】
のように定義し、Ｄを二つの動きベクトル間の類似性を検査するための臨界値と定義する。次は、動きベクトル間の相関性を考慮して５つのグループに区分する。即ち、図４（Ｂ）を参照すれば、グループ１は  ξ１≦Ｄ、ξ２≦Ｄ、ξ３≦Ｄ  を満足する場合であり、図４（Ｃ）を参照すれば、グループ２は  ξ１≦Ｄ、ξ２＞Ｄ、ξ３＞Ｄ  を満足する場合である。また、図４（Ｄ）と図４（Ｅ）を参照すれば、グループ３はξ１＞Ｄ、ξ２≦Ｄ、ξ３＞Ｄ  を、グループ４は  ξ１＞Ｄ、ξ２＞Ｄ、ξ３≦Ｄ  を満足する場合である。前述した以外の場合はグループ５に当る。動きベクトルは例えば各グループ別にグループ１の場合には  ＭＶ＝（ＭＶ１＋ＭＶ２＋ＭＶ３）／３、グループ２の場合には  ＭＶ＝（ＭＶ１＋ＭＶ２）／２、グループ３の場合には  ＭＶ＝（ＭＶ２＋ＭＶ３）／２、グループ４の場合には  ＭＶ＝（ＭＶ１＋ＭＶ３）／２  に計算する。計算された動きベクトルの平均値が最小になる位置を初期探索中心点として選択する。
【００３０】
このように、動きベクトル値の差の絶対値に従って５つのグループに区分し、探索初期点を各グループ別に平均動きベクトルを計算して決定する方法は単に説明のためのことであって、周辺ブロックの動きベクトル情報を読出して、周辺ブロックの動きベクトル相関性を用いて一つの初期探索中心点を選定する他の方法に変形して使用でき、請求項によって定義される本発明の範囲を限定しない。
【００３１】
次は、階層１で、三つの初期探索中心点を中心とした探索領域ＳＲ１（１）、ＳＲ２（１）、ＳＲ３（１）の各々に対して平均絶対誤差を計算する（段階２１０）。本実施形態では第１階層における探索領域を探索中心点を含んで±２画素、即ち、総５×５画素よりなるように設定した。
【００３２】
次は、段階２１０で計算された平均絶対誤差値が最小になる位置を階層０における初期探索中心点として選択（段階２１２）し、選択された初期探索中心点に対して±２画素領域を階層０の探索領域として平均絶対誤差を計算する（段階２１４）。
【００３３】
計算された平均絶対誤差値が最小になる位置と原点との距離情報を使用して最終動きベクトルを決定する（段階２１６）。決定された最終動きベクトルは二次元映像の場合、例えば、ｘ軸及びｙ軸座標値になる。
【００３４】
前記のような本発明に係る動き推定方法の性能を評価するためにＭＰＥＧ−２実験映像を使用したシミュレーション実験を遂行した。実験条件を説明すれば、入力映像としては、実験映像として当業者に知られている映像の中でフットボール（ｆｂ）、自動車（ｃａｒ）、スーズィー（ｓｕｓ）、自動車とカレンダー（ｍｏｂ）及びチアリーダー（ｃｈｅｅｒ）の５つのＭＰＥＧ−２映像シーケンスを使用した。
【００３５】
全ての映像は３０ヘルツのフレーム率を有し、各々１５０フレームよりなっている。各フレームの大きさは７２０×４８０である。４、２、１の探索点間隔を有する６４×６４（ＮＳ＝３２）、１０×１０、５×５の探索領域が各々階層２、１、０で選択された。階層０におけるブロックの大きさＮＢは１６であり、周辺ブロック間の相関性を調べるための臨界値Ｄは、８画素が外れれば類似度が低下することと見なすために８に設定した。この値は階層２における探索点間隔の２倍に該当する値である。
【００３６】
本発明に係る動き推定方法の効果を証明するために全域探索技法と一般の階層探索技法の性能とを比較した。複数候補戦略を採択した一般の階層探索技法の階層２では、最小予測誤差のみ有する三つの動きベクトルを候補に決める。反面に、提案した技法は三番目の候補を周辺ブロックの動きベクトルの中で予測する。表１にはＭＰＥＧ−２実験映像の最初の１５０フレームに対する動き予測及び動き補償性能を比較した結果を示した。
【００３７】
【表１】
0003615963.tif 000004
【００３８】
表１を参照すれば、本発明に係る動き推定方法は、全域探索技法に比べて０．２ｄＢ程度の微弱な性能減少を達成しながらも複雑度は全域探索技法の１．５％に過ぎないことと示される。画素当り平均絶対誤差ＭＡＤを計算するのに必要な演算数をＮ、ブロック数をＮＢとする時、複雑度は、
【００３９】
【数３】
0003615963.tif 000005
【００４０】
によって推定されうる。ここで、Ｎｓ２／６４項は階層２、３×２５／４項は階層１、２５項は階層０の解像度に従う計算量の比例値を示す。従って、３２と６４の  Ｎｓ  に対して全域探索技法（ＦＳＢＭＡ：  ｆｕｌｌ  ｓｃａｌｅ  ｂｌｏｃｋ  ｍａｔｃｈｉｎｇ  ａｎａｌｙｓｉｓ）の１．５％と０．７％に当ることが分かる。
【００４１】
また、表２には本発明に係る動き推定方法を比較的広い探索領域を要するＭＰＥＧ−２符号化器に適用した結果を示した。本実験ではＧＯＰ（Ｇｒｏｕｐ  ｏｆ  Ｐｉｃｔｕｒｅ）  Ｎは１２、Ｐフレーム間の距離Ｍは２、目標ビット率Ｔは６Ｍｂｐｓと設定して実験を進行した。表２には復元された映像のピーク信号対雑音比を比較した結果を示した。
【００４２】
【表２】
0003615963.tif 000006
【００４３】
表２を参照すれば、本発明に係る動き推定方法は全域探索技法の複雑度の０．９％という顕著な計算量減少を成し、ピーク信号対雑音比ＰＳＮＲはほとんど同じ水準を達成する。
【００４４】
前述したように本発明に係る動き推定方法は、フレーム間最小予測エラーを基本とした複数個の動きベクトル候補戦略と動きベクトル空間の相関性を効率的に使用することによって計算量が少なくて高速動き推定ができる。
【００４５】
このような本発明に係るリアルタイム動映像符号化のための超高速動き推定方法は動き推定装置で具現できる。前記動き推定装置（図示せず）は解像度調整手段、平均絶対誤差計算手段、初期探索点選択手段及び最終動きベクトル決定手段を具備する。
【００４６】
前記のような装置の動作を説明すれば、まず、解像度調整手段は入力された映像フレームを階層０とする時、階層０の解像度を低めて階層１を具備する。また、階層１の解像度を低めて階層２を具備する。例えば、解像度を１／２に低める場合には二つの隣接画素の平均を用い、解像度を１／４に低める場合には４つの隣接画素の平均を用いて映像フレームが具現できる。
【００４７】
平均絶対誤差計算手段は、階層２の探索領域に対する第１平均絶対誤差と、階層１で動きベクトル候補に対応する位置を探索中心点とする探索領域に対する第２平均絶対誤差、及び階層０で前記第２平均絶対誤差値が最小になる位置を階層０の探索中心点とした探索領域に対して第３平均絶対誤差を計算する。
【００４８】
初期探索点選択手段は前記第１平均絶対誤差値が最小になる少なくとも二つ以上の位置を次の段階（階層１）における初期探索中心点として選択する。また、動きベクトル候補選択手段は現在ブロックの周辺ブロックの相関性を用いて、一つ以上の他の初期探索中心点を次の段階（階層１）における初期探索中心点としてさらに選択する。
【００４９】
最終動きベクトル決定手段は前記第３平均絶対誤差値が最小になる位置と原点との距離情報を使用して最終動きベクトルに決定する。
【００５０】
また、前記動き推定方法の各段階はコンピュータで実行できるプログラムで作成可能である。また、コンピュータで用いられる媒体から前記プログラムを動作させる汎用ディジタルコンピューターで具現できる。前記媒体はフロッピーディスクやハードディスクのような磁気記録媒体、ＣＤ−ＲＯＭやＤＶＤのような光記録媒体、及びインターネットを通した伝送のような搬送波などの貯蔵媒体を含む。また、このような機能的プログラム、コード及びコードセグメントは本発明が属する技術分野のプログラマーにより容易に推論できる。
【００５１】
【発明の効果】
前述したように本発明に係る動き推定方法は、フレーム間最小予測エラーを基本とした複数個の動きベクトル候補戦略と動きベクトル空間の相関性を効率的に使用することによって計算量が少なくて高速動き推定ができる。
【図面の簡単な説明】
【図１】本発明が適用される動映像符号化装置の概略的な構造を示すブロック図である。
【図２】本発明の実施形態に係る動き推定方法の主要段階を示す流れ図である。
【図３】本発明の実施形態に係る動き推定方法によって階層別探索を遂行する時、各階層別探索位置を説明するための図である。
【図４】（Ａ）乃至（Ｆ）は本発明の実施形態に係る動き推定方法で、現在ブロックの周辺ブロックに対する相関性を用いて動きベクトル候補を決定する過程を説明するための図である。
【符号の説明】
ＳＲ（２）  階層２の探索領域
ＳＲ１（１），ＳＲ２（１），ＳＲ３（１）  階層１の探索領域
ＳＲ（０）  階層０の探索領域
【図１】
0003615963.tif 000007
【図２】
0003615963.tif 000008
【図３】
0003615963.tif 000009
【図４】
0003615963.tif 000010