(57)【要約】【課題】バタフライ演算結果のばらつきが小さいサブブロックであっても、零係数が得られる否かを精度良く予測可能な動画像符号化装置を提供する。【解決手段】入力画像信号と予測画像信号との差であるブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力するバタフライ演算器１３１と；ブロック単位のバタフライ演算結果を複数のサブブロックに分割する分割器１３２と；サブブロック単位のバタフライ演算結果の絶対値和が閾値より大きければ、サブブロック単位のバタフライ演算結果に予め定められた行列を乗じ、直交変換係数を演算する行列演算部１４５と；直交変換係数を量子化し、量子化直交変換係数を出力する量子化部１４６と；絶対値和が閾値以下であれば零係数を設定する設定部１４９と；量子化直交変換係数または零係数を符号化する符号化器と；を具備する。【選択図】      図２
2009021802.tif 000002
【特許請求の範囲】
【請求項１】
ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成する予測部と、
前記ブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力するバタフライ演算器と、
前記ブロック単位のバタフライ演算結果を複数のサブブロックに分割し、サブブロック単位のバタフライ演算結果を出力する分割器と、
前記サブブロック単位のバタフライ演算結果の絶対値和を算出する算出部と、
前記絶対値和が閾値より大きければ、前記サブブロック単位のバタフライ演算結果に予め定められた行列を乗じ、直交変換係数を演算する行列演算部と、
前記直交変換係数を量子化パラメータに従って量子化し、量子化直交変換係数を出力する量子化部と、
前記絶対値和が前記閾値以下であれば零係数を設定する設定部と、
前記量子化直交変換係数または前記零係数を符号化する符号化器と
を具備することを特徴とする動画像符号化装置。
【請求項２】
前記量子化パラメータ、前記ブロックの色コンポーネント及び予測モードの少なくとも一つに基づいて前記閾値を生成する生成部を更に具備することを特徴とする請求項１記載の動画像符号化装置。
【請求項３】
前記生成部は、前記量子化パラメータに対して単調増加するように前記閾値を生成することを特徴とする請求項２記載の動画像符号化装置。
【請求項４】
前記生成部は、前記予測モードがイントラ予測の場合、インター予測の場合に比べて小さな値となるように前記閾値を生成することを特徴とする請求項２記載の動画像符号化装置。
【請求項５】
前記生成部は、前記色コンポーネントが輝度信号の場合、色差信号の場合に比べて小さな値となるように前記閾値を生成することを特徴とする請求項２記載の動画像符号化装置。
【請求項６】
ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成する予測部と、
前記ブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力するバタフライ演算器と、
前記ブロック単位のバタフライ演算結果を複数のサブブロックに分割し、サブブロック単位のバタフライ演算結果を出力する分割器と、
前記サブブロック単位のバタフライ演算結果の絶対値和を算出する算出部と、
前記絶対値和が第１閾値より大きければ、前記サブブロック単位のバタフライ演算結果に予め定める行列を乗じ、第１直交変換係数を演算する第１の行列演算部と、
前記第１直交変換係数を量子化パラメータに従って量子化し、第１量子化直交変換係数を出力する第１の量子化部と、
前記絶対値和が前記第１閾値以下であってかつ第２閾値より大きければ、前記サブブロック単位のバタフライ演算結果のうち第１周波数領域に含まれる第１要素に前記行列を乗じ、前記第１周波数領域より高い第２周波数領域に含まれる第２要素に０を与えて、第２直交変換係数を演算する第２の行列演算部と、
前記第１要素を前記量子化パラメータに従って量子化し、前記第２要素に０を与えて、第２量子化直交変換係数を出力する第２の量子化部と、
前記絶対値和が前記第２閾値以下であれば零係数を設定する設定部と、
前記第１直交変換係数、第２量子化直交変換係数または前記零係数を符号化する符号化器と
を具備することを特徴とする動画像符号化装置。
【請求項７】
前記第１要素は、前記サブブロックに含まれる要素数の４分の１を限度として、前記サブブロック単位のバタフライ演算結果から水平方向及び垂直方向の周波数成分の低い順に選ばれた要素であることを特徴とする請求項６記載の動画像符号化装置。
【請求項８】
ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成する予測部と、
前記ブロック単位の予測残差信号のうちの第１要素に対してバタフライ演算を行い、ブロック単位の部分的バタフライ演算結果を出力する第１の部分的バタフライ演算器と、
前記ブロック単位の部分的バタフライ演算結果を複数のサブブロックに分割し、サブブロック単位の第１のバタフライ演算結果を出力する分割器と、
前記サブブロック単位の第１のバタフライ演算結果の絶対値和を算出する算出部と、
前記第１絶対値和が閾値より大きければ、前記予測残差信号のうちの第２要素にバタフライ演算を行ってサブブロック単位の第２のバタフライ演算結果を出力する第２の部分的バタフライ演算器と、
前記サブブロック単位の第２のバタフライ演算結果に予め定める行列を乗じ、直交変換係数を演算する行列演算部と、
前記直交変換係数を量子化パラメータに従って量子化し、量子化直交変換係数を出力する量子化部と、
前記絶対値和が前記閾値以下であれば零係数を設定する設定部と、
前記第１量子化直交変換係数または前記零係数を符号化する符号化器と
を具備することを特徴とする動画像符号化装置。
【請求項９】
前記サブブロックは４×４画素の矩形領域であり、
前記第１要素は、前記サブブロックの対角線上の要素及び前記サブブロック単位のバタフライ演算結果に４×４アダマール変換を行って２番目に低い垂直方向周波数成分及び水平方向周波数成分を求める際に付与される符号が共通する要素を含むことを特徴とする請求項８記載の動画像符号化装置。
【請求項１０】
ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成し、
前記ブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力し、
前記ブロック単位のバタフライ演算結果を複数のサブブロックに分割し、サブブロック単位のバタフライ演算結果を出力し、
前記サブブロック単位のバタフライ演算結果の絶対値和を算出し、
前記絶対値和が閾値より大きければ、前記サブブロック単位のバタフライ演算結果に予め定められた行列を乗じ、直交変換係数を演算し、
前記直交変換係数を量子化パラメータに従って量子化し、量子化直交変換係数を出力し、
前記絶対値和が前記閾値以下であれば零係数を設定し、
前記量子化直交変換係数または前記零係数を符号化する
ことを特徴とする動画像符号化方法。
【請求項１１】
ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成し、
前記ブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力し、
前記ブロック単位のバタフライ演算結果を複数のサブブロックに分割し、サブブロック単位のバタフライ演算結果を出力し、
前記サブブロック単位のバタフライ演算結果の絶対値和を算出し、
前記絶対値和が第１閾値より大きければ、前記サブブロック単位のバタフライ演算結果に予め定める行列を乗じ、第１直交変換係数を演算し、
前記第１直交変換係数を量子化パラメータに従って量子化し、第１量子化直交変換係数を出力し、
前記絶対値和が前記第１閾値以下であってかつ第２閾値より大きければ、前記サブブロック単位のバタフライ演算結果のうち第１周波数領域に含まれる第１要素に前記行列を乗じ、前記第１周波数領域より高い第２周波数領域に含まれる第２要素に０を与えて、第２直交変換係数を演算し、
前記第１要素を前記量子化パラメータに従って量子化し、前記第２要素に０を与えて、第２量子化直交変換係数を出力し、
前記絶対値和が前記第２閾値以下であれば零係数を設定し、
前記第１直交変換係数、第２量子化直交変換係数または前記零係数を符号化する
ことを特徴とする動画像符号化方法。
【請求項１２】
ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成し、
前記ブロック単位の予測残差信号のうちの第１要素に対してバタフライ演算を行い、ブロック単位の部分的バタフライ演算結果を出力し、
前記ブロック単位の部分的バタフライ演算結果を複数のサブブロックに分割し、サブブロック単位の第１のバタフライ演算結果を出力し、
前記サブブロック単位の第１のバタフライ演算結果の絶対値和を算出し、
前記第１絶対値和が閾値より大きければ、前記予測残差信号のうちの第２要素にバタフライ演算を行ってサブブロック単位の第２のバタフライ演算結果を出力し、
前記サブブロック単位の第２のバタフライ演算結果に予め定める行列を乗じ、直交変換係数を演算し、
前記直交変換係数を量子化パラメータに従って量子化し、量子化直交変換係数を出力し、
前記絶対値和が前記閾値以下であれば零係数を設定し、
前記第１量子化直交変換係数または前記零係数を符号化する
ことを特徴とする動画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像に対して予測符号化を行う動画像符号化装置及び方法に関する。
【背景技術】
【０００２】
従来、動画像符号化装置では符号化対象ブロックの画像信号に対して直交変換、例えば離散コサイン変換（ＤＣＴ：Discrete Cosine Transform）などの変換を行って得られた係数を量子化し、量子化後の係数を符号化している。一般に、画像信号は低周波成分に比べて高周波成分の持つパワーが小さく、量子化後の係数が０になりやすい、即ち零係数が得られやすいことが知られている。また、上記動画像符号化装置では、動き補償フレーム間予測（以下、単にインター予測と称する）やフレーム内予測（以下、単にイントラ予測と称する）を用いて上記符号化対象ブロックの予測を行っているが、これらの予測精度が高ければ零係数が得られやすいことが知られている。零係数が得られるような周波数領域を予測することにより、不要な直交変換、量子化、逆量子化及び逆直交変換などの演算を省略して処理を高速化することができる。
【０００３】
特許文献１では、画像信号に零係数が得られるような周波数領域を予測するデータ圧縮符号化システムについて記載されている。具体的には、高速８×８ＤＣＴ演算の途中演算である８×８バタフライ演算の６４個の演算結果を４つのサブブロックに分割し、各サブブロックに含まれる１６個の演算結果の最大絶対値を指標として、零係数の予測を行っている。即ち、上記指標と予め定められた閾値と比較することにより、零係数が得られるサブブロックを予測し、当該サブブロックに対する残りの行列演算及び量子化処理を打ち切っている。
【特許文献１】特表２００２−５２７０１１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
特許文献１記載のデータ圧縮符号化システムでは、各サブブロックに含まれるバタフライ演算結果の最大絶対値を指標として零係数が得られるサブブロックを予測しているが、ＤＣＴ係数は実際にはバタフライ演算結果の係数分布によっても左右されるため、上記指標とは必ずしも連動しない。即ち、サブブロック内のバタフライ演算結果の最大絶対値が等しくても、他の要素のばらつき次第でＤＣＴ係数が異なってしまう問題がある。
【０００５】
従って、本発明はバタフライ演算結果のばらつきが小さいサブブロックであっても、零係数が得られる否かを精度良く予測可能な動画像符号化装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一態様に係る動画像符号化装置は、ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成する予測部と；前記ブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力するバタフライ演算器と；前記ブロック単位のバタフライ演算結果を複数のサブブロックに分割し、サブブロック単位のバタフライ演算結果を出力する分割器と；前記サブブロック単位のバタフライ演算結果の絶対値和を算出する算出部と；前記絶対値和が閾値より大きければ、前記サブブロック単位のバタフライ演算結果に予め定められた行列を乗じ、直交変換係数を演算する行列演算部と；前記直交変換係数を量子化パラメータに従って量子化し、量子化直交変換係数を出力する量子化部と；前記絶対値和が前記閾値以下であれば零係数を設定する設定部と；前記量子化直交変換係数または前記零係数を符号化する符号化器と；を具備する。
【０００７】
本発明の他の態様に係る動画像符号化装置は、ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成する予測部と；前記ブロック単位の予測残差信号に対してバタフライ演算を行い、ブロック単位のバタフライ演算結果を出力するバタフライ演算器と；前記ブロック単位のバタフライ演算結果を複数のサブブロックに分割し、サブブロック単位のバタフライ演算結果を出力する分割器と；前記サブブロック単位のバタフライ演算結果の絶対値和を算出する算出部と；前記絶対値和が第１閾値より大きければ、前記サブブロック単位のバタフライ演算結果に予め定める行列を乗じ、第１直交変換係数を演算する第１の行列演算部と；前記第１直交変換係数を量子化パラメータに従って量子化し、第１量子化直交変換係数を出力する第１の量子化部と；前記絶対値和が前記第１閾値以下であってかつ第２閾値より大きければ、前記サブブロック単位のバタフライ演算結果のうち第１周波数領域に含まれる第１要素に前記行列を乗じ、前記第１周波数領域より高い第２周波数領域に含まれる第２要素に０を与えて、第２直交変換係数を演算する第２の行列演算部と；前記第１要素を前記量子化パラメータに従って量子化し、前記第２要素に０を与えて、第２量子化直交変換係数を出力する第２の量子化部と；前記絶対値和が前記第２閾値以下であれば零係数を設定する設定部と；前記第１直交変換係数、第２量子化直交変換係数または前記零係数を符号化する符号化器と；を具備する。
【０００８】
本発明の他の態様に係る動画像符号化装置は、ブロック単位の入力画像信号に対して動き補償予測を行い、ブロック単位の予測残差信号を生成する予測部と；前記ブロック単位の予測残差信号のうちの第１要素に対してバタフライ演算を行い、ブロック単位の部分的バタフライ演算結果を出力する第１の部分的バタフライ演算器と；前記ブロック単位の部分的バタフライ演算結果を複数のサブブロックに分割し、サブブロック単位の第１のバタフライ演算結果を出力する分割器と；前記サブブロック単位の第１のバタフライ演算結果の絶対値和を算出する算出部と；前記第１絶対値和が閾値より大きければ、前記予測残差信号のうちの第２要素にバタフライ演算を行ってサブブロック単位の第２のバタフライ演算結果を出力する第２の部分的バタフライ演算器と；前記サブブロック単位の第２のバタフライ演算結果に予め定める行列を乗じ、直交変換係数を演算する行列演算部と；前記直交変換係数を量子化パラメータに従って量子化し、量子化直交変換係数を出力する量子化部と；前記絶対値和が前記閾値以下であれば零係数を設定する設定部と；前記第１量子化直交変換係数または前記零係数を符号化する符号化器と；を具備する。
【発明の効果】
【０００９】
本発明によれば、バタフライ演算結果のばらつきが小さいサブブロックであっても、零係数が得られる否かを精度良く予測可能な動画像符号化装置を提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照して、本発明の実施形態について説明する。  
（第１の実施形態）  
図１に示すように、本発明の第１の実施形態に係る動画像符号化装置は、ブロックスキャン変換器１０１、イントラ予測器１０２、減算器１０３、動き検出器１０４、動き補償器１０５、減算器１０６、モード判定器１０７、選択器１０８、加算器１０９、フレームメモリ１１０、可変長符号化器１１１及び信号処理部１２０を有する。また、信号処理部１２０は、信号分割部１３０、直交変換・量子化部１４０及び逆量子化・逆直交変換部１５０を含む。
【００１１】
本実施形態に係る動画像符号化装置は、例えばISO/IEC13818-2(MPEG-2 Video)またはISO/IEC14496-2(MPEG-4 Video）などに準拠した符号化を行う。
【００１２】
ブロックスキャン変換器１０１は、入力画像信号１０をマクロブロック単位に分割する。ブロックスキャン変換器１０１によってマクロブロック単位に分割された入力画像信号（以下、単にブロック画像信号と称する）は、イントラ予測器１０２、減算器１０３、動き検出器１０４及び減算器１０６に渡される。
【００１３】
イントラ予測器１０２は、ブロックスキャン変換器１０１からのブロック画像信号について周囲の符号化済みのブロックからイントラ予測を行う。イントラ予測器１０２は、上記イントラ予測結果をイントラ予測信号として、減算器１０３及び選択器１０８に渡す。
【００１４】
減算器１０３は、ブロックスキャン変換器１０１からのブロック画像信号及びイントラ予測器１０２からのイントラ予測画像信号の差分を算出する。上記差分は、イントラ予測残差信号としてモード判定器１０７に渡される。
【００１５】
動き検出器１０４は、ブロックスキャン変換器１０１からのブロック画像信号及びフレームメモリ１１０からの参照画像信号との間の動きを示す動きベクトルを検出し、動き補償器１０５に渡す。
【００１６】
動き補償器１０５は、動き検出器１０４からの動きベクトルを用いてフレームメモリ１１０からの参照画像信号を動き補償する。動き補償器１０５は、動き補償器１０５は、上記動き補償結果をインター予測画像信号として、減算器１０６及び選択器１０８に渡す。
【００１７】
減算器１０６は、ブロックスキャン変換器１０１からのブロック画像信号及び動き補償器１０５からのインター予測画像信号の差分を算出する。上記差分は、インター予測残差信号としてモード判定器１０７に渡される。
【００１８】
モード判定器１０７は、減算器１０３からのイントラ予測残差信号及び減算器１０６からのイントラ予測残差信号に関して、符号化コストを比較するなどして符号化対象として最適な予測モードを判定する。モード判定器１０７は、上記最適な予測モードに対応する予測残差信号１１を信号処理部１２０に渡す。また、モード判定器１０７は、最適な予測モードを示すモード情報１２を選択器１０８及び直交変換・量子化部１４０に渡す。
【００１９】
選択器１０８は、モード判定器１０７からのモード情報１２に従って、イントラ予測器１０２からのイントラ予測画像信号及び動き補償器１０５からのインター予測画像信号ののうちモード判定器１０７によって判定された最適な予測モードに対応する一方を選択する。選択器１０８によって選択された予測画像信号は、加算器１０９に渡される。
【００２０】
加算器１０９は、選択器１０８からの予測画像信号及び逆量子化・逆直交変換部１５０からの復号予測残差信号を加算し、局所復号画像としてフレームメモリ１１０に渡す。
【００２１】
フレームメモリ１１０は、加算器１０９からの局所復号画像信号が参照画像信号として保存される。尚、フレームメモリ１１０の前段にデブロッキングフィルタを設けることにより、局所復号画像信号からブロック歪を除去してもよい。
【００２２】
信号処理部１２０では、信号分割部１３０がモード判定器１０７にて選択された予測残差信号１１をサブブロック単位に分割し、直交変換・量子化部１４０がサブブロック毎にＤＣＴなどの直交変換及び量子化を行う。直交変換・量子化部１４０は、量子化されたＤＣＴ係数（以下、単にＱＤＣＴ係数と称する）１４を可変長符号化器１１１及び逆量子化・逆直交変換部１５０に渡す。逆量子化・逆直交変換部１５０は、ＱＤＣＴ係数１４を逆量子化・逆直交変換して、復号予測残差信号１５として加算器１０９に渡す。
【００２３】
ここで、信号処理部１２０で行われる直交変換の一例として高速８×８ＤＣＴについて説明する。高速８×８ＤＣＴは、ＤＣＴを高速に行うためのアルゴリズムであって、ＤＣＴ変換行列の疎行列への分解を伴う。尚、疎行列分解に一意性は無く、分解のバリエーションは複数考えられるが、本実施形態ではバタフライ行列の分解を伴うのであれば、これ以外の疎行列の分解について特に限定しない。即ち、バタフライ行列以外の疎行列を以下に示す手法とは異なる手法で分解したとしても本実施形態は適用可能である。まず、説明の簡略化のため、以下に８×１ＤＣＴを示す。
【数１】
2009021802.tif 000003
【００２４】
ここで、ｙは８×１のＤＣＴ係数ベクトルを、Ｃは８×１ＤＣＴ変換行列を、ｘは８×１データベクトルを夫々示している。また、Ｐは８×８の置換行列、Ｂは８×８バタフライ行列、Ｄは以下の疎行列を夫々示している。
【数２】
2009021802.tif 000004
【００２５】
ここで、Φ及びΨは夫々４×４行列を示している。
【００２６】
次に、上記数式（１）と同様に８×８ＤＣＴに関する疎行列分解式を示す。  
【数３】
2009021802.tif 000005
【００２７】
ここで、Ｙは８×８ＤＣＴ係数行列、Ｘは８×８データ行列を示している。その他のＣ，Ｐ，Ｄ及びＢは数式（１）及び（２）で示した行列と同様である。また、添え字のＴは行列の転置を示している。以上のように、８×８ＤＣＴ係数行列Ｙは、８×８データ行列Ｘとバタフライ行列及びその他の疎行列の行列演算によって導出される。
【００２８】
以下、図２を用いて信号処理部１２０中の信号分割部１３０、直交変換・量子化部１４０及び逆量子化・逆直交変換部１５０について詳しく説明する。  
信号分割部１３０は、図２に示すようにバタフライ演算器１３１及びサブブロック分割器１３２を含む。
【００２９】
バタフライ演算器１３１は、モード判定器１０７から取得した予測残差信号１１に８×８の矩形領域（以下、単にブロックと称する）単位で８×８バタフライ演算を行い、６４個の演算結果をサブブロック分割器１３２に渡す。ここで、８×８バタフライ演算について説明する。
【００３０】
８×８バタフライ演算は、数式（３）に示した８×８ＤＣＴの途中演算であり、より具体的には数式（３）中のＢＸＢTの演算である。従って、バタフライ演算器１３１は８×８行列の行列演算を行うわけであるが、ここでは数式（１）における８×８バタフライ行列Ｂ及び８×１データベクトルｘの積Ｂｘについて説明する。
【数４】
2009021802.tif 000006
【００３１】
以上のように、８×１バタフライ演算結果Ｂｘの要素は、８×１データベクトルｘから選択された２つの要素を加算または減算することにより求めることができる。  
同様に、数式（３）における８×８バタフライ演算結果ＢＸＢTの要素は、８×８データ行列Ｘから選択された４つの要素を加算または減算することにより求めることができる。
【００３２】
サブブロック分割器１３２は、バタフライ演算器１３１から渡された６４個のバタフライ演算結果を４つのサブブロックに分割し、サブブロック単位で直交変換・量子化部１４０に夫々渡す。ここでサブブロック分割器１３２の行う分割について説明する。前述のようにバタフライ演算器１３１からのバタフライ演算結果は、８×８データ行列Ｘから選択された４つの要素を加算または減算することにより求められるが、この加算または減算のいずれを行うかによって演算結果を分割することができる。この分割に関して、まずバタフライ演算ＢＸＢTの途中演算であるＢＸについて考える。
【００３３】
ここで、説明の簡単のため８×８行列のうち、第１行第１列から第４行第４列までの４×４行列を左上部分行列、第１行第５列から第４行第８列までの４×４行列を右上部分行列、第５行第１列から第８行第４列までの４×４行列を左下部分行列、第５行第５列から第８行第８列までの４×４行列を右下部分行列と定義する。
【００３４】
このとき、途中演算結果ＢＸの左上部分行列は８×８データ行列Ｘの左上部分行列及び左下部分行列の要素の加算により求められる。途中演算結果ＢＸの右上部分行列は、８×８データ行列Ｘの右上部分行列及び右下部分行列の加算により求められる。途中演算結果ＢＸの左下部分行列は８×８データ行列Ｘの左上部分行列及び左下部分行列の要素の減算により求められる。途中演算結果ＢＸの右下部分行列は８×８データ行列Ｘの右上部分行列及び右下部分行列の要素の減算により求められる。以下、この途中演算ＢＸを垂直方向の演算と定義する。次にバタフライ演算ＢＸＢTの途中演算であるＸＢTについて考える。
【００３５】
途中演算結果ＸＢTの左上部分行列は、８×８データ行列Ｘの左上部分行列及び右上部分行列の加算により求められる。途中演算結果ＸＢTの右上部分行列は、８×８データ行列Ｘの左上部分行列及び右上部分行列の減算により求められる。途中演算結果ＸＢTの左下部分行列は、８×８データ行列Ｘの左下部分行列及び右下部分行列の加算により求められる。途中演算結果ＸＢTの右下部分行列は、８×８データ行列Ｘの左下部分行列及び右下部分行列の減算により求められる。以下、この途中演算ＸＢTを水平方向の演算と定義する。
【００３６】
以上より、バタフライ演算結果ＢＸＢTの左上部分行列は、８×８データ行列Ｘの垂直方向の加算及び水平方向の加算により求められる。バタフライ演算結果ＢＸＢTの右上部分行列は、８×８データ行列Ｘの垂直方向の加算及び水平方向の減算により求められる。バタフライ演算結果ＢＸＢTの左下部分行列は、８×８データ行列Ｘの垂直方向の減算及び水平方向の加算により求められる。バタフライ演算結果ＢＸＢTの右下部分行列は、８×８データ行列Ｘの垂直方向の減算及び水平方向の減算により求められる。このように、バタフライ演算結果ＢＸＢTは垂直方向及び水平方向に加算または減算のいずれが行われたかによって分類できる。即ち、バタフライ演算結果ＢＸＢTの左上部分行列をＧ1、バタフライ演算結果ＢＸＢTの右上部分行列をＧ2、バタフライ演算結果ＢＸＢTの左下部分行列をＧ3、バタフライ演算結果ＢＸＢTの右下部分行列をＧ4とすると、バタフライ演算結果ＢＸＢTは以下のように表すことができる。
【数５】
2009021802.tif 000007
【００３７】
各部分行列Ｇは、８×８ＤＣＴの残りの演算において互いに影響を与えないため、これらを独立に扱うことができる。サブブロック分割器１３２はこれら各部分行列Ｇをサブブロックとして直交変換・量子化部１４０に渡す。ここで、各部分行列Ｇが独立に扱えることを示す。数式（２）、（３）及び（５）より、８×８ＤＣＴ係数行列Ｙは以下のように表すことができる。
【数６】
2009021802.tif 000008
【００３８】
尚、Ｐは置換行列であるから、各演算結果ΦＧ1ΦT、ΦＧ2ΨT、ΨＧ3ΦT及びΨＧ4ΨTの並び替えは行われるものの、値は保存される。以上より、各部分行列Ｇが互いに影響を与えないことがわかる。
【００３９】
ここで、図４を用いて置換行列ＰによるＱＤＣＴ係数の並び替えについて説明する。図４左のブロックを構成する各小ブロックは置換前の８×８ＱＤＣＴ係数行列、即ち、数式（３）に示す行列ＤＢＸＢTＤTの量子化後の要素を示し、上記小ブロック中の数字ｉｊが、上記行列の第ｉ行第ｊ列目の要素に対応している。この置換前の８×８ＱＤＣＴ係数行列に置換行列Ｐを左右から乗じると、図４右に示すブロックが得られる。図４右において横軸が水平方向周波数ｈｆ、縦軸が垂直方向周波数ｖｆを夫々示している。尚、図４右に示すブロックにおいて、水平及び垂直方向周波数の低い４×４のサブブロックを周波数領域Ａのサブブロックとし、これ以外のサブブロックを周波数領域Ｂのサブブロックとする。即ち、置換前の各サブブロックには、周波数領域Ａの要素が４個、周波数領域Ｂの要素が１２個含まれている。具体的には、各サブブロックにおいて、第１行第１列、第１行第３列、第３行第１列及び第３行第３列目の要素が、周波数領域Ａに含まれる。
【００４０】
直交変換・量子化部１４０は、図２に示すように閾値生成部１４１、絶対値和算出部１４２、比較部１４３、選択器１４４、第１行列演算部１４５、第１量子化部１４６、第２行列演算部１４７、第２量子化部１４８及び零係数設定部１４９を含む。尚、ここで直交変換・量子化部１４０及び逆量子化・逆直交変換部１５０は、サブブロック単位で並列的に処理を行うために複数用意しておいてもよい。
【００４１】
閾値生成部１４１は、ブロックの信号種別（色コンポーネント情報）、モード判定器１０７からのモード情報１２及び量子化パラメータ１３を用いて第１閾値th1及び第２閾値th2（＞th1）を算出し、比較部１４３に渡す。閾値生成部１４１は、例えば以下の式に従って第１閾値th1及び第２閾値th2を算出する。
【数７】
2009021802.tif 000009
【００４２】
ここで、mode∈｛intra, inter｝、comp∈｛luma, chroma｝であり、α1及びα2（α1＜α2）は比例定数、qscaleは量子化パラメータを夫々表す。また、offset1及びoffset2はオフセットであり、任意に設定できるパラメタである。閾値生成部１４１はモード判定器１０７からのモード情報１２を参照し、予測モードがイントラであればβintra、インターであればβinterをβmodeに夫々適用する。一般に、イントラ予測に比べてインター予測はＤＣＴ係数の絶対値が小さくなる傾向にあるため、βintra＞βinterとする。また、閾値生成部１４１は、ブロックが輝度信号であればγluma、色差信号であればγchromaをγcompに夫々適用する。一般に、色差信号は輝度信号に比べて振幅が小さく、ＤＣＴ係数も小さくなる傾向があるため、γluma＞γchromaとして、色差信号の過剰な演算打ち切りを避けている。
【００４３】
絶対値和算出部１４２は、サブブロック分割器１３２からのサブブロックに含まれる１６個のバタフライ演算結果の絶対値和を算出し、比較部１４３に渡す。ここで、零係数が得られるサブブロックを予測するための指標として絶対値和を用いる技術的意義について説明する。
【００４４】
まず、バタフライ演算結果の最大絶対値を指標として用いる場合の問題点について簡単な例を示して説明する。図３Ａは、４×１データベクトルｘ＝｛ｘ0，ｘ1，ｘ2，ｘ3｝に４×４バタフライ演算を行って、バタフライ演算結果ｂ＝｛ｂ1，ｂ2，ｂ3，ｂ4｝を導出し、更に４×１ＤＣＴ係数ベクトルｙ＝｛ｙ1，ｙ2，ｙ3，ｙ4｝を導出するまでの４×１ＤＣＴの演算過程を示している。尚、図３Ａにおいてバタフライ演算結果ｂ0及びｂ1をサブブロック１、ｂ2及びｂ3をサブブロック２として夫々扱うが、以降の説明ではサブブロック１の説明のみを行い、サブブロック２の説明を省略する。
【００４５】
４×１データベクトルとしてｘ＝｛ｈ，ｈ／２，ｈ／２，ｈ｝を与えた場合のバタフライ演算結果は、図３Ｂに示すようにｂ0＝２ｈ，ｂ1＝ｈとなり、ＤＣＴ係数はｙ0＝３ｈ／√２，ｙ1＝ｈ／√２となる。上記例において、バタフライ演算結果の最大絶対値ＭＡＸは２ｈである。
【００４６】
一方、４×１データベクトルとしてｘ＝｛ｈ，０，０，ｈ｝を与えた場合のバタフライ演算結果は、図３Ｃに示すようにｂ0＝２ｈ，ｂ1＝０となり、ＤＣＴ係数はｙ0＝√２ｈ，ｙ1＝√２ｈとなる。図３Ｂに示した例と同様、バタフライ演算結果の最大絶対値ＭＡＸは２ｈである。
【００４７】
以上のように、バタフライ演算結果の最大絶対値とＤＣＴ係数との相関は高いとは必ずしもいえない。具体的には、画像信号では低周波数成分のパワーを予測することが重要であるが、上記２例では指標となる値ＭＡＸが同じであるにも係わらず図３Ｂに示した低周波成分ｙ0は図３Ｃに示した低周波成分ｙ0よりも５０％も大きい。このように、零係数を予測する指標にバタフライ演算結果の最大絶対値を用いる場合、ＤＣＴ係数の予測に残りの演算結果を考慮しないため、最大絶対値が小さく演算結果のばらつきが小さなサブブロックについて零係数であると誤って予測するおそれがある。このような予測誤りは符号化品質の低下を招く。
【００４８】
一方、零係数を予測する指標として絶対値和を用いれば、サブブロック内のバタフライ演算結果のばらつきが小さい場合であっても零係数を精度良く予測できる。例えば図３Ｂに示す例であれば絶対値和は３ｈ、図３Ｃに示す例であれば絶対値和は２ｈとなり、前述した最大絶対値を用いる場合に比べて低周波成分ｙ0との相関が高いといえる。また、絶対値和を計算する場合も、最大絶対値を計算する場合も全てのバタフライ演算結果を参照しなければならないため、計算量は１次のオーダーとなる。
【００４９】
比較部１４３は、絶対値和算出部１４２からの絶対値和と閾値生成部１４１からの２つの閾値とを比較し、比較結果を選択器１４４に通知する。即ち、比較部１４３は絶対値和と２つの閾値とを大小比較して、絶対値和が第１閾値th1以下（以下、単に第１状態と称する）、第１閾値th1より大きく第２閾値th2以下（以下、単に第２状態と称する）または第２閾値th2より大きい（以下、単に第３状態と称する）のいずれであるかを検出する。
【００５０】
選択器１４４は、比較部１４３より通知された比較結果に基づいて、サブブロック分割器１３２から受けたサブブロック単位のバタフライ演算結果を第１行列演算部１４５、第２行列演算部１４７または零係数設定部１４９のいずれか１つに渡す。具体的には、選択器１４４は、絶対値和が第１状態であればサブブロックを零係数設定部１４９に渡し、絶対値和が第２状態であればサブブロックを第２行列演算部１４７に渡し、絶対値和が第３状態であればサブブロックを第１行列演算部１４５に渡す。
【００５１】
第１行列演算部１４５は、８×８疎行列Ｄの４×４部分行列ΦまたはΨを与えられた部分行列Ｇに左右から乗じ、演算結果を第１量子化部１４６に渡す。第１行列演算部１４５は、具体的には数式（６）から置換行列Ｐ及びこれの転置行列を除いた演算部分における、各要素の行列演算を行う。即ち、第１行列演算部１４５は、数式（３）に示すＤＢＸＢTＤTを４分割して行っている。
【００５２】
第１量子化部１４６は、量子化パラメータ１３に従って、第１行列演算部１４５からの演算結果を量子化し、ＱＤＣＴ係数１４として可変長符号化器１１１及び第１逆量子化部１５１に渡す。
【００５３】
第２行列演算部１４７は、与えられた部分行列Ｇのうち一部の要素についてのみ第１行列演算部１４５と同様の演算を行う。具体的には前述した各部分行列Ｇのうち、前述した周波数領域Ａの要素についてのみ第１行列演算部１４５と同様の演算を行い、周波数領域Ｂの要素には０を与え、行列演算を省略する。即ち、第２行列演算部１４７は、パワーが大きくなりやすい低周波成分（周波数領域Ａ）の要素のみ行列演算を行い、パワーが小さくなりやすい高周波成分（周波数領域Ｂ）の要素は０と予測することで計算量を節約している。第２行列演算部１４７は以上のような演算結果を第２量子化部１４８に渡す。
【００５４】
第２量子化部１４８は、第１量子化部１４６と同様に、第２行列演算部１４７からの演算結果を量子化パラメータ１３に従って量子化する。但し、前述したように第２行列演算部１４７では、周波数領域Ａの要素についてのみ行列演算が行われ、周波数領域Ｂの要素については機械的に０が与えられているため、第２量子化部１４８は実質的には周波数領域Ａの要素についてのみ量子化を行う。第２量子化部１４８は上記量子化結果を、ＱＤＣＴ係数１４として可変長符号化器１１１及び第２逆量子化部１５３に渡す。
【００５５】
零係数設定部１４９は、部分行列Ｇの全ての要素に対して行列演算を行わず、与えられたサブブロックは零係数となると予測し、零行列をＱＤＣＴ係数１４として可変長符号化器１１１に出力し、行列演算結果として信号結合部１５５に出力する。
【００５６】
可変長符号化器１１１は、前述のようにサブブロック単位で第１量子化部１４６、第２量子化部１４８または零係数設定部１４９のいずれかからＱＤＣＴ係数１４を受け、これらを結合して置換前の８×８ＱＤＣＴ係数行列を生成し、置換行列を左右から乗じて８×８ＱＤＣＴ係数行列を導出する。可変長符号化器１１１は上記８×８ＱＤＣＴ係数行列に可変長符号化を行って、符号化ビットストリーム１６を出力する。また、可変長符号化器１１１は、動き検出部１０４によって検出された動きベクトルを含む動き補償パラメタ及びモード判定器１０７によって判定された予測モードを示すモード情報などのサイド情報に対しても符号化を行い、上記符号化ビットストリーム１６に付加して出力する。尚、可変長符号化器１１１は、算術符号化など他のエントロピー符号化を行ってもよい。
【００５７】
逆量子化・逆直交変換部１５０は、図２に示すように第１逆量子化部１５１、第１逆直交変換部１５２、第２逆量子化部１５３、第２逆直交変換部１５４及び信号結合部１５５を含む。
【００５８】
第１逆量子化部１５１は、第１量子化部１４６からのＱＤＣＴ係数１４を、量子化パラメータ１３に従って逆量子化し、復号ＤＣＴ係数として第１逆直交変換部１５２に渡す。第１逆直交変換部１５２は、第１逆量子化部１５１からの復号ＤＣＴ係数に逆直交変換を行う。具体的には、復号ＤＣＴ係数に対して、第１行列演算部１４５で乗じられた部分行列ΦまたはΨの逆行列を左右から乗じる。第１逆直交変換部１５２は行列演算結果を信号結合部１５５に渡す。
【００５９】
第２逆量子化部１５３は、第２量子化部１４８からのＱＤＣＴ係数１４を、量子化パラメータ１３に従って所定の逆量子化を行い、復号ＤＣＴ係数として第２逆直交変換部１５４に渡す。具体的には、前述したようにＱＤＣＴ係数１４のうち、第２量子化部１４８で量子化された周波数領域Ａの４個の要素のみ逆量子化を行い、周波数領域Ｂの１２個の要素については０を与えてＤＣＴ係数を復号する。
【００６０】
第２逆直交変換部１５４は、第２逆量子化部１５３からの復号ＤＣＴ係数に所定の逆直交変換を行う。具体的には、第２復号ＤＣＴ係数に対して、第２行列演算部１４７で乗じられた部分行列ΦまたはΨの逆行列を左右から乗じ、前述した周波数領域Ａの４個の要素のみ演算を行い、周波数領域Ｂの１２個の要素については実際には演算を行わずに０を与える。第２逆直交変換部１５４は行列演算結果を信号結合部１５５に渡す。
【００６１】
信号結合部１５５は、前述のようにサブブロック単位で第１逆直交変換部１５２、第２逆直交変換部１５４または零係数設定部１４９のいずれかから行列演算結果を受け、これらを結合し、バタフライ行列Ｂの逆行列を左右から乗じて予測残差信号を復号して、復号予測残差信号１５として加算器１０９に渡す。
【００６２】
以下、図５に示すフローチャートを用いて、図２に示す信号処理部１２０の動作について説明する。  
まず、バタフライ演算器１３１が、モード判定器１０７から取得した予測残差信号１１をブロック単位で８×８バタフライ演算を行う（ステップＳ２０１）。次に、サブブロック分割器１３２が、ステップＳ２０１における演算結果を４つのサブブロックに分割する（ステップＳ２０２）。次に、絶対値和算出部１４２が、ステップＳ２０２で分割された各サブブロック中の１６個のバタフライ演算結果の絶対値和を算出する（ステップＳ２０３）。次に、比較部１４３が、ステップＳ２０３で算出された絶対値和と第１閾値th1を比較する（ステップＳ２０４）。絶対値和が第１閾値th1以下であれば処理はステップＳ２０５に進み、絶対値和が第１閾値th1より大きければ処理はステップＳ２０８に進む。
【００６３】
ステップＳ２０５では、零係数設定部１４９が処理対象のサブブロック全ての要素について零係数であると予測する。次に、零係数設定部１４９は零行列をＱＤＣＴ係数１４として可変長符号化器１１１に出力し、行列演算結果として信号結合部１５５へ出力する（ステップＳ２０６）。次に、信号結合部１５５はステップＳ２０６、ステップＳ２１３またはステップＳ２１７のいずれかで行われたサブブロックに関する行列演算結果を結合して、バタフライ行列Ｂの逆行列を左右から乗じて予測残差信号を復号し、復号予測残差信号１５として加算器１０９へと出力し（ステップＳ２０７）、信号処理部１２０の動作が終了する。
【００６４】
ステップＳ２０８では、比較部１４３がステップＳ２０３で算出された絶対値和と第２閾値th2を比較する。絶対値和が第２閾値th2以下であれば処理はステップＳ２０９へと進み、絶対値和が第２閾値th2より大きければ処理はステップＳ２１４に進む。
【００６５】
ステップＳ２０９では、第２行列演算部１４７がステップＳ２０２で分割されたサブブロック単位のバタフライ演算結果に対して疎行列Ｄの部分行列ΦまたはΨを乗じ、周波数領域Ａの要素についてのみ行列演算を行い、周波数領域Ｂの要素については０を設定して上記行列演算を打ち切る。次に、第２量子化部１４８は、ステップＳ２０９での演算結果に量子化パラメータ１３を用いて所定の量子化を行い、ＱＤＣＴ係数１４を生成する（ステップＳ２１０）。第２量子化部１４８は具体的には、ステップＳ２０９での演算結果のうち周波数領域Ａの要素を量子化パラメータ１３に従って量子化し、周波数領域Ｂの要素を０とする部分的な量子化を行い、ＱＤＣＴ係数１４を生成する。次に、第２量子化部１４８はステップＳ２１０で生成されたＱＤＣＴ係数１４を可変長符号化器１１１及び第２逆量子化部１５３へと出力する（ステップＳ２１１）。
【００６６】
次に、第２逆量子化部１５３は、ステップＳ２１０で生成されたＱＤＣＴ係数１４に量子化パラメータ１３を用いて所定の逆量子化を行い、ＤＣＴ係数を復号する（ステップＳ２１２）。第２逆量子化部１５３は具体的には、ステップＳ２１０で生成されたＱＤＣＴ係数１４のうち周波数領域Ａの要素を逆量子化し、周波数領域Ｂの要素を０としてＤＣＴ係数を復号する。次に、第２逆直交変換部１５４は、ステップＳ２１２で復号されたＤＣＴ係数に逆直交変換、具体的にはステップＳ２０９で乗じた行列の逆行列を左右から乗じ、周波数領域Ａの要素についてのみ行列演算を行い、周波数領域Ｂの要素については０を与えて上記行列演算を打ち切る。第２逆直交変換部１５４は、この行列演算結果を信号結合部１５５に出力し、処理はステップＳ２０７へと進む（ステップＳ２１３）。
【００６７】
ステップＳ２１４では、第１行列演算部１４５がステップＳ２０２で分割されたサブブロック単位のバタフライ演算結果に、疎行列Ｄの部分行列ΦまたはΨを乗じる行列演算を行う。次に、第１量子化部１４６は、ステップＳ２１４での行列演算結果に量子化パラメータ１３を用いて量子化を行い、ＱＤＣＴ係数１４を生成する（ステップＳ２１５）。次に、第１量子化部１４６はステップＳ２１５で生成されたＱＤＣＴ係数１４を可変長符号化器１１１及び第１逆量子化部１５１へと出力する（ステップＳ２１６）。
【００６８】
次に、第１逆量子化部１５１は、ステップＳ２１４で生成されたＱＤＣＴ係数１４に量子化パラメータ１３を用いて逆量子化を行い、ＤＣＴ係数を復号する（ステップＳ２１７）。次に、第１逆直交変換部１５２は、ステップＳ２１７で復号されたＤＣＴ係数に逆直交変換、具体的には、ステップＳ２１４で乗じた行列の逆行列を左右から乗じ、この行列演算結果を信号結合部１５５に出力し、処理はステップＳ２０７へと進む（ステップＳ２１８）。
【００６９】
以上説明したように本実施形態に係る動画像符号化装置では、バタフライ演算結果のサブブロック単位での絶対値和を指標として零係数を予測し、直交変換及び量子化を行うか否かを決定している。従って、本実施形態に係る動画像符号化装置によれば、バタフライ演算結果のばらつきが小さいサブブロックであっても、零係数が得られる否かを精度良く予測できるため、符号化品質が向上する。また、計算量の観点でも、バタフライ演算結果のサブブロック単位での最大絶対値を指標として用いる従来手法と同じく、１次のオーダーである。
【００７０】
（第２の実施形態）  
本発明の第２の実施形態に係る動画像符号化装置は、上記図１に示す動画像符号化装置において、信号処理部１２０を信号処理部３２０に置き換えている。以下の説明では、図１と同一部分には同一符号を付して示し、異なる部分を中心に述べる。
【００７１】
図６に示すように、本実施形態に係る動画像符号化装置における信号処理部３２０は、信号分割部３３０、直交変換・逆直交変換部３４０及び逆量子化・逆直交変換部１５０を有する。
【００７２】
信号分割部３３０は、第１の部分的バタフライ演算器３３１及びサブブロック分割器１３２を含み、モード判定器１０７から取得した予測残差信号１１に部分的な８×８バタフライ演算を行い、上記部分的なバタフライ演算結果をサブブロック単位に分割し、直交変換・逆直交変換部３４０へ渡す。
【００７３】
第１の部分的バタフライ演算器３３１は、モード判定器１０７から取得した予測残差信号にブロック単位で第１の部分的バタフライ演算を行う。ここで、第１の部分的バタフライ演算について説明する。第１の部分的バタフライ演算では、ブロックの一部の要素についてのみ８×８バタフライ演算が行われ、それ以外の要素についての８×８バタフライ演算は省略される。具体的には、図７に示す白抜き部分の８×８バタフライ演算が省略され、それ以外の要素のみ８×８バタフライ演算が行われる。
【００７４】
以下、この白抜き部分の選択について詳細に説明する。前述したように画像信号において低周波数成分のパワーが大きいため、低周波成分に寄与する要素のバタフライ演算結果のみを用いて零係数の予測を行っても、全ての要素のバタフライ演算結果を用いて予測を行う場合と比べて予測精度はほとんど損なわれない。そこで、本実施形態に係る動画像符号化装置では、加減算のみで行われる簡単な直交変換として知られるアダマール変換の変換過程に着目し、低域成分に寄与する要素、即ち、図７に示す白抜き以外の部分を選択している。
【００７５】
まず、８×１アダマール変換について説明する。尚、行列のゲイン（係数）については本質的な問題でないため、以降の説明を省略する。８×１アダマール変換では、以下に示すように、８×１データベクトルｘが８×８アダマール行列Ｈによって変換される。
【数８】
2009021802.tif 000010
【００７６】
このように、８×８アダマール行列Ｈは置換行列Ｐ、Ｈ1及びＨ2を要素とする疎行列及びバタフライ行列Ｂの積に分解することができる。尚、ここで上記疎行列の要素Ｈ1及びＨ2は以下の通りである。また、置換行列Ｐ及びバタフライ行列Ｂについては前述した数式（１）で用いたものと同じ行列を表す。
【数９】
2009021802.tif 000011
【００７７】
次に、８×８アダマール変換について説明する。８×８アダマール変換では以下に示すように、８×８データ行列Ｘがアダマール行列Ｈによって変換される。
【数１０】
2009021802.tif 000012
【００７８】
数式（１０）より、８×８アダマール変換は、各部分行列Ｇに対する４×４アダマール行列Ｈ1及びＨ2の乗算によって独立に行うことができる。また、置換行列Ｐの乗算により要素の並び替えが生じるため、各部分行列Ｇに対する４×４アダマール変換結果の低周波成分は８×８アダマール変換の低周波成分に対応する。
【００７９】
まず、各サブブロックのもっとも低域にある周波数成分、即ち図４における００，０４，４０及び４４（以下、単にlowfreq1と称する）について考える。
【００８０】
各サブブロックのlowfreq1は、数式（１０）より、サブブロック１６個のバタフライ演算結果の総和により求められる。しかしながら、前述したように本実施形態では計算量削減のために、次のような近似を行う。具体的には、各部分行列Ｇの対角線上に存在する８個の要素の総和を２倍したものをlowfreq1として近似する。ここで、上記８個の要素を選んだ理由は、これら８個の要素を算出する際に使用される８×８データ行列Ｘの要素の空間的偏りが小さいためである。
【００８１】
次に、lowfreq1に次いで低い水平方向の周波数成分、即ち図４における０２，０６，４２及び４６（以下、単にlowfreq2hと称する）及びlowfreq1に次いで低い垂直方向の周波数成分、即ち図４における２０，２４，６０及び６４（以下、単にlowfreq2vと称する）について併せて考える。
【００８２】
前述したように、アダマール変換は行列の要素の加減算によって実現され、lowfreq2h及びlowfreq2vは、各部分行列Ｇ1乃至Ｇ4の要素について図８に示すような符号を付して総和を算出することにより求められる。例えば部分行列Ｇ１におけるlowfreq2hであれば、図８に示すように左半分の８個の要素に＋の符号を付し、右半分の８個要素に−の符号を付してこれら１６個の要素の総和を算出することにより求められる。一方、部分行列Ｇ1におけるlowfreq2vは、上半分の８個の要素に＋の符号を付し、下半分の８個の要素に−の符号を付してこれら１６個の総和を算出することにより求められる。
【００８３】
これらlowfreq2h及びlowfreq2vの近似計算は、図８に示した各部分行列Ｇの要素に対して付与する符号の共通部分のみを用いて行われる。即ち、前述した部分行列Ｇ1であれば、lowfreq2h及びlowfreq2vは左上部分の４個の要素に＋の符号を付し、右下部分の４個の要素に−の符号を付した総和を２倍した値を近似値とする。その他の部分行列Ｇ２乃至Ｇ４についても同様、１６個の要素のうち８個の要素のみを用いて近似計算が行われる。
【００８４】
ここで、図８に示した符号の共通部分の要素のみを近似計算に用いた理由は、以下の２つの条件を満たすからである。
【００８５】
（ａ）lowfreq1及びlowfreq2の近似計算に用いられる要素において、＋の符号が付与される要素と−の符号が付与される要素の数が同数である。
【００８６】
（ｂ）上記近似計算に用いられる要素において、元のデータ行列Ｘでの要素の空間的偏りが小さい。
【００８７】
以上説明したように、第１の部分的バタフライ演算器３３１は上記lowfreq1及びlowfreq2を近似計算する際に用いる要素のみの８×８バタフライ演算を行う。具体的には、図９において影付で示した要素についてのみ８×８バタフライ演算を行う。
【００８８】
直交変換・逆直交変換部３４０は、閾値生成部３４１、絶対値和算出部３４２、比較部３４３、選択器３４４、第２の部分的バタフライ演算器３４５、絶対値和算出部３４６、比較部３４７、選択器３４８、第１行列演算部１４５、第１量子化部１４６、第２行列演算部１４７、第２量子化部１４８及び零係数設定部１４９を含む。
【００８９】
閾値生成部３４１は、ブロックの信号種別（色コンポーネント情報）、モード判定器１０７からのモード情報１２及び量子化パラメータ１３を用いて第３閾値th3及び第４閾値th4（＞th3）を算出し、比較部１４３に渡す。閾値生成部１４１は、例えば以下の式に従って第３閾値th3及び第４閾値th4を算出する。
【数１１】
2009021802.tif 000013
【００９０】
ここで、α1、α2、βmode、γcomp、offset1、offset2及びqscaleは、数式（７）で用いたものと同様である。また、ε1及びε2は、比例定数であり、ε1＜ε2の関係がある。
【００９１】
絶対値和算出部３４２は、サブブロック分割器１３２からサブブロック単位で部分的バタフライ演算結果を受け、１２個のバタフライ演算結果の第１絶対値和を算出し、比較部３４３に渡す。比較部３４３は、絶対値和算出部３４２からの第１絶対値和と閾値生成部３４１からの第３閾値th3とを比較し、比較結果を選択器３４４に通知する。
【００９２】
選択器３４４は、比較部３４３からの比較結果を参照し、第１絶対値和が第３閾値th3以下であればサブブロックを零係数設定部１４９に渡し、第１絶対値和が第３閾値th3より大きければサブブロックを第２の部分的バタフライ演算器３４５に渡す。
【００９３】
第２の部分的バタフライ演算器３４５は、第１の部分的バタフライ演算器３３１で８×８バタフライ演算が行われなかった４つの要素について８×８バタフライ演算を行う。即ち、第２の部分的バタフライ演算器３４５によって、各サブブロックの全ての要素についての８×８バタフライ演算が完了する。第２の部分的バタフライ演算器３４５は、サブブロックを絶対値和算出部３４６及び選択器３４８に渡す。
【００９４】
絶対値和算出部３４６は、第２の部分的バタフライ演算器３４５からサブブロック単位でバタフライ演算結果を受け、１６個のバタフライ演算結果の第２絶対値和を算出し、比較部３４７に渡す。比較部３４７は、絶対値和算出部３４６からの第２絶対値和と閾値生成部３４１からの第４閾値th4とを比較し、比較結果を選択器３４８に通知する。
【００９５】
選択器３４８は、比較部３４７からの比較結果を参照し、第２絶対値和が第４閾値th4以下であればサブブロックを第２行列演算部１４７に渡し、第２絶対値和が第４閾値th4より大きければサブブロックを第１行列演算部１４５に渡す。
【００９６】
以下、図１０に示すフローチャートを用いて、図６に示す信号処理部２２０の動作について説明する。  
まず、第１の部分的バタフライ演算器３３１が、モード判定器１０７から取得した予測残差信号１１にブロック単位で部分的な８×８バタフライ演算を行う（ステップＳ４０１）。第１の部分的バタフライ演算器３３１は、具体的には前述したように図７において白抜きで示した要素以外について８×８バタフライ演算を行う。次に、サブブロック分割器１３２が、ステップＳ２０１における演算結果を４つのサブブロックに分割する（ステップＳ４０２）。次に、絶対値和算出部３４２が、ステップＳ４０２で分割された各サブブロック中の１２個のバタフライ演算結果の第１絶対値和を算出する（ステップＳ４０３）。次に、比較部３４３が、ステップＳ４０３で算出された第１絶対値和と第３閾値th3を比較する（ステップＳ４０４）。第１絶対値和が第３閾値th3以下であれば処理はステップＳ４０５に進み、第１絶対値和が第３閾値th3より大きければ処理はステップＳ４０７に進む。
【００９７】
ステップＳ４０５では、零係数設定部１４９が処理対象のサブブロック全ての要素について零係数であると予測する。次に、零係数設定部１４９は零行列をＱＤＣＴ係数１４として可変長符号化器１１１へ出力し、零行列を行列演算結果として信号結合部１５５へ出力する（ステップＳ４０６）。次に、信号結合部１５５はステップＳ４０６、ステップＳ４１４またはステップＳ４２０のいずれかで行われたサブブロックに関する行列演算結果を結合して、バタフライ行列Ｂの逆行列を左右から乗じて予測残差信号を復号し、復号予測残差信号１５として加算器１０９へと出力し（ステップＳ４１５）、信号処理部３２０の動作が終了する。
【００９８】
ステップＳ４０７では、第２の部分的バタフライ演算器３４５がステップＳ４０１で８×８バタフライ演算を省略した部分について８×８バタフライ演算を行う（ステップＳ４０７）。具体的には、第２の部分的バタフライ演算器３４５は図７において白抜きで示した要素について８×８バタフライ演算を行う。次に、絶対値和算出部３４６は、ステップＳ４０１及びステップＳ４０７で算出した１６個のバタフライ演算結果の第２絶対値和を算出する（ステップＳ４０８）。次に、比較部３４７が、ステップＳ４０８で算出された第２絶対値和と第４閾値th4を比較する（ステップＳ４０９）。第２絶対値和が第４閾値th4以下であれば処理はステップＳ４１０に進み、第２絶対値和が第４閾値th4より大きければ処理はステップＳ４１６に進む。
【００９９】
ステップＳ４１０では、第２行列演算部１４７がステップＳ４０１及びステップＳ４０７で算出されたサブブロック単位のバタフライ演算結果に対して疎行列Ｄの部分行列ΦまたはΨを乗じ、周波数領域Ａの要素についてのみ行列演算を行い、周波数領域Ｂの要素については０を設定して上記行列演算を打ち切る。次に、第２量子化部１４８は、ステップＳ４１０での演算結果に量子化パラメータ１３を用いて所定の量子化を行い、ＱＤＣＴ係数１４を生成する（ステップＳ４１１）。第２量子化部１４８は具体的には、ステップＳ４１０での演算結果のうち周波数領域Ａの要素を量子化パラメータ１３に従って量子化し、周波数領域Ｂの要素を０とする部分的な量子化を行い、ＱＤＣＴ係数１４を生成する。次に、第２量子化部１４８はステップＳ４１１で生成されたＱＤＣＴ係数１４を可変長符号化器１１１及び第２逆量子化部１５３へと出力する（ステップＳ４１２）。
【０１００】
次に、第２逆量子化部１５３は、ステップＳ４１１で生成されたＱＤＣＴ係数１４に量子化パラメータ１３を用いて所定の逆量子化を行い、ＤＣＴ係数を復号する（ステップＳ４１３）。第２逆量子化部１５３は具体的には、ステップＳ４１１で生成されたＱＤＣＴ係数１４のうち周波数領域Ａの要素を逆量子化し、周波数領域Ｂの要素を０としてＤＣＴ係数を復号する。次に、第２逆直交変換部１５４は、ステップＳ４１３で復号されたＤＣＴ係数に逆直交変換、具体的にはステップＳ４１０で乗じた行列の逆行列を左右から乗じ、周波数領域Ａの要素についてのみ行列演算を行い、周波数領域Ｂの要素については０を設定して上記行列演算を打ち切る。第２逆直交変換部１５４は、この行列演算結果を信号結合部１５５に出力し、処理はステップＳ４１５へと進む（ステップＳ４１４）。
【０１０１】
ステップＳ４１６では、第１行列演算部１４５がステップＳ４０１及びステップＳ４０７で算出されたサブブロック単位のバタフライ演算結果に、疎行列Ｄの部分行列ΦまたはΨを乗じる行列演算を行う。次に、第１量子化部１４６は、ステップＳ４１６での行列演算結果に量子化パラメータ１３を用いて量子化を行い、ＱＤＣＴ係数１４を生成する（ステップＳ４１７）。次に、第１量子化部１４６はステップＳ４１７で生成されたＱＤＣＴ係数１４を可変長符号化器１１１及び第１逆量子化部１５１へと出力する（ステップＳ４１８）。
【０１０２】
次に、第１逆量子化部１５１は、ステップＳ４１６で生成されたＱＤＣＴ係数１４に量子化パラメータ１３を用いて逆量子化を行い、ＤＣＴ係数を復号する（ステップＳ４１９）。次に、第１逆直交変換部１５２は、ステップＳ４１９で復号されたＤＣＴ係数に逆直交変換、具体的には、ステップＳ４１６で乗じた行列の逆行列を左右から乗じ、この行列演算結果を信号結合部１５５に出力し、処理はステップＳ４１５へと進む（ステップＳ４２０）。
【０１０３】
以上説明したように、本実施形態に係る動画像符号化装置では、バタフライ演算を２分割して行っており、零係数か否かを予測する際には１段階目のバタフライ演算結果のみを用いており、零係数が得られると予測する場合には２段階目のバタフライ演算を行わない。従って、本実施形態に係る動画像符号化装置によれば、バタフライ演算を一部省略することにより、計算量を削減することができる。
【０１０４】
なお、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また上記各実施形態に開示されている複数の構成要素を適宜組み合わせることによって種々の発明を形成できる。また例えば、各実施形態に示される全構成要素からいくつかの構成要素を削除した構成も考えられる。さらに、異なる実施形態に記載した構成要素を適宜組み合わせてもよい。
【０１０５】
その一例として例えば、上記各実施形態では、閾値を２つ設けてサブブロックに対する処理を３つに分岐して構成したが、閾値を１つだけ設けてサブブロックに対する処理を２に分岐しても同様の効果を得られる。図１１は７２０×４８０画素のサンプル画像の符号化を行った際の上記各実施形態及び従来例における省略ブロック数と歪み率（ＰＳＮＲ）の関係を示すグラフ図である。図１１中のＰＲＯＰＯＳＥ１は上記第１の実施形態を閾値１つのみで実施した場合、ＰＲＯＰＳＥ２は上記第２の実施形態を閾値１つのみで実施した場合、ＣＥＶＡは特許文献１記載の手法を閾値１つのみで実施した場合を夫々示している。例えば省略ブロック数が５０％程度になると、従来例に比べて上記各実施形態では０．１ｄＢ程度の歪み率の改善が見られる。
【０１０６】
また、上記各実施形態に係る動画像符号化装置では８×８ＤＣＴが行われているが、これに限定されるものでなく例えばＨ．２６４／ＡＶＣで行われる４×４ＤＣＴにも適用できる。
【０１０７】
その他、本発明の要旨を逸脱しない範囲で種々の変形を施しても同様に実施可能であることはいうまでもない。
【図面の簡単な説明】
【０１０８】
【図１】第１の実施形態に係る動画像符号化装置を示すブロック図。
【図２】図１における信号処理部を示すブロック図。
【図３Ａ】４×１ＤＣＴの演算過程を示すグラフ図。
【図３Ｂ】図３Ａに示すサブブロック１における演算結果の一例を示すグラフ図。
【図３Ｃ】図３Ａに示すサブブロック１における演算結果の一例を示すグラフ図。
【図４】置換行列による要素の並び替えを説明するための図。
【図５】図２に示す信号処理部の動作を示すフローチャート。
【図６】第２の実施形態に係る動画像符号化装置における信号処理部を示すブロック図。
【図７】図６における第１の部分的バタフライ演算器による部分的バタフライ演算を概念的に説明するための図。
【図８】lowfreq2h及びlowfreq2vの近似計算に用いられる要素の選択手法について説明するための図。
【図９】図７に示す部分的バタフライ演算が行われる要素の選択手法について説明するための図。
【図１０】図６に示す信号処理部の動作を示すフローチャート。
【図１１】第１及び第２の実施形態に係る動画像符号化装置による効果の一例を示すグラフ図。
【符号の説明】
【０１０９】
１０・・・・入力画像
１１・・・・予測残差信号
１２・・・・モード情報
１３・・・・量子化パラメータ
１４・・・・ＱＤＣＴ係数
１５・・・・復号予測残差信号
１６・・・・符号化ビットストリーム
１０１・・・ブロックスキャン変換器
１０２・・・イントラ予測器
１０３・・・減算器
１０４・・・動き検出器
１０５・・・動き補償器
１０６・・・減算器
１０７・・・モード判定器
１０８・・・選択器
１０９・・・加算器
１１０・・・フレームメモリ
１１１・・・可変長符号化器
１２０・・・信号処理部
１３０・・・信号分割部
１３１・・・バタフライ演算器
１３２・・・サブブロック分割器
１４０・・・直交変換・量子化部
１４１・・・閾値生成部
１４２・・・絶対値和算出部
１４３・・・比較部
１４４・・・選択器
１４５・・・第１行列演算部
１４６・・・第１量子化部
１４７・・・第２行列演算部
１４８・・・第２量子化部
１４９・・・零係数設定部
１５０・・・逆直交変換・逆量子化
１５１・・・第１逆量子化部
１５２・・・第１逆直交変換部
１５３・・・第２逆量子化部
１５４・・・第２逆直交変換部
１５５・・・信号結合部
３２０・・・信号処理部
３３０・・・信号分割部
３３１・・・第１の部分的バタフライ演算器
３４０・・・直交変換・量子化部
３４１・・・閾値生成部
３４２・・・絶対値和算出部
３４３・・・比較部
３４４・・・選択器
３４５・・・第２の部分的バタフライ演算器
３４６・・・絶対値和算出部
３４７・・・比較部
３４８・・・選択器
【図１】
2009021802.tif 000014
【図２】
2009021802.tif 000015
【図３Ａ】
2009021802.tif 000016
【図３Ｂ】
2009021802.tif 000017
【図３Ｃ】
2009021802.tif 000018
【図４】
2009021802.tif 000019
【図５】
2009021802.tif 000020
【図６】
2009021802.tif 000021
【図７】
2009021802.tif 000022
【図８】
2009021802.tif 000023
【図９】
2009021802.tif 000024
【図１０】
2009021802.tif 000025
【図１１】
2009021802.tif 000026