(57)【要約】【課題】  本発明は、デジタル画像のセルベースの圧縮方法を提供することができる。【解決手段】  ｍ×ｎ画素セルを、各画素が色値を有する入力画像から得る（１０００）。画素セルの最も低い色値と、最も高い色値と、を決定し、セルの特徴を判断する（１００２）。最も高い色値と最も低い色値との差を算出する（１００４）。差が閾値差以下である場合、最も高い色値と最も低い色値との間の出力色値を選択し、出力色値の第１の表現を出力媒体に書き込む（１００８）。差が閾値差より大きい場合、複数の出力色値を選択し、複数の出力色値の第２の表現を出力媒体に書き込む（１０１０）。【選択図】  図１０
2013258701.tif 000002
【特許請求の範囲】
【請求項１】
方法は、以下を含む：
コンピュータにより、ｍ×ｎ以上の画素を含む入力画像から、画素のそれぞれが色値を有するｍ×ｎ画素セルを得る工程と、
前記コンピュータにより、前記ｍ×ｎ画素セルにおける最も高い色値と、最も低い色値と、を決定する工程を含む、前記ｍ×ｎ画素セルの特徴を判断する工程と、
前記コンピュータにより、前記最も高い色値と前記最も低い色値との間の差を算出する工程と、
前記差が閾値差以下である場合、前記コンピュータにより、前記最も高い色値と、前記最も低い色値との間に含まれる色値から、１の出力色値を選択し、単色オペコードと、前記出力色値の表示と、を含む、前記出力色値の第１の表現を出力媒体に書き込む工程と、
前記差が前記閾値差より大きい場合、前記コンピュータにより、複数の出力色値を選択し、前記複数の出力色値の第２の表現を前記出力媒体に書き込む工程。
【請求項２】
前記ｍ×ｎ画素セルは、前記入力画像の単一のカラーチャンネルのみにおける複数の色値と関連付けられている請求項１に記載の方法。
【請求項３】
前記複数の出力色値は、２つの出力色値から構成されており、
前記第２の表現は、
２色オペコードと、
前記２つの出力色値のそれぞれの表示と、
前記ｍ×ｎ画素セルの各画素を、前記２つの出力色値のうちの１つと関連付ける前記ｍ×ｎ画素セルの画素ごとのビットマップと、
を含む、請求項１または２に記載の方法。
【請求項４】
前記特徴を判断する工程は、
前記ｍ×ｎ画素セルにおける色値のヒストグラムを決定する工程と、
前記ヒストグラムから、前記ｍ×ｎ画素セル内の色値のうち、前記最も低い色値からある閾値の範囲内にある２番目に低い色値と、前記最も高い色値から前記ある閾値の範囲内にある２番目に高い色値と、を取得する工程と、
前記ヒストグラムから、前記ｍ×ｎ画素セルには、前記最も低い色値と、前記２番目に低い色値と、前記２番目に高い色値と、前記最も高い色値と、以外の色値が存在しないと判断する工程と、
を含み、
前記複数の出力色値を選択する工程は、前記最も低い色値と前記２番目に低い色値とのうちの１つと、前記２番目に高い色値と前記最も高い色値とのうちの１つと、を選択する工程を含む、請求項３に記載の方法。
【請求項５】
前記複数の出力色値は、最大４つの出力色値からなり、
前記第２の表現は、
４色オペコードと、
前記最大４つの出力色値の各々の表示と、
前記ｍ×ｎ画素セル内の各画素を、前記最大４つの出力色値のうちの１つと関連付けるｍ×ｎ画素セルの画素ごとのビットマップと、
を含む、請求項１または２に記載の方法。
【請求項６】
前記特徴を判断する工程は、
前記ｍ×ｎ画素セルの色値のヒストグラムを決定する工程と、
前記ヒストグラムから、前記最も低い色値と前記最も高い色値との間にそれぞれ存在する第１の中間色値と、第２の中間色値とを取得する工程と、
前記ヒストグラムから、
前記最も低い色値と、
前記第１の中間色値と、
前記第２の中間色値と、
前記最も高い色値と、
前記最も低い色値と、前記第１の中間色値と、前記第２の中間色値と、前記最も高い色値と、のうちの１つに隣接する１つ以上の色値と、
以外の色値が、前記ｍ×ｎ画素セルに存在しないと判断する工程と、
をさらに含み、
前記複数の出力色値を選択する工程は、前記最も低い色値と、前記第１の中間色値と、前記第２の中間色値と、前記最も高い色値と、のそれぞれ、またはそれらの近傍の色値を、前記４つの出力色値として選択する工程を含む、請求項５に記載の方法。
【請求項７】
前記ｍ×ｎ画素セル上において離散コサイン変換（ＤＣＴ）を実行する工程をさらに含み、
前記複数の出力色値は、前記ＤＣＴの演算結果に基づいており、
前記第２の表現は、ＤＣＴオペコードと、前記ＤＣＴ演算結果を含む、請求項１または２に記載の方法。
【請求項８】
前記複数の出力色値は、４つの出力色値から構成されており、
前記４つの出力色値のそれぞれは、前記ｍ×ｎ画素セルの角の色値であり、
前記第２の表現は、勾配オペコードと、前記４つの色値の各々の表示と、を含む、請求項１または２に記載の方法。
【請求項９】
前記特徴を判断する工程は、
前記４つの出力色値の双一次補間に基づいて、ｍ×ｎの画素のテンプレートセットを取得する工程と、
前記ｍ×ｎ画素セルの色値を前記テンプレートセットのｍ×ｎの画素の色値と比較する工程と、
前記ｍ×ｎ画素セルの画素の色値が、前記テンプレートセットにおけるｍ×ｎの画素の色値と、少なくともほぼ一致すると決定する工程と、を含む、請求項８に記載の方法。
【請求項１０】
前記出力媒体に書き込まれる表現に基づいて、出力装置に、ｍ×ｎ画素セルの色値の近似値を再形成する工程をさらに含む、請求項１から９のいずれかに記載の方法。
【請求項１１】
コンピュータによる実行において、前記コンピュータに、請求項１から１０のいずれかに記載の方法の動作を実行させるプログラム命令を格納する非一時的なコンピュータ読み取り可能な記録媒体。
【請求項１２】
コンピュータであって、
プロセッサと、
データ記憶装置と、
前記データ記憶装置に格納され、前記コンピュータによる実行において、前記コンピュータに、請求項１から１０のいずれかに記載の方法の動作を実行させるプログラム命令を備えるコンピュータ。
【請求項１３】
コンピュータによる実行において、前記コンピュータに請求項１から１０のいずれかに記載の方法の動作を実行させるプログラム。
【請求項１４】
方法は、以下を含む：
コンピュータにより、ｍ×ｎ以上の画素を含む入力画像から、画素のそれぞれが色値を有するｍ×ｎ画素セルを得る工程と、
前記コンピュータにより、前記ｍ×ｎ画素セル内の画素の色値を判断する工程を含む、前記ｍ×ｎ画素セルの特徴を判断する工程と、
前記コンピュータにより、前記色値のうち、最も高い色値と最も低い色値との間の差を算出する工程と、
前記差が閾値差以下である場合、前記コンピュータにより、前記最も高い色値と、前記最も低い色値との間に含まれる色値から１の出力色値を選択し、単色オペコードと、前記出力色値の表示と、を含む、前記出力色値の第２の表現を、出力媒体に書き込む工程と、
他の場合において、前記ｍ×ｎ画素セルの前記色値が実質的に２つの色値から構成されている場合、前記コンピュータにより、
２色オペコードと、
前記２つの出力色値のそれぞれの表示と、
前記ｍ×ｎ画素セル内の各画素を、前記２つの出力色値のうちの１つと関連付ける、前記ｍ×ｎ画素セルの画素ごとのビットマップと、
を含む、第２の表現を前記出力媒体に書き込む工程と、
さらに他の場合において、前記ｍ×ｎ画素セルの前記色値が実質的に３つまたは４つの色値から構成されている場合、前記コンピュータにより、
４色オペコードと、
前記３つまたは４つの色値のそれぞれの表示と、
前記ｍ×ｎ画素セルの各画素を、前記３つまたは４つの色値のうちの１つと関連付ける、前記ｍ×ｎ画素セルの画素ごとのビットマップと、
を含む第３の表現を前記出力媒体に書き込む工程と、
さらに他の場合において、前記ｍ×ｎ画素セルの前記色値が、実質的に４つより多い色値から構成されている場合、前記コンピュータにより、
前記ｍ×ｎ画素に対して離散コサイン変換（ＤＣＴ）の演算を実行し、
ＤＣＴオペコードと、前記ＤＣＴ演算の結果と、を含む、第４の表現を前記出力媒体に書き込む工程。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタル画像の画素セルに基づく圧縮（Cell-Based Compression of Digital Images）に関する。
【背景技術】
【０００２】
近年、業務用および家庭用のいずれにおいても、様々な印刷装置の普及が進んでいる。従来の白黒のプリンタに加えて、現在、カラーのプリンタ、スキャナ、複写機、ファックス等の装置が、一般的である。これらのうちの２つ以上の機能を有する複合機（ＭＦＰ）も、広く利用されている。これらの装置は、より一般的になるにつれて、より複雑な文書の処理に使われるようになってきている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第５,９１５,０７９号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、デジタル画像の画素セルベースでの圧縮方法に提供することを目的とする。
【課題を解決するための手段】
【０００５】
例示の実施形態において、ｍ×ｎ画素セルは、入力画像から得られることができる。入力画像はｍ×ｎ画素より多くの画素を含んでいてもよく、ｍ×ｎ画素セルのｍ×ｎ画素の各々はそれぞれの色値を有していてもよい。ｍ×ｎ画素セルの特徴が判断されてもよい。特徴を判断する工程は、ｍ×ｎ画素セルの最も低い色値および最も高い色値を決定する工程を含んでいてもよい。最も高い色値と最も低い色値との差が算出されてもよい。差が閾値の差以下である場合、最も高い色値と最も低い色値との間に存在する出力色値が選択されてもよく、出力色値の第１の表現が出力媒体に書き込まれてもよい。第１の表現は、単色オペコードおよび出力色値の表示を含んでいてもよい。差が閾値差より大きい場合、複数の出力色値が選択されてもよく、複数の出力色値の第２の表現が出力媒体に書き込まれてもよい。
【０００６】
他の例示の実施形態において、ｍ×ｎ画素セルは、入力画像から得られることができる。入力画像はｍ×ｎ画素より多くの画素を含んでいてもよく、ｍ×ｎ画素セルのｍ×ｎ画素の各々はそれぞれの色値を有していてもよい。ｍ×ｎ画素セルの特徴が判断されてもよいく、特徴を判断する工程はｍ×ｎ画素セルの画素の色値を決定する工程を含んでいてもよい。最も高い色値と最も低い色値との差が決定されてもよい。差が閾値の差以下である場合、最も高い色値と最も低い色値との間に存在すの出力色値が、選択されてもよい。出力色値の第１の表現は、出力媒体に書き込まれてもよい。第１の表現は、単色オペコードおよび出力色値の表示を含んでいてもよい。ｍ×ｎ画素セルの色値が、実質的に２つの色値から成る場合、２つの色値の第２の表現が出力媒体に書き込まれてもよい。第２の表現は、２色オペコード、２つの色値の各々の表示およびｍ×ｎ画素セルの各画素を２つの色値のうちの１つと関連付ける、ｍ×ｎ画素セルの画素ごとのビットマップを含んでいてもよい。ｍ×ｎ画素セルの色値が、実質的に３つまたは４つの色値から成る場合、３つまたは４つの色値の第３の表現が出力媒体に書き込まれてもよい。第３の色値は４色のオペコード、３つまたは４つの色値の各々の表示およびｍ×ｎ画素セルの各画素を３つまたは４つの色値の１つと関連付けるｍ×ｎ画素セルの画素ごとのビットマップを含んでいてもよい。ｍ×ｎ画素セルの色値が、実質的に４つ以上の色値から成る場合、離散コサイン変換（ＤＣＴ）演算がｍ×ｎ画素セルに実行されてもよく、第４の表現が出力媒体に書き込まれてもよい。第４の表現は、ＤＣＴオペコードおよびＤＣＴ演算結果を含んでいてもよい。
【０００７】
追加の実施形態は、コンピュータによる実行において、前記コンピュータに、上記のいずれかに記載の方法の動作を実行させるプログラム命令を格納する非一時的なコンピュータ読み取り可能な記録媒体を含んでいてもよい。
【０００８】
さらなる実施形態は、少なくともプロセッサ、データ記憶装置、少なくとも一つのプロセッサによる実行に応じて、コンピュータ・システムに上記の例示の実施形態のいずれかまたは両方ともに従って作動させる、データ記憶装置に格納されたプログラム命令を含むコンピュータ・システムを含んでいてもよい。
【０００９】
他の態様、利点および変形例は、必要に応じて添付の図面を参照しながら以下の詳細な説明を読むことによって、当業者にとって明らかになるであろう。更に、この欄において、そして、この文書の他の部分で示される説明は、請求された内容を例示することを目的として示されるものであり、制限することを目的とするものではないことを理解されたい。
【発明の効果】
【００１０】
本発明によれば、デジタル画像の画素セル単位での圧縮方法が提供される。
【図面の簡単な説明】
【００１１】
【図１】図１は、例示の実施形態における印刷装置を示す模式図である。
【図２】図２は、例示の実施形態における印刷装置のコンピュータの構成要素を示すブロック図である。
【図３】図３は、例示の実施形態における、印刷装置を含む様々なデータ経路を示すブロック図である。
【図４】図４は、例示の実施形態における、電子文書に含まれる画像の一例を示す図である。
【図５Ａ】図５Ａは、例示の実施形態における、圧縮／解凍技術の例を示す図である。
【図５Ｂ】図５Ｂは、例示の実施形態における、圧縮／解凍技術の他の例を示す図である。
【図６】図６は、例示の実施形態における、一連のｍ×ｎ画素セルを評価して、圧縮する方法を表す図である。
【図７】図７は、例示の実施形態における、圧縮技術を示す図である。
【図８】図８は、例示の実施形態における、勾配圧縮の態様を表す図である。
【図９】図９は、例示の実施形態における、２色圧縮の態様を表す図である。
【図１０】図１０は、例示の実施形態における、フローチャートである。
【図１１Ａ】図１１Ａは、例示の実施形態におけるフローチャートの他の例である。
【図１１Ｂ】図１１Ｂは、例示の実施形態におけるフローチャートの他の例である。
【発明を実施するための形態】
【００１２】
以下、例示の実施形態の方法および装置を説明する。本願明細書において示される趣旨および内容の範囲を逸脱しない範囲で、他の例示の実施形態または構成を利用することが可能であり、また、他の変更がなされることもできる。以下では、添付の図面を参照しながら詳細な説明がなされる。
【００１３】
本願明細書において記載されている例示の実施形態は、本発明を限定しない。本願明細書において概要として記載されており、添付図面に図示される、本発明の態様は、多種多様な異なる構成において、配置されることができ、置換されることができ、組み合わせることができ、切り離されることができ、設計されることができることは容易に理解できる。そして、その態様の全ては本願明細書において明確に考察される。
【００１４】
１．  はじめに
印刷技術は、白黒の画像だけを形成する単純なドット・マトリクス・ベースの出力装置から、高解像度のカラー画像を形成することができる今日の高度なレーザー型の印刷装置まで、これまで３０年以上にわたり進展してきている。加えて、最新の印刷装置は、複写機、スキャナおよびファックスとして機能することもできる。そのために、それらの装置は、印刷またはファックスを行うために待機される、または、スキャンされた、多数の電子文書を格納することが可能である。このように、多くの印刷装置は、例えば、一つ以上のプロセッサ、データ格納部および入出力インタフェースを含むことができるコンピュータの特殊な形態でもある。
【００１５】
印刷装置は、家庭、事業、または、その他の場所において用いられるかどうかにかかわらず、様々な他のコンピュータに通信により接続することができる共用のリソースであってもよい。従って、ある環境においては、多数のコンピュータが、印刷する目的で、電子文書を印刷装置に発信することができるように、印刷装置の記憶容量の要求が非常に高くなることがある。典型的には、印刷装置は、先着順に（ｆｉｒｓｔ−ｃｏｍｅ−ｆｉｒｓｔ−ｓｅｒｖｅｄ）、一度に１つの電子文書を印刷、複製、ファックスおよび／またはスキャンする。従って、このような印刷装置は、これらのサービスを行うために待機している、潜在的にかなりの数の電子文書を格納することができる。データ格納部（例えば、ランダム・アクセス・メモリ（ＲＡＭ）、ソリッドステートメモリ、ハードディスク・メモリおよび／またはフラッシュメモリ等のメモリ）は、高価なことがあるので、印刷装置のデータ格納部の記憶容量を削減する目的で、格納された電子文書を圧縮することが有益となりうる。加えて、いくつかの電子文書が印刷装置およびコンピュータへと送信される、および／またはそれらから送信されることができるので、これらの電子文書を圧縮することにより、文書の送信速度をより急速にすることが可能となり、また、使用するネットワークの容量を削減することができる。
【００１６】
さらに、印刷ジョブが大きくなることがある（例えば、印刷ジョブは数百ページに及ぶ１以上の電子文書を含むことがある）ので、各ジョブが印刷される前に、キューで待機された印刷ジョブを圧縮することにより、短期記憶の使用を減らし空き領域を確保することが可能となる。加えて、ユーザは、後ほど印刷するために長期間の記憶装置（長期記憶領域）での印刷ジョブの保存を望むことがある。このときも、印刷ジョブを圧縮することによって、より多くの印刷ジョブを保存することができる。さらにまた、長期記憶装置からの大きい印刷ジョブの格納および引き出しは遅くなる可能性がある、しかし、印刷ジョブを圧縮し、その大きさをより小さくすることによって、そのような格納や引き出しを促進することができる。
【００１７】
２．  印刷装置の例
図１は、例示の実施形態の印刷装置１００を示す。印刷装置１００は、部分的に格納されたおよび／または全体が格納された電子文書を様々な形の物理的な出力メディアに印刷するように構成されていてもよい。これらの出力メディアは、種々の大きさおよび形態の紙、オーバーヘッドプロジェクタに用いられる透明フィルム（ｏｖｅｒｈｅａｄ  ｔｒａｎｓｐａｒｅｎｃｉｅｓ）、等を含んでもよく、また、これらに限定されるものではない。印刷装置１００は、「プリンタ」と呼ばれることもある。
【００１８】
印刷装置１００は、例えばパーソナル・コンピュータ、サーバ装置、プリントサーバ、などのコンピュータの、ローカル周辺機器として機能してもよい。これらの場合、印刷装置１００は、例えばシリアルポート・ケーブル、パラレル・ポート・ケーブル、ユニバーサルシリアルバス（ＵＳＢ）ケーブル、ファイヤーワイヤー（Ｆｉｒｅｗｉｒｅ、ＩＥＥＥ  １３９４）ケーブルまたは高精細度マルチメディアインターフェース（Ｈｉｇｈ―Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ（ＨＤＭＩ））ケーブルによりコンピュータに取り付けられることができる。このように、コンピュータは、印刷装置１００に対し、電子文書の供給源として機能することができる。
【００１９】
一方では、印刷装置１００は、例えばイーサネットまたは８０２．１１（Ｗｉｆｉ）インタフェース等、有線または無線のネットワーク・インタフェースを含んでいてもよい。このように配置されることで、印刷装置１００は、ネットワーク上の印刷装置１００と通信することができる任意の数のコンピュータに対する印刷装置として機能することができる。いくつかの実施形態においては、印刷装置１００は、同時に、ローカル周辺機器およびネットワーク上のプリンタとして機能することができる。印刷装置１００を使用する目的で、コンピュータは、一つ以上のプリンタ・ドライバをインストールしてもよい。これらのプリンタは、印刷される電子文書を、コンピュータに格納された種々のローカルな表現から、印刷装置１００によってサポートされる一つ以上の表現に変換するソフトウェアの構成要素を含んでいてもよい。
【００２０】
上記のように、印刷装置１００は、コンピュータであると考えられることができ、また、印刷に関連する作業も印刷に関連しない作業も実行することができる。
【００２１】
上記の如く、印刷装置１００は、複写機、ファックスおよびスキャナ機能を含んでいてもよい。いくつかの実施形態では、複写機および／またはファックスとしての機能を促進する目的で、印刷装置１００は、スキャナ機能を使用できるように構成されていてもよい。例えば、印刷装置１００は、電子フォーマットに物理的な文書（ｐｈｙｓｉｃａｌ  ｄｏｃｕｍｅｎｔ）をスキャンして電子文書を作成することができ、それから、結果として得られる電子文書を印刷して複写物を提供することができ、および／または結果として得られる電子文書を電話インターフェースを介して送信してファックス機能を提供することができる。
【００２２】
その様々な機能をサポートする目的で、印刷装置１００は、ドキュメントフィーダ／排出トレイ１０２、給紙カセット（ｐａｐｅｒ  ｓｔｏｒａｇｅ）１０４、ユーザ・インタフェース１０６、スキャナー部１０８および筐体１１０を含んでいてもよい。印刷装置が多種多様な形態をとることができることが理解される。従って、印刷装置１００は図１において表されるより多くまたはより少ない構成要素を含んでいてもよいし、図１において表される態様と異なる態様で配置された構成要素を含んでいてもよい。
【００２３】
ドキュメントフィーダ／排出トレイ１０２は、スキャンされることになっているか、複製されることになっているかまたは、ファックスされることになっている物理的な文書（例えば、一つ以上の用紙の束）を保持することができる。ドキュメントフィーダ／排出トレイ１０２により、マニュアル動作を必要とすることなく、印刷装置１００による処理のために複数の物理的な文書を印刷装置１００が自動的に供給することができる構成が有効である。ドキュメントフィーダ／排出トレイ１０２は、印刷装置１００によって処理された物理的な文書を保持する一つ以上の別々の排出トレイを含んでいてもよい。これらは、例えば、印刷装置１００のファックスおよび／または複写機能によって作成された物理的な文書だけでなく、印刷装置１００によってスキャンされたか、複製されたかまたは、ファックスされた物理的な文書を含んでいてもよい。
【００２４】
給紙カセット１０４は、様々な形態の物理的な媒体用のトレイおよび／または給紙の構成要素を含んでいてもよい。例えば、給紙カセット１０４は、８  １／２  ×  １１インチの紙、Ａ４紙、レターヘッド紙、封筒、その他のための別々のトレイを含んでいてもよい。物理的な媒体の出力（例えば、印刷、複製および／または、ファックスの受信等）を行う印刷装置１００の任意の機能として、給紙カセット１０４は、物理的な媒体を供給することができる。
【００２５】
例えばユーザから入力を受け取って、出力をユーザに提供するために、ユーザ・インタフェース１０６は、印刷装置１００と、人間または人間以外のユーザとの相互作用を促進することができる。このように、ユーザ・インタフェース１０６は、例えばキーパッド、キーボード、タッチ式または存在を感知する方式のパネル（ｐｒｅｓｅｎｃｅ−ｓｅｎｓｉｔｉｖｅ  ｐａｎｅｌ）、ジョイスティック、マイクロホン、スチルカメラおよび／またはビデオ・カメラ等の入力の構成要素を含んでいてもよい。ユーザ・インタフェース１０６は、例えば、ディスプレイ画面（例えば、存在を感知する方式のパネルと結合されることができる）、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）タイプのディスプレイ、デジタルミラーデバイスを使用した表示システム（ｄｉｇｉｔａｌ  ｌｉｇｈｔ  ｐｒｏｃｅｓｓｉｎｇ（ＤＬＰ））を使用したディスプレイ、電球および／または現在知られているまたは将来開発される一つ以上の他の類似の装置等の一つ以上の出力構成要素を含んでいてもよい。ユーザ・インタフェース１０６は、また、例えば、スピーカ、スピーカ・ジャック、オーディオ出力ポート、オーディオ出力デバイス、イヤホンおよび／または現在知られているまたは将来開発される他の類似の装置を介して、聞き取り可能な出力を生成することが可能となるように、構成されていてもよい。
【００２６】
スキャナー素子１０８は、移動可能な光源がガラスパネルの上に配置される物理的な媒体を走査するように作動するガラスパネルでもよい。あるいは、ガラスパネルの下に配置されたデジタル・カメラが、物理的な媒体の画像を撮影することによってガラスパネルの上に配置される物理的な媒体を「走査」してもよい。走査された物理的な媒体の画像は、印刷装置１００と関連付けられてデータ格納部に格納されてもよい。
【００２７】
筐体１１０は、例えばドキュメントフィーダ／排出トレイ１０２、給紙カセット１０４、ユーザ・インタフェース１０６および走査素子１０８のような、印刷装置１００の様々な構成要素を収容する、あるいは相互に接続する物理的な筐体を含んでいてもよい。加えて、シャシー１１０は、図１に示されない他の構成要素を収容していてもよい。例えば、筐体１１０は、一つ以上のトナーカートリッジ、液体インク・ジェット、ベルト、ローラーおよび／または電源を収容していてもよい。更に、筐体１１０は、例えば有線および／または無線のネットワーク・インタフェース、ＲＪ４５ジャック等の電話通信インタフェース、ＵＳＢインターフェース、ＢＬＵＥＴＯＯＴＨインタフェース、カードリーダーポート、等の通信インタフェースを収容していてもよい。
【００２８】
さらに、印刷装置１００は、汎用および／または特別に設計されたコンピュータの構成要素に基づいていてもよいので、筐体１１０はこれらの構成要素の一部もしくは全部を収容していてもよい。その点で、図２は、印刷装置１００に含まれうるコンピュータの構成要素（例えば、コンピュータの機能素子）の例示の実施形態２００を示す。
【００２９】
コンピュータの構成要素２００は、プロセッサ２０２、データ格納部（データ記憶部）２０４および入出力機能２０６を含んでいてもよい。そして、その全てはシステムバス２０８または類似の機構によって連結されていてもよい。プロセッサ２０２は、例えば、一つ以上の汎用プロセッサおよび／または一つ以上の専用プロセッサ（例えば、特定用途向け集積回路（ＡＳＩＣ）またはデジタル信号プロセッサ（ＤＳＰ）等））等の一つ以上の中央演算処理装置（ＣＰＵ）を含んでいてもよい。
【００３０】
また、データ格納部２０４は、揮発性および／または不揮発性のデータ格納部を有していてもよく、全体的にあるいは部分的にプロセッサ２０２と統合されていてもよい。データ格納部２０４は、プロセッサ２０２によって実行可能なプログラム命令、および、本願明細書において記載されている様々な方法、プロセスまたは機能を実行するようにこれらのプログラム命令によって扱われるデータを格納していてもよい。あるいは、これらの方法、プロセスまたは機能は、ハードウェア、ファームウェア、および／または、ハードウェア、ファームウェアおよびソフトウェアのうちの任意の組合せによって定義されることができる。従って、データ格納部２０４は、一つ以上のプロセッサによる実行において、印刷装置１００に、本願明細書または添付図面に開示された任意の方法、プロセス、または機能を実行させるプログラム命令を記憶した、有形の、非一時的なコンピュータ読み取り可能な記録媒体（ｔａｎｇｉｂｌｅ，ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ−ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）を含むことができる。
【００３１】
入出力機能２０６は、ユーザ・インタフェース１０６に関して記載されている任意の機能および／または構成要素を含んでいてもよい。このように、入出力機能２０６は、プロセッサ２０２の動作を構成する、および／または制御するものとして機能することができる。入出力機能２０６は、また、プロセッサ２０２によって実行される動作に基づく出力を提供することもできる。
【００３２】
印刷装置のこれらの例は、説明の便宜上示されている。更に、上記の例に加え、または上記の例に代えて、本願明細書における実施形態の要旨を逸脱しない範囲で、他の可能なプリンタおよびコンピュータ技術の他の組合せが存在してもよいし、また、他の態様で部分的に組み合わせてもよい。
【００３３】
図３は、印刷装置１００によって処理される電子文書の表現が通過することができる可能なデータ経路のいくつかを示す。図３においては、印刷装置１００は、スキャナ機能３０２および印刷機能３０４を含むことができると仮定されている。これらの機能の各々は、ハードウェア、ファームウェア、ソフトウェア、またはハードウェア、ファームウェアおよび／またはソフトウェアの任意の組合せでも行うことができる。加えて、スキャン機能３０２および印刷機能３０４の各々は、コンピュータ３００や、考えられる他のコンピュータにも通信することができる。ある場合においては、印刷装置１００でサポートされるデータ経路は、「パイプライン（ｐｉｐｅｌｉｎｅ）」と称されることもある。
【００３４】
スキャン−プリントデータ経路（ｓｃａｎ−ｔｏ−ｐｒｉｎｔ  ｄａｔａ  ｐａｔｈ）３１０は、スキャン機能３０２および印刷機能３０４によってサポートされることができる。例えば、ユーザが印刷装置１００に物理的文書を複製するように指示するときに、スキャン−プリントデータ経路３１０が使われることができる。この指示に応えて、スキャン機能３０２は、物理的文書を走査して電子文書にし、スキャン−プリントデータ経路３１０を介して印刷機能３０４に電子文書を送信することができる。スキャン−プリントデータ経路３１０の使用は、電子文書の一部もしくは全部を印刷装置１００のデータ格納部に少なくとも一時的に格納することを含んでいてもよい。それから、印刷機能３０４は、物理的な媒体（例えば、一枚以上の紙）に、電子文書を印刷することができる。
【００３５】
スキャン−ホストデータ経路（ｓｃａｎ−ｔｏ−ｈｏｓｔ  ｄａｔａ  ｐａｔｈ）３０６は、また、スキャン機能３０２およびコンピュータ３００によってサポートされることができる。例えば、ユーザが印刷装置１００に物理的な文書をスキャンするように指示する際に、スキャン−ホストデータ経路３０６が使われることができる。また、ユーザは、印刷装置１００に、結果として生じる電子文書の表現（ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）をコンピュータ３００に送信（転送）するように指示することもできるし、または、印刷装置１００は、自動的に電子文書をコンピュータ３００に転送するように予め設定されていてもよい。このように、この指示に応じて、スキャン機能３０２は、物理的な文書を走査して電子文書とし、スキャン−ホストデータ経路３０６を介して、結果として生じる電子文書をコンピュータ３００に送信することができる。スキャン−ホストデータ経路３０６の使用は、電子文書の一部もしくは全部を印刷装置１００のデータ格納部に少なくとも一時的に格納して、結果として生じる電子文書の表現をコンピュータ３００に転送することを含んでいてもよい。
【００３６】
ホスト−プリントデータ経路（ｈｏｓｔ−ｔｏ−ｐｒｉｎｔ  ｄａｔａ  ｐａｔｈ）３０８は、コンピュータ３００および印刷機能３０４によってサポートされることができる。例えば、ユーザがコンピュータ３００に対し、電子文書を印刷装置１００に印刷するように指示する際に、ホスト−プリントデータ経路３０８が使われることができる。この指示に応じて、コンピュータ３００は、電子文書の表現を印刷機能３０４に転送することができる。印刷装置１００は、印刷機能３０４を介して、物理的な媒体（ｐｈｙｓｉｃａｌ  ｍｅｄｉａ）に電子文書を印刷することができる。電子文書を印刷する前におよび／または印刷する間に、電子文書の一部もしくは全部が、印刷装置１００のデータ格納部に格納されてもよい。
【００３７】
おそらく印刷装置１００によりサポートされる他のデータ経路だけでなく、上記のデータ経路の少なくとも１つにおいては、電子文書は、明らかに、記憶領域、および／またはネットワークまたはケーブル上における転送を必要とする可能性がある。電子文書の蓄積および転送の効率は、記憶および／または転送されるこれらの電子文書を圧縮することによって、改善されうる。例えば、電子文書が、平均して、それらの最初のサイズの１／４に圧縮される場合、データ記憶領域の大きさが固定値であるとき、約４倍の電子文書を、データ格納部に格納することができる。更に、このように圧縮された電子文書のネットワークやケーブルを介した転送は、圧縮されていない電子文書の転送時に比べ、約４倍の速度で行うことができる。
【００３８】
以下では、印刷装置１００によって処理される電子文書の圧縮を提供する各種実施形態が説明される。
【００３９】
３．  例示の実施形態の圧縮技術（Ｃｏｍｐｒｅｓｓｉｏｎ  Ｔｅｃｈｎｉｑｕｅｓ）
これまで、圧縮方法として、あるデータ経路においては、非可逆圧縮（損失性の圧縮（ｌｏｓｓｙ  ｃｏｍｐｒｅｓｓｉｏｎ））が利用され、一方で、可逆圧縮（無損失の圧縮（ｌｏｓｓｌｅｓｓ  ｃｏｍｐｒｅｓｓｉｏｎ））が他のデータ経路で使われてきた（非可逆圧縮技術は、データの一部を破棄することによってデータを圧縮する技術であり、可逆圧縮技術はいかなるデータも破棄することなくデータを圧縮する技術である。）。例えば、ある実施態様においては、ホスト−プリントデータ経路３０８は、電子文書を印刷した文書において、テキストおよび画像の線画の鮮明なエッジが保存されるように、可逆圧縮を用いてもよい。一方、スキャン−ホストデータ経路３０６およびスキャン−プリントデータ経路３１０は、グラフィカルイメージを含んでいるスキャンされた物理的な文書を効率的に格納して転送することを目的として、非可逆圧縮を利用してもよい。印刷装置１００は、より効率的な構成とすることができ、そのソフトウェアおよび／またはハードウェアの実装は、そのデータ経路の少なくとも一部（場合によっては全部）において、同じまたは同様の圧縮技術を用いることにより、単純化することが可能である。
【００４０】
ａ．  例示の画像
図４は、印刷装置１００によって処理される物理的な文書あるいは電子文書に含まれる画像４００の例で示す。例示の画像４００はモノクロで示されているが、類似特性を有するカラー画像が印刷装置１００によって処理されてもよい。
【００４１】
図４から分かるように、例示の画像４００は、様々な形の内容を含む。例えば、例示の画像４００は、エッジが鮮明なテキストおよび線画を含む。更に、例示の画像４００には、写真のようにリアルなデータ（例えば、画像４００の右下角部）を含む部分だけでなく、連続的な中間調（例えば、画像４００の左上角部）を含む部分がある。例示の画像４００は、例えば、パンフレット、雑誌、ビラまたは広告のような、ビジネスでの印刷物において使われる一般的な画像の例である。
【００４２】
一元的な圧縮技術により、例示の画像４００の鮮明なエッジおよび線を正確に表現することが可能となり、その一方で、例示の画像４００を含む電子文書の必要な記憶領域を減らすために非可逆圧縮をさらに使用することができる。
【００４３】
ｂ．  例示の画像のカラーモデル（Ｉｍａｇｅ  Ｃｏｌｏｒ  Ｍｏｄｅｌｓ）
電子文書は、多くのカラーモデルを使用して表されることができる。そして、強力な圧縮技術が、これらのカラーモデルの一部もしくは全部に対し作用することが可能であるほうが好ましい。更に、圧縮技術は、個々のカラーモデルに特有の前処理を含んでいてもよい。
【００４４】
例えば、赤―緑―青（ＲＧＢ）カラーモデルは、テレビ、モニタ、およびコンピュータ・スクリーン等の電子的な出力装置上における画像の表示の用に供することができる。ＲＧＢは、可視光域の色を表現する様々な方法において、赤色光、緑色光、および青色光が互いに足し合わされる加法混色のカラーモデルである。例えば、シアンは緑および青を混合することによって表現することができ、黄色は赤および緑を混合することによって表現することができ、マゼンタは赤および青を混合することによって表現することができ、白は、赤・緑・青を混合することによって表現されることができる。
【００４５】
ＲＧＢ画像における画素は、３つのチャネルのタプル（Ｒ，Ｇ，Ｂ）として表されることができる。各チャネルはゼロから所定の最大値（例えば、２５５）まで変化することができる。もし、チャネルの全てがゼロである場合、黒が表現されてもよい。チャネルの全てが最大値である場合、再現可能な最も明るい白が表現されてもよい。
【００４６】
異なる出力装置においては、同じＲＧＢ画像を異なる方式により表示することができるという点で、ＲＧＢの出力は典型的にはデバイスに依存する。ある場合には、これらの違いは、人間によって知覚されることがある。いくつかの実施形態においては、スキャン−ホストデータ経路３０６を使用して印刷装置１００にスキャンされる物理的な文書が、ＲＧＢカラーモデルを使用して符号化されることができる。
【００４７】
シアン−マゼンタ−イエロー（ＣＭＹ）カラーモデルが、印刷装置によるカラー画像の印刷に用いられることができる。ＣＭＹは、可視光域の色を表現する様々な方法において、白色表面上に、シアン、イエローおよびマゼンタが付与される減法混色のカラーモデルである。例えば、赤はマゼンタおよびイエローを混合することによって表現することができ、青はシアンおよびマゼンタを混合させることによって表現することができ、そして、緑はシアンおよびイエローを混合することによって表現することができる。このように、ＣＭＹカラーモデルは、ＲＧＢカラーモデルを補うもの（補色の関係にある）と考えてもよい。
【００４８】
ＣＭＹ画像における画素は３つのチャネルのタプル（Ｃ，Ｍ，Ｙ）として表されることができる。そして、各チャネルはゼロから所定の最大値まで変化することができる。チャネルの全てがゼロである場合、白が表現されてもよい。チャネルの全てが最大値である場合、黒が表現されてもよい。
【００４９】
ＲＧＢカラーモデルと同様に、同じＣＭＹの画像が、異なる印刷装置上では、異なるように見える可能性があるという点で、ＣＭＹ出力は、典型的には、デバイスに依存する。ある場合には、これらの違いは、人間によって知覚される可能性がある。いくつかの実施形態においては、ホスト−プリントデータ経路３０８および／またはスキャン−プリントデータ経路３１０を使用している印刷装置１００によって印刷される電子文書が、ＣＭＹカラーモデルを使用して符号化されることができる。
【００５０】
いくつかの実施形態では、４つのチャネルを用いるＣＭＹＫカラーモデルが用いられることもできる。この４つのチャネルを用いたＣＭＹＫカラーモデルは、キー（ｋｅｙ）チャネル（黒チャネル）も使われるという点以外、ＣＭＹカラーモデルとほぼ同様または同じであってもよい。黒を形成するためにシアン、マゼンタおよび黄色を混合することに加えて、別のキーの（黒の）インク源が、黒を形成するために用いられることができる。このように、ＣＭＹＫ画像の画素は４つのチャネルのタプル（Ｃ，Ｍ，Ｙ，Ｋ）として表することができ、各チャネルはゼロから所定の最大値まで変化することができる。
【００５１】
ＣＭＹＫカラーモデルを使用して、ＣＭＹモデルと同じ色がサポートされることができるが、Ｋの色剤がＣ、ＭおよびＹの色剤の混合物と置き換えることができるので、典型的には、色剤（インク）の使用量をより少なくすることができる。しかしながら、ＣＭＹＫカラーモデルの、他のカラーモデルへの変換や、他のカラーモデルからの変換は、必ずしも都合よくは可能とならないことがある。なぜなら、Ｋの色剤の追加により、例えば、同じ色がＣ、Ｍ、ＹおよびＫの異なる組合せにより表現できることから、冗長性が付加される可能性があるからである。
【００５２】
他のカラーモデルはグレー（中間調）、または、グレースケールとも呼ばれ、モノクロの画像の表現に使われることができる。ＲＧＢおよびＣＭＹ／ＣＭＹＫカラーモデルとは異なり、グレースケールカラーモデルの各画素は、画素の強度を符号化する単一のチャネルを使用して表される。グレーチャネルによって使用される値は、黒に対応するゼロから、白（例えば、２５５）に対応する所定の最大値まで、変化することができる。いくつかの実施形態では、印刷装置１００でサポートされる１つ以上のデータ経路において、グレースケールのカラーモデルを使用して、画像を符号化することが可能となってもよい。
【００５３】
他のカラーモデルとしては、例えばＹＣｂＣｒがある。ある実施態様においては、このカラーモデルが、画像の代替の表現として用いられることができる。具体的には、Ｙチャネルは画素の輝度を表し、ＣｂおよびＣｒチャネルが、それぞれ、青−黄クロミナンス（ｂｌｕｅ−ｙｅｌｌｏｗ  ｃｈｒｏｍｉｎａｎｃｅ）および赤−緑クロミナンス（ｒｅｄ−ｂｌｕｅ  ｃｈｒｏｍｉｎａｎｃｅ）を表すことができる。ＹＣｂＣｒカラーモデルは、ＲＧＢカラーモデルおよびＣＭＹカラーモデルとの関係性が明確であり、比較的容易に、これらのカラーモデルからの変換およびこれらのカラーモデルへの変換が可能である。
【００５４】
ＹＣｂＣｒカラーモデルにおける更なる利点としては、ＹＣｂＣｒカラーモデルを用いて符号化される画像の圧縮は、ＲＧＢまたはＣＭＹ／ＣＭＹＫカラーモデルを用いて符号化される画像の圧縮より効率的であるという傾向がある点がある。特に、人間の眼は、画像における高周波（例えば、急速に変化する）成分のクロミナンスに関する情報の検知が得意ではない。従って、ＣｂおよびＣｒチャネルの高周波成分を無視することによっても、ＹＣｂＣｒカラーモデルを用いて符号化された画像は、この情報（クロミナンスの情報）を十分に利用したものとすることができる。このように、以下に詳述するように、特定のカラーモデルに符号化される画像は、圧縮のパフォーマンスを向上させる目的で、圧縮の前にＹＣｂＣｒカラーモデルに変換されてもよい。
【００５５】
ｃ．  例示の圧縮技術（Ｃｏｍｐｒｅｓｓｉｏｎ  Ｔｅｃｈｎｉｑｕｅｓ）の概要
例示の実施形態の圧縮技術の概要が、図５Ａおよび５Ｂに示されている。図５Ａにおいて、ブロック５００では、電子文書は、グレースケールのカラーモデルまたはＣＭＹＫカラーモデルで表されていてもよい。ブロック５０２では、セルベースでの圧縮（ｃｅｌｌ−ｂａｓｅｄ  ｃｏｍｐｒｅｓｓｉｏｎ（以下に詳細に述べられる））は、電子文書の各チャネルに適用することができる。従って、グレースケールの電子文書に対し、セルベースの圧縮は、グレーのチャネルに適用することができる。ＣＭＹＫの電子文書に対し、セルベースの圧縮は、Ｃ、Ｍ、ＹおよびＫのチャネルの各々に別々に適用することができる。ブロック５０２の結果は、電子文書の圧縮バージョンを表現するビットストリーム（ｂｉｔ  ｓｔｒｅａｍ）であってもよい。
【００５６】
ブロック５０４では、セルベースの解凍（以下に詳細に述べられる）が、電子文書の各チャネルに適用することができる。これは、ブロック５０６での、グレースケールまたはＣＭＹＫの電子文書の再現に結果としてなることもある。しかしながら、セルベースの技術が非可逆圧縮を使用する場合、ブロック５０６の電子文書がブロック５００の電子文書と異なる可能性がある点に留意する必要がある。しかしながら、電子文書のこれらのバージョン間の違いは小さくすることができ、したがって、人間によって認識されないようにすることもできる。
【００５７】
図５Ｂにおいて、ブロック５０８では、電子文書は、ＲＧＢまたはＣＭＹカラーモデルにおいて表現されてもよい。ブロック５１０では、この電子文書は、ＹＣｂＣｒカラーモデルに変換されることができる。加えて、属性ビット（ａｔｔｒｉｂｕｔｅ  ｂｉｔ）が、電子文書に対して格納されてもよい。例えば、画素が純粋な白（ｐｕｒｅ  ｗｈｉｔｅ）、純粋な黒（ｐｕｒｅ  ｂｌａｃｋ）または他のグレースケール（中間調）のカラーである場合、一つ以上の属性ビットが、この情報を符号化することができて、画素に対し、別々に格納されることができ、また、圧縮（例えば、可逆的な圧縮）されることができる。
【００５８】
ブロック５１２において、セルベースの圧縮は、電子文書の各チャネルに適用されることができる。このように、セルベースの圧縮は、Ｙ、ＣｂおよびＣｒチャネルの各々に対し、別々に適用されることができる。ブロック５１２の結果は、電子文書の圧縮されたバージョンを表すビットストリームであってもよい。
【００５９】
ブロック５１４では、セルベースの解凍を、電子文書の各チャネルに適用することができる。これは、電子文書のＹＣｂＣｒバージョンの再現に結果としてなることがある。しかしながら、セルベースの技術が非可逆圧縮を使用する場合、電子文書の再現されたバージョンがブロック５１０の電子文書と異なってもよい点に留意する必要がある。しかしながら、図５Ａに示される技術と同様に、電子文書のこれらのバージョンの違いは、小さくすることができ、したがって、人間によって認識されないようにすることもできる。加えて、ブロック５１６では、ブロック５１０で圧縮されて、格納される属性ビットに符号化される情報（もしあるならば）は、解凍され、電子文書の再現されたＹＣｂＣｒバージョンに統合されることができる。
【００６０】
ブロック５１８では、電子文書の再現されたＹＣｂＣｒバージョンが、その最初のＲＧＢまたはＣＭＹカラーモデルへ変換して戻されてもよい。これは、ブロック５２０におけるＲＧＢまたはＣＭＹの電子文書と同じまたはほぼ同様の電子文書の再現に、結果としてなる場合がある。
【００６１】
図５Ａおよび５Ｂに図示される圧縮技術は、単に例示のために示されていることを理解されたい。したがって、様々な代替技術が、本願明細書における実施形態によってさらに含まれうる。例えば、ＹＣｂＣｒカラーモデルへの変換、および、ＹＣｂＣｒカラーモデルからの変換は、省略されてもよい。更に、属性ビットの独立な圧縮、記憶および解凍が、省略されてもよい。
【００６２】
ｄ．  例示のセルベースの圧縮（Ｃｅｌｌ―Ｂａｓｅｄ  Ｃｏｍｐｒｅｓｓｉｏｎ）
セルベースの圧縮の一態様は、それが電子文書の各カラーチャネルを一つ以上のｍ×ｎ画素のセルに分割し、そして、部分的に独立あるいは完全に独立な方式で各セルを圧縮するというものであってもよい。例えば、ｍは８であり、ｎは４であってもよい。あるいは、ｍは８であり、同様に、ｎも８であってもよい。ｍおよびｎとして他の値が用いられてもよい。各セルは、どんなタイプの圧縮方法がそのセルのデータの圧縮に対して最も効率的であるか決定するために、評価されることができる。例えば、セルが、全体として、同じ色である画素から構成されている場合、そのセルのデータは、その色の表現およびおそらくいくらかの付加的なデータ（ｏｖｅｒｈｅａｄ  ｄａｔａ）の表現へと、非常に効率的に圧縮されることができる。しかしながら、セルが複雑な、多色の写真のようにリアルな画像の一部を含む場合、セルのデータはこのような高い圧縮率で圧縮されることは難しくなる。
【００６３】
図６は、電子文書におけるカラーチャネル６００における一連のセルを評価し、圧縮する方法を示す。列６０２の最も左のセルから始めて、各セルは、セルベースの技術に従って圧縮される。ある意味では、圧縮プロセスは、列６０２に沿って左から右に移動する。ついで、列６０４に対し、圧縮プロセスは、右から左に移動する。列６０６に対して、圧縮プロセスは、左から右にもう一度移動する。列６０８に対して、圧縮プロセスは、右から左にもう一度移動する。なお、カラーチャネル６００のセルは、異なる順で圧縮されてもよい。
【００６４】
上記の如く、所定のセル（注目セル）に対して使用される適した圧縮方法は、セルの中に含まれるデータに依存しうる。図７は、どの圧縮技術がセルに適用されるべきか決定する１つの可能な方法を示すフローチャートである。図７では、以下で更に詳細に説明される、例えばＤ１、Ｇ４、Ｐ２、Ｐ４およびＤＣＴのような、多くの圧縮方法に関連する。
【００６５】
ブロック７００で、画素情報が、所定のセル（注目セル）から集められてもよい。この情報は、セル内の最小の色値および最大の色値を含んでいてもよい。更に、色値のヒストグラムが、各セルに対して算出されてもよい。
【００６６】
本願明細書において、「色値（ｃｏｌｏｒ  ｖａｌｕｅ）」は、画素の色の数値的な表現を示していてもよい。例示の色値は、８ビットで表され、０−２５５の範囲であってもよいし、１６ビットで表され、０―６５５３５の範囲であってもよい。しかしながら、色値は、他の数のビットによって表されることができ、異なる範囲の値で表されることができる。更に、色値は、黒および／または白が、ある色の理論の下においては「色」であると考慮されない可能性がある場合であっても、黒、白、および黒と白との間の様々なグレーの中間調を表すのに用いることができる。
【００６７】
加えて、セルが色勾配を含むかどうかの評価が、実行されてもよい。この評価においては、セル内の色値が、双一次補間（ｂｉ―ｌｉｎｅａｒｌｙ  ｉｎｔｅｒｐｏｒａｔｉｏｎ）により４点、すなわち、例えば、セル内の４つの角における画素の色値の勾配により正確に表されることができるかどうか、判断されてもよい。セル内の角以外の画素の実際の色値が、画素の双一次補間により得られる色値の勾配閾値（ｇｒａｄｉｅｎｔ  ｔｈｒｅｓｈｏｌｄ）内にある場合には、そのセルは勾配圧縮（ｇｒａｄｉｅｎｔ  ｃｏｍｐｒｅｓｓｉｏｎ）（Ｇ４）の候補とされてもよい。
【００６８】
ブロック７０２では、セルの色値の範囲が決定され、色範囲閾値（ｃｏｌｏｒ  ｒａｎｇｅ  ｔｈｒｅｓｈｏｌｄ）と比較されてもよい。色値の範囲が色範囲閾値内にある場合、ブロック７０４において、Ｄ１圧縮がセルに適用されてもよい。そうでなければ、ブロック７０６では、セル内の画素が、双一次補間による４点の勾配により表現される（ブロック７００で決定されるように）場合、ブロック７０８では、Ｇ４圧縮がセルに適用されてもよい。セルが色勾配を含むかどうかの評価は、ブロック７００においてよりもむしろブロック７０６において実行されてもよい。
【００６９】
セルが色勾配を含まない場合、ブロック７１０では、セルが実質上２色のパターンを含むかどうかが決定されてもよい。この場合には、ブロック７１２では、Ｐ２圧縮が、セルに適用されてもよい。そうでなければ、ブロック７１４で、セルが実質上４色のパターンを含むかどうかが、判断されてもよい。この場合には、ブロック７１６で、Ｐ４圧縮がセルに適用されてもよい。セルが実質上４色のパターンを含まない場合、ブロック７１８で、離散コサイン変換（ＤＣＴ）圧縮がセルに適用されてもよい。
【００７０】
図７は、単にセルベースの圧縮の１つのありうる手順を例示している。他の手法が存在してもよく、そして、これらのブロックにおいては異なる圧縮方法を使用することもでき、および／または所定のセルに対してどの圧縮方法を使用するべきかについての判断に対し、異なる論理を適用してもよい。一般に、より効率的な圧縮方法（セルの圧縮表現を符号化するのに用いられるビットの数という点で）がより効率的でない圧縮方法より優先されるプロセスを、図７は例示する。以下では、様々な圧縮方法をより詳細に説明する。
【００７１】
ｉ．  Ｄ１圧縮（Ｄ１  Ｃｏｍｐｒｅｓｓｉｏｎ）
所定のセル（注目セル）の画素の全てが単一の色値を用いて表されることができる場合に、Ｄ１圧縮を使うことができる。これは、セル内のすべての画素が同じ色値を有する必要があるということではない。Ｄ１圧縮は、セルの最大色値と最小色値との差が予め定められた色範囲閾値内にあるときに、使われることができる。
【００７２】
例えば、セル内の各画素が０から２５５までの色値を示すと仮定する。色範囲閾値が３である場合に、すべての画素が７４、７５または７６のいずれかの色値を有する場合、このセルに対して、Ｄ１圧縮を適用することができる。存在する３つの色値のうちの１つ（例えば、中間の色値７５）が、セル内の全ての画素の色値を表すために用いられてもよい。
【００７３】
このようにして、セルを表すために必要なデータの量を、減らすことができる。この圧縮が非可逆性圧縮（損失性の圧縮）である場合であっても、閾値が十分に小さいときには、損失は人間の観察によっては認識されないようにすることができる。加えて、圧縮効率および画質は、色範囲閾値を変えることによって、互いにトレードオフの関係となりうる。例えば、色範囲閾値として１０を用いると、色範囲閾値として２を用いる場合に比べ、より効率的に圧縮できるが、画質が低下する可能性がある。
【００７４】
ある場合には、複数の隣接セル（例えば、行または列において隣接するセル）の全ては、Ｄ１圧縮および同一の色値を使用して、よく表現されることができる。このように、Ｄ１圧縮の方法は、色値によって符号化されるランレングス（ｒｕｎ  ｌｅｎｇｔｈ）符号化による圧縮を可能とする。いくつの続くセルにおいてＤ１圧縮および色値を使用して圧縮されるかについても、ランレングス符号化により表現することができる。あるいは、ランレングス符号化により、合計でいくつのセルがＤ１圧縮および色値を使用して圧縮されるかを表すことができる。
【００７５】
色値が所定の色値（デフォルト値（ｄｅｆａｕｌｔ  ｃｏｌｏｒ））である場合には、Ｄ１圧縮方法のバリエーション（Ｄ１Ｄ圧縮と呼ぶこともある）が使われることができる。ＹＣｂＣｒ色空間のＹチャネル、グレースケール色空間、および全てのＣＭＹＫ色空間において、デフォルト値は、０および２５５であってもよい。ＹＣｂＣｒ色空間のＣｂおよびＣｒ平面においては、デフォルト値は、１２８および２５５であってもよい。Ｄ１Ｄ圧縮は、Ｄ１圧縮よりいくらか効果的な符号化が可能である。限定された数のデフォルト値（例えば、２つ）だけが色空間にあるので、これらのデフォルトの色値は少数のビット（例えば、１つの色値につき１ビット）で表されることができる。従って、Ｄ１Ｄ圧縮によれば、各セルにつき必要となるビット数を、Ｄ１圧縮より少なくすることができる。
【００７６】
ｉｉ．  Ｇ４圧縮（Ｇ４  Ｃｏｍｐｒｅｓｓｉｏｎ）
上記の如く、セルの色値が双一次補間による４点の色勾配によって合理的によく表現されることができる場合に、Ｇ４圧縮を用いることができる。なお、４点は、それぞれ、セルの４つの角の画素に対応する。図８は、この方法の動作を例示する。ブロック８００および８０２は、８×８画素セルの画素の色値を表現する。個々の画素はｘ軸およびｙ軸を使用して配置することができ、各画素の色は画素と関連付けて、ｚ軸方向の高さによって表現される。（例えば、低い色値はｚ軸上の高さを小さくすることによって表され、その一方で、高い色値はｚ軸上の高さを大きくすることによって表されることができる。）
ブロック８００は、セル内の４点の色勾配の例である。角以外の画素は、角の画素の色値の間において円滑な変化を示すように、それぞれの色値を有する。セルがＧ４圧縮を使用して符号化されるかどうか判断するために、代表的な表現（例えばブロック８０２）が、セル内の角の画素の色値に基づいて形成されてもよい。例えば、双一次補間の方式を用いて、角以外の画素のそれぞれは、「提案された」（代表的な表現として提案された）色値と関連付けられてもよい。ブロック８０２に示すように、同じ提案された色値を有する画素は、２つまたは４つを単位にして分類されてもよい。より多くまたはより少ない画素の単位が用いられてもよい。それから、角以外の画素のそれぞれに対し、それぞれの提案された色値が、その画素の実際の色値と比較されてもよい。これらの色値の差が角以外の全ての画素に対し、勾配閾値より少ない場合、Ｇ４圧縮が使われてもよい。
【００７７】
ｉｉｉ  Ｐ２圧縮  （Ｐ２  Ｃｏｍｐｒｅｓｓｉｏｎ）
所定のセル（注目セル）の画素の全てが２つの色値を使用して表すことができる場合、Ｐ２圧縮を用いることができる。これは、セル内の全ての画素が、必ずしも、これらの２つの色値のうちの１つである場合に限らない。その代わりに、セル内の全ての色値が２つの色値の周辺に集まっている場合（例えば、２つの色値から所定の閾値以内である場合）、Ｐ２圧縮を使うことができる。例えば、セル内の画素が０と２５５との間の色値をとりうるが、全ての色値が７５、７６、１２４、または１２５のいずれかである場合、これらの色値のうちの、各群を代表する２つが、選択されてもよい。このように、７５の色値が、７５または７６の色値を有する画素の色を表現するために用いることができ、そして、１２４の色値を、１２４または１２５の色値を有する画素の色を表現するために用いてもよい。
【００７８】
セルがＰ２圧縮の候補であるかどうか判断するための評価の１つの方法を、図９に示す。セル９００は、２（二進数で００１０）、３（二進数で００１１）および１４（二進数で１１１０）の４ビットの色値を有する例示の実施形態の４×４画素のセルである。セル９００は２つより多くの色値を有するが、色値２および色値３を単一の色値（例えば、色値２および色値３のうちの１つ）によって表すことが可能であるので、Ｐ２圧縮をセル９００に対して使うことができる。
【００７９】
従って、セル９００は、Ｐ２圧縮について、３ステップのプロセスを使用して評価されることができる。第１ステップでは、ヒストグラムマスク（ｈｉｓｔｏｇｒａｍ  ｍａｓｋ）９０２が、セル９００に対して、判断に用いられてもよい。ｃ個の色値を有するセルに対して、ヒストグラムマスクは、ｃ／２ビットの長さであってもよい。例えば、セル９００は、１６個の色値を有する可能性があり、長さ８ビットのヒストグラムマスク９０２を有する。
【００８０】
更に、ヒストグラムマスク９０２の各ビットは、２つの連続する色値の異なる組を表わす。こうして、例えば、ヒストグラムマスク９０２の左端の色値は、０および１を表し、左端から２番目の色値は、２および３を表す。ヒストグラムマスク９０２内のあるビット（注目ビット）について、そのビットにより表される２つの色値のうちの少なくとも１つがセル９００内に存在する場合、そのビットは１に設定される。そうでなければ、ビットは、０に設定される。こうして、ヒストグラムマスク９０２に対して、色値２および３を示すビットおよび色値１４および１５を示すビットのみが、１に設定される。
【００８１】
加えて、クオリフィケーションマスク（ｑｕａｌｉｆｉｃａｔｉｏｎ  ｍａｓｋ）が、セルに対して判断に用いられてもよい。クオリフィケーションマスクにおいて、セルにおいて最も低い色値および最も高い色値を表しているビットは、０に設定されてもよい。さらに、最も低い色値を示すビットの右側にある１つ以上のビット、および最も高い色値を示すビットの左側にある１つ以上のビットを０に設定されてもよい。他の全てのビットは、１に設定されてもよい。こうして、クオリフィケーションマスク９０４において、左端から２番目にあるビットは、セル９００において最も低い色値である色値２を表すので、０に設定される。加えて、左端から２つ目のビットの右側に位置する２つのビットも、０に設定される。また、右端のビットも、そのセル内で最も高い色値である１４を表すので、０に設定される。右端のビットの左側の２つのビットも、０に設定される。
【００８２】
論理積（ｌｏｇｉｃａｌ  ａｎｄ）演算を、ヒストグラムマスクおよびクオリフィケーションマスクに実行してもよい。結果が０である（すなわち、全てのビットの結果が０である）場合、Ｐ２圧縮をこのセルの圧縮に使うことができる。例えば、そうでなければ、そのセルに対しては、Ｐ２圧縮を使わない。図９の論理積９０６は０であるので、セル９００はＰ２圧縮が適していると判断できる。しかしながら、セル９００の任意の１つの画素が色値８または色値９を含むように変えられた場合、セル９００はＰ２圧縮には適さないと判断されうる。
【００８３】
一つ以上の所定の色値（デフォルトの色値（ｄｅｆａｕｌｔ  ｃｏｌｏｒ  ｖａｌｕｅ））がセルに存在するときに、Ｐ２Ｄ圧縮とも呼ばれるＰ２圧縮のバリエーションが使われてもよい。上記のように、ＹＣｂＣｒ色空間のＹチャネル、グレースケールの色空間、および全てのＣＭＹＫ色空間については、デフォルト色値は、０および２５５であってもよい。ＹＣｂＣｒ色空間のＣｂおよびＣｒ平面において、デフォルト値は、１２８および２５５であってもよい。もし、セル内に、デフォルト色値のみが存在し、デフォルト色値以外の色値が存在しない場合、Ｐ２Ｄ圧縮を用いることができる。また、変形例として、各デフォルト色値の所定の閾値の範囲の色値がセル内に存在する場合には、Ｐ２Ｄ圧縮が用いられてもよい。Ｐ２Ｄ圧縮は、Ｐ２圧縮よりいくらか効率的な符号化が可能である。
【００８４】
ｉｖ．  Ｐ４圧縮（Ｐ４  Ｃｏｍｐｒｅｓｓｉｏｎ）
所定のセル（注目セル）の全ての画素が、３つまたは４つの色値を使用して表すことができるときに、Ｐ４圧縮が使われてもよい。例えば、ステップ７００で形成されるヒストグラムが、セル内には３つまたは４つの色値だけが存在することを示す場合、Ｐ４圧縮が用いられてもよい。
【００８５】
それ以外に、または、それに加えて、４つ以上の色値がセル内に表れているが、セル内に存在する全ての色値が、セルを表現するのに用いることができる４つの色値の周辺（例えば、４つの色値から所定の閾値の範囲内）に集まっている場合に、Ｐ４圧縮が用いられてもよい。例えば、所定の閾値が１であり、セルが１０、１１、５６、２１３、２１４、および２５５の色値を含む場合、例えば、色値１０、５６、２１３、および２５５によるＰ４圧縮が用いられてもよい。
【００８６】
ｖ．ＤＣＴ圧縮
ＤＣＴ圧縮は、いかなるカラーパターンのセルに対しても用いることができる。いくつかの実施形態では、セルがＤ１、Ｇ４、Ｐ２またはＰ４圧縮を使用して圧縮されない場合、最後の手段としてＤＣＴ圧縮が使われてもよい。ＤＣＴ圧縮を使用して圧縮されるセルに対しては、次のステップが実行されてもよい：ＤＣＴ変換、スケーリング、量子化、二次元に配列された係数配列の一次元のデータへの再配列、およびハフマン符号を用いたエントロピー符号化。いくつかの実施形態では、ＤＣＴ符号化により、Ｊｏｉｎｔ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ（ＪＰＥＧ）規格による係数のサブセットに従って、ハフマン符号化を用いて包括される量子化されたＤＣＴ係数の集合が得られてもよい。本願明細書において提示される圧縮方法のうち、ＤＣＴ圧縮は最も効率の低い圧縮方法である。
【００８７】
ｅ．  例示の実施形態のセルベースの圧縮の符号化（Ｃｅｌｌ―Ｂａｓｅｄ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｅｎｃｏｄｉｎｇ）
表１に、上記の圧縮方法のビットストリームの符号化の一例を示す。表１は、所定のｍ×ｎ画素セル（ｍ×ｎ画素の注目セル）が、圧縮される際にビットでコード化される方法を示す。本願明細書において示されない他の符号化も可能である。
表１：
2013258701.tif 000003
【００８８】
表１：各圧縮方法における圧縮されたビットストリームの符号化の例
「圧縮方法」（Ｃｏｍｐｒｅｓｓｉｏｎ  Ｍｅｔｈｏｄ）の列は、セルを符号化するために用いられる圧縮方法を示しており、上記の例示の実施形態の圧縮方法が、いくつかのバリエーションと併せて含まれている。「オペコード」（Ｏｐｃｏｄｅ）の列は、各圧縮方法を表す２―３ビットの表現を示している。いくつかの実施形態では、セルのオペコードは、セルの圧縮のビットストリーム符号の始めに配置されてもよい。Ｄ１／Ｄ１Ｄ圧縮を表すオペコードは、以降、「単色オペコード（ｓｉｎｇｌｅ−ｃｏｌｏｒ  ｏｐｃｏｄｅ）」と呼ぶことがある。同様に、Ｐ２／Ｐ２Ｄ圧縮を表すオペコードは、「２色オペコード（ｔｗｏ―ｃｏｌｏｒ  ｏｐｃｏｄｅ）」と呼ばれてもよい。そして、Ｐ４圧縮を表すオペコードは「４色オペコード（ｆｏｕｒ―ｃｏｌｏｒ  ｏｐｃｏｄｅ）」と呼ばれてもよく、Ｇ４圧縮を表すオペコードは「勾配演算コード（ｇｒａｄｉｅｎｔ  ｏｐｃｏｄｅ）」と呼ばれてもよく、そして、ＤＣＴ圧縮を表すオペコードは「ＤＣＴオペコード（ＤＣＴ  ｏｐｃｏｄｅ）」と呼ばれてもよい。
【００８９】
「オプション」（ｏｐｔｉｏｎｓ）の列には、コード化される圧縮方法に特有の一つ以上のオプションが含まれていてもよい。例えば、Ｄ１Ｄ圧縮方法は、セル全体を、２つの可能性のあるデフォルト値のうちの１つとして符号化する。オプション列のＶビットには、いずれのデフォルト値が符号化されるかが符号化されていてもよい（例えば、低いほうのデフォルト値に対し、Ｖ＝０とし、高いほうのデフォルト値に対しＶ＝１とする。）。
【００９０】
別の例として、例えば、Ｄ１圧縮方法は、可能性がある２５６の値のうちの１つにより、セル全体を符号化する。Ｄ１圧縮に対するオプションのＶ’ビットは、オプションに割り当てられたビットに対し、そのセルの値を符号化する１バイトが続くことを示す。Ｄ１ＤおよびＤ１圧縮に対し、ランレングスのバイト（ランレングスの列に関する下記の考察参照）が存在するかどうかを、Ｒビットは示す。
【００９１】
さらなる例として、Ｐ２圧縮方法は、Ｌビットを含んでいてもよい。Ｌビットは、Ｌビットに続いて、２つの色値が存在することを示す。これらの色値は、Ｐ２圧縮方法で圧縮されたセル内の全ての色値を表すのに使用される色値であってもよい。同様に、Ｐ４圧縮方法は、Ｌ’ビットを含んでいてもよい。Ｌ’ビットは、Ｌ’ビットの後に、４つの色値が存在することを示していてもよい。
これらの色値は、Ｐ４圧縮方法で圧縮されたセル内の全ての色値を表すのに使用される色値であってもよい。
【００９２】
「色値」（Ｃｏｌｏｒ  Ｖａｌｕｅｓ）の列は、圧縮されたセルを表すのに用いられる一つ以上の色値を含んでいてもよい。上述のように、Ｄ１、Ｐ２、Ｐ４圧縮方法は、それぞれ、１つ、２つおよび、４つの色値を特定する。各色値は、適切な数のビット（例えば、０―２５５の色値の範囲の８ビット）によって表されることができる。
【００９３】
「ラスター」（ｒａｓｔｅｒ）の列は、セル内の各画素の色値について、１画素につき１ビットまたは２ビットの表現（例えば、ビットマップ）を表していてもよい。例えば、Ｐ２Ｄ圧縮およびＰ２圧縮においては、セルにおいて各画素に２色の色値のうちのいずれが使われるか表すように１画素につき１ビットを使用してもよい。同様に、Ｐ４圧縮においては、セル内の各画素に４色の色値のうちのいずれが使われているかを表すように１画素につき２ビットを使用してもよい。ラスター列に記載の表現は、ランレングス符号化を使用して、更に圧縮されてもよい。
【００９４】
「ランレングス」（Ｌｅｎｇｔｈ）の列は、ランレングスの任意の１バイトの符号を含むことができる。いくつかの実施形態では、単一の色値がセル全体を表すのに用いることができる長さの列は、Ｄ１ＤおよびＤ１圧縮についてのみ使われてもよい。ある場合には、画像内の２つ以上の連続するセルの全てが、同じ単一の色値を使用して符号化されることが可能であってもよい。このように、ランレングスの列のバイトは、Ｄ１ＤまたはＤ１圧縮における、同じ色値を使用して表現できる連続するセルの数を示していてもよい。
【００９５】
表１には明確には示されていないが、ＤＣＴ圧縮の結果、ＤＣＴ圧縮方法により符号化された結果に続くＤＣＴオペコードのビットストリームによって表されてもよい。
【００９６】
ｆ．  例示の実施形態のセルベースの解凍（Ｃｅｌｌ―Ｂａｓｅｄ  Ｄｅｃｏｍｐｒｅｓｓｉｏｎ）
一旦、多くのセルが、例えば、上記の圧縮方法および符号化を使用して圧縮されると、それらは効率的に格納されることができ、および／またはケーブルまたはネットワークを通じて効率的に送信されることができる。それにもかかわらず、ある時点で、セルを、オリジナルの画像に近いものに解凍することができる。本願明細書において記載されているセルベースの圧縮技術は、損失性（ｌｏｓｓｙ）となる可能性があるので、解凍された画像は、少なくともある程度は、オリジナル画像と異なる可能性がある。しかしながら、多くの場合に、この違いは、人間によって認識されにくいか、またはオリジナル画像の許容可能な変形版であると見做されうる。
【００９７】
表１に記載の圧縮符号化によって符号化されたセルは、以下の通りに復号化および解凍することができる。所定のセル（注目セル）の符号化のために、オペコードを読む。オペコードの値に基づいて、任意の適用できるオプション、色値、ラスタおよび／またはランレングスが、オペコードに続くビットから判断されてもよい。これらのパラメータから、解凍されたバージョンのセルが、再現されてもよい。それから、画像が再現されるまで、次のオペコードの読み込み等が行われる。
【００９８】
例えば、オペコードが、Ｄ１Ｄ符号化を示す０００である場合、Ｖビットが色値を決定するのに読み込まれ、Ｒビットがランレングスが存在するかどうかを決定するのに読み込まれてもよい。それから、Ｖビットによって示されるデフォルト色値を呈している各セルのすべての画素により、ランレングスの長さに相応した多くのセルが作られる。
【００９９】
オペコードが、Ｄ１圧縮を示す００１である場合、Ｖ’ビットおよび色値フィールド（ｃｏｌｏｒ  ｖａｌｕｅ  ｆｉｅｌｄ）が、色値を決定するのに読み出されてもよい。Ｒビットが、ランレングスが存在するかどうか判断するのに、読み込まれてもよい。それから、色値のフィールドによって示される色値を呈している各セルのすべての画素により、ランレングスの長さに相応した多くのセルが作られてもよい。
【０１００】
オペコードが、Ｐ２Ｄ圧縮を示す０１０である場合、ラスターフィールドが読み込まれてもよい。
ラスタフィールド（ｒａｓｔｅｒ  ｆｉｅｌｄ）のビットマップに従って、低いほうのデフォルト色値または高いほうのデフォルト色値を呈する各画素によりセルが作られる。
【０１０１】
オペコードが、Ｐ２圧縮を示す０１１である場合、Ｌビット、色値フィールドおよびラスターフィールドが読み込まれてもよい。それから、セルは、ラスタフィールドのビットマップに従って、２つの色値のうちの１つを呈する各画素により、セルが作られてもよい。
【０１０２】
オペコードが、Ｐ４圧縮を示す１００である場合、Ｌ’ビット、色値フィールドおよびラスタフィールドが読み込まれてもよい。それから、ラスタフィールドのビットマップに従って、４つの色値のうちの１つを呈する各画素により、セルが作られてもよい。
【０１０３】
オペコードが、Ｇ４符号化を示す１０１である場合、色値フィールドが、４つの角の画素の色値を判断するのに読み込まれてもよい。それから、色値フィールドにより示される色値のうちの１つを呈する各角の画素と、角以外の画素の色値を判断するのに用いられる双一次補間により、セルが作られてもよい。
【０１０４】
オペコードが、ＤＣＴ圧縮を示す１１である場合、ＤＣＴ圧縮の結果が読み込まれ、このＤＣＴ符号化に従って、セルが作られてもよい。
【０１０５】
ｇ．  圧縮効率（Ｃｏｍｐｒｅｓｓｉｏｎ  Ｅｆｆｉｃｉｅｎｃｙ）
本願明細書において記載されているセルベースの圧縮技術は、非常に効率的となりうる。実際には、平均して２０：１の圧縮比が認められた。以下の例により、この効率を説明する。
【０１０６】
高速印刷システムが、ホスト−プリントデータ経路を使用して、１８０ページ／分（３ページ／秒）を印刷すると仮定する。これらのページの解像度は、８インチ×１０インチのページにおいて６００ドット／インチ（ｄｐｉ）であると仮定する。そして、１バイトの色値に符号化される３つのカラーチャネルが使われる。こうして、１秒に転送される圧縮前のデータの総量は６００（ドット）×６００（ドット）×１０（インチ）×８（インチ）×３（カラーチャネル）×３（ページ）であり、約２４７メガバイトに等しい。上記のセルベースの圧縮技術を使用して、このデータ量は、平均して、約１２．４メガバイトに減少することができる。
【０１０７】
４．  例示の実施形態における演算（Ｏｐｅｒａｔｉｏｎ）
図１０は、例示の実施形態のフローチャートである。このフローチャートで例示されるステップは、印刷装置１００のような印刷装置、および／または、コンピュータ３００のようなコンピュータにより実行することができる。更に、個々の各ステップは、複数のコンピュータで分割して実行される態様であってもよい。
【０１０８】
ステップ１０００では、ｍ×ｎ画素セルが、入力画像から得られてもよい。入力画像はｍ×ｎより多くの画素を含んでいてもよく、そして、ｍ×ｎ画素セルのｍ×ｎ画素の各々は色値を有していてもよい。いくつかの実施形態では、ｍ×ｎ画素セルは、入力画像の単一のカラーチャネルの色値のみと関連付けられていてもよい。
【０１０９】
ステップ１００２では、ｍ×ｎ画素セルの特徴が判断されてもよい。特徴を判断する工程には、ｍ×ｎ画素セルの画素のうち最も低い色値および最も高い色値を判断する工程を含んでいてもよい。
【０１１０】
特徴を判断する工程は、ｍ×ｎ画素セルについての色値のヒストグラムを決定する工程、およびヒストグラムから、ｍ×ｎ画素セル内の画素の色値のうち、２番目に低い色値および２番目に高い色値を得る工程を更に含んでいてもよい。２番目に低い色値は、最も低い色値に隣接している値であってもよいし、または、最も低い色値からある閾値の範囲内にある値であってもよい。また、２番目に高い色値は、最も高い色値に隣接している値であってもよいし、または、最も高い色値からある閾値の範囲内にある値であってもよい。それから、ヒストグラムから、最も低い色値、２番目に低い色値、２番目に高い色値および最も高い色値以外の色値が、ｍ×ｎ画素セル内には存在しないと判断される。複数の出力色値を選択する工程は、最も低い色値および２番目に低い色値のうちの１つと、および２番目に高い色値および最も高い色値のうちの１つと、を選択する工程を含んでいてもよい。
【０１１１】
ステップ１００４では、最も高い色値と最も低い色値との差が算出されてもよい。ステップ１００６では、この差が差の閾値以下かどうかが決定されてもよい。
【０１１２】
差が閾値以下である場合、それから、ステップ１００８において、出力の色値が、最も高い色値と最も低い色値との間に含まれる色値から選択されてもよい。また、ステップ１００８では、出力の色値の第１の表現が、出力媒体に書き込まれてもよい。第１の表現は、単色オペコードおよび出力色値の表示を含んでいてもよい。差が閾値より大きい場合、それから、ステップ１０１０において、複数の出力色値が選択され、複数の出力色値の第２の表現が出力媒体に書き込まれてもよい。
【０１１３】
出力媒体に書き込まれる表現（例えば、第１の表現または第２の表現）に基づいて、ｍ×ｎ画素のセルの近似を、出力装置に再形成することができる。出力装置は、出力媒体と密接に関係していてもよいし、関係していなくてもよい。例えば、出力媒体が、印刷装置内のデータ格納部（ｄａｔａ  ｓｔｏｒａｇｅ）であり、出力装置がその印刷装置であってもよい。あるいは、出力媒体がコンピュータ内のデータ格納部であり、出力装置が印刷装置であってもよい。
【０１１４】
複数の出力色値は、２つの出力色値から構成されていてもよく、そして、第２の表現は、２色オペコード、２つの出力色値それぞれの表示、およびｍ×ｎ画素セルの各画素を２つの出力色値のうちの１つと関連付ける、ｍ×ｎ画素セルの画素ごとのビットマップを含んでいてもよい。あるいは、複数の出力色値が、最多で４つの出力色値から構成されており、第２の表現が、４色のオペコード、最多で４つの出力色値の各々の表示、およびｍ×ｎ画素セルの各画素を最多で４つの出力色値のうちの１つと関連付ける、ｍ×ｎ画素セルの画素ごとのビットマップを含んでいてもよい。
【０１１５】
いくつかの実施形態では、特徴を判断する工程は、ｍ×ｎ画素セルについての色値のヒストグラムを決定する工程と、ヒストグラムから、ｍ×ｎ画素セル内の画素の第１の中間の色値および第２の中間の色値を得る工程とを更に含んでいてもよい。第１の中間の色値および第２の中間の色値の各々は、最も低い色値と最も高い色値との間にあってもよい。それから、ヒストグラムから、（ｉ）最も低い色値と、（ｉｉ）第１の中間の色値と、（ｉｉｉ）第２の中間の色値と、（ｉｖ）最も高い色値と、（ｖ）最も低い色値、第１の中間の色値、第２の中間の色値、および最も高い色値のうちの１つに隣接する１以上の色値と、以外の色値が、ｍ×ｎ画素セル内には存在しないと判断されてもよい。この場合、複数の出力色値を選択する工程は、４つの出力色値としての、最も低い色値、第１の中間の色値、第２の中間の色値、および最も高い色値のそれぞれと同一またはその近傍の色値を選択する工程を含んでいてもよい。あるいは、２つ以上の中間の色値が、使われてもよい。
【０１１６】
ある実施形態においては、ｍ×ｎ画素セル上にＤＣＴ圧縮演算を実行する工程を更に含んでいてもよい。従って、複数の出力色値はＤＣＴ演算の結果に基づいていてもよく、第２の表現はＤＣＴオペコードおよびＤＣＴ演算の結果を含んでいてもよい。
【０１１７】
それに代えて、または、それに加えて、複数の出力色値は、４つの出力色値から構成されていてもよい。４つの出力色値の各々は、ｍ×ｎ画素セルの４つの角の色値のうちの一つであってもよく、第２の表現は勾配オペコードおよび４つの出力色値の各々の表示を含んでいてもよい。さらに、ある場合には、セルの特徴を判断する工程は、更に、４つの出力色値の双一次補間に基づいて、ｍ×ｎ画素のテンプレートセットを取得する工程と、ｍ×ｎ画素セルの色値（例えば、画素値）をテンプレートセットの色値と比較する工程と、ｍ×ｎ画素セルの色値がテンプレートセットの色値に少なくともほぼ一致すると判断する工程と、を含んでいてもよい。
【０１１８】
図１１Ａおよび１１Ｂは、セルベースの圧縮をさらに説明する、他の例示の実施形態のフローチャートである。ステップ１１００では、ｍ×ｎ画素セルは、入力画像から得られてもよい。入力画像はｍ×ｎ画素より多くの画素を含んでいてもよく、ｍ×ｎ画素セルのｍ×ｎ個の画素の各々は色値を有していてもよい。
【０１１９】
ステップ１１０２では、ｍ×ｎ画素セルの特徴が、判断されてもよい。特徴を判断する工程は、ｍ×ｎ画素セルの画素の色値を決定する工程を含んでいてもよい。
【０１２０】
ステップ１１０４では、最も高い色値と最も低い色値との差が、算出されてもよい。ステップ１１０６では、この差が、差の閾値と比較されてもよい。
【０１２１】
差が閾値以下である場合、それから、ステップ１１０８において、最も高い色値と最も低い色値との間に含まれる出力色値が選択されてもよい。加えて、出力色値の第１の表現が、出力媒体に書き込まれてもよい。第１の表現は、単色オペコードおよび出力色値の表示を含んでいてもよい。
【０１２２】
差が閾値より大きい場合、それから、ステップ１１１０において、ｍ×ｎ画素セルの色値が、実質的に、２つの色値から構成されているかどうかが決定されてもよい。（ｉ）セル内に２つの色値だけが存在する場合、（ｉｉ）セル内には３つの色値が存在し、それらの３つの色値のうちの少なくとも２つは、数として連続している場合、（ｉｉｉ）セル内に４つの色値が存在し、これらの色値のうちの少なくとも２つの組み合わせが数として連続している場合、（ｉｖ）セル内の全ての色値が、１または２つの色値の周辺に集まっている場合、または、（ｖ）セル内の色値の他の考察に基づいて、ｍ×ｎ画素セルの色値は、実質的に２つの色値から構成されていると考えられてもよい。
【０１２３】
ｍ×ｎ画素セルの色値が実質的に２つの色値から構成されている場合、それから、ステップ１１１２において、２つの色値の第２の表現が出力媒体に書き込まれてもよい。第２の表現は、２色オペコード、２つの色値の各々の表示、およびｍ×ｎ画素セル内の各画素を２つの色値のうちの１つと関連付ける、ｍ×ｎ画素セルの画素ごとのビットマップを含んでいてもよい。
【０１２４】
ｍ×ｎ画素セルの色値が実質的に２つより多い（３つ以上の）色値から構成されている場合、それから、ステップ１１１４において、ｍ×ｎ画素セルの色値が、実質的に、３つまたは４つの色値から構成されているかどうかが決定されてもよい。（ｉ）セル内に３つまたは４つの色値だけ存在する場合、（ｉｉ）セル内に５〜８つの色値が存在し、これらの色値は、少なくとも２つが数として連続している場合、（ｉｉｉ）セル内の全ての色値が、３または４つの色値の周辺に集まっている場合、または、（ｉｖ）セル内の色値の他の考察に基づいて、ｍ×ｎ画素セル内の色値は、実質的に３つまたは４つの色値から構成されていると見做されてもよい。
【０１２５】
ｍ×ｎ画素セルの色値が実質的に３つまたは４つの色値から構成されている場合、それから、ステップ１１１６において、３つまたは４つの色値の第３の表現が出力媒体に書き込まれてもよい。第３の表現は、４色のオペコード、３つまたは４つの色値の各々の表示、およびｍ×ｎ画素セル内の各画素を３つまたは４つの色値のうちの１つと関連付ける、ｍ×ｎ画素セルの画素ごとのビットマップを含んでいてもよい。
【０１２６】
ｍ×ｎ画素セルの色値が、実質的に４つ以上の色値から構成されている場合、それから、ステップ１１１８において、離散コサイン変換（ＤＣＴ）の演算が、ｍ×ｎ画素セルに対して実行されてもよく、第４の表現が出力媒体に書き込まれてもよい。第４の表現は、ＤＣＴオペコードおよびＤＣＴ演算の結果を含んでいてもよい。
【０１２７】
５．結論
本願に記載された具体的な実施形態は、様々な態様の説明を意図しており、本発明はこれらの実施形態に限定されるものではない。当業者に明らかなように、その趣旨および範囲を逸脱しない範囲で、多くの修正変更がなされてもよい。本発明の範囲内の機能的に等価な方法および装置は、本願明細書において列挙されるそれらに加えて、上記の説明から明らかなものである。この種の修正変更は、添付の請求の範囲の範囲内に入ることを意図している。
【０１２８】
図示の、あるいは、本願明細書において述べられる、梯子図、シナリオおよびフローチャートの一部または全部に関して、各ブロックおよび／または通信は、例示の実施形態に従って、情報の処理および／または情報の通信を表していてもよい。別の例示の実施形態は、この種の例示の実施形態の範囲内に含まれていてもよい。さらに、より多いあるいはより少ないブロックおよび／または機能が、本願明細書において述べられる梯子図、シナリオおよびフローチャートのいずれかと共に用いられてもよく、一部で、または、全体として、これらの梯子図、シナリオおよびフローチャートは互いに結合されてもよい。
【０１２９】
情報の処理を表すステップおよびブロックは、本願明細書において説明された方法や技術の具体的な論理的機能を実行するように構成される電子回路に対応していてもよい。その代わりに、あるいはそれに加えて、情報の処理を示すステップまたはブロックは、モジュール、セグメント、またはプログラムコード（関連したデータを含む）の一部に、対応していてもよい。プログラムコードは、方法または技術における特定の論理的機能または動作を実行するプロセッサによって実行可能な一つ以上の命令を含んでいてもよい。プログラムコードおよび／または関連するデータは、任意の形態の、例えばディスク駆動装置、ハードディスクまたは他の記憶媒体を含む記憶装置のような、コンピュータ読み取り可能な記録媒体にも格納することができる。
【０１３０】
コンピュータ読み取り可能な記録媒体は、例えばレジスタ・メモリ、プロセッサ・キャッシュおよび／またはランダム・アクセス・メモリ（ＲＡＭ）のような短い期間にデータを格納するコンピュータ読み取り可能な記録媒体等の、非一時的なコンピュータ読み取り可能な記録媒体を含んでいてもよい。コンピュータ読み取り可能な記録媒体は、例えば、リードオンリーメモリ（ＲＯＭ）、光ディスクまたは磁気ディスク、および／またはＣＤ―ＲＯＭ（ＣＤ―ＲＯＭ）等の、二次的あるいは持続的な長期保存可能な記録媒体のような、より長い期間、プログラムコードおよび／またはデータを格納する非一時的なコンピュータ読み取り可能な記録媒体を含んでいてもよい。コンピュータ読み取り可能な記録媒体は、他の任意の揮発性あるいは不揮発性の記憶装置でもあってもよい。コンピュータ読み取り可能な記録媒体は、例えば、コンピュータ読み取り可能な格納媒体および／または有形の記憶装置と考えられてもよい。
【０１３１】
方法は、以下を含む：コンピュータにより、ｍ×ｎ以上の画素を含む入力画像から、画素のそれぞれが色値を有するｍ×ｎ画素セルを得る工程と、前記コンピュータにより、前記ｍ×ｎ画素セルにおける最も高い色値と、最も低い色値と、を決定する工程を含む、前記ｍ×ｎ画素セルの特徴を判断する工程と、前記コンピュータにより、前記最も高い色値と前記最も低い色値との間の差を算出する工程と、前記差が閾値差以下である場合、前記コンピュータにより、前記最も高い色値と、前記最も低い色値との間に含まれる色値から、１の出力色値を選択し、単色オペコードと、前記出力色値の表示と、を含む、前記出力色値の第１の表現を出力媒体に書き込む工程と、前記差が前記閾値差より大きい場合、前記コンピュータにより、複数の出力色値を選択し、前記複数の出力色値の第２の表現を前記出力媒体に書き込む工程。
【０１３２】
上記の方法において、前記ｍ×ｎ画素セルは、前記入力画像の単一のカラーチャンネルにおける複数の色値と関連付けられている。
【０１３３】
上記の方法において、前記複数の出力色値は、２つの出力色値を含み、前記第２の表現は、２色演算コードと、前記２つの出力色値のそれぞれの表示と、前記ｍ×ｎ画素セルの各画素を、前記２つの出力色値のうちの１つと関連付ける前記ｍ×ｎ画素セルの画素ごとのビットマップと、を含む。
【０１３４】
上記の方法において、前記特徴を判断する工程は、前記ｍ×ｎ画素セルにおける色値のヒストグラムを決定する工程と、前記ヒストグラムから、前記ｍ×ｎ画素セル内の色値のうち、前記最も低い色値からある閾値の範囲内にある２番目に低い色値と、前記最も高い色値から前記ある閾値の範囲内にある２番目に高い色値と、を取得する工程と、前記ヒストグラムから、前記ｍ×ｎ画素セルには、前記最も低い色値と、前記２番目に低い色値と、前記２番目に高い色値と、前記最も高い色値と、以外の色値が存在しないと判断する工程と、を含み、前記複数の出力色値を選択する工程は、前記最も低い色値と前記２番目に低い色値とのうちの１つと、前記２番目に高い色値と前記最も高い色値とのうちの１つと、を選択する工程を含む。
【０１３５】
上記の方法において、前記複数の出力色値は、最大４つの出力色値からなり、前記第２の表現は、４色演算コードと、前記最大４つの出力色値の各々の表示と、前記ｍ×ｎ画素セル内の各画素を、前記最大４つの出力色値のうちの１つと関連付けるｍ×ｎ画素セルの画素ごとのビットマップと、を含む。
【０１３６】
上記の方法において、前記特徴を判断する工程は、前記ｍ×ｎ画素セルの色値のヒストグラムを決定する工程と、前記ヒストグラムから、前記最も低い色値と前記最も高い色値との間にそれぞれ存在する第１の中間色値と、第２の中間色値とを取得する工程と、前記ヒストグラムから、前記最も低い色値と、前記第１の中間色値と、前記第２の中間色値と、前記最も高い色値と、前記最も低い色値と、前記第１の中間色値と、前記第２の中間色値と、前記最も高い色値と、のうちの１つに隣接する１つ以上の色値と、以外の色値が、前記ｍ×ｎ画素セルに存在しないと判断する工程と、をさらに含み、前記複数の出力色値を選択する工程は、前記最も低い色値と、前記第１の中間色値と、前記第２の中間色値と、前記最も高い色値と、のそれぞれ、またはそれらの近傍の色値を、前記４つの出力色値として選択する工程を含む。
【０１３７】
上記の方法において、前記ｍ×ｎ画素セル上において離散コサイン変換（ＤＣＴ）を実行する工程をさらに含み、前記複数の出力色値は、前記ＤＣＴの演算結果に基づいており、前記第２の表現は、ＤＣＴオペコードと、前記ＤＣＴ演算結果を含む。
【０１３８】
上記の方法において、前記複数の出力色値は、４つの出力色値から構成されており、前記４つの出力色値のそれぞれは、前記ｍ×ｎ画素セルの角の色値であり、前記第２の表現は、勾配オペコードと、前記４つの色値の各々の表示と、を含む。
【０１３９】
上記の方法において、前記特徴を判断する工程は、前記４つの出力色値の双一次補間に基づいて、ｍ×ｎの画素のテンプレートセットを取得する工程と、前記ｍ×ｎ画素セルの色値を前記テンプレートセットのｍ×ｎの画素の色値と比較する工程と、前記ｍ×ｎ画素セルの画素の色値が、前記テンプレートセットにおけるｍ×ｎの画素の色値と、少なくともほぼ一致すると決定する工程と、を含む。
【０１４０】
上記の方法において、前記出力媒体に書き込まれる表現に基づいて、出力装置に、ｍ×ｎ画素セルの色値の近似値を再形成する工程をさらに含む。
【０１４１】
非一時的なコンピュータ読み取り可能な記録媒体は、コンピュータによる実行において、前記コンピュータに、上記のいずれかに記載の方法の動作を実行させるプログラム命令を格納する。
【０１４２】
コンピュータは、プロセッサと、データ記憶装置と、前記データ記憶装置に格納され、前記コンピュータによる実行において、前記コンピュータに、上記のいずれかに記載の方法の動作を実行させるプログラム命令を備える。
【０１４３】
プログラムは、コンピュータによる実行において、前記コンピュータに上記のいずれかに記載の方法の動作を実行させるプログラム。
【０１４４】
方法は、以下を含む：コンピュータにより、ｍ×ｎ以上の画素を含む入力画像から、画素のそれぞれが色値を有するｍ×ｎ画素セルを得る工程と、前記コンピュータにより、前記ｍ×ｎ画素セル内の画素の色値を判断する工程を含む、前記ｍ×ｎ画素セルの特徴を判断する工程と、前記コンピュータにより、前記色値のうち、最も高い色値と最も低い色値との間の差を算出する工程と、前記差が閾値差以下である場合、前記コンピュータにより、前記最も高い色値と、前記最も低い色値との間に含まれる色値から１の出力色値を選択し、単色オペコードと、前記出力色値の表示と、を含む、前記出力色値の第２の表現を、出力媒体に書き込む工程と、他の場合において、前記ｍ×ｎ画素セルの前記色値が実質的に２つの色値から構成されている場合、前記コンピュータにより、２色オペコードと、前記２つの出力色値のそれぞれの表示と、前記ｍ×ｎ画素セル内の各画素を、前記２つの出力色値のうちの１つと関連付ける、前記ｍ×ｎ画素セルの画素ごとのビットマップと、を含む、第２の表現を前記出力媒体に書き込む工程と、さらに他の場合において、前記ｍ×ｎ画素セルの前記色値が実質的に３つまたは４つの色値から構成されている場合、前記コンピュータにより、４色オペコードと、前記３つまたは４つの色値のそれぞれの表示と、前記ｍ×ｎ画素セルの各画素を、前記３つまたは４つの色値のうちの１つと関連付ける、前記ｍ×ｎ画素セルの画素ごとのビットマップと、を含む第３の表現を前記出力媒体に書き込む工程と、さらに他の場合において、前記ｍ×ｎ画素セルの前記色値が、実質的に４つより多い色値から構成されている場合、前記コンピュータにより、前記ｍ×ｎ画素に対して離散コサイン変換（ＤＣＴ）の演算を実行し、ＤＣＴオペコードと、前記ＤＣＴ演算の結果と、を含む、第４の表現を前記出力媒体に書き込む工程。
【０１４５】
様々な態様および例示の実施形態が本願明細書において開示されているが、他の態様および実施形態が当業者にとって明らかになるであろう。本明細書において開示されている様々な態様および例示の実施形態は、以下の特許請求の範囲によって示される範囲および趣旨において説明の目的で示されたものであり、限定を目的とするものではない。
【産業上の利用可能性】
【０１４６】
本発明は、デジタル画像のセルベースの圧縮（Ｄｉｇｉｔａｌ  ＩｍａｇｅｓのＣｅｌｌ―Ｂａｓｅｄ  Ｃｏｍｐｒｅｓｓｉｏｎ）に適用できる。
【符号の説明】
【０１４７】
１００  印刷装置
１０２  トレイ
１０４  給紙カセット
１０６  ユーザ・インタフェース
１０８  スキャナー素子
１１０  筐体
２００，３００  コンピュータ
２０２  プロセッサ
２０４  データ記憶部
２０６  入出力機能
２０８  システムバス
３０２  スキャナ機能
３０４  印刷機能
３０６  スキャン−ホストデータ経路
３０８  ホスト−プリントデータ経路
３１０  スキャン−プリントデータ経路
【図１】
2013258701.tif 000004
【図２】
2013258701.tif 000005
【図３】
2013258701.tif 000006
【図４】
2013258701.tif 000007
【図５Ａ】
2013258701.tif 000008
【図５Ｂ】
2013258701.tif 000009
【図６】
2013258701.tif 000010
【図７】
2013258701.tif 000011
【図８】
2013258701.tif 000012
【図９】
2013258701.tif 000013
【図１０】
2013258701.tif 000014
【図１１Ａ】
2013258701.tif 000015
【図１１Ｂ】
2013258701.tif 000016
【外国語明細書】
Title:            Cell-Based Compression of Digital Images
Inventors:  
Guo Li
Kenneth A. Schmidt 
Dongpei Su
Stephen L. Schafer
Alfred Abkarian
Sheng Li
Michael M. Chang
FIELD OF THE INVENTION
[0001]      The present invention relates to Cell-Based Compression of Digital Images.
Background
[0002]      In recent years, various types of printing devices have become popular for both business and consumer use.  In addition to traditional black and white printers, color printers, scanners, copiers, fax machines, and other components are now common.  Multi-function peripherals (MFPs), that support two or more of these functions, are also widely available.  As these devices have grown more prevalent, they are being used for processing of more sophisticated and complicated documents.  
CITATION LIST
PATENT LITERATURE
[0003]      
US patent No. 5,915,079 
Summary
TECHNICAL PROBLEM
[0004]      The present invention may provide method for cell-based compression of digital images. 
SOLUTION TO PROBLEM
[0005]      In an example embodiment, an m x n pixel cell may be obtained from an input image.  The input image may contain more than m x n pixels, and each of the m x n pixels in the m x n pixel cell may have a respective color value.  A characterization of the m x n pixel cell may be determined.  Determining the characterization may involve determining a lowest color value and a highest color value of the pixels in the m x n pixel cell.  A difference between the highest color value and the lowest color value may be calculated.  If the difference is less than or equal to a threshold difference, an output color value between the highest color value and the lowest color value, inclusively, may be selected, and a first representation of the output color value may be written to an output medium.  The first representation may include a single-color opcode and an indication of the output color value.  If the difference is greater than the threshold difference, multiple output color values may be selected, and a second representation of the multiple output color values may be written to the output medium.
[0006]      In another example embodiment, an m x n pixel cell may be obtained from an input image.  The input image may contain more than m x n pixels, and each of the m x n pixels in the m x n pixel cell may have a respective color value.  A characterization of the m x n pixel cell may be determined, where determining the characterization may involve determining color values of the pixels in the m x n pixel cell.  A difference between a highest color value and a lowest color value of the color values may be determined.  If the difference is less than or equal to a threshold difference, an output color value between the highest color value and the lowest color value, inclusively, may be selected.  A first representation of this output color value may be written to an output medium.  The first representation may include a single-color opcode and an indication of the output color value.  If the color values of the m x n pixel cell substantially consist of two color values, a second representation of the two color values may be written to the output medium.  The second representation may include a two-color opcode, an indication of each of the two color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two color values.  If the color values of the m x n pixel cell substantially consist of three or four color values, a third representation of the three or four color values may be written to the output medium, where the third representation may include a four-color opcode, an indication of each of the three or four color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the three or four color values.  If the color values of the m x n pixel cell substantially consist of more than four color values, a discrete cosine transformation (DCT) operation may be performed on the m x n pixel cell, and a fourth representation may be written to the output medium.  The fourth representation may include a DCT opcode and a result of the DCT operation.
[0007]      Additional embodiments may include a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations in accordance with either or both of the example embodiments above.  
[0008]      Further embodiments may include a computing system comprising at least one processor, data storage, and program instructions in the data storage that, upon execution by the at least one processor, cause the computing system to operate in accordance with either or both of the example embodiments above.
[0009]      These as well as other aspects, advantages, and alternatives will become apparent to those of ordinary skill in the art by reading the following detailed description with reference where appropriate to the accompanying drawings.  Further, it should be understood that the description provided in this summary section and elsewhere in this document is intended to illustrate the claimed subject matter by way of example and not by way of limitation.
ADVANTAGEOUS EFFECTS
[0010]      According to the present invention, method for cell-based compression of digital images may be provided.
Brief Description of the Drawings
[0011]      Figure 1 depicts a printing device, according to an example embodiment.
[0012]      Figure 2 is a block diagram illustrating computing components of a printing device, according to an example embodiment.
[0013]      Figure 3 is a block diagram illustrating various data paths involving a printing device, according to an example embodiment.
[0014]      Figure 4 depicts an example image that may be contained in an electronic document, according to an example embodiment.
[0015]      Figure 5A depicts an example compression / decompression technique, according to an example embodiment.
[0016]      Figure 5B depicts another example compression / decompression technique, according to an example embodiment.
[0017]      Figure 6 depicts a method of evaluating and compressing a series of m x n pixel cells, according to an example embodiment.
[0018]      Figure 7 depicts a compression technique, according to an example embodiment.
[0019]      Figure 8 depicts aspects of gradient compression, according to an example embodiment.
[0020]      Figure 9 depicts aspects of two-color compression, according to an example embodiment.
[0021]      Figure 10 is a flow chart, according to an example embodiment.
[0022]      Figures 11A and 11B are another flow chart, according to an example embodiment.
Detailed Description
[0023]      Example methods and systems are described herein.  Other example embodiments or features may further be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein.  In the following detailed description, reference is made to the accompanying figures, which form a part thereof.   
[0024]      The example embodiments described herein are not meant to be limiting.  It will be readily understood that the aspects of the present invention, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein.
1.    Introduction
[0025]      Printing technology has evolved over the last 30-plus years from simple dot-matrix-based output devices producing only black and white images to today’s advanced laser-based printing devices that can produce high-resolution color images.  Additionally, modern printing devices may also function as copiers, scanners, and fax machines.  To do so, they may be able to store numerous electronic documents that are queued for printing or faxing, or that have been scanned.  Thus, many printing devices are specialized forms of computing devices that may include, for example, one or more processors, data storage, and input/output interfaces.
[0026]      Regardless of whether a printing device is used in a residence, a business, or in another type of location, the printing device may be a shared resource that can be communicatively coupled to various other computing devices.  Consequently, in some environments, the storage requirements of a printing device may be quite high, as numerous computing devices may be transmitting electronic documents to the printing device for printing.  Typically, a printing device will print, copy, fax, and/or scan one electronic document at a time, in a first-come-first-served fashion.  Therefore, the printing device may store a potentially large number of electronic documents that are waiting to be serviced.  Since the cost of data storage (e.g., memory such as random access memory (RAM), solid-state memory, hard-drive memory, and/or flash memory) can be expensive, it may be beneficial to compress the stored electronic documents, in order to reduce the data storage requirements of the printing device.  Additionally, since some electronic documents may be transferred to and/or from the printing device and a computing device, compressing these electronic documents may make transfers faster and use less network capacity.  
[0027]      Moreover, since print jobs may be large (e.g., a print job may include one or more electronic documents encompassing hundreds of pages), compressing queued print jobs in the queue saves short-term storage space before each job is printed.  In addition, users may want to save print jobs in long-term storage for printing at a later time.  Thus, compressing print jobs may allow more print jobs to be saved.  Furthermore, the act of storing and retrieving large print jobs from long-term memory can be slow, but it may be expedited by compressing the print jobs to make them smaller in size.
2.    Example Printing Device  
[0028]      Figure 1 depicts an example printing device 100.   Printing device 100 may be configured to print partially-stored and/or fully-stored electronic documents on various types of physical output media.   These output media include, but are not limited to, various sizes and types of paper, overhead transparencies, and so on.  Printing device 100 may be interchangeably referred to as a “printer.”
[0029]      Printing device 100 may serve as local peripheral to a computing device, such as a personal computer, a server device, a print server, etc.  In these cases, printing device 100 may be attached to the computing device by cable, such as a serial port cable, parallel port cable, Universal Serial Bus (USB) cable, Firewire (IEEE 1394) cable, or High-Definition Multimedia Interface (HDMI) cable.  Thus, the computing device may serve as a source of electronic documents for printing device 100. 
[0030]      On the other hand, printing device 100 may include a wireline or wireless network interface, such as an Ethernet or 802.11 (Wifi) interface.  So arranged, printing device 100 may serve as a printing device for any number of computing devices that can communicate with printing device 100 over a network.  In some embodiments, printing device 100 may serve as both a local peripheral and a networked printer at the same time.  In order to use printing device 100, computing devices may install one or more printer drivers.  These printer drivers may include software components that convert the electronic documents to be printed from various local representations stored on the computing devices to one or more representations supported by printing device 100.
[0031]      Regardless, printing device 100 may be considered to be a computing device, and may carry out both printing-related and non-printing related tasks.
[0032]      As noted above, printing device 100 may also include copier, fax, and scanner functions.  In some embodiments, printing device 100 may use a scanner function to facilitate copier and/or fax functions.  For instance, printing device 100 may scan a physical document into an electronic format, and then print the resulting electronic document to provide a copy, and/or transmit the resulting electronic document via a telephone interface to provide a fax function.
[0033]      In order to support its various functions, printing device 100 may include a document feeder / output tray 102, paper storage 104, user interface 106, scanning element 108, and chassis 110.  It should be understood that printing devices may take on a wide variety of forms.  Therefore printing device 100 may include more or fewer components than depicted in Figure 1, and/or components arranged in a different fashion than depicted in Figure 1.
[0034]      Document feeder / output tray 102 may hold physical documents (e.g., a stack of one or more sheets of paper) that are to be scanned, copied or faxed.  Advantageously, document feeder / output tray 102 may allow printing device 100 to automatically feed multiple physical documents for processing by printing device 100 without requiring manual intervention.  Document feeder / output tray 102 may also include one or more separate output trays for holding physical documents that have been processed by printing device 100.  These may include physical documents that have been scanned, copied or faxed by printing device 100, as well as physical documents that have been produced by, e.g., the fax and/or copying functions of printing device 100.
[0035]      Paper storage 104 may include trays and/or feeding elements for various types of physical media.  For instance, paper storage 104 may include separate trays for 8 1/2 x 11 inch paper, A4 paper, letterhead paper, envelopes, and so on.  For any function of printing device 100 that involves outputting physical media (e.g., printing, copying, and/or receiving a fax), paper storage 104 may supply the physical media.
[0036]      User interface 106 may facilitate the interaction of printing device 100 with a human or non-human user, such as to receive input from a user and to provide output to the user.  Thus, user interface 106 may include input components such as a keypad, keyboard, touch-sensitive or presence-sensitive panel, joystick, microphone, still camera and/or video camera.  User interface 106 may also include one or more output components such as a display screen (which, for example, may be combined with a presence-sensitive panel), a cathode ray tube (CRT), a liquid crystal display (LCD), a light emitting diode (LED) based display, a display using digital light processing (DLP(R)) technology, a light bulb, and/or one or more other similar devices, now known or later developed.  User interface 106 may also be configured to be able to generate audible output(s), via a speaker, speaker jack, audio output port, audio output device, earphones, and/or other similar devices, now known or later developed in the future.
[0037]      Scanning element 108 may be a glass panel below which a movable light source operates to scan physical media placed on top of the glass panel.  Alternatively, a digital camera below the glass panel may “scan” the physical media placed on top of the glass panel by taking a picture of the physical media.  Images of scanned physical media may be stored in data storage associated with printing device 100.  
[0038]      Chassis 110 may include a physical housing that contains and or interconnects various components of printing device 100, such as document feeder / output tray 102, paper storage 104, user interface 106, and scanning element 108.  Additionally, chassis 110 may house other components not shown in Figure 1.  For example, chassis 110 may contain one or more toner cartridges, liquid ink jets, belts, rollers, and/or power supplies.  Further, chassis 110 may include communication interfaces, such as a wireline and/or wireless network interfaces, a telephony interface (e.g., a RJ45 jack), a USB interface, a BLUETOOTH(R) interface, a card reader port, etc.
[0039]      Moreover, as printing device 100 may be based on general-purpose and/or specially-designed computing device components, chassis 110 may also house some or all of these components.  To that point, Figure 2 depicts an example embodiment 200 of computing device components (e.g., functional elements of a computing device) that may be included in printing device 100.  
[0040]      Computing device components 200 may include a processor 202, data storage 204, and input/output function 206, all of which may be coupled by a system bus 208 or a similar mechanism.  Processor 202 may include one or more central processing units (CPUs), such as one or more general purpose processors and/or one or more dedicated processors (e.g., application specific integrated circuits (ASICs) or digital signal processors (DSPs), etc.). 
[0041]      Data storage 204, in turn, may comprise volatile and/or non-volatile data storage and can be integrated in whole or in part with processor 202.  Data storage 204 may store program instructions, executable by processor 202, and data that are manipulated by these instructions to carry out the various methods, processes, or functions described herein.  Alternatively, these methods, processes, or functions can be defined by hardware, firmware, and/or any combination of hardware, firmware and software.  Therefore, data storage 204 may include a tangible, non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by one or more processors, cause printing device 100 to carry out any of the methods, processes, or functions disclosed in this specification or the accompanying drawings.  
[0042]      Input/output function 206 may include any of the functions and/or elements described in reference to user interface 106.  Thus, input/output function 206 may serve to configure and/or control the operation of processor 202.  Input/output function 206 may also provide output based on the operations performed by processor 202.
[0043]      It should be understood that these examples of a printing device are provided for illustrative purposes.  Further, in addition to and/or alternatively to the examples above, other combinations and/or sub-combinations of printer and computer technologies may also exist, amongst other possibilities, without departing from the scope of the embodiments herein.  
[0044]      Figure 3 depicts some of the possible data paths through which a representation of an electronic document processed by printing device 100 may pass.  In Figure 3 it is assumed that printing device 100 may include a scanning function 302 and a printing function 304.  Each of these functions may be implemented in hardware, firmware, software, or any combination of hardware, firmware and/or software.    Additionally, each of scanning function 302 and printing function 304 may communicate with computing device 300, and possibly with other computing devices as well.  In some situations, the data paths supported by printing device 100 may be referred to a “pipelines.”
[0045]      A scan-to-print data path 310 may be supported by scanning function 302 and printing function 304.  Scan-to-print data path 310 may be used, e.g., when a user instructs printing device 100 to copy a physical document.  In response to this instruction, scanning function 302 may scan the physical document into an electronic document, and transmit the electronic document via scan-to-print data path 310 to printing function 304.  Use of scan-to-print data path 310 may involve at least temporarily storing some or all of the electronic document in the data storage of printing device 100.  Then, printing function 304 may print the electronic document to physical media (e.g., one or more sheets of paper).  
[0046]      A scan-to-host data path 306 may also be supported by scanning function 302 and computing device 300.  Scan-to-host data path 306 may be used, e.g., when a user instructs printing device 100 to scan a physical document.  The user may also instruct printing device 100 to transmit a representation of the resulting electronic document to computing device 300, or printing device 100 may be pre-configured to automatically transmit the electronic document to computing device 300.  Thus, in response to this instruction, scanning function 302 may scan the physical document into an electronic document, and transmit the resulting electronic document via scan-to-host data path 306 to computing device 300.  Use of scan-to-host data path 306 may involve at least temporarily storing some or all of the electronic document in the data storage of printing device 100, and transmitting a representation of the resulting electronic document to computing device 300.  
[0047]      A host-to-print data path 308 may be supported by computing device 300 and printing function 304.  Host-to-print data path 308 may be used, e.g., when a user instructs computing device 300 to print an electronic document on printing device 100.  In response to this instruction, computing device 300 may transmit a representation of the electronic document to printing function 304.  Printing device 100, via printing function 304, may print the electronic document to physical media.  Some or all of the electronic document may be stored in the data storage of printing device 100 before and/or during the printing of the electronic document.
[0048] Clearly, for at least one of the data paths discussed above, as well as possibly other data paths supported by printing device 100, an electronic document may require storage and/or transmission over a network or a cable.  The efficiency of both the storage and transmission of electronic documents can be improved by compressing these electronic documents for storage and/or transmission.  For example, if electronic documents can, on average be compressed to one-quarter their initial size, then about four times as many electronic documents can be stored in a fixed amount of data storage.  Further, the transmission of these compressed electronic documents over a network or cable can occur about four times as fast as would transmission of the uncompressed electronic documents.  
[0049] The following sections describe various embodiments that provide compression of electronic documents handled by printing device 100.
3.    Example Compression Techniques
[0050] In the past, lossy compression may have been used for some data paths, while lossless compression may have been used for other data paths.  (Lossy compression techniques compress data by discarding some of it, while lossless compression techniques compress data without discarding any of it.)  For example, in some implementations, host-to-print data path 308 may utilize lossless compression in order to preserve sharp edges of text and line art in printed versions of electronic documents.  On the other hand, scan-to-host data path 306 and scan-to-print data path 310 may utilize lossy compression in order to efficiently store and transmit scanned physical documents containing graphical images.  Printing device 100 may be made more efficient and its software and/or hardware implementation may be simplified by using the same or a similar compression technique for at least some (and perhaps all) of its data paths.
a.    Example Image
[0051] Figure 4 depicts at example image 400 that may be included on or within a physical or electronic document handled by printing device 100.  While example image 400 appears in black and white, color images with similar characteristics may also be handled by printing device 100.
[0052] As can be seen in Figure 4, example image 400 contains various types of content.  For instance, example image 400 contains both text and line art with sharp edges.  Further, example image 400 also contains sections containing a continuous tone (e.g., the upper-left-hand corner of example image 400), as well as sections containing photorealistic data (e.g., the lower-right-hand-corner of example image 400).  Example image 400 illustrates a common type of image that is used in business printing, e.g., in pages of a brochure, magazine, flyer, or advertisement.
[0053] A unified compression technique may be able to accurately represent the sharp edges and lines of example image 400, while still using lossy compression in order to reduce the storage requirements of an electronic document containing example image 400.
b.    Example Image Color Models
[0054] Electronic documents can be represented using a number of color models.  Thus, a robust compression technique should be able to operate on some or all of these models.  Further, the compression technique may include preprocessing that is specific to individual color models.
[0055]      For example, the red-green-blue (RGB) color model may be used for display of images on electronic output devices, such as televisions, monitors, and computer screens.  RGB is an additive color model in which red, green, and blue light are added together in various ways to produce a spectrum of colors.  For instance, cyan may be formed by combining green and blue, yellow may be formed by combining red and green, magenta may be formed by combining red and blue, and white may be formed by combining red, green, and blue.  
[0056]      A particular pixel of an RGB image may be expressed as a three-channel tuple (R,G,B), each channel of which can vary from zero to a pre-defined maximum value (e.g., 255).  If all of the channels are at zero, the result may be black.  If all of the channels are at the maximum value, the result may be the brightest representable white.
[0057]      RGB output is typically device-dependent, in that different output devices may display the same RGB image in a different fashion.  Thus, in some cases, these differences may be perceivable by humans.  In some embodiments, physical documents scanned into printing device 100 using scan-to-host data path 306 may be encoded using an RGB color model.
[0058]      The cyan-magenta-yellow (CMY) color model may be used for the printing of color images by printing devices.  CMY is a subtractive color model in which cyan, yellow, and magenta are applied to a white surface in various ways to reproduce a spectrum of colors.  For instance, red can be formed by combining magenta and yellow, blue can be formed by combining cyan and magenta, and green can be formed by combining cyan and yellow.  Thus, the CMY color model might be considered a complement of the RGB color model.
[0059]      A particular pixel of a CMY image may be expressed as a three-channel tuple (C,M,Y), each channel of which can vary from zero to a pre-defined maximum value.  If all of the channels are at zero, the result may be white.  If all of the channels are at the maximum value, the result may be black.  
[0060]      Like, RGB output, CMY output is typically device-dependent, in that the printed output of the same CMY image on different printing devices may appear to be different.  In some cases, these differences may be perceivable by humans.  In some embodiments, electronic documents printed by printing device 100 using host-to-print data path 308 and/or scan-to-print data path 310 may be encoded using a CMY color model.
[0061]      In some embodiments, a four-channel CMYK color model can also be used.  This four-channel model of CMYK may be similar to or the same as the CMY color model, with the exception that a key (black) channel is also used.  In addition to possibly combining cyan, magenta, and yellow to form black, the separate key (black) ink source may be used to form black.  Thus, a particular pixel of a CMYK image may be expressed as a four-channel tuple (C,M,Y,K), each channel of which can vary from zero to a pre-defined maximum value.  
[0062]      Using the CMYK color model, the same colors as the CMY model can be supported, but less ink is typically used because the K colorant can replace mixtures of the C, M, and Y colorants.  However, the CMYK color model may not always be able to be conveniently converted to and from other color models, because the addition of the K colorant adds redundancy, e.g., the same color can be a result of mixing different C, M, Y, and K combinations.  
[0063]      An additional color model is gray, also referred to as grayscale, which may be used for the representation of black and white images.  Unlike the RGB and CMY/CMYK color models, each pixel of the gray color model is expressed using a single channel that encodes the pixel’s intensity.  The values used by the gray channel can vary from zero for black, to a pre-defined maximum value for white (e.g., 255).  In some embodiments, one or more of the data paths supported by printing device 100 may be able to encode images using the gray color model.
[0064]      Another color model is YCbCr.  In some implementations, this color model may be used as an alternative representation of an image.  Particularly, the Y channel may represent the brightness of a pixel, and the Cb and Cr channels may represent the blue-yellow chrominance and red-green chrominance, respectively.  The YCbCr color model has a well-defined relationship with the RGB and CMY colors models and can be converted to and from either of these color models with relative ease.
[0065]      An additional advantage to the YCbCr color model is that compression of images encoded using the YCbCr color model tends to be more efficient than compression of images encoded in the RGB or CMY/CMYK color models.  Particularly, the human eye is not very good at detecting high-frequency (e.g., rapidly varying) chrominance information in an image.  Thus, images encoded using the YCbCr color model can exploit this information by ignoring high-frequency components of the Cb and Cr channels.  Thus, as discussed in more detail below, images encoded in a particular color model may be converted to the YCbCr color model before compression in order to improve compression performance.
c.    Overview of Example Compression Techniques
[0066] A high-level overview of example compression techniques are shown in Figures 5A and 5B.  In Figure 5A, at block 500, an electronic document may be in either the gray or CMYK color model.  At block 502, cell-based compression (discussed in detail below) may be applied to each channel of the electronic document.  Thus, for gray electronic documents, cell-based compression may be applied to just the gray channel.  For CMYK electronic documents, cell-based compression may be applied separately for each of the C, M, Y, and K channels.  The result of block 502 may be a bitstream representing a compressed version of the electronic document.
[0067] At block 504, cell-based decompression (also discussed in detail below) may be applied to each channel of the electronic document.  This may result in the re-creation of the gray or CMYK electronic document at block 506.  However, it should be noted that if the cell-based technique uses lossy compression, the electronic document of block 506 may be different from the electronic document of block 500.  However, the difference between these versions of the electronic document may be slight, and therefore might not be perceived by humans.
[0068] In Figure 5B, at block 508, an electronic document may be in either the RGB or CMY color model.  At block 510, this electronic document may be converted to the YCbCr color model.  Additionally, attribute bits may be stored for the electronic document.  For instance, if a pixel is pure white, pure black, or another grayscale color, one or more attribute bits may encode this information and may be separately stored and compressed (e.g., in a lossless fashion) for the pixel.
[0069] At step 512, cell-based compression may be applied to each channel of the electronic document.  Thus, cell-based compression may be applied separately for each of the Y, Cb, and Cr channels.  The result of block 512 may be a bitstream representing a compressed version of the electronic document.  
[0070] At block 514, cell-based decompression may be applied to each channel of the electronic document.  This may result in the re-creation of the YCbCr version of the electronic document.  However, it should be noted that if the cell-based technique uses lossy compression, the re-created version of the electronic document may be different from the electronic document of block 510.  However, as was the case for the technique of Figure 5A, the difference between these versions of the electronic document may be slight, and therefore might not be perceived by humans.  Additionally, at block 516, the information (if any) encoded in the attribute bits compressed and stored at block 510 may be decompressed and integrated back into the re-created YCbCr version of the electronic document.  
[0071] At block 518, the re-created YCbCr version of the electronic document may be converted back to its original RGB or CMY color model.  This may result in the re-creation of an electronic document that is the same as or similar to the RGB or CMY electronic document at block 520.
[0072] It should be understood that the compression techniques illustrated in Figures 5A and 5B are merely for purposes of example.  Accordingly, various alternative techniques still are encompassed by the embodiments herein.  For instance, conversion to and from the YCbCr color model may be omitted.  Further, the separate compression, storage, and decompression of the attribute bits may also be omitted.
d.    Example Cell-Based Compression 
[0073]      One aspect of cell-based compression is that it may divide each color channel of an electronic document into one or more m x n pixel cells, and then compress each cell in a partially-independent or fully independent fashion.  For example, m might be 8 and n might be 4.  Alternatively, m might be 8 and n might be 8 as well.  Other values of m and n may be used.  Each cell may be evaluated to determine what type of compression methods might be most efficient for compressing the data in that cell.  For example, if a cell consists entirely of pixels that are the same color, the data in the cell may be very efficiently compressed into a representation of the color and perhaps some overhead data.  However, if a cell contains part of a complex, multi-color photorealistic image, the data in the cell may not be able to be compressed at such a high compression ratio.
[0074]      Figure 6 depicts a method of evaluating and compressing a series of cells in a color channel 600 of an electronic document.  Starting with the left-most cell of row 602, each cell is compressed according to the cell-based technique.  In a sense, the compression process moves left-to-right along row 602.  Then, for row 604, the compression process moves right-to-left.  For row 606, the compression process once again moves left-to-right.  For row 608, the compression process once more moves right-to-left.  Nonetheless, the cells of color channel 600 could be compressed in a different order.
[0075]      As noted above, the exact compression method used for a given cell may depend on the data contained within the cell.  Figure 7 is a flow chart that indicates one possible way of determining which compression technique should be applied to a cell.  Figure 7 refers to a number of compression methods, such as D1, G4, P2, P4, and DCT, that will be explained in more detail below.
[0076]      At block 700, pixel information may be collected from a given cell.  This information may include the cell’s minimum color value and maximum color value.   Further, a color value histogram may also be calculated for the cell.  
[0077]      Herein a “color value” may refer to a numerical representation of a pixel’s color.  Example color values may be represented by 8 bits, for a range of 0-255, or by 16 bits, for a range of 0-65535.  However, color values can be represented by a different number of bits and thus may take on different ranges as well.  Further, color values may be used to represent black, white, and various shades of gray in between black and white, even though black and/or white may not be considered to be “colors” under some theories of color.
[0078]      Additionally, an estimation of whether the cell contains a color gradient may be performed.  This estimation may determine whether the color values in the cell can be accurately represented by a four-point gradient with bi-linear interpolation, wherein each point is a respective corner pixel of the cell.  If the actual color values for each non-corner pixel in the cell are within a gradient threshold of the pixel’s bi-linearly interpolated value, then the cell may be a candidate for gradient (G4) compression.
[0079]      At block 702, the range of color values in the cell may be determined and compared to a color range threshold.  If the range is within the color range threshold, D1 compression may be applied to the cell at block 704.  Otherwise, at block 706, if the pixels in the cell can be represented by a four-point gradient with bi-linear interpolation (as determined in block 700), then G4 compression may be applied to the cell at block 708.  The estimation of whether the cell contains a color gradient may be performed in block 706 rather than in block 700.
[0080]      If the cell does not contain a color gradient, then, at block 710, it may be determined whether the cell contains a substantively two-color pattern.  If this is the case, then P2 compression may be applied to the cell at block 712.  Otherwise, at block 714, it may be determined whether the cell contains a substantively four-color pattern.  If this is the case, then P4 compression may be applied to the cell at block 716.  If the cell does not contain a substantively four-color pattern, then, at block 718, discrete cosine transform (DCT) compression may be applied to the cell.
[0081]      Figure 7 illustrates just one possible arrangement of cell-based compression.  Other arrangements may exist, and these arrangements may use different compression methods, and/or may apply different logic to determine which compression method to use for a given cell.  In general, Figure 7 illustrates a process in which more efficient compression methods (in terms of the number of bits used to encode a compressed representation of the cell) are preferred over less efficient compression methods.  The next several sections describe the various compression methods in more detail.
i.    D1 Compression  
[0082]      D1 compression may be used when all of the pixels in a given cell can be represented using a single color value.  This does not mean that all pixels in the cell need to have the same color value.  D1 compression may be used when the difference between the cell’s maximum color value and minimum color value is within a pre-determined color range threshold.  
[0083]      For example, suppose that each pixel in the cell takes on a value from 0 to 255.  If the color range threshold is 3 and all pixels have a color value of either 74, 75, or 76, then D1 compression may be applied to this cell.  One of the three color values present (e.g., the middle color value of 75) may be used to represent the color values of all pixels in the cell.  
[0084]      In this way, the amount of data needed to represent the cell can be dramatically reduced.  Even though this compression is lossy, when the threshold is sufficiently small, the loss is unlikely to be noticed by human observers.  Additionally, compression efficiency and image quality can be traded off with one another by changing the color range threshold.  For instance, a color range threshold of 10 may result in more efficient compression but lower image quality than a color range threshold of 2.
[0085]      In some cases, multiple adjacent cells (e.g., cells in a row or column) may all be well-represented using D1 compression and the same color value.  Thus, the D1 compression method allows for a run length to be encoded along with the color value.  The run length represents how many subsequent cells were also compressed using D1 compression and the color value.  Alternatively, the run length may represent how many total cells were compressed using D1 compression and the color value.
[0086]      A variation of the D1 compression method, which may be referred to as D1D compression, may be used when the color value is a default color.  In the YCbCr color space’s Y channel, the gray color space, and all CMYK color spaces, the default values may be 0 and 255. In the YCbCr color space’s Cb and Cr planes, the default values may be 128 and 255.  D1D compression has a somewhat more efficient encoding than D1 compression.  As there are only a limited number of default values (e.g., 2) in a color space, these default color values can be represented with a small number of bits (e.g., 1 per color value).   Consequently, D1D compression may require fewer bits per cell than D1 compression.
ii.   G4 Compression  
[0087]      As noted above, G4 compression may be used when the color values in the cell can be reasonably well-represented by a four-point color gradient with bi-linear interpolation, wherein each point is a respective corner pixel of the cell.  Figure 8 illustrates the operation of this method.  Blocks 800 and 802 represent the color values of pixels in an 8 x 8 pixel cell.  The individual pixels can be located using the x-axis and the y-axis, and the color of each respective pixel is represented by the z-axis height associated with the pixel.  (For example, a low color value may be represented by a small height on the z-axis, while a high color value may be represented by a large height on the z-axis.)
[0088]      Block 800 is an example of a four-point color gradient in a cell.  Each non-corner pixel has a respective color value such that the color values of the non-corner pixels form a smooth transition between the color values of the corner pixels.  To determine whether a cell is to be encoded using G4 compression, a representation, such as block 802, may be formed based on the color values in the cell’s corner pixels.  For instance, using a form of bi-linear interpolation, each non-corner pixel may be associated with a “proposed” color value.  As shown in block 802, the pixels with the same proposed color value may be grouped in units of 2 or 4.  Units of more or fewer pixels may be used as well.  Then, for each non-corner pixel, the respective proposed color value may be compared to that pixel’s actual color value.  If the difference between these color values is less than a gradient threshold for all non-corner pixels, G4 compression may be used.
iii.  P2 Compression  
[0089]      P2 compression may be used when all of the pixels in a given cell can be represented using two color values.  This does not mean that all pixels in the cell need to have one of these two color values.  Instead, P2 compression may be used when all of the color values in the cell are clustered around (e.g., no more than a given threshold from) two color values.  For instance, if the pixels in a cell can take on color values between 0 and 255, but all color values are either 75, 76, 124, or 125, two of these color values may be chosen, one to represent each cluster.  Thus, a color value of 75 may be used to represent the color in pixels that have a color value of 75 or 76, and a color value of 124 might be used to represent the color in pixels that have a color value of 124 or 125.  
[0090]      One way in which a cell may be evaluated to determine whether it is a candidate for P2 compression is illustrated in Figure 9.  Cell 900 is an example 4 x 4 pixel cell with 4-bit color values of 2 (0010 binary), 3 (0011 binary), and 14 (1110 binary).  Although cell 900 has more than two color values, P2 compression may be used for cell 900 because color value 2 and color value 3 may be able to be represented with a single color value (e.g., one of color value 2 and color value 3).  
[0091]      Accordingly, cell 900 may be evaluated for P2 compression using a three-step process.  In the first step, a histogram mask 902 may be determined for cell 900.  For a cell with c color values, a histogram mask may be c/2 bits in length.  For example, cell 900, which has 16 possible color values, has histogram mask 902 of 8 bits in length.  
[0092]      Further, each bit in histogram mask 902 represents a different pair of two sequential color values.   Thus, the left-most bit in histogram mask 902 represents color values 0 and 1, the second-leftmost bit histogram mask 902 represents color values 2 and 3, and so on.  A given bit in histogram mask 902 is set to 1 if at least one of the two color values represented by the bit is present in cell 900.   Otherwise, the bit is set to 0.  Thus, for histogram mask 902, only the bit representing color values 2 and 3, and the bit representing color values 14 and 15 are set to 1.  
[0093]      Additionally, a qualification mask may be determined for the cell.  In the qualification mask, the bits representing the lowest and highest color values in the cell may be set to 0.  Additionally, one or two more bits to the right of the bit representing the lowest color value, as well as one or two more bits to the left of the bit representing this highest color value, may also be set to 0.  All other bits may be set to 1.  Thus, for qualification mask 904, the second-leftmost bit is set to 0 because it represents color value 2, the lowest color value in cell 900.  Additionally, the two bits to the right of the second-leftmost bit are also set to 0.  Also, the rightmost bit is set to 0 because it represents color value 14, the highest color value in the cell.  The two bits to the left of the rightmost bit are also set to 0.  
[0094]      A logical AND operation may be performed on the histogram mask and the qualification mask.  If the result is 0 (i.e., all bits in the result are 0) then P2 compression may be used for the cell.  Otherwise, P2 compression might not be used for the cell.  Since logical AND 906 in Figure 9 is 0, cell 900 qualifies for P2 compression.  However, if any one pixel of cell 900 were changed to contain the color value 8 or the color value 9, cell 900 would not qualify for P2 compression.
[0095]      A variation of the P2 compression method, which may be referred to as P2D compression, may be used when one or more default color values appear in a cell.  As noted above, in the YCbCr color space’s Y channel, the gray color space, and all CMYK color spaces, the default values may be 0 and 255.  In the YCbCr color space’s Cb and Cr planes, the default values may be 128 and 255.  If only default color values are present in the cell and no non-default color values are present in the cell, P2D compression may be used.  On the other hand, variations may exist wherein P2D compression can be used if color values within a given threshold of each default color value are present in the cell.  P2D compression has a somewhat more efficient encoding than P2 compression.
iv.   P4 Compression  
[0096]      P4 compression may be used when all of the pixels in a given cell can be represented using three or four color values.  For example, if the histogram that may be produced at step 700 indicates that only three or four color values are present in a cell, then P4 compression may be used.  
[0097]      Alternatively or additionally, P4 compression may be used when more than four color values are used in a cell, but all color values present are clustered around (e.g., no more than a given threshold from) four color values that can be used to represent the cell.  For example, if the given threshold is 1 and the cell contains color values of 10, 11, 56, 213, 214, and 255, then P4 compression may be used for the cell, e.g., with color values 10, 56, 213, and 255.
v.    DCT Compression  
[0098]      DCT compression may be used for any color pattern in a cell.  In some embodiments, DCT compression may be used as a last resort if the cell is not compressed using D1, G4, P2, or P4 compression.  For a cell that is compressed using DCT compression, the following steps may be performed: a DCT transform, scaling, quantization, reordering from a two-dimensional coefficient array to one-dimensional data, and Huffman entropy coding.  In some embodiments, the DCT encoding may be a collection of quantized DCT coefficients packaged according to a subset of the Joint Picture Experts Group (JPEG) standard, with Huffman encoding.  Generally, DCT compression is the least efficient of the compression methods presented herein.
e.    Example Encoding of Cell-Based Compression 
[0099]      One possible compressed bitstream encoding of the above compression methods is shown in Table 1.  Table 1 represents how a given m x n pixel cell may be encoded with bits when compressed.  Other encodings not shown herein may also be possible.   
2013258701.tif 000017
Table 1: Example compressed bitstream encodings for each compression method.
[0100]      The compression method column indicates the compression method used to encode the cell, and includes each of the example compression methods discussed above, as well as variations of some.  The opcode column indicates a 2-3 bit representation indicating each respective compression method.  In some embodiments, a cell’s opcode may be placed at the beginning of the cell’s compressed bitstream encoding.  An opcode for D1 / D1D compression may be referred to as a “single-color opcode” hereafter.  Similarly, an opcode for P2 / P2D compression may be referred to as a “two-color opcode.”  And an opcode for P4 compression may be referred to as a “four-color opcode”, an opcode for G4 compression may be referred to as a “gradient opcode”, and an opcode for DCT compression may be referred to as a “DCT opcode.”
[0101]      The options column may contain one or more options that may be specific to the compression method being encoded.  For instance, the D1D compression method encodes an entire cell as one of two possible default values.  The V bit of the options column may encode which default value is being encoded (e.g., V=0 for the lower default value and V=1 for the higher default value).  
[0102]      As another example, the D1 compression method encodes an entire cell as one of, e.g., 256 possible values.  The V’ bit in the options for D1 compression indicates that the options fields are followed by 1 byte that encodes the value for the cell.  For both D1D and D1 compression, the R bit indicates whether the run length byte (see the discussion below of the run length column) is present.
[0103]      As a further example, the P2 compression method may include the L bit, which indicates the presence of two color values following the L bit.  These color values may be the color values that the P2 compression method uses to represent all color values in a compressed cell.  Similarly, the P4 compression method may include the L’ bit, which indicates the presence of four color values following the L’ bit.  These color values may be the color values that the P4 compression method uses to represent all color values in a compressed cell.  
[0104]      The Color Values column may contain one or more color values used to represent the compressed cell.  As noted above, the D1, P2, ad P4 compression methods specify 1, 2, and 4 color values, respectively.  Each color value may be represented by an appropriate number of bits (e.g., 8 bits for a color value range of 0-255).
[0105]      The Raster column may represent a one-bit-per-pixel or 2-bit-per-pixel representation (e.g., a bitmap) of the color values of each respective pixel in the cell.  For instance, P2D and P2 compression may use 1 bit per pixel to represent which of the two color values is used for each respective pixel in the cell.  Similarly, P4 compression may use 2 bits per pixel to represent which of the four color values is used for each respective pixel in the cell.  The representations referred to in the Raster column may be compressed further using a form of run length encoding.
[0106]      The Length column may contain an optional one-byte encoding of a run length.  In some embodiments, the length column may only be used for the D1D and D1 compression methods, in which a single color value can be used to represent an entire cell.  In some cases, two or more sequential cells in an image may all be able to be encoded using the same single color value.  Thus, the byte in the length column may indicate the number of sequential cells using the same color value for D1D or D1 compression.
[0107]      Although not explicitly shown in Table 1, DCT compression may result in a cell being represented by a bitstream of the DCT opcode followed by an encoded result of the DCT compression method.
f.    Example Cell-Based Decompression 
[0108]      Once a number of cells are compressed using, for example, the compression methods and encodings discussed above, they may be efficiently stored and/or transmitted over a cable or network.  Nonetheless, at some point, the cell may be decompressed into an approximation of the original image.  Since the cell-based compression techniques described herein can be lossy, the decompressed image may differ, at least to some extent, from the original image.  However, in many scenarios, this difference will either be unlikely to be perceived by a human, or considered to be an acceptable version of the original image.  
[0109]      The cells encoded with the compression encoding of Table 1 can be decoded and decompressed as follows.  For a given cell encoding, the opcode is read.  Based on the value of the opcode, any applicable options, color values, rasters, and/or lengths can be determined from the bits following the opcode.  From these parameters, a decompressed version of the cell can be reconstructed.  Then, the next opcode is read and so on until the image is reconstructed.
[0110]      For example, if the opcode is 000, indicating D1D encoding, the V bit may be read to determine the color value, and the R bit may be read to determine whether a run length is present.  Then, a number of cells commensurate with the run length are created with all pixels in each cell exhibiting the default color value indicated by the V bit. 
[0111]      If the opcode is 001, indicating D1 compression, the V’ bit and the color value field may be read to determine the color value.  The R bit may also be read to determine whether a run length is present.  Then, a number of cells commensurate with the run length are created with all pixels in each cell exhibiting the color value indicated by the color value field. 
[0112]      If the opcode is 010, indicating P2D compression, the raster field may be read.  A cell may be created with each pixel taking on a color value of either the low default color value or the high default color value, in accordance with the bitmap of the raster field.
[0113]      If the opcode is 011, indicating P2 compression, the L bit, the color values field, and the raster field may be read.  Then, a cell may be created with each pixel taking on one of the two color values in accordance with the bitmap of the raster field.
[0114]      If the opcode is 100, indicating P4 compression, the L’ bit, the color values field, and the raster field may be read.  Then, a cell may be created with each pixel taking on one of the four color values in accordance with the bitmap of the raster field.
[0115]      If the opcode is 101, indicating G4 encoding, the color values field may be read to determine the color values of the four corner pixels.  Then, a cell may be created with each corner pixel taking on one of the color values indicated by the color values field, and bi-linear interpolation may be used to determine the color values of the non-corner pixels.  
[0116]      If the opcode is 11, indicating DCT compression, the result of the DCT compression method may be read and a cell may be created in accordance with this DCT encoding.
g.    Compression Efficiency
[0117]      The cell-based compression techniques described herein can be very efficient.  In practice, an average compression ratio of 20:1 has been observed.  The following example illustrates this efficiency.  
[0118]      Suppose that a high speed printing system prints 180 pages per minute (3 pages per second) using a host-to-print data path, that the resolution of these pages is 600 dots-per-inch (dpi) for each 10 inch by 8 inch page, and that three color channels are used, each encoding a 1-byte color value.  Thus, the total amount of uncompressed data transferred in 1 second is 600 (dots) x 600 (dots) x 10 (inches) x 8 (inches) x 3 (color channels) x 3 (pages), which equals about 247 megabytes.   Using the cell-based compression techniques described above, this data amount may, on average, be reduced to about 12.4 megabytes.
4.    Example Operation 
[0119]      Figure 10 is a flow chart of an example embodiment. The steps illustrated by this flow chart may be carried out by one or more printing devices, such as printing device 100, and/or computing devices, such as computing device 300.  Further, aspects of each individual step may be distributed between multiple computing devices. 
[0120]      At step 1000, an m x n pixel cell may be obtained from an input image.  The input image may contain more than m x n pixels, and each of the m x n pixels in the m x n pixel cell may have a respective color value.  In some embodiments, the m x n pixel cell may be only associated with color values from a single color channel of the input image.
[0121]      At step 1002 a characterization of the m x n pixel cell may be determined.  Determining the characterization may involve determining a lowest color value and a highest color value of the pixels in the m x n pixel cell.  
[0122]      Determining the characterization may further involve determining a histogram of color values for the m x n pixel cell, and obtaining, from the histogram, a second-lowest color value and a second-highest color value of the pixels in the m x n pixel cell.  The second-lowest color value may be adjacent to (or within a threshold of) the lowest color value and the second-highest color value may be adjacent to (or within a threshold of) the highest color value.  Then, it may be determined, from the histogram, that no color value other than the lowest color value, the second-lowest color value, the second-highest color value, and the highest color value are in the m x n pixel cell, and selecting multiple output color values may include selecting one of the lowest color value and the second-lowest color value, and one of the second-highest color value and the highest color value.
[0123]      At step 1004 a difference between the highest color value and the lowest color value may be calculated.  At step 1006, it may be determined whether the difference is less than or equal to a threshold difference.  
[0124]      If the difference is less than or equal to the threshold difference, then, at step 1008, an output color value may be selected from color values between the highest color value and the lowest color value, inclusive.  Also at step 1008, a first representation of the output color value may be written to an output medium.  The first representation may include a single-color opcode and an indication of the output color value.  If the difference is greater than the threshold difference, then, at step 1010, multiple output color values may be selected, and a second representation of the multiple output color values may be written to the output medium.  
[0125]      Based on the representation written to the output medium (e.g., the first representation or the second representation), an approximation of the m x n pixel cell may be recreated on an output device.  The output device may or may not be closely associated with the output medium.  For instance, the output medium may be data storage within a printing device and the output device may be the printing device.  Alternatively, the output medium may be data storage within a computing device and the output device may be the printing device.
[0126]      The multiple output color values may consist of two output color values, and the second representation may include a two-color opcode, an indication of each of the two output color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two output colors.  Alternatively, the multiple output color values consist of up to four output color values, and the second representation may include a four-color opcode, an indication of each of the up to four output color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the up to four output colors.  
[0127]      In some embodiments, determining the characterization may further involve determining a histogram of color values for the m x n pixel cell, and obtaining, from the histogram, a first intermediate color value and a second intermediate color value of the pixels in the m x n pixel cell.   Each of the first intermediate color value and the second intermediate color value may be between the lowest color value and the highest color value.  Then it may be determined, from the histogram, that no color value other than (i) the lowest color value, (ii) the first intermediate color value, (iii) the second intermediate color value, (iv) the highest color value, and (v) one or more color values adjacent to one of the lowest color value, the first intermediate color value, the second intermediate color value, and the highest color value, are in the m x n pixel cell.  In this case, selecting multiple output color values may include selecting colors at or proximate to each of the lowest color value, the first intermediate color value, the second intermediate color value, and the highest color value as the four output colors.  Alternatively, more than two intermediate colors may be used.
[0128]      Some embodiments may further include performing a DCT operation on the m x n pixel cell.  Accordingly, the multiple output color values may be based on a result of the DCT operation, and the second representation may include a DCT opcode and the result of the DCT operation.
[0129]      Alternatively or additionally, the multiple output color values may consist of four output color values.  Each of the four output color values may be a color value of a respective one of the corners of the m x n pixel cell, and the second representation may include a gradient opcode, and an indication of each of the four output color values.  Moreover, in some of these scenarios, determining the characterization further involve deriving a template set of m x n pixels based on a bi-linear interpolation of the four output color values, comparing the color values (for example, pixel values) of the m x n pixel cell to those of the template set, and determining that the color valuesof the m x n pixel cell at least approximately match those of the template set.
[0130]      Figures 11A and 11B are a flow chart of another example embodiment, further illustrating cell-based compression.  At step 1100, an m x n pixel cell may be obtained from an input image.  The input image may contain more than m x n pixels, and each of the m x n pixels in the m x n pixel cell may have a respective color value;
[0131]      At step 1102, a characterization of the m x n pixel cell may be determined.  Determining the characterization may involve determining color values of the pixels in the m x n pixel cell.  
[0132]      At step 1104, a difference between a highest color value and a lowest color value of the color values may be calculated.  At step 1106, the difference may be compared to a threshold difference.  
[0133]      If the difference is less than or equal to a threshold difference, then, at step 1108, an output color value between the highest color value and the lowest color value, inclusive, may be selected.  Additionally, a first representation of the output color value may be written to an output medium.  The first representation may include a single-color opcode and an indication of the output color value.
[0134]      If the difference is greater than the threshold difference, then, at step 1110, it may be determined whether the color values of the m x n pixel cell substantially consist of two color values.  The color values of the m x n pixel cell may be considered to substantially consist of two color values if (i) there are only two color values in the cell, (ii) there are three color values in the cell and at least two of those three color values are sequential in number, (iii) there are four color values in the cell and at least two pairs of these color values are each sequential in number, (iv) all of the color values in the cell are clustered around one or two color values, or (v) based on some other observation of the color values in the cell.  
[0135]      If the color values of the m x n pixel cell substantially consist of two color values, then, at step 1112, a second representation of the two color values may be written to the output medium.  The second representation may include a two-color opcode, an indication of each of the two color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two color values.  
[0136]      If the color values of the m x n pixel cell substantially consist of more than two color values, then, at step 1114, it may be determined whether the color values of the m x n pixel cell substantially consist of three or four color values.  The color values of the m x n pixel cell may be considered to substantially consist of three or four color values if (i) there are only three or four color values in the cell, (ii) there are five to eight color values in the cell and these color values are such that at least two are sequential in number, (iii) all of the color values in the cell are clustered around three or four color values, or (iv) based on some other observation of the color values in the cell.
[0137]      If the color values of the m x n pixel cell substantially consist of three or four color values, then, at step 1116, a third representation of the three or four color values may be written to the output medium.  The third representation may include a four-color opcode, an indication of each of the three or four color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the three or four color values. 
[0138]      If the color values of the m x n pixel cell substantially consist of more than four color values, then, at step 1118, a discrete cosine transformation (DCT) operation may be performed on the m x n pixel cell, and a fourth representation may be written to the output medium.  The fourth representation may include a DCT opcode and a result of the DCT operation.
5.    Conclusion 
[0139]      The present invention is not to be limited in terms of the particular embodiments described in this application, which are intended as illustrations of various aspects.  Many modifications and variations can be made without departing from its spirit and scope, as will be apparent to those skilled in the art.  Functionally equivalent methods and apparatuses within the scope of the invention, in addition to those enumerated herein, will be apparent from the foregoing descriptions.  Such modifications and variations are intended to fall within the scope of the appended claims.  
[0140]      With respect to any or all of the ladder diagrams, scenarios, and flow charts in the figures and as discussed herein, each block and/or communication may represent a processing of information and/or a transmission of information in accordance with example embodiments.  Alternative embodiments may be included within the scope of such example embodiments.  Further, more or fewer blocks and/or functions may be used with any of the ladder diagrams, scenarios, and flow charts discussed herein, and these ladder diagrams, scenarios, and flow charts may be combined with one another, in part or in whole.    
[0141]      A step or block that represents a processing of information may correspond to circuitry that can be configured to perform the specific logical functions of a herein-described method or technique.  Alternatively or additionally, a step or block that represents a processing of information may correspond to a module, a segment, or a portion of program code (including related data).  The program code may include one or more instructions executable by a processor for implementing specific logical functions or actions in the method or technique.  The program code and/or related data may be stored on any type of computer-readable medium, such as a storage device, including a disk drive, a hard drive, or other storage media.
[0142]      The computer-readable medium may also include non-transitory computer-readable media such as computer-readable media that stores data for short periods of time like register memory, processor cache, and/or random access memory (RAM).  The computer-readable media may also include non-transitory computer-readable media that stores program code and/or data for longer periods of time, such as secondary or persistent long term storage, like read only memory (ROM), optical or magnetic disks, and/or compact-disc read only memory (CD-ROM), for example.  The computer-readable media may also be any other volatile or non-volatile storage systems.  A computer-readable medium may be considered a computer-readable storage medium, for example, and/or a tangible storage device.
[0143]      A method comprises: a computing device obtaining an m x n pixel cell from an input image, wherein the input image contains more than m x n pixels, and each of the m x n pixels in the m x n pixel cell has a respective color value; the computing device determining a characterization of the m x n pixel cell, wherein determining the characterization comprises determining a lowest color value and a highest color value of the pixels in the m x n pixel cell; the computing device calculating a difference between the highest color value and the lowest color value; if the difference is less than or equal to a threshold difference, the computing device selecting an output color value inclusively between the highest color value and the lowest color value, and writing a first representation of the output color value to an output medium, wherein the first representation includes a single-color opcode and an indication of the output color value; and if the difference is greater than the threshold difference, the computing device selecting multiple output color values, and writing a second representation of the multiple output color values to the output medium.
[0144]       In the above method, the m x n pixel cell is only associated with color values from a single color channel of the input image.
[0145]      In the above method, the multiple output color values consist of two output color values, and wherein the second representation includes a two-color opcode, an indication of each of the two output color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two output color values.
[0146]      In the above method, determining the characterization further comprises: determining a histogram of color values for the m x n pixel cell; obtaining, from the histogram, a second-lowest color value and a second-highest color value of the pixels in the m x n pixel cell, wherein the second-lowest color value is within a threshold of the lowest color value and the second-highest color value is within the threshold of the highest color value; and determining, from the histogram, that no color value other than the lowest color value, the second-lowest color value, the second-highest color value, and the highest color value are in the m x n pixel cell, and, selecting multiple output color values comprises selecting one of the lowest color value and the second-lowest color value, and one of the second-highest color value and the highest color value.
[0147]      In the above method, the multiple output color values consist of up to four output color values, and wherein the second representation includes a four-color opcode, an indication of each of the up to four output color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the up to four output color values.
[0148]      In the above method, determining the characterization further comprises: determining a histogram of color values for the m x n pixel cell; obtaining, from the histogram, a first intermediate color value and a second intermediate color value of the pixels in the m x n pixel cell, wherein each of the first intermediate color value and the second intermediate color value are between the lowest color value and the highest color value; and determining, from the histogram, that no color value other than the lowest color value, the first intermediate color value, the second intermediate color value, the highest color value, and one or more color values adjacent to one of the lowest color value, the first intermediate color value, the second intermediate color value, and the highest color value are in the m x n pixel cell, wherein selecting multiple output color values comprises selecting colors at or proximate to each of the lowest color value, the first intermediate color value, the second intermediate color value, and the highest color value as the four output colors. 
[0149]      In the above method, the method further comprises: performing a discrete cosine transformation (DCT) operation on the m x n pixel cell, wherein the multiple output color values are based on a result of the DCT operation, and wherein the second representation includes a DCT opcode and the result of the DCT operation.
[0150]      In the above method, the multiple output color values consist of four output color values, wherein each of the four output color values is a color value of a respective one of the corners of the m x n pixel cell, and wherein the second representation includes a gradient opcode, and an indication of each of the four output color values.
[0151]      In the above method, determining the characterization further comprises: deriving a template set of m x n pixels based on a bi-linear interpolation of the four output color values; comparing the color values of the m x n pixel cell to those of the template set; and determining that the pixel values of the m x n pixel cell at least approximately match those of the template set.
[0152]      In the above method, the method further comprises: based on the representation written to the output medium, recreating, on an output device, an approximation of the m x n pixel cell.
[0153]      An article of manufacture including a non-transitory computer-readable medium, has stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations of the above method.
[0154]      A computing device comprises: a processor; data storage; and program instructions, stored in the data storage, that, upon execution by a computing device, cause the computing device to perform operations of the above method.
[0155]      A program, upon execution by a computing device, causes the computing device to perform operations of the above method.
[0156]      A method comprises: a computing device obtaining an m x n pixel cell from an input image, wherein the input image contains more than m x n pixels, and each of the m x n pixels in the m x n pixel cell has a respective color value; the computing device determining a characterization of the m x n pixel cell, wherein determining the characterization comprises determining color values of the pixels in the m x n pixel cell; the computing device calculating a difference between a highest color value and a lowest color value of the color values; if the difference is less than or equal to a threshold difference, the computing device selecting an output color value inclusively between the highest color value and the lowest color value, and writing a first representation of the output color value to an output medium, wherein the first representation includes a single-color opcode and an indication of the output color value; else if the color values of the m x n pixel cell substantially consist of two color values, the computing device writing a second representation of the two color values to the output medium, wherein the second representation includes a two-color opcode, an indication of each of the two color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two color values; else if the color values of the m x n pixel cell substantially consist of three or four color values, the computing device writing a third representation of the three or four color values to the output medium, wherein the third representation includes a four-color opcode, an indication of each of the three or four color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the three or four color values; and else if the color values of the m x n pixel cell substantially consist of more than four color values, the computing device performing a discrete cosine transformation (DCT) operation on the m x n pixel cell, and writing a fourth representation to the output medium, wherein the fourth representation includes a DCT opcode and a result of the DCT operation.
[0157]      While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art.  The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.
INDUSTRIAL APPLICABILITY
[0158]      The present invention may be applicable to Cell-Based Compression of Digital Images. 
REFFERENCE SIGNS LIST
[0159]      
100   Printing device
102   Tray
104   Paper storage
106   User interface
108   Scanning element
110   Chassis
200, 300    Computing device
202   Processor
204   Data storage
206   Input/output function
208   System bus
302   Scanning function
304   Printing function
306   Scan-to-host data path
308   Host-to print data path
310   Scan-to-print data path
CLAIMS
We claim:
1.    A method comprising:
a computing device obtaining an m x n pixel cell from an input image, wherein the input image contains more than m x n pixels, and each of the m x n pixels in the m x n pixel cell has a respective color value;
the computing device determining a characterization of the m x n pixel cell, wherein determining the characterization comprises determining a lowest color value and a highest color value of the pixels in the m x n pixel cell;
the computing device calculating a difference between the highest color value and the lowest color value;
if the difference is less than or equal to a threshold difference, the computing device selecting an output color value inclusively between the highest color value and the lowest color value, and writing a first representation of the output color value to an output medium, wherein the first representation includes a single-color opcode and an indication of the output color value; and
if the difference is greater than the threshold difference, the computing device selecting multiple output color values, and writing a second representation of the multiple output color values to the output medium.
2.    The method of claim 1, wherein the m x n pixel cell is only associated with color values from a single color channel of the input image.
3.    The method of claim 1 or 2, wherein the multiple output color values consist of two output color values, and wherein the second representation includes a two-color opcode, an indication of each of the two output color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two output color values.
4.    The method of claim 3, wherein determining the characterization further comprises:
determining a histogram of color values for the m x n pixel cell;
obtaining, from the histogram, a second-lowest color value and a second-highest color value of the pixels in the m x n pixel cell, wherein the second-lowest color value is within a threshold of the lowest color value and the second-highest color value is within the threshold of the highest color value; and
determining, from the histogram, that no color value other than the lowest color value, the second-lowest color value, the second-highest color value, and the highest color value are in the m x n pixel cell, and
wherein selecting multiple output color values comprises selecting one of the lowest color value and the second-lowest color value, and one of the second-highest color value and the highest color value.
5.    The method of claim 1 or 2, wherein the multiple output color values consist of up to four output color values, and wherein the second representation includes a four-color opcode, an indication of each of the up to four output color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the up to four output color values.
6.    The method of claim 5, wherein determining the characterization further comprises:
determining a histogram of color values for the m x n pixel cell;
obtaining, from the histogram, a first intermediate color value and a second intermediate color value of the pixels in the m x n pixel cell, wherein each of the first intermediate color value and the second intermediate color value are between the lowest color value and the highest color value; and
determining, from the histogram, that no color value other than the lowest color value, the first intermediate color value, the second intermediate color value, the highest color value, and one or more color values adjacent to one of the lowest color value, the first intermediate color value, the second intermediate color value, and the highest color value are in the m x n pixel cell, wherein selecting multiple output color values comprises selecting colors at or proximate to each of the lowest color value, the first intermediate color value, the second intermediate color value, and the highest color value as the four output colors.
7.    The method of claim 1 or 2, further comprising:
performing a discrete cosine transformation (DCT) operation on the m x n pixel cell, wherein the multiple output color values are based on a result of the DCT operation, and wherein the second representation includes a DCT opcode and the result of the DCT operation.
8.    The method of claim 1 or 2, wherein the multiple output color values consist of four output color values, wherein each of the four output color values is a color value of a respective one of the corners of the m x n pixel cell, and wherein the second representation includes a gradient opcode, and an indication of each of the four output color values.
9.    The method of claim 8, wherein determining the characterization further comprises:
deriving a template set of m x n pixels based on a bi-linear interpolation of the four output color values; 
comparing the color valuesof the m x n pixel cell to those of the template set; and
determining that the pixel values of the m x n pixel cell at least approximately match those of the template set.
10.   The method of any one of claim 1 to claim 9, further comprising:
based on the representation written to the output medium, recreating, on an output device, an approximation of the m x n pixel cell.
11.   An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations of the method of any one of Claim 1 to Claim 10.
12.   A computing device comprising:
a processor;
data storage; and 
program instructions, stored in the data storage, that, upon execution by a computing device, cause the computing device to perform operations of the method of any one of Claim 1 to Claim 10.
13.   A program that, upon execution by a computing device, causes the computing device to perform operations of the method of any one of Claim 1 to Claim 10.
14.   A method comprising:
a computing device obtaining an m x n pixel cell from an input image, wherein the input image contains more than m x n pixels, and each of the m x n pixels in the m x n pixel cell has a respective color value;
the computing device determining a characterization of the m x n pixel cell, wherein determining the characterization comprises determining color values of the pixels in the m x n pixel cell;
the computing device calculating a difference between a highest color value and a lowest color value of the color values;
if the difference is less than or equal to a threshold difference, the computing device selecting an output color value inclusively between the highest color value and the lowest color value, and writing a first representation of the output color value to an output medium, wherein the first representation includes a single-color opcode and an indication of the output color value; 
else if the color values of the m x n pixel cell substantially consist of two color values, the computing device writing a second representation of the two color values to the output medium, wherein the second representation includes a two-color opcode, an indication of each of the two color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the two color values;
else if the color values of the m x n pixel cell substantially consist of three or four color values, the computing device writing a third representation of the three or four color values to the output medium, wherein the third representation includes a four-color opcode, an indication of each of the three or four color values, and a per-pixel bitmap of the m x n pixel cell that associates each pixel in the m x n pixel cell with one of the three or four color values; and
else if the color values of the m x n pixel cell substantially consist of more than four color values, the computing device performing a discrete cosine transformation (DCT) operation on the m x n pixel cell, and writing a fourth representation to the output medium, wherein the fourth representation includes a DCT opcode and a result of the DCT operation.
Abstract
PROBLEM TO BE SOLVED
The present invention may provide method for cell-based compression of digital images.
SOLUTION
An m x n pixel cell may be obtained from an input image, each of the pixels having a respective color value (1000).  A characterization of the cell may be determined, including determining a lowest color value and a highest color value of the pixels cell (1002).  A difference between the highest color value and the lowest color value may be calculated(1004).  If the difference is less than or equal to a threshold difference, an output color value inclusively between the highest color value and the lowest color value may be selected, and a first representation of the output color value may be written to an output medium (1008).  If the difference is greater than the threshold difference, multiple output color values may be selected, and a second representation of the multiple output color values may be written to the output medium (1010).
REPRESENTATIVE DRAWING: Fig. 10
2013258701.tif 000018
2013258701.tif 000019
2013258701.tif 000020
2013258701.tif 000021
2013258701.tif 000022
2013258701.tif 000023
2013258701.tif 000024
2013258701.tif 000025
2013258701.tif 000026
2013258701.tif 000027
2013258701.tif 000028
2013258701.tif 000029