JPH01502143A - パターン処理 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ユ≦胚 本発明は、パターン処理に関し、特に、しかし非排他的に、ビデオ信号のコーデ ィング（符号化）のための上記処理の適用に関する。

１つの例は、動画を伝送するためのコーディング方式としてフレーム間条件付き 画素補充方式を適用するビデオコーダについてのものである０画素値と予測値（ すなわち、先行するフレームに基づく予測値）との差分が用いられる。

この差分は、各差分値についてスレショルド回路ルえるか否かを示す°１°また は°０゛を生成するスレショルド回路に印加され、それによって「ムーブメント マトリクス」を形成する。対応するムーブメントマトリクスのエレメントが′１ °である画素Ｍ（または、もし必要ならば、画素差分）のみが伝送のためにコー ディングされる。

受信機においては、受信情報は局部フレーム記憶装置に格納された画像を更新す るために使用される。受信機が受信情報を正確にデコードできるようにするため には、係数が送られたことを示す副情報が伝送に含められる必要がある。ムーブ メントマトリクスの全てのビットを送ることは実質的なオーバヘッドとなり、そ のため、画像を８×８のブロックに分割し、５ビツトの伝送ビットのみを用いて 受信機が識別し得る１組の（例えば）３２個のパターンのうちの最も近いものを それに対応付けることによって、各８×８ムーブメントマトリクスを「ベクトル 量子化」することが提案されている。従来、この対応付けは、パターンについて の相関法を適用することによって達成されていた、これはコンピュータ的な浪費 であり、高速処理を用いたとしても３２個のパターンが一般にリアルタイムで実 行できる最大である。

上記技術は、変換コーディングとフレーム間条件付き画素補充方式のコーディン グの組合せが用いられるいわゆるハイブリッドビデオコーダにも適用することが できる変換コーディングは、変換係数の対応するマトリクスを生成するための画 素の（例えば８Ｘ８の）ブロックに対し、アダマール（Ｈａｄａｍａｒｄ）変換 または離散コサイン変換（ＯＣＴ）のような２次元変換の適用を含む（一度に全 フレームを変換することはリアルタイムの処理には遅過ぎる）、ここで、ムーブ メントマトリクスは、カレントフレームのマトリクスの係数と先行するフレーム のそれとの差異に基づいている。

この処理の変形としては、変換の後にフレーム間の差分なとらずに、フレーム間 の差分なとることを変換より先行させてもよい。

本発明の一つの局面によれば、２次元パターンを表現する１組の値をクラス分け する方法が提供される。該２次元パターンを表現するＩＭの値をクラス分けする 方法は、Ｘを法として（（至）ｏｄｕｌｏχ）、但しＸは２の２乗より小さい整 数、Ｐは上記組における値の数である、それらＩＭｉの値の重み付は加算を形成 し、且つクラス識別ワードが格納されるＸ個のロケーションを有する記憶装置を アクセスするためのアドレスとして上記加算を用いることを含む。

原則として、参照される値は、パターンの各エレメントに関連する値であり得る が、加算は単純であり、各々が多数のエレメントをあられす１組の値の最初の形 成により、重み付は係数および法（ｎｏｄｕ　１ｕｓ）の導出は、容易化される であろう、そして、本発明の望ましい実施例は、上記パターンの複数群の各々に ついて、予め定義された群の１つ、それら各群はそれに関連するコードを有する 、上記１つの群は所定の基準に従って最もよく似ている、を識別することにより 、上記１組の値を導く、上記コードはそのように識別され上記１組の値を形成す る群に関連する、ことを含む。

上記群は方形パターンマトリクスの行（または列）であるが、その他の選択であ ってもよい。

以下、本発明の一実施例を図面を参照して説明する。

第１図は、ムーブメントマトリクスのベクトル量子化のための装置のブロック図 、 第２図は、標準的なラインベクトルの１ｆＡを示す図、第３図は、標準的なパタ ーンの１組を示す図、第４図は、パターン領域のマツピングの概念を説明するた めの図、 第５図および第６図は、係数および法の導出のための処理を示すフローチャート 、そして 第７図は、モーションベクトルの生成を説明するための図である。

以下に述べる構成は、導入部で述べたように、多数の８×８ピクセルブロツクの 各々について、各エレメントが対応する画素（または変換係数）がフレーム間で 実質的に変化したかどうかを示す単一のビットである８×８のムーブメントマト リクスを形成するようなビデオコーダに用いられる。

先に論じた問題は、２の６４乗の可能なパターンをより小さい数（３２）のクラ スに割当てることの１つである。

理論的には、これは各々パターンがどのクラスに属するかを示す５ビツトの数値 を含む２の６４乗のロケーションを有するルックアップテーブルを用いることに より達成できるが、そのようなサイズのテーブルは明らかに実用的でない、たと え、上記マトリクスが、各８ビツトのラインを５ビツトであられして該マトリク スの行をベクトル量子化することにより前処理されたとしても、テーブルサイズ は、依然として２の４０乗である。提案の方法は、２の６４乗（２の４０乗）個 のパターンをより少ないＸ個のクラスにマツピングするために法Ｘ加算（Ｘを法 とする加算）関数を用いる。もちろん、加算関数の係数および法Ｘの値は、以下 に述べるように、所望のパターンの組に適するように選定されなければならない ０例外的なケースでは、特別なパターンの組がクラス数に等しいＸを可能とする のに対し、一般にはそうではないが、実際には、Ｘは、ルックアップテーブルが 、３２個のクラスの１つを識別する５ビツトの数を格納するＸ個のロケーション により構成されることを可能とするのに充分に小さくすることができる。

第１図は、ビデオコーダの一部を形成する構成を示しており、該構成は、３２個 の標準パターンのうち、入力８Ｘ８Ｘ１ビツトのムーブメントマトリクスに最も 良く似たものを識別するためのものである。エレメント当り１ビツトｂ　（ｉ、 ｊ）の上記ムーブメントマトリクスは、生成されて、６４ビツトのバッファメモ リ１に格納されているものとする。６ビツトのアドレスカウンタ２は、タロツク により動作して、メモリ１のアドレス入力に与えられる０から６３のアドレスを 発生する。メモリ１のデータ出力ｂ　（ｉ、ｊ）および列アドレスｊは、５ビツ トのラインベクトルコードを生成するライン量子化器３に与えられる０行アドレ スｉは、各々８ビツトの係数Ｃ（１）を格納する８つのロケーションを有するリ ードオンリ係数メモリ４のアドレス入力に与えられる。ラインベクトルコードｑ （ｉ）およびメモリ４のデータ出力は、積を形成するマルチプライヤ５に供給さ れる。

上記積は、法Ｘアダー６、およびその出力が該アダー６の１つの入力にフィード バックされる１６ビツトラツチ７に供給される。上記法は、もちろん、２の１６ 乗を超えることはできない。

アキュムレータ出力は、入力ムーブメントマトリクスが割当てられるべき、３２ 個のパターンクラスのうちの１個を識別する５ビツトのワードを各々格納する２ の１６乗＝６４にのロケーション（それらのうちＸ個のみが使用される）を有す るさらなるリードオンリメモリ８からなるルックアップテーブルに対するアドレ ス入力を形成する。

そして、メモリ７のデータ出力８は、法Ｘ加算の値に従ってテーブルから選択さ れた５ビツトのワードを与える。

上記処理をより詳細に考慮すれば、各エレメントｂ　（ｉ、ｊ）が画像の対応す る画素（ビクセル）が動いている（”１パ）と判定されたか否である（”ｏ’“ ）と判定されたかを示す１ビツトである８Ｘ８マトリクスＢから入カバターンが 構成されるとみなされる。これは、そうでない時にビクセルが動いていると表現 することが動いているビクセルを静止していると表現するよりも望ましいので、 類似度の基準を見つける上で重要なファクタである。

ライン量子化器３においては、８Ｘ８Ｘ１マトリクスの内容の情報が、各８×１ ビツトの水平ラインが、ｌｌｌ１ｌの８×１ベースベクトルの最も近い１つに対 応付けされるように、「ライン」量子化される。第２図に示すように６個のベー スベクトルを仮定する。原則として、この処理に供される８ビツトの群が入力マ トリクスのライン数から導かれる必要はなく、他の選択も可能であることに注意 すべきである。各ベースベクトルは、コードｖＯ・・・ｖ５であられされる。こ れらは、原則的に、０から６の整数であり得るが、特殊な結果を生成するために は他の選択もあり得る。特に、０から２５５の範囲、広く間のあいた数値、主と して素数、（例えば１４１．９５．１１１．１７３．２３７．２９．１９２．２ ２４、または１４９．９７．１１３．１７３．２３９．２９．１３７．４３）が 望ましいことが見出されている。

上記組は、マニュアル的に選定されるが、可能性のある候補の比較は、以下に（ 各ケースにおいて同じ乱数を用いて）次に述べる係数の対話的アルゴリズムを適 用することによって個々に比較される。最も高速の集束を与える膝組は、優れて いると思われる。

上記対応付は処理は、いくつかの位置に”１′°を持つ入力ラインが当該位置に パ０“を持つベースベクトルには対応付けされないことが必要である０例えば、 第２図に示される例としての入力ラインＥ１は、位置７に°１”があるので、（ うわべ上最も近い）Ｖ４に対応付けされ得す、ｖＯに対応付けされる。

このように、入力ラインが“１゛を持つ全ての位置に１“を持つベースベクトル を識別することにより処理が進められる。もしも、２以上ある場合、入力ライン における対応ビットと異なるビットの数の最も少ないことによって、それらのう ち最も近いものが選択される。

さて、８×８人カマトリクスは、８エレメントを有するベクトル［ｑ（ｉ）］に 変換される。

そこで、このベクトルは、マルチプライヤ５およびアキュムレータ６．７により 係数記憶部４の助けを受けてそのエレメントの重み付は加算りである法Ｘ、すな わち、１＝７ ｈ＝Σ　ｑ（ｉ）　・ｃ（ｉ） ｉ＝０ ０Ｄｘ （この定義は、以下の記述において加算間数と称される） を形成することにより、さらに量子化される。

このように、上記人力マトリクスは（ＯからＸの範囲の）スカラー加算に変換さ れ、それからメモリ８のルックアップテーブルをアクセスするために使用され、 上記メモリ８から使用されるべき標準パターンの１つを示すコードのワードを読 み出すことができる。＠準パターンの１４個の例が、対応するコードｚＯ・・・ ｚ１３と共に、第３図に示される。

法Ｘの制約無しにアキュムレータにより生成される重み付は加算が可能なパター ンのマツピングをあられすことくそれらのうちのいくつかは、第４図に概念的な パターン領域Ｐ内にＸ印＾からＥとして示され、「加算Ｊ領域Ｓ内になると、そ のサイズが係数ｃ　（ｊ）の値およびラインベクトルコードｖＯ・・・ｖ５に依 存する）が実現される。もしも、係数が、数値的に広く間がおいていると、全て のパターンは領域Ｓ内の興なる位置にマツピングされる。もしも、この条件が、 満足されないと、いくつかのパターンが、上記Ｓ領域に同じパターンとして（ｃ 、Ｅ参照）あられれる。

これは、もちろん、２つのパターンが同じクラスに属する場合にのみ望ましい。

法Ｘアキュムレーションの使用は、それ自体に１回以上折返すことにより領域Ｓ のサイズを減少させる。第４図に、領域ＨにおいてパターンＢがＣおよびＥと一 致する単一の折返しが図示される。

係数および法は、法の許容し得る低い値が、できれば、同じクラスに属する複数 のパターンのみがＨの同じ値にマツピングされる（実際には、次に論するように 、いくらかのエラーが許容されるけれども）ことが確実な範囲で達成されるよう に選択されなければならない０本発明者は、これが達成され得ることが理論的に 証明できず、ｃ（ｉ）およびＸの値を導出するのにいかなる理論的な方法もない ことに気付いている。けれども、実験によれば、これらの値を得るための対話的 な手続きを用いることにより満足すべき結果が得られることが示されている。

係数ｃ（ｉ）および法Ｘの適切な値を得る方法について以下に述べる。対話的方 法が係数ｃ（ｉ）を得るために用いられ、これは、（法の制約のない）加算関数 をパターンのテストシーケンスに適用することによる反復される係数の周期的な テストを必要とする。

明らかに、２の６４乗の全ての可能性のある８Ｘ８パターンをテストすること、 あるいはライン量子化ベクトルとしてあられされたときの可能性のある２の４０ 乗のパターンでさえも全てテストすることは現実的でない、したがって、テスト は、標準パターンそれ自体、およびａｍパターンの変形として定義されるさらな るパターンのクラスに限られる。変形パターンは、代替ベクトルで置換された１ 以上の要素ベクトルを伴う（ベースベクトルの形の）標準パターンとして定義さ れる。各ベースベクトルは、置換のためのある範囲の可能性のみ、すなわち、オ リジナルベクトルも”１゛°を有する位置にのみ”１゛′を有しているベクトル 、を有している。第２図は、各ベースベクトルに関連する変形ベクトルをリスト している。変形パターンの組は、そのような置換の全ての可能性のある組合せを 含んでいる。この変形の定義は、同様に変形パターンとベースパターンの間の基 準を与える。すなわち、画像コーディングが行なわれるとき、変形パターンは、 標準パターンと同じコードナンバを生成するときに、その変形パターンとなる。

１組の係数Ｃ＝［ｃ（ｉ）］のテストは、加算ｈ−（プライム「゛」は該加算が 法加算でないことを示す）の値を得るために標準および変形パターンに加算を適 用することにより行なわれる。完了すると、この処理は、ｑＩＩｉｎΣｃ（ｉ） からｑ　ｌａＸΣｃ（ｉ）の範囲、ここでｑｌｉｎおよびｑ　ｎａｘはｑ（すな わちＶ）の最小値および最大値である、に存在する１組の値ｈ−を生成する。

しかしながら、発生された新たなｈ−の各々は、ｈ゛の先行する値に対して照合 される。先行するｈ−の値の再発は、もしもその値を与えるパターンが同じ標準 パターン／変形パターン群からなる（すなわち、それらが同じコード番号を有す る）ならば、許容できる。さもなければ、このことは、別個のパターンの同じｈ ゛の値へのマツピングを意味し、これを「クラッシュ」と称する。テストにおい て生じなりラッシュの数は、テストされる係数の組の度合いＴＥＳＴ　（Ｃ）と して評価される。

上記反復処理は、第５図および第６図のフローチャートに示される。Ｃｎ　＝　 ［ｃｎ、Ｏ・−ｃｎ、？　］は、係数の組のｎ番目の繰返しを示す、　ＲＨＯ（ ｒ、ｓ）は、ｒからＳの範囲の乱数の発生を示す、処理は次のように進められる 。

初期推定値ＣＯが（１）で設定される。これは完全にランダムでよく、あるいは オペレータにより適切なスタート点の推定値が示唆されれば処理は短縮される。

そして、これは、（２）でテストされ、繰返しおよび時間切れカウンタが（３， ４）でしょきかされる、（５）で、係数のランダムな１つ（ｃｎ、Ｒ）の選択お よびそれに対するランダムな変化Ｐを生じさせることにより、Ｏｎの新たな値が Ｃｎ−１から導出される。最初の繰返しは、後の繰返しでは（例えばｌから７の 範囲で）小さく変化するのに対し、（例えば、８から２５５の範囲における、０ から２５５の範囲の係数値のために）大きく変化する。これは、係数を所定範囲 内に保持するため、法２５６加算により行なわれる。

それから（６）で新たな係数の組がテストされ、クラッシュが生じなければ（７ ）、処理は完了する。さもなければ、時間切れカウンタが進められ（８）、テス トの結果が、（９）で先行するテストのＧｎ−１と比較される。もしも、改善が 得られれば、ループカウンタは進められ（１０）、該ループは、クラッシュを生 じない係数の組が得られるまで繰返される。

しかし、この要求は、テストにおけるクラッシュの数が、テストされるパターン の数の、与えられた比率、例えば５または１０％、以下となったときに、それが 到達可能でない、あるいは繰返し時間を減少させるためそして繰返しが終わった ことにより、緩和され得る。これに代えて、繰返しの回数を制限してもよい、こ のようにクラッシュが許容されるならば、特別なｈ゛の値、該ｈ−の値は表現す るためにとられる、にマツピングされる２つ（またはそれ以上）のどれかを判定 することが必要である。それが引起こすクラス分はエラーの数を最小とするため に、通常、典型的な画像において生ずる最も高い可能性を有するクラスを選択す る。

らし、どんなときでも、改善が得られないならば、さらなる変化を試みる前にル ープカウンタをインクリメントすることに失敗することにより最新の係数の趙が 放棄される（１１）、もしも、特別の係数の組について、改善のために１０個の 成功しない試みがなされたならば、処理が悪い方向に進められていることを意味 し、最新のおよび先行するセットを放棄するため、ループカウンタがデクリメン トされる（１２）、もちろん、この制約は最初の繰返しに（あるいは、Ｇｏに折 返す処理に続く例に）適用することはない（１３，１４）　。

繰返しの終了は、加算に対し法の制約がないときのテストにおいてクラッシュを 生じない（または限られた数のクラッシュを与える）１組の係数Ｃｎを提供する 。上記係数の組を用いて得られるｈ−ｊ　（ｊ＝０・・・Ｔ−１、ここでＴはテ ストされたパターンの数）は、格納されたものと見なしく６ａ）、法Ｘを探す処 理に移行する。これは、Ｍから始まる、該Ｍは標準パターンの数である、連続す るＸの値についてのｈ−の組を変換することによって達成される。

（既に定義したように）クラッシュを生じない、あるいは限られた数のクラッシ ュを与える、最小のＸの値が所望の結果である。この処理は、第６図のフローチ ャートに示される。外側のループＡは、Ｘの各値を逐次調べ、クラッシュを生じ ない値が見出されたときに終了する。中間ルー１Ｂは、カレント法Ｘについて、 ｈ−の各連続する値を計算する。そして、内側のルーＩＣは、Ｘの値における全 ての先行するｈの値に対してｈｋを、クラッシュについて、チェックする。

係数および法の導出のために、可能性のある全ての入カバターンがテストされる 訳ではないことがわかるであろう。

標準パターンおよびその変形が最大の興味あるパターンをカバーするように選択 されることが意図されている。この例においては、“１パを含んでいるロケーシ ョンの半分以上のパターンが、標準の「全て１の」パターンにより表現されるよ うになっている。これらおよびその他のテストされていないパターンは、動作に おいて、疑似的な結果を生じ、そしてそれによってこの方法では結果をチェック するためのさらなるステップを含んでいる。得られたコードに対応する標準パタ ーンは、入カバターンと比較される。もしも、後者が、前者ではそうでないいず れがのロケーションに′１゛°を含んでいるならば、チェックは失敗であり、得 られたコードに代えてｚ１３が代入される。該動作は、第１図においテストユニ ット９と切換えスイッチ１ｏにより概念的に示されている。この処理は上述した 代替的な緩和されたクラッシュ基準によって生じるエラーも補償する。

本発明の他の応用は、モーションベクトルの生成にある。

これは、直前の先行ブロックに対応するカレントフレーム内のブロック位置を確 実にし、動きの大きさと方向を示すモーションベクトルを形成するために、画像 の先行するフレームのブロックをカレントフレームのシフトされたブロック（あ るいはその逆）との比較を含む、この技術をフレーム間コーディングシステムに 用いれば、ムーブメントベクトルは、受信機に送信して、シフトされた画像の適 切な部分に先行するフレームを用いて代えることによる先行するフレームに基づ く予測により効率を高めるために使用することができる。

上述のように、相関法は低速である。このようなムーブメントベクトルの使用は 、結果として、変形されていない先行するフレームよりも良好な予測が得られる 限り、正確なシフトされたブロックとシフトされていないブロックとの対応付け を必要としない。

さて、以下に述べられるモーションベクトルの発生の結果は、直接的に用いられ 、あるいは在来のモーションベクトルのため「検索の領域」を限定する第１の予 測を形成し得る。

画像の全てのノロツクが、上述した方法にしたがって（変換係数よりもむしろエ レメント値に基づいて）、コードナンバに割付けられるとする。先ず、１以上の 「全ての動く」コードＺ１３、すなわち、意味のある動きの生じる画像領域を識 別する、を有するブロックが配置される。

このようなブロックの各々について、（以下により詳細に示すように）それの示 す動きの位置を確認するなめ、カレントおよび先行フレームにおけるブロック位 置に対するコード間の比較が行なわれる。８つの周囲のブロックが同様に検査さ れ、もしも一貫性が得られれば（例えば半分以上の方向が同じであると推定され れば）、この方向は望ましい推定として採用される。

該比較処理は、第７図に示される。もしも、先行およびカレントフレームコード が第７（ａ）図に標準パターンが示されるように、ＺｌｌおよびＺ６であれば、 動きの方向は矢印として図示された方向であるとみなされる。第７（ｂ）および （Ｃ）図は、その他の例を示す、ルックアップテーブルは、各コードのペアに対 応するモーションベクトルのパラメータを提供するであろう。

もしも、もちろん、２つのブロックの比較が全体的な移動を示すならば、何の情 報も得られず、そのブロックを囲む複数のブロックまたは（両フレーム間におい て隣接するブロックも全体的に動く場合は）そのような１群のブロックを囲む複 数のブロックに基づいて判定される。

国際調査報告 国際調査報告 ＧＢ　８７００８１６ ＳＡ　１９５０４

Claims (1)

1. 【特許請求の範囲】 １　２次元パターンを示す１組の値をクラス分けするための装置において、それ らの値のｘを法とする重み付け加算、但しｘは２のｐ乗よりも小さい整数であり 、ｐはその組における値の数である、を形成するための加算手段と、各々標準パ ターンの１つを示すクラス識別ワードを格納するｘ個のロケーションを有する記 憶装置、該記憶装置のアドレス入力は上記加算手段の出力を受けるように接続さ れている、とを具備する装置。 ２　第１項の装置において、上記パターンの各エレメントをそれぞれ示し、上記 パターンのエレメントの複数の群の各々について、各々がそれに関連するコード 、該コードは１組の値を形成する識別された群に関連する、を有するそのような 群、該群は所定の基準に従って最も近い、の所定の組の１つを識別する、データ を受信する手段を含む装置。 ３　第１項または第２項の装置において、上記重み付け加算は、次のような加算 関数、 Ｎ−１ ｈ＝Σｑ（ｉ）・ｃ（ｉ） ｉ＝０ ＭＯＤｘ 但し、ｑ（ｉ）は上記値、Ｎは該組における値の数、そしてｃ（ｉ）は、係数値 にランダムに変更される繰返し処理によって導出される重み付け係数、 および次式で定義される変形加算関数、Ｎ−１ ｈ−＝Σｑ（ｉ）・ｃ（ｉ） ｉ＝０ ＭＯＤｘ が一連のテストパターンに適用され、変更が発生するクラッシュ、該クラッシュ は２つのパターン、所定のクラス分け基準に関し、同一のクラスに属さない、に 関し同一のｈ−の値の発生として定義される、の数において改善があるときにの み、さらなる繰返しのためにランダムな変更が保持され、そして処理が繰返され る装置。 ４　第３項の装置において、係数の組について得られるｈ−の値の法の減少を見 出すための繰返しの結果、クラッシュを生じない、または所定数よりもクラッシ ュの少ない最小の整数を見出すことにより導出される装置。 ５　上記第１項〜第４項のいずれか１項の装置において、さらに、上記２次元パ ターンを記憶装置の出力に得られるクラス識別ワードに対応する標準パターンと 比較し、該パターンが所定のクラス分け基準に関して、標準ワードと同じクラス に属さない場合は、代替クラス識別ワードに置換えるためのテスト手段を含む装 置。 ６　１フレーム間コーディング手段およびフレーム間で実質的に変化する画像パ ターンのエレメントを示すムーブメントマトリクスを発生する手段、上記マトリ クスをクラス分けするための上記第１項〜第５項のいずれか１項の装置、および 受信機に各画像パターン毎に、対応するクラス識別ワードおよび該クラス識別ワ ードに関連し標準パターンに従って選択された画像パターンのエレメントに関す る情報を伝送する手段を有するビデオコーディング装置。 ７　第６項のビデオコーディング装置において、連続する２フレームの対応する 領域に関するクラス識別ワードを比較することにより動画領域に関するモーショ ンベクトルを発生する手段を含む装置。 ８　第７項のビデオコーディング装置において、上記比較は、モーションベクト ルとそれに対応するクラス識別ワードとの組合せが格納されたルックアップテー ブルをアクセスするために２つのクラス識別ワードを用いることにより行なう装 置。