(57)【要約】【課題】画像・映像の信号に応じて最適な変換処理を適応的に自動生成する。【解決手段】入力画像信号を符号化する画像符号化装置は、遺伝的プログラミングを用いて、入力画像信号の符号化処理に用いる変換器の演算式を入力画像信号毎に適応構成して変換器データを出力する手段と、符号化処理における変換処理を変換器データにより置換して変換処理を行う手段と、符号化処理における逆変換処理を変換器データに対応する逆変換処理により置換して逆変換処理を行う手段と、入力画像信号を符号化し、映像符号化データを出力する手段と、変換器データを符号化し、変換器符号化データを出力する手段と、変換器符号化データと映像符号化データとを多重化し、符号化データを出力する手段とを備える。画像復号装置は、映像符号化データの復号処理における逆変換処理を変換器データに対応する逆変換処理により置換して逆変換処理を行う手段を備える。【選択図】図１５
2014082616.tif 000002
【特許請求の範囲】
【請求項１】
入力画像信号を符号化する画像符号化装置であって、
遺伝的プログラミングを用いて、前記入力画像信号の符号化処理に用いる変換器の演算式を前記入力画像信号毎に適応構成して変換器データを出力する変換器生成手段と、
前記符号化処理における変換処理を前記変換器データにより置換して前記変換処理を行う変換処理手段と、
前記符号化処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理手段と、
前記変換処理手段と前記逆変換処理手段とを用いて、前記入力画像信号を符号化し、映像符号化データを出力する画像符号化手段と、
前記変換器データを符号化し、変換器符号化データを出力する変換器符号化手段と、
前記変換器符号化データと前記映像符号化データとを多重化し、符号化データを出力する多重化手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記変換処理手段による前記変換処理及び前記逆変換処理手段による逆変換処理は、リフティング構造によって表現されていることを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記変換器生成手段は、
前記入力画像信号を符号化し、発生する符号量Ｒを推定する画像符号量推定手段と、
前記適応構成の手順を符号化し、手順符号量Ｒｏを推定する手順符号量推定手段と、
前記演算式を用いて導出された復元画像と前記入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出手段と、
ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λ（Ｒ＋Ｒｏ）によって算出するコスト算出手段とから構成し、
前記演算式を適応構成する際の最小化規準を前記ラグランジュコストＣとすることを特徴とする請求項１または２に記載の画像符号化装置。
【請求項４】
請求項１から３のいずれか１項に記載の画像符号化装置によって符号化された画像信号を復号する画像復号装置であって、
符号化データを逆多重化して、変換器符号化データと映像符号化データとを得る逆多重化手段と、
前記変換器符号化データを復号して変換器データを得る変換器復号手段と、
前記映像符号化データの復号処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理手段と
を備えることを特徴とする画像復号装置。
【請求項５】
入力画像信号を符号化する画像符号化方法であって、
遺伝的プログラミングを用いて、前記入力画像信号の符号化処理に用いる変換器の演算式を前記入力画像信号毎に適応構成して変換器データを出力する変換器生成ステップと、
前記符号化処理における変換処理を前記変換器データにより置換して前記変換処理を行う変換処理ステップと、
前記符号化処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理ステップと、
前記変換処理ステップと前記逆変換処理ステップとを用いて、前記入力画像信号を符号化し、映像符号化データを出力する画像符号化ステップと、
前記変換器データを符号化し、変換器符号化データを出力する変換器符号化ステップと、
前記変換器符号化データと前記映像符号化データとを多重化し、符号化データを出力する多重化ステップと
を有することを特徴とする画像符号化方法。
【請求項６】
請求項５に記載の画像符号化方法によって符号化された画像信号を復号する画像復号方法であって、
符号化データを逆多重化して、変換器符号化データと映像符号化データとを得る逆多重化ステップと、
前記変換器符号化データを復号して変換器データを得る変換器復号ステップと、
前記映像符号化データの復号処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理ステップと
を有することを特徴とする画像復号方法。
【請求項７】
コンピュータを、請求項１から３のいずれか１項に記載の画像符号化装置として機能させるための画像符号化プログラム。
【請求項８】
コンピュータを、請求項４に記載の画像復号装置として機能させるための画像復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像符号化装置、画像復号装置、画像符号化方法、画像復号方法、画像符号化プログラム及び画像復号プログラムに関する。
【背景技術】
【０００２】
非可逆な映像・画像符号化の構成要素は、予測・変換・量子化・エントロピー符号化の４要素に分類できる。従来、この要素中の「変換」部分は「線形変換」である。固定的な変換の例を説明する。変換には、例えば「離散コサイン変換（ＤＣＴ）」や「双直交ウェーブレット変換」、実数変換であるＤＣＴを整数近似した「整数変換」がもっぱら使われていた。
【０００３】
線形変換の簡単な例を挙げると、２入力（ｘ０，ｘ１）を２出力（ｙ０，ｙ１）に変換する際、
ｙ０＝ｘ０＋ｘ１
ｙ１＝ｘ０−ｘ１  ・・・（１）
と線形に演算するものである。画像・映像符号化で用いられるほとんどの変換式はＤＣＴあるいはその近似であり、言い換えれば予め定められた変換に固定されている。
【０００４】
次に、非固定的な変換の例を説明する。非固定的な変換を行うものとして、変換式を動的に変化させるものも存在する（例えば、非特許文献１参照）。これは、同じく簡単な例を示すと
ｙ０＝ａ＊ｘ０＋ｂ＊ｘ１
ｙ１＝ｃ＊ｘ０＋ｄ＊ｘ１  ・・・（２）
において、画像の性質に応じて最適な係数（ａ，ｂ，ｃ，ｄ）の値を調整し、符号化効率を高めるというものである。しかしながら変換そのものは線形の範疇に属するものである。
【０００５】
次に、選択的な変換の例を説明する。例えば映像符号化規格Ｈｉｇｈ  Ｅｆｆｉｃｉｅｎｃｙ  Ｖｉｄｅｏ  Ｃｏｄｉｎｇ（ＨＥＶＣ、非特許文献２参照）では、四種のサイズ（４点・８点・１６点・３２点）の整数変換が使われている。ＨＥＶＣのエンコーダ参照ソフトウェアでは、符号化効率を最も高めるサイズの変換を選択し、その選択情報とともに映像を符号化している。例えば、精細なテクスチャを含む画像ブロックには小さな点数の変換が、起伏のないなだらかな画像ブロックには大きな点数の変換が適しており、これらを選択的に用いることで符号化効率を高めるというものである。これらの変換も、線形の範疇に属するものである。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】松田，亀田，伊東，宇都宮：“適応的可変ブロック形状ＫＬ変換符号化の性能改善，  テレビジョン学会誌  Ｖｏｌ．４９，Ｎｏ．３，ｐｐ．３０９−３１８，１９９５
【非特許文献２】Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, "High efficiency video coding (HEVC) text specification draft 8", JCTVC-J1003_d7, July 2012
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非可逆な映像・画像符号化に線形変換が用いられる理由の一つは、復号時に必要になる「逆変換」が、線形変換の場合は容易であるが、非線形な変換では一般に極めて困難になるためである。（２）式の変換において出力（ｙ０，ｙ１）を入力（ｘ０，ｘ１）へ戻す変換（逆変換）は解析的に容易に求めることができ、
ｘ０＝（ｄ＊ｙ０−ｂ＊ｙ１）／（ａ＊ｄ−ｂ＊ｃ）
ｘ１＝（−ｃ＊ｙ０＋ａ＊ｙ１）／（ａ＊ｄ−ｂ＊ｃ）  ・・・（３）
となる。しかしながら非線形変換の場合、次のような比較的単純な変換
ｙ０＝ｘ０＾３＋ｘ１
ｙ１＝ｘ０−ｘ１＾３  ・・・（４）
ですら、逆変換は解析的手段では求められず、数値計算的手段により反復計算を行い、近似値を求めることになり、計算量が膨大になるため高速処理には向かないという問題がある。また反復計算に要する演算量は不定であるため、実時間処理にも向かないという問題もある。
【０００８】
本発明は、このような事情に鑑みてなされたもので、画像・映像の信号に応じて最適な変換処理を適応的に自動生成することができる画像符号化装置、画像復号装置、画像符号化方法、画像復号方法、画像符号化プログラム及び画像復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、入力画像信号を符号化する画像符号化装置であって、遺伝的プログラミングを用いて、前記入力画像信号の符号化処理に用いる変換器の演算式を前記入力画像信号毎に適応構成して変換器データを出力する変換器生成手段と、前記符号化処理における変換処理を前記変換器データにより置換して前記変換処理を行う変換処理手段と、前記符号化処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理手段と、前記変換処理手段と前記逆変換処理手段とを用いて、前記入力画像信号を符号化し、映像符号化データを出力する画像符号化手段と、前記変換器データを符号化し、変換器符号化データを出力する変換器符号化手段と、前記変換器符号化データと前記映像符号化データとを多重化し、符号化データを出力する多重化手段とを備えることを特徴とする。
【００１０】
本発明は、前記変換処理手段による前記変換処理及び前記逆変換処理手段による逆変換処理は、リフティング構造によって表現されていることを特徴とする。
【００１１】
本発明は、前記変換器生成手段は、前記入力画像信号を符号化し、発生する符号量Ｒを推定する画像符号量推定手段と、前記適応構成の手順を符号化し、手順符号量Ｒｏを推定する手順符号量推定手段と、前記演算式を用いて導出された復元画像と前記入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出手段と、ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λ（Ｒ＋Ｒｏ）によって算出するコスト算出手段とから構成し、前記演算式を適応構成する際の最小化規準を前記ラグランジュコストＣとすることを特徴とする。
【００１２】
本発明は、前記画像符号化装置によって符号化された画像信号を復号する画像復号装置であって、符号化データを逆多重化して、変換器符号化データと映像符号化データとを得る逆多重化手段と、前記変換器符号化データを復号して変換器データを得る変換器復号手段と、前記映像符号化データの復号処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理手段とを備えることを特徴とする。
【００１３】
本発明は、入力画像信号を符号化する画像符号化方法であって、遺伝的プログラミングを用いて、前記入力画像信号の符号化処理に用いる変換器の演算式を前記入力画像信号毎に適応構成して変換器データを出力する変換器生成ステップと、前記符号化処理における変換処理を前記変換器データにより置換して前記変換処理を行う変換処理ステップと、前記符号化処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理ステップと、前記変換処理ステップと前記逆変換処理ステップとを用いて、前記入力画像信号を符号化し、映像符号化データを出力する画像符号化ステップと、前記変換器データを符号化し、変換器符号化データを出力する変換器符号化ステップと、前記変換器符号化データと前記映像符号化データとを多重化し、符号化データを出力する多重化ステップとを有することを特徴とする。
【００１４】
本発明は、前記画像符号化方法によって符号化された画像信号を復号する画像復号方法であって、符号化データを逆多重化して、変換器符号化データと映像符号化データとを得る逆多重化ステップと、前記変換器符号化データを復号して変換器データを得る変換器復号ステップと、前記映像符号化データの復号処理における逆変換処理を前記変換器データに対応する逆変換処理により置換して前記逆変換処理を行う逆変換処理ステップとを有することを特徴とする。
【００１５】
本発明は、コンピュータを、前記画像符号化装置として機能させるための画像符号化プログラムである。
【００１６】
本発明は、コンピュータを、前記画像復号装置として機能させるための画像復号プログラムである。
【発明の効果】
【００１７】
本発明によれば、画像・映像の信号に応じて、最適な変換処理を適応的に自動生成することができる。また同時に、非線形変換に見られる逆変換処理の計算の困難さを回避し、反復計算などを用いず容易に逆変換処理を行うことが可能になるという効果が得られる。
【図面の簡単な説明】
【００１８】
【図１】Ｈ．２６４における４点変換を２×２行列で等価に表した図である。
【図２】行列表現の入出力と信号線とを機能ブロックで表したブロック図である。
【図３】典型的なリフティング構造変換のブロック図である。
【図４】図３に示す変換に対応する逆変換を表すブロック図である。
【図５】図１に示す変換を一部リフティング構造で置換したブロック図である。
【図６】図１に示す変換を一部リフティング構造で置換したブロック図である。
【図７】図１に示す変換を全部リフティング構造で置換したブロック図である。
【図８】図５に示す変換を書き直したブロック図である。
【図９】図８示す演算器の入力数をそれぞれ１個から３個にしたブロック図である。
【図１０】単純な演算式を木により表現し、上位・下位ノードや最上位ノード、終端ノードを示す説明図である。
【図１１】演算式の符号量の推定処理（アルゴリズム１）を示す説明図である。
【図１２】与えられた木に基づく演算器出力値を求める処理（アルゴリズム２）を示す説明図である。
【図１３】演算式の符号化処理（アルゴリズム３）を示す説明図である。
【図１４】演算式の復号処理（アルゴリズム４）を示す説明図である。
【図１５】本発明の一実施形態における画像符号化装置の構成を示すブロック図である。
【図１６】本発明の一実施形態における変換器生成・画像符号化の構成を示すブロック図である。
【図１７】図１５に示す変換処理部１０４の動作を示すフローチャートである。
【図１８】図１に示す逆変換処理部１０７の動作を示すフローチャートである。
【図１９】図１６に示す変換器生成部１５１の動作を示すフローチャートである。
【図２０】本発明の一実施形態における画像復号装置の構成を示すブロック図である。
【図２１】本発明の一実施形態における変換器復号・画像復号の構成を示すブロック図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して、本発明の一実施形態による画像符号化装置及び画像復号装置を説明する。本実施形態では、音声・画像の変換でしばしば用いられる「リフティング構造」と呼ばれる構造を、変換・逆変換に用いる。またこのリフティング構造の構成要素である「演算器」を、「遺伝的プログラミング」と呼ばれる手法により、線形に限らず非線形の範疇も含みながら自動構築する。リフティング構造を用いた変換は、その線形性・非線形性とは無関係に逆変換が可能である。
【００２０】
次に、符号化に用いられている変換・逆変換のリフティング構造による表現について説明する。ＤＣＴなどの直交変換は、数学的に等価な「リフティング構造」により表現することができる。例えばＨ．２６４／ＡＶＣの４点変換行列を４×４行列で表現すると、
【数１】
2014082616.tif 000003
のようになっている。ここでｘ０，…，ｘ３の４点が入力、ｙ０，…，ｙ３が同じく４点の出力である。これは、２×２行列を４個用いた図１の変換と数学的に等価である。図１は、Ｈ．２６４における４点変換を２×２行列で等価に表した図である。なお、２×２行列Ａによる、（ａ０，ａ１）の２点を（ｂ０，ｂ１）の２点に変換する数式
【数２】
2014082616.tif 000004
を、図２に示すブロック図により表している。図２は、行列表現の入出力と信号線とを機能ブロックで表したブロック図である。行列は入力が右、出力が左なのに対し、図２に示すブロック図では入力が左、出力が右になっている。
【００２１】
この２種の２×２行列は、どちらも平面回転行列を定数倍したものになっている。
【数３】
2014082616.tif 000005
ここでｃ１＝ｃｏｓα１、ｓ１＝ｓｉｎα１、α１はその行列の回転角、ｃ２＝ｃｏｓα２、ｓ２＝ｓｉｎα２、α２はその行列の回転角である。
【００２２】
角度αの平面回転行列は、ｃ＝ｃｏｓα、ｓ＝ｓｉｎαを使って、
【数４】
2014082616.tif 000006
と変形できる。これに基づき、平面回転行列を図３に示す「リフティング構造」で等価表現できる。図３は、典型的なリフティング構造変換のブロック図である。図３に示すブロック図中で、「＋」は２個の信号線からの入力の和を生成する操作を示し、「△」で示される要素は、１入力１出力の演算器である。以下で参照する図においては、「＋」は省略する。具体的には（６）式と整合させるように、Ｐは入力を（ｃ−１）／ｓ倍して出力する。また、Ｑは入力をｓ倍して出力し、Ｒは入力を（ｃ−１）／ｓ倍して出力する。例えば（４）式の変換に対応するリフティング構造は、定数倍を除くと、Ｐは入力を（１／√２−１）√２倍（−０．４１４２倍）して出力する。また、Ｑは入力を１／√２倍（０．７０７１倍）して出力し、Ｒは入力を（１／√２−１）√２倍（−０．４１４２倍）し出力することになる。
【００２３】
この逆変換は、図４に示すように、変換と同じ演算器Ｐ，Ｑ，Ｒを逆順（Ｒ，Ｐ，Ｑの順）に用い、加算を減算にしたリフティング構造で表現できる。図４は、図３に示す変換に対応する逆変換を表すブロック図である。図４に示す「−」は、水平の信号線の入力から垂直の信号線の入力を減じる操作を示している。
【００２４】
以下で説明するより複雑なリフティング構造も、すべてこのように演算器を逆順に並べ加算を減算にするだけで逆変換にすることができる。
【００２５】
Ｈ．２６４／ＡＶＣが用いている整数変換は、４点と８点があるが、いずれも「平面回転行列」と呼ばれる、２×２行列による変換を組み合わせた構造で表現される。ＨＥＶＣの４点・８点・１６点・３２点変換も同様である。したがって、これらの変換および逆変換はいずれも、リフティング構造を組み合わせた変換によって表現することができる。
【００２６】
次に、リフティング構造による変換・逆変換の性質について説明する。前述の説明では演算器Ｐ，Ｑ，Ｒはいずれも入力を定数倍して出力していたが、これらは線形・非線形を問わず任意の演算（入力に無関係な出力を行う演算（例えば「入力を０倍する」やゼロ除算を伴うものなどを除く）でよい。例えば入力ｘ、出力ｙとすると
ｙ＝ｓｉｎｘ
ｙ＝ｘ＾５＋ｘ
など、非線形な演算器でも問題はなく、図３に示す変換に続き図４に示す逆変換を施すことにより、入力値が完全再構成される。当然ながら、符号化処理において変換後に行われる「量子化・逆量子化」が加わり、変換後の値が変化したものを逆変換する場合は、入力値の完全再構成はなされない。
【００２７】
次に、自動生成演算器の利用について説明する。ここでは、リフティング構造の演算器を「遺伝的プログラミング」と呼ばれる方法により自動生成する。例えば、図１に示す変換を一部リフティング構造で置換した図５に示す変換において、Ｐ，Ｑ，Ｒ，Ｓ，Ｔ，Ｕの６演算器を、それぞれ遺伝的プログラミングにより自動生成する。図５は、図１に示す変換を一部リフティング構造で置換したブロック図である。
【００２８】
他にも、図６に示す変換においてＰ，Ｑ，Ｒを自動生成する、あるいはすべてを置換し、図７に示す変換のＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｐ，Ｑ，Ｒ，Ｓ，Ｔ，Ｕの１２個を自動生成するようにしてもよい。図６は、図１に示す変換を一部リフティング構造で置換したブロック図である。図７は、図１に示す変換を全部リフティング構造で置換したブロック図である。
【００２９】
前述の説明ではいずれも、各演算器（△）は１入力である。言い換えると入力数は、特定の信号線からの値１つのみである。しかしながらこの制約は必須ではなく、２入力あるいはそれ以上の入力を用いてもよい。特定の信号線以外からの入力値としては、例えば、ブロック内の他の信号線の値、変換しようとしているブロックの画面内ｘ座標やｙ座標、変換しようとしているブロックの（画面内・画面間）予測画像の画像特徴量（例えば、分散、予測モード番号、縦エッジ強度、横エッジ強度）、当該フレームの表示番号、当該フレームのピクチャタイプなど、「復号器でも得られる情報」であれば何でもよい。ブロック内の他の信号線を用いることで、変換の自由度を高めることができ、より良好な符号化性能を与える変換を獲得する可能性が高まる。入力値として画面内ｘ座標やｙ座標を用いると、例えば「画面の左下に向いた変換」や「画面の上１／３に向いた変換」など、空間的な絵柄の性質の違いに応じた変換が生成できる。予測画像の分散を用いると、「起伏の激しい領域（分散が大きい）に向いた変換」や「起伏の穏やかな領域（分散が小さい）に向いた変換」など、局所的な絵柄の性質に応じた変換を生成できる。また、画面内予測はエッジ方向に沿って行われることが多いため、予測モード番号を用いると、そのエッジ方向に適した変換を生成できる。同様に、縦エッジ強度、横エッジ強度を用いれば、「縦エッジの優勢な領域に向いた変換」や「縦にも横にもエッジのある領域に向いた変換」など、局所的な絵柄の性質に応じた変換を生成できる。当該フレームの表示番号を用いることで、符号化シーケンスが例えばフェードイン・フェードアウトなど時間的に変化する場合に、そのフェードの強度に応じた変換が生成でき、時間的な絵柄の性質の違いに応じた変換を生成できる。また、予測残差信号の統計的性質は、そのピクチャが画面内予測なのか、一方向画面間予測なのか、双方向画面間予測なのかというピクチャタイプにより異なっている。そのため当該フレームのピクチャタイプを用いることで、予測残差信号の統計的性質に応じた変換を生成できる。
【００３０】
例えば、図５に示す変換は、図８に示す変換とすることができるが、これを例えば、図９に示す変換のように、他の信号線からも値を参照するようにしてもよい。図８は、図５に示す変換を書き直したブロック図である。図９は、図８示す演算器の入力数をそれぞれ１個から３個にしたブロック図である。この場合も逆変換は、前述の説明と全く同様、演算器を逆順に配置し、信号線との交点を加算から減算に変更することで実現することができる。
【００３１】
次に、前述の演算器を高性能かつ自動に構成する方法について説明する。まず、遺伝的プログラミングについて説明する。ここでは遺伝的プログラミングを用いて演算器を自動構成する。遺伝的プログラミングは、生物進化にヒントを得た「手順の最適化探索」の一手法であり、手順を木で表現するものである。そして、（１）そのような木を多数生成して母集団を形成し、（２）その母集団から適宜取り出された木（親）から遺伝的手法（交叉や突然変異）により新しい木（子）を生成し、（３）その木（子）を評価して、より適したものであれば母集団に加える、という手順を繰り返すことにより、より評価の高い木を獲得（発見）する枠組みである。
【００３２】
上記（３）の「評価」は、映像符号化で広く用いられているラグランジュの未定乗数法により行う。これは、別途入力されるラグランジュ未定乗数λ、変換器を伝送するための符号量Ｒｏ［ｂｉｔｓ］、この変換器を用いて入力信号を符号化した場合の符号量Ｒ［ｂｉｔｓ］と、復号画像と原信号の間の二乗誤差和Ｄから求まるラグランジュコストＣ＝Ｄ＋λ（Ｒｏ＋Ｒ）を求め、Ｃが小さいほど高評価とするものである。ここで変換器の符号量は、変換器を構成する要素である演算器の符号量の和となる。
【００３３】
次に、木構造と演算器（変換器を構成する要素）の対応について説明する。演算器は次のように木構造により記述できる。例えば「１番目の信号線ｓ１と２番目の信号線ｓ２の平均を求める演算器」つまり（ｓ１＋ｓ２）／２という演算は、図１０に示すように、非終端ノードと終端ノードから構成される木構造により表現することができる。図１０は、単純な演算式を木により表現し、上位・下位ノードや最上位ノード、終端ノードを示す説明図である。ここで非終端ノードはいわゆる「関数」であり、例えば条件分岐、加減乗除、三角関数、二乗、平方根、指数・対数、絶対値、最小値、最大値など、一つあるいは複数の入力（引数）から一つの値を返すものである。これらの関数は引数をとるため、木の終端でない部分に現れるため「非終端ノード」と呼ばれる。
【００３４】
また、ノード自体が値を持つ（引数を要しない）ため木の終端に位置する「終端ノード」として、「０．１４８」のような数値や、ｓ０，ｓ１などのような信号線（信号線が４本あれば、その演算器が加算する信号線を除いた３本をｓ０、ｓ１、ｓ２と名付ける）の値、変換ブロックの画面内ｘ座標やｙ座標、変換ブロックの予測値の平均値や分散値、その他変換ブロックの予測モード番号など、符号化器と復号器で共有可能な値などがある。終端ノードおよび非終端ノードは事前に用意しておくもののほか、動的に定義してもよい（automatically defined function，ＡＤＦ）。ＡＤＦについては、文献：「J. Koza: ``Genetic Programming II, Automatic Discovery of Reusable Programs'', The MIT Press, 1998」等に記載されている。
【００３５】
次に、演算器の符号量の推定について説明する。演算器の木構造を表現するのに必要なビット数は、図１１に示す再帰的関数（アルゴリズム１）により求めることができる。図１１は、演算式の符号量の推定処理（アルゴリズム１）を示す説明図である。ここで木の終端ノードが表す数値は、例えば１０ビット固定小数点整数により表現されており、各関数には０からＮ−１までの固有の通し番号がついているものとする。ＦＵＮＣＩＮＦＯは、用いる関数がＮ種類としたとき、関数を固定長符号化したときの符号量を表す以下の量であり、ＦＵＮＣＩＮＦＯ＝ｌｏｇ＿２（Ｎ＋１）となる。
【００３６】
ここでＮ＋１となっているのは、関数の場合に加え数値（０．１４８など）の場合も含めるためである。ここでは固定長符号化を仮定しているが、関数毎の生起頻度を考慮した可変長符号化を行ってもよい。そして、着目している手順（木）の最上位ノードをｒｏｏｔとしたとき、Ｒ＝ｔｒｅｅ＿ｉｎｆｏ（ｒｏｏｔ）を実行すれば、木の情報量Ｒが求まる。
【００３７】
次に、与えられた木に基づく演算結果（出力値）について説明する。出力値は、図１２に示すように再帰的な手続き（アルゴリズム２）により求めることができる。図１２は、与えられた木に基づく演算器出力値を求める処理（アルゴリズム２）を示す説明図である。図１２においては、引数の個数が３個までの例を示しているが、引数の個数上限が４個、５個と増えても処理は同様で、容易に拡張できる。そして、着目している手順（木）の最上位ノードをｒｏｏｔとしたとき、演算器出力＝ｔｒｅｅ＿ｅｖａｌ（ｒｏｏｔ）として、この演算器の出力値を求めることができる。
【００３８】
次に、演算式の符号化・復号について説明する。符号化も、情報量推定（アルゴリズム１）と同様に、図１３に示す再帰的手続き（アルゴリズム３）で実行できる。図１３は、演算式の符号化処理（アルゴリズム３）を示す説明図である。そして、着目している手順（木）の最上位ノードをｒｏｏｔとしたとき、ｔｒｅｅ＿ｅｎｃｏｄｅ（ｒｏｏｔ）を実行すれば、その木が符号化できる。このときの必要符号量の下限はｔｒｅｅ＿ｉｎｆｏ（ｒｏｏｔ）に一致する。
【００３９】
また復号についても同様に図１４に示す再帰的関数（アルゴリズム４）で実行できる。図１４は、演算式の復号処理（アルゴリズム４）を示す説明図である。図１４において、「Ｆが必要とする引数の数」とは、たとえばＦがａｄｄ等の２項演算子であれば２、三項演算子あれば３、など、その関数が値を出すのに使用する値の個数（符号化側、復号側ともに既知）である。Ｆはその個数だけ下位ノードを直下に持っている。そして、ｔｒｅｅ＿ｄｅｃｏｄｅ（）を実行すれば、ビットストリームより木が復号され、返される。
【００４０】
このように、従来の変換においては入力画像の画素値または時空間予測差分値に関し、線形な処理でのみ変換結果を求めていたところ、本実施形態では遺伝的プログラミングにより、従来の変換と等価な変換その他の線形変換も含み、かつ線形の範疇にとらわれない変換を次々と生成させるようにしたため、変換設計の自由度を飛躍的に高めることができる。また、生成された変換はラグランジュコストにより符号量−歪みの面で評価し、生存選択を行うようにしたため、必ず性能を改善した変換が生き残り、従来の変換を用いては達成できなかった高い符号化効率を達成することができる。
【００４１】
次に、図面を参照して、本発明の一実施形態による画像符号化装置を説明する。図１５は同実施形態における画像符号化装置の構成を示すブロック図である。この画像符号化装置は、符号化対象画像の入力画像信号を入力し、入力画像信号のフレームをブロックに分割してブロック毎に符号化し、符号化データとして出力する。図１５に示す画像符号化装置は、変換器データ１１７を入力する点と、変換処理部１０４、逆変換処理部１０７に変更を加えている点が従来技術と異なる点であり、他の構成は、Ｈ．２６４／ＡＶＣその他の画像符号化装置として用いられている従来の一般的な構成と同様であるため、図１５に示す画像符号化装置の構成の説明を簡単に行う。
【００４２】
予測残差信号生成部１０３は、入力画像信号とインター予測処理部１０２あるいはイントラ予測処理部１０１の出力である予測信号との差分を求め、それを予測残差信号として出力する。変換処理部１０４は、入力した変換器データ１１７を参照し、予測残差信号に対して、前述した「変換」を行い、変換係数を出力する。量子化処理部１０５は、変換係数を量子化し、量子化後の値を出力する。逆量子化処理部１０６は、量子化後変換係数を入力し、逆量子化処理を行う。逆変換処理部１０７は、変換器データ１１７を参照し、逆量子化処理部１０６の出力である逆量子化後変換係数に対して、前述した「逆変換」を施し、予測残差復号信号を出力する。復号信号生成部１０８は、この予測残差復号信号とインター予測処理部１０２あるいはイントラ予測処理部１０１の出力である予測信号とを加算し、符号化した符号化対象ブロックの復号信号を生成する。この復号信号は、イントラ予測処理部１０１にて参照画像として用いるために、フレームメモリ１０９に格納する。イントラ予測処理部１０１は、フレームメモリ１０９に格納された画像から予測モードなどを設定する。
【００４３】
また、インター予測処理部１０２において参照するために、ループ内フィルタ処理部１１０は、フレームメモリ１０９に格納した画像を入力して、符号化歪みを低減するフィルタリング処理を行い、フレームメモリ１１５に格納する。インター予測処理部１０２は、フレームメモリ１１５に格納されている過去の画像と、現在の入力画像信号から動きベクトルや動き単位などの情報を求める。ループ内フィルタ処理部１１０において設定された予測係数等の情報は、ループ内フィルタ情報格納部１１４に格納される。イントラ予測処理部１０１において設定された予測モードなどの情報は、イントラ予測情報格納部１１２に格納される。エントロピー符号化処理部１１３は、量子化処理部１０５の出力である量子化後変換係数、ループ内フィルタ情報格納部１１４に格納された予測係数等の情報、インター予測情報格納部１１１に格納された動きベクトルなどの情報及びイントラ予測情報格納部１１２に格納された予測モードなどの情報をエントロピー符号化し、符号化データとして出力する。
【００４４】
次に、図１６を参照して、変換器生成・符号化の動作を説明する。図１６は、本発明の一実施形態における変換器生成・画像符号化の構成を示すブロック図である。図１６に示す符号化器１５４は、図１に示す装置全体であり、入力信号と変換器データ１５２を入力としている。変換器生成部１５１は、入力信号を繰り返し符号化しながら変換器を進化生成させ、最良である変換器の情報を変換器データ１５２として出力する。この「変換器データ」は、例えば図５に示す全演算器（Ｐ，Ｑ，Ｒ，Ｓ，Ｔ，Ｕ）を、前述のように「木」として表現したものである。変換器データ１５２は変換器符号化部１５３において符号化され、変換器符号化データとして出力される。これは、前述のアルゴリズム３（図１３参照）により、「木」で表現された演算器を符号化する。符号化器１５４はこの変換器データと入力信号から符号化を行い、映像符号化データを出力する。変換器符号化データと映像符号化データはＭｕｘ部１５５にて結合され、符号化データとして出力する。
【００４５】
次に、図１７を参照して、図１５に示す変換処理部１０４の動作を説明する。図１７は、図１に示す変換処理部１０４の動作を示すフローチャートである。まず、変換処理部１０４は、変換する点数に応じた数の信号線から値を入力する（ステップＳ１）。次いで、変換処理部１０４は、リフティングに用いる演算器Ａを処理順に列挙する（ステップＳ２）。例えば、図８ではＳ，Ｔ，Ｕ，Ｐ，Ｑ，Ｒの順に演算器Ａに割り当てられる。次いで、変換処理部１０４は、この演算器Ａの出力値を計算する（ステップＳ３）。これは前述したアルゴリズム２（図１２参照）の処理動作によって実現できる。次いで、変換処理部１０４は、その結果を接続されている信号線へ加算する（ステップＳ４）。全ループが終了したら（ステップＳ５）、変換処理部１０４は、信号線の値を出力する（ステップＳ６）。
【００４６】
次に、図１８を参照して、図１５に示す逆変換処理部１０７の動作を説明する。図１８は、図１に示す逆変換処理部１０７の動作を示すフローチャートである。まず、逆変換処理部１０７は、変換する点数に応じた数の信号線から値を入力する（ステップＳ１１）。次いで、逆変換処理部１０７は、リフティングに用いる演算器Ａを正変換とは逆順に列挙する（ステップＳ１２）。例えば、図８に示す変換の逆変換ではＲ，Ｑ，Ｐ，Ｕ，Ｔ，Ｓの順に演算器Ａに割り当てられる。次いで、逆変換処理部１０７は、この演算器Ａの出力値を計算する（ステップＳ１３）。これは前述したアルゴリズム２（図１２参照）の処理動作によって実現できる。次いで、逆変換処理部１０７は、その結果を接続されている信号線の値から減算する（ステップＳ１４）。全ループが終了したら（ステップＳ１５）、逆変換処理部１０７は、信号線の値を出力する（ステップＳ１６）。
【００４７】
次に、図１９を参照して、図１６に示す変換器生成部１５１の詳細動作を説明する。図１９は、図１６に示す変換器生成部１５１の動作を示すフローチャートである。まず、変換器生成部１５１は、母集団生成処理により、進化の元となる変換器（Ｐ，Ｑ，Ｒなど演算器の集合）の集団を生成する（ステップＳ２１）。次いで、変換器生成部１５１は、複製選択・子の生成処理において親集合の選択と子個体の生成を行う（ステップＳ２２）。「子の生成」は交叉、突然変異、逆位などの処理により行われる。
【００４８】
次に、変換器生成部１５１は、ステップＳ２２において生成した個体（変換手順を表す）を用い、符号化処理にて、この変換を用いた符号化・復号された画像を生成する（ステップＳ２３）。この変換動作は、前述したアルゴリズム２（図１２参照）の処理動作によって実現できる。次いで、変換器生成部１５１は、二乗誤差和Ｄ・符号量Ｒ算出処理において全画面の誤差和Ｄと符号量Ｒを算出する（ステップＳ２４）とともに、その個体の情報量を木情報量Ｒｏ算出処理において算出する（ステップＳ２５）。これは前述したアルゴリズム１（図１１参照）の処理動作によって実現できる。
【００４９】
次に、変換器生成部１５１は、ラグランジュコストＣ＝Ｄ＋λ（Ｒ＋Ｒｏ）の値を評価値として、生存選択処理において生存するか否かを決定する（ステップＳ２６）。ラグランジュ未定乗数λは、符号化プロセスがＲＤ最適化で用いているのと同一の値であってもよいし、異なったものを別途指定してもよい。そして、変換器生成部１５１は、進化が収束したか否かを判定する（ステップＳ２７）。例えば、収束条件として、Ｃの減少割合が一定値（例えば、０．１％）を下回る、評価回数が一定値（例えば、１万回）を超える、などが適用できる。変換器生成部１５１は、まだ収束していないと判定されればステップＳ２２へ戻り処理を繰り返し、収束と判定されれば処理を終了する。この処理動作によって、高能率変換器が自動生成されることになる。
【００５０】
なお、図１５に示す変換動作は、従来の変換処理（４点・８点・１６点・３２点変換、ＤＣＴ、ＤＳＴなど）と併用してもよいし、一部を置き換えるようにしてもよい。またＨ．２６４／ＡＶＣやＨＥＶＣでは、変換するブロックに対し縦方向（１次元）と横方向（同じく１次元）別々に変換を施しているが、変換を縦横同時に行うような変換（２次元変換）を、変換動作としてもよい。
【００５１】
次に、本発明の一実施形態による画像復号装置を説明する。図２０は同実施形態における画像復号装置の構成を示すブロック図である。この画像復号装置は、図１５に示す画像符号化装置により符号化された符号化データを入力して復号することにより復号画像の映像信号を出力する。図２０に示す画像復号装置は、変換器データ２１２を入力する点と逆変換処理部２０５に変更を加えている点が従来技術と異なる点であり、他の構成は、Ｈ．２６４その他の画像復号装置として用いられている従来の一般的な構成と同様であるため、図２０に示す画像復号装置の構成の説明を簡単に行う。
【００５２】
復号を行うため、エントロピー復号処理部２０１は、符号化データを入力し、復号対象ブロックの量子化後変換係数をエントロピー復号するとともに、イントラ予測、インター予測、およびループ内フィルタに関する情報を復号し、イントラ予測情報格納部２１０、インター予測情報格納部２０９、ループ内フィルタ情報格納部２１１にそれぞれ格納する。逆量子化処理部２０４は、量子化後変換係数を入力し、それを逆量子化して復号変換係数を出力する。逆変換処理部２０５は、変換器データ２１２を参照し、復号変換信号に前述した「逆変換」を施し、予測残差復号信号を出力する。
【００５３】
この予測残差復号信号とインター予測処理部２０３あるいはイントラ予測処理部２０２の出力である予測信号とを加算し、復号対象ブロックの復号信号を生成する。この復号信号は、イントラ予測処理部２０２にて参照画像として用いるために、フレームメモリ２０７に格納する。また、インター予測処理部２０３にて参照するために、ループ内フィルタ処理部２０８において、フレームメモリ２０７に格納された画像を入力して、符号化歪みを低減するフィルタリング処理を行い、出力信号として出力すると同時に、フレームメモリ２０６に格納する。ループ内フィルタ処理部２０８は、画質改善フィルタを復号し、得られた画質改善フィルタを使用して、フィルタを施した画素値を生成して出力信号として出力する。
【００５４】
次に、図２１を参照して、変換器復号・映像復号の動作を説明する。図２１は、本発明の一実施形態における変換器復号・画像復号の構成を示すブロック図である。図２１に示す復号器２５４は、図２０に示す装置全体であり、入力信号と変換器データ２５３を入力としている。符号化データはＤｅＭｕｘ部２５１に入力され、変換器符号化データと映像符号化データに分離される。変換器復号部２５２は、変換器データ２５３を復号する。復号器２５４はこの変換器データと映像符号化データから復号を行い出力信号を出力する。
【００５５】
以上説明したように、画像・映像の非可逆符号化において、映像品質の改善と符号化ビットレートの削減を目的とし、自動的に高性能な符号化方式を生成する際に、画像・映像の信号に応じて最適な変換処理を、非線形の範疇まで含めて、適応的に自動生成するようにした。また同時に、非線形変換に見られたような逆変換処理の計算の困難さを回避し、反復計算などを用いず容易に逆変換処理が可能であるよう変換処理を構成するようにした。これにより、画像・映像符号化において、変換処理後の符号量と逆変換処理後の符号化歪のバランス（ラグランジュコスト）を最適化できるため、より少ない符号量でより高い品質の復号映像を得ることができる。
【００５６】
なお、図１５、図２０における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより画像符号化処理及び画像復号処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００５７】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００５８】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。したがって、本発明の技術思想及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行っても良い。
【産業上の利用可能性】
【００５９】
画像・映像の非可逆符号化において、映像品質の改善および符号化ビットレートの削減を目的として、画像の符号化・復号を行うことが不可欠な用途に適用できる。
【符号の説明】
【００６０】
１０１・・・イントラ予測処理部、１０２・・・インター予測処理部、１０３・・・予測残差信号生成部、１０４・・・変換処理部、１０５・・・量子化処理部、１０６・・・逆量子化処理部、１０７・・・逆変換処理部、１０８・・・復号信号生成部、１０９・・・フレームメモリ、１１０・・・ループ内フィルタ処理部、１１１・・・インター予測情報格納部、１１２・・・イントラ予測情報格納部、１１３・・・エントロピー符号化処理部、１１４・・・ループ内フィルタ情報格納部、１１５・・・フレームメモリ、１１６・・・動きベクトル検出部、１１７・・・変換器データ、２０１・・・エントロピー復号処理部、２０２・・・イントラ予測処理部、２０３・・・インター予測処理部、２０４・・・逆量子化処理部、２０５・・・逆変換処理部、２０６・・・フレームメモリ、２０７・・・フレームメモリ、２０８・・・ループ内フィルタ処理部、２０９・・・インター予測情報格納部、２１０・・・イントラ予測情報格納部、２１１・・・ループ内フィルタ情報格納部、２１２・・・変換器データ、１５１・・・変換器生成部、１５２・・・変換器データ、１５３・・・変換器符号化部、１５４・・・符号化器、１５５・・・Ｍｕｘ部、２５１・・・ＤｅＭｕｘ部、２５２・・・変換器復号部、２５３・・・変換器データ、２５４・・・復号器
【図１】
2014082616.tif 000007
【図２】
2014082616.tif 000008
【図３】
2014082616.tif 000009
【図４】
2014082616.tif 000010
【図５】
2014082616.tif 000011
【図６】
2014082616.tif 000012
【図７】
2014082616.tif 000013
【図８】
2014082616.tif 000014
【図９】
2014082616.tif 000015
【図１０】
2014082616.tif 000016
【図１１】
2014082616.tif 000017
【図１２】
2014082616.tif 000018
【図１３】
2014082616.tif 000019
【図１４】
2014082616.tif 000020
【図１５】
2014082616.tif 000021
【図１６】
2014082616.tif 000022
【図１７】
2014082616.tif 000023
【図１８】
2014082616.tif 000024
【図１９】
2014082616.tif 000025
【図２０】
2014082616.tif 000026
【図２１】
2014082616.tif 000027