(57)【特許請求の範囲】
【請求項１】
ウェーブレット変換により帯域分割された各サブバンドにおける量子化されたウェーブレット変換係数をコードブロックに分割し、各コードブロックをビットプレーンに変換し、ビットプレーンを符号化パスに分割し、符号化パス毎に符号化して符号データを出力するエントロピー符号化手段と、
符号化された符号化パス毎の符号データを格納する符号メモリと、
各コードブロックの符号量の総和を示す総符号量又は各コードブロックの符号化歪の総和、各符号化パスとそれぞれ前の符号化パスを符号化した際の符号化歪の歪差分と各符号化パスの符号量の出力バイト数により算出したＲＤ曲線の傾き、及び各値が単調減少となっている与えられた複数のレート制御パラメータの逆数に基づき、どのコードブロックにおけるどの符号化パスまで上記エントロピー符号化手段が符号化するかを判断し、符号化終了となる符号化終了パスを出力するレート制御情報抽出手段と、
上記レート制御情報抽出手段より出力された符号化終了パスにより定まる符号化パスまでの符号データを上記符号メモリから読み出し、各コードブロックにおける符号化パス数を付加して符号ストリームとして出力する符号データ抽出手段とを備えた画像符号化装置。
【請求項２】
レート制御手段は、各符号化パスとそれぞれ１つ前の符号化パスを符号化した際の符号化歪の歪差分と各符号化パスの符号量の出力バイト数によりＲＤ曲線の傾きを算出し、各コードブロックの符号量の総和を示す総符号量、又は各コードブロックの符号化歪の総和を算出し、上記総符号量が目標符号量に達した場合、又は各コードブロックの上記符号化歪の総和が目標符号化歪に達した場合に、符号化終了と判断すると共に、上記総符号量が上記目標符号量に達しない場合、又は上記符号化歪の総和が上記目標符号化歪に達しない場合には、上記傾きが与えられたレート化制御パラメータの逆数より小さくなるまで、そのコードブロックにおける各符号化パスの符号化を行わせ、上記傾きがレート制御パラメータの逆数より小さくなった場合に、次のコードブロックにおける各符号化パスの符号化を行わせ、全てのコードブロックにおける各符号化パスの符号化が終了した場合に、与えられているレート制御パラメータの逆数より単調減少の値を示す他のレート制御パラメータの逆数を使用して、どのコードブロックにおけるどの符号化パスまで符号化するかを判断することを特徴とする請求の範囲第１項記載の画像符号化装置。
【請求項３】
レート制御情報抽出手段は、現符号化パス以前の符号化パスで現符号化パスとのＲＤ曲線の傾きが現符号化パス以前の符号化パスにおける傾きよりも小さくなる符号化パスと現符号化パス間での歪差分と出力バイト数の比を現符号化パスの傾きと補正し、各コードブロックの符号量の総和を示す総符号量、又は各コードブロックの符号化歪の総和を算出し、上記総符号量が目標符号量に達した場合、又は各コードブロックの上記符号化歪の総和が目標符号化歪に達した場合に、符号化終了と判断すると共に、上記総符号量が上記目標符号量に達しない場合、又は上記符号化歪の総和が上記目標符号化歪に達しない場合には、上記補正した傾きが与えられたレート制御パラメータの逆数より小さくなるまで、そのコードブロックにおける各符号化パスの符号化を行わせ、上記補正した傾きがレート制御パラメータの逆数より小さくなった場合に、次のコードブロックにおける各符号化パスの符号化を行わせ、全てのコードブロックにおける各符号化パスの符号化が終了した場合に、与えられている上記レート制御パラメータの逆数より単調減少の値を示す他の符号化制御パラメータの逆数を使用して、どのコードブロックにおけるどの符号化パスまで符号化するかを判断することを特徴とする請求の範囲第１項記載の画像符号化装置。
【請求項４】
ウェーブレット変換により帯域分割された各サブバンドにおける量子化されたウェーブレット変換係数をコードブロックに分割し、各コードブロックをビットプレーンに変換し、ビットプレーンを符号化パスに分割し、符号化パス毎に符号化して符号データを出力するエントロピー符号化手段と、
符号化された符号化パス毎の符号データを格納する符号メモリと、
各コードブロックの符号量の総和を示す総符号量又は各コードブロックの符号化歪の総和、各コードブロックの符号量、各コードブロックの符号化歪、及び各値が単調増加となっている与えられた複数のレート制御パラメータに基づき、どのコードブロックにおけるどの符号化パスまで上記エントロピー符号化手段が符号化するかを判断し、符号化終了となる符号化終了パスを出力するレート制御情報抽出手段と、
上記レート制御情報抽出手段より出力された符号化終了パスで定まる符号化パスまでの符号データを上記符号メモリから読み出し、各コードブロックにおける符号化パス数を付加して符号ストリームとして出力する符号データ抽出手段とを備えた画像符号化装置。
【請求項５】
レート制御情報抽出手段は、コードブロックの符号量と、コードブロックの符号化歪とレート制御パラメータの積との和により各符号化パスの傾き指標値を算出し、あるコードブロックで傾き指標値が最大となる符号化パスを導出し、導出した傾き指標値が最大となる符号化パスが現在符号化している符号化パスでなくなるまで、そのコードブロックにおける符号化パスの符号化を行わせ、各コードブロックの総符号量が目標符号量に達した場合、又は各コードブロックの符号化歪の総和が目標符号化歪に達した場合に、符号化終了と判断すると共に、上記総符号量が上記目標符号量に達しない場合、又は上記符号化歪の総和が上記目標符号化歪に達しない場合には、次のコードブロックにおける各符号化パスの符号化を行わせ、全てのコードブロックにおける各符号化パスの符号化が終了した場合に、与えられているレート制御パラメータより単調増加の値を示す他のレート制御パラメータを使用して、どのコードブロックにおけるどの符号化パスまで符号化するかを判断することを特徴とする請求の範囲第４項記載の画像符号化装置。
【発明の詳細な説明】
【技術分野】  この発明はエントロピー符号化を行う画像符号化装置に関するものである。
【背景技術】  現在、インターネットを中心に静止画像符号化アルゴリズムＪＰＥＧ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）が広く普及しているが、一方で次世代の符号化方式として、さらなる性能改善、機能付加の要求を背景として、１９９７年より新たにＪＰＥＧ２０００プロジェクトがＩＳＯとＩＴＵの合同機関によりスタートしている。また、２０００年１２月には、同ＪＰＥＧ２０００アルゴリズムの基本方式を定めるパート１について、その主要な技術内容が確定されている。以下に、勧告書（ＩＳＯ／ＩＴＵ  １５４４４−１：２０００）に従ってＪＰＥＧ２０００符号化アルゴリズムの基本方式の概略を説明する。
まず、入力される画像信号はウェーブレット変換部で２次元のウェーブレット変換が施されて複数のサブバンドに帯域分割され、各サブバンドにおけるウェーブレット変換係数が生成される。ここで、２次元のウェーブレット変換は１次元のウェーブレット変換の組み合わせとして実現される。つまり、垂直方向の一次元ウェーブレット変換を列毎に順次行う処理と水平方向の一次元ウェーブレット変換をライン毎に順次行う処理である。
第１図は従来技術におけるウェーブレット変換を示す図である。１次元のウェーブレット変換は、第１図（ａ）に示すように、所定の特性を持つローパスフィルタとハイパスフィルタ及びダウンサンプラにより実現されるものである。２次元のウェーブレット変換により帯域分割された各サブバンドは、低域成分をＬ、高域成分をＨとし、水平方向の変換を１文字目で表現し、垂直副走査方向の変換を２文字目で表現することで、第１図（ｂ）に示すようにＬＬ、ＨＬ、ＬＨ、ＨＨと表現される。ここで、水平、垂直方向の低域成分（ＬＬ成分）は再帰的にウェーブレット変換が施される。再帰的に施される各ウェーブレット変換の回数を分解レベルと称し、第１図（ｂ）中のＬＬ、ＨＬ、ＬＨ、ＨＨの前に記載された数字がこれにあたる。即ち、ウェーブレット変換の分解回数２の場合には、最低解像度成分の分解レベルは２となり、反対に最高解像度成分のＨＬ、ＬＨ、ＨＨの分解レベルは１になる。
次に各サブバンドにおけるウェーブレット変換係数は、サブバンド毎に設定された量子化ステップサイズにより量子化される。
次に各サブバンドの量子化後のウェーブレット変換係数をコードブロックと呼ばれる固定サイズの領域に分割した後、多値データからなるコードブロックを２値のビットプレーン表現に変換し、各ビットプレーンを３通りの符号化パスＳｉｇｎｉｆｉｃａｎｔ  Ｐｒｏｐａｇａｔｉｏｎ  Ｄｅｃｏｄｉｎｇ  Ｐａｓｓ、Ｍａｇｎｉｔｕｄｅ  Ｒｅｆｉｎｅｍｅｎｔ  Ｐａｓｓ、Ｃｌｅａｎｕｐ  Ｐａｓｓに分割する。
３つの符号化パスから出力される２値信号は、それぞれの符号化パス毎にコンテクストモデリングが行われエントロピー符号化が行われる。
また、エントロピー符号化処理と並行して、各コードブロックにおいて符号化パス毎の符号量と符号化歪を計算する。
最後に、ラグランジェの乗数法を用いて画質劣化（符号化歪）を最小にしながら、目標とする符号サイズ以下に符号量を調整するレート制御が行われる。レート制御の方法は標準化されているわけではなく、アプリケーションに応じて任意の方法を使うことができるが、以下に勧告書（ＩＳＯ／ＩＴＵ  １５４４４−１：２０００）Ｊ．１４．３に参考情報として記載されているレート制御部のメカニズムについて概略を説明する。
この方法では、各コードブロックｉにおける切り捨てポイントをｎｉとし、各切り捨てポイントまでの符号量をＲ（ｉ，ｎｉ）とし、符号化歪をＤ（ｉ，ｎｉ）としたとき、ラグランジェの乗数法を使い、次の式を最大にする切り捨てポイントｎｉによって生ずる画面全体での総符号量Ｒｓｕｍが目標符号量Ｒｍａｘの範囲内であることを満足するまでレート制御パラメータλを調整する。
Σ（Ｒ（ｉ，ｎｉ）−λＤ（ｉ，ｎｉ））
ここで、符号化歪Ｄとは、ある符号化パスまでの符号を送ったときに再生画像の平均二乗誤差が符号データを伝送しないときと比較してどれだけ減少したかを示すもので、厳密に言えば符号化歪の減少量ということになる。従って、符号化前は符号化歪Ｄは０、最終ビットプレーンまで符号化すると符号化歪Ｄは平均二乗誤差に等しくなる。
第２図は従来技術における最適な符号化パスの導出を説明する図である。上記式を最大にする切り捨てポイントを見つけることは、第２図に示すように、各コードブロックの符号量Ｒと符号化歪Ｄをグラフに表したとき（以下、ＲＤ曲線と称する）、その接線の傾きがレート制御パラメータλの逆数であるλ−１となる切り捨てポイントを見つけることと等価である。第２図では、２つのコードブロックｃ１，ｃ２において、接線の傾きがλ−１となる切り捨てポイントがｎｃ１、ｎｃ２で、その切り捨てポイントまでの符号量がＲ（ｃ１，ｎｃ１），Ｒ（ｃ２，ｎｃ２）となることを表している。このような符号量Ｒを全てのコードブロックに対して加算しＲｍａｘと比較する。
これをコードブロック毎に見た場合、（Ｒ（ｉ，ｎｉ）−λＤ（ｉ，ｎｉ））を最大化する切り捨てポイントｎｉを次のように見つける必要がある。ここで、ｋは切り捨てポイントｎｉを表す変数である。
Ｓｅｔ  ｎｉ＝０
Ｆｏｒ  ｋ＝１，２，３，・・・
Ｓｅｔ  ΔＲ（ｉ，ｋ）＝Ｒ（ｉ，ｋ）−Ｒ（ｉ，ｎｉ）  ａｎｄ
ΔＤ（ｉ，ｋ）＝Ｄ（ｉ，ｋ）−Ｄ（ｉ，ｎｉ）
Ｉｆ（ΔＤ（ｉ，ｋ）／ΔＲ（ｉ，ｋ））＞λ−１
ｔｈｅｎ  ｓｅｔ  ｎｉ＝ｋ
ところが、このアルゴリズムでは、多数のレート制御パラメータλに対して上記処理を実行しなければ切り捨てポイントｎｉを求めることができない。そこで、ＲＤ曲線の傾きＳ（ｉ，ｋ）＝ΔＤ（ｉ，ｋ）／ΔＲ（ｉ，ｋ）がｋについて単調減少になるように予め補正しておく。具体的には次のように処理を行う。ここで、ｐは切り捨てポイントｎｉを表す変数である。
（１）ｓｅｔ  Ｎｉ＝｛ｎ｝  （ｉ．ｅ．ｔｈｅ  ｓｅｔ  ｏｆ  ａｌｌ  ｔｒｕｎｃａｔｉｏｎ  ｐｏｉｎｔ）
（２）Ｓｅｔ  ｐ＝０
（３）Ｆｏｒ  ｋ＝１，２，３，４，・・・，ｋｍａｘ
Ｉｆ  ｋ  ｂｅｌｏｎｇｓ  ｔｏ  Ｎｉ
Ｓｅｔ  ΔＲ（ｉ，ｋ）＝Ｒ（ｉ，ｋ）−Ｒ（ｉ，ｐ），
ａｎｄ  ΔＤ（ｉ，ｋ）＝Ｄ（ｉ，ｋ）−Ｄ（ｉ，ｐ）
Ｓｅｔ  Ｓ（ｉ，ｋ）＝ΔＤ（ｉ，ｋ）／ΔＲ（ｉ，ｋ）
Ｉｆ  ｐ≠０  ａｎｄ  Ｓ（ｉ，ｋ）＞Ｓ（ｉ，ｐ），
ｔｈｅｎ  ｒｅｍｏｖｅ  ｐ  ｆｒｏｍ  Ｎｉ，ａｎｄ
ｇｏ  ｔｏ  ｓｔｅｐ  （２）
Ｏｔｈｅｒｗｉｓｅ，  ｓｅｔ  ｐ＝ｋ
この処理により、与えられたレート制御パラメータλに対する切り捨てポイントの最適化は、Ｓ（ｉ，ｋ）＞λ−１を満たすＮｉにおける最大のｋとすれば良い。
第３図は従来技術におけるＲＤ曲線の傾きの単調現象補正処理を示すフローチャートである。上記のステップ（１）〜（３）の単調現象補正処理を第３図に示すフローチャートにまとめている。なお、第３図においてコードブロックを示すｉを割愛している。第３図のステップＳＴ１３は上記ステップ（３）の「Ｉｆ  ｋ  ｂｅｌｏｎｇｓ  ｔｏ  Ｎｉ」に対応し、第３図のステップＳＴ１６は上記ステップ（３）の「ｒｅｍｏｖｅ  ｐ  ｆｒｏｍ  ｎｉ」つまり、切り捨てポイントの候補Ｎｉの中からｐを取り除く作業に対応している。このように、切り捨てポイントについて、第３図では有効、無効を表すフラグ（ｆｌａｇ）を用いて同様の処理を実現している。
全てのコードブロックでこれらの情報の導出が完了したら、目標符号量Ｒｍａｘとなるような符号データを作成する。具体的には、あるレート制御パラメータλに対する画面全体の総符号量Ｒｓｕｍに対して、Ｒｓｕｍ≦Ｒｍａｘを満たす最大の総符号量Ｒｓｕｍを与えるレート制御パラメータλを見つけることになる。ここで、あるレート制御パラメータλに対する総符号量Ｒｓｕｍは各コードブロックにおいて切り捨てポイントを一意に求め、その切り捨てポイントまでの符号データの総和を算出して初めてわかる。そこで、Ｒｓｕｍ≦Ｒｍａｘを満たす最大の総符号量Ｒｓｕｍを与えるレート制御パラメータλを見つけるには、通常は、レート制御パラメータλの複数の候補に対する総符号量Ｒｓｕｍを算出して、所望の値に近い総符号量Ｒｓｕｍを与えるレート制御パラメータλを収束演算により算出する。レート制御パラメータλが求まったらそのレート制御パラメータλに対応する切り捨てポイントまでの符号データを全てのコードブロックから集めて、さらに各コードブロックにおける符号化パス数を付加情報として付け加え、最終的な符号データを構成する。こうして、目標符号量Ｒｍａｘのもとで符号化歪Ｄを最小とする符号データを生成することができる。
以上のようなＪＰＥＧ２０００国際標準規格はＩＳＯやＩＴＵ−Ｔ等の標準化機関を通して入手することができる。また、ＪＰＥＧ２０００の最新情報については、ｈｔｔｐ：／／ｗｗｗ．ｊｐｅｇ．ｏｒｇを参照することにより入手することができる。
従来の画像符号化装置は以上のように構成されているので、上記のレート制御方法では、切り捨てポイントを見つけるにあたり、実際に符号として出力しない切り捨てポイント以降の符号化パス、通常は全ての符号化パスまで、予めエントロピー符号化しておかなければならず、ＪＰＥＧ２０００のエントロピー符号化には、１ビット単位に算術演算が必要な算術符号化が用いられており、算術符号化の演算量が全体の処理量に与えるインパクトは非常に大きなものとなっている。従って、切り捨てポイント以降の符号化パスをエントロピー符号化することにより、余計な処理量が増加し符号化に要する演算量が増加してしまうと共に処理時間の遅延をもたらすという課題があった。
また、あるレート制御パラメータλに対する総符号量Ｒｓｕｍは、各コードブロックにおいて切り捨てポイントを一意に求め、その切り捨てポイントまでの符号データの総和を算出して初めて明らかになる。そのため、Ｒｓｕｍ≦Ｒｍａｘを満たす最大の総符号量Ｒｓｕｍを与えるレート制御パラメータλを算出するにあたり、レート制御パラメータλの複数の候補に対する総符号量Ｒｓｕｍを算出して、所望の値に近い総符号量Ｒｓｕｍを与えるレート制御パラメータλを収束演算により何度も探索する必要があるため、レート制御に要する演算量増大に繋がるという課題があった。
この発明は上記のような課題を解決するためになされたもので、エントロピー符号化及びレート制御に要する演算量を低減することができる画像符号化装置を得ることを目的とする。
【発明の開示】
この発明に係る画像符号化装置は、ウェーブレット変換により帯域分割された各サブバンドにおける量子化されたウェーブレット変換係数をコードブロックに分割し、各コードブロックをビットプレーンに変換し、ビットプレーンを符号化パスに分割し、符号化パス毎に符号化して符号データを出力するエントロピー符号化手段と、符号化された符号化パス毎の符号データを格納する符号メモリと、各コードブロックの符号量の総和を示す総符号量又は各コードブロックの符号化歪の総和、各符号化パスとそれぞれ前の符号化パスを符号化した際の符号化歪の歪差分と各符号化パスの符号量の出力バイト数により算出したＲＤ曲線の傾き、及び各値が単調減少となっている与えられた複数のレート制御パラメータの逆数に基づき、どのコードブロックにおけるどの符号化パスまで上記エントロピー符号化手段が符号化するかを判断し、符号化終了となる符号化終了パスを出力するレート制御情報抽出手段と、上記レート制御情報抽出手段より出力された符号化終了パスにより定まる符号化パスまでの符号データを上記符号メモリから読み出し、各コードブロックにおける符号化パス数を付加して符号ストリームとして出力する符号データ抽出手段とを備えたものである。
この発明により、エントロピー符号化及びレート制御に要する演算量を低減することができるという効果がある。
【図面の簡単な説明】  第１図は従来技術におけるウェーブレット変換を示す図である。
第２図は従来技術における最適な符号化パスの導出を説明する図である。
第３図は従来技術におけるＲＤ曲線の傾きの単調現象補正処理を示すフローチャートである。
第４図はこの発明の実施の形態１による画像符号化装置の構成を示すブロック図である。
第５図はこの発明の実施の形態１による画像符号化装置のレート制御情報抽出手段の内部構成を示すブロック図である。
第６図はこの発明の実施の形態１による画像符号化装置のウェーブレット変換手段が分解レベル２までウェーブレット変換をしたときのサブバンドを示す図である。
第７図はこの発明の実施の形態１による画像符号化装置におけるビットプレーンを説明する図である。
第８図はこの発明の実施の形態１による画像符号化装置におけるビットプレーンから符号化パスへの分解を説明する図である。
第９図はこの発明の実施の形態１による画像符号化装置の処理の流れを示すフローチャートである。
第１０図はこの発明の実施の形態１による画像符号化装置における符号化パスの符号化順序を示す図である。
第１１図はこの発明の実施の形態２による画像符号化装置のレート制御情報抽出手段の内部構成を示すブロック図である。
第１２図はこの発明の実施の形態２による画像符号化装置のレート歪メモリに格納されているＲＤテーブルのデータ構造を示す図である。
第１３図はこの発明の実施の形態２による画像符号化装置の処理の流れを示すフローチャートである。
第１４図はこの発明の実施の形態２による画像符号化装置におけるＲＤ曲線の傾きの補正を示す図である。
第１５図はこの発明の実施の形態３による画像符号化装置のレート制御情報抽出手段の内部構成を示すブロック図である。
第１６図はこの発明の実施の形態３による画像符号化装置のレート歪メモリに格納されているＲＤテーブルのデータ構造を示す図である。
第１７図はこの発明の実施の形態３による画像符号化装置の処理の流れを示すフローチャートである。
【発明を実施するための最良の形態】  以下、この発明をより詳細に説明するために、この発明を実施するための最良の形態について、添付の図面に従って説明する。
実施の形態１．
第４図はこの発明の実施の形態１による画像符号化装置の構成を示すブロック図である。この画像符号化装置はウェーブレット変換手段１０１、量子化手段１０２、エントロピー符号化手段１０３、符号メモリ１０４、レート制御情報抽出手段１０５及び符号データ抽出手段１０６を備えている。
第４図において、ウェーブレット変換手段１０１は入力画像信号に対して２次元のウェーブレット変換を再帰的に行いサブバンドに帯域分割し、各サブバンドにおけるウェーブレット変換係数を生成する。量子化手段１０２はウェーブレット変換手段１０１によって生成されたウェーブレット変換係数を予め設定された量子化ステップサイズで量子化処理する。エントロピー符号化手段１０３は量子化されたウェーブレット変換係数をコードブロックに分割し、各コードブロックをビットプレーンに変換し、ビットプレーンを符号化パスに分割し、符号化パス毎にエントロピー符号化して符号データを出力する。符号メモリ１０４はエントロピー符号化された符号化パス毎の符号データを一時的に格納する。レート制御情報抽出手段１０５は各コードブロックの符号量Ｒの総和を示す総符号量、各符号化パスとそれぞれ前の符号化パスを符号化した際の符号化歪Ｄの歪差分ΔＤと各符号化パスの符号量Ｒの出力バイト数ΔＲにより算出したＲＤ曲線の傾きＳ、及び各値が単調減少となっている与えられた複数のレート制御パラメータの逆数λ−１に基づき、どのコードブロックにおけるどの符号化パスまでエントロピー符号化手段１０３が符号化するかを判断し、符号化終了となる符号化終了パスを出力する。符号データ抽出手段１０６はレート制御情報抽出手段１０５より出力された符号化終了パスにより定まる符号化パスまでの符号データを符号メモリ１０４から読み出し、各コードブロックにおける符号化パス数を付加して符号ストリームとして出力する。
第５図はレート制御情報抽出手段１０５の内部構成を示すブロック図である。このレート制御情報抽出手段１０５は歪計算手段１１１、符号量計算手段１１２、傾き計算手段１１３及び符号化終了パス導出手段１１４を備えている。
第５図において、歪計算手段１１１はエントロピー符号化手段１０３からの符号化パス毎にその符号化パスと一つ前の符号化パスにおける符号化歪Ｄの歪差分ΔＤを計算する。符号量計算手段１１２はエントロピー符号化手段１０３からの符号化パス毎にその符号化パスでの符号量Ｒの出力バイト数ΔＲをカウントする。傾き計算手段１１３は歪計算手段１１１により計算された歪差分ΔＤと符号量計算手段１１２によりカウントされた出力バイト数ΔＲからＲＤ曲線の傾きＳを計算する。符号化終了パス導出手段１１４は、各コードブロックの符号量Ｒの総和を示す画面全体の総号量Ｒｓｕｍと傾き計算手段１１３により計算された傾きＳと与えられたレート制御パラメータの逆数λ−１に基づき、各コードブロック毎に符号化を継続するか否かを判断して符号化終了パスを導出し、符号化終了の情報と符号化終了パスを出力する。
次に動作について説明する。
まず、第４図において、例えばイメージスキャナやデジタルカメラ、又はネットワークや記憶媒体等の画像入力装置（図示せず）からの画像信号がウェーブレット変換手段１０１に入力される。ウェーブレット変換手段１０１は入力した画像信号に対して、１次元のウェーブレット変換を垂直方向、水平方向の両方向に対して２次元的に施してサブバンドに帯域分割し、各サブバンドにおけるウェーブレット変換係数を生成する。ここで、１次元のウェーブレット変換は、低域通過フィルタと高域通過フィルタのフィルタバンクによって実現される。
第６図はウェーブレット変換手段１０１が分解レベル２までウェーブレット変換をしたときのサブバンドを示す図であり、２次元のウェーブレット変換を２回再帰的に施した例を示している。第６図において、先頭の数字は分解レベルを表しており、続くＬ又はＨの２つの英字は、水平方向、垂直方向のフィルタの種類を表している。Ｌは低域通過フィルタを、Ｈは高域通過フィルタを施した結果を表している。また、「再帰的に」ウェーブレット変換を２回施すと言うことは、まず、第１回目のウェーブレット変換により、サブバンド１ＬＬ，１ＨＬ，１ＬＨ，１ＨＨが生成されると、その１ＬＬに対して２回目のウェーブレット変換を施し、サブバンド２ＬＬ，２ＨＬ，２ＬＨ，２ＨＨを生成することを意味している。
量子化手段１０２は、サブバンド毎に設定された量子化ステップサイズにより、ウェーブレット変換手段１０１により生成されたウェーブレット変換係数を量子化する。
エントロピー符号化手段１０３は、各サブバンドにおけるウェーブレット変換係数をコードブロックと呼ばれる固定サイズの矩形領域に分割した後、多値データからなるそれぞれのコードブロックを２値のビットプレーンに変換する。通常このコードブロックの大きさは、６４×６４、３２×３２等のサイズに設定される。
第７図はビットプレーンを説明する図である。ここで、第７図を用いてビットプレーンの分解について詳しく説明する。第７図（ａ）は４×４のコードブロックの一例を表している。第７図（ａ）のコードブロックのデータに対して、正負を表す１ビットの信号と絶対値の表現に変換し、それらのデータを縦方向に２進表現した結果を各行単位に並べたものが第７図（ｂ）となる。次に、第７図（ｂ）に対して同一のビット番号のビットを集めたものが第７図（ｃ）となる。ここで、最下位ビット（ＬＳＢ：Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を第０ビット、最上位ビット（ＭＳＢ：Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を第３ビットとしたとき、第０ビットで集めたものを第０ビットプレーン、第１ビットで集めたものを第１ビットプレーン、第２ビットで集めたものを第２ビットプレーン、第３ビットで集めたものを第３ビットプレーンとしている。これ以外にも正負を表すビットの集まりとして符号ビットプレーンを作成する。
エントロピー符号化手段１０３は、ビットプレーン内の各ビットを、そのコンテクストに応じて、３通りの符号化パス、すなわち、シグニフィカントプロパゲーションデコーディングパス（Ｓｉｇｎｉｆｉｃａｎｃｅ  Ｐｒｏｐａｇａｔｉｏｎ  Ｄｅｃｏｄｉｎｇ  Ｐａｓｓ）、マグニチュードリファインメントパス（Ｍａｇｎｉｔｕｄｅ  Ｒｅｆｉｎｅｍｅｎｔ  Ｐａｓｓ）、クリーンナップパス（Ｃｌｅａｎｕｐ  Ｐａｓｓ）に分割する。
次に、エントロピー符号化手段１０３は、それぞれの符号化パス毎に算術符号によりエントロピー符号化するためのコンテクストモデリングを行う。但し、ＭＳＢプレーンから数えて全て０となるビットプレーンはコンテクストモデリングや符号化は行わず、全て０のビットプレーンの数をヘッダに書くだけとする。そして、最初に１が出現したビットプレーンについては全てのビットがクリーンナップパスに分類されるが、その他のビットプレーンについては前述したように３種類の符号化パスに分類される。
第８図はビットプレーンから符号化パスへの分解を説明する図であり、コードブロックのビットプレーン数が６で、１が出現する有効なビットプレーン数が４の場合の例を示している。
コンテストモデリングが終了すると、エントロピー符号化手段１０３は算術符号によるエントロピー符号化を行い、エントロピー符号化した符号データを符号メモリ１０４に格納する。
エントロピー符号化手段１０３の処理と並行して、レート制御情報抽出手段１０５の歪計算手段１１１は、エントロピー符号化手段１０３からの各コードブロックにおいて、ある符号化パスの符号化が終了する度に、その符号化パスと一つ前の前符号化パスにおける符号化歪Ｄの歪差分ΔＤを計算する。ここで、符号化歪Ｄとは、ある符号化パスまでの符号を送ったときに再生画像の平均二乗誤差が符号データを伝送しないときと比較してどれだけ減少したかを示すもので、厳密に言えば符号化歪の減少量ということになる。従って、符号化歪Ｄは最終ビットプレーンまで歪差分ΔＤを累積するとその平均二乗誤差に等しくなる。
同時に、レート制御情報抽出手段１０５の符号量計算手段１１２は、エントロピー符号化手段１０３からの各コードブロックにおいて、あるパスの符号化が終了する度にその符号化パスでの符号量Ｒの出力バイト数ΔＲをカウントする。傾き計算手段１１３は、歪計算手段１１１により計算された歪差分ΔＤを符号量計算手段１１２によりカウントされた現符号化パスでの出力バイト数ΔＲで除算することにより、現符号化パスにおけるＲＤ曲線の傾きＳを算出する。
符号化終了パス導出手段１１４は、各コードブロックの符号量Ｒの総和を示す画面全体の総号量Ｒｓｕｍと傾き計算手段１１３により算出された傾きＳと与えられたレート制御パラメータの逆数λ−１から、そのコードブロックでの符号化をさらなる符号化パスまで続行するか否かを判断し、判断結果をエントロピー符号化手段１０３に出力する。続行するならばエントロピー符号化手段１０３は次の符号化パスを符号化し、歪計算手段１１１はその符号化パスでの符号化歪Ｄの歪差分ΔＤを計算し、符号量計算手段１１２はその符号化パスでの符号量Ｒの出力バイト数ΔＲをカウントし、傾き計算手段１１３はその符号化パスでのＲＤ曲線の傾きＳを算出し、符号化終了パス導出手段１１４は、各コードブロックの符号量Ｒの総和を示す画面全体の総号量Ｒｓｕｍと傾き計算手段１１３により算出された傾きＳと与えられたレート制御パラメータの逆数λ−１から、再度、そのコードブロックでの符号化をさらなる符号化パスまで続行するか否かを判断する。符号化を続行しないならば、符号化終了の情報をエントロピー符号化手段１０３に出力し、符号化終了を示す符号化終了パスを符号データ抽出手段１０６に出力する。
エントロピー符号化手段１０３は、符号化終了パス導出手段１１４からの符号化終了の情報を受け取ってそのコードブロックでのそれ以降の符号化パスの符号化を行わない。
符号データ抽出手段１０６は、各コードブロックにおける符号化終了パスで定まる符号化パスまでの符号データを符号メモリ１０４から読み出し、各コードブロックにおける符号化パス数を付加情報として付け加えた後、それらを指定された順に並べて、所定のヘッダ情報を付加した上で符号ストリームとして出力する。
ここで、レート制御情報抽出手段１０５の処理の詳細について説明する。ここでは、予めレート制御パラメータλの候補を複数用意しておき、あるレート制御パラメータλを満足する符号化パスまでの符号化を全コードブロックに関して行う。その際、全コードブロックでの総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達しているか否かを判断して、達していれば符号化を終了させ、達していなければ次のレート制御パラメータλの候補を設定して、そのレート制御パラメータλを全コードブロックが満足するまで符号化を再度実行させる。このように、レート制御パラメータλを設定して符号化を行う処理を総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達するまで行う。あるレート制御パラメータλを満足するか否かは、各符号化パスの終了時点でＲＤ曲線の傾きＳを算出し、傾きＳがレート制御パラメータ逆数λ−１未満に達したか否かで判断する。
第９図はこの発明の実施の形態１による画像符号化装置の処理の流れを示すフローチャートである。以下、第９図を使用して符号化すべき符号化パスの決定方法について説明する。レート制御パラメータの候補λ（ｔ）を以下のように設定する。
λ（ｔ）＝｛λ（０），λ（１），λ（２），・・・λ（ｔｍａｘ）｝
ここで、各レート制御パラメータの候補λ（ｔ）の値は単調増加となるよう設定されており、λ（ｔ）＜λ（ｔ＋１）である。すなわち、各レート制御パラメータの候補λ（ｔ）の逆数λ（ｔ）−１の値は単調減少となるよう設定されている。
ステップＳＴ１０１において、エントロピー符号化手段１０３は次の初期設定を行う。すなわち、レート制御パラメータλのインデックスｔの初期値をｔ＝０（ｔ＝０〜ｔｍａｘ）とし、コードブロックのインデックスｉ＝０（ｉ＝０〜ｉｍａｘ）とし、総符号量のカウンタＲｓｕｍ＝０とし、各コードブロックにおける符号化パスを記憶する変数ｋ（ｉ）を全てコードブロックについて−１（ゼロビットプレーンをスキップした次のパスのインデックスが０、ｋ（ｉ）＝−１〜ｋｍａｘ、カウンタの都合上、初期値はｋ（ｉ）＝−１とする）とする。
なお、レート制御情報抽出手段１０５にはそのメモリを図示はしないが、変数ｋ（ｉ）はコードブロック毎に符号化パスを記憶する変数であり、レート制御パラメータλのインデックスｔ、コードブロックのインデックスｉ、総符号量のカウンタＲｓｕｍは全コードブロックで共通の変数である。
ステップＳＴ１０２において、符号化終了パス導出手段１１４はＳ（ｉ、ｋ（ｉ））≧λ（ｔ）−１であるかを判断する。このステップＳＴ１０２はレート制御パラメータの候補λ（ｔ）が更新された際に新たな符号化パスを符号化する必要があるか否かを判断するための処理なので、最初は必ずＳ（ｉ、ｋ（ｉ））≧λ（ｔ）−１となるようにＳ（ｉ、−１）を十分大きな値に設定しておく。ステップＳＴ１０３において、エントロピー符号化手段１０３は符号化パスを記憶する変数ｋ（ｉ）をインクリメントし最初の符号化パスの符号化に備える。
ステップＳＴ１０４において、エントロピー符号化手段１０３はコードブロックｉにおける符号化対象の符号化パスｋ（ｉ）を符号化する。ステップＳＴ１０５において、現符号化コードブロックｉについて、歪計算手段１１１が現符号化パスｋと前符号化パスｋ−１間の符号化歪Ｄの歪差分ΔＤ（ｉ，ｋ（ｉ））を計算し、符号量計算手段１１２が現符号化パスでの符号量Ｒの出力バイト数ΔＲ（ｉ，ｋ（ｉ））を算出し、傾き計算手段１１３が現符号化パスにおけるＲＤ曲線の傾きＳを算出する。
Ｓ（ｉ，ｋ（ｉ））＝ΔＤ（ｉ，ｋ（ｉ））／ΔＲ（ｉ，ｋ（ｉ））
なお、最初の符号化パス０については、傾きＳを十分大きな値に設定しておくものとする。
ステップＳＴ１０６において、符号化終了パス導出手段１１４は総符号量のカウンタＲｓｕｍに現符号化パスで発生した符号量Ｒの出力バイト数ΔＲ（ｉ，ｋ（ｉ））を加算する。ステップＳＴ１０７において、符号化終了パス導出手段１１４は、総符号量のカウンタＲｓｕｍが目標符号量Ｒｍａｘに達しているか否かを判断し、総符号量のカウンタＲｓｕｍが目標符号量Ｒｍａｘに達していたならば、各コードブロックで、符号化終了の情報をエントロピー符号化手段１０３に出力し、各コードブロックで、どの符号化パスまで符号化したかを示す符号化パスｋ（ｉ）を符号化終了パスとして符号データ抽出手段１０６に出力する。
ステップＳＴ１０７において、総符号量のカウンタＲｓｕｍが目標符号量Ｒｍａｘに達していないならば、ステップＳＴ１０８において、符号化終了パス導出手段１１４は現符号化パスでの傾きＳ（ｉ，ｋ（ｉ））とλ（ｔ）−１との大小を判断し、傾きＳ（ｉ，ｋ（ｉ））が大きければ、エントロピー符号化手段１０３に通知し、ステップＳＴ１０３に戻って、エントロピー符号化手段１０３はさらに次の符号化パスを符号化する。傾きＳ（ｉ，ｋ（ｉ））がλ（ｔ）−１未満になったならば、エントロピー符号化手段１０３に通知し、エントロピー符号化手段１０３は符号化済みの符号化パスの符号データを一旦、符号メモリ１０４に保存し、このコードブロックの符号化を中断する。ステップＳＴ１０９において、コードブロックインデックスｉがｉｍａｘでなければ、ステップＳＴ１１０において、エントロピー符号化手段１０３はコードブロックインデックスｉをインクリメントして、次のコードブロックの符号化に処理を移す。
次のコードブロックでも同様に、ステップＳＴ１０４〜ＳＴ１０８を繰り返し、傾きＳ（ｉ，ｋ（ｉ））がλ（ｔ）−１未満となるまで符号化を行う。ステップＳＴ１０９において、これを全てのコードブロックに対して行った後、ステップＳＴ１１１において、レート制御パラメータλのインデックスｔをインクリメントし、レート制御パラメータλを次の単調増加となっている候補に設定して、再度全コードブロックの符号化を傾きＳ（ｉ，ｋ（ｉ））がλ（ｔ）−１未満となるまで行う。なお、レート制御パラメータの候補λ（ｔ）を更新しても、Ｓ（ｉ，ｋ（ｉ））＜λ（ｔ）−１となり、つまり更新後のレート制御パラメータの逆数λ（ｔ）−１が既に符号化済みの符号化パスにおける傾きＳより大きい場合がある。その場合は、次の符号化パスの符号化を行わないので、ステップＳＴ１０２において、更新後のレート制御パラメータの逆数λ（ｔ）−１が符号化済みの符号化パスにおける傾きＳ（ｉ，ｋ（ｉ））より大きいことを検出し、符号化処理をスキップしてステップＳＴ１０８に移行する。
第１０図は符号化パスの符号化順序を示す図である。この第１０図を使用して、コードブロックの総数が２の場合（ｉｍａｘ＝１）の、各レート制御パラメータの候補λ（ｔ）に対応する符号化パス、及びそれらが処理される順序を説明する。第１０図（ａ）がコードブロック０の各パス番号で示す符号化パスにおける傾きＳを示し、第１０図（ｂ）がコードブロック１の各パス番号で示す符号化パスにおける傾きＳを示し、第１０図（ｃ）が予め設定されている各値が単調減少となっているレート制御パラメータの逆数λ（ｔ）−１を示す。
まず、コードブロック０において、傾きＳがＳ（ｋ）＜λ（０）−１となるまでパス番号０，１の符号化パスを符号化する（第１０図（ａ）のＡ）。この時点で総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達していなければ、処理は次のコードブロック１に移り、同様に傾きＳがＳ（ｋ）＜λ（０）−１となるまでパス番号０，１の符号化パスを符号化する（第１０図（ｂ）のＢ）。
この時点で総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達していなければ、レート制御パラメータを次の値λ（１）に設定し、コードブロック０から処理を行い、コードブロック０のパス番号２の符号化パスを符号化する（第１０図（ａ）のＣ）。次に、コードブロック１では、直前に符号化したパス番号１の符号化パスの傾きＳ＝１６０が既に１／λ（１）＝１６５より小さいので、ここでは符号化を行わない。
この後も同様に、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達していなければ、レート制御パラメータを次の値λ（２）に設定し、コードブロック０のパス番号３の符号化パスを符号化し（第１０図（ａ）のＤ）、次にコードブロック１のパス番号２，３の符号化パスを符号化する（第１０図（ｂ）のＥ）。以上の処理を総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達するまで行う。
この実施の形態１では、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達するまで符号化を行っているが、目標符号量Ｒｍａｘの代わりに目標符号化歪を設定し、画面全体における各コードブロックの符号化歪Ｄの総和が目標符号化歪に達するまで符号化を行うことも可能である。
このように、この実施の形態１のレート制御情報抽出手段１０５は、各符号化パスとそれぞれ１つ前の符号化パスを符号化した際の符号化歪Ｄの歪差分ΔＤと各符号化パスの符号量Ｒの出力バイト数ΔＲによりＲＤ曲線の傾きＳを算出し、各コードブロックの符号量Ｒの総和を示す総符号量Ｒｓｕｍ、又は各コードブロックの符号化歪Ｄの総和を算出し、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達した場合、又は各コードブロックの符号化歪Ｄの総和が目標符号化歪に達した場合に、符号化終了と判断すると共に、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達しない場合、又は符号化歪Ｄの総和が目標符号化歪に達しない場合には、傾きＳが与えられたレート制御パラメータの逆数λ−１より小さくなるまで、そのコードブロックにおける各符号化パスの符号化を行わせ、傾きＳがレート制御パラメータの逆数λ−１より小さくなった場合に、次のコードブロックにおける各符号化パスの符号化を行わせ、全てのコードブロックにおける各符号化パスの符号化が終了した場合に、与えられているレート制御パラメータの逆数λ−１より単調減少の値を示す他のレート制御パラメータの逆数λ−１を使用して、どのコードブロックにおけるどの符号化パスまで符号化するかを判断する。
以上のように、この実施の形態１によれば、実際に符号化結果を出力する符号化パスのみを対象として符号化を行うため、全ての符号化パスを符号化する従来方法に比べて、エントロピー符号化に要する演算量を低減することができるという効果が得られる。また、総符号量が目標符号量に達した段階で符号化を終了するので、総符号量を目標符号量に合わせ込むために収束演算を行う必要がなく、レート制御に必要な演算量を低減することができるという効果が得られる。
なお、符号化パス数を付加情報として伝送するのではなく、符号化対象パスを符号化した場合の発生符号量、歪減少量を符号化側、復号側双方で予測し、その予測符号量、予測歪減少量からどの符号化パスまでを符号化するかを決定することも可能である。
しかし、コードブロック毎に符号化パス数を伝送するこの発明では、符号化パス数の付加情報は高々数パーセントに過ぎず、この僅かなオーバーヘッドにより、符号化歪を最小化するという観点から、ほぼ最適な符号化パスで符号化を終了することができる（予測値から算出した符号化終了パスは最適な符号化パスではない）。また、符号量、符号化歪の予測に要する演算量は、一般に、この発明のように実際の発生符号量や符号化歪をカウントする方法に比べて遙かに大きいので、レート制御の演算量増加につながる。
以上の点から、符号化パス数を付加情報として伝送するこの発明のレート制御手法が符号化歪を最小化する符号化における符号量低減に有効であるといえる。
実施の形態２．
上記実施の形態１では、符号化するに従いＲＤ曲線の傾きＳが単調減少となっていることを前提に説明したが、場合によっては傾きＳが単調減少とならないことがあり、２乗誤差を最小化するという意味で最適でない符号化終了パスを選択してしまうことがある。そこで、この実施の形態２では、傾きＳが単調減少とならない場合に、より最適に近い符号化終了パスを決定するために、ある符号化パスまで符号化を進めて傾きＳを算出するたびに、それまで符号化した符号化パスの傾きＳより小さくなるよう傾きＳを補正する処理を加えている。
この発明の実施の形態２による画像符号化装置の構成を示すブロック図は、上記実施の形態１の第４図と同じである。
第１１図はこの発明の実施の形態２による画像符号化装置のレート制御情報抽出手段１０５の内部構成を示すブロック図である。このレート制御情報抽出手段１０５は歪計算手段１２１、符号量計算手段１２２、レート歪メモリ１２３、傾き計算手段１２４及び符号化終了パス導出手段１２５を備えている。
第１１図において、歪計算手段１２１は、エントロピー符号化手段１０３からの符号化パス毎にその符号化パスと一つ前の符号化パスにおける符号化歪Ｄの歪差分ΔＤと、歪差分ΔＤを累積した符号化歪Ｄを計算する。符号量計算手段１２２は、エントロピー符号化手段１０３からの符号化パス毎にその符号化パスでの符号量Ｒの出力バイト数ΔＲと、出力バイト数ΔＲを累積した符号量Ｒをカウントする。レート歪メモリ１２３は歪差分ΔＤを累積した符号化歪Ｄ、出力バイト数ΔＲを累積した符号量Ｒ及びＲＤ曲線の傾きＳ等を符号化パス毎に格納する。傾き計算手段１２４は、レート歪メモリ１２３に格納されている符号化パス毎の符号化歪Ｄにより歪差分ΔＤを求め、レート歪メモリ１２３に格納されている符号化パス毎の符号量Ｒにより出力バイト数ΔＲを求め、歪差分ΔＤと出力バイト数ΔＲからＲＤ曲線の傾きＳを計算する。符号化終了パス導出手段１２５は、現符号化パス以前の符号化パスで現符号化パスとのＲＤ曲線の傾きＳが現符号化パス以前の符号化パスにおける傾きＳよりも小さくなる符号化パスと現符号化パス間での歪差分ΔＤと出力バイト数ΔＲの比を現符号化パスの傾きＳと補正し、各コードブロックの符号量Ｒの総和を示す画面全体の総符号量Ｒｓｕｍと現符号化パスの補正した傾きＳと与えられたレート制御パラメータの逆数λ−１に基づき、各コードブロック毎に符号化を継続するか否かを判断して符号化終了パスを導出し、符号化終了の情報と符号化終了パスを出力する。
次に動作について説明する。
レート制御情報抽出手段１０５以外の処理については上記実施の形態１と同様であり、ここでは、レート制御情報抽出手段１０５の処理について説明する。
エントロピー符号化手段１０３の処理と並行して、レート制御情報抽出手段１０５の歪計算手段１２１は、エントロピー符号化手段１０３からの各コードブロックにおいて、ある符号化パスの符号化が終了する度にその符号化パスと一つ前の符号化パスの符号化歪Ｄの歪差分ΔＤと、歪差分ΔＤを累積した符号化歪Ｄ＝Ｄ＋ΔＤを算出する。符号化歪Ｄとは、あるビットプレーンまでの符号を送ったときに再生画像に対する平均二乗誤差がどれだけ減少したかを示すもので、厳密に言えば符号化歪の減少量ということになる。従って、最終ビットプレーンまで歪差分ΔＤを累積するとその平均二乗誤差に等しくなる。
同時に、符号量計算手段１２２は、エントロピー符号化手段１０３からの各コードブロックにおいて、ある符号化パスの符号化が終了する度にその符号化パスでの符号量Ｒの出力バイト数ΔＲと、出力バイト数ΔＲを累積した符号量Ｒ＝Ｒ＋ΔＲを算出する。
これらの歪差分ΔＤを累積した符号化歪Ｄ、出力バイト数ΔＲを累積した符号量Ｒは、サブバンド、コードブロック、符号化パス等々のインデックスが付与された後、レート歪メモリ１２３に格納される。
傾き計算手段１２４は、レート歪メモリ１２３に格納されている符号化パス毎の符号化歪Ｄにより歪差分ΔＤを求め、レート歪メモリ１２３に格納されている符号化パス毎の符号量Ｒにより出力バイト数ΔＲを求め、歪差分ΔＤを出力バイト数ΔＲで除算することにより、現符号化パスにおけるＲＤ曲線の傾きＳを算出し、符号化歪Ｄ、符号量Ｒと同一の符号化パスの傾きＳであることがわかるレート歪メモリ１２３の位置に格納する。
第１２図はレート歪メモリ１２３に格納されているＲＤテーブルのデータ構造を示す図であり、サブバンドやコードブックに対応して、各符号化パスのパス番号、符号化歪Ｄ、符号量Ｒ、傾きＳ及びフラグが格納されている。なお、フラグについては後述する。
符号化終了パス導出手段１２５は、現符号化パス以前の符号化パスで現符号化パスとのＲＤ曲線の傾きＳが現符号化パス以前の符号化パスにおける傾きＳよりも小さくなる符号化パスと現符号化パス間での歪差分ΔＤと出力バイト数ΔＲの比を現符号化パスの傾きＳと補正し、各コードブロックの符号量Ｒの総和を示す画面全体の総号量Ｒｓｕｍと現符号化パスの補正した傾きＳと与えられたレート制御パラメータの逆数λ−１に基づき、そのコードブロックでの符号化をさらなる符号化パスまで続行するか否かを判断し、判断結果をエントロピー符号化手段１０３に出力する。続行するならばエントロピー符号化手段１０３は、次の符号化パスを符号化し、歪計算手段１２１はその符号化パスでの歪差分ΔＤと歪差分ΔＤを累積したコードブロックでの符号化歪Ｄを計算し、符号量計算手段１２２はその符号化パスでの出力バイト数ΔＲと出力バイト数ΔＲを累積したコードブロックでの符号量Ｒをカウントし、傾き計算手段１２４はその符号化パスでのＲＤ曲線の傾きＳを算出し、符号化終了パス導出手段１２５は、現符号化パス以前の符号化パスで現符号化パスとのＲＤ曲線の傾きＳが現符号化パス以前の符号化パスにおける傾きＳよりも小さくなる符号化パスと現符号化パス間での歪差分ΔＤと出力バイト数ΔＲの比を現符号化パスの傾きＳと補正し、各コードブロックの符号量Ｒの総和を示す画面全体の総符号量Ｒｓｕｍと現符号化パスの補正した傾きＳとレート制御パラメータの逆数λ−１に基づき、再度、そのコードブロックでの符号化をさらなる符号化パスまで続行するか否かを判断する。符号化を続行しないならば、符号化終了の情報をエントロピー符号化手段１０３に出力し、符号化終了パスを符号データ抽出手段１０６に出力する。
符号データ抽出手段１０６は、各コードブロックにおける符号化終了パスで定まる符号化パスまでの符号データを符号メモリ１０４から読み出し、各コードブロックに含まれる符号化パス数を付加情報として付け加えた後、それらを指定された順に並べて、所定のヘッダ情報を付加した上で符号ストリームとして出力する。
ここで、傾き計算手段１２４及び符号化終了パス導出手段１２５の処理の詳細について説明する。この実施の形態２では、ある符号化パスにおける傾きＳを算出するたびに、必ずそれまでの傾きＳより小さくなるよう傾きを補正する処理行う。
第１３図はこの発明の実施の形態２による画像符号化装置の処理の流れを示すフローチャートである。
上記実施の形態１と同様に、レート制御パラメータλの候補λ（ｔ）を以下のように設定する。
λ（ｔ）＝｛λ（０），λ（１），λ（２），・・・λ（ｔｍａｘ）｝
ここで、各レート制御パラメータの候補λ（ｔ）の値は単調増加となるよう設定されており、λ（ｔ）＜λ（ｔ＋１）である。すなわち、各レート制御パラメータの候補λ（ｔ）の逆数λ（ｔ）−１の値は単調減少となるよう設定されている。
第１３図のステップＳＴ１２１において、エントロピー符号化手段１０３は次の初期設定を行う。すなわち、レート制御パラメータλのインデックスｔの初期値をｔ＝０（ｔ＝０〜ｔｍａｘ）とし、コードブロックのインデックスｉ＝０（ｉ＝０〜ｉｍａｘ）とし、総符号量のカウンタＲｓｕｍ＝０とし、各コードブロックにおける符号化パスを記憶する変数ｋ（ｉ）を全てコードブロックについて−１（ゼロビットプレーンをスキップした次のパスのインデックスが０、ｋ（ｉ）＝−１〜ｋｍａｘ、カウンタの都合上、初期値はｋ（ｉ）＝−１とする）とする。
なお、レート制御情報抽出手段１０５にはそのメモリを図示はしないが、ｋ（ｉ）はコードブロック毎に符号化パスを記憶する変数であり、レート制御パラメータλのインデックスｔ、コードブロックのインデックスｉ、総符号量のカウンタＲｓｕｍは全コードブロックで共通の変数である。
ステップＳＴ１２２において、符号化終了パス導出手段１２５は各コードブロックの各符号化パスでのＲＤ曲線の傾きＳを記憶するか否かを示す全ての変数ｆｌａｇ（ｉ，ｋ）の値を全て１、すなわち有効にセットする。
ステップＳＴ１２３において、符号化終了パス導出手段１２５はＳ（ｉ，ｋ（ｉ））≧λ（ｔ）−１であるかを判断する。このステップＳＴ１２３はレート制御パラメータの候補λ（ｔ）が更新された際に新たな符号化パスを符号化する必要があるか否かを判断するための処理なので、最初は必ずＳ（ｉ，ｋ（ｉ））≧λ（ｔ）−１となるようにＳ（ｉ、−１）を十分大きな値に設定しておく。ステップＳＴ１２４において、エントロピー符号化手段１０３は変数ｋ（ｉ）をインクリメントし最初の符号化パスの符号化に備える。
ステップＳＴ１２５において、エントロピー符号化手段１０３はコードブロックｉにおける符号化対象の符号化パスｋ（ｉ）を符号化する。
ステップＳＴ１２６において、歪計算手段１２１は現符号化コードブロックｉにおける現符号化パスでの符号化歪Ｄの歪差分ΔＤ（ｉ，ｋ（ｉ））と歪差分ΔＤ（ｉ，ｋ（ｉ））を累積した符号化歪Ｄ（ｉ，ｋ（ｉ））を算出して、符号化歪Ｄ（ｉ，ｋ（ｉ））をレート歪メモリ１２３に格納し、符号量計算手段１２２は現符号化コードブロックｉにおける現符号化パスでの出力バイト数ΔＲ（ｉ，ｋ（ｉ））と出力バイト数ΔＲ（ｉ，ｋ（ｉ））を累積した符号量Ｒ（ｉ，ｋ（ｉ））を算出して、符号量Ｒ（ｉ，ｋ（ｉ））をレート歪メモリ１２３に格納する。
ステップＳＴ１２７において、符号化終了パス導出手段１２５は、現符号化パス以前で最も近い有効符号化パスのインデックスｐを第１２図のＲＤテーブルのｆｌａｇ（ｉ，ｋ）が１の符号化パスを検出することにより導出する。ここで、有効符号化パスとは、現符号化パスのＲＤ曲線の傾きＳが前の符号化パスの傾きＳに対して小さく単調減少となっている前の符号化パスのことである。
ステップＳＴ１２８において、符号化終了パス導出手段１２５は、次の計算式により現符号化パスとインデックスｐの有効符号化パスとのＲＤ曲線の傾きＳを算出する。
ΔＤ（ｉ，ｋ（ｉ））＝Ｄ（ｉ，ｋ（ｉ））−Ｄ（ｉ，ｐ）
ΔＲ（ｉ，ｋ（ｉ））＝Ｒ（ｉ，ｋ（ｉ））−Ｒ（ｉ，ｐ）
Ｓ（ｉ，ｋ（ｉ））＝ΔＤ（ｉ，ｋ（ｉ））／ΔＲ（ｉ，ｋ（ｉ））
なお、最初の符号化パス０については、傾きＳを十分大きな値に設定しておくものとする。
ステップＳＴ１２９において、符号化終了パス導出手段１２５は、現符号化パスでの傾きＳ（ｉ，ｋ（ｉ））と前有効符号化パスでの傾きＳ（ｉ，ｐ（ｉ））との大小を判定する。現符号化パスでの傾きＳ（ｉ，ｋ（ｉ））が前有効符号化パスでの傾きＳ（ｉ，ｐ（ｉ））より大きい場合には、ステップＳＴ１３０において、符号化終了パス導出手段１２５は、前有効符号化パスを無効とし、第１２図のフラグを１から０に設定する。そして、ステップＳＴ１２７に戻って現符号化パスとの傾きが単調減少となるまで更に以前の符号化済みの有効符号化パスを探す。
第１４図はＲＤ曲線の傾きＳの補正を示す図である。第１４図において、横軸は符号量Ｒ（ｋ）を示し、縦軸は符号化歪Ｄ（ｋ）を示し、０〜４はパス番号０〜４の符号化パスを示し、Ｓ（１），Ｓ（２），Ｓ（３），Ｓ（４）は、それぞれパス番号１〜４の符号化パスの傾きを示している。この場合には、パス番号０の符号化パスからパス番号４の符号化パスの全てが有効符号化パスとしてセットされていたが、現符号化パスであるパス番号４の符号化パスの傾きＳ（４）が、現符号化パス以前で最も近い有効符号化パスであるパス番号３の符号化パスの傾きＳ（３）より大きくなることが判明したので、パス番号３の符号化パスを無効にセットとして、パス番号４の現符号化パスの傾きをパス番号２の符号化パスとの傾きＳ（４）’となるように補正する。この補正をしても、まだ傾きＳが単調減少とならない場合には、さらに以前の符号化パスの傾きＳに対して単調減少となるまで符号化パスを無効とする。
第１３図のステップＳＴ１２９において、現符号化パスでの傾きＳ（ｉ，ｋ（ｉ））が前有効符号化パスでの傾きＳ（ｉ，ｐ（ｉ））より小さいと判定された場合には、ステップＳＴ１３１において、符号化終了パス導出手段１２５は、総符号量のカウンタＲｓｕｍに、現符号化パスでの発生符号量Ｒ（ｉ，ｋ（ｉ）−Ｒ（ｉ，ｋ（ｉ）−１）を加算して、現符号化パスまでの総符号量Ｒｓｕｍを算出する。ステップＳＴ１３２において、符号化終了パス導出手段１２５は、総符号量のカウンタＲｓｕｍが目標符号量Ｒｍａｘに達しているか否かを判断し、総符号量のカウンタＲｓｕｍが目標符号量Ｒｍａｘに達していたならば、各コードブロックで、符号化終了の情報をエントロピー符号化手段１０３に出力し、各コードブロックで、どの符号化パスまで符号化したかの符号化終了を示す符号化パスｋ（ｉ）を符号化終了パスとして符号データ抽出手段１０６に出力する。
ステップＳＴ１３２において、総符号量のカウンタＲｓｕｍが目標符号量Ｒｍａｘに達していないならば、ステップＳＴ１３３において、符号化終了パス導出手段１２５は現符号化パスでの有効符号化パスに対する傾きＳ（ｉ，ｋ（ｉ））とレート制御パラメータの逆数λ（ｔ）−１との大小を判断し、傾きＳ（ｉ，ｋ（ｉ））が大きければ、符号化終了パス導出手段１２５はエントロピー符号化手段１０３に通知し、ステップＳＴ１２４に戻って、エントロピー符号化手段１０３はさらに次の符号化パスを符号化する。ステップＳＴ１３３において、傾きＳ（ｉ，ｋ（ｉ））がλ（ｔ）−１未満になったならば、符号化終了パス導出手段１２５はエントロピー符号化手段１０３に通知し、エントロピー符号化手段１０３は符号化済みの符号化パスの符号データを一旦、符号メモリ１０４に保存し、このコードブロックの符号化を中断する。ステップＳＴ１３４において、コードブロックインデックスｉがｉｍａｘでなければ、ステップＳＴ１３５において、エントロピー符号化手段１０３はコードブロックインデックスｉをインクリメントして、次のコードブロックの符号化に処理を移す。
次のコードブロックでも同様に、ステップＳＴ１２５〜ＳＴ１３３を繰り返し、傾きＳ（ｉ，ｋ（ｉ））がレート制御パラメータの逆数λ（ｔ）−１未満となるまで符号化を行う。ステップＳＴ１３４において、これを全てのコードブロックに対して行った後、ステップＳＴ１３６において、エントロピー符号化手段１０３はレート制御パラメータλのインデックスｔをインクリメントし、レート制御パラメータλを次の候補に設定して、再度全コードブロックの符号化を傾きＳ（ｉ，ｋ（ｉ））がレート制御パラメータの逆数λ（ｔ）−１未満となるまで行う。なお、レート制御パラメータの候補λ（ｔ）を更新しても、Ｓ（ｉ，ｋ（ｉ））＜λ（ｔ）−１となり、つまり更新後のレート制御パラメータの逆数λ（ｔ）−１が既に符号化済みの符号化パスにおける傾きＳ（ｉ，ｋ（ｉ））より大きい場合がある。その場合は、次の符号化パスの符号化を行わないので、ステップＳＴ１２３において更新後のレート制御パラメータの逆数λ（ｔ）−１が符号化済みの符号化パスにおける傾きＳ（ｉ，ｋ（ｉ））より大きいことを検出し、符号化処理をスキップしてステップＳＴ１３３に移行する。
この実施の形態２では、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達するまで符号化を行っているが、目標符号量Ｒｍａｘの代わりに目標符号化歪を設定し、画面全体における各コードブロックの符号化歪Ｄの総和が目標符号化歪に達するまで符号化を行うことも可能である。
このように、実施の形態２のレート制御情報抽出手段１０５は、現符号化パス以前の符号化パスで現符号化パスとのＲＤ曲線の傾きＳが現符号化パス以前の符号化パスにおける傾きＳよりも小さくなる符号化パスと現符号化パス間での歪差分ΔＤと出力バイト数ΔＲの比を現符号化パスの傾きＳと補正し、各コードブロックの符号量Ｒの総和を示す総符号量Ｒｓｕｍ、又は各コードブロックの符号化歪Ｄの総和を算出し、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達した場合、又は各コードブロックの符号化歪Ｄの総和が目標符号化歪に達した場合に、符号化終了と判断すると共に、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達しない場合、又は符号化歪Ｄの総和が目標符号化歪に達しない場合には、補正した傾きＳが与えられたレート制御パラメータの逆数λ−１より小さくなるまで、そのコードブロックにおける各符号化パスの符号化を行わせ、補正した傾きＳがレート制御パラメータの逆数λ−１より小さくなった場合に、次のコードブロックにおける各符号化パスの符号化を行わせ、全てのコードブロックにおける各符号化パスの符号化が終了した場合に、与えられているレート制御パラメータの逆数λ−１より単調減少の値を示す他のレート制御パラメータの逆数λ−１を使用して、どのコードブロックにおけるどの符号化パスまで符号化するかを判断する。
以上のように、この実施の形態２によれば、実際に符号化結果を出力する符号化パスのみを対象として符号化を行うため、全ての符号化パスを符号化する従来方法に比べて、エントロピー符号化に要する演算量を低減することができるという効果が得られる。また、累積符号量が目標値に達した段階で符号化を終了するので、総符号量を目標符号量に合わせ込むために収束演算を行う必要がなく、レート制御に必要な演算量を低減することができるという効果が得られる。
さらに、あるパスまで符号化を進めて傾きＳを算出するたびに、それまでの傾きＳより小さくなるよう傾きを補正する処理を加えることにより、上記実施の形態１に比べ、より最適に近い符号化パスで各コードブロックの符号化を打ち切ることができるという効果が得られる。
実施の形態３．
上記実施の形態１及び上記実施の形態２では、レート制御パラメータλに応じた切り捨てポイントを算出するにあたり、ＲＤ曲線の傾きＳを除算により算出したが、場合によっては、この除算による演算が大きな負荷となる場合がある。そこで、この実施の形態３では、
Σ（Ｒ（ｉ，ｋ）−λＤ（ｉ，ｋ））
が最大となるポイントを探す、つまり各コードブロックで、次式の傾き指標値Ｆが最大となるポイントを探すことにより除算を回避し、レート制御の演算負荷の低減を図る方法を説明する。
Ｆ＝Ｒ（ｉ，ｋ）−λＤ（ｉ，ｋ）
この発明の実施の形態３による画像符号化装置の構成を示すブロック図は、上記実施の形態１の第４図と同じである。
第１５図はこの発明の実施の形態３による画像符号化装置のレート制御情報抽出手段１０５の内部構成を示すブロック図である。このレート制御情報抽出手段１０５は歪計算手段１３１、符号量計算手段１３２、レート歪メモリ１３３、傾き指標値計算手段１３４及び符号化終了パス導出手段１３５を備えている。
このレート制御情報抽出手段１０５は、各コードブロックの符号量Ｒの総和を示す総符号量Ｒｓｕｍ、各コードブロックの符号量Ｒ、各コードブロックの符号化歪Ｄ、及び各値が単調増加となっている与えられた複数のレート制御パラメータλに基づき、どのコードブロックにおけるどの符号化パスまでエントロピー符号化手段１０３が符号化するかを判断し、符号化終了となる符号化終了パスを出力する。
第１５図において、歪計算手段１３１は、エントロピー符号化手段１０３からの符号化パス毎にその符号化パスと一つ前の符号化パスにおける符号化歪Ｄの歪差分ΔＤと、歪差分ΔＤを累積した符号化歪Ｄを計算する。符号量計算手段１３２は、エントロピー符号化手段１０３からの符号化パス毎にその符号化パスでの符号量Ｒの出力バイト数ΔＲと、出力バイト数ΔＲを累積した符号量Ｒをカウントする。レート歪メモリ１３３は歪差分ΔＤを累積した符号化歪Ｄ、出力バイト数ΔＲを累積した符号量Ｒ及びその傾き指標値Ｆ等を符号化パス毎に格納する。傾き指標値計算手段１３４は符号化歪Ｄ、符号量Ｒ及びレート制御パラメータλに基づき傾き指標値Ｆを算出する。符号化終了パス導出手段１３５は、、各コードブロックの符号量Ｒの総和を示す画面全体の総符号量Ｒｓｕｍと傾き指標値計算手段１３４により計算された傾き指標値Ｆに基づき、各コードブロック毎に符号化を継続するか否かを判断して符号化終了パスを導出し、符号化終了の情報と符号化終了パスを出力する。
次に動作について説明する。
エントロピー符号化手段１０３の処理と並行して、歪計算手段１３１は、各コードブロックにおいてある符号化パスの符号化が終了する度にその符号化パスと前符号化パスとの符号化歪Ｄの歪差分ΔＤと歪差分ΔＤを累積した符号化歪Ｄ＝Ｄ＋ΔＤを算出する。
同時に、符号量計算手段１３２は、各コードブロックにおいて、ある符号化パスの符号化が終了する度にその符号化パスでの出力バイト数ΔＲと出力バイト数ΔＲを累積した符号値Ｒ＝Ｒ＋ΔＲを算出する。これらの符号化歪Ｄ、符号量Ｒは、サブバンド、コードブロック、符号化パス等々のインデックスが付与された後、レート歪メモリ１３３に格納される。
また、傾き指標値計算手段１３４は符号化歪Ｄ、符号量Ｒ及びレート制御パラメータλに基づきその傾き指標値Ｆを計算し、符号化歪Ｄ、符号量Ｒと同一の符号化パスの傾き指標値であることがわかるレート歪メモリ１３３の位置に格納する。
第１６図はレート歪メモリ１３３に格納されているＲＤテーブルのデータ構造を示す図であり、サブバンド及びコードブックに対応して、パス番号、符号化歪Ｄ、符号量Ｒ、傾き指標値Ｆが格納されている。
符号化終了パス導出手段１３５は、各コードブロックの符号量Ｒの総和を示す画面全体の総符号量Ｒｓｕｍと傾き指標値Ｆから、そのコードブロックでの符号化をさらなる符号化パスまで続行するか否かを判断し、判断結果をエントロピー符号化手段１０３に出力する。続行するならばエントロピー符号化手段１０３は、次の符号化パスを符号化し、歪計算手段１３１は、その符号化パスと前符号化パスとの符号化歪Ｄの歪差分ΔＤと歪差分ΔＤを累積した符号化歪Ｄを算出し、符号量計算手段１３２は、その符号化パスでの出力バイト数ΔＲと出力バイト数ΔＲを累積した符号量Ｒを算出し、傾き指標値計算手段１３４はその符号化パスでの傾き指標値Ｆを算出する。符号化終了パス導出手段１３５は再度、符号化をさらなる符号化パスまで続行するか否かを判断する。符号化を続行しないならば、符号化終了の情報をエントロピー符号化手段１０３に出力し、符号化終了パスを符号データ抽出手段１０６に出力する。
符号データ抽出手段１０６は、各コードブロックにおける符号化終了パスで定まる符号化パスまでの符号データを符号メモリ１０４から読み出し、各コードブロックに含まれる符号化パス数を付加情報として付け加えた後、それらを指定された順に並べて、所定のヘッダ情報を付加した上で符号ストリームとして出力する。
第１７図はこの発明の実施の形態３による画像符号化装置の処理の流れを示すフローチャートである。
上記実施の形態１及び上記実施の形態２と同様に、レート制御パラメータの候補λ（ｔ）を以下のように設定する。
λ（ｔ）＝｛λ（０），λ（１），λ（２），・・・λ（ｔｍａｘ）｝
ここで、各レート制御パラメータの候補λ（ｔ）の値は単調増加となるよう設定されており、λ（ｔ）＜λ（ｔ＋１）である。
第１７図のステップＳＴ１４１において、エントロピー符号化手段１０３は、レート制御パラメータλのインデックスｔの初期値をｔ＝０（ｔ＝０〜ｔｍａｘ）とし、コードブロックのインデックスｉ＝０（ｉ＝０〜ｉｍａｘ）とし、総符号量のカウンタＲｓｕｍ＝０とし、各コードブロックにおける符号化パスを記憶する変数ｋ（ｉ）を全てコードブロックについて−１（ゼロビットプレーンをスキップした次のパスのインデックスが０、ｋ（ｉ）＝−１〜ｋｍａｘ、カウンタの都合上、初期値はｋ（ｉ）＝−１とする）とする。
なお、レート制御情報抽出手段１０５にはそのメモリを図示はしないが、変数ｋ（ｉ）はコードブロック毎に符号化パスを記憶する変数であり、レート制御パラメータλのインデックスｔ、コードブロックのインデックスｉ、総符号量のカウンタＲｓｕｍは全コードブロックで共通の変数である。
ステップＳＴ１４２において、エントロピー符号化手段１０３は設定されているコードブロックにおける符号化パスを符号化し、歪計算手段１３１はその符号化パスと前符号化パスとの符号化歪Ｄの歪差分ΔＤと歪差分ΔＤを累積した符号化歪Ｄを算出し、符号量計算手段１３２は符号化パスにおける出力バイト数ΔＲと出力バイト数ΔＲを累積した符号量Ｒを算出し、傾き指標値計算手段１３４は、その時点でのレート制御パラメータの候補λ（ｔ）から、符号化済みの符号化パスに関する傾き指標値Ｆを算出してレート歪メモリ１３３に格納する。
ステップＳＴ１４３において、符号化終了パス導出手段１３５はそのコードブロックで傾き指標値Ｆが最大となる符号化パスＫＬを導出する。ステップＳＴ１４４において、符号化終了パス導出手段１３５は傾き指標値Ｆが最大となる符号化パスＫＬが現在の符号化パスｋ（ｉ）であるか否かを判断する。なお、ステップＳＴ１４３，ＳＴ１４４の処理は、レート制御パラメータの候補λ（ｔ）が更新された際に新たな符号化パスを符号化する必要があるか否かを判断するための処理なので、最初は必ずＫＬ＝ｋ（ｉ）となるように設定しておく。
ステップＳＴ１４５において、エントロピー符号化手段１０３はｋ（ｉ）をインクリメントし、最初の符号化パスの符号化に備える。
ステップＳＴ１４６において、エントロピー符号化手段１０３はコードブロックｉにおける符号化対象の符号化パスｋ（ｉ）を符号化し、ステップＳＴ１４７において、歪計算手段１３１は現符号化パスと前符号化パスとの符号化歪Ｄの歪差分ΔＤ（ｉ，ｋ（ｉ））より歪差分ΔＤ（ｉ，ｋ（ｉ））を累積した符号化歪Ｄ（ｉ，ｋ（ｉ））を算出して、符号化歪Ｄ（ｉ，ｋ（ｉ））をレート歪メモリ１３３に格納し、符号量計算手段１３２は現符号化パスにおける出力バイト数ΔＲ（ｉ，ｋ（ｉ））より出力バイト数ΔＲ（ｉ，ｋ（ｉ））を累積した符号量Ｒ（ｉ，ｋ（ｉ））を算出してレート歪メモリ１３３に格納する。
ステップＳＴ１４８において、傾き指標値計算手段１３４は、現符号化パスでの傾き指標値Ｆ（ｉ，ｋ）を次の式により算出してレート歪メモリ１３３に格納する。
Ｆ（ｉ，ｋ）＝Ｒ（ｉ，ｋ（ｉ））−λ（ｔ）・Ｄ（ｉ，ｋ（ｉ））
ステップＳＴ１４９において、符号化終了パス導出手段１３５は、レート歪メモリ１３３を参照して、現コードブロックの符号化済みの符号化パスの中で、傾き指標値Ｆ（ｉ，ｋ）が最大となる符号化パスｋＬを導出する。
ステップＳＴ１５０において、符号化終了パス導出手段１３５は、傾き指標値Ｆ（ｉ，ｋ）が最大となる符号化パスｋＬが現符号化パスｋ（ｉ）であるか否かを判断し、符号化パスｋＬが現符号化パスｋ（ｉ）であれば、ステップＳＴ１４５に戻って、さらに次の符号化パスを符号化する。符号化パスｋＬが現符号化パスでなければ、ステップＳＴ１５１において、符号化終了パス導出手段１３５は、現符号化パスの一つ前の符号化パスが傾き指標値Ｆ（ｉ，ｋ）の最大値を与える符号化パスｋＬであったと判断し、この時点でのコードブロックｉの一つ前の符号化パスを符号化終了パスとして導出し、符号化パスｋＬを符号化終了パスとして変数ｋ（ｉ）に保存し、このコードブロックでの符号化を中断させる。
ステップＳＴ１５２において、符号化終了パス導出手段１３５は、総符号量のカウンタＲｓｕｍに、現符号化パスでの発生符号量Ｒ（ｉ，ｋ（ｉ））−Ｒ（ｉ，ｋ（ｉ）−１）を加算して、現符号化パスまでの総符号量Ｒｓｕｍを算出する。ステップＳＴ１５３において、符号化終了パス導出手段１３５は総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達しているか否かを判断し、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達していたならば、符号化はここの時点で終了と判断し、符号化終了の情報をエントロピー符号化手段１０３に出力し、各コードブロックで、どの符号化パスまで符号化したかの情報である符号化パスｋ（ｉ）を符号化終了パスとして符号データ抽出手段１０６に出力する。
ステップＳＴ１５３において、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達していないならば、ステップＳＴ１５４，ＳＴ１５５において、エントロピー符号化手段１０３は、全てのコードブロックについて、次のコードブロックでも同様に、最大の傾き指標値Ｆを与える符号化パスが符号化した最後の符号化パスでなくなるまで符号化を行い、ステップＳＴ１５６において、エントロピー符号化手段１０３は、レート制御パラメータλのインデックスｔをインクリメントし、レート制御パラメータλを次の候補に設定して、再度、全コードブロックの符号化を傾き指標値Ｆが最大となる符号化パスが現符号化パスでなくなるまで行う。
なお、レート制御パラメータの候補λ（ｔ）を更新しても、傾き指標値Ｆの最大値を与える符号化パスＫＬがその時点での最終符号化パスとならない場合がある。その場合は、次の符号化パスの符号化を行わないので、ステップＳＴ１４３、ＳＴ１４４において、符号化終了パス導出手段１３５は傾き指標値Ｆの最大値を与える符号化パスＫＬがその時点での最終符号化パス符号化済みの符号化パスでないことを検出して符号化処理をスキップする。
この実施の形態３では、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達するまで符号化を行っているが、目標符号量Ｒｍａｘの代わりに目標符号化歪を設定し、画面全体における各コードブロックの符号化歪Ｄの総和が目標符号化歪に達するまで符号化を行うことも可能である。
このように、この実施の形態３のレート制御情報抽出手段１０５は、コードブロックの符号量Ｒと、コードブロックの符号化歪Ｄとレート制御パラメータλの積との和により各符号化パスの傾き指標値Ｆを算出し、あるコードブロックで傾き指標値Ｆが最大となる符号化パスを導出し、導出した傾き指標値Ｆが最大となる符号化パスが現在符号化している符号化パスでなくなるまで、そのコードブロックにおける符号化パスの符号化を行わせ、各コードブロックの総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達した場合、又は各コードブロックの符号化歪Ｄの総和が目標符号化歪に達した場合に、符号化終了と判断すると共に、総符号量Ｒｓｕｍが目標符号量Ｒｍａｘに達しない場合、又は符号化歪Ｄの総和が目標符号化歪に達しない場合には、次のコードブロックにおける各符号化パスの符号化を行わせ、全てのコードブロックにおける各符号化パスの符号化が終了した場合に、与えられているレート制御パラメータλより単調増加の値を示す他のレート制御パラメータλを使用して、どのコードブロックにおけるどの符号化パスまで符号化するかを判断する。
以上のように、この実施の形態３によれば、実際に符号化結果を出力する符号化パスのみを対象として符号化を行うため、全ての符号化パスを符号化する従来方法に比べて、エントロピー符号化に要する演算量を低減することができるという効果が得られる。また、総符号量が目標値に達した段階で符号化を終了するので、総符号量を目標符号量に合わせ込むために収束演算を行う必要がなく、レート制御に必要な演算量を低減することができるという効果が得られる。
さらに、この実施の形態３では、除算を使用して傾きＳを算出するのではなく、乗算から算出される傾き指標値Ｆを使用するために、上記実施の形態１及び上記実施の形態２に比べ、レート制御における除算の演算負荷をより低減することができるという効果が得られる。
【産業上の利用可能性】  以上のように、この発明に係る画像符号化装置は、エントロピー符号化及びレート制御に要する演算量を低減するのに適している。
【図１】
0004322920.tif 000002
【図２】
0004322920.tif 000003
【図３】
0004322920.tif 000004
【図４】
0004322920.tif 000005
【図５】
0004322920.tif 000006
【図６】
0004322920.tif 000007
【図７】
0004322920.tif 000008
【図８】
0004322920.tif 000009
【図９】
0004322920.tif 000010
【図１０】
0004322920.tif 000011
【図１１】
0004322920.tif 000012
【図１２】
0004322920.tif 000013
【図１３】
0004322920.tif 000014
【図１４】
0004322920.tif 000015
【図１５】
0004322920.tif 000016
【図１６】
0004322920.tif 000017
【図１７】
0004322920.tif 000018