(57)【要約】【課題】符号量歪みＤと符号量Ｒとを算出して符号化シンタックスを決定する符号化において，複数回の段階で符号化を行う際の計算量の増加を抑えることを可能とする。【解決手段】λの候補選出部１１は，段階が増すごとにラグランジュ乗数λの最大値と最小値の差が小さくなるようにＬ個のラグランジュ乗数λi,j,k （ｉは１からＬ，ｊはブロック番号，ｋは段階の番号）の候補を選出する。各λに対するシンタックス選出部１２−ｉは，Ｌ個のλi,j,k に対し，それぞれＤ＋λi,j,k Ｒを最小化する符号化シンタックスを選出する。λの評価部１３は，各λi,j,k を評価し，１からＮまでのｋ段階を繰り返す制御を行う。符号化ストリーム出力部１４は，第Ｎ段階目の最終的なλi,j,N からＤ＋λi,j,N Ｒを最小にする符号化シンタックスを，ｊ＝１からＭまでのＭ個の符号化対象ブロックについて符号化ストリームとして出力する。【選択図】図１
2005348308.tif 000002
【特許請求の範囲】
【請求項１】
符号量歪みＤと符号量Ｒとを算出して，ラグランジュ乗数λをもとにＤ＋λＲを最小にする符号化シンタックスを決定する符号化装置による動画像符号化方法において，
Ｌ，Ｍ，Ｎを２以上の整数，ｉを１からＬまでの整数，ｊを１からＭまでの整数，ｋを１からＮまでの整数として，
第ｋの段階では，
第ｊのブロックに対して，第１の段階から第（ｋ−１）の段階までの間に保持された符号化情報を用いてＬ個のラグランジュ乗数λi,j,k （ただし，ｋ＝１の場合には初期値として与えられたＬ個のラグランジュ乗数λi,j,1 ）を選出するステップと，
第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスを，ｉ＝１，２，３，…，Ｌのそれぞれに対して選出するステップとを，ｊが１からＭになるまで繰り返し，
第ｋの段階における符号化情報を保持し，ｋに１を加算して次の段階に移行する処理をｋが１からＮになるまで繰り返し，
第Ｎの段階では，
第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λ1,j,N Ｒ，Ｄ＋λ2,j,N Ｒ，Ｄ＋λ3,j,N Ｒ，…，Ｄ＋λL,j,N Ｒのいずれかを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力するステップを，ｊが１からＭになるまで繰り返す
ことを特徴とする動画像符号化方法。
【請求項２】
請求項１記載の動画像符号化方法において，
第１のブロックから第Ｍのブロックまでの全体の目標符号量をＲtargetとし，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊが１からＭまでのＲi,j,k の和をＲi,sum,k としたとき，Ｒi,sum,k とＲtargetとの差の絶対値がある値より小さくなり，かつｊ＝１，２，３，…，Ｍとしたときのλi,j,k がある範囲内に収まっているときのｉをｉ0 ，ｋをＮとして，
第Ｎの段階では，
第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λi0,j,NＲを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力するステップを，ｊが１からＭになるまで繰り返す
ことを特徴とする動画像符号化方法。
【請求項３】
請求項１または請求項２記載の動画像符号化方法において，
前記ラグランジュ乗数は，全てのｉとｋについてλi,1,k ＝λi,2,k ＝λi,3,k ＝，…，＝λi,M,k が成立するように定められたものであり，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊが１からＭまでのＲi,j,k の和をＲi,sum,k としたとき，全てのｉについてのλi,1,k と，全てのｉについてのＲi,sum,k とを，第ｋの段階における符号化情報として保持する
ことを特徴とする動画像符号化方法。
【請求項４】
請求項２または請求項３記載の動画像符号化方法において，
第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊが１からＭまでのＲi,j,k の和をＲi,sum,k としたとき，前記Ｌ個のラグランジュ乗数λi,j,k を選出するステップでは，
λ1,j,k ＜λ2,j,k ＜λ3,j,k ＜……＜λL,j,k が全てのｊ，ｋについて成立し，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最大値はＲtargetより大きく，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最小値はＲtargetより小さくなるようにラグランジュ乗数λi,j,k を定めるとともに，
第２の段階以降の第ｋの段階において，第（ｋ−１）の段階までに保持されているＲi,sum,k-1 とＲtargetの値から，λ1,1,k-1 ≦λ1,1,k かつλL,1,k ≦λL,1,k-1 かつλL,1,k −λ1,1,k ＜λL,1,k-1 −λ1,1,k-1 が成り立つようにλi,1,k （ｉ＝１，２，３，…，Ｌ）を定める
ことを特徴とする動画像符号化方法。
【請求項５】
請求項３記載の動画像符号化方法において，
前記Ｌは３であり，第ｋの段階においては，λ1,j,k ＜λ2,j,k ＜λ3,j,k かつＲ1,sum,k ＞Ｒtarget＞Ｒ3,sum,k となるように３個のラグランジュ乗数λ1,j,k ，λ2,j,k ，λ3,j,k を選出し，
第２の段階以降の第ｋの段階において，Ｒ2,sum,k-1 ＜Ｒtargetの場合にはλ1,1,k ＝λ1,1,k-1 かつλ2,1,k ＝（λ1,1,k-1 ＋λ2,1,k-1 ）／２かつλ3,1,k ＝λ2,1,k-1 とし，Ｒ2,sum,k-1 ＞Ｒtargetの場合にはλ1,1,k ＝λ2,1,k-1 かつλ2,1,k ＝（λ2,1,k-1 ＋λ3,1,k-1 ）／２かつλ3,1,k ＝λ3,1,k-1 とし，
Ｒ2,sum,k とＲtargetの差の絶対値がある値より小さくなった時のｋをＮとして，前記第Ｎの段階により符号化ストリームを出力する
ことを特徴とする動画像符号化方法。
【請求項６】
請求項１記載の動画像符号化方法において，
Ｐを１以上の整数，ｐを１からＰまでの整数としたとき，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスをｉ＝１，２，３，…，Ｌのそれぞれに対して選出し，
第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k としたとき，ｉ＝１，２，３，…，Ｌについてのλi,j,k とＲi,j,k との関係から，第ｊのブロックにおける符号量Ｒのλ依存性を表すＰ個のパラメータＣj,k,1 ，Ｃj,k,2 ，Ｃj,k,3 ，…，Ｃj,k,P を算出し，
全てのｊ，ｐについてのＣj,k,p を符号化情報として保持する
ことを特徴とする動画像符号化方法。
【請求項７】
請求項６記載の動画像符号化方法において，
前記Ｐは１であり，ｉ＝１，２，３，…，Ｌについてのλi,j,k とＲi,j,k の関係から，第ｊのブロックにおける符号量Ｒのλ依存性として，Ｒ＝Ｃj,k,1 ／（λ1/2 ）としたときのＣj,k,1 を算出し，
ｊが１からＭまでのＣj,k,1 の和をＣsum,k,1 としたとき，第ｋの段階において，λ1,j,k ，λ2,j,k ，λ3,j,k ，…，λL,j,k のいずれかが（Ｃsum,k-1,1 ／Ｒtarget）2 と等しくなるようにλi,j,k を選出する
ことを特徴とする動画像符号化方法。
【請求項８】
請求項１記載の動画像符号化方法において，
ｉ’を１からＬまでの整数，ｋ’を１からｋまでの整数として，λi,j,k+1 ＝λi',j,k' となるｉ’，ｋ’が存在し，かつ，「第ｋの段階で第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,j,k+1 Ｒを最小にする符号化シンタックスを選出するステップ」と「第ｋ’の段階で第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi',j,k' Ｒを最小にする符号化シンタックスを選出するステップ」とが同一であると予測できる場合に，前者の過程を省略して後者の過程の結果を用いる
ことを特徴とする動画像符号化方法。
【請求項９】
請求項１記載の動画像符号化方法において，
前記Ｌ，Ｍがｋについて可変である
ことを特徴とする動画像符号化方法。
【請求項１０】
各第ｋの段階毎に，請求項３記載の動画像符号化方法か請求項６記載の動画像符号化方法かのいずれかの方法を選択する
ことを特徴とする動画像符号化方法。
【請求項１１】
符号量歪みＤと符号量Ｒとを算出して，ラグランジュ乗数λをもとにＤ＋λＲを最小にする符号化シンタックスを決定する動画像符号化装置において，
符号化対象の画像を入力する画像入力手段と，
Ｌ，Ｍ，Ｎを２以上の整数，ｉを１からＬまでの整数，ｊを１からＭまでの整数，ｋを１からＮまでの整数として，
ｋが１から（Ｎ−１）までの各第ｋの段階において，第ｊのブロックに対して，第１の段階から第（ｋ−１）の段階までの間に保持された符号化情報を用いてＬ個のラグランジュ乗数λi,j,k （ただし，ｋ＝１の場合には初期値として与えられたＬ個のラグランジュ乗数λi,j,1 ）を選出するラグランジュ乗数の候補選出手段と，
選出されたラグランジュ乗数λi,j,k （ｉ＝１，２，３，…，Ｌ）のそれぞれに対して，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスを選出するシンタックス選出手段と，
前記シンタックス選出手段による第ｋの段階における符号化情報を保持し，前記ラグランジュ乗数の候補選出手段と前記ラグランジュ乗数に対するシンタックス選択手段による処理を，ｋが１からＮになるまで繰り返す制御を行う評価手段と，
第Ｎの段階において前記第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λ1,j,N Ｒ，Ｄ＋λ2,j,N Ｒ，Ｄ＋λ3,j,N Ｒ，…，Ｄ＋λL,j,N Ｒのいずれかを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力する符号化ストリーム出力手段とを備える
ことを特徴とする動画像符号化装置。
【請求項１２】
請求項１ないし請求項１０のいずれか１項に記載の動画像符号化方法を，コンピュータに実行させるための動画像符号化プログラム。
【請求項１３】
請求項１ないし請求項１０のいずれか１項に記載の動画像符号化方法を，コンピュータに実行させるための動画像符号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，動画像符号化技術に関し，特に，動画像を与えられた符号量でＨ．２６４またはＭＰＥＧ−４，ＭＰＥＧ−２などの規格に基づき効率的に符号化するために，符号化を複数回の段階に分けて，いずれの段階においてもそれ以前の段階における符号化情報を用いて，より高い符号化効率を達成する動画像符号化技術に関するものである。
【背景技術】
【０００２】
例えば，下記の非特許文献１に記載されたＭＰＥＧ−２映像符号化方式に基づき，効率的に符号化するために，符号化を複数回の段階に分けて行う方法の一つに，第１の段階においては，全ての画像領域で同一の量子化パラメータ値を用いて符号化し，発生符号量から各領域の複雑さを予測し，第２の段階以降においては，各領域において，複雑さに基づく量子化パラメータ値を決定し，符号化の効率を高めるという方法がある。
【０００３】
符号量歪みＤと符号量Ｒを算出して符号化シンタックスを決定するＨ．２６４映像符号化方式においては，符号化を複数回の段階に分けて行って符号化効率を高める方法は提案されていない。なお，符号化シンタックスとは，符号化の文字（“１”または“０”）がどのように配列されているかという符号化の構文を意味する。
【非特許文献１】MPEG-2 International Standard ISO/IEC 13818-2 1995.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ラグランジュ未定乗数法の観点からは，ラグランジュ乗数λをなるべく定数に保ったまま符号量歪みＤと符号量Ｒを算出してＤ＋λＲを最小にするような符号化シンタックスを選択していくのが最も効率の高い符号化方法である。
【０００５】
ところが１回の段階の符号化だけでは，目標符号量に近い符号量を与える符号化ができたとしても，ラグランジュ乗数λが一定に近いことは保証されていない。また，目標符号量に近い符号量を与え，かつラグランジュ乗数λを一定に近い値に保つために，複数の段階で符号化を行う場合には，多くの符号化の段階が必要になることから，符号化に必要な計算量が膨大になるという問題がある。
【０００６】
本発明は，上記従来技術の問題点を解決し，複数回の段階で符号化を行う際の，符号化に必要な計算量の増加を抑える動画像符号化を実現することを目的とする。
【課題を解決するための手段】
【０００７】
上記問題点を解決するために，本発明は，各符号化の段階において，複数のラグランジュ乗数λに対してＤ＋λＲを最小化する符号化シンタックスを選択することを特徴とする。これにより，符号量Ｒのλ依存性を算出し，目標符号量に近い符号量を与えるλの値をなるべく少ない段階で決定することができる。
【０００８】
また，本発明は，目標符号量より大きい符号量と小さい符号量を与える少なくとも２通り以上のλを選出し，段階が増すごとにλの最大値と最小値の差を小さくすることを特徴とする。これにより，Ｒのλ依存性をモデル化することなく，目標符号量に近い符号量を与えるλの値を決定することができる。
【０００９】
複数のラグランジュ乗数λに対してＤ＋λＲを最小化する符号化シンタックスを選択する過程においては，各候補となる符号化シンタックスに対して，複数のλに対するＤ＋λＲを連続して計算することができ，かつ，その符号化シンタックスが，あるλについて，Ｄ＋λＲを最小化するかだけを確かめればよいので，計算量の増加はそれほど大きくない。
【００１０】
すなわち，第１の本発明は，符号量歪みＤと符号量Ｒを算出して符号化シンタックスを決定する動画像符号化方法において，Ｌ，Ｍ，Ｎを２以上の整数，ｉを１からＬまでの整数，ｊを１からＭまでの整数，ｋを１から（Ｎ−１）までの整数として，第ｋの段階においては，第ｊのブロックに対してＬ個のラグランジュ乗数λ1,j,k ，λ2,j,k ，λ3,j,k ，…，λL,j,k を選出し，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスをｉ＝１，２，３，…，Ｌのそれぞれに対して選出し，同様にして第（ｊ＋１）のブロックを処理することをｊが１からＭになるまで繰り返し，第ｋの段階における符号化情報を保持し，第（ｋ＋１）の段階では，第１の段階から第ｋの段階までの間に保持された符号化情報を用いてλi,j,k+1 を決定し，第Ｎの段階では，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λ1,j,N Ｒ，Ｄ＋λ2,j,N Ｒ，Ｄ＋λ3,j,N Ｒ，…，Ｄ＋λL,j,N Ｒのいずれかを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力することをｊが１からＭになるまで繰り返すことを特徴とする。
【００１１】
また，第２の本発明は，第１の本発明において，第１のブロックから第Ｍのブロックまでの全体の目標符号量をＲtargetとし，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊが１からＭまでのＲi,j,k の和をＲi,sum,k としたとき，Ｒi,sum,k とＲtargetとの差の絶対値がある値より小さくなり，かつｊ＝１，２，３，…，Ｍとしたときのλi,j,k がある範囲内に収まっているときのｉ，ｋをそれぞれｉ0 ，Ｎとして，第Ｎの段階では，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λi0,j,NＲを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力することをｊが１からＭになるまで繰り返すことを特徴とする。
【００１２】
また，第３の本発明は，第１の本発明において，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊが１からＭまでのＲi,j,k の和をＲi,sum,k としたとき，λi,1,k ＝λi,2,k ＝λi,3,k ＝，…，＝λi,M,k が全てのｉとｋについて成立するようにラグランジュ乗数を定め，全てのｉについてのλi,1,k と，全てのｉについてのＲi,sum,k を，第ｋの段階において符号化情報として保持することを特徴とする。
【００１３】
また，第４の本発明は，第１の本発明において，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊが１からＭまでのＲi,j,k の和をＲi,sum,k としたとき，λ1,j,k ＜λ2,j,k ＜λ3,j,k ＜……＜λL,j,k が全てのｋについて成立し，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最大値はＲtargetより大きく，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最小値はＲtargetより小さくなるようにラグランジュ乗数を定め，第ｋの段階までに保持されているＲi,sum,k とＲtargetの値から，λ1,j,k ≦λ1,j,k+1 かつλL,j,k+1 ≦λL,j,k かつλL,j,k+1 −λ1,j,k+1 ＜λL,j,k −λ1,j,k が成り立つようにλi,j,k+1 （ｉ＝１，２，３，…，Ｌかつｊ＝１，２，３，…，Ｍ）を定めることを特徴とする。
【００１４】
また，第５の本発明は，第３の本発明において，Ｌ＝３とし，Ｒ2,sum,k ＜Ｒtargetの場合にはλ1,1,k+1 ＝λ1,1,k かつλ2,1,k+1 ＝（λ1,1,k ＋λ2,1,k ）／２かつλ3,1,k+1 ＝λ2,1,k とし，Ｒ2,sum,k ＞Ｒtargetの場合にはλ1,1,k+1 ＝λ2,1,k かつλ2,1,k+1 ＝（λ2,1,k ＋λ3,1,k ）／２かつλ3,1,k+1 ＝λ3,1,k とし，Ｒ2,sum,k とＲtargetの差の絶対値がある値より小さくなった時のｋをＮとして符号化ストリームを出力することを特徴とする。
【００１５】
また，第６の本発明は，第１の本発明において，Ｐを１以上の整数，ｐを１からＰまでの整数としたとき，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスをｉ＝１，２，３，…，Ｌのそれぞれに対して選出し，ｉ＝１，２，３，…，Ｌについてのλi,j,k とＲi,j,k （ただし，Ｒi,j,k は第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量）の関係から，第ｊのブロックにおけるＲのλ依存性を表すＰ個のパラメータＣj,k,1 ，Ｃj,k,2 ，Ｃj,k,3 ，…，Ｃj,k,P を算出し，全てのｊ，ｐについてのＣj,k,p を符号化情報として保持することを特徴とする。
【００１６】
また，第７の本発明は，第６の本発明において，Ｐ＝１とし，ｉ＝１，２，３，…，Ｌについてのλi,j,k とＲi,j,k の関係から，第ｊのブロックにおけるＲのλ依存性として，Ｒ＝Ｃj,k,1 ／（λ1/2 ）としたときのＣj,k,1 を算出し，ｊが１からＭまでのＣj,k,1 の和をＣsum,k,1 としたとき，第（ｋ＋１）の段階において，λ1,j,k+1 ，λ2,j,k+1 ，λ3,j,k+1 ，…，λL,j,k+1 のいずれかが（Ｃsum,k,1 ／Ｒtarget）2 と等しくなるようにλi,j,k+1 を選出することを特徴とする。
【００１７】
また，第８の本発明は，第１の本発明において，ｉ’を１からＬまでの整数，ｋ’を１からｋまでの整数として，λi,j,k+1 ＝λi',j,k' となるｉ’，ｋ’が存在し，かつ，「第ｋの段階で第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,j,k+1 Ｒを最小にする符号化シンタックスを選出する過程」と「第ｋ’の段階で第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi',j,k' Ｒを最小にする符号化シンタックスを選出する過程」とが同一であると予測できる場合に，前者の過程を省略して後者の過程の結果を用いることを特徴とする。
【００１８】
また，第９の本発明は，第１の本発明において，Ｌ，Ｍがｋについて可変であることを特徴とする。
【００１９】
また，第１０の本発明は，各第ｋの段階毎に，第３の本発明の方法か第６の本発明の方法かのいずれかの方法を選択することを特徴とする。
【００２０】
図１は，本発明の動画像符号化装置の構成例を示す図である。動画像符号化装置１は，画像入力部１０，ラグランジュ乗数λの候補選出部１１，各ラグランジュ乗数λi,j,k に対するシンタックス選出部１２−ｉ（ｉ＝１，２，…，Ｌ），ラグランジュ乗数λの評価部１３，符号化ストリーム出力部１４からなる。
【００２１】
画像入力部１０は，符号化対象の画像信号を入力する。λの候補選出部１１は，各符号化対象ブロック（ｊ）ごとに，例えば目標符号量より大きい符号量と小さい符号量を与える少なくとも２通り以上のラグランジュ乗数λの候補を選出する。ここでは，段階（ｋ）が増すごとにラグランジュ乗数λの最大値と最小値の差が小さくなるようにラグランジュ乗数λの選出を行う。
【００２２】
各ラグランジュ乗数λi,j,k に対するシンタックス選出部１２−ｉは，Ｌ個のラグランジュ乗数λi,j,k に対し，それぞれＤ＋λi,j,k Ｒを最小化する符号化シンタックスを選出する。ラグランジュ乗数λの評価部１３は，各ラグランジュ乗数λ1,j,k ，λ2,j,k ，…，λL,j,k を評価し，所定の段階数になるまで，または所定の終了条件が満たされるまで，ラグランジュ乗数λの候補選出部１１，各ラグランジュ乗数λi,j,k に対するシンタックス選出部１２−ｉおよびラグランジュ乗数λの評価の処理を繰り返す制御を行う。
【００２３】
符号化ストリーム出力部１４は，第Ｎ段階目の最終的なラグランジュ乗数λi,j,N からＤ＋λi,j,N Ｒを最小にする符号化シンタックスを，ｊ＝１からＭまでのＭ個の符号化対象ブロックについて符号化ストリームとして出力する。
【００２４】
図２は，第１の本発明の符号化処理フローの一例を示す図である。符号量歪みＤと符号量Ｒを算出して符号化シンタックスを決定する動画像符号化処理において，Ｌ，Ｍ，Ｎを２以上の整数，ｉを１からＬまでの整数，ｊを１からＭまでの整数，ｋを１から（Ｎ−１）までの整数とする。
【００２５】
第ｋの段階の第ｊのブロックの処理が開始されると，第（ｋ−１）の段階までに保持された符号化情報をもとに，ｉ＝１，２，３，…，Ｌに対して，ラグランジュ乗数λi,j,k を選出する（ステップＳ１〜Ｓ５）。なお，第１の段階（ｋ＝１）においては，あらかじめ定められたＬ個のラグランジュ乗数λi,j,1 を初期値として与える。
【００２６】
第ｋの段階の第ｊのブロックの処理においては，ｉ＝１，２，３，…，Ｌのそれぞれに対して，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスを選出する（ステップＳ６）。
【００２７】
未処理のブロックがある場合には（ステップＳ７），ｊをインクリメントして（ステップＳ８），ステップＳ４に戻り，処理したブロックが最後のブロックの場合（ｊ＝Ｍの場合）には，第ｋ段階の符号化情報をメモリに記憶し保持する（ステップＳ９）。
【００２８】
未実行の段階がある場合には（ステップＳ１０），ｋをインクリメントして（ステップＳ１１），ステップＳ３に戻り，最後の段階である場合（ｋ＝Ｎの場合）には，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λi,j,N Ｒを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力することをｊ＝１からＭまで繰り返す（ステップＳ１２）。
【発明の効果】
【００２９】
本発明によれば，符号量歪みＤと符号量Ｒを算出して符号化シンタックスを決定する動画像符号化装置で，かつ，符号化を複数回の段階に分けて，いずれの段階においてもそれ以前の段階における符号化情報を用いて高い符号化効率を達成する動画像符号化装置において，計算量の微小な増加で，より高効率な動画像の映像符号化を行うことができる。
【発明を実施するための最良の形態】
【００３０】
〔第１の実施の形態〕
図３は，本発明の第１の実施の形態における符号化処理フローの一例である。第１の実施の形態は，第１〜第５の本発明，第８の本発明を同時に採用した場合に対応する。
【００３１】
第１の実施の形態では，符号量歪みＤと符号量Ｒを算出して符号化シンタックスを決定する動画像符号化処理において，Ｍ，Ｎを２以上の整数，ｉを１から３までの整数，ｊを１からＭまでの整数，ｋを１から（Ｎ−１）までの整数として，λi,1,k ＝λi,2,k ＝λi,3,k ＝，…，＝λi,M,k が全てのｉとｋについて成立するようにラグランジュ乗数を定める。
【００３２】
また，第１のブロックから第Ｍのブロックまでの全体の目標符号量をＲtargetとし，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,1,k を最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊ＝１からＭまでのＲi,j,k の和をＲi,sum,k とすると，λ1,1,k ＜λ2,1,k ＜λ3,1,k が全てのｋについて成立し，かつｉ＝１，２，３としたときのＲi,sum,k の最大値はＲtargetより大きく，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最小値はＲtargetより小さくなるようにラグランジュ乗数を定める。
【００３３】
第ｋの段階が開始されると，第（ｋ−１）の段階までに保持された符号化情報（Ｒ2,sum,k-1 ）とＲtargetの大小関係に応じて，ｉ＝１，２，３に対してλi,1,k を選出する（ステップＳ２１〜Ｓ２４）。ステップＳ２４の処理については，後に第（ｋ＋１）の段階を例にとって詳述する。なお，第１の段階においては，前の段階までに保持された符号化情報は存在しないので，λ1,1,1 ＜λ2,1,1 ＜λ3,1,1 かつＲ1,sum,1 ＞Ｒtarget＞Ｒ3,sum,1 となるように，初期値として定めた３個のラグランジュ乗数λ1,1,1 ，λ2,1,1 ，λ3,1,1 を選出する。
【００３４】
第ｊのブロックに対して第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,1,k Ｒを最小にする符号化シンタックスをｉ＝１，２，３のそれぞれに対して選出し（ステップＳ２６），同様にして第（ｊ＋１）のブロックを処理することをｊが１からＭになるまで繰り返し（ステップＳ２７，Ｓ２８），符号化情報としてＲ2,sum,k を保持する（ステップＳ２９）。
【００３５】
第（ｋ＋１）の段階では，上記ステップＳ２４において，Ｒ2,sum,k ＜Ｒtargetの場合にはλ1,1,k+1 ＝λ1,1,k かつλ2,1,k+1 ＝（λ1,1,k ＋λ2,1,k ）／２かつλ3,1,k+1 ＝λ2,1,k とし，Ｒ2,sum,k ＞Ｒtargetの場合にはλ1,1,k+1 ＝λ2,1,k かつλ2,1,k+1 ＝（λ2,1,k ＋λ3,1,k ）／２かつλ3,1,k+1 ＝λ3,1,k とする。
【００３６】
Ｒ2,sum,k とＲtargetの差の絶対値がある値より小さいかを判断し（ステップＳ３０），Ｒ2,sum,k とＲtargetの差の絶対値がある値より小さくない場合にはｋをインクリメントして（ステップＳ３１），次の段階の処理を行う。ｋが大きくなるにつれて，Ｒ2,sum,k とＲtargetの差の絶対値は小さくなるので，Ｒ2,sum,k とＲtargetの差の絶対値がある値より小さくなったときのｋをＮとして，最後の段階である第Ｎの段階では，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λ2,j,N Ｒを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力することをｊ＝１からＭまで繰り返す（ステップＳ３２）。
【００３７】
なお，上記の過程で，λ1,1,k+1 とλ3,1,k+1 の値は，λ1,1,k またはλ2,1,k またはλ3,1,k に等しいので，第（ｋ＋１）の段階では，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,1,k Ｒを最小にする符号化シンタックスをｉ＝１，２，３のそれぞれに対して選出する必要はなく，ｉ＝２についてのみ選出すれば十分である。
【００３８】
上記第１の実施の形態では，第１の本発明におけるＬを３とし，Ｒ2,sum,k ＜Ｒtargetの場合にはλ1,1,k+1 ＝λ1,1,k かつλ2,1,k+1 ＝（λ1,1,k ＋λ2,1,k ）／２かつλ3,1,k+1 ＝λ2,1,k とし，Ｒ2,sum,k ＞Ｒtargetの場合にはλ1,1,k+1 ＝λ2,1,k かつλ2,1,k+1 ＝（λ2,1,k ＋λ3,1,k ）／２かつλ3,1,k+1 ＝λ3,1,k とする例を述べたが，必ずしもこの式に限定されず，またＬも３に限定されず，λ1,1,k ≦λ1,1,k+1 かつλL,1,k+1 ≦λL,1,k かつλL,1,k+1 −λ1,1,k+1 ＜λL,1,k −λ1,1,k が成り立つような別の式を用いても良いことは言うまでもない。
【００３９】
第１の実施の形態では，λ1,1,k ＜λ2,1,k ＜λ3,1,k ＜，…，＜λL,1,k が全てのｋについて成立し，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最大値はＲtargetより大きく，かつｉ＝１，２，３，…，ＬとしたときのＲi,sum,k の最小値はＲtargetより小さくなるようにラグランジュ乗数を定める第４の本発明を用いた例を述べたが，必ずしもλi,1,k の大小関係がこの式に従う必要はなく，Ｒi,sum,k とＲtargetの差の絶対値がある値より小さくなり，かつｊ＝１，２，３，…，Ｍとしたときのλi,j,k がある範囲内に収まるような他の方法を用いても良いことは言うまでもない。
【００４０】
〔第２の実施の形態〕
第２の実施の形態は，第１の本発明，第２の本発明，第６の本発明，第７の本発明を同時に採用した場合に対応する。第２の実施の形態における符号化処理フローを図４に示す。
【００４１】
符号量歪みＤと符号量Ｒを算出して符号化シンタックスを決定する動画像符号化装置において，Ｌ，Ｍ，Ｎを２以上の整数，ｉを１からＬまでの整数，ｊを１からＭまでの整数，ｋを１から（Ｎ−１）までの整数，第１のブロックから第Ｍのブロックまでの全体の目標符号量をＲtargetとし，第ｋの段階において，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスにおける符号量をＲi,j,k ，ｊ＝１からＭまでのＲi,j,k の和をＲi,sum,k とする。
【００４２】
第ｋの段階においては，第（ｋ−１）の段階までに保持された符号化情報をもとに，第ｊのブロックに対してＬ個のラグランジュ乗数λ1,j,k ，λ2,j,k ，λ3,j,k ，…，λL,j,k を選出する（ステップＳ４１〜Ｓ４５）。ステップＳ４５の処理については，後に第（ｋ＋１）の段階を例にとって詳述する。なお，ステップＳ４５において，ｋ＝１の場合には初期値λi,j,1 を与える。
【００４３】
第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，第ｊのブロックにおけるＤ＋λi,j,k Ｒを最小にする符号化シンタックスをｉ＝１，２，３，…，Ｌのそれぞれに対して選出する（ステップＳ４６）。
【００４４】
次にｉ＝１，２，３，…，Ｌについてのλi,j,k とＲi,j,k の関係から，第ｊのブロックにおけるＲのλ依存性として，Ｒ＝Ｃj,k,1 ／（λ1/2 ）としたときのＣj,k,1 を最小２乗法などの方法から算出する（ステップＳ４７）。
【００４５】
同様にして第（ｊ＋１）のブロックを処理することをｊが１からＭになるまで繰り返し（ステップＳ４９），ｊ＝１からＭまでのＣj,k,1 の和をＣsum,k,1 とし，符号化情報としてＣsum,k,1 を保持する（ステップＳ５０）。
【００４６】
第ｋの段階が最後の段階であるかを判断し（ステップＳ５１），最後の段階でなければ，第（ｋ＋１）の段階の処理を行う（ステップＳ５２）。最後の段階かどうかの判断は，Ｒi,sum,k とＲtargetの差の絶対値がある値より小さくなり，かつｊ＝１，２，３，…，Ｍとしたときのλi,j,k がある範囲内に収まっているかどうかにより行う。
【００４７】
第（ｋ＋１）の段階では，上記ステップＳ４５において，λ1,j,k+1 ，λ2,j,k+1 ，λ3,j,k+1 ，…，λL,j,k+1 のいずれかが（Ｃsum,k,1 ／Ｒtarget）2 と等しくなるようにλi,j,k+1 を選出することにより，Ｒtargetに近い符号量を与えるラグランジュ乗数の収束を早める。
【００４８】
Ｒi,sum,k とＲtargetの差の絶対値がある値より小さくなり，かつｊ＝１，２，３，…，Ｍとしたときのλi,j,k がある範囲内に収まっているときのｉ，ｋをそれぞれｉ0 ，Ｎとして，最後の段階である第Ｎの段階では，第ｊのブロックを符号化するための候補となる符号化シンタックスの中から，Ｄ＋λi0,j,NＲを最小にする符号化シンタックスを，第ｊのブロックに対する符号化ストリームとして出力することをｊ＝１からＭまで繰り返す（ステップＳ５３）。
【００４９】
第２の実施の形態では，第ｊのブロックにおけるＲのλ依存性として，Ｒ＝Ｃj,k,1 ／（λ1/2 ）としたときのＣj,k,1 を算出する例を述べたが，必ずしもこの式に限定されず，Ｒのλ依存性として別の式を用いても良いことは言うまでもない。どのような式を用いるかは，実験などによって得られた情報をもとに定めることができる。
【００５０】
第２の実施の形態では，第ｊのブロックにおけるＲのλ依存性として，パラメータ数Ｐが１である場合の例を述べたが，必ずしもＰ＝１に限定されず，複数のパラメータを含むＲのλ依存性の式を用いても良いことは言うまでもない。
【００５１】
〔第３の実施の形態〕
本発明の第３の実施の形態は，第１の本発明，第９の本発明，第１０の本発明を同時に採用した場合に対応する。第１の段階から第Ｎ’の段階においては第６の本発明の方法を用いてλi,j,k を算出するが，モデルが当てはまらない画像などｋを大きくしてもＲi,sum,k とＲtargetの差の絶対値がある値より小さくならない場合には，第（Ｎ’＋１）段階以降においては，第３の本発明の方法を用いてＲi,sum,k とＲtargetの差の絶対値を確実に小さくする。
【００５２】
第１〜第３の実施の形態として，本発明のいくつかを組み合わせた代表的な方法を説明したが，以上の説明から第１ないし第１０の本発明の他の組み合わせについても容易に実施できることは明らかである。
【００５３】
以上の動画像符号化の処理は，ハードウェアやファームウェアによって実現することができるだけでなく，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【００５４】
【図１】動画像符号化装置の構成例を示す図である。
【図２】符号化処理フローの例を示す図である。
【図３】符号化処理フローの例を示す図である。
【図４】符号化処理フローの例を示す図である。
【符号の説明】
【００５５】
１  動画像符号化装置
１０  画像入力部
１１  λの候補選出部
１２−ｉ  λi,j,k に対するシンタックス選出部（ｉ＝１，２，…，Ｌ）
１３  λの評価部
１４  符号化ストリーム出力部
【図１】
2005348308.tif 000003
【図２】
2005348308.tif 000004
【図３】
2005348308.tif 000005
【図４】
2005348308.tif 000006