JPH06253291A - ビデオイメージ処理における符号化信号の発生方法及びその装置 - Google Patents

Abstract

(57)【要約】 【目的】 ビデオ信号の符号化を効率よく行う方法及び
装置を提供する。 【構成】 補間法を用いて行うビデオイメージ信号の符
号化において、動作推定器１１８において、各基準フレ
ームからそれぞれ１つの候補変位を有するような候補変
位グループのセットとこれに対応する最良重みとが決定
され、これらの候補変位とこれに対応する最良重みとを
用いて画素ブロックを表した場合に生じる誤差信号の値
が検討される。次に動作推定器１１８において、誤差信
号の値の最も小さいグループが、そのブロックを表す候
補変位グループとして、又は別の新たなグループセット
を選択するための出発点のグループとして選択される。
ブロック選択に際し、イメージの既知特性と本発明に基
づく補間法とを用いることにより、選択のための検討を
要する候補変位グループの数を、予め定められた探索範
囲内の検討対象グループ数最大値よりも少ない数に減じ
て検討が行われる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ビデオイメージ処理に
関し、特に、動作予測イメージ処理システムに（複数
の）基準フレームが採用される場合のイメージブロック
の動作推定方法に関する。

【０００２】

【従来の技術】ビデオイメージ信号符号化システムにお
いては、ビデオイメージフレーム（以下、フレーム）を
表すビデオイメージ信号におけるデータを圧縮するため
に動作推定技術を用いることが広く知られている。

【０００３】動作推定技術の一つである動作補償予測を
用いた符号化（動作補償予測符号化）においては、符号
化すべきフレームの各ブロックに、順次、動作ベクト
ル、すなわち、そのブロックに最もよくマッチするよう
な、前に符号化された基準フレームにおける同じ大きさ
のブロックの位置に一致するブロック位置（例えば各ブ
ロックにおける所定の位置から定義されるようなブロッ
ク位置）に関しての変位ｄが割り当てられる。

【０００４】動作ベクトルとして採用すべき変位を選択
するためには、候補変位のセットから最良の候補変位を
求める探索が行われる。一般に、変位の複数の候補から
なる候補変位セットは、符号化すべきフレームにおける
ブロックの位置から所定の距離範囲内にある変位の全て
によって構成され、又、所定の一連の基準に合致する候
補変位が、最良候補変位なる。この合致基準で最も多く
用いられるのは、絶対誤差信号の積分が最小になるかど
うかの判断基準で、これを式で示すと、次の数式［数
１］となる。

【０００５】

【数１】

【０００６】ここにおいて、ｘ’は、ｘに位置するブロ
ックを構成する全画素の位置からなる位置セットである
Ｎ（ｘ）、のメンバーである個別画素の位置を意味す
る。又、ｘは、各ブロックにおける同じ所定の点位置
で、ｘの値は、フレームの格子構造に関して計測され
る。Ｉn（）及びＩn-1（）は、その下付き文字で示され
るフレームにおいてその独立変数によって指定される位
置にある画素の輝度値をもたらす関数である。尚、位置
及び変位は全て、ベクトルである。これを示すために、
本明細書の数式、及び図面においては、ｘ及びｄの太字
で表す場合がある。

【０００７】実施例によっては、上手に推定した最適変
位を動作ベクトルとして用いる場合がある。これは、こ
のような推定によって探索作業が少なくて済むためであ
る。各ブロックについて動作ベクトルとして選択された
変位と、対応する誤差信号とが、ブロックの表示子とし
て用いられた。

【０００８】ビデオイメージを表すデータを更によく圧
縮するには、動作補償補間法が用いられる。これは、一
種の動作推定技術で、符号化すべきフレームに関して後
の時点（未来）に、基準フレームを１つ追加して組み込
む方法である。補間法においては、時間的にこれら基準
フレームの間にあるフレームについて予測を行う。そし
て、補間によって、符号化すべき各ブロックごとに時間
的に前（過去）の基準フレーム内の１つのブロックと時
間的に後（未来）の基準フレーム内の１つのブロックと
が、これらのブロックが組合せられたときにこの符号化
すべきブロックに最も良く近似した信号が得られるよう
に、決定される。

【０００９】この組合せは一般に、選択されたブロック
の画素値の、重み（ウエート）付けされた和（加重和）
の形で表現される。符号化すべきブロックから決定され
たブロックへの変位（過去の基準フレーム内のブロック
への変位ｄm 及び未来の基準フレーム内のブロックへの
変位ｄp ）の各々が、動作ベクトルとして採用される。
更に、現在対象となるブロック（現ブロック）を構成す
る画素値から加重和を減じて、補間誤差信号が得られ
る。

【００１０】

【発明が解決しようとする課題】加重和に用いられる重
みの決定は一般に、重みに所定の限度を設けるか、又は
候補変位に所定の限度を設けるかして行われる。例え
ば、ブロックごとに両方の変位したブロックから平等に
（１／２、１／２）値を取る方法、又は、或るブロック
については基準フレーム（０，１）及び（１，０）のう
ちの一方からだけ値を取る方法がある（ＩＳＯ（国際標
準化機構）のＭＰＥＧ提案草案を参照）。各ブロックに
ついての動作ベクトル、誤差信号、及び重みファクター
が、そのブロックの表示子として用いられる。

【００１１】これら従来の圧縮技術は、利用可能な帯域
幅を最適利用していないため、再構築イメージを最適化
するにはより大きな帯域幅を必要としていた。

【００１２】

【課題を解決するための手段】従来の圧縮技術である動
作補間技術の問題点を解決するための、本発明における
手段は、補間されるフレームと基準フレーム内のブロッ
クの加重和との間の誤差を、重み、又は動作ベクトルに
用いられる変位、のいずれにもその値に限度を設けず
に、最小化する（誤差が最小になる状態を求める）よう
にして、補間されるフレームに含まれるイメージの各画
素ブロックを表す信号を発生させる方法及び装置であ
る。誤差の最小化を達成するような重み及び変位が、画
素ブロックごとに、共に決定される。

【００１３】各基準フレームから１つずつ取った候補変
位を有する候補変位グループのセットと、本発明によ
る、候補変位に対応する最良重みとが決定される。次
に、各基準フレームから取った候補変位グループのセッ
トの各メンバーとこれに対応する最良重みとを用いて画
素ブロックを表した場合に生じる誤差信号の値が検討さ
れる。誤差信号の最も小さいグループが、そのブロック
を表す候補変位グループとして、又は別の新たなグルー
プセットを選択するための出発点のグループとして選択
される。

【００１４】画素ブロックを表すために検討対象とすべ
き候補変位グループの数は、実際の最適変位とこれに対
応する最良重みとの代わりに、上手に推定した最適変位
とこれに対応する最良重みとを用いた場合、又はイメー
ジの既知特性と本発明とを利用した場合に、所定の探索
範囲内にある選択される可能性のある全ての候補変位を
検討する場合に検討対象とされるグループ数の最大値よ
りも少ない数にすることができる。

【００１５】又、所定の制約を変位と重みとに設けるこ
とによって、更に利点が得られる。加えて、本発明によ
り、画素ブロックの再構築版（再構築バージョン）に生
じる、重み量子化に起因する誤差増加、が少ないように
重みを量子化したバージョンが、実際に採用される重み
として決定される。

【００１６】

【実施例】図１に、本発明に基づき、ディジタル形式で
表される一連のイメージフレーム（ＶＩＤＩＮ信号）
（以下、Ｖ信号）を符号化するためのビデオ変換符号器
１００を簡単なブロック図で示す。説明を分かりやすく
するために、図示の各素子に埋め込まれる、演算、作動
順序設定、及び調整用に必要な記憶素子は、図示しな
い。しかし、これらの記憶素子の使用については当業者
に明らかである。又、全体のタイミング及び作動順序設
定を行うコントローラも図示しない。このコントローラ
の使用についても、当業者には明らかである。

【００１７】ビデオ変換符号器１００は、これに入力と
して供給されたＶ信号のイメージフレーム（以下、フレ
ーム）を表す符号化されたディジタルデータ信号（ＢＩ
ＴＳＴＲＥＡＭ信号）（以下、ＢＩＴ信号）をその出力
として供給する。ビデオ変換符号器１００に供給された
各フレームは、そこで次の３つの符号化方法、又は形
式、すなわち、フレーム内相互符号化、動作補償予測符
号化、及び多重フレーム動作予測補間符号化（動作予測
補間符号化）のうちの１つによって、符号化される。

【００１８】Ｖ信号は、ビデオ変換符号器１００内の制
御・フレーム再構成ユニット１０１に入力として供給さ
れる。制御・フレーム再構成ユニット１０１は、ビデオ
変換符号器１００全体の動作を制御し、フレームの時間
的位置に基づいてそのフレームをどの形式で符号化すべ
きかを決定する。

【００１９】本実施例の説明に当たっては、どのフレー
ムについてもその符号化形式を数字で表し、「０」でフ
レーム内相互符号化、「１」で動作補償予測符号化、及
び「２」で、本発明に基づく、動作予測補間符号化を示
すこととする。フレーム内相互符号化及び動作補償予測
符号化については、周知である。

【００２０】制御・フレーム再構成ユニット１０１は、
一時的にＶ信号のフレームのうちの所定の数のフレーム
を記憶し、フレームが、受信された時間順序と異なる時
間順序で出力として供給されるようにする。各々特定の
位置を有する画素からなる格子構造として構成される各
フレームは、Ｑ×Ｒ個の画素ブロックに分割される。

【００２１】これらの画素ブロックは、受信された時間
順序と異なる所定の時間順序に、ＢＬＯＣＫＳ信号（以
下、ＢＬＫ信号）として供給される。この順序再設定
は、動作推定及び補間に必要な少なくとも２つの基準フ
レームを、動作予測補間符号化すべきフレームの処理に
先立って処理できるようにするために行うものである。
制御・フレーム再構成ユニット１０１によって決定され
た符号化形式は第１制御バス（母線）１０２上をスイッ
チ素子１０３〜１１０に搬送される。

【００２２】ブロック形式ユニット１１１は、或る画素
ブロックの属するフレームがビデオ信号（Ｖ信号）内の
フレームの時間位置に基づいて動作補償予測符号化又は
動作予測補間符号化されるように制御・フレーム再構成
ユニット１０１によって指定されているにも拘らず、そ
の画素ブロックがフレーム内相互符号化されるべきかど
うか、を画素ブロックごとに、決定する。

【００２３】この決定は、フレーム内相互符号化の方が
他の符号化形式よりもその画素ブロックを表すビット数
が少なくて済むとブロック形式ユニット１１１が判断し
た場合に、その判断に基づいて行われる。この目的のた
め、ブロック形式ユニット１１１には、ＢＬＫ信号と、
その画素ブロックの動作補償予測符号化又は動作予測補
間符号化による再構築バージョンの実際の画素ブロック
に関しての誤差を表す信号（Ｅ信号）とが供給される。
尚、Ｅ信号は減算器１１２から供給される。

【００２４】ブロック形式ユニット１１１は、第２制御
バス１１５を経てコマンド（指令）を送り、スイッチ素
子１１３及び１１４を制御する。更に、可変長符号器
（ＶＬＣ）１１６は、ブロック形式ユニット１１１のコ
マンドに応答して多重化・バッファユニット１１７への
動作ベクトル又は重みの供給を抑制する。

【００２５】ビデオ変換符号器１００内の素子で、或る
画素ブロックの処理中にその属する出力を生成するのに
必要な入力についての受信がない素子は、その画素ブロ
ックの処理中は動作がないものと考える。これらの入力
が受信されないのは、スイッチ素子１０３〜１１０、１
１３及び１１４のうちの１つ以上の素子の切換位置によ
るものである。

【００２６】説明を分かりやすくするため、Ｖ信号が最
初、ビデオ変換符号器１００の初期化後に受信される
か、又はビデオ変換符号器１００が、フレーム内相互符
号化によって符号化された新しいベースフレームを所定
の間隔で送り、現在もそうしているものと仮定する。

【００２７】フレーム内相互符号化モードで動作中、ス
イッチ素子１０３〜１１０、１１３及び１１４は各々、
その切換レバーが、少なくとも１つの「０」を有する端
子に接続される位置にあるように構成されている。もし
そのスイッチ素子に、少なくとも１つの「０」を有する
端子がない場合は、そのスイッチの位置は無関係であ
る。

【００２８】ＢＬＫ信号は、制御・フレーム再構成ユニ
ット１０１からスイッチ素子１０３及び１１４を経て離
散コサイン変換ユニット（ＤＣＴ）１１９に送られる。
Ｑ×Ｒ個の画素ブロックは、次に離散コサイン変換ユニ
ットによって、画素領域から離散コサイン変換領域に変
換される。離散コサイン変換ユニット１１９は、入力と
して受信した画素ブロックと同じ大きさの２次元画素ブ
ロックにグループ分けされる周波数係数（変換係数）の
セットを、出力として供給する。

【００２９】離散コサイン変換ユニット１１９から出力
として得られた変換係数は、量子化器１２０に供給され
る。量子化器は、係数に利用できる仮定用レベル数を減
少させる。量子化を、量子化制御信号（ＱＮＴＣＴＲＬ
信号）を介して多重化・バッファユニット１１７に記憶
される情報の数量に応答して行わせるように構成するこ
とも、オプションとして可能である。量子化器１２０か
ら出力として得られる量子化された係数は、次いで可変
長符号器（ＶＬＣ）１２１に符号化用の入力として供給
される。可変長符号化は周知であり、符号化方法の選択
は、符号化実現の際に自由に決めればよい。

【００３０】量子化された係数を符号化した符号化表示
信号は、出力として多重化・バッファユニット１１７に
供給される。多重化・バッファユニット１１７は、この
量子化された係数の符号化表示信号を、可変長符号器１
１６及び１２１の出力と共に多重化の方式で、ＢＩＴ信
号として出力する。このＢＩＴ信号は、用途によって、
伝送しても、記憶させてもよい。

【００３１】量子化器１２０から出力として供給され
る、量子化された係数は、スイッチ素子１０５を経て逆
量子化器１２３にも入力として供給される。逆量子化器
１２３は、量子化された係数について逆量子化を行うも
ので、これによって、再構築された係数を生成し、この
再構築された係数は、逆離散変換ユニット（ＩＤＣＴ）
１２４に供給され、ここで、画素領域におけるブロック
の再構築バージョンが生成される。

【００３２】この再構築された画素ブロックは、加算器
１２６及びスイッチ素子１０６を経てフレームバッファ
（Ｆ１）１２５に供給され、そこで記憶される。加算器
１２６には、ゼロブロック源１２７から全てがゼロの、
ゼロブロックが供給される。フレームバッファ１２５に
記憶される最初のフレームが、予測又は補間されるべき
フレームについての、過去（Ｉm ）の基準フレームとな
る。

【００３３】第１フレームについての処理の最終段とし
て、制御・フレーム再構成ユニット１０１は、第１フレ
ーム及び動作補間すべき全てのフレームに関して未来に
ある第２フレーム（Ｉp ）のＱ×Ｒ個の画素ブロックを
出力のＢＬＫ信号として、新しいベース時間長さが選択
されるまで供給する。

【００３４】更に、スイッチ素子１０３〜１１０は各
々、第１制御バス１０２上で制御・フレーム再構成ユニ
ット１０１に制御されて、その切換レバーが、少なくと
も１つの「１」を有する端子に接続される位置にあるよ
うに構成されている。もしそのスイッチ素子に、少なく
とも１つの「１」を有する端子がない場合は、そのスイ
ッチの位置は無関係である。

【００３５】説明を分かりやすくするために、第２フレ
ームの画素ブロックは全て動作補償予測符号化が適用さ
れ、ブロック形式ユニット１１１がスイッチ素子１１３
及び１１４の切換レバーを少なくとも１つの「１」を有
する端子に接続される位置に配置するものと仮定する。

【００３６】ＢＬＫ信号のＱ×Ｒ個の画素ブロックは各
々、動作推定器１１８及び減算器１１２の両方に入力と
して供給される。動作推定器１１８は、フレームバッフ
ァ１２５から第１フレームの再構築バージョンを、又、
ゼロブロック源１２７からゼロブロックを、それぞれ入
力として受信し、動作ベクトル、すなわちその画素ブロ
ックに最もよくマッチするような基準フレームＩm にお
ける同じ大きさの画素ブロックの位置に合致するブロッ
ク位置に関しての変位、を出力として供給する。

【００３７】画素ブロックの各々についての動作ベクト
ルは、スイッチ素子１０８を経て動作補償器１２８に、
又、可変長符号器１１６にそれぞれ供給され、可変長符
号器１１６においては、多重化・バッファユニット１１
７によってＢＩＴ信号に組み込まれる前に、符号化され
る。動作補償器１２８は、現在フレームバッファ１２５
に記憶されている、前に再構築されフレームも受信し、
現フレームにおける画素ブロックの予測バージョンを生
成し、スイッチ素子１０４を経て減算器１１２に供給す
る。

【００３８】減算器１１２は、実際の現ブロックから現
ブロックの予測バージョンを減じて、誤差信号（Ｅ信
号）を生成し、スイッチ素子１１４を経て離散コサイン
変換ユニット１１９に供給する。離散コサイン変換ユニ
ット１１９は、この誤差信号を離散コサイン変換領域に
変換し、結果として得られる変換された誤差信号は、量
子化器１２０に送られ、そこで量子化される。

【００３９】変換され量子化された誤差信号は、量子化
器１２０から出力され、可変長符号器１２１に入力とし
て供給され、そこで符号化される。変換され量子化され
た誤差信号の符号化表示としての信号は、可変長符号器
１２１からの出力として多重化・バッファユニット１１
７に供給される。

【００４０】変換され量子化されて量子化器１２０から
出力された誤差信号は、スイッチ素子１０５を経て逆量
子化器１２３にも入力として供給される。逆量子化器１
２３は、変換され量子化された誤差信号について逆量子
化を行うもので、これによって、再構築された誤差信号
を生成し、この再構築された誤差信号は、逆離散変換ユ
ニット（ＩＤＣＴ）１２４に供給され、ここで、画素領
域における誤差信号の再構築バージョンが生成される。

【００４１】この画素領域における誤差信号の再構築バ
ージョンは、加算器１２６によって、スイッチ素子１１
３を経て受信された現フレーム内の画素ブロックの動作
予測バージョンに加えられ、現ブロックに極めて正確に
対応する補正された予測現ブロックが形成される。この
補正された予測現ブロックは、スイッチ素子１０６を経
てフレームバッファ（Ｆ２）１３０に供給され、そこで
記憶される。

【００４２】現フレームに対応する画素ブロックは、フ
レームバッファ１３０に蓄積され、補間されるべきフレ
ームについての、未来の基準フレーム（Ｉp ）となる。
可変長符号化された動作ベクトルと、変換され量子化さ
れ可変長符号化された誤差信号とは、多重化・バッファ
ユニット１１７によって一体に多重化されてＢＩＴ信号
に形成され、更には、用途に応じて伝送され、又は記憶
される。ＢＩＴ信号は、対応する復号器によって元のフ
レームの表示信号を再構築するのに用いることもでき
る。

【００４３】次に続くフレームは、そのＱ×Ｒ個の画素
ブロックが制御・フレーム再構成ユニット１０１によっ
てＢＬＫ信号として供給されるが、このフレームは、動
作補償予測された第２フレームよりも後の時点に存在す
るフレームが符号化されるまで、動作補間される。

【００４４】スイッチ素子１０３〜１１０は各々、第１
制御バス１０２上で制御・フレーム再構成ユニット１０
１に制御されて、その切換レバーが、少なくとも１つの
「２」を有する端子に接続される位置にあるように構成
されている。もしそのスイッチ素子に、少なくとも１つ
の「２」を有する端子がない場合は、そのスイッチの位
置は無関係である。

【００４５】説明を分かりやすくするために、次ぎに続
くフレームの画素ブロックは全て動作予測補間符号化が
適用され、ブロック形式ユニット１１１がスイッチ素子
１１３及び１１４の切換レバーを少なくとも１つの
「２」を有する端子に接続される位置に配置するものと
仮定する。

【００４６】ＢＬＫ信号のＱ×Ｒ個の画素ブロックは各
々、動作推定器１１８及び減算器１１２の両方に入力と
して供給される。動作推定器１１８は、フレームバッフ
ァ１２５から第１（過去）フレームの再構築バージョン
を、又、フレームバッファ１３０から第２（未来）フレ
ームの再構築バージョンを受信する。

【００４７】本発明により、動作推定器１１８は、動作
ベクトルのセット、すなわちその画素ブロックの位置
の、所定の区域内の変位ｄm 及びｄp を導き出し、出力
として供給する。ここで、ｄm は、過去の基準フレーム
（Ｉm ）内の同じ大きさの画素ブロックを向く方向にあ
り、ｄp は、未来の基準フレーム（Ｉp ）内の同じ大き
さの画素ブロックを向く方向にある。そして、これらの
変位が向く先のブロックの画素値の荷重和が符号化され
るブロックに最もよく近似するように選ばれる。

【００４８】動作ベクトルは、スイッチ素子１０８を経
て動作補間器１２９に、又、可変長符号器１１６にそれ
ぞれ供給され、可変長符号器１１６においては、多重化
・バッファユニット１１７によってＢＩＴ信号に組み込
まれる前に、符号化される。動作推定器１１８は又、本
発明により、そのブロックについての動作ベクトルの各
々が向く先のブロックの画素値に対する重み値（重み）
αm、αpのセットを出力として動作補間器１２９に供給
する。尚ここで、１つの重みは動作ベクトルの各々にそ
れぞれ１つずつ対応する。

【００４９】動作補間器１２９は、現在フレームバッフ
ァ（Ｆ１）１２５に記憶されている、前に再構築されフ
レームを、又、フレームバッファ（Ｆ２）１３０から第
２（未来）フレームの再構築バージョンを、更に、スイ
ッチ素子１０８を経て動作ベクトルを、そしてスイッチ
素子１０９を経て重みを、それぞれ受信し、現フレーム
における画素ブロックの動作補間バージョンを生成し、
スイッチ素子１０４を経て減算器１１２に供給する。

【００５０】現フレームにおける画素ブロックの動作補
間バージョンは、第１（過去）フレームについての、動
作ベクトルが向く先のブロックの画素値に過去のフレー
ムについての重みを乗じ（重み付けし）、これを、第２
（未来）フレームについての、動作ベクトルが向く先の
ブロックの画素値に未来のフレームについての重みを乗
じたものに加えることによって導き出される。

【００５１】減算器１１２は、実際の現ブロックから現
ブロックの補間バージョンを減じて、誤差信号（Ｅ信
号）を生成し、スイッチ素子１１４を経て離散コサイン
変換ユニット１１９に供給する。離散コサイン変換ユニ
ット１１９は、このＥ信号を離散コサイン変換領域に変
換し、結果として得られる変換されたＥ信号は、量子化
器１２０に送られ、そこで量子化される。変換され量子
化されたＥ信号は、量子化器１２０から出力され、可変
長符号器１２１に入力として供給され、そこで符号化さ
れる。

【００５２】変換され量子化されたＥ信号の符号化表示
信号は、可変長符号器１２１からの出力として多重化・
バッファユニット１１７に供給される。動作推定器１１
８からの重みは、スイッチ素子１０９を経てオプション
の量子化器１３１に供給され、ここで重みが量子化さ
れ、量子化された重みは、可変長符号器１１６に供給さ
れる。

【００５３】多重化・バッファユニット１１７は、この
変換され量子化されたＥ信号の符号化表示信号を、可変
長符号器１１６及び１２２の出力と共に多重化の方式
で、ＢＩＴ信号として出力する。このＢＩＴ信号は、用
途によって、伝送しても、記憶させてもよい。

【００５４】或る画素ブロックが、そのフレームの時間
位置に基づきブロック形式ユニット１１１によって動作
補償予測形式又は動作補間形式すべきであると決定され
たフレームに属する場合、ブロック形式ユニット１１１
は、その特定の画素ブロックを直接にフレーム内相互形
式で符号化した方が、必要とするビット数がより少なく
て済むという決定をしてもよい。

【００５５】この場合の決定は、いずれもブロック形式
ユニット１１１に入力として供給された、Ｅ信号と実際
のフレーム自身との複雑さの比較に基づいてなされる。
もし形式ユニット１１１が、その特定のブロックを直接
にフレーム内相互符号化形式で符号化した方が、必要と
するビット数がより少なくて済むという決定をすると、
スイッチ素子１１３及び１１４は、第２制御バス１１５
を経て送られるコマンドを介して、「０」の端子に接続
するように命令される。

【００５６】更に、可変長符号器１１６は、ブロック形
式ユニット１１１のコマンドに応答して多重化・バッフ
ァユニット１１７への動作ベクトル及び重みの供給を抑
制する。選択された画素ブロックは、この結果として、
上記のように、フレーム内相互形式で符号化される。ブ
ロック形式ユニット１１１は、選択された符号化形式を
示す表示信号を供給する。この表示信号はそれ自身、可
変長符号器１２２によって符号化され、多重化・バッフ
ァユニット１１７に供給され、そこでＢＩＴ信号に適切
に組み込まれる。

【００５７】もしそのブロックが動作補償予測形式で符
号化されることになっていた場合は、フレーム内相互形
式で符号化されることになったフレームの画素ブロック
について画素領域のブロックの再構築バージョンが上記
のように生成される。しかし、画素領域のブロックの再
構築バージョンは、スイッチ素子１０６の位置の関係か
ら、フレームバッファ１２５の代わりにフレームバッフ
ァ１３０に記憶されることになる。

【００５８】制御・フレーム再構成ユニット１０１が、
第１（過去）フレームと第２（未来）フレームとの間の
フレームが全て符号化されたと判断すると、スイッチ素
子１１０が閉じられ、未来イメージフレームである、フ
レームバッファ１３０に記憶されているイメージフレー
ムが、フレームバッファ１２５にコピーされて、新たな
過去イメージフレームとなる。その後、古い未来フレー
ムよりも更に未来にある、新たな未来フレームが、動作
補償予測形式で符号化されてフレームバッファ１３０に
記憶される。

【００５９】代替方法として、制御・フレーム再構成ユ
ニット１０１が新たに、２つのフレームを選択し、その
一方をフレーム内相互形式で符号化してフレームバッフ
ァ１２５に記憶させ、他方を動作補償予測形式で符号化
してフレームバッファ１３０に記憶させるようにしても
よい。補間処理のプロセスは、この後、上記のように、
選択された基準フレームの間の全てのフレームについて
継続して行われる。

【００６０】図２に、Ｖ信号（図１）のフレームＩm 及
びＩp の各々のイメージ格子の、同じ表示区域から取っ
た画素例としての画素セット２０１及び２０２を示す。
これらのフレームは、ビデオ変換符号器１００によって
処理された第１及び第２フレームに対応する。フレーム
Ｉm は、ビデオ変換符号器１００によって動作補償予測
形式で符号化すべきフレームＩp よりも過去にある基準
フレームである。

【００６１】画素セット２０１の、Ｑ×Ｒ個の画素から
なる部分セット（サブセット）（「Ｑ×Ｒサブセッ
ト」）である画素ブロック２０３を、探索を行う対象の
ブロックとする。Ｑ及びＲの各々の一般的な値は１６で
ある。しかし、説明を分かりやすく且つ簡単にするた
め、図２においては、Ｑ及びＲは各々、４の値を持つも
のとして示してある。

【００６２】Ｄmax で示す探索範囲は、動作ベクトルの
候補となる変位のいずれについても、水平又は垂直のい
ずれかの方向における最大個別距離成分（一般に画素単
位で表される）である。探索範囲で定まる総探索区域
は、図形的には、影を付けた領域２０４とブロック２０
３との和、で示される。総探索区域は、ブロック２０３
に近似する候補ブロックの各画素を見いだす可能性のあ
る潜在区域を示す領域である。

【００６３】Ｘで印を付けた、前のフレーム２０２内の
位置は、ブロック２０３に最もよくマッチする可能性の
あるブロックを求める探索の対象となる、フレーム２０
２中の潜在ブロック、の中心のセットである。ブロック
２０３の中心からフレーム２０２中のＸで印を付けた位
置までの距離は、ブロック２０３についての動作ベクト
ルの候補である。

【００６４】Ｘで印を付けた、前のフレーム２０２内の
１つの中心位置によって定義される各変位について、数
式［数１］に定義されるマッチング関数が計算される。
動作ベクトルは、マッチング関数の最小値の見いだされ
るような変位ｄに対応する。これがすなわち、最良候補
変位である。

【００６５】図３に、本発明に基づき、図２の作用を２
つの基準フレームに一般化した場合を示す。図中、Ｖ信
号（図１）のフレームＩm、Ｉp、及びＩn の同じ表示区
域から、例として画素セット２０１、２０２、及び３０
１を示す。フレームＩn は、ビデオ変換符号器１００に
よって動作補間形式により符号化されようとするフレー
ムである。フレームＩm は、フレームＩn に対して過去
にある基準フレーム、又、フレームＩp は、フレームＩ
n に対して未来にある基準フレームである。

【００６６】画素セット３０１のＱ×Ｒサブセットであ
る画素ブロック３０２が、符号化されようとするブロッ
クである。動作ベクトル及び対応する重みの探索は、ブ
ロック３０２について行われる。基準フレームは一般
に、図３の画素セット２０１、２０２、及び３０１で示
すように、一方は、動作補間形式によって符号化されよ
うとするフレームＩn に対して過去にあるフレームＩm
、他方は、このフレームＩn に対して未来にあるフレ
ームＩp から構成される。

【００６７】しかし、符号化実現の際の自由裁量で、基
準フレームＩm 及びＩp の両方をフレームＩn に対して
過去にあるようにしてもよい。

【００６８】ブロック３０２について動作ベクトルと重
みとを決定するためには、フレームＩm 及びＩp の各々
における画素ブロックを向く方向を有する変位を動作推
定器１１８（図１）によって見いだし、誤差信号（Ｅ信
号）のエネルギー（Ｅエネルギー）の目安となる、その
ブロックを構成する画素値の加重合成値が最小になるよ
うにする必要がある。このような最小値は、次の数式
［数２］で表される。

【００６９】

【数２】

【００７０】ｄm 及びｄp はそれぞれ、フレームＩm 及
びＩp についての変位である。ｄm及びｄp に対する値
の候補を、図３において図式的に、ベクトル３０３及び
３０４として示す。又、Ｄm 及びＤp は、フレームＩm
及びＩp における探索範囲に対応する。Ｄm 及びＤp に
よって定義される探索範囲を、図３において図式的に、
影を付けた領域３０５及び３０６で示す。αm 及びαp
は、フレーム２０１及び２０２から結合されるそれぞれ
のブロックの各画素値に対する重みファクターである。

【００７１】本発明により、最適変位と重みとは、次に
示す数式［数４］の、αm 及びαpに関する偏導関数が
０（ゼロ）に等しいという条件を入れることによって、
決まる。

【００７２】

【数４】

【００７３】これから、２つの線形方程式を含む次の数
式［数Ａ］が導かれる。 Ｍ.ｕ ＝ ｖ ［数Ａ］

【００７４】ここにおいて、ベクトルｕ及びｖは、次の
数式［数５］及び［数６］で表され、行列Ｍは、数式
［数７］で表される。

【００７５】

【数５】

【００７６】

【数６】

【００７７】

【数７】

【００７８】行列Ｍは、ｘ、ｄm、ｄpの全ての値に対し
て有限且つ正とすることができ、これによって、ｄm、
ｄpの対について検討評価された結果として、対応する
重みの最適値、ｕ*＝αm*,αp*、が得られ、この特定の
ｄm、ｄpの対についてＥエネルギーが最小になることが
保証される。行列Ｍが特異値の場合、数式［数２］を満
足するような値αm*,αp* の無限セットが生じる。

【００７９】このような縮退例は例えば、Ｉm（ｘ）及
びＩp（ｘ）の両方でブロックについて完全なマッチン
グが存在する（誤差がない）場合に起こる。このような
縮退例については、重みの１つについての最適値と、残
りの重みについての最適値とが、数式［数Ａ］で表され
る２つの線形方程式のいずれかを解くことによって得ら
るため、任意の値を選ぶことができる。非縮退例におい
ては、重みｕ* のセットについての最適解は、次の数式
［数８］で与えられる。 ｕ* ＝ Ｍ-1.ｖ ［数８］

【００８０】実際値と入れ替える前においては、理想的
な重みｕ* は、変位ｄm、ｄpの対に依存する関数であ
る。したがって、最適解では、本発明に基づき、数式
［数Ａ］を満足し且つＥエネルギーを最小にするような
ｄm、ｄpの対を選択することを要する。

【００８１】このような最適のｄm、ｄpの対を見いだす
には、本発明に基づき、候補変位の対（変位対）のセッ
トの中から探索する必要がある。一般に、探索範囲内に
ある変位対は全て、候補変位対のセットに含まれる。候
補変位対のセットの各メンバーについて、数式［数８］
から特定のｕ* 値が得られるように、行列Ｍ、Ｍ-1とベ
クトルｖとが検討評価される。

【００８２】それから、本発明に基づき、Ｅエネルギー
の計算用に、ｕ*、 及び対応する変位ｄm、ｄpの値が用
いられる。もし或る特定の変位対について、探索中に既
に検討評価された他の変位対よりも小さいＥエネルギー
値が導き出された場合には、この特定変位対のｎ項組
（αm*、αp*、ｄm、ｄp）が記憶される。記憶されたｎ
項組のＥエネルギーも記憶され、これによって、以後に
続く各ｎ項組のエネルギーが検討評価される際に、記憶
されているｎ項組のＥエネルギーとの比較を迅速に行う
ことができる。

【００８３】全ての候補変位対が検討評価され終ったと
きにまだ残存しているｎ項組は、すなわち、符号化され
る画素ブロックについての最適重み及び変位である。こ
れらは、本発明に基づき、画素ブロック３０２について
の重み及び動作ベクトルとして動作推定器１８（図１）
によって供給される。尚、本発明の範囲に影響を与える
ことなく、Ｅエネルギーの代わりに、総合誤差信号を表
す別の尺度すなわち表示方式を用いることができること
は、当業者に明かである。このような代替表示の１つと
して、絶対値形式の関数がある。

【００８４】本発明を実現する際の自由裁量で、且つ本
発明に基づき、種々の方法を用いて探索プロセスを簡略
化且つ加速化、又は単に加速化することができる。本発
明によるこのような方法の１つは、誤差信号エネルギー
（Ｅエネルギー）が所定のしきい値Ｔより下がった場合
に、探索プロセスを中断して特定のｄm、ｄpを利用する
方法である。

【００８５】この方法は、絶対的最小値ではないかも知
れないが最小値として条件を満足する程度に小さなＥエ
ネルギーを見出そうとするもので、これによって、検討
を要する候補変位ｄm、ｄp対の数に限度を設けることが
できる。これは、一旦Ｅエネルギーについて条件を満足
する程度に小さな値が得られると、残りの候補変位ｄ
m、ｄpの対を検討する必要がなくなるからである。

【００８６】しきい値を用いた探索においてしきい値を
満足する変位対を見いだす速度は、候補変位対を検討評
価する順序を制御することによって更に増大させること
ができる。又、どの変位対を候補変位対セットのメンバ
ーにするかの選択を制御することによっても、検討評価
すべき候補変位対の数を制限できる。候補変位対を候補
変位対のセットに加えるか又はセットから削除するか
は、前に行った候補変位対検討評価結果に基づく。変位
対選択の制御を、しきい値基準と組み合わせることもで
きる。

【００８７】最適重み及び変位を探索するプロセスにお
いて、候補変位対のセットに対して加除する候補変位
対、を制御して最適重み及び変位の探索プロセスを短縮
する方法の一例は、Ｅエネルギーが、変位が最小ひずみ
の方向から外れるに従い、単調に減少する事実に基づい
ている。図４に、フレームＩm、Ｉp、及びＩn と同じ区
域から取った画素セット２０１、２０２、及び３０１
を、画素セット例として示す。

【００８８】画素ブロック４０１は、補間すべきフレー
ムＩn の格子に位置する、現対象画素ブロックである。
図４に関連して、例えば次に例示する一連の過程によっ
て、本発明に基づき動作ベクトルとして用いられる条件
を満足する変位対の探索を行う。各変位は、ｘが指す座
標原点に対する位置として定義される。本例では、座標
原点４０２を、ブロック４０１の中心にある十字で示
す。

【００８９】ゼロ変位（０，０）、及びｘ、例えばブロ
ック４０１の中心、から総探索区域の距離の約１／４だ
け離れたほぼ等距離の位置にあるフレームＩm及びＩpの
各々の中の所定の位置によって定義される変位に対応す
る全ての変位が、最初の候補変位セットとして選択され
る。

【００９０】例えば、画素セット２０１及び２０２の各
々においては、ゼロ変位４０３が選択される。又、ブロ
ック中心４０１の周囲の、構成要素に関する最大変位Ｄ
m 及びＤp のそれぞれ１／２よりも小さい最大整数、例
えばＤm ＝Ｄp＝７ に対して３、だけブロック中心４０
１から離れた位置として定義される８個の位置も選択さ
れる。選択された位置４０４のセットの各メンバーを図
４に少なくとも１つのＸで示す。

【００９１】その後、フレームＩm 内の位置によって定
義される１つの変位とフレームＩp内の位置によって定
義される１つの変位とを有する、選択された全ての変位
の対としての組合せからなる変位対のセットが決定され
る。本例では、この対セットのメンバーは、８１個の候
補変位から構成されることになる。

【００９２】この対セットの各候補変位対について、Ｅ
最小エネルギーが計算される。Ｅエネルギーが最小とな
る変位対を、ｄm(0)及びｄp(0)と名付ける。この選択さ
れた変位対は、フレームＩm 中の位置によって定義され
る１つの変位とフレームＩp中の位置によって定義され
る１つの変位とを有する。本例においてｄm(0)及びｄp
(0)を定める位置４０５の対を、画素セット２０１及び
２０２の各々中に、Ｘと、中を黒く塗りつぶした正方形
との両方のマークで示す。

【００９３】次に、候補変位セットから、削除されたメ
ンバーが取り除かれる。そして、位置４０５によって定
義される変位、すなわちｄm(0)及びｄp(0)、及び位置４
０５のセットの各位置から総探索区域の距離の約１／８
だけ離れたほぼ等距離の位置にあるフレームＩm及びＩp
の各々の中の所定の位置によって定義される変位が、新
たな候補変位セットとして選択される。

【００９４】例えば、画素セット２０１及び２０２の各
々において、ｄm(0)及びｄp(0)と、位置４０５の周囲
の、構成要素に関する最大変位Ｄm及びＤpのそれぞれ１
／４よりも小さい最大整数、例えばＤm ＝Ｄp＝７ に対
して２、だけ位置４０５から離れた位置として定義され
る８個の位置とが選択される。選択された位置４０６の
全セットを図４に、少なくとも１つの、中を黒く塗りつ
ぶした正方形のマークで示す。

【００９５】その後、フレームＩm 内の位置によって定
義される１つの変位とフレームＩp中の位置によって定
義される１つの変位とを有する、このように選択された
全ての変位の対としての組合せからなる第２の変位対セ
ットが決定される。本例では、この第２の対セットのメ
ンバーは、８１個の候補変位から構成される。

【００９６】この第２の変位対セットの各候補変位対に
ついて、最小Ｅエネルギーが計算される。Ｅエネルギー
が最小となる変位対を、ｄm(1)及びｄp(1)と名付ける。
このようにして選択された変位対は、フレームＩm 内の
位置によって定義される１つの変位とフレームＩp 内の
位置によって定義される１つの変位とを有する。本例に
おいて、ｄm(1)及びｄp(1)を定める点は位置４０７のセ
ットで、その位置を画素セット２０１及び２０２の各々
中に、中を黒く塗りつぶした正方形と、円との両方のマ
ークで示す。

【００９７】最後に、候補変位セットから、削除された
メンバーが再び取り除かれる。そして、位置４０７によ
って定義される変位、すなわちｄm(1)及びｄp(1)、及び
位置４０７のセットの各位置から総探索区域の距離の約
１／１６だけ離れたほぼ等距離の位置にあるフレームＩ
m及びＩpの各々の中の所定の位置によって定義される変
位が、最後の候補変位セットとして選択される。

【００９８】例えば、画素セット２０１及び２０２の各
々において、ｄm(1)及びｄp(1)と、位置４０７の周囲
の、構成要素に関する最大変位ｄm(1)及びｄp(1)のそれ
ぞれ１／８よりも小さい最大整数、例えばＤm ＝Ｄp＝
７ に対して１、だけ位置４０７から離れた位置として
定義される８個の位置とが選択される。選択された位置
４０８の各々を図４に少なくとも１つの円で示す。

【００９９】その後、フレームＩm 内の位置によって定
義される１つの変位とフレームＩp内の位置によって定
義される１つの変位とを有する、このように選択された
全ての変位の対としての組合せからなる第３の変位対セ
ットが決定される。本例では前と同様に、この第３の対
セットのメンバーは、８１個の候補変位から構成される
ことになる。

【０１００】この第３の対セットの各候補変位対につい
て、最小Ｅエネルギーが計算される。Ｅエネルギーが最
小となる変位対を、ｄm(2)及びｄp(2)と名付ける。この
選択された変位対は、フレームＩm 内の位置によって定
義される１つの変位とフレームＩp 内の位置によって定
義される１つの変位とを有する。

【０１０１】本例において、ｄm(2)及びｄp(2)を定める
点は位置４０９のセットで、その位置を画素セット２０
１及び２０２の各々の中に、中を黒く塗りつぶした円で
示す。この、フレームＩm 内の位置によって定義される
１つの変位とフレームＩp 内の位置によって定義される
１つの変位とを有する、選択された変位対が、画素ブロ
ック４０２についての動作ベクトルとして選択される。

【０１０２】更に、本発明に基づき、Ｅエネルギーが所
定のしきい値Ｔに等しく又はより小さくなった場合に、
この、動作ベクトルとして使用する変位対の探求プロセ
スを終結させるように決めてもよい。この場合、Ｔより
小さいＥエネルギーに最初に到達した変位対を動作ベク
トルとして選択する。尚、選ばれたブロックの大きさ及
び実現に際して条件とされる誤差限界によっては、更に
追加して探索過程を続行することはもちろん可能であ
り、これは当業者にも明らかである。

【０１０３】動作ベクトルの対とこれらに対応する重み
とを見いだす探索プロセスにおいて、これら動作ベクト
ルの対と重みとを見いだす際に検討する必要のある候補
変位対の数を減らしてプロセスを短縮するための方法の
別の例においては、本発明に基づき、候補変位セットの
メンバーである変位対を設定するのに、空間的に近隣に
ある画素ブロックと個々の画素とに関する情報を用い
る。

【０１０４】この設定方策は、或るフレームの或る特定
の区域の画素ブロックは全て、移動中の単一体の一部に
なりそうである、という概して正しい主張に基づく。し
たがって、その単一体を構成するブロックは全て、フレ
ームからフレームへほぼ均一な仕方で移動するものと初
めに想定する。図５に、ビデオ変換符号器１００（図
１）によって符号化すべきフレームＩn の一部が、制御
・フレーム再構成ユニット１０１によって画素ブロック
に分割された状態を示す。

【０１０５】画素ブロック５０１及び５０２は、ｘ(00)
に位置して現在符号化されようとしている画素ブロック
５０３の左側及び上側にそれぞれ位置するフレームＩn
内の位置ｘ(01)及びｘ(10)に位置する。画素ブロック５
０１及び５０２についての変位対すなわち動作ベクトル
の最適セットを、Ａ＝（ｄm(01)，ｄp(01)）及びＢ＝
（ｄm(10)，ｄp(10)）とそれぞれ名付ける。

【０１０６】自然場面の一連のイメージについては動作
の場が円滑であるとの想定に基づいて、画素ブロック５
０３に対する変位対を、最初の変位対Ａ又はＢのいずれ
かから選択し、Ｃ＝（ｄm(00)，ｄp(00)）と名付ける。
Ａ又はＢのいずれの最初の変位対を選択してＣとするか
の選択においては、いずれの変位対においてＥエネルギ
ーが最小になるかを判断し、そのように判断された変位
対をＣとする。

【０１０７】このようにして動作ベクトルとされた変位
対が表す画素ブロック５０３の動作の推定は、候補変位
対について追加探索することで更に改善される。この場
合、しきい値方式による探索方法を用い、基準フレーム
Ｉm及びＩpの各々に１つの変位を有するような、探索範
囲内にある全ての候補変位を走査し、選択された動作ベ
クトルが、Ｃの値に近接する変位値に対するＥエネルギ
ー最小値を有するような変位対を探索する。

【０１０８】動作ベクトルの対とこれらに対応する重み
とを見いだす探索プロセスを短縮するための方法の更に
別の例は、基準フレームＩm及びＩpの間で動作ベクトル
を探索する対象フレームを一方から他方へ交互に切り換
える、すなわちｄm が固定のときはｄp を変え、又はそ
の逆とする方法である。この方法は、ピンポン探索とい
われている。初めに固定することにした基準フレーム
は、動作補間符号化すべきフレームＩn に時間的に最も
近い。その理由は、このフレームの近隣ブロックについ
ての最初の推定に、より信頼がおけるからである。

【０１０９】走査には、２つの走査順序のうちの１つを
用いる。説明を分かりやすくするために、Ｃとして選択
された最初の変位をｄm,0 、及びｄp,0 と呼び替えるこ
とにする。すなわち、ｄm,0＝ｄm(00)及びｄp,0＝ｄp(0
0)となる。

【０１１０】図６に、ピンポン探索を構成する、例えば
ｗ個のステージのうちの、第１番目、第２番目、及び第
ｗ番目のステージにおける画素ブロック６０１及び６０
２を示す。ここに、ｗはブロックごとに異なる変数であ
る。フレームＩm 内にある画素ブロック６０１及びフレ
ームＩp 内にある画素ブロック６０２は、位置的にフレ
ームＩn の画素５０３に対応する。変位対６０３が最初
にＣとされる。説明を簡単にするために、ｄp が最初に
固定であると仮定する。

【０１１１】ｄp,0 と組み合わされて対を成す変位ｄm
の全ての値が、ｄm,0 の周りに円形状に走査される。図
６に示す探索例において候補変位が選択される順序を、
ｄmの有する各々の値に対応する各点に属する数値で示
す。反時計廻り又は時計廻りのいずれの向きを取るかは
任意に決める。

【０１１２】誤差信号エネルギー（Ｅエネルギー）が所
定のしきい値Ｔより小さくなり次第、探索プロセスは停
止され、現候補変位ｄm 及びｄp が動作ブロックとして
採用される。Ｅエネルギーがしきい値Ｔより小さくなら
ないでｄm の全ての値の走査が済んだ場合は、Ｅエネル
ギーの最小値につながるｄm がフレームＩn 内において
固定され、ｄm,1 と名付けられる。

【０１１３】次に、フレームＩp 内の変位ｄp につい
て、ｄp,1 の廻りに同様な円形状に走査が継続される。
このピンポン探索手順が、Ｅエネルギーがしきい値Ｔよ
り小さくなるか、又は減少しなくなるまで繰り返され
る。フレームＩn とフレームＩpとの間の切換が行われ
るにしたがってＥエネルギーは単調に減少し、探索は確
実に集束する。

【０１１４】探索を更に加速するため、ｄp,j と組み合
わされて対を成す変位ｄm の全ての値及びｄm,j と組み
合わされて対を成す変位ｄp の全ての値について探索を
行う代わりに、フレームＩn 及びフレームＩp の各々の
探索範囲内にある選ばれた変位サブセットのみが探索を
受けるようにする。ここで指標ｊは、フレームＩn 及び
フレームＩp の各々が探索プロセスにかけられる回数を
意味する。サブセットは、変位が固定されていない方の
フレームの現変位に位置的に近接している変位から構成
されるように選ぶ。

【０１１５】例えば、ｄp,j が固定のときにｄm,j 最も
近接している８個の近隣ブロック及びｄm,j 自身だけを
走査することに決めた場合には、上記と同様なピンポン
方式でフレームＩp に進む際に、これら９個の変位対以
上にＥエネルギーを最小化させるｄm （ｄm,j+1 と呼
ぶ）の値が、一定値に保たれる。

【０１１６】ここで、周知の共役方向探索方式を本発明
に基づいて拡張し、候補変位探索を加速する方法の１つ
として用いることとする。この拡張とはすなわち、動作
ベクトルを見いだす際に候補変位セットのメンバーにつ
いて探索を行う順序を定めることである。この場合の説
明上、探索範囲内の変位対はすべて、候補変位対のセッ
トに含まれるものとする。図７、図８及び図９に、拡張
された共役方向探索方式の実現例を順次連続する、分割
された３つの流れ図で示す。

【０１１７】プロセスの手順は、動作補間器１２９（図
１）によって実行され、或るブロックについて、動作ベ
クトルとして用いられる変位セットが必要な場合に、ス
テップ８０１（図７）の入口から開始される。ステップ
８０２において、現最小Ｅエネルギー（Ｓmin） を無限
大として初期化する。

【０１１８】次にステップ８０３において、第１の基準
フレーム、本例ではフレーム Ｉm、に関する変位が、上
に定義されたＣとして選択された最初の変位と同じ行成
分値（行値）を有し、列成分値（列値）については、探
索範囲Ｄmax によって定義される際左端の列変位に合わ
せた値を有するものと定義する。説明上、Ｄm＝Ｄp＝Ｄ
max とし、Ｄmax は、行成分Ｄmax,x と列成分Ｄmax,y
とを有するものとする。更に、行のフラッグである 「m
x-flag」が１に設定される。

【０１１９】同様にステップ８０４において、第２の基
準フレーム、本例ではフレーム Ｉp、に関する変位が、
上に定義されたＣとして選択された最初の変位、と同じ
行値を有し、列値については、探索範囲Ｄmax によって
定義される際左端の列変位に合わせて設定されるものと
定義する。又、行のフラッグである 「px-flag」が１に
設定される。

【０１２０】尚、最右端の方向と最左端の方向とは、本
探索の目的上、均等に置き換えが可能である。同様に、
最上端の方向と最下端の方向とは、本探索の目的上、均
等に置き換えが可能である。更に、行と列の順序も、本
探索の目的上、均等に置き換えが可能である。本例にお
ける方向は、単に説明上の便利さから選んだものであ
る。その後、ステップ８０５において、現変位値の対に
ついてＥエネルギーが計算され、Ｓと名付けられる。

【０１２１】次に、条件付き分岐点ステップ８０６にお
いて、ＳがＳmin より小さいかどうかが点検される。も
しステップ８０６における点検結果がＹＥＳの場合、プ
ロセスはステップ８０７に進み、そこで次に示す値の設
定が行われる。

【０１２２】すなわち、Ｓmin が変更されたことを示す
フラッグである「変更-min」フラッグが１に、フレーム
Ｉm における変位の現推定値を含む変数であるｄm,min
がｄm に、フレームＩp における変位の現推定値を含む
変数であるｄp,min がｄp に、それぞれ設定される。そ
して、Ｓmin がＳの現在値に合わせて設定される。プロ
セスはそれから条件付き分岐点ステップ８０８（図８）
に進む。

【０１２３】もしステップ８０６における点検結果がＮ
Ｏの場合、プロセスは直接にステップ８０８に進む。条
件付き分岐点ステップ８０８においては、 「px-flag」
が１に設定されているかどうかが点検される。もしステ
ップ８０８における点検結果がＮＯの場合、プロセスは
条件付き分岐点ステップ８０９に進み、そこでｄp,xが
最下端行値Ｄmax,x に等しいかどうかが点検される。

【０１２４】もしステップ８０９における点検結果がＮ
Ｏの場合、プロセスはステップ８１０に進み、そこで変
位ｄp の行値が１だけ増大される。プロセスはそれから
条件付き分岐点ステップ８０５（図７）に移り、ここで
Ｓの新たな値が定められ、更に点検される。もしステッ
プ８０９における点検結果がＹＥＳの場合、プロセスは
条件付き分岐点ステップ８１１に進み、そこで「変更-m
in」フラッグが１に設定されているかどうかが点検され
る。

【０１２５】もしステップ８１１における点検結果がＹ
ＥＳの場合、プロセスはステップ８１２に進み、そこ
で、新たなｄp 推定値が、最小Ｅエネルギー値と最左端
列変位とを有することが判明した行変位、に合わせて設
定される。更に、「変更-min」フラッグが０（ゼロ）
に、「px-flag」 が１に、それぞれ設定され、プロセス
はステップ８０５（図７）に戻る。

【０１２６】もし条件付き分岐点ステップ８０８におけ
る点検結果がＹＥＳの場合には、プロセスは条件付き分
岐点ステップ８１３に進み、そこでｄp,y が最右端列変
位値Ｄmax,y に等しいかどうかが点検される。もしステ
ップ８１３における点検結果がＮＯの場合、プロセスは
ステップ８１４に進み、そこで変位ｄp の列値が１だけ
増大される。プロセスはそれから条件付き分岐点ステッ
プ８０５（図７）に移り、ここでＳの新たな値が定めら
れ点検される。

【０１２７】もしステップ８１３における点検結果がＹ
ＥＳの場合、プロセスは条件付き分岐点ステップ８１５
に進み、そこで「変更-min」フラッグが１に設定されて
いるかどうかが点検される。もしステップ８１５におけ
る点検結果がＹＥＳの場合、プロセスはステップ８１６
に進み、そこで、新たなｄp 推定値が、最小Ｅエネルギ
ー値と最上端行変位とを有することが判明した列変位、
に合わせて設定される。更に、「変更-min」フラッグが
０（ゼロ）に、「px-flag」 が０（ゼロ）に、それぞれ
設定され、プロセスはステップ８０５（図７）に戻る。

【０１２８】もしステップ８１１又は８１５における点
検結果がＮＯの場合、プロセスは条件付き分岐点ステッ
プ８１７（図９）に進み、そこで 「mx-flag」フラッグ
が１に設定されているかどうかが点検される。もしステ
ップ８１７における点検結果がＮＯの場合、プロセスは
条件付き分岐点ステップ８１８に進み、そこでｄm,xが
最下端行値Ｄmax,x に等しいかどうかが点検される。

【０１２９】もしステップ８１８における点検結果がＮ
Ｏの場合、プロセスはステップ８１９に進み、そこで変
位ｄm の行値が１だけ増大される。プロセスはそれから
条件付き分岐点ステップ８０５（図７）に移り、ここで
Ｓの新たな値が定められ、更に点検される。もしステッ
プ８１８における点検結果がＹＥＳの場合、プロセスは
条件付き分岐点ステップ８２０に進み、そこで「変更-m
in」フラッグが１に設定されているかどうかが点検され
る。

【０１３０】もしステップ８２０における点検結果がＹ
ＥＳの場合、プロセスはステップ８２１に進み、そこ
で、新たなｄm 推定値が、最小Ｅエネルギー値と最左端
列変位とを有することが判明した行変位、に合わせて設
定される。又、「変更-min」フラッグが０（ゼロ）に、
「mx-flag」 が１に、それぞれ設定され、プロセスはス
テップ８０５（図７）に戻る。

【０１３１】もしステップ８１７における点検結果がＹ
ＥＳの場合、プロセスは条件付き分岐点ステップ８２２
に進み、そこでｄm,y が最右端列変位値Ｄmax,y に等し
いかどうかが点検される。

【０１３２】もしステップ８２２における点検結果がＮ
Ｏの場合、プロセスはステップ８２３に進み、そこで変
位ｄm の列値が１だけ増大される。プロセスはそれから
条件付き分岐点ステップ８０５（図７）に移り、ここで
Ｓの新たな値が定められ、更に点検される。もしステッ
プ８２２における点検結果がＹＥＳの場合、プロセスは
条件付き分岐点ステップ８２４に進み、そこで「変更-m
in」フラッグが１に設定されているかどうかが点検され
る。

【０１３３】もしステップ８２４における点検結果がＹ
ＥＳの場合、プロセスはステップ８２５に進み、そこ
で、新たなｄm 推定値が、最小Ｅエネルギー値と最上端
行変位とを有することが判明した列変位、に合わせて設
定される。又、「変更-min」フラッグが０（ゼロ）に、
「mx-flag」 が０（ゼロ）に、それぞれ設定され、プロ
セスはステップ８０５（図７）に戻る。もしステップ８
２０又は８２４における点検結果がＮＯの場合、変位ｄ
m,min 及びｄp,min の現在の値がステップ８２６を経て
返される。その後、プロセス手順はステップ８２７で出
口に至り、終結する。

【０１３４】代わりの方法として、限られた数、例えば
３又は５個の変位セットを、各フレームについてそれぞ
れ、［２｜Ｄm｜＋１］2、及び［２｜Ｄp｜＋１］2では
なく、各々の方向において比較してもよい。

【０１３５】実際には、補間されたフレームＩn に現存
する対象物は基準フレームＩm 又はＩp の少なくとも一
方に常に存在する。したがって、（αm，αp）の分布
は、次の数式［数９］を満足するような分布である。

【０１３６】 αm＋αp ＝ １ ［数９］

【０１３７】上記数式［数２］の方程式の最適解は、次
の数式［数１０］で表すことができる。

【０１３８】

【数１０】

【０１３９】同様に、或るビデオ場面において、たいて
いの対象物は一定の速度で動くので、フレームＩn 内に
ある対象物についての基準がフレームＩm 及びＩp の両
方にある限り、次の数式［数１１］で表される制限を課
すことができる。 ｄm ＝ （ｎ−ｍ）／（ｎ−ｐ）ｄp ［数１１］ ここにおいて、ｍ，ｎ及びｐは、過去の基準フレーム、
符号化すべきフレーム、及び未来の基準フレームのそれ
ぞれのフレーム番号である。

【０１４０】この場合、検討対象とすべき変位対の数は
（［２｜Ｄm｜＋１］2 ［２｜Ｄp｜＋１］2）から［２
ｍａｘ（｜Ｄm｜，｜Ｄp｜）＋１］2に減少する。但
し、画素以下の細かさの精度は必要とされないものと仮
定する。

【０１４１】任意の変位対ｄm、ｄpについて、これらの
変位がどの様に導き出された場合でも、この対に対して
最小Ｅエネルギーをもたらす重み対αm、αpは、数式
［数８］を解くことによって得られる。

【０１４２】条件を満足する程度に小さなＥエネルギー
を持ったｎ項組 （αm*、αp*、ｄm、ｄp） が一旦決ま
った後は、重みαm*、αp*、を量子化して、それらの伝
送に要する帯域幅を制限することが望ましい。又通常、
或る重み対、αm*、αp*が、異なる対、αm(q)、αp(q)
へと量子化される場合に発生するＥエネルギーの増加を
最小にすることが好ましい。量子化によるＥエネルギー
の、許容増加量に限度を設けることによって、適切なス
テップの大きさが選べる。

【０１４３】重みの値をそれぞれ△αm及び△αpだけ変
化させた場合に、Ｅエネルギーの表示内容を微分解析し
て得られるＥエネルギーの増加量△は、次の数式［数１
２］で与えられる。 △ ＝ ｍ11（△αm）2＋ｍ22（△αp）2＋２ｍ12（△α
m）（△αp）［数１２］ここに、ｍ11及びｍ22は、行列
Ｍの対角要素、ｍ12は、行列Ｍの非対角要素である。

【０１４４】尚、ここで重要なのは、数式［数１２］に
はフレームＩn から取った値が含まれていないことであ
る。このことから、量子化によるＥエネルギー増加量に
ついての許容最大値△max が判っている限り、復号器
が、フレームＩm 及びＩp の再構築フレームから直接に
αm及びαpについての量子化ステップの大きさを確実に
推定できる。

【０１４５】非縮退例（｜Ｍ｜≠０）においては、αm
及びαpについての量子化ステップの大きさとして、Ｅ
エネルギーの増加量△をしきい値△max 以下に維持する
ような大きさを選ぶことが可能である。それには、上記
数式［数１２］において△αm及び△αp を解けばよ
い。結果として得られる量子化ステップの大きさは、次
に示す数式［数１３］及び数式［数１４］によってそれ
ぞれ与えられる△αm 及び△αp の値以下に維持されな
ければならない。 △αm ＝ （ｍ22／ｍ11）× △αp ［数１３］ △αp ＝ （ｍ11△max／｜Ｍ｜）1/2 ［数１４］

【０１４６】数式［数９］の制約が課される場合、△α
m についての量子化ステップの大きさの最大値は、次の
数式［数１５］で与えられる。 △α ＝ （△max／（ｍ11＋ｍ22−２ｍ12））1/2 ［数１５］

【０１４７】尚ここで、重み値に数式［数９］の制約を
課すことによって、Ｅエネルギーの値がαm 及びαp の
量子化ステップの大きさに左右される度合、がきわめて
小さくなることが実験的に観察された。この数式［数
９］の制約を課さない場合には、ｍ11又はｍ22の値が大
きいことから、△αm 及び△αp について、より大きな
量子化ステップが必要となる。

【０１４８】図１０に、本発明に基づき、符号化すべき
画素ブロックについての動作ベクトルと重みとを生成す
るために動作推定器１１８（図１）が行う過程の簡単な
組合せを流れ図で示す。プロセスの手順は、動作ベクト
ルと重みとを生成すべきと判断されたときに、ステップ
１００１から開始される。その後、ステップ１００３に
おいて、誤差信号エネルギー（Ｅエネルギー）について
の現在の記憶値 （Ｅs）を無限大として初期化する。ス
テップ１００５においては、各基準フレームについて、
候補変位が決定される。

【０１４９】次にステップ１００７において、候補変位
が、ｄmとｄpとからなるグループからなるセットの形に
グループ分けされる。次の処理対象となるｄm、ｄpグル
ープは、ステップ１００９において、この候補変位のグ
ループセットの中から得られる。ステップ１０１１にお
いて、そのｄm、ｄpグループについて、Ｍ、Ｍ-1、及び
ベクトルｖが検討評価される。

【０１５０】次のステップ１０１３において、本発明に
基づき、ｕ*＝Ｍ-1.ｖ が導き出される。ステップ１０
１５では、 αm*、αp*、ｄm及びｄp についてのＥエネ
ルギー（Ｅe） が計算される。その後、条件付き分岐点
ステップ１０１７において、Ｅe がＥs より大きいかど
うかが点検される。もしステップ１０１７の結果がＮＯ
なら、プロセスはステップ１０１９に進み、そこでαm
*、αp*、ｄm及びｄpが記憶され、Ｅs が、現在のＥe
に等しく設定された後、次のステップ１０２１に進む。

【０１５１】もしステップ１０１７の結果がＹＥＳな
ら、プロセスは直接、ステップ１０２１に進む。ステッ
プ１０２１は条件付き分岐点で、ここでＥs がしきい値
Ｔと等しい又はより小さい状態にあるかどうかが点検さ
れる。

【０１５２】もしステップ１０２１の結果がＮＯなら、
プロセスはステップ１０２３に進み、そこでｄm、ｄpグ
ループが再調整される。この再調整は、ステップ１００
９におけるグループの選択順序の再構成であり、セット
へのグループ追加又はセットからのグループ削除のうち
いずれか効率的な探索に必要な操作である。この後、プ
ロセスはステップ１０２７に進む。

【０１５３】もしステップ１０２１の結果がＹＥＳな
ら、プロセスはステップ１０２５に進み、ここで、残存
するｄm、ｄpグループがすべて削除され、処理すべきグ
ループが後に残らない状態となる。ステップ１０２７は
条件付き分岐点で、ここでグループセット中に処理を要
するｄm、ｄpグループがまだ残っているかどうかが点検
される。もしステップ１０２７の結果がＹＥＳなら、プ
ロセスはステップ１００９に戻り、処理すべきグループ
が求められる。

【０１５４】もしステップ１０２７の結果がＮＯなら、
プロセスはステップ１０２９に進み、必要ならオプショ
ンの量子化操作が行われる。この量子化は、実際には量
子化器１３１（図１）によって行われる。その後、プロ
セスは出口のステップ１０３１に至り、終結する。αm
*、αp*、ｄm、ｄpの最終記憶値は、動作ベクトルと、
これに対応するオプションの重みとして供給される。

【０１５５】以上の説明は、本発明の一実施例に関する
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。

【０１５６】尚、特許請求の範囲に記載した参照番号は
発明の容易な理解のためで、その技術的範囲を制限する
よう解釈されるべきではない。

【０１５７】

【発明の効果】以上述べたごとく、本発明によれば、ビ
デオイメージフレームにおける画素ブロックのデータの
圧縮符号化において動作ベクトルを構成する最適候補変
位対及びこれに対応する重み対を選択する際の誤差最小
化プロセスで、所定の探索範囲内の全ての候補変位対及
び重み対について検討評価を行う代わりに、例えば誤差
信号エネルギーが所定のしきい値より下がったときにほ
ぼ最小値に達したものとみなして探索を終了するように
して、プロセスの簡略化、加速化を計るいるので、従来
技術による方法装置よりも効率よくデータの圧縮符号化
を行うことができる。

【図面の簡単な説明】

【図１】本発明の実施例としてのビデオ変換符号器の簡
略ブロック図である。

【図２】２つのフレーム間での画素ブロックマッチング
探索プロセスの局面を示す説明図である。

【図３】２つの基準フレームを用いた符号化システムに
生じる加重平均プロセスの説明図である。

【図４】２つの基準フレームを用いた場合に採用可能な
３段探索方式の局面を示す説明図である。

【図５】画素ブロックに分割されたフレームＩn の一部
分を示す説明図である。

【図６】順次に走査（スキャニング）を行うようにし
た、しきい値探索方式を示す説明図である。

【図７】図８及び図９と一体に連結された、本発明に基
づき、２つの基準フレームを用いた場合用に拡張された
共役方向探索方式、を示す流れ図の一部である。

【図８】図７及び図９と一体に連結して、本発明に基づ
き、２つの基準フレームを用いた場合用に拡張された共
役方向探索方式、を示す流れ図の一部である。

【図９】図７及び図８と一体に連結して、本発明に基づ
き、２つの基準フレームを用いた場合用に拡張された共
役方向探索方式、を示す流れ図の一部である。

【図１０】本発明による、符号化すべき画素ブロックに
対する動作ベクトルと重みとを生成するための動作推定
の際に必要な過程の組合せを簡単に示す流れ図である。

【符号の説明】

１００ ビデオ変換符号器 １０１ 制御・フレーム再構成ユニット １０２ 第１制御バス １０３〜１１０、１１３、１１４ スイッチ素子 １１１ ブロック形式ユニット １１２ 減算器 １１５ 第２制御バス １１６、１２１、１２２ 可変長符号器（ＶＬＣ） １１７ 多重化・バッファユニット １１８ 動作推定器 １１９ 離散コサイン変換ユニット（ＤＣＴ） １２０ 量子化器 １２３ 逆量子化器 １２４ 逆離散変換ユニット（ＩＤＣＴ） １２５ フレームバッファ（Ｆ１） １２６ 加算器 １２７ ゼロブロック源 １２８ 動作補償器 １２９ 動作補間器 １３０ フレームバッファ（Ｆ２） １３１ 量子化器（オプション） ２０１、２０２、 ２０３ 画素セット ２０４ 影を付けた領域 ３０１、３０２ 画素セット（ブロック） ３０３、３０４ フレームについての変位を表すベクト
ル ４０１ 画素セット（ブロック） ４０２ 座標原点 ４０３ ゼロ変位 ４０４ 第１の候補変位を定義する位置として選択され
た位置 ４０５ 誤差信号（Ｅ）のエネルギー（Ｅエネルギー）
が最小となるような変位対ｄm(0)及びｄp(0)を定める位
置 ４０６ 第２の候補変位を定義する位置として選択され
た位置 ４０７ Ｅエネルギーが最小となる変位対ｄm(1)及びｄ
p(1)を定める位置 ４０８ 第３の候補変位を定義する位置として選択され
た位置 ４０９ Ｅエネルギーが最小となる変位対ｄm(2)及びｄ
p(2)を定める位置 ５０１、５０２、５０３、６０１、６０２ 画素ブロッ
ク Ｉm 過去フレーム Ｉp 未来フレーム Ｉn 符号化すべき現フレーム ＢＩＴ信号 ＶＩＤＩＮ信号のフレームを表す符号化さ
れたディジタルデータ信号（ＢＩＴＳＴＲＥＡＭ信号） ＢＬＫ信号 順序再設定された画素ブロック信号（ＢＬ
ＯＣＫＳ信号） Ｅ信号 ブロックの動作補償予測符号化又は動作予測補
間符号化による再構築バージョンの実際のブロックに関
しての誤差を表す信号（誤差信号） Ｖ信号 ディジタル形式で表される、一連のイメージフ
レーム

【数３】

───────────────────────────────────────────────────── フロントページの続き (72)発明者 リカルド レオナルディ スイス ジュネ−ヴ シィ−エイチ−1204 ９ ル− エティエンヌ デュモン

Claims (15)

【特許請求の範囲】
1. 【請求項１】 各フレームが少なくとも１つのイメージ
   表示子を有するような複数のフレームから構成される印
   加ビデオ信号の或るフレーム内の所定の位置にある符号
   化すべき画素ブロックに関して、前記ビデオ信号の前記
   複数のフレームのうち基準フレームに指定され複数の画
   素ブロックに分割される少なくとも２つのフレームか
   ら、変位及び対応する重みを表す信号のセットを発生さ
   せることによって、前記符号化すべき画素ブロックにつ
   いての符号化信号を発生させるためのビデオイメージ処
   理における符号化信号の発生方法において、 ａ．前記基準フレームをメモリに記憶させる過程と、 ｂ．所定の選択基準に応じて、前記基準フレームの各々
   について前記符号化すべき画素ブロックの前記位置から
   計測され且つそのベクトルの大きさが所定の最大変位の
   ベクトルの大きさ以下の候補変位を選択する過程と、 ｃ．前記選択された候補変位から、その候補変位グルー
   プのセットの各グループが前記基準フレームの各々から
   の候補変位をそれぞれ１つずつ有するような候補変位グ
   ループのセットを抜粋する過程と、 ｄ．前記候補変位グループのセットの前記グループを、
   所定の順位付け基準に応じて順位付けする過程と、 ｅ．前記候補変位グループの各々に、１つの候補重みが
   前記候補変位グループの１つのメンバーにそれぞれ対応
   するように、前記候補変位グループについての最良候補
   重みのセットを割り当てる過程と、 ｆ．前記候補変位グループの各々について、前記符号化
   される画素ブロックの画素値と、符号化される前記画素
   ブロックの前記位置から前記候補変位の前記グループ内
   の前記候補変位のうちの対応する候補変位だけ変位され
   る前記基準フレームの前記画素ブロックの画素値の加重
   和であって前記記憶された基準フレームの前記画素ブロ
   ックの前記画素値のうちの対応する値に前記候補変位グ
   ループについての前記最良候補重みのセットのうちの対
   応する重みを乗ずることによって得られる加重和との、
   差異を示す合成誤差信号を、生成する過程と、 ｇ．もし前記合成誤差信号が前に記憶された合成誤差信
   号よりも小さい場合又は前に合成誤差信号が全く記憶さ
   れていない場合に、前記最良候補重みと、前記対応する
   候補変位グループと、前記候補変位グループのセットの
   うちの、最小の合成誤差信号を有する候補変位グループ
   についての前記合成誤差信号とを記憶する過程と、 ｈ．前記候補変位のうちの１つの候補変位グループとこ
   の１つの候補変位グループについての前記対応する最良
   候補重みのセットとが所定の条件を満足するまで、過程
   （ｂ）から過程（ｈ）までを繰り返す過程と、 ｉ．前記符号化信号に、前記所定の条件を満足するよう
   な、候補変位の前記グループと前記グループに対する前
   記対応する最良候補重みのセットとを含めることによっ
   て、もし前記記憶された基準フレームのコピーが利用可
   能なら前記画素ブロックの再構築バージョンをその符号
   化信号から再構築可能なような、前記画素ブロックに対
   応する前記符号化信号を形成する過程と、 ｊ．前記符号化信号を伝送媒体に送達する過程と、 からなることを特徴とするビデオイメージ処理における
   符号化信号の発生方法。
2. 【請求項２】 前記選択基準が意味する選択すべき候補
   変位は、 前記基準フレームの各々について且つ前記選択過程の繰
   り返しの全てについて、 （１）前記符号化すべき画素ブロックの前記位置に同一
   の第１の端点を有するとともにそれぞれ異なる第２の端
   点を有する変位であって、 前記選択過程の最初の繰り返しにおいては、これらの第
   ２の端点が、前記画素ブロックの前記位置、及び、前記
   画素ブロックの前記位置から、所定の距離セットのうち
   の或る所定の距離だけほぼ等距離離れ且つ相互にほぼ等
   距離離れた位置、にある変位、 更に、前記選択過程の前記最初の繰り返しに続く１つ以
   上の繰り返しにおいては、これら第２の端点が、前記生
   成過程の繰り返しのうち直前の繰り返しにおいて合成誤
   差信号が最小であった候補変位グループの中の前記基準
   フレームに対応する候補変位の第２の端点の位置として
   指定された位置にある変位、及び （２）前記指定された位置から、所定の距離セットのう
   ちの或る所定の距離だけほぼ等距離離れ且つ相互にほぼ
   等距離離れた位置にある変位、であることを特徴とする
   請求項１の方法。
3. 【請求項３】 前記所定の距離セットが、前記選択過程
   の各繰り返しについて各１つの距離を含み、引き続いて
   行われる繰り返しが順次進むにつれてこの各１つの距離
   が順次短くなるように構成され、 前記所定の条件が、前記所定の距離セット中に残存する
   メンバーが取り尽くされて消滅することを意味する、 ことを特徴とする請求項２の方法。
4. 【請求項４】 前記選択基準が意味する選択すべき候補
   変位が、前記選択過程の最初の繰り返しにおいて、少な
   くとも１つの、前記符号化すべき画素ブロックに隣接す
   る画素ブロックを符号化するのに用いられる変位に対応
   する候補変位であることを特徴とする請求項１の方法。
5. 【請求項５】 前記選択基準が、 前記選択過程の最初の繰り返しに続く１つ以上の繰り返
   しにおいて、前記基準フレームのうちから前記選択過程
   の各繰り返しごとに循環的に選択する仕方によって選択
   される１つの特定の基準フレームについては、所定の候
   補変位サブセットを選択すること、及び、 前記１つの特定の基準フレームではない前記基準フレー
   ムの各々については、前記記憶された候補変位グループ
   の中の対応する１つの候補変位を用いること、を意味す
   ることを特徴とする請求項４の方法。
6. 【請求項６】 所定の順位付け基準が、前記候補変位グ
   ループのセットの順位付けを、最も近い過去に合成誤差
   信号が最小であった候補変位グループから前記１つの特
   定の基準フレームにおいて最も近い過去に用いられた候
   補変位、のまわりの渦巻の向きに基づいて行うことを意
   味することを特徴とする請求項５の方法。
7. 【請求項７】 前記選択基準が、 前記選択過程の最初の繰り返しに続く１つ以上の繰り返
   しにおいて、前記基準フレームのうちから前記選択過程
   の各繰り返しごとに循環的に選択する仕方によって選択
   される１つの特定の基準フレームであり且つ前記（ｂ）
   から（ｈ）までの過程の繰り返しのうちの直前の繰り返
   しにおいてこの１つの特定の基準フレームについて前に
   記憶されていた誤差信号よりも小さな合成誤差信号が記
   憶されていなかったような１つの特定の基準フレームに
   ついては、所定の変位サブセットを選択すること、及
   び、 前記１つの特定の基準フレームではない前記基準フレー
   ムの各々については前記記憶された候補変位グループの
   中の対応する１つの変位を用いること、 を意味することを特徴とする請求項４の方法。
8. 【請求項８】 前記選択基準が更に、 前記（ｂ）から（ｈ）までの過程の前記繰り返しのうち
   の直前の繰り返しにおいて合成誤差信号が最小であった
   候補変位グループについての前記１つの特定の基準フレ
   ームからの１つの候補変位と同一の行成分又は同一の列
   成分を有するような前記１つの特定の基準フレームから
   の候補変位のみを選択すること、及び、 この同一の行成分又は同一の列成分を有するような候補
   変位の選択が、前記同一の行成分を有するような前記候
   補変位と、前記同一の列成分を有するような前記候補変
   位とを、前記選択過程の各繰り返しごとに交互に選択す
   ること、 を意味することを特徴とする請求項７の方法。
9. 【請求項９】 前記割り当て過程が、 前記候補変位グループのセットの各グループに対する１
   つの行列Ｍの各要素を検討評価する過程からなり、 前記行列は、列と行とに配列された行列要素を有し、１
   つの列と１つの行とが前記基準フレームの各々に対応し
   且つ列と行との両方について同様な順序に配列され、こ
   れらの列及び行は各々、これらの列及び行に対応し且つ
   前記符号化すべき画素ブロックの前記位置から前記候補
   変位の前記グループのうちの前記候補変位の中の対応す
   る１つの候補変位だけ変位する前記基準フレーム中の画
   素ブロックを識別するラベルを有し、前記行列要素は各
   々、前記行列要素の前記列ラベル及び行ラベルによって
   識別される画素ブロックの各対応する画素位置の値の積
   の和であり、 前記割り当てる過程が更に、 ベクトル要素を１つの列に配列されたベクトルｖの各ベ
   クトル要素を検討評価する過程からなり、前記列の各行
   は、前記基準フレームの１つに対応し且つ前記行列Ｍの
   前記行と同様の仕方で順位付けされ、前記行は各々、前
   記行に対応し且つ前記符号化すべき画素ブロックの前記
   位置から前記候補変位の前記グループの各々のうちの前
   記候補変位の中の対応する１つの候補変位だけ変位する
   前記基準フレーム中の画素ブロック、を識別するラベル
   を有し、前記ベクトル要素は、前記行ラベルと前記符号
   化すべき画素ブロックとによって識別される前記画素ブ
   ロックの各々における各対応する画素位置の値の積の和
   であり、 前記割り当てる過程が更に、線形方程式Ｍ.ｕ＝ｖ のシ
   ステムを解くことにより、前記候補変位グループの各々
   について、ベクトルｕ* を導く過程からなり、ベクトル
   ｕ* の各ベクトル要素が候補重みを表し、１つの候補重
   みが前記候補変位グループの各候補変位メンバーに対応
   し且つ前記行列の前記行と同様の仕方で順位付けされ、 前記割り当てる過程が更に、 前記候補変位グループの各々に割り当てられる前記最良
   重みのセットとして、前記ベクトルｕ* を採用する過程
   からなる、 ことを特徴とする請求項１の方法。
10. 【請求項１０】 異なるベクトルｕq についての前記所
    定の条件を満足する前記候補変位グループに対応する前
    記ベクトルｕ* の各重みを量子化する過程を有する、 ことを特徴とする請求項９の方法。
11. 【請求項１１】 ２つの基準フレームＩm、Ｉp が用いら
    れ、前記所定の量が△max であり、ｍ11及びｍ22が行列
    Ｍの対角要素であり、ｍ12が行列Ｍの非対角要素であ
    り、△αm 及び△αp が各々フレームＩm 及びフレーム
    Ｉp について用いられる量子化ステップの大きさであ
    り、且つ△αm 及び△αp が各々、（ｍ22／ｍ11）×△
    αp 、及び（ｍ11△max／｜Ｍ｜）1/2、より小さいか等
    しいように維持されることを要する、 ことを特徴とする請求項１０の方法。
12. 【請求項１２】 前記導く過程が更に、 前記ベクトルｕ*の全メンバーの和が、前記ステップの
    大きさ△αを（△max／（ｍ11＋ｍ22−２ｍ12））1/2、
    より小さいか等しい値に維持することを要するような
    状態をもたらす値、であることを要する、 ことを特徴とする請求項１０の方法。
13. 【請求項１３】 前記抜粋する過程は、 前記複数の候補変位グループのうちの各グループ内の全
    ての変位が、前記基準フレーム内のイメージ表示子に対
    応する相対時間の関数によって互いに相関関係にある状
    態を必要とすることを特徴とする請求項１の方法。
14. 【請求項１４】 前記時間関数が、前記基準フレームと
    前記符号化すべき画素ブロックの前記フレームとの間の
    差異の比率であることを特徴とする請求項１３の装置。
15. 【請求項１５】 各フレームが少なくとも１つのイメー
    ジ表示子を有するような複数のフレームから構成され
    る、入力として印加されたビデオ信号の或るフレーム内
    の所定の位置にある符号化すべき画素ブロックに関し
    て、前記ビデオ信号の前記複数のフレームのうち基準フ
    レームに指定され複数の画素ブロックに分割される少な
    くとも２つのフレームから、変位及び対応する重みを表
    す信号のセットを発生させることによって、前記符号化
    すべき画素ブロックについての符号化信号を発生させる
    ための、ビデオイメージ処理における符号化信号の発生
    装置において、 前記基準フレームを記憶する手段（１２５、１３０）
    と、 所定の選択基準に応じて、前記基準フレームの各々につ
    いて前記符号化すべき画素ブロックの前記位置から計測
    され且つそのベクトルの大きさが所定の最大変位のベク
    トルの大きさ以下の候補変位を選択する手段（１１８）
    と、 前記選択された候補変位から、その候補変位グループの
    セットの各グループが前記基準フレームの各々からの候
    補変位をそれぞれ１つずつ有するような候補変位グルー
    プのセットを抜粋する手段（１１８）と、 前記候補変位グループのセットの前記グループを、所定
    の順位付け基準に応じて順位付けする手段（１１８）
    と、 前記候補変位グループの各々に、１つの候補重みが前記
    候補変位グループの１つのメンバーにそれぞれ対応する
    ように、前記候補変位グループについての最良候補重み
    のセットを割り当てる手段（１２９）と、 前記候補変位グループの各々について、前記符号化され
    る画素ブロックの画素値と、符号化される前記画素ブロ
    ックの前記位置から前記候補変位の前記グループ内の前
    記候補変位のうちの対応する候補変位だけ変位される前
    記基準フレームの前記画素ブロックの画素値の加重和で
    あって前記記憶された基準フレームの前記画素ブロック
    の前記画素値のうちの対応する値に前記候補変位グルー
    プについての前記最良候補重みのセットのうちの対応す
    る重みを乗ずることによって得られる加重和との、差異
    を示す合成誤差信号を、生成する手段（１１８）と、 もし前記合成誤差信号が前に記憶された合成誤差信号よ
    りも小さい場合又は前に合成誤差信号が全く記憶されて
    いない場合に、前記最良候補重みと、前記対応する候補
    変位グループと、前記候補変位グループのセットのうち
    の、最小の合成誤差信号を有する候補変位グループにつ
    いての前記合成誤差信号とを記憶する手段（１１８）
    と、 前記候補変位のうちの１つの候補変位グループとこの１
    つの候補変位グループについての前記対応する最良候補
    重みのセットとが所定の条件を満足するまで、前記選択
    する手段、前記抜粋する手段、前記割り当てる手段、前
    記生成する手段、及び前記記憶する手段、の作動の順序
    立てと調整とを繰り返し行う手段（１１８）と、 前記符号化信号に、前記所定の条件を満足するような、
    候補変位の前記グループと前記グループに対する前記対
    応する最良候補重みのセットとを含めることによって、
    前記画素ブロックに対応する前記符号化信号を形成する
    手段と、 前記符号化信号を出力信号として供給する手段（１１
    ７）と、 からなるようにしたことを特徴とするビデオイメージ処
    理における符号化信号の発生装置。