(57)【要約】【課題】  本発明は、ブロック内に出現する画素値を抽出し、その抽出した画素値を持つ画素位置か否かを示す識別情報を符号化する技術を基礎にしつつも、更に効率良く符号化する技術を提供する。【解決手段】  ブロック化部はＭ個の画素で構成されるブロック単位の画像データを入力する。抽出部は、入力した着目ブロック内を解析し、その中に出現する画素値を抽出すると共に、各抽出画素値毎に、その画素値を持つ画素位置か否かを示す識別データで構成される識別情報を生成する。データ削減部は、生成された識別情報における識別データを削減する。符号化部１０４は、削減後の各識別情報を符号化する。パック部１０５は、抽出画素値と符号化識別情報とをパックし、着目ブロックの符号化データとして出力する。【選択図】  図１
2013255075.tif 000002
【特許請求の範囲】
【請求項１】
画像データを符号化し、符号化データを生成する画像符号化装置であって、
画像データを、Ｍ個の画素で構成されるブロック単位に入力するブロック化手段と、
該ブロック化手段で入力した着目ブロック内を解析し、当該着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を抽出すると共に、
判定した１つの画素値Ｐi（ｉは1,2,…,ｎのいずれか)について、前記着目ブロック内の各画素位置毎に、前記画素値Ｐiを持つ画素か否かを識別するための識別データを割り当て、Ｍ個の前記識別データで構成される識別情報Ｔiを生成する抽出手段と、
該抽出手段で生成された識別情報Ｔ1,Ｔ2,…における識別データを削減し、削減後の識別情報Ｔ1',Ｔ2'，…を出力するデータ削減手段と、
該データ削減手段による削減後の各識別情報Ｔ1',Ｔ2',…を符号化し、それぞれの符号化識別情報Ｃ1,Ｃ2,…を生成する符号化手段と、
前記画素値Ｐ1,Ｐ2,…,Ｐnと、前記符号化手段で得られた符号化識別情報Ｃ1,Ｃ2,…とをパックし、前記着目ブロックの符号化データとして出力するパック手段とを有し、
前記データ削減手段は、
識別情報Ｔiの削減処理の際には、当該識別情報Ｔiを構成するＭ個の識別データの中で、それ以前の識別情報Ｔ1乃至Ｔi-1の削減処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置の識別データを削除し、画素値Ｐ1乃至Ｐi-1のいずれの画素値でもない画素位置の識別データを残すことで、削減後の識別情報Ｔi'を出力することを特徴とする画像符号化装置。
【請求項２】
前記符号化手段は、識別情報Ｔ1',Ｔ2',…,Ｔn-1'それぞれを符号化して符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1を生成し、
前記パック手段は、前記画素値Ｐ1,Ｐ2,…,Ｐnと、前記符号化手段で得られた符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1をパックし、前記着目ブロックの符号化データとして出力する
ことを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記識別データは“０”、“１”の２値データであって、
前記データ削減手段は、
前記着目ブロックの符号化に先き立ってゼロクリアされる、Ｍ個の削減箇所データを格納するためのバッファメモリと、
前記バッファメモリから順番に削減箇所データを読み出し、当該読み出した削減箇所データが“０”の場合には、前記識別情報Ｔiにおける該当する識別データを出力し、前記バッファメモリから読み出した削減箇所データが“１”の場合には、前記識別情報Ｔiにおける該当する識別データを削除する削除手段と、
前記読み出した削減箇所データと前記削除手段が出力した識別データとの論理和を行ない、当該論理和の結果で、前記バッファメモリの中の前記読み出した削減箇所データを更新する更新手段とを有する
ことを特徴とする請求項１に記載の画像符号化装置。
【請求項４】
前記抽出手段は、前記着目ブロック内に出現する出現頻度の高い画素値の順に前記画素値Ｐ1,Ｐ2,…,Ｐnと判定することを特徴とする請求項１乃至３のいずれか１項に記載の画像符号化装置。
【請求項５】
出現する画素値の差が予め設定された閾値より小さい２つの画素値を、１つの画素値に変換すると共に、それぞれの識別情報を論理和して１つの識別情報を生成する変換手段を更に有することを特徴とする請求項１乃至４のいずれか１項に記載の画像符号化装置。
【請求項６】
前記変換手段は、前記２つの画素値それぞれの出現頻度の割合の比に応じて、前記２つの画素値の間の１つの画素値を変換後の画素値として決定することを特徴とする請求項５に記載の画像符号化装置。
【請求項７】
前記符号化手段は、前記識別情報を構成するＭ個の識別データがリング状になっているものとして最大ランを探し出し、当該最大ランの直後の位置の識別データを先頭にして、ランレングス符号化し、前記最大ランの直後の位置を示す情報とランレングス符号化データとを出力することを特徴とする請求項１乃至６のいずれか１項に記載の画像符号化装置。
【請求項８】
前記抽出手段は、
前記着目ブロック内にて、画素値Ｐiを持つ画素か否かを識別するための識別データを割り当てるためのスキャン方向が互いに異なる複数の識別情報生成手段と、
前記複数の識別情報生成手段で生成された各識別情報の中で、もっとも大きいランを持つ１つを、前記着目ブロックの画素値Ｐiのための識別情報Ｔiとして選択し、出力する選択手段とを有する
ことを特徴とする請求項１乃至７のいずれか１項に記載の画像符号化装置。
【請求項９】
前記パック手段は、
ブロックヘッダと、パック対象の前記画素値Ｐ1,Ｐ2,…,Ｐnと、前記符号化手段で得られた符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1で表わされるパック対象のデータ量が、予め設定された固定長Ｌを超える場合、前記固定長Ｌ以下になるまで、前記パック対象から、最後の画素値と最後の符号化識別情報の組を順に破棄して、前記固定長となるようにパックすることを特徴とする請求項１乃至８のいずれか１項に記載の画像符号化装置。
【請求項１０】
画像データを符号化し、符号化データを生成する画像符号化装置の制御方法であって、
ブロック化手段が、画像データを、Ｍ個の画素で構成されるブロック単位に入力するブロック化工程と、
抽出手段が、
該ブロック化工程で入力した着目ブロック内を解析し、当該着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を抽出すると共に、
判定した１つの画素値Ｐi（ｉは1,2,…,ｎのいずれか)について、前記着目ブロック内の各画素位置毎に、前記画素値Ｐiを持つ画素か否かを識別するための識別データを割り当て、Ｍ個の前記識別データで構成される識別情報Ｔiを生成する抽出工程と、
データ削減手段が、該抽出工程で生成された識別情報Ｔ1,Ｔ2,…における識別データを削減し、削減後の識別情報Ｔ1',Ｔ2'，…を出力するデータ削減工程と、
符号化手段が、該データ削減工程による削減後の各識別情報Ｔ1',Ｔ2',…を符号化し、それぞれの符号化識別情報Ｃ1,Ｃ2,…を生成する符号化工程と、
パック手段が、前記画素値Ｐ1,Ｐ2,…,Ｐnと、前記符号化手段で得られた符号化識別情報Ｃ1,Ｃ2,…とをパックし、前記着目ブロックの符号化データとして出力するパック工程とを有し、
前記データ削減工程では、
識別情報Ｔiの削減処理の際には、当該識別情報Ｔiを構成するＭ個の識別データの中で、それ以前の識別情報Ｔ1乃至Ｔi-1の削減処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置の識別データを削除し、画素値Ｐ1乃至Ｐi-1のいずれの画素値でもない画素位置の識別データを残すことで、削減後の識別情報Ｔi'を出力する
ことを特徴とする画像符号化装置の制御方法。
【請求項１１】
コンピュータに読み込ませ実行させることで、前記コンピュータに、請求項１０に記載の各工程を実行させるためのプログラム。
【請求項１２】
符号化画像データを復号する画像復号装置であって、
Ｍ個の画素で構成されるブロックの符号化データを入力する入力手段と、
該入力手段で入力した着目ブロックの符号化データを解析し、当該符号化データから前記着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を取得すると共に、前記着目ブロック内の各画素位置が画素値Ｐi（ｉは1,2,…)であるか否かを表わす識別データで構成される識別情報Ｔi'の符号化識別情報Ｃiを取得する解析手段と、
該解析手段で得られた各符号化識別情報Ｃ1, Ｃ2, …を復号し、識別情報Ｔ1',Ｔ2',…を生成する復号手段と、
該復号手段で得られた識別情報Ｔ1',Ｔ2',…における削減された識別データを復元し、復元後の識別情報Ｔ1, Ｔ2, …を生成する復元手段と、
前記画素値Ｐiと復元された識別情報Ｔiを用いて、画素値Ｐiを持つと判定された画素位置に画素値Ｐiを割り当てることで、前記着目ブロックの内の各画素値を決定し、前記着目ブロックの画像データとして出力する出力手段とを有し、
前記復元手段は、
識別情報Ｔi'の削減処理の際には、それ以前の識別情報Ｔ1'乃至Ｔi-1'の復元処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置については画素値Ｐiではないことを示す識別データを新規に生成し、前記画素値Ｐ1乃至Ｐi-1のいずれでもない画素位置については前記識別情報Ｔi'における識別データを出力することで、Ｍ個の識別データで構成される識別情報Ｔiを生成する
ことを特徴とする画像復号装置。
【請求項１３】
前記復号手段は、符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1それぞれを復号して、識別情報Ｔ1',Ｔ2',…,Ｔn-1'を生成し、
前記出力手段は、前記画素値Ｐ1,Ｐ2,…,Ｐn-1と、前記復元手段で得られた識別情報Ｔ1乃至Ｔn-1に基づき、前記着目ブロック内の画素値Ｐ1,Ｐ2,…,Ｐn-1を持つ画素位置にそれぞれの画素値を割り当て、未割り当ての画素位置に前記Ｐnの画素値を割り当てることを特徴とする請求項１２に記載の画像復号装置。
【請求項１４】
符号化画像データを復号する画像復号装置の制御方法であって、
入力手段が、Ｍ個の画素で構成されるブロックの符号化データを入力する入力工程と、
解析手段が、該入力工程で入力した着目ブロックの符号化データを解析し、当該符号化データから前記着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を取得すると共に、前記着目ブロック内の各画素位置が画素値Ｐi（ｉは1,2,…)であるか否かを表わす識別データで構成される識別情報Ｔi'の符号化識別情報Ｃiを取得する解析工程と、
復号手段が、該解析工程で得られた各符号化識別情報Ｃ1, Ｃ2, …を復号し、識別情報Ｔ1',Ｔ2',…を生成する復号工程と、
復元手段が、該復号工程で得られた識別情報Ｔ1',Ｔ2',…における削減された識別データを復元し、復元後の識別情報Ｔ1, Ｔ2, …を生成する復元工程と、
出力手段が、前記画素値Ｐiと復元された識別情報Ｔiを用いて、画素値Ｐiを持つと判定された画素位置に画素値Ｐiを割り当てることで、前記着目ブロックの内の各画素値を決定し、前記着目ブロックの画像データとして出力する出力工程とを有し、
前記復元工程では、
識別情報Ｔi'の削減処理の際には、それ以前の識別情報Ｔ1'乃至Ｔi-1'の復元処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置については画素値Ｐiではないことを示す識別データを新規に生成し、前記画素値Ｐ1乃至Ｐi-1のいずれでもない画素位置については前記識別情報Ｔi'における識別データを出力することで、Ｍ個の識別データで構成される識別情報Ｔiを生成する
ことを特徴とする画像復号装置の制御方法。
【請求項１５】
コンピュータに読み込ませ実行させることで、前記コンピュータに、請求項１４に記載の各工程を実行させるためのプログラム。
【請求項１６】
請求項１１又は１５に記載のプログラムを格納したことを特徴とするコンピュータが読み込み可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の符号化、復号化技術に関するものである。
【背景技術】
【０００２】
従来、画像を圧縮する手法の１つとして、ブロック符号化が知られている。ＪＰＥＧなどのブロック符号化では、ブロック毎の符号量が可変長である。従って、或るブロックの画像のみを編集するためには、先頭のブロックから順番に復号しなければならない。これに対して、特許文献１には、ブロック単位に符号量を固定長にする符号化技術が開示されている。固定長であるため、目的とするブロックの位置が判明すれば、その符号化データの格納位置が演算で特定でき、目的とするブロックのみを復号することが可能である。
【０００３】
特許文献１に記載された符号化技術は、ブロック内の画像を文字や線画等のエッジの鮮明さが重要な部分と、自然画などの階調性が重要な部分に分離し、それぞれ別の符号化方式で圧縮している。例えば、文字や線画の符号化においては、２値のブロックデータの符号化として、ランレングス符号化とハフマン符号化を組み合わせて適用している。また、自然画の符号化においては、多値のブロックデータの符号化として、ＪＰＥＧの符号化を適用している。そして、これら得られた符号化データを定められたフォーマットに従って、１ブロック分の固定長符号化データを生成している。
【０００４】
この手法で使用しているＪＰＥＧ符号化は非可逆圧縮であるため、画像データによっては非可逆圧縮したことによる影響で画質が劣化する場合がある。
【０００５】
そこで、本願発明者等は、画質の劣化を防ぐために可逆圧縮を使う手法として、以下の符号化技術を考察した。
【０００６】
先ず、ブロック内の画像データに出現する画素値を抽出し、抽出画素値を持つ画素位置と持たない画素位置とを区別する識別情報を、各抽出画素毎に生成する。例えばブロック内に出現する画素値が４種類あれば、識別情報も４種類得る。次に、画素値毎の識別情報を圧縮する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−２７８０４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記技術に従えば、生成される識別情報の個数は、出現する画素値の種類に依存する。従って、出現する色数が多い画像の場合には、その色数に依存したデータ量となることが容易に推察される。
【０００９】
本発明はかかる問題に鑑みなされたものであり、ブロック内に出現する画素値を抽出し、その抽出した画素値を持つ画素位置か否かを示す識別情報を符号化する技術を基礎にしつつも、更に効率良く符号化する技術を提供しようとするものである。
【課題を解決するための手段】
【００１０】
この課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像データを符号化し、符号化データを生成する画像符号化装置であって、
画像データを、Ｍ個の画素で構成されるブロック単位に入力するブロック化手段と、
該ブロック化手段で入力した着目ブロック内を解析し、当該着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を抽出すると共に、
判定した１つの画素値Ｐi（ｉは1,2,…,ｎのいずれか)について、前記着目ブロック内の各画素位置毎に、前記画素値Ｐiを持つ画素か否かを識別するための識別データを割り当て、Ｍ個の前記識別データで構成される識別情報Ｔiを生成する抽出手段と、
該抽出手段で生成された識別情報Ｔ1,Ｔ2,…における識別データを削減し、削減後の識別情報Ｔ1',Ｔ2'，…を出力するデータ削減手段と、
該データ削減手段による削減後の各識別情報Ｔ1',Ｔ2',…を符号化し、それぞれの符号化識別情報Ｃ1,Ｃ2,…を生成する符号化手段と、
前記画素値Ｐ1,Ｐ2,…,Ｐnと、前記符号化手段で得られた符号化識別情報Ｃ1,Ｃ2,…とをパックし、前記着目ブロックの符号化データとして出力するパック手段とを有し、
前記データ削減手段は、
識別情報Ｔiの削減処理の際には、当該識別情報Ｔiを構成するＭ個の識別データの中で、それ以前の識別情報Ｔ1乃至Ｔi-1の削減処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置の識別データを削除し、画素値Ｐ1乃至Ｐi-1のいずれの画素値でもない画素位置の識別データを残すことで、削減後の識別情報Ｔi'を出力することを特徴とする。
【発明の効果】
【００１１】
本発明によれば、ブロック内に出現する画素値を抽出し、その抽出した画素値を持つ画素位置か否かを示す識別情報を符号化する技術を基礎にしつつも、更に効率良く符号化することが可能になる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施形態における画像符号化装置のブロック図。
【図２】第１の実施形態における画像符号化装置の抽出部のブロック図。
【図３】第１の実施形態における入力ブロックデータの例を示す図。
【図４】第１の実施形態における抽出部が処理するデータの例を示す図。
【図５】第１の実施形態におけるデータ削減部のブロック図。
【図６】第１の実施形態におけるデータ削減部が処理するデータの例を示す図。
【図７】第１の実施形態における固定長符号化データのファイルの構造を示す図。
【図８】第１の実施形態における画像復号化装置のブロック図。
【図９】第１の実施形態におけるデータ復元部のブロック図。
【図１０】第１の実施形態におけるデータ復元部が処理するデータの例を示す図。
【図１１】第２の実施形態における画像復号化装置のブロック図。
【図１２】第３の実施形態における画像符号化装置のブロック図。
【図１３】第３の実施形態における出力順序制御部のブロック図。
【図１４】第３の実施形態における入力ブロックデータの例を示す図。
【図１５】第３の実施形態における画像符号化装置が処理するデータを示す図。
【図１６】第３の実施形態における画像符号化装置が処理するデータを示す図。
【図１７】第４の実施形態における画像符号化装置のブロック図。
【図１８】第４の実施形態における画像符号化装置が処理するデータを示す図。
【図１９】第５の実施形態における画像符号化装置のブロック図。
【図２０】第５の実施形態における開始位置制御部のブロック図。
【図２１】第５の実施形態における画像符号化装置が処理するデータを示す図。
【図２２】第５の実施形態における画像復号化装置のブロック図。
【図２３】第６の実施形態における画像符号化装置のブロック図。
【図２４】第６の実施形態における比較部のブロック図。
【図２５】第６の実施形態における画像符号化装置が処理するデータを示す図。
【図２６】第６の実施形態における画像符号化装置が処理するデータを示す図。
【図２７】第６の実施形態における画像復号化装置のブロック図。
【発明を実施するための形態】
【００１３】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。  
［第１の実施形態］
実施形態では、説明を簡単なものとするため、符号化対象の画像データは濃度成分のみで、１画素当たり８ビットのモノクログレースケールの画像データとする。そして、この画像データを符号化し、符号化画像データを生成する画像符号化装置を例に説明する。画素値が示すのは濃度値であるので、値が大きいほど黒く、逆に値が小さいほど白くなることを示す。なお、符号化対象の画像をモノクログレースケールで、１画素が８ビットとするのは、説明を単純化するためであり、複数の色成分で構成されるカラー画像に適用する場合には、各色成分毎に以下の処理を行えば良い。また、１画素のビット数が８ビットに限らず、何ビットでも構わないことも明らかである。
【００１４】
図１に、本発明の第１の実施形態における符号化装置のブロック図を示す。本発明における符号化装置は、ブロック化部１０１、抽出部１０２、データ削減部１０３、符号化部１０４、パック部１０５で構成される。なお、実際には、各処理部内には、タイミングを合わせるための適当な容量のバッファーメモリが搭載されているものであるが、それについては省略して示していることに注意されたい。以下、同図の構成における処理内容を簡単に説明する。
【００１５】
ブロック化部１０１は、入力画像データから、複数画素で構成されるブロック（ｍ×ｎ画素）を切り出して読み込み、それをブロックデータとして、後段の抽出部１０２へ出力する。
【００１６】
抽出部１０２は、入力されたブロックデータ内の画素値を抽出し、パック部１０５へ出力する。また、各画素値のそれぞれのブロック内の位置を示す識別情報を生成し、データ削減部１０３へ出力する。識別情報は、入力されたブロックデータの画素毎に、それが抽出した画素値であるか、そうでないかを識別するための識別データから構成される。１画素につき、抽出した画素値であるかそうでないかの２種類を示せれば良いので、識別データは１画素につき１ビットで良いことになる。実施形態の場合、１ブロックデータ内に含まれる全画素数はｍ×ｎ個であるから、抽出部１０２は、ｍ×ｎ個の識別データ（ｍ×ｎビット）を生成し、データ削減部１０３へ出力する。なお、これ以降、「ｍ×ｎ個の識別データ」を総称して識別情報といい、１画素について言う場合に「識別データ」という。
【００１７】
データ削減部１０３は、入力された識別情報において、ブロック内で既に確定した画素位置がある場合はその画素位置を除き、データを削減した識別情報を出力する。削減したデータは、既に確定した画素位置であるので、後述する復号化装置で算出可能である。
【００１８】
符号化部１０４は、データ削減部１０３から入力された識別情報（ｍ×ｎビット）を可逆符号化して符号化データを生成し、パック部１０５へ出力する。なお、以降、符号化部１０４が出力する符号化データを符号化識別情報という。
【００１９】
パック部１０５は、抽出部１０２から入力された画素値と、符号化部１０４から入力された符号化識別情報を、後述するアルゴリズムに従ってパックし、１ブロックの固定長符号化データとして出力する。
【００２０】
以上が第１の実施形態の符号化装置の大まかな処理である。次に、各構成要素の詳細を説明する。
【００２１】
まず、ブロック化部１０１について、詳細に説明する。ブロック化部１０１は、内部にｎライン分のバッファメモリを有し、符号化対象の画像データをラスタースキャン順に入力し、バッファに格納する。そして、ｎライン分の画像データが入力された後、水平方向ｍ画素、垂直方向ｎ画素の画像データを順に切り出し、それぞれを抽出部１０２に出力することを繰り返す。このｍ×ｎ画素の画像データを、本実施形態例ではブロックデータという。ブロックデータのサイズ（ｍ、ｎ）は特に規定しない。本実施例では、１ブロックデータのサイズを１６×１６画素（ｍ＝ｎ＝１６）として説明する。勿論、このサイズは適宜ユーザが設定しても良い。また、ブロックの形状は正方形である必要はなく、長方形でも可能である。
【００２２】
次に、抽出部１０２について、図２を用いて詳細に説明する。図２は、本実施形態における抽出部１０２の構成を示すブロック図である。画素値検出部２０１は、ブロック化部１０１から入力されたブロックデータ内の画素値を検出し、識別情報生成部２０２へ出力すると共に、パック部１０５へ出力する。識別情報生成部２０２は、ブロック化部１０１から入力されたブロックデータから、画素値毎の識別情報を生成して、データ削減部１０３へ出力する。以下、図２の各構成要素について詳細に説明する。
【００２３】
画素値検出部２０１は、ブロック化部１０１から１６×１６画素のブロックデータが入力されると、ブロックデータ内の各画素をスキャンし、このスキャン中の画素値を検出し出力する。また、ブロックデータ内で検出した画素値の個数を出力する。
【００２４】
識別情報生成部２０２は、ブロック化部１０１から１６×１６画素のブロックデータが入力されると、着目ブロック内をスキャンし、このスキャン中の着目画素が、画素値検出部２０１が検出した画素値である場合には、“１”の識別データを生成する。逆に、検出した画素値でない場合には、“０”の識別データを生成する。そして、１ブロック分の識別データを生成すると、識別情報としてデータ削減部１０３へ出力する。
【００２５】
画素値検出部２０１と識別情報生成部２０２が処理するデータの一例を、図３と図４を用いて具体的に説明する。図３は、ブロック化部１０１から入力された１６×１６画素のブロックデータの例である。図４は、画素値検出部２０１が検出した画素値と、識別情報生成部２０２が画素値毎に生成した識別情報の例である。
【００２６】
画素値検出部２０１は、ブロックデータ内の各画素をスキャンし、ブロックデータ内に出現する画素値“７０”、“６０”、“５０”、“４０”と、画素値の個数“４”を出力する。識別情報生成部２０２は、まず、画素値検出部２０１から画素値“７０”が入力されると、入力ブロックデータをスキャンし、スキャン中の着目画素の画素値が“７０”の場合は“１”の識別データを、“７０”以外の場合は“０”の識別データを生成する。この時にスキャンする方向は、例えば、ブロックデータの左上の画素からスタートしてライン方向に進み、１ラインスキャンすると次のラインのスキャンに進む（所謂、ラスタースキャン）。そして、ブロックデータの右下の画素までスキャンをすると、１ブロックデータのスキャンを完了する。この時の入力ブロックデータは１６×１６であるので、２５６個（ビット）の識別データ“1100000011000000・・・”が生成される。そして生成された２５６個の識別データを、画素値“７０”の識別情報として、出力する。以降、他の画素値に関しても同様にして識別情報を生成し出力する。すなわち、次に画素値“６０”の画素位置では“１”、それ以外では“０”の２５６個の識別データ（識別情報）を生成する。この後、画素値“５０”、画素値“４０”それぞれの識別情報を生成することになる。
【００２７】
次に、データ削減部１０３について、図５を用いて説明する。図５は、本実施形態におけるデータ削減部１０３の構成を示すブロック図である。削減箇所算出部５０１は、ブロック内で既に確定した画素位置、即ち、入力された識別情報のうち他の画素値が存在する位置として符号化済みであり削減可能なビットの位置を算出し、算出した削減箇所データをバッファメモリ５０２へ保存する。なお、以降、１画素毎の削減すべきか否かを示すデータを削減箇所データと呼び、ブロック全体の複数の削減箇所データを削減箇所情報と呼ぶこととする。削減部５０３は、バッファメモリ５０２に保存された削減箇所データを読み取り、削減箇所データに基づいて、入力された識別情報から識別データを削減して出力する。また、削減部５０３は、抽出部１０２から、何個の画素値が抽出されたかを示す情報を入力し、その個数で着目ブロックの削減処理が終了したのかを判定することとした。以下、図５の各構成要素について詳細に説明する。
【００２８】
削減箇所算出部５０１は、ある画素値の識別情報が入力されると、バッファメモリに保存された値を読み取り、入力された識別情報とバッファメモリに保存された値との論理和を計算し、その結果（論理和が“１”が削除対象位置となる）を次の画素値の削減箇所データとしてバッファメモリに保存する。そして、以降、識別情報が入力される毎に前述した動作を繰り返す。なお、最初の画素値の識別情報が入力された時点では、バッファメモリに保存されていない為、バッファメモリから読み取った値は“０”として処理を行う。
【００２９】
削減部５０３は、ある画素値の識別情報が入力されると、バッファメモリ５０２に保存された削減箇所データを読み取り、削減箇所データと、入力された識別情報の値を比較する。そして、入力された識別情報から削減箇所データの“１”に該当するビット位置の識別データを削除し、後段の符号化部１０４へ出力する。削減箇所データの“１”に該当するビット位置は、ブロック内で既に確定した画素位置を示している。なお、バッファーメモリ５０２は、１ブロック分の識別情報の削減処理を開始する際（もしくは１ブロック分の識別情報の削減処理が完了した際）、バッファメモリ５０２をゼロクリアされるものとする。
【００３０】
削減箇所算出部５０１、削減部５０３が処理するデータの一例を、図６を用いて具体的に説明する。図６は、図３に示すブロックデータが入力された際の、画素値、識別情報、削減部５０３がバッファメモリから読み出した削減箇所データ、識別データを削減する削減箇所と、出力する削減後の識別情報の例を示した図である。識別データ削減箇所の下線部は、削減部５０３が削減するビット位置を示している。つまり、このビット位置が既に確定した画素位置を表している。
【００３１】
まず、最初の画素値“７０”の識別情報“1100000011000000・・・”が入力されると、削減部５０３が、バッファメモリから値を読み出す。最初の画素値の識別情報が入力された時点ではバッファメモリには値は保存されていないので、バッファメモリ５０２からは削減箇所情報“0000000000000000・・・”を読み出したとして処理する。削減部５０３は、入力された識別情報から、削減箇所データの“１”に該当するビット位置の識別データを削除して出力する。この時点では、削減箇所データに“１”は含まれていないので、入力された識別情報からビットを削減しないでそのまま出力することになる。すなわち、最初の画素値“７０”の識別情報（２５６ビット）はそのまま出力される。また、削減箇所算出部５０１は、入力された画素値“７０”の識別情報“1100000011000000・・・”と、バッファメモリ５０２の値“0000000000000000・・・”との論理和を計算し、その結果である“1100000011000000・・・”を、次の画素値の削減箇所情報としてバッファメモリ５０２に保存、すなわち、バッファメモリ５０２を更新する。
【００３２】
次に、２つ目の画素値“６０”の識別情報“0011000000110000・・・”が入力されると、削減部５０３が、バッファメモリから削減箇所情報“1100000011000000・・・”を読み出して、入力された識別情報と比較する。比較した結果、入力された識別情報から、削減箇所情報の“１”に該当するビット位置を削除（間引き）して、“110000110000・・・”を出力する。ここで、削除された識別データの個数は、最初の画素値“７０”の識別情報内の“１”の値を持つ識別データの個数となる点に注意されたい。そして、削減箇所算出部５０１は、入力された識別情報“0011000000110000・・・”と、バッファメモリの値“1100000011000000・・・”との論理和を計算し、その結果である“1111000011110000・・・”を、次の画素値の削減箇所情報としてバッファメモリに保存する。
【００３３】
以降、識別情報が入力される毎に同様の動作を繰り返し、削減可能なビット位置を削減した識別情報を出力する。
【００３４】
なお、着目ブロックデータ内で最後に抽出した画素値“４０”の識別情報は、これまでに既に確定した画素位置以外の残りの位置を示す識別情報となるため、後述する復号化装置で復号化可能である。そのため、削減部５０３は、最後の画素値“４０”の識別情報は出力しない。つまり、削減部５０３は、着目ブロックより抽出した画素値がＮ個あった場合、Ｎ−１個の「削除後の識別情報」を出力処理で、着目ブロックに対する識別処理を終えることになる。
【００３５】
このように、データ削減部１０３は、後述する復号化装置で算出して復元可能な識別データ、即ち、ブロック内で既に確定した画素位置を削除し、必要な識別データのみを抽出して識別情報を生成して符号化部へ出力する。このことにより、ブロック内の同じ位置を示す識別情報を何度も符号化しないようにすることができる。よって、後段の符号化部で符号化する識別情報の情報量を削減することができ、符号化の効率が向上する。
【００３６】
符号化部１０４は、データ削減部１０３から供給された削除後の識別情報を可逆符号化して符号化識別情報を生成し、パック部１０５へ出力するればよい。なお、ここで用いられる符号化方式は特に規定せず、ランレングス符号化やハフマン符号化などの公知の符号化方式を用いれば良い。
【００３７】
次に、パック部１０５について、図７を用いて詳細に説明する。図７は、第１の実施形態のパック部１０５が生成する１ブロック分の固定長符号化データのデータ構造を示す図である。
【００３８】
パック部１０５は、ブロックヘッダと、抽出画素値、並びに符号化識別情報をこの順番でパックし、１ブロックにつき固定長Ｌ（実施形態では仮に５１２ビットとする）の符号化データを生成して出力する。
【００３９】
この中で、ブロックヘッダには、固定長符号化データの可逆性の有効／無効を示す値（１ビットで良い）と、抽出した画素値の個数を示す値が格納される。
【００４０】
固定長符号化データの可逆性が無効となるのは、そのブロックを復号したとき、オリジナルの画像ブロックに復元できない場合である。この場合、可逆性が維持できないことを表わす“１”とする。一方、可逆性が維持できる場合には、“０”とする。すなわち、固定長符号化データの可逆性の有効／無効を示す値は１ビットで良い。
【００４１】
また、抽出する画素値の許容最大個数をＮmax（実施形態では仮に４とする）とする。１ブロックに含まれる画素値の個数が最小となるのは、１ブロック内の全画素が同じ画素値を持つ場合であり、“１”のときであって、“０”になることは無い。故に、抽出した画素値の個数は、必ず｛１、２、３、…Ｎmax｝の中のいずれかで表現する。従って、それを示すためにはの最小ビット数は「２M≧Ｎmax』を満たす最小となるＭビット確保すれば良い。
【００４２】
さて、パック部１０５は、１ブロック内に出現する画素数ｎがＮmax以下であった場合には次のようにして、固定長Ｌの符号化データを生成する。
【００４３】
先ず、パック部１０５は、画素値_0から画素値_nまで順にパックしていく。画素値_0は、抽出部１０２が最初に抽出した画素値を示す。また、画素値_1は、抽出部１０２が次に抽出した画素値を示している。以下、同様である。
【００４４】
次に、パック部１０５は、符号化識別情報_0から符号化識別情報_n-1まで順にパックしていく。符号化識別情報_0は、画素値_0の識別情報を符号化した符号化識別情報を示す。また、符号化識別情報_1は、画素値_1の識別情報を符号化した符号化識別情報を示している。以下、同様である。なお、画素値_nの識別情報_nは、画素値_0〜画素値_n-1までの識別情報から後述する復号化装置で算出可能であるため、１ブロックの固定長符号データにパックしない。このことにより、固定長符号データへパックする情報量を削減することができる。
【００４５】
上記のようにして、パック部１０５は、当初、１ブロック分の符号化データのパック対象として、
『ブロックヘッダ＋｛画素値_0, 画素値_1, …, 画素値_n｝＋｛符号化識別情報_0, 符号化識別情報_1, …, 符号化識別情報_n-1｝』
をパックしていく。この時点でブロックヘッダには、暫定的に、固定長符号化データの可逆性の有効を示す“０”と、画素値の個数ｎを格納しておく。
【００４６】
パック部１０５は、１ブロックの符号化データのデータ量（ビット数）が固定長Ｌと等しい場合にはそのまま出力する。また、Ｌに満たない場合に、上記の符号化データに後続して、不足分のダミービットを付加して固定長Ｌにして出力する。
【００４７】
一方、もし上記のようにして生成された符号化データのビット数が固定長Ｌを超えた場合、パック部１０５は、固定長符号化データの可逆性が無効であることを示す“１”に変更する。そして、パック部１０５は、１ブロック分の符号化データのビット数が固定長Ｌ以下となるまで、次に示す処理を繰り返す。
『パック対象から、最後の抽出画素値、及び、最後の符号化識別情報を破棄する。このとき、ブロックヘッダにおける抽出画素数の値を１つ減らす。』
上記の処理の結果、次のような符号化データが生成されることになる。
『ブロックヘッダ＋｛画素値_0, 画素値_1, …, 画素値_m｝＋｛符号化識別情報_0, 符号化識別情報_1, …, 符号化識別情報_m-1｝』（ただし、ｍ＜ｎ）
そして、パック部１０５は、不足分のダミービットを付加し、固定長Ｌの符号化データとして出力する。
【００４８】
上記は、１ブロック内に出現する画素数ｎがＮmax以下であった場合であったが、画素数ｎ＞Ｎｍａｘであった場合、最初のｎ個の抽出画素値以外の画素値は破棄し、有効な画素数ｎとして上記の処理を行えばよい。ただし、この場合、既に可逆性は維持できないことが確実であるので、ブロックヘッダにおける可逆性の有効／無効の値は最初から“１”（無効）に設定した上で、上記の処理を行う。
【００４９】
以上、第１の実施形態における符号化装置の構成とその処理内容を説明した。
【００５０】
次に、第１の実施形態における復号化装置について説明する。図８に第１の実施形態の復号化装置のブロック図を示す。この復号化装置は、解析部８０１、復号化部８０２、データ復元部８０３、出力部８０４で構成される。なお、実際には、各処理部内には、タイミングを合わせるための適当な容量のバッファーメモリが搭載されているものであるが、それについては省略して示していることに注意されたい。以下、同図の構成における処理内容を説明する。
【００５１】
解析部８０１は、入力された固定長符号化データ（着目ブロックの符号化データ）から、ヘッダと画素値と符号化識別情報が格納されているビットをそれぞれ読み出して出力する。復号化部８０２は、入力された符号化識別情報を復号化し、データ復元部８０３へ出力する。データ復元部８０３は、前述した符号化装置で削減した識別データのビット位置を算出し、識別情報を復元して出力部８０４へ出力する。また、データ復元部８０３は、次画素の復元すべきビット数を求めて、復号化部８０２へ出力する。出力部８０４は、入力された画素値と識別情報から画像データを生成して出力する。
【００５２】
以上が第１の実施形態の復号化装置の大まかな処理である。以下では、各構成要素の詳細を説明する。
【００５３】
まず、解析部８０１の詳細を説明する。解析部８０１は、固定長符号化データが入力されると、そのブロックヘッダを解析し、抽出画素数ｎを得る。そして、ブロックヘッダに後続するｎ個の画素値を出力部８０４へ出力する。また、解析部８０１は、符号化識別情報が格納されているビットを読み出して、読み出した符号化識別情報を、復号化部８０２へ出力する。この際、符号化識別情報にヘッダデータを付加して出力する。よって、解析部８０１以降の各ブロックでヘッダデータを参照できるものとする。
【００５４】
次に復号化部８０２の詳細を説明する。復号化部８０２は、データ復元部８０３から通知されたビット数（１ブロックの復元の初期段階では１６×１６＝２５６）の符号化識別情報を、符号化部１０４での符号化方式に対応した復号化を行い、得られた識別情報をデータ復元部８０３へ出力する。こちらも符号化器と同様に公知の技術を使えば良い。
【００５５】
また、データ復元部８０３は、前回までに確定した画素値の個数（初期段階では０）と、１ブロックサイズ（実施形態では１６×１６＝２５６）から、復号すべき識別データの個数を計算して求める。計算式は以下のようになる。
『復号すべき識別データの個数＝ ブロックサイズ ― 前回迄に確定した画素値の個数』
【００５６】
例えば、最初の抽出画素値の識別データを個数は、それ以前に確定した画素値の個数が０であるので、２５６個（２５６ビット）となる。従って、復号化部８０２は、最初の画素値に対して２５６個（２５６ビット）の識別データ（識別情報）を復号する。
【００５７】
また、最初の抽出画素値の中の“１”の識別データの個数が仮に６４個存在したとする。このとき、データ復元部８０３は２５６−６４で「１９２」を復号化部８０２に通知する。従って、復号化部８０２は、２番目の抽出画素値に対しては、１９２個（１９２ビット）の識別データを復号する。
【００５８】
また、２番目の抽出画素値の中の“１”の識別データの個数が仮に６４個存在したとする。このとき、データ復元部８０３は『２５６−（６４＋６４）』を計算し、「１２８」を復号化部８０２に通知する。従って、復号化部８０２は、３番目の抽出画素値に対しては、１２８個（１２８ビット）の識別データを復号する。以下同様である。
【００５９】
次に、データ復元部８０３について、図９を用いて説明する。データ復元部８０３は、図示の如く、復元箇所算出部９０１、バッファメモリ９０２（１６×１６ビットの容量）、復元部９０３、カウント部９０４で構成される。このうち、カウント部９０４、バッファメモリ９０２は、１ブロックの復号処理の開始に先立って、ゼロクリアされるものとする。
【００６０】
復元箇所算出部９０１は、入力された識別情報と、バッファメモリ９０２の値から、復元箇所情報を算出して、算出データを復元部９０３とカウント部９０４へ出力すると共に、バッファメモリ９０２に、次の画素値の復元箇所情報として保存する。
【００６１】
復元部９０３は、バッファメモリ９０２に保存された復元箇所情報を読み取り、復元箇所情報に基づいて、識別データを復元し、復元した識別情報（２５６ビット）を出力する。
【００６２】
カウント部９０４は、１抽出画素に対する識別情報を復元する度に、復元箇所算出部９０１から入力された算出データの“１”のビットの数のカウントした結果から、次に復号すべき識別データの個数（＝ブロックサイズ−カウント値）を算出し、復号化部８０２に出力する。
【００６３】
以下、図９の各構成要素について詳細に説明する。
【００６４】
復元箇所算出部９０１は、バッファメモリ９０２から復元箇所情報を１ビットづつデータを読み出し、その値に応じて以下の処理Ａ，Ｂのいずれかを行う。
＜処理Ａ＞
この処理Ａは、バッファメモリ９０２から読み出した値が“０”の場合の処理である。この場合、復元箇所算出部９０１は、復号化部９０２からの識別情報を構成する識別データを選択し、復元部９０３、９０４に出力する。
＜処理Ｂ＞
この処理Ｂは、バッファメモリ９０２から読み出した値が“１”の場合の処理である。この場合、復元箇所算出部９０１は、復号化部９０２からの識別情報は一時的に待機状態にし、“１”を復元部９０３、９０４に出力する。
【００６５】
上記処理Ａ、Ｂのいずれの場合であっても、次の抽出画素に対する識別データの復元に備え、出力した識別データとバッファメモリ９０２から読み出したデータを論理和し、その論理和結果で、バッファメモリ９０２内の読み出したデータを更新する。
【００６６】
復元部９０３は、復元箇所算出部９０１からの算出データを供給を受けるたび、バッファメモリ９０２からの復元箇所情報（上記の更新する以前の復元箇所情報である）と、復元箇所算出部９０１から入力された算出データとの排他的論理和をとり、その結果を復元後の識別データとして出力する。これは、復元箇所情報の“０”であり、且つ、復元箇所算出部９０１から入力された算出データが“１”の場合のみ、“１”とするためである。換言すれば、ブロック内で既に確定した画素値が存在する位置における識別データは“０”とするためである。
【００６７】
カウント部９０４は、１抽出画素に対する識別情報（２５６ビット）の復元処理が完了するたびに、復元箇所算出部９０１からの算出データの“１”の個数をカウントし、次に復号すべき識別情報のビット数（＝ブロックのサイズ−カウント値）を復号化部８０２へ出力する。
【００６８】
以下、復元箇所算出部９０１、バッファメモリ９０２、復元部９０３、カウント部９０４が処理するデータの一例を、図１０を用いて具体的に説明する。
【００６９】
図１０は、入力される各画素値の識別情報と、バッファメモリ９０２から読み出された復元箇所情報と、復元箇所算出部９０１が出力した算出データと、識別データを復元する復元箇所と、出力する復元後の識別情報と、次画素の復元bit数の例を示した図である。識別データ復元箇所の下線部は、復元部９０３が復元したビット位置を示している。また、先に説明したように、１ブロック分の識別情報の復元に先立ってバッファメモリ９０２、カウント部９０４はゼロクリアされているものとしている。また、復元箇所算出部９０１は、解析部８０１から、１ブロックに含まれる抽出画素数を入力し、抽出画素数−１個の識別情報を復元するまでは以下の処理を行う。すなわち、以下は、抽出画素値“７０”、“６０”、“５０”に対する識別情報の復元処理の説明である。
【００７０】
まず、最初の抽出画素値“７０”の識別情報“1100000011000000・・・”（２５６個の識別データ）が入力された場合について説明する。復元箇所算出部９０１は、解析部８０１から、１ブロックに含まれる抽出画素数を入力し、「抽出画素数−１」個の識別情報を復元するまでは以下の処理を行う。
【００７１】
復元箇所算出部９０１は、バッファメモリ９０２から復元箇所情報を１ビットずつ読み出していくが、全てが０であるので、入力した識別情報“1100000011000000・・・”をそのまま出力していくことになる。また、復元部９０３は、バッファメモリ９０２に格納された１ビットずつ復元箇所情報を読み出し、復元箇所算出部９０１からの算出データ（１ビット）との排他論理和を行うが、バッファメモリ９０２から読み出す復元箇所情報は全て０であるので、入力した識別情報“1100000011000000・・・”を、そのまま復元後の識別情報として出力することになる。カウント部９０４は、復元箇所算出部９０１からの算出データの“１”の個数をカウントし、「６４」を得る。従って、カウント部９０４は、次に復号すべき２番目の識別情報のビット数として１９２（＝２５６−６４）を復号化部８０２に通知する。また、上記の結果、バッファメモリ９０２は、最初の抽出画素値の識別情報で更新されることになる。
【００７２】
次に２番目の抽出画素値“６０”の識別情報“110000110000・・・”（１９２個の識別データ）が入力された場合について説明する。
【００７３】
復元箇所算出部９０１がバッファメモリ９０２から復元箇所情報“1100000011000000・・・”を１ビット単位に読み出すが、“１”の場合には、先に説明した処理Ｂを行う。すなわち、復元箇所算出部９０１は、バッファメモリ９０２から読み出した“１”を、算出データとして出力する。このとき、復号化部８０２で復号された識別情報（実施形態の場合には１９２ビット）は保留状態にある。図１０の場合、バッファメモリ９０２から読み出した最初の２つの復元箇所情報が共に“１”であるので、復元箇所算出部９０１は最初の２つについては“１”を出力する。
【００７４】
一方、バッファメモリ９０２から読み出したデータが“０”の場合には、先に説明した処理Ａを行う。すなわち、復元箇所算出部９０１は、復号化部８０２で復号された識別データを、算出データとして出力する。
【００７５】
以上の結果、復元箇所算出部９０１は、最初の抽出画素の識別データの“０”となっている箇所（全部で１９２箇所）に対して、復号化部８０２で生成された１９２個の識別データを配置した、計２５６個の算出データを出力することになる。また、復元部９０３は、バッファメモリ９０２に格納された１ビットずつ復元箇所情報を読み出し、復元箇所算出部９０１からの算出データ（１ビット）との排他論理和を行う。排他論理和であるので、双方が“１”のときには、その論理演算結果は“０”となる。従って、結果的に、２番目の抽出画素値を持つ画素位置だけ“１”、それ以外では“０”の、計２５６個の識別データが復元できることになる。また、上記の結果、バッファメモリ９０２には、最初、及び、２番目の抽出画素値が位置した箇所で“１”、それ以外では０のデータで更新されることになる。別な言い方をすれば、バッファメモリ９０２には、抽出画素値を持つものとして確定した箇所では“１”、未定の箇所では“０”のデータで更新されることになる（最初と２番目の復元後の識別データの論理和と同じでもある）。また、カウント部９０４は、復元箇所算出部９０１からの算出データの“１”の個数をカウントし、「１２８」を得る。従って、カウント部９０４は、次に復号すべき３番目の識別情報のビット数として１２８（＝２５６−１２８）を復号化部８０２に通知する。また、上記の結果、バッファメモリ９０２は、最初の抽出画素値の識別情報で更新されることになる。
【００７６】
次に３番目の画素値“５０”の識別情報“11001100・・・”（１２８個の識別データ）を入力した場合の、復元箇所算出部９０１の処理内容は、上記の２番目の画素値を入力された場合と同様である。
【００７７】
次に、４番目、すなわち、最後の抽出画素値に対する識別情報の復元処理を説明する。なお、識別情報の復元処理が着目ブロックに対して最後か否かは、復元箇所算出部９０１が判定する。具体例では、解析部８０１より入力した抽出画素数から、これまでに復元した識別情報の個数を減じた値が“１”であるか否かで判定すれば良い。
【００７８】
復号化部８０２は、４番目の抽出画素値“４０”に対する識別情報は復号していない。復元箇所算出部９０１は、無条件に“１”のデータを算出データとして出力する。復元部９０３は、バッファメモリ９０２に格納された１ビットずつ復元箇所情報を読み出し、復元箇所算出部９０１からの算出データ“１”との排他論理和を行う。結果、復元部９０３は、バッファメモリ９０２における０、１とを反転した結果を、４番目の抽出画素値“４０”に対する識別情報（２５６ビット）として出力することになる。この結果、復元部９０３は、１番目から３番目までの抽出画素値を持つ画素位置では“０”、それ以外の未割り当ての画素位置は４番目の抽出画素値を持つ画素位置として“１”を出力することになる。
【００７９】
次に図８の出力部８０４の詳細を説明する。出力部８０４は、入力された画素値と識別情報から画像データを生成し出力する。即ち、入力された識別情報を参照し、その中の個々の識別データが“１”であれば、入力された画素値を内部のブロックバッファに格納する。以降、画素値と識別情報が入力される毎に前述した動作を繰り返すことで、１ブロック分の画像データを生成し出力する。そして、これを１画像分繰り返し、画像データを復元する。
【００８０】
以上説明したように、本第１の実施形態によれば、画素毎の識別情報を生成する際、ブロック内で既に確定した画素位置がある場合はその画素位置を除き、データを削減した識別情報を生成して符号化部へ出力する。このことにより、ブロック内の同じ位置を示す識別情報を何度も符号化しないようにすることができる。従って、符号化部で符号化する識別情報の情報量を削減することができ、符号化の効率を向上させることができる。
【００８１】
なお、上記実施形態の発明に係る技術思想を一般化して示すのであれば、画像符号化装置は以下の構成を有することになる。すなわち、
画像データを符号化し、符号化データを生成する画像符号化装置であって、
画像データを、Ｍ個（実施形態ではＭ＝１６×１６）の画素で構成されるブロック単位に入力するブロック化部と、
該ブロック化部で入力した着目ブロック内を解析し、当該着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を抽出すると共に、
判定した１つの画素値Ｐi（ｉは1,2,…,ｎのいずれか)について、前記着目ブロック内の各画素位置毎に、前記画素値Ｐiを持つ画素か否かを識別するための識別データを割り当て、Ｍ個の前記識別データで構成される識別情報Ｔiを生成する抽出部と、
該抽出部で生成された識別情報Ｔ1,Ｔ2,…,Ｔn-1における識別データを削減し、削減後の識別情報Ｔ1',Ｔ2'，…,Ｔn-1'を出力するデータ削減部と、
該データ削減部による削減後の各識別情報Ｔ1',Ｔ2',…,Ｔn-1'を符号化し、それぞれの符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1を生成する符号化部と、
前記画素値Ｐ1,Ｐ2,…,Ｐnと、前記符号化部で得られた符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1とをパックし、前記着目ブロックの符号化データとして出力するパック部とを有し、
前記データ削減部は、
識別情報Ｔiの削減処理の際には、当該識別情報Ｔiを構成するＭ個の識別データの中で、それ以前の識別情報Ｔ1乃至Ｔi-1の削減処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置の識別データを削除し、画素値Ｐ1乃至Ｐi-1のいずれの画素値でもない画素位置の識別データを残すことで、削減後の識別情報Ｔi'を出力することを特徴とする。
【００８２】
ここで、実施形態に従えば、符号化部は、識別情報Ｔ1',Ｔ2',…,Ｔn-1'それぞれを符号化して符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1を生成し、パック部は、画素値Ｐ1,Ｐ2,…,Ｐnと、符号化識別情報Ｃ1,Ｃ2,…,Ｃn-1をパックし、着目ブロックの符号化データとして出力する。つまり、最後の画素値Ｐnに対応する識別情報は符号化データには含めない。
【００８３】
一方、一般化した復号装置は以下の構成を有することになる。すなわち、
符号化画像データを復号する画像復号装置であって、
Ｍ個の画素で構成されるブロックの符号化データを入力する入力部と、
該入力部で入力部で入力した着目ブロックの符号化データを解析し、当該符号化データから前記着目ブロック内に出現する画素値Ｐ1,Ｐ2,…,Ｐn（ただし、１≦ｎ≦Ｍ）を取得すると共に、前記着目ブロック内の各画素位置が画素値Ｐi（ｉは1,2,…)であるか否かを表わす識別データで構成される識別情報Ｔi'の符号化識別情報Ｃiを取得する解析部と、
該解析部で得られた各符号化識別情報Ｃ1, Ｃ2, …を復号し、識別情報Ｔ1', Ｔ2', …を生成する復号部と、
該復号部で得られた識別情報Ｔ1', Ｔ2', …における削減された識別データを復元し、復元後の識別情報Ｔ1, Ｔ2, …を生成する復元部と、
前記画素値Ｐiと復元された識別情報Ｔiを用いて、画素値Ｐiを持つと判定された画素位置に画素値Ｐiを割り当てることで、前記着目ブロックの内の各画素値を決定し、前記着目ブロックの画像データとして出力する出力部とを有し、
前記復元部は、
識別情報Ｔi'の削減処理の際には、それ以前の識別情報Ｔ1'乃至Ｔi-1'の復元処理で判明した画素値Ｐ1乃至Ｐi-1のいずれかの画素値を持つ画素位置については画素値Ｐiではないことを示す識別データを新規に生成し、前記画素値Ｐ1乃至Ｐi-1のいずれでもない画素位置については前記識別情報Ｔi'における識別データを出力することで、Ｍ個の識別データで構成される識別情報Ｔiを生成することを特徴とする。
【００８４】
ここで、実施形態によれば、復元部は、画素値Ｐ1,Ｐ2,…,Ｐn-1と、復号部で得られた識別情報Ｔ1乃至Ｔn-1に基づき、着目ブロック内の画素値Ｐ1,Ｐ2,…,Ｐn-1を持つ画素位置にそれぞれの画素値を割り当て、未割り当ての画素位置に前記Ｐnの画素値を割り当てることになる。
【００８５】
上記実施形態では、ブロック内に出現する画素値を順番については特に言及しなかった。これまでの説明からもわかるように、実施形態では、１ブロックに対する符号化データは固定長とできるものの、全てのブロックについて可逆性を維持することを保証しない。そして、可逆性を維持できないのであれば、可能な限り、オリジナルのブロックの画像と、復号後のブロックの画像と差は小さい方が望ましい。そのためには、抽出画素の順番として、出現回数が多い順にすることである。詳細は、第３の実施形態で説明するが、着目ブロック（実施形態では１６×１６画素）の画像データを入力したとき、その中で出現頻度の多い順に抽出画素値を並べるものである。それをデータ削減部１０３、パック部１０５に通知する。このようにすると、固定長Ｌとするために、破棄された画素値は、元々、出現頻度が少ない画素値とすることができるので、画質劣化を最小限にできる。また、符号化する順番も、出現頻度が多いものが優先して配置されることになるので、符号化効率の点でも有利になる。
【００８６】
なお、実施形態では、着目ブロックに対する当初の符号化データが固定長Ｌを超える場合、その固定長Ｌとするために、抽出画素値及びそれに対応する符号化識別情報を破棄するものとして説明した。しかしこれに限定されない。例えば、当初の符号化データが固定長Ｌを超える場合には、１６×１６画素に対して、最初からＪＰＥＧ等の非可逆符号化処理を実行するようにしても良い。この場合、ブロックデータのヘッダの先頭の固定長符号化データの可逆性の有効／無効のビットは無効を表わし、後続して５１１ビットのＪＰＥＧ符号化データを格納すればよい。１６×１６画素には、ＤＣＴの処理単位となる８×８画素の小ブロックが４つ含まれる。そこで、この場合のＪＰＥＧ符号化データのデータ構造は、最初にＤＣ成分の符号化データを並べ、それに後続してＡＣ成分の符号化データを並べるようにする。そして、５１１ビットに満たない場合にはダミービットを付加し、５１１ビットを超えた場合には、超過分を破棄する。復号装置の構成は、図８の構成に、ＪＰＥＧ復号部を追加し、ブロックデータの可逆性の有効／無効のビットは無効を示す場合には、ＪＰＥＧ復号部で復号を行なう構成とすれば良いであろう。また、ここでは符号化データが固定長Ｌを超える場合にＪＰＥＧ処理を実行する例を説明したが、勿論これに限定するわけではなく、別の符号化方式で符号化処理を行っても良い。
【００８７】
［第２の実施形態］
第２の実施形態では、第１の実施形態に比べて、より高速に処理する構成について説明する。具体的には、復号化装置において、第１の実施形態では各画素値の識別情報を逐次処理していた構成に対して、第２の実施形態では並列処理を行うことで、処理速度を速くする構成である。
【００８８】
なお、本第２の実施形態における符号化装置の符号化部１０４は、各抽出画素値の符号化識別情報の符号量もパック部１０５に出力する。そして、パック部１０５は、ブロックヘッダに、各抽出画素値の符号化識別情報の符号量を格納するものとする。
【００８９】
以下、本第２の実施形態における復号化装置について説明する。
【００９０】
図１１は、本発明の第２の実施形態における復号化装置のブロック構成図である。図１１と図８（第１の実施形態）との違いは、復号化部を複数有する点と、データ復元部が復号化部へ次画素の識別情報の復元すべきビット数を出力しない点である。また、各復号化部において、各画素値の識別情報毎に並列処理を行う点で異なる。それ以外は第１の実施形態と同様であるので、その詳述は省略する。従って、以降では第１の実施形態と異なる動作についてのみ詳細な説明を行う。なお、図１１では復号化部が３つあるのは、第１の実施形態と同様、最大４つの画素値を抽出するためである。
【００９１】
まず、解析部１１０１について説明する。解析部１１０１は、入力された固定長符号データのヘッダデータ内に格納された、各画素値の符号化識別情報の符号量を読み取る。そして、読み取った各画素値の符号化識別情報の符号量に基づいて、各画素値の符号化識別情報をそれぞれ各復号化部１１０２へ出力する。
【００９２】
次に、復号化部１１０２について説明する。第１の実施形態と異なり、解析部１１０１が各画素値の符号化識別情報を抽出して各復号化部１１０２へ出力しているので、各復号化部１１０２は、入力された符号化識別情報の符号量分を全て復号化すれば良い。
【００９３】
次に、データ復元部１１０３について説明する。第１の実施形態と異なり、復号化部１１０２で復号化する符号量を算出する必要がないため、データ復元部１１０３は、復号化部１１０２へ次画素の復号すべき識別情報のビット数数を出力しない。データ復元部１１０３は、入力された各画素値の識別情報を元にして識別情報_0、1, 2, 3の順番に、復元された識別情報を復元し、出力部１１０４へ出力する。
【００９４】
次に、出力部１１０４について説明する。第１の実施形態と異なり、出力部１１０４は、各画素値の識別情報が並列に入力される。よって、出力部１１０４は、並列に入力された各画素値の識別情報と各画素値から１ブロック分の画像データを生成し、出力する。
【００９５】
なお、本実施形態では、復号化部１１０２の個数は３つとしているが、これは符号化器において画素値の個数の最大値を４としたためであり、画素値の個数の最大値に応じて復号化部１１０２の数を決定する。以上説明したように、復号化部を複数有して並列処理を行うことによって、第１の実施形態と比べて処理速度を向上することができる。
【００９６】
［第３の実施形態］
第３の実施形態では、第１の実施形態に比べて、データ削減部が出力する識別情報の情報量を更に減らす構成について説明する。具体的には、符号化装置において、第１の実施形態では各画素値の識別情報を、抽出した順にデータ削減部が削減していた構成に対して、第３の実施形態では、データ削減部が削減する識別情報の順序を制御する構成である。これにより、データ削減後の識別情報の情報量を減らすことができ、符号化の効率を向上させることができる。復号化装置の構成に変更は無く、第１の実施形態と同様の構成である。以下で符号化装置について説明する。
【００９７】
図１２は、本発明の第３の実施形態における符号化装置のブロック構成図である。図１２と図１（第１の実施形態）との違いは、出力順序制御部を有する点である。それ以外は第１の実施形態と同様であるので、その詳述は省略する。従って、以降では第１の実施形態と異なる動作についてのみ詳細な説明を行う。
【００９８】
出力順序制御部１２０３について説明する。出力順序制御部１２０３は、入力された各抽出画素値毎の識別情報の“１”の識別データの数をカウントする。そして、カウントした値に基づいて、各抽出画素値の識別情報を出力する順序を制御し、後段のデータ削減部１２０４へ出力すると共に、その順序で抽出画素値を後段のパック部１２０６へ出力する。
【００９９】
図１３は本実施形態における出力順序制御部の構成を示すブロック図である。出力順序制御部１２０３の詳細について、図１３を用いて説明する。
【０１００】
カウント部１３０１は、抽出部１２０２から識別情報が入力されると、識別情報の“１”の識別データの個数をカウントし、カウントした値をメモリ１３０２へ保存する。メモリ１３０２には、抽出部１２０２から入力された抽出画素値と識別情報と、カウント部１３０１から入力されたカウント値が保存される。着目ブロックに対する全抽出画素値に対する情報がメモリ１３０２に格納されると、出力部１３０３は、メモリ１３０２に保存された各識別情報毎のカウント値を読み出し、そのカウント値の大きいに出力順序を決定する。そして、出力部１３０３は、その順序でメモリ１３０２から識別情報を読み出して、後段のデータ削減部１２０４へ出力すると共に、抽出画素値をメモリ１３０２から読み出してパック部１２０６へ出力する。
【０１０１】
以下、図１３の各構成要素について詳細に説明する。まず、カウント部１３０１について詳細に説明する。
【０１０２】
抽出部１２０２から最初の画素値とその識別情報が入力されると、メモリ１３０２へ保存されると共に、識別情報はカウント部１３０１へ入力される。そして、カウント部１３０１は、入力された識別情報の“１”の識別データの個数をカウントし、メモリ１３０２へ保存する。以降、抽出部１２０２から画素値と識別情報が入力される毎に、前述した処理内容を同様に繰り返していき、１ブロック分の全ての画素値と識別情報とそのカウント値をメモリ１３０２へ保存する。
【０１０３】
次に、出力部１３０３について詳細に説明する。出力部１３０３は、まず、メモリ１３０２に保存された、１ブロック分の各識別情報毎のカウント値を読み出す。そして、カウント値が最も大きい識別情報と画素値をメモリ１３０２から読み出して、識別情報を後段のデータ削減部１２０４へ出力すると共に、その画素値をパック部１２０６へ出力する。次に、カウント値が２番目に大きい識別情報と画素値をメモリ１３０２から読み出して、識別情報を後段のデータ削減部１２０４へ出力すると共に、その画素値をパック部１２０６へ出力する。以降、カウント値が大きい順に識別情報と画素値を出力していく。
【０１０４】
カウント部１３０１と出力部１３０３が処理するデータの一例を、図１４〜図１６を用いて具体的に説明する。
【０１０５】
図１４は、ブロック化部１２０１が出力する４×４画素のブロックデータの例である。なお、本実施形態では説明を簡単なものとするために４×４画素のブロックデータとしているが、４×４画素に限らず、第１の実施形態と同様、１６画素×１６画素等、他の大きさのブロックデータにも適用できる。図１４はあくまで便宜的なものと理解されたい。図１５は、出力順序制御部１２０３と、データ削減部１２０４が処理する識別情報の例である。
【０１０６】
出力順序制御部１２０３内のカウント部１３０１は、抽出部１２０２から識別情報が入力されると、識別情報の“１”の識別データの個数をカウントして、メモリ１３０２へ保存する。図１５において、画素値「８」の識別情報の“１”の識別データの個数は、「１」となるため、画素値「８」の識別情報のカウント値「１」をメモリ１３０２へ保存する。また、画素値「９」の識別情報の“１”の識別データの個数は「２」となるため、画素値９の識別情報のカウント値「２」をメモリ１３０２へ保存する。以降、画素値「７０」と画素値「５０」に関しても同様にして“１”の個数をカウントし、それぞれのカウント値「１０」と「３」をメモリ１３０２へ保存する。
【０１０７】
出力部１３０３は、メモリ１３０２へ保存されたカウント値をを読み出して、そのカウント値の大きい順に、メモリ１３０２から識別情報と画素値を読み出して後段のデータ削減部１２０４へ出力する。図１５において、出力順序制御部１２０３は、カウント値が最も大きい画素値「７０」とその識別情報を、最初に出力する。次に、カウント値が２番目に大きい画素値「５０」とその識別情報を出力する。以降、カウント値の大きい順に、画素値９と画素値８についても順次出力していく。なお、カウント値が同数であった場合には、いずれでも構わないが、例えば先に入力した方を優先する等で良いであろう。
【０１０８】
データ削減部１２０４は、第１の実施形態で説明したように、既に確定した識別データを削減して出力する。そのため、最初に多くの識別データが確定していればそれだけ多くの識別データを削減することができる。よって、既に確定した識別データが最も多い識別情報、即ち、カウント値が最も大きい識別情報である画素値７０の識別情報を最初に処理することで、より多くの識別データを削減することができる。
【０１０９】
具体的には、最もカウント値が大きい画素値「７０」の識別情報を最初に出力することで、データ削減部１２０４は、２つ目の画素値「５０」の識別情報を削減する際、既に出力した画素値「７０」の識別情報の“１”に該当する識別データを削減する。画素値「７０」の識別情報の“１”の個数は１０個であるため、画素値「５０」の識別情報を削減する際、１０個の識別データを削減できる。
【０１１０】
このようにして、カウント値の大きい順序に識別情報を出力するように制御することで、後段のデータ削減部１２０４でより多くの識別データを削減することが可能になり、削減後の識別情報の情報量をより少なくできる。また、仮に出現する画素値の個数が多く、固定符号長の可逆性が維持できない場合であっても、破棄されるのは出現頻度の少ない画素値とすることができるので、画質劣化も小さなものとすることができる。
【０１１１】
図１６は、出力順序制御部がない場合の例を示す図である。処理の内容は第１の実施形態と同様であるため、説明は省略する。図１６に示した、出力順序の制御を行わない場合のデータ削減後の識別情報より、本実施形態の図１５に示した、出力順序の制御を行った場合のデータ削減後の識別情報の方が、より情報量が削減されていることが分かる。
【０１１２】
以上説明したように、本第３の実施形態によれば、抽出部で抽出したブロック内の識別情報をデータ削減部へ出力する際、各識別情報の識別データの“１”の個数が多い順にデータ削減部へ出力する。このことにより、データ削減後の識別情報の情報量を更に減らすことができ、符号化の効率を向上させることができる。
【０１１３】
［第４の実施形態］
第４の実施形態では、第１の実施形態に比べて、データ削減部へ入力する画素値と識別情報の種類を減らす構成について説明する。
【０１１４】
具体的には、符号化装置において、第１の実施形態では抽出した全ての画素値と識別情報をデータ削減部へ入力していた構成に対して、第４の実施形態では、抽出した画素値と識別情報の種類を減らす変換をしてからデータ削減部へ入力する構成である。
【０１１５】
これにより、データ削減部以降で処理を行う画素値と識別情報の種類を減らすことができ、符号化の効率を向上させることができる。復号化装置の構成に変更は無く、第１の実施形態と同様の構成である。以下で符号化装置について説明する。
【０１１６】
図１７は、本発明の第４の実施形態における符号化装置のブロック構成図である。図１７と図１（第１の実施形態）との違いは、変換部を有する点である。それ以外は第１の実施形態と同様であるので、その詳述は省略する。従って、以降では第１の実施形態と異なる動作についてのみ詳細な説明を行う。
【０１１７】
変換部１７０３について説明する。変換部１７０３は、入力された１ブロック内の各抽出画素値間の差分を検出する。そして、ある抽出画素値間の差分が、予め定められた閾値より小さいものに関しては、それらの画素値を１つの画素値に変換して、後段のデータ削減部へ出力する。この時の識別情報については、それらの画素値の識別情報の論理和を、変換後の画素値の識別情報として出力する。閾値は、事前に変換部１７０３に設定しておき、ブロック内の画素値間の差分が、予め定められた値以上の場合は前述した変換を行わない。
【０１１８】
以下、変換部１７０３の詳細を説明する。変換部１７０３は、抽出部１７０２から入力された１ブロック分の画素値と識別情報を、変換部１７０３内の図示しないメモリへ保存する。そして、メモリに保存された抽出画素値を読み取り、１ブロック内の各抽出画素値間の差分値を検出する。メモリへ１ブロック分の抽出画素値が入力されたかどうかは、例えば、抽出部１７０２から変換部１７０３へ、図示しないブロック終了信号を出力し、変換部１７０３がブロック終了信号を検知して判断しても良い。各抽出画素値間の差分値の検出については、例えば以下の方法で実行する。まず、メモリから１ブロック分の抽出画素値を読み出す。そして、抽出画素値の大きい順に並べ替えて、その並びの隣り合う抽出画素値毎に前後の画素値との差分を取る。その後、変換部１７０３は、検出した各抽出画素値間の差分値と、予め定められた値に基づいて、以下の処理を行う。
【０１１９】
検出した各画素値間の差分値が、予め定められた値より小さい場合は、それらの画素値を１つの画素値に変換する。その際、ブロック内の濃度を一定に保つように、それぞれの識別情報の“１”の数の割合に応じて、変換後の画素値を決定する。例えば、差分が閾値より小さくなる２つの抽出画素値があるとする。この場合、それぞれの識別情報の“１”の数に応じて線形補間で変換後の抽出画素値を決定する。例えば、２つの抽出画素値におけるそれぞれの“１”の識別データの個数が同じである場合、その２つの画素値を足して２で割った値を、変換後の抽出画素値とする。また、その際の変換後の識別情報は、２つの抽出画素値それぞれの識別情報の論理和とする。そして、変換後の画素値と識別情報を、データ削減部１７０４へ出力する。
【０１２０】
検出した各抽出画素値間の差分値が、予め定められた値以上の場合は、上述した変換は行わず、メモリから抽出画素値と識別情報を読み込み、後段のデータ削減部１７０４へ出力する。
【０１２１】
変換部１７０３が処理するデータの一例を、図１８を用いて具体的に説明する。図１８は、変換部１７０３へ入力される抽出画素値と識別情報の例と、変換部１７０３が出力する変換後の抽出画素値と識別情報を示した図である。
【０１２２】
まず、変換部１７０３は抽出部１７０２から入力された１ブロック分の画素値“５”、“９”、“７０”、“５０”とそれぞれの識別情報を、変換部１７０３内の図示しないメモリへ保存する。そして、保存した画素値を大きい順に並べ替え、“７０”、“５０”、“９”、“５”の順番にする。次に、それぞれの画素値の前後との差分である“２０”、“４１”、“４”を検出する。そして、検出した値と予め定められた閾値と比較する。ここでは、閾値は“１０”として説明を続ける。変換部１７０３は、閾値“１０”と、検出した各抽出画素値間の差分値“２０”、“４１”、“４”を比較する。比較した結果、画素値間の差分値“４”については、閾値“１０”より小さいため、画素値間の差分値が“４”となるとなる２つの抽出画素値を１つの画素値に変換する処理を行う。
【０１２３】
画素値間の差分値が“４”となる２つの抽出画素値は、“５”と“９”であり、それぞれの識別情報は、“1000000000000000”と“0111000000000000”である。画素値“５”の識別情報の“１”の個数は１個であり、画素値“９”の識別情報の“１”の個数は３個である。よって変換後の画素値は線形補間演算により、５×１＋９×３／（１＋３）＝８、の演算結果から８となる。また、変換後の識別情報は、それぞれの識別情報の論理和である“1111000000000000”となる。そして、変換後の抽出画素値“８”とその識別情報“1111000000000000”を後段のデータ削減部１７０４に出力する。このように変換することで、ブロック内の濃度値を変えずに、画素値の種類を減らすことが可能である。
【０１２４】
なお、本実施形態では、各画素値間の差分が予め定められた値より小さくなる画素が２個の場合について説明したが、複数個ある場合も同様に処理を行うことで、画素値の種類を削減できる。
【０１２５】
以上説明したように、本第４の実施形態によれば、抽出部で抽出したブロック内の画素値と識別情報をデータ削減部へ入力する際、画素値と識別情報の種類を減らす変換をしてから入力する。このことにより、データ削減部以降で処理を行う画素値と識別情報の種類を減らすことができ、符号化の効率を向上させることができる。
【０１２６】
［第５の実施形態］
第５の実施形態では、第３の実施形態に比べて、データ削減部へ入力する識別情報の開始位置を変更する構成について説明する。
【０１２７】
符号化装置において、第３の実施形態では識別情報の先頭の識別データから順にデータ削減部へ入力していた。これに対して、第５の実施形態では、識別情報の末尾の識別データがその先頭の識別データに隣接するリング状になっているものとし、識別データの同じ値が最も多く連続する箇所を最後に配置するように開始位置を変更してからデータ削減部へ入力する。
【０１２８】
これにより、後段の符号化部において、符号語長の短い符号語を用いてより多くの識別データを所定のコードに置き換えることができ、符号化する際の効率を更に向上させることができる。復号化装置は、符号化装置で変更した開始位置情報に基づいて、画像データを生成し出力する。
【０１２９】
以下、本実施形態における符号化装置について説明する。
【０１３０】
図１９は、本発明の第５の実施形態における符号化装置のブロック構成図である。図１９と図１２（第３の実施形態）との違いは、開始位置制御部を有する点と、開始位置制御部からパック部へ開始位置情報を出力する点である。それ以外は第３の実施形態と同様であるので、その詳述は省略する。従って、以降では第３の実施形態と異なる動作についてのみ詳細な説明を行う。
【０１３１】
開始位置制御部１９０４について説明する。開始位置制御部１９０４は、出力順序制御部１９０３から識別情報が入力されると、入力された識別情報の“１”若しくは“０”が最も連続する箇所を検出する。そして、検出した最も連続する箇所の次の識別データを、最初に出力する開始位置とする。開始位置制御部１９０４は、設定した開始位置に基づいて、識別情報を後段のデータ削減部１９０５に出力すると共に、設定した開始位置情報をパック部１９０７へ出力する。パック部１９０７は、開始位置情報をヘッダへ格納する。
【０１３２】
図２０は本実施形態における開始位置制御部１９０４の構成を示すブロック図である。図２０を用いて、開始位置制御部１９０４について詳細に説明する。
【０１３３】
メモリ２００１には、出力順序制御部１９０３から入力された識別情報が保存される。
【０１３４】
検出部２００２は、メモリ２００１に保存された識別情報を読み取り、“１”若しくは“０”が最も連続する箇所（最大ラン）を検知し、その連続個所の終了位置とその連続数を検出する。そして、検出した連続終了位置と連続数を比較部２００３へ出力する。比較部２００３は、検出部から入力された連続数をランレングス符号化で符号化した際の符号量と、予め設定された値を比較する。そして、比較結果に基づいて、開始位置情報を生成し、生成した開始位置情報を出力部２００４へ出力すると共に、後段のパック部１９０７へ出力する。出力部２００４は、比較部２００３から入力された開始位置情報に基づいて、メモリ２００１から識別情報を読み込み、後段のデータ削減部１９０５へ出力する。
【０１３５】
以下、図２０の各構成要素について詳細に説明する。
【０１３６】
検出部２００２は、メモリ２００１に保存された識別情報を読み取り、“１”若しくは“０”が最も連続する箇所の終了位置と、その連続数を検出する。検出の仕方は、例として、以下の様に行う。
【０１３７】
メモリ２００１に、出力順序制御部１９０３から入力された１つ目の識別情報が保存される。そして、検出部２００２は、メモリ２００１から１つ目の識別情報を読み取り、識別情報内の各識別データに注目する。
【０１３８】
識別データは“１”若しくは“０”の２値データであるため、注目した識別データが前の識別データと同じかどうかを判断することで、連続する数をカウントしていく。そして、最も連続するカウント数と、その時の終了位置を検出する。検出した終了位置を連続終了位置として比較部２００３へ出力する。また、検出した最も連続するカウント数を、連続数として比較部２００３へ出力する。
【０１３９】
比較部２００３は、検出部から入力された連続数をランレングス符号化で符号化した際の符号量と、予め設定されたＥＯＢ（Ｅｎｄ Ｏｆ Ｂｌｏｃｋ）の符号量を比較する。なお、ＥＯＢは、符号化部１９０６で符号化する際に使用される所定のコードで、ある識別データ以降がブロックの最後まで同じである時に、それらの符号化データをＥＯＢに置き換える。ＥＯＢは高い頻度で使用される符号語であり、短い符号語が割り当てられていることが多いため、置き換えることにより符号量を削減することが出来る。
【０１４０】
そして、連続数をランレングス符号化で符号化した際の符号量が、ＥＯＢの符号量より大きい場合、連続終了位置の直後の識別データの位置を開始位置情報として、出力部２００４へ出力すると共に、パック部１９０７へ出力する。連続数をランレングス符号化で符号化した際に生成されるランレングス符号化データの符号量が、ＥＯＢの符号量以下の場合は、開始位置情報は変更しない。そのため、従来通り識別データの先頭を開始位置情報として、出力部２００４へ出力すると共に、パック部１９０７へ出力する。
【０１４１】
出力部２００４は、比較部２００３から入力された開始位置情報に基づいて、メモリ２００１から識別情報を読み取る。そして、読み取った識別情報を後段のデータ削減部１９０５へ出力する。
【０１４２】
以上説明した内容で、開始位置制御部１９０４は、１つ目の識別情報に関する処理を終了する。
【０１４３】
出力順序制御部１９０３から入力される２つ目以降の識別情報については、１つ目の識別情報の処理で設定した開始位置情報に基づいて、出力部２００４が順次メモリ２００１から識別情報を読み取って後段のデータ削減部１９０５へ出力していく。
【０１４４】
開始位置制御部１９０４内の、検出部２００２と、比較部２００３と、出力部２００４が処理するデータの一例を、図２１を用いて具体的に説明する。
【０１４５】
図２１は、ブロックデータと、開始位置制御部１９０４に入力される識別情報と、開始位置制御部１９０４がスキャン開始位置を変更して出力した識別情報の例である。
【０１４６】
まず、１つ目の画素値“７０”の識別情報“0101111111110010”が、開始位置制御部１９０４に入力され、メモリ２００１に保存される。そして、検出部２００２が、メモリ２００１から識別情報“0101111111110010”を読み取り、連続数“９”と、その終了位置“１２番目”を検出し、比較部２００３へ出力する。次に、比較部２００３は、入力された連続数をランレングス符号化した符号量とＥＯＢ符号量を比較する。
【０１４７】
この時、連続数をランレングス符号化した符号量は“８”で、ＥＯＢの符号量は“６”とする。比較した結果、連続数の符号量の方がＥＯＢ符号量より大きい為、入力された終了位置“１２番目”の次の識別データの位置である“１３番目”を、開始位置情報として出力部２００４へ出力すると共に、後段のパック部１９０７へ出力する。
【０１４８】
そして、出力部２００４は、入力された開始位置情報“１３番目”に基づいて、メモリ２００１に保存された識別情報を読み取り、１３番目の識別データを先頭の識別データとなるように変更した識別情報“0010010111111111”を出力する。
【０１４９】
このように識別情報の開始位置を変更することで、識別情報内の最も連続する箇所を最後に配置することができ、後段の符号化部で符号化する際に、連続する箇所を所定のコードであるＥＯＢに置き換えることができる。
【０１５０】
２つ目以降の識別情報に関しては、１つ目の識別情報で設定された開始位置情報に基づいて、出力部２００４がメモリ２００１から識別情報を読み取り、後段のデータ削減部１９０５へ識別情報を出力する。
【０１５１】
次に、本実施形態における復号化装置について説明する。
【０１５２】
図２２は、本実施形態における復号化装置のブロック構成図である。図２２と図８（第１の実施形態）との違いは、解析部から出力部へ開始位置情報を出力する点である。それ以外は第１の実施形態と同様であるので、その詳述は省略する。従って、以降では第１の実施形態と異なる動作についてのみ詳細な説明を行う。
【０１５３】
解析部２２０１は、第１の実施形態で説明した解析部８０１の動作に加えて、符号化装置から入力された固定長符号化データ内の開始位置情報を読み取り、読み取った開始位置情報を出力部２２０４へ出力する。
【０１５４】
出力部２２０４は、入力された開始位置情報に基づいて画像データを生成し出力する。例えば、解析部２２０１から入力された開始位置情報が１３であった場合、出力部２２０４は、データ復元部２２０３から入力された識別情報の先頭の識別データを、生成する１ブロック分の画像データの１３番目とする。以降、第１の実施形態と同様の処理を行っていき、画像データを出力する。
【０１５５】
以上説明したように、本第５の実施形態によれば、抽出部で抽出したブロック内の識別情報をデータ削減部へ入力する際、識別情報内の識別データについて、同じ値が最も多く連続する箇所を最後に配置するように開始位置を変更してからデータ削減部へ入力する。これにより、後段の符号化部において、より多くの識別データを所定のコードに置き換えることができ、符号化する際の効率を更に向上させることができる。
【０１５６】
［第６の実施形態］
第６の実施形態では、第１の実施形態に比べて、データ削減部が出力する識別情報において、識別データの“１”若しくは“０”の連続性をより高める構成について説明する。具体的には、符号化装置において、第１の実施形態では抽出部で各画素値の識別情報を抽出する際、一様のスキャン方向で抽出していた構成に対して、第６の実施形態では、複数のスキャン方向で抽出する構成である。そして、複数のスキャン方向の中から、データ削減後の識別情報の“１” 若しくは“０”が最も連続する方向を選択し、その時の識別情報を符号化する。これにより、データ削減後の識別情報の“１” 若しくは“０”が連続する数をより多くすることができ、符号化部で実施する符号化の効率を更に向上させることができる。
【０１５７】
復号化装置は第１の実施形態で説明した動作において、符号化装置で選択したスキャン方向に基づいて、画像データを生成して出力する。
【０１５８】
以下、本第６の実施形態における符号化装置について説明する。
【０１５９】
図２３は、本発明の第６の実施形態における符号化装置のブロック構成図である。図２３と図１（第１の実施形態）との違いは、抽出部とデータ削減部を複数有し、それぞれの抽出部において、抽出画素値と識別情報を抽出する際のスキャン方向が異なる点と、比較部を有する点と、比較部からパック部へスキャン方向を出力する点である。それ以外は第１の実施形態と同様であるので、その詳述は省略する。従って、以降では第１の実施形態と異なる動作についてのみ詳細な説明を行う。
【０１６０】
以下、説明を簡単なものとするために、抽出部２３０２がスキャンする方向は水平方向で、抽出部２３０４がスキャンする方向は垂直方向として説明するが、それぞれの抽出部でスキャンする方向は他の方向でも良い。また、抽出部が２個の場合を例として説明するが、３個以上の場合でも同様である。
【０１６１】
比較部２３０６は、データ削減部２３０３から入力された水平方向にスキャンした場合の削減後の識別情報と、データ削減部２３０５から入力された垂直方向にスキャンした場合の削減後の識別情報を比較部２３０６内のメモリへ保存する。そして、各識別情報の“１” 若しくは“０”の識別データが連続する数を検出する。そして、最も識別データが連続する場合のスキャン方向時の識別情報を、後段の符号化部２３０７へ出力すると共に、パック部２３０８へ画素値とその時のスキャン方向を出力する。
【０１６２】
図２４は本実施形態における比較部２３０６の構成を示すブロック図である。比較部２３０６の詳細について、図２４を用いて説明する。
【０１６３】
メモリ２４０１には、垂直方向と水平方向のそれぞれのスキャン方向時の、削減後の識別情報と画素値が保存される。
【０１６４】
検出部２４０２は、メモリ２４０１から各方向毎の削減後の識別情報を読み出して、識別情報の連続数を検出する。そして、最も連続数が高くなる時のスキャン方向を、出力部２４０３へ出力すると共に、後段のパック部２３０８へ出力する。
【０１６５】
出力部２４０３は、検出部２４０２から入力されたスキャン方向に基づき、そのスキャン方向時の削減後の識別情報をメモリ２４０１から読み出して、後段の符号化部２３０７へ出力する。また、その時の画素値をメモリ２４０１から読み出して、パック部２３０８へ出力する。
【０１６６】
以下、図２４の各構成要素について詳細に説明する。
【０１６７】
検出部２４０２は、メモリ２４０１から、ある方向時の削減後の識別情報を読み出し、削減後の識別情報の“１” 若しくは“０”の識別データが連続する連続数を検出する。識別データは“１”若しくは“０”であるため、注目した識別データが前の識別データと同じかどうかを判断することで、連続数を検出しても良い。そして、ブロック内の全ての画素値の識別情報に関して同様の処理を行い、ある方向時における、ブロック内の連続数の最大値を、検出部２４０２内の図示しないバッファへ保存する。
【０１６８】
上述した処理を、入力された各方向毎の削減後の識別情報に対して同様に行う。そして、バッファに保存した各スキャン方向毎の連続数の最大値を参照し、連続数の最大値が最も大きい時のスキャン方向を出力部２４０３へ出力すると共に、パック部２３０８へ出力する。
【０１６９】
出力部２４０３は、検出部２４０２から入力されたスキャン方向に基づき、そのスキャン方向時の削減後の識別情報をメモリ２４０１から読み出して、後段の符号化部２３０７へ出力する。また、その時の画素値をメモリ２４０１から読み出して、パック部２３０８へ出力する。
【０１７０】
比較部２３０６が処理するデータの一例を、図２５と図２６を用いて具体的に説明する。
【０１７１】
図２５はスキャン方向が水平方向の場合の処理データ例を示した図である。
【０１７２】
検出部２４０２は、画素値８の削減後の識別情報“1111000000000011”をメモリ２４０１から読み出すと、識別データが連続する数をカウントし、カウントした「１０」を、画素値８の連続数として、図示しない検出部２４０２内のバッファへ保持する。次に、画素値７０の削減後の識別情報“1111110000”をメモリ２４０１から読み出すと、識別データが連続する数をカウントし、カウントして得られた値「６」は、連続数の最大値「１０」を超えないのでバッファを更新しない。最後に、画素値５０の削減後の識別情報に関しても同様の処理を行い、これも「１０」を超えないので、更新しない。そして、バッファには、水平方向時の連続数の最大値として「１０」を保持する。
【０１７３】
図２６はスキャン方向が垂直方向の場合の処理データ例を示した図である。
【０１７４】
検出部２４０２は、図２５で説明した処理と同様の処理を各識別情報に対して行う。この時、垂直方向時の各識別情報の連続数は、水平方向時の連続数の最大値「１０」を超えない。そのため、バッファには、水平方向時の連続数の最大値として「１０」が保持される。検出部２４０２は、全スキャン方向の処理が終了すると、バッファに保持された連続数の最大値をとる時のスキャン方向である水平方向を示す信号を、出力部２４０３へ出力すると共に、パック部２３０８へ出力する。
【０１７５】
出力部２４０３は、検出部２４０２から水平方向を示す信号が入力されると、メモリ２４０１に保存された、水平方向時の削減後の識別情報を符号化部２３０７へ出力すると共に、その時の画素値をパック部２３０８へ出力する。パック部部２３０８は、ブロックヘッダに、選択した方向を示す値を格納する点を除き、第１の実施形態と同じである。
【０１７６】
次に、本第６の実施形態における復号化装置について説明する。
【０１７７】
図２７は、本実施形態における復号化装置のブロック構成図である。図２７と図８（第１の実施形態）との違いは、解析部から出力部へスキャン方向を出力する点である。それ以外は第１の実施形態と同様であるので、その詳述は省略する。従って、以降では第１の実施形態と異なる動作についてのみ詳細な説明を行う。
【０１７８】
解析部２７０１は、第１の実施形態で説明した動作に加えて、符号化装置から入力された固定長符号化データ内のブロックヘッダから、スキャン方向を読み取り、読み取ったスキャン方向を出力部２７０４へ出力する。
【０１７９】
出力部２７０４は、入力されたスキャン方向に基づいて画像データを生成し出力する。
【０１８０】
以上説明したように、本第６の実施形態によれば、データ削減後の識別情報の“１”若しくは“０”が最も連続するスキャン方向を選択して、後段の符号化部へ識別情報を出力することができる。このことにより、後段の符号化部で実施する符号化の効率を更に向上させることができる。
【０１８１】
［その他の実施形態］
なお、上記各実施形態では、ブロックの固定長Ｌを５１２ビット、出現色数の上限個数を４とする例を説明したが、これはらユーザが適宜設定できるようにしても良い。また場合によっては、固定長Ｌの制約を外し、可変長としても良い。この場合、１ブロックがｍ×ｎ画素で構成されているとしたとき、２q≧ｍ×ｎを満たす最も小さい整数ｑのビット数をブロックヘッダの出現色数を表わすフィールドに確保した場合、完全な可逆符号化装置として機能させることができる。
【０１８２】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2013255075.tif 000003
【図２】
2013255075.tif 000004
【図３】
2013255075.tif 000005
【図４】
2013255075.tif 000006
【図５】
2013255075.tif 000007
【図６】
2013255075.tif 000008
【図７】
2013255075.tif 000009
【図８】
2013255075.tif 000010
【図９】
2013255075.tif 000011
【図１０】
2013255075.tif 000012
【図１１】
2013255075.tif 000013
【図１２】
2013255075.tif 000014
【図１３】
2013255075.tif 000015
【図１４】
2013255075.tif 000016
【図１５】
2013255075.tif 000017
【図１６】
2013255075.tif 000018
【図１７】
2013255075.tif 000019
【図１８】
2013255075.tif 000020
【図１９】
2013255075.tif 000021
【図２０】
2013255075.tif 000022
【図２１】
2013255075.tif 000023
【図２２】
2013255075.tif 000024
【図２３】
2013255075.tif 000025
【図２４】
2013255075.tif 000026
【図２５】
2013255075.tif 000027
【図２６】
2013255075.tif 000028
【図２７】
2013255075.tif 000029