(57)【要約】【課題】  ブロック単位に符号化する場合、互いに異なるスキャンルートに従って画素データを並べ替え、符号化し、その中の最小データ量の符号化データを注目ブロックの符号化データとして出力することで、画像全体に対して高い圧縮率の符号化データを生成する。【解決手段】  ブロック化部１０１は、複数画素で構成されるブロックを単位に入力し、符号化処理部１７１乃至１７４に出力する。符号化処理部１７１乃至１７４は、互いに異なるスキャンルートに従って、入力したブロック内の画素データの並び替えを行ない、可変長符号化を行なう。符号量検知部１５１は、各符号化処理部１７１乃至１７３で生成された符号化データのデータ量を検知し、符号量比較部１６１は各符号化データのデータ量を比較し、最小データ量の符号化データがいずれであるのかを示す制御信号をセレクタ１４１に出力する。セレクタ１４１は、この制御信号に従い、符号化データの１つを選択し、出力する。【選択図】  図１
2009005016.tif 000002
【特許請求の範囲】
【請求項１】
画像データを符号化する画像符号化装置であって、
複数画素で構成されるブロックを単位に画像データをスキャンし、当該スキャンの順に、該画像データを予測符号化することにより符号化データを生成する複数の符号化処理手段と、
前記符号化処理手段のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択手段と、
前記複数の符号化データのいずれが選択されたかを示す識別情報と、選択された符号化データとを出力する出力手段とを備え、
前記符号化処理手段のそれぞれは、互いに異なるスキャンルートに従ってブロック内の画素データをスキャンすることを特徴とする画像符号化装置。
【請求項２】
前記符号化処理手段のそれぞれの予測符号化は、着目画素の直前に入力した画素データを、前記着目画素の予測値として用い、予測誤差符号化することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記選択手段は、前記符号化処理手段のそれぞれで生成された符号化データに加えて、１ブロック分の非符号化の画像データのデータ量の中の最小のデータを選択することを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
画像データを符号化する画像符号化装置の制御方法であって、
複数画素で構成されるブロックを単位に画像データをスキャンし、当該スキャンの順に、該画像データを予測符号化することにより符号化データを生成する複数の符号化処理工程と、
前記符号化処理工程のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択工程と、
前記複数の符号化データのいずれが選択されたかを示す識別情報と、選択された符号化データとを出力する出力工程とを備え、
前記符号化処理工程のそれぞれは、互いに異なるスキャンルートに従ってブロック内の画素データをスキャンすることを特徴とする画像符号化装置の制御方法。
【請求項５】
コンピュータが読込み実行することで、前記コンピュータを請求項１乃至３のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項６】
画像データを符号化する画像符号化装置であって、
複数画素で構成されるブロックを単位に画像データを入力する入力手段と、
入力したブロックの画像データ中の各画素が、抽出部に属するのか、背景部に属するのかを識別し、前記ブロック内の各画素位置毎の識別情報を生成する生成手段と、
生成された前記識別情報を符号化する第１の符号化手段と、
前記背景部に属する画素データから、前記抽出部に属する画素に対する置換情報を生成し、生成された置換情報で、前記抽出色を持つ画素のデータを置換する置換手段と、
前記置換手段による置換後のブロック内の画素データを符号化する第２の符号化手段と、
前記第１、第２の符号化手段で生成された符号化データを多重化し、出力する多重化手段とを備え、
前記第１の符号化手段は、
前記生成手段で生成された前記ブロックの識別情報を、互いに異なるスキャンルートに従って並び替え、並び替え後の識別情報を符号化する複数の符号化処理手段と、
前記符号化処理手段のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択手段と、
前記選択手段で選択された符号化データが、前記複数の符号化処理手段のいずれで生成されたのかを特定する情報と、選択された符号化データとを出力する出力手段とを備えることを特徴とする画像符号化装置。
【請求項７】
前記符号化処理手段のそれぞれは、前記並び替え後の着目している識別情報と、直前の識別情報とが一致するか否かを判定し、一致を示すラン、不一致を示すランを符号化するランレングス符号化手段を有することを特徴とする請求項６に記載の画像符号化装置。
【請求項８】
前記ランレングス符号化手段は、前記一致を示すランのためのテーブルと、前記不一致を示すランのためのテーブルの２つを用いてランレングス符号化することを特徴とする請求項７に記載の画像符号化装置。
【請求項９】
前記選択手段は、前記符号化処理手段のそれぞれで生成された符号化データに加えて、１ブロック分の非符号化の前記識別情報のデータを含めた中の最小のデータを選択することを特徴とする請求項６乃至８のいずれか１項に記載の画像符号化装置。
【請求項１０】
画像データを符号化する画像符号化装置の制御方法であって、
複数画素で構成されるブロックを単位に画像データを入力する入力工程と、
入力したブロックの画像データ中の各画素が、抽出部に属するのか、背景部に属するのかを識別し、前記ブロック内の各画素位置毎の識別情報を生成する生成工程と、
生成された前記識別情報を符号化する第１の符号化工程と、
前記背景部に属する画素データから、前記抽出部に属する画素に対する置換情報を生成し、生成された置換情報で、前記抽出色を持つ画素のデータを置換する置換工程と、
前記置換工程による置換後のブロック内の画素データを符号化する第２の符号化工程と、
前記第１、第２の符号化工程で生成された符号化データを多重化し、出力する多重化工程とを備え、
前記第１の符号化工程は、
前記生成工程で生成された前記ブロックの識別情報を、互いに異なるスキャンルートに従って並び替え、並び替え後の識別情報を符号化する複数の符号化処理工程と、
前記符号化処理工程のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択工程と、
前記選択工程で選択された符号化データが、前記複数の符号化処理工程のいずれで生成されたのかを特定する情報と、選択された符号化データとを出力する出力工程とを備えることを特徴とする画像符号化装置の制御方法。
【請求項１１】
コンピュータが読込み実行することで、前記コンピュータを請求項６乃至９のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項１２】
請求項５又は１１に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの符号化技術に関するものである。
【背景技術】
【０００２】
従来、画像を符号化する方法として、予測符号化や直交変換符号化などの方法あった。予測符号化は、着目画素を符号化する際、既に符号化の終わった周辺画素から着目画素の予測値を演算し、その予測値と実際の着目画値の差分（予測誤差）を符号化するものである。通常、予測誤差が小さいほど短い符号語を割り当てる。従って、予測値の算出方法によって、生成される符号化データ量が大きく変わる。
【０００３】
そこで、複数の予測符号化方法を選択的に用いて符号化する技術が知られている（特許文献１）。
【０００４】
また、符号化対象となる複数の二次元配列のデータを一次元配列のデータに変換する技術（走査方式）も知られている（特許文献２）。
【特許文献１】特開平９−３７２４６号公報
【特許文献２】特開２００３−０３７８４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、これまでの画像符号化技術では、決まったスキャン順に画像データを符号化していたので、画像によっては符号化効率が下がるという問題があった。
【０００６】
そこで、本発明は、簡単な構成でありながらも、符号化に適したスキャン順に変えることで、符号化効率の高い符号化データを生成する技術を提供しようとするものである。
【課題を解決するための手段】
【０００７】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像データを符号化する画像符号化装置であって、
複数画素で構成されるブロックを単位に画像データをスキャンし、当該スキャンの順に、該画像データを予測符号化することにより符号化データを生成する複数の符号化処理手段と、
前記符号化処理手段のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択手段と、
前記複数の符号化データのいずれが選択されたかを示す識別情報と、選択された符号化データとを出力する出力手段とを備え、
前記符号化処理手段のそれぞれは、互いに異なるスキャンルートに従ってブロック内の画素データをスキャンすることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、互いに異なるスキャンルートに従ってブロック内の画素データを配列させて符号化し、その中の最小データ量の符号化データを注目ブロックの符号化データとして出力する。この結果、画像全体に対して高い圧縮率の符号化データを生成することが可能になる。
【発明を実施するための最良の形態】
【０００９】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１０】
＜第１の実施形態＞
図１は、第１の実施形態の画像符号化装置のブロック構成図を示している。
【００１１】
同図において、１０１はブロック化部、１７１乃至１７４は符号化処理部、１４１はセレクタ、１５１は符号量検知部、１６１は符号量比較部である。
【００１２】
符号化処理部１７１は、スキャン変換部１１１、前置予測部１２１及び可変長符号化部１３１を有する。また、符号化処理部１７２は、スキャン変換部１１２、前置予測部１２２及び可変長符号化部１３２を有する。符号化処理部１７３は、スキャン変換部１１３、前置予測部１２３及び可変長符号化部１３３を有する。そして、符号化処理部１７４は、スキャン変換部１１４、前置予測部１２４及び可変長符号化部１３４を有する。
【００１３】
なお、実施形態では、符号化処理部は４つで構成される例を説明するが、本発明がこの数に限定されるものではない。要は、複数の符号化処理部を備えれば良い。
【００１４】
ブロック化部１０１は、符号化対象の画像データから、予め設定されたサイズのブロック（ｎ×ｍ画素）の画像データ（以下、ブロックデータという）を入力し、符号化処理部１７１乃至１７４、及び、セレクタ１４１に出力する。実施形態では、ブロックのサイズを８×８画素とし、１画素がＲ，Ｇ，Ｂの３つの成分で構成され、且つ、各成分は８ビットであるものとする。なお、これらは一例であって、ブロックサイズはｍ×ｎ画素でよく、色空間はＲＧＢに限らず、ＹＭＣ（及びＫ）、Ｌａｂ、ＹＣｂＣｒ等でも構わず、各成分のビット数も８ビットに限定されるものではない。また、ブロック化部１０１が入力する画像データの発生源は、イメージスキャナとする。しかしながら、印刷データに基づいてレンダリングするレンダリング部、無圧縮の画像データをファイルとして記憶している記憶媒体（この場合は記憶媒体をアクセスするドライブを有する）でも構わず、その種類も問わない。
【００１５】
符号化処理部１７１乃至１７４内のスキャン変換部１１１〜１１４それぞれは、入力したブロックデータを図２（ａ）乃至（ｄ）に示すように、互いに異なるスキャンルートに従ってスキャンして（読込み）、出力する。すなわち、スキャン変換部１１１〜１１４は、互いに異なるスキャンルート（スキャンの順序）に従って、ブロックデータ内の各画素の順番を並べ替えを行ない、並べ替え変更後の画素データを出力する。図２（ａ）は、垂直方向のジグザグスキャン、同図（ｂ）は水平方向ジグザグスキャン、同図（ｃ）は４５°ジグザグスキャン、そして、同図（ｄ）は１３５°ジグザグスキャンの例である。実施形態では、１ブロック＝８×８画素の例を説明しているので、スキャン変換部１１１乃至１１４は、それぞれ６４個の画素データを並べ替えを行ない、出力することになる。
【００１６】
各符号化処理部内の前置予測部１２１乃至１２４は、それぞれ同じ処理を行なうものであり、回路設計も同じである。また、同様に、可変長符号化部１３１乃至１３４も同じ回路設計である。この結果、それぞれを別々に設計することがないので、設計コストを低減させることが可能となる。
【００１７】
上記の如く、前置予測部１２１乃至１２４、及び、可変長符号化部１３１乃至１３４は同一回路設計であるので、以下では、符号化処理部１７１内の前置予測部１２１、可変長符号化部１３１について説明する。
【００１８】
スキャン変換部１１１から出力される１つの画素を着目画素としたとき、その直前に入力した画素を前置画素という。前置予測部１２１は、この前置画素の値を、着目画素の予測値として決定し、着目画素と予測値との差を算出し、その差を予測誤差として可変長符号化部１３１に出力する。そして、前置予測部１２１は、この処理を、各色成分毎に行なう。実施形態では、１画素３成分の例であるので、前記予測部１２１が出力する予測誤差は６４×３個となる。なお、スキャン変換部１１１から出力された画素が、並べ替え後の先頭の画素の場合、それ以前の画素は存在しない。この場合には、着目画素（先頭画素）の各成分の予測値は“０”とみなし、予測誤差を算出し、可変長符号化部１３１に出力するものとする。ただし、この予測値“０”は、復号装置と同じとすれば良いので、必ずしも“０”である必要はない。或いは、先頭画素だけ予測誤差ではなく生データを送るようにしても良い。
【００１９】
可変長符号化部１３１は、前記予測部１２１からの予測誤差を、予測誤差符号化（エントロピー符号化）し、その符号化データをセレクタ１４１に出力する。
【００２０】
上記と同様の処理を符号化処理部１７２乃至１７３も行なうことになる。
【００２１】
符号量検知部１５１は、符号化処理部１７１乃至１７４から出力される符号化データを監視し、それぞれから出力される１ブロック分の符号化データのデータ量を検出し、その結果を符号量比較部１６１に出力する。
【００２２】
ここで、符号量検知部１５１が検出した符号化処理部１７１乃至１７４から出力される符号化データのデータ量（ビット数）をＣ１、Ｃ２、Ｃ３、Ｃ４と表わすこととする。また、１ブロックの非符号化データ（ラスタースキャン順に並んだ画素データとする）のデータ量をＣ０とする。実施形態では、１ブロックの画素数は８×８個、１画素が３成分、且つ、１成分は８ビットとしているので、データ量Ｃ０は「１５３６（＝８×８×３×８）」ビットとなる。
【００２３】
符号量比較部１６１は、符号化データ量｛Ｃ０、Ｃ１、Ｃ２、Ｃ３、Ｃ４｝を互いに比較し、その中の最小値を求め、最小値が｛Ｃ０、Ｃ１、Ｃ２、Ｃ３、Ｃ４｝中のいずれであるかを示す制御信号をセレクタ１４１に出力する。５つの候補の中から１つを特定することになるので、この制御信号は３ビットあれば十分である。なお、最小符号化データ量となった候補が複数存在する場合も有り得る。この場合には、符号量比較部１６１は、予め設定された優先順に従って１つを選択する制御信号を出力するものとする。
【００２４】
セレクタ１４１は、先ず、符号量比較部１６１からの制御信号に従ってブロックヘッダを生成し、出力する。そして、セレクタ１４１は、符号量比較部１６１からの制御信号で特定される、入力した５つのデータ中の最小データ量のデータを注目ブロックの符号データとして選択し、出力する。ブロックヘッダには、当然、どの経路で生成された符号化データが最小であったのかを示す情報を格納することになる（簡単には、符号量比較部１６１からの制御信号をそのままヘッダに格納すればよい）。
【００２５】
次に図３を用いて具体的な処理を説明する。
【００２６】
図３（ａ），（ｂ）は白・黒のデータが交互に市松模様状に入力されたブロックを示している。
【００２７】
このような画像を、通常のラスタスキャン、あるいは図３（ａ）のルート３０１に従って水平ジグザグスキャンして画素データの並べ替えを行ない、それを前値予測を行うと、予測誤差は非常に大きくなる。先に説明したように、一般に、予測誤差が小さい程、短い符号語を生成するものであるから、これでは、符号化効率が悪い。
【００２８】
一方、図３（ｂ）のルート３０２に示すような斜めジグザグスキャンにて前値予測を行うと、予測誤差が“０”の箇所が多く出現し、符号化効率は大幅に向上する。
【００２９】
また、可変長符号化部１３１（１３２乃至１３４も同様）を、予測誤差のデータ列をランレング符号化する処理部で構成しても構わない。この場合、その予測誤差の絶対値差分が予め設定した許容値以下の時に差分を０と見なし、その許容値を超える場合には、そこから新たなランが始まるものとして、ランレングス符号化すると、更に符号化効率は向上させることができる。この許容値はユーザが適宜、例えば、操作部より設定できるようにしても良い。許容値が０の場合には、可逆符号化データとなり、許容値が１以上の場合には非可逆符号化データとなる。あるいは、予測誤差を線形量子化または非線形量子化することによっても符号量の削減が可能である。
【００３０】
以上の如く、各符号化処理部１７１乃至１７４は、それぞれが異なるスキャンルートに従って、入力した１ブロック分の画素データを並べ替えを行ない、前置予測、及び、可変長符号化を行なう。そしてセレクタ１４１は、オリジナルのブロックのラスタースキャンのデータを含む、各符号化処理部で生成された符号化データ中の、最小となる符号化データを、着目ブロックの符号化データとして出力する。この処理を符号化対象の画像データの全域に対して行なうことで、圧縮効率の高い符号化データを生成することが可能になる。また、これら実施形態では、前置予測部１２１乃至１２４として同じ回路設計を用い、尚且つ、可変長符号化部１３１乃至１３４として同じ回路を用いるようにする。これにより、装置の開発コストを大幅に低減できる。
【００３１】
また、図１と同様の処理をコンピュータプログラムによって実現しても構わない。この場合、各処理部に相当する機能は、コンピュータプログラム上の関数、サブルーチン、プロシージャで実現するわけであるが、前置予測部、可変長符号化部は共通にできるので、プログラムサイズも小さなものとすることができる。
【００３２】
＜第２の実施形態＞
図４は、第２の実施形態における画像符号化装置のブロック構成図である。
【００３３】
本第２の実施形態における画像符号化装置は、装置全体の制御を司る制御部４５０、ブロック化部４０１、抽出色決定部４０２、第１の符号化部４０３、多重化部４０５、置換部４０６、第２の符号化部４０７で構成される。なお、各処理部における処理に要する時間は、互いに異なるので、各処理部の前段には互いに同期するためのバッファメモリが設けられているものとして説明する。以下、同図の構成における処理内容を説明する。
【００３４】
ブロック化部４０１は、符号化対象の多値画像データから、複数画素で構成されるブロック（ｎ×ｍ画素）単位に入力し、後段に出力する。本第２の実施形態でも、符号化対象の画像データの各画素は、Ｒ、Ｇ、Ｂの成分で構成され、各成分は８ビット（２５６階調）とする。また、１ブロックは８×８画素のサイズとする。ブロック化部４０１は、８×８画素をラスタースキャン順に、画素データ（Ｒ成分、Ｇ成分、Ｂ成分）を出力する。ただし、色成分の種類はＲＧＢに限らず、ＹＭＣでも良いし、成分の数、ビット数もこれに限定されるものではない。
【００３５】
抽出色決定部４０２は、入力したブロックの画像データ中の８×８（＝６４）の画素データに、高周波成分となる画素があるか否かを判定し、その画素の色を抽出部に属する抽出色として抽出し、出力する。また、抽出色決定部４０２は、各画素位置毎に、抽出色を持つ画素であるか、非抽出色（背景部に属する）の画素であるかを識別するための２値データを出力する。この２値データが“１”の場合、該当する画素は抽出色を持つ画素であるものとし、“０”の場合には該当する画素は非抽出色の画素とする。実施形態では、１つのブロックは８×８個の画素で構成されるわけであるから、抽出色決定部４０２は８×８個の２値データを生成することになる。この２値データは、抽出色／非抽出色それぞれの画素位置の判定に用いられるので、これ以降、位置情報と呼ぶ。
【００３６】
抽出色決定部４０２における抽出色、位置情報を求めるアルゴリズムの一例を示すのであれば次の通りである。
【００３７】
先ず、ブロック内の画素の輝度の平均値を算出する。そして、その平均値よりも大きな輝度値を持つ画素群（以下、第１の画素群という）と、その平均値以下の画素群（以下、第２の画素群という）とに分類する。更に、第１の画素群の平均値（第１の平均値）と第２の画素群の平均値（第２の平均値）を求め、それらの差の絶対値が、予め設定された閾値を超えるか否かを判定する。
【００３８】
第１、第２の平均値の差の絶対値が、上記の閾値を超えている場合、抽出色決定部４０２は、抽出色有りを示す抽出色有無情報を多重化部４０５に通知する。そして、第２の画素群を、抽出色を持つ画素として見なし、その色情報を抽出色情報として多重化部４０５に出力する。また、抽出色を持つ画素の位置では“１”、非抽出色の画素の位置では“０”とする位置情報を第１の符号化部４０３、置換部４０６に出力する。なお、位置情報はラスタースキャン順に出力するものとする。
【００３９】
一方、第１、第２の平均値の差の絶対値が、上記の閾値以下の場合、抽出色決定部４０２は、抽出色無しを示す抽出色有無情報を多重化部４０５に通知する。また、抽出色決定部４０２は全てが“０”の位置情報を出力する。また、抽出色決定部４０２は、抽出色情報は出力してもしなくても構わない。多重化部４０５は、抽出色無しを示す抽出色有無情報を受信した場合、抽出色決定部４０２からの抽出色情報は無視するからである。
【００４０】
以上、抽出色決定部４０２における処理内容を説明したが、これは一例である点に注意されたい。詳細は後述する説明から明らかになるが、抽出色決定部４０２は、着目ブロック内の高周波成分を抽出するようにすればよい。
【００４１】
第１の符号化部４０３は、抽出色決定部４０２から出力された６４ビットの位置情報を符号化し、その符号化データを多重化部４０５に出力する。この第１の符号化部４０３の詳細は後述する。
【００４２】
次に、置換部４０６について説明する。置換部４０６内の置換色算出部４０９は、位置情報が“０”の画素（非抽出色の画素）の各成分の平均値を算出し、その算出した色を置換色データ（置換情報）としてセレクタ４１０に出力する。具体的には、着目ブロックの座標（ｘ，ｙ）（ｘ、ｙ＝０、１、…、７）の位置にある色成分の値をＰ（ｘ，ｙ）、位置情報をＩ（ｘ，ｙ）（＝０、又は１のいずれか）、位置情報が“０”の個数をＮとしたとき、平均値Aveは次式の通りである。
Ａｖｅ＝ΣΣＰ（ｉ，ｊ）×（１−Ｉ（ｉ，ｊ））／Ｎ
ここで、ΣΣは、変数ｉ，ｊの取り得る範囲（０乃至７）での合算関数である。
そして、置換色算出部４０９は、算出したＡｖｅを置換色データとしてセレクタ４１０に出力する。なお、着目ブロック内に、位置情報が“０”となる個数が０の場合、つまり、Ｎ＝０となる場合には上記算出は行なわず、適当な値を出力して構わない。理由は、Ｎ＝０の場合、セレクタ４１０は、ブロック化部４０１からの６４個の画素データを選択し、出力するからである。
【００４３】
セレクタ４１０は、位置情報が“１”の場合、置換色算出部４０９から出力された置換色情報Ａｖｅを選択出力し、位置情報が“０”の場合にはブロック化部４０１からの画素データを選択出力する。このようにして置換後のブロックの階調データは、多重化部４０５に供給される。
【００４４】
一般に、空間周波数の高い画像は視覚特性における感度が低く、階調性は低くてよい。一方、空間周波数の低い領域では相対感度が高く、階調性が重要となる。別な言い方をすれば、文字線画は画像のエッジが鮮明な画像であり、空間周波数が高いことが望まれ、自然画の場合には空間周波数が低くて良く、高い階調性があることが望まれる。
【００４５】
実施形態における置換部４０６は、要するに、抽出色と判定された画素の各成分の値を、非抽出色の画素の平均値で置換して、第２の符号化部４０７に出力する。この結果、置換部４０６から出力される８×８画素のブロックの画像は、空間周波数の低い階調画像に変換されることになる。
【００４６】
第２の符号化部４０７は、例えば、ＪＰＥＧ符号化部（ＤＣＴ変換、量子化、エントロピー符号化）であり、置換部４０６から出力された８×８画素の階調画像データを符号化し、符号化データを多重化部４０５に出力する。
【００４７】
多重化部１０５は、抽出色決定部４０２からの抽出色有無情報に基づき、抽出色情報、第１の符号化部４０３からの符号化データ、第２の符号化部４０７からの符号化データを選択／多重化し、ブロック単位の符号化データを出力する。多重化部１０５が出力する符号化データは次の通りである。
・抽出色有無情報が抽出色無しを示している場合；
抽出色無しを示す識別情報を含むブロックヘッダ＋第２の符号化部４０７からの符号化データ
・抽出色有無情報が抽出色有りを示している場合；
抽出色有りを示す識別情報を含むブロックヘッダ＋抽出色情報＋第１の符号化部からの符号化データ＋第２の符号化部４０７からの符号化データ
【００４８】
次に、実施形態における第１の符号化部４０３の詳細を説明する。図５は、第１の符号化部４０３のブロック構成図である。第１の実施形態で示した図１と同様の構成であるので、同参照番号を付した。
【００４９】
図示の如く、本第２の実施形態では、セレクタ１４１、符号量検出部１５１、符号量比較部１６１、４つの符号化処理部１７１乃至１７４で構成される。
【００５０】
符号化処理部１７１は、スキャン変換部１１１、前置予測部１２１及び可変長符号化部１３１を有する。また、この可変長符号化部１３１は、位置情報（２値データ）のラン長を検出するラン長検出部１３１１を有する。また、この可変長符号化部１３１は、０ラン長を入力しハフマン符号化データを出力するハフマンテーブル１３１２、１ラン長を入力しハフマン符号化データを出力するハフマンテーブル１３１３を有する。また、可変長符号化部１３１は、０ランの符号化データ、１ランの符号化データを交互に選択し、出力するセレクタ１３１４を有する。
【００５１】
また、符号化処理部１７２は、スキャン変換部１１２、前置予測部１２２及び可変長符号化部１３２を有する。符号化処理部１７３は、スキャン変換部１１３、前置予測部１２３及び可変長符号化部１３３を有する。そして、符号化処理部１７４は、スキャン変換部１１４、前置予測部１２４及び可変長符号化部１３４を有する。
【００５２】
なお、実施形態では、符号化処理部は４つで構成される例を説明するが、本発明がこの数に限定されるものではない。要は、複数の符号化処理部を備えれば良い。また、符号化処理部１７２乃至１７４は、それぞれが異なるルートに従って位置情報を並べ替えるスキャン変換部を備える点を除き、符号化処理部１７１と同じである。それ故、以下では、符号化処理部１７１の処理内容を説明する。
【００５３】
スキャン変換部１１１は、抽出色決定部４０２からの位置情報（６４ビット）を図２（ａ）のルートに従ってスキャンし、位置情報の並べ替えを行ない、前置予測部１２１に出力する。
【００５４】
スキャン変換部１１１から出力される１つの位置情報を着目位置情報としたとき、その直前に入力した位置情報を前置位置情報という。前置予測部１２１は、この前置位置情報と着目位置情報とが一致しているか否かを判定し、一致している場合に“０”、不一致の場合に“１”の２値情報を出力する。なお、スキャン変換部１１１から出力された位置情報が、並べ替え後の先頭の位置情報の場合、それ以前の位置情報は存在しない。この場合には、着目位置情報に対する前置位置情報は“０”とみなす。
【００５５】
ラン長検出部１３１１は、前置予測部１２１から出力される２値情報が“０”ラン→“１”ラン→“０”ラン…と、０、１のランを交互に検出し、その結果を、ハフマンテーブル１３１２、１３１３の一方に交互に出力する。なお、ラン長検出部１３１１は、最後（６４個目）の一致／不一致情報を入力した場合には、ランが継続していても、それまでに検出したランを出力する。
【００５６】
セレクタ１３１４は、ハフマンテーブル１３１２、１３１３から、交互に出力される符号化データを選択し、出力する。
【００５７】
以上、符号化処理部１７１について説明した。他の符号化処理部１７２乃至１７４も、同様の処理を行なう。これら符号化処理部１７１乃至１７４の違いは、それぞれのスキャン変換部１１１乃至１１４におけるスキャンルートが異なる点である。
【００５８】
一般に、画像においては局所的な相関性があるため、上記０のランと１のランでは確率分布が異なる。図６（ａ），（ｂ）は上記確率分布の様子を模式化したものである。同図に示すように、０ランの確率分布は中間のラン長にピークがあり、１のランの確率分布はラン長１をピークにラン長が増加するに従って出現確率が下がって行く。従って、上記可変長符号化における符号化系列を０のランと１のランとで変えた方が符号化効率は向上する。このため、実施形態では、０ランと１ランとを異なるハフマンテーブルを用いた。
【００５９】
符号量検知部１５１は、符号化処理部１７１乃至１７４から出力される符号化データを監視し、それぞれから出力される１ブロック分の位置情報の符号化データのデータ量を検出し、その結果を符号量比較部１６１に出力する。
【００６０】
ここで、符号量検知部１５１が検出した符号化処理部１７１乃至１７４から出力される符号化データのデータ量（ビット数）をＣ１、Ｃ２、Ｃ３、Ｃ４と表わすこととする。また、１ブロックの非符号化データ（ラスタースキャン順に並んだ位置情報）のデータ量をＣ０とする。本第２の実施形態では、１ブロックの全位置情報は６４ビットであるので、Ｃ０＝６４となる。
【００６１】
符号量比較部１６１は、符号化データ量｛Ｃ０、Ｃ１、Ｃ２、Ｃ３、Ｃ４｝を互いに比較し、その中の最小値を求め、最小値が｛Ｃ０、Ｃ１、Ｃ２、Ｃ３、Ｃ４｝中のいずれであるかを示す制御信号をセレクタ１４１に出力する。５つの候補の中から１つを特定することになるので、この制御信号は３ビットあれば十分である。なお、最小符号化データ量となった候補が複数存在する場合も有り得る。この場合には、符号量比較部１６１は、予め設定された優先順に従って１つを選択する制御信号を出力するものとする。
【００６２】
セレクタ１４１は、先ず、符号量比較部１６１からの制御信号に従って、位置情報の符号化データの先頭に、どの経路で生成された符号化データが最小であったのかを示す情報を格納する。そして、セレクタ１４１は、それに後続して、符号量比較部１６１からの制御信号で特定される、入力した５つのデータ中の最小データ量のデータを注目ブロックの位置情報の符号データとして選択し、出力する。
【００６３】
＜他の実施形態＞
以上、本発明に係る実施形態を説明したが、上記の第１、第２の実施形態と機能をコンピュータプログラムでもって実現しても構わない。この場合、図１又は図４（及び図５）の各処理部に相当する部分は、コンピュータプログラムの関数、サブルーチンによって実現できる。また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータがアクセスする装置にセットして、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も本発明の範疇に入ることも明らかである。
【図面の簡単な説明】
【００６４】
【図１】第１の実施形態に係る画像符号化装置のブロック構成図である。
【図２】第１の実施形態における各スキャン変換部によるスキャンルートを示す図である。
【図３】第１の実施形態におけるスキャンルートによって符号化効率が異なる画像の例を示す図である。
【図４】第２の実施形態における画像符号化装置のブロック構成図である。
【図５】図４における第１の符号化部の詳細を示すブロック構成図である。
【図６】０ランと１ラインをラン長に対する発生確率分布を示す図である。
【図１】
2009005016.tif 000003
【図２】
2009005016.tif 000004
【図３】
2009005016.tif 000005
【図４】
2009005016.tif 000006
【図５】
2009005016.tif 000007
【図６】
2009005016.tif 000008