(57)【要約】      （修正有）【課題】画像データの入力を行ないながら、オーバヘッドを抑制し、且つ、所定の上限データ量に収まるように圧縮符号化を行う。【解決手段】符号化部１２は、符号化パラメータＱ０による符号化データ列３２ａ、Ｑ０よりも圧縮率の高いＱ１による符号化データ列３２ｂを出力する。符号化データ列３２ｂは、メモリ１６に一時的に蓄積される。符号化データ量計測部１５によって計測している符号化データ列３２ａのデータ量が上限値に達すると、符号化データ列３２ａの破棄を行わせ、メモリ１６に蓄積された符号化データ列３２ｂを出力すると共に、符号化部１２に対し符号化パラメータＱ０に代わって、符号化パラメータＱ１での符号化データ３２ａを生成させる。また、符号化データ列３２ｂを生成するための新たな符号化パラメータＱｉを符号化部１２に設定すると、共にメモリ１６に蓄積された符号化データ列を新たな符号化パラメータＱｉで再符号化させる。【選択図】  図１
2004247942.tif 000002
【特許請求の範囲】
【請求項１】
画像データを圧縮符号化する画像符号化方法であって、
符号化データ量を決定する第１の符号化パラメータと、該第１の符号化パラメータによる符号化データ量よりも少ない符号化データ量となる第２の符号化パラメータを設定可能で、前記第１の符号化パラメータによる符号化データを主符号化データとして生成し、前記第２の符号化パラメータによる符号化データを予備符号化データとして生成し出力する符号化工程と、
前記第２の符号化パラメータにより生成された予備符号化データを所定の記憶手段に蓄積する蓄積工程と、
設定された符号化パラメータに従い、前記記憶手段に記憶された符号化データを再符号化する再符号化工程と、
前記主符号化データの符号量が、所定の上限データ量に達したか否かを判定する判定工程と、
該判定工程によって前記主符号化データの符号量が、前記上限データ量に達したと判定した場合、前記記憶手段に記憶された予備符号化データを前記上限データ量に達したと判定される以前の主符号化データとして出力すると共に、前記第１の符号化パラメータを前記第２の符号化パラメータで更新し、
前記符号化工程に設定された第２の符号化パラメータを新たな符号化パラメータで更新すると共に、前記再符号化工程に前記新たなパラメータを設定して再符号化を行わせるパラメータ更新工程とを備え、
前記パラメータ更新工程は、今回更新された第１の符号化パラメータによる符号化データが前記上限データ量に到達するまでの予測時間と、次回に第１の符号化パラメータとして設定される候補群それぞれによる前記上限データ量に到達する予測時間と、夫々の候補群における前記再符号化手段による再符号化に要する予測時間を演算する演算工程と、
該演算工程の演算結果に基づき、前記候補群の中の１つを前記第２の符号化パラメータと選択する選択工程を含む
ことを特徴とする画像符号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像データの圧縮技術に関するものである。
【０００２】
【従来の技術】
現在、静止画像に対する圧縮符号化処理機能は多くのデジタルイメージング機器に搭載されている。このデジタルイメージング機器としては、デジタルカラーコピー機等がその代表例をして挙げられる。
【０００３】
デジタルカラーコピー機の場合、原稿読み取り部から読取った画像をバッファリングし、印刷部に対してその画像を転送する際、その転送量を少なくしする目的で、圧縮してから転送することになるし、印刷部はそれを伸長（復号）して印刷することになる。すなわち、読取部には圧縮機能、印刷部にはそれを復号する機能が搭載されるようになってきている。
【０００４】
原稿読取部の後段に設けられる圧縮符号化処理部によって生成される符号化された原稿画像データ列のデータ量は、圧縮符号化処理される前の原稿画像データ、すなわち読み取られた原稿画像データのデータ量に比べると数分の一から十数分の一程度に低減され得る。
【０００５】
符号化された原稿画像データ列の圧縮符号化処理される前の原稿画像データに対するデータ量の低減度、すなわち圧縮率の上限値は、符号化歪みが伸張復号化処理によって得られる再構成画像データから容易に視認できない程度の値がその許容される上限値として設定される。
【０００６】
一方、上記圧縮率の許容される下限値は、原稿読み取り部における単位時間あたりに読み込むことができる原稿画像データの最大データ量、および原稿読み取り部から印刷部に転送する際の圧縮符号化された原稿画像データ列の最大データ転送量、といったようなそのシステムにおける各種システム・パラメータによって一意に決定され得る。
【０００７】
このように圧縮率の許容される上限値或いは／および下限値が設定されたとしても、供給されるすべての原稿画像データに対する圧縮率をその範囲内に収めるように圧縮符号化処理を行なうことは容易で無い。
【０００８】
その理由は、量子化ステップに代表される符号化パラメータとして同一のものを用いて圧縮符号化処理を行なっても、得られる符号化された原稿画像データ列のデータ量は原稿画像データ毎に不定であること、言い換えるならば、読み取られた原稿画像データ毎にその圧縮率は変わってしまうことに起因する。
【０００９】
これは、読み取られた原稿画像データ毎にその画像データが有する情報の空間周波数から見た偏りおよびその度合いが異なり、そのような原稿画像データに対する圧縮符号化処理の中では、値が「０」である変換係数に対するランレングス符号化および可変長符号を用いたエントロピー符号化を行うためである。
【００１０】
従って、すべての原稿画像データに対する圧縮率をその許容される上限値以下（或いは／及び下限値以上）に収めるように圧縮符号化処理を施すためには、被圧縮符号化データ、すなわち供給される原稿画像データの各々に対して適用する符号化パラメータを適応的に変える必要がある。
【００１１】
一般的に圧縮率が一定になるように圧縮符号化処理を行なうためには、所謂、情報量制御あるいは符号量制御と称される符号化制御を実現しなければならない。
【００１２】
上記情報量制御の具体的な実現手法としては、フィードフォワード手法とフィードバック手法の大きくふたつの手法が知られている。
【００１３】
フィードフォワード手法とは、圧縮符号化処理を行なう前に被圧縮符号化データとして入力される原画像データから別途ダイナミック・レンジ、各種統計情報を算出して、それらの算出値を基に最適な符号化パラメータを予測した後、その得られた符号化パラメータを用いて実際の圧縮符号化処理を行なうものである。
【００１４】
これに対して、フィードバック手法とは、試行となる圧縮符号化処理を行なうことによって得られた符号化データ量の実測値から最適な符号化パラメータを予測した後、その得られた符号化パラメータを用いて最終的な圧縮符号化処理を行なうものである。
【００１５】
【発明が解決しようとする課題】
フィードバック手法の場合、圧縮符号化処理を試行することによって得られた符号化データ量の実測値から最適な符号化パラメータを予測するので、実際に得られた符号化データ量を直接的に予測値算出できる。かかる意味で、フィードフォワード手法に比べてより高い精度で目的とする符号化データ量を生成する符号化パラメータの予測値を得るのに都合が良い。しかし、このフィードバック手法は、原理的に、試行となる圧縮符号化処理のために費やされる時間的なオーバーヘッドが余計にかかってしまうという欠点がある。
【００１６】
本発明はかかる問題点に鑑みなされたものであり、画像を目標とするサイズ或いは上限値以内に納める際に、圧縮符号化処理のために費やされる時間的なオーバーヘッドの発生を許容範囲内にする技術を提供しようとするものである。
【００１７】
【課題を解決するための手段】
この課題を解決するため、例えば本発明の情報処理方法は以下のような工程を備える。すなわち、
画像データを圧縮符号化する画像符号化方法であって、
符号化データ量を決定する第１の符号化パラメータと、該第１の符号化パラメータによる符号化データ量よりも少ない符号化データ量となる第２の符号化パラメータを設定可能で、前記第１の符号化パラメータによる符号化データを主符号化データとして生成し、前記第２の符号化パラメータによる符号化データを予備符号化データとして生成し出力する符号化工程と、
前記第２の符号化パラメータにより生成された予備符号化データを所定の記憶手段に蓄積する蓄積工程と、
設定された符号化パラメータに従い、前記記憶手段に記憶された符号化データを再符号化する再符号化工程と、
前記主符号化データの符号量が、所定の上限データ量に達したか否かを判定する判定工程と、
該判定工程によって前記主符号化データの符号量が、前記上限データ量に達したと判定した場合、前記記憶手段に記憶された予備符号化データを前記上限データ量に達したと判定される以前の主符号化データとして出力すると共に、前記第１の符号化パラメータを前記第２の符号化パラメータで更新し、
前記符号化工程に設定された第２の符号化パラメータを新たな符号化パラメータで更新すると共に、前記再符号化工程に前記新たなパラメータを設定して再符号化を行わせるパラメータ更新工程とを備え、
前記パラメータ更新工程は、今回更新された第１の符号化パラメータによる符号化データが前記上限データ量に到達するまでの予測時間と、次回に第１の符号化パラメータとして設定される候補群それぞれによる前記上限データ量に到達する予測時間と、夫々の候補群における前記再符号化手段による再符号化に要する予測時間を演算する演算工程と、
該演算工程の演算結果に基づき、前記候補群の中の１つを前記第２の符号化パラメータと選択する選択工程を含むことを特徴とする。
【００１８】
【発明の実施の形態】
以下、添付図面に従って本発明に係る実施形態を説明する。なお、実施形態では圧縮技術としてＪＰＥＧを例にして説明することとするが、他の圧縮技術にも適用できることは、以下の説明から理解できよう。
【００１９】
先ず、本発明者は、図６に示すような画像圧縮符号化装置について考察した。以下に、その構成及び動作について説明する。
【００２０】
同図において、符号化部１０１は、例えばデジタル複写機が有する画像読取部からの画像データを、異なる２つの符号化パラメータに従って圧縮符号化したデータ１０１ａ、１０１ｂを出力する。ここで言う、符号化パラメータとは、実施形態では、ＪＰＥＧを例にしているので、ＤＣＴ変換して得た変換係数を量子化する「量子化ステップ」であると考えると分かりやすい。すなわち、以下の説明における「符号化パラメータＱ０、Ｑ１、…Ｑｉ」という表現は、「量子化ステップＱ０、Ｑ１、…Ｑｉ（Ｑ０＜Ｑ１＜…＜Ｑｉ）」を意図しているものとして説明する。
【００２１】
符号量の多い符号化データ列１０１ａ（符号化パラメータＱ０による符号データ列）は外部の不図示のバッファメモリ等の記憶装置へ出力され、符号量の少ない符号化データ列１０１ｂ（符号化パラメータＱ１による符号化データ列）はメモリ１０３へ出力される。
【００２２】
ここで、符号量の多い符号化データ量１０１ａがあらかじめ定められた上限値に達したとき（もしくは上限値を越えたときでも良い）、制御部１０２は、該当する符号化パラメータＱ０による符号化を打ち切り、既に出力されたデータを破棄させる。また、同時に、メモリ１０３には、符号化パラメータＱ１での符号データが蓄積されているので、それを出力し、符号化部１０１には、新たな量子化ステップＱ１、Ｑ２を設定する。この結果、これ以降に入力される画像データに対する符号化データ列１０１ａは符号化パラメータＱ１に基づくものとなり、上記上限値に達したと判断される以前のデータについては、メモリ１０３から出力させているので、あたかも最初から符号化パラメータＱ１で符号化したのと等価の出力がバッファに蓄積されることになる。
【００２３】
ここで、符号化データ列１０１ｂを生成する符号化パラメータをＱ１からＱ２に変更すると共に、メモリ１０３に既に記憶されている量子化ステップＱ１で符号化されているデータについて、量子化ステップＱ２で再符号化（一旦復号し、Ｑ２で符号化するという意味）を行うことが必要になる。
【００２４】
これ以降は、１ページの画像の入力が完了するまで、上記の処理を繰り返す。すなわち、符号化データ１０１ａがバッファに蓄積している最中に、１ページの画像の入力が完了したと判断した場合、その際にバッファに格納されているデータが、最終的な圧縮符号化データとして採用することになる。
【００２５】
図７は、横軸を時間とするバッファへ出力されるデータ（符号化データ１０１ａ）の量の推移の例を示している。
【００２６】
時刻ｔ１において、符号化パラメータＱ０を用いて符号化されたデータ列が上限値に達し、１回目の符号化パラメータ選択更新と再符号化処理が行われる。メモリ１０３に格納されていた符号化パラメータＱ１によって符号化された符号化データ列は、再符号化部１０４により再符号化され、時刻ｔ２で再符号化処理が終了する。次に、時刻ｔ３で符号化パラメータＱ１によって符号化された符号化データ列の総符号量が上限値に達したとき、２回目の符号化パラメータ選択と再符号化処理が行われる。
【００２７】
図示の如く、時刻ｔ３の以前に再符号化処理が完了しているので、２回目の符号化パラメータの選択更新処理と再符号化の開始については問題がない。
【００２８】
ところが、再符号化部１０４による再符号化処理が時刻ｔ５で終了する前の、時刻ｔ４において符号化パラメータＱ１によって符号化された符号化データ列の総符号量が上限値に達してしまうと、もはやそれ以降については正常な処理が望めない。従って、再符号化部１０４による再符号化処理が時刻ｔ５で終了するまで、符号化部１０１による符号化処理を停止しなければならない事態に陥る。
【００２９】
すなわち、時刻ｔ４から時刻ｔ５までの時間は、１枚の画像の符号化処理においてはオーバーヘッドとなり、画像符号化装置を組み込むシステムの性能の低下となって現れることになる。
【００３０】
以上が、本願発明者が考察した例である。本実施形態ではかかる問題を解決する。
【００３１】
図１は、本発明の実施形態の画像符号化装置の構成を示すブロック図である。図示に示す如く、本実施形態の画像符号化装置は、ブロック分割部１１、符号化部１２、上限値設定部１３、制御部１４、符号化データ量計測部１５、メモリ１６、符号化データ入出力制御部１７、有意係数計測部１８、再符号化部１９を備えるが、それぞれの構成の機能は以下の説明から明らかにする。
【００３２】
なお、以下の説明においても、ＪＰＥＧ符号化を例にして説明する。すなわち、符号化パラメータとは、量子化ステップを差すものであることに留意されたい。
【００３３】
本実施形態の画像符号化装置に原画像データ３１が入力されると、ブロック分割部１１によって原画像は所定の大きさのブロック（例えば８×８画素ブロックで、以下、単に「ブロック」と記す）に分割され、符号化部１２に入力される。符号化部１２は、符号化パラメータＱ０〜Ｑｎの中から、初期値として符号化パラメータＱ０とＱ１を用いて２つの符号化データ列３２ａ及び３２ｂを出力する。
【００３４】
同時に、符号化部１２は、符号化パラメータＱ０での符号化データ列中の有意係数（シンボル）の個数と、現在、非選択状態（仮符号化）の符号化パラメータＱ１での有意係数の個数を、付帯情報として出力する。
【００３５】
符号化データ列３２ａは画像符号化装置外部、例えばバッファメモリへ出力され、符号化データ列３２ｂはメモリ１６へ出力され、蓄積される。再符号化部１９は、制御部１４からの指示（新たな符号化パラメータを示す情報が含まれる）に従い、メモリ１６へ格納された符号化データ列を、指示された符号化パラメータ（Ｑ０〜Ｑｎの中の１つ）を用いて再符号化し、再符号化データ列３３をメモリ１６へ出力する。同時に、再符号化部１９は、再符号化データ列中の有意係数の個数と、現在選択されている符号化パラメータ以外で再符号化した場合の有意係数の個数を、付帯情報として出力する。
【００３６】
本実施形態の再符号化部１９は、入力される符号化データ列の可変長符号を復号化し、有意係数に対し量子化処理を行った後に可変長符号化するという手法で、再符号化処理を行う。よって、本実施形態の画像符号化装置において再符号化に要する時間は、再符号化部へ入力される符号化データ列中の有意係数の数に依存する。本実施形態の画像符号化装置においては、説明を簡単にするため、再符号化部１９の処理性能を１有意係数あたり１サイクルとし、１サイクル当たりΔｔ（既知）の時間を要するものとして説明する。
【００３７】
符号化データ量計測部１５は、符号化データ列３２ａ、３２ｂ及び再符号化データ列３３の符号化データ量を累積加算する。有意係数計測部１８は、符号化データ列３２ａ、３２ｂ及び再符号化データ列３３の有意係数（シンボル）と、符号化パラメータＱ２〜Ｑｎを用いて符号化したときの符号化データ列の有意係数を計測し累積加算する。上限値設定部１３には、符号化データ列の総符号化データ量の上限値が設定される。
【００３８】
従って、制御部１４は、前記上限値と前記符号化データ量累積加算値の比較結果に基づいて、ライン３２ａから出力された符号量（初期段階では符号化パラメータＱ０による符号量）が上限値に達しかか否かを監視できるようになる。また、上限値に達したと判断した場合には、それまでの符号化を打ち切り（外部に対して破棄指示情報を出力）、符号化部１２と再符号化部１９によって使用される符号化パラメータを選択した後に符号化部１２による符号化を再開すると共に、メモリ１６に既に格納されている符号化データ列を外部に出力し、更新後の符号化パラメータに従って画像圧縮を続行させる。
【００３９】
例えば、符号化データ列３２ａの総符号化データ量が前記上限値を超えた場合に、符号化パラメータの切り替えを行なう。
【００４０】
図３は時間とともに総符号化データ量が増加する様子を示している。横軸が時間を表し、縦軸が符号化データ列３２ａの総符号量を表している。図４は、ブロック分割部１１によって分割されたブロックの原画像データにおける符号化対象位置を示すものであり、図３におけるＢ１乃至Ｂ４と図４におけるＢ１乃至Ｂ４は共に同じタイミングである（厳密には、ブロック分割部１１と符号化部１２でのタイムディレイがある）。
【００４１】
図示の例では、画像符号化処理は時刻ｔ０で開始し、符号化部１２は符号化パラメータＱ０及びＱ１を用いて２つの符号化データ列を出力する。時刻ｔ１において図４のブロックＢ１まで符号化した時点で、符号化パラメータＱ０によって符号化された符号化データ列３２ａが上限値に達した（もしくは超えた）とする。
【００４２】
このとき、制御部１４は符号化パラメータＱ０による符号化を打ち切り、符号化データ列３２ａを生成するための符号化パラメータをＱ１に変更し、符号化データ列３２ｂに対する最適な符号化パラメータＱｘ（Ｑ２乃至Ｑｎのいずれか）を探索する。
【００４３】
図２は制御部１４が符号化パラメータを探索する処理手順（符号化データ列３２ａが上限値に達した場合の処理手順）を示すフローチャートである。以下、図３、図４を参照して説明する。
【００４４】
制御部１４は、時刻ｔ１までにブロックＢ１まで符号化を終えた時点で、符号化データ量計測部１５によって累積加算された符号化パラメータＱ１を用いた符号化データ列の総符号化データ量と、符号化パラメータＱ１における１ブロックあたりの平均符号化データ量を基に、符号化データ列３２ａが上限値を超える時刻ｔ３を予測する（ステップＳ１）。
【００４５】
より分かりやすく言えば、タイミングｔ１におけるメモリ１６に格納されていた符号化パラメータＱ１によるデータ量は判明しているので、原点（時間ｔ０）と時間ｔ１におけるメモリ１６に格納されていたデータ量を結ぶ直線と、上限値と交差する時間をｔ３として決定すればよい。
【００４６】
次いで、制御部１４は、図４のブロックＢ０からＢ１までを符号化パラメータＱｉ（ｉ＝２、３、４…で、最初は「２」として決定する）で画像データを符号化したときの時間ｔ１における符号化データ量予測値Ｌｉを、有意係数計測部１８によって累積加算された、符号化パラメータＱ１によって符号化された符号化データ列３２ｂの有意係数の総数と、符号化パラメータ候補Ｑｉを用いて符号化した場合の有意係数との比から求める（ステップＳ３）。
【００４７】
なお、本実施形態の画像符号化装置においては、符号化パラメータＱｉを用いて符号化されるブロックＢ０からＢ１までの符号化データ列は、メモリ１６に格納されている符号化データ列を再符号化部１９によって再符号化することにより生成される。
【００４８】
次に、制御部１４は、前記符号化データ量Ｌｉの予測値と、符号化パラメータ候補Ｑｉにおける１ブロックあたりの予測平均符号化データ量を基に、符号化パラメータＱｉを用いて符号化した符号化データ列の総符号量が上限値を超える時刻ｔ４を予測演算する（ステップＳ４）。
【００４９】
また、制御部１４は、有意係数計測部１８によって計測されている、ブロックＢ０からＢ１までを符号化パラメータ候補Ｑｉを用いて符号化したときの符号化データ列の有意係数の個数から、符号化パラメータ候補Ｑｉを用いて符号化されたブロックＢ０からＢ１までの符号化データ列を再符号化するのに要する時間Ｔｒを予測する（ステップＳ５）。符号化パラメータ候補Ｑｉを用いてブロックＢ０からＢ１までを符号化した場合の有意係数の値が１００００であるとすると、本実施形態の画像符号化装置においては、再符号化部の処理性能を１有意係数あたり１サイクルであるので、Ｔｒ＝１００００×Δｔとなる。
【００５０】
次に、制御部１４は、符号化パラメータ候補Ｑｉを用いて符号化した符号化データ列をさらに再符号化したときに前記時刻ｔ４で終了するような再符号化開始時刻ｔ２を以下に説明する手順で求める（ステップＳ６）。
【００５１】
前記時刻ｔ２までに符号化部１２によって符号化されるブロックの個数Ｎとする。符号化パラメータ候補Ｑｉを用いて符号化された符号化データ列を再符号化するのに必要な１ブロックあたりの平均再符号化所要時間をＴａとする（予めテーブル化させておく）。符号化部１２にブロックが入力される平均周期をＴｅとする。
【００５２】
前記時刻ｔ２から前記時刻ｔ４までの時間（ｔ４−ｔ２）は、以下の式（１）で表される。
ｔ４−ｔ２＝Ｔｒ＋Ｔａ×Ｎ  ・・・（１）
また、時間（ｔ４−ｔ２）は以下の式（２）でも表される。
ｔ４−ｔ２＝ｔ４−Ｔｅ×Ｎ  ・・・（２）
前記（１）及び（２）から、前記時刻ｔ２までに符号化部１２によって符号化されるブロックの個数Ｎは、以下の式で求められる。
Ｎ＝（ｔ４−Ｔｅ）／（Ｔｒ＋Ｔａ）  ・・・（３）
前記（３）式によって求められたブロックの個数Ｎから、再符号化開始時刻ｔ２は、次式で求められる。
ｔ２＝Ｎ×Ｔｅ  ・・・（４）
制御部１４は、前記時刻ｔ２と前記時刻ｔ３を比較し（ステップＳ７）、ｔ２＞ｔ３を満足するか否かを判断する（ステップＳ７）。
【００５３】
「ｔ２≦ｔ３」であると判断した場合（図３に示す状態の場合）、符号化パラメータＱ１によって上限値に到達する予測時刻ｔ３のタイミングでメモリ１６に蓄積していると予想される符号化パラメータＱｉの符号化データの再符号化が完了するタイミングが、符号化パラメータＱｉでの符号量が再び上限値に達する予測時間ｔ４よりも後になってしまうことになる。つまり、再符号化が間に合わない可能性が高いことを意味する。従って、この場合には、現時点での符号化パラメータＱｉを候補から除外し、符号化パラメータ候補Ｑｉ＋１を符号化パラメータ候補とし（ステップＳ８）、上記ステップＳ３に戻る。
【００５４】
一方、「ｔ２＞ｔ３」を満たすと判断した場合（図５の状態の場合）、その時に設定されている符号化パラメータに従って符号化データ列３２ａを生成し続け、上限値に到達したとしても（その予測時刻はｔ３）、符号化データ列３２ｂを生成するための符号化パラメータＱｉを用いていれば、再符号化が時刻ｔ４に間に合うことを意味することになる。従って、「ｔ２＞ｔ３」であると判断した場合には、それを満たす符号化パラメータＱｉを、時刻ｔ１における符号化データ列３２ｂを生成するための符号化パラメータとして採用することを決定する（ステップＳ９）。
【００５５】
なお、上記では、候補となる符号化パラメータをＱ２から開始し、Ｑ３、Ｑ４…をして探索し、最初に条件を満足する符号化パラメータを採用するものであったが、Ｑ２、Ｑ３、Ｑ４…にそれぞれに演算し、その中で上記条件を満足し、尚且つ、Ｑｉの添え字の一番小さいものを選択するようにしても良い。いずれの場合にも、複数の候補の中から最適な１つを選択していることに変わりはないので、その思想の基であれば如何なるようにしても構わない。
【００５６】
また、上記の符号化パラメータＱｉを決定法の代わりに、次のようにしても良い。図８を例にして説明するが、図示において、ｔ０、ｔ１、ｔ４とＬｉの意味は図３と同じであるものとする。ｔ５とＬｉ’については以下の説明から明らかにする。また、符号化パラメータの更新手順も同じであるとする。
【００５７】
さて、図８において、符号化パラメータＱ０を用いることで生成された符号化データ列３２ａの符号データ量が上限値に到達した時刻ｔ１とき、符号化パラメータＱ１による符号データ列３２ｂのデータ量Ｌｉ’は判明している。
【００５８】
原点（ｔ０）と、時刻ｔ１、符号量Ｌｉ’で示される点とを結ぶ線形関数と上限値と交差する点を求めれば、符号化パラメータＱ１によって上限値に到達する時刻ｔ２を予測できる。また、候補となるＱｉの時刻ｔ１における符号データ量Ｌｉについても、先に説明したようにして求め、同様にして符号化パラメータＱｉによる上限値に到達する時刻ｔ４を求めることができる。
【００５９】
従って、時刻ｔ２で符号化パラメータＱ１による上限値到達したとき、符号化パラメータＱｉでの符号データ量は、図示の点Ｐで示される符号量Ｌｉ’’を予測演算できる。
【００６０】
従って、この符号量Ｌｉ’’を再符号化する際の時間Ｔを算出し、それにｔ２を加算した時刻がｔ５と定義できることになる。
【００６１】
すなわち、「ｔ５＜ｔ４」なる条件を満足する場合、符号化パラメータＱｉの採用を決定する。また、「ｔ５≧ｔ４」（図８の状態）である場合には、Ｑｉ＋１を次の候補にして上記の処理を行ない、ｔ５＜ｔ４なる条件を満足する符号化パラメータを見つけ出す。
【００６２】
以上であるが、本実施形態における処理動作をまとめると次の通りとなる。
【００６３】
符号化部１２には、初期段階では、符号化データ列３２ａを生成するための符号化パラメータＱ０をセットし、設定値を越えた場合の予備として用意される符号化データ列３２ｂを生成するための符号化パラメータＱ１をセットし、圧縮符号化を行わせる。この結果、符号化パラメータＱ０による圧縮符号化データ列３２ａが出力され、符号化パラメータＱ１による圧縮符号化データ列３２ｂはメモリ１６に蓄積されていく。
【００６４】
１ページの圧縮符号化を各ブロック単位に行っている最中に、符号化データ列３２ａの符号データ量が上限値に達する、もしくは上限値を越えると（時間ｔ１）、それまで出力していた符号化データ列３２ａを破棄させる。そして、メモリ１６に格納されたデータ（符号化パラメータＱ１による時刻ｔ０〜ｔ１までに生成された符号化データ列）を出力し、且つ、時刻ｔ１以降の後続して入力されるブロックに対しては符号化データ列３２ａを符号化パラメータＱ１に設定して符号化データ列３２ａとして出力する。
【００６５】
このとき、予備用としての符号化データ列３２ｂを生成するための符号化パラメータＱｉを決定する。そして、その時点で既にメモリ１６に格納されている符号化パラメータＱ１による符号化データ列を、更新後の符号化パラメータＱｉに従って再符号化部１９で再符号化させる。ここで、予備用として採用する符号化パラメータＱｉの決定法であるが、符号化パラメータＱ１によって上限値に達する予測時刻から再符号化を開始させ、それが完了する時刻が、符号化データ列３２ａを生成させるための符号化パラメータＱｉによる上限値に達する時刻よりも前になる条件となるものである。ただし、Ｑｉの「ｉ」はその条件を満たす候補の中の最小値を持つものとする。
【００６６】
以上説明したように、本実施形態によれば、再符号化を完了する時刻が、上限値に到達する時刻よりも前になるように符号化パラメータを設定するので、再符号化処理の終了まで符号化部１２による符号化処理を停止、又は、原稿画像の入力を一時停止等の処理を行わずに済み、１枚の画像データの符号量を所定値以内に抑えながら符号化する際のオーバーヘッドを削減することができる。
【００６７】
＜他の実施形態の説明＞
上記実施形態では、ＪＰＥＧ圧縮符号化を例にし、符号化パラメータが量子化ステップを意味するものとして説明したが、本発明はこれによって限定されるものではない。
【００６８】
ＤＣＴ変換したとき、図９に示すような３つのマスクパターン（３つに限らずそれ以上でも構わない）を用意し、それぞれのマスクパターンＱ０乃至Ｑ２と定義する。マスクパターンＱ０は、ＤＣＴ変換した際のデータを全て採用することを示し、マスクパターンＱ１は、高周波領域の破線部分のＤＣＴ係数を０にマスクすることを示し、マスクパターンＱ２はマスクパターンＱ１よりも広い範囲を０でマスクすることを示している。
【００６９】
かかるマスクパターンの場合、例えばＤＣＴ変換して得られたデータをジグザグスキャンして符号を生成する際には、少なくともマスクパターンＱ０よりＱ１、Ｑ１よりＱ２の方が圧縮率が高くなる。
【００７０】
先に説明した実施形態では、量子化ステップを変更することで圧縮率を変化させたが、このようにマスクパターンを採用しても同様の効果が得られる。従って、実施形態で説明したように、符号化パラメータは量子化ステップに限定されるものではないことが理解できよう。
【００７１】
また、ウェーブレット変換を採用している通称ＪＰＥＧ２０００に適用しても構わない。ＪＰＥＧ２０００では、ウェーブレット変換の周波数変換処理して得られたデータを量子化し、エントロピー符号化を施すが、量子化して得られた各係数値のビット単位のプレーン毎に符号化することを行う提案も既に幾つかなされており、これに適用させても良いからである。より具体的に説明するため、図１０を用いて説明する。
【００７２】
図１０は、量子化した後の係数値のブロックを示している。図示では説明を単純化するため、４×４としているが勿論、これより大きくても構わないし、一般に、このサイズよりも大きなものとなる。座標（ｉ，ｊ）として表現したとき、図示は、（１，１）の係数値が「＋１３」、（４，１）が「−６」、（１、４）が「＋３」という値を持ち、それ以外は「０」となっている例を示している。この中で値が最も大きいものが「＋１３」であり、バイナリー（２進）で表記すると「１１０１」となる。つまり、図示の場合、全ての係数が４ビットで表現できるので、ビット３のプレーン、ビット２のプレーン、ビット１のプレーン、ビット０のプレーンの４つのプレーンがあれば十分に表現でき、ビットプレーン毎に符号化を行う。
【００７３】
一方、データの重要度から見た場合、高位のビットほど重要であるから、結局のところ、ビット３のプレーンがそのブロックの画質に支配的となる。換言すれば、下位に位置するビットプレーンほど支配的ではないことになる。そこで、符号化パラメータＱ０では全てのビットプレーンを利用し、符号化パラメータＱ１では最下位のビット０のプレーンを不採用、符号化パラメータＱ２では最下位から２つのプレーンを不採用というように、しても同様の効果が得られる。
【００７４】
以上、本発明にかかる実施形態を説明したが、本発明は、複写機だけに適用できるものではなく、例えばデジタルカメラにおける画像圧縮技術等の他の画像圧縮技術に適用できるのは当業者であれば容易に推察されよう。
【００７５】
また、本発明にかかる主要部分は、ハードウェアのみならずソフトウェアにも適用できるのは明らかである。すなわち、図１に示したような各処理部又は幾つかの処理部に相当する機能をコンピュータプログラムによっても実現できる。
【００７６】
また、通常、コンピュータプログラムは、ＣＤＲＯＭ等の可搬性のコンピュータ可読記憶媒体をコンピュータにセットし、システムにコピーもしくはインストールすることで実行可能となるわけであるから、本発明はかかるコンピュータ可読記憶媒体をもその範疇とするのは明らかである。
【００７７】
従って、本発明にかかる実施態様を列挙するのでれば、次の通りである。
【００７８】
［実施態様１］  画像データを圧縮符号化する画像符号化方法であって、
符号化データ量を決定する第１の符号化パラメータと、該第１の符号化パラメータによる符号化データ量よりも少ない符号化データ量となる第２の符号化パラメータを設定可能で、前記第１の符号化パラメータによる符号化データを主符号化データとして生成し、前記第２の符号化パラメータによる符号化データを予備符号化データとして生成し出力する符号化工程と、
前記第２の符号化パラメータにより生成された予備符号化データを所定の記憶手段に蓄積する蓄積工程と、
設定された符号化パラメータに従い、前記記憶手段に記憶された符号化データを再符号化する再符号化工程と、
前記主符号化データの符号量が、所定の上限データ量に達したか否かを判定する判定工程と、
該判定工程によって前記主符号化データの符号量が、前記上限データ量に達したと判定した場合、前記記憶手段に記憶された予備符号化データを前記上限データ量に達したと判定される以前の主符号化データとして出力すると共に、前記第１の符号化パラメータを前記第２の符号化パラメータで更新し、
前記符号化工程に設定された第２の符号化パラメータを新たな符号化パラメータで更新すると共に、前記再符号化工程に前記新たなパラメータを設定して再符号化を行わせるパラメータ更新工程とを備え、
前記パラメータ更新工程は、今回更新された第１の符号化パラメータによる符号化データが前記上限データ量に到達するまでの予測時間と、次回に第１の符号化パラメータとして設定される候補群それぞれによる前記上限データ量に到達する予測時間と、夫々の候補群における前記再符号化手段による再符号化に要する予測時間を演算する演算工程と、
該演算工程の演算結果に基づき、前記候補群の中の１つを前記第２の符号化パラメータと選択する選択工程を含む
ことを特徴とする画像符号化方法。
【００７９】
［実施態様２］  前記演算工程は、
更新後の第１の符号化パラメータによる主符号化データ量が前記上限データ量に再び到達する時間を予測演算する第１の演算工程と、
候補となる符号化パラメータでの前記上限データ量に到達する時間を予測演算する第２の演算工程と、
前記第１の演算工程で演算して得られたタイミングで、前記候補となる符号化パラメータを前記再符号化工程に設定して再符号化させた際に要する予測時間を演算する第３の演算工程と、
前記第１乃至第３の演算工程の演算結果に基づいて、前記候補となる符号化パラメータが許容できるか否かを判定し、許容範囲内にあると判定した場合には、当該候補となる符号化パラメータを前記第２の符号化パラメータとして決定し、許容外であると判定した場合には、他の候補の符号化パラメータについて前記第２、第３の演算工程を繰り返すことで許容範囲にある候補符号化パラメータを探索する符号化パラメータ探索工程とを備える
ことを特徴とする実施態様１に記載の画像符号化方法。
【００８０】
［実施態様３］  前記符号化パラメータは、量子化ステップであることを特徴とする実施態様１又は２に記載の画像符号化方法。
【００８１】
［実施態様４］  画像データを圧縮符号化する画像符号化装置であって、
符号化データ量を決定する第１の符号化パラメータと、該第１の符号化パラメータによる符号化データ量よりも少ない符号化データ量となる第２の符号化パラメータを設定可能で、前記第１の符号化パラメータによる符号化データを主符号化データとして生成し、前記第２の符号化パラメータによる符号化データを予備符号化データとして生成し出力する符号化手段と、
前記第２の符号化パラメータにより生成された予備符号化データを記憶する記憶手段と、
設定された符号化パラメータに従い、前記記憶手段に記憶された符号化データを再符号化する再符号化手段と、
前記主符号化データの符号量が、所定の上限データ量に達したか否かを判定する判定手段と、
該判定手段によって前記主符号化データの符号量が、前記上限データ量に達したと判定した場合、前記記憶手段に記憶された予備符号化データを前記上限データ量に達したと判定される以前の主符号化データとして出力すると共に、前記第１の符号化パラメータを前記第２の符号化パラメータで更新し、
前記符号化手段に設定された第２の符号化パラメータを新たなパラメータで更新すると共に、前記再符号化手段に前記新たなパラメータを設定して再符号化を行わせるパラメータ更新手段とを備え、
前記パラメータ更新手段は、今回更新された第１の符号化パラメータによる符号化データが前記上限データ量に到達するまでの予測時間と、次回に第１の符号化パラメータとして設定される候補群それぞれによる前記上限データ量に到達する予測時間と、夫々の候補群における前記再符号化手段による再符号化に要する予測時間を演算する演算手段と、
該演算手段の演算結果に基づき、前記候補群の中の１つを前記第２の符号化パラメータと選択する選択手段を含むことを特徴とする画像符号化装置。
【００８２】
［実施態様５］  コンピュータが読み込み実行することで、画像データを圧縮符号化する画像符号化装置として機能するコンピュータプログラムであって、
符号化データ量を決定する第１の符号化パラメータと、該第１の符号化パラメータによる符号化データ量よりも少ない符号化データ量となる第２の符号化パラメータを設定可能で、前記第１の符号化パラメータによる符号化データを主符号化データとして生成し、前記第２の符号化パラメータによる符号化データを予備符号化データとして生成し出力する符号化手段と、
前記第２の符号化パラメータにより生成された予備符号化データを記憶する記憶手段と、
設定された符号化パラメータに従い、前記記憶手段に記憶された符号化データを再符号化する再符号化手段と、
前記主符号化データの符号量が、所定の上限データ量に達したか否かを判定する判定手段と、
該判定手段によって前記主符号化データの符号量が、前記上限データ量に達したと判定した場合、前記記憶手段に記憶された予備符号化データを前記上限データ量に達したと判定される以前の主符号化データとして出力すると共に、前記第１の符号化パラメータを前記第２の符号化パラメータで更新し、
前記符号化手段に設定された第２の符号化パラメータを新たなパラメータで更新すると共に、前記再符号化手段に前記新たなパラメータを設定して再符号化を行わせるパラメータ更新手段とを備え、
前記パラメータ更新手段は、今回更新された第１の符号化パラメータによる符号化データが前記上限データ量に到達するまでの予測時間と、次回に第１の符号化パラメータとして設定される候補群それぞれによる前記上限データ量に到達する予測時間と、夫々の候補群における前記再符号化手段による再符号化に要する予測時間を演算する演算手段と、
該演算手段の演算結果に基づき、前記候補群の中の１つを前記第２の符号化パラメータと選択する選択手段を備え、
前記各手段として機能することを特徴とするコンピュータプログラム。
【００８３】
［実施態様６］  実施態様５に記載のコンピュータプログラムを格納することを特徴とするコンピュータ可読記憶媒体。
【００８４】
なお、上記実施態様４乃至６それぞれに対し、実施態様２、３が特徴づけられることは明らかである。
【００８５】
【発明の効果】
以上説明したように本発明によれば、画像データの入力を行ないながら、オーバヘッドを抑制し、且つ、所定の上限データ量に収まるように圧縮符号化を行うことが可能になる。
【図面の簡単な説明】
【図１】実施形態における画像符号化装置のブロック構成図である。
【図２】実施形態における符号化パラメータの決定処理手順を示すフローチャートである。
【図３】実施形態における圧縮符号化データ量の推移において問題とされる現象を示す図である。
【図４】実施形態における図３と関連して、画像データの入力シーケンスを示す図である。
【図５】実施形態における改善された圧縮符号化データ量の推移を示す図である。
【図６】実施形態における背景技術を説明するための装置ブロック図である。
【図７】図６の構成における圧縮符号化データ量の推移を示す図である。
【図８】実施形態における符号化パラメータの他の決定法を説明するための圧縮符号化データ量推移図である。
【図９】符号化パラメータをマスク領域に対応させた例を示す図である。
【図１０】符号化パラメータをビットプレーンに対応させた例を示す図である。
【図１】
2004247942.tif 000003
【図２】
2004247942.tif 000004
【図３】
2004247942.tif 000005
【図４】
2004247942.tif 000006
【図５】
2004247942.tif 000007
【図６】
2004247942.tif 000008
【図７】
2004247942.tif 000009
【図８】
2004247942.tif 000010
【図９】
2004247942.tif 000011
【図１０】
2004247942.tif 000012