(57)【要約】      （修正有）【課題】エッジ検出およびインターリーブ符号化を用いるセルベースの圧縮ための技術を提供する。【解決手段】ａｘｂ属性マクロセル、および入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得する。ａｘｂ画素マクロセルは、それぞれ４つの非オーバーラップｍｘｎ画素セルを含む。また、４つの非オーバーラップｍｘｎ属性セルを表す４つの属性平面出力値、前記輝度平面のａｘｂ画素マクロセルを表すための１乃至４つの輝度平面出力値、第１の色平面のａｘｂ画素マクロセルを表すための第１の色平面出力値および第２の色平面のａｘｂ画素マクロセルを表すための第２の色平面出力値を判定する。さらに、前記出力値のインターリーブ表現をコンピュータ読み取り可能な出力媒体に書き込む。【選択図】図１５
2016144210.tif 000002
【特許請求の範囲】
【請求項１】
印刷デバイスであって、
少なくとも１つの処理部と
記憶部と、
前記記憶部に格納され、前記少なくとも１つの処理部によって実行時、前記印刷デバイスに操作を実行させるプログラム指示と、
を備え、前記操作は、
（１）ａｘｂ属性マクロセル、および（２）入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得する工程であって、前記ａｘｂ画素マクロセルの各々は、４つの非オーバーラップｍｘｎ画素セルを含み、前記ａｘｂ画素マクロセルの前記ａｘｂ画素は、それぞれの画素値を有し、前記ａｘｂ属性マクロセルの要素は、それぞれの前記ａｘｂ画素マクロセルのそれぞれの画素と一対一で関連付けられている工程と、
４つの非オーバーラップｍｘｎ属性セルをそれぞれ表す４つの属性平面出力値を判定する工程と、
前記ａｘｂ属性マクロセルが、少なくとも前記ａｘｂ画素マクロセルのｅ画素（ｅは少なくとも１である。）が前記入力画像のエッジを表すことを示すかどうかに基づき、前記輝度平面の前記ａｘｂ画素マクロセルを表す１乃至４つの輝度平面出力値を判定する工程と、
前記第１の色平面の前記ａｘｂ画素マクロセルを表すための第１の色平面出力値および前記第２の色平面の前記ａｘｂ画素マクロセルを表すための第２の色平面出力値を判定する工程と、
前記４つの属性平面出力値、前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のインターリーブ表現を、コンピュータ読み取り可能な出力媒体に書き込む工程と、
を含む印刷デバイス。
【請求項２】
請求項１に記載の印刷デバイスであって、
前記１乃至４つの輝度平面出力値を判定する工程は、
前記ａｘｂ属性マクロセルが、少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表すことを示すことを判定する工程と、
前記輝度平面の前記ａｘｂ画素マクロセルの前記非オーバーラップｍｘｎ画素セルのそれぞれを表す４つの輝度平面出力値を判定する工程と、
を含む印刷デバイス。
【請求項３】
請求項２に記載の印刷デバイスであって、
前記第１の色平面出力値および前記第２の色平面出力値は、それぞれ前記入力画像のエッジを表す画素を、前記入力画像のエッジを表さない画素よりも重み付けする前記第１の色平面および前記第２の色平面の前記ａｘｂ画素マクロセルのダウンサンプリングバージョンである印刷デバイス。
【請求項４】
請求項１乃至３のいずれか１項に記載の印刷デバイスであって、
前記１乃至４つの輝度平面出力値を判定する工程は、
（１）前記ａｘｂ属性マクロセルが前記ａｘｂ画素マクロセルのｅ画素より少ない画素が前記入力画像のエッジを表すことを示すこと、および（２）前記ａｘｂ画素マクロセルの少なくとも１つの前記４つの非オーバーラップｍｘｎ画素セルの画素値の範囲が閾値よりも大きいことを判定する工程と、
前記輝度平面の前記ａｘｂ画素マクロセルの前記非オーバーラップｍｘｎ画素セルのそれぞれを表す４つの輝度平面出力値を判定する工程と、
を含む印刷デバイス。
【請求項５】
請求項４に記載の印刷デバイスであって、
前記第１の色平面出力値および前記第２の色平面出力値は、それぞれ前記第１の色平面および前記第２の色平面の前記ａｘｂ画素マクロセルのダウンサンプリングバージョンであり、前記ダウンサンプリングは、画素が前記入力画像のエッジを表すかどうかを考慮しない印刷デバイス。
【請求項６】
請求項１乃至５のいずれか１項に記載の印刷デバイスであって、
前記１乃至４つの輝度平面出力値を判定する工程は、
（１）前記ａｘｂ属性マクロセルが、前記ａｘｂ画素マクロセルのｅ画素より少ない画素が前記入力画像のエッジを表すことを示すこと、および（２）前記ａｘｂ画素マクロセルのそれぞれに対する４つの非オーバーラップｍｘｎ画素セルのそれぞれにおける画素値の範囲が閾値以下であることを判定する工程と、
前記輝度平面の前記ａｘｂ画素マクロセルを表す１つの輝度平面出力値を判定する工程と、
を含む印刷デバイス。
【請求項７】
請求項１乃至６のいずれか１項に記載の印刷デバイスであって、
前記第１の色平面出力値は、ａｘｂバイト未満で表され、また前記第２の色平面出力値は、ａｘｂバイト未満で表される印刷デバイス。
【請求項８】
請求項１乃至７のいずれか１項に記載の印刷デバイスであって、
４つの輝度平面出力値が判定され、前記インターリーブ表現は、複合モードインジケータで始まり、オペコードは、前記インターリーブ表現の前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のそれぞれに対して除外される印刷デバイス。
【請求項９】
請求項１乃至８のいずれか１項に記載の印刷デバイスであって、
１つの輝度平面出力値が判定され、前記インターリーブ表現は、プレーナモードインジケータで始まり、オペコードは、前記インターリーブ表現の前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のそれぞれに対して含まれる印刷デバイス。
【請求項１０】
コンピュータプログラムであって、
（１）ａｘｂ属性マクロセル、および（２）入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得する工程であって、前記ａｘｂ画素マクロセルの各々は、４つの非オーバーラップｍｘｎ画素セルを含み、前記ａｘｂ画素マクロセルの前記ａｘｂ画素は、それぞれの画素値を有し、前記ａｘｂ属性マクロセルの要素は、それぞれの前記ａｘｂ画素マクロセルのそれぞれの画素と一対一で関連付けられている工程と、
４つの非オーバーラップｍｘｎ属性セルをそれぞれ表す４つの属性平面出力値を判定する工程と、
前記ａｘｂ属性マクロセルが、少なくとも前記ａｘｂ画素マクロセルのｅ画素（ｅは少なくとも１である。）が前記入力画像のエッジを表すことを示すかどうかに基づき、前記輝度平面の前記ａｘｂ画素マクロセルを表す１乃至４つの輝度平面出力値を判定する工程と、
前記第１の色平面の前記ａｘｂ画素マクロセルを表すための第１の色平面出力値および前記第２の色平面の前記ａｘｂ画素マクロセルを表すための第２の色平面出力値を判定する工程と、
前記４つの属性平面出力値、前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のインターリーブ表現を、コンピュータ読み取り可能な出力媒体に書き込む工程と、
を印刷デバイスに実行させるコンピュータプログラム。
【請求項１１】
方法であって、
印刷デバイスによって、（１）ａｘｂ属性マクロセル、および（２）入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得する工程であって、前記ａｘｂ画素マクロセルの各々は、４つの非オーバーラップｍｘｎ画素セルを含み、前記ａｘｂ画素マクロセルの前記ａｘｂ画素は、それぞれの画素値を有し、および前記ａｘｂ属性マクロセルの要素は、前記ａｘｂ画素マクロセルのそれぞれにおけるそれぞれの画素と一対一で関連付けられている工程と、
前記印刷デバイスによって、４つの非オーバーラップｍｘｎ属性セルをそれぞれ表す４つの属性平面出力値を判定する工程と、
前記ａｘｂ属性マクロセルが、少なくとも前記ａｘｂ画素マクロセルのｅ画素（ｅは少なくとも１である。）が前記入力画像のエッジを表すことを示すかどうかに少なくとも部分的に基づき、前記印刷デバイスによって、前記輝度平面の前記ａｘｂ画素マクロセルを表す１乃至４つの輝度平面出力値を判定する工程と、
前記印刷デバイスによって、前記第１の色平面の前記ａｘｂ画素マクロセルを表すための第１の色平面出力値および前記第２の色平面の前記ａｘｂ画素マクロセルを表すための第２の色平面出力値を判定する工程と、
前記印刷デバイスによって、前記４つの属性平面出力値、前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のインターリーブ表現をコンピュータ読み取り可能な出力媒体に書き込む工程と、
を備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル画像の圧縮技術に関する。
【背景技術】
【０００２】
近年、さまざまな種類の印刷デバイスが業務用および民生用の両方で普及してきている。従来の白黒のプリンターに加え、カラープリンター、スキャナ、複写機、ファックス機、およびその他の装置も今日では一般的である。これらの機能の二つ以上に対応している複合機（ＭＦＰ）もまた広く普及している。これらのデバイスは、より広く普及してきているので、より洗練されたまた複雑な文書を処理するために使用されている。
【発明の概要】
【０００３】
第１の例示の実施形態は、入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得することを含み得る。前記ａｘｂ画素マクロセルは、それぞれ４つの非オーバーラップｍｘｎ画素セルを含み、そして前記ａｘｂ画素マクロセルの画素はそれぞれの画素値を有し得る。前記第１の例示の実施形態は、また、少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表すかどうか判定することを含み得る、ここで、ｅは少なくとも１である。前記第１の例示の実施形態は、さらに、おそらく少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表すかどうかに基づき、前記ａｘｂ画素マクロセルの第１の符号化もしくは第２の符号化のいずれかを選択することを含み得る。前記第１の符号化は、前記入力画像のエッジを表す一部の画素を前記入力画像のエッジを表さない画素より重み付けし、また前記第２の符号化は、画素が前記入力画像のエッジを表すかどうかを考慮しない場合がある。前記第１の例示の実施形態は、さらにまた、前記選択された符号化を実行し、そして前記選択された符号化の表現を、実行されたとおりに、コンピュータ読み取り可能な出力媒体に書き込むことを含み得る。
【０００４】
第２の例示の実施形態は、入力画像からａｘｂ画素マクロセルを取得することを含み得る。前記ａｘｂ画素マクロセルの画素はそれぞれの画素値を有し得る、そしてそれぞれのタグに関連付けられ得る。前記第２の例示の実施形態は、また、少なくとも前記それぞれのタグのｅが、タグが関連付けられた画素が前記入力画像のエッジを表すことを示すかどうかを判定することを含み得る、ここで、ｅは少なくとも１である。前記第２の例示の実施形態はさらに、おそらく、タグが関連付けられた画素が前記入力画像のエッジを表すことを、少なくとも前記それぞれのタグのｅが示すかどうかに基づき、前記ａｘｂ画素マクロセルの第１符号化もしくは第２符号化のいずれかを選択することを含み得る。前記第１の符号化は、前記入力画像のエッジを表す画素を前記入力画像のエッジを表さない画素より重み付けし、また前記第２の符号化は、画素がエッジを表すかどうかを考慮しない場合がある。前記第２の例示の実施形態は、さらにまた、前記選択された符号化を実行し、そして前記選択された符号化の表現を、実行されたとおりに、コンピュータ読み取り可能な出力媒体に書き込むことを含み得る。
【０００５】
第３の例示の実施形態は、（１）ａｘｂ属性マクロセル、および（２）入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得することを含み得る。前記ａｘｂ画素マクロセルは、それぞれ４つの非オーバーラップｍｘｎ画素セルを含み、そして前記ａｘｂ画素マクロセルのａｘｂ画素はそれぞれの画素値を有し得る。前記ａｘｂ属性マクロセルの要素は、それぞれの前記ａｘｂ画素マクロセルのそれぞれの画素と一対一方式で関連付けられ得る。前記第３の例示の実施形態は、また、前記４つの非オーバーラップｍｘｎ属性セルをそれぞれ表す４つの属性平面出力値を判定することを含み得る。前記第３の例示の実施形態は、さらに、おそらく、少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表すことを前記ａｘｂ属性マクロセルが示すかどうかに基づき、前記輝度平面の前記ａｘｂ画素マクロセルを表わす１乃至４つの輝度平面出力値を判定することを含み得る、ここで、ｅは少なくとも１である。前記第３の例示の実施形態は、さらにまた、前記第１の色平面の前記ａｘｂ画素マクロセルを表すための第１の色平面出力値および前記第２の色平面の前記ａｘｂ画素マクロセルを表すための第２の色平面出力値を判定することを含み得る。前記第３の例示の実施形態は、また、前記４つの属性平面出力値、前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のインターリーブ表現を、コンピュータ読み取り可能な出力媒体に書き込むことを含み得る。
【０００６】
第４の例示の実施形態は、コンピューティング・デバイスによって実行時、前記第１、第２および／または第３の例示の実施形態に従って、前記コンピューティング・デバイスに操作を実行させるプログラム指示を格納している非一時的でコンピュータ読み取り可能な記憶媒体を含み得る。
【０００７】
第５の例示の実施形態は、少なくとも処理部およびデータ記憶部を備えるコンピューティング・デバイスを含み得る。前記データ記憶部は、前記処理部によって実行時、前記第１、第２および／または第３の例示の実施形態に従って、前記コンピューティング・デバイスに操作を実行させるプログラム指示を内蔵し得る。
【０００８】
他の態様、有利な点、および代替案と同様、これらのことは、必要に応じて添付図面を参照して以下の詳細な説明を読むことによって当業者にとって明白になるであろう。さらに、本明細書における当該概要および他のセクションで提供されている説明は、請求されている主題を限定のためでなく例として示すことを意図していることを理解されたい。
【図面の簡単な説明】
【０００９】
【図１】例示の実施形態に係る印刷デバイスを示す。
【図２】例示の実施形態に係る、印刷デバイスのコンピューティング・コンポーネントをブロック図にて示す。
【図３】例示の実施形態に係る、印刷デバイスを含むさまざまなデータ経路をブロック図にて示す。
【図４】例示の実施形態に係る、電子文書に含まれ得る画像を示す。
【図５】例示の実施形態に係る属性配列を示す。
【図６】例示の実施形態に係る文書処理パイプラインを示す。
【図７】例示の実施形態に係る、４つのセルを含むマクロセルを示す。
【図８】例示の実施形態に係る色平面の決定木を示す。
【図９】例示の実施形態に係るグレースケールの平面決定木を示す。
【図１０】例示の実施形態に係る属性平面の決定木を示す。
【図１１Ａ】例示の実施形態に係る、４つの平面のセルを示す。
【図１１Ｂ】例示の実施形態に係る、出力媒体にインターリーブされた、図１１Ａのセルを示す。
【図１２Ａ】例示の実施形態に係る、４つの平面のセルを示す。
【図１２Ｂ】例示の実施形態に係る、出力媒体にインターリーブされた、図１２Ａのセルを示す。
【図１３】例示の実施形態に係るフローチャートを示す。
【図１４】例示の実施形態に係る別のフローチャートを示す。
【図１５】例示の実施形態に係るさらに別のフローチャートを示す。
【発明を実施するための形態】
【００１０】
本明細書において方法とシステムの例を記述する。さらに他の例示的な実施形態もしくは特徴を利用することは可能であり、また本明細書において提示されている主題の範囲から逸脱することなく、その他の変更をすることは可能である。以下の詳細な説明において、本明細書の一部を構成する添付図面を参照する。
【００１１】
本明細書において記載されている例示的な実施形態は限定することを意図するものではない。したがって、本明細書において全般的に記載され、そして図面に示されているように、本開示の諸態様は、様々に異なる構成に配置し、置き換え、結合し、分割し、および設計することができ、そしてそれらの全てが本明細書において明瞭に熟慮されている。
１．概要
【００１２】
印刷技術は、白黒画像のみを生成する簡単なドットマトリクスベースの出力デバイスから高解像度のカラー画像を生成することができる今日の進歩したレーザーベースの印刷デバイスへと過去３０年以上にわたって発展してきた。それと共に、最近の印刷デバイスは、また、複写機、スキャナ、およびファックス機として機能することも可能である。そうするため、印刷デバイスは、印刷しもしくはファックスするために待ち行列に入れられ、またはスキャンされた多くの電子文書を格納することができる場合がある。従って、多くの印刷デバイスは、例えば、一つ以上の処理部、データ記憶部、および入出力インターフェースを含むことが可能なコンピューティング・デバイスの特殊な形態である。
【００１３】
住宅、企業もしくは別の種類の場所で使用されるかどうかにかかわらず、印刷デバイスは、他のいろいろなコンピューティング・デバイスと通信可能に接続可能な共有のリソースであり得る。従って、状況によっては、多くのコンピューティング・デバイスが印刷のために電子文書を印刷デバイスに送信する場合があるので、印刷デバイスに対する格納の要求はかなり高い場合がある。一般的には、印刷デバイスは、早着順に一度に一つの電子文書を印刷、コピー、ファックス、および／またはスキャンすることがよくある。従って、印刷デバイスは、ともすれば、処理されるのを待っている多数の電子文書を格納する場合がある。さらに、背景画像もしくはロゴを含むオーバーレイ文書等、電子文書によっては、いつまでも印刷デバイスに格納される場合がある。というのは、当該電子文書は、複数の印刷ジョブに利用される可能性があるためである。
【００１４】
データの記憶装置（例えば、ランダム・アクセス・メモリ（ＲＡＭ）、固体メモリ、ハードドライブメモリ、および／またはフラッシュメモリなどのメモリ）のコストは高価である可能性があるので、印刷デバイスのデータ記憶の要求量を低減するために、格納された電子文書を圧縮することは有益であろう。それと共に、電子文書によっては、印刷デバイスからコンピューティング・デバイスへ、および／またはコンピューティング・デバイスから印刷デバイスへ転送される場合があるので、当該電子文書を圧縮することにより、より早く転送することができ、しかもネットワーク容量の使用をより少なくすることができる。
【００１５】
さらに、印刷ジョブは多量な場合がある（例えば、印刷ジョブは、何百ページも含む一つ以上の電子文書を含む場合がある）ので、順番を待っている印刷ジョブを圧縮することにより、各ジョブが印刷される前の短期格納スペースを節約する。これに加えて、ユーザは、後日印刷するために印刷ジョブを長期の記憶装置に保管したい場合がある。従って、印刷ジョブを圧縮することにより、より多くの印刷ジョブを保管できる可能性がある。さらに、大量の印刷ジョブを長期の記憶装置に格納したり検索する動作は手間がかかる可能性があるが、前記印刷ジョブを圧縮して大きさを小さくすることにより早めることが可能である。
２．印刷デバイスの例
【００１６】
図１は例示の印刷デバイス１００を示す。印刷デバイス１００は、部分的におよび／または全体的に格納されている電子文書を各種の物理的出力媒体に印刷するよう構成することができる。当該出力媒体は、いろいろな大きさと種類の紙、オーバーヘッドプロジェクタ用透明フィルムなどを含むが、これらに限定はされない。印刷デバイス１００は、同義的に「プリンター」と呼んでもよい。
【００１７】
印刷デバイス１００は、パーソナルコンピュータ、サーバーデバイス、プリンタサーバー等のコンピューティング・デバイスに対するローカル周辺装置としての働きをする場合がある。この場合、印刷デバイス１００は、シリアルポートケーブル、パラレルポートケーブル、ユニバーサルシリアルバス（ＵＳＢ）ケーブル、ファイヤーワイヤー（ＩＥＥＥ１３９４）ケーブル、もしくは高解像度マルチメディアインターフェース（ＨＤＭＩ）ケーブル等のケーブルによって前記コンピューティング・デバイスに接続することができる。こうして、前記コンピューティング・デバイスは、印刷デバイス１００に対して電子文書の供給源としての働きをすることができる。
【００１８】
一方、印刷デバイス１００は、イーサネットもしくは８０２．１１（Ｗｉｆｉ）インターフェース等の有線もしくは無線のネットワークインターフェースを含み得る。そのように配置されて、印刷デバイス１００は、ネットワークを介して印刷デバイス１００と通信可能な任意の数のコンピューティング・デバイスに対する印刷デバイスとしての働きをすることができる。実施形態によっては、印刷デバイス１００は、ローカル周辺装置およびネットワーク接続されたプリンターの両方としての働きを同時にすることが可能である。印刷デバイス１００を使用するために、コンピューティング・デバイスは、一つ以上のプリンタードライバーを組み込む場合がある。当該プリンタードライバーは、印刷される電子文書を、コンピューティング・デバイスに格納された各種のローカル表現から印刷デバイス１００によりサポートされる一つ以上の表現に変換するソフトウェアコンポーネントを含み得る。
【００１９】
それでも、印刷デバイス１００は、非ジェネリック型のコンピューティング・デバイスとみなすことができ、印刷関連および非印刷関連のタスクの両方を実行することが可能である。
たとえば、印刷デバイス１００は、また、複写機、ファックス機、およびスキャナ機能を含み得る。実施形態によっては、印刷デバイス１００は、複写機および／またはファックス機の機能を促進するためスキャナ部を用いることが可能である。例えば、印刷デバイス１００は、物理的文書をスキャンして電子フォーマットにし、次に得られた電子文書を印刷してコピーを提供し、および／または電話インターフェースを介して得られた電子文書を送信してファックス動作を提供してもよい。さらに、印刷デバイス１００は、電話インターフェースを介してファックスされた電子文書を受信し、次に当該電子文書の表現を圧縮して格納することができる。
【００２０】
各種機能に対応するために、印刷デバイス１００は、原稿の給紙／排紙トレイ１０２、用紙保管部１０４、ユーザーインターフェース１０６、スキャニング要素１０８、および筐体１１０を含むようにしてもよい。印刷デバイスはさまざまな形態を採り得ることを理解されるべきである。従って、印刷デバイス１００は、図１に示された構成要素よりも多いもしくは少ない構成要素、および／または図１に示された構成要素にくらべて異なった仕方で配置された構成要素を含む可能性がある。
【００２１】
原稿の給紙／排紙トレイ１０２は、スキャンされ、コピーされ、もしくはファックスされる物理的文書（例えば、一枚以上の紙の積み重ねた山）を保持することができる。有利なことには、原稿の給紙／排紙トレイ１０２は、印刷デバイス１００による処理のために、印刷デバイス１００が、人手を介することなく、複数枚の物理的文書を自動的に送り出すことを可能にする。
原稿の給紙／排紙トレイ１０２は、また、印刷デバイス１００によって処理された物理的文書を保持するための一つ以上の分離した排紙トレイを含み得る。これらには、印刷デバイス１００によりスキャンされ、コピーされもしくはファックスされた物理的文書と共に、例えば、印刷デバイス１００のファックスおよび／または複写機能により生成された物理的文書も含まれ得る。
【００２２】
用紙保管部１０４は、各種の物理的媒体のためのトレイおよび／または給紙要素を含み得る。例えば、用紙保管部１０４は、８．５ｘ１１インチ用紙、Ａ４用紙、レターヘッドのある用紙、封筒等のための別個のトレイを含み得る。物理的媒体を出力する（例えば、印刷、コピー、および／またはファックスの受信）ことに係わる印刷デバイス１００のあらゆる機能のために、用紙保管部１０４は、前記物理的媒体を供給することが可能である。
【００２３】
ユーザーインターフェース１０６は、ユーザからの入力を受け取ることおよびユーザに出力を提供すること等、印刷デバイス１００と人もしくは人以外のユーザとの情報交換を促進することが可能である。したがって、ユーザーインターフェース１０６は、キーパッド、キーボード、タッチパネルもしくは存在感知パネル、ジョイスティック、マイクロホン、静止カメラおよび／またはビデオカメラ等、入力構成要素を含み得る。ユーザーインターフェース１０６は、また、（例えば、存在感知パネルと組み合わせることが可能である）表示画面、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ベースのディスプレイ、デジタル光処理（ＤＬＰ（登録商標））技術を使用したディスプレイ、電球、および／または既知もしくは今後開発される一つ以上の類似なデバイス等、一つ以上の出力構成要素を含み得る。ユーザーインターフェース１０６は、また、スピーカー、スピーカージャック、オーディオ出力ポート、オーディオ出力デバイス、イヤホンおよび／または既知もしくは今後開発される他の類似のデバイスを介して可聴出力を生成することができるように構成することが可能である。
【００２４】
スキャニング要素１０８は、その下で、可動光源がガラスパネルの上に置かれた物理的媒体をスキャンするよう動作するガラスパネルであり得る。あるいは、ガラスパネルの下のデジタルカメラが、物理的媒体の写真を撮ることにより、ガラスパネルの上に置かれた物理的媒体を「スキャンする」ことが可能である。スキャンされた物理的媒体の画像は、印刷デバイス１００に関連付けられたデータ記憶部に格納され得る。
【００２５】
筐体１１０は、原稿の給紙／排紙トレイ１０２、用紙保管部１０４、ユーザーインターフェース１０６、およびスキャニング要素１０８等印刷デバイス１００の各種構成要素を収容しおよび／または相互に接続する物理的ハウジングを含み得る。それと共に、筐体１１０は、図１に示されていない他の構成要素を収容することができる。例えば、筐体１１０は、一つ以上のトナーカートリッジ、液体インクジェット、ベルト、ローラー、および／または電源部を収容することが可能である。さらに、筐体１１０は、有線および／または無線ネットワークインターフェース、電話インターフェース（例えば、ＲＪ４５ジャック）、ＵＳＢインターフェース、ＢＬＵＥＴＯＯＴＨ（登録商標）インターフェース、カードリーダーのポート等の通信インターフェースを含み得る。
【００２６】
さらに、印刷デバイス１００は、汎用のおよび／または特別に設計されたコンピューティング・デバイス構成要素を搭載する場合があるので、筐体１１０は、また、当該構成要素のいくつかもしくは全てを収容する場合がある。その点に対して、図２は、印刷デバイス１００に含まれ得るコンピューティング・デバイス構成要素（例えば、コンピューティング・デバイスの機能要素）の例示の実施形態２００を示す。
【００２７】
コンピューティング・デバイス構成要素２００は、処理部２０２、記憶部２０４、および入出力部２０６を含み、それらの全てはシステムバス２０８もしくは同様なメカニズムにより接続することができる。処理部２０２は、一つ以上の汎用プロセッサー等の一つ以上の中央処理装置（ＣＰＵ）および／または一つ以上の専用プロセッサー（例えば、特定用途向け集積回路（ＡＳＩＣ）もしくはデジタル信号プロセッサー（ＤＳＰ）等）を含み得る。
【００２８】
記憶部２０４は、次に、揮発性および／または不揮発性データ記憶部を含むことが可能で、処理部２０２に全体的にもしくは部分的に統合され得る。記憶部２０４は、処理部２０２により実行可能なプログラム指示、および本明細書に記載されている各種の方法、プロセス、もしくは機能を実行するために当該指示によって操作されるデータを格納することが可能である。一方、当該方法、プロセス、もしくは動作は、ハードウェア、ファームウェア、および／またはハードウェア、ファームウェア、およびソフトウェアの任意の組み合わせによって規定することができる。従って、記憶部２０４は、一つ以上のプロセッサーによって実行時、本明細書もしくは添付図面に開示された任意の方法、プロセスあるいは機能を印刷デバイス１００に実行させるプログラム指示を格納している、有形で非一時的でコンピュータ読み取り可能な媒体を含み得る。
【００２９】
記憶部２０４は、また、後で処理する（例えば、印刷する）ことができる圧縮されたおよび圧縮されていない電子文書を格納するように構成することが可能である。したがって、記憶部２０４は、当該電子文書に対する出力媒体としての働きをする。
【００３０】
入出力部２０６は、ユーザーインターフェース１０６に関連して記載した任意の動作および／または要素を含み得る。したがって、入出力部２０６は、処理部２０２の動作を構成しおよび／または制御する役割を果たすことが可能である。入出力部２０６は、また、処理部２０２により実行される動作に基づいて出力を提供することが可能である。
【００３１】
これらの印刷デバイスの例は例示の目的で提供されている。上記の例に加えておよび／またはそれに代えて、その他の可能性の中で、本明細書の実施の形態の範囲から逸脱することなく、その他のプリンターとコンピュータ技術の組み合わせおよび／または部分的組み合わせもまた存在し得る。
【００３２】
図３は、印刷デバイス１００により処理された電子文書の表現が通過できるいくつかの実行可能なデータ経路を示す。図３で、印刷デバイス１００は、スキャナ部３０２および印刷部３０４を含み得ると想定している。当該部のそれぞれの制御は、ハードウェア、ファームウェア、ソフトウェア、もしくはハードウェア、ファームウェア、および／またはソフトウェアの任意の組合せにおいて実行され得る。さらに、スキャナ部３０２および印刷部３０４のそれぞれは、コンピューティング・デバイス３００と、およびおそらくその他のコンピューティング・デバイスともまた通信することが可能である。場合によっては、印刷デバイス１００によりサポートされるデータ経路は、「パイプライン」と称される場合がある。
【００３３】
スキャナ部から印刷部へのデータ経路３１０は、スキャナ部３０２および印刷部３０４によりサポートされ得る。スキャナ部から印刷部へのデータ経路３１０は、たとえば、ユーザが印刷デバイス１００に物理的文書をコピーするように指示する場合に使用することができる。当該指示に応じて、スキャナ部３０２は、前記物理的文書を電子文書にスキャンして、スキャナ部から印刷部へのデータ経路３１０を介して、前記電子文書を印刷部３０４に送信することができる。スキャナ部から印刷部へのデータ経路３１０を使用すると、前記電子文書（おそらく圧縮された形式で）の一部もしくは全てを印刷デバイス１００のデータ記憶部に少なくとも一時的に格納することが含まれ得る。そして、印刷部３０４は、前記電子文書を物理的媒体（たとえば、一枚以上の用紙）に印刷することが可能となる。
【００３４】
スキャナ部からホストへのデータ経路３０６は、また、スキャナ部３０２とコンピューティング・デバイス３００によりサポートされ得る。スキャナ部からホストへのデータ経路３０６は、たとえば、ユーザが印刷デバイス１００に物理的文書をスキャンするように指示する場合に使用することができる。前記ユーザはまた、印刷デバイス１００に、得られた電子文書の表現をコンピューティング・デバイス３００に送信するよう指示することができる、もしくは印刷デバイス１００は、前記電子文書を自動的にコンピューティング・デバイス３００に送信するよう予め構成されていてもよい。このようにして、当該指示に応じて、スキャナ部３０２は、物理的文書をスキャンして電子文書にし、そして前記得られた電子文書をスキャナ部からホストへのデータ経路３０６を介してコンピューティング・デバイス３００に送信することができる。スキャナ部からホストへのデータ経路３０６を使用すると、前記電子文書の一部もしくは全てを印刷デバイス１００のデータ記憶部に少なくとも一時的に（おそらく圧縮された形式で）格納し、および前記得られた電子文書の表現をコンピューティング・デバイス３００に送信し得る。
【００３５】
ホストから印刷部へのデータ経路３０８は、コンピューティング・デバイス３００と印刷部３０４によりサポートされ得る。ホストから印刷部へのデータ経路３０８は、たとえば、ユーザがコンピューティング・デバイス３００に印刷デバイス１００の電子文書を印刷するように指示する場合に使用することができる。当該指示に応じて、コンピューティング・デバイス３００は、前記電子文書の表現を印刷部３０４に送信することができる。印刷デバイス１００は、印刷部３０４を介して、前記電子文書を物理的媒体に印刷することができる。前記電子文書の一部もしくは全ては、前記電子文書の印刷前および／または印刷中に、印刷デバイス１００のデータ記憶部に（おそらく圧縮された形式で）格納され得る。
【００３６】
上記の少なくとも一つのデータ経路に対して、並びに印刷デバイス１００によりサポートされているおそらく他のデータ経路に対して、明らかに、電子文書は、ネットワークもしくはケーブルを介して格納および／または送信する必要があるであろう。電子文書を格納および／または送信のために圧縮することにより、当該電子文書の格納と送信両方に関する効率性を向上することができる。たとえば、電子文書を、平均して元の大きさの４分の一に圧縮できた場合、約４倍多くの電子文書を既定の容量のデータ記憶部に格納することができる。さらに、当該圧縮された電子文書を、ネットワークもしくはケーブルを介して送信すると、圧縮されていない電子文書を送信するより約４倍速く送信することができる。
【００３７】
従来、一部のデータ経路には不可逆圧縮が使用されてきた可能性がある一方、その他のデータ経路には可逆圧縮が使用されてきた可能性がある。（不可逆圧縮技法は、データの一部を廃棄して圧縮するが、一方可逆圧縮技法は全く廃棄しないでデータを圧縮する。）たとえば、ある実装例では、ホストから印刷部へのデータ経路３０８は、電子文書の印刷バージョンにおけるテキストおよび線画のシャープエッジを維持するために可逆圧縮を利用する場合がある。その一方で、スキャナ部からホストへのデータ経路３０６およびスキャナ部から印刷部へのデータ経路３１０は、スキャンされたグラフィック画像を含む物理的文書を効率よく格納および送信するために不可逆圧縮を利用する場合がある。印刷デバイス１００は、自身のデータ経路の少なくとも一部およびおそらく全てに対して、同じもしくは類似の圧縮技法を使用することによってより効率化され、またソフトウェアおよび／またはハードウェアの実装が簡易化され得る。
【００３８】
このように、可逆圧縮および不可逆圧縮の両方に対応する圧縮技法が好ましい。また、可逆圧縮および不可逆圧縮の両方が、同じ文書内で適用できることが好ましい。その点に対して、画像がどのように表されるかを理解することが有用であろう。
３．画像の例
【００３９】
画像は、画像形式および色モデルに従って符号化された画素のマトリックスであるといってもよい。図４は、印刷デバイス１００によって取扱われる物理的もしくは電子文書上あるいはその内部に含まれ得る画像４００を示す。画像４００は、白と黒で表示されているが、同様の特性を持つカラー画像もまた、印刷デバイス１００で取り扱うことが可能である。画像４００は、他の例の中で、６００ドット／インチ（ｄｐｉ）もしくは１２００ｄｐｉ等、さまざまな解像度を用いて形成され得る。
【００４０】
図４で見ることができるように、画像４００は、様々な種類の内容を含む。例えば、画像４００は、シャープエッジを持つテキストと線画の両方を含む。さらに、画像４００は、また、連続階調を含む部分（例えば、画像４００の上方左手の角）、並びに写実的なデータを含む部分（例えば、画像４００の下方右手および上方右手の角）を含む。テキストが、画像４００のいろいろな部分に重ね合わさっている。このように、画像４００は、業務用の印刷、例えば、カタログのページ、雑誌、ちらし、あるいは広告において使用される一般的な種類の画像を示している。
【００４１】
いくつかの実行可能な実施の形態においては、例示の画像４００等、画像におけるそれぞれの画素は、３つの異なるオブジェクトタイプ―すなわち、画像グラフィックス、ベクターグラフィックス、あるいはテキスト―の１つとして分類することができる。画像グラフィックスは、写真の画像等、写実的な画像を含む。画像４００の下方右手角および上方右手角の写実的なデータは、画像グラフィックスに該当し得る。画像４００全体にわたる非テキストのラインは、ベクターグラフィックスに該当し、テキスト文字（例えば、「Ｅ」および「Ｒ」）がテキストに該当し得る。
【００４２】
特定の画素のオブジェクトタイプは、印刷デバイスのスキャナ部もしくは電子文書のページ記述言語（ＰＤＬ）の表現によって判定してもよい。ＰＤＬは、印刷されたもしくは表示されたページの外観を、ページの実際の画素より高級レベルで記述する言語、文法、もしくはフォーマットである。ページの画素表現は、ＰＤＬから得ることができる。
【００４３】
このように、電子文書は、ＰＤＬ文書により表現される１枚以上のページを含み得る。これらのページのそれぞれは、ＰＤＬ文書の一部もしくはすべて、および／または画像により表現され得る。ＰＤＬには多くの例があり、その中のポータブル・ドキュメント・フォーマット（ＰＤＦ）はその１つである。
【００４４】
画像４００を含む電子文書の必要メモリを低減するために依然として不可逆圧縮を使用しながらも、統合圧縮技法は、画像４００のシャープエッジおよびラインを正確に表現することができるであろう。特に、テキスト、基本的な幾何学的形状、および線画等、特定の要素の正確な特性を維持することが好ましい、なぜならば、これらの要素に軽微な歪みがあっても人の目には不快に見える場合があるからである。従って、これらの要素は、ベクターグラフィックスもしくはテキストとして分類され、可逆的方式での圧縮の対象とされる可能性がある。
【００４５】
その一方で、写実的な画像およびグラデーションがある複雑なグラフィックスは、そのような正確さ無しで見ることができる。従って、これらの要素は、画像グラフィックスとして分類され、不可逆的方式での圧縮の対象とされる可能性がある。たとえば、画像グラフィックスは、人の目に対して、個別の圧縮されていないバージョンと視覚的に同じかもしくは類似に見えるように圧縮することができる。
【００４６】
さらに、画素のオブジェクトタイプ（例えば、画像グラフィックス、ベクターグラフィックス、もしくはテキスト）は、前記画素に適用された色変換、並びに前記画素に適用されたハーフトーンスクリーンの種類に影響を及ぼす可能性がある。これらの課題は、以下でより詳細に説明する。
【００４７】
ある場合には、ベクターグラフィックスおよびテキストオブジェクトは、類似の特性を有するように見えるかもしれない。実際、これら２つのカテゴリーは、実施の形態によっては結合され、また同じ方式で処理され得る。しかしながら、薄く色づけられたライン等、ベクターグラフィックスの特定の種類は、テキストとは異なるように処理された場合、よりよく見える。たとえば、薄く色付けられたラインが、テキストと同じ方式で処理された場合、それらのラインの中には識別するのが困難になるものがあり得る。従って、ベクターグラフィックスに対して異なる色変換および／または異なるハーフトーンスクリーンを適用すると、これらのラインを維持および／または向上する可能性がある。例えば、ベクターグラフィックス画素に対してハーフトーンスクリーンを特別に選択すると、当該画素が印刷された場合、より多くのトナーが塗布される結果が得られる可能性がある。
４．画像の色モデルの例
【００４８】
電子文書は、多くの色モデルを用いて表現することができる。従って、ロバストな圧縮技法は、それらのモデルの一部またはすべてに影響を与えることができるであろう。さらに、圧縮技法は、個々の色モデルに対して特有な前処理を含む場合がある。
【００４９】
例えば、赤‐緑‐青（ＲＧＢ）色モデルは、テレビ、モニター、およびコンピュータ画面等、電子出力デバイスの画像の表示に使用することができる。ＲＧＢは、加法色モデルで、赤、緑、および青の光がさまざまな方法で足し合わされて色のスペクトラムを生成する。例えば、シアンは、緑と青を混ぜ合わせて作ることができ、イエローは、赤と緑を混ぜ合わせて作ることができ、マゼンタは、赤と青を混ぜ合わせて作ることができ、白は赤、緑、および青を混ぜ合わせて作ることができる。
【００５０】
ＲＧＢ画像の特定の画素は、３面タプル（Ｒ、Ｇ、Ｂ）として表すことができ、各面は、ゼロから所定の最大値（例えば、２５５）まで変化し得る。すべての面が０の場合、結果は黒色になるであろう。すべての面が最大値の場合は、結果は最も明るく表現可能な白となるであろう。（本明細書に記載する色平面は、また、カラーチャネルと称することがある）
【００５１】
ＲＧＢ出力は、異なる出力デバイスは異なる方式で同じＲＧＢ画像を表示する可能性があるという点で、一般的にデバイス依存である。従って、場合によっては、これらの差異は人によって知覚される場合がある。実施の形態によっては、スキャナ部からホストへのデータ経路３０６を用いて印刷デバイス１００にスキャンされた物理的文書は、ＲＧＢ色モデルを用いて符号化される場合がある。
【００５２】
シアン‐マゼンタ‐イエロー（ＣＭＹ）色モデルは、印刷デバイスによるカラー画像の印刷に使用され得る。ＣＭＹは、減法色モデルで、シアン、イエロー、およびマゼンタがさまざまな方法で白い表面に塗布されて色のスペクトラムを再生する。例えば、赤はマゼンタとイエローを混ぜ合わせて作られ、青はシアンとマゼンタを混ぜ合わせて作られ、緑はシアンとイエローを混ぜ合わせて作られ得る。このように、ＣＭＹ色モデルは、ＲＧＢ色モデルの補完とみなすことができる。
【００５３】
ＣＭＹ画像の特定の画素は、３面タプル（Ｃ、Ｍ、Ｙ）として表すことができ、各面は、０から所定の最大値まで変化し得る。すべての面が０の場合、結果は白色であろう。すべての面が最大値の場合、結果は黒色であろう。
【００５４】
ＲＧＢ出力のように、異なる印刷デバイスについて、同じＣＭＹ画像の印刷された出力が異なって見え得る点で、ＣＭＹ出力は、一般的にデバイス依存である。場合によっては、これらの差異は人によって知覚される場合がある。実施の形態によっては、ホストから印刷部へのデータ経路３０８および／またはスキャナ部から印刷部へのデータ経路３１０を用いて印刷デバイス１００によって印刷された電子文書は、ＣＭＹ色モデルを用いて符号化される場合がある。
【００５５】
実施の形態によっては、４面ＣＭＹＫ色モデルもまた使用され得る。当該ＣＭＹＫの４面モデルは、キー（ブラック）面もまた使用されることを除いて、ＣＭＹ色モデルと類似もしくは同じであり得る。できる限りシアン、マゼンタ、およびイエローを混ぜ合わせて黒色を作ることに加えて、別個のキー（ブラック）インクソースが黒色を作るために使用され得る。このように、ＣＭＹＫ画像の特定の画素は、４面タプル（ＣＭＹＫ）として表され、各面は、ゼロから所定の最大値まで変化し得る。
【００５６】
ＣＭＹＫ色モデルを用いると、ＣＭＹモデルと同じ色がサポートされ、しかもＫ着色剤が、Ｃ、Ｍ、およびＹ着色剤の混合物に取って代わることができるので、一般的にインクの使用量が低減する。しかしながら、ＣＭＹＫ色モデルは、常に他の色モデルにおよび他の色モデルから都合よく変換できるということではない、なぜならばＫ着色剤を追加したことが冗長性を増す―例えば、異なるＣ、Ｍ、Ｙ、およびＫの組み合わせを混ぜ合わせた結果が同じ色であり得る―ためである。実施の形態によっては、画素をＣＭＹモデルからＣＭＹＫモデルに、および／または他の色モデルの組の間で変換するために、一つ以上のカラーテーブルが使用され得る。
【００５７】
更なる色モデルはグレーで、グレースケールとも称され、黒色と白色の画像の表現に対して使用され得る。ＲＧＢおよびＣＭＹ／ＣＭＹＫ色モデルと異なり、グレー色モデルの各画素は、画素の明度を符号化する単一の平面（Ｋ）を用いて表される。グレー平面で使用される値は、黒色に対するゼロから、白色に対する所定の最大値（例えば、２５５）まで変化し得る。実施の形態によっては、印刷デバイス１００によってサポートされている一つ以上のデータ経路が、グレー色モデルを用いて画像を符号化できる場合がある。
【００５８】
さらなる色モデルはＹＣｂＣｒである。実装例によっては、当該色モデルは、画像の代替表現として使用され得る。特に、Ｙ平面は、画素の明度を表し、ＣｂおよびＣｒ平面は、それぞれ、青‐黄クロミナンス、および赤‐緑クロミナンスを表し得る。Ｙ平面は輝度を表しているにもかかわらず、ＣｂおよびＣｒ平面のように「色平面」と称される場合がある。ＹＣｂＣｒ色モデルは、ＲＧＢおよびＣＭＹ色モデルと明確に定義された関係を有し、これらの色モデルのいずれにも、もしくはいずれからも比較的容易に変換することができる。ＹＣｂＣｒ色モデルのグレースケールバージョンは、Ｙ色モデルと称される場合がある。
【００５９】
ＹＣｂＣｒ色モデルのさらなる有利な点は、ＹＣｂＣｒ色モデルを用いて符号化された画像の圧縮がＲＧＢもしくはＣＭＹ／ＣＭＹＫ色モデルで符号化された画像の圧縮よりもより効率的である傾向にあるということである。特に、人の目は、画像の高周波の（例えば、急激に変化する）クロミナンス情報をあまり検出できない。従って、ＹＣｂＣｒ色モデルを用いて符号化された画像は、ＣｂおよびＣｒ平面の高周波成分を無視することにより当該知見を利用することができる。そのため、特定の色モデルで符号化された画像は、圧縮性能を向上するために圧縮する前にＹＣｂＣｒ色モデルに変換される場合がある。
５．属性平面の例
【００６０】
色平面に加え、画像は、属性平面を用いてデジタル的に表現することができる。属性平面の値は、画像に目に見えて表れないかもしれないが、属性平面は、画像の圧縮と処理動作に対してガイダンスを与えるために利用することができる。
【００６１】
例として、画像の各画素は、属性を表すビット配列（例えば、８ビットもしくは１６ビット）に関連付けることができる。当該属性の中には、画素が他の題材の上にあるオーバーレイとして使用されているか、前記画像のエッジの一部として使用されているか、あるいは印刷もしくはコピーの特徴の一部として用いられているかどうかを示す場合があり得る。他の属性として、画素を色モデル間で変換する時に使用する色変換テーブルに対する基準および／または画素を印刷する時に使用するハーフトーンスクリーンに対する基準が含まれる場合がある。各画素の関連付けられた属性配列の中のビットは、印刷デバイスのスキャナ部により、もしくは電子文書のＰＤＬから決定され得る。
【００６２】
属性平面の配列は、関連付けられた画素が表すオブジェクトタイプを特定するために使用される場合がある。当該特定されたオブジェクトタイプは、例えば、グラフィック画像、ベクターグラフィックス、もしくはテキストを含み得る。オブジェクトタイプのタグは、そのような属性配列の一つ以上のビットであり得る。
【００６３】
例示の属性配列５００を図５に示す。属性配列５００は、オーバーレイビット５０２、未使用ビット５０４、エッジビット５０６、２つのカラーテーブルビット５０８、５１０、コピーもしくは印刷ビット５１２、および２つのハーフトーンビット５１４、５１６を含む。
【００６４】
オーバーレイビット５０２は、関連付けられた画素が他の題材にオーバーレイするかどうかを示す。たとえば、印刷デバイスの中には、いくつかの印刷ジョブに対して一つ以上の背景画像もしくはパターンの適用をサポートするものがある。これらの画像あるいはパターンは、ロゴもしくは縁飾り等、静的であるかもしれないし、もしくは自動ページ付け（例えば、文書の各ページの底部に「３分の１ページ」等のフレーズを表示すること）等、動的であるかもしれない。
【００６５】
たとえば、自動ページ付けの場合、印刷デバイスは、ユーザによりページ番号を付けるように指示されるであろう。ユーザは、印刷デバイスのユーザーインターフェースのオプションを選択して自動ページ付けを指定することができる。それに代わり、電子文書を印刷デバイスに送信するコンピュータのプリンタードライバーが自動ページ付けを指定する場合がある。その他の場合において、印刷デバイスは、どの画素が背景の画素（ページの白色の背景）等に対して前景の画素（ページのテキスト等）であるかを検出し、前景の画素がオーバーレイされていることを表示する場合がある。
【００６６】
エッジビット５０６は、関連付けられた画素が画像のエッジの一部であるかどうかを示し得る。例えば、エッジビット５０６は、そうである場合１の値を取り、そうでない場合０の値を取り得る。エッジビット５０６は、スキャナ部（例えば、スキャナ部３０２）によって設定され、薄く色づけられた輪郭にも隣接した濃く色づけられた輪郭のエッジ近くの画素をマークすることができる。例えば、エッジビットは、薄い背景のテキスト文字の境界を表わす画素に対して、１に設定され得る。エッジビット５０６は、以下に述べるように、インテリジェントダウンサンプリングの使用を通して画像のエッジを強調するために使用することができる。
【００６７】
カラーテーブルビット５０８、５１０は、１つの適切な例として、ＣＭＹとＣＭＹＫ色モデル間の色平面の値のマッピングを含むカラーテーブルを示し得る。上述したように、画素のオブジェクトタイプ（例えば、画像グラフィックス、ベクターグラフィックス、もしくはテキスト）は、前記画素が得られた電子文書のＰＤＬ表現から、もしくはスキャナ部により決定され得る。
【００６８】
前記画素の前記オブジェクトタイプに基づき、異なる色変換テーブルを適用することが出来る。例えば、カラーテーブルビット５０８、５１０は、前記画素がテキストオブジェクトの一部である場合「００」の値を取り、前記画素がベクターグラフィックスオブジェクトの一部である場合「０１」の値を取り、前記画素が画像グラフィックスオブジェクトの一部である場合「１１」の値を取る場合がある。カラーテーブルビット５０８、５１０の値に基づき、いくつかの色変換テーブルうちの１つが選択され、前記画素に適用され得る。
【００６９】
コピーもしくは印刷ビット５１２は、前記関連付けられた画素がコピーされる（スキャンされ、次に印刷される）かもしくは（例えば、ローカルに格納されたＰＤＬ文書からもしくは別のデバイスから受信して）従来通り印刷されるかどうかを示すことができる。当該ビットの値は、ハーフトーンビット５１４、５１６の値と結合され、最大８つのハーフトーンスクリーン（ハーフトーン処理の説明については下記を参照のこと）のうちの１つを選択し得る。場合によっては、スキャンされ、次に印刷される電子文書は、特定の種類のハーフトーンスクリーンを使用し、一方従来通り印刷される電子文書は、他の種類のハーフトーンスクリーンを使用する場合がある。
【００７０】
ハーフトーンビット５１４、５１６は、画像が印刷されるときに、前記画像にハーフトーンスクリーンが適用されるかどうか、そしてどのハーフトーンスクリーンを適用するかを示すことができる。ハーフトーン処理は、大きさ、形状、および間隔が異なるドットの使用を通して勾配をシュミレートする技法である。ハーフトーン処理は、各種の色の複数の濃淡を含む画像を、各スクリーンは特定の色の単一の（２値の）濃淡を含みながら、一連のオーバーレイされたハーフトーンスクリーンに分解することができる。オーバーレイされたハーフトーンスクリーンは、前記ドットが滑らかな階調に混和される外観を作り出す。
【００７１】
カラーテーブルビット５０８、５１０と同様に、ハーフトーンビット５１４、５１６は、前記画素が表わすオブジェクトのタイプに基づき値を取ることができる。例えば、ハーフトーンビット５１４、５１６は、前記画素が画像グラフィックスオブジェクトの一部である場合、「００」の値を取り、前記画素がベクターグラフィックスオブジェクトの一部である場合、「０１」の値を取り、前記画素がテキストオブジェクトの一部である場合、「１１」の値を取ることができる。ハーフトーンビット５１４、５１６の値に基づき、いくつかのハーフトーンスクリーンの一つが選択され、前記画素に適用され得る。
【００７２】
同じ３つのオブジェクトタイプに基づいているが、カラーテーブルビット５０８、５１０は、ハーフトーンビット５１４、５１６とは異なる場合がある。当該２つの異なる情報の組を保持する１つの考えられる理由は、いくつかのＰＤＬで混ざり合うオブジェクト画素の重なりに対応するためである。例えば、テキスト画素がラスター画像の画素と混ぜ合わされている場合、カラーテーブルビット５０８、５１０はラスター画像を表示し、ハーフトーンビット５１４、５１６はテキストを表示することができる。この機能により、重なり合って混ぜ合わされているオブジェクトの画像品質を維持している。
【００７３】
例示の属性配列５００は、画素当り８ビット（１バイト）を含んでいる。したがって、このスタイルの属性配列を用いることにより、属性平面の大きさは、画像内の画素の数と直線的に増大する。画像内の画素に関連付けられている属性配列の範囲は、当該画像に対する属性平面と称される場合がある。
【００７４】
属性平面は、Ａ平面と称せられる場合がある。したがって、属性平面が一つ以上の色平面と組み合わされた場合、前記属性と色平面の組み合わせは、用いられる色モデルによって、ＫＡ、ＣＭＹＡ、ＣＭＹＫＡ、ＲＧＢＡ、ＹＡ、もしくはＹＣｂＣｒＡと称される場合がある。ここで、属性平面は実際には色それ自体を表現していないけれども、これらの属性と色平面の組み合わせの例は、「色モデル」と称される場合がある。
６．画像パイプラインの例
【００７５】
例示の画像パイプラインの高いレベルの全体像を図６に示す。当該画像パイプラインは、フローチャート６００の形を取り、複数の圧縮および解凍のステップを含む。フローチャート６００は、電子文書を受信し、格納し、および印刷するために印刷デバイスによって実行される一連のステップを表すことができる。
【００７６】
図６のブロック６０２で、前記電子文書は、ＹＡもしくはＹＣｂＣｒＡ色モデルに従ってフォーマットされた一つ以上の画像として表現され得る。しかしながら、これらの色モデルは、例示の目的で選択されており、その他の色モデルも使用することができる。ＹＡもしくはＹＣｂＣｒＡ画素は、元の紙の文書もしくは他の対象物のスキャンプロセスから得ることができる。それに代えて、ブロック６０２で、前記電子文書は、例えば、ビットマップ、ＪＰＥＧ、ＧＩＦ等の画像フォーマットにより表現され、そしてＹＡもしくはＹＣｂＣｒＡ色モデルに変換されてもよい。
【００７７】
ブロック６０４で、セルベースの圧縮（下記で詳細に説明される）が前記電子文書の各平面の画素に適用され得る。例えば、ＹＡ電子文書に対して、セルベースの圧縮がグレー平面および属性平面に適用され得る。ＹＣｂＣｒＡ電子文書に対して、Ｙ、Ｃｂ、Ｃｒ、およびＡ平面のそれぞれに対して別々にもしくは複合方式でセルベースの圧縮が適用され得る。従って、場合によっては、セルベースの圧縮は、二つ以上の平面の対応するセルを同じ論理的操作で圧縮する場合がある。ブロック６０４の結果は、前記電子文書の圧縮バージョンを表わすビットストリームであり得る。
【００７８】
ブロック６０６で、当該圧縮バージョンは、記憶出力媒体に格納され得る。一般に、当該記憶装置は、１枚以上のページの圧縮表現を格納する印刷デバイスの記憶部であってもよい。本明細書に記載された圧縮技法は、これらの文書を元のビットマップサイズの少なくとも３分の１もしくは４分の１に圧縮できるので、当該記憶装置の必要なメモリの大きさはそれに応じて低減することができる。その結果、本明細書の実施形態を採りいれている印刷デバイスは、よい安価に製造することができる。
【００７９】
ブロック６０６における記憶装置に属する圧縮されたページは、印刷デバイスにより印刷されるかもしれないし、されないかもしれない。場合によっては、これらのページは、ブロック６０６０の記憶装置から可搬型ストレージ（例えば、ＵＳＢストレージ、セキュア・デジタル（ＳＤカード）等）に送信され、もしくはパーソナルコンピュータのホストに送信される場合がある。ページは、ユーザもしくはプログラムが、これらのページについて印刷、あるいは何か他のことをすると決定するまで、ブロック６０６の記憶装置に何日間、何週間等、保持される場合がある。
【００８０】
ブロック６０８で、セルベースの解凍が前記電子文書の各平面に適用され得る。これにより、前記電子文書のＹＡもしくはＹＣｂＣｒＡ表現の再現結果を得ることができる。しかしながら、前記セルベースの圧縮技法が不可逆圧縮を用いた場合、ブロック６０８の解凍から得られる電子文書は、ブロック６０４の圧縮により圧縮された前記電子文書とは異なる場合がある。しかしながら、前記電子文書のこれらのバージョン間の差異はわずかであり、従って人によって容易に知覚されないかもしれない。
【００８１】
ブロック６１０で、前記電子文書の前記解凍バージョンはさらに処理され得る。例えば、さまざまな変換が前記電子文書に適用され得る。これらの変換のうち一つ以上の変換が前記電子文書に実行された後、前記電子文書は、再びブロック６０４で圧縮され、ブロック６０６で記憶装置に格納され得る。ブロック６１０の適用は随意であり、すべての電子文書が当該処理の対象とはならないであろう。
【００８２】
ブロック６１２で、前記電子文書の前記解凍バージョンはまた、さらに処理され得る。ブロック６１４で、セルベースの圧縮が前記電子文書の各平面に適用され得る。当該圧縮処理手続きは、ブロック６０４の処理手続きと同じであるか、もしくは異なる場合がある。例えば、ブロック６１４で適用される圧縮は、ブロック６０４の圧縮比率よりも高いかもしくは低い圧縮比率を得るように構成してもよい。
【００８３】
ブロック６１６で、当該圧縮バージョンは、記憶装置に格納され得る。ブロック６０６の格納装置のように、当該格納装置は、１枚以上のページの圧縮表現を格納する印刷デバイスの記憶部であってもよい。これらのページ表現は圧縮されているので、記憶装置の必要メモリとコストは低減される。
【００８４】
ブロック６１８で、セルベースの解凍が、前記電子文書の各平面に適用され得る。これにより、ブロック６１４で圧縮された前記電子文書の表現の再現結果を得ることができる。ブロック６０８の場合と同様に、前記セルベースの圧縮技法が不可逆圧縮を用いた場合、ブロック６１８の解凍から得られる前記電子文書は、ブロック６０４および／またはブロック６１４の圧縮により圧縮された前記電子文書のバージョンとは異なる場合がある。
【００８５】
ブロック６２０で、前記電子文書の解凍バージョンに対してさらなる処理が適用され得る。ブロック６２０の後、前記電子文書は印刷の準備ができているであろう、もしくは更なる処理が適用されてもよい。
【００８６】
ブロック６０４および６１４のセルベースの圧縮の処理手続きは同じであるか、もしくは異なる場合がある。例えば、これらの処理手続きは、異なる圧縮アルゴリズムを使用するか、あるいは同じもしくは異なる設定で同じ圧縮アルゴリズムを使用してもよい。同様に、ブロック６０８と６１８のセルベースの解凍の処理手続きもまた、同じかもしくは異なる場合がある。
【００８７】
実施の形態によっては、画素当り使用される属性平面ビットの数は、フローチャート６００において圧縮が行われる場所に基づいて変わる可能性がある。例えば、属性配列５００の全てのビット（未使用ビット５０４を除く可能性はある）がブロック６０４で圧縮されるかもしれない。
【００８８】
しかしながら、ブロック６１２の後、オーバーレイビット５０２、未使用ビット５０４、エッジビット５０６、およびカラーテーブルビット５０８、５１０は、もはや必要でないかもしれない。さらに、印刷装置の中には、複写機能を有していないものがある。したがって、これらの印刷デバイスに対しては、コピーもしくは印刷ビット５１２は、フローチャート６００のどの場所でも使用されないであろう、そしてブロック６０４およびブロック６１４の圧縮から除外してもよい。
【００８９】
それでも、さまざまな実施の形態において、属性配列５００のゼロから６ビットのどこででもセルベースの圧縮処理手続きから除外される可能性がある。その結果、セル当り圧縮される全体のビットの数は低減され、その結果として、前記属性平面のセルの達成可能な圧縮比率を向上する可能性がある。
【００９０】
本明細書の前記説明は、画像の属性と色平面に適用されるセルベースの圧縮の単一のインスタンスに焦点を合わせている。前記画像は、１枚以上のページを含む電子文書からの１枚のページの表現でもよい。しかしながら、パイプライン６００もしくはその他の配置に従って、当該セルベースの圧縮の複数のインスタンスはそのような画像のセルに適用することができる。このようにして、画像全体が効率的な方式で圧縮され得る。
【００９１】
さらに、セルベースの解凍技法は、また、本明細書に記載のセルベースの圧縮技法を逆転することによって前記画像に適用することができる。
７．セルの構成の例
【００９２】
セルベースの圧縮の１つの態様は、電子文書の各色平面および属性平面を一つ以上のｍｘｎセルに分割し、次に各セルを部分的に独立したもしくは完全に独立した方式で圧縮することができるというものである。例えば、ｍが８かつｎが４でもよい。あるいは、同様に、ｍが８かつｎも８、もしくはｍが１６かつｎも１６でもよい。その他のｍおよびｎの値を用いてもよい。
【００９３】
各セルは、当該セル内のデータを圧縮するためにどの種類の圧縮技法が最も効率的かを判定するために評価され得る。例えば、セルが、同じ色の画素で全面的に構成される場合、前記セルの中のデータは、前記色の表現に大変効率よく圧縮されるであろう、またたぶん一部のオーバーヘッドデータも大変効率よく圧縮されるであろう。しかしながら、セルが、写実的な画像の一部を含む場合、前記セルの中のデータは、そのような高い圧縮比率で圧縮することはできないであろう。
【００９４】
図７は、セルベースの圧縮で使用できる例示のセル構造を示す。便宜上、セルはｐセルとｑセルという用語で考える。ｐセルは、画像の色平面もしくは属性平面のｍｘｎエレメントブロックであり得る。したがって、色平面に対して、ｐセルエレメントは画素であり得る一方、属性平面に対しては、ｐセルエレメントは属性配列であり得る。ｑセルは、画像の色平面もしくは属性平面のａｘｂエレメントブロックであり得る。各ｑセルは、非オーバーラップｐセルのいくつかの数から構成され得る。文脈によって、「ｐセル」および「ｑセル」という用語は、単一の属性もしくは単一の色平面のエレメント、あるいは複数の属性および複数の色平面のエレメントを指す場合がある。
【００９５】
例として、図７は、それぞれが特定の平面に対して６４の属性もしくは画素値を含む４つの８ｘ８ｐセル７００、７０２、７０４、７０６を示す。各属性もしくは画素値は、例えば、０乃至２５５の範囲の数字によって表わすことができ、したがってバイトとして表すことができる。しかしながら、他の可能性も存在する。簡単にするために、ｐセル７００は、ある代表値の場所を示すのみとする。
【００９６】
図７に示すように４つのｐセルの２ｘ２配列は、ｑセルと称する場合がある。したがって、図７のｑセル７１０は１６ｘ１６であり、特定の平面に対して２５６の属性もしくは画素値を含む可能性がある。しかしながら、ｑセルは異なる数のｐセル（例えば、３ｘ２、２ｘ３、もしくは３ｘ３ブロックのｐセル）を含み得る。
【００９７】
図７で、上方左手のｐセルを「ａ」ｐセル、上方右手のｐセルを「ｂ」ｐセル、下方左手のｐセルを「ｃ」ｐセル、および下方右手のｐセルを「ｄ」ｐセルと称する。これらの呼称は、ｐセル識別情報と呼んでもよい、そしてｑセル内のｐセルの位置を識別するための単なる便利な方法に過ぎず、下記のインターリービングの説明で使用されるであろう。
【００９８】
本明細書に記載のセルベースの圧縮技法は、ｐセルおよびｑセルに作用し得る。簡単にするために、８ｘ８ｐセルおよび１６ｘ１６ｑセルが使用されるものとする。しかしながら、当該前提は、異なる大きさのｐセルおよびｑセルが代わりに使用できることを理解の上でなされる。
【００９９】
さらに、プレーナｐセルもしくはｑセルは単一の平面のエレメントを指し、一方複合ｐセルもしくはｑセルは複数の平面間にわたって対応するエレメントを指す場合がある。例えば、ＣＭＹＡ色モデルが使用される場合、プレーナｐセルは、Ｃ、Ｍ、Ｙ、もしくはＡ平面のうちの１つの平面のエレメントを含む可能性があるが、一方複合ｐセルは、Ｃ、Ｍ、Ｙ、およびＡ平面のうちの２つ以上の平面のエレメントを含む可能性がある。
８．セルベースの圧縮の例
【０１００】
次のいくつかのサブセクションは、さまざまなセルベースの圧縮の技法を詳細に説明する。それぞれのこれらの技法は、ｐセル、ｑセル、もしくは両方を用いて動作する。表１にこれらの圧縮技法の概要を提供する。
2016144210.tif 000003
【０１０１】
属性平面のみに使用される圧縮技法をより一般的な用語で以下に説明することができる、なぜならば、システムによっては、特定の実施の形態に対して、色平面にも使用される場合があるからである。例えば、本明細書に記載のセルベースの圧縮が、パイプライン６００のブロック６０４で使用されるとする。異なる圧縮スイートがパイプライン６００のブロック６１４で使用され得る。従って、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、Ｐ４、Ｄ１Ｃ、Ｄ１Ｅ、およびＤ６４圧縮を全般的に説明する。
ａ．Ｄ１およびＤ１Ｄ圧縮
【０１０２】
Ｄ１圧縮は、所与のｐセルの属性もしくは画素の全てが同じである場合に使用することができる。例えば、前記ｐセルの各属性もしくは画素が０から２５５の値を取るとする。単なる一つの例として、全ての値が７４とすると、Ｄ１圧縮を当該セルに適用することができる。このようにして、前記ｐセルを表わすために必要とされるデータ量は大幅に低減することができる。
【０１０３】
Ｄ１Ｄ圧縮と称され得るＤ１圧縮のバリエーションは、色値がデフォルトの色である場合に使用することができる。例えば、ＹＣｂＣｒ色空間のＹ平面、グレー色空間、およびすべてのＣＭＹＫ色空間において、デフォルトの値は０および２５５であり得る。ＹＣｂＣｒ色空間のＣｂおよびＣｒ平面においては、デフォルトの値は１２８および２５５であり得る。Ｄ１Ｄ圧縮は、Ｄ１圧縮よりも幾分より効率的な符号化を備えている。色空間においては、限られた数のデフォルト値（例えば、２）があるのみなので、これらのデフォルトの色値は、少ない数のビット（例えば、１）で表すことができる。その結果、Ｄ１Ｄ圧縮は、必要とするｐセル当りのビット数はＤ１圧縮よりも少なくてもよい。
【０１０４】
属性平面に対して、前記Ｄ１Ｄデフォルト値は、予め定めることができる（例えば、０もしくは１２８）かあるいはユーザによって手動で設定することができる。
【０１０５】
場合によっては、すべての属性もしくは画素に対して同じ値を持つ複数の隣接したｐセル（例えば、行内もしくは列内のｐセル）は、Ｄ１もしくはＤ１Ｄ符号化を用いて表現することができる。これが起こり得る可能性のある２つの方法がある。Ｄ１およびＤ１Ｄ圧縮の両方とも、ランレングスが符号化されることを可能とする。前記ランレングスは、Ｄ１圧縮を用いて合計いくつのｐセルもまた圧縮されたかを表す。Ｄ１圧縮は、また、前に使用された（キャッシュされた）属性もしくは画素値を後続のｐセルの符号化において使用することを可能とする。
2016144210.tif 000004
【０１０６】
表２は、Ｄ１およびＤ１Ｄ圧縮に対する２進コード化の例を提供する。Ｄ１圧縮に対して、ｐセルの圧縮表現はオペコード００１で始まる。Ｖ’ビットが１である場合、Ｄ１符号化は、また、１バイトの値引数（これはｐセルのすべての属性もしくは画素に対して同じである）を含む。Ｖ’ビットが０である場合、値引数は符号化から除外され、最新のＤ１符号化における値（例えば、キャッシュされた値）が前記ｐセルのすべての属性もしくは画素に対して用いられる。レングス引数は２ビットであり得る、そして１乃至４ｐセルのｑセル内のランレングスに対応している。前記値引数は画素値並びに属性値に該当する。従って、前記値引数は、色平面のｐセルを圧縮する場合８ビットであり得る。しかしながら、上記のように、８ビット以下のビット数を用いて属性平面の値を表す場合があり、値フィールドの大きさが適切に低減される場合がある。
【０１０７】
Ｄ１Ｄ圧縮に対して、ｐセルの圧縮表現は、オペコード０００で始まる。Ｖビットは、２つのデフォルト値のうちどちらを用いるかを示す（例えば、Ｖが０の場合、１つの値が用いられ、またＶが１の場合、もう片方の値が用いられるであろう）。前記レングス引数は、Ｄ１圧縮に対して用いた方式と同じ方式で用いることができる。
ｂ．Ｐ２およびＰ２Ｄ圧縮
【０１０８】
Ｐ２圧縮は、所与のｐセルの属性もしくは画素のそれぞれが２つの値のうち１つを用いて表わすことができる場合に使用することができる。例えば、セルの属性もしくは画素が０と２５５の間の値を取り得るが、すべての値が７６もしくは１２５のいずれかである場合、Ｐ２圧縮を前記ｐセルに用いることができる。Ｐ２圧縮が用いられる場合、前記２つの値、並びに前記ｐセルの属性もしくは画素のビットマップが符号化され得る。前記ビットマップは、どの値が前記ｐセルの各属性もしくは画素に関連付けられているかを示す。Ｄ１およびＤ１Ｄ圧縮と同様に、Ｐ２圧縮は最後に使用された値の組のキャッシングを用いることができる。
【０１０９】
Ｐ２Ｄ圧縮と称されることがあるＰ２圧縮技法のバリエーションは、２つのデフォルトの色値のみがセルに現れる場合に用いることができる。上記のように、ＹＣｂＣｒ色空間のＹ平面、グレー色空間、およびすべてのＣＭＹＫ色空間において、デフォルトの値は０および２５５であり得る。ＹＣｂＣｒ色空間のＣｂおよびＣｒ平面においては、デフォルトの値は１２８および２５５であり得る。従って、Ｐ２Ｄ圧縮は、前記ｐセルの属性もしくは画素の前記ビットマップを符号化し得るが、明示的に前記属性もしくは画素の値を符号化する必要はない、なぜならば、前記デフォルトの値が用いられるからである。
【０１１０】
前記属性平面に対して、１つもしくは両方のＰ２Ｄデフォルト値は予め設定できる（例えば、０および１２８）あるいはユーザによって手動で設定することができる。
2016144210.tif 000005
【０１１１】
表３は、Ｐ２およびＰ２Ｄ圧縮に対する２進コード化の例を提供する。Ｐ２圧縮に対して、ｐセルの圧縮表現はオペコード０１１で始まる。Ｖ’ビットが１である場合、Ｐ２符号化は、また、前記ｐセルの属性もしくは画素によって用いられる値の組（値１および値２）を示す２バイトを含む。Ｖ’ビットが０である場合、これらの値は符号化から除外され、最新のＰ２符号化における値（例えば、キャッシュされた値）が前記ｐセルの属性もしくは画素に対して用いられる。
【０１１２】
Ｐ２Ｄ圧縮に対して、ｐセルの圧縮表現は、オペコード０１０で始まる。Ｐ２およびＰ２Ｄ圧縮の両方に対して、Ｐオプションが１の場合、ラインマップ引数が存在し、前記ビットマップの中の８ラインのどれがまた存在するかを示す。Ｐオプションが０の場合、ラインマップ引数もあるいは前記ビットマップの中のラインも存在しない。その代わりに、Ｐ２もしくはＰ２Ｄで圧縮された最新のｐセルからキャッシュされたビットマップを使用することができる。
【０１１３】
ラインマップの各ビットは、前記ビットマップの中に対応するラインフィールドが存在することを示す。前記ラインマップが存在する場合、前記ビットマップの中に少なくとも１本のラインがまた存在すると想定することができる。従って、前記ラインマップは、前記ビットマップの中の２番目から８番目のラインまでを符号化するために７ビットを使用するのみでよい。前記ラインマップの各ビットに対して、０は対応するラインが無く、前のラインが繰り返すことを示し、一方、１は、対応するラインが存在することを示す。
ｃ．Ｐ４圧縮
【０１１４】
Ｐ４圧縮は、所与のセルのすべての画素が、３つもしくは４つの色値を用いて表わすことができる場合に使用され得る。Ｐ４圧縮が使用される場合、３つもしくは４つの値、並びに前記ｐセルの属性もしくは画素のビットマップを符号化することができる。前記ビットマップは、どの値が前記ｐセルの各属性もしくは画素と関連付けられているかを示す。
2016144210.tif 000006
【０１１５】
表４は、Ｐ４圧縮に対する２進コード化の例を提供する。Ｐ４圧縮に対して、ｐセルの圧縮表現はオペコード１００で始まる。Ｐ２ビットマップのラインマップと同様に、７ビットのラインマップは、前記ビットマップがどのように圧縮されているかを明確にする。前記ラインマップの各ビットに対して、０は対応するラインが無く、前のラインが繰り返すことを示し、一方、１は、対応するラインが存在することを示す。
【０１１６】
前記４つの値引数は、ｐセルの中で検出されたエレメントの値を表す８ビットフィールドである。これらの値の間を識別するために、前記ビットマップの各ライン（存在する場合）は１６ビット長であろう。Ｐ４圧縮によって３つの値のみが符号化された場合、「値４」の引数は存在し得るが無視される。
ｄ．Ｄ１ＣおよびＤ１Ｅ圧縮
【０１１７】
Ｄ１ＣおよびＤ１Ｅ圧縮は、Ｄ１もしくはＤ１Ｄ圧縮の候補である連続したセルのランの効率的な符号化を促進する。これらのランを符号化すると、ソリッドカラー（例えば、白色の背景）を示す部分を有する画像についての圧縮性能を大幅に高めることができる。２種類のＤ１もしくはＤ１Ｄラン―すなわち、（１）ｑセルを横断するＤ１もしくはＤ１Ｄ候補のｐセルのｑセル間ラン、（２）ｑセル内のＤ１もしくはＤ１Ｄ候補のｐセルのｑセル内ラン―がサポートされ得る。
【０１１８】
ｑセル間Ｄ１もしくはＤ１Ｄランは、２つ以上のｑセルにわたるＤ１もしくはＤ１Ｄランを符号化する。ｑセル内の２つの右端のｐセル（前記「ｂ」および「ｄ」ｐセル）が、Ｄ１圧縮を用いて符号化される８×１６配列の一定の画素値を含む場合、Ｄ１もしくはＤ１Ｄランの開始を意味し、そして符号化モードをノーマル符号化モードからＤ１もしくはＤ１Ｄラン符号化モードに変えさせる。当該符号化モードは、平面毎に追跡され、またｑセル境界上で追跡される。従って、特定の平面に対して、Ｄ１もしくはＤ１Ｄラン符号化モードへのモード変化がセル境界の端部で起きる。
【０１１９】
Ｄ１もしくはＤ１Ｄラン符号化モードにおいて、２つのコードのみ―すなわち、Ｄ１Ｃ（続行）およびＤ１Ｅ（終了）―が定義され、それらはそれぞれ単一ビットを用いて符号化される。後続のｑセルが、前記ランを開始した２つのＤ１もしくはＤ１Ｄ候補ｐセルと同じ１６×１６画素値を含む限り、１ビットのＤ１Ｃオペコードが送出され、Ｄ１もしくはＤ１Ｄラン符号化モードが続行する。後続のｑセルが、前記ランの開始に適合する同じ色調の値以外の値を含む場合、前記ランは終了する。かかる場合には、１ビットのＤ１Ｅコードが送出され、ノーマル符号化モードに再度入る。また、現在のｑセルに対する任意の残りのＤ１、Ｐ２、Ｐ４、もしくはＤ６４符号化が送出される。
【０１２０】
ｑセル内のＤ１もしくはＤ１Ｄランは、ｑセル内でＤ１もしくはＤ１Ｄランを符号化する。例えば、ｑセル内の１つから４つのｐセルに及ぶＤ１もしくはＤ１Ｄランを符号化するために、２ビットのランレングスが使用され得る。そのようなランはＤ１（ｎ）およびＤ１Ｄ（ｎ）と表される、ここで、ｎは値１、２、３、もしくは４を取る。
2016144210.tif 000007
【０１２１】
表５は、Ｄ１ＣおよびＤ１Ｅ圧縮に対する２進コード化の例を提供する。Ｄ１Ｃ圧縮に対して、１はＤ１もしくはＤ１Ｄランの続行を示し、所与のｑセルの中の４つの全てのｐセルは、現在のランのＤ１もしくはＤ１Ｄセルと一致する。Ｄ１Ｅ圧縮に対して、０はＤ１もしくはＤ１Ｄランの終了を示す。
ｅ．Ｄ６４圧縮
【０１２２】
Ｄ６４圧縮は、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、およびＰ４圧縮が適切でない属性平面のｐセルを符号化するために使用される可逆技法である。例えば、ｐセルが５つ以上の異なる値を含む場合、Ｄ６４圧縮を使用することができる。
【０１２３】
Ｄ６４圧縮は、８ｘ８属性ｐセルの６４個の値すべてを符号化し、ヘッダーを含む場合は、圧縮というよりは極小さく伸張する結果となる。しかしながら、属性平面は可逆方式で圧縮するのが好ましいので、場合によってはＤ６４圧縮が必要になる場合がある。
【０１２４】
しかしながら、セルベースの圧縮が圧縮のパイプライン６００のどこで行われるかによって、ｐセルの属性値の８ビット全ては符号化されないかもしれない。その代わりに、これらの値の２乃至８ビットが圧縮および符号化され得る。これにより、Ｄ６４圧縮が向上する結果となる。
2016144210.tif 000008
【０１２５】
表６は、Ｄ６４圧縮に対する２進コード化の例を提供する。Ｄ６４ｐセルの圧縮表現はオペコード１１で始まり、また、属性当り２乃至８ビットを用いて符号化された、前記ｐセルの中の６４の属性配列を含む。属性配列当りのビット数は、上記のように、属性平面を圧縮する場合にどれだけの数の属性ビットを除外できるかによる。
ｆ．ファイルの終わり（ＥＯＦ）
【０１２６】
ＥＯＦは、それ自体圧縮技法ではないが、その代わりに、圧縮ストリームの最後を合図することと定義される。圧縮プログラムにて、すべての入力データが圧縮され、最後のｑセルの最後のコードが送出された後、ＥＯＦシーケンスが送出され得る。前記ＥＯＦは、属性平面のコードとして送出される。
【０１２７】
前記属性平面がＤ１もしくはＤ１Ｄラン符号化モードにある場合、前記ＥＯＦが送出される前に、Ｄ１Ｅが送出されてノーマル符号化モードに戻る場合がある。さらに、ＥＯＦは、前記属性平面以外のすべての平面での、すべてのアクティブなｑセル間Ｄ１もしくはＤ１Ｄランを自動的に終了させる。
2016144210.tif 000009
【０１２８】
表７は、ＥＯＦに対する２進コード化の例を提供する。オペコード００１の後、２進値「１００００００００００」が送出される。前記ＥＯＦは、Ｄ１圧縮とオペコードを共有するので、当該値は、ＥＯＦをｐセルのＤ１符号化から区別するために使用することができる。
ｇ．ＤＣＴ４：２：０もしくはＤＣＴ  Ｙ圧縮
【０１２９】
ＤＣＴ４：２：０圧縮は、離散コサイン変換（ＤＣＴ）技法を使用して、ＣｂおよびＣｒ色平面の解像度が水平方向と鉛直方向の両方向に２分の１に低減されるようにダウンサンプリングされたｑセルを圧縮することを指す。
【０１３０】
複合モード操作として、ＤＣＴ４：２：０圧縮は、ＣｂおよびＣｒ平面をそれぞれ１つのｐセルにダウンサンプリングおよび圧縮する一方、ｐセルごとに１つのＤＣＴ操作（合計４つのＹ平面ＤＣＴ操作のために）を用いてＹ平面を圧縮することが可能である。ＤＣＴ４：２：０圧縮は、また、ＤＣＴ変換、拡大縮小、量子化、二次元の係数配列から一次元のデータへの並べ替え、およびハフマンエントロピー符号化を含み得る。
【０１３１】
ＣｂおよびＣｒ平面に対して、当該技法は、最初にｑセルをｐセルの大きさにダウンサンプリングし、次に前記得られたｐセルに対してＤＣＴ符号化を適用する。例として、１６ｘ１６ｑセルは、８ｘ８ｐセルにダウンサンプリングされ得る。前記ダウンサンプリング処理手続きは、前記１６ｘ１６ｑセルを６４の非オーバーラップ２ｘ２ブロックに分割し、そして各ブロックを前記各ブロックの画素値の平均である（これらの２ｘ２ブロックが任意のエッジを表すかどうかは考慮されない）単一の画素値に置き換えることを含み得る。前記得られた６４の平均値は、８ｘ８セルを構成する。特に、当該ダウンサンプリングは、最初の４：１圧縮率をもたらす、そして次にＤＣＴ符号化がさらに追加して圧縮をもたらす。
【０１３２】
ＤＣＴ  Ｙ圧縮は、グレースケール画像（すなわち、ＣｂもしくはＣｒ平面が存在しない）のＹ平面の前記４つのｐセルのそれぞれにＤＣＴ符号化を行うことを指す。従って、ＤＣＴ  Ｙは、実際にはプレーナモード操作であるが、１つだけ色平面があるので、名目上の複合モード操作と考えることができる。
2016144210.tif 000010
【０１３３】
表８は、ＤＣＴ４：２：０およびＤＣＴ  Ｙ圧縮に対する２進コード化の例を提供する。ＤＣＴ圧縮は、オペコードを含まない―その代り、表８で定義されているように、ＤＣＴ圧縮ｐセルの６つのフィールドから成り得る。前記属性平面でのインターリービングのために（下記のインターリービングの説明を参照のこと）、これらの圧縮されたｐセルは、圧縮された属性ｐセルによって互いに分割することができ、ＤＣＴ４：２：０圧縮のためのオペコードに対する必要性を無くしている。しかしながら、ＤＣＴ４：２：０圧縮の一部の表現は、一つ以上のオペコードを含み得る。ＤＣＴ４：２：０符号化のように、ＤＣＴ  Ｙ符号化は、通常オペコードは使用しない。
【０１３４】
実施の形態によっては、各ＤＣＴ符号化は、ハフマン符号化を用いる、ジョイント・フォトグラフィック・エキスパート・グループ（ＪＰＥＧ）規格のサブセットに従ってひとまとめにされた量子化ＤＣＴ係数の収集であり得る。
ｈ．インテリジェントダウンサンプリングを用いるＤＣＴ４：２：０圧縮
【０１３５】
インテリジェントダウンサンプリングを用いるＤＣＴ４：２：０圧縮は、ダウンサンプリング処理手続きが、エッジを表さない画素よりもエッジを表す画素に重み付けすることを除いて、上記のＤＣＴ４：２：０圧縮と同一である。
【０１３６】
ダウンサンプリングは、全般的に画像品質が低下するのを回避しながら圧縮率を高めることができるので有利である。このことは、画像内容に関して特にＣｂおよびＣｒ平面に当てはまる、なぜならばこれらの平面は、ダウンサンプリングにより発生しうるアーチファクトへの耐性が本来的にあるからである。その一方で、テキストおよびベクターオブジェクトは当該耐性を有していない。テキストおよびベクターオブジェクトをダウンサンプリングすると、細部および鮮鋭さが低下するおそれがあり、また色ずれなどのアーチファクトが発生するおそれがある。
【０１３７】
インテリジェントダウンサンプリング技法は、属性平面のエッジビットを利用して基本的なダウンサンプリングを改善するものである。これらのエッジビットは、テキストおよびベクターオブジェクトにおいて鮮鋭さを維持し、それにより圧縮画像の品質を高めるようにダウンサンプリングを調整するために用いられる。
【０１３８】
特に、単一のダウンサンプリングされた画素値に置き換えられる各２ｘ２ブロック（４画素）において、前記属性平面のエッジビットに関連付けられる画素の数が数えられる。当該合計が０もしくは４の場合、４画素の画素値は平均化され、ダウンサンプリングされた画素値に書き込まれる。しかしながら、４画素の１乃至３がエッジビットに関連付けられる場合、エッジビットに関連付けられる画素の値のみが平均化され、ダウンサンプリングされた画素値に書き込まれる。
【０１３９】
例として、２ｘ２ブロックが以下のＣｂもしくはＣｒ平面の画素値―すなわち、０、７２、７６、および１―を含むとする。さらに、７２および７６の値を有する画素はエッジビットに関連づけられており、０および１の値を有する画素はエッジビットに関連づけられていないとする。そうすると、７２および７６の値を有する画素は平均化され、得られた画素値の７４がダウンサンプリングされた画素値に書き込まれ得る。その結果、７２および７６の値を有する画素により表わされるエッジが強調され得る。
【０１４０】
インテリジェントダウンサンプリングを用いるＤＣＴ４：２：０圧縮は、表８に規定されている符号化を用いることができる。
ｉ．ＤＣＴＬ圧縮
【０１４１】
ＤＣＴＬ圧縮は、また、ＣｂおよびＣｒ平面だけでなくすべての色平面をダウンサンプリングし、かつ圧縮することを除き、ＤＣＴ４：２：０圧縮と同様である。ＤＣＴＬ圧縮は、Ｙ平面上で小さい範囲の輝度値を有するｑセルに適用することが可能である。
2016144210.tif 000011
【０１４２】
表９は、ＤＣＴＬ圧縮に対する２進コード化の例を提供する。ＤＣＴＬ圧縮に対して、ｑセルの平面の圧縮表現は、オペコード１で始まる、そして表現の残りの部分はＤＣＴ符号化である。ＤＣＴ４：２：０の場合と同様に、ＤＣＴ符号化は、ハフマン符号化を用いる、ＪＰＥＧ規格のサブセットに従って圧縮された量子化ＤＣＴ係数の集合でありうる。
ｊ．ＱＤ１およびＱＤ１Ｄ圧縮
【０１４３】
ＱＤ１圧縮は、所与のｑセルのすべての画素が同じかもしくは値が近い場合に使用され得る。
ＱＤ１圧縮は、ｑセル全体を同じ画素値で符号化する。前記ｑセルの画素値がお互いに十分近いかどうかは、前記ｑセルの各ｐセル内の画素値の範囲、および各ｐセルの平均値間の差異を調べることにより判定することができる。例えば、前記各ｐセル内の画素値の範囲がセルレベルの閾値以下であり、および前記ｐセルの平均値が、すべてお互いのマクロセルレベル閾値以内である場合、ＱＤ１圧縮を用いることができる。実施の形態によっては、たとえば、セルレベルの閾値は２と１６の間で、一方、マクロセルレベル閾値は１と８の間である場合がある。
【０１４４】
ＱＤ１Ｄ圧縮は、Ｄ１Ｄ圧縮に類似している。したがって、ＱＤ１Ｄ圧縮は、ｑセルの画素値がＹ、Ｃｂ、もしくはＣｒに対するデフォルト値に一致する場合に使用することができる。
【０１４５】
ＱＤ１およびＱＤ１Ｄ圧縮は、それぞれ、ともにＤ１およびＤ１Ｄ圧縮についての不可逆のバリエーションである。ＱＤ１およびＱＤ１Ｄ圧縮に伴う限定された損失量を認めることにより、ＤＣＴベースの圧縮の圧縮率と比較して大幅に圧縮率を高めることができる。さらに、Ｄ１およびＤ１Ｄ圧縮のように、ＱＤ１およびＱＤ１Ｄ圧縮はランを可能にし、それによりさらに圧縮率を高める。
【０１４６】
その点に応じて、同じ画素値を有する複数の隣接するｑセル（例えば、行もしくは列内のｑセル）には、ＱＤ１もしくはＱＤ１Ｄ符号化を用いることが可能である。各ＱＤ１およびＱＤ１Ｄ符号化は、それぞれ、暗に、ＱＤ１もしくはＱＤ１Ｄセルのランの開始を示す。同じ色平面の中に２つ以上のＱＤ１もしくはＱＤ１Ｄセルのランが存在する場合、ランの２番目および任意の後続のＱＤ１もしくはＱＤ１Ｄセルは、ＱＤ１Ｃ符号化（下記参照）により表わされ得る。ランはＱＤ１Ｅ符号化（下記参照）で終了し得る。
2016144210.tif 000012
【０１４７】
表１０は、ＱＤ１およびＱＤ１Ｄ圧縮に対する２進コード化の例を提供する。ＱＤ１圧縮に対して、ｑセルの圧縮表現は、オペコード０１で始まる。Ｖ’ビットが１である場合、前記ＱＤ１符号化は、また、１バイト画素の値引数（前記ｑセルのすべての画素に対して同じである）を含む。Ｖ’ビットが０である場合、前記値引数は符号化から除外され、最新のＱＤ１符号化の値が、前記ｑセルのすべての画素に対して用いられる。
【０１４８】
ＱＤ１Ｄ圧縮に対して、ｐセルの圧縮表現は、オペコード００で始まる。前記Ｖビットは、２つのデフォルト値のうちどれを用いるかを示す（例えば、Ｖが０である場合、一つの値が用いられ、Ｖが１である場合、もう一方の値が用いられるであろう）
ｋ．ＱＤ１ＣおよびＱＤ１Ｅ圧縮
【０１４９】
上記のように、特定の色平面内のランの非先頭セルを符号化する場合、２つのコードのみ―すなわち、ＱＤ１Ｃ（続行）およびＱＤ１Ｅ（終了）―が定義され、それらは、それぞれ、単一ビットを用いて符号化される。後続のｑセルが、ランを開始した前記ｑセルと同じ画素値を含む限り、１ビットのＱＤ１Ｃオペコードが送出され、そしてＱＤ１もしくはＱＤ１Ｄラン符号化モードが続行する。後続のｑセルが、前記ランの開始に対応する同じ色調の値以外の値を含む場合、前記ランは終了する。かかる場合には、１ビットのＱＤ１Ｅコードが送出され、ノーマル符号化モードに再度入る。
2016144210.tif 000013
【０１５０】
表１１は、ＱＤ１ＣおよびＱＤ１Ｅ圧縮に対する２進コード化の例を提供する。ＱＤ１Ｃ圧縮に対して、１はＱＤ１もしくはＱＤ１Ｄランの続行を示す。ＱＤ１Ｅ圧縮に対して、０はＱＤ１もしくはＱＤ１Ｄランの終了を示す
ｌ．複合およびプレーナモード
【０１５１】
上記のように、ｑセルは、プレーナモード（各平面が独立して圧縮される）もしくは複合モード（２つ以上の平面が、関連する方式で圧縮される）のいすれかで圧縮することができる。実施の形態によっては、属性平面はプレーナモードを用いて圧縮されるのみかもしれないが、色平面は、その特性に基づいて、いずれかのモードを用いて圧縮され得る。
【０１５２】
圧縮ビットストリームにおいて、特定のｑセルに対して用いられているモードを示すために、各ｑセルの圧縮表現の初めに特別のｑオペコードが送出され得る。ｑセルが複合モードを用いて圧縮される場合、前記ｑオペコードは１であり得る、一方ｑセルがプレーナモードを用いて圧縮される場合は０であり得る。
2016144210.tif 000014
【０１５３】
表１２は、複合モードおよびプレーナモードが用いられた場合を規定する。たとえば、ｑセルに対して（インテリジェントダウンサンプリングを用いるもしくは用いない）ＤＣＴ４：２：０圧縮もしくはＤＣＴ  Ｙ圧縮が用いられる場合、当該ｑセルは、１のｑオペコードで始まるが、ｑセル内の各色平面の符号化に対してオペコードは存在しない。
【０１５４】
その他の圧縮技法がｑセルに対して用いられる場合、当該ｑセルは、０のｑオペコードが前書きされ、用いられる圧縮技法がそのオペコードで示される。また、ノーマルモードとランモードの間の区別はプレーナモードにおいてのみ存在する。例えば、ＱＤ１、ＱＤ１Ｄ、もしくはＤＣＴＬ圧縮を用いる任意のｑセル符号化はノーマルモードにおいて実行され、一方ＱＤ１ＣもしくはＱＤ１Ｅ圧縮を用いる任意のｑセル符号化はランモードにおいて実行される。プレーナモードから複合モードに切り替えると、暗黙的にすべてのランが終了する。
【０１５５】
複合の符号化は属性平面の符号化を含まないことに留意されたい。属性平面は、別々に符号化されると考えられる。
【０１５６】
下記のインターリービングの説明で、複合モードおよびプレーナモード符号化の更なる例を提供する。
９．決定木の例
【０１５７】
ｐセルおよびｑセルの符号化は一つ以上の決定木に基づく場合がある。各決定木は、ｐセルもしくはｑセルが符号化される前にさまざまな要因が考慮されるプロセスを示す。属性平面、色平面、およびグレースケール平面に対して別個の決定木があり得る。例えば、属性平面を圧縮する場合、いかなる情報も損失しないことが好ましい。従って、属性平面は、さまざまな可逆圧縮技法を用いて圧縮される可能性がある。その一方で、色平面のある部分（例えば、ベクターグラフィックスおよびテキスト部分）およびグレースケールは、画素の特性評価に基づき様々な程度の損失を伴って圧縮することが好ましい。このようにして、元の画像の細部を必要に応じ維持することができ、しかも高い圧縮率を達成することができる。
ａ．色平面決定木
【０１５８】
図８は、例示の実施形態に従って、色平面の決定木８００を示す。当該決定木は、ｑセルが４つの非オーバーラップｐセルから成ることを理解した上で、ｑセルの特性を考慮する。そのようなｑセルおよびｑセルに従属するｐセルの大きさは、それぞれ、１６ｘ１６および８ｘ８であり得る。しかしながら、その代わりに他の大きさも使用する場合がある。
【０１５９】
前記ｑセルの各画素は、前記画素が入力画像におけるエッジの一部であるかどうかという表示でタグ付けされている。これらのタグは、前記ｑセルに対する属性平面に存在する場合がある。
【０１６０】
各決定ブロック８０２、８０６、８１０において、決定の種類がかっこに入れて示されている。前記決定がプレーナ基準でされる場合、括弧付きのＰが存在する。前記決定が複合基準でされる場合、括弧付きのＣが存在する。
【０１６１】
プレーナ決定は、各色平面の前記ｑセルおよび／またはｐセルを別個に考慮してなされる。したがって、例えば、プレーナ決定は、単一のｑセルおよび／またはｐセルに関連付けられた色の特性および／または属性を考慮する場合がある。しかしながら、複合決定は、ｑセルによって規定された画像の場所のすべての色平面に対する前記ｑセルとｐセルの特性および関連付けられた属性を考慮する場合がある。
【０１６２】
簡単にするために、ＱＤ１Ｄ圧縮は決定木８００において明示的には参照されない。しかしながら、ＱＤ１が考慮されるあるいは用いられる場合は必ず、ＱＤ１Ｄ圧縮もまた考慮されあるいは用いられ得る。したがって、ブロック８１４はＱＤ１Ｄ圧縮を用いる場合がある。連続するＱＤ１もしくはＱＤ１Ｄ符号化のランは、また、決定木８００で明示的に考慮されていないが、それでも使用される場合がある。
【０１６３】
ブロック８０２で、エッジビットが前記ｑセルの任意の属性バイトに対して設定されているかどうかを判定する。設定されている場合、インテリジェントダウンサンプリングを用いるＤＣＴ４：２：０圧縮がブロック８０４で適用される。適用する場合、前記画像のエッジの鮮鋭さは維持されおよび／または向上され得る。
【０１６４】
そうでない場合、ブロック８０６で、任意の色平面の任意のｐセルが所定の閾値より大きい画素範囲を示すかどうか判定される。示す場合、インテリジェントダウンサンプリングを用いないＤＣＴ４：２：０圧縮が、ブロック８０８で適用され得る。ｐセルの画素範囲は、前記ｐセルの最も高い画素値から前記ｐセルの最も低い画素値を差し引くことにより判定され得る。所定の閾値は、８、１６、３２等の値を取り得る。
【０１６５】
そうでない場合は、ブロック８１０で、条件Ａが各色平面に対して別個に審査される。条件Ａに適合するためには、（１）各ｐセルの画素範囲は所定のセルレベル閾値以下であること、および（２）ｐセルの平均画素値の範囲が所定のマクロセルレベル閾値より小さいことが必要である。前記所定のセルレベル閾値は、４、８、１６等の値を取り、前記所定のマクロセルレベル閾値は、２、４、８等の値を取り得る。実施の形態によっては、前記所定のマクロセルレベル閾値は前記所定のセルレベル閾値より小さく、また前記所定のセルレベル閾値は前記所定の閾値より小さい。
【０１６６】
条件Ａが当てはまる場合、当該平面の前記ｑセルの画素は狭い範囲の画素値を有しており、ＱＤ１圧縮がブロック８１４で適用される。条件Ａが当てはまらない場合は、ＤＣＴＬ圧縮がブロック８１２で適用される。
【０１６７】
図８は、１つの可能性のある色平面の決定木を示す。その他のこのような決定木も可能である。
ｂ．グレースケール平面決定木
【０１６８】
図９は、例示の実施形態に従って、グレースケール平面の決定木９００を示す。当該決定木は、ｑセルが４つの非オーバーラップｐセルから成ることを理解した上で、ｑセルの特性を考慮する。そのようなｑセルおよびｑセルに従属するｐセルの大きさは、それぞれ、１６ｘ１６および８ｘ８であり得る。しかしながら、その代わりに他の大きさも使用する場合がある。グレースケール画像は、輝度（Ｙ）もしくはキー（Ｋ）平面のみを含む、そのためこれらの画像のｑセルは、プレーナ方式で圧縮することができる。
【０１６９】
色平面の決定木と同様、前記ｑセルの各画素は、前記画素が入力画像におけるエッジの一部であるかどうかという表示でタグ付けされている。これらのタグは、前記ｑセルに対する属性平面に存在し得る。
【０１７０】
各決定ブロック９０２、９０６、９１０において、決定の種類がかっこに入れて示されている。グレースケール画像は単一の色平面を有するので、そのような決定のすべてがプレーナである。したがって、これらの決定は、単一のｑセルおよび／またはｐセルに関連付けられた特性および／または属性を考慮する。
【０１７１】
簡単にするために、ＱＤ１Ｄ圧縮は決定木９００において明示的に参照されない。しかしながら、ＱＤ１が考慮されるあるいは用いられる場合は必ず、ＱＤ１Ｄ圧縮もまた考慮されあるいは用いられ得る。したがって、ブロック９１４はＱＤ１Ｄ圧縮を用いる可能性がある。連続するＱＤ１もしくはＱＤ１Ｄ符号化のランは、また、決定木９００で明示的に考慮されていないが、それでも使用され得る。
【０１７２】
ブロック９０２で、エッジビットが前記ｑセルの任意の属性バイトに対して設定されているかどうかを判定する。設定されている場合、ＤＣＴ  Ｙ圧縮がブロック９０４で適用される。そうでない場合、ブロック９０６で、前記画素平面の任意のｐセルが所定の閾値より大きい画素範囲を示すかどうか判定される。示す場合、ＤＣＴ  Ｙ圧縮がブロック９０８で適用され得る。ｐセルの前記画素範囲は、前記ｐセルの最も高い画素値から前記ｐセルの最も低い画素値を差し引くことにより判定され得る。前記所定の閾値は、８、１６、３２等の値を取り得る。
【０１７３】
ＤＣＴ  Ｙ圧縮は、ｑセルの中のｐセルのそれぞれにＤＣＴベースの圧縮を実行する。例えば、１６ｘ１６ｑセルは、４つの８ｘ８ｐセルに分割され得る、そしてＤＣＴベースの圧縮が各８ｘ８ｐセルに適用され得る。
【０１７４】
そうでない場合は、ブロック９１０で、条件Ａが審査される。条件Ａ適合するためには、（１）各ｐセル画素の範囲は所定のセルレベル閾値以下であること、および（２）ｐセルの平均画素値の範囲が所定のマクロセルレベル閾値より小さいことが必要である。前記所定のセルレベル閾値は、４、８、１６等の値を取り、前記所定のマクロセルレベル閾値は、２、４、８等の値を取り得る。実施の形態によっては、前記所定のマクロセルレベル閾値は前記所定のセルレベル閾値より小さく、また前記所定のセルレベル閾値は前記所定の閾値より小さい。
【０１７５】
条件Ａが当てはまる場合、前記ｑセルの画素は狭い範囲の画素値を有しており、ＱＤ１圧縮がブロック９１４で適用される。条件Ａが当てはまらない場合は、ＤＣＴＬ圧縮がブロック９１２で適用される。
【０１７６】
図９は、１つの可能性のあるグレースケール平面の決定木を示す。その他のこのような決定木も可能である。
ｃ．属性平面決定木
【０１７７】
図１０は、例示の実施形態に従って、属性平面の決定木１０００を示す。当該決定木は、当該属性平面のｐセルの各要素が、一対一方式で一つ以上の対応する色平面のｐセルの画素値と関連づけられていることを理解した上で、属性平面のｐセルの特性を考慮する。これらのｐセルの大きさは８ｘ８であり得るが、代わりにその他の大きさを用いてもよい。また、属性平面は１つしかないと想定され、そのため決定木１０００におけるすべての決定はプレーナベースでなされる。しかしながら、別の実施の形態では、異なる手法を取るかもしれない。
【０１７８】
決定木８００および９００と同様に、Ｄ１ＤおよびＰ２Ｄ圧縮は明示的に決定木１０００で参照されない。しかしながら、Ｄ１もしくはＰ２圧縮が考慮されもしくは用いられる場合は必ず、Ｄ１ＤおよびＰ２Ｄ圧縮もまた考慮されもしくは用いられ得る。したがって、ブロック１００２、１００４、１００６、および１００８は、Ｄ１ＤおよびＰ２Ｄ圧縮を考慮および／または用いる可能性がある。連続するＤ１もしくはＤ１Ｄ符号化のランは、また、決定木１０００で明示的に考慮されていないが、それでも使用され得る。
【０１７９】
ブロック１００２で、前記属性平面のｐセルがＤ１圧縮に適している（すなわち、前記ｐセルのすべての属性配列が同一である）かどうか判定される。適している場合、Ｄ１圧縮がブロック１００４で適用される。そうでない場合は、ブロック１００６で、前記ｐセルがＰ２圧縮に適している（すなわち、前記ｐセルのすべての属性配列が２つの値のうちの１つを有している）かどうか判定される。適している場合、Ｐ２圧縮がブロック１００８で適用され得る。
【０１８０】
前記ｐセルがＤ１もしくはＰ２圧縮いずれにも適していない場合、ブロック１０１０で、前記ｐセルがＰ４圧縮に適している（すなわち、前記ｐセルのすべての属性配列が４つの値のうちの１つを有している）かどうか判定され得る。適している場合、Ｐ４圧縮がブロック１０１２で適用され得る。そうでない場合、Ｄ６４圧縮がブロック１０１４で適用され得る。
【０１８１】
図１０は、１つの可能性がある属性平面の決定木を示す。他のそのような決定木も可能である。
１０．インターリーブ符号化
【０１８２】
セルベース圧縮の符号化出力はインターリーブされる可能性がある。場合によっては、インターリーブされた符号化は非インターリーブ符号化よりすぐれている場合がある。
【０１８３】
当該インターリーブは、（１）ｐセルの配列およびｑセル全体の平面、（２）ダウンサンプリングがプレーナ決定かもしくは複合決定か、（３）圧縮性能を考慮する場合がある。最後の考慮に対して、別個のＤＣＴ圧縮プロセッサーおよびパターン（非ＤＣＴ）圧縮プロセッサーが用いられる場合がある。前記ＤＣＴ圧縮プロセッサーは、前記パターンプロセッサーと並行して実行し、また前記ＤＣＴ圧縮プロセッサーはずっと実行が遅い―おそらく前記パターンプロセッサーの８分の１の速さ―と想定される。従って、インターリーブの形式は、ＤＣＴとパターンｐセルのさまざまな組合せにおいて、前記ＤＣＴプロセッサーの高い使用率を維持することをサポートし得る。
【０１８４】
これらの考慮に基づき、前記属性平面および色平面の前記ｑセルおよびｐセルは、インターリーブ方式で出力媒体（例えば、ブロック６０６の記憶装置および／またはブロック６１６の記憶装置）に書き込まれ得る。例として、色モデルがＹＣｂＣｒＡである場合、符号化セルの配列は、属性セル、次に輝度（Ｙ）セル、次にＣｂセル、次にＣｒセル、次に別の属性セル、次に別の輝度（Ｙ）セル、次に別のＣｂセル、次に別のＣｒセル等になるであろう。
【０１８５】
このようなインターリーブ操作の例は図１１Ａおよび１１Ｂに示されている。図１１Ａは、属性平面、Ｙ平面、Ｃｂ平面、およびＣｒ平面のそれぞれに対する一連の４つのｑセルを示す。ｑセル内の各ｐセルは、各ｐセルＩＤ（例えば、ａ、ｂ、ｃ、もしくはｄ）に関連付けられていて、ボックスとして示されている。前記ボックスは、各ｐセルを圧縮するために使用された圧縮技法、並びにｑセルの番号およびｐセルＩＤを含む。例えば、前記属性平面の第１（左端）のｐセルは、Ｐ２圧縮を用いて圧縮され、前記ｐセル１ａからのものである。
【０１８６】
４つのｑセル全体を通して、前記属性平面は一貫してＰ２圧縮を用いて符号化され、Ｙ平面はＤＣＴもしくはＤＣＴＬ圧縮を用いて符号化され、Ｃｂ平面はＤＣＴ（すなわち、ＤＣＴ４：２：０）もしくはＱＤ１圧縮を用いて符号化され、そしてＣｒ平面はＤＣＴ（すなわち、ＤＣＴ４：２：０）、ＱＤ１、もしくはＤＣＴＬ圧縮を用いて符号化されている。
【０１８７】
図１１Ｂは、図１１Ａのｐセルおよびｑセルのインターリーブ符号化を示す。色平面と属性平面のそれぞれは、ランがより効率的な方式で符号化される場合を除いて、一対一対一対一にインターリーブされている。例えば、符号化は、複合モード（ＣＭ）がアクティブであるという表示を伴って、一番目の出力位置において始まる。次に第１のｑセルのｐセルが続く。第１のｑセルはＤＣＴ４：２：０を用いて符号化されているので、第１のｑセルに対しては、複合モードが用いられている
【０１８８】
前記符号化において、第１のｐセルは、前記属性平面の１ａｐセル、次にＹ平面の１ａｐセル、Ｃｂ平面の１ａｐセル、Ｃｒ平面の１ａｐセル、前記属性平面の１ｂｐセル、Ｙ平面の１ｂｐセル、等である。複合モードにおいては、Ｙ、Ｃｂ、およびＣｒ符号化に対してオペコードが除外されることに留意されたい。
【０１８９】
第２のｑセルに対して、１２番目の出力位置において、プレーナモードに入っている、なぜならば、色チャネルがＤＣＴＬおよびＱＤ１圧縮を用いて符号化されているからである。ＣｂおよびＣｒ色チャネルに対するＱＤ１符号化のそれぞれは、暗黙的にＱＤ１ランを始める。符号化されたｐセルのそれぞれに対して、オペコードが存在することに留意されたい。
【０１９０】
第３のｑセルに対して、２０番目の出力位置において、またプレーナモードが表示されている、なぜならば色チャネルが、再びＤＣＴＬおよびＱＤ１圧縮を用いて符号化されているからである。Ｃｂ平面におけるＱＤ１ランが続行するので、ＱＤ１Ｃ符号化が当該平面に対して用いられる。しかしながら、前記ＱＤ１ランはＣｒ平面に対して続行しない。従って、ＱＤ１Ｅ符号化がＱＤ１ランの終了を示すために用いられ、２５番目の出力位置において、Ｃｒ平面のｐセルを表すためにＤＣＴＬ符号化が用いられる。
【０１９１】
第４のｑセルに対して、複合モードが再び用いられる。複合モードインジケータ（２９番目の出力位置のＣＭ符号化）は、暗黙的にＣｂ平面におけるＱＤ１符号化のランを終了する。第４のｑセルの符号化の後、インターリーブ表現の当該部分を終了するために、別の複合モードインジケータおよび次にエンド・オブ・ファイル（ＥＯＦ）が符号化される。
【０１９２】
インターリーブ操作の別の例を図１２Ａおよび１２Ｂに示す。図１２Ａは、前記属性平面、Ｙ平面、Ｃｂ平面、Ｃｒ平面のそれぞれに対する一連の４つのｑセルを示す。しかしながら、図１１Ａおよび１１Ｂの例と異なり、図１２Ａの例は、前記属性平面でのＤ１ランを含む。
【０１９３】
図１２Ｂは、図１２Ａのｐセルおよびｑセルのインターリーブ符号化を示す。前記色平面と前記属性平面のそれぞれは、ランがより効率的な方式で符号化される場合を除いて、一対一対一対一にインターリーブされている。特に、６番目と１０番目の出力位置における２つのＤ１符号化により表されるように、属性平面のＤ１ランは暗黙的に第１のｑセルで始まる。Ｃｂ平面の前記ＱＤ１ランは、図１１Ａおよび１１ＢのＱＤ１ランと同じである。
【０１９４】
第２のｑセルにおいて、前記Ｄ１ランは、１３番目の出力位置における単一のＤ１Ｃ符号化によって表される。しかしながら、前記Ｄ１ランは第３のｑセルで終了する。従って、Ｄ１Ｅ符号化が１８番目の出力位置に現れて、前記Ｄ１ランの終了を示す。そして、第３のｑセルの４つの属性のｐセルが個別に符号化される。
【０１９５】
第４のｑセルは、ｑセル内のＤ１ランを含む。従って、２８番目の出力位置において、これらの４つのｐセルは、４つのラン（Ｄ１Ｒ（４））を示す単一のＤ１符号化で表される。図１１Ｂの例と同じく、圧縮表現の当該部分を終了するために、別の複合モードインジケータおよび次にエンド・オブ・ファイル（ＥＯＦ）が符号化される。しかしながら、プレーナモードから複合モードに切り替わっても当該の例の属性平面のランを暗黙的に終了させない。その結果、当該機能を実行するためにＤ１Ｅ符号化が３６番目の出力位置に現れる。
【０１９６】
図１１Ａ、１１Ｂ、１２Ａ、および１２Ｂは、例示の目的で提供されている。その他の符号化も本明細書の実施形態によって対応することができ、また実施形態の範囲を逸脱することなくこれらの符号化に対する変形例を実施することは可能である。
１１．セルベース解凍の例
【０１９７】
一旦、多くのｐセルおよび／またはｑセルが、例えば、上記の圧縮方法および符号化を用いて圧縮されると、それらは、効率よく格納されおよび／またはケーブルもしくはネットワークを介して送信され得る。しかしながら、どこかの時点で、前記ｐセルおよび／またはｑセルは、元の画像もしくは元の画像の近似画像に解凍される場合がある。本明細書に記載のセルベースの圧縮技法は非可逆の場合もあるので、解凍された画像は、少なくともある程度、元の画像と異なる場合がある。しかしながら、多くのシナリオにおいて、当該差異は人によって知覚されそうにない、もしくは元の画像の許容可能なバージョンであると見なされるかのいずれかであろう。
【０１９８】
上記の圧縮符号化で符号化された前記ｐセルおよび／またはｑセルは、以下のように復号しおよび解凍することができる。特定のｑセル符号化に対して、前記ｑセルが、複合モードもしくはプレーナモードを用いて符号化されたかどうかを判定するために前記ｑオペコードが読み取られる。当該モードに基づき、一つ以上のオペコードが読み取られる。各オペコードの値に基づき、任意の適用可能なオプション、引数、ビットマップ等が、オペコードに続くビットから判定され得る。これらのパラメータから、前記ｐセルもしくは前記ｑセルの解凍バージョンが復元され得る。そして、前記画像が復元されるまで次のオペコードが読み取られる等々である。
ａ．属性平面の解凍
【０１９９】
前記属性平面上で、オペコードが００１で、Ｄ１符号化を示す場合、前記Ｖ’ビットおよび前記引数フィールドが読み取られて、圧縮されたエレメントの値が判定され得る。前記レングスビットもまた読み取られて、ランレングスが存在するかどうか判定され得る。そして、各セルのすべての画素が、符号化における値フィールド、もしくは値フィールドのキャッシュされたバージョンにおける値フィールドによって示される値を示し、前記ランレングスと等しい多くのセルが生成される。
【０２００】
前記オペコードが０００で、Ｄ１Ｄ符号化を示す場合、前記Ｖビットが読み取られて、圧縮されたエレメントの値が判定され、そして前記レングスビットが読み取られて、ランレングスが存在するかどうか判定され得る。そして、各セルのすべての画素が、前記Ｖビットにより示されるデフォルトの値を示して、前記ランレングスと等しい多くのセルが生成される。
【０２０１】
前記オペコードが０１１で、Ｐ２符号化を示す場合、前記オプション、前記引数、および前記ビットマップが読み取られ得る。前記Ｖ’ビットが１の場合、前記セルの前記２つの値が判定され得る。そして、各画素が、前記ラインマップおよびビットマップに従って前記２つの値のうち１つを取って、セルが生成され得る。前記ラインマップが存在しない場合、以前のＰ２セルからのラインマップおよびビットマップが使用される。
【０２０２】
前記オペコードが０１０で、Ｐ２Ｄ圧縮を示す場合、各画素が、前記ラインマップおよび前記ビットマップに従って前記２つの値のうち１つを取って、セルが生成され得る。前記ラインマップが存在しない場合、以前のＰ２セルからのラインマップおよびビットマップが使用される。
【０２０３】
前記オペコードが１００で、Ｐ４圧縮を示す場合、前記ラインマップと前記値引数、並びに前記ビットマップが読み取られ得る。そして、各画素が、前記ラインマップおよび前記ビットマップに従って前記４つの色値のうち１つを取って、セルが生成され得る。
【０２０４】
前記オペコードが１で、Ｄ１Ｃ圧縮を示す場合、最新のＤ１もしくはＤ１Ｄセルがコピーされる。前記オペコードが０で、Ｄ１Ｅ圧縮を示す場合、現在のＤ１もしくはＤ１Ｄランが終了してしまったと見なされる。
【０２０５】
前記オペコードが１１で、Ｄ６４圧縮を示す場合、属性当りのビット数が判定され、それに応じて、前記属性フィールドが復号される。属性当りのビット数は、印刷デバイスの種類、および前記解凍が前記パイプラインのどこで行われているかによる場合がある。
ｂ．色平面およびグレースケール平面の解凍
【０２０６】
色平面の解凍は、複合モードかあるいはプレーナモードが用いられているかによって変わる。プレーナモードが用いられている場合、前記解凍は、また、ノーマルモードあるいはランモードがアクティブであるかによって変わる。グレースケール平面の解凍は、プレーナモードを用いるのみである。
【０２０７】
複合モードが用いられる場合、前記画像がカラーかグレースケールかによって、１のｑオペコードに続き、ＤＣＴ４：２：０もしくはＤＣＴ  Ｙ符号化のいずれかが行われる。プレーナモードが用いられる場合、０のｑオペコードに、次に現れる符号化の種類を示すオペコードが続く。
【０２０８】
例えば、ノーマルモードにおいて、オペコード０１はＱＤ１符号化を示し、オペコード００はＱＤ１Ｄ符号化を示し、およびオペコード１はＤＣＴＬ符号化を示す。ランモードにおいては、オペコード１はＱＤ１Ｃ符号化を示し、オペコード０はＱＤ１Ｅ符号化を示す。
【０２０９】
インテリジェントダウンサンプリングを用いるＤＣＴ４：２：０を用いて圧縮されたｐセルを解凍するには、関連付けられた属性配列のエッジビットを用いる場合がある。前記エッジビットは、元の（ダウンサンプリングされていない）エッジビットを表わすので、元の画像のエッジの場所がわかる。さらに、ＤＣＴ４：２：０圧縮により、前記画素について対応するＹ平面の値（画素の輝度）もまたわかる。
【０２１０】
解凍する場合、ダウンサンプリングされたｐセルは、ｑセルにアップサンプリングされる。従って、例えば、前記ｐセルの各画素は、前記ｑセルの中に２ｘ２画素ブロックにアップサンプリングされる。前記ダウンサンプリングされた画素の値をｆとする。次に、当該画素がエッジを表す場合、前記２ｘ２ブロックの各画素ｃ（ｘ、ｙ）、ｃ（ｘ＋１、ｙ）、ｃ（ｘ、ｙ＋１）、およびｃ（ｘ＋１、ｙ＋１）はｆに設定される。エッジでない各画素のＹ平面の値は閾値と比較される。前記Ｙ平面の値が前記閾値を超えると、前記エッジでない画素は１２８（中間色）に設定され、そうでない場合、前記エッジでない画素はｆに設定される。エッジが無い場合、４つの画素すべてはｆに設定される。前記閾値は任意の値でよく、例えば、２２０もしくはそれより大きな値でもよい。
【０２１１】
実施の形態によっては、代わりに１２８以外の中間色の値を使用することができる。一般に、この技法は、アップサンプリングしている間エッジを保持する、なぜならば、前記スキャナ部は、エッジを規定する２つの画素のうちの１つが白色か白色に近い場合、画素に対して単にエッジビットを設定するように構成される場合があるからである。
１２．パフォーマンス結果の例
【０２１２】
本明細書に記載のセルベースの圧縮技法は、ＪＰＥＧ圧縮の２つのバリエーション―ＪＰＥＧＱ９０およびＪＰＥＧＱ９５―と比較された。ＪＰＥＧＱ９０およびＪＰＥＧＱ９５は、ＤＣＴ係数に対してＪＰＥＧで用いられる共通の量子化テーブルを参照する。ＪＰＥＧＱ９０は高い品質をもたらす、そしてＪＰＥＧＱ９５はさらに高い品質をもたらす。２６ページの代表的かつ難易度が高いページが、本明細書に記載のセルベースの圧縮技法、並びにＪＰＥＧＱ９０およびＪＰＥＧＱ９５により圧縮された。Ｆｌａｔ７量子化テーブルが、ＤＣＴ係数に対してセルベースの圧縮技法において使用された。
【０２１３】
これらの比較についての結果は以下のとおりである。セルベースの圧縮技法は、２６ページすべてに対してＪＰＥＧＱ９５より良い圧縮率をもたらした。平均して、ＪＰＥＧＱ９５はセルベースの圧縮技法より約８５％悪い圧縮率をもたらした。また、セルベースの圧縮技法は、５ページを除くすべてのページに対してＪＰＥＧＱ９０より良い圧縮率をもたらした。当該５ページについて、ＪＰＥＧＱ９０は、セルベースの圧縮技法と比較して最大で８％の改善をもたらした。しかし、平均すると、ＪＰＥＧＱ９０は、セルベースの圧縮技法より約１９％悪い圧縮率をもたらした。
【０２１４】
意義深いことに、セルベースの圧縮技法は、２つのＪＰＥＧセッティングより、主観的により良い画像品質をもたらした。
１３．動作の例
【０２１５】
図１３、１４、および１５は、例示の実施形態のフローチャートを示す。これらのフローチャートにより示されるステップは、印刷デバイス１００等の１台以上の印刷デバイス、および／またはコンピューティング・デバイス３００等のコンピューティング・デバイスにより実行され得る。さらに、各個別のステップの態様は、複数のコンピューティング・デバイスもしくは印刷デバイス間で利用に供することができる。
【０２１６】
本明細書で使用される用語に関して、ｍｘｎ属性セルは、属性平面のプレーナｐセルを指し、ｍｘｎ画素セルは、色平面のプレーナｐセルを指し得る。さらに、ａｘｂ属性セルは、属性平面のプレーナｑセルを指し、ａｘｂ画素セルは、色平面のプレーナｑセルを指し得る。全体を通して、ａはｍより大きく、またｂはｎより大きい。
【０２１７】
図１３は、入力画像の色平面のセルベースの圧縮についてのステップを全般的に示す。しかしながら、これらのステップはその他の目的に対しても使用される場合がある。図５乃至１２Ｂに関連して説明された動作は、明示的または暗黙的に当該フローチャートにおいて参照される場合がある。例えば、図１３のステップは、印刷デバイスのパイプラインの他の場所においてあるいはホストコンピュータによって、図６のブロック６０４で行われるであろう。
【０２１８】
ステップ１３００で、入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルが取得され得る。前記ａｘｂ画素マクロセルは、それぞれ４つの非オーバーラップｍｘｎ画素セルを含み、前記ａｘｂ画素マクロセルの画素は、それぞれの画素値を有し得る。
【０２１９】
ステップ１３０２で、少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表すかどうか判定され得る。ｅの値は少なくとも１であるとしてもよい。
【０２２０】
ステップ１３０４で、おそらく、少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表しているかどうかに基づき、前記ａｘｂ画素マクロセルの第１の符号化もしくは第２の符号化のいずれかが選択され得る。前記第１の符号化は、前記入力画像のエッジを表す一部の画素を前記入力画像のエッジを表さない画素より重み付けし、前記第２の符号化は、画素が前記入力画像のエッジを表すかどうかを考慮しない場合がある。
【０２２１】
ステップ１３０６で、前記選択された符号化が実行され得る。ステップ１３０８で、前記選択された符号化の表現が、実行されたとおり、コンピュータ読み取り可能な出力媒体に書き込まれ得るであろう。
【０２２２】
前記第１および第２符号化は圧縮符号化であり得る。従って、今後のステップは、前記ａｘｂ画素マクロセルについての前記選択された符号化の表現を解凍すること、および、解凍されたａｘｂ画素マクロセルを含めて、前記入力画像を印刷することに関係するであろう。
【０２２３】
前記第１の符号化が選択された符号化である場合がある。そのような実施の形態では、前記選択された符号化を実行する場合、第１の色平面と第２の色平面の前記ａｘｂ画素マクロセルの画素のブロックをダウンサンプリングし、第１の色平面に対する第１のダウンサンプリングされたｍｘｎ画素セルと第２の色平面に対する第２のダウンサンプリングされたｍｘｎ画素セルを形成し得る。前記ダウンサンプリングは、前記入力画像のエッジを表す画素を前記入力画像のエッジを表さない画素より重み付けし（例えば、インテリジェントダウンサンプリングを使用して）。前記選択された符号化を実行する場合、さらに、前記輝度平面の前記４つの非オーバーラップｍｘｎ画素セル、前記第１のダウンサンプリングされたｍｘｎ画素セル、および前記第２のダウンサンプリングされたｍｘｎ画素セルの変換を符号化し得る。前記変換は、ＤＣＴ４：２：０等の離散コサイン変換に基づいてもよい。
【０２２４】
一方、前記第２の符号化が選択された符号化となる場合がある。そのような実施の形態では、前記選択された符号化を実行する場合、（１）任意の前記ａｘｂ画素マクロセルの前記４つの非オーバーラップｍｘｎ画素セルの少なくとも１つにおける画素値の範囲が閾値より大きいことを判定し、（２）前記第１の色平面および前記第２の色平面の前記ａｘｂ画素マクロセルの画素のブロックをダウンサンプリングし、前記第１の色平面に対する第１のダウンサンプリングされたｍｘｎ画素セルと前記第２の色平面に対する第２のダウンサンプリングされたｍｘｎ画素セルを形成し、（３）前記輝度平面の前記４つの非オーバーラップｍｘｎ画素セル、前記第１のダウンサンプリングされたｍｘｎ画素セル、および前記第２のダウンサンプリングされたｍｘｎ画素セルの変換を符号化し得る。前記ダウンサンプリングは、画素が前記入力画像のエッジを表すかどうかを考慮しない場合がある。前記変換は、ＤＣＴ４：２：０等の離散コサイン変換に基づいてもよい。
【０２２５】
さらにべつの代替案では、前記第２の符号化が前記選択された符号化となる場合があり、前記選択された符号化を実行する場合、（１）前記ａｘｂ画素マクロセルのそれぞれに対する前記４つの非オーバーラップｍｘｎ画素セルのそれぞれにおける画素値の範囲が閾値以下であることを判定し、（２）特定の１つの前記ａｘｂ画素マクロセルに対する前記４つの非オーバーラップｍｘｎ画素セルのそれぞれに対するそれぞれの平均画素値を判定し、（３）（ａ）少なくとも１つの画素値の範囲がセルレベル閾値より大きいか、もしくは（ｂ）前記それぞれの平均画素値の範囲がマクロセルレベル閾値以上であるかのいずれかを判定し、（４）特定の１つの前記ａｘｂ画素マクロセルにおける画素のブロックをダウンサンプリングしてダウンサンプリングされたｍｘｎ画素セルにし、そして（５）前記ダウンサンプリングされたｍｘｎ画素セルの変換を（例えば、ＤＣＴＬ圧縮を用いて）符号化し得る。前記ダウンサンプリングは、特定の１つの前記ａｘｂ画素マクロセルの画素が入力画像のエッジを表すかどうかを考慮しない場合がある。前記閾値は、前記セルレベル閾値および前記マクロセルレベル閾値の両方より大きい場合がある。
【０２２６】
さらにべつの代替案では、前記第２の符号化が前記選択された符号化となる場合があり、前記選択された符号化を実行する場合、（１）特定の１つの前記ａｘｂ画素マクロセルに対する前記４つの非オーバーラップｍｘｎ画素セルのそれぞれに対するそれぞれの平均画素値を判定し、（２）前記特定の１つのａｘｂ画素マクロセルに対する前記４つの非オーバーラップｍｘｎ画素セルのそれぞれにおける画素値の範囲がすべて、セルレベル閾値以下であることを判定し、（３）前記それぞれの平均画素値の範囲がマクロセルレベル閾値より小さいことを判定し、（４）前記特定の１つの前記ａｘｂ画素マクロセルを単一の画素値を用いて（例えば、ＱＤ１圧縮を用いて）符号化し得る。
【０２２７】
図１４は、色平面のセルベースの圧縮についてのステップを全般的に示す。しかしながら、これらのステップはその他の目的にも使用される場合がある。図５乃至１２Ｂに関連して説明された動作は、明示的または暗黙的に当該フローチャートにおいて参照される場合がある。例えば、図１４のステップは、印刷デバイスのパイプラインの他の場所においてあるいはホストコンピュータによって、図６のブロック６０４で行われるであろう。
【０２２８】
ステップ１４００で、入力画像のａｘｂ画素マクロセルが取得され得る。前記ａｘｂ画素マクロセルの画素はそれぞれの画素値を有し、そしてそれぞれのタグに関連付けられ得る。これらタグは、それぞれ関連付けられた属性配列のエッジビットである場合がある。
【０２２９】
ステップ１４０２で、少なくとも前記それぞれのタグのｅが、タグが関連付けられている画素が前記入力画像のエッジを表すことを示すかどうか判定され得る。ｅの値は少なくとも１であるとしてもよい。
【０２３０】
ステップ１４０４で、おそらく、少なくとも前記それぞれのタグのｅが、タグが関連付けられている画素が前記入力画像のエッジを表すことを示すかどうかに基づき、前記ａｘｂ画素マクロセルの第１の符号化もしくは第２の符号化のいずれかが選択され得る。前記第１の符号化は、前記入力画像のエッジを表す画素を前記入力画像のエッジを表さない画素より重み付けする。前記第２の符号化は、画素が前記入力画像のエッジを表すかどうかを考慮しない場合がある。
【０２３１】
ステップ１４０６で、前記選択された符号化が実行され得る。ステップ１４０８で、前記選択された符号化の表現が、実行されたとおり、コンピュータ読み取り可能な出力媒体に書き込まれ得る。
【０２３２】
実施の形態によっては、前記第１の符号化が選択された符号化である場合があり、前記選択された符号化を実行する場合、（１）前記タグに基づき、前記ａｘｂ画素マクロセルの第１の２ｘ２画素ブロックが前記入力画像のエッジを表すｇ画素を含むことを判定し、（２）そしてダウンサンプリングされたｍｘｎ画素セルの第１の画素を前記ｇ画素の平均値で符号化し得る（例えば、インテリジェントダウンサンプリングを用いるＤＣＴ４：２：０圧縮）。ｇの値は１、２、もしくは３であってもよい。これらの実施の形態において、前記選択された符号化を実行する場合、さらに、（１）前記タグに基づき、前記ａｘｂ画素マクロセルの第２の２ｘ２画素ブロックが前記入力画像のエッジを表す画素を含まないことを判定し、（２）そして前記ダウンサンプリングされたｍｘｎ画素セルの第２の画素を、前記第２の２ｘ２画素ブロックのすべての画素の平均値で符号化し得る。前記すべての画素の平均値は、画素がエッジを表すかどうかを考慮しない場合がある。
【０２３３】
別の実施の形態において、前記ａｘｂ画素マクロセルは、４つの非オーバーラップｍｘｎ画素セルを含む場合がある。前記第２の符号化が選択された符号化である場合があり、前記選択された符号化を実行する場合、（１）少なくとも１つの前記４つの非オーバーラップｍｘｎ画素セルにおける画素値の範囲が所定の非ゼロ閾値を超えることを判定し、そして（２）ダウンサンプリングされたｍｘｎ画素セルの特定の画素を、前記ａｘｂ画素マクロセルの特定の２ｘ２画素ブロックの全ての画素の平均値で符号化し得る（例えば、インテリジェントダウンサンプリングを用いないＤＣＴ４：２：０圧縮）。前記すべての画素の平均値は、画素がエッジを表すかどうかを考慮しない場合がある。
【０２３４】
さらなる実施の形態において、前記ａｘｂ画素マクロセルは、また、４つの非オーバーラップｍｘｎ画素セルを含む場合がある。前記第２の符号化が選択された符号化である場合があり、前記選択された符号化を実行する場合、（１）前記４つの非オーバーラップｍｘｎ画素セルのそれぞれにおける画素値の範囲が閾値以下であることを判定し、（２）前記４つの非オーバーラップｍｘｎ画素セルのそれぞれに対するそれぞれの平均画素値を判定し、（３）（ａ）少なくとも１つの前記画素値の範囲がセルレベル閾値より大きいか、もしくは（ｂ）前記それぞれの平均画素値の範囲がマクロセルレベル閾値以上であるかのいずれかを判定し、（４）前記ａｘｂ画素マクロセルの画素のブロックをダウンサンプリングしてダウンサンプリングされたｍｘｎ画素セルとし、そして（５）前記ダウンサンプリングされたｍｘｎ画素セルの変換を符号化し得る（例えば、ＤＣＴＬ圧縮を使用して）。前記閾値は、前記セルレベル閾値およびマクロセルレベル閾値の両方より大きい場合がある。前記ダウンサンプリングは、前記ａｘｂ画素マクロセルの画素が前記入力画像のエッジを表すかどうかを考慮しない場合がある。
【０２３５】
さらなる実施の形態において、前記ａｘｂ画素マクロセルは、また、４つの非オーバーラップｍｘｎ画素セルを含む場合がある。前記第２の符号化が選択された符号化である場合があり、そして前記選択された符号化を実行する場合、（１）前記４つの非オーバーラップｍｘｎ画素セルのそれぞれに対するそれぞれの平均画素値を判定し、（２）前記４つの非オーバーラップｍｘｎ画素セルのそれぞれの画素値の範囲がすべてセルレベル閾値以下であることを判定し、（３）それぞれの平均画素値の範囲がマクロセルレベル閾値より小さいことを判定し、そして（４）前記ａｘｂ画素マクロセルを単一の画素値で符号化し得る（例えば、ＱＤ１圧縮を使用して）。
【０２３６】
図１５は、属性平面および一つ以上の色平面のセルのインターリーブ圧縮表現についてのステップを全般的に示す。しかしながら、これらのステップはその他の目的にも使用される場合がある。図５乃至１２Ｂに関連して説明された動作は、明示的または暗黙的に当該フローチャートにおいて参照される場合がある。例えば、図１５のステップは、印刷デバイスのパイプラインの他の場所においてあるいはホストコンピュータによって、図６のブロック６０４で行われるであろう。
【０２３７】
ステップ１５００で、（１）ａｘｂ属性マクロセル、および（２）入力画像の輝度平面、第１の色平面、および第２の色平面のそれぞれに対するａｘｂ画素マクロセルを取得し得る。前記ａｘｂ画素マクロセルは、それぞれ、４つの非オーバーラップｍｘｎ画素セルを含み得る。前記ａｘｂ画素マクロセルのａｘｂ画素は、それぞれの画素値を有し得る、そして前記ａｘｂ属性マクロセルの要素は、一対一方式で、前記ａｘｂ画素マクロセルのそれぞれにおけるそれぞれの画素に関連付けられ得る。
【０２３８】
ステップ１５０２で、それぞれ４つの非オーバーラップｍｘｎ属性セルを表す４つの属性平面出力値が判定され得る。ステップ１５０４で、少なくとも前記ａｘｂ画素マクロセルのｅ画素が入力画像のエッジを表すことを、前記ａｘｂ属性マクロセルが示すかどうかに、おそらく少なくとも部分的に基づいて、前記輝度平面の前記ａｘｂ画素マクロセルを表す１乃至４つの輝度平面出力値が判定され得る。ｅの値は少なくとも１であるとしてもよい。
【０２３９】
ステップ１５０６で、前記第１の色平面の前記ａｘｂ画素マクロセルを表わすための第１の色平面出力値および前記第２の色平面の前記ａｘｂ画素マクロセルを表わすための第２の色平面出力値が判定され得る。ステップ１５０８で、前記４つの属性平面出力値、前記１乃至４つの輝度平面出力値、前記第１の色平面出力値および前記第２の色平面出力値のインターリーブ表現が、コンピュータ読み取り可能な出力媒体に書き込まれ得る。前記第１の色平面出力値はａｘｂバイト未満で表され、そして前記第２の色平面出力値もａｘｂバイト未満で表され得る。
【０２４０】
実施の形態によっては、前記１乃至４つの輝度平面出力値を判定する場合、（１）少なくとも前記ａｘｂ画素マクロセルのｅ画素が前記入力画像のエッジを表すことを、前記ａｘｂ属性マクロセルが示すことを判定し、そして（２）前記輝度平面の前記ａｘｂ画素マクロセルの前記非オーバーラップｍｘｎ画素セルのそれぞれを別々に表す４つの輝度平面出力値を判定し得る。前記第１の色平面出力値および前記第２の色平面出力値は、それぞれ、前記第１の色平面および前記第２の色平面の前記ａｘｂ画素マクロセルのダウンサンプリングバージョンであり得る、そして前記入力画像のエッジを表す画素を前記入力画像のエッジを表さない画素よりも重み付けする。
【０２４１】
一方、前記１乃至４つの輝度平面出力値を判定する場合、（１）（ａ）前記ａｘｂ画素マクロセルのｅ画素より少ない画素が前記入力画像のエッジを表すことを前記ａｘｂ属性マクロセルが示すこと、および（ｂ）前記ａｘｂ画素マクロセルの前記４つの非オーバーラップｍｘｎ画素セルのうちの少なくとも１つの画素値の範囲が閾値より大きいことを判定し、そして（２）前記輝度平面の前記ａｘｂ画素マクロセルの前記非オーバーラップｍｘｎ画素セルのそれぞれを別々に表す４つの輝度平面出力値を判定し得る。前記第１の色平面出力値および前記第２の色平面出力値は、それぞれ、前記第１の色平面および前記第２の色平面の前記ａｘｂ画素マクロセルのダウンサンプリングバージョンであり得る、そしてここで、前記ダウンサンプリングは、画素が前記入力画像のエッジを表すかどうかを考慮しない。
【０２４２】
他の実施の形態において、前記１乃至４つの輝度平面出力値を判定する場合、（１）（ａ）前記ａｘｂ画素マクロセルのｅ画素より少ない画素が前記入力画像のエッジを表すことを前記ａｘｂ属性マクロセルが示すこと、および（ｂ）前記ａｘｂ画素マクロセルのそれぞれに対する前記４つの非オーバーラップｍｘｎ画素セルのそれぞれの画素値の範囲が閾値以下であることを判定し、そして（２）前記輝度平面の前記ａｘｂ画素マクロセルを表す１つの輝度平面出力値を判定し得る。
【０２４３】
それに代わってもしくはさらに、４つの輝度平面出力値が判定された場合、前記インターリーブ表現は複合モードインジケータによって始まり、前記インターリーブ表現の前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のそれぞれに対してオペコードは除外され得る。その一方で、１つの輝度平面出力値が判定された場合、前記インターリーブ表現がプレーナモードインジケータによって始まり、そしてオペコードが、前記インターリーブ表現の前記１乃至４つの輝度平面出力値、前記第１の色平面出力値、および前記第２の色平面出力値のそれぞれに対して含まれ得る。
【０２４４】
場合によっては、前記第１の色平面出力値は、前記第１の色平面に対する同一の出力値のランの続行もしくは終了を示す場合がある。同様に、前記第２の色平面出力値は、前記第２の色平面に対する同一の出力値のランの続行もしくは終了を示す場合がある。
１４．結論
【０２４５】
本出願において記述されている具体的な実施形態に関して、本開示は限定されるべきではなく、それらはいろいろな態様の実例として意図されている。
当業者にとって明白であるように、本開示の主旨と範囲から逸脱することなく多くの変更および変形をすることが可能である。本記載に列挙されていることに加え、本開示の範囲内の機能的に等価な方法および装置は前述の記載から明白であろう。そのような変更および変形は、添付された請求項の範囲内に入るように意図されている。
【０２４６】
図面における、任意のすなわち全てのラダー図、シナリオ、およびフローチャートに関しておよび本記載で述べられたように、各ブロックおよび／または通信は、例示の実施形態に従って情報を処理しおよび／または情報を送信することを表し得る。他の実施形態もそのような例示の実施形態の範囲に含まれ得る。さらに、より多くのもしくはより少ないブロックおよび／または機能が、本記載に記述されているどのラダー図、シナリオ、およびフローチャートと共に使用されてもよいし、また当該ラダー図、シナリオ、およびフローチャートは、部分的にもしくは全体的にお互いに結合されてもよい。
【０２４７】
情報の処理を表すステップもしくはブロックは、本記載の方法もしくは技法の具体的な論理機能を実行するように構成することが可能な回路に相当し得る。それに代えてまたはさらに、情報の処理を表すステップもしくはブロックは、モジュール、セグメント、もしくはプログラムコードの一部分（関連するデータを含めて）に相当し得る。前記プログラムコードは、前記方法もしくは技法における具体的な論理機能もしくは動作を実行するための、処理部により実行可能な一つ以上の指示を含み得る。前記プログラムコードおよび／または関連するデータは、ディスクドライブ、ハードドライブ、もしくはその他の記憶媒体を含む記憶装置等の任意の種類のコンピュータ読み取り可能な媒体に格納することが可能である。
【０２４８】
コンピュータ読み取り可能な媒体は、また、レジスタメモリ、プロセッサーキャッシュ、および／またはランダムアクセスメモリ（ＲＡＭ）のような短期間データを格納するコンピュータ読み取り可能な媒体等の、非一時的でコンピュータ読み取り可能な媒体を含み得る。コンピュータ読み取り可能な媒体は、また、例えば、リードオンリーメモリー（ＲＯＭ）、光学もしくは磁気ディスク、および／またはコンパクトディスク・リードオンリーメモリー（ＣＤ―ＲＯＭ）のような、二次的もしくは持続的長期記憶装置等、より長期間プログラムコードおよび／またはデータを格納する非一時的でコンピュータ読み取り可能な媒体を含み得る。コンピュータ読み取り可能な媒体は、また、他の揮発性もしくは不揮発性記憶システムでもあり得る。コンピュータ読み取り可能な媒体は、また、例えば、コンピュータ読み取り可能な記憶媒体および／または有形の記憶デバイスと考えることができる。
【０２４９】
さらに、本明細書における要素、ブロックもしくはステップのあらゆる列挙、図面、あるいは請求項は明確にする目的のためである。したがって、このように列挙されていても、これらの要素、ブロック、もしくはステップが特定の配置に固執したり、あるいは特定の順序で実行されることを必要とするあるいは意味するものと解釈されるべきではない。
【０２５０】
本記載においてさまざまな態様および実施形態が開示されてきたが、他の態様および実施形態も当業者にとって明白であろう。本記載において開示されたさまざまな態様および実施形態は、例示目的であって限定することを意図するものではなく、真の範囲と主旨は以下の請求項により示されている。
【符号の説明】
【０２５１】
１００  印刷デバイス
２００  コンピューティング・デバイス構成要素
２０２  処理部
２０４  メモリ
２０６  入出力部
２０８  システムバス
３００  コンピューティング・デバイス
３０２  スキャナ部
３０４  印刷部
３０６  スキャン〜ホストデータパス
３０８  ホスト〜印刷データパス
３１０  スキャン〜印刷データパス
【図１】
2016144210.tif 000015
【図２】
2016144210.tif 000016
【図３】
2016144210.tif 000017
【図４】
2016144210.tif 000018
【図５】
2016144210.tif 000019
【図６】
2016144210.tif 000020
【図７】
2016144210.tif 000021
【図８】
2016144210.tif 000022
【図９】
2016144210.tif 000023
【図１０】
2016144210.tif 000024
【図１１Ａ】
2016144210.tif 000025
【図１１Ｂ】
2016144210.tif 000026
【図１２Ａ】
2016144210.tif 000027
【図１２Ｂ】
2016144210.tif 000028
【図１３】
2016144210.tif 000029
【図１４】
2016144210.tif 000030
【図１５】
2016144210.tif 000031
【外国語明細書】
PRINTING DEVICE, COMPUTER PROGRAM, AND METHOD
FIELD
[0001]       The present invention relates to a compression technique for 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 operations, are also widely available.  As these devices have grown more prevalent, they are being used for processing of more sophisticated and complicated documents.  
Summary
[0003]          A first example embodiment may involve obtaining a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image. The a x b pixel macro-cells may each contain 4 non-overlapping m x n pixel cells, and pixels in the a x b pixel macro-cells may have respective pixel values.  The first example embodiment may also involve determining whether at least e pixels in the a x b pixel macro-cells represent edges in the input image, where e is at least 1.  The first example embodiment may further involve, possibly based on whether at least e pixels in the a x b pixel macro-cells represent edges in the input image, selecting either a first encoding or a second encoding of the a x b pixel macro-cells.  The first encoding may weigh some pixels that represent edges in the input image heavier than pixels that do not represent edges in the input image, and the second encoding might not consider whether pixels represent edges in the input image.  The first example embodiment may additionally involve performing the selected encoding, and writing a representation of the selected encoding, as performed, to a computer-readable output medium.
[0004]          A second example embodiment may involve obtaining an a x b pixel macro-cell from an input image.  Pixels in the a x b pixel macro-cell may have respective pixel values and may be associated with respective tags.  The second example embodiment may also involve determining whether at least e of the respective tags indicate that their associated pixels represent edges in the input image, where e is at least 1.  The second example embodiment may further involve, possibly based on whether at least e of the respective tags indicate that their associated pixels represent edges in the input image, selecting either a first encoding or a second encoding of the a x b pixel macro-cell.  The first encoding may weigh pixels that represent edges in the input image heavier than pixels that do not represent edges in the input image, and the second encoding might not consider whether pixels represent edges.  The second example embodiment may additionally involve performing the selected encoding, and writing a representation of the selected encoding, as performed, to a computer-readable output medium.
[0005]          A third example embodiment may involve obtaining (i) an a x b attribute macro-cell, and (ii) a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image.  The a x b pixel macro-cells may each contain 4 non-overlapping m x n pixel cells, and the a x b pixels in the a x b pixel macro-cells may have respective pixel values.  Elements of the a x b attribute macro-cell may be associated in a one-to-one fashion with respective pixels in each of the a x b pixel macro-cells.  The third example embodiment may also involve determining 4 attribute-plane output values that respectively represent the 4 non-overlapping m x n attribute cells.  The third example embodiment may further involve, possibly based on whether the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image, determining 1 to 4 luminance-plane output values that represent the a x b pixel macro-cell of the luminance plane, where e is at least 1.  The third example embodiment may additionally involve determining a first color-plane output value to represent the a x b pixel macro-cell of the first color plane and a second color-plane output value to represent the a x b pixel macro-cell of the second color plane.  The third example embodiment may also involve writing an interleaved representation of the 4 attribute-plane output values, the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value to a computer-readable output medium. 
[0006]          A fourth example embodiment may include a non-transitory, computer-readable storage medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations in accordance with the first, second, and/or third example embodiments.
[0007]          A fifth example embodiment may include a computing device containing at least a processor and data storage. The data storage may include program instructions that, when executed by the processor, cause the computing device to perform operations in accordance with the first, second, and/or third example embodiments.
[0008]          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.
Brief Description of the Drawings
[0009]          Figure 1 depicts a printing device, according to example embodiments.
Figure 2 is a block diagram illustrating computing components of a printing device, according to example embodiments.
Figure 3 is a block diagram illustrating various data paths involving a printing device, according to example embodiments.
Figure 4 depicts an image that may be contained in an electronic document, according to example embodiments.
Figure 5 depicts an attribute array, according to example embodiments.
Figure 6 depicts a document processing pipeline, according to example embodiments.
Figure 7 depicts a macro-cell containing four cells, according to example embodiments.
Figure 8 depicts a color plane decision tree, according to example embodiments.
Figure 9 depicts a grayscale plane decision tree, according to example embodiments.
Figure 10 depicts an attribute plane decision tree, according to example embodiments.
Figure 11A depicts cells of four planes, according to example embodiments.
Figure 11B depicts the cells of Figure 11A interleaved on an output medium, according to example embodiments.
Figure 12A depicts cells of four planes, according to example embodiments.
Figure 12B depicts the cells of Figure 12A interleaved on an output medium, according to example embodiments.
Figure 13 is a flow chart, according to example embodiments.
Figure 14 is another flow chart, according to example embodiments.
Figure 15 is yet another flow chart, according to example embodiments.
Detailed Description of the Drawings
[0010]          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 scope of the subject matter presented herein.  In the following detailed description, reference is made to the accompanying figures, which form a part thereof.   
[0011]          The example embodiments described herein are not meant to be limiting.  Thus, aspects of the present disclosure, 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
[0012]          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.
[0013]          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.  Additionally, some electronic documents, such as overlay documents containing background images or logos, may be stored in a printing device indefinitely, as these electronic documents may be applied to multiple print jobs.
[0014]          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.  
[0015]          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 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  
[0016]          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.”
[0017]          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. 
[0018]          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.
[0019]          Regardless, printing device 100 may be considered to be a non-generic type of computing device, and may carry out both printing-related and non-printing related tasks.  For instance, printing device 100 may also include copier, fax, and scanner functions.  In some embodiments, printing device 100 may use a scanning unit 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 operation.  Additionally, printing device 100 may be able to receive a faxed electronic document via a telephone interface, and then compress and store a representation of this electronic document.
[0020]          In order to support its various capabilities, 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.
[0021]          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.
[0022]          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.5 x 11 inch paper, A4 paper, letterhead paper, envelopes, and so on.  For any operation 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.
[0023]          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 (Registered Trademark)) 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.
[0024]          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.  
[0025]          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 (Registered Trademark) interface, a card reader port, etc.
[0026]          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.  
[0027]          Computing device components 200 may include a processor 202, memory 204, and input/output unit 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.). 
[0028]          Memory 204, in turn, may comprise volatile and/or non-volatile data storage and can be integrated in whole or in part with processor 202.  Memory 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 operations can be defined by hardware, firmware, and/or any combination of hardware, firmware and software.  Therefore, memory 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.  
[0029]          Memory 204 may also be configured to store compressed and non-compressed electronic documents that may later be processed (e.g., printed).  Thus, memory 204 may serve as an output medium for these electronic documents.
[0030]          Input/output unit 206 may include any of the operations and/or elements described in reference to user interface 106.  Thus, input/output unit 206 may serve to configure and/or control the operation of processor 202.  Input/output unit 206 may also provide output based on the operations performed by processor 202.
[0031]          These examples of a printing device are provided for illustrative purposes.  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.  
[0032]          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 unit 302 and a printing unit 304.  Control of each of these units may be implemented in hardware, firmware, software, or any combination of hardware, firmware and/or software.  Additionally, each of scanning unit 302 and printing unit 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.”
[0033]          A scan-to-print data path 310 may be supported by scanning unit 302 and printing unit 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 unit 302 may scan the physical document into an electronic document, and transmit the electronic document via scan-to-print data path 310 to printing unit 304.  Use of scan-to-print data path 310 may involve at least temporarily storing some or all of the electronic document (possibly in a compressed format) in the data storage of printing device 100.  Then, printing unit 304 may print the electronic document to physical media (e.g., one or more sheets of paper).  
[0034]          A scan-to-host data path 306 may also be supported by scanning unit 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 unit 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 (possibly in a compressed format) 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.  
[0035]          A host-to-print data path 308 may be supported by computing device 300 and printing unit 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 unit 304.  Printing device 100, via printing unit 304, may print the electronic document to physical media.  Some, or all, of the electronic document may be stored (possibly in a compressed format) in the data storage of printing device 100 before and/or during the printing of the electronic document.
[0036]          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.  
[0037]          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.
[0038]          Thus, a compression technique that supports both lossless and lossy compression is desirable.  It is also desirable for both lossless and lossy compression to be able to be applied within the same document.  To that point, an understanding of how images are presented may be useful.  
3.         
Example Image
[0039]          An image may be a matrix of pixels encoded according to an image format and a color model.  Figure 4 depicts an image 400 that may be included on or within a physical or electronic document handled by printing device 100.  While image 400 appears in black and white, color images with similar characteristics may also be handled by printing device 100.  Image 400 may be formed using various resolutions, such as 600 dots per inch (dpi) or 1200 dpi among other examples.
[0040]          As can be seen in Figure 4, image 400 contains various types of content.  For instance, image 400 contains both text and line art with sharp edges.  Further, image 400 also contains sections containing a continuous tone (e.g., the upper-left-hand corner of image 400), as well as sections containing photorealistic data (e.g., the lower-right-hand corner and upper-right-hand corner of image 400).  Text overlays various sections of image 400.  Thus, 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.
[0041]          In some possible embodiments, each of the pixels in an image, such as example image 400, may be categorized as one of three different object types: image graphics, vector graphics, or text.  Image graphics include photorealistic images, such as images from photographs.  The photorealistic data in the lower-right-hand corner and upper-right-hand corner of image 400 may qualify as image graphics.  The non-text lines throughout image 400 may qualify as vector graphics, and the textual characters (e.g., the “E” and the “R” for instance) may qualify as text.
[0042]          The object type of a particular pixel may be determined by or from the scanning unit of the printing device or a page description language (PDL) representation of an electronic document.  A PDL is a language, grammar, or format that describes the appearance of a printed or displayed page at a higher level than the page’s actual pixels.  A pixel representation of a page may be derived from a PDL.  
[0043]          Thus, an electronic document may contain one or more pages that are represented by a PDL document.  Each of these pages may be represented by part or all of a PDL document, and/or by an image.  There are many examples of PDLs, of which the Portable Document Format (PDF) is one.
[0044]          A unified compression technique may be able to accurately represent the sharp edges and lines of image 400, while still using lossy compression in order to reduce the storage requirements of an electronic document containing image 400.  Particularly, it is desirable to preserve the exact characteristics of certain elements, such as text, basic geometric shapes, and line drawings, because even minor distortions to these elements can appear unpleasing to the human eye.  Thus, these elements may be categorized as vector graphics or text, and may be targeted for compression in a lossless fashion.  
[0045]          On the other hand, photorealistic images and complex graphics with gradients can be viewed without such exactness.  Thus, these elements may be categorized as image graphics, and may be targeted for compression in a lossy fashion.  For instance, image graphics may be compressed in a manner such that they appear visually the same or similar to the human eye as their respective uncompressed versions.
[0046]          Further, the object type of a pixel (e.g., image graphics, vector graphics, or text), may influence a color conversion applied to the pixel, as well as the type of halftone screen applied to the pixel.  These issues are discussed in more detail below.
[0047]          In some cases, vector graphics and text objects may appear to have similar characteristics.  Indeed, these two categories can be combined in some embodiments, and processed in the same fashion.  However, certain types of vector graphics, such as lightly-colored lines, appear better when processed differently from text.  For instance, if lightly colored lines are processed in the same fashion as text, some of these lines may become difficult to distinguish.  Consequently, applying a different color conversion and/or a different halftone screen to vector graphics may preserve and/or enhance these lines.  For instance, the halftone screen selected specifically for a vector graphics pixel may result in more toner being applied when this pixel is printed.
4.         
Example Image
Color Models
[0048]          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.
[0049]          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.  
[0050]          A particular pixel of an RGB image may be expressed as a three-plane tuple (R,G,B), each plane of which can vary from zero to a pre-defined maximum value (e.g., 255).  If all of the planes are 0, the result may be black.  If all of the planes are at the maximum value, the result may be the brightest representable white.  (The color planes described herein may also be referred to as color channels.)
[0051]          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.
[0052]          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.
[0053]          A particular pixel of a CMY image may be expressed as a three-plane tuple (C,M,Y), each plane of which can vary from 0 to a pre-defined maximum value.  If all of the planes are at 0, the result may be white.  If all of the planes are at the maximum value, the result may be black.  
[0054]          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.
[0055]          In some embodiments, a four-plane CMYK color model can also be used.  This four-plane model of CMYK may be similar to or the same as the CMY color model, with the exception that a key (black) plane 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-plane tuple (C,M,Y,K), each plane of which can vary from zero to a pre-defined maximum value.  
[0056]          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.  In some embodiments, one or more color tables may be used to convert pixels from the CMY model to the CMYK model, and/or between other pairs of color models.
[0057]          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 plane (K) that encodes the pixel’s intensity.  The values used by the gray plane 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.
[0058]          Another color model is YCbCr.  In some implementations, this color model may be used as an alternative representation of an image.  Particularly, the Y plane may represent the brightness of a pixel, and the Cb and Cr planes may represent the blue-yellow chrominance and red-green chrominance, respectively.  Despite the Y plane representing luminance, it may be referred to as a “color plane” like the Cb and Cr planes.  The YCbCr color model has a well-defined relationship with the RGB and CMY color models and can be converted to and from either of these color models with relative ease.  A grayscale version of the YCbCr color model may be referred to as the Y color model.
[0059]          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 planes.  So, images encoded in a particular color model may be converted to the YCbCr color model before compression in order to improve compression performance.
5.         
Example Attribute
Plane
[0060]          In addition to color planes, an image may be digitally represented using an attribute plane.  While the values of the attribute plane might not appear visibly in the image, the attribute plane may be used to provide guidance to image compression and processing operations.  
[0061]          As an example, each pixel in an image may be associated with an array of bits (e.g., 8 bits or 16 bits) representing attributes.  Some of these attributes may indicate whether a pixel is used as an overlay on top of other materials, part of an edge in the image, or being used as part of a printing or a copying feature.  Other attributes may include a reference to a color conversion table to use when converting the pixel between color models and/or a reference to a halftone screen to use when printing the pixel.  The bits in each pixel’s associated attribute array may be determined by the scanning unit of the printing device or from the PDL of an electronic document.
[0062]          An array of the attribute plane may be used to identify an object type that its associated pixel represents.  These identified object types may include a graphical image, vector graphics, or text, for example.  Object type tags may be one or more bits of such an attribute array.
[0063]          An example attribute array 500 is shown in Figure 5.  Attribute array 500 includes overlay bit 502, unused bit 504, edge bit 506, two color table bits 508, 510, a copy or print bit 512, and two halftone bits 514, 516.  
[0064]          Overlay bit 502 may indicate whether the associated pixel overlays other materials.  For instance, some printing devices may support applying one or more background images or patterns to some print jobs.  These images or patterns may be static, such as a logo or a border, or may be dynamic, such as automatic page numbering (e.g., displaying a phrase such as “Page 1 of 3” at the bottom of each page in a document).  
[0065]          For instance, in the case of automatic page numbering, the printing device may be directed by a user to add page numbers.  The user might select an option on the user interface of the printing device to specify automatic page numbering.  Alternatively, the printer driver of the computer that transmits the electronic document to the printing device may specify automatic page numbering. In other cases, the printing device may detect which pixels are foreground pixels (such as text on a page) versus background pixels (such as the white background of a page), and indicate that the foreground pixels are overlaid.
[0066]          Edge bit 506 may indicate whether the associated pixel is part of an edge in the image.  For instance, edge bit 506 may take on a value of 1 when this is the case, and may take on a value of 0 when this is not the case.  Edge bit 506 may be set by a scanning unit (e.g., scanning unit 302) to mark pixels near the edges of dark colored shapes that are also adjacent to light colored shapes.  For instance, the edge bits may be set to 1 for pixels representing the borders of text characters on a light background.  Edge bit 506 may be used to enhance the edges in images through the use of intelligent downsampling, as described below.
[0067]          Color table bits 508, 510 may indicate a color table that contains a mapping of color plane values between the CMY and CMYK color models, as one possible example.  As noted above, the object type of a pixel (e.g., image graphics, vector graphics, or text) may be determined from the PDL representation of the electronic document from which the pixel is derived, or by the scanning unit.  
[0068]          Based on the object type of the pixel, a different color conversion table may be applied.  For instance, color table bits 508, 510 may take on a value of “00” when the pixel is part of a text object, “01” when the pixel is part of a vector graphics object, and “11” when the pixel is part of an image graphics object.  Based on the values of color table bits 508, 510, one of several color conversion tables may be selected and applied to the pixel.
[0069]          Copy or print bit 512 may indicate whether the associated pixel is being copied (scanned and then printed) or traditionally printed (e.g., from a PDL document locally stored or received from another device).  The value of this bit may be combined with those of halftone bits 514, 516 to select one of up to eight halftone screens (see below for a discussion of halftoning).  In some cases, electronic documents that are scanned and then printed may use certain types of halftone screens, while electronic documents that are traditionally printed may use other types of halftone screens.
[0070]          Halftone bits 514, 516 may indicate whether a halftone screen is to be applied to the image when printed, and which halftone screen is to be applied.  Halftoning is a technique that simulates a gradient through the use of dots that vary in size, shape, or spacing.  Halftoning can decompose images containing multiple shades of various colors into a series of overlaid halftone screens, with each screen containing a single (binary) shade of a particular color.  The overlaid halftone screen creates an appearance that the dots are blended into smooth tones.  
[0071]          Similar to color table bits 508, 510, halftone bits 514, 516 may take on values based on the type of object that the pixel represents.  Thus, halftone bits 514, 516 may take on a value of “00” when the pixel is part of an image graphics object, “01” when the pixel is part of a vector graphics object, and “11” when the pixel is part of a text object.  Based on the values of halftone bits 514, 516 one of several halftone screens may be selected and applied to the pixel.
[0072]          Although based on the same three object types, color table bits 508, 510 may be distinct from halftone bits 514, 516.  One possible reason for keeping these two distinct sets of information is to accommodate object pixel overlap blending in some PDLs.  For example, when text pixels are blended with raster image pixels, color table bits 508, 510 may indicate a raster image, halftone bits 514, 516 may indicate text.  This feature upholds the image quality of overlapping, blended objects.
[0073]          Example attribute array 500 contains 8 bits (1 byte) per pixel.  Thus, using this style of attribute array, the magnitude of the attribute plane grows linearly with the number of pixels in the image.  The extent of attribute arrays associated with pixels in an image may be referred to as the attribute plane for that image.
[0074]          An attribute plane may be referred to as an A plane.  Thus, when an attribute plane is combined with one or more color planes, the combined attribute and color planes may be referred to as KA, CMYA, CMYKA, RGBA, YA, or YCbCrA, depending on color model being used.  Herein, these examples of combined attribute and color planes may be referred to as a “color model” despite the attribute plane not actually representing a color per-se.
6.         
Example Imaging
Pipeline 
[0075]          A high-level overview of an example imaging pipeline is shown in Figure 6.  This imaging pipeline takes the form of a flow chart 600, and includes multiple compression and decompression steps.  Flow chart 600 may represent a series of steps carried out by a printing device in order to receive, store, and print an electronic document.
[0076]          At block 602 of Figure 6, an electronic document may be represented as one or more images formatted according to the YA or YCbCrA color models.  However, these color models are chosen for purposes of illustration, and other color models may be used.  The YA or YCbCrA pixels may be derived from a scanning process of an original paper document or other object.  Alternatively, at block 602, the electronic document may be represented by an image format, such as a bitmap, JPEG, GIF, etc., and converted to the YA or YCbCrA color model, for instance.
[0077]          At block 604, cell-based compression (discussed in detail below) may be applied to the pixels of each plane of the electronic document.  Thus, for YA electronic documents, cell-based compression may be applied to the gray plane and the attribute plane.  For YCbCrA electronic documents, cell-based compression may be applied separately for each of the Y, Cb, Cr, and A planes or in a composite fashion.  Therefore, in some cases, the cell-based compression may compress the corresponding cells of two or more planes in the same logical operation.  The result of block 604 may be a bitstream representing a compressed version of the electronic document.
[0078]          At block 606, this compressed version may be stored in a storage output medium.  In general, this storage may be memory of a printing device that stores compressed representations of one or more pages.  Since the compression techniques described herein may be able to compress these documents to at least one-third or one-fourth of their original bitmapped size, the memory size requirements for this storage may be reduced accordingly.  As a result, printing devices incorporating the embodiments herein may be less expensive to produce.
[0079]          Pages compressed to the storage in block 606 might or might not be printed by the printing device.  In some cases, these pages may be transmitted from the storage of block 606 to portable storage (e.g., USB storage, a secure digital (SD card), etc.) or transmitted to a personal computer host. Pages may be held in the storage of block 606 for days, weeks, and so on, until a user or a program decides to print or do something else with these pages.  
[0080]          At block 608, cell-based decompression may be applied to each plane of the electronic document.  This may result in the re-creation of the YA or YCbCrA representation of the electronic document.  However, if the cell-based compression technique uses lossy compression, the electronic document resulting from the decompression of block 608 may be different from the electronic document that was compressed by the compression of block 604.  Nonetheless, the differences between these versions of the electronic document might be slight, and therefore might not be readily perceived by humans.
[0081]          At block 610, the decompressed version of the electronic document may be further processed.  For instance, various transforms may be applied to the electronic document.  After one or more of these transforms are performed on the electronic document, the electronic document may be compressed again at block 604 and stored in storage at block 606.  Application of block 610 is optional, and not all electronic documents will be subject to this processing.
[0082]          At block 612, the decompressed version of the electronic document may also be further processed.  At block 614, cell-based compression may be applied to each plane of the electronic document.  This compression procedure may be the same as that of block 604, or may be different.  For instance, the compression applied at block 614 may be configured to obtain higher or lower compression ratios than that of block 604.
[0083]          At block 616, this compressed version may be stored in storage.  Like the storage of block 606, this storage may be memory of a printing device that stores compressed representations of one or more pages.  Since these page representations are compressed, the memory requirements and cost of storage is reduced.  
[0084]          At block 618, cell-based decompression may be applied to each plane of the electronic document.  This may result in the re-creation of the representation of the electronic document that was compressed at block 614.  As was the case for block 608, if the cell-based compression technique uses lossy compression, the electronic document resulting from the decompression of block 618 may be different from the versions of the electronic document that were compressed by the compression of block 604 and/or block 614.  
[0085]          At block 620, further processing may be applied to the decompressed version of the electronic document.  After block 620, the electronic document may be ready for printing, or further processing may be applied.
[0086]          The cell-based compression procedures of blocks 604 and 614 may be the same or different.  For instance, these procedures may use different compression algorithms, or may use the same compression algorithm with the same or different settings.  Likewise, the cell-based decompression procedures of blocks 608 and 618 may also be the same or different.  
[0087]          In some embodiments, the number of attribute plane bits used per pixel may vary based on the point at which compression takes place in flow chart 600.  For instance, all bits of attribute array 500 (with the possible exception of unused bit 504) may be compressed at block 604.    
[0088]          However, after step 612, overlay bit 502, unused bit 504, edge bit 506, and color table bits 508, 510 may no longer be needed.  Further, some types of printing devices do not have a copy function.  Thus, for these printing devices, copy or print bit 512 might not be used any point in flow chart 600, and can be omitted from the compression of block 604 and block 614.
[0089]          Regardless, in various embodiments, anywhere from zero to six bits of attribute array 500 may be omitted from a cell-based compression procedure.  As a result, the overall number of bits that are compressed per cell may be reduced, which may in turn improve the achievable compression ratio of cells of the attribute plane.
[0090]          The description herein focuses on a single instance of cell-based compression applied to the attribute and color planes of an image.  The image may be a representation of a single page from an electronic document containing one or more pages.  Nonetheless, multiple instances of this cell-based compression may be applied to the cell of such an image, according to pipeline 600 or some other arrangement.  In this way the entire image may be compressed in an efficient fashion.
[0091]          Further, cell-based decompression techniques may also be applied to the image by reversing the cell-based compression techniques described herein.
7.         
Example Cell
Configuration 
[0092]          One aspect of cell-based compression is that it may divide each color plane and attribute plane of an electronic document into one or more m x n 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, or m might be 16 and n might be 16, as well.  Other values of m and n may be used.  
[0093]          Each cell may be evaluated to determine what type of compression techniques 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 photorealistic image, the data in the cell may not be able to be compressed at such a high compression ratio.
[0094]          Figure 7 depicts an example cell structure that can be used with cell-based compression.  For sake of convenience, cells are considered in terms of pCells and qCells.  pCells may be m x n element blocks of a color plane or attribute plane of an image.  Thus, for a color plane, pCell elements may be pixels, while for an attribute plane, pCell elements may be attribute arrays.  qCells may be a x b element blocks of a color plane or attribute plane of an image.  Each qCell may consist of some number of non-overlapping pCells.  Depending on context, the terms “pCell” and “qCell” could refer to the elements of a single attribute or color plane or multiple attribute and color planes. 
[0095]          As an example, Figure 7 depicts four 8 x 8 pCells 700, 702, 704, 706 each containing 64 attribute or pixel values for a particular plane.  Each attribute or pixel value, for example, may be represented by a number in the range of 0-255, and thus may be expressed as a byte.  However, other possibilities exist.  For sake of simplicity, pCell 700 only shows the positions of some representative values.
[0096]          A 2 x 2 arrangement of four pCells as shown in Figure 7 may be referred to as a qCell.  Thus, the qCell 710 of Figure 7 may be 16 x 16, and may contain 256 attribute or pixel values for a particular plane.  Nonetheless, a qCell could include a different number of pCells (e.g., a 3 x 2, 2 x 3, or 3 x 3 block of pCells).
[0097]          Figure 7 refers to the upper-left-hand pCell as the “a” pCell, the upper-right-hand pCell as the “b” pCell, the lower-left-hand pCell as the “c” pCell, and the lower-right-hand pCell as the “d” pCell.  These designations may be referred to as pCell IDs, and are merely a convenient way to distinguish the locations of pCells within a qCell, and will be used in the interleaving discussion below. 
[0098]          The cell-based compression techniques described herein may operate on pCells and qCells.  For purposes of simplicity, it will be assumed that 8 x 8 pCells and 16 x 16 qCells are used.  However, this assumption is made with the understanding that differently sized pCells and qCells may be used instead.
[0099]          Further, a planar pCell or qCell may refer to elements of a single plane, while a composite pCell or qCell may refer to corresponding elements across multiple planes.  For instance, when the CMYA color model is used, a planar pCell may include elements of one of the C, M, Y, or A planes, while a composite pCell may include elements from two or more of the C, M, Y, and A planes.
8.         
Example Cell-Based
Compression 
[00100]         The next several sub-sections describe various cell-based compression techniques in detail.  Each of these techniques operates with pCells, qCells, or both.  An overview of these compression techniques is provided in Table 1.
2016144210.tif 000032
[00101]         Compression techniques that are used only on the attribute plane may be described below in more generic terms, because in some systems they may be used on color planes as well for certain embodiments.  For instance, suppose that the cell-based compression disclosed herein is used in block 604 of pipeline 600.  A different compression suite may be used in block 614 of pipeline 600.  Therefore, D1, D1D, P2, P2D, P4, D1C, D1E, and D64 compression is described generically.
a.         
D1 and D1D Compression  
[00102]         D1 compression may be used when all of the attributes or pixels in a given pCell are the same.  For instance, suppose that each attribute or pixel in the pCell takes on a value from 0 to 255.  If all of the values are 74, as just one example, then D1 compression may be applied to this cell.  In this way, the amount of data needed to represent the pCell can be dramatically reduced.  
[00103]         A variation of D1 compression, which may be referred to as D1D compression, may be used when the color value is a default color.  For instance, in the YCbCr color space’s Y plane, 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).   Consequently, D1D compression may require fewer bits per pCell than D1 compression.
[00104]         For the attribute plane, the D1D default value may be predetermined (e.g., 0 or 128) or set manually by a user.
[00105]         In some cases, multiple adjacent pCells (e.g., pCells in a row or column) with same value for all attributes or pixels may be represented using D1 or D1D encoding.  There are two possible ways in which this may occur.  Both D1 and D1D compression allow for a run length to be encoded.  The run length represents how many total pCells were also compressed using D1 compression.  D1 compression also allows a previously used (cached attribute or pixel value) to be used in the encoding of a subsequent pCell.
2016144210.tif 000033
[00106]         Table 2 provides example binary encodings for D1 and D1D compression.  For D1 compression, a compressed representation of a pCell begins with the opcode 001.  If the V’ bit is 1, the D1 encoding also includes the 1-byte value argument (which is the same for all attributes or pixels in the pCell).  If the V’ bit is 0, the value argument is omitted from the encoding, and the value in the most recent D1 encoding (e.g., a cached value) is used for all attributes or pixels in the pCell.  The length argument may be two bits, thus supporting a run length within a qCell from 1 to 4 pCells.  The value argument applies to pixel values as well as attribute values.   Therefore, the value argument may be 8 bits when compressing a pCell of the color plane.  As noted above, however, less than 8 bits may be used to represent attribute plane values, and the size of the value field may be decreased appropriately.
[00107]         For D1D compression, a compressed representation of a pCell begins with the opcode 000.  The V bit indicates which of the two default values is to be used (e.g., if V is 0, then one value will be used, and if V is 1, then the other value will be used).  The length argument may be used in the same fashion as it is used for D1 compression.
b.         
P2 and P2D Compression  
[00108]         P2 compression may be used when each of the attributes or pixels in a given pCell can be represented using one of two values.  For instance, if the attributes or pixels in a cell can take on values between 0 and 255, but all values are either 76 or 125, P2 compression may be used on the pCell.  When P2 compression is used, the two values, as well as a bitmap of the attributes or pixels in the pCell, may be encoded.  The bitmap indicates which value is associated with each attribute or pixel in the pCell.  Similar to D1 and D1D compression, P2 compression may use caching of the most recently used pair of values.
[00109]         A variation of the P2 compression technique, which may be referred to as P2D compression, may be used when only two default color values appear in a cell.  As noted above, in the YCbCr color space’s Y plane, 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.  Thus, P2D compression may encode the bitmap of the attributes or pixels in the pCell, but does not need to explicitly encode the values of the attributes or pixels, because the default values are used. 
[00110]         For the attribute plane, one or both P2D default values may be predetermined (e.g., 0 and 128) or set manually by a user.
2016144210.tif 000034
[00111]         Table 3 provides example binary encodings for P2 and P2D compression.  For P2 compression, a compressed representation of a pCell begins with the opcode 011.  If the V’ bit is 1, the P2 encoding also includes the 2 bytes indicating the pair of values (value 1 and value 2) used by the attributes or pixels in the pCell.  If the V’ bit is 0, these values are omitted from the encoding, and the values in the most recent P2 encoding (e.g., the cached values) are used for the attributes or pixels in the pCell.
[00112]         For P2D compression, a compressed representation of a pCell begins with the opcode 010.  For both P2 and P2D compression, when the P option is 1, the line map argument is present, indicating which of the 8 lines in the bitmap are also present.  When the P option is 0, no line map argument or lines in the bitmap are present.  Instead, a cached bitmap from the most recent pCell compressed with P2 or P2D may be used.
[00113]         Each bit of a line map indicates the presence of a corresponding line field in the bitmap.  If the line map is present, then it may be assumed that at least one line is also present in the bitmap.  Therefore, the line map might only use 7 bits to encode the 2nd through 8th line in the bitmap.  For each bit of the line map a 0 indicates that the corresponding line is absent, and the previous line repeats, while a 1 indicates that the corresponding line is present.
c.         
P4 Compression  
[00114]         P4 compression may be used when all of the pixels in a given cell can be represented using three or four color values.  When P4 compression is used, three or four values, as well as a bitmap of the attributes or pixels in the pCell, may be encoded.  The bitmap indicates which value is associated with each attribute or pixel in the pCell.
2016144210.tif 000035
[00115]         Table 4 provides an example binary encoding for P4 compression.  For P4 compression, a compressed representation of a pCell begins with the opcode 100.  The 7-bit line map defines how the bitmap is compressed, similar to that of a P2 bitmap.  For each bit of the line map, a 0 indicates that the corresponding line is absent, and the previous line repeats, while a 1 indicates that the corresponding line is present.  
[00116]         The four value arguments are 8-bit fields representing the values of elements found in the pCell.  In order to distinguish between these values, each line of the bitmap (if present) may be 16 bits long.  When only three values are encoded by P4 compression, the “value 4” argument may be present but ignored.
d.         
D1C and D1E Compression 
[00117]         D1C and D1E compression facilitate efficient encoding of runs of consecutive cells that are candidates for D1 or D1D compression.  Encoding these runs may dramatically increase compression performance on images with sections exhibiting a solid color (e.g., a white background).  Two types of D1 or D1D runs may be supported: (i) inter-qCell runs of D1 or D1D candidate pCells that cross qCells, and (ii) intra-qCell runs of D1 or D1D candidate pCells within a qCell.
[00118]         Inter-qCell D1 or D1D runs encode D1 or D1D runs that span two or more qCells.  When the two right most pCells (the “b” and “d” pCells) in a qCell contain an 8×16 array of constant pixel values that get encoded using D1 compression, this implies the start of a D1 or D1D run, and causes the encoding mode to change from a normal encoding mode to D1 or D1D run encoding mode.  This encoding mode is tracked per plane, and on qCell boundaries.  Thus, for a particular plane, the mode change to D1 or D1D run encoding mode takes place at the end of a qCell boundary.  
[00119]         In D1 or D1D run encoding mode, only two codes are defined: D1C (continue) and D1E (end), and they are each encoded using a single bit.  As long as subsequent qCells contain the same 16×16 pixel value as the two D1 or D1D candidate pCells that began the run, a 1-bit D1C opcode is emitted, and D1 or D1D run encoding mode continues.  If a subsequent qCell contains anything other than a solid value matching the start of the run, then the run ends.  In this case, a 1-bit D1E code is emitted and normal encoding mode is reentered.  Also, any remaining D1, P2, P4, or D64 encodings for the present qCell are emitted. 
[00120]         Intra-qCell D1 or D1D runs encode D1 or D1D runs within a qCell.  For instance, a 2-bit run length may be used to encode D1 and D1D runs that extend from 1 to 4 pCells within a qCell. Such runs are denoted D1(n) and D1D(n), where n takes on values 1, 2, 3, or 4.
2016144210.tif 000036
[00121]         Table 5 provides example binary encodings for D1C and D1E compression.  For D1C compression, a 1 indicates a continuation of a D1 or D1D run, and all four pCells in the given qCell match the D1 or D1D cells of the current run.  For D1E compression, a 0 indicates the end of a D1 or D1D run.
e.         
D64 Compression
[00122]         D64 compression is a lossless technique that is used to encode a pCell of the attribute plane for which D1, D1D, P2, P2D, and P4 compression is not appropriate.  For instance, if the pCell contains 5 or more different values, D64 compression may be used.  
[00123]         D64 compression encodes all 64 values of an 8 x 8 attribute pCell, and when included with its header, the results in a very small expansion rather than a compression.  However, since it is desirable for the attribute plane to be compressed in a lossless fashion, D64 compression may be necessary in some situations.  
[00124]         Nonetheless, depending on where the cell-based compression is taking place in compression pipeline 600, all 8 bits of the attribute values in a pCell might not be encoded.  Instead, 2-8 bits of these values may instead be packed and encoded.  This results in an improvement for D64 compression.
2016144210.tif 000037
[00125]         Table 6 provides an example binary encoding for D64 compression.  A compressed representation of a D64 pCell begins with the opcode 11, and also includes the 64 attribute arrays in the pCell, encoded using 2-8 bits per attribute.  The number of bits per attribute array is based on how many attribute bits can be omitted when compressing the attribute plane, as discussed above.  
f.         
End of File (EOF)
[00126]         An EOF is not a compression technique per-se, but instead is defined to signal the end of a compression stream.  At a compressor, after all input data has been compressed and the last codes of the last qCell have been emitted, an EOF sequence can be emitted.  The EOF is emitted as an attribute plane code.  
[00127]         If the attribute plane is in D1 or D1D run encoding mode, a D1E may be emitted to return to normal encoding mode before the EOF is emitted.  Additionally, an EOF automatically terminates any active inter-qCell D1 or D1D runs on any plane other than the attribute plane.
2016144210.tif 000038
[00128]         Table 7 provides an example binary encoding for an EOF.  After an opcode of 001, the binary value “10000000000” is emitted.  Since the EOF shares an opcode with D1 compression, this value can be used to differentiate an EOF from a D1 encoding of a pCell.
g.         
DCT 4:2:0 or DCT Y Compression 
[00129]         DCT 4:2:0 compression refers to using discrete cosine transform (DCT) techniques to compress a downsampled qCell such that the resolution of the Cb and Cr color planes is reduced by a factor of 2 in both the horizontal and vertical directions.  
[00130]         As a composite mode operation, DCT 4:2:0 compression may compress the Y plane using one DCT operation per pCell (for a total of four Y plane DCT operations), while downsampling and compressing the Cb and Cr planes into one pCell each. DCT 4:2:0 compression may also involve: a DCT transform, scaling, quantization, reordering from a two-dimensional coefficient array to one-dimensional data, and Huffman entropy coding.  
[00131]         For the Cb and Cr planes, this technique first downsamples a qCell to the size of a pCell, and then applies DCT encoding to the resulting pCell.  As an example, a 16 x 16 qCell may be downsampled to an 8 x 8 pCell.  The downsampling procedure may involve dividing the 16 x 16 qCell into 64 non-overlapping 2 x 2 blocks, and replacing each block with a single pixel value that is the average of the pixel values in the respective block (whether these 2 x 2 blocks represent any edges is not considered).  The resulting 64 average values make up the 8 x 8 cell.  Notably, this downsampling provides an initial 4:1 compression ratio, and then the DCT encoding provides additional compression on top of that.
[00132]         DCT Y compression refers to performing DCT encoding on each of the four pCells of the Y plane of a grayscale image (i.e., where no Cb or Cr plane is present).  Thus, DCT Y is actually a planar mode operation, but can be considered a nominal composite mode operation since there is only one color plane.  
2016144210.tif 000039
[00133]         Table 8 provides an example binary encoding for DCT 4:2:0 and DCT Y compression.  DCT compression may involve no opcode - instead it may consist of the six fields of DCT compressed pCells, as defined in Table 8.  Due to interleaving with the attribute plane (see the discussion of interleaving below) these compressed pCells can be separated from each other by compressed attribute pCells, eliminating the need for an opcode for DCT 4:2:0 compression.  Nonetheless, some representations of DCT 4:2:0 compression may include one or more opcodes.  Like DCT 4:2:0 encodings, DCT Y encodings typically do not use an opcode.  
[00134]         In some embodiments, each 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.
h.         
DCT 4:2:0 Compression with Intelligent Downsampling
[00135]         DCT 4:2:0 compression with intelligent downsampling is identical to that of the DCT 4:2:0 compression discussed above, with an exception - the downsampling procedure weighs pixels that represent edges more heavily than pixels that do not represent edges.  
[00136]         Downsampling is advantageous because it can improve compression ratios while it generally avoids degrading image quality.  This is especially true on the Cb and Cr planes for image content, because these planes are inherently tolerant of artifacts that can be introduced by downsampling.  On the other hand, text and vector objects do not have this tolerance. Downsampling text and vector objects can degrade detail and sharpness, and may introduce artifacts such as color shifts.
[00137]         The intelligent downsampling technique improves upon the basic downsampling by taking advantage of the edge bits in the attribute plane.  These edge bits are used to adjust the downsampling so that sharpness is maintained in text and vector objects, thereby increasing the quality of compressed images.  
[00138]         Particularly, in each 2 x 2 block (4 pixels) that is to be replaced with a single downsampled pixel value, the number of pixels that are associated with edge bits of the attribute plane are counted.  If this sum is 0 or 4, then the pixel values of the 4 pixels are averaged and written to the downsampled pixel value.  However, if 1 to 3 of the 4 pixels are associated with edge bits, then only the values of pixels are associated with edge bits are averaged and written to the downsampled pixel value.
[00139]         As an example, suppose that a 2 x 2 block contains the following Cb or Cr plane pixel values: 0, 72, 76, and 1.  Suppose further that the pixels with the values of 72 and 76 are associated with edge bits, but the pixels with the values of 0 and 1 are not.  Then, the pixels with the values of 72 and 76 may be averaged and the resulting pixel value of 74 may be written to the downsampled pixel value.  Consequently, the edge represented by the pixels with the values of 72 and 76 may be enhanced.
[00140]         DCT 4:2:0 compression with intelligent downsampling may use the encoding defined in Table 8.
i.         
DCTL Compression  
[00141]         DCTL compression is also similar to DCT 4:2:0 compression, except that it downsamples and compresses all color planes, not just the Cb and Cr planes.  DCTL compression may be applied to qCells with small ranges of luminance values on the Y plane.
2016144210.tif 000040
[00142]         Table 9 provides an example binary encoding for DCTL compression.  For DCTL compression, a compressed representation of a plane of a qCell begins with the opcode 1, and the remaining part of the representation is a DCT encoding.  Similar to the DCT 4:2:0 case, the DCT encoding may be a collection of quantized DCT coefficients packaged according to a subset of the JPEG standard, with Huffman encoding.  
j.         
QD1 and QD1D Compression
[00143]         QD1 compression may be used when all of the pixels in a given qCell are the same or close in value.  QD1 compression encodes an entire qCell with the same pixel value.  Whether the pixel values in the qCell are close enough to one another may be determined by examining the range of pixel values within each pCell of the qCell, and the difference between the average values of each pCell.  If, for example, the range of pixel values within each pCell is less than or equal to a cell-level threshold value, and the average values of the pCells are all within a macro-cell-level threshold value of one another, QD1 compression may be used.  In some embodiments, the cell-level threshold value may be between 2 and 16, while the macro-cell-level threshold value may be between 1 and 8, for instance.
[00144]         QD1D compression is analogous to that of D1D compression.  Thus, QD1D compression can be used when the pixel values in a qCell match the default values for Y, Cb, or Cr.  
[00145]         QD1 and QD1D compression are both lossy variations of D1 and D1D compression, respectively.  By allowing a limited amount of loss with QD1 and QD1D compression, compression ratios can be greatly increased over that of DCT-based compression.  Additionally, like D1 and D1D compression, QD1 and QD1D compression allow runs, which further improve compression ratios.
[00146]         To that point, multiple adjacent qCells (e.g., qCells in a row or column) with same pixel values may use QD1 or QD1D encoding.  Each QD1 and QD1D encoding implicitly indicates the beginning of a run of QD1 or QD1D cells, respectively.  If a run of two or more QD1 or QD1D cells in the same color plane exists, then the second and any subsequent QD1 or QD1D cells in the run may be represented by QD1C encodings (see below).  A run may end with a QD1E encoding (see below).
2016144210.tif 000041
[00147]         Table 10 provides example binary encodings for QD1 and QD1D compression.  For QD1 compression, a compressed representation of a qCell begins with the opcode 01.  If the V’ bit is 1, the QD1 encoding also includes the 1-byte pixel value argument (which is the same for all pixels in the qCell).  If the V’ bit is 0, the value argument is omitted from the encoding, and the value in the most recent QD1 encoding (e.g., a cached value) is used for all pixels in the qCell.  
[00148]         For QD1D compression, a compressed representation of a pCell begins with the opcode 00.  The V bit indicates which of the two default values is to be used (e.g., if V is 0, then one value will be used, and if V is 1, then the other value will be used).  
k.         
QD1C and QD1E Compression
[00149]         As noted above, when encoding non-initial cells of a run within a particular color plane, only two codes are defined: QD1C (continue) and QD1E (end), and they are each encoded using a single bit.  As long as subsequent qCells contain the same pixel value as the qCell that began the run, a 1-bit QD1C opcode is emitted, and QD1 or QD1D run encoding mode continues.  If a subsequent qCell contains anything other than a solid value matching the start of the run, then the run ends.  In this case, a 1-bit QD1E code is emitted and normal encoding mode is reentered.  
2016144210.tif 000042
[00150]         Table 11 provides example binary encodings for QD1C and QD1E compression.  For QD1C compression, a 1 indicates a continuation of a QD1 or QD1D run.   For QD1E compression, a 0 indicates the end of a QD1 or QD1D run.
l.         
Composite and Planar Modes
[00151]         As noted above, qCells may be compressed in either a planar mode (each plane is compressed independently) or a composite mode (two or more planes are compressed in a related fashion).  In some embodiments, the attribute plane might only be compressed using planar mode, but the color planes may be compressed using either mode, based on their characteristics.  
[00152]         In order to indicate, in the compressed bitstream, the mode that is being used for a particular qCell, a special q-opcode may be emitted at the beginning of the compressed representation of each qCell.  When a qCell is compressed using composite mode, the q-opcode may be a 1, whereas when a qCell is compressed using planar mode, the q-opcode may be a 0.
2016144210.tif 000043
[00153]         Table 12 specifies when composite and planar modes are used.  For instance, when DCT 4:2:0 compression (with or without intelligent downsampling) or DCT Y is used for a qCell, that qCell is prefaced by a q-opcode of 1, but no opcodes are present for the encodings of each color plane within the qCell.
[00154]         When any other compression technique is used for a qCell, that qCell is prefaced with a q-opcode of 0, and the compression technique used is indicated with its opcode.  Also, the distinction between normal mode and run mode only exists in planar mode.  For instance, any qCell encoding using QD1, QD1D, or DCTL compression is performed in normal mode, while any encoding using QD1C or QD1E compression is performed in run mode.  Switching from planar mode to composite mode implicitly ends all runs.
[00155]         Note that composite encoding does not include encoding of the attribute plane.  It is assumed that the attribute plane is encoded separately.
[00156]         More examples of composite mode and planar mode encodings are provided below in the discussion of interleaving.
9.         
Example Decision
Trees
[00157]         The encoding of pCells and qCells may be based on one or more decision trees.  Each decision tree illustrates a process through which various factors are considered before a pCell or qCell is encoded.  There may be separate decision trees for attribute planes, color planes, and grayscale planes.  For instance, it is desirable to not lose any information when compressing an attribute plane.  Therefore, attribute planes may be compressed using various lossless compression techniques.  On the other hand, it is desirable to compress some portions of color planes (e.g., vector graphics and text portions) and grayscale with varying degrees of loss based on characterization of the pixels.  In this way, details in the original image can be preserved when desired, but high compression ratios can still be achieved.
a.         
Color Plane Decision Tree
[00158]         Figure 8 depicts a color plane decision tree 800, in accordance with example embodiments.  This decision tree considers the properties of a qCell, with the understanding that a qCell consists of four non-overlapping pCells.  The sizes of such a qCell and its subsidiary pCells may be 16 x 16 and 8 x 8, respectively.  However, other sizes may be used instead.
[00159]         It is assumed that the each pixel in the qCell is tagged with an indication of whether the pixel is part of an edge in the input image.  These tags may reside in the attribute plane for the qCell.  
[00160]         In each decision block 802, 806, 810, the type of decision is indicated parenthetically.  If the decision is made on a planar basis, a parenthetical P is present.  If the decision is made on a composite basis, a parenthetical C is present.  
[00161]         Planar decisions are made by considering the qCells and/or pCells of each color plane separately.  Thus, for instance, a planar decision may consider the color properties and/or attributes associated with a single qCell and/or pCell.  However, a composite decision may consider the qCell and pCell properties and associated attributes for all color planes in a location of the image defined by the qCell.  
[00162]         For purposes of simplicity, QD1D compression is not referenced explicitly in decision tree 800.  However, wherever QD1 is considered or used, QD1D compression may be considered or used as well.  Thus, block 814 may use QD1D compression.  Runs of consecutive QD1 or QD1D encodings are also not explicitly considered in decision tree 800, but may be used regardless.
[00163]         At block 802, it is determined whether an edge bit is set for any attribute byte in the qCell.  If so, DCT 4:2:0 compression with intelligent downsampling is applied at block 804.  In doing so, the sharpness of the edges in the image may be preserved and/or enhanced.
[00164]          Otherwise, at block 806, it is determined whether any pCell in any color plane exhibits a pixel range greater than a predetermined threshold.   If so, DCT 4:2:0 compression without intelligent downsampling may be applied at block 808.  The pixel range of a pCell may be determined by subtracting the lowest pixel value in the pCell from the highest pixel value in the pCell.  The predetermined threshold may take on values such as 8, 16, 32, etc.
[00165]           Otherwise, at block 810, condition A is tested separately for each color plane.  In order to be met, condition A requires that (i) each pCell’s pixel range is less than or equal to a predetermined cell-level threshold, and (ii) the range of pCell average pixel values is less than a predetermined macro-cell-level threshold.  The predetermined cell-level threshold may take on values such as 4, 8, 16, etc., and the predetermined macro-cell-level threshold may take on values such as 2, 4, 8, etc.  In some embodiments, the predetermined macro-cell-level threshold is less than the predetermined cell-level threshold, and the predetermined cell-level threshold is less than the predetermined threshold.
[00166]         If condition A is true, then the pixels in the qCell of the plane in question have a narrow range of pixel values, and QD1 compression is applied at block 814.  If condition A is not true, then DCTL compression is applied at block 812.
[00167]         Figure 8 depicts one possible color plane decision tree.  Other such decision trees are possible.  
b.         
Grayscale Plane Decision Tree
[00168]         Figure 9 depicts a grayscale plane decision tree 900, in accordance with example embodiments.  This decision tree considers the properties of a qCell, with the understanding that a qCell consists of four non-overlapping pCells.  The sizes of such a qCell and its subsidiary pCells may be 16 x 16 and 8 x 8, respectively.  However, other sizes may be used instead. Grayscale images include only the luminance (Y) or key (K) planes, so qCells from these images can be compressed in a planar fashion.
[00169]         As was the case for the color plane decision tree, it is assumed that the each pixel in the qCell is tagged with an indication of whether the pixel is part of an edge in the input image.  These tags may reside in the attribute plane for the qCell.  
[00170]         In each decision block 902, 906, 910, the type of decision is indicated parenthetically.  Since grayscale images have a single color plane, all such decisions are planar.  Thus, these decisions consider the properties and/or attributes associated with a single qCell and/or pCell.    
[00171]         For purposes of simplicity, QD1D compression is not referenced explicitly in decision tree 900.  However, wherever QD1 is considered or used, QD1D compression may be considered or used as well.  Thus, block 914 may use QD1D compression.  Runs of consecutive QD1 or QD1D encodings are also not explicitly considered in decision tree 900, but may be used regardless.
[00172]         At block 902, it is determined whether an edge bit is set for any attribute byte in the qCell.  If so, DCT Y compression is applied at block 904.  Otherwise, at block 906, it is determined whether any pCell in the pixel plane exhibits a pixel range greater than a predetermined threshold.   If so, DCT Y compression may be applied at block 908.  The pixel range of a pCell may be determined by subtracting the lowest pixel value in the pCell from the highest pixel value in the pCell.  The predetermined threshold may take on values such as 8, 16, 32, etc.
[00173]         DCT Y compression performs DCT-based compression on each of the pCells in a qCell.  For example, a 16 x 16 qCell may be divided into four 8 x 8 pCells, and DCT-based compression may be applied to each 8 x 8 pCell.  
[00174]         Otherwise, at block 910, condition A is tested.  In order to be met, condition A requires that (i) each pCell’s pixel range is less than or equal to a predetermined cell-level threshold, and (ii) the range of pCell average pixel values is less than a predetermined macro-cell-level threshold.  The predetermined cell-level threshold may take on values such as 4, 8, 16, etc., and the predetermined macro-cell-level threshold may take on value such as 2, 4, 8, etc.  In some embodiments, the predetermined macro-cell-level threshold is less than the predetermined cell-level threshold, and the predetermined cell-level threshold is less than the predetermined threshold.
[00175]         If condition A is true, then the pixels in the qCell have a narrow range of pixel values, and QD1 compression is applied at block 914.  If condition A is not true, then DCTL compression is applied at block 912.
[00176]         Figure 9 depicts one possible grayscale plane decision tree.  Other such decision trees are possible.  
c.         
Attribute Plane Decision Tree
[00177]         Figure 10 depicts an attribute plane decision tree 1000, in accordance with example embodiments.  This decision tree considers the properties of a pCell of an attribute plane, with that understanding that each element of this attribute plane pCell is associated in a one-to-one fashion with a pixel values of one or more corresponding color plane pCells.  The size of these pCells may be 8 x 8, but other sizes may be used instead.  It is also assumed that there is only one attribute plane, so all decisions in decision tree 1000 are made on a planar basis.  However, alternative embodiments could take different approaches. 
[00178]         Similar to decision trees 800 and 900, D1D and P2D compression are not referenced explicitly in decision tree 1000.  However, wherever D1 or P2 compression are considered or used, D1D and P2D compression may be considered or used as well.  Thus, blocks 1002, 1004, 1006, and 1008 may consider and/or use D1D and P2D compression.  Runs of consecutive D1 or D1D encodings are also not explicitly considered in decision tree 1000, but may be used regardless.
[00179]         At block 1002, it is determined whether the attribute plane pCell qualifies for D1 compression (i.e., all attribute arrays in the pCell are identical).  If so, D1 compression is applied at block 1004.  Otherwise, at block 1006, it is determined whether the pCell qualifies for P2 compression (i.e., all attribute arrays in the pCell have one of two values).  If so, P2 compression may be applied at block 1008.  
[00180]         If the pCell does not qualify for either D1 or P2 compression, at block 1010 it may be determined whether the pCell qualifies for P4 compression (i.e., all attribute arrays in the pCell have one of four values).  If so, P4 compression may be applied at block 1012.  Otherwise, D64 compression may be applied at block 1014.
[00181]         Figure 10 depicts one possible attribute plane decision tree.  Other such decision trees are possible.  
10.        
Interleaved
Encoding
[00182]         The encoded output of cell-based compression may be interleaved.  In some cases, an interleaved encoding may be superior to a non-interleaved encoding.
[00183]         This interleaving may consider (i) the ordering of pCells and planes across qCells, (ii) whether downsampling is a planar or composite decision, and (iii) compression performance.  For the latter consideration, separate DCT compression and pattern (non-DCT) compression processors may be used.  It is assumed that the DCT compression processor will run in parallel with the pattern processor, and that the DCT processor may run much slower, perhaps at one-eighth the speed of the pattern processor.  Thus, the interleave format may support maintaining high utilization of the DCT processor in various mixes of DCT and pattern pCells.  
[00184]         Based on these considerations, the qCells and pCells of the attribute plane and color planes may be written to an output medium (e.g., storage of block 606 and/or storage of block 616) in an interleaved fashion.  As an example, if the color model is YCbCrA, then the ordering of encoded cells may be an attribute cell, then a luminance (Y) cell, then a Cb cell, then a Cr cell, then another attribute cell, then another luminance (Y) cell, then another Cb cell, then another Cr cell, and so on.
[00185]         An example of such an interleaving operation is shown in Figures 11A and 11B.  Figure 11A depicts a series of four qCells for each of the attribute, Y, Cb, and Cr planes.  Each pCell within a qCell is associated with a respective pCell ID (e.g., a, b, c, or d), and depicted as a box.  The boxes contain the compression technique used to compress each respective pCell, as well as the qCell number and pCell ID.  For example, the first (left-most) pCell of the attribute plane was compressed using P2 compression and is from pCell 1a.  
[00186]         Throughout the four qCells, the attribute plane is consistently encoded using P2 compression, the Y plane is encoded using DCT or DCTL compression, the Cb plane is encoded using DCT (i.e., DCT 4:2:0) or QD1 compression, and the Cr plane is encoded using DCT (i.e., DCT 4:2:0), QD1, or DCTL compression.  
[00187]         Figure 11B depicts an interleaved encoding of the pCells and qCells of Figure 11A.  Each of the color and attribute planes are interleaved one-by-one-by-one-by-one, except for when a run is encoded in a more efficient fashion.  For instance, the encoding begins, in the 1st output position, with an indication that composite mode (CM) is active.  This is followed by the pCells of the first qCell.  Composite mode is used for the first qCell because it is encoded using DCT 4:2:0.  
[00188]         In the encoding, the first pCell is the 1a pCell of the attribute plane, then the 1a pCell of the Y plane, the 1a pCell of the Cb plane, the 1a pCell of the Cr plane, the 1b pCell of the attribute plane, the 1b pCell of the Y plane, and so on.  Note that the opcodes are omitted for Y, Cb, and Cr encodings in composite mode. 
[00189]         For the second qCell, planar mode is entered, at the 12th output position, because the color channels are encoded using DCTL and QD1 compression.  Each of the QD1 encodings for the Cb and Cr color channels implicitly begins a QD1 run.  Note that opcodes are present for each of the encoded pCells.
[00190]         For the third qCell, planar mode is also indicated, at the 20th output position, because the color channels are once again encoded using DCTL and QD1 compression.  Since the QD1 run in the Cb plane continues, a QD1C encoding is used for that plane.  However, the QD1 run does not continue for the Cr plane.  Thus, a QD1E encoding is used to indicate the end of the QD1 run, and a DCTL encoding, at the 25th output position, is used to represent the Cr plane pCell.
[00191]         For the fourth qCell, composite mode is used once again.  The composite mode indicator (the CM encoding in the 29th output position) implicitly ends the run of QD1 encodings in the Cb plane.  After the encoding of the fourth qCell, another composite mode indicator and then an end-of-file (EOF) are encoded to end this section of the interleaved representation.
[00192]         Another example of an interleaving operation is shown in Figures 12A and 12B.  Figure 12A depicts a series of four qCells for each of the attribute, Y, Cb, and Cr planes.  However, unlike the example of Figures 11A and 11B, the example of Figure 12A includes a D1 run on the attribute plane.
[00193]         Figure 12B depicts an interleaved encoding of the pCells and qCells of Figure 12A.  Each of the color and attribute planes are interleaved one-by-one-by-one-by-one, except for when a run is encoded in a more efficient fashion,  In particular, an attribute plane D1 run implicitly begins in the first qCell as represented by the two D1 encodings at the 6th and 10th output positions.  The QD1 run on the Cb plane is the same as that of Figures 11A and 11B.
[00194]         In the second qCell, the D1 run is represented by a single D1C encoding at the 13th output position.  However, the D1 run ends in the third qCell.  Thus, a D1E encoding appears at the 18th output position, indicating the end of the D1 run.  Then, the four attribute pCells of the third qCell are encoded individually.  
[00195]         The fourth qCell contains an intra-qCell D1 run.  Therefore, these four pCells are represented in a single D1 encoding that indicates a run of four (D1 R(4)) at the 28th output position.  Like the example of Figure 11B, another composite mode indicator and then an end-of-file (EOF) are encoded to end this section of the compressed representation.  However, switching from planar mode to composite mode does not implicitly end an attribute plane run in this example.  As a result, a D1E encoding appears at the 36th output position in order to perform this function.
[00196]         Figures 11A, 11B, 12A, and 12B are provided for purposes of illustration.  Other encodings may be supported by the embodiments herein, and variations may be made to these encodings without departing from the scope of the embodiments.
11.        
Example Cell-Based
Decompression 
[00197]         Once a number of pCells and/or qCells 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 pCells and/or qCells may be decompressed into the original image or 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.  
[00198]         The pCells and/or qCells encoded with the compression encodings described above can be decoded and decompressed as follows.  For a particular qCell encoding, the q-opcode is read to determine whether the qCell is encoded using composite mode or planar mode.  Based on this mode, one or more opcodes are read.  Based on the value of each opcode, any applicable options, arguments, bitmaps, etc., can be determined from the bits following the opcode.  From these parameters, a decompressed version of the pCell or qCell can be reconstructed.  Then, the next opcode is read and so on until the image is reconstructed.
a.         
Attribute Plane Decompression
[00199]         On the attribute plane, if the opcode is 001, indicating D1 encoding, the V’ bit and the arguments field may be read to determine the value of the compressed element.  The length bits 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 value indicated by the value field in the encoding, or in a cached version of the value field. 
[00200]         If the opcode is 000, indicating D1D encoding, the V bit may be read to determine the value of the compressed element, and the length bits 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 value indicated by the V bit. 
[00201]         If the opcode is 011, indicating P2 encoding, the options, arguments, and bitmap may be read.  If the V’ bit is 1, the two values in the cell may be determined.  Then, a cell may be created with each pixel taking on one of the two values in accordance with the line map and the bitmap.  If the line map is not present, then the line map and bit map from the previous P2 cell are used.  
[00202]         If the opcode is 010, indicating P2D compression, a cell may be created with each pixel taking on one of the two values in accordance with the line map and the bitmap.  If the line map is not present, then the line map and bitmap from the previous P2 cell are used.  
[00203]         If the opcode is 100, indicating P4 compression, the line map and values arguments may be read, as well as the bitmap.  Then, a cell may be created with each pixel taking on one of the four color values in accordance with the line map and bitmap.
[00204]         If the opcode is 1, indicating D1C compression, then the most recent D1 or D1D cell is copied.  If the opcode is 0, indicating D1E compression, the current D1 or D1D run is considered to have ended.
[00205]         If the opcode is 11, indicating D64 compression, the number of bits per attribute is determined, and then the attributes field is decoded accordingly.  The number of bits per attribute may depend on the type of printing device and where in the pipeline that the decompression is occurring.
b.         
Color Plane and Grayscale Plane Decompression
[00206]         Color plane decompression varies based on whether composite mode or planar mode is being used.  If planar mode is being used, the decompression also varies based on whether normal mode or run mode is active.  Grayscale plane decompression only uses planar mode.
[00207]         When composite mode is used, a q-opcode of 1 is followed by either a DCT 4:2:0 or a DCT Y encoding, based on whether the image is color or grayscale.  When planar mode is used, a q-opcode of 0 is followed by an opcode indicating the type of encoding that appears next.  
[00208]         For instance, in normal mode, a 01 opcode indicates a QD1 encoding, a 00 opcode indicates a QD1D encoding, and a 1 opcode indicates a DCTL encoding.  In run mode, a 1 opcode indicates a QD1C encoding, and a 0 opcode indicates a QD1E encoding.
[00209]         Decompressing a pCell that was compressed using DCT 4:2:0 with intelligent downsampling may involve using the edge bits in the associated attribute arrays.  Since the edge bits represent the original (non-downsampled) edge bits, the location of edges in the original image is known.  Further, with DCT 4:2:0 compression, the corresponding Y plane value for the pixel (the pixel’s luminance) is also known.
[00210]         When decompressing, a downsampled pCell is upsampled to a qCell.  Thus, for example, each pixel in the pCell is upsampled to a 2 x 2 block of pixels in the qCell.  Assume that the value of the downsampled pixel is f.  Then each pixel c(x,y), c(x+1,y), c(x,y+1), and c(x+1,y+1) of the 2 x 2 block is set to f if that pixel represents an edge.  The Y plane value of each non-edge pixel is compared to a threshold.  If the Y plane value exceeds the threshold, the non-edge pixel is set to 128 (a neutral color), otherwise the non-edge pixel is set to f.  If no edges are present, then all four pixels are set to f. The threshold may be any value, for instance, 220 or higher.
[00211]         In some embodiments, neutral color values other than 128 can be used instead.  In general, this technique preserves edges while upsampling because the scanning unit may be configured to only set the edge bit for a pixel when one of the two pixels defining the edge is white or near-white. 
12.        
Example
Performance Results
[00212]         The cell-based compression techniques described herein were compared to two variations of JPEG compression, JPEG Q90 and JPEG Q95.  JPEG Q90 and JPEG Q95 refer to common quantization tables used in JPEG for DCT coefficients.  JPEG Q90 yields high quality, and JPEG Q95 yields even higher quality.  Twenty-six representative and challenging pages were compressed with the cell-based compression techniques described herein, as well as with JPEG Q90 and JPEG Q95.  Flat7 quantization tables were used in the cell-based compression techniques for DCT coefficients.
[00213]         The results of these comparisons are as follows.  The cell-based compression techniques yielded better compression ratios than JPEG Q95 for all twenty-six pages.  On average, JPEG 95 provided a compression ratio approximately 85% worse than the cell-based compression techniques.  Also, the cell-based compression techniques yielded better compression ratios than JPEG 90 for all but five pages.  Of these five pages, JPEG 90 provided at most an 8% improvement over the cell-based compression techniques.  But, on average, JPEG 90 provided a compression ratio approximately 19% worse than the cell-based compression techniques.
[00214]         Significantly, the cell-based compression techniques produced subjectively better image quality than both JPEG settings.
13.        
Example Operations
[00215]         Figures 13, 14, and 15 are flow charts of example embodiments. The steps illustrated by these flow charts 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 or printing devices. 
[00216]         With respect to the terms used herein, an m x n attribute cell may refer to a planar pCell of the attribute plane, and an m x n pixel cell may refer to a planar pCell of a color plane.  Further, an a x b attribute cell may refer to a planar qCell of the attribute plane, and an a x b pixel cell may refer to a planar qCell of a color plane.  It is assumed throughout that a is greater than m and b is greater than n.
[00217]         Figure 13 generally depicts steps for cell-based compression of color planes of an input image.  However, these steps may be used for additional purposes as well.  Operations discussed in reference to Figures 5-12B may be explicitly or implicitly referenced in this flow chart.  For instance, the steps of Figure 13 could take place at block 604 of Figure 6, in other locations of a printing device’s pipeline, or by a host computer.
[00218]         At step 1300, a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image may be obtained.  The a x b pixel macro-cells may each contain 4 non-overlapping m x n pixel cells, and pixels in the a x b pixel macro-cells may have respective pixel values.
[00219]         At step 1302, it may be determined whether at least e pixels in the a x b pixel macro-cells represent edges in the input image.  The value of e may be at least 1.
[00220]         At step 1304, possibly based on whether at least e pixels in the a x b pixel macro-cells represent edges in the input image, either a first encoding or a second encoding of the a x b pixel macro-cells may be selected.  The first encoding may weigh some pixels that represent edges in the input image heavier than pixels that do not represent edges in the input image, and the second encoding might not consider whether pixels represent edges in the input image.  
[00221]         At step 1306 the selected encoding may be performed.  At step 1308, a representation of the selected encoding, as performed, may be written to a computer-readable output medium.
[00222]         The first and second encodings may be compressed encodings.  Therefore, further steps may involve decompressing the representation of the selected encoding of the a x b pixel macro-cells and printing the input image, including the a x b pixel macro-cells as decompressed.
[00223]         The first encoding may be the selected encoding.  In such embodiments, performing the selected encoding may involve downsampling blocks of pixels in the a x b pixel macro-cells of the first color plane and the second color plane to form a first downsampled m x n pixel cell for the first color plane and a second downsampled m x n pixel cell for the second color plane.  The downsampling may weigh pixels that represent edges in the input image heavier than pixels that do not represent edges in the input image (e.g., using intelligent downsampling).  Performing the selected encoding may further involve encoding a transform of the 4 non-overlapping m x n pixel cells of the luminance plane, the first downsampled m x n pixel cell, and the second downsampled m x n pixel cell.  The transforms may be based on discrete cosine transforms, such as DCT 4:2:0.
[00224]         Alternatively, the second encoding may be the selected encoding.  In such embodiments, performing the selected encoding may involve (i) determining that a range of pixel values in at least one of the 4 non-overlapping m x n pixel cells from any of the a x b pixel macro-cells is greater than a threshold value, (ii) downsampling blocks of pixels in the a x b pixel macro-cells of the first color plane and the second color plane to form a first downsampled m x n pixel cell for the first color plane and a second downsampled m x n pixel cell for the second color plane, and (iii) encoding transforms of the 4 non-overlapping m x n pixel cells of the luminance plane, the first downsampled m x n pixel cell and the second downsampled m x n pixel cell.  The downsampling might not consider whether pixels represent edges in the input image.  The transforms may be based on discrete cosine transforms, such as DCT 4:2:0.
[00225]         In yet another alternative, the second encoding may be the selected encoding, and performing the selected encoding may involve (i) determining that ranges of pixel values in each of the 4 non-overlapping m x n pixel cells for each of the a x b pixel macro-cells are less than or equal to a threshold value, (ii) determining respective average pixel values for each of the 4 non-overlapping m x n pixel cells for a particular one of the a x b pixel macro-cells, (iii) determining that either (a) at least one of the ranges of pixel values is greater than a cell-level threshold value, or (b) a range of the respective average pixel values is greater than or equal to a macro-cell-level threshold value, (iv) downsampling blocks of pixels in the particular one of the a x b pixel macro-cells to a downsampled m x n pixel cell, and (v) encoding a transform of the downsampled m x n pixel cell (e.g., using DCTL compression).  The downsampling might not consider whether pixels in the particular one of the a x b pixel macro-cells represent edges in the input image.  The threshold value may be greater than both of the cell-level threshold value and the macro-cell-level threshold value.
[00226]         In still another alternative, the second encoding may be the selected encoding, and performing the selected encoding may involve (i) determining respective average pixel values for each of the 4 non-overlapping m x n pixel cells for a particular one of the a x b pixel macro-cells, (ii) determining that ranges of pixel values in each of the 4 non-overlapping m x n pixel cells for the particular one of the a x b pixel macro-cells are all less than or equal to a cell-level threshold value, (iii) determining that the ranges of the respective average pixel values are less than a macro-cell-level threshold value, and (iv) encoding the particular one of the a x b pixel macro-cells with a single pixel value (e.g., using QD1 compression).
[00227]         Figure 14 generally depicts steps for cell-based compression of a color plane.  However, these steps may be used for additional purposes as well.  Operations discussed in reference to Figures 5-12B may be explicitly or implicitly referenced in this flow chart.  For instance, the steps of Figure 14 could take place at block 604 of Figure 6, in other locations of a printing device’s pipeline, or by a host computer.
[00228]         At step 1400, an a x b pixel macro-cell from an input image may be obtained.  Pixels in the a x b pixel macro-cell may have respective pixel values, and may be associated with respective tags. These tags might be edge bits in respectively associated attribute arrays. 
[00229]         At step 1402, it may be determined whether at least e of the respective tags indicate that their associated pixels represent edges in the input image.  The value of e may be at least 1.
[00230]         At step 1404, possibly based on whether at least e of the respective tags indicate that their associated pixels represent edges in the input image, either a first encoding or a second encoding of the a x b pixel macro-cell may be selected.  The first encoding may weigh pixels that represent edges in the input image heavier than pixels that do not represent edges in the input image.  The second encoding might not consider whether pixels represent edges. 
[00231]         At step 1406, the selected encoding may be performed.  At step 1408, a representation of the selected encoding, as performed, may be written to a computer-readable output medium.
[00232]         In some embodiments, the first encoding may be the selected encoding, and performing the selected encoding may involve (i) based on the tags, determining that a first 2 x 2 block of pixels in the a x b pixel macro-cell contains g pixels representing edges in the input image, and encoding a first pixel in a downsampled m x n pixel cell with an average value of the g pixels (e.g., DCT 4:2:0 compression with intelligent downsampling).  The value of g may be 1, 2, or 3.  In these embodiments, performing the selected encoding may further involve (i) based on the tags, determining that a second 2 x 2 block of pixels in the a x b pixel macro-cell contains no pixels representing edges in the input image, and encoding a second pixel in the downsampled m x n pixel cell with an average value of all pixels in the second 2 x 2 block of pixels.  The average value of all pixels might not consider whether pixels represent edges.
[00233]         In alternative embodiments, the a x b pixel macro-cell may contain 4 non-overlapping m x n pixel cells.  The second encoding may be the selected encoding, and performing the selected encoding may involve (i) determining that a range of pixel values in at least one of the 4 non-overlapping m x n pixel cells exceeds a predetermined non-zero threshold value, and (ii) encoding a particular pixel in a downsampled m x n pixel cell with an average value of all pixels in a particular 2 x 2 block of pixels in the a x b pixel macro-cell (e.g., DCT 4:2:0 compression without intelligent downsampling).  The average value of all pixels might not consider whether pixels represent edges.  
[00234]         In further embodiments, the a x b pixel macro-cell may also contain 4 non-overlapping m x n pixel cells.  The second encoding may be the selected encoding, and performing the selected encoding may involve (i) determining that ranges of pixel values in each of the 4 non-overlapping m x n pixel cells are less than or equal to a threshold value, (ii) determining respective average pixel values for each of the 4 non-overlapping m x n pixel cells, (iii) determining that either (a) at least one of the ranges of pixel values is greater than a cell-level threshold value, or (b) a range of the respective average pixel values is greater than or equal to a macro-cell-level threshold value, (iv) downsampling blocks of pixels in the a x b pixel macro-cell to a downsampled m x n pixel cell, and (v) encoding a transform of the downsampled m x n pixel cell (e.g., using DCTL compression).  The threshold value may be greater than both of the cell-level threshold value and the macro-cell-level threshold value.  The downsampling might not consider whether pixels in the a x b pixel macro-cells represent edges in the input image.
[00235]         In additional embodiments, the a x b pixel macro-cell may also contain 4 non-overlapping m x n pixel cells.  The second encoding may be the selected encoding, and performing the selected encoding may involve (i) determining respective average pixel values for each of the 4 non-overlapping m x n pixel cells, (ii) determining that ranges of pixel values in each of the 4 non-overlapping m x n pixel cells are all less than or equal to a cell-level threshold value, (iii) determining that the ranges of the respective average pixel values are less than a macro-cell-level threshold value, and (iv) encoding the a x b pixel macro-cell with a single pixel value (e.g., using QD1 compression).  
[00236]         Figure 15 generally depicts steps for interleaving compressed representations of cells from an attribute plane and one or more color planes.  However, these steps may be used for additional purposes as well.  Operations discussed in reference to Figures 5-12B may be explicitly or implicitly referenced in this flow chart.  For instance, the steps of Figure 15 could take place at block 604 of Figure 6, in other locations of a printing device’s pipeline, or by a host computer.
[00237]         At step 1500, (i) an a x b attribute macro-cell, and (ii) a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image may be obtained.  The a x b pixel macro-cells may each contain 4 non-overlapping m x n pixel cells.  The a x b pixels in the a x b pixel macro-cells may have respective pixel values, and elements of the a x b attribute macro-cell may be associated in a one-to-one fashion with respective pixels in each of the a x b pixel macro-cells.
[00238]         At step 1502, 4 attribute-plane output values that respectively represent the 4 non-overlapping m x n attribute cells may be determined.  At step 1504, possibly based at least partially on whether the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image, 1 to 4 luminance-plane output values that represent the a x b pixel macro-cell of the luminance plane may be determined.  The value of e may be at least 1.
[00239]         At step 1506, a first color-plane output value to represent the a x b pixel macro-cell of the first color plane and a second color-plane output value to represent the a x b pixel macro-cell of the second color plane may be determined.  At step 1508, an interleaved representation of the 4 attribute-plane output values, the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value may be written to a computer-readable output medium.  The first color-plane output value may be represented in less than a x b bytes, and the second color-plane output value may be represented in less than a x b bytes.
[00240]         In some embodiments, determining the 1 to 4 luminance-plane output values may involve (i) determining that the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image, and (ii) determining 4 luminance-plane output values that respectively represent each of the non-overlapping m x n pixel cells in the a x b pixel macro-cell of the luminance plane.  The first color-plane output value and the second color-plane output value may be downsampled versions of the a x b pixel macro-cell of the first color plane and of the second color plane, respectively, that weigh pixels representing edges in the input image heavier than pixels that do not represent edges in the input image.
[00241]         Alternatively, determining the 1 to 4 luminance-plane output values may involve (i) determining that (a) the a x b attribute macro-cell indicates that less than e pixels in the a x b pixel macro-cells represent edges in the input image, and (b) a range of pixel values in at least one of the 4 non-overlapping m x n pixel cells of the a x b pixel macro-cells is greater than a threshold value, and (ii) determining 4 luminance-plane output values that respectively represent each of the non-overlapping m x n pixel cells in the a x b pixel macro-cell of the luminance plane.  The first color-plane output value and the second color-plane output value may be downsampled versions of the a x b pixel macro-cell of the first color plane and of the second color plane, respectively, and wherein the downsampling does not consider whether pixels represent edges in the input image.
[00242]         In other embodiments, determining the 1 to 4 luminance-plane output values may involve (i) determining that (a) the a x b attribute macro-cell indicates that less than e pixels in the a x b pixel macro-cells represent edges in the input image, and (b) ranges of pixel values in each of the 4 non-overlapping m x n pixel cells for each of the a x b pixel macro-cells are less than or equal to a threshold value, and (ii) determining 1 luminance-plane output value that represents the a x b pixel macro-cell of the luminance plane.
[00243]         Alternatively or additionally, when 4 luminance-plane output values are determined, the interleaved representation may be prefaced by a composite mode indicator, and opcodes may be omitted for each of the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value in the interleaved representation.  On the other hand, when 1 luminance-plane output value is determined, and the interleaved representation may be prefaced by a planar mode indicator, and opcodes may be included for each of the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value in the interleaved representation.
[00244]         In some cases, the first color-plane output value may indicate the continuation or the ending of a run of identical output values for the first color plane.  Similarly, the second color-plane output value may indicate the continuation or the ending of a run of identical output values for the second color plane.
14.        
Conclusion 
[00245]         The present disclosure 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 disclosure, 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.  
[00246]         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.    
[00247]         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.
[00248]         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.
[00249]         Additionally, any enumeration of elements, blocks, or steps in this specification, the drawings, or the claims is for purposes of clarity.  Thus, such enumeration should not be interpreted to require or imply that these elements, blocks, or steps adhere to a particular arrangement or are carried out in a particular order.
[00250]         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.
[00251]       
REFFERENCE SIGNS LIST
100    Printing device 
200    Computing device component
202    Processor
204    Memory
206    Input/output unit
208    System bus
300    Computing device
302    Scanning unit
304    Printing unit
306    Scan-to-host data path
308    Host-to-print data path
310    Scan-to-print data path
CLAIMS
We claim:
1.      A printing device comprising:
at least one processor;
memory; and
program instructions, stored in the memory, that upon execution by the at least one processor cause the printing device to perform operations comprising:
obtaining (i) an a x b attribute macro-cell, and (ii) a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image, wherein the a x b pixel macro-cells each contain 4 non-overlapping m x n pixel cells, wherein the a x b pixels in the a x b pixel macro-cells have respective pixel values, and wherein elements of the a x b attribute macro-cell are associated in a one-to-one fashion with respective pixels in each of the a x b pixel macro-cells;
determining 4 attribute-plane output values that respectively represent 4 non-overlapping m x n attribute cells;
based on whether the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image, determining 1 to 4 luminance-plane output values that represent the a x b pixel macro-cell of the luminance plane, wherein e is at least 1; 
determining a first color-plane output value to represent the a x b pixel macro-cell of the first color plane and a second color-plane output value to represent the a x b pixel macro-cell of the second color plane; and 
writing an interleaved representation of the 4 attribute-plane output values, the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value to a computer-readable output medium.
2.      The printing device of claim 1, wherein determining the 1 to 4 luminance-plane output values comprises:
determining that the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image; and
determining 4 luminance-plane output values that respectively represent each of the non-overlapping m x n pixel cells in the a x b pixel macro-cell of the luminance plane.
3.      The printing device of claim 2, wherein the first color-plane output value and the second color-plane output value are downsampled versions of the a x b pixel macro-cell of the first color plane and of the second color plane, respectively, that weigh pixels representing edges in the input image heavier than pixels that do not represent edges in the input image.
4.      The printing device of any of claims 1 to 3, wherein determining the 1 to 4 luminance-plane output values comprises:
determining that (i) the a x b attribute macro-cell indicates that less than e pixels in the a x b pixel macro-cells represent edges in the input image, and (ii) a range of pixel values in at least one of the 4 non-overlapping m x n pixel cells of the a x b pixel macro-cells is greater than a threshold value; and
determining 4 luminance-plane output values that respectively represent each of the non-overlapping m x n pixel cells in the a x b pixel macro-cell of the luminance plane.
5.      The printing device of claim 4, wherein the first color-plane output value and the second color-plane output value are downsampled versions of the a x b pixel macro-cell of the first color plane and of the second color plane, respectively, and wherein the downsampling does not consider whether pixels represent edges in the input image.
6.      The printing device of any of claims 1 to 5, wherein determining the 1 to 4 luminance-plane output values comprises:
determining that (i) the a x b attribute macro-cell indicates that less than e pixels in the a x b pixel macro-cells represent edges in the input image, and (ii) ranges of pixel values in each of the 4 non-overlapping m x n pixel cells for each of the a x b pixel macro-cells are less than or equal to a threshold value; and
determining 1 luminance-plane output value that represents the a x b pixel macro-cell of the luminance plane.
7.      The printing device of any of claims 1 to 6, wherein the first color-plane output value is represented in less than a x b bytes, and the second color-plane output value is represented in less than a x b bytes.
8.      The printing device of any of claims 1 to 7, wherein 4 luminance-plane output values are determined, and wherein the interleaved representation is prefaced by a composite mode indicator, and wherein opcodes are omitted for each of the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value in the interleaved representation.
9.      The printing device of any of claims 1 to 8, wherein 1 luminance-plane output value is determined, and wherein the interleaved representation is prefaced by a planar mode indicator, and wherein opcodes are included for each of the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value in the interleaved representation.
10.     A computer program causing a printing device to perform operations comprising:
obtaining (i) an a x b attribute macro-cell, and (ii) a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image, wherein the a x b pixel macro-cells each contain 4 non-overlapping m x n pixel cells, wherein the a x b pixels in the a x b pixel macro-cells have respective pixel values, and wherein elements of the a x b attribute macro-cell are associated in a one-to-one fashion with respective pixels in each of the a x b pixel macro-cells;
determining 4 attribute-plane output values that respectively represent 4 non-overlapping m x n attribute cells;
based on whether the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image, determining 1 to 4 luminance-plane output values that represent the a x b pixel macro-cell of the luminance plane, wherein e is at least 1; 
determining a first color-plane output value to represent the a x b pixel macro-cell of the first color plane and a second color-plane output value to represent the a x b pixel macro-cell of the second color plane; and 
writing an interleaved representation of the 4 attribute-plane output values, the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value to a computer-readable output medium.
11.     A method comprising:
obtaining, by a printing device, (i) an a x b attribute macro-cell, and (ii) a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image, wherein the a x b pixel macro-cells each contain 4 non-overlapping m x n pixel cells, wherein the a x b pixels in the a x b pixel macro-cells have respective pixel values, and wherein elements of the a x b attribute macro-cell are associated in a one-to-one fashion with respective pixels in each of the a x b pixel macro-cells;
determining, by the printing device, 4 attribute-plane output values that respectively represent the 4 non-overlapping m x n attribute cells;
based at least partially on whether the a x b attribute macro-cell indicates that at least e pixels in the a x b pixel macro-cells represent edges in the input image, determining, by the printing device, 1 to 4 luminance-plane output values that represent the a x b pixel macro-cell of the luminance plane, wherein e is at least 1; 
determining, by the printing device, a first color-plane output value to represent the a x b pixel macro-cell of the first color plane and a second color-plane output value to represent the a x b pixel macro-cell of the second color plane; and 
writing, by the printing device, an interleaved representation of the 4 attribute-plane output values, the 1 to 4 luminance-plane output values, the first color-plane output value, and the second color-plane output value to a computer-readable output medium.
1. Abstract
PROBLEM TO BE SOLVED
To provide a technique for a cell-based compression with edge detection and interleaved encoding.
2. SOLUTION
An example embodiment may involve obtaining (i) an a x b attribute macro-cell, and (ii) a x b pixel macro-cells for each of a luminance plane, a first color plane, and a second color plane of an input image.  The a x b pixel macro-cells may each contain 4 non-overlapping m x n pixel cells.  The example embodiment may also involve determining 4 attribute-plane output values that represent the 4 non-overlapping m x n attribute cells, 1 to 4 luminance-plane output values that represent the a x b pixel macro-cell of the luminance plane, a first color-plane output value to represent the a x b pixel macro-cell of the first color plane, and a second color-plane output value to represent the a x b pixel macro-cell of the second color plane.  The example embodiment may further involve writing an interleaved representation of the output values to a computer-readable output medium.
3. Representative Drawing: Fig. 1
2016144210.tif 000044
2016144210.tif 000045
2016144210.tif 000046
2016144210.tif 000047
2016144210.tif 000048
2016144210.tif 000049
2016144210.tif 000050
2016144210.tif 000051
2016144210.tif 000052
2016144210.tif 000053
2016144210.tif 000054
2016144210.tif 000055
2016144210.tif 000056
2016144210.tif 000057
2016144210.tif 000058