(57)【特許請求の範囲】
【請求項１】
２値画像データを符号化する画像符号化装置であって、
複数の画素を含む画素ブロックを単位に、２値画像データを入力する入力手段と、
前記入力手段で入力した画素ブロック内の各画素データを、前記画素ブロックに含まれる画素数の１／Ｋ（Ｋは２以上の整数）の画素数で構成されるＫ個のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）のいずれかに分配する分配手段と、
前記分配手段の分配処理で作成されたサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列をそれぞれ同一の符号化方法で符号化し、得られた符号化データを前記画素ブロックの符号化データとして出力する符号化手段と、
前記符号化手段で前記画素ブロックの符号化データとして出力された、複数種類の符号化データのデータ量を比較することにより、最小符号量となる符号化データを特定する比較手段と、
前記最小符号量となる符号化データと前記比較結果を示す識別情報とを出力する出力手段とを備え、
前記分配手段は、着目画素ブロック内の各画素データから、互いに異なるアルゴリズムの分配処理を用いて、複数種類のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列を作成し、
前記符号化手段は、前記複数種類の画像データ列のそれぞれを独立に符号化することにより、複数種類の符号化データを、前記画素ブロックの符号化データとして出力することを特徴とする画像符号化装置。
【請求項２】
前記分配手段は、互いに異なるアルゴリズムの分配処理を行う複数の画素分配手段で構成されることを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記複数の画素分配手段の１つは、
前記Ｋがｐ×ｑ（ｐ、及び、ｑはいずれも１以上の整数であって、いずれか一方は２以上の整数）で表わせ、前記画素ブロックを水平方向にｐ等分、垂直方向にｑ等分した場合の各分割領域を前記サブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）として、前記画素ブロック内の画素データを分配し、
前記複数の画素分配手段のもう１つは、
前記画素ブロック内の座標（ｘ，ｙ）の画素データを、ｘをｐで除算したときの余りと、ｙ座標をｑで除算したときの余りで示されるサブブロックの１つに分配する
ことを特徴とする請求項２に記載の画像符号化装置。
【請求項４】
２値画像データを符号化する画像符号化装置の制御方法であって、
入力手段が、複数の画素を含む画素ブロックを単位に、２値画像データを入力する入力工程と、
分配手段が、前記入力工程で入力した画素ブロック内の各画素データを、前記画素ブロックに含まれる画素数の１／Ｋ（Ｋは２以上の整数）の画素数で構成されるＫ個のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）のいずれかに分配する分配工程であって、互いに異なるアルゴリズムに従って分配を行なう複数の分配工程と、
符号化手段が、前記分配工程の分配処理で生成されたサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列をそれぞれ同一の符号化方法で符号化し、得られた符号化データを前記画素ブロックの符号化データとして出力する、前記複数の分配工程それぞれに対応する複数の符号化工程と、
比較手段が、前記複数の符号化工程で出力された複数種類の符号化データのデータ量を比較することにより、最小符号量となる符号化データを特定する比較工程と、
出力手段が、前記最小符号量となる符号化データと前記比較結果を示す識別情報とを出力する出力工程と
を有することを特徴とする画像符号化装置の制御方法。
【請求項５】
２値画像データを符号化する画像符号化装置であって、
複数の画素を含む画素ブロックを単位に、２値画像データを入力する入力手段と、
前記入力手段で入力した着目画素ブロックの画像データを符号化し、得られた符号化データを前記画素ブロックの符号化データとして出力する第１乃至第４の符号化処理手段と、
前記第１乃至第４の符号化処理手段で得られたそれぞれの符号化データを比較し、最小となった符号化データを前記着目画素ブロックの符号化データとして出力する出力手段とを備え、
前記第１乃至第４の符号化処理手段における第１の符号化処理手段、第２の符号化処理手段、第３の符号化処理手段、並びに、第４の符号化処理手段のそれぞれは、前記着目画素ブロックに含まれる各画素データを、当該着目画素ブロックに含まれる画素数の１／Ｋ（Ｋは２以上の整数）の画素数で構成されるＫ個のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）のいずれかに分配する分配手段を有し、
ここで、前記第１の符号化処理手段及び前記第２の符号化処理手段のそれぞれが有する分配手段は、前記第３の符号化処理手段及び前記第４の符号化処理手段それぞれが有する分配手段とは異なるアルゴリズムを用いて、複数種類のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列を作成し；
前記第２の符号化処理手段及び前記第４の符号化処理手段のそれぞれは、それぞれが有する前記分配手段で得られたＫ個のサブブロックの１つを参照用のサブブロックとして出力し、残るＫ−１個のサブブロックについては前記参照用のサブブロック内の画素値を予測値とする予測差分値で構成されるサブブロックとして出力する差分予測手段を有し、
前記第１の符号化処理手段及び前記第３の符号化処理手段のそれぞれは、それぞれが有する前記分配手段で得られたＫ個のサブブロックを圧縮符号化し、
前記第２の符号化処理手段及び前記第４の符号化処理手段のそれぞれは、それぞれが有する前記差分予測手段で得られたＫ個のサブブロックを同一の符号化方法で圧縮符号化する圧縮手段とを有する
ことを特徴とする画像符号化装置。
【請求項６】
２値画像データを符号化する画像符号化装置の制御方法であって、
入力手段が、複数の画素を含む画素ブロックを単位に、２値画像データを入力する入力工程と、
第１乃至第４の符号化処理手段が、前記入力工程で入力した着目画素ブロックの画像データを符号化し、得られた符号化データを前記画素ブロックの符号化データとして出力する第１乃至第４の符号化処理工程と、
出力手段が、前記第１乃至第４の符号化処理工程で得られたそれぞれの符号化データを比較し、最小となった符号化データを前記着目画素ブロックの符号化データとして出力する出力工程とを備え、
前記第１乃至第４の符号化処理工程における第１の符号化処理工程、第２の符号化処理工程、第３の符号化処理工程、並びに、第４の符号化処理工程のそれぞれは、前記着目画素ブロックに含まれる各画素データを、当該着目画素ブロックに含まれる画素数の１／Ｋ（Ｋは２以上の整数）の画素数で構成されるＫ個のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）のいずれかに分配する分配工程を有し、
ここで、前記第１の符号化処理工程及び前記第２の符号化処理工程のそれぞれが有する分配工程は、前記第３の符号化処理工程及び前記第４の符号化処理工程のそれぞれが有する分配工程とは異なるアルゴリズムを用いて、複数種類のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列を作成し；
前記第２の符号化処理工程及び前記第４の符号化処理工程のそれぞれは、それぞれが有する前記分配工程で得られたＫ個のサブブロックの１つを参照用のサブブロックとして出力し、残るＫ−１個のサブブロックについては前記参照用のサブブロック内の画素値を予測値とする予測差分値で構成されるサブブロックとして出力する差分予測工程を有し、
前記第１の符号化処理工程及び前記第３の符号化処理工程のそれぞれは、それぞれが有する前記分配工程で得られたＫ個のサブブロックを圧縮符号化し、
前記第２の符号化処理工程及び前記第４の符号化処理工程のそれぞれは、それぞれが有する前記差分予測工程で得られたＫ個のサブブロックを同一の符号化方法で圧縮符号化するための圧縮工程とを有する
ことを特徴とする画像符号化装置の制御方法。
【請求項７】
コンピュータが読込み実行することで、前記コンピュータを、請求項１乃至３、５のいずれか１項に記載の画像符号化装置の各手段として機能させるコンピュータプログラム。
【請求項８】
請求項７に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像データの圧縮符号化技術に関するものである。
【背景技術】
【０００２】
従来、文字や線画など高い解像度が要求される画像（以下、文字線画）と、写真画像や背景などの画像（以下、階調画像）とに分離し、それぞれ別の圧縮方式で圧縮し、圧縮後にそれらのデータを結合し、固定長の符号化データを生成する試みが行われていた。文字線画は、各画素が文字線画を構成する画素であるか否かを識別する２値の識別情報と、その画素値を可逆可変長符号化する。一方、階調画像は固定長の残りの符号量に収まるように非可逆圧縮を行う。このような固定長符号化の画像品質を確保するためには、２値の識別情報の可変長符号化をあらゆるパターンに対して効率的に行うこと、即ち、圧縮効率の最悪値を改善することが最も重要な指針とされていた。
【０００３】
従来、２値データに対して圧縮を行うものとしては、ＩＴＵ−ＴＳのＧ３ファクシミリで規格化されているＭＨ（Ｍｏｄｉｆｉｅｄ  Ｈｕｆｆｍａｎ）やＭＲ（Ｍｏｄｉｆｉｅｄ  ＲＥＡＤ）、ＭＭＲ（Ｍｏｄｉｆｉｅｄ  ＭＲ）などが一般的であった。これらの方式はランレングス符号化を基本とした圧縮アルゴリズムであり、例えばＭＨはラスタ方向のランレングスを予め定められた符号語で符号化するという方式である。
【０００４】
また、ブロック化された２値画像を圧縮する技術として特許文献１が提案されている。この文献には、２値画像を４×４から１６×１６画素のブロックに分割し、ブロックのサイズの符号と、４×４のサイズに対しては原画像におけるブロック内の画素パターン情報の符号する点が開示されている。また、その他のサイズに対しては、ブロック内の黒画素数をカウントすることにより求めた、ブロックの階調情報の符号を合成して圧縮を行うことが開示されている。
【特許文献１】特許第２９３６０４２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
これらの圧縮方式は文字や線画など連続性が高く単純な画像に対しては効率的な圧縮が可能であるが、より複雑な画像の圧縮には不向きである。例えば、ＰＣのアプリケーションソフトにおいて中間濃度の画像や半透明の画像を用いて文書を作成した場合に、その文書をＰＣでレンダリングすると図５（ａ），（ｂ）に示すようなパターンが表れることが多くあった。図５（ａ），（ｂ）を見ると、中間濃度や半透明の部分は、必ずしも中間濃度値の画素で表現されるわけではなく高濃度値と低濃度値の画素の発生する割合によって濃度表現される場合があるということが分かる。そして、図５のように濃度の変化点が多い画像は、ランを稼ぐことができず、ＭＨやＭＲなどの圧縮アルゴリズムは不向きである場合が多かった。
【０００６】
また、特許文献１においても４×４以外のサイズに対してはブロックの濃度のみを保証するアルゴリズムであり、その形状までは保証できず、復号化後に形状が変わってしまうという問題があった。
【０００７】
本発明は上記のような複雑な画像に対しても、効率的な圧縮が可能となる技術を提供しようとするものである。
【課題を解決するための手段】
【０００８】
この課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
２値画像データを符号化する画像符号化装置であって、
複数の画素を含む画素ブロックを単位に、２値画像データを入力する入力手段と、
前記入力手段で入力した画素ブロック内の各画素データを、前記画素ブロックに含まれる画素数の１／Ｋ（Ｋは２以上の整数）の画素数で構成されるＫ個のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）のいずれかに分配する分配手段と、
前記分配手段の分配処理で作成されたサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列をそれぞれ同一の符号化方法で符号化し、得られた符号化データを前記画素ブロックの符号化データとして出力する符号化手段と、
前記符号化手段で前記画素ブロックの符号化データとして出力された、複数種類の符号化データのデータ量を比較することにより、最小符号量となる符号化データを特定する比較手段と、
前記最小符号量となる符号化データと前記比較結果を示す識別情報とを出力する出力手段とを備え、
前記分配手段は、着目画素ブロック内の各画素データから、互いに異なるアルゴリズムの分配処理を用いて、複数種類のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）の画像データ列を作成し、
前記符号化手段は、前記複数種類の画像データ列のそれぞれを独立に符号化することにより、複数種類の符号化データを、前記画素ブロックの符号化データとして出力することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、複雑な２値画像を効率的に符号化することが可能となる。
【発明を実施するための最良の形態】
【００１０】
以下、添付図面に従って本発明に係る実施形態を説明する。本実施形態での符号化対象の画像データは２値画像データであるものとする。但し、ここで言う２値画像とは、例えば画素値が０、１のみを言うのでない。すなわち、例えば、８ビットで表わされる画素値のうち、出現する濃度が５０と１５０の２種類である場合にも適用できる。
【００１１】
［第１の実施形態］
図１は第１の実施形態における可逆画像符号化装置のブロック構成図である。
【００１２】
本装置は、符号化処理部１１０、１２０、１３０、１４０と、それぞれの符号量を検出する符号量検出部１５１乃至１５４、比較部１６０、及び、選択部１７０を有する。
【００１３】
符号化処理部１１０、１２０、１３０、１４０は、入力した１６×１６画素ブロックを符号化し、生成した符号化データを選択部１７０に出力する（詳細後述）。符号量検知部１５１乃至１５４は、それぞれの符号化データのデータ量を検出し、その検出した結果を比較部１６０に出力する。比較部１６０は、符号量検知部１５１乃至１５４からの符号量を比較し、最も小さい符号量がいずれであるのかを判定し、その判定結果を制御信号として選択部１７０に出力する。選択部１７０は、比較部１６０から制御信号に従い、符号化処理部１１０、１２０、１３０、１４０のいずれか１つからの符号化データを選択し、出力する。このとき、選択部１７０は、どの符号化処理部の符号化データであるかを示す識別情報を、選択した符号化データのヘッダに付加して出力する。実施形態の場合、符号化処理部は４つであるので、この識別情報は２ビットで良い。なお、符号化処理部１１０、１２０、１３０、１４０で生成された符号化データのデータ量が最小となるものが２つ存在することも起こり得る。この場合、符号化処理部１１０、１２０、１３０、１４０の優先順位に１つの符号化データを選択対象として決定する。
【００１４】
次に、各符号化処理部１１０、１２０、１３０、１４０について説明する。
【００１５】
符号化処理部１１０は、分配部１１１、圧縮部１１２乃至１１５、連結部１１６を有する。
【００１６】
分配部１１１は、入力した１６×１６画素ブロック内の各画素データを、図３（ａ）のテーブルを参照し、４つの８×８画素のサブブロックのいずれかに分配する。具体的には、次の通りである。
【００１７】
分配部１１１は、図３（ａ）の“０”で示される位置の画素データを、８×８画素のサブブロック（以下、サブブロックＳＢ０という）に分配し、そのサブブロックＳＢ０を圧縮部１１２に出力する。
【００１８】
同様に、分配部１１１は、同様に、図３（ａ）の“１”で示される位置の画素データをサブブロックＳＢ１に分配し、圧縮部１１３に出力する。また、分配部１１１は、図３（ａ）の“２”で示される位置の画素データをサブブロックＳＢ２に分配し、圧縮部１１４に出力する。そして、分配部１１１は図３（ａ）の“３”で示される位置の画素データをサブブロックＳＢ３に分配し、圧縮部１１５に出力する。
【００１９】
より分かりやすく説明するのであれば、次の通りである。今、入力した１６×１６画素ブロック内の座標（ｘ，ｙ）の画素値をＢ（ｘ，ｙ）と定義する。そして、サブブロックＳＢ０、ＳＢ１、ＳＢ２，ＳＢ３の座標（ｘ，ｙ）の画素値をＳＢ０（ｘ，ｙ）、ＳＢ１（ｘ，ｙ）、ＳＢ２（ｘ，ｙ）、ＳＢ３（ｘ，ｙ）と定義する。この場合、分配部１１１は、入力したブロック画像Ｂ内の各画素データを以下のようにして、４つのサブブロックＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３に分配する。
ＳＢ０（ｘ，ｙ）←Ｂ（２ｘ，２ｙ）
ＳＢ１（ｘ，ｙ）←Ｂ（２ｘ＋１，２ｙ）
ＳＢ２（ｘ，ｙ）←Ｂ（２ｘ，２ｙ＋１）
ＳＢ３（ｘ，ｙ）←Ｂ（２ｘ＋１，２ｙ＋１）        …（１）
ここでｘ、ｙは０乃至７の整数である。
【００２０】
要するに、画素ブロックのサイズをＭ×Ｎ画素とし、それをＫ（＝ｐ×ｑ）個のサブブロックに分配するとする。この場合、分配部１１１は、画素ブロック内の座標（ｘ，ｙ）の画素データを、ｘをｐで除算したときの余りと、ｙ座標をｑで除算したときの余りで示されるサブブロックの１つに分配する。
【００２１】
圧縮部１１２乃至１１５は、それぞれに供給されたサブブロックＳＢ０乃至ＳＢ３を圧縮符号化し、連結部１１６に出力する。圧縮部の圧縮符号化アルゴリズムは如何なるものでも構わないが、実施形態ではサブブロック内をスキャンし、ランを求め、ハフマン符号表に従ってランの符号語を生成するものとする（可変長可逆符号化）。連結部１１６は、各サブブロックの符号化データを予め設定された順番、例えば、サブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３の順番に符号化データを連結し、選択部１７０及び符号量検知部１５１に出力する。
【００２２】
次に、符号化処理部１２０について説明する。符号化処理部１２０内における分配部１２１、圧縮部１２２乃至１２５、及び、連結部１２６は、符号化処理部１１０における分配部１１１、圧縮部１１２乃至１１５、連結部１１６と同じである。異なる点は、差分予測部１２７を設けた点にある。それ故、以下では、差分予測部１２７について説明する。
【００２３】
差分予測部１２７は、分配部１２１から入力したＫ個のサブブロック中の１つのサブブロックについては加工せずそのまま出力する。そして、その１つのサブブロックをリファレンスとし、そのリファレンス以外の、Ｋ−１個のサブブロックについては、リファレンスに対する差分予測値を演算し、その演算結果を出力する。
【００２４】
実施形態における差分予測部１２７は、具体的には、分配部１２１から入力したサブブロックＳＢ０はそのまま圧縮部１２２に出力する。そして、そのサブブロックＳＢ０をリファレンスとする。差分予測部１２７は、リファレンスであるサブブロックＳＢ０と残りの３つのサブブロックＳＢ１、ＳＢ２、ＳＢ３との排他的論理和演算を、同位相位置の画素単位に行なう。そして、その論理演算結果をＳＢ１’、ＳＢ２’、ＳＢ３’として圧縮部１２３乃至１２５に出力する。
ＳＢ１’←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ１（ｘ，ｙ）｝
ＳＢ２’←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ２（ｘ，ｙ）｝
ＳＢ３’←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ３（ｘ，ｙ）｝      …（２）
ここでＸＯＲ｛ａ，ｂ｝は、値ａ，ｂのビット同士の排他的論理和演算を表わす。
【００２５】
従って、符号化処理部１２０は、サブブロックＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’それぞれの符号化データを結合して出力することになる。
【００２６】
要するに、符号化処理部１１０と１２０との違いは、符号化処理部１１０は上記論理演算前のサブブロックを符号化し、符号化処理部１２０は上記論理演算後のサブブロックを符号化するものである。
【００２７】
次に、符号化処理部１３０について説明する。符号化処理部１３０内における圧縮部１３２乃至１３５、及び、連結部１３６は、符号化処理部１１０内の圧縮部１１２乃至１１５、連結部１１６と同じである。異なる点は、分配部１３１による分配の仕方である。それ故、以下では、分配部１３１について説明する。
【００２８】
分配部１３１は、図３（ｂ）の“０”で示される位置の画素データをサブブロックＳＢ０に分配し、圧縮部１３２に出力する。
【００２９】
同様に、分配部１３１は、同様に、図３（ｂ）の“１”で示される位置の画素データをサブブロックＳＢ１に分配し、圧縮部１３３に出力する。また、分配部１３１は、図３（ｂ）の“２”で示される位置の画素データをサブブロックＳＢ２に分配し、圧縮部１３４に出力する。そして、分配部１３１は、図３（ａ）の“３”で示される位置の画素データをサブブロックＳＢ３に分配し、圧縮部１３５に出力する。
【００３０】
要するに、分配部１３１は、入力した画素ブロックＢを、水平方向にｐ等分、垂直方向にｑ等分した各分割領域（ｐ×ｑ個）をサブブロックとして定義する。そして、入力した画素ブロックＢ内の画素データを各サブブロックに分配する。なお、ここで、ｐ、及び、ｑは１以上の整数であり、いずれか一方は少なくとも２以上の整数である。
【００３１】
実施形態における分配部１３１は、入力した１６×１６画素のブロックＢを、水平、垂直方向とも２等分して、４つのサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を構築する。式で示せば次式（３）の通りである。
ＳＢ０（ｘ，ｙ）←Ｂ（ｘ，ｙ）
ＳＢ１（ｘ，ｙ）←Ｂ（ｘ＋８，ｙ）
ＳＢ２（ｘ，ｙ）←Ｂ（ｘ，ｙ＋８）
ＳＢ３（ｘ，ｙ）←Ｂ（ｘ＋８，ｙ＋８）        …（３）
ここでｘ、ｙは０乃至７の整数である。
【００３２】
符号化処理部１３０は、上記式（３）で示されるサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３それぞれの符号化データを結合して出力することになる。
【００３３】
次に、符号化処理部１４０について説明する。符号化処理部１４０内の分配部１４１は符号化処理部１３０内の分配部１３１と同じである（図３（ｂ）参照）。また、分配部１４０内の圧縮部１４２乃至１４５、連結部１４６、及び、差分予測部１４７は、符号化処理部１２０内の圧縮部１２２乃至１２５、連結部１２６、及び、差分予測部１２７と同じである。それ故、差分予測部１２７は、サブブロックＳＢ０については、そのまま圧縮部１４２に出力し、他のサブブロックＳＢ１，ＳＢ２，ＳＢ３について次式（４）によってサブブロックＳＢ１’、ＳＢ２’、ＳＢ３’を演算し、圧縮部１４３乃至１４５に出力する。
ＳＢ１’←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ１（ｘ，ｙ）｝
ＳＢ２’←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ２（ｘ，ｙ）｝
ＳＢ３’←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ３（ｘ，ｙ）｝      …（４）
【００３４】
上記の式（４）は、先に示した式（２）と同じであるが、式（４）内におけるサブブロックＳＢ１、ＳＢ２、ＳＢ３は、式（３）によって得られた結果である点に注意されたい。
【００３５】
以上、符号化処理部１１０、１２０、１３０、１４０について説明した。
【００３６】
各符号化処理部は、生成した符号化データを、先に説明したように、選択部１７０に出力されると共に、対応する符号量検知部１５１、１５２、１５３、１５４にも出力する。そして、選択部１７０は、４つの符号化データの中で最もデータ量の少ない符号化データを選択して、出力する。この際、選択部１７０は、どの符号化処理部からの符号化データが選択されたのかを示す識別情報（実施形態では４種類であるので２ビット）を、ヘッダに格納する。つまり、選択部１７０から出力される１６×１６画素のブロックＢの符号化データのフォーマットは、図４に示す様になる。図示の如く、識別情報がヘッダとなり、それに後続してサブブロックＳＢ０の符号化データ、ＳＢ１又はＳＢ１’の符号化データ、ＳＢ２又はＳＢ２’の符号化データ、ＳＢ３又はＳＢ３’の符号化データが配置される。
【００３７】
以上、実施形態における画像符号化装置を説明した。次に、実施形態における画像復号装置を説明する。なお、以下の説明における表記は、符号化装置での表記を用いるものとし、その説明は省略する。
【００３８】
図２は、画像復号装置のブロック構成図である。本装置は、識別情報分離部２０１、伸長部２０２、サブブロック復元部２０３、サブブロック統合部２０４で構成される。
【００３９】
符号化データが本装置に入力されると、識別情報分離部２０１は符号化データのヘッダの識別情報（２ビット）を分離、抽出し、その識別情報をサブブロック復元部２０３、サブブロック統合部２０４に出力する。
【００４０】
伸長部２０２は、識別情報に後続する符号化データを入力し、伸長処理（復号処理）を行ない、｛ＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３｝、もしくは、｛ＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’｝を生成し、サブブロック復元部２０３に出力する。
【００４１】
識別情報が、符号化処理部１１０、１３０のいずれかにより符号化されたことを示す情報である場合、入力したデータは｛ＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３｝であることになる。この場合、サブブロック復元部２０３は、入力したデータをそのままサブブロック統合部２０４に出力する。
【００４２】
一方、識別情報が、符号化処理部１２０、１４０のいずれかにより符号化されたことを示す情報で場合、伸長部２０２から入力したデータは｛ＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’｝であることになる。この場合、サブブロック復元部２０３は、サブブロックＳＢ０については、そのままサブブロック統合部２０４に出力する。そして、サブブロック復元部２０３は、残りのＳＢ１’、ＳＢ２’、ＳＢ３’について、次式（５）によりサブブロックＳＢ１、ＳＢ２、ＳＢ３を復元する。
ＳＢ１←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ１’（ｘ，ｙ）｝
ＳＢ２←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ２’（ｘ，ｙ）｝
ＳＢ３←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ３’（ｘ，ｙ）｝      …（５）
【００４３】
サブブロック統合部２０４は、サブブロック復元部２０３からのサブブロックＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３を入力し、識別情報に基づき１６×１６画素のブロックＢを構築する。具体的には、次の通りである。
【００４４】
識別情報が符号化処理部１３０、１４０のいずれかにより符号化されたことを示す情報であったとする。この場合、サブブロック統合部２０４は、単純にサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を、図３（ｂ）に示す形式、すなわち、次式に従って１６×１６画素の画素ブロックＢの各画素を統合し、出力する。
Ｂ（ｘ，ｙ）        ←  ＳＢ０（ｘ，ｙ）
Ｂ（ｘ＋８，ｙ）    ←  ＳＢ１（ｘ，ｙ）
Ｂ（ｘ，ｙ＋８）    ←  ＳＢ２（ｘ，ｙ）
Ｂ（ｘ＋８，ｙ＋８）←  ＳＢ３（ｘ，ｙ）
ここで、ｘ，ｙは０乃至７の整数である。
【００４５】
また、識別情報が符号化処理部１１０、１２０のいずれかにより符号化されたことを示す情報であったとする。この場合、サブブロック統合部２０４は、サブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を、図３（ａ）に示す形式で統合し、１６×１６画素の画素ブロックＢとして出力する。具体的には次式の通りである。
Ｂ（２ｘ，２ｙ）        ←  ＳＢ０（ｘ，ｙ）
Ｂ（２ｘ＋１，２ｙ）    ←  ＳＢ１（ｘ，ｙ）
Ｂ（２ｘ，２ｙ＋１）    ←  ＳＢ２（ｘ，ｙ）
Ｂ（２ｘ＋１，２ｙ＋１）←  ＳＢ３（ｘ，ｙ）
ここで、ｘ，ｙは０乃至７の整数である。
【００４６】
以上の結果、符号化対象の画像データを効率良く、符号化することが可能になり、その符号化データから画像を復元することが可能になる。
【００４７】
ここで、符号化対象の画像データ中の１６×１６画素のブロックが、例えば図５（ａ）に示す画像であったとする。この場合、画像符号化装置における符号化処理部１１０、１２０、１３０、１４０内の圧縮部１１２乃至１１５、１２２乃至１２５、１３２乃至１３４、１４２乃至１４５に入力されるサブブロック｛ＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３｝又は｛ＳＢ０、ＳＢ１’，ＳＢ２’，ＳＢ３’｝は図６乃至図９のようになる。
【００４８】
図６（ａ）乃至（ｄ）は符号化処理部１１０における圧縮部１１２乃至１１５に供給されるサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を示している。また、図７（ａ）乃至（ｄ）は符号化処理部１２０における圧縮部１２２乃至１２５に供給されるサブブロックＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’を示している。図８（ａ）乃至（ｄ）は符号化処理部１３０における圧縮部１３２乃至１３５に供給されるサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を示している。また、図９（ａ）乃至（ｄ）は符号化処理部１４０における圧縮部１４２乃至１４５に供給されるサブブロックＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’を示している。ここで、図７、図９では、サブブロックＳＢ１，ＳＢ２，ＳＢ３ではなく、ＳＢ１’，ＳＢ２’，ＳＢ３’である点に注意されたい。
【００４９】
図５（ａ）の画像の場合、ランが稼げるのは、図６か図７のいずれかである。すなわち、最終的に選択される符号化データは符号化処理部１１０、１２０のいずれかで生成されたものとなるであろう。
【００５０】
また、符号化対象の画像データ中の１６×１６画素のブロックが、例えば図５（ｂ）に示す画像であったとする。この場合、画像符号化装置における符号化処理部１１０、１２０、１３０、１４０のそれぞれの４つの圧縮部に入力されるサブブロック｛ＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３｝又は｛ＳＢ０、ＳＢ１’，ＳＢ２’，ＳＢ３’｝は図１０乃至図１３のようになる。
【００５１】
図１０（ａ）乃至（ｄ）は符号化処理部１１０における圧縮部１１２乃至１１５に供給されるサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を示している。また、図１１（ａ）乃至（ｄ）は符号化処理部１２０における圧縮部１２２乃至１２５に供給されるサブブロックＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’を示している。図１２（ａ）乃至（ｄ）は符号化処理部１３０における圧縮部１３２乃至１３５に供給されるサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を示している。また、図１３（ａ）乃至（ｄ）は符号化処理部１４０における圧縮部１４２乃至１４５に供給されるサブブロックＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’を示している。ここでも、図１１、図１３では、サブブロックＳＢ１，ＳＢ２，ＳＢ３ではなく、ＳＢ１’，ＳＢ２’，ＳＢ３’である点に注意されたい。
【００５２】
図５（ｂ）の画像の場合、ランが稼げるのは、図１３である。すなわち、最終的に選択される符号化データは符号化処理部１４で生成されたものとなる。
【００５３】
なお、上記実施形態では、１６×１６画素の画素ブロック内の画素を、４つの８×８画素のサブブロックに分配する例を２つ（図３（ａ），（ｂ））を示したが、３つ以上でも構わないし、その数に限定はされない。要するに、Ｍ×Ｎ画素の画素ブロック内の画素データを、その画素ブロックに含まれる画素数の１／Ｋ（Ｋは２以上の整数）個の画素数を格納するＫ個のサブブロックに分配する複数のアルゴリズムを用いるようにすればよい。例えば、１６×１６画素の画素ブロック内のライン番号をｉ（ｉ＝０乃至１５のいずれか）としたとき、ｉを４で除算した際の余りをｊとしたとき、第ｉラインの画像データをサブブロックＳＢ（ｊ）に分配するようにしても構わないであろう。
【００５４】
また、各符号化処理部には、分配部が設けられるものとして説明したが、いくつかはその構成を省くことができる。例えば、符号化処理部１１０、１２０内の分配部１１１、１２１は同じであるので、符号化処理部１２０内の分配部１２１を無くし、差分予測部１２７と第１の符号化処理部１１０内の分配部１１１とを接続しても構わない。
【００５５】
［第２の実施形態］
以下、本発明に係る第２の実施形態を説明する。
【００５６】
上記第１の実施形態では、符号化対象の画素ブロック内の画素データを、その画素ブロックに含まれる画素数の１／Ｋの画素数で構成されるＫ個のサブブロックＳＢ（０）乃至ＳＢ（Ｋ−１）のいずれかに分配し、符号化するものであった。本第２の実施形態では、更に、同じ符号化対象の画素ブロック内の画素データを、その画素ブロックに含まれる画素数の１／Ｊの画素数で構成されるＪ個のサブブロックＳＢ（０）乃至ＳＢ（Ｊ−１）のいずれかに分配する構成を加える例を説明する。ここで、Ｊは２以上の整数であり、Ｊ≠Ｋの関係にある。サブブロックのサイズが異なる、第１の分配方法と、第２の分配方法を有する点を特徴とする。
【００５７】
図１４は第２の実施形態の画像符号化装置のブロック構成図である。図１と同様の構成については同じ参照符号を付し、その説明は省略する（詳細は図１を参照されたい）。
【００５８】
図１４では、図１の構成に、符号化処理部３００、４００、及び、符号量検知部１５５、１５６を追加した点である。
【００５９】
なお、第１の実施形態では、符号化対象の画素ブロックは１６×１６画素のサイズである例を説明したが、本第２の実施形態では符号化対象の画素ブロックは１２×１２画素のサイズであるものとする。
【００６０】
従って、図１４における符号化処理部１１０、１２０、１３０、１４０におけるサブブロックのサイズは６×６画素サイズとなる点に注意されたい。
【００６１】
すなわち、本第２の実施形態における符号化処理部１１０内の分配部１１１は、図１５（ａ）に示すように、１２×１２画素のブロックＢ中の“０”で示される画素データを、６×６画素のサブブロックＳＢ０に分配し、生成する。同様にして、サブブロックＳＢ１、ＳＢ２、ＳＢ３を生成する。そして、符号化処理部１１０は、サブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３の符号化データを連結して選択部１７０に出力する。
【００６２】
符号化処理部１２０は、符号化処理部１１０とほぼ同じである。但し、符号化処理部１２０は、サブブロックＳＢ０、ＳＢ１’，ＳＢ２’，ＳＢ３’の符号化データを生成し、それらを連結して出力する。
【００６３】
また、本第２の実施形態における符号化処理部１３０内の分配部１３１（符号化処理部１４０内の分配部１４１も同様）は、図１５（ｂ）に示すように、１２×１２画素のブロックＢ中の“０”で示される画素データを、６×６画素のサブブロックＳＢ０に分配する。同様にして、サブブロックＳＢ１、ＳＢ２、ＳＢ３を生成する。そして、符号化処理部１３０は、サブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３の符号化データを連結して選択部１７０に出力する。
【００６４】
符号化処理部１４０は、符号化処理部１３０とほぼ同じである。但し、符号化処理部１４０は、サブブロックＳＢ０、ＳＢ１’，ＳＢ２’，ＳＢ３’の符号化データを生成し、それらを連結して出力する。
【００６５】
なお、本第２の実施形態における符号化処理部１１０、１２０、１３０、１４０内の各圧縮部で圧縮符号化するサブブロックのサイズは、第１の実施形態と異なるので、第１の実施形態とは異なるハフマン符号表を用いることが望ましい。これは、以下に説明する符号化処理部３００、４００についても同様である。
【００６６】
次に、本第２の実施形態にて新に追加した符号化処理部３００、４００について説明する。
【００６７】
符号化処理部３００は、図示の如く、分配部３０１、圧縮部３１１乃至３１９、連結部３２０で構成される。
【００６８】
分配部３０１は、入力した１２×１２画素の画素ブロックＢ内の各画素データを、９個の４×４画素サイズのサブブロックＳＢ０乃至ＳＢ８のいずれかに分配する。そして、生成されたサブブロックＳＢ０乃至ＳＢ８の画像データは圧縮部３１１乃至３１９に供給される。図１５（ｃ）は、画素ブロックＢと、各サブブロックＳＢ０乃至ＳＢ８との対応関係を示しており、式で示すのであれば次の通りである。
ＳＢ０（ｘ，ｙ）←Ｂ（３ｘ，３ｙ）
ＳＢ１（ｘ，ｙ）←Ｂ（３ｘ＋１，３ｙ）
ＳＢ２（ｘ，ｙ）←Ｂ（３ｘ＋２，３ｙ）
ＳＢ３（ｘ，ｙ）←Ｂ（３ｘ，３ｙ＋１）
ＳＢ４（ｘ，ｙ）←Ｂ（３ｘ＋１，３ｙ＋１）
ＳＢ５（ｘ，ｙ）←Ｂ（３ｘ＋２，３ｙ＋１）
ＳＢ６（ｘ，ｙ）←Ｂ（３ｘ，３ｙ）＋２
ＳＢ７（ｘ，ｙ）←Ｂ（３ｘ＋１，３ｙ＋２）
ＳＢ８（ｘ，ｙ）←Ｂ（３ｘ＋２，３ｙ＋２）        …（６）
ここでｘ、ｙは０乃至３の整数である。
【００６９】
圧縮部３１１乃至３１９は、上記のようにして生成されたサブブロックＳＢ０乃至ＳＢ８をそれぞれ符号化し、連結部３２０に出力する。連結部３２０は、サブブロックＳＢ０乃至ＳＢ８の符号化データ、この順番に連結し、選択部１７０及び符号量検知部１５５に出力する。
【００７０】
次に、符号化処理部４００を説明する。この符号化処理部４００は、分配部４０１、圧縮部４１１乃至４１９、連結部４２０、及び、差分予測部４３０で構成される。このうち、分配部４０１、圧縮部４１１乃至４１９、連結部４２０は、符号化処理部３００の分配部３０１、圧縮部３１１乃至３１９、連結部３２０と同じ機能とし、その説明は省略する。以下は差分予測部４３０の説明である。
【００７１】
差分予測部４３０は、９個のサブブロックＳＢ０乃至ＳＢ８のうちの１つをそのまま通過させる。そして、差分予測部４３０は、その１つのサブブロックと、残りの８のサブブロックとの差分を算出し、その差分結果を出力する。具体的な例として、差分予測部４３０は、分配部４０１で生成されたサブブロックＳＢ０については、そのまま圧縮部４１１に出力する。残りのサブブロックＳＢ１乃至ＳＢ８については、次式に従って、差分を算出し、その結果をサブブロックＳＢ１’乃至ＳＢ８’として圧縮部４１２乃至４１９に出力する。
ＳＢ１’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ１（ｘ，ｙ）｝
ＳＢ２’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ２（ｘ，ｙ）｝
ＳＢ３’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ３（ｘ，ｙ）｝
ＳＢ４’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ４（ｘ，ｙ）｝
ＳＢ５’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ５（ｘ，ｙ）｝
ＳＢ６’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ６（ｘ，ｙ）｝
ＳＢ７’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ７（ｘ，ｙ）｝
ＳＢ８’（ｘ，ｙ）←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ８（ｘ，ｙ）｝
【００７２】
圧縮部４１１はサブブロックＳＢ０を圧縮符号化し、符号化データを生成する。圧縮部４１２乃至４１９はサブブロックＳＢ１’乃至ＳＢ８’を符号化し、符号化データを生成する。連結部４２０は、サブブロックＳＢ０の符号化データ、サブブロックＳＢ１’乃至ＳＢ８’の符号化データを、この順番に連結し、選択部１７０及び符号量検知部１５６に出力する。
【００７３】
比較部１６０は、符号量検知部１５１乃至１５６から出力された符号量を示す値を比較し、最小符号量がいずれであるか判定する。そして、比較部１６０は、どの符号化処理部の符号化データは最小であったかを示す制御信号を選択部１７０に出力する。選択部１７０は、比較部１６０からの制御信号で特定された、符号化処理部１１０、１２０、１３０、１４０、３００、４００のいずれか１つの符号化データを選択し、出力する。このとき、どの符号化処理部からの符号化データを選択したのかを示す識別情報をヘッダに付加する。本第２の実施形態の場合、符号化処理部は全部で６個存在するので、識別情報は少なくとも３ビットが必要となる。
【００７４】
従って、選択部１７０が符号化処理部１１０、１２０、１３０、１４０のいずれかからの符号化データを選択した場合、符号化対象の１２×１２画素の符号化データのデータ構造は図１６（ａ）に示す様になる。一方、選択部１７０が符号化処理部３００、４００のいずれかからの符号化データを選択した場合、符号化対象の１２×１２画素の符号化データのデータ構造は図１６（ｂ）に示す様になる。
【００７５】
以上、第２の実施形態における画像符号化装置を説明した。次に、第２の実施形態における画像復号装置を説明する。なお、以下の説明における表記は、符号化装置での表記を用いるものとし、その説明は省略する。
【００７６】
図１７は、画像復号装置のブロック構成図である。本装置は、識別情報分離部５０１、伸長部５０２、サブブロック復元部５０３、サブブロック統合部５０４で構成される。
【００７７】
符号化データが本装置に入力されると、識別情報分離部５０１は符号化データのヘッダの識別情報（３ビット）を分離、抽出し、その識別情報を伸長部５０２、サブブロック復元部２０３、サブブロック統合部２０４に出力する。
【００７８】
ここで、識別情報分離部５０１からの識別情報が、図１６（ａ）の符号化データのデータ構造であることを示しているとする。即ち、復号対象の符号化データが符号化処理部１１０、１２０、１３０、１４０のいずれかによって生成されたかを示しているとする。この場合、伸長部５０２は、識別情報に後続して４つのサブブロックの符号化データが存在するものとし、｛ＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３｝、もしくは｛ＳＢ０、ＳＢ１’，ＳＢ２’，ＳＢ３’｝を復号する。そして、伸長部５０２は、その復号結果をサブブロック復元部５０３に出力する。
【００７９】
また、識別情報分離部５０１からの識別情報が、図１６（ｂ）の符号化データのデータ構造を示しているとする。すなわち、復号対象の符号化データが符号化処理部３００、４００のいずれかによって生成されたかを示しているとする。この場合、識別情報に後続して９つのサブブロックの符号化データが存在することになる。そこで、伸長部５０２は、９個のサブブロック｛ＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３、ＳＢ４、ＳＢ５、ＳＢ６、ＳＢ７、ＳＢ８｝、又は、｛ＳＢ０，ＳＢ１’，ＳＢ２’，ＳＢ３’、ＳＢ４’、ＳＢ５’、ＳＢ６’、ＳＢ７’、ＳＢ８’｝を復号し、サブブロック復元部５０３に出力する。
【００８０】
識別情報が、符号化処理部１１０、１３０のいずれかにより符号化されたことを示す情報であるとする。この場合、サブブロック復元部５０３は、入力したデータは｛ＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３｝であることになるので、そのままサブブロック統合部２０４に出力する。
【００８１】
識別情報が、符号化処理部３００により符号化されたことを示す情報である場合には、入力したデータは｛ＳＢ０，ＳＢ１，ＳＢ２，ＳＢ３、ＳＢ４、ＳＢ５、ＳＢ６、ＳＢ７、ＳＢ８｝であることになる。そこで、サブブロック復元部５０３は、そのままサブブロック統合部２０４に出力する。
【００８２】
また、識別情報が、符号化処理部１２０、１４０のいずれかにより符号化されたことを示す情報である場合には、入力したデータは｛ＳＢ０、ＳＢ１’、ＳＢ２’、ＳＢ３’｝であることになる。そこで、サブブロック復元部５０３は、サブブロックＳＢ０を用いて、サブブロックＳＢ１、ＳＢ２、ＳＢ３を構築する。具体的には、第１の実施形態における式（５）を参照されたい。
【００８３】
また、識別情報が、符号化処理部４００により符号化されたことを示す情報である場合には、入力したデータは｛ＳＢ０，ＳＢ１’，ＳＢ２’，ＳＢ３’、ＳＢ４’、ＳＢ５’、ＳＢ６’、ＳＢ７’、ＳＢ８’｝であることになる。そこで、サブブロック復元部５０３は、ＳＢ０を用いて、サブブロックＳＢ１乃至ＳＢ８を次式に従って構築する。
ＳＢ１←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ１’（ｘ，ｙ）｝
ＳＢ２←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ２’（ｘ，ｙ）｝
ＳＢ３←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ３’（ｘ，ｙ）｝
ＳＢ４←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ４’（ｘ，ｙ）｝
ＳＢ５←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ５’（ｘ，ｙ）｝
ＳＢ６←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ６’（ｘ，ｙ）｝
ＳＢ７←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ７’（ｘ，ｙ）｝
ＳＢ８←ＸＯＲ｛ＳＢ０（ｘ，ｙ），ＳＢ８’（ｘ，ｙ）｝  …（７）
【００８４】
サブブロック統合部５０４は、サブブロック復元部５０３からのサブブロックＳＢ０乃至ＳＢ３、又は、ＳＢ０乃至ＳＢ８を入力し、識別情報に基づき１２×１２画素のブロックＢを構築する。
【００８５】
より具体的には、識別情報が符号化処理部１３０、１４０のいずれかにより符号化されたことを示す情報で場合、サブブロック統合部５０４は、単純にサブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を、図１５（ｂ）に示す形式、すなわち、次式に従って１２×１２画素の画素ブロックＢの各画素を求め、出力する。
Ｂ（ｘ，ｙ）        ←  ＳＢ０（ｘ，ｙ）
Ｂ（ｘ＋６，ｙ）    ←  ＳＢ１（ｘ，ｙ）
Ｂ（ｘ，ｙ＋６）    ←  ＳＢ２（ｘ，ｙ）
Ｂ（ｘ＋６，ｙ＋６）←  ＳＢ３（ｘ，ｙ）
ここで、ｘ，ｙは０乃至５の整数である。
【００８６】
また、識別情報が符号化処理部１１０、１２０のいずれかにより符号化されたことを示す情報で場合、サブブロック統合部５０４は、サブブロックＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３を、図１５（ａ）に示す形式で統合し、１２×１２画素の画素ブロックＢとして出力する。具体的には次式の通りである。
Ｂ（２ｘ，２ｙ）        ←  ＳＢ０（ｘ，ｙ）
Ｂ（２ｘ＋１，２ｙ）    ←  ＳＢ１（ｘ，ｙ）
Ｂ（２ｘ，２ｙ＋１）    ←  ＳＢ２（ｘ，ｙ）
Ｂ（２ｘ＋１，２ｙ＋１）←  ＳＢ３（ｘ，ｙ）
ここで、ｘ，ｙは０乃至５の整数である。
【００８７】
また、識別情報が符号化処理部３００、又は４００により符号化されたことを示す情報で場合、サブブロック統合部５０４は、単純にサブブロックＳＢ０乃至ＳＢ８を図１５（ｃ）に示す形式、すなわち、次式に従って１２×１２画素の画素ブロックＢの各画素を求め、出力する。
Ｂ（３ｘ，３ｙ）        ←  ＳＢ０（ｘ，ｙ）
Ｂ（３ｘ＋１，３ｙ）    ←  ＳＢ１（ｘ，ｙ）
Ｂ（３ｘ＋２，３ｙ）    ←  ＳＢ２（ｘ，ｙ）
Ｂ（３ｘ，３ｙ＋１）    ←  ＳＢ３（ｘ，ｙ）
Ｂ（３ｘ＋１，３ｙ＋１）←  ＳＢ４（ｘ，ｙ）
Ｂ（３ｘ＋２，３ｙ＋１）←  ＳＢ５（ｘ，ｙ）
Ｂ（３ｘ，３ｙ＋２）    ←  ＳＢ６（ｘ，ｙ）
Ｂ（３ｘ＋１，３ｙ＋２）←  ＳＢ７（ｘ，ｙ）
Ｂ（３ｘ＋２，３ｙ＋２）←  ＳＢ８（ｘ，ｙ）
ここで、ｘ，ｙは０乃至３の整数である。
【００８８】
以上説明したように、本第２の実施形態によれば、第１の実施形態の作用効果に加えて、３画素周期で変化する画像データについても圧縮効率を上げることが可能となる。
【００８９】
なお、第２の実施形態においても、符号化部１３０、１４０と同様の構成、すなわち、１２×１２画素のブロックを水平、垂直方向とも３等分にしたサブブロックに分配し、それぞれを符号化する２つの符号化処理部を更に追加しても構わない。
【００９０】
さらに、この分配方法以外にも別の分配方法を追加することで、様々な種類の画像に対して効率的な圧縮を行うことが可能である。
【００９１】
［第３の実施形態］
第３の実施形態を説明する。本第３の実施形態は、先に示した第１の実施形態の２値画像用の符号化装置を組み込んだ、固定長符号化データを生成する画像符号化装置を例に説明する。なお、２値画像用の符号化装置として、第２の実施形態を適用しても構わないことは以下の説明から明らかであることを付言しておく。
【００９２】
本第３の実施形態における符号化装置のブロック構成図を図１８に示す。本装置は、装置全体の制御を司る制御部２１５０、ブロック化部２１０１、抽出色決定部２１０２、第１の符号化部２１０３、符号量検出部２１０４、多重化部２１０５、置換部２１０６、第２の符号化部２１０７、符号量調整部２１０８で構成される。
【００９３】
上記構成において、第１の符号化部２１０３が、第１の実施形態で示した構成（図１）を有するものものである。また、各処理部における処理に要する時間は、互いに異なるので、各処理部の前段には互いに同期するためのバッファメモリが設けられているものとする。
【００９４】
以下、同図の構成における処理内容を説明する。
【００９５】
ブロック化部２１０１は、符号化対象の多値画像データから、複数画素で構成されるブロック（Ｍ×Ｎ画素）単位に入力し、後段に出力する。本第３の実施形態における第１の符号化部２１０３は第１の実施形態の構成を有するものであるので、Ｍ＝Ｎ＝１６となる。
【００９６】
本第３の実施形態では、説明を簡単なものとするため、符号化対象の画像データの各画素は、Ｒ，Ｇ，Ｂの成分で構成され、各成分は８ビット（２５６階調）とする。また、１ブロックは上記の通り１６×１６画素のサイズとする。ブロック化部２１０１は、Ｒ成分のブロックデータ、Ｇ成分のブロックデータ、Ｂ成分のブロックデータの順に出力する。ただし、色成分の種類はＲＧＢに限らず、ＹＭＣでも良いし、成分の数、ビット数もこれに限定されるものではない。
【００９７】
抽出色決定部２１０２は、入力した１つの色成分のブロック内の１６×１６（＝２５６）の画像データに、高周波成分となる画素があるか否かを判定し、その画素の色を抽出色として抽出し、多重化部２１０５に出力する。また、抽出色決定部２１０２は、抽出色を持つ画素と、非抽出色を持つ画素を識別するための２値データを置換色算出部２１０９、第１の符号化部２１０３に出力する。この２値のデータが“１”の場合、該当する画素は抽出色を持つ画素であるものとし、“０”の場合には該当する画素は非抽出色の画素とする。実施形態では、１つのブロックは１６×１６個の画素で構成されるわけであるから、抽出色決定部２１０２は１６×１６個の２値データを生成することになる。この２値データは、ブロック内の各画素が抽出色、非抽出色のいずれであるかを識別するために用いられるので、これ以降、画素識別情報と呼ぶ。
【００９８】
抽出色決定部２１０２における抽出色、画素識別情報を求めるアルゴリズムの一例を示すのであれば次の通りである。
【００９９】
先ず、ブロック内の画素の平均値を算出する。そして、その平均値よりも大きな値を持つ画素群（以下、第１の画素群という）と、その平均値以下の画素群（以下、第２の画素群という）とに分類する。更に、第１の画素群の平均値（第１の平均値）と第２の画素群の平均値（第２の平均値）を求め、それらの差の絶対値が、予め設定された閾値を超えるか否かを判定する。
【０１００】
第１、第２の平均値の差の絶対値が、上記の閾値を超えている場合、抽出色決定部２１０２は、抽出色有りを示す抽出色有無情報を多重化部２１０５に通知する。そして、第２の画素群を、抽出色を持つ画素として見なし、その色情報を抽出色情報として多重化部２１０５に出力する。また、抽出色を持つ画素の位置では“１”、非抽出色の画素の位置では“０”とする画素識別情報を第１の符号化部２１０３、置換部２１０６に出力する。なお、画素識別情報はラスタースキャン順に出力するものとする。
【０１０１】
一方、第１、第２の平均値の差の絶対値が、上記の閾値以下の場合、抽出色決定部２１０２は、抽出色無しを示す抽出色有無情報を多重化部２１０５に通知する。また、抽出色決定部２１０２は全てが“０”の位置情報を出力する。また、抽出色決定部２１０２は、抽出色情報は出力してもしなくても構わない。多重化部２１０５は、抽出色無しを示す抽出色有無情報を受信した場合、抽出色決定部２１０２からの抽出色情報は無視するからである。
【０１０２】
以上、抽出色決定部２１０２における処理内容を説明したが、これは一例である点に注意されたい。詳細は後述する説明から明らかになるが、抽出色決定部２１０２は、着目ブロック内の高周波成分を抽出するようにすればよい。
【０１０３】
第１の符号化部２１０３は、抽出色決定部２１０２から出力された１６×１６個の２値の画素識別情報を符号化し、その符号化データを多重化部２１０５に出力する。第１の符号化部２１０３の符号化する対象の画素識別情報は、０、１のいずれかの値を持つ１６×１６個の情報であるので、第１の実施形態で説明した符号化処理がそのまま適用できるのは理解できよう。
【０１０４】
符号量検出部２１０４は、第１の符号化部２１０３から出力された１ブロック分の画素識別情報の符号化データ量（ビット数）を検出し、その結果を符号量調整部２１０８に出力する。この符号量調整部２１０８の詳細は後述する。
【０１０５】
次に、置換部２１０６について説明する。置換部２１０６内の置換色算出部２１０９は、画素識別情報が“０”の画素（非抽出色の画素）の各成分の平均値を算出し、その算出した色を置換色データとしてセレクタ２１１０に出力する。具体的には、着目ブロックの座標（ｘ，ｙ）（ｘ、ｙ＝０、１、…、１５）の位置にある色成分の値をＰ（ｘ，ｙ）、画素識別情報をＩ（ｘ，ｙ）（＝０、又は１のいずれか）、画素識別情報が“０”の個数をＮとしたとき、平均値Aveは次式の通りである。
Ａｖｅ＝ΣΣＰ（ｉ，ｊ）×（１−Ｉ（ｉ，ｊ））／Ｎ
ここで、ΣΣは、変数ｉ，ｊの取り得る範囲（０乃至１５）での合算関数である。
そして、置換色算出部２１０９は、算出したＡｖｅを置換色データとしてセレクタ２１１０に出力する。なお、着目ブロック内に、画素識別情報が“０”となる個数が０の場合、つまり、Ｎ＝０となる場合には上記算出は行なわず、適当な値を出力して構わない。理由は、Ｎ＝０の場合、セレクタ２１１０は、ブロック化部２１０１からの２５６個の画素データを選択し、出力するからである。
【０１０６】
セレクタ２１１０は、画素識別情報が“１”の場合、置換色算出部２１０９から出力された置換色情報Ａｖｅを選択し、画素識別情報が“０”の場合にはブロック化部２１０１からの画素データを選択し、出力する。
【０１０７】
実施形態における置換部２１０６は、要するに、抽出色と判定された画素の各成分の値を、非抽出色の画素の平均値で置換して、第２の符号化部２１０７に出力する。この結果、置換部２１０６から出力される１６×１６画素のブロックの画像は、空間周波数の低い画像に変換されることになる。
【０１０８】
第２の符号化部２１０７は、例えば、非可逆の符号化の代表であるＪＰＥＧ符号化部（ＤＣＴ変換、量子化、エントロピー符号化）であり、置換部１０６から出力された１６×１６画素の画像データを４つの８×８画素のサブブロックに分配する。そして、第２の符号化部２１０７は、４つのサブブロックそれぞれについて、公知のＤＣＴ変換、量子化、エントロピー符号化を行なう。このとき、１つのサブブロックには、１つのＤＣ成分と、６３個のＡＣ成分が含まれる。そこで、データの並びとしては、４つのＤＣ成分の符号化データを先ず出力する。そして、４つのサブブロックのＡＣ成分については、それぞれを低周波から高周波に向かうジグザグスキャン順し、互い違いに出力する。このようにする理由は、後述する符号量調整によって各サブブロックのＤＣ成分がカットされることを防ぐためである。
【０１０９】
第２の符号化部２１０７は、上記のようにして生成した符号化データ（１６×１６画素のブロックの符号化データ）を、符号量調整部１０８に出力する。
【０１１０】
符号量調整部２１０８は、符号量検出部２１０４から出力された画素識別情報の符号化データ量に従い、第２の符号化部から出力された階調画像データの符号化データのデータ量抑制手段として機能する。これにより１ブロック当たりの符号化データ量を、画質劣化の少ない固定長Ｌとする。
【０１１１】
ここで、第１の符号化部２１０３で生成される最大符号化データ量を仮にＬ０、第２の符号化部２１０７で生成される４つのＤＣ成分の最大符号化データ量をＬ１としたとき、本第３の実施形態における固定長Ｌは、最低でも、Ｌ≧ブロックヘッダ長＋Ｌ０＋Ｌ１を満たすものとする。
【０１１２】
１ブロックの符号化データを固定長Ｌを上記のように定めると、文字線画等の解像度が要求される情報は可逆となり、尚且つ、階調画像についてもそのＤＣ成分が確実に維持させることができる。また、仮に、第２の符号化部２１０７で生成された符号化データの全てが、固定長Ｌ内に納めることができない場合には、その位置でカット（破棄）する。この結果、固定長であるが故に、どの画素ブロックからでも復号することができる。
【０１１３】
図１９は第３の実施形態における画像符号化装置の多重化部２１０５より出力された符号化データで構成される画像データファイル２２００の構造を示している。
【０１１４】
多重化部２１０５は、符号化データを出力するに先立ち、ファイルヘッダを生成し、出力する。ファイルヘッダには、画像のサイズ（水平、垂直方向の画素数）、色空間を特定する情報、及び、各色成分を表わすビット数、及び、１ブロック分の符号化データのデータ長等、復号処理に必要な情報が含まれている。また、各ブロックの符号化データは、図示の如く、参照番号２２０１、２２０２のタイプのいずれかである。符号化データ２２０１は抽出色無しのデータ構造を示し、符号化データ２２０２は抽出色有りのデータ構造を示している。抽出色無しの１ブロック分のデータ構造は、抽出色無しを示す情報を格納したブロックヘッダと、第２の符号化部２１０７で生成された階調画像の符号化データで構成される。一方、符号化データ２２０２は、抽出色有りを示す情報を格納したブロックヘッダと、抽出色情報、画素識別情報の符号化データ、及び、階調画像の符号化データで構成される。いずれの場合でも、符号化データ２２０１、２２０２は共に同じデータ長である。
【０１１５】
なお、本第３の実施形態の符号化データを復号する装置は、１ブロック分の非可逆符号化データをエントロピー復号する際、カットされ、復号できなかったＡＣ成分については適当な値（例えば０）と見なし、復号処理し、階調画像を復元すればよい。そして、画素識別情報を復号した結果、“１”の画素位置には、抽出色の画素値で置換すればよい。
【０１１６】
以上説明したように、本第３の実施形態によれば、ブロック画像の固定長符号化に本発明を適用することにより、識別情報が複雑であっても効率的な圧縮が可能となり、置換画像の圧縮に与えられる符号量が増すことによって画像品質の向上を図ることが出来る。
【０１１７】
［第４の実施形態］
以上説明した第１乃至第３の実施形態は、コンピュータ内のマイクロプロセッサが読込み実行するコンピュータプログラムでもって実現しれも構わない。この場合、コンピュータプログラムは、図１、図２、図１４、図１７、図１８に示す各処理部に相当する関数プログラムをマージして構成すれば良い。また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されており、それをコンピュータが有する読取り装置（ＣＤ−ＲＯＭドライブ等）にセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も本発明の範疇に入ることは明らかである。
【図面の簡単な説明】
【０１１８】
【図１】第１の実施形態における画像符号化装置のブロック構成図である。
【図２】第１の実施形態における画像復号装置のブロック構成図である。
【図３】第１の実施形態における各分配部の画素データの分配を行なう際に参照するテーブルを示す図である。
【図４】第１の実施形態における１ブロック分の符号化データのデータフォーマットを示す図である。
【図５】符号化対象の画像データの示す図である。
【図６】第１の実施形態の装置における符号化処理部１１０で符号化するサブブロックを示す図である。
【図７】第１の実施形態の装置における符号化処理部１２０で符号化するサブブロックを示す図である。
【図８】第１の実施形態の装置における符号化処理部１３０で符号化するサブブロックを示す図である。
【図９】第１の実施形態の装置における符号化処理部１４０で符号化するサブブロックを示す図である。
【図１０】第１の実施形態の装置における符号化処理部１１０で符号化するサブブロックを示す図である。
【図１１】第１の実施形態の装置における符号化処理部１２０で符号化するサブブロックを示す図である。
【図１２】第１の実施形態の装置における符号化処理部１３０で符号化するサブブロックを示す図である。
【図１３】第１の実施形態の装置における符号化処理部１４０で符号化するサブブロックを示す図である。
【図１４】第２の実施形態における画像符号化装置のブロック構成図である。
【図１５】第２の実施形態における各分配部の画素データの分配を行なう際に参照するテーブルを示す図である。
【図１６】第２の実施形態に係る１ブロック分の符号化データのデータフォーマットを示す図である。
【図１７】第２の実施形態における画像復号装置のブロック構成図である。
【図１８】第３の実施形態における画像符号化装置のブロック構成図である。
【図１９】第３の実施形態に係る１ブロック分の符号化データのデータフォーマットを示す図である。
【図１】
0005086777.tif 000002
【図２】
0005086777.tif 000003
【図３】
0005086777.tif 000004
【図４】
0005086777.tif 000005
【図５】
0005086777.tif 000006
【図６】
0005086777.tif 000007
【図７】
0005086777.tif 000008
【図８】
0005086777.tif 000009
【図９】
0005086777.tif 000010
【図１０】
0005086777.tif 000011
【図１１】
0005086777.tif 000012
【図１２】
0005086777.tif 000013
【図１３】
0005086777.tif 000014
【図１４】
0005086777.tif 000015
【図１５】
0005086777.tif 000016
【図１６】
0005086777.tif 000017
【図１７】
0005086777.tif 000018
【図１８】
0005086777.tif 000019
【図１９】
0005086777.tif 000020