JPH04500423A - 画像の動きフィールドをセグメント化する方法および画像エンコード方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 画像の動きフィールドをセグメント化する方法およびビデオ画像のコード化への その応用本発明はビデオ画像の、特にデコード補助ディジタルデータをＩＭビッ ト／Ｓに等しいスルーブツトをもって付加しうる伝送チャンネルを介しての高解 像度画像の伝送のための、エンコード／デコードの分野に関する。本発明の目的 は特に画像のビンポイント的動きフィールドを、それをＩＭとット／Ｓの限界ま でエンコードするためにセグメント化する方法およびビデオ画像のエンコードへ のその応用である。

ディジタルビデオ画像を伝送するための最も有効な現在の方法は伝送されるライ ン伝送速度の低下を可能にする処理を伝送の前に行う方法である。このように、 例えばビクセルのすべてに関係する情報（クロミナンス、輝度）のすべてを送る のではなく、この処理方法は画像間の差、特に画素すなわちビクセルのずれを見 い出しそして画像を更新するための情報、すなわち画像間のそのゾーンまたはビ クセルのずれを特徴づけるベクトルを送ることを可能にする。有効な処理方法は ポイント毎に一つの動きベクトルをつくりそしてこの動きフィールドを伝送する ことから成る。

１　Ｍビット／Ｓの伝送速度はビデオ画像のポイント的動きのフィールドの完全 な伝送を行うには低すぎる。従って、画像の最高の再生を得るように伝送される 動きフィールドに関係する情報を注意深く選ぶ必要があり、伝送される情報のデ コードは前の画像と、現在の画像に関連した動きフィールドとにより行われる。

ポイント状動きエステイメータ（ｅｓｔ！ｌ１ａｔｏｒ）から生じる動きフィー ルドの処理のための第一の構成はｎＸｎ個のビクセス（ｎは常に２のべき数）ブ ロック当り一個の動きベクトルを伝送することである。ライン当り１４４０ポイ ントの高精度グリッドそしてライン数１１５２本から、結果としての伝送速度は ８，８ブロツクについて１．３Ｍブロックである。

伝送速度を上記の伝送速度（ＩＭビット／ｓ）より低く保ちつつこのエンコード を最適にするために「カッド−ツリー（’ｑｕａｄ−１ｒｅｅ）　Ｊと呼ばれる エンコード法が有効であることが証明されている。この方法は異なったサイズの ブロックを使用しそしてブロック伝送速度を低下させることを可能にする。この ため、問題はブロックのセットに最も均一なポイント状の動きフィールドをもど すことになる。

従って、ポイント状の動きフィールドの全体のヒストグラムを構成することが可 能となる。頭初からこの手順は大域形であり、処理されるべきデータ量は大きい 。更に、次にｎＸｎ個のブロックの夫々に一つのベクトルを割当てるために、ヒ ストグラムからドミナントすなわち優勢と確認される各ベクトルはそのブロック に最適のベクトルを選ぶようにｎ、ｎブロックの動きベクトルのすべてと比較し なければならな−・。このセグメレト［Ｌ法はそれ故複雑で時間のかかるもので ある。

本発明の主題はエンコード後に送信される「優勢」ベクトルの、「カッド−ツリ ー」エンコードによる次の処理に適したように抽出することを可能にする動きエ ステイメータによって得られる動きフィールドをセグメント化する方法である。

このため、本発明のセグメント化方法はまず各ｎ、ｎブロックにブロックに対し て使用可能な動きベクトル群またはセットを割当てるために動きフィールドにつ いて局所的な処理を行うことからなる。次に入城処理が、すでに減少した数のベ クトルを含み且つポイント形の動きフィールドから得られる最良の動きフィール ドブロックと考えることの出来るｎ、ｎブロック形ベクトルフィールドからの一 セットの優勢ベクトルの抽出を可能にする。

優勢ベクトル抽出後のｎ、ｎブロックベクトルの再割当て相はかくして容易とな る。

更に、本発明の方法を行うためにｎ、ｎブロック動きフィールドを直接に考慮す ることさえ可能である。

また本発明の主題はこのセグメント化方法のビデオ画像の「カッド−ツリー」エ ンコードへの適用である。

本発明によれば、画像面内に２つの成分をもつベクトルの形で前の画像に対する その後の画像のピクセルのずれを与える動きエステイメータからの動きフィール ドのとグメレ：・ｒ上方法は次の点を含むことを特徴とする。

−画像をｎ、ｎピクセルのブロックに区分けしそして各ブロックにつき多数決に より可能なベクトルから選ばれた一つの動きベクトルを割当ての予備相。

−ブロック形動きベクトルのヒストグラムをセットアツプする相。この相の終了 時に動きベクトルの分類がそれらの発生回数に従って行われる。

−各ブロックについて一つの動きベクトルを再割当てする相。このベクトルはヒ ストグラムから選択された限られた数Ｎの優勢ベクトルから選ばれそしてこれら 優勢ベクトルからそのブロックの初期ベクトルに最も近いベクトルである。

−隣接するブロックとはインコヒーレント（１ｎｅｏｈｅｒ−ｅｎｔ）な動きベ クトルを有する独立したブロックのベクトルをフィルタリングする相。

−結果としてのフィルタリングされた動きフィールドのエンコードに必要な伝送 速度を計算しそして、この伝送速度が最大可能伝送速度以下であることを検査す る相。

より少数の優勢ベクトルからのブロックの夫々についての一つの動きベクトルの 再割当て相は伝送速度が最大可能伝送速度より大のときに再び行われる。

本発明は添付図面についての以降の説明でより明らかとなるものである。

−図１は２つの連続する画像間の１個のピクセルの動きベクトルを例示する図で ある。

−図２は高精度画像および本発明によるセグメント化方法の実行のためその区分 けを例示する図である。

−図３は素ブロックについての動きベクトルおよびそれからブロックベクトルの 割振りを生じさせるヒストグラムテーブルの成分のテーブルの形成を例示する図 である。

−図４はブロックベクトルの割振り後のフィルタリング相を例示する図である。

−図５は４分の１の画像についてフィルタリングされた動きブロックフィールド のベクトルのヒストグラムの形成を例示する図である。

−図６は動きの分類によるベクトルの抽出相を例示する図である。

−図７は２次最大値の除去後の優勢ベクトルテーブルを例示する図である。

−図８は連続する画像の対応部分において優勢ベクトルを考慮する時間−フィル タリング相を例示する図である。

−図９および図１０は夫々、１６Ｘ１６個の素ブロックからなるマクロブロック 内の均一ベクトルゾーンと対応するエンコードツリーを示す図である。

−図１１は本発明によるポイント状の動きフィールドをセグメント化する方法の フローチャートである。

前述のように、このセグメント化方法は動きエステイメータにより与えられるポ イント状動きフィールドに特に適用する。ポイント状動きエステイメータは分析 されているビデオ画像の各ポイントについて現在の画像とその前の画像との間の ピクセルのずれを特徴づける動きベクトルＶを与えることは前述した。それ故こ のベクトルは画像面のＸおよびｙ座標軸において成分Ｖ　とＶ　をｙ 有する。

図１は動きベクトルおよびその画像の成分を示しており、画像Ｉ　のポイントＰ は後の画像Ｉ２のＰ′となる。

本発明による点の動きフィールドからのセグメント方法は次のように行われる。

第１相はｎ、ｎピクセルからなるブロック当りに一つの動きベクトルを割当てる ことからなる。図２は１４４０コラムおよび１１５２ラインからなる高密度画像 を示しており、エステイメータにより行われる動き予測法に従って、１ベクトル ／ポイントまたは１ラインの２点の内の１点（Ｏｎｅ　ｐｏｉｎｔ　ｊｎ　ｔｖ Ｏｏｆａ　１ｉｎｅ）につき１ベクトル（そのとき前のラインのベクトルと千鳥 形となる点に対応する次のラインについて計算されたベクトル）により構成され る一つの動きフィールドが使用可能である。この第１相はそのブロックの６４個 （または３２個）のベクトルの内の１個をｎ、ｎ　（８，８）ポイントからなる ブロックに属させることからなり、このベクトルは多数決によりそのブロックの ベクトルとして選ばれる。このため、各ブロックの動きベクトルの成分Ｖ　とＶ 　は、図３に示すようにＸ成分をテーブルｙ ＴＡＢＸ％Ｙ成分をテーブルＴＡＢＹとしてブロックの寸法と共にテーブル内に ランクづけされる。このように、例えばテーブルＴＡＢＸにおいて、ｋ番目のコ ラムおよび１番目のラインに対応する位置の値ＴＡＢＸ　（ｋ、Ｉ）はブロック のライン１のランクにのビクセルの成分Ｖ８である。ブロックＶ（ｋ、ｌ）のベ クトルについては次の操作がこのベクトルの成分とブロックＶ（ｉ、ｊ）の他の ベクトルの成分との間のずれを決定するために行われる。ここで１と」はセット Ｃ１，ｎ〕を記述するものであり、 （１）　ＦＸ−ＩＴＡＢＸ　（ｋ、ｌ）　−ＴＡＢＸ　（ｉ、　ｊ）　１（２） 　ＦＹ−ＩＴＡＢＹ（ｋ、１）−ＴＡＢＹ（ｉ、ｊ）ｌこれら二つのテストはベ クトルＶ（ｋ、ｌ）とこのブロックのすべてのベクトルとの精度内での比較に対 応する。

ＦＸとＦＹがベクトルの精度（Ｌ／８−０．１２５ビクセル）に等しいしきい値 ８１以下であれば、ベクトルＶ（ｋ、１）の発生数は１だけ増加する。Ｖ（ｋ、 Ｉ）の発生数はＨＩＳＴＯ（ｋ、１）で示し、このテストが満足されるたびにＨ ＩＳＴＯ（ｋ、］）は更新される。

（３）　ＨＩＳＴＯ（ｋ、　ｌ）　−ＨＩＳＴＯ（ｋ、ｌ）　＋１、、’Ｖ’　 （Ｋ、１　ンと同様のベタ１ルの散逸も同様に更新される。

（４）　ＤＩＳＰ　（ｋ、１）−ＤＩＳＰ　（ｋ、＋）＋ＦＸ＋ＦＹこのブロッ クについての一つのベクトルの選択は最も発生回数の多い、そして発生回数か同 じであれば、散逸の最も少いベクトルをそのブロックのテーブルＴＡＢＸとＴＡ ＢＹから構成されるテーブルＨＩＳＴＯからとり出すことによりこれら比較の終 了時に行われる。テーブルＴＡＢＸとＴＡＢＹには例えばベクトルＶ　（６，５ ）の成分Ｖ　−２，１２５とＶ　−１，２５０，すなわち分ｙ 折中の現在の８．８ブロツクの５番目のラインの６番目のポイントの動きベクト ルを示している。

同様に例として、同様と考えられるベクトルの成分を含むテーブルＴＡＢＸとＴ ＡＢＹの位置（差ＦＸとＦＹは５ｌ−０，１２５より小さい）をＸ印で示しであ る。

結果として得られるテーブルＨＩＳＴＯには、このベクトルの発生回数であるＨ ＩＳＴＯ（５，６）を１６に等しいとして示している。この対応する散逸（ｄｌ ｓｐｅｒｓｉｏｎ）をＤＩＳＰ　（６，５）　−２，５で示す。

本発明による動きフィールドのセグメント化方法の第２相はブロックベクトルの 割振りにより得られる動きフィールドのフィルタリングである。このフィールド は現在の処理されるベクトルのまわりで隣接するブロックのベクトルを含む３． ３窓を与えることによりフィルタリングされる。この窓の中心ベクトルが８個の 隣接するベクトルと比較され、もしこのベクトルがこれら隣接ベクトルのすべて から離れていればそのベクトルがこれら隣接ベクトルの内の１個と置き換えられ る。

ベクトルＶ（Ｖ、Ｖ）は、ＸおよびＹに沿ったＶｘｙ とＶ′の成分の差の絶対値であるＦＸとＦＹが予定のしきい値Ｓ２より大のとき にはベクトルＶ’（Ｖ’、。

Ｖ′　）から離れているとする。Ｓ２は例えば０．５である。一つのベクトルが このようにそのすべての隣接ベクトルから離れているとき、それは［フィルタリ ングされた」、すなわち８個の隣接ブロックの内の、対応するテーブルＨＩＳＴ Ｏ（ｋ、１）内でフィルタリングされるべきブロックのポイント状ベクトル内で 発生回数が一番大きい１個、あるいは発生回数が等しいときには散逸の最も小さ いもので置き換えられるのであり、発生回数および散逸は前の相で述べたように フィルタリングされるべきブロックの夫々のベクトルについて計算されている。

図４はこのフィルタリング相を示す。図３に示すデープルを有し、フィルタリン グ相に関する処理中のブロックについて受け入れられた、ベクトルをベクトルＶ （６゜５）−（２，１２５，１，１２５０）であるとすると、この中央ブロック は８個の隣接ブロックで囲まれて（３，３）ブロックの窓を形成する。図示の例 ではこのベクトルはすべての隣接するものから離れていないから保持される（こ れは前のラインのブロックおよび同じラインの隣接するものに特に近い）。

次の相は動きフィールドのヒストグラムをつくることからなる。

ｎ、ｎポイントのブロックベクトルにより構成される動きフィールドに変換され ている高密度画像のポイント状動きフィールドのサイズは１４４０／ｎコラムと １１５２／ｎライン、すなわち８．８ブロツクについて１８０．１４４である。

１つのヒストグラムが１つの高密度画像象現について、すなわちサイズ（１４４ ０／２ｎ、１．１５２／２ｎ）の動きベクトルすなわち数値−１６と＋１６の間 に精度１／８−０．１２５ビクセルをもって含まれる成分を有する動きフィール ドのベクトルの夫々について、上記の例では９０．７２ブロツクについて行われ 、単純化のだめに各成分の１×８が行われ、これが整数成分を有する２５５．２ ５５の可能なベクトルを与える。

Ｖｘはセット［−１５，８７５，＋１５．８７５）に属し、従って８Ｖ　はセッ ト［−１２７，＋１２７）に属する。

一■　はセット［−１５，８７５，＋１５．８７５）に属し、従って８Ｖ　はで ストｌニー１２７．＋１２７）に属する。

フィルタリングされたポイント形動きフ、１−ルト′のヒストグラムをつくるた めに、すべての可能なずれ８Ｖｘと８Ｖ　を含む２次元テーブルが用いられる。

このチープルの中心位置はずれ０のベクトルに対応する。画像象現の動きベクト ルテーブルは分析され、そして、画像象現のブロックの夫々のずれベクトルにつ いてヒストグラムテーブルの対応する位置がこの実施例ではこの相においてヒス トグラムの拡大を行うように８個の隣接する位置と共に増加される。図５は一つ の画像象現についてのヒストグラムテーブルを示しそして、図４に示すベクトル Ｖ　（２，１２５，１，２５０）すなわち８Ｖ（１７゜１０）をもつ現在のブロ ックとなるときの更新の詳細を与えるものであり、図示のように隣接するものの 位置の増加を伴うものである。この図ではこれら位置は夫々座標で示されている 。それらの内容（図示せず）は連続する増加によりきまる。このヒストグラムの 構成後に、画像象現（９０，７２ブロツク）について、４にセット可能なしきい 値Ｓ３より大きい発生回数を有するすべてのベクトルがその発生により図６に示 す新しいテーブルに移される。それ故そのテーブルの各ラインは３個のゾーン、 すなわちベクトルの発生回数、そのＸ成分■　（または８Ｖ　）、およびそのｙ 成分Ｖ　（または８Ｖ　）ｘ　ｙ　ｙ を含む。発生数を減少させることによる分類がこのテーブルで行われる。

次の相は、ずれベクトルのＸ成分、ｙ成ニ〕および発生数を含む上記の相の終り に得られるテーブルから、各動きの「クラス」を表わすベクトルの抽出である。

このため、まずこの行われた分類におけるすなわちこのテーブル内のライン１に おける最大発生回数をもつベクトルと１より大きい指標を有するこのテーブル内 の他のすべてのベクトルとの比較が行われる。フィルタリングのコンテキストに おける近似評価中と同じしきい値であるＳ２（すなわち例えば５２−０．５）内 でそれに近いと考えられるものが除かれそしてこのテーブルの内容がそのギャッ プを埋めるべくシフトされる。

次に、このテーブル内で位置２にランクづけされるベクトルが分類後にこのテー ブルのすべてのベクトルについて第３位置等からランクづけされるベクトルに対 して検査される。図６では接近したベクトルを矢印で結んでいる。この相の終り にこれら矢印のスタート点にあるベクトルはこのテーブルから消える。この相の 終了時にこのテーブルに残る各ベクトルは動きベクトルの拡大されたクラスを表 わす。

次の相は２次最大値の除去である。発生回数の多いベクトルのまわりに、接近し ているがしきい値Ｓ２より大である成分差で評価される接近度を有し、発生回数 の少いいくつかのベクトルがある。この現象は優勢ベクトルについてのヒストグ ラムの拡大に対応する。これらベクトルは、０．５より差が大きくてもそれが接 近しているベクトルで有効にグループ化しうる。その理由は前の相で得られたク ラスの低下した動きフィールドのヒストグラムに２次最大値をつくるそのような ベクトルを保持しても使用しえないからである。

しかしながら、この操作中、画像の各ポイントがその隣接するもののそれに非常 に接近したずれを有するがすべての画像ポイントは異なるずれを有するから、事 実上フラットなヒストグラムをつくる効果を有するズームまたは回転形の画像の 入城動作を含める必要がある。その結果、このヒストグラムの２次最大値をさが すとき、検査された第１ベクトルはテーブルの第１ラインからのもの、すなわち 発生回数の最大であるものであり、このベクトル内の２次最大値の存在はこのテ ーブル内の１より大きい指標を有する少くとも２個のベクトルがしきい値Ｓ５内 でそれに接近するまで考慮されない。

５ＯＲＴ　（Ｎ、３）をクラスへの区分により生じる３つのゾーンを有する１次 元テーブルであり、Ｎをこのアルゴリズムのこの段階に残るベクトルの数とする 。ｋをテーブル５ＯＲＴ内で検査されるべきベクトルラインの指標とすると、ｋ は１からＮまで変化する。ｋ、ｉ、ｊより大きい指標をもつライン上の、ライン にのベクトルの発生回数より小さい発生回数をもつ少くとも２個のベクトルがラ インに内のベクトルに接近すると、これらベクトルは２次最大値とされて除去さ れる。テーブル５ＯＲＴの内容は次にこのギャップを埋めるべくシフトされ、発 生回数が更新される。

近接の概念は前述のように決定されるが、しきい値Ｓ　は異なる（Ｓ５は例えば ２にセットされる）。図７のテーブル５ＯＲＴにおいて、５ＯＲＴ　（ｋ、１） はラインｋにランクづけされたベクトルのＸ成分であり、５ＯＲＴ　（ｋ、２） そのベクトルのＹ成分である。

ｉとｊをｋより大とすると、 Ｉ　Ｓ　ＯＲＴ　（ｋ、１）　−Ｓ　ＯＲＴ　（ｉ、１）　Ｉ　＜　Ｓｓｌ　Ｓ 　ＯＲＴ　（ｋ、　２）　−３ＯＲＴ　（ｔ　、２）　ｌ　＜　Ｓ　ｓでありそ して ｌ　５ＯＲＴ　（ｋ、１）−ＳＯＲＴ　（ｊ、１）ｌ＜５５１５ＯＲＴ　（ｋ、 ２）−８ＯＲＴ　（ｊ、２）ｌ＜８５であるとすると、ラインｉとｊにランクづ けされるこれらベクトルは２次最大値でありこのテーブル５ＯＲＴから除かれる 。

これらの操作はに−１について開始しそしてテーブル５ＯＲＴのすべてのベクト ルがカバーされるまでｋを増加する。

この相の終了時に発生回数の多い最大値のまわりの２次最大値が除かれる。

次の相は時間フィルタリングである。

この時間フィルタリングは前の相の終りにＮ　ペクトルを含むテーブル５０　Ｒ Ｔに適用され乙。前の操作の目的は「カッド−ツリー」エンコード法により処理 後にエンコードされる動きフィールドの伝送速度を低下させるために高密度画像 象現からの優勢ベクトルの抽出であった。伝送されるベクトルの数は許容伝送速 度の関数として選ばれそしてＮｍａｘ／画像象現で示される。

テーブル５ＯＲＴの第１のＮ１１ａＸベクトルはバッファメモリＭＥＭＩに転送 されて、前の画像についての優勢ベクトルとして抽出されそして図８のバッファ メモリＭＥＭ２に含まれているものと比較される。メモリＭＥＭＩに移されたＮ ｍａｘからのテーブル５ＯＲＴの１つのベクトルがしきい値Ｓ１で前に限定され た距離についてメモリＭＥＭ２のすべてのベクトルから離れていれば、このベク トルは５ＯＲＴから除かれる。テーブル５ＯＲＴは次にこのギャップを埋めるた めにシフトされそしてＮ　がＮｎａｘより大であれば付加ベクトルを回復する。

テーブル５ＯＲＴのＮｌｌ１ａｘベクトルがテーブルＭＥＭ２のそれに接近して いることが決定された後に、これらベクトルは次のモジュールに移される。テー ブルＭＥＭＩの内容は新しい動きが生じる、例えば、２つの画像に共通の背景内 の一つの目標が動きはじめる場合を考慮してテーブルＭ　Ｅ　Ｍ　２に移される 。テーブルＭＥＭ２の内容は時間フィルタリングの結果によっては変更されない 。

次の相は画像内の寸法ｎ、ｎの各ビク七ルブ′Ｓ／りに一つのベクトルを再割当 てする相である。

この再割当て相は前の相で選ばれたベクトルを用いて各１１．１画像ビクセルブ ロックについてこのブロックを最適に表わすことの出来るベクトルを検査するこ とからなる。実際にはその画像内で優勢とみなされたＮＩＩａｘベクトル（これ らベクトルはＮ１ａｘより小さい数となる）の１個がｎ、ｎビクセルの各素ブロ ックに割振られる。

このため、第１相（１ベクトル／ｎ、ｎブロックの割当て）により生じるベクト ルフィールドが再びとり上げられ、そして各ブロックに二のブロックにはじめに 割当てられたベクトルに最も近い優勢ベクトルを属させる。

第１相の終了時の問題のブロックのベクトルをＶ（Ｖ、Ｖ）とすると、このベク トルとテーブルｙ ＳＯＲＴの優勢ベクトルの夫々との間の距離は次のように計算出来る。

Ｄｌ（ｋ）　−Ｍａｘ　（Ｄ、（ｋ）　、　Ｄ、　（ｋ）　）但しＤ　（ｋ）− １Ｖ　−９ＯＲＴ（ｋ、１）ＩＸ　Ｘ Ｄ　（ｋ）−１Ｖ　−５ＯＲＴ（ｋ、２）１ｙ で限定される最少値を与える、テーブル５ＯＲＴ内のランクにのベクトルＶａｘ 　（Ｖａｓ　、Ｖａｓ　）である。

ｙ しかしながら、最少距ｊｌｉＤ１．（ｋ）がしきい値Ｓ５より大であればこのブ ロックにはベクトル割当てがない。

更に、数個の指標ｋが同一の最少値Ｄ１を与える場合にはこれら指標に対応する 動きベクトルは次のように距１ｉＤ２　（ｋ）を与えるものを用いることにより 決定される。

Ｄ２　（ｋ）−最低ｍ　ｉ　ｎ　（Ｄ（ｋ）　、Ｄｙ　（ｋ）　）この相の終了 時に優勢ベクトルを割当て得ないブロックが存在しうる。

次の相はこれら割当てられないブロックの処理である。

前述のように各ｎ、ｎブロックへのベクトルの再割当て相の終了時に、テーブル ５ＯＲＴの優勢ベクトルのいずれも適していないことがありうる。これらブロッ クは動きエステイメータの誤動作により初期の動きに誤りをもつブロックまたは 、例えば非常に小さい動く目標に対応する特に局部的な動きをもつブロックであ る。

これらブロックについてのベクトルの割当ては「カッド−ツリー」エンコードで 行われる。「カッド−ツリー」区分において問題とするブロックに隣接する３個 のプロッタが同一のベクトルを有するときこのベクトルを割当てされていないブ ロックに割振る。「カッド−ツリー」エンコードにおけるこれら３個の隣接ブロ ックのベクトルが間−でないならば、それに隣接する８個の最も近いブロック内 の主ベクトルがこの割当てされていないブロックに属するようにされる。

次の相は分離されたブロックのフィルタリングである。

割当てされないブロックを処理する相の終りに得られる再割当てされた動きフィ ールドは、分離されたベクトルをもつブロックがエンコード速度において高いコ ストとなるからそれらブロックを除くようにフィルタリングされる。一つのブロ ックが同一ベクトルをもつ８個のブロックで囲まれ、その結果、中央のこのブロ ックのベクトルが隣接するすべてのブロックとは異なるものとなる場合にこのブ ロックを分離されたベクトルをもつブロックと呼ぶ。この場合、隣接するブロッ クのベクトルがこの中央のブロックに割当てられる。

このフィルタリングの終りに行われる次の相はエンコード速度の計算である。

伝送前に、このようにして行われるセグメント化方法により得られる動きベクト ルのエンコードのコストが最大許容エンコード速度と比肩しうるかどうかを決定 することが必要である。動きフィールドに関する情報は「カッド−ツリー」エン コード法により、すなわち４つの象現に従って対応するビクセルマクロブロック を区分し次に各象現を４等に、この区分により得られたブロックがベクトルの動 きフィールドについて均一となるまで区分することにより構成されるエンコード ツリーに従って上述のようにエンコードされる。このような技術は例えば「コン ピュータ・ビジョン・グラフィックス、アンド・イメージ・プロセシング」３７ 巻、４０２−４１９＜！９８？ンのＣ，Ａ、ジニ７７−およびＨ，サメ、・トに よる「オプチカル・クオドラチャ・コンストラクション・アルゴリズム」に開示 されている。

エンコード後の伝送速度は例えば１２８．１２８ピクセルの「マクロブロック」 を考慮して計算される。ｎを２のべき数としてｎ、ｎが素ブロックのサイズであ るとすればマクロブロック自体に対応する初期レベルに加えて各マクロブロック のエンコードツリーの深さレベルの数はｌｏｇ２　（１２８／ｎ）である。「レ ベルＯ」を初期レベルとすると、マクロブロックを均一でないとすると第ルベル 、すなわち６４Ｘ６４個のブロックの１個となる。第２レベルはそれが均一でな いとき一つの６４Ｘ６４ブロツクについて得られ、そしてこのプロセスは寸法ｎ 、ｎの素ブロックまで続行する。

一つの高密度画像象現についての伝送速度は次式で得られる。

Ｄ−Ｎ　ＸｂＸＭＢＸｃ（ビット／ｓ）但し −ｒＮＪはすべてのエンコードツリーのノード数、〇 −「ｂ」は１つのノードについて夫々の可能な状態を記述するに必要なビット数 、 −ｒＭＢＪは一つの画像象現についてのマクロブロックの数、 ＝「Ｃ」はフィールド数７秒 である。

一つのノードの状態は画像の動きフィールドを表わす優勢ベクトルの１つかある いはツリーの低いレベルへ通るための、このブロックの４区分への区分を示すイ ンジケータである。

前のセグメント化アルゴリズムにより抽出されるベクトルの数をＮ１とし、時間 フィルタリング後に実際に伝送されるベクトルの数をＮｔｒａｎｓとし、伝送さ れたベクトルの最大数をＮｍａｘとする（Ｎｔｒａｎｓは常にＮ５ａｘ以下であ る）と、一つのノードの状態を記述するに必要なビット数はｌ　ｏｇ２　（Ｎｔ ｒａｎｓ＋１　）以上の整数である。

図９と１０はレベル０．　１．２および３の１６Ｘ１６素ブロツクからなるマク ロブロックについての区分けとエンコードを示す。図９は図１０のエンコードツ リーに対応するマクロブロックの動きフィールドのセグメント化を示す。このマ クロブロックの第２象現は第３および第４象現と同様に均一であり、それ故これ ら象現の夫々はレベル１の異なるベクトルによりエンコードされる。

第１象現はレベル２のベクトルによりエンコードされる３個の均一な象現と、４ 分割後にレベル３でエンコードされる１個の非均−な象現を含む。レベル３のｅ ｓ（ｓｌｃＥ　ブロックは均一である。図１０に示すエンコードツリーは１３個 のノードを含む。Ｎ１ａｘ−７でありＮｔｒａｎｓ−Ｎｍａｘであれば、一つの ノードの状態を記述するに必要なビット数はＥ　［Ｉｏｇ２８］　（Ｅ　（Ｘ） はＸ以上の整数を考慮した操作を表わす）、すなわち３である。

最終レベルまで下げる必要はない。この図に示すようなマクロブロックのツリー のコストは１３　Ｘ　Ｅ　（ｌｏｇ２（Ｎ５ａｘ以下））である。ＮＩＩａｘが ７であれば、すなわちこの画像象現について記憶された７個の優勢ベクトルがあ るとすれば、このツリーのコストは１３Ｘ３−３９ビツトである。

整数個のマクロブロックが、セグメント化を行う高密度画像象現より大きいゾー ンをカバーする。事実、ＨＤ画像象現は夫々８．８ビクセルからなる９０Ｘ７２ 素ブロツクを含み、水平に６マクロブロツクより小さく、垂直には５ブロツクよ り小さい。この画像のこの象現からあふれた部分はエンコードツリーについて最 少コストを与えるベクトルで埋められる。

このセグメント化アルゴリズムは各画像象現につき別々に行われる。それ故、前 述の式により計算される伝送速度は合計伝送速度の一部にのみ対応する。

最後の相は伝送速度の調整相である。

前の相の終了時に計算された伝送速度が許容限界を越えれば、このセグメント化 方法が各ｎ、ｎブロックへのベクトルの再割当て相のスタート時に再び用いられ 、そしてこの相を再びとり上げる前に数ＮＩＩａＸを１だけ減算する。次に最後 の４つの相が、合計した計算伝送速度が最大許容伝送速度以下となるまでこのよ うにして再び用いられる。

ｒポイント形」動きフィールドすなわち各ビクセル当り１つの動きベクトルまた は各ラインに連続するラインに千鳥状に配置される２つの内の１つのピクセルに ついて１つの動きベクトルを含むものを用いるセグメント方法については前述し た。

本発明による方法は上流側で用いられる動きエステイメータがブロック動きベク トルを与える場合にはブロック動きフィールドセグメント化に同様に適用される 。この場合には勿論ｎ、ｎブロック当り１ベクトルの割当て相はエステイメータ がｎ、ｎブロック当り１動きベクトルを与える場合には削除され、あるいはエス テイメータがｎ、ｎより小さいサイズのブロック当り１つの動きベクトルを与え る場合には変更される。

図１１はポイント形動きフィールドのセグメント化方法の、前述した種々の相の 流れ、すなわち−人力Ｅ１に与えられるポイント形動きベクトルのフィールドか らｎ、ｎブロック当り１個のベクトルの割当て。

−第１の相により得られる（または入力Ｅ２に与えられるｎ、ｎビクセルブロッ ク状動きベクトルフィールドがあれば直接に得られる）ブロック状動きフィール ドのフィルタリング。

一一一つの画像象現につ一゛てフＸ５“Ｌり”、′−グされた動きフィールドの ヒストグラムの作成。

−動きのクラス毎に代表的ベクトルの抽出。

−２次最大値の除去。

−時間フィルター１ング。

−各ｎ、ｎブロックへのベクトルの再割当て。

−ベクトル割当てのないブロックの処理。

−分離されたブロックのフィルタリング。

−　エンコード速度の計算およびこの速度が限界値より小さいかどうかの評価、 および、小さくないとき、新しい再割当て段階の上述のような実行、小さいとき 出力Ｓに得られるセグメント化された動きベクトルフィールドのエンコードの伝 送のための実行、 を示している。

本発明は上記詳述した方法に限られない。特に、このセグメント化方法の各段階 において成る数の選択が行われそして成る数の計算が各段階で行われる。ブロッ クの寸法およびしきい値について例として上げた図はそれに限定されない。しか しながらしきい値についてはＳ２はＳ　より大でありＳ５はＳ２より大でなけれ ばならない。

更に、特に次のカッド−ツリーエンコードに適用される画像象現処理は本発明の 本質ではない。計算容量が画像の１回処理に充分なものであればこの処理を画像 全体について行うことが出来、あるいは１／４ではない画像Ｓ部分についての処 理を行うことが出来る。

ｎ、ｎブロックの動きフィールドのフィルタリング相（このセグメント法の第２ 相）は以降の処理を容易にするが、分離したブロックのフィルタリング相が次に あることおよび、全体として本発明のセグメント化方法が分離された動きベクト ルを含めないことを目的とするものであることにより、特に本質的なものではな い。本発明のセグメント法の第２および第９相である動きフィールドのフィルタ リングそしてまたは分離ブロックのフィルタリングはそれ紋付われるシーケンス 分析の形式によっては変更または省略しうる。

最も頻繁に生じる動きベクトルのテーブル作成を可能にするヒストグラムの形成 段階では、フィルタリング後の現在ブロックについて許容されたベクトルに対応 する位置のみが増加されるばかりでなくそれに隣接する８個のベクトルも増加さ れることは先に述べた。ヒストグラムを拡張するために与えられるこの特徴は、 例えば画像が１回だけ処理される場合等、場合によっては不必要である。成分Ｖ 　とＶ　の８倍の乗算は有利ではあるが不ｙ 可欠ではない。

他の変更は本発明の範囲内で可能である。例えば成る場合には「動きのクラス」 当り１つの代表的ベクトルの抽出相を行わずにヒストグラムテーブルの最大発生 回数をもつＮ個のベクトルを選びそしてそれらベクトルをエンコード前に各ブロ ックにベクトルを再割当てするための優勢ベクトルとして直接使用することで充 分である。

図２ 図４ 報 図５ 図７ 図８ 図９ 図１０ レベルじ 図１１ 国際調査報告 国際調査報告

Claims (12)

【特許請求の範囲】
1. １．前の画像に対する画像のピクセルのずれを画像面内に２つの成分をもつベク トルの形で出す動きエスティメークからの動きフィールドの、下記相を特徴とし て含むセグメント化方法： −画像を夫々ｎ，ｎ個のピクセルを含むブロックヘと区分しそして各ブロックに 多数決に従って可能なベクトルから選ばれる一つの動きベクトルを割当てる前相 ；−ブロック状動きベクトルのヒストグラムをセットアップする相であって、そ の相の終りにそれら動きベクトルの分類をそれらの発生回数に従って行うように なった相； −夫々の上記ブロックについて、上記ヒストグラムから選択された有限個Ｎの優 勢ベクトルから選ばれる、これら優勢ベクトルの内の上記ブロックの初期ベクト ルに最も近い動きベクトルを再割当てする相；−隣接するブロックとインコヒー レントである動きベクトルを有する分離されたブロックのベクトルをフィルタリ ングする相； −結果としてのフィルタリングされた動きフィールドのエンコードに必要な伝送 速度を計算しそしてこの伝送速度が長大可能伝送速度以下であるかどうかを決定 し、伝送速度が最大可能伝送速度より大のとき、より少数の優勢ベクトルから上 記夫々のブロックに動きベクトルを再割当てする棺が再び採られるようにする相 。
2. ２．ポイント状動きフィールドの処理のために、前記前相はｎ，ｎピクセルの各 ブロックにつきそのブロックにおいて発生回数が最大である動きベクトルを検索 し、同じ場合には最少の散逸をもつ動きベクトルを検索することからなることを 特徴とする請求項１の方法。
3. ３．一つの動きフィールドのブロック処理について、前記前相は、そのブロック の寸法がｎ，ｎであるとき動きフィールドを伝送しそしてその動きフィールドが より小さい寸法のブロックについて成立するときこのｎ，ｎブロックに割当てら れるベクトルを伝送することから成ることを特徴とする請求項１の方法。
4. ４．前記動きフィールドのブロックフィルタリング棺は前記ヒストグラム作成相 の前に行われ、そしてこのブロックフィルタリング相はそのブロックのベクトル がその８個の隣接ブロックのベクトルから離れているとされたときそのブロック の動きベクトルをそれら８個の隣接ブロックのベクトルの内の１つにより置き換 えることから成ることを特徴とする請求項１乃至３の１に記載の方法。
5. ５．前記ブロック状動きベクトルフィールドのヒストグラムの作成は２次元テー ブルから行われ、その中央位置が０ずれに対応し、その他の位置がすべての可能 なずれに対応し、このテーブルの同一ラインの位置（夫々のコラム）が現在画像 のずれる横座標（夫々の綾座標）成分に対応し、このヒストグラムが現在の分離 されるブロックのずれに対応する位置並びにそのヒストグラムテーブルの８個の 隣接する位置の内容を１だけ増加することにより形成されるごとくなったことを 特徴とする請求項１乃至４の１に記載の方法。
6. ６．前記再割当て相について、前記優勢ベクトルは前記ヒストグラムテーブル内 に最大の発生回数を有するＮ個のベクトルであることを特徴とする請求項５の方 法。
7. ７．前記再割当て相の前に、ヒストグラムテーブルの対応する位置の内容の順序 を下げることによりベクトルを分類しそして、より高いランクのベクトルに近い ベクトルを除去して動きの拡大されたクラスを表わすベクトルのしきい値Ｓ２内 にシーケンスを形成することからなる、動きのクラス当りに１個の代表的ベクト ルを抽出する相が置かれることを特徴とする請求項５の方法。
8. ８．前記動きの拡大されたクラスを表わすベクトルの内、より高いランクのベク トルにＳ２より大であるしきい値Ｓ５との比較で近いとされる２つの異なるベク トルの対によって限定される２次最大値に対応するものが同様に除去されてこの 近いベクトルの除去後に残るベクトル群がブロック動きフィールドのエンコード に用いられる優勢ベクトル群となることを特徴とする請求項７の方法。
9. ９．前記再割当て棺の前に前記優勢ベクトル群の時間フィルタリングが各ベクト ルを前の画像について成立した優勢ベクトル群のすべてのベクトルと比較しそし て前の画像に関連した群のすべてのベクトルから離れていると見積もられたベク トルを除去することにより行われることを特徴とする請求項８の方法。
10. １０．前記再割当て相は前記優勢ベクトル群内の前記ブロックの初期ベクトルに 最も近いベクトルをこの初期ベクトルとこれら優勢ベクトルの夫々との間の距離 を計算しそして最小距離となる優勢ベクトルを選ぶことにより検索することから なることを特徴とする請求項１の方法。
11. １１．前記最小距離となる優勢ベクトルはその距離がしきい値より小さいときに のみそのブロックに再割当てされ、ベクトルの割当て不能なブロックが隣接する ブロックのベクトルにより動きベクトルのエンコード中に割当てられるようにな ったことを特徴とする請求項１０の方法。
12. １２．カッド・ツリーの形の方法にもとづく画像エンコードヘの、前記請求項の 内の１つによるビデオ画像の動きフィールドのセグメント化方法の応用。