(57)【特許請求の範囲】
【請求項１】
映像データを動き補償エンコードするための映像エンコーダであって、当該映像エンコーダは、基準フレームに対してコード化されるべき現在フレームの映像ピクセルの運動ベクトルフィールドを与え、そして当該映像エンコーダは当該運動ベクトルフィールドをコード化して圧縮された運動情報を与えるための運動フィールドコーダを有し、各フレームは複数のセグメントを有し、上記運動フィールドコーダは運動分析器を有し、当該運動分析器は現在フレームの各セグメントｋに対して近似マトリクスＥk及び近似ベクトルｑkを計算して記憶するための手段を含み、各セグメントの２乗予想エラーΔｅkは、（Ｅkｃk−ｑk）の関数で近似され、ｃkは、上記運動ベクトルフィールドを近似する１組の多項式基礎関数ｆnの運動係数ｃnを含むベクトルであり、そして更に、上記運動フィールドコーダは、上記Ｅk及びｑkから出力マトリクスＡk及び出力ベクトルｄkを含む運動分析器出力パラメータを発生するための手段を備え、ここで、Ａkは、Ｅkの転置とＥkとの積であり、そしてｄkは、Ｅkの転置とｑkとの積であり、上記Ｅk及びｑkは、上記２乗予想エラーΔｅkを近似するときに使用する近似方法に依存することを特徴とする映像エンコーダ。
【請求項２】
上記運動フィールドコーダは、運動分析器の出力を受信するセグメント合体ブロックを備え、このセグメント合体ブロックは、共通の運動係数ベクトルを使用して合成領域におけるピクセル値を予想できる場合に隣接セグメントＳi及びＳjの対を合体するための合体手段を備え、この合体手段は、次の一次式を解くことにより合体セグメントＳkに対する共通の運動係数ベクトルｃkを決定し、
Ａkｃk＝ｄk
但し、Ａkは、運動分析器出力マトリクスＡi及びＡjの和により与えられる合体マトリクスであり、そしてｄkは、セグメントＳi及びＳjの運動分析器出力ベクトルｄi及びｄjの和により与えられる合体ベクトルである請求項１に記載の映像エンコーダ。
【請求項３】
スレッシュホールドより小さいラグランジュコストの減少を有する隣接セグメントは、非隣接セグメントとして定められ、合体されない請求項２に記載の映像エンコーダ。
【請求項４】
セグメントＳi及びＳjを１つのセグメントＳkに合体することは、次の基準
ΔＬij＝(Ｌ(Ｓi)＋Ｌ(Ｓj))−Ｌ(Ｓk)
に基づくラグランジュコストΔＬijの減少に基づく請求項２又は３に記載の映像エンコーダ。
【請求項５】
上記セグメント合体ブロックは、上記基準にしたがって所定のスレッシュホールドより低い上記ラグランジュコストΔＬijの減少を有する隣接セグメントＳi及びＳjの対を非隣接セグメントとして定義するための手段と、隣接セグメントの全ての対の中でラグランジュコストの最大減少をもつ隣接セグメントの対を探索する手段と、減少がゼロを越える場合に上記隣接セグメントを合体する手段とを備えた請求項４に記載の映像エンコーダ。
【請求項６】
新たに形成されるセグメントＳkのｌ＝１、・・Ｌである隣接セグメントＳlについてラグランジュコストを再計算するための手段を備え、これは、Ｓk及びＳlが新たなセグメントＳmを形成するために合成された場合、Ｓk及びＳlの合成領域における２乗予想エラーΔｅklである隣接セグメントのための歪の予め定められた尺度の増加をｌ＝１、・・Ｌに対して、次の式に基づいて計算し、
【数１】
0004573438.tif 000012
そして予想エラーの増加が最も小さいセグメントから、予想エラーの増加が最も大きいセグメントへと進むラグランジュコストの減少を、ΔＬklが正で且つ上記合成領域のための２乗予想エラーΔｅklがスレッシュホールドを越えるようなセグメントＳlに遭遇するまで計算するための手段より成り、ｃmは新たなセグメントｍのための運動係数ベクトルであり、Ｚlk，Ｚllは隣接セグメントｌ及びｋそれぞれのセットｌの補助ベクトルであり、（Ｒlk）Tｚlk＝ｄkであり、Ｒlkは上部三角マトリクスである請求項５に記載の映像エンコーダ。
【請求項７】
セグメントＳi及びＳjを合体すべきであることが決定された場合に、合体されたセグメントＳkの出力マトリクスＡk及び出力ベクトルｄkは、次のように計算される
Ａk＝Ａi＋Ａj、ｄk＝ｄi＋ｄj
請求項２ないし６のいずれかに記載の映像エンコーダ。
【請求項８】
各合体されたセグメント出力パラメータに対し、
0004573438.tif 000013
請求項２ないし７のいずれかに記載の映像エンコーダ。
【請求項９】
映像データを動き補償エンコードする方法であって、当該方法は、基準フレームに対してコード化されるべき現在フレームの映像ピクセルの運動ベクトルフィールドを与えることを含み、各フレームは複数のセグメントを含み、上記方法はさらに運動ベクトルフィールドをコード化して、圧縮された運動情報を提供することを含み、運動ベクトルフィールドの上記コード化は、現在フレームの各セグメントｋに対して近似マトリクスＥk及び近似ベクトルｑkを計算して記憶することを含み、各セグメントの２乗予想エラーΔｅkは、（Ｅkｃk−ｑk）の関数で近似され、ｃkは、上記運動ベクトルフィールドを近似する１組の多項式基礎関数ｆnの運動係数ｃnを有するベクトルであり、そして更に、上記Ｅk及びｑkから出力マトリクスＡk及び出力ベクトルｄkを含む運動分析器出力パラメータを発生し、ここで、Ａkは、Ｅkの転置とＥkとの積であり、そしてｄkは、Ｅkの転置とｑkとの積であり、上記Ｅk及びｑkは、上記２乗予想エラーΔｅkを近似するときに使用する近似方法に依存することを特徴とする方法。
【請求項１０】
共通の運動係数ベクトルを使用して合成領域におけるピクセル値を予想できる場合に隣接セグメントＳi及びＳjの対を合体し、これは、次の一次式を解くことにより合体セグメントＳkに対する共通の運動係数ベクトルｃkを決定することを含み、
Ａkｃk＝ｄk
但し、Ａkは、運動分析器出力マトリクスＡi及びＡjの和により与えられる合体マトリクスであり、そしてｄkは、セグメントＳi及びＳjの運動分析器出力ベクトルｄi及びｄjの和により与えられる合体ベクトルである請求項９に記載の方法。
【請求項１１】
スレッシュホールドより小さいラグランジュコストの減少を有する隣接セグメントは、非隣接セグメントとして定められ、合体されない請求項１０に記載の方法。
【請求項１２】
セグメントＳi及びＳjを１つのセグメントＳkに合体することは、次の基準
ΔＬij＝(Ｌ(Ｓi)＋Ｌ(Ｓj))−Ｌ(Ｓk)
に基づくラグランジュコストΔＬijの減少に基づく請求項１０又は１１に記載の方法。
【請求項１３】
上記セグメント化は、上記基準にしたがって所定のスレッシュホールドより低い上記ラグランジュコストΔＬijの減少を有する隣接セグメントＳi及びＳjの対を非隣接セグメントとして定義し、隣接セグメントの全ての対の中でラグランジュコストの最大減少をもつ隣接セグメントの対を探索し、そして減少がゼロを越える場合に上記隣接セグメントを合体することを含む請求項１２に記載の方法。
【請求項１４】
新たに形成されるセグメントＳkのｌ＝１、・・Ｌである隣接セグメントＳlについてラグランジュコストを再計算することを含み、これは、Ｓk及びＳlが新たなセグメントＳmを形成するために合成された場合、Ｓk及びＳlの合成領域における２乗予想エラーΔｅklである隣接セグメントのための歪の予め定められた尺度の増加をｌ＝１、・・Ｌに対して、次の式に基づいて計算し、
【数２】
0004573438.tif 000014
そして予想エラーの増加が最も小さいセグメントから、予想エラーの増加が最も大きいセグメントへと進むラグランジュコストの減少を、ΔＬklが正で且つ上記合成領域のための２乗予想エラーΔｅklがスレッシュホールドを越えるようなセグメントＳlに遭遇するまで計算することより成り、ｃmは新たなセグメントｍのための運動係数ベクトルであり、Ｚlk，Ｚllは隣接セグメントｌ及びｋそれぞれのセットｌの補助ベクトルであり、（Ｒlk）Tｚlk＝ｄkであり、Ｒlkは上部三角マトリクスである請求項１３に記載の方法。
【請求項１５】
セグメントＳi及びＳjが合体される場合に、合体されたセグメントＳkの出力マトリクスＡk及び出力ベクトルｄkは、次のように計算される
Ａk＝Ａi＋Ａj、ｄk＝ｄi＋ｄj
請求項１０ないし１４のいずれかに記載の方法。
【請求項１６】
各合体されたセグメント出力パラメータに対し、
0004573438.tif 000015
請求項１０ないし１５のいずれかに記載の方法。
【発明の詳細な説明】
【０００１】
【技術分野】
本発明は、映像データのエンコード及びデコード動作に係り、より詳細には、動き補償された予想を用いた映像データの圧縮及び圧縮解除に係る。
【０００２】
【背景技術】
動き補償予想を用いた映像コード化システムの回路図が、添付図面の図１及び２に示されている。図１は、エンコーダを示し、そして図２は、それに対応するデコーダを示す。このようなシステムにおける動き補償予想について以下に概要を述べる。
典型的な映像シーケンスでは、シーンにおける動きの結果として相次ぐフレームの内容が大きく変化する。この動きは、カメラの動き又はシーンに描かれる対象物の動きによるものである。それ故、典型的な映像シーケンスは、動きの軌跡に沿って最大となる著しい時間的相関を特徴とし、そして映像シーケンスを効率的に圧縮するには、映像シーケンスのこの特性を利用することが必要となる。動き補償（ＭＣ）予想は、映像を圧縮するための広く知られた技術である。これは、典型的な映像シーケンスにおいて、２つのフレーム間で動きの軌跡が与えられると、特定フレームにおける像の強度値を、他の既にコード化されたフレームの像強度を使用して予想できることを利用するものである。
【０００３】
図１に示すエンコーダでは、動き推定ブロックは、現在フレームとも称するコード化されるフレームＩｎ(ｘ、ｙ)と、基準フレームＲｒｅｆ(ｘ、ｙ)との間のピクセルの運動ベクトル(Δｘ(ｘ、ｙ)、Δｙ(ｘ、ｙ))を計算する。基準フレームは、エンコーダ及びデコーダのフレームメモリにおいて所与の瞬間に使用できる既にコード化されたフレームの１つ（例えば、現在コード化されているフレームに先行するフレーム）である。一対の数字(Δｘ(ｘ、ｙ)、Δｙ(ｘ、ｙ))は、現在フレームの位置(ｘ、ｙ)におけるピクセルの運動ベクトルと称され、そしてΔｘ(ｘ、ｙ)及びΔｙ(ｘ、ｙ)は、各々、水平及び垂直変位の値である。
【０００４】
0004573438.tif 000002
【０００５】
0004573438.tif 000003
【０００６】
動き補償予想の目的は、デコーダに送信しなければならない情報の量と、エンコード動作に導入されるロスとの間に最適な妥協を見出すことであり、即ち、
１．予想エラーの量を最小にし、そして
２．運動ベクトルフィールドを表すのに必要な情報の量を最小にすることである。
フレームには非常に多数のピクセルがあるために、ピクセルごとに個別の運動ベクトルを送信するのは効率的でない。むしろ、ほとんどの映像コード化機構では、現在フレームを多数の像セグメントに分割し、セグメントの全運動ベクトルを僅かな係数で記述できるようにしている。現在フレームをセグメントに分割する方法に基づいて、２つの形式の動き補償コーダを区別することができる。
１．国際規格ＩＳＯ／ＩＥＣ  ＭＰＥＧ１又はＩＴＵ−ＴＨ．Ｔ６１のコーデックにおいて現在フレームを固定の既知のブロック、例えば、１６ｘ１６ピクセルブロックに分割するブロックベースのコーダ（図３ａを参照）、或いは
２．現在フレームを、例えば、図３ｂのセグメント化アルゴリズムにより得られる任意形状のセグメントに分割するセグメント化ベースの、即ち領域ベースのコーダ。
【０００７】
典型的な映像シーケンスのフレームは、異なる動きを伴う多数のオブジェクトを含む。ＭＣ予想は、フレームＩｎ(ｘ、ｙ)を多数のセグメントＳｋに分割し、そしてそのフレームと基準フレームＲｒｅｆ(ｘ、ｙ)との間でこれらセグメントの動きを推定することにより実行される。実際に、セグメントは、少なくとも数十のピクセルを含む。これらピクセルの運動ベクトルをコンパクトに表すためには、幾つかのパラメータの関数でそれらの値を記述することが望ましい。このような関数を運動ベクトルフィールドモデルと称する。動き補償映像コード化機構は、像セグメントの運動ベクトルを次の一般式を用いて近似する。
【数３】
0004573438.tif 000004
【０００８】
エンコーダにおいて、運動フィールドコード化ブロックは、運動ベクトルフィールドを表すのに必要なビット数を最小にすると同時に、予想エラーを低く抑えることを目的とする。運動ベクトルフィールドを表すのに必要な全ビット数は、次のものに依存する。
−  像におけるセグメントの数、
−  セグメントあたりの運動係数の数、及び
−  運動係数を表すのに必要なビット数。
運動フィールドコード化を実行するための公知のシステムが図４に示されており、このシステムは、４つの主要構成ブロック、即ちＱＲ運動分析器１と、セグメント合体ブロック２と、直交化ブロック３と、運動係数除去ブロック４とで構成される。このようなシステムは、ＰＣＴ公報ＷＯ９７／１６０２５号及びＷＯ９７／４０６２８号に開示されている。
運動フィールドコード化ブロックへの入力は、次の通りである。
−  運動推定ブロックにより見つけられた運動ベクトルフィールド(Δｘ(ｘ、ｙ)、Δｙ(ｘ、ｙ))、
−  現在フレーム、
−  基準フレーム、及び
−  現在フレームの最初のセグメント化。この最初のセグメント化は、運動推定中又はその前にエンコーダにおいて得ることができる。又、セグメント化は、ある外部手段によりエンコーダに対して行うこともできる。
【０００９】
運動フィールドコード化ブロックは、デコーダに送信されるべき全ビット数を次のようにして減少することができる。
−  予想エラーの大きな増加を生じることなく運動係数の共通ベクトルで予想することのできるセグメントを結合（合体）することによってセグメントの数を減少する。このようなセグメントを結合するプロセスを運動助成合体と称し、これは、セグメント合体ブロック２によって行われる。
−  対応する運動係数を少数のビットで表すことができるように、これら係数の量子化（量子化ブロック５で行われる）に対してあまり敏感でない基礎関数を使用する。離散的直交関数に対応する係数は、量子化に対して頑丈であることが知られている。それ故、セグメント合体の後に、セグメントを包囲する方形に対して基礎関数が直交される。これは、直交化ブロック３により行われる。
−  セグメントごとに、満足な低い予想エラーを達成する最少数の基礎関数を見つける。これらの選択された基礎関数に対応する係数だけをデコーダに送信すればよい。基礎関数及びそれに対応する運動係数のこのような適応選択プロセスは、運動係数除去ブロック４により行われる。
【００１０】
ＱＲ運動分析器１の機能は、セグメント及び基礎関数の異なる組合せに対応する運動係数を効率的に計算するためにセグメント合体ブロック２及び運動係数除去ブロック４により下流で使用できる運動ベクトルフィールドの表示を探索することである。ＱＲ運動分析器１及びセグメント合体ブロック２は、次のように動作する。
ＱＲ運動分析器１は、マトリクス演算を含む複数の段階を実行する。これらは、ＰＣＴ公報ＷＯ９７／１６０２５号及びＷＯ９７／４０６２８号に詳細に説明されている。第１段階では、予想フレームが運動ベクトルに対して直線的になるように、予想フレームを近似する。第２段階では、予想フレームの各セグメントＳｋに対しマトリクスＥｋ及びベクトルｑｋを構成する。第３段階では、良く知られたＱＲ因数分解アルゴリズムを使用して、マトリクスＥｋを２つのマトリクスＱｋ及びＲｋの積に分解する。但し、Ｑｋは、ユニタリーマトリクスであり、そしてＲｋは、上部三角マトリクスである。更に、因数マトリクスＱｋ及びマトリクスｑｋから補助ベクトルｚｋを計算する。マトリクスＲｋ及びベクトルｚｋの一部分をセグメント合体ブロック２に供給する。
【００１１】
セグメント合体ブロックは、共通の運動係数ベクトルを使用して合成領域におけるピクセル値を予想できるかどうか見出すことにより隣接セグメントＳｉ及びＳｊの対について合体動作を実行する。運動係数の１つのベクトルを用いて合成セグメントの領域をコード化することができ、しかも、予想エラーとして定義される歪が著しく増加せず、ひいては、再構成エラーと送信ビット数との間に良好な妥協が得られる場合には、これらのセグメントが合体される。マトリクス演算においては、最初に、マトリクス式が形成され、その後、既知のマトリクス計算方法を用いて因数マトリクスが処理される。それにより得られるマトリクス式では、１つのマトリクスに含まれた項に基づき、合体セグメントの領域で２乗予想エラーが容易に計算される。
【００１２】
全てのセグメント対が考慮された後に、セグメント合体ブロック２の出力は、次のようになる。
ｉ．減少されたセグメント数での像の新たな分割。
ii．新たなセグメントごとに、ブロックは、マトリクスＲ１ｋ、ベクトルｚ１ｋを出力する。
iii.デコーダに送られ、そして合体されたセグメントを識別する上でデコーダの助けとなる合体情報。
全体的に、運動フィールドコード化ブロックの出力は、次の通りである。
−  像のセグメント化を示す情報、
−  係数がデコーダに送信されることに関する情報、及び
−  送信された運動係数についての量子化値。
運動フィールドコード化は、エンコーダが到来レートでデータを処理できるように計算上簡単であるのが重要である。
【００１３】
【発明の開示】
本発明は、上述した運動フィールドコード化システムに変更を導入することを提案する。
従って、本発明は、その１つの観点において、映像データを動き補償エンコードするための映像コーデックであって、この映像コーデックは、基準フレームに対してコード化されるべき現在フレームの映像ピクセルの運動ベクトルフィールドを与え、そしてこの運動ベクトルフィールドをコード化して圧縮された運動情報を発生するための運動フィールドコーダを有し、この運動フィールドコーダは、現在フレームの各セグメントｋに対して近似マトリクスＥｋ及び近似ベクトルｑｋを計算して記憶するための手段を含む運動分析器を備え、各セグメントの歪に対して予め定められた尺度Δｅｋは、（Ｅｋｃｋ−ｑｋ）の関数であり、ｃｋは、上記運動ベクトルフィールドを、１組の多項式基礎関数ｆｎの運動係数ｃｎとして近似するベクトルであり、そして更に、上記運動フィールドコーダは、出力マトリクスＡｋ及び出力ベクトルｄｋを含む運動分析器出力パラメータを発生するための手段を備え、ここで、Ａｋは、Ｅｋの転置とＥｋとの積であり、そしてｄｋは、Ｅｋの転置とｑｋとの積である映像コーデックを提供する。
【００１４】
ここで、記号ｋは、映像フレームのセグメントを表す一般的な記号である。
本発明によれば、運動分析器における運動ベクトルフィールドの表示は、公知システムの場合とは異なり、そして実質的に低い計算上の複雑さで得ることができ、ひいては、計算能力、メモリをあまり必要とせず、そしてダウンサイジングを可能にする。より詳細には、これらの変更は、性能を妥協せずに計算を相当に簡単化し、ひいては、エンコードプロセスをスピードアップする。
好ましくは、運動フィールドコーダは、運動分析器の出力を受信するセグメント合体ブロックを備え、このセグメント合体ブロックは、共通の運動係数ベクトルを用いて合成領域におけるピクセル値を予想できる場合に隣接セグメントＳｉ及びＳｊの対を合体するための合体手段を備え、この合体手段は、次の一次式を解くことにより合体セグメントＳｋに対する共通の運動係数ベクトルｃｋを決定し、
Ａｋｃｋ＝ｄｋ
但し、Ａｋは、運動分析器出力マトリクスＡｉ及びＡｊの和により与えられる合体マトリクスであり、そしてｄｋは、セグメントＳｉ及びＳｊの運動分析器出力ベクトルｄｉ及びｄｊの和により与えられる合体ベクトルである。
【００１５】
このような運動助成合体の解決策は、運動係数の単一ベクトルを与え、合成セグメントを良好に予想できるようにする。
本発明の第２の観点においては、映像データを動き補償エンコードする方法であって、基準フレームに対してコード化されるべき現在フレームの映像ピクセルの運動ベクトルフィールドを与え、そして運動ベクトルフィールドをコード化して、圧縮された運動情報を形成することを含み、運動ベクトルフィールドの上記コード化は、各セグメントｋに対して近似マトリクスＥｋ及び近似ベクトルｑｋを計算して記憶することを含み、各セグメントの歪に対して予め定められた尺度Δｅｋは、（Ｅｋｃｋ−ｑｋ）の関数であり、ｃｋは、上記運動ベクトルフィールドを、１組の多項式基礎関数ｆｎの運動係数ｃｎとして近似するベクトルであり、そして更に、出力マトリクスＡｋ及び出力ベクトルｄｋを含む運動分析器出力パラメータを発生し、ここで、Ａｋは、Ｅｋの転置とＥｋとの積であり、そしてｄｋは、Ｅｋの転置とｑｋとの積である方法が提供される。
本発明は、更に、本発明の原理に基づいて動作するデコーダも含む。
【００１６】
【発明を実施するための最良の形態】
以下、添付図面を参照して、本発明を詳細に説明する。
0004573438.tif 000005
【００１７】
図５は、本発明による運動フィールドエンコーダの実施形態を示す。その入力は、基準フレーム及び現在フレームを含む。このブロックへの第３入力は、運動推定フィールドブロックにより形成された運動ベクトルフィールド［Δｘ(ｘ、ｙ)、Δｙ(ｘ、ｙ)］である。
このタスクを満足するために、運動フィールドエンコーダは、４つの主要構成ブロック、即ち運動分析ブロック１と、セグメント合体ブロック２と、直交化ブロック３と、運動係数除去ブロック４とで構成される。セグメント合体ブロック２と、直交化ブロック３と、運動係数除去ブロック４は、予想精度を下げ、ひいては、２乗予想エラーを高める運動情報の量を減少する。
【００１８】
運動分析器１の目的は、予想エラーに対するセグメント合体、直交化及び係数除去の影響を効率的に判断するのに適した運動フィールドの表示を見出すことである。この表示は、以下、合体されるセグメント及び係数除去に対して運動係数を迅速に柔軟に決定するために３つの後続ブロック（セグメント合体ブロック２、直交化ブロック３及び運動係数除去ブロック４）において使用される。図６は、本発明による運動分析器の実施形態を示す。
直交化ブロック３及び運動係数除去ブロック４は、ＰＣＴ公報ＷＯ９７／１６０２５号及びＷＯ９７／４０６２８号に開示されており、これらの説明を参考としてここに援用する。
【００１９】
運動分析器を説明すれば、各セグメントＳｋに対し、運動分析器は、次の動作を遂行する。
ステップ１．エラーの近似
0004573438.tif 000006
【００２０】
ステップ２．マトリクスの構成
式１３における２乗されるエレメントは、係数ｃｎの線形結合であるので、式１３を最小にすることは、次のマトリクス式を最小にすることに完全に等しい。  （Ｅｋｃｋ−ｑｋ）Ｔ（Ｅｋｃｋ−ｑｋ）                （１４）
但し、Ｅｋ、ｑｋ及びｃｋは、次の式で表される。
【数４】
0004573438.tif 000007
【００２１】
ステップ３．出力の計算
運動分析器１の出力は、次の通りである。
１）マトリクスＡｋ
Ａｋ＝ＥｋＴＥｋ          （１６）
２）ベクトルｄｋ
ｄｋ＝ＥｋＴｑｋ          （１７）
セグメント合体ブロック２で行われる合体動作は、共通運動係数ベクトルｃｋが新たなセグメントＳｋにおける選択されたエラー尺度の過剰な増加を招かないように２つのセグメントＳｉ及びＳｊを新たなセグメントＳｋに合成できるかどうかを決定する。
【００２２】
セグメントＳｉ及びＳｊの特定対について、合体動作は、次の段階で構成される。
ステップ１．共通運動係数の評価
本発明のこの好ましい実施形態は、一次方程式の系統を解くことによりｃｋを見つけられるという既に知られた特性を利用するものである。
Ａｋｃｋ＝ｄｋ                （１８）
但し、Ａｋ＝Ａｉ＋Ａｊ、ｄｋ＝ｄｉ＋ｄｊ          （１９）
Ａｉ、ｄｉ及びＡｊ、ｄｊは、各々、セグメントＳｉ及びＳｊに対し運動分析ブロック１により発生される。
ステップ２．セグメントの合体
運動係数ベクトルｃｎを使用して、セグメントＳｉ及びＳｊを合体できるかどうか判断される。それらが合体される場合には、新たに形成されるセグメントＳｋのマトリクスＡｋ及びベクトルｄｋが式（１９）に基づいて計算され、即ち
Ａｋ＝Ａｉ＋Ａｊ、ｄｋ＝ｄｉ＋ｄｊ          （２０）
となる。ステップ１−２は、全ての隣接セグメント対に適用される。
【００２３】
セグメント合体の後に得られる新たなセグメントの各セグメントＳｋに対して次の値が計算される。
0004573438.tif 000008
【００２４】
好ましい実施形態では、次の多項式基礎関数ｆｎが使用される。
ｆ１(ｘ、ｙ)＝ｆ４(ｘ、ｙ)＝１、
ｆ２(ｘ、ｙ)＝ｆ５(ｘ、ｙ)＝ｙ、              （２３）
ｆ３(ｘ、ｙ)＝ｆ６(ｘ、ｙ)＝ｘ
線形化段階は、次のものに関してＲrefの一次テイラー拡張を使用することにより行われる。
ｘｉ’＝ｘｉ＋Δｘ(ｘｉ、ｙｉ)
ｙｉ’＝ｙｉ＋Δｙ(ｘｉ、ｙｉ)              （２４）
ｘ及びｙに対しては、
【数５】
0004573438.tif 000009
【００２５】
共通の運動係数評価は、次のように行われる。
式１８を次のようにして解く。
0004573438.tif 000010
セグメントの合体は、次のように行われる。
セグメントＳｋのラグランジュコストは、次のように定義される。
Ｌ(Ｓｋ)＝Ｄ(Ｓｋ)＋λＲ(Ｓｋ)            （３１）
【００２６】
歪Ｄ(Ｓｋ)は、元のセグメントとコード化されたセグメントとの間の２乗エラーである。セグメントは、運動係数ベクトルｃｋを使用してそれを予想し、その後、予想エラーを圧縮することによりコード化される。２次元（２Ｄ）の離散的コサイン変換（ＤＣＴ）を使用して、予想エラーを圧縮する。レートＲ(Ｓｋ)は、運動係数及びＤＣＴ係数をコード化する際に消費したビットの数に等しい。パラメータλは、コード化されたフレームのクオリティと、その圧縮に必要なビット数との間の妥協パラメータを与える所定値を有する。
セグメントＳｉ及びＳｊを合体すべきかどうか判断するために、これらセグメントが１つのセグメントＳｋに合体される場合のラグランジュコストΔＬｉｊの減少が基準として使用される。
ΔＬｉｊ＝(Ｌ(Ｓｉ)＋Ｌ(Ｓｊ))−Ｌ(Ｓｋ)          （３２）
セグメントＳｋの予想を得るのに必要な運動係数は、式１８を用いて計算される。
【００２７】
セグメント合体手順は、初期のセグメント化からスタートし、そして手順は、次のように進む。
１）おそらく負のスレッシュホールドより小さいΔＬｉｊを有する隣接セグメントＳｉ及びＳｊの対を「非隣接セグメント」として定義する。（この段階は、以下の段階４で行われる更新の回数が著しく減少するために全体的な計算コストを低減する上で特に重要である。）
２）全ての対の中でラグランジュコストの最も減少した隣接セグメントの対を見出す。
３）この減少が０より大きい場合には、それらのセグメントを合体する。
４）新たに合体されるセグメントのインデックスをｋと仮定すれば、新たに形成されるセグメントＳｋの全隣接セグメントＳｌ（ｌ＝１、・・Ｌ）に対するラグランジュコストΔｋｌの減少を次のように再計算する。
ａ）ｌ＝１、・・Ｌの場合に、セグメントＳｋ及びＳｌの合成領域における２乗予想エラーΔｅｋｌの増加は、それらが合体されて新たなセグメントＳｍを形成する場合に、次のように計算される。
【数６】
0004573438.tif 000011
【００２８】
ｂ）ラグランジュコストの減少は、２乗予想エラーの増加が最も小さいセグメントから、２乗予想エラーの増加が最も大きいセグメントへと進めて計算される。この計算は、ΔＬｋｌが正で且つΔｅｋｌがおそらく適応スレッシュホールドより大きいセグメントＳｌに遭遇した場合に停止される。残りのセグメントについては、ラグランジュコストの減少が、ある負の値にセットされる。
５）考えられる全ての対のラグランジュコスト減少が負になるまで、段階１−３を繰り返す。
セグメントＳｉ及びＳｊを１つのセグメントＳｋに合体することによる予想エラーの増加が所定のスレッシュホールドより小さい場合には、式１９を使用してマトリクスＡｋ及びベクトルｄｋが再計算され、そして式１８を使用して共通運動係数ベクトルｃｋが計算される。さもなくば、
１）運動推定を用いてセグメントＳｋの運動係数ベクトルｃｋが見出され、
２）式１６−１７を用いてマトリクスＡｋ及びベクトルｄｋが再計算される。
【００２９】
ピクセル値の評価においては、Ｒref(ｘ、ｙ)の値が整数座標ｘ及びｙについてのみ定義される。動き補償予想が、基準フレームＲrefの非整数位置(ｘ、ｙ)におけるルミナンス及びクロミナンス値を評価する必要があるときには、立体コンボリューション補間が使用される。ｘ及びｙ方向の像導関数Ｇｘ(ｘ、ｙ)及びＧｙ(ｘ、ｙ)も、立体コンボリューションを用いて計算される。立体コンボリューション補間により得られる連続関数の導関数が計算され、そしてそれらが像導関数として解釈される。
本発明は、その本質的な属性から逸脱せずに他の特定の形態でも実施することができる。従って、本発明の範囲を示すものとしては、上記説明ではなく、特許請求の範囲及び他の一般的な記述を参照されたい。
【００３０】
システムは、次のような種々のやり方で実施することができる。
１）異なる多項式基礎関数を式１１に使用することができる。
２）式１２の線形化を行うのに異なる方法を使用できる。
３）２つのセグメントを合体すべきか又は合体すべきでないかを判断するのに異なる基準を使用できる。
４）１組の式１８を解くのに異なる方法を使用できる。
更に、本明細書（請求の範囲も含む）で説明され及び／又は添付図面に示された各特徴は、他の開示及び／又は図示された特徴とは独立して本発明に組み込まれる。この点について、本発明は、それが請求の範囲に記載した発明に関するものであるか又は該当する問題の全部又はいずれかを軽減するものであるかに関わらず、ここに明白に開示された新規な特徴又は特徴の組合せ、或いはその一般性を包含するものとする。
【図面の簡単な説明】
【図１】  既知のエンコーダの回路図である。
【図２】  既知のデコーダの回路図である。
【図３ａ】  ブロックベースの動き補償のための現在フレームの分割を示す図である。
【図３ｂ】  セグメントベースの動き補償のための現在フレームの分割を示す図である。
【図４】  公知の運動フィールドコード化システムの回路図である。
【図５】  本発明の好ましい実施形態に基づく運動フィールドコード化システムの回路図である。
【図６】  図５の実施形態に基づく運動分析器の回路図である。
【図１】
0004573438.tif 000016
【図２】
0004573438.tif 000017
【図３】
0004573438.tif 000018
【図４】
0004573438.tif 000019
【図５】
0004573438.tif 000020
【図６】
0004573438.tif 000021