(57)【要約】【課題】複数の大きさのテンプレートに対応した動きベクトルを検出できる動きベクトル検出装置を少ないハード量およびコストで提供できるようにする。【解決手段】複数の大きさのテンプレート群に含まれる一つのテンプレートに対応する符号化対象の画素ブロックと，探索領域内から切り出した画素ブロック群に含まれる前記テンプレートと同じ大きさの画素ブロックとの間で，対応する位置にある画素間の値の違いを評価し，評価値が最小となる画素ブロックの位置を動きベクトルとして検出することを，テンプレート群に含まれる全てのテンプレートについて行う動きベクトル検出装置において，テンプレート群に含まれる複数の最小のテンプレートの各々に対応した評価値計算回路１０２と，評価値計算回路１０２の出力を加算して，最小のテンプレートより大きな全てのテンプレートの評価値を計算する所定の数の加算回路１０３とを備える。【選択図】      図１
2004200984.tif 000002
【特許請求の範囲】
【請求項１】
動画像符号化の対象である動画像から選択した第１の画像中の所定の大きさの画素ブロックを分割して得られるテンプレート群に含まれる一つのテンプレートと，前記動画像符号化の対象である動画像から選択した第２の画像中における探索領域内から切り出した画素ブロック群に含まれる前記一つのテンプレートと同じ大きさの画素ブロックとの間で，対応する位置にある画素間の値の違いを評価し，評価値が最小となる画素ブロックの位置を動きベクトルとして検出することを，前記テンプレート群に含まれる全てのテンプレートについて行う動きベクトル検出装置において，
前記テンプレート群に含まれる複数の最小のテンプレートの各々に対応した評価値計算回路と，
前記評価値計算回路の出力を加算して，前記最小のテンプレートより大きな全てのテンプレートの評価値を計算する所定の数の加算回路とを含む
ことを特徴とする動きベクトル検出装置。
【請求項２】
動画像符号化の対象である動画像から選択した第１の画像中の水平方向が（ｍ×ａ）画素，垂直方向が（ｎ×ｂ）ラインである画素ブロックを分割して得られるテンプレート群に含まれるテンプレートであって，水平方向がａ画素，垂直方向がｂラインであるテンプレートから，水平方向が（ｍ×ａ）画素，垂直方向が（ｎ×ｂ）ラインの大きさのテンプレートまでの複数種類の大きさのテンプレートの中の一つと，前記動画像符号化の対象である動画像から選択した第２の画像中における探索領域内から切り出した画素ブロック群に含まれる前記一つのテンプレートと同じ大きさの画素ブロックとの間で，対応する位置にある画素間の値の違いを評価し，評価値が最小となる画素ブロックの位置を動きベクトルとして検出することを，前記テンプレート群に含まれる全てのテンプレートについて行う動きベクトル検出装置において，
水平方向がａ画素，垂直方向がｂラインであるテンプレート群に含まれる個々のテンプレートに対応したｍ×ｎ個の評価値計算回路と，
前記ｍ×ｎ個の評価値計算回路の出力を加算して，水平方向がａ画素，垂直方向がｂラインであるテンプレートより大きなテンプレートの評価値を計算する所定の数の加算回路とを含む
ことを特徴とする動きベクトル検出装置。
【請求項３】
請求項２記載の動きベクトル検出装置であって，
前記評価値計算回路において，水平方向について，水平方向がａ画素，垂直方向がｂラインであるテンプレートの画素数と同じａ個の画素ブロックの評価を行うことを繰り返すことにより，探索範囲に含まれる水平方向がａ画素，垂直方向がｂラインである全ての画素ブロックの評価を行う
ことを特徴とする動きベクトル検出装置。
【請求項４】
請求項３記載の動きベクトル検出装置であって，
前記評価値計算回路は，水平方向がａ画素，垂直方向がｂラインであるテンプレートの評価値を評価するために，同一構成のａ個の演算器からなるｂ個の演算器群で構成され，探索領域内から切り出した画素ブロック中の２画素のうちいずれか１画素を選択することにより構成されるａ個の画素を外部より入力し，同一の列に属するｂ個の演算器全てに同一の画素を供給する画素供給手段を有し，
前記演算器は，水平方向がａ画素，垂直方向がｂラインであるテンプレート内の画素であって，対応した位置に存在する画素をそれぞれ保持する手段と，前記画素供給手段によって供給される探索領域内から切り出した画素ブロック中の画素と前記演算器に保持されているテンプレート中の画素との間における値の違いを評価値として計算する手段と，前段の演算器から入力される評価値の和に当該演算器自体の評価値を加算する手段と，当該加算結果を１単位時間後に次段の演算器に送る手段とを有する
ことを特徴とする動きベクトル検出装置。
【請求項５】
請求項４記載の動きベクトル検出装置であって，
前記ｍ×ｎ個の評価値計算回路に対し，探索領域内から切り出した画素ブロック中の画素をそれぞれ２画素ずつ，合計２×ｍ×ｎ画素供給する手段と，
個々の評価値計算回路ごとに，該２画素のうちいずれか１画素を選択することにより構成されるａ個の画素を，評価値計算回路中の前記演算器に供給する手段とを有する
ことを特徴とする動きベクトル検出装置。
【請求項６】
請求項４記載の動きベクトル検出装置であって，
垂直方向のｎ個の前記評価値計算回路をひとまとまりとして，探索領域内から切り出した画素ブロック中の画素をそれぞれ２画素ずつ，合計２×ｍ画素供給する手段と，
垂直方向のｎ個の前記評価値計算回路ごとに，該２画素のうちいずれか１画素を選択することにより構成されるａ個の画素を，評価値計算回路中の前記演算器に供給する手段と，
垂直方向にｊ番目（ｊ＝１，２，…，ｎ）の前記評価値計算回路の出力を，（ａ×ｂ）×ｙ単位時間（ｙ＝ｎ−１，ｎ−２，…，２，１，０）遅延させる所定の数の遅延手段とを有し，
垂直方向にｊ番目の前記評価値計算回路を，垂直方向における最初の前記評価値計算回路（ｊ＝１）が動作を開始してから（ａ×ｂ）×（ｊ−１）単位時間後に動作を開始させる
ことを特徴とする動きベクトル検出装置。
【請求項７】
請求項４記載の動きベクトル検出装置であって，
前記ｍ×ｎ個の評価値計算回路全体に対し，探索領域内から切り出した画素ブロック中の画素を２画素のみ供給する手段と，
前記ｍ×ｎ個の評価値計算回路全体に共通の手段であって，該２画素のうちいずれか１画素を選択することにより構成されるａ個の画素を，評価値計算回路中の前記演算器に供給する手段と，
水平方向にｉ番目，垂直方向にｊ番目（ｉ＝１，２，…，ｍ；ｊ＝１，２，…，ｎ）の前記評価値計算回路の出力を，（ａ×ｂ）×（ｍ＋１）×（ｘ−１）＋（ａ×ｂ）×ｙ単位時間（ｘ＝ｍ−１，ｍ−２，…，２，１，０；ｙ＝ｎ−１，ｎ−２，…，２，１，０）遅延させる所定の数の遅延手段とを有し，
水平方向にｉ番目，垂直方向にｊ番目の前記評価値計算回路を最初の前記評価値計算回路（ｉ＝１，ｊ＝１）が動作を開始してから（ａ×ｂ）×（ｍ＋１）×（ｉ−１）＋（ａ×ｂ）×（ｊ−１）単位時間後に動作を開始させる
ことを特徴とする動きベクトル検出装置。
【請求項８】
請求項２記載の動きベクトル検出装置であって，
前記評価値計算回路において，垂直方向について，水平方向がａ画素，垂直方向がｂラインであるテンプレートのライン数と同じｂ個の画素ブロックの評価を行うことを繰り返すことにより，探索範囲に含まれる水平方向がａ画素，垂直方向がｂラインである全ての画素ブロックの評価を行う
ことを特徴とする動きベクトル検出装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，動画像符号化処理において，画像間における動きを検出するために用いられる動きベクトル検出装置に関するものであり，特に，１６画素×１６ラインや８画素×８ライン等，複数種類の大きさの画素ブロックの動きを検出する動きベクトル検出装置に関するものである。
【０００２】
【従来の技術】
動画像には，時間的に連続した複数の画像が存在する。動きベクトル検出装置とは，動画像において，ある画像中の画素ブロックが他の画像中のどの位置から動いてきたかを検出する装置である。
【０００３】
図１６は，動き検出の対象となる画素ブロック（以下，テンプレートと呼ぶ）１と探索領域２の例を示す。ここで，テンプレート１は，ある画像中の画素ブロック，探索領域２は，他の画像中の画素ブロックである。テンプレート１と探索領域２の両方とも任意の大きさの矩形領域が考えられるが，以下では，テンプレート１が４画素×４ライン，探索領域２は１１画素×１１ラインの場合について説明する。この場合，探索領域２の中心の４画素×４ラインの領域を動きベクトル（０，０）と設定すると，探索範囲は，水平方向，垂直方向とも−３〜＋４となる。ａ0,0 〜ａ3,3 はテンプレート１中の画素を表し，ｘ0,0 〜ｘa,a （添え字は１６進数で表す）は探索領域２中の画素を表す。なお，本明細書では，水平方向の画素数の単位を画素，垂直方向の画素数の単位をラインと呼ぶ。
【０００４】
図１７は，全探索法による動き検出の方法を説明するための図である。探索領域２から取り得る全ての４画素×４ラインの領域を切り出し，その４画素×４ラインの領域中の画素とテンプレート１中の対応する位置にある画素との値の違いを差分絶対値の総和または差分自乗値の総和等で評価する。１画素または１ラインずれた４画素×４ラインの領域全部，すなわち８×８＝６４個の領域についてこの総和を計算し，この総和が最も小さい領域からテンプレート１が動いてきたものとする。
【０００５】
なお，評価式として何を用いるかは本発明の本質ではないので，以下では，差分絶対値の総和を用いる場合について説明する。また，本発明による動きベクトル検出装置は，同期式回路で実現される場合が多いが，同期式回路は通常クロック（以下，ＣＫと記す）に同期して動作する。そこで，以下では動作の単位をＣＫと呼ぶ。
【０００６】
図１８は，第１の従来例の動きベクトル検出装置における差分絶対値和計算回路（例えば，特許文献１の段落［０００６］〜［０００８］および図６，または非特許文献１の９１６ページ，９１７ページおよび図７参照）の構成を示す図である。符号３で示すＰi,j （ｉ＝０〜３，ｊ＝０〜３）は，テンプレート１と探索領域２の対応する画素の間で差分絶対値を計算する回路であり，テンプレート１中の画素と１対１に対応しており，そのテンプレート１中の画素ａi,j を保持し，各行ごとに放送（供給）される探索領域２中の画素をＣＫごとに取り込み，差分絶対値を計算する。４はレジスタ，５は加算器，６は総和回路である。
【０００７】
図１９は，図１８の差分絶対値和計算回路において，探索領域２の左上の角から切り出された４画素×４ラインの領域とテンプレート１中の画素間で差分絶対値和Ｓ0,0 を計算するときのタイミングを表した図である。図示したように，０ＣＫ目，１ＣＫ目，２ＣＫ目，３ＣＫ目に，それぞれ１列目，２列目，３列目，４列目の差分絶対値和が計算され，４ＣＫ目に各行の部分和Ｓi の総和が計算され，５ＣＫで１行目から４行目までの各行の部分和Ｓi の和Ｓ0,0 が出力される。
【０００８】
図２０は，第２の従来例の動きベクトル検出装置における差分絶対値和計算回路（例えば，特許文献１の段落［００１０］〜［００１２］および図９，または非特許文献１の９１９ページ，９２０ページおよび図１４参照）の構成を示す図である。Ｐi,j ３，レジスタ４，加算器５の機能は，上述した第１の従来例と同一である。
【０００９】
図２１は，図２０の差分絶対値和計算回路において，探索領域２の左上の角から切り出された４画素×４ラインの領域とテンプレート１中の画素間で差分絶対値和Ｓ0,0 を計算するときのタイミングを表した図である。図中のＳ0:j は１行目から（ｊ＋１）行目までの各行の部分和Ｓi の和を意味する。上記図２０に示した差分絶対値和計算回路では，探索領域２中の画素の入力を各行ごとに１ＣＫずつ遅らせることにより，各行の部分和Ｓi が出力されるタイミングを各行ごとに１ＣＫずつ遅らせ，ＣＫごとに各行の部分和Ｓi を加算する。
【００１０】
図２２は，第３の従来例の動きベクトル検出装置における差分絶対値和計算回路（例えば，特許文献１の段落［００１９］〜［００２１］および図１，または非特許文献１の９２０ページ，９２１ページおよび図１５参照）の構成を示す図である。Ｐi,j ３，レジスタ４，加算器５の機能は，上述した第１，第２の従来例と同一である。個々のＰi,j ３の出力は，加算器５によって前段の加算器５から送られてくる計算結果と加算され，次段の加算器５に送られる。この次段への送りは，レジスタ４を介してＣＫごとに行なわれる。
【００１１】
図２３は，図２２の差分絶対値和計算回路において，探索領域２の左上の角から切り出された４画素×４ラインの領域とテンプレート１中の画素間で差分絶対値和Ｓ0,0 を計算するときのタイミングを説明するための図である。本従来例の差分絶対値和計算回路では，探索領域２中の画素の入力を各行ごとに４ＣＫずつ遅らせることにより，各行の部分和Ｓi が得られるタイミングを行ごとに４ＣＫずつ遅らせる。この場合，各行の部分和Ｓi が得られる次のＣＫで，その一つ下の行の計算が始まることになる。したがって，本従来例では，各行の部分和Ｓi を次の行の先頭の差分絶対値と加算することができるので，行間を連続させた１次元アレイ構造とすることができる。
【００１２】
ここで，上述した第１〜第３の従来例の差分絶対値和計算回路では，計算対象である探索領域２から切り出された４画素×４ラインの領域が探索領域の右端から左端に移るとき無効サイクルが生じる。図２４は，無効サイクルが生じる場合の探索領域２からの画素読み出し例を示す。探索領域２の左上の角から切り出された４画素×４ラインの領域とテンプレート１中の画素間の差分絶対値和をＳ0,0 ，右横に１画素ずれた領域とテンプレート１中の画素間の差分絶対値和をＳ0,1 ，以下順次Ｓ0,2 ，Ｓ0,3 とし，探索領域２の左上の角の４画素×４ラインの領域から１ライン下にずれた領域とテンプレート１中の画素間の差分絶対値和をＳ1,0 とすると，差分絶対値和Ｓ0,0 からＳ0,7 までは連続して計算される。しかし，Ｓ0,7 の計算に必要な画素ｘ0,a ，ｘ1,a ，ｘ2,a ，ｘ3,a の供給が終わらなければ，Ｓ1,0 の計算に使われるｘ1,0 ，ｘ2,0 ，ｘ3,0 ，ｘ4,0 は供給できない。そのため，Ｓ1,0 の計算を開始するまでに３（テンプレートの横方向の画素数−１）ＣＫ無効サイクルが生じる。なお，探索領域から切り出された４画素×４ラインの領域が探索領域の下端から上端に移るときには，同様の理由で１５ＣＫの無効サイクルが生じる。
【００１３】
図２５は，第４の従来例の動きベクトル検出装置における差分絶対値和計算回路（例えば，非特許文献１の９２２ページおよび図１６参照）の構成を示す図である。外部から入力される２画素からいずれか１画素を選択するためのセレクタ７が付加された以外は，第３の従来例と同一の構成である。本従来例においては，ｘ0,8 ，ｘ1,8 ，ｘ2,8 ，ｘ3,8 等の探索領域右端の画素と同時にｘ1,0 ，ｘ2,0 ，ｘ3,0 ，ｘ4,0 等の探索領域左端の画素が供給され，セレクタ７により選択される。このため，Ｓ0,7 に続いて連続してＳ1,0 の計算を開始でき，上記無効サイクルを削除できる。
【００１４】
図２６は，第５の従来例の動きベクトル検出装置における差分絶対値和計算回路（例えば，特許文献２の段落［００４１］〜［００４３］および図２〜図４，または非特許文献１の９２２ページおよび図１７参照）の構成を示す図である。また，図２７は，本従来例における探索領域からの画素読み出し例を示す図である。Ｐi,j ３，レジスタ４，加算器５，セレクタ７の機能は，上述した第１〜第４の従来例と同一である。ここで，後述する実施例での説明の都合上，セレクタ７を除き，Ｐi,j ３，レジスタ４および加算器５からなる部分を演算器と呼び，該演算器で構成される評価値計算回路をＰＥアレイ８と呼ぶ。
【００１５】
本従来例では，探索する水平方向の動きベクトル数をテンプレートの水平方向の画素数と一致させる。この構成において，ｘ0,4 ，ｘ1,4 ，ｘ2,4 ，ｘ3,4 等の探索領域右端の画素と同時にｘ1,0 ，ｘ2,0 ，ｘ3,0 ，ｘ4,0 等の探索領域左端の画素を供給することにより無効サイクルを削除でき，さらに同一の列に属するＰi,j （ｉ＝０〜３）に供給する探索領域中の画素が同一となるという効果が得られる。
【００１６】
図２８は，本従来例において図１６に示した探索領域２中の動きベクトルを検出する場合の例を示す。水平方向の動きベクトルを−３〜０と１〜４の２回に分けて探索することにより探索領域２中の動きベクトルを全て検出できる。
【００１７】
【特許文献１】
特許第３１２７９８０号公報
【特許文献２】
特許第２８３８８１７号公報
【非特許文献１】
南俊宏，近藤利夫，村主一仁，笠井良太，“１次元シストリックアレー型全探索動きベクトル検出器の提案”，信学論（Ｄ−Ｉ），ｖｏｌ．Ｊ７８−Ｄ−Ｉ，ｎｏ．１２，ｐｐ．９１３−９２５，Ｄｅｃ．１９９５．
【００１８】
【発明が解決しようとする課題】
ところが，最近の動画像符号化の国際標準規格では，テンプレートとして複数の大きさの画素ブロックを用いるものがある。例えば，Ｈ．２６３では，テンプレートとして１６画素×１６ラインと８画素×８ラインの２種類の画素ブロックを用いる。また，Ｈ．２６Ｌでは，４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ライン，８画素×１６ライン，１６画素×８ラインおよび１６画素×１６ラインの７種類の画素ブロックを用いる。これら各大きさのテンプレートごとに動きベクトル検出装置を別々に設けると，ハード量およびコストが増大するという問題がある。
【００１９】
本発明は上述した点に鑑みてなされたもので，その目的は，複数の大きさのテンプレートに対応した動きベクトルを検出できる動きベクトル検出装置を，最小のテンプレートの動きベクトルを検出する動きベクトル検出装置と同程度のハード量およびコストで提供することである。
【００２０】
【課題を解決するための手段】
このために本発明における動きベクトル検出装置は，動画像符号化の対象である動画像から選択した第１の画像中の所定の大きさの画素ブロックを分割して得られるテンプレート群に含まれる一つのテンプレートと，前記動画像符号化の対象である動画像から選択した第２の画像中における探索領域内から切り出した画素ブロック群に含まれる前記一つのテンプレートと同じ大きさの画素ブロックとの間で，対応する位置にある画素間の値の違いを評価し，評価値が最小となる画素ブロックの位置を動きベクトルとして検出することを，前記テンプレート群に含まれる全てのテンプレートについて行う動きベクトル検出装置において，前記テンプレート群に含まれる複数の最小のテンプレートの各々に対応した評価値計算回路と，前記評価値計算回路の出力を加算して，前記最小のテンプレートより大きな全てのテンプレートの評価値を計算する所定の数の加算回路とを含むことを特徴とする。
【００２１】
さらに，本発明における動きベクトル検出装置は，前記評価値計算回路において，水平方向について，水平方向がａ画素，垂直方向がｂラインであるテンプレートの画素数と同じａ個の画素ブロックの評価を行うことを繰り返すことにより，探索範囲に含まれる水平方向がａ画素，垂直方向がｂラインである全ての画素ブロックの評価を行うか，または前記評価値計算回路において，垂直方向について，水平方向がａ画素，垂直方向がｂラインであるテンプレートのライン数と同じｂ個の画素ブロックの評価を行うことを繰り返すことにより，探索範囲に含まれる水平方向がａ画素，垂直方向がｂラインである全ての画素ブロックの評価を行うことを特徴とする。
【００２２】
図１は，本発明の構成例を説明するためのブロック図である。図１において，参照画像メモリ１００は，動画像符号化の際に参照される画像データが格納されているメモリである。探索領域読み出し回路１０１は，参照画像メモリ１００に格納された動画像の探索領域内から画素ブロック群を読み出し，各評価値計算回路１０２に供給する回路である。
【００２３】
各評価値計算回路１０２は，複数の大きさのテンプレート群に含まれる最小のテンプレートの大きさに対応する動画像符号化の対象の画素ブロックと，探索領域読み出し回路１０１から供給される探索領域内から切り出した画素ブロック群に含まれる最小のテンプレートと同じ大きさの画素ブロックとの間で，対応する位置にある画素間の値の違いを評価する回路である。
【００２４】
例えば水平方向がａ画素，垂直方向がｂラインであるテンプレートから，水平方向が（ｍ×ａ）画素，垂直方向が（ｎ×ｂ）ラインの大きさのテンプレートまでの複数種類の大きさのテンプレートによる動きベクトルの検出を行う場合，それぞれの評価値計算回路１０２は，水平方向がａ画素，垂直方向がｂラインの大きさの動画像符号化の対象である画素ブロックと，参照画像中の探索領域内から切り出した同じ大きさの画素ブロックとの間で，対応する位置にある画素間の値の違いを評価する回路であり，ｍ×ｎ個（ｍ，ｎは整数で，ｍ×ｎ≧２）設けられる。
【００２５】
加算回路１０３は，評価値計算回路１０２の出力を加算して，最小のテンプレートより大きな全てのテンプレートの評価値を計算する回路である。
【００２６】
ｍ×ｎ個の個々の評価値計算回路１０２としては，従来例として説明した図１８，図２０，図２２，図２５または図２６の差分絶対値和計算回路と同様な構成の回路を用いることができる。
【００２７】
本発明は以上のように構成されるので，複数の大きさのテンプレートに対応した動きベクトルを検出できる動きベクトル検出装置を，最小のテンプレートの動きベクトルを検出する動きベクトル検出装置と同程度のハード量およびコストで実現することができる。
【００２８】
【発明の実施の形態】
本実施形態では，テンプレートの大きさが４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ラインの４種類の場合について説明する。
【００２９】
図２は，隣接した４画素×４ラインのテンプレート４個と探索領域の対応を示す。８画素×８ラインのテンプレートは，４画素×４ラインのテンプレート１０，１１，１２および１３の４個に分割される。図２中の左上，右上，左下，右下のテンプレート１０，１１，１２，１３の探索領域は，それぞれ２０，２１，２２，２３である。
【００３０】
ここで，探索領域２０の左上の角から切り出された４画素×４ラインの領域とテンプレート１０中の画素間の差分絶対値和をＳ0,0 （４×４左上），右横に１画素ずれた領域とテンプレート１０中の画素間の差分絶対値和をＳ0,1 （４×４左上），以下順次Ｓ0,2 （４×４左上），Ｓ0,3 （４×４左上）とし，探索領域２０の左上の角の４画素×４ラインの領域から１ライン下にずれた領域とテンプレート１０中の画素間の差分絶対値和をＳ1,0 （４×４左上）とする。
【００３１】
同様に，探索領域２１，２２，２３の左上の角からそれぞれ切り出された４画素×４ラインの領域とテンプレート１１，１２，１３中の画素間の差分絶対値和を，それぞれＳ0,0 （４×４右上），Ｓ0,0 （４×４左下），Ｓ0,0 （４×４右下）とする。このとき，Ｓ0,4 （４×４左上）とＳ0,0 （４×４右上）を計算するための探索領域中の画素は一致する。同様に，Ｓ4,0 （４×４左上）とＳ0,0 （４×４左下）を計算するための探索領域中の画素も一致する。また，Ｓ4,4 （４×４左上），Ｓ0,4 （４×４左下），Ｓ4,0 （４×４右上）およびＳ0,0 （４×４右下）を計算するための探索領域中の画素は一致する。
【００３２】
図３は，テンプレートの大きさが８画素×４ラインのときのテンプレートと探索領域の対応を示す。８画素×８ラインのテンプレートは，８画素×４ラインのテンプレート１４と１５の２個に分割される。上，下のテンプレート１４と１５の探索領域はそれぞれ２４と２５である。探索領域２４の左上の角から切り出された８画素×４ラインの領域とテンプレート１４中の画素間の差分絶対値和をＳ0,0 （８×４上），右横に１画素ずれた領域とテンプレート１４中の画素間の差分絶対値和をＳ0,1 （８×４上），以下順次Ｓ0,2 （８×４上），Ｓ0,3 （８×４上）とし，探索領域２４の左上の角の８画素×４ラインの領域から１ライン下にずれた領域とテンプレート１４中の画素間の差分絶対値和をＳ1,0 （８×４上）とする。同様に，探索領域２５の左上の角から切り出された８画素×４ラインの領域とテンプレート１５中の画素間の差分絶対値和をＳ0,0 （８×４下）とする。
【００３３】
図２と図３とを比較すると分かるように，Ｓ0,0 （８×４上）は，上記Ｓ0,0 （４×４左上）およびＳ0,0 （４×４右上）との間に以下の関係がある。
【００３４】
Ｓ0,0 （８×４上）＝Ｓ0,0 （４×４左上）＋Ｓ0,0 （４×４右上）
同様に，Ｓ0,0 （８×４下）は，上記Ｓ0,0 （４×４左下）およびＳ0,0 （４×４右下）との間に以下の関係がある。
【００３５】
Ｓ0,0 （８×４下）＝Ｓ0,0 （４×４左下）＋Ｓ0,0 （４×４右下）
一般化すると，次式の関係がある。
【００３６】
Ｓi,j （８×４上）＝Ｓi,j （４×４左上）＋Ｓi,j （４×４右上）……（１）
Ｓi,j （８×４下）＝Ｓi,j （４×４左下）＋Ｓi,j （４×４右下）……（２）
図４は，テンプレートの大きさが４画素×８ラインのときのテンプレートと探索領域の対応を示す。８画素×８ラインの画素ブロックは，４画素×８ラインのテンプレート１６と１７の２個に分割される。左と右のテンプレート１６と１７の探索領域は，それぞれ２６と２７である。探索領域２６の左上の角から切り出された４画素×８ラインの領域とテンプレート１６中の画素間の差分絶対値和をＳ0,0 （４×８左），右横に１画素ずれた領域とテンプレート１６中の画素間の差分絶対値和をＳ0,1 （４×８左），以下順次Ｓ0,2 （４×８左），Ｓ0,3 （４×８左）とし，探索領域２６の左上の角の４画素×８ラインの領域から１ライン下にずれた領域とテンプレート１６中の画素間の差分絶対値和をＳ1,0 （４×８左）とする。同様に，探索領域２７の左上の角から切り出された４画素×８ラインの領域とテンプレート１７中の画素間の差分絶対値和をＳ0,0 （４×８右）とする。
【００３７】
図２と図４とを比較すると分かるように，Ｓ0,0 （４×８左）は，上記Ｓ0,0 （４×４左上）およびＳ0,0 （４×４左下）との間に以下の関係がある。
【００３８】
Ｓ0,0 （４×８左）＝Ｓ0,0 （４×４左上）＋Ｓ0,0 （４×４左下）
同様に，Ｓ0,0 （４×８右）は，上記Ｓ0,0 （４×４右上）およびＳ0,0 （４×４右下）との間に以下の関係がある。
【００３９】
Ｓ0,0 （４×８右）＝Ｓ0,0 （４×４右上）＋Ｓ0,0 （４×４右下）
一般化すると，次式の関係がある。
【００４０】
Ｓi,j （４×８左）＝Ｓi,j （４×４左上）＋Ｓi,j （４×４左下）……（３）
Ｓi,j （４×８右）＝Ｓi,j （４×４右上）＋Ｓi,j （４×４右下）……（４）
図５は，テンプレートの大きさが８画素×８ラインのときのテンプレート１８と探索領域２８の対応を示す。探索領域２８の左上の角から切り出された８画素×８ラインの領域とテンプレート１８中の画素間の差分絶対値和をＳ0,0 （８×８），右横に１画素ずれた領域とテンプレート１８中の画素間の差分絶対値和をＳ0,1 （８×８），以下順次Ｓ0,2 （８×８），Ｓ0,3 （８×８）とし，探索領域２８の左上の角の８画素×８ラインの領域から１ライン下にずれた領域とテンプレート１８中の画素間の差分絶対値和をＳ1,0 （８×８）とする。
【００４１】
図２〜図５を比較すると分かるように，Ｓ0,0 （８×８）は，上記Ｓ0,0 （４×４左上），Ｓ0,0 （４×４右上），Ｓ0,0 （４×４左下），Ｓ0,0 （４×４右下），Ｓ0,0 （８×４上），Ｓ0,0 （８×４下），Ｓ0,0 （４×８左）およびＳ0,0 （４×８右）との間に以下の関係がある。
【００４２】
Ｓ0,0 （８×８）＝Ｓ0,0 （４×４左上）＋Ｓ0,0 （４×４右上）＋Ｓ0,0 （４×４左下）＋Ｓ0。0 （４×４右下）
＝Ｓ0,0 （８×４上）＋Ｓ0,0 （８×４下）
＝Ｓ0,0 （４×８左）＋Ｓ0,0 （４×８右）
一般化すると，次式の関係がある。
【００４３】
Ｓi,j （８×８）＝Ｓi,j （４×４左上）＋Ｓi,j （４×４右上）
＋Ｓi,j （４×４左下）＋Ｓi,j （４×４右下）
＝Ｓi,j （８×４上）＋Ｓi,j （８×４下）
＝Ｓi,j （４×８左）＋Ｓi,j （４×８右）……（５）
上記（１）式〜（５）式より，４画素×４ラインのテンプレート１０〜１３についての差分絶対値和を計算し，それらを加算することにより，８画素×４ライン，４画素×８ラインおよび８画素×８ラインのテンプレート１４，１５，１６，１７および１８についての差分絶対値和を算出できることが分かる。本発明では，４画素×４ラインの４個のテンプレート１０〜１３に，ＰＥアレイを個別に割り当てて差分絶対値和を計算し，その結果から他の大きさのテンプレートの差分絶対値和を算出する。
【００４４】
図６は，本発明の第１の実施形態の動きベクトル検出装置における差分絶対値和計算回路の構成を示す。図７は，図６に示す差分絶対値和計算回路へ入力する画素のタイミングを表した図である。ＰＥアレイi,j ８の構成を図８に示す。
【００４５】
第１の実施形態のＰＥアレイi,j ８は，第５の従来例におけるＰＥアレイ８と同一構造であり，第５の従来例と同様に水平方向の動きベクトルを−３〜０と１〜４の２回に分けて探索する。この点は後述する第２および第３の実施形態も同様であるが，第１の実施形態では，ＰＥアレイ0,0 ，ＰＥアレイ1,0 ，ＰＥアレイ0,1 ，ＰＥアレイ1,1 に対し，図７に示すように，探索領域中の画素を別々に供給する点が第２および第３の実施形態と異なる。
【００４６】
この構成により，４個のＰＥアレイi,j ８を並列に動作させ，ＰＥアレイ0,0 でＳi,j （４×４左上），ＰＥアレイ1,0 でＳi,j （４×４左下），ＰＥアレイ0,1 でＳi,j （４×４右上），ＰＥアレイ1,1 でＳi,j （４×４右下）を同時に計算し，これらを加算器５で加算することにより，Ｓi,j （８×４上），Ｓi,j （８×４下），Ｓi,j （４×８左），Ｓi,j （４×８右），Ｓi,j （８×８）を計算する。
【００４７】
図９は，本発明の第２の実施形態の動きベクトル検出装置における差分絶対値和計算回路の構成を示す。図１０は，図９に示す差分絶対値和計算回路へ入力する画素のタイミングを表した図である。遅延回路Ａ３０は，入力した画素を１６ＣＫ遅延させて出力する回路である。
【００４８】
図２で説明したように，左上のテンプレート１０の探索領域２０を下方に４ラインずらすと左下のテンプレート１２の探索領域２２となるため，Ｓ4,0 （４×４左上）を計算するための探索領域中の画素とＳ0,0 （４×４左下）を計算するための探索領域中の画素は一致する。一般化すると，Ｓi,j （４×４左上）を計算するための探索領域中の画素とＳi-4,j （４×４左下）を計算するための探索領域中の画素は一致する。
【００４９】
本実施形態では，この点に着目し，ＰＥアレイ0,0 とＰＥアレイ1,0 に同一の探索領域中の画素を入力して，Ｓi,j （４×４左上）とＳi-4,j （４×４左下）を同時に計算する。ただし，ｉは０以上１１以下の整数であり，ｉ＜４のとき，Ｓi-4,j （４×４左下）は計算されず，また，ｉ＞７のとき，Ｓi,j （４×４左上）は計算されないものとする。なお，ｊは０以上７以下の整数である。
【００５０】
本実施形態において，Ｓi,j （４×４左下）は，Ｓi,j （４×４左上）がＰＥアレイ0,0 から出力された後，１６ＣＫ遅れてＰＥアレイ1,0 から出力される。このため，遅延回路Ａ３０によりＳi,j （４×４左上）を１６ＣＫ遅延させて，加算器５によりＳi,j （４×４左下）と加算することにより，Ｓi,j （４×８左）を算出できる。
【００５１】
同様に，ＰＥアレイ0,1 とＰＥアレイ1,1 にも同一の探索領域中の画素を入力して，Ｓi,j （４×４右上）とＳi-4,j （４×４右下）を同時に計算する。ただし，ｉは０以上１１以下の整数であり，ｉ＜４のとき，Ｓi-4,j （４×４右下）は計算されず，また，ｉ＞７のとき，Ｓi,j （４×４右上）は計算されないものとする。なお，ｊは０以上７以下の整数である。本実施形態においては，Ｓi,j （４×４右上）がＰＥアレイ0,1 から出力された後，１６ＣＫ遅れてＳi,j （４×４右下）がＰＥアレイ1,1 から出力される。このため，遅延回路Ａ３０によりＳi,j （４×４右上）を１６ＣＫ遅延させて，Ｓi,j （４×４右下）と加算することにより，Ｓi,j （４×８右）を算出できる。
【００５２】
図１１は，本発明の第３の実施形態の動きベクトル検出装置における差分絶対値和計算回路の構成を示す。図１２は，図１１に示す差分絶対値和計算回路へ入力する画素のタイミングを表した図である。遅延回路Ａ３０，遅延回路Ｂ３１および遅延回路Ｃ３２は，それぞれ入力した画素を１６ＣＫ，４８ＣＫおよび６４ＣＫ遅延させて出力する回路である。
【００５３】
図２で説明したように，Ｓ4,4 （４×４左上），Ｓ0,4 （４×４左下），Ｓ4,0 （４×４右上）およびＳ0,0 （４×４右下）を計算するための探索領域中の画素は一致する。すなわち，Ｓi,j （４×４左上），Ｓi-4,j （４×４左下），Ｓi,j-4 （４×４右上）およびＳi-4,j-4 （４×４右下）を計算するための探索領域中の画素は一致する。ただし，ｉは０以上１１以下の整数であり，ｉ＜４のとき，Ｓi-4,j （４×４左下）とＳi-4,j-4 （４×４右下）は計算されず，ｉ＞７のとき，Ｓi,j （４×４左上）とＳi,j-4 （４×４右上）は計算されないものとする。同様に，ｊは０以上１１以下の整数であり，ｊ＜４のとき，Ｓi,j-4 （４×４右上）とＳi-4,j-4 （４×４右下）は計算されず，ｊ＞７のとき，Ｓi,j （４×４左上）とＳi-4,j （４×４左下）は計算されないものとする。
【００５４】
図１３は，各テンプレート１０〜１３の１回目と２回目の探索範囲を示す図である。図中の５０はテンプレート１０の１回目の探索範囲，５１はテンプレート１０の２回目の探索範囲とテンプレート１１の１回目の探索範囲，５２はテンプレート１１の２回目の探索範囲，５３はテンプレート１２の１回目の探索範囲，５４はテンプレート１２の２回目の探索範囲とテンプレート１３の１回目の探索範囲，５５はテンプレート１３の２回目の探索範囲を表している。
【００５５】
本実施形態では，最初にＰＥアレイ0,0 とＰＥアレイ1,0 のみ動作させてテンプレート１０の１回目の探索範囲とテンプレート１２の１回目の探索範囲を探索し，次にＰＥアレイ0,0 ，ＰＥアレイ1,0 ，ＰＥアレイ0,1 およびＰＥアレイ1,1 を全て動作させてテンプレート１０の２回目の探索範囲とテンプレート１１の１回目の探索範囲，およびテンプレート１２の２回目の探索範囲とテンプレート１３の１回目の探索範囲を探索し，最後にＰＥアレイ0,1 とＰＥアレイ1,1 のみ動作させてテンプレート１１の２回目の探索範囲とテンプレート１３の２回目の探索範囲を探索する。
【００５６】
この構成により，ＰＥアレイ0,0 ，ＰＥアレイ1,0 ，ＰＥアレイ0,1 およびＰＥアレイ1,1 に同一の画素を入力して，Ｓi,j （４×４左上），Ｓi-4,j （４×４左下），Ｓi,j-4 （４×４右上）およびＳi-4,j-4 （４×４右下）を同時に計算することができる。
【００５７】
ただし，Ｓi,j （４×４左下）は，Ｓi,j （４×４左上）がＰＥアレイ0,0 から出力された後，１６ＣＫ遅れてＰＥアレイ1,0 から出力される。また，第１〜第３の従来例の動きベクトル検出装置同様，探索領域から切り出された４画素×４ラインの領域が探索領域の下端から上端に移るとき１５ＣＫの無効サイクルが生じるため，Ｓi,j （４×４右上）とＳi,j （４×４右下）は，Ｓi,j （４×４左上）がＰＥアレイ0,0 から出力された後，それぞれ４８ＣＫと６４ＣＫ遅れでＰＥアレイ0,1 とＰＥアレイ1,1 から出力される。
【００５８】
そこで，本実施形態においては，遅延回路Ｃ３２によりＳi,j （４×４左上）を６４ＣＫ遅延させ，遅延回路Ｂ３１によりＳi,j （４×４左下）を４８ＣＫ遅延させ，遅延回路Ａ３０によりＳi,j （４×４右上）を１６ＣＫ遅延させた後，Ｓi,j （４×４左上），Ｓi,j （４×４左下），Ｓi,j （４×４右上）およびＳi,j （４×４右下）を加算することにより，Ｓi,j （８×４上），Ｓi,j （８×４下），Ｓi,j （４×８左），Ｓi,j （４×８右），Ｓi,j （８×８）を算出する。
【００５９】
上記第３の実施形態では，探索領域から切り出された４画素×４ラインの領域が探索領域の下端から上端に移るときの無効サイクルを無視すると，水平方向の探索範囲が−３〜＋４の場合，ＰＥアレイ0,0 ，ＰＥアレイ1,0 ，ＰＥアレイ0,1 およびＰＥアレイ1,1 が全て動作するのは全体のＣＫ数の１／３である。しかし，探索範囲が広くなれば，ＰＥアレイ0,0 ，ＰＥアレイ1,0 ，ＰＥアレイ0,1 およびＰＥアレイ1,1 が全て動作する割合は増加する。例えば，水平方向の探索範囲が−７〜＋８の場合，全体のＣＫ数の３／５，水平方向の探索範囲が−１１〜＋１２の場合，全体のＣＫ数の５／７だけ，ＰＥアレイ0,0 ，ＰＥアレイ1,0 ，ＰＥアレイ0,1 およびＰＥアレイ1,1 が全て動作する。
【００６０】
なお，上記第１〜第３の実施形態においては，テンプレートの大きさが４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ラインの４種類の場合についてのみ示したが，本発明は，いろいろな大きさのテンプレートの組み合わせに対して適用できる。例えば，本発明は，４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ライン，８画素×１６ライン，１６画素×８ラインおよび１６画素×１６ラインの大きさのテンプレートの組み合わせに対しても適用できる。
【００６１】
図１４は，これらのテンプレートの組み合わせに適用した場合における本発明の第２の実施形態の差分絶対値和計算回路の構成を示す図である。ここで，遅延回路Ａ３０，遅延回路Ｄ３３および遅延回路Ｂ３１は，それぞれ入力した画素を１６ＣＫ，３２ＣＫおよび４８ＣＫ遅延させて出力する回路である。ただし，図１４では，最小のテンプレートの評価値であるＰＥアレイi,j の出力を加算して，より大きなテンプレートの評価値を算出するための加算器は，図示を省略している。
【００６２】
また，図１５は，４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ライン，８画素×１６ライン，１６画素×８ラインおよび１６画素×１６ラインの大きさのテンプレートの組み合わせに適用した場合における本発明の第３の実施形態の差分絶対値和計算回路の構成を示す図である。ここで，遅延回路Ａ３０，遅延回路Ｄ３３および遅延回路Ｂ３１は，それぞれ入力した画素を１６ＣＫ，３２ＣＫおよび４８ＣＫ遅延させて出力する回路であり，遅延回路Ｅ３４，遅延回路Ｆ３５，遅延回路Ｇ３６および遅延回路Ｈ３７は，それぞれ入力した画素を８０ＣＫ，９６ＣＫ，１１２ＣＫおよび１２８ＣＫ遅延させて出力する回路である。同様に，遅延回路Ｉ３８〜遅延回路Ｐ４５は，入力した画素を１６０ＣＫ〜２８８ＣＫ遅延させて出力する回路である。ただし，図１５でも，最小のテンプレートの評価値であるＰＥアレイi,j の出力を加算して，より大きなテンプレートの評価値を算出するための加算器は，図示を省略している。
【００６３】
また，上記第１〜第３の実施形態においては，水平方向について最小のテンプレートの画素数と同じ個数の動きベクトルの評価を行うことを繰り返すことにより探索範囲内の全動きベクトルを検出する構成のみを示したが，垂直方向について最小のテンプレートのライン数と同じ個数の動きベクトルの評価を行うことを繰り返すことにより探索範囲内の全動きベクトルを検出する構成とすることもできる。
【００６４】
さらに，第２および第３の実施形態で用いた遅延回路Ａ〜Ｐはレジスタを直列に接続することにより実現しても良いし，ファースト・イン・ファースト・アウト・メモリによって実現しても良く，入力画素を所定のＣＫだけ遅延して出力するものであれば，実現手段は問わない。
【００６５】
【発明の効果】
以上説明したように，本発明によれば，複数の大きさのテンプレートに対応した動きベクトルを検出できる動きベクトル検出装置を，最小のテンプレートの動きベクトルを検出する動きベクトル検出装置と同程度のハード量およびコストで実現することができる効果がある。
【図面の簡単な説明】
【図１】本発明の構成例を説明するためのブロック図である。
【図２】隣接した４画素×４ラインのテンプレート４個と探索領域の対応を示す図である。
【図３】テンプレートの大きさが８画素×４ラインのときのテンプレートと探索領域の対応を示す図である。
【図４】テンプレートの大きさが４画素×８ラインのときのテンプレートと探索領域の対応を示す図である。
【図５】テンプレートの大きさが８画素×８ラインのときのテンプレートと探索領域の対応を示す図である。
【図６】第１の実施形態の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図７】第１の実施形態の差分絶対値和計算回路へ入力する画素のタイミングを表した図である。
【図８】第１の実施形態の差分絶対値和計算回路の中のＰＥアレイi,j の構成を示す図である。
【図９】第２の実施形態の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図１０】第２の実施形態の差分絶対値和計算回路へ入力する画素のタイミングを表した図である。
【図１１】第３の実施形態の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図１２】第３の実施形態の差分絶対値和計算回路へ入力する画素のタイミングを表した図である。
【図１３】第３の実施形態における各テンプレートの１回目と２回目の探索範囲を示す図である。
【図１４】４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ライン，８画素×１６ライン，１６画素×８ラインおよび１６画素×１６ラインの大きさのテンプレートの組み合わせに適用した場合における本発明の第２の実施形態の差分絶対値和計算回路の構成を示す図である。
【図１５】４画素×４ライン，４画素×８ライン，８画素×４ライン，８画素×８ライン，８画素×１６ライン，１６画素×８ラインおよび１６画素×１６ラインの大きさのテンプレートの組み合わせに適用した場合における本発明の第３の実施形態の差分絶対値和計算回路の構成を示す図である。
【図１６】動き検出の対象となるテンプレートと探索領域の例を示す図である。
【図１７】全探索法による動き検出の方法を説明するための図である。
【図１８】第１の従来例の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図１９】第１の従来例の差分絶対値和計算回路において，探索領域の左上の角から切り出された４画素×４ラインの領域とテンプレート中の画素間で差分絶対値和を計算するときのタイミングを表した図である。
【図２０】第２の従来例の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図２１】第２の従来例の差分絶対値和計算回路において，探索領域の左上の角から切り出された４画素×４ラインの領域とテンプレート中の画素間で差分絶対値和を計算するときのタイミングを表した図である。
【図２２】第３の従来例の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図２３】第３の従来例の差分絶対値和計算回路において，探索領域の左上の角から切り出された４画素×４ラインの領域とテンプレート中の画素間で差分絶対値和を計算するときのタイミングを説明するための図である。
【図２４】無効サイクルが生じる場合の探索領域からの画素読み出し例を示す図である。
【図２５】第４の従来例の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図２６】第５の従来例の動きベクトル検出装置における差分絶対値和計算回路の構成を示す図である。
【図２７】第５の従来例における探索領域からの画素読み出し例を示す図である。
【図２８】第５の従来例において図１６に示した探索領域中の動きベクトルを検出する場合の例を示す図である。
【符号の説明】
１，１０，１１，…，１８  テンプレート
２，２０，２１，…，２８  探索領域
３  差分絶対値を計算する回路
４  レジスタ
５  加算器
６  総和回路
７  セレクタ
８  ＰＥアレイ
３０，３１，…，４５  遅延回路
１００  参照画像メモリ
１０１  探索領域読み出し回路
１０２  評価値計算回路
１０３  加算回路
【図１】
2004200984.tif 000003
【図２】
2004200984.tif 000004
【図３】
2004200984.tif 000005
【図４】
2004200984.tif 000006
【図５】
2004200984.tif 000007
【図６】
2004200984.tif 000008
【図７】
2004200984.tif 000009
【図８】
2004200984.tif 000010
【図９】
2004200984.tif 000011
【図１０】
2004200984.tif 000012
【図１１】
2004200984.tif 000013
【図１２】
2004200984.tif 000014
【図１３】
2004200984.tif 000015
【図１４】
2004200984.tif 000016
【図１５】
2004200984.tif 000017
【図１６】
2004200984.tif 000018
【図１７】
2004200984.tif 000019
【図１８】
2004200984.tif 000020
【図１９】
2004200984.tif 000021
【図２０】
2004200984.tif 000022
【図２１】
2004200984.tif 000023
【図２２】
2004200984.tif 000024
【図２３】
2004200984.tif 000025
【図２４】
2004200984.tif 000026
【図２５】
2004200984.tif 000027
【図２６】
2004200984.tif 000028
【図２７】
2004200984.tif 000029
【図２８】
2004200984.tif 000030