(57)【特許請求の範囲】
【請求項１】
画像を構成するタイルを符号化する画像符号化装置であって、
タイルを構成する２×２画素の各ブロックについて、代表１画素を出力することにより、１／２縮小タイルを生成する縮小手段と、
前記１／２縮小タイルの各１画素から前記２×２画素の各ブロックを復元するための補間方法を示す補間データを生成する生成手段と、
前記１／２縮小タイルを可逆符号化することにより、可逆符号化データを生成する可逆符号化手段と、
前記補間データを用いて前記１／２縮小タイルから前記タイルと同じ解像度の画像を復元し、復元された画像を非可逆符号化することにより、非可逆符号化データを生成する非可逆符号化手段と、
前記生成手段で生成された補間データに基づいて、前記可逆符号化手段、前記非可逆符号化手段のいずれか一方を選択して実行させる選択手段と、
前記可逆符号化手段が選択された場合には、前記可逆符号化データおよび前記補間データを前記タイルの符号化データとして出力し、前記非可逆符号化手段が選択された場合には、前記非可逆符号化データを前記タイルの符号化データとして出力する出力手段とを備え、
前記補間方法は、各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いて求める第１の補間方法と、各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いずに画素データから求める第２の補間方法を含むことを特徴とする画像符号化装置。
【請求項２】
前記選択手段は、前記生成手段で生成される補間データが示す補間方法の分布に基づいて、前記可逆符号化手段、前記非可逆符号化手段のいずれか一方を選択することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記選択手段は、前記生成手段で生成される補間データのデータ量に基づいて、前記可逆符号化手段、前記非可逆符号化手段のいずれか一方を選択することを特徴とする請求項１に記載の画像符号化装置。
【請求項４】
前記選択手段は、前記生成手段で生成される補間データのデータ量Ｌを所定の閾値ＴＨと比較し、Ｌ≦ＴＨであれば可逆符号化手段を選択し、Ｌ＞ＴＨであれば非可逆符号化手段を選択することを特徴とする請求項１に記載の画像符号化装置。
【請求項５】
コンピュータに読み込み込ませ実行させることで、前記コンピュータを請求項１乃至４のいずれか１項に記載の画像符号化装置として機能させるコンピュータプログラム。
【請求項６】
請求項５に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項７】
画像を構成するタイルを符号化する画像符号化装置の制御方法であって、該制御方法には、
縮小手段により、タイルを構成する２×２画素の各ブロックについて、代表１画素を出力することにより、１／２縮小タイルを生成する縮小工程と、
生成手段により、前記１／２縮小タイルの各１画素から前記２×２画素の各ブロックを復元するための補間方法を示す補間データを生成する生成工程と、
可逆符号化手段により、前記１／２縮小タイルを可逆符号化することにより、可逆符号化データを生成する可逆符号化工程と、
非可逆符号化手段により、前記補間データを用いて前記１／２縮小タイルから前記タイルと同じ解像度の画像を復元し、復元された画像を非可逆符号化することにより、非可逆符号化データを生成する非可逆符号化工程と、
選択手段により、前記生成手段で生成された補間データに基づいて、前記可逆符号化手段、前記非可逆符号化手段のいずれか一方を選択して実行させる選択工程と、
出力手段により、前記可逆符号化手段が選択された場合には、前記可逆符号化データおよび前記補間データを前記タイルの符号化データとして出力し、前記非可逆符号化手段が選択された場合には、前記非可逆符号化データを前記タイルの符号化データとして出力する出力工程とを備え、
前記補間方法は、各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いて求める第１の補間方法と、各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いずに画素データから求める第２の補間方法を含むことを特徴とする制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高解像度の画像データを符号化する技術に関する。
【背景技術】
【０００２】
従来、画像をタイルに分割し、このタイルを可逆符号化する構成と、非可逆符号化する構成を備え、いずれか一方の符号化結果をタイルの最終的な符号化データとして出力する画像符号化技術が知られている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０８−１６７０３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
近年、画像入出力機器の高精度化に伴い、画像データの高解像度化が進んでいる。高解像度の画像データを高速に処理するためには、それ以前より多くのハードウェアリソースや、処理時間が必要である。たとえば、１２００ｄｐｉの解像度の画像を扱う符号化装置が、それ以前の６００ｄｐｉの画像を符号化する装置と同等の時間内で、符号化処理を行なう場合には、内部の演算処理能力を４倍にする必要がある。本願発明は、上述点に鑑みてなされたものであり、高解像度画像を、効率良く符号化する技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
かかる課題を解決するため、本発明の画像符号化装置は以下の構成を備える。すなわち、画像を構成するタイルを符号化する画像符号化装置であって、タイルを構成する２×２画素の各ブロックについて、代表１画素を出力することにより、１／２縮小タイルを生成する縮小手段と、前記１／２縮小タイルの各１画素から前記２×２画素の各ブロックを復元するための補間方法を示す補間データを生成する生成手段と、前記１／２縮小タイルを可逆符号化することにより、可逆符号化データを生成する可逆符号化手段と、前記補間データを用いて前記１／２縮小タイルから前記タイルと同じ解像度の画像を復元し、復元された画像を非可逆符号化することにより、非可逆符号化データを生成する非可逆符号化手段と、前記生成手段で生成された補間データに基づいて、前記可逆符号化手段、前記非可逆符号化手段のいずれか一方を選択して実行させる選択手段と、前記可逆符号化手段が選択された場合には、前記可逆符号化データおよび前記補間データを前記タイルの符号化データとして出力し、前記非可逆符号化手段が選択された場合には、前記非可逆符号化データを前記タイルの符号化データとして出力する出力手段とを備え、前記補間方法は、各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いて求める第１の補間方法と、ブロックにおける非代表３画素を１／２縮小画像の画素値を用いずに画素データから求める第２の補間方法を含むことを特徴とする。
【発明の効果】
【０００６】
本発明によれば、高解像度画像を、効率良く符号化することが可能となる。
【図面の簡単な説明】
【０００７】
【図１】画像符号化装置の構成図
【図２】画像符号化の処理手順を示すフローチャート
【図３】タイルデータと２×２画素ブロックとの関係図
【図４】２×２画素の画素ブロックを示す図
【図５】画像符号化装置の構成図
【図６】１タイル分の符号化データの構造を示す図
【図７】ＪＰＥＧベースライン符号化データの構成図
【図８】符号化対象画像とストライプ、タイルの関係を示す図
【図９】複数タイル分の符号化データの構造を示す図
【図１０】タイルとブロックラインの関係を示す図
【図１１】フラット／ノンフラットの判定結果を示す図
【図１２】補間データ生成部の内部構成図
【図１３】フラット判定部１２０１の処理手順を示す図
【図１４】情報処理装置のブロック構成図
【図１５】ノンフラットブロック符号化処理の手順を示す図
【図１６】２×２画素のパターンを示す図
【図１７】画像符号化装置の構成図
【図１８】画像符号化装置の構成図
【発明を実施するための形態】
【０００８】
以下添付図面に従って本発明に係る実施形態を詳細に説明する。
【０００９】
［第１の実施形態］
図１は、本実施形態における画像符号化装置の構成図である。本実施形態では、画像符号化装置における縮小手段が、装置外部からの入力画像データ中の着目Ｎ画素（Ｎは２以上の整数）に対応する１画素を出力することで縮小画像データを生成する。すなわち、入力画像データの総画素数をＭとしたとき、縮小画像生成手段は、着目Ｎ画素に対応する１画素を出力する処理をＭ／Ｎ回繰り返すことで、Ｍ／Ｎ画素からなる縮小画像を生成する。例えば、総画素数を４０９６画素（６４×６４画素）としたとき、着目４画素（２×２画素）に対応する１画素を出力する処理を１０２４回繰り返すことで、１０２４画素（３２×３２画素）からなる縮小画像を生成する。そして、補間データ生成手段が、元解像度の画像を復元するための着目Ｎ画素の補間方法を複数種類の補間手法から特定する、補間データを生成する。そして、この補間データと縮小画像の可逆符号化データとからなる符号列、あるいは縮小画像を元の解像度に復元した画像の非可逆符号化データからなる符号列を生成し、出力するものである。なお、入力画像データの入力源は、イメージスキャナとするが、画像データをファイルとして格納している記憶媒体等であっても良いし、印刷データ等の情報に基づいてレンダリングするレンダリング部であっても良い。なお、以降の実施形態では、上記の「Ｎ」で表わされる画素数が２×２個（＝４画素）として説明する。本実施形態に係る画像符号化装置の符号化対象とする画像データは、ＲＧＢカラー画像データであり、各コンポーネント（色成分）は８ビットで０〜２５５の範囲の輝度値を表現した画素データにより構成されるものとする。符号化対象の画像データの並びは点順次、即ち、ラスタースキャン順に各画素を並べ、その各画素はＲ，Ｇ，Ｂの順番でデータを並べて構成されるものとする。画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。また、説明を簡易にするため、Ｗ、Ｈは後述する符号化の処理単位、タイルのサイズ（本実施形態では水平、垂直方向とも３２画素）の整数倍であるとして説明する。但し、入力画像データはＲＧＢ以外の色空間、例えば、ＹＣｂＣｒやＣＭＹＫでも構わず、その色空間の種類、成分の数は問わない。さらに、１成分のビット数も８ビットに限らず、８ビットを超えるビット数でも構わない。
【００１０】
以下、図１に示す画像符号化装置における符号化処理を説明する。図中、１１５は図１の画像符号化装置全体の動作を制御する制御部である。各処理部は制御部１１５の制御によって協調して動作する。まず、画像入力部１０１は符号化対象となる画像データを順に入力し、ラインバッファ１０２に出力する。ここでの画像データの入力順序は、先に説明したとおりラスタースキャン順とする。ラインバッファ１０２は画像データを所定のライン数（Ｔｈ）分格納する領域を持ち、画像入力部１０１から入力される画像データを順次格納していく。ここで、Ｔｈは後述するタイル分割部１０３で切り出されるタイルの垂直方向の画素数であり、本実施形態では３２画素とする。以降、符号化対象画像データをＴｈラインの幅で分割したデータをストライプと呼ぶ。ラインバッファ１０２に必要とされる容量、即ち１ストライプのデータ量はＷ×Ｔｈ×３（ＲＧＢ分）バイトである。先に述べた通り、説明の便宜上、垂直方向画素数ＨはＴｈの整数倍であるとし、画像の末尾で不完全なストライプが発生しないものとする。さて、ラインバッファ１０２に１ストライプ（Ｔｈライン分）の画像データが格納されると、タイル分割部１０３はラインバッファ１０２に格納されるＴｈライン分の画像データから、水平方向Ｔｗ画素、垂直方向Ｔｈ画素で構成されるタイルに分割する。そして、このタイル単位に読み出してタイルバッファ１０４へと格納する。上述したように、符号化対象の画像の水平方向画素数ＷはＴｗの整数倍としているので、タイルに分割した場合に不完全なタイルが発生しないものとする。なお、実施形態では、Ｔｗ＝Ｔｈ＝３２としているので、１タイルのサイズは３２×３２画素となる。図８に符号化対象の画像データとストライプ、タイルの関係を図示する。図のように画像中、水平方向ｉ番目、垂直方向ｊ番目のタイルをＴ（ｉ，ｊ）と記す。タイルバッファ１０４は１タイル分の画素データを格納する領域を持ち、タイル分割部１０３から出力されるタイルデータを順次格納していく。タイルバッファ１０４に必要とされる容量はＴｗ×Ｔｈ×３（ＲＧＢ分）バイトである。解像度変換部１０５は、タイルバッファ１０４に格納されるタイルデータについて２×２画素の領域から１画素を抽出するサブサンプリングを行い、１／２縮小タイルを生成する。ここで１／２縮小タイルとはタイルバッファ１０４に格納されるタイルデータを、水平、垂直両方向の画素数を１／２としたタイルを表す。また、２×２画素の領域の画像データを、これ以降、単に画素ブロックと呼ぶ。図３にタイルデータと２×２画素の画素ブロックＢｎの関係を図示する。また、注目する画素ブロックＢｎの中の４つの画素を、同図のように、Ｂｎ（０，０）、Ｂｎ（０，１）、Ｂｎ（１，０）、Ｂｎ（１，１）と表す。また、注目ブロックＢｎの前（左隣）の画素ブロックをＢｎ−１、Ｂｎの次（右隣）の画素ブロックをＢｎ＋１と表現し、Ｂｎの下のブロックをＢｎ＋ｂと表す。ここで“ｂ”はタイル内の水平方向のブロック数であり、タイルの水平方向画素数Ｔｗを用いて表せば、ｂ＝Ｔｗ／２である。実施形態では、Ｔｗ＝３２であるので、ｂ＝１６となる。本実施形態の解像度変換部１０５は、着目画素ブロックＢｎのうち��左上隅の位置の画素Ｂｎ（０，０）を、１／２縮小タイルの１画素として抽出する。タイルデータ中の全ての画素ブロックＢ０〜Ｂｍ（ｍ＝Ｔｗ／２×Ｔｈ／２−１＝１６×１６−１＝２５５）についてサブサンプリングを行い、オリジナルタイルに対し、水平、垂直方向とも１／２の画素数の１／２縮小タイルを生成する。解像度変換部１０５は、生成した１／２縮小タイルデータを１／２縮小タイルバッファ１０６へ格納する。従って、実施形態の場合、Ｗ×Ｈ画素で構成されるオリジナルの画像データのから、Ｗ×Ｈ／４画素数の縮小画像を生成する縮小画像生成手段として機能することになる。補間データ生成部１１０は、１／２縮小タイルから元のタイルデータ（初期タイル）を復元するために必要な情報を生成する。即ち、画素ブロック内のサブサンプリング対象となった画素Ｂｎ（０，０）を除く、非サンプリング対象の３画素｛Ｂｎ（０，１），Ｂｎ（１，０），Ｂｎ（１，１）｝を、どのように補間すればよいかを示す補間データを生成するものである。
【００１１】
図１２は、本実施形態に係る補間データ生成部１１０の内部のブロック構成図を示す。生成部１１０は、「各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いて求める第１の補間方法」または「各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いずに画素データから求める第２の補間方法」に属する補間データを出力する。この補間データ生成部１１０は、フラット判定部１２０１、ノンフラットブロック解析部１２０２で構成される。フラット判定部１２０１は、タイル内の画像データが、縮小タイルデータの画素から単純拡大（画素繰り返し）処理して復元可能であるかどうかを判定する“フラット判定”を行う。フラット判定の最小単位は２×２画素の画素ブロックである。以下、この画素ブロックが単純拡大で再現できるブロックである場合、それをフラットブロックと呼び、そうでないブロックをノンフラットブロックと呼ぶこととする。図３において、着目画素ブロックＢｎがフラットブロックであるのは、以下の式（１）が成り立つ場合である。
Ｂｎ（０，０）＝Ｂｎ（０，１）＝Ｂｎ（１，０）＝Ｂｎ（１，１）…（１）
【００１２】
フラット判定部１２０１の役割は、タイルを構成する各画素ブロックについてフラットブロックかノンフラットブロックかを表す情報を生成する。以下、図１３のフローチャートに従い、フラット判定部１２０１の処理手順を説明する。なお、図１３は、１つのタイルに対する処理である点に注意されたい。また、タイルに含まれる全ての画素ブロックがフラットブロックである場合、そのタイルをフラットタイルと呼び、そうでない場合には、ノンフラットタイルと呼ぶ。同様に、タイル内で水平方向に連続するＴｗ／２個（実施形態では１６個）のブロック群を以降、ブロックラインと呼ぶ。そして、ブロックライン内の全ブロックがフラットブロックであるとき、そのブロックラインをフラットブロックラインと呼び、少なくとも１つのノンフラットブロックが含まれる場合にはノンフラットブロックラインと呼ぶ。まず、フラット判定部１２０１はＴｗ×Ｔｈ画素のタイルデータを入力する（ステップＳ１３０１）。各タイルは独立に処理を行うものとし、タイルの外部の画素（周囲画素）を参照する場合には、各色成分の値が２５５であるものとして処理する。フラット判定部１２０１は、次に、ステップＳ１３０２にて、フラット／ノンフラットの判定を、Ｔｗ×Ｔｈ画素のタイルを構成する２×２画素の画素ブロックが全てに対して行なう。すなわち、着目タイルがフラットタイルであるか否かを判定する。着目タイルがフラットタイルであると判定した場合、処理をステップＳ１３０３へ移し、１ビットのフラグ“１”をノンフラットブロック解析部１２０２に出力し、本処理を終える。一方、着目タイル内に少なくとも１つのノンフラットブロックが存在する場合（ステップＳ１３０２がＮＯ）には、フラット判定部１２０１は、処理をステップＳ１３０４へ移す。そして、１ビットのフラグ“０”をノンフラットブロック解析部１２０２に出力し、ステップＳ１３０５へ処理を移す。ステップＳ１３０５では、水平方向に連続するｂ（＝Ｔｗ／２＝１６）個の画素ブロックからなるブロックラインのひとつに着目し、ステップＳ１３０２と同様に、フラットブロックラインかノンフラットブロックラインかの判定を行う。フラットブロックラインである場合（ＹＥＳ）は、ステップＳ１３０６へ処理を移し、１ビットのフラグ“１”をノンフラットブロック解析部１２０２に出力する。一方、着目ブロックラインがノンフラットブロックラインであると判定した場合（ステップＳ１３０５がＮＯ）には、処理をステップＳ１３０７へ移し、１ビットのフラグ“０”をノンフラットブロック解析部１２０２に出力して、処理をステップＳ１３０８へ移す。ステップＳ１３０８に至る場合には、着目するブロックライン内に、少なくとも１つのノンフラットブロックが存在することになる。このため、着目するブロックラインを構成するｂ（＝Ｔｗ／２＝１６）個のブロックそれぞれについて、フラット／ノンフラットブロックの判定結果を示すフラグの配列が必要となる。ここで、ブロックのフラグは１ビットで良く、フラットブロックの場合は“１”、ノンフラットブロックの場合は“０”とする。本実施形態の場合、ブロックラインはｂ（＝１６）個の画素ブロックで構成されるので、ノンフラットブロックラインのフラグ配列はｂ個、すなわち、１６ビットとなる。ステップＳ１３０８では、着目するブロックラインのフラグ配列を以前のノンフラットブロックラインのフラグ配列と比較し、一致するか否かを判定する。なお、着目ブロックラインが着目タイルの最初のブロックラインである場合には、それ以前のブロックラインは存在しない。そこで、フラット判定部１２０１は、着目タイルのブロックラインの判定に先立ち、内部のメモリに、ブロックラインの全ブロックがノンフラットブロックであることを示す情報を予め用意しておく。つまり、フラットブロックを“１”、ノンフラットブロックを“０”と定義したとき、初期値としてｂ個（ｂビット）の“０”を用意しておく。以降、このｂビットを“参照ノンフラットブロックライン情報”と呼ぶ。勿論、復号装置でも１タイルの復元する際には、“参照ノンフラットブロックライン情報”を用意しておく。従って、ステップＳ１３０８では、着目ブロック内の各ブロックのフラットブロック／ノンフラットブロックの判定結果の並びが、参照ノンフラットブロックライン情報と一致するか否かを判定することになる。
【００１３】
ここで、図１０のタイルデータを例にして、ステップＳ１３０８の判定処理を説明する。このタイルデータはは、先頭から４番目までのブロックラインがフラットブロックラインであり、５番目のブロックラインがノンフラットブロックラインの例である。図１０のタイルに対する画素ブロックのフラット／ノンフラットの判定結果は、図１１に示す通りとなる。今、５番目のブロックラインが着目ブロックラインであるとする。着目ブロックラインは５番目のブロックラインであるから、そのブロックラインは着目タイル内の最初のノンフラットブロックラインであると判定される。従って、その着目ブロックラインに含まれる画素ブロックの判定結果と、参照ノンフラットブロックライン情報（１６ビットの“０００…０００”）と比較され、一致すると判定される。このように、着目ブロックラインの判定結果と参照ノンフラットブロックライン情報とが一致したと判定した場合には、ステップＳ１３０９に進む。そして、着目ブロックライン内の各ブロックの判定結果が、参照ノンフラットブロックライン情報と一致したことを示す１ビットのフラグ“１”をノンフラットブロック解析部１２０２に出力する。この場合、ブロック毎のフラット／ノンフラット判定結果を示すｂ（＝Ｔｗ／２）ｂｉｔのフラグは出力しなくてよい。一方、着目ブロックラインのフラット／ノンフラット判定結果を示すフラグの配列が、参照ノンフラットブロックラインと一致しない場合（ステップＳ１３０８がＮＯ）は、ステップＳ１３１０へ処理を移す。ここでは、フラット判定部１２０１は先ず、１ビットのフラグ”０”をノンフラットブロック解析部１２０２に出力する。そして、それに後続して着目ブロックラインのフラット／ノンフラット判定結果を示すフラグ配列（Ｔｗ／２ビット）をノンフラットブロック解析部１２０２に出力する。この後、フラット判定部１２０１は、ステップＳ１３１１にて、着目ブロックラインのフラットブロック／ノンフラットブロックの判定結果（ｂビット）で、参照ノンフラットブロックライン情報を更新する。注目しているブロックラインに対して、フラット／ノンフラット判定が終了したら、ステップＳ１３１２へ処理を移し、注目ブロックラインが、着目タイル内の最終ブロックラインであるか否かの判定を行う。最終ブロックラインではない場合（ＮＯ）は、着目するブロックラインを次のブロックラインへ移す（ステップＳ１３１３）。そして、ステップＳ１３０５へ処理を戻して同様の処理を繰り返す。最終ブロックラインであった場合（ＹＥＳ）は、タイルデータに対するフラット判定処理を終了する。フラット判定部１２０１は、以上の処理を、着目するタイルデータについて行い、フラット／ノンフラットの判定結果をノンフラットブロック解析部１２０２へ出力する。次に、ノンフラットブロック解析部１２０２の処理を説明する。このノンフラットブロック解析部１２０２は、フラット判定部１２０１と同様に、１タイルに相当する処理の開始時に、１ブロックラインの全ブロックがノンフラットブロックを示す「参照ノンフラットブロックライン情報」を設定しておく。そして、ノンフラットブロック解析部１２０２は、フラット判定部１２０１からの判定結果を解析しつつ、そのまま通過させ、補間データバッファ１１２に出力する。上記ステップＳ１３１０で、１ビットのフラグ“０”が出力されたブロックラインが存在する場合、解析部１２０２は、それに後続する各ブロックのフラットブロック／ノンフラットブロックを示す判定結果で、参照ノンフラットブロックライン情報を更新する。もし、着目ブロックラインに対し図１３のステップＳ１３０９の処理が行われた場合には、その際の参照ノンフラットブロックラインを参照することで、どのブロックがノンフラットブロックであるのかを判定できる。また、着目ブロックラインに対し、図１３のステップＳ１３１０の処理が行われていると判断した場合には先頭の１ビットのフラグ“０”に後続するｂビットの値を調べれば、ブロックがノンフラットブロックであるのかを判定できる。すなわち、ノンフラットブロック解析部１２０２は、着目タイル中の全てのノンフラットブロックの位置と個数を判定できることになる。そして、ノンフラットブロック解析部１２０２は、縮小タイルの画素の単純拡大では再現できない２×２画素で構成される画素ブロック（ノンフラットブロック）に対して、その画素ブロック内の色数や配置を解析して、付加情報を生成し、出力する。すなわち、ノンフラットブロック解析部１２０２は、フラット判定部１２０１から出力される、フラット／ノンフラットの判定結果を受け取り、ノンフラットブロックについて、解析を行い、ノンフラットブロックを復元するための情報を生成し、出力する。ノンフラットブロック解析部１２０２は、ノンフラットブロックと判定されたブロックにつき、図１５のフローチャートに従ったノンフラットブロック符号化処理を行なう。以下、図１５に従って、ノンフラットブロック解析部１２０２の処理を説明する。先ず、ステップＳ１５０１にて、１個のノンフラットブロックＢｎを着目ブロックとし、２×２画素の画素ブロックデータを入力する。そして、ステップＳ１５０２にて、着目画素ブロックＢｎが、以下の式（２）が成立するブロックであるかどうかの判定を行う。
Ｂｎ（０，１）＝Ｂｎ＋１（０，０）
且つ
Ｂｎ（１，０）＝Ｂｎ＋ｂ（０，０）
且つ
Ｂｎ（１，１）＝Ｂｎ＋ｂ＋１（０，０）          …（２）
【００１４】
上記式（２）が成り立つブロックＢｎを、以降、「周囲３画素一致ブロック」と定義する。上記式（２）に示すように、ペア｛Ｂｎ（０，１）、Ｂｎ＋１（０，０）｝、｛Ｂｎ（１，０）、Ｂｎ＋ｂ（０，０）｝、及び、｛Ｂｎ（１，１）とＢｎ＋ｂ＋１（０，０）｝との一致／不一致を判定するのには、理由がある。一般に、着目画素と、その着目画素に隣接する画素間の相関度は高いし、そのような画像が多い。そのため、着目画素の画素値を予測する場合には、その隣接する画素を予測のための参照画素として使用することが多い。ブロック内の４画素が全て同一ではない、即ちフラットブロックではない場合には、ペア｛Ｂｎ（０，１）、Ｂｎ＋１（０，０）｝、｛Ｂｎ（１，０）、Ｂｎ＋ｂ（０，０）｝、及び、｛Ｂｎ（１，１）とＢｎ＋ｂ＋１（０，０）｝とが一致する可能性が高い。この理由で、Ｂｎ（０，１）とＢｎ＋１（０，０）とが一致するか否かを判定するようにした。他のペア｛Ｂｎ（１，０）、Ｂｎ＋ｂ（０，０）｝、及び、｛Ｂｎ（１，１）とＢｎ＋ｂ＋１（０，０）｝を比較するのも同じ理由である。そして、先に示した式（２）が満たされる場合（３つのペアが互いに等しい場合）、短い符号語を割り当てることで情報量の削減できた。なお、実施形態では、各画素ブロックの左上隅の位置の画素をサブサンプリングして縮小画像を生成した。従って、式（２）における、画素Ｂｎ＋１（０，０）、Ｂｎ＋ｂ（０，０）、Ｂｎ＋ｂ＋１（０，０）は、着目画素ブロックＢｎに隣接する画素ブロック内のサブサンプリング対象画素でもある点に注意されたい。さて、注目ブロックＢｎが、式（２）の成立するブロックである場合には、Ｂｎ（０，１）、Ｂｎ（１，０）、Ｂｎ（１，１）の位置の３画素が、周囲の画素から再現可能であると判断できる。但し、ブロックが画像の右端もしくは、画像の下端に位置する場合には、ブロックの外側の画素を参照することができない。そのため、外側の画素の各成分を仮想的に、予め任意の値を設定しておき、その画素値との一致／不一致判定を行うこととする。本実施形態では、仮想的に、各成分値を“２５５”を設定しておく。しかし、“２５５”に限らず、符号化側と復号側で同じ値を用いるように定めておけばこれ以外の値でも構わない。
【００１５】
図４に、注目する２×２画素の画素ブロックを示す。図４に示す画素Ｘが縮小画像生成のためにサブサンプリングされた画素（非代表１画素）を示し、着目画素ブロックＢｎ内の画素Ｂｎ（０，０）に相当するものである。また、画素Ｘａ，Ｘｂ，Ｘｃは着目ブロックＢｎ内の画素（０，１），Ｂｎ（１，０），Ｂｎ（１，１）の画素（非代表３画素）を示している。以下、画素Ｘ、Ｘａ，Ｘｂ，Ｘｃについて説明する。さて、ステップＳ１５０２にて、式（２）の成立すると判定した場合、着目ブロックＢｎ内の画素Ｘａ、Ｘｂ、Ｘｃは、縮小画像の画素を用いて再現できることになる。従って、ステップＳ１５０３へ処理を移し、再現できることを示す１ビットのフラグ“１”を出力する。一方、着目ブロックが式（２）を満足しないブロックあると判定された場合、ステップＳ１５０４へ処理を移し、１ビットのフラグ“０”を出力する。次に、処理はステップＳ１５０５に進み、着目ブロックに含まれる色数が“２”か、それ以上（３、もしくは４色）かを判定する。なお、着目ブロックはノンフラットブロックであるので、色数が“１”となることは有り得ない。着目ブロックに含まれる色数が“２”より大きい（３、もしくは４色）と判定した場合、ステップＳ１５１２にて、１ビットのフラグ“０”を出力する。そして、ステップＳ１５１３にて、非代表３画素Ｘａ，Ｘｂ，Ｘｃの画素値そのものを、１／２縮小画像の画素値とは関わりの無い画素データとして更に出力する。実施形態では、１画素がＲ、Ｇ、Ｂの３コンポーネントであり、１コンポーネントが８ビットとしているので、３画素Ｘａ，Ｘｂ，Ｘｃの合計ビット数は３×８×３＝７２ビットとなる。一方、着目ブロックに含まれる色数が“２”であると判定した場合、ステップＳ１５０６にて出現色数が“２”であることを示す１ビットのフラグ“１”を出力する。そして、ステップＳ１５０７にて、着目ブロック内の、縮小画像に利用されている図４の画素Ｘ（代表１画素）を除く３画素Ｘａ，Ｘｂ，Ｘｃ（非代表３画素）が、図１６のパターン１６０１乃至１６０７のいずれであるのかを示す画素配置情報を出力する。図１６に示すようにパターン数は全部で７つあるので、画素配置情報は３ビットであれば１つのパターンを特定できる。ただし、実施形態では、縮小画像に利用されている画素と同じ色の画素は“１”、異なる色の画素を“０”と表わし、図４の画素Ｘａ，Ｘｂ，Ｘｃに相当する各ビットをその順番に出力するようにした（この場合も３ビットとなる）。例えば、図１６のパターン１６０１に一致する場合、画素Ｘａ，Ｘｂ，Ｘｃは同色であり、且つ、縮小画像に利用されている画素Ｘの色とは異なるので、画素配置情報の３ビットは“０００”となる。また、パターン１６０２の場合は、“１００”、パターン１６０３の場合には“０１０”、パターン１６０４の場合には“００１”となる。他は説明するまでもないであろう。次いで、ステップＳ１５０８にて、着目ブロックＢｎ内の縮小画像に利用された画素Ｘを除く画素Ｘａ，Ｘｂ，Ｘｃのうち、画素Ｘと異なる色の画素と同じ色の画素が、近傍に存在するか否かを判断する。本実施形態では、比較する近傍の画素は以下の３画素とし、かつ以下に記す順番に比較する。着目ブロックの右隣のブロックＢｎ＋１の画素Ｂｎ＋１（０，０）、着目ブロックの直下のブロックＢｎ＋ｂの画素Ｂｎ＋ｂ（０，０）、着目ブロックの右下に隣接するブロックＢｎ＋ｂ＋１の画素Ｂｎ＋ｂ＋１（０，０）。なお、３画素のいずれかと一致するかを示せば良いので、この比較結果は２ビットとした。そして、一致するのが、Ｂｎ＋１（０，０）であった場合には２ビットの“１１”、Ｂｎ＋ｂ（０，０）と一致するなら２ビットの“０１”、Ｂｎ＋ｂ＋１（０，０）とが一致するなら２ビットの“１０”を出力する（ステップＳ１５０９）。また、周辺の３画素のいずれとも一致しない場合（ＮＯ）には、処理をステップＳ１５１０へ移し、２ビットのフラグ“００”を出力する。そして、第２色の画素値を出力し（ステップＳ１５１１）、注目ブロックＢｎに対する処理を終了する。本実施形態では符号化対象画像が、各色８ビットのＲＧＢデータであるからステップＳ１５１１においては２４ビットが出力される。こうして、注目ブロックＢｎの処理が終了したら、ステップＳ１５１４により、着目ブロックが着目タイル中の最後のノンフラットブロックであるか否かの判定を行う。否の場合には、次のノンフラットブロックの処理に移る（ステップＳ１５１５）。次のノンフラットブロックに対しても、ステップＳ１５０１からの処理を同様に行う。また、着目ブロックが最後のノンフラットブロックであると判定した場合には、本処理を終了する。以上のようにして、ノンフラットブロック解析部１２０２からは、フラット／ノンフラット判定結果と、ノンフラットブロックの解析結果により生成された補間データが出力される。これらのデータは補間データバッファ１１２に格納される。なお、２×２画素で表わされる画素ブロックは、これまでの説明からわかるように、以下の（ａ）乃至（ｅ）の５種類に分類できる。
（ａ）フラットブロック
（ｂ）ノンフラットブロック、かつ、周囲３画素一致ブロック
（ｃ）ノンフラットブロック、かつ、そのブロック内に出現する色数が“２”であり、周辺画素に第２色と同じ色の画素が存在するブロック、
（ｄ）ノンフラットブロック、かつ、そのブロック内に出現する色数が“２”であり、周辺画素に第２色と同じ色の画素が存在しないブロック、
（ｅ）ノンフラットブロック、かつ、そのブロック内に出現する色数が“２”より多い（３色、もしくは４色）ブロック
【００１６】
上記種類（ａ）乃至（ｅ）は「各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いて求める第１の補間方法」に相当する。また、上記種類（ｄ），（ｅ）は「各ブロックにおける非代表３画素を１／２縮小画像の画素値を用いずに画素データから求める第２の補間方法」に相当する。補間データ生成部１１０は、上記の処理を行なっている最中に、画素ブロックが上記（ａ）乃至（ｅ）のいずれに該当するかを判定し、それぞれのブロックの出現数を計数する。以降、上記種類（ａ）乃至（ｅ）のブロック数をＮａ、Ｎｂ、Ｎｃ，Ｎｄ、Ｎｅと表わす。補間データ生成部１１０は、１タイルに対して補間データを生成するに先立って、Ｎａ乃至Ｎｅを“０”で初期化し、１タイルに対する補間データの生成及び出力が完了したとき、計数したブロック数Ｎａ乃至Ｎｅを符号化方式選択部１１１に出力する。実施形態では、１タイルが３２×３２画素で構成されるので、その中には１６×１６個の画素ブロックが存在することになる。従って、補間データ生成部１１０が、仮に図１３のステップＳ１３０３の処理を行なった場合、注目タイル内の全画素ブロックは、フラットブロックであることになり、Ｎａ＝２５６となり、Ｎａ以外のブロック数Ｎｂ乃至Ｎｅは“０”として決定できる。また、ステップＳ１３０６の処理を行なった場合には、それまでに計数したＮａに“１６”を加算すればよい。そして、図１５のステップＳ１５０３の処理を行なった場合には、Ｎａに“１”を加算する。また、ステップＳ１５１２の処理を行なった場合にはＮｅに“１”を加算する。それ以外については、これまでの説明から十分に理解できよう。さて、符号化方式選択部１１１は、補間データ生成部１１０が計数したブロック数Ｎａ乃至Ｎｅの頻度分布に基づき、１／２縮小タイルバッファ１０６に格納される１／２縮小タイルデータの符号化方法を決定する。そして、その決定結果を２値（１ビット）の制御信号として非可逆符号化部１０７、可逆符号化部１０８、及び、符号列形成部１１３に出力する。この結果、非可逆符号化部１０７、可逆符号化部１０８のいずれか一方が、１／２縮小タイルバッファ１０６に格納された１／２縮小タイルデータの符号化処理を行なう。
【００１７】
なお、非可逆符号化部１０７が選択された場合には、１／２縮小タイルバッファ１０６に格納された１／２縮小タイルデータは、解像度変換部１１６により、一旦、元の解像度の画像に復元（拡大）される。具体的には、解像度変換部１１６は、補間データバッファ１１２に格納されている補間データを用いて解像度変換（１／２縮小タイルデータから元の解像度の画像を復元する処理）を行う。そして、ここで解像度が復元された画像データが非可逆符号化部１０７で符号化され、符号化データバッファ１０９へ出力される。
【００１８】
以上で生成された符号化データは、符号列形成部１１３に出力される。これ以降の実施形態では、符号化方式選択部１１１（または後述する符号化方式選択部５０４）からの制御信号が“０”の場合には非可逆符号化部１０７が非可逆符号化処理を行なう。また、制御信号が“１”の場合には、可逆符号化部１０８が可逆符号化処理を行なう。
【００１９】
一般に、文字、線画、クリップアート画像などでは、先に示したブロックの種類（ａ）乃至（ｃ）が多い傾向が見られる。言い換えれば、文字、線画、クリップアート画像などの場合、ブロック数Ｎａ乃至Ｎｃの値が大きくなる。一方、複雑なＣＧ画像や自然画像などでは、ブロック数Ｎｄ、Ｎｅの値が大きくなる傾向が見られる。また、文字、線画、クリップアートなどでは、非可逆符号化による画質劣化が目に付きやすく、可逆符号化により高い圧縮性能を得られる傾向にある。一方、複雑なＣＧや自然画像では、逆に非可逆符号化による画質劣化が目に付きにくく、かつ、可逆符号化では高い圧縮性能を得られない傾向がある。更には、ブロックの種類（ａ）乃至（ｃ）の画素ブロックは、１／２縮小画像の画素値を用いて元の画像を復元することになる。従って、仮に、縮小画像に画素変化（劣化）が生じた場合、復号時に元の解像度の画像（初期タイル）を復元する際にその劣化を広げる方向に作用する。このため、縮小画像符号化時の画質劣化の影響を受け易い。一方で、ブロックの種類（ｄ），（ｅ）の画素ブロックは、３画素Ｘａ，Ｘｂ，Ｘｃの画素値そのものを、１／２縮小画像の画素値とは関わりの無い画素データとして指定するため、画質劣化の影響が少ない。
【００２０】
上記の考えから、符号化方式選択部１１１は、Ｎａ，Ｎｂ，Ｎｃの値が大きい場合は、１／２縮小タイルデータを可逆符号化するよう、制御信号“１”を出力する。また、符号化方式選択部１１１は、Ｎｄ、Ｎｅの値が大きい場合は、１／２縮小タイルデータを元の解像度の画像に復元してから非可逆符号化するよう、制御信号“０”を出力する。具体的には、符号化方式選択部１１１は、予め設定された閾値ＴＨ１と、Ｎａ＋Ｎｂ＋Ｎｃの合算値とを比較し、次式（３）を満たすとき、制御信号“１”を出力し、満たさない場合には制御信号“０”を出力する。
Ｎａ＋Ｎｂ＋Ｎｃ＞ＴＨ１    …（３）
上記式（３）の代りに、次式（４）を採用しても良い。これら式（３）、（４）は互いに等価のものであるのは理解できよう。
Ｎｄ＋Ｎｅ≦ＴＨ１          …（４）
なお、閾値ＴＨ１は、ユーザが適宜設定できるようにするものとするが、典型的には、タイルに含まれるブロック数の１／２を示す値が好適である。実施形態では、１タイルには１６×１６個の画素ブロックが含まれるので、ＴＨ１＝１２８となる。
【００２１】
さて、非可逆符号化部１０７は、符号化方式選択部１１１から出力される制御信号が“０”の場合に、バッファ１０６に格納される１／２縮小タイルデータを、バッファ１１２に格納されている補間データを用いて、解像度変換部１１６で解像度復元する。そして、解像度復元された画像データを非可逆符号化して符号化データを生成し、生成された符号化データを符号化データバッファ１０９に格納する。
【００２２】
なお、非可逆符号化部１０７における非可逆符号化処理としては様々な手法が適用可能である。ここでは静止画像符号化の国際標準方式として勧告されているＪＰＥＧ（ＩＴＵ−Ｔ  Ｔ．８１｜ＩＳＯ／ＩＥＣ１０９１８−１）のベースライン方式を適用するものとする。ＪＰＥＧについては勧告書等に詳細な説明があるのでここでは説明を省略する。なお、ＪＰＥＧ符号化で用いるハフマンテーブル、量子化テーブルは全タイルで同じものを使用することとする。また、全タイルで共通となるフレームヘッダや、スキャンヘッダ、各種テーブルなどについては符号化データバッファ１０９に格納せず、符号化データ部分のみを格納する。即ち、図７に示した一般的なＪＰＥＧベースライン符号化データの構成のうち、スキャンヘッダの直後からＥＯＩマーカの直前までのエントロピ符号化データセグメントのみが格納される。なお、ここでは説明簡略化のため、ＤＲＩ、ＲＳＴマーカによるリスタートインターバルの定義や、ＤＮＬマーカによるライン数の定義などは行わないものとする。可逆符号化部１０８は、符号化方式選択部１１１から出力される制御信号が“１”である場合に、１／２縮小タイルバッファ１０６に格納される１／２縮小タイルデータを可逆符号化して符号化データを生成する。そして、可逆符号化部１０８は、生成した符号化データを符号化データバッファ１０９に格納する。可逆符号化部１０８が実行する可逆符号化にも様々なものがあるが、ここではその一例として、国際標準方式としてＩＳＯとＩＴＵ−Ｔから勧告されるＪＰＥＧ−ＬＳ（ＩＴＵ−Ｔ  Ｔ．８７｜ＩＳＯ／ＩＥＣ１４４９５−１）を用いるものとする。しかしながら、ＪＰＥＧ（ＩＴＵ−Ｔ  Ｔ．８１｜ＩＳＯ／ＩＥＣ１０９１８−１）のロスレスモードなど、他の可逆符号化手法を用いても構わない。ＪＰＥＧ−ＬＳの詳細についても勧告書等に記載されているので、ここでは説明を省略する。また、ＪＰＥＧと同様にヘッダ等はバッファに格納せず、符号化データ部分のみを格納することとする。符号列形成部１１３は、符号化方式選択部１１１から出力される制御信号と、補間データバッファ１１２に格納される補間データ、符号化データバッファ１０９に格納される１／２縮小タイルの符号化データを結合させる。そして、必要な付加情報を加えて本画像符号化装置の出力となる符号列を、オリジナル画像データに対応する符号化画像データとして形成する。また、非可逆符号化方式が選択された場合には、補間データを用いて１／２縮小タイルは元の解像度の画像（初期タイル）に復元しているので、補間データを含まない「元の解像度のタイルを表す符号化データ」となる。このとき、符号列形成部１１３は、符号化方式選択部１１１から出力される制御信号に基づき、どのタイルが可逆符号化され、どのタイルが非可逆符号化されているのかを示す情報も付加して、出力する。符号出力部１１４は符号列形成部１１３により生成された出力符号列を装置外部へと出力する。出力対象が記憶装置であれば、ファイルとして出力することになる。以上のように、本実施形態の画像符号化装置では、複数の画素で構成されるタイル（実施形態では３２×３２画素のサイズ）を単位に符号化処理を行う。各タイルについて、縮小���像と、縮小画像から元の画像（初期タイル）を復元するための補間データを生成し、縮小画像を可逆符号化、または、補間データを用いて縮小画像を元の画像に復元した画像を非可逆符号化により符号化する。補間データの生成は単純、簡易な処理であり、高度な演算処理を要するビットマップ符号化処理（可逆符号化部１０８による符号化処理）を縮小画像に限定することにより、画像全体をビットマップ符号化する場合に比べて、簡易・高速に符号化処理を実現できる。縮小画像の符号化には可逆と非可逆符号化のいずれかを選択して適用するが、補間データの構造に基づいて非可逆符号化を適用した場合の画質への影響が大きい場合には可逆符号化を適用することになる。よって、復号時に解像度を元に戻した場合に画質劣化が拡大することを防止できる。
【００２３】
また、非可逆符号化部１０７による符号化処理を行う際には、先に縮小されている画像を、一旦、拡大（高解像度の画像に復元）してから処理することにより、非可逆符号化による画質の劣化を極力抑えることができる。これにより、可逆符号化されるタイルと隣接する、非可逆符号化されるタイルなどの画質劣化（画質の差異）が目立ち難い。
【００２４】
［第１の実施形態の変形例］
上記第１の実施形態の変形例として、上述と同等の処理を、コンピュータプログラムによって実現する例を説明する。図１４は、本変形例における情報処理装置（例えばパーソナルコンピュータ）のブロック構成図である。図中、１４０１はＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理、復号処理を実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。また、ＲＡＭ１４０２は、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７はハードディスクドライブ装置等の大容量の外部記憶装置である。この外部記憶装置１４０７には、ＯＳ（オペレーティングシステム）や後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象画像の符号化データなどがファイルとして保存されている。また、ＣＰＵ１４０１は、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードし、実行することになる。１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象の画像の符号化データなどを記録しておいても良い。この場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えは符号化対象の画像データや、復号対象の画像の符号化データなどを本装置のＲＡＭ１４０２や外部記憶装置１４０７、あるいは記憶媒体ドライブ１４０８に入力することもできる。１４１０は上述の各部を繋ぐバスである。上記構成において、本装置の電源がＯＮになると、ＣＰＵ１４０１はＲＯＭ１４０３のブートプログラムに従って、外部記憶装置１４０７からＯＳをＲＡＭ１４０２にロードする。この結果、キーボード１４０４、マウス１４０５の入力が可能となり、表示装置１４０６にＧＵＩを表示することが可能になる。ユーザが、キーボード１４０４やマウス１４０５を操作し、外部記憶装置１４０７に格納された画像符号化処理用アプリケーションプログラムの起動の指示を行なうと、ＣＰＵ１４０１はそのプログラムをＲＡＭ１４０２にロードし、実行する。これにより、本装置が画像符号化装置として機能することになる。
【００２５】
図２のフローチャートに従って、ＣＰＵ１４０１が実行する画像符号化用のアプリケーションプログラムの処理手順を説明する。基本的に、このプログラムは、図１に示す各構成要素に相当する関数（もしくはサブルーチン）を備えることになる。ただし、図１におけるラインバッファ１０２、タイルバッファ１０４、１／２縮小タイルバッファ１０６、符号化データバッファ１０９、補間データバッファ１１２等の各領域はＲＡＭ１４０２内に予め確保することになる。まず、ステップＳ２００において、符号化を開始する前の初期化処理が行われる。ここでは、符号化対象となる画像データについて符号列に含めるべきヘッダ情報を準備したり、各種メモリ、変数等の初期化処理が行われる。初期化処理の後、ステップＳ２０１では、Ｉ／Ｆ１４０９によって接続される外部装置から符号化対象の画像データを順次入力し、ＲＡＭ１４０２に符号化対象となる画像データの１ストライプ分のデータが格納される（画像入力部１０１の処理に相当）。次に、ステップＳ２０２では、ＲＡＭ１４０２に格納されるストライプについて、着目するタイルデータを切り出し、ＲＡＭ１４０２の別のアドレス位置に格納する（タイル分割部１０３の処理に相当）。続いて、ステップＳ２０３において、着目するタイルデータ中の各画素ブロック中の左上隅の画素をサブサンプリングすることで１／２縮小タイルデータを生成し、ＲＡＭ１４０２内に格納する（解像度変換部１０５の処理に相当）。ステップＳ２０４では、１／２縮小タイルデータから元の解像度のタイルデータ（初期タイル）を復元するための補間データを生成する（補間データ生成部１１０の処理に相当）。ステップＳ２０５では、補間データの構造情報から、１／２縮小タイルデータについて可逆と非可逆のどちらの符号化方式を適用するかを決定する（符号化方式選択部１１１の処理に相当）。ステップＳ２０６において選択された符号化方式が可逆符号化である場合にはステップＳ２０７に進み、非可逆符号化である場合にはステップＳ２１３に進む。ステップＳ２０７では、１／２縮小タイルデータを可逆符号化して符号化データを生成し、ＲＡＭ１４０２に格納する（可逆符号化部１０８の処理に相当）。ステップＳ２１３では、１／２縮小タイルデータを上述した補間データを用いて元の解像度の画像に復元する（解像度変換部１１６に相当）。ステップＳ２０８では、元の解像度に復元されたタイルデータ（初期タイル）を非可逆符号化することにより、符号化データを生成し、ＲＡＭ１４０２に格納する（非可逆符号化部１０７の処理に相当）。ステップＳ２０９では、着目するタイルについて、タイルヘッダ、可逆／非可逆を識別する情報、補間データ、１／２縮小タイルまたは元の解像度のタイル符号化データを結合させて、タイル符号化データを形成する（符号列形成部１１３の処理に相当）。ステップＳ２１０では、符号化処理を行ったタイルが現在読み込まれているストライプの最後のタイルであるか否かを判定する。最後のタイルでない場合には次のタイルについてステップＳ２０２から処理を繰り返す。ストライプの最後のタイルである場合には、処理をステップＳ２１１へと移す。ステップＳ２１１では、現在読み込まれているストライプが画像の最終ストライプであるか否かを判定する。最終ストライプでない場合にはステップＳ２０１に戻り、次のストライプデータを読み込み、処理を継続する。最終ストライプの場合には、ステップＳ２１２へと処理を移す。処理がステップＳ２１２に移ったときには、符号化対象画像データのすべてのタイルについて符号化処理が終了している。そして、ＲＡＭ１４０２に格納された全タイルの符号化データから、最終的な符号化データを生成して、Ｉ／Ｆ１４０９を解して外部装置へと出力する（符号列形成部１１３、符号出力部１１４の処理に相当）。以上説明したように本変形例によっても、第１の実施形態と同様の作用効果を奏することが可能となるのは明らかであろう。
【００２６】
以上のように、符号化対象となる画像を縮小画像と補間データに分解し、縮小画像を補間データの構造によって可逆符号化か非可逆符号化を切り替える。そして、非可逆符号化選択の場合には、縮小画象を、一旦、元の解像度の画像（初期タイル）に復元してから符号化するにより、高解像度画像の符号化であっても、出来るだけ画質劣化を抑えることができる。
【００２７】
なお、図２に示した処理フローの処理順序は必ずしもこれに限定されるものではなく、処理順序に依存関係が無いもの同士は処理タイミングを入れ替えても良いし、並列にそれら処理を動作させても良いであろう。例えば、１／２縮小タイルデータを生成する処理（ステップＳ２０３）、補間データを生成する処理（ステップＳ２０４）、符号化方式を選択する処理（ステップＳ２０５）などは、補間データの生成を先に行っても良い。また例えば、ステップＳ２０５の符号化方式の決定と同時またはその前に、予めステップＳ２１３における解像度の復元処理を行っても良い。
【００２８】
［第２の実施形態］
上記実施形態では、補間データを用いて元の解像度の画像を復元する際に適用される補間手法の分布に基づいて、縮小画像を可逆符号化するか、非可逆符号化するかを選択した。しかしながら、補間データの符号量などから、補間手法の分布を推定し、その推定結果に基づいて可逆、非可逆符号化のいずれを実行するかを決定するようにしても、同様の効果を得ることができる。そこで、本第２の実施形態として、補間データの符号量に基づいて、符号化方式を選択する手法について説明する。なお、本第２の実施形態でも、対象の画像データは、ＲＧＢ各色８ビットで構成される画像データとするが、ＣＭＹＫカラー画像データなど、他の形式の画像データに適用しても良い。また、画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとし、タイルのサイズＴｗ，Ｔｈは、も第１の実施形態と同じく“３２”であるとする。本第２の実施形態の画像符号化装置の補間データ生成部１１０、符号化方式選択部１１１の処理内容が、第１の実施形態のそれらと異なるだけであり、図１のブロック構成図と基本的に同じであるので、新たに図示はしない。以下、第２の実施形態の処理について、第１の実施形態と動作が異なる補間データ生成部１１０、符号化方式選択部１１１の処理内容について説明する。上述の第１の実施形態では、補間データ生成部１１０における補間データ生成の過程でタイル内の各画素ブロックの種類の頻度分布を示すブロック数Ｎａ乃至Ｎｅを算出し、これを符号化方式選択部１１１へと提供するとした。これに対し、本実施形態においては、補間データ生成部１１０は頻度分布の代わりに、着目タイルについての補間データの符号量Ｌを求め、それを符号化方式選択部１１１へと提供する。符号化方式選択部１１１は補間データ生成部１１０から提供される補間データの符号量Ｌを所定の閾値ＴＨ２と比較する。そしてＬ＜ＴＨ２ならば可逆符号化を適用するよう、制御信号“１”を出力する。また、Ｌ≧ＴＨ２ならば非可逆符号化を適用するよう、制御信号“０”を出力する。１タイルは３２×３２画素であるので、そのデータ量は３２×３２×３（ＲＧＢ成分の数）＝３０７２バイトである。本第２の実施形態では、閾値ＴＨ２は、３０７２バイトの１／８（＝３８４バイト）として説明する。ここで、第１の実施形態の符号化方式選択部１１１の説明で述べた、２×２画素の画素ブロックについての種類（ａ）乃至（ｅ）の５つの種別を考える。これまでの説明から明らかなように、文字、線画、クリップアート画像などで多く出現する種類（ａ）乃至（ｃ）の場合、補間データとして出力される符号長は短い。一方で、複雑なＣＧや自然画像で多く見られる種類（ｄ），（ｅ）の場合には、色の情報をそのまま補間データに含めるためのその符号長は大きくなる。これを別な表現で示すと、注目タイルに種類（ａ）〜（ｃ）のブロックが多く存在する場合には着目タイルの補間データの符号量は少なくなり、逆に種類（ｄ），（ｅ）のブロックが多く含まれる場合には補間データの符号量は多くなる。よって補間データの符号量の量によって第１の実施形態で頻度を参照したのと同様の効果を得ることが可能となる。なお、本実施形態と同等の処理をコンピュータプログラムでもって実現で���ることは、先に説明した第１の実施形態の変形例から明らかであるので、その説明については省略する。
【００２９】
［第３の実施形態］
上記第１、第２の実施形態の画像符号化装置では、符号化対象となる画像データを水平、垂直方向共に１／２に縮小し、これを可逆、または、非可逆符号化の対象とした。しかしながら、１／２の縮小に限らず、より小さい画像を生成してビットマップ符号化の対象としても構わない。本第３の実施形態では、その一例として１／２の縮小処理を再帰的に所定回数実行する。そして１回の縮小処理の生成するたびに、縮小元の画像から補間データを生成する例を説明する。ただし、以下では、説明を簡単なものとするため、再帰処理回数を２回とする具体例を説明する。
【００３０】
図５に本実施形態における画像符号化装置のブロック構成図を示す。第１、第２の実施形態と異なるのは、解像度変換部５０１、１／４縮小タイルバッファ５０２、補間データ生成部５０３が追加された点と、符号化方式選択部１１１が符号化方式選択部５０４に変更された点である。以下、第２の実施形態と動作の異なる部分について説明する。
【００３１】
解像度変換部５０１は、解像度変換部１０５と同様の処理により、１／２縮小タイルバッファ１０６に格納される１／２縮小タイルデータを、更に水平、垂直１／２に縮小し、１／４縮小タイルデータを生成する。そして、この１／４縮小タイルデータを、１／４縮小タイルバッファ５０２へ格納する。
【００３２】
補間データ生成部５０３は、１／４縮小タイルバッファに格納される縮小タイルデータから、１／２縮小タイルバッファに格納される１／２縮小タイルデータを復元するために必要な補間データを生成する。ここでの処理は、補間データ生成部１１０がタイルバッファ１０４に格納されるタイルデータに対して行うのと同様である。以降、補間データ生成部１１０が生成する補間データと補間データ生成部５０３が生成する補間データを区別するため、前者をレベル１補間データと呼び、後者をレベル２補間データと呼ぶ。補間データバッファ１１２にはレベル１補間データとレベル２補間データの両方が格納される。
【００３３】
符号化方式選択部５０４には、補間データ生成部１１０、５０３からそれぞれ、レベル１補間データの符号量Ｌ１とレベル２補間データの符号量Ｌ２が提供される。符号化方式選択部５０４は、入力したＬ１とＬ２の和を所定のしきい値ＴＨ３と比較する。すなわち、Ｌ１＋Ｌ２＜ＴＨ３ならば可逆符号化を適用するよう、制御信号“１”を出力する。一方、Ｌ１＋Ｌ２≧ＴＨ３ならば非可逆符号化を適用するよう、制御信号“０”を出力する。本第３の実施形態では閾値ＴＨ３は、元のタイルデータ量３０７２バイトの１／４、即ち、“７６８”（バイト）とする。
【００３４】
なお、本実施形態の解像度変換部１１６は、１／４縮小タイルデータを、レベル２補間データを用いて解像度変換（１／２縮小タイルデータへ復元）を行い、更に、１／２縮小タイルデータをレベル１補間データを用いて元の解像度（初期タイル）の画像に復元する。
【００３５】
以上によれば、非可逆符号化部１０７では、元の解像度まで変換された画像（初期タイル）を非可逆符号化を行うので、上記実施形態よりも画質の劣化を抑えることができる。なお、本実施形態に相当する処理をコンピュータプログラムでもって実現できることは、先に説明した第１の実施形態の変形例と同様、明らかであるので説明を省略する。また、高度な演算処理を要するビットマップ符号化処理（可逆符号化部１０８による符号化処理）を適用する画素数が元画像データの１／１６にまで限定されているため、上記実施形態よりも処理の負荷が軽減される。
【００３６】
［第４の実施形態］
上述の第２、第３の実施形態では、補間データの符号量から補間手法の構成を推定して、可逆、非可逆符号化を選択する方法を示した。補間手法の構成を推定は、補間データの一部の符号量からでも可能ある。本第４の実施形態としてこのような例について説明する。第４の実施形態は、先に説明した第２の実施形態と基本的に同じであるが、補間データ生成部１１０、符号化方式選択部１１１の動作が若干異なる。以下、動作の異なる部分について説明する。上述の第２の実施形態では、補間データ生成部１１０において、着目するタイルの補間データ量Ｌを符号化方式選択部１１１へと提供した。本第４の実施形態では、第１の実施形態で説明した種類（ａ）乃至（ｅ）の５種のブロックのうち、種類（ｄ）にかかわる補間データの符号量Ｌｄと、種類（ｅ）にかかわる符号量Ｌｅの和を符号化方式選択部１１１へと提供する。ここでは、種類（ｄ）にかかわる補間データとは、図１５の処理フローにおいて、ステップＳ１５１０、Ｓ１５１１で処理がなされるノンフラットブロックについて出力される符号を指す。より具体的に述べるならば、ステップＳ１５１０、１５１１に至るノンフラットブロックについて、ステップＳ１５０４、Ｓ１５０６、Ｓ１５０７、Ｓ１５１０、Ｓ１５１１で出力される符号である。また種類（ｅ）にかかわる補間データとは、同図、ステップＳ１５１２、Ｓ１５１３で処理がなされるノンフラットブロックについて出力される符号を指す。これは、ステップＳ１５１２、１５１３に至るノンフラットブロックについて、ステップＳ１５０４、Ｓ１５１２、Ｓ１５１３で出力される符号である。符号化方式選択部１１１は補間データ生成部１１０から提供される補間データの符号量Ｌｄ＋Ｌｅを所定のしきい値ＴＨ４と比較する。Ｌｄ＋Ｌｅ＜ＴＨ４ならば可逆符号化を適用するよう制御信号“１”を出力し、Ｌｄ＋Ｌｅ≧ＴＨ４ならば非可逆符号化を適用するよう、制御信号“０”を出力する。複雑なＣＧや自然画では、ＬｄとＬｅの和が大きくなる傾向にあり、非可逆符号化の歪が目に付きにくく、元の解像度に戻すときにも縮小画像の劣化の影響を受けにくい。よって、本実施形態においても、高画質、高圧縮、簡易・高速という効果を得ることができる。
【００３７】
［第５の実施形態］
前記第１の実施形態では、非可逆符号化方式を選択した場合には、補間データから元の解像度の画像に復元して、非可逆符号化処理を行うことを説明した。本実施の形態では、非可逆符号化処理を選択した場合に、補間データから元の解像度画像（初期タイル）に復元するかしないかを選択することで、非可逆符号化処理を行う画素数を減らすことが可能になり、軽い処理を実現することも可能である。そこで、非可逆符号化の前に解像度を復元するかしないかを制御する方法に関して説明する。
【００３８】
図１７は、第５の実施形態における画像符号化装置のブロック構成図を示す。第１の実施形態と異なるのは、解像度変換選択部１７０１が追加された点である。以下、第１の実施形態と動作の異なる部分について説明する。解像度変換選択部１７０１では、元の解像度に復元して非可逆符号化処理を行うか、１／２縮小タイルで非可逆符号化処理を行うかを選択する処理である。元の解像度に復元するかしないかの判断は、非可逆符号化処理する際のパラメータに基づいて決定する。ここでのパラメータとは、例えば、ＪＰＥＧの場合、量子化ステップ、量子化テーブルと呼ばれる、離散コサイン変換した係数を除算するところで用いるものである。ここでは、非可逆符号化部１０７がＪＰＥＧ符号化を実行する場合を例に説明する。以下の例では、ＪＰＥＧ符号化で用いる量子化ステップが上記パラメータに相当する。
【００３９】
例えば、非可逆符号化部１０７によるＪＰＥＧ符号化で適用される量子化ステップが細かいものであれば、元の解像度に復元する処理は行わない。一方、そこで適用される量子化ステップが粗いものであれば、元の解像度に復元する処理を行う。これにより、ＪＰＥＧ符号化における量子化において大きな画質劣化が生じそうな場合には、符号化の前段で元の解像度に復元することで全体的な画質劣化を抑制できる。
【００４０】
また例えば、非可逆符号化部１０７によるＪＰＥＧ符号化で適用される量子化ステップが粗いものであれば、元の解像度の画像に復元する処理は行わない。一方、そこで適用される量子化ステップが細かいものであれば、元の解像度の画像に復元する処理を行う。これにより、ＪＰＥＧ符号化における量子化において画質劣化を抑えたいタイルについては、符号化の前段で元の解像度の画像（初期タイル）に復元することで、よりよい画質で符号化することができる。
【００４１】
なお、上記量子化ステップが細かいか粗いのかの判断としては、例えば、量子化ステップ全ての値の平均値が閾値（例えば２０）以下であれば細かく、閾値を超えるものが粗いと判断する。あるいは、量子化ステップのすべての値の最大値が閾値（例えば２０）以下であれば、量子化ステップは細かいと判断し、閾値を超えるものは粗いと判断すれば良い。なお、上記閾値はユーザが任意に設定可能である。
【００４２】
以上では、ＪＰＥＧ符号化を例にあげて説明したが、ＪＰＥＧ２０００やＪＰＥＧＸＲなどの符号化方式でも圧縮率あるいは画質に影響する符号化パラメータが各種存在している。よって、それら符号化パラメータを基準にして、非可逆符号化の前に解像度を復元するか否かを判断することは有効である。
【００４３】
［第６の実施形態］
上記第３の実施形態では、非可逆符号化方式を選択した場合には、レベル１補間データとレベル２補間データを用いて、縮小画象（１／４縮小タイルデータ）を元の解像度の画像にまで復元して、非可逆符号化処理を行っていた。本実施の形態では、非可逆符号化処理を行う前に、以下の３つの選択肢から処理を選択する。
「非可逆符号化の対象画像を、１／４縮小タイルデータとする（解像度を復元しない）」
「非可逆符号化の対象画像を、１／２縮小タイルデータとする（解像度を１段階復元する）」「非可逆符号化の対象画像を、元の解像度の画像とする（解像度を２段階復元する）」
【００４４】
図１８は、第５の実施形態における画像符号化装置のブロック構成図を示す。第３の実施形態でのブロック図と異なるのは、解像度変換選択部１８０１が追加された点と、解像度変換部１８０２が変更になった点である。以下、第３の実施形態と動作の異なる部分について説明する。解像度変換選択部１８０１では、上述した３つの選択肢の１つを選択する処理である。本実施形態では、上記選択は、非可逆符号化処理する際のパラメータに基づいて行われる。ここでのパラメータとは、第５実施形態で述べたものと同様である。以下、ＪＰＥＧ符号化を行う場合であって、上記パラメータを量子化ステップとして例示する。本実施形態では、量子化ステップの細かさを予め３つの範囲（値域）に分けておく。量子化ステップの１番細かい範囲、２番目に細かい範囲、３番目に細かい範囲と徐々に量子化ステップが粗くなっていくように、量子化ステップに相当するパラメータの値域を予め設定しておく。
【００４５】
例えば、非可逆符号化部１０７によるＪＰＥＧ符号化で適用される量子化ステップが１番細かい範囲に相当するものであれば、高解像度の画像に復元する処理は行わない。一方、そこで適用される量子化ステップが２番目に細かい範囲に相当するものであれば、解像度を１段階復元する。一方、そこで適用される量子化ステップが３番目に細かいものであれば、解像度を２段階復元する。これにより、ＪＰＥＧ符号化における量子化において画質劣化が生じそうな場合には、符号化の前段で、１／２縮小タイルデータあるいは元の解像度の画像（初期タイル）に復元することで全体的な画質劣化を抑制できる。
【００４６】
なお、第５実施形態で述べた変形例と同様、非可逆符号化部１０７による量子化ステップが３番目に細かい時、高解像度の画像に復元する処理は行わず、量子化ステップが１番、２番目に細かい時、１／２縮小タイルデータや元の解像度の画像に復元しても良い。これにより、ＪＰＥＧ符号化における量子化において画質劣化を抑えたいタイルについては、符号化の前段で高解像度の画像に復元することで、よりよい画質で符号化することができる。また、第５実施形態と同様に、上記量子化ステップの細かさの判断方法や閾値などはユーザが任意に設定可能である。また、ＪＰＥＧ２０００やＪＰＥＧＸＲなどの符号化方式の場合に適用しても良い。
【００４７】
［符号化データの構造］
図６は、上記各実施形態において生成される１タイル分の符号化データの構造を示したものである。よって、複数のタイルを符号化する場合には、後述するように、図６の符号化データがタイルの数だけ連結されることになる。図６（ａ）は、１／４縮小タイルを可逆符号化することになった場合の符号化データ構造である。ここでは、１／４縮小タイル符号化データとレベル２補間データとレベル１補間データが含まれる。図６（ｂ）は、１／２縮小タイルを非可逆符号化することになった場合、あるいは１／２縮小タイルを可逆符号化することになった場合の符号化データ構造である。ここでは、１／２縮小タイル符号化データとレベル１補間データが含まれ、レベル２補間データは含まれない。図６（ｃ）は、元の解像度の画像（初期タイル）を非可逆符号化することになった場合の符号化データ構造である。ここでは、タイルの符号化データが含まれ、レベル１補間データとレベル２補間データは含まれない。
【００４８】
図９は、複数のタイルを符号化した場合の符号化データ構造を示す図である。符号列の先頭には、画像を復号するために必要となる情報、例えば、画像の水平方向画素数、垂直方向画素数、コンポーネント数、各コンポーネントのビット数やタイルの幅、高さなどの付加情報がヘッダとして付与される。また、このヘッダ部分には、画像データそのものについての情報のみでなく、各タイルに使用するハフマン符号化テーブルや、量子化テーブルなどの符号化に関する情報も含まれる。このヘッダに続いて、上述した各タイルの符号化データが連結される。
【００４９】
［その他の実施形態］
上記各実施形態では可逆符号化としてＪＰＥＧ−ＬＳ、非可逆符号化としてＪＰＥＧを利用するとして説明したが、それぞれが、同様の性質を有する別の符号化手法を適用しても構わない。また、上記各実施形態では、１／２縮小画像を生成する際、２×２画素の画素ブロック内の左上隅に位置する画素Ｂｎ（０，０）を縮小画像の画素としてサンプリングし、他の３画素Ｂｎ（１，０）、Ｂｎ（０，１）、Ｂｎ（１，１）の補間データの生成を行った。しかし、縮小画像の利用する画素は必ずしも２×２画素のブロックの左上隅の画素でなくても構わず、Ｂｎ（１，０）、Ｂｎ（０，１）、Ｂｎ（１，１）のいずれであっても構わない。要するに、Ｂｎ（１，０）、Ｂｎ（０，１）、Ｂｎ（１，１）のいずれか１つをサンプリング対象の画素Ｘとした場合であっても、残りの３画素がＸａ，Ｘｂ，Ｘｃと定義できる。この場合、以下の様に、
Ｘ１：画素Ｘａを復元するために参照する隣接画素ブロック内の前記画素Ｘａに隣接するサンプリング対象となる画素
Ｘ２：画素Ｘｂを復元するために参照する隣接ブロック内の前記画素Ｘｂに隣接するサンプリング対象となる画素
Ｘ３：画素Ｘｃを復元するために参照する隣接ブロック内の前記画素Ｘｃに隣接するサンプリング対象となる画素を
と定義したとき、「Ｘａ＝Ｘ１  且つ、Ｘｂ＝Ｘ２  且つ、Ｘｃ＝Ｘ３」を満たす場合に、その着目画素ブロックは周囲３画素一致ブロックと判定すればよい。また、画素ブロックのサイズは３×３画素とし、その中から１画素を抽出することで、水平、垂直ともオリジナルの１／３の画素数の縮小画像を生成しても構わない。また、画素ブロック中の１画素を抽出するだけでなく、その画素ブロックの平均色を求めて縮小画像を生成するなどしても良い。このような場合、縮小画像の生成方法に応じて、元の解像度の画像データを復元できるように補間データの構成方法を工夫すれば良い。また、補間データの構成方法として、元の解像度の画像データが完全に元に戻せるような構成例について示したが、必ずしもこれに限らない。例えば、画素ブロックに含める色数が３色以上である場合には、減色するなどして、元の解像度には戻るものの、画素値としては多少変化することを許容するような補間データとしても良い。また、上述の実施形態では３２×３２画素のタイルに分割して処理を行ったがタイルの大きさはこれに限定されるものではなく、画素ブロックの整数倍であれば良い。従って。１６×１６、６４×６４、１２８ｘ１２８など、別のブロックサイズとしても良いし、正方である必要もない。また、実施形態では、画像の色空間はＲＧＢであるとしたが、ＣＭＹＫ、Ｌａｂ、ＹＣｒＣｂなど様々なタイプの画像データに適用可能であるのは明らかであるので、色成分の数や色空間の種類によって本発明が限定されるものではない。また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータの読取り装置（ＣＤ−ＲＯＭドライブ）にセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、このようなコンピュータ可読記憶媒体も本発明の範疇に入ることも明らかである。
【図１】
0005538985.tif 000002
【図２】
0005538985.tif 000003
【図３】
0005538985.tif 000004
【図４】
0005538985.tif 000005
【図５】
0005538985.tif 000006
【図６】
0005538985.tif 000007
【図７】
0005538985.tif 000008
【図８】
0005538985.tif 000009
【図９】
0005538985.tif 000010
【図１０】
0005538985.tif 000011
【図１１】
0005538985.tif 000012
【図１２】
0005538985.tif 000013
【図１３】
0005538985.tif 000014
【図１４】
0005538985.tif 000015
【図１５】
0005538985.tif 000016
【図１６】
0005538985.tif 000017
【図１７】
0005538985.tif 000018
【図１８】
0005538985.tif 000019