(57)【特許請求の範囲】
【請求項１】
原信号に一致する復号が可能なビデオ符号化を行う可逆ビデオ符号化方法であって，
あらかじめ定められた非可逆のビデオ符号化方式に準拠し，画像信号の各ブロック毎に原信号からフレーム内符号化における空間予測またはフレーム間符号化における時間予測による予測信号を差し引いた残差信号を入力するステップと，
前記非可逆のビデオ符号化方式に基づき，前記残差信号に対し直交変換を施して得られる変換係数およびそれを量子化した量子化係数を求めるステップと，
量子化時に用いた量子化パラメータおよび量子化方法を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定するステップと，
前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断のステップと，
前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを所定の格子点の順番で探索し列挙するステップと，
列挙された格子点に，列挙順に通し番号を割り当てるステップと，
列挙された格子点の中で，残差信号の変換係数に一致する格子点の通し番号を得るステップと，
前記残差信号の変換係数に一致する格子点の通し番号を符号化し出力するステップとを有する
ことを特徴とする段階的可逆ビデオ符号化方法。
【請求項２】
請求項１に記載の段階的可逆ビデオ符号化方法において，
前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを列挙するステップでは，複数の変換係数の間に，該複数の変換係数を用いて所定の計算処理をすることで得られるベクトルの全ての要素の値が常にＮ（但し，Ｎは２以上の整数）の倍数になるという整数的値関係があるとき，該整数的値関係を用いることにより，前記空間内で変換係数がとり得ない点については，残差信号の直交変換の結果として妥当であるかどうかの判断処理を省略する
ことを特徴とする段階的可逆ビデオ符号化方法。
【請求項３】
請求項１または請求項２に記載の段階的可逆ビデオ符号化方法において，
特定のいくつかの変換係数について，該係数と既に出力済みの係数との間に，該係数と前記既に出力済みの係数とを用いて所定の計算処理をすることで得られるベクトルの全ての要素の値が常にＮ（但し，Ｎは２以上の整数）の倍数になるという整数的値関係がある場合に，該整数的値関係を利用し，範囲を狭めて該係数を符号化することで，該係数がとり得ない値を除いた情報を出力するステップを有し，
前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを列挙するステップでは，前記既に出力済みの係数を用い，次元の縮小した存在空間内で格子点を列挙する
ことを特徴とする段階的可逆ビデオ符号化方法。
【請求項４】
請求項１から請求項３までのいずれか１項に記載の段階的可逆ビデオ符号化方法において，
前記妥当性判断のステップでは，前記逆変換に用いる直交行列の逆行列が０．２５の整数倍である場合，前記直交行列の逆行列を２０倍した値を用いて前記量子化残差信号を算出し，該量子化残差信号の全ての要素の下位４ビットが０であるか否かを判定することにより，妥当性を判定する
ことを特徴とする段階的可逆ビデオ符号化方法。
【請求項５】
請求項１から請求項４までのいずれか１項に記載の段階的可逆ビデオ符号化方法において，
残差信号の存在範囲と変換係数の存在範囲の交わりが凸多面体となることを用いて，判断対象となる前記格子点が前記凸多面体の外部に存在する場合に前記妥当性判断を途中で中止する
ことを特徴とする段階的可逆ビデオ符号化方法。
【請求項６】
請求項１から請求項５までのいずれか１項に記載の段階的可逆ビデオ符号化方法により符号化された符号化ストリームを復号する復号方法であって，
前記あらかじめ定められた非可逆のビデオ符号化方式に対応する復号方式を実行するステップと，
量子化パラメータおよび符号化側の量子化方法，ならびに既に復号された係数がある場合にはその係数を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定するステップと，
復号すべき係数を復号するステップと，
前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断のステップと，
前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを，符号化時における格子点の探索の順番と同じ順番で探索し列挙するステップと，
通し番号を復号するステップと，
前記列挙された格子点の中で，前記復号された通し番号に等しい順番の格子点を出力するステップとを有する
ことを特徴とする段階的可逆ビデオ復号方法。
【請求項７】
原信号に一致する復号が可能なビデオ符号化を行う可逆ビデオ符号化装置であって，
あらかじめ定められた非可逆のビデオ符号化方式に準拠し，画像信号の各ブロック毎に原信号からフレーム内符号化における空間予測またはフレーム間符号化における時間予測による予測信号を差し引いた残差信号を入力する手段と，
前記非可逆のビデオ符号化方式に基づき，前記残差信号に対し直交変換を施して得られる変換係数およびそれを量子化した量子化係数を求める手段と，
量子化時に用いた量子化パラメータおよび量子化方法を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定する存在空間決定手段と，
前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断手段と，
前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを所定の格子点の順番で探索し列挙する手段と，
列挙された格子点に，列挙順に通し番号を割り当てる手段と，
列挙された格子点の中で，残差信号の変換係数に一致する格子点の通し番号を得る手段と，
前記残差信号の変換係数に一致する格子点の通し番号を符号化し出力する手段とを備える
ことを特徴とする段階的可逆ビデオ符号化装置。
【請求項８】
請求項７に記載の段階的可逆ビデオ符号化装置により符号化された符号化ストリームを復号する復号装置であって，
前記あらかじめ定められた非可逆のビデオ符号化方式に対応する復号方式を実行する手段と，
量子化パラメータおよび符号化側の量子化方法，ならびに既に復号された係数がある場合にはその係数を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定する存在空間決定手段と，
復号すべき係数を復号する係数復号手段と，
前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断手段と，
前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを，符号化時における格子点の探索の順番と同じ順番で探索し列挙する手段と，
通し番号を復号する通し番号復号手段と，
前記列挙された格子点の中で，前記復号された通し番号に等しい順番の格子点を出力する出力手段とを備える
ことを特徴とする段階的可逆ビデオ復号装置。
【請求項９】
請求項１から請求項５までのいずれか１項に記載の段階的可逆ビデオ符号化方法をコンピュータに実行させるための段階的可逆ビデオ符号化プログラム。
【請求項１０】
請求項６に記載の段階的可逆ビデオ復号方法をコンピュータに実行させるための段階的可逆ビデオ復号プログラム。
【請求項１１】
請求項１から請求項５までのいずれか１項に記載の段階的可逆ビデオ符号化方法をコンピュータに実行させるためのプログラムをコンピュータ読み取り可能な記録媒体に記録したことを特徴とする段階的可逆ビデオ符号化プログラムの記録媒体。
【請求項１２】
請求項６に記載の段階的可逆ビデオ復号方法をコンピュータに実行させるためのプログラムをコンピュータ読み取り可能な記録媒体に記録したことを特徴とする段階的可逆ビデオ復号プログラムの記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は高能率ビデオ符号化／復号技術に関し，特に，基本部分として伝送される符号はＨ．２６４標準と互換性を保ちながら，付加部分の符号量をできるだけ低く抑えつつ，原信号に一致する可逆な復号を可能とする段階的可逆ビデオ符号化／復号技術に関する。【０００２】
本願は，２００４年９月３０日に出願された特願２００４−２８６４１２号に対して優先権を主張するものであって，その内容をここに援用する。
【背景技術】
【０００３】
従来の可逆あるいは段階的ビデオ符号化方式には以下のようなものがある。ＭｏｔｉｏｎＪＰＥＧ２０００標準（非特許文献１参照）の可逆モードやＪＰＥＧ−ＬＳ（非特許文献２参照）は，静止画ベースであるためフレーム内に閉じた符号化を行う。【０００４】
Ｈ．２６４標準（非特許文献３参照）の第二版“Fidelity Range Extension(FRExt) ”は，フレーム内・フレーム間予測残差信号を（直交変換・量子化せず）そのまま伝送する。【０００５】
非可逆な符号化方式と組み合わせた段階的符号化方式としては，復号画像と原画像の差分を符号化するもの（非特許文献４参照）がある。これは基本情報にＭＰＥＧ−２を用いているが，他の方式であっても適用は可能である。【０００６】
また，ＭＰＥＧ−４標準（非特許文献５参照）の Fine Granularity Scalable(FGS) Profile 方式のように，ＤＣＴ（離散コサイン変換）を施し整数化したものに対し，ビットプレーン展開し逐次伝送するというものがある。
【非特許文献１】ISO/IEC 15444-3:2002 Information technology −JPEG 2000 image coding system −Part 3:Motion JPEG 2000
【非特許文献２】ISO/IEC l4495-1:1999 Information technology −Lossless and near-lossless coding of continuous tone still images
【非特許文献３】ISO/IEC 14496-10:2003 Information technology− Coding of audio-visual objects −Part 10:Advanced Video Coding
【非特許文献４】中嶋，八島，小林：“ＭＰＥＧ−２符号化パラメータに基づく階層的ロスレス符号化の検討”，信学総大  D-11-49 ，Mar. 2000
【非特許文献５】ISO/IEC l4496-2:2003 Information technology −Coding of audio-visual objects−Part 2:Visual
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記ＪＰＥＧ２０００（非特許文献１参照）は，段階的伝送が可能であるが，フレーム内符号化をするため，ビデオ特有のフレーム間相関を用いた高能率符号化はできないという問題がある。また，上記ＪＰＥＧ−ＬＳ（非特許文献２参照）は，ＪＰＥＧ２０００よりも効率は高いが，やはりフレーム内に閉じた符号化であり効率に限界があるほか，段階的伝送ができないという問題がある。【０００８】
Ｈ．２６４標準（非特許文献３参照）の第二版“Fidelity Range Extension(FRExt) ”は，段階的伝送ができないという問題がある。【０００９】
また，上記非特許文献４に記載された技術は，直交変換空間内での残差ではなく，原信号空間での残差を符号化対象とするため，元来原信号が存在しないはずの空間までも考慮した符号化をせざるをえず，圧縮効率に限界がある。【００１０】
ＭＰＥＧ−４標準（非特許文献５参照）の Fine Granularity Scalable(FGS) Profile 方式は，
・実数変換であるＤＣＴ後，係数が整数化されるため，いくら付加情報を多く使っても可逆にはできないという問題，
・後述の式（６）のように変換後の係数が伸張されるＨ．２６４標準方式においてそのまま適用すると，伸張分がそのまま符号量の無駄につながってしまうという問題，
などがあった。【００１１】
このようにフレーム間予測を行うことでビデオ符号化効率を高め，スケーラビリティを有し，かつ基本情報がＨ．２６４標準互換である方式は提案されていなかった。【００１２】
本発明は，上に述べたような問題に鑑みて，基本部分として伝送される符号はＨ．２６４標準と互換性を保ちながら，付加部分の符号量をできるだけ低く抑えつつ，可逆な復号を可能とすることを目的とする。
【課題を解決するための手段】
【００１３】
上記課題を解決するため，本発明の第１の態様に係る段階的可逆ビデオ符号化方法は，原信号に一致する復号が可能なビデオ符号化を行う可逆ビデオ符号化方法であって，あらかじめ定められた非可逆のビデオ符号化方式に準拠し，画像信号の各ブロック毎に原信号からフレーム内符号化における空間予測またはフレーム間符号化における時間予測による予測信号を差し引いた残差信号を入力するステップと，前記非可逆のビデオ符号化方式に基づき，前記残差信号に対し直交変換を施して得られる変換係数およびそれを量子化した量子化係数を求めるステップと，量子化時に用いた量子化パラメータおよび量子化方法を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定するステップと，前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断のステップと，前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを所定の格子点の順番で探索し列挙するステップと，列挙された格子点に，列挙順に通し番号を割り当てるステップと，列挙された格子点の中で，残差信号の変換係数に一致する格子点の通し番号を得るステップと，前記残差信号の変換係数に一致する格子点の通し番号を符号化し出力するステップとを有する。
【００１４】
本発明の第２の態様は，上記段階的可逆ビデオ符号化方法において，前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを列挙するステップでは，複数の変換係数の間に，該複数の変換係数を用いて所定の計算処理をすることで得られるベクトルの全ての要素の値が常にＮ（但し，Ｎは２以上の整数）の倍数になるという整数的値関係があるとき，該整数的値関係を用いることにより，前記空間内で変換係数がとり得ない点については，残差信号の直交変換の結果として妥当であるかどうかの判断処理を省略する。
【００１５】
本発明の第３の態様は，上記段階的可逆ビデオ符号化方法において，特定のいくつかの変換係数について，該係数と既に出力済みの係数との間に，該係数と前記既に出力済みの係数とを用いて所定の計算処理をすることで得られるベクトルの全ての要素の値が常にＮ（但し，Ｎは２以上の整数）の倍数になるという整数的値関係がある場合に，該整数的値関係を利用し，範囲を狭めて該係数を符号化することで，該係数がとり得ない値を除いた情報を出力するステップを有し，前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを列挙するステップでは，前記既に出力済みの係数を用い，次元の縮小した存在空間内で格子点を列挙する。
【００１６】
本発明の第４の態様は，上記段階的可逆ビデオ符号化方法において，前記妥当性判断のステップでは，前記逆変換に用いる直交行列の逆行列が０．２５の整数倍である場合，前記直交行列の逆行列を２０倍した値を用いて前記量子化残差信号を算出し，該量子化残差信号の全ての要素の下位４ビットが０であるか否かを判定することにより，妥当性を判定する。
【００１７】
本発明の第５の態様は，上記段階的可逆ビデオ符号化方法において，残差信号の存在範囲と変換係数の存在範囲の交わりが凸多面体となることを用いて，判断対象となる前記格子点が前記凸多面体の外部に存在する場合に前記妥当性判断を途中で中止する。【００１９】
本発明の第６の態様は，上記段階的可逆ビデオ符号化方法により符号化された符号化ストリームを復号する復号方法であって，前記あらかじめ定められた非可逆のビデオ符号化方式に対応する復号方式を実行するステップと，量子化パラメータおよび符号化側の量子化方法，ならびに既に復号された係数がある場合にはその係数を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定するステップと，復号すべき係数を復号するステップと，前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断のステップと，前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを，符号化時における格子点の探索の順番と同じ順番で探索し列挙するステップと，通し番号を復号するステップと，前記列挙された格子点の中で，前記復号された通し番号に等しい順番の格子点を出力するステップとを有する。
【００２０】
本発明の第７の態様に係る段階的可逆ビデオ符号化装置は，原信号に一致する復号が可能なビデオ符号化を行う可逆ビデオ符号化装置であって，あらかじめ定められた非可逆のビデオ符号化方式に準拠し，画像信号の各ブロック毎に原信号からフレーム内符号化における空間予測またはフレーム間符号化における時間予測による予測信号を差し引いた残差信号を入力する手段と，前記非可逆のビデオ符号化方式に基づき，前記残差信号に対し直交変換を施して得られる変換係数およびそれを量子化した量子化係数を求める手段と，量子化時に用いた量子化パラメータおよび量子化方法を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定する存在空間決定手段と，前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断手段と，前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを所定の格子点の順番で探索し列挙する手段と，列挙された格子点に，列挙順に通し番号を割り当てる手段と，列挙された格子点の中で，残差信号の変換係数に一致する格子点の通し番号を得る手段と，前記残差信号の変換係数に一致する格子点の通し番号を符号化し出力する手段とを備える。
【００２１】
本発明の第８の態様は，上記段階的可逆ビデオ符号化装置により符号化された符号化ストリームを復号する復号装置であって，前記あらかじめ定められた非可逆のビデオ符号化方式に対応する復号方式を実行する手段と，量子化パラメータおよび符号化側の量子化方法，ならびに既に復号された係数がある場合にはその係数を用いて，前記量子化係数に対して量子化の逆演算をすることで，変換係数がとり得る上下限値の数値範囲である変換係数の存在空間を特定する存在空間決定手段と，復号すべき係数を復号する係数復号手段と，前記変換係数の存在空間内の各格子点に対して，該格子点が残差信号の直交変換の結果として妥当であるかどうかを，前記量子化係数を逆変換することで得られる量子化残差信号の全要素が整数であるか否か，及び前記量子化残差信号と前記予測信号を加算して得られる行列の全要素が所定のビット数の範囲に収まっているか否かによって判断する妥当性判断手段と，前記変換係数の存在空間内の格子点のうち前記判断が妥当であるものを，符号化時における格子点の探索の順番と同じ順番で探索し列挙する手段と，通し番号を復号する通し番号復号手段と，前記列挙された格子点の中で，前記復号された通し番号に等しい順番の格子点を出力する出力手段とを備える。
【００２２】
以上の段階的可逆ビデオ符号化および復号の処理は，コンピュータとソフトウェアプログラムとによって実現することもでき，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。【００２３】
すなわち、本発明の第９の態様は、本発明の段階的可逆ビデオ符号化方法をコンピュータに実行させるための段階的可逆ビデオ符号化プログラムである。
本発明の第１０の態様は、本発明の段階的可逆ビデオ復号方法をコンピュータに実行させるための段階的可逆ビデオ復号プログラムである。
本発明の第１１の態様は、本発明の段階的可逆ビデオ符号化方法をコンピュータに実行させるためのプログラムをコンピュータ読み取り可能な記録媒体に記録した段階的可逆ビデオ符号化プログラムの記録媒体である。
本発明の第１２の態様は、本発明の段階的可逆ビデオ復号方法をコンピュータに実行させるためのプログラムをコンピュータ読み取り可能な記録媒体に記録した段階的可逆ビデオ復号プログラムの記録媒体である。
【発明の効果】
【００２４】
本発明によれば，基本部分として伝送される符号はＨ．２６４標準の符号化と互換性を保ちながら，付加部分の符号量をできるだけ低く抑えつつ，原信号に一致する可逆な復号を可能とすることができる。【００２５】
また，本発明によれば，処理を数兆倍に高速化して上記の処理を実行することができる。また，実際の符号化を行わずに，符号量の推定を行うことができ，結果として符号量を減らす予測モードの選択を高速に行うことができる。
【図面の簡単な説明】
【００２６】
【図１】Ｒ，Ｘの存在範囲ΩとΨをそれぞれ図示したものである。
【図２】Ψ領域の拡大図である。
【図３】段階的可逆ビデオ符号化装置の構成例を示す図である。
【図４】段階的可逆ビデオ復号装置の構成例を示す図である。
【図５】ｉｎｄｅｘの符号化に汎用可変長符号を用いた場合の段階的可逆ビデオ復号装置の構成例を示す図である。
【図６】実施例１の処理フローを示す図である。
【図７】実施例２の処理フローを示す図である。
【符号の説明】
【００２７】
１  段階的可逆ビデオ符号化装置
２，３  段階的可逆ビデオ復号装置
１１  初期化部
１２  直交変換部
１３  量子化部
１４  存在空間決定部
１５  係数逐次符号化部
１６  係数一括符号化部
１７  終了判定部
２１  初期化復号部
２２  存在空間決定部
２３  係数逐次復号部
２４，２８  係数一括復号部
２５  Ｕｂｕｆ［］
２６  終了判定部
２７  汎用可変長復号部
１６１，２４１，２８１  多重ループ開始部
１６２，２４２，２８２  逆直交変換部
１６３，２４３，２８３  予測信号加算部
１６４，２４４，２８４  内部変数更新部
１６５，２４５，２８５  多重ループ終了判定部
１６６  通し番号符号化部
２４６  通し番号復号部
２４７，２８６  原信号出力部
【発明を実施するための最良の形態】
【００２８】
以下，図面を参照して本発明の実施形態及び実施例を詳細に説明する。ただし，本発明は以下に説明する実施形態及び実施例に限定されるものではなく，例えばこれらを適宜組み合わせたものも本発明の範囲に属する。【００２９】
本発明の説明の前提として，Ｈ．２６４方式の直交変換について説明する。
〔Ｈ．２６４方式の直交変換〕
Ｈ．２６４標準においては，フレーム内あるいはフレーム間で画素値を予測した後，縦横４画素ずつの小ブロック毎に，残差の直交変換・係数の量子化を行う。【００３０】
原信号の小ブロックを４×４行列Ｕで，フレーム内あるいはフレーム間で該ブロックを予測した信号を同じく４×４行列Ｙで表す。そして予測残差信号（４×４行列Ｒ）を
Ｒ＝Ｕ−Ｙ                                                    （１）
とする。これらはいずれも，要素がすべて整数である。ここでは残差信号の各要素を【００３１】
【数１】
0004767860.tif 000002
のように表記することとする。【００３２】
これに次のような直交変換を施す。【００３３】
Ｘ＝ＴＲＴt                                                   （３）
ここで【００３４】
【数２】
0004767860.tif 000003
である。また，Ｔt は行列Ｔの転置行列を表す。【００３５】
さらに，Ｘの各要素を【００３６】
【数３】
0004767860.tif 000004
とする。【００３７】
ここでＴは直交変換ではあるが正規直交変換ではないことに注意する。正規直交変換の行列式は常に１であるが，Ｔの行列式（ｄｅｔＴ）は４０であるので，任意の１６次元領域の体積はＴによる写像後４０倍になる。式（３）はＴによりＲの４行および４列に変換を施すため，変換後の係数Ｘは，変換前（残差信号Ｒ）に比べ
４０4+4 ＝ 6,553,600,000,000倍                                （６）
に引き伸ばされた，極めて疎な空間内に写像される。Ｈ．２６４における直交変換係数は整数となるが，係数空間の格子点は，ほとんどが残差信号として不適（つまり後の式（８）により逆変換しても整数値が得られない）であるということになる。仮に係数空間の格子点をすべて対象とし，原信号に対応する格子点を符号化すると，上記の数の２を底とする対数を画素数（４＊４＝１６）で除した
ｌｏｇ2 （４０4+4 ）／１６＝２．６６［ｂｉｔ］                  （７）
が，１画素あたり余分に必要になる。対象としている信号が（１カラーコンポーネントあたり）８ｂｉｔであることを考えると，２．６６ｂｉｔの増加は実用性を著しく阻害していると言わざるを得ない。【００３８】
Ｈ．２６４方式では，前述のように大きく拡大されたＸの各要素を，粗く（比較的広い幅で）量子化することにより，この拡大分を補償している。【００３９】
もし量子化がなければ，逆変換
Ｒ＝Ｔ-1Ｘ（Ｔt ）-1                                            （８）
により残差信号は完全に元に戻り，
Ｕ＝Ｒ＋Ｙ                                                    （９）
により原画素値の４×４行列Ｕが再現できるところであるが，実際のＨ．２６４符号化においては量子化を施された係数が復号側で逆量子化されると，一般に，元の値には近いが完全に同じではない値が復元されることになる。こうしてＸは伝送後，異なる値Ｘ′（≠Ｘ）となり，これを式（８）により逆変換しても
Ｒ≠Ｒ′＝Ｔ-1Ｘ′（Ｔt ）-1
となる。復号側ではＹは符号化側と同一のものを持つことができるが，Ｒが再現できないため原画素値Ｕ＝Ｒ＋Ｙも再現できない。【００４０】
したがってＵを完全再現するためには，Ｘの量子化で失われた情報を補うような付加情報を，別途伝送する必要がある。【００４１】
［実施形態１］
本実施形態は本発明の第１の態様に対応するものである。
実施形態１に係る段階的可逆ビデオ符号化方法は，この量子化で失われた情報を，以下のように効率よく符号化する。【００４２】
例えば，式（５）における係数Ａの値は量子化され伝送されるため，復号側では量子化前のＡの値は正確にはわからない。ここでは符号化側の量子化方法は既知としており，Ａがとり得る範囲はわかる。すなわち，Ｈ．２６４ソフトウェアＪＭ（参考文献： http://bs.hhi.de/〜suehring/tml/,“JM Reference Software version 8.4 ”, Jul 2004）の量子化方法を例にとると，
｜ levelA ｜＝（｜Ａ｜＊qcA ＋qpconst ）＞＞qbits   （１０）
のようにして量子化された値 levelA を求める。ここで“＞＞”は右ビットシフト演算子である。なお levelA の正負はＡのそれに一致させる。ここでqcA はＡの位置，量子化パラメータに対応してＪＭが決める整数，qpconst は符号化モード，量子化パラメータに対応してＪＭが決める整数，qbits は量子化パラメータに対応して，ＪＭが決める整数である。【００４３】
復号側では量子化パラメータや符号化モードおよび量子化方法を知ることができるので，符号化側と共通の levelA ，qpconst ，qbits を持つことができる。 levelA の値からまず
ｘ＝ ｜levelA｜ ＜＜qbits 
ｙ＝ｘ＋（１＜＜qbits ）−１
mmin＝（ｘ−qpconst ＋qcA −１）／qcA 
mmax＝（ｙ−qpconst ）／qcA 
を求める。ここで“＜＜”は左ビットシフト演算子，“／”は小数点以下を切捨てる整数除算である。ついで上下限Ａmin ，Ａmax が以下のように求められる。【００４４】
【数４】
0004767860.tif 000005
こうして，量子化前の係数がとり得る上下限値
下限値  Ａmin ，Ｂmin ，Ｃmin ，... ，Ｐmin                       （１３）
上限値  Ａmax ，Ｂmax ，Ｃmax ，... ，Ｐmax                       （１４）
を得ることができる。これらの数値範囲が本発明の第１の態様の「変換係数の存在空間」に相当する。【００４５】
この上下限を元に，下記のアルゴリズム１のような１６重ループ（本発明の第１の態様の「列挙するステップ」に相当）を回すことにより，直交変換後の空間において妥当なものをもれなくすべて列挙することができる。ここで，以下の処理が本発明の第１の態様の「妥当性判断」に相当する。
・「Ｒの全要素が整数である」
・「Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている」
上記の妥当性判断の結果，列挙された格子点の総数はcases ，残差信号の直交変換係数に一致する格子点の「通し番号」は indexとして与えられる。【００４６】
〔アルゴリズム１〕
１． index←０
２． cases←０
３． for  Ａ←Ａmin   to  Ａmax 
４． for  Ｂ←Ｂmin   to  Ｂmax 
５． for  Ｃ←Ｃmin   to  Ｃmax 
６． for  Ｄ←Ｄmin   to  Ｄmax 
７． for  Ｅ←Ｅmin   to  Ｅmax 
８． for  Ｆ←Ｆmin   to  Ｆmax 
９． for  Ｇ←Ｇmin   to  Ｇmax 
10.  for  Ｈ←Ｈmin   to  Ｈmax 
11． for  Ｉ←Ｉmin   to  Ｉmax 
12． for  Ｊ←Ｊmin   to  Ｊmax 
13.  for  Ｋ←Ｋmin   to  Ｋmax 
14． for  Ｌ←Ｌmin   to  Ｌmax 
15． for  Ｍ←Ｍmin   to  Ｍmax 
16． for  Ｎ←Ｎmin   to  Ｎmax 
17． for  Ｏ←Ｏmin   to  Ｏmax 
18． for  Ｐ←Ｐmin   to  Ｐmax 
19．  begin 
20．  Ｒ←Ｔ-1Ｘ（Ｔt ）-1（＊式（８）＊）
21．  if  Ｒの全要素が整数である
22．    then  （＊Ａ〜Ｐが整数信号の直交変換の結果として妥当＊）
23．      Ｕ←Ｒ＋Ｙ（＊式（９）＊）
24．        if  Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている
25．          then （＊Ａ〜Ｐが残差信号の直交変換の結果として妥当＊）
26．            if  Ｘが原変換係数に一致する
27．              then  index ←cases 
28．            endif 
29．            cases ←cases ＋１
30．        endif 
31．  endif 
32．  end 
33． cases分の情報量を用いてindex を符号化
［実施形態２］：変換係数間の整数的値関係を利用した高速化
本実施形態は本発明の第２の態様に対応するものである。
実施形態１では，１６重のループをそれぞれ１間隔で回すため，総ループ回数は非常に多くなる。しかし，実施形態２では，直交変換係数間に存在する整数的関係を用いることで，符号化効率は同じままで，ループ回数を大幅に削減することができる。【００４７】
まず４×４行列Ｒを，上の行から下の行へ順に並べなおした１６次元の行ベクトル↑ｘにより
↑ｘ＝［ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｉ，ｊ，ｋ，ｌ，ｍ，ｎ，ｏ，ｐ］
（１５）
のように表現することとする。【００４８】
式（３）をこの１６次元ベクトルを用いて書き換えると，
Ａ＝↑ｔA ↑ｘt 
Ｂ＝↑ｔB ↑ｘt 
・・・
Ｐ＝↑ｔP ↑ｘt 
のように書くことができる。
ここで
↑ｔA ＝［1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ］
↑ｔB ＝［2,1,-1,-2,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2 ］
↑ｔC ＝［1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1 ］
↑ｔD ＝［1,-2,2,-1,1,-2,2,-1,1,-2,2,-1,1,-2,2,-1 ］
↑ｔE ＝［2,2,2,2,1,1,1,1,-1,-1,-1,-1,-2,-2,-2,-2 ］
↑ｔF ＝［4,2,-2,-4,2,1,-1,-2,-2,-1,1,2,-4,-2,2,4 ］
↑ｔG ＝［2,-2,-2,2,1,-1,-1,1,-1,1,1,-1,-2,2,2,-2 ］
↑ｔH ＝［2,-4,4,-2,1,-2,2,-1,-1,2,-2,1,-2,4,-4,2 ］
↑ｔI ＝［1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1 ］
↑ｔJ ＝［2,1,-1,-2,-2,-1,1,2,-2,-1,1,2,2,1,-1,-2 ］
↑ｔK ＝［1,-1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1,1 ］
↑ｔL ＝［1,-2,2,-1,-1,2,-2,1,-1,2,-2,1,1,-2,2,-1 ］
↑ｔM ＝［1,1,1,1,-2,-2,-2,-2,2,2,2,2,-1,-1,-1,-1 ］
↑ｔN ＝［2,1,-1,-2,-4,-2,2,4,4,2,-2,-4,-2,-1,1,2 ］
↑ｔO ＝［1,-1,-1,1,-2,2,2,-2,2,-2,-2,2,-1,1,1,-1 ］
↑ｔP ＝［1,-2,2,-1,-2,4,-4,2,2,-4,4,-2,-1,2,-2,1 ］
である。【００４９】
ここで↑ｔA ＋↑ｔC を計算すると
↑ｔA ＋↑ｔC ＝［2,0,0,2,2,0,0,2,2,0,0,2,2,0,0,2]
＝２［1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1]
となる。したがって，
Ａ＋Ｃ＝（↑ｔA ＋↑ｔC ）↑ｘt 
＝２［1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1 ］↑ｘt 
であるので，任意の整数要素ベクトル↑ｘに対し，Ａ＋Ｃは常に偶数となる。【００５０】
つまりＡの値がわかっている場合，Ｃの下位第１ビットはＡのそれと同じとわかるので，Ｃの存在範囲は，
Ｃmin ＋（（Ｃmin ＋Ａ）＆１）≦Ｃ≦Ｃmax −（（Ｃmax ＋Ａ）＆１）
（１６）
であり，この区間中に間隔２でまばらに存在していることになる。ここで‘＆’はビットＡＮＤ演算子である。同じ位置関係である，
ＥとＧ
ＩとＫ
ＭとＯ
も同様である。【００５１】
同様に縦方向においても，Ａ＋Ｉも偶数であることから，Ａの値がわかっている場合，Ｉが間隔２で存在する範囲がわかる。同じ位置関係である，
ＢとＪ
ＣとＫ
ＤとＬ
も同様である。【００５２】
次に，任意の整数要素ベクトル↑ｘに対し，Ｂ＋（Ｃ＞＞１）＋（Ａ＞＞１）は常に偶数になる。これは，↑ｘの各要素を０，１，２，３と変化させたすべての場合について確認することで証明される。つまりＡとＣの値がわかっている場合，Ｂの下位第１ビットは（Ｃ＞＞１）＋（Ａ＞＞１）のそれと同じとわかるので，上記と同様にＢの存在範囲がわかり，そこに間隔２で存在することになる。同じ位置関係，および縦に同じ位置関係である，
Ｆと（Ｅ＞＞１）＋（Ｇ＞＞１）
Ｊと（Ｉ＞＞１）＋（Ｋ＞＞１）
Ｎと（Ｍ＞＞１）＋（Ｏ＞＞１）
Ｅと（Ａ＞＞１）＋（Ｉ＞＞１）
Ｆと（Ｂ＞＞１）＋（Ｊ＞＞１）
Ｇと（Ｃ＞＞１）＋（Ｋ＞＞１）
Ｈと（Ｄ＞＞１）＋（Ｌ＞＞１）
も同様である。【００５３】
次に
２．５（↑ｔA ＋↑ｔC ）＋２↑ｔB ＋↑ｔD 
＝［10,0,0,0,10,0,0,0,10,0,0,0,10,0,0,0 ］
＝１０［1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0 ］
となるので，任意の整数要素ベクトル↑ｘに対し，２Ｂ＋Ｄ＋２．５（Ａ＋Ｃ）は，常に１０の倍数になる。【００５４】
つまりＡ，Ｂ，Ｃの値がわかっている場合，Ｄの１０を法とする剰余（Ｄ  mod １０）と２．５（Ａ＋Ｃ）＋２Ｂのそれとの和は０か１０となるので，Ｄの存在範囲がわかり，その中に間隔１０で存在することになる。【００５５】
同じ位置関係や，縦に同じ位置関係，例えばＭとＡ，Ｅ，Ｉの間にも同様の関係がある。【００５６】
ここで用いた，ある整数ｙを法とする剰余演算子ｍｏｄ  ｙは，非負整数ｘ≧０に対してはＣ言語などの剰余演算子‘％’と同じで
ｘ  mod ｙ＝ｘ％ｙ
である。なお％演算子は，負の整数ｘ＜０に対しては，
ｘ％ｙ＝−（（−ｘ）％ｙ）
のように奇関数となるが，ここで用いるｍｏｄ  ｙは，結果が負にならないよう
ｘ  mod   ｙ＝（ｘ％ｙ）＋ｙ    （ｘ＜０の場合）
であるとする。例えば
（−１）  mod １０＝９
である。【００５７】
さらに，
↑ｔA ＋↑ｔC ＋↑ｔI ＋↑ｔK ＝［4,0,0,4,0,0,0,0,0,0,0,0,4,0,0,4]
＝４［1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1]
となる。したがって，任意の整数要素ベクトル↑ｘに対し，Ａ＋Ｃ＋Ｉ＋Ｋは常に４の倍数になる。【００５８】
つまりＡ，Ｃ，Ｉの値がわかっている場合，Ｋの４を法とする剰余と（Ａ＋Ｃ＋Ｉ）のそれとの和は０か４となるので，Ｋの存在範囲がわかり，そこに間隔４で存在することになる。【００５９】
さらに以下のような関係もある。【００６０】
↑ｔB−↑ｔJ ＋↑ｔE −↑ｔG ＝［0,4,4,0,4,4,0,-4,4,0,-4,-4,0,-4,-4,0］
＝４［0,1,1,0,1,1,0,-1,1,0,-1,-1,0,-1,-1,0］
２．５（↑ｔA ＋↑ｔC ＋↑ｔI ＋↑ｔK ）＋２（↑ｔE ＋↑ｔG ）＋↑ｔM ＋↑ｔO 
＝［20,0,0,20,0,0,0,0,0,0,0,0,0,0,0,0]
＝２０［1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0]
２．５（↑ｔA ＋↑ｔC ＋↑ｔI ＋↑ｔK ）＋２（↑ｔB ＋↑ｔJ ）＋↑ｔD ＋↑ｔL 
＝［20,0,0,0,0,0,0,0,0,0,0,0,20,0,0,0]
＝２０［1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
６．２５（↑ｔA ＋↑ｔC ＋↑ｔI ＋↑ｔK ）
＋５（↑ｔB ＋↑ｔE ＋↑ｔG ＋↑ｔJ ）
＋２．５（↑ｔD ＋↑ｔL ＋↑ｔM ＋↑ｔO ）
＋４↑ｔF ＋２（↑ｔH ＋↑ｔN ）＋↑ｔP 
＝［100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
＝１００［1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
つまり，
１）Ａの範囲を１間隔にループ
２）Ｃの範囲を２間隔にループ（Ａを利用）
３）Ｂの範囲を２間隔にループ（Ａ，Ｃを利用）
４）Ｄの範囲を１０間隔にループ（Ａ，Ｂ，Ｃを利用）
５）Ｉの範囲を２間隔にループ（Ａを利用）
６）Ｅの範囲を２間隔にループ（Ａ，Ｉを利用）
７）Ｍの範囲を１０間隔にループ（Ａ，Ｉ，Ｅを利用）
８）Ｋの範囲を４間隔にループ（Ａ，Ｃ，Ｉを利用）
９）Ｇの範囲を２間隔にループ（Ｅを利用）
１０）Ｆの範囲を２間隔にループ（Ｅ，Ｇを利用）
１１）Ｈの範囲を１０間隔にループ（Ｅ，Ｆ，Ｇを利用）
１２）Ｊの範囲を４間隔にループ（Ｂ，Ｅ，Ｇを利用）
１３）Ｌの範囲を２０間隔にループ（Ａ，Ｂ，Ｃ，Ｄ，Ｉ，Ｊ，Ｋを利用）
１４）Ｎの範囲を１０間隔にループ（Ｂ，Ｆ，Ｊを利用）
１５）Ｏの範囲を２０間隔にループ（Ａ，Ｃ，Ｅ，Ｇ，Ｉ，Ｋ，Ｍを利用）
１６）Ｐの範囲を１００間隔にループ（Ａ〜Ｏを利用）
のように多重ループを実行すれば，各ｆｏｒループを１間隔にループするのに比べ，総ループ回数を
１／(2*2*10*2*2*10*4*2*2*10*4*20*10*20*100) 
＝１／４０９，６００，０００，０００
に削減できる。【００６１】
具体的な手順はアルゴリズム２のようになる。ここでＣ′min ，Ｂ′min ，Ｄ′min は，
ｆ（ｘ，ｙ）＝（−ｘ） mod  ｙ                            （１７）
を用いて例えば次のようにして求める。【００６２】
Ｃ′min ＝Ｃmin ＋ｆ（Ｃmin ＋Ａ，２）                          （１８）
Ｂ′min ＝Ｂmin ＋ｆ（Ｂmin ＋（Ａ＞＞１）＋（Ｃ＞＞１），２）  （１９）
Ｄ′min ＝Ｄmin ＋ｆ（Ｄmin ＋２Ｂ＋２．５（Ａ＋Ｃ），１０）    （２０）
Ｅ′min 〜Ｐ′min も同様である。【００６３】
〔アルゴリズム２〕
１． index←０
２． cases←０
３． for  Ａ←Ａmin   to  Ａmax （＊ここだけは１間隔＊）
４． for  Ｃ←Ｃ′min   to  Ｃmax   step  ２
５． for  Ｂ←Ｂ′min   to  Ｂmax   step  ２
６． for  Ｄ←Ｄ′min   to  Ｄmax   step  １０
７． for  Ｉ←Ｉ′min   to  Ｉmax   step  ２
８． for  Ｅ←Ｅ′min   to  Ｅmax   step  ２
９． for  Ｍ←Ｍ′min   to  Ｍmax   step  １０
10． for  Ｋ←Ｋ′min   to  Ｋmax   step  ４
11． for  Ｇ←Ｇ′min   to  Ｇmax   step  ２
12． for  Ｆ←Ｆ′min   to  Ｆmax   step  ２
13． for  Ｈ←Ｈ′min   to  Ｈmax   step  １０
14． for  Ｊ←Ｊ′min   to  Ｊmax   step  ４
15． for  Ｌ←Ｌ′min   to  Ｌmax   step  ２０
16． for  Ｎ←Ｎ′min   to  Ｎmax   step  １０
17． for  Ｏ←Ｏ′min   to  Ｏmax   step  ２０
18． for  Ｐ←Ｐ′min   to  Ｐmax   step  １００
19．  begin 
20．  Ｒ←Ｔ-1Ｘ（Ｔt ）-1（＊式（８）＊）
21．  if  Ｒの全要素が整数である
22．    then  （＊Ａ〜Ｐが整数信号の直交変換の結果として妥当＊）
23．      Ｕ←Ｒ＋Ｙ（＊式（９）＊）
24．        if  Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている
25．          then （＊Ａ〜Ｐが残差信号の直交変換の結果として妥当＊）
26．            if  Ｘが原変換係数に一致する
27．              then  index ←cases 
28．            endif 
29．            cases ←cases ＋１
30．        endif 
31．  endif 
32．  end 
33． cases分の情報量を用いてindex を符号化
［実施形態３］：ループ多重度削減
本実施形態は本発明の第３の態様に対応するものである。
上記実施形態１および実施形態２におけるアルゴリズムは，いずれも１６重ループを用いるものであったが，実施形態３では，さらに高速化するためにループの多重度を減らすようにする。ここではＡ〜Ｐの１６係数のうち
Ａ  Ｂ  Ｃ  Ｄ
Ｅ  ・  ・  ・
Ｉ  ・  Ｋ  ・
Ｍ  ・  ・  ・
の８係数を別途伝送することでこれらのループを除くようにする。【００６４】
まず係数Ａの伝送を考える。例えば「付加情報」として
ＺA ＝Ａ−Ａmin 
を伝送すれば，復号側で
Ａ＝ＺA ＋Ａmin 
とすることでＡを復元することができる。【００６５】
なお，このときＡのとり得る場合の数が
Ａmax −Ａmin ＋１
であるので，ＺA を符号化するのに必要な情報量は，
ｌｏｇ2 （Ａmax −Ａmin ＋１）［ｂｉｔ］                        （２１）
となる。これは復号側でも共有できるので，ＺA を復号することは可能である。【００６６】
Ｂ〜ＰについてもこのＡのように伝送することも可能であるが，残差信号は直交変換後の空間内で非常に疎に分布していることから，符号量が大変に無駄になる。そこで例えばＢについては，Ａ，Ｃが既知の場合Ｂに関するループを２間隔にできたことから，
ＺB ＝（Ｂ−Ｂ′min ）／２
を伝送すれば，復号側で
Ｂ＝２ＺB ＋Ｂ′min 
によりＢを復元できる。ＺB を符号化するのに必要な情報量は，
ｌｏｇ2 （（Ｂmax −Ｂ′min ）／２＋１）［ｂｉｔ］
となる。Ｃ〜Ｋについても同様である。したがって，
１）Ａの値をＺA により符号化
２）Ｃの範囲を約１／２に狭めたＺC で符号化（Ａを利用）
３）Ｂの範囲を約１／２に狭めたＺB で符号化（Ａ，Ｃを利用）
４）Ｄの範囲を約１／１０に狭めたＺD で符号化（Ａ，Ｂ，Ｃを利用）
５）Ｉの範囲を約１／２に狭めたＺI で符号化（Ａを利用）
６）Ｅの範囲を約１／２に狭めたＺE で符号化（Ａ，Ｉを利用）
７）Ｍの範囲を約１／１０に狭めたＺM で符号化（Ａ，Ｅ，Ｉを利用）
８）Ｋの範囲を約１／４に狭めたＺK で符号化（Ａ，Ｃ，Ｉを利用）
のような手順を実行することで，Ｘのうち
Ａ  Ｂ  Ｃ  Ｄ
Ｅ  ・  ・  ・
Ｉ  ・  Ｋ  ・
Ｍ  ・  ・  ・
の８係数が無駄なく伝送される。このように範囲を狭められたＺx が，本発明の第３の態様の「該係数がとり得ない値を除いた情報」に相当する。【００６７】
残る８係数
・  ・  ・  ・
・  Ｆ  Ｇ  Ｈ
・  Ｊ  ・  Ｌ
・  Ｎ  Ｏ  Ｐ
については，実施形態１と同様，まとめて１つの数index で表現し伝送する。【００６８】
これらをまとめるとアルゴリズム３に示すような手順となる。【００６９】
〔アルゴリズム３〕
１．Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋをこの順で符号化する
２． index←０
３． cases←０
４． for  Ｇ←Ｇ′min   to  Ｇmax   step  ２
５． for  Ｆ←Ｆ′min   to  Ｆmax   step  ２
６． for  Ｈ←Ｈ′min   to  Ｈmax   step  １０
７． for  Ｊ←Ｊ′min   to  Ｊmax   step  ４
８． for  Ｌ←Ｌ′min   to  Ｌmax   step  ２０
９． for  Ｎ←Ｎ′min   to  Ｎmax   step  １０
10． for  Ｏ←Ｏ′min   to  Ｏmax   step  ２０
11． for  Ｐ←Ｐ′min   to  Ｐmax   step  １００
12．  begin 
13．  Ｒ←Ｔ-1Ｘ（Ｔt ）-1（＊式（８）＊）
14．  if  Ｒの全要素が整数である
15．    then  （＊Ａ〜Ｐが整数信号の直交変換の結果として妥当＊）
16．      Ｕ←Ｒ＋Ｙ（＊式（９）＊）
17．      if  Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている
18．        then  （＊Ａ〜Ｐが残差信号の直交変換の結果として妥当＊）
19．          if  Ｘが原変換係数に一致する
20．            then  index ←cases 
21．          endif 
22．          cases ←cases ＋１
23．      endif 
24．  endif 
25．  end 
26． cases分の情報量を用いてindex を符号化
上記のようにして，１６重だったループが８重に削減され，処理がより高速になる。【００７０】
なおindex を記述するのに必要な情報量は
ｌｏｇ2 cases ［ｂｉｔ］                                    （２２）
である。これは復号側が付加情報なしに持つことができ，かつindex の復号に必要な情報である。【００７１】
［実施形態４］：対応する復号
本実施形態は本発明の第７の態様に対応するものである。
ここでは，上記実施形態３に係る符号化に対応する復号に係る実施形態について説明する。復号側でも符号化と同様のループを回すことにより，ループ最内部の妥当性判断の結果がindex ＋１回目に真となったときの，Ａ〜ＫおよびＧ〜Ｐの値が，原残差信号に対応する直交変換係数となることを知る。【００７２】
index の符号化時にこれがどれだけの情報量を持つかに応じて符号化した場合，index の復号においては，まずこれがどれだけの情報量をもつかを知らなければならない。そこで予めcases を得る必要がある。そのためにはやはり符号化と同様のループを実行することが必要である。【００７３】
例えば，メモリは余分に必要であるが，多重ループの二度実行を避けるためにアルゴリズム４のようにすることで多重ループを一度実行することによりcases ，index ，原信号をこの順で取得できる。ここでＵｂｕｆ［］は，４×４行列を要素とする配列であり，動的に確保あるいはあらかじめ十分な量を確保しておくこととする。【００７４】
〔アルゴリズム４〕
１．Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋをこの順で復号する
２． cases←０
３． for  Ｇ←Ｇ′min   to  Ｇmax   step  ２
４． for  Ｆ←Ｆ′min   to  Ｆmax   step  ２
５． for  Ｈ←Ｈ′min   to  Ｈmax   step  １０
６． for  Ｊ←Ｊ′min   to  Ｊmax   step  ４
７． for  Ｌ←Ｌ′min   to  Ｌmax   step  ２０
８． for  Ｎ←Ｎ′min   to  Ｎmax   step  １０
９． for  Ｏ←Ｏ′min   to  Ｏmax   step  ２０
10． for  Ｐ←Ｐ′min   to  Ｐmax   step  １００
11．  begin 
12．  Ｒ←Ｔ-1Ｘ（Ｔt ）-1（＊式（８）＊）
13．  if  Ｒの全要素が整数である
14．    then  （＊Ａ〜Ｐが整数信号の直交変換の結果として妥当＊）
15．      Ｕ←Ｒ＋Ｙ（＊式（９）＊）
16．      if  Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている
17．        then  （＊Ａ〜Ｐが残差信号の直交変換の結果として妥当＊）
18．          Ｕｂｕｆ［cases ］←Ｕ
19．          cases ←cases ＋１
20．      endif 
21．  endif 
22．  end 
23． cases分の情報量を用いてindex を復号
24．Ｕ←Ｕｂｕｆ［index ］（＊原信号値＊）
［実施形態５］：高速な符号量推定
本実施形態は本発明の第６の態様に対応するものである。
Ｈ．２６４方式では，フレーム内予測においては複数のモードや種類，フレーム間予測においては複数のブロックサイズなど，さまざまな予測モードを選択することができる。予測残差信号Ｒも予測モードにより変化するため，符号量対歪みの意味で最適な予測モードを選択する場合，モード毎の符号量を適切に見積もる必要が生じる。【００７５】
可逆符号化の場合，歪みは常に零であるので，符号量（Ｈ．２６４準拠の符号量と，付加情報の符号量の和）を最小化することだけに注意すればよい。【００７６】
アルゴリズム１，アルゴリズム２，アルゴリズム３に示したような多重ループを実行すれば当然正確な付加情報符号量を見積もることが可能であるが，より高速な符号量推定法があれば，複数のモードを比較するのに都合がよい。【００７７】
実施形態５は，多重ループを実行することなく，付加情報の符号量を見積もることを目的としている。【００７８】
まず実施形態１，実施形態２のように特定の変換係数を事前に伝送しない場合を説明する。事前に量子化前の係数がとり得る上下限値（式（１３），式（１４））を求めておく。これを元に本発明の第６の態様の「変換係数の存在空間」の体積Ｖを次のように求める：【００７９】
【数５】
0004767860.tif 000006
このＶが存在空間中の格子点の数を近似していると考えられる。この中のすべてが原残差信号に対応しているわけではなく，空間は式（６）に示したように拡大されているため，Ｖをこの倍率で除したＶ0 
Ｖ0 ＝Ｖ／４０4+4                                             （２４）
が格子点の総数を近似していると考えられる。したがって，１画素あたりの付加情報符号量ｌ0 は，
ｌ0 ＝ｌｏｇ2 Ｖ0 ／１６
＝ｌｏｇ2 （Ｖ／４０4+4 ）／１６
＝ｌｏｇ2 Ｖ／１６−２．６６［ｂｉｔ］                  （２５）
となる。【００８０】
また実施形態３のように特定の変換係数を事前に伝送する場合，それらの情報量ｌ1 は式（２１）と同様にして，【００８１】
【数６】
0004767860.tif 000007
ここでｘは
Ａ  Ｂ  Ｃ  Ｄ
Ｅ  ・  ・  ・
Ｉ  ・  Ｋ  ・
Ｍ  ・  ・  ・
の係数である。【００８２】
なおｎx はすでに述べた区間を狭める量であり，Ａ，... ，Ｍそれぞれについて
１  ２  ２  10
２  ・  ・  ・
２  ・  ４  ・
10  ・  ・  ・
である。Ａ′min ＝Ａmin ，Ｃ′min 〜Ｍ′min は，式（１８）などのようにして求める。【００８３】
また，残る８次元の「変換係数の存在空間」の体積Ｖ1 は次のようになる：【００８４】
【数７】
0004767860.tif 000008
ここでも，先のケース同様，原残差信号に対応する格子点はまばらに存在している。この空間の拡大率は，式（６）をｎx （ｘ∈Ａ，... ，Ｍ）をすべて掛け合わせたもので除した【００８５】
【数８】
0004767860.tif 000009
となっているはずである。そこで「格子点の総数」の情報量ｌ1 は一画素あたり
ｌ2 ＝ｌｏｇ2 （Ｖ1 ／ｎ0 ）／１６
＝ｌｏｇ2 Ｖ1 ／１６−１．８７［ｂｉｔ］                （２９）
となる。【００８６】
結局，一画素あたり付加情報量は両者の和
ｌ1 ＋ｌ2 ［ｂｉｔ］                                        （３０）
となる。【００８７】
式（２５），式（３０）のように見積もられた値を利用して，多重ループを用いる符号化を実行することなしに，符号量の推定を行うことができる。これを用いて符号量最小となるモードを選択し，選択されたモードについてだけ実際の符号化を行うことで，準最適な可逆符号化を実現することができる。【００８８】
［実施形態６］：妥当性判断の高速化
本実施形態は本発明の第４の態様に対応するものである。【００８９】
【数９】
0004767860.tif 000010
であるので，式（８）をそのまま計算する場合，浮動小数点演算が必要になる。しかしながら，これを２０倍すると，【００９０】
【数１０】
0004767860.tif 000011
となるので，Ｔ-1の代わりにＴ0 を用いることで，以下のように正しいＲの４００（＝２０＊２０）倍の値（Ｒ400 とする）を整数演算のみで得ることができる。【００９１】
Ｒ400 ＝４００Ｒ＝Ｔ0 ＸＴ0 t                                   （３３）
ここで【００９２】
【数１１】
0004767860.tif 000012
としたとき，式（３３）は式（３４）を８回縦横に施すことに分解できるが，この計算は具体的にアルゴリズム５のように高速に求められる。【００９３】
〔アルゴリズム５〕
１．ｘ0 ←５（ａ＋ｃ）
２．ｘ1 ←５（ａ−ｃ）
３．ｘ2 ←４ｂ＋２ｃ
４．ｘ3 ←２ｂ−４ｃ
５．ｓ←ｘ0 ＋ｘ2 
６．ｔ←ｘ1 ＋ｘ3 
７．ｕ←ｘ1 −ｘ3 
８．ｖ←ｘ0 −ｘ2 
ここで，５ｘは（ｘ＜＜２）＋ｘのようにシフト１回，加算１回で求められるし，４ｂ＋２ｃなども（ｂ＜＜２）＋（ｃ＜＜１）としてシフト２回，加算１回で求められるため，式（３３）の計算に乗算は一切不要である。【００９４】
ここで，前述した「妥当性判断」の一つである，「Ｒの全要素が整数であること」は，「Ｒ400 の全要素が４００の倍数であること」と等価である。これを実行する場合，４００で除した余りが０であることを確認するために，除算が必要となる。しかしながら，既にループを回す時点で２５の倍数である冗長性は除去されているので，１６の倍数であることを確認すればよい。これは「Ｒ400 の全要素の下位４ｂｉｔがすべて０であること」と等価である。これは「各要素と１５（二進数で１１１１）とのビットＡＮＤ演算の結果が０であること」と等価であり，除算を用いずに判断ができる。【００９５】
ここで，もう一つの「妥当性判断」である，「Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっていること」も修正が必要になる。式（９）の両辺に４００を乗ずると
Ｕ400 ＝４００Ｕ＝Ｒ400 ＋Ｙ400                                 （３５）
となる。ここでＹ400 は予測信号Ｙを４００倍したものであり，これを予め用意しておき（２５６要素のルックアップテーブルを用いれば４００倍の乗算は不要である），Ｒ400 との和を求めれば，原信号の４００倍が得られる。ここで２５５＊４００＝１０２，０００なので「Ｕ400 の全要素が［０〜１０２０００］におさまっていること」を確認すればよい。【００９６】
この手順をまとめるとアルゴリズム６のようになる。【００９７】
〔アルゴリズム６〕
１． index←０
２． cases←０
３． for  Ａ←Ａmin   to  Ａmax （＊ここだけは１間隔＊）
４． for  Ｃ←Ｃ′min   to  Ｃmax   step  ２
５． for  Ｂ←Ｂ′min   to  Ｂmax   step  ２
６． for  Ｄ←Ｄ′min   to  Ｄmax   step  １０
７． for  Ｉ←Ｉ′min   to  Ｉmax   step  ２
８． for  Ｅ←Ｅ′min   to  Ｅmax   step  ２
９． for  Ｍ←Ｍ′min   to  Ｍmax   step  １０
10． for  Ｋ←Ｋ′min   to  Ｋmax   step  ４
11． for  Ｇ←Ｇ′min   to  Ｇmax   step  ２
12． for  Ｆ←Ｆ′min   to  Ｆmax   step  ２
13． for  Ｈ←Ｈ′min   to  Ｈmax   step  １０
14． for  Ｊ←Ｊ′min   to  Ｊmax   step  ４
15． for  Ｌ←Ｌ′min   to  Ｌmax   step  ２０
16． for  Ｎ←Ｎ′min   to  Ｎmax   step  １０
17． for  Ｏ←Ｏ′min   to  Ｏmax   step  ２０
18． for  Ｐ←Ｐ′min   to  Ｐmax   step  １００
19．  begin 
20．  Ｒ400 ←Ｔ0 ＸＴ0 t （＊式（３３）＊）
21．  if  Ｒ400 の全要素の下位４ｂｉｔが０である
22．    then  （＊Ａ〜Ｐが整数信号の直交変換の結果として妥当＊）
23．      Ｕ400 ←Ｒ400 ＋Ｙ400 （＊式（３５）＊）
24．      if  Ｕ400 の全要素が［０〜１０２０００］におさまっている
25．        then  （＊Ａ〜Ｐが残差信号の直交変換の結果として妥当＊）
26．          if  Ｘが原変換係数に一致する
27．            then  index ←cases 
28．          endif 
29．          cases ←cases ＋１
30．      endif 
31．  endif 
32．  end 
33． cases分の情報量を用いてindex を符号化
［実施形態７］：凸性を利用した処理高速化
本実施形態は本発明の第５の態様に対応するものである。
残差信号【００９８】
【数１２】
0004767860.tif 000013
の存在空間を考える。左上の要素ａは，この位置の予測画素信号をＹa とすると，
０≦ａ＋Ｙa ≦２５５                                        （３６）
−Ｙa ≦ａ≦２５５−Ｙa                                     （３７）
という存在範囲を満たしている。ｂ〜ｐも同様に上限・下限が定まっている。１６次元空間で考えると，Ｒの存在範囲Ωは凸多面体（超直方体）の形状をしていることになる。【００９９】
Ｒの存在範囲を式（３）により変換した先の，やはり１６次元の空間でも，回転・拡大を経ているが凸多面体であることには変わりがない。変換係数Ｘはこの変換先の空間内に存在しているが，各要素の上下限は式（１３），式（１４）のように求まっているため，Ｘの存在範囲Ψもやはり凸多面体（超直方体）となっている。したがって，ΩとΨの交わりΩ∩Ψも，やはり凸多面体になる。これらの関係を簡単のため２次元で図示すると図１のようになる。【０１００】
図１のΨ領域を拡大したものが図２である。格子点を列挙するステップにおいて多重ループを回す際，この図に示すように，Ａ＝Ａ0 でＢを変化させていった場合，妥当性判断の第二番（Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている）は５個目の格子点（灰色）において「真」→「偽」となる。存在範囲Ω∩Ψが凸であるため，６個目以降は偽であることが確定するので，Ｂのループを中止し，次の，Ａ＝Ａ1 としてＢのループを再開する。ここでは６個目の格子点（灰色）において「真」→「偽」となるためループを中止する。このようにして，図の破線で囲った部分についての判断を中止することができる。【０１０１】
これらをまとめるとアルゴリズム７のようになる。全係数について妥当性判断中止を行う手順を示すと字下げが深くなりすぎるため，ここでは簡単のため多重ループ最内部の３変数（Ｎ，Ｏ，Ｐ）について妥当性判断を中止する手順を示しているが，一般性を示すには十分である。【０１０２】
〔アルゴリズム７〕
１． index←０
２． cases←０
３． for  Ａ←Ａmin   to  Ａmax 
４． for  Ｂ←Ｂmin   to  Ｂmax 
５． for  Ｃ←Ｃmin   to  Ｃmax 
６． for  Ｄ←Ｄmin   to  Ｄmax 
７． for  Ｅ←Ｅmin   to  Ｅmax 
８． for  Ｆ←Ｆmin   to  Ｆmax 
９． for  Ｇ←Ｇmin   to  Ｇmax 
10． for  Ｈ←Ｈmin   to  Ｈmax 
11． for  Ｉ←Ｉmin   to  Ｉmax 
12． for  Ｊ←Ｊmin   to  Ｊmax 
13． for  Ｋ←Ｋmin   to  Ｋmax 
14． for  Ｌ←Ｌmin   to  Ｌmax 
15． for  Ｍ←Ｍmin   to  Ｍmax 
16．   begin
17．   CheckＮ←偽
18．   for  Ｎ←Ｎmin   to  Ｎmax 
19．     begin
20．     CheckＯ←偽
21．     for  Ｏ←Ｏmin   to  Ｏmax 
22．       begin
23．       CheckＰ←偽
24．       for  Ｐ←Ｐmin   to  Ｐmax 
25．         begin
26．          Ｒ←Ｔ-1Ｘ（Ｔt ）-1（＊式（８）＊）
27．          if  Ｒの全要素が整数である
28．            then  （＊Ａ〜Ｐが整数信号の直交変換の結果として妥当＊）
29．              Ｕ←Ｒ＋Ｙ（＊式（９）＊）
30．              if  Ｕの全要素が８ｂｉｔ整数の範囲［０〜２５５］におさまっている
31．                then  （＊Ａ〜Ｐが残差信号の直交変換の結果として妥当＊）
32．                  if  Ｘが原変換係数に一致する
33．                    then  index ←cases 
34．                  endif 
35．                  Check Ｎ←真
36．                  Check Ｏ←真
37．                  Check Ｐ←真
38．                  cases ←cases ＋１
39．                else if  CheckＰ＝真
40．                  then  goto  21（＊真→偽に変わった＊）
41．              endif 
42．          endif 
43．         end
44．         if  CheckＰ＝偽  and  CheckＯ＝真
45．            then  goto  18（＊真→偽に変わった＊）
46．         endif
47．      end 
48．      if   CheckＰ＝偽 and CheckＯ＝偽 and CheckＮ＝真
49．            then  goto  15（＊真→偽に変わった＊）
50．      endif 
51．     end
52．   end
53． cases分の情報量を用いてindex を符号化
［実施形態８］：符号化装置の構成例
本実施形態は本発明の第８の態様に対応するものである。
上述した本発明を実現する装置構成について以下に説明する。図３は，本発明の段階的可逆ビデオ符号化装置の構成例を示す図である。段階的可逆ビデオ符号化装置１は，Ｈ．２６４標準符号化方式に基づき各ブロック毎に原画像信号と，フレーム内符号化における空間予測またはフレーム間符号化における時間予測による予測画像信号との残差信号Ｒorigを算出する部分（図３では図示省略）の他に，cases ，index を初期化する初期化部１１，残差信号Ｒorigを直交変換する直交変換部１２，直交変換部１２の出力を量子化する量子化部１３，上下限値情報Ａmin ，Ａmax ，... ，Ｐmin ，Ｐmax を求める存在空間決定部１４，逐次符号化伝送する係数を符号化処理する係数逐次符号化部１５，係数を一括して代表する数index を求めて符号化する係数一括符号化部１６，画像内のすべてのブロックを符号化したかを判定する終了判定部１７を備える。【０１０３】
係数一括符号化部１６は，各係数の上下限内ですべての係数の組合せを列挙する多重ループ開始部１６１，既に符号化伝送した係数および現在ループ中の係数により定まる４×４行列Ｘを逆直交変換する逆直交変換部１６２，行列和Ｕ＝Ｒ＋Ｙを求める予測信号加算部１６３，index とcases を更新処理する内部変数更新部１６４，各係数の上下限内ですべての係数の組合せが調べられたかを判定する多重ループ終了判定部１６５，index を符号化する通し番号符号化部１６６から構成される。【０１０４】
図３に示す段階的可逆ビデオ符号化装置１は，以下のように動作する。まず初期化部１１において「格子点の総数」cases ，残差信号の直交変換係数に一致する格子点の「通し番号」index をそれぞれ０に初期化する。【０１０５】
次いで直交変換部１２において，残差信号Ｒorigに直交変換を施しＸorigを得る。これを量子化部１３において，量子化パラメータ情報を用いて量子化する。この量子化情報から，存在空間決定部１４において，上下限値情報Ａmin ，Ａmax ，... ，Ｐmin ，Ｐmax を求める。【０１０６】
次に，係数逐次符号化部１５で，逐次符号化伝送する係数を符号化処理する。例えば上述した実施形態１の場合０個，実施形態３の場合Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋの８個である。【０１０７】
次いで，係数一括符号化部１６において，残る係数を一括して代表する数index を求めて符号化する。すなわち，係数一括符号化部１６中の多重ループ開始部１６１は，残る係数（例えば実施形態１の場合Ａ〜Ｐの１６個，実施形態３の場合Ｇ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，Ｏ，Ｐの８個）についてのそれぞれの上下限でとり得る範囲すべてを列挙する。その際，実施形態２のように，係数間の整数的値関係を利用して，とり得ない係数の組合せをとばして列挙してもよい。【０１０８】
逆直交変換部１６２では，既に符号化伝送した係数および現在ループ中の係数Ａ〜Ｐにより定まる４×４行列Ｘを逆直交変換し，Ｒとする。ここでもしＲに整数でない値が存在すれば，多重ループ終了判定部１６５の処理に進む。【０１０９】
次に予測信号加算部１６３において，行列和Ｕ＝Ｒ＋Ｙを求める。ここでもしＵの要素に［０〜２５５］の範囲に収まっていない値が存在すれば，多重ループ終了判定部１６５の処理に進む。【０１１０】
次に内部変数更新部１６４において，ＸとＸorigが一致する場合，index にcases を代入する処理を行う。また，cases に１を加算する。【０１１１】
多重ループ終了判定部１６５では，上下限内ですべての係数の組合せが調べられたかを判定し，まだであれば多重ループ開始部１６１の処理へ戻る。済みであれば，通し番号符号化部１６６で，cases 分の情報量を用いてindex を符号化する。【０１１２】
次いで，終了判定部１７において，画像内のすべてのブロックを符号化したかを判定し，済んでいなければ次のブロックに移って初期化部１１による処理を再開する。済みであれば，符号化を終了する。【０１１３】
〔index の符号化に汎用可変長符号化を用いる場合〕
本発明においては，例えば，汎用可変長符号（参考文献：Y.Itoh, N-M Cheung:"Universal variable length code for DCT coding", IEEE Proc. Int. Conf. Image Processing, Vol.1, pp.940-943, 2000 ）等を用いることにより，cases を使わずにindex を符号化してもよい。この場合，内部変数更新部１６４においてＸとＸorigが一致すれば，その時のcases の値を汎用可変長符号化し，すぐさま係数一括符号化部１６による処理を終了する。【０１１４】
［実施形態９］：復号装置の構成例
本実施形態は本発明の第９の態様に対応するものである。
図４は，本発明の段階的可逆ビデオ復号装置の構成例を示す図である。段階的可逆ビデオ復号装置２は，量子化パラメータ・量子化係数を復号するとともに予測信号Ｙの生成を行う初期化復号部２１，上下限値情報Ａmin ，Ａmax ，... ，Ｐmin ，Ｐmax を求める存在空間決定部２２，逐次符号化伝送された係数を復号する係数逐次復号部２３，係数を一括して代表する数index を復号する係数一括復号部２４，Ｕの値を記憶する配列記憶であるＵｂｕｆ［］２５，および画像内のすべてのブロックを復号したかを判定する終了判定部２６から構成される。【０１１５】
係数一括復号部２４は，各係数の上下限内ですべての係数の組合せを列挙する多重ループ開始部２４１，既に復号された係数および現在ループ中の係数により定まる４×４行列Ｘを逆直交変換する逆直交変換部２４２，行列和Ｕ＝Ｒ＋Ｙを求める予測信号加算部２４３，Ｕｂｕｆ［］２５のcases 番地にＵを格納するとともにcases を更新する内部変数更新部２４４，各係数の上下限内ですべての係数の組合せが調べられたかを判定する多重ループ終了判定部２４５，index を復号する通し番号復号部２４６，Ｕｂｕｆ［］２５のindex 番目の値を原画像信号として出力する原信号出力部２４７から構成される。【０１１６】
図４に示す段階的可逆ビデオ復号装置２は，以下のように動作する。まず初期化復号部２１において，格子点の総数cases を０に初期化し，量子化パラメータ・量子化係数の復号，予測信号Ｙの生成を行う。【０１１７】
量子化パラメータと量子化係数とに基づき，存在空間決定部２２において，上下限値情報Ａmin ，Ａmax ，... ，Ｐmin ，Ｐmax を求める。【０１１８】
次に，係数逐次復号部２３で，逐次符号化伝送された係数を復号する。例えば上記実施形態１の場合０個，実施形態３の場合Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋの８個をこの順に復号する。【０１１９】
次いで，係数一括復号部２４において，残る係数を一括して代表する数index を復号し可逆復元を行う。すなわち，係数一括復号部２４中の多重ループ開始部２４１は，残る係数（例えば実施形態１の場合Ａ〜Ｐの１６個，実施形態３の場合Ｇ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，Ｏ，Ｐの８個）についてのそれぞれの上下限でとり得る範囲すべてを列挙する。【０１２０】
その際，実施形態２のように，係数間の整数的値関係を利用して，とり得ない係数の組合せをとばして列挙してもよい。ただし，とり得ない係数の組合せをとばして列挙する手順は，対応する符号化装置と全く同一の手順とする。【０１２１】
逆直交変換部２４２では，既に復号された係数および現在ループ中の係数Ａ〜Ｐにより定まる４×４行列Ｘを逆直交変換し，Ｒとする。ここでもしＲに整数でない値が存在すれば，多重ループ終了判定部２４５の処理に進む。【０１２２】
次に，予測信号加算部２４３において，行列和Ｕ＝Ｒ＋Ｙを求める。ここでもしＵの要素に［０〜２５５］の範囲に収まっていない値が存在すれば，多重ループ終了判定部２４５の処理に進む。【０１２３】
次に，内部変数更新部２４４において，予め確保しておいたＵｂｕｆ［］２５のcases 番地にＵを格納し，cases に１を加算する。【０１２４】
多重ループ終了判定部２４５では，上下限内ですべての係数の組合せが調べられたかを判定し，まだであれば多重ループ開始部２４１による処理へ戻る。済みであれば，通し番号復号部２４６で，cases 分の情報量を用いてindex を復号する。【０１２５】
次いで原信号出力部２４７で，Ｕｂｕｆ［］２５のindex 番目の値を取り出し，原画像信号として出力する。【０１２６】
次いで，終了判定部２６において，画像内のすべてのブロックを復号したかを判定し，済んでいなければ次のブロックに移って初期化復号部２１による処理を再開する。済みであれば，復号を終了する。【０１２７】
［index の符号化に汎用可変長符号化を用いる場合の復号装置の構成例］
本発明において，index の符号化に汎用可変長符号を用いる場合，復号側は図５に示すような機能ブロック構成になる。図５に示す段階的可逆ビデオ復号装置３は，汎用可変長復号部２７においてindex を復号し，多重ループ終了判定部２８５では多重ループを回った回数がindex 回目であるかを判定し，そうであればすぐさま終了と判定し，そのときのＵの値を原信号として出力する。したがって，図４に示すＵｂｕｆ［］２５のような配列記憶は不要となる。他の部分の動作は，図４で説明した例と同様である。
【実施例１】
【０１２８】
実施形態３に対応する実施例１について説明する。この実施例１において核となる処理の概略は以下となる。【０１２９】
入力：量子化パラメータ，予測信号Ｙ，原残差信号Ｒorig
処理：原信号に対応する直交変換係数について，一部は圧縮情報化し，残りは，原信号となり得る組合せをもれなくすべて列挙した中の通し番号として表現する。【０１３０】
出力：係数の一部（Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋ）をそれぞれ表現する圧縮情報（ＺA 〜ＺK ），残りの係数（Ｇ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，Ｏ，Ｐ）をまとめて１数値で代表する符号（index ）
実施例１について，図６に示す処理フローを参照して説明する。まずステップＳ１０１にて量子化パラメータ，予測信号Ｙ，原残差信号Ｒorigを入力する。次いでステップＳ１０２においてindex ，cases をともに０に初期化する。【０１３１】
次いでステップＳ１０３においてＲorigに直交変換を施し原変換係数Ｘorigを得ると同時に，Ｘorigに量子化を施した量子化係数も求める。ステップＳ１０４では，これまでに得られた量子化パラメータ，量子化係数の情報から，Ｘorigを逆に推定した行列である，Ｘの各要素（Ａ〜Ｐ）の上下限を求める。これを元に，ステップＳ１０５において，Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋをこの順で圧縮符号化する。【０１３２】
続いて，Ｇ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，Ｏ，Ｐの８重ループ（ステップＳ１０６〜ステップＳ１１４）に入る。ステップＳ１０７にて，現在のＡ〜Ｐの値からなる４×４行列Ｘを式（８）により逆変換しＲを得る。【０１３３】
ステップＳ１０８にて，Ｒの要素がすべて整数であるかを確認し，偽であればステップＳ１１４へ，真であればステップＳ１０９に進み，Ｕ＝Ｒ＋Ｙを計算する。【０１３４】
次いでステップＳ１１０にて，Ｕの全要素が［０〜２５５］の範囲内であるかどうかを確認する。これが偽であればステップＳ１１４へ，真であればステップＳ１１１に進み，Ｘが原変換係数Ｘorigに等しいかを確認する。これが真であればステップＳ１１２にて，変数index に現在のcases の値を保存する。次いでステップＳ１１３にてcases の値を１加算しステップＳ１１４へ進む。【０１３５】
ステップＳ１１４では８重ループがすべて完了したかを確認し，偽である間はループ先頭のステップＳ１０６へ戻る。真であれば，ステップＳ１１５において，既に求められた cases（格子点の総数）分の情報量（式（２２））を用いてindex を符号化し，終了する。【０１３６】
ここでは，予め一部の係数（Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋの８係数）をまず別途符号化する（ステップＳ１０５）処理例を示したが，これを省略し，ステップＳ１０６からステップＳ１１４までを全１６係数の多重ループとすれば，全く同じ枠組で実施形態１または実施形態２に対応する実施例となる。
【実施例２】
【０１３７】
実施形態４に対応する実施例２について説明する。この実施例２において核となる処理の概略は以下となる。【０１３８】
入力：量子化パラメータ，予測信号Ｙ，量子化係数
処理：原信号に対応する直交変換係数について，一部（Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋ）は圧縮情報から，残り（Ｇ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，Ｏ，Ｐ）は，原信号となりうる組合せをもれなくすべて列挙した中の通し番号番目として復号する。
出力：原画像信号
実施例２について，図７に示す処理フローを参照して説明する。まずステップＳ２０１にてcases を０に初期化する。次いでステップＳ２０２において量子化パラメータ・量子化係数の復号，予測信号Ｙの生成を行う。これらはＨ．２６４基本情報ビットストリームから得られる情報である。【０１３９】
ステップＳ２０３では，これまでに得られた情報から，行列Ｘの各係数（Ａ〜Ｐ）の上下限を求める。これを元に，ステップＳ２０４において，Ａ，Ｃ，Ｂ，Ｄ，Ｉ，Ｅ，Ｍ，Ｋをこの順で復号する。【０１４０】
次いでＧ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，Ｏ，Ｐの８重ループ（ステップＳ２０５〜ステップＳ２１２）に入る。ステップＳ２０６にて，現在のＡ〜Ｐの値からなる４×４行列Ｘを第８式により逆変換しＲを得る。【０１４１】
ステップＳ２０７にて，Ｒの要素がすべて整数であるかを確認し，偽であればステップＳ２１２へ，真であればステップＳ２０８に進み，Ｕ＝Ｒ＋Ｙを計算する。【０１４２】
次いでステップＳ２０９にて，Ｕの全要素が［０〜２５５］の範囲内であるかどうかを確認する。これが真であれば，ステップＳ２１０にて，配列Ｕｂｕｆ［］の cases番地に現在のＵの値を保存し，ステップＳ２１１へ進み casesを１加算し，ステップＳ２１２へ進む。偽であればステップＳ２１２へ進む。【０１４３】
ステップＳ２１２では８重ループがすべて完了したかを確認し，偽である間はループ先頭のステップＳ２０５へ戻る。真であれば，ステップＳ２１３において，既に求められたcases （格子点の総数）分の情報量（式（２２））を用いてindex を復号し，ステップＳ２１４にてＵｂｕｆ［index ］（原信号に相当）を出力し，終了する。【０１４４】
以上の実施例では，cases を用いてindex を符号化する例を説明したが，index の符号化に汎用可変長符号化（ＵＶＬＣ：Universal Variable Length Code）やストップ符号を用いるようにしてもよい。index の符号化に汎用可変長符号化やストップ符号を用いた場合，復号側では casesがわからなくても復号することができる。この場合，index 用の符号量は２割弱増えると予想されるが， casesの値を算出する必要がないため，多重ループを途中で打ち切ることができ，符号化も復号も時間が約１／２になるというメリットがある。また，復号側の配列記憶Ｕｂｕｆ［］が不要になるというメリットもある。【０１４５】
以上，本発明の実施形態及び実施例を図面を参照して説明してきたが，これらは本発明の例示に過ぎず，本発明がこれら実施形態及び実施例に限定されるものでないことは明らかである。したがって，本発明の精神および範囲を逸脱しない範囲で構成要素の追加，省略，置換，その他の変更を行うようにしても良い。【０１４６】
例えば，図３〜図５に示した装置は専用のハードウェアにより実現する形態のほか，メモリおよびＣＰＵ（中央処理装置）等を備えたコンピュータシステムで構成し，これら装置の処理（例えば，図６〜図７に示した各ステップ）を実現するためのプログラムをメモリにロードして実行することによってその機能を実現させるようにしても良い。また，当該の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録しておき，この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませて実行するようにしても良い。【０１４７】
なお，ここでいうコンピュータシステムとは，ＯＳや周辺機器等のハードウェアを含むものとする。また，コンピュータ読み取り可能な記録媒体とは，フレキシブルディスク，光磁気ディスク，ＲＯＭ，ＣＤ−ＲＯＭ等の可搬媒体，コンピュータシステムに内蔵されるハードディスク等の記憶装置のことを言い，インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように，短時間の間，動的にプログラムを保持するもの（伝送媒体ないしは伝送波），その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように，一定時間プログラムを保持しているものも含む。また上記プログラムは，前述した機能の一部を実現するためのものであっても良く，さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの，いわゆる差分ファイル（差分プログラム）であっても良い。【０１４８】
また，段階的可逆ビデオ符号化装置および段階的可逆ビデオ復号装置は例えば以下のように構成しても良い。
すなわち，段階的可逆ビデオ符号化装置は，Ｈ．２６４標準準拠のビットストリームを生成する手段と，これに加えて画像信号の各ブロックの符号化において，フレーム内符号化における空間予測またはフレーム間符号化における時間予測による予測信号を入力する手段と，原信号から予測信号を差し引いた残差信号を入力する手段と，Ｈ．２６４標準方式に基づき残差信号に対し直交変換を施して得られる変換係数およびそれを量子化した量子化係数を求める手段と，量子化係数，量子化パラメータおよび量子化方法から定まる変換係数の存在空間を特定する手段と，該空間中のある格子点が残差信号の直交変換の結果として妥当であるかどうかを判断する妥当性判断手段と，該空間内の格子点のうち上記判断が妥当であるものを列挙する列挙手段と，列挙された格子点に，列挙順に０から始まる通し番号を割り当てる手段と，列挙された格子点の中で，残差信号の変換係数に一致する格子点の通し番号を得る手段と，得られた通し番号を符号化する手段とを備えるように構成する。【０１４９】
上記段階的可逆ビデオ符号化装置において，格子点を列挙する際に，変換係数間の整数的値関係を用いることにより，空間内で変換係数がとりえない点については妥当の判断処理を省略する手段を備えるようにしても良い。【０１５０】
上記段階的可逆ビデオ符号化装置において，特定のいくつかの変換係数について，該係数と既に伝送済みの係数（もしあれば）との整数的値関係を利用し，該係数がとりえない値を除いた情報を伝送することで，該係数を伝送することに代替する手段と，こうして予め伝送された変換係数を用い，次元の縮小した存在空間内で格子点を列挙する手段とを備えるようにしても良い。【０１５１】
上記段階的可逆ビデオ符号化装置において，前記妥当性判断をビット演算・整数加減算のみで等価に実現する手段を備えるようにしても良い。【０１５２】
上記段階的可逆ビデオ符号化装置において，残差信号の存在範囲と変換係数の存在範囲の交わりが凸多面体となることを用いて上記妥当性判断を途中で中止する手段を備えるようにしても良い。【０１５３】
上記段階的可逆ビデオ符号化装置において，上記列挙手段による格子点の列挙を実行せず符号量の見積もりを行う手段を備えるようにしても良い。【０１５４】
上記段階的可逆ビデオ符号化装置に対応する段階的可逆ビデオ復号装置は，Ｈ．２６４標準復号方式を実行する手段と，量子化パラメータ，量子化係数，符号化側の量子化方法，および既に復元された係数（もしあれば）から定まる変換係数の存在空間を特定する手段と，復号すべき係数を復号する手段と，第１〜第３の本発明と同様な列挙手段および妥当性判断手段と，通し番号を復号する手段と，列挙された順が通し番号に等しい格子点を出力する手段とを備えるように構成する。
【産業上の利用可能性】
【０１５５】
本発明は高能率ビデオ符号化／復号を実現する段階的可逆ビデオ符号化／復号技術に関するものである。本発明によれば，基本部分として伝送される符号はＨ．２６４標準の符号化と互換性を保ちながら，付加部分の符号量をできるだけ低く抑えつつ，原信号に一致する可逆な復号を行うことが可能となる。また，本発明によれば，処理を数兆倍に高速化して実行することができる。さらに，本発明によれば，実際の符号化を行わずに符号量の推定を行うことができ，結果として符号量を減らす予測モードの選択を高速に行うことができる。
【図１】
0004767860.tif 000014
【図２】
0004767860.tif 000015
【図３】
0004767860.tif 000016
【図４】
0004767860.tif 000017
【図５】
0004767860.tif 000018
【図６】
0004767860.tif 000019
【図７】
0004767860.tif 000020