(57)【要約】【課題】フィルタの演算式を自動構築することができる画像符号化方法を提供する。【解決手段】入力画像信号を符号化する画像符号化方法であって、遺伝的プログラミングを用いて、符号化ループの内部で用いる画質改善フィルタの演算式を入力画像信号毎に適応構成するフィルタ生成ステップと、演算式を符号化する符号化ステップと、入力画像信号に対して画質改善フィルタの演算式によりフィルタ処理を施すフィルタリングステップと、適応構成の手順を表現するための符号量Ｒを推定する推定ステップと、演算式を用いて導出された復元画像と入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出ステップと、ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λＲによって求めるコスト算出ステップとを有し、画質改善フィルタを適応構成する際の最小化規準をラグランジュコストＣとする。【選択図】図１
2015167423.tif 000002
【特許請求の範囲】
【請求項１】
入力画像信号を符号化する画像符号化装置が行う画像符号化方法であって、
遺伝的プログラミングを用いて、符号化ループの内部で用いる画質改善フィルタの演算式を前記入力画像信号毎に適応構成するフィルタ生成ステップと、
前記演算式を符号化する符号化ステップと、
前記入力画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタリングステップと、
前記適応構成の手順を表現するための符号量Ｒを推定する推定ステップと、
前記演算式を用いて導出された復元画像と前記入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出ステップと、
ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λＲによって求めるコスト算出ステップとを有し、
前記画質改善フィルタを適応構成する際の最小化規準を前記ラグランジュコストＣとし、
前記符号化ステップにおいて、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする画像符号化方法。
【請求項２】
符号化された画像信号を復号する画像復号装置が行う画像復号方法であって、
画質改善フィルタの演算式を前記符号化された画像信号から復号する復号ステップと、
前記符号化された画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタリングステップとを有し、
前記復号ステップにおいて、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする画像復号方法。
【請求項３】
入力画像信号を符号化する画像符号化装置であって、
遺伝的プログラミングを用いて、符号化ループの内部で用いる画質改善フィルタの演算式を前記入力画像信号毎に適応構成するフィルタ生成手段と、
前記演算式を符号化する符号化手段と、
前記入力画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタ手段と、
前記適応構成の手順を表現するための符号量Ｒを推定する推定手段と、
前記演算式を用いて導出された復元画像と前記入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出手段と、
ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λＲによって求めるコスト算出手段とを備え、
前記画質改善フィルタを適応構成する際の最小化規準を前記ラグランジュコストＣとし、
前記符号化手段は、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする画像符号化装置。
【請求項４】
符号化された画像信号を復号する画像復号装置であって、
画質改善フィルタの演算式を前記符号化された画像信号から復号する復号手段と、
前記符号化された画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタ手段とを備え、
前記復号手段は、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする画像復号装置。
【請求項５】
請求項１に記載の画像符号化方法をコンピュータに実行させるための画像符号化プログラム。
【請求項６】
請求項２に記載の画像復号方法をコンピュータに実行させるための画像復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像・映像の非可逆符号化において、映像品質の改善および符号化ビットレートを削減する画像符号化方法、画像復号方法、画像符号化装置、画像復号装置、画像符号化プログラム及び画像復号プログラムに関する。
【背景技術】
【０００２】
従来から、ＨＥＶＣ（High Efficiency Video Coding）などの映像符号化の構成要素の一つに、「ループ内フィルタ」と呼ばれる画質改善フィルタがある。これは、復号直後の局所復号画像に含まれる歪みを低減させるフィルタである。ループ内フィルタには、デブロッキングフィルタやSample Adaptive Offset（以下、ＳＡＯという；例えば、非特許文献１参照）、Adaptive Loop Filter（以下、ＡＬＦという；例えば、非特許文献２参照）などが存在する。画像内に、フィルタを適用しても画質が改善される効果が得られる場所と、画質が改善されない場所があるため、事前に定められた規則、または、四分木等の付加情報により、フィルタを適用する領域としない領域を分離している。
【０００３】
デブロッキングフィルタは、符号化ブロックとブロックの境界に生じる歪み（これをブロック歪みという）を、位置に応じて適応的に変化する方法により、効果的に取り除くものである。ＳＡＯは、符号化・復号により生じる画素値の上下変動（オフセット）のトレンドを、着目画素の属する輝度帯域（バンド）やエッジ方向に応じて補正するものである。また、ＡＬＦは、線形空間フィルタにより符号化歪みの重畳した復号画像を効果的に原画像信号に近づけるものである。
【０００４】
ここで、図１６を参照して、ＡＬＦについて説明する。着目画素（これから画質改善を施す画素）の画素値をｘ２とする（図１６（ａ）参照）。またその周辺の画素値をｘ０，ｘ１，ｘ３，ｘ４とする（図１６（ｂ）参照）。また別途、ＡＬＦ用フィルタ係数Ｃ０，Ｃ１，Ｃ２が伝送されている。ｘ２の位置の画質改善後の値は、
Ｃ０×ｘ０＋Ｃ１×ｘ１＋Ｃ２×ｘ２＋Ｃ１×ｘ３＋Ｃ０×ｘ４
＝Ｃ０×（ｘ０＋ｘ４）＋Ｃ１×（ｘ１＋ｘ３）＋Ｃ２×ｘ２
となる。
【０００５】
上記の画質改善技術はいずれも局所復号された画像の品質を高める効果がある。また動き予測符号化において、参照画像の画質が高まると、動き補償後の差分信号の振幅が減り、送信すべき情報が少なくて済むようになることから、映像符号化効率の改善に寄与している。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Chih-Ming Fu, Ching-Yeh Chen, Chia-Yang Tsai, Yu-Wen Huang, and Shawmin Lei: “Sample Adaptive Offset with Zero Pixel Line Buffers for LCU-based Decoding", ITU-T and ISO/IEC, JCTVC-F055, July, 2011
【非特許文献２】W. Lai, F. C. A. Fernandes, H. Guermazi F. Kossentini and M. Horowitz: "CE8 Subtest 4: ALF using vertical-size 5 filters with up to 9 coefficients", ITU-T and ISO/IEC, JCTVC-F303, July, 2011
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の画質改善を行うためのループ内フィルタの演算式は、線形変換であり、かつ手順が固定であるため、参照画像の品質をさらに高め、より少ない符号量でより高い品質の復号映像を得ることができないという問題がある。
【０００８】
本発明は、このような事情に鑑みてなされたもので、フィルタの演算式を自動構築することにより、参照画像の品質を高め、より少ない符号量でより高い品質の復号映像を得ることができる画像符号化方法、画像復号方法、画像符号化装置、画像復号装置、画像符号化プログラム及び画像復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、入力画像信号を符号化する画像符号化装置が行う画像符号化方法であって、遺伝的プログラミングを用いて、符号化ループの内部で用いる画質改善フィルタの演算式を前記入力画像信号毎に適応構成するフィルタ生成ステップと、前記演算式を符号化する符号化ステップと、前記入力画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタリングステップと、前記適応構成の手順を表現するための符号量Ｒを推定する推定ステップと、前記演算式を用いて導出された復元画像と前記入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出ステップと、ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λＲによって求めるコスト算出ステップとを有し、前記画質改善フィルタを適応構成する際の最小化規準を前記ラグランジュコストＣとし、前記符号化ステップにおいて、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする。
【００１０】
本発明は、符号化された画像信号を復号する画像復号装置が行う画像復号方法であって、画質改善フィルタの演算式を前記符号化された画像信号から復号する復号ステップと、前記符号化された画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタリングステップとを有し、前記復号ステップにおいて、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする。
【００１１】
本発明は、入力画像信号を符号化する画像符号化装置であって、遺伝的プログラミングを用いて、符号化ループの内部で用いる画質改善フィルタの演算式を前記入力画像信号毎に適応構成するフィルタ生成手段と、前記演算式を符号化する符号化手段と、前記入力画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタ手段と、前記適応構成の手順を表現するための符号量Ｒを推定する推定手段と、前記演算式を用いて導出された復元画像と前記入力画像信号に基づく原画像の間の二乗誤差和Ｄを導出する導出手段と、ラグランジュ未定乗数λを用いて、ラグランジュコストＣをＣ＝Ｄ＋λＲによって求めるコスト算出手段とを備え、前記画質改善フィルタを適応構成する際の最小化規準を前記ラグランジュコストＣとし、前記符号化手段は、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする。
【００１２】
本発明は、符号化された画像信号を復号する画像復号装置であって、画質改善フィルタの演算式を前記符号化された画像信号から復号する復号手段と、前記符号化された画像信号に対して前記画質改善フィルタの演算式によりフィルタ処理を施すフィルタ手段とを備え、前記復号手段は、前記画質改善フィルタによる画質改善の対象となる画素である着目画素から所定距離以上離れた複数の画素を、特定の画素値を持つ１つの画素とみなすものであり、当該特定の画素値を持つ１つの画素とみなされた画素のうち、少なくとも１つは、隣接する複数の画素を１つの画素とみなしたものであることを特徴とする。
【００１３】
本発明は、前記画像符号化方法をコンピュータに実行させることを特徴とする。
【００１４】
本発明は、前記画像復号方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、動き補償映像符号化において、参照画像の品質を高められるため、より少ない符号量でより高い品質の復号映像が得られるという効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態における画像符号化装置の構成を示すブロック図である。
【図２】図１に示すループ内フィルタ処理部１１０の処理動作を示すフローチャートである。
【図３】図２に示すフィルタ生成処理動作の詳細を示すフローチャートである。
【図４】本発明の一実施形態における画像復号装置の構成を示すブロック図である。
【図５】図４に示すループ内フィルタ処理部２０８の処理動作を示すフローチャートである。
【図６】単純な平均値フィルタの演算式を木により表現し、上位・下位ノードや最上位ノード、終端ノードを示す説明図である。
【図７】演算式の符号量の推定処理（アルゴリズム１）を示す説明図である。
【図８】与えられた木に基づくフィルタ出力値を求める処理（アルゴリズム２）を示す説明図である。
【図９】演算式の符号化処理（アルゴリズム３）を示す説明図である。
【図１０】演算式の復号処理（アルゴリズム４）を示す説明図である。
【図１１】着目画素および周辺画素値の対応例を示す説明図である。
【図１２】着目画素および周辺画素値の対応例を示す説明図である。
【図１３】フィルタの２つのパターンの例を示す説明図である。
【図１４】着目画素および周辺画素値の対称画素対の対応例を示す説明図である。
【図１５】着目画素および周辺画素の統合についての単純な例と、着目画素および周辺画素の統合例を示す説明図である。
【図１６】ＡＬＦが施すフィルタが用いる係数と画素位置の関係を、比較的単純な例で示した説明図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して、本発明の一実施形態による画像符号化装置を説明する。図１は同実施形態における画像符号化装置の構成を示すブロック図である。この画像符号化装置は、符号化対象画像の入力画像信号を入力し、入力画像信号のフレームをブロックに分割してブロック毎に符号化し、符号化データとして出力する。図１に示す画像符号化装置は、ループ内フィルタ処理部１１０を備えている点が従来技術と異なる点であり、他の構成は、Ｈ．２６４／ＡＶＣその他の画像符号化装置として用いられている従来の一般的な構成と同様であるため、図１に示す画像符号化装置の構成の説明を簡単に行う。
【００１８】
予測残差信号生成部１０３は、入力画像信号とインター予測処理部１０２あるいはイントラ予測処理部１０１の出力である予測信号との差分を求め、それを予測残差信号として出力する。変換処理部１０４は、予測残差信号に対して離散コサイン変換（ＤＣＴ）等の直交変換を行い、変換係数を出力する。量子化処理部１０５は、変換係数を量子化し、量子化後の値を出力する。逆量子化処理部１０６は、量子化後変換係数を入力し、逆量子化処理を行う。逆変換処理部１０７は、逆量子化処理部１０６の出力である逆量子化後変換係数を逆直交変換し、予測残差復号信号を出力する。復号信号生成部１０８は、この予測残差復号信号とインター予測処理部１０２あるいはイントラ予測処理部１０１の出力である予測信号とを加算し、符号化した符号化対象ブロックの復号信号を生成する。この復号信号は、イントラ予測処理部１０１にて参照画像として用いるために、フレームメモリ１０９に格納する。イントラ予測処理部１０１は、フレームメモリ１０９に格納された画像から予測モードなどを設定する。
【００１９】
また、インター予測処理部１０２において参照するために、ループ内フィルタ処理部１１０は、フレームメモリ１０９に格納した画像を入力して、符号化歪みを低減するフィルタリング処理を行い、フレームメモリ１１５に格納する。インター予測処理部１０２は、フレームメモリ１１５に格納されている過去の画像と、現在の入力画像信号から動きベクトルや動き単位などの情報を求める。ループ内フィルタ処理部１１０において設定された予測係数等の情報は、ループ内フィルタ情報格納部１１４に格納される。イントラ予測処理部１０１において設定された予測モードなどの情報は、イントラ予測情報格納部１１２に格納される。エントロピー符号化処理部１１３は、量子化処理部１０５の出力である量子化後変換係数、ループ内フィルタ情報格納部１１４に格納された予測係数等の情報、インター予測情報格納部１１１に格納された動きベクトルなどの情報及びイントラ予測情報格納部１１２に格納された予測モードなどの情報をエントロピー符号化し、符号化データとして出力する。
【００２０】
次に、図２を参照して、図１に示すループ内フィルタ処理部１１０の動作を説明する。図２は、図１に示すループ内フィルタ処理部１１０の動作を示すフローチャートである。まず、ループ内フィルタ処理部１１０は、入力画像に適した画質改善フィルタを生成する（ステップＳ１）。このステップＳ１の処理内容は後述する。次いで、ループ内フィルタ処理部１１０は、そのフィルタを符号化する（ステップＳ２）。これは後述するアルゴリズム３の処理動作によって実現できる。そして、ループ内フィルタ処理部１１０は、そのフィルタを用いて、フィルタを施した画素値を生成する（ステップＳ３）。これは後述するアルゴリズム２の処理動作によって実現できる。
【００２１】
次に、図３を参照して、図２に示すフィルタ生成処理（ステップＳ１）の詳細動作を説明する。図３は、図２に示すフィルタ生成処理（ステップＳ１）の詳細動作を示すフローチャートである。まず、ループ内フィルタ処理部１１０は、母集団生成処理により、進化の元となるフィルタ演算式の集団を生成する（ステップＳ１１）。次いで、ループ内フィルタ処理部１１０は、複製選択・子の生成処理において親集合の選択と子個体の生成を行う（ステップＳ１２）。「子の生成」は交叉、突然変異、逆位などの処理により行われる。
【００２２】
次に、ループ内フィルタ処理部１１０は、ステップＳ１２において生成した個体を用い、フィルタ画像生成処理にて、フィルタを施した画素値からなる画像を生成する（ステップＳ１３）。これは後述するアルゴリズム２の処理動作によって実現できる。次いで、ループ内フィルタ処理部１１０は、二乗誤差和Ｄ算出処理において全画面の誤差和を算出する（ステップＳ１４）とともに、その個体の情報量を木情報量Ｒ算出処理において算出する（ステップＳ１５）。これは後述するアルゴリズム１の処理動作によって実現できる。
【００２３】
次に、ループ内フィルタ処理部１１０は、ラグランジュコストＣ＝Ｄ＋λＲの値を評価値として、生存選択処理において生存するか否かを決定する（ステップＳ１６）。ラグランジュ未定乗数λは、符号化プロセスがＲＤ最適化で用いているのと同一の値であってもよいし、異なったものを別途指定してもよい。そして、ループ内フィルタ処理部１１０は、進化が収束したか否かを判定する（ステップＳ１７）。例えば、収束条件として、Ｃの減少割合が一定値（ｅ．ｇ．，０．１％）を下回る、評価回数が一定値（ｅ．ｇ．，１万回）を超える、などが適用できる。ループ内フィルタ処理部１１０は、まだ収束していないと判定されればステップＳ１２へ戻り処理を繰り返し、収束と判定されれば処理を終了する。この処理動作によって、画質改善フィルタが自動生成されることになる。
【００２４】
なお、図３に示す処理動作は、従来のループ内フィルタ処理（デブロッキングフィルタ、ＳＡＯ、ＡＬＦなど）と併用してもよいし、一部を置き換えるようにしてもよい。
【００２５】
次に、本発明の一実施形態による画像復号装置を説明する。図４は同実施形態における画像復号装置の構成を示すブロック図である。この画像復号装置は、図１に示す画像符号化装置により符号化された符号化データを入力して復号することにより復号画像の映像信号を出力する。図４に示す画像復号装置は、ループ内フィルタ処理部２０８を備えている点が従来技術と異なる点であり、他の構成は、Ｈ．２６４その他の画像復号装置として用いられている従来の一般的な構成と同様であるため、図４に示す画像復号装置の構成の説明を簡単に行う。
【００２６】
復号を行うため、エントロピー復号処理部２０１は、符号化データを入力し、復号対象ブロックの量子化後変換係数をエントロピー復号するとともに、イントラ予測、インター予測、およびループ内フィルタに関する情報を復号し、イントラ予測情報格納部２１０、インター予測情報格納１０９、ループ内フィルタ情報格納部２１１にそれぞれ格納する。逆量子化処理部２０４は、量子化後変換係数を入力し、それを逆量子化して復号変換係数を出力する。逆変換処理部２０５は、復号変換信号に逆直交変換を施し、予測残差復号信号を出力する。この予測残差復号信号とインター予測処理部２０３あるいはイントラ予測処理部２０２の出力である予測信号とを加算し、復号対象ブロックの復号信号を生成する。この復号信号は、イントラ予測処理部２０２にて参照画像として用いるために、フレームメモリ２０７に格納する。また、インター予測処理部２０３にて参照するために、ループ内フィルタ処理部２０８において、フレームメモリ２０７に格納された画像を入力して、符号化歪みを低減するフィルタリング処理を行い、出力信号として出力すると同時に、フレームメモリ２０６に格納する。ループ内フィルタ処理部２０８は、画質改善フィルタを復号し、得られた画質改善フィルタを使用して、フィルタを施した画素値を生成して出力信号として出力する。
【００２７】
次に、図５を参照して、図４に示すループ内フィルタ処理部２０８の処理動作を説明する。図５は、図４に示すループ内フィルタ処理部２０８の処理動作を示すフローチャートである。まず、ループ内フィルタ処理部２０８は、画質改善フィルタを復号する（ステップＳ２１）。これは後述するアルゴリズム４の処理動作によって実現できる。続いて、ループ内フィルタ処理部２０８は、復号したフィルタを用いて、フィルタを施した画素値を生成して出力する（ステップＳ２２）。これは後述するアルゴリズム２の処理によって実現できる。
【００２８】
次に、図１に示すループ内フィルタ処理部１１０の詳細について説明する。ループ内フィルタ処理部１１０では、「遺伝的プログラミング」と呼ばれる手法により、フィルタの演算式を自動構築する。また、そのフィルタを伝送するために必要な符号量と、そのフィルタを用いることで得られる画質の関係を、ラグランジュコストの最小化を通し最適化する。
【００２９】
遺伝的プログラミングは、生物進化にヒントを得た「手順の最適化探索」の一手法であり、手順を木で表現するものである。そして、（１）そのような木を多数生成して母集団を形成し、（２）その母集団から適宜取り出された木（親）から遺伝的手法（交叉や突然変異）により新しい木（子）を生成し、（３）その木（子）を評価して、より適したものであれば母集団に加える、という手順を繰り返すことにより、より評価の高い演算式を獲得（発見）する枠組みである。上記（３）の「評価」は、映像符号化で広く用いられているラグランジュの未定乗数法により行う。これは、別途入力されるラグランジュ未定乗数λ、フィルタを伝送するための符号量Ｒ［ｂｉｔｓ］、フィルタ後の画像と原信号の間の二乗誤差和Ｄから求まるラグランジュコストＣ＝Ｄ＋λＲを求め、Ｃが小さいほど高評価とするものである。
【００３０】
次に、木構造と演算式の対応について説明する。フィルタを表す演算式は次のように木構造により記述できる。例えば、（ｘ１＋ｘ５）／２という平均値フィルタは、図６に示すように、非終端ノードと終端ノードから構成される木構造により表現できる。ここで非終端ノードはいわゆる「関数」であり、例えば条件分岐、加減乗除、三角関数、二乗、平方根、指数・対数、絶対値、最小値、最大値など、一つあるいは複数の入力（引数）から一つの値を返すものである。これらの関数は引数をとるため、木の終端でない部分に現れるため「非終端ノード」と呼ばれる。
【００３１】
また、ノード自体が値を持つ（引数を要しない）ため木の終端に位置する「終端ノード」として、「０．１４８」のような数値や、ｘ０，ｘ１，ｘ２，・・・のような着目画素値および周辺画素値、その他符号化器と復号器で共有できる情報などがある。終端ノード及び非終端ノードは事前に用意しておくもののほか、動的に定義してもよい（automatically defined function, ADF）（例えば、文献：J. Koza: ''Genetic Programming II, Automatic Discovery of Reusable Programs'', The MIT Press, 1998参照）。
【００３２】
次に、演算式の符号量の推定について説明する。木構造を表現するのに必要なビット数は、図７に示す再帰的関数（アルゴリズム１）により求めることができる。ここで木の終端ノードが表す数値は、例えば１０ビット固定小数点整数により表現されており、各関数には０からＮ−１までの固有の通し番号がついているものとする。ＦＵＮＣＩＮＦＯは、用いる関数がＮ種類としたとき、関数を固定長符号化したときの符号量を表す以下の量である。
ＦＵＮＣＩＮＦＯ＝ｌｏｇ＿２（Ｎ＋１）
【００３３】
ここでＮ＋１となっているのは、関数の場合に加え数値（０．１４８など）の場合も含めるためである。ここでは固定長符号化を仮定しているが、関数毎の生起頻度を考慮した可変長符号化を行ってもよい。そして、着目している手順（木）の最上位ノードをｒｏｏｔとしたとき
Ｒ＝ｔｒｅｅ＿ｉｎｆｏ（ｒｏｏｔ）
を実行すれば、木の情報量Ｒが求まる。
【００３４】
次に、与えられた木に基づくフィルタ出力値について説明する。フィルタ出力値は、図８に示すように再帰的な手続き（アルゴリズム２）により求めることができる。図８においては、引数の個数が３個までの例を示しているが、引数の個数上限が４個、５個と増えても処理は同様で、容易に拡張できる。そして、着目している手順（木）の最上位ノードをｒｏｏｔとしたとき
フィルタ出力＝ｔｒｅｅ＿ｅｖａｌ（ｒｏｏｔ）
として、現在の着目画素におけるフィルタ出力値を求めることができる。
【００３５】
次に、演算式の符号化・復号について説明する。符号化も、情報量推定（アルゴリズム１）と同様に、図９に示す再帰的手続き（アルゴリズム３）で実行できる。そして、着目している手順（木）の最上位ノードをｒｏｏｔとしたとき
ｔｒｅｅ＿ｅｎｃｏｄｅ（ｒｏｏｔ）
を実行すれば、その木が符号化できる。このときの必要符号量の下限はｔｒｅｅ＿ｉｎｆｏ（ｒｏｏｔ）に一致する。
【００３６】
また復号についても同様に図１０に示す再帰的関数（アルゴリズム４）で実行できる。図１０において、「Ｆが必要とする引数の数」とは、たとえばＦがａｄｄ等の２項演算子であれば２、三項演算子あれば３、など、その関数が値を出すのに使用する値の個数（符号化側、復号側ともに既知）である。Ｆはその個数だけ下位ノードを直下に持っている。そして、
ｔｒｅｅ＿ｄｅｃｏｄｅ（）
を実行すれば、ビットストリームより木が復号され、返される。
【００３７】
画質改善フィルタ符号化は、図１１に示す入力画像において、画質改善対象画素（着目画素）の復元値（フィルタ出力値）を、それ自身の画素値（ｘ０）やその周辺の画素値ｘ１，…，ｘ８を「終端ノード」の候補に用いて、求めるものである。ここでは、９画素を示しているが、もっと広くても、または狭くてもよく、また正方形状でなくてもよい。また、画素値は映像符号化における局所復号直後の値であったり、他のループフィルタを施した後の値でもよい。
【００３８】
なお、符号化方式が上記フィルタ（デブロッキングフィルタ、ＳＡＯ、ＡＬＦ等）も用いており、かつ本実施形態のフィルタ処理がそれらフィルタの後に施される場合は、復号装置でもそれらに由来する情報（フィルタ適用・不適用領域情報や、フィルタ処理後画素値等）を用いることができるため、それらの値を終端ノード候補に含めてもよい。
【００３９】
このように、従来のループフィルタにおいては入力画像の画素値に関する線形な処理でのみフィルタ結果を求めていたところ、本実施形態では遺伝的プログラミングにより、線形の範疇にとらわれないフィルタを次々と生成させるようにしたため、フィルタ設計の自由度を飛躍的に高めることができる。また、生成されたフィルタはラグランジュコストにより符号量−歪みの面で評価し、生存選択を行うようにしたため、必ず性能を改善したフィルタが生き残り、従来のループフィルタを用いては達成できなかった高い符号化効率を達成することができる。
【００４０】
また、画質改善フィルタ符号化は、前述の説明では、ｘ１，…，ｘ８の８個あった画素値を、着目画素に対して対称な位置にある画素対の平均値ａ１，…，ａ４の４個に縮退させるようにしてもよい。例えば図１２に示す復号画素値は
ａ１＝（ｘ１＋ｘ５）／２
ａ２＝（ｘ２＋ｘ６）／２
ａ３＝（ｘ３＋ｘ７）／２
ａ４＝（ｘ４＋ｘ８）／２
のようになる。この図の例では、ｘ０，ａ１，…，ａ４が演算式を生成する終端ノードの候補となる。もちろんこれより減らしてもよいし、外へ増やしてもよい。
【００４１】
簡単な例として、参照できる画素値がｘ１，ｘ２，ｙ１，ｙ２のみの場合、各画素値を表現するのに２ビットが必要である。
ｘ１  ０１
ｘ２  ００
ｙ１  １０
ｙ２  １１
【００４２】
縮退した場合は次のように１ビットで表現できる。
ａ１  ０
ａ２  １
このように、より短い符号語で表現できる。
【００４３】
一般に、画像を左右反転させても、その絵柄はほとんど変わらない。また局所的に見れば、画像を上下反転させても絵柄は変わらない。このことから、ある着目画素に対し、それと対称位置にある２画素のもつ関係、あるいは着目画素の値への、対称画素対からの寄与はどちらからも同じと考えてよい。このような画像の性質に鑑み、例えばＡＬＦでは、対称な画素対についてはフィルタ係数値を同一にして、伝送すべき係数の個数を約半分に削減している。図１３において、２パターン用意されているフィルタのパターンのうち、パターンＡではＣ０…Ｃ８の９係数を伝送し、例えばＣ０は左上と右下の、対象画素対に等しく乗じられその積がフィルタ結果導出に用いられる。パターンＢでも同様で、Ｃ０…Ｃ７の８係数を伝送し、例えばＣ０は上端と下端の対称画素対に等しく乗じられその積がフィルタ結果導出に用いられる。
【００４４】
このように、終端ノードの候補数を削減することで、演算式の多様性の爆発を抑制し、もって遺伝的プログラミングによる優良演算式の生成を高速化することができるほか、演算式の表現に要する符号量も削減することができる。
【００４５】
対称画素対を表現するのに前述した説明では２個の終端ノードとして表現されていたがここでは一個の終端ノード（画素対の平均値）として表現する（ノード表現の自由度を制約する）ため、終端ノードの個数が削減されることになり、演算式の情報量を削減することができる。したがって、より少ない符号量でフィルタを生成することができる。
【００４６】
また、終端ノードの種類が減るため、遺伝的プログラミングの生成しうるフィルタのバリエーションが限定され、より高速にフィルタを生成することができる。また、画像特有の性質（統計的に対称画素の性質は等しい）に着目するようにしたため、生成されたフィルタの画質改善性能は、より自由度の高いフィルタと遜色がない。従って、より少ない符号量でほぼ同じ画質改善性能をもつフィルタを、より高速に生成することができる。
【００４７】
また、画質改善フィルタ符号化は、図１４に示すように、着目画素位置に関して対称な画素対（ｘ１とｙ１、ｘ２とｙ２、ｘ３とｙ３、・・・）をｘｎとｙｎと名付け、フィルタを表す演算式が
０．２（ｘ１＋ｙ１）＋０．１（ｘ２＋ｙ２）、
ｅｘｐ（（ｘ１＋ｙ１）／ｔａｎ（ｘ２  ×  ｙ２））
のように、画素対ｘｎ，ｙｎについて対称な（ｘｎとｙｎを交換しても値が変化しない）式となるよう限定し進化を効率化するようにしてもよい。このような式を「ｘｙ対称式」と呼ぶこととする。ｘｙ対称式は対称画素対からの寄与が等しくなる（ｘｎからもｙｎからも寄与が等しい）ので、前述の理由で画像のフィルタに適している。
【００４８】
なお、いわゆる「対称多項式」は多項式に限定した対称式であり、ここでは、多項式以外も含む、より一般的な形態のものを、「ｘｙ対称式」は指している。上記の演算式の例において、ｘ１とｙ１、ｘ２とｙ２を交換すると
０．２（ｙ１＋ｘ１）＋０．１（ｙ２＋ｘ２）、
ｅｘｐ（（ｙ１＋ｘ１）／ｔａｎ（ｙ２  ×  ｘ２））
となるが、交換前と完全に等価であることは明らかである。
【００４９】
例えばｘｙ対称式でないものは、
ｘ１＋０．１×ｙ１、
ｘ１／ｙ１
などである。
【００５０】
ｘｙ対称式を生成する方法は以下の通りである。
（１）差と偶関数による生成・・・ｅ（ｆ（ｘｎ，ｙｎ）−ｆ（ｙｎ，ｘｎ））
（２）変数交換と積による生成・・・ｆ（ｘｎ，ｙｎ）  ×  ｆ（ｙｎ，ｘｎ）
（３）変数交換と和による生成・・・ｆ（ｘｎ，ｙｎ）  ＋  ｆ（ｙｎ，ｘｎ）
（４）複数のｘｙ対称式の結合・・・ｆ（ｓ１（ｘｎ，ｙｎ），ｓ２（ｘｍ，ｙｍ），．．．）
（５）上記（４）の特別な場合・・・ｆ（ｓ（ｘｎ，ｙｎ））
【００５１】
但し、ｆ（ｘ，ｙ）は任意の関数、ｓ（ｘ，ｙ），ｓ１（ｘ，ｙ），ｓ２（ｘ，ｙ），…はｘｙ対称式、ｅ（ｘ）は偶関数（ｅ（ｘ）＝ｅ（−ｘ）となる関数）、ｘｎ，ｙｎとｘｍ，ｙｍは別の対称画素対（同じでもよい）である。
【００５２】
例えば、以下のｘｙ対称式において、
ｃｏｓ（ｘ１−ｙ１）・・・（１）のケース（ｃｏｓは偶関数である）、
ｘ１×ｙ１・・・（２）２のケース、
ｓｉｎ（ｘ１）＋ｓｉｎ（ｙ１）・・・（３）のケース
ｓｉｎ（ｘ１  ×  ｙ１）・・・（４）のケース
から生成されている。
【００５３】
一旦生成されたｘｙ対称式は、（４）のケースの組み合わせによりいくらでも複雑にしていくことができる。はじめに示した例では、
０．２（ｘ１＋ｙ１）＋０．１（ｘ２＋ｙ２）・・・（３）と（４）のケースの組み合わせ
ｅｘｐ（（ｘ１＋ｙ１）／ｔａｎ（ｘ２×ｙ２））・・・（２）、（３）、（４）のケースの組み合わせ
である。
【００５４】
このように、画像に向かない可能性の高い「ｘｎ，ｙｎについて対称でない式」の生成を排除し、より画像に向くと思われるｘｙ対称式からなる演算式を生成・評価することができるため、遺伝的プログラミングによる優良演算式の生成を高速化することができる。また、「ｘｎ，ｙｎの対を表す符号語」を用意しておくことで、ｘｎとｙｎを独立に与える場合よりも短い符号量で演算式を表現できる。
【００５５】
簡単な例として、参照できる画素値がｘ１，ｘ２，ｙ１，ｙ２のみ場合、最初の１ビットが０なら個別画素値、続く２ビットで識別、最初の１ビットが１なら画素値対、続く１ビットで識別することとする。
ｘ１  ００１
ｘ２  ０００
ｙ１  ０１０
ｙ２  ０１１
（ｘ１，ｙ１）  １０
（ｘ２，ｙ２）  １１
【００５６】
ここで、１０，１１が「ｘｎ，ｙｎの対を表す符号語」であり、（ｘ１，ｙ１）を表現するのに１０の２ビットで済むのに対し、個別に表現する場合は００１（ｘ１）０１０（ｙ１）と、６ビットが必要になる。
【００５７】
このように、画像特有の性質（統計的に対称画素の性質は等しい）に着目し、画素値対の平均を用いていたものを一般化し、画素値対に関する対称式（平均も含む）を扱うようにするようにしたため、得られるフィルタは自由度が高いものとなる。したがって、生成されたフィルタの画質改善性能は、より高い性能が期待できる。また、非対称式の生成が自動的に排除されるように組織的対称式生成を行うようにしたため、高速に対称式を含む画質改善フィルタを生成することができる。したがって、画質改善性能をもつフィルタを、高速に生成することができる。
【００５８】
また、画質改善フィルタ符号化は、着目画素位置から比較的離れた画素については、複数統合して１画素とみなし、特定の値とするようにしてもよい。例えば、図１５（ａ）に示すように、ｘ６より遠い画素について、ｘ７やｘ８のように、３画素を例えばその平均値にて代表させる。また、このパターンは任意であり、例えば図１５（ｂ）に示すように、ｘ１０より遠い画素を適宜統合するなど、無数に考えられる。いずれにおいても、ｘ０に対して対称な画素については説明を省略している。ここでは、対称位置の画素との平均値を用いたり、対称画素対を特別に扱うようにすることが可能である。
【００５９】
これにより、着目画素への寄与が比較的小さい遠方の画素をまとめることで、例えばフィルタ係数の個数を削減することができるほか、広い領域を参照しつつも画素値の種類は抑えることで、演算式の多様性の爆発を抑制し、もって遺伝的プログラミングによる優良演算式の生成を高速化することができるほか、演算式の表現に要する符号量も削減できる。
【００６０】
このように、画像特有の性質（画素間の相関は距離に応じて下がる）に着目し、１画素値あるいは１画素値対にひとつの終端ノードが対応していたものと異なり、画質復元対象画素からある程度離れた領域においては、複数画素をまとめて平均値で代表させるようにしたため、生成されたフィルタの画質改善性能は、より自由度の高いフィルタと遜色がない。また、終端ノードの種類が減るため、遺伝的プログラミングの生成しうるフィルタのバリエーションが限定され、より高速にフィルタを生成することができる。
【００６１】
なお、図１、図４における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより画像符号化処理及び画像復号処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６２】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００６３】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。したがって、本発明の精神及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行っても良い。
【産業上の利用可能性】
【００６４】
画像・映像の非可逆符号化において、映像品質の改善および符号化ビットレートの削減を目的として、画像の符号化・復号を行うが不可欠な用途に適用できる。
【符号の説明】
【００６５】
１０１・・・イントラ予測処理部、１０２・・・インター予測処理部、１０３・・・予測残差信号生成部、１０４・・・変換処理部、１０５・・・量子化処理部、１０６・・・逆量子化処理部、１０７・・・逆変換処理部、１０８・・・復号信号生成部、１０９・・・フレームメモリ、１１０・・・ループ内フィルタ処理部、１１１・・・インター予測情報格納部、１１２・・・イントラ予測情報格納部、１１３・・・エントロピー符号化処理部、１１４・・・ループ内フィルタ情報格納部、１１５・・・フレームメモリ、２０１・・・エントロピー復号処理部、２０２・・・イントラ予測処理部、２０３・・・インター予測処理部、２０４・・・逆量子化処理部、２０５・・・逆変換処理部、２０６・・・フレームメモリ、２０７・・・フレームメモリ、２０８・・・ループ内フィルタ処理部、２０９・・・インター予測情報格納部、２１０・・・イントラ予測情報格納部、２１１・・・ループ内フィルタ情報格納部
【図１】
2015167423.tif 000003
【図２】
2015167423.tif 000004
【図３】
2015167423.tif 000005
【図４】
2015167423.tif 000006
【図５】
2015167423.tif 000007
【図６】
2015167423.tif 000008
【図７】
2015167423.tif 000009
【図８】
2015167423.tif 000010
【図９】
2015167423.tif 000011
【図１０】
2015167423.tif 000012
【図１１】
2015167423.tif 000013
【図１２】
2015167423.tif 000014
【図１３】
2015167423.tif 000015
【図１４】
2015167423.tif 000016
【図１５】
2015167423.tif 000017
【図１６】
2015167423.tif 000018