(57)【要約】【課題】専用のハードウェアを必要とすることなく、比較的少ない演算量で小数画素精度の動きベクトルを求める。【解決手段】実施形態の動きベクトル探索装置は、原画像中の対象ブロックと、参照画像中の整数画素位置の各参照ブロックとの差分絶対値和演算を行う第１の計算部と、前記参照画像中の整数画素位置の２つの参照ブロック相互間の差分絶対値和演算を行う第２の計算部と、前記第１の計算部によって得られた２つの参照ブロックについての差分絶対値和演算結果を加算する加算計算部と、前記加算計算部の計算結果と前記第２の計算部の差分絶対値和演算結果とに基づいて、前記対象ブロックと前記参照画像中の小数画素位置の各参照ブロックとの差分絶対値和演算結果が最小となる小数画素位置の参照ブロックを推定する制御部とを具備したことを特徴とする。【選択図】図１
2012156707.tif 000002
【特許請求の範囲】
【請求項１】
原画像中の対象ブロックと、参照画像中の整数画素位置の各参照ブロックとの差分絶対値和演算を行う第１の計算部と、
前記参照画像中の整数画素位置の２つの参照ブロック相互間の差分絶対値和演算を行う第２の計算部と、
前記第１の計算部によって得られた２つの参照ブロックについての差分絶対値和演算結果を加算する加算計算部と、
前記加算計算部の計算結果と前記第２の計算部の差分絶対値和演算結果とに基づいて、前記対象ブロックと前記参照画像中の小数画素位置の各参照ブロックとの差分絶対値和演算結果が最小となる小数画素位置の参照ブロックを推定する制御部と
を具備したことを特徴とする動きベクトル探索装置。
【請求項２】
原画像中の対象ブロックと、参照画像中の整数画素位置の各参照ブロックとの差分絶対値和演算を行う第１の計算部と、
前記原画像中の整数画素位置の２つのブロック相互間の差分絶対値和演算を行う第３の計算部と、
前記第１の計算部によって得られた２つの参照ブロックについての差分絶対値和演算結果を加算する加算計算部と、
前記加算計算部の計算結果と前記第３の計算部の差分絶対値和演算結果とに基づいて、前記対象ブロックと前記参照画像中の小数画素位置の各参照ブロックとの差分絶対値和演算結果が最小となる小数画素位置の参照ブロックを推定する制御部と
を具備したことを特徴とする動きベクトル探索装置。
【請求項３】
前記第１及び第３の計算部は、並列に差分絶対値和演算を行う
ことを特徴とする請求項２に記載の動きベクトル探索装置。
【請求項４】
第１の計算部が、原画像中の対象ブロックと、参照画像中の整数画素位置の各参照ブロックとの差分絶対値和演算を順次行い、
第２の計算部が、前記差分絶対値和演算が最小となる参照ブロックの周囲の整数画素位置の２つの参照ブロック相互間の差分絶対値和演算を行い、
加算計算部が、前記第１の計算部によって得られた２つの参照ブロックについての差分絶対値和演算結果を加算し、
制御部が、前記加算計算部の計算結果と前記第２の計算部の差分絶対値和演算結果とに基づいて、前記対象ブロックと前記参照画像中の小数画素位置の各参照ブロックとの差分絶対値和演算結果が最小となる小数画素位置の参照ブロックを推定する
ことを特徴とする動きベクトル探索方法。
【請求項５】
第１の計算部が、原画像中の対象ブロックと、参照画像中の整数画素位置の各参照ブロックとの差分絶対値和演算を順次行い、
第３の計算部が、前記第１の計算部の前記差分絶対値和演算と並列に、前記原画像中の整数画素位置の２つのブロック相互間の差分絶対値和演算を順次行い、
加算計算部が、前記第１の計算部によって得られた２つの参照ブロックについての差分絶対値和演算結果を加算し、
制御部が、前記加算計算部の計算結果と前記第３の計算部の差分絶対値和演算結果とに基づいて、前記対象ブロックと前記参照画像中の小数画素位置の各参照ブロックとの差分絶対値和演算結果が最小となる小数画素位置の参照ブロックを推定する
ことを特徴とする動きベクトル探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、動きベクトル探索装置及び方法に関する。
【背景技術】
【０００２】
近年、画像処理のディジタル化が普及している。デジタル画像処理においては、画像の動きを求める動きベクトルの探索が重要な技術となる。例えば、ディジタル化された画像データは、符号量を削減するために、Ｈ．２６４、ＡＶＣ規格等の動画像符号化方法を採用して符号化されることが多い。このような符号化技術では、画像の動きを考慮した画面間予測によって符号量を削減する動き補償予測符号化が行われており、この動き補償予測符号化において動きベクトルの探索が行われる。
【０００３】
また、近年、入力画像のデプス（奥行き）を推定して、２次元画像から３次元画像を生成する方法も開発されている。このデプスの推定手法の１つとして、動きベクトルの探索結果を用いるものがある。
【０００４】
動きベクトルは、対象画像のブロックと参照画像のブロックとの間でブロックマッチング演算を行い、差分絶対値和（以下、ＳＡＤ（Sum of Absolute Difference）という）が最小となるブロックを探索することで求められる。
【０００５】
このような動きベクトルの探索精度として、整数画素精度を採用した場合には、探索に必要な演算量はそれ程大きくない。しかし、１／２画素精度等の小数画素精度を採用すると、探索に必要な演算量は膨大となる。
【０００６】
そこで、整数画素位置の画素同士の差分の符号を用いたパラメータを利用して、動きベクトルを探索する手法も開発されている。この手法においては、整数画素位置の画素同士の差分の符号に対する処理を専用のハードウェアを用いることで、小数画素精度の動きベクトル探索における演算量を低減している。
【０００７】
しかしながら、この手法では、演算量の十分な削減効果を得るためには、整数画素位置の画素同士の差分の符号に対する処理を行うための専用のハードウェアが必須である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−２５３０１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の実施形態は、専用のハードウェアを必要とすることなく、比較的少ない演算量で小数画素精度の動きベクトルを求めることができる動きベクトル探索装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
実施形態の動きベクトル探索装置は、原画像中の対象ブロックと、参照画像中の整数画素位置の各参照ブロックとの差分絶対値和演算を行う第１の計算部と、前記参照画像中の整数画素位置の２つの参照ブロック相互間の差分絶対値和演算を行う第２の計算部と、前記第１の計算部によって得られた２つの参照ブロックについての差分絶対値和演算結果を加算する加算計算部と、前記加算計算部の計算結果と前記第２の計算部の差分絶対値和演算結果とに基づいて、前記対象ブロックと前記参照画像中の小数画素位置の各参照ブロックとの差分絶対値和演算結果が最小となる小数画素位置の参照ブロックを推定する制御部とを具備したものである。
【図面の簡単な説明】
【００１１】
【図１】本発明の第１の実施の形態に係る動きベクトル探索装置を示すブロック図。
【図２】ブロックマッチング演算の対象となるブロックを示す説明図。
【図３】第１の実施の形態を説明するためのフローチャート。
【図４】特徴量の算出に用いる参照ブロックを説明するための説明図。
【図５】特徴量の理論最大値を示す図表。
【図６】本発明の第２の実施の形態を示すブロック図。
【図７】パラメータＰＡＲＡＭ＿Ｃを説明するための説明図。
【図８】第２の実施の形態の動作を説明するためのフローチャート。
【図９】各実施の形態をエンコーダに適用した例を示すブロック図。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施の形態について詳細に説明する。
【００１３】
（第１の実施の形態）
図１は本発明の第１の実施の形態に係る動きベクトル探索装置を示すブロック図である。
【００１４】
先ず、図２の説明図を参照して、本実施の形態における動きベクトルの探索方法を説明する。
【００１５】
図２はブロックマッチング演算の対象となるブロックを示している。図２（ａ）は原画像中の対象ブロックＳを示し、図２（ｂ）は参照画像中の参照ブロックＲを示している。
【００１６】
対象画像中の対象ブロックＳについての整数画素精度の動きベクトルは、参照画像中の参照ブロックＲを１画素単位でずらしながら、対象ブロックＳと各位置の参照ブロックＲとのＳＡＤ値を求めて、ＳＡＤ値が最小となる参照ブロックＲの位置によって求められる。
【００１７】
即ち、対象ブロックＳの左上端の画素の座標を（ｓｘ，ｓｙ）として対象ブロックＳの各画素の画素値をＳ（ｓｘ＋ｉ，ｓｙ＋ｊ）で表し（０≦ｉ，ｊ≦１５）、参照ブロックＲの左上端の画素の座標を（ｒｘ，ｒｙ）として参照ブロックＲの各画素の画素値をＲ（ｒｘ＋ｉ，ｒｙ＋ｊ）で表すものとし、左上端の画素の座標が（ｒｘ，ｒｙ）の参照ブロックＲと対象ブロックＳとのＳＡＤ値をＳＡＤ（ｒｘ，ｒｙ）とすると、ＳＡＤ（ｒｘ，ｒｙ）は、下記（１）式によって求められる。
【００１８】
2012156707.tif 000003
なお、上記（１）式はｉ，ｊで表される対象ブロックＳ及び参照ブロックＲのブロックサイズが１６×１６画素の例を示している。また、以下に示す各式は、（１）式と同様の記載方法を採用するものとする。また、各ブロックをその左上端の画素の座標によって特定するものとし、左上端の画素の座標が（ｓｘ，ｓｙ）の対象ブロックを対象ブロックＳＢ（ｓｘ，ｓｙ）とし、左上端の画素の座標が（ｒｘ，ｒｙ）の参照ブロックを参照ブロックＲＢ（ｒｘ，ｒｙ）とする。
【００１９】
また、対象ブロックＳについての１／２小数画素精度の動きベクトルを求めるためには、整数画素位置のＳＡＤ値だけでなく、１／２画素位置におけるＳＡＤ値を求める必要がある。例えば、座標（ｒｘ，ｒｙ）の画素から水平方向に１／２画素だけずれた位置が左上端となる参照ブロックＲと対象ブロックＳとのＳＡＤ（ｒｘ＋０．５，ｒｙ）は、下記（２）式によって与えられる。
【００２０】
2012156707.tif 000004
１／２小数画素精度や１／４小数画素精度等の高精度探索では、計算量が膨大となる。そこで、特許文献１においては、１／２画素位置のＳＡＤ値については、ＳＡＤ値を直接求めるのではなく、整数画素精度の画素値を用いた下記（３）式のパラメータＰＡＲＡＭ＿Ａを求め、求めたパラメータＰＡＲＡＭ＿Ａによって最小のＳＡＤ値を与える参照ブロックを推測するようになっている。
【００２１】
2012156707.tif 000005
なお、ＰＡＲＡＭ＿Ａ（ｒｘ＋０．５，ｒｙ）は、ＳＡＤ（ｒｘ＋０．５，ｒｙ）に対応した１／２小数画素精度のパラメータを示している。なお、上記（３）式において、ｓｉｇｎ（）は、（）内の符号に対応した値を示し、（）内の符号が正（０を含む）の場合には０で、負の場合には１である。
【００２２】
特許文献１の技術では、パラメータＰＡＲＡＭ＿Ａが大きいほど、ＳＡＤ値は小さいと予測することにより、パラメータＰＡＲＡＭ＿Ａにより最小ＳＡＤ値を与える参照ブロックを求めている。これにより、１／２小数精度の探索処理に要する計算量を削減可能である。
【００２３】
しかしながら、特許文献１の技術では、上記（３）式に従って、ｉ，ｊを変化させながら符号の累積計算を行うために、各参照ブロック毎に、ブロックサイズに応じたビット数（（３）式では２５６ビット）で符号に応じた値を記憶する必要がある。そして、記憶した値に対して上記（３）式に対応した排他的論理和演算及び加算処理を行うようになっている。このため、特許文献１の発明では、計算量を削減するためには、このような整数画素位置の画素同士の差分の符号に対する処理を行うための専用のハードウェアが必須である。
【００２４】
これに対し、本実施の形態においては、ＳＡＤ値を求める演算によって求めることができ、ＳＡＤ値の大小を推測可能な特徴量（以下、パラメータＰＡＲＡＭ＿Ｂという）を採用することで、動きベクトルの小数精度探索において、特別な専用ハードウェアを不要にし、且つ演算量を著しく低減することを可能にする。
【００２５】
下記（４）式は本実施の形態において採用するパラメータＰＡＲＡＭ＿Ｂを示している。
【００２６】
2012156707.tif 000006
いま、説明の簡略化のために、上記（３）式のパラメータＰＡＲＡＭ＿ＡのＳ（ｓｘ＋ｉ，ｓｙ＋ｊ）＝Ａとし、Ｒ（ｒｘ＋ｉ，ｒｙ＋ｊ）＝Ｂとし、Ｒ（ｒｘ＋ｉ＋１，ｒｙ＋ｊ））＝Ｃとするものとする。ｓｉｇｎ（）の値は０又は１であり、（３）式の絶対値内は、０又は１となる。パラメータＰＡＲＡＭ＿Ａは、絶対値内が１となることにより増加し、ブロックサイズが１６×１６の場合には、取り得る最大値は２５６となる。
【００２７】
パラメータＰＡＲＡＭ＿Ａが増加しない場合、即ち、（３）式の絶対値内が０の場合には、
ｓｉｇｎ（Ａ−Ｂ）＝ｓｉｇｎ（Ａ−Ｃ）＝０であるか、又は、ｓｉｇｎ（Ａ−Ｂ）＝ｓｉｇｎ（Ａ−Ｃ）＝１である。従って、
（Ａ−Ｂ）≧０で且つ（Ａ−Ｃ）≧０であるか、又は、（Ａ−Ｂ）＜０で且つ（Ａ−Ｃ）＜０である。
【００２８】
一方、上記（４）式で示すパラメータＰＡＲＡＭ＿Ｂの絶対値内は、（Ｂ−Ｃ）で表され、（３）式の｜ｓｉｇｎ（Ａ−Ｂ）−ｓｉｇｎ（Ａ−Ｃ）｜が０の場合には、
｜Ｂ−Ｃ｜＝｜Ａ−Ｂ｜−｜Ａ−Ｃ｜である。
【００２９】
また、パラメータＰＡＲＡＭ＿Ａが増加する場合、即ち、（３）式の絶対値内が１の場合には、
ｓｉｇｎ（Ａ−Ｂ）＝１で且つｓｉｇｎ（Ａ−Ｃ）＝０であるか、又は、ｓｉｇｎ（Ａ−Ｂ）＝０で且つｓｉｇｎ（Ａ−Ｃ）＝１である。従って、
（Ａ−Ｂ）≧０で且つ（Ａ−Ｃ）＜０であるか、又は、（Ａ−Ｂ）≧０で且つ（Ａ−Ｃ）＜０である。
【００３０】
即ち、（３）式の｜ｓｉｇｎ（Ａ−Ｂ）−ｓｉｇｎ（Ａ−Ｃ）｜が１の場合には、
｜Ｂ−Ｃ｜＝｜Ａ−Ｂ｜＋｜Ａ−Ｃ｜である。
【００３１】
このように、パラメータＰＡＲＡＭ＿Ａが増加する場合には、パラメータＰＡＲＡＭ＿Ｂも増加することになり、パラメータＰＡＲＡＭ＿ＡとパラメータＰＡＲＡＭ＿Ｂとは、相関関係を有すると共に、広義単調増加の関係を有する。従って、パラメータＰＡＲＡＭ＿Ａが最大となる参照ブロックにおいては、パラメータＰＡＲＡＭ＿Ｂも最大となると考えられる。
【００３２】
パラメータＰＡＲＡＭ＿Ａの取り得る最大値は上述したように２５６であるのに対し、パラメータＰＡＲＡＭ＿Ｂの取り得る最大値（以下、理論最大値という）はブロック毎に異なり、下記（５）式によって与えられる。
【００３３】
2012156707.tif 000007
従って、本実施の形態においては、各参照ブロックについてパラメータＰＡＲＡＭ＿Ｂを求め、パラメータＰＡＲＡＭ＿Ｂとその理論最大値との差分が最も小さいパラメータＰＡＲＡＭ＿Ｂを、最も値が大きいパラメータＰＡＲＡＭ＿Ａに対応したパラメータＰＡＲＡＭ＿Ｂであるものと判断して、このパラメータＰＡＲＡＭ＿Ｂが得られる参照ブロックを、対象ブロックと参照ブロックとの１／２画素精度のＳＡＤ値が最小の参照ブロックと推定するようになっている。
【００３４】
上記（４）式に示す演算は、１画素ずれた参照ブロック同士のＳＡＤ値を求める演算である。また、上記（５）式に示す演算も、対象ブロックと参照ブロックとのＳＡＤ値を求める演算である。従って、パラメータＰＡＲＡＭ＿Ｂは、ＳＡＤ値を求める回路ブロックによって算出することができ、本実施の形態においては、パラメータＰＡＲＡＭ＿Ｂを求めるために特別な専用のハードウェアは不要である。
【００３５】
図１において、動きベクトル探索装置１０は、制御部１１、ブロック計算部２１及び加算計算部３１によって構成されている。制御部１１には、所定の対象ブロックについての探索開始座標が与えられる。制御部１１は、参照画像の各参照ブロックを特定する情報、例えば左上端の座標の情報を格納する領域１２を有する。制御部１１は、領域１２の情報によって特定される各参照ブロック毎に、整数精度のＳＡＤ値を格納する領域１３、パラメータＰＡＲＡＭ＿Ｂを格納する領域１４及びパラメータＰＡＲＡＭ＿Ｂの理論最大値を格納する領域１５を有する。
【００３６】
制御部１１は、与えられた探索開始座標に基づいてブロック計算部２１及び加算計算部３１を制御することにより、各対象ブロック毎に領域１２〜１５の情報を求め、求めた結果によって、小数精度のＳＡＤ値が最小となる参照ブロックを推定するようになっている。
【００３７】
整数精度のＳＡＤ値の算出には、原画像及び参照画像が必要であり、制御部１１は、画像選択情報によっていずれの画像を選択すべきかをブロック計算部２１の画像選択部２２に指示する。画像選択部２２は、画像選択情報に基づいて原画像及び参照画像を選択的にブロック切り出し部２３に与える。
【００３８】
探索開始座標は、探索を開始する参照ブロックを特定するものであり、制御部１１は、探索開始座標に基づいてブロック位置を指定する情報、例えば、各ブロックの左上端の座標（ｒｘ，ｒｙ），（ｓｘ，ｓｙ）をブロック切り出し部２３に与える。ブロック切り出し部２３は、制御部１１によって指定されたブロックの各画素の値を読出して、差分計算部２４に出力する。
【００３９】
差分計算部２４は、上記（１）式及び（４）式に示す画素値の差分演算を行って差分演算結果を絶対値計算部２５に出力する。絶対値計算部２５は、上記（１）式及び（４）式の絶対値演算を行って、演算結果を累積加算計算部２６に出力する。累積加算計算部２６は、上記（１）式及び（４）式の累積加算演算を行う。この累積加算計算部２６の演算結果は、所定の参照ブロックについて求めた整数精度のＳＡＤ値とパラメータＰＡＲＡＭ＿Ｂである。
【００４０】
（４）式に示すように、パラメータＰＡＲＡＭ＿Ｂの演算は、参照画像中の１画素ずれた参照ブロックの各画素同士の差分演算であり、ＳＡＤ値を求める演算によって求めることができる。従って、本実施の形態においては、特別な専用ハードウェアを必要とすることなく、整数精度のＳＡＤ値を求めると共に、パラメータＰＡＲＡＭ＿Ｂを求めることができる。
【００４１】
制御部１１は、所定の参照ブロックについて、領域１３の情報を取得すると、参照ブロックを１画素ずらして同様の処理を繰り返す。こうして、制御部１１は、各参照ブロックについて、整数精度のＳＡＤ値を取得することができる。
【００４２】
また、制御部１１は、小数精度探索のために、所定の参照ブロックについて領域１４の情報を取得すると、次の参照ブロックについて同様の処理を繰り返す。こうして、制御部１１は、小数精度探索の探索範囲内の各参照ブロックについて、パラメータＰＡＲＡＭ＿Ｂを取得することができる。
【００４３】
なお、制御部１１は、動きベクトル探索の探索範囲内の全ての参照ブロックについてパラメータＰＡＲＡＭ＿Ｂを求めてもよく、整数精度の探索の結果得られた最小ＳＡＤを与える参照ブロックの周囲に設定した所定範囲の参照ブロックついて、パラメータＰＡＲＡＭ＿Ｂを求めるようにしてもよい。
【００４４】
制御部１１は、パラメータＰＡＲＡＭ＿Ｂの理論最大値を求めるために、領域１３からＳＡＤ値を読出して加算計算部３１に与える。加算計算部３１は、制御部１１から与えられたＳＡＤ値を用いた上記（５）式の演算によって、パラメータＰＡＲＡＭ＿Ｂの理論最大値を求めて制御部１１に与える。制御部１１は、加算計算部３１の計算結果を領域１５に記憶させるようになっている。
【００４５】
更に、制御部１１は、領域１４，１５の情報を読み出して、パラメータＰＡＲＡＭ＿Ｂとその理論最大値の差分を求め、最小の差分を与える参照ブロックを、ＳＡＤ値が最小の小数精度の参照ブロックであるものと推定する。
【００４６】
次に、このように構成された実施の形態の動作について図３乃至図５を参照して説明する。図３は第１の実施の形態を説明するためのフローチャートであり、図４は特徴量の算出に用いる参照ブロックを説明するための説明図であり、図５は特徴量の理論最大値を示す図表である。
【００４７】
図３のステップＳ１〜Ｓ４は整数精度の探索処理を行うためのステップである。図３に示す整数精度の探索処理においては、先ずステップＳ１においてブロック指定が行われる。制御部１１は、所定の対象ブロックについて、例えば、整数画素精度の探索処理における所定の探索範囲を設定する。制御部１１は、ブロック計算部２１に対して、探索範囲内の各ブロックを順次指定する。
【００４８】
ブロック切り出し部２３は、画像選択部２２を介して原画像及び参照画像が入力されて、対象ブロック及び参照ブロックを切り出して差分計算部２４に出力する。差分計算部２４は、ステップＳ２のＳＡＤ演算における差分演算を行う。これにより、（１）式の絶対値内の差分演算が行われる。差分計算部２４の計算結果は絶対値計算部２５に与えられて絶対値が求められる。絶対値計算部２５は差分演算結果の絶対値を求めて、演算結果を累積加算計算部２６に出力する。累積加算計算部２６は、ブロック内の全ての画素についての差分計算及び絶対値計算結果を累積する。これにより、（１）式のＳＡＤ値が求められる。制御部１１は、領域１２に参照ブロックの情報を記録すると共に、探索範囲内の参照ブロックについて求められたＳＡＤ値を、領域１２に対応する領域１３に記録する（ステップＳ３）。
【００４９】
制御部１１は、ステップＳ４において、探索範囲内の全ての参照ブロックについてＳＡＤ値の計算が行われたか否かを判定し、整数精度の探索処理が終了していない場合には、処理をステップＳ１に戻して次の参照ブロックについてＳＡＤ値の算出処理及び記録処理を行う。
【００５０】
対象ブロックと探索範囲内の全ての参照ブロックとのＳＡＤ値が求められると、制御部１１は、ステップＳ５に処理を移行して、整数精度において最もＳＡＤ値が小さい参照ブロック（以下、整数精度検出ブロックという）を決定する（ステップＳ５）。
【００５１】
次に、制御部１１は、整数精度探索において最もＳＡＤ値が小さい参照ブロック（整数精度検出ブロック）の周囲に、小数精度（高精度）探索のための探索範囲を設定する。ステップＳ６乃至Ｓ１２は、高精度探索を行うためのステップを示している。
【００５２】
制御部１１は、探索範囲内の参照ブロックを指定する。いま、例えば、高精度探索における探索範囲として、整数精度検出ブロックの上下左右に０．５画素ずれた４つの参照ブロックを設定する例について説明する。なお、高精度探索の探索範囲は適宜設定可能であり、例えば、上下左右、斜めに０．５画素ずれた８つの参照ブロックを設定するようにしてもよく、更に、広範囲の探索範囲を設定してもよい。
【００５３】
例えば、整数精度検出ブロックがＲＢ（ｒｘ，ｒｙ）であるものとすると、高精度探索の参照ブロックとしてＲＢ（ｒｘ−０．５，ｒｙ），ＲＢ（ｒｘ＋０．５，ｒｙ），ＲＢ（ｒｘ，ｒｙ−０．５），ＲＢ（ｒｘ，ｒｙ＋０．５）を設定する。
【００５４】
本実施の形態においては、これらの４つの参照ブロックについてＳＡＤに対応した特徴量であるパラメータＰＡＲＡＭ＿Ｂを求め、パラメータＰＡＲＡＭ＿Ｂの理論最大値との差が最も小さいパラメータＰＡＲＡＭ＿Ｂを与える参照ブロックを、ＳＡＤが最も小さい参照ブロックであると推定する。
【００５５】
そして、本実施の形態においては、これらの０．５画素ずれた参照ブロックのパラメータＰＡＲＡＭ＿Ｂの演算には、整数位置のブロックＲＢ（ｒｘ−１，ｒｙ），ＲＢ（ｒｘ＋１，ｒｙ），ＲＢ（ｒｘ，ｒｙ−１），ＲＢ（ｒｘ，ｒｙ＋１）を用いる。
【００５６】
即ち、パラメータＰＡＲＡＭ＿Ｂ（ｒｘ−０．５，ｒｙ）の算出のために、図４（ａ）に示す参照ブロックＲＢ（ｒｘ，ｒｙ），ＲＢ（ｒｘ−１，ｒｙ）を用いる。同様に、ブロック計算部２１は、パラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）の算出のために、図４（ｂ）に示す参照ブロックＲＢ（ｒｘ，ｒｙ），ＲＢ（ｒｘ＋１，ｒｙ）を用い、パラメータＰＡＲＡＭ＿Ｂ（ｒｘ，ｒｙ−０．５）の算出のために、図４（ｃ）に示す参照ブロックＲＢ（ｒｘ，ｒｙ），ＲＢ（ｒｘ，ｒｙ−１）を用い、パラメータＰＡＲＡＭ＿Ｂ（ｒｘ，ｒｙ＋０．５）の算出のために、図４（ｄ）に示す参照ブロックＲＢ（ｒｘ，ｒｙ），ＲＢ（ｒｘ，ｒｙ＋１）を用いる。
【００５７】
これらのパラメータのうち（４）式で示したパラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）の算出について説明する。なお、他のパラメータの算出も同様の手順により算出できることは明らかである。
【００５８】
画像選択部２２及びブロック切り出し部２３は、制御部１１に制御されて、図４（ｂ）に示す参照ブロックＲＢ（ｒｘ，ｒｙ），ＲＢ（ｒｘ＋１，ｒｙ）を切り出す。差分計算部２４はこれらの参照ブロック同士の差分を求め、絶対値計算部２５は差分結果の絶対値を求める。
【００５９】
ブロック内の全ての画素についての差分計算及び絶対値計算結果が累積加算計算部２６に与えられて累積加算される。こうして、式（４）のパラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）が求められる（ステップＳ７）。
【００６０】
また、制御部１１は、パラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）の理論最大値を求める（ステップＳ８）。特徴量の理論最大値の演算には、（５）式に示すように、対象ブロックと整数画素位置の参照ブロックとのＳＡＤ値を用いる。このＳＡＤ値は、ステップＳ２，Ｓ３において算出され記録されている。制御部１１は、パラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）の理論最大値を求めるために、対象ブロックＳＢ（ｓｘ，ｓｙ）と参照ブロックＲＢ（ｒｘ，ｒｙ）とのＳＡＤ値であるＳＡＤ（ｒｘ，ｒｙ）と、対象ブロックＳＢ（ｓｘ，ｓｙ）と参照ブロックＲＢ（ｒｘ＋１，ｒｙ）とのＳＡＤ値であるＳＡＤ（ｒｘ＋１，ｒｙ）とを領域１３から読出して加算計算部３１に出力する。
【００６１】
加算計算部３１は、２入力の加算によって、パラメータＰＡＲＡＭ＿Ｂの理論最大値を求めて、制御部１４に出力する。パラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）の理論最大値は、図５に示すように、ＳＡＤ（ｒｘ，ｒｙ）＋ＳＡＤ（ｒｘ＋１，ｒｙ）で与えられる。
【００６２】
なお、（５）式は、このパラメータＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）の理論最大値を求めるためのものであるが、図５に示すように、他のパラメータの理論最大値も同様の手順により算出できることは明らかである。
【００６３】
制御部１１は、算出されたパラメータＰＡＲＡＭ＿Ｂ及びその理論最大値を対応させて領域１４，１５に記録する（ステップＳ９）。制御部１１は、ステップＳ１０において、高精度探索に設定した探索範囲の全ての参照ブロックについてパラメータＰＡＲＡＭ＿Ｂ及びその理論最大値を算出したか否かを判定し、算出していない場合には、処理をステップＳ６に戻して、次の参照ブロックについて処理を繰り返す。
【００６４】
高精度探索の探索範囲内の全ての参照ブロックについてパラメータＰＡＲＡＭ＿Ｂ及びその理論最大値が求められると、制御部１１は、各参照ブロックについてパラメータＰＡＲＡＭ＿Ｂとその理論最大値との差分を求める（ステップＳ１１）。制御部１１は、求めた差分が最も小さいパラメータＰＡＲＡＭ＿Ｂを与える参照ブロックを、高精度探索においてＳＡＤ値が最小となる参照ブロック（以下、高精度検出ブロックという）と推定する（ステップＳ１２）。
【００６５】
上述したように、パラメータＰＡＲＡＭ＿ＢはパラメータＰＡＲＡＭ＿Ａと相関が高く、パラメータＰＡＲＡＭ＿Ｂと理論最大値との差が最も小さい参照ブロックは、パラメータＰＡＲＡＭ＿Ａについても最大値が得られると考えられ、ＳＡＤ値が最も小さいブロックであると判定することができる。なお、最終的には、整数精度検出ブロックと高精度検出ブロックとについて対象ブロックとの間で求めたＳＡＤ値を比較することで、ＳＡＤ値が最も小さい参照ブロックを特定する。
【００６６】
このように本実施の形態においては、ＳＡＤに対応する特徴量としてパラメータＰＡＲＡＭ＿Ｂを採用し、パラメータＰＡＲＡＭ＿Ｂとその理論最大値との差分が最も小さいパラメータＰＡＲＡＭ＿Ｂを与える小数画素位置の参照ブロックをＳＡＤ値が最小のブロックと推定する。整数画素位置の参照ブロックを用いて、小数精度のパラメータＰＡＲＡＭ＿Ｂの算出を行うことができ、探索に必要な演算量を著しく低減することができる。しかも、ＳＡＤ演算のみによってパラメータＰＡＲＡＭ＿Ｂの算出を行うことができ、特別なハードウェアを必要とすることなく、演算量の削減が可能である。
【００６７】
なお、上述した実施の形態においては、整数精度探索によって最小ＳＡＤの参照ブロックを特定し、当該参照ブロックの周囲に高精度探索の探索範囲を設定する例を説明したが、高精度探索の探索範囲の決定方法は種々考えられる。例えば、画面全体を高精度探索の探索範囲に設定してもよい。
【００６８】
（第２の実施の形態）
図６は本発明の第２の実施の形態を示すブロック図である。図６において図１と同一の構成要素には同一符号を付して説明を省略する。本実施の形態のハードウェア構成は第１の実施の形態と同様であり、制御部１１が領域１４，１５に第１の実施の形態と異なるパラメータを記憶させると共に、制御部１１によるブロック計算部２１及び加算計算部３１の制御が第１の実施の形態と異なる。
【００６９】
本実施の形態においては、パラメータＰＡＲＡＭ＿Ｂに代えてパラメータＰＡＲＡＭ＿Ｄを採用する。パラメータＰＡＲＡＭ＿Ｄを説明するために、パラメータＰＡＲＡＭ＿Ａに近似した値を有するパラメータＰＡＲＡＭ＿Ｃを考える。下記（６）式は、パラメータＰＡＲＡＭ＿Ｃを示している。
【００７０】
2012156707.tif 000008
図７はパラメータＰＡＲＡＭ＿Ｃを説明するための説明図である。上記（３）式及び（６）式に示すパラメータＰＡＲＡＭ＿Ａ，ＰＡＲＡＭ＿Ｃの絶対値内の第１項は、図７（ａ），（ｂ）の実線に示すブロックＳＢ（ｓｘ，ｓｙ）、ブロックＲＢ（ｒｘ，ｒｙ）間のＳＡＤ値を示している。
【００７１】
パラメータＰＡＲＡＭ＿Ａの絶対値内の第２項は、ブロックＳＢ（ｓｘ，ｓｙ）（図７（ａ）実線）とブロックＲＢ（ｒｘ＋１，ｒｙ）（図７（ｂ）破線）とのＳＡＤ値を示している。一方、（６）式のパラメータＰＡＲＡＭ＿Ｃの絶対値内は、ブロックＳＢ（ｓｘ−１，ｓｙ）（図７（ａ）破線）とブロックＲＢ（ｒｘ，ｒｙ）（図７（ｂ）実線）とのＳＡＤ値を示している。
【００７２】
ブロックＳＢ（ｓｘ，ｓｙ），ＲＢ（ｒｘ＋１，ｒｙ）間のＳＡＤ演算と、ブロックＳＢ（ｓｘ−１，ｓｙ），ＲＢ（ｒｘ，ｒｙ）間のＳＡＤ演算とでは、図７（ａ），（ｂ）の斜線部分において、共通の加算処理が行われている。即ち、これらのＳＡＤ演算により得られるＳＡＤ値は、近似した値になることが予想される。即ち、パラメータＰＡＲＡＭ＿ＡとパラメータＣとは近似した値になるものと考えられる。
【００７３】
そこで、本実施の形態においては、パラメータＰＡＲＡＭ＿Ｃについて、上記パラメータＰＡＲＡＭ＿Ａ，ＰＡＲＡＭ＿Ｂの関係と同様の関係を有するパラメータＰＡＲＡＭ＿Ｄを規定する。即ち、パラメータＰＡＲＡＭ＿Ｄは下記（７）式によって与えられ、パラメータＰＡＲＡＭ＿Ｄの取り得る最大値（理論最大値）は下記（８）式によって与えられる。
【００７４】
2012156707.tif 000009
2012156707.tif 000010
パラメータＰＡＲＡＭ＿Ｃ，ＰＡＲＡＭ＿Ｄの関係は、パラメータＰＡＲＡＭ＿Ａ，ＰＡＲＡＭ＿Ｂの関係と同様であるので、パラメータＰＡＲＡＭ＿Ｄとその最大値との差分が最も小さいパラメータＰＡＲＡＭ＿Ｄを与える参照ブロックについては、パラメータＰＡＲＡＭ＿Ｃも最大値をとり、パラメータＰＡＲＡＭ＿Ａも最大値をとるものと考えられる。そこで、本実施の形態においては、パラメータＰＡＲＡＭ＿Ｄとその最大値との差分が最も小さいパラメータＰＡＲＡＭ＿Ｄを与える参照ブロックを対象ブロックとのＳＡＤ値が最も小さいブロックであるものと推定して、高精度探索の探索結果を得るようになっている。
【００７５】
パラメータＰＡＲＡＭ＿Ｄ及びその最大値は、ＳＡＤ演算のみによって算出することができ、本実施の形態においても、特別な専用のハードウェアを必要とすることなく、演算量を削減することができる。
【００７６】
次に、このように構成された実施の形態の動作について図８のフローチャートを参照して説明する。図８において図３と同一の手順には同一符号を付して説明を省略する。
【００７７】
図８においてステップＳ１〜Ｓ５は整数精度探索のためのステップであり、ステップＳ６〜Ｓ１２は小数精度（高精度）探索のためのステップである。本実施の形態においては、高精度探索において求めるパラメータＰＡＲＡＭ＿Ｄが、原画像内のブロックを用いた演算であることから、整数精度探索処理と高精度探索処理とを並列に実行することが可能である。
【００７８】
制御部１１は、ステップＳ１において整数精度探索用の参照ブロックを指定し、ステップＳ６において小数精度探索用の参照ブロックを指定する。ブロック計算部２１は、ステップＳ２において整数精度のＳＡＤ演算を行い、ステップＳ７において特徴量算出のためのＳＡＤ演算を行う。
【００７９】
ステップＳ７の処理によって、上記（７）式のパラメータＰＡＲＡＭ＿Ｄが求められる。整数精度探索で得たＳＡＤ値及びパラメータＰＡＲＡＭ＿Ｄは、制御部１１によって夫々領域１３，１４に記録される（ステップＳ３，Ｓ９）。
【００８０】
パラメータＰＡＲＡＭ＿Ｃ，ＰＡＲＡＭ＿Ｄの関係は、パラメータＰＡＲＡＭ＿Ａ，ＰＡＲＡＭ＿Ｂの関係と同様であるので、パラメータＰＡＲＡＭ＿ＢとパラメータＰＡＲＡＭ＿Ｄとは略近似した値となる。例えば、以下の式が成立する。
【００８１】
ＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ）＝ＰＡＲＡＭ＿Ｄ（ｒｘ−０．５，ｒｙ）
ＰＡＲＡＭ＿Ｂ（ｒｘ，ｒｙ＋０．５）＝ＰＡＲＡＭ＿Ｄ（ｒｘ，ｒｙ−０．５）
ＰＡＲＡＭ＿Ｂ（ｒｘ＋０．５，ｒｙ＋０．５）＝ＰＡＲＡＭ＿Ｄ（ｒｘ−０．５，ｒｙ−０．５）
ＰＡＲＡＭ＿Ｂ（ｒｘ−０．５，ｒｙ＋０．５）＝ＰＡＲＡＭ＿Ｄ（ｒｘ＋０．５，ｒｙ−０．５）
制御部１１は、整数精度探索に設定した探索範囲内の全参照ブロックについての探索処理が終了すると、処理をステップＳ４からステップＳ５に移行して、整数精度検出ブロックを決定する。また、制御部１１は、小数精度探索に設定した探索範囲内の全参照ブロックについての探索処理が終了すると、処理をステップＳ１０からステップＳ８’に移行して、理論最大値を算出する。式（８）に示すように、パラメータＰＡＲＡＭ＿Ｄの理論最大値は、対象ブロックと参照ブロックとのＳＡＤ値の和であり、制御部１１は、領域１３に記憶させたＳＡＤ値を読出して加算計算部３１に出力する。なお、制御部１１は、当該対象ブロックについて求めたＳＡＤ値だけでなく、理論最大値の演算に用いる対象ブロックについて求めたＳＡＤ値も保持しているものとする。
【００８２】
加算計算部３１は、加算処理によって（８）式の理論最大値を求めて、制御部１１に出力する。制御部１１は、各参照ブロックについて理論最大値とパラメータＰＡＲＡＭ＿Ｄの差分を求め、差分が最も小さいパラメータＰＡＲＡＭ＿Ｄを与える参照ブロックを、高精度検出ブロックとして決定する（ステップＳ１２）。
【００８３】
このように本実施の形態においても、第１の実施の形態と同様の効果を得ることができる。更に、本実施の形態においては、特徴量であるパラメータＰＡＲＡＭ＿Ｄは、原画像のデータのみを用いたＳＡＤ演算によって取得することができ、整数精度探索と小数精度探索とを並列に実行することができ、演算時間を短縮することができるという利点がある。
【００８４】
次に、上記各実施の形態における演算量について説明する。例えば、整数画素精度探索の後、上下左右斜めの８方向のうち、いずれの方向に高精度探索の結果が存在するかを予測する場合の計算量を示す。
【００８５】
特許文献１の技術を採用してパラメータＰＡＲＡＭ＿Ａを求めると、１画素につき、除算、正負判定、除算、正負判定、除算、絶対値計算及び累積加算の７回の演算が必要である。よって、８方向探索すると、
７（演算回数／画素）×１６（画素数）×１６（画素数）×８（探索方向数）
＝１４３３６回  の演算が必要である。
【００８６】
これに対し、第１の実施の形態において採用したパラメータＰＡＲＡＭ＿Ｂの計算では、１画素につき除算、絶対値計算及び累積加算の３回の演算を行えばよい。また、１度計算したパラメータＰＡＲＡＭ＿Ｂを２方向の探索に適用できるので、
３（演算回数／画素）×１６（画素数）×１６（画素数）×４（索探方向数の半分）
＝３０７２回  の演算ですむ。
【００８７】
また、パラメータＰＡＲＡＭ＿Ｅを用いた第２の実施の形態における演算回数は、パラメータＰＡＲＡＭ＿Ｂを用いた場合と同じである。また、パラメータＰＡＲＡＭ＿Ｅは、参照画像の座標に依存しない。従って、パラメータＰＡＲＡＭ＿Ｅを用いた場合には、整数画素精度探索と高精度探索とを並列演算することが可能になる。
【００８８】
図９は上記各実施の形態をエンコーダに適用した例を示すブロック図である。
【００８９】
エンコーダ４０には、第１又は第２の実施の形態の動きベクトル探索装置を含む動き検出部４３が設けられている。制御部４１はエンコーダ全体を制御する。動き検出部４３は、バッファメモリ４２及びバス４７を介して映像信号が与えられて、動画圧縮処理時に動きベクトルを求める。動き補償部４６は、動きベクトルが与えられて、参照画像と原画像との間の動き補償演算を行う。ＤＣＴ/量子化部４４は、圧縮処理時に、離散コサイン変換及び量子化処理を行う。
【符号の説明】
【００９０】
１０…動きベクトル探索装置、１１…制御部、２１…ブロック計算部、２２…画像選択部、２３…ブロック切り出し部、２４…差分計算部、２５…絶対値計算部、２６…累積加算計算部、３１…加算計算部。
【図１】
2012156707.tif 000011
【図２】
2012156707.tif 000012
【図３】
2012156707.tif 000013
【図４】
2012156707.tif 000014
【図５】
2012156707.tif 000015
【図６】
2012156707.tif 000016
【図７】
2012156707.tif 000017
【図８】
2012156707.tif 000018
【図９】
2012156707.tif 000019