(57)【要約】【課題】  精度の高いブロックマッチングをおこなう。【解決手段】  代表勾配方向特定データ演算手段２は、第nフレームおよび第kフレームの比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算する。差分演算手段４は、前記得られた２つの代表勾配方向特定データの代表勾配方向の差分を演算する。ブロックマッチング手段６は、前記得られた差分の半分ずつ前記比較対象のブロックデータをそれぞれ逆方向に回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行う。動きベクトル決定手段８は、ブロックマッチング手段５の結果に基づいて、対象フレームにおけるブロックの動きベクトルを決定する。【選択図】  図１
2011145845.tif 000002
【特許請求の範囲】
【請求項１】
第nフレームと第kフレームから対象フレームについてのブロック別の動きベクトルであるローカル動きベクトルを求めるブロック別動きベクトル演算装置において、
第nフレームおよび第kフレームについての比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算する代表勾配方向特定データ演算手段、
前記得られた２つの代表勾配方向特定データの代表勾配方向の差分を演算する差分演算手段、
前記得られた差分に基づいて、前記比較対象のブロックデータを回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行うブロックマッチング手段、
前記ブロックマッチング手段の結果に基づいて、前記対象フレームにおける当該ブロックの動きベクトルを決定する動きベクトル決定手段、
を備えたことを特徴とするブロック別動きベクトル演算装置。
【請求項２】
請求項１のブロック別動きベクトル演算装置において、
前記ブロックマッチング手段は、前記得られた差分の半分ずつ前記比較対象のブロックデータが近づく方向に、それぞれ逆方向に回転させて、前記ブロックマッチングを行うこと、
を特徴とするブロック別動きベクトル演算装置。
【請求項３】
請求項１または請求項２のブロック別動きベクトル演算装置において、
前記代表勾配方向特定データは、ブロックごとに得られたブロック別輝度勾配ベクトルであること、
を特徴とするブロック別動きベクトル演算装置。
【請求項４】
第nフレームと第kフレームから対象フレームについてのブロック別の動きベクトルであるローカル動きベクトルを求めるブロック別動きベクトル演算方法において、
第nフレームおよび第kフレームについての比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算し、
前記得られた２つの代表勾配方向特定データの代表勾配方向の差分を演算し、
前記得られた差分に基づいて、前記比較対象のブロックデータを回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行い、
前記ブロックマッチングの結果に基づいて、前記対象フレームにおける当該ブロックの動きベクトルを決定すること、
を特徴とするブロック別動きベクトル演算方法。
【請求項５】
第nフレームおよび第kフレームの１画面を構成する画素を所定の矩形のブロックにブロック化したブロックを比較するブロックマッチング方法において、
第nフレームおよび第kフレームについての比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算し、
前記得られた２つの代表勾配方向特定データの代表勾配方向の差分を演算し、
前記得られた差分に基づいて、前記比較対象のブロックデータを回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行うこと、
を特徴とするブロックマッチング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ブロック別動きベクトル演算装置に関し、特にその精度向上に関する。
【背景技術】
【０００２】
従来、動き推定法として、勾配法とブロックマッチング法とが知られている。前者は、輝度および色調の変化の傾き(勾配)を捉え、それがx,y軸でどのように動いているかを算出することにより、全体としてどのように動いているのかを算出するというものである。後者は、所定の矩形のブロックを定義し、ブロック単位でx,y方向に１画素ずらすとともに、回転θについて−２度〜＋２度程度を０．５度ピッチで回転させて、誤差が最小となるブロックマッチングを行うというものである。
【０００３】
特許文献１には、 上記勾配法およびブロックマッチング法の詳細が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2009-111599号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述のような総当たりによるブロックマッチング法は、演算処理をある程度の範囲に制限するためには、回転方向θをごく限られた範囲でしか検討が出来ないという問題があった。
【０００６】
この発明は、演算負荷を削減しつつ、精度の高いブロックマッチングが可能な動き推定装置またはその方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
(1)本発明にかかるブロック別動きベクトル演算装置は、第nフレームと第kフレームから対象フレームについてのブロック別の動きベクトルであるローカル動きベクトルを求めるブロック別動きベクトル演算装置であって、Ａ）第nフレームおよび第kフレームの比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算する代表勾配方向特定データ演算手段、Ｂ）前記得られた２つの代表勾配方向特定データの代表勾配方向の差分を演算する差分演算手段、Ｃ）前記得られた差分に基づいて、前記比較対象のブロックデータを回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行うブロックマッチング手段、Ｄ）前記ブロックマッチング手段の結果に基づいて、前記対象フレームにおける当該ブロックの動きベクトルを決定する動きベクトル決定手段を備えている。
【０００８】
このように、前記代表勾配方向を求めて、比較対象のブロックデータの回転方向を揃えておいてから前記ブロックマッチングすることにより、精度の高いブロックマッチングが可能となる。
【０００９】
(2)本発明にかかるブロック別動きベクトル演算装置においては、前記ブロックマッチング手段は、前記得られた差分の半分ずつ前記比較対象のブロックデータを近づく方向にそれぞれ逆方向に回転させて、前記ブロックマッチングを行う。したがって、かかる回転後のデータを利用して中間フレームの生成も可能となる。
【００１０】
(3)本発明にかかるブロック別動きベクトル演算装置においては、前記代表勾配方向特定データは、ブロックごとに得られたブロック別輝度勾配ベクトルである。したがって、前記ブロックマッチング前の回転処理が可能となる。
【００１１】
(5)本発明にかかるブロックマッチング方法は、第nフレームおよび第kフレームについての比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算し、前記得られた２つの代表勾配方向特定データの代表勾配方向の差分を演算し、前記得られた差分に基づいて、前記比較対象のブロックデータを回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行う。前記代表勾配方向を求めて、比較対象のブロックデータの回転方向を揃えておいてから前記ブロックマッチングすることにより、精度の高いブロックマッチングが可能となる。
【００１２】
本明細書において、「代表勾配方向特定データ」とは、特定の画像エリアの代表的な１つの勾配方向を特定するデータをいう。算出には、当該画像エリアを構成する各画素の輝度勾配ベクトル、エッジ方向ベクトル、輝度および／または色素（ＲＧＢ）の統計値より導き出すことができる。また、統計方法としては、例えば、当該エリアの各画素の持つベクトルの平均値や中央値や、より複雑には輝度勾配ベクトルのヒストグラムから算出するＨＯＧ(Histogram of Oriented Gradient）法などを用いることができる。ただし、上記に限らず多くの方法を用い得る。
【００１３】
ブロック別輝度勾配ベクトルとは、当該ブロックに属する画素の輝度勾配ベクトルをいい、本実施形態においては、そのブロックに属する画素の輝度勾配ベクトルからＨＯＧ法により算出した。
【図面の簡単な説明】
【００１４】
【図１】ブロック別動きベクトル演算装置１の機能ブロック図である。
【図２】ブロック別動きベクトル演算装置１の詳細ハード構成を示す図である。
【図３】ブロック別動きベクトル演算装置１における各処理部の処理を説明するフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明における実施形態について、図面を参照して説明する。
【００１６】
（１.機能ブロック図について）
ブロック別動きベクトル演算装置１は、第nフレームと第kフレームから対象フレームについてのブロック別の動きベクトルであるローカル動きベクトルを求めるブロック別動きベクトル演算装置であって、代表勾配方向特定データ演算手段２、差分演算手段４、ブロックマッチング手段６、および動きベクトル決定手段８を備えている。
【００１７】
代表勾配方向特定データ演算手段２は、第nフレームおよび第kフレームの比較対象ブロックについて、それぞれの代表勾配方向を表す代表勾配方向特定データを演算する。本実施形態においては、代表勾配方向特定データとして、ブロックごとに得られたブロック別輝度勾配ベクトルを採用した。差分演算手段４は、前記得られた２つの代表勾配方向特定データの代表勾配方向の差分θを演算する。
【００１８】
ブロックマッチング手段６は、前記差分θから、「−θ／２」と「＋θ／２」を求めて、前記比較対象のブロックデータが近づく方向に（「−θ／２」と「＋θ／２」）回転させてから、前記２つの比較対象ブロックについてブロックマッチングを行う。動きベクトル決定手段８は、ブロックマッチング手段６の結果に基づいて、前記対象フレームにおける当該ブロックの動きベクトルを決定する。
【００１９】
（２.各部の構成について）
ブロック別動きベクトル演算装置１の詳細ブロック図を図２に示す。ブロック別動きベクトル演算装置１は、制御部３，ブロック用レジスタアレイ５，特徴ベクトル取得部７，シフトレジスタアレイ１５，特徴ベクトル取得部１７、回転量算出部９，回転処理部２１，２２，ＰＥアレイ２４、最小値検出回路２５、ＳＲＡＭ３１，４１、およびＤＲＡＭ３３，４３を備えている。ＤＲＡＭ３３，４３以外の各部には共通のクロックが与えられることにより同期処理がなされる。ＤＲＡＭ３３，４３については、別クロックで同期処理がなされる。
【００２０】
制御部３は、シフトレジスタアレイ１５に対して、シフト制御を行う。また、ＤＲＡＭ３３、４３から画像データを読み出してＳＲＡＭ３１，４１に記憶させる処理を行う。
【００２１】
ＤＲＡＭ３３は、前フレームの画像データを１フレーム分記憶する。ＳＲＡＭ３１は、ＦＩＦＯ方式で、ＤＲＡＭ３３から前フレームの１ブロック分の画像データを記憶する。ブロック用レジスタアレイ５は、ＳＲＡＭ３１から１ブロック分の画像データが与えられると、これを記憶保持し、特徴ベクトル取得部７および、回転処理部２１に与える。ブロック用レジスタアレイ５は、ブロックのデータを１画素ずつシフト処理する。シフト処理により不足したデータは、ＳＲＡＭ３１から与えられる。ＳＲＡＭ３１から読み出し要求があると、ＤＲＡＭ３３はデータを与える。
【００２２】
ＤＲＡＭ４３は、後フレームの画像データを１フレーム分記憶する。ＳＲＡＭ４１は、ＦＩＦＯ方式で、ＤＲＡＭ３３から後フレームの探索範囲＋回転マージン分の画像データを記憶する。シフトレジスタアレイ１５は、ＳＲＡＭ４１から１ブロック分＋回転マージン分の画像データが与えられると、これを記憶する。ＳＲＡＭ４１は、シフトレジスタアレイ１５から読み出し要求がなされると、探索範囲のうち、つぎのブロックに該当するブロックの画像データおよび回転マージン分の画像データを、特徴ベクトル取得部１７および回転処理部２２に出力する。
【００２３】
特徴ベクトル取得部７は、ブロック用レジスタアレイ５から与えられた１ブロック分の画像から、当該ブロックにおけるブロック別輝度勾配ベクトルを演算する。特徴ベクトル取得部１７は、シフトレジスタアレイ１５から与えられた１ブロック分の画像から、当該ブロックのブロック別輝度勾配ベクトルを演算する。
【００２４】
回転量算出部９は、特徴ベクトル取得部７，１７から与えられた２つのブロック別輝度勾配ベクトルにおける角度の差分θを演算するとともに、回転処理部２１に「＋θ／２」を、回転処理部２２に「−θ／２」を、回転角度として与える。
【００２５】
回転処理部２１は、回転量算出部９から与えられた回転角度に基づいて、ブロック用レジスタアレイ５から与えられた画像の回転処理を行う。回転処理部２２は、回転量算出部９から与えられた回転角度に基づいて、シフトレジスタアレイ１５から与えられた画像の回転処理を行う。
【００２６】
ＰＥアレイ２４は、回転処理部２１，２２から与えられた回転処理後の両画像の差分を演算する。最小値検出回路２５は、ＰＥアレイ２４からデータが与えられると、既に記憶されている値と比較して、値が小さければそのデータを保持する。
【００２７】
（３.動きベクトル演算処理について）
図１に示す各ブロックによる処理を、図２を用いて説明する。なお、図２は、各ステップがシリアルに処理されるかのように記述している。これは、各部の処理の関係をわかりやすくするためであり、実際は、処理時間の短縮化のためにいくつかのステップは、他のステップと並列処理がなされる。
【００２８】
制御部３は、前フレームおよび後フレーム画像を取得する(図３ステップＳ１）。これは、ＤＲＡＭ３３、４３にそれぞれ、前フレームおよび後フレームの画像データを記憶することにより実行される。
【００２９】
制御部３は、前フレーム画像における１ブロックの画素数を決定する(ステップＳ３)。本実施形態においては、１ブロックを８＊８画素で構成した。
【００３０】
制御部３は、前フレームの対象ブロック番号iを初期化する（ステップＳ５）。制御部３は、各ブロックを左上座標pで特定し、i番目のブロックの画像データを記憶するように、ＳＲＡＭ３１に書き込み命令を与える（ステップＳ７）。ＳＲＡＭ３１のデータは、ブロック用レジスタアレイ５に転送される（ステップＳ９）。
【００３１】
制御部３は、後ろフレームにおいて、左上座標pに相当する部分を中心に「探索範囲」を設定し、ＳＲＡＭ４１に記憶させる(ステップＳ１１）。本実施形態においては、ブロックサイズに回転マージンを加えた範囲に、さらに、周囲１ブロック分を加えた範囲を探索範囲とした。本実施形態においてはブロックサイズを、８＊８画素とし、回転マージンとしてとしてその外周に上下左右に＋２画素としたので、探索範囲としては、２８＊２８（8+8+8+2+2=28)画素とした。
【００３２】
ＳＲＡＭ４１に記憶されたデータは、シフトレジスタアレイ１５に転送される（ステップＳ１３）。制御部３は、シフト回数数ｊを初期化する（ステップＳ１５）。
【００３３】
特徴ベクトル取得部７は、ブロック用レジスタアレイ５から与えられたブロックサイズ画像から、当該ブロックにおけるブロック別輝度勾配ベクトルを演算する（ステップＳ１７）。ここでは、ブロック別輝度勾配ベクトルvifが得られたものとする。また、特徴ベクトル取得部１７は、制御部３から演算命令が与えられると、シフトレジスタアレイ１５から与えられた画像（ブロックサイズに回転マージンを加えた分の画像）から、回転マージン分の画像を除いた中央部分の画像から、当該画像を構成するブロックのブロック別輝度勾配ベクトルを演算する（ステップＳ１９）。本実施形態においては、ブロックサイズが８*８画素であるので、回転マージンとしてその外周に上下左右に＋２画素の１２とした。ここでは、ブロック別輝度勾配ベクトルvirが得られたものとする。
【００３４】
回転量算出部９は、ブロック別輝度勾配ベクトルvifとブロック別輝度勾配ベクトルvirから、両者の角度をθiとθqnとを求めて、その差分θiqnを演算する(ステップＳ２１）。
【００３５】
回転量算出部９は、θiqnの半分であるθiqn/2を回転処理部２１に、θiqnの半分である-θiqn/2を回転処理部２２に回転量として与える。
【００３６】
これにより、回転処理部２１は、前ブロックをθiqn/2回転させ、回転処理部２２は、後ろブロックを−θiqn/2回転させる。(ステップＳ２３）。
【００３７】
ＰＥアレイ２４は、回転処理部２１，２２から与えられた回転処理後の両画像の差分を演算する(ステップＳ２５）。具体的には、回転処理後は、双方を構成するブロックの大きさは同じであるので、通常の絶対値差分和を演算すればよい。
【００３８】
最小値検出回路２５は、ＰＥアレイ２４からデータが与えられると、既に記憶されている値と比較して、値が小さければ、その時の、差分データ、タイミング、および角度を保持する（ステップＳ２７）。この場合、既に記憶されているデータが存在しないので、与えられた差分データを記憶する。
【００３９】
制御部３は、シフトレジスタアレイ１５が所定回数シフト処理を実行したか否か判断する（ステップＳ２９）。この場合、シフト回数ｊ＝1であるので、シフトレジスタアレイ１５によってシフト処理が実行される（ステップＳ３１）。かかるシフト処理により、シフト回数ｊもインクリメントされる。
【００４０】
以下、ステップＳ１９〜ステップＳ２９が繰り返される。なお、前フレームのブロックについては、ブロック別輝度勾配ベクトルがステップＳ１７にて演算されているので、それが保持されている。
【００４１】
制御部３は、シフトレジスタアレイ１５が所定回数シフト処理を実行したか否か判断する（ステップＳ２９）。すなわち、全探索範囲についての検討が終了した場合（ｊ＝ｊmax＋１）であれば、制御部３は、前フレームの全対象ブロックについて処理を終了したと判断して、最小値検出回路２５に記憶されている値を、ブロックiの動きベクトルとして出力する（ステップＳ３２）。
【００４２】
制御部３は、前フレームの全対象ブロックについて処理を終了したかを判断する（ステップＳ３３）。フレームの画素数と１のブロックサイズから全対象ブロックについて処理終了したかを判断できる。この場合、対象ブロック番号ｉ＝１であるので、処理終了していないと判断して、対象ブロック番号iをインクリメントし（ステップＳ３５）、ステップＳ７以下を繰り返す。
【００４３】
制御部３は、ステップＳ３３にて、前フレームの全対象ブロックについて処理を終了したと判断した場合には、処理を終了する。
【００４４】
なお、ステップＳ１７〜ステップＳ２３以外の処理については、一般ブロックマッチングの処理であるので、その詳細については省略する。
【００４５】
本実施形態においては、全ブロックについてブロック別輝度勾配ベクトルに基づいて画像を回転させた状態で対応するブロックのマッチングが行われて、各ブロックの動きベクトルが演算される。これにより、ブロックマッチングの精度が向上する。
【００４６】
また、本実施形態においては、ブロック別輝度勾配ベクトルに基づいて画像を回転させる際に、前フレームのブロックを＋θiqn/2、後ろフレームのブロックを−θiqn/2、とそれぞれ近づく方向に回転させている。これにより、ブロックマッチングによる差分が最小の組み合わせについて、いずれかまたは双方の回転済みデータを記憶することにより、動き補償型フレーム補間法における中間フレームとして利用することもできる。なお、かかる回転処理は、一方のブロックにおいてのみ、行うようにすることもできる。
【００４７】
（４．他の実施形態)
本実施形態においては、前フレームと後フレーム間でブロックマッチングをする場合、すなわち、k＝n+1である場合について説明したが、k＝n+α（αは整数、または分数）であってもよいし、k＝nであってもよい。k＝nである場合とは、たとえば、H.264のイントラ符号化のように、同一フレーム内でブロックマッチングを行う場合である。
【００４８】
また、順方向型探索装置である場合について説明したので、対象フレームが第k（＝n+1）フレームに該当する。これに対して、逆方向探索の場合は、対象フレームが、第nフレームとなる。さらに、対称型探索装置に適用することもできる。その場合、第n+0.5フレームが対象フレームとなる。このように、対象フレームについては、限定されない。
【００４９】
また、ブロック形状は、矩形に限定されることなく、任意の形状に適用可能である。これにより、オブジェクトの形状のブロックを定義して、ブロックマッチングするようにしてもよい。
【００５０】
本実施形態においては、ブロックマッチング型動き推定に適用した場合について説明したが、ブロックに分割する形の動き推定装置、たとえば、位相相関型動き推定装置に応用してもよい。
【００５１】
本実施形態においては、代表勾配方向特定データとしてブロック別輝度勾配ベクトルを採用したが、対象となるブロックの勾配方向を示すデータであればどのようなものであってもよく、たとえば、そのブロックにおけるエッジを抽出してブロック内の画像の角度を求めるようにしてもよい。また、勾配ヒストグラムから輝度勾配ベクトルを求めるＨＯＧ法と同様に、エッジの連続方向を画素毎に求めて、そのヒストグラムからエッジベクトルを求めるようにしてもよい。
【００５２】
また、図３ステップＳ２１において、求めた回転量の差分が、所定の差分閾値を超えている場合（あまりに大きい場合）、またはブロック別輝度勾配ベクトルの絶対値が所定の閾値を超える程度ずれている場合には、当該ブロックについては、ステップＳ２３〜ステップＳ２７の処理を行わず、ステップＳ２９にジャンプするようにしてもよい。これにより、無駄な演算時間を排除できる。
【００５３】
上記実施形態においては、本件発明をローカル動きベクトル演算装置として把握した場合について説明したが、ベクトル符号化やフラクタル符号化等のブロックマッチング装置またはその方法として把握することも可能である。
【００５４】
上記実施形態においては、各ブロックで行っているアルゴリズムを、ハードウェア記述言語（Hardware Description Language）で記述することにより、各ブロックを構成すればよい。
【００５５】
上記実施形態においては、図１に示す機能を実現するために、並列処理を可能とするために、全てをハードウェア処理する場合について説明した。しかし、これに限定されず、一部をソフトウェアによって実現してもよい。なお、その場合、プログラムの一部の処理を、オペレーティングシステム（ＯＳ）にさせるようにしてもよい。
【図１】
2011145845.tif 000003
【図２】
2011145845.tif 000004
【図３】
2011145845.tif 000005