(57)【要約】【課題】  符号化単位のブロックサイズに応じて、パレット化を行なうか否かの閾値を決定することで、符号化効率を更に向上させる。【解決手段】  ブロック化部２００は、設定されたブロックサイズを単位に画像データを入力し、バッファメモリ２０１に格納する。ヒストグラム作成部２０２は、１ブロック分の画像データの色のヒストグラムを作成する。判定部２０３は、設定されたブロックサイズから閾値を決定し、作成されたヒストグラムに出現する色数と閾値とを比較し、比較結果を置換部２０４に出力する。また、判定部２０３は、色数が閾値以下の場合、ブロック内に出現する各色についてパレット番号を割り当た変換テーブルを作成し、置換部２０４に設定する。置換部２０４は、バッファメモリから１ブロック分に画像データを読込み、符号化部２０５に出力する。但し、判定部２０３から変換テーブルが設定されてる場合には、パレット変換し、その結果を画素データとして符号化部２０５に出力する。【選択図】  図４
2008311792.tif 000002
【特許請求の範囲】
【請求項１】
画像データを符号化し、符号化データを生成する画像符号化装置であって、
符号化単位のブロックのサイズを設定する設定手段と、
設定されたブロックのサイズに応じて閾値を決定する決定手段と、
設定されたサイズのブロックを単位に、画像データを入力する入力手段と、
入力した着目ブロックの色のヒストグラムを作成するヒストグラム作成手段と、
作成されたヒストグラムから、着目ブロック内に出現する色数を算出し、前記決定手段で決定した閾値と前記色数とを比較し、前記色数が前記閾値以下であるかを判定する比較手段と、
前記比較手段で前記色数が前記閾値以下であると判定された場合、前記着目ブロック内に出現する各色にパレット番号を割り当て、着目ブロック内の各画素データをパレット番号に変換する変換手段と、
前記比較手段で前記色数が前記閾値以下と判定された場合、前記変換手段で変換されたパレット番号を画素データとして可逆符号化し、パレット変換したことを示す情報と共に、符号化して得られた符号化データを出力し、
前記比較手段で前記色数が閾値よりも大きいと判定された場合、着目ブロックを構成する各画素データを可逆符号化し、非パレット変換を示す情報と共に、符号化して得られた符号化データを出力する符号化手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記符号化手段は、
前記比較手段で前記色数が前記閾値以下であると判定された場合、前記パレット変換したことを示す情報と、前記着目ブロック内に出現する色数、及び、各パレット番号と画素データとの対応を示すテーブルとを、ブロックヘッダに格納し、前記符号化データを前記ブロックヘッダに後続して格納することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
更に、前記ヒストグラム作成手段で作成されたヒストグラムを、頻度順に並べ替える並べ替え手段を備え、
前記変換手段は、前記並べ替え手段による並べ替え後の順番に従って、各色にパレット番号を割り当てて、パレット変換を行なうことを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
更に、ページ記述言語で記述された印刷データを解釈し、１ページ分の画像データを生成する生成手段を備え、
前記入力手段は、前記生成手段で生成された１ページ分の画像データから、前記ブロック単位の画像データを入力することを特徴とする請求項１乃至３のいずれか１項に記載の画像符号化装置。
【請求項５】
画像データを符号化し、符号化データを生成する画像符号化装置の制御方法であって、
符号化単位のブロックのサイズを設定する設定工程と、
設定された前記ブロックのサイズに応じて閾値を決定する決定工程と、
設定されたサイズのブロックを単位に、画像データを入力する入力工程と、
入力した着目ブロックの色のヒストグラムを作成するヒストグラム作成工程と、
作成されたヒストグラムから、着目ブロック内に出現する色数を算出し、前記決定工程で決定した閾値と前記色数とを比較し、前記色数が前記閾値以下であるかを判定する比較工程と、
前記比較工程で前記色数が前記閾値以下であると判定した場合、前記着目ブロック内に出現する各色にパレット番号を割り当て、着目ブロック内の各画素データをパレット番号に変換する変換工程と、
前記比較工程で前記色数が前記閾値以下と判定された場合、前記変換工程で変換されたパレット番号を画素データとして可逆符号化し、パレット変換したことを示す情報と共に、符号化して得られた符号化データを出力し、
前記比較工程で前記色数が閾値よりも大きいと判定された場合、着目ブロックを構成する各画素データを可逆符号化し、非パレット変換を示す情報と共に、符号化して得られた符号化データを出力する符号化工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項６】
コンピュータが読込み実行することで、前記コンピュータに請求項１乃至４のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項７】
画像データを符号化し、符号化データを生成する画像符号化装置であって、
符号化単位のブロックのサイズを設定する設定手段と、
設定された前記ブロックのサイズに応じて閾値を決定する決定手段と、
設定されたサイズのブロックを単位に、画像データと、当該画像データを構成する各画素が自然画と非自然画のいずれに属するかを示す属性データとを入力する入力手段と、
前記ブロック内の画素数に対する、前記非自然画を示す属性を持つ画素数の比率を算出し、前記比率と前記閾値とを比較する比較手段と、
前記比較手段が前記比率が前記閾値以上であることを示す場合、入力した着目ブロックの色のヒストグラムを作成するヒストグラム作成手段と、
作成されたヒストグラムから、着目ブロック内に出現する各色にパレット番号を割り当て、着目ブロック内の各画素データをパレット番号に変換する変換手段と、
前記比較手段が前記比率が前記閾値以上と判定した場合、前記変換手段で変換されたパレット番号を画素データとして可逆符号化し、パレット変換したことを示す情報と共に、符号化して得られた符号化データを出力し、
前記比較手段が前記比率が前記閾値未満と判定した場合、着目ブロックを構成する各画素データを可逆符号化し、非パレット変換を示す情報と共に、符号化して得られた符号化データを出力する符号化手段と
を備えることを特徴とする画像符号化装置。
【請求項８】
前記符号化手段は、
前記比較手段で前記比率が前記閾値以上であると判定した場合、前記パレット変換したことを示す情報と、前記着目ブロック内に出現する色数、及び、各パレット番号と画素データとの対応を示すテーブルとを、ブロックヘッダに格納し、前記符号化データを前記ブロックヘッダに後続して格納することを特徴とする請求項７に記載の画像符号化装置。
【請求項９】
更に、前記ヒストグラム作成手段で作成されたヒストグラムを、頻度順に並べ替える並べ替え手段を有し、
前記変換手段は、前記並べ替え手段による並べ替え後の順番にパレット番号を割り当てて、パレット変換を行なうことを特徴とする請求項７又は８に記載の画像符号化装置。
【請求項１０】
更に、ページ記述言語で記述された印刷データを解釈し、１ページ分の画像データを生成すると共に、生成する際の各画素の属性データを生成する生成手段を備え、
前記入力手段は、前記生成手段で生成された１ページ分の画像データと属性データから、前記ブロック単の画像データ及び属性データを入力することを特徴とする請求項７乃至９のいずれか１項に記載の画像符号化装置。
【請求項１１】
画像データを符号化し、符号化データを生成する画像符号化装置の制御方法であって、  符号化単位のブロックのサイズを設定する設定工程と、
設定された前記ブロックのサイズに応じて閾値を決定する決定工程と、
設定されたサイズのブロックを単位に、画像データと、当該画像データを構成する各画素が自然画と非自然画のいずれに属するかを示す属性データとを入力する入力工程と、
前記ブロック内の画素数に対する、前記非自然画を示す属性を持つ画素数の比率を算出し、前記比率と前記閾値とを比較する比較工程と、
前記比較工程が前記比率が前記閾値以上であることを示す場合、入力した着目ブロックの色のヒストグラムを作成するヒストグラム作成工程と、
作成されたヒストグラムから、着目ブロック内に出現する各色にパレット番号を割り当て、着目ブロック内の各画素データをパレット番号に変換する変換工程と、
前記比較工程が前記比率が前記閾値以上と判定した場合、前記変換工程で変換されたパレット番号を画素データとして可逆符号化し、パレット変換したことを示す情報と共に、符号化して得られた符号化データを出力し、
前記比較工程が前記比率が前記閾値未満と判定した場合、着目ブロックを構成する各画素データを可逆符号化し、非パレット変換を示す情報と共に、符号化して得られた符号化データを出力する符号化工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１２】
コンピュータが読込み実行することで、前記コンピュータに請求項７乃至１０のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項１３】
請求項６又は１２に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データを符号化する技術に関するものである。
【背景技術】
【０００２】
従来、静止画像の非可逆圧縮方式には、離散コサイン変換を利用したＪＰＥＧ方式や、Ｗａｖｅｌｅｔ変換を利用した方式が多く使われている。また可逆圧縮方式としては、Ｒｕｎｌｅｎｇｔｈ方式、予測符号化を使う方式などが広く知られている。
【０００３】
また、可逆圧縮方式として、Ｐａｋｃｂｉｔｓや国際標準化方式であるＪＰＥＧ−ＬＳ、ＪＰＥＧ２０００符号化方式などが用いられてきた。予測符号化を用いた可逆符号化方式において、符号化効率をあげるためには、予測精度をあげることである。例えば、予測をするために参照する範囲を広くするや、出現した頻度を記録することによって、予測精度を高めて符号化効率をあげることが出来る。
【０００４】
さらに、予測誤差を小さくする方法として、出現画素値がまばらな画像に対して、出現画素値をまとめて、予測誤差を抑えようとする方式が提案されている（例えば、特許文献１）。
【特許文献１】特開２００５−３４８３９０公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
この特許文献１では、出現画素をまとめるための適用レベル数を可変にする事が可能になっているが、この適用レベル数によっては、符号化効率が悪くなることもあり、未だ改善の余地がある。
【０００６】
本発明はかかる問題点に鑑みなされたものであり、ブロックサイズに応じて、パレット化を行なうか否かの閾値を決定することで、符号化効率を更に向上させる技術を提供しようとするものである。
【課題を解決するための手段】
【０００７】
この課題を解決するため、例えば、本発明の画像符号化装置は以下の構成を備える。すなわち、
画像データを符号化し、符号化データを生成する画像符号化装置であって、
符号化単位のブロックのサイズを設定する設定手段と、
設定されたブロックのサイズに応じて閾値を決定する決定手段と、
設定されたサイズのブロックを単位に、画像データを入力する入力手段と、
入力した着目ブロックの色のヒストグラムを作成するヒストグラム作成手段と、
作成されたヒストグラムから、着目ブロック内に出現する色数を算出し、前記決定手段で決定した閾値と前記色数とを比較し、前記色数が前記閾値以下であるかを判定する比較手段と、
前記比較手段で前記色数が前記閾値以下であると判定された場合、前記着目ブロック内に出現する各色にパレット番号を割り当て、着目ブロック内の各画素データをパレット番号に変換する変換手段と、
前記比較手段で前記色数が前記閾値以下と判定された場合、前記変換手段で変換されたパレット番号を画素データとして可逆符号化し、パレット変換したことを示す情報と共に、符号化して得られた符号化データを出力し、
前記比較手段で前記色数が閾値よりも大きいと判定された場合、着目ブロックを構成する各画素データを可逆符号化し、非パレット変換を示す情報と共に、符号化して得られた符号化データを出力する符号化手段とを備える。
【発明の効果】
【０００８】
本発明によれば、符号化単位のブロックサイズに応じて、パレット化を行なうか否かの閾値を決定することで、符号化効率を更に向上させることが可能になる。
【発明を実施するための最良の形態】
【０００９】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１０】
なお、以下では、画像符号化技術を印刷装置に適用する例を説明するが、画像符号化装置単独でも構わないし、他の情報処理装置内に搭載されるものでも構わない。
【００１１】
＜第１の実施形態＞
図２は、本実施形態によるシステム概略図である。図中、１０は印刷装置であり、５０は印刷データを出力するホストコンピュータである。印刷装置１０は、印刷データの受信やレンダリングを行なうプリンタ制御部１１、ハードディスク等の大容量の記憶装置１０５、及び、記録紙上に可視画像を印刷するプリンタエンジン部１１０を有する。プリンタ制御部１１には、各種処理回路が含まれるが、その中には、ＣＰＵ、及びＣＰＵが実行するプログラム、及び、ワークエリアとして使用するメモリが含まれる。また、ホストコンピュータ５０と印刷装置１０は、ネットワークを介して接続されるものとするが、他のインタフェース（例えば、ＵＳＢ）でも構わず、その種類は問わない。また、プリンタエンジン部１１０は、本実施形態では、電子写真方式を採用するものとして説明するが、インクジェット、感熱記録等でも良く、その種類も問わない。また、ホストコンピュータ５０は、例えばパーソナルコンピュータである。ホストコンピュータ５０上では、例えば文書編集アプリケーションプログラムを実行されるものとする。ユーザがホストコンピュータ５０のキーボードやマウス等を用いて印刷指示を行なったとする。このとき、ホストコンピュータ５０のＯＳ（オペレーティングシステム）にインストールされたプリンタドライバがアプリケーションから印刷対象のデータを入力し、印刷装置１０が解釈可能なページ記述言語（ＰＤＬ）で記述した印刷データを生成する。そして、ＯＳを介して、その印刷データが印刷装置１０に送信されてくる。印刷装置１０のプリンタ制御部１１は、ホストコンピュータ５０から受信した印刷データを解釈し、ページ単位にレンダリングし記憶装置１０５に格納しつつ、記憶装置１０５に格納されたレンダリング結果をプリンタエンジン部１１０に出力する。また、印刷装置１０は、他のホストコンピュータからも印刷データを受信可能である。
【００１２】
図１は、主として、実施形態における印刷装置１０のプリンタ制御部１１のブロック構成図である。
【００１３】
図示において、１００はホストコンピュータ５０から受信した印刷データ（ＰＤＬデータ）を解釈し、ビットマップイメージを生成するレンダリング部である。このレンダリング部１００内には、１ページ分の描画メモリと、各画素毎の属性を格納する属性フラグメモリが内蔵されている。そして、ＰＤＬデータで指定された文字コードについては、指定されたフォント種類に従って、不図示のフォントメモリからデータを読出し、文字パターンを生成し、描画メモリへ展開する。また、ＰＤＬデータで指定された線画や各種図形の描画処理も行なう。更に、ＰＤＬデータに自然画等の画像データが含まれる場合には、その画像データの展開処理も行なう。また、レンダリング部１００は、描画メモリへのレンダリング処理を行なう際、該当する画素位置毎にその属性フラグ（文字線画、自然画、ＣＧを識別する情報、有彩色／無彩色を示す情報、網点であるか否かを示す情報の属性）を属性フラグメモリに格納する。この属性フラグメモリは、描画メモリ中の１画素に対して、１バイト（８ビット）単位に属性フラグを記憶管理する。そして、８ビット中の何ビットかを用いて、上記の各属性を表わす。
【００１４】
１０１は圧縮処理用のバッファメモリ、１０２は属性フラグ符号化部、１０３はカラー画像符号化部、１０４は書き込み用のバッファメモリ、１０５はハードディスク装置等の大容量の記憶装置である。１０６は復号処理用のバッファ、１０７は属性フラグ復号部、１０８はカラー画像復号部、１０９は復号された属性フラグ、画像データを展開するためのバッファメモリである。また１１０は画像処理部であり、復号された画像データを属性データを参照した色変換（記録色成分ＣＭＹＫへの変換）、階調補正を行ない、得られたデータをプリンタエンジン１１０に出力する。
【００１５】
上記構成において、印刷データ（ＰＤＬデータ）を不図示のインタフェースを介して受信したとする。この場合、レンダリング部１００はその印刷データを解釈し、ページ単位に画像データの描画（レンダリング）すると共に、その際に属性フラグメモリに該当する画素位置の属性フラグを格納する。なお、レンダリングする際には、各画素はＲＧＢの色空間であって、１成分は８ビットであるものとする。この色空間、ビット数は一例であり、他の色空間でも構わない。
【００１６】
１ページ分の画像データ及び属性フラグの格納が完了すると、レンダリング部１００は、バッファメモリ１０１にそのデータを出力する共に、次ページのレンダリング処理を開始する。
【００１７】
画像符号化処理部１０３はバッファメモリに格納された画像データを、属性フラグ符号化部１０２はバッファメモリに格納された属性フラグをそれぞれ符号化する。生成された符号化画像データ及び符号化属性フラグは、バッファメモリ１０４を介して、記憶装置１０５にそれぞれファイルとして格納される。
【００１８】
一方、属性フラグ復号部１０７、及び、画像復号処理部１０８は、プリンタエンジン部１１１の印刷出力処理に同期して、記憶装置１０５に格納された符号化画像データファイル、符号化属性フラグファイルをバッファメモリ１０６に読込む。そして、それぞれが、復号処理を行ない、復号結果をバッファメモリ１０９に格納する。画像処理部１１０は、復号された属性フラグを参照し、復号された画像データ（ＲＧＢデータ）から、属性に応じたＹＭＣＫ色空間への変換、補正処理を行ない、プリンタエンジン部１１１の印刷処理に同期して出力する処理を行なう。
【００１９】
上記の結果、画像及び属性フラグの符号化処理と、その復号処理は、記憶装置１０５を介在させることで、互いに非同期にできる。従って、レンダリング部１００、画像符号化部１０３、属性フラグ符号化部１０２は、プリンタエンジン部１１１の印刷速度とは無関係に、各ページの画像及び属性フラグを符号化できる。この結果、ホストコンピュータ５０は、本実施形態の印刷装置１０への印刷データの出力処理から素早く解放される。また、本印刷装置は、不図示の他のコンピュータからの印刷データの受信に対処することも可能となる。
【００２０】
次に、上記構成を備えた本実施形態の印刷装置１０における制御部１５０の符号化処理を、図３のフローチャートを参照して以下に説明する。
【００２１】
ホストコンピュータ５０より印刷ジョブ（ＰＤＬデータ）を受信すると、まず、ステップＳ１１にて、レンダリング部１００は、ＰＤＬ解析を行なう。そして、ステップＳ１２にて、レンダリング部１００は、ＰＤＬに基づいてレンダリングすることによりビットマップイメージを生成する。また、レンダリング部１００は、ステップＳ１３にて、ＰＤＬ解析時に各画素毎の属性情報を得て属性フラグを生成し、属性メモリに格納する。なお、レンダリング処理と、属性フラグの生成及び格納は、並列的に行われる。
【００２２】
このように、レンダリング部１００は、ホストコンピュータ５０から受信したＰＤＬで記述された印刷データを解析し、その中に含まれるＰＤＬコマンドを解釈してプリントのための画像（ビットマップイメージ）を生成する。このとき、ＰＤＬコマンドにおけるコマンドの種別を示す情報を参照して、各画素の属性を判定し、それを属性フラグとして属性フラグメモリに格納する。
【００２３】
１ページ分のレンダリングが完了すると、レンダリングされたビットマップイメージは画像符号化処理部１０３によって可逆圧縮符号化（本実施形態では、ＪＰＥＧ―ＬＳを採用した）に従って符号化が行われる（ステップＳ１４）。一方、属性フラグデータは符号化器１０２によって可逆圧縮される（ステップＳ１５）。属性フラグデータの符号化としては、ランレングス符号化を用いるものとするが、他の符号化技術（例えば予測符号化、パックビッツ符号化等）でも構わない。そして、それぞれで生成された符号化データは、バッファ１０４を介して、記憶装置１０５に格納される（ステップＳ１６）。
【００２４】
上記処理における、属性フラグ符号化部１０２については、１ページ分の属性フラグをラスタースキャンし、ランレングする符号化するだけであるので、その説明については省略する。以下では、実施形態における画像符号化処理部１０３について更に詳細に説明する。
【００２５】
図４は、実施形態における画像符号化処理部１０３の詳細ブロック構成図を示している。
【００２６】
画像符号化装置部１０３は、図示の如く、ブロック化部２００、バッファメモリ２０１、ヒストグラム作成部２０２、判定部２０３、置換部２０４、及び、符号化部２０５とを備える。以下、同図に従って、実施形態の画像符号化処理部１０３の処理内容を説明する。
【００２７】
制御部１５０は、操作部１５１からの指示、もしくは印刷データ中に格納された制御情報に従い、画像データの符号化単位であるブロックサイズ（ｍ×ｎ画素のｍ、ｎ）を特定する制御信号を生成する。そして、制御部１５０は生成した制御信号を、１ページの符号化処理に先立って、画像符号化処理部１０３に出力する。なお、操作部１５１から指示されたブロックサイズと、印刷データに含まれる制御情報で特定されるブロックサイズが異なる場合もありえる。制御部１５０は、印刷データ中に、ブロックサイズを指定するコマンドが含まれていれば、それに従って符号化単位のブロックサイズを決定する。また、印刷データ中にブロックサイズを指定するコマンドが存在しなかった場合には、操作部１５１から指示されたサイズを符号化単位のブロックサイズとして決定する。
【００２８】
ブロック化部２００は、バッファメモリ１０１（図１参照）から、制御部１５０からの上記制御信号に従ったサイズのブロック（ｍ×ｎ画素分）の画像データ（以下、ブロックデータという）を読込み、バッファ２０１に格納する。なお、ブロック化部２００が読込むブロックの順序は、ブロックを単位とするラスタースキャン順とする。
【００２９】
ヒストグラム作成部２０２は、バッファメモリ２０１に格納されたブロックデータのヒストグラム情報（色毎の出現頻度）を作成し、その作成されたヒストグラムの情報を判定部２０３に出力する。
【００３０】
判定部２０３は、内部に閾値記憶部としてのルックアップテーブルを内蔵し、制御部１５０からの制御情報で示されるブロックサイズに基づき閾値Ｔｈをそのルックアップテーブルから読込む。また、判定部２０３は、ヒストグラム作成部２０２からのヒストグラム情報に基づき、着目ブロック内に出現する色の数Ｎｃを算出する。そして、判定部２０３は、その算出した色数Ｎｃと閾値Ｔｈとを比較し、色数Ｎｃは閾値Ｔｈ以下であるか否かを判定し、その判定結果に応じて以下の処理を行なう。
・色数Ｎｃが閾値以下の場合；
判定部２０３は、置換部２０４、符号化部２０５に、置換処理を有効にする信号（色数≦閾値Ｔｈであることを示す信号でもある）を出力する。そして、判定部２０３は、着目ブロック内に出現する頻度の大きい順に色を並べ替える。そして、判定部２０３は、並べ替え後の各色データ（ＲＧＢの値）と、０、１、２、…、Ｎｃ−１のパレット番号を対にして、図５に示すように変換テーブル（以下、パレット変換テーブル）を作成し、置換部２０４及び符号化部２０５に出力する。
・色数Ｎｃが閾値よりも大きい場合；
判定部２０３は、置換部２０４に対して置換処理を無効にする信号（色数＞閾値Ｔｈを示す信号でもある）を出力する。
【００３１】
置換部２０４は、制御部１５０からの制御信号で示されるブロックサイズ毎にバッファメモリ２０１からブロックデータを読込み、置換処理を行ない、符号化部２０５に出力する。より具体的には、次の通りである。
【００３２】
判定部２０３からの信号が、置換処理無効を示す場合、置換部２０３は、バッファメモリ２０１に格納された着目ブロック内をラスタースキャンして各画素データを読込み、その読込んだ画素データをそのまま符号化部２０５に出力する。
【００３３】
一方、判定部２０３からの信号が置換処理を有効を示す場合、置換部２０４は判定部２０３からのパレット変換テーブルを内部の書き込み可能なメモリにルックアップテーブルとして格納する。そして、置換部２０４は、バッファ２０１に格納された着目ブロックのラスタースキャンして各画素データを読込み、読込んだ画素データをルックアップテーブルを用いてパレット番号に変換する。また、置換部２０４は、その変換後のデータ（パレット番号）を、ＲＧＢのうちの１つの成分（実施形態ではＲ成分とする）のデータとして符号化部２０５に出力する。また、置換部２０４は、他の成分（Ｇ、Ｂ成分）用のバスにはダミーとして“０”を出力する。
【００３４】
次に符号化部２０５について説明する。
【００３５】
符号化部２０５は、１つの画像の符号化に先立ち、ファイルヘッダを生成し、出力する。このファイルヘッダには、符号化対象の画像データのサイズ（水平、垂直方向の方向画素数）、色空間の種別、各成分のビット数、ブロックのサイズを特定する情報等、復号処理に必要な情報が格納される。符号化部２０５は、ブロック単位に符号化する際には次の処理を行なう。
【００３６】
符号化部２０５は、判定部２０３から置換処理無効を示す制御信号を受信した場合、置換無し（非パレット変換）を示す識別情報（例えば“０”）を格納したブロックヘッダを出力する。また、判定部２０３から置換処理有効を示す制御信号を受信した場合、置換色有り（パレット変換）を示す識別情報（例えば“１”）、及び、パレット変換テーブルを格納したブロックヘッダを生成し出力する。なお、ブロックヘッダに格納するパレット変換テーブルには、色数Ｎｃと、各色成分値で構わない。理由は、各色に対するパレット番号が、０、１、…、Ｎｃ−１となっていることが約束されているためである。図１０は、実施形態における符号化部２０５が生成する符号化データファイルの構造を示している。１つのブロックの符号化データは、図示の参照番号３０１、３０２のいずれかのタイプである。
【００３７】
この後、符号化部２０５は、置換部２０４から出力されるラスタースキャン順の各画素データ（カラー画像データ）をＪＰＥＧ−ＬＳ符号化方法に従って可逆符号化し、符号化データを生成する。そして、符号化部２０５は、生成した符号化データを、先に示したブロックヘッダに後続するデータとして出力する。
【００３８】
図６は実施形態における符号化部２０５の詳細ブロック構成図である。符号化部２０５は、図示のように、コンテクスト生成部２５１、予測補佐生成部２５２、予測誤差符号化部２５３、ランレングス変換部２５４、ランレングス符号化部２５５、及び、セレクタ２５６を有する。
【００３９】
先に説明したように、符号化部２０５はＪＰＥＧ−ＬＳ符号化方法に従って、入力した画像データを可逆符号化する。ＪＰＥＧ−ＬＳは、ブロック内をラスタースキャン中、図７に示すように、着目画素Ｘの近傍の既に符号化済み近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄの色からコンテクスト値を算出する。そして、その算出したコンテクスト値に従い、予測符号化するか、ランレングス符号化するのかを決定する。なお、着目ブロックがブロックの先頭ライン上にあるとき、又は、着目画素位置がラインの左端、右端位置である場合、近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄの全部、もしくは一部はブロック外の位置になってしまう。このようなブロック外の画素の各成分値は“０”であるものとして符号化処理を行なうものとする。なお、ここではブロック外の画素の成分値を“０”としているが、復号処理と同じにすればよいわけであるから、必ずしも“０”でなくても構わない。
【００４０】
さて、図６に示すように、コンテクスト生成部２５１は、着目画素Ｘの近傍画素の画素データを参照するため、内部に２ライン分のメモリを有する。そして、コンテキスト生成部２５１は、着目画素Ｘの近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄを内部メモリから読込み、着目画素Ｘにおけるコンテクス値を算出する。そして、そのコンテクスト値に基づき、コンテクスト生成部２５１は、着目画素Ｘをランレングする符号化すべきか、予測誤差符号化すべきかを判定し、入力した着目画素Ｘを予測誤差算出部２５２、ランレングス変換部２５４のいずれかに出力する。
【００４１】
実施形態では、簡単なものとするため、近傍画素Ｘａ＝Ｘｂ＝Ｘｃ＝Ｘｄを満たか否か、すなわち、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝で表わされる色数が“１”であるか否かを示す情報をコンテクスト値とする。
【００４２】
近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝で合わされる色数が“１”以外（２以上）である場合、コンテクスト生成部２５１は、着目画素Ｘを予測符号化するため、着目画素Ｘの各画素成分値を予測誤差算出部２５２に出力する。
【００４３】
また、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝で合わされる色数が“１”である場合、着目画素Ｘがその直前の画素Ｘａと同色である確率が非常に高い。従って、コンテクスト生成部２５１は、着目画素Ｘからランレングス符号化を開始するため、着目画素Ｘの各画素成分値をランレング変換部２５４に出力する。
【００４４】
なお、一旦、着目画素Ｘをランレングス変換部２５４に出力した場合、着目画素Ｘに後続して同じ画素が入力さてる限り、コンテクスト値の算出は行なわず、入力される画素データをランレングス変換部２５４に出力する。
【００４５】
また、ランレングス符号化処理中、着目画素Ｘがその直前の画素Ｘａと非同一色となった場合、或いは、着目画素Ｘはブロック右端に到達した場合、コンテクスト生成部２５１はランが終端したと判定する。そして、ラン終端を示す信号をランレングス変換部２５４に通知し、着目画素Ｘのコンテクスト値の算出も行なう。
【００４６】
予測誤差算出部２５２は、着目画素Ｘの近傍画素｛Ｘａ，Ｘｂ，Ｘｃ｝から、着目画素の各成分の予測値を算出し、その各成分の予測値と、着目画素の各成分値との差を算出し、予測誤差符号化部２５３に出力する。実施形態では、簡単のため、近傍Ｘａの各成分値が着目画素の各成分値の予測値として用いるものとする。予測誤差符号化部２５３は、着目画素の各成分の予測誤差に対してハフマン符号化、もしくは、算術符号化等の手法を利用して符号語を生成し、セレクタ２０５に出力する。
【００４７】
また、ランレングス変換部２５４は、コンテクスト生成部２５１から、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝で表わされる色数が“１”であることを示す信号を入力すると、ランの計数を開始する。そして、ランレングス変換部２５４は、ランをカウント中に、コンテクスト生成部２５１から、着目画素Ｘがその直前の画素Ｘａと非同一色となった、着目画素Ｘはブロック右端に到達したことを示す信号を受信した場合、ランの計数を終了する。そして、それまでカウントした値をランレングス符号化部２５５に出力する。ランレングス符号化部２５５は、ランレングス変換部２５４から入力したカウントした値に対応する符号語を生成し、セレクタ２５６に出力する。
【００４８】
セレクタ２５６は、コンテクスト生成部２５１によって、着目画素についてランレングス符号化を中か、予測誤差符号化中かを示す信号を受信する。従って、セレクタ２５６は、その受信する信号に従い、予測誤差符号化部２５３、ランレングス符号化部２５５のいずれか一方からの符号化データを選択し、出力する。なお、予測誤差符号化部２５３は、１画素単位に符号化データを出力するのに対し、ランレングス符号化部２５５は１つのランがラン終端になって初めて符号化データを出力することになる。それ故、セレクタ２５６は各タイミングに応じて入力、出力の制御を行なうことになる。
【００４９】
以上実施形態における符号化に係る構成とその処理を説明した。ここで、ブロック内に出現する色の数Ｎｃが、そのブロックのサイズによって決まる閾値Ｔｈ以下の場合にパレット化する理由を以下に説明する。
【００５０】
１つのブロック内に出現する色の数Ｎｃが閾値Ｔｈ以下というのは、そのブロック内に出現する色が、比較的少なくいことを意味する。色数が少ない場合、各色の差が大きくなる確率が高い傾向にある。特に、ＣＧ（コンピュータグラフィックス）の場合に、ブロック内の色数は比較的少なく、この傾向が強い。
【００５１】
説明を単純なものとするため、モノクロ画像（明度の濃淡画像）を例にして説明する。図８（ａ）は、ブロック内に出現する画素値が４種類｛Ｃ１、Ｃ２、Ｃ３、Ｃ４）であり、それぞれの頻度がＣ１＞Ｃ２＞Ｃ０＞Ｃ４の順番になっている例を示している。
【００５２】
予測誤差符号化する場合、着目画素値（ここでは明度）と、その近傍の符号化済みの画素値（予測値）との差分を算出し、その差分に応じた符号語を生成する。一般に、差分が小さい確率が高いから、差分が小さい場合には短い符号語を生成し、差分値が大きくなるにしたがって長い符号語を生成している。
【００５３】
しかしながら、図８（ａ）に示すような状態の場合、同じ画素値であれば差分値が“０”となるものの、異なる画素値の差分値は、無視できない程大きな値になってしまう。仮に、画素値Ｃ０、Ｃ１間の距離が“５０”とするなら、差分が１乃至４９までの符号語は未使用となり、高い符号化効率は望めない。
【００５４】
そこで、実際に出現する各画素の値を、０で始めるシーケンシャルなパレット番号を割り当てる。この結果、図８（ａ）のヒストグラムを、図８（ｂ）のヒストグラムに変換できる。このパレット番号を画素値と見立てれば、色Ｃ０、Ｃ１、Ｃ２、Ｃ３はパレット番号０、１、２、３に置き換えられる。従って、このパレット番号を用いれば、予測誤差の絶対値は最大でも“３”であることが約束され、高い符号化効率が期待できる。
【００５５】
更に、本実施形態では、ＣＧの場合、画素値Ｃ０、Ｃ１、Ｃ２、Ｃ３の画素がランダムに配置される確率が低く、Ｃ０→Ｃ１→Ｃ２→Ｃ３（又はその逆）の画素値を持つ領域が連続する確率が高いことを確かめた。換言すれば、予測誤差を算出する際、着目画素の画素値がＣ０である場合、その予測値がＣ０となる確率が一番高く、次いで、Ｃ１、Ｃ２、Ｃ３の順番になる。また、着目画素がＣ１である場合、予測値がＣ１なる確率が一番高く、その次に｛Ｃ０、Ｃ２｝、次いで、Ｃ３の順番になる。
【００５６】
上記をまとめると、出現頻度順にパレット番号を割り当てると、予測誤差を小さくできる確率を更に高めることができることに他ならない。そこで、本実施形態では、図８（ａ）のようなヒストグラムが作成された場合、図８（ｂ）ではなく、更にその頻度をキーにして色データを並べ替え、図８（ｃ）のヒストグラムを作成する。そして、その並べ替え後の画素値にパレット番号を割り当てる。判定部２０３が、着目ブロック内に出現する頻度の大きい順に色を並べ替え、並べ替え後の各色データ（ＲＧＢの値）と、０、１、２、…、Ｎｃ−１のパレット番号を対にして、図５に示すようなパレット変換テーブルを作成したのは、上記理由によるものである。なお、図８（ｃ）は頻度をキーにして降順に並べ替える例を示したが、昇順でも構わない。
【００５７】
上記処理を行なうため、図３のステップＳ１４の処理の詳細を示すと図１１のようになる。
【００５８】
先ず、制御部１５０は、ステップＳ２１において、ブロックのサイズを決定する。この処理では、ステップＳ１１（図３）のＰＤＬデータの解析処理によって、印刷データ中にブロックサイズの指定があった場合には、その指定されたサイズに従う。また、印刷データ中にそのブロックサイズの指定がなかった場合には、操作部１５１で設定されたサイズに従う。また、ステップＳ２１では、ブロックサイズによって、色数判定のための閾値を決定する処理も行なう。
【００５９】
この後、ステップＳ２２にて、画像符号化処理部１０３のブロック化部２００は、決定したサイズのブロックデータを、バッファメモリ１０１から読込み、バッファメモリ２０１に格納する。ステップＳ２２３にて、ヒストグラム作成部２０２は、バッファメモリ２０１に格納されたブロックをスキャンし、ヒストグラムを作成し、作成したヒストグラムに関する情報を判定部２０３に出力する。
【００６０】
ステップＳ２４では、判定部２０３は、入力したヒストグラム情報に基づき、出現する色数を算出する。そして、判定部２０３は、ステップＳ２５にて、算出した色数が、制御部１５０より設定された閾値以下であるか否かを判定する。算出した色数が、閾値よりも大きいと判断した場合には、判定部２０３は算出した色数が閾値よりも大きいことを示す制御信号を置換部２０４、及び、符号化部２０５に出力する。この結果、符号化部２０５は、ステップＳ２６にて、パレット変換無しを示す識別情報を持つブロックヘッダを生成し、出力する。また、置換部２０４は、バッファ２０１内の階調画像データをそのまま符号化部２０５に出力することになる。従って、符号化部２０５は、ステップＳ３０にて、入力した階調画像データをそのまま符号化し、生成された符号化データを出力する。
【００６１】
一方、判定部２０３が、ステップＳ２５にて、色数が閾値以下であると判定した場合、処理はステップＳ２７に進む。このステップＳ２７では、判定部２０３が、ヒストグラムの色を、頻度順に並べ替え、並べ替え後の色に対してパレット番号を符番し、パレット変換テーブルを作成する。そして、判定部２０３は算出した色数が閾値以下であることを示す信号、及び、生成されたパレット変換テーブルの情報を、置換部２０４、及び、符号化部２０５に出力する。
【００６２】
符号化部２０５は、これらの情報を入力した場合、パレット変換を行なったことを
示す識別情報、及び、色数、各色の成分のデータを含むブロックヘッダを生成し、出力する（ステップＳ２８）。
【００６３】
また、置換部２０４は、バッファ２０１内の階調画像データを、パレット番号に置換し、その置換後のデータを符号化部２０５に出力する（ステップＳ２９）。従って、符号化部２０５は、ステップＳ３０にて、入力したパレット化したデータを符号化し、生成された符号化データを出力することになる。
【００６４】
ステップＳ３０の処理を終えると、ステップＳ３１に進み、制御部１５０は、全ブロックの符号化が終了したのか否かを判定する。否の場合には、次のブロックの符号化を行なうため、ステップＳ２２以降の処理を行なう。また、全ブロックの符号化処理が行なったと判定した場合、着目ページの符号化処理を終了する。
【００６５】
以上、本実施形態における符号化処理について説明したが、次に復号処理について説明する。属性フラグ復号部１０７については説明するまでもないので、以下では画像復号処理部１０８について説明する。
【００６６】
図９は画像復号処理部１０８のブロック構成図である。画像復号処理部は、ヘッダ解析部２７０、コンテクスト生成部２７１、予測誤差復号部２７２、ランレングス復号部２７３、セレクタ２７４、置換部２７５、及び、メモリ２７６を有する。
【００６７】
メモリ２７６は、１ブロック中の少なくとも着目画素Ｘの近傍画素の復号結果を２ライン分格納する容量を有する。また、１ブロック分の復号開始時には、このメモリ２７６はゼロクリアされる。これは、ブロック外の画素値の各成分値を“０”とするためである。
【００６８】
ヘッダ解析部２７０は、符号化ブロックデータのブロックヘッダの識別情報を解析し、注目ブロックがパレット番号に置換後に符号化されているか否かの判定、及び、パレット番号に変換されている場合にはその色の数と、画素値とを抽出する処理を行なう。そして、パレット番号の符号化データであると判定した場合、パレット番号の符号化データであることを示す制御信号を置換部２７５に出力する。また、ブロックヘッダに格納されている画素値とパレット番号（色の数によって幾つの画素値が存在するのかは容易にわかる）とを対にして、置換部２７５に出力する。また、着目ブロックが階調画像として符号化されていると判定した場合には、階調画像の符号化であることを示す制御信号を置換部２７５に出力する。この後、ヘッダ解析部２７０は、ブロックヘッダに後続する符号化データをコンテクスト生成部２７１に出力する。
【００６９】
コンテクスト生成部２７１は、着目画素Ｘを復号する際、メモリ２７０を参照し、近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄからコンテクスト値を算出する。そして、コンテクスト生成部２７１は、この算出結果に基づき、着目画素Ｘがランレング符号化されているのか、予測誤差符号化されているのかは判定する。実施形態では、４つの近傍画素で示される色数が２以上の場合には予測符号化、色数が１の場合にはランレングス符号化されていると判定する。着目画素が予測誤差符号化されていると判定した場合（近傍画素が２色以上の場合）、コンテクスト生成部２７１は符号化データを予測誤差復号部２７２に出力する。また、着目画素がランレングス符号化されていると判定した場合（近傍画素が１色の場合）、コンテクスト生成部２７１は符号化データをランレングス復号部２７３に出力する。また、コンテキスト生成部２７１は、符号化種別の判定結果を制御信号としてセレクタ２７５にも出力する。
【００７０】
予測誤差復号部２７２は、符号化データから予測誤差に復号する。そして、予測誤差復号部２７２は、メモリ２１０を参照し、着目画素Ｘの予測値を算出し、その予測値に、復号した予測誤差を加算することで、着目画素Ｘの１つの成分値を復号し、セレクタ２７４に出力する。そして、この処理を残りの２成分についても同様に行なうことで、１画素分の復号が完了する。
【００７１】
また、ランレングス復号部２７３は、ランを復号し、そのランをセレクタ２７５に出力する。
【００７２】
セレクタ２７５は、着目画素が予測誤差符号化されていることを示す制御信号を入力した場合には、予測誤差復号部２７２からの復号結果を置換部２７５に出力すると共に、メモリ２７６に格納する。また、セレクタ２７５は、着目画素がランレングス符号化されていることを示す制御信号を入力した場合には、ランレングス復号部２７３から入力したランの直前の画素の値を、ランで示される個数分だけ、置換部２７５、及び、メモリ２７６に出力する。
【００７３】
置換部２７５は、ヘッダ解析部２７０から、注目ブロックが階調画像データのまま符号化されていることを示す制御信号を入力した場合には、セレクタ２７４からの画素値をそのままバッファメモリ１０９に出力する。
【００７４】
一方、ヘッダ解析部２７０から、注目ブロックがパレット番号に変換した後に符号化されていることを示す制御信号と、パレット番号と画素値とを入力したとする。この場合、置換部２７５は、セレクタ２７４からの画素値のＲ成分のみを着目し、そのＲ成分の値がパレット番号であるものとし、該当する画素値で置換し、出力する。
【００７５】
以上説明したように本実施形態によれば、画像をブロック単位に符号化する際、そのブロック中に出現する色の数に応じて、画像データをパレット番号に変換して符号化するか否かを切り替えることで、高い圧縮率で可逆符号化することが可能になる。
【００７６】
＜第２の実施形態＞
上記実施形態では、パレット化するか否かの閾値をブロックサイズによって決定した。パレット化して符号化効率の上がる画像は、文字線画及びコンピュータグラフィクスである。そこで、ブロックサイズに加え、更に、ブロック内の各画素の属性フラグを参照して、パレット化するか否かを決定するようにしても良い。
【００７７】
１つの属性フラグは１つの画素に対して生成されるものである。従って、ブロックのサイズがｍ×ｎの場合、属性フラグの個数もｍ×ｎ個である。そこで、文字線画の属性フラグ＋ＣＧの属性フラグ（非自然画の属性を持つ画素数）の個数をＭとしたとき、その比率Ｍｒを次式によって算出する。
Ｍｒ＝１００×Ｍ／（ｎ×ｍ）
そして、Ｍｒが予め設定された閾値Ｔｈ１を以上の場合、着目ブロックをパレットするものとして決定する。
【００７８】
図１２は、本第２の実施形態における画像符号化処理部１０３のブロック構成図である。図４と異なる点は、ブロック化部２００は、制御部１５０からの制御信号によって決定されたサイズの画像データと、そのサイズ分の属性フラグデータをバッファメモリ１０１から入力し、バッファメモリ２０１に格納する点である。また、図４の構成に、比率算出部２０６を設けた点、及び、判定部２０３の処理内容が変更された点も異なる。
【００７９】
比率算出部２０６は、バッファメモリ２０１に格納された１ブロック分の属性フラグデータを参照し、文字線画、又は、コンピュータグラフィックスの属性を持つ画素数Ｍをカウントする。そして、制御部１５０からの制御信号で特定されたブロックサイズ（ｍ×ｎ）に対するＭの比率Ｍｒを算出し、その結果を判定部２０３に出力する。
【００８０】
判定部２０３は、ブロックサイズに従って閾値Ｔｈ１を決定する。そして、算出した比率が閾値以上であるか否か、すなわち、Ｍｒ≧Ｔｈ１を満たすか否かを判定し、その判定結果を置換部２０４、符号化部２０５に出力する。そして、特に、Ｍｒ≧Ｔｈ１の場合、着目ブロックの各画素データをパレット変換するため、ヒストグラムを作成し、パレット変換テーブルを作成する。そして、作成したパレット変換テーブルを置換部２０４、符号化部２０５に出力する。また、算出した比率が閾値未満の場合には、パレット変換は行なわない。
【００８１】
この後の処理は、第１の実施形態と同様である。なお、符号化データのデータ構造については特に変更はない。また、復号処理は第１の実施形態と同じで良い。
【００８２】
以上説明したように本第２の実施形態によっても、第１の実施形態と同様の作用効果を奏することが可能になる。
【００８３】
＜第３の実施形態＞
第１、第２の実施形態では、置換部２０４がパレット変換を実行した際、そのパレット番号の情報を転送するバスを１色成分（実施形態ではＲ成分）を用い、他の成分（実施形態ではＧ、Ｂ成分）のバスには“０”をであるものとして符号化した。パレット変換した場合、Ｇ、Ｂ成分は０であるので、Ｇ、Ｂ成分の符号化データは効率の良いライレングス符号化されることになるが、それでも、Ｇ、Ｂの各成分はライン単位に符号化データが生成されることに変わりはない。そこで、パレット変換する場合、１つの成分しか利用しないわけであるから、そのパレット番号の符号化データのみを出力し、他の２つの成分の符号化データは出力しないようにしても構わない。このようにすると、更に圧縮率を高めることが可能になる。
【００８４】
また、上記実施形態では、印刷装置に適用する例を示した。印刷装置であるため、符号化処理を行なう構成と、復号処理を行なう構成が１つの装置内に存在することになる。しかしながら、それぞれ単独の装置に適用しても構わない。例えば、パーソナルコンピュータ等の情報処理装置で画像を符号化し、他の情報処理に装置にそれを転送し、そこで復号する場合にも適用できよう。また、パーソナルコンピュータ等の情報処理装置の場合、当然、上記各処理部に相当する部分を、コンピュータプログラムの関数やサブルーチンで機能させ、各バッファはＲＡＭに確保して利用することになる。従って本発明はコンピュータプログラムをもその範疇とする。更に、通常、コンピュータプログラムはＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されており、それを装置の読取部（ＣＤ−ＲＯＭドライブ等）にセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、本発明はかかるコンピュータ可読記憶媒体をもその範疇とすることも明らかである。
【００８５】
また、実施形態では、画像データの符号化処理に、ＪＰＥＧ−ＬＳを用いる例を説明したが、予測誤差符号化のみを利用しても構わないので、必ずしもＪＰＥＧ−ＬＳを必須とはしない。
【図面の簡単な説明】
【００８６】
【図１】実施形態におけるプリンタ制御部のブロック構成図である。
【図２】実施形態における印刷システムのブロック構成図である。
【図３】実施形態における画像符号化処理のメインルーチンを示すフローチャートである。
【図４】第１の実施形態の画像符号化処理部のブロック構成図である。
【図５】判定部が生成するパレット変換テーブルの例を示す図である。
【図６】図４の符号化部のブロック構成図である。
【図７】着目画素Ｘとのその近傍画素との相対位置関係を示す図である。
【図８】ヒストグラムからパレットへの変換処理を説明するための図である。
【図９】実施形態における画像復号処理部のブロック構成図である。
【図１０】実施形態の画像符号化処理部が生成する符号化画像データのファイルの構造を示す図である。
【図１１】図３のステップＳ１４の詳細を示すフローチャートである。
【図１２】第２の実施形態の画像符号化処理部のブロック構成図である。
【図１】
2008311792.tif 000003
【図２】
2008311792.tif 000004
【図３】
2008311792.tif 000005
【図４】
2008311792.tif 000006
【図５】
2008311792.tif 000007
【図６】
2008311792.tif 000008
【図７】
2008311792.tif 000009
【図８】
2008311792.tif 000010
【図９】
2008311792.tif 000011
【図１０】
2008311792.tif 000012
【図１１】
2008311792.tif 000013
【図１２】
2008311792.tif 000014