(57)【要約】【課題】処理量が少なく、かつ隣接する代表点の動きも考慮した動き推定方法を提供することを目的とする。【解決手段】反復型動き推定部１０３は、第１のピクチャ中に代表点を設定する代表点設定ステップと、代表点の第２のピクチャに対する動きベクトルの初期値を設定する初期値設定ステップと、代表点の動きベクトルを所定の範囲内で変更して評価関数を計算し、評価関数値に応じて動きベクトルを更新する動き検出ステップと、所定の代表点に対して動き検出ステップによる処理を施し、異なる動きベクトルに更新された代表点の個数が所定値未満であれば処理を終了し、所定値以上であれば再び前記動き検出ステップの処理を実施する制御ステップと、を有している。【選択図】  図１
2004364064.tif 000002
【特許請求の範囲】
【請求項１】
第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルの初期値を設定する初期値設定ステップと、
前記代表点の動きベクトルを所定の範囲内で変更して評価関数を計算し、前記評価関数値に応じて動きベクトルを更新する動き検出ステップと、
所定の代表点に対して前記動き検出ステップによる処理を施し、異なる動きベクトルに更新された代表点の個数が所定値未満であれば処理を終了し、所定値以上であれば再び前記動き検出ステップの処理を実施する制御ステップと、を含むことを特徴とする動き推定方法。
【請求項２】
前記評価関数は、第１のピクチャ内の前記代表点の周辺の画素集合と、前記動きベクトルにより参照する前記第２のピクチャ内の画素集合との類似度と、前記代表点の動きベクトルと、前記代表点の近傍の代表点の動きベクトルとの類似度との重み付け和により表現されることを特徴とする、請求項１記載の動き推定方法。
【請求項３】
第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルをＮ（Ｎ≧２）種類の方法で検出する第１から第Ｎの動き検出ステップと、
前記代表点のそれぞれに対して、前記第１から第Ｎの動き検出ステップにより求められたＮ個の動きベクトルの中から、評価関数を用いて１つの動きベクトルを選択する動きベクトル選択ステップと、を含むことを特徴とする動き推定方法。
【請求項４】
前記動き検出ステップには、少なくとも請求項１記載の動き推定方法とブロックマッチング法とを含むことを特徴とする、請求項３記載の動き推定方法。
【請求項５】
前記動きベクトル選択ステップにより選択した動きベクトルを初期値として、再び動き検出処理を実施することを特徴とする請求項３記載の動き推定方法。
【請求項６】
前記評価関数は、第１のピクチャ内の前記代表点の周辺の画素集合と、前記動きベクトルにより参照する第２のピクチャ内の画素集合との類似度と、前記代表点の動きベクトルと、前記代表点の近傍の代表点の動きベクトルとの類似度とを用いて表現されることを特徴とする、請求項３記載の動き推定方法。
【請求項７】
第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルを検出する動き検出ステップと、
前記代表点の動きベクトルの有効性を、前記代表点の近傍の代表点の動きベクトルまたは前記第１と第２のピクチャを用いて判定する動きベクトル判定ステップとを含むことを特徴とする動き推定方法。
【請求項８】
さらに前記動きベクトル判定ステップで無効と判断された動きベクトルに対して補正を施す動きベクトル補正ステップを有することを特徴とする、請求項７記載の動き推定方法。
【請求項９】
前記動きベクトル判定ステップでは、隣接する代表点により形成される第１の多角形の面積と、前記隣接する代表点のそれぞれが動きベクトルにより参照する前記第２のピクチャ中の対応点により形成される第２の多角形の面積との比が、所定の範囲内であれば、前記代表点の動きベクトルを有効と判断することを特徴とする、請求項７記載の動き推定方法。
【請求項１０】
前記動きベクトル判定ステップでは、隣接する代表点により形成される第１の多角形内での前記隣接する代表点の位置関係と、前記隣接する代表点のそれぞれが動きベクトルにより参照する前記第２のピクチャ中の対応点により形成される第２の多角形内での前記対応点の位置関係とが、同じ位置関係であれば、前記代表点の動きベクトルを有効と判断することを特徴とする、請求項７記載の動き推定方法。
【請求項１１】
前記動きベクトル判定ステップでは、代表点が動きベクトルにより参照する前記第２のピクチャ中の第２の対応点から、前記第１のピクチャに対して動き検出処理を行うことにより第１の対応点を求め、前記代表点と前記第１の代表点との距離が所定の値以下であれば、前記代表点の動きベクトルを有効と判断することを特徴とする、請求項７記載の動き推定方法。
【請求項１２】
前記動きベクトル補正ステップでは、隣接する代表点のうち有効な動きベクトルを用いて動きベクトルの補間処理を行うことを特徴とする請求項８記載の動き推定方法。
【請求項１３】
請求項１〜１２の何れか１項に記載の動き推定方法により代表点の動きベクトルを検出する動き推定ステップと、
前記代表点以外の画素の動きベクトルを近傍の代表点の動きベクトルから補間生成することにより動き補償を行い予測画像を生成する動き補償ステップと、
前記予測画像を用いて符号化処理を行う符号化ステップとを含むことを特徴とする動画像符号化方法。
【請求項１４】
コンピュータにより、請求項１記載の動き推定方法を行うためのプログラムであって、
上記プログラムはコンピュータに、
第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルの初期値を設定する初期値設定ステップと、
前記代表点の動きベクトルを所定の範囲内で変更して評価関数を計算し、前記評価関数値に応じて動きベクトルを更新する動き検出ステップと、
所定の代表点に対して前記動き検出ステップによる処理を施し、異なる動きベクトルに更新された代表点の個数が所定値未満であれば処理を終了し、所定値以上であれば再び前記動き検出ステップの処理を実施する制御ステップと、からなる動き推定方法を、行わせるものであることを特徴とするプログラム。
【請求項１５】
コンピュータにより、請求項３記載の動き推定方法を行うためのプログラムであって、
上記プログラムはコンピュータに、
第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルをＮ（Ｎ≧２）種類の方法で検出する第１から第Ｎの動き検出ステップと、
前記代表点のそれぞれに対して、前記第１から第Ｎの動き検出ステップにより求められたＮ個の動きベクトルの中から、評価関数を用いて１つの動きベクトルを選択する動きベクトル選択ステップと、からなる動き推定方法を、行わせるものであることを特徴とするプログラム。
【請求項１６】
コンピュータにより、請求項７記載の動き推定方法を行うためのプログラムであって、
上記プログラムはコンピュータに、
第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルを検出する動き検出ステップと、
前記代表点の動きベクトルの有効性を、前記代表点の近傍の代表点の動きベクトルまたは前記第１と第２のピクチャを用いて判定する動きベクトル判定ステップとからなる動き推定方法を、行わせるものであることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画素の動きベクトルを近隣の複数の代表点の動きベクトルからの内挿により求める動き推定方法、およびその動きベクトルを用いて符号化処理を行う動画像符号化方法に関する。
【０００２】
【従来の技術】
近年、音声，画像，その他の画素値を統合的に扱うマルチメディア時代を迎え、従来からの情報メディア，つまり新聞，雑誌，テレビ，ラジオ，電話等の情報を人に伝達する手段がマルチメディアの対象として取り上げられるようになってきた。一般に、マルチメディアとは、文字だけでなく、図形、音声、特に画像等を同時に関連づけて表すことをいうが、上記従来の情報メディアをマルチメディアの対象とするには、その情報をディジタル形式にして表すことが必須条件となる。
【０００３】
ところが、上記各情報メディアの持つ情報量をディジタル情報量として見積もってみると、文字の場合１文字当たりの情報量は１〜２バイトであるのに対し、音声の場合１秒当たり６４Ｋｂｉｔｓ（電話品質）、さらに動画については１秒当たり１００Ｍｂｉｔｓ（現行テレビ受信品質）以上の情報量が必要となり、上記情報メディアでその膨大な情報をディジタル形式でそのまま扱うことは現実的では無い。例えば、テレビ電話は、６４Ｋｂｉｔ／ｓ〜１．５Ｍｂｉｔ／ｓの伝送速度を持つサービス総合ディジタル網（ＩＳＤＮ  ：  Ｉｎｔｅｇｒａｔｅｄ  Ｓｅｒｖｉｃｅｓ  Ｄｉｇｉｔａｌ  Ｎｅｔｗｏｒｋ）によってすでに実用化されているが、テレビ・カメラの映像をそのままＩＳＤＮで送ることは不可能である。
【０００４】
そこで、必要となってくるのが情報の圧縮技術であり、例えば、テレビ電話の場合、ＩＴＵ−Ｔ（国際電気通信連合  電気通信標準化部門）で勧告されたＨ．２６１やＨ．２６３規格の動画圧縮技術が用いられている。また、ＭＰＥＧ−１規格の情報圧縮技術によると、通常の音楽用ＣＤ（コンパクト・ディスク）に音声情報とともに画像情報を入れることも可能となる。
【０００５】
ここで、ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）とは、ＩＳＯ／ＩＥＣ（国際標準化機構  国際電気標準会議）で標準化された動画像信号圧縮の国際規格であり、ＭＰＥＧ−１は、動画像信号を１．５Ｍｂｉｔ／ｓまで、つまりテレビ信号の情報を約１００分の１にまで圧縮する規格である。また、ＭＰＥＧ−１規格では対象とする品質を伝送速度が主として約１．５Ｍｂｉｔ／ｓで実現できる程度の中程度の品質としたことから、さらなる高画質化の要求をみたすべく規格化されたＭＰＥＧ−２では、動画像信号を２〜１５Ｍｂｉｔ／ｓでＴＶ放送品質を実現する。さらに現状では、ＭＰＥＧ−１，ＭＰＥＧ−２と標準化を進めてきた作業グループ（ＩＳＯ／ＩＥＣ  ＪＴＣ１／ＳＣ２９／ＷＧ１１）  によって、ＭＰＥＧ−１，ＭＰＥＧ−２を上回る圧縮率を達成し、更に物体単位で符号化・復号化・操作を可能とし、マルチメディア時代に必要な新しい機能を実現するＭＰＥＧ−４が規格化された。ＭＰＥＧ−４では、当初、低ビットレートの符号化方法の標準化を目指して進められたが、現在はインタレース画像も含む高ビットレートも含む、より汎用的な符号化に拡張されている。
【０００６】
一般に動画像の符号化では、時間方向および空間方向の冗長性を削減することによって情報量の圧縮を行う。そこで時間的な冗長性の削減を目的とする画面間予測符号化では、前方または後方のピクチャを参照してブロック単位で動きの検出および予測画像の作成を行い、得られた予測画像と符号化対象ピクチャとの差分値に対して符号化を行う。ここで、ピクチャとは１枚の画面を表す用語であり、プログレッシブ画像ではフレームを意味し、インタレース画像ではフレームもしくはフィールドを意味する。ここで、インタレース画像とは、１つのフレームが時刻の異なる２つのフィールドから構成される画像である。インタレース画像の符号化や復号化処理においては、１つのフレームをフレームのまま処理したり、２つのフィールドとして処理したり、フレーム内のブロック毎にフレーム構造またはフィールド構造として処理したりすることができる。
【０００７】
参照画像を持たず画面内予測符号化を行うものをＩピクチャと呼ぶ。また、１枚のピクチャのみを参照し画面間予測符号化を行うものをＰピクチャと呼ぶ。また、同時に２枚のピクチャを参照して画面間予測符号化を行うことのできるものをＢピクチャと呼ぶ。Ｂピクチャは表示時間が前方もしくは後方から任意の組み合わせとして２枚のピクチャを参照することが可能である。参照画像（参照ピクチャ）は符号化および復号化の基本単位であるブロックごとに指定することができるが、符号化を行ったビットストリーム中に先に記述される方の参照ピクチャを第１参照ピクチャ、後に記述される方を第２参照ピクチャとして区別する。ただし、これらのピクチャを符号化および復号化する場合の条件として、参照するピクチャが既に符号化および復号化されている必要がある。
【０００８】
Ｐピクチャ又はＢピクチャの符号化には、動き補償画面間予測符号化が用いられている。動き補償画面間予測符号化とは、画面間予測符号化に動き補償を適用した符号化方式である。動き補償とは、単純に参照フレームの画素値から予測するのではなく、ピクチャ内の各部の動き量（以下、これを動きベクトルと呼ぶ）を検出し、当該動き量を考慮した予測を行うことにより予測精度を向上すると共に、データ量を減らす方式である。例えば、符号化対象ピクチャの動きベクトルを検出し、その動きベクトルの分だけシフトした予測値と符号化対象ピクチャとの予測残差を符号化することによりデータ量を減している。この方式の場合には、復号化の際に動きベクトルの情報が必要になるため、動きベクトルも符号化されて記録又は伝送される。
【０００９】
上記のＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４方式等では、動きベクトルは１６画素×１６画素の大きさを有するマクロブロック単位で検出されており、具体的には、符号化対象ピクチャ側のマクロブロックを固定しておき、参照ピクチャ側のマクロブロックを探索範囲内で移動させ、基準ブロックと最も似通った参照ブロックの位置を見つけることにより、ブロック位置の変化分が動きベクトルとして検出される。ここで、基準ブロックと参照ブロックとがどの程度似通っているかは、所定の評価基準を用いるより決定することができるが、その評価基準としては、例えば対応する画素の差分値の２乗和や絶対値和が用いられる。そして、その２乗和や絶対値和が最小となる参照ブロックが選択される。このような方式は、ブロックマッチングと呼ばれる。
【００１０】
ブロックマッチングは、現在広く採用されているが、ブロック内のすべての画素が同一の動きベクトルを持つ、すなわち平行移動をする、という前提を有している。そのため、拡大・縮小などの変形などを伴う場合、ブロックマッチングでは、動き補償時の誤差が大きくなるという問題点を有している。
【００１１】
そこでこの問題を解決するために、画素が異なる動きベクトルを持ち、拡大や縮小などの変形に対応することができる動き補償方式が提案されている。以下にこの方式の一例である空間変換に基づく動き補償について説明する。
空間変換に基づく動き補償では、予測画像の位置（ｘ，  ｙ）の画素値を参照画像の位置（ｘ’，ｙ’）の画素値として取得する際に、ｘ’とｙ’の値がｘとｙに対して所定の変換式を施して得られるものである。ブロックマッチングは、ｘとｙのそれぞれに水平方向および垂直方向の移動量を加算することにより、ｘ’とｙ’とが得られるため、空間変換に基づく動き補償の特殊な例と考えることもできる。
【００１２】
変換関数の形としては、アフィン変換を用いた例（非特許文献１）、共１次変換を用いた例、透視変換を用いた例などが提案されている。
ここで変換関数のパラメータは、符号化側で領域毎に決定し、それを復号化側に伝送することにより、復号化側でも同じ変換を行うことができる。例えば、変換関数にアフィン変換を用い、領域の形状が３角形であるとする。この場合、６個のアフィン変換パラメータを伝送しても良いし、領域の３個の頂点の動きベクトルを伝送し、復号化側で６個のアフィン変換パラメータを再生しても良い。また、共１次変換、透視変換を用いた場合、領域の形状を４角形とすれば同様の処理が可能となる。
【００１３】
以下では、変換関数にアフィン変換を用いた場合について説明する。まず現ピクチャに複数の代表点が設定され、隣接する代表点を線分で結ぶことにより複数の多角形領域が形成される。そして、各代表点に対して動き推定を行う。これは具体的には現ピクチャの各代表点に対し、参照ピクチャにおいて対応している点を求めることにより実行される。つまり、代表点の移動があれば参照画像の対応点は現ピクチャの代表点と異なった場所に位置することになる。この結果、動き推定後の参照ピクチャでは、各多角形領域は変形されたものとなる。予測画像は多角形内の各画素に関して変換関数を計算し、参照ピクチャの中から対応する点の画素値を求めることにより生成される。
【００１４】
さて、各代表点の動き推定の方法、すなわち動きベクトルを求める方法としては、第１段階目にブロックマッチングにより大まかな動き推定を行った後、第２段階目に代表点の動きベクトルを少しずつ変化させて、参照ピクチャの多角形領域を変形させ、動きベクトルを変化させる度に予測誤差を計算し、その結果予測誤差を最も小さくした動きベクトルを新たに採用する方法が提案されている（第１の従来方法）。また、このような処理では演算量が膨大となることから、評価関数に重みをつけながらブロックマッチングのみで動き推定を行う方法（特許文献１、第２の従来方法）も提案されている。
【００１５】
【特許文献１】
特開平０８−１１６５４１号公報
【００１６】
【非特許文献１】
中屋他、「３角形パッチに基づく動き補償の基礎検討」、電子情報通信学会技術報告、ＩＥ９０−１０６、平２−０３
【００１７】
【発明が解決しようとする課題】
しかしながら、上記第１の従来方法では、第２段階目の処理として、代表点の動きベクトルから変換パラメータを求め、その変換パラメータから予測画像を生成して予測誤差を計算し、予測誤差が小さくなる方向に動きベクトルを徐々に修正させていくため、特に予測画像を生成するために膨大な処理量が必要となる。
【００１８】
また、上記第２の従来方法では、代表点を含むブロックを用いたブロックマッチングのみにより動き推定を行う。この方法は、第１の従来方法と比較して処理量を大きく削減することができるが、他の代表点の動きを考慮していないため、隣接する代表点が同じような動きをしていても、絵柄によっては異なる動きベクトルとして推定されることがある。代表点で囲まれる領域中の画素の動きベクトルは、それらの代表点の動きベクトルから計算するため、一つでも大きく異なる動きベクトルがあると、領域中のすべての画素の動きベクトルが正しくない動きベクトルとなってしまうという課題を有していた。
【００１９】
【課題を解決するための手段】
この課題を解決するために、第１の発明は、第１のピクチャ中に代表点を設定する代表点設定ステップと、前記代表点の第２のピクチャに対する動きベクトルの初期値を設定する初期値設定ステップと、前記代表点の動きベクトルを所定の範囲内で変更して評価関数を計算し、前記評価関数値に応じて動きベクトルを更新する動き検出ステップと、所定の代表点に対して前記動き検出ステップによる処理を施し、異なる動きベクトルに更新された代表点の個数が所定値未満であれば処理を終了し、所定値以上であれば再び前記動き検出ステップの処理を実施する制御ステップと、を含むことを特徴としている。
【００２０】
第２の発明は、第１のピクチャ中に代表点を設定する代表点設定ステップと、前記代表点の第２のピクチャに対する動きベクトルをＮ（Ｎ≧２）種類の方法で検出する第１から第Ｎの動き検出ステップと、前記代表点のそれぞれに対して、前記第１から第Ｎの動き検出ステップにより求められたＮ個の動きベクトルの中から、評価関数を用いて１つの動きベクトルを選択する動きベクトル選択ステップと、を含むことを特徴としている。
第３の発明は、第１のピクチャ中に代表点を設定する代表点設定ステップと、
前記代表点の第２のピクチャに対する動きベクトルを検出する動き検出ステップと、
前記代表点の動きベクトルの有効性を、前記代表点の近傍の代表点の動きベクトルまたは前記第１と第２のピクチャを用いて判定する動きベクトル判定ステップと、を含むことを特徴としている。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態について、図１から図１６を用いて説明する。
【００２２】
（実施の形態１）
まず、本発明の動き推定方法の第１の実施の形態を図１を用いて説明する。
【００２３】
図１は、本発明の動き推定方法を用いた動画像符号化装置１００のブロック図である。動画像符号化装置１００は、本発明の動き推定方法を実施する動き推定部１０１と、予測画像生成部１０５、予測誤差符号化部１０６、可変長符号化部１０７、予測誤差復号化部１０８、差分演算部１０９、加算演算部１１０から構成され、動き推定部１０１は、フレームメモリ１０２、１０４，反復型動き推定部１０３から構成される。
【００２４】
フレームメモリ１０２には入力画像が入力され、現ピクチャが保持される。また、フレームメモリ１０４には、既に符号化済みの参照ピクチャが保持されているとする。
反復型動き推定部１０３では、フレームメモリ１０２に保持された現ピクチャの画像データと、フレームメモリ１０４に保持された参照ピクチャの画像データとを用いて、動き推定を行う。反復型動き推定部１０３の動作を図２、図３を用いて説明する。
【００２５】
図２（ａ）は、現ピクチャの画素の並びの一部を示す模式図である。図２（ａ）において、黒丸と白丸はそれぞれ画素を示している。また、白丸は代表点を表している。図２（ａ）に示すように、代表点は、代表点を結ぶことによって三角形が構成されるように配置される。
【００２６】
図３は、反復型動き推定部１０３の処理内容を示すフローチャートである。まず、ステップＳ３０１において、全ての代表点に対して初期動きベクトルを設定する。ここでは、初期動きベクトルの大きさは０であるとする。そして、全ての代表点に対して、所定の順番でステップＳ３０２、ステップＳ３０３の処理を行う。所定の順番としては、例えばラスタ順がある。ステップＳ３０２では、代表点の現在の動きベクトルが指し示す参照ピクチャ中の位置を中心として、所定の範囲に対して評価関数を求める。例えば、現在処理中の代表点が図２の２０１であるとすると、例えば画素集合（ブロック）２１０に含まれる画素を用いて、評価関数値を求める。
ここで、評価関数値は、（数式１）により求めるとする。
【００２７】
【数１】
2004364064.tif 000003
【００２８】
ここで、ｉは代表点番号、Ｊｉは代表点ｉの評価関数値、Ｂｉは代表点ｉの動きベクトルを探索する際に用いる画素集合（例えば代表点２０１に対する画素集合２１０）、Ｄｊは現ピクチャの画素と参照ピクチャ中の対応画素との差を示す値（例えば差の絶対値や、差の２乗値）、Ｎｉは代表点ｉに隣接する代表点の集合（例えば代表点２０１に対しては、代表点２０２〜２０７）、Ｒｉｋは代表点ｉと代表点ｋの動きベクトルの差を表す値（例えば動くベクトルの各成分の差分値の２乗和）、αは重み係数である。
【００２９】
すなわち（数式１）の右辺第１項は、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離の指標を示し、右辺第２項は、注目代表点の動きベクトルとその隣接代表点との動きベクトルの距離の指標を示す。
図２（ｂ）を用いて評価関数値を求める範囲について説明する。図２（ｂ）の現ピクチャ中の画素２５６が、現在注目する代表点であり、その周辺画素集合がブロック２５０である。また、代表点２５６の現在の動きベクトルが動きベクトル２５４であるとする。この際、動きベクトル２５４が指し示す位置２５２を中心として、所定の範囲２５１の中を指し示す動きベクトルを用いて評価関数値を計算する。例えば、位置２５２に対する評価関数値の第１項は、ブロック２５０とブロック２５７の画素値を用いて計算することになる。そして範囲２５１内での位置を少しずつずらしながら（動きベクトルの値を変化させながら）、評価関数値を求めていく。ここで、範囲２５１としては、例えば参照ピクチャ中のブロックの中心位置が上下左右に１〜３画素程度移動するような範囲に設定することができる。
【００３０】
ステップＳ３０３では、ステップＳ３０２で求めた評価関数値のうち、最小となる評価関数値を求める。そして、その評価関数値が最小となる位置を求め、その位置を指す動きベクトルに更新する。例えば図２（ｂ）において、位置２５８に対する評価関数値が最小であったとすると、代表点２５６の動きベクトルは、動きベクトル２５５に更新することになる。ここで、評価関数値が最小値を示す動きベクトルが元の動きベクトルと同じ場合には、更新処理は行わない。
【００３１】
このような処理をすべての代表点に対して行う。すべての代表点に対して処理が終了すると、ステップＳ３０４において、動きベクトル値が更新された代表点の数を計数し、その個数が所定値以下あるかどうかを判断する。所定値としては、例えば全代表点の個数の１％などの値を用いることができる。そして、条件を満たしていれば処理を終了し、条件を満たしていなければ、現在の動きベクトルを初期値として、全代表点に対してステップＳ３０２とステップＳ３０３の処理を再び実行する。
【００３２】
すべての処理が完了すると、反復型動き推定部１０３は、全代表点の動きベクトルを予測画像生成部１０５、可変長符号化部１０７に対して出力する。予測画像生成部１０５では、反復型動き推定部１０３から出力された各代表点の動きベクトルと、フレームメモリ１０４から得られる参照ピクチャの画像データとを用いて、予測画像（動き補償画像）を生成する。
【００３３】
例えば、図２（ａ）における代表点２０１、２０２、２０３により囲まれる三角形領域内の画素は、代表点２０１、２０２、２０３の動きベクトルから各画素位置での動きベクトルを内挿生成し、その生成された動きベクトルを用いて、参照ピクチャから画素値を取得することにより、予測画素を生成する。ここで、動きベクトルの内挿方法としては、従来方法で説明した方法（例えばアフィン変換）を用いることができる。
【００３４】
予測画像は差分演算部１０９と加算演算部１１０に対して出力される。差分演算部１０９では、フレームメモリ１０２から得られる現ピクチャとの差分画像が計算される。差分画像は予測誤差符号化部１０６に入力され、周波数変換や量子化等の処理が施されて、符号化データとなり、可変長符号化部１０７と予測誤差復号化部１０８に対して出力される。可変長符号化部１０７では、予測誤差符号化部１０６にから入力された符号化データと、反復型動き推定部１０３から入力された各代表点の動きベクトルとに対して可変長符号化を施して、符号列として出力する。
【００３５】
また、予測誤差復号化部１０８では、予測誤差符号化部１０６から入力された符号化データに対して、逆量子化や逆周波数変換等の処理を施し、復号化差分画像として加算演算部１１０に対して出力する。加算演算部１１０では、予測誤差復号化部１０８から入力された復号化差分画像と、予測画像生成部１０５から入力された予測画像とを加算し、復号化画像を生成し、それをフレームメモリ１０４に対して出力する。この復号化画像は、以降の入力画像を符号化する際の参照ピクチャとして用いる。
【００３６】
以上のように、本発明の動き推定方法および動画像符号化方法では、画像中に代表点を設定し、各代表点の動きベクトルを求める際に、小さな探索範囲を設定し、（数式１）で示す評価関数値が最小となる位置を指す動きベクトルに更新する。この処理を動きベクトルが更新される代表点の個数が所定値以下となるまで繰り返し、最終的な動きベクトルを決定する。ここで、評価関数は、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離の指標と、注目代表点の動きベクトルとその隣接代表点との動きベクトルの距離の指標の重み付け和である。
【００３７】
したがって、本発明の動き推定方法および動画像符号化方法を用いることにより、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離が小さく、かつ隣接代表点の動きベクトルとの距離も小さい動きベクトルを得ることができる。すなわち、他の代表点の動きも考慮することができるため、誤った動きベクトルを推定する可能性が小さくなり、これにより隣接代表点と大きく異なる動きベクトルが求められる可能性が非常に小さくなり、領域中の画素の動きベクトルを正確に得ることができるため、例えば第２の従来方法等と比較して、予測画像（動き補償画像）の画質の向上、すなわち符号化画像の画質の向上を図ることができる。また、例えば第１の従来方法と比較すると、動き推定の際に領域内の画素毎の動きベクトル（変換パラメータ）を求める必要がないため、処理量の大幅な削減を行うことができる。
【００３８】
なお、本実施の形態においては、動き推定における参照ピクチャは既に符号化済みのピクチャを用いるとしたが、これは参照ピクチャの原画像を用いても良い。ただし、符号化においては、本実施の形態と同様に符号化済みのピクチャを用いる。
【００３９】
また、本実施の形態においては、本発明の動き推定方法を利用した例として、動画像符号化に適用する場合について説明したが、これは動画像符号化以外の処理、例えば画像処理等に適用しても良い。
また、本実施の形態においては、図２（ｂ）のように代表点の配置と領域の分割を行う場合を例として説明したが、代表点の配置方法と領域の分割方法は、他の方法であっても良い。他の方法の一例としては、例えば図４（ａ）、（ｂ）のような方法がある。また、領域の分割方法は、固定でなくても良く、例えば画像のエッジ情報を取得し、そのエッジに沿って領域を分割し、代表点を配置するような方法であっても良い。
【００４０】
また、本実施の形態においては、現ピクチャに対して代表点を設定し、その代表点と参照ピクチャとの動き量に基づいて、現ピクチャの領域中の各画素の動きを補間生成し、参照ピクチャから動き補償する場合について説明したが、これは、参照ピクチャに対して所定の代表点を設定し、その代表点と現ピクチャとの動き量に基づいて、現ピクチャの領域中の各画素の動きを補間生成し、参照ピクチャから動き補償する場合であっても良い。
【００４１】
（実施の形態２）
次に、本発明の動き推定方法の第２の実施の形態について、図５を用いて説明する。
図５は、本発明の動き推定方法を用いた動画像符号化装置５００のブロック図である。動画像符号化装置５００は、本発明の動き推定方法を実施する動き推定部５０１と、予測画像生成部１０５、予測誤差符号化部１０６、可変長符号化部１０７、予測誤差復号化部１０８、差分演算部１０９、加算演算部１１０から構成され、動き推定部５０１は、フレームメモリ５０２、５０４、反復型動き推定部５０３、ブロックマッチング動き推定部５０５、動きベクトル選択部５０６から構成される。
【００４２】
動き推定部５０１以外の動作は、第１の実施の形態と同様であるので、ここでは動き推定部５０１の動作について説明する。
フレームメモリ５０２には入力画像が入力され、現ピクチャが保持される。また、フレームメモリ５０４には、既に符号化済みの参照ピクチャが保持されているとする。
【００４３】
まず、反復型動き推定部５０３において、フレームメモリ５０２に保持された現ピクチャの画像データと、フレームメモリ５０４に保持された参照ピクチャの画像データとを用いて、動き推定を行う。この動作は、第１の実施の形態と同様であるので、詳細な説明は割愛する。検出された動きベクトルは、動きベクトル選択部５０６に対して出力される。
【００４４】
次に、ブロックマッチング型動き推定部５０５において、フレームメモリ５０２に保持された現ピクチャの画像データと、フレームメモリ５０４に保持された参照ピクチャの画像データとを用いて、動き推定を行う。これは、反復型動き推定部５０３において現ピクチャに対して設定した代表点と同じ代表点を用いて、その周辺画素から構成される画素集合（ブロック）を用いて、従来のブロックマッチングと同様の処理により、現ピクチャから参照ピクチャに対して探索を行うことにより、動き推定を行う。検出された動きベクトルは、動きベクトル選択部５０６に対して出力される。ここで、ブロックマッチングの際には、ブロック間の画素差分値のみを動き推定の評価関数としても良いし、ブロック間の画素差分値と、既に動きベクトルの検出が終わっている周辺代表点の動きベクトルとの相関性とを用いた評価関数を使っても良い。
【００４５】
動きベクトル選択部５０６では、反復型動き推定部５０３とブロックマッチング型動き推定部５０５とから入力された各代表点の動きベクトルを用いて、代表点毎に動きベクトルの選択を行う。
代表ベクトルの選択方法を説明する。選択方法としては、代表点毎に評価関数値を求め、それを比較することにより決定することができる。例えば、評価関数値としては、（数式１）、（数式２）、（数式３）等を用いることができる。
【００４６】
【数２】
2004364064.tif 000004
【００４７】
【数３】
2004364064.tif 000005
【００４８】
ここで、各記号の定義は（数式１）の記号の定義に従う。
例えば（数式２）を用いることにより、参照する画像との差分値による類似度により、各動きベクトルを評価することができる。また、例えば（数式１）、（数式３）を用いることにより、参照する画像との差分値による類似度と隣接する代表点の動きベクトルとの類似度とを用いることにより、各動きベクトルを評価することができる。
【００４９】
動きベクトル選択部５０６で選択された各代表点の動きベクトルは、反復型動き推定部５０３に対して出力される。反復型動き推定部５０３では、動きベクトル選択部５０６から入力された各代表点の動きベクトルを初期値として、再び動き推定を行う。この動作は、図３のフローチャートにおけるＳ３０１における、初期動きベクトルとして、動きベクトル選択部５０６から入力された各代表点の動きベクトルを用いることに相当する。
【００５０】
そして、反復型動き推定部５０３において検出された動きベクトルは、予測画像生成部１０５と可変長符号化部１０７に対して出力され、第１の実施の形態と同様の処理により、符号化処理が行われる。
以上のように、本発明の動き推定方法および動画像符号化方法では、画像中に代表点を設定し、各代表点の動きベクトルを求める際に、小さな探索範囲を設定し、（数式１）で示す評価関数値が最小となる位置を指す動きベクトルに更新する。この処理を動きベクトルが更新される代表点の個数が所定値以下となるまで繰り返し、第１の動きベクトルを決定する。ここで、評価関数は、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離の指標と、注目代表点の動きベクトルとその隣接代表点との動きベクトルの距離の指標の重み付け和である。したがって、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離が小さく、かつ隣接代表点の動きベクトルとの距離も小さい動きベクトルを得ることができる。次に、従来のブロックマッチング法を用いて、各代表点の第２の動きベクトルを用いる。そして、第１の動きベクトルと第２の動きベクトルとから所定の判定基準（例えば（数式１）から（数式３））を用いて、動きベクトルの選択を行い、その選択した動きベクトルを初期値として再び動きベクトルの推定を行う。
【００５１】
すなわち、第１の動きベクトルでは、他の代表点の動きも考慮しながら、少しずつ動きベクトルの値を変えながら動き推定するため、誤った動きベクトルを推定する可能性が小さい動きベクトルを得ることができる。また、第２の動きベクトルでは、大きな動きに追従した動きベクトルを得ることができる。そして、第１と第２の動きベクトルを選択することにより、第１の動きベクトルの特性と、第２の動きベクトルの特性の長所を兼ね備えた動きベクトルを選択することができる。そして、この選択した動きベクトルを初期値として、再び反復型の動きベクトル推定を行うことにより、更に動きベクトルの精度を高めることができる。
【００５２】
このような動作により、本発明の動き推定方法および動画像符号化方法を用いることにより、隣接代表点と大きく異なる動きベクトルが求められる可能性が非常に小さくなり、かつ大きな動きに追従した動きベクトルを得ることができ、それにより領域中の画素の動きベクトルを正確に得ることができ、予測画像（動き補償画像）の画質の向上、すなわち符号化画像の画質の向上を図ることができる。
【００５３】
なお、本実施の形態においては、動き推定における参照ピクチャは既に符号化済みのピクチャを用いるとしたが、これは参照ピクチャの原画像を用いても良い。ただし、符号化においては、本実施の形態と同様に符号化済みのピクチャを用いる。
【００５４】
また、本実施の形態においては、本発明の動き推定方法を利用した例として、動画像符号化に適用する場合について説明したが、これは動画像符号化以外の処理、例えば画像処理等に適用しても良い。
また、本実施の形態においては、図２（ｂ）のように代表点の配置と領域の分割を行う場合を例として説明したが、代表点の配置方法と領域の分割方法は、他の方法であっても良い。他の方法の一例としては、例えば図４（ａ）、（ｂ）のような方法がある。また、領域の分割方法は、固定でなくても良く、例えば画像のエッジ情報を取得し、そのエッジに沿って領域を分割し、代表点を配置するような方法であっても良い。
【００５５】
また、本実施の形態においては、現ピクチャに対して代表点を設定し、その代表点と参照ピクチャとの動き量に基づいて、現ピクチャの領域中の各画素の動きを補間生成し、参照ピクチャから動き補償する場合について説明したが、これは、参照ピクチャに対して所定の代表点を設定し、その代表点と現ピクチャとの動き量に基づいて、現ピクチャの領域中の各画素の動きを補間生成し、参照ピクチャから動き補償する場合であっても良い。
【００５６】
また、本実施の形態においては、動きベクトル選択部５０６において動きベクトルの選択を行った後、その動きベクトルを初期値として、反復型動き推定部５０２で再び動き推定を行う場合について説明したが、これは、動きベクトル選択部５０６において選択した動きベクトルをそのまま用いて、動き補償を行っても良い。この場合には、動きベクトル選択部５０６において選択した動きベクトルが、そのまま予測画像生成部１０５と可変長符号化部１０７に対して出力され、この後第１の実施の形態と同様の処理により、符号化処理が行われることになる。この場合、動きベクトルの精度は若干悪くなるが、２回目の反復型動き推定部５０２の処理を行わないため、処理量を削減することができる。
【００５７】
また、本実施の形態においては、反復型動き推定部５０２で求めた動きベクトルと、ブロックマッチング型動き推定部５０６とで求めた、各代表点の２つの動きベクトルを評価基準により比較し、１つの動きベクトルを求める場合について説明したが、これはＮ（Ｎ≧２）種類の動き推定方法により、各代表点のＮ個の動きベクトルを評価基準により比較し、１つの動きベクトルを求めても良い。
【００５８】
（実施の形態３）
次に、本発明の動き推定方法の第２の実施の形態について、図７を用いて説明する。
図７は、本発明の動き推定方法を用いた動き推定部７０１のブロック図である。動き推定部７０１は、フレームメモリ７０２、７０４、動き検出部７０３、動きベクトル判定部７０５、動きベクトル補正部７０６から構成される。
本実施の形態では、動き推定方法についてのみ説明するが、動きベクトル推定部７０１は、第１の実施の形態、第２の実施の形態で説明した動画像符号化装置における動きベクトル推定部としても用いることができる。
【００５９】
フレームメモリ７０２には入力画像が入力され、現ピクチャが保持される。また、フレームメモリ７０４には、既に符号化済みの画像が参照ピクチャとして保持されているとする。
動き検出部７０３では、フレームメモリ７０２に保持された現ピクチャの画像データと、フレームメモリ７０４に保持された参照ピクチャの画像データとを用いて、現ピクチャの各代表点について、参照ピクチャに対する動き検出を行う。この動き検出の方法としては、第１の実施の形態における反復型動き推定部１０３や、第２の実施の形態における反復型動き推定部５０３、ブロックマッチング型動き推定部５０５、動きベクトル選択部５０６による動き検出方法等を用いることができる。
【００６０】
動き検出部７０３で検出された動きベクトルは、動きベクトル判定部７０５に対して出力される。
動きベクトル判定部７０５では、動き検出部７０３から入力された各代表点の動きベクトルに対して有効か無効かの判定を行う。
【００６１】
第１の判定方法を図６（ａ）と図８を用いて説明する。まず、ステップＳ８０１において、隣接する３つの代表点を抽出する。ここでは、３つの代表点が、図６（ａ）の代表点６０１ａ、６０２ａ、６０３ａであるとする。そして、ステップＳ８０２で、これらの代表点により形成される三角形６００ａの面積Ｌ１を求める。次にステップＳ８０３において、参照ピクチャ中で代表点に対応する対応点を抽出する。代表点６０１ａ、６０２ａ、６０３ａに対する動きベクトルが、それぞれ動きベクトル６１１、動きベクトル６１２、動きベクトル６１３であるとすると、参照ピクチャ中での対応点はそれぞれ対応点６０１ｂ、６０２ｂ、６０３ｂとなる。ステップＳ８０４では、これらの対応点により形成される三角形６００ｂの面積Ｌ２を計算する。そして、ステップＳ８０５において、このＬ１とＬ２の比、すなわち対応する三角形の面積比が所定の範囲Ｔ１〜Ｔ２に入っているかを判断する。例えば、Ｔ１、Ｔ２の値としては、それぞれ０．５、２．０といった値を用いればよい。ステップＳ８０５の条件を満たしていれば、これらの代表点は有効であり（ステップＳ８０７）、ステップＳ８０５の条件を満たしていなければ、これらの代表点は無効であると判断する（ステップＳ８０６）。
ここで、代表点が無効であると判断された場合、ある代表点が他の三角形の一部として同様の処理がなされ、その場合に有効であると判断された場合には、その代表点は有効と判断しても良い。
【００６２】
動きベクトル判定部７０５での第２の判定方法を図６（ｂ）と図９を用いて説明する。まず、ステップＳ９０１において、隣接する３つの代表点を抽出する。
ここでは、３つの代表点が、図６（ｂ）の代表点６２１ａ、６２２ａ、６２３ａであるとする。ステップＳ９０２において、参照ピクチャ中で代表点に対応する対応点を抽出する。代表点６２１ａ、６２２ａ、６２３ａに対する動きベクトルが、それぞれ動きベクトル６３１、動きベクトル６３２、動きベクトル６３３であるとすると、参照ピクチャ中での対応点はそれぞれ対応点６２１ｂ、６２２ｂ、６２３ｂとなる。ステップＳ９０３では、代表点と対応点の位置関係を調べる。ここでは、まず代表点に関して、６２１ａ→６２２ａ→６２３ａの順で三角形をどのように形成するかを判断する。この場合は、図６（ｂ）からわかるように、反時計回りに三角形を形成していることがわかる。次に、対応点に関して、対応する同じ順序、すなわち６２１ｂ→６２２ｂ→６２３ｂの順で三角形をどのように形成するかを判断する。この場合は、図６（ｂ）からわかるように、時計回りに三角形を形成していることがわかる。すなわち、代表点とその対応点とで位置関係が異なっていることがわかる。ステップＳ９０３の条件を満たしていれば、これらの代表点は有効であり（ステップＳ９０５）、ステップＳ９０３の条件を満たしていなければ、これらの代表点は無効であると判断する（ステップＳ９０４）。ここで、代表点が無効であると判断された場合、ある代表点が他の三角形の一部として同様の処理がなされ、その場合に有効であると判断された場合には、その代表点は有効と判断しても良い。
【００６３】
動きベクトル判定部７０５での第３の判定方法を図１０、図１１を用いて説明する。まず、ステップＳ１１０１で現ピクチャ中の代表点を選択する。今、選択した代表点が代表点１００１であるとする。次にステップＳ１１０２で、代表点１００１の動きベクトル１００４を用いて、代表点１００１の対応点１００２を特定する。ステップＳ１１０３では、参照ピクチャ中の対応点、すなわち対応点１００２、から現ピクチャに対して動き推定を行う。この動き検出の方法としては、第１の実施の形態における反復型動き推定部１０３や、第２の実施の形態における反復型動き推定部５０３、ブロックマッチング型動き推定部５０５、動きベクトル選択部５０６による動き検出方法等を用いることができる。ここでは、この動き推定により動きベクトル１００５が得られたとする。そして、ステップ１１０４では、参照ピクチャ中の対応点１００２に対する動きベクトル１００５を用いて、現ピクチャ中の対応点１００３を特定する。そして、ステップＳ１１０５において、現ピクチャ中の代表点１００１と対応点１００３との距離を計算し、この距離が閾値以下であるかどうかを判定する。ステップＳ１１０５の条件を満たしていれば、これらの代表点は有効であり（ステップＳ１１０７）、ステップＳ１１０５の条件を満たしていなければ、これらの代表点は無効であると判断する（ステップＳ１１０６）。
【００６４】
動きベクトル判定部７０５では、以上のような判定方法を用いて、各代表点が有効であるか無効であるかを判定する。ここで、判定方法は、上記の第１〜第３の判定方法のいずれかを用いてもよいし、これらを組み合わせて用いてもよい。
組み合わせて判定を行う場合、すべての判定結果が有効である代表点のみを有効としてもよいし、第１と第２の判定方法で無効とされても第３の判定方法で有効と判断されると有効とする、としてもよく、様々な組み合わせが可能である。
そして、動きベクトル判定部７０５で判定された各代表点に対する有効、無効の判定結果は、動きベクトル補正部７０６に対して出力される。
【００６５】
動きベクトル補正部７０６では、動きベクトル判定部７０５で無効と判断された代表点の動きベクトルに対して補正処理を施す。この補正処理の方法を図２（ａ）を用いて説明する。今、例えば代表点２０１の動きベクトルが無効であると判断されたとする。この場合、隣接する代表点の有効な動きベクトルから、代表点２０１の動きベクトルを補間生成し、また例えば、代表点２０２と代表点２０５の動きベクトルのみが有効であると判断されたとすると、代表点２０１の動きベクトルは代表点２０２と代表点２０５の動きベクトルの平均ベクトルで置き換え、という処理を行い、代表点２０１の動きベクトルを補間生成する。
【００６６】
動きベクトル補正部７０６において、以上のような処理により、すべての無効な代表点の動きベクトルが補間生成されると、全代表点の動きベクトルが出力される。
以上のように、本発明の動き推定方法および動画像符号化方法では、画像中に代表点を設定し、各代表点の動きベクトルを求める。そして、その代表点の動きベクトルが有効であるか、無効であるかを判定する。この判定方法としては例えば、隣接する代表点により形成される多角形の面積と、動きベクトルにより代表点に対応する対応点が形成する多角形の面積比が、所定の範囲内であれば有効であるとする方法や、隣接する代表点により形成される多角形内での各代表点の位置関係と、動きベクトルにより代表点に対応する対応点が形成する多角形内での各対応点の位置関係とが同じであれば有効であるとする方法や、代表点に対応する対応点から逆方向に動き推定を行い、それにより得られる対応点と元の代表点との距離が所定値以下であれば有効であると判定する方法があり、これらを単独であるいは組み合わせることにより、有効であるか無効であるかを判定する。そして、無効であると判定された代表点の動きベクトルは、有効である隣接する代表点の動きベクトルから補間生成する。
【００６７】
このような動作により、本発明の動き推定方法および動画像符号化方法を用いることにより、代表点の動きベクトルが有効であるか、無効であるかを確実に判断することができる。例えば、代表点が無効であるのは、明らかに動き推定が間違っている場合や、隠れなどによって実際には動き推定ができない場合等であり、これらの場合を確実に検出することができる。そして、無効であると判定した動きベクトルを周辺の代表点の動きベクトルから補間生成することにより、予測画像（動き補償画像）の画質の向上、すなわち符号化画像の画質の向上を図ることができる。
【００６８】
なお、本実施の形態においては、動き推定における参照ピクチャは既に符号化済みのピクチャを用いるとしたが、これは参照ピクチャの原画像を用いても良い。ただし、符号化においては、本実施の形態と同様に符号化済みのピクチャを用いる。
【００６９】
また、本実施の形態においては、本発明の動き推定方法を利用した例として、動画像符号化に適用する場合について説明したが、これは動画像符号化以外の処理、例えば画像処理等に適用しても良い。
また、本実施の形態においては、図２（ｂ）のように代表点の配置と領域の分割を行う場合を例として説明したが、代表点の配置方法と領域の分割方法は、他の方法であっても良い。他の方法の一例としては、例えば図４（ａ）、（ｂ）のような方法がある。また、領域の分割方法は、固定でなくても良く、例えば画像のエッジ情報を取得し、そのエッジに沿って領域を分割し、代表点を配置するような方法であっても良い。
【００７０】
また、本実施の形態においては、現ピクチャに対して代表点を設定し、その代表点の参照ピクチャに対する動き量を求める場合について説明したが、これは、参照ピクチャに対して所定の代表点を設定し、その代表点の現ピクチャに対する動き量を求める場合であっても良い。
【００７１】
（実施の形態４）
さらに、上記各実施の形態で示した動き推定方法および動画像符号化方法を実現するためのプログラムを、フレキシブルディスク等の記録媒体に記録するようにすることにより、上記各実施の形態で示した処理を、独立したコンピュータシステムにおいて簡単に実施することが可能となる。
【００７２】
図１２は、上記各実施の形態の動き推定方法および動画像符号化方法を、フレキシブルディスク等の記録媒体に記録されたプログラムを用いて、コンピュータシステムにより実施する場合の説明図である。
図１２（ｂ）  は、フレキシブルディスクの正面からみた外観、断面構造、及びフレキシブルディスクを示し、図１２  （ａ）  は、記録媒体本体であるフレキシブルディスクの物理フォーマットの例を示している。フレキシブルディスクＦＤはケースＦ内に内蔵され、該ディスクの表面には、同心円状に外周からは内周に向かって複数のトラックＴｒが形成され、各トラックは角度方向に１６のセクタＳｅに分割されている。従って、上記プログラムを格納したフレキシブルディスクでは、上記フレキシブルディスクＦＤ上に割り当てられた領域に、上記プログラムが記録されている。
【００７３】
また、図１２（ｃ）  は、フレキシブルディスクＦＤに上記プログラムの記録再生を行うための構成を示す。動き推定方法および動画像符号化方法を実現する上記プログラムをフレキシブルディスクＦＤに記録する場合は、コンピュータシステムＣｓから上記プログラムをフレキシブルディスクドライブを介して書き込む。また、フレキシブルディスク内のプログラムにより動き推定方法および動画像符号化方法を実現する上記動き推定方法および動画像符号化方法をコンピュータシステム中に構築する場合は、フレキシブルディスクドライブによりプログラムをフレキシブルディスクから読み出し、コンピュータシステムに転送する。
【００７４】
なお、上記説明では、記録媒体としてフレキシブルディスクを用いて説明を行ったが、光ディスクを用いても同様に行うことができる。また、記録媒体はこれに限らず、ＩＣカード、ＲＯＭカセット等、プログラムを記録できるものであれば同様に実施することができる。
【００７５】
（実施の形態５）
さらにここで、上記実施の形態で示した動き推定方法および動画像符号化方法の応用例とそれを用いたシステムを説明する。
図１３は、コンテンツ配信サービスを実現するコンテンツ供給システムｅｘ１００の全体構成を示すブロック図である。通信サービスの提供エリアを所望の大きさに分割し、各セル内にそれぞれ固定無線局である基地局ｅｘ１０７〜ｅｘ１１０が設置されている。
【００７６】
このコンテンツ供給システムｅｘ１００は、例えば、インターネットｅｘ１０１にインターネットサービスプロバイダｅｘ１０２および電話網ｅｘ１０４、および基地局ｅｘ１０７〜ｅｘ１１０を介して、コンピュータｅｘ１１１、ＰＤＡ（ｐｅｒｓｏｎａｌ  ｄｉｇｉｔａｌ  ａｓｓｉｓｔａｎｔ）ｅｘ１１２、カメラｅｘ１１３、携帯電話ｅｘ１１４、カメラ付きの携帯電話ｅｘ１１５などの各機器が接続される。
【００７７】
しかし、コンテンツ供給システムｅｘ１００は図１３のような組合せに限定されず、いずれかを組み合わせて接続するようにしてもよい。また、固定無線局である基地局ｅｘ１０７〜ｅｘ１１０を介さずに、各機器が電話網ｅｘ１０４に直接接続されてもよい。
【００７８】
カメラｅｘ１１３はデジタルビデオカメラ等の動画撮影が可能な機器である。また、携帯電話は、ＰＤＣ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）方式、ＣＤＭＡ（Ｃｏｄｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）方式、Ｗ−ＣＤＭＡ（Ｗｉｄｅｂａｎｄ−Ｃｏｄｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）方式、若しくはＧＳＭ（Ｇｌｏｂａｌ  Ｓｙｓｔｅｍ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）方式の携帯電話機、またはＰＨＳ（Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙｐｈｏｎｅ  Ｓｙｓｔｅｍ）等であり、いずれでも構わない。
【００７９】
また、ストリーミングサーバｅｘ１０３は、カメラｅｘ１１３から基地局ｅｘ１０９、電話網ｅｘ１０４を通じて接続されており、カメラｅｘ１１３を用いてユーザが送信する符号化処理されたデータに基づいたライブ配信等が可能になる。撮影したデータの符号化処理はカメラｅｘ１１３で行っても、データの送信処理をするサーバ等で行ってもよい。また、カメラｅｘ１１６で撮影した動画データはコンピュータｅｘ１１１を介してストリーミングサーバｅｘ１０３に送信されてもよい。カメラｅｘ１１６はデジタルカメラ等の静止画、動画が撮影可能な機器である。この場合、動画データの符号化はカメラｅｘ１１６で行ってもコンピュータｅｘ１１１で行ってもどちらでもよい。また、符号化処理はコンピュータｅｘ１１１やカメラｅｘ１１６が有するＬＳＩｅｘ１１７において処理することになる。なお、画像符号化・復号化用のソフトウェアをコンピュータｅｘ１１１等で読み取り可能な記録媒体である何らかの蓄積メディア（ＣＤ−ＲＯＭ、フレキシブルディスク、ハードディスクなど）に組み込んでもよい。さらに、カメラ付きの携帯電話ｅｘ１１５で動画データを送信してもよい。このときの動画データは携帯電話ｅｘ１１５が有するＬＳＩで符号化処理されたデータである。
【００８０】
このコンテンツ供給システムｅｘ１００では、ユーザがカメラｅｘ１１３、カメラｅｘ１１６等で撮影しているコンテンツ（例えば、音楽ライブを撮影した映像等）を上記実施の形態同様に符号化処理してストリーミングサーバｅｘ１０３に送信する一方で、ストリーミングサーバｅｘ１０３は要求のあったクライアントに対して上記コンテンツデータをストリーム配信する。クライアントとしては、上記符号化処理されたデータを復号化することが可能な、コンピュータｅｘ１１１、ＰＤＡｅｘ１１２、カメラｅｘ１１３、携帯電話ｅｘ１１４等がある。このようにすることでコンテンツ供給システムｅｘ１００は、符号化されたデータをクライアントにおいて受信して再生することができ、さらにクライアントにおいてリアルタイムで受信して復号化し、再生することにより、個人放送をも実現可能になるシステムである。
【００８１】
このシステムを構成する各機器の符号化、復号化には上記各実施の形態で示した画像符号化装置あるいは画像復号化装置を用いるようにすればよい。
その一例として携帯電話について説明する。
図１４は、上記実施の形態で説明した動き推定方法および動画像符号化方法を用いた携帯電話ｅｘ１１５を示す図である。携帯電話ｅｘ１１５は、基地局ｅｘ１１０との間で電波を送受信するためのアンテナｅｘ２０１、ＣＣＤカメラ等の映像、静止画を撮ることが可能なカメラ部ｅｘ２０３、カメラ部ｅｘ２０３で撮影した映像、アンテナｅｘ２０１で受信した映像等が復号化されたデータを表示する液晶ディスプレイ等の表示部ｅｘ２０２、操作キーｅｘ２０４群から構成される本体部、音声出力をするためのスピーカ等の音声出力部ｅｘ２０８、音声入力をするためのマイク等の音声入力部ｅｘ２０５、撮影した動画もしくは静止画のデータ、受信したメールのデータ、動画のデータもしくは静止画のデータ等、符号化されたデータまたは復号化されたデータを保存するための記録メディアｅｘ２０７、携帯電話ｅｘ１１５に記録メディアｅｘ２０７を装着可能とするためのスロット部ｅｘ２０６を有している。記録メディアｅｘ２０７はＳＤカード等のプラスチックケース内に電気的に書換えや消去が可能な不揮発性メモリであるＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）の一種であるフラッシュメモリ素子を格納したものである。
【００８２】
さらに、携帯電話ｅｘ１１５について図１４を用いて説明する。携帯電話ｅｘ１１５は表示部ｅｘ２０２及び操作キーｅｘ２０４を備えた本体部の各部を統括的に制御するようになされた主制御部ｅｘ３１１に対して、電源回路部ｅｘ３１０、操作入力制御部ｅｘ３０４、画像符号化部ｅｘ３１２、カメラインターフェース部ｅｘ３０３、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）制御部ｅｘ３０２、画像復号化部ｅｘ３０９、多重分離部ｅｘ３０８、記録再生部ｅｘ３０７、変復調回路部ｅｘ３０６及び音声処理部ｅｘ３０５が同期バスｅｘ３１３を介して互いに接続されている。
【００８３】
電源回路部ｅｘ３１０は、ユーザの操作により終話及び電源キーがオン状態にされると、バッテリパックから各部に対して電力を供給することによりカメラ付ディジタル携帯電話ｅｘ１１５を動作可能な状態に起動する。
携帯電話ｅｘ１１５は、ＣＰＵ、ＲＯＭ及びＲＡＭ等でなる主制御部ｅｘ３１１の制御に基づいて、音声通話モード時に音声入力部ｅｘ２０５で集音した音声信号を音声処理部ｅｘ３０５によってディジタル音声データに変換し、これを変復調回路部ｅｘ３０６でスペクトラム拡散処理し、送受信回路部ｅｘ３０１でディジタルアナログ変換処理及び周波数変換処理を施した後にアンテナｅｘ２０１を介して送信する。また携帯電話機ｅｘ１１５は、音声通話モード時にアンテナｅｘ２０１で受信した受信データを増幅して周波数変換処理及びアナログディジタル変換処理を施し、変復調回路部ｅｘ３０６でスペクトラム逆拡散処理し、音声処理部ｅｘ３０５によってアナログ音声データに変換した後、これを音声出力部ｅｘ２０８を介して出力する。
【００８４】
さらに、データ通信モード時に電子メールを送信する場合、本体部の操作キーｅｘ２０４の操作によって入力された電子メールのテキストデータは操作入力制御部ｅｘ３０４を介して主制御部ｅｘ３１１に送出される。主制御部ｅｘ３１１は、テキストデータを変復調回路部ｅｘ３０６でスペクトラム拡散処理し、送受信回路部ｅｘ３０１でディジタルアナログ変換処理及び周波数変換処理を施した後にアンテナｅｘ２０１を介して基地局ｅｘ１１０へ送信する。
【００８５】
データ通信モード時に画像データを送信する場合、カメラ部ｅｘ２０３で撮像された画像データをカメラインターフェース部ｅｘ３０３を介して画像符号化部ｅｘ３１２に供給する。また、画像データを送信しない場合には、カメラ部ｅｘ２０３で撮像した画像データをカメラインターフェース部ｅｘ３０３及びＬＣＤ制御部ｅｘ３０２を介して表示部ｅｘ２０２に直接表示することも可能である。
【００８６】
画像符号化部ｅｘ３１２は、本願発明で説明した画像符号化装置を備えた構成であり、カメラ部ｅｘ２０３から供給された画像データを上記実施の形態で示した画像符号化装置に用いた符号化方法によって圧縮符号化することにより符号化画像データに変換し、これを多重分離部ｅｘ３０８に送出する。また、このとき同時に携帯電話機ｅｘ１１５は、カメラ部ｅｘ２０３で撮像中に音声入力部ｅｘ２０５で集音した音声を音声処理部ｅｘ３０５を介してディジタルの音声データとして多重分離部ｅｘ３０８に送出する。
【００８７】
多重分離部ｅｘ３０８は、画像符号化部ｅｘ３１２から供給された符号化画像データと音声処理部ｅｘ３０５から供給された音声データとを所定の方式で多重化し、その結果得られる多重化データを変復調回路部ｅｘ３０６でスペクトラム拡散処理し、送受信回路部ｅｘ３０１でディジタルアナログ変換処理及び周波数変換処理を施した後にアンテナｅｘ２０１を介して送信する。
【００８８】
データ通信モード時にホームページ等にリンクされた動画像ファイルのデータを受信する場合、アンテナｅｘ２０１を介して基地局ｅｘ１１０から受信した受信データを変復調回路部ｅｘ３０６でスペクトラム逆拡散処理し、その結果得られる多重化データを多重分離部ｅｘ３０８に送出する。
【００８９】
また、アンテナｅｘ２０１を介して受信された多重化データを復号化するには、多重分離部ｅｘ３０８は、多重化データを分離することにより画像データのビットストリームと音声データのビットストリームとに分け、同期バスｅｘ３１３を介して当該符号化画像データを画像復号化部ｅｘ３０９に供給すると共に当該音声データを音声処理部ｅｘ３０５に供給する。
【００９０】
次に、画像復号化部ｅｘ３０９は、本願発明で説明した画像復号化装置を備えた構成であり、画像データのビットストリームを上記実施の形態で示した符号化方法に対応した復号化方法で復号することにより再生動画像データを生成し、これをＬＣＤ制御部ｅｘ３０２を介して表示部ｅｘ２０２に供給し、これにより、例えばホームページにリンクされた動画像ファイルに含まれる動画データが表示される。このとき同時に音声処理部ｅｘ３０５は、音声データをアナログ音声データに変換した後、これを音声出力部ｅｘ２０８に供給し、これにより、例えばホームページにリンクされた動画像ファイルに含まる音声データが再生される。
【００９１】
なお、上記システムの例に限られず、最近は衛星、地上波によるディジタル放送が話題となっており、図１６に示すようにディジタル放送用システムにも上記実施の形態の少なくとも画像符号化装置または画像復号化装置のいずれかを組み込むことができる。具体的には、放送局ｅｘ４０９では映像情報のビットストリームが電波を介して通信または放送衛星ｅｘ４１０に伝送される。これを受けた放送衛星ｅｘ４１０は、放送用の電波を発信し、この電波を衛星放送受信設備をもつ家庭のアンテナｅｘ４０６で受信し、テレビ（受信機）ｅｘ４０１またはセットトップボックス（ＳＴＢ）ｅｘ４０７などの装置によりビットストリームを復号化してこれを再生する。また、記録媒体であるＣＤやＤＶＤ等の蓄積メディアｅｘ４０２に記録したビットストリームを読み取り、復号化する再生装置ｅｘ４０３にも上記実施の形態で示した画像復号化装置を実装することが可能である。この場合、再生された映像信号はモニタｅｘ４０４に表示される。また、ケーブルテレビ用のケーブルｅｘ４０５または衛星／地上波放送のアンテナｅｘ４０６に接続されたセットトップボックスｅｘ４０７内に画像復号化装置を実装し、これをテレビのモニタｅｘ４０８で再生する構成も考えられる。このときセットトップボックスではなく、テレビ内に画像復号化装置を組み込んでも良い。また、アンテナｅｘ４１１を有する車ｅｘ４１２で衛星ｅｘ４１０からまたは基地局ｅｘ１０７等から信号を受信し、車ｅｘ４１２が有するカーナビゲーションｅｘ４１３等の表示装置に動画を再生することも可能である。
【００９２】
更に、画像信号を上記実施の形態で示した画像符号化装置で符号化し、記録媒体に記録することもできる。具体例としては、ＤＶＤディスクｅｘ４２１に画像信号を記録するＤＶＤレコーダや、ハードディスクに記録するディスクレコーダなどのレコーダｅｘ４２０がある。更にＳＤカードｅｘ４２２に記録することもできる。レコーダｅｘ４２０が上記実施の形態で示した画像復号化装置を備えていれば、ＤＶＤディスクｅｘ４２１やＳＤカードｅｘ４２２に記録した画像信号を再生し、モニタｅｘ４０８で表示することができる。
【００９３】
なお、カーナビゲーションｅｘ４１３の構成は例えば図１５に示す構成のうち、カメラ部ｅｘ２０３とカメラインターフェース部ｅｘ３０３、画像符号化部ｅｘ３１２を除いた構成が考えられ、同様なことがコンピュータｅｘ１１１やテレビ（受信機）ｅｘ４０１等でも考えられる。
【００９４】
また、上記携帯電話ｅｘ１１４等の端末は、符号化器・復号化器を両方持つ送受信型の端末の他に、符号化器のみの送信端末、復号化器のみの受信端末の３通りの実装形式が考えられる。
このように、上記実施の形態で示した動き推定方法および動画像符号化方法を上述したいずれの機器・システムに用いることは可能であり、そうすることで、上記実施の形態で説明した効果を得ることができる。
【００９５】
また、本発明はかかる上記実施形態に限定されるものではなく、本発明の範囲を逸脱することなく種々の変形または修正が可能である。
【００９６】
【発明の効果】
以上の様に、本発明の動き推定方法および動画像符号化方法の第１の発明では、画像中に代表点を設定し、各代表点の動きベクトルを求める際に、小さな探索範囲を設定し、（数式１）で示す評価関数値が最小となる位置を指す動きベクトルに更新する。この処理を動きベクトルが更新される代表点の個数が所定値以下となるまで繰り返し、最終的な動きベクトルを決定する。ここで、評価関数は、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離の指標と、注目代表点の動きベクトルとその隣接代表点との動きベクトルの距離の指標の重み付け和である。
【００９７】
したがって、本発明の動き推定方法および動画像符号化方法の第１の発明を用いることにより、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離が小さく、かつ隣接代表点の動きベクトルとの距離も小さい動きベクトルを得ることができる。すなわち、他の代表点の動きも考慮することができるため、誤った動きベクトルを推定する可能性が小さくなり、これにより隣接代表点と大きく異なる動きベクトルが求められる可能性が非常に小さくなり、領域中の画素の動きベクトルを正確に得ることができるため、例えば第２の従来方法等と比較して、予測画像（動き補償画像）の画質の向上、すなわち符号化画像の画質の向上を図ることができる。また、例えば第１の従来方法と比較すると、動き推定の際に領域内の画素毎の動きベクトル（変換パラメータ）を求める必要がないため、処理量の大幅な削減を行うことができる。
【００９８】
また、本発明の動き推定方法および動画像符号化方法の第２の発明では、画像中に代表点を設定し、各代表点の動きベクトルを求める際に、小さな探索範囲を設定し、（数式１）で示す評価関数値が最小となる位置を指す動きベクトルに更新する。この処理を動きベクトルが更新される代表点の個数が所定値以下となるまで繰り返し、第１の動きベクトルを決定する。ここで、評価関数は、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離の指標と、注目代表点の動きベクトルとその隣接代表点との動きベクトルの距離の指標の重み付け和である。したがって、現ピクチャの画素ブロックと、参照ピクチャの画素ブロックの画素値で求めた距離が小さく、かつ隣接代表点の動きベクトルとの距離も小さい動きベクトルを得ることができる。次に、従来のブロックマッチング法を用いて、各代表点の第２の動きベクトルを用いる。そして、第１の動きベクトルと第２の動きベクトルとから所定の判定基準（例えば（数式１）から（数式３））を用いて、動きベクトルの選択を行い、その選択した動きベクトルを初期値として再び動きベクトルの推定を行う。すなわち、第１の動きベクトルでは、他の代表点の動きも考慮しながら、少しずつ動きベクトルの値を変えながら動き推定するため、誤った動きベクトルを推定する可能性が小さい動きベクトルを得ることができる。また、第２の動きベクトルでは、大きな動きに追従した動きベクトルを得ることができる。そして、第１と第２の動きベクトルを選択することにより、第１の動きベクトルの特性と、第２の動きベクトルの特性の長所を兼ね備えた動きベクトルを選択することができる。そして、この選択した動きベクトルを初期値として、再び反復型の動きベクトル推定を行うことにより、更に動きベクトルの精度を高めることができる。
【００９９】
このような動作により、本発明の動き推定方法および動画像符号化方法の第２の発明を用いることにより、隣接代表点と大きく異なる動きベクトルが求められる可能性が非常に小さくなり、かつ大きな動きに追従した動きベクトルを得ることができ、それにより領域中の画素の動きベクトルを正確に得ることができ、予測画像（動き補償画像）の画質の向上、すなわち符号化画像の画質の向上を図ることができる。
【０１００】
また、本発明の動き推定方法および動画像符号化方法の第３の発明では、画像中に代表点を設定し、各代表点の動きベクトルを求める。そして、その代表点の動きベクトルが有効であるか、無効であるかを判定する。この判定方法としては例えば、隣接する代表点により形成される多角形の面積と、動きベクトルにより代表点に対応する対応点が形成する多角形の面積比が、所定の範囲内であれば有効であるとする方法や、隣接する代表点により形成される多角形内での各代表点の位置関係と、動きベクトルにより代表点に対応する対応点が形成する多角形内での各対応点の位置関係とが同じであれば有効であるとする方法や、代表点に対応する対応点から逆方向に動き推定を行い、それにより得られる対応点と元の代表点との距離が所定値以下であれば有効であると判定する方法があり、これらを単独であるいは組み合わせることにより、有効であるか無効であるかを判定する。そして、無効であると判定された代表点の動きベクトルは、有効である隣接する代表点の動きベクトルから補間生成する。
【０１０１】
このような動作により、本発明の動き推定方法および動画像符号化方法の第３の発明を用いることにより、代表点の動きベクトルが有効であるか、無効であるかを確実に判断することができる。例えば、代表点が無効であるのは、明らかに動き推定が間違っている場合や、隠れなどによって実際には動き推定ができない場合等であり、これらの場合を確実に検出することができる。そして、無効であると判定した動きベクトルを周辺の代表点の動きベクトルから補間生成することにより、予測画像（動き補償画像）の画質の向上、すなわち符号化画像の画質の向上を図ることができる。
【０１０２】
以上のように、本発明の動き推定方法および動画像符号化方法はその実用的価値が高い。
【図面の簡単な説明】
【図１】本発明の動き検出方法を用いた動画像符号化装置ブロック図（実施の形態１）
【図２】本発明の動き推定方法を説明するための模式図（実施の形態１）
【図３】本発明の動き推定方法を説明するためのフローチャート（実施の形態１）
【図４】本発明の動き推定方法を説明するための模式図（実施の形態１）
【図５】本発明の動き検出方法を用いた動画像符号化装置のブロック図（実施の形態２）
【図６】本発明の動き検出方法を説明するための模式図（実施の形態３）
【図７】本発明の動き検出方法を用いた動画像符号化装置のブロック図（実施の形態３）
【図８】本発明の動き推定方法を説明するためのフローチャート（実施の形態３）
【図９】本発明の動き推定方法を説明するためのフローチャート（実施の形態３）
【図１０】本発明の動き検出方法を説明するための模式図（実施の形態３）
【図１１】本発明の動き推定方法を説明するためのフローチャート（実施の形態３）
【図１２】上記各実施の形態の動き推定方法および動画像符号化方法をコンピュータシステムにより実現するためのプログラムを格納するための記録媒体についての説明図（実施の形態４）
【図１３】コンテンツ供給システムの全体構成を示すブロック図（実施の形態５）
【図１４】動き推定方法および動画像符号化方法を用いた携帯電話の例（実施の形態５）
【図１５】携帯電話のブロック図（実施の形態５）
【図１６】ディジタル放送用システムの例（実施の形態５）
【符号の説明】
１０１  動き推定部
１０２、１０４  フレームメモリ
１０３  反復型動き推定部
１０５  予測画像生成部
１０６  予測誤差符号化部
１０７  可変長符号化部
１０８  予測誤差復号化部
【図１】
2004364064.tif 000006
【図２】
2004364064.tif 000007
【図３】
2004364064.tif 000008
【図４】
2004364064.tif 000009
【図５】
2004364064.tif 000010
【図６】
2004364064.tif 000011
【図７】
2004364064.tif 000012
【図８】
2004364064.tif 000013
【図９】
2004364064.tif 000014
【図１０】
2004364064.tif 000015
【図１１】
2004364064.tif 000016
【図１２】
2004364064.tif 000017
【図１３】
2004364064.tif 000018
【図１４】
2004364064.tif 000019
【図１５】
2004364064.tif 000020
【図１６】
2004364064.tif 000021