(57)【要約】  本発明は、時空間的複雑度を用いた符号化モード決定方法及び装置に関するものである。  本発明は、符号化モードを決定する装置であって、マクロブロックの時間的複雑度を計算する時間的複雑度計算部と、時間的複雑度を用いて符号化モードを決定するモード決定部と、を含むことを特徴とする時間的複雑度を用いた符号化モード決定装置を提供する。  本発明によれば、マクロブロックに対する時間的複雑度と空間的複雑度をより正確に計算できるだけでなく、それを用いて最適の符号化モードを選別することによって、レート−歪み最適化技法を適用する時の計算の複雑度を減らし、処理速度を向上することができる。
2011510591.tif 000002
【特許請求の範囲】
【請求項１】
符号化モードを決定する装置であって、
マクロブロックの時間的複雑度を計算する時間的複雑度計算部と、
前記時間的複雑度を用いて前記符号化モードを決定するモード決定部と、
を含むことを特徴とする時間的複雑度を用いた符号化モード決定装置。
【請求項２】
前記モード決定部は、
前記時間的複雑度が既設定された時間しきい値より大きい場合には、イントラブロックモードを前記符号化モードとして決定することを特徴とする請求項１に記載の時間的複雑度を用いた符号化モード決定装置。
【請求項３】
前記モード決定部は、
前記時間的複雑度が既設定された時間しきい値より小さいか等しい場合には、インターブロックモードを前記符号化モードとして決定することを特徴とする請求項１に記載の時間的複雑度を用いた符号化モード決定装置。
【請求項４】
前記時間しきい値は、
前記マクロブロックを含む現在フレームの以前フレームで前記マクロブロックと同一な位置を有する以前マクロブロックの時間的複雑度であることを特徴とする請求項２または請求項３に記載の時間的複雑度を用いた符号化モード決定装置。
【請求項５】
前記時間的複雑度計算部は、
前記マクロブロックのブロックレジデュアルをアダマール変換し、量子化幅で割って、前記時間的複雑度を計算することを特徴とする請求項１に記載の時間的複雑度を用いた符号化モード決定装置。
【請求項６】
符号化モードを決定する装置であって、
マクロブロックの空間的複雑度を計算する空間的複雑度計算部と、
前記空間的複雑度を用いて前記符号化モードを決定するモード決定部と、
を含むことを特徴とする空間的複雑度を用いた符号化モード決定装置。
【請求項７】
前記モード決定部は、
前記空間的複雑度が既設定された空間しきい値より大きい場合には小型ブロックモードを前記符号化モードとして決定することを特徴とする請求項６に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項８】
前記モード決定部は、
前記空間的複雑度が既設定された空間しきい値より小さいか等しい場合には、大型ブロックモードを前記符号化モードとして決定することを特徴とする請求項６に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項９】
前記空間しきい値は、
前記マクロブロックを含む現在フレームの以前フレームで前記マクロブロックと同一な位置を有する以前マクロブロックの空間的複雑度であることを特徴とする請求項７または請求項８に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項１０】
前記空間的複雑度は、前記マクロブロックの垂直複雑度及び前記マクロブロックの水平複雑度を含み、かつ、前記モード決定部は、前記垂直複雑度が前記水平複雑度より大きい場合には、垂直方向性ブロックモードを前記符号化モードとして決定することを特徴とする請求項６に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項１１】
前記空間的複雑度は、前記マクロブロックの垂直複雑度及び前記マクロブロックの水平複雑度を含み、かつ、前記モード決定部は、前記垂直複雑度と前記水平複雑度とが同一な場合には、非方向性ブロックモードを前記符号化モードとして決定することを特徴とする請求項６に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項１２】
前記空間的複雑度は、前記マクロブロックの垂直複雑度及び前記マクロブロックの水平複雑度を含み、かつ、前記モード決定部は、前記垂直複雑度が前記水平複雑度より小さい場合には、水平方向性ブロックモードを前記符号化モードとして決定することを特徴とする請求項６に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項１３】
前記空間的複雑度計算部は、
前記マクロブロックの垂直複雑度及び前記マクロブロックの水平複雑度の和を量子化幅で割って、前記空間的複雑度を計算することを特徴とする請求項６に記載の空間的複雑度を用いた符号化モード決定装置。
【請求項１４】
符号化モードを決定する装置が前記符号化モードを決定する方法であって、
（ａ）マクロブロックの時間的複雑度を計算するステップと、
（ｂ）前記マクロブロックの空間的複雑度を計算するステップと、
（ｃ）前記時間的複雑度が既設定された時間しきい値より大きい場合には、イントラブロックモードを前記符号化モードとして決定するステップと、
（ｄ）前記時間的複雑度が前記時間しきい値より小さいか等しい場合には、インターブロックモードを前記符号化モードとして決定するステップと、
を含むことを特徴とする時空間的複雑度を用いた符号化モード決定方法。
【請求項１５】
前記符号化モード決定方法は、
前記ステップ（ｂ）の以後に、
（ｅ）前記空間的複雑度が既設定された空間しきい値より大きい場合には、小型のブロックモードを前記符号化モードとして決定するステップと、
（ｆ）前記空間的複雑度が前記空間しきい値より小さいか等しい場合には、大型のブロックモードを前記符号化モードとして決定するステップと、
をさらに含むことを特徴とする請求項１４に記載の時空間的複雑度を用いた符号化モード決定方法。
【請求項１６】
前記符号化モード決定方法は、
前記ステップ（ｂ）の以後に、
（ｇ）前記空間複雑度を用いて前記マクロブロックの垂直複雑度と前記マクロブロックの水平複雑度とを比較するステップと、
（ｈ）前記マクロブロックの垂直複雑度が前記マクロブロックの水平複雑度より大きい場合には、垂直方向性ブロックモードを前記符号化モードとして決定するステップと、
（ｉ）前記マクロブロックの垂直複雑度が前記マクロブロックの水平複雑度と同一な場合には、非方向性ブロックモードを前記符号化モードとして決定するステップと、
（ｊ）前記マクロブロックの垂直複雑度が前記マクロブロックの水平複雑度より小さい場合には、水平方向性ブロックモードを前記符号化モードとして決定するステップと、
をさらに含むことを特徴とする請求項１５に記載の時空間的複雑度を用いた符号化モード決定方法。
【請求項１７】
前記ステップ（ａ）で、前記符号化モード決定装置は、
前記マクロブロックのブロックレジデュアルをアダマール変換し、量子化幅で割って前記時間的複雑度を計算することを特徴とする請求項１４に記載の時空間的複雑度を用いた符号化モード決定方法。
【請求項１８】
前記ステップ（ｂ）で、前記符号化モード決定装置は、
前記マクロブロックの垂直複雑度及び前記マクロブロックの水平複雑度の和を量子化幅で割って前記空間的複雑度を計算することを特徴とする請求項１４に記載の時空間的複雑度を用いた符号化モード決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時空間的複雑度を用いた符号化モード決定方法及び装置に関し、より詳しくは、レート−歪み最適化（ＲＤＯ：Rate-Distortion Optimization）技法を用いてマクロブロック（Macro Block）に対し、最適の符号化モードを決定するに当たって、レート−歪み値（ＲＤ Ｃｏｓｔ：Rate-Distortion Cost）の計算を最小にするための符号化モードを決定する方法及び装置に関する。
【背景技術】
【０００２】
通常、ＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４ Visual、Ｈ．２６１、Ｈ．２６３、及びＨ．２６４／ＭＰＥＧ−４ ＡＶＣなどの画像圧縮標準案では、１つのフレームを複数個のマクロブロックに分割した後、マクロブロック単位に予測を遂行して予測ブロックを求め、元の画像ブロックと予測ブロックとの差を変換及び量子化する方式により画像データを圧縮する。
【０００３】
予測の方式には、イントラ予測（Intra Prediction）とインター予測（Inter Prediction）の２つがある。イントラ予測は、現在フレームに存在する周辺ブロックのデータを用いて現在ブロックの予測を遂行する。インター予測は、ブロック基盤動き補償を用いて以前に符号化された１つまたはその以上のビデオフレームから現在ブロックに対応する予測ブロックを生成する。
【０００４】
特に、インター予測時に、Ｈ．２６４／ＭＰＥＧ−４ ＡＶＣは固定されたサイズのブロックでなく、４×４から１６×１６までの７種類の可変ブロックモードを用いて動き予測を遂行する。
【０００５】
図１ａは、従来のＨ．２６４／ＭＰＥＧ−４ ＡＶＣの可変ブロックサイズ動き予測で用いられる多様なサイズのブロックを示す例示図である。
【０００６】
図１ａに示すように、各マクロブロックの輝度成分（１６×１６サンプル）は、４つの方法により分割できる。即ち、各マクロブロックは１つの１６×１６マクロブロックパーティション、２つの１６×８パーティション、２つの８×１６パーティション、または４個の８×８パーティションに分割されて動き予測できる。
【０００７】
また、８×８モードが選択されれば、マクロブロック内の４個の８×８サブマクロブロックは、各々４つの方法により分割できる。即ち、８×８モードが選択された場合、各８×８ブロックは１つの８×８サブマクロブロックパーティション、２つの８×４サブマクロブロックパーティション、２つの４×８サブマクロブロックパーティション、または４個の４×４サブマクロブロックパーティションのうちの１つに分割される。
【０００８】
各マクロブロック内でこのようなパーティションとサブマクロブロックの非常に多い数の組合せが可能である。マクロブロックを多様なサイズのサブブロックに分けるこのような方法をツリー構造動き補償（Tree Structured Motion Compensation）という。
【０００９】
１つのマクロブロックに対し、最適の符号化モードを決定するために、Ｈ．２６４標準案によると、レート−歪み最適化技法を用いる。通常のレート−歪み最適化等式は、次の＜数式１＞の通りである。
【００１０】
【数１】
2011510591.tif 000003
【００１１】
＜数式１＞で、Jmodeはレート−歪み値、λmodeはラグランジュ乗算子（Lagrangian Multiplier）、Ｄは元のマクロブロックと再構成されたマクロブロックとの間の歪み値、Ｒはモード選択及びマクロブロックの量子化値と関連したビット数を反映する係数である。＜数式１＞を用いて各マクロブロックを多様な可変ブロックに分けて符号化して見た後、最小のレート−歪み値を有するモードを最適のモードとして決定する。
【００１２】
即ち、符号化器は全ての予測された符号化モードに対し、符号化過程を遂行した後、レート−歪み値を計算して、レート−歪み値が最も小さい予測モードを実際の符号化に用いる予測モードとして決定する。
【００１３】
このようなレート−歪み最適化技法は、Ｈ．２６４／ＡＶＣ符号化器の圧縮性能を格段に向上させるが、それによって複雑度が非常にたくさん増加するため、リアルタイム符号化に大きい障害となる問題点がある。
【００１４】
図１ｂは、レート−歪み最適化の遂行に従う計算複雑度を示す例示図である。
【００１５】
図１ｂに示すように、レート−歪み最適化を遂行する場合がそうでない場合に比べて最小７倍乃至８倍以上に計算の複雑度が増加する。
【００１６】
したがって、レート−歪み最適化技法を用いて、符号化して圧縮に対する性能を維持しながらも符号化器が画像を圧縮することにかかる速度を最小化し、計算の複雑度を格段に減少させるための技術の開発が必要な実状である。
【発明の概要】
【発明が解決しようとする課題】
【００１７】
前述した要求に応ずるために、本発明は、レート−歪み最適化技法を用いてマクロブロックに対して最適の符号化モードを決定するに当たって、レート−歪み値の計算を最小にするための符号化モードを決定する方法及び装置を提供することをその目的とする。
【課題を解決するための手段】
【００１８】
前述した目的を達成するために、本発明は、符号化モードを決定する装置であって、マクロブロックの時間的複雑度を計算する時間的複雑度計算部と、時間的複雑度を用いて上記符号化モードを決定するモード決定部と、を含むことを特徴とする時間的複雑度を用いた符号化モード決定装置を提供する。
【００１９】
また、本発明の他の目的によれば、符号化モードを決定する装置であって、マクロブロックの空間的複雑度を計算する空間的複雑度計算部と、空間的複雑度を用いて上記符号化モードを決定するモード決定部と、を含むことを特徴とする空間的複雑度を用いた符号化モード決定装置を提供する。
【００２０】
また、本発明の更に他の目的によれば、符号化モードを決定する装置が符号化モードを決定する方法であって、（ａ）マクロブロックの時間的複雑度を計算するステップと、（ｂ）マクロブロックの空間的複雑度を計算するステップと、（ｃ）時間的複雑度が既設定された時間しきい値より大きい場合には、イントラブロックモードを上記符号化モードとして決定するステップと、（ｄ）時間的複雑度が時間しきい値より小さいか等しい場合には、インターブロックモードを符号化モードとして決定するステップと、を含むことを特徴とする時空間的複雑度を用いた符号化モード決定方法を提供する。
【発明の効果】
【００２１】
以上、説明したように、本発明によれば、マクロブロックに対する時間的複雑度と空間的複雑度をより正確に計算できるだけでなく、それを用いて最適の符号化モードを選別することによって、レート−歪み最適化技法を適用する時の計算の複雑度を減らし、処理速度を向上することができる。
【図面の簡単な説明】
【００２２】
【図１ａ】従来のＨ．２６４／ＭＰＥＧ−４ ＡＶＣの可変ブロックサイズ動き予測で用いられる多様なサイズのブロックを示す例示図である。
【図１ｂ】レート−歪み最適化の遂行に従う計算複雑度を示す例示図である。
【図２】本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定装置の電子的な構成を示すブロック構成図である。
【図３】本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定方法を説明するためのフローチャートである。
【図４】本発明の一実施形態に従って時間的複雑度と空間的複雑度を計算する過程を説明するための例示図である。
【発明を実施するための形態】
【００２３】
以下、本発明の好ましい実施形態を添付された図面を参照しつつ詳細に説明する。まず各図面の構成要素に参照符号を付加するに当たって、同一な構成要素に対してはたとえ他の図面上に表示されても、できる限り同一な符号を有するようにしていることに留意しなければならない。また、本発明を説明するに当たって、関連した公知構成または機能に対する具体的な説明が本発明の要旨を曖昧にすることができると判断される場合にはその詳細な説明は省略する。
【００２４】
Ｈ．２６４の画像圧縮標準によれば、マクロブロックが有することができるブロックモードの種類は、＜表１＞及び＜表２＞の通りである。
【００２５】
＜表１＞はイントラブロックモードの種類と分類を示すものであり、＜表２＞はインターブロックモードの種類と分類を示すものである。
【００２６】
【表１】
2011510591.tif 000004
【００２７】
【表２】
2011510591.tif 000005
【００２８】
本発明では、サイズによって４個のイントラブロックモード（イントラ１６×１６_Vertical、イントラ１６×１６_Horizontal、イントラ１６×１６_ＤＣ、イントラ１６×１６_Plane）と、４個のインターブロックモード（インターSKIP、インター１６×１６、インター１６×８、インター８×１６）を‘大型ブロックモード’と定義し、９個のイントラブロックモード（イントラ４×４_Vertical、イントラ４×４_Horizontal、イントラ４×４_ＤＣ、イントラ４×４_Diagonal Down Left、イントラ４×４_Diagonal Down Right、イントラ４×４_Vertical Right、イントラ４×４_Horizontal Down、イントラ４×４_Vertical Left、イントラ４×４_Horizontal UP）と、４個のインターブロックモード（インター８×８、インター８×４、インター４×８、インター４×４）を‘小型ブロックモード’と定義する。
【００２９】
また、本発明では方向性によって、垂直方向性を有する４個のイントラブロックモード（イントラ１６×１６_Vertical、イントラ４×４_Vertical、イントラ４×４_Vertical Right、イントラ４×４_Vertical Left）と、垂直方向性を有する２つのインターブロックモード（インター８×１６、インター４×８）を‘垂直方向性ブロックモード’と定義し、水平方向性を有する４個のイントラブロックモード（イントラ１６×１６_Horizontal、イントラ４×４_Horizontal、イントラ４×４_Horizontal Down、イントラ４×４_Horizontal UP）と、２つのインターブロックモード（インター１６×８、インター８×４）を‘水平方向性ブロックモード’と定義し、垂直または水平の方向性を有しない５個のイントラブロックモード（イントラ１６×１６_ＤＣ、イントラ１６×１６_Plane、イントラ４×４_ＤＣ、イントラ４×４_Diagonal Down Left、イントラ４×４_Diagonal Down Right）と、４個のインターブロックモード（インターSKIP、インター１６×１６、インター８×８、インター４×４）を‘非方向性ブロックモード’と定義する。
【００３０】
したがって、＜表１＞及び＜表２＞に表したイントラブロックモードまたはインターブロックモードは、各々そのサイズと方向性によって‘分類’項目に表したように分類できる。即ち、例えば‘イントラ１６×１６_Vertical’は‘イントラブロックモード’として１６×１６のサイズを有するので、‘大型ブロックモード’であり、Verticalの特性があるので‘垂直方向性ブロックモード’である。したがって、このような特性を組み合わせると、＜表１＞に表した分類のように、‘大型垂直方向性イントラブロックモード’に分類できる。残りのイントラブロックモード及びインターブロックモードもこのような方式により分類できる。
【００３１】
図２は、本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定装置の電子的な構成を示すブロック構成図である。
【００３２】
本発明の一実施形態に従う符号化モード決定装置は、時間的複雑度（Temporal Complexity）計算部２１０、空間的複雑度（Spatial Complexity）計算部２２０、及びモード決定部２２０を含んで構成する。
【００３３】
本発明の一実施形態に従う時間的複雑度計算部２１０は、演算を遂行してデータを生成し格納するデータ処理手段であって、画像のマクロブロック（Macro Block）を分析してマクロブロックの時間的複雑度を計算する。
【００３４】
また、本発明の一実施形態に従う時間的複雑度計算部２１０は、マクロブロックのレジデュアル（Residual）であるブロックレジデュアル（Block Residual）を計算し、ブロックレジデュアルをアダマール変換（Hadamard Transform）して、時間的ブロック複雑度（Temporal Block Complexity）を計算した後、時間的ブロック複雑度を量子化幅（Quantization Step Size）で割って時間的複雑度を計算する。時間的複雑度を計算する過程については図４を通じて詳細に説明する。
【００３５】
本発明の一実施形態に従う空間的複雑度計算部２２０は、演算を遂行してデータを生成し格納するデータ処理手段であって、画像のマクロブロックを分析してマクロブロックの空間的複雑度を計算する。
【００３６】
また、本発明の一実施形態に従う空間的複雑度計算部２２０は、マクロブロックを垂直フィルタリング（Vertical Filtering）して垂直複雑度（Vertical Complexity）を計算し、マクロブロックを水平フィルタリング（Horizontal Filtering）して水平複雑度（Horizontal Complexity）を計算し、垂直複雑度と水平複雑度とを合せて空間的ブロック複雑度（Spatial Block Complexity）を計算した後、量子化幅で割って空間的複雑度を計算する。空間的複雑度を計算する過程については図４を通じて詳細に説明する。
【００３７】
本発明の一実施形態に従うモード決定部２３０は、演算を遂行してデータを生成し格納するデータ処理手段であって、時間的複雑度計算部２１０で計算した時間的複雑度と空間的複雑度計算部２２０で計算した空間的複雑度を用いて符号化するブロックモードである符号化モード（Encoding Mode）を決定する。
【００３８】
即ち、本発明の一実施形態に従うモード決定部２３０は、時間的複雑度が大きければ、イントラモードに符号化する確率が高いので、イントラブロックモード（イントラ１６×１６_Vertical、イントラ１６×１６_Horizontal、イントラ１６×１６_ＤＣ、イントラ１６×１６_Plane、イントラ４×４_Vertical、イントラ４×４_Horizontal、イントラ４×４_ＤＣ、イントラ４×４_Diagonal Down Left、イントラ４×４_Diagonal Down Right、イントラ４×４_Vertical Right、イントラ４×４_Horizontal Down、イントラ４×４_Vertical Left、イントラ４×４_Horizontal UP）を符号化モードとして決定し、時間的複雑度が小さければ、インターモードに符号化する確率が高いので、インターブロックモード（インターSKIP、インター１６×１６、インター１６×８、インター８×１６、インター８×８、インター８×４、インター４×８、インター４×４）を符号化モードとして決定する。
【００３９】
したがって、本発明の一実施形態に従うモード決定部２３０は、時間的複雑度を既設定された時間しきい値と比較して時間的複雑度が時間しきい値より大きい場合には、イントラブロックモードを符号化モードとして決定し、時間的複雑度が時間しきい値より小さいか等しい場合には、インターブロックモードを符号化モードとして決定する。
【００４０】
本発明において、時間しきい値とは、現在のマクロブロックを含む現在フレームの以前のフレームである以前フレームで現在のマクロブロックと同一な位置を有する以前マクロブロックの時間的複雑度をいう。
【００４１】
また、本発明の一実施形態に従うモード決定部２３０は、空間的複雑度が大きければ、小さなサイズ、即ち小型のブロックモードが符号化モードに決定される確率が高いので、小型ブロックモード（イントラ４×４_Vertical、イントラ４×４_Horizontal、イントラ４×４_ＤＣ、イントラ４×４_Diagonal Down Left、イントラ４×４_Diagonal Down Right、イントラ４×４_Vertical Right、イントラ４×４_Horizontal Down、イントラ４×４_Vertical Left、イントラ４×４_Horizontal UP、インター８×８、インター８×４、インター４×８、インター４×４）を符号化モードとして決定し、空間的複雑度が小さければ、大きいサイズ、即ち大型のブロックモードが符号化モードに決定される確率が高いので、大型ブロックモード（イントラ１６×１６_Vertical、イントラ１６×１６_Horizontal、イントラ１６×１６_ＤＣ、イントラ１６×１６_Plane、インターSKIP、インター１６×１６、インター１６×８、インター８×１６）を符号化モードとして決定する。
【００４２】
したがって、本発明の一実施形態に従うモード決定部２３０は、空間的複雑度と既設定された空間しきい値とを比較して、空間的複雑度が空間しきい値より大きければ、小型ブロックモードを符号化モードとして決定し、空間的複雑度が空間しきい値より小さいか等しいと、大型ブロックモードを符号化モードとして決定する。
【００４３】
本発明において、空間しきい値とは、現在のマクロブロックを含む現在フレームの以前のフレームである以前フレームで現在のマクロブロックと同一な位置を有する以前マクロブロックの空間的複雑度をいう。
【００４４】
また、本発明の一実施形態に従うモード決定部２３０は、マクロブロックの垂直複雑度とマクロブロックの水平複雑度とを比較して、垂直複雑度が水平複雑度より大きければ、垂直方向性を有するブロックモードである垂直方向性ブロックモード（イントラ１６×１６_Vertical、イントラ４×４_Vertical、イントラ４×４_Vertical Right、イントラ４×４_Vertical Left、インター８×１６、インター４×８）を符号化モードとして決定し、垂直複雑度と水平複雑度とが同一な場合には、方向性を有しないブロックモードである非方向性ブロックモード（イントラ１６×１６_ＤＣ、イントラ１６×１６_Plane、イントラ４×４_ＤＣ、イントラ４×４_Diagonal Down Left、イントラ４×４_Diagonal Down Right、インターSKIP、インター１６×１６、インター８×８、インター４×４）を符号化モードとして決定し、垂直複雑度が水平複雑度より小さい場合には、水平方向性ブロックモード（イントラ１６×１６_Horizontal、イントラ４×４_Horizontal、イントラ４×４_Horizontal Down、イントラ４×４_Horizontal UP、インター１６×８、インター８×４）を符号化モードとして決定する。
【００４５】
本発明において、時間的複雑度計算部２１０、空間的複雑度計算部２２０、及びモード計算部２３０は、各機能を遂行するプログラム、データを格納するメモリ、及びメモリに格納されたプログラムを実行し、データを生成してメモリに格納するマイクロプロセッサを含む独立的なハードウェアとして具現されることもできるが、各機能を遂行するプログラムモジュールとして具現されてメモリに格納され、マイクロプロセッサにより実行されることもできる。
【００４６】
また、以上ではモード計算部２３０が時間的複雑度を用いてイントラブロックモードまたはインターブロックモードを符号化モードとして決定し、空間的複雑度を用いて小型ブロックモードまたは大型ブロックモードを符号化モードとして決定し、垂直複雑度と水平複雑度とを用いて垂直方向性ブロックモード、非方向性ブロックモード、及び水平方向性ブロックモードのうちのいずれか１つを符号化モードとして決定することが各々選択的に遂行されることと説明したが、各々互いに総合して遂行することもできる。
【００４７】
即ち、例えば時間的複雑度が時間しきい値より大きく、空間的複雑度が空間しきい値より大きく、垂直複雑度が水平複雑度より大きい場合、モード計算部２３０は、イントラブロックモードのうち、小型で、かつ垂直方向性を有するブロックモードである小型垂直方向性イントラブロックモード（イントラ４×４_Vertical、イントラ４×４_Vertical Right、イントラ４×４_Vertical Left）を符号化モードとして決定する。したがって、この場合、本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定装置を含む符号化器は、符号化モード決定装置が符号化モードとして決定した前述した３個のブロックモードのみのレート−歪み値を計算して最終の符号化モードを決定することができるので、レート−歪み最適化技法を遂行するための計算量や処理時間を最小化することができる。
【００４８】
画像または動画を圧縮する符号化器は、動画を符号化する前に動画をフレーム単位に分割し、各フレームのイメージをマクロブロックに分割して符号化するが、この際、符号化モードを決定する。符号化器が符号化モードを決定する際、Ｈ．２６４画像圧縮標準ではレート−歪み最適化技法を用いる。しかしながら、レート−歪み最適化技法を用いて符号化モードを決定する際、符号化モードと予想される全てのブロックモード（即ち、イントラブロックモードとインターブロックモード）に対し、レート−歪み最適化技法を遂行してレート−歪み値を求めるので、計算が非常に複雑になり、計算に従う符号化器の負荷負担が増加し、それによって符号化に多くの時間がかかる。
【００４９】
したがって、本発明では、前述したように、符号化器がレート−歪み値を計算しなければならないブロックモードの個数を最小化できるように符号化モードを決定して全てのブロックモードに対してレート−歪み値を計算しなければならない非効率を改善する。
【００５０】
このために、符号化器に一種のハードウェアまたはソフトウェアモジュールとして具現されることができ、図２を通じて前述した本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定装置がマクロブロックの時間的複雑度と空間的複雑度を計算して最小個数の符号化モードを決定し、符号化器はこのように決定された最小個数の符号化モードに対してレート−歪み最適化技法を遂行してレート−歪み値を計算して最終符号化モードを決定する。
【００５１】
以下、図３を通じて本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定装置が符号化モードを決定する過程について説明する。
【００５２】
図３は、本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定方法を説明するためのフローチャートである。
【００５３】
本発明の一実施形態に従う時空間的複雑度を用いた符号化モード決定装置（以下、説明の便宜のために、‘符号化モード決定装置’と略称する）は、マクロブロックの時間的複雑度を計算し（Ｓ３１０）、マクロブロックの空間的複雑度を計算する（Ｓ３２０）。
【００５４】
マクロブロックの時間的複雑度と空間的複雑度を計算した符号化モード決定装置は、時間的複雑度を既設定した時間しきい値と比較することによって、時間的複雑度が時間しきい値より大きいか否かを確認して（Ｓ３３０）、時間的複雑度が時間しきい値より大きい場合には、イントラブロックモードを符号化モードとして決定し（Ｓ３４０）、時間的複雑度が時間しきい値より小さいか等しい場合には、インターブロックモードを符号化モードとして決定する（Ｓ３４２）。
【００５５】
即ち、符号化モード決定装置は、現在フレームの現在のマクロブロックの時間的複雑度が以前フレームの以前マクロブロックの時間的複雑度より大きい場合には、レート−歪み値を計算して符号化モードを決定するとしても、イントラブロックモードが符号化モードとして決定される確率が高いので、イントラブロックモードを符号化モードとして決定し、その反対の場合にはインターブロックモードを符号化モードとして決定するものである。
【００５６】
また、符号化モード決定装置は、空間的複雑度を既設定した空間しきい値と比較することによって、空間的複雑度が空間しきい値より大きいか否かを確認して（Ｓ３５０）、空間的複雑度が空間的しきい値より大きい場合には、小型ブロックモードを符号化モードとして決定し（Ｓ３６０）、空間的複雑度が空間的しきい値より小さいか等しい場合には、大型ブロックモードを符号化モードとして決定する（Ｓ３６２）。
【００５７】
即ち、符号化モード決定装置は、現在フレームの現在のマクロブロックの空間的複雑度が以前フレームの以前マクロブロックの空間的複雑度より大きい場合には、レート−歪み値を計算して符号化モードを決定するとしても、小型ブロックモードが符号化モードとして決定される確率が高いので、小型ブロックモードを符号化モードとして決定し、その反対の場合には大型ブロックモードを符号化モードとして決定するものである。
【００５８】
また、符号化モード決定装置は、空間的複雑度に含まれた垂直複雑度と水平複雑度とを比較することによって、垂直複雑度が水平複雑度より大きいか否かを確認して（Ｓ３７０）、垂直複雑度が水平複雑度より大きい場合には、垂直方向性ブロックモードを符号化モードとして決定し（Ｓ３７２）、垂直複雑度と水平複雑度が同一な場合には、非方向性ブロックモードを符号化モードとして決定し（Ｓ３７４）、垂直複雑度が水平複雑度より小さい場合には、水平方向性ブロックモードを符号化モードとして決定する（Ｓ３７６）。
【００５９】
即ち、符号化モード決定装置は、現在フレームが現在のマクロブロックの垂直複雑度が水平複雑度より大きい場合には、レート−歪み値を計算して符号化モードを決定するとしても垂直方向性ブロックモードが符号化モードとして決定される確率が高いので、垂直方向性ブロックモードを符号化モードとして決定し、同一な場合には非方向性ブロックモードを、そして、その小さい場合には大型ブロックモードを符号化モードとして決定するものである。
【００６０】
このように、符号化モード決定装置は、時間的複雑度、空間的複雑度、及び空間的複雑度に含まれた垂直複雑度と水平複雑度などを用いて符号化モードを決定する。
【００６１】
一方、図３を通じては符号化モードを決定するに当たって、時間的複雑度を用いて符号化モードを決定する過程（ステップＳ３３０乃至ステップＳ３４２）、空間的複雑度を用いて符号化モードを決定する過程（ステップＳ３５０乃至ステップＳ３６２）、及び空間的複雑度に含まれた垂直複雑度と水平複雑度とを全て用いて符号化モードを決定する過程（ステップＳ３６０乃至ステップＳ３７６）を全て遂行することと説明したが、このような各過程は１つまたは２つのみ選択的に遂行されることもでき、３個の過程が全て遂行されることができ、その遂行される順序も任意に決定できる。
【００６２】
したがって、例えば図３に示すように、３個の過程が順に遂行されて時間的複雑度を用いてイントラブロックモードが決定され、空間的複雑度を用いて小型ブロックモードが決定され、垂直複雑度と水平複雑度とを用いて垂直方向性ブロックモードが決定されたことと仮定すれば、符号化モードとして決定されるブロックモードは＜表１＞で‘小型垂直方向性イントラブロックモード’に分類される‘イントラ４×４_Vertical’、‘イントラ４×４_Vertical Right’及び‘イントラ４×４_Vertical Left’となる。即ち、符号化器は前述した３個のブロックモードのみでレート−歪み値を計算して最終の符号化モードを決定し、最終の符号化モードに画像を圧縮する。
【００６３】
また、例えば、符号化モード決定装置が垂直複雑度と水平複雑度とを全て用いて符号化モードを決定する過程（ステップＳ３６０乃至ステップＳ３７６）を遂行して水平方向性ブロックモードが符号化モードとして決定された後、時間的複雑度を用いて符号化モードを決定する過程（ステップＳ３３０乃至ステップＳ３４２）を遂行してインターブロックモードが符号化モードとして決定されたことと仮定すれば、符号化モードとして決定されるブロックモードは‘水平方向性インターブロックモード（即ち、‘大型水平方向性インターブロックモード’と‘小型水平方向性インターブロックモード’）’である‘インター１６×８’と‘インター８×４’となる。即ち、符号化器は前述した２つのブロックモードのみでレート−歪み値を計算して最終の符号化モードを決定し、最終の符号化モードに画像を圧縮する。
【００６４】
図４は、本発明の一実施形態に従って時間的複雑度と空間的複雑度を計算する過程を説明するための例示図である。
【００６５】
図４ａは、時間的複雑度を計算するために使われるアダマール変換（Hadamard Transform）行列を示すものである。
【００６６】
符号化モード決定装置は、マクロブロックの時間的複雑度を計算するために、マクロブロックに動き補償を遂行して重複性を除去することによって、レジデュアル信号の行列であるブロックレジデュアルを計算し、ブロックレジデュアルに図４ａに示すアダマール変換行列を掛けてアダマール変換を遂行することによって、時間的ブロック複雑度を計算する。また、符号化モード決定装置は、時間的ブロック複雑度を量子化幅で割って時間的複雑度を計算する。ここで、マクロブロックは、マクロブロックのピクセル（Pixel）値を有する１６×１６の行列をいう。このような過程は＜数式２＞のように表示することができる。
【００６７】
【数２】
2011510591.tif 000006
【００６８】
本発明では、動き補償によりマクロブロックの重複性を除去した後、アダマール変換をさらに遂行してレジデュアル信号上の重複性をもう一度除去することによって、実際のビット発生量の誤差を格段に減少させる。
【００６９】
即ち、アダマール変換は入力信号を周波数に分解する機能があるので、アダマール変換を経たレジデュアル信号は総１６個の周波数に分解され、このように分解された周波数は実際の符号化過程で信号を圧縮するために使われる離散コサイン変換（ＤＣＴ：Discrete Cosine Transform）の周波数分解された結果物と極めて近似した値を有するようになる。したがって、符号化モード決定装置は、アダマール変換を通じて分解された周波数を用いて時間上に類似性を有する以前フレームとの差分信号を発生するデータ量を極めて正確に予測することができ、これを通じて時間的複雑度を極めて正確に計算することができる。
【００７０】
図４ｂは空間的複雑度を計算するために使われる垂直フィルタ（Vertical Filter）を示すものであり、図４ｃは空間的複雑度を計算するために使われる水平フィルタ（Horizontal Filter）を示すものである。
【００７１】
符号化モード決定装置は、空間的複雑度を計算するために、マクロブロックに図４ｂに図示した垂直フィルタを掛けることによって、マクロブロックを垂直フィルタリングしてマクロブロックの垂直複雑度を計算し、マクロブロックに図４ｃに図示した水平フィルタを掛けてマクロブロックを水平フィルタリングしてマクロブロックの水平複雑度を計算する。また、符号化モード決定装置は、垂直複雑度と水平複雑度を足した値を２で割って空間的ブロック複雑度を計算し、空間的ブロック複雑度を量子化幅で割って空間的複雑度を計算する。ここで、マクロブロックはマクロブロックのピクセル（Pixel）値を有する１６×１６の行列をいう。このような過程を＜数式３＞のように表示することができる。
【００７２】
【数３】
2011510591.tif 000007
【００７３】
本発明では、２次元の５個のタップ（Tap）を有するフィルタ（即ち、垂直フィルタと水平フィルタ）を使用して空間的複雑度を計算する。空間的複雑度は、イントラ予測が使われた場合のビット発生量を高い正確度で予測しようと計算するものである。
【００７４】
通常的な空間的複雑度を計算する方式では、マクロブロックの隣接した画素の差を求めた後、その差の総和を用いて単純に複雑度を計算する。しかしながら、本発明では２次元で構成される高域通過フィルタ（High Pass Filter、即ち、垂直フィルタ及び水平フィルタ）を用いて画素の位置に従ってその重要度に重み付け値を置いて検出を行なって符号化器の入力画像に存在する隅（Edge）を検出するようにする。隅は多様な方向性を有することができるので、水平フィルタと垂直フィルタを全て使用してフィルタリングし、これを合算して水平方向と垂直方向だけでなく、対角線方向に対しても隅を検出することができる。
【００７５】
また、本発明では実際の符号化過程でビット発生量を調節することに極めて重要に用いられる量子化幅を空間的複雑度を計算することに使用することによって、より正確に空間的複雑度を計算する。即ち、マクロブロックを垂直フィルタリングした値と水平フィルタリングした値とを足した後、量子化幅で割って空間的複雑度を計算するので、量子化幅によって変化できるビット発生量と空間的複雑度との間に発生できる誤差を格段に減少させることができる。このような接近は、イントラ予測で多様な予測方向（Prediction Direction）のうち、最も効率的なもののみを選別することに使われ、これによって符号化モードをより正確に決定することができる。
【００７６】
以上の説明は、本発明の技術思想を例示的に説明したことに過ぎないものであって、本発明が属する技術分野で通常の知識を有する者であれば、本発明の本質的な特性から逸脱しない範囲で多様な修正及び変形が可能である。したがって、本発明に開示された実施形態は本発明の技術思想を限定するためのものではなく、説明するためのものであり、このような実施形態により本発明の技術思想の範囲が限定されるのではない。本発明の保護範囲は請求範囲により解釈されなければならず、それと同等な範囲内にある全ての技術思想は本発明の権利範囲に含まれるものと解釈されるべきである。
【００７７】
本特許出願は、２００８年０１月２４日付で韓国に出願した特許出願番号第１０−２００８−０００７６６６号に対し、米国特許法１１９（ａ）条（３５Ｕ．Ｓ．Ｃ§１１９（ａ））に従って優先権を主張すれば、その全ての内容は参考文献として本特許出願に併合される(If applicable, this non-provisional application claims priorities under 35 U.S.C § 119(a) on Patent Application No.10-2008-0007666 filed in Korea on January 24, 2008, the entire content of which is hereby incorporated by reference.)。併せて、本特許出願は米国の以外に国家に対しても上記と同一な理由により優先権を主張すれば、その全ての内容は参考文献として本特許出願に併合される。
【産業上の利用可能性】
【００７８】
以上、説明したように、本発明はレート−歪み最適化技法を用いてマクロブロックに対して最適の符号化モードを決定するに当たって、レート−歪み値の計算を最小にするための符号化モードを決定する方法及び装置分野に適用されて、マクロブロックに対する時間的複雑度と空間的複雑度をより正確に計算できるだけでなく、それを用いて最適の符号化モードを選別することによって、レート−歪み最適化技法を適用する時の計算の複雑度を減らし、処理速度を向上することができる効果を発生する極めて有用な発明である。
【図１ａ】
2011510591.tif 000008
【図１ｂ】
2011510591.tif 000009
【図２】
2011510591.tif 000010
【図３】
2011510591.tif 000011
【図４ａ】
2011510591.tif 000012
【図４ｂ】
2011510591.tif 000013
【図４ｃ】
2011510591.tif 000014
【国際調査報告】
2011510591.tif 000015
2011510591.tif 000016
2011510591.tif 000017
2011510591.tif 000018