(57)【特許請求の範囲】
【請求項１】
近傍に位置するデジタル信号どうしの相関を利用し、線形予測に用いる全ての予測係数の絶対値和の総和の上限を定める制約の下で予測誤差の２乗和を最小化するように線形予測を行う線形予測器を用いてデジタル信号を線形予測するための予測係数を出力する線形予測係数出力装置であって、
予測するデジタル信号を、行列をなす前記予測係数と、列ベクトルをなす参照するデジタル信号とが乗算された列ベクトルとして表現することにより、前記予測係数を複数の前記線形予測器の集合として扱い、前記予測係数を出力する予測係数出力部を備え、
前記予測係数出力部は、
前記予測係数の一部であり前記デジタル信号を予測するために必要とする前記予測係数を単信号予測係数とし、該単信号予測係数の絶対値和の増加量と前記予測誤差の減少量の比である予測誤差削減効率に基づき、非零値であり用いられる前記予測係数の位置を前記行列において定めるため、前記線形予測器の集合を構成する線形予測器であってＬ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器にＬ１ノルムを分配し、Ｌ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器へのＬ１ノルムの再分配を、分配及び再分配されたＬ１ノルムの総和があらかじめ定められた値となるまで行い、Ｌ１ノルムが分配若しくは再分配された位置を、用いられる前記予測係数の位置として定め、定められた位置に、予測誤差の２乗和を最小化する値を予測係数として設定し、設定された予測係数を出力する、
線形予測係数出力装置。
【請求項２】
前記デジタル信号を区間に分割し、分割した区間を少なくとも１つのクラスに分類するクラス分類部をさらに備え、前記予測係数出力部は、前記クラスごとに前記予測係数を出力する、請求項１に記載の線形予測係数出力装置。
【請求項３】
近傍に位置するデジタル信号どうしの相関を利用し、線形予測に用いる全ての予測係数の絶対値和の総和の上限を定める制約の下で予測誤差の２乗和を最小化するように線形予測を行う線形予測器を用いてデジタル信号を線形予測するための予測係数を出力する線形予測係数出力方法であって、
予測するデジタル信号を、行列をなす前記予測係数と、列ベクトルをなす参照するデジタル信号とが乗算された列ベクトルとして表現することにより、前記予測係数を複数の前記線形予測器の集合として扱い、前記予測係数を出力する予測係数出力ステップを有し、
前記予測係数出力ステップでは、
線形予測係数出力装置は、
前記予測係数の一部であり前記デジタル信号を予測するために必要とする前記予測係数を単信号予測係数とし、該単信号予測係数の絶対値和の増加量と前記予測誤差の減少量の比である予測誤差削減効率に基づき、非零値であり用いられる前記予測係数の位置を前記行列において定めるため、前記線形予測器の集合を構成する線形予測器であってＬ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器にＬ１ノルムを分配し、Ｌ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器へのＬ１ノルムの再分配を、分配及び再分配されたＬ１ノルムの総和があらかじめ定められた値となるまで行い、Ｌ１ノルムが分配若しくは再分配された位置を、用いられる前記予測係数の位置として定め、定められた位置に、予測誤差の２乗和を最小化する値を予測係数として設定し、設定された予測係数を出力する、
線形予測係数出力方法。
【請求項４】
コンピュータを、請求項１または２に記載の線形予測係数出力装置として機能させるための線形予測係数出力プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル信号に対する線形予測のための予測係数を出力する線形予測係数出力装置、線形予測係数出力方法及び線形予測係数出力プログラムに関する。
【背景技術】
【０００２】
高能率な映像符号化を実現するには、イントラ予測の予測誤差低減は重要な課題となる。同一フレーム内における隣接画素値間の相関除去を目的として、周辺画素値を用いた画素値予測処理がＨ．２６３（動画圧縮方式の規格）から導入された。Ｈ．２６３ではＤＣ成分に対する予測のみを行っている。Ｈ．２６４／ＡＶＣ（動画圧縮方式の規格）ではＰｌａｎｅ予測や９通りの方向性予測が追加された。更に、Ｈ．２６５／ＨＥＶＣ（動画圧縮方式の規格）ではＰｌａｎｅ予測を改善したＰｌａｎａｒ予測が追加されると共に方向性予測の方向数を３３通りに増加した。
【０００３】
しかし、Ｈ．２６５／ＨＥＶＣは予測誤差を低減する余地が残されている。ＨＥＶＣのイントラ予測は、画素値変化の方向が直線的であることを仮定している。また、映像によらず予測器の数や種類が固定されている。従って、画素値変化の方向が直線的でない場合、予測誤差が増大する。また、特定の予測器が使用されない場合、予測情報表現に要する符号量が増大する。従って、予測誤差低減のため、映像毎に適切な予測器を構築する必要がある。
【０００４】
映像毎に予測器を定める方法として、画像ごとに複数の線形予測器を設計する方法がある（例えば、非特許文献１参照）。非特許文献１では１枚の画像を矩形ブロックに分割し、矩形ブロックごとに予測を行う。また、各矩形ブロックを複数種類のクラスへ分類し、クラスごとに適応的な予測器の設計が行われる。以降では、予測処理の単位となる矩形ブロックを予測ブロックと呼ぶ。
【０００５】
非特許文献１では予測ブロックを最小単位である１画素として定めている。予測ブロック内の画素値と原画像の画素値の誤差である予測誤差は低く抑えることが望ましい。一方で、同一画像内の各予測ブロックはそれぞれ信号特性が異なる。そこで、類似した信号特性を持つ予測ブロックを１つのクラスにまとめ、各クラスに対して予測誤差の少ない予測器が設計されている。クラス分類の方法として、非特許文献１は付加情報を用いずに予測ブロック周辺の近傍画素値の分散を用いた分類を行っている。
【０００６】
非特許文献１では予測ブロック内の画素値予測に式（１）に示す線形予測を用いる。
【数１】
0006649184.tif 000002
ここで、ｉは予測ブロックの番号を示す指数、ｃはクラス番号であり、１からＣまでとりうる。＾ｘｉ＝（＾ｘｉ１，・・・，＾ｘｉｌ，・・・，＾ｘｉＭｉ）Ｔ（＾は後に続く文字の上に付く、以下同様）は参照画素を要素とするＭｉ次元の列ベクトルである。Ｍｉは予測に用いる参照画素数である。＾ｙｉｃは予測ブロックにおける予測画素値である。非特許文献１では予測ブロックの大きさが１×１であるため、１次元の実数である。ｂｃはクラスｃにおける予測係数であり、Ｍｉ次元行ベクトルである。
【０００７】
各クラスの予測係数ｂｃに対し予測誤差を最小化する係数を設定する方法は、Ｗｉｅｎｅｒ−Ｈｏｐｔ方程式と呼ばれる線形連立方程式を解くことで容易に設計できることが知られている。以上説明した事項は非特許文献１に詳述されている。
【０００８】
非特許文献１の線形予測を拡張し、画素単位でない予測ブロック内の正規化された画素値に対する線形予測は、式（２）と記述できる。
【数２】
0006649184.tif 000003
ここで、ｉは予測ブロックの番号を示す指数、ｃはクラス番号であり、１からＣまでとりうる。＾ｘｉ＝（＾ｘｉ１，・・・，＾ｘｉｌ，・・・，＾ｘｉＭｉ）Ｔは正規化処理を施した参照画素を要素とするＭｉ次元の列ベクトルである。Ｍｉは予測に用いる参照画素数である。＾ｘｉは、以下のように正規化されているとする。
【数３】
0006649184.tif 000004
ここで、￣ｘｉ＝（￣ｘｉ１；，・・・，￣ｘｉｌ，・・・，￣ｘｉＭｉ）Ｔ（￣は後に続く文字の上に付く、以下同様）は正規化処理を施していない参照画素を要素とするＭｉ次元の列ベクトルである．Ｓｃはクラス番号ｃを選択する予測ブロック番号の集合である．μｘｌは、クラスｃに属するｌ番目の参照画素値￣ｘｉｌの平均値である．σｘｌは、クラスｃに属するｌ番目の参照画素値の標準偏差である。
【０００９】
＾ｙｉｃ＝（＾ｙｉｃ［１］，・・・，＾ｙｉｃ［ｊ］，・・・，＾ｙｉｃ［Ｍｉ］）Ｔは正規化処理を施した予測ブロック内の画素値を要素とするＭｏ次元の列ベクトルである。＾ｙｉｃは以下のように正規化されているとする。
【数４】
0006649184.tif 000005
ここで、￣ｙｉｃ＝（￣ｙｉｃ［１］，・・・，￣ｙｉｃ［ｌ］，・・・，￣ｙｉｃ［Ｍｏ］）Ｔは正規化処理を施していない予測ブロック内の画素値を要素とするＭｉ次元の列ベクトルである．μｉｃ［ｊ］は、クラスｃに属するｌ番目の被予測画素値￣ｘｉｌの平均値である。Ｍｏは予測ブロックの画素数である。ｊは予測ブロック内の画素位置を示す指数である。Ａｃはクラスｃにおける予測係数であり、列数がＭｉ、行数がＭｏの実数値行列である。ｊ行目の予測係数により、ｊ番目の予測ブロック内画素値を予測する。
【００１０】
正規化されていない実際の予測画素値〜ｙｉｃ（〜は後に続く文字の上に付く、以下同様）は以下のように算出される。
【数５】
0006649184.tif 000006
以降では、参照画素、予測ブロック内のいずれに対しても正規化処理を施しているものとする。
【００１１】
画像ごとに線形予測に用いる係数方法は予測係数が付加情報となるため、予測係数の発生符号量の抑制が課題となる。予測係数の発生符号量を抑制する方法として、予測係数の多くが零値であるスパースの状態にする制約条件の下、予測誤差を低減する予測係数を設定する方法がある。
【００１２】
予測係数の多くが零値である場合、予測係数表現に要する符号量を削減できるため、付加情報として送信する予測係数の符号量の削減が見込まれる。一方で、零値の予測係数が多すぎると予測誤差が増大してしまうため、予測誤差表現に要する符号量の増大や復号画像の画質劣化を招いてしまう。
【００１３】
スパース性（予測係数の多くが零値である）を課した制約条件の下で予測誤差を最小化する方法の一つとして、下記に示すＬ０ノルムに関する制約付き二乗誤差最小化問題が挙げられる。
【数６】
0006649184.tif 000007
ここで、Ｓｃはクラス番号ｃを選択する予測ブロック番号の集合である。‖Ａｃ‖０は、行列Ａｃにおける非零値である係数の個数である。予測係数の符号量は非零値である予測係数の個数に依存するため、非零値の係数の個数に関する制約条件は予測係数に要する符号量を調整する役割を持つ。
【００１４】
しかし、式（６）における最適解求解は困難であるため、次式（７）で示す制約条件に緩和して求解する方法が考えられる。
【数７】
0006649184.tif 000008
ここで、‖Ａｃ‖１は、行列Ａｃにおける非零値である係数の絶対値の総和である。θ１は、予測係数Ａｃの絶対値和を全クラスに関して取った総和に対して課す上限である。以降では、上記θ１を総和上限と呼ぶ。総和上限を定める制約条件を付与することで、経験的にスパース性を有する予測係数が得られる。総和上限は全クラスに渡った行列内における零値の係数を含む割合を調整する。
【００１５】
式（２）で示される予測係数は予測ブロック内の各画素を独立に予測しており、予測係数Ａｃのｊ行目の係数を用いてｊ番目の予測ブロック内画素値が予測される。すなわち、Ａｃ＝（ａｃ［１］Ｔ，・・・，ａｃ［ｊ］Ｔ，・・・，ａｃ［Ｍｏ］Ｔ）Ｔと表記すると、ａｃ［ｊ］はクラスｃに属する予測ブロックのｊ番目の画素値を予測するための係数であり、Ｍｉ次元の行ベクトルである。以降では、上記ａｃ［ｊ］を単画素予測係数と呼ぶ。
【００１６】
単画素予測係数ａｃ［ｊ］および参照画素ｘｉを用いてクラスｃに属するｉ番目の予測ブロック内のｊ番目の画素値はａｃ［ｊ］ｘｉと予測される。上記Ｌ１ノルムによる制約条件を付与した最適化問題において、特にクラス数Ｃが１種類かつ予測ブロック内の画素数Ｍｏが１個である場合、予測係数を定める最適化問題はＬＡＳＳＯ（線形回帰を実行するための正則化手法）と同一の問題として定義され、様々な解法が知られている。
【００１７】
なお、本明細書において、画像とは、静止画像、または動画像を構成する１フレーム分の画像のことをいう。また映像とは、動画像と同じ意味であり、一連の画像の集合である。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】松田一朗、森弘史、前田譲治、伊東晋、可逆符号化のためのレートを最小とする予測器の設計と評価、電子情報通信学会論文誌Ｄ−ＩＩ、Ｖｏｌ．Ｊ８５、Ｎｏ．３、ｐｐ．４４８−４５６、２００２．
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかしながら、クラス数Ｃが複数種類である場合や予測ブロック内の画素数Ｍｏが複数存在する場合において、制約条件を式（７）に緩和した最適化問題の求解方法は今まで検討されてこなかった。ＬＡＳＳＯの求解アルゴリズムはクラス数ＣおよびＭｏを１と限定した定式化および制約条件を定めている。従って、クラス数ＣおよびＭｏを１より大きな設定した場合の最適解もしくは凖最適解を効率的に求める手法が存在しないため、上記条件の下で式（２）における予測誤差削減には改善の余地が残されている。
【００２０】
本発明は、このような事情に鑑みてなされたもので、デジタル信号に対する線形予測を行うためのスパース性（非零値の係数がまばらに存在すること）を有する予測係数を効率的に出力することができる線形予測係数出力装置、線形予測係数出力方法及び線形予測係数出力プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明の一態様は、近傍に位置するデジタル信号どうしの相関を利用し、線形予測に用いる全ての予測係数の絶対値和の総和の上限を定める制約の下で予測誤差の２乗和を最小化するように線形予測を行う線形予測器を用いてデジタル信号を線形予測するための予測係数を出力する線形予測係数出力装置であって、予測するデジタル信号を、行列をなす前記予測係数と、列ベクトルをなす参照するデジタル信号とが乗算された列ベクトルとして表現することにより、前記予測係数を複数の前記線形予測器の集合として扱い、前記予測係数を出力する予測係数出力部を備え、前記予測係数出力部は、前記予測係数の一部であり前記デジタル信号を予測するために必要とする前記予測係数を単信号予測係数とし、該単信号予測係数の絶対値和の増加量と前記予測誤差の減少量の比である予測誤差削減効率に基づき、非零値であり用いられる前記予測係数の位置を前記行列において定めるため、前記線形予測器の集合を構成する線形予測器であってＬ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器にＬ１ノルムを分配し、Ｌ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器へのＬ１ノルムの再分配を、分配及び再分配されたＬ１ノルムの総和があらかじめ定められた値となるまで行い、Ｌ１ノルムが分配若しくは再分配された位置を、用いられる前記予測係数の位置として定め、定められた位置に、予測誤差の２乗和を最小化する値を予測係数として設定し、設定された予測係数を出力する、線形予測係数出力装置である。
【００２３】
本発明の一態様は、前記線形予測係数出力装置であって、前記デジタル信号を区間に分割し、分割した区間を少なくとも１つのクラスに分類するクラス分類部をさらに備え、前記予測係数出力部は、前記クラスごとに前記予測係数を出力する。
【００２６】
本発明の一態様は、近傍に位置するデジタル信号どうしの相関を利用し、線形予測に用いる全ての予測係数の絶対値和の総和の上限を定める制約の下で予測誤差の２乗和を最小化するように線形予測を行う線形予測器を用いてデジタル信号を線形予測するための予測係数を出力する線形予測係数出力方法であって、予測するデジタル信号を、行列をなす前記予測係数と、列ベクトルをなす参照するデジタル信号とが乗算された列ベクトルとして表現することにより、前記予測係数を複数の前記線形予測器の集合として扱い、前記予測係数を出力する予測係数出力ステップを有し、前記予測係数出力ステップでは、線形予測係数出力装置は、前記予測係数の一部であり前記デジタル信号を予測するために必要とする前記予測係数を単信号予測係数とし、該単信号予測係数の絶対値和の増加量と前記予測誤差の減少量の比である予測誤差削減効率に基づき、非零値であり用いられる前記予測係数の位置を前記行列において定めるため、前記線形予測器の集合を構成する線形予測器であってＬ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器にＬ１ノルムを分配し、Ｌ１ノルムを分配したときに前記予測誤差削減効率が最も大きい線形予測器へのＬ１ノルムの再分配を、分配及び再分配されたＬ１ノルムの総和があらかじめ定められた値となるまで行い、Ｌ１ノルムが分配若しくは再分配された位置を、用いられる前記予測係数の位置として定め、定められた位置に、予測誤差の２乗和を最小化する値を予測係数として設定し、設定された予測係数を出力する、線形予測係数出力方法である。
【００２７】
本発明の一態様は、コンピュータを、前記線形予測係数出力装置として機能させるための線形予測係数出力プログラムである。
【発明の効果】
【００２８】
本発明によれば、デジタル信号に対する線形予測を行うためのスパース性（非零値の係数がまばらに存在すること）を有する予測係数を効率的に出力できるという効果が得られる。
【図面の簡単な説明】
【００２９】
【図１】本発明の実施形態におけるロスレス符号化を行う場合の動画像符号化装置の構成を示すブロック図である。
【図２】図１に示すイントラ予測部４００の詳細な構成を示すブロック図である。
【図３】図２に示すイントラ予測部４００の動作を示すフローチャートである。
【図４】図２に示すイントラ予測係数生成部４０２の第１の構成を示すブロック図である。
【図５】図４に示すイントラ予測係数生成部４０２の動作を説明するフローチャートである。
【図６】図２に示すイントラ予測係数生成部４０２の第２の構成を示すブロック図である。
【図７】図６に示すイントラ予測係数生成部４０２の動作を説明するフローチャートである。
【図８】図２に示すイントラ予測係数生成部４０２の第３の構成を示すブロックである。
【図９】図２に示すイントラ予測係数生成部４０２の第４の構成を示すブロックである。
【図１０】本発明の実施形態による動画像復号装置の構成を示すブロック図である。
【図１１】図１０に示すイントラ予測部８００の詳細な構成を示すブロック図である。
【図１２】図１１に示すイントラ予測部８００の動作を示すフローチャートである。
【図１３】線形予測によるイントラ予測の定式化を示す説明図である。
【図１４】適応的なイントラ予測器の目的と課題を示す説明図である。
【図１５】適応的なイントラ予測器の目的と課題を示す説明図である。
【図１６】適応的なイントラ予測器の動作を示す説明図である。
【図１７】予測器の符号量を削減する動作を示す説明図である。
【図１８】スパースな予測係数を設定するＳＴＥＰ２の詳細な動作を示す説明図である。
【図１９】Ｌ１ノルム正則化項に基づく定式化を示す説明図である。
【図２０】Ｌ１ノルム正則化項に基づく定式化を示す説明図である。
【図２１】複数予測器設計の最適化の動作を示す説明図である。
【図２２】複数予測器設計の最適化の動作を示す説明図である。
【図２３】複数予測器設計の最適化の動作を示す説明図である。
【図２４】複数予測器設計の最適化の動作を示す説明図である。
【図２５】複数予測器設計の最適化の動作を示す説明図である。
【図２６】複数予測器設計の最適化の動作を示す説明図である。
【図２７】複数予測器設計の最適化の動作を示す説明図である。
【図２８】複数予測器設計の最適化の動作を示す説明図である。
【図２９】ＳＴＥＰ２−１で得られる非ゼロ係数位置を示す説明図である。
【発明を実施するための形態】
【００３０】
以下、図面を参照して、本発明の一実施形態による線形予測係数出力装置を説明する。はじめに線形予測係数を出力する原理について説明する。式（７）で示される最適化問題を求解するため、まず、式（７）は下記の式（８）で示す単画素予測係数の設計問題に書き換える。
【数８】
0006649184.tif 000009
ここで、θｃ［ｊ］は各単画素予測係数に対して定める係数の絶対値和の上限である。以降では、上記θｃ［ｊ］を単一上限と呼ぶ。式（８）で示される最適化問題は複数のＬＡＳＳＯを含んでおり、全てのクラスおよび予測ブロック内画素に関する単一上限の総和が総和上限となる制約条件が設けられている。
【００３１】
上記最適化問題を求解するために、全てのクラスおよび予測ブロック内画素に対する単一上限θｃ［ｊ］を決定する必要がある。複数のＬＡＳＳＯにおけるｃ［ｊ］の設定を行う際、計算量の低減を目的として、Least Angle Regression（ＬＡＲＳ）（参考文献１参照）を拡張する。
参考文献１：Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani.Least Angle Regression. The Annals of Statistics, Vol. 32, No. 2, pp.407-499、2004.
【００３２】
ＬＡＲＳは、ＬＡＳＳＯにおけるあらゆる単一上限に対応する単画素予測係数を、１度の最適化で出力できる。上記最適化の結果、各θｃ［ｊ］に対応する単画素予測係数ａｃ［ｊ］∈ＲＭｏが、ＲＭｏの空間内における複数の連結した線分の集合として与えられる。以降では、上記の線分の集合をパスと呼ぶ。パス上の各点は、θｃ［ｊ］＝‖ａｃ［ｊ］‖１と設定した際のＬＡＳＳＯの解と対応付けられる。
【００３３】
また、パスにおける線分と線分の連結箇所でのみ、（１）１つの係数が非零値から零値になる、（２）１つの係数が零値から非零値になる、のいずれかが起こる。θｃ［ｊ］の設定を行う際、パスが求まっていればθｃ［ｊ］を変更した際の単画素予測係数ａｃ［ｊ］を求めるための計算時間を削減できる。
【００３４】
従って、本実施形態ではＬＡＲＳの拡張により、式（８）に示す最適化問題を求解する。ＬＡＲＳを拡張する準備として、各単画素予測係数に対して、下記の式（９）ように予測誤差削減効率ｅｃ［ｊ］を定義する。
【数９】
0006649184.tif 000010
ここで、ｆｃ［ｊ］は入力された単画素予測係数ａｃ［ｊ］を使用した際の予測誤差の総和を返す関数である。ａｃ［ｊ］は、現在の単画素予測係数である。ｄｃ［ｊ］は、現在の単画素予測係数を更新する際の差分を表すベクトルである。予測誤差削減効率の式（９）は、単画素予測係数の絶対値和の増加量に対する予測誤差の低減量を表す。
【００３５】
ＬＡＲＳでは、パスを辿ることで予測誤差削減効率が常に最大となるよう係数を設定できる。以降の説明においては、予測誤差削減効率は常に式（９）を意味する。また、上記内容は参考文献１に詳述されている。
【００３６】
提案するＬＡＲＳの拡張は、同時に最適化する各単画素予測係数ａｃ［ｊ］の予測誤差削減効率ｅｉ（ｊ）が比較される。そして、最も予測誤差削減効率が高い単画素予測係数ａｃ［ｊ］に対してパスを１線分だけ進める操作を、非零値の係数が一定割合に到達するまで続けるというものである。これにより、予測誤差削減効率という指標に基づきＬＡＳＳＯ同士を比較し、予測誤差削減効率の良い係数を設定できる。
【００３７】
また、非零値の係数が一定割合に到達した場合、各単画素予測係数ａｃ［ｊ］の絶対値和を、ＬＡＳＳＯにおける係数の絶対値和の上限θｃ［ｊ］に設定して最適化を行ったとみなせる。従って、提案するＬＡＲＳの拡張により、各ＬＡＳＳＯにおける絶対値和の上限θｃ［ｊ］が設定できる。
【００３８】
次に、図１３〜図２９を参照して、予測係数を出力する動作を説明する。図１３は、線形予測によるイントラ予測の定式化を示す説明図である。イントラ予測では、１枚の画像を矩形状のブロックに分割し、分割されたブロックごとに、ブロック周辺の参照画素を用いて、被予測画素ブロックの予測が行われる。このとき、用いる参照画素を適応的に選択して予測が行われる。本実施形態の具体的なイントラ予測は、図１３に示す線形予測器の式で示す線形予測により予測する。参照画素を縦に並べたベクトルｘに対して、参照画素を使う位置と重みを定める予測係数Ａをかけることで、被予測画素の予測値を縦に並べたベクトル＾ｙが出力される。
【００３９】
ＨＥＶＣのイントラ予測においても、この線形予測で表現されるが、その係数は映像によらず固定されている。しかし、本実施形態では、１枚のフレームごとにこの予測係数の各要素が適応的に設定される。また、１枚の画像を矩形状のブロックに分割した後、類似した予測を必要とするブロックを１つのクラスとしてまとめ、クラスごとに予測係数Ａを用意する。例えば、３種類のクラスを用意した場合、各ブロックが３種類のクラスのいずれかに分類される。そして、それぞれクラスに１つの予測器が使用される。このとき、ＨＥＶＣでは全ての映像に対して予測器の数、すなわちクラス数が固定されている。これを、本実施形態では、１枚のフレームごとにクラス数が適応的に設定される。
【００４０】
このような問題を考える場合、２つの要素を最適化する必要がある。１つ目は、各ブロックがどのクラスを選べば予測誤差が小さくなるかという、クラス分類の最適化である。クラス分類とは少なくとも１つのクラスに分類することである。２つ目は、選択されたブロックに対して、各クラスがどのような係数を設定すれば、予測誤差が最小となるかという、予測係数の最適化である。本実施形態では、この２つの最適化問題を求解する。この求解の目的は、予測誤差の低減である。前述したように、ＨＥＶＣにおけるイントラ予測では、あらゆる映像に対して、クラスの数、各クラスで定める予測係数、参照画素の位置が固定されている。しかし、本実施形態による方法では、その全てを１枚のフレーム毎に適応的に設定することで、予測誤差を低減する。
【００４１】
図１４、図１５は、適応的なイントラ予測器の目的と課題を示す説明図である。映像ごとの適応させる際に課題となるのが、予測係数のデータ圧縮である。前述した符号化データは、ＨＥＶＣでは２つから構成される。１つ目はクラス選択の情報であり、２つ目は予測誤差の情報である。本実施形態では、ＨＥＶＣと比べて予測誤差の低減が期待できるため、（２）で示す予測誤差の符号量は低減できると考えられる。また、本実施形態による方法では、（３）で示す予測係数の情報が追加される。このため、本実施形態による方法では、予測係数を圧縮する必要がある。予測係数の符号量が増大すると、十分な符号量削減が期待できない。そこで、後述するスパースな予測器設計を行うことで、（３）で示す予測係数の符号量削減を図る。
【００４２】
図１６は、適応的なイントラ予測器の動作を示す説明図である。イントラ予測を行うために最適化する箇所は次の２箇所である。１箇所目は、各ブロックが、どのクラスを選択するかを示すクラス分類の最適化である。２箇所目は、選択されたブロックに対して、クラス毎にどのような予測係数を設定するかを示す、予測係数の最適化である。これら２つの最適化を同時に行うことは困難なため、図１６に示す２ステップ（ＳＴＥＰ１、ＳＴＥＰ２）を経て、交互に最適化が行なわれる。
【００４３】
まず最初に、クラスごとの予測係数を固定した状態で、各ブロックがどのクラスを選択するかが最適化される（ＳＴＥＰ１）。具体的には、各ブロックが予測誤差を最小にするクラスが選択される。次に、各ブロックのクラス選択を固定した状態で、選択されたブロックに対して予測誤差を小さくするように、かつ予測係数の符号量が少なくなるように、予測係数が最適化される（ＳＴＥＰ２）。この具体的な処理は、後述する。また、この２つのステップは、予測誤差が十分収束するまで交互に繰り返される。
【００４４】
図１７は、予測器の符号量を削減する動作を示す説明図である。前述したＳＴＥＰ２は、予測誤差を小さくする予測係数を決めるステップである。このとき、予測誤差を小さくするように係数を決定するが、予測係数の全てを使用すると、予測係数を表現する符号量が増大してしまう。そこで、予測係数をスパースな状態に設定する。ここで、スパースとは、予測係数の中の多くが図１７に示すようにグレーで示す０である状態を指す。このとき、ゼロ係数が多ければ予測に用いる係数の数が削減でき、予測係数の符号量の削減が期待できる。
【００４５】
図１８は、スパースな予測係数を設定するＳＴＥＰ２の詳細な動作を示す説明図である。スパースな予測係数を設定するＳＴＥＰ２は、次の２つのステップからなる。まず、ＳＴＥＰ２−１では、使う予測係数の位置が定められる。次に、ＳＴＥＰ２−１で定められた非ゼロ係数の位置に対して、ＳＴＥＰ２−２では、予測誤差を最小化する予測係数が設定される。
【００４６】
図１９、図２０は、Ｌ１ノルム正則化項に基づく定式化を示す説明図である。ＳＴＥＰ２−１において、予測係数の位置を決めるために、ある１つの画素に着目した予測誤差の最小化問題を、予測係数の絶対値和、すなわちＬ１ノルムの大きさの上限を定める制約を追加して解く。このＬ１ノルム（絶対値和）の大きさにより、予測係数のスパース性の制御が行なわれる。以降では、ある１つの画素を予測する予測器を、単画素予測器と呼ぶ。
【００４７】
単画素予測器の予測係数は、前述した予測係数Ａの１行分の係数に対応している。従って、１番目の画素値を予測する場合は、予測係数Ａの１行目を、２番目の画素値を予測する場合は、Ａの２行目を、３番目の画素値を予測する場合は、Ａの３行目を単画素予測器の予測係数として利用する。また、１つの予測係数Ａを定めるためには、ブロック（被予測画素ｙ）内の予測画素の数だけ、単画素予測器の設計問題を解く必要がある。
【００４８】
また、それだけでなく、図２０に示すように、予測画素ブロックは各クラスが保持する予測係数の中から、予測誤差を小さくするクラスを選択することができる。従って、最終的に、ブロックの中の予測画素数×クラス数の数だけ、単画素予測器を同時に設計する必要がある。
【００４９】
図２１〜図２８は、複数予測器設計の最適化の動作を示す説明図である。予測画素数×クラス数の単画素予測器を同時に最適化するためには、単画素予測器ごとにＬ１ノルムを適切に配分する必要がある。配分に利用可能なＬ１ノルムの総和は、図２１に示すように与えられている。そこで、図２２に示すように、全体の予測誤差を最小化するように、単画素予測器ごとにＬ１ノルムを割り振る。ここで、従来の最適化手法では、このような複数の設計問題に対するＬ１ノルムの分配方法について考慮されていなかった。そこで、本実施形態ではこのＬ１ノルムの分配を行う。
【００５０】
次に、具体的にＬ１ノルムの配分を行う動作について説明する。図２３に示す例では、クラス数と予測画素数が２つの場合で説明する。まず、分配を行う際、単画素予測器ごとに予測誤差削減効率が算出される。これは、Ｌ１ノルムを分配したときにどの程度効率よく予測誤差を削減できるかを示したものである。
【００５１】
この予測誤差削減効率が最も大きい（ここでは、図２４に示す「２５」）単画素予測器が選択され、Ｌ１ノルムの分配が行われる。ここで、一度に分配する量はＬＡＲＳという既存アルゴリズムに基づいて定める。また、一度Ｌ１ノルムの配分を行うごとに、選択された単画素予測器の予測誤差削減効率が減少する（図２５に示すように「２５」→「１９」）。そこで、Ｌ１ノルムを配分する度に、予測誤差削減効率が最も高い単画素予測器を再選択する（図２５に示すように、「２１」が選択される）。
【００５２】
単画素予測器へ配分を行ったので、予測誤差削減効率が減少し（図２６に示すように「２１」→「１２」）、再び予測誤差削減効率が最も大きい（図２６に示す例は「１９」）単画素予測器が選択される。このような操作を続けていき、図２７に示すように、最初に定めたＬ１ノルムの総和が０になるまで続けられる。
【００５３】
すなわち、ＳＴＥＰ２−１では、単画素予測器にＬ１ノルムを配分する際、予測誤差削減効率を用いてどの単画素予測器へＬ１ノルムを配分するかが定められる（図２８参照）。
【００５４】
図２９は、ＳＴＥＰ２−１で得られる非ゼロ係数位置を示す説明図である。前述した単画素予測器の設計問題を解くことで、図２９の左図に示すように非ゼロ係数の位置と値を求めることができる。しかし、ここで得られた係数はＬ１ノルムの制約を課した結果であるため、予測誤差が最小化されていない。そこで、ＳＴＥＰ２−１では、図２９の右図に示すように、得られた非ゼロ係数の位置のみを利用する。
【００５５】
次に、ＳＴＥＰ２−２では、非ゼロ係数の位置を固定して、予測誤差を最小化する係数が改めて求められる。非ゼロ係数の位置を固定した場合、予測誤差を最小化する係数は解析的に求めることができるため、各クラス毎に、予測係数の値を求めることができる。
【００５６】
次に、図面を参照して本発明の線形予測係数出力装置を適用した実施形態による動画像符号化装置および動画像復号装置を説明する。図１は本実施形態におけるロスレス符号化を行う場合の動画像符号化装置の構成を示すブロック図である。ただし、本発明における線形予測係数出力装置はロスレス符号化（可逆符号化）においてもロッシー符号化（非可逆符号化）においても適用可能である。
【００５７】
本動画像符号化装置は符号化対象の映像信号を入力し、符号化された映像を符号化ストリームとして出力する。以降の実施形態の説明において、符号化対象となる映像信号を単に映像信号と呼ぶ。
【００５８】
原信号出力部１００は映像信号を入力し、インター予測部３００またはイントラ予測部４００へ映像信号を出力する。出力する映像信号はインター予測部３００とイントラ予測部４００のそれぞれで画素値予測のための参照画素として利用される。
【００５９】
イントラ予測部４００は参照画素に用いられる映像信号を入力し、生成した予測画像を予測残差生成部２００へ出力する。また、イントラ予測部４００は反復処理収束判定部６００から反復処理要求フラグを受けとる。反復要求がある場合はイントラ予測情報を用いてイントラ予測係数の最適化を一度行う。反復要求がない場合は、最終的に得られたイントラ予測係数およびイントラ予測情報をエントロピ符号化処理部５００へ出力する。
【００６０】
インター予測部３００は参照画素に用いられる映像信号を入力し、生成した予測画像を予測残差生成部２００へ出力する。予測残差生成部２００は原信号出力部１００から映像信号を入力し、また、インター予測部３００もしくはイントラ予測部４００から予測画像を入力し、映像信号と予測画像との差分である予測残差を出力する。
【００６１】
エントロピ符号化処理部５００は予測残差生成部２００から予測残差を、インター予測部３００、イントラ予測部４００からインター予測情報とイントラ予測係数を受け取り、予測残差、インター予測情報、イントラ予測情報、イントラ予測係数から符号化ストリームを生成し、符号化ストリームを出力する。
【００６２】
反復処理収束判定部６００は反復符号化処理により符号化効率が向上するか否かを判定し、原信号出力部１００およびイントラ予測部４００に対して反復処理要求フラグを送信する。反復処理要求を行った場合、原信号出力部１００は符号化処理を行うために映像信号を再度送信し、イントラ予測部４００は後述するイントラ予測係数の最適化を行う。
【００６３】
反復処理要求は、（１）反復を行わない場合も含め、符号化時に定められた回数だけ反復処理を行う、（２）１度前の符号化時と比較した際の符号量の減少率が、符号化時に定められた閾値を上回る、のいずれかによって判断される。
【００６４】
次に、図２を参照して、図１に示すイントラ予測部４００の詳細な構成を説明する。図２は図１に示すイントラ予測部４００の詳細な構成を示すブロック図である。図２に示す構成では特にイントラ予測係数生成部４０２を備えている点が従来の構成と異なる。
【００６５】
イントラ予測処理部４０１は、（１）原信号出力部１００が出力する映像信号、（２）イントラ予測係数記憶部４０３が出力するイントラ予測係数を受け取り、符号化効率の高いイントラ予測情報を決定する。そして、イントラ予測処理部４０１は、同イントラ予測情報に従って映像信号を参照画素とした予測ブロック内の画素値予測により予測画像を生成し、予測画像とイントラ予測情報を出力する。
【００６６】
イントラ予測係数生成部４０２は反復処理収束判定部６００から反復要求があった場合、イントラ予測情報記憶部４０３からイントラ予測情報を受け取る。そして、イントラ予測係数生成部４０２は、符号化効率の観点で映像信号およびイントラ予測情報に適したイントラ予測係数を決定するためイントラ予測係数の最適化を行い、イントラ予測係数をイントラ予測係数記憶部４０３へ出力する。
【００６７】
イントラ予測係数記憶部４０３はイントラ予測係数生成部４０２からイントラ予測係数を受け取り、受けとったイントラ予測係数を自身が保持するメモリに格納する。必要に応じて、イントラ予測処理部４０１とエントロピ符号化処理部５００へイントラ予測係数を出力する。
【００６８】
イントラ予測情報記憶部４０４はイントラ予測処理部４０１が決定したイントラ予測情報を受け取る。必要に応じて、イントラ予測係数生成部４０２とエントロピ符号化処理部５００へイントラ予測情報を出力する。
【００６９】
イントラ予測係数初期化部４０５は最初の反復におけるイントラ予測係数を定める。イントラ予測係数生成部４０２はイントラ予測情報を定めることで初めてイントラ予測係数の最適化が可能となる。そこで、符号化の反復処理の最初はイントラ予測係数をイントラ予測係数生成部４０２と別途の処理で定める必要がある。
【００７０】
次に、図３を参照して、図２に示すイントラ予測部４００の動作を説明する。図３は図２に示すイントラ予測部４００の動作を示すフローチャートである。まず、イントラ予測係数初期化部４０５は、映像信号の符号化を開始する前にイントラ予測係数の初期化を行う（ステップＳ１０１）。
【００７１】
次に、イントラ予測処理部４０１は、反復した符号化を行う最中に、符号化効率の高いイントラ予測情報を決定する（ステップＳ１０２）。続いて、イントラ予測処理部４０１は、ステップＳ１０２により定まったイントラ予測情報に基づいてイントラ予測を行い、予測画を出力する（ステップＳ１０３）。
【００７２】
また、イントラ予測処理部４０１は、ステップＳ１０２により定まったイントラ予測情報をイントラ予測情報記憶部４０４に保存する（ステップＳ１０４）。そして、イントラ予測係数生成部４０２は、全ての予測ブロックにおいてイントラ予測情報が決定された後、反復処理要求フラグを受け取る（ステップＳ１０５）。
【００７３】
次に、イントラ予測係数生成部４０２は、イントラ予測係数を最適化するか否かを判定する（ステップＳ１０６）。この判定の結果、イントラ予測係数を最適化するための反復処理要求があった場合、イントラ予測係数生成部４０２は、イントラ予測情報記憶部４０４に保存したイントラ予測情報を読み込み、最適化を行う（ステップＳ１０７）。また、イントラ予測係数生成部４０２は、最適化を行ったイントラ予測係数をイントラ予測係数保存部４０３に保存する（ステップＳ１０８）。
【００７４】
次に、図２に示すイントラ予測係数生成部４０２の詳細な構成を説明する。図４は図２に示すイントラ予測係数生成部４０２の第１の構成を示すブロック図である。予測係数最適化情報生成部４０２１は映像信号およびイントラ予測情報を入力とし、イントラ予測係数最適化に必要な予測係数最適化情報を出力する。この予測係数最適化情報は、予測係数最適化情報記憶部４０２２に記憶される。単画素予測係数最適化処理部４０２３は反復処理要求があった場合、予測係数最適化情報を入力とし、予測誤差の２乗和を最小化する予測係数を解析的に導出し、出力する。
【００７５】
次に、図４に示すイントラ予測係数生成部４０２の動作を説明する。図５は図４に示すイントラ予測係数生成部４０２の動作を説明するフローチャートである。まず、予測係数最適化情報生成部４０２１はイントラ予測情報および映像信号を基に予測係数最適化情報Σｃ１，Σｃ２を生成する（ステップＳ２０１）。そして、スパースでない予測係数の解を解析的に導出するため、予測係数最適化情報や予測係数は、予測係数最適化情報記憶部４０２２に保存する。次に、単画素予測係数最適化処理部４０２３は、生成した予測係数最適化情報を基に、予測誤差の２乗和を最小化する係数を解析的に導出し、出力する（ステップＳ２０２）。
【００７６】
図６は、図２に示すイントラ予測係数生成部４０２の第２の構成を示すブロック図である。予測係数最適化情報生成部４０２１は映像信号およびイントラ予測情報を入力とし、イントラ予測係数最適化に必要な予測係数最適化情報を出力する。ここで、予測係数最適化情報とは下記に示す２種類の行列Σｃ１，Σｃ２を指す。
【数１０】
0006649184.tif 000011
ここで、Ｓｃはクラス番号ｃを選択する予測ブロック番号の集合である。ｘｉは参照画素を要素とするＭｉ次元の列ベクトルである。ｙｉ［ｃ］は予測ブロック内の画素値を要素とするＭｏ次元の列ベクトルである。
【００７７】
予測係数最適化情報記憶部４０２２は予測係数最適化情報生成部４０２１が出力した予測係数最適化情報を入力とし、自身が保持する記憶領域に保存する。単画素予測係数情報記憶部４０２４は単画素予測係数初期化部４０２５が出力した予測係数を入力とし、自身が保持する記憶領域に保存する。また、単画素予測係数最適化処理部４０２３が出力した予測係数を最適化処理を入力とし、自身が保持する記憶領域に保存してある予測係数を上書きして保存する。
【００７８】
単画素予測係数初期化部４０２５は予測係数最適化を行う前に全てがゼロ係数の単画素予測係数を出力する。単画素予測係数反復最適化終了判定部４０２７は反復処理要求を受け取っている場合、単画素予測係数集合を入力とし、予測係数の最適化をこれ以上続行すべきか否か判定を下す。ここで、単画素予測係数集合とは、単画素予測係数を全てのクラス数Ｃおよび予測ブロック内画素数Ｍｏ分集めた係数の集合とする。最適化を続行する場合、単画素予測係数選択部４０２６に単画素予測係数集合を出力する。最適化を続行しない場合、単画素予測係数を最終的な予測係数として出力する。
【００７９】
単画素予測係数選択部４０２６は単画素予測係数反復最適化終了判定部４０２７から出力された単画素予測係数集合を入力とし、次に最適化すべき単画素予測係数として式（９）に示す予測誤差削減効率が最も大きい単画素予測係数を選択し、単画素予測係数最適化処理部４０２３へ出力する。
【００８０】
単画素予測係数最適化処理部４０２３は単画素予測係数選択部４０２６が出力した最適化対象となる単画素予測係数、および予測係数最適化情報記憶部４０２２が出力する予測係数最適化情報を入力とし、ＬＡＲＳにおける単画素予測係数の最適化を１ステップ進めた後の単画素予測係数を出力とする。
【００８１】
次に、図７を参照して、図６に示すイントラ予測係数生成部４０２の動作を説明する。図７は、図６に示すイントラ予測係数生成部４０２の動作を説明するフローチャートである。まず、予測係数最適化情報生成部４０２１はイントラ予測情報を基に予測係数最適化情報を生成し、予測係数最適化情報記憶部４０２２へ保存する（ステップＳ３０１）。
【００８２】
次に、単画素単画素予測係数初期化部４０２５は、各単画素予測係数を零値に初期化した状態の単画素予測係数集合を単画素予測係数情報記憶部４０２４に保存する（ステップＳ３０２）。次に、単画素予測係数最適化終了判定部４０２７は、現在の単画素予測係数集合を最適化すべきか否かを判定する（ステップＳ３０３）。この最適化すべきか否かの判定は、同時に最適化する各単画素予測係数ａｃ［ｊ］の予測誤差削減効率ｅｉ（ｊ）の最大値が一定のしきい値に到達したか否かに基づいて行われる。また、非零値の係数が一定割合に到達したか否かに基づいて判定が行われてもよい。
【００８３】
そして、最適化が必要だと判定された場合、単画素予測係数選択部４０２６は、単画素予測係数集合の中から最適化すべき単画素予測係数として式（９）に示す予測誤差削減効率が最も大きい単画素予測係数を選択する（ステップＳ３０４）。続いて、単画素予測係数最適化処理部４０２３は、選択された単画素予測係数に対して最適化処理を行う（ステップＳ３０５）。最適化処理を行った単画素予測係数は単画素予測係数情報記憶部４０２４に保存される（ステップＳ３０６）。
【００８４】
また、イントラ予測係数生成部４０２において、単画素予測係数の最適化を終了する判定がなされた場合、非零値の予測係数の位置を固定する制約条件の下で予測誤差の２乗和を最小化する単画素予測係数再設定するようにしてもよい。
【００８５】
図８は、図２に示すイントラ予測係数生成部４０２の第３の構成を示すブロックである。図８は、上記単画素予測係数の再設定を行う場合における構成例である。図６と図８との差異は単画素予測係数精緻化処理部４０２８であるため、このブロックについて詳細な説明を行う。
【００８６】
単画素予測係数精緻化処理部４０２８は単画素予測係数反復最適化終了判定部４０２７が出力した最適化終了済の単画素予測係数であるイントラ予測係数を入力とし、非零値の予測係数の位置を固定する制約条件の下で予測誤差の２乗和を最小化するイントラ予測係数を導出し、新たに求めたイントラ予測係数を出力する。
【００８７】
次に、前述したイントラ予測係数生成部４０２は式（８）で示される最適化問題における凖最適解を求める方法であった。しかし、最適解の導出が望ましい場合もあるため、式（８）における最適解を導出する方法について説明する。
【００８８】
図９は、図２に示すイントラ予測係数生成部４０２の第４の構成を示すブロックである。図９は式（８）における最適解を導出する場合における、図６で示されるイントラ予測係数生成部４０２の構成の詳細を示すブロック図である。図６と図９との差異は単画素予測係数選択部４０２６および単画素予測係数最適化処理部４０２３であるため、この２つのブロックについて詳細な説明を行う。
【００８９】
単画素予測係数選択部４０２６は単画素予測係数反復最適化終了判定部４０２７から更なる最適化が必要と判断された単画素予測係数集合を入力として受け取る。そして、単画素予測係数選択部４０２６は、単画素予測係数集合の中から予測誤差削減効率が最も高い単画素予測係数を全て選択し、単画素予測係数最適化処理部４０２３へ出力する。図６で示した単画素予測係数では必ず１つの単画素予測係数を選択したが、図９における構成例では複数の単画素予測係数を選択しうる。
【００９０】
単画素予測係数最適化処理部４０２３は単画素予測係数選択部４０２６が出力した単画素予測係数集合全てに対し、各単画素予測係数に対して図６における単画素予測係数最適化処理部４０２３と同様の処理を行う。ただし、単画素予測係数最適化処理部４０２３の最適化後においても単画素予測係数選択部４０２６が出力した単画素予測係数集合における予測誤差削減効率が全て等しくなる制約条件を課す。上記制約条件を課した最適化を行い、単画素予測係数情報記憶部４０２４に最適化した単画素予測係数集合を出力する。
【００９１】
次に、動画像復号装置について説明する。図１０は同実施形態における動画像復号装置の構成を示すブロック図である。動画像復号装置は、図１０におけるエントロピ符号処理部５００が出力した符号化ストリームを入力とし、符号化ストリームから予測残差、インター予測情報、イントラ予測情報、イントラ予測係数の計４つの情報を復元し、４つの情報を用いて生成される復号映像信号を出力する。動画像符号化装置では、ロスレス圧縮を行っているため、復号映像信号と映像信号は同一となる。
【００９２】
エントロピ復号処理部７００は、図１に示すエントロピ符号化処理部５００が出力した符号化ストリームを入力とし、符号化ストリームから予測残差、インター予測情報、イントラ予測情報、イントラ予測係数の計４つの情報を復元し、上記４つの情報をそれぞれ出力する。イントラ予測部８００はフレームメモリ１１００から復号映像信号を、エントロピ復号処理部７００からイントラ予測情報とイントラ予測係数を受け取り、イントラ予測処理により生成された予測画像を出力する。
【００９３】
インター予測部９００は復号映像信号、インター予測情報をそれぞれフレームメモリ１１００、エントロピ復号処理部から受け取り、インター予測処理により生成された予測画像を出力する。復号信号生成部１０００はインター予測部９００もしくはイントラ予測部８００が出力した予測画像、エントロピ復号処理部７００が出力した予測残差を入力し、予測画像と予測残差を加算することで生成される復号映像信号を出力する。
【００９４】
フレームメモリ１１００は復号信号生成部１０００が出力した復号映像信号を入力し、自身が保持するメモリへ格納する。復号映像信号は、インター予測部９００およびイントラ予測部８００における参照画素として利用される。
【００９５】
次に、図１０に示すイントラ予測部８００の詳細な構成を説明する。図１１は図１０に示すイントラ予測部８００の詳細な構成を示すブロック図である。本ブロック図では特にイントラ予測係数生成部８０３が従来法と異なる。
【００９６】
イントラ予測処理部８０１はイントラ予測情報記憶部８０２からイントラ予測情報を、イントラ予測係数記憶部８０３からイントラ予測係数を読み込み、フレームメモリ１１００から復号映像信号を入力し、イントラ予測処理を行い予測画像を出力する。イントラ予測情報記憶部８０２はイントラ予測情報をエントロピ復号処理部７００から受け取り、自身が保持する記憶領域に保存する。イントラ予測係数記憶部８０３はイントラ予測係数をエントロピ復号処理部７００から受け取り、自身が保持する記憶領域に保存する。
【００９７】
次に、図１１に示すイントラ予測部８００の動作を説明する。図１２は、図１１に示すイントラ予測部８００の動作を示すフローチャートである。まず、イントラ予測処理を行う前処理としてエントロピ復号処理部７００からイントラ予測情報を受け取ってイントラ予測情報記憶部８０２に保存する（ステップＳ４０１）。そして、エントロピ復号処理部７００からイントラ予測係数を受け取ってイントラ予測係数記憶部８０３に保存する（ステップＳ４０２）。その後、イントラ予測処理部８０１がフレームメモリ１１００から復号映像信号を受け取り、イントラ予測を行って予測画像を生成する（ステップＳ４０３）。
【００９８】
以上説明したように、イントラ予測においてクラス数や予測ブロック内の画素数を１より大きく設定した制約条件下であっても最適化問題を効率的に求解することで、信号特性に適合した予測係数を効率的に出力できる。この構成によれば、デジタル信号に対する線形予測を行うためのスパース性（非零値の係数がまばらに存在すること）を有する予測係数を効率的に出力できる。
【００９９】
なお、本実施形態における０でない係数を少なくするというのは手段の１つにすぎず、０という数字や係る予測器に限定するものではない。本実施形態による線形予測係数出力装置は音声など他のメディアの符号化や、工数や稼働の管理システム等様々な分野に適用可能である。その際０でない係数を少なくする、という条件は適用する分野に応じて設定すればよい。
【０１００】
なお、請求項でいうデジタル信号、単信号は、映像符号化の場合、それぞれ、画素の集合、単画素に相当する。また、デジタル信号を区間に分割するとは、映像符号化においては、ブロック分割することに相当する。
【０１０１】
前述した実施形態における線形予測係数出力装置の全部または一部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＰＬＤ（Programmable Logic Device）やＦＰＧＡ（Field Programmable Gate Array）等のハードウェアを用いて実現されるものであってもよい。
【０１０２】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。従って、本発明の技術思想及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行ってもよい。
【産業上の利用可能性】
【０１０３】
イントラ予測においてクラス数や予測ブロック内の画素数を１より大きく設定した制約条件下であっても最適化問題を効率的に求解することで、信号特性に適合したイントラ予測を可能にすることが不可欠な用途に適用できる。
【符号の説明】
【０１０４】
１００・・・原信号出力部、２００・・・予測残差生成部、３００・・・インター予測部、４００・・・イントラ予測部、５００・・・エントロピ符号化処理部、６００・・・反復処理収束判定部、４０１・・・イントラ予測処理部、４０２・・・イントラ予測係数生成部、４０３・・・イントラ予測係数記憶部、４０４・・・イントラ予測情報記憶部、４０５・・・イントラ予測係数初期化部、４０２１・・・予測係数最適化情報生成部、４０２２・・・測係数最適化情報記憶部、４０２３・・・単画素予測係数最適化処理部、４０２４・・・単画素予測係数情報記憶部、４０２５・・・単画素予測係数初期化部、４０２６・・・単画素予測係数選択部、４０２７・・・単画素予測係数反復最適化終了判定部、４０２８・・・単画素予測係数精緻化処理部、７００・・・エントロピ復号処理部、８００・・・イントラ予測部、９００・・・インター予測部、１０００・・・復号信号生成部、１１００・・・フレームメモリ、８０１・・・イントラ予測処理部、８０２・・・イントラ予測情報記憶部、８０３・・・イントラ予測係数記憶部
【図１】
0006649184.tif 000012
【図２】
0006649184.tif 000013
【図３】
0006649184.tif 000014
【図４】
0006649184.tif 000015
【図５】
0006649184.tif 000016
【図６】
0006649184.tif 000017
【図７】
0006649184.tif 000018
【図８】
0006649184.tif 000019
【図９】
0006649184.tif 000020
【図１０】
0006649184.tif 000021
【図１１】
0006649184.tif 000022
【図１２】
0006649184.tif 000023
【図１３】
0006649184.tif 000024
【図１４】
0006649184.tif 000025
【図１５】
0006649184.tif 000026
【図１６】
0006649184.tif 000027
【図１７】
0006649184.tif 000028
【図１８】
0006649184.tif 000029
【図１９】
0006649184.tif 000030
【図２０】
0006649184.tif 000031
【図２１】
0006649184.tif 000032
【図２２】
0006649184.tif 000033
【図２３】
0006649184.tif 000034
【図２４】
0006649184.tif 000035
【図２５】
0006649184.tif 000036
【図２６】
0006649184.tif 000037
【図２７】
0006649184.tif 000038
【図２８】
0006649184.tif 000039
【図２９】
0006649184.tif 000040