(57)【特許請求の範囲】
【請求項１】
ビデオデータを動き補償符号化するためのビデオエンコーダであって、
基準フレームに基づき符号化すべき現在フレームの第１の画像セグメントＳｋの第１の動きベクトルを生成する手段と、
ｆｉ（ｘ，ｙ）が基底関数であり、ｉが個々の基底関数及び絶対動き係数ｃｉ間の対応を定義するインデックスである場合に、ｃｉ・ｆｉ（ｘ，ｙ）が前記第１の動きベクトルの近似値を表すように、前記第１の動きベクトルを符号化し、前記絶対動き係数ｃｉを要素とする第１の動き係数ベクトルｃｋを含む、圧縮された動き情報を提供する動き場エンコーダと、
前記基準フレームに基づき続いて符号化すべき前記現在フレームの第２の画像セグメントＳｌの第２の動きベクトルを生成する手段と、
ｆｊ（ｘ，ｙ）が基底関数であり、ｊが個々の基底関数及び絶対動き係数ｃｊ間の対応を定義するインデックスである場合に、ｃｊ・ｆｊ（ｘ，ｙ）が前記第２の画像セグメントＳｌの前記第２の動きベクトルの近似値を表すように、前記第２の動きベクトルを符号化し、前記絶対動き係数ｃｊを要素とする第２の動き係数ベクトルｃｌを含む、圧縮された動き情報を提供する手段と、
以前に生成された前記第１の動き係数ベクトルｃｋに基づき予測動き係数ｐｊを含む前記第２の画像セグメントＳｌの予測動き係数ベクトルｐｌを予測する手段とを含み、前記ビデオエンコーダは、
細分動き係数ｒｊの各々が前記絶対動き係数ｃｊの１つとこれと対応する予測動き係数ｐｊとの間の差を表す時、第２の絶対動き係数ｃｊの各々を前記対応する予測動き係数ｐｊ及び前記細分動き係数ｒｊの合計として表す手段と、
前記細分動き係数ｒｊの値を決定する手段と、
前記第２の画像セグメントＳｌの前記第２の動き係数ベクトルｃｌを前記細分動き係数ｒｊのベクトルとして表す手段とをさらに含む、ビデオエンコーダ。
【請求項２】
請求項１に記載のビデオエンコーダにおいて、
前記各動きベクトルが１つの擬似動きモデルによって表現される、ビデオエンコーダ。
【請求項３】
請求項１または２に記載のビデオエンコーダにおいて、
前記絶対動き係数、前記細分動き係数及び前記予測動き係数と前記対応する基底関数は、１つの擬似動きモデルを表す、ビデオエンコーダ。
【請求項４】
請求項１乃至３の何れかに記載のビデオエンコーダにおいて、
第１の画像歪み量と、前記第１の画像の歪み量を有するセグメントＳｌを表すのに必要な第１の情報量とを示し、動き係数の第１の選択に対応する第１のコスト（Ｌ（Ｓｌ））を計算する手段と、
第２の画像歪み量と、前記第２の画像の歪み量を有する前記セグメントＳｌを表すのに必要な第２の情報量とを示し、前記第１の選択とは異なる動き係数の第２の選択に対応する第２のコスト（Ｌ（Ｓｌ））を計算する手段と、
前記第１及び前記第２のコストの中から予め定められた最大コストより小さく、かつそれにより接近している方を選択する手段と、
前記選択したコストに対応する動き係数ｃｊを計算する手段とをさらに備える、ビデオエンコーダ。
【請求項５】
請求項１乃至４の何れかに記載のビデオエンコーダにおいて、
前記第２の画像セグメントＳｌの行列Ｅｌ及びベクトルｙｌを計算する手段と、
前記第２の絶対動き係数ｃｊを含む前記第２の動きベクトルをｃｌとすると、前記第２の画像セグメントの予め定義された歪み測度を関数Ｅｌｃｌ−ｙｌとして計算する手段と、
前記行列Ｅｌ及びベクトルｙｌから対角行列Ｒｌ及び対応するベクトルｚｌ０を生成する手段とをさらに備える、ビデオエンコーダ。
【請求項６】
請求項５に記載のビデオエンコーダにおいて、
行列Ａｌ＝ＥｌTＥｌを下位の対角行列ＲｌTとその転置行列Ｒｌとに分解し、Ａｉ＝ＲｌTＲｌとなるように前記行列Ｒｌを取得する手段をさらに備える、ビデオエンコーダ。
【請求項７】
請求項５または６に記載のビデオエンコーダにおいて、
ｄｌ＝ＥｌTｙｌを計算して前記式ＲｌTｚｌ０＝ｄｌを解くことによってベクトルｚｌ０を取得する手段をさらに備える、ビデオエンコーダ。
【請求項８】
請求項５乃至７の何れかに記載のビデオエンコーダにおいて、
出力ベクトルｚｌ＝ｚｌ０−Ｒｌｐｌを計算する手段をさらに備える、ビデオエンコーダ。
【請求項９】
請求項１乃至８の何れかに記載のビデオエンコーダを備える記憶装置。
【請求項１０】
請求項１乃至８の何れかに記載のビデオエンコーダを備える移動局。
【請求項１１】
請求項１乃至８の何れかに記載のビデオエンコーダを備える移動電気通信システム。
【請求項１２】
プロセッサを、請求項１乃至８の何れかに記載のビデオエンコーダとして動作させるプログラムコードを含む、コンピュータ読み取り可能な記録媒体。
【請求項１３】
ビデオデータの動き補償符号化方法であって、
基準フレームに基づき符号化すべき現在フレームの第１の画像セグメントＳｋの第１の動きベクトルを生成するステップと、
ｆｉ（ｘ，ｙ）が基底関数であり、ｉが個々の基底関数及び絶対動き係数ｃｉ間の対応を定義するインデックスである場合に、ｃｉ・ｆｉ（ｘ，ｙ）が前記第１の動きベクトルの近似値を表すように、前記第１の動きベクトルを符号化し、前記絶対動き係数ｃｉを要素とする第１の動き係数ベクトルｃｋを含む、圧縮された動き情報を提供するステップと、
前記基準フレームに基づき続いて符号化すべき前記現在フレームの第２の画像セグメントＳｌの第２の動きベクトルを生成するステップと、
ｆｊ（ｘ，ｙ）が基底関数であり、ｊが個々の基底関数及び絶対動き係数ｃｊ間の対応を定義するインデックスである場合に、ｃｊ・ｆｊ（ｘ，ｙ）が前記第２の画像セグメントＳｌの前記第２の動きベクトルの近似値を表すように、前記第２の動きベクトルを符号化し、前記絶対動き係数ｃｊを要素とする第２の動き係数ベクトルｃｌを含む、圧縮された動き情報を提供するステップと、
前記第１の動き係数ベクトルｃｋに基づき予測動き係数ｐｊを含む前記第２の画像セグメントＳｌの予測動き係数ベクトルｐｌを予測するステップとを含み、前記方法は、
細分動き係数ｒｊの各々が前記絶対動き係数ｃｊの１つとこれと対応する予測動き係数ｐｊとの間の差を表す時、第２の絶対動き係数ｃｊの各々を前記対応する予測動き係数ｐｊ及び前記細分動き係数ｒｊの合計として表すステップと、
前記細分動き係数ｒｊの値を決定するステップと、
前記第２の動き係数ベクトルｃｌを前記細分動き係数ｒｊのベクトルとして表すステップとをさらに含む、方法。
【請求項１４】
請求項１３に記載の方法において、
前記各動きベクトルが１つの擬似動きモデルによって表現される、方法。
【請求項１５】
請求項１３または１４に記載の方法において、
前記絶対動き係数、前記細分動き係数及び前記予測動き係数と対応する前記基底関数は、１つの擬似動きモデルを表す、方法。
【請求項１６】
請求項１３乃至１５の何れかに記載の方法において、
第１の画像歪み量と、前記第１の画像の歪み量を有するセグメントＳｌを表すのに必要な第１の情報量とを示し、動き係数の第１の選択に対応する第１のコスト（Ｌ（Ｓｌ））を計算するステップと、
第２の画像歪み量と、前記第２の画像の歪み量を有する前記セグメントＳｌを表すのに必要な第２の情報量とを示し、前記第１の選択とは異なる動き係数の第２の選択に対応する第２のコスト（Ｌ（Ｓｌ））を計算するステップと、
第１及び第２のコストの中から予め定められた最大コストより小さく、かつそれにより接近している方を選択するステップと、
前記選択したコストに対応する動き係数ｃｊを計算するステップとをさらに含む、方法。
【請求項１７】
請求項１３乃至１６の何れかに記載の方法において、
前記第２の画像セグメントＳｌの行列Ｅｌ及びベクトルｙｌを計算するステップと、
前記第２の絶対動き係数ｃｊを含む前記第２の動きベクトルをｃｌとすると、前記第２の画像セグメントの予め定義された歪み測度を関数Ｅｌｃｌ−ｙｌとして計算するステップと、
前記行列Ｅｌ及びベクトルｙｌから対角行列Ｒｌ及び対応するベクトルｚｌ０を生成するステップとをさらに含む、方法。
【請求項１８】
請求項１７に記載の方法において、
行列Ａｌ＝ＥｌTＥｌを下位の対角行列ＲｌTとその転置行列Ｒｌとに分解し、Ａｉ＝ＲｌTＲｌとなるように前記行列Ｒｌを取得するステップをさらに含む、方法。
【請求項１９】
請求項１７または１８に記載の方法において、
ｄｌ＝ＥｌTｙｌを計算して前記式ＲｌTｚｌ０＝ｄｌを解くことによってベクトルｚｌ０を取得するステップをさらに含む、方法。
【請求項２０】
請求項１７乃至１９の何れかに記載の方法において、
出力ベクトルｚｌ＝ｚｌ０−Ｒｌｐｌを計算するステップをさらに含む、方法。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は画像圧縮に係り、特に、推定動き場の符号化と、ビデオシーケンスに動き情報を生成することに関するものである。
【０００２】
（発明の背景）
動き補償予測は、大部分の画像符号化方式の主要な要素である。動き補償予測の動作を説明するには、各デジタル画像が、その画像の一定の部分に対応して一定のピクセルの組を含むことを理解する必要がある。各ピクセルは、例えば、赤、緑及び青の強度（RGBカラーシステム）か、輝度及び２つの色信号の強度として表される。
【０００３】
図１には、実例として、１つの画像の２つのセグメントＳｋ及びＳｌが示されており、各セグメントの１０から１５は、連続する画像の前の画像におけるピクセル位置を示す。現在画像におけるこれらのピクセルの新位置は、符号１０’から１５’で示される。このピクセル位置の変化、すなわち動きは、これらセグメント内のピクセルの動きベクトルｖ１ｋからｖ３ｋ、及びｖ１ｌからｖ３ｌを定義する。最も単純な場合、セグメントは正方形または長方形である。または、従来のように、図1に示すような任意の形でも良い。
【０００４】
図２は、動き補償を用いて画像シーケンスを圧縮するエンコーダの概略図である。このエンコーダの必須要素は、動き補償予測ブロック１、動き場推定ブロック２、及び動き場コーダ３である。動き補償ビデオコーダの動作原理は、現在フレームと称される符号化された着信フレームｌｎ（ｘ，ｙ）と予測フレームｌ^ｎ（ｘ，ｙ）との間の差異である予測誤差Ｅｎ（ｘ，ｙ）を圧縮することにある。ここでは、
【０００５】
【数１】
0004596718.tif 000002
となる。
【０００６】
予測フレームＩ^ｎ（ｘ，ｙ）は、動き補償予測ブロック１によって構成され、先行フレーム、あるいは、基準フレームと称されＩ〜ｒｅｆ（ｘ，ｙ）で示される既に符号化された他フレームのピクセル値、及び現在フレーム及び基準フレーム間のピクセルの動きベクトルのピクセル値を用いて組み立てられる。動きベクトルは動き場推定ブロック２によって算出され、結果として得られるベクトル場が何らかの方法で符号化され、予測ブロック１に入力される。この予測フレームを下記式に示す。
【０００７】
【数２】
0004596718.tif 000003
【０００８】
ここで、Δ〜ｘ（ｘ，ｙ）及びΔ〜ｙ（ｘ，ｙ）は、位置（ｘ，ｙ）における水平及び垂直方向のピクセル変位の値であり、この１組の数値［Δ〜ｘ（ｘ，ｙ），Δ〜ｙ（ｘ，ｙ）］をそのピクセルの動きベクトルと称す。そして、現在フレームＩｎ（ｘ，ｙ）の全ピクセルの動きベクトルの１組を動きベクトル場と称す。符号化された動きベクトル場は、符号化された予測誤差情報と共に動き情報としてデコーダに送信される。
【０００９】
そして、図３に示すように、デコーダでは、基準フレームＩ〜ｒｅｆ（ｘ，ｙ）におけるピクセルの予測Ｉ^ｎ（ｘ，ｙ）を見つけて復号化予測誤差Ｅ^ｎ（ｘ，ｙ）を付加し、現在出力フレームＩ〜ｎ（ｘ，ｙ）を再構成する。動き補償予測ブロック２１は、受信した動き情報と基準フレームＩ〜ｒｅｆ（ｘ，ｙ）とを用いて予測フレームを生成する。予測誤差デコーダ２２は、予測フレームに付加する復号化予測誤差Ｅ^ｎ（ｘ，ｙ）を生成し、その結果が現在出力フレームＩ〜ｎ（ｘ，ｙ）となる。
動き補償(ＭＣ)予測の総合的な目的は、例えばＥｎ（ｘ，ｙ）のエネルギーとして計測された予測誤差の量と共にデコーダに送信されるべき情報量をできるだけ少なくすることにある。
【００１０】
マサチューセッツ州ケンブリッジにて１９９０年３月１８日―２６日に開催されたピクチャーコーディングシンポジウム‘９０の議事録、８４１−８４５頁、Ｈ．Ｎｇｕｅｎ及びＥ．Ｄｕｂｏｉｓの論文“Representation of motion information for image coding”では、動き場符号化技術についての報告がなされている。経験則として、予測誤差の削減はより高度の動き場モデルが必要となる、つまり、より多くのビットがその符号化に必要となる。そのため、画像符号化の全体的な目標は、予測誤差の程度をできるだけ低く保ちつつ動きベクトルをできるだけコンパクトに符号化することにある。
【００１１】
図２に示されている動き場推定ブロック２は、所定の画像セグメントにおいてある程度の予測誤差、例えば２乗予測誤差を最小化する所与の画像セグメントの全ピクセルの動きベクトルを算出する。
【００１２】
フレームのピクセル数が膨大なため、ピクセル毎に異なる動きベクトルを送信するのは効率的ではない。その代わり、大部分の画像符号化構成では、現在フレームがより大きな画像セグメントに分割されているので、このセグメントの全動きベクトルを少ないパラメータで表すことができる。画像セグメントは正方形のブロックで、例えば１６×１６及び８×８のピクセルブロックが、国際標準規格ＩＳＯ／ＩＥＣのＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４またはＩＴＵ―Ｔ  Ｈ．２６４及びＨ．２６３に従ってコーデックで使用される。また、例えば分割アルゴリズムによって得られた任意の形状の領域で構成してもよい。実際には、セグメントは少なくとも数十のピクセルで構成される。
【００１３】
１セグメント中のピクセルの動きベクトルをコンパクトに表現するためには、動きベクトルが少ないパラメータによる関数で表現されるのが望ましい。そのような関数は動きベクトル場モデルと呼ばれる。既知のモデル群は線形動きモデルで、動きベクトルが動き場基底関数の１次結合によって表される。このようなモデルでは、画像セグメントの動きベクトルが下記の一般式で表される。
【００１４】
【数３】
0004596718.tif 000004
【００１５】
ここでは、パラメータｃｉが動き係数と称され、デコーダに送信される。一般的に、１セグメント用の動きモデルはＮ+Ｍ動き係数に基づく。関数ｆｉ（ｘ，ｙ）は動き場基底関数と称され、エンコーダ及びデコーダ双方に対するものとして知られている。既知の動き場推定技術は、動き場を表現するのに用いられるモデルの観点から、かつ選択された予測誤差量を最小化するアルゴリズムによって異なる。
【００１６】
また、動きの量及び複雑さもフレーム間及びセグメント間で異なる。例えば、画像の中身が回転したり斜めになったり、画像の一方の側から反対の側に移動する場合がある。一方、ビデオカメラがゆっくりと垂直の軸の周りを回転し、全ピクセルを水平面において少しだけ移動させるような場合もある。このため、セグメントにつきいつもＮ+Ｍ動き係数を用いるのは効率的でない。
動き情報を削減する１つの方法は、ピクセル位置をある画像から他の画像へと動かす動き場モデルから、動き係数の数を単純に減らすものである。しかしながら、動き場モデルのきめが粗くなると、予測誤差は増加する傾向にある。
【００１７】
セグメント毎では、十分に低い予測誤差におさめる最少数の動き係数を決める必要がある。そのような動き係数の適応選択プロセスを動き係数除去と称する。このプロセスは、図２にあるように、エンコーダにて動き場符号化ブロック３が実行する。これは、動き場推定ブロック２によって実行される動き場推定の後に実行される。
【００１８】
将来的に、デジタル画像伝送は、無線移動端末間で可能になるだろう。通常、そのような端末は追加コンポーネントに対して限られた空間しか持たず、かつ電池駆動のため、デスクトップコンピュータのような固定装置に匹敵する演算容量を搭載する見込みはない。よって、ビデオコーダで実行される動き場コーディングが計算的に単純であり、装置のプロセッサに過度の負担を課すことがないようにすることが重要である。さらに、符号化された動き場モデルは、受信（移動）端末のデコーダにおける後の復号処理を容易にするために、計算的に単純なものにすべきである。
【００１９】
異なるモデルで動き推定を行い最適なものを選択する方法は、１９９４年の音響・音声・信号処理国際会議の議事録、ＩＩＩ２６５−２６８頁、Ｈ，Ｎｉｃｏｌａｓ及びＣ．Ｌａｂｉｔの論文“Region-based motion estimation using deterministic relaxation schemes for image sequence coding”、及び１９９４年６月発行、IEEE Tran. On Circuits and Systems for Video Technology、４巻、３号、３５７−364頁、Ｐ．Ｃｉｃｃｏｎｉ及びＨ．Ｎｉｃｏｌａｓの論文“Efficient region-based motion estimation and symmetry oriented segmentation for image sequence coding”で提案されている。これらの方法は、異なるモデルで動き推定を行い最適なものを選択することにより、動きの複雑さの程度によって動きモデルを適合させようと試みるものである。これらの方法の主な欠点は、計算に関する複雑度が高く、実際にテスト可能な異なる動き場モデルの数が少ないことである。
【００２０】
さらに他の方法が国際出願番号ＷＯ９７／１６０２５に記載されている。ここで、ビデオコーデックは、動きベクトル場の動き係数の数を最小化する動き場コーダを備える。このコーダでは、第１ブロックが動きベクトル場の新しい行列表記を形成する手段を備える。新規に符号化されたこの動きベクトル場は線形である。次に、第２ブロックは、合成されたセグメントエリアを１つの共通動き場を用いて予測できる場合に隣接セグメント対をマージする手段を備える。情報の合成はデコーダに送信される。次に、第３ブロックは、動き場基底関数を除去する手段を備える。各除去ステップの後、２乗された予測誤差が算出されると共に、この除去処理は誤差の大きさが許容できなくなるまで継続される。そして、最終的な動き係数は、線形行列式を解くことにより計算される。その結果、セグメント毎に数が減らされた動き係数が得られる。そして、これら動き係数がデコーダに送信される。この方法により、ある閾値の予測誤差に達するまで動き係数の除去が可能となる。
しかしながら、復号化された画像の品質低下を最小限にとどめながらデコーダに送られるべき動き情報の量と、動き符号化プロセスの複雑さとをさらに低減させる必要がある。
【００２１】
本発明は、再構成誤差を激増させることなく、動き情報の量を大幅に削減することを目的とする。
また、本発明の別の目的は、市販の信号プロセッサや汎用マイクロプロセッサを使用して実際に実現できるように、動き場コーダの複雑さを低く抑えることである。
【００２２】
（発明の開示）
本発明は添付の特許請求の範囲によって定義される。
ビデオエンコーダの動き場コーダの一部をなす動き分析器において予測動き係数を利用することにより、従来公知の解決法よりもより良い速度歪み性能が達成できる。
また、動き係数除去ブロックを利用して、速度歪み性能をさらに最適化するのに用いられる複数の動き係数の代替組合せを計算できる。動き係数除去ブロックは、ある費用関数を実行し、最終の速度歪みを最適化する組み合わせを見つけるようにするのが好ましい。
【００２３】
（発明を実施するための最良の形態）
図1から図３は上述されている。
以下に本発明のあらましを述べ、本発明の各種実施形態をさらに詳しく説明する。
本発明の好適実施形態によれば、ビデオエンコーダの動き場コーダは２つの主ブロックからなる。
【００２４】
第１の主ブロックは、図４及び図５の通り、動き分析器３２と称される。そのタスクは、図２の動き場推定ブロック２が生成した入力動き場の新しい表現を見つけ出すことにある。この新しい表現は、図４の第２の主ブロック、すなわち動き係数除去ブロック３４に適用される。動き分析器における動作は、行列演算を含む複数のステップを含む。第１のステップでは、予測フレームの動きベクトルへの依存度が近似法を用いて線形化される。第２のステップでは、２乗予測誤差の極少化のために行列Ａｋとベクトルｄｋとが構成される。第３のステップでは、対角行列Ｒｋ及び補助ベクトルｚｋの形で柔軟な動き表現を作成するために、Ａｋの因数分解に基づく対角系の１次方程式がたてられる。
【００２５】
動き係数除去ブロック３４は、動き分析器ブロックが生成した対角行列Ｒｋ及び補助ベクトルｚｋを入力する。１セグメントの動きベクトルは、複数の動き係数で表される。動き係数除去ブロックは、各セグメントに対して、再構成誤差を過剰に増加させることなく動き場モデルを簡略化することが可能かどうかを判断する。通例、いくつかの基底関数が動きモデルから除去されることにより、そのように簡略化された動き場モデルを記述するのに必要となる係数の数はより少なくなる。
【００２６】
動き係数除去ブロック34は、対角行列Ｒｋの１列を取り除いて新しい配列を三角化することによって、対角行列Ｒｋを含む行列式を修正する。その結果、それらの式において動き係数が１つ少なくなり、ベクトルｚｋから１つの項が取り除かれる。この処理は、動き場モデルから１つの基底関数を取り除くことに相当する。選択された予測誤差の程度、すなわち費用関数を最適化する動き場モデルを決定するために、動き場モデルに残存する基底関数がなくなるまで、これらの処理が繰り返される。基底関数が取り除かれるたびに、行列式を解いて新しい動き係数の組が推定される。これは、例えば、後退代入のような公知のアルゴリズムであるなら、どのようなものを用いても良い。最終組の動きパラメータ、すなわち、特定セグメントの動きを表現するのに選択されたものは、費用関数を最小にするものである。ここで、費用関数は、予測誤差量と画像を復号するのに要する情報量との加重合計であるのが好ましい。
【００２７】
各処理セグメントに対し、動き係数除去ブロック34は動き場モデルから取り除かれた基底関数を定義する選択情報を出力する。加えて、残存する基底関数に対応する新しい動き係数も出力する。そして、選択情報と新しい動き係数の両方がデコーダに送信される。
【００２８】
図4は本発明の１つの実施形態による動き場エンコーダ３を示しており、図２のブロック3に対応する。動き場エンコーダは基準フレームＩ〜ｒｅｆ（ｘ，ｙ）、現在フレームＩ〜ｎ（ｘ，ｙ）、予測動き係数、もしあれば、図２の動き場推定ブロック２が生成した動きベクトル場［Δｘ（ｘ、ｙ），Δｙ（ｘ，ｙ）］を入力する。
ビデオエンコーダの出力は、１つのセグメントＳｋに対して動き係数が定義したセグメントに分割されて圧縮されたフレームを含んでいる。このセグメントＳｋは座標（ｘｉ，ｙｉ）のＰ個のピクセルからなる（ここではｉ＝１，２，．．．Ｐ）。動き場コーダのタスクは、圧縮された動きベクトル場［Δ〜ｘ（・），Δ〜ｙ（・）］の動き係数ｃ〜＝（ｃ〜１，ｃ〜２，．．．，ｃ〜Ｎ＋Ｍ）を見つけ出すことにある。ここで、動きベクトルはある線形動きモデルによって表され、そのフィールドは下記の形式からなる。
【００２９】
【数４】
0004596718.tif 000005
【００３０】
これにより、選択された費用関数、例えばラグランジュ・コストが下記の通り最小化される。
【数５】
0004596718.tif 000006
【００３１】
ここで、歪みＤ（Ｓｋ）は、元のセグメント及び符号化されたセグメント間の2乗誤差である。そして、速度Ｒ（Ｓｋ）は、セグメントを符号化するのに必要なビットの数と等しく、パラメータλは、符号化されたセグメントの品質とそのセグメントの圧縮に要するビット数とのトレードオフを定めるあらかじめ定義された係数である。
【００３２】
このタスクの条件を満たすために、動き場コーダ３は２つの主ブロックからなる。すなわち、それらは動き分析器ブロック３２と動き係数除去ブロック３４である。動き分析器３２の目的は、動き場の新しい表現を見つけることである。この新しい表現は、後に動き係数除去ブロックで用いられ、素早くかつ柔軟な方法で、所定の画像セグメントに対する動き係数を見つけ出す。動き係数除去ブロック３４は、１つのセグメントの動き場を表すために用いられる動き情報の量を減少させ、その結果、以下に定義するように、２乗予測誤差を増加させる。
【００３３】
【数６】
0004596718.tif 000007
【００３４】
動き分析器３２の動作を次に図５を参照して詳細に説明する。動き分析器３２の動作は以下のステップからなる。
ステップ１：誤差の線形化。ブロック４２。このステップでは、［Δｘ（ｘ，ｙ），Δｙ（ｘ，ｙ）］への依存度が線形をなすように、式（6）の基準フレームＩ~ｒｅｆ（ｘ，ｙ）を公知の近似法を用いて近似する。そして、式（6）の合計における要素が動き係数Ｃｉの線形結合になる。
【００３５】
【数７】
0004596718.tif 000008
【００３６】
ステップ２：行列の構成。ブロック43。式(7)の最小化は行列式(Ｅｋｃｋ−ｙｋ)T(Ｅｋｃｋ−ｙｋ)の最小化、あるいは下記式の解とまったく等価となる。
【数８】
0004596718.tif 000009
ここで、Ａｋ＝ＥｋTＥｋ及びｄｋ＝ＥｋTｙｋ。そしてベクトルｙｋはブロック４６で作られる。
【００３７】
【数９】
0004596718.tif 000010
【００３８】
ステップ３：三角化と出力の生成。ブロック44。このステップでは、Ａｋを下位の対角行列ＲｋTとその転置行列ＲｋTとの積に分解するための公知の方法を用いて式(8)を三角化する。
【数１０】
0004596718.tif 000011
これは、コレスキー分解を用いて行うことができる。
【００３９】
そして、補助ベクトルｚｋ０が、例えば後退代入を用いて下記式を解くことにより作成される。
【数１１】
0004596718.tif 000012
【００４０】
下記に示すように、式（７）を最小化する動き係数ｃｋのベクトルは、対角配列では未知のベクトルである。
【数１２】
0004596718.tif 000013
そして、必要であれば、例えば後退代入を用いて解くことができる。
【００４１】
動き係数ｃｋは、予測動き係数ｐｋ及び細分動き係数ｒｋの合計として得られる。予測動き係数は、以前に生成された動き係数と細分動き係数から予測され、その予測動き係数と、動き場推定ブロック(図２)で計算された動き係数との差に対応する。この場合、式（１２）は以下の形をとる。
【００４２】
【数１３】
0004596718.tif 000014
【００４３】
そして出力ベクトルｚｋは、下記式を計算することにより得られる。
【数１４】
0004596718.tif 000015
【００４４】
ブロック47は項ｚｋ０を形成し、ブロック45はＲｋｐｋを生成する。そして、次の動き係数除去ブロック３４の出力は、絶対動き係数ではなく、細分動き係数となる。もしくは、出力ベクトルｚｋ＝ｚｋ０となる。
動き係数除去ブロック３４は、動き分析器ブロック32が生成した入力行列Ｒｋとベクトルｚｋとして受信する。各セグメントの動きベクトルはＮ＋Ｍ個の動き係数で表される。
【００４５】
所定セグメントＳｋに対して、動き係数除去ブロックは、選択された誤差量を過剰に増加することなく、動き場モデルを簡略化することが可能かどうかを判断する。簡略化された動き場モデルは、本願の背景技術において説明した式（３）におけるモデルから基底関数が取り除かれる際に得られる。そのような簡略化された動き場モデルを記述するのに必要な係数の数はより少なくてすむ。
【００４６】
最適な動きベクトル場を見つけ出すためには、以下の繰返し手順が実行される。
ステップＡ：初期コスト計算。セグメントに対するラグランジュ・コストは完全な動きモデルで評価され、動き係数のフルセットと共に格納される。
ステップＢ：予測品質への影響が最小の基底関数を求める。Ｒｋｎは、残存するｎ個の基底関数を伴うｎ×ｎの上位対角固有行列を示し、Ｒｋｎ，ｉはｉ番目の列が取り除かれた同行列を示す。ここで、行列Ｒｋｎからｉ番目の列が取り除かれ、ｃｋｎからｉ番目の要素が取り除かれてｎ組の式が生成される。
【００４７】
【数１５】
0004596718.tif 000016
【００４８】
生成されたすべての式は、スカラーによる一連の行の乗法を適用した後、それらの行の加算を行う公知の方法で三角化される。つまり方程式（15）は次の形に変換される。
【数１６】
0004596718.tif 000017
【００４９】
ここで、（ｑｉ）２は、ｉ番目の基底関数を動きモデルから除去することより生じる２乗予測エラーの増分の近似値である。除去の際に最小の（ｑｉ）２値を生じる列は、この繰返し中に除去されるべきものであり、i番目の基関数を動きモデルから効果的に除去させる。
【００５０】
ステップＣ：基底関数のモデルからの除去。新しい行列式は、除去すべき基底関数に関連する行列Ｒｋｎ，ｉ及びベクトルｚｋｎ，ｉを選択し、行列の最終行及びベクトルの最終要素を以下のように除去して作られる。
【数１７】
0004596718.tif 000018
【００５１】
ステップＤ：係数計算。数が削減された基底関数の組に対し、以下の三角配列を解くことにより、動き係数の新しい組を計算する。
【数１８】
0004596718.tif 000019
例えば、後退代入によって上記計算を行う。
【００５２】
ステップＥ：コスト計算。このモデルがその時点で最上のものであれば、セグメントに対するラグランジュ・コストが評価され、１組の動きパラメータと共に格納される。
ステップＦ：最終動きモデル選択。まだ除去すべき基底関数がある場合、ステップＢからＥの処理を繰り返す。モデルから基底関数が全て除去されている場合は、その出力が生成される。その出力は、残存基底関数に対応する新しい動き係数と共に、どの基底関数を動き場モデルから除去すべきかを記述する選択情報とで構成されている。そして、選択情報及び動き係数両方ともがデコーダに送信される。
【００５３】
従来技術の解決策に対する本発明の主たる利点は、再構築誤差を過度に増加させることなく、動き情報量を大幅に削減できることである。加えて、システム全体の複雑さの度合いが低いので、市販の信号プロセッサや汎用マイクロプロセッサに現実的に実装できる。
動き係数除去ブロックは、ビデオシーンにおける実際の動きの量と種類に動きモデルを瞬時に合わせる非常に強力なツールとなる。このブロックは、動きパラメータ予測の有無にかかわらず、多くの動きモデルをテストするのに用いられる。この構成の優れた利点は、動きモデルを変更する際に動き推定プロセスを繰り返す必要が無く、そのために演算的に単純なことである。
動き分析器が従う動き推定を利用することにより、動き場コーダは、１次方程式の非常に単純な系列を計算により解き、いかなる所望の動き場モデルに対しても新しい動き係数を発見できる。
【００５４】
好適な実施形態では、６つの係数を持ち正規直交化された擬似動きベクトル場モデルが使われる。実際に、このモデルは、ビデオシーケンスの非常に複雑な動きでさえ高精度に処理することができ、良い予測結果を生み出す。
擬似動きベクトル場は、１組の動き係数で動きベクトルの近似値を得るのに用いられる動きモデルである。擬似動きモデルは、各種の動きを描写できるが、その中には、移動、回転、拡大縮小及び傾斜などの動作が含まれる。擬似動きモデルは６つの基底関数からなり、その場合に動きベクトルは、動き係数が掛けられた６つの基底関数を含む和データと実質的に置換可能であり、各動き係数は１つの特定基底関数に対して計算される。基底関数自体は、エンコーダ及びデコーダいずれに対しても公知のものである。
【００５５】
動き分析器ブロック32において、ステップ1の線形化は、以下のポイントを取り囲むピクセル（ｘｉ，ｙｉ）毎に基準フレームＩ〜ｒｅｆ（ｘ，ｙ）のテイラー展開を用いて実行される。なお、ここでｉ＝１，２，．．．，Ｐ（Ｐはセグメント内のピクセル数）。
【００５６】
【数１９】
0004596718.tif 000020
【００５７】
そして、Σａ２＝Σ（−ａ）２である特性を用いると、予測誤差は次の通りとなる。
【数２０】
0004596718.tif 000021
【００５８】
補助値ｇｊ（x，ｙ）は下記式を用いて算出される。
【数２１】
0004596718.tif 000022
【００５９】
ここで、関数ｆｊ（ｘｉ，ｙｉ）は式（４）で定義されるような基底関数である。式（９）の行列Ｅｋ及びベクトルｙｋは下記式を用いてつくられる。
【数２２】
0004596718.tif 000023
【数２３】
0004596718.tif 000024
【００６０】
Ｇｘ（ｘ，ｙ）及びＧｙ（ｘ，ｙ）は、公知の３次スプライン補間関数の導関数を用いて計算された基準フレームＩ〜ｒｅｆ（ｘ，ｙ）の水平及び垂直の勾配の値である。
行列Ａｋは、コレスキー分解を使って因数分解され、式（１５）の配列はギブンズ回転列を用いて三角化される。
【００６１】
新しい動きモデルに対する動き係数は、後退代入アルゴリズムを用いて式（18）を解くことにより計算される。
Ｉ〜ｒｅｆ（ｘ，ｙ）、Ｇｘ（ｘ，ｙ）及びＧｙ（ｘ，ｙ）のピクセル値は、ｘ及びｙの整数座標に対してのみ定義される。ｘまたはｙが整数でないとき、ピクセル値は。ｘとｙ近辺の整数ピクセル値を用いた３次スプライン補間を使って計算される。
【００６２】
図6は本発明の１つの実施形態の移動局ＭＳを示す。中央処理ユニット、すなわちマイクロプロセッサπＰは移動局の異なる機能を担うブロック、すなわち、ランダムアクセスメモリRAM、高周波ブロックＲＦ、読み出し専用メモリＲＯＭ、ディスプレイＤＰＬとキーボードＫＢＤを有するユーザインタフェースＵＩ、及びデジタルカメラブロックＣＡＭを制御する。マイクロプロセッサの動作指示、すなわちプログラムコードと移動局の基底関数は、前もって、例えば製造工程中に移動局のＲＯＭに格納される。そのプログラムに従い、マイクロプロセッサは無線路上でメッセージを送受信するための高周波ブロックＲＦを用い、ユーザインターフェースUIの状態をモニタし、デジタルカメラブロックCAMを制御する。そして、ユーザコマンドに応じて、マイクロプロセッサはデジタル画像をＲＡＭに記録するようデジタルカメラブロックCAMに指示する。ひとたび画像が取り込まれるか、あるいは画像取り込みプロセスの間、マイクロプロセッサは前述したような圧縮画像を生成するために、画像を画像セグメントに分割してそれらセグメントに対する動き場モデルを計算する。ディスプレイ上に画像を表示するよう、あるいはＲＦブロックを用いて圧縮画像を他の移動局、有線電話機、ファクシミリ装置、または他の電気通信装置に送るよう、ユーザは移動局にコマンドを送ることができる。
【００６３】
好適な実施形態においては、受信者が最少遅延時間で復号処理を始められるように、最初のセグメントが符号化されるとすぐに画像送信が開始される。また、他の実施形態においては、移動局は、符号化、そしておそらくデジタルビデオデータを復号化する専用のエンコーダブロックＥＮＣを備える。
【００６４】
図7は本発明の１つの実施形態による移動電気通信網の概略図である。ここでは、移動局ＭＳが無線リンクによって基地局ＢＴＳと通信している。基地局ＢＴＳは、いわゆるＡｂｉｓインタフェースを通じて基地局コントローラＢＳＣにさらに接続される。基地局コントローラＢＳＣは、いくつかの基地局を制御、管理する。複数の基地局ＢＴＳ（通常は数ダースの基地局）及び１つの基地局コントローラＢＳＣによって構成されるエンティティは、基地局システムＢＳＳと呼ばれる。特に、基地局コントローラＢＳＣは無線通信チャンネルとハンドオーバとを管理する。一方、基地局コントローラＢＳＣは、いわゆるＡインタフェースを介して移動サービス交換局ＭＳＣに接続される。移動サービス交換局ＭＳＣは、移動局から、あるいはそれら移動局への接続の形成を調整する。そして、移動サービス交換局ＭＳＣを介して、移動通信網の外部にさらに接続される。移動通信網の外部には、ゲートウェイＧＴＷ、例えばインターネットによって移動通信網に接続された他の通信網がさらに存在する。そのような外部ネットワーク、または電気通信ネットワークでは、コンピュータＰＣ等のビデオ復号または符号化局が設置されている場合もある。本発明の実施形態において、移動電気通信網はこのようなサービスへ加入しているＭＳにビデオデータを提供するビデオサーバＶＳＲＶＲを備える。このビデオデータは、本文献で先に述べたように、動き補償画像圧縮法を用いて圧縮される。ここでは、ビデオサーバがオンラインビデオソースへのゲートウェイとして機能するか、あるいは以前に記録されたビデオクリップを含んでいる。
【００６５】
本システムは、本発明の精神及び範囲から逸脱することなく、様々な方法で実現することができる。例えば、
・異なる動きモデルを使用できる。
・方程式（５）で与えられたラグランジュ・コストの代わりに、異なるコスト関数を用いることができる。
・式（６）の項を線形化するために異なる方法を使用できる（コレスキー分解の代わりにＱＲ分解を用いる等）。
・基底関数の除去順序を決定する方法を変更できる（例えば、式（16）における評価ｑｉ’の代わりに予め定義した順番を使用できる）。
【００６６】
・動きモデルによっては動き係数除去ブロックで省略できる（入力係数の中で無視し得るレベルのものがあれば、対応する基底関数を廃棄するとの決定ができる等）。
・動き係数除去ブロックにおけるコスト計算は、基底関数の除去の直後に行う必要はなく、遅延してもよい。これは、係数除去ブロックのステップＢ−ＤがステップＢ−Ｅの代わりに繰り返されてもよいことを意味する。そして、ステップＥ（コスト計算）は、（このセグメントに対して）生成された全動きモデルに対する他のループで実行される場合もある。
【００６７】
・式（１５）の配列の三角化は様々なアルゴリズムを使用して実行可能である。
・式（１８）を求めることによる最終係数計算は、１次方程式の配列を解く多数の公知アルゴリズムを用いて実行可能である。
・式（１３）及び（１４）における予測項は、式（２３）の動きベクトル（Δｘ（ｘｉ，ｙｉ）及びΔｙ（ｘｉ，ｙｉ））を動きベクトルの細分（推定動きベクトルと予測動きベクトル間の差）によって置き換えることによって代替的に組み入れられる。
・非整数座標において基準フレームＩ〜ｒｅｆ（ｘ，ｙ）、Ｇｘ（ｘ，ｙ）及びＧｙ（ｘ，ｙ）の値を得るのに、異なる補間方法を用いることができる。
【図面の簡単な説明】
【図１】  セグメントに分割された画像の概略図である。
【図２】  従来技術によるエンコーダの概略図である。
【図３】  従来技術によるデコーダの概略図である。
【図４】  本発明の１つの実施形態による動き場コーダである。
【図５】  本発明の１つの実施形態による動き分析器である。
【図６】  本発明の１つの実施形態による移動局の概略図である。
【図７】  本発明の１つの実施形態による移動電気通信網の概略図である。
【図１】
0004596718.tif 000025
【図２】
0004596718.tif 000026
【図３】
0004596718.tif 000027
【図４】
0004596718.tif 000028
【図５】
0004596718.tif 000029
【図６】
0004596718.tif 000030
【図７】
0004596718.tif 000031