(57)【要約】  本発明の演算装置において、基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算装置において、前記基準ブロックのデータを格納する基準ブロックデータ格納部と、前記参照ブロックのデータを格納する参照ブロックデータ格納部と、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算部と、前記相関演算部によって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソート部と、を備え、複数の前記相関演算部にそれぞれ入力される相関閾値と、複数の前記相関演算部によってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算部の動作を停止させる相関演算停止処理を行うことを特徴とする。
2016194828.tif 000002
【特許請求の範囲】
【請求項１】
基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算装置において、
前記基準ブロックのデータを格納する基準ブロックデータ格納部と、
前記参照ブロックのデータを格納する参照ブロックデータ格納部と、
前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算部と、
前記相関演算部によって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソート部と、
を備え、
複数の前記相関演算部にそれぞれ入力される相関閾値と、複数の前記相関演算部によってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算部の動作を停止させる相関演算停止処理を行うことを特徴とする、演算装置。
【請求項２】
前記相関閾値は、前記ソート部から出力されることを特徴とする、請求項１に記載の演算装置。
【請求項３】
前記相関閾値は、前記ソート部が保持するソート後の前記相関値のうち最も相関が高い相関値であることを特徴とする、請求項２に記載の演算装置。
【請求項４】
前記相関閾値を制御する制御部、を備え、
前記相関閾値は、前記制御部から出力されることを特徴とする、請求項１に記載の演算装置。
【請求項５】
前記相関演算停止処理は、前記相関演算部の動作クロックを停止させることによって前記相関演算部の動作を停止させる処理であることを特徴とする、請求項１に記載の演算装置。
【請求項６】
前記相関演算停止処理は、前記相関演算部へ入力されるデータを、片方は最大値、もう片方は最小値にすることによって前記相関演算部の動作を停止させる処理であることを特徴とする、請求項１に記載の演算装置。
【請求項７】
前記相関演算停止処理は、次の前記基準ブロックと前記参照ブロックとの間の相関演算が開始される場合に終了する処理であることを特徴とする、請求項１に記載の演算装置。
【請求項８】
基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算方法において、
前記基準ブロックのデータを格納する基準ブロックデータ格納ステップと、
前記参照ブロックのデータを格納する参照ブロックデータ格納ステップと、
前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算ステップと、
前記相関演算ステップによって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソートステップと、
を有し、
複数の前記相関演算ステップにそれぞれ入力される相関閾値と、複数の前記相関演算ステップによってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算ステップの動作を停止させる相関演算停止ステップと、
を有することを特徴とする、演算方法。
【請求項９】
コンピュータに、
基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算ステップと、
前記基準ブロックのデータを格納する基準ブロックデータ格納ステップと、
前記参照ブロックのデータを格納する参照ブロックデータ格納ステップと、
前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算ステップと、
前記相関演算ステップによって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソートステップと、
複数の前記相関演算ステップにそれぞれ入力される相関閾値と、複数の前記相関演算ステップによってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算ステップの動作を停止させる相関演算停止ステップと、
を実行させるための、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置、演算方法、及びプログラムに関する。本願は、２０１５年６月３日に、日本国に出願された特願２０１５−１１３２１０号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【０００２】
動画像の手ぶれ補正や動画像の圧縮の分野において、動きベクトルを算出した結果を利用する方法が知られている。動きベクトルの演算方法としては、ブロックマッチング法を利用する方法が広く知られている。ブロックマッチング法とは、比較する２枚の画像をそれぞれ複数の領域に切り分け、切り分けた領域毎に２枚の画像の間の相関値を演算する方法である。その演算結果から得られた相関値に基づいて、動きベクトルが算出される。
このようなブロックマッチング法を利用した動きベクトル検出装置が、例えば、特許文献１において提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】日本国特許第４５４７３２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
２枚の画像の間の相関値を演算する場合、ブロックマッチング法によれば、正確な相関値の演算が可能である。しかしながら、ブロックマッチング法による相関演算においては、演算対象となる画像の領域が広くなるほど、演算量がより膨大になる。そのため、相関値を演算する演算回路は常時動作し続けることになり、演算回路が消費する消費電力はより大きくなるという問題がある。【０００５】
本発明は上記の点に鑑みてなされたものであり、演算回路の消費電力を削減することができる演算装置、演算方法、及びプログラムを提供する。
【課題を解決するための手段】
【０００６】
本発明の第一の態様に係る演算装置は、基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算装置において、前記基準ブロックのデータを格納する基準ブロックデータ格納部と、前記参照ブロックのデータを格納する参照ブロックデータ格納部と、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算部と、前記相関演算部によって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソート部と、を備え、複数の前記相関演算部にそれぞれ入力される相関閾値と、複数の前記相関演算部によってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算部の動作を停止させる相関演算停止処理を行うことを特徴とする。【０００７】
本発明の第二の態様によれば、第一の態様に係る演算装置では、前記相関閾値は、前記ソート部から出力されることを特徴とする。【０００８】
本発明の第三の態様によれば、第二の態様に係る演算装置では、前記相関閾値は、前記ソート部が保持するソート後の前記相関値のうち最も相関が高い相関値であることを特徴とする。【０００９】
（本発明の第四の態様によれば、第一の態様に係る演算装置は、前記相関閾値を制御する制御部、を備え、前記相関閾値は、前記制御部から出力されることを特徴とする。【００１０】
本発明の第五の態様によれば、第一の態様に係る演算装置では、前記相関演算停止処理は、前記相関演算部の動作クロックを停止させることによって前記相関演算部の動作を停止させる処理であることを特徴とする。【００１１】
本発明の第六の態様によれば、第一の態様に係る演算装置では、前記相関演算停止処理は、前記相関演算部へ入力されるデータを、片方は最大値、もう片方は最小値にすることによって前記相関演算部の動作を停止させる処理であることを特徴とする。【００１２】
本発明の第一七の態様によれば、第一の態様に係る演算装置では、前記相関演算停止処理は、次の前記基準ブロックと前記参照ブロックとの間の相関演算が開始される場合に終了する処理であることを特徴とする。【００１３】
本発明の第八の態様に係る演算方法は、基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算方法において、前記基準ブロックのデータを格納する基準ブロックデータ格納ステップと、前記参照ブロックのデータを格納する参照ブロックデータ格納ステップと、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算ステップと、前記相関演算ステップによって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソートステップと、を有し、複数の前記相関演算ステップにそれぞれ入力される相関閾値と、複数の前記相関演算ステップによってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算ステップの動作を停止させる相関演算停止ステップと、を有することを特徴とする。【００１４】
本発明の第九の態様に係るプログラムは、コンピュータに、基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算ステップと、前記基準ブロックのデータを格納する基準ブロックデータ格納ステップと、前記参照ブロックのデータを格納する参照ブロックデータ格納ステップと、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算ステップと、前記相関演算ステップによって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持するソートステップと、複数の前記相関演算ステップにそれぞれ入力される相関閾値と、複数の前記相関演算ステップによってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算ステップの動作を停止させる相関演算停止ステップと、を実行させる。
【発明の効果】
【００１５】
本発明によれば、演算回路の消費電力を削減することができる。
【図面の簡単な説明】
【００１６】
【図１】ブロックマッチング法を用いた２枚の画像の間の相関演算の一例を示す概略図である。
【図２Ａ】ブロックマッチング法における相関演算の演算量の一例を示す概略図である。
【図２Ｂ】ブロックマッチング法における相関演算の演算量の一例を示す概略図である。
【図３】本発明の第１の実施形態に係る演算装置による相関演算の一例を示す概略図である。
【図４】本発明の第１の実施形態に係る演算装置による相関演算の一例を示す概略図である。
【図５】本発明の第１の実施形態に係る演算装置による相関演算の一例を示す概略図である。
【図６】本発明の第１の実施形態に係る演算装置の構成の一例を示す図である。
【図７】本発明の第１の実施形態に係る演算装置１の差分絶対値算出部３０１へ輝度値データが入力されるタイミングの一例を示すタイミングチャートである。
【図８】本発明の第１の実施形態に係る演算装置１のソート部４０の構成の一例を示す図である。
【図９】本発明の第１の実施形態に係る演算装置１による相関演算の一例を示す概略図である。
【図１０】本発明の第１の実施形態に係る演算装置１による相関演算の一例を示す概略図である。
【図１１】本発明の第１の実施形態に係る演算装置１による相関演算の一例を示す概略図である。
【図１２】本発明の第１の実施形態に係る演算装置１の相関演算部３０及びソート部４０の構成の一例を示す図である。
【図１３】本発明の第１の実施形態に係る演算装置１の相関演算部３０の演算停止動作の一例を示す図である。
【図１４】本発明の第１の実施形態に係る演算装置１の動作の一例を示すフローチャートである。
【図１５】本発明の第２の実施形態に係る演算装置１の相関演算部３０の演算停止動作の一例を示す図である。
【図１６】本発明の第３の実施形態に係る演算装置１の相関演算部３０の演算停止動作の一例を示す図である。
【発明を実施するための形態】
【００１７】
まず、図面を参照してブロックマッチング法の簡単な原理を説明する。
ブロックマッチング法とは、比較する２枚の画像のうち、少なくとも一方の画像を複数の領域に切り分け、２枚の画像の間の相関値を各領域ごとに演算する方法である。以下、比較する２枚の画像のうち、一方を基準フレーム、他方を参照フレームと呼ぶ。
ブロックマッチング法では、基準フレームにおける特定の領域（基準ブロック）と、参照フレーム内における特定の領域（参照ブロック）との間で相関演算が行われる。基準ブロックと参照ブロックとは、等しい領域サイズを有する。
【００１８】
相関演算には、一般的に、ＳＡＤ（Ｓｕｍ  ｏｆ  Ａｂｕｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ；差分絶対値和演算）、ＳＳＤ（Ｓｕｍ  ｏｆ  Ｓｑｕａｒｅｄ  Ｄｉｆｆｅｒｅｎｃｅ；差分二乗和演算）、ＮＣＣ（Ｎｏｒｍａｌｉｚｅｄ  Ｃｒｏｓｓ−Ｃｏｒｒｅｌａｔｉｏｎ；正規化相互相関）、またはＺＮＣＣ（Ｚｅｒｏ−ｍｅａｎｓ  Ｎｏｒｍａｌｉｚｅｄ  Ｃｒｏｓｓ−Ｃｏｒｒｅｌａｔｉｏｎ；零平均正規化相互相関）、等の演算方法が用いられる。
ブロックマッチング法によって、参照ブロックと最も相関の高い基準ブロック（の位置）を特定したり、動きベクトルを検出したりすることができる。
【００１９】
以下、説明を簡略化するために、本例における参照フレームの領域サイズは、基準フレームよりも小さい領域サイズであるものとする。また、参照フレームと参照ブロックとは、等しい領域サイズであるものとする。すなわち、参照フレーム全体が１つの参照ブロックであるものとする。
【００２０】
図１は、ブロックマッチング法を用いた２枚の画像の間の相関演算の一例を示す概略図である。
相関演算を行う場合には、例えば、基準フレームを示す基準フレームＹデータ１（Ｉ）内の１つの基準ブロック（ここでは、図１の画像ｐ１に示すような最も左上の基準ブロック）に対して、参照ブロック（参照フレームＹデータ２（Ｔ））を設定する。そして、この基準ブロックと参照ブロックとの間の相関値を演算する。なお、本例においては、求める相関値はＳＡＤ値であるものとする。また、本例におけるＳＡＤ値とは、基準ブロックデータと参照ブロックデータのそれぞれの画素における輝度値の差の絶対値を合計することによって算出される。そして、ＳＡＤ値が小さいほど、基準ブロックに含まれる画像と参照ブロックに含まれる画像の間の相関がより高いことを表す。
【００２１】
そして、基準フレームＹデータ１（Ｉ）内で上記の基準ブロックから水平方向に１画素ずれた領域である次の基準ブロックと、参照ブロックとの間のＳＡＤ値を演算する（図１の画像ｐ２）。続けて同様に、水平方向に右へ更に１画素ずつずれた基準ブロックと、参照ブロックとの間のＳＡＤ値を順に演算していく。そして、基準フレームＹデータ１（Ｉ）内で右端の基準ブロックに到達した後は（図１の画像ｐ３）、再び基準フレームＹデータ１（Ｉ）内で左端の基準ブロックであって垂直方向に下へ１画素ずつずれた基準ブロックと、参照ブロックとの間のＳＡＤ値を演算する（図１の画像ｐ４）。続けて同様に、水平方向に右へ１画素ずつずれた基準ブロックと、参照ブロックとの間のＳＡＤ値を順に演算していく。上記の処理を繰り返して、基準フレームＹデータ１（Ｉ）内で最も右下の基準ブロックと参照ブロックとの間のＳＡＤ値を演算したところで、全ての基準ブロックと参照ブロックとの間のＳＡＤ値の演算が完了する（図１の画像ｐ９）。
【００２２】
以上の処理によって算出された各ＳＡＤ値は、用途に応じて種々の統計処理が施され、利用される。例えば、参照ブロックに最も類似する基準ブロックを特定するために、算出されたＳＡＤ値の中の最小値が求められたり、評価値として利用するために、算出されたＳＡＤ値を小さい順に並べ替えられたりして利用される。または、演算された各ＳＡＤ値は、動きベクトルを算出するために利用される。
【００２３】
上述したように、ブロックマッチング法では、ＳＡＤ値を演算する画像の領域がより広くなるほど、演算量はより多くなる。そのため、ＳＡＤ値を演算する演算回路は常時動作し続けることになり、演算回路が消費する消費電力はより大きくなる。
【００２４】
図２Ａ及び図２Ｂは、ブロックマッチング法における相関演算の演算量の一例を示す概略図である。
例えば、基準フレームＹデータ１（Ｉ）が、水平方向に２０画素及び垂直方向に２０画素を有する４００画素の画像であるものとする（図２Ａ）。また、例えば、参照フレームＹデータ２（Ｔ）が、水平方向に１０画素及び垂直方向に１０画素を有する画像であるものとする（図２Ｂ）。すなわち、参照ブロック及び各基準ブロックも、水平方向に１０画素及び垂直方向に１０画素を有する画像であるものとする。
【００２５】
この場合、１つの基準ブロックと参照ブロックとの間のＳＡＤ値を演算するＳＡＤ演算処理には、１００（＝１０×１０）回の輝度値の減算処理、１００回（＝１０×１０）の差分絶対値演算処理、及び９９（＝１００−１）回の差分絶対値の加算処理が含まれる。
そして、基準フレーム内には合計１２１（＝１１×１１）個の基準ブロックが含まれるため、基準フレームに含まれる各基準ブロックと参照ブロックとの間のＳＡＤ値を演算するためには、上記のＳＡＤ演算処理を１２１回行う必要がある。
【００２６】
上記は、基準フレームＹデータ１（Ｉ）が４００画素である場合の例であるが、例えば、昨今のコンパクトデジタルカメラが撮影する画像には１，５００万画素を超える画素数を有する画像も珍しくなく、実際には膨大な量の演算が繰り返される。
【００２７】
（第１の実施形態）
以下、第１の実施形態について図面を参照しながら説明する。
図３、図４、及び図５は、本発明の第１の実施形態に係る演算装置による相関演算の一例を示す概略図である。
以下に例示する演算装置１は、図２Ａに示すような、水平方向に２０画素及び垂直方向に２０画素を有する画像を示すデータである基準フレームＹデータ１（Ｉ）と、図２Ｂに示すような、水平方向に１０画素及び垂直方向に１０画素を有する画像を示すデータである参照フレームＹデータ２（Ｔ）と、の間のＳＡＤ値を演算する演算装置である。
第１の実施形態に係る演算装置１は、速い演算速度を確保するため、ＳＡＤ値を演算するための複数の演算回路を搭載している。例えば、第１の実施形態に係る演算装置１は、画素の輝度値の差の絶対値（以下、差分絶対値という）を算出することができる演算回路（以下、差分絶対値算出回路という）を１１０個搭載している。よって、演算装置１は、同時に１１０画素分の差分絶対値を演算することができる。
【００２８】
図３の画像ｐａ１は、基準フレームＹデータ１（Ｉ）の最も左上の基準ブロックが参照ブロックとの比較領域として設定されていることを示す。第１の実施形態に係る演算装置は、基準ブロックの１０画素からなる最も上のラインの各画素について、基準ブロックと参照ブロックとの間の画素の差分絶対値を演算する。そして、演算装置は、演算した差分絶対値（合計１０画素分）を合計してＳＡＤ値を算出する（以下、この加算処理を水平方向加算という）。
【００２９】
図３の画像ｐａ１に示す１０画素分の差分絶対値の演算を１回で同時に行うためには、１０個の差分絶対値算出回路が必要となる。更に、第１の実施形態に係る演算装置１が、同時に図３の画像ｐａ１から図３の画像ｐａ１１に示す１１０（＝１０×１１）画素分の差分絶対値の演算を１回で同時に行うためには、１１０個の差分絶対値算出回路が必要となる。
【００３０】
上述したように、第１の実施形態に係る演算装置１は、１１０個の差分絶対値算出回路を備え、基準フレームＹデータ１（Ｉ）の中の１つのライン（行）に含まれる画素に対する１１０回分の差分絶対値の演算を１回で同時に行うことができる。
これにより、演算装置１は、１回の演算で図３の画像ｐａ１から図３の画像ｐａ１１までの各差分絶対値の演算及び水平方向加算を行うことができ、１回の演算で１１個のＳＡＤ値を算出することができる。
【００３１】
第１の実施形態に係る演算装置は、続いて、基準フレームＹデータ１（Ｉ）の上から２番目のラインの１１０回分の差分絶対値の演算を１回で同時に行う。すなわち、第１の実施形態に係る演算装置は、図３の画像ｐａ１２から図３の画像ｐａ２２に示す１１０画素分の差分絶対値の演算、および１１回の水平方向加算を１回の処理で同時に行う。
そして、演算装置は、図３の画像ｐａ１２から図３の画像ｐａ２２において、それぞれ水平方向加算により算出したＳＡＤ値を、上記図３の画像ｐａ１から図３の画像ｐａ１１において算出したＳＡＤ値に、それぞれ加算する（以下、この加算処理を垂直方向加算という）。
【００３２】
さらに、上記の処理を繰り返すことにより、第１の実施形態に係る演算装置は、図３の画像ｐａ１から図３の画像ｐａ１１０までのＳＡＤ演算を、合計１０回の処理回数で行うことができる。したがって、第１の実施形態に係る演算装置は、参照ブロックと基準フレームＹデータ１（Ｉ）内の最も上段に位置する１１個の基準ブロックとの間のＳＡＤ演算を、合計１０回の処理回数で行うことができる。
これにより、演算装置は、参照ブロックと基準フレームＹデータ１（Ｉ）内の最も上段に位置する１１個の基準ブロックとの間のＳＡＤ値（ＳＡＤ値ｓ００１、ＳＡＤ値ｓ００２、・・・、ＳＡＤ値ｓ０１１）を算出することができる。
【００３３】
ここで、第１の実施形態に係る演算装置は、算出した１１個のＳＡＤ値（ＳＡＤ値ｓ００１、ＳＡＤ値ｓ００２、・・・、ＳＡＤ値ｓ０１１）を、後述するソート部４０によって、値の小さい順（すなわち、相関が高い順）に並べ替える。
そして、ソート部４０は、例えば、このうち値が小さい方から上位１０位までのＳＡＤ値のみを保持する。
【００３４】
続けて同様に、第１の実施形態に係る演算装置は、参照ブロックと基準フレームＹデータ１（Ｉ）内で垂直方向に下へ１画素ずらしたの領域にある１１個の基準ブロックとの間のＳＡＤ演算を、合計１０回の処理回数で行う（図４の画像ｐａ１１１から図４の画像ｐａ２２０まで）。
これにより、演算装置は、参照ブロックと基準フレームＹデータ１（Ｉ）内で垂直方向に下へ１画素ずらした領域にある１１個の基準ブロックとの間のＳＡＤ値（ＳＡＤ値ｓ０１２、ＳＡＤ値ｓ０１３、・・・、ＳＡＤ値ｓ０２２）を算出することができる。
【００３５】
ここで、第１の実施形態に係る演算装置１は、算出した１１個のＳＡＤ値（ＳＡＤ値ｓ０１２、ＳＡＤ値ｓ０１３、・・・、ＳＡＤ値ｓ０２２）に加え、それ以前に算出しソート部に保持している１０個のＳＡＤ値を含めて、後述するソート部４０によって、値の小さい順（すなわち、相関が高い順）に並べ替える。
そして、ソート部４０は、例えば、このうち値が小さい方から上位１０位までのＳＡＤ値のみを保持する。
【００３６】
そして、第１の実施形態に係る演算装置１は、参照ブロックと基準フレームＹデータ１（Ｉ）の最も下段に位置する１１個の基準ブロックとの間のＳＡＤ演算（図５の画像ｐａ１１０１から図５の画像ｐａ１２１０）まで行うことにより、参照ブロックと基準フレームＹデータ１（Ｉ）内の１２１個の全ての基準ブロックとの間のＳＡＤ演算が終了する。
したがって、第１の実施形態に係る演算装置１は、参照ブロックと基準フレームＹデータ１（Ｉ）内の１２１個の全ての基準ブロックとの間のＳＡＤ演算を、合計１１０（＝１０×１１）回の処理回数で行うことができる。
【００３７】
以上により、演算装置１は、基準フレームＹデータ１（Ｉ）内の１２１個全ての基準ブロックと参照ブロックとの間のＳＡＤ値（ＳＡＤ値ｓ００１、ＳＡＤ値ｓ００２、・・・、ＳＡＤ値ｓ１２１）の中で、例えば、値の小さい（すなわち、相関が高い）ほうから上位１０位のＳＡＤ値を特定することができる。すなわち、演算装置１は、基準フレームＹデータ１（Ｉ）内の１２１個の基準ブロックの中で、参照ブロックと相関が高い基準ブロックを特定することができる。
【００３８】
（演算装置１の基本的な構成）
次に、演算装置１の基本的な構成について図面を参照しながら説明する。
図６は、本発明の第１の実施形態に係る演算装置１の構成の一例を示す図である。
図示するように、演算装置１は、基準ブロックデータ格納部１０と、参照ブロックデータ格納部２０と、相関演算部３０と、ソート部４０と、を含んで構成される。
【００３９】
基準ブロックデータ格納部１０は、基準フレームデータＹ１（Ｉ）から切り分けられた（分割された）各基準ブロックのデータを格納する。基準ブロックデータ格納部１０は、例えば、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、またはＳＤＲＡＭ（Ｓｙｎｃｈｒｏｎｏｕｓ  ＤＲＡＭ）によって構成される。
【００４０】
参照ブロックデータ格納部２０は、参照フレームデータＹ２（Ｔ）から切り分けられた（分割された）各参照ブロックのデータを格納する。参照ブロックデータ格納部２０も、例えば、ＤＲＡＭ、ＳＲＡＭ、またはＳＤＲＡＭによって構成される。
【００４１】
相関演算部３０は、基準ブロックデータ格納部１０から取得する基準ブロックのデータと、参照ブロックデータ格納部２０から取得する参照ブロックのデータと、の間の相関演算を行う。図６に示す演算装置１は、ＳＡＤ演算をする回路を示している。この場合、相関演算部３０は、各基準ブロックと参照ブロックに含まれる画素毎の輝度値の差の絶対値（差分絶対値）を演算し、各基準ブロック毎に差分絶対値の総和を求めることによって得られるＳＡＤ値をソート部４０へ出力する。
なお、相関演算部３０の構成の詳細な説明は後述する。
【００４２】
ソート部４０は、相関演算部３０から取得した各基準ブロック毎のＳＡＤ値を、値の小さい順（相関の高い順）に並べ替える。そして、ソート部４０は、並べ替えたＳＡＤ値のうち、予め定められた件数分（例えば、上位１０件分）のＳＡＤ値を記憶する。
そして、ソート部４０は、相関演算部３０からＳＡＤ値を取得する毎に、その都度、取得したＳＡＤ値に、既に記憶しているＳＡＤ値を含めて、値の小さい順（相関の高い順）にＳＡＤ値を並べ替える。そして、ソート部４０は、並べ替えたＳＡＤ値のうち、予め定められた件数分（例えば、上位１０件分）のＳＡＤ値を特定し、特定したＳＡＤ値によって記憶していたＳＡＤ値を上書き更新する。
【００４３】
（相関演算部の構成）
次に、相関演算部３０の構成について図６を参照しながら説明する。
図示するように、相関演算部３０は、１１０個の差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）と、１１個の水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）と、１１個の垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）と、１１個の保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）と、を含んで構成される。
【００４４】
差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）は、基準ブロックデータ格納部１０から基準ブロックの中の１画素分の輝度値を示すデータ（図６の、Ｙ１からＹ２０）を、また、参照ブロックデータ格納部２０から参照ブロックの中の１画素分の輝度値を示すデータ（図６の、ｙ１からｙ１０）を取得する。差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）は、取得した２つの輝度値の差分絶対値を演算し、演算結果を水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）へ出力する。
【００４５】
例えば、差分絶対値算出部３０１−１から差分絶対値算出部３０１−１０に入力されるデータは、図３の画像ｐａ１、図３の画像ｐａ１２、図３の画像ｐａ１００、図４の画像ｐａ１１１、図４の画像ｐａ１２２、図４の画像ｐａ２１０、図５の画像ｐａ１１０１、図５の画像ｐａ１１１２、または図５の画像ｐａ１２００等に示すように、基準ブロックが、基準フレームの最も左端にある場合の、１ライン分のデータである。
【００４６】
同様に、例えば、差分絶対値算出部３０１−１１から差分絶対値算出部３０１−２０に入力されるデータは、図３の画像ｐａ２、図３の画像ｐａ１３、図３の画像ｐａ１０１、図４の画像ｐａ１１２、図４の画像ｐａ１２３、図４の画像ｐａ２１１、図５の画像ｐａ１１０２、図５の画像ｐａ１１１３、または図５の画像ｐａ１２０１等に示すように、基準ブロックが、基準フレームの中で左端から１画素分右にずれた位置にある場合の、１ライン分のデータである。
【００４７】
同様に、例えば、差分絶対値算出部３０１−１１から差分絶対値算出部３０１−２０に入力されるデータは、図３の画像ｐａ１１、図３の画像ｐａ２２、図３の画像ｐａ１１０、図４の画像ｐａ１２１、図４の画像ｐａ１３２、図４の画像ｐａ２２０、図５の画像ｐａ１１１１、図５の画像ｐａ１１２２、または図５の画像ｐａ１２１０等に示すように、基準ブロックが、基準フレームの最も右端にある場合の、１ライン分のデータである。
【００４８】
これにより、相関演算部３０は、１１０個の差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）で、１度に１１０個の差分絶対値の演算をすることによって、基準フレームの１ライン分の差分絶対値の演算を１度に行うことができる。
【００４９】
水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）は、１０個の差分絶対値算出部３０１からそれぞれ取得した１０個の差分絶対値を合算することによって得られるＳＡＤ値を算出し、垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）へ出力する。
【００５０】
例えば、水平方向加算部３０２−１は、差分絶対値算出部３０１−１から差分絶対値算出部３０１−１０までの差分絶対値算出部３０１が出力した差分絶対値を合算してＳＡＤ値を算出する。このＳＡＤ値は、例えば、図３の画像ｐａ１、図３の画像ｐａ１２、図３の画像ｐａ１００、図４の画像ｐａ１１１、図４の画像ｐａ１２２、図４の画像ｐａ２１０、図５の画像ｐａ１１０１、図５の画像ｐａ１１１２、または図５の画像ｐａ１２００等に示すように、基準ブロックが、基準フレームの最も左端にある場合の、１ライン分について演算したＳＡＤ値である。
【００５１】
同様に、例えば、水平方向加算部３０２−２は、差分絶対値算出部３０１−１１から差分絶対値算出部３０１−２０までの差分絶対値算出部３０１が出力した差分絶対値を合算してＳＡＤ値を算出する。このＳＡＤ値は、例えば、図３の画像ｐａ２、図３の画像ｐａ１３、図３の画像ｐａ１０１、図４の画像ｐａ１１２、図４の画像ｐａ１２３、図４の画像ｐａ２１１、図５の画像ｐａ１１０２、図５の画像ｐａ１１１３、または図５の画像ｐａ１２０１等に示すように、基準ブロックが、基準フレームの中で左端から１画素分右にずれた位置にある場合の、１ライン分について演算したＳＡＤ値である。
【００５２】
同様に、例えば、水平方向加算部３０２−１１は、差分絶対値算出部３０１−１０１から差分絶対値算出部３０１−１１０までの差分絶対値算出部３０１が出力した差分絶対値を合算してＳＡＤ値を算出する。このＳＡＤ値は、例えば、図３の画像ｐａ１１、図３の画像ｐａ２２、図３の画像ｐａ１１０、図４の画像ｐａ１２１、図４の画像ｐａ１３２、図４の画像ｐａ２２０、図５の画像ｐａ１１１１、図５の画像ｐａ１１２２、または図５の画像ｐａ１２１０等に示すように、基準ブロックが、基準フレームの最も右端にある場合の、１ライン分について演算したＳＡＤ値である。
【００５３】
垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）は、水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）から、それぞれＳＡＤ値を取得し、取得したＳＡＤ値を後述する保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）にそれぞれ記憶されたＳＡＤ値に加算する。そして、垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）は、保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）にそれぞれ記憶しているＳＡＤ値を、加算した後のＳＡＤ値で、上書き更新させる。
【００５４】
例えば、垂直方向加算部３０３−１は、水平方向加算部３０２−１からＳＡＤ値を取得し、取得したＳＡＤ値を後述する保持部３０４−１に記憶されたＳＡＤ値に加算する。そして、垂直方向加算部３０３−１は、保持部３０４−１に記憶されたＳＡＤ値を、加算した後のＳＡＤ値で、上書き更新させる。
【００５５】
同様に、例えば、垂直方向加算部３０３−２は、水平方向加算部３０２−２からＳＡＤ値を取得し、取得したＳＡＤ値を後述する保持部３０４−２に記憶されたＳＡＤ値に加算する。そして、垂直方向加算部３０３−２は、保持部３０４−２に記憶されたＳＡＤ値を、加算した後のＳＡＤ値で、上書き更新させる。
【００５６】
同様に、例えば、垂直方向加算部３０３−１１は、水平方向加算部３０２−１１からＳＡＤ値を取得し、取得したＳＡＤ値を後述する保持部３０４−１１に記憶されたＳＡＤ値に加算する。そして、垂直方向加算部３０３−１１は、保持部３０４−１１に記憶されたＳＡＤ値を、加算した後のＳＡＤ値で、上書き更新させる。
【００５７】
保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）は、それぞれＳＡＤ値を記憶する。保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）は、それぞれ、ある基準ブロックと参照ブロックとの間のＳＡＤ値を演算する過程における、一時記憶領域として機能する。
【００５８】
保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）は、垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）から、それぞれ１０回のＳＡＤ値の入力がなされた場合（すなわち、最初にＳＡＤ値が入力された後、９回のＳＡＤ値の上書き更新がなされた場合）、その時点でのＳＡＤ値をソート部４０へ出力する。そして、保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）は、記憶しているＳＡＤ値を初期化する（値を０にする）。
【００５９】
例えば、保持部３０４−１は、垂直方向加算部３０３−１から１０回のＳＡＤ値の入力がなされたことによって、１０ライン（行）からなる基準ブロックと参照ブロックとの間のＳＡＤ演算が完了したものと判定し、そのＳＡＤ演算結果をソート部４０へ出力する。そして、保持部３０４−１は、記憶しているＳＡＤ値を初期化する（値を０にする）。
保持部３０４−１がＳＡＤ値を演算する対象となる基準ブロックは、例えば、図３の画像ｐａ１、図３の画像ｐａ１２、図３の画像ｐａ１００、図４の画像ｐａ１１１、図４の画像ｐａ１２２、図４の画像ｐａ２１０、図５の画像ｐａ１１０１、図５の画像ｐａ１１１２、または図５の画像ｐａ１２００等に示すように、基準フレームの最も左端に基準ブロックが位置している場合の基準ブロックである。
【００６０】
同様に、例えば、保持部３０４−２は、垂直方向加算部３０３−２から１０回のＳＡＤ値の入力がなされたことによって、１０ライン（行）からなる基準ブロックと参照ブロックとの間のＳＡＤ演算が完了したものと判定し、そのＳＡＤ演算結果をソート部４０へ出力する。そして、保持部３０４−２は、記憶しているＳＡＤ値を初期化する（値を０にする）。
保持部３０４−２がＳＡＤ値を演算する対象となる基準ブロックは、例えば、図３の画像ｐａ２、図３の画像ｐａ１３、図３の画像ｐａ１０１、図４の画像ｐａ１１２、図４の画像ｐａ１２３、図４の画像ｐａ２１１、図５の画像ｐａ１１０２、図５の画像ｐａ１１１３、または図５の画像ｐａ１２０１等に示すように、基準フレームの中で左端から１画素分右にずれた位置にある場合の基準ブロックである。
【００６１】
同様に、例えば、保持部３０４−１１は、垂直方向加算部３０３−１１から１０回のＳＡＤ値の入力がなされたことによって、１０ライン（行）からなる基準ブロックと参照ブロックとの間のＳＡＤ演算が完了したものと判定し、そのＳＡＤ演算結果をソート部４０へ出力する。そして、保持部３０４−１１は、記憶しているＳＡＤ値を初期化する（値を０にする）。
保持部３０４−１１がＳＡＤ値を演算する対象となる基準ブロックは、例えば、図３の画像ｐａ１１、図３の画像ｐａ２２、図３の画像ｐａ１１０、図４の画像ｐａ１２１、図４の画像ｐａ１３２、図４の画像ｐａ２２０、図５の画像ｐａ１１１１、図５の画像ｐａ１１２２、または図５の画像ｐａ１２１０等に示すように、基準フレームの最も右端に基準ブロックが位置している場合の基準ブロックである。
【００６２】
以上により、第１の実施形態に係る演算装置１の相関演算部３０は、基準ブロックデータ格納部１０及び参照ブロックデータ格納部２０からの１０回の輝度値データの入力に基づいて、１１個の基準ブロックと参照ブロックとの間のＳＡＤ演算結果をそれぞれ出力することができる。
【００６３】
図７は、本発明の第１の実施形態に係る演算装置１の差分絶対値算出部３０１へ輝度値データが入力されるタイミングの一例を示すタイミングチャートである。
図示するように、差分絶対値算出部３０１−１へは輝度値データＹ（０，０）とｙ（０，０）、差分絶対値算出部３０１−２へは輝度値データＹ（０，１）とｙ（０，１）、・・・、及び差分絶対値算出部３０１−１１０へは輝度値データＹ（０，１９）とｙ（０，９）が、同一のタイミングで入力される。
【００６４】
図示するように、例えば、差分絶対値算出部３０１−１には、まず始めに基準ブロックの１画素分の輝度値であるＹ（０，０）が入力される。ここで、「（０，０）」とは、基準ブロックにおける座標を表す。「（０，０）」は、基準ブロックの中で、最も左上の画素から、垂直方向に０画素分、及び水平方向に０画素分を移動させた位置の座標を表す。
すなわち、Ｙ（０，０）は、基準ブロックの中の最も左上の画素の輝度値を表すデータである。
【００６５】
同様に、例えば、差分絶対値算出部３０１−１には、まず始めに参照ブロックの１画素分の輝度値であるｙ（０，０）が入力される。同様に、「（０，０）」とは、参照ブロックにおける座標を表す。「（０，０）」は、参照ブロックの中で、最も左上の画素から、垂直方向に０画素分、及び水平方向に０画素分を移動させた位置の座標を表す。すなわち、ｙ（０，０）は、参照ブロックの中の最も左上の画素の輝度値を表すデータである。
【００６６】
同様に、例えば、差分絶対値算出部３０１−１１０には、まず始めに輝度値データＹ（０，１９）が入力される。「（０，１９）」は、参照ブロックの中で、最も左上の画素から、垂直方向に０画素分、及び水平方向に１９画素分を移動させた位置の座標を表す。すなわち、Ｙ（０，１９）は、２０画素×２０画素からなる参照ブロックの中の最も右上の画素の輝度値を表すデータである。
同様に、例えば、差分絶対値算出部３０１−１１０には、まず始めに輝度値データｙ（０，９）が入力される。「（０，９）」は、参照ブロックの中で、最も右上の画素から、垂直方向に０画素分、及び水平方向に９画素分を移動させた位置の座標を表す。すなわち、ｙ（０，９）は、１０画素×１０画素からなる参照ブロックの中の最も右上の画素の輝度値を表すデータである。
【００６７】
そして、図示するように、差分絶対値算出部３０１−１へ輝度値データＹ（１９，０）とｙ（９，０）、差分絶対値算出部３０１−２へ輝度値データＹ（１９，１）とｙ（９，１）、・・・、及び差分絶対値算出部３０１−１１０へ輝度値データＹ（１９，１９）とｙ（９，９）が同一のタイミング入力されたところで、基準フレーム内の１２１個の全ての基準ブロックと参照ブロックとの間のＳＡＤ演算するための全ての輝度値データの入力が終了する。
【００６８】
（ソート部の構成）
次に、ソート部４０の構成について図面を参照しながら説明する。
図８は、本発明の第１の実施形態に係る演算装置１のソート部４０の構成の一例を示す図である。
図示するように、ソート部４０は、ソート実行部４０１と、ｎ個の保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）と、を含んで構成される。
【００６９】
ソート実行部４０１は、相関演算部３０の１１個の保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）から、１１個の各基準ブロック毎のＳＡＤ値を表すデータを、同一のタイミングで取得する。そして、ソート実行部４０１は、取得したＳＡＤ値を、値の小さい順に（すなわち、相関が高い順に）並べ替えをする。ソート実行部４０１は、並べ替えをしたＳＡＤ値の中の上位ｎ位まで（例えば、ｎ＝１０ならば１０位まで）のデータを、それぞれ保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）へ出力する。ソート実行部４０１は、取得したＳＡＤ値の中で、最も値が小さかったＳＡＤ値を保持部４０２−１へ、２番目に値が小さかったＳＡＤ値を保持部４０２−２へ、・・・、及びｎ番目に値が小さかったＳＡＤ値を保持部４０２−ｎへ出力する。
【００７０】
保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）は、それぞれＳＡＤ値を記憶する。保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）は、それぞれ、各基準ブロックと参照ブロックとの間のＳＡＤ値を演算する過程における、一時記憶領域として機能する。保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）は、各基準ブロックと参照ブロックとの間のＳＡＤ値を順に演算する過程の各時点において、演算したＳＡＤ値の値が小さいほうから上位ｎ位分のＳＡＤ値を一時的に記憶する。
【００７１】
次に、ソート実行部４０１が、再び、相関演算部３０の１１個の保持部３０４（３０４−１、３０４−２、・・・、３０４−１１）から、１１個の各基準ブロック毎のＳＡＤ値を表すデータを、同一のタイミングで取得する。
ソート実行部４０１は、取得した１１個のＳＡＤ値と、保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）に記憶されたｎ個のＳＡＤ値とを合わせた１１＋ｎ個のＳＡＤ値について、値の小さい順に（すなわち、相関が高い順に）並べ替えをする。
ソート実行部４０１は、並べ替えをしたＳＡＤ値の中の上位ｎ位まで（例えば、ｎ＝１０ならば１０位まで）のデータを、それぞれ保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）へ出力し、各保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）に記憶されているＳＡＤ値のデータを上書き更新する。
【００７２】
そして、各保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）が、ソート実行部４０１から、１１回、ＳＡＤ値のデータを取得した場合（すなわち、ソート実行部４０１が各保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）へ最初にＳＡＤ値を記憶させてから、ＳＡＤ値を１０回、上書き更新した場合）、各保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）は、参照ブロックと基準フレーム内の１２１個の全ての基準ブロックとの間のＳＡＤ演算が終了したものとし、その時点におけるｎ個の保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）にそれぞれ記憶されたＳＡＤ値を示すデータを、演算装置１の外部へ出力する。
すなわち、ソート部４０は、基準フレーム内の１２１個の基準ブロックの中で、参照ブロックとの相関が高かった（すなわち、ＳＡＤ値が小さかった）上位ｎ個分のＳＡＤ値を示すデータ、演算装置１の外部へ出力する。
【００７３】
なお、保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）の数は、ＳＡＤ値を出力する目的によって異なる。例えば、基準フレームの画像の中で、最も参照ブロックの画像と近似している部分を１つだけ出力することが目的であるならば、保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）の数は１つ（すなわち、ｎ＝１）だけでよい。
【００７４】
以上、本発明の第１の実施形態に係る演算装置１の構成の基本的な部分について説明した。しかしながら、上述した説明においては、本発明が解決する課題である、消費電力を削減するための構成の部分については言及していない。
【００７５】
上述した構成だけである場合、演算装置１は、基準フレーム内の全ての基準ブロックと参照ブロック間のＳＡＤ演算について、各画素の輝度値の差分絶対値の演算を全て実行する。すなわち、１回の処理でのべ１１０画素分の輝度値の差分絶対値の演算を行い、その演算を１１０回繰り返し行う（基準フレームが２０画素×２０画素、及び参照ブロックが１０画素×１０画素である場合）。したがって、演算装置１には、のべ１２，１００回分の差分絶対値演算に伴う演算回路の動作が発生する。消費電力は、この回路の動作に伴って発生するため、演算回路の動作の回数を減少させることは消費電力の削減に繋がる。
【００７６】
以下に、演算装置１の、消費電力を削減するための構成について説明する。
図９、図１０、及び図１１は、本発明の第１の実施形態に係る演算装置１による相関演算の一例を示す概略図である。
【００７７】
図９、図１０、及び図１１に図示する、基準フレーム、基準ブロック、及び参照ブロックの基本的な説明については、図３、図４、及び図５において説明した内容と同一であるため、説明を省略する。
図９に図示するように、演算装置１は基準フレームの中の最も上側に位置する基準ブロックから、順に参照ブロックとの間のＳＡＤ演算を行う。
そして、例えば、図１０の画像ｐｂ１２３及び図１１の画像ｐｂ１１０１に示す基準ブロックように、当該基準ブロックのＳＡＤ値の算出が完了する前に（すなわち、図１０の画像ｐｂ２１１及び図１１の画像ｐｂ１２００に示す基準ブロックのＳＡＤ値の算出が完了する前に）、演算の途中であるＳＡＤ値が後述する相関閾値を超えた場合には、演算装置１は、当該基準ブロックについてのその後のＳＡＤ値の演算及びＳＡＤ値の加算の処理を停止させる。
【００７８】
ここで言う相関閾値とは、例えば、上述したソート部４０の保持部４０２−ｎが記憶しているＳＡＤ値の値である。すなわち、保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）が記憶しているＳＡＤ値の中で、最も値が大きいＳＡＤ値（すなわち、記憶しているＳＡＤ値の中では最も相関度が低いＳＡＤ値の値）を記憶する保持部４０２−ｎの値が相関閾値である。
【００７９】
ＳＡＤ演算する場合、差分絶対値を加算していく演算であるため、ＳＡＤ演算の途中過程においてＳＡＤ値の値が減少することはない。演算中のＳＡＤ値が、保持部４０２−ｎが記憶するＳＡＤ値の値（相関閾値）を超過したならば、そのＳＡＤ値は最終的に保持部４０２−ｎが記憶するＳＡＤ値の値（相関閾値）よりも必ず大きな値となる。そのため、ソート部４０が行うＳＡＤ値の並べ替え処理において、この最終的なＳＡＤ値（例えば、図１０のＳＡＤ値ｓ０１３及び図１１のＳＡＤ値ｓ１１１）の値が、ＳＡＤ値の小さい方から上位ｎ位以内になることはない。よって、この最終的なＳＡＤ値は、保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）に記憶されることはなく、必ず破棄されるＳＡＤ値である。
【００８０】
したがって、演算中のＳＡＤ値が、保持部４０２−ｎが記憶するＳＡＤ値の値（相関閾値）を超過した場合には、ＳＡＤ演算中の基準ブロックにおけるその後のＳＡＤ値の演算処理は不要な演算処理となる。よって、演算中のＳＡＤ値が相関閾値を超えた場合には、演算装置１は、当該基準ブロックについてのその後のＳＡＤ値の演算を停止させる。
【００８１】
（演算装置１の詳細な構成）
以下に、演算装置１の詳細な構成について、図面を参照しながら説明する。
図１２は、本発明の第１の実施形態に係る演算装置１の相関演算部３０及びソート部４０の構成の一例を示す図である。
【００８２】
図示するように、図１２に示す相関演算部３０は、１１個の比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）を含んで構成される。１１個の比較器にはそれぞれ、ソート部４０の保持部４０２−ｎに記憶されたＳＡＤ値の値（相関閾値）が入力される。
そして、比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、垂直方向加算部３０３（３０３−１、３０３−２・・・、３０３−１１）が出力するＳＡＤ値と相関閾値との値を比較し、ＳＡＤ値が相関閾値を超過した値であった場合には、停止命令を示す信号を出力する。
【００８３】
図１３は、本発明の第１の実施形態に係る演算装置１の相関演算部３０の演算停止動作の一例を示す図である。
図１３に図示している範囲は、演算装置１の相関演算部３０の一部の範囲である。
相関演算部３０は、１１個のセレクタ３０６（３０６−１Ｍ、３０６−２Ｍ、・・・、３０６−１１）を含んで構成される。なお、図１３に図示しているのは、そのうちの１つであるセレクタ３０６−１Ｍである。
【００８４】
比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）が出力するＳＡＤ値と相関閾値との値を比較する。ＳＡＤ値が相関閾値を超過した値であった場合には、比較器３０５は、停止命令を示す信号を出力することによって、演算回路（例えば、ＦｌｉｐＦｌｏｐ）に供給する動作クロック（図示せず）を停止させる。また、比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、停止命令を示す信号を、セレクタ３０６へ出力する。セレクタ３０６は、比較器３０５から停止命令を示す信号を取得した場合、保持部３０４から取得するＳＡＤ値がどのような値であったとしても、ソート部４０へ出力するＳＡＤ値を最大値（例えば、０ｘｆｆ、等の値）に固定する。このように、ＳＡＤ値の演算回路の動作を停止させることによって、演算装置１は、ＳＡＤ演算回路の消費電力を抑えることができる。
【００８５】
（演算装置の動作）
次に、演算装置１の動作の流れについて説明する。
図１４は、本発明の実施形態に係る演算装置１の動作の一例を示すフローチャートである。
本フローチャートは、演算装置１が、基準フレームと参照フレームとの間のＳＡＤ演算を開始した際に開始する。
【００８６】
（ステップＳ１０１）相関演算部３０の差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）は、基準ブロックデータ格納部１０から取得した輝度値と、参照ブロックデータ格納部２０から取得した輝度値と、に基づいて、順次、差分絶対値を演算する。その後、ステップＳ１０２へ進む。
【００８７】
（ステップＳ１０２）相関演算部３０の水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）は、順次、差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）から取得した差分絶対値を加算することによって、基準ブロックの中の１ライン分のＳＡＤ値を演算する。そして、相関演算部３０の垂直方向加算部３０３は、順次、水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）から取得したＳＡＤ値を加算することによって、基準ブロック全体のＳＡＤ値を演算する。そして、相関演算部３０の保持部３０４は、垂直方向加算部３０３から取得したＳＡＤ値を記憶する。相関演算部３０の保持部３０４は、記憶したＳＡＤ値をソート部４０へ出力する。その後、ステップＳ１０３へ進む。
【００８８】
（ステップＳ１０３）相関演算部３０の比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、垂直方向加算部３０３から取得したＳＡＤ値と、ソート部４０から取得した相関閾値とを比較し、垂直方向加算部３０３から取得したＳＡＤ値が相関閾値を超過している場合には、比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、ＳＡＤ値の演算回路の動作を停止させた後、ステップＳ１０５へ進む。垂直方向加算部３０３から取得したＳＡＤ値が相関閾値を超過していない場合には、ステップＳ１０４へ進む。
【００８９】
（ステップＳ１０４）演算中の基準ブロックのデータ入力が終了した場合には、ステップＳ１０６へ進む。そうでない場合は、ステップＳ１０１へ戻る。
【００９０】
（ステップＳ１０５）演算中の基準ブロックのデータ入力が終了した場合には、ステップＳ１０６へ進む。そうでない場合は、ステップＳ１０５に留まる。
【００９１】
（ステップＳ１０６）ソート部４０のソート実行部４０１は、相関演算部３０から取得したＳＡＤ値と保持部４０２（４０２−１、４０２−２、・・・、４０２−ｎ）が記憶するＳＡＤ値とを含めて、ＳＡＤ値を小さい順に並べ替える。その後、ステップＳＡＤ値を１０７へ進む。
【００９２】
（ステップＳ１０７）最後の基準ブロックまでＳＡＤ値の演算が完了した場合は、本フローチャートの処理を終了する。そうでない場合は、ステップＳ１０１へ戻る。
【００９３】
以上、説明したように、本発明の第１の実施形態に係る演算装置１は、相関演算部３０の各水平方向加算部３０２（３０２−１、３０２−２、・・・、３０２−１１）及び各垂直方向加算部３０３によって演算された複数の相関値（ＳＡＤ値）を相関が高い順にソートし、その結果を保持するソート部４０を備える。そして、ソート部４０は、保持する相関値に基づく相関閾値を相関演算部３０の各比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）へ出力する。各比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、取得した相関閾値と、それぞれ演算された複数の相関値とを比較し、相関閾値よりも相関値のほうが低い場合に、相関演算部３０の動作を停止させる相関演算停止処理を行う。
これにより、第１の実施形態に係る演算装置１は、相関演算における、演算回路の消費電力を削減することができる。
【００９４】
（第２の実施形態）
次に、本発明の第２の実施形態について、図面を参照しながら説明する。
なお、第２の実施形態に係る演算装置１の基本的な構成は、第１の実施形態に係る演算装置１の基本的な構成と同一であるため、構成が共通する部分については説明を省略する。
図１５は、本発明の第２の実施形態に係る演算装置１の相関演算部３０の演算停止動作の一例を示す図である。
【００９５】
図示するように、第２の実施形態に係る演算装置１は、２２０個のセレクタ３０６（３０６−１Ａ、３０６−２Ａ、・・・、３０６−１１０Ａ、及び３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１１０Ｂ）を含んで構成される。なお、図１５に図示しているのは、そのうち２０個のセレクタ３０６（３０６−１Ａ、３０６−２Ａ、・・・、３０６−１０Ａ、及び３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１０Ｂ）の部分のみである。
【００９６】
基準ブロックデータ格納部１０及び参照ブロックデータ格納部２０から出力されたデータは、それぞれセレクタ３０６（３０６−１Ａ、３０６−２Ａ、・・・、３０６−１１０Ａ、及び３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１１０Ｂ）を介して、相関演算部３０の各差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）へ入力される。セレクタ３０６（３０６−１Ａ、３０６−２Ａ、・・・、３０６−１１０Ａ）は、基準ブロックデータ格納部１０と１１０個の差分絶対値算出部３０１との間にそれぞれ１つずつ、セレクタ３０６（３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１１０Ｂ）は、参照ブロックデータ格納部２０と１１０個の差分絶対値算出部３０１との間にそれぞれ１つずつ設けられる。
【００９７】
図示するように、相関演算部３０の比較器３０５（３０５−１、３０５−２、・・・、３０５−ｎ）は、垂直方向加算部３０３（３０３−１、３０３−２・・・、３０３−１１）が演算したＳＡＤ値とソート部４０から取得した相関閾値を比較し、そのＳＡＤ値が相関閾値の値を超過していた場合には、停止命令を示す信号を出力する。第２の実施形態においては、停止命令を示す信号は、２２０個の全てのセレクタ３０６（３０６−１Ａ、３０６−２Ａ、・・・、３０６−１１０Ａ、及び３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１１０Ｂ）へ出力される。
【００９８】
セレクタは３０６（３０６−１Ａ、３０６−２Ａ、・・・、３０６−１１０Ａ）は、比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）から停止命令を示す信号を取得した場合には、基準ブロックデータ格納部１０から取得する輝度値がどのような値であっても、最大値を示す値（例えば、０ｘｆｆ）を差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）へ出力する。
また、セレクタは３０６（３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１１０Ｂ）は、比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）から停止命令を示す信号を取得した場合には、参照ブロックデータ格納部２０から取得する輝度値がどのような値であっても、最小値を示す値（例えば、０ｘ００）を差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）へ出力する。
【００９９】
すなわち、第２の実施形態に係る演算装置１の相関演算部３０においては、比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）から停止命令を示す信号が出力された場合、各差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）へは、最大値を示す値（例えば、０ｘｆｆ（白を表すデータ））と最小値を示す値（例えば、０ｘ００（黒を表すデータ））の２つの固定値のデータが入力される。
【０１００】
これにより、各差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）が演算する差分絶対値は、取り得る最大の値で固定される。入力される値が固定されることによって、差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）、比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）、及びソート部４０等の各機能ブロック（演算回路）におけるデータ遷移が停止される。データ遷移が停止されることにより、各演算回路の消費電力が削減される。
【０１０１】
以上、説明したように、本発明の第２の実施形態に係る演算装置１は、相関演算における、演算回路の消費電力を削減することができる。
【０１０２】
（第３の実施形態）
次に、本発明の第３の実施形態について、図面を参照しながら説明する。
なお、第３の実施形態に係る演算装置１の基本的な構成は、第１の実施形態に係る演算装置１の基本的な構成と同一であるため、構成が共通する部分については説明を省略する。
図１６は、本発明の第３の実施形態に係る演算装置１の相関演算部３０の演算停止動作の一例を示す図である。
【０１０３】
図示するように、第３の実施形態に係る演算装置１は、制御部５０を含んで構成される。制御部５０は、何らかの手段によって相関閾値を設定し、設定した相関閾値を各比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）へ出力することができる。何らかの手段とは、例えば、初期設定時に予め一定の値が相関閾値として設定されるようにする、等の手段であってもよい。制御部５０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ；中央演算処理装置）によって構成される。
【０１０４】
図示するように、相関演算部３０の比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）は、垂直方向加算部３０３（３０３−１、３０３−２、・・・、３０３−１１）が演算したＳＡＤ値と制御部５０から取得した相関閾値を比較し、そのＳＡＤ値が相関閾値の値を超過していた場合には、停止命令を示す信号を出力する。
比較器３０５（３０５−１、３０５−２、・・・、３０５−１１）が停止命令を示す信号を出力することによって、例えば、第１の実施形態における演算装置１のように演算回路（例えば、ＦｌｉｐＦｌｏｐ）に供給する動作クロックを停止して、演算回路の消費電力を削減してもよい。
または、例えば、第２の実施形態における演算装置１のように各差分絶対値算出部３０１（３０１−１、３０１−２、・・・、３０１−１１０）へ入力されるデータを固定化することによって、演算回路の消費電力を削減してもよい。
【０１０５】
以上、説明したように、本発明の第２の実施形態に係る演算装置１は、相関演算における、演算回路の消費電力を削減することができる。
【０１０６】
以上、本発明の好ましい実施形態を説明したが、本発明はこれら実施形態及びその変形例に限定されることはない。本発明の趣旨を逸脱しない範囲で、構成の付加、省略、置換、およびその他の変更が可能である。
また、本発明は前述した説明によって限定されることはなく、添付のクレームの範囲によってのみ限定される。
【０１０７】
なお、上述した実施形態における演算装置１の一部又は全部をコンピュータで実現するようにしてもよい。その場合、この制御機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。
【０１０８】
なお、ここでいう「コンピュータシステム」とは、演算装置１に内蔵されたコンピュータシステムであって、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１０９】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信回線のように、短時間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよい。
【０１１０】
また、上述した実施形態における演算装置１を、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等の集積回路として実現してもよい。演算装置１の各機能ブロックは個別にプロセッサ化してもよいし、一部、または全部を集積してプロセッサ化してもよい。また、集積回路化の手法はＬＳＩに限らず専用回路、または汎用プロセッサで実現してもよい。また、半導体技術の進歩によりＬＳＩに代替する集積回路化の技術が出現した場合、当該技術による集積回路を用いてもよい。
【産業上の利用可能性】
【０１１１】
演算回路の消費電力を削減することができる。
【符号の説明】
【０１１２】
１・・・演算装置、１０・・・基準ブロックデータ格納部、２０・・・参照ブロックデ
ータ格納部、３０・・・相関演算部、４０・・・ソート部、５０・・・制御部、３０１（
３０１−１、３０１−２、・・・、３０１−１１０）・・・差分絶対値算出部、３０２（
３０２−１、３０２−２、・・・、３０２−１１）・・・水平方向加算部、３０３（３０
３−１、３０３−２・・・、３０３−１１）・・・垂直方向加算部、３０４（３０４−１
、３０４−２、・・・、３０４−１１）・・・保持部、３０５（３０５−１、３０５−２
、・・・、３０５−１１）・・・比較器、３０６（３０６−１Ａ、３０６−２Ａ、・・・
、３０６−１１０Ａ、３０６−１Ｂ、３０６−２Ｂ、・・・、３０６−１１０Ｂ、３０６
−１Ｍ、３０６−２Ｍ、・・・、３０６−１１０Ｍ）・・・セレクタ、４０１・・・ソー
ト実行部、４０２（４０２−１、４０２−２、・・・、４０２−ｎ）・・・保持部、ｐ１
〜ｐ９・・・画像、ｐａ１〜ｐａ１２１０・・・画像、ｐｂ１〜ｐｂ１２１０・・・画像
【図１】
2016194828.tif 000003
【図２Ａ】
2016194828.tif 000004
【図２Ｂ】
2016194828.tif 000005
【図３】
2016194828.tif 000006
【図４】
2016194828.tif 000007
【図５】
2016194828.tif 000008
【図６】
2016194828.tif 000009
【図７】
2016194828.tif 000010
【図８】
2016194828.tif 000011
【図９】
2016194828.tif 000012
【図１０】
2016194828.tif 000013
【図１１】
2016194828.tif 000014
【図１２】
2016194828.tif 000015
【図１３】
2016194828.tif 000016
【図１４】
2016194828.tif 000017
【図１５】
2016194828.tif 000018
【図１６】
2016194828.tif 000019
【手続補正書】
【提出日】平成28年10月3日(2016.10.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算装置において、
前記基準ブロックのデータを格納する基準ブロックデータ格納部と、
前記参照ブロックのデータを格納する参照ブロックデータ格納部と、
所定の相関閾値をそれぞれ入力し、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算部と、
前記相関演算部によって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持すると共に、前記相関閾値を出力するソート部と、
を備え、
それぞれ入力される前記相関閾値と、複数の前記相関演算部によってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算部の動作を停止させる相関演算停止処理を行うことを特徴とする、演算装置。
【請求項２】
（削除）
【請求項３】
前記相関閾値は、前記ソート部が保持するソート後の前記相関値のうち最も相関が高い相関値であることを特徴とする、請求項１に記載の演算装置。
【請求項４】
（削除）
【請求項５】
前記相関演算停止処理は、前記相関演算部の動作クロックを停止させることによって前記相関演算部の動作を停止させる処理であることを特徴とする、請求項１に記載の演算装置。
【請求項６】
前記相関演算停止処理は、前記相関演算部へ入力されるデータを、片方は最大値、もう片方は最小値にすることによって前記相関演算部の動作を停止させる処理であることを特徴とする、請求項１に記載の演算装置。
【請求項７】
前記相関演算停止処理は、次の前記基準ブロックと前記参照ブロックとの間の相関演算が開始される場合に終了する処理であることを特徴とする、請求項１に記載の演算装置。
【請求項８】
基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行う演算方法において、
前記基準ブロックのデータを格納する基準ブロックデータ格納ステップと、
前記参照ブロックのデータを格納する参照ブロックデータ格納ステップと、
所定の相関閾値をそれぞれ入力し、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算ステップと、
前記相関演算ステップによって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持すると共に、前記相関閾値を出力するソートステップと、
を有し、
それぞれ入力される前記相関閾値と、複数の前記相関演算ステップによってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算ステップの動作を停止させる相関演算停止ステップと、
を有することを特徴とする、演算方法。
【請求項９】
コンピュータに、
基準フレームを複数の基準ブロックに分割し、参照フレームに前記基準フレームに対応する参照ブロックを設定し、前記基準ブロックと前記参照ブロックとの間で相関演算を行わせるプログラムであって、
前記基準ブロックのデータを格納する基準ブロックデータ格納ステップと、
前記参照ブロックのデータを格納する参照ブロックデータ格納ステップと、
所定の相関閾値をそれぞれ入力し、前記基準ブロックのデータと前記参照ブロックのデータとを用いて、複数の異なる位置の相関値を同時にそれぞれ演算する複数の相関演算ステップと、
前記相関演算ステップによって演算された複数の前記相関値を相関が高い順にソートし、その結果を保持すると共に、前記相関閾値を出力するソートステップと、
それぞれ入力される前記相関閾値と、複数の前記相関演算ステップによってそれぞれ演算された複数の前記相関値とを比較し、前記相関閾値よりも前記相関値のほうが相関が低い場合に、前記相関演算ステップの動作を停止させる相関演算停止ステップと、
を実行させるための、プログラム。
【国際調査報告】
2016194828.tif 000020
2016194828.tif 000021
2016194828.tif 000022
2016194828.tif 000023