画像符号化装置及び画像復号装置及びそれらの制御方法
【課題】 文字、線画、ＣＧ画像など、同一画素値の連続、または、同一パターンの連続を多く含む画像に対して高い圧縮率で符号化データを生成する。
【解決手段】 ブロック符号化部１０４は、初期の３２×３２画素のブロック内の全画素が同じ色であるか否かを判定し、同じ色であれば同一色であることを示す符号語とその色の情報を付加して出力する。また、同一色でない場合には、着目ブロックを複数のサブブロックに分割し、各サブブロックそれぞれを着目ブロックとして、同一色の判定、同一色のブロックがない場合には同一ブロックの判定を行なう。そして、この判定を着目ブロックのサイズが下限サイズである４×４画素ブロックになるまで行なう。着目ブロックのサイズが下限サイズとなり、尚且つ、着目ブロック内の全画素が同一色でなく、且つ、着目ブロックと同一のブロックが存在しない場合、着目ブロックをラスタースキャンし、予測誤差符号化を行なう。
【解決手段】 ブロック符号化部１０４は、初期の３２×３２画素のブロック内の全画素が同じ色であるか否かを判定し、同じ色であれば同一色であることを示す符号語とその色の情報を付加して出力する。また、同一色でない場合には、着目ブロックを複数のサブブロックに分割し、各サブブロックそれぞれを着目ブロックとして、同一色の判定、同一色のブロックがない場合には同一ブロックの判定を行なう。そして、この判定を着目ブロックのサイズが下限サイズである４×４画素ブロックになるまで行なう。着目ブロックのサイズが下限サイズとなり、尚且つ、着目ブロック内の全画素が同一色でなく、且つ、着目ブロックと同一のブロックが存在しない場合、着目ブロックをラスタースキャンし、予測誤差符号化を行なう。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の符号化及び復号技術に関するものである。
【背景技術】
【０００２】
従来、画像の符号化、復号を行う画像処理装置を構成する一手法として予測符号化をベースとするものがある。予測符号化は、画像データを予測変換により予測誤差へと変換する系列変換部と、系列変換部から出力される予測誤差をハフマン符号化等のエントロピー符号化を用いて、より冗長性の少ない符号化データへと変換するエントロピー符号化部とによって構成される。
【０００３】
ＩＳＯとＩＴＵ−Ｔから国際標準の静止画像符号化方式として勧告されるＪＰＥＧではＬｏｓｓｌｅｓｓ Processとして予測符号化をベースとした可逆符号化方式が規定されている（非特許文献１）。以下、これをＪＰＥＧ可逆符号化モードと呼ぶ。
【０００４】
ＪＰＥＧ可逆符号化モードでは、近傍画素から着目画素の値を予測する方法として７つの予測式を規定しており、画像に応じて予測方法を選択できるようになっている。ＪＰＥＧ可逆モードでは符号化対象の画像データをラスタースキャン順に符号化する。各画素を定められた予測方式により予測し、その予測誤差をハフマン符号、または算術符号により順次符号化していく。ハフマン符号化を用いる場合には予測誤差の１つに対して１ビット以上が出力されるため、文字、線画、ＣＧ画像など人工的で、同一画素や同一パターンの連続が多く見られる画像に対しては高い圧縮性能を得ることができない。
【０００５】
一方、ＪＰＥＧ標準化の後、ＩＳＯとＩＴＵ−Ｔから新たに国際標準勧告された可逆符号化方式ＪＰＥＧ−ＬＳ Ｂａｓｅｌｉｎｅ（非特許文献２）では、予測符号化とランレングス符号化とを組み合わせて符号化システムが勧告されている。これは、周囲画素の状態によって予測方法、確率モデルを変えるなどの工夫により、自然画像での圧縮性能を向上するものである。すなわち、ランレングス符号化の採用により、複数画素を一纏めにして符号化することができ、上述のような文字、線画、ＣＧ画像などに対しても、ＪＰＥＧ可逆符号化モードよりも高い符号化性能を得ることができる。
【非特許文献１】ＩＴＵ−Ｔ Ｔ．８１｜ＩＳＯ／ＩＥＣ１０９１８−１
【非特許文献２】ＩＴＵ−Ｔ Ｔ．８７｜ＩＳＯ／ＩＥＣ１４４９５−１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述のＪＰＥＧ−ＬＳを用いた従来の装置では、水平方向に同じ値を持つ画素が連続する場合には効率良く圧縮きるが、垂直方向に同じ値を持つ画素が連続する場合にはランレングス符号化が適用されず、効率良く圧縮できない。
【０００７】
また、同じパターンの繰り返しがある場合、画像の構成自体は単純であっても、効率良い圧縮性能を得ることはできない。
【０００８】
本願発明は、上述の問題点に鑑みてなされたものであり、文字、線画、ＣＧ画像など、同一画素値や同一パターンの連続の多い画像に対しても効率良く符号化する技術、および復号する技術を提供しようとするものである。
【課題を解決するための手段】
【０００９】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像データを符号化する画像符号化装置であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力手段と、
着目ブロックの画像データの全画素が同一色である否かを判定し、同一色である場合には同一色であることを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックの画像データが非同一色の画素を含んでいると判定した場合には非同一色を示す符号化データを出力する第１の符号化手段と、
該第１の符号化手段で出力される符号化データが、前記非同一色を示している場合、前記着目ブロックの画像データと同じ画像データが、既に符号化処理された画像データ領域内に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す情報を符号化データとして出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第２の符号化手段と、
該第２の符号化手段で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段と、
該判定手段で前記着目ブロックのサイズが、前記下限サイズであると判定した場合、当該着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化手段と、
前記判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記入力手段に設定し、前記第１、第２の符号化手段による符号化を再帰的に実行する制御手段とを備える。
【発明の効果】
【００１０】
本発明の構成によれば、文字、線画、ＣＧ画像など、同一画素値の連続、または、同一パターンの連続を多く含む画像に対して高い圧縮率で符号化データを生成することができる。
【発明を実施するための最良の形態】
【００１１】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００１２】
＜第１の実施形態＞
図１は本実施形態に係る画像符号化装置のブロック構成図である。
【００１３】
本実施形態の画像符号化装置は、画像入力部１０１、ストライプバッファ１０２、ブロック切り出し部１０３、ブロック符号化部１０４、符号列形成部１０５、符号出力部１０６、ブロック情報管理メモリ１０７、装置全体の制御を司る制御部１１０を備える。
【００１４】
以下、図１を参照して、本実施形態の画像符号化装置の各構成要素とその処理内容を説明する。
【００１５】
本実施形態に係る画像符号化装置の符号化対象とする画像データは、Ｒ、Ｇ、Ｂの３つのコンポーネント（成分）で構成されるカラー画像データとする。１画素を構成する各コンポーネントは、８ビット（２５６階調）とする。符号化対象の画像データの並びは点順次、即ち、ラスタースキャン順に各画素が並べられており、各画素のコンポーネントはＲ，Ｇ，Ｂ順に並べられて構成されるものとする。すなわち、Ｒ、Ｇ、Ｂ、Ｒ、Ｇ、Ｂ…のデータの並びで構成されているものとする。また、説明を簡単なものとするため、実施形態では、符号化対象の画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。また、実施形態における画像符号化装置は、符号化対象画像データから水平方向Ｂｗ画素、垂直方向Ｂｈ画素のブロックに分割してブロック単位に符号化を行う。ブロックのサイズＢｗ、Ｂｈは様々な値とすることができるが、以下の説明ではＢｗ＝Ｂｈ＝３２として説明する。また、説明を簡易にするため、画像の水平方向画素数Ｗ、垂直方向画素数Ｈは、それぞれ３２の整数倍の大きさであるとし、ブロックに分割した場合に不完全なブロックは発生しないものとして説明する。
【００１６】
さて、画像入力部１０１は、符号化対象の画像データをラスタースキャンし、Ｂｈ個のライン（３２ライン分）の画像データを入力し、ストライプバッファ１０２に出力（格納）する。１ラインはＷ画素で構成されるので、画像入力部１０１はＢｈ×Ｗ画素分の画像データをストライプバッファ１０２に格納することになる。１画素は３バイトで表現されるので、結局のところ、ストライプバッファ１０２は、最低でも、３２×Ｗ×３バイトの容量を備えることになる。以降、このストライプバッファ１０２に格納されるＢｈライン分の画像データをストライプデータと呼ぶ。
【００１７】
ストライプバッファ１０２に３２ライン分の画像データ（ストライプデータ）が格納されたとする。この場合、ブロック切り出し部１０３はストライプバッファ１０２に格納されるストライプデータについて、左端から右端に向かって、高さＢｈ、幅Ｂｗのブロックの画像データ（３２×３２画素）を順に切り出して、内部の不図示の記憶領域に格納する。この３２×３２画素のサイズは、後述する説明から明らかになるように、最大サイズでもある。
【００１８】
ブロック情報管理メモリ１０７は、ブロック符号化部１０４におけるブロックデータの符号化の過程で必要となるブロック情報を管理するための記憶領域を有する。この記憶領域には、図２（ａ）乃至（ｄ）に示すようにブロックサイズ“３２”，“１６”，“８”，“４”のそれぞれについてブロック管理テーブルが確保される。なお、ここで言うブロックサイズ“３２”とは、３２×３２の正方ブロックの１辺の長さを示しているものである点に注意されたい。これは、他のブロックサイズも同様である。
【００１９】
各ブロックサイズ毎のブロック管理テーブルのエントリ数はそれぞれに異なる。ブロックサイズ“３２”のブロック管理テーブルのエントリ数は１つ、ブロックサイズ“１６”のエントリ数は最大で４つ、ブロックサイズ“８”のエントリ数は最大で１６、ブロックサイズ“４”のエントリ数は最大で６４である。これは、３２×３２画素のブロックは、４つの１６×１６画素のブロック、または、１６個の８×８画素のブロック、又は、６４個の４×４画素のブロックに対応するためである。
【００２０】
以降の説明では、現在着目するブロックサイズと同じブロックサイズのブロック管理テーブルを、着目ブロックリストと呼び、その１／２の大きさのブロックサイズのブロック管理テーブルをサブブロックリストと呼ぶ。また、ブロック管理テーブルに格納される情報については後述する。
【００２１】
ブロック符号化部１０４は、ブロック切り出し部の内部に格納される３２×３２画素のブロックデータ（以降、初期ブロックと呼ぶ）を符号化する度に、ブロック情報管理メモリ１０７内の各サイズ別のブロックリストを初期化する。そして、ブロック符号化部１０４は、符号化過程でブロックリストの登録と、その登録したブロックリストを参照しながら、符号化データを生成し、出力する。
【００２２】
図３はブロック符号化部１０４における符号化処理の流れを示すフローチャートである。以下、同図を参照して、ブロック符号化部１０４によるブロックデータの符号化処理の全体的な流れについて説明する。
【００２３】
ブロック符号化部１０４はその内部に、着目ブロックの大きさ（水平／垂直方向画素数）を保持する変数ＳＩＺＥと、着目ブロックの左上隅の座標（以降、始点座標と呼ぶ）ベクトルＢを備える。着目ブロックは、このＳＩＺＥと始点座標のベクトルＢの組で特定する。始点座標は初期ブロック（符号化単位となる３２×３２のブロック）の左上隅を原点（０，０）として、水平方向ｘ画素、垂直方向ｙ画素の位置をベクトル（ｘ、ｙ）で表現する。
【００２４】
図４に示した太線の矩形は初期ブロックであり、このブロックの始点座標はＢ＝（０，０）、大きさＳＩＺＥ＝３２である。また、これを４分割して得られる斜線領域を着目ブロックとする場合、その始点座標Ｂ＝（１６，０）であり、ＳＩＺＥ＝１６となる。
【００２５】
符号化の開始時には、先ず、ステップＳ１０００にて、変数ＳＩＺＥに“３２”を設定する。次いで、ステップＳ１００１において、変数Ｎｍａｘに“１”を設定する。この変数Ｎｍａｘは、変数ＳＩＺＥで示されるエントリ数を格納するためのものである。ＳＩＺＥ＝３２の場合、エントリ数は“１”であるため、ステップＳ１００１では変数ＳＩＺＥに“１”を設定することになる。
【００２６】
次に、ステップＳ１００２にて、ブロック情報管理メモリ１０７に、ＳＩＺＥ＝３２のブロックリスト（エントリ数＝１）を登録する。次いで、ステップＳ１００３にて、変数ｉに初期値として“０”を設定し、ステップＳ１００４にて、着目ブロックから派生するサブブロックのエントリ数を格納する変数ＳＵＢｉを“０”で初期化する。
【００２７】
ステップＳ１００５では、ブロック切り出し部１００３から、変数ＳＩＺＥで示される第ｉ番目のブロック（着目ブロック）を入力し、着目ブロック内の全画素が同一色を示しているか否かを判定する。換言すれば、着目ブロック内の色数が“１”である否かを判定すると言い換えても良い。なお、ここでは、全画素が同一色であるか否かを判断するものであるから、ブロック内をスキャンして、着目画素の色と直前の画素の色が異なった場合には、少なくとも２色以上存在することを示しているので、それ以降のスキャンは不要である。同一色（色数が“１”）である場合には二進データ“１”、非同一色（色数が“２”以上）である場合には二進データ“０”を出力する（ステップＳ１００６）。
【００２８】
この後、ステップＳ１００７にて、変数ｉで示される着目ブロックの全画素が同一色（色数が“１”）であったか否か、すなわち、ステップＳ１００６で出力した二進データが“１”であったか否かを判定する。同一色（色数が“１”）であった場合には、ステップＳ１００８に進み、その色を示す画素データ（Ｒ、Ｇ、Ｂ値）を出力し、着目ブロックの処理を終えるため、ステップＳ１０１８に処理を進める。
【００２９】
つまり、着目ブロック内の全画素が同一色を示している場合、ステップＳ１００６、及び、ステップＳ１００８によって生成される着目ブロックの符号化データは、
“１”＋Ｒ、Ｇ、Ｂデータ（各８ビット）
のデータ構造（計２５ビット）となる。
【００３０】
一方、ステップＳ１００７にて、着目ブロック内の色数が“２”以上であると判定した場合、処理をステップＳ１００９に進める。このステップＳ１００９では、変数ｉの値が“０”であるか否か、すなわち、着目ブロックが着目ブロックリストに登録した先頭ブロックであるか否かを判断する。
【００３１】
着目ブロックが登録したブロックリストの先頭ブロックである場合には比較対象が存在しないので、処理はステップＳ１０１４に進める。
【００３２】
ここで、変数ｉが“０”以外である場合に、すなわち、着目ブロックは、変数ＳＩＺＥで定義されるブロックリストの２番目以降のブロックであるものとして説明する。この場合、ステップＳ１０１０にて、着目ブロックリストに登録された符号化処理済みのブロック（１つ又は複数）と着目ブロックとの比較処理を行ない、その結果をステップＳ１０１１にて出力する。
【００３３】
例えば、着目ブロックリストが図５のような状態にあり、変数ｉ＝３、すなわち、着目ブロックがブロック番号「３」であったとする。この場合、ブロック番号「２」、「１」、「０」の順番（降順）で着目ブロックと同一ブロックか否かを判定する。
【００３４】
ここで仮に、着目ブロックが、ブロック番号「２」のブロックとは同一でないが、ブロック番号「１」と同一であったとする。この場合には、先ず、着目ブロックと同一のブロックが存在したことを示す二進データ“１”を出力する。また、ブロック番号「２」、「１」、「０」の順番に、画像領域における既に符号化処理済みブロックと着目ブロックとを比較し、いずれとも一致しなかった場合には、同一ブロック無し（非存在）を示す二進データ“０”を出力する。
【００３５】
ここまでの処理により出力されるデータを２分木構造にして示したのが図６（ａ），（ｂ）である。
【００３６】
着目ブロックが変数ＳＩＺＥで示されるブロックリストの先頭にあるとき、図６（ａ）に従い、着目ブロック内の全画素が同一色（色数が“１”）を示すか否かの判定結果を出力する。特に、同一色である場合には、この判定結果に後続して同一色となった画素の各成分値を出力する。
【００３７】
また、着目ブロックが変数ＳＩＺＥで示されるブロックリストの２番目以降の場合、図６（ｂ）に従い、着目ブロック内の全画素が同一色を示すか否かの判定結果を出力する。特に、同一色（色数が“１”）である場合には、この判定結果に後続して同一色となった画素の各成分値を出力するのは、図６（ａ）と同様である。また、非同一色（色数が“２”以上）である場合には、先ず、二進データ“０”を出力した後、既に処理済みのブロック内に着目ブロックと同一のブロックが存在するかを示す二進データ“０”か“１”かのいずれか一方を出力する。
【００３８】
さて、ステップＳ１０１２に処理が進むと、着目ブロックと同一ブロックが処理済みブロック内に存在したか否か、すなわち、ステップＳ１０１１での出力が“１”であったか否かを判定する。着目ブロックと同一ブロックが処理済みブロック内に存在したと判断した場合には、ステップＳ１０１３に進み、同一であると判定したブロック番号を特定する情報を出力し、ステップＳ１０１８９進む。
【００３９】
このステップＳ１０１３の処理内容を図７の符号木を用いて説明する。図中、変数ｉは着目ブロックリストにおける着目ブロックの番号を表している。図に示すように、符号木は着目ブロックの番号ｉによって変化し、ブロック番号ｉの場合にはｉ個のリーフノードを持つ符号木が用いられる。着目ブロック番号を「ｉ」とし、それに一致するブロック番が仮に「ｊ」（０≦ｊ＜ｉ）であるとした場合、「ｉ−ｊ−１」個の“０”を出力し、その後に“１”を出力する。
【００４０】
例えば、図５におけるブロック番号「３」が着目ブロックであり、その着目ブロックと同一のブロックのブロック番号が「１」であるとする。この場合、ステップＳ１０１３で出力する二進データは“０１”となる。ステップＳ１００６で二進データ“０”、ステップＳ１０１１にて二進データ“１”を出力しているわけであるから、着目ブロックの符号化データは、結局のところ、二進データ“０１０１”となる。
【００４１】
つまり、着目ブロック内の色数が２以上であり、尚且つ、着目ブロックと同一のブロックが存在する場合、着目ブロックの符号化データは、
“０１”＋同一ブロックを特定するデータ
のデータ構造となる。ここで、「同一ブロックを特定するデータ」は、０個以上の“０”＋“１”のデータである。
【００４２】
また、ステップＳ１００９にて、変数ｉが“０”である場合には、着目ブロックはブロックリストの先頭ブロックであるので、比較対象の処理済みブロックは存在しない。そのため、ステップＳ１０１４にて、一致するブロックが存在しないことを示す“０”を出力し、ステップＳ１０１５に処理を進める。
【００４３】
このステップＳ１０１５に処理が進んだ場合、ステップＳ１００６で二進データ“０”が出力され、ステップＳ１０１１又はステップＳ１０１４で二進データ“０”が出力された場合である。すなわち、ステップＳ１０１５に処理が進むのは、着目ブロック内の色数が２以上であり、尚且つ、着目ブロックと同一のブロックが存在しない場合となる点に注意されたい。
【００４４】
ステップＳ１０１５では、変数ＳＩＺＥが“４”であるか否か、すなわち、着目ブロックリストがＳＩＺＥ＝４のブロックリストであるか否かを判断する。これは、着目ブロックが処理の下限サイズであるか否かを判断しているとも言える。
【００４５】
変数ＳＩＺＥが“４”以外（ＳＩＺＥが８、１６、３２のいずれか）であると判断した場合には、着目ブロックは下限サイズよりも大きいことになる。そこで、ステップＳ１０１６にて、着目ブロックを構成する４つのサブブロックを、ＳＩＺＥ／２で示されるブロックリストに登録する。また、ステップＳ１０１７にて、サブブロックの個数を更新するため、変数ＳＵＢｉを“４”だけ増加させる。そして、ステップＳ１０１９に処理を進める。
【００４６】
例えば、図８に示すごとく、サイズＳＩＺＥ＝Ｌの着目ブロックの始点座標をＢ=（ｂｘ、ｂｙ）としたとき、その着目ブロックを構成する４つのサブブロックの各始点座標Ｂ０〜Ｂ３は次のように定義できる。
Ｂ０＝（ｂｘ、ｂｙ）
Ｂ１＝（ｂｘ＋Ｌ／２、ｂｙ）
Ｂ２＝（ｂｘ、ｂｙ＋Ｌ／２）
Ｂ３＝（ｂｘ＋Ｌ／２、ｂｙ＋Ｌ／２）
これらブロックを、ＳＩＺＥ／２で示されるブロックリストに追加登録する。なお、登録する４つのサブブロックのサイズは、着目ブロックのサイズの水平、垂直方向の画素数の１／２である。また、このサブブロックを登録する以前に、既にいくつかのサブブロックが登録されている場合には、今回登録するサブブロック番号は、最後に登録したブロック番号＋１から割り当てる。
【００４７】
また、ステップＳ１０１５にて、変数ＳＩＺＥが“４”であると判断した場合、すなわち、着目ブロックのサイズが下限サイズであると判断した場合、ステップＳ１１０８に進める。このステップＳ１０１８では、着目ブロック内の各画素データの符号化処理を行ない、その符号化データを出力する。そして、ステップＳ１０１９に処理を進める。
【００４８】
ブロック内の画素の符号化方法としては予測符号化、変換符号化など様々な手法を用いて良い。本実施の形態ではその一例として簡易な予測符号化を用いる方法を示す。以下は、その予測符号化処理の説明である。
【００４９】
まず、着目ブロック（４×４画素のサイズである）内（もしくは着目サブブロック内）の左上隅の画素の成分値をそのまま出力する。その後、着目ブロック内をラスタースキャンしていく。この過程での着目画素の色成分と、前置予測値（前符号化画素の同一成分値）との差分を予測誤差ｅとして算出し、その予測誤差ｅを符号化する。予測誤差ｅはＪＰＥＧ可逆符号化モードと同様に、まず、図９から予測誤差ｅの属するカテゴリＳＳＳＳを得て、これを図１０のハフマンテーブルで符号化する。続いて、カテゴリの中のどの値かを特定するための長さＳＳＳＳビットの付加ビットを出力する。予測誤差ｅが正である場合、付加ビットは予測誤差ｅの下位ＳＳＳＳビットであり、負である場合には予測誤差ｅ−１の下位ＳＳＳＳビットを取り出したものである。以上のようにして、着目ブロック内の各画素の符号化が行われる。
【００５０】
つまり、着目ブロック内の色数が“２”以上であり、着目ブロックと同一のブロックが存在せず、尚且つ、着目ブロックが下限サイズである場合の着目ブロックの符号化データは、
“００”＋予測誤差符号化データ
のデータ構造となる。
【００５１】
さて、処理がステップＳ１０１９に処理が進むと、着目ブロックを次のブロックに更新するあめ、変数ｉを“１”だけ増加する。そして、ステップＳ１０２０にて、変数ｉと変数Ｎｍａｘとを比較する。ｉ＜Ｎｍａｘである場合、着目ブロックリスト中に、未処理のブロックが存在することになるので、ステップＳ１００５以降の処理を行なう。なお、ＳＩＺＥ＝３２の場合、Ｎｍａｘ＝１であるので、ステップＳ１０２０の判定は必ず「Ｎｏ」となり、ステップＳ１０２１に処理が進む。
【００５２】
ステップＳ１０２１では、登録したサブブロックの個数ＳＵＢｉが“０”よりも多いか否かを判断する。ＳＵＢｉ＝０であると判断した場合、処理すべきサブブロックが存在しないことになるので、本処理を終える。
【００５３】
また、少なくとも１つのサブブロック（実際は４の整数倍）が登録されていると判断した場合、処理はステップＳ１０２２に進み、そのサブブロックの処理を行なうため、変数ＳＩＺＥを１／２に設定する。すなわち、変更後の変数ＳＩＺＥで示されるブロックリストを着目ブロックリストとして設定する。そして、ステップＳ１０２３にて、エントリの上限をＳＵＢｉとするため、変数ＮｍａｘにＳＵＢｉを代入し、ステップＳ１００３以降の処理を行なう。
【００５４】
以上、説明した処理により、ブロック符号化部１０４において、ブロック切り出し部１０３の内部に保持される初期ブロックの符号化が行われ、ブロックの符号化データが符号列形成部１０５へと出力される。
【００５５】
符号列形成部１０５は画像の水平方向／垂直方向の画素数、画素を構成する成分の数、各成分の精度など、画像の復号に必要な付加情報を有するヘッダを先ず生成する。そして、符号列形成部１０５は、ブロック符号化部１０４から出力される符号化データをヘッダに後続するデータとして、所定のフォーマットの符号列を形成し、符号出力部１０６に出力する。図１１に符号列形成部１０５から出力される符号列の構成の一例を示す。先頭のＨｅａｄｅｒ部分に付加情報が格納され、続いてラスタースキャン順の各ブロックの符号化データが並ぶ。符号出力部１０６は符号列形成部１０５から出力される符号列を装置外部へと出力を行う。
【００５６】
ここで、上記の符号化処理をより分かりやすく説明する。
【００５７】
説明を簡単なものとするため、３２×３２画素の初期ブロックの画像が図１２のようになっているものとする。また、ブロック情報管理メモリ１０７にブロックリストとして登録する各ブロックをＢＬＫ（ＳＩＺＥ，ブロック番号）として表現することとする。
【００５８】
ここで３２×３２画素中、右上隅の幅４画素、高さ１６画素の領域以外の領域（白色領域）では、全て同一色であるものとする。また、右上隅の幅４画素、高さ１６画素の領域中のブロックＢＬＫ（４，１）、ＢＬＫ（４，３）、ＢＬＫ（４，５）は互いに異なる色又はパターンとなっており、ブロックＢＬＫ（４，５）とＢＬＫ（４，７）は互いに同じ色の同じパターンであるものとする。
【００５９】
図１３は、図１２の３２×３２画素のブロックの符号化データのデータ構造を示している。この符号化データは、図１１における１つのブロック（３２×３２画素）分の符号化データを示してもいる。
【００６０】
以下、図１２の３２×３２画素の画像データから、図１３に示す１ブロック分の符号化データが生成される手順を説明する。
【００６１】
＜ＳＩＺＥ＝３２の処理＞
初期サイズ（３２×３２画素）に着目すると、その内部の色数が“１”ではない。従って、ＳＩＺＥ＝３２の同一色判定の判定結果により出力される二進データは“０”（ステップＳ１００６の出力）となる。また、初期サイズの場合、変数ｉが“０”の場合にだけ処理がなされる。すなわち、着目ブロックを処理する以前に処理されたブロックせず、ブロック間の一致判定も行なわない。従って、着目ブロックの符号化データは、同一色判定の判定結果である“０”のみとなる。
【００６２】
なお、初期サイズの着目ブロックに対しては、４分割したサブブロックをＳＩＺＥ＝１６に対応するサブブロックに登録する。このとき、登録する４つのサブブロックは、図１２の場合、ＢＬＫ（１６，０）、ＢＬＫ（１６，１）、ＢＬＫ（１６，２）、ＢＬＫ（１６，４））である。なお、ＢＬＫ（１６，１）は、図１２では示されていないが、右上隅の１６×１６画素の領域である。
【００６３】
ところで、もし３２×３２画素の全てが同一色である場合、符号語は「“１”＋Ｒ、Ｇ、Ｂの値」で計２５ビットの符号化データを生成し、ＳＩＺＥ＝１６、８、４の符号化処理は行なわない。
【００６４】
＜ＳＩＺＥ＝１６の処理＞
未符号化として登録されたＳＩＺＥ＝１６のブロックをラスタースキャン順に評価する。すなわち、ＢＬＫ（１６、０）→ＢＬＫ（１６、１）→ＢＬＫ（１６、２）→ＢＬＫ（１６，３）の順番に判定処理を行なう。
【００６５】
先ず、ブロックＢＬＫ（１６，０）に着目する。このブロックＢＬＫ（１６，０）内の全画素は同一色であるので、符号語「“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００６６】
次に、ブロックＢＬＫ（１６，１）に着目する。このブロックＢＬＫ（１６，１）は、その内部の色数が“２”以上であり、既に処理したブロックＢＬＫ（１６，０）とも一致しない。従って、着目ブロックＢＬＫ（１６、１）については、判定情報として“００”を出力する。また、着目ブロックＢＬＫ（１６、１）を構成する４つの８×８画素のサブブロックＢＬＫ（８，０）、ＢＬＫ（８，１）、ＢＬＫ（８，２），ＢＬＫ（８、３）をＳＩＺＥ＝８のブロックリストに登録する。
【００６７】
次に、ブロックＢＬＫ（１６，２）に着目する。このブロックＢＬＫ（１６，２）内の全画素は同一色であるので、「符号語“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）として出力する。
【００６８】
次に、ブロックＢＬＫ（１６，３）に着目する。このブロックＢＬＫ（１６，３）内の全画素は同一色であるので、「符号語“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００６９】
＜ＳＩＺＥ＝８の処理＞
未符号化として登録されたＳＩＺＥ＝８のブロックをラスタースキャン順に評価する。すなわち、ＢＬＫ（８、０）→ＢＬＫ（８、１）→ＢＬＫ（８、２）→ＢＬＫ（８，３）の順番に判定処理を行なう。
【００７０】
先ず、ブロックＢＬＫ（８，０）に着目する。このブロックＢＬＫ（８，０）内の全画素は同一色であるので、符号語「“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００７１】
次に、ブロックＢＬＫ（８，１）に着目する。このブロックＢＬＫ（８，１）は、その内部の色数は“２”以上であり、既に処理したブロックＢＬＫ（８，０）とも一致しない。従って、着目ブロックＢＬＫ（８、１）については、判定情報として“００”を出力する。また、着目ブロックＢＬＫ（８、１）は分割対象とし決定し、それを構成する４つの４×４画素のサブブロックＢＬＫ（４，０）、ＢＬＫ（４，１）、ＢＬＫ（４，２），ＢＬＫ（４、３）をＳＩＺＥ＝４のブロックリストに登録する。
【００７２】
次に、ブロックＢＬＫ（８，２）に着目する。このブロックＢＬＫ（８，２）内の全画素データは同一色であるので、符号語「“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００７３】
次に、ブロックＢＬＫ（８，３）に着目する。このブロックＢＬＫ（８，３）は、その内部の色数は“２”以上であり、既に処理したブロックＢＬＫ（８，２）、ＢＬＫ（８，１）、ＢＬＫ（８，０）のいずれとも一致しない。従って、着目ブロックＢＬＫ（８、３）については、判定情報として“００”を出力する。また、着目ブロックＢＬＫ（８、３）を構成する４つの４×４画素を、ＳＩＺＥ＝４のブロックリストに登録する。ＳＩＺＥ＝４のブロックリストには、ブロックＢＬＫ（８、１）に対する処理で、既に４つのブロックが登録されている。従って、着目ブロックＢＬＫ（８，３）を４分割して登録するブロックはＢＬＫ（４，４）、ＢＬＫ（４，５）、ＢＬＫ（４，６），ＢＬＫ（４、７）となる。つまり、ＳＩＺＥ＝４のブロックリストには、計８個のブロックが登録される。
【００７４】
＜ＳＩＺＥ＝４の処理＞
未符号化として登録されたＳＩＺＥ＝４のブロックをラスタースキャン順に評価する。すなわち、ＢＬＫ（４、０）→ＢＬＫ（４、１）→ＢＬＫ（４、２）→…→ＢＬＫ（４，６）→ＢＬＫ（４，７）の順番に判定処理を行なう。
【００７５】
ＢＬＫ（４，０）、ＢＬＫ（４，２）、ＢＬＫ（４，４）、ＢＬＫ（４，６）は、それぞれの内部の画素が同一色であるので、それぞれの判定情報は「“１”＋Ｒ、Ｇ、Ｂの値」となるのは、これまでの説明から明らかである。従って以下では、ＢＬＫ（４、１）、ＢＬＫ（４，３）、ＢＬＫ（４，５）、ＢＬＫ（４，７）について説明する。
【００７６】
ブロックＢＬＫ（４，１）に着目する。このブロックＢＬＫ（４，１）内の色数は“２”以上であり、且つ、既に処理したブロックＢＬＫ（４，０）とも一致しない。従って、着目ブロックＢＬＫ（４、１）については、判定情報として“００”を出力する。ただし、実施形態では、ＳＩＺＥ＝４を下限としているので、後続して着目ブロックＢＬＫ（４，１）の可逆符号化データを生成し、出力する。
【００７７】
ブロックＢＬＫ（４，３）に着目する。このブロックＢＬＫ（４，３）内の色数は“２”以上であり、且つ、既に処理したブロックＢＬＫ（４，２）、ＢＬＫ（４，１）、ＢＬＫ（４，０）のいずれとも一致しない。従って、着目ブロックＢＬＫ（４、３）については、判定情報として“００”を出力し、後続して着目ブロックＢＬＫ（４，１）の可逆符号化データを生成し、出力する。
【００７８】
ブロックＢＬＫ（４，５）に着目する。このブロックＢＬＫ（４，５）内の色数は“２”以上であり、且つ、既に処理したブロックＢＬＫ（４，４）、ＢＬＫ（４，３）、ＢＬＫ（４，２）、ＢＬＫ（４，１）、ＢＬＫ（４，０）のいずれとも一致しない。従って、着目ブロックＢＬＫ（４、５）については、判定情報として“００”を出力し、後続して着目ブロックＢＬＫ（４，５）の可逆符号化データを生成し、出力する。
【００７９】
ブロックＢＬＫ（４，７）に着目する。このブロックＢＬＫ（４，７）内の色数は“２”以上である。しかしながら、着目ブロックＢＬＫ（４，７）のパターンは、既に処理したブロックＢＬＫ（４，５）のパターンと一致する。従って、着目ブロックＢＬＫ（４、７）の判定情報（符号化データ）の先頭の２ビットは“０１”となる。また、それに後続して、ブロックＢＬＫ（４、５）を特定する情報（図示の場合には、“０１”）を付加する（図７参照）。
【００８０】
以上の結果、３２×３２画素のブロックが、図１２に示す状態である場合、図１３に示す符号化データを生成することが可能になる。
【００８１】
図１４（ａ）乃至（ｄ）は、図１２に示す３２×３２画素のブロックの符号化処理が完了したときの、ブロック情報管理メモリ１０７に作成された各サイズ別の管理テーブルを示している。図１４（ａ）は、ＳＩＺＥ＝３２のブロックリストを示し、１つのブロックだけが登録されている。図１４（ｂ）は、ＳＩＺＥ＝１６のブロックリストを示し、４つのブロックが登録されている。図１４（ｃ）は、ＳＩＺＥ＝８のブロックリストを示し、４つのブロックが登録されている。図１４（ｄ）は、ＳＩＺＥ＝４のブロックリストを示し、８つのブロックが登録されている。各サイズのブロックリストとそれらに登録されているブロック数は、図１３の符号化データのデータ構造と一致している。
【００８２】
図１５は、本実施形態に係る画像符号化装置の制御部１１０による符号化対象画像データの符号化処理の手順を示すフローチャートである。
【００８３】
まず、画像入力部１０１から符号化対象画像の３２ライン分が入力され、ストライプバッファ１０２へと格納される（ステップＳ１７０１）。ブロック切り出し部１０３ではストライプバッファ１０２に格納されるストライプデータの左から右へ、順番に３２×３２の大きさのブロックを一つずつ取り出してブロック切り出し部の内部に格納する（ステップＳ１７０２）。続いて、ステップＳ１７０３ではブロック情報管理メモリ１０７に保持されている各サイズ毎のブロック管理テーブルを初期状態にする。初期状態において、各ブロック管理テーブルは空の状態である。ブロック管理情報の初期化が終了すると、ブロック符号化部１０４にて、ブロック情報管理メモリ内のブロック管理テーブルを更新しながらブロックの符号化が行われる。ステップＳ１７０４の処理の流れは、先に説明した図３の通りである。着目するブロックの符号化を終えると、符号化したブロックがストライプデータの最後のブロックであるか否かを判断し（ステップＳ１７０５）、最後のブロックでない場合（ＮＯ）にはステップＳ１７０２に処理を戻して次のブロックについて同様に処理を行う。最後のブロックである場合（ＹＥＳ）にはステップＳ１７０６へと処理を移す。ステップＳ１７０６では、符号化したストライプが画像の最終ストライプであるか否かを判断し、最後のストライプでない場合（ＮＯ）にはステップＳ１７０１へと処理を戻し、次のストライプについて同様に処理を継続する。最後のストライプであった場合（ＹＥＳ）にはステップＳ１７０７に移り、符号列形成部１０５から所定のフォーマットの符号化データが出力され、符号出力部１０６から装置外部へと出力される。
【００８４】
以上の処理により、画像データの符号化処理が行われる。様々な大きさのブロックで周囲の符号化済みのブロックとの一致／不一致を符号化することにより、文字、線画、ＣＧ画像など、同じ画素配置のパターンが多く出現する画像に対し、高い圧縮性能の可逆符号化を実現できる。なお、本実施形態の画像処理装置ではブロック単位に独立の符号化が行われているため、部分的な復号や、並列符号化／復号をも可能になる。
【００８５】
次に、上記の画像符号化装置で生成された符号化画像データを復号する復号装置について説明する。
【００８６】
実施形態における画像復号装置のブロック構成図を図１６に示す。本装置は、符号入力部２０１、符号バッファ２０２、ヘッダ解析部２０３、ブロック復号部２０４、ブロック情報管理メモリ２０５、ブロック書き出し部２０６、ストライプバッファ２０７、画像出力部２０８、及び、装置全体の制御を司る制御部２１０を備える。
【００８７】
以下、図１６を参照して、本実施形態に係る画像復号装置が行う処理について説明する。
符号入力部２０１は、復号対象となる符号化画像データを入力し、符号バッファ２０２に格納する。この符号化画像データは、記憶媒体に格納されていても構わないし、ネットワークを介して入力しても構わず、その入力源の種類は問わない。
【００８８】
ヘッダ解析部２０３は符号バッファ２０２に格納される符号化データのヘッダ部分を解析し、画像の水平方向／垂直方向の画素数、画素を構成する成分の数、各成分の精度など、復号に必要な付加情報を抽出する。制御部２１０は、この付加情報に基づき、各構成要素に復号に必要な設定を行ない、復号処理を開始させる。
【００８９】
ブロック復号部２０４は符号バッファ２０４から符号データを読み出して、３２×３２画素の画像データを復号を開始する度に、ブロック情報管理メモリ２０５を初期化する。そして、その初期化後に、ブロック情報管理メモリ２０５を更新しながら、ブロック書き出し部２０６内のメモリに格納された画像データを参照し、各サイズのブロックを復号していく。復号して得られた各サイズのブロックデータはブロック書き出し部２０６の内部バッファに格納する。そして、３２×３２画素の画像データが復号できたら、その画像データをストライプバッファ２０７に格納する。画像出力部２０８は、１ストライプ分の画像データが、ストライプバッファ２０７に格納される度に、そのストライプ画像データを復号結果として出力する。
【００９０】
図１７はブロック復号部２０４における復号処理の流れを示すフローチャートである。基本的に、復号処理は、符号化処理とは逆の処理となる。以下、同図を参照して、ブロック復号部２０４によるブロックデータの復号処理の全体的な流れについて説明する。
【００９１】
ブロック復号部１０４は、図１におけるブロック符号化部１０４と同様に、その内部に、着目ブロックの大きさ（水平／垂直方向画素数）を保持する変数ＳＩＺＥと、着目ブロックの左上隅の座標（以降、始点座標と呼ぶ）ベクトルＢを備える。復号の開始時には、符号化時と同じく、ステップＳ４０１にて、変数ＳＩＺＥを「３２」で初期化する。次いで、ステップＳ４０２にて、変数Ｎｍａｘに“１”を設定する。
【００９２】
次に、ステップＳ４０３にて、ブロック情報管理メモリ１０７に、ＳＩＺＥ＝３２のブロックリスト（エントリ数＝１）を登録する。次いで、ステップＳ４０４にて、変数ｉに初期値として“０”を設定し、ステップＳ４０５にて、着目ブロックから派生するサブブロックのエントリ数を格納する変数ＳＵＢｉを“０”で初期化する。以上で、符号化処理を開始する際の初期の処理が終了する。
【００９３】
次に、ステップＳ４０６に進み、符号化バッファ２０２から先頭の１ビットである、同一色の判定情報を入力し、その判定情報が“１”であるか否かを判断する。同一色判定情報が“１”である場合、ステップＳ４０７に進み、同一色の判定情報に後続するＲＧＢの各成分値を符号化バッファ２０２から入力する。そして、ステップＳ４０８にて、着目ブロックに含まれる個数分だけ、入力したＲＧＢデータを繰り返し出力することで、着目ブロックの復号処理を行なう。この後、処理はステップＳ４１５に進める。
【００９４】
また、ステップＳ４０６にて、同一色判定情報が“０”であると判定した場合、処理はステップＳ４０９に進む。このステップＳ４０９では、符号化バッファ２０２から、１ビットの同一パターン符号化データを入力し、それが“１”であるか否かを判断する。同一パターン符号化データが“１”であると判断した場合、同一パターン符号化データの直後のビットから、最初に“１”となるデータが、着目ブロックと同一パターンの位置を特定する情報である。従って、その間の“０”の個数で特定される位置の復号済みのブロックのデータを、ブロック書き出し部２０６から探し出し、そのブロックのデータを着目ブロックのデータとして出力する。この後、処理はステップＳ４１５に進める。
【００９５】
また、ステップＳ４０９にて、同一パターン符号化データが“０”であると判断した場合、処理はステップＳ４１１に進める。このステップＳ４１１では、変数ＳＩＺＥが“４”であるか否か、すなわち、着目ブロックが下限サイズであるか否かを判断する。
【００９６】
変数ＳＩＺＥが“４”以外（ＳＩＺＥ＝８、１６、３２のいずれか）である場合には、ステップＳ４１２にて、着目ブロックを構成する４つのサブブロックを登録する。そして、変数ＳＵＢｉを“４”だけ増加させる。
【００９７】
また、ステップＳ４１１にて、変数ＳＩＺＥが“４”であると判断した場合、処理はステップＳ４１４に進める。このステップＳ４１４では、同一パターン符号化データに後続するデータは、予測誤差符号化データであるものとして、符号化バッファ２０２から読込み、復号処理を行ない、その復号結果の４×４画素の画像データをブロック書き出し部２０６に出力する。そして、処理をステップＳ４１５に進める。
【００９８】
ステップＳ４１４では、先に説明した符号化と逆の手順で着目ブロックの画素値を復号する。まず、左上隅の画素の各成分値をそのまま取り出し、その後、着目ブロック内をラスタースキャン順に、前置を予測値とした予測誤差を復号し、前置と加算することにより各画素値を復号する。予測誤差はＪＰＥＧ可逆符号化モードの復号と同様に、まず、図９から予測誤差ｅの属するカテゴリＳＳＳＳを復号し、続いて、ＳＳＳＳビットの付加ビットを取得して、カテゴリの中のどの値かを特定する。このように復号された各画素の値はブロック書き出し部２０６の内部の、着目ブロックに対応する記憶領域に順次格納される。
【００９９】
さて、上記のようにして処理がステップＳ４１５に進むと、変数ｉを“１”だけ増加させる。そして、ステップＳ４１６にて、変数ｉと変数Ｎｍａｘとを比較する。ｉ＜Ｎｍａｘである場合、着目ブロックリスト中に、未処理のブロックが存在することになるので、ステップＳ４０６以降の処理を行なう。
【０１００】
また、ｉ＝Ｎｍａｘであると判断した場合には、処理をステップＳ４１７に進める。ここのステップＳ４１７では、変数ＳＵＢｉが“０”よりも多いか否かを判断する。ＳＵＢｉ＞０であると判断した場合、処理はステップＳ４１８に進み、そのサブブロックの処理を行なうため、変数ＳＩＺＥを１／２に設定する。すなわち、変更後の変数ＳＩＺＥで示されるブロックリストを着目ブロックリストとして設定する。そして、ステップＳ４１９にて、エントリの上限をＳＵＢｉとするため、変数ＮｍａｘにＳＵＢｉを代入し、ステップＳ４０４以降の処理を行なう。
【０１０１】
また、ステップＳ４１７にて、変数ＳＵＢｉが“０”であると判断した場合、３２×３２画素で構成されるブロックの復号処理が終了したものとし、本処理を終える。
【０１０２】
以上、説明した処理により、ブロック復号部２０４において、１つのブロックの復号が行われ、ブロック書き出し部２０６の内部にブロックのデータが格納される。
【０１０３】
ブロック書き出し部２０６は、その内部に、ブロック復号部２０４によるブロックの復号処理により生成された画像データを格納する内部メモリ（３２×３２画素分のメモリ）を有する。そして、内部メモリに３２×３２画素分の画像データが格納されると、その画像データをストライプバッファ２０７に出力する。
【０１０４】
図１８は、本実施形態に係る画像復号置による制御部２１０による復号処理の全体の流れを示すフローチャートである。以下、同図を参照して、本実施形態に係る画像処理装置が行う画像符号化処理の全体的な流れについて説明する。
【０１０５】
まず、符号入力部２０１から復号対象となる符号化データが符号バッファ２０２に入力され、ヘッダ解析部２０３で符号化データのヘッダを解析して復号に必要な付加情報を取り出す（ステップＳ３０１）。ヘッダの解析が終了すると、ブロック情報管理メモリ２０５の内部に格納されているブロック管理テーブルを初期化する（ステップＳ３０２）。初期状態でブロック管理テーブルは空の状態である。ブロック復号部２０４は、符号バッファ２０２に格納されている符号を読み出して、ブロック情報管理メモリに格納されているブロック管理テーブルを更新しながら１つの３２×３２画素の画像データを復号する。そして、ブロック復号部２０４は、その画像データを、ブロック書き出し部２０６の内部バッファに書き込む（ステップＳ３０３）。ブロック復号部２０４の動作については先に図１７を用いて説明した通りである。
【０１０６】
ブロック復号部２０６によるブロックデータの復号が終了し、ブロック書き出し部２０６の内部バッファにブロックデータが格納されると、ブロック書き出し部２０６はこれをストライプバッファ２０７へと転送する。ブロックデータは、ストライプバッファの左から右へ順に並べて書き込まれる。復号したブロックデータがストライプの最後のブロックであるか否かを判断し（ステップＳ３０５）、ストライプの最後のブロックでない場合（ＮＯ）は、処理をステップＳ３０２へと移して次のブロックの復号を行う。ストライプの最後のブロックであった場合（ＹＥＳ）にはストライプバッファ２０７に格納されたストライプデータをラスタースキャン順に読み出して、画像出力部２０８から装置外部へと出力する（ステップＳ３０６）。ステップＳ３０７では、出力したストライプデータが画像の最後のストライプデータであるか否かを判断する。最終ストライプでない場合（ＮＯ）はステップＳ３０２へと処理を移し、次のストライプの復号処理を継続して行う。このとき、ストライプバッファ２０７はクリアされており、また、左端から次のブロックデータを格納していく。
【０１０７】
以上の処理により、符号化データから元の画像データを完全に復元することができるようになる。
【０１０８】
以上説明したように本実施形態によれば、文字、線画、ＣＧ画像など、同一画素値や同一パターンの連続の多い画像に対しても効率良く可逆符号化することが可能になり、オリジナル画像を可逆復元することも可能になる。
【０１０９】
なお、実施形態では、符号化処理における初期のブロックサイズを３２×３２画素とし、サブブロックのサイズを１６×１６、８×８、４×４の４段階としたが、これらのサイズ、段階数によって本発明が限定されるものではない。また、各ブロック（サブブロック）のサイズも必ずしも正方である必要もない。また、１つのブロックが４つのサブブロックで構成されるものとしたが、必ずしも４つではなくても構わない。要するに、１つのブロックを、再帰的にｐ×ｑ個（ｐ，ｑは２以上の整数）のサブブロックに再帰的に分割できるようにすればよい。ただし、サブブロックのサイズの下限は、実施形態の如く４×４画素程度の、ある程度のサイズであることが望ましい。
【０１１０】
また、上記実施形態の場合、着目ブロック（または着目サブブロック）内の全画素が同一である場合、同一色であることを示す情報（実施形態では“１”）に後続して、その色を示す画素データ（Ｒ、Ｇ、Ｂの２４ビット）を付加させた。この結果、着目する３２×３２画素の画像データが、図１２に示すような場合、サブブロック
ＢＬＫ（１６，０）、ＢＬＫ（１６，２）、ＢＬＫ（１６，３）、ＢＬＫ（８，０）、ＢＬＫ（８，２）、ＢＬＫ（４，０）、ＢＬＫ（４，２）、ＢＬＫ（４，４）、ＢＬＫ（４，６）
の符号化データは、いずれも、
「“１”＋Ｒ，Ｇ，Ｂ」
の形式となり、冗長となってしまう（図１３参照）。
【０１１１】
そこで、同一色の画素のみで構成されると判断した最初のサブブロック（図１２の場合にはＢＬＫ（１６，０）の符号化データについては
「“１”＋Ｒ，Ｇ，Ｂ」
という形式にする（以下、このサブブロックを同一色起源サブブロックという）。そして、それ以降で同一色の画素のみで構成されるサブブロックについては、そのサブブロック内の画素の各成分値と、同一色起源サブブロックの各成分値との差分を演算し、その差分を符号化すつようにしても構わない。
【０１１２】
図１２の場合、サブブロックＢＬＫ（１６，０）が同一色起源サブブロックとなり、それ以外の
ＢＬＫ（１６，２）、ＢＬＫ（１６，３）、ＢＬＫ（８，０）、ＢＬＫ（８，２）、ＢＬＫ（４，０）、ＢＬＫ（４，２）、ＢＬＫ（４，４）、ＢＬＫ（４，６）
の各成分は差分を符号化する。差分が小さいほど短い符号語を割り当てるようにすると、符号化効率は格段に高くなる。
【０１１３】
なお、上記実施形態では、１つのブロック内の画像データを符号化する際に、そのブロック内の全画素が同じ色を示すか否かを判定したが、この同一色判定とその符号化データの生成は省略しても構わない。ただし、この場合、各ブロックの符号化データの先頭には、着目ブロックの画像データと同一の画像データが既に符号化された画像データの領域内に存在するか否かを示す１ビットを配置するようにする。そして、同一ブロックが存在する場合には先頭の“１”に後続して、同一ブロックの位置を特定する符号語を格納すればよい。
【０１１４】
＜第１の実施形態の変形例＞
上記第１の実施形態と同様の処理は、コンピュータプログラムによって実現できる。以下、その例を第１の実施形態の変形例として説明する。
【０１１５】
図１９は、本変形例における情報処理装置（例えばパーソナルコンピュータ）のブロック構成図である。
【０１１６】
図中、１４０１はＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理、復号処理のアプリケーションプログラムを実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。また、ＲＡＭ１４０２は、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。
【０１１７】
１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７はハードディスクドライブ装置等の大容量の外部記憶装置である。この外部記憶装置１４０７には、ＯＳ（オペレーティングシステム）や後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象画像の符号化データなどがファイルとして保存されている。また、ＣＰＵ１４０１は、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードし、実行することになる。
【０１１８】
１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象の画像の符号化データなどを記録しておいても良い。この場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。
【０１１９】
１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えは符号化対象の画像データや、復号対象の画像の符号化データなどを本装置のＲＡＭ１４０２や外部記憶装置１４０７、あるいは記憶媒体ドライブ１４０８に入力することもできる。１４１０は上述の各部を繋ぐバスである。
【０１２０】
上記構成において、本装置の電源がＯＮになると、ＣＰＵ１４０１はＲＯＭ１４０３のブートプログラムに従って、外部記憶装置１４０７からＯＳをＲＡＭ１４０２にロードする。この結果、キーボード１４０４、マウス１４０５の入力が可能となり、表示装置１４０６にＧＵＩを表示することが可能になる。ユーザが、キーボード１４０４やマウス１４０５を操作し、外部記憶装置１４０７に格納された画像処理用アプリケーションプログラムの起動の指示を行なうと、ＣＰＵ１４０１はそのプログラムをＲＡＭ１４０２にロードし、実行する。これにより、本装置が画像符号化装置又は画像復号装置として機能することになる。
【０１２１】
画像符号化装置として機能する場合には、図１に示した各種バッファ、テーブルはＲＡＭ１４０２に格納に確保し、各処理部に相当する機能はＣＰＵ１４０１が実行する関数やサブルーチンとして機能させればよい。そして、ＣＰＵ１４０１は、上記第１の実施形態で示した各フローチャートに従った処理を行なえばよいのは明らかである。これは画像復号装置として機能させる場合にも言えることである。
【０１２２】
以上説明した様に、本変形例に従えば、第１の実施形態に相当する処理をコンピュータプログラムによっても実現できるのは明らかであろう。
【０１２３】
＜第２の実施形態＞
上記第１の実施形態の画像処理装置では、全てのブロックをブロック符号化部１０４で符号化する構成とした。文字、線画、ＣＧ画像では、或る領域について着目すると、その領域内の全画素が同一画素値である確率が高いし、同一画素配置パターンが繰り返し出現する確率も高い。従って、上記第１の実施形態は、文字、線画、ＣＧ画像については効率の良い可逆符号化データを生成することができる。
【０１２４】
しかしながら、自然画像（風景画や人物画）の場合、隣接する２画素の間の差は小さくなる可能性が高いものの、隣接する２画素が完全に一致することはむしろ希である。従って、着目ブロック内の全画素が同一色となる確率、及び、着目ブロックと同一パターンを持つ処理済みブロックの存在する確率は共に小さなものとなる。つまり、上記第１の実施形態の技術を自然画に適用した場合、初期ブロックサイズ（３２×３２画素）の多くの部分が下限サイズ（４×４画素）にまで分割した後、可逆符号化することになり、符号化効率が下がる可能性が高い。
【０１２５】
そこで、第３の実施形態としてブロック単位に画像の特性を判定し、ブロックの一致判定を用いた符号化と、これを用いない画素単位の予測符号化とを切り替える例を説明する。これにより、文字、線画、ＣＧ画像と自然画像が混在するような画像でも効率良く符号化することを目指す。
【０１２６】
本第２の実施形態の画像符号化装置の構成を図２０に示す。第１の実施形態の構成である図１と異なる点は、色数判定部１８０１、スイッチ１８０２、ブロック予測符号化部１８０３が追加された点と、符号列形成部１０５に代わって符号列形成部１８０４となった点である。それ以外の構成要素は、第１の実施形態と同じであるので、同参照番号を付し、その説明は省略する。
【０１２７】
なお、図２０に示す構成はハードウェアにより実現しても良いが、本第２の実施形態では、先に説明した第１の実施形態の変形例と同様に、図２０に示す各部の機能をコンピュータに実現させるプログラムによって実現しても構わない。この場合、そのプログラムは図１９の外部記憶装置１４０７や記憶媒体ドライブ１４０８、もしくはＩ／Ｆ１４０９を介して外部装置からＲＡＭ１４０２にロードされ、ＣＰＵ１４０１が実行することになる。
【０１２８】
以下、図２０を参照して、本第２の実施形態に係る画像符号化装置が行う画像符号化処理について説明する。
本第２の実施形態に係る画像処理装置の符号化対象とする画像データは、第１の実施形態と同じく、ＲＧＢの多値のカラー画像データであり、各コンポーネント（色成分）は８ビット（２５６階調）の輝度値を表現した画素データにより構成されるものとする。符号化対象の画像データの並びは点順次、即ち、ラスタースキャン順に各画素を並べ、その各画素はＲ、Ｇ、Ｂの順番のデータで構成されるものとする。また、画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。
【０１２９】
以下、第１の実施形態と同じ動作のブロックについては説明を省略し、本第２の実施形態で特徴的な処理部についてのみ説明する。
【０１３０】
色数判定部１８０１はブロック切り出し部１０３の内部に格納される３２×３２画素のブロックデータについて、そのブロック内の出現する色の種類数を色数Ｎｃとして計数する。そして、色数判定部１８０１は、色数Ｎｃと予め定められた閾値Ｔｈとを比較し、Ｎｃ＞Ｔｈである場合（色数が閾値よりも大きい場合）には「１」、Ｎｃ≦Ｔｈである場合（色数が閾値以下の場合）には「０」の判定信号を生成し、その判定信号をスイッチ１８０２及び符号列形成部１８０４に出力する。なお、閾値Ｔｈの値は、符号化対象の画像のサイズに応じて設定することが望ましい。本第２の実施形態ではＴｈ＝３２として説明する。
【０１３１】
この色数判定部１８０１の目的は、ブロックの特性に応じて、後述するブロック予測符号化部１８０３とブロック符号化部１０４とを切り替えることにある。すなわち、文字、線画、ＣＧ画像では使用されている色数は少ない傾向にあり、また、自然画像では多くの色数が使用される傾向にある。判定部１８０１は、この性質を利用して、符号化対象のブロックが文字、線画、ＣＧの画像であるか、自然画であるかを判定していると言うこともできる。本第２の実施形態の画像処理装置では色数によって処理対象ブロックが、文字、線画、ＣＧの画像であるか、自然画であるかを判断するものとしているが、この判断は一例であることに留意願いたい。例えば、別の実施形態として、ブロック内での同一画素値の連続数や、ブロック内画素のヒストグラムの形状から判別してもよいであろう。
【０１３２】
スイッチ１８０２は色数判定部１８０１から出力される制御信号によって、ブロック単位に画像データの供給先を切り替える。色数判定部１８０１からの制御信号が「０」である場合、すなわち、着目している３２×３２画素の画像が文字、線画、ＣＧの属性を持つと判断した場合、スイッチを端子ｂ側に接続し、画像データをブロック符号化部１０４に供給する。
【０１３３】
また、色数判定部１８０１からの制御信号が「１」である場合、すなわち、着目している３２×３２画素の画像が自然画属性を持つと判断した場合、スイッチを端子ａ側に接続し、画像データをブロック予測符号化部１８０３に供給する。
【０１３４】
ブロック予測部１８０３はスイッチ１８０２が端子ａ側に接続された場合に、ブロック切り出し部１０３に格納される３２×３２画素のブロックデータを、サブブロックに分割すること無しに、符号化する。従って、各サブブロックの同一色判定情報、同一パターンの有無情報が無くなる。ブロック予測符号化部１８０３におけるブロックデータの符号化には予測符号化が用いられる。ブロック切り出し部１０３に格納されるブロックデータの各画素をラスタースキャン順に、各画素Ｒ，Ｇ，Ｂの順番で成分値を読み出して順番に符号化していく。着目する画素を符号化する場合には、着目画素の近傍に位置し、既に符号化された複数の近傍画素を参照し、着目画素の着目色成分の予測値ｐを求める。そしして、着目画素の成分値と予測値ｐとの差分値を算出し、その差分値を符号化する。
【０１３５】
着目画素の水平方向（右方向）の座標値ｘ、垂直（下方向）の座標値ｙとし、着目画素の座標を（ｘ，ｙ）と定義したとき、３つの近傍画素を利用する場合、それら近傍画素の座標は（ｘ−１，ｙ）、（ｘ，ｙ−１）、（ｘ−１，ｙ−１）とする。そして、着目画素の着目色成分Ｃ（ＣはＲ、Ｇ、Ｂのいずれか）の値をＰ（ｘ、ｙ、Ｃ）と表現したとき、予測値ｐは例えば次のようにして求める。
ｐ＝Ｐ(x-1,y,C)＋Ｐ(x,y-1,C)−Ｐ(x-1,y-1,C)
【０１３６】
従って、予測誤差ｅは、
ｅ＝Ｐ(x,y)−ｐ
＝Ｐ(x,y)−｛Ｐ(x-1,y,C)＋Ｐ(x,y-1,C)−Ｐ(x-1,y-1,C)｝
となる。なお、着目画素が、ブロックデータの最初のライン上にある場合、予測値ｐ＝ａとする。また、着目画素が、ブロックデータの左端位置にある場合にはｐ＝ｂとする。そして、着目画素が、ブロックの最初の画素（最初のラインの左端位置）ではｐ＝１２８とする。ただし、これらの取り決めは、復号処理と同じすればよく、ここで示されるのは一例である点に留意願いたい。
【０１３７】
予測誤差はＪＰＥＧ可逆符号化モードと同様に、まず、図９から予測誤差ｅの属するカテゴリＳＳＳＳを得て、これを図１０のハフマンテーブルで符号化する。続いて、カテゴリの中のどの値かを特定するための長さＳＳＳＳビットの付加ビットを出力する。予測誤差ｅが正である場合、付加ビットは予測誤差ｅの下位ＳＳＳＳビットであり、負である場合には予測誤差ｅ−１の下位ＳＳＳＳビットを取り出したものである。
【０１３８】
本第２の実施形態の場合、３２×３２画素の符号化データは、ブロック予測符号化部１８０３、ブロック符号化部１０４のいずれか一方の符号化データとなる。従って、いずれの符号化データであるかを示す識別情報がないと、正しく復号できない。それ故、符号列形成部１８０４は、色数判定部１８０１からの判定信号（１ビットで良い）を、ブロックのヘッダに挿入する。
【０１３９】
符号列形成部１８０４は画像データの符号化処理を開始する際に、所定のフォーマットのヘッダ符号列を形成し、符号出力部１０６に出力する。ヘッダ符号列には、画像の水平方向／垂直方向の画素数、画素を構成する成分の数、各成分の精度など、画像の復号に必要な付加情報が含まれる。また、各ブロック毎に色数判定部１８０１から出力される判定結果をブロックヘッダとし、それに後続してブロック予測符号化部１８０３かブロック符号化部１０４のどちらか一方から出力されるブロックの符号化データを出力する。図２１に符号列形成部１０５から出力される符号列の構成の一例を示す。先頭のヘッダに付加情報が格納され、続いてラスタースキャン順の各ブロックの符号化データが並ぶが、その先頭（図中、斜線部分）に色数判定部１８０１から出力される判定結果が付与される。これにより復号側でも、２種類の符号化データを正しく復号することができる。
【０１４０】
図２２は、本第２の実施形態に係る画像符号化装置の制御部１１０の処理内容を示すフローチャートである。以下、同図を参照して、本実施形態に係る画像処理装置が行う画像符号化処理の全体的な流れについて説明する。
【０１４１】
まず、画像入力部１０１から符号化対象画像の３２ライン分が入力され、ストライプバッファ１０２へと格納される（ステップＳ２００１）。ブロック切り出し部１０３ではストライプバッファ１０２に格納されるストライプデータの左から右へ、順番に３２×３２の大きさのブロックを一つ取り出して、ブロック切り出し部１０３の内部メモリに格納する（ステップＳ２００２）。
【０１４２】
ブロック切り出し部１０３にブロックデータが格納されると、色数判定部１８０１によりブロック内の画素の種類の数を色数Ｎｃとして計数し（ステップＳ２００３）、Ｎｃ＞Ｔｈであるか否かを判定する（ステップＳ２００３）。
【０１４３】
Ｎｃ＞Ｔｈである場合（ＹＥＳ）、スイッチ１８０２が端子ａ側に接続され、ブロック予測符号化部１８０３によりブロック切り出し部１０３の内部に格納されている３２×３２画素のブロックデータの符号化が行われる（ステップＳ２００５）。
【０１４４】
一方、Ｎｃ≦Ｔｈである場合（ＮＯ）、スイッチ１８０２が端子ｂ側に接続される。その後、ブロック情報管理メモリ１０７を初期状態に設定し（ステップＳ２００６）、ブロック符号化部１０４によりブロックデータの符号化が行われる（ステップＳ２００７）。このステップＳ２００７の符号化処理は、先に説明した第１の実施形態と同じである。
【０１４５】
ステップＳ２００５又はＳ２００７にて生成される符号化データは符号列形成部１８０４へと出力される。符号列形成部１８０４は、色数判定部１８０１の色数判定結果、すなわち、Ｎｃ＞Ｔｈであるか、Ｎｃ≦Ｔｈであるかを示す１ビットの信号をブロックヘッダとして出力する。そして、符号列形成部１８０４は、それに後続して、ブロック予測符号化部１８０３又はブロック符号化部１０４のいずれか一方からの符号化データを出力する。
【０１４６】
ステップＳ２００８では符号化したブロックがストライプの最後のブロックであるか否かを判定し、最後のブロックでない場合（ＮＯ）にはステップＳ２００２へと処理を移し、次のブロックについて処理を行う。また、最後のブロックである場合（ＹＥＳ）、ステップＳ２００９へと処理を移す。このステップＳ２００９では、符号化したストライプが画像の最終ストライプであるか否かを判断し、最後のストライプでない場合（ＮＯ）にはステップＳ２００１へと処理を戻し、次のストライプについて同様に処理を継続する。
【０１４７】
また、最後のストライプであった場合（ＹＥＳ）にはステップＳ２０１０に移り、符号列形成部１８０４から所定のフォーマットの符号化データが出力され、符号出力部１０６から装置外部へと出力される。
【０１４８】
以上の処理により、画像データの符号化処理が行われる。自然画特性のブロックに対しては３２×３２画素のブロックで予測符号化を適用し、文字、線画、ＣＧ特性のブロックについては、様々な大きさのブロックで周囲の符号化済みのブロックとの一致／不一致を符号化することになる。この結果、２つの特性の混在する画像においても高い圧縮性能の可逆符号化を実現できる。なお、本実施形態の画像処理装置ではブロック単位に独立の符号化が行われているため、部分的な復号や、並列符号化／復号が可能という特徴がある。
【０１４９】
次に、第２の実施形態における画像復号装置について説明する。
【０１５０】
図２３は第２の実施形態における画像復号装置のブロック構成図である。本第２の実施形態における画像復号装置は、符号入力部２０１、符号バッファ２０２、ヘッダ解析部２０３、ブロック復号部２０４、ブロック情報管理メモリ２０５、ブロック書き出し部２０６、ストライプバッファ２０７を備える。また、画像出力部２０８、ブロック判定部２１０１、スイッチ２１０２、ブロック予測復号部２１０３、及び、装置全体の制御を司る制御部２１０とを備える。
【０１５１】
図２３の画像復号装置と、先に説明した第１の実施形態における図１９の画像復号装置との違いは、図１９の構成に、復号方式選択部２１０１、スイッチ２１０２、ブロック予測復号部２１０３が追加された点である。
【０１５２】
以下、図２３を参照して、本第２の実施形態に係る画像復号装置が行う処理について説明する。
【０１５３】
第１の実施形態と同様、符号入力部２０１は復号対象となる符号化データを入力し、その符号化データを符号バッファ２０２に適宜格納する。ヘッダ解析部２０３は、付加情報の取得を、復号に必要な情報を取得し、制御部２１０に出力する。制御部２１０は、この情報に基づき、各処理部に復号に必要な情報を設定する。
【０１５４】
ブロック判定部２１０１は、各ブロック（３２×３２画素の符号化データ）のヘッダに含まれる符号化データの種類を示す信号が“０”か“１”かを判定し、制御信号としてスイッチ２１０２に出力する。
【０１５５】
スイッチ２１０２は、ブロック判定部２１０１により出力されるを制御信号により、端子ａと端子ｂの何れかを選択接続する。
【０１５６】
制御信号が「０」である場合、端子ｂ側に接続し、符号化データをブロック復号部２０４に出力する。ブロック復号部２０４は、スイッチ２１０２が端子ｂを選択した場合に復号処理を開始する。そして、ブロック復号部２０４は、入力した符号化データを復号し、ブロック書き出し部２０６に復号結果である３２×３２画素の画像データを出力する。このブロック復号部２０４は第１の実施形態で説明した通りである。
【０１５７】
一方、制御信号が「１」である場合、スイッチ２１０２は端子ａを選択接続し、符号化データをブロック予測符号化復号部２１０３に出力する。ブロック予測復号部２１０３は、スイッチ２１０２が端子ａ側に接続される場合に処理を開始する。そして、入力した符号化データを復号し、３２×３２画素の画像データを生成し、ブロック書き出し部２０６に出力する。ブロック予測復号部２１０３のブロック復号処理は、第２の実施形態におけるブロック予測符号化部１８０３の逆の処理を行なう。ブロック予測符号化部１８０３の動作から、その復号処理は明らかであり、また、ＪＰＥＧ可逆符号化モードの復号処理と基本的に同じであるので、ここでは説明を省略する。
【０１５８】
ブロック書き出し部２０６は、上記の２つの復号部のいずれか一方から３２×３２画素分の画像データを入力した場合、その画像データをストライプバッファ２０７に格納する。この後の処理は第１の実施形態と同様である。
【０１５９】
図２４は、本第２の実施形態に係る画像復号装置の制御部２１０の処理手順を示すフローチャートである。以下、同図を参照して、本第２の実施形態に係る画像復号処理を説明する。
【０１６０】
まず、制御部２１０は、符号入力部２０１を制御して、復号対象となる符号化データを符号バッファ２０２に格納させる。そして、ヘッダ解析部２０３に、符号化データのヘッダを解析して復号に必要な付加情報を取り出させる（ステップＳ２２０１）。ヘッダの解析が終了すると、制御部２１０は、各ブロックの復号処理に必要な設定を行なう。
【０１６１】
次いで、制御部２１０は、ブロック判定部２１０１に、ブロック符号化データの先頭に格納される符号化データの種別を示す情報（Ｎｃ＞Ｔｈである場合には“１”、Ｎｃ≦Ｔｈである場合には“０”）を取り出させる（ステップＳ２２０２）。そして、その情報を判定して、制御部２１０は、スイッチ２１０２の切り替えを行う（ステップＳ２２０３）。取り出した情報が“０”である場合には、後続符号化データは、画像符号化装置が有するブロック符号化部１０４により生成されたデータであることになる。従って、スイッチ２１０２は端子ｂへ接続し、処理はステップＳ２２０４に進む。また、取り出した情報が“１”である場合には、後続符号化データは、画像符号化装置が有するブロック予測符号化部１８０３により生成されたデータであることになる。従って、スイッチ２１０２は端子ａへ接続し、処理はステップＳ２２０６に進む。
【０１６２】
ステップＳ２２０４に処理が進むと、ブロック情報管理メモリ２０５の内部に格納されているブロック管理テーブル２０５を初期化する。初期状態でブロック管理テーブル２０５は空の状態である。続いて、ステップＳ２２０５にて、ブロック復号部２０４は、スイッチ２１０２を介して入力した符号化データを、ブロック情報管理メモリ２０５に格納されているブロック管理テーブルを更新しながら３２×３２画素の画像データを復元する。ブロック復号部２０４は、このようにして復元した画像データを、ブロック書き出し部２０６の内部メモリに書き込む。ブロック復号部２０４の動作については第１の実施形態と同様である。
【０１６３】
一方、ステップＳ２２０６に処理が進んだ場合には、ブロック予測復号部２１０３が、スイッチ２１０２を介して入力した符号化データを復号し、３２×３２画素の画像データを生成し、それをブロック書き出し部２０６の内部メモリに書き込む。
【０１６４】
ブロック復号部２０６、またはブロック予測復号部２１０３によるブロックデータの復号が終了し、ブロック書き出し部２０６の内部メモリに１ブロック分の画像データが格納されると、処理はステップＳ２２０７に進む。このステップＳ２２０７に処理が進むと、ブロック書き出し部２０６はこれをストライプバッファ２０７へと転送する（ステップＳ２２０７）。ブロックデータは、ストライプバッファの左から右へ順に並べて書き込まれる。
【０１６５】
復号したブロックデータがストライプの最後のブロックであるか否かを判断し（ステップＳ２２０８）、ストライプの最後のブロックでない場合（ＮＯ）は、処理をステップＳ２２０２へと移して次のブロックの復号を行う。
【０１６６】
また、ストライプの最後のブロックであった場合（ＹＥＳ）にはストライプバッファ２０７に格納されたストライプデータをラスタースキャン順に読み出して、画像出力部２０８から装置外部へと出力する（ステップＳ２２０９）。
【０１６７】
ステップＳ２２１０では、出力したストライプデータが画像の最後のストライプデータであるか否かを判断し、最終ストライプでない場合（ＮＯ）はステップＳ２２０２へと処理を移し、次のストライプの復号処理を継続して行う。このとき、ストライプバッファ２０７はクリアされており、また再び、左端から次のブロックデータを格納していく。最終ストライプであった場合（ＹＥＳ）には復号処理を終了する。
【０１６８】
以上の説明した本第２の実施形態の処理により、符号化データから完全に元の画像データを復元することができる。また、本第２の実施形態によれば、自然画の場合、ブロック分割を行なわないで予測符号化を行なうから、ブロック分割した各サブブロックの先頭に同一色判定情報、同一パターンの有無を示す情報が不要となり、高い符号化効率が期待できる。
【０１６９】
＜第１、第２の実施形態の変形例＞
上記第１の実施形態（その変形例も含む）及び第２の実施形態では、着目ブロックと同一ブロックを探し出す際、着目サイズのブロックリストに登録されたブロックを検索対象とした。例えば着目ブロックのサイズが４であり、図２５（ａ）のｂ（ｎ）のブロックを着目ブロックとする場合、符号化済みのｂ（ｎ−１）、ｂ（ｎ−２）、ｂ（ｎ−３）…との比較を行った。しかしながら、これに限らず、例えば、符号化済みの領域から自由にブロックを取り出して一致判定に用いることができる。例えば、図２５（ｂ）のようにブロックｂｘとも比較するようにすれば、符号化済みの領域の中に同一のブロックを検出できる確率が高くなる。
【０１７０】
第１の実施形態では同一のブロックをブロック番号で特定したが、上記のようにする場合には、初期サイズである３２×３２画素の領域全域を検索対象とする（ブロックリストは参照しない）。そして、着目ブロックとその同一ブロック（図２５（ｂ）の場合にはｂｘ）が見つかった場合には、その同一ブロックと判定したブロックの左上隅の画素の相対座標を符号化するすれば良い。
【０１７１】
また、第２の実施形態では初期ブロックの色数Ｎｃに応じて、ブロックの各画素の負符号化と、ブロック単位の分割符号化を選択的に実施する構成を示した。また、第２の実施形態では、同一画素値、または同一パターンの連続する領域に対してはブロック単位の分割符号化を適用し、それ以外では画素単位の符号化を適用することで符号化の効率改善を図るものであり、色数を２つの符号化方式選択の指標として用いた。この変形例として、色数以外の指標を用いて方式選択しても良いし、実際に２つの符号化方式を実施してみて発生符号量の少なくなる方を選択するよう構成しても良い。
【０１７２】
また、上記実施形態では、前値を予測値とした単純な予測符号化の例を示したが、これに限らず、自然画向きの符号化方式であれば良い。予測符号化を用いる場合においても、成分値の予測方法、予測誤差のエントロピ符号化方式など、様々な手法を用いることができる。例えば、着目する成分値の予測方法としては、幾つかの予測方法を用意して、適応的に切り換えても構わないし、符号化済みの各成分値に発生した予測誤差の平均値を着目する成分の予測にフィードバックするなど、非線形な予測を用いても構わない。
【０１７３】
また、予測誤差のエントロピ符号化としてハフマン符号化を用いる例について示したが、Ｇｏｌｏｍｂ符号化や算術符号など、これ以外のエントロピ符号化を用いも良い。
【０１７４】
また、上述の実施形態ではＲＧＢ画像の符号化を例に説明したが、モノクロ画像、ＣＭＹＫ画像や、Ｌａｂ画像や、ＹＣｒＣｂ画像など、各種の画像データに適用可能である。
【０１７５】
また、上述の実施形態では、符号化装置と復号装置を別々の装置であるものとして説明したが、符号化、及び復号にかかる構成を一つの機器に収容し、共通部分を統合しても構わない。
【０１７６】
＜第３の実施形態＞
上記第１、第２の実施形態及びその変形例では、処理済のブロック中に着目ブロックと同一のものがあるか否かを判断した。本第３の実施形態では、この同一ブロック判定に、更に、着目ブロックを０度、９０度、１８０度、２７０度の回転を行なう処理を含めた例を説明する。
【０１７７】
本第３の実施形態では、符号化対象画像データから２４×２４画素の画像データを抜き出す。以下、この２４×２４画素の画像データをタイルと表現する。本第３の実施形態では、このタイル毎に符号化し、符号化データを生成する。また、１つのタイルを符号化する際には、そのタイルを垂直方向４画素、水平方向２４画素のサイズの複数のストライプに更に分割する。そして、１つのストライプに含まれる４×４画素のブロックを着目ブロックとし、当該着目ブロックとその近傍のブロックとに基づき、符号化処理を行なう。図２６は、タイルとストライプとの関係を示している。１つのタイルは、図２６に示すように６つのストライプで構成されることになる。なお、本第３の実施形態における表現のタイル、ストライプは、共に垂直、水平方向の画素数で定義されるものであるので、第１、第２の実施形態で用いたブロック、サブブロックと技術的に同義のものである。
【０１７８】
図２７に第３の実施の形態における画像符号化装置のブロック構成図を示す。本装置は、入力部１２０１、ストライプメモリＡ１２０２、ストライプメモリＢ１２０３、符号列メモリ１２０４、２つのブロック符号化部１２０５、１２０６、画素符号化部１２０７、出力部１２０８、及び、装置全体の制御を司る制御部１２０９とを備える。ブロック符号化部１２０５は、４×４画素の画像データを、符号化部１２０６は２×２画素の画像データを符号化するものである。ストライプメモリＡ１２０２は、ストライプ中の４×４画素の着目ブロックを格納するために用いられ、ストライプメモリＢ１２０３は１つ前のストライプを格納するために用いられる。
【０１７９】
図２８は、１つのタイル（２４×２４画素の画像データ）の符号化処理を示すフローチャートである。この処理は、制御部１２０９の処理手順でもある。以下、図２８のフローチャートに従い、本第３の実施形態における画像符号化装置の処理内容を説明する。
【０１８０】
先ず、制御部１２０９は、ストライプカウンタｉを“０”にセットする（ステップＳ１３０１）。このストライプカウンタｉは、１タイル（２４×２４画素）内に含まれるストライプの１つを特定するためのものである。ストライプの番号は、タイル中の最上部のストライプの番号を「０」とし、下方向に向かって“１”、“２”、…、“５”を割り当てる。
【０１８１】
入力部２０１は、符号化対象の画像データから、１タイル分の画像データを入力し、入力部２０１内のメモリに１タイル分のデータを格納する。そして、制御部１２０９からのストライプカウンタｉで示されるストライプのデータを、ストライプメモリＡ１２０２に格納する（ステップＳ１３０２）。なお、ストライプカウンタｉが“０”である場合、制御部１２０９は、ストライプメモリＢ１２０３をゼロクリア（４×２４＝８６画素分のデータをゼロクリア）する。
【０１８２】
次いで、ステップＳ１３０３にて、制御部１２０９は、ストライプカウンタｉが“０”であるか否かを判断する。ストライプカウンタｉが“０”である場合、着目ストライプが先頭のストライプを符号化することを示している。それ故、ストライプカウンタｉが“０”である場合、ステップＳ１３０４に処理を進め、制御部１２０９は画素符号化部１２０７に対し、着目ストライプの先頭の４×４画素のブロックについて符号化するように指示する。この画素符号化部１２０７は、第１の実施形態における前置予測誤差を用いた符号化処理と同じであるとし、その説明については省略する。画素符号化部１２０７は、先頭ストライプの先頭の４×４画素ブロックの符号化データを生成し、その符号化データを符号列メモリ１２０４に一時的に記憶する。この後、処理はステップＳ１３０５に進める。
【０１８３】
ステップＳ１３０５に処理が進むと、制御部１２０９は、ブロック符号化部１２０５に対し、着目ストライプの未処理の４×４画素ブロックについて符号化処理を行なせる。ストライプカウンタｉが“０”の場合、図３０に示すように未処理の４×４画素ブロックの数が５つ、ストライプカウンタｉが“０”以外の場合には未処理の４×４画素ブロックの数が６つである。
【０１８４】
このブロック符号化部１２０５の符号化処理の詳細は後述するが、概要を説明すれば次の通りである。
１．着目ストライプ中の未処理の４×４画素ブロックのうち、最も左に位置するブロックから右方向に向かう順番に、各ブロックの符号化データを生成する。
２．符号化対象の１つの４×４画素ブロックを着目ブロックとしたとき、相対的に左、上、左上の処理済みブロック（近傍ブロック）の中に、着目ブロックと同一のブロックが存在するかを判定する。そして、存在する場合には、存在することを示すと共に、着目ブロックを何度回転させた場合に一致するかを示す判定情報を符号化データとして、符号列メモリ１２０４に出力する。着目ブロックの上、及び、左上のブロックは、ストライプメモリＢ１２０３に格納されている。
【０１８５】
ステップＳ１３０６では、制御部１２０９は、ブロック符号化部１２０６に対し、符号化処理を行なわせる。但し、ブロック符号化部１２０６の符号化対象は、ステップＳ１３０５にて、着目ブロックと同一のブロックが近傍ブロック内に存在しないと判定された４×４画素ブロックである。つまり、着目ストライプ中の全４×４画素ブロックが、それぞれの近傍ブロックと同一であった場合、このステップＳ１３０６の処理は行なわない。ブロック符号化部１２０６の符号化処理は次の通りである。
１．符号化対象の４×４画素のブロックを４つの２×２画素のブロックに分割する。誤解を招かないようにするため、この２×２画素のブロックを以降、サブブロックと呼ぶ。
２．４つのサブブロックをラスタースキャン順に符号化していく。
３．符号化対象の１つの２×２画素のサブブロックを着目サブブロックとしたとき、相対的に左、上、左上の処理済みサブブロック（近傍サブブロック）の中に、着目サブブロックと同一のブロックが存在するかを判定する。そして、存在する場合には、存在することを示すと共に、着目サブブロックを何度回転させた場合に一致するかを示す判定情報を符号化データとして、符号列メモリ１２０４に出力する。着目ブロックの上、及び、左上のブロックは、ストライプメモリＡ１２０２、Ｂ１２０３に格納されている。
【０１８６】
ステップＳ１３０７では、制御部１２０９は、画素符号化部１２０７に対し、符号化処理を行なわせる。但し、画素符号化部１２０７の符号化対象は、ステップＳ１３０６にて、着目サブブロックと同一のサブブロックが近傍サブブロック内に存在しないと判定された２×２画素のサブブロックである。また、画素符号化部１２０７は生成した符号化データを符号列メモリ１２０４に格納する。なお、画素符号化部１２０７は、既に説明したように予測誤差符号化処理である。
【０１８７】
ステップＳ１３０８では、ストライプカウンタｉが“５”であるか否か、すなわち、着目ストライプが着目タイルの最後のストライプであるか否かを判定する。否の場合には、ステップＳ１３０９にて、制御部１２０９は、ストライプメモリＡ１２０２内のデータを、ストライプメモリＢ１２０３にコピーする。そして、制御部１２０９は、ステップＳ１３１０にて、ストライプカウンタｉを“１”だけ増加させ、ステップＳ１３０２の処理に戻る。
【０１８８】
一方、着目タイルの全ストライプの符号化処理が終了したと判断した場合、処理はステップＳ１３１１に進む。制御部１２０９は、符号列メモリ１２０４に格納された１タイル中の４×４画素のブロック（全部で３６個）の判定情報の符号化データ、２×２画素のサブブロックの判定情報の符号化データ、及び、画素符号化部１２０７で生成された符号化データを連結する。この連結により、符号列を形成する。そして、ステップＳ１３１２にて、生成された符号列を、着目タイルの符号化データとして出力する。
【０１８９】
次に、上記ステップＳ１３０５の処理の詳細を図２９のフローチャートに従って説明する。同図は、制御部１２０９のブロック符号化部１２０５に対する処理手順でもある。
【０１９０】
先ず、ステップＳ１４０１にて、４×４画素のブロックの初期位置を設定する。着目ストライプがタイルの先頭ストライプである場合には、２つ目の画素ブロックが初期位置となる。また、着目ストライプが２番目以降のストライプの場合には、左端を着目ブロックの初期値として設定する。
【０１９１】
次に、ステップＳ１４０２にて、着目ブロックと、その近傍の処理済のブロックとを、着目ブロックを回転させながら順次比較し、着目ブロックと同じブロックが近傍ブロック内にあるか否かをサーチする。図３１の「＊」印が着目ブロックの位置とした場合、近傍のブロックはＢａ（着目ブロックの左側のブロック）、Ｂｂ（着目ブロックの真上のブロック）、Ｂｃ（着目ブロックの左上のブロック）の３つである。
【０１９２】
なお、着目ブロックが、タイルの先頭ストライプ内にあるとき、近傍ブロックＢｂ，Ｂｃはタイル外となる。この場合、着目ブロックと比較する対象はブロックＢａのみとする。また、着目ブロックがストライプの左端にある場合、ブロックＢａはタイル外となる。この場合、着目ブロックと比較する対象はブロックＢｂのみとする。
【０１９３】
また、着目ブロックを回転する際の回転角は０度（回転無し）、９０度、１８０度、２７０の４通りである。
【０１９４】
さて、ステップＳ１４０３では、ステップＳ１４０２のサーチ処理の結果、着目ブロックと同一ブロックが近傍ブロック内に存在したか否かを判定する。存在しなかった場合には、ステップＳ１４０４にて、着目ブロックのブロック符号化情報（判定情報）として１ビットの“０”を出力する。
【０１９５】
また、ステップＳ１４０３にて、着目ブロックと同一のブロックが近傍ブロック内に存在すると判定した場合には、処理はステップＳ１４０６、Ｓ１４０７の処理を行なう。すなわち、着目ブロックと一致すると判定した近傍ブロックの位置（方向）を示す情報を生成するとともに、着目ブロックを何度回転させた場合に一致するのかを示す情報を生成し、これらの情報を着目ブロックのブロック符号化情報（判定情報）としてを出力する。
【０１９６】
ここで、ステップＳ１４０３、Ｓ１４０６，Ｓ１４０７において生成される符号化データは、図３２（ａ），（ｂ）に示すテーブルに従って決定される。
【０１９７】
図３２（ａ）は、着目ブロックと同一のブロックが近傍ブロックＢａ，Ｂｂ，Ｂｃ内に存在するか否か、存在する場合にはどの近傍ブロックであるかを示す符号語テーブルである。
【０１９８】
着目ブロックと同一のブロックが存在しない場合には、図３２（ａ）に従い“０”を出力し、着目ブロックの処理を終える。
【０１９９】
一方、着目ブロックと同一のブロックが近傍ブロックＢａ，Ｂｂ，Ｂｃ内に存在する場合、その近傍ブロックを特定する図３２（ａ）の符号語を出力する。次いで、その一致すると判定した近傍ブロックに対し、回転後の着目ブロックの回転角を示す符号語を図３２（ｂ）の符号語テーブルを参照して出力する。例えば、着目ブロックを如何なる回転角で回転させても近傍ブロックＢａと等しくはならず、着目ブロックを９０度回転させた場合に近傍ブロックＢｂと等しくなったとする。この場合、ステップＳ１４０６、Ｓ１４０７で生成される着目ブロックの符号化データは、二進で“１０１０１”となる。
【０２００】
さて、上記のようにして着目ブロックについてのブロック判定処理に基づく符号化データの出力を終えると、ステップＳ１４０８にて、着目ブロックがストライプの右端にあるか否かを判断する。否の場合にはステップＳ１４０９にて、着目ブロックの位置を４画素分だけ右方向に移動し、ステップＳ１４０２の処理を行なう。
【０２０１】
一方、着目ブロックがストライプの右端位置あると判断した場合には、１ストライプ分の処理が終了したことになるので、本処理を終える。
【０２０２】
以上のようにして画像データの符号化処理が行われる。ここで、１つのタイルの符号化データのデータ構造の一例を図３３に示す。同図は、先に示した図１１における１ブロック分の符号化データの内容に相当するものでもある。
【０２０３】
実施形態では、１タイルのサイズを２４×２４画素としているので、その中には４×４画素のブロックが３６個存在する。従って、先ず、３６個の４×４画素のブロックの符号化データが配置される。図３０に示した様に、１タイルの最初（左上隅）の４×４画素のブロックについては、予測誤差符号化処理が行われる。従って、図３３に示すように、最初の４×４画素の符号化データは、予測誤差符号化データとなる。２番目以降の４×４画素のブロックの符号化データは、近傍ブロックに一致するか否か、一致する場合にはどの近傍ブロックであり、回転角は何度であるかを示す判定情報が格納される。この４×４画素の符号化データに後続して、２×２画素のサブブロックの符号化データが配置される。２×２画素のサブブロックの数は、４×４画素ブロックについて近傍ブロック内に一致すブロックが発見できなかった数×４である。そして、最後に、２×２画素のサブブロック内の予測誤差符号化データが配置される。
【０２０４】
以上説明したように本第３の実施形態によれば、ブロック単位に符号化する際に、着目ブロックを回転させた上で、符号化済みの画像データ領域内に同一の画像が存在するか否かを判定する。この結果、着目ブロックと一致するブロックが発見できる可能性がくなり、圧縮率を向上させることが可能になる。
【０２０５】
なお、第３の実施形態では、ブロックのサイズを４×４画素、２×２画素の２種類の例を示したが、この数に限定されるものではない。例えば、８×８画素、４×４画素、２×２画素としても構わない。要するに、下限サイズにまで分割され、且つ、その下限サイズの着目ブロックと同じ画像が、符号化済みの画像データ領域内に存在しない場合に、着目ブロックを画素単位の符号化を行なうようにすればよい。
【０２０６】
また、本第３の実施形態における着目ブロックと同一の画像が、符号化済みの画像データ領域に内に存在するか否かを示す符号語の生成を、第１、第２の実施形態に適用しても構わないのは、明らかである。
【０２０７】
さらにまた、本第３の実施形態における復号装置は、第１の実施形態における復号装置とほぼ同じである。異なる点は、着目ブロックと着目ブロックと一致するブロックが存在する場合、符号化データにはその一致するブロックを特定する情報と回転角が含まれる。従って、符号化済みの画像データから該当サイズと位置の画像データを読出し、回転角だけ逆に回転した結果を、復号結果として出力すればよい。
【０２０８】
また、本第３の実施形態は、先の第１の実施形態の変形例と同様、コンピュータプログラムでもって実現することができることも明らかである。
【０２０９】
以上本発明に係る実施形態を説明した。
【０２１０】
上記実施形態によれば、例えば、画像データを符号化する画像符号化装置は、以下の構成を備える。即ち、ブロック単位に画像データを入力する入力手段を備える。また、着目ブロックの全画素が同一色かを判定し、同一色の場合にはそれを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックが非同一色の画素を含む場合には非同一色を示す符号化データを出力する第１の符号化手段を備える。また、上記非同一色を示す場合、着目ブロックと同じ画像が、既に符号化処理された画像領域内に存在するか判定し、非存在を示す情報か、存在を示すと共に存在位置の情報を符号化データとして出力する第２の符号化手段を備える。また、該第２の符号化手段で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段を備える。また、着目ブロックのサイズが、下限サイズであると判定した場合、着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化手段を備える。また、着目ブロックが下限サイズよりも大きいと判定した場合、着目ブロックが複数のサブブロックで構成されるものとし、サブブロックのサイズを新たなブロックのサイズとして設定し、第１、第２の符号化手段による符号化を再帰的に実行する制御手段を備える。
【０２１１】
また、例えば、上記入力手段で入力するブロックのサイズが初期の最大サイズである場合、入力したブロック内に含まれる色数を判定する色数判定手段を備える。また、初期サイズのブロック内の画像データをラスタースキャンし、予測誤差符号化を行い、符号化データの生成及び出力を行なう第４の符号化手段を備える。また、判定した色数が予め設定された閾値よりも大きい場合には、入力したブロックを第４の符号化手段に供給し、色数が予め設定された閾値である場合、判定手段、第１、第２の符号化手段による符号化データの生成と出力を行なわせるスイッチ手段を備える。
【０２１２】
また、例えば、画像符号化装置で生成された符号化データを復号する画像復号装置は、以下の構成を備える。即ち、符号化データを入力する第２の入力手段を備える。また、入力した符号化データが着目ブロック内の全画素が同一色を示している場合、後続する符号化データは前記着目ブロック内の色を示す情報とし、着目ブロックを構成する全画素データが前記色を持つものとして出力する第１の復号手段を備える。また、符号化データが着目ブロック内の全画素が非同一色を示し、後続符号化データが、復号済み画像データの領域内に着目ブロックと同一のブロックが存在することを示す場合、前記同一のブロックの画像データを出力する第２の復号手段を備える。また、前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しない示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定手段を備える。また、第２の判定手段が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第３の復号手段を備える。また、着目ブロックが下限サイズより大きいと判定した場合、着目ブロックが複数のサブブロックで構成されるものとし、サブブロックのサイズを新たなブロックのサイズとし、第１、第２の符号化手段による符号化を再帰的に実行する第２の制御手段を備える。
【０２１３】
また、これらの中には、コンピュータに、コンピュータプログラムを実行させる例も説明した。通常、コンピュータプログラム等のソフトウェアは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されている。そして、そのコンピュータ可読記憶媒体を、コンピュータが読取り可能なデバイスにセットし、その上で、システムにコピーもしくはインストールという手順を踏む。従って、このようなコンピュータ可読記憶媒体も本発明の範疇にあることは明らかである。
【図面の簡単な説明】
【０２１４】
【図１】第１の実施形態に係る画像符号化装置のブロック構成図である。
【図２】ブロック情報管理メモリ１０７に格納されるブロック管理テーブルのデータ構造を示す図である。
【図３】図１におけるブロック符号化部１０４でのブロック符号化の処理手順を示すフローチャートである。
【図４】第１の実施形態における初期ブロックと、分割されたブロックとの関係を示す図である。
【図５】着目ブロックリストの一例を示す図である。
【図６】同一色判定と、同一ブロックの判定に用いる符号木を示す図である。
【図７】同一ブロックの位置を符号化する際に用いる符号木を示す図である。
【図８】着目ブロックを４つのサブブロックに分割した際の、着目ブロックと各サブブロックの座標との関係を示す図である。
【図９】予測誤差ｅとグループ番号ＳＳＳＳとの対応テーブルを示す図である。
【図１０】グループ番号ＳＳＳＳと符号語との対応テーブルを示す図である。
【図１１】符号列形成部１０５から出力される符号化画像データのデータ構造を示す図である。
【図１２】第１の実施形態における符号化対象の画像ブロックの一例を示す図である。
【図１３】図１２の画像ブロックの符号化データの例を示す図である。
【図１４】図１２の画像ブロックを符号化する際に、ブロック情報管理メモリ１０７に構築されたブロック管理テーブルの例を示す図である。
【図１５】第１の実施形態における画像符号化処理のメイン処理を示すフローチャートである。
【図１６】第１の実施形態における画像復号装置のブロック構成図である。
【図１７】図１６におけるブロック復号部２０４でのブロック復号の処理手順を示すフローチャートである。
【図１８】第１の実施形態における画像復号装置のメイン処理を示すフローチャートである。
【図１９】第１の実施形態の変形例におけるコンピュータのブロック構成図である。
【図２０】第２の実施形態における画像符号化装置のブロック構成図である。
【図２１】第２の実施形態の画像符号化装置が生成する符号化データのデータ構造を示す図である。
【図２２】第２の実施形態における画像符号化処理のメイン処理を示すフローチャートである。
【図２３】第２の実施形態における画像復号装置のブロック構成図である。
【図２４】第２の実施形態における画像復号装置のメイン処理を示すフローチャートである。
【図２５】第１、第２の実施形態におけるブロック比較の変形例を示す図である。
【図２６】第３の実施形態における画像データの符号化対象のタイルとストライプとの関係を示す図である。
【図２７】第３の実施形態における画像符号化装置のブロック構成図である。
【図２８】第３の実施形態における画像符号化処理のメイン処理を示すフローチャートである。
【図２９】図２８のステップＳ１３０５の詳細を示すフローチャートである。
【図３０】第３の実施形態における１つのタイルに含まれる４×４画素のブロックの配列とストライプ番号との関係を示す図である。
【図３１】第３の実施形態におけるブロック符号化を行なう際の着目ブロックと参照する近傍ブロックの相対位置関係を示す図である。
【図３２】第３の実施形態のブロック符号化の際に参照する符号化テーブルを示す図である。
【図３３】第３の実施形態における１タイルの符号化データのデータ構造を示す図である。
【技術分野】
【０００１】
本発明は、画像の符号化及び復号技術に関するものである。
【背景技術】
【０００２】
従来、画像の符号化、復号を行う画像処理装置を構成する一手法として予測符号化をベースとするものがある。予測符号化は、画像データを予測変換により予測誤差へと変換する系列変換部と、系列変換部から出力される予測誤差をハフマン符号化等のエントロピー符号化を用いて、より冗長性の少ない符号化データへと変換するエントロピー符号化部とによって構成される。
【０００３】
ＩＳＯとＩＴＵ−Ｔから国際標準の静止画像符号化方式として勧告されるＪＰＥＧではＬｏｓｓｌｅｓｓ Processとして予測符号化をベースとした可逆符号化方式が規定されている（非特許文献１）。以下、これをＪＰＥＧ可逆符号化モードと呼ぶ。
【０００４】
ＪＰＥＧ可逆符号化モードでは、近傍画素から着目画素の値を予測する方法として７つの予測式を規定しており、画像に応じて予測方法を選択できるようになっている。ＪＰＥＧ可逆モードでは符号化対象の画像データをラスタースキャン順に符号化する。各画素を定められた予測方式により予測し、その予測誤差をハフマン符号、または算術符号により順次符号化していく。ハフマン符号化を用いる場合には予測誤差の１つに対して１ビット以上が出力されるため、文字、線画、ＣＧ画像など人工的で、同一画素や同一パターンの連続が多く見られる画像に対しては高い圧縮性能を得ることができない。
【０００５】
一方、ＪＰＥＧ標準化の後、ＩＳＯとＩＴＵ−Ｔから新たに国際標準勧告された可逆符号化方式ＪＰＥＧ−ＬＳ Ｂａｓｅｌｉｎｅ（非特許文献２）では、予測符号化とランレングス符号化とを組み合わせて符号化システムが勧告されている。これは、周囲画素の状態によって予測方法、確率モデルを変えるなどの工夫により、自然画像での圧縮性能を向上するものである。すなわち、ランレングス符号化の採用により、複数画素を一纏めにして符号化することができ、上述のような文字、線画、ＣＧ画像などに対しても、ＪＰＥＧ可逆符号化モードよりも高い符号化性能を得ることができる。
【非特許文献１】ＩＴＵ−Ｔ Ｔ．８１｜ＩＳＯ／ＩＥＣ１０９１８−１
【非特許文献２】ＩＴＵ−Ｔ Ｔ．８７｜ＩＳＯ／ＩＥＣ１４４９５−１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述のＪＰＥＧ−ＬＳを用いた従来の装置では、水平方向に同じ値を持つ画素が連続する場合には効率良く圧縮きるが、垂直方向に同じ値を持つ画素が連続する場合にはランレングス符号化が適用されず、効率良く圧縮できない。
【０００７】
また、同じパターンの繰り返しがある場合、画像の構成自体は単純であっても、効率良い圧縮性能を得ることはできない。
【０００８】
本願発明は、上述の問題点に鑑みてなされたものであり、文字、線画、ＣＧ画像など、同一画素値や同一パターンの連続の多い画像に対しても効率良く符号化する技術、および復号する技術を提供しようとするものである。
【課題を解決するための手段】
【０００９】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像データを符号化する画像符号化装置であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力手段と、
着目ブロックの画像データの全画素が同一色である否かを判定し、同一色である場合には同一色であることを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックの画像データが非同一色の画素を含んでいると判定した場合には非同一色を示す符号化データを出力する第１の符号化手段と、
該第１の符号化手段で出力される符号化データが、前記非同一色を示している場合、前記着目ブロックの画像データと同じ画像データが、既に符号化処理された画像データ領域内に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す情報を符号化データとして出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第２の符号化手段と、
該第２の符号化手段で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段と、
該判定手段で前記着目ブロックのサイズが、前記下限サイズであると判定した場合、当該着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化手段と、
前記判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記入力手段に設定し、前記第１、第２の符号化手段による符号化を再帰的に実行する制御手段とを備える。
【発明の効果】
【００１０】
本発明の構成によれば、文字、線画、ＣＧ画像など、同一画素値の連続、または、同一パターンの連続を多く含む画像に対して高い圧縮率で符号化データを生成することができる。
【発明を実施するための最良の形態】
【００１１】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００１２】
＜第１の実施形態＞
図１は本実施形態に係る画像符号化装置のブロック構成図である。
【００１３】
本実施形態の画像符号化装置は、画像入力部１０１、ストライプバッファ１０２、ブロック切り出し部１０３、ブロック符号化部１０４、符号列形成部１０５、符号出力部１０６、ブロック情報管理メモリ１０７、装置全体の制御を司る制御部１１０を備える。
【００１４】
以下、図１を参照して、本実施形態の画像符号化装置の各構成要素とその処理内容を説明する。
【００１５】
本実施形態に係る画像符号化装置の符号化対象とする画像データは、Ｒ、Ｇ、Ｂの３つのコンポーネント（成分）で構成されるカラー画像データとする。１画素を構成する各コンポーネントは、８ビット（２５６階調）とする。符号化対象の画像データの並びは点順次、即ち、ラスタースキャン順に各画素が並べられており、各画素のコンポーネントはＲ，Ｇ，Ｂ順に並べられて構成されるものとする。すなわち、Ｒ、Ｇ、Ｂ、Ｒ、Ｇ、Ｂ…のデータの並びで構成されているものとする。また、説明を簡単なものとするため、実施形態では、符号化対象の画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。また、実施形態における画像符号化装置は、符号化対象画像データから水平方向Ｂｗ画素、垂直方向Ｂｈ画素のブロックに分割してブロック単位に符号化を行う。ブロックのサイズＢｗ、Ｂｈは様々な値とすることができるが、以下の説明ではＢｗ＝Ｂｈ＝３２として説明する。また、説明を簡易にするため、画像の水平方向画素数Ｗ、垂直方向画素数Ｈは、それぞれ３２の整数倍の大きさであるとし、ブロックに分割した場合に不完全なブロックは発生しないものとして説明する。
【００１６】
さて、画像入力部１０１は、符号化対象の画像データをラスタースキャンし、Ｂｈ個のライン（３２ライン分）の画像データを入力し、ストライプバッファ１０２に出力（格納）する。１ラインはＷ画素で構成されるので、画像入力部１０１はＢｈ×Ｗ画素分の画像データをストライプバッファ１０２に格納することになる。１画素は３バイトで表現されるので、結局のところ、ストライプバッファ１０２は、最低でも、３２×Ｗ×３バイトの容量を備えることになる。以降、このストライプバッファ１０２に格納されるＢｈライン分の画像データをストライプデータと呼ぶ。
【００１７】
ストライプバッファ１０２に３２ライン分の画像データ（ストライプデータ）が格納されたとする。この場合、ブロック切り出し部１０３はストライプバッファ１０２に格納されるストライプデータについて、左端から右端に向かって、高さＢｈ、幅Ｂｗのブロックの画像データ（３２×３２画素）を順に切り出して、内部の不図示の記憶領域に格納する。この３２×３２画素のサイズは、後述する説明から明らかになるように、最大サイズでもある。
【００１８】
ブロック情報管理メモリ１０７は、ブロック符号化部１０４におけるブロックデータの符号化の過程で必要となるブロック情報を管理するための記憶領域を有する。この記憶領域には、図２（ａ）乃至（ｄ）に示すようにブロックサイズ“３２”，“１６”，“８”，“４”のそれぞれについてブロック管理テーブルが確保される。なお、ここで言うブロックサイズ“３２”とは、３２×３２の正方ブロックの１辺の長さを示しているものである点に注意されたい。これは、他のブロックサイズも同様である。
【００１９】
各ブロックサイズ毎のブロック管理テーブルのエントリ数はそれぞれに異なる。ブロックサイズ“３２”のブロック管理テーブルのエントリ数は１つ、ブロックサイズ“１６”のエントリ数は最大で４つ、ブロックサイズ“８”のエントリ数は最大で１６、ブロックサイズ“４”のエントリ数は最大で６４である。これは、３２×３２画素のブロックは、４つの１６×１６画素のブロック、または、１６個の８×８画素のブロック、又は、６４個の４×４画素のブロックに対応するためである。
【００２０】
以降の説明では、現在着目するブロックサイズと同じブロックサイズのブロック管理テーブルを、着目ブロックリストと呼び、その１／２の大きさのブロックサイズのブロック管理テーブルをサブブロックリストと呼ぶ。また、ブロック管理テーブルに格納される情報については後述する。
【００２１】
ブロック符号化部１０４は、ブロック切り出し部の内部に格納される３２×３２画素のブロックデータ（以降、初期ブロックと呼ぶ）を符号化する度に、ブロック情報管理メモリ１０７内の各サイズ別のブロックリストを初期化する。そして、ブロック符号化部１０４は、符号化過程でブロックリストの登録と、その登録したブロックリストを参照しながら、符号化データを生成し、出力する。
【００２２】
図３はブロック符号化部１０４における符号化処理の流れを示すフローチャートである。以下、同図を参照して、ブロック符号化部１０４によるブロックデータの符号化処理の全体的な流れについて説明する。
【００２３】
ブロック符号化部１０４はその内部に、着目ブロックの大きさ（水平／垂直方向画素数）を保持する変数ＳＩＺＥと、着目ブロックの左上隅の座標（以降、始点座標と呼ぶ）ベクトルＢを備える。着目ブロックは、このＳＩＺＥと始点座標のベクトルＢの組で特定する。始点座標は初期ブロック（符号化単位となる３２×３２のブロック）の左上隅を原点（０，０）として、水平方向ｘ画素、垂直方向ｙ画素の位置をベクトル（ｘ、ｙ）で表現する。
【００２４】
図４に示した太線の矩形は初期ブロックであり、このブロックの始点座標はＢ＝（０，０）、大きさＳＩＺＥ＝３２である。また、これを４分割して得られる斜線領域を着目ブロックとする場合、その始点座標Ｂ＝（１６，０）であり、ＳＩＺＥ＝１６となる。
【００２５】
符号化の開始時には、先ず、ステップＳ１０００にて、変数ＳＩＺＥに“３２”を設定する。次いで、ステップＳ１００１において、変数Ｎｍａｘに“１”を設定する。この変数Ｎｍａｘは、変数ＳＩＺＥで示されるエントリ数を格納するためのものである。ＳＩＺＥ＝３２の場合、エントリ数は“１”であるため、ステップＳ１００１では変数ＳＩＺＥに“１”を設定することになる。
【００２６】
次に、ステップＳ１００２にて、ブロック情報管理メモリ１０７に、ＳＩＺＥ＝３２のブロックリスト（エントリ数＝１）を登録する。次いで、ステップＳ１００３にて、変数ｉに初期値として“０”を設定し、ステップＳ１００４にて、着目ブロックから派生するサブブロックのエントリ数を格納する変数ＳＵＢｉを“０”で初期化する。
【００２７】
ステップＳ１００５では、ブロック切り出し部１００３から、変数ＳＩＺＥで示される第ｉ番目のブロック（着目ブロック）を入力し、着目ブロック内の全画素が同一色を示しているか否かを判定する。換言すれば、着目ブロック内の色数が“１”である否かを判定すると言い換えても良い。なお、ここでは、全画素が同一色であるか否かを判断するものであるから、ブロック内をスキャンして、着目画素の色と直前の画素の色が異なった場合には、少なくとも２色以上存在することを示しているので、それ以降のスキャンは不要である。同一色（色数が“１”）である場合には二進データ“１”、非同一色（色数が“２”以上）である場合には二進データ“０”を出力する（ステップＳ１００６）。
【００２８】
この後、ステップＳ１００７にて、変数ｉで示される着目ブロックの全画素が同一色（色数が“１”）であったか否か、すなわち、ステップＳ１００６で出力した二進データが“１”であったか否かを判定する。同一色（色数が“１”）であった場合には、ステップＳ１００８に進み、その色を示す画素データ（Ｒ、Ｇ、Ｂ値）を出力し、着目ブロックの処理を終えるため、ステップＳ１０１８に処理を進める。
【００２９】
つまり、着目ブロック内の全画素が同一色を示している場合、ステップＳ１００６、及び、ステップＳ１００８によって生成される着目ブロックの符号化データは、
“１”＋Ｒ、Ｇ、Ｂデータ（各８ビット）
のデータ構造（計２５ビット）となる。
【００３０】
一方、ステップＳ１００７にて、着目ブロック内の色数が“２”以上であると判定した場合、処理をステップＳ１００９に進める。このステップＳ１００９では、変数ｉの値が“０”であるか否か、すなわち、着目ブロックが着目ブロックリストに登録した先頭ブロックであるか否かを判断する。
【００３１】
着目ブロックが登録したブロックリストの先頭ブロックである場合には比較対象が存在しないので、処理はステップＳ１０１４に進める。
【００３２】
ここで、変数ｉが“０”以外である場合に、すなわち、着目ブロックは、変数ＳＩＺＥで定義されるブロックリストの２番目以降のブロックであるものとして説明する。この場合、ステップＳ１０１０にて、着目ブロックリストに登録された符号化処理済みのブロック（１つ又は複数）と着目ブロックとの比較処理を行ない、その結果をステップＳ１０１１にて出力する。
【００３３】
例えば、着目ブロックリストが図５のような状態にあり、変数ｉ＝３、すなわち、着目ブロックがブロック番号「３」であったとする。この場合、ブロック番号「２」、「１」、「０」の順番（降順）で着目ブロックと同一ブロックか否かを判定する。
【００３４】
ここで仮に、着目ブロックが、ブロック番号「２」のブロックとは同一でないが、ブロック番号「１」と同一であったとする。この場合には、先ず、着目ブロックと同一のブロックが存在したことを示す二進データ“１”を出力する。また、ブロック番号「２」、「１」、「０」の順番に、画像領域における既に符号化処理済みブロックと着目ブロックとを比較し、いずれとも一致しなかった場合には、同一ブロック無し（非存在）を示す二進データ“０”を出力する。
【００３５】
ここまでの処理により出力されるデータを２分木構造にして示したのが図６（ａ），（ｂ）である。
【００３６】
着目ブロックが変数ＳＩＺＥで示されるブロックリストの先頭にあるとき、図６（ａ）に従い、着目ブロック内の全画素が同一色（色数が“１”）を示すか否かの判定結果を出力する。特に、同一色である場合には、この判定結果に後続して同一色となった画素の各成分値を出力する。
【００３７】
また、着目ブロックが変数ＳＩＺＥで示されるブロックリストの２番目以降の場合、図６（ｂ）に従い、着目ブロック内の全画素が同一色を示すか否かの判定結果を出力する。特に、同一色（色数が“１”）である場合には、この判定結果に後続して同一色となった画素の各成分値を出力するのは、図６（ａ）と同様である。また、非同一色（色数が“２”以上）である場合には、先ず、二進データ“０”を出力した後、既に処理済みのブロック内に着目ブロックと同一のブロックが存在するかを示す二進データ“０”か“１”かのいずれか一方を出力する。
【００３８】
さて、ステップＳ１０１２に処理が進むと、着目ブロックと同一ブロックが処理済みブロック内に存在したか否か、すなわち、ステップＳ１０１１での出力が“１”であったか否かを判定する。着目ブロックと同一ブロックが処理済みブロック内に存在したと判断した場合には、ステップＳ１０１３に進み、同一であると判定したブロック番号を特定する情報を出力し、ステップＳ１０１８９進む。
【００３９】
このステップＳ１０１３の処理内容を図７の符号木を用いて説明する。図中、変数ｉは着目ブロックリストにおける着目ブロックの番号を表している。図に示すように、符号木は着目ブロックの番号ｉによって変化し、ブロック番号ｉの場合にはｉ個のリーフノードを持つ符号木が用いられる。着目ブロック番号を「ｉ」とし、それに一致するブロック番が仮に「ｊ」（０≦ｊ＜ｉ）であるとした場合、「ｉ−ｊ−１」個の“０”を出力し、その後に“１”を出力する。
【００４０】
例えば、図５におけるブロック番号「３」が着目ブロックであり、その着目ブロックと同一のブロックのブロック番号が「１」であるとする。この場合、ステップＳ１０１３で出力する二進データは“０１”となる。ステップＳ１００６で二進データ“０”、ステップＳ１０１１にて二進データ“１”を出力しているわけであるから、着目ブロックの符号化データは、結局のところ、二進データ“０１０１”となる。
【００４１】
つまり、着目ブロック内の色数が２以上であり、尚且つ、着目ブロックと同一のブロックが存在する場合、着目ブロックの符号化データは、
“０１”＋同一ブロックを特定するデータ
のデータ構造となる。ここで、「同一ブロックを特定するデータ」は、０個以上の“０”＋“１”のデータである。
【００４２】
また、ステップＳ１００９にて、変数ｉが“０”である場合には、着目ブロックはブロックリストの先頭ブロックであるので、比較対象の処理済みブロックは存在しない。そのため、ステップＳ１０１４にて、一致するブロックが存在しないことを示す“０”を出力し、ステップＳ１０１５に処理を進める。
【００４３】
このステップＳ１０１５に処理が進んだ場合、ステップＳ１００６で二進データ“０”が出力され、ステップＳ１０１１又はステップＳ１０１４で二進データ“０”が出力された場合である。すなわち、ステップＳ１０１５に処理が進むのは、着目ブロック内の色数が２以上であり、尚且つ、着目ブロックと同一のブロックが存在しない場合となる点に注意されたい。
【００４４】
ステップＳ１０１５では、変数ＳＩＺＥが“４”であるか否か、すなわち、着目ブロックリストがＳＩＺＥ＝４のブロックリストであるか否かを判断する。これは、着目ブロックが処理の下限サイズであるか否かを判断しているとも言える。
【００４５】
変数ＳＩＺＥが“４”以外（ＳＩＺＥが８、１６、３２のいずれか）であると判断した場合には、着目ブロックは下限サイズよりも大きいことになる。そこで、ステップＳ１０１６にて、着目ブロックを構成する４つのサブブロックを、ＳＩＺＥ／２で示されるブロックリストに登録する。また、ステップＳ１０１７にて、サブブロックの個数を更新するため、変数ＳＵＢｉを“４”だけ増加させる。そして、ステップＳ１０１９に処理を進める。
【００４６】
例えば、図８に示すごとく、サイズＳＩＺＥ＝Ｌの着目ブロックの始点座標をＢ=（ｂｘ、ｂｙ）としたとき、その着目ブロックを構成する４つのサブブロックの各始点座標Ｂ０〜Ｂ３は次のように定義できる。
Ｂ０＝（ｂｘ、ｂｙ）
Ｂ１＝（ｂｘ＋Ｌ／２、ｂｙ）
Ｂ２＝（ｂｘ、ｂｙ＋Ｌ／２）
Ｂ３＝（ｂｘ＋Ｌ／２、ｂｙ＋Ｌ／２）
これらブロックを、ＳＩＺＥ／２で示されるブロックリストに追加登録する。なお、登録する４つのサブブロックのサイズは、着目ブロックのサイズの水平、垂直方向の画素数の１／２である。また、このサブブロックを登録する以前に、既にいくつかのサブブロックが登録されている場合には、今回登録するサブブロック番号は、最後に登録したブロック番号＋１から割り当てる。
【００４７】
また、ステップＳ１０１５にて、変数ＳＩＺＥが“４”であると判断した場合、すなわち、着目ブロックのサイズが下限サイズであると判断した場合、ステップＳ１１０８に進める。このステップＳ１０１８では、着目ブロック内の各画素データの符号化処理を行ない、その符号化データを出力する。そして、ステップＳ１０１９に処理を進める。
【００４８】
ブロック内の画素の符号化方法としては予測符号化、変換符号化など様々な手法を用いて良い。本実施の形態ではその一例として簡易な予測符号化を用いる方法を示す。以下は、その予測符号化処理の説明である。
【００４９】
まず、着目ブロック（４×４画素のサイズである）内（もしくは着目サブブロック内）の左上隅の画素の成分値をそのまま出力する。その後、着目ブロック内をラスタースキャンしていく。この過程での着目画素の色成分と、前置予測値（前符号化画素の同一成分値）との差分を予測誤差ｅとして算出し、その予測誤差ｅを符号化する。予測誤差ｅはＪＰＥＧ可逆符号化モードと同様に、まず、図９から予測誤差ｅの属するカテゴリＳＳＳＳを得て、これを図１０のハフマンテーブルで符号化する。続いて、カテゴリの中のどの値かを特定するための長さＳＳＳＳビットの付加ビットを出力する。予測誤差ｅが正である場合、付加ビットは予測誤差ｅの下位ＳＳＳＳビットであり、負である場合には予測誤差ｅ−１の下位ＳＳＳＳビットを取り出したものである。以上のようにして、着目ブロック内の各画素の符号化が行われる。
【００５０】
つまり、着目ブロック内の色数が“２”以上であり、着目ブロックと同一のブロックが存在せず、尚且つ、着目ブロックが下限サイズである場合の着目ブロックの符号化データは、
“００”＋予測誤差符号化データ
のデータ構造となる。
【００５１】
さて、処理がステップＳ１０１９に処理が進むと、着目ブロックを次のブロックに更新するあめ、変数ｉを“１”だけ増加する。そして、ステップＳ１０２０にて、変数ｉと変数Ｎｍａｘとを比較する。ｉ＜Ｎｍａｘである場合、着目ブロックリスト中に、未処理のブロックが存在することになるので、ステップＳ１００５以降の処理を行なう。なお、ＳＩＺＥ＝３２の場合、Ｎｍａｘ＝１であるので、ステップＳ１０２０の判定は必ず「Ｎｏ」となり、ステップＳ１０２１に処理が進む。
【００５２】
ステップＳ１０２１では、登録したサブブロックの個数ＳＵＢｉが“０”よりも多いか否かを判断する。ＳＵＢｉ＝０であると判断した場合、処理すべきサブブロックが存在しないことになるので、本処理を終える。
【００５３】
また、少なくとも１つのサブブロック（実際は４の整数倍）が登録されていると判断した場合、処理はステップＳ１０２２に進み、そのサブブロックの処理を行なうため、変数ＳＩＺＥを１／２に設定する。すなわち、変更後の変数ＳＩＺＥで示されるブロックリストを着目ブロックリストとして設定する。そして、ステップＳ１０２３にて、エントリの上限をＳＵＢｉとするため、変数ＮｍａｘにＳＵＢｉを代入し、ステップＳ１００３以降の処理を行なう。
【００５４】
以上、説明した処理により、ブロック符号化部１０４において、ブロック切り出し部１０３の内部に保持される初期ブロックの符号化が行われ、ブロックの符号化データが符号列形成部１０５へと出力される。
【００５５】
符号列形成部１０５は画像の水平方向／垂直方向の画素数、画素を構成する成分の数、各成分の精度など、画像の復号に必要な付加情報を有するヘッダを先ず生成する。そして、符号列形成部１０５は、ブロック符号化部１０４から出力される符号化データをヘッダに後続するデータとして、所定のフォーマットの符号列を形成し、符号出力部１０６に出力する。図１１に符号列形成部１０５から出力される符号列の構成の一例を示す。先頭のＨｅａｄｅｒ部分に付加情報が格納され、続いてラスタースキャン順の各ブロックの符号化データが並ぶ。符号出力部１０６は符号列形成部１０５から出力される符号列を装置外部へと出力を行う。
【００５６】
ここで、上記の符号化処理をより分かりやすく説明する。
【００５７】
説明を簡単なものとするため、３２×３２画素の初期ブロックの画像が図１２のようになっているものとする。また、ブロック情報管理メモリ１０７にブロックリストとして登録する各ブロックをＢＬＫ（ＳＩＺＥ，ブロック番号）として表現することとする。
【００５８】
ここで３２×３２画素中、右上隅の幅４画素、高さ１６画素の領域以外の領域（白色領域）では、全て同一色であるものとする。また、右上隅の幅４画素、高さ１６画素の領域中のブロックＢＬＫ（４，１）、ＢＬＫ（４，３）、ＢＬＫ（４，５）は互いに異なる色又はパターンとなっており、ブロックＢＬＫ（４，５）とＢＬＫ（４，７）は互いに同じ色の同じパターンであるものとする。
【００５９】
図１３は、図１２の３２×３２画素のブロックの符号化データのデータ構造を示している。この符号化データは、図１１における１つのブロック（３２×３２画素）分の符号化データを示してもいる。
【００６０】
以下、図１２の３２×３２画素の画像データから、図１３に示す１ブロック分の符号化データが生成される手順を説明する。
【００６１】
＜ＳＩＺＥ＝３２の処理＞
初期サイズ（３２×３２画素）に着目すると、その内部の色数が“１”ではない。従って、ＳＩＺＥ＝３２の同一色判定の判定結果により出力される二進データは“０”（ステップＳ１００６の出力）となる。また、初期サイズの場合、変数ｉが“０”の場合にだけ処理がなされる。すなわち、着目ブロックを処理する以前に処理されたブロックせず、ブロック間の一致判定も行なわない。従って、着目ブロックの符号化データは、同一色判定の判定結果である“０”のみとなる。
【００６２】
なお、初期サイズの着目ブロックに対しては、４分割したサブブロックをＳＩＺＥ＝１６に対応するサブブロックに登録する。このとき、登録する４つのサブブロックは、図１２の場合、ＢＬＫ（１６，０）、ＢＬＫ（１６，１）、ＢＬＫ（１６，２）、ＢＬＫ（１６，４））である。なお、ＢＬＫ（１６，１）は、図１２では示されていないが、右上隅の１６×１６画素の領域である。
【００６３】
ところで、もし３２×３２画素の全てが同一色である場合、符号語は「“１”＋Ｒ、Ｇ、Ｂの値」で計２５ビットの符号化データを生成し、ＳＩＺＥ＝１６、８、４の符号化処理は行なわない。
【００６４】
＜ＳＩＺＥ＝１６の処理＞
未符号化として登録されたＳＩＺＥ＝１６のブロックをラスタースキャン順に評価する。すなわち、ＢＬＫ（１６、０）→ＢＬＫ（１６、１）→ＢＬＫ（１６、２）→ＢＬＫ（１６，３）の順番に判定処理を行なう。
【００６５】
先ず、ブロックＢＬＫ（１６，０）に着目する。このブロックＢＬＫ（１６，０）内の全画素は同一色であるので、符号語「“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００６６】
次に、ブロックＢＬＫ（１６，１）に着目する。このブロックＢＬＫ（１６，１）は、その内部の色数が“２”以上であり、既に処理したブロックＢＬＫ（１６，０）とも一致しない。従って、着目ブロックＢＬＫ（１６、１）については、判定情報として“００”を出力する。また、着目ブロックＢＬＫ（１６、１）を構成する４つの８×８画素のサブブロックＢＬＫ（８，０）、ＢＬＫ（８，１）、ＢＬＫ（８，２），ＢＬＫ（８、３）をＳＩＺＥ＝８のブロックリストに登録する。
【００６７】
次に、ブロックＢＬＫ（１６，２）に着目する。このブロックＢＬＫ（１６，２）内の全画素は同一色であるので、「符号語“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）として出力する。
【００６８】
次に、ブロックＢＬＫ（１６，３）に着目する。このブロックＢＬＫ（１６，３）内の全画素は同一色であるので、「符号語“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００６９】
＜ＳＩＺＥ＝８の処理＞
未符号化として登録されたＳＩＺＥ＝８のブロックをラスタースキャン順に評価する。すなわち、ＢＬＫ（８、０）→ＢＬＫ（８、１）→ＢＬＫ（８、２）→ＢＬＫ（８，３）の順番に判定処理を行なう。
【００７０】
先ず、ブロックＢＬＫ（８，０）に着目する。このブロックＢＬＫ（８，０）内の全画素は同一色であるので、符号語「“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００７１】
次に、ブロックＢＬＫ（８，１）に着目する。このブロックＢＬＫ（８，１）は、その内部の色数は“２”以上であり、既に処理したブロックＢＬＫ（８，０）とも一致しない。従って、着目ブロックＢＬＫ（８、１）については、判定情報として“００”を出力する。また、着目ブロックＢＬＫ（８、１）は分割対象とし決定し、それを構成する４つの４×４画素のサブブロックＢＬＫ（４，０）、ＢＬＫ（４，１）、ＢＬＫ（４，２），ＢＬＫ（４、３）をＳＩＺＥ＝４のブロックリストに登録する。
【００７２】
次に、ブロックＢＬＫ（８，２）に着目する。このブロックＢＬＫ（８，２）内の全画素データは同一色であるので、符号語「“１”＋Ｒ、Ｇ、Ｂの値」を判定情報（符号化データ）を出力する。
【００７３】
次に、ブロックＢＬＫ（８，３）に着目する。このブロックＢＬＫ（８，３）は、その内部の色数は“２”以上であり、既に処理したブロックＢＬＫ（８，２）、ＢＬＫ（８，１）、ＢＬＫ（８，０）のいずれとも一致しない。従って、着目ブロックＢＬＫ（８、３）については、判定情報として“００”を出力する。また、着目ブロックＢＬＫ（８、３）を構成する４つの４×４画素を、ＳＩＺＥ＝４のブロックリストに登録する。ＳＩＺＥ＝４のブロックリストには、ブロックＢＬＫ（８、１）に対する処理で、既に４つのブロックが登録されている。従って、着目ブロックＢＬＫ（８，３）を４分割して登録するブロックはＢＬＫ（４，４）、ＢＬＫ（４，５）、ＢＬＫ（４，６），ＢＬＫ（４、７）となる。つまり、ＳＩＺＥ＝４のブロックリストには、計８個のブロックが登録される。
【００７４】
＜ＳＩＺＥ＝４の処理＞
未符号化として登録されたＳＩＺＥ＝４のブロックをラスタースキャン順に評価する。すなわち、ＢＬＫ（４、０）→ＢＬＫ（４、１）→ＢＬＫ（４、２）→…→ＢＬＫ（４，６）→ＢＬＫ（４，７）の順番に判定処理を行なう。
【００７５】
ＢＬＫ（４，０）、ＢＬＫ（４，２）、ＢＬＫ（４，４）、ＢＬＫ（４，６）は、それぞれの内部の画素が同一色であるので、それぞれの判定情報は「“１”＋Ｒ、Ｇ、Ｂの値」となるのは、これまでの説明から明らかである。従って以下では、ＢＬＫ（４、１）、ＢＬＫ（４，３）、ＢＬＫ（４，５）、ＢＬＫ（４，７）について説明する。
【００７６】
ブロックＢＬＫ（４，１）に着目する。このブロックＢＬＫ（４，１）内の色数は“２”以上であり、且つ、既に処理したブロックＢＬＫ（４，０）とも一致しない。従って、着目ブロックＢＬＫ（４、１）については、判定情報として“００”を出力する。ただし、実施形態では、ＳＩＺＥ＝４を下限としているので、後続して着目ブロックＢＬＫ（４，１）の可逆符号化データを生成し、出力する。
【００７７】
ブロックＢＬＫ（４，３）に着目する。このブロックＢＬＫ（４，３）内の色数は“２”以上であり、且つ、既に処理したブロックＢＬＫ（４，２）、ＢＬＫ（４，１）、ＢＬＫ（４，０）のいずれとも一致しない。従って、着目ブロックＢＬＫ（４、３）については、判定情報として“００”を出力し、後続して着目ブロックＢＬＫ（４，１）の可逆符号化データを生成し、出力する。
【００７８】
ブロックＢＬＫ（４，５）に着目する。このブロックＢＬＫ（４，５）内の色数は“２”以上であり、且つ、既に処理したブロックＢＬＫ（４，４）、ＢＬＫ（４，３）、ＢＬＫ（４，２）、ＢＬＫ（４，１）、ＢＬＫ（４，０）のいずれとも一致しない。従って、着目ブロックＢＬＫ（４、５）については、判定情報として“００”を出力し、後続して着目ブロックＢＬＫ（４，５）の可逆符号化データを生成し、出力する。
【００７９】
ブロックＢＬＫ（４，７）に着目する。このブロックＢＬＫ（４，７）内の色数は“２”以上である。しかしながら、着目ブロックＢＬＫ（４，７）のパターンは、既に処理したブロックＢＬＫ（４，５）のパターンと一致する。従って、着目ブロックＢＬＫ（４、７）の判定情報（符号化データ）の先頭の２ビットは“０１”となる。また、それに後続して、ブロックＢＬＫ（４、５）を特定する情報（図示の場合には、“０１”）を付加する（図７参照）。
【００８０】
以上の結果、３２×３２画素のブロックが、図１２に示す状態である場合、図１３に示す符号化データを生成することが可能になる。
【００８１】
図１４（ａ）乃至（ｄ）は、図１２に示す３２×３２画素のブロックの符号化処理が完了したときの、ブロック情報管理メモリ１０７に作成された各サイズ別の管理テーブルを示している。図１４（ａ）は、ＳＩＺＥ＝３２のブロックリストを示し、１つのブロックだけが登録されている。図１４（ｂ）は、ＳＩＺＥ＝１６のブロックリストを示し、４つのブロックが登録されている。図１４（ｃ）は、ＳＩＺＥ＝８のブロックリストを示し、４つのブロックが登録されている。図１４（ｄ）は、ＳＩＺＥ＝４のブロックリストを示し、８つのブロックが登録されている。各サイズのブロックリストとそれらに登録されているブロック数は、図１３の符号化データのデータ構造と一致している。
【００８２】
図１５は、本実施形態に係る画像符号化装置の制御部１１０による符号化対象画像データの符号化処理の手順を示すフローチャートである。
【００８３】
まず、画像入力部１０１から符号化対象画像の３２ライン分が入力され、ストライプバッファ１０２へと格納される（ステップＳ１７０１）。ブロック切り出し部１０３ではストライプバッファ１０２に格納されるストライプデータの左から右へ、順番に３２×３２の大きさのブロックを一つずつ取り出してブロック切り出し部の内部に格納する（ステップＳ１７０２）。続いて、ステップＳ１７０３ではブロック情報管理メモリ１０７に保持されている各サイズ毎のブロック管理テーブルを初期状態にする。初期状態において、各ブロック管理テーブルは空の状態である。ブロック管理情報の初期化が終了すると、ブロック符号化部１０４にて、ブロック情報管理メモリ内のブロック管理テーブルを更新しながらブロックの符号化が行われる。ステップＳ１７０４の処理の流れは、先に説明した図３の通りである。着目するブロックの符号化を終えると、符号化したブロックがストライプデータの最後のブロックであるか否かを判断し（ステップＳ１７０５）、最後のブロックでない場合（ＮＯ）にはステップＳ１７０２に処理を戻して次のブロックについて同様に処理を行う。最後のブロックである場合（ＹＥＳ）にはステップＳ１７０６へと処理を移す。ステップＳ１７０６では、符号化したストライプが画像の最終ストライプであるか否かを判断し、最後のストライプでない場合（ＮＯ）にはステップＳ１７０１へと処理を戻し、次のストライプについて同様に処理を継続する。最後のストライプであった場合（ＹＥＳ）にはステップＳ１７０７に移り、符号列形成部１０５から所定のフォーマットの符号化データが出力され、符号出力部１０６から装置外部へと出力される。
【００８４】
以上の処理により、画像データの符号化処理が行われる。様々な大きさのブロックで周囲の符号化済みのブロックとの一致／不一致を符号化することにより、文字、線画、ＣＧ画像など、同じ画素配置のパターンが多く出現する画像に対し、高い圧縮性能の可逆符号化を実現できる。なお、本実施形態の画像処理装置ではブロック単位に独立の符号化が行われているため、部分的な復号や、並列符号化／復号をも可能になる。
【００８５】
次に、上記の画像符号化装置で生成された符号化画像データを復号する復号装置について説明する。
【００８６】
実施形態における画像復号装置のブロック構成図を図１６に示す。本装置は、符号入力部２０１、符号バッファ２０２、ヘッダ解析部２０３、ブロック復号部２０４、ブロック情報管理メモリ２０５、ブロック書き出し部２０６、ストライプバッファ２０７、画像出力部２０８、及び、装置全体の制御を司る制御部２１０を備える。
【００８７】
以下、図１６を参照して、本実施形態に係る画像復号装置が行う処理について説明する。
符号入力部２０１は、復号対象となる符号化画像データを入力し、符号バッファ２０２に格納する。この符号化画像データは、記憶媒体に格納されていても構わないし、ネットワークを介して入力しても構わず、その入力源の種類は問わない。
【００８８】
ヘッダ解析部２０３は符号バッファ２０２に格納される符号化データのヘッダ部分を解析し、画像の水平方向／垂直方向の画素数、画素を構成する成分の数、各成分の精度など、復号に必要な付加情報を抽出する。制御部２１０は、この付加情報に基づき、各構成要素に復号に必要な設定を行ない、復号処理を開始させる。
【００８９】
ブロック復号部２０４は符号バッファ２０４から符号データを読み出して、３２×３２画素の画像データを復号を開始する度に、ブロック情報管理メモリ２０５を初期化する。そして、その初期化後に、ブロック情報管理メモリ２０５を更新しながら、ブロック書き出し部２０６内のメモリに格納された画像データを参照し、各サイズのブロックを復号していく。復号して得られた各サイズのブロックデータはブロック書き出し部２０６の内部バッファに格納する。そして、３２×３２画素の画像データが復号できたら、その画像データをストライプバッファ２０７に格納する。画像出力部２０８は、１ストライプ分の画像データが、ストライプバッファ２０７に格納される度に、そのストライプ画像データを復号結果として出力する。
【００９０】
図１７はブロック復号部２０４における復号処理の流れを示すフローチャートである。基本的に、復号処理は、符号化処理とは逆の処理となる。以下、同図を参照して、ブロック復号部２０４によるブロックデータの復号処理の全体的な流れについて説明する。
【００９１】
ブロック復号部１０４は、図１におけるブロック符号化部１０４と同様に、その内部に、着目ブロックの大きさ（水平／垂直方向画素数）を保持する変数ＳＩＺＥと、着目ブロックの左上隅の座標（以降、始点座標と呼ぶ）ベクトルＢを備える。復号の開始時には、符号化時と同じく、ステップＳ４０１にて、変数ＳＩＺＥを「３２」で初期化する。次いで、ステップＳ４０２にて、変数Ｎｍａｘに“１”を設定する。
【００９２】
次に、ステップＳ４０３にて、ブロック情報管理メモリ１０７に、ＳＩＺＥ＝３２のブロックリスト（エントリ数＝１）を登録する。次いで、ステップＳ４０４にて、変数ｉに初期値として“０”を設定し、ステップＳ４０５にて、着目ブロックから派生するサブブロックのエントリ数を格納する変数ＳＵＢｉを“０”で初期化する。以上で、符号化処理を開始する際の初期の処理が終了する。
【００９３】
次に、ステップＳ４０６に進み、符号化バッファ２０２から先頭の１ビットである、同一色の判定情報を入力し、その判定情報が“１”であるか否かを判断する。同一色判定情報が“１”である場合、ステップＳ４０７に進み、同一色の判定情報に後続するＲＧＢの各成分値を符号化バッファ２０２から入力する。そして、ステップＳ４０８にて、着目ブロックに含まれる個数分だけ、入力したＲＧＢデータを繰り返し出力することで、着目ブロックの復号処理を行なう。この後、処理はステップＳ４１５に進める。
【００９４】
また、ステップＳ４０６にて、同一色判定情報が“０”であると判定した場合、処理はステップＳ４０９に進む。このステップＳ４０９では、符号化バッファ２０２から、１ビットの同一パターン符号化データを入力し、それが“１”であるか否かを判断する。同一パターン符号化データが“１”であると判断した場合、同一パターン符号化データの直後のビットから、最初に“１”となるデータが、着目ブロックと同一パターンの位置を特定する情報である。従って、その間の“０”の個数で特定される位置の復号済みのブロックのデータを、ブロック書き出し部２０６から探し出し、そのブロックのデータを着目ブロックのデータとして出力する。この後、処理はステップＳ４１５に進める。
【００９５】
また、ステップＳ４０９にて、同一パターン符号化データが“０”であると判断した場合、処理はステップＳ４１１に進める。このステップＳ４１１では、変数ＳＩＺＥが“４”であるか否か、すなわち、着目ブロックが下限サイズであるか否かを判断する。
【００９６】
変数ＳＩＺＥが“４”以外（ＳＩＺＥ＝８、１６、３２のいずれか）である場合には、ステップＳ４１２にて、着目ブロックを構成する４つのサブブロックを登録する。そして、変数ＳＵＢｉを“４”だけ増加させる。
【００９７】
また、ステップＳ４１１にて、変数ＳＩＺＥが“４”であると判断した場合、処理はステップＳ４１４に進める。このステップＳ４１４では、同一パターン符号化データに後続するデータは、予測誤差符号化データであるものとして、符号化バッファ２０２から読込み、復号処理を行ない、その復号結果の４×４画素の画像データをブロック書き出し部２０６に出力する。そして、処理をステップＳ４１５に進める。
【００９８】
ステップＳ４１４では、先に説明した符号化と逆の手順で着目ブロックの画素値を復号する。まず、左上隅の画素の各成分値をそのまま取り出し、その後、着目ブロック内をラスタースキャン順に、前置を予測値とした予測誤差を復号し、前置と加算することにより各画素値を復号する。予測誤差はＪＰＥＧ可逆符号化モードの復号と同様に、まず、図９から予測誤差ｅの属するカテゴリＳＳＳＳを復号し、続いて、ＳＳＳＳビットの付加ビットを取得して、カテゴリの中のどの値かを特定する。このように復号された各画素の値はブロック書き出し部２０６の内部の、着目ブロックに対応する記憶領域に順次格納される。
【００９９】
さて、上記のようにして処理がステップＳ４１５に進むと、変数ｉを“１”だけ増加させる。そして、ステップＳ４１６にて、変数ｉと変数Ｎｍａｘとを比較する。ｉ＜Ｎｍａｘである場合、着目ブロックリスト中に、未処理のブロックが存在することになるので、ステップＳ４０６以降の処理を行なう。
【０１００】
また、ｉ＝Ｎｍａｘであると判断した場合には、処理をステップＳ４１７に進める。ここのステップＳ４１７では、変数ＳＵＢｉが“０”よりも多いか否かを判断する。ＳＵＢｉ＞０であると判断した場合、処理はステップＳ４１８に進み、そのサブブロックの処理を行なうため、変数ＳＩＺＥを１／２に設定する。すなわち、変更後の変数ＳＩＺＥで示されるブロックリストを着目ブロックリストとして設定する。そして、ステップＳ４１９にて、エントリの上限をＳＵＢｉとするため、変数ＮｍａｘにＳＵＢｉを代入し、ステップＳ４０４以降の処理を行なう。
【０１０１】
また、ステップＳ４１７にて、変数ＳＵＢｉが“０”であると判断した場合、３２×３２画素で構成されるブロックの復号処理が終了したものとし、本処理を終える。
【０１０２】
以上、説明した処理により、ブロック復号部２０４において、１つのブロックの復号が行われ、ブロック書き出し部２０６の内部にブロックのデータが格納される。
【０１０３】
ブロック書き出し部２０６は、その内部に、ブロック復号部２０４によるブロックの復号処理により生成された画像データを格納する内部メモリ（３２×３２画素分のメモリ）を有する。そして、内部メモリに３２×３２画素分の画像データが格納されると、その画像データをストライプバッファ２０７に出力する。
【０１０４】
図１８は、本実施形態に係る画像復号置による制御部２１０による復号処理の全体の流れを示すフローチャートである。以下、同図を参照して、本実施形態に係る画像処理装置が行う画像符号化処理の全体的な流れについて説明する。
【０１０５】
まず、符号入力部２０１から復号対象となる符号化データが符号バッファ２０２に入力され、ヘッダ解析部２０３で符号化データのヘッダを解析して復号に必要な付加情報を取り出す（ステップＳ３０１）。ヘッダの解析が終了すると、ブロック情報管理メモリ２０５の内部に格納されているブロック管理テーブルを初期化する（ステップＳ３０２）。初期状態でブロック管理テーブルは空の状態である。ブロック復号部２０４は、符号バッファ２０２に格納されている符号を読み出して、ブロック情報管理メモリに格納されているブロック管理テーブルを更新しながら１つの３２×３２画素の画像データを復号する。そして、ブロック復号部２０４は、その画像データを、ブロック書き出し部２０６の内部バッファに書き込む（ステップＳ３０３）。ブロック復号部２０４の動作については先に図１７を用いて説明した通りである。
【０１０６】
ブロック復号部２０６によるブロックデータの復号が終了し、ブロック書き出し部２０６の内部バッファにブロックデータが格納されると、ブロック書き出し部２０６はこれをストライプバッファ２０７へと転送する。ブロックデータは、ストライプバッファの左から右へ順に並べて書き込まれる。復号したブロックデータがストライプの最後のブロックであるか否かを判断し（ステップＳ３０５）、ストライプの最後のブロックでない場合（ＮＯ）は、処理をステップＳ３０２へと移して次のブロックの復号を行う。ストライプの最後のブロックであった場合（ＹＥＳ）にはストライプバッファ２０７に格納されたストライプデータをラスタースキャン順に読み出して、画像出力部２０８から装置外部へと出力する（ステップＳ３０６）。ステップＳ３０７では、出力したストライプデータが画像の最後のストライプデータであるか否かを判断する。最終ストライプでない場合（ＮＯ）はステップＳ３０２へと処理を移し、次のストライプの復号処理を継続して行う。このとき、ストライプバッファ２０７はクリアされており、また、左端から次のブロックデータを格納していく。
【０１０７】
以上の処理により、符号化データから元の画像データを完全に復元することができるようになる。
【０１０８】
以上説明したように本実施形態によれば、文字、線画、ＣＧ画像など、同一画素値や同一パターンの連続の多い画像に対しても効率良く可逆符号化することが可能になり、オリジナル画像を可逆復元することも可能になる。
【０１０９】
なお、実施形態では、符号化処理における初期のブロックサイズを３２×３２画素とし、サブブロックのサイズを１６×１６、８×８、４×４の４段階としたが、これらのサイズ、段階数によって本発明が限定されるものではない。また、各ブロック（サブブロック）のサイズも必ずしも正方である必要もない。また、１つのブロックが４つのサブブロックで構成されるものとしたが、必ずしも４つではなくても構わない。要するに、１つのブロックを、再帰的にｐ×ｑ個（ｐ，ｑは２以上の整数）のサブブロックに再帰的に分割できるようにすればよい。ただし、サブブロックのサイズの下限は、実施形態の如く４×４画素程度の、ある程度のサイズであることが望ましい。
【０１１０】
また、上記実施形態の場合、着目ブロック（または着目サブブロック）内の全画素が同一である場合、同一色であることを示す情報（実施形態では“１”）に後続して、その色を示す画素データ（Ｒ、Ｇ、Ｂの２４ビット）を付加させた。この結果、着目する３２×３２画素の画像データが、図１２に示すような場合、サブブロック
ＢＬＫ（１６，０）、ＢＬＫ（１６，２）、ＢＬＫ（１６，３）、ＢＬＫ（８，０）、ＢＬＫ（８，２）、ＢＬＫ（４，０）、ＢＬＫ（４，２）、ＢＬＫ（４，４）、ＢＬＫ（４，６）
の符号化データは、いずれも、
「“１”＋Ｒ，Ｇ，Ｂ」
の形式となり、冗長となってしまう（図１３参照）。
【０１１１】
そこで、同一色の画素のみで構成されると判断した最初のサブブロック（図１２の場合にはＢＬＫ（１６，０）の符号化データについては
「“１”＋Ｒ，Ｇ，Ｂ」
という形式にする（以下、このサブブロックを同一色起源サブブロックという）。そして、それ以降で同一色の画素のみで構成されるサブブロックについては、そのサブブロック内の画素の各成分値と、同一色起源サブブロックの各成分値との差分を演算し、その差分を符号化すつようにしても構わない。
【０１１２】
図１２の場合、サブブロックＢＬＫ（１６，０）が同一色起源サブブロックとなり、それ以外の
ＢＬＫ（１６，２）、ＢＬＫ（１６，３）、ＢＬＫ（８，０）、ＢＬＫ（８，２）、ＢＬＫ（４，０）、ＢＬＫ（４，２）、ＢＬＫ（４，４）、ＢＬＫ（４，６）
の各成分は差分を符号化する。差分が小さいほど短い符号語を割り当てるようにすると、符号化効率は格段に高くなる。
【０１１３】
なお、上記実施形態では、１つのブロック内の画像データを符号化する際に、そのブロック内の全画素が同じ色を示すか否かを判定したが、この同一色判定とその符号化データの生成は省略しても構わない。ただし、この場合、各ブロックの符号化データの先頭には、着目ブロックの画像データと同一の画像データが既に符号化された画像データの領域内に存在するか否かを示す１ビットを配置するようにする。そして、同一ブロックが存在する場合には先頭の“１”に後続して、同一ブロックの位置を特定する符号語を格納すればよい。
【０１１４】
＜第１の実施形態の変形例＞
上記第１の実施形態と同様の処理は、コンピュータプログラムによって実現できる。以下、その例を第１の実施形態の変形例として説明する。
【０１１５】
図１９は、本変形例における情報処理装置（例えばパーソナルコンピュータ）のブロック構成図である。
【０１１６】
図中、１４０１はＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理、復号処理のアプリケーションプログラムを実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。また、ＲＡＭ１４０２は、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。
【０１１７】
１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７はハードディスクドライブ装置等の大容量の外部記憶装置である。この外部記憶装置１４０７には、ＯＳ（オペレーティングシステム）や後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象画像の符号化データなどがファイルとして保存されている。また、ＣＰＵ１４０１は、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードし、実行することになる。
【０１１８】
１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象の画像の符号化データなどを記録しておいても良い。この場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。
【０１１９】
１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えは符号化対象の画像データや、復号対象の画像の符号化データなどを本装置のＲＡＭ１４０２や外部記憶装置１４０７、あるいは記憶媒体ドライブ１４０８に入力することもできる。１４１０は上述の各部を繋ぐバスである。
【０１２０】
上記構成において、本装置の電源がＯＮになると、ＣＰＵ１４０１はＲＯＭ１４０３のブートプログラムに従って、外部記憶装置１４０７からＯＳをＲＡＭ１４０２にロードする。この結果、キーボード１４０４、マウス１４０５の入力が可能となり、表示装置１４０６にＧＵＩを表示することが可能になる。ユーザが、キーボード１４０４やマウス１４０５を操作し、外部記憶装置１４０７に格納された画像処理用アプリケーションプログラムの起動の指示を行なうと、ＣＰＵ１４０１はそのプログラムをＲＡＭ１４０２にロードし、実行する。これにより、本装置が画像符号化装置又は画像復号装置として機能することになる。
【０１２１】
画像符号化装置として機能する場合には、図１に示した各種バッファ、テーブルはＲＡＭ１４０２に格納に確保し、各処理部に相当する機能はＣＰＵ１４０１が実行する関数やサブルーチンとして機能させればよい。そして、ＣＰＵ１４０１は、上記第１の実施形態で示した各フローチャートに従った処理を行なえばよいのは明らかである。これは画像復号装置として機能させる場合にも言えることである。
【０１２２】
以上説明した様に、本変形例に従えば、第１の実施形態に相当する処理をコンピュータプログラムによっても実現できるのは明らかであろう。
【０１２３】
＜第２の実施形態＞
上記第１の実施形態の画像処理装置では、全てのブロックをブロック符号化部１０４で符号化する構成とした。文字、線画、ＣＧ画像では、或る領域について着目すると、その領域内の全画素が同一画素値である確率が高いし、同一画素配置パターンが繰り返し出現する確率も高い。従って、上記第１の実施形態は、文字、線画、ＣＧ画像については効率の良い可逆符号化データを生成することができる。
【０１２４】
しかしながら、自然画像（風景画や人物画）の場合、隣接する２画素の間の差は小さくなる可能性が高いものの、隣接する２画素が完全に一致することはむしろ希である。従って、着目ブロック内の全画素が同一色となる確率、及び、着目ブロックと同一パターンを持つ処理済みブロックの存在する確率は共に小さなものとなる。つまり、上記第１の実施形態の技術を自然画に適用した場合、初期ブロックサイズ（３２×３２画素）の多くの部分が下限サイズ（４×４画素）にまで分割した後、可逆符号化することになり、符号化効率が下がる可能性が高い。
【０１２５】
そこで、第３の実施形態としてブロック単位に画像の特性を判定し、ブロックの一致判定を用いた符号化と、これを用いない画素単位の予測符号化とを切り替える例を説明する。これにより、文字、線画、ＣＧ画像と自然画像が混在するような画像でも効率良く符号化することを目指す。
【０１２６】
本第２の実施形態の画像符号化装置の構成を図２０に示す。第１の実施形態の構成である図１と異なる点は、色数判定部１８０１、スイッチ１８０２、ブロック予測符号化部１８０３が追加された点と、符号列形成部１０５に代わって符号列形成部１８０４となった点である。それ以外の構成要素は、第１の実施形態と同じであるので、同参照番号を付し、その説明は省略する。
【０１２７】
なお、図２０に示す構成はハードウェアにより実現しても良いが、本第２の実施形態では、先に説明した第１の実施形態の変形例と同様に、図２０に示す各部の機能をコンピュータに実現させるプログラムによって実現しても構わない。この場合、そのプログラムは図１９の外部記憶装置１４０７や記憶媒体ドライブ１４０８、もしくはＩ／Ｆ１４０９を介して外部装置からＲＡＭ１４０２にロードされ、ＣＰＵ１４０１が実行することになる。
【０１２８】
以下、図２０を参照して、本第２の実施形態に係る画像符号化装置が行う画像符号化処理について説明する。
本第２の実施形態に係る画像処理装置の符号化対象とする画像データは、第１の実施形態と同じく、ＲＧＢの多値のカラー画像データであり、各コンポーネント（色成分）は８ビット（２５６階調）の輝度値を表現した画素データにより構成されるものとする。符号化対象の画像データの並びは点順次、即ち、ラスタースキャン順に各画素を並べ、その各画素はＲ、Ｇ、Ｂの順番のデータで構成されるものとする。また、画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。
【０１２９】
以下、第１の実施形態と同じ動作のブロックについては説明を省略し、本第２の実施形態で特徴的な処理部についてのみ説明する。
【０１３０】
色数判定部１８０１はブロック切り出し部１０３の内部に格納される３２×３２画素のブロックデータについて、そのブロック内の出現する色の種類数を色数Ｎｃとして計数する。そして、色数判定部１８０１は、色数Ｎｃと予め定められた閾値Ｔｈとを比較し、Ｎｃ＞Ｔｈである場合（色数が閾値よりも大きい場合）には「１」、Ｎｃ≦Ｔｈである場合（色数が閾値以下の場合）には「０」の判定信号を生成し、その判定信号をスイッチ１８０２及び符号列形成部１８０４に出力する。なお、閾値Ｔｈの値は、符号化対象の画像のサイズに応じて設定することが望ましい。本第２の実施形態ではＴｈ＝３２として説明する。
【０１３１】
この色数判定部１８０１の目的は、ブロックの特性に応じて、後述するブロック予測符号化部１８０３とブロック符号化部１０４とを切り替えることにある。すなわち、文字、線画、ＣＧ画像では使用されている色数は少ない傾向にあり、また、自然画像では多くの色数が使用される傾向にある。判定部１８０１は、この性質を利用して、符号化対象のブロックが文字、線画、ＣＧの画像であるか、自然画であるかを判定していると言うこともできる。本第２の実施形態の画像処理装置では色数によって処理対象ブロックが、文字、線画、ＣＧの画像であるか、自然画であるかを判断するものとしているが、この判断は一例であることに留意願いたい。例えば、別の実施形態として、ブロック内での同一画素値の連続数や、ブロック内画素のヒストグラムの形状から判別してもよいであろう。
【０１３２】
スイッチ１８０２は色数判定部１８０１から出力される制御信号によって、ブロック単位に画像データの供給先を切り替える。色数判定部１８０１からの制御信号が「０」である場合、すなわち、着目している３２×３２画素の画像が文字、線画、ＣＧの属性を持つと判断した場合、スイッチを端子ｂ側に接続し、画像データをブロック符号化部１０４に供給する。
【０１３３】
また、色数判定部１８０１からの制御信号が「１」である場合、すなわち、着目している３２×３２画素の画像が自然画属性を持つと判断した場合、スイッチを端子ａ側に接続し、画像データをブロック予測符号化部１８０３に供給する。
【０１３４】
ブロック予測部１８０３はスイッチ１８０２が端子ａ側に接続された場合に、ブロック切り出し部１０３に格納される３２×３２画素のブロックデータを、サブブロックに分割すること無しに、符号化する。従って、各サブブロックの同一色判定情報、同一パターンの有無情報が無くなる。ブロック予測符号化部１８０３におけるブロックデータの符号化には予測符号化が用いられる。ブロック切り出し部１０３に格納されるブロックデータの各画素をラスタースキャン順に、各画素Ｒ，Ｇ，Ｂの順番で成分値を読み出して順番に符号化していく。着目する画素を符号化する場合には、着目画素の近傍に位置し、既に符号化された複数の近傍画素を参照し、着目画素の着目色成分の予測値ｐを求める。そしして、着目画素の成分値と予測値ｐとの差分値を算出し、その差分値を符号化する。
【０１３５】
着目画素の水平方向（右方向）の座標値ｘ、垂直（下方向）の座標値ｙとし、着目画素の座標を（ｘ，ｙ）と定義したとき、３つの近傍画素を利用する場合、それら近傍画素の座標は（ｘ−１，ｙ）、（ｘ，ｙ−１）、（ｘ−１，ｙ−１）とする。そして、着目画素の着目色成分Ｃ（ＣはＲ、Ｇ、Ｂのいずれか）の値をＰ（ｘ、ｙ、Ｃ）と表現したとき、予測値ｐは例えば次のようにして求める。
ｐ＝Ｐ(x-1,y,C)＋Ｐ(x,y-1,C)−Ｐ(x-1,y-1,C)
【０１３６】
従って、予測誤差ｅは、
ｅ＝Ｐ(x,y)−ｐ
＝Ｐ(x,y)−｛Ｐ(x-1,y,C)＋Ｐ(x,y-1,C)−Ｐ(x-1,y-1,C)｝
となる。なお、着目画素が、ブロックデータの最初のライン上にある場合、予測値ｐ＝ａとする。また、着目画素が、ブロックデータの左端位置にある場合にはｐ＝ｂとする。そして、着目画素が、ブロックの最初の画素（最初のラインの左端位置）ではｐ＝１２８とする。ただし、これらの取り決めは、復号処理と同じすればよく、ここで示されるのは一例である点に留意願いたい。
【０１３７】
予測誤差はＪＰＥＧ可逆符号化モードと同様に、まず、図９から予測誤差ｅの属するカテゴリＳＳＳＳを得て、これを図１０のハフマンテーブルで符号化する。続いて、カテゴリの中のどの値かを特定するための長さＳＳＳＳビットの付加ビットを出力する。予測誤差ｅが正である場合、付加ビットは予測誤差ｅの下位ＳＳＳＳビットであり、負である場合には予測誤差ｅ−１の下位ＳＳＳＳビットを取り出したものである。
【０１３８】
本第２の実施形態の場合、３２×３２画素の符号化データは、ブロック予測符号化部１８０３、ブロック符号化部１０４のいずれか一方の符号化データとなる。従って、いずれの符号化データであるかを示す識別情報がないと、正しく復号できない。それ故、符号列形成部１８０４は、色数判定部１８０１からの判定信号（１ビットで良い）を、ブロックのヘッダに挿入する。
【０１３９】
符号列形成部１８０４は画像データの符号化処理を開始する際に、所定のフォーマットのヘッダ符号列を形成し、符号出力部１０６に出力する。ヘッダ符号列には、画像の水平方向／垂直方向の画素数、画素を構成する成分の数、各成分の精度など、画像の復号に必要な付加情報が含まれる。また、各ブロック毎に色数判定部１８０１から出力される判定結果をブロックヘッダとし、それに後続してブロック予測符号化部１８０３かブロック符号化部１０４のどちらか一方から出力されるブロックの符号化データを出力する。図２１に符号列形成部１０５から出力される符号列の構成の一例を示す。先頭のヘッダに付加情報が格納され、続いてラスタースキャン順の各ブロックの符号化データが並ぶが、その先頭（図中、斜線部分）に色数判定部１８０１から出力される判定結果が付与される。これにより復号側でも、２種類の符号化データを正しく復号することができる。
【０１４０】
図２２は、本第２の実施形態に係る画像符号化装置の制御部１１０の処理内容を示すフローチャートである。以下、同図を参照して、本実施形態に係る画像処理装置が行う画像符号化処理の全体的な流れについて説明する。
【０１４１】
まず、画像入力部１０１から符号化対象画像の３２ライン分が入力され、ストライプバッファ１０２へと格納される（ステップＳ２００１）。ブロック切り出し部１０３ではストライプバッファ１０２に格納されるストライプデータの左から右へ、順番に３２×３２の大きさのブロックを一つ取り出して、ブロック切り出し部１０３の内部メモリに格納する（ステップＳ２００２）。
【０１４２】
ブロック切り出し部１０３にブロックデータが格納されると、色数判定部１８０１によりブロック内の画素の種類の数を色数Ｎｃとして計数し（ステップＳ２００３）、Ｎｃ＞Ｔｈであるか否かを判定する（ステップＳ２００３）。
【０１４３】
Ｎｃ＞Ｔｈである場合（ＹＥＳ）、スイッチ１８０２が端子ａ側に接続され、ブロック予測符号化部１８０３によりブロック切り出し部１０３の内部に格納されている３２×３２画素のブロックデータの符号化が行われる（ステップＳ２００５）。
【０１４４】
一方、Ｎｃ≦Ｔｈである場合（ＮＯ）、スイッチ１８０２が端子ｂ側に接続される。その後、ブロック情報管理メモリ１０７を初期状態に設定し（ステップＳ２００６）、ブロック符号化部１０４によりブロックデータの符号化が行われる（ステップＳ２００７）。このステップＳ２００７の符号化処理は、先に説明した第１の実施形態と同じである。
【０１４５】
ステップＳ２００５又はＳ２００７にて生成される符号化データは符号列形成部１８０４へと出力される。符号列形成部１８０４は、色数判定部１８０１の色数判定結果、すなわち、Ｎｃ＞Ｔｈであるか、Ｎｃ≦Ｔｈであるかを示す１ビットの信号をブロックヘッダとして出力する。そして、符号列形成部１８０４は、それに後続して、ブロック予測符号化部１８０３又はブロック符号化部１０４のいずれか一方からの符号化データを出力する。
【０１４６】
ステップＳ２００８では符号化したブロックがストライプの最後のブロックであるか否かを判定し、最後のブロックでない場合（ＮＯ）にはステップＳ２００２へと処理を移し、次のブロックについて処理を行う。また、最後のブロックである場合（ＹＥＳ）、ステップＳ２００９へと処理を移す。このステップＳ２００９では、符号化したストライプが画像の最終ストライプであるか否かを判断し、最後のストライプでない場合（ＮＯ）にはステップＳ２００１へと処理を戻し、次のストライプについて同様に処理を継続する。
【０１４７】
また、最後のストライプであった場合（ＹＥＳ）にはステップＳ２０１０に移り、符号列形成部１８０４から所定のフォーマットの符号化データが出力され、符号出力部１０６から装置外部へと出力される。
【０１４８】
以上の処理により、画像データの符号化処理が行われる。自然画特性のブロックに対しては３２×３２画素のブロックで予測符号化を適用し、文字、線画、ＣＧ特性のブロックについては、様々な大きさのブロックで周囲の符号化済みのブロックとの一致／不一致を符号化することになる。この結果、２つの特性の混在する画像においても高い圧縮性能の可逆符号化を実現できる。なお、本実施形態の画像処理装置ではブロック単位に独立の符号化が行われているため、部分的な復号や、並列符号化／復号が可能という特徴がある。
【０１４９】
次に、第２の実施形態における画像復号装置について説明する。
【０１５０】
図２３は第２の実施形態における画像復号装置のブロック構成図である。本第２の実施形態における画像復号装置は、符号入力部２０１、符号バッファ２０２、ヘッダ解析部２０３、ブロック復号部２０４、ブロック情報管理メモリ２０５、ブロック書き出し部２０６、ストライプバッファ２０７を備える。また、画像出力部２０８、ブロック判定部２１０１、スイッチ２１０２、ブロック予測復号部２１０３、及び、装置全体の制御を司る制御部２１０とを備える。
【０１５１】
図２３の画像復号装置と、先に説明した第１の実施形態における図１９の画像復号装置との違いは、図１９の構成に、復号方式選択部２１０１、スイッチ２１０２、ブロック予測復号部２１０３が追加された点である。
【０１５２】
以下、図２３を参照して、本第２の実施形態に係る画像復号装置が行う処理について説明する。
【０１５３】
第１の実施形態と同様、符号入力部２０１は復号対象となる符号化データを入力し、その符号化データを符号バッファ２０２に適宜格納する。ヘッダ解析部２０３は、付加情報の取得を、復号に必要な情報を取得し、制御部２１０に出力する。制御部２１０は、この情報に基づき、各処理部に復号に必要な情報を設定する。
【０１５４】
ブロック判定部２１０１は、各ブロック（３２×３２画素の符号化データ）のヘッダに含まれる符号化データの種類を示す信号が“０”か“１”かを判定し、制御信号としてスイッチ２１０２に出力する。
【０１５５】
スイッチ２１０２は、ブロック判定部２１０１により出力されるを制御信号により、端子ａと端子ｂの何れかを選択接続する。
【０１５６】
制御信号が「０」である場合、端子ｂ側に接続し、符号化データをブロック復号部２０４に出力する。ブロック復号部２０４は、スイッチ２１０２が端子ｂを選択した場合に復号処理を開始する。そして、ブロック復号部２０４は、入力した符号化データを復号し、ブロック書き出し部２０６に復号結果である３２×３２画素の画像データを出力する。このブロック復号部２０４は第１の実施形態で説明した通りである。
【０１５７】
一方、制御信号が「１」である場合、スイッチ２１０２は端子ａを選択接続し、符号化データをブロック予測符号化復号部２１０３に出力する。ブロック予測復号部２１０３は、スイッチ２１０２が端子ａ側に接続される場合に処理を開始する。そして、入力した符号化データを復号し、３２×３２画素の画像データを生成し、ブロック書き出し部２０６に出力する。ブロック予測復号部２１０３のブロック復号処理は、第２の実施形態におけるブロック予測符号化部１８０３の逆の処理を行なう。ブロック予測符号化部１８０３の動作から、その復号処理は明らかであり、また、ＪＰＥＧ可逆符号化モードの復号処理と基本的に同じであるので、ここでは説明を省略する。
【０１５８】
ブロック書き出し部２０６は、上記の２つの復号部のいずれか一方から３２×３２画素分の画像データを入力した場合、その画像データをストライプバッファ２０７に格納する。この後の処理は第１の実施形態と同様である。
【０１５９】
図２４は、本第２の実施形態に係る画像復号装置の制御部２１０の処理手順を示すフローチャートである。以下、同図を参照して、本第２の実施形態に係る画像復号処理を説明する。
【０１６０】
まず、制御部２１０は、符号入力部２０１を制御して、復号対象となる符号化データを符号バッファ２０２に格納させる。そして、ヘッダ解析部２０３に、符号化データのヘッダを解析して復号に必要な付加情報を取り出させる（ステップＳ２２０１）。ヘッダの解析が終了すると、制御部２１０は、各ブロックの復号処理に必要な設定を行なう。
【０１６１】
次いで、制御部２１０は、ブロック判定部２１０１に、ブロック符号化データの先頭に格納される符号化データの種別を示す情報（Ｎｃ＞Ｔｈである場合には“１”、Ｎｃ≦Ｔｈである場合には“０”）を取り出させる（ステップＳ２２０２）。そして、その情報を判定して、制御部２１０は、スイッチ２１０２の切り替えを行う（ステップＳ２２０３）。取り出した情報が“０”である場合には、後続符号化データは、画像符号化装置が有するブロック符号化部１０４により生成されたデータであることになる。従って、スイッチ２１０２は端子ｂへ接続し、処理はステップＳ２２０４に進む。また、取り出した情報が“１”である場合には、後続符号化データは、画像符号化装置が有するブロック予測符号化部１８０３により生成されたデータであることになる。従って、スイッチ２１０２は端子ａへ接続し、処理はステップＳ２２０６に進む。
【０１６２】
ステップＳ２２０４に処理が進むと、ブロック情報管理メモリ２０５の内部に格納されているブロック管理テーブル２０５を初期化する。初期状態でブロック管理テーブル２０５は空の状態である。続いて、ステップＳ２２０５にて、ブロック復号部２０４は、スイッチ２１０２を介して入力した符号化データを、ブロック情報管理メモリ２０５に格納されているブロック管理テーブルを更新しながら３２×３２画素の画像データを復元する。ブロック復号部２０４は、このようにして復元した画像データを、ブロック書き出し部２０６の内部メモリに書き込む。ブロック復号部２０４の動作については第１の実施形態と同様である。
【０１６３】
一方、ステップＳ２２０６に処理が進んだ場合には、ブロック予測復号部２１０３が、スイッチ２１０２を介して入力した符号化データを復号し、３２×３２画素の画像データを生成し、それをブロック書き出し部２０６の内部メモリに書き込む。
【０１６４】
ブロック復号部２０６、またはブロック予測復号部２１０３によるブロックデータの復号が終了し、ブロック書き出し部２０６の内部メモリに１ブロック分の画像データが格納されると、処理はステップＳ２２０７に進む。このステップＳ２２０７に処理が進むと、ブロック書き出し部２０６はこれをストライプバッファ２０７へと転送する（ステップＳ２２０７）。ブロックデータは、ストライプバッファの左から右へ順に並べて書き込まれる。
【０１６５】
復号したブロックデータがストライプの最後のブロックであるか否かを判断し（ステップＳ２２０８）、ストライプの最後のブロックでない場合（ＮＯ）は、処理をステップＳ２２０２へと移して次のブロックの復号を行う。
【０１６６】
また、ストライプの最後のブロックであった場合（ＹＥＳ）にはストライプバッファ２０７に格納されたストライプデータをラスタースキャン順に読み出して、画像出力部２０８から装置外部へと出力する（ステップＳ２２０９）。
【０１６７】
ステップＳ２２１０では、出力したストライプデータが画像の最後のストライプデータであるか否かを判断し、最終ストライプでない場合（ＮＯ）はステップＳ２２０２へと処理を移し、次のストライプの復号処理を継続して行う。このとき、ストライプバッファ２０７はクリアされており、また再び、左端から次のブロックデータを格納していく。最終ストライプであった場合（ＹＥＳ）には復号処理を終了する。
【０１６８】
以上の説明した本第２の実施形態の処理により、符号化データから完全に元の画像データを復元することができる。また、本第２の実施形態によれば、自然画の場合、ブロック分割を行なわないで予測符号化を行なうから、ブロック分割した各サブブロックの先頭に同一色判定情報、同一パターンの有無を示す情報が不要となり、高い符号化効率が期待できる。
【０１６９】
＜第１、第２の実施形態の変形例＞
上記第１の実施形態（その変形例も含む）及び第２の実施形態では、着目ブロックと同一ブロックを探し出す際、着目サイズのブロックリストに登録されたブロックを検索対象とした。例えば着目ブロックのサイズが４であり、図２５（ａ）のｂ（ｎ）のブロックを着目ブロックとする場合、符号化済みのｂ（ｎ−１）、ｂ（ｎ−２）、ｂ（ｎ−３）…との比較を行った。しかしながら、これに限らず、例えば、符号化済みの領域から自由にブロックを取り出して一致判定に用いることができる。例えば、図２５（ｂ）のようにブロックｂｘとも比較するようにすれば、符号化済みの領域の中に同一のブロックを検出できる確率が高くなる。
【０１７０】
第１の実施形態では同一のブロックをブロック番号で特定したが、上記のようにする場合には、初期サイズである３２×３２画素の領域全域を検索対象とする（ブロックリストは参照しない）。そして、着目ブロックとその同一ブロック（図２５（ｂ）の場合にはｂｘ）が見つかった場合には、その同一ブロックと判定したブロックの左上隅の画素の相対座標を符号化するすれば良い。
【０１７１】
また、第２の実施形態では初期ブロックの色数Ｎｃに応じて、ブロックの各画素の負符号化と、ブロック単位の分割符号化を選択的に実施する構成を示した。また、第２の実施形態では、同一画素値、または同一パターンの連続する領域に対してはブロック単位の分割符号化を適用し、それ以外では画素単位の符号化を適用することで符号化の効率改善を図るものであり、色数を２つの符号化方式選択の指標として用いた。この変形例として、色数以外の指標を用いて方式選択しても良いし、実際に２つの符号化方式を実施してみて発生符号量の少なくなる方を選択するよう構成しても良い。
【０１７２】
また、上記実施形態では、前値を予測値とした単純な予測符号化の例を示したが、これに限らず、自然画向きの符号化方式であれば良い。予測符号化を用いる場合においても、成分値の予測方法、予測誤差のエントロピ符号化方式など、様々な手法を用いることができる。例えば、着目する成分値の予測方法としては、幾つかの予測方法を用意して、適応的に切り換えても構わないし、符号化済みの各成分値に発生した予測誤差の平均値を着目する成分の予測にフィードバックするなど、非線形な予測を用いても構わない。
【０１７３】
また、予測誤差のエントロピ符号化としてハフマン符号化を用いる例について示したが、Ｇｏｌｏｍｂ符号化や算術符号など、これ以外のエントロピ符号化を用いも良い。
【０１７４】
また、上述の実施形態ではＲＧＢ画像の符号化を例に説明したが、モノクロ画像、ＣＭＹＫ画像や、Ｌａｂ画像や、ＹＣｒＣｂ画像など、各種の画像データに適用可能である。
【０１７５】
また、上述の実施形態では、符号化装置と復号装置を別々の装置であるものとして説明したが、符号化、及び復号にかかる構成を一つの機器に収容し、共通部分を統合しても構わない。
【０１７６】
＜第３の実施形態＞
上記第１、第２の実施形態及びその変形例では、処理済のブロック中に着目ブロックと同一のものがあるか否かを判断した。本第３の実施形態では、この同一ブロック判定に、更に、着目ブロックを０度、９０度、１８０度、２７０度の回転を行なう処理を含めた例を説明する。
【０１７７】
本第３の実施形態では、符号化対象画像データから２４×２４画素の画像データを抜き出す。以下、この２４×２４画素の画像データをタイルと表現する。本第３の実施形態では、このタイル毎に符号化し、符号化データを生成する。また、１つのタイルを符号化する際には、そのタイルを垂直方向４画素、水平方向２４画素のサイズの複数のストライプに更に分割する。そして、１つのストライプに含まれる４×４画素のブロックを着目ブロックとし、当該着目ブロックとその近傍のブロックとに基づき、符号化処理を行なう。図２６は、タイルとストライプとの関係を示している。１つのタイルは、図２６に示すように６つのストライプで構成されることになる。なお、本第３の実施形態における表現のタイル、ストライプは、共に垂直、水平方向の画素数で定義されるものであるので、第１、第２の実施形態で用いたブロック、サブブロックと技術的に同義のものである。
【０１７８】
図２７に第３の実施の形態における画像符号化装置のブロック構成図を示す。本装置は、入力部１２０１、ストライプメモリＡ１２０２、ストライプメモリＢ１２０３、符号列メモリ１２０４、２つのブロック符号化部１２０５、１２０６、画素符号化部１２０７、出力部１２０８、及び、装置全体の制御を司る制御部１２０９とを備える。ブロック符号化部１２０５は、４×４画素の画像データを、符号化部１２０６は２×２画素の画像データを符号化するものである。ストライプメモリＡ１２０２は、ストライプ中の４×４画素の着目ブロックを格納するために用いられ、ストライプメモリＢ１２０３は１つ前のストライプを格納するために用いられる。
【０１７９】
図２８は、１つのタイル（２４×２４画素の画像データ）の符号化処理を示すフローチャートである。この処理は、制御部１２０９の処理手順でもある。以下、図２８のフローチャートに従い、本第３の実施形態における画像符号化装置の処理内容を説明する。
【０１８０】
先ず、制御部１２０９は、ストライプカウンタｉを“０”にセットする（ステップＳ１３０１）。このストライプカウンタｉは、１タイル（２４×２４画素）内に含まれるストライプの１つを特定するためのものである。ストライプの番号は、タイル中の最上部のストライプの番号を「０」とし、下方向に向かって“１”、“２”、…、“５”を割り当てる。
【０１８１】
入力部２０１は、符号化対象の画像データから、１タイル分の画像データを入力し、入力部２０１内のメモリに１タイル分のデータを格納する。そして、制御部１２０９からのストライプカウンタｉで示されるストライプのデータを、ストライプメモリＡ１２０２に格納する（ステップＳ１３０２）。なお、ストライプカウンタｉが“０”である場合、制御部１２０９は、ストライプメモリＢ１２０３をゼロクリア（４×２４＝８６画素分のデータをゼロクリア）する。
【０１８２】
次いで、ステップＳ１３０３にて、制御部１２０９は、ストライプカウンタｉが“０”であるか否かを判断する。ストライプカウンタｉが“０”である場合、着目ストライプが先頭のストライプを符号化することを示している。それ故、ストライプカウンタｉが“０”である場合、ステップＳ１３０４に処理を進め、制御部１２０９は画素符号化部１２０７に対し、着目ストライプの先頭の４×４画素のブロックについて符号化するように指示する。この画素符号化部１２０７は、第１の実施形態における前置予測誤差を用いた符号化処理と同じであるとし、その説明については省略する。画素符号化部１２０７は、先頭ストライプの先頭の４×４画素ブロックの符号化データを生成し、その符号化データを符号列メモリ１２０４に一時的に記憶する。この後、処理はステップＳ１３０５に進める。
【０１８３】
ステップＳ１３０５に処理が進むと、制御部１２０９は、ブロック符号化部１２０５に対し、着目ストライプの未処理の４×４画素ブロックについて符号化処理を行なせる。ストライプカウンタｉが“０”の場合、図３０に示すように未処理の４×４画素ブロックの数が５つ、ストライプカウンタｉが“０”以外の場合には未処理の４×４画素ブロックの数が６つである。
【０１８４】
このブロック符号化部１２０５の符号化処理の詳細は後述するが、概要を説明すれば次の通りである。
１．着目ストライプ中の未処理の４×４画素ブロックのうち、最も左に位置するブロックから右方向に向かう順番に、各ブロックの符号化データを生成する。
２．符号化対象の１つの４×４画素ブロックを着目ブロックとしたとき、相対的に左、上、左上の処理済みブロック（近傍ブロック）の中に、着目ブロックと同一のブロックが存在するかを判定する。そして、存在する場合には、存在することを示すと共に、着目ブロックを何度回転させた場合に一致するかを示す判定情報を符号化データとして、符号列メモリ１２０４に出力する。着目ブロックの上、及び、左上のブロックは、ストライプメモリＢ１２０３に格納されている。
【０１８５】
ステップＳ１３０６では、制御部１２０９は、ブロック符号化部１２０６に対し、符号化処理を行なわせる。但し、ブロック符号化部１２０６の符号化対象は、ステップＳ１３０５にて、着目ブロックと同一のブロックが近傍ブロック内に存在しないと判定された４×４画素ブロックである。つまり、着目ストライプ中の全４×４画素ブロックが、それぞれの近傍ブロックと同一であった場合、このステップＳ１３０６の処理は行なわない。ブロック符号化部１２０６の符号化処理は次の通りである。
１．符号化対象の４×４画素のブロックを４つの２×２画素のブロックに分割する。誤解を招かないようにするため、この２×２画素のブロックを以降、サブブロックと呼ぶ。
２．４つのサブブロックをラスタースキャン順に符号化していく。
３．符号化対象の１つの２×２画素のサブブロックを着目サブブロックとしたとき、相対的に左、上、左上の処理済みサブブロック（近傍サブブロック）の中に、着目サブブロックと同一のブロックが存在するかを判定する。そして、存在する場合には、存在することを示すと共に、着目サブブロックを何度回転させた場合に一致するかを示す判定情報を符号化データとして、符号列メモリ１２０４に出力する。着目ブロックの上、及び、左上のブロックは、ストライプメモリＡ１２０２、Ｂ１２０３に格納されている。
【０１８６】
ステップＳ１３０７では、制御部１２０９は、画素符号化部１２０７に対し、符号化処理を行なわせる。但し、画素符号化部１２０７の符号化対象は、ステップＳ１３０６にて、着目サブブロックと同一のサブブロックが近傍サブブロック内に存在しないと判定された２×２画素のサブブロックである。また、画素符号化部１２０７は生成した符号化データを符号列メモリ１２０４に格納する。なお、画素符号化部１２０７は、既に説明したように予測誤差符号化処理である。
【０１８７】
ステップＳ１３０８では、ストライプカウンタｉが“５”であるか否か、すなわち、着目ストライプが着目タイルの最後のストライプであるか否かを判定する。否の場合には、ステップＳ１３０９にて、制御部１２０９は、ストライプメモリＡ１２０２内のデータを、ストライプメモリＢ１２０３にコピーする。そして、制御部１２０９は、ステップＳ１３１０にて、ストライプカウンタｉを“１”だけ増加させ、ステップＳ１３０２の処理に戻る。
【０１８８】
一方、着目タイルの全ストライプの符号化処理が終了したと判断した場合、処理はステップＳ１３１１に進む。制御部１２０９は、符号列メモリ１２０４に格納された１タイル中の４×４画素のブロック（全部で３６個）の判定情報の符号化データ、２×２画素のサブブロックの判定情報の符号化データ、及び、画素符号化部１２０７で生成された符号化データを連結する。この連結により、符号列を形成する。そして、ステップＳ１３１２にて、生成された符号列を、着目タイルの符号化データとして出力する。
【０１８９】
次に、上記ステップＳ１３０５の処理の詳細を図２９のフローチャートに従って説明する。同図は、制御部１２０９のブロック符号化部１２０５に対する処理手順でもある。
【０１９０】
先ず、ステップＳ１４０１にて、４×４画素のブロックの初期位置を設定する。着目ストライプがタイルの先頭ストライプである場合には、２つ目の画素ブロックが初期位置となる。また、着目ストライプが２番目以降のストライプの場合には、左端を着目ブロックの初期値として設定する。
【０１９１】
次に、ステップＳ１４０２にて、着目ブロックと、その近傍の処理済のブロックとを、着目ブロックを回転させながら順次比較し、着目ブロックと同じブロックが近傍ブロック内にあるか否かをサーチする。図３１の「＊」印が着目ブロックの位置とした場合、近傍のブロックはＢａ（着目ブロックの左側のブロック）、Ｂｂ（着目ブロックの真上のブロック）、Ｂｃ（着目ブロックの左上のブロック）の３つである。
【０１９２】
なお、着目ブロックが、タイルの先頭ストライプ内にあるとき、近傍ブロックＢｂ，Ｂｃはタイル外となる。この場合、着目ブロックと比較する対象はブロックＢａのみとする。また、着目ブロックがストライプの左端にある場合、ブロックＢａはタイル外となる。この場合、着目ブロックと比較する対象はブロックＢｂのみとする。
【０１９３】
また、着目ブロックを回転する際の回転角は０度（回転無し）、９０度、１８０度、２７０の４通りである。
【０１９４】
さて、ステップＳ１４０３では、ステップＳ１４０２のサーチ処理の結果、着目ブロックと同一ブロックが近傍ブロック内に存在したか否かを判定する。存在しなかった場合には、ステップＳ１４０４にて、着目ブロックのブロック符号化情報（判定情報）として１ビットの“０”を出力する。
【０１９５】
また、ステップＳ１４０３にて、着目ブロックと同一のブロックが近傍ブロック内に存在すると判定した場合には、処理はステップＳ１４０６、Ｓ１４０７の処理を行なう。すなわち、着目ブロックと一致すると判定した近傍ブロックの位置（方向）を示す情報を生成するとともに、着目ブロックを何度回転させた場合に一致するのかを示す情報を生成し、これらの情報を着目ブロックのブロック符号化情報（判定情報）としてを出力する。
【０１９６】
ここで、ステップＳ１４０３、Ｓ１４０６，Ｓ１４０７において生成される符号化データは、図３２（ａ），（ｂ）に示すテーブルに従って決定される。
【０１９７】
図３２（ａ）は、着目ブロックと同一のブロックが近傍ブロックＢａ，Ｂｂ，Ｂｃ内に存在するか否か、存在する場合にはどの近傍ブロックであるかを示す符号語テーブルである。
【０１９８】
着目ブロックと同一のブロックが存在しない場合には、図３２（ａ）に従い“０”を出力し、着目ブロックの処理を終える。
【０１９９】
一方、着目ブロックと同一のブロックが近傍ブロックＢａ，Ｂｂ，Ｂｃ内に存在する場合、その近傍ブロックを特定する図３２（ａ）の符号語を出力する。次いで、その一致すると判定した近傍ブロックに対し、回転後の着目ブロックの回転角を示す符号語を図３２（ｂ）の符号語テーブルを参照して出力する。例えば、着目ブロックを如何なる回転角で回転させても近傍ブロックＢａと等しくはならず、着目ブロックを９０度回転させた場合に近傍ブロックＢｂと等しくなったとする。この場合、ステップＳ１４０６、Ｓ１４０７で生成される着目ブロックの符号化データは、二進で“１０１０１”となる。
【０２００】
さて、上記のようにして着目ブロックについてのブロック判定処理に基づく符号化データの出力を終えると、ステップＳ１４０８にて、着目ブロックがストライプの右端にあるか否かを判断する。否の場合にはステップＳ１４０９にて、着目ブロックの位置を４画素分だけ右方向に移動し、ステップＳ１４０２の処理を行なう。
【０２０１】
一方、着目ブロックがストライプの右端位置あると判断した場合には、１ストライプ分の処理が終了したことになるので、本処理を終える。
【０２０２】
以上のようにして画像データの符号化処理が行われる。ここで、１つのタイルの符号化データのデータ構造の一例を図３３に示す。同図は、先に示した図１１における１ブロック分の符号化データの内容に相当するものでもある。
【０２０３】
実施形態では、１タイルのサイズを２４×２４画素としているので、その中には４×４画素のブロックが３６個存在する。従って、先ず、３６個の４×４画素のブロックの符号化データが配置される。図３０に示した様に、１タイルの最初（左上隅）の４×４画素のブロックについては、予測誤差符号化処理が行われる。従って、図３３に示すように、最初の４×４画素の符号化データは、予測誤差符号化データとなる。２番目以降の４×４画素のブロックの符号化データは、近傍ブロックに一致するか否か、一致する場合にはどの近傍ブロックであり、回転角は何度であるかを示す判定情報が格納される。この４×４画素の符号化データに後続して、２×２画素のサブブロックの符号化データが配置される。２×２画素のサブブロックの数は、４×４画素ブロックについて近傍ブロック内に一致すブロックが発見できなかった数×４である。そして、最後に、２×２画素のサブブロック内の予測誤差符号化データが配置される。
【０２０４】
以上説明したように本第３の実施形態によれば、ブロック単位に符号化する際に、着目ブロックを回転させた上で、符号化済みの画像データ領域内に同一の画像が存在するか否かを判定する。この結果、着目ブロックと一致するブロックが発見できる可能性がくなり、圧縮率を向上させることが可能になる。
【０２０５】
なお、第３の実施形態では、ブロックのサイズを４×４画素、２×２画素の２種類の例を示したが、この数に限定されるものではない。例えば、８×８画素、４×４画素、２×２画素としても構わない。要するに、下限サイズにまで分割され、且つ、その下限サイズの着目ブロックと同じ画像が、符号化済みの画像データ領域内に存在しない場合に、着目ブロックを画素単位の符号化を行なうようにすればよい。
【０２０６】
また、本第３の実施形態における着目ブロックと同一の画像が、符号化済みの画像データ領域に内に存在するか否かを示す符号語の生成を、第１、第２の実施形態に適用しても構わないのは、明らかである。
【０２０７】
さらにまた、本第３の実施形態における復号装置は、第１の実施形態における復号装置とほぼ同じである。異なる点は、着目ブロックと着目ブロックと一致するブロックが存在する場合、符号化データにはその一致するブロックを特定する情報と回転角が含まれる。従って、符号化済みの画像データから該当サイズと位置の画像データを読出し、回転角だけ逆に回転した結果を、復号結果として出力すればよい。
【０２０８】
また、本第３の実施形態は、先の第１の実施形態の変形例と同様、コンピュータプログラムでもって実現することができることも明らかである。
【０２０９】
以上本発明に係る実施形態を説明した。
【０２１０】
上記実施形態によれば、例えば、画像データを符号化する画像符号化装置は、以下の構成を備える。即ち、ブロック単位に画像データを入力する入力手段を備える。また、着目ブロックの全画素が同一色かを判定し、同一色の場合にはそれを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックが非同一色の画素を含む場合には非同一色を示す符号化データを出力する第１の符号化手段を備える。また、上記非同一色を示す場合、着目ブロックと同じ画像が、既に符号化処理された画像領域内に存在するか判定し、非存在を示す情報か、存在を示すと共に存在位置の情報を符号化データとして出力する第２の符号化手段を備える。また、該第２の符号化手段で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段を備える。また、着目ブロックのサイズが、下限サイズであると判定した場合、着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化手段を備える。また、着目ブロックが下限サイズよりも大きいと判定した場合、着目ブロックが複数のサブブロックで構成されるものとし、サブブロックのサイズを新たなブロックのサイズとして設定し、第１、第２の符号化手段による符号化を再帰的に実行する制御手段を備える。
【０２１１】
また、例えば、上記入力手段で入力するブロックのサイズが初期の最大サイズである場合、入力したブロック内に含まれる色数を判定する色数判定手段を備える。また、初期サイズのブロック内の画像データをラスタースキャンし、予測誤差符号化を行い、符号化データの生成及び出力を行なう第４の符号化手段を備える。また、判定した色数が予め設定された閾値よりも大きい場合には、入力したブロックを第４の符号化手段に供給し、色数が予め設定された閾値である場合、判定手段、第１、第２の符号化手段による符号化データの生成と出力を行なわせるスイッチ手段を備える。
【０２１２】
また、例えば、画像符号化装置で生成された符号化データを復号する画像復号装置は、以下の構成を備える。即ち、符号化データを入力する第２の入力手段を備える。また、入力した符号化データが着目ブロック内の全画素が同一色を示している場合、後続する符号化データは前記着目ブロック内の色を示す情報とし、着目ブロックを構成する全画素データが前記色を持つものとして出力する第１の復号手段を備える。また、符号化データが着目ブロック内の全画素が非同一色を示し、後続符号化データが、復号済み画像データの領域内に着目ブロックと同一のブロックが存在することを示す場合、前記同一のブロックの画像データを出力する第２の復号手段を備える。また、前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しない示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定手段を備える。また、第２の判定手段が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第３の復号手段を備える。また、着目ブロックが下限サイズより大きいと判定した場合、着目ブロックが複数のサブブロックで構成されるものとし、サブブロックのサイズを新たなブロックのサイズとし、第１、第２の符号化手段による符号化を再帰的に実行する第２の制御手段を備える。
【０２１３】
また、これらの中には、コンピュータに、コンピュータプログラムを実行させる例も説明した。通常、コンピュータプログラム等のソフトウェアは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されている。そして、そのコンピュータ可読記憶媒体を、コンピュータが読取り可能なデバイスにセットし、その上で、システムにコピーもしくはインストールという手順を踏む。従って、このようなコンピュータ可読記憶媒体も本発明の範疇にあることは明らかである。
【図面の簡単な説明】
【０２１４】
【図１】第１の実施形態に係る画像符号化装置のブロック構成図である。
【図２】ブロック情報管理メモリ１０７に格納されるブロック管理テーブルのデータ構造を示す図である。
【図３】図１におけるブロック符号化部１０４でのブロック符号化の処理手順を示すフローチャートである。
【図４】第１の実施形態における初期ブロックと、分割されたブロックとの関係を示す図である。
【図５】着目ブロックリストの一例を示す図である。
【図６】同一色判定と、同一ブロックの判定に用いる符号木を示す図である。
【図７】同一ブロックの位置を符号化する際に用いる符号木を示す図である。
【図８】着目ブロックを４つのサブブロックに分割した際の、着目ブロックと各サブブロックの座標との関係を示す図である。
【図９】予測誤差ｅとグループ番号ＳＳＳＳとの対応テーブルを示す図である。
【図１０】グループ番号ＳＳＳＳと符号語との対応テーブルを示す図である。
【図１１】符号列形成部１０５から出力される符号化画像データのデータ構造を示す図である。
【図１２】第１の実施形態における符号化対象の画像ブロックの一例を示す図である。
【図１３】図１２の画像ブロックの符号化データの例を示す図である。
【図１４】図１２の画像ブロックを符号化する際に、ブロック情報管理メモリ１０７に構築されたブロック管理テーブルの例を示す図である。
【図１５】第１の実施形態における画像符号化処理のメイン処理を示すフローチャートである。
【図１６】第１の実施形態における画像復号装置のブロック構成図である。
【図１７】図１６におけるブロック復号部２０４でのブロック復号の処理手順を示すフローチャートである。
【図１８】第１の実施形態における画像復号装置のメイン処理を示すフローチャートである。
【図１９】第１の実施形態の変形例におけるコンピュータのブロック構成図である。
【図２０】第２の実施形態における画像符号化装置のブロック構成図である。
【図２１】第２の実施形態の画像符号化装置が生成する符号化データのデータ構造を示す図である。
【図２２】第２の実施形態における画像符号化処理のメイン処理を示すフローチャートである。
【図２３】第２の実施形態における画像復号装置のブロック構成図である。
【図２４】第２の実施形態における画像復号装置のメイン処理を示すフローチャートである。
【図２５】第１、第２の実施形態におけるブロック比較の変形例を示す図である。
【図２６】第３の実施形態における画像データの符号化対象のタイルとストライプとの関係を示す図である。
【図２７】第３の実施形態における画像符号化装置のブロック構成図である。
【図２８】第３の実施形態における画像符号化処理のメイン処理を示すフローチャートである。
【図２９】図２８のステップＳ１３０５の詳細を示すフローチャートである。
【図３０】第３の実施形態における１つのタイルに含まれる４×４画素のブロックの配列とストライプ番号との関係を示す図である。
【図３１】第３の実施形態におけるブロック符号化を行なう際の着目ブロックと参照する近傍ブロックの相対位置関係を示す図である。
【図３２】第３の実施形態のブロック符号化の際に参照する符号化テーブルを示す図である。
【図３３】第３の実施形態における１タイルの符号化データのデータ構造を示す図である。
【特許請求の範囲】
【請求項１】
画像データを符号化する画像符号化装置であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力手段と、
着目ブロックの画像データの全画素が同一色である否かを判定し、同一色である場合には同一色であることを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックの画像データが非同一色の画素を含んでいると判定した場合には非同一色を示す符号化データを出力する第１の符号化手段と、
該第１の符号化手段で出力される符号化データが、前記非同一色を示している場合、前記着目ブロックの画像データと同じ画像データが、既に符号化処理された画像データ領域内に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す情報を符号化データとして出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第２の符号化手段と、
該第２の符号化手段で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段と、
該判定手段で前記着目ブロックのサイズが、前記下限サイズであると判定した場合、当該着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化手段と、
前記判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記入力手段に設定し、前記第１、第２の符号化手段による符号化を再帰的に実行する制御手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記第２の符号化手段は、
前記入力手段で入力した着目ブロックを回転させる回転手段を含み、
符号化処理済みの画像データの領域内に、前記回転後の着目ブロックと一致するブロックが存在するか否かを判定し、前記着目ブロックと一致するブロックが存在する場合には、回転角を特定する情報を含む符号化データを生成し、出力する
ことを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記第３の符号化手段は、着目ブロック内をラスタースキャンし、着目画素の値と予測値との差分値を求め、当該差分値を符号化する可逆符号化手段であることを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
前記第２の符号化手段による符号化処理は、前記入力手段で入力するブロックのサイズが初期の最大サイズよりも小さい場合に実行されることを特徴とする請求項１乃至３のいずれか１項に記載の画像符号化装置。
【請求項５】
更に、前記入力手段で入力するブロックのサイズが初期の最大サイズである場合、入力したブロック内に含まれる色数を判定する色数判定手段と、
前記初期サイズのブロック内の画像データをラスタースキャンし、予測誤差符号化を行い、符号化データの生成及び出力を行なう第４の符号化手段と、
前記色数判定手段で判定した色数が予め設定された閾値よりも大きい場合には、前記入力手段で入力したブロックの画像データを前記第４の符号化手段に供給し、
前記色数判定手段で判定した色数が予め設定された閾値以下である場合、前記第１、第２、第３の符号化手段のいずれかによって符号化データの生成と出力を行なわせるスイッチ手段と
を備えることを特徴とする請求項１乃至４のいずれか１項に記載の画像符号化装置。
【請求項６】
画像データを符号化する画像符号化装置であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力手段と、
入力したブロックを複数のサブブロックに分割する分割手段と、
着目サブブロックの画像データと同じ画像データが既に符号化処理された画像領域に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す符号化データを出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第１の符号化手段と、
該第１の符号化手段で出力される符号化データが非存在を示す場合、前記着目サブブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段と、
該判定手段で前記着目サブブロックのサイズが、前記下限サイズであると判定した場合、当該着目サブブロック内の各画素データを符号化し、符号化データを出力する第２の符号化手段と、
前記判定手段で前記着目サブブロックのサイズが、前記下限サイズよりも大きいと判定した場合、前記着目サブブロックを、当該着目サブブロックのサイズよりも更に小さい複数のサブブロックに分割し、当該分割したサブブロックのサイズを前記入力手段が入力するブロックのサイズとして設定して、前記第１の符号化手段による符号化処理を再び実行させる制御手段と
を備えることを特徴とする画像符号化装置。
【請求項７】
更に、前記入力手段で入力したブロック内の画像データの全画素が同一色を示すか否かを判定する色判定手段と、
該色判定手段が、前記同一色と判定した場合、着目ブロックが同一色であることを示すと共に、前記色を示す情報を符号化データとして出力する第３の符号化手段とを備え、
前記分割手段は、前記色判定手段が、非同一色と判定した場合、着目ブロックを分割対象とすることを特徴とする請求項６に記載の画像符号化装置。
【請求項８】
前記第１の符号化手段は、
前記着目サブブロックを回転させる回転手段を含み、
符号化処理済みの画像データの領域内に、前記回転後の着目サブブロックと一致するブロックが存在するか否かを判定し、前記着目サブブロックと一致するブロックが存在する場合には、回転角を特定する情報を含む符号化データを生成し、出力する
ことを特徴とする請求項６又は７に記載の画像符号化装置。
【請求項９】
前記第２の符号化手段は、着目サブブロック内をラスタースキャンし、着目画素の値と、当該着目画素の近傍の１又は複数の画素から求めた予測値との差分値を求め、当該差分値を符号化する可逆符号化手段であることを特徴とする請求項６至８のいずれか１項に記載の画像符号化装置。
【請求項１０】
更に、
前記入力手段で入力するブロックのサイズが初期の最大サイズである場合、入力したブロック内に含まれる色数を判定する色数判定手段と、
前記初期サイズのブロック内の画像データをラスタースキャンし、予測誤差符号化を行い、符号化データの生成及び出力を行なう第４の符号化手段と、
前記色数判定手段で判定した色数が予め設定された閾値よりも大きい場合には、前記入力手段で入力したブロックの画像データを前記第４の符号化手段に供給し、
前記色数判定手段で判定した色数が予め設定された閾値である場合、前記判定手段、前記第１、第２の符号化手段による符号化データの生成と出力を行なわせるスイッチ手段と
を備えることを特徴とする請求項６乃至９のいずれか１項に記載の画像符号化装置。
【請求項１１】
画像データを符号化する画像符号化装置の制御方法であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力工程と、
着目ブロックの画像データの全画素が同一色である否かを判定し、同一色である場合には同一色であることを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックの画像データが非同一色の画素を含んでいると判定した場合には非同一色を示す符号化データを出力する第１の符号化工程と、
該第１の符号化工程で出力される符号化データが、前記非同一色を示している場合、前記着目ブロックの画像データと同じ画像データが、既に符号化処理された画像データ領域内に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す情報を符号化データとして出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第２の符号化工程と、
該第２の符号化工程で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定工程と、
該判定工程で前記着目ブロックのサイズが、前記下限サイズであると判定した場合、当該着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化工程と、
前記判定工程で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記入力工程に設定し、前記第１、第２の符号化工程による符号化を再帰的に実行する制御工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１２】
画像データを符号化する画像符号化装置の制御方法であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力工程と、
入力したブロックを複数のサブブロックに分割する分割工程と、
着目サブブロックの画像データと同じ画像データが既に符号化処理された画像領域に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す符号化データを出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第１の符号化工程と、
該第１の符号化工程で出力される符号化データが非存在を示す場合、前記着目サブブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定工程と、
該判定工程で前記着目サブブロックのサイズが、前記下限サイズであると判定した場合、当該着目サブブロック内の各画素データを符号化し、符号化データを出力する第２の符号化工程と、
前記判定工程で前記着目サブブロックのサイズが、前記下限サイズよりも大きいと判定した場合、前記着目サブブロックを、当該着目サブブロックのサイズよりも更に小さい複数のサブブロックに分割し、当該分割したサブブロックのサイズを前記入力工程が入力するブロックのサイズとして設定して、前記第１の符号化工程による符号化処理を再び実行させる制御工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１３】
コンピュータが読込み実行することで、前記コンピュータを請求項１乃至１０のいずれか１項に記載の画像符号化装置として機能させるコンピュータプログラム。
【請求項１４】
請求項１に記載の画像符号化装置で生成された符号化データを復号する画像復号装置であって、
符号化データを入力する第２の入力手段と、
入力した符号化データが着目ブロック内の全画素が同一色を示している場合、後続する符号化データは前記着目ブロック内の色を示す情報とし、着目ブロックを構成する全画素データが前記色を持つものとして出力する第１の復号手段と、
前記入力した符号化データが着目ブロック内の全画素が非同一色を示している場合であって、後続する符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第２の復号手段と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定手段と、
該第２の判定手段が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第３の復号手段と、
前記第２の判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力手段に設定し、前記第１、第２の符号化手段による符号化を再帰的に実行する第２の制御手段と
を備えることを特徴とする画像復号装置。
【請求項１５】
請求項６に記載の画像符号化装置で生成された符号化データを復号する画像復号装置であって、
符号化データを入力する第２の入力手段と、
入力した符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第１の復号手段と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定手段と、
該第２の判定手段が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第２の復号手段と、
前記第２の判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力手段に設定し、前記第１の符号化手段による符号化を再帰的に実行する第２の制御手段と
を備えることを特徴とする画像復号装置。
【請求項１６】
請求項１に記載の画像符号化装置で生成された符号化データを復号する画像復号装置の制御方法であって、
符号化データを入力する第２の入力工程と、
入力した符号化データが着目ブロック内の全画素が同一色を示している場合、後続する符号化データは前記着目ブロック内の色を示す情報とし、着目ブロックを構成する全画素データが前記色を持つものとして出力する第１の復号工程と、
前記入力した符号化データが着目ブロック内の全画素が非同一色を示している場合であって、後続する符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第２の復号工程と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定工程と、
該第２の判定工程が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第３の復号工程と、
前記第２の判定工程で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力工程に設定し、前記第１、第２の符号化工程による符号化を再帰的に実行する第２の制御工程と
を備えることを特徴とする画像復号装置の制御方法。
【請求項１７】
請求項６に記載の画像符号化装置で生成された符号化データを復号する画像復号装置の制御方法であって、
符号化データを入力する第２の入力工程と、
入力した符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第１の復号工程と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定工程と、
該第２の判定工程が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第２の復号工程と、
前記第２の判定工程で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力工程に設定し、前記第１の符号化工程による符号化を再帰的に実行する第２の制御工程と
を備えることを特徴とする画像復号装置の制御方法。
【請求項１８】
コンピュータが読込み実行することで、前記コンピュータを請求項１４又は１５に記載の画像復号装置として機能させるコンピュータプログラム。
【請求項１９】
請求項１３又は１８に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項１】
画像データを符号化する画像符号化装置であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力手段と、
着目ブロックの画像データの全画素が同一色である否かを判定し、同一色である場合には同一色であることを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックの画像データが非同一色の画素を含んでいると判定した場合には非同一色を示す符号化データを出力する第１の符号化手段と、
該第１の符号化手段で出力される符号化データが、前記非同一色を示している場合、前記着目ブロックの画像データと同じ画像データが、既に符号化処理された画像データ領域内に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す情報を符号化データとして出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第２の符号化手段と、
該第２の符号化手段で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段と、
該判定手段で前記着目ブロックのサイズが、前記下限サイズであると判定した場合、当該着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化手段と、
前記判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記入力手段に設定し、前記第１、第２の符号化手段による符号化を再帰的に実行する制御手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記第２の符号化手段は、
前記入力手段で入力した着目ブロックを回転させる回転手段を含み、
符号化処理済みの画像データの領域内に、前記回転後の着目ブロックと一致するブロックが存在するか否かを判定し、前記着目ブロックと一致するブロックが存在する場合には、回転角を特定する情報を含む符号化データを生成し、出力する
ことを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記第３の符号化手段は、着目ブロック内をラスタースキャンし、着目画素の値と予測値との差分値を求め、当該差分値を符号化する可逆符号化手段であることを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
前記第２の符号化手段による符号化処理は、前記入力手段で入力するブロックのサイズが初期の最大サイズよりも小さい場合に実行されることを特徴とする請求項１乃至３のいずれか１項に記載の画像符号化装置。
【請求項５】
更に、前記入力手段で入力するブロックのサイズが初期の最大サイズである場合、入力したブロック内に含まれる色数を判定する色数判定手段と、
前記初期サイズのブロック内の画像データをラスタースキャンし、予測誤差符号化を行い、符号化データの生成及び出力を行なう第４の符号化手段と、
前記色数判定手段で判定した色数が予め設定された閾値よりも大きい場合には、前記入力手段で入力したブロックの画像データを前記第４の符号化手段に供給し、
前記色数判定手段で判定した色数が予め設定された閾値以下である場合、前記第１、第２、第３の符号化手段のいずれかによって符号化データの生成と出力を行なわせるスイッチ手段と
を備えることを特徴とする請求項１乃至４のいずれか１項に記載の画像符号化装置。
【請求項６】
画像データを符号化する画像符号化装置であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力手段と、
入力したブロックを複数のサブブロックに分割する分割手段と、
着目サブブロックの画像データと同じ画像データが既に符号化処理された画像領域に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す符号化データを出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第１の符号化手段と、
該第１の符号化手段で出力される符号化データが非存在を示す場合、前記着目サブブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定手段と、
該判定手段で前記着目サブブロックのサイズが、前記下限サイズであると判定した場合、当該着目サブブロック内の各画素データを符号化し、符号化データを出力する第２の符号化手段と、
前記判定手段で前記着目サブブロックのサイズが、前記下限サイズよりも大きいと判定した場合、前記着目サブブロックを、当該着目サブブロックのサイズよりも更に小さい複数のサブブロックに分割し、当該分割したサブブロックのサイズを前記入力手段が入力するブロックのサイズとして設定して、前記第１の符号化手段による符号化処理を再び実行させる制御手段と
を備えることを特徴とする画像符号化装置。
【請求項７】
更に、前記入力手段で入力したブロック内の画像データの全画素が同一色を示すか否かを判定する色判定手段と、
該色判定手段が、前記同一色と判定した場合、着目ブロックが同一色であることを示すと共に、前記色を示す情報を符号化データとして出力する第３の符号化手段とを備え、
前記分割手段は、前記色判定手段が、非同一色と判定した場合、着目ブロックを分割対象とすることを特徴とする請求項６に記載の画像符号化装置。
【請求項８】
前記第１の符号化手段は、
前記着目サブブロックを回転させる回転手段を含み、
符号化処理済みの画像データの領域内に、前記回転後の着目サブブロックと一致するブロックが存在するか否かを判定し、前記着目サブブロックと一致するブロックが存在する場合には、回転角を特定する情報を含む符号化データを生成し、出力する
ことを特徴とする請求項６又は７に記載の画像符号化装置。
【請求項９】
前記第２の符号化手段は、着目サブブロック内をラスタースキャンし、着目画素の値と、当該着目画素の近傍の１又は複数の画素から求めた予測値との差分値を求め、当該差分値を符号化する可逆符号化手段であることを特徴とする請求項６至８のいずれか１項に記載の画像符号化装置。
【請求項１０】
更に、
前記入力手段で入力するブロックのサイズが初期の最大サイズである場合、入力したブロック内に含まれる色数を判定する色数判定手段と、
前記初期サイズのブロック内の画像データをラスタースキャンし、予測誤差符号化を行い、符号化データの生成及び出力を行なう第４の符号化手段と、
前記色数判定手段で判定した色数が予め設定された閾値よりも大きい場合には、前記入力手段で入力したブロックの画像データを前記第４の符号化手段に供給し、
前記色数判定手段で判定した色数が予め設定された閾値である場合、前記判定手段、前記第１、第２の符号化手段による符号化データの生成と出力を行なわせるスイッチ手段と
を備えることを特徴とする請求項６乃至９のいずれか１項に記載の画像符号化装置。
【請求項１１】
画像データを符号化する画像符号化装置の制御方法であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力工程と、
着目ブロックの画像データの全画素が同一色である否かを判定し、同一色である場合には同一色であることを示す情報と前記色を特定する情報を符号化データとして出力し、着目ブロックの画像データが非同一色の画素を含んでいると判定した場合には非同一色を示す符号化データを出力する第１の符号化工程と、
該第１の符号化工程で出力される符号化データが、前記非同一色を示している場合、前記着目ブロックの画像データと同じ画像データが、既に符号化処理された画像データ領域内に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す情報を符号化データとして出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第２の符号化工程と、
該第２の符号化工程で出力される符号化データが、前記着目ブロックの画像データと同じ画像データの非存在を示す場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定工程と、
該判定工程で前記着目ブロックのサイズが、前記下限サイズであると判定した場合、当該着目ブロック内の各画素データを符号化し、符号化データを出力する第３の符号化工程と、
前記判定工程で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記入力工程に設定し、前記第１、第２の符号化工程による符号化を再帰的に実行する制御工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１２】
画像データを符号化する画像符号化装置の制御方法であって、
複数の画素で構成され、設定されたサイズのブロック単位に、画像データを入力する入力工程と、
入力したブロックを複数のサブブロックに分割する分割工程と、
着目サブブロックの画像データと同じ画像データが既に符号化処理された画像領域に存在するか否かを判定し、同じ画像データが存在しない場合には非存在を示す符号化データを出力し、同じ画像データが存在する場合には存在を示すと共に存在する位置を特定する情報を符号化データとして出力する第１の符号化工程と、
該第１の符号化工程で出力される符号化データが非存在を示す場合、前記着目サブブロックのサイズが、予め設定された下限サイズであるか否かを判定する判定工程と、
該判定工程で前記着目サブブロックのサイズが、前記下限サイズであると判定した場合、当該着目サブブロック内の各画素データを符号化し、符号化データを出力する第２の符号化工程と、
前記判定工程で前記着目サブブロックのサイズが、前記下限サイズよりも大きいと判定した場合、前記着目サブブロックを、当該着目サブブロックのサイズよりも更に小さい複数のサブブロックに分割し、当該分割したサブブロックのサイズを前記入力工程が入力するブロックのサイズとして設定して、前記第１の符号化工程による符号化処理を再び実行させる制御工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１３】
コンピュータが読込み実行することで、前記コンピュータを請求項１乃至１０のいずれか１項に記載の画像符号化装置として機能させるコンピュータプログラム。
【請求項１４】
請求項１に記載の画像符号化装置で生成された符号化データを復号する画像復号装置であって、
符号化データを入力する第２の入力手段と、
入力した符号化データが着目ブロック内の全画素が同一色を示している場合、後続する符号化データは前記着目ブロック内の色を示す情報とし、着目ブロックを構成する全画素データが前記色を持つものとして出力する第１の復号手段と、
前記入力した符号化データが着目ブロック内の全画素が非同一色を示している場合であって、後続する符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第２の復号手段と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定手段と、
該第２の判定手段が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第３の復号手段と、
前記第２の判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力手段に設定し、前記第１、第２の符号化手段による符号化を再帰的に実行する第２の制御手段と
を備えることを特徴とする画像復号装置。
【請求項１５】
請求項６に記載の画像符号化装置で生成された符号化データを復号する画像復号装置であって、
符号化データを入力する第２の入力手段と、
入力した符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第１の復号手段と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定手段と、
該第２の判定手段が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第２の復号手段と、
前記第２の判定手段で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力手段に設定し、前記第１の符号化手段による符号化を再帰的に実行する第２の制御手段と
を備えることを特徴とする画像復号装置。
【請求項１６】
請求項１に記載の画像符号化装置で生成された符号化データを復号する画像復号装置の制御方法であって、
符号化データを入力する第２の入力工程と、
入力した符号化データが着目ブロック内の全画素が同一色を示している場合、後続する符号化データは前記着目ブロック内の色を示す情報とし、着目ブロックを構成する全画素データが前記色を持つものとして出力する第１の復号工程と、
前記入力した符号化データが着目ブロック内の全画素が非同一色を示している場合であって、後続する符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第２の復号工程と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定工程と、
該第２の判定工程が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第３の復号工程と、
前記第２の判定工程で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力工程に設定し、前記第１、第２の符号化工程による符号化を再帰的に実行する第２の制御工程と
を備えることを特徴とする画像復号装置の制御方法。
【請求項１７】
請求項６に記載の画像符号化装置で生成された符号化データを復号する画像復号装置の制御方法であって、
符号化データを入力する第２の入力工程と、
入力した符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在することを示す符号化データである場合、前記同一のブロックの画像データを着目ブロックの復号結果として出力する第１の復号工程と、
前記符号化データが、既に復号済みの画像データの領域内に着目ブロックと同一のブロックが存在しないことを示している場合、前記着目ブロックのサイズが、予め設定された下限サイズであるか否かを判定する第２の判定工程と、
該第２の判定工程が、前記着目ブロックのサイズが、予め設定された下限サイズであると判定した場合、後続する符号化データは前記着目ブロック内の各画素の符号化データであるものとし、復号して出力する第２の復号工程と、
前記第２の判定工程で前記着目ブロックのサイズが、前記下限サイズよりも大きいと判定した場合、当該着目ブロックが複数のサブブロックで構成されるものとし、当該サブブロックのサイズを新たなブロックのサイズとして前記第２の入力工程に設定し、前記第１の符号化工程による符号化を再帰的に実行する第２の制御工程と
を備えることを特徴とする画像復号装置の制御方法。
【請求項１８】
コンピュータが読込み実行することで、前記コンピュータを請求項１４又は１５に記載の画像復号装置として機能させるコンピュータプログラム。
【請求項１９】
請求項１３又は１８に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【公開番号】特開２００８−３０１３７３（Ｐ２００８−３０１３７３Ａ）
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願番号】特願２００７−１４７４１９（Ｐ２００７−１４７４１９）
【出願日】平成１９年６月１日（２００７．６．１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願日】平成１９年６月１日（２００７．６．１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]