画像符号化装置及びその制御方法
【課題】 ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することが可能になる。
【解決手段】 属性判定部は、入力した着目ブロックを解析することで、当該着目ブロックを非可逆符号化、可逆符号化のいずれで符号化すべきかを判定する。着目ブロックが可逆符号化すべきとして判定された場合、可逆符号化部は基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを生成する。そして、生成された符号化データ量が予め設定された目標符号量を超えるか否かが判定され、超えると判定した場合には着目ブロックを非可逆符号化すべきブロックとして変更する。また、超えないと判定された場合には、可逆符号化部は、残りの階層の符号化データを可逆符号化部により生成させる。また、属性判定部で非可逆符号化すべきと判定されたブロック、或いは、可逆から非可逆へ変更されたブロックについては、非可逆符号化部で非可逆符号化する。
【解決手段】 属性判定部は、入力した着目ブロックを解析することで、当該着目ブロックを非可逆符号化、可逆符号化のいずれで符号化すべきかを判定する。着目ブロックが可逆符号化すべきとして判定された場合、可逆符号化部は基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを生成する。そして、生成された符号化データ量が予め設定された目標符号量を超えるか否かが判定され、超えると判定した場合には着目ブロックを非可逆符号化すべきブロックとして変更する。また、超えないと判定された場合には、可逆符号化部は、残りの階層の符号化データを可逆符号化部により生成させる。また、属性判定部で非可逆符号化すべきと判定されたブロック、或いは、可逆から非可逆へ変更されたブロックについては、非可逆符号化部で非可逆符号化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像データの符号化技術に関するものである。
【背景技術】
【０００２】
離れた場所からプリンタに対してプリントを指示するプリント形態があり、それをリモートプリントと言う。リモートプリントにおいて、ＰＤＬのレンダリングは、インターネット上のサーバー上で行われることがある。この場合、ネットワークを介して、プリントジョブを伝送するため、レンダリングした画像（文書画像）に対しては、レート制御機能を持つ画像圧縮が必要となる。レート制御機能とは、画像圧縮されたデータ（画像符号化データ）を、復号することなく符号量を変更できる機能である。この機能により、画像符号化データを伝送するネットワークの帯域幅に応じたデータ量の変更が容易となる。
【０００３】
また、文書画像においては、文字，線画等の領域、写真の領域が混在する場合も少なくない。この点に着目した高効率な圧縮方式として、領域毎に適した符号化方法を用いる適応符号化方式がある。その例として、特許文献１がある。
【０００４】
特許文献１においては、画像をブロックに分割して、写真領域のブロックには、高周波成分のデータを大きく削減して高圧縮性を狙える、周波数変換をベースとした符号化を用いる。一方、文字，線画等のブロックには、領域の低エントロピー性を利用して、高効率な符号化性能を実現可能な予測符号化を用いる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−６７１１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
適応符号化による高画質／高圧縮の利点を活かし、かつ、用途に応じて符号量の調整が可能なレート制御機能の実現が求められている。レート制御機能を持つ適応符号化には、ＪＰＥＧ２０００のような、レート制御機能を有する周波数変換ベースの符号化方式が望ましい。一方、予測符号化は多値データを「多値」として処理を行うため、レート制御機能を持たず、利用しずらい。
【０００７】
かかる点を踏まえると、適応符号化のレート制御のためには次のような処理が考えられる。先ず、文字・線画等の領域のブロックに対して予測符号化を実施する。その後、該当領域の符号量を算出する。その上で、画像全体の目標符号量から、文字・線画等の領域の符号量を減算して、写真領域の目標符号量を得る。次いで、写真領域のブロックに対し周波数変換ベースの符号化方式を実施する。そして、写真領域に対して目標符号量となるようにレート制御を行い、画像全体に求められる目標符号量を達成する処理となる。
【０００８】
ただし、この処理においては、文字・線画等の領域の符号量が多くなる場合、写真領域に対して、十分に符号量を割り当てられないことがある。極端な場合には、文字，線画等の領域のみで、画像全体の目標符号量を超過してしまうことも発生し得る。
【０００９】
この問題に対しては、上記方法で写真領域の目標符号量を得た後に、当該目標符号量は不十分であると判断した際、文字，線画等の領域の一部もしくは全部のブロックを周波数ベースの符号化方式で圧縮し直すことである。そして、その上で、周波数ベースの符号化方式で圧縮した領域に対してレート制御を行うことである。たしかに、この場合、画像全体の目標符号量に符号化することができるが、この方法では、文字，線画等の領域に対する予測符号化が終了した後にも、該当領域のビットマップを保持しなければならない。つまり、メモリ使用量の増加を伴う。もしくは、ビットマップを保持しないのであれば、予測符号化の復号を行ってビットマップを生成した上で、圧縮をし直す必要があり、処理時間の増大につながる。
【００１０】
本発明は上記点に鑑みなされたものであり、ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することを可能ならしめる技術を提供しようとするものである。
【課題を解決するための手段】
【００１１】
この課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像を符号化して符号化データを生成し、目標とするビットレートに従い、生成された符号化データ中の一部を削除し出力するレート制御手段を有する画像符号化装置であって、
複数画素で構成されるブロックを非可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ１段階の階層データ構造を持つ符号化データを生成する第１の符号化手段と、
前記ブロックを予測演算を用いて可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ２（Ｎ１＞Ｎ２）段階の階層データ構造を持つ符号化データを生成する第２の符号化手段と、
符号化対象画像から前記ブロックを単位に入力する入力手段と、
入力した着目ブロックを解析することで、当該着目ブロックを前記第１の符号化手段、前記第２の符号化手段のいずれで符号化すべきかを判定する判定手段と、
該判定手段により、前記着目ブロックを前記第２の符号化手段で符号化すべきとして判定された場合、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを前記第２の符号化手段により生成させ、生成された符号量が予め設定された目標符号量を超えるか否かを判定し、超えると判定した場合には前記着目ブロックを前記第１の符号化手段で符号化すべきブロックとして変更し、超えないと判定された場合には、残りの階層の符号化データを前記第２の符号化手段により生成させる第１の制御手段と、
前記判定手段、或いは、前記第１の制御手段によって前記第１の符号化手段で符号化すべきと判定されたブロックに対して前記第１の符号化手段により符号化させ、符号化データを生成させる第２の制御手段とを有する。
【発明の効果】
【００１２】
本発明によれば、ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することが可能になる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施形態における画像符号化処理の機能ブロック図。
【図２】第１の実施形態における画像符号化処理のフローチャート。
【図３】符号化情報テーブルの説明図。
【図４】レート制御部１０６のフローチャート。
【図５】符号化情報テーブルの説明図。
【図６】補間データ削除の説明図。
【図７】補間データ削除の説明図。
【図８】第２の実施形態における画像符号化処理の機能ブロック図。
【図９】ブロック符号化部８０１のブロック図。
【図１０】第１の実施形態における画像符号化処理のフローチャート。
【図１１】ブロック符号化部８０１のフローチャート。
【図１２】サブブロック符号化情報テーブルの説明図。
【図１３】レート制御部８０２のフローチャート。
【図１４】画像処理装置のブロック図。
【図１５】ステップＳ１３０１のフローチャート。
【図１６】サブブロック符号化情報テーブルの説明図。
【図１７】補間データ生成方法の説明図。
【図１８】画像符号化データの構成の説明図。
【発明を実施するための形態】
【００１４】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１５】
［第１の実施形態］
最初に、従来技術の課題に対する、本発明における解決方法の考え方について述べる。なお、以下では、文字・線画等の領域については、高周波性の維持が必要であるので、予測符号化を用いた可逆符号化を用いるものとする。そして、写真領域（階調画像）については、解像度よりも階調性が重要であるので、高圧縮性が期待できる周波数変換ベースの非可逆符号化を用いるものとする。その上で、文字・線画等の領域を符号化する手法を可逆符号化方式、写真領域を符号化する手法を非可逆符号化方式として説明する。
【００１６】
処理のおおまかな考え方としては、２つある。１つ目は、画像をブロック単位に、可逆符号化対象ブロック、非可逆符号化対象ブロックに仮判定する。そして、ブロックをラスタスキャン順に符号化処理する過程において、ブロック平均符号量を超過する可逆符号化対象ブロックに対しては、可逆符号化の符号列を出力せずに、非可逆符号化対象ブロックに切り替える。こうすることで、非可逆符号化のブロックに十分な符号量を割り当てられない問題の発生を防ぐ。
【００１７】
より詳しくは次のとおりである。まず、ラスタスキャン順に、写真領域のブロックには非可逆符号化を行い、文字・線画等の領域のブロックに対して可逆符号化を行う。その上で、文字，線画等の領域の各ブロックの可逆符号化が終了した後に、逐次注目ブロックの符号量を算出するとともに、ブロック平均符号量と比較し、非可逆符号化による圧縮のし直しの要否を判断する。もし、注目ブロックの符号量の方が大きければ、可逆符号化の符号列を出力せず、ラスターイメージを用いて非可逆符号化で圧縮し直す。一方で、注目ブロックの符号量の方がブロック平均符号量以下であれば、そのまま符号列を出力するものとする。例えば、ラスタスキャン順で見て連続するブロックの一部について、図６（ａ）のように符号量が分布する場合を考える。同図で、ブロック番号１，２，５〜１０，１６のブロックは、ブロック平均符号量を超えている。このため、各ブロックの可逆符号化が終了した後、逐次、非可逆符号化で圧縮し直す。また、番号３のブロックについては、そのまま出力する。一方で、写真領域については、非可逆符号化を実施する。そして、すべてのブロックの符号化が終了した後で、可逆符号化のブロックの符号量の総和を算出し、画像全体の目標符号量から減じる。そこで得られた符号量を、非可逆符号化の目標符号量として、レート制御を行う。
【００１８】
この方法については、使用メモリ量や処理時間の増大を回避しつつ、非可逆符号化のための符号量を確保できるが、必要以上に文字，線画等の領域を非可逆符号化で圧縮してしまうことがある。つまり、可逆符号化のブロック全体から見て、ブロック平均符号量を超過する可逆符号化のブロックが少ない場合、画像全体で見れば、非可逆符号化のための符号量を十分に確保できる。それにもかかわらず、前述方式では非可逆符号化による圧縮のし直しを行ってしまう。
【００１９】
本発明における２つ目の考え方は、これに対する対応策である。具体的には、可逆符号化の符号列に階層性を持たせることで解決する。ここで考える階層は、符号化対象領域における最低限の画質を保証するために必要な階層（基本階層）と、基本階層と併せて復号することでより高画質な画質を生成できる階層（付加的階層）に分類されるものである。そして、可逆符号化の符号列は、基本階層と付加的階層の構造を持つことになる。このような階層性を持たせることで、符号列生成後に付加的階層を削除して、可逆符号化の符号量を減らすことができる。したがって、付加的階層の削除により、符号量をブロック平均符号量以下にできるブロックについては、圧縮のし直しをせず、可逆符号化の符号列にしておく。その上で、符号化終了後に、非可逆符号化のための符号量が少ないと判断すれば付加的階層を削除して符号量を確保し、そうでなければ、削除を行わず可逆符号列をそのまま出力することが可能となる。結果として、文字，線画等の領域に対して、必要以上に非可逆符号化で圧縮してしまう問題を避けることができる。具体的な処理概要を、図６（ｂ）を用いて説明する。同図において、各可逆符号化が適用されるブロックは、階層１と階層２から構成されるものとして、階層１は上記の「基本階層」であり、階層２は「付加的階層」である。この符号量分布において、ブロック番号８，１０，１６のブロックのみ、非可逆符号化で圧縮し直すことが必要となる。これは、削除してはならない基本階層の符号量がブロック平均符号量を超過しているためである。そして、このようなブロックが画像中に多数存在していると、非可逆符号化に十分な符号を割り当てられなくなるからである。しかし、ブロック番号１，２，５〜７，９のブロックについては、各ブロックの符号量はブロック平均符号量を超えているが、基本階層の符号量がブロック平均符号量より少ない。このため、階層２を削除することで符号量を減らして、ブロック平均符号量より少なくすることが可能ある。この点を踏まえて、非可逆符号化による圧縮のし直しを行わないで済む。一方で、写真領域については非可逆符号化で逐次符号化を行う。そして、全ブロックの符号化が終了した後に、可逆符号化のブロックの符号量の総和を算出し、画像全体の目標符号量から減じる。ここで得られた符号量を非可逆符号化の目標符号量と考え、十分な符号量であれば、当該目標符号量で非可逆符号化の符号化を行う。他方で、十分な符号量でないとした場合、可逆符号化のブロックの一部、もしくは全部の階層２のデータを削除して、非可逆符号化のための符号量を確保する。その上で、非可逆符号化を実施する。本実施の形態においては、かかる２つ目の考え方に基づいた方法を採用するものであり、以下にその詳細について説明する。
【００２０】
図１４は本実施形態に係る画像処理装置として機能する情報処理装置の基本構成を示す図である。本装置は、外部から符号化対象となる画像、並びに目標ビットレートＴＲの入力を受け付け、目標ビットレートの画像符号化データを生成するものである。ここで言う目標ビットレートＴＲとは、画像の圧縮率を示す指標であり、圧縮処理により生成されたデータの１画素当たりの符号量（ビット数）である。単位はbpp(bit per pixel)となる。
【００２１】
１４０１は装置全体の制御を司るＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理を実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。さらに、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７は外部記憶装置で、ハードディスクドライブ装置等の大容量情報記憶装置である。ここにＯＳ（オペレーティングシステム）や後述する画像符号化処理の為のプログラムや画像等のデータなどが保存されている。そして、ＣＰＵ１４０１による制御によって、これらのプログラムやデータはＲＡＭ１４０２上の所定のエリアにロードされる。１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどのコンピュータ可読記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化処理の為のプログラム、符号化対象の画像を記録しておいても良くい。その場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えば画像符号化装置をＩ／Ｆ１４０９に接続し、当該画像符号化装置によって生成された画像符号化データを本装置のＲＡＭ１４０２や外部記憶装置１４０７に入力することもできる。１４１０は上述の各ユニットを繋ぐバスである。
【００２２】
なお、符号化対象の画像、並びに目標ビットレートＴＲについては、本装置のユーザーが、キーボード１４０４、マウス１４０５により指定する。そして、ＣＰＵ１４０１は、外部記憶装置１４０７に格納されている、本発明の画像符号化処理プログラムをＲＡＭ１４０２にロードするとともに、符号化対象の画像，ＴＲをＲＡＭ１４０２へ展開する。その後、ＣＰＵ１４０１は、画像符号化処理を行い、生成した画像符号化データを、Ｉ／Ｆ１４０９を通して、外部装置に出力するものである。
【００２３】
本実施形態における符号化対象の画像データは、外部記憶装置１４０７に格納されており、符号化後のデータも外部記憶装置１４０７に格納するものとする。ただし、これは便宜的なものであり、符号化対象の画像データをネットワークを介して受信しても良いし、符号化後のデータをネットワークを介して送信しても良い。勿論、符号化対象の画像をイメージスキャナより読込むものとしても構わないので、符号化対象の画像データの発生源、符号化済みの出力対象で本願発明が限定されるものではない。また、実施形態における符号化対象の画像データは、ＲＧＢカラー多値画像データとし、各コンポーネント（色）は８ビット（０乃至２５５の２５６階調）として説明する。但し、ＲＧＢ以外のコンポーネントの構成（例えば、グレーやＣＭＹＫ）でも構わず、色空間の種類，コンポーネントの個数は問わない。また、１成分のビット数も８ビットに限らず、８ビットを超えるビット数、もしくは８ビット未満のビット数でも構わない。更に、符号化対象の画像は水平方向W画素、垂直方向H画素により構成されるものとする。
【００２４】
図１は本実施形態に係る画像処理装置における、画像符号化アプリケーションをＣＰＵ１４０１が実行した場合の機能構成を示すブロック図である。同図のように、ブロック分割部１０２、ブロックバッファ１０３、属性判定部１０４、非可逆符号化部１０５（第１の符号化部）、レート制御部１０６、可逆符号化部１０７（第２の符号化部）、可逆符号化可否判定部１０８、画像符号化データ形成部１０９を備える。なお、図１ではコンピュータプログラム（ソフトウェア）の例をしめすものとしているが、全処理部もしくはその一部をハードウェアにより実現しても良いのは勿論である。また、
図２は、本実施形態に係る画像処理装置の符号化処理（ＣＰＵ１４０１の処理）を示すフローチャートである。以下、図１，図２を参照して、本実施形態に係る画像処理装置が行う画像符号化処理について説明する。
【００２５】
ＣＰＵ１４０１は、画像の符号化処理を開始すると、初期化処理を行う（ステップＳ２０１）。この初期化処理として、ブロックカウンタに対する０の設定，外部から指定された目標ビットレートＴＲ(bpp)の設定、符号化対象の画像の先頭ポインタの取得、等である。初期化処理の後、ブロック分割部１０２は、ブロックバッファ１０３へブロックデータの格納する（ステップＳ２０２）。
【００２６】
ブロックバッファ１０３は１ブロック分の画素データを格納する領域を持ち、ブロック分割部１０２から出力されるブロックデータを順次格納していく。ブロックのサイズは、水平方向Ｂw画素、垂直方向Ｂh画素である。説明の便宜上、符号化対象のオリジナル画像の水平方向画素数ＷはＢwの整数倍、垂直方向画素数ＨはＢhの整数倍であり、矩形ブロックに分割した場合に正規のサイズではないブロックが発生しないものとする。
【００２７】
また、ブロックバッファ１０３に必要とされる容量はＢｗ×Ｂｈ×３（RGB分）バイトである。ここで、ブロックのサイズの設定について簡単に述べる。後述するが、ブロックを単位として、領域の属性（文字，線画等、写真の２種類）を判断し、可逆符号化方式と非可逆方式のいずれを用いるか選択する。このため、ブロックのサイズが大きいと、写真領域と文字，線画等の領域の境目等において、可逆符号化のブロックと非可逆符号化のブロックが混在する場合に、歪みと見えてしまう。一方、あまり小さくすると、符号化において参照できる範囲が限定されてしまい、符号化の性能低下を招く。これらのことを勘案し、本実施の形態においては、Ｂｗ＝３２、Ｂｈ＝３２とする。なお、本実施の形態における以下の説明では、画像全体にわたるブロックの個数（（Ｗ／Ｂｗ）ｘ（Ｈ／Ｂｈ））をＮと定義する。また、ブロックバッファ１０３へのブロックデータの取得順は、このブロックを単位とするラスタースキャン順とする。
【００２８】
ブロックバッファ１０３へのブロックデータの格納が終わると、属性判定部１０４はブロックデータを解析し、その属性判定処理を行う（ステップＳ２０３）。具体的な判定処理は次に述べるとおりである。
【００２９】
属性の判定は、Ｂｗ×Ｂｈ画素のブロックデータを入力し、ブロック内をＫ画素単位（本実施形態ではＫ＝２×２画素）にラスタースキャン順で処理する。以降、この２×２画素をピース（Ｐｉｅｃｅ）と呼ぶ。実施形態の場合、１ブロックのサイズは３２×３２画素であるので、この中には２５６（＝１６×１６）個のピースが存在することとなる。図１７の右側に示す図は、１つのピースに含まれる４つの画素を示している。
【００３０】
判定手順は、まず、１つのピースの中で、色数が何色であるかの判別を行う。注目しているピース内の４個の画素を図１７の右側に示すａ、ｂ、ｃ、Ｘで表現し、画素ａ，ｂ，ｃ，Ｘそれぞれの画素値（色）が一致するかどうかの判定によって、ピースの色数を判定できる。ａ，ｂ，ｃ，Ｘそれぞれの差分値Ｄａｂ，Ｄａｃ，Ｄａｄ，Ｄｂｃ，Ｄｂｄ，Ｄｃｄを次式（１）により求める。
Ｄａｂ＝ａ−ｂ
Ｄａｃ＝ａ−ｃ
Ｄａｄ＝ａ−Ｘ
Ｄｂｃ＝ｂ−ｃ
Ｄｂｄ＝ｂ−Ｘ
Ｄｃｄ＝ｃ−Ｘ …（１）
【００３１】
そして、差分値Ｄａｂ，Ｄａｃ，Ｄａｄ，Ｄｂｃ，Ｄｂｄ，Ｄｃｄのうち、０となる数Ｆをカウントする。従って、差分値は６つあるので、値Ｆは０乃至６の値を取り得る。ここで、Ｆ＝０の場合、ピース内の４画素ａ，ｂ，ｃ，Ｘは全て違う色であることを意味するのは明らかで、色数が４であることを示す。また、Ｆ＝１の場合、４画素中２画素が同じ色となるので、ａ，ｂ，ｃ，Ｘの色数は３となる。同様に、Ｆ＝２の場合には、色数が２であることを示し、Ｆ＝３以上の場合にはａ，ｂ，ｃ，Ｘが全て同じ色であることになる。以上の方法により、着目ピースの色数の判別が可能となる。そして、ブロック内の全ピースの色数を判定する。ブロックの終端に位置するピースの色数判定が終了したら、符号化方式の判定を行う。本実施形態では、ブロック内のピースの色数が１色の場合の数、２色の場合の数、３色の場合の数、４色の場合の数をカウントしておく。ブロック内のピース数と、１色ピース及び２色ピースのカウント数ＣＰ１を比較して、ＣＰ１が総ピース数の５０％以上であれば（過半数を占めれば）、注目ブロックは文字，線画等の領域であると判定する。一方、ＣＰ１が総ピース数の５０％未満である場合には、注目ブロックは非文字線画領域、換言すれば写真領域（階調領域）であると判定する。なお、上記の代わりに、３色ピース及び４色ピースの合計カウント数と総ピース数との比で判定しても良いのは勿論である。
【００３２】
属性判定（ステップＳ２０３）を行った結果を受け、着目ブロックが文字、線画領域にあるか、写真領域であるかの判定を行う。そして、文字、線画領域にあると判定された場合には後述する第１の制御処理を行う。また、写真領域である場合には以下に説明する２の制御処理を行う。
【００３３】
以下は、ステップＳ２０４でＹｅｓ、すなわち、着目ブロックが写真領域である場合の第２の制御処理である。非可逆符号化部１０５は、着目ブロックのビットマップイメージを非可逆符号化する（ステップＳ２０５）。ここで非可逆符号化とは、符号化終了後に符号列の一部を切り捨てることが可能な階層性を持つ非可逆符号化である。例えば、ビットプレーンを単位として符号化を行うビットプレーン符号化、画像中の周波数係数を低い成分からグループ化させて、グループを単位として順に符号化を行う周波数ベースの階層的符号化がある。本実施の形態においては、ビットプレーン符号化，周波数ベースの階層的符号化を併せ持つ、国際標準方式のＪＰＥＧ２０００(ITU-T T.800 | ISO/IEC 15444-1)により符号化を行う。ＪＰＥＧ２０００の詳細については、勧告書等に記載されているので、ここでは説明を省略する。なお、後述するが、本実施の形態における非可逆符号化方式における階層数は２であるが、ＪＰＥＧ２０００は目標符号量の符号列を生成できるレート制御機能を持っているため、階層数は無数にあると言える。
【００３４】
非可逆符号化で生成された符号列については、レート制御部１０６に出力する。その上で、図３のとおり、ＲＡＭ１４０２に予め確保しておいた、ブロックの符号化情報をまとめたテーブル（符号化情報テーブル）に、非可逆符号化を行ったことを示す圧縮フラグ“０”を記録する（ステップＳ２０６）。さらに、非可逆符号化データサイズとデータの先頭ポインタを記す。なお、非可逆符号化部１０５では、符号列における所定のデータを単位として、符号量と、データを復号しないことにより復号画像上に発生する歪みの比率（Ｒ−Ｄ比）を求める。そして、レート制御部１０６では、Ｒ−Ｄ比の情報を基に、歪みの発生を抑えつつ、生成された符号化データ中の符号を選択的に削除してレート制御を行う。このＲ−Ｄ比を求める処理は負荷が大きいため、非可逆符号化の符号列に求められる目標符号量から見て、必要以上の符号列を生成することは望ましくない。つまり、後述するレート制御部１０６において、レート制御を行える程度に符号を生成すればよい。
【００３５】
次に、着目ブロックが文字，線画領域にあると判定された場合の第１の制御処理について説明する（ステップＳ２０４でＮｏ）。この場合、可逆符号化部１０７は、着目ブロックに対し、階層性を持たせることが可能な予測演算を主体とする可逆符号化を行う。具体的には、着目ブロックから補間データと縮小画像ブロックを生成する。その上で、先ず、縮小画像ブロックに対して可逆符号化を行う（ステップＳ２０７）。ここで、補間データと縮小画像ブロックについて簡単に説明する。縮小画像ブロックは、図１７における各ピースの右下の画素Pn(1,1)を集めて得られるデータであり、結局のところ、オリジナルのブロックに対して水平、垂直とも１／２のサイズである。一方、補間データは各ピースの残りの画素Pn(0,0),Pn(1,0),Pn(0,1)を集めたデータである。縮小画像ブロックについては、注目ブロックの最低限の画質の画像を表示する上で必要となるデータであり、図６（ｂ）の階層１に相当する。つまり、この階層１の１画素から同じ値の画素を２×２個生成すれば、少なくともオリジナルのブロックと同じサイズの画像を構成できる。また、補間データについては、非可逆符号化のための符号量確保のために削除され得るデータであり、図６（ｂ）の階層２に相当する。なお、可逆符号化で用いる符号化方式としては、国際標準方式のＪＰＥＧ−ＬＳ（ITU-T T.87 | ISO/IEC 14495-1）を用いるものとする。ＪＰＥＧ−ＬＳの詳細については、勧告書等に記載されているので、ここでは説明を省略する。縮小画像ブロックの符号化が終了した後、可逆符号化可否判定部１０８は、縮小画像ブロックの符号列に関するビットレート（r_i_block）を算出し、目標ビットレートＴＲとの比較を行う（ステップＳ２０８）。なお、縮小画像ブロックの符号量をM_i_block（バイト）としたとき、縮小画像ブロックの符号列に関するビットレートr_i_blockは、次式に従って算出できる。
r_i_block＝8 * M_i_block / (Bw/2 * Bh/2)＝32 * M_i_block/(Bw * Bh)
【００３６】
もし、算出したビットレートr_i_blockが目標ビットレートＴＲより大きい場合（ステップＳ２０８でＮｏ）、着目ブロックは図６（ｂ）のブロック番号８、１０や１６と同じ状況であるとことになる。従って、レート制御を保証するために、着目ブロックについての可逆符号化での符号化をあきらめ、非可逆符号化する（ステップＳ２０５）。なお、繰り返すが、非可逆符号化により圧縮し直す理由は、縮小画像の符号列については、当該ブロックの画像を表示でする必須のものであり、削除することはできないためである。そして、このようなブロックが画像中に多く存在すると、非可逆符号化に割り当て可能な符号量が極端に少なくなる可能性があるからである。また場合によっては、可逆符号化の符号量だけで目標符号量を超えてしまう可能性があるからである。他方、ビットレートr_i_blockが目標ビットレートＴＲ以下である場合（ステップＳ２０８でＹｅｓ）、非可逆符号化による圧縮のし直しを行わず、残りの補間データの符号化を行う（ステップＳ２０９）。これは、このようなブロックが多く存在しても、非可逆符号化への符号量割り当てに関する問題は発生しないからである。なお、補間データの符号化は、可逆符号化方式，非可逆符号化方式のいずれでもよい。ただし、本実施の形態においては、文字，線画等の領域を可逆符号化するものとしているので、補間データについても可逆符号化を行うものとする。具体的な方法としては、次に述べる方式を用いる。
【００３７】
補間データの符号化はピース単位で行うものであり、属性判定部１０４において導出した色数に応じて符号を割り当てる。もし、注目ピース内の色数が１色の場合、“１”（１ビット）を出力する。復号装置では、縮小画像を復号した後、もし補間データの符号語が“１”であった場合、縮小画像中の該当する１つの画素をＰn(1,1)と見なす。そして、それと同じ色の画素Ｐn(0,0),Ｐn(1,0),Ｐn(0,1)を生成すれば良いことになる。
【００３８】
また、注目ピース内の色数が１色ではなく、以下の次式（２）が成り立つ場合、“０１”（２ビット）を出力する。
Pn(0, 1) = Pn-1(1, 1)
かつ
Pn(1, 0) = Pn-b(1, 1)
かつ
Pn(0, 0) = Pn-b-1(1, 1) …（２）
ここで、Ｐnが着目ピースを示し、Ｐn-1,Ｐn-b,Ｐn-b-1の関係は図１７に示すように、隣接する３つのピース内の各右下画素である。復号装置では、縮小画像を復号した後、もし補間データの符号語が“０１”であった場合、縮小画像中の該当する１つの画素をＰn(1,1)と見なし、その画素の左上隣画素Ｐn-b-1(1,1)と同じ色を持つ画素Ｐn(0,0)を生成し、上隣の画素Ｐm-b（1,1）と同じ色を持つ画素Ｐn(1,0)を生成し、そして、左隣の画素Ｐn-1(1,1)と同じ色を持つ画素Ｐn(0,1)を生成すれば良い。
【００３９】
そして、注目ピース内の色数が１色ではなく、上式（２）も成り立たない場合、“００”（２ビット）を出力し、続けて３つの画素Ｐn(0,0),Ｐn(1,0),Ｐn(0,1)の値をそのまま出力する。実施形態の場合、１画素の色成分の数は３つであり、各々が８ビットであるので、“００”に後続して、７２ビット（＝３×８×３）が出力されることになる。なお、この方式は、あくまで本実施の形態において用いる処理の一例であり、その他の方式を使ってもよい。例えば、画素値をそのまま出力する方法や、特開２０１０−１５４４８６に開示された方法でも構わない。
【００４０】
補間データの符号化が終了した後、図３に示したように、符号化情報テーブルに圧縮フラグとして“１”を記す（ステップＳ２１０）。さらに、補間データの符号量と、補間データの符号量と縮小画像の符号量の和とを符号化情報テーブルに記録する（ステップＳ２１０）。その上で、補間データと縮小画像の符号列をレート制御部１０６へ出力する。この出力においては、まず、補間データの符号列をレート制御部１０６内部のメモリへ書き込み、それに後続するように縮小画像の符号列を書き出す。さらに、符号化情報テーブルに、補間データの符号列の先頭アドレスを記録する。補間データの符号量を記録する理由は、格納した先頭アドレスにその符号量を加算するだけで、補間データを読み飛ばし、縮小画像データの符号列の読み出しアドレスが算出できるためである。
【００４１】
ステップＳ２０６もしくはステップＳ２１０の処理が終了した後、ブロックカウンタi_blockをインクリメントし（ステップＳ２１１）、ブロックカウンタの値i_blockとブロック総数Ｎの比較を行う（ステップＳ２１２）。もしi_blockの方が、符号化対象画像内の総ブロック数Ｎより小さければ（ステップＳ２１２でＹｅｓ）、処理をＳ２０２へ戻す。そうでなければ（ステップＳ２１２でＮｏ）、レート制御部１０６はレート制御処理を行う（ステップＳ２１３）。
【００４２】
レート制御部１０６では、先ず、可逆符号化のブロックに関するビットレート(r_lossless)を求める。そして、所定の閾値(Th_r1)との比較を行い、Th_r1よりr_losslessの方が大きい場合には、可逆符号化実施ブロックの符号量が多く、非可逆符号化に十分な符号量が割り当てられないと考えて、補間データの削除を行う。なお、補間データの削除の方法については、いくつか考えられるが、本実施の形態においては、最も簡易な方法を採る。具体的には、画像全体の可逆符号化のブロックの全ての補間データを削除する。
【００４３】
レート制御部１０６の処理フローについては、図４にまとめており、同図を用いて説明する。レート制御処理が開始すると、図３の符号化情報テーブルを基に画像全体の可逆符号化データのビットレート(r_lossless)を算出する（ステップＳ４０１）。なお、r_losslessについては、可逆符号化が実施されたブロック（可逆符号化実施ブロック）の数をnum_lossless_block、可逆符号化実施ブロックの符号量(byte)の和（総符号量）をsum_M_losslessとして、次の通り算出される。
r_lossless = 8 * sum_M_lossless/(Bw*Bh*num_lossless_block)
【００４４】
次いで、可逆符号化実施ブロックを可逆のまま出力するのか、補間データを削除して符号量を削減して出力するかの判断を行う（ステップＳ４０２）。具体的には、現在の可逆符号化データのビットレート(r_lossless)と閾値Th_r1との比較を行う。もし、r_losslessが閾値Th_r1より大きい場合（ステップＳ４０２でＹｅｓ）、可逆符号化実施ブロックに対して補間データの削除を行う（ステップＳ４０３）。その上で、今度は非可逆符号化の目標ビットレート(TR_lossy)を算出する（ステップＳ４０４）。一方で、r_losslessがTh_r1以下の場合（ステップＳ４０２でＮｏ）、非可逆符号化の目標ビットレート(TR_lossy)を算出する（ステップＳ４０４）。
【００４５】
ここで、閾値Th_r1の設定について簡単に述べる。後述するが、非可逆符号化領域の目標符号量は、画像全体の目標符号量から、可逆符号化実施ブロックの最終的な符号列の符号量を減じた値である。このため、Th_r1として大きい値を設定するほど、“可逆”の符号量を多く出力することになり、結果として、非可逆符号化の符号列に割り当て可能な符号量は少なくなる。そして、非可逆符号化が実施されるブロック（非可逆ブロック）の画質は、画像全体を非可逆符号化により目標ビットレートで圧縮した場合と比べて、低くなってしまう。一方で、Th_r1として小さい値を設定するほど、“可逆”としての出力を制限することである。このため、可逆符号化方式を導入することのメリットが失われていく。これらのことを鑑みると、Th_r1については、画像全体の目標ビットレートＴＲに近い値を設定することが望ましい。そこで、Th_r1とＴＲとの間には、相関性を持たせるものとした。すなわち、Th_r1＝α * ＴＲ（ただし、αは１以上の実数）とすることが望ましい。そこで、実施形態では、α＝１、すなわち、Th_r1＝ＴＲを設定するものとする。
【００４６】
ステップＳ４０３においては、補間データの削除を行うための、符号化情報テーブルの更新を行う。具体的には、図５に示したとおり、圧縮フラグが“１”となっている全てを“２”へ変更する。さらに、可逆符号化データサイズを、補間データサイズを減じた値とし、データ先頭ポインタの値を縮小画像列の先頭へ変更する（従前のデータ先頭ポインタを補間データのデータサイズで加算して更新する）。なお、説明のとおり、この処理ステップにおいては、実際に補間データの削除は行なわなくてよい。後述する画像符号化データ形成部１０９では、符号化情報テーブルを参照しながら、補間データを読み飛ばして符号列を生成し、最終的には補間データを削除した符号列を生成できるためである。
【００４７】
ステップＳ４０４においては、非可逆符号化の目標ビットレートTR_lossyを下記の通り行う。
・ステップＳ４０２でＹｅｓの場合：
TR_lossy ＝ 8 * (M_img - sum_M_reduced_img) / (Bw * Bh * num_lossy_block)
・ステップＳ４０２でＮｏの場合：
TR_lossy = 8 * (M_img - sum_M_lossless) / (Bw * Bh * num_lossy_block)
ここで、sum_M_reduced_imgは、各可逆符号化実施ブロックにおける縮小画像の符号列の符号量和であり、num_lossy_blockは非可逆ブロックのブロック数である。また、M_imgは、画像全体の目標符号量であり以下のとおりである。
M_img = TR * W * H / 8
【００４８】
ステップＳ４０４における非可逆符号化の目標ビットレートTR_lossyの算出が終了した後、非可逆符号化データのビットレートがTR_lossyとなるように、レート制御を行う。このレート制御については、各非可逆ブロックのＲ−Ｄ比の情報を基に、非可逆ブロック全体の中から、削除すべきデータを決定しながら行う。実施形態では、非可逆符号化としてＪＰＥＧ２０００を例にしているので、非可逆ブロックのＲ−Ｄ比の情報を基に、最下位のビットプレーンから何層までのビットプレーンまでを削除するかを決定していく。ただし、詳細については、本発明の主たる目的から外れるので、ここでは割愛する。このレート制御処理が完了した後、符号化情報テーブルを画像符号化データ形成部１０９へ出力し（ステップＳ４０６）、処理を終える。
【００４９】
ステップＳ２１３のレート制御処理が終了すると、画像符号化データ形成部１０９において画像全体の符号化データ（画像符号化データ）の形成を行う（ステップＳ２１４）。このステップでは、まず、画像符号化データの先頭に配置するヘッダの情報を生成する。ヘッダには、画像の縦横サイズ，ブロックのサイズ，各ブロックの圧縮フラグと符号長等、復号する上で必要となる情報をまとめる。次いで、ヘッダに続けて、ブロック番号順で各ブロックの符号列を並べる。その際には、符号化情報テーブルの情報を基に処理を行う。これらの処理により、画像符号化データの形成が終了すると、画像符号化処理は完了する。
【００５０】
以上説明したように本第１の実施形態では、ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することが可能になる。しかも、文字や線画が含まれる領域については、或る程度の画質が維持することも可能になる。また、特に、第１の実施形態のように、１つのブロックについて可逆符号化から非可逆符号化に切り替えるべきか否かの判断（Ｓ２０８）は、オリジナルのブロックよりも小さい縮小画像についての可逆符号化結果の符号量から判断する。従って、仮に、着目ブロックを可逆符号化から非可逆符号化に切り替えるにしても、その間のロスは縮小画像の可逆符号化に係る時間で済み、全体に与える時間を小さなものとすることができる。
【００５１】
なお、上記実施形態では、可逆符号化部１０７は、３２×３２画素のブロックから、水平、垂直とも１／２の１６×１６画素の縮小画像ブロックと補間データを生成し、それぞれ可逆符号化するものとした。すなわち、階層構造として２層の例である。しかし、生成された１６×１６画素の縮小画像を再帰的に入力するようにすれば、そこから８×８画素の縮小画像が生成でき、補間データが何段も生成できる。従って、上記実施形態で本願発明が限定されるものではない。すなわち、可逆符号化部１０７は、要するに基礎となる画質の画像から段階的に高精細な画質の画像を復号するための階層データ構造を持つ符号化データを生成し、全ての符号化データを復号した場合にオリジナルのブロックの画像にまで可逆的に復元可能な階層データ構造を持つ可逆符号化データを生成するものであれば良い。この場合、どの縮小画像とどの補間データまでが、許容画質とするかは適宜決定すれば良いであろう。
【００５２】
［第２の実施形態］
第１の実施形態においては、ブロックサイズを３２×３２画素として判定，符号化を行う方法を示した。しかし、非可逆符号化方式によっては、このサイズでは符号化の性能を十分に出せない場合もある。例えば、そのような非可逆符号化方式として、第１の実施形態で用いたＪＰＥＧ２０００があり、理由について簡単に説明する。ＪＰＥＧ２０００ではエントロピー符号化で算術符号化を用いる。算術符号化では、符号化対象のシンボルの出現確率について想定値を設け、想定値を基に符号化を行う。そして、符号化を進めながら想定値を実際の出現確率に近づけていく。つまり、算術符号化は処理を進めながら、性能を向上させていく。このため、ブロックのサイズが小さいと、想定値を実際の値に近づけることはできず、十分な性能を得られない結果となる。
【００５３】
そこで本第２の実施の形態においては、判定処理と非可逆符号化方式で、処理対象とする矩形領域のサイズを変える方法を示す。具体的には、判定処理で用いる矩形領域のサイズを３２×３２画素（第１のブロックに対応）とし、非可逆符号化処理で用いる矩形領域のサイズをそれより十分に大きく、且つ、水平、垂直とも整数倍の、例えば１２８×１２８画素（第２のブロックに対応）とする。このように本第２の実施形態では、異なるサイズのブロックを利用することになるので、以降、前者の矩形領域（３２×３２画素）のブロックをサブブロック、後者の矩形領域（１２８×１２８画素）を単にブロックと呼ぶものとする。
【００５４】
また、第１の実施形態におけるレート制御では、非可逆符号化の符号量を十分に確保できないと判断した場合、全ての可逆符号化が適用されたブロックの補間データを削除し、非可逆符号化データに多くの符号量を確保した。この方法を採った理由は、補間データの削除に関する処理の軽減である。しかし、この方法では必要以上に補間データを削除してしまう、という問題がある。例えば、図７に示した通り、２つのブロック（２×１２８×１２８画素）から構成される画像があったとする。同図において、ブロック０，１それぞれに存在する可逆符号化のサブブロック（可逆サブブロック）のみの符号量を示していて、ブロックをまたいで、サブブロック番号を割り振っている。そして、番号１〜３，５〜７，１０のサブブロックについては、補間データサイズは10byteで、サブブロックに対して求められる目標符号量より10byte少ない。番号４のサブブロックについては、補間データサイズが60byteで40byte超過している。また、番号８のサブブロックについては補間データサイズが70byteで50byte超過し、番号９については、補間データサイズが80byteで60byte超過している。この画像に対して、第１の実施形態と同様な補間データの削除を行うと、１サブブロックあたり20byte目標符号量を下回る。結局、合計200byteのデータを削除することとなり、削除し過ぎてしまい、不必要に画質が劣化する可能性がある。この点を踏まえ、本第２の実施の形態においては、処理負荷は多少かかるが、補間データを必要以上に削除しない方法を示す。
【００５５】
図８は本第２の実施形態に係る画像処理装置の機能構成を示すブロック図である。図８に示すように、本第２の実施形態に係る画像処理装置は、ブロック分割部１０２、ブロックバッファ１０３、ブロック符号化部８０１、レート制御部８０２、画像符号化データ形成部８０３を備える。なお、図８に示す構成はハードウェアにより実現しても良いが、本第２の実施形態では、各部の機能をコンピュータに実現させるプログラムにより実現するものとする。このプログラムは上記外部記憶装置１４０７や記憶媒体ドライブ１４０８、もしくはＩ／Ｆ１４０９を介して外部装置からＲＡＭ１４０２にロードされるものとする。
【００５６】
続いて、図８の画像処理装置の処理について、図１０のフローチャートを用いて説明をする。
【００５７】
ＣＰＵ１４０１は、画像の符号化処理を開始すると、初期化処理を行う（ステップＳ１００１）。初期化処理の後、ブロック分割部１０２は、ブロックバッファ１０３へブロックデータの入力を行う（ステップＳ２０２）。ここまでの処理については、第１の実施形態と同様であるので、詳細説明を割愛する。なお、本第２の実施形態の冒頭でも説明したが、ブロックのサイズについては、１２８×１２８画素である。次いで、ブロックデータをブロック符号化部８０１へ入力し、ブロック符号化部８０１はブロック符号化処理を行う（ステップＳ１００３）。
【００５８】
このステップＳ１００３については、図９のブロック符号化のブロック図と、図１１のフローチャートを用いて説明する。ブロック符号化部８０１にブロックデータが入力されると、サブブロック分割部９０１において、３２×３２画素サイズのサブブロックに分割する（ステップＳ１１０１）。またこのタイミングで、サブブロックのカウンタi_subblock=0と初期化する。なお、以下の説明において、ブロック内のサブブロックの個数をＭとする。本第２の実施の形態においては、ブロックサイズ，サブブロックサイズから、Ｍ＝１６となる。次いで、サブブロックを属性判定部１０４に入力し（ステップＳ１１０２）、属性判定を行う（ステップＳ１１０３）。属性判定部１０４の処理については、第１の実施形態と同様であるので、説明を割愛する。属性判定の結果、写真であると判定した場合（ステップＳ１１０４でＹｅｓ）、サブブロックのイメージを非可逆符号化対象イメージ生成部９０２へ出力する（ステップＳ１１０５）。そして、図１２（ａ）に示したサブブロック符号化情報テーブルに圧縮フラグとして“０”を設定する（ステップＳ１１０６）。その後、サブブロックカウンタi_subblockをインクリメントし（ステップＳ１１０７）、サブブロック数のＭと比較する（ステップＳ１１０８）。もし、i_subblockがＭより小さければ（ステップＳ１１０８でＹｅｓ）、処理をステップＳ１１０２へ戻す。一方で、i_subblockがＭであれば（ステップＳ１１０８でＮｏ）、処理をステップＳ１１０９へ進める。
【００５９】
ステップＳ１１０４において、属性は写真でないと判断した場合（ステップＳ１１０４でＮｏ）、可逆符号化部１０７においてサブブロックの縮小ブロックに対して可逆符号化を行う（ステップＳ１１１０）。この処理については、第１の実施形態と同様である。次いで、注目サブブロックにおける縮小ブロックの符号列のビットレート(r_i_reduced)を求めて、ＴＲと比較を行う（ステップＳ１１１１）。もし、r_i_reducedの方が大きい場合（ステップＳ１１１１でＹｅｓ）、非可逆符号化の対象とするため、サブブロックのイメージを非可逆符号化対象イメージ生成部９０２へ出力する（ステップＳ１１０５）。一方で、縮小ブロックのビットレートr_i_reducedがＴＲ以下であるい場合（ステップＳ１１１１でＮｏ）、補間データの符号化を行う（ステップＳ１１１２）。その後、サブブロックのイメージを非可逆符号化対象イメージ生成部９０２へ出力し（ステップＳ１１１３）、サブブロック符号化情報テーブルに圧縮フラグとして“１”を設定する（ステップＳ１１１４）。ここで、ステップＳ１１１３でサブブロックのイメージを出力する理由について簡単に述べる。非可逆符号化は１２８×１２８画素サイズのブロックで行うため、可逆符号化が実施されたサブブロック（可逆符号化実施サブブロック）の領域に対して、何かしらの画素値を与えることが必要となる。本実施の形態においては、非可逆符号化が実施されるサブブロック（非可逆サブブロック）との画素値の連続性を考慮して与える。具体的には、可逆符号化実施サブブロックには、非可逆サブブロックとの画素値の連続性を持つ場合もあることに注目し、ブロック内の全可逆符号化実施サブブロックの画素値平均を用いる。このため、可逆符号化実施サブブロックのイメージを出力する。ステップＳ１１１４が終了すると、サブブロックのカウンタをインクリメントして（ステップＳ１１０７）、処理をステップＳ１１０８へ進める。ステップＳ１１０８の処理については、すでに説明しているため割愛する。
【００６０】
ステップＳ１１０９においては、サブブロック符号化情報テーブルを基に、着目ブロック内に非可逆サブブブロックが存在しているかどうかを判断する。もし存在しなければ（ステップＳ１１０９でＮｏ）、サブブロック符号化情報テーブルをレート制御部８０２へ出力する（ステップＳ１１１７）。一方で、存在する場合（ステップＳ１１０９でＹｅｓ）、非可逆符号化対象イメージ生成部９０２において、非可逆符号化の対象となる１２８×１２８ピクセルのイメージ（非可逆符号化対象イメージ）を生成する（ステップＳ１１１５）。このステップにおいては、非可逆符号化を行えるようにするために、可逆サブブロックの存在位置に対応する領域に対して、何らかの画素値を与える処理（穴埋め）が必要となる。この穴埋めについては、該当領域の符号がなるべく発生しないようにする必要がある。この点を念頭におき、本実施の形態では、注目ブロック内の非可逆符号化対象のサブブロックはそのままにし、それ以外の可逆符号化実施サブブロック内の全画素を、可逆符号化実施サブブロックの画素値の平均値（平均画素値）で穴埋め（ペイント）するものとする。具体的な処理については、次に述べる。
【００６１】
ステップＳ１１１５が開始すると、１２８×１２８画素のメモリ領域を確保する。次いで、非可逆サブブロックについて、ブロック内と同じ位置に、非可逆符号化対象イメージ内へ画素値をコピーする。その後、ブロック内の全可逆符号化実施サブブロックの平均画素値を求める。そして、ブロック内の可逆符号化実施サブブロックと同じ領域に対して、平均画素値をコピーする。この結果、１２８×１２８画素のブロック内の、可逆符号化するとして決定した３２×３２画素を単位とするサブブロック内の全画素が同じ値を持つことになり、高周波成分が少ない状態を作り出すことができる。このようにして、非可逆符号化対象イメージを生成した後、非可逆符号化部１０５では、非可逆符号化を実施する（ステップＳ１１１６）。非可逆符号化については第１の実施形態と同様であり、説明を割愛する。なお、非可逆符号化が終了すると、図１２（ｂ）のように示したように、非可逆符号化情報を生成し、レート制御部８０２へ出力する（ステップＳ１１１７）。ステップＳ１１１７の処理が終了すると、Ｓ１００３の処理を終える。
【００６２】
さて、図１０における注目ブロックの符号化（ステップＳ１００３）が終了すると、ブロックカウンタをインクリメントして（ステップＳ１００４）、ブロック数Ｎとの比較を行う（ステップＳ１００５）。もし、i_blockの方が小さければ（ステップＳ１００５でＹｅｓ）、処理をＳ１００２へ戻す。一方で、i_blockとＮが等しければ（ステップＳ１００５でＮｏ）、レート制御部８０２においてレート制御処理を行う（ステップＳ１００６）。
【００６３】
レート制御部８０２における処理の流れを図１３のフローチャートに示す。同図の処理は、第１の実施形態のレート制御の処理フロー（図４）とおおまかな流れは同じであり、相違点を中心に説明する。レート制御処理が開始すると、まず画像全体の可逆符号化実施サブブロックのビットレートr_losslessを算出する（ステップＳ４０１）。この後、画像全体の目標ビットレートTh_r1との比較を行う（ステップＳ４０２）。もし、r_losslessの方が大きければ（ステップＳ４０２でＮｏ）、非可逆符号化の目標ビットレートの算出を行う（ステップＳ４０４）。一方、r_losslessの方が小さければ（ステップＳ４０２でＹｅｓ）、補間データ削除のための符号化情報テーブルの更新を行う（ステップＳ１３０１）。ステップＳ１３０１の処理については、図１５のフローチャートにまとめてあるので、そちらを用いて説明することとし、以下では、本第２の実施の形態における補間データの削除方法に関する概略をまとめる。
【００６４】
本第２の実施の形態の冒頭でも説明したが、第１の実施の形態においては、必要以上に補間データを削除していた。これに対する改善として、目標圧縮率をサブブロックに適用したときの符号量（サブブロック平均符号量）を上回っているサブブロックのみについて、補間データを削除する方法がある。例えば、図７の符号量分布であれば、番号４，８，９のサブブロックの補間データを削除すればよい。
【００６５】
また別には、サブブロック平均符号量を超過しているサブブロックの符号量と、下回っているサブブロックの符号量を相殺させる。そして、超過している場合、超過している分だけ、補間データを削除する方法がある。例えば、図７の場合であれば、超過符号量は150byteで、下回っている符号量は70byteであり、80byte削除すれば十分である。そこで、サブブロック９の補間データの削除が必要であると判断し、削除を行う。
【００６６】
さらには、ブロック平均符号量を超過しているブロックを選択して、サブブロック平均符号量を上回っているサブブロックの補間データを削除する方法がある。図７であれば、ブロック０については、目標符号量を超過しているサブブロックの超過符号量は40byteである。また、目標符号量を下回っているサブブロックにおいて下回っている符号量（余符号量）は50byteである。このため、補間データの削除を行わない。一方でブロック１については、超過しているサブブロックの超過符号量は110byteで、下回っているサブブロックの余符号量は20byteである。このため、補間データの削除が必要となり、サブブロック８，９の補間データを削除する。
【００６７】
これら、いずれの方法でも、可逆符号化が実施された領域の符号量を、当該領域に対して目標圧縮率を適用して得られる符号量より小さくできる。このため、非可逆符号化に必要となる符号量を確保することはできる。以下では、３番目に述べた方法について、図１５のフローチャートに従い説明する。
【００６８】
符号化情報テーブルの更新処理が開始すると、ブロックカウンタi_blockを０にセットする（ステップＳ１５０１）。次いで、i_block番目のブロックのビットレートr_lossless_i_blockを算出して、Th_r1と比較する（ステップＳ１５０２）。もし、r_lossless_i_blockの方が大きければ、当該ブロックについては、画像全体の可逆符号化の符号量が閾値(Th_r1)を超過している原因であると考える。その上で、Th_r1を超える可逆符号化実施サブブロックの補間データを出力しないように、第１の実施形態と同様な方法で、サブブロック符号化情報テーブルを更新する（ステップＳ１５０３）。例えば、もし注目ブロックにおいてＭ−１番目のサブブロックの補間データを出力しない場合、図１６のようになる。すなわち、Ｍ−１番目のサブブロックの圧縮フラグを“２”にし、その上で補間データサイズを削除するために、可逆符号kデータサイズを更新する（図示の場合「２５」だけ減じる）。そして、補間データを削除するために、データのポインタを縮小画像ブロックのアドレスに更新する。ステップ１５０３の処理が終了すると、ブロックカウンタをインクリメントし（ステップＳ１５０４）。一方で、ステップＳ１５０２でr_lossless_i_blockがTh_r1より小さい場合、当該ブロックについては、画像全体の可逆符号化の符号量が閾値(Th_r1)を超過する原因ではない、と考える。そして、処理をステップＳ１５０４へ進める。ステップＳ１５０４が終わると、ステップＳ１５０５へ進み、ブロックカウンタとブロック数を比較する（ステップＳ１５０５）。もし、ブロックカウンタの値がブロック数より小さい場合（ステップＳ１５０５でＹｅｓ）、処理をステップＳ１５０２へ戻す。一方で、ブロックカウンタの値がブロック数と同じである場合（ステップＳ１５０５でＮｏ）、ステップＳ１３０１の処理を終える。
【００６９】
上記のようにしてステップＳ１３０１が終了すると、非可逆符号化の目標ビットレートを算出し（ステップＳ４０４）、画像全体の非可逆ブロックに対してレート制御を行う（ステップＳ４０５）。ここまでの処理が終了すると、符号化した結果の情報を画像符号化データ形成部８０３へ出力する（ステップＳ１３０２）。
【００７０】
図１０におけるステップＳ１００６のレート制御処理が終了すると、画像符号化データ形成部８０３において符号列の形成を行う（ステップＳ１００７）。このステップでは、図１８に示したとおり、画像符号化データの先頭に配置するヘッダの情報を生成する。ヘッダには、画像の縦横サイズ，ブロックのサイズ，各ブロックの符号長、各サブブロックの圧縮フラグ，符号長等がまとめられる。他には、非可逆符号化を復号する上で必要となる情報もまとめられる。次いで、各ブロックの符号列がラスタスキャン順に並べられる。そして、各ブロックの符号列としては、最初に可逆符号化実施サブブロックの符号列が並べられ、それに続いて、非可逆符号化対象イメージの符号列が並べられる。ここで、可逆符号化実施サブブロックの符号列と、非可逆符号化対象イメージの符号列の２つを並べることを述べたが、どちらか一方しかない場合は、該当符号列のみが並べられることになる。例えば、注目ブロックにおいて、可逆符号化実施サブブロックが存在しない場合、非可逆符号化対象イメージの符号列のみが並べられる。また、可逆符号化実施サブブロックの符号列については、ラスタスキャン順に非可逆符号化が実施されたサブブロックの符号列が並ぶ。ここで、並べられる符号列は、可逆符号化が実施されたサブブロックの符号列のみである。例えば、番号０、３のサブブロックのみに対して可逆符号化が実施されたのであれば、これらのサブブロックの符号列のみが並べられる。さらに、各サブブロックの符号列においては、補間データの符号列、縮小画像の符号列が順に並ぶ。なお、補間データが削除されたサブブロックについては、縮小画像の符号列のみが並べられる。例えば、番号０、３のサブブロックに対して可逆符号化が実施され、番号０については補間データの削除が行われたとする。その場合には、番号０については縮小画像の符号列のみが並べられ、番号３については、補間データと縮小画像の符号列が並べられることになる。
【００７１】
これらの処理により、画像符号化データの形成が終了すると、画像符号化処理は完了する。
【００７２】
［その他の実施形態］
補間データの削除方法として、第１，２の実施形態において、いくつか示したが、本発明の範疇に入る手法はそれらだけではない。その他として、第２の実施形態では選択的に補間データを削除する方法を説明したが、補間データに対して予め、優先順位をつけておく。その上で、優先順位に従って、削除すべきデータを決定する方法でもよい。なお、優先順位のつけ方としては、各補間データの符号量と、補間データを復号することにより得られる画質向上の比率などが考えられる。
【００７３】
実施形態においては、可逆符号化方式の階層数として２段階の方法を示したが、これに限らない。例えば、縮小画像に対して、さらに補間データ（補間データ１）と縮小画像を生成して、補間データ１、補間データ２、縮小画像の３段階構成にしてもよい。その際、削除が許されない最低限の画質を保証するデータとして、縮小画像のみを設定してもよい。また、途中の解像度を生成するために必要な、縮小画像と補間データ２を削除不可と設定してもよい。また、階層数を３段階以上にした場合、基本階層は複数階層から構成される場合もあれば、１階層から構成されることもある。他方、付加的階層についても、複数階層から構成される場合もあれば、１階層から構成されることもある。
【００７４】
文字，線画等の領域における符号列における階層のデータは、補間データと縮小画像の組に限られることはない。あくまで、基本階層と付加的階層の関係を持つことが可能な階層構造であればよい。一例として、注目ブロック内の全画素の上位ビット群（例えば上位３ビット）を基本階層として、下位ビット群（例えば下位５ビット）を付加的階層とする。さらにその上で、上位ビット群には予測符号化等の符号化方式を適用する方法がある。
【００７５】
文字，線画等の領域における縮小画像の可逆符号化方式として、ＪＰＥＧ−ＬＳを使うものとして説明したが、これに限られることはない。例えば、ＪＰＥＧ Ｓｐａｔｉａｌ方式、ラン・レングス符号化方式、ＰＮＧなどの、予測符号化方式でも構わない。さらには、実施形態として、文字，線画等の領域における高効率な符号化性能を得るために、予測符号化方式を用いる方式を示した。しかし、本発明は予測符号化方式に限られることはなく、ＬＺ７７，ＺＩＰ等の辞書型符号化方式を用いてもよい。
【００７６】
写真領域の符号化処理として、ＪＰＥＧ２０００を用いる方法を示したが、これに限られることはなく、レート制御を行える符号化方式であれば、本発明の範疇となる。
【００７７】
実施形態においては、写真領域の符号列をレート制御するために、写真領域の符号化方式として、無数の階層数を持つことができるＪＰＥＧ２０００を用いた。しかし、目標符号量未満の画像符号化データを出力する画像処理装置を想定するのであれば、階層数は無数でなくてもよい。例えば、写真領域中のブロックに対して、離散ウェーブレット変換やＤＣＴ等の周波数変換を行い、全係数をビットプレーン分割して、各ビットプレーンを階層とみなす。つまり、この方法であれば階層数はビットプレーンの枚数となる。その上で、各階層を単位としてエントロピー符号化する。そして、符号列がこのような階層を取る場合に、写真領域としての目標符号量以下の符号列を生成するためには、ＬＳＢのビットプレーンを削除し、残っている符号量を算出する。もし、当該符号量が目標符号量以下でなければ、１つ上位にあるビットプレーンを削除して、残っている符号量を算出し、目標符号量との比較を行う。この処理を繰り返すことで、目標符号量以下の写真領域の符号列を生成する。なお、文字，線画等の領域に適用する符号化方式は多くの階層数を持たせることは難しく、写真領域の符号量調整で、画像全体の目標符号量以下にさせる必要がある。したがって、非可逆符号化方式の階層数をＮ１段階、可逆符号化方式の階層数をＮ２段階とした場合、Ｎ１＞Ｎ２という関係が成り立つ。
【００７８】
実施形態においては、属性判定部を設けて、注目するブロックもしくはサブブロック（符号化処理対象矩形）の属性判定を行い、符号化方式を選択する方法を示したが、属性判定を設けない方法でもよい。その場合には、いったん全ての符号化処理対象矩形を可逆符号化部に入力し、可逆符号化を実施する。そして、ブロック平均符号量もしくはサブブロック平均符号量を超える符号化処理対象矩形については、全て非可逆符号化を実施する。こうすることで、写真領域の符号化対象矩形は非可逆符号化が適用される。なぜなら、写真領域については、可逆符号化を実施した際の圧縮率は１／２(=１２bpp)程度であり、実用的なビットレート（例えば2bpp以下）では、ブロック，サブブロック平均符号量を超えてしまうからである。
【００７９】
また、実施形態ではブロックのサイズとして３２×３２画素や１２８×１２８画素を例にしたが、可逆、非可逆符号化の双方が支障なく符号化できる程度の複数画素を内包するブロックであれば良いので、上記実施形態に限定されるものではない。
【００８０】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は画像データの符号化技術に関するものである。
【背景技術】
【０００２】
離れた場所からプリンタに対してプリントを指示するプリント形態があり、それをリモートプリントと言う。リモートプリントにおいて、ＰＤＬのレンダリングは、インターネット上のサーバー上で行われることがある。この場合、ネットワークを介して、プリントジョブを伝送するため、レンダリングした画像（文書画像）に対しては、レート制御機能を持つ画像圧縮が必要となる。レート制御機能とは、画像圧縮されたデータ（画像符号化データ）を、復号することなく符号量を変更できる機能である。この機能により、画像符号化データを伝送するネットワークの帯域幅に応じたデータ量の変更が容易となる。
【０００３】
また、文書画像においては、文字，線画等の領域、写真の領域が混在する場合も少なくない。この点に着目した高効率な圧縮方式として、領域毎に適した符号化方法を用いる適応符号化方式がある。その例として、特許文献１がある。
【０００４】
特許文献１においては、画像をブロックに分割して、写真領域のブロックには、高周波成分のデータを大きく削減して高圧縮性を狙える、周波数変換をベースとした符号化を用いる。一方、文字，線画等のブロックには、領域の低エントロピー性を利用して、高効率な符号化性能を実現可能な予測符号化を用いる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−６７１１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
適応符号化による高画質／高圧縮の利点を活かし、かつ、用途に応じて符号量の調整が可能なレート制御機能の実現が求められている。レート制御機能を持つ適応符号化には、ＪＰＥＧ２０００のような、レート制御機能を有する周波数変換ベースの符号化方式が望ましい。一方、予測符号化は多値データを「多値」として処理を行うため、レート制御機能を持たず、利用しずらい。
【０００７】
かかる点を踏まえると、適応符号化のレート制御のためには次のような処理が考えられる。先ず、文字・線画等の領域のブロックに対して予測符号化を実施する。その後、該当領域の符号量を算出する。その上で、画像全体の目標符号量から、文字・線画等の領域の符号量を減算して、写真領域の目標符号量を得る。次いで、写真領域のブロックに対し周波数変換ベースの符号化方式を実施する。そして、写真領域に対して目標符号量となるようにレート制御を行い、画像全体に求められる目標符号量を達成する処理となる。
【０００８】
ただし、この処理においては、文字・線画等の領域の符号量が多くなる場合、写真領域に対して、十分に符号量を割り当てられないことがある。極端な場合には、文字，線画等の領域のみで、画像全体の目標符号量を超過してしまうことも発生し得る。
【０００９】
この問題に対しては、上記方法で写真領域の目標符号量を得た後に、当該目標符号量は不十分であると判断した際、文字，線画等の領域の一部もしくは全部のブロックを周波数ベースの符号化方式で圧縮し直すことである。そして、その上で、周波数ベースの符号化方式で圧縮した領域に対してレート制御を行うことである。たしかに、この場合、画像全体の目標符号量に符号化することができるが、この方法では、文字，線画等の領域に対する予測符号化が終了した後にも、該当領域のビットマップを保持しなければならない。つまり、メモリ使用量の増加を伴う。もしくは、ビットマップを保持しないのであれば、予測符号化の復号を行ってビットマップを生成した上で、圧縮をし直す必要があり、処理時間の増大につながる。
【００１０】
本発明は上記点に鑑みなされたものであり、ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することを可能ならしめる技術を提供しようとするものである。
【課題を解決するための手段】
【００１１】
この課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像を符号化して符号化データを生成し、目標とするビットレートに従い、生成された符号化データ中の一部を削除し出力するレート制御手段を有する画像符号化装置であって、
複数画素で構成されるブロックを非可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ１段階の階層データ構造を持つ符号化データを生成する第１の符号化手段と、
前記ブロックを予測演算を用いて可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ２（Ｎ１＞Ｎ２）段階の階層データ構造を持つ符号化データを生成する第２の符号化手段と、
符号化対象画像から前記ブロックを単位に入力する入力手段と、
入力した着目ブロックを解析することで、当該着目ブロックを前記第１の符号化手段、前記第２の符号化手段のいずれで符号化すべきかを判定する判定手段と、
該判定手段により、前記着目ブロックを前記第２の符号化手段で符号化すべきとして判定された場合、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを前記第２の符号化手段により生成させ、生成された符号量が予め設定された目標符号量を超えるか否かを判定し、超えると判定した場合には前記着目ブロックを前記第１の符号化手段で符号化すべきブロックとして変更し、超えないと判定された場合には、残りの階層の符号化データを前記第２の符号化手段により生成させる第１の制御手段と、
前記判定手段、或いは、前記第１の制御手段によって前記第１の符号化手段で符号化すべきと判定されたブロックに対して前記第１の符号化手段により符号化させ、符号化データを生成させる第２の制御手段とを有する。
【発明の効果】
【００１２】
本発明によれば、ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することが可能になる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施形態における画像符号化処理の機能ブロック図。
【図２】第１の実施形態における画像符号化処理のフローチャート。
【図３】符号化情報テーブルの説明図。
【図４】レート制御部１０６のフローチャート。
【図５】符号化情報テーブルの説明図。
【図６】補間データ削除の説明図。
【図７】補間データ削除の説明図。
【図８】第２の実施形態における画像符号化処理の機能ブロック図。
【図９】ブロック符号化部８０１のブロック図。
【図１０】第１の実施形態における画像符号化処理のフローチャート。
【図１１】ブロック符号化部８０１のフローチャート。
【図１２】サブブロック符号化情報テーブルの説明図。
【図１３】レート制御部８０２のフローチャート。
【図１４】画像処理装置のブロック図。
【図１５】ステップＳ１３０１のフローチャート。
【図１６】サブブロック符号化情報テーブルの説明図。
【図１７】補間データ生成方法の説明図。
【図１８】画像符号化データの構成の説明図。
【発明を実施するための形態】
【００１４】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１５】
［第１の実施形態］
最初に、従来技術の課題に対する、本発明における解決方法の考え方について述べる。なお、以下では、文字・線画等の領域については、高周波性の維持が必要であるので、予測符号化を用いた可逆符号化を用いるものとする。そして、写真領域（階調画像）については、解像度よりも階調性が重要であるので、高圧縮性が期待できる周波数変換ベースの非可逆符号化を用いるものとする。その上で、文字・線画等の領域を符号化する手法を可逆符号化方式、写真領域を符号化する手法を非可逆符号化方式として説明する。
【００１６】
処理のおおまかな考え方としては、２つある。１つ目は、画像をブロック単位に、可逆符号化対象ブロック、非可逆符号化対象ブロックに仮判定する。そして、ブロックをラスタスキャン順に符号化処理する過程において、ブロック平均符号量を超過する可逆符号化対象ブロックに対しては、可逆符号化の符号列を出力せずに、非可逆符号化対象ブロックに切り替える。こうすることで、非可逆符号化のブロックに十分な符号量を割り当てられない問題の発生を防ぐ。
【００１７】
より詳しくは次のとおりである。まず、ラスタスキャン順に、写真領域のブロックには非可逆符号化を行い、文字・線画等の領域のブロックに対して可逆符号化を行う。その上で、文字，線画等の領域の各ブロックの可逆符号化が終了した後に、逐次注目ブロックの符号量を算出するとともに、ブロック平均符号量と比較し、非可逆符号化による圧縮のし直しの要否を判断する。もし、注目ブロックの符号量の方が大きければ、可逆符号化の符号列を出力せず、ラスターイメージを用いて非可逆符号化で圧縮し直す。一方で、注目ブロックの符号量の方がブロック平均符号量以下であれば、そのまま符号列を出力するものとする。例えば、ラスタスキャン順で見て連続するブロックの一部について、図６（ａ）のように符号量が分布する場合を考える。同図で、ブロック番号１，２，５〜１０，１６のブロックは、ブロック平均符号量を超えている。このため、各ブロックの可逆符号化が終了した後、逐次、非可逆符号化で圧縮し直す。また、番号３のブロックについては、そのまま出力する。一方で、写真領域については、非可逆符号化を実施する。そして、すべてのブロックの符号化が終了した後で、可逆符号化のブロックの符号量の総和を算出し、画像全体の目標符号量から減じる。そこで得られた符号量を、非可逆符号化の目標符号量として、レート制御を行う。
【００１８】
この方法については、使用メモリ量や処理時間の増大を回避しつつ、非可逆符号化のための符号量を確保できるが、必要以上に文字，線画等の領域を非可逆符号化で圧縮してしまうことがある。つまり、可逆符号化のブロック全体から見て、ブロック平均符号量を超過する可逆符号化のブロックが少ない場合、画像全体で見れば、非可逆符号化のための符号量を十分に確保できる。それにもかかわらず、前述方式では非可逆符号化による圧縮のし直しを行ってしまう。
【００１９】
本発明における２つ目の考え方は、これに対する対応策である。具体的には、可逆符号化の符号列に階層性を持たせることで解決する。ここで考える階層は、符号化対象領域における最低限の画質を保証するために必要な階層（基本階層）と、基本階層と併せて復号することでより高画質な画質を生成できる階層（付加的階層）に分類されるものである。そして、可逆符号化の符号列は、基本階層と付加的階層の構造を持つことになる。このような階層性を持たせることで、符号列生成後に付加的階層を削除して、可逆符号化の符号量を減らすことができる。したがって、付加的階層の削除により、符号量をブロック平均符号量以下にできるブロックについては、圧縮のし直しをせず、可逆符号化の符号列にしておく。その上で、符号化終了後に、非可逆符号化のための符号量が少ないと判断すれば付加的階層を削除して符号量を確保し、そうでなければ、削除を行わず可逆符号列をそのまま出力することが可能となる。結果として、文字，線画等の領域に対して、必要以上に非可逆符号化で圧縮してしまう問題を避けることができる。具体的な処理概要を、図６（ｂ）を用いて説明する。同図において、各可逆符号化が適用されるブロックは、階層１と階層２から構成されるものとして、階層１は上記の「基本階層」であり、階層２は「付加的階層」である。この符号量分布において、ブロック番号８，１０，１６のブロックのみ、非可逆符号化で圧縮し直すことが必要となる。これは、削除してはならない基本階層の符号量がブロック平均符号量を超過しているためである。そして、このようなブロックが画像中に多数存在していると、非可逆符号化に十分な符号を割り当てられなくなるからである。しかし、ブロック番号１，２，５〜７，９のブロックについては、各ブロックの符号量はブロック平均符号量を超えているが、基本階層の符号量がブロック平均符号量より少ない。このため、階層２を削除することで符号量を減らして、ブロック平均符号量より少なくすることが可能ある。この点を踏まえて、非可逆符号化による圧縮のし直しを行わないで済む。一方で、写真領域については非可逆符号化で逐次符号化を行う。そして、全ブロックの符号化が終了した後に、可逆符号化のブロックの符号量の総和を算出し、画像全体の目標符号量から減じる。ここで得られた符号量を非可逆符号化の目標符号量と考え、十分な符号量であれば、当該目標符号量で非可逆符号化の符号化を行う。他方で、十分な符号量でないとした場合、可逆符号化のブロックの一部、もしくは全部の階層２のデータを削除して、非可逆符号化のための符号量を確保する。その上で、非可逆符号化を実施する。本実施の形態においては、かかる２つ目の考え方に基づいた方法を採用するものであり、以下にその詳細について説明する。
【００２０】
図１４は本実施形態に係る画像処理装置として機能する情報処理装置の基本構成を示す図である。本装置は、外部から符号化対象となる画像、並びに目標ビットレートＴＲの入力を受け付け、目標ビットレートの画像符号化データを生成するものである。ここで言う目標ビットレートＴＲとは、画像の圧縮率を示す指標であり、圧縮処理により生成されたデータの１画素当たりの符号量（ビット数）である。単位はbpp(bit per pixel)となる。
【００２１】
１４０１は装置全体の制御を司るＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理を実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。さらに、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７は外部記憶装置で、ハードディスクドライブ装置等の大容量情報記憶装置である。ここにＯＳ（オペレーティングシステム）や後述する画像符号化処理の為のプログラムや画像等のデータなどが保存されている。そして、ＣＰＵ１４０１による制御によって、これらのプログラムやデータはＲＡＭ１４０２上の所定のエリアにロードされる。１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどのコンピュータ可読記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化処理の為のプログラム、符号化対象の画像を記録しておいても良くい。その場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えば画像符号化装置をＩ／Ｆ１４０９に接続し、当該画像符号化装置によって生成された画像符号化データを本装置のＲＡＭ１４０２や外部記憶装置１４０７に入力することもできる。１４１０は上述の各ユニットを繋ぐバスである。
【００２２】
なお、符号化対象の画像、並びに目標ビットレートＴＲについては、本装置のユーザーが、キーボード１４０４、マウス１４０５により指定する。そして、ＣＰＵ１４０１は、外部記憶装置１４０７に格納されている、本発明の画像符号化処理プログラムをＲＡＭ１４０２にロードするとともに、符号化対象の画像，ＴＲをＲＡＭ１４０２へ展開する。その後、ＣＰＵ１４０１は、画像符号化処理を行い、生成した画像符号化データを、Ｉ／Ｆ１４０９を通して、外部装置に出力するものである。
【００２３】
本実施形態における符号化対象の画像データは、外部記憶装置１４０７に格納されており、符号化後のデータも外部記憶装置１４０７に格納するものとする。ただし、これは便宜的なものであり、符号化対象の画像データをネットワークを介して受信しても良いし、符号化後のデータをネットワークを介して送信しても良い。勿論、符号化対象の画像をイメージスキャナより読込むものとしても構わないので、符号化対象の画像データの発生源、符号化済みの出力対象で本願発明が限定されるものではない。また、実施形態における符号化対象の画像データは、ＲＧＢカラー多値画像データとし、各コンポーネント（色）は８ビット（０乃至２５５の２５６階調）として説明する。但し、ＲＧＢ以外のコンポーネントの構成（例えば、グレーやＣＭＹＫ）でも構わず、色空間の種類，コンポーネントの個数は問わない。また、１成分のビット数も８ビットに限らず、８ビットを超えるビット数、もしくは８ビット未満のビット数でも構わない。更に、符号化対象の画像は水平方向W画素、垂直方向H画素により構成されるものとする。
【００２４】
図１は本実施形態に係る画像処理装置における、画像符号化アプリケーションをＣＰＵ１４０１が実行した場合の機能構成を示すブロック図である。同図のように、ブロック分割部１０２、ブロックバッファ１０３、属性判定部１０４、非可逆符号化部１０５（第１の符号化部）、レート制御部１０６、可逆符号化部１０７（第２の符号化部）、可逆符号化可否判定部１０８、画像符号化データ形成部１０９を備える。なお、図１ではコンピュータプログラム（ソフトウェア）の例をしめすものとしているが、全処理部もしくはその一部をハードウェアにより実現しても良いのは勿論である。また、
図２は、本実施形態に係る画像処理装置の符号化処理（ＣＰＵ１４０１の処理）を示すフローチャートである。以下、図１，図２を参照して、本実施形態に係る画像処理装置が行う画像符号化処理について説明する。
【００２５】
ＣＰＵ１４０１は、画像の符号化処理を開始すると、初期化処理を行う（ステップＳ２０１）。この初期化処理として、ブロックカウンタに対する０の設定，外部から指定された目標ビットレートＴＲ(bpp)の設定、符号化対象の画像の先頭ポインタの取得、等である。初期化処理の後、ブロック分割部１０２は、ブロックバッファ１０３へブロックデータの格納する（ステップＳ２０２）。
【００２６】
ブロックバッファ１０３は１ブロック分の画素データを格納する領域を持ち、ブロック分割部１０２から出力されるブロックデータを順次格納していく。ブロックのサイズは、水平方向Ｂw画素、垂直方向Ｂh画素である。説明の便宜上、符号化対象のオリジナル画像の水平方向画素数ＷはＢwの整数倍、垂直方向画素数ＨはＢhの整数倍であり、矩形ブロックに分割した場合に正規のサイズではないブロックが発生しないものとする。
【００２７】
また、ブロックバッファ１０３に必要とされる容量はＢｗ×Ｂｈ×３（RGB分）バイトである。ここで、ブロックのサイズの設定について簡単に述べる。後述するが、ブロックを単位として、領域の属性（文字，線画等、写真の２種類）を判断し、可逆符号化方式と非可逆方式のいずれを用いるか選択する。このため、ブロックのサイズが大きいと、写真領域と文字，線画等の領域の境目等において、可逆符号化のブロックと非可逆符号化のブロックが混在する場合に、歪みと見えてしまう。一方、あまり小さくすると、符号化において参照できる範囲が限定されてしまい、符号化の性能低下を招く。これらのことを勘案し、本実施の形態においては、Ｂｗ＝３２、Ｂｈ＝３２とする。なお、本実施の形態における以下の説明では、画像全体にわたるブロックの個数（（Ｗ／Ｂｗ）ｘ（Ｈ／Ｂｈ））をＮと定義する。また、ブロックバッファ１０３へのブロックデータの取得順は、このブロックを単位とするラスタースキャン順とする。
【００２８】
ブロックバッファ１０３へのブロックデータの格納が終わると、属性判定部１０４はブロックデータを解析し、その属性判定処理を行う（ステップＳ２０３）。具体的な判定処理は次に述べるとおりである。
【００２９】
属性の判定は、Ｂｗ×Ｂｈ画素のブロックデータを入力し、ブロック内をＫ画素単位（本実施形態ではＫ＝２×２画素）にラスタースキャン順で処理する。以降、この２×２画素をピース（Ｐｉｅｃｅ）と呼ぶ。実施形態の場合、１ブロックのサイズは３２×３２画素であるので、この中には２５６（＝１６×１６）個のピースが存在することとなる。図１７の右側に示す図は、１つのピースに含まれる４つの画素を示している。
【００３０】
判定手順は、まず、１つのピースの中で、色数が何色であるかの判別を行う。注目しているピース内の４個の画素を図１７の右側に示すａ、ｂ、ｃ、Ｘで表現し、画素ａ，ｂ，ｃ，Ｘそれぞれの画素値（色）が一致するかどうかの判定によって、ピースの色数を判定できる。ａ，ｂ，ｃ，Ｘそれぞれの差分値Ｄａｂ，Ｄａｃ，Ｄａｄ，Ｄｂｃ，Ｄｂｄ，Ｄｃｄを次式（１）により求める。
Ｄａｂ＝ａ−ｂ
Ｄａｃ＝ａ−ｃ
Ｄａｄ＝ａ−Ｘ
Ｄｂｃ＝ｂ−ｃ
Ｄｂｄ＝ｂ−Ｘ
Ｄｃｄ＝ｃ−Ｘ …（１）
【００３１】
そして、差分値Ｄａｂ，Ｄａｃ，Ｄａｄ，Ｄｂｃ，Ｄｂｄ，Ｄｃｄのうち、０となる数Ｆをカウントする。従って、差分値は６つあるので、値Ｆは０乃至６の値を取り得る。ここで、Ｆ＝０の場合、ピース内の４画素ａ，ｂ，ｃ，Ｘは全て違う色であることを意味するのは明らかで、色数が４であることを示す。また、Ｆ＝１の場合、４画素中２画素が同じ色となるので、ａ，ｂ，ｃ，Ｘの色数は３となる。同様に、Ｆ＝２の場合には、色数が２であることを示し、Ｆ＝３以上の場合にはａ，ｂ，ｃ，Ｘが全て同じ色であることになる。以上の方法により、着目ピースの色数の判別が可能となる。そして、ブロック内の全ピースの色数を判定する。ブロックの終端に位置するピースの色数判定が終了したら、符号化方式の判定を行う。本実施形態では、ブロック内のピースの色数が１色の場合の数、２色の場合の数、３色の場合の数、４色の場合の数をカウントしておく。ブロック内のピース数と、１色ピース及び２色ピースのカウント数ＣＰ１を比較して、ＣＰ１が総ピース数の５０％以上であれば（過半数を占めれば）、注目ブロックは文字，線画等の領域であると判定する。一方、ＣＰ１が総ピース数の５０％未満である場合には、注目ブロックは非文字線画領域、換言すれば写真領域（階調領域）であると判定する。なお、上記の代わりに、３色ピース及び４色ピースの合計カウント数と総ピース数との比で判定しても良いのは勿論である。
【００３２】
属性判定（ステップＳ２０３）を行った結果を受け、着目ブロックが文字、線画領域にあるか、写真領域であるかの判定を行う。そして、文字、線画領域にあると判定された場合には後述する第１の制御処理を行う。また、写真領域である場合には以下に説明する２の制御処理を行う。
【００３３】
以下は、ステップＳ２０４でＹｅｓ、すなわち、着目ブロックが写真領域である場合の第２の制御処理である。非可逆符号化部１０５は、着目ブロックのビットマップイメージを非可逆符号化する（ステップＳ２０５）。ここで非可逆符号化とは、符号化終了後に符号列の一部を切り捨てることが可能な階層性を持つ非可逆符号化である。例えば、ビットプレーンを単位として符号化を行うビットプレーン符号化、画像中の周波数係数を低い成分からグループ化させて、グループを単位として順に符号化を行う周波数ベースの階層的符号化がある。本実施の形態においては、ビットプレーン符号化，周波数ベースの階層的符号化を併せ持つ、国際標準方式のＪＰＥＧ２０００(ITU-T T.800 | ISO/IEC 15444-1)により符号化を行う。ＪＰＥＧ２０００の詳細については、勧告書等に記載されているので、ここでは説明を省略する。なお、後述するが、本実施の形態における非可逆符号化方式における階層数は２であるが、ＪＰＥＧ２０００は目標符号量の符号列を生成できるレート制御機能を持っているため、階層数は無数にあると言える。
【００３４】
非可逆符号化で生成された符号列については、レート制御部１０６に出力する。その上で、図３のとおり、ＲＡＭ１４０２に予め確保しておいた、ブロックの符号化情報をまとめたテーブル（符号化情報テーブル）に、非可逆符号化を行ったことを示す圧縮フラグ“０”を記録する（ステップＳ２０６）。さらに、非可逆符号化データサイズとデータの先頭ポインタを記す。なお、非可逆符号化部１０５では、符号列における所定のデータを単位として、符号量と、データを復号しないことにより復号画像上に発生する歪みの比率（Ｒ−Ｄ比）を求める。そして、レート制御部１０６では、Ｒ−Ｄ比の情報を基に、歪みの発生を抑えつつ、生成された符号化データ中の符号を選択的に削除してレート制御を行う。このＲ−Ｄ比を求める処理は負荷が大きいため、非可逆符号化の符号列に求められる目標符号量から見て、必要以上の符号列を生成することは望ましくない。つまり、後述するレート制御部１０６において、レート制御を行える程度に符号を生成すればよい。
【００３５】
次に、着目ブロックが文字，線画領域にあると判定された場合の第１の制御処理について説明する（ステップＳ２０４でＮｏ）。この場合、可逆符号化部１０７は、着目ブロックに対し、階層性を持たせることが可能な予測演算を主体とする可逆符号化を行う。具体的には、着目ブロックから補間データと縮小画像ブロックを生成する。その上で、先ず、縮小画像ブロックに対して可逆符号化を行う（ステップＳ２０７）。ここで、補間データと縮小画像ブロックについて簡単に説明する。縮小画像ブロックは、図１７における各ピースの右下の画素Pn(1,1)を集めて得られるデータであり、結局のところ、オリジナルのブロックに対して水平、垂直とも１／２のサイズである。一方、補間データは各ピースの残りの画素Pn(0,0),Pn(1,0),Pn(0,1)を集めたデータである。縮小画像ブロックについては、注目ブロックの最低限の画質の画像を表示する上で必要となるデータであり、図６（ｂ）の階層１に相当する。つまり、この階層１の１画素から同じ値の画素を２×２個生成すれば、少なくともオリジナルのブロックと同じサイズの画像を構成できる。また、補間データについては、非可逆符号化のための符号量確保のために削除され得るデータであり、図６（ｂ）の階層２に相当する。なお、可逆符号化で用いる符号化方式としては、国際標準方式のＪＰＥＧ−ＬＳ（ITU-T T.87 | ISO/IEC 14495-1）を用いるものとする。ＪＰＥＧ−ＬＳの詳細については、勧告書等に記載されているので、ここでは説明を省略する。縮小画像ブロックの符号化が終了した後、可逆符号化可否判定部１０８は、縮小画像ブロックの符号列に関するビットレート（r_i_block）を算出し、目標ビットレートＴＲとの比較を行う（ステップＳ２０８）。なお、縮小画像ブロックの符号量をM_i_block（バイト）としたとき、縮小画像ブロックの符号列に関するビットレートr_i_blockは、次式に従って算出できる。
r_i_block＝8 * M_i_block / (Bw/2 * Bh/2)＝32 * M_i_block/(Bw * Bh)
【００３６】
もし、算出したビットレートr_i_blockが目標ビットレートＴＲより大きい場合（ステップＳ２０８でＮｏ）、着目ブロックは図６（ｂ）のブロック番号８、１０や１６と同じ状況であるとことになる。従って、レート制御を保証するために、着目ブロックについての可逆符号化での符号化をあきらめ、非可逆符号化する（ステップＳ２０５）。なお、繰り返すが、非可逆符号化により圧縮し直す理由は、縮小画像の符号列については、当該ブロックの画像を表示でする必須のものであり、削除することはできないためである。そして、このようなブロックが画像中に多く存在すると、非可逆符号化に割り当て可能な符号量が極端に少なくなる可能性があるからである。また場合によっては、可逆符号化の符号量だけで目標符号量を超えてしまう可能性があるからである。他方、ビットレートr_i_blockが目標ビットレートＴＲ以下である場合（ステップＳ２０８でＹｅｓ）、非可逆符号化による圧縮のし直しを行わず、残りの補間データの符号化を行う（ステップＳ２０９）。これは、このようなブロックが多く存在しても、非可逆符号化への符号量割り当てに関する問題は発生しないからである。なお、補間データの符号化は、可逆符号化方式，非可逆符号化方式のいずれでもよい。ただし、本実施の形態においては、文字，線画等の領域を可逆符号化するものとしているので、補間データについても可逆符号化を行うものとする。具体的な方法としては、次に述べる方式を用いる。
【００３７】
補間データの符号化はピース単位で行うものであり、属性判定部１０４において導出した色数に応じて符号を割り当てる。もし、注目ピース内の色数が１色の場合、“１”（１ビット）を出力する。復号装置では、縮小画像を復号した後、もし補間データの符号語が“１”であった場合、縮小画像中の該当する１つの画素をＰn(1,1)と見なす。そして、それと同じ色の画素Ｐn(0,0),Ｐn(1,0),Ｐn(0,1)を生成すれば良いことになる。
【００３８】
また、注目ピース内の色数が１色ではなく、以下の次式（２）が成り立つ場合、“０１”（２ビット）を出力する。
Pn(0, 1) = Pn-1(1, 1)
かつ
Pn(1, 0) = Pn-b(1, 1)
かつ
Pn(0, 0) = Pn-b-1(1, 1) …（２）
ここで、Ｐnが着目ピースを示し、Ｐn-1,Ｐn-b,Ｐn-b-1の関係は図１７に示すように、隣接する３つのピース内の各右下画素である。復号装置では、縮小画像を復号した後、もし補間データの符号語が“０１”であった場合、縮小画像中の該当する１つの画素をＰn(1,1)と見なし、その画素の左上隣画素Ｐn-b-1(1,1)と同じ色を持つ画素Ｐn(0,0)を生成し、上隣の画素Ｐm-b（1,1）と同じ色を持つ画素Ｐn(1,0)を生成し、そして、左隣の画素Ｐn-1(1,1)と同じ色を持つ画素Ｐn(0,1)を生成すれば良い。
【００３９】
そして、注目ピース内の色数が１色ではなく、上式（２）も成り立たない場合、“００”（２ビット）を出力し、続けて３つの画素Ｐn(0,0),Ｐn(1,0),Ｐn(0,1)の値をそのまま出力する。実施形態の場合、１画素の色成分の数は３つであり、各々が８ビットであるので、“００”に後続して、７２ビット（＝３×８×３）が出力されることになる。なお、この方式は、あくまで本実施の形態において用いる処理の一例であり、その他の方式を使ってもよい。例えば、画素値をそのまま出力する方法や、特開２０１０−１５４４８６に開示された方法でも構わない。
【００４０】
補間データの符号化が終了した後、図３に示したように、符号化情報テーブルに圧縮フラグとして“１”を記す（ステップＳ２１０）。さらに、補間データの符号量と、補間データの符号量と縮小画像の符号量の和とを符号化情報テーブルに記録する（ステップＳ２１０）。その上で、補間データと縮小画像の符号列をレート制御部１０６へ出力する。この出力においては、まず、補間データの符号列をレート制御部１０６内部のメモリへ書き込み、それに後続するように縮小画像の符号列を書き出す。さらに、符号化情報テーブルに、補間データの符号列の先頭アドレスを記録する。補間データの符号量を記録する理由は、格納した先頭アドレスにその符号量を加算するだけで、補間データを読み飛ばし、縮小画像データの符号列の読み出しアドレスが算出できるためである。
【００４１】
ステップＳ２０６もしくはステップＳ２１０の処理が終了した後、ブロックカウンタi_blockをインクリメントし（ステップＳ２１１）、ブロックカウンタの値i_blockとブロック総数Ｎの比較を行う（ステップＳ２１２）。もしi_blockの方が、符号化対象画像内の総ブロック数Ｎより小さければ（ステップＳ２１２でＹｅｓ）、処理をＳ２０２へ戻す。そうでなければ（ステップＳ２１２でＮｏ）、レート制御部１０６はレート制御処理を行う（ステップＳ２１３）。
【００４２】
レート制御部１０６では、先ず、可逆符号化のブロックに関するビットレート(r_lossless)を求める。そして、所定の閾値(Th_r1)との比較を行い、Th_r1よりr_losslessの方が大きい場合には、可逆符号化実施ブロックの符号量が多く、非可逆符号化に十分な符号量が割り当てられないと考えて、補間データの削除を行う。なお、補間データの削除の方法については、いくつか考えられるが、本実施の形態においては、最も簡易な方法を採る。具体的には、画像全体の可逆符号化のブロックの全ての補間データを削除する。
【００４３】
レート制御部１０６の処理フローについては、図４にまとめており、同図を用いて説明する。レート制御処理が開始すると、図３の符号化情報テーブルを基に画像全体の可逆符号化データのビットレート(r_lossless)を算出する（ステップＳ４０１）。なお、r_losslessについては、可逆符号化が実施されたブロック（可逆符号化実施ブロック）の数をnum_lossless_block、可逆符号化実施ブロックの符号量(byte)の和（総符号量）をsum_M_losslessとして、次の通り算出される。
r_lossless = 8 * sum_M_lossless/(Bw*Bh*num_lossless_block)
【００４４】
次いで、可逆符号化実施ブロックを可逆のまま出力するのか、補間データを削除して符号量を削減して出力するかの判断を行う（ステップＳ４０２）。具体的には、現在の可逆符号化データのビットレート(r_lossless)と閾値Th_r1との比較を行う。もし、r_losslessが閾値Th_r1より大きい場合（ステップＳ４０２でＹｅｓ）、可逆符号化実施ブロックに対して補間データの削除を行う（ステップＳ４０３）。その上で、今度は非可逆符号化の目標ビットレート(TR_lossy)を算出する（ステップＳ４０４）。一方で、r_losslessがTh_r1以下の場合（ステップＳ４０２でＮｏ）、非可逆符号化の目標ビットレート(TR_lossy)を算出する（ステップＳ４０４）。
【００４５】
ここで、閾値Th_r1の設定について簡単に述べる。後述するが、非可逆符号化領域の目標符号量は、画像全体の目標符号量から、可逆符号化実施ブロックの最終的な符号列の符号量を減じた値である。このため、Th_r1として大きい値を設定するほど、“可逆”の符号量を多く出力することになり、結果として、非可逆符号化の符号列に割り当て可能な符号量は少なくなる。そして、非可逆符号化が実施されるブロック（非可逆ブロック）の画質は、画像全体を非可逆符号化により目標ビットレートで圧縮した場合と比べて、低くなってしまう。一方で、Th_r1として小さい値を設定するほど、“可逆”としての出力を制限することである。このため、可逆符号化方式を導入することのメリットが失われていく。これらのことを鑑みると、Th_r1については、画像全体の目標ビットレートＴＲに近い値を設定することが望ましい。そこで、Th_r1とＴＲとの間には、相関性を持たせるものとした。すなわち、Th_r1＝α * ＴＲ（ただし、αは１以上の実数）とすることが望ましい。そこで、実施形態では、α＝１、すなわち、Th_r1＝ＴＲを設定するものとする。
【００４６】
ステップＳ４０３においては、補間データの削除を行うための、符号化情報テーブルの更新を行う。具体的には、図５に示したとおり、圧縮フラグが“１”となっている全てを“２”へ変更する。さらに、可逆符号化データサイズを、補間データサイズを減じた値とし、データ先頭ポインタの値を縮小画像列の先頭へ変更する（従前のデータ先頭ポインタを補間データのデータサイズで加算して更新する）。なお、説明のとおり、この処理ステップにおいては、実際に補間データの削除は行なわなくてよい。後述する画像符号化データ形成部１０９では、符号化情報テーブルを参照しながら、補間データを読み飛ばして符号列を生成し、最終的には補間データを削除した符号列を生成できるためである。
【００４７】
ステップＳ４０４においては、非可逆符号化の目標ビットレートTR_lossyを下記の通り行う。
・ステップＳ４０２でＹｅｓの場合：
TR_lossy ＝ 8 * (M_img - sum_M_reduced_img) / (Bw * Bh * num_lossy_block)
・ステップＳ４０２でＮｏの場合：
TR_lossy = 8 * (M_img - sum_M_lossless) / (Bw * Bh * num_lossy_block)
ここで、sum_M_reduced_imgは、各可逆符号化実施ブロックにおける縮小画像の符号列の符号量和であり、num_lossy_blockは非可逆ブロックのブロック数である。また、M_imgは、画像全体の目標符号量であり以下のとおりである。
M_img = TR * W * H / 8
【００４８】
ステップＳ４０４における非可逆符号化の目標ビットレートTR_lossyの算出が終了した後、非可逆符号化データのビットレートがTR_lossyとなるように、レート制御を行う。このレート制御については、各非可逆ブロックのＲ−Ｄ比の情報を基に、非可逆ブロック全体の中から、削除すべきデータを決定しながら行う。実施形態では、非可逆符号化としてＪＰＥＧ２０００を例にしているので、非可逆ブロックのＲ−Ｄ比の情報を基に、最下位のビットプレーンから何層までのビットプレーンまでを削除するかを決定していく。ただし、詳細については、本発明の主たる目的から外れるので、ここでは割愛する。このレート制御処理が完了した後、符号化情報テーブルを画像符号化データ形成部１０９へ出力し（ステップＳ４０６）、処理を終える。
【００４９】
ステップＳ２１３のレート制御処理が終了すると、画像符号化データ形成部１０９において画像全体の符号化データ（画像符号化データ）の形成を行う（ステップＳ２１４）。このステップでは、まず、画像符号化データの先頭に配置するヘッダの情報を生成する。ヘッダには、画像の縦横サイズ，ブロックのサイズ，各ブロックの圧縮フラグと符号長等、復号する上で必要となる情報をまとめる。次いで、ヘッダに続けて、ブロック番号順で各ブロックの符号列を並べる。その際には、符号化情報テーブルの情報を基に処理を行う。これらの処理により、画像符号化データの形成が終了すると、画像符号化処理は完了する。
【００５０】
以上説明したように本第１の実施形態では、ブロックを単位とする可逆符号化データ、非可逆符号化データが混在しつつも、目標符号レートの符号化データを容易に生成することが可能になる。しかも、文字や線画が含まれる領域については、或る程度の画質が維持することも可能になる。また、特に、第１の実施形態のように、１つのブロックについて可逆符号化から非可逆符号化に切り替えるべきか否かの判断（Ｓ２０８）は、オリジナルのブロックよりも小さい縮小画像についての可逆符号化結果の符号量から判断する。従って、仮に、着目ブロックを可逆符号化から非可逆符号化に切り替えるにしても、その間のロスは縮小画像の可逆符号化に係る時間で済み、全体に与える時間を小さなものとすることができる。
【００５１】
なお、上記実施形態では、可逆符号化部１０７は、３２×３２画素のブロックから、水平、垂直とも１／２の１６×１６画素の縮小画像ブロックと補間データを生成し、それぞれ可逆符号化するものとした。すなわち、階層構造として２層の例である。しかし、生成された１６×１６画素の縮小画像を再帰的に入力するようにすれば、そこから８×８画素の縮小画像が生成でき、補間データが何段も生成できる。従って、上記実施形態で本願発明が限定されるものではない。すなわち、可逆符号化部１０７は、要するに基礎となる画質の画像から段階的に高精細な画質の画像を復号するための階層データ構造を持つ符号化データを生成し、全ての符号化データを復号した場合にオリジナルのブロックの画像にまで可逆的に復元可能な階層データ構造を持つ可逆符号化データを生成するものであれば良い。この場合、どの縮小画像とどの補間データまでが、許容画質とするかは適宜決定すれば良いであろう。
【００５２】
［第２の実施形態］
第１の実施形態においては、ブロックサイズを３２×３２画素として判定，符号化を行う方法を示した。しかし、非可逆符号化方式によっては、このサイズでは符号化の性能を十分に出せない場合もある。例えば、そのような非可逆符号化方式として、第１の実施形態で用いたＪＰＥＧ２０００があり、理由について簡単に説明する。ＪＰＥＧ２０００ではエントロピー符号化で算術符号化を用いる。算術符号化では、符号化対象のシンボルの出現確率について想定値を設け、想定値を基に符号化を行う。そして、符号化を進めながら想定値を実際の出現確率に近づけていく。つまり、算術符号化は処理を進めながら、性能を向上させていく。このため、ブロックのサイズが小さいと、想定値を実際の値に近づけることはできず、十分な性能を得られない結果となる。
【００５３】
そこで本第２の実施の形態においては、判定処理と非可逆符号化方式で、処理対象とする矩形領域のサイズを変える方法を示す。具体的には、判定処理で用いる矩形領域のサイズを３２×３２画素（第１のブロックに対応）とし、非可逆符号化処理で用いる矩形領域のサイズをそれより十分に大きく、且つ、水平、垂直とも整数倍の、例えば１２８×１２８画素（第２のブロックに対応）とする。このように本第２の実施形態では、異なるサイズのブロックを利用することになるので、以降、前者の矩形領域（３２×３２画素）のブロックをサブブロック、後者の矩形領域（１２８×１２８画素）を単にブロックと呼ぶものとする。
【００５４】
また、第１の実施形態におけるレート制御では、非可逆符号化の符号量を十分に確保できないと判断した場合、全ての可逆符号化が適用されたブロックの補間データを削除し、非可逆符号化データに多くの符号量を確保した。この方法を採った理由は、補間データの削除に関する処理の軽減である。しかし、この方法では必要以上に補間データを削除してしまう、という問題がある。例えば、図７に示した通り、２つのブロック（２×１２８×１２８画素）から構成される画像があったとする。同図において、ブロック０，１それぞれに存在する可逆符号化のサブブロック（可逆サブブロック）のみの符号量を示していて、ブロックをまたいで、サブブロック番号を割り振っている。そして、番号１〜３，５〜７，１０のサブブロックについては、補間データサイズは10byteで、サブブロックに対して求められる目標符号量より10byte少ない。番号４のサブブロックについては、補間データサイズが60byteで40byte超過している。また、番号８のサブブロックについては補間データサイズが70byteで50byte超過し、番号９については、補間データサイズが80byteで60byte超過している。この画像に対して、第１の実施形態と同様な補間データの削除を行うと、１サブブロックあたり20byte目標符号量を下回る。結局、合計200byteのデータを削除することとなり、削除し過ぎてしまい、不必要に画質が劣化する可能性がある。この点を踏まえ、本第２の実施の形態においては、処理負荷は多少かかるが、補間データを必要以上に削除しない方法を示す。
【００５５】
図８は本第２の実施形態に係る画像処理装置の機能構成を示すブロック図である。図８に示すように、本第２の実施形態に係る画像処理装置は、ブロック分割部１０２、ブロックバッファ１０３、ブロック符号化部８０１、レート制御部８０２、画像符号化データ形成部８０３を備える。なお、図８に示す構成はハードウェアにより実現しても良いが、本第２の実施形態では、各部の機能をコンピュータに実現させるプログラムにより実現するものとする。このプログラムは上記外部記憶装置１４０７や記憶媒体ドライブ１４０８、もしくはＩ／Ｆ１４０９を介して外部装置からＲＡＭ１４０２にロードされるものとする。
【００５６】
続いて、図８の画像処理装置の処理について、図１０のフローチャートを用いて説明をする。
【００５７】
ＣＰＵ１４０１は、画像の符号化処理を開始すると、初期化処理を行う（ステップＳ１００１）。初期化処理の後、ブロック分割部１０２は、ブロックバッファ１０３へブロックデータの入力を行う（ステップＳ２０２）。ここまでの処理については、第１の実施形態と同様であるので、詳細説明を割愛する。なお、本第２の実施形態の冒頭でも説明したが、ブロックのサイズについては、１２８×１２８画素である。次いで、ブロックデータをブロック符号化部８０１へ入力し、ブロック符号化部８０１はブロック符号化処理を行う（ステップＳ１００３）。
【００５８】
このステップＳ１００３については、図９のブロック符号化のブロック図と、図１１のフローチャートを用いて説明する。ブロック符号化部８０１にブロックデータが入力されると、サブブロック分割部９０１において、３２×３２画素サイズのサブブロックに分割する（ステップＳ１１０１）。またこのタイミングで、サブブロックのカウンタi_subblock=0と初期化する。なお、以下の説明において、ブロック内のサブブロックの個数をＭとする。本第２の実施の形態においては、ブロックサイズ，サブブロックサイズから、Ｍ＝１６となる。次いで、サブブロックを属性判定部１０４に入力し（ステップＳ１１０２）、属性判定を行う（ステップＳ１１０３）。属性判定部１０４の処理については、第１の実施形態と同様であるので、説明を割愛する。属性判定の結果、写真であると判定した場合（ステップＳ１１０４でＹｅｓ）、サブブロックのイメージを非可逆符号化対象イメージ生成部９０２へ出力する（ステップＳ１１０５）。そして、図１２（ａ）に示したサブブロック符号化情報テーブルに圧縮フラグとして“０”を設定する（ステップＳ１１０６）。その後、サブブロックカウンタi_subblockをインクリメントし（ステップＳ１１０７）、サブブロック数のＭと比較する（ステップＳ１１０８）。もし、i_subblockがＭより小さければ（ステップＳ１１０８でＹｅｓ）、処理をステップＳ１１０２へ戻す。一方で、i_subblockがＭであれば（ステップＳ１１０８でＮｏ）、処理をステップＳ１１０９へ進める。
【００５９】
ステップＳ１１０４において、属性は写真でないと判断した場合（ステップＳ１１０４でＮｏ）、可逆符号化部１０７においてサブブロックの縮小ブロックに対して可逆符号化を行う（ステップＳ１１１０）。この処理については、第１の実施形態と同様である。次いで、注目サブブロックにおける縮小ブロックの符号列のビットレート(r_i_reduced)を求めて、ＴＲと比較を行う（ステップＳ１１１１）。もし、r_i_reducedの方が大きい場合（ステップＳ１１１１でＹｅｓ）、非可逆符号化の対象とするため、サブブロックのイメージを非可逆符号化対象イメージ生成部９０２へ出力する（ステップＳ１１０５）。一方で、縮小ブロックのビットレートr_i_reducedがＴＲ以下であるい場合（ステップＳ１１１１でＮｏ）、補間データの符号化を行う（ステップＳ１１１２）。その後、サブブロックのイメージを非可逆符号化対象イメージ生成部９０２へ出力し（ステップＳ１１１３）、サブブロック符号化情報テーブルに圧縮フラグとして“１”を設定する（ステップＳ１１１４）。ここで、ステップＳ１１１３でサブブロックのイメージを出力する理由について簡単に述べる。非可逆符号化は１２８×１２８画素サイズのブロックで行うため、可逆符号化が実施されたサブブロック（可逆符号化実施サブブロック）の領域に対して、何かしらの画素値を与えることが必要となる。本実施の形態においては、非可逆符号化が実施されるサブブロック（非可逆サブブロック）との画素値の連続性を考慮して与える。具体的には、可逆符号化実施サブブロックには、非可逆サブブロックとの画素値の連続性を持つ場合もあることに注目し、ブロック内の全可逆符号化実施サブブロックの画素値平均を用いる。このため、可逆符号化実施サブブロックのイメージを出力する。ステップＳ１１１４が終了すると、サブブロックのカウンタをインクリメントして（ステップＳ１１０７）、処理をステップＳ１１０８へ進める。ステップＳ１１０８の処理については、すでに説明しているため割愛する。
【００６０】
ステップＳ１１０９においては、サブブロック符号化情報テーブルを基に、着目ブロック内に非可逆サブブブロックが存在しているかどうかを判断する。もし存在しなければ（ステップＳ１１０９でＮｏ）、サブブロック符号化情報テーブルをレート制御部８０２へ出力する（ステップＳ１１１７）。一方で、存在する場合（ステップＳ１１０９でＹｅｓ）、非可逆符号化対象イメージ生成部９０２において、非可逆符号化の対象となる１２８×１２８ピクセルのイメージ（非可逆符号化対象イメージ）を生成する（ステップＳ１１１５）。このステップにおいては、非可逆符号化を行えるようにするために、可逆サブブロックの存在位置に対応する領域に対して、何らかの画素値を与える処理（穴埋め）が必要となる。この穴埋めについては、該当領域の符号がなるべく発生しないようにする必要がある。この点を念頭におき、本実施の形態では、注目ブロック内の非可逆符号化対象のサブブロックはそのままにし、それ以外の可逆符号化実施サブブロック内の全画素を、可逆符号化実施サブブロックの画素値の平均値（平均画素値）で穴埋め（ペイント）するものとする。具体的な処理については、次に述べる。
【００６１】
ステップＳ１１１５が開始すると、１２８×１２８画素のメモリ領域を確保する。次いで、非可逆サブブロックについて、ブロック内と同じ位置に、非可逆符号化対象イメージ内へ画素値をコピーする。その後、ブロック内の全可逆符号化実施サブブロックの平均画素値を求める。そして、ブロック内の可逆符号化実施サブブロックと同じ領域に対して、平均画素値をコピーする。この結果、１２８×１２８画素のブロック内の、可逆符号化するとして決定した３２×３２画素を単位とするサブブロック内の全画素が同じ値を持つことになり、高周波成分が少ない状態を作り出すことができる。このようにして、非可逆符号化対象イメージを生成した後、非可逆符号化部１０５では、非可逆符号化を実施する（ステップＳ１１１６）。非可逆符号化については第１の実施形態と同様であり、説明を割愛する。なお、非可逆符号化が終了すると、図１２（ｂ）のように示したように、非可逆符号化情報を生成し、レート制御部８０２へ出力する（ステップＳ１１１７）。ステップＳ１１１７の処理が終了すると、Ｓ１００３の処理を終える。
【００６２】
さて、図１０における注目ブロックの符号化（ステップＳ１００３）が終了すると、ブロックカウンタをインクリメントして（ステップＳ１００４）、ブロック数Ｎとの比較を行う（ステップＳ１００５）。もし、i_blockの方が小さければ（ステップＳ１００５でＹｅｓ）、処理をＳ１００２へ戻す。一方で、i_blockとＮが等しければ（ステップＳ１００５でＮｏ）、レート制御部８０２においてレート制御処理を行う（ステップＳ１００６）。
【００６３】
レート制御部８０２における処理の流れを図１３のフローチャートに示す。同図の処理は、第１の実施形態のレート制御の処理フロー（図４）とおおまかな流れは同じであり、相違点を中心に説明する。レート制御処理が開始すると、まず画像全体の可逆符号化実施サブブロックのビットレートr_losslessを算出する（ステップＳ４０１）。この後、画像全体の目標ビットレートTh_r1との比較を行う（ステップＳ４０２）。もし、r_losslessの方が大きければ（ステップＳ４０２でＮｏ）、非可逆符号化の目標ビットレートの算出を行う（ステップＳ４０４）。一方、r_losslessの方が小さければ（ステップＳ４０２でＹｅｓ）、補間データ削除のための符号化情報テーブルの更新を行う（ステップＳ１３０１）。ステップＳ１３０１の処理については、図１５のフローチャートにまとめてあるので、そちらを用いて説明することとし、以下では、本第２の実施の形態における補間データの削除方法に関する概略をまとめる。
【００６４】
本第２の実施の形態の冒頭でも説明したが、第１の実施の形態においては、必要以上に補間データを削除していた。これに対する改善として、目標圧縮率をサブブロックに適用したときの符号量（サブブロック平均符号量）を上回っているサブブロックのみについて、補間データを削除する方法がある。例えば、図７の符号量分布であれば、番号４，８，９のサブブロックの補間データを削除すればよい。
【００６５】
また別には、サブブロック平均符号量を超過しているサブブロックの符号量と、下回っているサブブロックの符号量を相殺させる。そして、超過している場合、超過している分だけ、補間データを削除する方法がある。例えば、図７の場合であれば、超過符号量は150byteで、下回っている符号量は70byteであり、80byte削除すれば十分である。そこで、サブブロック９の補間データの削除が必要であると判断し、削除を行う。
【００６６】
さらには、ブロック平均符号量を超過しているブロックを選択して、サブブロック平均符号量を上回っているサブブロックの補間データを削除する方法がある。図７であれば、ブロック０については、目標符号量を超過しているサブブロックの超過符号量は40byteである。また、目標符号量を下回っているサブブロックにおいて下回っている符号量（余符号量）は50byteである。このため、補間データの削除を行わない。一方でブロック１については、超過しているサブブロックの超過符号量は110byteで、下回っているサブブロックの余符号量は20byteである。このため、補間データの削除が必要となり、サブブロック８，９の補間データを削除する。
【００６７】
これら、いずれの方法でも、可逆符号化が実施された領域の符号量を、当該領域に対して目標圧縮率を適用して得られる符号量より小さくできる。このため、非可逆符号化に必要となる符号量を確保することはできる。以下では、３番目に述べた方法について、図１５のフローチャートに従い説明する。
【００６８】
符号化情報テーブルの更新処理が開始すると、ブロックカウンタi_blockを０にセットする（ステップＳ１５０１）。次いで、i_block番目のブロックのビットレートr_lossless_i_blockを算出して、Th_r1と比較する（ステップＳ１５０２）。もし、r_lossless_i_blockの方が大きければ、当該ブロックについては、画像全体の可逆符号化の符号量が閾値(Th_r1)を超過している原因であると考える。その上で、Th_r1を超える可逆符号化実施サブブロックの補間データを出力しないように、第１の実施形態と同様な方法で、サブブロック符号化情報テーブルを更新する（ステップＳ１５０３）。例えば、もし注目ブロックにおいてＭ−１番目のサブブロックの補間データを出力しない場合、図１６のようになる。すなわち、Ｍ−１番目のサブブロックの圧縮フラグを“２”にし、その上で補間データサイズを削除するために、可逆符号kデータサイズを更新する（図示の場合「２５」だけ減じる）。そして、補間データを削除するために、データのポインタを縮小画像ブロックのアドレスに更新する。ステップ１５０３の処理が終了すると、ブロックカウンタをインクリメントし（ステップＳ１５０４）。一方で、ステップＳ１５０２でr_lossless_i_blockがTh_r1より小さい場合、当該ブロックについては、画像全体の可逆符号化の符号量が閾値(Th_r1)を超過する原因ではない、と考える。そして、処理をステップＳ１５０４へ進める。ステップＳ１５０４が終わると、ステップＳ１５０５へ進み、ブロックカウンタとブロック数を比較する（ステップＳ１５０５）。もし、ブロックカウンタの値がブロック数より小さい場合（ステップＳ１５０５でＹｅｓ）、処理をステップＳ１５０２へ戻す。一方で、ブロックカウンタの値がブロック数と同じである場合（ステップＳ１５０５でＮｏ）、ステップＳ１３０１の処理を終える。
【００６９】
上記のようにしてステップＳ１３０１が終了すると、非可逆符号化の目標ビットレートを算出し（ステップＳ４０４）、画像全体の非可逆ブロックに対してレート制御を行う（ステップＳ４０５）。ここまでの処理が終了すると、符号化した結果の情報を画像符号化データ形成部８０３へ出力する（ステップＳ１３０２）。
【００７０】
図１０におけるステップＳ１００６のレート制御処理が終了すると、画像符号化データ形成部８０３において符号列の形成を行う（ステップＳ１００７）。このステップでは、図１８に示したとおり、画像符号化データの先頭に配置するヘッダの情報を生成する。ヘッダには、画像の縦横サイズ，ブロックのサイズ，各ブロックの符号長、各サブブロックの圧縮フラグ，符号長等がまとめられる。他には、非可逆符号化を復号する上で必要となる情報もまとめられる。次いで、各ブロックの符号列がラスタスキャン順に並べられる。そして、各ブロックの符号列としては、最初に可逆符号化実施サブブロックの符号列が並べられ、それに続いて、非可逆符号化対象イメージの符号列が並べられる。ここで、可逆符号化実施サブブロックの符号列と、非可逆符号化対象イメージの符号列の２つを並べることを述べたが、どちらか一方しかない場合は、該当符号列のみが並べられることになる。例えば、注目ブロックにおいて、可逆符号化実施サブブロックが存在しない場合、非可逆符号化対象イメージの符号列のみが並べられる。また、可逆符号化実施サブブロックの符号列については、ラスタスキャン順に非可逆符号化が実施されたサブブロックの符号列が並ぶ。ここで、並べられる符号列は、可逆符号化が実施されたサブブロックの符号列のみである。例えば、番号０、３のサブブロックのみに対して可逆符号化が実施されたのであれば、これらのサブブロックの符号列のみが並べられる。さらに、各サブブロックの符号列においては、補間データの符号列、縮小画像の符号列が順に並ぶ。なお、補間データが削除されたサブブロックについては、縮小画像の符号列のみが並べられる。例えば、番号０、３のサブブロックに対して可逆符号化が実施され、番号０については補間データの削除が行われたとする。その場合には、番号０については縮小画像の符号列のみが並べられ、番号３については、補間データと縮小画像の符号列が並べられることになる。
【００７１】
これらの処理により、画像符号化データの形成が終了すると、画像符号化処理は完了する。
【００７２】
［その他の実施形態］
補間データの削除方法として、第１，２の実施形態において、いくつか示したが、本発明の範疇に入る手法はそれらだけではない。その他として、第２の実施形態では選択的に補間データを削除する方法を説明したが、補間データに対して予め、優先順位をつけておく。その上で、優先順位に従って、削除すべきデータを決定する方法でもよい。なお、優先順位のつけ方としては、各補間データの符号量と、補間データを復号することにより得られる画質向上の比率などが考えられる。
【００７３】
実施形態においては、可逆符号化方式の階層数として２段階の方法を示したが、これに限らない。例えば、縮小画像に対して、さらに補間データ（補間データ１）と縮小画像を生成して、補間データ１、補間データ２、縮小画像の３段階構成にしてもよい。その際、削除が許されない最低限の画質を保証するデータとして、縮小画像のみを設定してもよい。また、途中の解像度を生成するために必要な、縮小画像と補間データ２を削除不可と設定してもよい。また、階層数を３段階以上にした場合、基本階層は複数階層から構成される場合もあれば、１階層から構成されることもある。他方、付加的階層についても、複数階層から構成される場合もあれば、１階層から構成されることもある。
【００７４】
文字，線画等の領域における符号列における階層のデータは、補間データと縮小画像の組に限られることはない。あくまで、基本階層と付加的階層の関係を持つことが可能な階層構造であればよい。一例として、注目ブロック内の全画素の上位ビット群（例えば上位３ビット）を基本階層として、下位ビット群（例えば下位５ビット）を付加的階層とする。さらにその上で、上位ビット群には予測符号化等の符号化方式を適用する方法がある。
【００７５】
文字，線画等の領域における縮小画像の可逆符号化方式として、ＪＰＥＧ−ＬＳを使うものとして説明したが、これに限られることはない。例えば、ＪＰＥＧ Ｓｐａｔｉａｌ方式、ラン・レングス符号化方式、ＰＮＧなどの、予測符号化方式でも構わない。さらには、実施形態として、文字，線画等の領域における高効率な符号化性能を得るために、予測符号化方式を用いる方式を示した。しかし、本発明は予測符号化方式に限られることはなく、ＬＺ７７，ＺＩＰ等の辞書型符号化方式を用いてもよい。
【００７６】
写真領域の符号化処理として、ＪＰＥＧ２０００を用いる方法を示したが、これに限られることはなく、レート制御を行える符号化方式であれば、本発明の範疇となる。
【００７７】
実施形態においては、写真領域の符号列をレート制御するために、写真領域の符号化方式として、無数の階層数を持つことができるＪＰＥＧ２０００を用いた。しかし、目標符号量未満の画像符号化データを出力する画像処理装置を想定するのであれば、階層数は無数でなくてもよい。例えば、写真領域中のブロックに対して、離散ウェーブレット変換やＤＣＴ等の周波数変換を行い、全係数をビットプレーン分割して、各ビットプレーンを階層とみなす。つまり、この方法であれば階層数はビットプレーンの枚数となる。その上で、各階層を単位としてエントロピー符号化する。そして、符号列がこのような階層を取る場合に、写真領域としての目標符号量以下の符号列を生成するためには、ＬＳＢのビットプレーンを削除し、残っている符号量を算出する。もし、当該符号量が目標符号量以下でなければ、１つ上位にあるビットプレーンを削除して、残っている符号量を算出し、目標符号量との比較を行う。この処理を繰り返すことで、目標符号量以下の写真領域の符号列を生成する。なお、文字，線画等の領域に適用する符号化方式は多くの階層数を持たせることは難しく、写真領域の符号量調整で、画像全体の目標符号量以下にさせる必要がある。したがって、非可逆符号化方式の階層数をＮ１段階、可逆符号化方式の階層数をＮ２段階とした場合、Ｎ１＞Ｎ２という関係が成り立つ。
【００７８】
実施形態においては、属性判定部を設けて、注目するブロックもしくはサブブロック（符号化処理対象矩形）の属性判定を行い、符号化方式を選択する方法を示したが、属性判定を設けない方法でもよい。その場合には、いったん全ての符号化処理対象矩形を可逆符号化部に入力し、可逆符号化を実施する。そして、ブロック平均符号量もしくはサブブロック平均符号量を超える符号化処理対象矩形については、全て非可逆符号化を実施する。こうすることで、写真領域の符号化対象矩形は非可逆符号化が適用される。なぜなら、写真領域については、可逆符号化を実施した際の圧縮率は１／２(=１２bpp)程度であり、実用的なビットレート（例えば2bpp以下）では、ブロック，サブブロック平均符号量を超えてしまうからである。
【００７９】
また、実施形態ではブロックのサイズとして３２×３２画素や１２８×１２８画素を例にしたが、可逆、非可逆符号化の双方が支障なく符号化できる程度の複数画素を内包するブロックであれば良いので、上記実施形態に限定されるものではない。
【００８０】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
画像を符号化して符号化データを生成し、目標とするビットレートに従い、生成された符号化データ中の一部を削除し出力するレート制御手段を有する画像符号化装置であって、
複数画素で構成されるブロックを非可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ１段階の階層データ構造を持つ符号化データを生成する第１の符号化手段と、
前記ブロックを予測演算を用いて可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ２（Ｎ１＞Ｎ２）段階の階層データ構造を持つ符号化データを生成する第２の符号化手段と、
符号化対象画像から前記ブロックを単位に入力する入力手段と、
入力した着目ブロックを解析することで、当該着目ブロックを前記第１の符号化手段、前記第２の符号化手段のいずれで符号化すべきかを判定する判定手段と、
該判定手段により、前記着目ブロックを前記第２の符号化手段で符号化すべきとして判定された場合、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを前記第２の符号化手段により生成させ、生成された符号量が予め設定された目標符号量を超えるか否かを判定し、超えると判定した場合には前記着目ブロックを前記第１の符号化手段で符号化すべきブロックとして変更し、超えないと判定された場合には、残りの階層の符号化データを前記第２の符号化手段により生成させる第１の制御手段と、
前記判定手段、或いは、前記第１の制御手段によって前記第１の符号化手段で符号化すべきと判定されたブロックに対して前記第１の符号化手段により符号化させ、符号化データを生成させる第２の制御手段と
を有することを特徴とする画像符号化装置。
【請求項２】
前記判定手段は、前記着目ブロックが文字、線画のブロックであるか否かを判定する手段であり、前記着目ブロックが文字、線画のブロックである場合に当該着目ブロックを前記第２の符号化手段で符号化すべきと判定し、前記着目ブロックが文字、線画のブロックではない場合に当該着目ブロックを第１の符号化手段で符号化すべきと判定することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記第１の符号化手段は周波数変換を用いた非可逆符号化手段であって、前記第２の符号化手段は予測演算を用いた可逆符号化手段であることを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
前記判定手段は、
前記着目ブロックを、２×２画素で構成される複数のピースに分割し、
各ピースに内包される画素の色数を判別し、
色数が１又は２のピース数が、過半数を占めれば前記着目ブロックは文字、線画のブロックと判定し、過半数を占めなければ前記着目ブロックは文字、線画のブロックではないと判定する
ことを特徴とする請求項２に記載の画像符号化装置。
【請求項５】
前記レート制御手段は、
前記第１の制御手段の制御の下で前記第２の符号化手段により符号化すべきとして判定された全ブロックの符号化データ中の、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データの総符号量に対する１画素当たりのビットレートをr_lossless、
予め設定された閾値をTh_r1、
予め設定された１画素当たりの目標ビットレートをTR、
非可逆符号化データの目標ビットレートをTR_lossyと定義したときに、
（１） r_lossless＞Th_r1の関係を満たす場合：
前記第１の制御手段で生成された符号化データ中、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データのみを残し、
前記第１の制御手段で生成された符号化データ中の残った符号化データの総符号量をsum_M_reduced_imgとしたとき、
TR_lossy＝（符号化対象の画像の全画素 * TR - sum_M_reduced_img）／（非可逆符号化対象となった全ブロックの画素数）
として前記非可逆符号化データのビットレートTR_lossyを算出して、非可逆符号化データのビットレートの制御を行い、
（２） r_lossless≦Th_r1の関係を満たす場合：
前記第１の制御手段で生成された符号化データの総符号量をsum_M_losslessとしたとき、
TR_lossy＝（符号化対象の画像の全画素 * TR - sum_M_lossless）／（非可逆符号化対象となった全ブロックの画素数）
として前記非可逆符号化データのビットレートTR_lossyを算出して、非可逆符号化データのビットレートの制御を行う
ことを特徴とする請求項１乃至４のいずれか１項に記載の画像符号化装置。
【請求項６】
前記ブロックを第１のブロック、前記第１のブロックの水平、垂直とも整数倍のサイズを持つ矩形領域を第２のブロックとしたとき、前記第１の符号化手段は、前記第２のブロックの画像を単位に符号化し、
更に、前記判定手段が、着目している第１のブロックを前記第１の符号化手段で符号化すべきとした場合、或いは、前記第１の制御手段にて前記着目している第１のブロックを前記第１の符号化手段で符号化すべきと判定された場合、当該着目している第１のブロックの画像を前記第２のブロックの中に配置し、
前記第２のブロックに中において、前記第１の制御手段でによって全ての階層を前記第２の符号化手段で符号化すべきと判定されたブロック内の画素値を、前記第２の符号化手段で符号化すべきと判定された画素値の平均値で置き換えることで、前記第２のブロックの画像を生成する生成手段とを備え、
前記第１の符号化手段は、前記生成手段で生成された第２のブロックの画像を符号化し、
前記レート制御手段は、前記第２の符号化手段で符号化して得られた各第１のブロックの符号化データのうち、前記目標ビットレートを超えると判定された第１のブロックの符号化データの一部を削除することでビットレートを制御する
ことを特徴とする請求項１乃至５のいずれか１項に記載の画像符号化装置。
【請求項７】
コンピュータに読み込ませ実行させることで、前記コンピュータを、請求項１乃至６のいずれか１項に記載の画像符号化装置が有する各手段として機能させるためのコンピュータプログラム。
【請求項８】
請求項７に記載のコンピュータプログラムを格納したコンピュータ可読記憶媒体。
【請求項９】
画像を符号化して符号化データを生成し、目標とするビットレートに従い、生成された符号化データ中の一部を削除し出力するレート制御手段を有する画像符号化装置の制御方法であって、
第１の符号化手段が、複数画素で構成されるブロックを非可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ１段階の階層データ構造を持つ符号化データを生成する第１の符号化工程と、
第２の符号化手段が、前記ブロックを予測演算を用いて可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ２（Ｎ１＞Ｎ２）段階の階層データ構造を持つ符号化データを生成する第２の符号化工程と、
入力手段が、符号化対象画像から前記ブロックを単位に入力する入力工程と、
判定手段が、入力した着目ブロックを解析することで、当該着目ブロックを前記第１の符号化工程、前記第２の符号化工程のいずれで符号化すべきかを判定する判定工程と、
第１の制御手段が、
前記判定工程により、前記着目ブロックを前記第２の符号化工程で符号化すべきとして判定された場合、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを前記第２の符号化工程により生成させ、生成された符号量が予め設定された目標符号量を超えるか否かを判定し、超えると判定した場合には前記着目ブロックを前記第１の符号化工程で符号化すべきブロックとして変更し、超えないと判定された場合には、残りの階層の符号化データを前記第２の符号化工程により生成させる第１の制御工程と、
第２の制御手段が、
前記判定工程、或いは、前記第１の制御工程によって前記第１の符号化工程で符号化すべきと判定されたブロックに対して前記第１の符号化工程により符号化させ、符号化データを生成させる第２の制御工程と
を有することを特徴とする画像符号化装置の制御方法。
【請求項１】
画像を符号化して符号化データを生成し、目標とするビットレートに従い、生成された符号化データ中の一部を削除し出力するレート制御手段を有する画像符号化装置であって、
複数画素で構成されるブロックを非可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ１段階の階層データ構造を持つ符号化データを生成する第１の符号化手段と、
前記ブロックを予測演算を用いて可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ２（Ｎ１＞Ｎ２）段階の階層データ構造を持つ符号化データを生成する第２の符号化手段と、
符号化対象画像から前記ブロックを単位に入力する入力手段と、
入力した着目ブロックを解析することで、当該着目ブロックを前記第１の符号化手段、前記第２の符号化手段のいずれで符号化すべきかを判定する判定手段と、
該判定手段により、前記着目ブロックを前記第２の符号化手段で符号化すべきとして判定された場合、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを前記第２の符号化手段により生成させ、生成された符号量が予め設定された目標符号量を超えるか否かを判定し、超えると判定した場合には前記着目ブロックを前記第１の符号化手段で符号化すべきブロックとして変更し、超えないと判定された場合には、残りの階層の符号化データを前記第２の符号化手段により生成させる第１の制御手段と、
前記判定手段、或いは、前記第１の制御手段によって前記第１の符号化手段で符号化すべきと判定されたブロックに対して前記第１の符号化手段により符号化させ、符号化データを生成させる第２の制御手段と
を有することを特徴とする画像符号化装置。
【請求項２】
前記判定手段は、前記着目ブロックが文字、線画のブロックであるか否かを判定する手段であり、前記着目ブロックが文字、線画のブロックである場合に当該着目ブロックを前記第２の符号化手段で符号化すべきと判定し、前記着目ブロックが文字、線画のブロックではない場合に当該着目ブロックを第１の符号化手段で符号化すべきと判定することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記第１の符号化手段は周波数変換を用いた非可逆符号化手段であって、前記第２の符号化手段は予測演算を用いた可逆符号化手段であることを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
前記判定手段は、
前記着目ブロックを、２×２画素で構成される複数のピースに分割し、
各ピースに内包される画素の色数を判別し、
色数が１又は２のピース数が、過半数を占めれば前記着目ブロックは文字、線画のブロックと判定し、過半数を占めなければ前記着目ブロックは文字、線画のブロックではないと判定する
ことを特徴とする請求項２に記載の画像符号化装置。
【請求項５】
前記レート制御手段は、
前記第１の制御手段の制御の下で前記第２の符号化手段により符号化すべきとして判定された全ブロックの符号化データ中の、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データの総符号量に対する１画素当たりのビットレートをr_lossless、
予め設定された閾値をTh_r1、
予め設定された１画素当たりの目標ビットレートをTR、
非可逆符号化データの目標ビットレートをTR_lossyと定義したときに、
（１） r_lossless＞Th_r1の関係を満たす場合：
前記第１の制御手段で生成された符号化データ中、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データのみを残し、
前記第１の制御手段で生成された符号化データ中の残った符号化データの総符号量をsum_M_reduced_imgとしたとき、
TR_lossy＝（符号化対象の画像の全画素 * TR - sum_M_reduced_img）／（非可逆符号化対象となった全ブロックの画素数）
として前記非可逆符号化データのビットレートTR_lossyを算出して、非可逆符号化データのビットレートの制御を行い、
（２） r_lossless≦Th_r1の関係を満たす場合：
前記第１の制御手段で生成された符号化データの総符号量をsum_M_losslessとしたとき、
TR_lossy＝（符号化対象の画像の全画素 * TR - sum_M_lossless）／（非可逆符号化対象となった全ブロックの画素数）
として前記非可逆符号化データのビットレートTR_lossyを算出して、非可逆符号化データのビットレートの制御を行う
ことを特徴とする請求項１乃至４のいずれか１項に記載の画像符号化装置。
【請求項６】
前記ブロックを第１のブロック、前記第１のブロックの水平、垂直とも整数倍のサイズを持つ矩形領域を第２のブロックとしたとき、前記第１の符号化手段は、前記第２のブロックの画像を単位に符号化し、
更に、前記判定手段が、着目している第１のブロックを前記第１の符号化手段で符号化すべきとした場合、或いは、前記第１の制御手段にて前記着目している第１のブロックを前記第１の符号化手段で符号化すべきと判定された場合、当該着目している第１のブロックの画像を前記第２のブロックの中に配置し、
前記第２のブロックに中において、前記第１の制御手段でによって全ての階層を前記第２の符号化手段で符号化すべきと判定されたブロック内の画素値を、前記第２の符号化手段で符号化すべきと判定された画素値の平均値で置き換えることで、前記第２のブロックの画像を生成する生成手段とを備え、
前記第１の符号化手段は、前記生成手段で生成された第２のブロックの画像を符号化し、
前記レート制御手段は、前記第２の符号化手段で符号化して得られた各第１のブロックの符号化データのうち、前記目標ビットレートを超えると判定された第１のブロックの符号化データの一部を削除することでビットレートを制御する
ことを特徴とする請求項１乃至５のいずれか１項に記載の画像符号化装置。
【請求項７】
コンピュータに読み込ませ実行させることで、前記コンピュータを、請求項１乃至６のいずれか１項に記載の画像符号化装置が有する各手段として機能させるためのコンピュータプログラム。
【請求項８】
請求項７に記載のコンピュータプログラムを格納したコンピュータ可読記憶媒体。
【請求項９】
画像を符号化して符号化データを生成し、目標とするビットレートに従い、生成された符号化データ中の一部を削除し出力するレート制御手段を有する画像符号化装置の制御方法であって、
第１の符号化手段が、複数画素で構成されるブロックを非可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ１段階の階層データ構造を持つ符号化データを生成する第１の符号化工程と、
第２の符号化手段が、前記ブロックを予測演算を用いて可逆符号化し、基礎となる画質の画像から段階的に高精細な画質の画像を復号するためのＮ２（Ｎ１＞Ｎ２）段階の階層データ構造を持つ符号化データを生成する第２の符号化工程と、
入力手段が、符号化対象画像から前記ブロックを単位に入力する入力工程と、
判定手段が、入力した着目ブロックを解析することで、当該着目ブロックを前記第１の符号化工程、前記第２の符号化工程のいずれで符号化すべきかを判定する判定工程と、
第１の制御手段が、
前記判定工程により、前記着目ブロックを前記第２の符号化工程で符号化すべきとして判定された場合、前記基礎となる画質の階層から予め設定された許容画質の階層までの符号化データを前記第２の符号化工程により生成させ、生成された符号量が予め設定された目標符号量を超えるか否かを判定し、超えると判定した場合には前記着目ブロックを前記第１の符号化工程で符号化すべきブロックとして変更し、超えないと判定された場合には、残りの階層の符号化データを前記第２の符号化工程により生成させる第１の制御工程と、
第２の制御手段が、
前記判定工程、或いは、前記第１の制御工程によって前記第１の符号化工程で符号化すべきと判定されたブロックに対して前記第１の符号化工程により符号化させ、符号化データを生成させる第２の制御工程と
を有することを特徴とする画像符号化装置の制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１２−２５３４４３（Ｐ２０１２−２５３４４３Ａ）
【公開日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願番号】特願２０１１−１２２５９５（Ｐ２０１１−１２２５９５）
【出願日】平成２３年５月３１日（２０１１．５．３１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願日】平成２３年５月３１日（２０１１．５．３１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]