JPH0192885A - デイジタル像シーケンスからの運動ベクトル場の探索方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、ディジタル像シーケンスから運動ベクトル
場を探索するための方法であって、それぞれ２つの相続
く像から、一方の像の各画素に他方の像の画素を対応付
ける運動ベクトル場が探索・され、その対応付けは、互
いに相対的な画素のシフトを表すそれぞれ１つの運動ベ
クトルにより定められており、またその際に正方形また
は長方形ブロックのなかのそれぞれすべての画素は等し
い運動ベクトルを保持する方法に関するものである。

〔従来の技術〕

種々の応用、たとえば像データ圧縮または機械的ビュー
（ロボット、情景解析）のために、１つの像シーケンス
のなかに存在する、対象物運動またはカメラ運動から生
ずる像から像への像内容のシフトを自動的に検出する必
要がある。局部的像内容のこれらのシフトは、たとえば
１つの像の各画素にこの個所における像内容が以前の像
にくらべてどれだけシフトしているかを示す運動ベクト
ル場により表され得る。

運動ベクトル場はたとえば像データ圧縮において低いデ
ータ速度でディジタル像を伝達する目的で、既に伝達さ
れた像からすぐ次のまだ伝達されていない像を予測する
ために使用される。この予測が良好であるほど、新しい
像の伝達のために必要なデータ速度は小さいし、または
−層良好な像質で新しい像が予め定められたデータ速度
で伝達され得る。

運動ベクトル場の別の応用は、データ圧縮の目的でサブ
サンプリングされた像シーケンスからの欠落像の再構成
である。これはたとえばシーケンスの容筒３の像のみが
利用可能であり、各２つの存在する像（“支持点像ｎ）
の間の両欠落像が、再構成された情景のなかで対象物の
運動が原像のなかの運動のように均整に経過するように
、できるかぎり゛°運動正しく”内挿されなければなら
ないことを意味する。そのために、内挿すべき像の各画
素に対して、付属の両支持点像のなかのどの画素を当該
の画素の再構成のために使用すべきかを示す運動ベクト
ル場が必要である。

いずれの場合にも、運動ベクトル場のなかで１つの像の
各画素に、または隣り合う画素の各１つの群に、局部的
運動を２つの構成要素、すなわち水平および垂直運動成
分により記述する運動ベクトルが対応付けられている。

このような運動ベクトル場の探索の際の問題は、像シー
ケンスのなかに存在する運動が一般に画素の位置に関係
しており、従って既に小さい像断片のなかに、特に動か
された対象物の縁において、多くのシフトされた運動ベ
クトルが生じ得ることにある。従って、特定の画素に対
する運動ベクトルの探索に対しては本質的にこの画素自
体のみが考慮されればよい。他方において、個別画素か
ら運動ベクトルを探索することは可能でない。なぜなら
ば、運動ベクトルは２つの構成要素を含んでおり、また
各個別画素はこれらの２つの未知数に対して１つの式の
みを定めるからである。たとえばホーン（Ｂ、に、Ｐ、
　Ｈｏｒｎ　）およびシュンク（Ｂ、Ｇ。

５ｃｈｕｎｋ　）著“光学的流れの決定°゛、アーティ
フィシアル・インテリジェンス（Ａｒｔｉｆｉｃｉａｌ
　Ｉｎｔｅｒｉｇｅｎｃｅ）　ｌ　７、第１８５〜２０
３頁、１９８１年を参照されたい。しかし、画素の周り
の小さい周囲のなかでも像内容はしばしば、当該の画素
の位置における運動が一義的に確定可能でないようにわ
ずかに構造化されている。このことから、一方では強く
位置に関係する運動ベクトルを有する領域のなかでは小
さい周囲のみを１つの運動ベクトルの計算のために使用
すべきであり、他方では明白に構造化されていない像内
容を有する領域のなかでは、一義的に運動を認識し得る
ように、大きい周囲が必要とされるという難点が生ずる
。従って、そのつどの周囲の大きさを変更する必要があ
り、さらに、ノイズを存する像においても、またわずか
に区別された像断片のなかでも、上記の応用に使用可能
な運動ベクトルを得るため、予知、すなわちたとえば運
動ベクトル場の特定の平滑性の仮定が利用されなければ
ならない。

たとえばムスマン（）１．Ｇ、　Ｍｕｓｍａｎｎ）　、
ビルシュ（Ｐ、　Ｐｉｒｓｃｈ　）　、グララード（Ｈ
，Ｊ、　Ｇｒａｌｌｅｒｔ　）著゛両像符号化の進歩”
、米国電気電子学会雑誌（Ｐｒｏｃ、　ＩＥＥＥ）　７
３　（１９８５）　４、第５２３〜５４８頁に記載され
ているように、既に運動ベクトル推定のための主に３種
類の方決が研究されている。すなわち、 ■）ブロック−マツチング法 ２）差分法 ３）卓越した点により動作する方法 これらの方法の動作の仕方は以下に、１つの像シーケン
スの１つの像（たとえば像Ｂ）に対して先行像にくらべ
ての像内容のシフトが決定されるべき場合について簡単
に説明される。

りについて ブロック−マツチング法では、運動ベクトルを決定され
るべき像は一定の大きさの、すなわち予め定められた数
の画素（しばしば１６Ｘ１６または８×８）を有する正
方形または長方形のブロックに分割される。たとえばリ
ン（Ｃ，Ｍ、　Ｌｔｎ）　、クワトラ（Ｓ、Ｃ６Ｋｗａ
ｔａ）著パ運動補償′されたインターフレームカラー両
像符号化”、国際通信会議論文集（Ｐｒｏｃ、　Ｉｎｔ
、　Ｃｏｎｆ、　ｏｎ　ＣｏＩＩｌｍｕｎｉｃａｔｉｏ
ｎｓ）、１９８４、第１巻、第５１６〜５２０頁および
ブルセヴイツ（Ｈ，Ｂｒｕｓｅｗｉｔｚ）　、ワイス（
Ｐ、　Ｗｅｉｓｓ）著“３８４ｋｂｉｔ／ｓでのビデオ
会議システム”、両像符号化シンポジウム、東京、抄録
第２１２真、１９８６を参照されたい、１つのブロック
のなかのすべでの画素に対して、近似的に運動が１つの
ブロックに相応する小さい像断片のなかで一定であると
いう仮定に相応して、同一の運動ベクトルが決定される
。

この場合、像Ｂのなかの１つのブロックに対する運動ベ
クトルは、予め定められた値範囲のなかの多数の可能な
運動ベクトルに対してそれぞれ、像Ａからの運動ベクト
ルだけシフトされた画素を含んでいる像Ａのなかの画素
が取り出されること、また多数のこれらのブロックから
像Ｂのなかの予め定められたブロックに対して最もわず
かな相違を存するブロックが選び出されることにより決
定される。その際に像ＡおよびＢのなかの２つのブロッ
クの相違は適当な間隔尺度、すなわちたとえば画素差の
二乗の和（Ｌ２ノルム）または絶対値の和（Ｌｌノルム
）により表される。像ＡおよびＢからの両ブロックが最
もわずかな間隔を有する運動ベクトルが探索される運動
ベクトル場のなかに受は入れられる。

この場合、問題は、Ｗ頭に記載したように、適当な大き
さのブロックの選定にある。あまりに大きいブロックで
は運動ベクトルはあまりに粗くかつ不正確になる。なぜ
ならば、個々のブロックのなかの一定の運動の仮定がも
はやそぐわなくなるからである。あまりに小さいブロッ
クではしばしば像内容が、正しい対象物運動を認識する
ためにあまりに無差異である０文献クンマーフェルト（
Ｋｕｍｍｅｒｆｅｌｄｔ　）　、メイ（Ｆ、　Ｍａｙ）
　、ウオルフ（朽。

Ｗｏｌｆ）著“３２０および６４　ｋ　ｂ　ｉ　ｔ　／
　ｓでのテレビジョン信号符号化°°、イメージコーデ
ィング（Ｉｍａｇｅ　Ｃｏｄｉｎｇ）　、シフト（Ｍ、
　Ｋｕｎ）　、ファング（Ｔ、Ｓ、　Ｈｕａｎｇ）　　
（出版者）、Ｐｒｏｃ、５ＰＩＥ５９４、第１１９〜１
２８頁、１９８５には、１つの対象物に属するものとし
て分類される多くのブロックの運動ベクトルの事後の統
合および平滑化により、どっちつかずの像内容を存する
ブロックのなかの誤ったベクトルの問題を解決すること
が試みられている。しかし、この方法は、追加的な対象
物運動なしの“カメラズーム”のような像内容の非常に
箭単に記述すべき全体運動の場合にのみ運動ベクトル場
の改善（この場合、像データ圧縮のなかの運動適応性予
測に使用）をもたらすという結果が示されている。

２）について 差分法（たとえばロバート（Ｐ、　Ｒｏｂｅｒｔ　）　
、キャホリオ（Ｃ，Ｃａｆｆｏｒｉｏ　）　、ロッカ（
Ｆ、　Ｒｏｃｃａ）著゛差分運動推定のための時間／空
間的反復“、イメージコーディング（Ｉｍａｇｅ　Ｃｏ
ｄｉｎｇ）　、シフト（Ｍ、　Ｋｕｎｔ　）　、ファン
グ（Ｔ、Ｓ、　Ｈｕａｎｇ）　　（出版者）、Ｐｒｏｃ
、５ＰＩＥ５９４、第１７５〜１８５頁１９８６を参照
）では、隣り合う画素のブロックに対する一定の運動の
仮定が放棄され、その代わりに各画素に対して固有の運
動ベクトルが探索される。この目的で各画素に対して、
画素の周囲のなかの像信号の局部的経過を記述する特定
のモデルパラメータが計算され、またこれらのパラメー
タと、考察されている画素の位置における像ＡおよびＢ
の像内容の差とから、基礎となっている運動、すなわち
像内容のシフトが推定される。一般にこの運動の推定は
先ず単に近領解であるので、運動ベクトルのそれ以上の
改善がもはや生じなくなるまで、手順が反復して継続さ
れる。

この方法における１つの問題は、モデルパラメータによ
る像内容の記述が狭い限界内でのみ有効であり、またた
とえば像Ａと像Ｂとの間の大きい　。

シフトの際には誤ることにある。さらに、１つの画素に
対するモデルパラメータの計算のために画素の周囲が一
緒に利用され、その際に再びこの周囲のなかの運動の一
様性が前提とされ、従ってこの周囲の大きさの選定がブ
ロック−マツチング法でのブロックの大きさの選定と同
じ問題を投げかける。画素の周囲が重なり合っているこ
とにより、１つの画素からすぐ次の画素へわずかしか変
化せず、従って対象物境界において生ずるような運動の
なかの跳躍を正しく再現しないベクトル場が生ずる。

文献ホーン（Ｂ、に、Ｐ、　Ｈｏｒｎ　）およびシュン
ク（Ｂ、Ｇ、　５ｃｈｕｎｃｋ）著“光学的流れの決定
”、アーティフィシアル・インテリジェンス（Ａｒｔｉ
ｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　）　１７、
第１８５〜２０３頁、１９８１年には、これらの差分法
において、一義的な運動＃、？！熾を許さない均等な像
範囲のなかでもリアリティに十分に相応する有意義な運
動ベクトル場が探索され得るようにどのように注意され
得るかの問題が議論されている。最小化すべき目的関数
のなかに、相応の運動ベクトル場の非平滑性を表す１つ
の項を取り入れることが提案される。運動ベクトル場の
非平滑性を測定するこの目的間数の成分の形成のために
、（なかんずく解析的かつ数学的に簡単に取り扱い可能
な関数を生ずるので、ベクトル場のいわゆる“ラブラシ
アンパの二乗ノルムが測定される）、対象物境界におけ
るこの方法の問題が生ずる。すなわち運動ベクトル場の
なかの跳躍が誤って抑制される。

３）について 第３の方法では、実際の対象物運動が局部的な像内容か
らしばしば一義的に認識可能でないという問題を、先ず
卓越した点（“グレー値コーナー”）または線（輝度縁
）が像のなかで探索され、またこれらの点に対してまた
は線に沿ってのみ１つの運動ベクトルが探索されること
により迂回することが試みられる。たとえばレンツ（Ｒ
，Ｌｅｎｚ　）著“ＴＶ情景のなかの２Ｄ一般運動パラ
メータの推定”、第７回国際パターン認識会議論文集（
Ｐｒｏｃ。

７ｔｈ　Ｉｎｔ、　Ｃｏｎｆ、　Ｐａｔｔｅｒｎ　Ｒｅ
ｃ、　）　、モントリオール、カナダ、１９８４年７月
３０日〜８月２日、第１巻、第５４６〜５４８頁および
ラドフォード（Ｃ，Ｊ、　Ｉ？ａｄｆｏｒｄ）著“ホウ
フ（ＨＯｕｇｈ　）変換空間内の光学的流れ場′”、パ
ターン認識レターズ（Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉ
ｔｉｏｎ　Ｌｅｔｔｅｒｓ　）　４、第２９３〜３０３
頁を参照されたい。この場合、画素の残余に対して運動
ベクトル場が適当な手段により所与の運動ベクトルから
内挿されなければならない。この場合、問題となるのは
、先ず運動ベクトルが探索される卓越した点または線を
確実に見出すこと、また卓越した点または線の所与のベ
クトルから内挿により探索され得る−様な運動を有する
領域のなかの像をセグメント化することである。これら
の部分的課題が困難であるために、これらの方法は実際
にたとえば車両のような剛固な物体を有する像シーケン
スにのみ適しており、しばしば像データ圧縮に生ずるよ
うな動く人物を有する情景の処理には適していない。

これらの方法に対しても平滑化操作が開発されている。

同様に運動ベクトル場から導き出された非平滑性関数の
二乗ノルムに暴づく、たとえばナーゲル（Ｈ，Ｈ，Ｎａ
ｇｅ１）　、エンケルマン（Ｗ、　Ｅｎｋｅｌｍａｎｎ
　）著“像シーケンスからの変位ヘクトル場の推定に対
する平滑性抑制の検討パ、米国電気電子学会論文集（ｒ
ＥＥＥ　Ｔｒａｎｓ、　）　Ｐ　ＡＭ　Ｉ　−８／　５
第５６５〜５９３頁、１９８６年９月を参照されたい。

この場合、周知の問題が対象物境界において生ずるので
、この論文では、運動ベクトル場の平滑化を当該の像の
なかの耀度分布の勾配に対し、て垂直にのみ行う“方間
付けられた平滑性要求゛を作成することが提案された。

しかしながら、そのための方法は非常に費用がかかる。

〔発明が解決しようとする課題〕

本発明の課題は、運動ベクトル場を所与の像シーケンス
から決定し得る冒頭に記載した種類の方法であって、運
動ベクトル場ができるかぎり実際に像のなかに存在する
運動を再現するように特別な対策が講じられている新し
い方法を提供することである。

〔課題を解決するための手段〕

この課題は、本発明によれば、ディジタル像シーケンス
から運動ベクトル場を探索するための方法であって、そ
れぞれ２つの相続く像から、一方の像の各画素に他方の
像の画素を対応付ける運動ベクトル場が探索され、その
対応付けは、互いに相対的な画素のシフトを表すそれぞ
れ１つの運動ベクトルにより定められており、また正方
形または長方形ブロックのなかのそれぞれすべての画素
は等しい運動ベクトルを保持する方法において、運動ベ
クトルの探索が、一方では２つの与えられた像の互いに
対応付けられる画素の輝度値の差を考慮し、他方では座
標が隣り合っている運動ベクトル、すなわちいわゆる近
傍運動ベクトルの間の差を平滑性尺度により評価する合
成された目的関数の最小化により行われ、またこの目的
関数の最小化が、先ず目的関数を最小化する運動ベクト
ルが運動ベクトルが最終的に得ようと努められるブロッ
クよりも大きいブロックのなかでは一定であるという制
限のもとに探索され、続いてこれらのブロックの各々が
、得ようと努められるブロックの大きさが到達されるま
で、より小さい、好ましくは等大のブロックに分割され
るように行われ、ブロックの各縮小の後に再び目的関数
が運動ベクトルの変化により最小化されることを特徴と
するディジタル像シーケンスからの運動ベクトル場の探
索方法により解決される。

本発明による方法は先に説明したブロック−マツチング
法（前記のムスマンはかの文献を参照）から出発する。

すなわち、それぞれ画素のブロックに対して運動ベクト
ルが種々の可能なベクトルに対する目的関数の評価と目
的関数の最適を供給する運動ベクトルの探索とにより探
索される。

本発明の有利な実施態様は請求項２以下にあげられてい
る。

〔作用効果〕

前記の問題を克服するため、本発明によれば、下記の新
しい原理が運動ベクトル探索方法に取り入れられている
。

（１）対象物境界においても実際の運動を高い精度で記
述する高い分解能を有する運動ベクトル場を得るため、
像がたとえば４×４画素の小さいブロックに分割され、
これらのブロックに対してそれぞれ運動ベクトルが探索
される。しかし、小さいブロックの欠点（場合によって
は、どっちつかずで十分に特徴的でない像内容）を克服
するため、先ず本方法の第１のステップで運動ベクトル
探索がかなり大きいほうのブロック（たとえば１６×１
６−または３２×３２画素）に対して行われる。

これらの大きいブロックは本方法のその後のステップで
より小さいブロックに分割され、それらに対してそれぞ
れ固有の運動ベクトルが探索され、その際に大きいブロ
ックの運動ベクトルは出発点および補助手段としての役
割をする（減少するブロック大きさ）。

（２）相続く像の画素値の差のみを表すブロック−マツ
チング法の通常の目的関数の代わりに、本発明による方
法では、適当な追加項により運動ベクトル場の“平滑性
°゛をも考慮する目的関数が使用される。特に本方法の
第１のステップで大きいブロック大きさを有する運動ベ
クトル場の初期化の際に個々の運動ベクトルの長さが最
小化すべき目的関数に入れられる。次いで本方法の後続
ステップで、°隣り合うパ運動ベクトル、すなわち隣り
合うブロックの運動ベクトルの差が目的関数に入れられ
る。この形式の目的関数により、たとえば人物のように
形状が変化し得る対象物の運動の探索の際にも、運動ベ
クトル場の平滑化と１孤立値”として現れる探索誤差の
抑制とが行われる。

（３）他の方法（差分法および卓越した点により動作す
る方法）において平滑性尺度に関連して現れる（運動ベ
クトル場のなかの跳躍が可能でなければならない）対象
物縁における問題は本発明によるブロック−マツチング
法では、隣り合う運動ベクトルの差を測定する平滑性尺
度が差の二乗ノルムではなく絶対値ノルムに基づいてい
ることにより回避される。効果は、はっきり打ち出され
た跳躍は運動ベクトル場のなかにとどめられており、い
わゆる“孤立値”のみが抑制される運動ベクトル場のメ
ジアン−フィルタリングに類似している。

従って、この平滑性尺度は対象物縁における運動ベクト
ル場の正しい探索をも可能にする。

（４）特に像データ圧縮の目的の像符号化では本方法は
、送信側で先ず大きいほうのブロックのみで動作され、
また付属の運動ベクトルが受信器に伝達されるように応
用される。これらの運動ベクトルは像の運動補償された
予測のために送信器（コーダー）および受信器（デコー
ダー）のなかで使用される。追加的に受信器側で受−信
された像により、所望の畠小のブロック大きさが得られ
るまで、反復して運動ベクトル場に対するまだ欠けてい
る細分化ステップが行われる。この運動ベクトル場は次
いで、送信器においてデータ整理の目的でとばされた像
シーケンスの欠落像を運動正しく内挿するのに使用され
る。

（実施例） 以下、本発明を複数の図面により詳細に説明する。

本方法は以下に、２つの像−像Ａおよび像Ｂ−から１つ
の運動ベクトル場が探索される場合に対する好ましい実
施例により説明され、その際にそれぞれ４×４画素のブ
ロックに対して１つの−様な運動ベクトル場が定められ
る。本方法は先ず、多くの小さいブロックを含んでいる
大きいほうのブロックで開始する。いまの例では大きさ
１６×１６のブロックで開始される。

すべての進行過程は、第１図に示されているようなプラ
ンに従う。

本方法のステップは以下に説明される。

ブロック−マツチング１６Ｘ１６　（ＩＮＩＴ１６）画
素 ａ（ｋ、ｈ）、　ｋ　＝　１．、、Ｉ、　ｈ　＝　１．
、、Ｊ　　　（１，１ａ）および ｂ（ｉ、ｊＬ　ｉ　＝　１．、、Ｉ、　ｊ　＝　１．、
、Ｊ　　　（１，１ｂ）ここでｉまたはｋは行インデッ
クス、ｊまたはｈは列インデックス から成るシーケンスの２つの相続く像ＡおよびＢが与え
られている。

方法全体の目的は運動ベクトル場 Ｘ（ｉ、ｊ）、ｉ＝１．、、Ｉ、ｊ＝１．、、Ｊ　　　
（１，１ｃ）の探索である。

像Ｂはいま、それぞれ１６×１６画素ｂ（ｉ。

ｊ）を含んでいるブロック Ｂ（ｍ、ｎ）ここでｍ　＝　１．、、Ｍ、　ｎ　＝　１
．、、Ｎ　　　（１，２）に分割される（第２図参照）
。

各ブロックＢ　（ｍ、ｎ）に対していま先行の補助手段
としての役割をする運動ベクトルＸ１６（ｎ＋、ｎ）　
＝　（ｘ１６（ｍ、ｎ）、　ｙ１６（ｍ、ｎ））　　　
　（１，３）が探索される。この運動ベクトルは２つの
構成要素、すなわち水平シフトｘ１６　（ｍ、ｎ）およ
び垂直シフトｙ１６　（ｍ、ｎ）から成っている。

この運動ベクトルＸ１６　（ｍ、ｎ）によりブロックＢ
　（ｍ、ｎ）のなかの各画素ｂ（ｉ、ｊ）に像Ａからの
画素ａ　（ｋ、　　ｈ）が関係式％式％） により対応付けられる。すなわち、画素ｂ　（ｉ。

ｊ）に対応付けられる画素ａ　（ｋ、ｈ）の座標〔ｋ、
ｈ〕は座標（ｉ、ｊ）へのシフトまたは運動ベクトルχ
１６（ｍ、ｎ）の加算により生ずる。

Ｘ１６（ｍ、ｎ）を計算するためブロックＢ（ｍ、ｎ）
のなかの各画素ｂ（ｉ、ｊ）に対して、また考察される
各運動ベクトル（ｒ、ｓ）に対して“変位されたフレー
ム差” ｄ（ｉ、ｊ、ｒ、ｓ）　＝　ｂ（ｉ、ｊ）−ａ（ｉ＋ｒ
、ｊ＋ｓ）　　　（１，５）すなわち、像Ａからの運動
ベクトル（ｒ、ｓｌだけシフトされた相応の画素への差
が定義される。

その後にブロックＢ　（ｍ、ｎ）のなかの差ｄ（ｉ、ｊ
、ｒ、ｓ）の絶対値が累算され、それによりブロックＢ
　（ｍ、ｎ）および運動ベクトル（ｒ。

Ｓ）に対する“変位されたフレーム差パのＬｌノルム（
絶対値ノルム）Ｄ１６　（ｍ、ｎ、ｒ、ｓ）が生ずる： ０１６（ｍ＋”＋ｒ＋ｓ）　＝　ｓｕ＋ｓ　ａｂｓ　（
ｄ（ｉ、ｊ、ｒ、５））ｔ、ｊｉｎ　Ｂ（ｍ、ｎ）　　
　　　　　（１，６）この和Ｄ　（ｍ、ｎ、ｒ、ｓ）に
いま、運動ベクトル場の平滑化のための第１の対策とし
て、運動ベクトル（ｒ、ｓ）の長さを評価する“ペナル
ティ類”ＰＩ３　（ｒ、ｓ）が加算される：０１６’（
ｍ、ｎ、ｒ、ｓ）　＝　０１６（ｍ、ｎ、ｒ、ｓ）＋Ｐ
１６（ｒ、ｓ）　（１，７ａ）その際 ＰＩ３（ｒ、５）＝２５６傘β１ｓ（ａｂｓ（ｒ）＋ａ
ｂｓ（ｓ））（１，７ｂ）である。

すなわち“ペナルティ類”はコントロールパラメータβ
および１つのブロックのなかの画素の数すなわち２５６
で乗算された運動ベクトルのＬｌノルムである。パラメ
ータβにより、どのように強く運動ベクトルの長さが目
的関数Ｄ１６’　　（ｍ。

ｎ、　　ｒ、　　ｓ）に入るかが決定されるａ　（シミ
ュレーション実験で実証されているβの典型的な値はβ
−１，０である。） その後にＤ１６’　　（ｍ、ｎ、ｒ、５）（７）最小が
（ｒ、ｓ）の変更により予め定められた値範囲Ｓのなか
で決定され、それにより探索される運動ベクトルＸ１６
　（ｍ、ｎ）＝　（ｘ１６　（ｍ、ｎ）。

ｙ１６　（ｍ、ｎ））が生ずる： ０１６°（ｍ、ｎ、ｘ１６（ｍ、ｎ）、ｙ１６（ｍ、ｎ
））＝ｍｉｎ　　Ｄ１６’（ｍ、ｎ、ｓ）ｒ、Ｓ　ｉｎ
　Ｓ （１，８） 一般にＳに対して正方形値範囲、たとえば両構成要素ｒ
およびＳの最大絶対値が上限を超過しないすべての運動
ベクトル（ｒ、　　ｓ）の集合が選ばれる。

変更された平滑性尺度を表す“ペナルティ類°。

をＤ　（ｍ、ｎ、ｒ、ｓ）に加算することにより、均等
な像範囲のなかで、または運動が局部的な像内容から一
義的に決定され得ない（Ｄ　（ｍ、ｎ。

ｒ、ｓ）の明白な最小がない）直線的に延びる縁におい
て、短い運動ベクトルが優先的に扱われることが達成さ
れる。こうして既に運動ベクトルパラメータのなかでの
“孤立値′°の生起の確率が減ぜられる。

β＝１．０に対してたとえば運動ベクトル（ｒ。

５）＝（０，１）は、零ベクトル（ｒ、５）＝（０，０
〕よりも優先されるように、平均的に少なくとも１．０
だけ少ない“変位されたフレーム差”ｄ　（ｉ、ｊ、ｒ
、ｓ）を生ずる。相応のことが、大きいほうの運動ベク
トルにも当てはまる。

完全探索は一般にあまりに時間がかかるので、値範囲Ｓ
は先ず１つの固定ラスクー（たとえば格子定数４）のな
かの成る数のサンプル値（ｒ、　　ｓ）に制限され、ま
た続いて最適の周囲のなかでさらに探索されるのが最も
よい（“３ステツプ探索”、たとえばムスマン（）１．
Ｇ、　Ｍｕｓｍａｎｎ）　、ピルシュ（Ｐ、　Ｐｉｒｓ
ｃｈ　）　、グララード（Ｈ，Ｊ、　Ｇｒａｌｌｅｒｔ
　）著゛両像符号化の進歩′°、米国電気電子学会雑誌
（Ｐｒｏｃ、　Ｉ［１ＥＥ）　７３　（１９８５）　４
、第５２３〜５４８頁参照）。この場合、本方法の的中
確実性は、探索が最適な運動ベクトルに従って部分的に
低域通過フィルタリングをされた像のなかで行われるこ
とにより高められ得る。このことと再び像のサブサンプ
リングが費用低減のために結び付けられ得る。

運動ベクトル探索法のこの第１のステップは公知のブロ
ック−マツチング法によっているが、運動ベクトル場の
平滑化の目的の式１．７ａ、ｂによる゛ペナルティ項°
“ＰＩ３　（ｒ、Ｓ）の導入により変更されている。

前記のように、すべてのブロックＢ　（ｍ、ｎ）に対す
る仮の運動ベクトルＸ１６　（ｍ、ｎ）の決定の後に、
この運動ベクトル場の反復改善が行われる（緩和）。そ
のためにいま新しい“ペナルティ環″“または新しい平
滑性尺度Ｐ１６”　　（ｍ、ｎ。

ｒ、ｓ）が定められ、それによりそのつどの４つの近傍
運動ベクトルＸ１６　（ｍ−１，ｎ）、ＸＩ６　（ｍ＋
１．ｎ）、Ｘ１６　、（ｍ、ｎ−１）およびＸ１６　（
ｍ、ｎ＋１）からの運動ベクトルＸ１６（ｍ、ｎ）の偏
差が測定される（第３図参照）。

平滑性尺度Ｐ１６’　　（ｍ、ｎ、ｒ、ｓ）は下式によ
り定められている。

Ｐ１６’　（ｍ、ｎ、ｒ、ｓ） −ａｂｓ（ｒ−ｘ１６（ｍ−１，ｎ））＋ａｂｓ（ｓ−
ｙ１６（＋＋＋−１＋ｎ））＋＋ａｂｓ　（ｒ−ｘ１６
　（ｍ＋　１　、　ｎ）　）＋ａｂｓ　（ｓ−ｙ１６　
（ｍ＋　１．　ｎ）　）＋＋ａｂｓ（ｒ−ｘ１６（ｍ、
　Ｉ−ｎ））＋ａｂｓ（ｓ−ｙ１６（ｍ、１−ｎ））＋
＋ａｂｓ（ｒ−ｘ１６（ｍ、　１＋ｎ））＋ａｂｓ（ｓ
−ｙ１６（ｍ、　１＋ｎ））重重α率　１６ （２，１） ここで、ｒおよびＳはブロックＢ　（ｍ、ｎ）に対する
新しい運動ベクトルＸ１６　（ｍ、ｎ）として使用され
るべき運動ベクトル（ｒ、ｓ）の構成要素である。

すなわち平滑性尺度Ｐ１６’　　（ｍ、ｎ、ｒ、ｓ）は
Ｘ］６　（ｍ、ｎ）とその近傍ベクトルとの間の４つの
差ベクトルの絶対値ノルム（Ｌｌノルム）の和にコント
ロールパラメータ“α”とブロックの辺の長さすなわち
１６とを乗算したものである。

コントロールパラメータダ°α”によ−り運動ベクトル
場の平滑性の度合いが緩和ステップでコントロールされ
得る。Ｌ１ノルムが選ばれた理由は、それによって、連
続的な移行を優先的に扱う“二乗ノルム”　（Ｌ２ノル
ム）と対照的に、対象物縁に存在するような運動ベクト
ル場の辺が保たれ続けるからである。

平滑性尺度Ｐ１６’　　（ｍ、ｎ、ｒ、ｓ）および″変
位されたフレーム差”　Ｄ１６　（ｍ、ｎ、ｒ。

ｓ）（式１．６）から新しい目的関数Ｄ１６’（ｍ。

ｎ、ｒ、ｓ）が形成される： ０１６”　（ｍ＋ｎ＋ｒ＋ｓ）□Ｄ（ｍ＋ｒ＋＋ｒ＋ｓ
）＋Ｐ１６°（ｍ＋ｎ＋ｒ＋ｓ）　（２−２）いま運動
ベクトル場の平滑化が、先ず式１．８（隣接関係なし）
に従って探索された運動ベクトル場から出発され、また
この事前割付けから出発して段階的に１つのブロックか
ら他のブロックへ新しい最適な運動ベクトルＸ１６　（
ｍ、ｎ）がＸ１６（ｍ、ｎ）　＝　　（ｘ１６（ｍ、ｎ
）、ｙ１６（ｍ、ｎ）　）　　　（２，３ａ）により決
定されることにより行われる。従って０１６”　（ｍ、
　ｎ、　ｘ１６（ｍ、　ｎ）　、　ｙ１６（ｍ、　ｎ）
）＝ｍｉｎ　０１６”　（ｍ＋　ｎ＋　ｒ＋　ｓ）ｒ、
ｓ　ｉｎ　Ｓ（ｍ、ｎ） （２，３ｂ） である。

その際、探索費用を制限するため（またベクトルを平滑
化するための別の対策として）、各ブロックに対する値
範囲Ｓ　（ｍ、ｎ）は適応性に、すなわち運動ベクトル
Ｘ１６　（ｍ、ｎ）＝ｘ１６　（ｍ、ｎ）、ｙ１６　（
ｍ、ｎ）およびその各４つの近傍運動ベクトルが異なっ
ているほど探索が広範囲であるように形成される： Ｓ（ｍ、ｎ）　＝　（ｒｍｔｎ、、、ｒｍａｘ、　５ｍ
１ｎ、、、ｓｍａｘ）　　（２，４ａ）ここで ｒｍｉｎ＝ｍｉｎ（ｘ１６（ｍ、ｎ）、ｘ１６（ｍ−Ｌ
ｎ）、ｘ１６（ｍ＋１．ｎＬｘ１６（ｍ、ｎ−１）、ｘ
１６（ｍ、ｒ＋＋１））ｒｍａｘ＝ｍａｘ　（ｘ１６　
（ｍ、　ｎ）　、　ｘ１６　（ｍ−１、ｎ）　、　ｘ１
６　（ｍ＋　ｌ　、　ｎ）　。

ｘ１６（ｍ、ｎ−１）、ｘ１６（ｍ、ｎ＋１））ｓｍｉ
ｎ＝ｍｉｎ（ｙ１６（ｍ、ｎ）、ｙ１６（ｍ−１，ｎ）
、ｙ１６（ｍ４１．ｎ）。

ｙ１６（ｍ、ｎ−１）＋ｙ１６（ｍ、ｎ＋１））ｓｍａ
ｘ＝ｍａｘ（ｙ１６（ｍ、ｎ）、ｙ１６（ｍ−１，ｎ）
、ｙ１６（ｍ＋ｌ、ｎ）。

ｙ１６（ｍ、ｎ−１）、ｙ１６（ｍ、ｎ＋１））（２，
４ｂ） いま ｒ＋ａｉｎ　’：　ｒ≦ｒｍａｘおよび５ｍ１ｎ≦Ｓ≦
ｓｍａｘが成り立つ運動ベクトル（ｒ、ｓ）のみが調べ
られる。

ブロック限界を越えても一定の運動ベクトルを有する領
域のなかではｒｍｉｎ＝ｘ１６　（ｍ、ｎ）”ｒｍａ　
Ｘかつｓｍ’ｒｎ＝ｙ１６　（ｍ、ｎ）＝ｓｍａｘであ
り、従って値範囲は１つの点に収縮し、また探索費用は
生じない、運動ベクトル場のなかに跳’１７Ｍおよびそ
の他の発散および“孤立値”の存在時にのみ改善が追求
される。

すべてのブロックＢ　（ｍ、ｎ）に対して１回ベクトル
Ｘ１６　（ｍ、ｎ）の改善が追求された後に、４つの近
傍運動ベクトルＸ１６　（ｍ−１，ｎ）などの少なくと
も１つが先行のバスで変化したすべてのブロックＢ　（
ｍ、　　ｎ）に対する過程がもう一度繰り返されなけれ
ばならない。こうして、４つの近傍運動ベクトルの一定
保持のもとに運動ベクトルＸ１６　（ｍ、ｎ）のいずれ
も改善され得なくなるまで継続される反復過程が行われ
る。

一般に像のなかの運動の度合いに応じて約５ないし１０
回の反復で十分であり、その際に最初の反復でのみ実際
にすべてのブロックが検査されなければならず、その後
は隣に最後のパスの際になお変化が生じているブロック
のみが検査されればよいことを考慮すべきである。

隣接ベクトルのし２ノルムではなくＬｌノルムが平滑性
尺度Ｐ１６’　　（ｍ、ｎ、ｒ、ｓ）（式２゜１）の基
礎となっているという事実は、この平滑性過程において
メジアン−フィルタリングの隙と類似して、辺が保持さ
れたままであることに通ずる。実際に数の集合の中位数
は、差の絶対値の和、すなわちＬｌノルムの和を最小化
する値である。

従って、Ｄ１６’　　（ｍ、ｎ、ｒ、ｓ）の最小化によ
る前記の平滑性は、“変位されたフレーム差”を考慮す
る運動ベクトルの一般化されたメジアン−フィルタリン
グとして解釈され得る。

いま、像のなかのすべてのブロックＢ　（ｍ、ｎ）にわ
たるＤ１６”　　（ｍ、ｎ、ｒ、ｓ）の加算により生ず
る全目的関数Ｚの１つの局部的最適が得られている。す
なわち、Ｚに対して下式が成り立つ：Ｚ　＝　Ｚｌ　＋
　αＺ２　　　　　　　　　　＜２．５）その際に７１
は式（１，５）に相応してｄ（ｉ、ｊ。

ｘ　（ｉ、ｊ）、ｙ　（ｉ、ｊ））を用いてＺｌ　−ｓ
ｕ摺ｄ（ｔ＋ｊ、ｘ（ｔ＋ｊＬｙ（Ｌｊ））＋１Ｊ　＋
ｎ　ｔｍａｇｅ　　　　　　　　　　　　（２，６）で
表され、またＺ２は Ｚ２　　＝　　ｓｕｍ ｉ＋ｊ　　ｉｎ　　ｉｍａｇｅ （１ｘ（ｉ、ｊ）−ｘ（ｉ−１，ｊ）ｌ＋　１ｙ（ｉ、
ｊ）−ｙ（ｉ−１，３）　ｌ＋＋　１ｘ（ｉ、ｊ）−ｘ
（ｉ＋Ｉ、ｊ）ｌ＋１ｙ（ｉ、ｊ）−ｙ（ｉ＋ｌ、ｊ）
　ｌ＋＋　　１ｘ（ｉ、ｊ）−ｘ（ｉ、ｊ−１）ｌ＋１
ｙ（ｉ、ｊ）−ｙ（Ｌｊ−１）ｌ＋＋　１ｘ（ｉ、ｊ）
−ｘ（ｉ、ｊ＋１）ｌ＋１ｙ（ｉ、ｊ）−ｙ（ｉ、ｊ＋
ＩＮ）（２，７） で表される。この場合、１ｘ（ｉ、ｊ）またはｙ（ｉ、
ｊ）などは、ブロックＢ　（ｍ、ｎ）のなかのすべての
画素ｂ（ｉ、ｊ）に同一の運動ベクトルＸ１６　（ｍ、
ｎ）が割り当てられることにより運動ベクトル場Ｘ１６
　（ｍ、ｎ）から生ずる運動ベクトルＸ（ｉ、ｊ）の構
成要素である：Ｘ（ｉ、ｊ）　＝　（ｘ（ｉ、ｊ）、ｙ
（ｉ、Ｄ　）　＝　Ｘ１６（ｍ、ｎ）Ｂ　Ｃｍ、ｎ）の
なかのｂ（ｉ、ｊ）の場合Ｘ（Ｌｊ）　＝　（ｘ（ｉ、
ｊ）、ｙ（ｉ、Ｄ　〕＝　Ｘ１６（ｎ＋、ｎ）　　（２
，８）運動ベクトル場は続いて、運動ベクトル場が均等
と仮定されるブロックの大きさが半減されることにより
、さらに最適化される。すなわち、目的関数Ｚがさらに
最小化される。

１６Ｘ１６画素から８×８画素へのブロック　割Ａ五二
旦Ｚｌと １６ブロツクに対する所与の運動ベクトル場〔Ｘ１６　
（ｍ、ｎ））から８ブロツクＢ８　（ｐ、ｑ）に対する
新しい場（Ｘ８　（ｐ、ｑ））が作成される。この新し
い場は運動ベクトル Ｘ８（ｐ、ｑ＞　−（ｘ８（ｐ、ｑ）、ν８（ｐ、ｑ）
　〕（３，１）から成っている。そのためにすべての１
６ブロツクが各４つの８ブロツクに分割され、また部分
ブロックの各々は先ず同一の運動ベクトル、すなわち１
６ブロツクの運動ベクトルを割り当てられる。

この新しい運動ベクトル場はすぐ次の緩和ステップに対
するプリセットとしての役割をする。

このステップは、目的関数に対する式のなかで１６’が
８′”により置換されていることを除いて、前記のよう
なブロック大きさ１６に対する緩和ステップにまさに相
応する。すなわち目的関数ＤＢ’　　（ｐ、ｑ、ｒ、ｓ
）が式２．１中のように平滑性尺度Ｐａ’　　（ｐ、ｑ
、ｒ、ｓ）を含んでいる式２．２によるＤ１６“　（ｍ
、ｎ、ｒ、ｓ）に相応して最小化される。ここでα（弐
２．１参照）に対してはブロック大きさ１６の場合と同
一の値が使用される。

１６ｘ１６画素から８×８画素へのブロック分割の場合
のように、いま大きさ８×８のブロックに対して探索さ
れた運動ベクトルが４×４画素を有する各４つのブロッ
クに分配される。

このステップはブロック大きさ１６および８に対する緩
和ステップにまさに相応する。

°°ブロック分割”および“緩和”ステップはブロック
大きさｌ×１まで継続され得る。しかし７、多くの応用
に対して、４×４画素ごとに１つの運動ベクトルを有す
る運動ベクトル場の分解能が十分である。

一般的なブロック回路図 第８図には、前記の運動ベクトル探索法を原理的に実行
し得る装置がブロック回路図で示されている。

２つの入力像ＡおよびＢから出発して運動ベクトル場の
一連の変更中に目的関数Ｚのそのつどの埴の考慮のもと
に最終的な運動ベクトル場が決定される。

！　　のための゛φベクトル“索（） 前記の方法は像内挿のための運動ベクトル場の探索のた
めにも使用され得る。そのために°“変位されたフレー
ム差”を測定する量、すなわちＤ１６　（ｍ、　　ｎ、
　　ｒ、　　ｓ）および大きさＢＸ８および４×４のブ
ロックに対する相応の量のみが若干変更されなければな
らない。

たとえば所与の像ＡおよびＢの間にまさに１つの中間像
が運動適応性の内挿により、動かされた像が内挿された
像のなかでまさに像Ａから像Ｂへのシフトの半分だけさ
らに動いたように挿入されるべきであれば、式１．６の
なかのＤ１６　（ｍ、ｎ。

ｒ、ｓ）の代わりに新しい大きさＤ１６ｉ（ｍ。

ｎ、ｒ、ｓ）が生ずる。その際にｉは内挿を示す：Ｄ１
６ｉ（ｍｔｎ、ｒ＋ｓ）＝ｓｕｍ　　　　　ａｂｓ　（
ｄ’（ｉ、ｊ、ｒ、５））ｔ、ｊｉｎ　Ｂ（ｍ、ｎ）　
　　　　　　（７，１）ここで ｄ’　（ｉ＋　ｊ　、　ｒ、　５）＝ｂ　（ｉ　−ｒ／
２．　ｊ　−ｓ／２）　−ａ　（ｉ＋ｒ／２．　ｊ＋ｓ
／２）（７，２） すなわち、いま運動ベクトル（ｒ、　　ｓ）は完全には
像Ａに応用されず、像Ａに半分だけ、また反転された符
号で像Ｂに応用され、従って全体として像ＡおよびＢは
再び全運動ベクトル（ｒ、ｓ）だけ互いにずらされてい
る。

同様のことが、２よりも高い係数だけの内挿にも、すな
わち２つまたはそれ以上の像が所与の像ＡおよびＢの間
に挿入されるべき場合にも当てはまる。一般的に、Ｑ＜
ｔ＜１として、像Ａにはシフト（ｒｘｒ、ｔｘｓ）が、
また像Ｂにはシフト（（ｔ−１）Ｘｒ、（ｔ−１）Ｘｓ
）が応用される。

シフトが整数の画素座標に通じない場合には、丸めが必
要である。

翌 運動像符号化法では運動ベクトル探索が２つの目的で使
用される： １）送信器および受信器における運動補償された予測、 ２）受信器における欠落像の運動適応性の内挿。

この場合、送信側では、運動ベクトル探索が運動補償さ
れた予測のための運動ベクトルを探索するために必要で
ある。これらの運動ベクトルは伝達されなければならな
いので、ここで運動ベクトル場を任意に細分化すること
はできない、しかし、これらの運動ベクトルは、予め伝
達された運動ベクトル場および受信側に存在する伝達さ
れた像から１つの細分化された運動ベクトル場が得られ
るならば、受信器において予測用に追加して運動補償さ
れた内挿用に使用され得る。

従って、像シーケンス符号化での応用のためには、前記
の多段の方法（第１図参照）がステップ“ブロック大き
さ１６Ｘ１６を有する初期化°°および“ブロック大き
さ１６を有する内挿が送信側で行われ、またその他のス
テップ（“ブロック分割”および８および４ブロツクに
対する“反復”）が受信側で行われるように、使用され
得る（第９図参照）。

シミュレーション実験により、実際に送信側で運動補償
された予測に対して得られた運動ベクトル場が内挿の目
的で受信器側の細分化に対する所与として適しているこ
とが判明しており、その際に送信側では式１．６からの
“変位されたフレーム差″Ｄ１６　（ｍ、ｎ、ｒ、ｓ）
が、また受信器側では内挿に適合させられた関数Ｄ１６
ｉ　　（ｍ、ｎ。

ｒ、　　ｓ）　　（式７．１．７．２）またはより小さ
いブロックに対する相応の関数が使用される。

前記の運動ベクトル探索の過程は第４図ないし第７図に
示されているフローダイアグラムから明らかにされる。

第４図には、先ず最大のブロック大きさＬ−Ｌｌｌｌａ
Ｘによりベクトル場の初期化（ＩＮＩＴ）が行われ、そ
れに続いてＬ□。ないしＬ　５ｈｉｎのすべてのブロッ
ク大きさ（それぞれブロックの辺の長さしが２等分され
る）に対して反復改善（ＩＴＥＲ）が行われる方法の全
過程が示されている。所与のブロック大きさしにおける
反復改善（ＩＴＥＲ）は第５図に示されている。ここで
、すべてのブロックＢ　（ｍ、ｎ）に対して、変更され
た平滑性尺度により目的関数を最小化する運動ベクトル
が探索される。

反復改善（ＩＴＥＲ）は第６図によるフローダイアグラ
ムに従って行われる。ここに、そのつどのブロック大き
さＬを有する各ブロックＢ　（ｍ。

ｎ）に対して、ブロックがなお処理されるべきか、すな
わちＦ　ｌＮｌ５Ｈ（ｍ、ｎ）＝Ｏか、または既に目的
関数の局部的最適（すなわち最小）に位置するか、すな
わちＦＴＮＩＳＨ（ｍ、ｎ）＝１かを示すロギング領域
Ｆ　ｌＮｌ５Ｈ（ｍ、ｎ）が存在する。先ずすべてのブ
ロックに対する領域ＦＩＮＩＳＨが零にセットされる。

それに続くループのなかでそれぞれまだ“ＦＩＮＩＳＨ
”でないすべてのブロックに対して、目的関数の最小が
特定の値範囲のなかで探索される（ＯＰＴＩ）（第７図
参照）。すべてのこれらのブロックに対してＦ　ｒＮＩ
ｓＨ（ｍ、ｎ）−１がセットされる。最小探索の際にブ
ロックの運動ベクトルが変化した場合には、近傍ブロッ
クに対して、これらが再度処理されるように、領域ＦＩ
ＮＩＳＨが零にセットされる。すべてのブロックが値Ｆ
ＩＮＩＳＨ（ｍ、ｎ）＝１を有するならば、反復過程は
終了している。

ＩＴＥＲのなかで実行される最適化ステップ（ＯＰＴｒ
）の過程は第７図に示されている。

要約して確認すべきこととして、ブロックの分割はそれ
ぞれブロックの辺の長さの２等分により行われる０両像
の間に１つの中間像を挿入する際に、この中間像の各画
素に２つの画素、すなわち第１の像からの１つの画素お
よび第２の像からの１つの画素が対応付けられる。画素
の１つのブロックのなかの相続く両像の互いに相応する
画素の輝度値の差が輝度値の差の絶対値の和により評価
され、また最小化すべき目的関数のなかで加数として使
用され、その際にこの加数が目的関数の第１の構成要素
を形成する。画素の１つのブロックのなかの相続く両像
の互いに相応する画素の輝度値の差が輝度値の差の二乗
の和により評価され、また最小化すべき目的関数のなか
で加数として使用され、その際にこの加数が目的関数の
第１の構成要素を形成する。

本発明による方法では、さらに、近傍運動ベクトルの間
の差がこれらの差の絶対値ノルムにより表され、その際
にこれらの絶対値ノルムの和が目的関数の第２の構成要
素を形成し、また平滑性尺度として使用される。両構成
要素の少なくとも１つが重み係数により乗算され、また
相応の積が加算により目的関数を形成し、その際に目的
関数が特にＺ−２１＋αＺ２（ここで２１は第１の構成
要素、Ｚ２は第２の構成要素、またαは重み係数）の形
式を有する。

各運動ベクトルの近傍運動ベクトルとして、好ましい実
施例では、水平および垂直に当該の運動ベクトルの座標
と隣り合う座標、すなわち当該の運動ベクトルの座標か
ら（０，１）、（０，−１）、（１，０）または（−１
，０）だけ異なる座標に位置する４つの近傍運動ベクト
ルのみが使用される。

大きいブロック、特に１６Ｘ１６画素を有する運動ベク
トル場の初期化の際に、すなわちまだ各ブロックに対し
て少な（とも既に１回１つの運動ベクトルが計算されな
かったかぎりは、平滑性尺度が、近傍運動ベクトルの間
の差の代わりに、最適化すべき運動ベクトルの絶対値ノ
ルムが、重み係数により乗算されて、目的関数のなかで
平滑性尺度により使用されるように変更される。

ブロック分割の各ステップで、すなわち最大のブロック
大きさにおける開始時に、またそれに基づいて特に４×
４画素のブロック大きさまで行われる各ブロック分割の
後に、運動ベクトルに対してもはやこうして目的関数の
より小さい値が見出され得ないまでに、順番に各個の運
動ベクトルが変更により当該の値範囲のなかで最適化さ
れる。

目的関数を最小化するため個々の運動ベクトルが変更さ
れる運動ベクトルの値範囲が、既に計算された運動ベク
トル場のなかの運動ベクトルがどの値を存するかに関係
して決められ、従って運動ベクトル場の最適化に対する
値範囲は、近傍運動ベクトルが等しい場合またはｌ１ｆ
Ｈしている場合には小さく、また近傍運動ベクトルが互
いに大きい差を有する場合にのみ大きい。

ロギングシステムにより、近傍運動ベクトルが当該の運
動ベクトルの最後の最適化以後に変化し、従って場合に
よっては平滑性尺度も変化した運動ベクトルのみが再度
目的関数の値の一可能な縮小を期待して最適化されるよ
うにされ、その際にロギングシステムが最適化経過に対
するコントロール情報を記憶するためブロックごとにメ
モリ場所を有するロギング場を含んでいる。

特定の運動ベクトルの最適化の際に当該の値範囲の各運
動ベクトルではなく運動ベクトルの部分集合のみが予め
定められたプランに従って考慮される。

計算すべき運動ベクトル場のなかの近傍運動ベクトルの
間の差に追加して、現在の運動ベクトル場の運動ベクト
ルと直前に相続く像の先行の対から計算された運動ベク
トル場の運動ベクトルとの間の差も探索され、また時間
軸方向の運動ベクトル場の平滑化の目的で、すなわち相
続く運動ベクトル場の同化のために平滑性尺度のなかに
使用される。

本発明による方法は、データ圧縮によりコーダーからチ
ャネルを経てデコーダーに伝達された各２つの相続く像
から運動ベクトル場が中間像の挿入の目的で探索される
場合にも、本方法の初期化のために、既に以前に伝達さ
れている相応の運動ベクトル場が使用されるように応用
され得る。

以下には、好ましいプログラム例に対して本発明による
全過程に関する完全なプログラムリストがプログラミン
グ言語ＦＯＲＴＲＡＮで示されている。

Ｕ　　　　　　　　　　　　０ ＋ （Ｊ（ＪＣＪ（ＪＬ）（Ｊ（Ｊ　　　（Ｊ（Ｊ（Ｊ（Ｊ
（Ｊ（ＪＵ　　　　　　　　　　　　　　　　　　　　
　　　　　　ＵＵｕ　　　　　　　　　ｕ　　　　　　
　ｕ　　　　　　ｕ　　　　　　　ｕＵ　　　　　　　
　Ｕ　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　Ｑ寝 ｔ く　　； コ　　（ ）　　Ｃ −コ 一　　　　　　　　　　　　　　　　　　−−＾＾　４
　　ＮＮＮＩＮ→　　　　　　　８　　　　　　　　　
　　　　　　　　　　・−＼＼閲頓　　喫ｈ　　　　口
＾＾　　　　　　　　　　關ωＮ凶　喫　区匡匡−１＋
−閲　　Ｈ沁ｃＩ３凶　　　　　　　　　　　　　　　
トドベ２２　　４１　　　薗闇閲田ｔａｍｔｑ−コ　　
　　　　　　　ＺＺ−−４１ｏｏｔｐ。

コーＸＸ　４１　　關闇閲閲 ５　：コ　クコ巾　　−−ｚ＞＞ｚｚ　　タ　２２：２
２ＸＮφ（Ｑ４Ｅ−１トトト →　　の　ψ（１）ｌ／）−鴎２　　コ　　り切−一　
愼　１−１１−１１−１１−１フ　　　−２０２２１７
１ｋｌ　〈ｗｏｈｚｚυＵ　　　（Ｃ−−Ｘｌ−ｊ−−
り−ＺＮＺ　　ｐｃＪ　　−１ｉＥ’ｒ、　　喫υ　　
　ｔｏ　　　　　　　　　　　ｕ　　　　　　　　ｕｌ
　　　　　　　　　υ　　　　　　　　　　　　　　　
　　　　　　Ｑり 闇 ０　　　　　　　　　　　　　　　　　　　　　　　　
＋　　　　　　　＋＋＋＋匡 Ｌｌ　　　　　　　　　　　　　　　　　　　　　ｗ（
Ｊ　　　　　　　　　　　　　　　　　　　　　１４）
ト 〉 Ｕ　　　　　　　　　電　　　　　　　　　　　　　Ｖ
すｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕ
ｕｕｕｕｕｕｕｕｕｕ關 コ 〇 ； 一 ｕ　　　　　　ｕ　　　　　　　　　　　　　　ψφ　
　　　　　　　　　　＋＋　　　　　＋＋＋　　　　　
　　　　　＋＋菌 Ｌｌ（Ｊ　　　（Ｊ（Ｊ（ＪＣＪ（ＪＣＪＬＩＣＪ（Ｊ
（Ｊｕ（Ｊ　　　　　　　　ｗｗｗｗ−ｎ薗 ０の 　ｔＯ Ｕ　　　　　　　　　　　　　　　０ 閲 閃 ト 閃 〉 ％ＯＣＪＩＪ（ＪＬＪ（ＪＬＩ（Ｊ ＬＩＬＩ　　　　　　　　　　　υυυＵＵυυ０υＵ
υυυυ・　　　　　菌 Ｏり ｕｕｕｕｕｕｕｕｕｕυυＵ０υ ｕ　　　　　　　ｇ　　　　　　　　　　ｕ　　　　　
　　　　　　　　　　　ｕＱ　　　　　　　　　　　　
　　　υ （ＪＣＪ　　　　　　　　　　ｕｕｕｕｕｕｕｕｕｕｕ
ｕｕｕｕｕｕｕｕｕｕｕｕｕｕｔノｕｕｕｕｕｕ　　　
　　　　　　　　　　　　　　　　　　　　　　　　ｕ
υ 国 〉 Ｑ　　　　　　　　　　　　　　　　　　ＮＮ口　　　
　　　　　　　　　　　　　ｌＮｉω Ｌｌ　　　　　　　　　　　　　　　　　　　　　　　
　　　　　（Ｊ　　　　　　　　　　ｃＪｏ　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　Ｕ　　　　　υ＋＋− コ 一　　　　ベ ψυ ｕ　　　　　　　　　　　ｕ　　　　　　　　　ｕ　　
　　　　　　　　　　　ｕ　　　　　　　　　ｕ　ｕ　
ｕ　（Ｊ　（Ｊ　ＣＪＣＪ　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　０Ｕ　　　　　　　　　０　　　
　　　０ω　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　＾（Ｊ
　　　　　　　　　　　　　ｕ　　　　　　　　　　　
　　　　　　　　　（Ｊψ ベ ロ　　　　　＋　　　　　　　　　十＋り η ≦ コ ベ （Ｊ　　　　　　　　　　　　　　　　　　　　　　　
　　　　ｖｏ　　　　　　　　　％ＯＩＪｙ目Ｊ（Ｊ　
　　　　　ｇ　　　　　　　　ｕ　　　　　υＵ　　　
　　　ｕ 、、４≦６≦耘魁二：：　　ｏ　　；：：　　：　　　
　　　Ｅ　　　　　　　ごｕｕ　　　　　ｕｕｕｕｕｕ
ｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕＣＪＣＪ（ＪＩＪＬ
）リ　ｕｕｕｕｕｕυｕｕｕｕｕｕυｕｕ　　ｕｕｕｕ
　　ｕｕｕｕｕｕｕｕｕｕ ＵすＶリリリ　　　　　　　　　　　　　　　リリ　Ｖ
υ０υＱ０υ（ＪＬ）ＣＪ（Ｊ（ＪＣＪＬ）（Ｊ（ＪＬ
）ＣＪυＱ０（ＪＬＩ　　　ＣＪＬＩＬＩＣＪＵＬＩ（
Ｊ（ＪＬｌｕ（ＪＬＩ（ＪＬＩ（ノ（Ｊ（Ｊ（Ｊ（Ｊ（
Ｊ ト ＋　＋　＋　　　　　　り ｒｑ、−＋ｕｕ　　　ＬＩＣＪＬ’ＣＪ　　ｖ）ｕへＵ
、　ＬＩ　Ｌ／　Ｑ　ＣＪ　ＣＪ　ＣＪ　（Ｊ　ＣＪ　
（Ｊ　ＣＪ　（Ｊ　（Ｊ　（Ｊ　（Ｊ　Ｕ　ｕ　Ｕ　（
Ｊ　（Ｊ　（Ｊ　ＣＪ　（i　（Ｊ　（Ｊ　Ｌ ノｕｕｕｕｕｕｕｕ　　　　　　　　　　　　　　　ｕ
　　　　　　　　　　　　　　　υ日 閲 υ ロ　　　　　　　　　　　　　　　　　　　＾−＾ ｕｕｕｕｕｕｕｕｕｕｕυ（Ｊ（Ｊ　　　　　　　　　
Ｌｌｕ　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　ｕｕ　　　　　　　ｕｕｕｃ、
＋ｃ、＋ｕｕｕｕｕｕｒ、、＋ｕｕｕｕｕｕｕｕｕυＬ
）Ｌｌ　　　　　　　　　　　　　υ　　　　　　　　
υＱ　　　　　　　　　　　　　　　　　　　　　　　
ｕ　　　　　　　ｕｔ、、＋　　　　　　　　　　　　
　　　　　　　　　　　　　ｕｕ　　　　　　ｕｕｕｕ
ｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕ　　　　　　　　　
　　ｕ−国 一く ｕ　　　　　　　　　　　　　　　　　ｕｕ　　　　ｕ
ｕｕｃ）ＩＪｔＪＬ）ｔ）ＣＪｔＪＣＪＣＪｔＪＣＪＣ
ＪＣＪυＬｌ＋、、、Ｌ／ｌＪロ　　　　セ ４喫 ｃＱり ｕｕ　ｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕｕ

【図面の簡単な説明】

第１図は最終的なブロック大きさ４×４および開始ブロ
ック大きさ１６Ｘ１６に対する運動ベクトル探索法の過
程の概要図、第２図はブロック分割の仕方を示す概要図
、第３図は４つの近傍ブロックの運動ベクトルを有する
運動ベクトルＸ１６（ｍ、ｎ）の概要図、第４図は本方
法の全過程のフローダイアダラム、第５図は本方法の初
期化の過程を示す第１のサブフローダイアグラム、第６
図は本方法のなかの反復の過程を示す第２のサブフロー
ダイアグラム、第７図は本方法のなかの最適化の過程を
示す第３のサブフローダイアグラム、第８図は運動ベク
トル探索法をブロック図状に示す図、第９図は本発明に
よる方法を実施するための装置を含んでいる像シーケン
ス伝達装置のブロック回路図である。 ＩＧ　Ｉ ＩＧ２ ＩＧ３ ＦＩＧ６　　　　　　　　　ＦＩＧ７ 手　続　ネ甫　正　書（方式） ２１発明の名称　　ディジタル像シーケンスからの運動
ベクトル場の探索方決 ３６補正をする者 事件との関係　　特許出願人 住　所　ドイツ連邦共和国ベルリン及ミュンヘン（番地
なし） 名　称　シーメンス、アクチェンゲゼルシャフト４、代
理人■１１２ 住　所　東京都文京区大塚４−１６−１２る（内容に変
更なし）。

Claims (1)

1. 【特許請求の範囲】 １）ディジタル像シーケンスから運動ベクトル場を探索
   するための方法であって、それぞれ２つの相続く像から
   、一方の像の各画素に他方の像の画素を対応付ける連動
   ベクトル場が探索され、その対応付けは、互いに相対的
   な画素のシフトを表すそれぞれ１つの運動ベクトルによ
   り定められており、また正方形または長方形ブロックの
   なかのそれぞれすべての画素は等しい運動ベクトルを保
   持する方法において、運動ベクトル（Ｘ（ｍ、ｎ））の
   探索が、一方では２つの与えられた像の互いに対応付け
   られる画素の輝度値の差を考慮し、他方では座標が隣り
   合っている運動ベクトル、すなわちいわゆる近傍運動ベ
   クトルの間の差を平滑性尺度（Ｐ）により評価する合成
   された目的関数（Ｚ）の最小化により行われ、またこの
   目的関数の最小化が、先ず目的関数を最小化する運動ベ
   クトルが運動ベクトルが最終的に得ようと努められるブ
   ロックよりも大きいブロックのなかでは一定であるとい
   う制限のもとに探索され、続いてこれらのブロック（１
   ６×１６）の各々が、得ようと努められるブロックの大
   きさ（４×４）が到達されるまで、より小さい、好まし
   くは等大のブロックに分割されるように行われ、ブロッ
   クの各縮小の後に再び目的関数が運動ベクトルの変化に
   より最小化されることを特徴とするディジタル像シーケ
   ンスからの運動ベクトル場の探索方法。 ２）ブロックの分割がそれぞれブロックの辺の長さの２
   等分により行われることを特徴とする請求項１記載の方
   法。 ３）両像の間に１つの中間像を挿入する際に、この中間
   像の各画素に２つの画素、すなわち第１の像からの１つ
   の画素および第２の像からの１つの画素が対応付けられ
   ることを特徴とする請求項１記載の方法。 ４）画素の１つのブロックのなかの相続く両像の互いに
   相応する画素の輝度値の差が輝度値の差の絶対値の和に
   より評価され、また最小化すべき目的関数のなかで加数
   として使用され、この加数が目的関数の第１の構成要素
   を形成することを特徴とする請求項１記載の方法。 ５）画素の１つのブロックのなかの相続く両像の互いに
   相応する画素の輝度値の差が輝度値の差の二乗の和によ
   り評価され、また最小化すべき目的関数のなかで加数と
   して使用され、この加数が目的関数の第１の構成要素を
   形成することを特徴とする請求項１記載の方法。 ６）近傍運動ベクトルの間の差がこれらの差の絶対値ノ
   ルムにより表され、これらの絶対値ノルムの和が目的関
   数の第２の構成要素を形成し、また平滑性尺度として使
   用されることを特徴とする請求項４または５記載の方法
   。 ７）両構成要素の少なくとも１つが重み係数により乗算
   され、また相応の積が加算により目的関数を形成し、そ
   の目的関数が特にＺ＝Ｚ１＋αＺ２（ここでＺ１は第１
   の構成要素、Ｚ２は第２の構成要素、またαは重み係数
   ）の形式を有することを特徴とする請求項６記載の方法
   。 ８）各運動ベクトルの近傍運動ベクトルとして、水平お
   よび垂直に当該の運動ベクトルの座標と隣り合う座標、
   すなわち当該の運動ベクトルの座標から（０、１）、（
   ０、−１）、（１、０）または（−１、０）だけ異なる
   座標に位置する４つの近傍運動ベクトルのみが使用され
   ることを特徴とする請求項６記載の方法。 ９）大きいブロック、特に１６×１６画素を有する運動
   ベクトル場の初期化の際に、すなわちまだ各ブロックに
   対して少なくとも既に１回１つの運動ベクトルが計算さ
   れなかったかぎりは、平滑性尺度が、近傍運動ベクトル
   の間の差の代わりに、最適化すべき運動ベクトルの絶対
   値ノルムが、重み係数により乗算されて、目的関数のな
   かで平滑性尺度により使用されるように変更されること
   を特徴とする請求項６記載の方法。 １０）ブロック分割の各ステップで、すなわち最大のブ
   ロック大きさにおける開始時に、またそれに基づいて特
   に４×４画素のブロック大きさまで行われる各ブロック
   分割の後に、運動ベクトルに対してもはやこうして目的
   関数のより小さい値が見出され得ないまでに、順番に各
   個の運動ベクトルが変更により当該の値範囲のなかで最
   適化されることを特徴とする請求項２記載の方法。 １１）目的関数を最小化するため個々の運動ベクトルが
   変更される運動ベクトルの値範囲が、既に計算された運
   動ベクトル場のなかの運動ベクトルがどの値を有するか
   に関係して決められ、従って運動ベクトル場の最適化に
   対する値範囲は、近傍運動ベクトルが等しい場合または
   類似している場合には小さく、また近傍運動ベクトルが
   互いに大きい差を有する場合にのみ大きいことを特徴と
   する請求項１ないし１０の１つに記載の方法。 １２）ロギングシステムにより、近傍運動ベクトルが当
   該の運動ベクトルの最後の最適化以後に変化し、従って
   場合によっては平滑性尺度も変化した運動ベクトルのみ
   が再度目的関数の値の可能な縮小を期待して最通化され
   るようにされ、その際にロギングシステムが最適化経過
   に対するコントロール情報を記憶するためブロックごと
   に１つのメモリ場所を有するロギング場を含んでいるこ
   とを特徴とする請求項１ないし１１の１つに記載の方法
   。 １３）特定の運動ベクトルの最適化の際に当該の値範囲
   の各運動ベクトルではなく運動ベクトルの部分集合のみ
   が予め定められたプランに従って考慮されることを特徴
   とする請求項１１または１２記載の方法。 １４）計算すべき運動ベクトル場のなかの近傍運動ベク
   トルの間の差に追加して、現在の連動ベクトル場と直前
   に相続く像の先行の対から計算された運動ベクトル場と
   間の差も探索され、また時間軸方向の運動ベクトル場の
   平滑化の目的で、すなわち相続く運動ベクトル場の同化
   のために平滑性尺度のなかに使用されることを特徴とす
   る請求項１または６記載の方法。 １５）データ圧縮によりコーダーからチャネルを経てデ
   コーダーに伝達された各２つの相続く像から運動ベクト
   ル場が中間像の挿入の目的で探索される方法であって、
   方法の初期化のために、既に以前に伝達されている相応
   の運動ベクトル場が使用されることを特徴とする請求項
   １ないし１４の１つに記載の方法。