(57)【要約】【課題】イントラ予測においてクラス数と予測ブロック内の画素数とが１よりも大きな値であるという制約条件の下でも最適化問題を効率的に求解することが可能である線形予測係数出力方法、線形予測係数出力装置及び線形予測係数出力プログラムを提供する。【解決手段】線形予測係数出力方法は、予測対象のデジタル信号を線形予測するための予測係数の一部であり１次元のデジタル信号の予測係数である単信号予測係数の集合のうち制約条件を満たす単信号予測係数の集合を、予測対象のデジタル信号を線形予測するための予測係数と定めるステップと、予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和に基づいて上限値を定めるステップと、予測対象のデジタル信号を線形予測するための予測係数と上限値とを出力するステップとを含む。【選択図】図１１
2018098581.tif 000002
【特許請求の範囲】
【請求項１】
予測対象のデジタル信号と予測されたデジタル信号との差分である予測誤差について、線形予測に用いられる係数である予測係数の絶対値和の総和が上限値を満たすという制約条件の下で前記予測誤差の二乗和を最小化する線形予測器を用いて前記予測対象のデジタル信号を線形予測するための予測係数を出力する線形予測係数出力装置が実行する線形予測係数出力方法であって、
前記予測対象のデジタル信号を線形予測するための予測係数の一部であり１次元のデジタル信号の予測係数である単信号予測係数の集合のうち前記制約条件を満たす前記単信号予測係数の集合を、前記予測対象のデジタル信号を線形予測するための予測係数と定めるステップと、
前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和に基づいて前記上限値を定めるステップと、
前記予測対象のデジタル信号を線形予測するための予測係数と前記上限値とを出力するステップと
を含む線形予測係数出力方法。
【請求項２】
前記予測対象のデジタル信号は、前記予測対象のデジタル信号を線形予測するための予測係数と符号化の際に参照されるデジタル信号との行列積である、請求項１に記載の線形予測係数出力方法。
【請求項３】
前記制約条件を満たす前記単信号予測係数の集合における前記単信号予測係数の絶対値和の上限値の増加量と前記予測誤差の二乗和の減少量との比である予測誤差削減率のうち、前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数であるＬ０ノルムの変化量が１である前記予測誤差削減率と前記Ｌ０ノルムの変分との組が列挙されたリストを前記単信号予測係数ごとに出力するステップと、
列挙された全ての前記予測誤差削減率と前記Ｌ０ノルムの変分との組が統合されたリストである統合リストを出力するステップと、
前記予測誤差削減率が大きい順に前記組を前記統合リストから選択し、前記組ごとに前記Ｌ０ノルムの変分の累積和を算出することで、前記予測対象のデジタル信号を線形予測するための予測係数の全体の前記Ｌ０ノルムを算出するステップと、
前記予測対象のデジタル信号を線形予測するための予測係数の全体の前記Ｌ０ノルムが前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和以下である場合、前記組の一方の前記予測誤差削減率を、前記予測対象のデジタル信号を線形予測するための予測係数の全体の前記予測誤差削減率と定めるステップと
を含む、請求項１又は請求項２に記載の線形予測係数出力方法。
【請求項４】
予測対象のデジタル信号と予測されたデジタル信号との差分である予測誤差について、空間的な相関を利用する線形予測に用いられる係数である予測係数の絶対値和の総和が上限値を満たすという制約条件の下で前記予測誤差の二乗和を最小化する線形予測器を用いて前記予測対象のデジタル信号を線形予測するための予測係数を出力する線形予測係数出力装置であって、
前記予測対象のデジタル信号を線形予測するための予測係数の一部であり１次元のデジタル信号の予測係数である単信号予測係数の集合のうち前記制約条件を満たす前記単信号予測係数の集合を、前記予測対象のデジタル信号を線形予測するための予測係数と定める予測係数決定部と、
前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和に基づいて前記上限値を定める上限決定部と、
前記予測対象のデジタル信号を線形予測するための予測係数と前記上限値とを出力する予測係数出力部と
を備える線形予測係数出力装置。
【請求項５】
請求項１から請求項３のいずれか一項に記載の線形予測係数出力方法をコンピュータに実行させるための線形予測係数出力プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線形予測係数出力方法、線形予測係数出力装置及び線形予測係数出力プログラムに関する。
【背景技術】
【０００２】
高能率な映像符号化を実現するには、イントラ予測の予測誤差の低減が重要な課題となる。以下では、映像とは、動画像、すなわち、一連の画像の集合である。画像とは、動画像を構成する１フレーム又は静止画像である。動画圧縮方式の規格の一つであるＨ．２６３では、同一フレーム内における隣接画素値間の相関除去を目的として、周辺画素値を用いた画素値予測処理が導入された。Ｈ．２６３では、ＤＣ（Direct Current）成分に対する予測のみが行われる。動画圧縮方式の規格の一つであるＨ．２６４／ＡＶＣでは、Ｐｌａｎｅ予測や９通りの方向性予測が追加された。
【０００３】
動画圧縮方式の規格の一つであるＨ．２６５／ＨＥＶＣ（High Efficiency Video Coding）では、Ｐｌａｎｅ予測を改善したＰｌａｎａｒ予測が導入されると共に、方向性予測の方向数が３３通りに増加された。しかし、Ｈ．２６５／ＨＥＶＣでは、予測誤差を低減する余地が残されている。
【０００４】
ＨＥＶＣのイントラ予測は、画素値変化の方向が直線的であると仮定している。また、Ｈ．２６５／ＨＥＶＣでは、予測器の数や種類は、映像によらずに固定されている。従って、画素値変化の方向が直線的でない場合、予測誤差は増大する。また、特定の予測器が使用されない場合、予測情報の表現に要する符号量が増大する。従って、予測誤差を低減するには、映像ごとに適切な予測器を構築する必要がある。
【０００５】
映像ごとに予測器を定める方法として、複数の線形予測器を画像ごとに定める方法がある（非特許文献１参照）。非特許文献１では、１枚の画像を矩形ブロックに分割し、矩形ブロックごとに予測が実行される。また、非特許文献１では、各矩形ブロックを複数種類のクラスに分類し、適応的な予測器がクラスごとに定められる。以下では、予測処理の単位となる矩形ブロックを「予測ブロック」という。
【０００６】
図１９は、複数の予測ブロックに分割された符号化対象フレームにおける、予測に用いられる参照画素及び被予測画素の関係の例を示す図である。図１９では、一例として、符号化対象フレームである画像を（５×３）に分割し、１３個の参照画素から１６個の被予測画素を予測する。参照画素の数及び形と被予測画素の数とは、自由に変更できる。
【０００７】
図２０は、予測ブロックを複数のクラスに分類する方法の例を示す図である。図２０では、一例として、１５個の予測ブロックが３個のクラスに分類され、予測に必要となる係数がクラスごとに用意される。クラス数は、１以上の整数であればどのように設定してもよい。予測係数の導出方法については後述する。
【０００８】
非特許文献１では、最小単位である単画素の予測ブロック（予測対象）が定められている。予測ブロック内の画素値と原画像の画素値との誤差である予測誤差は、低く抑えることが望ましい。一方、同一画像内の各予測ブロックは、信号特性がそれぞれ異なる。そこで、類似した信号特性を持つ予測ブロックを１個のクラスにまとめ、まとめられたクラスにおいて予測誤差の少ない予測器が設計される。非特許文献１には、クラス分類の方法として、付加情報を用いずに予測ブロック周辺の近傍画素値の分散を用いる分類の方法が開示されている。非特許文献１では、予測ブロック内の画素値の予測に、式（１）に示す線形予測が用いられる。
【０００９】
【数１】
2018098581.tif 000003
【００１０】
ここで、ｉは、予測ブロックの番号を示す指数である。ｃは、クラス番号であり、１からＣまでとりうる。＾ｘｉ＝（＾ｘｉ１，・・・，＾ｘｉｌ，・・・，＾ｘｉＭｉ）Ｔ（＾は、後に続く文字の上に付く。以下同様）は、参照画素を要素とするＭｉ次元の列ベクトルである。Ｍｉは、予測に用いる参照画素数である。＾ｙｉｃは、予測ブロックにおける予測画素値である。非特許文献１では、予測ブロックの大きさが（１×１）であるため、＾ｙｉｃは、１次元の実数である。ｂｃは、クラスｃにおける予測係数であり、Ｍｉ次元行ベクトルである。
【００１１】
各クラスの予測係数ｂｃに対し予測誤差を最小化する係数を定める方法では、Ｗｉｅｎｅｒ−Ｈｏｐｔ方程式と呼ばれる線形連立方程式を解くことが知られている。以上に説明した事項は、非特許文献１に詳述されている。非特許文献１の線形予測を拡張し、画素単位でない予測ブロック内の正規化された画素値に対する線形予測は、式（２）のように記述できる。
【００１２】
【数２】
2018098581.tif 000004
【００１３】
ここで、ｉは、予測ブロックの番号を示す指数である。ｃは、クラス番号であり、１からＣまでとりうる。＾ｘｉ＝（＾ｘｉ１，・・・，＾ｘｉｌ，・・・，＾ｘｉＭｉ）Ｔは正規化処理を施した参照画素を要素とするＭｉ次元の列ベクトルである。Ｍｉは予測に用いる参照画素数である。＾ｘｉは、式（３）のように正規化されている。
【００１４】
【数３】
2018098581.tif 000005
【００１５】
ここで、￣ｘｉ＝（￣ｘｉ１；，・・・，￣ｘｉｌ，・・・，￣ｘｉＭｉ）Ｔ（￣は、後に続く文字の上に付く。以下同様）は、正規化処理を施していない参照画素を要素とするＭｉ次元の列ベクトルである．Ｓｃは、クラス番号ｃを選択する予測ブロック番号の集合である．μｘｌは、クラスｃに属するｌ番目の参照画素値￣ｘｉｌの平均値である．σｘｌは、クラスｃに属するｌ番目の参照画素値の標準偏差である。
【００１６】
＾ｙｉｃ＝（＾ｙｉｃ［１］，・・・，＾ｙｉｃ［ｊ］，・・・，＾ｙｉｃ［Ｍｉ］）Ｔは、正規化処理を施した予測ブロック内の画素値を要素とするＭｏ次元の列ベクトルである。＾ｙｉｃは、式（４）のように正規化されている。
【００１７】
【数４】
2018098581.tif 000006
【００１８】
ここで、￣ｙｉｃ＝（￣ｙｉｃ［１］，・・・，￣ｙｉｃ［ｌ］，・・・，￣ｙｉｃ［Ｍｏ］）Ｔは、正規化処理を施していない予測ブロック内の画素値を要素とするＭｉ次元の列ベクトルである．μｉｃ［ｊ］は、クラスｃに属するｌ番目の被予測画素値￣ｘｉｌの平均値である。Ｍｏは、予測ブロックの画素数である。ｊは、予測ブロック内の画素位置を示す指数である。Ａｃは、クラスｃにおける予測係数であり、列数がＭｉであり、行数がＭｏである実数値行列である。ｊ行目の予測係数により、ｊ番目の予測ブロック内画素値が予測される。
【００１９】
正規化されていない実際の予測画素値〜ｙｉｃ（〜は、後に続く文字の上に付く。以下同様）は、式（５）を用いて表される。
【００２０】
【数５】
2018098581.tif 000007
【００２１】
以下では、正規化処理は、参照画素及び予測ブロックに対して施される。画像ごとに線形予測に用いる係数方法では、予測係数が付加情報となる。このため、画像ごとに線形予測に用いる係数方法では、予測係数の発生符号量の抑制が課題となる。予測係数の発生符号量を抑制する方法として、予測係数の多くが零値であるスパースの状態にする制約条件の下で予測誤差を低減することが可能である予測係数を定める方法がある。
【００２２】
予測係数の多くが零値である場合、予測係数の表現に要する符号量を削減できるため、付加情報として送信する予測係数の符号量の削減が見込まれる。一方、零値の予測係数が多すぎる場合、予測誤差が増大してしまうため、予測誤差の表現に要する符号量の増大や復号画像の画質劣化が見込まれる。
【００２３】
予測係数の多くが零値であるというスパース性を課した制約条件の下で予測誤差を最小化する方法の一つとして、Ｌ０ノルムの二乗誤差の最小化問題がある。Ｌ０ノルムの二乗誤差の最小化問題は、式（６）を用いて表される。
【００２４】
【数６】
2018098581.tif 000008
【００２５】
ここで、Ｓｃは、クラス番号ｃを選択する予測ブロック番号の集合である。以下の文中では、式中における双柱は「｜｜」を用いて表す。｜｜Ａｃ｜｜０は、行列Ａｃにおける非零値である係数の個数である。予測係数の符号量は、非零値である予測係数の個数に依存する。このため、非零値の係数の個数に関する制約条件は、予測係数に要する符号量を調整する役割を持つ。θ０は、予測係数におけるＬ０ノルムの総和の上限値を表す。以下では、θ０を「Ｌ０ノルム総和上限」という。
【００２６】
しかし、式（６）における最適解の求解は困難である。このため、式（７）に示す条件に制約条件を緩和して求解する方法が考えられる。
【００２７】
【数７】
2018098581.tif 000009
【００２８】
ここで、｜｜Ａｃ｜｜１は、行列Ａｃにおける非零値である係数の絶対値の総和である。θ１は、線形予測に用いる全てのクラスにおける予測係数Ａｃの絶対値和の総和の上限値である。以下では、θ１を「Ｌ１ノルム総和上限」という。Ｌ１ノルム総和上限を定める制約条件を課すことで、スパース性を有する予測係数が得られる。Ｌ１ノルム総和上限によって、全てのクラスに亘った行列内における零値の係数を含む割合が調整される。
【００２９】
式（２）に示された予測係数は、予測ブロック内の各画素が独立であるとして予測される。予測ブロック内のｊ番目の画素値は、予測係数Ａｃのｊ行目の係数を用いて予測される。すなわち、Ａｃ＝（ａｃ［１］Ｔ，・・・，ａｃ［ｊ］Ｔ，・・・，ａｃ［Ｍｏ］Ｔ）Ｔと表記すると、ａｃ［ｊ］は、クラスｃに属する予測ブロックのｊ番目の画素値を予測するための係数であり、Ｍｉ次元の行ベクトルである。以下では、ａｃ［ｊ］を「単画素予測係数」という。
【００３０】
クラスｃに属するｉ番目の予測ブロック内のｊ番目の画素値は、単画素予測係数ａｃ［ｊ］及び参照画素ｘｉを用いて、ａｃ［ｊ］ｘｉと予測される。Ｌ１ノルムによる制約条件の下での最適化問題においてクラス数Ｃが１種類であり予測ブロック内の画素数Ｍｏが１個である場合、予測係数を定める最適化問題は、線形回帰を実行するための正則化手法であるＬＡＳＳＯと同一の問題として定義され、最適化問題の様々な解法が知られている。
【先行技術文献】
【非特許文献】
【００３１】
【非特許文献１】松田一朗、森弘史、前田譲治、伊東晋、可逆符号化のためのレートを最小とする予測器の設計と評価、電子情報通信学会論文誌Ｄ−ＩＩ、Ｖｏｌ．Ｊ８５、Ｎｏ．３、ｐｐ．４４８−４５６、２００２．
【発明の概要】
【発明が解決しようとする課題】
【００３２】
しかしながら、ＬＡＳＳＯの求解アルゴリズムでは、クラス数Ｃ及び画素数Ｍｏを１に限定した定式化及び制約条件が必要である。クラス数Ｃ及び画素数Ｍｏが１よりも大きな値である場合には、式（７）に示す条件に制約条件を緩和した最適化問題を効率的に求解することができない、という問題があった。式（７）に示す条件に制約条件を緩和した最適化問題を効率的に求解することができないので、式（５）の最適化問題を効率的に求解することができない。従って、式（５）における予測誤差の削減（最適解の求解）には改善の余地がある。
【００３３】
上記事情に鑑み、本発明は、イントラ予測においてクラス数と予測ブロック内の画素数とが１よりも大きな値であるという制約条件の下でも最適化問題を効率的に求解することが可能である線形予測係数出力方法、線形予測係数出力装置及び線形予測係数出力プログラムを提供することを目的としている。
【課題を解決するための手段】
【００３４】
本発明の一態様は、予測対象のデジタル信号と予測されたデジタル信号との差分である予測誤差について、線形予測に用いられる係数である予測係数の絶対値和の総和が上限値を満たすという制約条件の下で前記予測誤差の二乗和を最小化する線形予測器を用いて前記予測対象のデジタル信号を線形予測するための予測係数を出力する線形予測係数出力装置が実行する線形予測係数出力方法であって、前記予測対象のデジタル信号を線形予測するための予測係数の一部であり１次元のデジタル信号の予測係数である単信号予測係数の集合のうち前記制約条件を満たす前記単信号予測係数の集合を、前記予測対象のデジタル信号を線形予測するための予測係数と定めるステップと、前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和に基づいて前記上限値を定めるステップと、前記予測対象のデジタル信号を線形予測するための予測係数と前記上限値とを出力するステップとを含む線形予測係数出力方法である。
【００３５】
本発明の一態様は、上記の線形予測係数出力方法であって、前記予測対象のデジタル信号は、前記予測対象のデジタル信号を線形予測するための予測係数と符号化の際に参照されるデジタル信号との行列積である。
【００３６】
本発明の一態様は、上記の線形予測係数出力方法であって、前記制約条件を満たす前記単信号予測係数の集合における前記単信号予測係数の絶対値和の上限値の増加量と前記予測誤差の二乗和の減少量との比である予測誤差削減率のうち、前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数であるＬ０ノルムの変化量が１である前記予測誤差削減率と前記Ｌ０ノルムの変分との組が列挙されたリストを前記単信号予測係数ごとに出力するステップと、列挙された全ての前記予測誤差削減率と前記Ｌ０ノルムの変分との組が統合されたリストである統合リストを出力するステップと、前記予測誤差削減率が大きい順に前記組を前記統合リストから選択し、前記組ごとに前記Ｌ０ノルムの変分の累積和を算出することで、前記予測対象のデジタル信号を線形予測するための予測係数の全体の前記Ｌ０ノルムを算出するステップと、前記予測対象のデジタル信号を線形予測するための予測係数の全体の前記Ｌ０ノルムが前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和以下である場合、前記組の一方の前記予測誤差削減率を、前記予測対象のデジタル信号を線形予測するための予測係数の全体の前記予測誤差削減率と定めるステップとを含む。
【００３７】
本発明の一態様は、予測対象のデジタル信号と予測されたデジタル信号との差分である予測誤差について、空間的な相関を利用する線形予測に用いられる係数である予測係数の絶対値和の総和が上限値を満たすという制約条件の下で前記予測誤差の二乗和を最小化する線形予測器を用いて前記予測対象のデジタル信号を線形予測するための予測係数を出力する線形予測係数出力装置であって、前記予測対象のデジタル信号を線形予測するための予測係数の一部であり１次元のデジタル信号の予測係数である単信号予測係数の集合のうち前記制約条件を満たす前記単信号予測係数の集合を、前記予測対象のデジタル信号を線形予測するための予測係数と定める予測係数決定部と、前記予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和に基づいて前記上限値を定める上限決定部と、前記予測対象のデジタル信号を線形予測するための予測係数と前記上限値とを出力する予測係数出力部とを備える線形予測係数出力装置である。
【００３８】
本発明の一態様は、上記の線形予測係数出力方法をコンピュータに実行させるための線形予測係数出力プログラムである。
【発明の効果】
【００３９】
本発明により、イントラ予測においてクラス数と予測ブロック内の画素数とが１よりも大きな値であるという制約条件の下でも最適化問題を効率的に求解することが可能である。
【図面の簡単な説明】
【００４０】
【図１】実施形態における、エンコード処理の入出力とデコード処理の入出力を示す図である。
【図２】実施形態における、全予測係数の最適化問題の入出力の関係の例を示す図である。
【図３】実施形態における、２個のＬＡＳＳＯについて、単一上限と予測誤差削減率との対応関係を示した図である。
【図４】実施形態における、ＬＡＳＳＯ解算出部における入出力の例を示す図である。
【図５】実施形態における、１個のＬＡＳＳＯ解に対して予測係数のＬ０ノルムが変化する予測誤差削減率とＬ０ノルムの変分とを出力する例を示す図である。
【図６】実施形態における、各ＬＡＳＳＯ解算出部が算出した予測誤差削減率及びＬ０ノルム変化量を統合する例を示す図である。
【図７】実施形態における、Ｌ０ノルム総和上限に関する制約条件を満たす最小の予測誤差削減率を算出する例を示す図である。
【図８】実施形態における、ＬＡＲＳ等のＬＡＳＳＯ解算出部ごとに、単画素予測係数を算出する例を示す図である。
【図９】実施形態における、ロスレス符号化を実行する動画像符号化装置の構成の例を示すブロック図である。
【図１０】実施形態における、動画像復号装置の構成の例を示すブロック図である。
【図１１】実施形態における、図９に示すイントラ予測部の詳細な構成の例を示すブロック図である。
【図１２】実施形態における、図１１に示すイントラ予測部の詳細な動作の例を説明するフローチャートである。
【図１３】実施形態における、図１０に示すイントラ予測部の詳細な構成の例を示すブロック図である。
【図１４】実施形態における、図１３に示すイントラ予測部の詳細な動作の例を示すフローチャートである。
【図１５】実施形態における、図１１に示すイントラ予測係数生成部の詳細な構成の例を示すブロック図である。
【図１６】実施形態における、図１５に示すイントラ予測係数生成部の詳細な動作の例を示すフローチャートである。
【図１７】従来技術における、イントラ予測部の詳細な構成の例を示すブロック図である。
【図１８】従来技術における、図１７に示すイントラ予測部の詳細な動作の例を示すフローチャートである。
【図１９】複数の予測ブロックに分割された符号化対象フレームにおける、予測に用いられる参照画素及び被予測画素の関係の例を示す図である。
【図２０】予測ブロックを複数のクラスに分類する方法の例を示す図である。
【発明を実施するための形態】
【００４１】
本発明の実施形態について、図面を参照して詳細に説明する。
まず、線形予測係数を出力する原理について説明する。式（７）に示される最適化問題を求解するため、式（７）は、式（８）に示される単画素予測係数（単信号予測係数）の設計問題に書き換えられる。
【００４２】
【数８】
2018098581.tif 000010
【００４３】
ここで、θｃ［ｊ］は、各単画素予測係数に対して定める係数の絶対値和の上限値である。以下では、θｃ［ｊ］を「単一上限」という。式（８）に示される最適化問題は、複数のＬＡＳＳＯを含んでいる。式（８）に示される最適化問題では、全てのクラスと予測ブロック内の画素値とに関する単一上限の総和が総和上限となるという制約条件が課せられる。
【００４４】
図１は、実施形態における、エンコード処理の入出力とデコード処理の入出力を示す図である。本発明の実施形態を用いた予測方式を用いたエンコード処理及びデコード処理における入出力の例として、図１に示す入出力が想定される。
【００４５】
動画像符号化装置（エンコーダ）は、符号化対象となる原画像と、スパース性を制御するためのＬ０ノルム総和上限とを取得する。動画像符号化装置は、予測係数全体のＬ０ノルムがＬ０ノルム総和上限以下になるという制約条件を満たす予測係数の中から、本発明の実施形態で想定される予測方式によって出力された予測画像と原画像との差分の二乗和が最小となる全ての予測係数と、式（７）に対して設定されるＬ１ノルム総和上限θ１とを、動画像復号装置（デコーダ）に出力する。動画像符号化装置は、動画像符号化装置及び動画像復号装置の間で予測係数が共有されていないため、全ての予測係数を圧縮し、圧縮された全ての予測係数を動画像復号装置に伝送する必要がある。デコード処理では、動画像復号装置は、定められた予測係数と予測係数以外の符号化パラメータとを取得し、圧縮した復号画像を出力する。
【００４６】
本発明の実施形態の特徴の一つは、図１に示すように、式（７）に示すＬ１ノルム総和上限ではなく、スパース性を意味する全予測係数のＬ０ノルムの総和の上限を定めるパラメータを、動画像復号装置（デコーダ）が制約条件として取得する点である。映像符号化において、符号量抑制の観点でみると、Ｌ０ノルムの制約条件の下で解を導出することが望ましい場合がある。例えば、予測係数の大半が０である場合、予測係数が０であるか否かを表すフラグを導入することで、予測係数を表す符号量を大幅に削減できることが期待される。また、予測係数の符号量は、非零値の係数の符号量が支配的であると考えられる。このことから、予測係数の符号量制御方法として、Ｌ０ノルムの総和を制約する方法が考えられる。
【００４７】
従って、式（７）に示される最適化問題の求解にあたり、動画像符号化装置（エンコーダ）は、予測係数の全体の非零値の係数の個数の総和、すなわちＬ０ノルムの総和の上限を表すθ０を取得する。式（７）に示される最適化問題におけるＬ１ノルム総和上限と予測係数とを求解する方式を検討する必要がある。
【００４８】
上記の最適化問題を求解するために、全てのクラスと予測ブロック内の画素値とに対する単一上限θｃ［ｊ］を決定する必要がある。複数のＬＡＳＳＯにおけるｃ［ｊ］の設定を実行する際、計算量の低減を目的として、ＬＡＲＳ（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.
【００５０】
ＬＡＲＳは、ＬＡＳＳＯにおけるあらゆる単一上限に対応する単画素予測係数を、１度の最適化処理によって出力できる。上記の最適化の結果、各θｃ［ｊ］に対応する単画素予測係数ａｃ［ｊ］∈ＲＭｏが、ＲＭｏの空間内における複数の連結した線分の集合として与えられる。以下では、上記の線分の集合を「パス」という。パス上の各点は、θｃ［ｊ］＝｜｜ａｃ［ｊ］｜｜１と設定した際のＬＡＳＳＯの解と対応付けられる。
【００５１】
また、パスにおける線分同士の連結箇所でのみ、（１）１個の係数が非零値から零値になること、（２）１個の係数が零値から非零値になること、のいずれかが生じる。θｃ［ｊ］を設定する際にパスが求まっていれば、θｃ［ｊ］を変更した際の単画素予測係数ａｃ［ｊ］を求めるための計算時間は削減される。
【００５２】
従って、式（８）に示す最適化問題は、ＬＡＲＳを拡張することによって求解される。ＬＡＲＳを拡張する準備として、各単画素予測係数に対して、式（９）ように予測誤差削減効率ｅｃ［ｊ］が定義される。
【００５３】
【数９】
2018098581.tif 000011
【００５４】
ここで、ｆｃ［ｊ］は、取得された単画素予測係数ａｃ［ｊ］を使用した際の予測誤差の総和を返す関数である。ａｃ［ｊ］は、現在の単画素予測係数である。ｄｃ［ｊ］は、現在の単画素予測係数を更新する際の差分を表すベクトルである。予測誤差削減効率の式（９）は、単画素予測係数の絶対値和の増加量に対する予測誤差の低減量を表す。
【００５５】
ＬＡＲＳでは、パスを辿ることで予測誤差削減効率が常に最大となるように係数が設定される。以下では、予測誤差削減効率は、式（９）を用いて表される（参考文献１参照）。
【００５６】
図２は、全予測係数の最適化問題の入出力の関係の例を示す図である。式（７）に示されるＬ１ノルム総和上限が与えられた際の予測係数の全体の最適化問題Ｐは、図２に示すようなＬＡＲＳを用いる入出力の関係を有する。まず、全体として、最適化問題Ｐのソルバは、Ｌ１ノルム総和上限を取得した際、予測係数の全体のＬ１ノルムの総和がＬ１ノルム総和上限以下となるよう予測係数の全体を定める。
【００５７】
次に、最適化問題Ｐのソルバ（イントラ予測部）は、各単画素予測係数を定めるため、予測係数全体を単画素予測係数に分解し、ＬＡＲＳに代表されるＬＡＳＳＯ解算出部５０２を用いて各単画素予測係数を定める。ＬＡＳＳＯ解算出部５０２は、単画素予測係数に対するＬ１ノルムの上限を表す単一上限を取得する。ＬＡＳＳＯ解算出部５０２は、Ｌ１ノルムに関する制約条件を満たし、かつ、予測誤差の二乗和が最小化される単画素予測係数を出力する。この場合、予測係数全体のＬ１ノルムの総和に関する制約条件を満たすため、それぞれの単一上限の和がＬ１ノルム総和上限となるよう定める。このとき、単一上限をどのように定めれば画像全体の予測誤差の二乗和が最小化されるかは、既存の最適化手法では知られていない。
【００５８】
以下では、予測誤差の二乗和が最小化される単一上限の定め方について説明する。予測誤差の二乗和が最小化される単一上限の設定方法は、図３に示すように、（クラス数×被予測画素）の数だけ求解されたＬＡＳＳＯごとに定まる予測誤差削減率が全てのＬＡＳＳＯにおいて等しい場合における、単一上限の設定方法である。
【００５９】
図３は、２個のＬＡＳＳＯについて、単一上限と予測誤差削減率との対応関係を示した図である。以下、予測誤差の二乗和が最小化される単一上限を「最適な単一上限」という。まず、各ＬＡＳＳＯ解算出部５０２は、最適な単一上限を定めるため、単一上限と予測誤差削減率との対応関係を算出する。単一上限と予測誤差削減率との対応関係は、従来のＬＡＳＳＯ求解アルゴリズムであるＬＡＲＳを用いて導出は可能である。
【００６０】
全てのＬＡＳＳＯ解算出部５０２は、単一上限と予測誤差削減率との対応関係を算出した後、予測誤差削減率が全て等しくなるよう各単一上限を定める。この場合、図３に示された領域１０００の面積は、予測画像の画素値の二乗和を表す。式（７）に示される最適化問題は、全てのＬＡＳＳＯ解算出部５０２に関する領域１０００の面積の総和を最大化する問題と等価である。
【００６１】
ＬＡＳＳＯ解算出部５０２は、領域１０００の面積の総和を最大化するには、Ｌ０ノルム総和上限に関する制約条件を遵守するよう、予測誤差削減率を可能な限り下げる必要がある。また、図３のように単一上限（図３における領域１１００の面積）を定める際、各ＬＡＳＳＯ解算出部５０２は、予測誤差削減率をどのように定めればＬ０ノルム総和上限に関する制約上限が満たされるかを知る必要がある。以下では、Ｌ０ノルムに関する制約条件を満たした上で、予測係数の全体におけるＬ０ノルム総和上限と予測誤差削減率との対応関係を導出する方法について説明する。
【００６２】
図４は、ＬＡＳＳＯ解算出部５０２における入出力の例を示す図である。まず、図４に示すように、ＬＡＳＳＯ解算出部５０２は、予測誤差削減率とＬ０ノルム総和上限との対応関係を導出するため、予測係数全体を単画素予測係数に分割する。ＬＡＳＳＯ解算出部５０２は、予測誤差削減率、単一上限及び単画素予測係数の組を、ＬＡＲＳ等のＬＡＳＳＯ求解ソルバを用いて全て導出する。これにより、ＬＡＳＳＯ解算出部５０２は、単一上限又は予測誤差削減率を取得した場合、予測誤差削減率、単一上限又は単画素予測係数を出力することができる。
【００６３】
本発明の実施形態では、予測誤差削減率を均一化することが最適な単一上限を設定することであることに着目する。ＬＡＳＳＯ解算出部５０２は、予測係数全体のＬ０ノルム及びＬ１ノルムの対応関係を導出する問題を、予測係数全体のＬ０ノルムと予測誤差削減率との対応関係を導出する問題とみなす。ＬＡＳＳＯ解算出部５０２は、更に単画素予測係数ごとのＬ０ノルムと予測誤差削減率との対応関係を導出する部分問題に分割する。単画素予測係数におけるＬ０ノルムと予測誤差削減率との対応関係は、ＬＡＲＳ等の既存アルゴリズムを用いて探索可能である。ＬＡＳＳＯ解算出部５０２は、予測誤差削減率という指標を導入し、部分問題を統合することで、予測誤差削減率と予測係数全体のＬ０ノルムとの対応関係を容易に算出できる。
【００６４】
図５は、１個のＬＡＳＳＯ解に対して予測係数のＬ０ノルムが変化する予測誤差削減率とＬ０ノルムの変分とを出力する例を示す図である。最適化問題Ｐのソルバは、図５に示すように、単画素予測係数ごとに予測誤差削減率と単画素予測係数におけるＬ０ノルムの変化する変化点とを列挙する。最適化問題Ｐのソルバは、Ｌ０ノルムの変化量とＬ０ノルムが変化する予測誤差削減率との全てを、リストにまとめて出力する。
【００６５】
図５における左側に示された対応関係の横軸は、予測誤差削減率である。縦軸は、Ｌ０ノルムである。最適化問題Ｐのソルバは、単画素予測係数のＬ０ノルムの変化点を、ＬＡＲＳを用いて効率的に列挙可能である。最適化問題Ｐのソルバは、Ｌ０ノルムの変化点と変化する際の予測誤差削減率とを組として、全ての変化点を列挙して出力する。この場合、最適化問題Ｐのソルバは、予測誤差削減率が０になる場合にＬ０ノルムが変化しなくても、Ｌ０ノルムの変化点を出力する。なお、変化量は、増加する場合もあれば減少する場合もある。
【００６６】
図６は、各ＬＡＳＳＯ解算出部が算出した予測誤差削減率及びＬ０ノルム変化量を統合する例を示す図である。最適化問題Ｐのソルバは、図６に示すように、全ての単画素予測係数に対して、Ｌ０ノルムの変化量とＬ０ノルムが変化する予測誤差削減率とが列挙されたリストを求める。最適化問題Ｐのソルバは、Ｌ０ノルムの変化量とＬ０ノルムが変化する予測誤差削減率とが列挙されたリストを全て一つに統合し、予測誤差削減率が高い順に並び換える。図６における操作の目的は、ＬＡＳＳＯ解算出部５０２が予測係数全体のＬ０ノルムと予測誤差削減率との対応関係を知ることである。
【００６７】
最適化問題Ｐのソルバは、全体の予測誤差削減率がある一定値Ｅとなるように、単画素予測係数を設定する。その際、Ｌ０ノルムの変化量とＬ０ノルムが変化する予測誤差削減率との全ての組のうち、予測誤差削減率が一定値Ｅ以上の組におけるＬ０ノルムの変化量を全て加算した値が、予測係数全体のＬ０ノルムとなる。従って、ＬＡＳＳＯ解算出部５０２は、予測誤差削減率と予測係数全体のＬ０ノルムとの対応関係を、統合及び並び替え（ソート）後のリストに基づいて求めることができる。
【００６８】
次に、統合及び並び替え後のリストを用いて、Ｌ０ノルムの制約条件下における最小の予測誤差削減率を設定する方法を示す。
図７は、Ｌ０ノルム総和上限に関する制約条件を満たす最小の予測誤差削減率を算出する例を示す図である。すなわち、図７は、予測係数全体のＬ０ノルムと予測誤差削減率との対応関係を示す。横軸は予測誤差削減率を示す。縦軸は予測係数全体のＬ０ノルムの総和を示す。
【００６９】
最適化問題Ｐのソルバは、予測誤差削減率が高い順にＬ０ノルムの変化量を反映させることで、予測誤差削減率を変化させた際のＬ０ノルムの総和の推移を監視する。最適化問題Ｐのソルバは、予測係数全体のＬ０ノルムがＬ０ノルム総和上限以下である条件下において、予測誤差削減率が最も小さくなる予測誤差削減率を選択する。
【００７０】
この場合、Ｌ０ノルムの変化量が負の場合もあるため、Ｌ０ノルム総和上限を一度上回った場合においても、再びＬ０ノルム総和上限以下となる場合が存在する。従って、Ｌ０ノルムの変化量とＬ０ノルムが変化する予測誤差削減率との全てを、予測誤差削減率の選択に反映させる必要がある。最適化問題Ｐのソルバは、選択された最小の予測誤差削減率を、図３で示したように、各単画素予測係数に設定する最終的な予測誤差削減率Ｅｏｐｔとして算出する。
【００７１】
図８は、ＬＡＲＳ等のＬＡＳＳＯ解算出部５０２ごとに、単画素予測係数を算出する例を示す図である。最適化問題Ｐのソルバは、図７に示すように、算出された予測誤差削減率Ｅｏｐｔを各単画素予測係数に設定する。各ＬＡＳＳＯ解算出部５０２は、図８に示すように予測誤差削減率Ｅｏｐｔを取得し、予測誤差削減率がＥｏｐｔとなる単画素予測係数を出力する。
【００７２】
以上の基本的な考え方に基づいて、本発明の実施形態の線形予測係数出力装置を適用した動画像符号化装置及び動画像復号装置を説明する。
【００７３】
まず、実施形態の線形予測係数出力装置を適用した動画像符号化装置について説明する。
図９は、実施形態における、ロスレス符号化（可逆符号化）を実行する動画像符号化装置１００の構成の例を示すブロック図である。線形予測係数出力装置は、ロッシー符号化（非可逆符号化）を実行してもよい。
【００７４】
動画像符号化装置１００は、符号化対象の映像信号を取得し、符号化された映像を符号化ストリームとして出力する。以下では、符号化対象となる映像信号を単に「映像信号」という。
【００７５】
動画像符号化装置１００は、フレームメモリ１０１と、イントラ予測部１０２と、インター予測部１０３と、予測残差信号生成部１０４と、エントロピー符号化処理部１０５とを備える。動画像符号化装置１００は、磁気ハードディスク装置や半導体記憶装置等の不揮発性の記録媒体（非一時的な記録媒体）を有する記憶装置を更に備えてもよい。
【００７６】
フレームメモリ１０１とイントラ予測部１０２とインター予測部１０３と予測残差信号生成部１０４とエントロピー符号化処理部１０５とのうち一部又は全部は、例えば、ＣＰＵ（Central Processing Unit）等のプロセッサが、記憶部に記憶されたプログラムを実行することにより実現されてもよいし、ＬＳＩ（Large Scale Integration）やＡＳＩＣ（Application Specific Integrated Circuit）等のハードウェアを用いて実現されてもよい。
【００７７】
フレームメモリ１０１は、映像信号を取得する。フレームメモリ１０１は、インター予測部１０３がインター予測を実行する際に、映像信号をインター予測部１０３に参照画像として出力する。
【００７８】
イントラ予測部１０２（予測係数決定部）（上限決定部）（予測係数出力部）は、最適化問題Ｐのソルバとして、映像信号を取得し、予測係数を映像信号ごとに最適化する。イントラ予測部１０２は、最適化された予測係数を利用してイントラ予測を実行し、予測映像信号を予測残差信号生成部１０４に出力する。
【００７９】
イントラ予測部１０２は、予測対象の画素集合の信号として、符号化の際に参照される画素集合の信号と予測対象の画素集合の信号を線形予測するための予測係数との行列積を算出する。イントラ予測部１０２は、予測対象の画素集合の信号を線形予測するための予測係数の一部であり単画素の信号（１次元の信号）の予測係数である単画素予測係数（単信号予測係数）の集合のうち制約条件を満たす単画素予測係数の集合を、予測対象の画素集合の信号を線形予測するための予測係数として出力する。イントラ予測部１０２は、圧縮及び伝送の必要がある全ての予測係数と予測ブロックごとに定めるクラス番号等のイントラ予測情報とを、エントロピー符号化処理部１０５に出力する。イントラ予測部１０２は、本発明の実施形態における特徴的な処理部である。イントラ予測部１０２の詳細については、図８以降の図等を用いて説明する。
【００８０】
インター予測部１０３は、フレームメモリ１０１から映像信号を取得し、インター予測によって導出した予測映像信号を予測残差信号生成部１０４に出力する。インター予測部１０３は、動きベクトル等のインター予測に必要でありかつ圧縮及び伝送の必要があるインター予測情報を、エントロピー符号化処理部１０５に出力する。予測残差信号生成部１０４は、映像信号と、イントラ予測部１０２又はインター予測部１０３が出力した予測映像信号とを取得し、映像信号と予測映像信号の差分をエントロピー符号化処理部１０５に出力する。エントロピー符号化処理部１０５は、インター予測部１０３、イントラ予測部１０２からインター予測情報及びイントラ予測係数をそれぞれ取得し、予測残差、インター予測情報、イントラ予測情報及びイントラ予測係数に基づいて符号化ストリームを生成し、生成された符号化ストリームを出力する。
【００８１】
次に、実施形態の線形予測係数出力装置を適用した動画像復号装置について説明する。
図１０は、実施形態における、動画像復号装置２００の構成の例を示すブロック図である。動画像復号装置２００は、図９に示されたエントロピー符号化処理部１０５が出力した符号化ストリームを取得し、予測残差、インター予測情報、イントラ予測情報及びイントラ予測係数の計４個の情報を符号化ストリームから復号し、計４個の情報に基づく復号映像信号を出力する。なお、動画像符号化装置１００がロスレス符号化（可逆符号化）を実行している場合、符号化前の映像信号と復号映像信号とは同一である。
【００８２】
動画像復号装置２００は、エントロピー復号処理部２０１と、イントラ予測部２０２と、インター予測部２０３と、復号信号生成部２０４と、フレームメモリ２０５とを備える。動画像復号装置２００は、磁気ハードディスク装置や半導体記憶装置等の不揮発性の記録媒体（非一時的な記録媒体）を有する記憶装置を更に備えてもよい。
【００８３】
エントロピー復号処理部２０１とイントラ予測部２０２とインター予測部２０３と復号信号生成部２０４とのうち一部又は全部は、例えば、ＣＰＵ等のプロセッサが、記憶部に記憶されたプログラムを実行することにより実現されてもよいし、ＬＳＩやＡＳＩＣ等のハードウェアを用いて実現されてもよい。
【００８４】
エントロピー復号処理部２０１は、図９に示すエントロピー符号化処理部１０５が出力した符号化ストリームを取得し、予測残差、インター予測情報、イントラ予測情報及びイントラ予測係数の計４個の情報を符号化ストリームから復号し、計４個の情報を出力する。イントラ予測部２０２は、フレームメモリ２０５から復号映像信号を取得し、エントロピー復号処理部２０１からイントラ予測情報及びイントラ予測係数を取得し、イントラ予測処理によって生成された予測画像を出力する。
【００８５】
インター予測部２０３は、復号映像信号をフレームメモリ２０５から取得し、インター予測情報をエントロピー復号処理部２０１から取得し、インター予測処理により生成された予測画像を出力する。復号信号生成部２０４は、インター予測部２０３又はイントラ予測部２０２が出力した予測画像と、エントロピー復号処理部２０１が出力した予測残差とを取得し、予測画像及び予測残差を加算することで生成される復号映像信号を出力する。
【００８６】
フレームメモリ２０５は、復号信号生成部２０４が出力した復号映像信号を取得し、フレームメモリ２０５の記憶領域に復号映像信号を記憶する。復号映像信号は、インター予測部２０３及びイントラ予測部２０２によって、参照画素として利用される。
【００８７】
次に、図１１を参照して、動画像符号化装置１００に関して、図９に示すイントラ予測部１０２の構成を説明する。
図１１は、図９に示すイントラ予測部１０２の詳細な構成の例を示すブロック図である。イントラ予測部１０２は、イントラ予測係数初期化部３０１と、イントラ予測係数生成部３０２と、イントラ予測係数記憶部３０３と、イントラ予測処理部３０４と、イントラ予測情報記憶部３０５とを備える。
【００８８】
イントラ予測係数初期化部３０１は、動画像符号化装置１００に記録されたイントラ予測係数を取得し、イントラ予測係数記憶部３０３に出力する。図１１では、イントラ予測係数生成部３０２の動作が、従来の動作とは異なる。すなわち、イントラ予測係数生成部３０２は、符号化対象の映像信号と、予測係数全体のＬ１ノルムの上限を示す閾値であるＬ１ノルム総和上限と、各予測対象ブロックが属するクラス情報を表すイントラ予測情報とを取得し、予測係数全体のＬ１ノルムの総和がＬ１ノルム総和上限以下であるという制約条件の下で予測誤差の二乗和を最小化する予測係数を、イントラ予測係数記憶部３０３に出力する。
【００８９】
イントラ予測係数記憶部３０３は、イントラ予測係数初期化部３０１及びイントラ予測係数生成部３０２からイントラ予測係数を取得し、予測映像信号を生成するイントラ予測処理部３０４にイントラ予測係数を出力する。イントラ予測係数記憶部３０３は、エントロピー符号化処理部１０５にイントラ予測係数を出力する。
【００９０】
イントラ予測処理部３０４は、符号化対象となる映像信号と、イントラ予測係数記憶部３０３から予測係数とを取得し、生成されたイントラ予測信号を予測残差信号生成部１０４に出力する。イントラ予測処理部３０４は、予測されたブロックが属するクラス番号を、イントラ予測情報としてイントラ予測情報記憶部３０５に出力する。
【００９１】
イントラ予測情報記憶部３０５は、イントラ予測処理部３０４により選択されたイントラ予測情報を取得し、予測係数を決定するためにイントラ予測係数生成部３０２へイントラ予測係数を出力する。イントラ予測情報記憶部３０５は、イントラ予測情報を圧縮及び伝送する必要があるため、イントラ予測情報をエントロピー符号化処理部１０５に出力する。
【００９２】
次に、図１２を参照して、動画像符号化装置１００に関して、図１１に示すイントラ予測部１０２における動作を説明する。
図１２は、図１１に示すイントラ予測部１０２の詳細な動作の例を説明するフローチャートである。イントラ予測係数初期化部３０１は、エンコーダに記録されたイントラ予測係数を取得し、イントラ予測係数記憶部３０３に記録する（ステップＳ１０１）。
【００９３】
イントラ予測処理部３０４は、矩形状に分割された全てのブロックに対して、ステップＳ１０３からステップＳ１０５までの処理を実行する。イントラ予測処理部３０４は、全ての予測ブロックに関するイントラ予測処理が終了したか否かを判定する（ステップＳ１０２）。いずれかの予測ブロックに関するイントラ予測処理が終了してない場合（ステップＳ１０２：ＮＯ）、イントラ予測処理部３０４は、各予測対象ブロックがいずれのクラスに属せば符号量が最小化されるかを、逐次的に決定する。すなわち、イントラ予測処理部３０４は、予測ブロックごとにイントラ予測情報を決定する（ステップＳ１０３）。
【００９４】
イントラ予測処理部３０４は、ステップＳ１０３において決定されたクラスに属するイントラ予測係数を用いて、予測映像信号を出力する（ステップＳ１０４）。イントラ予測処理部３０４は、ステップＳ１０３において決定されたクラス番号を、イントラ予測情報記憶部３０５に記録する（ステップＳ１０５）。全ての予測ブロックに関するイントラ予測処理が終了した場合（ステップＳ１０２：ＹＥＳ）、イントラ予測処理部３０４は、映像信号、イントラ予測情報及び単一上限に基づいて、イントラ予測係数を最適化する（ステップＳ１０６）。イントラ予測処理部３０４は、イントラ予測係数をイントラ予測係数記憶部３０３に記録する（ステップＳ１０７）。
【００９５】
次に、図１３を参照して、動画像復号装置２００に関して、図１０に示すイントラ予測部２０２における構成を説明する。
図１３は、図１０に示すイントラ予測部２０２の詳細な構成を示すブロック図である。イントラ予測部２０２は、イントラ予測係数記憶部４０１と、イントラ予測情報記憶部４０２と、イントラ予測処理部４０３とを備える。イントラ予測係数記憶部４０１は、エントロピー復号処理部２０１からイントラ予測係数を取得し、イントラ予測係数記憶部４０１の記憶領域にイントラ予測係数を記憶する。
【００９６】
イントラ予測情報記憶部４０２は、エントロピー復号処理部２０１からイントラ予測情報を取得し、イントラ予測情報記憶部４０２の記憶領域にイントラ予測情報を記憶する。イントラ予測処理部４０３は、符号化対象である映像信号と、イントラ予測係数記憶部４０１からイントラ予測係数と、イントラ予測情報記憶部４０２からイントラ予測情報とを取得し、イントラ予測を実行した結果として予測映像信号を出力する。
【００９７】
次に、図１４を参照して、図１３に示すイントラ予測部２０２における動作を説明する。
図１４は、図１３に示すイントラ予測部２０２の詳細な動作の例を示すフローチャートである。イントラ予測係数記憶部４０１は、エントロピー復号処理部２０１からイントラ予測係数を取得し、イントラ予測係数記憶部４０１の記憶領域にイントラ予測係数を記憶する（ステップＳ２０１）。
【００９８】
イントラ予測処理部４０３は、矩形状に分割された全てのブロックに対して、ステップＳ２０３からステップＳ２０４までの処理を実行する。イントラ予測処理部４０３は、全ての予測ブロックに関するイントラ予測処理が終了したか否かを判定する（ステップＳ２０２）。いずれかの予測ブロックに関するイントラ予測処理が終了していない場合（ステップＳ２０２：ＮＯ）、イントラ予測処理部４０３は、各予測対象となるブロックが属するクラス番号をイントラ予測係数記憶部４０１から取得し、使用する予測係数を定める。すなわち、イントラ予測処理部４０３は、予測ブロックごとにイントラ予測情報を取得する（ステップＳ２０３）。
【００９９】
イントラ予測処理部４０３は、ステップＳ２０３において決定された予測ブロックに対してイントラ予測処理を実行し、予測映像信号を出力する（ステップＳ２０４）。全ての予測ブロックに関するイントラ予測処理が終了している場合（ステップＳ２０２：ＹＥＳ）、イントラ予測処理部４０３は、処理を終了する。
【０１００】
次に、図１５を参照して、動画像符号化装置１００のイントラ予測部１０２に関して、図１１に示すイントラ予測係数生成部３０２の構成を説明する。
図１５は、図１１に示すイントラ予測係数生成部３０２の詳細な構成の例を示すブロック図である。イントラ予測係数生成部３０２は、イントラ予測情報分割部５０１と、ＬＡＳＳＯ解算出部５０２と、Ｌ０ノルム変化点抽出部５０３と、Ｌ０ノルム変化点統合部５０４と、終了判定部５０５と、Ｌ０ノルム更新部５０６と、Ｌ０ノルム記憶部５０７と、準拠判定部５０８と、予測誤差削減率更新部５０９と、予測誤差削減率記憶部５１０と、Ｌ０ノルム変化点リスト更新部５１１とを備える。
【０１０１】
イントラ予測情報分割部５０１は、符号化対象となる入力映像信号と各予測ブロックが属するクラス番号であるイントラ予測情報とを取得し、各単画素予測係数の最適化に必要な情報に入力映像信号及びイントラ予測情報を分割する。イントラ予測情報分割部５０１は、各単画素予測係数の最適化に必要な情報をＬＡＳＳＯ解算出部５０２に出力する。
【０１０２】
ＬＡＳＳＯ解算出部５０２は、イントラ予測情報分割部５０１から分割後の入力映像信号およびイントラ予測情報を取得し、ＬＡＲＳ等のＬＡＳＳＯ求解ソルバを用いて、予測誤差削減率、単一上限及び単画素予測係数の組を全て導出する。ＬＡＳＳＯ解算出部５０２は、予測誤差削減率、単一上限及び単画素予測係数の組の全てを、Ｌ０ノルム変化点抽出部５０３に出力する。ＬＡＳＳＯ解算出部５０２は、図３に示すように揃えるべき予測誤差削減率を、予測誤差削減率記憶部５１０から取得する。ＬＡＳＳＯ解算出部５０２は、各ＬＡＳＳＯ解算出部５０２で予測誤差削減率が一定となる単画素予測係数を算出し、イントラ予測係数としてイントラ予測係数記憶部３０３に記録する。
【０１０３】
Ｌ０ノルム変化点抽出部５０３は、予測誤差削減率、単一上限及び単画素予測係数の組の全てを、ＬＡＳＳＯ解算出部５０２から取得する。Ｌ０ノルム変化点抽出部５０３は、各単画素予測係数においてＬ０ノルムが変化する予測誤差削減率の値と変化量（±１）との組を算出し、全ての組を一つのリストとしてまとめる。Ｌ０ノルム変化点抽出部５０３は、Ｌ０ノルム変化点統合部５０４にリストを出力する。
【０１０４】
Ｌ０ノルム変化点統合部５０４は、予測誤差削減率及びＬ０ノルムの変化量のリストを、最適化する単画素予測係数の数だけ取得する。Ｌ０ノルム変化点統合部５０４は、全てのリストを一つのリストとして統合して、統合されたリストを終了判定部５０５（予測誤差削減率探索終了判定部）に出力する。以下、統合されたリストを「統合リスト」という。
【０１０５】
終了判定部５０５は、Ｌ０ノルム変化点統合部５０４又はＬ０ノルム変化点リスト更新部５１１から、統合リストを取得する。終了判定部５０５は、統合リストが空であるか否かを判定する。終了判定部５０５は、統合リストが空ではなく要素が含まれている場合、要素が含まれている統合リストをＬ０ノルム更新部５０６に出力する。終了判定部５０５は、統合リストが空である場合、反復終了フラグを予測誤差削減率記憶部５１０に出力する。終了判定部５０５は、Ｌ０ノルム変化点リスト更新部５１１に統合リストを出力する。
【０１０６】
Ｌ０ノルム更新部５０６は、統合リストを終了判定部５０５から取得する。Ｌ０ノルム更新部５０６は、取得された統合リストの中から予測誤差削減率が最大である組Ｔを選択する。Ｌ０ノルム更新部５０６は、予測係数全体のＬ０ノルムをＬ０ノルム記憶部５０７から取得する。Ｌ０ノルム更新部５０６は、予測誤差削減率が最大である組ＴにおけるＬ０ノルムの変化量を、予測係数全体のＬ０ノルムに加算する。Ｌ０ノルム更新部５０６は、加算後のＬ０ノルムの総和と統合リストとを、Ｌ０ノルム記憶部５０７に記録する。
【０１０７】
Ｌ０ノルム記憶部５０７は、予測誤差削減率が最大である組ＴにおけるＬ０ノルムの変化量を予測係数全体のＬ０ノルムに加算した結果を、Ｌ０ノルム更新部５０６から取得する。Ｌ０ノルム記憶部５０７は、予測誤差削減率が最大である組ＴにおけるＬ０ノルムの変化量を予測係数全体のＬ０ノルムに加算した結果を、Ｌ０ノルム記憶部５０７の記憶領域に記憶する。Ｌ０ノルム記憶部５０７は、記憶している予測係数全体のＬ０ノルムの総和に変化量を加算するため、記憶しているＬ０ノルムの累積和をＬ０ノルム更新部５０６に出力する。
【０１０８】
準拠判定部５０８（Ｌ０ノルム制約準拠判定部）は、統合リストとＬ０ノルムの累積和とを、Ｌ０ノルム更新部５０６から取得する。準拠判定部５０８は、Ｌ０ノルムの総和がＬ０ノルム総和上限以下であるか否か判定する。準拠判定部５０８は、Ｌ０ノルム総和上限以下である場合、予測誤差削減率更新部５０９に統合リストを出力する。準拠判定部５０８は、Ｌ０ノルム総和上限以下を超えている場合、Ｌ０ノルム変化点リスト更新部５１１に統合リストを出力する。
【０１０９】
予測誤差削減率更新部５０９は、統合リスト内で最大の予測誤差削減率を持つ組Ｔにおける予測誤差削減率を、取得された統合リストから抽出する。予測誤差削減率更新部５０９は、統合リスト内で最大の予測誤差削減率を持つ組Ｔにおける予測誤差削減率を、予測誤差削減率記憶部５１０に記録する。予測誤差削減率更新部５０９は、統合リスト更新フラグを、Ｌ０ノルム変化点リスト更新部５１１に出力する。
【０１１０】
予測誤差削減率記憶部５１０は、更新後の予測誤差削減率を予測誤差削減率更新部５０９から取得する。予測誤差削減率記憶部５１０は、予測誤差削減率記憶部５１０の記憶領域に記憶する。予測誤差削減率記憶部５１０は、反復終了フラグを終了判定部５０５から取得する。予測誤差削減率記憶部５１０は、予測誤差削減率記憶部５１０が記憶しているＬ０ノルム総和上限の制約条件を満たす予測誤差削減率のうち最小の予測誤差削減率を、ＬＡＳＳＯ解算出部５０２に出力する。
【０１１１】
Ｌ０ノルム変化点リスト更新部５１１は、統合リストを準拠判定部５０８から取得する。Ｌ０ノルム変化点リスト更新部５１１は、統合リスト内で最大の予測誤差削減率を持つ組Ｔを、統合リストから削除する。Ｌ０ノルム変化点リスト更新部５１１は、統合リスト内で最大の予測誤差削減率を持つ組Ｔが削除された統合リストを、終了判定部５０５に出力する。
【０１１２】
次に、図１６を参照して、符号化時におけるイントラ予測係数生成部３０２の動作を説明する。
図１６は、図１５に示すイントラ予測係数生成部３０２の詳細な動作の例を示すフローチャートである。図１６に示すフローチャートは、図１２に示すステップＳ１０６の詳細を表す。
【０１１３】
イントラ予測情報分割部５０１は、符号化対象となる入力映像信号と各予測ブロックが属するクラス番号であるイントラ予測情報とを、各単画素予測係数の最適化に必要な情報に分割する（ステップＳ３０１）。ＬＡＳＳＯ解算出部５０２は、分割された単画素予測係数ごとの最適化問題を、ＬＡＲＳ等のＬＡＳＳＯソルバを用いて求解する。ＬＡＳＳＯ解算出部５０２は、予測誤差削減率、単一上限及び単画素予測係数の組の全てを、Ｌ０ノルム変化点抽出部５０３に出力する（ステップＳ３０２）。
【０１１４】
Ｌ０ノルム変化点抽出部５０３は、得られた予測誤差削減率、単一上限及び単画素予測係数の組の全てを用いて、全ての予測誤差削減率及びＬ０ノルムの変化量を算出し、リストとしてまとめる。Ｌ０ノルム変化点抽出部５０３は、算出したリストをＬＡＳＳＯソルバごとにＬ０ノルム変化点統合部５０４に出力する（ステップＳ３０３）。
【０１１５】
Ｌ０ノルム変化点統合部５０４は、ＬＡＳＳＯソルバごとに算出されたリストを全て統合し、統合リストを作成する（ステップＳ３０４）。Ｌ０ノルム変化点統合部５０４は、予測誤差削減率とＬ０ノルムの変分との組の統合リストを、予測誤差削減率が大きい順に並び替える（ステップＳ３０５）。予測誤差削減率更新部５０９は、Ｌ０ノルム総和上限の制約条件を満たし、最小の予測誤差削減率を記録するための予測誤差削減率記憶部５１０を初期化する。Ｌ０ノルム更新部５０６は、全予測係数Ｌ０ノルムの総和を記録するためのＬ０ノルム記憶部５０７を初期化する（ステップＳ３０６）。
【０１１６】
終了判定部５０５は、統合リスト内が空になるまで、ステップＳ３０８からステップＳ３１２までを反復させる。すなわち、終了判定部５０５は、統合リスト内が空であるか否かを判定する（ステップＳ３０７）。統合リスト内が空である場合（ステップＳ３０７：ＹＥＳ）、終了判定部５０５は、ステップＳ３１３に処理を進める。統合リストが空ではなく要素が含まれている場合（ステップＳ３０７：ＮＯ）、Ｌ０ノルム更新部５０６は、取得された統合リストの中から予測誤差削減率が最大である組Ｔを選択する（ステップＳ３０８）。
【０１１７】
Ｌ０ノルム更新部５０６は、予測係数全体のＬ０ノルムをＬ０ノルム記憶部５０７から取得する。Ｌ０ノルム更新部５０６は、予測誤差削減率が最大である組ＴにおけるＬ０ノルムの変化量（変分）を、予測係数全体のＬ０ノルムに加算する（ステップＳ３０９）。準拠判定部５０８は、Ｌ０ノルム記憶部５０７に記憶されているＬ０ノルムの総和がＬ０ノルム総和上限以下であるか否か判定する（ステップＳ３１０）。
【０１１８】
Ｌ０ノルムの総和がＬ０ノルム総和上限を超えている場合（ステップＳ３１０：ＮＯ）、準拠判定部５０８は、ステップＳ３１２に処理を進める。Ｌ０ノルムの総和がＬ０ノルム総和上限以下である場合（ステップＳ３１０：ＹＥＳ）、予測誤差削減率更新部５０９は、統合リスト内で最大の予測誤差削減率を持つ組Ｔにおける予測誤差削減率を、予測誤差削減率記憶部５１０に記録する（ステップＳ３１１）。予測誤差削減率更新部５０９は、統合リスト内で最大の予測誤差削減率を持つ組Ｔを、統合リストから削除する（ステップＳ３１２）。ＬＡＳＳＯ解算出部５０２は、予測誤差削減率Ｅｏｐｔを取得し、予測誤差削減率がＥｏｐｔとなる単画素予測係数を導出する（ステップＳ３１３）。
【０１１９】
本発明の実施形態では、イントラ予測部１０２がイントラ予測係数生成部３０２を有している点が、従来技術にない特徴である。イントラ予測部１０２とイントラ予測部１０２ａとの比較のため、従来技術におけるイントラ予測部１０２ａの詳細な構成及び動作を示す。
【０１２０】
次に、比較のため、従来技術における動画像符号化装置のイントラ予測部１０２ａの詳細な構成を図１７に示す。
図１７は、従来技術における、イントラ予測部１０２ａの詳細な構成の例を示すブロック図である。イントラ予測部１０２ａは、イントラ予測処理部６０１と、イントラ予測情報記憶部６０２と、イントラ予測情報選択部６０３と、イントラ予測係数記憶部６０４とを備える。
【０１２１】
イントラ予測処理部６０１は、イントラ予測係数記憶部６０４から予測係数を取得し、符号化対象の映像信号を取得し、イントラ予測を実行することで予測映像信号を出力する。また、イントラ予測処理部６０１は、各予測ブロックが属するクラス番号を選択し、イントラ予測情報記憶部６０２に出力する。
【０１２２】
イントラ予測情報記憶部６０２は、イントラ予測処理部６０１から出力されたイントラ予測情報を取得する。イントラ予測情報記憶部６０２は、圧縮及び伝送が必要であるイントラ予測情報を、エントロピー符号化処理部１０５に出力する。イントラ予測情報選択部６０３は、イントラ予測情報記憶部６０２に記憶されているイントラ予測情報から、イントラ予測情報を選択する。イントラ予測係数記憶部６０４は、イントラ予測係数記憶部６０４の記憶領域に記憶されているイントラ予測係数を、イントラ予測処理部６０１に出力する。
【０１２３】
次に、従来技術における動画像符号化装置に関して、図１７に示すイントラ予測部１０２ａの処理動作を図１８に示す。
図１８は、従来技術における、図１７に示すイントラ予測部１０２ａの詳細な動作の例を示すフローチャートである。イントラ予測処理部６０１は、イントラ予測係数記憶部６０４の記憶領域に記憶されているイントラ予測係数を取得する（ステップＳ４０１）。イントラ予測処理部６０１は、全ての予測ブロックに対する処理が終わるまで、ステップＳ４０３からステップＳ４０５までの処理を反復する。イントラ予測処理部６０１は、全ての予測ブロックに関するイントラ予測処理が終了したか否かを判定する（ステップＳ４０２）。
【０１２４】
いずれかの予測ブロックに関するイントラ予測処理が終了していない場合（ステップＳ４０２：ＮＯ）、イントラ予測処理部６０１は、各予測ブロックが属するクラス番号であるイントラ予測情報を、符号量が最小となるよう決定する（ステップＳ４０３）。イントラ予測処理部６０１は、決定されたクラス番号に属するイントラ予測係数を用いて、イントラ予測を実行し、予測映像信号を出力する。すなわち、イントラ予測処理部６０１は、予測ブロックごとにイントラ予測処理を実行する（ステップＳ４０４）。
【０１２５】
イントラ予測処理部６０１は、ステップＳ４０３において定められたイントラ予測情報を圧縮及び伝送するため、イントラ予測情報をイントラ予測情報記憶部６０２へ記録する（ステップＳ４０５）。全ての予測ブロックに関するイントラ予測処理が終了していない場合（ステップＳ４０２：ＹＥＳ）、イントラ予測処理部６０１は、処理を終了する。
【０１２６】
以上のように、実施形態の線形予測係数出力装置は、予測対象のデジタル信号と予測されたデジタル信号との差分である予測誤差について、空間的な相関を利用する線形予測に用いられる係数である予測係数の絶対値和の総和が上限値を満たすという制約条件の下で予測誤差の二乗和を最小化する線形予測器を用いて予測対象のデジタル信号を線形予測するための予測係数を出力する。イントラ予測部１０２は、予測係数決定部として、予測対象のデジタル信号を線形予測するための予測係数の一部であり１次元のデジタル信号の予測係数である単信号予測係数の集合のうち制約条件を満たす単信号予測係数の集合を、予測対象のデジタル信号を線形予測するための予測係数と定める。イントラ予測部１０２は、上限決定部として、予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和に基づいて上限値を定める。イントラ予測部１０２は、予測係数出力部として、予測対象のデジタル信号を線形予測するための予測係数と上限値とを出力する。
【０１２７】
これによって、実施形態の線形予測係数出力装置は、イントラ予測においてクラス数と予測ブロック内の画素数とが１よりも大きな値であるという制約条件の下でも、式（５）に示す条件に制約条件を緩和した最適化問題を効率的に求解することが可能である。実施形態の線形予測係数出力装置は、式（５）に示す条件に制約条件を緩和した最適化問題を効率的に求解することで、信号特性に適合したイントラ予測を実行することが可能である。
【０１２８】
また、従来の最適化問題の求解には、直感的なスパース性制御を与えるため、全予測係数のＬ０ノルムの制約上限の設定が困難であるという課題もある。Ｌ１ノルム総和上限による制約はスパース性を与えるために必要なパラメータである一方、符号量制御を行う観点から、直感的に正しいＬ１ノルム総和上限を与えることが困難である。この課題に対して、実施形態の線形予測係数出力装置は、式（５）に示す条件に制約条件を緩和した最適化問題のスパース性制御にＬ０ノルムの上限を直接指定することで、ユーザがスパース性をより容易に制御可能である。
【０１２９】
また、実施形態の線形予測係数出力装置は、デジタル信号に対する線形予測を実行するためのスパース性（非零値の係数がまばらに存在すること）を有する予測係数を、効率的に出力することが可能である。実施形態では、デジタル信号とは、映像符号化の場合、画素集合の信号である。単信号（１次元の信号）は、映像符号化の場合、単画素の信号である。なお、映像符号化の場合、デジタル信号を分割するとは、ブロック分割することである。
【０１３０】
実施形態のＬ０ノルム変化点抽出部５０３は、制約条件を満たす単信号予測係数の集合における単信号予測係数の絶対値和の上限値の増加量と予測誤差の二乗和の減少量との比である予測誤差削減率のうち、予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数であるＬ０ノルムの変化量が１である予測誤差削減率とＬ０ノルムの変分との組が列挙されたリストを単信号予測係数ごとに出力する。実施形態のＬ０ノルム変化点統合部５０４は、列挙された全ての予測誤差削減率とＬ０ノルムの変分との組が統合されたリストである統合リストを出力する。実施形態の予測誤差削減率更新部５０９は、予測誤差削減率が大きい順に組を統合リストから選択し、組ごとにＬ０ノルムの変分の累積和を算出することで、予測対象のデジタル信号を線形予測するための予測係数の全体のＬ０ノルムを算出する。実施形態の予測誤差削減率更新部５０９は、予測対象のデジタル信号を線形予測するための予測係数の全体のＬ０ノルムが予測対象のデジタル信号を線形予測するための予測係数に設定可能である非零値の係数の個数の総和以下である場合、組の一方の予測誤差削減率を、予測対象のデジタル信号を線形予測するための予測係数の全体の予測誤差削減率と定める。
【０１３１】
なお、本発明の実施形態における０でない係数を少なくするというのは手段の一つにすぎず、係る予測器に限定するものではない。本発明の実施形態による線形予測係数出力装置は音声など他のメディアの符号化や、工数や稼働の管理システム等様々な分野に適用可能である。その際０でない係数を少なくする、という条件は適用する分野に応じて設定すればよい。
【０１３２】
上述した実施形態における線形予測係数出力装置の少なくとも一部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【０１３３】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【産業上の利用可能性】
【０１３４】
本発明は、イントラ予測においてクラス数と予測ブロック内の画素数とが１よりも大きな値であるという制約条件の下でも最適化問題を効率的に求解することで、信号特性に適合したイントラ予測を可能にすることが不可欠な用途に適用できる。
【符号の説明】
【０１３５】
１００…動画像符号化装置、１０１…フレームメモリ、１０２…イントラ予測部、１０２ａ…イントラ予測部、１０３…インター予測部、１０４…予測残差信号生成部、１０５…エントロピー符号化処理部、２００…動画像復号装置、２０１…エントロピー復号処理部、２０２…イントラ予測部、２０３…インター予測部、２０４…復号信号生成部、２０５…フレームメモリ、３０１…イントラ予測係数初期化部、３０２…イントラ予測係数生成部、３０３…イントラ予測係数記憶部、３０４…イントラ予測処理部、３０５…イントラ予測情報記憶部、４０１…イントラ予測係数記憶部、４０２…イントラ予測情報記憶部、４０３…イントラ予測処理部、５０１…イントラ予測情報分割部、５０２…ＬＡＳＳＯ解算出部、５０３…Ｌ０ノルム変化点抽出部、５０４…Ｌ０ノルム変化点統合部、５０５…終了判定部、５０６…Ｌ０ノルム更新部、５０７…Ｌ０ノルム記憶部、５０８…準拠判定部、５０９…予測誤差削減率更新部、５１０…予測誤差削減率記憶部、５１１…Ｌ０ノルム変化点リスト更新部、６０１…イントラ予測処理部、６０２…イントラ予測情報記憶部、６０３…イントラ予測情報選択部、６０４…イントラ予測係数記憶部、１０００…領域、１１００…領域
【図１】
2018098581.tif 000012
【図２】
2018098581.tif 000013
【図３】
2018098581.tif 000014
【図４】
2018098581.tif 000015
【図５】
2018098581.tif 000016
【図６】
2018098581.tif 000017
【図７】
2018098581.tif 000018
【図８】
2018098581.tif 000019
【図９】
2018098581.tif 000020
【図１０】
2018098581.tif 000021
【図１１】
2018098581.tif 000022
【図１２】
2018098581.tif 000023
【図１３】
2018098581.tif 000024
【図１４】
2018098581.tif 000025
【図１５】
2018098581.tif 000026
【図１６】
2018098581.tif 000027
【図１７】
2018098581.tif 000028
【図１８】
2018098581.tif 000029
【図１９】
2018098581.tif 000030
【図２０】
2018098581.tif 000031