(57)【特許請求の範囲】
【請求項１】
ビデオ・データの動き補償エンコーディングを行うためのエンコーダであって、
第１のビデオ・データフレームInと基準フレームRrefを受け取るための入力部を持ち、ビデオ・フレームピクセルの場面の動き変位を記述する動きベクトルフィールド（ΔＸ、ΔＹ）を推定するようになっている動きフィールド推定手段であって、前記第１のビデオ・フレーム、前記動きベクトルフィールド及び前記基準フレームRrefを出力するための出力部を持つ前記動きフィールド推定手段（２）と、
前記動きフィールド推定手段から前記の第１の推定された動きベクトルフィールドを受け取る入力部と、一つのビデオ・フレームの少なくとも二つの、第１のセグメントSiと第２のセグメントSjである複数のセグメントへの分割と、前記第１のビデオ・データフレームと前記基準フレームRrefとを持つ動きフィールドエンコード手段であって、前記動きベクトルフィールドを表す第１の動き係数から成る圧縮された動き情報を得るようになっている前記動きフィールドエンコード手段（３）と、
前記基準フレームRrefと前記圧縮された動き情報に基づいて予測ビデオ・データフレームを予測するための動き補償予測手段（１）と、
前記第１のビデオ・データフレームと前記予測されたビデオ・データフレームを受け取るための入力部を持つ計算手段であって、前記予測されたビデオ・データフレームと前記第１のビデオ・データフレームに基づいて予測誤差フレームを計算するようになっている前記計算手段（６）と、
前記予測誤差フレームをエンコードするための予測誤差エンコード手段（４）と、
前記動き係数と前記予測誤差フレームをデコーダへ伝えるための手段（８）と、
を有するエンコーダにおいて、
前記動きエンコード手段がさらに、
多項式基本関数fiの集合の係数ciとして前記動きベクトルフィールドを近似させることに起因する、各セグメントの中の歪みを表す所定の尺度ΔＥが、（Ｅ  ｃ−ｙ）の関数（但しｃは前記動き係数ciのベクトル）となるように、各セグメントについて歪み行列Ｅと歪みベクトルｙを計算して格納するための手段（41、42、45）と、
det Ｑ≠０、かつ
Ｑ  Ｒ＝Ｅ、
となるように第１の行列Ｑと第２の行列Ｒに前記歪み行列Ｅを分解するための手段であって、行列Ｑの全ての列の集合の部分集合が、行列Ｅの全ての列ベクトルの全ての可能な線形結合によって定義されるベクトル空間の基礎となり、行列Ｑの列が互いに直交するようになっている手段（43）と、
ｚ＝Ｑ-1ｙ（但しＱ-1は前記第１の行列Ｑの逆行列）に従って補助ベクトルｚを計算するための手段（46）と、
追加列として行列Ｒの列とベクトルｚから成る列拡張行列Ａを各セグメントについて生成するための手段であって、行列Ｒに起因する全ての列内にあるゼロに等しくない要素を持つ行列Ａの全ての行を選択するための手段（44、47）と、
ある限度内で前記予測誤差を増大させるセグメントの選択的結合に基づいてセグメントを合併するための手段（32）と、
前記第１のセグメントSiの行列Ａの前記選択された行及び前記第２のセグメントSjの行列Ａの前記選択された行から成る行拡張行列Ｂを生成するための手段（32）と、
行列Ｒに起因する列の中にできるだけ多くのゼロで満たされた行を持つ修正された行列Ｂ’を得るために、ゼロに等しくないスカラーを持つ行列Ｂの行の一連の掛算と行列Ｂの行の加算を行うための手段（32）と、
入力行列Ｍとして前記行列Ａ、Ｂ及びＢ’の内の一つを受け取る直交化手段であって、直交する基本関数
0003790804.tif 000070
によって前記多項式基本関数をfiと置換し、前記直交する基本関数と前記入力行列Ｍを用いて第２の動き係数
0003790804.tif 000071
を計算するようになっている前記直交化手段と、
前記第２の動き係数
0003790804.tif 000072
を量子化するための量子化手段と、
を有することを特徴とするエンコーダ。
【請求項２】
ビデオ・データの動き補償エンコーディングを行うためのエンコーダであって、
第１のビデオ・データフレームInと基準フレームRrefを受け取るための入力部を持ち、ビデオ・フレームピクセルの場面の動き変位を記述する動きベクトルフィールド（ΔＸ、ΔＹ）を推定するようになっている動きフィールド推定手段であって、前記第１のビデオ・フレーム、前記動きベクトルフィールド及び前記基準フレームRrefを出力するための出力部を持つ前記動きフィールド推定手段（２）と、
前記動きフィールド推定手段から前記の第１の推定された動きベクトルフィールドを受け取る入力部と、一つのビデオ・フレームの少なくとも二つの、第１のセグメントSiと第２のセグメントSjである複数のセグメントへの分割と、前記第１のビデオ・データフレームと前記基準フレームRrefとを持つ動きフィールドエンコード手段であって、前記動きベクトルフィールドを表す第１の動き係数から成る圧縮された動き情報を得るようになっている前記動きフィールドエンコード手段（３）と、
前記基準フレームRrefと前記圧縮された動き情報に基づいて予測ビデオ・データフレームを予測するための動き補償予測手段（１）と、
前記第１のビデオ・データフレームと前記予測されたビデオ・データフレームを受け取るための入力部を持つ計算手段であって、前記予測されたビデオ・データフレームと前記第１のビデオ・データフレームに基づいて予測誤差フレームを計算するようになっている前記計算手段（６）と、
前記予測誤差フレームをエンコードするための予測誤差エンコード手段（４）と、
前記動き係数と前記予測誤差フレームをデコーダへ伝えるための手段（８）と、
を有するエンコーダにおいて、
前記動きエンコード手段がさらに、
多項式基本関数fiの集合の係数ciとして前記動きベクトルフィールドを近似させることに起因する、各セグメントの中の歪みを表す所定の尺度ΔＥが、（Ｅ  ｃ−ｙ）の関数（但しｃは前記動き係数ciのベクトル）となるように、各セグメントについて歪み行列Ｅと歪みベクトルｙを計算して格納するための手段（41、42、45）と、
det Ｑ≠０、かつ
Ｑ  Ｒ＝Ｅ、
となるように第１の行列Ｑと第２の行列Ｒに前記歪み行列Ｅを分解するための手段であって、行列Ｑの全ての列の集合の部分集合が、行列Ｅの全ての列ベクトルの全ての可能な線形結合によって定義されるベクトル空間の基礎となり、行列Ｑの列が互いに直交するようになっている手段（43）と、
ｚ＝Ｑ-1ｙ（但しＱ-1は前記第１の行列Ｑの逆行列）に従って補助ベクトルｚを計算するための手段（46）と、
追加列として行列Ｒの列とベクトルｚから成る列拡張行列Ａを各セグメントについて生成するための手段であって、行列Ｒに起因する全ての列内にあるゼロに等しくない要素を持つ行列Ａの全ての行を選択するための手段（44、47）と、
ある限度内で前記予測誤差を増大させるセグメントの選択的結合に基づいてセグメントを合併するための手段（32）と、
前記第１のセグメントSiの行列Ａの前記選択された行及び前記第２のセグメントSjの行列Ａの前記選択された行から成る行拡張行列Ｂを生成するための手段（32）と、
行列Ｒに起因する列の中にできるだけ多くのゼロで満たされた行を持つ修正された行列Ｂ’を得るために、ゼロに等しくないスカラーを持つ行列Ｂの行の一連の掛算と行列Ｂの行の加算を行うための手段（32）と、
入力行列Ｍとして前記行列Ａ、Ｂ及びＢ’の内の一つを受け取る直交化手段であって、直交する基本関数
0003790804.tif 000073
によって前記多項式基本関数をfiと置換し、前記直交する基本関数に対応して前記入力行列を第３の行列
0003790804.tif 000074
へ修正するようになっている前記直交化手段と、
前記第３の行列
0003790804.tif 000075
を受け取るための入力部を持つ除去手段であって、前記除去手段が、前記基本関数のｉ番目の基本関数に対応してＲに起因するｉ番目の列を前記第３の行列から除去することによって、前記第３の行列を修正するようになっていて、行列
0003790804.tif 000076
を生成する出力部を有する前記除去手段（33）と、
前記第４の行列
0003790804.tif 000077
を用いて第２の動き係数
0003790804.tif 000078
を計算するための手段と、
前記第２の動き係数
0003790804.tif 000079
を量子化するための量子化手段と、
を有することを特徴とするエンコーダ。
【請求項３】
前記直交化手段が、直交する基本関数
0003790804.tif 000080
を多項式基本関数fk（・）、ｋ＝１，２，…，ｉ、の線形結合として選択する手段を有し、ここで、
0003790804.tif 000081
（ここで、ｉとｋは添字、ｔ値は乗数、Ｎ＋Ｍは所定のセグメントの動きベクトルフィールドを表す係数の数を示す。）
であることを特徴とする請求項１に記載のエンコーダ。
【請求項４】
前記直交化手段が、直交する基本関数
0003790804.tif 000082
を多項式基本関数fk（・）、ｋ＝１，２，…，ｉ、の線形結合として選択する手段を有し、ここで、
0003790804.tif 000083
（ここで、ｉとｋは添字、ｔ値は乗数、Ｎ＋Ｍは所定のセグメントの動きベクトルフィールドを表す係数の数を示す。）
であることを特徴とする請求項２に記載のエンコーダ。
【請求項５】
前記動きフィールドエンコード手段がさらに、
以下の関係式を用いて
0003790804.tif 000084
を計算するための手段を有し、すなわち、
0003790804.tif 000085
ここで、行列Ｒ1が、前記行列Ｒに起因する前記行列Ｍの列を含み、かつ、
前記ベクトルｚ1がベクトルｚに起因する行列Ｍの列を含む、
ことを特徴とする請求項３に記載のエンコーダ。
【請求項６】
前記動きフィールドエンコード手段がさらに、
以下の関係式を満たす行列
0003790804.tif 000086
とベクトル
0003790804.tif 000087
を計算するための手段を有し、すなわち、
0003790804.tif 000088
ここで、行列Ｒ1が、前記行列Ｒに起因する前記行列Ｍの列を含み、
前記ベクトルｚ1がベクトルｚに起因する行列Ｍの列を含み、かつ、
以下の関係式にしたがって
0003790804.tif 000089
を計算するための手段を有し、すなわち、
0003790804.tif 000090
ここで、行列
0003790804.tif 000091
が、前記行列Ｒに起因する前記行列
0003790804.tif 000092
の列を含み、
ベクトル
0003790804.tif 000093
が前記ベクトルｚに起因する行列
0003790804.tif 000094
の列を含む、
ことを特徴とする請求項４に記載のエンコーダ。
【請求項７】
ビデオ・データの動き補償エンコーディングの方法であって、
ａ）第１のビデオ・データフレームInと基準フレームとを受け取り、ビデオ・フレームピクセルの場面の動き変位を記述する動きベクトルフィールド（ΔＸ、ΔＹ）を推定し、前記第１のビデオ・フレーム、前記動きベクトルフィールド及び基準フレームRrefを出力し、
ｂ）前記動きベクトルフィールドを表す第１の動き係数を有する圧縮された動き情報を得るために、前記第１の推定された動きベクトルフィールドと、一つのビデオ・フレームの少なくとも二つの、第１のセグメントSiと第２のセグメントSjである複数のセグメントへの分割と、前記第１のビデオ・データフレームと前記基準フレームRrefとを受け取り、
ｃ）前記基準フレームRrefと前記圧縮された動き情報とに基づいて予測されたビデオ・データフレームを予測し、
ｄ）前記予測されたビデオ・データフレームと前記第１のビデオ・データフレームとに基づいて予測誤差フレームを計算するために、前記第１のビデオ・データフレームを受け取り、
ｅ）前記予測誤差フレームをエンコードし、
ｆ）前記動き係数と前記予測誤差フレームをデコーダへ伝える各ステップを有する方法において、
前記方法がさらに、
ｇ）多項式基本関数fiの集合の係数ciとして前記動きベクトルフィールドを近似させることに起因する、各セグメントの中の歪みを表す所定の尺度ΔＥが、（Ｅ  ｃ−ｙ）の関数（但しｃは前記動き係数ciのベクトル）となるように、各セグメントについて歪み行列Ｅと歪みベクトルｙを計算して格納し、
ｈ）det Ｑ≠０、かつ
Ｑ  Ｒ＝Ｅ、
となるように第１の行列Ｑと第２の行列Ｒに前記歪み行列Ｅを分解し、行列Ｑの全ての列の集合の部分集合が、行列Ｅの全ての列ベクトルの全ての可能な線形結合によって定義されるベクトル空間の基礎となり、行列Ｑの列が互いに直交するようにし、
ｉ）ｚ＝Ｑ-1ｙ（但しＱ-1は前記第１の行列Ｑの逆行列）に従って補助ベクトルｚを計算し、
ｊ）追加列として行列Ｒの列とベクトルｚから成る列拡張行列Ａを各セグメントについて生成し、行列Ｒに起因する全ての列内にあるゼロに等しくない要素を持つ行列Ａの全ての行を選択し、
ｋ）ある限度内で前記予測誤差を増大させるセグメントの選択的結合に基づいてセグメントを合併し、
ｌ）前記第１のセグメントSiの行列Ａの前記選択された行及び前記第２のセグメントSjの行列Ａの前記選択された行から成る行拡張行列Ｂを生成し、
ｍ）行列Ｒに起因する列の中にできるだけ多くのゼロで満たされた行を持つ修正された行列Ｂ’を得るために、ゼロに等しくないスカラーを持つ行列Ｂの行の一連の掛算と行列Ｂの行の加算を行い、
ｏ）直交する基本関数
0003790804.tif 000095
によって前記多項式基本関数をfiと置換し、前記直交する基本関数と入力行列Ｍを用いて第２の動き係数
0003790804.tif 000096
を計算するために、前記入力行列Ｍとして前記行列Ａ、Ｂ及びＢ’の中の一つを受け取り、さらに、
ｑ）前記第２の動き係数
0003790804.tif 000097
を受け取り、量子化する、
各ステップを有することを特徴とする方法。
【請求項８】
ビデオ・データの動き補償エンコーディングの方法であって、
ａ）第１のビデオ・データフレームInと基準フレームとを受け取り、ビデオ・フレームピクセルの場面の動き変位を記述する動きベクトルフィールド（ΔＸ、ΔＹ）を推定し、前記第１のビデオ・フレーム、前記動きベクトルフィールド及び基準フレームRrefを出力し、
ｂ）前記動きベクトルフィールドを表す第１の動き係数を有する圧縮された動き情報を得るために、前記第１の推定された動きベクトルフィールドと、一つのビデオ・フレームの少なくとも二つの、第１のセグメントSiと第２のセグメントSjである複数のセグメントへの分割と、前記第１のビデオ・データフレームと前記基準フレームRrefとを受け取り、
ｃ）前記基準フレームRrefと前記圧縮された動き情報とに基づいて予測されたビデオ・データフレームを予測し、
ｄ）前記予測されたビデオ・データフレームと前記第１のビデオ・データフレームとに基づいて予測誤差フレームを計算するために、前記第１のビデオ・データフレームを受け取り、
ｅ）前記予測誤差フレームをエンコードし、
ｆ）前記動き係数と前記予測誤差フレームをデコーダへ伝える各ステップを有する方法において、
前記方法がさらに、
ｇ）多項式基本関数fiの集合の係数ciとして前記動きベクトルフィールドを近似させることに起因する、各セグメントの中の歪みを表す所定の尺度ΔＥが、（Ｅ  ｃ−ｙ）の関数（但しｃは前記動き係数ciのベクトル）となるように、各セグメントについて歪み行列Ｅと歪みベクトルｙを計算して格納し、
ｈ）
det Ｑ≠０、かつ
Ｑ  Ｒ＝Ｅ、
となるように第１の行列Ｑと第２の行列Ｒに前記歪み行列Ｅを分解し、行列Ｑの全ての列の集合の部分集合が、行列Ｅの全ての列ベクトルの全ての可能な線形結合によって定義されるベクトル空間の基礎となり、行列Ｑの列が互いに直交するようにし、
ｉ）ｚ＝Ｑ-1ｙ（但しＱ-1は前記第１の行列Ｑの逆行列）に従って補助ベクトルｚを計算し、
ｊ）追加列として行列Ｒの列とベクトルｚから成る列拡張行列Ａを各セグメントについて生成し、行列Ｒに起因する全ての列内にあるゼロに等しくない要素を持つ行列Ａの全ての行を選択し、
ｋ）ある限度内で前記予測誤差を増大させるセグメントの選択的結合に基づいてセグメントを合併し、
ｌ）前記第１のセグメントSiの行列Ａの前記選択された行及び前記第２のセグメントSjの行列Ａの前記選択された行から成る行拡張行列Ｂを生成し、
ｍ）行列Ｒに起因する列の中にできるだけ多くのゼロで満たされた行を持つ修正された行列Ｂ’を得るために、ゼロに等しくないスカラーを持つ行列Ｂの行の一連の掛算と行列Ｂの行の加算を行い、
ｎ）入力行列Ｍとして前記行列Ａ、Ｂ及びＢ’の中の一つを受け取り、前記直交化手段が直交する基本関数
0003790804.tif 000098
によって前記多項式基本関数をfiと置換し、前記直交する基本関数に対応して前記入力行列を第３の行列
0003790804.tif 000099
に修正するようにし、
ｏ）前記第３の行列
0003790804.tif 000100
を受け取り、前記基本関数のｉ番目の基本関数に対応して行列Ｒに起因するｉ番目の列を前記第３の行列
0003790804.tif 000101
から除去することによって前記第３の行列
0003790804.tif 000102
を第４の行列
0003790804.tif 000103
へ修正して、前記第４の行列
0003790804.tif 000104
を出力し、
ｐ）前記第４の行列
0003790804.tif 000105
を用いて第２の動き係数
0003790804.tif 000106
を計算し、
ｑ）前記第２の動き係数
0003790804.tif 000107
を受け取り、前記第２の動き係数
0003790804.tif 000108
を量子化する、
各ステップを有することを特徴とする方法。
【請求項９】
請求項７に記載のビデオデータの動き補償エンコーディングの方法において、前記方法がさらに、
直交する基本関数
0003790804.tif 000109
を多項式基本関数fk（・）、ｋ＝１，２，…，ｉ、の線形結合として選択するステップを有し、ここで、
0003790804.tif 000110
（ここで、ｉとｋは添字、ｔ値は乗数、Ｎ＋Ｍは所定のセグメントの動きベクトルフィールドを表す係数の数を示す。）
であることを特徴とする方法。
【請求項１０】
請求項８に記載のビデオデータの動き補償エンコーディングの方法において、前記方法がさらに、
直交する基本関数
0003790804.tif 000111
を多項式基本関数fk（・）、ｋ＝１，２，…，ｉ、の線形結合として選択するステップを有し、ここで、
0003790804.tif 000112
（ここで、ｉとｋは添字、ｔ値は乗数、Ｎ＋Ｍは所定のセグメントの動きベクトルフィールドを表す係数の数を示す。）
であることを特徴とする方法。
【請求項１１】
請求項９に記載のビデオデータの動き補償エンコーディングの方法において、前記方法がさらに、
以下の関係式を用いて
0003790804.tif 000113
を計算するステップを有し、すなわち、
0003790804.tif 000114
但し、
0003790804.tif 000115
ここで、行列Ｒ1が、前記行列Ｒに起因する前記行列Ｍの列を含み、かつ
ベクトルｚ1が前記ベクトルｚに起因する前記行列Ｍの列を含む、
ことを特徴とする方法。
【請求項１２】
請求項10に記載のビデオデータの動き補償エンコーディングの方法において、前記方法がさらに、
以下の関係式を満たす行列
0003790804.tif 000116
とベクトル
0003790804.tif 000117
を計算するステップを有し、すなわち、
0003790804.tif 000118
ここで、行列Ｒ1が、前記行列Ｒに起因する前記行列Ｍの列を含み、
前記ベクトルｚ1が前記ベクトルｚに起因する前記行列Ｍの列を含み、かつ、
以下の関係式にしたがって
0003790804.tif 000119
を計算するステップを有し、すなわち、
0003790804.tif 000120
ここで、行列
0003790804.tif 000121
が、前記行列Ｒに起因する前記行列
0003790804.tif 000122
の列を含み、
ベクトル
0003790804.tif 000123
が前記ベクトルｚに起因する行列
0003790804.tif 000124
の列を含む、
ことを特徴とする方法。
【請求項１３】
動き補償エンコードされたビデオ・データをデコードするためのデコーダにおいて、
前記デコーダが、
ビデオ・データフレームを格納するための手段と、
前記格納されたビデオ・データフレーム及び受け取った動き情報に基づいてビデオ・データフレームを予測する手段と、
受け取った予測誤差データをデコードし、予測誤差フレームを得るための手段と、
前記予測されたビデオ・データフレームと前記デコードされた予測誤差フレームに基づいて更新されたビデオ・データフレームを計算して出力し、前記格納手段に前記更新されたビデオ・データフレームを格納するための手段と、
を有し、ビデオ・データフレームを予測するための前記手段が、
以下のデータ、すなわち、前記更新されたビデオ・データフレームのセグメントSiへの分割に関するデータ、動きフィールド・モデル基本関数の集合からの基本関数の選択に関するデータ及び選択された基本関数の係数に関するデータの中の少なくとも二つに、受け取った動きデータを分離するための手段（11）と、
前記選択された基本関数と係数の線形結合から各セグメントSi中の前記動きベクトルフィールドを再構成するための手段（13）と、
前記再構成された動きベクトルフィールドに基づいて、また、前記格納されたビデオ・データフレームに基づいて前記予測フレームを計算するための手段と、
を有することを特徴とするデコーダ。
【請求項１４】
前記動きベクトル・フィールドを再構成するための前記手段（13）が、前記更新されたビデオ・データフレームの各セグメントSiについて、基本関数の前記集合の各構成要素の構造に関するデータを受け取るようになっていることを特徴とする請求項13に記載のデコーダ。
【請求項１５】
前記動きベクトル・フィールドを再構成するための前記手段（13）が、前記セグメントSiの形状によって決定される領域に関して互いに直交している各セグメントSiについて、動きフィールドモデル基本関数の前記集合を計算するようになっていることを特徴とする請求項13又は14に記載のデコーダ。
【請求項１６】
ビデオ・データの動き補償エンコーディングを行うためのエンコーダ及びビデオ・データの前記動き補償エンコーディングをデコードするためのデコーダを含む、ビデオ・データの処理システムにおいて、
前記エンコーダが、
第１のビデオ・データフレームInと基準フレームRrefを受け取るための入力部を持ち、ビデオ・フレームピクセルの場面の動き変位を記述する動きベクトルフィールド（ΔＸ、ΔＹ）を推定するようになっている動きフィールド推定手段であって、前記第１のビデオ・フレーム、前記動きベクトルフィールド及び前記基準フレームRrefを出力するための出力部を持つ前記動きフィールド推定手段（２）と、
前記動きフィールド推定手段から前記第１の推定された動きベクトルフィールドを受け取る入力部と、一つのビデオ・フレームの少なくとも二つの、第１のセグメントSiと第２のセグメントSjである複数のセグメントへの分割と、前記第１のビデオ・データフレームと前記基準フレームRrefとを持つ動きフィールドエンコード手段であって、前記動きベクトルフィールドを表す第１の動き係数から成る圧縮された動き情報を得るようになっている前記動きフィールドエンコード手段（３）と、
前記基準フレームRrefと前記圧縮された動き情報に基づいて予測ビデオ・データフレームを予測するための動き補償予測手段（１）と、
前記第１のビデオ・データフレームと前記予測されたビデオ・データフレームを受け取るための入力部を持つ計算手段であって、前記予測されたビデオ・データフレームと前記第１のビデオ・データフレームに基づいて予測誤差フレームを計算するようになっている前記計算手段（６）と、
前記予測誤差フレームをエンコードするための予測誤差エンコード手段（４）と、
前記動き係数と前記予測誤差フレームをデコーダへ伝えるための手段（８）とを有し、
前記動きエンコード手段がさらに、
多項式基本関数fiの集合の係数ciとして前記動きベクトルフィールドを近似させることに起因する、各セグメントの中の歪みを表す所定の尺度ΔＥが、（Ｅ  ｃ−ｙ）の関数（但しｃは前記動き係数ciのベクトル）となるように、各セグメントについて歪み行列Ｅと歪みベクトルｙを計算して格納するための手段（41、42、45）と、
det Ｑ≠０、かつ
Ｑ  Ｒ＝Ｅ、
となるように第１の行列Ｑと第２の行列Ｒに前記歪み行列Ｅを分解するための手段であって、行列Ｑの全ての列の集合の部分集合が、行列Ｅの全ての列ベクトルの全ての可能な線形結合によって定義されるベクトル空間の基礎となり、行列Ｑの列が互いに直交するようになっている手段（43）と、
ｚ＝Ｑ-1ｙ（但しＱ-1は前記第１の行列Ｑの逆行列）に従って補助ベクトルｚを計算するための手段（46）と、
追加列として行列Ｒの列とベクトルｚから成る列拡張行列Ａを各セグメントについて生成するための手段であって、行列Ｒに起因する全ての列内にあるゼロに等しくない要素を持つ行列Ａの全ての行を選択するための手段（44、47）と、
ある限度内で前記予測誤差を増大させるセグメントの選択的結合に基づいてセグメントを合併するための手段（32）と、
前記第１のセグメントSiの行列Ａの前記選択された行及び前記第２のセグメントSjの行列Ａの前記選択された行から成る行拡張行列Ｂを生成するための手段（32）と、
行列Ｒに起因する列の中にできるだけ多くのゼロで満たされた行を持つ修正された行列Ｂ’を得るために、ゼロに等しくないスカラーを持つ行列Ｂの行の一連の掛算と行列Ｂの行の加算を行うための手段（32）と、
入力行列Ｍとして前記行列Ａ、Ｂ及びＢ’の内の一つを受け取る直交化手段であって、直交する基本関数
0003790804.tif 000125
によって前記多項式基本関数をfiと置換し、前記直交する基本関数と前記入力行列Ｍを用いて第２の動き係数
0003790804.tif 000126
を計算するようになっている前記直交化手段と、
前記第２の係数
0003790804.tif 000127
を量子化するための量子化手段とを有し、かつ、
前記デコーダが、
ビデオ・データフレームを格納するための手段と、
前記格納されたビデオ・データフレーム及び受け取った動き情報に基づいてビデオ・データフレームを予測する手段と、
受け取った予測誤差データをデコードし、予測誤差フレームを得るための手段と、
前記予測されたビデオ・データフレームと前記デコードされた予測誤差フレームに基づいて更新されたビデオ・データフレームを計算して出力し、前記格納手段に前記更新されたビデオ・データフレームを格納するための手段とを有し、
ビデオ・データフレームを予測するための前記手段がさらに、
以下のデータ、すなわち、前記更新されたビデオ・データフレームのセグメントSiへの分割に関するデータ、動きフィールド・モデル基本関数の集合からの基本関数の選択に関するデータ及び選択された基本関数の係数に関するデータの中の少なくとも二つに、受け取った動きデータを分離するための手段（11）と、
前記選択された基本関数と係数の線形結合から各セグメントSi中の前記動きベクトルフィールドを再構成するための手段（13）と、
前記再構成された動きベクトルフィールドに基づいて、また、前記格納されたビデオ・データフレームに基づいて前記予測フレームを計算するための手段とを有する、
ことを特徴とするシステム。
【請求項１７】
ビデオ・データの動き補償エンコーディングを行うためのエンコーダ及びビデオ・データの前記動き補償エンコーディングをデコードするためのデコーダを含む、ビデオ・データの処理システムにおいて、
前記エンコーダが、
第１のビデオ・データフレームInと基準フレームRrefを受け取るための入力部を持ち、ビデオ・フレームピクセルの場面の動き変位を記述する動きベクトルフィールド（ΔＸ、ΔＹ）を推定するようになっている動きフィールド推定手段であって、前記第１のビデオ・フレーム、前記動きベクトルフィールド及び前記基準フレームRrefを出力するための出力部を持つ前記動きフィールド推定手段（２）と、
前記動きフィールド推定手段から前記第１の推定された動きベクトルフィールドを受け取る入力部と、一つのビデオ・フレームの少なくとも二つの、第１のセグメントSiと第２のセグメントSjである複数のセグメントへの分割と、前記第１のビデオ・データフレームと前記基準フレームRrefとを持つ動きフィールドエンコード手段であって、前記動きベクトルフィールドを表す第１の動き係数から成る圧縮された動き情報を得るようになっている前記動きフィールドエンコード手段（３）と、
前記基準フレームRrefと前記圧縮された動き情報に基づいて予測ビデオ・データフレームを予測するための動き補償予測手段（１）と、
前記第１のビデオ・データフレームと前記予測されたビデオ・データフレームを受け取るための入力部を持つ計算手段であって、前記予測されたビデオ・データフレームと前記第１のビデオ・データフレームに基づいて予測誤差フレームを計算するようになっている前記計算手段（６）と、
前記予測誤差フレームをエンコードするための予測誤差エンコード手段（４）と、
前記動き係数と前記予測誤差フレームをデコーダへ伝えるための手段（８）とを有し、
前記動きエンコード手段がさらに、
多項式基本関数fiの集合の係数ciとして前記動きベクトルフィールドを近似させることに起因する、各セグメントの中の歪みを表す所定の尺度ΔＥが、（Ｅ  ｃ−ｙ）の関数（但しｃは前記動き係数ciのベクトル）となるように、各セグメントについて歪み行列Ｅと歪みベクトルｙを計算して格納するための手段（41、42、45）と、
det Ｑ≠０、かつ
Ｑ  Ｒ＝Ｅ、
となるように第１の行列Ｑと第２の行列Ｒに前記歪み行列Ｅを分解するための手段であって、行列Ｑの全ての列の集合の部分集合が、行列Ｅの全ての列ベクトルの全ての可能な線形結合によって定義されるベクトル空間の基礎となり、行列Ｑの列が互いに直交するようになっている手段（43）と、
ｚ＝Ｑ-1ｙ（但しＱ-1は前記第１の行列Ｑの逆行列）に従って補助ベクトルｚを計算するための手段（46）と、
追加列として行列Ｒの列とベクトルｚから成る列拡張行列Ａを各セグメントについて生成するための手段であって、行列Ｒに起因する全ての列内にあるゼロに等しくない要素を持つ行列Ａの全ての行を選択するための手段（44、47）と、
ある限度内で前記予測誤差を増大させるセグメントの選択的結合に基づいてセグメントを合併するための手段（32）と、
前記第１のセグメントSiの行列Ａの前記選択された行及び前記第２のセグメントSjの行列Ａの前記選択された行から成る行拡張行列Ｂを生成するための手段（32）と、
行列Ｒに起因する列の中にできるだけ多くのゼロで満たされた行を持つ修正された行列Ｂ’を得るために、ゼロに等しくないスカラーを持つ行列Ｂの行の一連の掛算と行列Ｂの行の加算を行うための手段（32）と、
入力行列Ｍとして前記行列Ａ、Ｂ及びＢ’の内の一つを受け取る直交化手段であって、直交する基本関数
0003790804.tif 000128
によって前記多項式基本関数をfiと置換し、前記直交する基本関数に対応して前記入力行列を第３の行列
0003790804.tif 000129
へ修正するようになっている前記直交化手段と、
前記第３の行列
0003790804.tif 000130
を受け取るための入力部を持つ除去手段であって、前記除去手段が、前記基本関数のｉ番目の基本関数に対応してＲに起因するｉ番目の列を前記第３の行列から除去することによって、前記第３の行列を修正するようになっていて、行列
0003790804.tif 000131
を生成する出力部を有する前記除去手段（33）と、
前記第４の行列
0003790804.tif 000132
を用いて第２の動き係数
0003790804.tif 000133
を計算するための手段と、
前記第２の動き係数
0003790804.tif 000134
を量子化するための量子化手段とを有し、かつ、
前記デコーダが、
ビデオ・データフレームを格納するための手段と、
前記格納されたビデオ・データフレーム及び受け取った動き情報に基づいてビデオ・データフレームを予測する手段と、
受け取った予測誤差データをデコードし、予測誤差フレームを得るための手段と、
前記予測されたビデオ・データフレームと前記デコードされた予測誤差フレームに基づいて更新されたビデオ・データフレームを計算して出力し、前記格納手段に前記更新されたビデオ・データフレームを格納するための手段とを有し、
前記ビデオ・データフレームを予測するための前記手段がさらに、
以下のデータ、すなわち、前記更新されたビデオ・データフレームのセグメントSiへの分割に関するデータ、動きフィールド・モデル基本関数の集合からの基本関数の選択に関するデータ及び選択された基本関数の係数に関するデータの中の少なくとも二つに、受け取った動きデータを分離するための手段（11）と、
前記選択された基本関数と係数の線形結合から各セグメントSi中の前記動きベクトルフィールドを再構成するための手段（13）と、
前記再構成された動きベクトルフィールドに基づいて、また、前記格納されたビデオ・データフレームに基づいて前記予測フレームを計算するための手段とを有する、
ことを特徴とするシステム。
【請求項１８】
ビデオデータを前記エンコーダから前記デコーダへ伝える手段を有することを特徴とする請求項16又は17に記載のビデオデータ処理システム。
【請求項１９】
前記エンコーダによってエンコードされたビデオデータを格納する手段と、エンコードされたビデオデータを前記デコーダによって圧縮解除する手段とを有することを特徴とする請求項16又は17に記載のビデオデータ処理システム。
【発明の詳細な説明】
発明の分野
本発明は一般的にビデオ圧縮に関する。特に、本発明は、ビデオ・データの動き補償エンコーディング及びビデオ・データの動き補償エンコーディングを実行するエンコーダ及び方法に関する。本発明は、その様にエンコーディングされたビデオ・データをデコーディングするためのデコーダにも関する。
発明の背景
動き補償予測は大半のビデオ・コーディングスキームの重要な要素である。図１は動き補償を用いてビデオ・シーケンスを圧縮するためのエンコーダの略図である。このエンコーダの必須要素は動き補償予測ブロック１と、動き推定器２と、動きフィールド・コーダ３とである。動き補償ビデオ・エンコーダの動作原理は、現在のフレームと称されるコーディング（コード化）されるべき入ってきたフレームＩｎ（ｘ，ｙ）と、予測フレーム
0003790804.tif 000002
との差である予測誤差Ｅｎ（ｘ，ｙ）を圧縮するというものであり、ここで：
0003790804.tif 000003
である。予測フレーム
0003790804.tif 000004
は、動き補償予測ブロック１によって構成され、基準フレームと称される、前のフレーム又は既にコーディングされている
0003790804.tif 000005
と表示される他のフレームのピクセル値と、現在のフレームと基準フレームとの間のピクセルの推定された動きを記述する動きベクトルとを用いて作られる。動きベクトルは動きフィールド推定器２によって計算され、その結果としての動きベクトル・フィールドは、予測ブロック１に入力される前に何らかの方法でコーディングされる。予測フレームは次の通りとなる：
0003790804.tif 000006
数の対［Δｘ（ｘ，ｙ），Δｙ（ｘ，ｙ)］は現在のフレームの位置（ｘ，ｙ）のピクセルの動きベクトルと称され、Δｘ（ｘ，ｙ）とΔｙ（ｘ，ｙ)とはこのピクセルの水平変位及び垂直変位の値である。現在のフレームＩｎ（ｘ，ｙ）の中の全てのピクセルの動きベクトルの集合（セット）は動きベクトル・フィールドと称される。コーディングされた動きベクトル・フィールドも動き情報としてデコーダに送られる。
図２に示されているデコーダでは、現在のフレームＩｎ（ｙ，ｙ）の各ピクセルは、基準フレーム
0003790804.tif 000007
におけるピクセルの予測
0003790804.tif 000008
を発見することによって復元される。動き補償予測ブロック２１は、受け取った動き情報と基準フレーム
0003790804.tif 000009
とを使って予測フレームを作る（この絵では基準フレームは現在のフレームと同じである）。予測誤差デコーダ２２において、デコーディング（デコード）された予測誤差フレームＥｎ（ｘ，ｙ）が予測フレームと加算され、その結果は最初の現在のフレームＩｎである。
動き補償（motion compensated（ＭＣ））予測エンコーダの一般的目的は、デコーダに送る必要のある情報の量をなるべく少なくすることである。それは、例えばＥｎ(ｘ，ｙ）のエネルギーなど、測定される予測誤差の量をなるべく小さくすると共に、動きベクトル・フィールドを表すのに必要な情報の量をなるべく少なくするべきである。
Ｎ．グエン、Ｅ．デュボアの文献、即ち１９９０年３月２６−１８日、マサチューセッツ州ケンブリッジ市、画像コーディング・シンポジウム’９０議事録、８４１−８４５ページ、“イメージ・コーディングのための動き情報の表示”(N. Nguen, E. Dubois, "Representation of motion information for image coding". Proc. Picture Coding Symposium '90, Cambridge, Massachusetts, March 26-18, 1990, pages 841-845)は、動きフィールド・コーディング技術の概観を与えている。
目の子算と同じく、予測誤差を減少させるためには、より洗練された動きフィールドが必要である、即ちそれをエンコーディングするためにより多くのビットを使う必要がある。従って、ビデオ・エンコーディングの総合的目的は、予測誤差の尺度をなるべく低く保ちながら動きベクトル・フィールドをなるべくコンパクトにエンコーディング（エンコード）することである。
フレーム中のピクセルの数が非常に大きいので、各ピクセルについて別々の動きベクトルを送るのは効率的でない。むしろ、殆どのビデオ・コーディングスキームにおいて、少数のパラメータでセグメントのすべての動きベクトルを記述できるように、例えば図３に示されているように現在のフレームはイメージ・セグメントに分割される。各イメージ・セグメントは正方形ブロックであっても良い。例えば、国際規格ISO/IEC MPEG-1又はITU-T H.261に準拠するコーデックでは１６×１６ピクセルのブロックが使用されるが、ブロックは例えば分割アルゴリズムによって得られる完全に任意の形状の領域から成っていても良い。実際上、セグメントは少なくとも数十個のピクセルを含む。
図１の動きフィールド推定ブロック１は与えられたセグメントの全てのピクセルの動きベクトルを計算するが、それはそのセグメントの例えば二乗予測誤差などの予測誤差の何らかの尺度を最小にする。動きフィールド推定手法は、動きフィールドのモデルと、予測誤差の選択された尺度を最小にするためのアルゴリズムとの両方において種々様々である。
セグメント中のピクセルの動きベクトルをコンパクトに表示するために、それらの値を少数のパラメータの関数で記述するのが望ましい。その様な関数は動きベクトル・フィールド・モデルと称される。モデルの公知グループは線形動きモデルであり、そのモデルでは動きベクトルは動きフィールド基本関数の線形結合（組合わせ）で近似される。その様なモデルでは、イメージ・セグメントの動きベクトルは一般式：
0003790804.tif 000010
で記述され、ここでパラメータＣｉは動き係数と称されるものであって、デコーダに送られる。関数ｆｉ（ｘ，ｙ）は動きフィールド基本関数と称され、エンコーダ及びデコーダの両方に知られている一定の形を有する。
上記の式を有する線形動きモデルを用いるときの問題は、例えば予測誤差Ｅｎ（ｘ，ｙ）の選択された尺度などの、歪みの何らかの尺度をなるべく低く保ちながら、デコーダに送られる動き係数Ｃｉの個数を計算に関して単純な方法で如何にして最小限にするかということである。
デコーダに送る必要のある動き係数の総数はイメージ中のセグメントの個数と、セグメントあたりの動き係数の個数との両方に依存する。従って、動き係数の総数を減らす方法は少なくとも２つある。
第１の方法は、予測誤差を大きく増大させることなく共通の動きベクトル・フィールド・モデルで予測することのできるセグメントを結合させる（合併する）ことによってセグメントの個数を減らすことである。隣接する、すなわち隣り合うセグメントを同じ動き係数の集合（セット）で予測できることが非常に多くあるので、フレーム内のセグメントの個数を減らすことができる。その様なセグメント同士を結合させるプロセスは動き補助合併と称される。図３はセグメントに分割されたフレームを示している。動き係数コーディングを実行するための従来技術の手法として動き補助合併のための幾つかの手法がある。全てのセグメントの動きベクトルが推定された後、動き補助合併が実行される。それは、隣り合うセグメントＳｉ及びＳｊの全ての対をそれらの動き係数Ｃｉ及びＣｊと共に考慮することによって実行される。結合されたセグメントＳｉ及びＳｊの領域はＳｉｊと表示される。Ｓｉ及びＳｊを別々に予測した結果として生じる誤差と比べて予測誤差をあまり増大させることなく動き係数Ｃｉｊの１つの集合で領域Ｓｉｊを予測できるのであれば、Ｓｉ及びＳｊは合併される。動き補助合併を行う方法は、基本的に、互いに結合されるセグメントを良好に予測することを可能にする動き係数Ｃｉｊの単一の集合を見つけだす方法においてまちまちである。
１つの方法は全数動き推定による合併として知られている。この方法は、隣り合うセグメントＳｉ及びＳｊの全ての対について動きパラメータＣｉｊの新しい集合を“全くの無から”推定する。Ｓｉｊについての予測誤差があまり増えないならば、セグメントＳｉ及びＳｊは合併される。この方法は合併することのできるセグメントを非常に良好に選択できるけれども、エンコーダの複雑さを通常は数桁も大きくしてしまうので、具体化するのには適していない。
もう一つの方法は、動きフィールド拡張による合併として知られている。この方法は、予測誤差をあまり大きくすることなく動きパラメータＣｉ又はＣｊを用いてＳｉｊの領域を予測できるか否か試験する。この方法は、新しい動き推定を必要としないので、計算の複雑さが非常に低いことを特徴とする。けれども、１セグメントについて計算された係数での動き補償が隣りのセグメントをも良好に予測できることは非常に稀であるので、この方法ではセグメント同士を合併し損なうことが非常にしばしばある。
もう一つの方法は動きフィールドはめ込みによる合併として知られている。この方法では、近似の方法によって動き係数Ｃｉｊが計算される。これは、各セグメントで少数の動きベクトルを評価することによって実行される。セグメントＳｉ及びＳｊにおける幾つかの動きベクトルが図３に示されている。セグメントＳｉｊについての動きフィールドは公知の何らかのはめ込み方法を用いてこれらのベクトルを通して共通動きベクトル・フィールドをはめ込むことによって行われる。この方法の欠点は、はめ込みによって得られる動きフィールドが充分に精密ではなくて、予測誤差を許容できないほど増大させる結果をしばしばもたらすことである。
種々のモデルで動き推定を実行して最も適当な１つを選択する方法が音響学、会話及び信号処理に関する１９９４年度国際会議議事録ページIII265-268に載っている、H.ニコラス及びＣ．ラビットの“イメージ・シーケンス・コーディングのための決定論的緩和方式を用いる領域に基づく動き推定”（H. Nicolas and C. Labit, "Region-based motion estimation using deterministic relaxation schemes for image sequence coding, " Proc. 1994 International Conference on Acoustics, Speech and Signal Processing, pp. III265-268）と、ビデオ技術のための回路及びシステムに関するIEEE会報１９９４年６月第４巻第３号、ページ357-364に載っているＰ．チッコーニ及びH.ニコラスの“イメージ・シーケンス・コーディングのための領域に基づく効率的動き推定及び対称指向分割”（P. Cicconi and H. Nicolas, "Efficient region-based motion estimation and symmetry oriented segmentation for image sequence coding," IEEE Tran. on Circuits and Systems for Video Technology, Vol. 4, No. 3, June 1994, pp. 357-364）とにおいて提案されている。これらの方法は、種々のモデルで動き推定を行って最も適したものを１つ選択することによって動きの複雑さに依存する動きモデルを適合させようと試みる。これらの方法の主な欠点は、計算が非常に複雑で、実際に試験することのできる種々の動きフィールド・モデルの量が少ないことである。
動き係数の個数を最小限にするための第２の方法は、なるべく少ない係数で満足できるほど予測誤差を小さくすることを可能にする動きモデルを各セグメントのために選択することである。動きの量及び複雑さはフレーム毎に、またセグメント毎にまちまちであるので、常に１セグメントあたりにＮ＋Ｍ個の動き係数を全部使うのは効率的でない。どのセグメントについても、満足できるほど予測誤差を小さくすることを可能にする動き係数の最小数はどれほどかを見いだすことが必要である。この様な係数の適応的選択のプロセスは動き係数除去と称される。
上記の方法は、いずれも、単独では、予測誤差の前記尺度をなるべく低く保ちながら、デコーダに送られる動き係数Ｃｉの個数をどの様にして最小限にするかという問題を解決できない。
発明の概要
本発明の目的は、動きベクトル・フィールドを容認できないほど歪ませることなく、公知の動き推定器によって作られる動きベクトル・フィールド・データの量を大幅に減らすことを可能にする、動き補償ビデオ・エンコーダとビデオ・データの動き補償エンコーディングを行う方法と動き補償エンコーディング（エンコード）されたビデオ・データをデコーディング（デコード）するためのビデオ・デコーダとを作ることである。その動きフィールド・エンコーダは、入手可能な信号プロセッサ又は汎用マイクロプロセッサで実用的に実現できるように、あまり複雑でないのが好ましい。
本発明は、請求の範囲第１項、第１０項、第２０項、第２３項、第２６項及び第３９項において規定されているようにして、それぞれ、解決される。本発明の実施例は従属請求項において規定されている。本発明の第１の形態に準拠するエンコーダは、セグメント同士を合併させて、合併されたセグメントについて歪みの尺度を最小にする動き係数の集合を計算に関して効率よく見いだすことができる。本発明のこの形態は、希望に応じて、セグメント合併に起因する歪みを簡単に且つ効率よく評価することも可能にする。有利なことに、この形態に準拠するエンコーダは、追加の歪みを所定尺度に従って計算して、もしその追加の歪みが例えば与えられた閾値以下であったりして許容できるか或いは達成されるビットレート減少に関して許容できるならばセグメント同士を合併させることによって、ビデオ・フレームの隣り合うセグメント同士を適応的に合併させる。この歪みを計算するために選択される尺度は、例えば該セグメントにおけるエネルギー又は二乗予測誤差等の、予測誤差の何らかの尺度であって良いが、これに限定はされない。歪みについてのもう一つの尺度は、例えば原フレームと、エンコーディング及びデコーディングされた後に復元された原フレームとの二乗差である。この目的のために、ビデオ・エンコーダに含まれている動きフィールド・エンコーダは２つの主要なブロックから成っている。
第１の主要ブロックはＱＲ動き分析器と称することができる。その役割は動きフィールド推定器によって作られ入力された動きベクトル・フィールドの新しい表示を見いだすことである。その新しい表示は第２の主要ブロックに入力される。この第１の主要ブロックにおける動作は、行列演算から成る複数のステップを含んでいる。その第１ステップでは公知の何らかの近似方法によって予測フレームが線形化され、予測フレームは動きベクトルの線形関数となる。第２ステップでは、例えば二乗予測誤差などの予測誤差の適当な尺度を最小化するために行列Ｅｉと行列ｙｉとが作られる。この目的のために行列Ｅｉは２つの行列Ｑｉ及びＲｉの積に分解される。また、因子行列Ｑｉ及び行列ｙｉから補助ベクトルｚｉが計算される。行列Ｒｉの一部分と補助ベクトルｚｉとは第２の主要ブロックに入力される。
セグメント合併ブロックと称される第２の主要なブロックはセグメントＳｉ、Ｓｊの対について合併操作を行う。有利なことに、このブロックは、それらの結合された領域について共通動きフィールド・モデルを使ってそれらの結合された領域を予測できるか否か調べる。合併操作では、前記因子行列に基づいて始めに行列方程式が形成され、その後に該因子行列は公知の行列計算方法により処理される。その結果は、検討されているセグメント対について共通の動き係数を簡単且つ効率的に計算することを可能にする行列方程式である。これらの係数を使って、合併されたセグメントの領域での選択された歪みの尺度を計算することができる。歪みの尺度として二乗予測誤差を用いるならば、結果として得られる行列の１つに含まれている項に基づいてそれを容易に計算することができる。選択された基準に照らして予測誤差の前記尺度の変化が許容できるならば、該セグメント同士は合併される。
全てのセグメント対が検討された後、セグメント合併ブロックの出力は、セグメントの個数が減少したイメージの新しい分割態様である。更に、各々の新しいセグメントについて該ブロックは行列Ｒ1ｉｊとベクトルｚ1ｉｊを出力するが、それは全ての動き係数を簡単に且つ効率よく計算することを可能にする。また該エンコーダは、フレーム内の、結果として得られた新しいセグメントを復元できるようにする情報をデコーダに与える。
本発明のこの形態に準拠するセグメント合併ブロックは、セグメント同士を合併させて１つにすることができるか否か単純な計算で判定することを可能にする。隣り合うセグメント同士の各対について合併が可能か否か判定し、合併に適する隣り合うセグメント同士の対が該フレーム内に無くなるまで該フレームについての結果として得られる分割についてのこのプロセスを反復することによって、なるべく多くのセグメントの合併を達成することができる。
本発明の１実施例では、基本関数の線形結合により動きベクトル・フィールドを近似することに起因する追加の歪みの線形近似に基づいて歪みの量を計算することができる。
本発明の第２の形態に準拠するエンコーダは、セグメントの動きベクトル・フィールドを表す係数の集合から係数を除去して、歪みの尺度に関して最適の残りの係数を効率の良い計算で見いだすことを可能にする。また、希望に応じて、本発明は、この形態においては、この集合の特定の係数を省略すると動きフィールドの歪みが顕著に増大するか否かを調べることを可能にする。この調べは、各セグメントＳｉについて該集合のうちの各係数をその様に調べることができるように効率の良い計算で実行される。省略されれば歪みを顕著に増大させるということが分かった係数だけをデコーダに送ればよい。
第２の形態に準拠するエンコーダは、本発明の第１の形態に準拠する第１の主要ブロックと同様に動作する第１の主要ブロックを有する。それは更に第２のブロックを有し、このブロックは、全てのセグメントＳｉについて該第１のブロックにより作られた行列Ｒｉとベクトルｚｉとを受け取り、また希望に応じて、行列Ｒｉとベクトルｚｉとに基づいて、各セグメントについて歪みを耐え難いほど増大させることなく動きフィールド・モデルから基本関数を除去することによって該モデルを簡略化することが可能か否か判定する。
この第２のブロックにおける操作は行列操作であり、行列方程式は始めに行列方程式Ｒｉｃ＝ｚｉの１列及び１行を除去することにより修正されるが、このｃは該モデルの係数Ｃｉから成るベクトルである。１つの列及び行の除去は、動きモデルからの１つの基本関数の除去に対応する。その後、該行列方程式は三角化される。その結果として得られた線形方程式を解くことによって基本関数の縮小された集合に対応する動き係数を計算することができる。後退代入又はその他の周知のアルゴリズムによってその方程式を解くことができる。予測誤差を歪みの尺度として用いるならば、基本関数を除去したことからセグメントに生じるその変化は、その結果としての方程式の中の１項の単純な所定の関数である。
それらの行列操作を更に反復することによって該セグメントについてもっと多くの係数を減らすことができる。この様なアプローチにより、基本関数の種々の縮小された集合を用いるときに歪みを容易に発見することができる。所望の歪みをもたらす集合は該セグメントの動きを表すように選択される。
このブロックは、処理された全てのセグメントについて、どの基本関数が動きフィールド・モデルから除去されたかを知らせる選択情報を出力する。また、このブロックは、残っている基本関数に対応する新しい動き係数を出力する。選択情報及び動き係数の両方がデコーダに送られる。
基本関数の集合から基本関数を除去することは、除去された基本関数に対応する係数の値をゼロに設定することと完全に同等である。従って、代わりの具体的構成では、エンコーダは、選択情報を出力した後に動き係数を出力する代わりに全ての動き係数を出力し、そのうちの除去された基本関数に対応する係数の値はゼロに等しい。
好ましくは、動き補償ビデオ・エンコーダは、適応的にセグメントを合併することと、全体としての歪みに対して重要ではない動き係数を除去することとの両方を利用する。その様な好ましいエンコーダは、本発明の第１の形態に準拠するＱＲ動き分析器及びセグメント合併ブロックと共に本発明の第２の形態に準拠する係数除去ブロックを包含する。この係数除去ブロックは、セグメント合併ブロックから行列Ｒｉｊとベクトルｚｉｊとを受け取る。隣り合うセグメント同士を合併させ、係数除去のために行列Ｒ及びベクトルｚを操作した後にはじめて各セグメントの送信される係数Ｃｉが計算されて、その結果としてビデオ・エンコーダから出力される動きデータの量が実質的に減少する。
好ましくは、本発明のビデオ・エンコーダ及びデコーダは、本発明に従って、それぞれ、受け取ったビデオ・フレームのエンコーディング及び圧縮を行い、エンコーディングされたビデオ・データをデコーディングするようになっている、例えば１つ以上の集積回路として、ハードウェアで実現される。
ビデオ・コーディング技術では、異なるコーディング・モードを使ってビデオ・フレームの異なる領域をコーディングすることはありふれたことである。コーディング・モードのこの変化性は、コーデックスに使用される動き補償予測方法も含んでいる。ITU H.261及びH.263並びにISO MPEG-1及びMPEG-2ビデオ・コーディング規格などの全ての最新のビデオ・コーデックに幾つかのモードが用いられている。
例えば、一部のビデオ・フレーム領域は時間的予測を全く使わずにコーディングされる（いわゆるブロック内の）。その様なイメージ領域については動き係数は送られず、それらの領域は前のイメージを全く参照せずにコーディングされる。本発明の実用的実施例は、本発明をその様な内部コーディング（intra-coding）と組み合わせる。
更に、典型的なビデオ・イメージ・シーケンスでは、数フレームの存続期間にわたってビデオ・フレームの大きな領域が不動のままである（即ち、動きが無い）。計算に関しては、ビデオ・フレーム領域の動きを推定するよりは領域が不動のままであったということを検出する方がはるかに容易である。従って、実用的ビデオ・コーデックは、しばしば領域を調べて何らかの動きがあるかどうかを検出するようになっていて、動きパラメータを送る必要のない不動予測モードを含んでいる。本発明の実用的実施例は、本発明をその様な不動モードとも組み合わせる。
MPEGビデオ・コーディング規格は、２つの基準フレームに関して動き推定を行う（双方向予測）コーディング・モードも含んでいる。その結果として、コーディングされるべき領域について２つの異なった予測がもたらされる。エンコーダは、それらの予測のうちの良好な方を使用するように決定することができ、或いはエンコーダは（例えば、平均を取ることによって）それら２つの予測を組み合わせるように決定しても良い。モードに関する決定はデコーダに伝達されなければならない。ITU H.263規格は２つの基準フレームを用いる時間予測モードも含んでいる。本発明が多数の基準フレームを使用する類似の手法から利益を得ることができることは明らかである。
本発明がビデオ・コーデックにおける１つ以上のコーディング・モードのための基礎となって従来技術のコーディング・モード（内部コーディング、不動モード、或いは多数の基準フレームなど）と共に使用され得ることは当業者にとっては明らかである。
次に添付図面を参照して本発明の好ましい実施例について説明する。
【図面の簡単な説明】
図１は公知のエンコーダの概略図である。
図２は公知のデコーダの概略図である。
図３は合併される隣り合うセグメントを示す。
図４は動きフィールド近似による合併を示す。
図５は本発明による動きフィールド・コーダを示す。
図６はQR動き分析器の概略図である。
図７は本発明による動き補償予測ブロックの１実施例の概略図である。
好ましい実施形態の説明
図１に示されているビデオ・エンコーダの出力はセグメントＳｉに分割された圧縮されているフレームであり、各セグメントＳｉには、それぞれのセグメントの各ピクセル（ｘ，ｙ）についての動きベクトル［Δｘ（ｘ，ｙ）,Δｙ（ｘ，ｙ）］に関する情報が伴っている。座標（ｘｉ，ｙｉ），ｉ＝１，２，．．．，Pを有するＰ個のピクセルから成るセグメントＳｉについて、動きフィールド・エンコーダ３の任務は、動きフィールド推定ブロック２から出力された動きベクトル・フィールド（Δｘ（ｘｉ，ｙｉ），Δｙ（ｘｉ，ｙｉ））から、下記の形：
0003790804.tif 000011
の線形動きモデルによって、二乗予測誤差ＳＰＥ：
0003790804.tif 000012
を最小にするのに必要なだけの精度で［Δｘ（ｘ，ｙ），Δｙ（ｘ，ｙ）］を近似する動きベクトル・フィールド
0003790804.tif 000013
の動き係数ｃ＝（ｃ１、ｃ２，．．．，cＮ＋Ｍ）を発見することである。
図５は、本発明によるビデオ・エンコーダにおける動きフィールド・エンコーダの実施例を示している。これは図１のブロック３に対応するけれども、これは入力として基準フレームと現在のフレームも有する。このブロックへの第３の入力は図１の動きフィールド推定ブロック２によって作られた動きベクトル・フィールド［Δｘ(・)，Δｙ(・)］である。
前記任務を遂行するために、動きフィールド・エンコーダ３は、３つの主要な組立ブロック、即ちＱＲ動き分析器ブロック３１、セグメント合併ブロック３２及び動き係数除去ブロック３３、から成っている。セグメント合併ブロック３２と動き係数除去ブロック３３とは動き情報の量を減少させるが、それは予測の精度を低下させて二乗予測誤差を増大させるという結果をもたらす可能性がある。
ＱＲ動き分析器の目的は、セグメント合併と係数除去とが予測誤差に及ぼす影響の大きさを効率よく判定するのに適する動きフィールドの新しい表示を発見することである。この新しい表示は、合併されたセグメントについての動き係数を高速に且つ自在に発見するために、また係数除去のために、後に他の２つのブロックで使用される。図６は、本発明によるＱＲ動き分析器の実施例を示している。このブロックは、前のビデオ・フレーム入力I ｎ−１を受け取る、又はより好ましくは、図２に示されているビデオ・デコーダによりデコーディング（デコード）されたフレーム
0003790804.tif 000014
に似ている前のビデオ・フレーム
0003790804.tif 000015
を受け取る、勾配フィルタ４１を有する。この目的のために、図１のビデオ・エンコーダは、予測誤差デコーダ・ブロック５と、該ビデオ・デコーダによってデコーディング（デコード）されたビデオ・フレームに対応するビデオ・フレーム
0003790804.tif 000016
を計算するための手段７も有する。
該勾配フィルタの出力Ｇｘ、Ｇｙは、行列Ｅを組み立てるためのブロック４２と、ベクトルyを組み立てるためのブロック４５とに入力される。行列組立ブロック４２は、近似された予測フレームが
0003790804.tif 000017
の線形関数となるように予測フレーム
0003790804.tif 000018
の線形化を実行し、この線形化に基づいて行列Ｅを計算するが、この行列Ｅと上記の式４ａ、４ｂの各係数Ｃｉのベクトルｃとの掛け算は、もしΔｘ、Δｙを線形動きモデルの基本関数ｆｉ（ｘ，ｙ）の線形結合と置き換えたならば生じることになる予測誤差と解され得るものである。
ベクトルyを組み立てるためのブロック４５は、現在のフレームＩｎ、予測されたフレーム
0003790804.tif 000019
勾配フィルタ４１の出力Ｇｘ、Ｇｙ、及び図１のブロック２によって推定された動きベクトル［Δｘ（ｘ，ｙ），Δｙ（ｘ，ｙ）］を受け取り、これらの入力された正しい値から、場面（シーン）に動きがあったことに起因する予測誤差、即ち固有予測誤差、と解釈することのできる前記ベクトルｙを計算する。
行列Ｅとベクトルｙとは、それぞれ、ＱＲ因数分解器ブロック４３と行列掛け算器ブロック４６とに受け取られる。これらのブロックの機能は、与えられたセグメントの全てのピクセルについて基本関数ｆｉの線形結合としてのΔｘ、Δｙの表示から生じる予測誤差が固有予測誤差になるべく近くなるように係数Ｃｉを発見するための準備のための行列E及びベクトルｙの座標変換であると見なし得るものである。このことについて次に更に詳しく説明する。
ブロック４３は、ブロック４３から出力される行列Ｑの座標で行列Ｅを表示した結果としての行列Ｒを出力する。ブロック４６は、前記ベクトルｙだけではなくてブロック４３から前記行列Ｑも受け取り、行列Ｑの座標でｙを表示するベクトルｚを見いだす。好ましくは、行列Ｑは正規直交行列である。以下の記述で更に詳しく示すように、それぞれＲ及びｚとしてのこのＥ及びｙの表示は、隣り合うセグメント同士を予測誤差の容認できるような増加で合併することができるか否か判定するために非常に有利であり、また合併され又は合併されないセグメントの動きベクトル・フィールドを表示するのに必要な最小個数の係数を発見するのにも非常に有利である、即ち式４ａ、４ｂの各係数Ｃｉの集合から重要でない係数を除去するのに非常に有利である。
ブロック４４及び４７は、行列Ｒ及びベクトルｚをそれぞれ受け取って、これらからセグメント合併及び／又は動き係数除去の効果を判定するのに必要な行を選択する。それらの動作は、前記係数Ｃｉを計算することを必要とすることなくＲ及びｚに基づいて行われる。更に、セグメント合併及び／又は動き係数除去の目的のためにＲ及びｚを、Ｒの列を有すると共に追加の列としてベクトルｚを有する単一列拡張行列Ａと見なし得るように、全ての行操作はＲの行とｚの対応する行との両方に関連している。従って、ブロック４４及び４７は、Ａの適当な行を選択して行列Ａを操作し、Ａの選択された行から成る修正された行列Ａ'を出力する１つのブロックと見なして該１ブロックとして実現することのできるものである。Ａ'は、Ｒ1と表記されるＲの選択された行と、ｚ1と表記されるｚの選択された行とから成る。
セグメント合併ブロック３２は、各セグメントについてＲ1及びｚ1、即ち行列Ａ'、を受け取り、２つのセグメントＳｉ、Ｓｊの動きベクトル・フィールドを係数の同じ集合で表示することによる該２つのセグメントの合併が予測誤差を許容できる範囲で増大させる結果となるか否か判定する。これは、セグメントＳｉの行列Ａ'ｉの全ての行とセグメントＳｊの行列Ａ'ｊの全ての行とから成る行拡張行列Ｂを作ることによって実行される。セグメントＳｉ、Ｓｊは、隣り合っていても良いけれども必ずしも隣り合っていなくても良い。行列Ｂに対しては、例えば行列Ｂを三角化することによる更なる座標変換が行われ、修正された行列Ｂ'が得られる。図５のブロック３２は、行列Ｂ'の、ベクトルｚ'ｉ及びｚ'ｊからもたらされた列と行列Ｒ1ｉ及びＲ1ｊからもたらされたＢ'の列にゼロを有する行との中の選択された要素から、セグメント合併が可能か否か判定する。好ましくは、前記の更なる座標変換は正規直交変換である。その場合、合併からもたらされる追加の予測誤差は前記の選択された要素の二乗の和である。
図５の動き係数除去ブロック３３は、各セグメントについて、フレーム再分割後に、もし対応するセグメントが合併されないままであれば前記行列Ａ'を受け取り、或いは合併されたセグメントについては行列Ｂ'を受け取り、予測誤差の許容できる増加で係数Ｃｉを除去できるか否か判定する。これは、ブロック３３により、行列Ａ'及びＢ'から係数Ｃｉに対応する行をそれぞれ抽出するとともに、前記行の抽出後の行列Ａ'及びＢ'からそれぞれもたらされる行列の好ましくは正規直交型の座標変換を行うことによって、実行される。係数Ｃｉを除去したことに起因する追加の予測誤差を前記の変換された行列の選択された要素から計算することができ、前記の選択された要素は、前記の変換された行列のｚ1からもたらされる列と、Ｒ1からもたらされる全ての列にゼロを有するこの行列の行とに置かれる。図５のマルチプレクサ３４は、ブロック３２からの合併情報と、どの係数Ｃｉが送られるべく選択されるかについての情報と、ブロック３３によって前記の変換された行列に基づいて最終的に計算される選択された係数Ｃｉとを受け取る。マルチプレクサ３４により出力されるこの情報はビデオ・デコーダ（図示されていない）へ出力される。
より詳しくは、QR動き分析器の動作は下記のステップから成る：
ステップ１は予測誤差の線形化である。このステップでは式（７）の予測フレーム
0003790804.tif 000020
が公知の何らかの近似方法によって近似されて
0003790804.tif 000021
に関して線形となる。式（５）において合計される要素は係数Ｃｉの線形結合となる。
0003790804.tif 000022
好ましい具体的構成では、１２個の係数を有する二次多項式の動きベクトル・フィールド・モデルが使用される：
0003790804.tif 000023
このモデルは、実際上、ビデオ・シーケンスにおける非常に複雑な動きも十分に処理することができ、良好な予測結果をもたらす。
ＱＲ動き分析器ブロックにおいて、全てのピクセル（ｘｉ，ｙｉ）で
0003790804.tif 000024
のテイラー展開を用いて各点：
0003790804.tif 000025
の周りでステップ１の線形化が行われる。ここでｉ＝１，２，．．．Ｐである。
Σa2＝Σ（-a）2という性質を用いると、二乗予測誤差ＳＰＥは下記のようになる。
0003790804.tif 000026
補助値ｇｊ（ｘ，ｙ）が下記の式：
0003790804.tif 000027
を用いて計算される。ここで関数ｆｊ（ｘｉ，ｙｉ）は、式（４ａ）及び（４ｂ）で、より具体的には式（４ｃ）及び（４ｄ）で定義されている動きフィールド・モデルによる所定の基本関数である。
ステップ２は行列の作成である。それは、式（６）によるＳＰＥの最小化が行列式(Ec-y)T(Ec-y)の最小化と完全に同等であるという事実に基づいており、このE及びyは：
0003790804.tif 000028
である。式（９）の行列E及びベクトルyは下記の式：
0003790804.tif 000029
を用いて組み立てられる。
Ｇｘ（ｘ，ｙ）及びＧｙ（ｘ，ｙ）は、下記の式：
0003790804.tif 000030
を用いて計算される基準フレーム
0003790804.tif 000031
の水平勾配及び垂直勾配の値である。
0003790804.tif 000032
及びＧｙ（ｘ，ｙ）のピクセル値は整数座標ｘ及びｙについてのみ定義される。ｘ又はｙが整数でないときは、ピクセル値は例えば整数座標を有する最も近いピクセル同士の双一次補間を用いて計算される。
ステップ３はＱＲ因数分解である。行列のＱＲ因数分解は、それ自体としては良く知られていて、適当なアルゴリズムが１９８９年ジョンズホプキンス大学出版会の、Ｄ．Ｈ．ゴルブ及びＣ．ヴァン・ローンによる“行列計算”第２版（D. H. Golub and C. van Loan, "Matrix computation"2'nd edition, The Johns Hopkins University Press, 1989）で解説されている。このアルゴリズムを使ってＥを２つの行列の積に分解することができる。
0003790804.tif 000033
換言すれば、ＲはＱの座標でのＥの表示である。Ｑは好ましくは正規直交であって、Ｒは上三角形である、即ちＲの行Ｎ＋Ｍ＋１からＰまでは全て０である。
このステップにおいて補助ベクトルｚも計算され、ここで、
0003790804.tif 000034
である。
ステップ４ではＱＲ動き分析器ブロックの出力が計算される。その出力は、行列Ｒの始めのＮ＋Ｍ個の行から成る行列Ｒ1と、ｚの始めのＮ＋Ｍ個の要素から成るベクトルｚ1とから成る。
セグメント合併ブロックでは、隣り合うセグメントＳｉ及びＳｊの対について（図４を参照）、結合されたセグメントＳｉｊについて動き係数Ｃｉｊで記述される共通動きフィールドを用いて動きベクトル・フィールドを表示できるか否か判定することによって合併操作が実行される。合併操作は下記のステップから成る：
ステップ１は行列計算から成る。本発明は、合併されたセグメントＳｉｊにおける予測誤差を最小にする動き係数Ｃｉｊがスカラー値
0003790804.tif 000035
をも最小にするという、これまで知られていなかった性質を利用する。ここでＲ1ｉ、ｚ1ｉ及びＲ1ｊ、ｚ1ｊは、前述したように、それぞれセグメントＳｉ及びＳｊについてＱＲ分析器ブロックによって既に作られている。（１０）のこの最小化は、最小二乗の意味で重複決定された方程式のシステム（the overdetermined system of equations）、
0003790804.tif 000036
を解くことと同等である。
ステップ２は、ステップ１で得られた行列の三角化である。上記文献の教示に従ってセグメントＳｉについてのＥであるＥｉと、セグメントＳｊについてのＥであるＥｊとのＱＲ因数分解を行えば、行列Ｒ1ｉ、Ｒ1ｊは上三角行列となり、（１０）でのシステム、
0003790804.tif 000037
は下記の形：
0003790804.tif 000038
を有する。ここで記号ｘはゼロでない要素を意味し、ｚｉｋはベクトルｚ1ｉのｋ番目の要素を意味し、ｚｊｋはベクトルｚ1ｊのｋ番目の要素を意味する。
各行にスカラーを乗じる一連の掛け算を行った後に各行を加算することによって方程式（１１）のシステムは三角化される；即ち、それは下記の形に変換される：
0003790804.tif 000039
この三角化のためにも上記の前記文献によるＱＲ因数分解を用いることができる。
ステップ３では合併誤差が評価される。セグメントＳｉ及びＳｊの合併に起因するセグメントＳｉｊにおける二乗予測誤差の変化ΔＥｉｊは、
0003790804.tif 000040
に従って計算される。この好ましい実施例では、（１１）のＱＲ因数分解の結果としてＱは正規直交行列となり、式１３は非常に簡単になる。しかし、もし予測誤差の尺度として二乗予測誤差が用いられるのであれば、この因数分解におけるＱの性質に依存して、ΔＥｉｊは一般にｑ2ｋ、ｋ＝１，．．．，Ｎ＋Ｍ、の関数である；もちろん、予測誤差について他の尺度を用いることも可能であり、従って、ｑｋとΔＥｉｊとの他の関数関係を適合させることができる。
最後に、ステップ４において、選択された基準に照らして式（１３）の二乗予測誤差の変化が許容できるものであるならば、セグメント同士が合併される。セグメント合併ブロックはセグメント合併のために下記の方針をとる：
ａ．フレーム全体における二乗予測誤差の許容される増加に対応する閾値Ｔを選択する。
ｂ．隣り合うセグメントの全ての対について式（１３）を用いてΔＥｉｊを計算する。
ｃ．最小のΔＥｉｊを有するセグメントの対を合併させる。
ｄ．合併された全てのセグメントの対に対応するΔＥｉｊの合計がＴより大きくなるまでポイントｂ−ｃを反復する。
式（１１）におけるシステムの三角化のために、一連のギブンズ回転を用いることができる。
得られた新しいセグメントＳｉｊについて、式（１２）におけるシステムの始めのＮ＋Ｍ行をとることによって行列Ｒ1ｉｊ及びベクトルｚ1ｉｊが組み立てられる、即ち式：
0003790804.tif 000041
により与えられる。
フレームの全てのセグメント対を検討した後、セグメント合併ブロックの出力が得られる。その出力は３種類の情報から成る。第１に、それは、イメージの、セグメント数が減った新しい分割態様を与える。第２に、各々の新しいセグメントについて該ブロックは行列Ｒ1ｉｊ及びベクトルｚ1ｉｊを出力する。第３に、それは、デコーダに送られてデコーダが合併されたセグメントを特定するのに役立つ合併情報を与える。
いま、各方程式のシステムＲ1ｉｊＣｉｊ＝ｚ1ｉｊを解くことによってセグメントＳｉｊについての動き係数Ｃｉｊ＝（ｃ１，ｃ２，．．．ｃＮ＋Ｍ）を計算することができるけれども、係数除去ブロック３３を用いるのであれば、それらの計算は未だ必要ではない。また、次に更に説明するように、この段階において、係数除去を実行する前に、セグメント合併から得られたセグメントに関して動きフィールド・モデルを直交化するのが有利であるかも知れない。その様に直交化された動きフィールド・モデルは、動き係数を量子化することの結果として生じる量子化誤差の結果として生じる量子化誤差にあまり敏感でない。しかし、好ましい実施例についての説明をなるべく明瞭に保つために、ここでは最適の動きフィールド・モデル直交化は省略する。
係数除去ブロック３３は、入力として現在のフレームのセグメントへの前記の新しい分割態様を受け取り、全てのセグメントＳｋについて該ブロックはセグメント合併ブロックによって前に作られていた、（１４）に示されている前記行列Ｒ1ｋ、ｚ1ｋを受け取る。全てのセグメントの動きベクトルはＮ＋Ｍ個の動き係数によって表されるが、Ｎ及びＭはΔｘ及びΔｙについての動きフィールド・モデルにより決定される。
動き係数除去ブロック３３は、与えられたセグメントＳｋについて、予測誤差をあまり増大させることなく動きフィールド・モデルを簡単化することが可能か否か判定する。簡単化された動きフィールド・モデルは、この明細書の背景技術の箇所で説明した式（３）のモデルから多少の基本関数を除去したときに得られ、その様に簡単化された動きフィールド・モデルを記述するのに必要な係数は少なくなっている。
ｉ番目の基本関数（及びｉ番目の係数）を動きフィールド・モデルから除去できるか否か調べるために、全てのセグメントについて下記の処理手順がブロック３３によって実行される：
ステップ１は行列修正を包含し、Ｒ1ｋからｉ番目の列を除去すると共にＣｋからｉ番目の要素を除去することによって各線形方程式のシステム
0003790804.tif 000042
が修正される。
ステップ２は行列三角化を包含し、好ましくは上記文献で解説されている前記ＱＲ因数分解アルゴリズムを使用し、或いは一連のギブンズ回転を用いる。即ち、方程式（１５）におけるシステムは、行にスカラーを掛ける一連の乗算に続けて行の加算を行うことによって、それ自体としては公知の方法で三角化される、即ち、それは下記の形に変換される：
0003790804.tif 000043
ステップ３は誤差評価を含む。ｉ番目の係数の除去に起因するセグメントについての二乗予測誤差の変化は単に式（１６）の項ｑ2ｉに等しい。これも、前記ＱＲ因数分解におけるＱが正規直交型であることを基礎として妥当である。一般に、Ｑの性質と予測誤差についての尺度とにより、二乗予測誤差の変化はｑｉの関数である。
ステップ４は係数の除去を含む。もし選択された基準に照らして予測誤差の変化が許容できるならば、係数Ｃｉは係数の集合から除去される。ここで係数の新しい個数はＮ＋Ｍ−１となる。行列Ｒ1ｋ及びベクトルｚ1ｋは例えばＱＲ因数分解によって下記の形に修正される：
0003790804.tif 000044
式（１７）に基づいてステップ１−４を反復することによってセグメントについての係数の個数を更に減らすことができる。
動き係数除去ブロックでは係数除去のために下記の方針をとる：
ａ．フレーム全体での二乗予測誤差の許容される増加に対応する閾値Ｔを選択する。
ｂ．全てのセグメント及びそれらの基本関数について式（１６）を用いてｑｉ2を計算する。
ｃ．最小のｑｉ2を有するセグメントの基本関数を除去する。
ｄ．いろいろなセグメントにおける全ての除去された基本関数に対応する全てのｑｉ2の合計がＴより大きくなるまでポイントｂ−ｃを反復する。
最後に、ステップ５は係数計算を含む。このステップで適当な係数が除去された後、セグメントＳｋについての最終の動き係数が各線形方程式のシステム：
0003790804.tif 000045
を解くことによって計算される。ここで行列Ｒ1ｋ及びベクトルｚ1ｋは前のステップ１−４の結果である。例えば後退代入法などの周知のアルゴリズムのうちの１つを用いてこの方程式を解くことができる。
この好ましい実施例は、Ｒ1ｉｊ及びｚ1ｉｊに基づいて係数Ｃｉを計算しなくて、与えられたセグメントを囲む矩形に関して動きフィールド・モデルを直交化するための更なるブロック（図示されていない）を含んでいる。このブロックは、入力として、現在のフレームのセグメントへの区分化態様を受け取ると共に、全てのセグメントＳｋについてセグメント合併ブロックからの（１４）に示されている行列Ｒ1ｋ及びｚ1ｋとを受け取る。この直交化ブロックにおいて、多項式基本関数ｆｉ（・）は直交多項式
0003790804.tif 000046
に置き換えられる。すると、このセグメントの動きベクトル・フィールドを下記のように表示することができる：
0003790804.tif 000047
式（４）の動きベクトル・フィールドは式２３のと完全に同等であるけれども、係数
0003790804.tif 000048
はＣｉよりも量子化に対して敏感ではなくて、従ってより少数のビットで表示できるので、後者のものが用いられる。
直交多項式基本関数の計算は、ビデオ・エンコーダ及びビデオ・デコーダの両方において、各セグメントの形状と動きモデルの所定基本関数ｆｉとに基づいて、次のように行われる。
与えられたセグメントを囲む矩形のサイズがＮ１×Ｎ２ピクセルであるとしよう。始めに、例えばルジャンドル（Legendre）の多項式などの、１次元多項式の２つのシーケンスを計算する：
１．ｇｋ（ｘ），ｋ＝０，１，．．．間隔［１，Ｎ１］で直交
２．ｈｌ（ｙ），ｌ＝０，１，．．．間隔［１，Ｎ２］で直交
２次元（２−Ｄ）直交多項式基本関数
0003790804.tif 000049
が１−Ｄ直交多項式のテンソル積：
0003790804.tif 000050
として組み立てられる。米国アカデミックプレス社の、Ａ．アカンス及びＲ．ハダッドによる１９９２年の“多解像度信号分解”のページ５５−５６（A. Akansu and R. Haddad, "Multiresolution Signal Decomposition", Academic Press Inc., USA, 1992, pages 55 to 56）から、多項式の選択に関する詳細を得ることができる。
この様にして実行される与えられたセグメントを囲む矩形に関する直交化は、他の直交化方法より計算に関してはるかに単純ではあるけれども、それらを例えばセグメントの形状に関する直交化に選択肢として使用可能である。
しかし、一般に、例えばグラム・シュミットのアルゴリズムなどの周知の直交化アルゴリズムを使って、通常の多項式を任意形状のセグメント領域で直交する多項式に変換することができる。
直交多項式基本関数
0003790804.tif 000051
は、多項式基本関数ｆｋ（・）、ｋ＝１，２，．．．，ｉ、の線形結合として表示され得るように選択される、即ち、
0003790804.tif 000052
である。この仮定は、非直交基本関数から直交基本関数への変換を単純な行列乗算によって複雑さの低い計算で実行し得ることを保証する。
ｆｉ（・）からそれらの直交バージョン
0003790804.tif 000053
への基本関数の変化を反映するようにセグメントの動きベクトル・フィールドを記述する行列Ｒ1ｋ及びｚ1ｋを計算し直す必要がある。式（２５）を満たす直交多項式基本関数
0003790804.tif 000054
に対応する新しい行列
0003790804.tif 000055
を行列Ｒ1ｋ及びベクトルｚ1ｋを使って下記の式：
0003790804.tif 000056
に従って計算することができる。行列Ｔは、
0003790804.tif 000057
で与えられる。ここで要素ｔｋ，ｉは式（２５）からとられる。直交多項式基本関数
0003790804.tif 000058
に対応するセグメントＳｋについての新しい動きベクトル係数
0003790804.tif 000059
を、多項式基本関数ｆｉ（・）、ｉ＝１，．．．，Ｎ＋Ｍ、に対応する係数ｃｋ＝（ｃ１，．．．，ｃＮ＋Ｍ）を用いて計算することができる
0003790804.tif 000060
或いは各方程式のシステム、
0003790804.tif 000061
を解くことによって計算することができる。係数除去ブロック３３は、入力として、現在のフレームのセグメントへの新しい分割態様を受け取ると共に、全てのセグメントＳｋについて直交化ブロックにより作られた行列
0003790804.tif 000062
を受け取る。全てのセグメントの動きベクトル・フィールドがＮ＋Ｍ個の動きフィールド・モデル基本関数で表示される。
動き係数除去ブロック３３は、与えられたセグメントＳｋについて、上記のように動きフィールド・モデルを簡単化することが可能か否か判定する。
図７は図１の動き補償予測ブロック１の実施例を示している。このブロックは、動きフィールド・コーディング・ブロック３から出力される動き情報を受け取ると共に、更に基準フレーム
0003790804.tif 000063
を受け取る。この情報に基づいて、ブロック１は予測フレーム
0003790804.tif 000064
を出力する。図７に示されているように、動き補償予測ブロック１はデマルチプレクサ１１を有し、このデマルチプレクサは、動きフィールド・エンコーディング・ブロック３から多重化された動き情報を受け取って、分離された動き情報成分、即ちイメージ区分化情報、係数選択情報及び、最後に、送られてきた動き係数の値、を出力する。参照数字１２は、イメージ区分化ブロックを意味しており、このブロックは、前記イメージ区分化情報と前記基準フレーム
0003790804.tif 000065
とを受け取って、イメージ区分化情報に従ってイメージを区分化した結果としてもたらされたフレームのセグメントを出力する。参照数字１３は、基本関数組立ブロックを意味している。このブロックは、基本関数の所定の集合（セット）から、動きフィールド・エンコーディング・ブロック３の動き係数除去ブロック３３で作られた選択情報で表示されている特定の基本関数を選び出す。参照数字１４はセグメント予測ブロックを意味しており、このブロックは、前記基準フレーム
0003790804.tif 000066
の各セグメントについて付随の基本関数の選択と付随の動き係数とを受け取り、動きベクトル
0003790804.tif 000067
を計算し、それらの動きベクトルに基づいて、各セグメントの各ピクセル（ｘ，ｙ）について予測フレーム
0003790804.tif 000068
を計算する。動き補償予測ブロック１は、その構造及び機能において、図２に示されているビデオ・デコーダの動き補償予測ブロック２１に対応する。この両方の動き補償予測ブロックが、図１に示されているビデオ・エンコーダの動きフィールド・コーディング・ブロック３から出力される動き情報に基づいて予測を行う。
全ブロックにおける全ステップの結果として、本発明による動きフィールド・エンコーダは、どのセグメントが合併されるかをデコーダに知らせるための合併情報と、どの基本関数が除去されるかをデコーダに知らせる選択情報と、動き係数情報とを作り出す。
従来技術の解決策と比べて本発明の主な利点は、予測誤差を大幅に増大させることなく動き情報の量を大幅に減少させ得る能力を持っていることである。また、システム全体の複雑さが低いので、入手可能な信号処理装置或いは汎用マイクロプロセッサで実施することができる。
セグメント合併ブロックは、別々のセグメントについて推定された与えられた動きベクトルから、結合されたセグメントの動きベクトルを見いだせる独特の能力を持っている。それが作り出す動きベクトルが実際上、結合されたセグメントについてごく僅かな二乗誤差を保つことに関して最適であるということを証明することができる。このことが、このブロックが二乗予測誤差を僅かに増大させるだけでセグメントの個数を劇的に減少させ得る能力を持っている理由である。
動き係数除去ブロックは、ビデオ・シーンにおける実際の動きの量及び種類に動きモデルを瞬時に適応させるための非常に強力な手段である。このブロックは、予測の結果（セグメントについての二乗予測誤差の値）を非常に多数のモデルで、例えば動きフィールド基本関数のあり得る全ての組み合わせで、容易に試験することができる。このスキームの強力な利点は、動き推定のプロセスを反復する必要が無く、従って計算に関して単純であることである。
動き推定に続いてＱＲ動き分析を用いて、動きフィールド・コーダは、非常に単純な線形方程式のシステムを解くことによりイメージ・セグメントの如何なる所望の組み合わせ或いは該セグメントにおける動きフィールドの如何なる所望のモデルについても、新しい動き係数を見いだすことができる。
本システムを本発明の思想及び範囲から逸脱することなくいろいろな方法で実施することができる。例えば、種々の線形動きモデルを式（３）に用いることができる。種々の方法を用いて式（５）の項を線形化することができる。更に、２つのセグメントを合併させるか否かを決めるために種々の基準を用いることができる。与えられた基本関数をモデルから除去するべきか否かを決めるための方針は種々様々であって良い。種々のアルゴリズムを用いて式（１０）及び（１５）の行列の三角化を実行することができ、各線形方程式のシステムを解くためのいろいろな公知のアルゴリズムを用いて式（１８）を解いて最終の係数を計算することができる。最後に、非整数座標における
0003790804.tif 000069
の値に種々の補間方法を用いることができる。
【図１】
0003790804.tif 000135
【図２】
0003790804.tif 000136
【図３】
0003790804.tif 000137
【図４】
0003790804.tif 000138
【図５】
0003790804.tif 000139
【図６】
0003790804.tif 000140
【図７】
0003790804.tif 000141