(57)【要約】【課題】計算量の減少方法を提供する。【解決手段】本方法は、極小部分のハードディスクを変更し、ビデオ圧縮方法に少しの修正を加えるだけで、周波数領域中で、動き推定を実行する。肉眼は、高周波数領域では、低周波数領域ほど敏悦ではないので、本発明は、低周波数データだけを取って、動き推定のモーションベクトルを探し出す。【選択図】図７
2006261950.tif 000002
【特許請求の範囲】
【請求項１】
周波数領域中のブロックマッチングの動き推定方法であって、
動き推定が、二枚のデジタルアニメーションフレームの相同画像間の動き関係を定義する工程と、
ビデオ圧縮が、DCT（Discrere  Cosine  Transfer）プロセスを使用し、画像入力を、時間領域から周波数領域のデータに転換する工程と、
その後、前記データを直流、低周波数、高周波数の順に排列する工程と、
量化を応用し、前記データ中の高周波余剰を減少する工程と、
からなり、
前記方法は、前記量化の後、前記動き推定が前記二つのデジタルアニメーションフレームの前記データに応用され、計算量の減少を達成することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き推定（motion  estimation）のブロックマッチング（block  matching）時に、低周波数情報を使用して、モーションベクトル（motion  vector）を生成する方法に関するものであって、ブロックマッチング処理は低周波数だけに応用され、全周波数幅に採用されないので、デジタル動画計算の複雑性を減少させる方法に関するものである。
【背景技術】
【０００２】
一般のコンピュータ、テレビ、携帯電話等のスクリーン上のデジタルアニメーション処理は、メモリ空間、或いは、伝送帯域幅を減少させるため、デジタルアニメーション圧縮技術を使用する。現在、デジタルアニメーション圧縮技術において、最もよく使用される規格は、MPEG−２、MPEG−４、AVS、H．２６４で、これらの規格は、どれも、“動き推定”の方法を使用し、時間領域中、前後データの関連性を照合し、そのデータ量を圧縮する。一般に、連続したアニメーションは、画面が流れるように動くために、毎秒、２０〜３０枚の画面が必要で、連続した二枚の画面中、相同のイメージは、動き推定を使用して、その移動関係を決定する。
動き推定の方法は、フレームを、１６×１６の２５６画素マトリクスを、一つのマクロブロック（Macro−Block、MB）に分割し、その後、各MBに、前の画面と相関する最適なモーションベクトルを探し出す。図１を参照すると、フレーム（ａ）とフレーム（ｂ）は、二枚の連続した画面である。しかし、フレーム（ｂ）を伝送（或いは、保存）する時、列車のモーションベクトル（点線の矢印で示される）だけが伝送され、その後フレーム（ａ）中の列車が遮蓋された背景を加え、元の列車と背景データを配合することにより、フレーム（ｂ）を生成する。この方法は、伝送帯域幅（或いは、メモリの容量）を減少させることができるが、計算の複雑性を増加させる。
フレーム（ａ）のMBのモーションベクトルを計算する時、フレーム（ｂ）のあるMBの対応画素により、フレーム（ａ）のMB中の各画素を減らすことが必要で、その後、２５６個の絶対差異値を加えて、「差分絶対値の総和」（SAD）を得る。この場合、多くのSADは、フレーム（ｂ）の全MBを計算する時生成され、最小のSADに対応する比較点の位置の差異が、ターゲットポイントである。フレーム（ａ）の比較点に関連するターゲットポイントの位置の差異は、
“モーションベクトル”と称される。計算量を減少させるため、通常は、小さいサーチ範囲（Searching  Range）を設定し、このサーチ範囲中、で見つかったSADが所定の設定値より小さい場合、この比較点位置の差異が、モーションベクトルである。
図２を参照すると、全サーチ方法の動き推定と、サーチ範囲３２×３２画素に基づいて、MBの大きさは１６×１６で、あるMBのモーションベクトルを見つけたい場合、あるMBとその他の全MBを運算しなければならず、これにより、１７×１７＝２８９回のMBの比較を有する（MBは、サーチ範囲内１７×１７の範囲で移動する）。各比較は、最小の差分絶対値の総和MADの運算方法に基づいて処理される。MB画素値は、他のMBの対応する画素値により引かれ、その後、絶対値を得て、累加し、全部で７６７回の運算を必要とする（２５６回減少、絶対値を２５６回得る、２５５回累加する、２５６＋２５６＋２５５＝７６７）。全部で２８９回の比較を有するので、それぞれ、７６７回の運算を必要とし、２８９×７６７＝２２１６６３回の運算で、一個のMBのモーションベクトルの検索が完成する。
一枚のフレームは７２０×４８０のフレームを有し、フレームは、１３５０個のMBに分割できる。この場合、約２．９９×１０８回（１３５０×２２１６６３）の演算で、このフレームのモーションベクトルの計算を完成する。一般の連続アニメーションは、毎秒、少なくとも２２枚のフレームを必要とするので、毎秒の総運算量は、約６．５８×１０９回（２２×２．２９×１０８）である。
上述から、動き推定は、非常に大きい演算処理力を必要とする。このシステムは、高システムクロックと大DSPを装備しなければならず、電力消耗が多くなるにつれて、ポータブル電子用品のバッテリーはロードをサポートすることが出来ず、コストが増加する。よって、多くの新しいソリューションが発展し、二つのカテゴリに分割される。まず、比較点の数を減少させ、次に、演算を減少させる。共に、同時に応用でき、計算量を最小にまで減少することができる。
比較点を減少させるため、多くのソリューションが用いられ、“三ステップサーチTSS”“四ステップサーチFSS”等がよく用いられ、現在のサーチ範囲で、幾つかの点を探し、最小MAD値を求め、その後、最小MAD値付近で、領域化運算を実行する。
演算を減少するのに用いられるソリューションは少なく、常用されるのは：
SUM（ABS（ａ−ｂ））>＝ABS（SUM（ａ）−SUM（ｂ））
ａ、ｂはそれぞれ、二つのMBの各点の画素値を示す。この不等式の意義は、二つのMBが対応する画素差分絶対値の総和（前述のMAD運算）は、二つのMBの各画素値の和の差分絶対値より大きいか、或いは、等しい（近似計算と称される）。
上述の全ての方法は、時間領域（timing  domain）に適用される。しかし、時間領域を周波数領域に転換した後、我々は、ブロックマッチングアルゴリズムは、更に改善できることを発見した。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、計算量を減少させる方法を提供し、極小部分のハードディスクを変更し、ビデオ圧縮方法に少しの修正を加えるだけで、周波数領域中で、動き推定を実行することを目的とする。
【課題を解決するための手段】
【０００４】
肉眼は、高周波数領域では、低周波数領域ほど敏悦ではないので、本発明は、低周波数データだけを取って、動き推定のモーションベクトルを探し出す。
動き推定は、二枚のデジタルアニメーションフレームの相同画像間で、動き関係を定義する。ビデオ圧縮はDCTを用いて、イメージを、時間領域から周波数領域のデータに転換し、データを、直流、低周波数、高周波数の順に排列する。量化ブロックを使用し、データ中の高周波数余剰部分を減少させる。
【発明の効果】
【０００５】
本発明の方法は、量化方法の後、動き推定を二枚のデジタルアニメーションフレームの周波数領域のデータに応用して、計算量を減少させる。
【発明を実施するための最良の形態】
【０００６】
現在、大部分のビデオ標準は、異なるアルゴリズムを使用し、データを圧縮する。人間の目の高周波数領域に対する敏感度は、低周波数領域の敏感度ほどではないので、大部分のビデオ圧縮標準は、離散コサイン転換DCT（Discrere  Cosine  Transfer）プロセスを使用し、画像入力を、時間領域から周波数領域のデータに転換する。その後、データを直流、低周波数、高周波数の順に排列する。量化を応用し、高周波余剰を減少する。可変長符号化VCL（Variable  Length  Coding）を使用し、コード空間中の余剰を減少する。反圧縮、反DCT（inverse  DCT）と反VLCを経たデータは、最後に、時間領域中で、動き推定を用いて、前後二枚のピクチャ間の重複部分を減少し、これについては、図３を参照する。
【０００７】
図４と図５を参照すると、ビデオ圧縮はDCTを用いて、サンプルピクチャのイメージを、時間領域（図４）から周波数領域（図５）に転換し、データを、直流、低周波数、高周波数の順に、鋸歯状（或いは、その他の形状）に排列する（図６）。その後、量化ブロック（図３中のQ）を使用し、人類が不敏感である高周波数情報を圧縮する。最後に、VLCを使用し、コード空間でデータを圧縮し、バッファ（図３）によりイメージコードを出力する。
【０００８】
再び、図３を参照すると、時間性圧縮を達成するため、反量化（iQ）、反排列（inverse  formatting、iF、鋸歯状／或いは、その他の形状）、及び、反DCT（iDCT）の後、動き推定のブロックマッチングが完成する。全情報が、時間領域に回復した後、動き推定中のブロックマッチングが、時間領域中のデータに適用される。
【０００９】
図７を参照すると、本発明は、一種の新方法を提出する。全ブロックマッチングアルゴリズムが周波数領域に適用できるので、動き推定は、iDCTプロセスの前に実行され、図７の二つの矢印１と２で示される。低周波数は人の目には敏感であるので、低周波数情報が最適なマッチングポイントを見つけ、高周波数情報を削除すればよい。例えば、８×８DCTブロック（図５）で、各６４ビットの最初の８ビットだけを得て、動き推定し、その後、計算の複雑性は、元の計算の１２．５％まで減少する。必要時に、動き推定の一部は、iDCT後に完成する。全比較アルゴリズムが周波数領域に適用できるため、また、高周波数情報を削除したために比較点が減少するため、計算の複雑性が減少する。
本発明は、現有のブロック／アルゴリズムを使用し、処理の順序を変更するだけで、計算を減少する目的を達成する。
【００１０】
本発明では好ましい実施例を前述の通り開示したが、これらは決して本発明に限定するものではなく、当該技術を熟知する者なら誰でも、本発明の精神と領域を脱しない範囲内で各種の変動や潤色を加えることができ、従って本発明明の保護範囲は、特許請求の範囲で指定した内容を基準とする。
【図面の簡単な説明】
【００１１】
【図１】動き推定中のモーションベクトルを示す図である。
【図２】公知のフルサーチ動き推定を示す図である。
【図３】MPEG４システムがビデオ圧縮に用いられることを示す図である。
【図４】ビデオ圧縮のサンプルピクチャを示す図である。
【図５】サンプルピクチャがDCT転換を経た後の結果を示す図である。
【図６】DCT転換中の鋸歯形状の順序を示す図である。
【図７】本発明のビデオ圧縮に用いられるシステムを示す図である。
【図１】
2006261950.tif 000003
【図２】
2006261950.tif 000004
【図３】
2006261950.tif 000005
【図４】
2006261950.tif 000006
【図５】
2006261950.tif 000007
【図６】
2006261950.tif 000008
【図７】
2006261950.tif 000009