(57)【要約】【課題】本発明は、画像ブロックの動きベクトルの検出処理時間の短縮を実現する新たな動きベクトル検出技術の提供を目的とする。【解決手段】先ず最初に、検出対象となる画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする減ビット画像を生成する。続いて、減ビット画像を処理対象としてＳＡＤ値を算出し、それらの中で最小値となるものを抽出する。続いて、抽出した最小ＳＡＤ値を基準にして、減ビット画素値でのＳＡＤ値を評価することで、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定する。続いて、真のＳＡＤ値の算出対象となる画像ブロックを処理対象として、真の画素値でのＳＡＤ値を算出し、それらの中で最小値となるものを特定する。最後に、特定した真のＳＡＤ値の算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する。【選択図】図１
2005260392.tif 000002
【特許請求の範囲】
【請求項１】
画像ブロック間でＳＡＤ値を算出し、それに基づいて、画像ブロックの動きベクトルを検出する動きベクトル検出方法であって、
動きベクトルの検出対象となる画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、該画像を減ビット画像に変換する過程と、
上記減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出し、それらの中で最小値となるものを抽出する過程と、
上記最小ＳＡＤ値を基準にして、上記算出したＳＡＤ値を評価することで、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定する過程と、
上記真のＳＡＤ値の算出対象となる画像ブロックを処理対象として、画像ブロック間で真の画素値でのＳＡＤ値を算出し、それらの中で最小値となるものを特定する過程と、
上記特定した真のＳＡＤ値の算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する過程とを備えることを、
特徴とする動きベクトル検出方法。
【請求項２】
請求項１に記載の動きベクトル検出方法において、
上記判定する過程では、
Ｘmin ≦Ｘj ≦Ｘmin ＋２×Ｎ
ただし、Ｘj   ：判定対象の画像ブロックの持つ減ビット画像
の画素値でのＳＡＤ値
Ｘmin ：減ビット画像の画素値でのＳＡＤ値の最小値
Ｎ    ：画像ブロック内の画素数
に基づいて、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定することを、
特徴とする動きベクトル検出方法。
【請求項３】
画像ブロック間でＳＡＤ値を算出し、それに基づいて、画像ブロックの動きベクトルを検出する動きベクトル検出装置であって、
動きベクトルの検出対象となる画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、該画像を減ビット画像に変換する手段と、
上記減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出し、それらの中で最小値となるものを抽出する手段と、
上記最小ＳＡＤ値を基準にして、上記算出したＳＡＤ値を評価することで、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定する手段と、
上記真のＳＡＤ値の算出対象となる画像ブロックを処理対象として、画像ブロック間で真の画素値でのＳＡＤ値を算出し、それらの中で最小値となるものを特定する手段と、
上記特定した真のＳＡＤ値の算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する手段とを備えることを、
特徴とする動きベクトル検出装置。
【請求項４】
請求項３に記載の動きベクトル検出装置において、
上記判定する手段は、
Ｘmin ≦Ｘj ≦Ｘmin ＋２×Ｎ
ただし、Ｘj   ：判定対象の画像ブロックの持つ減ビット画像
の画素値でのＳＡＤ値
Ｘmin ：減ビット画像の画素値でのＳＡＤ値の最小値
Ｎ    ：画像ブロック内の画素数
に基づいて、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定することを、
特徴とする動きベクトル検出装置。
【請求項５】
ＳＥＡ探索法に基づいて、画像ブロックの動きベクトルを検出する動きベクトル検出方法であって、
動きベクトルの検出対象となる画像を変換対象として、隣接画素同士をまとめることで、該画像を粗画像に変換する過程と、
上記粗画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、上記粗画像を減ビット画像に変換する過程と、
上記減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出する過程と、
上記算出したＳＡＤ値と、上記除算に用いた数値と、上記粗画像におけるブロック内画素数と、真のＳＡＤ値の暫定最小値とに基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定する過程と、
上記省略できない画像ブロックを処理対象として、真の画素値でのＳＡＤ値を算出し、それに応じて上記暫定最小値を更新するのか否かを判断して、更新する必要がある場合には、それを更新する過程と、
上記暫定最小値が最小値として確定するときに、その算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する過程とを備えることを、
特徴とする動きベクトル検出方法。
【請求項６】
請求項５に記載の動きベクトル検出方法において、
上記判定する過程では、
ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ
ただし、ＸＣj     ：減ビット画像の画素値でのＳＡＤ値
Ｑ        ：除算に用いた数値
ＮＣ      ：粗画像におけるブロック内画素数
ＳＡＤcand：真のＳＡＤ値の暫定最小値
に基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定することを、
特徴とする動きベクトル検出方法。
【請求項７】
ＳＥＡ探索法に基づいて、画像ブロックの動きベクトルを検出する動きベクトル検出装置であって、
動きベクトルの検出対象となる画像を変換対象として、隣接画素同士をまとめることで、該画像を粗画像に変換する手段と、
上記粗画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、上記粗画像を減ビット画像に変換する手段と、
上記減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出する手段と、
上記算出したＳＡＤ値と、上記除算に用いた数値と、上記粗画像におけるブロック内画素数と、真のＳＡＤ値の暫定最小値とに基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定する手段と、
上記省略できない画像ブロックを処理対象として、真の画素値でのＳＡＤ値を算出し、それに応じて上記暫定最小値を更新するのか否かを判断して、更新する必要がある場合には、それを更新する手段と、
上記暫定最小値が最小値として確定するときに、その算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する手段とを備えることを、
特徴とする動きベクトル検出装置。
【請求項８】
請求項７に記載の動きベクトル検出装置において、
上記判定する手段は、
ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ
ただし、ＸＣj     ：減ビット画像の画素値でのＳＡＤ値
Ｑ        ：除算に用いた数値
ＮＣ      ：粗画像におけるブロック内画素数
ＳＡＤcand：真のＳＡＤ値の暫定最小値
に基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定することを、
特徴とする動きベクトル検出装置。
【請求項９】
請求項１、２、５又は６に記載の動きベクトル検出方法の実現に用いられる処理をコンピュータに実行させるための動きベクトル検出プログラム。
【請求項１０】
請求項１、２、５又は６に記載の動きベクトル検出方法の実現に用いられる処理をコンピュータに実行させるための動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル動画像の符号化で用いられる画像ブロックの動きベクトルを検出する動きベクトル検出方法及びその装置と、その動きベクトル検出方法の実現に用いられる動きベクトル検出プログラム及びそのプログラムを記録したコンピュータ読み取り可能な記録媒体とに関する。
【背景技術】
【０００２】
従来の動画像圧縮符号化方式（ＭＰＥＧ−１，ＭＰＥＧ−２，ＭＰＥＧ−４等）では、動画像フレーム間の動きベクトル検出を行う。
【０００３】
この動きベクトル検出では、ある画像フレーム（以下、画像フレーム１と呼ぶ）内のあるブロック（以下、ブロックＢi と呼ぶ）に対し、別の画像フレーム（以下、画像フレーム２と呼ぶ）に含まれるブロックの中で最も類似度の高いブロック（以下、ブロックＢ0 と呼ぶ）を求め、ブロックＢi とブロックＢ0 との座標変分を求める処理を行う。
【０００４】
ブロックＢ0 を求めるには、画像フレーム２からあるブロック（以下、ブロックＢj と呼ぶ）を取り出してはブロックＢi との類似度を算出し、その算出値が最高か否かを判定することを繰り返す、というブロックマッチング処理が行われる。
【０００５】
一般に、類似度にはＳＡＤ（Sum of Absolute Difference）を用いる。ＳＡＤは、ブロックＢi とブロックＢj がともにＮ個の画素を含む場合、ブロックＢi 内の画素値Ｉa とブロックＢj 内の画素値Ｊa との絶対差｜Ｉa −Ｊa ｜により、Σa ｜Ｉa −Ｊa ｜で計算される。ここでΣa は、ブロック内の全画素を参照するように添字ａを変化させて積算することを意味する。ＳＡＤを１回求めるのには、Ｎ回の絶対差とＮ−１回の加算とが必要である。類似度にＳＡＤを用いた場合、最高の類似度を持つブロックＢ0 は最小のＳＡＤを持つブロックである。
【０００６】
ＳＡＤを用いてブロックＢ0 を求めるには、画像フレーム２からブロックＢj を取り出し、ブロックＢi とブロックＢj とのＳＡＤ（以下、ＳＡＤj と呼ぶ）を計算し、探索中の暫定最小値ＳＡＤcandと比較して、
ＳＡＤj ＝Σa ｜Ｉa −Ｊa ｜＜ＳＡＤcand              （１）式
ならばＳＡＤcandをＳＡＤj で置き換え、ブロックＢj の座標を記録する。この処理を全てのブロックＢj について終えた時のＳＡＤcandが最小ＳＡＤ値のＳＡＤmin となる。
【０００７】
通常、画素値は８ビットのデータ（値域は０から２５５）として表される。ゆえに、絶対差｜Ｉa −Ｊa ｜は８ビットの演算器で求められ、その積算値であるＳＡＤj はブロック内画素数Ｎで決まるビット数にて表される。
【０００８】
この動きベクトル検出を効率的に行う手法としてＳＥＡ探索法が知られている（例えば、非特許文献１参照）。
【０００９】
ＳＥＡ探索法では、画像フレーム内の隣接画素同士をまとめて粗い画素（粗い画像）を作り、その画素値でＳＡＤを求め、それを下限閾値として、真の画素値によるＳＡＤ計算を省略するものである。画素を粗くすることでブロック内画素数が減るため、粗い画素値でのＳＡＤ計算にかかる演算量は真の画素値でのそれよりも少ない。それゆえ、ＳＡＤ計算全体に要する演算量を削減できる効果が見込まれる。
【非特許文献１】"W.Li and E.Sarari, Successive Elimination Algorithm for Motion Estimation, IEEE Trans. Image Proc., vol.4, pp.105-107, Jan.1995”
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述したことから分かるように、動きベクトル検出では、一つのブロックＢi に対してでもブロックＢ0 を求めるのにＳＡＤを多数回計算せねばならない。さらに、この処理は、画像フレーム１内の全ブロックに対して行わねばならず、膨大な回数のＳＡＤ計算、すなわち、絶対差とその加算という演算を要する。こうした処理を現実的な量の演算リソースで処理するには非常に多くの処理時間がかかることになる。
【００１１】
処理時間を短縮する方法の一つとして、画素値Ｉa およびＪa を表現するビット数を減らし、一定のビット幅の演算器で一度に演算できる画素数を増やすことで、処理効率の向上を図る方法が考えられる。
【００１２】
しかし、画素値Ｉa およびＪa のそれぞれのビット数を減らして値Ｙa およびＺa とし、単純に、これを用いて、（１）式と同様に
Σa ｜Ｙa −Ｚa ｜≦Ｘmin 
という更新式に従って、最小ＳＡＤ値“Ｘmin ”を持つブロックを見つけたとしても、それが必ずしも真の最小ＳＡＤ値“ＳＡＤmin ”を持つブロックＢ0 であるとは限らない。
【００１３】
それゆえ、ビット数を減らした画素値でＳＡＤ計算を行い、処理の効率化を図る試みはそのままではうまくいかないことになる。この点については、ＳＥＡ探索法でも同様である。
【００１４】
本発明はかかる事情に鑑みてなされたものであって、画像ブロックの動きベクトルの検出処理時間の短縮を実現する新たな動きベクトル検出技術の提供を目的とする。
【課題を解決するための手段】
【００１５】
〔１〕第１の構成
上記目的を達成するために、本発明の動きベクトル検出装置は、画像ブロック間でＳＡＤ値を算出し、それに基づいて、画像ブロックの動きベクトルを検出する処理を行うときにあって、（イ）動きベクトルの検出対象となる画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、動きベクトルの検出対象となる画像を減ビット画像に変換する変換手段と、（ロ）減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出し、それらの中で最小値となるものを抽出する抽出手段と、（ハ）抽出手段の抽出した最小ＳＡＤ値を基準にして、減ビット画像の画素値でのＳＡＤ値を評価することで、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定する判定手段と、（ニ）真のＳＡＤ値の算出対象となる画像ブロックを処理対象として、画像ブロック間で真の画素値でのＳＡＤ値を算出し、それらの中で最小値となるものを特定する特定手段と、（ホ）特定手段の特定した真のＳＡＤ値の算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する検出手段とを備えるように構成する。
【００１６】
以上の各処理手段が動作することで実現される本発明の動きベクトル検出方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどのような適当な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
【００１７】
このように構成される本発明の動きベクトル検出装置では、先ず最初に、動きベクトルの検出対象となる画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、動きベクトルの検出対象となる画像を減ビット画像に変換する。
【００１８】
続いて、このようにして得た減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出し、それらの中で最小値となるものを抽出する。
【００１９】
続いて、この抽出した最小ＳＡＤ値（減ビット画像の画素値で得たもの）を基準にして、減ビット画像の画素値でのＳＡＤ値を評価することで、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定する。
【００２０】
具体的には、判定対象の画像ブロックの持つ減ビット画像の画素値でのＳＡＤ値をＸj 、減ビット画像の画素値でのＳＡＤ値の最小値をＸmin 、画像ブロック内の画素数をＮで表すならば、
Ｘmin ≦Ｘj ≦Ｘmin ＋２×Ｎ
という評価式に基づいて、真のＳＡＤ値の算出対象となる画像ブロックであるのか否かを判定するのである。
【００２１】
続いて、このようにして得た真のＳＡＤ値の算出対象となる画像ブロックを処理対象として、画像ブロック間で真の画素値でのＳＡＤ値を算出し、それらの中で最小値となるものを特定する。
【００２２】
そして、最後に、この特定した真のＳＡＤ値の算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する。
【００２３】
このようにして、本発明によれば、２つの画像フレーム間の動きベクトルを検出する方法として、画素値を表現するビット数を減じた計算が主体となることから、一定のビット幅の演算リソースでの処理効率を向上させることができるようになる。
【００２４】
〔２〕第２の構成
上記目的を達成するために、本発明の動きベクトル検出装置は、ＳＥＡ探索法に基づいて画像ブロックの動きベクトルを検出する処理を行うときにあって、（イ）動きベクトルの検出対象となる画像を変換対象として、隣接画素同士をまとめることで、動きベクトルの検出対象となる画像を粗画像に変換する変換手段と、（ロ）粗画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、粗画像を減ビット画像に変換する変換手段と、（ハ）減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出する算出手段と、（ニ）算出手段の算出したＳＡＤ値と、減ビット画像を得るための除算に用いた数値と、粗画像におけるブロック内画素数と、真のＳＡＤ値の暫定最小値とに基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定する判定手段と、（ホ）真の画素値でのＳＡＤ値の算出を省略できない画像ブロックを処理対象として、真の画素値でのＳＡＤ値を算出し、それに応じて真のＳＡＤ値の暫定最小値を更新するのか否かを判断して、更新する必要がある場合には、それを更新する更新手段と、（ヘ）真のＳＡＤ値の暫定最小値が最小値として確定するときに、その算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する検出手段とを備えるように構成する。
【００２５】
以上の各処理手段が動作することで実現される本発明の動きベクトル検出方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどのような適当な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
【００２６】
このように構成される本発明の動きベクトル検出装置では、先ず最初に、動きベクトルの検出対象となる画像を変換対象として、隣接画素同士をまとめることで、動きベクトルの検出対象となる画像を粗画像に変換する。
【００２７】
続いて、このようにして得た粗画像の画素値を１以上の数で除算し、その商の整数部を新たな画素値とする画像を生成することで、粗画像を減ビット画像に変換する。
【００２８】
続いて  このようにして得た減ビット画像を処理対象として、画像ブロック間でＳＡＤ値を算出する。
【００２９】
続いて、この算出したＳＡＤ値（減ビット画像の画素値で得たもの）と、減ビット画像を得るための除算に用いた数値と、粗画像におけるブロック内画素数と、真のＳＡＤ値の暫定最小値とに基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定する。
【００３０】
具体的には、判定対象の画像ブロックの持つ減ビット画像の画素値でのＳＡＤ値をＸＣj 、減ビット画像を得るための除算に用いた数値をＱ、粗画像におけるブロック内画素数をＮＣ、真のＳＡＤ値の暫定最小値をＳＡＤcandで表すならば、
ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ
という評価式に基づいて、真の画素値でのＳＡＤ値の算出を省略できる画像ブロックであるのか否かを判定するのである。
【００３１】
続いて、このようにして得た真の画素値でのＳＡＤ値の算出を省略できない画像ブロックを処理対象として、真の画素値でのＳＡＤ値を算出し、それに応じて真のＳＡＤ値の暫定最小値を更新するのか否かを判断して、更新する必要がある場合には、それを更新する。
【００３２】
そして、最後に、真のＳＡＤ値の暫定最小値が最小値として確定するときに、その算出元となった画像ブロックに基づいて、画像ブロックの動きベクトルを検出する。
【００３３】
このようにして、本発明によれば、ＳＥＡ探索法に基づいて画像ブロックの動きベクトルを検出する処理を行うときにあって、２つの画像フレーム間の動きベクトルを検出する方法として、画素値を表現するビット数を減じた計算が主体となることから、一定のビット幅の演算リソースでの処理効率を向上させることができるようになる。
【００３４】
〔３〕本発明の理論的根拠
〔３−１〕第１の構成の理論的根拠
本発明の第１の構成では、従来技術の問題を解決するために、ビット数を減じた画素値で得られるＳＡＤ値と、真の画素値により得られるＳＡＤ値との間にある関係を導出し、これを利用することで動きベクトル検出処理を効率化するという方法を採っている。
【００３５】
まず、画素値Ｉa およびＪa （ともに非負の整数）を、それぞれ定数Ｑ（１以上の実数）で除算し、その整数部を取り出してＵa およびＶa とする。以後、ビット数削減のこのやり方を、定数Ｑで減ビットする、と呼ぶことにする。
【００３６】
適当な定数Ｑを用いれば、値Ｕa およびＶa は、それぞれ、真の画素値Ｉa およびＪa よりも少ないビット数で表現できる。
【００３７】
このとき、後述するように、
｜Ｉa −Ｊa ｜−Ｑ≦Ｑ×｜Ｕa −Ｖa ｜≦｜Ｉa −Ｊa ｜＋Ｑ      （２）式
が成り立つ。
【００３８】
この（２）式をΣa で積算すると、
Σa ｜Ｉa −Ｊa ｜−Ｑ×Ｎ≦Ｑ×Σa ｜Ｕa −Ｖa ｜
≦Σa ｜Ｉa −Ｊa ｜＋Ｑ×Ｎ      （３）式
を得る。ここで、Ｎはブロック内の画素数である。
【００３９】
この（３）式は、定数Ｑで減ビットして得るＳＡＤ値“Σa ｜Ｕa −Ｖa ｜”のＱ倍に対して、真のＳＡＤ値“Σa ｜Ｉa −Ｊa ｜”を使って、その上限値と下限値を与えるものである。
【００４０】
この（３）式から、減ビット後のＳＡＤ値を用いてブロックＢ0 を求める方法が導ける。
【００４１】
いま、ブロックＢ0 に対して、定数Ｑで減ビットして得られるＳＡＤ値をＸとすると、後述するように、Ｘは下記の（４）式で示す範囲にある。ここで、Ｘmin は定数Ｑで減ビットして得たＳＡＤ値の中での最小の値、Ｎはブロック内の画素数である。
【００４２】
Ｘmin ≦Ｘ≦Ｘmin ＋２×Ｎ                            （４）式
この関係を利用してブロックＢ0 を求めるには、まず、画像フレーム２からブロックＢj を参照し、ブロックＢi とブロックＢj の各画素値を定数Ｑで減ビットしてＳＡＤ値“Ｘj ”を得て、Ｘj をメモリに記録した後、探索中に減ビットにより得たＳＡＤ値についての暫定最小値Ｘcandと比較し、
Ｘj ≦Ｘcand                                          （５）式
ならばＸcandをＸj に置き換える。
【００４３】
この処理を、ブロックＢj の全てについて終えたときのＸcandが、減ビットで得られる最小ＳＡＤ値“Ｘmin ”である。
【００４４】
次に、全てのブロックＢj に対して、メモリに記録された減ビット後のＳＡＤ値“Ｘj ”とこのＸmin とを比較し、（４）式を満たすブロックＢj についてのみ、真の画素値Ｉa 、Ｊa を用いて真のＳＡＤ値を計算する。
【００４５】
そして、（１）式に基づいて、真の最小ＳＡＤ値“ＳＡＤmin ”を持つブロックＢ0 を求める。
【００４６】
このようにして、本発明の第１の構成では、ビット数を減じた画素値で得られるＳＡＤ値と、真の画素値により得られるＳＡＤ値との間にある関係を導出し、これを利用することで動きベクトル検出処理を効率化するという方法を採るのである。
【００４７】
〔３−２〕第２の構成の理論的根拠
本発明の第２の構成は、従来技術の問題を解決するために、ＳＥＡ探索法を利用して動きベクトルを検出する。
【００４８】
ＳＥＡ探索法は、画像フレーム内の隣接画素同士をまとめて粗い画素（粗い画像）を作り、その画素値でＳＡＤを求め、それを下限閾値として、真の画素値によるＳＡＤ計算を省略する方法であり、本発明の第２の構成は、この粗い画像を減ビットして、ＳＥＡ探索法を適用するということを基本的構成とする。
【００４９】
粗画像フレーム１からあるブロックＢＣ(1) i 、粗画像フレーム２からあるブロックＢＣ(2) j を参照し、そのＳＡＤ値をＣj とし、各々のブロックに含まれる画素値を定数Ｑで減ビットし、その画素値で計算したＳＡＤ値をＸＣj とすると、ＳＥＡ探索法では、真のＳＡＤ値の暫定最小値“ＳＡＤcand”と比較して、
ＳＡＤcand＜Ｃj                                       （６）式
が成り立つブロックについては、真の画素値でのＳＡＤ計算を省略できる。
【００５０】
いま、減ビットして得たＳＡＤ値“ＸＣj ”についても同様の条件式を考える。上述の（３）式が減ビットで得たＳＡＤ値と元のＳＡＤ値との間で上限値を定める式であることから、
Ｃj ≦Ｑ×ＸＣj ＋Ｑ×ＮＣ                            （７）式
が導かれる。ここで、ＮＣは粗画像でのブロック内画素数である。
【００５１】
すると、（６）式と（７）式とから、
ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ                      （８）式
が減ビット後の条件式であることがわかる。
【００５２】
本発明の第２の構成は、ＳＥＡ探索法と減ビット画像への変換とを組み合わせることで動きベクトルを検出するときにあって、この（７）式に従って、真の画素値でのＳＡＤ計算を省略できるブロックであるのか否かを判定しつつ、ＳＥＡ探索法を利用して動きベクトルを検出するのである。
【００５３】
〔３−３〕（２）式の導出
次に、（２）式を導出する。
【００５４】
非負の整数Ｉa とＪa を定数Ｑで割り、その整数部をそれぞれＵa とＶa とし、
Ｕa ＝Ｉa ／Ｑ−ｄi                                     （Ａ１−１）
Ｖa ＝Ｊa ／Ｑ−ｄj                                     （Ａ１−２）
と表す。ここで、０≦ｄi ≦１、０≦ｄj ≦１である。
【００５５】
このとき、minkowsky 不等式の定理から、
｜Ｉa −Ｊa ｜＝Ｑ×｜（Ｕa ＋ｄi ）−（Ｖa ＋ｄj ）｜
≦Ｑ×｜Ｕa −Ｖa ｜＋Ｑ×｜ｄi −ｄj ｜      （Ａ１−３）
となる。
【００５６】
また、０≦ｄi ≦１、０≦ｄj ≦１なので、
｜ｄi −ｄj ｜≦１                                      （Ａ１−４）
が成り立つ。
【００５７】
よって、（Ａ１−３）と（Ａ１−４）とから、
｜Ｉa −Ｊa ｜≦Ｑ×｜Ｕa −Ｖa ｜＋Ｑ×｜ｄi −ｄj ｜
≦Ｑ×｜Ｕa −Ｖa ｜＋Ｑ                      （Ａ１−５）
が成り立つ。
【００５８】
また、三角不等式の定理と（Ａ１−４）とから、
Ｑ×｜Ｕa −Ｖa ｜＝｜（Ｉa −Ｊa ）＋Ｑ×（ｄj −ｄi ）｜
≦｜Ｉa −Ｊa ｜＋Ｑ×｜ｄj −ｄi ｜
≦｜Ｉa −Ｊa ｜＋Ｑ                      （Ａ１−６）
も成り立つ。
【００５９】
したがって、（Ａ１−５）と（Ａ１−６）とから、
｜Ｉa −Ｊa ｜−Ｑ≦Ｑ×｜Ｕa −Ｖa ｜≦｜Ｉa −Ｊa ｜＋Ｑ    （Ａ１−７）
という（２）式が導かれる（証明終了）。
【００６０】
〔３−４〕（４）式の導出
次に、（３）式が成り立つときに、真の最小ＳＡＤを持つブロックＢ0 について、減ビットして得たＳＡＤ値“Ｘ”が（４）式を満たすことについて証明する。
【００６１】
まず、（３）式を再掲する。
【００６２】
Σa ｜Ｉa −Ｊa ｜−Ｑ×Ｎ≦Ｑ×Σa ｜Ｕa −Ｖa ｜
≦Σa ｜Ｉa −Ｊa ｜＋Ｑ×Ｎ      （３）式
この（３）式は、あるブロックに対して、減ビットして得られるＳＡＤ値“Σa ｜Ｕa −Ｖa ｜”の上限値と下限値を、真のＳＡＤ値“Σa ｜Ｉa −Ｊa ｜”を使って与えるものである。すなわち、上限値は“Σa ｜Ｉa −Ｊa ｜＋Ｑ×Ｎ”であり、下限値は“Σa ｜Ｉa −Ｊa ｜−Ｑ×Ｎ”である。
【００６３】
（３）式を変形すると、
Ｑ×Σa ｜Ｕa −Ｖa ｜−Ｑ×Ｎ≦Σa ｜Ｉa −Ｊa ｜
≦Ｑ×Σa ｜Ｕa −Ｖa ｜＋Ｑ×Ｎ    （Ａ２−ｌ）
となる。
【００６４】
（Ａ２−１）式は、（３）式とは逆に、真のＳＡＤ値“Σa ｜Ｉa −Ｊa ｜”の値域を定めるものである。上限が“Ｑ×Σa ｜Ｕa −Ｖa ｜＋Ｑ×Ｎ”であり、下限値が“Ｑ×Σa ｜Ｕa −Ｖa ｜−Ｑ×Ｎ”である。
【００６５】
いま、最小の真のＳＡＤ値“ＳＡＤmin ”を持つブロックＢ0 に対して、減ビットして得るＳＡＤ値をＸとする。また、減ビットで得られたＳＡＤ値の中で最小の値をＸmin とする。
【００６６】
まず、ＳＡＤmin が“Ｑ×Ｘmin ＋Ｑ×Ｎ”より大きいとしてみる。このとき、Ｘmin を与えたブロックの真のＳＡＤ値は、最大でも“Ｑ×Ｘmin ＋Ｑ×Ｎ”であることが（Ａ２−２）式で明らかなので、ＳＡＤmin より小さい値を持つ。これはＳＡＤmin が最小であるという仮定に反する。ゆえに、ＳＡＤmin は“Ｑ×Ｘmin ＋Ｑ×Ｎ”以下でなければならない。
【００６７】
さらに、ブロックＢ0 について得たＸは、その上限値が“ＳＡＤmin ＋Ｑ×Ｎ”であることが（３）式でわかるので、
Ｑ×Ｘ≦ＳＡＤmin ＋Ｑ×Ｎ≦Ｑ×Ｘmin ＋２×Ｑ×Ｎ        （Ａ２−２）
が成り立つ。
【００６８】
また、いかなるブロックに対しても、減ビットで得られるＳＡＤ値がＸmin より小さくなることはないので、明らかに、
Ｘmin ≦Ｘ                                                （Ａ２−３）
である。
【００６９】
ゆえに、（Ａ２−２）と（Ａ２−３）とから、
Ｘmin ≦Ｘ≦Ｘmin ＋２×Ｎ                                （Ａ２−４）
という（４）式が満たされることがわかる（証明終了）。
【発明の効果】
【００７０】
以上説明したように、本発明は、２つの画像フレーム間の動きベクトルを検出する方法として、画素値を表現するビット数を減じた計算を主体とすることから、一定のビット幅の演算リソースでの処理効率を向上させることができるようになる。
【発明を実施するための最良の形態】
【００７１】
以下、実施の形態に従って本発明を詳細に説明する。
【００７２】
ここで、以下に説明する実施の形態では、各画像フレームにおいて全てのブロックは順序付けが成されており、１個の参照変数により順序参照が可能であるものとする。また、ブロック内の画素についても順序付けがなされており、１個の参照変数で順序参照が可能であるとする。
【００７３】
最初に、上述した第１の構成に従う本発明の動きベクトル検出装置１の実施の形態について説明する。
【００７４】
図１に、第１の構成に従う本発明の動きベクトル検出装置１の装置構成を図示する。
【００７５】
この図に示すように、本発明の動きベクトル検出装置１は、第１の構成を実現する場合には、画像フレーム１と画像フレーム２という動きベクトルの検出対象となる２つの画像フレームを格納する画像フレーム用メモリ１０と、画像フレーム１と画像フレーム２との間の動きベクトルを検出する動きベクトル検出機構１１ａと、動きベクトル検出機構１１ａが生成する減ビット画像を格納する減ビット画像用メモリ１２と、作業用に用意される作業用メモリ１３と、検出結果の動きベクトルを格納する動きベクトル用メモリ１４とを備える。
【００７６】
ここで、後述するメモリＭ(1) ，Ｍ(2) は減ビット画像用メモリ１２に該当し、後述するメモリＭＸは作業用メモリ１３に該当し、後述するメモリＭＶは動きベクトル用メモリ１４に該当する。
【００７７】
この動きベクトル検出機構１１ａは、減ビット画像への変換を実行する減ビット画像生成部と、減ビット画素値でのＳＡＤ値を算出して、その中の最小のものを抽出する最小減ビットＳＡＤ値抽出部と、その抽出結果に基づいて、真の画素値でのＳＡＤ値を算出する必要のあるブロックであるのか否かを判定する真ＳＡＤ値算出要否判定部と、その判定結果に基づいて、真の画素値でのＳＡＤ値を算出して、その中の最小のものを特定する最小真ＳＡＤ値特定部と、その特定結果に基づいて、動きベクトルを検出する動きベクトル検出部とを備える。
【００７８】
図２及び図３に、動きベクトル検出機構１１ａの実行するフローチャートを図示する。次に、このフローチャートに従って、このように構成される本発明の動きベクトル検出装置１の実行する動きベクトル検出処理について詳細に説明する。
【００７９】
動きベクトル検出機構１１ａは、先ず最初に、ステップ１０で、変数ｉを初期化し、変数Ｎにブロック内画素数を入れる。
【００８０】
続いて、ステップ１１で、変数ｊを初期化する。また、画像フレーム１の第ｉ番目のブロックＢ(1) i 内の画素値を順次参照し、定数Ｑで減ビットした値を求めてメモリＭ(1) に順次記憶しておく。さらに、変数Ｘmin に十分大きな値を入れておく。
【００８１】
続いて、ステップ１２で、画像フレーム２の第ｊ番目のブロックＢ(2) j 内の画素値を順次参照し、定数Ｑで減ビットした値を求めてメモリＭ(2) に順次記憶しておく。
【００８２】
続いて、ステップ１３で、メモリＭ(1) およびメモリＭ(2) から減ビット後の画素値を順次読み出し、減ビット後のＳＡＤ値“Ｘj ”を算出して、メモリＭＸの第ｊ番目に記憶しておく。
【００８３】
続いて、ステップ１４で、暫定最小値“Ｘmin ”とＸj とを比較して、“Ｘmin ＞Ｘj ”であることを判断するときには、ステップ１５に進んで、Ｘmin をＸj で置き換え、一方、“Ｘmin ＞Ｘj ”でないことを判断するときには、この置き換え処理を省略する。
【００８４】
続いて、ステップ１６で、変数ｊを更新し、その更新したｊの値が画像フレーム２のブロック数より小さいことを判断するときには、画像フレーム２に未処理のブロックが残されているので、ステップ１２に戻る。
【００８５】
このようにして、ステップ１２〜ステップ１６の処理を繰り返していくことで、減ビット後のＳＡＤ値“Ｘj ”の中の最小値“Ｘmin ”が求められることになる。
【００８６】
これから、ステップ１６で、画像フレーム２の全てのブロックを処理したことで最小値“Ｘmin ”が求められたことを判断すると、ステップ１７に進んで、変数ｊを初期化する。また、変数ＳＡＤmin に十分大きな値を入れておく。さらに、変数ｉｄｘを初期化しておく。
【００８７】
続いて、ステップ１８で、メモリＭＸの第ｊ番目にある減ビット後のＳＡＤ値“Ｘj ”を参照する。
【００８８】
続いて、ステップ１９で、参照したＸj と最小値“Ｘmin ”とを比較して、
Ｘmin ≦Ｘj ≦Ｘmin ＋２×Ｎ
であるのか否かを判断して、この式が成立しないことを判断するときには、これから説明するステップ２０〜ステップ２２の処理を省略して、ステップ２３に進む。
【００８９】
一方、ステップ１９で、“Ｘmin ≦Ｘj ≦Ｘmin ＋２×Ｎ”が成立することを判断するときには、真の画素値でのＳＡＤ値を算出する必要のあるブロックであることを判断して、ステップ２０に進んで、画像フレーム１の第ｉ番目のブロックＢ(1) i 内の画素値と、画像フレーム２の第ｊ番目のブロックＢ(2) j 内の画素値とを順次参照して、真のＳＡＤ値“ＳＡＤj ”を算出する。
【００９０】
続いて、ステップ２１で、暫定最小値“ＳＡＤmin ”とＳＡＤj とを比較して、“ＳＡＤmin ＞ＳＡＤj ”であることを判断するときには、ステップ２２に進んで、ＳＡＤmin をＳＡＤj で置き換えるとともに、変数ｉｄｘにｊを入れ、一方、“ＳＡＤmin ＞ＳＡＤj ”でないことを判断するときには、この置き換え処理を省略する。
【００９１】
続いて、ステップ２３で、変数ｊを更新し、その更新したｊの値が画像フレーム２のブロック数より小さいことを判断するときには、画像フレーム２に未処理のブロックが残されているのでステップ１８に戻る。
【００９２】
このようにして、ステップ１８〜ステップ２３の処理を繰り返していくことで、真のＳＡＤ値“ＳＡＤj ”の中の最小値“ＳＡＤmin ”が求められることになる。
【００９３】
これから、ステップ２３で、画像フレーム２の全てのブロックを処理したことで真のＳＡＤ値の最小値“ＳＡＤmin ”が求められたことを判断すると、ステップ２４に進んで、画像フレーム１におけるブロックＢ(1) i の座標と、画像フレーム２における第ｉｄｘ番目のブロックＢ(2) idx の座標との変分を求め、メモリＭＶの第ｉ番地に格納する。
【００９４】
このステップ２４の段階で、ブロックＢ(1) i に対する動きベクトルが求まることになる。
【００９５】
続いて、ステップ２５で、変数ｉを更新し、その更新したｉの値が画像フレーム１のブロック数より小さいことを判断するときには、画像フレーム１に未処理のブロックが残されているので、ステップ１１に戻る。
【００９６】
このようにして、本発明の動きベクトル検出装置１は、図２及び図３のフローチャートに従って、画素値を表現するビット数を減じた計算を主体として２つの画像フレーム間の動きベクトルを検出するように処理するので、一定のビット幅の演算リソースでの処理効率を向上させることができるようになる。
【００９７】
次に、上述した第２の構成に従う本発明の動きベクトル検出装置１の実施の形態について説明する。
【００９８】
本発明の動きベクトル検出装置１は、上述した第２の構成に従うには、ＳＥＡ探索法を利用して動きベクトルを検出する処理を行う。
【００９９】
ＳＥＡ探索法では、画像フレーム内の隣接画素同士をまとめて粗い画素（粗い画像）を作り、その画素値でＳＡＤを求め、それを下限閾値として、真の画素値によるＳＡＤ計算を省略するものである。画素を粗くすることでブロック内画素数が減るため、粗い画素値でのＳＡＤ計算にかかる演算量は真の画素値でのそれよりも少ない。それゆえ、ＳＡＤ計算全体に要する演算量を削減できる効果が見込まれる。
【０１００】
例えば、画像フレーム１の２つの画素（画素値ａ1,ａ2)を、１画素（画素値ａ1 ＋ａ2 ）にまとめて粗画像フレーム１を作成し、同様に、画像フレーム２についても２つの画素（画素値ｂ1,ｂ2)を、１画素（画素値ｂ1 ＋ｂ2 ）にまとめて粗画像フレーム２を作成したとする。このとき、粗画像フレームでのブロック内画素数ＮＣは、元の画像フレームでのブロック内画素数Ｎの２分の１である。
【０１０１】
いま、粗画像フレーム１および粗画像フレーム２に対して、あるブロック間でＳＡＤ値を得たとすると、この値については、minkowsky 不等式
｜（ａ1 ＋ａ2 ）−（ｂ1 ＋ｂ2 ）｜≦｜ａ1 −ｂ1 ｜＋｜ａ2 −ｂ2 ｜
が成り立つことから、元の画像フレーム１および画像フレーム２の対応するブロック間での真のＳＡＤ値に対して、その下限を与えていることになる。
【０１０２】
ゆえに、探索中の真のＳＡＤ値の暫定最小値をＳＡＤcandとし、粗画像フレーム１および粗画像フレーム２のあるブロック間で計算したＳＡＤ値をＣとすると、
ＳＡＤcand＜Ｃ
であれば、このブロック間に関して真のＳＡＤ値を計算する必要はない。
【０１０３】
これがＳＥＡ探索法の基本原理である。このことから分かるように、ＳＥＡ探索法では、粗画像フレームの画素値を用いたＳＡＤ計算が主となる。これらの画素値は、元の画像フレームの画素値を加算することで得られるので、その表現に用いるビット数は元の画素値のそれよりも多い。それゆえ、ＳＥＡ探索法でのＳＡＤ計算には、真の画素値でのＳＡＤ計算よりも、ビット幅の大きい演算リソースが必要となる。
【０１０４】
そこで、第２の構成に従う本発明の動きベクトル検出装置１では、粗画像フレームを減ビットすることで、ＳＥＡ探索法で要求されるＳＡＤ計算の効率化を図るものである。
【０１０５】
粗画像フレーム１からあるブロックＢＣ(1) i 、粗画像フレーム２からあるブロックＢＣ(2) j を参照し、そのＳＡＤ値をＣj とし、各々のブロックに含まれる画素値を定数Ｑで減ビットし、その画素値で計算したＳＡＤ値をＸＣj とすると、ＳＥＡ探索法では、真のＳＡＤ値の暫定最小値“ＳＡＤcand”と比較して、
ＳＡＤcand＜Ｃj                                       （６）式
が成り立つブロックについては、真の画素値でのＳＡＤ計算を省略できる。
【０１０６】
いま、減ビットして得たＳＡＤ値“ＸＣj ”についても同様の条件式を考える。上述の（３）式が減ビットで得たＳＡＤ値と元のＳＡＤ値との間で上限値を定める式であることから、
Ｃj ≦Ｑ×ＸＣj ＋Ｑ×ＮＣ                            （７）式
が導かれる。ここで、ＮＣは粗画像でのブロック内画素数である。
【０１０７】
すると、（６）式と（７）式とから、
ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ                      （８）式
が減ビット後の条件式であることがわかる。
【０１０８】
第２の構成に従う本発明の動きベクトル検出装置１は、この（７）式に従って、真の画素値でのＳＡＤ計算を省略できるブロックであるのか否かを判定しつつ、ＳＥＡ探索法を利用して動きベクトルを検出するのである。
【０１０９】
図４に、第２の構成に従う本発明の動きベクトル検出装置１の装置構成を図示する。
【０１１０】
この図に示すように、本発明の動きベクトル検出装置１は、第２の構成を実現する場合には、画像フレーム１と画像フレーム２という動きベクトルの検出対象となる２つの画像フレームを格納する画像フレーム用メモリ１０と、画像フレーム１と画像フレーム２との間の動きベクトルを検出する動きベクトル検出機構１１ｂと、動きベクトル検出機構１１ｂが生成する粗画像を格納する粗画像フレーム用メモリ１５と、動きベクトル検出機構１１ｂが生成する減ビット画像を格納する減ビット画像用メモリ１２と、作業用に用意される作業用メモリ１３と、検出結果の動きベクトルを格納する動きベクトル用メモリ１４とを備える。
【０１１１】
ここで、後述するメモリＭＣ(1) ，ＭＣ(2) は減ビット画像用メモリ１２に該当し、後述するメモリＭＶは動きベクトル用メモリ１４に該当する。
【０１１２】
この動きベクトル検出機構１１ｂは、粗画像への変換を実行する粗画像生成部と、減ビット画像への変換を実行する減ビット画像生成部と、減ビット画素値でのＳＡＤ値を算出する減ビットＳＡＤ値算出部と、その算出結果と真のＳＡＤ値の暫定最小値とに基づいて、真の画素値でのＳＡＤ値を算出する必要のあるブロックであるのか否かを判定する真ＳＡＤ値算出要否判定部と、その判定結果に基づいて、真の画素値でのＳＡＤ値を算出して、それに応じて真のＳＡＤ値の暫定最小値を更新する真ＳＡＤ暫定最小値更新部と、真のＳＡＤ値の暫定最小値が確定するときに、それに基づいて、動きベクトルを検出する動きベクトル検出部とを備える。
【０１１３】
図５及び図６に、動きベクトル検出機構１１ｂの実行するフローチャートを図示する。次に、このフローチャートに従って、このように構成される本発明の動きベクトル検出装置１の実行する動きベクトル検出処理について詳細に説明する。
【０１１４】
動きベクトル検出機構１１ｂは、先ず最初に、ステップ３０で、画像フレーム１および画像フレーム２をそれぞれ、粗画像フレーム１および粗画像フレーム２に変換し、粗画像フレーム用メモリ１５に格納する。さらに、変数Ｎに元の画像フレームでのブロック内画素数を入れ、変数ＮＣに粗画像フレームでのブロック内画素数を入れる。
【０１１５】
続いて、ステップ３１で、変数ｉを初期化する。
【０１１６】
続いて、ステップ３２で、変数ｊを初期化する。そして、粗画像フレーム１の第ｉ番目のブロックＢＣ(1) i 内の画素値を順次参照し、その値を定数Ｑで減ビットしてメモリＭＣ(1) に順次記憶する。さらに、真のＳＡＤ値の暫定最小値を示す変数ＳＡＤcandに十分大きな値を入れるとともに、変数ｉｄｘを初期化する。
【０１１７】
続いて、ステップ３３で、粗画像フレーム２の第ｊ番目のブロックＢＣ(2) j 内の画素値を順次参照し、その値を定数Ｑで減ビットしてメモリＭＣ(2) に順次記憶する。
【０１１８】
続いて、ステップ３４で、メモリＭＣ(1) およびメモリＭＣ(2) から減ビット後の画素値を順次読み出し、減ビット後のＳＡＤ値“ＸＣj ”を算出する。
【０１１９】
続いて、ステップ３５で、算出したＸＣj とＳＡＤcandとＱとＮＣとに基づいて、
ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ
という式が成立するのか否かを判断して、この式が成立することを判断するときには、これから説明するステップ３６〜ステップ３８の処理を省略して、ステップ３９に進む。
【０１２０】
一方、ステップ３５で、“ＳＡＤcand＜Ｑ×ＸＣj ＋Ｑ×ＮＣ”が成立しないことを判断するときには、真の画素値でのＳＡＤ値を算出する必要のあるブロックであることを判断して、ステップ３６に進んで、画像フレーム１の第ｉ番目のブロックＢ(1) i 内の画素値と、画像フレーム２の第ｊ番目のブロックＢ(2) j 内の画素値とを順次参照して、真のＳＡＤ値“ＳＡＤj ”を算出する。
【０１２１】
続いて、ステップ３７で、暫定最小値“ＳＡＤcand”とＳＡＤj とを比較して、“ＳＡＤcand＞ＳＡＤj ”であることを判断するときには、ステップ３８に進んで、ＳＡＤcandをＳＡＤj で置き換えるとともに、変数ｉｄｘにｊを入れ、一方、“ＳＡＤcand＞ＳＡＤj ”でないことを判断するときには、この置き換え処理を省略する。
【０１２２】
続いて、ステップ３９で、変数ｊを更新し、その更新したｊの値が画像フレーム２のブロック数より小さいことを判断するときには、画像フレーム２に未処理のブロックが残されているので、ステップ３３に戻る。
【０１２３】
このようにして、ステップ３３〜ステップ３９の処理を繰り返していくことで、真のＳＡＤ値の最小値“ＳＡＤmin ”が求められることになる。
【０１２４】
これから、ステップ３９で、画像フレーム２の全てのブロックを処理したことで真のＳＡＤ値の最小値“ＳＡＤmin ”が求められたことを判断すると、ステップ４０に進んで、画像フレーム１におけるブロックＢ(1) i の座標と、画像フレーム２における第ｉｄｘ番目のブロックＢ(2) idx の座標との変分を求め、メモリＭＶの第ｉ番地に格納する。
【０１２５】
このステップ４０の段階で、ブロックＢ(1) i に対する動きベクトルが求まることになる。
【０１２６】
続いて、ステップ４１で、変数ｉを更新し、その更新したｉの値が画像フレーム１のブロック数より小さいことを判断するときには、画像フレーム１に未処理のブロックが残されているので、ステップ３２に戻る。
【０１２７】
このようにして、本発明の動きベクトル検出装置１は、図５及び図６のフローチャートに従って、ＳＥＡ探索法を使って動きベクトルを検出するときに、画素値を表現するビット数を減じた計算を主体として２つの画像フレーム間の動きベクトル量を検出するように処理するので、一定のビット幅の演算リソースでの処理効率を向上させることができるようになる。
【０１２８】
本発明の動きベクトル検出装置１は、減ビットした画素値に対してＳＡＤ値を計算することを基本的な構成としている。このＳＡＤ値の計算はハードウェアで実現することも可能であるし、ソフトウェアで計算することも可能である。
【０１２９】
図７に、ハードウェアを使って、減ビットした画素値に対してＳＡＤ値を計算する構成の一例を示す。
【０１３０】
上述したように、ブロックＢ(1) i の各画素値を定数Ｑで減ビットした値はメモリＭＣ(1) に格納され、ブロックＢ(2) j の各画素値を減ビットした値はメモリＭＣ(2) に格納されている。
【０１３１】
図７に示すハードウェアにおいて、入力端子１にメモリＭＣ(1) から画素値が与えられ、入力端子２にメモリＭＣ(2) からの画素値が与えられて、減算器１００は、入力端子１と入力端子２との差信号を端子３に出力する。
【０１３２】
これを受けて、符号判定器１０１は、端子３の信号の符号を端子４に出力し、一方、符号反転器１０２は、端子３の信号の符号を反転して端子５に出力する。
【０１３３】
これを受けて、選択器１０３は、端子４の符号が正を示すときには、端子３と出力端子６との間を結線し、端子４の符号が負を示すときには、端子５と出力端子６との間を結線する。
【０１３４】
この後段に、ハードウェア構成の累積加算器が設けられており、この構成に従って、減ビットした画素値についてのＳＡＤ値が計算されることになる。
【０１３５】
図８に、ソフトウェアを使って、減ビットした画素値に対してＳＡＤ値を計算する構成の一例を示す。
【０１３６】
画像フレーム１および画像フレーム２の画素値がともに８より多いビット数で表現されている場合を例にとる。このとき、定数Ｑを適当にとれば、ブロックＢ(1) i およびブロックＢ(2) j の各画素値の表現ビット数を８まで減らすことができる。そのような定数Ｑで減ビットして、メモリＭ(1) とメモリＭ(2) のそれぞれに８ビットデータが格納されているものとする。
【０１３７】
いま、市販の計算機に搭載されている一般的なＣＰＵの多くが持つ並列演算命令（アセンブラ命令）の利用を考える。例えば、あるＣＰＵにはpsadbw命令という命令があり、８ビット画素値８個分同士のＳＡＤ計算を一度に計算できる。
【０１３８】
本発明を応用すれば、８以上の多ビット画素値に対しても、減ビットにより、上記のような汎用の並列演算命令が利用可能となる。
【０１３９】
図８では、このpsadbw命令を用いる構成を示しており、
（１）メモリＭ(1) の先頭アドレスＭ１から数えてＡバイト目からＡ＋７バイト目まで        に置かれた８ビット画素値８個分をレジスタｍｍ０にロードし、
（２）メモリＭ(2) の先頭アドレスＭ２から数えてＡバイト目からＡ＋７バイト目まで        に置かれた８ビット画素値８個分をレジスタｍｍ１にロードし、
（３）並列演算命令psadbwにより、レジスタｍｍ０とｍｍ１とに置かれた画素８個同志        のＳＡＤ値をレジスタｍｍ０に得る。
という手順に従って、減ビットした画素値についてのＳＡＤ値が計算されることになる。
【産業上の利用可能性】
【０１４０】
本発明は動画像の画像を符号化を行う画像符号化装置に適用することができ、本発明を適用することで、従来よりも高速な符号化処理が実現できるようになる。
【図面の簡単な説明】
【０１４１】
【図１】本発明の動きベクトル検出装置の装置構成図である。
【図２】動きベクトル検出機構の実行するフローチャートである。
【図３】動きベクトル検出機構の実行するフローチャートである。
【図４】本発明の動きベクトル検出装置の装置構成図である。
【図５】動きベクトル検出機構の実行するフローチャートである。
【図６】動きベクトル検出機構の実行するフローチャートである。
【図７】ＳＡＤ値の計算を実現するハードウェアの一例を示す図である。
【図８】ＳＡＤ値の計算を実現するソフトウェアの一例を示す図である。
【符号の説明】
【０１４２】
１０  画像フレーム用メモリ
１１  動きベクトル検出機構
１２  減ビット画像用メモリ
１３  作業用メモリ
１４  動きベクトル用メモリ
１５  粗画像フレーム用メモリ
【図１】
2005260392.tif 000003
【図２】
2005260392.tif 000004
【図３】
2005260392.tif 000005
【図４】
2005260392.tif 000006
【図５】
2005260392.tif 000007
【図６】
2005260392.tif 000008
【図７】
2005260392.tif 000009
【図８】
2005260392.tif 000010