JPH1051793A - ブロックマッチング装置 - Google Patents
ブロックマッチング装置Info
- Publication number
- JPH1051793A JPH1051793A JP22170096A JP22170096A JPH1051793A JP H1051793 A JPH1051793 A JP H1051793A JP 22170096 A JP22170096 A JP 22170096A JP 22170096 A JP22170096 A JP 22170096A JP H1051793 A JPH1051793 A JP H1051793A
- Authority
- JP
- Japan
- Prior art keywords
- reduced
- pixels
- pixel
- template
- block
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Image Analysis (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
Abstract
(57)【要約】
【課題】 従来の全探索ブロックマッチング法と同程度
の探索精度を維持しつつ、従来の全探索ブロックマッチ
ング法における演算量の１／４に演算量を削減すること
ができ、しかも、メモリからブロックマッチング装置に
転送する探索領域中の画素データの転送量を、従来の全
探索ブロックマッチング法の１／４に抑えることができ
るブロックマッチング装置を提供することを目的とする
ものである。 【解決手段】 探索領域中の画素から水平方向に所定画
素毎、垂直方向に所定ライン毎に、サブサンプリングし
て縮小画像を作成し、テンプレート中の所定の位置に存
在する画素を１画素づつサブサンプリングすることによ
って縮小テンプレートを複数個作成し、各縮小テンプレ
ート毎に、上記縮小画像から切り出した縮小ブロックと
の間で、対応する位置にある画素間の値の違いを評価す
るものである。
の探索精度を維持しつつ、従来の全探索ブロックマッチ
ング法における演算量の１／４に演算量を削減すること
ができ、しかも、メモリからブロックマッチング装置に
転送する探索領域中の画素データの転送量を、従来の全
探索ブロックマッチング法の１／４に抑えることができ
るブロックマッチング装置を提供することを目的とする
ものである。 【解決手段】 探索領域中の画素から水平方向に所定画
素毎、垂直方向に所定ライン毎に、サブサンプリングし
て縮小画像を作成し、テンプレート中の所定の位置に存
在する画素を１画素づつサブサンプリングすることによ
って縮小テンプレートを複数個作成し、各縮小テンプレ
ート毎に、上記縮小画像から切り出した縮小ブロックと
の間で、対応する位置にある画素間の値の違いを評価す
るものである。
Description
【０００１】
【発明の属する技術分野】本発明は、動画像符号化や動
画像認識等において動きベクトルを検出するために用い
られるブロックマッチング装置に関するものである。
画像認識等において動きベクトルを検出するために用い
られるブロックマッチング装置に関するものである。
【０００２】
【従来の技術】動きベクトルは、所定の画像において隣
接する複数の画素で構成される画素ブロックが、所定の
画像とは異なる画像中のどの位置から動いてきたかを示
すベクトルである。
接する複数の画素で構成される画素ブロックが、所定の
画像とは異なる画像中のどの位置から動いてきたかを示
すベクトルである。
【０００３】図７は、従来のブロックマッチング装置の
動作を説明する図であり、動き検出の対象となるテンプ
レートＴ０と探索領域Ｒ０との関係を示す図である。
動作を説明する図であり、動き検出の対象となるテンプ
レートＴ０と探索領域Ｒ０との関係を示す図である。
【０００４】従来のブロックマッチング装置は、所定画
像中の画素ブロックが他の画像中のどこに移動したかを
探索するものであり、つまり、探索領域Ｒ０は、上記他
の画像中の画素ブロックであり、テンプレートＴ０は、
上記所定の画像中の画素ブロック（現在の画像中の画素
ブロック）である。すなわち、従来のブロックマッチン
グ装置は、上記所定の画像から切り出した画素ブロック
であるテンプレートＴ０が、上記他の画像における探索
領域Ｒ０中のどこから移動したかを探索するものであ
る。また、画素３（△）は、テンプレートＴ０中の画素
であり、画素４（〇）は、探索領域Ｒ０中の画素であ
る。
像中の画素ブロックが他の画像中のどこに移動したかを
探索するものであり、つまり、探索領域Ｒ０は、上記他
の画像中の画素ブロックであり、テンプレートＴ０は、
上記所定の画像中の画素ブロック（現在の画像中の画素
ブロック）である。すなわち、従来のブロックマッチン
グ装置は、上記所定の画像から切り出した画素ブロック
であるテンプレートＴ０が、上記他の画像における探索
領域Ｒ０中のどこから移動したかを探索するものであ
る。また、画素３（△）は、テンプレートＴ０中の画素
であり、画素４（〇）は、探索領域Ｒ０中の画素であ
る。
【０００５】図７では、探索領域Ｒ０の上にテンプレー
トＴ０を重ねて示してあるので、探索領域Ｒ０中、テン
プレートＴ０が重なっている部分における画素４（〇）
の表示が省略されている。また、図７において、テンプ
レートＴ０の矩形領域と探索領域Ｒ０の矩形領域の大き
さは、ともに４画素×４ラインであるが、両矩形領域の
大きさは、上記４画素×４ライン以外の大きさであって
もよい。なお、本明細書においては、水平方向の画素数
の単位を画素と呼び、垂直方向の画素数の単位をライン
と呼ぶ。また、１つの画素は、複数ビットで表現されて
いる。
トＴ０を重ねて示してあるので、探索領域Ｒ０中、テン
プレートＴ０が重なっている部分における画素４（〇）
の表示が省略されている。また、図７において、テンプ
レートＴ０の矩形領域と探索領域Ｒ０の矩形領域の大き
さは、ともに４画素×４ラインであるが、両矩形領域の
大きさは、上記４画素×４ライン以外の大きさであって
もよい。なお、本明細書においては、水平方向の画素数
の単位を画素と呼び、垂直方向の画素数の単位をライン
と呼ぶ。また、１つの画素は、複数ビットで表現されて
いる。
【０００６】上記動きベクトルを検出する方法として、
従来、全探索ブロックマッチング法が知られている。こ
の全探索ブロックマッチング法は、まず、探索領域Ｒ０
から４画素×４ラインの画素ブロック５を切り出し、こ
の画素ブロック５における４画素×４ラインの各画素の
値と、テンプレートＴ０中の対応する位置に存在する画
素の値との違いを、画素毎に、差分絶対値または差分二
乗値等で算出し、これら算出値の総和を求め、次に、画
素ブロック５を１画素分左右または上下に移動し、この
移動後の新たな画素ブロック５における４画素×４ライ
ンの各画素の値と、上記テンプレートＴ０中の対応する
位置に存在する画素の値との違いを、画素毎に、差分絶
対値または差分二乗値等で算出し、これら算出値の総和
を求める。そして、このように、画素ブロック５を１画
素分左右または上下に順次、移動しながら、移動後の新
たな画素ブロック５における４画素×４ラインの各画素
の値と、上記テンプレートＴ０中の対応する位置に存在
する画素の値との違いを、画素毎に、差分絶対値または
差分二乗値等で算出し、これら算出値の総和である評価
値を求める。
従来、全探索ブロックマッチング法が知られている。こ
の全探索ブロックマッチング法は、まず、探索領域Ｒ０
から４画素×４ラインの画素ブロック５を切り出し、こ
の画素ブロック５における４画素×４ラインの各画素の
値と、テンプレートＴ０中の対応する位置に存在する画
素の値との違いを、画素毎に、差分絶対値または差分二
乗値等で算出し、これら算出値の総和を求め、次に、画
素ブロック５を１画素分左右または上下に移動し、この
移動後の新たな画素ブロック５における４画素×４ライ
ンの各画素の値と、上記テンプレートＴ０中の対応する
位置に存在する画素の値との違いを、画素毎に、差分絶
対値または差分二乗値等で算出し、これら算出値の総和
を求める。そして、このように、画素ブロック５を１画
素分左右または上下に順次、移動しながら、移動後の新
たな画素ブロック５における４画素×４ラインの各画素
の値と、上記テンプレートＴ０中の対応する位置に存在
する画素の値との違いを、画素毎に、差分絶対値または
差分二乗値等で算出し、これら算出値の総和である評価
値を求める。
【０００７】そして、上記評価値が最も小さい画素ブロ
ックに対応する位置から、テンプレートＴ０が移動して
きたと判断する。この場合、図７の例では、探索領域Ｒ
０が１１画素×１１ラインで構成されているので、テン
プレートＴ０が水平方向に８回移動し、垂直方向にも８
回移動する。つまり、テンプレートＴ０と比較して評価
すべき画素ブロック５の数は、８×８＝６４組であり、
評価値の数は６４個である。
ックに対応する位置から、テンプレートＴ０が移動して
きたと判断する。この場合、図７の例では、探索領域Ｒ
０が１１画素×１１ラインで構成されているので、テン
プレートＴ０が水平方向に８回移動し、垂直方向にも８
回移動する。つまり、テンプレートＴ０と比較して評価
すべき画素ブロック５の数は、８×８＝６４組であり、
評価値の数は６４個である。
【０００８】また、図７に示す例において、動きベクト
ルの範囲を水平、垂直ともに−４〜＋３とし、たとえ
ば、図７に示す画素ブロック５における評価値が最小で
あったとすると、その動きベクトルは（２，２）であ
る。
ルの範囲を水平、垂直ともに−４〜＋３とし、たとえ
ば、図７に示す画素ブロック５における評価値が最小で
あったとすると、その動きベクトルは（２，２）であ
る。
【０００９】なお、上記従来例では単画素精度（注目す
る画像が１画素を単位として移動した場合にその移動を
検出する方法）における動きを検出する例を示してある
が、注目画像は、水平方向または垂直方向に整数画素数
分移動するとは限らず、実際には、動きを検出すべき探
索領域Ｒ０中のブロックとテンプレートＴ０との間に、
１画素分以下のずれが存在する場合が多い。また、評価
式として何を用いるかは本発明の本質ではないので、以
下では、便宜上、差分絶対値を評価式として用いる場合
について説明する。
る画像が１画素を単位として移動した場合にその移動を
検出する方法）における動きを検出する例を示してある
が、注目画像は、水平方向または垂直方向に整数画素数
分移動するとは限らず、実際には、動きを検出すべき探
索領域Ｒ０中のブロックとテンプレートＴ０との間に、
１画素分以下のずれが存在する場合が多い。また、評価
式として何を用いるかは本発明の本質ではないので、以
下では、便宜上、差分絶対値を評価式として用いる場合
について説明する。
【００１０】上記従来の全探索ブロックマッチング法に
おいて、全矩形領域を評価するためには、テンプレート
Ｔ０と比較して評価すべき画素ブロック５の組が６４組
であり、各画素ブロック５には１６画素が含まれるの
で、６４×１６＝１０２４回、差分絶対値を計算する必
要があり、演算量が多いという問題がある。
おいて、全矩形領域を評価するためには、テンプレート
Ｔ０と比較して評価すべき画素ブロック５の組が６４組
であり、各画素ブロック５には１６画素が含まれるの
で、６４×１６＝１０２４回、差分絶対値を計算する必
要があり、演算量が多いという問題がある。
【００１１】また、上記従来の全探索ブロックマッチン
グ法において、探索領域Ｒ０中の画素が、通常、メモリ
に格納され、このメモリから、ブロックマッチング装置
（動きベクトルを評価する装置）に転送されるが、この
場合、探索領域Ｒ０が１１画素×１１ラインで構成され
ているので、１１画素×１１ライン＝１２１画素を転送
する必要があり、この転送量が多いという問題がある。
グ法において、探索領域Ｒ０中の画素が、通常、メモリ
に格納され、このメモリから、ブロックマッチング装置
（動きベクトルを評価する装置）に転送されるが、この
場合、探索領域Ｒ０が１１画素×１１ラインで構成され
ているので、１１画素×１１ライン＝１２１画素を転送
する必要があり、この転送量が多いという問題がある。
【００１２】そこで、上記演算量と転送量とを削減する
ために次の方法が知られている。この方法は、第１ステ
ップと第２ステップとで構成され、第１ステップでは、
複数の画素から１つの画素を選択するサブサンプリング
を行い、このようにサブサンプリングすることによって
縮小画像を得、この縮小画像上で動きを評価し、この第
１ステップに続く第２ステップにおいて、上記第１ステ
ップで得られた動きベクトルを初期変移とし、サブサン
プリング前の画像上で狭い範囲のみ探索する方法であ
る。
ために次の方法が知られている。この方法は、第１ステ
ップと第２ステップとで構成され、第１ステップでは、
複数の画素から１つの画素を選択するサブサンプリング
を行い、このようにサブサンプリングすることによって
縮小画像を得、この縮小画像上で動きを評価し、この第
１ステップに続く第２ステップにおいて、上記第１ステ
ップで得られた動きベクトルを初期変移とし、サブサン
プリング前の画像上で狭い範囲のみ探索する方法であ
る。
【００１３】図８は、上記従来例において、２画素×２
ラインから１画素をサブサンプリングするときに、取り
出される画素を示す図である。
ラインから１画素をサブサンプリングするときに、取り
出される画素を示す図である。
【００１４】この従来例においては、テンプレートＴ０
からも探索領域Ｒ０からもサンプリングされ、画素６
（▲）は、テンプレートＴ０からサブサンプリングされ
る画素であり、画素７（●）は、探索領域Ｒ０からサブ
サンプリングされる画素である。したがって、図８に示
す例において、縮小画像上では、全矩形領域を評価する
ために、テンプレートＴ０と比較して評価すべき領域の
組が１６組であり、この１つの組が２画素×２ラインで
構成されているので、１６×４＝６４回の差分絶対値計
算を行う必要があり、また、転送する場合には、画素７
の数である５画素×５ライン＝２５画素の探索領域画素
７（●）を転送する必要がある。さらに、上記第２ステ
ップとして、サブサンプリング前の画像上で上記初期変
移の周り−１〜＋１を探索する場合、テンプレートＴ０
に含まれる１６画素について差分絶対値を計算し、この
テンプレートＴ０を水平方向に３画素分移動し、垂直方
向に３ライン分の合計９回移動させて差分絶対値を計算
するので、１６×９＝１４４回の差分絶対値計算が必要
であり、また、探索すべき６画素×６ライン＝３６画素
について探索領域画素の転送が必要である。演算量と転
送量との合計は、６４＋１４４＝２０８回であり、ま
た、２５＋３６＝６１画素であるので、上記２画素×２
ラインから１画素をサブサンプリングするサブサンプリ
ング法は、上記従来の全探索ブロックマッチング法より
も、演算量と転送量との合計が大幅に削減される。
からも探索領域Ｒ０からもサンプリングされ、画素６
（▲）は、テンプレートＴ０からサブサンプリングされ
る画素であり、画素７（●）は、探索領域Ｒ０からサブ
サンプリングされる画素である。したがって、図８に示
す例において、縮小画像上では、全矩形領域を評価する
ために、テンプレートＴ０と比較して評価すべき領域の
組が１６組であり、この１つの組が２画素×２ラインで
構成されているので、１６×４＝６４回の差分絶対値計
算を行う必要があり、また、転送する場合には、画素７
の数である５画素×５ライン＝２５画素の探索領域画素
７（●）を転送する必要がある。さらに、上記第２ステ
ップとして、サブサンプリング前の画像上で上記初期変
移の周り−１〜＋１を探索する場合、テンプレートＴ０
に含まれる１６画素について差分絶対値を計算し、この
テンプレートＴ０を水平方向に３画素分移動し、垂直方
向に３ライン分の合計９回移動させて差分絶対値を計算
するので、１６×９＝１４４回の差分絶対値計算が必要
であり、また、探索すべき６画素×６ライン＝３６画素
について探索領域画素の転送が必要である。演算量と転
送量との合計は、６４＋１４４＝２０８回であり、ま
た、２５＋３６＝６１画素であるので、上記２画素×２
ラインから１画素をサブサンプリングするサブサンプリ
ング法は、上記従来の全探索ブロックマッチング法より
も、演算量と転送量との合計が大幅に削減される。
【００１５】ただし、上記縮小画像で動きベクトルを求
める方法において、画像にノイズが含まれる場合には、
検出精度が劣化するという欠点がある。
める方法において、画像にノイズが含まれる場合には、
検出精度が劣化するという欠点がある。
【００１６】図９は、画像にノイズが含まれる場合に検
出精度が劣化するという欠点を排除するために提案され
た従来の方法であり、２画素×２ライン＝４画素の平均
値を計算して縮小画像を作成する方法を示す図である。
出精度が劣化するという欠点を排除するために提案され
た従来の方法であり、２画素×２ライン＝４画素の平均
値を計算して縮小画像を作成する方法を示す図である。
【００１７】上記縮小画像を使用して動きベクトルを求
める場合、画像にノイズが含まれているときに検出精度
の劣化を防止するには、図９に示すように２画素×２ラ
イン＝４画素の平均値を計算し、これに基づいて、縮小
画像を作ればよい。画素８（▼）は、テンプレートＴ０
の上で２画素×２ライン＝４画素のそれぞれの値を平均
値を計算して得られた値を有する画素であり、画素９
（◎）は、探索領域Ｒ０の上で２画素×２ライン＝４画
素の平均値を計算して得られた値を有する画素である。
める場合、画像にノイズが含まれているときに検出精度
の劣化を防止するには、図９に示すように２画素×２ラ
イン＝４画素の平均値を計算し、これに基づいて、縮小
画像を作ればよい。画素８（▼）は、テンプレートＴ０
の上で２画素×２ライン＝４画素のそれぞれの値を平均
値を計算して得られた値を有する画素であり、画素９
（◎）は、探索領域Ｒ０の上で２画素×２ライン＝４画
素の平均値を計算して得られた値を有する画素である。
【００１８】上記動きベクトル検出方法については、た
とえば、N.Hayashi, T.Kitsuki, I.Tamitani, H.Honma,
Y.Ooi, T.Miyazaki, K.Oobuchi, "A bidirectional mo
tioncompensation LSI with a compact motion estimat
or"IEICE Trans. Electron,E78-C, 12, pp. 1682-1690,
Dec.1995.に記載されている。
とえば、N.Hayashi, T.Kitsuki, I.Tamitani, H.Honma,
Y.Ooi, T.Miyazaki, K.Oobuchi, "A bidirectional mo
tioncompensation LSI with a compact motion estimat
or"IEICE Trans. Electron,E78-C, 12, pp. 1682-1690,
Dec.1995.に記載されている。
【００１９】上記従来例は、４画素の平均値を計算して
得られた縮小画像上で、２画素精度の動きベクトルを求
めた後、単画素精度の動きベクトルを求める例である
が、上記文献では、２画素精度の動きベクトルを求めた
後、半画素精度の動きベクトルを求める例が記載されて
いる。
得られた縮小画像上で、２画素精度の動きベクトルを求
めた後、単画素精度の動きベクトルを求める例である
が、上記文献では、２画素精度の動きベクトルを求めた
後、半画素精度の動きベクトルを求める例が記載されて
いる。
【００２０】
【発明が解決しようとする課題】上記従来の全探索ブロ
ックマッチング法は、上記のように、演算量が多いとい
う問題があり、また、メモリと動きベクトルを評価する
装置との間で、探索領域中の画素データの転送量が多い
という問題がある。
ックマッチング法は、上記のように、演算量が多いとい
う問題があり、また、メモリと動きベクトルを評価する
装置との間で、探索領域中の画素データの転送量が多い
という問題がある。
【００２１】図１０は、従来のサブサンプリング法にお
いて、動きベクトルを検出する対象である探索領域Ｒ０
中の縮小ブロックＢＬとテンプレートＴ０との間に、水
平方向に最大１画素、垂直方向に最大１ラインのずれが
存在していることを示す図である。
いて、動きベクトルを検出する対象である探索領域Ｒ０
中の縮小ブロックＢＬとテンプレートＴ０との間に、水
平方向に最大１画素、垂直方向に最大１ラインのずれが
存在していることを示す図である。
【００２２】従来の全探索ブロックマッチング法では、
最大でも水平方向０．５画素、垂直方向０．５ラインの
ずれしか存在しないが、サブサンプリング法では、２画
素精度で探索するので、画像が水平方向に奇数画素、垂
直方向に奇数ライン動いた場合、図１０に示すように、
動きベクトルを検出する対象である探索領域Ｒ０内の縮
小ブロックＢＬとテンプレートＴ０との間に、水平方向
１画素、垂直方向１ラインのずれが存在する可能性があ
る。このために、従来の全探索ブロックマッチング法と
比べると、従来のサブサンプリング法は、誤った動きベ
クトルを検出しやすいという問題がある。
最大でも水平方向０．５画素、垂直方向０．５ラインの
ずれしか存在しないが、サブサンプリング法では、２画
素精度で探索するので、画像が水平方向に奇数画素、垂
直方向に奇数ライン動いた場合、図１０に示すように、
動きベクトルを検出する対象である探索領域Ｒ０内の縮
小ブロックＢＬとテンプレートＴ０との間に、水平方向
１画素、垂直方向１ラインのずれが存在する可能性があ
る。このために、従来の全探索ブロックマッチング法と
比べると、従来のサブサンプリング法は、誤った動きベ
クトルを検出しやすいという問題がある。
【００２３】さらに、従来のサブサンプリング法では、
単画素精度の動きベクトルを求めるステップが別途必要
になるという問題がある。
単画素精度の動きベクトルを求めるステップが別途必要
になるという問題がある。
【００２４】本発明は、従来の全探索ブロックマッチン
グ法と同程度の探索精度を維持しつつ、従来の全探索ブ
ロックマッチング法における演算量の１／４に演算量を
削減することができ、しかも、メモリからブロックマッ
チング装置に転送する探索領域中の画素データの転送量
を、従来の全探索ブロックマッチング法の１／４に抑え
ることができるブロックマッチング装置を提供すること
を目的とするものである。
グ法と同程度の探索精度を維持しつつ、従来の全探索ブ
ロックマッチング法における演算量の１／４に演算量を
削減することができ、しかも、メモリからブロックマッ
チング装置に転送する探索領域中の画素データの転送量
を、従来の全探索ブロックマッチング法の１／４に抑え
ることができるブロックマッチング装置を提供すること
を目的とするものである。
【００２５】
【課題を解決するための手段】本発明は、探索領域中の
画素から水平方向に所定画素毎、垂直方向に所定ライン
毎に、サブサンプリングして縮小画像を作成し、テンプ
レート中の所定の位置に存在する画素を１画素づつサブ
サンプリングすることによって縮小テンプレートを複数
個作成し、各縮小テンプレート毎に、縮小画像から切り
出した縮小ブロックとの間で、対応する位置にある画素
間の値の違いを評価するものである。
画素から水平方向に所定画素毎、垂直方向に所定ライン
毎に、サブサンプリングして縮小画像を作成し、テンプ
レート中の所定の位置に存在する画素を１画素づつサブ
サンプリングすることによって縮小テンプレートを複数
個作成し、各縮小テンプレート毎に、縮小画像から切り
出した縮小ブロックとの間で、対応する位置にある画素
間の値の違いを評価するものである。
【００２６】
【発明の実施の形態および実施例】図１は、本発明の一
実施例であるブロックマッチング装置ＢＭ１を示す図で
ある。図２は、ブロックマッチング装置ＢＭ１の動作を
示すフローチャートである。図３は、ブロックマッチン
グ装置ＢＭ１において、探索領域Ｒ１とテンプレートＴ
１との関係を示す図である。
実施例であるブロックマッチング装置ＢＭ１を示す図で
ある。図２は、ブロックマッチング装置ＢＭ１の動作を
示すフローチャートである。図３は、ブロックマッチン
グ装置ＢＭ１において、探索領域Ｒ１とテンプレートＴ
１との関係を示す図である。
【００２７】ブロックマッチング装置ＢＭ１は、縮小画
像生成部３０と、メモリＭと、縮小テンプレート作成手
段４０と、縮小ブロック評価手段５０と、縮小テンプレ
ート選択手段６０とを有する。
像生成部３０と、メモリＭと、縮小テンプレート作成手
段４０と、縮小ブロック評価手段５０と、縮小テンプレ
ート選択手段６０とを有する。
【００２８】縮小画像作成手段３０は、１１画素×１１
ラインの探索領域Ｒ１中の画素から水平方向に２画素
毎、垂直方向に２ライン毎にサンプリングすることによ
ってサブサンプリングし、これによって５画素×５ライ
ンの縮小画像ＳＲ１を作成する手段である。
ラインの探索領域Ｒ１中の画素から水平方向に２画素
毎、垂直方向に２ライン毎にサンプリングすることによ
ってサブサンプリングし、これによって５画素×５ライ
ンの縮小画像ＳＲ１を作成する手段である。
【００２９】メモリＭは、探索領域Ｒ１中の画素のデー
タを格納するメモリであり、動きベクトルを評価する縮
小ブロック評価手段５０にその画素のデータを転送する
メモリである。
タを格納するメモリであり、動きベクトルを評価する縮
小ブロック評価手段５０にその画素のデータを転送する
メモリである。
【００３０】縮小テンプレート作成手段４０は、４画素
×４ラインのテンプレートを２画素×２ラインの小ブロ
ックに分割し、その小ブロックの中の所定位置に存在す
る画素を１画素づつサンプリングすることによってサブ
サンプリングし、これによって２画素×２ラインの縮小
テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４を作成す
る手段であり、縮小テンプレート作成部４１、４２、４
３、４４を有する。縮小テンプレート作成部４１、４
２、４３、４４は、それぞれ、縮小テンプレートＳＴ
１、ＳＴ２、ＳＴ３、ＳＴ４を作成する。
×４ラインのテンプレートを２画素×２ラインの小ブロ
ックに分割し、その小ブロックの中の所定位置に存在す
る画素を１画素づつサンプリングすることによってサブ
サンプリングし、これによって２画素×２ラインの縮小
テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４を作成す
る手段であり、縮小テンプレート作成部４１、４２、４
３、４４を有する。縮小テンプレート作成部４１、４
２、４３、４４は、それぞれ、縮小テンプレートＳＴ
１、ＳＴ２、ＳＴ３、ＳＴ４を作成する。
【００３１】縮小ブロック評価手段５０は、縮小テンプ
レート作成手段４０によって作成された各縮小テンプレ
ートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４毎に、縮小画像作
成手段３０によって作成された５画素×５ラインの縮小
画像ＳＲ１内から切り出した２画素×２ラインの縮小ブ
ロックとの間で、対応する位置にある画素間の値の違い
を評価する手段であり、縮小テンプレートによる縮小ブ
ロック評価部５１、５２、５３、５４を有する。縮小ブ
ロック評価部５１、５２、５３、５４は、それぞれ、縮
小テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４によっ
て上記縮小ブロックを評価するものである。
レート作成手段４０によって作成された各縮小テンプレ
ートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４毎に、縮小画像作
成手段３０によって作成された５画素×５ラインの縮小
画像ＳＲ１内から切り出した２画素×２ラインの縮小ブ
ロックとの間で、対応する位置にある画素間の値の違い
を評価する手段であり、縮小テンプレートによる縮小ブ
ロック評価部５１、５２、５３、５４を有する。縮小ブ
ロック評価部５１、５２、５３、５４は、それぞれ、縮
小テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４によっ
て上記縮小ブロックを評価するものである。
【００３２】縮小テンプレート選択手段６０は、縮小テ
ンプレート作成手段４０によって作成された４個の縮小
テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４の中か
ら、縮小ブロック評価手段５０によって得られた評価値
が最小である縮小テンプレートを選択する手段である。
ンプレート作成手段４０によって作成された４個の縮小
テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４の中か
ら、縮小ブロック評価手段５０によって得られた評価値
が最小である縮小テンプレートを選択する手段である。
【００３３】一般的に表現すれば、ブロックマッチング
装置ＢＭ１は、所定画像中のａ画素×ｂラインの画素ブ
ロックで構成されるテンプレートと、上記所定画像以外
の画像中におけるｃ画素×ｄライン（ｃ≧ａ、ｄ≧ｂ）
で構成される探索領域の画像データから切り出されたａ
画素×ｂラインの画素ブロックとの間で、対応する位置
に存在する画素間の値の違いを評価するブロックマッチ
ング装置である。
装置ＢＭ１は、所定画像中のａ画素×ｂラインの画素ブ
ロックで構成されるテンプレートと、上記所定画像以外
の画像中におけるｃ画素×ｄライン（ｃ≧ａ、ｄ≧ｂ）
で構成される探索領域の画像データから切り出されたａ
画素×ｂラインの画素ブロックとの間で、対応する位置
に存在する画素間の値の違いを評価するブロックマッチ
ング装置である。
【００３４】そして、縮小画像作成手段３０は、上記探
索領域の画像データから水平方向にｍ画素毎、垂直方向
にｎライン毎にサンプリングすることによってサブサン
プリングし、（ｃ／ｍ）画素×（ｄ／ｎ）ラインの縮小
画像を作成する縮小画像作成手段の例である。
索領域の画像データから水平方向にｍ画素毎、垂直方向
にｎライン毎にサンプリングすることによってサブサン
プリングし、（ｃ／ｍ）画素×（ｄ／ｎ）ラインの縮小
画像を作成する縮小画像作成手段の例である。
【００３５】縮小テンプレート作成手段４０は、上記テ
ンプレートをｍ画素×ｎラインの小ブロックに分割し、
上記小ブロック中の所定の位置に存在する画素を１画素
づつサンプリングすることによってサブサンプリング
し、（ａ／ｍ）画素×（ｂ／ｎ）ラインの縮小テンプレ
ートをｍ×ｎ個作成する縮小テンプレート作成手段の例
である。
ンプレートをｍ画素×ｎラインの小ブロックに分割し、
上記小ブロック中の所定の位置に存在する画素を１画素
づつサンプリングすることによってサブサンプリング
し、（ａ／ｍ）画素×（ｂ／ｎ）ラインの縮小テンプレ
ートをｍ×ｎ個作成する縮小テンプレート作成手段の例
である。
【００３６】縮小ブロック評価手段５０は、上記縮小テ
ンプレート作成手段によって作成された上記縮小テンプ
レート毎に、上記縮小画像作成手段によって作成された
上記縮小画像内から切り出した（ａ／ｍ）画素×（ｂ／
ｎ）ラインの画素ブロックとの間で、対応する位置にあ
る画素間の値の違いを評価する縮小ブロック評価手段の
例である。
ンプレート作成手段によって作成された上記縮小テンプ
レート毎に、上記縮小画像作成手段によって作成された
上記縮小画像内から切り出した（ａ／ｍ）画素×（ｂ／
ｎ）ラインの画素ブロックとの間で、対応する位置にあ
る画素間の値の違いを評価する縮小ブロック評価手段の
例である。
【００３７】次に、ブロックマッチング装置ＢＭ１の動
作について説明する。
作について説明する。
【００３８】図２に示すフローチャートにおいて、ま
ず、探索領域Ｒ１を構成する画素から所定の画素をサブ
サンプリングすることによって、縮小画像ＳＲ１を作成
する。つまり、探索領域Ｒ１の画像データを入力し（Ｓ
１）、探索領域Ｒ１を構成する画素のうちで、図３に示
す画素Ｅ１１を選択し、この選択された画素Ｅ１１をサ
ブサンプリングすることによって、縮小画像ＳＲ１を作
成する。
ず、探索領域Ｒ１を構成する画素から所定の画素をサブ
サンプリングすることによって、縮小画像ＳＲ１を作成
する。つまり、探索領域Ｒ１の画像データを入力し（Ｓ
１）、探索領域Ｒ１を構成する画素のうちで、図３に示
す画素Ｅ１１を選択し、この選択された画素Ｅ１１をサ
ブサンプリングすることによって、縮小画像ＳＲ１を作
成する。
【００３９】次に、縮小テンプレートＳＴ１、ＳＴ２、
ＳＴ３、ＳＴ４を作成する。つまり、テンプレートＴ１
の画素データを入力し（Ｓ１１）、テンプレートＴ１を
構成する画素から画素Ｅ１をサブサンプリングすること
によって、１個目の縮小テンプレートＳＴ１を作成し
（Ｓ１２）、テンプレートＴ１を構成する画素から画素
Ｅ２をサブサンプリングすることによって、２個目の縮
小テンプレートＳＴ２を作成し（Ｓ１３）、テンプレー
トＴ１を構成する画素から画素Ｅ３をサブサンプリング
することによって、３個目の縮小テンプレートＳＴ３を
作成し（Ｓ１４）、テンプレートＴ１を構成する画素か
ら画素Ｅ４をサブサンプリングすることによって、４個
目の縮小テンプレートＳＴ４を作成する（Ｓ１５）。そ
して、評価の回数を示す関数ｎを１にセットする（Ｓ１
６）。
ＳＴ３、ＳＴ４を作成する。つまり、テンプレートＴ１
の画素データを入力し（Ｓ１１）、テンプレートＴ１を
構成する画素から画素Ｅ１をサブサンプリングすること
によって、１個目の縮小テンプレートＳＴ１を作成し
（Ｓ１２）、テンプレートＴ１を構成する画素から画素
Ｅ２をサブサンプリングすることによって、２個目の縮
小テンプレートＳＴ２を作成し（Ｓ１３）、テンプレー
トＴ１を構成する画素から画素Ｅ３をサブサンプリング
することによって、３個目の縮小テンプレートＳＴ３を
作成し（Ｓ１４）、テンプレートＴ１を構成する画素か
ら画素Ｅ４をサブサンプリングすることによって、４個
目の縮小テンプレートＳＴ４を作成する（Ｓ１５）。そ
して、評価の回数を示す関数ｎを１にセットする（Ｓ１
６）。
【００４０】図４は、ブロックマッチング装置ＢＭ１に
おいて、４個の縮小テンプレートＳＴ１〜ＳＴ４を作成
する一例を示す図である。
おいて、４個の縮小テンプレートＳＴ１〜ＳＴ４を作成
する一例を示す図である。
【００４１】ブロックマッチング装置ＢＭ１において、
探索領域Ｒ１中の画素から上記従来例におけるサブサン
プリング法と同様に、画素７（●）をサブサンプリング
することによって、縮小画像ＳＲ１を作成する。つま
り、１１画素×１１ラインの探索領域Ｒ１中の画素から
水平方向に２画素毎、垂直方向に２ライン毎に、サブサ
ンプリングして５画素×５ラインの縮小画像ＳＲ１を作
成する。
探索領域Ｒ１中の画素から上記従来例におけるサブサン
プリング法と同様に、画素７（●）をサブサンプリング
することによって、縮小画像ＳＲ１を作成する。つま
り、１１画素×１１ラインの探索領域Ｒ１中の画素から
水平方向に２画素毎、垂直方向に２ライン毎に、サブサ
ンプリングして５画素×５ラインの縮小画像ＳＲ１を作
成する。
【００４２】一方、テンプレートＴ１中の画素は、図３
に示すように、まず、互いに隣接する２画素×２ライン
＝４画素を構成する画素Ｅ１（▲）、Ｅ２（▽）、Ｅ３
（★）、Ｅ４（☆）のうちで、左上の画素Ｅ１（▲）を
サブサンプリングし、縮小テンプレートＳＴ１を作成す
る。これと同様に、右上の画素Ｅ２（▽）、左下の画素
Ｅ３（★）、右下の画素Ｅ４（☆）をサブサンプリング
し、それぞれ、縮小テンプレートＳＴ２、ＳＴ３、ＳＴ
４を作成する。
に示すように、まず、互いに隣接する２画素×２ライン
＝４画素を構成する画素Ｅ１（▲）、Ｅ２（▽）、Ｅ３
（★）、Ｅ４（☆）のうちで、左上の画素Ｅ１（▲）を
サブサンプリングし、縮小テンプレートＳＴ１を作成す
る。これと同様に、右上の画素Ｅ２（▽）、左下の画素
Ｅ３（★）、右下の画素Ｅ４（☆）をサブサンプリング
し、それぞれ、縮小テンプレートＳＴ２、ＳＴ３、ＳＴ
４を作成する。
【００４３】次に、縮小テンプレートＳＴ１〜ＳＴ４に
よって、縮小画像ＳＲ１を評価する。つまり、縮小画像
ＳＲ１から２画素×２ラインの縮小ブロックＳＩ１を作
成し（Ｓ２０）、縮小テンプレートＳＴ１によって縮小
ブロックＳＩ１を評価し、その評価値ＥＶ11を得（Ｓ２
１）、縮小テンプレートＳＴ２によって縮小ブロックＳ
Ｉ１を評価し、その評価値ＥＶ12を得（Ｓ２２）、縮小
テンプレートＳＴ３によって縮小ブロックＳＩ１を評価
し、その評価値ＥＶ13を得（Ｓ２３）、縮小テンプレー
トＳＴ４によって縮小ブロックＳＩ１を評価し、その評
価値ＥＶ14を得る（Ｓ２４）。そしてｎを１インクリメ
ントし（Ｓ２５）、ステップＳ２０に戻り、縮小画像Ｓ
Ｒ１から２画素×２ラインの縮小ブロックＳＩ２を作成
し、評価値ＥＶ21、ＥＶ22、ＥＶ23、ＥＶ24を得る。そ
して、ステップＳ２０〜Ｓ２５の動作を、所定回数繰り
返し、評価値ＥＶ31、ＥＶ32、ＥＶ33、ＥＶ34〜Ｅ
Ｖn1、ＥＶn2、ＥＶn3、ＥＶn4を得る（Ｓ２６）。
よって、縮小画像ＳＲ１を評価する。つまり、縮小画像
ＳＲ１から２画素×２ラインの縮小ブロックＳＩ１を作
成し（Ｓ２０）、縮小テンプレートＳＴ１によって縮小
ブロックＳＩ１を評価し、その評価値ＥＶ11を得（Ｓ２
１）、縮小テンプレートＳＴ２によって縮小ブロックＳ
Ｉ１を評価し、その評価値ＥＶ12を得（Ｓ２２）、縮小
テンプレートＳＴ３によって縮小ブロックＳＩ１を評価
し、その評価値ＥＶ13を得（Ｓ２３）、縮小テンプレー
トＳＴ４によって縮小ブロックＳＩ１を評価し、その評
価値ＥＶ14を得る（Ｓ２４）。そしてｎを１インクリメ
ントし（Ｓ２５）、ステップＳ２０に戻り、縮小画像Ｓ
Ｒ１から２画素×２ラインの縮小ブロックＳＩ２を作成
し、評価値ＥＶ21、ＥＶ22、ＥＶ23、ＥＶ24を得る。そ
して、ステップＳ２０〜Ｓ２５の動作を、所定回数繰り
返し、評価値ＥＶ31、ＥＶ32、ＥＶ33、ＥＶ34〜Ｅ
Ｖn1、ＥＶn2、ＥＶn3、ＥＶn4を得る（Ｓ２６）。
【００４４】上記実施例においては、４個の縮小テンプ
レートＳＴ１〜ＳＴ４のそれぞれによって、縮小ブロッ
クＳＩ１〜ＳＩｎを順次、評価し、評価値を得るように
しているが、縮小ブロックＳＩ１〜ＳＩｎの１つについ
て、４個の縮小テンプレートＳＴ１〜ＳＴ４による評価
を同時に実行するようにしてもよい。
レートＳＴ１〜ＳＴ４のそれぞれによって、縮小ブロッ
クＳＩ１〜ＳＩｎを順次、評価し、評価値を得るように
しているが、縮小ブロックＳＩ１〜ＳＩｎの１つについ
て、４個の縮小テンプレートＳＴ１〜ＳＴ４による評価
を同時に実行するようにしてもよい。
【００４５】そして、縮小テンプレート選択手段６０
が、評価値ＥＶ11〜ＥＶn4のうちで最小の評価値を選択
し（Ｓ３１）、この最小の評価値に対応する縮小ブロッ
ク（画素ブロック）を出力し（Ｓ３２）、上記最小の評
価値に対応する縮小テンプレートの動きベクトルを選択
する。なお、縮小テンプレートＳＴ１、ＳＴ２、ＳＴ
３、ＳＴ４の動きベクトルは、それぞれ、（２ｘ，２
ｙ）、（２ｘ＋１，２ｙ）、（２ｘ，２ｙ＋１）、（２
ｘ＋１，２ｙ＋１）である。なお、ｘとｙとの範囲は、
それぞれ−２〜＋１である。
が、評価値ＥＶ11〜ＥＶn4のうちで最小の評価値を選択
し（Ｓ３１）、この最小の評価値に対応する縮小ブロッ
ク（画素ブロック）を出力し（Ｓ３２）、上記最小の評
価値に対応する縮小テンプレートの動きベクトルを選択
する。なお、縮小テンプレートＳＴ１、ＳＴ２、ＳＴ
３、ＳＴ４の動きベクトルは、それぞれ、（２ｘ，２
ｙ）、（２ｘ＋１，２ｙ）、（２ｘ，２ｙ＋１）、（２
ｘ＋１，２ｙ＋１）である。なお、ｘとｙとの範囲は、
それぞれ−２〜＋１である。
【００４６】上記実施例において、縮小テンプレートＳ
Ｔ１、ＳＴ２、ＳＴ３、ＳＴ４を作成する動作（Ｓ１１
〜Ｓ１５）を、縮小画像ＳＲ１を作成する動作（Ｓ１、
Ｓ２）よりも先に実行してもよく、また、縮小テンプレ
ートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４を作成する動作
（Ｓ１１〜Ｓ１５）と縮小画像ＳＲ１を作成する動作
（Ｓ１、Ｓ２）とを同時に実行するようにしてもよい。
Ｔ１、ＳＴ２、ＳＴ３、ＳＴ４を作成する動作（Ｓ１１
〜Ｓ１５）を、縮小画像ＳＲ１を作成する動作（Ｓ１、
Ｓ２）よりも先に実行してもよく、また、縮小テンプレ
ートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４を作成する動作
（Ｓ１１〜Ｓ１５）と縮小画像ＳＲ１を作成する動作
（Ｓ１、Ｓ２）とを同時に実行するようにしてもよい。
【００４７】図５は、ブロックマッチング装置ＢＭ１に
おいて、４個の縮小テンプレートＳＴ１、ＳＴ２、ＳＴ
３、ＳＴ４の中の１個が、全探索ブロックマッチング法
と同じ大きさのずれを持つことを説明する図である。
おいて、４個の縮小テンプレートＳＴ１、ＳＴ２、ＳＴ
３、ＳＴ４の中の１個が、全探索ブロックマッチング法
と同じ大きさのずれを持つことを説明する図である。
【００４８】図５では、動きを検出されるべき探索領域
Ｒ１における縮小ブロックＢＬ１と、縮小テンプレート
ＳＴ４との間に、水平方向、垂直方向共に０．３画素の
ずれがある場合を示してある。全探索ブロックマッチン
グ法に比べて、上記実施例は、評価画素数は１／４に減
少しているものの、縮小ブロックＳＩ１と縮小テンプレ
ートＳＴ４との間におけるずれの大きさは、全探索ブロ
ックマッチング法で探索した場合のテンプレートと画素
ブロックとの間におけるずれの大きさと同じである。
Ｒ１における縮小ブロックＢＬ１と、縮小テンプレート
ＳＴ４との間に、水平方向、垂直方向共に０．３画素の
ずれがある場合を示してある。全探索ブロックマッチン
グ法に比べて、上記実施例は、評価画素数は１／４に減
少しているものの、縮小ブロックＳＩ１と縮小テンプレ
ートＳＴ４との間におけるずれの大きさは、全探索ブロ
ックマッチング法で探索した場合のテンプレートと画素
ブロックとの間におけるずれの大きさと同じである。
【００４９】上記実施例では、縮小画像を縮小テンプレ
ート毎に評価するが、この場合、上記実施例では、探索
領域Ｒ１における画素のうち、水平方向の画素数を１／
２にし、ライン数を１／２したものが縮小画像であるの
で、縮小画像についてブロックマッチングする場合、探
索領域Ｒ１についてブロックマッチングするよりも、１
／４の画素数で評価することになる。つまり、上記実施
例は、従来の全探索ブロックマッチング法の１／４画素
数で評価するできることになる。
ート毎に評価するが、この場合、上記実施例では、探索
領域Ｒ１における画素のうち、水平方向の画素数を１／
２にし、ライン数を１／２したものが縮小画像であるの
で、縮小画像についてブロックマッチングする場合、探
索領域Ｒ１についてブロックマッチングするよりも、１
／４の画素数で評価することになる。つまり、上記実施
例は、従来の全探索ブロックマッチング法の１／４画素
数で評価するできることになる。
【００５０】また、上記実施例において、４個の縮小テ
ンプレートＳＴ１〜ＳＴ４のうちの１個と縮小ブロック
ＳＩｎとの間のずれの大きさは、必ず、全探索ブロック
マッチング法におけるテンプレートＴ０と画素ブロック
５との間のずれの大きさと同じである。したがって、上
記実施例は、従来の全探索ブロックマッチング法と同程
度の精度を得ることができる。
ンプレートＳＴ１〜ＳＴ４のうちの１個と縮小ブロック
ＳＩｎとの間のずれの大きさは、必ず、全探索ブロック
マッチング法におけるテンプレートＴ０と画素ブロック
５との間のずれの大きさと同じである。したがって、上
記実施例は、従来の全探索ブロックマッチング法と同程
度の精度を得ることができる。
【００５１】上記従来例では、画像にノイズが含まれる
場合、２画素×２ライン＝４画素の平均値を計算して縮
小画像を作ることによって、低周波通過フィルタを構成
し、これによって、ノイズによる探索精度の劣化を防止
している。上記実施例においても、画像にノイズが含ま
れると、探索領域Ｒ１中のサブサンプリング画素Ｅ１１
（●）にノイズが含まれる場合、探索精度が劣化する。
場合、２画素×２ライン＝４画素の平均値を計算して縮
小画像を作ることによって、低周波通過フィルタを構成
し、これによって、ノイズによる探索精度の劣化を防止
している。上記実施例においても、画像にノイズが含ま
れると、探索領域Ｒ１中のサブサンプリング画素Ｅ１１
（●）にノイズが含まれる場合、探索精度が劣化する。
【００５２】図６は、上記実施例においては、隣接４画
素のデータを平均した値をデータとして有する画素を使
用して、上記と同様の方法によって、ブロックマッチン
グする方法の説明図である。
素のデータを平均した値をデータとして有する画素を使
用して、上記と同様の方法によって、ブロックマッチン
グする方法の説明図である。
【００５３】つまり、探索領域Ｒ１では、隣接４画素の
データを平均することによって得られる画素２２と、同
様に隣接４画素のデータを平均することによって得られ
る画素２３とのうちで、画素２３をサブサンプリングし
て縮小画像を作成する。
データを平均することによって得られる画素２２と、同
様に隣接４画素のデータを平均することによって得られ
る画素２３とのうちで、画素２３をサブサンプリングし
て縮小画像を作成する。
【００５４】一方、テンプレートＴ１は、２画素×２ラ
イン＝４画素のうちで、左上の画素２４（▼）、右上の
画素２５（▽）、左下の画素２６（★）、右下の画素２
７（☆２７）をサブサンプリングし、４個の縮小テンプ
レートを作成する。これら４個の縮小テンプレートで同
時に縮小画像を評価し（同時に縮小画像を評価しなくて
もよい）、評価値を得、これらの評価値のうちで、最小
の評価値を得た縮小テンプレートを選択し、画素ブロッ
クを特定し、その動きベクトルを求める。
イン＝４画素のうちで、左上の画素２４（▼）、右上の
画素２５（▽）、左下の画素２６（★）、右下の画素２
７（☆２７）をサブサンプリングし、４個の縮小テンプ
レートを作成する。これら４個の縮小テンプレートで同
時に縮小画像を評価し（同時に縮小画像を評価しなくて
もよい）、評価値を得、これらの評価値のうちで、最小
の評価値を得た縮小テンプレートを選択し、画素ブロッ
クを特定し、その動きベクトルを求める。
【００５５】上記実施例によれば、ブロックマッチング
によって動きベクトルを求める場合、ブロックマッチン
グにおける探索精度を、従来の全探索ブロックマッチン
グ法と同程度に維持しつつ、ブロックマッチングにおけ
る演算量を、従来の全探索ブロックマッチング法の１／
４に削減できる。しかも、メモリＭから探索領域中画素
を転送する量を、従来の全探索ブロックマッチング法の
１／４に抑えて、単画素精度の動きベクトルを直接求め
ることができる。
によって動きベクトルを求める場合、ブロックマッチン
グにおける探索精度を、従来の全探索ブロックマッチン
グ法と同程度に維持しつつ、ブロックマッチングにおけ
る演算量を、従来の全探索ブロックマッチング法の１／
４に削減できる。しかも、メモリＭから探索領域中画素
を転送する量を、従来の全探索ブロックマッチング法の
１／４に抑えて、単画素精度の動きベクトルを直接求め
ることができる。
【００５６】なお、上記実施例においては、隣接する複
数の画素のデータを平均することによって、低域通過フ
ィルタを構成するようにしているが、ノイズ除去のため
の平滑化処理であれば、他の方法を採用するようにして
もよい。
数の画素のデータを平均することによって、低域通過フ
ィルタを構成するようにしているが、ノイズ除去のため
の平滑化処理であれば、他の方法を採用するようにして
もよい。
【００５７】また、上記各実施例では、４：１にサブサ
ンプリングする場合のみを説明したが、２：１、８：
１、１６：１等の他の比率でサブサンプリングを行うこ
とによって縮小画像、縮小ブロックを作成するようにし
てもよい。この場合にも、上記と同様の効果を得ること
ができる。また、上記実施例では、隣接４画素のデータ
を平均した値を有する画素で構成される画像上で探索す
ることによって、精度の劣化を防止する例を示したが、
上記低域通過フィルタ以外の任意の低域通過フィルタを
かけることによって探索するようにしてもよく、これに
よって、精度の劣化を防止することができる。
ンプリングする場合のみを説明したが、２：１、８：
１、１６：１等の他の比率でサブサンプリングを行うこ
とによって縮小画像、縮小ブロックを作成するようにし
てもよい。この場合にも、上記と同様の効果を得ること
ができる。また、上記実施例では、隣接４画素のデータ
を平均した値を有する画素で構成される画像上で探索す
ることによって、精度の劣化を防止する例を示したが、
上記低域通過フィルタ以外の任意の低域通過フィルタを
かけることによって探索するようにしてもよく、これに
よって、精度の劣化を防止することができる。
【００５８】
【発明の効果】請求項１、２記載の発明によれば、ブロ
ックマッチングによって、動きベクトルを求める装置に
おいて、従来の全探索ブロックマッチング法における探
索精度と同程度の探索精度を維持しつつ、ブロックマッ
チングにおける演算量を、従来の全探索ブロックマッチ
ング法の１／４に削減することができ、しかも、探索領
域中画素の転送量を、従来の全探索ブロックマッチング
法の１／４に抑えて、単画素精度の動きベクトルを直接
求めることができるという効果を奏する。
ックマッチングによって、動きベクトルを求める装置に
おいて、従来の全探索ブロックマッチング法における探
索精度と同程度の探索精度を維持しつつ、ブロックマッ
チングにおける演算量を、従来の全探索ブロックマッチ
ング法の１／４に削減することができ、しかも、探索領
域中画素の転送量を、従来の全探索ブロックマッチング
法の１／４に抑えて、単画素精度の動きベクトルを直接
求めることができるという効果を奏する。
【００５９】請求項３記載の発明によれば、画像にノイ
ズが含まれる場合でも、探索精度の劣化を起こさないと
いう効果を奏する。
ズが含まれる場合でも、探索精度の劣化を起こさないと
いう効果を奏する。
【図１】本発明の一実施例であるブロックマッチング装
置ＢＭ１を示す図である。
置ＢＭ１を示す図である。
【図２】ブロックマッチング装置ＢＭ１の動作を示すフ
ローチャートである。
ローチャートである。
【図３】ブロックマッチング装置ＢＭ１において、探索
領域Ｒ１とテンプレートＴ１との関係を示す図である。
領域Ｒ１とテンプレートＴ１との関係を示す図である。
【図４】ブロックマッチング装置ＢＭ１において、４個
の縮小テンプレートＳＴ１〜ＳＴ４を作成する一例を示
す図である。
の縮小テンプレートＳＴ１〜ＳＴ４を作成する一例を示
す図である。
【図５】ブロックマッチング装置ＢＭ１において、４個
の縮小テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４の
中の１個が、全探索ブロックマッチング法と同じ大きさ
のずれを持つことを説明する図である。
の縮小テンプレートＳＴ１、ＳＴ２、ＳＴ３、ＳＴ４の
中の１個が、全探索ブロックマッチング法と同じ大きさ
のずれを持つことを説明する図である。
【図６】上記実施例において、隣接４画素のデータを平
均した値をデータとして有する画素を使用して、ブロッ
クマッチングする方法の説明図である。
均した値をデータとして有する画素を使用して、ブロッ
クマッチングする方法の説明図である。
【図７】従来のブロックマッチング装置の動作を説明す
る図であり、動き検出の対象となるテンプレートＴ０と
探索領域Ｒ０との関係を示す図である。
る図であり、動き検出の対象となるテンプレートＴ０と
探索領域Ｒ０との関係を示す図である。
【図８】上記従来例において、２画素×２ラインから１
画素をサブサンプリングするときに、取り出される画素
を示す図である。
画素をサブサンプリングするときに、取り出される画素
を示す図である。
【図９】画像にノイズが含まれる場合に検出精度が劣化
するという欠点を排除するために提案された従来の方法
であり、２画素×２ライン＝４画素の平均値を計算して
縮小画像を作成する方法を示す図である。
するという欠点を排除するために提案された従来の方法
であり、２画素×２ライン＝４画素の平均値を計算して
縮小画像を作成する方法を示す図である。
【図１０】従来のサブサンプリング法において、動きベ
クトルを検出する対象である探索領域Ｒ０中の縮小ブロ
ックＢＬとテンプレートＴ０との間に、水平方向に最大
１画素、垂直方向に最大１ラインのずれが存在している
ことを示す図である。
クトルを検出する対象である探索領域Ｒ０中の縮小ブロ
ックＢＬとテンプレートＴ０との間に、水平方向に最大
１画素、垂直方向に最大１ラインのずれが存在している
ことを示す図である。
ＢＭ１…ブロックマッチング装置、 ３０…縮小画像生成部、 Ｍ…メモリ、 ４０…縮小テンプレート作成手段、 ４１〜４４…縮小テンプレート作成部、 ＳＴ１〜ＳＴ４…縮小テンプレート、 ５０…縮小ブロック評価手段、 ５１〜５４…縮小ブロック評価部、 ６０…縮小テンプレート選択手段。
Claims (3)
- 【請求項１】 所定画像中のａ画素×ｂラインの画素ブ
ロックで構成されるテンプレートと、上記所定画像以外
の画像中におけるｃ画素×ｄライン（ｃ≧ａ、ｄ≧ｂ）
で構成される探索領域の画像データから切り出されたａ
画素×ｂラインの画素ブロックとの間で、対応する位置
に存在する画素間の値の違いを評価するブロックマッチ
ング装置において、 上記探索領域の画像データから水平方向にｍ画素毎、垂
直方向にｎライン毎にサンプリングすることによってサ
ブサンプリングし、（ｃ／ｍ）画素×（ｄ／ｎ）ライン
の縮小画像を作成する縮小画像作成手段と；上記テンプ
レートをｍ画素×ｎラインの小ブロックに分割し、上記
小ブロック中の所定の位置に存在する画素を１画素づつ
サンプリングすることによってサブサンプリングし、
（ａ／ｍ）画素×（ｂ／ｎ）ラインの縮小テンプレート
をｍ×ｎ個作成する縮小テンプレート作成手段と；上記
縮小テンプレート作成手段によって作成された上記縮小
テンプレート毎に、上記縮小画像作成手段によって作成
された上記縮小画像内から切り出した（ａ／ｍ）画素×
（ｂ／ｎ）ラインの画素ブロックとの間で、対応する位
置にある画素間の値の違いを評価する縮小ブロック評価
手段と；を有することを特徴とするブロックマッチング
装置。 - 【請求項２】 請求項１において、 上記縮小テンプレート作成手段によって作成された上記
ｍ×ｎ個の縮小テンプレートの中から、上記縮小ブロッ
ク評価手段によって得られた評価値が最小である縮小テ
ンプレートを選択する縮小テンプレート選択手段を有す
ることを特徴とするブロックマッチング装置。 - 【請求項３】 請求項１または請求項２において、 上記探索領域画像に含まれる各画素について、低域通過
フィルタによって高周波成分が低減された探索領域画像
と、上記低域通過フィルタと同じ低域通過フィルタによ
って高周波成分が低減されたテンプレートとを上記ブロ
ックマッチング装置に入力することを特徴とするブロッ
クマッチング装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22170096A JPH1051793A (ja) | 1996-08-05 | 1996-08-05 | ブロックマッチング装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22170096A JPH1051793A (ja) | 1996-08-05 | 1996-08-05 | ブロックマッチング装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH1051793A true JPH1051793A (ja) | 1998-02-20 |
Family
ID=16770915
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP22170096A Pending JPH1051793A (ja) | 1996-08-05 | 1996-08-05 | ブロックマッチング装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH1051793A (ja) |
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6169766B1 (en) | 1997-08-26 | 2001-01-02 | Matsushita Electric Industrial Co., Ltd. | Method and apparatus for detecting motion vector and image coding apparatus |
| JP2001169296A (ja) * | 1999-10-19 | 2001-06-22 | Deutsche Thomson Brandt Gmbh | デジタル入力ビデオ信号の動き推定方法 |
| US6370195B1 (en) | 1998-04-14 | 2002-04-09 | Hitachi, Ltd. | Method and apparatus for detecting motion |
| JP2006127195A (ja) * | 2004-10-29 | 2006-05-18 | Fujitsu Ltd | 画像センサ装置および画像センサシステム |
| JP2007194973A (ja) * | 2006-01-20 | 2007-08-02 | Victor Co Of Japan Ltd | 動きベクトル検出装置 |
| JP2009017113A (ja) * | 2007-07-03 | 2009-01-22 | Casio Comput Co Ltd | 有効性判定装置、画像処理装置及びプログラム |
| JP2012022654A (ja) * | 2010-07-16 | 2012-02-02 | Canon Inc | 画像処理装置、画像処理方法、およびプログラム |
| US9363515B2 (en) | 2011-03-09 | 2016-06-07 | Nippon Telegraph And Telephone Corporation | Image processing method, image processing apparatus, video encoding/decoding methods, video encoding/decoding apparatuses, and non-transitory computer-readable media therefor that perform denoising by means of template matching using search shape that is set in accordance with edge direction of image |
| US9438912B2 (en) | 2011-03-09 | 2016-09-06 | Nippon Telegraph And Telephone Corporation | Video encoding/decoding methods, video encoding/decoding apparatuses, and programs therefor |
-
1996
- 1996-08-05 JP JP22170096A patent/JPH1051793A/ja active Pending
Cited By (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6169766B1 (en) | 1997-08-26 | 2001-01-02 | Matsushita Electric Industrial Co., Ltd. | Method and apparatus for detecting motion vector and image coding apparatus |
| US6370195B1 (en) | 1998-04-14 | 2002-04-09 | Hitachi, Ltd. | Method and apparatus for detecting motion |
| US6496539B2 (en) | 1998-04-14 | 2002-12-17 | Hitachi, Ltd. | Method and apparatus for detecting motion |
| JP2001169296A (ja) * | 1999-10-19 | 2001-06-22 | Deutsche Thomson Brandt Gmbh | デジタル入力ビデオ信号の動き推定方法 |
| JP2006127195A (ja) * | 2004-10-29 | 2006-05-18 | Fujitsu Ltd | 画像センサ装置および画像センサシステム |
| JP2007194973A (ja) * | 2006-01-20 | 2007-08-02 | Victor Co Of Japan Ltd | 動きベクトル検出装置 |
| JP4674549B2 (ja) * | 2006-01-20 | 2011-04-20 | 日本ビクター株式会社 | 動きベクトル検出装置 |
| JP2009017113A (ja) * | 2007-07-03 | 2009-01-22 | Casio Comput Co Ltd | 有効性判定装置、画像処理装置及びプログラム |
| JP2012022654A (ja) * | 2010-07-16 | 2012-02-02 | Canon Inc | 画像処理装置、画像処理方法、およびプログラム |
| US9667841B2 (en) | 2010-07-16 | 2017-05-30 | Canon Kabushiki Kaisha | Image processing apparatus and image processing method |
| US9363515B2 (en) | 2011-03-09 | 2016-06-07 | Nippon Telegraph And Telephone Corporation | Image processing method, image processing apparatus, video encoding/decoding methods, video encoding/decoding apparatuses, and non-transitory computer-readable media therefor that perform denoising by means of template matching using search shape that is set in accordance with edge direction of image |
| US9438912B2 (en) | 2011-03-09 | 2016-09-06 | Nippon Telegraph And Telephone Corporation | Video encoding/decoding methods, video encoding/decoding apparatuses, and programs therefor |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6380986B1 (en) | Motion vector search method and apparatus | |
| US8437401B2 (en) | Refinement of motion vectors in hierarchical motion estimation | |
| JP5044568B2 (ja) | 予測誘導間引き探索を使用する動き推定 | |
| US6690729B2 (en) | Motion vector search apparatus and method | |
| KR100492127B1 (ko) | 적응형 움직임 추정장치 및 추정 방법 | |
| US8644387B2 (en) | Motion estimation method | |
| US7782957B2 (en) | Motion estimation circuit and operating method thereof | |
| US20080260033A1 (en) | Hybrid hierarchical motion estimation for video streams | |
| KR100870115B1 (ko) | 블록정합 및 움직임 보상 보간을 이용한 영상 형성 방법 | |
| US8130835B2 (en) | Method and apparatus for generating motion vector in hierarchical motion estimation | |
| US12114005B2 (en) | Encoding and decoding method and apparatus, and devices | |
| US11704840B2 (en) | Attribute information prediction method, encoder, decoder and storage medium | |
| US20050123039A1 (en) | Motion estimation method for motion picture encoding and recording medium having program recorded thereon to implement the motion estimation method | |
| JPH1051793A (ja) | ブロックマッチング装置 | |
| US9406376B2 (en) | Motion vector detection apparatus and method | |
| JP2011141710A (ja) | 奥行推定装置、奥行推定方法および奥行推定プログラム | |
| US9317904B2 (en) | Image processing system and image processing method | |
| JP2005506626A (ja) | 動き推定ユニット及び方法並びにかような動き推定ユニットを備えた画像処理装置 | |
| US6823012B2 (en) | Method and system for estimating motion vector at high speed for low bit-rate coding | |
| JP4377693B2 (ja) | 画像データ検索 | |
| US20130235274A1 (en) | Motion vector detection device, motion vector detection method, frame interpolation device, and frame interpolation method | |
| JP5788299B2 (ja) | 画像検索装置、画像検索方法およびプログラム | |
| JP5316309B2 (ja) | 画像処理装置および画像処理方法 | |
| US20100260435A1 (en) | Edge Directed Image Processing | |
| JP2008236096A (ja) | 動き探索方法、動き探索装置、動き探索プログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体 |