(57)【要約】【課題】画質の劣化を生じさせることなく，イントラ予測モードを選択するときの演算量を削減し，予測モード選択の高速化を実現する。【解決手段】予測モードのコスト算出に先立ち，被予測画素値和と参照画素値和と丸め誤差に対する補正値とから同コストの下限値を算出し（Ｓ５），各予測モードのコスト計算において下限値を利用した枝刈りを行い（Ｓ６），コストを最小化する予測モードを探索する。また，コストの下限値を算出する際に，四捨五入演算により発生する丸め誤差を予めルックアップテーブルに格納しておき，そのルックアップテーブルを参照することにより丸め誤差の補正値を算出する演算を省略できるようにする（Ｓ４）。【選択図】図１０
2006279374.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個（ｎ≧２）のイントラ予測モードの中から符号化コストが最小となる予測モードを選択しイントラ予測を行う画像符号化方法において，
前記ｎ個の予測モードの中の一つの予測モードｍ1 の符号化コストＥ（ｍ1 ）を算出し，暫定最小コストとして記憶する第１の過程と，
次にコスト算出対象となる予測モードｍi （ｉ＝２，３，…，ｎ）の符号化コストの下限値Ｌ（ｍi ）を算出する第２の過程と，
前記暫定最小コストと前記下限値Ｌ（ｍi ）との大小比較を行い，前記下限値Ｌ（ｍi ）が前記暫定最小コストよりも小さい場合にのみ，予測モードｍi に対する符号化コストＥ（ｍi ）を算出し，前記下限値Ｌ（ｍi ）が前記暫定最小コストより小さくない場合には，その予測モードｍi のコスト算出処理を打ち切る第３の過程と，
前記予測モードｍi に対する符号化コストＥ（ｍi ）を算出した場合に，その符号化コストＥ（ｍi ）と現在の前記暫定最小コストとの大小比較を行い，前記符号化コストＥ（ｍi ）が前記暫定最小コストよりも小さい場合に，前記符号化コストＥ（ｍi ）を新たな暫定最小コストとして記憶する第４の過程と，
前記第２の過程から前記第４の過程までを予測モードｍ2 から最終の予測モードｍn まで繰り返し，最終的に暫定最小コストとして記憶されている符号化コストＥ（ｍj ）に対応する予測モードｍj を最適予測モードとして選択する第５の過程とを有する
ことを特徴とするイントラ予測モード選択方法。
【請求項２】
前記第２の過程における下限値Ｌ（ｍi ）の算出では，予測モードｍi に対する参照画素値和を算出するとともに，下限値Ｌ（ｍi ）の算出において必要となる四捨五入演算により発生する丸め誤差に対する補正値を求め，あらかじめ算出した被予測画素値和と前記参照画素値和と前記丸め誤差に対する補正値とから予測誤差の最小値として下限値Ｌ（ｍi ）を算出する
ことを特徴とする請求項１記載のイントラ予測モード選択方法。
【請求項３】
前記第２の過程における丸め誤差に対する補正値を求める過程では，あらかじめ参照画素値の下位ビットの組み合わせで参照される位置に，それらの参照画素値に対応する丸め誤差に対する補正値が格納されたルックアップテーブルを用いて，該ルックアップテーブルから該当する予測モードｍi の丸め誤差に対する補正値を読み込む
ことを特徴とする請求項２記載のイントラ予測モード選択方法。
【請求項４】
前記ルックアップテーブルが予測モードｍi 毎に個別に設けられ，各予測モードｍi に対応するルックアップテーブルから該当する予測モードｍi の丸め誤差に対する補正値を読み込む
ことを特徴とする請求項３記載のイントラ予測モード選択方法。
【請求項５】
前記ルックアップテーブルが参照画素のクラスタリング結果に応じて個別に設けられ，参照画素のクラスタリング結果に対応するルックアップテーブルから該当する予測モードｍi の丸め誤差に対する補正値を読み込む
ことを特徴とする請求項３記載のイントラ予測モード選択方法。
【請求項６】
ｎ個（ｎ≧２）のイントラ予測モードの中から符号化コストが最小となる予測モードを選択しイントラ予測を行う画像符号化装置において，
暫定的に決定された最小予測誤差を記憶する暫定最小予測誤差記憶手段と，
前記ｎ個の予測モードの中の一つの予測モードｍ1 の予測誤差を算出し，前記暫定最小予測誤差記憶手段に格納する手段と，
被予測画素値和を算出する手段と，
前記予測モードｍ1 以外の各予測モードｍi （ｉ＝２，３，…，ｎ）毎に参照画素値和を算出する手段と，
参照画素値の下位ビットの組み合わせで参照される位置に，予測誤差の下限値Ｌ（ｍi ）の算出において必要となる四捨五入演算により発生する丸め誤差に対する補正値をあらかじめ記憶する補正値記憶手段と，
前記被予測画素値和と前記参照画素値和と前記補正値記憶手段から読み出された丸め誤差に対する補正値とから各予測モードｍi （ｉ＝２，３，…，ｎ）毎に予測誤差の下限値Ｌ（ｍi ）を算出する手段と，
前記暫定最小予測誤差記憶手段に記憶された予測誤差と前記下限値Ｌ（ｍi ）との大小比較を行い，前記予測誤差が前記下限値Ｌ（ｍi ）より小さい場合に，その予測モードｍi の予測誤差の算出を省略し，最適予測モード探索の枝刈りを行う手段と，
前記各予測モードｍi に対する処理の後，最終的に前記暫定最小予測誤差記憶手段に記憶された予測誤差に対応する予測モードｍj を最適予測モードとして選択する手段と，
選択された最適予測モードを用いてイントラ予測を行い入力した画像を符号化する手段とを備える
ことを特徴とする画像符号化装置。
【請求項７】
請求項１から請求項５までのいずれか１項に記載されたイントラ予測モード選択方法を，コンピュータに実行させるための画像符号化プログラム。
【請求項８】
請求項１から請求項５までのいずれか１項に記載されたイントラ予測モード選択方法を，コンピュータに実行させるための画像符号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，高能率画像信号符号化方法に関し，特にイントラ予測のモード選択時のコスト算出の演算量を削減可能にしたイントラ予測モード推定方法に関する。
【背景技術】
【０００２】
Ｈ．２６４（非特許文献１参照）のイントラ予測において，４×４サイズのブロックを符号化する場合，９つのモードのいずれかを用いる。このモードの選択は，符号化側で自由に設定することができる。最も単純な選択方法は，９つのモード全てに対して，以下に示すコストを算出し，同コストを最小化するモードを選択する方法である。
〔１〕各モードを用いた場合の予測信号を求める。
〔２〕原信号と予測信号との差分信号を求める。
〔３〕差分信号の絶対値和（ＳＡＤ）を求める。
〔４〕次式で与えられるコストを計算する。
【０００３】
ＳＡＤ＋ａ×λ（ＱＰ）                                          （１）
ここで，ａは定数，ＱＰは量子化パラメータ，λ（ＱＰ）は量子化パラメータＱＰの値に応じた加算項を返す関数である。
〔５〕上記〔１〕から〔４〕までの処理を９つのモードに対して繰り返し，コストを最小化するモードを選択する。
【０００４】
コストとして，ＳＡＤの代りに差分信号に対するアダマール変換を施し，その変換係数の和（ＳＡＴＤ）を用いる例も検討されているが，演算量を少なく抑える場合には，上述のＳＡＤを用いる方が適している。しかし，ＳＡＴＤではなくＳＡＤを用いたとしても，上述のような全モードを対象とした探索処理の場合，コスト算出の計算量は非常に大きなものとなる。
【０００５】
これに対し，予測モードのコスト算出の計算量を低減させるため，最適解であるモードを求めることをあきらめ，準最適解に相当する予測モードを求める方法が検討されている（非特許文献２，非特許文献３参照）。
【非特許文献１】“Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification”ITU-T Rec. H.264｜ISO/IEC 14496-10 AVC，JVT-G050r1，May ，2003．
【非特許文献２】P.Feng et.al.“Fast mode decision for intra prediction ”，JVT-I049，Sept. ，2003.
【非特許文献３】“Ｈ．２６４／ＡＶＣにおけるイントラ予測高速化の一検討”，高木幸一他，電子情報通信学会技術報告 IE2003-123 ，pp.51-54，2003．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述のように，準最適解に相当する予測モードを求める方法の場合，計算量の低減とひきかえに，予測誤差の増加を招く。準最適解を選択したことによる画質の劣化は画像に依存するため，画像によっては大きな劣化を引き起こす可能性が残る。このため，予測誤差を増加させることなく計算量を低減させる予測モードの選択法が必要となる。
【０００７】
本発明は，かかる事情に鑑みてなされたものであって，イントラ予測モード選択の基準となるコストの高速な計算法を確立することを目的とする。記述の簡略化のため，以下，単にモードとした場合は，イントラ予測モードを指すものとする。
【課題を解決するための手段】
【０００８】
イントラ予測モードのモード推定時に計算量の大部分を占めるのはコストの算出である。本発明では，コストの算出において，下限値を利用した枝刈りを行う。基本的な考え方は，次の通りである。
・モードのコストの算出に先立ち，コストの下限値を算出する。
・下限値を利用した枝刈りを行う。
・下限値算出の計算量をコストのそれと比べて，少なく抑える。
【０００９】
二つのモードｍ1 ，ｍ2 のコストを比較する場合，両モードに対するコストを直接比較するのではなく，モードｍ1 のコストＥ（ｍ1 ）に対して，モードｍ2 のコストＥ（ｍ2 ）の下限値Ｌ（ｍ2 ）との大小比較を行う。この時，
Ｅ（ｍ1 ）≦Ｌ（ｍ2 ）
であれば，Ｌ（ｍ2 ）がコストＥ（ｍ2 ）の下限値であるため，
Ｅ（ｍ1 ）≦Ｅ（ｍ2 ）
となり，Ｅ（ｍ2 ）を算出して比較する必要はない。つまり，Ｅ（ｍ2 ）の算出は，
Ｌ（ｍ2 ）＜Ｅ（ｍ1 ）
となる場合のみ行えば十分である。後述するように，コストの下限値は，コストに比べて少ない計算量での算出が可能である。このため，コストの下限値との比較を行い，コストの算出を省くことにより，コストの最小化を保証した上で，計算量の低減を図ることができる。
【００１０】
すなわち，本発明は，ｎ個（ｎ≧２）のイントラ予測モードの中から符号化コストが最小となる予測モードを選択しイントラ予測を行う画像符号化方法において，前記ｎ個の予測モードの中の一つの予測モードｍ1 の符号化コストＥ（ｍ1 ）を算出し，暫定最小コストとして記憶する第１の過程と，次にコスト算出対象となる予測モードｍi （ｉ＝２，３，…，ｎ）の符号化コストの下限値Ｌ（ｍi ）を算出する第２の過程と，前記暫定最小コストと前記下限値Ｌ（ｍi ）との大小比較を行い，前記下限値Ｌ（ｍi ）が前記暫定最小コストよりも小さい場合にのみ，予測モードｍi に対する符号化コストＥ（ｍi ）を算出し，前記下限値Ｌ（ｍi ）が前記暫定最小コストより小さくない場合には，その予測モードｍi のコスト算出を打ち切る第３の過程と，前記予測モードｍi に対する符号化コストＥ（ｍi ）を算出した場合に，その符号化コストＥ（ｍi ）と現在の前記暫定最小コストとの大小比較を行い，前記符号化コストＥ（ｍi ）が前記暫定最小コストよりも小さい場合に，前記符号化コストＥ（ｍi ）を新たな暫定最小コストとして記憶する第４の過程と，前記第２の過程から前記第４の過程までを予測モードｍ2 から最終の予測モードｍn まで繰り返し，最終的に暫定最小コストとして記憶されている符号化コストＥ（ｍj ）に対応する予測モードｍj を最適予測モードとして選択する第５の過程とを有することを特徴とする。
【００１１】
第３の過程による最適予測モードの探索における枝刈りによって，精度を落とすことなく演算量を削減することができる。
【００１２】
前記第２の過程における下限値Ｌ（ｍi ）の算出では，予測モードｍi に対する参照画素値和を算出するとともに，下限値Ｌ（ｍi ）の算出において必要となる四捨五入演算により発生する丸め誤差に対する補正値を求め，あらかじめ算出した被予測画素値和と前記参照画素値和と前記丸め誤差に対する補正値とから予測誤差の最小値として下限値Ｌ（ｍi ）を算出する。
【００１３】
被予測画素値和は全予測モードの探索において一度だけ算出すればよく，また参照画素値和の算出においても，最初の予測モードにおける予測誤差の算出において算出済みの結果を利用することができるので，下限値Ｌ（ｍi ）を少ない演算量で求めることができる。
【００１４】
特に，補正値を求める過程では，あらかじめ参照画素値の下位ビットの組み合わせで参照される位置に，それらの参照画素値に対応する丸め誤差に対する補正値が格納されたルックアップテーブルを用意しておき，該当する予測モードｍi の丸め誤差に対する補正値をそのルックアップテーブルから読み込む。これにより，丸め誤差に対する補正値をその都度演算する必要はなく，高速に求めることができる。
【００１５】
また，前記ルックアップテーブルを予測モードｍi 毎に個別に設ける。または，ルックアップテーブルを参照画素のクラスタリング結果に応じて個別に設ける。これにより，ルックアップテーブルのサイズを，１つのルックアップテーブルにまとめた場合に比較して小さくすることができる。
【発明の効果】
【００１６】
本発明では，Ｈ．２６４等の高能率画像信号符号化におけるイントラ予測のモード選択時のコスト計算において，既算出の計算結果を再利用してコスト算出の演算量を削滅する。この際，本発明ではコスト計算に近似は含まれないため，本発明の導入によるモード選択結果は導入前と変化はなく，画質の劣化は発生しない。
【発明を実施するための最良の形態】
【００１７】
以下の説明では，簡単のため，モード選択に用いるコスト関数を予測誤差（ＳＡＤ）とする。なお，符号化対象ブロック（以下，ＭＢと記す）の左上角の座標を（ｘ0 ，ｙ0 ）とおく。ＭＢのサイズが４×４の場合と１６×１６の場合に分けて説明する。
【００１８】
１．ブロックサイズが４×４の場合の実施の形態
ＭＢのサイズは全て４×４として説明する。コスト関数値の計算法については，まず，予測において丸め誤差が発生しない垂直方向予測および水平方向予測の場合を説明する。次に，これら以外の場合を説明する。
【００１９】
１−１．丸め誤差が発生しない場合
モード番号０の予測（垂直方向予測）およびモード番号１の予測（水平方向予測）のコスト算出は，以下のように行う。
【００２０】
まずは，この２つのモードに対するコスト算出に先立ち，モード番号２の予測（ＤＣ予測）に対する予測誤差を求める。同予測誤差をＥ（２）4x4 とする。このＥ（２）4x4 をレジスタεに格納する。本モードの場合，参照画素が参照可能（参照可能な場合，参照画素は“available for Intra ＿4x4prediction ”となっている）か否かに応じて，予測値ｑ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］（ｘ＝０，１，２，３；ｙ＝０，１，２，３）は，次式のようになる。なお，座標［ｘ0 ＋ｘ，ｙ0 ＋ｙ］の画素値をＰ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］としている。
【００２１】
(ｉ) Ｐ［ｘ0 ＋ｘ，ｙ0 −１］，Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が，ともに参照可能な場合：
【００２２】
【数１】
2006279374.tif 000003
(ii) Ｐ［ｘ0 ＋ｘ，ｙ0 −１］は参照可能であり，Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が参照可能でない場合：
【００２３】
【数２】
2006279374.tif 000004
(iii)  Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が参照可能であり，Ｐ［ｘ0 ＋ｘ，ｙ0 −１］は参照可能でない場合：
【００２４】
【数３】
2006279374.tif 000005
(iv) Ｐ［ｘ0 ＋ｘ，ｙ0 −１］，Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が，ともに参照可能でない場合：
ｑ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］＝１２８                                    （５）
ｑ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］の算出過程で求めた次の値を，メモリまたはレジスタに格納しておく。
【００２５】
【数４】
2006279374.tif 000006
また，次の値も計算し，格納しておく。
【００２６】
【数５】
2006279374.tif 000007
なお，以下では，記述の簡単化のため，次のように略記する。
【００２７】
ｐ［ｘ，ｙ］≡Ｐ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］
次に，ｐ［ｘ，−１］（ｘ＝０，１，２，３）が参照可能であれば，モード番号０の予測（垂直予測）を行う。
【００２８】
図１は，ブロックサイズが４×４の場合の垂直予測モードを示している。図１（ａ）に示すように，垂直予測モードでは，符号化対象ブロックに隣接する上の４画素を垂直方向に下ろして参照画素とする。被予測画素と参照画素とが図１（ｂ），（ｃ）に示す関係にあることから，予測誤差Ｅ（０）4x4 は次の下限値を持つ。
【００２９】
【数６】
2006279374.tif 000008
このとき次式を満たせば，垂直予測は予測誤差を最小化できないと判断できるため，予測誤差の算出は行うことなく，次の処理に移る。
【００３０】
【数７】
2006279374.tif 000009
上式を満たさないときのみ，垂直予測に対する予測誤差Ｅ（０）4x4 を求める。
Ｅ（０）4x4 ＜εであれば，レジスタεの値をＥ（０）4x4 で上書きして置き換える。
【００３１】
次に，ｐ［−１，ｙ］（ｙ＝０，１，２，３）が参照可能であれば，モード番号１の予測（水平予測）を行う。
【００３２】
図２は，ブロックサイズが４×４の場合の水平予測モードを示している。図２（ａ）に示すように，水平予測モードでは，符号化対象ブロックに隣接する左の４画素を水平方向にのばして参照画素とする。被予測画素と参照画素とが図２（ｂ），（ｃ）に示す関係にあることから，予測誤差Ｅ（１）4x4 は次の下限値を持つ。
【００３３】
【数８】
2006279374.tif 000010
このとき次式を満たせば，水平予測は予測誤差を最小化できないと判断できるため，予測誤差の算出は行うことなく，次の処理に移る。
【００３４】
【数９】
2006279374.tif 000011
上式を満たさないときのみ，水平予測に対する予測誤差Ｅ（１）4x4 を求める。
Ｅ（１）4x4 ＜εであれば，レジスタεの値をＥ（１）4x4 で上書きして置き換える。
【００３５】
１−２．丸め誤差が発生する場合
図３は，４×４ブロックの予測モードとモード番号の関係を示している。Ｈ．２６４では，各モード番号０〜８の予測モードの予測に用いる参照画素の適用方向が図３に示すようになっている。これらの予測モードのうち，モード番号３〜８に対して，予測誤差の下限値を算出する場合，四捨五入演算により発生する丸め誤差を考慮する必要がある。
【００３６】
前述した垂直方向予測および水平方向予測モードの場合との違いは，この丸め誤差に対する補正値の算出が必要となる点である。なお，以下では，除算により得た実数値は切り捨てにより整数値に丸めるものとする。図４に，補正値の計算例を示す。
【００３７】
モード番号３の場合の例に以下に示す。同モードの予測を行う場合，予測誤差Ｅ（３）4x4 は次の下限値を持つ。
【００３８】
【数１０】
2006279374.tif 000012
ここで，Ｓ（３）4x4 は参照画素の加重和として求める以下の値である。
【００３９】
【数１１】
2006279374.tif 000013
また，Ｒ（３）4x4 は，四捨五入演算により発生する丸め誤差を考慮した補正値であり，次式となる。
【００４０】
【数１２】
2006279374.tif 000014
なお，前述の通り，除算により得た実数値は切り捨てにより整数値に丸めるものとする。
【００４１】
このように，モード番号３の予測の場合，補正値は参照画素ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［５，−１］，ｐ［６，−１］，ｐ［７，−１］の下位２ビットにより定まる。補正値に関しては，予め計算した結果をテーブルに格納しておき，下限値算出時には，このテーブルを参照し，演算量の増加を防ぐ。他のモードについても同様に，予測誤差Ｅ（ｍ）4x4 （ｍ＝３，... ，８）の下限値は次式として与えられる。
【００４２】
Ｔ4x4 −Ｓ（ｍ）4x4 −Ｒ（ｍ）4x4 
Ｓ（ｍ）4x4 を参照画素の加重和，Ｒ（ｍ）4x4 を丸め誤差の補正値，Ｔ4x4 を被予測画素の画素値和と呼ぶ。なお，Ｓ（ｍ）4x4 およびＲ（ｍ）4x4 （ｍ＝３，... ，８）の詳細については，［付録Ａ］として本説明の最後に示す。
【００４３】
１−３．補正値のルックアップテーブルの設計法
以下，補正値のルックアップテーブルの設計法の例について説明する。
【００４４】
１−３−１．ルックアップテーブルの設計法（その１）
いずれのモードの補正値も，参照画素ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［５，−１］，ｐ［６，−１］，ｐ［７，−１］，ｐ［８，−１］，ｐ［−１，１］，ｐ［−１，２］，ｐ［−１，３］，ｐ［−１，４］の下位２ビットにより定まる。そこで，この１３個の参照画素の下位２ビットのとり得る全ての組み合わせに対して，各モード毎の補正値をルックアップテーブルに格納する。このとき，各モードの補正値は０から１６までの値をとるため，５ビット必要となり，ルックアップテーブルのサイズは次のようになる。
【００４５】
５×４13＝３３５．５４４３２［Ｍｂｉｔｓ］
１−３−２．ルックアップテーブルの設計法（その２）
各モード毎に補正値をルックアップテーブルに格納する。ここでは，予測モード３を例にとり説明する。予測モード３の場合，補正値は参照画素ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［５，−１］，ｐ［６，−１］，ｐ［７，−１］の下位２ビットにより定まる。そこで，この８個の参照画素の下位２ビットのとり得る全ての組み合わせ（４8 通り）に対して，各々の補正値をルックアップテーブルに格納する。
【００４６】
画素値ｘの下位ｎビットをＵ（ｘ，ｎ）とし，例として，（Ｕ（ｐ［０，−１］，２），（Ｕ（ｐ［１，−１］，２），（Ｕ（ｐ［２，−１］，２），（Ｕ（ｐ［３，−１］，２），（Ｕ（ｐ［４，−１］，２），（Ｕ（ｐ［５，−１］，２），（Ｕ（ｐ［６，−１］，２），（Ｕ（ｐ［７，−１］，２））＝（００2 ，００2 ，００2 ，００2 ，００2 ，００2 ，００2 ，００2 ）の場合を考える。なお，００2 は２桁の二進数で表した０である。このとき，式（１３）より，補正値はＲ（３）4x4 ＝０となり，ルックアップテーブルには，引数（００2 ，００2 ，００2 ，００2 ，００2 ，００2 ，００2 ，００2 ）に対応する値として０が格納される。本モードの補正値は０から１６までの値をとるため，ルックアップテーブルのサイズは
５×４8 ＝０．３２７６８［Ｍｂｉｔｓ］
となる。他のモードの場合も同様に考えれば，全モードのルックアップテーブルのサイズは次式となる。なお，次式の第ｉ（ｉ＝１，２，... ，６）項は予測番号ｉ＋２の予測モードの補正値の格納に必要なテーブルサイズである。
【００４７】
５×４8 ＋５×４7 ＋５×４8 ＋（３×４6 ＋３×２3 ）
＋５×４7 ＋（３×４4 ＋３×２4 ）＝０．８３３０９６［Ｍｂｉｔｓ］
１−３−３．ルックアップテーブルの設計法（その３）
図５は，イントラ予測における被予測画素のグルーピングの例を示す。また，図６は，各モードにおいて各グループ（クラス）毎に被予測画像を分類した結果を示す。
【００４８】
図５に示すように，参照画素を位置に応じて３つのクラスに分類し，各クラス毎に補正値を格納するルックアップテーブルを作成する。各モードにおいてクラス毎の被予測画素を分類した結果を図６に示す。各クラスにおける被予測画素数の内訳を図７に示す。
【００４９】
例えば，モード３では，クラス２の参照画素を用いて６画素の予測を行う（ここでは，クラス２に含まれる６個の参照画素のうち５画素が利用される）。そこで，この６個の参照画素の下位２ビットのとり得る全ての組み合わせ（４6 通り）に対して，各々の補正値をルックアップテーブルに格納する。具体的な補正値の算出は，式（１３）において，クラス２の参照画素に関する項のみ和をとるものとする。この補正値は０から６までの値をとるため，ルックアップテーブルのサイズは次のようになる。
【００５０】
３×４6 ＝０．０１２２８８［Ｍｂｉｔｓ］
一方，クラス３の場合ルックアップテーブルのサイズは次のようになる。
【００５１】
４×４5 ＝０．００４０９６［Ｍｂｉｔｓ］
従って，モード３のルックアップテーブルのサイズは
３×４6 ＋４×４5 ＝０．０１６３８４［Ｍｂｉｔｓ］
となる。なお，クラス毎に個別のルックアップテーブルを参照しているため，補正値の算出には，テーブル参照に加えて，各クラスの参照値の加算が必要である。他のモードの場合も同様に考えれば，全モードのルックアップテーブルのサイズは次のようになる。
【００５２】
（３＋４＋４＋５）×４6 ＋（３＋４＋４＋３＋２）×４6 
＋（４＋３）×４5 ＝０．１３８２４０［Ｍｂｉｔｓ］
２．ブロックサイズが１６×１６の場合の実施の形態
ＭＢのサイズは全て１６×１６として説明する。コスト関数値の計算法については，まず，予測において丸め誤差が発生しない垂直方向予測および水平方向予測の場合を説明する。次に，これら以外の場合を説明する。
【００５３】
２−１．丸め誤差が発生しない場合
モード番号０の予測（垂直方向予測）およびモード番号１の予測（水平方向予測）のコスト算出は，以下のように行う。
【００５４】
ＭＢサイズが４×４の場合と同様に，まずは，この２つのモードに対するコスト算出に先立ち，モード番号２の予測（ＤＣ予測）に対する予測誤差を求める。同予測誤差をＥ（２）16x16 とする。このＥ（２）16x16 をレジスタεに格納する。このとき，予測値ｑ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］（ｘ＝０，１，... ，１５；ｙ＝０，１，... ，１５）は参照画素が参照可能（参照画素は“available for Intra ＿16x16prediction ”となっている）か否かに応じて，次式のようになる。
【００５５】
(ｉ) Ｐ［ｘ0 ＋ｘ，ｙ0 −１］，Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が，ともに参照可能な場合：
【００５６】
【数１３】
2006279374.tif 000015
(ii)Ｐ［ｘ0 ＋ｘ，ｙ0 −１］は参照可能であり，Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が参照可能でない場合：
【００５７】
【数１４】
2006279374.tif 000016
(iii) Ｐ［ｘ0 −１，ｙ0 ＋ｙ］が参照可能であり，Ｐ［ｘ0 ＋ｘ，ｙ0 −１］は参照可能でない場合：
【００５８】
【数１５】
2006279374.tif 000017
(iv)Ｐ［ｘ0 ＋ｘ，ｙ0 −１］，Ｐ［ｘ0 −１，ｙ0 ＋ｙ］がともに参照可能でない場合：
ｑ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］＝１２８                                  （１７）
ｑ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］の算出過程で求めた次の値を，メモリまたはレジスタに格納しておく。
【００５９】
【数１６】
2006279374.tif 000018
また，次の値も計算し，格納しておく。
【００６０】
【数１７】
2006279374.tif 000019
なお，以下では，記述の簡単化のため，次のように略記する。
【００６１】
ｐ［ｘ，ｙ］≡Ｐ［ｘ0 ＋ｘ，ｙ0 ＋ｙ］
次に，Ｐ［ｘ，−１］（ｘ＝０，１，２，... ，１５）が参照可能であれば，モード番号０の予測（垂直予測）を行う。
【００６２】
図８は，ブロックサイズが１６×１６の場合の垂直予測モードを示している。図８（ａ）に示すように，垂直予測モードでは，符号化対象ブロックに隣接する上の１６画素を垂直方向に下ろして参照画素とする。被予測画素と参照画素とが図８（ｂ），（ｃ）に示す関係にあることから，予測誤差Ｅ（０）16x16 は次の下限値を持つ。
【００６３】
【数１８】
2006279374.tif 000020
このとき次式を満たせば，垂直予測は予測誤差を最小化できないと判断できるため，予測誤差の算出は行うことなく，次の処理に移る。
【００６４】
【数１９】
2006279374.tif 000021
上式を満たさないときのみ，垂直予測に対する予測誤差Ｅ（０）16x16 を求める。
Ｅ（０）16x16 ＜εであれば，レジスタεの値をＥ（０）16x16 で上書きして置き換える。
【００６５】
次に，Ｐ［−１，ｙ］（ｙ＝０，１，２，... ，１５）が参照可能であれば，モード番号１の予測（水平予測）を行う。
【００６６】
図９は，ブロックサイズが１６×１６の場合の水平予測モードを示している。図９（ａ）に示すように，水平予測モードでは，符号化対象ブロックに隣接する左の１６画素を水平方向にのばして参照画素とする。被予測画素と参照画素とが図９（ｂ），（ｃ）に示す関係にあることから，予測誤差Ｅ（１）16x16 は次の下限値を持つ。
【００６７】
【数２０】
2006279374.tif 000022
このとき次式を満たせば，水平予測は予測誤差を最小化できないと判断できるため，予測誤差の算出は行うことなく，次の処理に移る。
【００６８】
【数２１】
2006279374.tif 000023
上式を満たさないときのみ，水平予測に対する予測誤差Ｅ（１）16x16 を求める。Ｅ（１）16x16 ＜εであれば，レジスクεの値をＥ（１）16x16 で上書きして置き換える。
【００６９】
２−２．丸め誤差が発生する場合
モード番号３の場合の予測誤差の下限値を算出する場合，四捨五入演算により発生する丸め誤差を考慮する必要がある。前述の垂直方向予測および水平方向予測モードの場合との違いは，この丸め誤差に対する補正値の算出が必要となる点である。なお，以下では，除算により得た実数値は切り捨てにより整数値に丸めるものとする。
【００７０】
ｐ［ｘ，−１］，ｐ［−１，ｙ］（ｘ＝−１，... ，１５），（ｙ＝０，... ，１５）がともに参照可能な場合に限り，モード番号３の予測が可能であり，このとき，予測誤差Ｅ（３）16x16 は，次のような下限値を持つ。
【００７１】
【数２２】
2006279374.tif 000024
ここで，
【００７２】
【数２３】
2006279374.tif 000025
であり，Ｓ（３）16x16 ，Ｒ（３）16x16 については，以下のようにおいた。
【００７３】
【数２４】
2006279374.tif 000026
Ｒ（３）16x16 の値は，ａ，ｂ，ｃの下位５ビットにより定まる。そこで，この３つの値の下位５ビットのとり得る全ての組み合わせに対して，各モード毎の補正値をルックアップテーブルに格納する。このとき，各モードの補正値は０から２５６までの値をとるため，ルックアップテーブルのサイズは次のようになる。
【００７４】
９×（２5 ）3 ＝０．２９４９１２［Ｍｂｉｔｓ］
【実施例１】
【００７５】
図１０は，本発明の実施例の処理フローチャートである。以下に説明する実施例では，丸め誤差をルックアップテーブルに格納する際，参照画素のクラスタリング結果に応じて，個別のルックアップテーブルに格納するものとする。上述した他のルックアップテーブルの設計法を利用しても，同様に本発明を実施することができる。
【００７６】
まずは，イントラ予測のブロックサイズが４×４の正方形領域の場合について示す。まず，ステップＳ１では，被予測画素，参照画素，第一算出予測モードを入力とし，第一算出予測モードとして指定された予測モードｍ0 に対して，予測誤差Ｅ（ｍ0 ）4x4 を出力する。例えば，ｍ0 ＝２の場合には，式（２）〜（５）に従う処理を行い，予測誤差Ｅ（２）4x4 を出力する。この場合，後続のモード０，１の算出において，式（９）およひ式（１０）で示したように，モード２における計算結果
【００７７】
【数２５】
2006279374.tif 000027
を再利用できる。
【００７８】
次に，被予測画素を入力とし，被予測画素値和Ｔ4x4 を出力する。より具体的には，式（８）により被予測画素値和Ｔ4x4 を算出する（ステップＳ２）。
【００７９】
予測モード番号ｍ（ｍ＝０，１，... ，８，ｍ≠ｍ0 ），参照画素を入力とし，予測モードに対する参照画素値和Ｓ（ｍ）4x4 を算出する処理を行う（ステップＳ３）。より具体的には，付録Ａ（後記）に示す式により算出する。
【００８０】
予測モード番号ｍ（ｍ＝０，１，... ，８，ｍ≠ｍ0 ），参照画素を入力とし，予測モードの丸め誤差に対する補正値Ｒ（ｍ）4x4 をルックアップテーブルから読み込む処理を行う。なお，同テーブルには，予め付録Ａに示す式に従い算出した値を格納しておく。なお，丸め誤差の発生しないモード０，１については，補正値を０として格納しておく（ステップＳ４）。
【００８１】
被予測画素値和Ｔ4x4 ，参照画素値和Ｓ（ｍ）4x4 ，丸め誤差に対する補正値Ｒ（ｍ）4x4 を入力とし，予測モードの予測誤差の下限値を算出する処理を行う。より具体的には，次式により下限値Ｌ（ｍ）を求める（ステップＳ５）。
【００８２】
Ｔ4x4 −Ｓ（ｍ）4x4 −Ｒ（ｍ）4x4 
ステップＳ５で求めた下限値Ｌ（ｍ），予測誤差の最小値として格納された値εを入力とし，Ｌ（ｍ）とεとの大小比較を行い，
Ｌ（ｍ）＜ε
であれば真値を出力し，そうでなければ偽値を出力する（ステップＳ６）。
【００８３】
出力が真値の場合，被予測画素，参照画素を入力とし，予測モードｍに対する予測誤差Ｅ（ｍ）4x4 を算出する処理を行い，Ｅ（ｍ）4x4 を出力する（ステップＳ７）。続いて，予測モードｍに対する予測誤差Ｅ（ｍ）4x4 ，予測誤差の最小値として格納された値εを入力とし，両値の大小比較を行う処理を行い，
Ｅ（ｍ）4x4 ＜ε
であれば真値を出力し，そうでなければ偽値を出力する（ステップＳ８）。
【００８４】
この出力も真値の場合，予測モードｍ，同モードに対する予測誤差Ｅ（ｍ）4x4 を入力とし，ｍを現時点での最適予測モード，Ｅ（ｍ）4x4 を予測誤差の最小値として，各々，レジスタＭ，εに代入する処理を行う（ステップＳ９）。
【００８５】
予測モードｍを更新しながら（ステップＳ１１），全モードについて上述の処理を繰り返し，全ての予測モードに対する処理が終了したならば（ステップＳ１０），最終的に，全モードの中で予測誤差を最小化する予測モードとして，レジスタＭに格納された値を出力する（ステップＳ１０）。
【００８６】
イントラ予測のブロックサイズが１６×１６の正方形領域の場合には，４×４の正方形領域の場合を示した上述の処理において，モード番号をｍ＝０，１，２，３，第一算出予測モードをｍ0 ′とし，Ｅ（ｍ）4x4 ，Ｓ（ｍ）4x4 ，Ｒ（ｍ）4x4 ，Ｔ4x4 を，各々，Ｅ（ｍ）16x16 ，Ｓ（ｍ）16x16 ，Ｒ（ｍ）16x16 ，Ｔ16x16 として，同様の処理を行う。
【００８７】
図１１に本発明の実施例の装置構成図を示す。予測モードを決定した後の符号化処理の部分は従来技術と同様でよいため，予測モードを決定する部分の構成だけを示している。図１１において，スイッチＳＷ１は，予測モードが第一予測モードの場合，第一予測モード予測誤差決定部１０１および被予測画素値和決定部１０２の処理を行い，それ以外の場合，参照画素値和決定部１０４の処理を行うように制御を切り換える。
【００８８】
第一予測モード予測誤差決定部１０１は，符号化対象ブロックの画素，参照画素，第一予測モードに対応する予測モードを入力とし，予測誤差を算出する処理を行い，同予測誤差を暫定最小予測誤差記憶部１１２に出力し，同予測モードを暫定最適予測モード記憶部１１３に出力する。
【００８９】
被予測画素値和決定部１０２は，符号化対象ブロックの画素を入力とし，同ブロック内の被予測画素値和を算出する処理を行い，この被予測画素値和を被予測画素値和記憶部１０３に出力する。なお，被予測画素値和Ｔ4x4 ，Ｔ16x16 は，各々，式（８），式（２０）により算出する。
【００９０】
参照画素値和決定部１０４は，参照画素，予測モードを入力とし，参照画素値和を算出する処理を行い，この参照画素値和を参照画素値和記憶部１０５に出力する。なお，参照画素値和Ｓ（ｍ）4x4 ，Ｓ（ｍ）16x16 の算出は，各々，付録Ａ，付録Ｂ（後記）に従う。
【００９１】
予測誤差下限値決定部１０６は，予測モードを入力とし，被予測画素値和記憶部１０３，参照画素値和記憶部１０５，補正値記憶部１０７から，各々，被予測画素値和，参照画素値和，補正値を読み込み，予測誤差の下限値を算出する処理を行い，同下限値を下限値記憶部１０８に出力する。具体的な算出は，各ブロックサイズの各モード毎に，
Ｔ4x4 −Ｓ（ｍ）4x4 −Ｒ（ｍ）4x4 （ｍ＝０，１，... ，８，ｍ≠ｍ0 ），
Ｔ16x16 −Ｓ（ｍ）16x16 −Ｒ（ｍ）16x16 （ｍ＝０，１，２，３，ｍ≠ｍ0 ′），
により行う。なお，補正値Ｒ（ｍ）4x4 ，Ｒ（ｍ）16x16 は，補正値記憶部１０７に予め格納しておくものとする。
【００９２】
枝刈り判定部１０９は，下限値記憶部１０８および暫定最小予測誤差記憶部１１２から，各々，予測誤差の下限値，およびこれまでに格納された予測誤差の最小値を読み込み，２つの値の大小比較を行い，同下限値の方が小さい場合に，次の処理へ進む（ＳＷ２）。それ以外の場合には，現在のモードに対する処理を終了する。
【００９３】
予測誤差算出部１１０は，符号化対象ブロックの画素，参照画素，予測モードを入力とし，予測誤差を算出する処理を行い，同予測誤差を出力する。
【００９４】
また，最適予測モード判定部１１１は，予測誤差算出部１１０で算出された予測誤差を入力とし暫定最小予測誤差記憶部１１２からこれまでに格納された予測誤差の最小値を読み込み，２つの値の大小比較を行い，予測誤差算出部１１０で算出された予測誤差の方が小さい場合，同予測誤差を暫定最小予測誤差記憶部１１２に記憶し，同予測モードを暫定最適予測モード記憶部１１３に記憶する。
【００９５】
予測モード制御部１１４は，以上の処理を全てのモードに対して繰り返し，最終的に暫定最適予測モード記憶部１１３に記憶された値を最適な予測モードとして出力する。
【００９６】
以上のイントラ予測モードを決定する処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【００９７】
［付録Ａ］
ブロックサイズ４×４の場合の各モードの補正項について示す。各モードの対する参照画素値和および補正値は，以下の通りである。
〔１〕モード番号０の場合：
Ｓ（０）4x4 ＝４（ｐ［０，−１］＋ｐ［１，−１］
＋ｐ［２，−１］＋ｐ［３，−１］）        （２９）
Ｒ（０）4x4 ＝０                                                  （３０）
〔２〕モード番号１の場合：
Ｓ（１）4x4 ＝４（ｐ［−１，０］＋ｐ［−１，１］
＋ｐ［−１，２］＋ｐ［−１，３］）        （３１）
Ｒ（１）4x4 ＝０                                                  （３２）
〔３〕モード番号２の場合：
【００９８】
【数２６】
2006279374.tif 000028
〔４〕モード番号３の場合：
【００９９】
【数２７】
2006279374.tif 000029
なお，Ｒ（３）4x4 は，式（１３）に同じ。また，前述の通り，モード番号３の予測の場合，補正項は参照画素ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［５，−１］，ｐ［６，−１］，ｐ［７，−１］の下位２ビットにより定まる。
〔５〕モード番号４の場合：
【０１００】
【数２８】
2006279374.tif 000030
補正項Ｒ（４）4x4 は，参照画素ｐ［−１，−１］，ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［−１，１］，ｐ［−１，２］，ｐ［−１，３］の下位２ビットにより定まる。
〔６〕モード番号５の場合：
【０１０１】
【数２９】
2006279374.tif 000031
以下では，ｚvr＝２ｘ−ｙとする。
【０１０２】
【数３０】
2006279374.tif 000032
補正項Ｒ（５）4x4 は，参照画素ｐ［−１，−１］，ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［−１，１］，ｐ［−１，２］，ｐ［−１，３］の下位２ビットにより定まる。
〔７〕モード番号６の場合：
【０１０３】
【数３１】
2006279374.tif 000033
以下では，ｚhd＝２ｙ−ｘとする。
【０１０４】
【数３２】
2006279374.tif 000034
補正項Ｒ（６）4x4 は，参照画素ｐ［−１，−１］，ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［−１，１］の下位２ビットおよびｐ［−１，２］，ｐ［−１，３］，ｐ［−１，４］の下位１ビットにより定まる。
〔８〕モード番号７の場合：
【０１０５】
【数３３】
2006279374.tif 000035
補正項Ｒ（７）4x4 は参照画素ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］，ｐ［４，−１］，ｐ［５，−１］，ｐ［６，−１］，ｐ［７，−１］の下位２ビットにより定まる。
〔９〕モード番号８の場合：
【０１０６】
【数３４】
2006279374.tif 000036
以下では，ｚhu＝２ｙ＋ｘとする。
【０１０７】
【数３５】
2006279374.tif 000037
補正項Ｒ（７）4x4 は，参照画素ｐ［０，−１］，ｐ［１，−１］，ｐ［２，−１］，ｐ［３，−１］の下位１ビットおよびｐ［−１，１］，ｐ［−１，２］，ｐ［−１，３］，ｐ［−１，４］の下位２ビットにより定まる。
【０１０８】
［付録Ｂ］
ブロックサイズ１６×１６の場合の各モードの補正項は，以下の通りである。
〔１〕モード番号０の場合：
【０１０９】
【数３６】
2006279374.tif 000038
〔２〕モード番号１の場合：
【０１１０】
【数３７】
2006279374.tif 000039
〔３〕モード番号２の場合：
【０１１１】
【数３８】
2006279374.tif 000040
〔４〕モード番号３の場合：
【０１１２】
【数３９】
2006279374.tif 000041
ここで，ａ，ｂ，ｃは，以下のようにおいた。
【０１１３】
【数４０】
2006279374.tif 000042
【図面の簡単な説明】
【０１１４】
【図１】ブロックサイズが４×４の場合の垂直予測モードを示す図である。
【図２】ブロックサイズが４×４の場合の水平予測モードを示す図である。
【図３】４×４ブロックの予測モードとモード番号の関係を示す図である。
【図４】補正値の計算例を示す図である。
【図５】イントラ予測における被予測画素のグルーピングの例を示す図である。
【図６】各モードにおける各クラス毎の被予測画像の分類結果を示す図である。
【図７】各クラスにおける被予測画素数の内訳を示す図である。
【図８】ブロックサイズが１６×１６の場合の垂直予測モードを示す図である。
【図９】ブロックサイズが１６×１６の場合の水平予測モードを示す図である。
【図１０】本発明の実施例の処理フローチャートである。
【図１１】本発明の実施例の装置構成図である。
【符号の説明】
【０１１５】
１０１  第一予測モード予測誤差決定部
１０２  被予測画素値和決定部
１０３  被予測画素値和記憶部
１０４  参照画素値和決定部
１０５  参照画素値和記憶部
１０６  予測誤差下限値決定部
１０７  補正値記憶部
１０８  下限値記憶部
１０９  枝刈り判定部
１１０  予測誤差算出部
１１１  最適予測モード判定部
１１２  暫定最小予測誤差記憶部
１１３  暫定最適予測モード記憶部
１１４  予測モード制御部
【図１】
2006279374.tif 000043
【図２】
2006279374.tif 000044
【図３】
2006279374.tif 000045
【図４】
2006279374.tif 000046
【図５】
2006279374.tif 000047
【図６】
2006279374.tif 000048
【図７】
2006279374.tif 000049
【図８】
2006279374.tif 000050
【図９】
2006279374.tif 000051
【図１０】
2006279374.tif 000052
【図１１】
2006279374.tif 000053