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