(57)【要約】【課題】画像符号化においてＮ個のフレームの画像情報うちＭ個のフレームの符号化順序を決定する際の演算負荷を軽減する。【解決手段】Ｎ個の各フレーム内の画像情報から算出した発生符号量を評価するための評価値と，各フレーム間の差分画像情報から算出した発生符号量を評価するための評価値とを記憶しておく。フレーム追加初期設定部１６が設定した（Ｍ−１）個のフレームの符号化順序に，さらに他の１フレームを追加し，暫定符号化順序設定部１９がフレーム追加後のＭ個のフレームの暫定符号化順序を設定する。フレームを追加した位置に応じてそれぞれ評価合計初期設定部２０と評価合計加算部２１が各暫定符号化順序の評価合計値を計算し，対象フレーム順序決定部２２が評価合計値Ｓが最小となる暫定符号化順序をＭ個のフレームの符号化順序とする。【選択図】図１
2005080179.tif 000002
【特許請求の範囲】
【請求項１】
複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化装置における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定装置であって，
前記Ｎ個の各フレームについてフレーム内の画像情報を用いて発生符号量を評価するための第１の評価値を算出する手段と，
前記Ｎ個のフレームから２フレームを選択する全組み合わせについて各フレーム間の差分画像情報を用いて発生符号量を評価するための第２の評価値を算出する手段と，
前記第１および第２の評価値を記憶する手段と，
前記第１および第２の評価値に基づいて前記Ｎ個のフレームのうち（Ｍ−１）個のフレームを選択しその符号化順序を設定する手段と，
前記符号化順序が設定された（Ｍ−１）個のフレームの列に，前記Ｎ個のフレームのうちの他の１フレームを追加したＭ個のフレームの暫定符号化順序を設定する手段と，
前記１フレームを追加した位置ごとの各暫定符号化順序の先頭フレームから最終フレームまでの各フレームについて前記第１の評価値および前記第２の評価値から最小となるように選ばれた評価値を合計して評価合計値を算出する手段と，
前記算出された評価合計値が最も小さい値になるときの前記Ｍ個のフレームの暫定符号化順序を，求めるＭ個のフレームの符号化順序として決定する手段とを備える
ことを特徴とする画像符号化順序決定装置。
【請求項２】
複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化装置における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定装置であって，
フレーム番号ｉ（ｉ＝１，２，…，Ｎ）のフレームの画像情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｉ）を計算するフレーム内評価値計算手段と，
前記Ｎ個のフレームからフレーム番号ｉ（ｉ＝１，２，…，Ｎ）とフレーム番号ｊ（ｊ＝１，２，…，Ｎ；ただしｊ≠ｉ）の２フレームを選択する全組み合わせについて，フレーム番号ｊのフレームの画像情報の，フレーム番号ｉのフレームの画像情報からの差分情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｊ）を計算するフレーム間評価値計算手段と，
前記フレーム内評価値計算手段および前記フレーム間評価値計算手段によって計算された評価値を記憶する評価値記憶手段と，
前記Ｎ個のフレームのうち（Ｍ−１）個のフレームについてフレームの符号化順序を示す符号化順序フレーム番号Ｆの値Ｆ（ｉ）（ｉ＝１，２，…，Ｍ−１）を設定するフレーム追加初期設定手段と，
符号化対象として追加するフレームのフレーム番号の値ｋを前記符号化順序フレーム番号Ｆの値以外の１からＮまでの値に設定する対象フレーム設定手段と，
フレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか；ただし１≦ｃ≦Ｍ−１）の符号化順序に設定する対象フレーム順序設定手段と，
符号化順序フレーム番号Ｆに設定された符号化順序に対して，前記対象フレーム順序設定手段で設定したフレーム番号ｋのフレームを加えた暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を設定する暫定符号化順序設定手段と，
評価値Ｅ（Ｔ（１），Ｔ（１））を，評価合計値Ｓに設定する評価合計初期設定手段と，
前記暫定符号化順序で設定されたフレーム番号の順序でＴ（ｊ）のｊを２からＭまで順次変更し，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））（ｉは１からｊ−１までのいずれか）を，評価合計値Ｓに繰り返し加算する評価合計加算手段と，
前記対象フレーム順序設定手段，前記暫定符号化順序設定手段，前記評価合計初期設定手段および前記評価合計加算手段により，前記値ｂを前記値ｃからＭまで順次変更して算出した評価合計値Ｓの中で評価合計値Ｓが最も小さい値となる値ｂによる暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を，求めるＭ個のフレームの符号化順序として決定する対象フレーム順序決定手段とを備える
ことを特徴とする画像符号化順序決定装置。
【請求項３】
複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化方法における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定方法であって，
前記Ｎ個の各フレームについてフレーム内の画像情報を用いて発生符号量を評価するための第１の評価値を算出するステップと，
前記Ｎ個のフレームから２フレームを選択する全組み合わせについて各フレーム間の差分画像情報を用いて発生符号量を評価するための第２の評価値を算出するステップと，
前記第１および第２の評価値を記憶するステップと，
前記第１および第２の評価値に基づいて前記Ｎ個のフレームのうち（Ｍ−１）個のフレームを選択しその符号化順序を設定するステップと，
前記符号化順序が設定された（Ｍ−１）個のフレームの列に，前記Ｎ個のフレームのうちの他の１フレームを追加したＭ個のフレームの暫定符号化順序を設定するステップと，
前記１フレームを追加した位置ごとの各暫定符号化順序の先頭フレームから最終フレームまでの各フレームについて前記第１の評価値および前記第２の評価値から最小となるように選ばれた評価値を合計して評価合計値を算出するステップと，
前記算出された評価合計値が最も小さい値になるときの前記Ｍ個のフレームの暫定符号化順序を，求めるＭ個のフレームの符号化順序として決定するステップとを有する
ことを特徴とする画像符号化順序決定方法。
【請求項４】
複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化方法における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定方法であって，
フレーム番号ｉ（ｉ＝１，２，…，Ｎ）のフレームの画像情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｉ）を計算し，評価値記憶手段に記憶するフレーム内評価値計算ステップと，
前記Ｎ個のフレームからフレーム番号ｉ（ｉ＝１，２，…，Ｎ）とフレーム番号ｊ（ｊ＝１，２，…，Ｎ；ただしｊ≠ｉ）の２フレームを選択する全組み合わせについて，フレーム番号ｊのフレームの画像情報の，フレーム番号ｉのフレームの画像情報からの差分情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｊ）を計算し，評価値記憶手段に記憶するフレーム間評価値計算ステップと，
前記Ｎ個のフレームのうち（Ｍ−１）個のフレームについてフレームの符号化順序を示す符号化順序フレーム番号Ｆの値Ｆ（ｉ）（ｉ＝１，２，…，Ｍ−１）を設定するフレーム追加初期設定ステップと，
符号化対象として追加するフレームのフレーム番号の値ｋを前記符号化順序フレーム番号Ｆの値以外の１からＮまでの値に設定する対象フレーム設定ステップと，
フレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか；ただし１≦ｃ≦Ｍ−１）の符号化順序に設定する対象フレーム順序設定ステップと，
符号化順序フレーム番号Ｆに設定された符号化順序に対して，前記対象フレーム順序設定ステップで設定したフレーム番号ｋのフレームを加えた暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を設定する暫定符号化順序設定ステップと，
評価値Ｅ（Ｔ（１），Ｔ（１））を，評価合計値Ｓに設定する評価合計初期設定ステップと，
前記暫定符号化順序で設定されたフレーム番号の順序でＴ（ｊ）のｊを２からＭまで順次変更し，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））（ｉは１からｊ−１までのいずれか）を，評価合計値Ｓに繰り返し加算する評価合計加算ステップと，
前記対象フレーム順序設定ステップ，前記暫定符号化順序設定ステップ，前記評価合計初期設定ステップおよび前記評価合計加算ステップにより，前記値ｂを前記値ｃからＭまで順次変更して算出した評価合計値Ｓの中で評価合計値Ｓが最も小さい値となる値ｂによる暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を，求めるＭ個のフレームの符号化順序として決定する対象フレーム順序決定ステップとを有する
ことを特徴とする画像符号化順序決定方法。
【請求項５】
請求項４に記載の画像符号化順序決定方法において，
前記評価合計加算ステップでは，
フレーム番号Ｔ（ｊ）について，値ｉを１からｊ−１までのいずれかの値に変更して，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））が最小となる値を探索し，最小となる評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を，評価合計値Ｓに加算するフレーム評価合計加算ステップを，ｊを２からＭまで順次変更して繰り返し実行する
ことを特徴とする画像符号化順序決定方法。
【請求項６】
請求項５に記載の画像符号化順序決定方法において，
前記フレーム評価合計加算ステップでは，
参照可能フレーム番号ＲとしてＬ個の値Ｒ（ｄ）（ｄ＝１，２，…，Ｌ）を設定する参照可能フレーム番号設定ステップを実行し，
前記Ｔ（ｉ）が前記設定された参照可能フレーム番号Ｒに含まれる値のいずれかに等しい場合のみ，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を探索候補とする
ことを特徴とする画像符号化順序決定方法。
【請求項７】
請求項４に記載の画像符号化順序決定方法において，
前記フレーム追加初期設定ステップでは，
第ｉフレームについて，前記フレーム間評価値計算ステップで計算された評価値Ｅ（ｉ，ｊ）（ｊ≠ｉ）の，評価値がｐ番目に小さい場合のｊの値ｊp （ｉ）を，ｐが１からＭ−２まで求めるフレーム近傍評価探索ステップと，
第ｉフレームについて，評価値Ｅ（ｉ，ｉ）と評価値Ｅ（ｉ，ｊp （ｉ））のｐが１からＭ−１までの全ての値とを合計して，評価合計値ＥＳ（ｉ）を求めるフレーム近傍評価加算ステップとを，１からＮまでの全てのｉについて実行し，
評価合計値ＥＳ（ｉ）（１≦ｉ≦Ｎ）が最も小さい時のｉの値ｍを求め，前記符号化順序フレーム番号Ｆとしてｍとｊp （ｍ）（ｐ＝１，２，…，Ｍ−２）とを設定する
ことを特徴とする画像符号化順序決定方法。
【請求項８】
請求項４に記載の画像符号化順序決定方法において，
前記フレーム内評価値計算ステップでは，
第ｉフレームの画像情報をフレーム内符号化するフレーム内符号化ステップと，
前記フレーム内符号化ステップで作成した符号化データから復号画像を作成する復号画像作成ステップと，
第ｉフレームの画像情報と前記作成された復号画像との間の差分情報を計算する差分計算ステップと，
前記差分計算ステップで計算した差分情報を用いて前記評価値Ｅ（ｉ，ｉ）を計算するステップとを実行する
ことを特徴とする画像符号化順序決定方法。
【請求項９】
請求項４に記載の画像符号化順序決定方法において，
前記フレーム間評価値計算ステップでは，
第ｊフレームの画像情報の，第ｉフレームの画像情報からの差分情報を符号化する差分符号化ステップと，
前記符号化した差分情報を復号し，第ｉフレームの画像情報に加算して復号画像を作成する復号画像作成ステップと，
第ｊフレームの画像情報と前記作成された復号画像との間の差分情報を計算する差分計算ステップと，
前記差分計算ステップで計算した差分情報を用いて前記評価値Ｅ（ｉ，ｊ）を計算するステップとを実行する
ことを特徴とする画像符号化順序決定方法。
【請求項１０】
請求項３から請求項９までのいずれか１項に記載の画像符号化順序決定方法をコンピュータに実行させるための画像符号化順序決定プログラム。
【請求項１１】
請求項３から請求項９までのいずれか１項に記載の画像符号化順序決定方法をコンピュータに実行させるための画像符号化順序決定プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，複数の画像をフレーム間予測符号化を用いて符号化する画像符号化において，符号化順序を決定するときの演算負荷を軽減することを可能にした画像符号化順序決定装置，画像符号化順序決定方法，画像符号化順序決定プログラムおよびそのプログラムを記録した記録媒体に関するものである。
【背景技術】
【０００２】
動画像のような複数の画像を符号化する場合に，画像間の相関が高い場合には画像をフレームとみなしてフレーム間予測符号化を適用すると，高い符号化効率を実現することができる。国際標準動画像符号化方式Ｈ．２６４（非特許文献１参照）では，フレームの符号化モードに，フレーム間の相関を使わずに符号化するＩフレームと，過去に符号化した１フレームから予測するＰフレームと，過去に符号化した２フレームから予測することができるＢフレームを定義している。
【０００３】
参照画像メモリに複数フレーム分の復号画像を蓄積しておき，ＰフレームとＢフレームは，そのメモリから参照画像を選択して予測することができる。この参照画像の選択は，マクロブロック単位に行うことができる。また，Ｂフレームで過去の２フレームから予測する方法を両方向予測と呼び，各フレームの画像情報を重み付け平均して予測画像を作成する。
【０００４】
ここで，フレームの符号化順序（復号順序）と入力順序（出力順序）は異なっていてもよく，例えば入力動画像における時間が過去のフレームから予測してもよいし，未来のフレームから予測してもよい。
【非特許文献１】ITU-T Rec.H.264/ISO/IEC 11496-10, "Advanced Video Coding", Final Committee Draft, Document JVT-E022, September 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
複数の画像をフレーム間予測符号化を用いて符号化するときに，それら複数の画像の符号化効率は画像の符号化順序に依存する。フレーム間予測符号化では，参照画像メモリに蓄積されている参照画像との差分を符号化対象にするため，符号化時に蓄積されている参照画像と符号化対象画像との相関が大きいほど，予測効率が向上し，符号化効率を向上できる。
【０００６】
符号化順序を決定する方法としては，全てのパターンの符号化順序で一度符号化し，最も符号量が少ない順序を求める方法が考えられる。しかしながら，この方法では，符号化順序のパターン数は画像数の順列となるため，符号化対象の画像の数が多くなると，必要な演算量が急激に増加する問題がある。
【０００７】
例えば，符号化順序は画像数が３の場合には（１×２×３）パターンあり，画像数が４の場合には（１×２×３×４）パターンとなる。したがって，画像数が３から４になると符号化時間は４倍に増加する。
【０００８】
あるいは符号量ではなく，フレーム間の相関を示す評価関数を設定しておき，その値の合計が最も小さくなるように符号化順序を決定する方法も考えられる。このとき，評価値が小さいほど符号化した際の符号量が小さくなるような評価関数を設定する。しかしながら，この方法においても，全てのパターンの符号化順序で全フレーム間の評価値の合計を求める必要がある。符号化順序のパターン数は，（画像数−１）の順列となるため，符号化対象の画像の数が多くなると，必要な演算量が急激に増加する問題がある。
【０００９】
本発明は上記問題点を解決し，複数の画像をフレーム間予測符号化を用いて符号化する際に，符号化順序を決定するときの演算負荷を軽減することを目的とする。
【課題を解決するための手段】
【００１０】
以上の課題を解決するため，本発明は，複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化装置における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定装置であって，前記Ｎ個の各フレームについてフレーム内の画像情報を用いて発生符号量を評価するための第１の評価値を算出する手段と，前記Ｎ個のフレームから２フレームを選択する全組み合わせについて各フレーム間の差分画像情報を用いて発生符号量を評価するための第２の評価値を算出する手段と，前記第１および第２の評価値を記憶する手段と，前記第１および第２の評価値に基づいて前記Ｎ個のフレームのうち（Ｍ−１）個のフレームを選択しその符号化順序を設定する手段と，前記符号化順序が設定された（Ｍ−１）個のフレームの列に，前記Ｎ個のフレームのうちの他の１フレームを追加したＭ個のフレームの暫定符号化順序を設定する手段と，前記１フレームを追加した位置ごとの各暫定符号化順序の先頭フレームから最終フレームまでの各フレームについて前記第１の評価値および前記第２の評価値から最小となるように選ばれた評価値を合計して評価合計値を算出する手段と，前記算出された評価合計値が最も小さい値になるときの前記Ｍ個のフレームの暫定符号化順序を，求めるＭ個のフレームの符号化順序として決定する手段とを備えることを特徴とする。
【００１１】
さらに詳しくは，本発明は，複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化装置における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定装置であって，
フレーム番号ｉ（ｉ＝１，２，…，Ｎ）のフレームの画像情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｉ）を計算するフレーム内評価値計算手段と，
前記Ｎ個のフレームからフレーム番号ｉ（ｉ＝１，２，…，Ｎ）とフレーム番号ｊ（ｊ＝１，２，…，Ｎ；ただしｊ≠ｉ）の２フレームを選択する全組み合わせについて，フレーム番号ｊのフレームの画像情報の，フレーム番号ｉのフレームの画像情報からの差分情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｊ）を計算するフレーム間評価値計算手段と，
前記フレーム内評価値計算手段および前記フレーム間評価値計算手段によって計算された評価値を記憶する評価値記憶手段と，
前記Ｎ個のフレームのうち（Ｍ−１）個のフレームについてフレームの符号化順序を示す符号化順序フレーム番号Ｆの値Ｆ（ｉ）（ｉ＝１，２，…，Ｍ−１）を設定するフレーム追加初期設定手段と，
符号化対象として追加するフレームのフレーム番号の値ｋを前記符号化順序フレーム番号Ｆの値以外の１からＮまでの値に設定する対象フレーム設定手段と，
フレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか；ただし１≦ｃ≦Ｍ−１）の符号化順序に設定する対象フレーム順序設定手段と，
符号化順序フレーム番号Ｆに設定された符号化順序に対して，前記対象フレーム順序設定手段で設定したフレーム番号ｋのフレームを加えた暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を設定する暫定符号化順序設定手段と，
評価値Ｅ（Ｔ（１），Ｔ（１））を，評価合計値Ｓに設定する評価合計初期設定手段と，
前記暫定符号化順序で設定されたフレーム番号の順序でＴ（ｊ）のｊを２からＭまで順次変更し，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））（ｉは１からｊ−１までのいずれか）を，評価合計値Ｓに繰り返し加算する評価合計加算手段と，
前記対象フレーム順序設定手段，前記暫定符号化順序設定手段，前記評価合計初期設定手段および前記評価合計加算手段により，前記値ｂを前記値ｃからＭまで順次変更して算出した評価合計値Ｓの中で，評価合計値Ｓが最も小さい値となる値ｂによる暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を，求めるＭ個のフレームの符号化順序として決定する対象フレーム順序決定手段とを備えることを特徴とする。
【００１２】
また，本発明は，複数フレームの画像情報をフレーム間予測符号化を用いて符号化する画像符号化方法における，Ｎ個のフレームの画像情報のうちＭ個のフレームの符号化順序を決定する画像符号化順序決定方法であって，
フレーム番号ｉ（ｉ＝１，２，…，Ｎ）のフレームの画像情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｉ）を計算し，評価値記憶手段に記憶するフレーム内評価値計算ステップと，
前記Ｎ個のフレームからフレーム番号ｉ（ｉ＝１，２，…，Ｎ）とフレーム番号ｊ（ｊ＝１，２，…，Ｎ；ただしｊ≠ｉ）の２フレームを選択する全組み合わせについて，フレーム番号ｊのフレームの画像情報の，フレーム番号ｉのフレームの画像情報からの差分情報を用いて発生符号量を評価するための評価値Ｅ（ｉ，ｊ）を計算し，評価値記憶手段に記憶するフレーム間評価値計算ステップと，
前記Ｎ個のフレームのうち（Ｍ−１）個のフレームについてフレームの符号化順序を示す符号化順序フレーム番号Ｆの値Ｆ（ｉ）（ｉ＝１，２，…，Ｍ−１）を設定するフレーム追加初期設定ステップと，
符号化対象として追加するフレームのフレーム番号の値ｋを前記符号化順序フレーム番号Ｆの値以外の１からＮまでの値に設定する対象フレーム設定ステップと，
フレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか；ただし１≦ｃ≦Ｍ−１）の符号化順序に設定する対象フレーム順序設定ステップと，
符号化順序フレーム番号Ｆに設定された符号化順序に対して，前記対象フレーム順序設定ステップで設定したフレーム番号ｋのフレームを加えた暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を設定する暫定符号化順序設定ステップと，
評価値Ｅ（Ｔ（１），Ｔ（１））を，評価合計値Ｓに設定する評価合計初期設定ステップと，
前記暫定符号化順序で設定されたフレーム番号の順序でＴ（ｊ）のｊを２からＭまで順次変更し，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））（ｉは１からｊ−１までのいずれか）を，評価合計値Ｓに繰り返し加算する評価合計加算ステップと，
前記対象フレーム順序設定ステップ，前記暫定符号化順序設定ステップ，前記評価合計初期設定ステップおよび前記評価合計加算ステップにより，前記値ｂを前記値ｃからＭまで順次変更して算出した評価合計値Ｓの中で，評価合計値Ｓが最も小さい値となる値ｂによる暫定符号化順序Ｔ（ｉ）（ｉ＝１，２，…，Ｍ）を，求めるＭ個のフレームの符号化順序として決定する対象フレーム順序決定ステップとを有することを特徴とする。
【００１３】
本発明による作用は，以下のとおりである。本発明による上記フレーム内評価値計算ステップ，フレーム間評価値計算ステップ，フレーム追加初期設定ステップ，対象フレーム設定ステップ，対象フレーム順序設定ステップ，暫定符号化順序設定ステップ，評価合計初期設定ステップ，評価合計加算ステップ，対象フレーム順序決定ステップを実行することにより，予め符号化順序を設定しておいた（Ｍ−１）フレームに，さらに１フレームを追加するときに，全Ｍフレームの評価値が最も小さくなるように，追加するフレームの符号化順序を決定することができる。
【００１４】
この方法では，フレームを追加する個所を変更するたびに全Ｍフレームの評価値を加算する計算が必要なため，評価値を加算する計算は（Ｍ−ｃ）×（Ｍ−１）回行われる。従来では（Ｍ−１）の順列だけの加算回数が必要であったため，本発明によれば，従来の方法に比べて計算回数を大幅に軽減することができる。
【００１５】
対象フレーム順序設定ステップでの，フレーム番号ｋのフレームの符号化順序設定時の値ｃは１から（Ｍ−１）までの値を設定することができる。値ｃを大きくするほど計算回数を低減できるが，評価する符号化順序の候補が少なくなる。
【００１６】
前記評価合計加算ステップは，フレーム番号Ｔ（ｊ）について，値ｉを１からｊ−１までのいずれかの値に変更して，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））が最小となる値を探索し，最小となる評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を，評価合計値Ｓに加算するフレーム評価合計加算ステップを，ｊを２からＭまで順次変更して繰り返し実行することにより実施することができる。
【００１７】
この前記評価合計加算ステップで，値ｉが１からｊ−１までのいずれかとなる評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））のうち，最小の値となる評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を探索して，評価合計値Ｓに加算することによって，評価合計値Ｓとして最小の値となるように値ｉを決定することができる。
【００１８】
また，評価合計加算ステップで加算する評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））における値ｉの他の決定方法として，例えばＴ（ｉ）がＴ（ｊ）に１を加算または減算した値となるように値ｉを設定するようにしてもよい。
【００１９】
また，前記フレーム評価合計加算ステップは，参照可能フレーム番号ＲとしてＬ個の値Ｒ（ｄ）（ｄ＝１，２，…，Ｌ）を設定する参照可能フレーム番号設定ステップを実行し，前記Ｔ（ｉ）が前記設定された参照可能フレーム番号Ｒに含まれる値のいずれかに等しい場合のみ，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を探索候補とすることにより実施することができる。この方法を用いれば，フレーム評価合計加算ステップで値ｉを変更する範囲を小さくすることができる。したがって演算回数をさらに削減することができる。
【００２０】
また，前記フレーム追加初期設定ステップは，第ｉフレームについて，前記フレーム間評価値計算ステップで計算された評価値Ｅ（ｉ，ｊ）（ｊ≠ｉ）の，評価値が最小の場合のｊの値ｊ１（ｉ）と，評価値が２番目に小さい場合のｊの値ｊ２（ｉ）を求めるフレーム近傍評価探索ステップと，第ｉフレームについて，評価値Ｅ（ｉ，ｉ）と評価値Ｅ（ｉ，ｊ１（ｉ））と評価値Ｅ（ｉ，ｊ２（ｉ））の値を合計して，評価合計値ＥＳ（ｉ）を求めるフレーム近傍評価加算ステップとを１からＮまでの全てのｉについて実行し，評価合計値ＥＳ（ｉ）（１≦ｉ≦Ｎ）が最も小さい時のｉの値ｍを求め，前記符号化順序フレーム番号Ｆとしてｍとｊ１（ｍ）とｊ２（ｍ）とを設定することにより実施することができる。
【００２１】
この方法を用いることにより，フレーム追加初期設定ステップで，３個の符号化順序フレーム番号Ｆを決定する場合に，評価値Ｅ（ｉ，ｉ）と，２つの評価値Ｅ（ｉ，ｊ）（ｊ≠ｉ）の合計が最も小さくなるように値ｉとｊを決定することができる。これにより，評価値を使わずに符号化順序フレーム番号Ｆの初期値を決定する方法よりも，評価合計値Ｓの値を小さくすることができる。
【００２２】
この他に，フレーム追加初期設定ステップで設定する符号化順序フレーム番号Ｆとして，例えば初期値ｉを決めて，その値を中心にして１を加算または減算することを繰り返した値に設定する方法を用いてもよい。例えば５個の値を設定すると，Ｆ＝（ｉ，ｉ−１，ｉ＋１，ｉ−２，ｉ＋２）となる。
【００２３】
また，前記フレーム内評価値計算ステップは，第ｉフレームの画像情報をフレーム内符号化するフレーム内符号化ステップと，前記フレーム内符号化ステップで作成した符号化データから復号画像を作成する復号画像作成ステップと，第ｉフレームの画像情報と前記作成された復号画像との間の差分情報を計算する差分計算ステップと，前記差分計算ステップで計算した差分情報を用いて前記評価値Ｅ（ｉ，ｉ）を計算するステップとを実行することにより実施することができる。
【００２４】
この方法では，一度符号化して復号した画像情報と，原画像との間の差分情報を使って評価値Ｅ（ｉ，ｉ）を計算する。不可逆符号化の場合には，原画像と復号画像が異なり，差分が大きいほど符号化歪が大きい。したがって，差分が小さいほど評価値が小さくなるように評価関数を設定すれば，評価値が小さいＥ（ｉ，ｉ）を探索することにより差分の小さい値ｉを探索できることになる。
【００２５】
差分の大きさの評価方法としては，差分の絶対値和ＳＡＤＲや差分の２乗和ＳＳＤが挙げられる。ＳＡＤＲまたはＳＳＤはそれぞれ下記の式（１）または式（２）で計算される。ｏ（ｉ）（ｘ，ｙ）は画素位置（ｘ，ｙ）におけるフレーム番号ｉの原画像を示し，ｒ（ｉ）（ｘ，ｙ）は画素位置（ｘ，ｙ）における復号画像を示す。
【００２６】
ＳＡＤＲ＝Σx,y ｜ｒ（ｉ）（ｘ，ｙ）−ｏ（ｉ）（ｘ，ｙ）｜    ……式（１）
ＳＳＤ＝Σx,y （ｒ（ｉ）（ｘ，ｙ）−ｏ（ｉ）（ｘ，ｙ））2     ……式（２）
このようなＳＡＤＲやＳＳＤを評価値に設定してもよいし，さらに，予測残差や予測情報についての発生符号量を考慮した評価関数Ｊを評価値に設定してもよい。Ｊは下記の式（３）で計算される。Ｒは発生符号量，λは所定の係数を示す。式（３）のＳＳＤは，ＳＡＤＲにしてもよい。
【００２７】
Ｊ＝ＳＳＤ＋λ×Ｒ      ……式（３）
また，前記フレーム内評価値計算ステップでの評価値Ｅ（ｉ，ｉ）を求める他の方法として，例えばフレーム内画像情報の平均値や分散，または隣接画素間の相関係数などを用いる算出方法を用いることもできる。
【００２８】
前記フレーム間評価値計算ステップは，第ｊフレームの画像情報の，第ｉフレームの画像情報からの差分情報を符号化する差分符号化ステップと，前記符号化した差分情報を復号し，第ｉフレームの画像情報に加算して復号画像を作成する復号画像作成ステップと，第ｊフレームの画像情報と前記作成された復号画像との間の差分情報を計算する差分計算ステップと，前記差分計算ステップで計算した差分情報を用いて前記評価値Ｅ（ｉ，ｊ）を計算するステップとを実行することにより実施することができる。この他に，フレーム間評価値計算ステップでの評価値Ｅ（ｉ，ｊ）を求める方法として，例えばフレーム間画像情報の絶対値の平均値や分散を用いる算出方法などがある。
【００２９】
このフレーム間評価値計算ステップにおいて，例えば評価値Ｅ（ｉ，ｊ）の算出方法として，フレーム番号ｊの画素位置（ｘ，ｙ）に対する，フレーム番号ｉにおいて差分を計算する位置（ｘ０，ｙ０）（ｘ０，ｙ０は実数精度）とすると，評価関数として，２フレーム間の差分の絶対値ＳＡＤＯを用いてもよい。
【００３０】
ＳＡＤＯは，下記の式（４）で計算される。ｏ（ｊ）（ｘ，ｙ）はフレーム番号ｊにおける画素位置（ｘ，ｙ）の画像情報を示し，ｏ（ｉ）（ｘ０，ｙ０）はフレーム番号ｉにおける画素位置（ｘ０，ｙ０）の画像情報を示す。
【００３１】
ＳＡＤＯ＝Σx,y ｜ｏ（ｊ）（ｘ，ｙ）−ｏ（ｉ）（ｘ０，ｙ０）｜  ……式（４）
これらの評価値は画面を分割した領域毎に，例えばマクロブロック毎に算出してもよい。この場合には，評価合計加算ステップで評価合計値Ｓに加算する評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））におけるＴ（ｉ）は，領域毎に異なってもよい。
【００３２】
この方法によれば，フレーム間評価値計算ステップで，一度符号化して復号した画像情報と，原画像との間の差分情報を使って評価値Ｅ（ｉ，ｊ）を計算する。ここでフレーム間の差分が大きいほど符号化歪が大きい。したがって，差分が小さいほど評価値が小さくなるように評価関数を設定すれば，評価値が小さいＥ（ｉ，ｊ）を探索することにより差分の小さい値ｉを探索できることになる。差分の大きさの評価方法としては，上記のＳＡＤＲやＳＳＤやＪを使用することができる。
【発明の効果】
【００３３】
本発明によれば，複数の画像をフレーム間予測符号化を用いて符号化する際の，符号化順序を決定するときに，全ての符号化順序パターンで評価値の合計を求めて符号化順序を決定する方法よりも，評価値の合計を計算する回数を減少することができ，演算負荷を軽減することができる。
【発明を実施するための最良の形態】
【００３４】
本発明の実施の形態を図面を参照して説明する。図１は，本発明の画像符号化順序決定装置の構成の一例を示す図である。１はＮフレームの画像情報のうち，Ｍフレームの符号化順序を決定する画像符号化順序決定装置である。画像符号化順序決定装置１において，１１は原画像が蓄積される原画像蓄積メモリ，１２はフレーム内評価値の計算モードとフレーム間評価値の計算モードとの切替えを行う切替部である。
【００３５】
１３はフレーム番号ｉ（１≦ｉ≦Ｎ）の画像情報を用いて評価値Ｅ（ｉ，ｉ）を計算するフレーム内評価値計算部，１４はフレーム番号ｉのフレームの画像情報について，フレーム番号ｊ（ｊ≠ｉ）の画像情報の，フレーム番号ｉのフレームの画像情報からの差分情報を用いて評価値Ｅ（ｉ，ｊ）を計算するフレーム間評価値計算部，１５は計算された評価値が蓄積される評価値蓄積メモリである。
【００３６】
１６は（Ｍ−１）個のフレームについてフレームの符号化順序を示す符号化順序フレーム番号Ｆの値Ｆ（ｉ）（ｉは１からＭ−１まで）を設定するフレーム追加初期設定部，１７は符号化対象として追加するフレームのフレーム番号の値ｋを前記符号化順序フレーム番号Ｆの値以外の１からＮまでの値に設定する対象フレーム設定部である。
【００３７】
１８はフレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか）の符号化順序に設定する対象フレーム順序設定部，１９は符号化順序フレーム番号Ｆに設定された符号化順序に対して，前記対象フレーム順序設定部１８で符号化順序を設定したフレーム番号ｋのフレームを加えた暫定符号化順序Ｔ（ｉ）（ｉは１からＭまで）を設定する暫定符号化順序設定部である。
【００３８】
また，２０は評価値Ｅ（Ｔ（１），Ｔ（１））を評価合計値Ｓに設定する評価合計初期設定部，２１は暫定符号化順序で設定されたフレーム番号の順序でＴ（ｊ）を変更し，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））（ｉは１からｊ−１までのいずれか）を，ｊが２からＭまでの全てについて，評価合計値Ｓに繰り返し加算する評価合計加算部，２２は前記値ｃからＭまでの全てのｂについて各々暫定符号化順序に対する評価合計加算部２１により得られる評価合計値Ｓの中で値が最も小さい値となる値ｂを探索して，その符号化順序をＭ個のフレームの求める符号化順序として決定する対象フレーム順序決定部である。
【００３９】
図２は，図１に示すフレーム追加初期設定部１６の構成の一例を示す図である。フレーム追加初期設定部１６において，１６１はフレーム近傍評価探索部，１６２はフレーム近傍評価加算部，１６３はフレーム近傍評価蓄積メモリ，１６４はフレーム近傍評価合計探索部である。
【００４０】
例えばＭ＝４の場合，フレーム近傍評価探索部１６１は，第ｉフレームについて，評価値蓄積メモリ１５に蓄積された評価値Ｅ（ｉ，ｊ）（ｊ≠ｉ）の，評価値Ｅ（ｉ，ｊ）が最小の場合のｊの値ｊ１（ｉ）と，評価値Ｅ（ｉ，ｊ）が２番目に小さい場合のｊの値ｊ２（ｉ）を求める処理を１からＮまでの全てのｉについて実行する。
【００４１】
フレーム近傍評価加算部１６２は，第ｉフレームについて，評価値Ｅ（ｉ，ｉ）と評価値Ｅ（ｉ，ｊ１（ｉ））と評価値Ｅ（ｉ，ｊ２（ｉ））の値を合計して，評価合計値ＥＳ（ｉ）を求める処理を１からＮまでの全てのｉについて実行する。すなわち，ＥＳ（ｉ）は，
ＥＳ（ｉ）＝Ｅ（ｉ，ｉ）＋Ｅ（ｉ，ｊ１（ｉ））＋Ｅ（ｉ，ｊ２（ｉ））
（ｉ＝１，２，…，Ｎ）として算出される。
【００４２】
フレーム近傍評価蓄積メモリ１６３には，フレーム近傍評価加算部１６２により求められた評価合計値ＥＳ（ｉ）が蓄積される。フレーム近傍評価合計探索部１６４は，評価合計値ＥＳ（ｉ）（１≦ｉ≦Ｎ）が最も小さいときのｉの値ｍを求め，符号化順序フレーム番号をｍ，ｊ１（ｍ），ｊ２（ｍ）とする。
【００４３】
図３および図４は，本発明の実施の形態の処理概要を説明する図である。図３（Ａ）に示すようなＮ個のフレームの画像情報から符号化効率のよいＭ個（この例ではＭ＝４）のフレームの符号化順序を決定するものとする。フレーム内評価値計算部１３は，図３（Ｂ）のように，各フレームの画像情報を用いて，発生符号量を評価するための評価値Ｅ（１，１），Ｅ（２，２），…，Ｅ（Ｎ，Ｎ）を計算し，結果を評価値蓄積メモリ１５に蓄積する。また，フレーム間評価値計算部１４は，図３（Ｃ）のように，Ｎ個のフレームからフレーム番号ｉ（ｉ＝１，２，…，Ｎ）とフレーム番号ｊ（ｊ＝１，２，…，Ｎ；ただしｊ≠ｉ）の２フレームを選択する全組み合わせについて，評価値Ｅ（ｉ，ｊ）を計算し，結果を評価値蓄積メモリ１５に蓄積する。
【００４４】
フレーム追加初期設定部１６は，図３（Ｄ）のように，Ｎ個のフレームのうち（Ｍ−１）個（この例では３個）のフレームについて，フレームの符号化順序を示す符号化順序フレーム番号Ｆの値Ｆ（１），Ｆ（２），Ｆ（３）を設定する。この符号化順序の設定では，１からＮまでの第ｉフレームについて，評価値Ｅ（ｉ，ｊ）（ｊ≠ｉ）の，評価値が最小の場合のｊの値ｊ１（ｉ）と，評価値Ｅ（ｉ，ｊ）が２番目に小さい場合のｊの値ｊ２（ｉ）を求め，各第ｉフレームについて，
ＥＳ（ｉ）＝Ｅ（ｉ，ｉ）＋Ｅ（ｉ，ｊ１（ｉ））＋Ｅ（ｉ，ｊ２（ｉ））
を計算し，この評価合計値ＥＳ（ｉ）（１≦ｉ≦Ｎ）が最も小さい時のｉの値ｍを求め，Ｆ（１）＝ｍ，Ｆ（２）＝ｊ１（ｍ），Ｆ（３）＝ｊ２（ｍ）とする。
【００４５】
次に，対象フレーム設定部１７は，図３（Ｅ）のように，符号化対象として追加するフレームのフレーム番号ｋを符号化順序フレーム番号Ｆの値Ｆ（ｉ）以外の１からＮまでの値に設定する。対象フレーム順序設定部１８は，フレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか）の符号化順序に設定する。例えば，ｃ＝２の場合，ｂは２，３，４のいずれかとなる。
【００４６】
暫定符号化順序設定部１９は，図４（Ａ）のように，符号化順序フレーム番号Ｆに設定された符号化順序Ｆ（１），Ｆ（２），Ｆ（３）に対して，フレーム番号ｋのフレームをｂ番目に加えた暫定符号化順序Ｔ（１），Ｔ（２），Ｔ（３），Ｔ（４）を設定する。
【００４７】
各暫定符号化順序（順序１〜３）の各々について，図４（Ｂ）に示すように，評価合計初期設定部２０と評価合計加算部２１が，評価合計値Ｓを計算する。
【００４８】
Ｓ＝Ｅ（Ｔ（１），Ｔ（１））＋Ｅ（Ｔ（１），Ｔ（２））＋ｍｉｎ（Ｅ（Ｔ（１），Ｔ（３））＋Ｅ（Ｔ（２），Ｔ（３）））＋ｍｉｎ（Ｅ（Ｔ（１），Ｔ（４）），Ｅ（Ｔ（２），Ｔ（４）），Ｅ（Ｔ（３），Ｔ（４）））
ここで，ｍｉｎ（ｘ，ｙ，ｚ）は，ｘ，ｙ，ｚの中の最小値を表す。
【００４９】
各暫定符号化順序について評価合計値Ｓを計算し，図４（Ｃ）のように，その中で最小となる評価合計値Ｓの暫定符号化順序を，求めるＭフレームの符号化順序として出力する。
【００５０】
図５に，画像符号化順序決定装置１による符号化順序決定処理フローを示す。まず，フレーム内評価値計算部１３によりフレーム内評価値計算ステップＳ１，フレーム間評価値計算部１４によりフレーム間評価値計算ステップＳ２を実行し，評価値Ｅ（ｉ，ｉ），評価値Ｅ（ｉ，ｊ）を計算して結果を，評価値蓄積メモリに１５に蓄積する。フレーム内評価値計算ステップＳ１およびフレーム間評価値計算ステップＳ２をＮフレームの全組み合せに対して繰り返し実行する（ステップＳ３）。ここで，フレーム内評価値計算ステップＳ１とフレーム間評価値計算ステップＳ２の順序は入れ替えてもよい。
【００５１】
その後，フレーム追加初期設定部１６によりフレーム追加初期設定ステップＳ４を実行し，（Ｍ−１）個のフレームについて符号化順序フレーム番号Ｆの値を設定する。また，対象フレーム設定部１７により対象フレーム設定ステップＳ５を実行し，符号化対象として追加するフレームのフレーム番号の値ｋを符号化順序フレーム番号Ｆの値以外の１からＮまでの値に設定する。なお，フレーム追加初期設定ステップＳ４と対象フレーム設定ステップＳ５の順序は入れ替えてもよい。
【００５２】
次に，対象フレーム順序設定部１８により対象フレーム順序設定ステップＳ６を実行し，フレーム番号ｋのフレームを，第ｂ番目（ｂは予め設定された値ｃからＭまでのいずれか）の符号化順序に設定する。暫定符号化順序設定部１９では，暫定符号化順序設定ステップＳ７を実行し，符号化順序フレーム番号Ｆに設定された符号化順序に対して，対象フレーム順序設定ステップＳ６で設定したフレーム番号ｋのフレームを加えた暫定符号化順序Ｔ（ｉ）（ｉは１からＭまで）を設定する。
【００５３】
評価合計初期設定部２０により評価合計初期設定ステップＳ８を実行し，評価値Ｅ（Ｔ（１），Ｔ（１））を評価合計値Ｓに設定する。その後，評価合計加算部２１により評価合計加算ステップＳ９を実行し，暫定符号化順序で設定されたフレーム番号の順序でＴ（ｊ）を変更し，評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））（ｉは１からｊ−１までのいずれか）を，ｊが２からＭまで，評価合計値Ｓに繰り返し加算する。
【００５４】
対象フレームの全ての符号化順序に対して対象フレーム順序設定ステップＳ６から評価合計加算ステップＳ９までの処理を繰り返し（ステップＳ１０），対象フレーム順序決定部２２により対象フレーム順序決定ステップＳ１１を実行して，評価合計加算ステップＳ９で得られる暫定符号化順序ごとの評価合計値Ｓが最も小さい値となる対象フレーム順序ｂの値を決定して，処理を終了する。
【００５５】
評価合計加算ステップＳ９の処理フローの一例を図６に示す。まず，ｊ＝２に設定する（ステップＳ９１）。次に，値ｉを１からｊ−１までのいずれかの値に決定する（ステップＳ９２）。評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を評価合計値Ｓに加算し（ステップＳ９３），ｊがＭに等しくなるまで（ステップＳ９４），ｊの値を１加算して（ステップＳ９５），ステップＳ９２〜Ｓ９４を繰り返し実行し，ｊがＭに等しくなったら，処理を終了する。
【００５６】
図７は，図５に示す評価合計加算ステップＳ９の他の処理フローの一例を示す。まず，ｊ＝２に設定する（ステップＳ１０１）。次に，フレーム評価合計加算ステップＳ１０２（図８，図９，図１０）を実行する。その後，ｊがＭに等しいかどうかを判定し（ステップＳ１０３），ｊがＭに等しくなければｊの値を１加算して（ステップＳ１０４），ステップＳ１０２に戻り，同様に処理を繰り返す。ｊがＭに等しければ，処理を終了する。
【００５７】
図８は，フレーム評価合計加算ステップＳ１０２の処理フローの一例を示す。この例では，最初に評価値の最小値ＭＥにＥ（Ｔ（１），Ｔ（ｊ））を設定する（ステップＳ１１１）。ｊ＝２かどうかを判定し（ステップＳ１１２），ｊが２ならばステップＳ１１８に進む。ｊが２でなければ，ｉ＝２に設定する（ステップＳ１１３）。
【００５８】
次に，Ｅ（Ｔ（ｉ），Ｔ（ｊ））とＭＥとの大小を比較し（ステップＳ１１４），Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥであれば，Ｅ（Ｔ（ｉ），Ｔ（ｊ））をＭＥに設定する（ステップＳ１１５）。Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥでなければ，ステップＳ１１６に進む。
【００５９】
ステップＳ１１６において，ｉがｊ−１に等しいかどうかを判断する。ｉがｊ−１に等しくなければｉの値を１加算して（ステップＳ１１７），ステップＳ１１４に戻り，ｉがｊ−１に等しければ，ＭＥを評価合計値Ｓに加算して（ステップＳ１１８），処理を終了する。
【００６０】
図９は，フレーム評価合計加算ステップＳ１０２の他の処理フローの一例を示す。この例では，まず，評価値の最小値ＭＥに，最大値∞を設定し（ステップＳ１２１），ｉ＝１に設定する（ステップＳ１２２）。その後，Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥかを判断する（ステップＳ１２３）。Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥの場合には，Ｅ（Ｔ（ｉ），Ｔ（ｊ））をＭＥに設定し（ステップＳ１２４），Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥでない場合には，ステップＳ１２５へ進む。ステップＳ１２５において，ｉがｊ−１に等しいかをどうか判断し（ステップＳ１２５），ｉがｊ−１に等しくなければｉの値を１加算して（ステップＳ１２６），ステップＳ１２３に戻り，ｉがｊ−１に等しければＭＥを評価合計値Ｓに加算して（ステップＳ１２７），処理を終了する。
【００６１】
図８と図９の例では，評価値の最小値の初期値の設定方法が異なっている。このように評価値の最小値を求めるフローは，初期値の設定方法により複数パターンが考えられるため，フレーム評価合計加算ステップＳ１０２の処理フローは，図８や図９に示したフロー以外でもよい。
【００６２】
フレーム評価合計加算ステップＳ１０２におけるさらに他の処理フローの例を，図１０に示す。図１０に示すフレーム評価合計加算ステップＳ１０２は，後述する実施例２で採用している処理の例である。
【００６３】
まず，参照可能フレーム番号設定ステップＳ１３１を実行して，参照可能フレーム番号の値を設定する。次に，評価値の最小値ＭＥに最大値∞を設定し（ステップＳ１３２），ｉ＝１に設定した後（ステップＳ１３３），以下の処理を繰り返す。
【００６４】
Ｔ（ｉ）が参照可能フレーム番号に含まれているかを判断する（ステップＳ１３４）。Ｔ（ｉ）が参照可能フレーム番号に含まれていなければ，ステップＳ１３７へ進む。Ｔ（ｉ）が参照可能フレーム番号に含まれていれば，Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥかをどうかを判断する（ステップＳ１３５）。Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥである場合には，Ｅ（Ｔ（ｉ），Ｔ（ｊ））をＭＥに設定し（ステップＳ１３６），Ｅ（Ｔ（ｉ），Ｔ（ｊ））＜ＭＥでない場合には，そのままステップＳ１３７へ進む。
【００６５】
ステップＳ１３７において，ｉがｊ−１に等しいかどうかを判断し，ｉがｊ−１に等しくない場合には，ｉの値を１加算して（ステップＳ１３８），ステップＳ１３４に戻り，ｉがｊ−１に等しい場合には，ＭＥを評価合計値Ｓに加算して（ステップＳ１３９），処理を終了する。
【００６６】
参照可能フレーム番号設定ステップ（ステップＳ１３１）以後における，評価値の最小値を求めるフローは，図１０に示す処理フローに限らず，他のフローに従ってもよい。
【００６７】
図５に示すフレーム追加初期設定ステップＳ４における処理フローの一例を，図１１に示す。図１１において，まずｉ＝１に設定する（ステップＳ１４１）。次に，フレーム近傍評価探索ステップＳ１４２を実行する。ここでは，第ｉフレームについて，例えば評価値Ｅ（ｉ，ｊ）の，評価値が最小の場合のｊの値ｊ１（ｉ）と，評価値が２番目に小さい場合のｊの値ｊ２（ｉ）を求める。続いてフレーム近傍評価加算ステップＳ１４３を実行する。ここでは，第ｉフレームについて，評価値Ｅ（ｉ，ｉ）と評価値Ｅ（ｉ，ｊ１（ｉ））と評価値Ｅ（ｉ，ｊ２（ｉ））の値を合計して，評価合計値ＥＳ（ｉ）を求める。
【００６８】
次に，ｉがＮに等しいかを判断する（ステップＳ１４４）。ｉがＮに等しくない場合にはｉの値を１加算して（ステップＳ１４５），ステップＳ１４２に戻る。ｉがＮに等しい場合には，フレーム近傍評価合計探索ステップＳ１４６の実行へ移る。
【００６９】
フレーム近傍評価合計探索ステップＳ１４６では，評価合計値ＥＳ（ｉ）が最も小さいときのｉの値ｍを求め，次にステップＳ１４７において，求めたｍから符号化順序フレーム番号に，ｍとｊ１（ｍ）とｊ２（ｍ）とを設定し，処理を終了する。
【実施例１】
【００７０】
Ｎフレームの２次元画像の符号化順序を決定する方法について示す。２次元画像を全Ａ個のマクロブロックに分割して符号化する際の符号化順序を決定する。
【００７１】
最初の３フレーム分の符号化順序をフレーム追加初期設定部１６がフレーム追加初期設定ステップＳ４で決定するものとする。また，フレーム内評価値計算部１３によるフレーム内評価値計算ステップＳ１とフレーム間評価値計算部１４によるフレーム間評価計算ステップＳ２では，式（３）で計算される値Ｊを評価値として使用するものとする。
【００７２】
フレーム内評価値計算ステップＳ１では，国際標準映像符号化方式Ｈ．２６４のイントラ予測を用いるものとする。フレーム内評価値計算ステップＳ１とフレーム間評価値計算ステップＳ２では，予測残差をＤＣＴして量子化し，さらに逆量子化してＩＤＣＴして得られる予測誤差を予測画像に加算することにより復号画像を作成する。
【００７３】
量子化に使用するパラメータは，Ｎフレームの全マクロブロックで同じものを使う。評価値はマクロブロック毎に求め，フレーム内評価値計算ステップＳ１で計算するフレーム番号ｉにおけるマクロブロックａの評価値をＥ（ｉ，ａ，ｉ）とする。フレーム間評価値計算ステップＳ２で計算するフレーム番号ｊにおけるマクロブロックａの，フレーム番号ｉからの差分に関する評価値をＥ（ｉ，ａ，ｊ）とする。対象フレーム順序設定ステップＳ６における値ｃは２に設定する。
【００７４】
実施例１として参照可能フレーム番号設定ステップを行わない方法の例を示す。評価合計加算ステップＳ９では，図７のフレーム評価合計加算ステップＳ１０２を実行し，フレーム評価合計加算ステップＳ１０２は，図９に示したフローに従って実行するものとする。本実施例では，先頭３フレームの符号化順序をフレーム追加初期設定ステップＳ４で決定した後，４フレーム目以後の全フレームの符号化順序を決定する手順を示す。
【００７５】
まず，図５のフローに従い，全Ｎフレームの組み合わせについて，フレーム内評価値計算部１３によるフレーム内評価値計算ステップＳ１およびフレーム間評価値計算部１４によるフレーム間評価値計算ステップＳ２を実行する。続いてフレーム追加初期設定部１６がフレーム追加初期設定ステップＳ４（図１１）を実行する。
【００７６】
図１１のフローに従って，３フレーム分の符号化順序フレーム番号Ｆ（Ｆ（１），Ｆ（２），Ｆ（３））を求める。まず，フレーム近傍評価探索部１６１がフレーム近傍評価探索ステップＳ１４２を実行する。このステップＳ１４２では，例えば，フレーム番号ｉについて，評価値Ｅ（ｉ，ａ，ｉ）を全マクロブロックで合計して評価値Ｅ（ｉ，ｉ）を求める。次に，フレーム番号ｊがｉ以外の１からＮまでについて，評価値Ｅ（ｉ，ａ，ｊ）をフレーム毎に全マクロブロックで合計して評価値Ｅ（ｉ，ｊ）を求める。そして評価値Ｅ（ｉ，ｊ）の値が最も小さいときのｊの値ｊ１（ｉ）と，２番目に小さいときのｊの値ｊ２（ｉ）を求める。
【００７７】
次に，フレーム近傍評価加算部１６２が，フレーム近傍評価加算ステップＳ１４３を実行する。ここでは，フレーム近傍評価探索ステップＳ１４２で求めた，各ｉに対するｊの２つの値ｊ１（ｉ）とｊ２（ｉ）から，評価値Ｅ（ｉ，ｉ）とＥ（ｉ，ｊ１（ｉ））とＥ（ｉ，ｊ２（ｉ））を合計して評価値ＥＳ（ｉ）を求める。以上のフレーム近傍評価探索ステップＳ１４２とフレーム近傍評価加算ステップＳ１４３を，値ｉを１からＮまで変更して実行する（ステップＳ１４４，Ｓ１４５）。
【００７８】
次に，フレーム近傍評価合計探索部１６４が，フレーム近傍評価合計探索ステップＳ１４６を実行し，評価値ＥＳ（ｉ）が最も小さいときのｉの値ｍを求める（ステップＳ１４６）。そして（ｍ，ｊ１（ｍ），ｊ２（ｍ））を符号化順序フレーム番号Ｆ（Ｆ（１），Ｆ（２），Ｆ（３））に設定する（ステップＳ１４７）。
【００７９】
次に，図５の対象フレーム設定ステップＳ５では，対象フレーム設定部１７が，値ｋとして符号化順序フレーム番号Ｆ以外で１からＮまでの値を設定する。ここでは，最も小さい値を設定するものとする。以後，ここで設定した値をフレーム番号とするフレームを追加し，符号化順序を決定することになる。
【００８０】
符号化順序フレーム番号Ｆが（Ｍ−１）フレームある場合に，フレーム番号ｋを追加した符号化順序の決定方法を次に示す。まず，図５の対象フレーム順序設定ステップＳ６では，フレーム番号ｋのフレームの符号化順序を第ｂ番目に設定する。図５の暫定符号化順序設定ステップＳ７では，暫定符号化順序設定部１９が符号化順序フレーム番号Ｆのｂ番目にフレーム番号ｋを挿入して，暫定符号化順序Ｔ（Ｔ（ｉ），ｉは１からＭまで）を設定する。図５の評価合計初期設定ステップＳ８では，評価合計初期設定部２０が評価合計値ＳをＥ（Ｔ（１），Ｔ（１））に設定する。
【００８１】
図５の評価合計加算ステップＳ９では，図７のフローに従い，評価合計加算部２１が，暫定符号化順序Ｔの順序で，１フレームずつ評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を評価合計値Ｓに加算していく。
【００８２】
加算する評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））は，フレーム評価合計加算ステップＳ１０２として図９に示したフローに従って決定し，加算する。ここでフレーム評価合計加算ステップＳ１０２はマクロブロック毎に実行する。すなわち，マクロブロックａについて評価値Ｅ（Ｔ（ｉ），ａ，Ｔ（ｊ））を決定して，加算する処理を，ａを１からＡまで変更して繰り返し実行する。評価合計加算ステップＳ９により，暫定符号化順序Ｔで設定された，Ｔ（１）以外の全（Ｍ−１）フレームについての評価値を加算した評価合計値Ｓを求める。
【００８３】
以上の対象フレーム順序設定ステップＳ６から評価合計加算ステップＳ９までの処理をｂの値を変更して実行し（図５のステップＳ１０），対象フレーム順序決定ステップＳ１１では，対象フレーム順序決定部２２が評価合計値Ｓが最小となるｂの値を探索し，探索された位置にフレーム番号ｋを挿入した順序を符号化順序に決定する。このようにして得られたＭフレームの符号化順序を符号化順序フレーム番号Ｆに設定する。
【００８４】
以上の対象フレーム設定ステップＳ５から対象フレーム順序決定ステップＳ１１までを，値ｋを変更しながら（Ｎ−３）回繰り返し実行していき，全Ｎフレーム分の符号化順序を決定する。
【００８５】
本実施例では，先頭３フレームの符号化順序をフレーム追加初期設定部１６で決定したが，２フレームまたは４フレーム目以上のフレーム数の符号化順序をフレーム追加初期設定部１６で決定してもよい。先頭（ｋ＋１）フレームの符号化順序を，フレーム追加初期設定ステップＳ４で決定する場合には，フレーム近傍評価探索部１６１で，評価値Ｅ（ｉ，ｊ）の値が１番目に小さいときのｊの値ｊ１（ｉ）からｋ番目に小さいときのｊの値ｊｋ（ｉ）の合計ｋ個の値を求める。フレーム近傍評価加算部１６２では，各ｉに対するｊのｋ個の値ｊ１（ｉ）からｊｋ（ｉ）までについて，評価値Ｅ（ｉ，ｉ）と，Ｅ（ｉ，ｊ１（ｉ））からＥ（ｉ，ｊｋ（ｉ））までを合計して評価値ＥＳ（ｉ）を求める。
【００８６】
以上のフレーム近傍評価探索部１６１とフレーム近傍評価加算部１６２の処理を，値ｉを１からＮまで変更して実行する。次に，フレーム近傍評価合計探索部１６４で評価値ＥＳ（ｉ）が最も小さいときのｉの値ｍを求める。求めた値ｍをもとに，（ｍ，ｊ１（ｍ），ｊ２（ｍ），…，ｊｋ（ｍ））を符号化順序フレーム番号Ｆ（Ｆ（１），Ｆ（２），…，Ｆ（ｋ））に設定する。
【００８７】
以上のように実施例１によれば，全パターンの符号化順序を検証する方法に比べて，符号化順序を決定するために必要な評価値の加算回数を減少することができ，演算負荷を軽減することができる。
【実施例２】
【００８８】
実施例２として，参照可能フレーム番号設定ステップを行う方法の例を示す。参照可能フレーム数をＬ（Ｌ＜Ｎ）と設定する。図５の評価合計加算ステップＳ９では，図７のフレーム評価合計加算ステップＳ１０２を実行し，フレーム評価合計加算ステップＳ１０２は，図１０に示したフローに従って実行するものとする。
【００８９】
符号化順序フレーム番号ＦがＬ個以下の場合には，実施例１と全く同様な動作である。符号化順序フレーム番号ＦがＬ個より多い場合の処理について次に示す。図５に示すフレーム内評価値計算ステップＳ１から評価合計初期設定ステップＳ８までは，実施例１と同様な処理である。
【００９０】
図５の評価合計加算ステップＳ９での動作を次に示す。評価合計加算ステップＳ９では，図７のフローに従い，評価合計加算部２１が，暫定符号化順序Ｔの順序で，１フレームずつ評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を評価合計値Ｓに加算していく。加算する評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））は，フレーム評価合計加算ステップＳ１０２として，図１０に示したフローに従って決定し，加算する。図１０の参照可能フレーム番号設定ステップＳ１３１では，参照可能フレーム番号Ｒ（Ｒ（ｄ），ｄは１からＬまで）を設定する。
【００９１】
暫定符号化順序で第ｊ番目フレームの評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を決定する際には，参照可能フレーム番号Ｒは，暫定符号化順序Ｔのうちの（Ｔ（ｊ−ｄ），ｄは１からＬまで）に設定する。なお，ｊがＬ以下の場合には，参照可能フレーム番号Ｒとして暫定符号化順序Ｔの先頭ｊ個の値に設定する。
【００９２】
フレーム評価合計加算ステップＳ１０２は，マクロブロック毎に実行する。すなわち，マクロブロックａについて評価値Ｅ（Ｔ（ｉ），ａ，Ｔ（ｊ））を決定して，加算する処理を，ａを１からＡまで変更して繰り返し実行する。Ｔ（ｉ）の候補は参照可能フレーム番号Ｒ（Ｒ（ｄ），ｄは１からＬまで）のうちのいずれかと一致するように選択する。
【００９３】
評価合計加算ステップＳ９により，暫定符号化順序Ｔで設定された，Ｔ（１）以外の全（Ｍ−１）フレームについての評価値を加算した評価合計値Ｓを求める。以後の他のステップは実施例１と同様に処理し，全Ｎフレーム分の符号化順序を決定する。以上のように実施例２によれば，フレーム間評価値を加算する回数を軽減することができ，実施例１よりも，さらに演算負荷を軽減することができる。
【００９４】
また，実施例２によれば，符号化対象フレーム数Ｎよりも少ないフレーム分の参照画像メモリを備える画像符号化順序決定装置によって画像を符号化する場合の，符号化順序を決定することができる。本実施例２の参照可能フレーム番号設定ステップＳ１３１で設定する参照可能フレーム番号の数を，画像符号化順序決定装置の参照画像メモリのフレーム数と同じ値にしておけばよい。
【００９５】
なお，実施例２における参照可能フレーム番号設定ステップＳ１３１では，暫定符号化順序で第ｊ番目フレームの評価値Ｅ（Ｔ（ｉ），Ｔ（ｊ））を決定する際には，参照可能フレーム番号Ｒは暫定符号化順序Ｔのうちの（Ｔ（ｊ−ｄ），ｄは１からＬまで）に設定したが，他の方法でもよい。
【００９６】
例えば次の方法が挙げられる。なお，これらの方法に限らず，参照可能フレーム番号設定ステップＳ１３１では，Ｌ個の参照可能フレーム番号を設定できれば，どのような方法に従ってもよい。例えば，以下の方法ｄ１，ｄ２を用いてもよい。
・方法ｄ１：暫定符号化順序ＴのうちのＴ（ｅ）（ｅは１からｊまで）の中で，値が大きい順からＬ個の値に設定する。
・方法ｄ２：暫定符号化順序ＴのうちのＴ（ｅ）（ｅは１からＬまで）に設定する。
【００９７】
上記「方法ｄ１」によれば，フレーム番号の近い画像を使って符号化順序を決定することができる。また，「方法ｄ２」によれば，符号化順序の早いフレームを使って符号化順序を決定することができる。
【００９８】
本実施例により，参照画像メモリがＬ個に限定されている条件下で決定した符号化順序で符号化した複数の画像を伝送するときに，伝送エラーの発生する伝送路を介して符号化データを通信する際に，「方法ｄ２」によれば，直前に受信したフレームに伝送エラーが発生したとしても，現フレームで符号化順序の早いフレームを参照するようにしていれば，伝送エラーの伝播を防ぐことができる。
【００９９】
また，上記実施例１と実施例２とでは，対象フレーム設定ステップで設定する値ｋを，値の小さいものから順に設定したが，他の方法に従ってもよい。Ｍフレーム目を追加した場合のフレーム番号がｋであったとすると，次に対象フレーム設定ステップＳ５を実行するときの値の設定方法として，例えば以下の２つの方法ｋ１，ｋ２が挙げられる。なお，これらの方法に限らず，対象フレーム設定ステップＳ５では，符号化順序フレーム番号Ｆ以外で１からＮまでの値を設定できれば，どのような方法に従って値ｋを設定してもよい。
・方法ｋ１：値をｋ＋１またはｋ−１にいずれかに設定する。
・方法ｋ２：符号化順序フレーム番号Ｆの最大のフレーム番号に１を加算した値，または最小のフレーム番号から１を減算した値に設定する。
【０１００】
以上の画像符号化順序を決定する処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【０１０１】
【図１】本発明の画像符号化順序決定装置の構成の一例を示す図である。
【図２】フレーム追加初期設定部の構成の一例を示す図である。
【図３】本発明の実施の形態の処理概要を説明する図である。
【図４】本発明の実施の形態の処理概要を説明する図である。
【図５】本発明に係る符号化順序決定処理フローの例を示す図である。
【図６】評価合計加算ステップの処理フロー（例１）を示す図である。
【図７】評価合計加算ステップの処理フロー（例２）を示す図である。
【図８】フレーム評価合計加算ステップの処理フロー（例１）を示す図である。
【図９】フレーム評価合計加算ステップの処理フロー（例２）示す図である。
【図１０】フレーム評価合計加算ステップの処理フロー（例３）を示す図である。
【図１１】フレーム追加初期設定ステップの処理フローの例を示す図である。
【符号の説明】
【０１０２】
１    画像符号化順序決定装置
１１  原画像蓄積メモリ
１２  切替部
１３  フレーム内評価値計算部
１４  フレーム間評価値計算部
１５  評価値蓄積メモリ
１６  フレーム追加初期設定部
１７  対象フレーム設定部
１８  対象フレーム順序設定部
１９  暫定符号化順序設定部
２０  評価合計初期設定部
２１  評価合計加算部
２２  対象フレーム順序決定部
１６１  フレーム近傍評価探索部
１６２  フレーム近傍評価加算部
１６３  フレーム近傍評価蓄積メモリ
１６４  フレーム近傍評価合計探索部
【図１】
2005080179.tif 000003
【図２】
2005080179.tif 000004
【図３】
2005080179.tif 000005
【図４】
2005080179.tif 000006
【図５】
2005080179.tif 000007
【図６】
2005080179.tif 000008
【図７】
2005080179.tif 000009
【図８】
2005080179.tif 000010
【図９】
2005080179.tif 000011
【図１０】
2005080179.tif 000012
【図１１】
2005080179.tif 000013