JP3655651B2

JP3655651B2 - データ処理装置

Info

Publication number: JP3655651B2
Application number: JP21006194A
Authority: JP
Inventors: 秀明植田; 博久山口
Original assignee: テキサスインスツルメンツインコーポレイテツド
Priority date: 1994-09-02
Filing date: 1994-09-02
Publication date: 2005-06-02
Anticipated expiration: 2020-06-02
Also published as: US5815602A; JPH0884337A

Description

【０００１】
【産業上の利用分野】
本発明は、デジタル画像データの高能率符号化（データ圧縮）に関し、特に、動画像における動き推定（ＭｏｔｉｏｎＥｓｔｉｍａｔｉｏｎ）に関する。
【０００２】
【従来の技術】
近年、半導体集積技術の進展に伴い、デジタル画像データ等の高能率符号化（データ圧縮）技術が急速に進められている。こうした技術は、画像信号や音声信号などの種々のデータを統合的に扱うマルチメディアシステムや、デジタルＨＤＴＶ等におけるデータの伝送及び蓄積に不可欠なものである。
【０００３】
連続したフレーム／フィールドにおける画像データ（動画像）は、空間方向と時間方向の３次元データからなるものである。こうした画像データの空間方向の冗長性は、２次元ＤＣＴ（離散コサイン変換）などを用いて効果的に削減することが可能であり、他方、時間方向の冗長性は、フレーム／フィールド間の符号化、例えば、動き補償（ＭｏｔｉｏｎＣｏｍｐｅｎｓａｔｉｏｎ）によるフレーム／フィールド間の予測符号化により削減可能である。
【０００４】
動き補償によるフレーム／フィールド間の予測符号化は、単にフレーム／フィールド間の差分を符号化するのではなく、物体の動き情報、すなわちフレーム間の物体の空間的な変位である動きベクトルを検出し、その動きベクトルに基づいて得られた予測値との差分を符号化し、データ圧縮をより効果的にするものである。
【０００５】
動き推定を行うためには２つのアプローチがある。ペル・リカーシブアルゴリズム（ｐｅｌ−ｒｅｃｕｒｓｉｖｅａｌｇｏｒｉｔｈｍ）と、ブロックマッチングアルゴリズム（ＢＭＡ）である。一般に、後者は、前者よりもより精度がよく、ＭＰＥＧ標準に採用されている。
ブロックマッチングによる動き推定アルゴリズムについての簡単な方法は、フルサーチと呼ばれるものである。フルサーチは、サーチ範囲内のすべての位置をサーチし、画素間の絶対差分の合計の最小値によって動きベクトルを提供するものである。フルサーチの結果は、フレーム間差分において最も正確なベクトルを与えるものである。しかし、フルサーチの実行は、非常に高価であるとともに時間を要し、リアルタイムハードウェアにとって必ずしも実用的であるとはいえない。
【０００６】
このような理由により、種々の高速動き推定アルゴリズムの研究が成されてき。これらのアルゴリズムは、演算の複雑さ（演算量）を減少させる方法によって、２つのグループに分類される。１つは、ステップ毎のアプローチでサーチ位置数を減少させる方法である。もう１つは、絶対画素差分の合計を求める代わりに、別な基準、すなわちひずみ（Ｄｉｓｔｏｒｔｉｏｎ）測定を用いて各ブロックの比較演算を減少させる方法である。
【０００７】
前者のグループは、３段階の階層サーチ（３ＳＨＳ）、２次元ロガリズムサーチ（ＬｏｇａｒｉｔｈｍｉｃＳｅａｒｃｈ）、及び並列階層一次元サーチを含む。また、後者のグループは、積分投影法（ＩｎｔｅｇｒａｌＰｒｏｊｅｃｔｉｏｎ）を用いた特徴に基づくブロックマッチングアルゴリズムを含む。画素のサブサンプリングは、ブロック内の画素の断片を使用するものであり、これもまた各ブロックの比較の演算を減少させるものである。さらに、両グループの技術の組み合わせにより、改良された結果を得ることもできる。例えば、３段階階層サーチ（３ＳＨＳ）に組み合わされた積分投影法を用いたアルゴリズムである。
【０００８】
【発明が解決しようとする課題】
一般に、前者のグループの方法は、サーチされる位置が、最も一致する位置から遠ざかるにつれて、ひずみが単調に増加することを前提とする。しかしながら、このことは、必ずしも正しくはなく、動きベクトルが、最小値ではなく、極小値でトラップされてしまうことがある。さらに、アルゴリズムの不規則なデータフロー及び複雑な制御が、ハードウェアの実用化にとって欠点となる場合もある。
【０００９】
他方、後者のグループの方法は、比較的実現することが容易であり、また、積分投影法よりも適切な変換を用いることによる、改良の余地がまだまだ残されているように思われる。過去において、ブロックマッチングの動き推定アルゴリズムのための適切な変換は、未だ研究されていない。このアプローチにより演算の複雑さを低減させるためには、少ない数の変換係数によってブロックの主な特徴を表す必要があり、なお且つ係数は、簡単に計算されるものでなければならない。もし、非常に少ない計算で、すべての位置をサーチすることができるのならば、このアルゴリズムは、フルサーチと比べて非常に高速なものとすることが可能であり、しかも、フルサーチに匹敵するサーチ精度を達成することも可能である。
【００１０】
本発明の目的は、動画像の動き推定を高速、かつ高精度に行うことができるデータ処理装置及びその方法を提供することである。
本発明の他の目的は、直交変換、例えばアダマール変換に基づく動き推定により高速ブロックマッチング可能なデータ処理装置及びその方法を提供することである。
【００１１】
本発明の他の目的は、ディジタル画像データ処理においてシストリックアレイアーキテクチャに適合するデータ処理装置及びその方法を提供することである。本発明の他の目的は、低コスト、高品質のビデオエンコーダとして利用できるデータ処理装置及びその方法を提供することである。
【００１２】
【課題を解決するための手段】
上記課題を解決するために、本発明に係るデータ処理装置は、第１、第２のフレーム（またはフィールド）をそれぞれ構成する第１、第２の画像データを直交変換、例えばアダマール変換し、変換された各第１、第２の変換データを出力する変換手段と、前記変換手段に接続され、前記第１の画像データに対応する前記第１の変換データと、前記第２の変換データとを比較し、前記第１の画像データの動きを推定する推定手段と、前記推定手段から第２の画像データの予測値を求め、予測値と第１の画像データの差分を符号化する手段とを有する。
【００１３】
好ましくは、推定手段は、第１の変換データの選択された幾つかの係数（例えば低周波）のみを用いて第２の変換データとブロックマッチングされる。つまり、アダマール変換を行うことにより、エネルギーの多くが低周波成分に集中され、少ない係数でブロックの主な特徴を表すことができ、マッチング処理に要される時間を削減することが可能となる。
【００１４】
また、好ましくは、推定手段は、アダマール係数を用いた動き推定からサーチ領域を第２の画像データ内に定め、このサーチ範囲において第１画像データの動きベクトルを検出する。
【００１５】
また、本発明に係るデータ処理方法は、第１、第２のフレームまたはフィールドをそれぞれ構成する第１、第２の画像データをそれぞれアダマール変換するステップと、前記第１の画像データに対応する第１の変換データと、前記第２の画像データに対応する第２の変換データとのマッチングを行い、最適なマッチング位置を示す動き推定情報を算出するステップと、前記動き推定情報に基づき動き補償された第２の画像データを出力するステップと、第１の画像データと前記動き補償された第２の画像データとの差分を符号化するステップを含むものである。
【００１６】
好ましくは、動き推定情報を提供するために、第１、第２の変換データのマッチング後に、さらに、該マッチングの結果から第２の画像データのサーチ領域を特定し、第１の画像データをサーチ領域内でサーチするステップを含む。
【００１７】
【作用】
本発明は、上述したように、高速ブロックマッチングの実行について、アダマール（Ｈａｄａｍａｒｄ）変換に基づく動き予測を提案する。アダマール変換は、離散コサイン変換（ＤＣＴ）に類似した直交変換であり、ＤＣＴは、画像信号の圧縮について非常に優れた変換を行うものの１つであると考えられている。アダマール変換は、係数を加算と減算だけで計算することができるので、ＤＣＴと比べて非常に少ない演算でよい。本発明のアルゴリズムは、以下の説明で示すように、サーチ精度をほとんど劣化させることなく、フルサーチと比較して１／５ないし１／１０以下に演算量を低減させることができる。他の技術、つまり適応型インデッキシング（ＡｄａｐｔｉｖｅＩｎｄｅｘｉｎｇ）と結合させて、演算量を数１０分の１程度にを減少させることができる。本発明のアルゴリズムの規則的なデータフロー及び簡単な制御は、特にシストリックアレイプロセッサのようなハードウェアへの実用化において、優れた効果を発揮することができる。
【００１８】
【実施例】
以下、本発明の好適な実施例について説明する。
図１は、一般的な画像データ符号化回路の構成を示すブロック図である。現フレームを構成するディジタル画像データ１２は、動き補償を施された参照フレームのディジタル画像データ１４と減算器１６により差分をとられ、離散コサイン変換部（ＤＣＴ）１８へ供給される。ＤＣＴによる変換を施されたデータは、量子化部２０により、量子化され、そして、可変長符号化部２２により符号化され、伝送される。
【００１９】
また、量子化されたデータは、逆量子化部２４へ供給され、逆量子化された後、ＩＤＣＴ２６により逆ＤＣＴ変換され、加算器２８により画像データ１４と加算される。加算器２８からの画像データは、フレームメモリ３０に供給され、１フレーム前（場合によっては、前のフィールドや、後のフレームまたはフィールドを参照することがある）の画像データとして出力されるようメモリ内に蓄積される。動き補償部３２は、現フレームの画像データ１２と、フレームメモリ３０からの前フレームの画像データ３４を受け取り、現フレーム内の１６＊１６画素のブロックについて動きベクトルを求め、その動きベクトルによって動き補償された画像データ１４（予測値）を減算器１６へ供給する。
【００２０】
本実施例による動き推定アルゴリズムは、アダマール変換を利用するものであり、これについて説明する。図２は、本実施例に係る動き補償部の内部構成を示すブロック図である。
【００２１】
動き補償部３２は、画像データについてアダマール変換を行うアダマール変換部１１０と、アダマール変換部１１０に接続された第１段階処理部１２０と、現フレーム及び前フレームの画像データを受け取り、かつ第１段階処理部１２０に接続された第２段階処理部１３０と、第２段階処理部１３０に接続された動き補償回路１４０とを有する。
【００２２】
アダマール変換部１１０は、現フレーム（４８０＊７０４画素）の画像データ１２と、フレームメモリ３０からの前フレーム（４８０＊７０４画素）の画像データ３４を受け取り、直交変換の一種であるアダマール変換を行う。アダマール行列は、変換行列の要素が＋１または−１のため、変換を加減算だけで行うことができるという特徴を持つ（詳細は後述）。
【００２３】
第１段階処理部１２０は、アダマール変換部１１０によって変換された係数データ１１２、１１４を受け取り、ブロックマッチングを行う。本実施例による第１段階処理部１２０は、現フレームの係数データ１１２から１６＊１６画素のブロック（以下、ターゲットブロック）の係数データを抽出し、また、前フレームの係数データ１１４から垂直方向（−１６，＋１５）、水平方向（−６４，＋６３）のサーチウィンドウ内の係数データを抽出する。そして、ターゲットブロックについてのブロックマッチングを行い、マッチング位置を算出する。
【００２４】
第２段階処理部１３０は、第１段階処理部１２０により得られたマッチング位置を受け取り、マッチング位置から前フレームの画像データ内にサーチウィンドウを特定し、ターゲットブロックについての最終的な動きベクトルを求める。ここでは、アダマール変換された係数データを用いるのではなく、一般のフルサーチと同様の画像データを用いた処理が実行される。
【００２５】
動き補償回路１４０は、第２段階処理部１３０により検出された動きベクトルに応じた予測値、すなわち動き補償された画像データ１４を減算器１６（図１）へ供給するものである。
【００２６】
以下に、（１）アダマール変換特性、（２）アダマール変換に基づく動き推定アルゴリズム、（３）本アルゴリズムの演算量、（４）ＭＰＥＧテストシーケンスを用いたシミュレーション結果を詳細に説明する。
【００２７】
（１）アダマール変換特性
画像Ｘ（ｉ，ｊ）（０≦ｉ，ｊ≦Ｎ−１）のブロックについての２次元アダマール変換は、次のように表される。
【数１】
〔Ｆ（ｕ，ｖ）〕＝〔Ｔ〕〔Ｘ（ｉ，ｊ）〕〔Ｔ〕^t 式（１）
【００２８】
ここで、Ｔはアダマール変換行列である。次数Ｎ＝２ⁿのアダマール変換行列は、次式によって定義される。
【数２】

ここで、
【数３】

項ｋ_mとｌ_mは、ｋとｌの２進表示の各ビット状態である。アダマール変換行列は、対称行列である。すなわち、〔Ｔ〕^t＝〔Ｔ〕である。８＊８のブロックサイズのケースでは、Ｔは、以下のように表される。
【数４】

【００２９】
本実施例では、８＊８のブロックサイズを取り扱うこととする。ここで、式（４）は、連続的に順序付けされたアダマール変換行列であり、他方、式（２）は、自然型アダマール変換の定義であることに留意を要する。これらの２つのアダマール変換は、同一組の基底関数を有する同一の変換であるが、基底関数の順序に差異を生ずる。それ故、変換係数は、異なる順序で配置される。なお、以後の説明において、アダマール変換係数の要素のいかなる記載、例えば（０，２）要素のような記載は、式（４）の定義に対応するものとする。
【００３０】
また、電力スペクトラムを解析するために、式（１）は次のように表される。
【数５】
〔ｆ（ｗ）〕＝〔Ｔ’〕〔ｘ（ｚ）〕式（５）
ここで、〔ｆ（ｗ）〕^t＝〔ｆ₀₀...f₇₇〕，〔ｘ（ｚ）〕^t＝〔ｘ₀₀...x₇₇〕，〔Ｔ’〕は式（２）から導出された６４＊６４アダマール変換行列である。
【００３１】
共分散は、以下のように定義される。
【数６】

【００３２】
ここで、Ｅ（）は、統計上の期待値を表し、Ｒは画素領域の共分散行列である。式（６）の左辺をアダマール変換領域の電力スペクトラムとして定義する。マトリックスＲの詳細は、画像信号と統計上の画像モデルの特性によって決定される。マトリックスＲは独立マルコフ過程に従って設計され、自己相関係数ρを有するという最も簡単なケースを仮定すると、マトリックスＲは次のように表される。
【数７】

ここで、ｉとｊはマトリックスの座標を表し、Ｎはブロックのサイズ（＝８）である。
【００３３】
〔Ｅ（ｆｆ^t）〕の対角線上の要素は、入力画素信号に関して各アダマール変換係数に分配された平均電力を表す。図３は、自己相関係数ρ＝０、９５のケースで計算されたアダマール変換領域の電力スペクトラムを示すものである。同図に示すように、エネルギーが、低周波数のアダマール変換係数に集中していることがわかる。例えば、信号エネルギーの７７％（０，０）の係数（直流（ＤＣ）要素）に集中し、信号エネルギーの９１％が５つの低周波要素（０，０），（０，１），（０，２），（１，０）及び（２，０）に集中している。
【００３４】
（２）アダマール変換に基づく動き予測アルゴリズム
上述したように、アダマール変換は、信号ブロックの特徴の大部分を、幾つかの低周波係数に集中させている。言い替えれば、ブロックのおおよその特徴は、ごく少数の係数によって表すことができる。つまり、アダマール変換領域内の低周波係数を用いて動き推定を実行できることを意味する。演算の複雑さの低減は、各ブロックの比較を実行するための少ない演算数によって達成することができる。
【００３５】
本実施例のアダマール変換行列は、８行＊８列で構成される。従って、例えば１６＊１６のターゲットブロックは、図４に示すように、４つの８＊８ブロックに分割され、そして、各ブロックは図５に示すようにアダマール変換される（図中、マーク“Ｏ”は、低周波係数の選択例を示す）。
【００３６】
こうして、第１段階処理部１１０は、係数データ１１２から取り出された１６＊１６のターゲットブロックと、前フレーム内の所定のサーチウィンドゥとの間で、係数データを比較することによりブロックマッチングを行う。ターゲットブロックの係数の内、マッチングに供されるのは、低周波係数だけであり、例えば、上述した５つの要素（０，０），（０，１），（０，２），（１，０）及び（２，０）が用いられる（図５のマークを付けられた要素）。ターゲットブロックのマッチングに、どの低周波要素を用いるかは、予め設定しておく必要がある。こうして、８＊８のブロックについての最小のひずみ（Ｄｉｓｔｏｒｔｉｏｎ）を有するマッチング位置（Ｖ’_x'Ｖ’_y）が低周波アダマール変換係数の絶対誤差の合計を用いて検出される。
このひずみ関数は、以下のように表される。
【００３７】
【数８】

ここで、
【数９】

【００３８】
１６＊１６のターゲットブロックのマッチング位置は、式（８）により求められた８＊８の４つのブロックについてのひずみＤの和として定義される。このように、選択された低周波要素に対応する少数の組み合わせを計算するだけで、マッチング位置の検出が可能となる。
【００３９】
通常は、第１段階の処理結果として、ベストに近いマッチングを達成することができる。しかしながら、第１段階では、低周波係数だけしか考慮していないため、（Ｖ’_x'Ｖ’_y）とベストマッチ位置との間で、わずかな不一致を生じさせるかもしれない。このような理由から、本実施例では、第２段階において近隣フルサーチを実行する。フルサーチは、画素間の絶対誤差の合計の最小を求める方法である。
【００４０】
第２段階処理部１２０は、現フレームと前フレームの画像データ１２、３４と、第１段階処理部１１０で求められたマッチング位置（Ｖ’_x'Ｖ’_y）を受け取り、当該マッチング位置の近隣においてフルサーチを実行する。サーチ範囲は、（Ｖ’_x'Ｖ’_y）の近隣の垂直及び水平方向（−２、＋２）である。つまり、第１段階で求められたマッチング位置を基準として、その近隣の範囲において、さらに、画素精度（場合によっては、半画素精度）のマッチングを行うことにより、より高精度の動き予測を可能にする。
こうして最終的なマッチングによりターゲットブロックの動きベクトルが求められる。動き補償回路１４０は、第２段階処理部１３０からの動きベクトルを受け取り、動き補償された前フレームの画像データ１４を出力する。
【００４１】
（３）本実施例に係るアルゴリズムの演算量
本実施例によるアルゴリズムでは、一連の加算と減算を実行しなければならない。式（４）に示す２√２の除算は必要ではない、なぜなら、２√２の除算なしで同一の動きベクトルを得ることができるからである。フルサーチもまた、一連の加算と減算を必要とするだけである。こうして、従来のフルサーチと比較した場合の、本アルゴリズムによる加減算数を演算の複雑さとして考えることができる。
【００４２】
後述のシミュレーション条件は、画像サイズを４８０＊７０４、ブロックサイズを１６＊１６、サーチ範囲を垂直方向（−１６，＋１５）；水平方向（−６４，＋６３）、サーチを画素精度（整数サーチのみ）とし、これに対応するアルゴリズムの演算の複雑さを求める。
【００４３】
図６は、使用された係数とアルゴリズムの高速化ファクター間の関係をまとめたものである。ここで、第１段階で使用された低周波係数が、８＊８ブロックについて、３つの（０，０），（０，１），（１，０）であれば、使用された係数の数は、１６＊１６のブロックサイズ全体で１２（＝３＊４）となる。高速化ファクターは、同じフルサーチ範囲のフルサーチを“１”とした場合の時間比を表すものであり、例えば“１８．３”であれば、フルサーチの１／１８．３の処理時間を意味する。高速化ファクターの上限は、２５６を、使用された係数の数で割った値であり、使用された数が“１２”であれば、２１．３となり、フルサーチの１／２１．３の処理時間が限界であることを意味する。つまり、高速化ファクターは、上限のファクターから、第１段階処理以外の例えば、第２段階処理やアダマール係数の計算、その他の処理に費やした時間を考慮したものである。
【００４４】
本実施例のアルゴリズムでは、いかなるケースにおいても、幾つかの低周波係数を使用するだけであり、係数は前処理によって効果的に計算され、演算の複雑さは、主に、式（８）でカウントされるべきアダマール変換係数の数によって決定される。選択されたアダマール変換係数及び近隣フルサーチについてのオーバーヘッド計算は、後述するようにかなり少ない。
【００４５】
以下の説明では、（０，０），（０，１），（０，２），（１，０）及び（２，０）の５つの係数を選択した場合についての演算の複雑さ（演算量）を求める。なお、他の係数を選択した場合についても、同一の方法により計算される。
【００４６】
先ず、本実施例のアルゴリズムでは、同一のアダマール変換係数が繰り返し使用されることを理解しておく必要がある。これは、以下の２つの理由によるものである。
（イ）１ブロック及び他のブロックについてのサーチ範囲が互いに重複する。参照フレーム内のある画素は、最大２７ブロックで、サーチ範囲内に存在する。
（ロ）１６＊１６ブロックが８＊８ブロックに分割される。従って、サーチ範囲内の８＊８ブロックは、最大４つのマッチング位置で使用される。
【００４７】
従って、８＊８ブロックのすべてにおいて、前処理として、予め必要なアダマール変換係数のすべてを計算しておくことが望ましい。参照される前フレームには、全体で４７３＊６９７個の８＊８ブロックが存在する。
【００４８】
次に、アダマール変換係数についての合理的な求め方について説明する。図７は、８＊８アダマール変換の基底関数の１部を示すものである。同図において、例えば、（０，０）は、アダマール変換の直流成分であり、画像データの各画素値の合計に１／８を掛けたものに等しい。（１，０）は、上述したようにアダマール変換の低周波係数であり、これは、４行＊８列の上半分の画像データの各画素値の合計に１／８を乗じたもの（白い部分）から、黒い部分で示す４行＊８列の下半分の画像データの各画素値の合計に１／８を乗じたものを減算した値に等しい。
【００４９】
このような点に鑑み、アダマール変換係数を計算するために、最初に、参照フレーム内のすべての８＊８ブロックについて、１＊８，８＊１，２＊８，８＊２，４＊８及び８＊４サブブロックの画素値の合計を計算しておくことが望ましい。そして、これらのサブブロックの値の適当な組み合わせの加減算により、適宜所望のアダマール変換係数を容易に求めることができる。その際、同一のサブブロックの値は、同一の８＊８ブロックの他のアダマール変換係数の計算、さらに、他の８＊８ブロックのアダマール変換係数の計算にも用いることが可能である。
【００５０】
図８は、上記方法によるアダマール変換係数を計算するためのデータフローを示すものである。参照フレームの８＊８ブロックの各画素データ２１０について、８＊１のサブブロック２２０の画素値の合計を求め、この合計を利用して８＊２のサブブロック２３０の合計を求め、さらに、８＊２の合計を利用して８＊４のサブブロック２４０の合計を求める。１＊８、２＊８、４＊８のサブブロック２５０、２６０、２７０についても同様である。こうして、これらのいくつかのサブブロックの値を加算、または減算することにより、アダマール変換係数データ２８０が求められる。
【００５１】
また、サーチウィンドゥ内の１６＊１６の参照ブロック（８＊８に分割）と、ターゲットブロック（８＊８に分割）とのマッチングを行い、引き続き、サーチウィンドゥ内で参照ブロックを１画素分水平にシフト（場合によっては、これ以外の水平及び垂直シフト）させて、次のマッチング計算が行われる。この場合、参照ブロック内の１＊８のサブブロックを例にとると、先に用いられた１＊８のサブブロックが、次のマッチングで、１列分水平シフトされた１＊８のサブブロックの値が必要となる。しかし、一度、１＊８サブブロックの値が計算されれば、同一行の次の１＊８サブブロックの値は、前に計算された値から１回の減算及び１回の加算で求めることができる（図９参照）。つまり、
【数１０】

が計算されると、次のサブブロックの値Ｉ（１）は、Ｉ（０）−Ｘ（０）＋Ｘ（８）でよい。こうしたアダマール変換係数は、上述したように、予め計算して求めておくので、マッチング毎に計算を行う必要はない。
【００５２】
ここで、フレーム内のすべての１＊８サブブロックの値についての計算回数を求めると、
【数１１】
（７＋２＊６９６）＊４８０＝６７１，５２０式（１０）
８＊１サブブロックについての計算は、
【数１２】
（７＋２＊４７２）＊７０４＝６６９，５０４式（１１）
２つの１＊８サブブロックの値の合計から得られた２＊８サブブロックの値と、２つの８＊１サブブロックの値の合計から得られた８＊２サブブロックの値についての計算回数は、それぞれ以下のようである。
【００５３】
【数１３】
６９７＊４７９＝３３３，８６３式（１２）
【数１４】
４７３＊７０３＝３３２，５１９式（１３）
２つの２＊８サブブロックの値の合計から得られた４＊８サブブロックの値と、２つの８＊２サブブロックの値の合計から得られた８＊４サブブロックの値についての計算回数は、それぞれ以下のようである。
【数１５】
６９７＊４７７＝３３２，４６９式（１４）
【数１６】
４７３＊７０１＝３３１，５７３式（１５）
【００５４】
５つの選択されたアダマール変換係数を計算するために、各８＊８ブロックについて、７回の加算または減算を必要とする。つまり、要素（０，０）は、２つの８＊４サブブロック（あるいは４＊８サブブロック）の加算、要素（０，１）は、２つの８＊４サブブロックの減算、要素（０，２）は、１つの８＊４サブブロックと２つの８＊２サブブロックとの加減算、要素（１，０）は、２つの４＊８サブブロックの減算、要素（２，０）は、１つの４＊８サブブロックと２つの２＊８サブブロックとの加減算から求められる。
【００５５】
こうして、参照フレーム内のアダマール変換係数を計算すると、
【数１７】
７＊４７３＊６９７＝２，３０７，７６７式（１６）
全体で、
【数１８】
６７１，５２０＋６６９，５０４＋３３３，８６３＋３３２，５１９＋３３
２，４６９＋３３１，５７３＋２３０，７７６７＝４，９７９，２１５式（１７）
【００５６】
これは、１フレーム内の選択されたアダマール変換係数（５つの低周波係数）についての計算時間である。従って、１つの動きベクトルについてのアダマール変換の計算時間は、次式に等しい。
【数１９】

【００５７】
次に、現フレームの４つの８＊８ブロックに分割される１６＊１６ターゲットブロックの係数についての計算回数を求める。１＊８と８＊１の各サブブロックの値は７回の加算によって計算される。従って、１つの８＊８ブロック内の８つの１＊８と８＊１サブブロックの値の計算回数は、
【数２０】
７＊８＊２＝１１２式（１９）
２つの１＊８サブブロックの値の加算から得られる４つの２＊８サブブロックと、２つの８＊１サブブロックの値の加算から得られる４つの８＊２サブブロックについての計算回数は、
【数２１】
４＊２＝８式（２０）
２つの２＊８サブブロックの値の加算から得られる３つの４＊８サブブロックと、２つの８＊２サブブロックの値の加算から得られる３つの８＊４サブブロックについての計算回数は、
【数２２】
３＊２＝６式（２１）
【００５８】
上記サブブロックの値から選択されたアダマール係数を計算するため、７回の計算を要する。
こうして、４つの８＊８ブロックに分割される現在のブロックの係数についての計算回数は、
【数２３】
（１１２＋８＋６＋７）＊４＝５３２式（２２）
以上のようにして、アダマール変換の計算回数が求められる。
アダマール変換領域における第１段階の比較では、
【数２４】
（５＊４）＊２＊３２＊１２８＝１６３，８４０式（２３）
（３２＊１２８サーチ位置の各々について５＊４の加算と５＊４の減算）
第２段階における（−２，＋２）近隣のフルサーチについて、
【数２５】
２５６＊２＊５＊５＝１２，８００式（２４）
（５＊５サーチ位置の各々について２５６の加算と２５６の減算）
【００５９】
こうして、動きベクトルについてのアダマール変換に基づく動き推定の計算回数は、式（１８）＋式（２２）＋式（２３）＋式（２４）である
【数２６】
３７７２．１＋５３２＋１６３，８４０＋１２，８００＝１８０，９４４．１式（２５）
他方、同一サーチウィンドウに対するフルサーチの計算回数は、
【数２７】
２５６＊２＊３２＊１２８＝２，０９７，１５２式（２６）
こうして、高速化ファクターは、
【数２８】

【００６０】
式（２５）に示すように、計算回数の大部分は第１段階のアダマール変換領域のマッチングに要され、高速化ファクターの上限を決定する。この場合、例えば、高速化ファクターの上限が１２．８（＝２５６／２０）である。実際に、高速化ファクターは、アダマール変換と近隣フルサーチのオーバーヘッド計算により、１２．８から１１．６へわずかに減少する。
【００６１】
ここで、１つの動きベクトルについて選択されたアダマール変換係数に、３７７１．１＋５３２＝４３０４．１の計算回数を要することに留意すべきである（式（１８）（２２））。１つの動きベクトルについて３２＊１２８＝４０９６のサーチ位置を有する。これは、１つのサーチ位置についてアダマール変換の必要とされる計算回数が、わずか４３０４．１／４０９６＝１．０５であることを意味する。ブロックごとの比較による計算回数である、（５＊４）＊２＝４０（式２３）よりもはるかに小さい値である。
【００６２】
（４）シミュレーション結果
シミュレーションは、７つのＭＰＥＧテストシーケンスの各２フレームについて合計１４フレームを対象に行われ、各フレームを直前のフレームで補償するようにした。シミュレーションの条件は、以下のようにＭＰＥＧ標準の単純化したものであった。
【００６３】
予測モード：フレームモード、
画像サイズ：４８０＊７０４、
ブロックサイズ：１６＊１６、
サーチ範囲：垂直方向（−１６．＋１５）、水平方向（−６４，＋６３）、
【００６４】
（１）画素精度（整数サーチ）
シミュレーションについては、画像シーケンスのインタレース構造を考慮して、第１段階において３つのケースの係数パターン群を実行することとした。インタレース構造は、（７，０）係数（図７参照）において大きなエネルギーを発生するものである。テストされた３つのケースを以下に示す（図１０参照）。
【００６５】
（ａ）対称−１２，対称−２０，対称−２８，対称−３６，対称−４４；
対角線に関して対称となるように、（０，ｖ）と（ｕ，０）要素の同一数を使用するものである。数字は、第１段階の１６＊１６ブロックにつき使用されるアダマール変換係数の数を意味する。例えば、“１２”は、各８＊８ターゲットブロックにおいて、使用する係数を３つ選択したことを意味し、同様に“２０”であれば係数を５つ選択したことを意味する。
【００６６】
（ｂ）非対称−１６，非対称−２４，非対称−３２，非対称−４０，非対称−４８；
８＊８アダマール変換係数マトリックスにおいてもう１つの（ｕ，０）要素を使用したものである。
【００６７】
（ｃ）対称＋（７，０）−１６，対称＋（７，０）−２４，対称＋（７，０）−３２，対称＋（７，０）−４０，対称＋（７，０）−４８
アダマール変換係数マトリックスに、低周波数要素（０，ｖ）と（ｕ，０）と同一の数を使用するとともに、（７，０）要素を使用するものである。言い替えれば、上記（ａ）の対称のものに、（７，０）を加えたものである。
【００６８】
なお、図１０（ａ）は対称−２０、（ｂ）は非対称−２４、（ｃ）は対称＋（７，０）−２４を示し、マーク“Ｏ”が使用される係数を示す。
図１１は、サーチ精度劣化と使用されたアダマール変換係数の数との間の関係をｄＢスケール上に示すものである。ここでは、“ＦＯＯＴＢＡＬＬ”のフレーム＃１３２、＃１３３と、“ＢＩＣＹＣＬＥ”，“ＣＡＲ”，“ＣＨＥＥＲＬＥＡＤＥＲＳ”，“ＦＬＯＷＥＲＧＡＲＤＥＮ”，“ＭＯＢＩＬＥ＆ＣＡＬＥＮＤＡＲ”，“ＴＡＢＬＥＴＥＮＮＩＳ”のフレーム＃２、＃３の１４フレームについて動き補償を行った。
【００６９】
サーチ精度は、１４フレームのすべてを通じての補償されたフレームと、原フレームの画素間の自乗誤差の和によって測定され、フルサーチのものと対比される。自乗誤差の和の測定は粗いが、簡単でかつエンコーダに依存しない測定法である。フルサーチは、図１１には示されないが、０．０ｄＢ−２５６に対応する。１／４または１／８の画素サブサンプリング法の後に（−２，＋２）近隣フルサーチを行った場合（つまり、第１段階のアダマール領域でのマッチングを画素サブサンプリングによるマッチングに置き換えることを意味する）についても比較のために図１１に示してある。これらは、横軸の６４と３２にそれぞれ対応する。アダマール変換に基づく動き推定は、画素サブサンプリング方法よりも少ない計算で、より優れたサーチ精度を達成することができるということがわかる。
【００７０】
本実施例において、さらに他の計算低減方法を有する技術、いわゆる適応型インデックシング技術を組み合わせた場合のシミュレーションを実行した。この技術によって、サーチ範囲内の各２または４（もしくはそれ以上）の位置が、周囲のブロックの動きベクトルを参照しながら第１段階でサーチされる。換言すれば、第１段階の動きフィールドがサブサンプリングされる。どのサブサンプリング格子が第１段階で選択されるべきかということを決定することに関し、周囲のロックで得られた動きベクトルを参照することによって、第１段階で最小位置がサーチされる可能性が大きくなる。こうして、サーチ精度は、サーチ範囲内のすべての位置が第１段階でサーチされるケースに近づくように保たれる。第２段階の近隣フルサーチは、アダマール変換に基づく動き推定のみの場合と同一の方法として適用される。シミュレーションは、アダマール変換に基づく動き推定のみのケースにおいて比較的良い精度を示した。係数パターンの６つのケース、非対称−１６、対称−２０、対称＋（７，０）−２４、３２、４０、４８について実行された。図１２は、第１段階での１／２，１／４及び１／８サーチ位置でのケースのシミュレーション結果を示すものである。すべての位置が第１段階でサーチされたケース（１／１）の結果も示してある。アダマール変換に基づく動き推定と適用型インデックシング技術の組み合わせのアルゴリズムは、フルサーチに近いサーチ精度を達成することができ、その一方で、計算の複雑さを数１０倍減少することができる。例えば、計算が１／１８で劣化が０．１２ｄＢ、計算が１／３６で劣化が０．１８ｄＢである。
【００７１】
尚、本実施例では、１フレーム前の画像データを参照フレームとして用いたが、これに限らず、前のフィールドや、後のフレームあるいはフィールドを参照フレームまたは参照フィールドとして用いることも可能である。
また、本実施例によれば、ＭＰＥＧ−１やＭＰＥＧ−２（１６＊１６画素、または８＊１６画素のブロックサイズを処理単位とする）に利用することも可能である。
【発明の効果】
本発明において、アダマール変換に基づく動き推定は、高速ブロックマッチングアルゴリズムに対する解決として提案されたものである。本発明の動き予測アルゴリズムは、高速性、規則性、単純化、及び優れた精度の点で利点を有する。アダマール変換に基づく動き推定と適応型インデックシング技術の組み合わせは、ほとんどサーチ精度を損なうことなく、数１０倍程度計算の複雑さを低減することができる。実際に、高速化ファクターは、達成される精度にほとんど反比例する。また、本発明のアルゴリズムは、シストリックアレイアーキテクチャーに適するもので、それは、その規則性及び単純性によるものである。このアルゴリズムをハードウェア実装に適用することで、低コスト、高品質ビデオエンコーダが近い将来に現実の技術となることが期待できる。
【図面の簡単な説明】
【図１】一般的な画像データ符号化回路の構成を示すブロック図。
【図２】本実施例の動き補償部の内部構成を示すブロック図である。
【図３】自己相関係数ρ＝０．９５の場合におけるアダマール変換領域の電力スペクトラムを示す図。
【図４】１６＊１６ブロックが４つの８＊８ブロックに分割された状態を示す図。
【図５】各８＊８ブロックがアダマール変換された状態を示す図。
【図６】使用されたアダマール係数とアルゴリズムの高速化ファクター間の関係を示す図。
【図７】８＊８アダマール変換の基底関数の１部を示す図。
【図８】本実施例におけるアダマール変換係数を計算するためのデータフローを示す図。
【図９】１＊８サブブロックの値の計算方法を示す図。
【図１０】シミュレーションに用いたアダマール変換係数の例を示す図。
【図１１】サーチ精度劣化と使用されるアダマール変換係数の数との関係を示す図。
【図１２】アダマール変換に基づく動き推定と適応型インデックシング技術の組み合わせにおけるサーチ精度劣化と高速化ファクターとの関係を示す図である。
【符号の説明】
１２、３４画像データ
３２動き補償部
１１０アダマール変換部
１２０第１段階処理部
１３０第２段階処理部
１４０動き補償回路

Claims

第１及び第２の画像データを受け取り、前記第１及び第２の画像データを夫々第１及び第２のアダマール変換データに変換するアダマール変換手段と、
前記第１のアダマール変換データから選択された低周波係数を用いて前記第１及び第２のアダマール変換データのブロックマッチングを行いマッチング位置を検出する第１処理手段と、
前記マッチング位置、並びに前記第１及び第２の画像データを受け取り、前記第２の画像データの前記マッチング位置の近隣のフルサーチを実行することによって前記第１の画像データのターゲットブロックの動きベクトルを求める第２処理手段と、
前記第１の画像データ及び前記動きベクトルによって補償された第２の画像データ間の差分を符号化する符号化手段
を含むデータ処理装置。