(57)【要約】【課題】参照領域のデータをパッキングして記憶装置に格納した場合に、重複して参照領域のデータを読み出すことなく、動きベクトルを検出できるようにする。【解決手段】対象画像記憶部から、対象画像を読み出す対象画像読み出しステップと、参照画像記憶部から、対象画像と同サイズ分の画像データに加えて、少なくともパッキングの１単位分以上の画像データを余分に読み出す参照画像読み出しステップと、参照画像読み出しステップで読み出された画像データ内の前記対象画像と同サイズ分の画像データのブロックであり、互いに位置が異なる複数の参照ブロックのそれぞれと、前記対象画像との相関度を算出する相関度算出ステップとを設ける。相関度算出ステップで相関度を求める参照ブロックの数は、パッキングされた画素の数とは同数、又はパッキングされた画素の数の倍数とする。【選択図】図１
2011147185.tif 000002
【特許請求の範囲】
【請求項１】
動画像圧縮符号化を行なう際に、第１の画素数単位でパッキングされて対象画像記憶部に格納された矩形状の対象画像と、第２の画素数単位でパッキングされて参照画像記憶部に格納された矩形状の参照画像とを使用して、ブロック単位で動きベクトルを検出する動きベクトル検出方法であって、
前記対象画像記憶部から、前記対象画像を読み出す対象画像読み出しステップと、
前記参照画像記憶部から、前記対象画像と同サイズ分の画像データに加えて、少なくとも前記参照画像のパッキング１単位分以上の画像データを余分に読み出す参照画像読み出しステップと、
前記参照画像読み出しステップで読み出された画像データの内、前記対象画像と同サイズであり互いに位置が異なる複数の参照ブロックに対し、前記対象画像との相関度の算出を同時に実行する相関度算出ステップとを有し、
前記相関度算出ステップで相関度を求める参照ブロックの数は、パッキングされた画素の数とは同数、又はパッキングされた画素の数の倍数であることを特徴とする動きベクトル検出方法。
【請求項２】
請求項１の動きベクトル検出方法であって、さらに、
前記対象画像読み出しステップの前に、前記対象画像を、前記対象画像のパッキング２単位ごとに、相関度の算出に使用する画素と使用しない画素とに並び替える対象画像並び替えステップと、
前記参照画像読み出しステップの前に、前記参照画像を、前記参照画像のパッキング２単位ごとに、相関度の算出に使用する画素と使用しない画素とに並び替える参照画像並び替えステップとを有し、
前記対象画像読み出しステップ及び参照画像読み出しステップは、相関度の算出に使用する画素を含んだパッキングデータのみを読み出すことを特徴とする動きベクトル検出方法。
【請求項３】
請求項１の動きベクトル検出方法であって、
前記参照画像読み出しステップにおいて余分に読み出す画像データの量は、前記相関度算出ステップで同時に算出できる量以上であることを特徴とする動きベクトル検出方法。
【請求項４】
請求項１の動きベクトル検出方法であって、
さらに、前記相関度算出ステップで求めた各相関度を探索結果記憶部に格納する算出結果格納ステップを有し、
前記相関度算出ステップは、相関度の算出対象となっている参照ブロックに対応した相関度が、前記探索結果記憶部に格納されている場合には、その値を読み出すことを特徴とする動きベクトル検出方法。
【請求項５】
請求項４の動きベクトル検出方法であって、さらに、
前記対象画像よりも小さな領域であるサブブロックと、前記参照画像読み出しステップで読み出された画像データ内の前記サブブロックと同サイズ分の画像データのブロックであり、互いに位置が異なる複数のサブ参照ブロックのそれぞれとの相関度を算出するサブブロック相関度算出ステップと、
サブブロック相関度算出ステップで求めた各相関度を前記探索結果記憶部に格納するサブブロック算出結果格納ステップと、
前記探索結果記憶部に格納されている前記相関度算出ステップで求めた各相関度、及びサブブロック相関度算出ステップで求めた各相関度の何れか一方の値を選択するステップと、
を有することを特徴とする動きベクトル検出方法。
【請求項６】
請求項４の動きベクトル検出方法であって、
前記相関度算出ステップは、画像の偶数ラインごとに前記相関度を算出するモードと、  画像の奇数ラインごとに前記相関度を算出するモードとを有していることを特徴とする動きベクトル検出方法。
【請求項７】
請求項４の動きベクトル検出方法であって、
さらに、前記探索結果記憶部で相関値格納に使用されている容量が、所定の閾値を越えた場合に、前記探索結果記憶部内に格納されている相関値を削除する削除ステップを有していることを特徴とする動きベクトル検出方法。
【請求項８】
請求項７の動きベクトル検出方法であって、
前記削除ステップは、相関値を削除する際には、格納されている全ての相関値を削除することを特徴とする動きベクトル検出方法。
【請求項９】
請求項７の動きベクトル検出方法であって、
前記削除ステップは、最も相関が強いことを示す相関値を除く相関値を、前記探索結果記憶部から削除することを特徴とする動きベクトル検出方法。
【請求項１０】
請求項４の動きベクトル検出方法であって、
さらに、参照ブロックごとに、前記相関度の算出が行なわれたか否かを識別するフラグを管理するフラグ管理ステップを有することを特徴とする動きベクトル検出方法。
【請求項１１】
請求項１の動きベクトル検出方法であって、
前記対象画像読み出しステップ、前記参照画像読み出しステップ、及び前記相関度算出ステップは、上下左右にある参照ブロックよりも強い相関度を有する参照ブロックが見つかるまで繰り返して実行されるものであり、
前記相関度算出ステップは、前回に相関度算出ステップで算出した複数の相関度のうち、最も強い相関を示す相関値が対応した参照ブロックの位置に応じ、次に相関値を求める参照ブロックを決定することを特徴とする動きベクトル検出方法。
【請求項１２】
請求項１１の動きベクトル検出方法であって、
参照ブロックごとに、前記相関度の算出が行なわれたか否かを識別するフラグを管理するフラグ管理ステップをさらに有することを特徴とする動きベクトル検出方法。
【請求項１３】
請求項１２の動きベクトル検出方法であって、
前記相関度算出ステップは、前記フラグの値に応じ、次に相関値を算出する参照ブロックを決定することを特徴とする動きベクトル検出方法。
【請求項１４】
動画像圧縮符号化を行なう際に、第１の画素数単位でパッキングされて対象画像記憶部に格納された矩形状の対象画像と、第２の画素数単位でパッキングされて参照画像記憶部に格納された矩形状の参照画像とを使用して、ブロック単位で動きベクトルを検出する動きベクトル検出装置であって、
前記対象画像記憶部から、前記対象画像を読み出す対象画像読出部と、
前記参照画像記憶部から、前記対象画像と同サイズ分の画像データに加えて、少なくとも前記参照画像のパッキング１単位分以上の画像データを余分に読み出す参照画像読出部と、
前記参照画像読出部が読み出した画像データ内、前記対象画像と同サイズであり互いに位置が異なる複数の参照ブロックに対し、前記対象画像との相関度の算出を同時に実行する複数のＳＡＤ計算部と、
前記相関度が格納される探索結果記憶部と、
互いに位置が異なる複数の参照ブロックをそれぞれ、各探索結果記憶部に対して送って相関度を算出させるとともに、各相関度のうちの１つを用いて、次に前記ＳＡＤ計算部で相関度を算出させる参照ブロックを決定し、残りの相関度を前記探索結果記憶部に格納する動きベクトル検出制御部とを備え、
前記ＳＡＤ計算部で相関度を求める参照ブロックの数は、パッキングされた画素の数とは同数、又はパッキングされた画素の数の倍数であることを特徴とする動きベクトル検出装置。
【請求項１５】
動画像圧縮符号化を行なう際に、第１の画素数単位でパッキングされて対象画像記憶部に格納された矩形状の対象画像と、第２の画素数単位でパッキングされて参照画像記憶部に格納された矩形状の参照画像とを使用して、ブロック単位で動きベクトルを検出する動きベクトル検出装置であって、
前記対象画像記憶部から、前記対象画像を読み出す対象画像読出部と、
前記参照画像記憶部から、前記対象画像と同サイズ分の画像データに加えて、少なくとも前記参照画像のパッキング１単位分以上の画像データを余分に読み出す参照画像読出部と、
前記参照画像読出部が読み出した画像データ内、前記対象画像と同サイズであり互いに位置が異なる複数の参照ブロックに対し、前記対象画像との相関度の算出を同時に実行する複数のＳＡＤ計算部と、
互いに位置が異なる複数の参照ブロックをそれぞれ、各探索結果記憶部に対して送って相関度を算出させるとともに、複数の相関度のうち、最も強い相関を示す相関値が対応した参照ブロックの位置に応じ、次に前記ＳＡＤ計算部で相関度を算出させる参照ブロックを決定する動きベクトル検出制御部とを備え、
前記ＳＡＤ計算部で相関度を求める参照ブロックの数は、パッキングされた画素の数とは同数、又はパッキングされた画素の数の倍数であることを特徴とする動きベクトル検出装置。
【請求項１６】
請求項１４又は請求項１５の動きベクトル検出装置と、
画像光を画像信号に変換するセンサと、
入射された画像光を前記センサ上に結像させる光学系と、
前記画像信号をデジタルデータに変換して前記動きベクトル検出装置に出力するＡＤ変換器と、
を備えたことを特徴とする撮像システム。
【請求項１７】
請求項１４又は請求項１５の動きベクトル検出装置と、
入力されたアナログ値の画像信号をデジタルデータに変換して前記動きベクトル検出装置に出力するＡＤ変換器と、
を備えたことを特徴とする撮像システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像圧縮符号化における動き補償予測符号化に使用する動きベクトル検出方法、動きベクトル検出装置、及び撮像システムに関するものである。
【背景技術】
【０００２】
近年、高能率符号化を行うＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）等の動画像圧縮符号化技術の実用化が急速に進み、ビデオカメラや携帯電話等に普及している。ＭＰＥＧ等の動画像圧縮符号化技術においては、被写体の変位と画像の差分データのみを符号化することで効率よく画像データを圧縮する動き補償予測が用いられている。この動き補償予測を行なう際には、被写体の変位を示す動きベクトルを検出する必要がある。
【０００３】
動きベクトル検出においては、ブロックマッチング法が広く採用されている。ブロックマッチング法による動きベクトル検出方法では、現画像内で符号化の対象となる所定数の画素からなるブロックの画像データ（以下、対象画像若しくは対象ブロックと呼ぶ）と、現画像よりも前画像において対象ブロックと同一空間位置の近傍で、かつ対象ブロックよりも大きい領域（以下、参照領域と呼ぶ）との比較を行い、対象画像と参照画像との相関度を所定の評価関数を算出することによって求める。そして、対象ブロックと最もマッチングの取れている（相関が強い）参照ブロック（参照領域上のブロックであり、対象ブロックと同サイズのブロック）の位置を求め、その参照ブロックの位置と、対象ブロックの位置との間の距離および方向を動きベクトルとして検出するものである。
【０００４】
相関が強い参照ブロックの検出方法としては、例えば、参照領域内の所定の探索開始位置（基準点と呼ぶ）を基準に、上下左右位置の相関係数を求め、相関が最大となった位置へ基準点を移動し、まだ相関係数を演算していない方向の相関演算を行いながら、相関が最大となるように探索位置をずらす方法（Ｏｎｅ  ａｔ  ａ  Ｔｉｍｅ方式）がよく知られている。
【０００５】
ブロックマッチング法による動きベクトル検出は処理量が多いので、処理完了までには多くの時間を必要とする。このため、様々な面から高速化の検討が行なわれてきた。例えば、前記評価関数を算出するための装置（例えば差分累積装置）を複数用意し、並列に処理させることで処理の高速化を図った動きベクトル検出装置が開示されている（例えば、特許文献１を参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−１３８７３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一般に多くのデータ処理装置においては、データの転送および記憶装置への読み書きを行う際に、Ｐ個（Ｐは任意の自然数）のデータをパッキングして処理速度を上げる手法が採用されている。そのため、上記の動きベクトル検出装置においても、対象画像および参照画像をパッキングして処理の高速化を図ることが考えられる。
【０００８】
しかしながら、参照ブロックの境界と、パッキングされたデータの境界とは必ずしも一致しないので、位置をずらしつつ複数の参照ブロックを、参照領域のデータが格納された記憶装置から読み出す場合には、重複して同じデータを読み出してしまうことが考えられ、読み出し効率が非常に悪くなる可能性がある。
【０００９】
本発明は上記の問題に着目してなされたものであり、参照領域のデータをパッキングして記憶装置に格納した場合に、重複して参照領域のデータを読み出すことなく、動きベクトルを検出できるようにすることを目的としている。
【課題を解決するための手段】
【００１０】
前記の課題を解決するため、本発明の一態様は、
動画像圧縮符号化を行なう際に、第１の画素数単位でパッキングされて対象画像記憶部に格納された矩形状の対象画像と、第２の画素数単位でパッキングされて参照画像記憶部に格納された矩形状の参照画像とを使用して、ブロック単位で動きベクトルを検出する動きベクトル検出方法であって、
前記対象画像記憶部から、前記対象画像を読み出す対象画像読み出しステップと、
前記参照画像記憶部から、前記対象画像と同サイズ分の画像データに加えて、少なくとも前記参照画像のパッキング１単位分以上の画像データを余分に読み出す参照画像読み出しステップと、
前記参照画像読み出しステップで読み出された画像データの内、前記対象画像と同サイズであり互いに位置が異なる複数の参照ブロックに対し、前記対象画像との相関度の算出を同時に実行する相関度算出ステップとを有し、
前記相関度算出ステップで相関度を求める参照ブロックの数は、パッキングされた画素の数とは同数、又はパッキングされた画素の数の倍数であることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、参照領域のデータをパッキングして記憶装置に格納した場合に、重複して参照領域のデータを読み出すことなく、動きベクトルを検出できる。
【図面の簡単な説明】
【００１２】
【図１】実施形態１に係る動きベクトル検出装置の構成を示すブロック図である。
【図２】対象画像記憶部に格納される象画像のサイズを示す図である。
【図３】参照画像の一部分を抜粋したものである。
【図４】参照画像の一部分を抜粋したものである。
【図５】ＳＡＤ計算部に送られデータを示す図である。
【図６】動きベクトル検出装置で行なわれる処理の流れを示すフローチャートである。
【図７】探索結果記憶部内のデータの変化状況を示す図である。
【図８】時刻ｔ０における探索済点記憶部の状況を示す図である。
【図９】動きベクトル（４，０）点を探索するのに必要となる参照画像領域を示す図である。
【図１０】動きベクトル（０，０）点を計算する際の対象画像及び参照画像の読出し、読み出したデータの一時蓄積、及びＳＡＤ計算部へのデータ供給タイミングを示す図である。
【図１１】時刻ｔ１における探索済点記憶部の状況を示す図である。
【図１２】時刻ｔ２における探索済点記憶部の状況を示す図である。
【図１３】時刻ｔ３における探索済点記憶部の状況を示す図である。
【図１４】時刻ｔ４における探索済点記憶部の状況を示す図である。
【図１５】Ｏｎｅ  ａｔ  ａ  Ｔｉｍｅ方式で、１点ずつＳＡＤ値を求めた場合の対象画像及び参照画像を読み出し回数を説明する図である。
【図１６】実施形態１に係る動きベクトル検出装置で、ＳＡＤ値を求めた場合の対象画像及び参照画像を読み出し回数を説明する図である。
【図１７】重複探索点の探索を行なわないようにした場合に、同時探索される点を説明する図である。
【図１８】実施形態２に係る動きベクトル検出装置の構成を示すブロック図である。
【図１９】実施形態２に係る動きベクトル検出装置で行なわれる探索動作を説明する図である。
【図２０】実施形態２に係る動きベクトル検出装置で行なわれる処理の流れを示すフローチャートである。
【図２１】フラグの値の事前確認が行なわれた場合の探索動作を説明する図である。
【図２２】サブサンプリングした対象画像を示す図である。
【図２３】動きベクトル（０，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図２４】動きベクトル（１，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図２５】動きベクトル（２，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図２６】動きベクトル（３，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図２７】動きベクトル（４，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図２８】動きベクトル（５，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図２９】動きベクトル（６，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図３０】動きベクトル（７，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図３１】動きベクトル（８，０）点の探索において使用する、サブサンプリングした参照画像を示す図である。
【図３２】再パッキングした画像データを説明する図である。
【図３３】再パッキングした対象画像を示す図である。
【図３４】動きベクトルのｘ座標が偶数の場合の、参照画像の読み出し順を説明する図である。
【図３５】動きベクトルのｘ座標が奇数の場合の、参照画像の読み出し順を説明する図である。
【図３６】実施形態４に係る撮像システムの構成を示すブロック図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態について図面を参照しながら説明する。なお、以下の各実施形態の説明において、一度説明した構成要素と同様の機能を有する構成要素については、同一の符号を付して説明を省略する。
【００１４】
《発明の実施形態１》
図１は、本発明の実施形態１に係る動きベクトル検出装置１００の構成を示すブロック図である。動きベクトル検出装置１００は、例えば、ビデオカメラや携帯電話等において、動き補償予測を行なう際に、被写体の変位を示す動きベクトルを検出する装置の例である。
【００１５】
（動きベクトル検出装置１００の構成）
図１に示すように、動きベクトル検出装置１００は、動きベクトル検出制御部１０１、対象画像記憶部１０２、参照画像記憶部１０３、対象画像読出部１０４、参照画像読出部１０５、対象画像一時蓄積部１０６、参照画像一時蓄積部１０７、ＳＡＤ計算部１０８、探索結果記憶部１０９、及び探索済点記憶部１１０を備えている。これらのうちＳＡＤ計算部１０８は、複数個（ｎ個）が設けられており、図１では、ＳＡＤ計算部１０８−１、ＳＡＤ計算部１０８−２・・・ＳＡＤ計算部１０８−ｎのように、枝番をつけて識別してある。
【００１６】
（各構成要素の機能）
動きベクトル検出制御部１０１は、対象画像記憶部１０２、参照画像記憶部１０３、対象画像読出部１０４、参照画像読出部１０５、対象画像一時蓄積部１０６、参照画像一時蓄積部１０７、及びＳＡＤ計算部１０８の動作を、後述するように制御するようになっている。
【００１７】
対象画像記憶部１０２は、符号化の対象となる画像データ（対象画像、若しくは対象ブロックと呼ぶ）が、所定の画素数（第１の画素数とする）の単位でパッキングされた状態で、格納されるようになっている。
【００１８】
参照画像記憶部１０３は、現在の画像よりも時間的に前の画像において、対象ブロックと同一空間位置の近傍で、かつ対象ブロックよりも大きい領域（以下、参照領域と呼ぶ）の画像データ（参照画像）の一部、もしくは全てが、所定の画素数（第２の画素数とする）の単位でパッキングされた状態で、格納されるようになっている。参照画像は、対象画像の動きベクトル探索、及び符号化（具体的には、対象画像と参照画像の差分を符号化する）のために使用される。第１の画素数及び第２の画素数のことは、ともにパッキングデータ数と呼ぶことにする。
【００１９】
なお、本実施形態では、対象画像のサイズ（探索サイズ）は、図２に示すように１６画素×１６画素であるものとする。また、第１の画素数及び第２の画素数は、何れも同数のＰ画素（Ｐは自然数）であるものとする。以下では、Ｐ＝４の例を説明する。
【００２０】
図３及び図４は、参照画像の一部分を抜粋したものである。太線で囲んである１６画素×１６画素の領域（参照ブロックと呼ぶ）が、対象ブロックとの相関の強さを算出する領域である。相関の強さは、対象ブロックを構成する画素が有する画素値と参照ブロックを構成する画素が有する画素値との差分の絶対値の和である評価関数値の最小値を求めることにより評価する（以下、この評価関数で求めた値をＳＡＤ値と呼ぶ）。
【００２１】
図３は、点（０，０）を探索の開始位置（基準点）にした参照ブロックと、その周囲の画像データ部分を抜粋したものである。また、図４は、点（１，０）を基準点にして探索を開始する参照ブロックと、その周囲の画像データ部分を抜粋したものである。ここで、点（ｎ，ｍ）を基準点とする参照ブロックについてＳＡＤ値を求めることを、「動きベクトル（ｎ，ｍ）点を探索する」ということにする。
【００２２】
図３を見ると動きベクトル（０，０）点を探索する際に必要となるパッキングデータ数がわかる。すなわち、水平４パッキングデータ×垂直１６ラインである。これは、水平方向に４パッキングデータ（１６画素）を読み出し、読み出した全ての画像データを探索に使用した場合の読み出しパッキング数である。
【００２３】
しかし、参照画像の位置が、これよりもずれた場合は、より多くの画像データを読み込む必要がある。例えば、動きベクトル（１，０）点を探索する際に必要となるパッキングデータ数は、図４に示すように、水平５パッキングデータ×垂直１６ラインとなる。すなわち、参照画像記憶部１０３からの参照画像の読み出しは、水平５パッキングデータ×垂直１６ラインを、基準読み出しサイズとするとよい。すなわち、対象画像のサイズに、参照画像のパッキング単位のサイズ（少なくとも１単位分以上）を加えたものを基準読み出しサイズとするとよい。
【００２４】
対象画像読出部１０４は、ＳＡＤ計算を行なう上で必要となる、対象画像記憶部１０２に格納されている対象画像を、動きベクトル検出制御部１０１の制御に応じ、第１の画素数の単位（この例ではＰ画素単位）で読み出すようになっている。
【００２５】
参照画像読出部１０５は、ＳＡＤ計算を行なう上で必要となる、参照画像記憶部１０３に格納されている参照画像を、動きベクトル検出制御部１０１の制御に応じ、第２の画素数の単位（この例ではＰ画素単位）で、基準読み出しサイズ分を読み出すようになっている。
【００２６】
対象画像一時蓄積部１０６は、対象画像読出部１０４が読み出した対象画像を一時的に蓄積するようになっている。より詳しくは、対象画像一時蓄積部１０６は、対象画像の１パッキングデータ分（すなわちＰ画素分のデータ）のバッファ領域を有しており、ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）動作を行なうようになっている。なお、対象画像一時蓄積部１０６の出力は、動きベクトル検出制御部１０１の制御に応じて、ＳＡＤ計算部１０８−１〜ＳＡＤ計算部１０８−ｎに供給されている。
【００２７】
参照画像一時蓄積部１０７は、参照画像読出部１０５が読み出した参照画像を一時的に蓄積するようになっている。より詳しくは、参照画像一時蓄積部１０７は、参照画像の２パッキングデータ分（すなわち２Ｐ画素分のデータ）のバッファ領域を有しており、ＦＩＦＯ動作を行なうようになっている。
【００２８】
ＳＡＤ計算部１０８−１〜ｎ（本実施形態では、ｎ＝５とする）は、対象画像一時蓄積部１０６から供給された対象画像、及び参照画像一時蓄積部１０７から供給された参照画像を使用して、次のように定義されるＳＡＤ値を計算する。
【００２９】
ＳＡＤ値の定義は、以下のとおりである。
【００３０】
ＳＡＤ＝Σ｜Ｒｅｆ（Ｍｘ＋ｘ，Ｍｙ＋ｙ）−Ｏｒｇ（ｘ，ｙ）｜
ここで、Ｒｅｆ（Ｍｘ＋ｘ，Ｍｙ＋ｙ）は、対象ブロックに対して相対位置（Ｍｘ，Ｍｙ）にある参照ブロックの画素位置（Ｍｘ＋ｘ，Ｍｙ＋ｙ）における画素値を示している。また、Ｏｒｇ（ｘ，ｙ）は対象ブロックの画素位置（ｘ，ｙ）における画素値を示している。
【００３１】
また、動きベクトル検出制御部１０１の制御に応じて、ＳＡＤ計算部１０８−１〜ＳＡＤ計算部１０８−ｎには、参照画像一時蓄積部１０７の出力が供給されている。詳しくは、参照画像一時蓄積部１０７に蓄積されている２パッキングデータ（すなわち８画素分のデータ）は、動きベクトル検出制御部１０１によって、パッキングデータから画素単位のデータに分解され、ＳＡＤ計算部１０８−１〜ＳＡＤ計算部１０８−ｎに送られる。具体的には、参照画像一時蓄積部１０７に蓄積されている８画素分のデータをｄ１〜ｄ８とすると、ＳＡＤ計算部１０８−１にはｄ１〜ｄ４の４画素分のデータを送り、ＳＡＤ計算部１０８−２にはｄ２〜ｄ５の４画素分のデータを送り、ＳＡＤ計算部１０８−３にはｄ３〜ｄ６の４画素分のデータを送り、ＳＡＤ計算部１０８−４にはｄ４〜ｄ７の４画素分のデータを送り、ＳＡＤ計算部１０８−５にはｄ５〜ｄ８の４画素分のデータを送るようにする（図５を参照）。
【００３２】
これにより、水平方向に１画素ずつずれた５点について、同時にＳＡＤ値を求めることができる。すなわち、探索点（０，０）のＳＡＤ値計算を行なうＳＡＤ計算部がＳＡＤ計算部１０８−１であり、また探索点（１，０）のＳＡＤ値計算を行なうＳＡＤ計算部がＳＡＤ計算部１０８−２であり、また、探索点（４，０）のＳＡＤ値計算を行なうＳＡＤ計算部がＳＡＤ計算部１０８−５である。同時にＳＡＤ値計算が行なえる探索点をまとめると、点（４ｘＰ，Ｑ）、点（４ｘＰ＋１，Ｑ）、点（４ｘＰ＋２，Ｑ）、点（４ｘＰ＋３，Ｑ）、点（４ｘＰ＋４，Ｑ）となる。（ただし、ＰおよびＱは整数である）。
【００３３】
探索結果記憶部１０９は、対象画像以外の画像の動きベクトル探索に使用できるＳＡＤ値を一時的に蓄積するようになっている。
【００３４】
探索済点記憶部１１０は、参照画像内の各点について、探索を行なったかどうか（ＳＡＤ値を求めたかどうか）等を識別するフラグを記憶するようになっている。本実施形態では、このフラグは２ビットである。なお、フラグの値が『１０ｂ』（ｂは２進数を示す）ならば、既に探索が完了しているがＳＡＤ値が探索結果記憶部１０９に格納されていないことを示し、フラグの値が『０１ｂ』ならば、探索は完了し、かつＳＡＤ値が探索結果記憶部１０９に格納されていることを示し、フラグの値が『００ｂ』ならば、探索が行なわれていないことを示しているものとする。
【００３５】
（動きベクトル検出装置１００の動作）
基準点（０，０）から順に、最小のＳＡＤ値を求める場合を例に、動きベクトル検出装置１００の動作を説明する。図６は、動きベクトル検出装置１００で行なわれる処理の流れを示すフローチャートである。なお、探索処理を行なうステップ（Ｓ１００〜Ｓ１０２、及びＳ１０５〜Ｓ１０６）においては、探索毎にサブステップ（ＳＵＢ１０１〜ＳＵＢ１０４）の処理を行なう。
【００３６】
また、フローを開始する時の処理（初期化処理）として、探索結果記憶部１０９をクリアし、（図７に示すｔ０のタイミング）、探索済点記憶部１１０のフラグも全て『００ｂ』にクリアする（図８を参照）。初期化が完了すると、引き続き以下のように処理が行なわれる。
【００３７】
第一の処理としては、基準点（０，０）の探索を行なう（Ｓ１００）。探索にあたり、ＳＵＢ１０１の処理に移行する。この処理では、まず、動きベクトル検出制御部１０１は、基準点（０，０）が探索済みか否かを探索済点記憶部１１０のフラグ状況を確認して判断する（ＳＵＢ１０１）。
【００３８】
この例では、フラグの値が『００ｂ』であるため（図８を参照）、ＳＵＢ１０２に移る。ＳＵＢ１０２では、実際に基準点（０，０）を探索する。
【００３９】
まず、動きベクトル検出制御部１０１は、参照画像読出部１０５を制御して、参照画像を読み出す。動きベクトル（０，０）点を探索するにあたって必要なのは、パッキングデータＰ２−２ｂ〜Ｐ１７−５（計６４パッキングデータ）であるが、基準読み出しサイズに従い、Ｐ２−２ｂ〜Ｐ１７−６（計８０パッキングデータ）を読み出す。この読み出しにより、基準点（０，０）の探索は勿論のこと、点（１，０）、点（２，０）、点（３，０）、そして点（４，０）の探索を行なうことができる。参考のため、図９には動きベクトル（４，０）点を探索するのに必要となる参照画像領域を示す。
【００４０】
図１０に動きベクトル（０，０）点を計算する際の対象画像及び参照画像の読出し（対象画像読出部１０４、参照画像読出部１０５の動作）、読み出したデータの一時蓄積（対象画像一時蓄積部１０６、参照画像一時蓄積部１０７の動作）、及びＳＡＤ計算部１０８へのデータ供給タイミングを示す。
【００４１】
このように、ＳＡＤ計算部１０８にデータが供給されると、ＳＡＤ計算部１０８はＳＡＤ値を求める（探索する）。そして、探索が完了すると、基準点（０，０）のＳＡＤ値（例えば『２０』とする）を動きベクトル検出制御部１０１に返す。
【００４２】
また、動きベクトル検出制御部１０１は、基準点（０，０）に対応した探索済点記憶部１１０内のフラグを書き換える。具体的には、図１１に示すように、『１０ｂ』に書き換える。
【００４３】
基準点（０，０）を探索すると、同時に探索点（１，０）〜（４，０）も探索できるので、同時に探索した探索点（１，０）〜（４，０）に関しては、探索結果記憶部１０９にＳＡＤ値の計算結果を格納しておく（図７に示すｔ１を参照）。すなわち、本実施形態では、同時に計５点の探索を行なうことができる。また、探索結果記憶部１０９にＳＡＤ値が格納されている探索点（１，０）〜（４，０）に対応した探索済点記憶部１１０内のフラグは『０１ｂ』に書き換える。
【００４４】
次の処理は、基準点の右の点を探索する（Ｓ１０１）。今、基準点は、点（０，０）であるため、ここでは、探索点（１，０）のＳＡＤ値を計算することになる。それを計算するにあたり、動きベクトル検出制御部１０１は、探索点（１，０）が探索済みか否かを探索済点記憶部１１０のフラグ状況を確認して判断する（ＳＵＢ１０１）。
【００４５】
例えば、図１１に示すように、フラグの値が『０１ｂ』ならば、探索は既に完了しており、ＳＡＤ値は探索結果記憶部１０９に格納されている。
【００４６】
よって、この点に関しては、改めて対象画像及び参照画像を読み出して、ＳＡＤ計算を行なう必要はなく、探索結果記憶部１０９内に格納されている探索点（１，０）に対応したＳＡＤ値（例えば『１９』）を読み出すだけで、探索を行なうことができる（ＳＵＢ１０４）。
【００４７】
なお、探索点（１，０）の情報は、以後不要となるため、探索結果記憶部１０９から削除し、メモリを開放することができる。
【００４８】
また、このステップでも、探索を行なった点に関しては、探索済点記憶部１１０のフラグを書き換えておく（図１２を参照）。
【００４９】
Ｓ１０１が完了すると、次のステップ（Ｓ１０２）に移る。Ｓ１０２では、基準点の左の点を探索する。今、基準点は（０，０）であるため、探索点（−１，０）のＳＡＤ値を計算することになる。それを計算するにあたり、動きベクトル検出制御部１０１は、探索点（−１，０）が探索済みか否かを探索済点記憶部１１０のフラグ状況を確認し判断する（ＳＵＢ１０１）。
【００５０】
例えば、図１２に示すように、フラグの値が『００ｂ』ならば、ＳＵＢ１０２に移る。このサブステップでは、実際に探索点（−１，０）を探索する。
【００５１】
探索点（−１，０）を探索すると、同時に探索点（−４，０）〜（０，０）も探索できる。これらのうち、探索点（−４，０）〜（−２，０）に関しては、探索結果記憶部１０９にＳＡＤ値の計算結果を格納しておく（図７に示すｔ３を参照）。ただし、探索点（０，０）は既に探索が完了しており、以後は、この点のＳＡＤ値を使用することはないので、格納はしない。そして探索を行なった点に関しては、探索済点記憶部１１０のフラグを書き換えておく（図１３を参照）。
【００５２】
基準点の左右の点の探索が完了すると、ＳＡＤ値の比較を行う（Ｓ１０３）。今、基準点（０，０）のＳＡＤ値である『２０』よりも、右側の探索点のＳＡＤ値『１９』の方が小さいため、基準点を右側の探索点（１，０）に移動し、再度、Ｓ１０１に移る。
【００５３】
次の処理では、基準点（１，０）の右側の点を探索する（Ｓ１０１）。今、基準点が（１，０）なので、探索点（２，０）のＳＡＤを計算することになる。それを計算するにあたり、動きベクトル検出制御部１０１は、探索点（２，０）が探索済みか否かを探索済点記憶部１１０のフラグ状況を確認し判断する（ＳＵＢ１０１）。
【００５４】
例えば、図１３に示すように、フラグの値が『０１ｂ』ならば、探索は既に完了しているので、探索結果記憶部１０９からＳＡＤ値『１８』を読み出す（ＳＵＢ１０４）。探索結果記憶部１０９内の探索点（２，０）に対応した情報は、以後不要となるので削除する（図７に示すｔ４を参照）。また、探索を行なった点に関しては、探索済点記憶部１１０のフラグを書き換えておく（図１４を参照）。
【００５５】
次いで行なう探索は、探索点（２，０）の左の点の探索（Ｓ１０２）であるが、探索済点記憶部１１０内の、この点に対応したフラグをみると『１０ｂ』であり、既に探索が完了している点（無効点と呼ぶ）なので探索はしない。
【００５６】
Ｓ１０３で行なうＳＡＤ比較においては、基準点のＳＡＤ値『１９』よりも、右点のＳＡＤ値『１８』の方が小さいため、基準点を右の点（２，０）に移し再度ステップＳ１０１を実行する。
【００５７】
以下、同様にして探索を進めていく。なお、探索済点記憶部１１０内のフラグの値が『００ｂ』に対応した点を探索する必要がある場合は、図６の四角形の太枠で囲まれた５点が同時に探索できる５点となる。
【００５８】
上記のように、本実施形態では、重複して参照画像記憶部１０３からデータを読み出す必要がないので、読み出し効率が悪化することがない。
【００５９】
また、例えば、Ｏｎｅ  ａｔ  ａ  Ｔｉｍｅ方式で、１点ずつＳＡＤ値を求めたとすれば、上記に例示したＳＡＤ値となる参照領域に対しては、図１５に示すように、探索が完了するまでに１５回も対象画像及び参照画像を読み出しＳＡＤ計算を行なう必要がある。これに対して、本実施形態では、図１６に示すように、僅か７回の読み出しに削減することができる。
【００６０】
要するに、Ｐ画素単位でパッキングされた参照画像を探索サイズ分だけ読み出そうとしても、当然、不要な画像データも同時に読み出してしまう可能性が高い。本実施形態の例でいうと、水平１６画素×垂直１６画素を読み出すのに、一旦、水平２０画素×垂直１６を読み出す必要があった。この時の左右にできる水平４画素×１６画素分のデータが不要なデータ（処理には使用されないデータ）となることは言うまでもない。従来は、この不要データは使用せずに捨てていたが、この不要データも最大限活用して、探索できる点に関しては全て探索（ＳＡＤ値の計算）するようにしたので、再度、同位置のデータの読み出しを行い、改めてＳＡＤ計算を行なうといった手間を省くことができる。すなわち、高速に探索を進め完了させることができる。
【００６１】
なお、本実施形態で示した５点の同時探索において、例えば、動きベクトル（０，０）点を探索することができるのは、以下の２通りの読み出しを行った場合である。
【００６２】
１通り目は、探索点（−４，０）、（−３，０）、（−２，０）、（−１，０）、及び（０，０）を探索するのに必要なパッキング画素データ「Ｐ２−１ｂ→Ｐ２−２ｂ→Ｐ２−３ｂ→Ｐ３−１ｂ→・・・Ｐ１７−３ｂ」を読み出した場合である。また、２通り目は、探索点（０，０）、（１，０）、（２，０）、（３，０）、及び（４，０）を探索するのに必要なパッキング画素データ「Ｐ２−２ｂ→Ｐ２−３ｂ→Ｐ２−４ｂ→Ｐ３−２ｂ→・・・Ｐ１７−４ｂ」を読み出した場合である。以下、動き探索を行なう際に２通り画像データ読出し方法がある点を『重複探索点』と呼ぶ。
【００６３】
動きベクトル検出装置１００では、上記の何れかの読み出しの際にのみ、探索点（０，０）を探索するように変更することで、例えば、１通り目の読み出し位置では、探索点（０，０）は探索せずに、探索点（−４，０）、（−３，０）、（−２，０）、及び（−１，０）の４点のみ探索し、２通り目の読み出し位置では探索するようにしてもよい。すなわち、ある動きベクトル点を探索するのに２通りの読み出し方法がある場合は、（図１６における重複探索点は、（０，０）、（４，０）、（４，１）などである。）、何れか１通りの読み出しでのみ探索するようにする。
【００６４】
これにより、５点同時探索ではなく４点同時探索になり（図１７を参照）、ＳＡＤ計算部の個数を削減することができる。すなわち、パッキングデータ数Ｐ＝４と、同時探索点数とを同一にすることで、重複探索点の発生を防ぐことができ、ＳＡＤ計算部を削減することができる。
【００６５】
また、読み出す参照画像データのサイズをさらに、水平、もしくは垂直方向に拡張することで、同時に探索できる点を増加させることができ、更に探索の高速化を図ることができる。
【００６６】
例えば、探索点（０，０）、（１，０）、（２，０）、（３，０）、及び（４，０）を探索するのに必要であった参照画像「Ｐ２−２ｂ→Ｐ２−３ｂ→Ｐ２−４ｂ→Ｐ３−２ｂ→・・・Ｐ１７−４ｂ」に対し、読み出しサイズを、水平方向に１パッキング画素拡張した参照画像「Ｐ２−２ｂ→Ｐ２−３ｂ→Ｐ２−４ｂ→Ｐ２−５ｂ→Ｐ３−２ｂ→・・・Ｐ１７−４ｂ→Ｐ１７−５ｂ」とする。これにより、上記の探索点に加え、探索点（５，０）、（６，０）、（７，０）、及び（８，０）の計９点を同時に探索することができる。
【００６７】
一方、読み出しサイズを垂直方向に１パッキング画素拡張した参照画像「Ｐ２−２ｂ→Ｐ２−３ｂ→Ｐ２−４ｂ→Ｐ３−２ｂ→・・・Ｐ１７−４ｂ→Ｐ１８−２ｂ→Ｐ１８−３ｂ→Ｐ１８−４ｂ」とすることで、探索点に加え、探索点（０，１）、（１，１）、（２，１）、（３，１）、及び（４，１）の計１０点を同時に探索することができる。また、水平、垂直双方を拡張することで、同時探索点数を増やすこともでき、処理を高速化することができる。
【００６８】
また、上記のように読み出しサイズを拡張した場合でも、重複探索点が存在する。例えば、水平方向に拡張した場合は、探索点（０，０）と（８，０）が重複探索点である。また、垂直方向に拡張した場合は、探索点（０，０）と（０，１）と（４，０）と（４，１）とが重複探索点として挙げられる。そこで、例えば、前者の場合は、探索点（８，０）を除く計８点を、また、後者の場合は、探索点（４，０）、及び（４，１）を除く８点を同時に探索することで、重複探索点が発生を防止し、最もＳＡＤ計算手段を削減することができる。この場合の同時探索点数は、パッキングデータ数Ｐの倍数となることは言うまでもない。
【００６９】
また、探索サイズが固定で処理されない場合がある。例えば、１６×１６画素だけではなく、８×１６画素、１６×８画素、８×８画素、さらには４×４画素で探索するといったマルチ探索サイズによる探索を行なう場合もある。この場合は、複数の探索サイズで探索し、その結果の中から最適なものを選ぶことになる。
【００７０】
今、４×４画素単位のブロック（サブブロック）で探索（ＳＡＤ値計算）を実行すれば、その結果から、その他の探索サイズの探索（ＳＡＤ値計算）結果を作ることができる。そのため、本実施形態で示した各探索を行なう際には、最小探索サイズである４×４画素単位で探索を行なうようにする。当然、４×４画素にて１６×１６画素分のＳＡＤ値を並列に算出するには、ＳＡＤ計算部１０８を１６個持つ必要はある。
【００７１】
そして、各点の探索が終了する度に、１６×１６画素サイズのＳＡＤ値を算出し、それを動きベクトル検出制御部１０１、又は探索結果記憶部１０９に渡すことで、本実施形態で示した探索と同処理の探索を実現することができる。
【００７２】
また、４×４画素、８×８画素、１６×８画素、８×１６画素などといった他サイズのＳＡＤ値も計算し、探索結果記憶部１０９に格納しておく。探索は、１６×１６画素単位で進んでいくが、全ての探索が終わった時点で、１６×１６画素のＳＡＤ値と、探索結果記憶部１０９に格納されている他サイズのＳＡＤ値とを用いて、どの探索サイズが一番有効であるかを含めて探索点を決定することができる。
【００７３】
また、垂直方向に１画素間引きを行ない、その画素を使用した探索であるインタレース探索（ＳＡＤ値計算）を実施すれば、画素間引きを行なわない探索（プログレッシブ探索と呼ぶ）のＳＡＤ値を作れることは言うまでもない。これは、インタレース符号化の際には非常に有効な手法となる。
【００７４】
また、本実施形態では、探索を進めるにあたり、同時に探索できる点のＳＡＤ値を探索結果記憶部１０９に格納していくので、探索結果記憶部１０９の容量は非常に多く確保しておく必要がある。
【００７５】
これを、ある閾値を超える容量のデータを格納した際に、探索結果記憶部１０９内に格納されているデータ量を減らすように工夫を加えることで、予め確保しておく容量を削減することができる。
【００７６】
例えば、その１つ目の方法としては、探索結果記憶部１０９内の探索結果データを全て消去する。同時に、消去したデータに対応した動きベクトル点に関しては、探索済点記憶部１１０内の対応するフラグを、未探索を示す『００ｂ』にする。そして、以後の探索においてその結果が必要であれば再度探索を行なうようにする。これにより、探索結果記憶部１０９の容量の上限を補償することができる。
【００７７】
また、別の手法としては、記憶手段容量が閾値を超えた時の探索点のＳＡＤ値よりも大きな値が探索結果記憶部１０９に格納されている場合は、その探索結果データを消去する。同時に、消去したデータに対応した動きベクトル点に関しては、探索済点記憶部１１０内の対応するフラグを、探索済みを示す『１０ｂ』にする。これにより、今後の探索においても使用しない不要な探索結果データのみを消去することができる。
【００７８】
また、後者の手法をまず実行し、実行後でもデータ容量が閾値を越えている場合に、前者の手法を実行するといったように、両方の手法を組み合わせることで、更に有効な手法となる。
【００７９】
《発明の実施形態２》
図１８は、本発明の実施形態２に係る動きベクトル検出装置２００の構成を示すブロック図である。同図に示すように、動きベクトル検出装置２００は、実施形態１で示した動きベクトル検出装置１００から、探索結果記憶部１０９を省くとともに、動きベクトル検出制御部１０１の代わりに動きベクトル検出制御部２０１を設けて構成したものである。
【００８０】
なお、実施形態２においても、探索サイズは１６画素×１６画素、パッキングデータ数Ｐ＝４、ＳＡＤ計算部の個数ｎ＝５とする。
【００８１】
実施形態１では、基準点のＳＡＤ値のみを動きベクトル検出制御部１０１に渡し、同時に探索できるそれ以外の点に関しては、ＳＡＤ値を探索結果記憶部１０９に格納していた。しかし、本実施形態では、探索できる全ての点（５点）のＳＡＤ値を動きベクトル検出制御部２０１に渡す。
【００８２】
動きベクトル検出制御部２０１は、以下のようにして、ＳＡＤ値の算出を制御する。本実施形態では、探索できる全ての点（５点）のＳＡＤ値のうち、最小となる点を選択して処理を行なう。
【００８３】
具体的に、図１９、図２０を用いて処理を説明する。図２０は、動きベクトル検出装置２００で行なわれる処理の流れを示すフローチャートである。なお、探索処理を行なうステップ（Ｓ２００〜Ｓ２０２、及びＳ２０５〜Ｓ２０６）においては、探索毎にサブステップ（ＳＵＢ２０１〜ＳＵＢ２０３）の処理を行なう。
【００８４】
まず、基準点（０，０）についてＳＡＤ値を計算する（図２０に示すＳ２００）。その時に同時に探索点（１，０）〜（４，０）もＳＡＤ値を計算することができるのは、実施形態１で説明した理由と同じである。その時の５点のＳＡＤ値を全て、動きベクトル検出制御部２０１に渡す。
【００８５】
図１９に示す例では、探索点（０，０）のＳＡＤ値：２０、（１，０）のＳＡＤ値：１９、（２，０）のＳＡＤ値：１８、（３，０）のＳＡＤ値：１６、そして（４，０）のＳＡＤ値：１５を渡すことになる。この例では、ＳＡＤ値：１５が最小のＳＡＤ値なので、次の基準点を（４，０）として、次の探索（図２０に示すＳ２０１）に移る。
【００８６】
なお、ＳＵＢ２０３では、５点全てについて、探索済点記憶部１１０内の値を『１０ｂ』に書き換える。
【００８７】
図２０に示すＳ２０１では、基準点の右の（５，０）を探索することになる。この点を探索する場合は（４，０）〜（８，０）の５点を同時に探索することができるが、この５点内で最小のＳＡＤとなるのは、図１９に示す例では、（４，０）のＳＡＤ：１５である。
【００８８】
Ｓ２０２では、基準点（４，０）の左の（３，０）が探索の対象であるが、（３，０）は既に探索が完了している（探索済点記憶部１１０内のフラグが『１０ｂ』）ので、再度の探索は行なわない。
【００８９】
次に、Ｓ２０３において、ＳＡＤ値の比較を行なう。左右点を探索した結果、図１９に示す例では、基準点（４，０）のＳＡＤ：１５よりも小さいＳＡＤ値が検出されなかったので、Ｓ２０５以降の処理（上点探索、下点探索）に移る。
【００９０】
Ｓ２０５では、基準点（４，０）の下の（４，１）と、それと同時に探索できる（５，１）〜（８，１）とを探索し、ＳＡＤ値が最小となる点を求める。この例では、（４，１）のＳＡＤ値：１４を下点探索の結果とする。
【００９１】
また、Ｓ２０６では、基準点（４，０）の上の（４，−１）と、それと同時に探索できる（５，−１）〜（８，−１）を探索し、ＳＡＤ値が最小となる点を求める。この例では、（５，−１）のＳＡＤ値：１６を上点探索の結果とする。
【００９２】
そして、Ｓ２０７において、ＳＡＤ値の比較を行なう。上下点を探索した結果、下点の（４，１）のＳＡＤ値：１４が、基準点のＳＡＤ（４，０）：１５よりも小さいので、基準点を（４，１）に移し、再度Ｓ２０１に処理を戻す。
【００９３】
Ｓ２０１では、基準点（４，１）の右の（５，１）が探索の対象であるが、（５，１）は既に探索済みであるので、再度の探索は行なわない。
【００９４】
また、Ｓ２０２では基準点（４，１）の左が探索の対象であるが、（０，１）〜（４，１）を同時に探索する。この例では、探索の結果、（１，１）のＳＡＤ値：８が最小となるので、これを左点の探索結果とする。
【００９５】
次に、Ｓ２０３においてＳＡＤ値の比較を行なう。この例では、基準点（４，１）のＳＡＤ：１４よりも、下の（１，１）のＳＡＤ値：８のほうが小さいので、（１，１）に基準点を移す。同様の処理を行なって、この基準点の上下左右点を探索する。この例では、ＳＡＤ値は８よりも小さくならないので、この基準点（１，１）に対応した参照ブロックが動きベクトル検知の結果となる。
【００９６】
上記のように、本実施形態は、複数点を探索する度に、その複数点の中でＳＡＤ値が最小となる点を選択して探索を進めて行くので、実施形態１で必要であった探索結果記憶部１０９が不要となる。それゆえ、よりコンパクトな動きベクトル検出装置を実現することができる。
【００９７】
なお、本実施形態においても、実施形態１で述べた重複探索点を防止するための手法『パッキングデータ数Ｐ＝同時探索点数』は有効である。また、本実施形態においては、重複探索点を無くすことで、探索済点記憶部に格納するフラグ数を削減することができる。例えば、探索点（０，０）が探索済みということは、探索点（１，０）〜（３，０）も探索済みということになる。すなわち、この４点のフラグを共有化することができる。
【００９８】
また、本実施形態での各点の探索状態は、「未探索」又は「探索済み」の２状態である。そのため、フラグは実施形態１のように、２ｂｉｔにする必要は必ずしもない。
【００９９】
また、実施形態１で示した、水平もしくは垂直方向に拡張した参照画像を読み出して、同時探索点を増やす手法は、本実施形態においても非常に有効な手法であることは、言うまでもない。
【０１００】
なお、基準点を移動する場合には、事前に探索済点記憶部１１０内のフラグの値を確認することで、処理の高速化に繋がる。
【０１０１】
本実施形態の動き探索手法は、探索結果を受け次探索点を決定するステップ（次探索点決定ステップと呼ぶ）と、実際に探索を実行して探索結果を得るステップ（ＳＡＤ値算出ステップと呼ぶ）とからなり、それを繰り返すことで動きベクトル検知が進んでいく。
【０１０２】
今、ＳＡＤ値算出ステップにおいて、例えば図２１に示す位置の４点を探索しているとする。この時の探索結果において「２−０４」のＳＡＤ値が一番小さく、この探索終了後に動きベクトル探索の基準点がこの「２−０４」に移った場合の次点決定方法（次探索点決定ステップ）を考える。
【０１０３】
基準点「２−０４」の右点「２−０５」が探索の対象となるが、この点は既に探索が完了しているので、基準点「２−０４」の左点「２−０３」の探索を行なうことになる。既に「２−０３」点の探索が完了している場合（完了しているか否かは探索済点記憶部１１０により判断）は、基準点「２−０４」の下点「３−０４」を探索することになる。既に「３−０４」点の探索が完了している場合は、基準点「２−０４」の上点「１−０４」を探索することになる。また、周囲全ての探索点が完了している場合は、「２−０４」を動きベクトルとし、探索を終了することになる。
【０１０４】
また、図２１に示す位置の４点を探索し、その探索結果、「２−０５」のＳＡＤ値が一番小さく、その探索終了後に基準点が、「２−０５」に移る場合の次点決定方法（次探索点決定ステップ）を考える。
【０１０５】
基準点「２−０５」の右点「２−０６」が探索の対象となるが、この点は既に探索を完了しているので、基準点「２−０５」の左点「２−０４」の探索を行なうことになる。これも探索を完了しているので、基準点「２−０５」の下点「３−０５」を探索することになる。既に「３−０５」点の探索を完了している場合は、基準点「２−０５」の上点「１−０５」を探索することになる。また、周囲全ての点の探索が完了している場合は、基準点「２−０５」を動きベクトルとして、探索を終了することになる。また、図２１に示す位置の４点を探索し、その探索結果、「２−０６」もしくは「２−０７」のＳＡＤ値が一番小さかった場合の次点決定方法（次探索点決定ステップ）についても同様である。
【０１０６】
以上のように、４点の探索を行なっている時に、その各点における次点探索位置を探索済点記憶部１１０内のフラグ値に基づいて予め決定しておくことで、探索が完了し次第、決定した点の探索に直ぐに移ることができため、処理の高速化にも繋がる。
【０１０７】
《発明の実施形態３》
実施形態３は、更に高速にＳＡＤ値の計算を行なうために、探索サイズ全ての画像データを用いるのではなく、サブサンプリングした画像データを用いてＳＡＤ値計算を行なう装置の例である。
【０１０８】
実施形態３に係る動きベクトル検出装置が有する構成要素は実施形態１（図１）と同様であるが、対象画像記憶部１０２、及び参照画像記憶部１０３における画像データの格納方法が異なる。
【０１０９】
図２２は、サブサンプリングした対象画像を示している。また、図２３〜図３１は、動きベクトル（０，０）点〜（８，０）点の各探索において使用する、サブサンプリングした参照画像を示している。これらの図に示すように、パッキングされた画像データのうち、探索に使用する画像は僅か半分であり、もう半分は読み出すが使用せずに捨てることになる。
【０１１０】
そこで、対象画像記憶部１０２及び参照画像記憶部１０３には、図３２に示すように、８画素単位で、使用する画素と使用しない画素とを並び替え、再パッキングしてから格納することで、使用する画像データのみを一気に読み出すことができる。
【０１１１】
対象画像について、使用する画像のみを読み出すには、Ｔ１−１ｃ→Ｔ１−３ｃ→Ｔ２−２ｃ→Ｔ２−４ｃ→Ｔ３−１ｃ→Ｔ３−３ｃ→・・Ｔ１６−２ｃ→Ｔ１６−４ｃと読み出せばよい（図３３を参照）。
【０１１２】
また、参照画像について、使用する画像のみを読み出すには、２種類の読み出し方法がある。これは、動きベクトルのｘ座標の値により異なる。動きベクトルのｘ座標が偶数の場合は、Ｐ２−２ｃ→Ｐ２−４ｃ→Ｐ２−６ｃ→Ｐ３−３ｃ→Ｐ３−５ｃ→Ｐ３−７ｃ→・・→Ｐ１７−３ｃ→Ｐ１７−５ｃ→Ｐ１７−７ｃと読み出せばよい（図３４を参照）。一方、動きベクトルのｘ座標が奇数の場合は、Ｐ２−３ｃ→Ｐ２−５ｃ→Ｐ２−７ｃ→Ｐ３−２ｃ→Ｐ３−４ｃ→Ｐ３−６ｃ→・・→Ｐ１７−２ｃ→Ｐ１７−４ｃ→Ｐ１７−６ｃと読み出せばよい（図３５を参照）。
【０１１３】
図３４に示す画像データを用いた場合には、探索点（０，０）、（２，０）、（４，０）、（６，０）、（８，０）を探索することができる。すなわち、（４ｘＰ，Ｑ）、（４ｘＰ＋２，Ｑ）、（４ｘＰ＋４，Ｑ）、（４ｘＰ＋６，Ｑ）、（４ｘＰ＋８，Ｑ）の計５点を探索することができる。
【０１１４】
また、図３５に示す画像データを用いた場合には、探索点（１，０）、（３，０）、（５，０）、（７，０）を探索することができる。すなわち、（４ｘＰ＋１，Ｑ）、（４ｘＰ＋３，Ｑ）、（４ｘＰ＋５，Ｑ）、（４ｘＰ＋７，Ｑ）の計４点を探索することができる。ただし、Ｐ及びＱは整数である。
【０１１５】
上記のように、本実施形態では、同時探索点の位置が実施形態１や実施形態２とは異なるが、それ以外の探索方法については、実施形態１や実施形態２と同様の処理を行なうことで、サブサンプリングした画素による動きベクトル探索（ＳＡＤ値計算）を高速に行なうことができる。
【０１１６】
なお、実施形態１、２に示した重複探索点を削減する手法、及び参照画像の読み出しを水平、もしくは垂直方向に拡大して同時探索点を増やす手法は、本実施形態においても非常に有効な手段であることは言うまでもない。
【０１１７】
《発明の実施形態４》
図３６は、本発明の実施形態４に係る撮像システム４００（例えばデジタルスチルカメラ（ＤＳＣ））の構成を示すブロック図である。同図に示すように、撮像システム４００は、光学系４０１、センサ４０２、ＡＤ変換器４０３（図中ではＡＤＣと略記）、画像処理回路４０４、記録転送回路４０６、再生回路４０７、タイミング制御回路４０８、及びシステム制御回路４０９を備えている。
【０１１８】
光学系４０１は、入射した画像光をセンサ４０２上に結像させるようになっている。
【０１１９】
センサ４０２は、タイミング制御回路４０８によって駆動されて、光学系４０１によって結像された画像光を蓄積し、電気信号へと光電変換するようになっている。
【０１２０】
ＡＤ変換器４０３は、センサ４０２から出力された電気信号を、デジタル信号へと変換し、画像処理回路４０４に出力するようになっている。
【０１２１】
画像処理回路４０４は、Ｙ／Ｃ処理、エッジ処理、画像の拡大縮小、及び画像圧縮伸張処理などの画像処理が行われるようになっている。画像処理された信号は、記録転送回路４０６に出力される。画像処理回路４０４は、画像圧縮のために、信号処理装置４０５を備えている。信号処理装置４０５は、上記の実施形態１〜３に係る動きベクトル検出装置の何れかである。
【０１２２】
記録転送回路４０６は、画像処理回路４０４の出力を、メディアへ記録あるいは転送するようになっている。
【０１２３】
再生回路４０７は、記録転送回路４０６によって記録あるいは転送された信号を再生するようになっている。
【０１２４】
タイミング制御回路４０８は、光学系４０１、センサ４０２、ＡＤ変換器４０３、及び画像処理回路４０４の動作タイミングを制御するようになっている。
【０１２５】
システム制御回路４０９は、システム全体の動作を制御するようになっている。
【０１２６】
なお、本実施形態に係る信号処理装置４０５における画像処理は、必ずしも光学系４０１を介してセンサ４０２に結像された画像光に基づく信号のみに適用されるものではない。例えば、外部装置から電気信号として入力される画像信号を処理する際にも適用可能であることは言うまでもない。
【０１２７】
また、対象画像のパッキングの単位と参照画像のパッキングの単位とは、必ずしも同じである必要はない。例えば、対象画像を８画素単位、参照画像を４画素単位のように、異なる単位でパッキングする場合にも本発明を適用できる。
【産業上の利用可能性】
【０１２８】
本発明に係る動きベクトル検出方法は、参照領域のデータをパッキングして記憶装置に格納した場合に、重複して参照領域のデータを読み出すことなく、動きベクトルを検出できるという効果を有し、動画像圧縮符号化における動き補償予測符号化に使用する動きベクトル検出装置や撮像システム等として有用である。
【符号の説明】
【０１２９】
１００      動きベクトル検出装置
１０１      動きベクトル検出制御部
１０２      対象画像記憶部
１０３      参照画像記憶部
１０４      対象画像読出部
１０５      参照画像読出部
１０６      対象画像一時蓄積部
１０７      参照画像一時蓄積部
１０８      ＳＡＤ計算部
１０９      探索結果記憶部
１１０      探索済点記憶部
２００      動きベクトル検出装置
２０１      動きベクトル検出制御部
４００      撮像システム
４０１      光学系
４０２      センサ
４０３      ＡＤ変換器
４０４      画像処理回路
４０５      信号処理装置
４０６      記録転送回路
４０７      再生回路
４０８      タイミング制御回路
４０９      システム制御回路
【図１】
2011147185.tif 000003
【図２】
2011147185.tif 000004
【図３】
2011147185.tif 000005
【図４】
2011147185.tif 000006
【図５】
2011147185.tif 000007
【図６】
2011147185.tif 000008
【図７】
2011147185.tif 000009
【図８】
2011147185.tif 000010
【図９】
2011147185.tif 000011
【図１０】
2011147185.tif 000012
【図１１】
2011147185.tif 000013
【図１２】
2011147185.tif 000014
【図１３】
2011147185.tif 000015
【図１４】
2011147185.tif 000016
【図１５】
2011147185.tif 000017
【図１６】
2011147185.tif 000018
【図１７】
2011147185.tif 000019
【図１８】
2011147185.tif 000020
【図１９】
2011147185.tif 000021
【図２０】
2011147185.tif 000022
【図２１】
2011147185.tif 000023
【図２２】
2011147185.tif 000024
【図２３】
2011147185.tif 000025
【図２４】
2011147185.tif 000026
【図２５】
2011147185.tif 000027
【図２６】
2011147185.tif 000028
【図２７】
2011147185.tif 000029
【図２８】
2011147185.tif 000030
【図２９】
2011147185.tif 000031
【図３０】
2011147185.tif 000032
【図３１】
2011147185.tif 000033
【図３２】
2011147185.tif 000034
【図３３】
2011147185.tif 000035
【図３４】
2011147185.tif 000036
【図３５】
2011147185.tif 000037
【図３６】
2011147185.tif 000038