JPH01295379A - ブロツクマツチング型動き検出回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔目　次〕 概要 産業上の利用分野 従来の技術（第６図〜第９図） 発明が解決しようとする課題 課題を解決するための手段（第１図） 作用 実施例（第２図〜第５図） 発明の効果 〔概　要〕 動きのある対象における動きの量を検出するためのブロ
ックマツチング型動き検出回路に関し、参照データメモ
リへのデータアクセスを高速にせずにアクセスポート数
を減らすことを目的とし、現ブロックと各参照ブロック
との相関を演算するとともに参照ブロックのデータを保
持する複数の相関演算ユニットを二次元的に配列してな
り、外側の相関演算ユニットにおいて参照ブロックを構
成する画素における４方向または３方向のいずれか１方
向のデータを選択して前フレームの画像信号によって更
新するとともに、更新された参照ブロックを選択された
方向と逆の方向に各相関演算ユニットを逐次シフトする
ように構成し、各相関演算ユニットにおいて入力参照ブ
ロックと現ブロックとの間で相関演算を行って相関の大
きさを示す信号を発生ずる相関演算回路と、相関演算回
路における相関の大きさを示す信号中最大のものを検出
するとともにこれに対応する参照ブロックと現ブロック
との動きを示す動きベクトルを発生する最小値検出回路
とを備えて構成される。

〔産業上の利用分野〕

本発明は画像信号を対象とする高能率符号化技術に係り
、特に動きのある対象における動きの量を検出するため
のブロックマツチング型動き検出回路に関するものであ
る。

画像信号の高能率符号化方式においては、動き補償予測
方式を用いて画像を前フレームとの差分と動きの量を示
す動きベクトルとに分解して伝送することによって、伝
送すべき情Ｉ［ｔを圧縮する方式が用いられる。

またこのような動きの量の検出は、物体や人物の追跡シ
ステム等における動きのある対象の動きの量を検出する
回路や、放送等で用いられる画面ゆれ補正装置における
カメラのゆれの量を検出する回路等において必要となる
ものである。

画像信号における対象の動きの量を検出する動き検出回
路は、参照データメモリからのデータ転送速度を上げる
ことなく、アクセスポート数を減らすことができるもの
であることが要望される。

〔従来の技術〕

高能率符号化方式においては、対象の動きを検出するた
めにブロックマツチング型動き検出方式第６図はブロッ
クマツチング型動き検出方式を説明するものであって、
（ａｌは現フレームを示し、（ｂｌば前フレームを示し
ている。

すなわち現フレーム中のあるブロック（現ブロック）が
、時間方向の相関が大きい前フレーム中のどのブロック
と最も相関が大きいかを検出することによって、動きの
量が測られる。連続するフレーム間においては物体の動
きは小さいと考えられるので、現ブロックの１フレーム
前のブロックを中心ブロックとして、斜線を付して示し
たその近傍を参照範囲としてこの範囲を探索して、相関
の最も大きいブロック（最適ブロック）を求める方法が
用いられる。

第７図はブロックマツチング型動き検出における参照ブ
ロックを説明するものである。第７図においては、ブロ
ックサイズ４×４の場合、中心ブロックに対して水平（
ｘ）方向に一２〜＋２画素。

垂直（Ｙ）方向に一２〜＋２画素の範囲すなわち８×８
画素の範囲を参照範囲として、その中にある２５ブロツ
クから例えば第ｎ番目の参照ブロックを最適ブロックと
して求めることを示している。

第８図は従来のブロックマツチング型動き検出回路の一
例を示したものであって、（ａ）はその構成を示すブロ
ック図、（ｂｌはその動作を示すタイムチャートである
。第８図は参照ブロックの数ｎに対応してｎｕｌｌの相
関演算ユニットを並列に備え、メモリからｎ本のアクセ
スポートを有する場合を示している。

第８図（ａｌ、　（ｂｌにおいて、現フレームの画像信
号はブロックごとにその構成画素Ｔ、〜１ｍが順次入力
端子■からｎ（［ｌｉｌの相関演算ユニッＩ−ＰＵＩ〜
Ｐｕｎに入力される。図示されないメモリにおける前フ
レームの画像信号は、ｎ本のアクセスポートからそれぞ
れ相関演算ユニソ）ＰＵＩ〜ＰＵｎの入力Ｒ１〜Ｒｎに
入力される。Ｒｌ、〜Ｒ”；、　　Ｒ’２〜Ｒ２，−、
Ｒｍ−Ｒｍはそれぞれ第１〜第ｎ番目の参照ブロックの
画素の入力を示している。

これによって各相関演算ユニットでは、現フレームの画
像信号と前フレームの画像信号とが減算器ＳＵＢにおい
て減算され、減算結果から絶対値演算器ＡＢＳにおいて
それぞれ絶対値出力が求められ、絶対値出力は累算器Ａ
ＣＣにおいてそれぞれ累算されて、参照ブロックごとの
累算出力Ａ、〜Ａｎを生じる。累算出力Ａ１〜Ａｎは最
小値検出回路ＭＩＤに入力されて、どの累算出力が最小
であるかが検出され、最小の累算出力例えばＡ２が動き
ベクトル出力信号として出力される。

第９図は従来のブロックマツチング型動き検出回路の他
の例を示したものであって、ｔａ＋はその構成を示すブ
ロック図、ｆｂｌはその動作を示すタイムチャートであ
る。第９図は相関演算ユニットを１個だけ備え、メモリ
から１本のアクセスポートを経て、ｎ倍の速度でデータ
をアクセスするものである。

この場合は第９図（ｂ）に示すように、減算器ＳＵＢに
対して現フレームの画像信号１）〜１ｍが順次入力され
る間に、前フレームの画像信号がｎ倍の速度で、Ｒ＋〜
Ｒ１，Ｒｚ〜Ｒ２，−、Ｒｍ　〜Ｒｍというように入力
されて減算が行われ、減算結果に対して絶対値回路ＡＢ
Ｓで絶対値が求められ、絶対値出力は累算器ＡＣＣにお
いて累算されて累算出力Ａ＋−Ａｍが出力され、これに
対して最小値検出回路ＭＩＤにおいて最小値が検出され
て、最小の累算出力例えばＡ２が動きベクトルとして出
力される。従って第９図（ａ）の回路では、現フレーム
の画像信号入力に対して前フレームの画像信号入力がｎ
倍の速度で減算、絶対値演算、累算、最小値検出が行わ
れて、動きベクトル出力信号が出力される。

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

第８図に示された従来のブロックマツチング型動き検出
回路は、演算速度を高くする必要はないが、メモリのア
クセスポート数が多くなり、メモリ回路の規模が大きく
なるという問題点がある。

また第９図に示された従来のプロ・ツクマツチング型動
き検出回路は、アクセスポート数は少なくて済むが、ア
クセス速度が高くなり、素子の能力によっては実現不可
能となるという問題がある。

本発明はこのような従来技術の課題を解決しようとする
ものであって、第８図の回路において同じデータが繰り
返しアクセスされていることに着目して、繰り返しアク
セスする回数を少なくし、アクセス速度を高くしないで
、アクセスポート数を少なくすることができる回路形式
を提供することを目的としている。

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

本発明は第１図にその基本的構成を示すように、現ブロ
ックと前フレームにおいて現フレームに対応する中心ブ
ロックの近傍に設定された参照範囲内における現ブロッ
クと同サイズの複数の各参照ブロックのうち現ブロック
との相関が最大なものを検出して該参照ブロックと現ブ
ロックとの動きを示す動きベクトルを発生ずるブロック
マツチング型動き検出回路において、相関演算回路１と
、最小値検出回路２とを設けたものである。

相関演算回路ｌは、現ブロックと前記各参照ブロックと
の相関を演算するとともに該参照ブロックのデータを１
サンプル周期保持する複数の相関演算ユニット（ＰＵｕ
〜ＰＵ悄巾）を二次元的に配列してなるものである。外
側の相関演算ユニットにおいては、参照ブロックを構成
する画素における最上行、最左列、最下行、最右列の４
方向またはこれらのうちの３方向のいずれか１方向のデ
ータを選択して前フレームの画像信号によって更新する
。そしてこの更新された参照ブロックを該選択された方
向と逆の方向に各相関演算ユニットを逐次シフトするこ
とができるように構成する。各相関演算ユニットにおい
ては、参照ブロックが入力されるごとに入力参照ブロッ
クと現ブロックとの間で相関演算を行って相関の大きさ
を示す信号を発生する。

最小値検出回路２は、相関演算回路１において発生した
相関の大きさを示す信号中最大の値を有するものを検出
する。そして最大の相関値を検出された参照ブロックと
現ブロックとの動きを示す動きベクトルを発生する。

〔作　用〕

本発明のブロックマツチング型動き検出回路は第１図に
示された基本的構成に示されるように相関演算回路１と
最小値検出回路２とを有し、現フレームの画像信号と０
本のポートから入力される前フレームの画像信号とは、
相関演算回路１において相関を演算され累算出力が最小
値検出回路２に入力される。最小値検出回路２において
は最小の累算出力を検出し、これに基づいて動きベクト
ル出力信号を出力する。

従って本発明のブロックマツチング型動き検出回路では
、繰り返しアクセスする回数を少なくすることができ、
アクセス速度を高くしないで、アクセスポート数を少な
くすることができるようになる。

〔実施例〕

第２図は本発明の一実施例における相関演算回路の構成
をブロック図によって示したものであって、参照ブロッ
クが４×４の場合を例示し、ＰＵ１〜ＰＵ１６は相関演
算ユニットである。

第２図において、現フレームの画像信号Ｐ■は相関演算
ユニットＰＵ１〜Ｐ　Ｉ　１６のそれぞれの端子Ｐ１〜
Ｐ１６に入力される。また前フレームの画像信号ＲＩＩ
〜ＲＩ４は４本のアクセスポートから、相関演算ユニッ
）ＰＵＩ〜ＰＵ４の左入力端子Ｌ１〜Ｌ４、および相関
演算ユニッＩ−ＰＵＩ。

ＰＯ２，ＰＯ９，ＰＯ１３の上人力Ｕｌ、Ｕ５．Ｕ９、
Ｕ１３、および相関演算ユニットＰＵ４．ＰＵ８、ＰＯ
１２，ＰＯ１６の上人力Ｄ４．Ｄ８．Ｄ１２゜ＤＩ６よ
り入力され、相関演算ユニット内部で演算された結果は
、端子８１〜Ｓ１６から累算出力ＳＵＭＯとして出力さ
れる。

また各相関演算ユニ・ノドの上人力Ｕ１〜Ｕ１６、左入
力Ｌ１〜Ｌ１６、上人力Ｄ１〜Ｄ１６に対するセレクト
信号ＳＥＬ　Ｉがそれぞれ端子ＳＥＬ　１〜ＳＥ　Ｌ　
１６から入力される。各相関演算ユニット内で１サンプ
ル周期分遅延された出力は、端子０１〜０１６からそれ
ぞれ上、右、下の各相関演算ユニットにおける下（Ｄ）
、左（Ｌ）、上（Ｕ）の入力端子に入力される。

第３図は相関演算ユニットの内部構成を示すブロック図
である。同図において１）はセレクタ、１２は減算器、
１３は絶対値演算器、１４は加算器、１５゜１７、１８
はシフトレジスタ、１６はフリップフロップである。

第３図において上セル出力信号Ｕ、左セル出力信号り、
下セル出力信号りはセレクタ１）においてセレクト信号
入力ＳＥＬに従って、いずれか１つが選択されて減算器
１２に入力され、現入力信号Ｐと差分の演算を行われる
。差分の信号は絶対値演算器１３に加えられて絶対値出
力を求められ、絶対値出力は加算器１４とシフトレジス
タ１５より構成される累算器に入力されて累算出力を求
められる。

累算出力はフリップフロップ１６において、累算結果ラ
フチク口・７り入力ＣＫによりラッチされ、累算出力Ｓ
を生じる。出力コントロールパルスＯＣ■はシフトレジ
スタ１７において１サンプル周期分遅延され、ＯＣＯと
して出力されるとともに、ランチ用フリップフロップ１
６のＯＣ入力に加えられてその出力をイネーブルにする
。

またシフトレジスタ１８はセレクタ１）の出力における
参照ブロックのデータを１サンプル周期遅延させて、出
力Ｏとして出力する。

第４図は前フレーム画像信号入力および相関演算回路の
動作を説明する図である。

７×７画素サイズの参照範囲内において、右上端の参照
ブロックが最初に第２図に示す相関演算ユニッＩ−ＰＵ
Ｉ〜ＰＵ１６に入力され、演算が行われる。

サンプル時間ｔ＝１においては、相関演算ユニットＰＵ
Ｉ〜ＰＵ、１６のすべてのセレクタでは玉入力が選択さ
れ、メモリから新たに４画素分のデータがポートＲ１）
，ＲＩ２．ＲＩ３．ＲＩ４を経て端子Ｄ４．Ｄ８．ＤＩ
２．　　Ｄ１６からそれぞれ相関演算ユニットＰＵ４．
ＰＵ８．ＰＵ１２．ＰＯ１６に入力され、相関演算ユニ
ッＩ−ＰＵ４．ＰＵ８．ＰＯ１２，ＰＯ１６に蓄積され
ていたデータは出力端子０４．０８，０１２．０１６か
ら相関演算ユニットＰＵ３．ＰＵ７．Ｐｕ１ｌ、ＰＯ１
５に端子Ｄ３．Ｄ？。

Ｄｌｌ、　　Ｄ、１５を経て入力され、相関演算ユニッ
トＰＵ３．ＰＵ７．ＰＵＩＩ、ＰＯ１５に蓄積されてい
たデータは、出力端子０３，０７，０１），０１５から
相関演算ユニットＰＵ２．ＰＵ６．ＰＵＩＯ，ＰＯ１４
に端子Ｄ２．Ｄ６．ＤＩＯ，Ｄ１４を経て入力され、相
関演算ユニットＰＵ２．ＰＵ６．ＰＵＩＯ，ＰＯ１４に
蓄積されていたデータは、出力端子０２，０６．０１０
，０１４から相関演算ユニットＰＵＩ、ＰＵ５．ＰＵ９
．ＰＯ１３に端子Ｄ１．Ｄ５．Ｄ９゜Ｄ１３を経て入力
され、相関演算ユニッ）ＰＵＩ〜ＰＵ１６では次の参照
ブロックとの間で演算が行われる。

時間ｔ＝２．ｔ＝３のときも同様にして動作が行われる
。

時間ｔ＝４のとき、相関演算ユニソ）ＰＵＩ〜ＰＵ１６
のすべてのセレクタでは左入力ＬＩＪ＜選択され、メモ
リから新たに４画素分のデータがポートＲ１），ＲＩ２
．ＲＩ３．ＲＩ４を経て端子Ｌｌ。

Ｌ２．Ｌ３．Ｌ４から相関演算ユニット、ＰＵＩ〜ＰＵ
４に入力され、相関演算ユニソ）ＰＵＩ〜ＰＵに蓄積さ
れていたデータは、出力端子０１〜０４から相関演算ユ
ニットＰＵ５〜ＰＵ８に対しその左端子Ｌ５〜Ｌ８を経
て入力され、相関演算ユニットＰＵ５〜ＰＵ１２に蓄積
されていたデータは出力端子０５〜０８から相関演算ユ
ニットＰＵ９〜ＰＵ１２に対しその左端子Ｌ９〜Ｌ１２
を経由して入力され、相関演算ユニットＰＵ９〜ＰＵ１
２に蓄積されていたデータは出力端子０９〜０１２から
相関演算ユニッ１−ＰＵ１３〜１６に対しその左端子Ｌ
１３〜Ｌ１６を経由して入力される。

時間ｔ＝５のとき、相関演算ユニノ１−ＰＵＩ〜ＰＵ１
６のすべてのセレクタでは上人力Ｕが選択され、メモリ
から新たに４画素分のデータがポートｔｌ、ＲＴ２．Ｒ
Ｉ３．ＲＩ４を経て上端子Ｕ１、Ｕ５．Ｕ９．Ｕ１３か
ら相関演算ユニットＰＵ１、ＰＯ５，ＰＯ９，ＰＯ１３
に入力される。相関演算ユニットＰＵＩ、ＰＵ５．ＰＵ
９．ＰＯ１３に蓄積されていたデータは、出力端子Ｏｆ
、０５゜０９．０１３から上端子Ｕ２．ｔＪ６．ＵＩＯ
，Ｕ１４を経由して相関演算ユニッ）ＰＯ２，ＰＯ６，
ＰＵｌｏ、ＰＯ１４に入力され、相関演算ユニッ）Ｐｔ
Ｊ２゜ＰＯ６，ＰＵＩＯ，ＰＯ１４に蓄積されていたデ
ータは出力端子０２．０６．０１０．　０１４から上端
子Ｕ３、Ｕ７．Ｕｌｌ、Ｕ１５を経由して相関演算ユニ
ソ）ＰＯ３，ＰＯ７，ＰＵＩＩ、ＰＯ１５に入力され、
相関演算ユニットＰＵ３．ＰＵ７．Ｐｕ１ｌ、ＰＯ１５
に蓄積されていたデータは出力端子０３，０？。

０１）．０１５から上端子Ｕ４．Ｕ８．Ｕ１２．Ｕ１６
を経由して相関演算ユニッ）ＰＯ２，ＰＯ８，ＰＯ１２
、ＰＯ１６に入力される。

時間ｔ＝６．７のときも同様である。

時間ｔ＝８のときは、時間ｔ＝４のときと同様である。

時間ｔ＝９〜１）のときは、ｔ＝１〜３のときと同様で
ある。

時間ｔ＝１２のときは、時間ｔ＝４のときと同様である
。

時間ｔ＝１３〜１５のときは、ｔ＝５〜７のときと同様
である。

このようにして現ブロックとの相関を演算されるべき参
照ブロックは、第４図の右上端から始めて順次１６個の
位置をシフトされ、その都度各相関演算ユニットにおい
て現ブロックとの相関が演算されて、相関累算出力Ｓ１
〜Ｓ１６がＳＵＭＯに出力される。

第５図は最小値検出回路の構成を示すプロ・ツク図であ
る。

セレクタ２２はセレクト信号によって最初１側が選択さ
れ、初期値として累算出力の最大値（ＭＡＸ）が比較器
２３の入力Ａ側に与えられる。各相関回路ＰＵＩ〜ＰＵ
１６から出力された累算出力ＳＵＭＯは、比較器２３の
入力Ｂ　１）！Ｉに与えられてＡ側の入力と比較され、
Ｂ＜Ａのとき比較器間の出力Ｃ＝１となり、サンプルク
ロックＣＫに応じてフリップフロップ２４にラッチされ
る。フリップフロップ２４はサンプルクロックＣＫごと
にリセットされており、１を保持したときアンド回路２
５を開いてフリップフロップ２１にサンプルクロックＣ
Ｋを与えて累算出力ＳＵＭＯをランチさせる。フリップ
フロップ２Ｉに井保持された累算出力ＳＵＭＯによって
、次に入力される累算出力ＳＵＭＯとの比較が行われ、
このようにして最小の累算出力ＳＵＭＯが検出されたと
き、アンド回路２５の出力クロノクによってフリップフ
ロップ２８．２９に水平ベクトル発生用カウンタ２６．
垂直ベクトル発生用カウンタ２７の出力値がラッチされ
、以後保持される。水平ベクトル発生用カウンタ２６．
垂直ベクトル発生用カウンタ２７は累算出力ＳＵＭＯの
発生に対応してカウントしており、最小の累算出力ＳＵ
ＭＯを発生した参照ブロックに相当する値が動きベクト
ル出力信号の水平成分および垂直成分として、それぞれ
フリップフロップ２８．２９から出力される〔発明の効
果〕 以上説明したように本発明によれば、参照データメモリ
から相関演算回路への画像データのアクセスにおいて、
データ転送速度を上げることなくアクセスポート数を減
少させることができる。

また本発明の回路は非常に規則的な回路の組合せによっ
て実現することができるので、アレイプロセッサ化およ
びＬＳＩ化に好適である。

【図面の簡単な説明】 第１図は本発明の基本的構成を示す図、第２図は本発明
の一実施例の相関演算ユニットの構成を示す図、 第３図は相関演算ユニットの内部構成を示す図、第４図
は前フレーム画像信号入力および相関演算回路の動作を
説明する図、 第５図は本発明の一実施例の最小値検出回路の構成を示
す図、 第６図はブロックマツチング型動き検出方式を説明する
図、 第７図はブロックマツチング型動き検出における参照ブ
ロックを説明する図、 第８図は従来のブロックマツチング型動き検出回路の一
例を示す図、 第９図は従来のブロックマツチング型動き検出回路の他
の例を示す図である。 １−相関演算回路 ２−最小値検出回路 Ｐ　Ｕ　１−Ｐ　Ｕ１６−相関演算ユニット１）．２２
−ｍ−セレクタ １２−減算器 １３−絶対値回路 １４−・・加算器 １５、１７．　　ＩＥＩ−シフトレジスタ１６、２１．
２４．２８．２９−一一フリップフロップ２３−比較器 ２５−　アンド回路 ２６・−水平ベクトル発生用カウンタ

Claims (1)

1. 【特許請求の範囲】 現ブロックと前フレームにおいて現フレームに対応する
   中心ブロックの近傍に設定された参照範囲内における現
   ブロックと同サイズの複数の各参照ブロックのうち現ブ
   ロックとの相関が最大なものを検出して該参照ブロック
   と現ブロックとの動きを示す動きベクトルを発生するブ
   ロックマッチング型動き検出回路において、 現ブロックと前記各参照ブロックとの相関を演算すると
   ともに該参照ブロックのデータを１サンプル周期保持す
   る複数の相関演算ユニット（ＰＵ＿ｎ〜ＰＵ＿ｍ＿ｎ）
   を二次元的に配列してなり、外側の相関演算ユニットに
   おいて参照ブロックを構成する画素における最上行、最
   左列、最下行、最右列の４方向またはこれらのうちの３
   方向のいずれか１方向のデータを選択して前フレームの
   画像信号によって更新するとともに、該更新された参照
   ブロックを該選択された方向と逆の方向に各相関演算ユ
   ニットを逐次シフトするように構成し、各相関演算ユニ
   ットにおいてその都度入力された参照ブロックと現ブロ
   ックとの間で相関演算を行って相関の大きさを示す信号
   を発生する相関演算回路（１）と、 該相関演算回路（１）において発生した相関の大きさを
   示す信号中最大の値を有するものを検出するとともに該
   検出された信号に対応する参照ブロックと現ブロックと
   の動きを示す動きベクトルを発生する最小値検出回路（
   ２）と を備えてなることを特徴とするブロックマッチング型動
   き検出回路。