JPH04504319A

JPH04504319A - ブロックマッチングアルゴリズムの実現回路

Info

Publication number: JPH04504319A
Application number: JP1504005A
Authority: JP
Inventors: ウー、ランセロット; ヤング、クンミン
Original assignee: ベル　コミュニケーションズ　リサーチ　インコーポレーテッド
Priority date: 1988-03-14
Filing date: 1989-03-13
Publication date: 1992-07-30
Also published as: EP0400084B1; EP0400084A1; WO1989008891A1; US4897720A; CA1306061C

Abstract

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

Description

【発明の詳細な説明】ブロックマツチングアルゴリズムの実現回路発明の分野本発明は、動き補償として知られるビデオデータ圧縮技術に関する。より具体的には、動きが引き起こす連続ビデオフレーム相互間の差を検出し補償するフルサーチ機能を持ったブロックマツチングアルゴリズムの超ＬＳＩ形成法に関する。

発明の背景３０フレ一ム／秒の走査速度のテレビ信号は、フレームから７レームへの冗長度が膨大である。特にビデオ会議技術に適用されるとき、１シーンにおける動きが通常少なく、７レームから７レームへの冗長度が大きくなる。このような場合、フレームから７レームへのデータ冗長度を縮減しデータ圧縮の高効率を達成するためにコーディング技術を用いることができる。

ビデオ会議技術応用において現れる第１と第２の連続ビデオフレームについて考えてみると、これら２７レ一ム間の差は、人の腕や手のような対象物の動きによって引き起こされる。もしこの動きがフレームの小さなエリアに限られており、また第１フレームを受信機に映像化することができるのなら、第２フレーム全体を受信機に伝送する代わりに、その動き情報だけを受信機に伝送すれば足りるわけである。こうした動き情報を受ければ受信機は第１７レームから第２フレームを構成することができる。特に、その動き情報は第２フレームと第１７レーム間に動いている対象物の置換を予測することによって得ることができる。この予測された置換は、受信機が第２７レームを第１フレームから構成することができるように受信機に伝送、される。

このようなビデオデータ伝送法を用いることによって、２フレームにつき１つだけの完全７レームデータを伝送すればよいから、かなりな量のデータ圧縮を達成することができる。このデータ圧縮技術は動き補償と呼ばれ、種々のビデオコーディングで重要な役割をしている。

ビデオ継起中の対象物の置換を予測するには数種の方法がある。一般に次の２つに大別される。即ち画素再帰アルゴリズム（例、Ａ、Ｎ−Ｎｅｔｒａｖａｌｉ　ａｔ　ａｌ、　Ｍｏｔｉｏｎ　Ｃｏｍｐｅｎｓａｔｅｄ　Ｔｅ１ｅｖｉｓｉ。

ｎ　Ｃｏｄｉｎｇ：　Ｐａｒｔ　Ｉ“ＢＳＴＪ　Ｖｏｌ、　５８．　ｐｐ、　６３１−６７０．　Ｍａｒｃｈ　１９７９；ａｎｄ　Ｋ、Ａ、Ｐｒｏｂｈｕ　ｅｔ　ａｌ−”Ｐａ１−Ｒｅｃｕｒｓｉｖｅ　Ｍｏｔｉｏｎ　ＣｏｍｅｎｓａｔａｄＣｏｌｏｒ　Ｃｏｄｅｓ”、　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＣＣ８２ｐｐ −２Ｇ、８．１．−２Ｇ、８．５．。

Ｐｈ１ｌａｄｅｌｐｈｉａ、　ＰＡ、　１９８２年６月、参照）およびブロックマツチングアルゴリズム（Ｊ、Ｒ，Ｊａｉｎ　ｅｔ　ａｌ、　”Ｄｉｓｐｌａｃｅｍｅｎｔ、　Ｍｅａｓｕｒｅｌ′ＩＩｅｎｔ　ａｎｄ　Ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　Ｉｎｔｅｒｆｒａｍｅ　Ｉｍａｇｅ　Ｃｏｄｉｎｇ”　ＩＥＥＥＴｒａｎｓ　ｏｎ　Ｃｏ＋ｎｍｕｎ、、　Ｖｏｌ、　Ｃ０Ｍ−２９，ｏｏ、　１７９９−１８０８．１９８１年１２月、参照）である。本発明に関連するのは後者のブロックマツチングアルゴリズムである。

ブロックマツチングアルゴリズムにおいては、現７レーム（つまり第２フレーム）が画素のブロックに分割される。例えばもし１ｙレ−ムが２５６　Ｘ　２５６画素なら、２５６個のＭＸＮブロックに分割される。この場合ＭとＮは共に１６画素である。ブロックマツチングアルゴリズムの目的は、現フレームにおける各画素ブロックに代わる置換ベクトルを得ることにある。置換ベクトルは前のフレーム（即ち第１フレーム）におけるブロック位置に相対するブロックの置換位置を示す。これらの置換ベクトルは次に、受信機が前の７レーム（第１７レーム）から現７レーム（第２フレーム）を形成することができるように受信機に伝送される。ビデオ会議のような比較的のろい動きのものに適用する場合は、多くの置換ベクトルはゼロである。

現フレーム中の画素ブロックの置換ベクトルを演算するために、現フレームのブロックと前のフレームの概してより大きなサーチエリア中に並べられた同サイズの多数のブロック各々との間で類否演算が行われる。現フレーム中の画素ブロックと前の７レーム中のサーチエリアにある画素ブロックは同一の中心を持っている。平均絶対誤差または平均二乗誤差のような誤差関数は、サーチエリア中の現フレームのブロックの各位置ニ関する類否測定として演算される。置換ベクトルは、サーチエリアの中心とそのサーチエリア中のブロックの中心との置換であって、こうすれば現フレームからのブロックと比較したとき最小限の誤差で済む。

より具体的には、前の７レーム中のサーチエリアは、サーチエリアの上方左側隅にある現７レームから１つの画素ブロックを置き、そのサーチエリア中のオーバーラツプされた画素に対する誤差（平均二乗または平均絶対の）を演算することにょって探索される。次に現フレームからのブロックはサーチエリアの右側領域に画素ごとに移される。各段階ごとにサーチエリアのオーバーラツプされた画素に対する誤差が演算される。現フレームのブロックは次に、各段階ごとにサーチエリアのオーバーラツプされた画素に対する誤差が演算されてサーチエリア中の画素の一列上に移され、ブロックが再度画素ごとにサーチエリアの左側領域から右側領域へ移される。現７レームからの画素ブロックは次に下の別の列へ左から右へ画素ごとに移される。

このプロセスは誤差関数（平均二乗または平均絶対の）がサーチエリア内で可能な全てのブロック位置を演算するまで続けられる（したがってフルサーチブロックマツチングアルゴリズムと命名された）。この演算された平均誤差が比較され、最小限誤差を出すブロック位置がそのブロックのための置換ベクトルを決定する。

上記のフルサーチブロックマツチング手順は、非常に多量の演算を必要とする。

例えば以下の仕様について考えてみる。

画面：　２５６Ｘ２５６画素フレーム速度：１５フレ一ム／秒現７レームにおけるブロックサイズ：ＭＸＮ、ただしＭ−１６，Ｎ−１６前の７レームのサーチエリアのサイズ：（Ｍ＋２７ＸＮ＋２Ｔ）、ただしＴ−８画素現フレーム内にある各ブロックのフルサーチ手順は、現７レームからの画素ブロックとサーチエリアからのオーバーラツプしている画素ブロックとを含める（２Ｔ＋　１）　２−２８９の大変な数の平均エラーの演算が必要とされる。かかるエラー演算の各々は、各プロ／り中には２５６５６画素から、２５５回の加算が必要である。１／１５秒間で２５６ブロ７りの現フレーム全部のタスクを完了するには、加算が逐次的に行われるとすれば８ビツトの加算機は３．５ナノセカンドで実行しなければならない。これは極めて厳しい高速度である。もし動き補償技術が５１２Ｘ５１２画素のＮＴＳＣ信号（上記のような２５６×２５６画素のものでなく）に適用されるとすれば、加算器の速度は０．４３７５ナノセカンドとなり、現在技術では明らかに達成できない高速となってしまう。さらに、画素値を記憶する記憶装置のアクセス時間はこの加算器の時間と同じオーダーである。かかるアクセス時間は現在技術で簡単に達成できるものではない。

このようなフルサーチブロックマツチング手順の厳しい演算要求に鑑み、何らかの高速だがフルサーチ方式でないアルゴリズムが提案されてきた。（例えばＪ、ｌ？、Ｊａｉｎ　ａｔ　ａｌ、　”ＤｉｓｐｌａｃａｒＱｅｎｔ　Ｍｅａｓｕｒｅｍｅｎｔ　ａｎｄ　Ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　Ｉｎｔｅｒｆｒａｍｅ　ＩｍａｇｅＣｏｄｉｎｇ”、　ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｃｏｍｍｕｎ、、　Ｖｏｌ、　Ｃｏｍ−２９，ｐｐ、１７９９−１８０８　Ｄｅｃ、　１９８１；　ａｎｄ　Ｔ、Ｋｏｇａ　ｅｔ　ａｌ、　”Ｍｏｔｉｏｎ　Ｃｏｍｐｅｎｓａｔｉｏｎ　Ｉｎｔｅｒｅｆｒａｍｅ　Ｃｏｄｉｎｇ　ｆｏｒ　Ｖｉｄｅｏ　Ｃｏｎｆｅｒｅｎｃｉｎｇ”、　ＮＴＣ８１Ｐｒｏｃ、　ｐｐ。

Ｇ５．３．１−Ｇ５．３．５．Ｎｅｗ　０ｒｌｅａｎｓ、　ＬＡ、　Ｎｏｖ、　２９−Ｄｅｃ、　３．１９８１参照）これらの単純化されたフルでないサーチ方式は演算の重荷を減らしたが、ブロックマツチングアルゴリズムの最適実現体を提供するものではない。フルサーチブロックマッチングズロシージャの実行こそあらゆるブロックマツチングサーチプロシージャ中で最上のものであることが認められている。遅いビット速度（例えば６４〜ｌ　２８　ｋｂ／５ｅｅ）のビデオにとって、フルサーチとフルサーチでないものとのアルゴリズム間では実行上の差が著しい。

Ｒｏｔｈ　ｅｔ　ａｌ、の“Ａ　ＶＬＳＩ　ｆｏｒ　Ｍｏｔｉｏｎ　Ｃｏｍｐｅｎｓａｔｉｏｎ”、　ｐｐ−１３゜１−１３．２　ＰＯ２８７に、フルサーチブロックマツチングアルゴリズムを実現化することができる超ＬＳＩチップが開示されている。

このチップは８×８ブロツクを処理するように設計されている。

このチップ内のデータ７ｃｍは、チップを相対的に大きなサイズにしてしまう多量のバッファ容量を必要としている。そのためＲｏｔｈ等の参考例の設計は、８ ×８画素より大きなブロックを処理するには実用的でないとされてきた。もし１６Ｘ１６ブロツクを処理することができるチップが要求されたなら、Ｒｏｔｈ等の技術は通常のコストを超えた高価なもので、また受け入れることができないような遅い処理となるサイズのチップになってしまう。

そこで、ビデオデータ圧縮のためのフルサーチブロックマツチングアルゴリズムを実行するための超ＬＳｒに実現可能な回路を提供することが本発明の目的である。また、８×８および１６Ｘ１６画素ブロックを効果的に取り扱うことができるブロックマツチングアルゴリズムを実現化するための適当なサイズ、適当なコストの超ＬＳ１回路を提供することも本発明のもう−つの目的である。

発明の要旨本発明は１実施例において、フルサーチブロックマ・ンチングアルゴリズムを実現化することができる一個の超ＬＳＴチ・／プに形成される回路である。この回路は小サイズで高速にすることができ、また高い並列処理を行うことができる高効率なデータ７０−設計で構成されている。

本発明によればフルサーチプロツクアマッチングルゴリズムを実現化する回路は現７レームからブロックを構成する画素値と、前のフレームのサーチエリアを成す画素値とを逐次受信する。したがってこの回路は、比較的少数のピンしか必要とせず、また比較的小さい場所しか必要としないから低価格である。

本発明の回路は、前のフレームのサーチエリア中の現７レームからのブロックの隣接位置をめる平均二乗または平均絶対誤差の演算並列処理が、膨大な数の共通な画素値入力を使用しているという事実に着眼し、これを利用する並列処理技術を用いたものである。したがって本発明によれば、多数の演算処理機構がサーチエリアにおける多数のブロック位置から生ずる平均二乗誤差または平均絶対誤差を並行して演算することができる。例えばサーチエリアの左側境界から右側境界まで画素ごとに水平に現フレームのブロックを動かすことによって到達したブロック位置の誤差（平均二乗または平均絶対の）を並行して演算できる。（換言すれば、サーチエリア中のブロック位置の１列に対する誤差が並行して演算される）。各々の演算処理機構が（前のフレームの）サーチエリア中の（現フレームの）ブロックの１位置につき誤差演算を行う。本発明の回路は、多数のブロック位置の誤差演算が並列処理できるように、現フレームと前の７レームの画素値を演算処理機構へ移送するための内部バス構造を持っている。第１パス構造は現７レームの画素値を演算処理機構へパイプラインで結ぶため使用され、第２バス構造は前の７レームの画素値を演算処理機構へ同報通信するために使用される。ブロック位置の１列について誤差演算が終了したら、ブロック位置の次の列につき並行して誤差演算が行われる。例えばサーチエリア中でブロックを１画素分下方に移すことにより生ずるブロック位置について行われるのである。サーチエリア内のブロックの各位置について誤差演算が完了したら、どのブロック位置が最小限の誤差を生み出したかを判定することによってそのブロックのベクトル置換が決定される。

この回路は次に、ベクトル置換が現フレーム中の全ブロックにつき得られるまで現７レーム中の次のブロックを処理するために使用される。

このようにして画素値の逐次入力と効率的なデータフロー設計が小サイズのチップに結晶し、誤差値の並行演算が、適切な速度基準に合致する、即ち１５フレ一ム／秒のシステムで、１／１５秒の間に全ベクトル置換を演算する１個のチップを提供するのである。

図面の簡単な説明第１図は送信機から受信機へ送信されるビデオフレームの順番を概略示すものである。

第２図はブロックマツチングアルゴリズムを実行するための、現時点のビデオフレームからのブロックと、前のビデオフレーム中のサーチエリアとを概略示すものである。

第３図は現フレームの１ブロツクが前のフレームのサーチエリア内に占めることができる位置を示す。

第４図は本発明の１実施例に従ったブロックマツチングアルゴリズムを実現するための回路を概略示す。

第５図は第４図の回路のためのタイミングダイヤグラム。

第６図は第４図の回路のアドレスジェネレータを概略示す。

第７図はこのアドレスジェネレータが実行した境界翻訳を概略示す。

第８図は第４図の回路を構成する多数のパラレルプロセッサのうちの１プロセツサの概略図である。

発明の詳細な説明第１図は送信機（図示せず）から受信機（図示せず）へ送信されるビデオフレームの順番を概略示している。図面上、フレームは２５６Ｘ２５６画素から成り、１秒間に１５フレームが送信される。

上述したようにビデオ会議に適用する場合は、■場面中の動きは通常遅く、連続的な７レームは膨大な量の繰り返し情報を有している。そこでインターフレームコーディング技術が連続的なフレーム間の繰り返し情報を圧縮して有意義なデータを達成するために用いられる。

上述したように、ここでの関心事項は、動き検出と動き補償として公知のデータ圧縮技術である。もし第１図のフレーム１とフレーム２間に置換ないし対象物の動きによって違いが引き起こされたが、この違いはフレームの相対的に小領域に限定されたものであるときは、フレーム２の全データを受信機に送信することは不要である。そうしないで置換された情報のみを受信機に送信すれば足りる。そうすれば受信機は７レーム１からフレーム２を構成するのにその置換された情報を使用すればよい。

上述したように、置換情報はブロックマツチングアルゴリズムによって得ることができる。ブロックマツチングアルゴリズムは７レーム２内の画素の１ブロツクと、７レーム１のサーチエリア内に並んだ同サイズの多数のブロック間の類否を測定するものである。こうして第１図に示すように、７レーム２は各々がＭＸＮの画素を有する多数のブロックに分割される。図面上、ＭとＮは共に１６である。７レーム２内の画素の各ブロックに対して、プロ７クマツチングアルゴリズムは、７レーム１中の位置から７レーム２中の位置へのブロックの置換を示す置換ベクトルを付与する。このように動き補償ビデオデータ圧縮アルゴリズムを実現するためには、７レーム２中の画素の各ブロックに対する置換ベクトルを演算することが必要である。次にこの置換ベクトルがフレーム■からフレーム２を構成するため置換ベクトルを用いる受信機へと送信される。

第２図は７レーム２（即ち現時点のフレーム）からの画素ブロックとフレームｌからのサーチエリアとの概略図である。第２図においてエリアＡは現フレームからの画素の１ＭｘＮブロックを表し、エリアＢは前のフレームからのサーチエリアを表している。Ｂのエリアは（Ｍ＋２ＴＸＮ＋２Ｔ）である。ただし図面上Ｔは８画票である。ブロックＡとブロックＢは同一中心を持っていることに留意されたい。ブロックＡがサーチエリアＢ内で取ることができる位置が第３図に示される。第３図においてブロックＡの水平方向における各シフトは、１画素のシフトであって、ブロックＡの垂直方向における各シフトも１画素である。Ｔ−８のときブロックＡは１６画素の横幅でありサーチエリアは３２画素であるから、ブロックＡはその各位置を隣接する１画素ごとに水平方向にシフトすることによって異にする１７種の位置を第３図の最上列において取ることができる。

サーチエリアＢ内におけるブロックＡに最適な位置を決定するためには、例えば第３図に示したサーチエリアＢ中におけるブロックＡの各々可能な位置のブロックＡの画素値とサーチエリアＢのオーパーラ７プする画素値との間の平均絶対誤差または平均二乗誤差を演算することが必要である。こうしてサーチエリアＢ内でのブロックＡの最適な合致を見付は出すために式：の誤差関数（２Ｔ＋１）ａを演算することが要求される。サーチエリアＢ中のブロックＡの各位置、即ちサーチエリア内の各画素シフト（水平方向の）と各行シフト（垂直方向の）をめるため１つの誤差関数が演算されるのである。

上記等式において、ａ（ｋ、１）はブロックＡ申の画素値を、ｂ（ｋ、ｌ）はサーチエリアＢ中の画素値を表す。値ｍ、、ｍ、はサーチエリアｂ内でのブロックＡの置換を示す。

したがって、−Ｔ≦ｍｋ、ｍ、≦Ｔまただし例えばＴ−８画素このように第３図の上段左隅に、ｍ　ｋ”＝　８　＊　ｍ　１””　８の位置にブロックＡがくるようにされ、この場合のｎｌ　、は第３図の対応するブロック位置のダイヤグラムの下欄の数式に示され、ｌ　ａ　（ｋ　、ｌ　）　ｂ　（ｋ　＋　ｍ　＞　、　１　＋　ｍ　ｔ　）　Ｉである。また、上記等式においてｐ−１は平均絶対誤差を、ｐ−２は平均二乗誤差を示す。

サーチエリアＢｃｂのブロックＡの各位置につき誤差が演算されたら、それら誤差が比較され、最小誤差をもたらしたブロックＡの位置が同定される。するとブロックＡのこの位置に対応する値ｍ　＞　Ｔ　ｍ　１が、ブロックＡのための置換ベクトルを表す。

同様に現フレーム内の各ブロック（第１図参照）について置換ベクトルが演算される。

サーチエリアＢ中のブロックＡの隣接位置の誤差演算が膨大な量の共通の画素値入力を利用していることは明らかである。

本発明は、多数の並行するブロック位置についての誤差関数を演算するため、これを利用しているのである。

このように本発明の１実施例においては、サーチエリアＢ内のブロックＡの位置の全体の列をめることができる誤差関数を並行に演算するための回路が設けられている。この回路は例えば、第３図の各列中のブロックＡの１７つの位置中の１つをめる誤差関数を演算するため各々採用された１７個のパラレルプロセッサを有している。好ましくはこの回路は、１個の超ＬＳＩチップに構成されるのがよい。

本発明によるフルサーチブロックマツチングアルゴリズムを実現する回路１００が、第４図に示される。第４図において回路１００は、１７個のプロセッサＰＥ、、ＰＥ□０．−ＰＥ１ｍで構成されている。これらのプロセッサは、各々１つのブロック位置をめる誤差関数演算プロセッサによって、第３図中のブロック位置の１列をめる誤差関数を並行して演算する。かかる並列処理能力は、このブロックマツチングアルゴリズムをして全７レームに真速で実行されることを可能にする。プロセッサＰＥ　、、、、　Ｐ　Ｅ　、、のうちの１つが第８図に示され、以下に説明される。現フレームのブロックからの画素値が入力１１０で逐次受信される。前のフレームのサーチエリアからの画素値は、入力１２０と１２２で逐次受信される。これらの画素値は逐次に受信されているので、回路１００を実現する超ＬＳＩチップは比較的少ない数のピンで足り、したがってサイズおよびコスト的に妥当なものができる。

バス構造１３０は現フレームのブロックからこれらプロセッサへ画素値を分配するのに用いられる。バス構造１４０は前の７レームのサーチエリアからこれらプロセッサへ画素値を分配するのに用いられる。これらバス構造１３０．１４０につき以下に詳述する。

第４図の回路１００は、２個のフレーム格納記憶装置（囚示せず）と協働している。１個のフレーム格納記憶装置は前の７レームの画素値を格納し、もう１個の７レーム格納記憶装置は現７レームの画素値を格納する。

第４図の回路１００中のデータの７０−について考察する前に、次のアドレス指定体系について考えることが有益である。

第２図及び第３図において、ブロックＡの上段左隅の画素は基底アドレスＩ　、、Ｊ、で表されている。ブロックＡ由のその他全ての画素アドレスは、１．、Ｊ、に対する１１＋１．Ｊ１＋ｊの式で表されている。したがってもしブロックＡが１６Ｘ１６なら、そのブロック内の下段右側の画素はｒ、＋１５．Ｊ、＋１５のアドレスを持つことになる。第３図において、影斜線のエリアＦ　、、、、Ｆ　、、は、ブロックＡの位置の１列と関係するサーチエリアＢの部分を表す。例えばゾーンＦ１．は、サーチエリア内のブロックＡの位置の最下列と関係している。各ゾーンＦの上段左隅は、基底アドレスＩ　ｔ−、Ｊ　ｂを持つ。サーチエリアの特定のゾーン中のその他の全アドレスは、式Ｉ　、、＋　ｉ　、Ｊ　、＋ｊで基底アドレスに対するものとして表されている。したがつて例えば、ゾーンＦ、中の上段左側の画素は基底アドレスエ、。

Ｊ、を持っており、そのゾーン中の下段右側の画素は■５＋１５、Ｊｉ−＋３１のアドレスを持っている。このアドレス体系は、サーチエリアＢ中のブロックＡの位置の各列をめて並行に誤差関数演算をしている間は、基底アドレスに何等の変化も起こさないということを意味する。回路１００のアドレスジェネレータ１５０は、式１．＋ｉ、ｚ、＋ｊとｒｉ、＋ｉ、Ｊ、＋ｊのアドレスを７レーム格納記憶装置（図示せず）へ送信し、咳フレーム格納記憶装置は第４図の回路１００の入力１１０．１２０．１２２へ画素値を送信する。、１（１，＋ｉ、Ｊ、＋ｊ）は現フレームのブロックからの画素値、ｂ（Ｉ　ｂ、　＋　ｉ、Ｊ　ｂ　＋　Ｊ）は前の７レームのサーチエリアからの画素値である。アドレスジェネレータ１５０を形成する回路を第６図に概略示し、以下に説明する。

画素値が入力１１０．１２０．１２２に到達する順番を有する回路１００のデータ７０−は、第５図のデータ７０−タイミングダイヤグラムを見れば理解される。特に第５図は、例えば第３図の最上列のようなサーチエリアＢ中のブロックＡの位置の１列をめる誤差関数の並行演算に関係するデータ７０−を提供している。したがってここに記述されたフルサーチブロックマツチング手順は、第３図の最上列で発しその最下列に終わるサーチエリアＢ中のプロ７りＡの位置の各列をめる第５図のデータ７０−シーケンスを繰り返すことを要求するものである。第５図において基底アドレスは簡略を期して省略されていることに留意されたい。

基底アドレスは、第５図の全データフローシーケンスを通して常に同一であるから、第５図において基底アドレスを省略してもよい。しかし実際には、第５図の各アドレスは索引は勿論、基底アドレス（図示せず）も有している。

第５図の第１欄はサイクル数の形式で時間を示している。同第２１１は各サイクル中で受信する入力を示し、ａ（ｉ、ｊ）は現７レームのブロックからの画素値を表し、ｂ（ｉ、ｊ）は前の７レームのサーチエリアからの画素値を表す。８５図のデータ７０−シーケンスの最初の１６サイクルと最後の１６サイクルは衆いて、１つの画素値ａ　（ｉ　ｌ　Ｊ　）は、各１サイクルごとに（入力１１０経由で）現フレームから入力され、２つの画素値が各サイクルごとに前のフレームから入力される。即ち入力１２０経由でｂ（ｉ、ｊ）、入力１２２経由でｂ（ｉ −１，ｊ＋１６）である。第３欄は各サイクルごとにＰＥ０が実行する演算を示すもので、第４欄は各サイクルごとにＰＥ、が実行する演算０．。

そして最後の欄は、各サイクルごとにＰＥ１６が実行する演算を示している。各プロセッサＰＨ，。、、ＰＥ＋ｓは、プロセッサが実行する全演算の算出値を累算することができるように、１個の累算器（第８図）を有している。したがって例えばＰＥ、は、第５図の第３欄に列挙されたその演算の全結果を累算する（即ち加算する）ことによってその誤差関数を演算する。

第４（！Ｉの回路１００を通じるデータ７０−シーケンスにつき第５図に補助されながら詳細に述べる。図において、このデータフローシーケンスは、まづ＠３］の最上列中のブロックＡの位置をめて実行され、次に第３図のブロックＡの位置の各列をめて繰り返される。

（ａ）サイクルＯでは、ａ（０，０）とｂ（０，０）とが入力１１０．１２０経由で各々入力される。プロセンサＰＥ、は１ａ（０，０）−ｂ（０，０）１を演算すると、ａ（０、Ｏ）がバス構造１３０の一部を構成する遅延素子、即ち遅延クリップ７０ツブＤＦＦ　Ｄ　１でラッチされる。

（ｂ）サイクル１では、ａ（０，０）とｂ（０，０）とが入力】１０．１２０経由で各々入力される。ｂ（０，０）はバス構造１４０を使ってプロセッサＰＥ、、ＰＥ、へ同報通信され、ａ（０，０）はバス構造１３０上にパイプ結合される。すると１ａ（０゜０）−ｂ（０，０）１がプロセッサＰＥ、で演算され１ａ（０，０）−ｂ（０，０）１がプロセッサＰＲ□で演算される。またａ（０，０）が遅延７リツグ７０ツブＤＦＦ、、でラッチされ、ａ（０、■）が遅延クリップ７０ツブＤＦＦ、□でラッチされる。

（ｃ）サイクル２では、ａ（０，２）とｂ（０，２）とが入力１１０．１．２０経由で各々入力される。ｂ（０，２）はバス構造１４０経由でプロセッサＰＥ、、ＰＥ□、ＰＨ２へ同報通信され、ａ（０，０）はバス構造１３０上にプロセッサＰＥ２へパイプ結合され、するとｌ　ａｃｏ、２）−ｂ（０，２）１がプロセッサＰＥ０で演算され、１ａ（０，１）−ｂ（０，２）１がプロセッサＰＥ、で演算され、１ａ（０，０）−ｂ（０，２）ｌがＰＥ２で演算される。

またａ（０、Ｏ）が遅延フリップ７０ツブＤＦＦ、３でラッチされ、ａ（０，１）が遅延フリップ７０ツブＤＦＦ、□でラッチされ、ａ（０，２）が遅延７リツプ７０ンプＤＦＦ、□でラッチされる。

このシーケンスはサイクル１５まで行われる。サイクル１６からは前のフレームからの２つの画素値が入力され、該当するプロセッサへ同報通信される。第５図に示すサイクルの全セットを通じてａ（ｉ、ｊ）が、１つのプロセッサから次のプロセッサへ遅延フリップ７０ツブＤ　Ｆ　Ｆ　、、、、、Ｄ　Ｆ　Ｆ　、、を介しバス構造１３０経由で逐次パイプラインされる。

（ｄ）サイクル１６ではａ（１，０）が入力１１０経由で、ｂ（］、Ｏ）が入力１２０経由で、モしてｂ（０，１６）が入力１２２経由で各々入力される。ｂ（１，０）はバス構造１４０を介してプロセッサＰＥ、へ同報通信され、ｂ（０，１６）はプロセッサＰＥ、、Ｐ　Ｅ　ｚ、、、Ｐ　Ｅ　＋ｓへやはりバス構造１４０を介して同報通信される。（バス構造１４０の詳細な説明は後述する）　次に１ａ（０、Ｌ５）−ｂ（０，１６）１がプロセッサＰ　Ｅ　、、、、で演算され、１ａ（０、Ｏ）−ｂ　（０，１６）１がプロセッサＰ　Ｅ　ｘ　ｓで演算される。

（ｅ）サイクル１７ではａ（１、ｉ）が入力１１０経由で、ｂ（１，１）が入力１２０経由で、モしてｂ（０，１７）が入力１２２経由で各々入力される。ｂ（１，１）はバス構造１４０を介してプロセッサＰＥ、％ＰＥ、八同報へ信され、ｂ（０，１７）はプロセッサＰ　Ｅ　、　、、、Ｐ　Ｅ□６へやはりバス構造１４０を介して同報通信される。次に１ａ（１，１）−ｂ（１，１）１がプロセッサＰ　Ｅ　ｏで演算され、１ａ（１，０）−ｂ（１，１）１がプロセッサＰＥ、で演算され、１ａ（０，１５）−ｂ（０，１７）１がプロセッサＰＥ、で０１．そして、１ａ（０，１）−ｂ（０，１７）１がプロセッサＰＨ□６で演算される。

サイクル２５５の完了時点で、プロセッサＰＥ０はＩ誤差関数計算のための画素値を受信することを止める（例えばＡにおける位置ブロックが第３図の上方左隅を占める）。次の１６サイクル内に、プロセッサＰＥ、〜ＰＥ、、はその対応する誤差関数計算のための画素値を受信することを完了する（例えば第３図の最上列中のブロックＡの位置の残りのために）。久方画素値を受信後の数サイクルがプロセッサで行われると、そのプロセッサは完了した誤差関数計算結果を出す。

するとこの誤差関数計算結果は比較器１６０へ転送される。比較器１６０については後に詳述する。

次に第５図のサイクル０〜２７１のシーケンスが、第３図の各列につき繰り返される。特に、プロセッサＰ　Ｅ　ａ、−、Ｐ　Ｈ＋ｓの最も効率的な利用のために、第３図のブロック位置の１列のためにサイクル１６Ｘ１６＋ｏ、、、１６Ｘ１６＋１５　（即ちサイクル２５６から２７１まで）を実行し、このとき興時にブロック位置の次の列のためにサイクル０．、、Ｉ５が実行することが望ましい。この可能性は第５図に簡単に見付けることができる。

例えばサイクル１６Ｘ１６−２５６は、サイクル０がプロセッサＰＥｏＬか使わないとき、プロセフすＰＥよ、、、Ｐ　Ｅ　ｘ　ｅ　Ｌか使っていない。このように第４図の回路１００の効率性は１００％に近いものとなる。現フレームから１６Ｘ１６ブロツクツ　を各々処理するには４３５２サイクル行われる。サーチエリアＢにおけるブロックＡ中の各位置につき、第３図が誤差関数を演算するプロセッサとその誤差関数が演算されるサイクルとを示している。

もし回路１００が１７１５秒で２５６の１６Ｘ１６ブロツクを処理しなければならず、各ブロックにっき４３５２サイクルが必要であるとすれば、サイクル時間は５６ナノセカンドのオーダーになる。このことは、もしこのフルサーチブロックマツチングアルゴリズムが並列地理ではなく順次処理を用いて実行されていれば、約３ナノセカンドというサイクル時間で足りる事実を見ればその違いが明らかである。３ナノセカンドのアクセス時間を実現できるメモリ７１ミリ−は販売されていない。

誤差関数がプロセッサＰ　Ｅ　＠−＋＋Ｐ　Ｅ　＋ｓで演算されたら、どの誤差関数が最小なものかを判定するため、その誤差関数を比較する必要がある。この比較は第４図の比較器１６０が行う。比較器１６０は２つの比較回路ＣｏとＣ□ とから構成されている。

比較回路Ｃｏ、ＣＩは各々トライステートバッファ（バッファ。、バッファ□）、最小値格納バッファ（最小値。、最小値、）、および比較器（比較器。、比較器、）を持っている。誤差関数がプロセッサＰＥ０．．．ＰＨ□６のいずれかによる演算によって分かったら、同誤差関数はトライステートバッファと比較回路Ｃ０、ＣＩの１つの比較器へ送られる。もしその新たに入手した誤差関数が最小値バッファ（最小値。または最小値□）中に既に格納されている値より大きいときは７ラグ（フラグ。またはフラグ、）がゼロで、該最／４％値バンファに格納されている値は変更されない。

一方、もしその新たに入手された誤差関数が最小値格納バッファ（Ｍ■Ｎ□またはＭＩＮＯ）に格納されている値よりも小さいときは、フラグ（ＦＬＡＧ　ｏまたはＦＬＡＧ　１　）が１に等しくなりトライステートバッファ（ＢＵＦＦＥ！？　。またはＢＵＦＦＥＲ□）がその新たな誤差関数でＭＩＮＯ８よびＭＩＮ□ の値が置き換えられる。こうしてバッファＭＩＮ０またはＭＩＮ□は、常にＣ８およびＣ□が受信した最小誤差関数を格納する。なぜ２つの比較回路Ｃ０およびＣ１を用いるかにつき以下に説明する。

プロセッサがその誤差関数演算を終了したら、その結果がプロセッサＰＥ０、Ｐ　Ｅ　ｒ、−、Ｐ　Ｅ　、、から第４図の比較機構１６０の一部を成して連係するトライステルトバッファ装置ＴＲＩＢＵＦｏ、ＴＲＩＢＵＦ　ｘ　−、、ＴＲＩＢＵＦ　ｘ　ａへ転送される。プロセッサＰＥ、、、、Ｅ’Ｅ□６は１７サイクル時間で次々と誤差関数演算を終了するものであることに留意されたい。こうしてイネーブル信号ＥＮ、がトライステートバッファ装置ＴＲｒＢＵＦ　ｏ　− 、ＴＲｒＢＵＦ　ｘ　ｅを順次に使用可能にする。このイネーブル信号ＥＮ１は、トライステートバッファ装置ＴＲＩＢＵＦ、、ＴＲＩＢＵＦ、　、、、ＴＲＩＢＵＦｌ　ｇカ指定時ニ使用可能になるように遅延クリップ７０７プ１６１の連鎖を通る。例えばトライステートバッファ装置ＴＲＩＢＵＦ、はＴＲＩＢＵＦ、の１サイクル後に使用可能にされる。一方、新たに演算された誤差関数が１サイクルに１回の割で到達し、比較回路Ｃ８とＣ１が比較と置換プロシージャのため２サイクルを要求する。このため２つの比較回路Ｃ０とＣ０とが用いられているのである。したがって偶数のトライステートバッファ装置ＴＲｒＢ（ＪＦ、、、、ＴＲＩＢＩＪＦ、　＠は共通ハス１６２へ接続され、奇数のトライステートバッファ装置ＴＲＩＢＵＦ、、ＴＲＩＢＵＦｘ、、、ＴＲＴＢＵＦ＋ｓは共通バス１６３へ接続される。

共通バス１６２は偶数のプロセッサの誤差関数を順次比較回路Ｃ０へ転送し、共通バス１６３は奇数プロセッサの誤差関数を比較回路Ｃよへ順次転送する。こうして各比較回路Ｃ０とＣ１は２サイクルごとに１つの誤差関数を受信することになる。すると比較回路Ｃ０とＣ１は誤差関数が到達するたびに比較と置換のプロシージャを行う。

１７の誤差関数の群が比較回路Ｃ０とＣ１により処理されたら、（遅延７リツプ７０ツブＤＦＦ１６１と１７１を経由して）イネーブル信号ＥＮ□がＢＵＦＦＥＲ２に到達し、これでＭＩＮ、に格納された値を比較回路Ｃ０内のＣＯＭＰＡＲＡＴＯＲｏに転送できるようにする。２サイクル後にＭＩＮｏとＭＩＮ□の小さい方の値が、次の処理に備えてＢＵＦＦＥＲ，に格納される。

ＭＴＮ、とＭＴＮｘニ格納された値は、プロセッサＰＥ、、−、、ＰＥ３．が演算した比較回路Ｃ６とＣＩから受信した誤差関数であって１７の誤差関数の最後の群中の最小のものとは限らないこと、むしろブロックが現時点でマツチしている限り、比較回路Ｃ０とＣＩが受信した最小誤差関数を含むものであることに留意されたい。しかし、第３図のブロック位置の各列についての誤差関数が演算され比較機構１６０により処理されたら、ブロックがマツチされるにつきめられる最小の誤差関数がＢＵＦＦＥ３中に存在する。また各プロセンサは、どのブロック位置につき誤差関数を演算したのであるかにつき知っていることを留意されたい。したがってブロック位置（例えば上記の座標ｍ、、ｍ＋）は、最小誤差関数が決定されたとき置換情報を即座に得ることかでさるように、誤差関数と共に出力される。

以下にアドレスジェネレータ１５０につき詳細に説明する。

第６図はアドレスジェネレータの概略図であるが、例えば■１＋ｉ、Ｊ、十ｊ、ｒ、＋ｉおよびＪｂ＋ｊの各アドレスは、例えばｒ、、Ｊ、という基底アドレス、および例えばｉ＋Ｊという指標とから構成されている。基底アドレスは基底アドレスジェネレータ１５２によって作り出され、指標は指標ジェネレータ１５４によって作り出される。

境界状態翻訳回路１５６は次のような問題を解決する。現７レームからのブロックがフレーム境界上にあるときどんなことが起こるか考えてみると、例えばそのブロックが第１図でＡ′の印が付けられたものとする。第７図に示すように、ＭＸＮブロックがそのブロックと同一の中心点を持つ（Ｍ＋２ＴＸＮ＋２７）のサーチエリアを持つようにサーチエリアが定義されたとき、現７レームのブロックＡ′をめるサーチエリアＢ’（第７図の水乎のハツチング部分）は、前の７レームの外側に伸びている。したがって、サーチエリアＢ′の右側部分はｗｃｊ図に示すようにフレーム境界の外側になっている。境界状態翻訳回路１５６は、フレーム境界の内側に位置するようにフレーム境界の外側に伸びるサーチエリアＢ″ やその他のサーチエリアを成すアドレスを翻訳する。こうしてサーチエリアＢ′ は、第７図中Ｂ”と示されたサーチエリア（垂直のハンチング）に翻訳される。

このサーチエリアＢ”はフレーム境界の完全に内側ある。この境界状態翻訳回路１５６は、サーチエリアがフレーム境界を越えないときは何も為さない。

アドレスジェネレータ１５０の指標ジェネレータ１５４により作り出される指標と、基底アドレスジェネレータ１５２により作り出される（翻訳をする場合としない場合がある）基底アドレスとは加算器１５８によってアドレスＩ　＋　＋　Ｉ　、　Ｊ　、　＋　ｊ及びＩ　ｂ　＋ｊ　ｓ　Ｊ　ｂ　”　ｊを作るため加算される。これらのアドレスは次に、対応する画素値ａ（１，＋ｉ％Ｊ、＋ｊ）及びｂ（Ｉ　。

＋ｉ、Ｊ、、＋ｊ）を検索するため上記の７レーム格納バツフアに転送される。

次に第４図のバス構造１３０．１４０につき詳細に説明する。

上記の通りバス構造１３０は遅延クリップ７０ツブＤＦＦ　、□９．。

ＤＦＦ　、□５の連鎖で構成されている。現フレームからの画素値（ａ（ｉ、Ｄの）が、指定時に指定のプロセッサに到達するように１つの遅延７リツプ７０ツブから次のそれへとバス構造１３０を経て転送される。

バス構造１４０は、前の７レームからの画素値ｂ（ｉ、ｊ）を上から、またｂ（ｉ−Ｌ、ｊ　＋１６）を下から指定のプロセッサ八同報通信するものである。この性質は第４図の回路が超ＬＳＩで構成されるときシリコンの多大なエリアを節約する。しかしバス構造１４０は、ｂ（ｉ、ｊ）が指定のプロセッサへ伝送されｂｉ−１，Ｊ＋１６）が指定のプロセッサへ伝送されるように適切な時、適切な場で、２つのサブバスへと分割されなければならない。特に第５図でサイクル１６で始まる各列は縦線も含んでいる。画素値ｂ（ｉ、ｊ）は線の右側のプロセッサへ伝送され、画素値ｂ（ｉ　−１、ｊ　＋　１６）は線の右側のプロセッサへ伝送される。このバス構造１４０は、バス構造１４０のパストランジスタ１４２の１つをオフにするため１６サイクルごとにキー信号を送ることによって分割される。パストランジスタ１４２の１つがオフにされたときは、バスの上方（つまり入力１２０）からくるデータとバスの下方からくるデータとはオフにされたパストランジスタ１４２を通過して伝播することができない。このキー信号はアドレスジェネレータ１５０に組み込まれた論理（図示せず）によって作り出される。キー信号はＤＦＦｔ。

からＤＦＦｔ＋ｓへサイクルごとに適切な時に適切なパストランジスタ１４２をオフにして伝播する。

次にプロセンサＰＥ−、、、ＰＥ＋ａについて詳細に説明する。プロセンサの１つについて第８図に概略示す。第８図のプロセッサは３つの機能ブロックで構成される。減算器１８５が画素値ａ（ｉ、ｊ）とｂ（ｉ、ｊ）を受信し、その差を演算する。すると絶対値回路１８６が減算器回路の結果の絶対値を取り込み、同絶対値は累算器１８７で累算される。こうして累算器１８７は第５図の該当する欄内の演算全部を加算する。第８因のプロセンサは平均絶対エラーを計算するものであることに留意されたい。

そうでなくて平均二乗エラーが演算される場合もあるが、このときは二乗回路が第８図の絶対値回路１８６に置換する。

要するに完全サーチブロックマッチングアルゴリズムを実現する回路について述べてきた。現フレームのブロックと前の７レームのサーチエリアとの画素値が回路に順次受信されている。

次にこれらの画素値はバス構造によって複数のプロセッサへ分配される。これらのプロセッサは前のフレームのサーチエリア中の現７レームのブロックの位置の群をめる誤差関数の群を並行して演算する。この回路は非常に高効率であるが１個の超ＬＳＩチップで実現することが可能である。

なお、不発明の上記実施例は単に説明を目的としたものに過ぎず、無数の代替実施態様が本発明の請求範囲の趣旨に外れないで肖業者が実施可能である。

第１図第２図第３図第４図第６図第７図第８図国際調査報告国際調査報告

Claims

【特許請求の範囲】

１．現ビデオフレーム中の画素のブロックから画素値を逐次受信する第１入力手段と、前のビデオフレームのサーチエリアから画素を逐次受信する第２入力手段と、上記サーチエリア中の上記ブロックの位置群に対応する誤差関数群を並行して演算する複数のプロセッサと、上記ブロックから逐次受信した画素値を該プロセッサへ移送する第１パス構造と、上記サーチエリアから該逐次受信した画素値を該プロセッサへ移送する第２パス構造と、上記誤差関数を比較する比較器と、を特徴とするフルサーチブロックマッチングアルゴリズム実現回路。
２．第２入力手段が、上記サーチエリアからの画素値を逐次受信する２つの別個の入力で構成されている請求項１の回路。
３．第２バス構造が、上記２つの別個の入力間に渡されている請求項２の回路。
４．第２バス構造が、第２バス構造を第１と第２のサブバス構造に分割する手段を持つ請求項３の回路であって、該第１サブバス構造に上記２つの別個の入力中の１つを経由して受信された画素値を上記１または２以上のプロセッサから成る第１群に同報通信させ、また該第２サブバス構造に上記２つの別個の入力の他方から受信した画素値を上記１または２以上のプロセッサから成る第２群へ同報通信させることを特徴とするもの。
５．第１パス構造が、上記ブロックの画素値をバイプラインで上記の各プロセッサに結ぶ一連の遅延素子から成る請求項１の回路。
６．回路が１個の超ＬＳＩチップ上に実現された請求項１の回路。
７．回路がさらに、画素値アドレスを作り出すアドレスジェネレータを持っている請求項１の回路。
８．回路の第１入力でブロックの画素値を逐次受信し、同回路の第２第３入力で上記サーチエリアの画素値を逐次受信し、同回路の一部を成す複数のプロセッサによって、上記サーチエリア中の上記ブロックの位置群に対応する誤差関数群を並行して演算し、誤差関数を比較する、ことを特徴とする前のビデオフレームのサーチエリア中の現ビデオフレームからのブロックの位置に最適に合致するものを見付け出すフルサーチ法。
９．現ビデオフレーム中の画素のブロックから画素値を逐次受信し、前のビデオフレームのサーチエリアからの画素値を逐次受信する入力手段と、上記入力手段で上記ブロックから逐次受信した画素値および上記サーチエリアから逐次受信した画素値に応答して、上記サーチエリア中の上記ブロックの位置群に対応する誤差関数群を並行して演算する複数のプロセッサと、上記誤差関数を比較する比較器と、を特徴とする画像伝送を目的としたフルサーチブロックマッチングアルゴリズムの実現回路。
１０．上記現フレームから逐次受信した画素値を上記プロセッサへ移送する所の、上記入力手段を上記プロセッサに接続する第１バス構造と、上記サーチエリアから上記逐次受信した画素値を上記プロセッサへ移送する所の、上記入力手段を上記プロセッサへ接続する第２バス構造と、から成る請求項９の回路。
１１．比較手段が、各々上記プロセッサの１つに接続された逐次使用可能なバッファと、該バッファに接続された比較回路と、を有する請求項９の回路。
１２．比較手段が、上記バッファの偶数のものに接続された第１比較回路と、上記バッフアの奇数のものに接続された第２比較回路とから成る請求項１１の回路。
１３．上記入力手段に画素を検索するアドレスジェネレータが付加され、サーチエリアのアドレスがフレーム境界の内側に位置するようにフレーム境界の外側のサーチエリアのアドレスを翻訳する境界翻訳回路を有する請求項９の回路。
１４．上記ブロックから逐次受信した画素値を上記プロセッサへ適用する一連の遅延素子を有する第１バス構造と、上記サーチエリアから逐次受信した画素値をそこへ適用する所の、バス構造の２つの別個の入力を上記プロセッサへ接続する第２バス構造とが付加されている請求項９の回路。
１５．上記別個の入力の一方または他方から上記プロセッサのあるものへの画素値の伝播を阻害するため、上記第２バス構造を分割する手段が付加されている請求項１４の回路。