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