(57)【特許請求の範囲】
【請求項１】
ビデオシーケンスの現在のフレームＩnを符号化するためのビデオ符復号器であって、このビデオ符復号器は、符号化された動きベクトルフィールドを供給する動きフィールド符号器を有し、この動きフィールド符号器は、
現在のフレームＩnと、
参照フレーム
0003781194.tif 000037
と、
動きベクトルフィールドとを受け取るようになっている動き分析器を有し、
この動き分析器は、動きベクトルフィールドの新しい表示を求めるようになっており、その表示は、現在のフレームＩnの複数の画像セグメントのうちの各セグメントＳiについて、ベクトルｃiによって表されるN+M個の動き係数の集合と基底関数の集合とに基づく線形動きモデルを伴っており、ここにＮ及びＭはそれぞれ、圧縮されている動きベクトルフィールド
0003781194.tif 000038
の動き係数の個数であり、
該動き分析器は、
現在のフレームの各セグメントＳiについて、行列表示Ｅiｃi−ｙiに基づいて、その現在のフレームのセグメントと参照フレーム
0003781194.tif 000039
のセグメントとに基づく予測エラー関数を近似するための予測エラー線形化手段を含んでおり、ここでＥiは行列であり、ｙiはベクトルであり、
ここに現在のフレームの各セグメントについて動き分析器によって近似される予測エラーの関数は下記の通りであり、
0003781194.tif 000040
ここで、
0003781194.tif 000041
であり、かつ
現在のフレームの各セグメントについて、前記行列表示から、第１の行列Ｒi1及び第１のベクトルｚi1を作成するための行列処理手段を含んでおり、ここでＲi1ｃi＝ｚi1であり、第１の行列Ｒi1の行の個数は動き係数の個数N+Mに等しく、
ここに前記行列処理手段はＱＲ因数分解手段を含んでおり、この手段は、行列Ｅiを行列Ｑi及びＲiの積に分解し、補助ベクトルｚi（ここで、ｚi＝Ｑiγｙi）を作成し、行列Ｒiの始めのN+M個の行からＲi1を形成するとともにベクトルｚiの始めのN+M個の要素からベクトルｚi1を形成するようになっており、
該動きフィールド符号器はセグメント併合手段を有し、この手段は、
該動き分析器に結合されて前記第１の行列Ｒi1及び前記第１のベクトルｚi1を受け取るようになっていて、
現在のフレームＩnの隣り合うセグメントの対（Ｓi，Ｓj）について、第１の行列Ｒi1，Ｒj1及び第１のベクトルｚi1，ｚj1のそれぞれの対から併合行列Ｒij1及び併合ベクトルｚij1を決定するとともに、
第１の行列Ｒi1及び第１のベクトルｚi1の対を、併合行列Ｒij1及び併合ベクトルｚij1が選択された基準に照らして許容できる予測エラーを生じさせる場合には、その併合行列Ｒij1及び併合ベクトルｚij1と置き換えて、対応するセグメント対を併合させるようになっており、
該動きフィールド符号器は、該セグメント併合手段に結合されている係数除去手段を有し、この手段は、
残りの第１の行列Ｒi1と第１のベクトルｚi1と置換した併合行列Ｒij1と併合ベクトルｚij1とを受け取って、
現在のフレームＩnの各セグメント又は併合されたセグメントについて、対応する行列Ｒk1及びベクトルｚk1を使って、近似された予測エラー関数の変化が選択された基準に照らして許容できるように動き係数ｃkの減らされた集合を決定し、
現在のフレームＩnの符号化されたバージョンを提供するようになっており、その形は、各セグメント又は併合されたセグメントについて、個数の減らされた前記の動き係数と、どの係数が省略されたかを示す表示とから成るビデオ符復号器。
【請求項２】
該セグメント併合手段は、隣り合うセグメントの前記の対（Ｓi，Ｓj）について、下記の式：
0003781194.tif 000042
を下記の形：
0003781194.tif 000043
に三角化するための手段を含んでおり、ここでｃijは併合された隣り合うセグメントの対のN+M個の動き係数の集合である請求項１に記載のビデオ符復号器。
【請求項３】
該セグメント併合手段は、隣り合うセグメントの各対（Ｓi，Ｓj）について下記の式：
0003781194.tif 000044
に従って二乗予測エラーの変化ΔＥijを計算することにより予測エラーが選択された基準に照らして許容できるか否かを判定するようになっている請求項２に記載のビデオ符復号器。
【請求項４】
該セグメント併合手段は、三角化された行列方程式の始めのN+M個の行を使って前記併合行列Ｒij1及び前記併合ベクトルｚij1を下記の形：
0003781194.tif 000045
に決定するようになっている請求項２又は３に記載のビデオ符復号器。
【請求項５】
現在のフレームＩnの前記の符号化されたバージョンは、併合されたセグメントの識別子を含んでいる請求項１乃至４のいずれか一項に記載のビデオ符復号器。
【請求項６】
前記係数除去手段は、各セグメントについて、行列Ｒk1からi番目の列を選択的に除去するとともにベクトルｚk1からi番目の要素を選択的に除去して簡略化された行列方程式Ｒk1ｃk＝ｚk1を設けることによって、個数の減らされた動き係数ｃkを決定するようになっている請求項１乃至５のいずれか一項に記載のビデオ符復号器。
【請求項７】
該係数除去手段は、簡略化された行列方程式を下記の形：
0003781194.tif 000046
に三角化して、下記の式：
ΔＥk＝ｑi2
に従って二乗予測エラーの変化を計算するようになっている請求項６に記載のビデオ符復号器。
【請求項８】
該係数除去手段は、もし二乗予測エラーの変化が選択された基準に照らして許容できる場合には、係数行列ｃkから動き係数ｃiを除去するとともに、前記の三角化された行列方程式、すなわち
0003781194.tif 000047
の一番下の行を除去するようになっている請求項７に記載のビデオ符復号器。
【請求項９】
該係数除去手段は、行列方程式Ｒk1ｃk＝ｚk1又はこの方程式の簡略化された形を解くことによって動き係数ｃkを決定するようになっている請求項１乃至８のいずれか一項に記載のビデオ符復号器。
【発明の詳細な説明】
発明の分野
本発明は、一般的にはビデオ圧縮に関する。より正確には、本発明は、推定された動きフィールド（motion field）を符号化してビデオシーケンスにおける動き情報を作成する方法に関する。
発明の背景
動き補償予測は、大多数のビデオ符号化方式の非常に重要な要素である。図１は、動き補償を使用してビデオシーケンスを圧縮する符号器の略図である。この符号器の必須要素は、動き補償予測ブロック１，動き推定器２，及び動きフィールド符号器３である。動き補償ビデオ符号器の動作原理は、現在のフレームと呼ばれる符号化される入来フレームＩn(x,y)と予測フレーム
0003781194.tif 000002
との差である予測エラーＥn(x,y)を圧縮するというものであり、ここで、
0003781194.tif 000003
予測フレーム
0003781194.tif 000004
は動き補償予測ブロック１により作成されるものであって、前の、或いはその他の既に符号化されている
0003781194.tif 000005
と表記されるフレーム（参照フレーム（reference frame）と呼ばれる）のピクセル値と、現在のフレーム及び参照フレームの間の各ピクセルの動きベクトル（motion vector）とを使って作成される。動きベクトルは動きフィールド推定器２により計算され、その結果として得られたベクトルフィールドは、予測ブロック１に入力される前に何らかの方法で符号化される。予測フレームは次の通りである：
0003781194.tif 000006
数の対［x+Δx(x,y)，y+Δy(x,y)］は、現在のフレームの中の場所(x,y)のピクセルの動きベクトルと呼ばれ、Δx(x,y)及びΔy(x,y)はこのピクセルの水平変位及び垂直変位の値である。現在のフレームＩn(x,y)の中の全てのピクセルの動きベクトルの集合は動きベクトルフィールドと称される。符号化された動きベクトルフィールドは動き情報として復号器にも送られる。
図２の復号器において、現在のフレームＩn(x,y)の各ピクセルは、参照フレーム
0003781194.tif 000007
の中の該ピクセルの予測値
0003781194.tif 000008
を求めることによって、復元（再構成）される。動き補償予測ブロック２１は、受け取った動き情報及び参照フレーム
0003781194.tif 000009
（この絵では参照フレームは現在のフレームと同じである）を使用して予測フレームを作成する。予測エラー復号器２２において、復号された予測エラーＥn(x,y)が予測フレームと加算されて、元の現在のフレームＩnが得られる。
動き補償（motion compensated）（MC））予測の一般的目的は、復号器に送らなければならない情報の量をなるべく少なくすることである。この予測は、例えばＥn(x,y)のエネルギーとして測定された予測エラーの量をなるべく少なくし、且つ、動きベクトルフィールドを表示するのに必要な情報の量をなるべく少なくするべきである。
１９９０年３月２６−１８日、マサチューセッツ州ケンブリッジ市での画像符号化シンポジウム’９０の議事録、841-845ページに掲載されているＨ．グエン、E.デュボアの文献”画像符号化のための動き情報の表示”（the document H.Nguen, E. Dubois, ”Representation of motion information for image coding”. Proc. Picture Coding Symposium '90, Cambridge, Massachusetts, March 26-18, 1990, pages 841-845）は、動きフィールド符号化手法を概説している。大ざっぱに言うと、予測エラーを小さくするためには、より複雑な動きフィールドが必要である、即ち、より多数のビットをその符号化のために使用しなければならない。従って、ビデオ符号化の総合的目的は、予測エラーの尺度をなるべく低く保ちながら動きベクトルフィールドをなるべくコンパクトに符号化することである。
動きフィールド推定ブロック１（図１）は、与えられたセグメントの全てのピクセルの、このセグメントの例えば二乗予測エラー（square prediction error）などの予測エラーの何らかの尺度を最小にする動きベクトルを、計算する。動きフィールド推定手法は、動きフィールドのモデルと、予測エラーの選択された尺度を最小化するためのアルゴリズムとの両方において異なる。
フレームの中のピクセルの数が非常に多いために、各ピクセルについて別々の動きベクトルを送信するのは効率的でない。殆どのビデオ符号化方式で、現在のフレームは大きな画像セグメントに分割され、セグメントの全ての動きベクトルを少数のパラメータで記述できるようになっている。画像セグメントは正方形のブロックであってもよくて、例えば国際規格ISO/IEC MPEG-1又はITU-TH.261に準拠する符復号器（コーデック）では１６×１６のピクセル（画素）のブロックが使用されており、また画像セグメントは例えば分割アルゴリズムによって得られる全て任意の形状の領域から成っていてもよい。実際上、各セグメントは少なくとも数十個のピクセルを包含する。
セグメント内の各ピクセルの動きベクトルをコンパクトに表示するためには、それらの値を少数のパラメータの関数で記述できることが望ましい。その様な関数は動きベクトルフィールドモデル（motion vector field model）と称されている。公知のグループのモデルは線形の動きモデルであり、その動きベクトルは動きフィールド基底関数の線形結合である。このようなモデルでは画像セグメントの動きベクトルは下記の一般式：
0003781194.tif 000010
で記述され、ここでパラメータｃiは動き係数（motion coefficent）と呼ばれるものであり、復号器に送られる。関数ｆi(x,y)は動きフィールド基底関数（motion field basis function）と呼ばれていて、この関数は固定されていて符号器及び復号器の両方に知られている。
上記の式を有する線形動きモデルを使うときの問題は、予測エラーＥn(x,y)の尺度をなるべく低く保ちながら、復号器に送られる動き係数ｃiの数をどうやって最小化するかということである。このプロセスは、符号器において動きフィールド符号化ブロック３によって実行される（図１を参照）。それは、ブロック２によって達成される、計算に関して非常に複雑な動きフィールド推定の後に、実行される。従って、動きフィールド符号化は計算に関して単純で、追加の負担を符号器にかけないことがきわめて重要である。
復号器に送る必要のある動き係数の総数は、画像の中のセグメントの個数と、セグメントあたりの動き係数の個数との両方に依存する。従って、動き係数の総数を減らす方法は少なくとも２つある。
第１の方法は、予測エラーを大幅に増大させることなく共通の動きベクトルフィールドで予測することのできるセグメント同士を結合（併合）させることによってセグメントの数を減らすことである。隣り合っているセグメントを同じ動き係数の集合で予測できることが非常に頻繁にあるので、フレーム内のセグメントの数を減らすことができる。その様なセグメント同士を結合させるプロセスは動き補助併合（motion assisted merging）と呼ばれる。
第２の方法は、なるべく少ない係数で満足できるほど低い予測エラーを達成できる動きモデルを各セグメントについて選択することである。動きの量と複雑さとは各フレーム間で、また各セグメント間で異なるので、セグメントあたりに常にN+M個の動き係数をすべて使用するのは効率的でない。満足できるほど低い予測エラーを達成できる最少数の動き係数を全てのセグメントについて求める必要がある。その様な係数の適応的選択のプロセスは動き係数除去と呼ばれる。
図３は、各セグメントに分割されたフレームを示している。動き係数符号化を行う従来技術の手法は、動き補助併合を行う幾つかの手法を含んでいる。全てのセグメントの動きベクトルが推定された後、動き補助併合が行われる。それは、隣接するセグメントＳi及びＳjの全ての対をそれらの動き係数ｃi及びｃjとともに考慮して行われる。結合されたセグメントＳi及びＳjの領域はＳijと表示される。予測エラーをＳi及びＳjの別々の予測から生じるエラーより大幅に増大させることなく動き係数ｃijの１つの集合で領域Ｓijを予測できるならば、Ｓi及びＳjは併合される。動き補助併合を行う方法は、本質的に、互いに結合されたセグメントを良好に予測することを可能する動き係数ｃijの単一の集合を求める方法において異なる。
１つの方法は徹底的な動き推定による併合方法として知られている。この方法は、隣り合うセグメントＳi及びＳjの全ての対について動き係数ｃijの新しい集合を”最初から”推定する。もしＳijについての予測エラーがあまり大きくはならなければ、セグメントＳi及びＳjは併合される。この方法では、併合することのできるセグメントを非常によく選択できるけれども、通常は符号器の複雑さを数桁も大きくするので、この方法を実行することはできない。
もう一つの方法は、動きフィールド拡張による併合として知られている。この方法は、予測エラーをあまり大きくすることなくいずれかの動きパラメータｃi又はｃjを使ってＳijの領域を予測できるか否か試験する。この方法は、新しい動き推定を全く必要としないので、計算の複雑さが非常に低いという特徴を持っている。しかし、この方法では、１つのセグメントについて計算された係数での動きの補償によって隣のセグメントを予測することさえもうまくできるのは非常にまれであるので、セグメント同士を併合できないことが非常に頻繁にある。
もう一つの方法は動きフィールドはめ込みによる併合として知られている。この方法では、動き係数ｃijは近似の方法により計算される。それは、各セグメントで少数の動きベクトルを評価することによって行われる。図４においてセグメントＳi及びＳjの幾つかの動きベクトルが描かれている。セグメントＳijについての動きフィールドは、或る公知のはめ込み方法を使用してこれらのベクトルを通じて共通の動きベクトルフィールドをはめ込むことによって作成される。この方法の欠点は、はめ込みによって得られる動きフィールドが充分に精密ではなくて、予測エラーが許容できないほど大きくなることがしばしばあることである。
いろいろなモデルで動きを推定し、最も適当なものを選択する方法が下記の２つの文献で提案されている：
１９９４年度、音響学、音声及び信号処理に関する国際会議議事録、III265-268ページ、H.ニコラス及びC.ラビットの”画像シーケンス符号化のための決定論的緩和法を用いる領域に基づく動き推定方法”（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-286）；
ビデオ技術のための回路及びシステムに関するIEEE会報、１９９４年６月、第３巻第４号、357-364ページ、Ｐ．チッコーニ及びH. ニコラスによる”画像シーケンス符号化のための領域に基づく効率的動き推定方法及び対称指向分割方法”（P. Cicconi and H. Nicolas, ”Efficient regient-based motion estimation and symmetry oriented segmentation for image sequence coding, ”IEEE Trans. on Circuits and Systems for Video Technology, Vol. 4, No. 3, June 1994, pp. 357-364）
それらの方法は、いろいろなモデルで動き推定を行って、最も適当なものを１つ選択することによって、動きの複雑さに応じて動きモデルを適応させようと試みる。それらの方法の主な欠点は、計算が複雑で、実際に試験することのできるいろいろな動きフィールドモデルの量が少ないことである。
上記の方法のいずれも、単独では、予測エラーＥn(x,y)の尺度をなるべく低く保ちながら、復号器に送られる動き係数ｃiの数を最小にするという問題を解決することはできない。
発明の概要
本発明の目的は、予測エラーを大幅に増大させずに公知の動き推定方法により作成される動きフィールドベクトル情報の量を大幅に減少させる動きフィールド符号器を作ることである。利用可能な信号処理装置或いは汎用マイクロプロセッサで実用的に実現できるように、その動きフィールド符号器の複雑さは低くなければならない。
本発明によれば、動きフィールド符号器は３個の主なブロックを含んでいる。
第１の主なブロックはQR動き分析器（motion analyzer）と呼ばれる。その任務は、動きフィールド推定器によって作成されて入力された動きフィールドの新しい表示を求めることである。その新しい表示は第２の主なブロックに入力される。この第１の主なブロックでの動作は、行列演算からなる複数のステップを含んでいる。その第１のステップでは予測フレームが公知の近似方法で線形化され、予測フレームは動きベクトルに関して線形となる。第２ステップでは二乗予測エラー（square prediction error）を最小化するために行列Ｅi及び行列ｙiが作成される。第３ステップでは周知のQR因数分解アルゴリズムを使って行列Ｅiを２つの行列Ｑi及びＲiの積に分解する。また、因数行列Ｑi及び行列ｙiから補助ベクトルｚiを計算する。行列Ｒiの一部分と補助ベクトルｚiとが第２の主なブロックに入力される。
セグメント併合ブロック（segment merging block）と呼ばれる第２の主なブロックは、隣り合うセグメントの対の結合された領域を共通の動きフィールドを使用して予測できるか否かを判定して、それらのセグメントの対を併合させる。行列演算では始めに行列方程式を作成し、その後に公知の行列計算方法を使用して因数行列を処理する。その結果は行列方程式であり、その１つの行列はいくつかの項を含んでいて、それらに基づいて、併合されるセグメントの領域での二乗予測エラーを簡単に計算できる。もし二乗予測エラーの変化が、選択された基準に照らして許容できる程度のものであるならば、それらのセグメントを併合させる。
全てのセグメントの対が検討された後、セグメント併合ブロックの出力は：
i.  セグメントの数が減っている、新たに分割された画像であるか、
ii. 各新セグメントについて該ブロックは行列Ｒ1ij、ベクトルｚ1ijを出力するか、
iii.併合情報であり、この情報は復号器に送られて、復号器が併合されたセグメントを特定するのに役立つ。
第３の主なブロックは係数除去ブロック（coefficient removal block）と呼ばれる。このブロックは入力として、新たに各セグメントに分割された現在のフレームを受け取るとともに、全てのセグメントについてセグメント併合ブロックにより作成された行列Ｒ1k、ｚ1k、及びｃkを受け取る。全てのセグメントの動きベクトルが数個の動き係数によって表示される。動き係数除去ブロックは、各セグメントについて、予測エラーをあまり増大させることなく動きフィールドモデルを簡単にすることができるか否か判定する。何らかの基底関数が動きモデルから除去され、その様にして単純化された動きフィールドモデルを記述するのに必要な係数は少なくなる。
この第３の主なブロックでの動作は行列操作であり、始めに因数行列の１つの行と列とを除去して行列方程式を修正し、次にその行列方程式を三角行列にする（triangularized）。１つの列及び行の除去は動きモデルからの１つの基底関数の除去に相当する。１つの基底関数の除去によって生じるセグメントについての二乗予測エラーの変化は方程式中の１つの項の二乗に等しい。
選択された基準に照らして予測エラーの変化が許容できる程度であるならば、１つの係数が係数の集合から除去される。これらの行列操作を更に繰り返して、該セグメントについてより多くの係数を減らすことができる。充分な量の係数が除去された後、得られた一次方程式を解くことによってそのセグメントについての最終の動き係数が計算される。例えば後退代入（backsubstitution）など、周知のアルゴリズムの１つを使って方程式を解くことができる。
第３の主なブロックは、処理した全てのセグメントについて、どの基底関数が動きフィールドモデルから除去されたのかを知らせる選択情報を出力する。更にこのブロックは、残っている基底関数に対応する新しい動き係数も出力する。選択情報と動き係数との両方が復号器に送られる。
【図面の簡単な説明】
図１は、公知の符号器の概略図である。
図２は、公知の復号器の概略図である。
図３は、併合される隣り合っているセグメントを示す。
図４は、動きフィールド近似による併合を示す。
図５は、本発明による動きフィールド符号器である。
図６は、ＱＲ動き分析器の概略図である。
図示した実施例の説明
図５は、本発明による動きフィールド符号器を示している。これは図１のブロック３に対応するものであるけれども、入力として参照フレーム及び現在のフレームも有する。このブロックへの第３の入力は、図１の動きフィールド推定ブロック２によって作成された動きベクトルフィールド［Δx(・)，Δy(・)］である。
ビデオ符号器の出力が各セグメントに分割された圧縮されているフレームであり、その各セグメントに動き係数が随伴しているとするならば、座標(xi,yi），i=1，2，．．．，P、のP個のピクセルからなるセグメントＳiについて、動きフィールド符号器の任務は、圧縮されている動きベクトルフィールド
0003781194.tif 000011
の動き係数
0003781194.tif 000012
を求めることであり、その動きベクトルは線形動きモデルで記述され、そのフィールドは下記の形を持っており：
0003781194.tif 000013
それは二乗予測エラー：
0003781194.tif 000014
を最小化するようになっている。
前記の任務を達成するために、動きフィールド符号器は３つの主な構成ブロックからなっており、それらはＱＲ動き分析ブロック、セグメント併合ブロック、及び動き係数除去ブロックである。セグメント併合ブロック及び動き係数除去ブロックは、二乗予測エラーを増大させる結果をもたらす動き情報の量を減少させる。
ＱＲ動き分析器の目的は、動きフィールドの新しい表示を求めることである。その新しい表示は、後に、他の２つのブロック、即ち併合されたセグメントについての動き係数を高速で且つ柔軟に求めるためのブロック及び係数除去を行うブロック、で使用される。ＱＲ動き分析器の動作は下記のステップからなる。
即ち、ステップ１はエラーの線形化である。このステップでは方程式（５）の予測フレーム
0003781194.tif 000015
が公知の何らかの近似方法によって近似されて
0003781194.tif 000016
に関して線形となる。すると、式（５）の総和での各要素は係数ｃiの一次結合となる：
0003781194.tif 000017
ステップ２は行列の作成である。それは、式（６）の最小化が行列表示
0003781194.tif 000018
の最小化と全く同等であるという事実に基づいており、ここでＥi及びｙiは次の通りである：
0003781194.tif 000019
ステップ３はＱＲ因数分解である。周知のＱＲ因数分解アルゴリズムがG.H.ゴルブ及びＣ．ブァン・ローンの文献”行列計算”第２版、１９８９年ジョンズホプキンス大学出版会（the document G. H. Golub and C. van Loan, ”Matrix computation”2'nd edition, The Jojns Hopkins University Press, 1989）で解説されている。このアルゴリズムを使用してＥiを２つの行列の積に分解する：
Ｅi＝ＱiＲi    (8)
このステップで補助ベクトルｚiも計算するが、これは次の通りである：
ｚi＝ＱTiｙi    (9)
ステップ４ではＱＲ動き分析ブロックの出力を計算する。その出力は行列Ｒiの始めのN+M個の行からなる行列Ｒi1と、ｚiの始めのN+M個の要素からなるベクトルｚ1iとからなる。
セグメント併合ブロックでは、隣り合うセグメントＳi及びＳj（図４を参照）の対を、動き係数ｃijによって記述される共通の動きフィールドを使ってそれらの結合領域Ｓijを予測できるか否かを判定して、併合操作がなされる。合併操作は次の各ステップからなる。
即ち、ステップ１は行列計算からなる。本発明は、下記の一次方程式の系：
0003781194.tif 000020
を解くことによって動き係数ｃijを求めることができるという、以前は知られていなかった性質を利用する。ここでＲ1i，ｚ1i及びＲ1j，ｚ1jは、それぞれセグメントＳi及びＳjについてＱＲ分析ブロックにより既に作成されている。
ステップ２は、ステップ１で得られた行列を三角行列にする（triangularization）ステップである。行列Ｒ1i，Ｒ1jは上部の三角行列であり、方程式系（１０）は前記の文献の教示によると下記の形を有する：
0003781194.tif 000021
ここで記号×はゼロでない要素を表す。前記の文献の教示によると、この系は、各行にスカラーを乗じる一連の掛け算を行った後にそれらの行を加えることによって三角行列にされる、即ち、それは下記の形に変換される：
0003781194.tif 000022
ステップ３では併合エラーを計算する。セグメントＳi及びＳjの併合により生じる領域Ｓijでの二乗予測エラーの変化ΔＥijを前記の文献の教示に従って次のようにして計算する：
0003781194.tif 000023
最後に、ステップ４で、式（１３）の二乗予測エラーの変化が、選択された基準に照らして許容できる程度であるならば、前記のセグメント同士を併合させる。それにより得られた新しいセグメントＳijについて、方程式系（１２）の始めのN+M個の行をとることによって行列Ｒ1ij及びベクトルｚ1ijを作成する、即ちそれらは下記の式によって与えられる：
0003781194.tif 000024
フレームのセグメントの全ての対が検討された後、セグメント併合ブロックの出力が得られる。その出力は３種類の情報からなる。第１に、その出力は、セグメントの個数が減らされている、画像の新しい分割態様を提示する。第２に、新しいセグメントの各々について該ブロックは行列Ｒ1ij及びベクトルｚ1ijを出力する。第３に、該ブロックは併合情報を提示し、それは復号器に送られて、復号器が併合されたセグメントを識別しやすくする。
今、方程式系Ｒ1ijｃij＝ｚ1ijを解くことによってセグメントＳijについての動き係数ｃij（ｃ1，ｃ2，．．．ｃN+M）を計算することができるが、もし次のブロック（係数除去ブロック）を使用するのならばその計算は不要である。
ここで係数除去ブロックの動作を考察する。このブロックは入力として現在のフレームのセグメントへの新しい分割態様を受け取るとともに、全てのセグメントＳkについて、前もってセグメント併合ブロックによって作成された行列Ｒ1k，ｚ1k及びｃkを受け取る。どのセグメントの動きベクトルもN+M個の動き係数によって表示される。
動き係数除去ブロックは、与えられたセグメントＳkについて予測エラーをあまり増大させることなく動きフィールドモデルを簡単化することが可能か否かを判定する。本明細書の背景技術の項で説明した方程式（３）のモデルから何らかの基底関数が除去されると、簡単化された動きフィールドモデルが得られる。その様に簡単化された動きフィールドモデルを記述するのに必要な係数は比較的に少なくなっている。
動きフィールドモデルからi番目の基底関数（及びi番目の係数）を除去できるか否かを判定するために、下記の処理手順が各セグメントに対して実行される。
即ち、ステップ１は行列修正を含んでおり、ここでＲ1kからi番目の列を除去し、ｃkからi番目の要素を除去することによって下記の一次方程式系：
Ｒ1kｃk＝ｚ1k    (15)
を修正する。
ステップ２は行列三角化を含んでおり、ここで各行にスカラーを乗じる一連の掛け算を行った後にそれらの行を加えることによって方程式系（１５）が公知の方法で三角行列にされる、即ち、それは下記の形に変換される：
0003781194.tif 000025
ステップ３はエラー評価を含んでいる。i番目の係数の除去によって生じるセグメントについての二乗予測エラーの変化は、単に方程式（１６）の中の項ｑ2iに等しい。
ステップ４は係数の除去を含んでいる。もし予測エラーの変化が選択された基準に照らして許容できる程度であれば、係数ｃiは係数の集合から除去される。これで係数の新しい個数はN+M-1となる。行列Ｒ1k及びベクトルｚ1kは下記の形に修正される：
0003781194.tif 000026
行列（１７）を方程式（１５）で使用してステップ１−４を繰り返すことによって、このセグメントについての係数の個数を更に減らすことができる。
ステップ５は係数計算を含んでいる。充分な数の係数が除去された後、このステップが始まる。このステップで、一次方程式系：
Ｒ1kｃk＝ｚ1k    (18)
を解くことによってセグメントＳkについての最終の動き係数が計算される。ここで行列Ｒ1k及びベクトルｚ1kは前のステップ１−４の結果である。例えば後退代入（backsubstitution）など、周知のアルゴリズムの１つを使ってこの方程式を解くことができる。
動き係数除去ブロックは、処理した全てのセグメントについて、どの基底関数が動きフィールドモデルから除去されたのかを復号器に知らせる選択情報を出力する。また、該ブロックは残っている基底関数に対応する新しい動き係数を出力する。この選択情報と動き係数との両方が復号器に送られる。
これらブロックの全てにおける全てのステップの結果として、本発明による動きフィールド符号器は、どのセグメントが併合されたかを復号器に知らせる併合情報と、どの基底関数が除去されたかを復号器に知らせる選択情報と、動き係数情報とを作成する。
従来技術と比べると、本発明の主な利点は、予測エラーを大幅に増大させずに動き情報の量を大幅に減少させることができることである。また、システム全体の複雑さが低くて、利用可能な信号処理装置或いは汎用マイクロプロセッサで実用的に実現できる。
セグメント併合ブロックは、別々のセグメントについて推定された与えられた動きベクトルから、結合されたセグメントの動きベクトルを求めることができるという独特の能力を持っている。このブロックが作成する動きベクトルは、実際上、結合されたセグメントについての二乗エラーを最小に保つことに関して最適であることを証明することができる。このことが、このブロックが二乗予測エラーをごくわずか増大させるだけでセグメントの個数を劇的に減少させる能力を持っていることの理由である。
動き係数除去ブロックは、動きモデルをビデオシーンの中の動きの実際の量及び種類に瞬時に適応させるための非常に強力な手段である。このブロックは、例えば実現可能なあらゆる動きフィールド基底関数の組み合わせなど、非常に多数のモデルで予測の結果（セグメントについての二乗予測エラーの値）を容易に試験することができる。他の公知の如何なる方法もこの様な柔軟性を持っていない。この方式の強力な利点は、動き推定のプロセスを反復する必要がないので計算が簡単だということである。
動き推定後にＱＲ動き分析を行うことによって、この動きフィールド符号器は、画像セグメントの所望の如何なる組み合わせについても、或いはセグメントの動きフィールドの所望の如何なるモデルについても、非常に単純な一次方程式系を解くことによって新しい動き係数を求めることができる。
好ましい実施例の説明
好ましい実施例では１２個の係数を有する下記の二次多項式動きベクトルフィールドモデルが使用される：
0003781194.tif 000027
このモデルは、実際上、ビデオシーケンスにおける非常に複雑な動きでも十分に処理することができて、良好な予測結果をもたらす。
ＱＲ動き分析ブロックで、下記の各点：
x′i＝xi＋Δx(xi，ｙi）
y′i＝yi＋Δy(xi，yi）
の周りの全てのピクセル(xi，yi），i=1，2，．．．，P、での
0003781194.tif 000028
のテイラー展開（Taylor expansion）を使ってステップ１での線形化を行う。
0003781194.tif 000029
という性質を使うと、予測エラーは下記の通りとなる：
0003781194.tif 000030
下記の式：
0003781194.tif 000031
を使って補助値ｇj(x,y)を計算する。ここで関数ｆj(xi，yi）は方程式（4a）及び(4b）で定義される基底関数である。
方程式（９）の中の行列E及びベクトルyは下記の式：
0003781194.tif 000032
を使って作成される。Ｇx(x,y)及びＧy(x,y)は、下記の式：
0003781194.tif 000033
を使って計算される参照フレーム
0003781194.tif 000034
の水平勾配及び垂直勾配の値である。
図６はＱＲ動き分析器の略図である。行選択ブロックは入力された行列の始めのN+M個の行だけを選択する。セグメント併合ブロックでは、セグメント併合のために下記の方針が実行される：
ａ．フレーム全体で許容される二乗予測エラーの増加に対応するしきい値Ｔを選択する。
ｂ．隣り合うセグメント同士の全ての対について方程式（１３）を使ってΔＥijを計算する。
ｃ．ΔＥijが最小であるセグメントの対を併合させる。
ｄ．併合された全てのセグメント対に対応するΔＥijの総和がTより大きくなるまでポイントｂ−ｃを繰り返す。
方程式系（１１）を三角化するために、一連のギブンズ回転（Givens rotations）が使用される。
動き係数除去ブロックでは係数除去のために下記の方針を実行する：
ａ．フレーム全体で許容される二乗予測エラーの増加に対応するしきい値Ｔを選択する。
ｂ．全てのセグメント及び全ての基底関数について方程式（１６）を使ってｑi2を計算する。
ｃ．ｑi2が最小のセグメントの基底関数を除去する。
ｄ．いろいろなセグメントで除去された全ての基底係数に対応する全てのｑi2の総和がTより大きくなるまでポイントｂ−ｃを反復する。
式の系（１６）は、一連のギブンズ回転によって三角化される。
セグメントの最終の動き係数は、後退代入アルゴリズムを使用して方程式（１８）を解くことによって計算される。
0003781194.tif 000035
のピクセル値は、整数座標x及びyだけについて定義される。x又はyが整数でない多くの場合に、整数座標を持った最も近い各ピクセルの双線形補間を行ってそのピクセル値を計算する。
このシステムを、本発明の範囲から逸脱せずにいろいろに実施することができる。例えば、方程式（３）でいろいろな線形動きモデルを使用することができる。いろいろな方法を使用して式（５）の項を線形化することができる。更に、２つのセグメントを併合させるか否かを決定するためにいろいろな基準を用いることができる。与えられた基底関数をモデルから除去するべきか否かを決定するための方針は様々であってよい。方程式（１０）及び（１５）の各行列の三角化をいろいろなアルゴリズムを使用して実行することができ、方程式（１８）を解くことによる最終係数の計算を、一次方程式系を解くための公知のいろいろなアルゴリズムを使用して実行することができる。最後に、非整数座標における
0003781194.tif 000036
の値に対していろいろな補間方法を使用することができる。
【図１】
0003781194.tif 000048
【図２】
0003781194.tif 000049
【図３】
0003781194.tif 000050
【図４】
0003781194.tif 000051
【図５】
0003781194.tif 000052
【図６】
0003781194.tif 000053