(57)【要約】【課題】動き予測のための方法およびその装置が提供される。【解決手段】動き予測のための方法では複解像度階層的探索を用い、低解像度レベルでの最適ブロックモードの分割が可能になる。この方法により、高解像度レベルでの局所洗練中にブロックの分割がさらに可能になる。【選択図】  図２
2007028574.tif 000002
【特許請求の範囲】
【請求項１】
動き予測のための方法であって、この方法が：
（ａ）階層的データ構造を形成するために原フレームデータおよび基準フレームデータを用い、この階層的データ構造がＮ個の層を含むステップであって、Ｎ番目の層が原フレームデータおよび基準フレームデータを含み、残りのｉ番目の層が原フレームデータおよび基準フレームデータから生成されたデータを含み、ｉ番目の層の画像解像度が（ｉ＋１）番目の層の画像解像度よりも低く、ここでＮが２以上の正の整数であり、１≦ｉ＜Ｎであることを特徴とするステップと；
（ｂ）１番目の層上にあるマクロブロックの複数候補セットのコストに応じてこの候補セットから少なくとも１つの候補セットを選択し、この選択された候補セットを２番目の層に与えるステップであって、候補セットのおのおのがマクロブロックの可変ブロックモードと、この可変ブロックモードのブロックのおのおのの動きベクトルとのセットであることを特徴とするステップと；
（ｃ）Ｎが２より大きい場合に２番目から始まって２≦ｉ＜Ｎの順番で各ｉ番目の層に対して以下の２つのサブステップを順序実施するステップであって、このサブステップが：
（ｃ１）（ｉ−１）番目の層でもたらされる候補セットに基づいて局所探索を行うサブステップと；
（ｃ２）局所探索後に候補セットのコストに応じて局所探索から得られた候補セットから少なくとも１つの候補セットを選択し、選択された候補セットを（ｉ＋１）番目の層にもたらすサブステップであるステップと；
（ｄ）Ｎ番目の層に対して以下の２つのサブステップを実施するステップであって、このサブステップが：
（ｄ１）（Ｎ−１）番目の層でもたらされる候補セットに基づいて局所探索を行うサブステップと；
（ｄ２）局所探索後に候補セットのコストに応じて局所探索から得られた候補セットから１つの候補セットを選択するサブステップであるステップと
を含む方法。
【請求項２】
請求項１に記載の動き予測のための方法であって、各ｉ番目の層のデータが、（ｉ＋１）番目の層のデータに対して低帯域フィルタリングを行い、サブサンプリングを行うことから生成されることを特徴とする方法。
【請求項３】
請求項１に記載の動き予測のための方法であって、ステップ（ｂ）がさらに：
コストに対応付けられた候補が選択されないようコストの１つを調整するステップを含むことを特徴とする方法。
【請求項４】
請求項１に記載の動き予測のための方法であって、ステップ（ｃ２）あるいは（ｄ２）がさらに：
コストに対応付けられた候補が選択されないようそのコストあるいはコストの１つを調整するステップを含むことを特徴とする方法。
【請求項５】
請求項１に記載の動き予測のための方法であって、ステップ（ｃ１）あるいは（ｄ１）がさらに：
候補セットあるいは候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを次のステップの選択に追加するステップであって、導出された候補セットのおのおのおよび上述の候補セットが同一の可変ブロックモードをもつが、動きベクトルは異なることを特徴とするステップを含む方法。
【請求項６】
請求項１に記載の動き予測のための方法であって、ステップ（ｃ１）あるいは（ｄ１）がさらに：
候補セットあるいは候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを次のステップの選択に追加するステップであって、導出された候補セットのおのおのに対する可変ブロックモードが、上述の候補セットの可変ブロックモードを分割することから得られる結果であることを特徴とするステップを含む方法。
【請求項７】
動き予測のための装置であって、この装置が：
原フレームデータおよび基準フレームデータを用いて階層的データ構造を形成するための層生成器であって、この階層的データ構造が２つの層を含むものであって、２番目の層が原フレームデータおよび基準フレームデータを含み、１番目の層が原フレームデータおよび基準フレームデータから生成されるデータを含み、１番目の層の画像解像度が２番目の層の画像解像度よりも低いことを特徴とする層生成器と；
上述の候補セットのコストに応じて１番目の層上にあるマクロブロックの複数候補セットから少なくとも１つの候補セットをもたらすための全文対象探索ユニットであって、候補セットのおのおのがマクロブロックの可変ブロックモードと、この可変ブロックモードのブロックのおのおのの動きベクトルとのセットであることを特徴とする全文対象探索ユニットと；
全範囲探索ユニットにより与えられた候補セットに基づいて２番目の層に対して局所探索を行い、局所探索後に候補セットのコストに応じた局所探索で得られた候補セットから候補セットを選択するための最終探索ユニットと
を備える装置。
【請求項８】
請求項７に記載の動き予測装置であって、１番目の層のデータが、２番目の層のデータに対して低帯域フィルタリングを行い、サブサンプリングを行うことから生成されることを特徴とする装置。
【請求項９】
請求項７に記載の動き予測装置であって、全文対象探索ユニットがさらに、コストに対応付けられた候補が選択されないようコストの１つを調整するステップを含むことを特徴とする装置。
【請求項１０】
請求項７に記載の動き予測装置であって、最終探索ユニットがさらに、コストに対応付けられた候補が選択されないようコストあるいはコストの１つを調整するステップを含むことを特徴とする装置。
【請求項１１】
請求項７に記載の動き予測装置であって、最終探索ユニットがさらに、候補セットあるいは候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを局所探索後に選択に追加するステップを含み、導出された候補セットのおのおのおよび上述の候補セットが同一の可変ブロックモードをもつが、動きベクトルは異なることを特徴とする装置。
【請求項１２】
請求項７に記載の動き予測装置であって、最終探索ユニットがさらに、候補セットあるいは候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを局所探索後に選択に追加するステップを含み、導出された候補セットのおのおのの可変ブロックモードが上述の候補セットの可変ブロックモードを分割することから得られる結果であることを特徴とする装置。
【請求項１３】
動き予測のための装置であって、この装置が：
原フレームデータおよび基準フレームデータを用いて階層的データ構造を形成するための層生成器であって、この階層的データ構造がＮ個の層を含むものであって、Ｎ番目の層が原フレームデータおよび基準フレームデータを含み、残りのｉ番目の層が原フレームデータおよび基準フレームデータから生成されたデータを含み、ｉ番目の層の画像解像度が（ｉ＋１）番目の層の画像解像度よりも低く、ここでＮが２よりも大きな正の整数であり、１≦ｉ＜Ｎであることを特徴とする層生成器と；
上述の候補セットのコストに応じて１番目の層上にあるマクロブロックの複数候補セットから少なくとも１つの候補セットをもたらすための全文対象探索ユニットであって、候補セットのおのおのがマクロブロックの可変ブロックモードと、この可変ブロックモードのブロックのおのおのの動きベクトルとのセットであることを特徴とする全文対象探索ユニットと；
Ｎ−２個の局所探索ユニットであって、１番目の局所探索ユニットが２番目の層に対応して全文対象探索ユニットにより与えられる候補セットを受け入れ、ｋ番目の局所探索ユニットが（ｋ＋１）番目の層に対応して（ｋ−１）番目の局所探索ユニットにより与えられる少なくとも１つの候補セットを受け入れ、ここでｋは整数であり、１≦ｋ≦Ｎ−２であり、局所探索ユニットのおのおのが、受け入れられた候補セットに基づいて対応する層に対して局所探索を行い、局所探索後に候補セットのコストに応じて局所探索から得られた候補セットから選択された少なくとも１つの候補セットをもたらすことを特徴とする局所探索ユニットと；
（Ｎ−２）番目の局所探索ユニットにより与えられた候補セットに基づいてＮ番目の層に対して局所探索を行い、局所探索後に候補セットのコストに応じた局所探索で得られた候補セットから１つの候補セットを選択するための最終探索ユニットと
を備える装置。
【請求項１４】
請求項１３に記載の動き予測のための方法であって、各ｉ番目の層のデータが、（ｉ＋１）番目の層のデータに対して低帯域フィルタリングを行い、サブサンプリングを行うことから生成されることを特徴とする方法。
【請求項１５】
請求項１３に記載の動き予測装置であって、全文対象探索ユニットがさらに、コストに対応付けられた候補が選択されないようコストの１つを調整するステップを含むことを特徴とする装置。
【請求項１６】
請求項１３に記載の動き予測装置であって、局所探索ユニットおよび最終探索ユニット内の１つが、さらに、コストに対応付けられた候補が選択されないようコストあるいはコストの１つを調整するステップを含むことを特徴とする装置。
【請求項１７】
請求項１３に記載の動き予測装置であって、局所探索ユニットおよび最終探索ユニットの内の１つが、さらに、候補セットあるいは候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを局所探索後に選択に追加するステップを含み、導出された候補セットのおのおのおよび上述の候補セットが同一の可変ブロックモードをもつが、動きベクトルが異なることを特徴とする装置。
【請求項１８】
請求項１３に記載の動き予測装置であって、局所探索ユニットおよび最終探索ユニットの内の１つが、さらに、候補セットあるいは候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを局所探索後に選択に追加するステップを含み、導出された候補セットのおのおのの可変ブロックモードが上述の候補セットの可変ブロックモードを分割することにより得られる結果であることを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き予測の方法および装置、さらに詳細には、動きベクトル予測のための階層的探索を用いる方法およびその装置に関する。
【背景技術】
【０００２】
動き予測は、ビデオ圧縮エンコーダにおける計算量に関してもっとも複雑な計算エリアであり、さらに圧縮結果にもっとも影響を与えるものである。したがって、計算量およびメモリ利用量を低下させるために提案された多数の高速アルゴリズムがあり、これにより十分な圧縮品位が維持される。
【０００３】
さまざまな高速アルゴリズムの中で、階層的探索は、計算量とメモリ使用量との両方を効果的に減少させるアルゴリズムである。階層的探索法は、図１のフロー図で示されているとおり、Ｊ．Ｈ．リー[１]により提案されたものであり、可変ブロックが生成できる。
【０００４】
図１を参照すると、まず、ステップ１０１および１０２において、原フレームデータ１１１および基準フレームデータ１１２に対して低帯域フィルタリングおよびサブサンプリングが行われ、これにより３つの異なる解像度層が得られる。これらの層は、原解像度層、中間解像度層、低解像度層である。ここで、原解像度層には原フレームデータ１１１および基準フレームデータ１１２が含まれ、中間解像度層にはステップ１０１で生成されるデータが含まれ、低解像度層にはステップ１０２で生成されるデータが含まれる。
【０００５】
その後、ステップ１０３において、低解像度層に対して広範囲探索が行われ、これにより３つの動きベクトルが得られる。これらのベクトルは、２つの最適動きベクトルと、ビデオ基準から得られた1つの予測動きベクトルである。その後、ステップ１０４において、中間解像度層に対して局所探索が行われる。ここで、上述の低解像度層および中間解像度層に対して行われる両探索において、１６×１６のブロックサイズが用いられる。最後に、ステップ１０５において、中間解像度層から得られる動きベクトルに近接する原解像度層に対して局所探索が行われる。一方、１６×１６の原ブロックは８×８の４つの小さなブロックに分割される。さらに最終的に、最適ブロックモードおよび動きベクトル１１３が選択される。この方法の欠点としては、小さなブロックの動きベクトルが非常に小さな範囲に限られるということである。このため、小さなブロック間の物理的動きベクトルがそれぞれ大きく離れているような場合に効果的な予測ができない。
【０００６】
【非特許文献１】Ｊ．Ｈ．リーら著「高速複数解像度ブロック整合アルゴリズムおよび低ビット速度ビデオコーディングに対するＬＳＩアーキテクチャ」、ＩＥＥＥトランザクション、ビデオ技術用回路・システム、第１１巻、Ｎｏ．１２、２００１年１２月、ｐ．１２８９−１３０１
【発明の開示】
【発明が解決しようとする課題】
【０００７】
したがって、本発明の目的は動き予測のための方法を提供することである。このような方法を用いて、計算量が少なくメモリ使用量も小さいという利点が維持され、最適な可変ブロックモードおよび動きベクトルが正確に予測できる。
【０００８】
本発明の他の目的は、動き予測のための装置を提供することである。この装置により可変ブロック動きベクトルの高効率組合せをもたらすことができる。
【課題を解決するための手段】
【０００９】
上述の目的、その他を達成するため、本発明は動き予測方法を提供する。この方法は以下のステップを含む：
（ａ）階層的データ構造を形成するために原フレームデータおよび基準フレームデータを用い、この階層的データ構造がＮ個の層を含むステップであって、Ｎ番目の層が原フレームデータおよび基準フレームデータを含み、残りのｉ番目の層が原フレームデータおよび基準フレームデータから生成されたデータを含み、ｉ番目の層の画像解像度が（ｉ＋１）番目の層の画像解像度よりも低く、ここでＮが２以上の正の整数であり、１≦ｉ＜Ｎであることを特徴とするステップと；
（ｂ）１番目の層上にあるマクロブロックの複数候補セットのコストに応じてこの候補セットから少なくとも１つの候補セットを選択し、この選択された候補セットを２番目の層に与えるステップであって、候補セットのおのおのがマクロブロックの可変ブロックモードと、この可変ブロックモードのブロックのおのおのの動きベクトルとのセットであることを特徴とするステップと；
（ｃ）Ｎが２より大きい場合に２番目の層から始まって２≦ｉ＜Ｎの順番で各ｉ番目の層に対して以下の２つのサブステップを順次実施するステップであって、このサブステップが：
（ｃ１）（ｉ−１）番目の層でもたらされる候補セットに基づいて局所探索を行うサブステップと；
（ｃ２）局所探索後に候補セットのコストに応じて局所探索から得られた候補セットから少なくとも１つの候補セットを選択し、選択された候補セットを（ｉ＋１）番目の層にもたらすサブステップであるステップと；
（ｄ）Ｎ番目の層に対して以下の２つのサブステップを実施するステップであって、このサブステップが：
（ｄ１）（Ｎ−１）番目の層でもたらされる候補セットに基づいて局所探索を行うサブステップと；
（ｄ２）局所探索後に候補セットのコストに応じて局所探索から得られた候補セットから１つの候補セットを選択するサブステップであるステップ。
【００１０】
本発明の１つの実施例による動き予測方法において、各ｉ番目の層の全データが、（ｉ＋１）番目の層に対して低帯域フィルタリングおよびサブサンプリングを行うことで生成される。
【００１１】
本発明の１つの実施例による動き予測方法において、ステップ（ｃ１）あるいは（ｄ１）がさらに以下のサブステップ：候補セットの１つから複数の導出された候補セットを導出し、この導出された候補セットを次のステップの選択に追加するサブステップであって、導出された候補セットのおのおのおよび上述の候補セットが同一の可変ブロックモードをもつが、動きベクトルは異なることを特徴とするサブステップを含む。
【００１２】
本発明の１つの実施例による動き予測方法において、ステップ（ｃ１）あるいは（ｄ１）がさらに以下のサブステップ：候補セットの１つから複数の導出された並行候補セットを導出し、この導出された候補セットを次のステップの選択に追加するサブステップであって、導出された候補セットのおのおのの可変ブロックモードが、上述の候補セットの可変ブロックモードを分割することから得られる結果であることを特徴とするサブステップを含む。
【００１３】
本発明の他の観点により、本発明はさらに動き予測装置を提供するが、この装置は層発生器、全文対象探索ユニット、最終探索ユニットを含む。ここで、層発生器は、原フレームデータおよび基準フレームデータを用いて階層的データ構造を形成する。階層的データ構造は２つの層を含み、ここで、２番目の層は原フレームデータおよび基準フレームデータを含み、１番目の層は原フレームデータおよび基準フレームデータに基づいて生成されたデータを含み、１番目の層の画像解像度は２番目の層の画像解像度よりも低い。全文対象探索ユニットは、上述の候補セットのコストに応じて１番目の層のマクロブロックの複数の候補セットから選択された少なくとも１つの候補セットをもたらす。最終探索ユニットは、全文対象探索ユニットにより与えられた候補セットに基づいて２番目の層に対して局所探索を行い、局所探索後に候補セットのコストに応じた局所探索で得られた候補セットから候補セットを選択する。
【００１４】
本発明の他の観点により、本発明はさらに、動き予測装置を提供するが、この装置は層発生器、全文対象探索ユニット、Ｎ−２個の局所探索ユニットおよび最終探索ユニットを含み、ここでＮは２よりも大きな正の整数である。ここで、層発生器は、原フレームデータおよび基準フレームデータを用いて階層的データ構造を形成する。階層的データ構造はＮ個の層を含み、ここで、Ｎ番目の層は原フレームデータおよび基準フレームデータを含み、残りのｉ番目の層は原フレームデータおよび基準フレームデータに基づいて生成されたデータを含み、ｉ番目の層の画像解像度は（ｉ＋１）番目の層の画像解像度よりも低く、ここでｉは整数であり、１≦ｉ＜Ｎである。全文対象探索ユニットは、上述の候補セットのコストに応じて１番目の層のマクロブロックの複数の候補セットから選択された少なくとも１つの候補セットをもたらす。Ｎ−２個の局所探索ユニットの内、１番目の局所探索ユニットが２番目の層に対応して全文対象探索ユニットにより与えられる候補セットを受け入れ、ｋ番目の局所探索ユニットが（ｋ＋１）番目の層に対応して（ｋ−１）番目の局所探索ユニットにより与えられる少なくとも１つの候補セットを受け入れ、ここでｋは整数であり、１≦ｋ≦Ｎ−２である。さらに、各局所探索ユニットは、受け入れられた候補セットに基づき、対応する層に対して局所探索を行い、局所探索後に候補セットのコストに応じた局所探索で得られた候補セットから少なくとも１つの候補セットをもたらす。最終探索ユニットは、（Ｎ−２）番目の局所探索ユニットにより与えられた候補セットに基づいてＮ番目の層に対して局所探索を行い、局所探索後に候補セットのコストに応じた局所探索で得られた候補セットから１つの候補セットを選択する。
【００１５】
添付の図面は、本発明の理解をさらに深めるためのものであり、本仕様書に組み込まれ、その一部を構成するものである。これらの図面は本発明の実施例を示すものであり、説明とあわせて本発明の原理を説明する一助となるものである。
【発明の効果】
【００１６】
本発明において、最適ブロックモードは、低解像度の１番目の層に対する分割を可能にし、高解像度の層に対して局所探索が行われ、これによりこのブロックをさらに分解することができる。本発明によりさらに柔軟性がもたらされることから、計算量が少なくメモリ使用量も小さいという利点が維持され、最適な可変ブロックモードおよび動きベクトルが正確に予測できる。
【発明を実施するための最良の形態】
【００１７】
本発明の１つの実施例による動き予測方法は、これ以降、図２を参照しながらさらに詳しく説明される。図２は、ステップ２１０から始まる本実施例のフロー図である。
【００１８】
まず、ステップ２１０において、Ｎ層の階層的データ構造は、原フレームデータおよび基準フレームデータを含み、ここでＮは２以上の正の整数である。ここで、Ｎ番目の層は原フレームデータおよび基準フレームデータで構成され、残りのｉ番目の層のデータは、（ｉ＋１）番目の層のデータに対して低帯域フィルタリングおよびサブサンプリングを行うことで全て生成されるものであり、ここでｉは整数であり、１≦ｉ＜Ｎである。上述の説明から、Ｎ番目の層は最大画像解像度の原解像度層であり、この解像度は、最低解像度の１番目の層まで層を追う毎に小さくなることがわかる。
【００１９】
その後、ステップ２２０において、最低解像度の１番目の層に対して全文対象探索が行われ、これはまた、上述の候補セットのコストに応じてマクロブロックの複数候補セットから少なくとも１つの候補セットを選択するステップと、選択された候補セットを２番目の層に与えるステップとを含む広範囲探索として知られている。ここで、候補セットのおのおのは、上述のマクロブロックの可変ブロックモードと、この可変ブロックモードのブロックのおのおのの動きベクトルとのセットである。さらに、候補セットはビデオ圧縮エンコーダに対して最終的に与えられるデータ構造である。
【００２０】
上述の選択方法に関して、全般として、この方法では各候補に対するコストをまず計算し、その後、このコストを比較してさらに選択を行い、例えば、この方法では、最小量のある値のコストを選択する、あるいは特定の所定値よりもコストの小さな候補セットを選択する。このようにコスト計算およびさらに選択を行う方法は通常の当業者にとってよく知られた従来技術であるため、ここでは詳細を省略する。
【００２１】
ステップ２２０においてマクロブロックの動きベクトルだけを選択するのではなく、このマクロブロックの可変ブロックモードも選択するという点が従来技術と異なる。言い換えると、ステップ２２０において全マクロブロックを残しておくことが可能である、すなわち複数の小さなブロックに分解し、これらのブロックをさらに２番目の層に与えることが可能である。物理的適用を考慮するため、マクロブロックを小さなブロックに分解する際に、この小さいブロックのサイズが小さすぎるためにマクロブロックを分解したくない場合、小さなブロックの候補セットコストが選択されないよう適切に調整することができる。当然ながら、コスト調整はまた、他の形式の候補セットの選択を避けるために用いることができる。
【００２２】
それに続くステップには異なる２つのオプションがあり、このオプションはステップ２１０の階層的データ構造に基づいて選択される。Ｎが２に等しい場合、このプロセスはステップ２４０に進むが、ここでＮ番目の層に対して最終探索が行われ、Ｎが２より大きければ、このプロセスはまずステップ２３０に進むが、ここで２番目の層と（Ｎ−１）番目の層間で各層に対して局所探索が行われ、その後、このプロセスはステップ２４０に進む。
【００２３】
上で述べたとおり、Ｎが２より大きければ、このプロセスはまずステップ２３０に進み、ここで（ｉ−１）番目の層で与えられる候補セットに応じて２番目の層から各ｉ番目の層に対して局所探索が行われ、ここで２≦ｉ＜Ｎであり、その後、局所探索後に候補セットのコストに応じて局所探索から得られた候補セットから少なくとも１つの候補セットが選択され、選択された候補セットが（ｉ＋１）番目の層に与えられる。
【００２４】
上述の局所探索において、ｉ番目の層の高解像度のデータは、動きベクトルの再予測と、さらに選択を行うためにコストを再計算するため、（ｉ−１）番目の層で与えられる候補セットとともに用いられる。局所探索において、導出された複数候補セットが１つの候補セットから導出され、選択に合わされる。例えば、これらのセットは同一の可変ブロックモードをもつが、動きベクトルが異なる。その他の場合、（ｉ−１）番目の層で与えられる可変ブロックモードがさらに分割される。最適の圧縮品位を達成するため、全て可能性のある選択肢が独立した候補セットとして導出され、（ｉ＋１）番目の層の選択に合わされる。ステップ２２０と同じく、特定の候補セットあるいは複数候補セットのコストがステップ２３０で調整され、これによりフィルタリング結果が修正される。
【００２５】
最後のステップ２４０はステップ２２０（ここでＮは２に等しい）あるいはステップ２３０（ここでＮは２より大きい）に続くものである。ステップ２４０において、（Ｎ−１）番目の層により与えられる候補セットに基づいて原解像度をもつＮ番目の層に対して局所探索がまず行われ、その後、局所探索後に候補セットのコストに応じた局所探索で得られた候補セットから１つの候補セットが選択される。
【００２６】
実際には、ステップ２４０はステップ２３０に類似しており、これら２つのステップ間の主な違いは、局所探索が行われる層が同一ではなく、ステップ２４０においてビデオ圧縮エンコーダの入力として１つの候補セットだけが最終的に選択されるという点である。さらに、ステップ２４０で行われる局所探索により、導出された候補セットを選択することができ、局所探索から得られるコストが調整可能であり、これにより特定の候補セットあるいは複数の候補セットが選択されることを避けることができる。
【００２７】
上述の動き予測方法に加えて、本発明はさらに、動き予測装置を提供するが、この装置は動き予測方法を具現化するものである。図３は、本発明の他の実施例による動き予測装置３００の概略図である。動き予測装置３００は図２に示される動き予測方法を具現化するものであるが、ここでＮは２に等しい。
【００２８】
図３で示すとおり、動き予測装置３００は層発生器３０１、全文対象探索ユニット３０２、最終探索ユニット３０３を含む。ここで、層発生器３０１は、原フレームデータ３１１および基準フレームデータ３１２を用いて、ステップ２１０で示すとおり、階層的データ構造を形成する。しかし、本実施例の階層的データ構造では、低解像度の１番目の層と原解像度の２番目の層の２つの層だけを含む。さらに、全文対象探索ユニット３０２では、ステップ２２０で全文対象探索と同一の全文対象探索を１番目の層に対して行い、最終探索ユニット３０３に対して少なくとも１つの候補セットをもたらす。その後、最終探索ユニット３０３が、ステップ２４０で最終探索と同一の最終探索を上述の候補セットに対して行い、これにより最適候補セット３１３を選択する。
【００２９】
図４は、本発明の他の実施例による動き予測装置４００の概略図である。動き予測装置４００は図２に示される動き予測方法を具現化するものであるが、ここでＮは２より大きい。
【００３０】
図４で示されるとおり、動き予測装置４００は層発生器４０１、全文対象探索ユニット４０２、Ｎ−２個の局所探索ユニット（２つの局所探索ユニット４０３および４０４だけが図４で示されている）、最終探索ユニット４０５を含む。ここで、層発生器４０１は、原フレームデータ４１１および基準フレームデータ４１２を用いて、ステップ２１０で示すとおり、Ｎ層の階層的データ構造を形成し、ここでＮは２より大きい。さらに、全文対象探索ユニット４０２では、ステップ２２０で階層的データ構造の１番目の層に対して全文対象探索と同一の全文対象探索を行い、Ｎ−２個の局所探索ユニットの１番目の局所探索ユニットに対して少なくとも１つの候補セットをもたらす。
【００３１】
動き予測装置４００のＮ−２個の局所探索ユニットに関して、１番目の局所探索ユニット４０３が階層的データ構造の２番目の層に対応して全文対象探索ユニット４０２により与えられる候補セットを受け入れる。それに続くｋ番目の局所探索ユニットは（ｋ＋１）番目の層に対応し、（ｋ−１）番目の局所探索ユニットでもたらされる候補セットを受け入れるが、ここでｋは整数であり、１≦ｋ≦Ｎ−２である。さらに、局所探索ユニットのおのおのはステップ２３０の局所探索と同一の方法で、受け入れられた候補セットに基づく対応層に対して局所探索を行い、これにより少なくとも１つの候補セットを選択する。
【００３２】
上述の探索および選択の後、最終探索ユニット４０５はステップ２４０の局所探索と同一の方法で、最終局所探索ユニット４０４でもたらされた候補セットに基づく原解像度のＮ番目の層に対して局所探索を行い、これにより最適候補セット４１３を選択する。
【００３３】
上述の実施例より、本発明において、最適ブロックモードは、最低解像度の１番目の層に対する分割を可能にし、高解像度の層に対して局所探索が行われ、これによりこのブロックをさらに分解することができることがわかる。本発明によりさらに柔軟性がもたらされることから、計算量が少なくメモリ使用量も小さいという利点が維持され、最適な可変ブロックモードおよび動きベクトルが正確に予測できる。
【００３４】
本発明は、本発明の特定の実施例を参照しながら説明したが、通常の当業者であれば、本発明の考え方から逸脱することなく、説明された実施例に対して改造を行ってもよいことは明白である。したがって、本発明の適用範囲は、上述の詳細な説明ではなく、添付の請求項により決められる。
【図面の簡単な説明】
【００３５】
【図１】従来技術における動き予測方法を図示するフロー図の概略を示す。
【図２】本発明の１つの実施例による動き予測方法を図示するフロー図の概略を示す。
【図３】本発明の１つの実施例による動き予測装置の図の概略を示す。
【図４】本発明の１つの実施例による動き予測装置の図の概略を示す。
【符号の説明】
【００３６】
１１１ 原フレームデータ
１１２ 基準フレームデータ
１１３ ベクトル
３００ 予測装置
３０１ 層発生器
３０２ 全文対象探索ユニット
３０３ 最終探索ユニット
３１１ 原フレームデータ
３１２ 基準フレームデータ
３１３ 最適候補セット
４００ 予測装置
４０１ 層発生器
４０２ 全文対象探索ユニット
４０３ 局所探索ユニット
４０４ 最終局所探索ユニット
４０５ 最終探索ユニット
４１１ 原フレームデータ
４１２ 基準フレームデータ
４１３ 最適候補セット
【図１】
2007028574.tif 000003
【図２】
2007028574.tif 000004
【図３】
2007028574.tif 000005
【図４】
2007028574.tif 000006