(57)【特許請求の範囲】
【請求項１】
処理対象フレームのブロック単位に複数の参照フレームとの間でブロック間の類似度を算出する類似度算出部と、
既に決定した処理対象フレームのブロックに対する類似ブロックの参照フレームに関する情報を記憶する決定済み参照フレームデータメモリと、
処理対象フレームにおけるブロックごとに、前記決定済み参照フレームデータメモリに記憶された既に決定した処理対象フレームのブロックに対する類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームに対する、前記類似ブロックを探索するフレームの順番を決定する探索順決定部と、
決定した探索するフレームの順番にしたがって選択した前記参照フレームにおいて、前記類似度が所定の閾値を満たすブロックを探索する探索部と、を備え、
前記探索順決定部は、
前記処理対象フレームにおけるブロックごとに、前記処理対象フレームにおいて既に参照フレームにおける類似ブロックが決定されているブロックの参照フレームのうち、参照数が多い参照フレームの優先順位が高くなるように探索順番を決定することを特徴とする動きベクトル検出装置。
【請求項２】
前記探索順決定部は、前記処理対象フレームに参照フレームが決定したブロックが無い場合、前のフレームの同位置周囲のブロックの参照先フレームの参照数が多い参照フレームの優先順位が高くなるように探索順番を決定することを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項３】
処理対象フレームにおけるブロックごとに、複数の参照フレームの中から類似度の高い類似ブロックを検出する動きベクトル検出方法であって、
前記処理対象フレームにおけるブロックごとに、前記処理対象フレームにおいて既に参照フレームにおける類似ブロックが決定されているブロックの参照フレームのうち、参照数が多い参照フレームの優先順位が高くなるように探索順番を決定し、
決定した探索するフレームの順番にしたがって選択した前記参照フレームのブロックごとに前記類似度を算出し、
算出した類似度が所定の閾値を満たした時点で探索を停止して、前記類似度が前記所定の閾値を満たすブロックを類似ブロックとして決定する、ことを特徴とする動きベクトル検出方法。
【請求項４】
コンピュータが、
処理対象フレームにおけるブロックごとに、前記処理対象フレームにおいて既に参照フレームにおける類似ブロックが決定されているブロックの参照フレームのうち、参照数が多い参照フレームの優先順位が高くなるように探索順番を決定し、
決定した探索するフレームの順番にしたがって選択した前記参照フレームのブロックごとに類似度を算出し、
算出した類似度が所定の閾値を満たした時点で探索を停止して、前記類似度が前記所定の閾値を満たすブロックを類似ブロックとして決定する、ように動作させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像符号化を行うために動きベクトル検出装置、動きベクトル検出方法およびプログラムに関する。
【背景技術】
【０００２】
動画像データはデータ量が大きいため、送信装置から受信装置へ伝送される際、あるいは記憶装置に格納される際には、圧縮符号化処理が施されることが多い。代表的な動画像の圧縮符号化方式として、ISO/IEC(International Standardization Organization／International Electrotechnical Commission)で策定されたMPEG(Moving Picture Experts Group)-2/MPEG-4が広く利用されている。また、ITU(国際電気通信連合)とISO/IECのMPEGによって策定された、H.264/AVC(Advanced Video Coding)が知られている。
【０００３】
これらの圧縮符号方式は、動き補償フレーム間予測と直交変換とを組み合わせたハイブリッド符号化方式である。動き補償フレーム間予測では、符号化処理対象のフレームを横ｍ画素、縦ｎ画素からなるブロックに分割し、各ブロック（符号化ブロック）と最も類似するブロック（参照ブロック）を参照フレームの中から検出する。そして、符号化ブロックを再現するための情報として参照ブロックの位置（動きベクトル）と符号化ブロックと参照ブロックの差分画像（差分ブロック）を符号化することで、符号化ブロックそのものを直接符号化する場合よりも情報量を大幅に削減する。動き補償フレーム間予測を用いるためには、各符号化ブロックに対して、それぞれ動きベクトルを検出する必要がある。
【０００４】
動きベクトル検出処理では、候補となる各動きベクトルにおいて、評価値を計算し、もっとも小さい評価値を与える点(予測画像が処理対象ブロックともっとも似ている点)を動きベクトルとして算出する。評価値としては一般的にＳＡＤ（差分絶対値和）が用いられる。
【０００５】
動きベクトル検出処理に必要な演算量は膨大で、動画像符号化処理全体の演算量に対して多くを占めるため、演算量を削減した処理方式が望まれる。そこで、動きベクトル検出処理に閾値による打ち切り処理を設けることで演算量を削減することが知られている。動きベクトルの各候補に対して順次ＳＡＤを計算していくが、途中で閾値より小さいＳＡＤとなる動きベクトル候補が見つかった時点で残りの候補に対するＳＡＤ計算をやめ、閾値より小さいＳＡＤを与える動きベクトル候補を動きベクトルとして算出する。
【０００６】
ところで、ＭＰＥＧ２やＨ．２６４／ＡＶＣでは、複数の参照フレームの中から参照ブロックを選択することが許されている。例えば、Ｈ．２６４／ＡＶＣでは最大１５枚の参照フレームの中からブロックごとに最適な参照フレームを選択することが許されている。そのため、Ｈ．２６４／ＡＶＣでの動きベクトル検出処理では、複数の参照フレームの中から、また、参照フレームごとに数多く存在する動きベクトル候補の中から最適な動きベクトルを決定する必要があり、動きベクトル検出処理に必要な演算量がさらに膨大になる。
【０００７】
閾値より小さいＳＡＤとなる動きベクトル候補が見つかった時点で残りの候補に対するＳＡＤ計算をやめ、閾値より小さいＳＡＤを与える動きベクトル候補を動きベクトルとする方法を使用する場合でも、参照フレームが複数になると演算量が増加する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００１−１４５１０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
そのため、複数の参照フレームを対象とした動きベクトル検出において、動きベクトル検出の演算量を削減しながら、画質を落とさず適切な参照フレームを選択することができることが求められている。
【００１０】
実施形態によれば、動きベクトル検出の演算量を削減しても、適切な参照フレームを選択することができる。
【課題を解決するための手段】
【００１１】
本発明の第１の観点によれば、ブロック間の類似度を算出する類似度算出部と、既に決定した類似ブロックの参照フレームに関する情報を記憶する決定済み参照フレームデータメモリと、処理対象フレームにおけるブロックごとに、決定済み参照フレームデータメモリに記憶された既に決定した類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームの中から、類似ブロックを探索する順番を決定する探索順決定部と、決定した順番にしたがって選択した参照フレームにおいて、類似度が所定の閾値を満たすブロックを探索する探索部と、を備える動きベクトル検出装置が提供される。
【００１２】
また、本発明の第２の観点によれば、処理対象フレームにおけるブロックごとに、複数の参照フレームの中から類似度のもっとも高い類似ブロックを検出する動きベクトル検出方法であって、処理対象フレームにおけるブロックごとに、このブロック以外のブロックに関して既に決定した類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームの中から、類似ブロックを探索する順番を決定し、決定した順番にしたがって選択した参照フレームのブロックごとに類似度を算出し、算出した類似度が所定の閾値を満たした時点で探索を停止して、類似度が所定の閾値を超えたブロックを類似ブロックとして決定する動きベクトル検出方法が提供される。
【００１３】
また、本発明の第３の観点によれば、コンピュータが、処理対象フレームにおけるブロックごとに、このブロック以外のブロックに関して既に決定した類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームの中から、類似ブロックを探索する順番を決定し、決定した順番にしたがって選択した参照フレームのブロックごとに類似度を算出し、算出した類似度が所定の閾値を超えた時点で探索を停止して、類似度が前記所定の閾値を満たすブロックを類似ブロックとして決定する、ように動作させるプログラムが提供される。
【発明の効果】
【００１４】
実施形態によれば、類似ブロックの探索を始めて早い段階で最適な参照フレームを見つけることができ、演算量を削減できる。
【図面の簡単な説明】
【００１５】
【図１】図１は、実施形態の符号化装置の概略構成を示す図である。
【図２】図２は、動きベクトル検出処理を示すフローチャートである。
【図３】図３は、映像信号データの一連のフレームにおける処理対象フレームを示す図である。
【図４】図４は、類似していると判定する時の閾値の決定方法を説明する図である。
【図５】図５は、参照フレームの選択順の決定方法の１つを説明する図である。
【図６】図６は、前側周辺ブロックについて決定された参照フレームの例を示す図である。
【図７】図７は、より多くの個数の前側周辺ブロックから参照フレームを決定する例を示す図である。
【図８】図８は、処理対象フレームで、選択された参照フレームが１つ前のフレームである場合の探索範囲の例を示す図である。
【図９】図９は、探索範囲における探索対象点の選択順を示す図である。
【発明を実施するための形態】
【００１６】
図１は、実施形態の符号化装置の概略構成を示す図である。
【００１７】
実施形態の符号化装置は、符号化部１と、フレームメモリ２と、信号入力部３と、を有する。実施形態の符号化装置は、例えば、プロセッサやＤＳＰおよびメモリなどで構成されるコンピュータを、インストールしたプログラムで動作させることにより実現される。
【００１８】
信号入力部３は、外部から順次供給される映像信号データを受け取り、フレームメモリ２に供給する。フレームメモリ２は、受け取った映像信号データを記憶する。フレームメモリ２は、映像信号データのうち符号化処理に使用する複数のフレームのデータを記憶する容量を有し、符号化処理で使用する必要のなくなったフレームのデータを廃棄して処理に使用する新しいフレームのデータに随時置き換える。符号化部１は、フレームメモリ２に記憶された複数のフレームのデータにアクセスし、映像信号データの符号化処理を行い、符号化した符号化データを出力する。  
符号化部１は、動きベクトル検出部１０と、動きベクトル検出部１０の検出した類似ブロックに関する情報を利用して、直交変換の一種であるＤＣＴなどの変換符号化処理を行う変換符号化部と、を有する。言い換えれば、実施形態の符号化装置は、動き補償フレーム間予測と変換符号化を組み合わせたハイブリッド符号化方式で符号化処理を行う。変換符号化部の処理については広く知られているので、ここでは説明は省略する。
【００１９】
動きベクトル検出部１０は、類似度算出部１１と、探索部１２と、決定済み参照フレームデータメモリ１３と、探索順決定部１４と、を有する。
【００２０】
類似度算出部１１は、ブロック間のＳＡＤ（差分絶対値和）を算出する。この処理については広く知られているので、説明は省略する。
【００２１】
探索部１２は、処理対象フレームにおけるブロックごとに、複数の参照フレームのうちから類似ブロックを探索し、類似ブロックの属する参照フレームの識別番号およびその参照フレームにおける類似ブロックの座標を出力する。
【００２２】
決定済み参照フレームデータメモリ１３は、探索部１２が決定した類似ブロックの参照フレームに関する情報を記憶する。
【００２３】
探索順決定部１４は、処理対象フレームにおけるブロックごとに、決定済み参照フレームデータメモリ１３に記憶された既に決定した類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームの中から、類似ブロックを探索する順番を決定する。
【００２４】
探索部１２は、探索順決定部１４が決定した順番にしたがって参照フレームを選択し、選択した参照フレームにおいて、類似度が所定の閾値を超えるブロックを探索する。
【００２５】
次に、本実施形態の符号化装置の動画像符号化における動きベクトル検出処理を説明する。
【００２６】
図２は、動きベクトル検出処理を示すフローチャートである。
【００２７】
ここでは、図３に示すように映像信号データの一連のフレーム＃０〜＃５があり、＃３のフレーム２２が処理対象フレームである。前述のように、Ｈ．２６４／ＡＶＣでは、前述のように最大１５枚の参照フレームを利用できる。図２は、処理対象フレームである＃３のフレーム２２内の１つのブロックの動きベクトル検出処理を示している。
【００２８】
ステップＳ０では、変数ｍｉｎｉＳＡＤを最大値ＭＡＸで初期化する。最大値ＭＡＸは、ブロック間のＳＡＤ（差分絶対値和）がとり得る最大値より大きな値であればよい。
【００２９】
ステップＳ１では、類似していると判定する時の閾値Ｔｈを設定する。閾値Ｔｈの決定方法は、各種あり得る。
【００３０】
第１の方法は、既に動きベクトル検出が完了している過去のフレームにおいて、各ブロックの動きベクトル検出で得られた動きベクトルに対応するＳＡＤの平均値を１．１倍した値をＴｈと設定する。
【００３１】
第２の方法は、処理対象フレーム２２の既に動きベクトル検出が完了している周辺ブロックのＳＡＤの平均値を１．１倍した値をＴｈと設定する。
【００３２】
図４は、これらの方法を説明する図である。図４において、対象フレーム２２のブロック３０について動きベクトルを検出する場合、対象フレーム２２の前のフレーム２１以前のフレームでは、すべてのブロックについて動きベクトル検出が完了して、ＳＡＤが算出されている。第１の方法では、前のフレームにおけるすべてのブロックの平均値を算出して、それを１．１倍する。ＳＡＤの平均値の算出は、例えば累積加算器を使用して行う。なお、対象フレーム２２のブロック３０より前のブロックについても動きベクトル検出が完了して、ＳＡＤが算出されているので、それらを含めるようにしてもよい。
【００３３】
第２の方法では、対象フレーム２２において、動きベクトルを検出するブロック３０に隣接する前側のブロックＡ，Ｂ，Ｃ，Ｄについて動きベクトル検出が完了して、ブロックＡ，Ｂ，Ｃ，ＤのＳＡＤが算出されている。ここでは、周辺ブロックＡ，Ｂ，Ｃ，Ｄは、ブロック３０に対して前側周辺ブロックと称する。第２の方法では、前側周辺ブロックＡ，Ｂ，Ｃ，ＤのＳＡＤの平均値を算出し、その値を１．１倍した値をＴｈと設定する。この場合、前側周辺ブロックＡ，Ｂ，Ｃ，ＤのＳＡＤを記憶しておく必要があり、例えば、ブロック２ライン分のＳＡＤを記憶するメモリを設け、随時更新する。なお、図４では、前側周辺ブロックが４個である場合を示したが、個数は特に制限されない。
【００３４】
図２に戻り、ステップＳ２では、複数の参照フレームについて、選択する順番を決定する。
【００３５】
図５は、参照フレームの選択順の決定方法の１つを説明する図である。
【００３６】
１フレームの中でのブロックの動きベクトルの検出は、ラスタスキャン順に行われる。図５では、処理対象フレーム２２の画面で、上端の行から下の行に向かって、行内の各ブロックは左側から右側のブロックの順で動きベクトル検出が行われる。したがって、図５の（Ａ）に示すように、ブロック３０の動きベクトルを検出する時には、周辺ブロックＡ，Ｂ，Ｃ，Ｄは、動きベクトルおよび参照フレームともすでに決定している。ここでは、周辺ブロックＡ，Ｂ，Ｃ，Ｄは、ブロック３０に対して前側周辺ブロックと称する。
【００３７】
参照フレームの選択順は、前側周辺ブロックＡ，Ｂ，Ｃ，Ｄにおける参照フレームに基づいて決定する。例えば、参照フレームの選択順は、前側周辺ブロックＡ，Ｂ，Ｃ，Ｄについて決定された参照フレームのうちの多い順とする。
【００３８】
図６は、前側周辺ブロックＡ，Ｂ，Ｃ，Ｄについて決定された参照フレームの例を示す。なお、処理対象フレームは＃３である。この例では、ブロックＡが参照フレーム＃１、ブロックＢが参照フレーム＃１、ブロックＣが参照フレーム＃１、ブロックＤが参照フレーム＃２、であるように決定されている。この場合、もっとも多い参照フレーム＃１が最初に選択され、２番目にフレーム＃２が選択されるように決定される。なお、処理対象フレームは＃３である。
【００３９】
図５の（Ｂ）に示すように、動きベクトルを検出するブロック３０が、処理対象フレーム２２の上端、左端、右端に位置する場合、前側周辺ブロックの一部あるいはすべてが存在しない場合があり得る。その場合、存在する前側周辺ブロックのうちで決定されている参照フレームの多数決をとって参照フレームの選択順を決定する。また、動きベクトルを検出するブロック３０が、処理対象フレーム２２の左上端に位置する場合、前側周辺ブロックは存在しない。この場合は、前のフレームの対応する位置（左上端）のブロックの後ろ側も含めた周辺ブロックの参照フレームから決定してもよい。
【００４０】
なお、図５および図６では、前側周辺ブロックが４個である場合を示したが、参照フレームを決定するためのブロックは、特に制限されず、より多くの個数の前側周辺ブロックから参照フレームを決定してもよい。例えば、図７に示すように、処理対象フレームにおいて、動きベクトルを検出するブロック３０に対してスキャンの前側に位置するブロックで既に決定されている参照フレームの多い順に決定してもよい。また、図５の（Ａ）で、前側周辺ブロックのうちのブロックＡの参照フレームのみで決定してもよい。前側周辺ブロックで同じ最大数の参照フレームが存在する場合には、例えばブロックＡが選択している参照フレームを選択する。ブロックＡのみから参照フレームを選択する場合、直前に処理をしたブロックＡの参照フレームを記憶するだけでよいので、参照フレームの選択処理が簡単になる。また、動きベクトルを検出するブロック３０からの距離が近いブロックＡおよびＢが選択する参照フレームを優先して参照フレームを選択するようにしてもよい。この場合、ブロックＡおよびＢについては、ブロックＣおよびＤの参照フレームの２倍重み付けを行うことなどが考えられる。
【００４１】
ステップＳ３では、図３に示したような複数の参照フレームの候補＃０〜＃５の中から、ステップＳ２で決定した選択順にしたがって、１つの参照フレームを選択する。
【００４２】
ステップＳ４では、探索対象点を選択する。ここでは一例としてフルサーチ法を用いた場合で説明するが、本発明では探索対象点の設定方法はフルサーチ法に限らず、スリーステップ法、ヘキサゴンサーチ法、勾配法、階層探索法など様々な方法を選んで用いることができる。
【００４３】
図８は、処理対象フレーム２２がフレーム＃３で、選択された参照フレーム２１がフレーム＃２である場合の探索範囲の例を示している。参照フレーム２１のブロック４０は、動きベクトルを検出するブロック３０の処理対象フレーム２２における座標と同じ座標のブロックである。そして、参照番号４１で示す範囲が探索範囲であり、横幅がＨ画素で、縦幅がＶ画素である。ブロック４０は、探索範囲４１の中央に位置する。
【００４４】
図９は、探索範囲４１における探索対象点の選択順を示している。１回目のステップＳ４では、探索範囲４１の左上端のブロック５０を動きベクトル候補として選択する。ステップＳ４で２回目の選択を行う場合には、ブロック５０を右方向に１画素ずらしたブロック５１を動きベクトル候補として選択する。ステップＳ４で３回目以降の選択を行う場合には、ブロック５０を右方向に１画素ずらしたブロックを動きベクトル候補として順次選択し、右上端のブロック６１まで選択する。その後、左端に戻り、左上端のブロック５０を１画素下方向にずらしたブロックを動きベクトル候補として選択する。その後、順次右方向に１画素ずらしたブロックを動きベクトル候補として選択し、右端まで選択したら、左端に戻り１画素下方向にずらして選択し、同様の選択を繰り返す。そして、最終行では、ブロック６２を選択し、その後順次右方向に１画素ずらしたブロックを動きベクトル候補として選択し、右端のブロック６３まで選択したら終了する。以上のように、ステップＳ４では、ステップを繰り返すごとに、ラスタスキャンのようにブロックを選択する。上記のように、探索範囲４１は、Ｈ×Ｖ画素であるから、探索範囲４１のすべてのブロックを選択するには、ステップＳ４をＨ×Ｖ回繰り返すことになる。
【００４５】
ステップＳ５では、ステップＳ４で選択された点のブロックに対してＳＡＤ（差分絶対和）を計算する。ＳＡＤの計算式を次の式に示す。
【００４６】
【数１】
0005754120.tif 000002
【００４７】
ここで、ｃ（ｉ，ｊ）は処理対象ブロックの水平方向ｉ番目、垂直方向ｊ番目の位置に存在する画素の値を示し、ｒ（ｘ＋ｉ，ｙ＋ｊ）は参照フレームにおける処理対象ブロックの（ｉ，ｊ）の位置の画素から水平方向ｘ、垂直方向ｊだけ離れた位置の画素の値を表す。また、ｎは動きベクトルを検出するブロック（処理対象ブロック）の水平方向の画素数、ｍは処理対象ブロックの垂直方向の画素数である。
【００４８】
ステップＳ６では、計算したＳＡＤと変数ｍｉｎｉＳＡＤを比較する。ＳＡＤ＜ｍｉｎｉＳＡＤである場合、ｍｉｎｉＳＡＤを計算したＳＡＤで置き換え、変数ＲｅｆをステップＳ３で選択した参照フレームで置き換え、変数ＶｅｃをステップＳ４で選択した動きベクトル候補の座標で置き換える。
【００４９】
ステップＳ７では、計算したＳＡＤが閾値Ｔｈ以下であるかを判定し、閾値Ｔｈ以下であればステップＳ１０に進み、閾値Ｔｈより大きければステップＳ８に進む。
【００５０】
ステップＳ８では、選択されている参照フレームについて、探索範囲４１内のすべての探索対象点でＳＡＤを計算したかどうかを判定する。ＳＡＤを計算していない探索対象点が残っている場合はステップＳ４に戻り、残っていない場合はステップＳ９に進む。
【００５１】
ステップＳ４に戻った場合には、上記のように、探索範囲４１において、探索対象点をラスタスキャンのようにずらしてブロックを選択する。
【００５２】
ステップＳ９では、すべての参照フレームについて探索処理が完了しているかを判定する。すべての参照フレームに対して探索が完了している場合はステップＳ１０に進み、探索が完了していない参照フレームが残っている場合はステップＳ３に戻る。
【００５３】
ステップＳ３に戻った場合には、上記のように、参照フレームの選択順にしたがって次の参照フレームを選択する。
【００５４】
ステップＳ１０では、保存されている変数Ｒｅｆを類似ブロックの参照フレームとして決定済み参照フレーム１３に記憶すると共に出力し、変数ＶｅｃをステップＳ４で選択した動きベクトル候補の座標として出力する。
【００５５】
以上のようにして、１ブロックの動きベクトル検出処理が完了する。
【００５６】
上記の実施形態では、探索対象点が動きベクトルとして適切かどうかの指標としてＳＡＤを用いたが、代わりに次の式ＭＡＤを用いてもよい。
【００５７】
【数２】
0005754120.tif 000003
【００５８】
また、ＳＡＤに動きベクトルの符号化コストを加算した値を用いるなどしてもよい。この場合、ステップＳ７で閾値と比較される値はＳＡＤではなく、ＭＡＤやＳＡＤに動きベクトルの符号化コストを加算した値となる。また、ステップS1で設定する閾値ＴｈはＭＡＤやＳＡＤに動きベクトルの符号化コストを加算した値に応じて設定する。
【００５９】
以上説明したように、本実施形態では、探索する参照フレームの順番を、動きベクトルを決定済みの周囲のブロックが選択している参照フレームをもとに決定することにより、最適な参照フレームの探索を動きベクトル検出処理の早い段階で行う確率を高める。したがって、閾値より小さいＳＡＤの検出タイミングを早めることができ、閾値より大きなＳＡＤとなる確率が高い参照フレームの探索を省略する可能性を高めることができ、動きベクトル検出処理の平均演算量を削減することができる。同一の被写体オブジェクトが隣接する複数のブロックにまたがって映っている場合など、隣接するブロック間では同じ参照フレームが最適な参照フレームである確率が大きいため、本実施形態の方法を用いればより早い段階で最適な参照フレーム上の動きベクトル候補を評価することができる。
【００６０】
以上、実施形態を説明したが、ここに記載したすべての例や条件は、発明および技術に適用する発明の概念の理解を助ける目的で記載されたものであり、特に記載された例や条件は発明の範囲を制限することを意図するものではなく、明細書のそのような例の構成は発明の利点および欠点を示すものではない。発明の実施形態を詳細に記載したが、各種の変更、置き換え、変形が発明の精神および範囲を逸脱することなく行えることが理解されるべきである。
【００６１】
以下、実施形態に関し、更に以下の付記を開示する。
（付記１）
ブロック間の類似度を算出する類似度算出部と、
既に決定した類似ブロックの参照フレームに関する情報を記憶する決定済み参照フレームデータメモリと、
処理対象フレームにおけるブロックごとに、前記決定済み参照フレームデータメモリに記憶された既に決定した類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームの中から、前記類似ブロックを探索する順番を決定する探索順決定部と、
決定した順番にしたがって選択した前記参照フレームにおいて、前記類似度が所定の閾値を満たすブロックを探索する探索部と、を備えることを特徴とする動きベクトル検出装置。
（付記２）
前記探索順決定部は、
前記処理対象フレームにおけるブロックごとに、前記処理対象フレームにおいて当該ブロックに隣接し且つ既に類似ブロックが決定されているブロックの参照フレームに基づいて順番を決定する付記１記載の動きベクトル検出装置。
（付記３）
前記探索順決定部は、
前記処理対象フレームにおけるブロックごとに、前記処理対象フレームに近く且つ既に類似ブロックが決定されているフレームで、当該ブロックに対応する位置のブロックの参照フレームに基づいて順番を決定する付記１記載の動きベクトル検出装置。
（付記４）
処理対象フレームにおけるブロックごとに、複数の参照フレームの中から類似度のもっとも高い類似ブロックを検出する動きベクトル検出方法であって、
前記処理対象フレームにおけるブロックごとに、当該ブロック以外のブロックに関して既に決定した類似ブロックの参照フレームに関する情報を利用して、前記複数の参照フレームの中から、前記類似ブロックを探索する順番を決定し、
決定した順番にしたがって選択した前記参照フレームのブロックごとに前記類似度を算出し、
算出した類似度が所定の閾値を満たした時点で探索を停止して、前記類似度が前記所定の閾値を満たすブロックを類似ブロックとして決定する、ことを特徴とする動きベクトル検出方法。
（付記５）
前記探索する順番の決定は、
前記処理対象フレームにおけるブロックごとに、前記処理対象フレームにおいて当該ブロックに隣接し且つ既に類似ブロックが決定されているブロックの参照フレームに基づいて順番を決定する付記４記載の動きベクトル検出方法。
（付記６）
前記探索する順番の決定は、
前記処理対象フレームにおけるブロックごとに、前記処理対象フレームに近く且つ既に類似ブロックが決定されているフレームで、当該ブロックに対応する位置のブロックの参照フレームに基づいて順番を決定する付記４記載の動きベクトル検出方法。
（付記７）
コンピュータが、
処理対象フレームにおけるブロックごとに、当該ブロック以外のブロックに関して既に決定した類似ブロックの参照フレームに関する情報を利用して、複数の参照フレームの中から、類似ブロックを探索する順番を決定し、
決定した順番にしたがって選択した前記参照フレームのブロックごとに類似度を算出し、
算出した類似度が所定の閾値を満たした時点で探索を停止して、前記類似度が前記所定の閾値を満たすブロックを類似ブロックとして決定する、ように動作させるプログラム。
【符号の説明】
【００６２】
１    符号化部
２    フレームメモリ
３    信号入力部
４    変換符号化部
１０    動きベクトル検出部
１１    類似度算出部
１２    探索部
１３    決定済み参照フレームデータメモリ
１４    探索順決定部
【図１】
0005754120.tif 000004
【図２】
0005754120.tif 000005
【図３】
0005754120.tif 000006
【図４】
0005754120.tif 000007
【図５】
0005754120.tif 000008
【図６】
0005754120.tif 000009
【図７】
0005754120.tif 000010
【図８】
0005754120.tif 000011
【図９】
0005754120.tif 000012