(57)【特許請求の範囲】
【請求項１】
探索対象ブロックを探索範囲より順次選択するための探索対象ブロック選択手段と、
前記探索対象ブロックのサンプル値を保持し、隣接するレジスタの値を受ける複数のレジスタと、
前記複数のレジスタに接続され、リファレンスブロックと前記探索対象ブロックとの間の対応するサンプル間で順次差分をとり、差分値の絶対値を累積し、累積値と所定のしきい値とを比較し、前記累積値が前記所定のしきい値よりも大きくなった場合に動作を中断するための複数の演算手段と、
前記複数の演算手段に接続され、前記演算手段の演算結果が前記所定のしきい値よりも小さい場合に前記演算結果および前記演算結果に対応する前記探索対象ブロックを記憶するための手段と、
前記複数の演算手段の各々に前記所定のしきい値を与え、前記複数の演算手段のすべてが、前記累積値が所定のしきい値よりも大きくなることにより中断した場合には、前記所定のしきい値を一定値増加させ、再度、前記複数の演算手段に与えるためのしきい値管理手段とを含み、
前記所定のしきい値は、前記リファレンスブロックと同位置における１フレーム前のリファレンスブロックに対して求められた累積値の最終結果のうちの最小値である、動き検出装置。
【請求項２】
探索対象ブロックを探索範囲より順次選択するための探索対象ブロック選択手段と、
前記探索対象ブロックのサンプル値を保持し、隣接するレジスタの値を受ける複数のレジスタと、
前記複数のレジスタに接続され、リファレンスブロックと前記探索対象ブロックとの間の対応するサンプル間で順次差分をとり、差分値の絶対値を累積し、累積値と所定のしきい値とを比較し、前記累積値が前記所定のしきい値よりも大きくなった場合に動作を中断するための複数の演算手段と、
前記複数の演算手段に接続され、前記演算手段の演算結果が前記所定のしきい値よりも小さい場合に前記演算結果および前記演算結果に対応する前記探索対象ブロックを記憶するための手段と、
前記複数の演算手段の各々に前記所定のしきい値を与え、前記複数の演算手段のすべてが、前記累積値が所定のしきい値よりも大きくなることにより中断した場合には、前記所定のしきい値を一定値増加させ、再度、前記複数の演算手段に与えるためのしきい値管理手段とを含み、
前記所定のしきい値は、前記リファレンスブロックと隣接する同一フレーム内のリファレンスブロックに対して求められた累積値の最終結果のうちの最小値である、動き検出装置。
【請求項３】
前記複数の演算手段にそれぞれ接続され、前記リファレンスブロックのサンプルデータを保持する複数のリファレンス値レジスタをさらに含む、請求項１または２に記載の動き検出装置。
【請求項４】
前記複数の演算手段に前記リファレンスブロックのサンプル値を供給するバスと、
前記バスと前記複数の演算手段にそれぞれ接続され、前記しきい値を保持する複数のしきい値レジスタとをさらに含み、
前記バスで、第１の期間に前記しきい値を転送し、第２の期間に前記リファレンスブロックのサンプル値を転送する、請求項１〜３のいずれか１項に記載の動き検出装置。
【請求項５】
前記しきい値管理手段は、
前記複数の演算手段より出力される比較結果を受けるマンチェスタ型キャリー伝播回路と、
前記複数の演算手段の各々に前記所定のしきい値を与え、前記マンチェスタ型キャリー伝播回路の出力に従い、前記所定のしきい値を一定値増加させ、再度、前記複数の演算手段に与えるための手段とを含む、請求項１〜４のいずれか１項に記載の動き検出装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、デジタル動画像圧縮システムで用いられる動き検出方法および装置に関し、特に、少ない演算量で動き検出を行なうことができる動き検出方法および装置に関する。
【０００２】
【従来の技術】
動き検出装置は、ＭＰＥＧ（Moving Picture Experts Group）方式の動画像圧縮システムで用いられ、非常に多くの演算を行なう装置である。これまで、動き検出装置の演算アルゴリズムについて様々な方法が提案されている。ＭＰＥＧ方式による動画像圧縮システムについては、「P.Pirsch et al., "VLSI Architecture for Video Compression -A Survey", Proc. IEEE Vol.83, No.2, pp.220-246, 1995 」、「M.Yoshimoto et al., “ULSI Realization of MPEG2 Realtime Video Encoder and Decoder -An Overview", IEICE Trans. Electron., Vol.E78-C, No.12, pp.1668-1681, 1995」、および「田中他，“MPEG2 符号化LSI が家庭を変える" ，日経エレクトロニクス1998.3.9号(No.711)」などに詳しく開示されている。
【０００３】
また、動き検出演算用ＬＳＩ（Large Scale Integration ）に関しては、「K.Ishihara et al.,“A-Half-Pel Precision MPEG2 Motion Estimation Processor with Concurrent Three-Vector Search", ISSCC Digest of Technical Papers, pp.288-289, 1995 」、「A.Ohtani et al.,“A Motion Estimation Processor for MPEG2 Video Real Time Encoding at Wide Search Range", Proc. IEEE Custom Integrated Circuits Conference, pp.405-408, 1995」、および「Hanami et al.,“A 165-GOPS Motion Estimation Processor with Adaptive Dual-Array Architecture for High Quality Video-Encoding Applications", Proc. IEEE Custom Integrated Circuits Conference, pp.169-172,1998 」などに詳しく開示されている。
【０００４】
従来、動き検出方法として全サンプル全探索方式が知られている。この方式は、探索範囲内のすべての候補ベクトルについて、探索対象ブロックとリファレンスブロックとの差分演算をブロック内のすべての座標位置において行なう方法である。この方式によると、最小差分値を持った座標位置のベクトルを正確に検出することができる。
【０００５】
しかし、全サンプル全探索方式では演算量が非常に多く、１つのＬＳＩで実現可能なベクトルの探索範囲が狭くなる。このため、この方式を用いて広い範囲を探索するためには、多くのＬＳＩが必要になるという問題点がある。差分演算の演算量を削減するために、各探索位置で一部の座標位置についてのみ差分演算を行なうサブサンプル方式や、特定のアルゴリズムに従い、探索範囲中の探索位置を選び、一部の探索位置についてのみ探索対象ブロックとリファレンスブロックとの差分演算を行なうアルゴリズミック探索方式が提案されている。また、両方式を組み合わせて、より広い探索範囲をより少ない演算量で探索することができる様々な方式が提案されている。サブサンプル方式とアルゴリズミック探索方式とを組み合わせた方式を用いて動き検出を行なう動き検出回路を備えた動画像圧縮装置は、「M.Mizuno et al.,“A 1.5W Single-Chip MPEG2 MP ‘ML Encoder with Low-Power Motion Estimation and Clocking", ISSCC Digest of Technical Papers, pp.256-257, 1997 」などに詳しく開示されている。
【０００６】
一方、上述のような静的アルゴリズムではなく、入力となる原画像に依存して動的に探索範囲を変化させることができる方式として中断法が提案されている。中断法では、あらかじめ差分値の目標値を設定しておき、その目標値より小さな差分値を持つベクトルを検出し、かつそのベクトルに引き続く探索において差分値の減少がなくなる時のベクトルを探索結果とする。中断法に関しては、「笹島、榎本，“中断法動きベクトル検出と閾値の適応的設定"，電子情報通信学会総合大会，PP.46, 1998」などに詳しく開示されている。
【０００７】
【発明が解決しようとする課題】
これまでに提案されたサブサンプル方式およびアルゴリズミック探索方式は、いずれも入力となる原画像データに依存せずに静的に定められたアルゴリズムに従って、ベクトルの探索が行われる。このため、ある特定の原画像データに対しては全サンプル全検索方式と同じまたはほぼ同等の差分値を持ったベクトルを検出することができる。しかし、別の特定の原画像データに対しては、全サンプル全検索方式に比べてかなり大きな差分値を持ったベクトルが検出され、結果として動画像の圧縮率が低下したり、圧縮された動画像を伸張した際の画質が悪くなるなどの欠点がある。
【０００８】
また、中断法では、全サンプル全検索方式に比べ、演算量が約４０％にしか削減されないにもかかわらず、全探索方式に比べて平均的にかなり大きな差分値を持つベクトルを検出するという欠点がある。
【０００９】
また、従来の動き検出装置はＬＳＩの特徴を生かし、規則的に配列された回路を、できるだけ稼働率高く、しかも並列にに動作させるように設計されていることが多い。このため、最終的には必要でない動きベクトルに対する差分値を計算するなど、消費電力を削減することより演算回路の稼働率を高めることに主眼がおかれており、演算性能は高いものの消費電力が大きいという欠点がある。
【００１０】
特開平１０−１９１３５２号公報には、所定のしきい値との比較結果に応じて途中で演算を中止させることができる動き検出装置が開示されている。これにより処理の高速化を図っている。しかし、この装置では、初回の演算サイクルにおいては、しきい値を求めるため途中で演算を中止させることはできない。このため、１度に処理可能な候補ベクトルの数を多くしすぎると、演算を中止させることによる効果が現れてこない。また、この装置では、あらかじめ所定のしきい値を与えることも可能ではあるが、そのしきい値の性質についての開示がなされていない。このため、最適なしきい値を設定することが困難である。
【００１１】
本発明は、上述の課題を解決するためになされたもので、その目的は、最適なしきい値を設定でき、高速処理可能な動き検出方法を提供することである。
【００１２】
他の目的は、最適なしきい値を設定でき、高速処理可能で、かつ消費電力が低い動き検出装置を提供することである。
【００１３】
さらに他の目的は、最適なしきい値を設定でき、高速処理可能で、消費電力が低く、かつ内部構成が簡略化された動き検出装置を提供することである。
【００１４】
【課題を解決するための手段】
請求項１に記載の発明に係る動き検出方法は、探索対象ブロックを探索範囲より順次選択するステップと、リファレンスブロックと探索対象ブロックとの間の対応するサンプル間で順次差分をとり、差分値の絶対値を累積するステップと、所定サンプル数ごとに、累積値の途中結果と所定のしきい値とを比較し、途中結果が所定のしきい値より大きくなった時点で差分値の絶対値を累積するステップを中断させるステップと、累積値の最終結果が最小となる探索対象ブロックをリファレンスブロックに対応づけるステップとを含み、所定のしきい値は、リファレンスブロックに依存した値である。
【００１５】
請求項１に記載の発明によると、演算の途中結果がしきい値を超えた場合には、その探索対象ブロックに対する演算を中断させることができる。このため、次の探索対象ブロックに対する処理にすぐに移行することができる。また、所定のしきい値をリファレンスブロックに依存した値とすることにより、リファレンスブロックごとに最適なしきい値を設定することができる。このため、処理の高速化につながる。
【００１６】
請求項２に記載の発明は、請求項１に記載の発明の構成に加えて、探索対象ブロックを探索範囲より順次選択するステップは、探索対象ブロックをリファレンスブロックに近い位置に存在するものから順に選択するステップを含む。
【００１７】
請求項２に記載の発明は、請求項１に記載の発明の作用、効果に加えて、早い段階でリファレンスブロックに対応した探索対象ブロックを検出することができる。これに伴い、後続の処理における差分累積演算を早い段階で中断させることができる。これは、リファレンスブロックに対応する探索対象ブロックは一般にリファレンスブロックに近傍に位置するためである。このため、処理の高速化につながる。
【００１８】
請求項３に記載の発明は、請求項１に記載の発明の構成に加えて、差分値の絶対値を累積するステップは、複数の探索対象ブロックの各々について、リファレンスブロックと探索対象ブロックとの間の対応するサンプル間で順次差分をとり、差分値の絶対値を累積する複数のステップを含み、差分値の絶対値を累積するステップを中断させるステップは、差分値の絶対値を累積する複数のステップの各々について、所定サンプル数ごとに、累積値の途中結果と所定のしきい値とを各々比較し、途中結果が所定のしきい値より大きくなった時点で累積処理を中断させるステップと、差分値の絶対値を累積する複数のステップのすべてが、累積値の途中結果が所定のしきい値より大きくなることにより中断した場合には、所定のしきい値を一定値増加させ、再度、差分値の絶対値を累積する複数のステップを並列に実行させるステップとを含む。
【００１９】
請求項３に記載の発明は、請求項１に記載の発明の作用、効果に加えて、複数の探索対象ブロックに対する差分累積演算を並列に処理することができる。また、しきい値の初期値が小さすぎ、リファレンスブロックに対応する探索対象ブロックが検出されなかったとしても、しきい値を徐々に大きくすることにより、適当なしきい値を決定することができる。よって、早い段階で差分累積演算を中断させることができ、処理の高速化につながる。
【００２０】
請求項４に記載の発明に係る動き検出装置は、探索対象ブロックを探索範囲より順次選択するための探索対象ブロック選択手段と、リファレンスブロックと探索対象ブロックとの間の対応するサンプル間で順次差分をとり、差分値の絶対値を累積するための差分絶対値累積手段と、差分絶対値累積手段の出力に接続され、リファレンスブロックと探索ブロックとの間の対応するサンプル間の差分が所定回数行われるごとに、累積値の途中結果と所定のしきい値とを比較し、途中結果が所定のしきい値より大きくなった時点で差分絶対値累積手段の動作を中断させる累積動作中断手段と、累積値の最終結果が最小となる探索対象ブロックをリファレンスブロックに対応づける対応づけ手段とを含み、所定のしきい値は、リファレンスブロックに依存した値である。
【００２１】
請求項４に記載の発明によると、演算の途中結果がしきい値を超えた場合には、その探索対象ブロックに対する演算を中断させることができる。このため、次の探索対象ブロックに対する処理にすぐに移行することができる。また、所定のしきい値をリファレンスブロックに依存した値とすることにより、リファレンスブロックごとに最適なしきい値を設定することができる。このため、処理の高速化につながる。ひいては、低消費電力化を図ることができる。
【００２２】
請求項５に記載の発明は、請求項４に記載の発明の構成に加えて、累積値の最終結果と所定のしきい値とを比較し、最終結果が所定のしきい値よりも小さければ、所定のしきい値を最終結果で置き換える手段をさらに含む。
【００２３】
請求項６に記載の発明は、請求項４または５に記載の発明の構成に加えて、探索対象ブロック選択手段は、探索対象ブロックをリファレンスブロックに近い位置に存在するものから順に選択する手段を含む。
【００２４】
請求項６に記載の発明は、請求項４または５に記載の発明の作用、効果に加えて、早い段階でリファレンスブロックに対応した探索対象ブロックを検出することができる。これに伴い、後続の処理における差分累積演算を早い段階で中断させることができる。これは、リファレンスブロックに対応する探索対象ブロックは一般にリファレンスブロックの近傍に位置するためである。このため、処理の高速化につながる。ひいては低消費電力化を図ることができる。
【００２５】
請求項７に記載の発明は、請求項４に記載の発明の構成に加えて、所定のしきい値は、リファレンスブロックのイントラ評価値である。
【００２６】
請求項７に記載の発明は、請求項４に記載の発明の作用、効果に加えて、イントラ評価値を所定のしきい値にしているため、リファレンスブロック自体を符号化の対象とするか否かの判断が容易になる。すなわち、リファレンスブロックに対応する探索対象ブロックが検出されなかった場合には、リファレンスブロック自体を符号化の対象とすればよい。
【００２７】
請求項８に記載の発明に係る動き検出装置は、探索対象ブロックを探索範囲より順次選択するための探索対象ブロック選択手段と、探索対象ブロックを探索範囲より順次選択するための探索対象ブロック選択手段と、探索対象ブロックのサンプル値を保持し、隣接するレジスタの値を受ける複数のレジスタと、複数のレジスタに接続され、リファレンスブロックと探索対象ブロックとの間の対応するサンプル間で順次差分をとり、差分値の絶対値を累積し、累積値と所定のしきい値とを比較し、累積値が所定のしきい値よりも大きくなった場合に動作を中断するための複数の演算手段と、複数の演算手段に接続され、演算手段の演算結果が所定のしきい値よりも小さい場合に演算結果および演算結果に対応する探索対象ブロックを記憶するための手段と、複数の演算手段の各々に所定のしきい値を与え、複数の演算手段のすべてが、累積値が所定のしきい値よりも大きくなることにより中断した場合には、所定のしきい値を一定値増加させ、再度、複数の演算手段に与えるためのしきい値管理手段とを含み、所定のしきい値は、リファレンスブロックに依存した値である。
【００２８】
請求項８に記載の発明によると、複数の探索対象ブロックに対する差分累積演算を並列に処理することができる。また、しきい値の初期値が小さすぎ、リファレンスブロックに対応する探索対象ブロックが検出されなかったとしても、しきい値を徐々に大きくすることにより、適当なしきい値を決定することができる。よって、早い段階で差分累積演算を中断させることができ、処理の高速化につながる。ひいては低消費電力化を図ることができる。また、所定のしきい値をリファレンスブロックに依存した値とすることにより、リファレンスブロックごとに最適なしきい値を設定することができる。
【００２９】
請求項９に記載の発明は、請求項８に記載の発明の構成に加えて、所定のしきい値は、リファレンスブロックと同位置における１フレーム前のリファレンスブロックに対して求められた累積値の最終結果のうちの最小値である。
【００３０】
請求項９に記載の発明は、請求項８に記載の発明の作用、効果に加えて、リファレンスブロックと同位置における１フレーム前のリファレンスブロックに対して求められた累積値の最終結果のうちの最小値を所定のしきい値としている。１フレーム異なる画像であっても同一位置における画像の性質は類似している。このため、最適なしきい値を設定することができる。
【００３１】
請求項１０に記載の発明は、請求項８に記載の発明の構成に加えて、所定のしきい値は、リファレンスブロックと隣接する同一フレーム内のリファレンスブロックに対して求められた累積値の最終結果のうちの最小値である。
【００３２】
請求項１０に記載の発明は、請求項８に記載の発明の作用、効果に加えて、リファレンスブロックと隣接する同一フレーム内のリファレンスブロックに対して求められた累積値の最終結果のうちの最小値を所定のしきい値としている。現在着目しているリファレンスブロックに隣接するリファレンスブロックではその画像の性質も類似している。このため、最適なしきい値を設定することができる。
【００３３】
請求項１１に記載の発明は、請求項８に記載の発明の構成に加えて、シーンチェンジの有無を検知するための手段をさらに含み、所定のしきい値は、シーンチェンジの有無に従い定められる、現フレームのリファレンスブロックに依存した値および１フレーム前のリファレンスブロックに依存した値のいずれかである。
【００３４】
請求項１１に記載の発明は、請求項８に記載の発明の作用、効果に加えて、シーンチェンジがおきた場合にも最適なしきい値を設定できる効果がある。シーンチェンジがおきた場合には１フレーム前のリファレンスブロックに応じた値をしきい値として利用することはできない。これは、シーンチェンジが起こることにより、画像の性質が変化しているためである。このため、シーンチェンジが生じた場合には現在のフレームに応じた値をしきい値として利用することにより、最適なしきい値を設定することができる。
【００３５】
請求項１２に記載の発明は、請求項８に記載の発明の構成に加えて、複数の演算手段にそれぞれ接続され、リファレンスブロックのサンプルデータを保持する複数のリファレンス値レジスタをさらに含む。
【００３６】
請求項１２に記載の発明は、請求項８に記載の発明の作用、効果に加えて、複数の演算手段をグループ化し、グループごとに異なるリファレンスブロックを対応付けることにより、複数のリファレンスブロックに対する処理を並列に行なうことができる。このため処理速度を向上させることができ、ひいては消費電力を低減させることができる。
【００３７】
請求項１３に記載の発明は、請求項８に記載の発明の構成に加えて、複数の演算手段にリファレンスブロックのサンプル値を供給するバスと、バスと複数の演算手段にそれぞれ接続され、しきい値を保持する複数のしきい値レジスタとをさらに含み、バスで、第１の期間にしきい値を転送し、第２の期間にリファレンスブロックのサンプル値を転送する。
【００３８】
請求項１３に記載の発明は、請求項８に記載の発明の作用、効果に加えて、所定のしきい値を与えるためのバスと、リファレンスフレームのサンプル値を与えるためのバスとを共通化することにより装置の内部構成が簡略化される。
【００３９】
請求項１４に記載の発明は、請求項８に記載の発明の構成に加えて、しきい値管理手段は、複数の演算手段より出力される比較結果を受けるマンチェスタ型キャリー伝播回路と、複数の演算手段の各々に所定のしきい値を与え、マンチェスタ型キャリー伝播回路の出力に従い、所定のしきい値を一定値増加させ、再度、複数の演算手段に与えるための手段とを含む。
【００４０】
【発明の実施の形態】
以下、図面を参照しつつ、本発明における実施の形態の１つである適応型動き検出装置について説明する。なお、以下の説明では、同一の部品には同一の参照符号を付す。それらの名称および機能も同一であるので、説明の繰返しは適宜省略する。
［実施の形態１］
本実施の形態で述べる適応型動き検出装置は、各リファレンスブロックに対して、その探索対象ブロックとなる入力データに適応して動的サブサンプルおよび動的アルゴリズミック検索を行なうものである。
【００４１】
図１を参照して、本実施の形態に係る適合型動き検出装置１００は、入力部１１０と、入力部１１０の出力に接続された差分絶対値和演算器１１１と、差分絶対値和演算器１１１の出力に接続された出力部１１２と、入力部１１０、差分絶対値和演算器１１１および出力部１１２を制御するための制御部１１３とを含む。
【００４２】
図２を参照して、入力部１１０は、現在のフレーム（リファレンスフレーム）１６１の画像データと、１フレーム前のフレーム（探索対象画像フレーム）１６２の画像データとを受け、リファレンスブロックＸ内の（Ｉ×Ｊ）個のサンプルデータｘ（ｉ，ｊ）を順次出力し、リファレンスブロックＸの左上隅を中心とする２Ｍ×２Ｎの大きさの探索範囲１６３内にある（２Ｍ×２Ｎ）個のベクトルｖ＝（ｍ，ｎ）にそれぞれ対応したＩ×Ｊの大きさの探索対象ブロックＹ（ｍ，ｎ）（ｍ＝−Ｍ〜Ｍ−１，ｎ＝−Ｎ〜Ｎ−１）内の（Ｉ×Ｊ）個のサンプルデータｙ（ｉ＋ｍ，ｊ＋ｎ）（＝ｙ（ｋ，ｌ））を順次出力する。
【００４３】
差分絶対値和演算器１１１は、入力部１１０より出力されるサンプルデータｘ（ｉ，ｊ）（以下、「サンプルデータｘ」と称する。）およびサンプルデータｙ（ｋ，ｌ）（以下、「サンプルデータｙ」と称する。）を順次受け、リファレンスブロックＸと、（２Ｍ×２Ｎ）個の探索対象ブロックＹ（ｍ，ｎ）との間でそれぞれ差分絶対値和Ｄ（ｍ，ｎ）を算出し、差分絶対値和Ｄ（ｍ，ｎ）が最小となるときの値ｍｉｎＤおよび差分絶対値和が最小となるときのｍおよびｎの値、すなわちベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を出力する。出力部１１２は、最小差分絶対値和ｍｉｎＤおよびベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を受け、適当なタイミングでそれらの値を出力する。
【００４４】
図３を参照して、差分絶対値和演算器１１１は、サンプルデータｘおよびｙを受ける減算器５１と、減算器５１による減算結果を受ける絶対値演算器５２と、絶対値演算器５２の出力と後述の累積レジスタ５４に保持された値とを受ける加算器５３と、加算器５３の出力を保持する累積レジスタ５４と、制御部１１３より最小差分絶対値和ｍｉｎＤおよび差分絶対値和が最小となる場合のベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を受け、出力する、図示しない回路とを含む。減算器５１、絶対値演算器５２、加算器５３および累積レジスタ５４は、制御部１１３の後述する制御回路６７より出力される制御信号に従い、動作する。
【００４５】
図４を参照して、制御部１１３は、ベクトルのｖ＝（ｍ，ｎ）の要素をそれぞれ保持し、かつ差分絶対値和演算器１１１で算出された差分絶対値和が最小となる場合のベクトルｖ＝（ｍ，ｎ）の要素をそれぞれ保持するレジスタ６１および６２と、リファレンスブロックの座標（ｉ，ｊ）の各値を記憶するレジスタ６３および６４と、後述する目標差分値Ｔ（Ｘ）を保持するレジスタ６５と、目標差分値Ｔ（Ｘ）と図３の累積レジスタ５４に保持された値とを比較する比較器６６と、入力部１１０、差分絶対値和演算器１１１、出力部１１２および制御部１１３の動作を制御する制御回路６７とを含む。
【００４６】
図５を参照して、適応型動き検出装置１００の各部は以下のように動作する。制御回路６７は、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、リファレンスブロックＸ内のサンプルデータの絶対値の累積加算和であるイントラ評価値を設定する（Ｓ１）。なお、イントラ評価値はこれに限定されるものではなく、一般には、サンプルデータに依存した値である。ベクトルｖ＝（ｍ，ｎ）として、リファレンスブロックＸの左上隅から探索範囲１６３の左下隅へ向かうベクトルｖ＝（−Ｍ，−Ｎ）を設定する（Ｓ２〜Ｓ３）。ベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）として０を設定する。すなわち、累積レジスタ５４をリセットする（Ｓ４）。リファレンスブロックの座標（ｉ，ｊ）を表わすカウンタｉおよびｊの値をそれぞれ０に設定する（Ｓ５〜Ｓ６）。減算器５１でサンプルデータｘ（ｉ，ｊ）とサンプルデータｙ（ｉ＋ｍ，ｊ＋ｎ）との差分値が算出され、絶対値演算器５２で差分値の絶対値が求められる。加算器５３で差分絶対値と累積レジスタ５４との加算が行なわれ、結果Ｄ（ｍ，ｎ）が累積レジスタ５４に保持される（Ｓ７）。比較器６６は、差分絶対値和Ｄ（ｍ，ｎ）と目標差分値Ｔ（Ｘ）とを比較する。差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）以下であれば（Ｓ８でＮＯ）、リファレンスブロックのｙ座標の値ｊが（Ｊ−１）に達したか否かを判断する（Ｓ９）。値ｊが（Ｊ−１）に達していなければ（Ｓ９でＮＯ）、値ｊを１つインクリメントして（Ｓ１０）、Ｓ７の処理に戻る。値ｊが（Ｊ−１）に達していれば（Ｓ９でＹＥＳ）、リファレンスブロックのｘ座標の値ｉが（Ｉ−１）に達したか否かを判断する（Ｓ１１）。値ｉが（Ｉ−１）に達していなければ（Ｓ１１でＮＯ）、値ｉを１つインクリメントして（Ｓ１２）、Ｓ６に処理を戻す。
【００４７】
値ｉが（Ｉ−１）に達していれば（Ｓ１１でＹＥＳ）、そのベクトルｖ＝（ｍ，ｎ）についての差分絶対値和Ｄ（ｍ，ｎ）が求められたことになり、かつその差分絶対値和Ｄ（ｍ，ｎ）がこれまで計算した中で最小となるため、目標差分値Ｔ（Ｘ）に差分絶対値和Ｄ（ｍ，ｎ）を設定する。また、その時のベクトルｖ＝（ｍ，ｎ）をｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）として記憶する（Ｓ１３）。その後Ｓ１４の処理を行なう。あるベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）の演算途中で、差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）を超えた場合には（Ｓ８でＹＥＳ）、それ以上差分絶対値和の演算を行なっても、そのベクトルに対する差分絶対値和は最小とはならない。このため、その時点で差分絶対値和Ｄ（ｍ，ｎ）の演算を打ち切りＳ１４の処理を行なう。
【００４８】
Ｓ１４では、ベクトルｖの要素ｎが（Ｎ−１）に達したか否かを判断する。要素ｎが（Ｎ−１）に達していなければ（Ｓ１４でＮＯ）、要素ｎを１つインクリメントして（Ｓ１５）、Ｓ４に処理を戻す。要素ｎが（Ｎ−１）に達していれば（Ｓ１４でＹＥＳ）、ベクトルｖの要素ｍが（Ｍ−１）に達したか否かを判断する（Ｓ１６）。要素ｍが（Ｍ−１）に達していなければ（Ｓ１６でＮＯ）、要素ｍを１つインクリメントして（Ｓ１７）、Ｓ３に処理を戻す。要素ｍが（Ｍ−１）に達していれば（Ｓ１６でＹＥＳ）、すべてのベクトルに対する探索が終了したことになるため、目標差分値Ｔ（Ｘ）とイントラ評価値Ｔ０（Ｘ）とを比較する（Ｓ１８）。目標差分値Ｔ（Ｘ）とイントラ評価値Ｔ０（Ｘ）とが等しい場合には（Ｓ１８でＹＥＳ）、当初の目標差分値Ｔ（Ｘ）であるイントラ評価値Ｔ０（Ｘ）をいずれのベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）も値として下回ることができなかったことを示している。このため、制御回路６７は、リファレンスブロックＸに最も似通った探索対象ブロックＹ（ｍ，ｎ）が見つからなかったと判断する（Ｓ１９）。
【００４９】
目標差分値Ｔ（Ｘ）と初期値Ｔ０（Ｘ）として設定したイントラ評価値とが異なっている場合には（Ｓ１８でＮＯ）、目標差分値Ｔ（Ｘ）に設定されている値を最小差分絶対値和ｍｉｎＤとして差分絶対値和演算器１１１（図１）を介して、出力部１１２に出力し、ベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を差分絶対値和Ｄ（ｍ，ｎ）が最小となる場合のベクトルとして差分絶対値和演算器１１１を介して出力部１１２に出力する（Ｓ２０）。
【００５０】
そもそも、動き検出装置では、探索範囲内のベクトルｖ＝（ｍ，ｎ）に対して、差分絶対値和Ｄ（ｍ，ｎ）が最小となるベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を１つ検出できればよい。このため、それ以外のベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）は必要とされない。本実施の形態に係る動き適合型検出装置１００では、ベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）の演算過程で演算の途中結果が目標差分値Ｔ（Ｘ）を超えた場合には、そのベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）は最小とはなり得ないと判断して、演算を中止する。このため、各ベクトルｖ＝（ｍ，ｎ）に対応する差分絶対値和Ｄ（ｍ，ｎ）の演算をすべてのサンプルデータについて行なう従来の動き検出装置に比べて、大幅に演算量を削減することができる。また、演算量の削減に伴い処理が高速化され、消費電力が低減される。
【００５１】
また、適合型動き検出装置１００は、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、リファレンスブロック内の各サンプルデータの絶対値の累積和であるイントラ評価値を用いている。このため、この適応型動き検出装置１００を用いた動画像圧縮システムを考えると、ベクトルｖ＝（ｍ，ｎ）が見つからなかった場合には、リファレンスブロック自体を画像圧縮の対象とすることにより、圧縮効率の低下を防ぐことができる。
［実施の形態２］
図６を参照して、本実施の形態に係る適応型動き検出装置２００は、動画像フレームの画像データを順次受け、リファレンスブロックＸのサンプルデータｘと、探索対象ブロックＹ（ｍ，ｎ）のサンプルデータｙとを順次出力する入力部２２０と、探索対象ブロックＹ（ｍ，ｎ）のサンプルデータｙを保持し、隣接するレジスタと接続されたレジスタ２１１〜２１４と、レジスタ２１１〜２１４より探索対象ブロックＹ（ｍ，ｎ）のサンプルデータｙを受け、入力部よリファレンスブロックＸのサンプルデータｘを受け、後述する出力部２３０より目標差分値Ｔ（Ｘ）を受け、後述する制御部２４０より出力される制御信号およびクロック信号に従い、リファレンスブロックＸと探索対象ブロックＹ（ｍ，ｎ）との間の差分絶対値和Ｄ（ｍ，ｎ）を算出するための複数の演算エレメント（以下「ＰＥ」と称する。）２０１〜２０４と、ＰＥ２０１〜２０４より出力された差分絶対値和Ｄ（ｍ，ｎ）を受け、差分絶対値和Ｄ（ｍ，ｎ）の最小値ｍｉｎＤを適当なタイミングで出力し、差分絶対値和Ｄ（ｍ，ｎ）を算出する際に必要となる目標差分値Ｔ（Ｘ）をしきい値メモリ２３０に保持する出力部２３０と、各構成部品の制御を行ない、ベクトルｖ＝（ｍ，ｎ）の要素を管理するベクトル管理部２５０を有し、差分絶対値和Ｄ（ｍ，ｎ）が最小となる場合のベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を保持するための制御部２４０とを含む。
【００５２】
図７を参照して、ＰＥ２０１の内部構成について説明する。なお、ＰＥ２０２〜２０４の内部構成もＰＥ２０１の内部構成と同一であるため、説明は繰返さない。ＰＥ２０１は、サンプルデータｘおよびｙをそれぞれ受けるゲート２１および２２と、ゲート２１および２２の出力に接続され、サンプルデータｘとサンプルデータｙとの間の差分絶対値和を求める差分絶対値和演算器２３と、差分絶対値和演算器２３の出力に接続されたラッチ２４と、ラッチ２４の出力および後述の比較演算器２７の出力Ｄ（ｍ，ｎ）を受ける加算器２５と、加算器２５の値を保持するための累積レジスタ２６と、累積レジスタ２６に保持された値と出力部２３０より与えられる目標差分値Ｔ（Ｘ）とを受ける比較演算器２７と、比較演算器２７の出力Ｐおよび制御部２４０より出力されるクロック信号にそれぞれ接続された２入力を有するＡＮＤゲート２８とを含む。ゲート２１および２２は、ＡＮＤゲート２８より出力されるクロック信号の立ち上がり時または立ち下がり時にゲートをオープンする。比較演算器２７の出力Ｄ（ｍ，ｎ）は、累積レジスタ２６に保持された値である。比較演算器２７の出力Ｐは、累積レジスタ２６に保持された値が目標差分値Ｔ（Ｘ）よりも大きい場合には０となり、それ以外では１となる。
【００５３】
比較演算器２７の出力Ｐが０の場合には、ＡＮＤゲート２８の一方の入力に０が与えられる。このため、ＡＮＤゲート２８の出力は常に０となり、サンプルデータｘおよびｙの値は、ゲート２１および２２をそれぞれ通過することができなくなる。よって、この場合の消費電力は、ＰＥ２０１の動作時の消費電力に比べて無視できるほど小さくなっている。
図８を参照して、出力部２３０に含まれるしきい値更新回路の構成について説明する。この回路は、ＰＥ２０１〜２０４でそれぞれ算出される差分絶対値和Ｄ（ｍ，ｎ）がすべて目標差分値Ｔ（Ｘ）を超えた場合に、目標差分値Ｔ（Ｘ）に固定値Δを加算して新たな目標差分値Ｔ（Ｘ）とするものである。しきい値更新回路は、ＰＥ２０１〜２０４より出力され、目標差分値Ｔ（Ｘ）以下の値を取る差分絶対値和Ｄ（ｍ，ｎ）を保持するためのしきい値メモリ２６０と、ＰＥ２０１〜２０４のそれぞれの比較演算器２７の出力に接続され、比較演算器２７の出力Ｐが全て０の場合に０を出力し、それ以外の場合に１を出力するマンチェスタ型キャリー伝播回路２３１と、マンチェスタ型キャリー伝播回路２３１の出力が０の場合に後述の加算器２３５の加算結果を選択して出力し、マンチェスタ型キャリー伝播回路２３１の出力が１の場合にしきい値メモリ２６０に保持された値を選択して出力するセレクタ２３２と、セレクタ２３２の出力を保持するためのラッチ２３４と、上述の固定値Δを保持するためのレジスタ２３３と、レジスタ２３３およびラッチ２３４にそれぞれ保持された値を受ける加算器２３５とを含む。なお、マンチェスタ型キャリー伝播回路については、特開昭６２−１０３７３２号公報に詳しく開示されている。
【００５４】
図９および図１０を参照して、適応型動き検出装置２００の各部は以下のように動作する。適応型動き検出装置２００では、１つのリファレンスブロックＸに対する探索範囲１６３をｘ軸方向およびｙ軸方向にそれぞれＬ分割し、Ｌ2 個のサブ領域を作成し、処理を行なう。各サブ領域をＶ（ｌ）とする。ただし、ｌは０から（Ｌ2 −１）までの整数である。また、サブ領域Ｖ（ｌ）のｘ軸方向の大きさは２Ｍ（ｌ）とし、ｙ軸方向の大きさは２Ｎ（ｌ）とする。
【００５５】
出力部２３０は、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）を設定する。初期値Ｔ０（Ｘ）は、現フレームのリファレンスブロックＸと同一の位置における１フレーム前のリファレンスブロックＸに対して求められた最小差分絶対値和ｍｉｎＤである。また、集合Ｓを空集合とし、ｌ＝０とする（Ｓ２１）。
【００５６】
サブ領域Ｖ（０）内の（２Ｍ（０）×２Ｎ（０））個のベクトルｖ＝（ｍ，ｎ）を集合Ｓの要素とする。ここで、ｍおよびｎはそれぞれ（Ａ（０）−Ｍ（０））〜（Ａ（０）＋（Ｍ（０）−１））の間の整数および（Ｂ（０）−Ｎ（０））〜（Ｂ（０）＋（Ｎ（０）−１））の間の整数とする（Ｓ２２）。なお、Ａ（０）およびＢ（０）は、それぞれサブ領域Ｖ（０）の中央のｘ座標およびｙ座標とする。
【００５７】
（２Ｍ（０）×２Ｎ（０））個のベクトルｖ＝（ｍ，ｎ）のそれぞれにＰＥ２０１〜２０４のいずれかを割り当て、起動する（Ｓ２３）。割り当てられたＰＥを以下ＰＥ（ｍ，ｎ）と称する。各ＰＥ（ｍ，ｎ）は、リファレンスブロックＸとベクトルｖ＝（ｍ，ｎ）における探索対象ブロックＹ（ｍ，ｎ）との間の差分絶対値Ｄ（ｍ，ｎ）を計算するため、差分絶対値和Ｄ（ｍ，ｎ）に０を初期設定する。すなわち、累積レジスタ２６をリセットする（Ｓ２４）。また、リファレンスブロックＸ内の各サンプルのｘ座標を表わす列番号ｉに０を設定する（Ｓ２５）。
【００５８】
各ＰＥ（ｍ，ｎ）を並列に動作させ、リファレンスブロックＸと探索対象ブロックＹ（ｍ，ｎ）との間の第ｉ列目に対する差分絶対値和Ｄ（ｍ，ｎ）を算出する（Ｓ２６）。すなわち、行番号ｊを０から（Ｊ−１）まで変化させながら、リファレンスブロックＸのサンプルｘ（ｉ，ｊ）と探索対象ブロックＹ（ｍ，ｎ）のサンプルｙ（ｉ＋ｍ，ｊ＋ｎ）との間の差分絶対値を算出し、その差分絶対値を累積加算する。
【００５９】
各ベクトルｖ＝（ｍ，ｎ）について、第ｉ列目まで求められた差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）より大きいか否かを判断する（Ｓ２７）。差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）を超えていれば（Ｓ２７でＹＥＳ）、対応するベクトルｖ＝（ｍ，ｎ）を集合Ｓから集合Ｓｉに移動させる（Ｓ２８）。差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）以下であれば（Ｓ２７でＮＯ）、何もしない。Ｓ２７およびＳ２８の処理を集合Ｓ内のすべてのベクトルｖ＝（ｍ，ｎ）に関して行なう。
【００６０】
Ｓ２７およびＳ２８の処理の後、集合Ｓが空集合か否かを判断する（Ｓ２９）。集合Ｓが空集合の場合（Ｓ２９でＹＥＳ）、すなわちすべての差分絶対値Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）を超えてしまった場合には、集合Ｓｉの要素をすべて集合Ｓに移動させ（Ｓ３０）、目標差分値Ｔ（Ｘ）の値を固定値Δだけ増やす（Ｓ３１）。その後、Ｓ２７の処理を再度繰返す。
【００６１】
集合Ｓが空集合でなければ（Ｓ２９でＮＯ）、すなわち目標差分値Ｔ（Ｘ）以下の差分絶対値Ｄ（ｍ，ｎ）が１つでも存在するならば、集合Ｓｉに属するすべてのベクトルｖ＝（ｍ，ｎ）に関するＰＥ（ｍ，ｎ）での演算を中止させる（Ｓ３２）。列番号ｉが（Ｉ−１）に達したか否かを判断する（Ｓ３３）。列番号ｉが（Ｉ−１）に達していなければ（Ｓ３３でＮＯ）、列番号ｉを１つインクリメントし（Ｓ３４）、Ｓ２６以下の処理を繰返す。列番号ｉが（Ｉ−１）に達していれば（Ｓ３３でＹＥＳ）、集合Ｓに残ったベクトルｖ＝（ｍ，ｎ）に対応する差分絶対値和Ｄ（ｍ，ｎ）の最小値を目標差分値Ｔ（Ｘ）とし、最小の差分絶対値和Ｄ（ｍ，ｎ）をとるベクトルｖ＝（ｍ，ｎ）をベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）として記憶する（Ｓ３５）。
【００６２】
カウンタｌが（Ｌ2 −１）に達したか否か、すなわちすべてのサブ領域Ｖ（ｌ）についての差分絶対値和の演算が終了したか否かを判断する（Ｓ３６）。カウンタｌが（Ｌ2 −１）に達していれば（Ｓ３６でＹＥＳ）、処理を終了する。カウンタｌが（Ｌ2 −１）に達していなければ（Ｓ３６でＮＯ）、カウンタｌを１つインクリメントする（Ｓ３７）。
【００６３】
サブ領域Ｖ（ｌ）内の（２Ｍ（ｌ）×２Ｎ（ｌ））個のベクトルｖ＝（ｍ，ｎ）を集合Ｓの要素とする。ここで、ｍおよびｎはそれぞれ（Ａ（ｌ）−Ｍ（ｌ））〜（Ａ（ｌ）＋（Ｍ（ｌ）−１））の間の整数および（Ｂ（ｌ）−Ｎ（ｌ））〜（Ｂ（ｌ）＋（Ｎ（ｌ）−１））の間の整数とする（Ｓ４２）。なお、Ａ（ｌ）およびＢ（ｌ）はそれぞれ、サブ領域Ｖ（ｌ）の中央のｘ座標およびｙ座標とする。
【００６４】
（２Ｍ（ｌ）×２Ｍ（ｌ））個のベクトルｖ＝（ｍ，ｎ）の各々にＰＥ（ｍ，ｎ）を割り当て、起動する（Ｓ４３）。各ＰＥ（ｍ，ｎ）の演算結果である差分絶対値和Ｄ（ｍ，ｎ）に０を初期設定する（Ｓ４４）。すなわち、累積レジスタ２６をリセットする（Ｓ４４）。また、リファレンスブロックＸ内の各サンプルのｘ座標を表わす列番号ｉに０を設定する（Ｓ４５）。
【００６５】
各ＰＥ（ｍ，ｎ）を並列に動作させ、リファレンスブロックＸと探索対象ブロックＹ（ｍ，ｎ）との間の第ｉ列目に対する差分絶対値和Ｄ（ｍ，ｎ）を算出する（Ｓ４６）。すなわち、行番号ｊを０から（Ｊ−１）まで変化させながら、リファレンスブロックＸのサンプルｘ（ｉ，ｊ）と探索対象ブロックＹ（ｍ，ｎ）のサンプルｙ（ｉ＋ｍ，ｊ＋ｎ）との間の差分絶対値を算出し、その差分絶対値を累積する。
【００６６】
各ベクトルｖ＝（ｍ，ｎ）について、第ｉ列目まで求められた差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）より大きいか否かを判断する（Ｓ４７）。差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）を超えていれば（Ｓ４７でＹＥＳ）、対応するベクトルｖ＝（ｍ，ｎ）を集合Ｓから削除して、ＰＥ（ｍ，ｎ）の演算を停止させる（Ｓ５２）。
【００６７】
差分絶対値和Ｄ（ｍ，ｎ）が目標差分値Ｔ（Ｘ）を超えていなければ（Ｓ５３でＮＯ）、列番号ｉをインクリメントし、停止していないＰＥ（ｍ，ｎ）に関して差分絶対値和Ｄ（ｍ，ｎ）の計算を続行させる（Ｓ４６）。
【００６８】
列番号ｉが（Ｉ−１）に到達した場合には（Ｓ５３でＹＥＳ）、集合Ｓに残ったベクトルｖ＝（ｍ，ｎ）に対応する差分絶対値和Ｄ（ｍ，ｎ）の最小値を新たな目標差分値Ｔ（Ｘ）とし、最小の差分絶対値和Ｄ（ｍ，ｎ）をとるベクトルｖ＝（ｍ，ｎ）をベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）として記憶する（Ｓ５５）。
【００６９】
カウンタｌが（Ｌ2 −１）に達したか否か、すなわちすべてのサブ領域Ｖ（ｌ）についての差分絶対値和の演算が終了したか否かを判断する（Ｓ５６）。カウンタｌが（Ｌ2 −１）に達していれば（Ｓ５６でＹＥＳ）、処理を終了する。カウンタｌが（Ｌ2 −１）に達していなければ（Ｓ５６でＮＯ）、Ｓ３７以降の処理を繰返す。
【００７０】
図１１を参照して、適応型動き検出装置２００を用いて差分絶対値和を求めた際の演算過程の一例について説明する。この例では、目標差分値Ｔ（Ｘ）を５とし、リファレンスブロックＸに対する６種類の探索対象ブロックＹとの間の絶対値差分和演算を６つのＰＥ（ＰＥ（０）〜ＰＥ（５））を用いてそれぞれ実行する。リファレンスブロックＸと６種類の探索対象ブロックＹの各々は、３行３列のサンプルからなるものとする。また、差分絶対値和Ｄ（ｍ，ｎ）は、図９および図１０のフローチャートとは異なり、１行ずつ求められるものとする。
【００７１】
１行目のサンプルデータに対するＰＥ（０）〜ＰＥ（５）の演算結果が、それぞれ３、０、３、９、３、５となったとする。この時点でＰＥ（３）の演算結果は目標差分値Ｔ（Ｘ）を超えているため、ＰＥ（３）の処理が中断する。ＰＥ（３）を除く５つのＰＥにおいて２行目の演算が行われる。
【００７２】
２行目のサンプルデータに対するＰＥ（０）〜ＰＥ（２）、ＰＥ（４）およびＰＥ（５）の演算結果が、それぞれ６、０、６、３、１０となったとする。この時点でＰＥ（０）、ＰＥ（２）およびＰＥ（５）の演算結果が目標差分値Ｔ（Ｘ）を超えているため、ＰＥ（０）、ＰＥ（２）およびＰＥ（５）の処理が中断する。残りの２つのＰＥにおいて３行目の演算が行なわれる。
【００７３】
３行目のサンプルデータに対するＰＥ（１）およびＰＥ（４）の演算結果が、それぞれ０および６であるとする。この時点で、ＰＥ（４）の演算結果が目標差分値Ｔ（Ｘ）を超えているため、ＰＥ（４）の処理が終了する。結局、ＰＥ（１）の演算結果が最小差分絶対値和ｍｉｎＤとして検出され、ＰＥ（１）に対応するベクトルが探索結果となる。この例では、２行目のサンプルデータに対する演算においては１つのＰＥが、３行目のサンプルデータに対する演算においては４つのＰＥが、それぞれ停止している。このため、このように途中でＰＥの演算を停止させない場合に比べて、ＰＥの稼働率が１３／１８となる。また、停止時のＰＥの消費電力は、動作時のＰＥの消費電力に比べて、無視できるほど小さい。このため、ＰＥの消費電力も１３／１８に削減される。
【００７４】
そもそも、動き検出装置では、探索範囲内のベクトルｖ＝（ｍ，ｎ）に対して、差分絶対値和Ｄ（ｍ，ｎ）が最小となるベクトルｍｉｎｖ＝（ｍｉｎｍ，ｍｉｎｎ）を１つ検出できればよい。このため、それ以外のベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）は必要とされない。本実施の形態に係る動き適合型検出装置２００では、ベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）の演算過程で演算の途中結果が目標差分値Ｔ（Ｘ）を超えた場合には、そのベクトルｖ＝（ｍ，ｎ）に対する差分絶対値和Ｄ（ｍ，ｎ）は最小となり得ないと判断して、演算を中止する。このため、各ベクトルｖ＝（ｍ，ｎ）に対応する差分絶対値和Ｄ（ｍ，ｎ）の演算をすべてのサンプルデータについて行なう従来の動き検出装置に比べて、大幅に演算量を削減することができる。
【００７５】
また、適合型動き検出装置２００では、現フレームのリファレンスブロックＸと同一の位置における１フレーム前のリファレンスブロックＸに対して求められた最小差分絶対値和ｍｉｎＤを初期の目標差分値Ｔ（Ｘ）としている。これは、同一位置のリファレンスブロックＸは隣接するフレーム間では、類似しているためである。これにより、初期の目標差分値Ｔ（Ｘ）を小さめに設定することができ、多くのＰＥの演算を早い段階で停止させることができる。このため、処理が高速となり、消費電力を削減することができる。
【００７６】
適合型動き検出装置２００では、１列分のサンプルデータに対する差分絶対値和が求められ、もとの差分絶対値和に累積加算された後に（図９のＳ２６および図１０のＳ４６）、差分絶対値和が目標差分値Ｔ（Ｘ）と比較される（Ｓ２７およびＳ４７）。この目標差分値Ｔ（Ｘ）との比較処理は、数列ごとで行なってもよいし、数サンプルデータごとに行なってもよい。また、１列ごとに差分絶対値和を求めるのではなく、１行ごとまたは矩形領域ごとに差分絶対値和を求め、その後、目標差分値Ｔ（Ｘ）との比較を行なうようにしてもよい。
［実施の形態３］
本実施の形態に係る適応型動き検出装置は、実施の形態１に係る適応型動き検出装置１００と同様の構成をとる。このため、説明は繰返さない。本実施の形態に係る適応型動き検出装置１００は、制御部１１３の制御方法が一部異なる。
【００７７】
図１２を参照して、制御部１１３の制御方法が異なった適応型動き検出装置１００の各部は、以下のように動作する。
【００７８】
目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、リファレンスブロックＸ内のサンプルデータの絶対値の累積加算和であるイントラ評価値を設定する（Ｓ１）。（ｍ2 ＋ｎ2 ）の値が最小となる未探索のベクトルｖ＝（ｍ，ｎ）を選択する（Ｓ６０）。図５のＳ４〜Ｓ１３までの処理と同様の処理が行なわれ、必要に応じて目標差分値Ｔ（Ｘ）が更新される（Ｓ４〜Ｓ１３）。未探索のベクトルｖ＝（ｍ，ｎ）が存在するか否かが判断される（Ｓ６１）。未探索のベクトルが存在するのであれば（Ｓ６１でＹＥＳ）、Ｓ６０以降の処理が繰返される。未探索のベクトルが存在しなければ（Ｓ６１でＮＯ）、図５のＳ１８〜Ｓ２０の処理と同様の処理が行なわれ、探索結果が決定される（Ｓ１８〜Ｓ２０）。
【００７９】
本実施の形態に係る適合型動き検出装置１００では、（ｍ2 ＋ｎ2 ）の値が小さいベクトルｖ＝（ｍ，ｎ）から探索が行われる。これは、リファレンスブロックＸの近傍から探索が行われることを意味する。一般にリファレンスブロックＸの近傍に最小差分絶対値和をとるベクトルｖ＝（ｍ，ｎ）が存在することが多い。このため、動きの少ない動画像に対しては、早い段階で最小の差分絶対値和を求めることができ、リファレンスブロックＸより遠いベクトルに対しては初期の段階で差分絶対値和演算を打ち切ることができる。このため消費電力が低減する。
【００８０】
本実施の形態では、（ｍ2 ＋ｎ2 ）の値が小さいベクトルｖ＝（ｍ，ｎ）から探索が行われるが、同様の効果を上げることができる方法として、リファレンスブロックＸの存在する位置から螺旋状に遠ざかる方向にベクトルｖ＝（ｍ，ｎ）の探索を行なうことも可能である。
【００８１】
また、本実施の形態に係る適応型動き検出装置１００は、実施の形態１に係る適応型動き検出装置１００と同様の効果を奏する。
［実施の形態４］
実施の形態２に係る適応型動き検出装置２００では、図９のＳ２１の処理で、現フレームのリファレンスブロックＸと同一の位置における１フレーム前のリファレンスブロックＸに対して求められた最小差分絶対値和ｍｉｎＤを初期の目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）としている。すなわち、初期値Ｔ０（Ｘ）は現フレームから数えて１フレーム前の画像データおよび２フレーム前の画像データを用いて算出されたものである。しかし、１フレーム前と現フレームとの間でシーンチェンジが生じた場合には、初期値Ｔ０（Ｘ）よりも小さな差分絶対値Ｄ（ｍ，ｎ）が見つかる可能性は低くなる。このため、適合型動き検出装置２００は、Ｓ２７〜Ｓ３１までの処理を何度も繰返さなければならなくなる。
【００８２】
そこで、本実施の形態では、シーンチェンジが生じた場合には初期値Ｔ０（Ｘ）として、一定の大きな値またはイントラ評価値を使用するものである。
【００８３】
本実施の形態に係る適応型動き検出装置は、図６〜図８を参照して説明した実施の形態２の動き検出装置２００と同様の構成をとる。以下に異なる部品の説明のみを行ない、その他の説明は繰返さない。本実施の形態に係る適応型動き検出装置２００の出力部は、実施の形態２の出力部２３０の構成において、図示しない入力フィルタによりシーンチェンジが検出された際には、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、一定の大きな値またはイントラ評価値を出力するための回路（図示せず）が付け加えられたものである。
【００８４】
本実施の形態に係る適応型動き検出装置の動作は、図９および図１０に示したものとＳ２１の処理以外は同様である。このため、それらの処理の説明は繰返さない。
【００８５】
Ｓ２１においては、上述のように、通常は目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、現フレームのリファレンスブロックと同一の位置における１フレーム前のリファレンスブックＸに対して求められた最小差分絶対値和ｍｉｎＤを用いる。しかし、シーンチェンジが検出された際には、一定の大きな値またはイントラ評価値を初期値Ｔ０（Ｘ）に設定する。
【００８６】
本実施の形態に係る適応型動き検出装置は、実施の形態２と同様の効果を奏する。それに加え、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）が小さすぎるために図９のＳ２７〜Ｓ３１の処理を繰返すという問題を少なくすることができる。これに伴い、処理時間が短くなり、消費電力が削減される。
【００８７】
特に、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、イントラ評価値を用いる場合には、最終的に最小差分絶対値和が求まらなくてもよい。これは、実施の形態１の場合と同様に、リファレンスブロック自体を画像圧縮の対象とすればよいからである。したがって、この場合には、Ｓ２７〜Ｓ３１までの処理をＳ４７〜Ｓ５４の処理で置き換えることも可能である。このようにすることにより、処理のアルゴリズムを単純化することができる。
［実施の形態５］
実施の形態２に係る適応型動き検出装置２００では、現フレームのリファレンスブロックＸと同一の位置における１フレーム前のリファレンスブロックＸに対して求められた最小差分絶対値和ｍｉｎＤを目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として用いた。本実施の形態に係る適合型動き検出装置２００では、リファレンスブロックＸに隣接するリファレンスブロック（Ｘ−１）に対して求められた最小差分絶対値和ｍｉｎＤまたはリファレンスブロックＸのイントラ評価値のうち、いずれか小さいほうの値を目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として用いる。
【００８８】
本実施の形態に係る適応型動き検出装置は、実施の形態２に係る適応型動き検出装置２００と同様の構成をとる。このため、以下に異なる点のみを説明し、その他の説明は繰返さない。本実施の形態に係る適応型動き検出装置２００のしきい値メモリ２６０は、実施の形態２のしきい値メモリ２６０よりも少ない容量にすることができる。
【００８９】
実施の形態２では、目標差分値の初期値Ｔ０（Ｘ）として、１フレーム前の処理で求められた最小差分絶対値和ｍｉｎＤを用いている。一般にリファレンスフレーム内には１０００個程度のリファレンスブロックが存在する。このため、実施の形態２のしきい値メモリ２６０には、リファレンスブロックの個数と同じ１０００個程度の最小差分絶対値和ｍｉｎＤを記憶する必要がある。しかし、本実施の形態では、リファレンスブロックＸに隣接する、同一フレーム内のリファレンスブロック（Ｘ−１）に対して求められた最小差分絶対値和ｍｉｎＤまたはリファレンスブロックＸのイントラ評価値のいずれかを目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として用いる。このため、しきい値メモリ２６０には、隣接するリファレンスブロック（Ｘ−１）に対する最小差分絶対値和ｍｉｎＤのみを記憶するだけでよい。
【００９０】
本実施の形態に係る適応型動き検出装置２００の動作は、図９および図１０を参照して説明した実施の形態２に係る適応型動き検出装置２００と同様であるため、説明は繰返さない。なお、上述のように、本実施の形態に係る適応型動き検出装置２００では、図９のＳ２１の処理において、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）として、リファレンスブロック（Ｘ−１）に対する差分絶対値和ｍｉｎＤよびイントラ評価値のいずれか小さいほうの値を設定する。
【００９１】
一般にあるリファレンスブロックＸは、隣接するリファレンスブロック（Ｘ−１）と類似の性質を持つことが多い。このため、目標差分値Ｔ（Ｘ）の初期値Ｔ０（Ｘ）としてリファレンスブロック（Ｘ−１）に対する最小差分絶対値和ｍｉｎＤを用いることにより、図９のステップ２７〜３１までの処理を効率的に行なうことができる。
【００９２】
また、本実施の形態に係る適応型動き検出装置２００は、実施の形態２に係る適応型動き検出装置２００と同様の効果を奏する。
［実施の形態６］
図６を参照して、実施の形態２に係る適応型動き検出装置２００では、しきい値メモリ２６０を出力部２３０に備えていた。このため、目標差分値Ｔ（Ｘ）は、出力部２３０より各ＰＥ２０１〜２０４に与えられていた。
【００９３】
本実施の形態に係る適応型動き検出装置２００では、ＰＥ２０１〜２０４ごとにしきい値メモリを設け、それぞれのしきい値メモリに目標差分値Ｔ（Ｘ）を記憶するようにしたものである。
【００９４】
図１３を参照して、本実施の形態に係る適応型動き検出装置３００は、動画像フレームを順次受け、リファレンスブロックＸのサンプルデータｘと、探索対象ブロックＹ（ｍ，ｎ）のサンプルデータｙとを順次出力し、後述の出力部３３０より目標差分値Ｔ（Ｘ）を受け、出力する、入力部３２０と、レジスタ２１１〜２１４と、ＰＥ２０１〜２０４と、ＰＥ２０１〜２０４より出力された差分絶対値和を受け、差分絶対値和の最小値を適当なタイミングで出力し、目標差分値Ｔ（Ｘ）を出力するための出力部３３０と、入力部３２０より出力された目標差分値Ｔ（Ｘ）をそれぞれ保持し、目標差分値Ｔ（Ｘ）をＰＥ２０１〜２０４にそれぞれ与えるしきい値メモリ２６１〜２６４とを含む。
【００９５】
適応型動き検出装置３００の動作は、図９および図１０を参照して説明した実施の形態２に係る適応型動き検出装置２００の動作と同様である。このため、説明は繰返さない。
【００９６】
適応型動き検出装置３００では、しきい値メモリ２６１〜２６４がＰＥ２０１〜２０４の入力の近傍にそれぞれ配置されている。しきい値メモリ２６１〜２６４へは、入力部３２０より各ＰＥ２０１〜２０４へリファレンスブロックＸを与える際に用いられるバス２２６を介して、目標差分値Ｔ（Ｘ）が設定される。このため、適応型動き検出装置２００で必要であった、出力部２３０からＰＥ２０１〜２０４のそれぞれへ目標差分値Ｔ（Ｘ）を与えるためのバス２２９（図６）が必要なくなる。このため、適応型動き検出装置３００は、適応型動き検出装置２００に比べて単純なバス構成となる。しかも、適応型動き検出装置２００と同様の効果を奏することができる。
［実施の形態７］
図１４を参照して、本実施の形態に係る適応型動き検出装置４００は、図１３を参照して説明した実施の形態６に係る適応型動き検出装置３００の構成に加えて、リファレンスブロックＸのサンプルデータｘを記憶し、ＰＥ２０１〜２０４の入力にそれぞれ接続されたレジスタ２７１〜２７４をさらに含む。レジスタ２７１〜２７４の各々はＪ個のラッチを有し、リファレンスブロックＸの１列分のサンプルデータを記憶することができる。
【００９７】
ＰＥ２０１〜２０４ならびにＰＥに接続されたしきい値メモリ２６１〜２６４、レジスタ２７１〜２７４および２１１〜２１４は、それぞれＩ個ごとにグループ化されている。このため、１つのグループ内のレジスタ２７１〜２７４にはリファレンスブロックＸの（Ｉ×Ｊ）個のサンプルデータがすべて記憶されていることになる。
【００９８】
グループの個数をＫ個とした場合、適応型動き検出装置４００は、Ｋ個のリファレンスブロックに対する処理を同時に行なうことができる。Ｋ個のリファレンスブロックは、その探索範囲１６３（図２）が共通部分を有するように選択される。Ｋ個のリファレンスブロックの各々は、他のリファレンスブロックのいずれかと隣接するように配置されていれば、探索範囲の共通部分の面積を最大にすることができる。
【００９９】
共通する探索範囲に含まれる探索対象ブロックＹ（ｍ，ｎ）の値は、すべてのＰＥ２０１〜２０４で使用することが可能である。このため、レジスタ２１１〜２１４に共通探索範囲内の探索対象ブロックＹ（ｍ，ｎ）の値を順次設定することにより、複数のリファレンスブロックに対する処理を同時に実行することが可能となる。
【０１００】
適応型動き検出装置４００の動作は、図９および図１０を参照して説明した実施の形態２に係る適応型動き検出装置２００の動作と同様である。ただし、適応型動き検出装置２００では、１つのリファレンスブロックＸに対する複数の処理が並列に実行されたのに対して、適応型動き検出装置４００ではＫ個のリファレンスブロックに対する複数の処理が並列に実行される。
【０１０１】
適応型動き検出装置４００によると、複数のリファレンスブロックに対する探索対象ブロックとの差分絶対値和演算を並列に行なうことができる。このため、処理速度を向上させることができる。ひいては装置の消費電力を低減させることができる。
【０１０２】
また、適応型動き検出装置４００は、実施の形態６に係る適応型動き検出装置３００と同様の効果を奏する。
【０１０３】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【０１０４】
【発明の効果】
請求項１〜３に記載の発明によると、最適なしきい値を設定でき、高速処理可能な動き検出方法を提供することができる。
【０１０５】
請求項４〜１４に記載の発明によると、最適なしきい値を設定でき、高速処理可能で、かつ消費電力が低い動き検出装置を提供することができる。
【０１０６】
請求項１３に記載の発明によると、最適なしきい値を設定でき、高速処理可能で、消費電力が低く、かつ内部構成が簡略化された動き検出装置を提供することができる。
【図面の簡単な説明】
【図１】  実施の形態１に係る適応型動き検出装置１００の構成を示す図である。
【図２】  リファレンスブロックと探索対象ブロックとの位置関係を示す図である。
【図３】  差分絶対値和演算器１１１の構成を示す図である。
【図４】  制御部１１３の構成を示す図である。
【図５】  適応型動き検出装置１００の動作を示すフローチャートである。
【図６】  実施の形態２に係る適応型動き検出装置２００の構成を示す図である。
【図７】  演算エレメント（ＰＥ）２０１の構成を示す図である。
【図８】  出力部２３０に含まれるしきい値更新回路の構成を示す図である。
【図９】  適応型動き検出装置２００の動作を示すフローチャートである。
【図１０】  適応型動き検出装置２００の動作を示すフローチャートである。
【図１１】  適応型動き検出装置２００を用いて差分絶対値和を求める際の演算過程を説明する図である。
【図１２】  実施の形態３に係る適応型動き検出装置１００の動作を示すフローチャートである。
【図１３】  実施の形態６に係る適応型動き検出装置３００の構成を示す図である。
【図１４】  実施の形態７に係る適応型動き検出装置４００の構成を示す図である。
【符号の説明】
２１，２２  ゲート、２３  差分絶対値和演算器、２４  ラッチ、２５，５３，２３５  加算器、２６，５４  累積レジスタ、２７  比較演算器、２８  ＡＮＤゲート、５１  減算器、５２  絶対値演算器、６１〜６５，２１１〜２１４，２３３，２７１〜２７４  レジスタ、６６  比較器、６７  制御回路、１００，２００，３００，４００  適応型動き検出装置、１１０，２２０，３２０  入力部、１１１  差分絶対値和演算器、１１２，２３０，３３０  出力部、１１３，２４０  制御部、１６１  リファレンスフレーム、１６２  探索対象画像フレーム、１６３  探索範囲、２０１〜２０４  演算エレメント（ＰＥ）、２２６，２２９  バス、２３１  マンチェスタ型キャリー伝播回路、２３２  セレクタ、２３４  ラッチ、２５０  ベクトル管理部、２６０〜２６４  しきい値メモリ。
【図１】
0004027513.tif 000002
【図２】
0004027513.tif 000003
【図３】
0004027513.tif 000004
【図４】
0004027513.tif 000005
【図５】
0004027513.tif 000006
【図６】
0004027513.tif 000007
【図７】
0004027513.tif 000008
【図８】
0004027513.tif 000009
【図９】
0004027513.tif 000010
【図１０】
0004027513.tif 000011
【図１１】
0004027513.tif 000012
【図１２】
0004027513.tif 000013
【図１３】
0004027513.tif 000014
【図１４】
0004027513.tif 000015