(57)【特許請求の範囲】
【請求項１】
映像データフレームを圧縮するために動き推定を行う動き推定器において、
以前の探索領域のデータをライン別に貯蔵する複数個のメモリ領域を具備する以前の探索領域メモリと、現在の処理領域のデータをライン別に貯蔵する現在の処理領域メモリを具備する第１メモリ部と、
前記複数個のメモリ領域から出力されるライン別の以前の探索領域データを、前記現在の処理領域のデータの１ラインの絶対差和(ＳＡＤ；sum of absolute difference)の計算のために必要な所定のデータ単位で１クロック毎に所定画素単位ほどシフトさせながら前記所定のデータ単位で以前の探索領域データを出力する複数個の以前の探索領域データ供給部と、
前記複数個の以前の探索領域データ供給部のうち所定画素単位ほどシフトさせながら前記所定のデータ単位で以前の探索領域データを出力する以前の探索領域データ供給部を選択する第１スイッチング部と、
前記現在の処理領域メモリにライン別に貯蔵された前記現在の処理領域のデータをライン別に選択して出力する第２スイッチング部と、
前記第２スイッチング部から出力されるライン別の現在の処理領域のデータを貯蔵する複数個のレジスタと、一方の入力端は前記レジスタに連結され、他方の入力端は前記第１スイッチング部に連結され、前記第１スイッチング部により選択された前記以前の探索領域データの所定データ単位と前記第２スイッチング部により選択されたライン別の現在の処理領域のデータ間の絶対差和を計算する複数個の減算器を具備する複数個の絶対差和計算部を含む計算部と、
探索領域を−ｐから＋ｐ(ｐは整数)とする時、前記絶対差和計算部から出力された絶対差和データを２ｐ＋１ほどシフトして前記各絶対差和計算部から出力される絶対差和を合算するシフトレジスタ部と、を含むことを特徴とする動き推定器。
【請求項２】
上位階層、中間階層及び下位階層の３階層で階層的動き推定を行い、前記中間階層及び下位階層では探索領域が−２〜＋２ピクセルであり、入力映像フレームの最大サイズは水平方向に２２個のマクロブロックに該当する時、
入力データをバッファリングするバッファと、
前記バッファから出力されたデータを２５シフトする２５シフトジスタと、
部分ＳＡＤ値と前記シフトレジスタから出力されたデータを加えてＳＡＤ値を出力する加算器と、
加算器から出力されたＳＡＤ値に基づき動きベクトルを生成するＳＡＤ比較及び動きベクトル生成部と、
動きベクトル値を２２シフトさせてＳＡＤ比較及び動きベクトル生成部に出力する２２シフトレジスタと、をさらに含むことを特徴とする請求項１に記載の動き推定器。
【請求項３】
前記２２シフトレジスタは、３階層で階層的動き推定を行うとき、中間階層で周辺マクロブロックがもつ動きベクトルの相関関係を用いて初期探索点をさらに得るために２２シフト動作を行うことを特徴とする請求項２に記載の動き推定器。
【請求項４】
前記第１メモリは、
三つの領域をもつ以前の探索領域メモリと、現在の処理領域メモリとに区分され、
前記計算部は、
前記現在の処理領域のデータが４x４ブロックサイズを有し、探索領域のサイズを−４〜＋４ピクセルに該当するとした時、
前記以前の探索領域のデータの所定データ単位と現在の処理領域のデータの各ライン別絶対差和を計算する第１絶対差和計算部と、第２絶対差和計算部と、第３絶対差和計算部と、第４絶対差和計算部とを具備し、
前記シフトレジスタ部は、
前記第１絶対差和計算部から出力された絶対差和データを９シフトさせて出力する第１の９シフトレジスタと、前記第１の９シフトレジスタの出力データに前記第２絶対差和計算部の出力データを加える第１加算器と、前記第２絶対差和計算部から出力された絶対差和データを９シフトさせて出力する第２の９シフトレジスタと、前記第２の９シフトレジスタの出力データに前記第３絶対差和計算部の出力データを加える第２加算器と、第３計算部から出力された絶対差和データを９シフトさせて出力する第３の９シフトレジスタと、前記第３の９シフトレジスタの出力データに前記第４絶対差和計算部の出力データを加える第３加算器と、を具備することを特徴とする請求項１に記載の動き推定器。
【請求項５】
前記第１絶対差和計算部は、複数のレジスタＣＲ０、ＣＲ１、ＣＲ２、ＣＲ３と、一方の入力端は前記レジスタＣＲ０、ＣＲ１、ＣＲ２、ＣＲ３の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備し、前記第２絶対差和計算部は複数のレジスタＣＲ４、ＣＲ５、ＣＲ６、ＣＲ７と、一方の入力端は前記レジスタＣＲ４、ＣＲ５、ＣＲ６、ＣＲ７の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備し、前記第３絶対差和計算部は複数のレジスタＣＲ８、ＣＲ９、ＣＲ１０、ＣＲ１１と、一方の入力端は前記レジスタＣＲ８、ＣＲ９、ＣＲ１０、ＣＲ１１の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備し、前記第４絶対差和計算部は複数のレジスタＣＲ１２、ＣＲ１３、ＣＲ１４、ＣＲ１５と、一方の入力端は前記レジスタＣＲ１２、ＣＲ１３、ＣＲ１４、ＣＲ１５の出力端に接続され、他方の入力端はスイッチに接続された減算器(ＳＵＢ)を具備することを特徴とする請求項４に記載の動き推定器。
【請求項６】
以前の探索領域のデータを半画素単位で補間して補間されたデータを前記計算部に出力する補間部をさらに含むことを特徴とする請求項１に記載の動き推定器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は動き推定器に係り、より詳細には、動映像の圧縮中に用いられる動き推定を高速で行える動き推定器に関する。
【０００２】
【従来の技術】
動き推定は、ビデオコーダにおいて、入力されるビデオデータの時間的な重複を除去して圧縮効率を高めるために用いられる。ほとんどの一般の動映像圧縮標準はブロック基盤のコーダであり、このようなブロック基盤のコーダではブロック整合アルゴリズムが用いられる。ブロック整合アルゴリズムとは、ブロック単位で動き推定を行うアルゴリズムを言う。ブロック整合アルゴリズムによれば、以前のフレームの探索領域内に位置する候補ブロックのうち現在のフレームのブロックと最も類似したブロックを探す。このとき、得られる現在のフレームの処理ブロックと以前のフレームの最も類似した候補ブロックとの相対的な位置の差は動きベクトル（ＭＶ）と呼ばれる。動き推定のためには、ＳＡＤ（Ｓｕｍ ｏｆ Ａｂｓｏｌｕｔｅ Ｄｉｆｆｅｒｅｎｃｅｓ）値を計算することが一般的である。１６×１６ブロックを単位として動き推定を行う場合、ＳＡＤ値及び動きベクトル（ＭＶ）は各々、
【数１】
0003863376.tif 000002
【数２】
0003863376.tif 000003
のように計算される。ここで、C(i,j)は現在のフレームのブロックデータであり、P(i+u,j+v)は以前のフレームの候補ブロックのデータであり、(u,v)は動きベクトル候補である。
【０００３】
このような計算に基づいて実際に動き推定器を設計するときには、動き推定の性能及び演算量を考慮しなければならない。動き推定において、演算量のほとんどはＳＡＤ値を計算することである。つまり、一つのＳＡＤ値を計算するためには引き算、絶対値、及び累積演算を行う必要があり、特に、このような計算量は処理ブロックの大きさに比例する。したがって、従来の動き推定方法によれば、演算量が多いため、動き推定に長時間がかかるという問題点がある。
【０００４】
前記問題点を解決するために、従来の他の動き推定方法として、階層的な動き推定方法が提案されている。図１は、前記階層的な動き推定方法を説明するための図である。図１に示された階層的な動き推定方法によれば、下位階層のイメージをサブサンプリングすることにより中間階層、及び上位階層のサブサンプリングされたイメージを生成する。次に、サブサンプリングされた上位階層のイメージに対してＳＡＤ値を計算することにより中間階層のイメージに対する初期探索領域の候補を選択し、周辺のマクロブロックとの相関関係を用いて探索領域の候補をさらに選択する。そして、選択された初期探索領域の候補に対してＳＡＤ値を計算することにより、下位階層のイメージに対するそのＳＡＤ値が最小となる地点の最終的な動きベクトル（ＭＶ）を求める。
【０００５】
このような方法は、全域にわたっての探索方法に比べて性能の低下は極めて小さく、しかも処理速度は速い。しかし、動き推定をより高速で行えるような方法への要求は依然として存在する。
【０００６】
【発明が解決しようとする課題】
本発明は上記事情に鑑みて成されたものであり、その目的は、動き推定を高速で行える動き推定器を提供するところにある。
【０００７】
【課題を解決するための手段】
前記目的を達成するために、本発明による動き推定器は、映像データフレームを圧縮するために動き推定を行う動き推定器において、以前の探索領域のデータをライン別に貯蔵する複数個のメモリ領域を具備する以前の探索領域メモリと、現在の処理領域のデータをライン別に貯蔵する現在の処理領域メモリを具備する第１メモリ部と、複数個のメモリ領域から循環的に出力される以前の探索領域のデータをシフトさせて出力する以前の探索領域データ供給部と、以前の探索領域データ供給部から出力された以前の探索領域のデータを選択する第１スイッチング部と、現在の処理領域メモリから出力される現在の処理領域のデータを行別に選択する第２スイッチング部と、選択された以前の処理領域のデータと現在の処理領域データとの絶対差和（ＳＡＤ）を計算する複数個のＳＡＤ計算部が並列で接続された計算部と、計算部の一段のＳＡＤ計算部から出力されたＳＡＤデータを入力してシフトを行い、シフトされたデータと次段のＳＡＤ計算部から出力されたＳＡＤ値を和して部分ＳＡＤ値を出力するシフトレジスタ部と、を含むことを特徴とする。
【０００８】
さらに、好ましくは、前記計算部は、探索領域の大きさをｐとしたとき、ｐ個のＳＡＤ計算部が並列で接続され、前記シフトレジスタ部は２ｐ＋１個のシフトレジスタを具備する。
【０００９】
さらに、好ましくは、前記動き推定器は、入力データをバッファリングするバッファと、バッファから出力されたデータを２５シフトする２５シフトレジスタと、部分ＳＡＤ値に２５シフトレジスタから出力されたデータを加えてＳＡＤ値を出力する加算器と、加算器から出力されたＳＡＤ値に基づき動きベクトルを生成するＳＡＤ比較及び動きベクトル生成部と、動きベクトル値を２０シフトさせてＳＡＤ比較及び動きベクトル生成部に出力する２０シフトレジスタと、をさらに含む。
【００１０】
さらに、好ましくは、前記動き推定器は、３階層で階層的動き推定を行うとき、中間階層で周辺マクロブロックがもつ動きベクトルの相関関係を用いて初期探索点をさらに得るために２２シフト動作を行う２２シフトレジスタをさらに含む。
【００１１】
さらに、好ましくは、前記動き推定器は、動き推定を行うために現在のデータ及び以前の探索領域データを区分して第１メモリに貯蔵されるように制御し、動き推定制御部の処理状況に応じて部分ＳＡＤ計算部にデータを供給するように制御するＤＭＡ制御部と、ＤＭＡ制御部から出力された制御信号に応答して動き推定動作を制御する動き推定制御部と、計算された部分ＳＡＤ値を貯蔵する第２メモリ部と、をさらに含む。
【００１２】
さらに、好ましくは、前記第１メモリは、三つの領域をもつ以前の探索領域メモリと現在の処理領域メモリとに区分され、前記計算部は、以前の探索領域のデータ及び現在の処理領域のデータに基づきＳＡＤを計算する第１のＳＡＤ計算部、第２のＳＡＤ計算部、第３のＳＡＤ計算部及び第４のＳＡＤ計算部を具備し、前記シフトレジスタ部は、前記第１ＳＡＤ計算部から出力されたＳＡＤデータを９シフトさせて出力する第１の９シフトレジスタと、前記第１の９シフトレジスタの出力データに前記第２のＳＡＤ計算部の出力データを加える第１加算器と、前記第２のＳＡＤ計算部から出力されたＳＡＤデータを９シフトさせて出力する第２の９シフトレジスタと、前記第２の９シフトレジスタの出力データに前記第３のＳＡＤ計算部の出力データを加える第２加算器と、第３計算部から出力されたＳＡＤデータを９シフトさせて出力する第３の９シフトレジスタと、前記第３の９シフトレジスタの出力データに前記第４のＳＡＤ計算部の出力データを加える第３加算器と、を具備する。
【００１３】
さらに、好ましくは、前記第１のＳＡＤ計算部は、複数のレジスタＣＲ０、ＣＲ１、ＣＲ２、ＣＲ３と、一方の入力端は前記レジスタＣＲ０、ＣＲ１、ＣＲ２、ＣＲ３の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備し、前記第２のＳＡＤ計算部は複数のレジスタＣＲ４、ＣＲ５、ＣＲ６、ＣＲ７と、一方の入力端は前記レジスタＣＲ４、ＣＲ５、ＣＲ６、ＣＲ７の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備し、前記第３のＳＡＤ計算部は複数のレジスタＣＲ８、ＣＲ９、ＣＲ１０、ＣＲ１１と、一方の入力端は前記レジスタＣＲ８、ＣＲ９、ＣＲ１０、ＣＲ１１の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備し、前記第４のＳＡＤ計算部は複数のレジスタＣＲ１２、ＣＲ１３、ＣＲ１４、ＣＲ１５と、一方の入力端は前記レジスタＣＲ１２、ＣＲ１３、ＣＲ１４、ＣＲ１５の出力端に接続され、他方の入力端はスイッチに接続された減算器（ＳＵＢ）を具備する。
【００１４】
さらに、好ましくは、前記動き推定器は、以前の探索領域のデータを補間して補間されたデータを出力する補間部をさらに含む。
【００１５】
さらに、好ましくは、前記動き推定器は、以前の探索領域に該当するデータと現在の処理ブロックに該当するデータとを区分する動作を行い、処理状況によって前記以前の探索領域データ供給部及び前記計算部にデータを供給するように制御するＤＭＡ制御部をさらに含む。
【００１６】
【発明の実施の形態】
以下、添付した図面に基づき、本発明の望ましい実施形態について詳細に説明する。
【００１７】
図２は、本発明の実施形態による動き推定器の構造を示したブロック図である。この実施形態の動き推定器は、３階層の階層的な動き推定方法に基づく。下位階層では１６×１６ブロック、中間階層では８×８ブロック、及び上位階層では４×４ブロックに対してＳＡＤ計算が行われる。つまり、中間階層は下位階層を１／２だけデシメ―ションした階層であり、上位階層は中間階層を１／２だけデシメ―ションした階層である。さらに、上位階層では±４画素単位の探索が行われ、中間階層及び下位階層では±２画素単位の探索が行われる。また、この実施形態の動き推定器は、下位階層の正画素単位の推定が完了した後に、前記下位階層に対して半画素単位の推定を行う。また、この実施形態では、例えば、本出願人により出願され、かつ本明細書に参照として引用された韓国特許出願第９８-６７１８号に開示された、改善された動き推定方法を用いる。前記特許出願に開示された動き推定方法によれば、中間階層で選択されたマクロブロック候補に加えて、下位階層で周辺マクロブロックとの相関関係に基づき少なくとも１つ以上のマクロブロック候補をさらに選択する。
【００１８】
図２を参照すると、本発明の実施形態による動き推定器は、第１メモリ２００、部分ＳＡＤ計算部２１０、補間部２１２、加算器２２０、及びバッファ２２２を具備する。また、前記動き推定器は、２５シフトレジスタ２３０、ＳＡＤ比較及び動きベクトル生成部２４０、２２シフトレジスタ２５０、ＤＭＡ制御部２６０、動き推定制御部２７０、及び第２メモリ２８０を具備する。第１メモリは、以前の探索領域メモリ２０２と現在の処理領域メモリ２０４とに分けられる。
【００１９】
これらの動作について述べると、ＤＭＡ制御部２６０は、動き推定を行うために現在のデータと以前の探索領域データとを区分してこれらが第１メモリ２００に貯蔵されるように制御する。また、ＤＭＡ制御部２６０は、動き推定制御部２７０の処理状況によって部分ＳＡＤ計算部２１０にデータを供給するように制御する。
【００２０】
部分ＳＡＤ計算部２１０は、現在の処理ブロックデータ及び以前の探索領域データを入力して部分ＳＡＤ値を計算する。また、前記動き推定器は２２シフトレジスタ２５０を具備することにより、３階層で階層的な動き推定を行うとき、中間階層で周辺マクロブロックがもつ動きベクトルの相関関係に基づき初期の探索点を得る。
【００２１】
図３Ａは、図２の動き推定器の第１メモリ２００、部分ＳＡＤ計算部２１０、及び補間部２１２の詳細図である。これを参照すると、第１メモリ２００は、三つの領域をもつ以前の探索領域メモリ（以前の探索領域メモリ_Ａ、以前の探索領域メモリ_Ｂ、以前の探索領域メモリ_Ｃ）と、現在の処理領域メモリとに分けられる。また、部分ＳＡＤ計算部２１０は、以前の探索領域データ供給部３０、計算部３２、及びシフトレジスタ部３４を具備する。また、図３Ｂを参照すると、以前の探索領域データ供給部３０と計算部との間にはスイッチング部３８２、３８６が具備される。また、補間部２１２の出力端と計算部３２との間にはスイッチ３８４が具備される。また、現在の処理領域メモリの出力端と計算部３２との間にはスイッチング部３８８が具備される。この実施形態において、前記スイッチは制御信号Ｃｔｒｌ_Ａ、Ｃｔｒｌ_Ｂ、Ｃｔｒｌ_Ｃ、Ｃｔｒｌ_Ｄを出力するスイッチング制御部３６により制御され、前記スイッチング制御部３６は動き推定制御部２７０内に具備できる。
【００２２】
以前の探索領域データ供給部３０は、第１以前の探索領域データ供給部３０ａ、第２以前の探索領域データ供給部３０ｂ、及び第３以前の探索領域データ供給部３０ｃを具備する。計算部３２は、第１のＳＡＤ計算部３２２、第２のＳＡＤ計算部３２４、第３のＳＡＤ計算部３２６、及び第４のＳＡＤ計算部３２８を具備する。シフトレジスタ部３４は、第１の９シフトレジスタ３４０、第２の９シフトレジスタ３４４、第３の９シフトレジスタ３４８、及び複数の加算器３４２、３４６、３５０を具備する。
【００２３】
これらの動作について述べると、スイッチング部３８２は、制御信号Ｃｔｒｌ_Ａに応答して以前の探索領域データ供給部３０から出力された以前の探索領域のデータを選択する。また、スイッチ３８８は、制御信号Ｃｔｒｌ_Ｄに応答して現在の処理領域メモリから出力される現在の処理領域のデータを行別に選択する。部分ＳＡＤ計算部２１０は、以前の探索領域メモリ及び現在の処理領域メモリから以前の探索領域に該当するデータ及び現在の処理ブロックに該当するデータを入力して部分ＳＡＤ値を計算する。ＤＭＡ制御部２６０は、以前の探索領域に該当するデータ及び現在の処理ブロックに該当するデータを区分する動作を行う。部分ＳＡＤ計算部２１０は、４×４ブロックに対し−４〜＋４探索領域に限って演算できるので、この実施形態による動き推定器は加算器２２０、バッファ２２２、及び２５シフトレジスタ２３０を具備して４×４ブロックよりも大きいブロックに対してＳＡＤ値を得る。
【００２４】
部分ＳＡＤ計算部２１０は、以前の探索領域メモリ（以前の探索領域メモリ_Ａ、以前の探索領域メモリ_Ｂ、以前の探索領域メモリ_Ｃ）による三つのチャンネルと、現在の処理領域メモリによる一つのチャンネルを通じて各々以前の探索領域データ及び現在の処理領域データを入力される。
【００２５】
図４は、以前の探索領域のデータがメモリに配置される順序を示したものである。これを参照すると、以前の探索領域の第１ラインのデータは以前の探索領域メモリ_Ａ、第２ラインのデータは以前の探索領域メモリ_Ｂ、第３ラインのデータは以前の探索領域メモリ_Ｃから各々出力される。次に、以前の探索領域の第４ラインのデータは再び以前の探索領域メモリ_Ａから出力される。図４において、以前の探索領域メモリ_Ａから出力されるデータは○、以前の探索領域メモリ_Ｂから出力されるデータは◇、以前の探索領域メモリ_Ｃから出力されるデータは□で各々示されている。
【００２６】
また、部分ＳＡＤ計算部２１０には、現在の処理領域メモリから現在の処理領域データが入力される。図５は、４×４画素よりなる現在の処理領域のデータが図３Ａの計算部内のレジスタに配置される順序を示したものである。４×４画素よりなる現在の処理領域のデータは、図５に示されたように、図３ＡのレジスタＣＲ０，ＣＲ１，．．．，ＣＲ１５にロードされる。このように現在の処理領域データが各レジスタＣＲ０，ＣＲ１，．．．，ＣＲ１５に貯蔵中に、以前の探索領域のデータもレジスタＰＡＲ０，ＰＡＲ１，．．．，ＰＡＲ４，ＰＢＲ１，．．．，ＰＢＲ４，ＰＣＲ０，．．．，ＰＣＲ４にロードされる。
【００２７】
レジスタへのデータのロードが完了すると、部分ＳＡＤ計算部２１０の減算器（ＳＵＢ）は以前の探索領域データと現在の処理領域データとの差値を計算する。次に、絶対差計算部（図示せず）は、前記差値を入力して前記差値の絶対値を出力する。各絶対差計算部の出力は各画素に該当する演算値であり、これらの演算値は現在の処理領域データの水平成分同士で和される。これにより、以前の探索領域データが一度入力されるとき、現在の処理領域の各ラインに対し差の絶対値が計算される。
【００２８】
以降の説明のために、図４に示された以前の探索領域において、 最左上部のデータをP(0,0)、P(0,0)から右側に１画素分シフトした位置の画素データをP(0,1)、P(0,0)から右側に２画素分シフトした位置の画素データをP(0,2)と定義する。また、P(0,0)から下方に１画素分シフトした位置の画素データをP(1,0)、P(0,0)から下方に２画素分シフトした位置の画素データをP(2,0)と定義する。
【００２９】
これと同様に、 図５に示された現在の処理領域において、最左上部のデータをc(0,0)、c(0,0)から右側に１画素分シフトした位置の画素データをc(0,1)、c(0,0)から右側に２画素分シフトした位置の画素データをc(0,2)と定義する。また、c(0,0)から下方に１画素分シフトした位置の画素データをc(1,0)、c(0,0)から下方に２画素分シフトした位置の画素データをc(2,0)と定義する。
【００３０】
このように定義すると、レジスタＣＲ０にはc(0,0)データがロードされ、レジスタＣＲ１にはデータc(0,1)がロードされる。また、レジスタＣＲ４にはデータc(1,0)がロードされ、レジスタＣＲ５にはデータc(1,1)がロードされ、レジスタＣＲ１５にはデータc(3,3)がロードされる。
【００３１】
部分ＳＡＤ計算部２１０は、現在の処理領域内において１ラインずつに対して演算を行うため、第１計算部３２２、第２計算部３２４、第３計算部３２６、及び第４計算部３２８の加算器から出力される演算結果値L0(0,0)、L1(0,0)、L2(0,0)及びL3(0,0)は各々、
【数３】
0003863376.tif 000004
になる。演算結果値L0(0,0)、L1(0,0)、L2(0,0)及びL3(0,0)は現在の処理領域データの第１、第２、第３及び第４ラインに対する演算結果に該当する。iを行、jを列を表わす正の数としたとき、以前の探索領域データをP(i,j)で表わすと、以前の探索領域データP(i,j)及び現在の処理領域データの第１、第２、第３及び第４ラインに対する演算結果は各々L0(i,j)、L1(i,j)、L2(i,j)及びL3(i,j)となる。この表現によると、探索領域の最左上部に対するＳＡＤ値は、
【数４】
0003863376.tif 000005
のように表される。以前の探索領域データは部分ＳＡＤ計算部２１０に１ラインずつ入力されるので、前記数式４から得られるＳＡＤ値が最初に得られるＳＡＤ値となる。
【００３２】
L0(0,0)は第１ラインに対する演算によって得られる。しかし、L1(1,0)は以前の探索領域データの第２ラインが入力されてこそ得られ、L2(2,0)は第３ライン、そしてL3(3,0)は第４ラインが入力されてこそ得られる。つまり、L0(0,0)及びL1(1,0)は探索領域を-ｐ〜＋ｐとしたとき、２ｐ＋１に該当する時間差が発生する。したがって、L0(0,0)にL1(1,0)を加えるために２ｐ＋１クロック分の遅延が必要になる。この実施形態では、探索領域を-４〜＋４とするため９クロック分の遅延が必要になり、シフトレジスタ部３４の９シフトレジスタ３４０、３４４、３４８がこのような遅延動作を行う。図３Ａを戻って詳細に述べると、第１の９シフトレジスタ３４０は第１のＳＡＤ計算部３２２から出力されたＳＡＤデータを９シフトさせて出力する。第１加算器３４２は、第１の９シフトレジスタ３４０の出力データに第２のＳＡＤ計算部３２４の出力データを加える。第２の９シフトレジスタ３４４は、第２のＳＡＤ計算部３２４から出力されたＳＡＤデータを９シフトさせて出力する。第２加算器３４６は、第２の９シフトレジスタ３４４の出力データに第３のＳＡＤ計算部３２６の出力データを加える。第３の９シフトレジスタ３４８は、第３のＳＡＤ計算部３２６から出力されたＳＡＤデータを９シフトさせて出力する。第３加算器３５０は、第３の９シフトレジスタ３４８の出力データに第４のＳＡＤ計算部３２８の出力データを加える。第３加算器３５０から出力されたデータは、与えられた探索領域に対する部分ＳＡＤ値である。
【００３３】
図６を参照すると、この実施形態による動き推定器では、L0(0,0)にL1(1,0)を加えるために９クロック分の遅延が必要になる。また、この実施形態による動き推定器では、第１ラインをレジスタ部３４にロードするのに必要な９クロック分の処理遅延を除いた他の処理遅延は発生しない。つまり、斜線部分のL0(0,0)、L1(1,0)、L2(2,0)及びL3(3,0)がクロック毎に順次得られ、次に、網がけ部分のL0(0,1)、L1(1,1)、L2(2,1)及びL3(3,1)がクロック毎に順次得られる。したがって、４×４画素の探索領域の各々のＳＡＤ値を全域探索により求めるのに必要な総時間は、初期のデータロード時間を除いたとき、９×１２クロック、つまり１０８クロックとなる。
【００３４】
また、本発明による動き推定器は、正画素単位の探索を完了すると、正画素探索を通じて得た動きベクトル地点を基準として半画素単位の探索を行う。
【００３５】
補間部２１２は、３個の以前の探索領域メモリ（以前の探索領域メモリ_Ａ、以前の探索領域メモリ_Ｂ、以前の探索領域メモリ_Ｃ）からデータを受け入れる。
【００３６】
以下、図７を参照し、本発明の実施形態による動き推定器で適用される半画素単位の探索過程について述べる。半画素単位の探索を行うためには、探索点を決める必要がある。半画素単位の探索点を各々alpha(i,j)、beta(i,j)及びgamma(i,j)としたとき、これらの探索点は各々、
【数５】
0003863376.tif 000006
【００３７】
のように定義される。例えば、alpha(0,0)に該当する探索点は７０、beta(0,1)に該当する探索点は７２、gamma(1,0)に該当する探索点は７４と参照される。また、alpha(0,4)に該当する探索点は７６、gamma(1,4)に該当する探索点は７８と参照される。
【００３８】
図８は、前記動き推定器の補間部２１２の一例を参考として示したものである。これを参照すると、例えば、補間部２１２は、レジスタＰＡＲ０、ＰＢＲ０、ＰＣＲ０、またはレジスタＰＡＲ１、ＰＢＲ１、ＰＣＲ１、レジスタＰＡＲ２、ＰＢＲ２、ＰＣＲ２、レジスタＰＡＲ３、ＰＢＲ３、ＰＣＲ３、及びレジスタＰＡＲ４、ＰＢＲ４、ＰＣＲ４のうち各々両レジスタから以前の探索領域データを選択して入力し、前記数式５ａ、５ｂ及び５ｃに示された等式に従い補間を行うことにより、alpha、beta及びgamma画素値を求め、出力端子に順次出力する。
【００３９】
これにより、補間部２１２は、最上位ビット（ＭＳＢ）及び最下位ビット（ＬＳＢ）を含んで４ビットの補間されたデータを出力する。スイッチ３８４は、制御信号Ｃｔｒｌ_Ｂに応答して補間部２１２の出力端子のいずれか一方の端子に順次切り換えられることにより計算部３２の入力データの選択を行う。また、スイッチング部３８６は、制御信号Ｃｔｒｌ_Ｃに応答して補間されたデータを選択して計算部３２に入力する。これにより、計算部３２及びシフトレジスタ部３４によって補間されたデータに対する部分ＳＡＤ値が得られる。
【００４０】
すなわち、本発明による動き推定器は、以前のフレーム領域のデータを一度読み出すことにより、alpha、beta及びgammaに該当する探索点の画素値を同時に生成できる。その結果、本発明による動き推定器は従来の技術のそれに比べて処理速度が速い。
【００４１】
また、ある４×４領域に対する動き推定が完了してから、次の４×４領域で動き推定をする場合、alpha(0,4)に該当する探索点７６、beta(1,4)に該当する探索点７８の画素値は、すでに読み出していた以前の探索領域のデータをシフトして書き込むことにより得られる。したがって、本発明による動き推定器は、特に半画素単位の探索を高速で、しかも効率良く行える。
【００４２】
図９は、図２の示された動き推定器に半画素単位の探索を適用した場合のデータ流れを示したものである。これを参照すると、前記動き推定器では、一つの４×４ブロックに対する半画素単位の探索が２４クロック中に完了する。
【００４３】
一方、本実施形態による動き推定器に具備された部分ＳＡＤ計算部２１０の処理単位は４×４ブロックである。このような動き推定器を３階層の階層的探索に用いるとき、上位階層の場合には４×４ブロック内で-４〜＋４画素の探索領域に対して全域探索を行い、中間階層の場合には８×８ブロック内で-２〜+２画素の探索領域に対して探索を行い、下位階層の場合には１６×１６ブロック内で-２〜+２画素の探索領域に対して探索を行う。
【００４４】
本実施形態による動き推定器の部分ＳＡＤ計算部２１０は、４×４ブロックを計算できる。したがって、８×８ブロックの中間階層及び１６×１６ブロックの下位階層に対して動き推定を行うためには、階層を各々４個及び１６個のブロックらに分けて計算した後に、結果値を加え合わせることが必要である。しかし、中間階層及び下位階層では探索領域が、図１０に示されたように、-２〜+２画素に該当するので、探索を一回行うと、２５ポイントに対する部分ＳＡＤ値を求めることができる。このために、図２を参照すると、本発明による動き推定器は、２５シフトレジスタ２３０を具備する。前記動き推定器は部分ＳＡＤ値を２５シフトレジスタ２３０に入力させ、次の部分ＳＡＤ値が出力されるとき毎に２５シフトレジスタ２３０に貯蔵されたデータをシフトさせて次の４×４ブロックの部分ＳＡＤ値に加えることにより、中間階層及び下位階層の探索作業を行える。
【００４５】
一方、この実施形態による動き推定器は、３個の初期探索点のうちいずれか一つを周辺マクロブロックとの相関関係に基づき選択する。周辺マクロブロックの位置は、図１１のように定めることができる。入力映像フレームの左上部の左方から水平方向に動きベクトルを求めるため、現在の処理ブロックとこの上に位置したマクロブロックとの距離は、入力映像フレームの水平方向のマクロブロック数に等しい。したがって、入力映像フレームが３５２×２８８画素のＣＩＦ形式のものであるとしたとき、入力映像フレームの最大のサイズは水平方向に２２個のマクロブロックに該当する。したがって、本発明の他の実施形態によれば、動き推定器は、２２シフトレジスタアレイ１１００及び中間値計算部１１０２をさらに具備する。２２シフトレジスタアレイ１１００は周辺マクロブロックに対する動きベクトル値を入力し、中間値計算部１１０２はこれらの中間値を動きベクトル候補として出力することにより、周辺マクロブロックとの相関関係に基づき動きベクトル候補をさらに選択する。選択された動きベクトル候補は、中間階層の初期探索点として用いられる。
【００４６】
本発明の実施形態による動き推定器に適用される３階層の階層的探索において、上位階層データは元のデータを４：１デシメ―ションした値よりなる。この実施形態において、デシメ―ションに際しては、元のデータを４サンプルおきに一つずつ取る方法を用いる。現在の処理領域のデータは一つの現在の処理領域メモリに貯蔵されているため、水平及び垂直方向に４サンプルおきに一つずつ取る。以前の探索領域のデータは三つの以前の探索領域メモリに分かれて貯蔵されているため、水平方向のデシメ―ションは現在の処理領域のデータの場合と同様に、４サンプルおきに一つずつ取るが、垂直方向のデシメ―ションは図１２のように行われる。すなわち、この実施形態によれば、以前の探索領域メモリは、探索領域データの第１ラインが以前の探索領域メモリ_Ａに、第２ラインが以前の探索領域メモリ_Ｂに、第３ラインが以前の探索領域メモリ_Ｃに、のように貯蔵されているため、図２のＤＭＡ制御部２６０はアドレスを４ずつインクリメントし、以前の探索領域メモリ_Ａ、以前の探索領域メモリ_Ｂ、及び以前の探索領域メモリ_Ｃの順番に読み出すように制御することが要される。
【００４７】
メモリから読み出したデータは部分ＳＡＤ計算部２１０の各レジスタに貯蔵され、-４〜+４ブロックの探索領域に対して全域探索を行うことにより、最小のＳＡＤ値をもつ両位置を中間階層の初期探索点として選択する。上位階層でのデータ処理の流れは、図１３に示されている。図１３は基本的に図６と同一であるため、これ以上の説明はしない。
【００４８】
中間階層のデータは下位階層のデータを２：１デシメ―ションすることにより得られる。したがって、現在の処理領域メモリ及び以前の探索領域メモリから水平及び垂直方向にアドレスを２ずつインクリメントすることにより、図１４に示されたように、メモリの読み出し及びスキップを行う。以前の探索領域データは３つのメモリに分かれて貯蔵されているため、垂直方向には以前の探索領域メモリ_Ａ、以前の探索領域メモリ_Ｂ、以前の探索領域メモリ_Ｃの順番でデータを読み出す。これにより、以前の探索領域のデータに対する垂直方向への２：１デシメ―ションがなされる。
【００４９】
中間階層では、上位階層で探した２個の初期探索点と、２２シフトレジスタ２５０で得られる動きベクトル候補に該当する一つの初期探索点を中心点として決定される８×８ブロックに対して-２〜＋２探索領域の全域探索を行い、これにより部分ＳＡＤ値を求める。部分ＳＡＤ計算部２１０は、４×４ブロック単位に探索を行うように設計されているため、８×８ブロックの中間階層に対して探索を行うためには、図１５に示されたように、現在のフレームの８×８ブロックを４個の４×４ブロックに分けて探索を行う。すなわち、最初の４×４ブロックに対して-２〜＋２探索領域にわたって２５ポイントの部分ＳＡＤ値を求め、前記部分ＳＡＤ値を２５シフトレジスタ２３０に貯蔵する。それから、加算器２２０により、前記部分ＳＡＤ値に次の４×４ブロックに対する部分ＳＡＤ値を加える。このような過程を４回繰り返すことにより、８×８ブロックに対するＳＡＤ値を求める。このように３個の初期探索点に対する-２〜＋２探索領域によって最小のＳＡＤ値をもつ位置を下位階層の初期探索点として用いる。中間階層でのデータ処理の流れは、図１６に示されている。これを参照すると、中間階層では、L0(0,0)にL1(1,0)を加えるために５クロックの遅延が必要である。すなわち、斜線部分のL0(0,0)、L1(1,0)、L2(2,0)及びL3(3,0)がクロック毎に順次求められ、次に網がけ部分のL0(0,1)、L1(1,1)、L2(2,1)及びL3(3,1)がクロック毎に順次求められる。
【００５０】
下位階層のデータは、元のデータよりなる。中間階層で探した初期探索点を中心点として１６×１６ブロックに対して-２〜＋２探索領域にわたって全域探索を行い、最小のＳＡＤ値をもつ位置を求める。前記位置から、正画素単位の探索による最終的な動きベクトルが求められる。下位階層に対する動き推定は、図１７に示されたように、１６×１６ブロックに対して行われ、部分ＳＡＤ計算部２１０は４×４ブロックを基準として処理を行うため、４×４ブロック単位の探索を１６回繰り返すことにより１６×１６ブロックに対するＳＡＤ値を求める。下位階層でのデータ処理の流れは、図１８に示されている。図１８に示された下位階層でのデータ処理の流れは、±２画素の探索を行う中間階層でのデータ流れを示した図１６と同一であるため、これ以上の説明は省く。
【００５１】
【発明の効果】
以上述べたように、本発明による動き推定器は処理速度が速く、特に半画素単位の探索を高速で、しかも効率良く行える。
【図面の簡単な説明】
【図１】  従来の階層的動き推定方法を説明するための図である。
【図２】  本発明の実施形態による動き推定器の構造を示したブロック図である。
【図３】  図３Ａは、図２の動き推定器の第１メモリ、部分ＳＡＤ計算部、及び補間部の詳細図であり、図３Ｂは、図２の動き推定器のスイッチ及びスイッチング制御部の詳細図である。
【図４】  以前の探索領域のデータがメモリに配置される順序を説明するための図である。
【図５】  ４×４画素よりなる現在の処理ブロックのデータが図３Ａの計算部内のレジスタに配置される順序を示した図である。
【図６】  図２の動き推定器でのデータ流れを説明するための図である。
【図７】  本発明による動き推定器で適用される半画素単位の探索過程を説明するための図である。
【図８】  図２に示された動き推定器の補間部の一例を示したブロック図である。
【図９】  図２の本発明による動き推定器で半画素単位の探索を適用した場合の動き推定器でのデータ流れを説明するための図である。
【図１０】  本発明の実施形態による動き推定器で適用される階層的探索に用いられた中間階層及び下位階層での探索領域を説明するための図である。
【図１１】  図２に示された動き推定器において、周辺マクロブロックの相関関係に基づき 初期探索点を一つさらに選択するための２２シフトレジスタの構成例を示した図である。
【図１２】  以前の探索領域のデータを垂直方向に４：１デシメ―ションする過程を説明するための図である。
【図１３】  上位階層でのデータ処理の流れを説明するための図である。
【図１４】  以前の探索領域のデータを垂直方向に２：１デシメ―ションする過程を説明するための図である。
【図１５】  中間階層でのデータ処理を説明するための図である。
【図１６】  中間階層でのデータ処理の流れを説明するための図である。
【図１７】  下位階層でのデータ処理を説明するための図である。
【図１８】  下位階層でのデータ処理の流れを説明するための図である。
【符号の説明】
３０，３０ａ，３０ｂ，３０ｃ  以前の探索領域データ供給部
３２  計算部
３４  シフトレジスタ部
３６  スイッチング制御部
２００  第１メモリ
２０２  以前の探索領域メモリ
２０４  現在の処理領域メモリ
２１０  部分ＳＡＤ計算部
２１２  補間部
２２０  加算器
２２２  バッファ
２３０  ２５シフトレジスタ
２４０  ＳＡＤ比較及び動きベクトル生成部
２５０  ２２シフトレジスタ
２６０  ＤＭＡ制御部
２７０  動き推定制御部
２８０  第２メモリ
３２２，３２４，３２６，３２８  ＳＡＤ計算部
３４０，３４４，３４８  ９シフトレジスタ
３４２，３４６，３５０  加算器
３８２，３８６  スイッチング部
３８４  スイッチ
３８８  スイッチング部
１１００  ２２シフトレジスタアレイ
１１０２  中間値計算部
【図１】
0003863376.tif 000007
【図２】
0003863376.tif 000008
【図３】
0003863376.tif 000009
0003863376.tif 000010
【図４】
0003863376.tif 000011
【図５】
0003863376.tif 000012
【図６】
0003863376.tif 000013
【図７】
0003863376.tif 000014
【図８】
0003863376.tif 000015
【図９】
0003863376.tif 000016
【図１０】
0003863376.tif 000017
【図１１】
0003863376.tif 000018
【図１２】
0003863376.tif 000019
【図１３】
0003863376.tif 000020
【図１４】
0003863376.tif 000021
【図１５】
0003863376.tif 000022
【図１６】
0003863376.tif 000023
【図１７】
0003863376.tif 000024
【図１８】
0003863376.tif 000025