(57)【要約】【課題】デジタル画像カラープレーン圧縮のための技術を提供する。【解決手段】例示の実施形態は、入力画像からのａ×ｂ画素マクロセルの取得を含んでもよい。前記ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含んでもよい。前記ａ×ｂ画素マクロセルの前記ａ×ｂ画素はそれぞれの色値を有し、各オブジェクトタイプタグに関連付けられてもよい。前記例示の実施形態はまた、（ｉ）前記ａ×ｂ画素マクロセルを全体で圧縮、又は（２）前記４つの非オーバーラップｍ×ｎ画素セルの各々を別々に圧縮することにより、前記ａ×ｂ画素マクロセルを圧縮のいずれかの圧縮技術の選択を含んでもよい。前記例示の実施形態はさらに、前記選択された圧縮技術に従った前記ａ×ｂ画素マクロセルの圧縮、および前記圧縮されたａ×ｂ画素マクロセルの表現の、コンピュータ読み取り可能な出力媒体への書き込みを含んでもよい。【選択図】図１
2016149762.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティング・デバイスであって、
少なくとも１つの処理部と、
メモリと、
前記メモリに格納され、前記少なくとも１つの処理部による実行に応じて、前記コンピューティング・デバイスに操作を実行させるプログラム命令と、
を備え、
前記操作は、
入力画像からａ×ｂ画素マクロセルを取得する工程であって、前記ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含み、前記ａ×ｂ画素マクロセルの前記ａ×ｂ画素は、それぞれの色値を有し、各オブジェクトタイプタグに関連付けられている工程と、
前記各色値および前記各オブジェクトタイプタグに基づいて、（１）前記ａ×ｂ画素マクロセルを全体で圧縮、又は（２）前記４つの非オーバーラップｍ×ｎ画素セルの各々を別々に圧縮することにより前記ａ×ｂ画素マクロセルを圧縮のいずれかの圧縮技術を選択する工程と、
前記選択された圧縮技術に従って前記ａ×ｂ画素マクロセルを圧縮する工程と、
前記圧縮されたａ×ｂ画素マクロセルの表現をコンピュータ読み取り可能な出力媒体に書き込む工程と、
を含むコンピューティング・デバイス。
【請求項２】
請求項１に記載のコンピューティング・デバイスであって、
前記選択された圧縮技術は、前記ａ×ｂ画素マクロセルを全体で圧縮し、前記ａ×ｂ画素マクロセルを全体で圧縮する工程は、
前記ａ×ｂ画素マクロセルをダウンサンプリングされたｍ×ｎ画素セルにダウンサンプリングする工程と、
前記ダウンサンプリングされたｍ×ｎ画素セルを非可逆で圧縮する工程と、
を含むコンピューティング・デバイス。
【請求項３】
請求項２に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値を超えることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素がそれぞれ前記同一のオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記ａ×ｂ画素の前記各色値が少なくともｄ色（ｄは少なくとも２である。）を含むことを決定する工程と、
（４）前記ａ×ｂ画素マクロセルを全体で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項４】
請求項２又は３に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値以内であることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記ａ×ｂ画素の前記各色値が少なくともｄ色（ｄは少なくとも２である。）を含むことを決定する工程と、
（４）前記ａ×ｂ画素マクロセルを全体で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項５】
請求項２乃至４のいずれか１項に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値以内であることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素がそれぞれ同一のオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記ａ×ｂ画素の前記各色値が複数の色を含むことを決定する工程と、
（４）前記ａ×ｂ画素マクロセルを全体で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項６】
請求項１乃至５のいずれか１項に記載のコンピューティング・デバイスであって、
前記選択された圧縮技術は、前記４つの非オーバーラップｍ×ｎ画素セルの１以上のｍ×ｎ画素セルを別々に可逆で圧縮する方法。
【請求項７】
請求項６に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値を超えることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素がそれぞれ前記同一のオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記１以上のｍ×ｎ画素セルの各々に対する前記各色値がｄ未満（ｄは少なくとも２である。）の色を含むことを決定する工程と、
（４）前記１以上のｍ×ｎ画素セルの各々を別々に可逆で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項８】
請求項６又は７に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値以内であることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記１以上のｍ×ｎ画素セルの各々に対する前記各色値がｄ未満（ｄは少なくとも２である。）の色を含むことを決定する工程と、
（４）前記１以上のｍ×ｎ画素セルの各々を別々に可逆で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項９】
請求項６乃至８のいずれか１項に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値を超えることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記１以上のｍ×ｎ画素セルの各々に対する前記各色値がｄ未満（ｄは少なくとも２である。）の色を含むことを決定する工程と、
（４）前記１以上のｍ×ｎ画素セルの各々を別々に可逆で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項１０】
請求項６乃至９のいずれか１項に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値以内であることを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素が同一のオブジェクトタイプを表すことを示すことを決定する工程と、
（３）前記ａ×ｂ画素の前記各色値がそれぞれ同一の色値を表すことを決定する工程と、
（４）前記４つの非オーバーラップｍ×ｎ画素セルの各々を別々に可逆で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項１１】
請求項１乃至１０のいずれか１項に記載のコンピューティング・デバイスであって、
前記選択された圧縮技術は、前記４つの非オーバーラップｍ×ｎ画素セルの１以上のｍ×ｎ画素セルを別々に非可逆で圧縮する方法。
【請求項１２】
請求項１１に記載のコンピューティング・デバイスであって、
前記圧縮技術を選択する工程は、
（１）前記ａ×ｂ画素の前記各色値の範囲が所定の非ゼロ閾値を超える、又は前記ａ×ｂ画素に対する前記各オブジェクトタイプタグが、前記ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことを決定する工程と、
（２）前記ａ×ｂ画素に対する前記各色値が５未満の色を含むことを決定する工程と、
（３）前記１以上のｍ×ｎ画素セルの各々に対する前記各色値が少なくともｄ色（ｄは少なくとも２である。）を含むことを決定する工程と、
（４）前記１以上のｍ×ｎ画素セルの各々を別々に非可逆で圧縮することを選択する工程と、
を含むコンピューティング・デバイス。
【請求項１３】
請求項１乃至１２のいずれか１項に記載のコンピューティング・デバイスであって、さらに、
前記ａ×ｂ画素マクロセルを圧縮するために利用された前記圧縮技術を反転することにより前記圧縮されたａ×ｂ画素マクロセルを解凍する工程であって、前記圧縮されたａ×ｂ画素マクロセルを解凍する工程は、結果として第２のａ×ｂ画素マクロセルになる工程を含み、前記第２のａ×ｂ画素マクロセルの画素値は、前記ａ×ｂ画素マクロセルの前記画素値と同一又は近似のどちらかである工程とを含むコンピューティング・デバイス。
【請求項１４】
請求項１乃至１３のいずれか１項に記載のコンピューティング・デバイスであって、さらに、
前記入力画像から第２のａ×ｂ画素マクロセルおよび第３のａ×ｂ画素マクロセルを取得する工程であって、前記第２および第３のａ×ｂ画素マクロセルは、それぞれ４つの非オーバーラップｍ×ｎ画素セルを含み、前記第２および第３のａ×ｂ画素マクロセルの各々の前記画素は、それぞれ色値も有し、前記各オブジェクトタイプタグにも関連付けられている工程と、
前記第２のａ×ｂ画素マクロセルの前記４つの非オーバーラップｍ×ｎ画素セルおよび前記第３のａ×ｂ画素マクロセルの前記４つの非オーバーラップｍ×ｎ画素セルの各々を互いに別々に、そして前記ａ×ｂ画素マクロセルの前記４つの非オーバーラップｍ×ｎ画素セルから圧縮することにより前記第２および第３のａ×ｂ画素マクロセルの各々を圧縮するための圧縮技術を選択する工程と、
前記第２のａ×ｂ画素マクロセルの前記４つの非オーバーラップｍ×ｎ画素セルおよび前記第３のａ×ｂ画素マクロセルの前記４つの非オーバーラップｍ×ｎ画素セルの各々を互いに別々に、そして前記ａ×ｂ画素マクロセルの前記４つの非オーバーラップｍ×ｎ画素セルから圧縮する工程と、
前記圧縮された第２のａ×ｂ画素マクロセルおよび前記圧縮された第３のａ×ｂ画素マクロセルの表現を前記コンピュータ読み取り可能な出力媒体に書き込む工程と、
を含むコンピューティング・デバイス。
【請求項１５】
請求項１乃至１４のいずれか１項に記載のコンピューティング・デバイスであって、
前記選択された圧縮技術は、前記４つの非オーバーラップｍ×ｎ画素セルの各々を別々に可逆で圧縮するコンピューティング・デバイス。
【請求項１６】
コンピュータプログラムであって、
入力画像からａ×ｂ画素マクロセルを取得する工程であって、
前記ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含み、前記ａ×ｂ画素マクロセルの前記ａ×ｂ画素は、それぞれの色値を有し、各オブジェクトタイプタグに関連付けられている工程と、
前記各色値および前記各オブジェクトタイプタグに基づいて、（１）前記ａ×ｂ画素マクロセルを全体で圧縮、又は（２）前記４つの非オーバーラップｍ×ｎ画素セルの各々を別々に圧縮することにより前記ａ×ｂ画素マクロセルを圧縮のいずれかの圧縮技術を選択する工程と、
前記選択された圧縮技術に従って前記ａ×ｂ画素マクロセルを圧縮する工程と、
前記圧縮されたａ×ｂ画素マクロセルの表現をコンピュータ読み取り可能な出力媒体に書き込む工程と、
を前記コンピューティング・デバイスに実行させるコンピュータプログラム。
【請求項１７】
方法であって、
コンピューティング・デバイスによって、入力画像からａ×ｂ画素マクロセルを取得する工程であって、前記ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含み、前記ａ×ｂ画素マクロセルの前記ａ×ｂ画素は、それぞれの色値を有し、各オブジェクトタイプタグに関連付けられている工程と、
前記各色値および前記各オブジェクトタイプタグに基づいて、前記コンピューティング・デバイスによって（１）前記ａ×ｂ画素マクロセルを全体で圧縮、又は（２）前記４つの非オーバーラップｍ×ｎ画素セルのそれぞれを別々に圧縮することにより前記ａ×ｂ画素マクロセルを圧縮、のどちらかの圧縮技術を選択する工程と、
前記コンピューティング・デバイスによって、前記選択された圧縮技術に従って前記ａ×ｂ画素マクロセルを圧縮する工程と、
前記コンピューティング・デバイスによって、前記圧縮されたａ×ｂ画素マクロセルの表現をコンピュータ読み取り可能な出力媒体に書き込む工程と、
を備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル画像の圧縮技術に関する。
【背景技術】
【０００２】
近年、さまざまな種類の印刷デバイスが業務用および民生用の両方で普及してきている。従来の白黒のプリンタに加え、カラープリンタ、スキャナ、コピー機、ファックス機、およびその他の装置も今日では一般的である。これらの操作の二つ以上に対応している複合機（ＭＦＰ）もまた広く普及している。これらの装置が普及するにつれて、より精緻で複雑な文書処理に利用されるようになっている。
【発明の概要】
【０００３】
第１の例示の実施形態は、入力画像からのｍ×ｎ画素セルの取得を含んでもよい。前記入力画像は、ｍ×ｎ画素より多くの画素を含んでもよく、前記ｍ×ｎ画素セルの前記ｍ×ｎ画素の各々は、少なくとも１つの色値に関連付けられてもよい。前記第１の例示の実施形態は、おそらく前記ｍ×ｎ画素セルに基づいた、ｍ×ｎ属性セルの取得も含んでもよい。前記ｍ×ｎ属性セルの構成要素は、前記ｍ×ｎ画素セルのそれぞれの画素に１対１で関連付けられてもよく、前記構成要素は、これらの関連付けられた画素に関連しているそれぞれの制御データを識別してもよい。前記第１の例示の実施形態はさらに、非可逆での前記ｍ×ｎ画素セル、および可逆での前記ｍ×ｎ属性セルの圧縮を含んでもよい。前記ｍ×ｎ画素セルの圧縮は、前記ｍ×ｎ属性セルの少なくとも一部に基づいてもよい。前記第１の例示の実施形態は加えて、前記圧縮されたｍ×ｎ画素セル、および前記圧縮されたｍ×ｎ属性セルのインターリーブ表現の出力媒体への書き込みを含んでもよい。
【０００４】
第２の例示の実施形態は、入力画像からのａ×ｂ画素マクロセルの取得を含んでもよい。前記ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含んでもよく、前記ａ×ｂ画素マクロセルの前記ａ×ｂ画素は、それぞれの色値を持ち、各オブジェクトタイプタグに関連付けられている。前記第２の例示の実施形態はまた、おそらく前記各色値および前記各オブジェクトタイプタグに基づいた、下記いずれかの圧縮技術の選択を含んでもよい。（１）前記ａ×ｂ画素マクロセル全体での圧縮、又は（２）前記４つの非オーバーラップｍ×ｎ画素セルごとに別々に圧縮する、前記ａ×ｂ画素マクロセルの圧縮。前記第２の例示の実施形態はさらに、前記選択された圧縮技術に従った、前記ａ×ｂ画素マクロセルの圧縮を含んでもよい。前記第２の例示の実施形態は加えて、前記圧縮されたａ×ｂ画素マクロセルの表現の、コンピュータ読み取り可能な出力媒体への書き込みを含んでもよい。
【０００５】
第３の例示の実施形態は、１以上のカラープレーン、およびａ×ｂ属性マクロセルを備えた入力画像からのａ×ｂ画素マクロセルの取得を含んでもよい。前記ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含み、前記ａ×ｂ属性マクロセルは、４つの非オーバーラップｍ×ｎ属性セルを含んでもよい。前記ａ×ｂ画素マクロセルの前記ａ×ｂ画素は、それぞれ色値に関連付けられてもよく、前記ａ×ｂ属性マクロセルの構成要素は、前記ａ×ｂ画素マクロセルのそれぞれの画素に、１対１で関連付けられてもよい。前記第３の例示の実施形態はまた、前記４つの非オーバーラップｍ×ｎ属性セルにそれぞれ関連付けられている、４つの属性プレーン出力値の決定を含んでもよい。前記第３の例示の実施形態はさらに、前記非オーバーラップｍ×ｎ画素セルに対する、１乃至４のカラープレーン出力値の決定を含んでもよい。前記第３の例示の実施形態は加えて、前記４つの属性プレーン出力値、および前記決定されたカラープレーン出力値のインターリーブ表現の、コンピュータ読み取り可能な出力媒体への書き込みを含んでもよい。
【０００６】
第４の例示の実施形態は、非一時的でコンピュータ読み取り可能な記憶媒体を含んでもよく、コンピューティング・デバイスによる実行に応じて、前記コンピューティング・デバイスに前記第１、第２、および／または第３の例示の実施形態に従った操作を行わせるプログラム命令を前記記憶媒体に格納している。
【０００７】
第５の例示の実施形態は、少なくとも処理部とデータ記憶部を有するコンピューティング・デバイスを含んでもよい。前記データ記憶部は、前記処理部により実行される場合、前記コンピューティング・デバイスに前記第１、第２、および／または第３の例示の実施形態に従った操作を行わせるプログラム命令を含んでもよい。
【０００８】
他の態様、有利な点、および代替案と同様、これらのことは、必要に応じて添付図面を参照して以下の詳細な説明を読むことによって当業者にとって明白になるであろう。さらに、本明細書における当該概要および他のセクションで提供されている説明は、請求されている主題を限定のためでなく例として示すことを意図していることを理解されたい。
【図面の簡単な説明】
【０００９】
【図１】例示の実施形態に係る、印刷デバイスを示す。
【図２】例示の実施形態に係る、印刷デバイスのコンピューティング構成要素をブロック図にて示す。
【図３】例示の実施形態に係る、印刷デバイスを含む各種データパスをブロック図にて示す。
【図４】例示の実施形態に係る、電子文書に含んでもよい画像を示す。
【図５】例示の実施形態に係る、属性配列を示す。
【図６】例示の実施形態に係る、文書処理パイプラインを示す。
【図７】例示の実施形態に係る、４つのセルを含むマクロセルを示す。
【図８】例示の実施形態に係る、カラープレーン決定木を示す。
【図９】例示の実施形態に係る、属性プレーン決定木を示す。
【図１０】例示の実施形態に係る、インターリーブ符号化用の疑似コードを示す。
【図１１Ａ】例示の実施形態に係る、４つのプレーンのセルを示す。
【図１１Ｂ】例示の実施形態に係る、出力媒体にインターリーブされた図１１Ａのセルを示す。
【図１２Ａ】例示の実施形態に係る、４つのプレーンのセルを示す。
【図１２Ｂ】例示の実施形態に係る、出力媒体にインターリーブされた図１２Ａのセルを示す。
【図１３】例示の実施形態に係る、フローチャートを示す。
【図１４】例示の実施形態に係る、別のフローチャートを示す。
【図１５】例示の実施形態に係るさらに別のフローチャートを示す。
【発明を実施するための形態】
【００１０】
本明細書において方法とシステムの例を記述する。さらに他の例示的な実施形態又は特徴を利用してもよく、また本明細書において提示されている主題の範囲から逸脱することなく、その他の変更がなされてもよい。以下の詳細な説明において、本明細書の一部を構成する添付図面を参照する。
【００１１】
本明細書において記載されている例示的な実施形態は限定することを意図するものではない。従って、本明細書において全般的に記載され、そして図面に示されているように、本開示の諸態様は、様々に異なる構成に配置し、置き換え、結合し、分離し、および設計することが可能である、そしてそれらの全てが本明細書において明瞭に熟慮されている。
［１．概要］
【００１２】
印刷技術は、白黒画像のみを生成する簡単なドットマトリクスベースの出力デバイスから高解像度のカラー画像を生成することができる今日の進歩したレーザーベースの印刷デバイスへと過去３０年以上にわたって発展してきた。それと共に、最近の印刷デバイスは、また、コピー機、スキャナ、およびファックス機として機能してもよい。そうするため、印刷デバイスは、印刷し又はファックスするために待ちマトリクスに入れられた、またはスキャンされた多くの電子文書を格納することができてもよい。従って、多くの印刷デバイスは、例えば、一つ以上の処理部、データ記憶部、および入出力インターフェースを含んでもよいコンピューティング・デバイスの特定の形態である。
【００１３】
住宅、企業又は別の種類の場所で使用されるかどうかにかかわらず、印刷デバイスは、他のいろいろなコンピューティング・デバイスと通信可能に接続可能な共有のリソースであってもよい。従って、状況によっては、多くのコンピューティング・デバイスが印刷のために電子文書を印刷デバイスに送信する場合があるので、印刷デバイスに対する格納要求はかなり高い場合がある。一般的には、印刷デバイスは、早着順に一度に一つの電子文書を印刷、コピー、ファックス、および／またはスキャンすることがよくある。従って、印刷デバイスは、ともすれば、処理されるのを待っている多数の電子文書を格納する場合がある。加えて、背景画像やロゴマークを含むオーバーレイ文書のような電子文書は、これらの電子文書が複数の印刷ジョブに適応されるにつれて、印刷デバイスに無制限に格納される場合がある。
【００１４】
データの記憶装置（例えば、ランダム・アクセス・メモリ（ＲＡＭ）、固体メモリ、ハードドライブメモリ、および／またはフラッシュメモリなどのメモリ）のコストは高価である可能性があるので、印刷デバイスのデータ記憶の要求量を低減するために、格納された電子文書を圧縮することは有益であろう。それと共に、電子文書によっては、印刷デバイスからコンピューティング・デバイスへ、および／またはコンピューティング・デバイスから印刷デバイスへ転送される場合があるので、当該電子文書を圧縮することにより、より早く転送することができ、しかもネットワーク容量の使用をより少なくすることができる。
【００１５】
さらに、印刷ジョブは多量な場合がある（例えば、印刷ジョブは、何百ページも含む一つ以上の電子文書を含む場合がある）ので、順番を待っている印刷ジョブを圧縮することにより、各ジョブが印刷される前の短期格納スペースを節約する。これに加えて、ユーザは、後日印刷するために印刷ジョブを長期の記憶装置に保管したい場合がある。従って、印刷ジョブを圧縮することにより、より多くの印刷ジョブを保管できる可能性がある。さらに、大量の印刷ジョブを長期の記憶装置に格納したり検索する動作は手間がかかる可能性があるが、前記印刷ジョブを圧縮して大きさを小さくすることにより早めることが可能である。
［２．印刷デバイスの例］
【００１６】
図１は例示の印刷デバイス１００を示す。印刷デバイス１００は、部分的におよび／または全体的に格納されている電子文書を各種の物理的出力媒体に印刷するよう構成してもよい。当該出力媒体は、いろいろな大きさと種類の紙、オーバーヘッドプロジェクタ用透明フィルムなどを含むが、これらに限定はされない。印刷デバイス１００は、同義的に「プリンタ」と呼んでもよい。
【００１７】
印刷デバイス１００は、パーソナルコンピュータ、サーバーデバイス、プリンタサーバー等のコンピューティング・デバイスに対するローカル周辺装置としての働きをしてもよい。この場合、印刷デバイス１００は、シリアルポートケーブル、パラレルポートケーブル、ユニバーサルシリアルバス（ＵＳＢ）ケーブル、ファイヤーワイヤー（ＩＥＥＥ１３９４）ケーブル、又は高解像度マルチメディアインターフェース（ＨＤＭＩ）ケーブル等のケーブルによってコンピューティング・デバイスに接続してもよい。このように、コンピューティング・デバイスは、印刷デバイス１００に対して電子文書の供給源としての働きをしてもよい。
【００１８】
一方、印刷デバイス１００は、イーサネット又は８０２．１１（Ｗｉｆｉ）インターフェース等の有線又は無線のネットワークインターフェースを含んでもよい。そのように配置されて、印刷デバイス１００は、ネットワークを介して印刷デバイス１００と通信可能な任意の数のコンピューティング・デバイスに対する印刷デバイスとしての働きをしてもよい。実施形態によっては、印刷デバイス１００は、ローカル周辺装置およびネットワーク接続されたプリンタの両方としての働きを同時にしてもよい。印刷デバイス１００を使用するために、コンピューティング・デバイスは、一つ以上のプリンタドライバーを組み込んでもよい。当該プリンタドライバーは、印刷される電子文書を、コンピューティング・デバイスに格納された各種のローカル表現から印刷デバイス１００によりサポートされる一つ以上の表現に変換するソフトウェアコンポーネントを含んでもよい。
【００１９】
それでも、印刷デバイス１００は、非一般型のコンピューティング・デバイスとみなしてもよく、印刷関連および非印刷関連のタスクの両方を実行してもよい。例えば、印刷デバイス１００は、また、コピー機、ファックス機、およびスキャナの機能を含んでもよい。実施形態によっては、印刷デバイス１００は、コピー機および／またはファックス機の機能を促進するためスキャナ部を用いてもよい。例えば、印刷デバイス１００は、物理的文書をスキャンして電子フォーマットにし、次に得られた電子文書を印刷してコピーを提供し、および／または電話インターフェースを介して得られた電子文書を送信してファックス操作を提供してもよい。加えて、印刷デバイス１００は、電話インターフェースを介してファクスされた電子文書を受信した後、この電子文書の表現を圧縮し、格納することができてもよい。
【００２０】
各種機能に対応するために、印刷デバイス１００は、原稿の給紙／排紙トレイ１０２、用紙保管部１０４、ユーザインターフェース１０６、スキャニング要素１０８、および筐体１１０を含んでもよい。印刷デバイスはさまざまな形態を採り得ることを理解されるべきである。従って、印刷デバイス１００は、図１に示された構成要素よりも多い又は少ない構成要素、および／または図１に示された構成要素にくらべて異なった仕方で配置された構成要素を含んでもよい。
【００２１】
原稿の給紙／排紙トレイ１０２は、スキャンされ、コピーされ、又はファックスされる物理的文書（例えば、一枚以上の紙の積み重ねた山）を保持してもよい。原稿の給紙／排紙トレイ１０２は、印刷デバイス１００による処理のために、印刷デバイス１００が、人手を介することなく、複数枚の物理的文書を自動的に送り出すことが可能であってもよい。原稿の給紙／排紙トレイ１０２は、また、印刷デバイス１００によって処理された物理的文書を保持するための一つ以上の分離した排紙トレイを含んでもよい。これらには、印刷デバイス１００によりスキャンされ、コピーされ又はファックスされた物理的文書と共に、例えば、印刷デバイス１００のファックスおよび／またはコピー機能により生成された物理的文書も含んでもよい。
【００２２】
用紙保管部１０４は、各種の物理的媒体のためのトレイおよび／または給紙要素を含んでもよい。例えば、用紙保管部１０４は、８．５×１１インチ用紙、Ａ４用紙、レターヘッドのある用紙、封筒等のための別個のトレイを含んでもよい。物理的媒体を生成する（例えば、印刷、コピー、および／またはファックスの受信）ことに係わる印刷デバイス１００のあらゆる機能のために、用紙保管部１０４は、前記物理的媒体を供給してもよい。
【００２３】
ユーザインターフェース１０６は、ユーザからの入力を受け取ることおよびユーザに出力を提供すること等、印刷デバイス１００と人又は人以外のユーザとの情報交換を促進してもよい。したがって、ユーザインターフェース１０６は、キーパッド、キーボード、タッチパネル又は存在感知パネル、ジョイスティック、マイクロホン、静止カメラおよび／またはビデオカメラ等、入力構成要素を含んでもよい。ユーザインターフェース１０６は、また、（例えば、存在感知パネルと組み合わせてもよい）表示画面、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ベースのディスプレイ、デジタル光処理（ＤＬＰ（登録商標））技術を使用したディスプレイ、電球、および／または既知又は今後開発される一つ以上の他の類似なデバイス等、一つ以上の出力構成要素を含んでもよい。ユーザインターフェース１０６は、また、スピーカー、スピーカージャック、オーディオ出力ポート、オーディオ出力デバイス、イヤホンおよび／または既知又は今後開発される他の類似のデバイスを介して可聴出力を生成することができるように構成してもよい。
【００２４】
スキャニング要素１０８は、その下で、可動光源がガラスパネルの上に置かれた物理的媒体をスキャンするよう動作するガラスパネルであってもよい。あるいは、ガラスパネルの下のデジタルカメラが、物理的媒体の写真を撮ることにより、ガラスパネルの上に置かれた物理的媒体を「スキャン」してもよい。スキャンされた物理的媒体の画像は、印刷デバイス１００に関連付けられたデータ記憶部に格納されてもよい。
【００２５】
筐体１１０は、原稿の給紙／排紙トレイ１０２、用紙保管部１０４、ユーザインターフェース１０６、およびスキャニング要素１０８等印刷デバイス１００の各種構成要素を収容しおよび／または相互に接続する物理的ハウジングを含んでもよい。それと共に、筐体１１０は、図１に示されていない他の構成要素を収容してもよい。例えば、筐体１１０は、一つ以上のトナーカートリッジ、液体インクジェット、ベルト、ローラー、および／または電源を収容してもよい。さらに、筐体１１０は、有線および／または無線ネットワークインターフェース、電話インターフェース（例えば、ＲＪ４５ジャック）、ＵＳＢインターフェース、ＢＬＵＥＴＯＯＴＨ（登録商標）インターフェース、カード読取部のポート等の通信インターフェースを含んでもよい。
【００２６】
さらに、印刷デバイス１００は、汎用のおよび／または特別に設計されたコンピューティング・デバイス構成要素を搭載する場合があるので、筐体１１０は、また、当該構成要素のいくつか又は全てを収容してもよい。その点について、図２は、印刷デバイス１００に含まれ得るコンピューティング・デバイス構成要素（例えば、コンピューティング・デバイスの機能要素）の例示の実施形態２００を示す。
【００２７】
コンピューティング・デバイス構成要素２００は、処理部２０２、メモリ２０４、および入出力部２０６を含み、これらすべてはシステムバス２０８、又は類似の仕組みにより接続されてもよい。処理部２０２は、一つ以上の汎用プロセッサ等の一つ以上の中央処理装置（ＣＰＵ）および／または一つ以上の専用プロセッサ（例えば、特定用途向け集積回路（ＡＳＩＣ）又はデジタル信号プロセッサ（ＤＳＰ）等）を含んでもよい。
【００２８】
次に、メモリ２０４は、揮発性および／または不揮発性データ記憶部を含んでもよく、処理部２０２に全体的に又は部分的に統合され得る。メモリ２０４は、処理部２０２により実行可能なプログラム命令、および本明細書に記載されている各種の方法、プロセス、又は機能を実行するために当該命令によって操作されるデータを格納してもよい。あるいは、当該方法、プロセス、又は操作は、ハードウェア、ファームウェア、および／またはハードウェア、ファームウェア、およびソフトウェアの任意の組み合わせによって規定することができる。従って、メモリ２０４は、一つ以上のプロセッサにより実行される際、本明細書又は添付図面で開示された任意の方法、プロセスあるいは機能を印刷デバイス１００に実行させるプログラム命令を格納している、有形で非一時的でコンピュータ読み取り可能な媒体を含んでもよい。
【００２９】
メモリ２０４は、また、後で処理される（例えば、印刷される）場合がある圧縮電子文書および非圧縮電子文書を格納するように構成してもよい。従って、メモリ２０４は、これらの電子文書用の出力媒体として機能してもよい。
【００３０】
入出力部２０６は、ユーザインターフェース１０６に関連して記載された操作および／または構成要素のいずれかを含んでもよい。従って、入出力部２０６は、処理部２０２の操作を構成および／または制御するように機能してもよい。入出力部２０６は、また、処理部２０２により実行される操作に基づいたアウトプットを提供してもよい。
【００３１】
これら例示の印刷デバイスは、例証目的に提供される。上記の例に加えおよび／または代わり、プリンタとコンピュータ技術の他のコンビネーションおよび／またはサブコンビネーションは、いくつかある可能性の中でも特に、本明細書中の実施形態の要旨を逸脱しない範囲で存在してもよい。
【００３２】
図３は、印刷デバイス１００により処理される電子文書の表現が通る場合があるいくつかの考えられるデータパスを示す。図３では、印刷デバイス１００は、スキャナ部３０２および印刷部３０４を含んでもよいと仮定されている。これらの各部の制御は、ハードウェア、ファームウェア、ソフトウェア、又はハードウェア、ファームウェアおよび／またはソフトウェアの任意の組合せで実装してもよい。加えて、スキャナ部３０２および印刷部３０４はそれぞれ、コンピューティング・デバイス３００、およびおそらく同様に他のコンピューティング・デバイスとも、通信してもよい。場合によっては、印刷デバイス１００にサポートされたデータパスは、「パイプライン」と呼んでもよい。
【００３３】
スキャン〜印刷データパス３１０は、スキャナ部３０２および印刷部３０４によりサポートされてもよい。スキャン〜印刷データパス３１０は、例えば、ユーザが物理的文書をコピーするため、印刷デバイス１００に指示する場合に利用してもよい。この指示に従い、スキャナ部３０２は、物理的文書を電子文書にスキャンし、電子文書をスキャン〜印刷データパス３１０を介して、印刷部３０４に送信してもよい。スキャン〜印刷データパス３１０の使用には、印刷デバイス１００のデータ記憶部内の電子文書（おそらく圧縮された形式）のいくつか、または全ての、少なくとも一時的な格納を含んでもよい。その後、印刷部３０４は、電子文書を物理的媒体（例えば、１枚以上の用紙）に印刷してもよい。
【００３４】
スキャン〜ホストデータパス３０６もまた、スキャナ部３０２およびコンピューティング・デバイス３００によりサポートされてもよい。スキャン〜ホストデータパス３０６は、例えば、ユーザが物理的文書のスキャンを印刷デバイス１００に指示する場合に利用してもよい。ユーザは、また、得られた電子文書の表現をコンピューティング・デバイス３００に送信するように印刷デバイス１００に指示してもよいし、又は、印刷デバイス１００を電子文書をコンピューティング・デバイス３００に自動的に送信するように、予め構成してもよい。よって、この指示に従い、スキャナ部３０２は、物理的文書を電子文書にスキャンし、得られた電子文書をスキャン〜ホストデータパス３０６を介して、コンピューティング・デバイス３００に送信してもよい。スキャン〜ホストデータパス３０６の使用には、印刷デバイス１００のデータ記憶部内の電子文書のいくつか、又は全ての、少なくとも一時的な格納（おそらく圧縮された形式で）と、得られた電子文書の表現の、コンピューティング・デバイス３００への送信を含んでもよい。
【００３５】
ホスト〜印刷データパス３０８は、コンピューティング・デバイス３００および印刷部３０４によりサポートされてもよい。ホスト〜印刷データパス３０８は、例えば、ユーザが電子文書の印刷デバイス１００での印刷を、コンピューティング・デバイス３００に指示する場合、利用してもよい。この指示に従い、コンピューティング・デバイス３００は、電子文書の表現を印刷部３０４に送信してもよい。印刷デバイス１００は、印刷部３０４を介して、電子文書を物理的媒体に印刷してもよい。電子文書のいくつか、又は全ては、電子文書の印刷前および／または間に、印刷デバイス１００のデータ記憶部に（おそらく圧縮された形式で）格納してもよい。
【００３６】
おそらく印刷デバイス１００によりサポートされた他のデータパスと同様、上述のデータパスの少なくとも１つに対して、電子文書がネットワーク、又はケーブルを通じて、格納および／または送信を要求してもよいのは明らかだ。電子文書の格納および送信両方の効率は、これらの格納および／または送信用の電子文書の圧縮により、向上させることができる。例えば、電子文書を平均して元のサイズの４分の１に圧縮できれば、約４倍の電子文書を固定量のデータ記憶部に格納することができる。さらに、ネットワーク、又はケーブルを通じた、これらの圧縮された電子文書の送信は、圧縮されていない電子文書の送信より、約４倍速くなる可能性がある。
【００３７】
過去、データパスによっては非可逆圧縮が利用されてきた一方、他のデータパス用には可逆圧縮が利用されてきたかもしれない。（非可逆圧縮技術では、データの一部を廃棄することにより、データを圧縮する一方、可逆圧縮技術では、いずれのデータも廃棄することなく、データを圧縮する。）。例えば、実装によっては、ホスト〜印刷データパス３０８は、電子文書の印刷されたバージョンにおいて、テキストと線画のはっきりしたエッジを保持するため、可逆圧縮を使用してもよい。一方、スキャン〜ホストデータパス３０６およびスキャン〜印刷データパス３１０は、グラフィカル画像を含むスキャンされた物理的文書を効率的に格納、送信するため、非可逆圧縮を使用してもよい。データパスの少なくともいくつか（およびおそらく全て）に対し、同じ又は類似の圧縮技術を使用することにより、印刷デバイス１００は、より効率的になり、そのソフトウェアおよび／またはハードウェアの実装は、簡略化されるかもしれない。
【００３８】
従って、可逆および非可逆圧縮の両方をサポートする圧縮技術が望ましい。また、同一文書内で可逆および非可逆圧縮の両方が適用可能なことが望ましい。その点について、画像の提示方法を理解することが有益であるかもしれない。
［３．画像の例］
【００３９】
画像は、画像フォーマットおよびカラーモデルに従って符号化された画素のマトリクスであってもよい。図４は、印刷デバイス１００により操作される物理的文書又は電子文書上、又は内部に含んでもよい画像４００を示す。画像４００が白黒で現れる一方、類似の特性のカラー画像もまた、印刷デバイス１００により操作されてもよい。画像４００は、他の例のうち、６００ドット毎インチ（ｄｐｉ）又は１２００ｄｐｉ等、さまざまな解像度を使用して、形成されてもよい。
【００４０】
図４から理解されるように、画像４００は各種内容を含む。例えば、画像４００は、はっきりしたエッジを持ったテキストおよび線画の両方を含む。さらに、画像４００は、フォトリアリスティックデータ（例えば、画像４００の下方右手角および上方右手角）を含むセクションと同様に、連続階調（例えば、画像４００の上方左手角）を含むセクションも含む。テキストは、画像４００のさまざまなセクションに重なっている。つまり、画像４００は、例えばパンフレット、雑誌、チラシ、又は広告のページなど、ビジネス上の印刷に利用される一般的なタイプの画像を示している。
【００４１】
可能性のある実施形態によっては、例示の画像４００のような画像の各画素は、画像グラフィックス、ベクトルグラフィックス、又はテキストという、３つの異なるオブジェクトタイプの１つとして分類してもよい。画像グラフィックスは、写真からの画像のような、フォトリアリスティック画像を含む。画像４００の下方右手角および上方右手角のフォトリアリスティックデータは、画像グラフィックスと見なしてよい。画像４００全般にわたる非テキストラインはベクトルグラフィックスと見なし、テキスト特性（例えば、「Ｅ」および「Ｒ」）はテキストと見なしてよい。
【００４２】
特定の画素のオブジェクトタイプは、電子文書のページ記述言語（ＰＤＬ）表現により、又はから、決定してもよい。ＰＤＬは、ページの実際の画素より高いレベルで印刷、又は表示されたページの外観を示す言語、文法、又は形式である。ページの画素表現は、ＰＤＬから取り出してもよい。
【００４３】
このように、電子文書は、ＰＤＬ文書によって表される１ページ以上のページを含んでもよい。これらの各ページは、ＰＤＬ文書の一部又は全て、および／または画像によって表されてもよい。ＰＤＬには多数の例があり、ポータブル・ドキュメント・フォーマット（ＰＤＦ）はその１つである。
【００４４】
統合された圧縮技術は、画像４００を含む電子文書のストレージ要求を減らすため、なお非可逆圧縮を使用して、画像４００のはっきりしたエッジおよびラインを正確に表すことができてもよい。特に、テキスト、基本的な幾何学的図形、線画のような特定の構成要素の正確な特性を保存することが望ましい。それは、これらの構成要素の軽微な歪であっても、人間の眼には不快に見えるためである。従って、これらの構成要素は、ベクトルグラフィックス又はテキストとして分類され、可逆での圧縮対象としてもよい。
【００４５】
一方、フォトリアリスティック画像、および傾きのある複雑なグラフィックスは、このような正確さがなくても見ることができる。従って、これらの構成要素は、画像グラフィックスとして分類され、非可逆での圧縮対象としてもよい。例えば、画像グラフィックスは、それぞれの非圧縮バージョンと、人間の眼に視覚的に同一又は同様に見えるような方法で圧縮してもよい。
【００４６】
さらに、画素のオブジェクトタイプ（例えば、画像グラフィックス、ベクトルグラフィックス、又はテキスト）は、画素に適用されているハーフトーン・スクリーンのタイプと同様に、画素に適用されている色変換に影響してもよい。これらの論点は、以下で詳細に説明する。
【００４７】
場合によっては、ベクトルグラフィックスおよびテキスト・オブジェクトは、類似の特性を有するように見えてもよい。実際、これら２つのカテゴリは、いくつかの実施形態に結合され、同一の方法で処理されることが可能である。しかしながら、薄色のラインのような、ベクトルグラフィックスの特定のタイプは、テキストと分けて処理した方が、よく見える。例えば、薄色のラインがテキストと同一の方法で処理されると、これらのラインのいくつかは区別が難しくなるかもしれない。結果として、ベクトルグラフィックスへの異なった色変換および／または異なったハーフトーン・スクリーンの適用により、これらのラインが保存および／または向上されるかもしれない。例えば、ベクトルグラフィックス画素用に特に選択されたハーフトーン・スクリーンは、この画素が印刷された場合に適用されるトナーとなるかもしれない。
［４．画像カラーモデルの例］
【００４８】
電子文書は、カラーモデルの番号を使用して表すことができる。従って、安定した圧縮技術は、これらのモデルのいくつか、又は全てで動作できるようにする必要がある。さらに、圧縮技術は、個別のカラーモデルに特有な前処理を含んでもよい。
【００４９】
例えば、赤緑青（ＲＧＢ）カラーモデルは、テレビ、モニター、およびコンピュータ・スクリーンのような、電子出力装置での画像表示に利用されてもよい。ＲＧＢは、赤、緑、青の光を、色のスペクトルを作り出すさまざまな方法で同時に加えた、加法混色モデルである。例えば、シアンは緑と青を混ぜて形成し、イエローは赤と緑を混ぜて形成し、マゼンタは赤と青を混ぜて形成し、白は赤、緑、青を混ぜて形成し得る。
【００５０】
ＲＧＢ画像の特定の画素は３プレーン・タプル（Ｒ、Ｇ、Ｂ）として表現され、各プレーンは０から予め定義された最大値（例えば、２５５）まで変化することができる。全てのプレーンが０の場合、結果は黒になり得る。全てのプレーンが最大値の場合、結果は最も明るく表せる白になり得る。（カラープレーンは、本明細書において、カラーチャンネルと呼んでもよい。）
【００５１】
ＲＧＢ出力は、異なった出力装置は異なった方法で同一のＲＧＢ画像を表示してもよいという点で、一般的に装置依存である。従って、場合によっては、これらの差異は人間に知覚可能かもしれない。実施形態によっては、スキャン〜ホストデータパス３０６を使用して印刷デバイス１００にスキャンされた物理的文書は、ＲＧＢカラーモデルを使用して符号化されてもよい。
【００５２】
シアン・マゼンタ・イエロー（ＣＭＹ）カラーモデルは、印刷デバイスによるカラー画像の印刷に利用してもよい。ＣＭＹは、シアン、イエロー、マゼンタを、色のスペクトルを再現するさまざまな方法で白色表面に印加する、減法混色モデルである。例えば、赤はマゼンタとイエローを混ぜて形成し、青はシアンとマゼンタを混ぜて形成し、緑はシアンとイエローを混ぜて形成し得る。従って、ＣＭＹカラーモデルは、ＲＧＢカラーモデルを補完するものと見なしてよい。
【００５３】
ＣＭＹ画像の特定の画素は３プレーン・タプル（Ｃ、Ｍ、Ｙ）として表され、各プレーンは０から予め定義された最大値まで変化することができる。全てのプレーンが０の場合、結果は白になり得る。全てのプレーンが最大値の場合、結果は黒になり得る。
【００５４】
ＲＧＢ出力と同様、ＣＭＹ出力は、異なる印刷デバイスにおける同一のＣＭＹ画像の印刷アウトプットが異なって見えるという点で、一般的に装置依存である。場合によっては、これらの差異は人間に知覚可能かもしれない。実施形態によっては、ホスト〜印刷データパス３０８および／またはスキャン〜印刷データパス３１０を使用して、印刷デバイス１００により印刷された電子文書は、ＣＭＹカラーモデルを使用して符号化されてもよい。
【００５５】
実施形態によっては、４プレーンＣＭＹＫカラーモデルも利用可能である。このＣＭＹＫの４プレーン・モデルは、キー（黒）プレーンも利用されている点を除いて、ＣＭＹカラーモデルと同様又は同一かもしれない。黒を形成する可能性のあるシアン、マゼンタ、イエローの組合せに加え、分離キー（黒）インクソースが黒の形成のために利用されてもよい。従って、ＣＭＹＫ画像の特定の画素は、４プレーン・タプル（Ｃ、Ｍ、Ｙ、Ｋ）として表され、各プレーンは０から予め定義された最大値まで変化することができる。
【００５６】
ＣＭＹＫカラーモデルを使用することで、ＣＭＹモデルと同一の色がサポートされるが、Ｋ着色剤はＣ、Ｍ、Ｙ着色剤の混合物に置き換えることができるため、一般的にインクの利用が減少する。しかしながら、例えば、異なるＣ、Ｍ、Ｙ、およびＫの組合せの混合が同一の色となり得るように、Ｋ着色剤の追加により余剰が加わるため、ＣＭＹＫカラーモデルは他のカラーモデルへ、または他のカラーモデルから、常に都合良く変換できるわけではないかもしれない。実施形態によっては、１以上のカラーテーブルは、画素をＣＭＹモデルからＣＭＹＫモデルへ、および／または他のカラーモデルのペア間で変換するために利用されてもよい。
【００５７】
追加のカラーモデルはグレーで、グレースケールとも呼ばれ、白黒画像の表現に利用してもよい。ＲＧＢおよびＣＭＹ／ＣＭＹＫカラーモデルと異なり、グレーカラーモデルの各画素は、画素の強度を符号化するシングルプレーン（Ｋ）を使用して表される。グレープレーンにより利用される値は、黒を表す０から、白を表す予め定義された最大値（例えば、２５５）まで変化させることができる。実施形態によっては、印刷デバイス１００によりサポートされたデータパスの１以上は、グレーカラーモデルを使用して画像を符号化できてもよい。
【００５８】
もう１つのカラーモデルはＹＣｂＣｒである。実装によっては、このカラーモデルは、画像の代替表現として利用してもよい。具体的に言えば、Ｙプレーンは画素の明度を表し、Ｃｂ、Ｃｒプレーンはそれぞれブルー・イエロークロミナンスおよびレッド・グリーンクロミナンスを表すかもしれない。ＹＣｂＣｒカラーモデルは、ＲＧＢおよびＣＭＹカラーモデルと、明確に定義された関係を有し、比較的容易にこれらのカラーモデルのいずれかへ、またはいずれかから変換できる。
【００５９】
ＹＣｂＣｒカラーモデルの追加的な利点は、ＹＣｂＣｒカラーモデルを使用して符号化された画像の圧縮は、ＲＧＢ又はＣＭＹ／ＣＭＹＫカラーモデルで符号化された画像の圧縮より効率的な傾向にあることである。具体的に言えば、人間の眼は、画像の高周波（例えば、急変する）クロミナンス情報を検出することが苦手である。従って、ＹＣｂＣｒカラーモデルを使用して符号化された画像は、Ｃｂ、Ｃｒプレーンの高周波成分を無視することにより、この情報を利用することができる。そのため、特定のカラーモデルで符号化された画像は、圧縮パフォーマンスを向上するため、圧縮前にＹＣｂＣｒカラーモデルに変換してもよい。
［５．属性プレーンの例］
【００６０】
カラープレーンに加え、画像は属性プレーンを使用して、デジタル処理で表示してもよい。属性プレーンの値は画像に明白に現れないかもしれないが、属性プレーンは画像圧縮への指示、および操作の処理に利用してもよい。
【００６１】
例として、画像の各画素は、属性を表すビットの配列（例えば、８ビット、又は１６ビット）に関連付けられてもよい。これらの属性のいくつかは、画素が他の材料上のオーバーレイとして利用されているかどうか、又は印刷又はコピー機能の一部として利用されているかどうかを示してもよい。他の属性は、中性色保存技術の参照、カラーモデル間の画素変換の際に使用する色変換テーブル、および／または画素の印刷の際に使用するハーフトーン・スクリーンの参照を含んでもよい。
【００６２】
属性プレーンの配列は、関連付けられている画素が表すオブジェクトタイプを識別するために、利用してもよい。これらの識別されたオブジェクトタイプは、例えば、グラフィカル画像、ベクトルグラフィックス、又はテキストを含んでもよい。オブジェクトタイプタグは、属性配列のような、１以上のビットであってもよい。
【００６３】
例示の属性配列５００は、図５に示される。属性配列５００は、オーバーレイビット５０２、２つの中性色保存ビット５０４、５０６、２つのカラーテーブルビット５０８、５１０、コピー又は印刷ビット５１２、および２つのハーフトーンビット５１４、５１６を含む。
【００６４】
オーバーレイビット５０２は、関連付けられている画素が他の材料に重なるかどうかを示すかもしれない。例えば、印刷デバイスによっては、いくつかの印刷ジョブへの１以上の背景画像又はパターンの適用をサポートしてもよい。これらの画像又はパターンは、ロゴマーク又は境界のような、静的なもの、又は自動ページ番号付け（例えば、文書の各ページの下部の「ページ１／３」のような語句の表示）のような動的なものでもよい。
【００６５】
例えば、自動ページ番号付けの場合、ページ番号を付与するため、ユーザが印刷デバイスに指示してもよい。ユーザは、自動ページ番号付けを特定するため、印刷デバイスのユーザインターフェースでオプションを選択してもよい。代わりに、電子文書を印刷デバイスに送信するコンピュータのプリンタドライバーが、自動ページ番号付けを特定してもよい。別の場合では、印刷デバイスは、画素が前景画素（例えば、ページのテキスト）か、背景画素（例えば、ページの白色背景）かを検知し、前景画素が重なっていることを示すかもしれない。
【００６６】
中性色保存ビット５０４、５０６は、画素が白、黒、又はグレーのような「中性」色か、非中性色かを示してもよい。例えば、中性色保存ビット５０４、５０６は、白に「００」、黒に「０１」、他の中性のグレーに「１０」、又は非中性色に「１１」の値を取ってもよい。
【００６７】
中性色保存の実行は、ＣＭＹカラーモデルからＣＭＹＫカラーモデルへの色変換処理、および／または他のカラーモデル間の色変換処理を向上させるかもしれない。プリンタは、ブラックトナーのみの使用の結果、Ｋカラーチャンネルを使用して中性色を全体的に表せるように、この変換を行なってもよい。従って、白い画素を白のまま、黒い画素を黒のまま、グレーの画素をＣＭＹＫカラーモデルで（０、０、０、Ｋ）として表すのが望ましい。しかしながら、本明細書における非可逆圧縮・解凍技術では、中性の画素を非中性色として表すことができる。
【００６８】
ＣＭＹカラーモデルでは、３つの全チャンネルが同一の値を取る場合、色は中性のグレーであり、このような中性色は（０、０、０、Ｋ）というＣＭＹＫカラーモデルに変換することができる。例として、グレーのＣＭＹ画素（７３、７３、７３）は、非可逆圧縮／解凍技術により、非グレーの画素（７３、７４、７２）に変更してもよい。従って、この画素の色の中性は失われ、この画素の印刷にはカラートナーが利用される。この欠点を克服するため、中性色保存ビット５０４、５０６は、解凍されたＣＭＹ画素を中性の状態に戻すために利用することができる。これを行う１つの可能な方法は、Ｃ、Ｍ、Ｙ画素の平均値を取り、その値を最も近い整数に丸め、得られた値を３つの全カラーチャンネルに使用することである。
【００６９】
一方、場合によっては、画素の値は中性である（例えば、Ｃ、Ｍ、Ｙ画素は全て同一の値を取る）と示しているかもしれない。しかし、中性色保存ビットは「１１」という値を取ってもよい。この場合、カラープレーンの１つの最下位ビットは、画素を非中性色に変更するため、反転（０から１、又は１から０）してもよい。
【００７０】
加えて、純白のＣＭＹ画素は（０、０、０）の値を取り、関連付けられている中性色保存ビットは「００」となるかもしれない。圧縮および解凍後、画素は（０、２、１）のような、非純白の値を取るかもしれない。この場合、中性色保存ビットは検討され、画素は純白であるべきだと決定されてもよい。従って、画素の値はその純白の特性を保存するため、（０、０、０）に変更されてもよい。
【００７１】
同じく、純黒のＣＭＹ画素は（２５５、２５５、２５５）の値を取り、関連付けられている中性色保存ビットは「０１」となるかもしれない。圧縮および解凍後、画素は（２５５、２５３、２５３）のような、非純黒の値を取るかもしれない。この場合、中性色保存ビットは検討され、画素は純黒であるべきだと決定されてもよい。従って、画素の値はその純黒の特性を保存するため、（２５５、２５５、２５５）に変更されてもよい。
【００７２】
本明細書において、（０、０、０）の値を持つ純白画素、および（２５５、２５５、２５５）の値を持つ純黒画素は、「純極」値を持つ画素と呼んでもよい。色値を表すために、８ビットより多くのビットが利用される場合、（０、０、０）および（２５５、２５５、２５５）以外のそれぞれの画素値が純白および純黒を表してもよい。「純極」値を持つ画素は、（２５５、０、０）および（０、２５５、０）のような任意の組合せの「純極」値を有する画素を含むようにしてもよい。
【００７３】
カラーテーブルビット５０８、５１０は、可能性のある一例として、ＣＭＹおよびＣＭＹＫカラーモデル間のカラープレーン値のマッピングを含むカラーテーブルを示してもよい。上で述べたように、画素のオブジェクトタイプ（例えば、画像グラフィックス、ベクトルグラフィックス、又はテキスト）は、画素が取り出された電子文書のＰＤＬ表現から決定してもよい。画素のオブジェクトタイプに基づいて、異なった色変換テーブルが適用されてもよい。例えば、カラーテーブルビット５０８、５１０は、画素がテキスト・オブジェクトの一部の場合「００」を、画素がベクトルグラフィックス・オブジェクトの一部の場合「０１」を、画素が画像グラフィックス・オブジェクトの一部の場合「１１」の値を取ってもよい。カラーテーブルビット５０８、５１０の値に基づいて、複数の色変換テーブルの１つが選択され、画素に適用されてもよい。
【００７４】
コピー又は印刷ビット５１２は、関連付けられている画素が、コピーされる（スキャンされて、印刷される）、又は従来通り印刷される（例えば、ＰＤＬ文書からローカルに格納される、又は他のデバイスから受信される）かを示してもよい。このビットの値は、８つまでのハーフトーン・スクリーン（下記ハーフトーニングの考察を参照）の１つを選択するため、ハーフトーンビット５１４、５１６の値と結合されてもよい。場合によっては、スキャン後、印刷される電子文書は、特定のタイプのハーフトーン・スクリーンを使用してもよく、従来通り印刷される電子文書は、他のタイプのハーフトーン・スクリーンを使用してもよい。
【００７５】
ハーフトーンビット５１４、５１６は、ハーフトーン・スクリーンが印刷時に画像に適用されるかどうか、また、どのハーフトーン・スクリーンが適用されるかを、示してもよい。ハーフトーニングは、サイズ、形状、又は間隔が異なるドットを利用して、勾配をシミュレーションする技術である。ハーフトーニングは、さまざまな色の多数の色調を含む画像を、一連の重ね合ったハーフトーン・スクリーンに分解することができ、各スクリーンは単一（２値）の色合いの特定の色を含む。重ね合ったハーフトーン・スクリーンにより、ドットが滑らかな階調に混合された外観が作成される。
【００７６】
カラーテーブルビット５０８、５１０と同様、ハーフトーンビット５１４、５１６は、画素が表すオブジェクトのタイプに基づいた値を取ってもよい。従って、ハーフトーンビット５１４、５１６は、画素が画像グラフィックス・オブジェクトの一部場合「００」を、画素がベクトルグラフィックス・オブジェクトの一部の場合「０１」を、画素がテキスト・オブジェクトの一部の場合「１１」の値を取ってもよい。ハーフトーンビット５１４、５１６の値に基づいて、複数のハーフトーン・スクリーンの１つが選択され、画素に適用されてもよい。
【００７７】
同一の３つのオブジェクトタイプに基づくにもかかわらず、カラーテーブルビット５０８、５１０はハーフトーンビット５１４、５１６と異なるかもしれない。これら２つの情報の異なるセットを保持する１つの考えられる理由は、いくつかのＰＤＬで混合するオブジェクト画素のオーバーラップを考慮することである。例えば、テキスト画素がラスター画像画素と混合する場合、カラーテーブルビット５０８、５１０はラスター画像を示し、ハーフトーンビット５１４、５１６はテキストを示してもよい。この特徴により、オーバーラップし、混合されたオブジェクトの画像品質が維持される。
【００７８】
例示の属性配列５００は、１画素当たり８ビット（１バイト）を含む。従って、このスタイルの属性配列を使用すると、属性プレーンの大きさは画像の画素数と共に、直線的に増加する。画像の画素に関連付けられている属性配列の範囲を、その画像に対する属性プレーンと呼んでもよい。
【００７９】
属性プレーンはＡプレーンと呼んでもよい。従って、属性プレーンが１以上のカラープレーンと結合される場合、結合された属性およびカラープレーンは、利用されるカラーモデルによって、ＫＡ、ＣＭＹＡ、ＣＭＹＫＡ、ＲＧＢＡ、又はＹＣｂＣｒＡと呼んでもよい。本明細書において、これらの結合された属性およびカラープレーンの例を、属性プレーンがそれ自体、実際、色を表していないにも拘わらず、「カラーモデル」 と呼んでもよい。
［６．イメージング・パイプラインの例］
【００８０】
例示のイメージング・パイプラインの高レベルな概観は、図６に示される。このイメージング・パイプラインはフローチャート６００の形式を取り、多数の圧縮および解凍のステップを含む。フローチャート６００は、電子文書の受信、格納、および印刷のため、印刷デバイスによって実行される一連のステップを表してもよい。
【００８１】
図６のブロック６０２では、電子文書はＫＡ又はＣＭＹＡカラーモデルに従ってフォーマットされた１以上の画像として表してもよい。しかしながら、これらのカラーモデルはイラスト用に選択され、他のカラーモデルが利用されてもよい。ＫＡ又はＣＭＹＡ画素は、電子文書のＰＤＬ表現から取り出されてもよい。
【００８２】
代わりに、ブロック６０２では、電子文書は、ビットマップ、ＪＰＥＧ、ＧＩＦなどのような、画像フォーマットによって表され、例えば、ＫＡ又はＣＭＹＡカラーモデルに変換されてもよい。
【００８３】
ブロック６０４では、セルベース圧縮（以下で詳細に説明）が電子文書の各プレーンの画素に適用されてもよい。従って、ＫＡ電子文書用に、セルベース圧縮がグレープレーンおよび属性プレーンに適用されてもよい。ＣＭＹＡ電子文書用には、セルベース圧縮がＣ、Ｍ、Ｙ、Ａプレーン毎に別々に、又は合成して、適用されてもよい。よって、場合によっては、セルベース圧縮は、同一の論理演算において、２つ以上のプレーンの対応するセルを圧縮してもよい。ブロック６０４の結果は、電子文書の圧縮バージョンを表すビットストリームであってもよい。
【００８４】
ブロック６０６では、この圧縮バージョンはストレージ出力媒体に格納されてもよい。概して、このストレージは、１枚以上のページの圧縮表現を格納する印刷デバイスのメモリであってもよい。本明細書において説明されている圧縮技術によれば、これらの文書を元のビットマップサイズの少なくとも３分の１、又は４分の１に圧縮できるかもしれないため、ストレージのメモリサイズの要求は従って、縮小されるかもしれない。結果として、本明細書における実施形態を組み込んだ印刷デバイスは、安価に製造されるかもしれない。
【００８５】
ブロック６０８では、セルベース解凍が電子文書の各プレーンに適用されてもよい。これにより、電子文書のＫＡ又はＣＭＹＡ表現が再現されるかもしれない。しかしながら、セルベース圧縮技術が非可逆圧縮を使用する場合、ブロック６０８の解凍から得られる電子文書は、ブロック６０４の圧縮により圧縮された電子文書とは異なるかもしれない。それでも、これらの電子文書のバージョン間の差異はほんのわずかであり、人間により容易には認識されないかもしれない。
【００８６】
ブロック６１０では、電子文書の解凍バージョンがさらに処理されてもよい。例えば、電子文書にさまざまな変換が適用されてもよい。電子文書に１以上のこれらの変換が行われた後、電子文書はブロック６０４で再び圧縮され、ブロック６０６でストレージに格納されてもよい。ブロック６１０のアプリケーションはオプションで、全ての電子文書がこの処理の対象となるわけではない。
【００８７】
ブロック６１２では、電子文書の解凍バージョンも、さらに処理されてもよい。ブロック６１４では、セルベース圧縮が電子文書の各プレーンに適用されてもよい。この圧縮手順は、ブロック６０４の手順と同一でもよいし、異なってもよい。例えば、ブロック６１４で適用された圧縮は、ブロック６０４の圧縮よりも高い、又は低い圧縮比を得られるように構成されてもよい。
【００８８】
ブロック６１６では、この圧縮バージョンはストレージに格納されてもよい。ブロック６０６のストレージのように、このストレージは１枚以上のページの圧縮表現を格納する印刷デバイスのメモリでもよい。これらのページ表現は圧縮されるため、ストレージのメモリ要求および費用は縮小する。
【００８９】
ブロック６１８では、セルベース解凍が電子文書の各プレーンに適用されてもよい。これにより、電子文書のＫＡ、ＣＭＹＡ、又はＣＭＹＫＡ表現が再現されてもよい。ブロック６０８のケースのように、セルベース圧縮技術が非可逆圧縮を使用する場合、ブロック６１８の解凍から得られた電子文書は、ブロック６０４および／またはブロック６１４の圧縮により圧縮された電子文書のバージョンとは異なるかもしれない。
【００９０】
ブロック６２０では、電子文書にさらに処理が適用されてもよい。ブロック６２０の後、電子文書は印刷準備が整う、又は追加の処理が適用されるかもしれない。
【００９１】
ブロック６０４および６１４のセルベース圧縮手順は、同一でもよいし、異なってもよい。例えば、これらの手順は、異なる圧縮アルゴリズムを使用してもよい、又は、同一又は異なる設定で同一の圧縮アルゴリズムを使用してもよ。同様に、ブロック６０８および６１８のセルベース解凍手順は、同一でもよいし、異なってもよい。
【００９２】
実施形態によっては、１画素当たり利用される属性プレーンビットの数は、フローチャート６００で圧縮が行われるポイントに基づいて変化してもよい。例えば、属性配列５００の全ビットが、ブロック６０４で圧縮されてもよい。色変換、中性色保存、オーバーレイ処理、およびハーフトーニングはブロック６０４の後で起こるため、属性配列５００の各ビットは、保存されるべきである。
【００９３】
しかしながら、ブロック６１２の後、オーバーレイビット５０２、中性色保存ビット５０４、５０６、およびカラーテーブルビット５０８、５１０はもはや必要ではないかもしれない。さらに、いくつかのタイプの印刷デバイスはコピー機能を持たない。従って、これらの印刷デバイスに対しては、コピー又は印刷ビット５１２はフローチャート６００のいずれのポイントでも利用されない可能性があり、ブロック６０４およびブロック６１４の圧縮から省略できる。
【００９４】
いずれにしても、さまざまな実施形態において、属性配列５００の０から６までのビットのどこでも、セルベース圧縮手順から省略されてもよい。その結果、１セル当たり圧縮されるビットの総数は減少し、代わりに属性プレーンのセルの達成可能な圧縮比が上昇するかもしれない。
【００９５】
本明細書における説明では、画像の属性およびカラープレーンに適用されるセルベース圧縮の単一インスタンスに焦点を当てている。画像は、１枚以上のページを含む電子文書の単一ページの表現でもよい。とはいえ、このセルベース圧縮の多数のインスタンスは、パイプライン６００又はいくつかの他の配置に従って、画像などのセルに適用されてもよい。この方法により、画像全体が効率的に圧縮されるかもしれない。
【００９６】
さらに、セルベース解凍技術も、本明細書において説明されているセルベース圧縮技術を反転させることにより、画像に適用されてもよい。
［７．セル・コンフィギュレーションの例］
【００９７】
セルベース圧縮の１局面は、電子文書の各カラープレーンおよび属性プレーンを１以上のｍ×ｎセルに分割し、その後、各セルを部分的に独立した、又は完全に独立した方法で圧縮してもよいということである。例えば、ｍは８、ｎは４かもしれない。代わりに、ｍが８、ｎが８、又は同様に、ｍが１６、ｎが１６かもしれない。ｍおよびｎの他の値を利用してもよい。
【００９８】
各セルは、どのタイプの圧縮技術が、そのセルのデータの圧縮に最も効率的かを判定するために評価されてもよい。例えば、セルが全て同一の色の画素から成る場合、セルのデータはその色およびおそらくいくつかのオーバーヘッドデータの表現に非常に効率よく圧縮されるかもしれない。しかしながら、セルがフォトリアリスティック画像の一部を含む場合、セルのデータはそのように高い圧縮比では圧縮できないかもしれない。
【００９９】
図７は、セルベース圧縮で利用され得るセル構造の一例を示す。便宜上、セルは、ｐＣｅｌｌおよびｑＣｅｌｌを単位として考える。ｐＣｅｌｌは、画像のカラープレーン又は属性プレーンのｍ×ｎ構成要素ブロックでよい。従って、カラープレーン用に、ｐＣｅｌｌ構成要素が画素、属性プレーン用に、ｐＣｅｌｌ構成要素が属性配列であってよい。ｑＣｅｌｌは、画像のカラープレーン又は属性プレーンのａ×ｂ構成要素ブロックでよい。各ｑＣｅｌｌは、いくつかの数の非オーバーラップｐＣｅｌｌから構成されてもよい。コンテキストによって、「ｐＣｅｌｌ」および「ｑＣｅｌｌ」という言葉は、単一の属性又はカラープレーン、又は複数の属性およびカラープレーンの構成要素に言及することもあり得る。
【０１００】
例として、図７はそれぞれが特定プレーン用の６４の属性又は画素値を含む、４つの８×８・ｐＣｅｌｌ・７００、７０２、７０４、７０６を示す。各属性又は画素値は、例えば、０乃至２５５の範囲の数によって表され、従って、バイトとして表されてもよい。しかしながら、他の可能性も存在する。単純化するため、ｐＣｅｌｌ・７００は、いくつかの代表値の位置のみを示す。
【０１０１】
図７に示される４つのｐＣｅｌｌの２×２配置は、ｑＣｅｌｌと呼んでもよい。従って、図７のｑＣｅｌｌ・７１０は１６×１６で、特定のプレーンの２５６の属性又は画素値を含んでもよい。とはいえ、ｑＣｅｌｌは、異なる数のｐＣｅｌｌ（例えば、３×２、２×３、又は３×３ブロックのｐＣｅｌｌ）を含むこともあり得る。
【０１０２】
図７は、上方左手のｐＣｅｌｌを「ａ」ｐＣｅｌｌと、上方右手のｐＣｅｌｌを「ｂ」ｐＣｅｌｌと、下方左手のｐＣｅｌｌを「ｃ」ｐＣｅｌｌと、および下方右手のｐＣｅｌｌを「ｄ」ｐＣｅｌｌと呼ぶ。これらの名称はｐＣｅｌｌ・ＩＤと呼んでもよく、単にｑＣｅｌｌ内のｐＣｅｌｌの位置を区別するための便利な方法であり、以下のインターリービングの考察で利用される。
【０１０３】
本明細書において説明されているセルベース圧縮技術は、ｐＣｅｌｌおよびｑＣｅｌｌで動作してもよい。単純化のため、８×８・ｐＣｅｌｌおよび１６×１６・ｑＣｅｌｌが利用されると仮定する。しかしながら、この仮定は、異なったサイズのｐＣｅｌｌおよびｑＣｅｌｌを代わりに利用してもよいという了解のもとにある。
【０１０４】
さらに、プレーンのｐＣｅｌｌ又はｑＣｅｌｌは、単一プレーンの構成要素に言及してもよい一方、合成ｐＣｅｌｌ又はｑＣｅｌｌは、複数のプレーンにまたがる、対応する構成要素に言及してもよい。例えば、ＣＭＹＡカラーモデルが利用される場合、プレーンのｐＣｅｌｌがＣ、Ｍ、Ｙ、Ａプレーンの１つの構成要素を含んでもよい一方、合成ｐＣｅｌｌはＣ、Ｍ、Ｙ、Ａプレーンの２つ以上の構成要素含んでもよい。
［８．セルベース圧縮の例］
2016149762.tif 000003
【０１０５】
次の複数のサブセクションでは、さまざまなセルベース圧縮技術について、詳細に説明する。これらの各技術は、ｐＣｅｌｌ、ｑＣｅｌｌ、又は両方で動作する。これらの圧縮技術の概要は、表１に提供される。
［ａ．Ｄ１およびＤ１Ｄ圧縮］
【０１０６】
Ｄ１圧縮は、任意のｐＣｅｌｌの全ての属性又は画素が同一の場合に利用してもよい。例えば、ｐＣｅｌｌの各属性又は画素が０乃至２５５の値を取ると仮定する。全ての値が７４の場合、ただ１つの例として、Ｄ１圧縮をこのセルに適用してもよい。この方法により、ｐＣｅｌｌを表すために必要とされるデータの量を著しく縮小することができる。
【０１０７】
Ｄ１Ｄ圧縮と呼んでもよい、Ｄ１圧縮の変形は、色値がデフォルトの色の場合に利用してもよい。例えば、ＹＣｂＣｒ色空間のＹプレーン、グレー色空間、および全ＣＭＹＫ色空間において、デフォルト値は０および２５５でよい。ＹＣｂＣｒ色空間のＣｂおよびＣｒプレーンにおいては、デフォルト値は１２８および２５５でよい。Ｄ１Ｄ圧縮は、Ｄ１圧縮より多少効率的に符号化する。色空間には限られた数のデフォルト値（例えば、２）のみしかないため、これらのデフォルト色値は少数のビット（例えば、１）で表すことができる。結果的に、Ｄ１Ｄ圧縮は１・ｐＣｅｌｌ当たり、Ｄ１圧縮より少ないビットしか要求しないかもしれない。
【０１０８】
属性プレーンに対して、Ｄ１Ｄデフォルト値は予め決められていてもよいし（例えば、０又は１２８）、又はユーザにより手動で設定されてもよい。
【０１０９】
場合によっては、全ての属性又は画素に対して、同一の値を持つ複数の隣接するｐＣｅｌｌ（例えば、１行又は１列のｐＣｅｌｌ）は、Ｄ１又はＤ１Ｄ符号化を使用して表してもよい。これが起こり得る、２つの考えられる方法がある。Ｄ１およびＤ１Ｄの両圧縮は、ランレングスの符号化を可能にする。ランレングスは、合計どのくらいのｐＣｅｌｌについても、Ｄ１圧縮を使用して圧縮されたかを表す。Ｄ１圧縮も、後続のｐＣｅｌｌの符号化で利用されるための、事前の利用（キャッシュされた属性又は画素値）を可能にする。
2016149762.tif 000004
【０１１０】
表２はＤ１およびＤ１Ｄ圧縮用の２進符号化の例を提供する。Ｄ１圧縮に対しては、ｐＣｅｌｌの圧縮表現はオペコード００１から始まる。Ｖ’ビットが１の場合、Ｄ１符号化も１バイト値の引数（ｐＣｅｌｌの全ての属性又は画素に対して同一）を含む。Ｖ’ビットが０の場合、値引数は符号化から省略され、最新のＤ１符号化の値（例えば、キャッシュされた値）がｐＣｅｌｌの全ての属性又は画素に利用される。長さ引数は２ビットでよく、１乃至４つのｐＣｅｌｌのｑＣｅｌｌ内のランレングスをサポートする。値引数は、属性値と同様、画素値に適用する。従って、値引数は、カラープレーンのｐＣｅｌｌを圧縮する場合、８ビットでよい。しかしながら、上で述べたように、８未満のビットは属性プレーン値を表すために利用され、値フィールドのサイズは適宜減少されるかもしれない。
【０１１１】
Ｄ１Ｄ圧縮に対しては、ｐＣｅｌｌの圧縮表現はオペコード０００から始まる。Ｖビットは２つのデフォルト値のどちらが利用されるか（例えば、Ｖが０の場合、１つの値が利用され、Ｖが１の場合、他の値が利用される）を示す。長さ引数は、Ｄ１圧縮で利用されたのと同一の方法で利用してもよい。
［ｂ．Ｐ２およびＰ２Ｄ圧縮］
【０１１２】
Ｐ２圧縮は、任意のｐＣｅｌｌの各属性又は画素が２つの値の１つを使用して表すことができる場合に利用してもよい。例えば、セルの属性又は画素が０と２５５間の値を取ることができるが、全ての値が７６又は１２５のどちらかの場合、Ｐ２圧縮はｐＣｅｌｌで利用してもよい。Ｐ２圧縮が利用される場合、ｐＣｅｌｌの属性又は画素のビットマップと同様、２つの値は符号化されてもよい。ビットマップは、どの値がｐＣｅｌｌの各属性又は画素に関連付けられているかを示す。Ｄ１およびＤ１Ｄ圧縮と同様、Ｐ２圧縮は直前に利用された値のペアのキャッシングを使用してもよい。
【０１１３】
Ｐ２Ｄ圧縮と呼んでもよいＰ２圧縮技術の変形は、セルに２つのデフォルト色値のみが現れる場合に利用してもよい。上で述べたように、ＹＣｂＣｒ色空間のＹプレーン、グレー色空間、および全ＣＭＹＫ色空間において、デフォルト値は０および２５５でよい。ＹＣｂＣｒ色空間のＣｂおよびＣｒプレーンにおいては、デフォルト値は１２８および２５５でよい。従って、Ｐ２Ｄ圧縮はｐＣｅｌｌの属性又は画素のビットマップを符号化してもよいが、デフォルト値が利用されるため、属性又は画素の値の符号化を明示的に行う必要はない。
【０１１４】
属性プレーンに対しては、１つ又は両方のＰ２Ｄデフォルト値が予め決定されていてもよいし（例えば、０および１２８）、ユーザにより手動で設定されてもよい。
2016149762.tif 000005
【０１１５】
表３は、Ｐ２およびＰ２Ｄ圧縮用の２進符号化の例を提供する。Ｐ２圧縮に対しては、ｐＣｅｌｌの圧縮表現はオペコード０１１から始まる。Ｖ’ビットが１の場合、Ｐ２符号化もｐＣｅｌｌの属性又は画素により利用される値のペア（値１および値２）を示す２バイトを含む。Ｖ’ビットが０の場合、これらの値は符号化から省略され、最新のＰ２符号化の値（例えば、キャッシュされた値）がｐＣｅｌｌの属性又は画素に利用される。
【０１１６】
Ｐ２Ｄ圧縮に対しては、ｐＣｅｌｌの圧縮表現はオペコード０１０から始まる。Ｐ２およびＰ２Ｄ圧縮の両方に対し、Ｐオプションが１の場合、線図引数が提示され、ビットマップの８ラインのどれがまた提示されているかを示す。Ｐオプションが０の場合、ビットマップのいずれの線図引数又はラインも提示されない。その代わりに、Ｐ２又はＰ２Ｄで圧縮された最新のｐＣｅｌｌからキャッシュされたビットマップを利用してもよい。
【０１１７】
線図の各ビットは、ビットマップの対応するラインフィールドの存在を示す。線図が提示されると、少なくとも１つのラインもビットマップに提示されると仮定してもよい。従って、線図は、ビットマップの２列目から８列目のラインに渡って符号化を行うため、７ビットのみを使用してもよい。線図の各ビットに対し、０は対応するラインがないため、前のラインを繰り返すことを示す。一方、１は対応するラインがあることを示す。
［ｃ．Ｐ４圧縮］
【０１１８】
Ｐ４圧縮は、任意のセルの全ての画素が３つ又は４つの色値を使用して表すことができる場合に利用してもよい。Ｐ４圧縮が利用される場合、ｐＣｅｌｌの属性又は画素のビットマップと同様、３つ又は４つの値は符号化されてもよい。ビットマップはどの値がｐＣｅｌｌの各属性又は画素に関連付けられているかを示す。
2016149762.tif 000006
【０１１９】
表４は、Ｐ４圧縮用の２進符号化の例を提供する。Ｐ４圧縮に対して、ｐＣｅｌｌの圧縮表現はオペコード１００から始まる。７ビットの線図は、Ｐ２ビットマップの圧縮と同様に、ビットマップがどのように圧縮されるかを定義する。線図の各ビットに対し、０は対応するラインがないため、前のラインを繰り返すことを示す。一方、１は対応するラインがあることを示す。
【０１２０】
４つの値引数は、ｐＣｅｌｌに見られる構成要素の値を表す８ビットフィールドである。これらの値を区別するため、ビットマップの各ライン（もしあれば）は１６ビットの長さでよい。Ｐ４圧縮により３つの値のみ符号化される場合、「値４」の引数は存在しても、無視して構わない。
［ｄ．ＤＣＴＰ圧縮］
【０１２１】
ＤＣＴＰ圧縮は、ｐＣｅｌｌを圧縮するための離散コサイン変換（ＤＣＴ）技術の使用に言及する。実施形態によっては、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、およびＰ４圧縮がカラープレーンの特定のｐＣｅｌｌに適さない場合、ＤＣＴＰ圧縮を利用してもよい。ＤＣＴＰ圧縮は非可逆で、属性プレーンに対しては可逆で圧縮するのが望ましいため、ＤＣＴＰ圧縮は属性プレーンには利用されないかもしれない。ＤＣＴＰ圧縮は、ＤＣＴ変換、スケーリング、量子化、２次元係数配列から１次データへの並べ換え、およびハフマン・エントロピー符号化を含んでもよい。
2016149762.tif 000007
【０１２２】
表５は、ＤＣＴＰ圧縮用の２進符号化の例を提供する。ＤＣＴＰ圧縮に対して、ｐＣｅｌｌの圧縮表現はオペコード１１から始まり、表現の残りの部分はＤＣＴ符号化である。実施形態によっては、ＤＣＴ符号化は、ジョイント・フォトグラフィック・エキスパート・グループ（ＪＰＥＧ）規格のサブセットに従って、ハフマン符号化でパッケージ化された、量子化されたＤＣＴ係数の集合でよい。
［ｅ．ＤＣＴＱ圧縮］
【０１２３】
ＤＣＴＱ圧縮は、ｑＣｅｌｌを全体でｐＣｅｌｌのサイズにダウンサンプリングすることにより圧縮するＤＣＴ技術の使用、続いて得られたｐＣｅｌｌへのＤＣＴＰ符号化の適用に言及する。実施形態によっては、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、およびＰ４圧縮がカラープレーンの１以上の特定のｐＣｅｌｌに適さない場合、ＤＣＴＱ圧縮を利用してもよい。ＤＣＴベース圧縮は非可逆で、属性プレーンに対しては可逆で圧縮するのが望ましいため、ＤＣＴＱ圧縮は属性プレーンには利用されないかもしれない。
【０１２４】
例として、１６×１６・ｑＣｅｌｌは、８×８・ｐＣｅｌｌにダウンサンプリングしてもよい。ダウンサンプリング手順は、１６×１６・ｑＣｅｌｌの６４の非オーバーラップ２×２ブロックへの分割、および各ブロックの、それぞれのブロックにおける画素値の平均である単一画素値への置き換えを含んでもよい。得られた６４の平均値は、８×８セルを形成する。とりわけ、このダウンサンプリングは初期の４：１圧縮比を提供し、続いて、ＤＣＴＰ符号化がその上に追加の圧縮を提供する。
2016149762.tif 000008
【０１２５】
表６は、ＤＣＴＱ圧縮用の２進符号化の例を提供する。ＤＣＴＱ圧縮に対して、ｑＣｅｌｌの圧縮表現はオペコード１０１から始まり、表現の残りの部分はＤＣＴ符号化である。ＤＣＴＰのケースと同様、ＤＣＴ符号化は、ＪＰＥＧ規格のサブセットに従って、ハフマン符号化でパッケージ化された量子化されたＤＣＴ係数の集合でよい。
［ｆ．Ｄ１ＣおよびＤ１Ｅ圧縮］
【０１２６】
Ｄ１ＣおよびＤ１Ｅ圧縮は、Ｄ１又はＤ１Ｄ圧縮候補の連続したセルの実行の効率的な符号化を促進する。これらの実行の符号化は、無地（例えば、白色背景）を示すセクションの画像において、圧縮パフォーマンスを著しく上昇させるかもしれない。Ｄ１又はＤ１Ｄの２つのタイプの実行がサポートされてもよい。つまり、（１）ｑＣｅｌｌを横断するＤ１又はＤ１Ｄ候補のｐＣｅｌｌのインターｑＣｅｌｌの実行、および（２）ｑＣｅｌｌ内のＤ１又はＤ１Ｄ候補のｐＣｅｌｌのイントラｑＣｅｌｌの実行、である。
【０１２７】
インターｑＣｅｌｌ・Ｄ１又はＤ１Ｄ実行は、２つ以上のｑＣｅｌｌに及ぶＤ１又はＤ１Ｄ実行の符号化を行う。ｑＣｅｌｌの２つの右端のｐＣｅｌｌ（「ｂ」および「ｄ」ｐＣｅｌｌ）が、Ｄ１圧縮を使用して符号化された一定の画素値の８×１６配列を含む場合、これはＤ１又はＤ１Ｄ実行の開始を意味し、符号化モードを通常の符号化モードからＤ１又はＤ１Ｄ実行符号化モードへ変更する。この符号化モードはプレーン毎に、およびｑＣｅｌｌの境界で追跡される。従って、特定のプレーンに対し、Ｄ１又はＤ１Ｄ実行符号化モードへのモードの変更は、ｑＣｅｌｌの境界の端部で行われる。
【０１２８】
Ｄ１又はＤ１Ｄ実行符号化モードでは、Ｄ１Ｃ（継続）およびＤ１Ｅ（終了）の２つのコードのみが定義され、それぞれシングルビットを使用して符号化される。後続のｑＣｅｌｌが、実行を開始する２つのＤ１又はＤ１Ｄ候補のｐＣｅｌｌと同一の１６×１６画素値を含む限り、１ビットのＤ１Ｃオペコードは放出され、Ｄ１又はＤ１Ｄ実行符号化モードが継続する。後続のｑＣｅｌｌが実行の開始にマッチングするベタ値以外の何かを含む場合、実行は終了する。この場合、１ビットのＤ１Ｅコードが放出され、通常の符号化モードが再入力される。また、その時点のｑＣｅｌｌに対する任意の残りのＤ１、Ｐ２、Ｐ４、ＤＣＴＰ、又はＤＣＴＱ符号化は放出される。
【０１２９】
イントラｑＣｅｌｌ・Ｄ１又はＤ１Ｄ実行は、ｑＣｅｌｌ内でＤ１又はＤ１Ｄ実行の符号化を行う。例えば、２ビットのランレングスは、ｑＣｅｌｌ内の１乃至４つのｐＣｅｌｌに広がっているＤ１およびＤ１Ｄ実行の符号化を行うために利用されてもよい。このような実行は、表示されたＤ１（ｎ）およびＤ１Ｄ（ｎ）であり、ｎは値１、２、３、又は４を取る。
2016149762.tif 000009
【０１３０】
表７は、Ｄ１ＣおよびＤ１Ｅ圧縮用の２進符号化の例を提供する。Ｄ１Ｃ圧縮に対して、１はＤ１又はＤ１Ｄ実行の連続を示し、任意のｑＣｅｌｌの全４つのｐＣｅｌｌは現在の実行のＤ１又はＤ１Ｄセルに対応する。Ｄ１Ｅ圧縮に対しては、０はＤ１又はＤ１Ｄ実行の端部を示す。
［ｇ．Ｄ６４圧縮］
【０１３１】
Ｄ６４圧縮は、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、およびＰ４圧縮が適さない属性プレーンのｐＣｅｌｌの符号化を行うために利用される可逆技術である。例えば、ｐＣｅｌｌが５つ以上の異なる値を含む場合、Ｄ６４圧縮を利用してもよい。
【０１３２】
Ｄ６４圧縮は、８×８属性ｐＣｅｌｌの全６４の値を符号化し、８×８属性ｐＣｅｌｌのヘッダに含まれる場合、結果として、圧縮よりむしろ非常にわずかな拡張となる。しかしながら、属性プレーンは可逆で圧縮するのが望ましいため、Ｄ６４圧縮が場合によっては必要となるかもしれない。
【０１３３】
とはいえ、セルベース圧縮が圧縮パイプライン６００で起きているかどうかにより、ｐＣｅｌｌの属性値の全８ビットは符号化されないかもしれない。その代わりに、これらの値の２乃至８ビットはまとめられ、符号化されてもよい。これにより、Ｄ６４圧縮が改良される。
2016149762.tif 000010
【０１３４】
表８は、Ｄ６４圧縮用の２進符号化の例を提供する。Ｄ６４・ｐＣｅｌｌの圧縮表現はオペコード１１から始まり、属性毎に２乃至８ビットを使用して符号化された、ｐＣｅｌｌの６４の属性配列も含む。属性配列毎のビットの数は、上述のように、属性プレーンの圧縮の際、どのくらいの数の属性ビットが省略できたかに基づく。ここで留意すべきは、ＤＣＴＰおよびＤ６４圧縮が同一のオペコードを共有することである。しかしながら、ＤＣＴＰはカラープレーンにのみ利用され、Ｄ６４は属性プレーンにのみ利用されるため、これらの符号化は、圧縮されるｐＣｅｌｌのプレーンに基づいて識別することができる。
［ｈ．エンドオブファイル（ＥＯＦ）］
【０１３５】
ＥＯＦはそれ自体圧縮技術ではないが、その代わりに、圧縮ストリームの終了を知らせるために定義される。コンプレッサでは、全入力データが圧縮され、最終のｑＣｅｌｌの最終コードが放出されると、ＥＯＦシーケンスを放出することができる。ＥＯＦは属性プレーンコードとして放出される。
【０１３６】
属性プレーンがＤ１又はＤ１Ｄ実行符号化モードの場合、Ｄ１Ｅは、ＥＯＦが放出される前に、通常の符号化モードに戻すために放出されてもよい。加えて、ＥＯＦは、属性プレーン以外の任意プレーンで、任意のアクティブなインターｑＣｅｌｌ・Ｄ１又はＤ１Ｄ実行を自動的に終了させる。
2016149762.tif 000011
【０１３７】
表９は、ＥＯＦ用の２進符号化の例を提供する。００１のオペコードの後、２進値「１００００００００００」が放出される。ＥＯＦはＤ１圧縮とオペコードを共有するため、この値はｐＣｅｌｌのＤ１符号化からＥＯＦを識別するために利用できる。
［９．決定木の例］
【０１３８】
ｐＣｅｌｌおよびｑＣｅｌｌの符号化は、１以上の決定木に基づいてもよい。各決定木は、ｐＣｅｌｌ又はｑＣｅｌｌが符号化される前に、さまざまな要因を検討する処理を示す。属性プレーンおよびカラープレーンに分かれた決定木であってもよい。例えば、属性プレーンの圧縮の際、いずれの情報も失われないのが望ましい。従って、属性プレーンはさまざまな可逆圧縮技術を使用して圧縮してもよい。一方、カラープレーンのある部分（例えば、ベクトルグラフィックスおよびテキスト部分）は可逆で圧縮するのが望ましいが、カラープレーンの他の部分（例えば、画像グラフィックス部分）は非可逆で圧縮することが望ましい。この方法により、元の画像の詳細は所望の際に保存できるが、なお高い圧縮比を達成することができる。
［ａ．カラープレーン決定木］
【０１３９】
図８は、例示の実施形態に係るカラープレーン決定木８００を示す。この決定木は、ｑＣｅｌｌが４つの非オーバーラップｐＣｅｌｌで構成されるという了解のもとで、ｑＣｅｌｌの特性を検討する。このようなｑＣｅｌｌおよびこれに従属するｐＣｅｌｌのサイズは、それぞれ１６×１６および８×８でよい。しかしながら、代わりに他のサイズを利用してもよい。
【０１４０】
ｑＣｅｌｌの各画素は、テキスト、ベクトル（例えば、線画）、又はラスター（例えば、画像）など、画素が属するオブジェクトのタイプの指示によってタグ付けされると仮定する。これらのタグは、ｑＣｅｌｌの属性プレーンに属してもよい。
【０１４１】
さらに、決定木８００は１２００ｄｐｉおよび／または６００ｄｐｉの画像に利用されてもよい。しかしながら、場合によっては、６００ｄｐｉの画像の処理の際、３００ｄｐｉへのダウンサンプリングを避けるため、ＤＣＴＱ方法が省略されてもよい。例えば、６００ｄｐｉの画像向けの決定木は、図８のブロック８０４、８０６、および８０８のみを含んでもよい。
【０１４２】
各決定ブロック８０２、８０４、８１０、８１２、８１６、８１８、８２０、８２２において、決定のタイプは括弧で示される。プレーンベースで決定される場合、括弧付きＰが存在する。合成ベースで決定される場合、括弧付きＣが存在する。しかしながら、各圧縮技術はプレーン毎に適用される。
【０１４３】
プレーンは、各カラープレーンのｑＣｅｌｌおよび／またはｐＣｅｌｌを別々に検討して、決定する。従って、例えば、プレーンの決定では、単一のｑＣｅｌｌおよび／またはｐＣｅｌｌに関連付けられている色特性および／または属性が検討されてもよい。しかしながら、合成の決定では、ｑＣｅｌｌにより定義された画像の位置の全カラープレーンに対する、ｑＣｅｌｌおよびｐＣｅｌｌの特性、および関連付けられている属性が検討されてもよい。
【０１４４】
単純化のため、Ｄ１ＤおよびＰ２Ｄ圧縮は、決定木８００では明示的に言及しない。しかしながら、Ｄ１又はＰ２圧縮が検討、又は利用されるところで、Ｄ１ＤおよびＰ２Ｄ圧縮も同様に、検討、又は利用されてもよい。従って、ブロック８０４、８０６はＤ１ＤおよびＰ２Ｄ圧縮を検討および使用する一方、ブロック８２４はＤ１Ｄ圧縮を適用してもよい。連続したＤ１又はＤ１Ｄ符号化の実行も、決定木８００で明示的に検討されないが、それでも利用して構わない。
【０１４５】
ブロック８０２、８１０、８１６、８２０はそれぞれ、ｑＣｅｌｌに基づいた合成の決定を表している。これらの各決定に対して、ｑＣｅｌｌの全カラープレーンの値の範囲は、ｑＣｅｌｌによって表されるオブジェクトタイプの数のように、検討される。範囲が広いか狭いかを判定するために、各プレーンの値の範囲を決定してもよい（よって、例えば、３つのカラープレーンがある場合、３つの範囲が決定される）。各範囲は、そのプレーンのｑＣｅｌｌの最高画素値の差を取って、およびそのプレーンのｑＣｅｌｌの最低画素値を減ずることにより、算出してもよい。これらの範囲のいずれかが所定の閾値を越える場合、範囲が広いと分類される。そうでない場合は、範囲が狭いと分類される。所定の閾値は、４、８、１６、３２、又は別の値でもよい。
【０１４６】
さらに、タグの混合は、２つ以上のオブジェクトがｑＣｅｌｌに集まっていることを示し、従ってｑＣｅｌｌはエッジを含んでもよい。画像の鮮鋭度を保持するため、エッジを保存するのが望ましい。ｑＣｅｌｌの全２５６のタグの値が同一の場合、ｑＣｅｌｌにエッジがあるとは考えにくい。
【０１４７】
広い範囲は保存するに値する詳細を示す一方、狭い範囲はダウンサンプリングに適したｑＣｅｌｌ候補を示している。広い範囲および混合タグは、総合すれば、エッジを持ったｑＣｅｌｌの証拠となるかもしれない。この場合、ブロック８０２にあるように、ダウンサンプリングは避けるべきである。ブロック８０２の質問が肯定された場合、次にブロック８０４が検討される。
【０１４８】
ブロック８０４では、ｑＣｅｌｌは保存するべきエッジ・ディティールを有してもよく、各プレーンはこのディティールを最良で保存するため、ｐＣｅｌｌ毎に符号化される。ｐＣｅｌｌが１、２、又は４色を有する場合、それぞれＤ１、Ｐ２、又はＰ４での符号化が適している。Ｄ１、Ｐ２、又はＰ４圧縮の１つが選択された場合、この技術はブロック８０６で適用してもよい。そうでない場合、ＤＣＴＰ圧縮はブロック８０８で適用してもよい。実施形態によっては、ブロック８０４は、各カラープレーンの各ｐＣｅｌｌのｍ×ｎ画素のそれぞれの色値が、ｄは少なくとも２である、少なくともｄ色を含んでいるかどうか決定する、一般的な処理を含んでもよい。
【０１４９】
一方、ｑＣｅｌｌが広い範囲および同一タグを全般にわたって提示する場合、ブロック８１０の質問は肯定され、次にブロック８１２が検討される。合成ベースでは、ｑＣｅｌｌに５つ以上の色があるかどうか決定され、全てのタグはラスターを示す。この条件が真の場合、ｑＣｅｌｌは画像データのみを含むので、ブロック８１４ではＤＣＴＱ技術を使用して圧縮されてもよい。この条件が真でない場合、ｑＣｅｌｌはダウンサンプリングするべきではないテキスト又は線画のどちらかを含む、又は非常に少数の値を持つ画像データ含む。いずれにせよ、Ｄ１、Ｐ２、Ｐ４、又はＤＣＴＰ圧縮は、ｑＣｅｌｌの情報の保存に優れていてもよく、又は優れた圧縮比を提供してもよい。従って、ｑＣｅｌｌはブロック８０４でさらに検討され、ブロック８０６又はブロック８０８のどちらかで圧縮されてもよい。
【０１５０】
代わって、ｑＣｅｌｌが狭い範囲および混合タグを提示する場合、わずかな情報はこの処理で失われるべきなので、ｑＣｅｌｌはダウンサンプリングの候補としてよい。しかしながら、ｑＣｅｌｌに４つ以下の色がある場合、Ｄ１、Ｐ２、又はＰ４圧縮の１つが、ＤＣＴベース圧縮より優れた圧縮比を提供するかもしれない。
【０１５１】
従って、ブロック８１６の質問が肯定された場合、ブロック８１８に到達する。ブロック８１８では、合成ベースで、ｑＣｅｌｌが５つ以上の色を含むかどうかが決定される。５つ以上の色を含む場合、ｑＣｅｌｌは概ね画像データを含む可能性が高く、ブロック８１４でＤＣＴＱ技術を使用して圧縮されてもよい。５つ以上の色を含まない場合、ｑＣｅｌｌはブロック８０４でさらに検討され、ブロック８０６で圧縮されてもよい。ｑＣｅｌｌは４つ以下の色を有するため、Ｄ１、Ｐ２、又はＰ４圧縮の１つが適用でき、ブロック８０８にはこのシナリオでは到達しないかもしれない。
【０１５２】
ｑＣｅｌｌが狭い範囲および同一タグを全般にわたって提示する場合、これはｑＣｅｌｌにエッジがない強力な証拠である。ブロック８２０の質問が肯定された場合、次にブロック８２２を検討してもよい。ブロック８２２では、ｑＣｅｌｌの各プレーンの全画素が同一の値を有するかどうか、決定されてもよい。同一の値を有する場合、Ｄ１圧縮の使用が、ＤＣＴベース圧縮より効率的だろう。従って、ｑＣｅｌｌのプレーンは、ブロック８２４でｐＣｅｌｌ毎のベースで圧縮されてもよい。そうでない場合、ブロック８１４で、ＤＣＴＱがｑＣｅｌｌのプレーンに適用される。
【０１５３】
図８は、１つの考えられるカラープレーン決定木を示す。他のこのような決定木も可能である。例えば、６００ｄｐｉ画像を圧縮する場合、ブロック８０４、８０６、８０８のみが利用されてもよい。
［ｂ．属性プレーン決定木］
【０１５４】
図９は、例示の実施形態に係る属性プレーン決定木９００を示す。この決定木は属性プレーンのｐＣｅｌｌの特性を検討するが、この属性プレーンｐＣｅｌｌの各構成要素は、１以上の対応するカラープレーンｐＣｅｌｌの画素値と、１対１で関連付けられているという了解の下にある。これらのｐＣｅｌｌのサイズは８×８でよいが、他のサイズが代わりに利用されてもよい。属性プレーンは１つのみで、決定木９００の全決定はプレーンベースでなされることも仮定される。しかしながら、代替の実施形態では異なるアプローチを取ることもあり得る。
【０１５５】
決定木８００と同様、Ｄ１ＤおよびＰ２Ｄ圧縮は決定木９００で明示的に言及されない。しかしながら、Ｄ１又はＰ２圧縮が検討、又は利用されるところで、Ｄ１ＤおよびＰ２Ｄ圧縮が同様に検討、又は利用されてもよい。従って、ブロック９０２、９０４、９０６、９０８は、Ｄ１ＤおよびＰ２Ｄ圧縮を検討および／または使用してもよい。連続したＤ１又はＤ１Ｄ符号化の実行も、決定木９００で明示的に検討されないが、それでも利用して構わない。
【０１５６】
ブロック９０２では、属性プレーンｐＣｅｌｌがＤ１圧縮に適しているかどうか決定される。Ｄ１圧縮に適している場合、ブロック９０４でＤ１圧縮が適用される。そうでない場合、ブロック９０６で、ｐＣｅｌｌがＰ２圧縮に適しているかどうか決定される。Ｐ２圧縮に適している場合、ブロック９０８でＰ２圧縮が適用されてもよい。
【０１５７】
ｐＣｅｌｌがＤ１又はＰ２圧縮のどちらも適さない場合、ブロック９１０で、ｐＣｅｌｌがＰ４圧縮に適しているかどうか決定してもよい。Ｐ４圧縮に適している場合、ブロック９１２でＰ４圧縮が適用されてもよい。そうでない場合、ブロック９１４でＤ６４圧縮が適用されてもよい。
【０１５８】
図９は、１つの考えられる属性プレーン決定木を示す。他のこのような決定木も可能である。
［ｃ．フォールバックモード］
【０１５９】
場合によっては、図６のパイプラインのような、印刷デバイスのパイプラインの動きは、さまざまな達成目標に基づいて、動的に修正されてもよい。具体的に言えば、印刷デバイスは、その圧縮比又はその解凍速度のいずれかが予め決められた閾値を満たしていない場合、フォールバックモードに入るように構成することができる。
【０１６０】
上述のように、ブロック６１６のストレージが少数のページ（例えば、２つの１２００ｄｐｉのＡ３のＣＭＹＫＡページ）を格納するように設計してもよいため、圧縮サイズを目標としてもよい。ブロック６１８のセルベース解凍は、印刷デバイスが解凍データを印刷できる速度よりも遅く作動するべきではないため、解凍速度も目標としてもよい。
【０１６１】
従って、印刷デバイスは、圧縮バッファーのオーバーフローおよび／または解凍速度のアンダーランを検知するように構成してもよい。圧縮バッファーのオーバーフローは、達成された圧縮比では不十分であることを示す、メモリ（例えば、ブロック６１６のストレージ）に書き込まれたバイト数が所定の閾値を越える場合に発生する。解凍速度のアンダーランは、ページの一部又は全て毎のｑＣｅｌｌのＤＣＴ符号化数が所定の閾値を超える場合に発生する。
【０１６２】
圧縮バッファーのオーバーフローの検出後、図８および／または図９の決定木は、常時少なくとも４：１圧縮を実現する圧縮技術が利用されるように修正されてもよい。例えば、カラープレーンでは、通常Ｐ４圧縮で符号化されるｐＣｅｌｌに対して、同一のｑＣｅｌｌの残りのｐＣｅｌｌと同様、Ｐ４圧縮の使用が除外され、ＤＣＴＱ圧縮に置き換えられてもよい。同様の方法で、ＤＣＴＰ圧縮もＤＣＴＱ圧縮に置き換えられてもよい。属性プレーンでは、属性構成要素につき１又は２ビットのみ保持される場合、Ｐ４圧縮はＤ６４圧縮に置き換えてもよい。
【０１６３】
解凍速度のアンダーランの検出後、図８のカラープレーン決定木は、ｔが１、２、又は３である、ｑＣｅｌｌのｔ程度のＤＣＴ操作を強制するように修正されてもよい。
［１０．インターリーブ符号化］
【０１６４】
セルベース圧縮の符号化されたアウトプットはインターリーブされてもよい。場合によって、インターリーブ符号化は非インターリーブ符号化よりも優れているかもしれない。
【０１６５】
このインターリービングは、（１）ｑＣｅｌｌにまたがるｐＣｅｌｌおよびプレーンの順序付け、（２）ダウンサンプリングがプレーン又は合成の決定かどうか、および（３）圧縮パフォーマンスを検討してもよい。後者の検討に対しては、ＤＣＴ圧縮およびパターン（非ＤＣＴ）圧縮で別々のプロセッサが利用されてもよい。ＤＣＴ圧縮プロセッサはパターンプロセッサと平行に稼働すること、およびＤＣＴプロセッサは、おそらくパターンプロセッサの８分の１の速度で、ゆっくり稼働してもよいことが仮定される。このように、インターリーブ形式は、ＤＣＴおよびパターンｐＣｅｌｌのさまざまな混合において、ＤＣＴプロセッサの高い利用度の維持をサポートしてもよい。
【０１６６】
これらの検討に基づいて、属性プレーンおよびカラープレーンのｑＣｅｌｌおよびｐＣｅｌｌは、インターリーブ方法で出力媒体（例えば、ブロック６０６のストレージおよび／またはブロック６１６のストレージ）に書き込まれてもよい。例として、カラーモデルがＣＭＹＡの場合、符号化されたｐＣｅｌｌの順序付けは、属性ｐＣｅｌｌ、続いてシアンｐＣｅｌｌ、続いてマゼンタｐＣｅｌｌ、続いてイエローｐＣｅｌｌ、続いて他の属性ｐＣｅｌｌ、続いて他のシアンｐＣｅｌｌ、続いて他のマゼンタｐＣｅｌｌ、続いて他のイエローｐＣｅｌｌ、などとしてよい。
【０１６７】
このような操作の疑似コード表現１０００は、図１０に示される。疑似コード表現１０００のライン１では、入力画像の各合成（複数プレーン）ｑＣｅｌｌが検討される。ライン３では、合成ｑＣｅｌｌは、属性プレーンが１番目、シアンプレーンが２番目、マゼンタプレーンが３番目、イエロープレーンが４番目、そしてＫプレーン（もしあれば）が５番目となるように、プレーンの順にソートされる。
【０１６８】
ライン４およびライン５では、各ｐＣｅｌｌの各プレーンが検討される。ライン７では、プレーンｑＣｅｌｌがサブサンプリング（ダウンサンプリング）されるべきかを決定する。もしするべきであれば、ライン８乃至１１で、プレーンｑＣｅｌｌ全体に対する単一のｐＣｅｌｌが符号化され、放出される（例えば、出力媒体に書き込まれる）。プレーンｑＣｅｌｌがダウンサンプリングされない場合、ライン１３で、（非ＤＣＴ技術を使用して符号化された）そのプレーンｐＣｅｌｌの各々が放出される。
【０１６９】
このようなインターリービング操作の一例は、図１１Ａおよび図１１Ｂに示される。図１１Ａは、属性、シアン、マゼンタ、およびイエローの各プレーンに対する一連の４つｑＣｅｌｌを示す。ｑＣｅｌｌ内の各ｐＣｅｌｌは、それぞれのｐＣｅｌｌ・ＩＤ（例えば、ａ、ｂ、ｃ、又はｄ）に関連付けられ、ボックスとして示される。ボックスは、ｑＣｅｌｌ番号およびｐＣｅｌｌ・ＩＤと同様、各個別のｐＣｅｌｌを圧縮するために利用される圧縮技術を含む。例えば、属性プレーンの１番目（左端）のｐＣｅｌｌはＰ２圧縮を使用して圧縮され、それはｐＣｅｌｌ・１ａからとなる。
【０１７０】
４つのｑＣｅｌｌ全般にわたって、属性プレーンは一貫してＰ２圧縮を使用して符号化され、シアンプレーンはＰ４圧縮を使用して符号化され、イエロープレーンはＤＣＴＰ圧縮を使用して符号化される。マゼンタプレーンは、しかしながら、Ｐ２およびＤ１圧縮を混合して使用し、符号化される。とりわけ、マゼンタプレーンの１３の連続した、同一のｐＣｅｌｌは、Ｄ１圧縮の実行で符号化される。
【０１７１】
図１１Ｂは、図１１ＡのｐＣｅｌｌおよびｑＣｅｌｌのインターリーブ符号化を示す。色および属性の各プレーンは、実行がより効率的な方法で符号化される場合以外、１つずつインターリーブされる。例えば、符号化は第１・ｑＣｅｌｌのｐＣｅｌｌから始まる。最初は属性プレーンの１ａ・ｐＣｅｌｌ、続いてシアンプレーンの１ａ・ｐＣｅｌｌ、マゼンタプレーンの１ａ・ｐＣｅｌｌ、イエロープレーンの１ａ・ｐＣｅｌｌ、属性プレーンの１ｂ・ｐＣｅｌｌ、シアンプレーンの１ｂ・ｐＣｅｌｌ、などである。
【０１７２】
Ｄ１圧縮を使用した１３のマゼンタセルの実行に関して、出力シーケンスの７番目のｐＣｅｌｌは、Ｄ１実行が始まることを示す。特に、このｐＣｅｌｌは１番目のｑＣｅｌｌからのＤ１実行の３つのｐＣｅｌｌの内の１つである。従って、このｐＣｅｌｌはＤ１圧縮を使用して符号化され、３つの連続した、同一のＤ１・ｐＣｅｌｌを表すことを示すため、３の値を持った長さフィールドを含んでもよい。従って、１ｂ、１ｃ、１ｄマゼンタｐＣｅｌｌは単一のｐＣｅｌｌとして符号化され、１ｃ、１ｄマゼンタｐＣｅｌｌは出力シーケンスから省略される。
【０１７３】
２番目のｑＣｅｌｌに関して、その中の１番目のマゼンタｐＣｅｌｌは、出力シーケンスの１７番目の位置に現れる。しかしながら、Ｄ１Ｃ符号化は、マゼンタＤ１・ｐＣｅｌｌの実行がこのｑＣｅｌｌを通じて継続することを示すために利用される。同じく、３番目のｑＣｅｌｌに関して、その中の１番目のマゼンタｐＣｅｌｌは、出力シーケンスの３０番目の位置に現れる。ここでも、Ｄ１Ｃ符号化は、マゼンタＤ１・ｐＣｅｌｌの実行がこのｑＣｅｌｌを通じて継続することを示すために利用される。２番目、３番目のｑＣｅｌｌの他のマゼンタｐＣｅｌｌは、この符号化で省略される。
【０１７４】
４番目のｑＣｅｌｌで、マゼンタＤ１・ｐＣｅｌｌの実行は２つ以上のｐＣｅｌｌで継続し、その後終了する。従って、出力シーケンスの４３番目の位置では、Ｄ１Ｅ符号化がＤ１実行の終了を示すために利用される。しかし、実際、実行に２つの残りの連続した、同一のマゼンタＤ１・ｐＣｅｌｌがあるため、第２のＤ１実行は符号化される。出力シーケンスの４４番目の位置では、マゼンタｐＣｅｌｌがＤ１圧縮を使用して符号化されても構わない。このｐＣｅｌｌは、２つの連続した、同一のＤ１・ｐＣｅｌｌを表すことを示すため、２の値を持った長さフィールドを含んでもよい。従って、４ｂマゼンタｐＣｅｌｌは符号化から省略されるが、４ｃ、４ｄマゼンタｐＣｅｌｌは含まれる。
【０１７５】
５７番目の出力位置での、最終的な符号化は、圧縮表現のこのセクションの終了を示すために利用される、エンドオブファイル（ＥＯＦ）である。
【０１７６】
インターリービング操作の他の例は、図１２Ａおよび図１２Ｂに示される。図１２Ａは、属性、シアン、マゼンタ、およびイエローの各プレーンに対する一連の４つのｑＣｅｌｌを示す。しかしながら、図１１Ａ、図１１Ｂの例とは異なり、図１２Ａの例は潜在的Ｄ１実行と同様に、ＤＣＴＱ符号化を含む。
【０１７７】
図１２Ｂは、図１２ＡのｐＣｅｌｌおよびｑＣｅｌｌのインターリーブ符号化を示す。色および属性の各プレーンは、実行がより効率的な方法で符号化される場合以外、１つずつインターリーブされる。ＤＣＴＱ符号化に関して、このような符号化は４つの実際のｐＣｅｌｌを包含するため、ｑＣｅｌｌ当たり、１つのＤＣＴＱ符号化のみを利用してもよい。従って、図１２Ｂにおいて、シアンＤＣＴＱ符号化はそれぞれ、２番目、１３番目、２３番目、および３３番目の出力位置に現れる。
【０１７８】
図１１Ｂのように、１３のマゼンタＤ１・ｐＣｅｌｌの実行は、図１２Ｂで２つの論理実行に圧縮される。しかしながら、６つの連続した、同一の属性Ｄ１・ｐＣｅｌｌの実行は、わずかに異なる方法で符号化される。実行はｑＣｅｌｌのｂおよびｄ・ｐＣｅｌｌから始まるため、実行の開始は潜在的に検討される。従って、これら２つのｐＣｅｌｌはそれぞれ、予想通り、２６番目および３０番目の出力位置で符号化される。しかしながら、３２番目の出力位置では、４番目のｑＣｅｌｌにある、この実行の４つＤ１セルに対して、Ｄ１Ｃ符号化が利用される。そして、４２番目の出力位置では、Ｄ１Ｅ符号化が実行の終了を示すために利用され、４３番目の出力位置では、ＥＯＦ符号化が圧縮表現のこのセクションの終了を示すために利用される。
【０１７９】
図１１Ａ、図１１Ｂ、図１２Ａ、および図１２Ｂは、説明のために提供される。他の符号化が本明細書の実施形態によりサポートされてもよく、実施形態の要旨を逸脱しない範囲で、これらの符号化に変形がなされてもよい。
［１１．セルベース解凍の例］
【０１８０】
一旦、例えば、上述したような圧縮方法および符号化を使用して、多数のｐＣｅｌｌおよび／またはｑＣｅｌｌが圧縮されれば、これらは効率的に格納、および／またはケーブル又はネットワークを通して送信されてもよい。とはいえ、ある時点で、ｐＣｅｌｌおよび／またはｑＣｅｌｌは、元の画像又は元の画像に近似しているものに解凍されてもよい。本明細書において説明されているセルベース圧縮技術は非可逆になり得るため、解凍された画像は、元の画像とは、少なくともある程度、異なるかもしれない。しかしながら、多数のシナリオにおいて、この差異は人間により認識される可能性が低い、又は元の画像の許容範囲のバージョンであると見なされるであろう。
【０１８１】
上述のような圧縮符号化で符号化されたｐＣｅｌｌおよび／またはｑＣｅｌｌは、以下のように複合および解凍することができる。特定のｐＣｅｌｌ又はｑＣｅｌｌ符号化に対し、オペコードが読み取られる。オペコードの値に基づいて、任意の適用可能なオプション、引数、ビットマップなどが、オペコードに続くビットから決定され得る。これらのパラメータから、ｐＣｅｌｌ又はｑＣｅｌｌの解凍バージョンが再構築され得る。そして、画像が再構築されるまで、次のオペコードが読み取られたりする。
【０１８２】
例えば、オペコードが００１の場合、Ｄ１符号化を示し、Ｖ’ビットおよび引数フィールドは、圧縮された構成要素の値を決定するために読み取られてもよい。長さビットもまた、ランレングスが存在するかどうか決定するために読み取られてもよい。そして、ランレングスと等しい多数のセルが、符号化の値フィールドにより、又は値フィールドのキャッシュされたバージョンに示された値を提示する各セルの全画素で作成される。
【０１８３】
オペコードが０００の場合、Ｄ１Ｄ符号化を示し、Ｖビットは圧縮された構成要素の値を決定するために読み取られ、長さビットはランレングスが存在するかどうか決定するために読み取られてもよい。そして、ランレングスに等しい多数のセルが、Ｖビットにより示されたデフォルト値を提示する各セルの全画素で作成される。
【０１８４】
オペコードが０１１の場合、Ｐ２符号化を示し、オプション、引数、およびビットマップが読み取られてもよい。Ｖ’ビットが１の場合、セルの２つの値が決定されてもよい。そして、セルは、線図およびビットマップに従った２つの値の内の１つを取る各画素で作成されてもよい。線図が存在しない場合、その前のＰ２セルの線図およびビットマップが利用される。
【０１８５】
オペコードが０１０の場合、Ｐ２Ｄ圧縮を示し、セルは線図およびビットマップに従った２つの値の内の１つを取る各画素で作成されてもよい。線図が存在しない場合、その前のＰ２セルの線図およびビットマップが利用される。
【０１８６】
オペコードが１００の場合、Ｐ４圧縮を示し、線図および値引数がビットマップと同様に読み取られてもよい。そして、セルは線図およびビットマップに従った４つの色値の内の１つを取る各画素で作成されてもよい。
【０１８７】
オペコードが１１の場合、ＤＣＴＰ圧縮を示し、ＤＣＴＰ圧縮方法のビットマップが読み取られ、セルはこのＤＣＴＰ符号化に従って作成されてもよい。
【０１８８】
オペコードが１０１の場合、ＤＣＴＱ圧縮を示し、ＤＣＴＱ圧縮方法のビットマップが読み取られ、ｐＣｅｌｌはこのＤＣＴＱ符号化に従って作成されてもよい。そして、ｐＣｅｌｌの各構成要素は、同一の値の構成要素の２×２ブロックにより置き換えられてもよい。結果、ＤＣＴＱダウンサンプリング処理の近似反転であるｑＣｅｌｌとなる。
【０１８９】
オペコードが１の場合、Ｄ１Ｃ圧縮を示し、最新のＤ１又はＤ１Ｄセルがコピーされる。オペコードが０の場合、Ｄ１Ｅ圧縮を示し、この時点のＤ１又はＤ１Ｄ実行が終了したものとみなされる。
【０１９０】
オペコードが１１の場合、Ｄ６４圧縮を示し、属性当たりのビット数が決定され、それに応じて属性フィールドが複号化される。属性当たりのビット数は、印刷デバイスのタイプ、および解凍が起こっているパイプラインの場所次第であってよい。
［１２．パフォーマンス結果の例］
【０１９１】
本明細書において開示されたセルベース圧縮（ＣＢＣ）技術の圧縮パフォーマンスは、ＪＰＥＧベースの圧縮、および分割ランレングス符号化（ＳＲＬＥ）ベースの圧縮（可逆技術）の圧縮パフォーマンスと比較された。テストスイートは、さまざまな量のテキスト、線画、および画像内容を含む４０８ページで構成された。
2016149762.tif 000012
【０１９２】
表１０は、６００ｄｐｉおよび１２００ｄｐｉの画像両方に対する、ＣＢＣ、ＪＰＥＧ、およびＳＲＬＥにより達成された圧縮比を提供する。これらの結果には、各技術で達成された、最大、最小、平均、および中央値の圧縮比が含まれる。
【０１９３】
本明細書において開示されたＣＢＣ技術は、６００ｄｐｉおよび１２００ｄｐｉの両画像に対して、大幅に優れた最大圧縮比を提供する。ＣＢＣ技術は、１２００ｄｐｉの画像に対して、優れた最小圧縮比も提供するが、６００ｄｐｉの画像に対しては、ＪＰＥＧ技術がわずかに良い最小圧縮比を提供する。
【０１９４】
何より、本明細書において開示されたＣＢＣ技術は、ＪＰＥＧおよびＳＲＬＥより極めて良い平均および中央値の圧縮比を提供する一方、ＪＰＥＧの画質よりも優れた画質を提供する。結果として、ＣＢＣ技術は印刷および印刷デバイス技術において、著しい改良となる。
［１３．操作の例］
【０１９５】
図１３、図１４、および図１５は、例示の実施形態のフローチャートである。これらのフローチャートにより説明されるステップは、印刷デバイス１００のような１以上の印刷デバイス、および／またはコンピューティング・デバイス３００のようなコンピューティング・デバイスによって実行してもよい。さらに、各個別のステップの局面は、多数のコンピューティング又は印刷デバイス間で分布してもよい。
【０１９６】
本明細書において利用される用語に関して、ｍ×ｎ属性セルは属性プレーンのプレーンｐＣｅｌｌに言及し、ｍ×ｎ画素セルはカラープレーンのプレーンｐＣｅｌｌに言及してもよい。さらに、ａ×ｂ属性セルは属性プレーンのプレーンｑＣｅｌｌに言及し、ａ×ｂ画素セルはカラープレーンのプレーンｑＣｅｌｌに言及してもよい。全般にわたって、ａはｍよりも大きく、ｂはｎよりも大きいことが仮定されている。
【０１９７】
図１３は、属性プレーンのセル、および１以上のカラープレーンのセルのインターリーブ圧縮に関するステップを一般的に示す。しかしながら、これらステップは追加の目的で同様に利用されてもよい。図５乃至図１２Ｂに関連して説明されている操作は、このフローチャートで明示的に又は暗黙的に言及されてもよい。例えば、図１３のステップは、図６のブロック６０４および／または６１４で、印刷デバイスのパイプラインの他の場所で、又はホストコンピュータにより、行われるかもしれない。
【０１９８】
ステップ１３００では、入力画像からｍ×ｎ画素セルが得られてもよい。入力画像はｍ×ｎ画素より多くの画素を含んでもよく、ｍ×ｎ画素セルのｍ×ｎ画素の各々は少なくとも１つの色値に関連付けられてもよい。
【０１９９】
ステップ１３０２では、おそらくｍ×ｎ画素セルに基づいて、ｍ×ｎ属性セルが得られてもよい。ｍ×ｎ属性セルの構成要素は、１対１でｍ×ｎ画素セルのそれぞれの画素と関連付けられていてもよいし、構成要素はこれらの関連付けられている画素に関連するそれぞれの制御データを識別してもよい。属性セルの構成要素は、属性配列および／または属性バイトでもよい。
【０２００】
ステップ１３０４では、ｍ×ｎ画素セルが非可逆で圧縮され、ｍ×ｎ属性セルが可逆で圧縮されてもよい。非可逆圧縮はＤＣＴベースの圧縮で、可逆圧縮は本明細書において説明されている他の圧縮技術のいずれかでよい。ｍ×ｎ画素セルの圧縮は、ｍ×ｎ属性セルの少なくとも一部に基づいてもよい（例えば、圧縮は、ｍ×ｎ属性セルにより符号化されるように、ｍ×ｎ画素セルが表すオブジェクトのタイプによってもよい）。ステップ１３０６では、圧縮されたｍ×ｎ画素セルおよび圧縮されたｍ×ｎ属性セルのインターリーブ表現が、出力媒体に書き込まれてもよい。このインターリーブ表現は、図１１Ａ、図１１Ｂ、図１２Ａ、および図１２Ｂの本開示に従ったフォーム、又は他のフォームを取ってもよい。
【０２０１】
実施形態によっては、制御データのユニットは、ｍ×ｎ画素セルの特定の画素に関連付けられてもよい。制御データは、特定の画素が画像オブジェクトタイプ、ベクトル・オブジェクトタイプ、又はテキスト・オブジェクトタイプを表すかどうかを示す、１以上のビットであってよい。圧縮されたｍ×ｎ画素セルおよび圧縮されたｍ×ｎ属性セルは解凍され、ハーフトーン・スクリーンが１以上のビットに基づいて選択されてもよい。ｍ×ｎ画素セルは特定の画素に適用される、選択されたハーフトーン・スクリーンに（おそらく入力画像の残りと一緒に）印刷されてもよい。
【０２０２】
代わりに、又は加えて、ｍ×ｎ画素セルの特定の画素に関連付けられている制御データは、特定の画素が印刷手順又はスキャン手順の一部として形成されたかどうかを示す、１以上のビットを含んでもよい。圧縮されたｍ×ｎ画素セルおよび圧縮されたｍ×ｎ属性セルは解凍され、ハーフトーン・スクリーンが１以上のビットに基づいて選択されてもよい。ｍ×ｎ画素セルは、特定の画素に適用される、選択されたハーフトーン・スクリーンに（おそらく入力画像の残りと一緒に）印刷されてもよい。
【０２０３】
代わりに、又は加えて、ｍ×ｎ画素セルの特定の画素に関連付けられている制御データは、特定の画素が圧縮前に中性色値を取ったことを示す、１以上のビットを含んでもよい。圧縮されたｍ×ｎ画素セルおよび圧縮されたｍ×ｎ属性セルは、解凍されてもよい。おそらく、特定の画素が圧縮前に中性色値を取ったことを示す１以上のビットを受けて、特定の画素の色値が同一でないことが決定され、少なくとも色値の１つは、色値が同一になるように変更されてもよい。
【０２０４】
代わりに、又は加えて、ｍ×ｎ画素セルの特定の画素に関連付けられている制御データは、特定の画素が圧縮前に非中性色値を取ったことを示す、１以上のビットを含んでもよい。圧縮されたｍ×ｎ画素セルおよび圧縮されたｍ×ｎ属性セルは、解凍されてもよい。おそらく、特定の画素が圧縮前に非中性色値を取ったことを示す１以上のビットを受けて、特定の画素の色値が同一であると決定され、少なくとも色値の１つは、色値が同一とならないように変更されてもよい。
【０２０５】
代わりに、又は加えて、ｍ×ｎ画素セルの特定の画素に関連付けられている制御データは、特定の画素が圧縮前に同一の純粋で極端な色値（ピュアエクストリーム色値）を取ったことを示す１以上のビットを含んでもよい。圧縮されたｍ×ｎ画素セルおよび圧縮されたｍ×ｎ属性セルは、解凍されてもよい。おそらく、特定の画素が圧縮前に同一の純粋で極端な色値を取ったことを示す１以上のビットを受けて、特定の画素の色値が同一の純粋で極端な色値でないことが決定され、少なくとも色値の１つは、色値が同一の純粋で極端な色値となるように変更されてもよい。
【０２０６】
代わりに、又は加えて、ｍ×ｎ画素セルの特定の画素に関連付けられている制御データは、特定の画素がデジタルオブジェクトに重なり合うかどうかを示す、１以上のビットを含んでもよい。ｍ×ｎ画素セルの非可逆での圧縮には、（１）特定の画素、又は（２）デジタルオブジェクトからの交換画素、のどちらかの選択、および選択された画素の圧縮を含んでもよい。選択は１以上のビットに基づいてもよい。場合によっては、１以上のビットはｍ×ｎ属性セルの可逆圧縮から省略されてもよい。
【０２０７】
代わりに、又は加えて、ｍ×ｎ画素セルの特定の画素に関連付けられている制御データは、特定の色変換が特定の画素に適用されるかどうかを示す、１以上のビットを含んでもよい。ｍ×ｎ画素セルの非可逆での圧縮の前に、特定の画素は、特定の色変換に基づいて、１つのカラーモデルから他のカラーモデルに変換されてもよい。場合によっては、１以上のビットはｍ×ｎ属性セルの可逆圧縮から省略されてもよい。
【０２０８】
ｍ×ｎ属性セルの可逆での圧縮には、ｍ×ｎ属性セルの各構成要素が同一の値を取ることの決定、およびおそらくこの決定に基づく、（例えば、Ｄ１又はＤ１Ｄ圧縮を使用した）単一値のオペコード、および同一の値の指示を使用した、ｍ×ｎ属性セルの符号化を含んでもよい。代わりに、ｍ×ｎ属性セルの可逆での圧縮には、ｍ×ｎ属性セルの各構成要素が２つの異なる値の１つを取ることの決定、およびおそらくこの決定に基づく、（例えば、Ｐ２又はＰ２Ｄ圧縮を使用した）２値のオペコード、２つの異なる値の指示、およびどの構成要素が２つの異なる値の各々を取るかを示すビットマップを使用したｍ×ｎ属性セルの符号化を含んでもよい。
【０２０９】
さらに他の局面では、ｍ×ｎ属性セルの可逆での圧縮には、ｍ×ｎ属性セルの各構成要素が３つ又は４つの異なる値の１つを取ることの決定、およびおそらくこの決定に基づく、（例えば、Ｐ４圧縮を使用した）４値のオペコード、３つ又は４つの異なる値の指示、およびどの構成要素が３つ又は４つの異なる値の各々を取るかを示すビットマップを使用したｍ×ｎ属性セルの符号化を含んでもよい。他の代替手段では、ｍ×ｎ属性セルの可逆での圧縮には、ｍ×ｎ属性セルの構成要素が少なくとも５つの異なる値を取ることの決定、およびおそらくこの決定に基づく、（例えば、Ｄ６４圧縮を使用した）多値のオペコード、およびｍ×ｎ属性セルの各構成要素により取得された値の指示を使用したｍ×ｎ属性セルの符号化を含んでもよい。
【０２１０】
図１４は、カラープレーンのセルの圧縮に関するステップを一般的に示す。しかしながら、これらのステップは、追加の目的で同様に利用されてもよい。図５乃至図１２Ｂに関連して説明されている操作は、このフローチャートで明示的に又は暗黙的に言及されてもよい。例えば、図１４のステップは、図６のブロック６０４および／または６１４で、印刷デバイスのパイプラインの他の場所で、又はホストコンピュータにより、行われるかもしれない。
【０２１１】
このフローチャートは単一のカラープレーンの圧縮を含むため、（カラープレーン決定木８００の決定のような）決定は、プレーンベースで行われる。とはいえ、図１４のステップは、多数のカラープレーンを同時に検討する合成操作の一部として行われる可能性がある。
【０２１２】
ステップ１４００では、入力画像からａ×ｂ画素マクロセルを得てもよい。ａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルを含んでもよい。ａ×ｂ画素マクロセルのａ×ｂ画素はそれぞれの色値を有し、各オブジェクトタイプタグに関連付けられてもよい。これらのオブジェクトタイプタグはそれぞれ、例えば、属性配列の１以上のビットでもよい。
【０２１３】
ステップ１４０２では、おそらく各色値および各オブジェクトタイプタグに基づいて、圧縮技術は（１）ａ×ｂ画素マクロセル全体で圧縮する、又は（２）４つの非オーバーラップｍ×ｎ画素セルの各々を別々に圧縮することにより、ａ×ｂ画素マクロセルを圧縮する、のどちらかが選択されてもよい。
【０２１４】
ステップ１４０４では、ａ×ｂ画素マクロセルは、選択された圧縮技術に従って圧縮されてもよい。ステップ１４０６では、圧縮されたａ×ｂ画素マクロセルの表現が、コンピュータ読み取り可能な出力媒体に書き込まれてもよい。
【０２１５】
実施形態によっては、選択された圧縮技術は、ａ×ｂ画素マクロセルを全体で圧縮する。この処理は、ａ×ｂ画素マクロセルのダウンサンプリングされたｍ×ｎ画素セルへのダウンサンプリング、およびダウンサンプリングされたｍ×ｎ画素セルの（例えば、ＤＣＴＱ圧縮を使用した）非可逆での圧縮を含んでもよい。
【０２１６】
ａ×ｂ画素マクロセルが全体で圧縮される場合、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値を超えることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素がそれぞれ同一のオブジェクトタイプを表すことを示すことの決定、（３）ａ×ｂ画素の各色値が、ｄは少なくとも２である、少なくともｄ色を含むことの決定、および（４）ａ×ｂ画素マクロセルを全体で圧縮するための選択を含んでもよい。
【０２１７】
代わりに、ａ×ｂ画素マクロセルが全体で圧縮される場合、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値以内であることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことの決定、（３）ａ×ｂ画素の各色値が、ｄは少なくとも２である、少なくともｄ色を含むことの決定、および（４）ａ×ｂ画素マクロセルを全体で圧縮するための選択を含んでもよい。
【０２１８】
他の代替手段では、ａ×ｂ画素マクロセルが全体で圧縮される場合、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値以内であることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素がそれぞれ同一のオブジェクトタイプを表すことを示すことの決定、（３）ａ×ｂ画素の各色値が複数の色を含んでいることの決定、および（４）ａ×ｂ画素マクロセルを全体で圧縮するための選択を含んでもよい。
【０２１９】
追加の実施形態では、選択された圧縮技術は、４つの非オーバーラップｍ×ｎ画素セルの各々を別々に、（例えば、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、又はＰ４圧縮を使用して）可逆で圧縮する。
【０２２０】
４つの非オーバーラップｍ×ｎ画素セルが可逆で別々に圧縮される場合、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値を超えることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素はそれぞれ同一のオブジェクトタイプを表すことを示すことの決定、（３）１以上のｍ×ｎ画素セルの各々に対する各色値が、ｄは少なくとも２である、ｄ未満の色を含むことの決定、および（４）１以上のｍ×ｎ画素セルの各々を可逆で別々に圧縮するための選択を含んでもよい。
【０２２１】
代わりに、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値以内であることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグがａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことの決定、（３）１以上のｍ×ｎ画素セルの各々に対する各色値が、ｄは少なくとも２である、ｄ未満の色を含むことの決定、および（４）１以上のｍ×ｎ画素セルの各々を可逆で別々に圧縮するための選択を含んでもよい。
【０２２２】
他の代替手段では、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値を超えることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことの決定、（３）１以上のｍ×ｎ画素セルの各々に対する各色値が、ｄは少なくとも２である、ｄ未満の色を含むことの決定、および（４）１以上のｍ×ｎ画素セルの各々を可逆で別々に圧縮するための選択を含んでもよい。
【０２２３】
さらに他の代替手段では、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値以内であることの決定、（２）ａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素が同一のオブジェクトタイプを表すことを示すことの決定、（３）ａ×ｂ画素の各色値がそれぞれ、同一の色値を表すことの決定、および（４）４つの非オーバーラップｍ×ｎ画素セルの各々を可逆で別々に圧縮するための選択を含んでもよい  。
【０２２４】
実施形態によっては、選択された圧縮技術は、４つの非オーバーラップｍ×ｎ画素セルの１以上のｍ×ｎ画素セルを非可逆（例えば、ＤＣＴＰ圧縮）で別々に圧縮してもよい。
【０２２５】
４つの非オーバーラップｍ×ｎ画素セルが非可逆で別々に圧縮される場合、圧縮技術の選択には、（１）ａ×ｂ画素の各色値の範囲が所定の非ゼロ閾値を超える、又はａ×ｂ画素に対する各オブジェクトタイプタグが、ａ×ｂ画素のいくつかが異なるオブジェクトタイプを表すことを示すことの決定、（２）ａ×ｂ画素に対する各色値が、５未満の色を含むことの決定、（３）１以上のｍ×ｎ画素セルの各々に対する各色値が、ｄは少なくとも２である、少なくともｄ色を含むことの決定、および（４）１以上のｍ×ｎ画素セルの各々を非可逆で別々に圧縮するための選択を含んでもよい。
【０２２６】
圧縮されたａ×ｂ画素マクロセルは、ａ×ｂ画素マクロセルを圧縮するために利用された圧縮技術を反転することにより、解凍してもよい。従って、圧縮されたａ×ｂ画素マクロセルの解凍は、第２のａ×ｂ画素マクロセルをもたらしてもよく、第２のａ×ｂ画素マクロセルの画素値は、ａ×ｂ画素マクロセルの画素値と同一又は近似のどちらかでよい。
【０２２７】
実施形態によっては、第２のａ×ｂ画素マクロセルおよび第３のａ×ｂ画素マクロセルは、入力画像から取得してもよい。第２および第３のａ×ｂ画素マクロセルは、それぞれ４つの非オーバーラップｍ×ｎ画素セルを含み、第２および第３のａ×ｂ画素マクロセルの各々の画素はそれぞれ色値も有してもよいし、各オブジェクトタイプタグに関連付けられてもよい。これらの実施形態において、圧縮技術は、第２のａ×ｂ画素マクロセルの４つの非オーバーラップｍ×ｎ画素セル、および第３のａ×ｂ画素マクロセルの４つの非オーバーラップｍ×ｎ画素セルの各々を互いに別々に、そしてａ×ｂ画素マクロセルの４つの非オーバーラップｍ×ｎ画素セルから圧縮することにより、第２および第３のａ×ｂ画素マクロセルの各々を圧縮するために選択されてもよい。従って、第２のａ×ｂ画素マクロセルの４つの非オーバーラップｍ×ｎ画素セルおよび第３のａ×ｂ画素マクロセルの４つの非オーバーラップｍ×ｎ画素セルの各々は、互いに別々に、そしてａ×ｂ画素マクロセルの４つの非オーバーラップｍ×ｎ画素セルから圧縮されてもよい。圧縮された第２のａ×ｂ画素マクロセルおよび圧縮された第３のａ×ｂ画素マクロセルの表現は、コンピュータ読み取り可能な出力媒体に書き込んでもよい。
【０２２８】
図１５は、属性プレーンおよび１以上のカラープレーンのセルの圧縮表現をインターリービングするためのステップを一般的に示す。しかしながら、これらのステップは追加の目的で同様に利用されてもよい。図５乃至図１２Ｂに関連して説明されている操作は、このフローチャートに明示的に又は暗黙的に言及されてもよい。例えば、図１５のステップは、図６のブロック６０４および／または６１４で、印刷デバイスのパイプラインの他の場所で、又はホストコンピュータにより行われるかもしれない。
【０２２９】
ステップ１５００では、ａ×ｂ画素マクロセルは、１以上のカラープレーンを持つ入力画像から取得してもよい。ａ×ｂ属性マクロセルも取得してもよい。ａ×ｂ画素マクロセルは４つの非オーバーラップｍ×ｎ画素セルを含み、ａ×ｂ属性マクロセルは４つの非オーバーラップｍ×ｎ属性セルを含んでもよい。ａ×ｂ画素マクロセルのａ×ｂ画素は各色値に関連付けられ、ａ×ｂ属性マクロセルの構成要素は１対１でａ×ｂ画素マクロセルの各画素に関連付けられてもよい。
【０２３０】
ステップ１５０２では、４つの非オーバーラップｍ×ｎ属性セルにそれぞれ関連付けられている、４つの属性プレーン出力値が決定されてもよい。ステップ１５０４では、非オーバーラップｍ×ｎ画素セルに対する１乃至４つのカラープレーン出力値が決定されてもよい。ステップ１５０６では、４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現が、コンピュータ読み取り可能な出力媒体に書き込まれてもよい。このインターリーブ表現は、図１１Ａ、図１１Ｂ、図１２Ａ、および／または図１２Ｂの本開示に従ったフォーム、又は他のフォームを取ってもよい。
【０２３１】
さらに、第２のａ×ｂ画素マクロセルも、入力画像から得られてもよい。第２のａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルの第２のセットを含んでもよく、第２のａ×ｂ画素マクロセルのａ×ｂ画素も、各色値に関連付けられおり、ａ×ｂ属性マクロセルの構成要素は、１対１で第２のａ×ｂ画素マクロセルの各画素に関連付けられている。第３のａ×ｂ画素マクロセルも、入力画像から得られてもよい。第３のａ×ｂ画素マクロセルは、４つの非オーバーラップｍ×ｎ画素セルの第３のセットを含んでもよく、第３のａ×ｂ画素マクロセルのａ×ｂ画素も、各色値に関連付けられており、ａ×ｂ属性マクロセルの構成要素は、１対１で第３のａ×ｂ画素マクロセルの各画素に関連付けられている。操作はさらに、４つの非オーバーラップｍ×ｎ画素セルの第２のセットに対する、１乃至４つのカラープレーン出力値の第２のセットの決定、および４つの非オーバーラップｍ×ｎ画素セルの第３のセットに対する、１乃至４つのカラープレーン出力値の第３のセットの決定を含んでもよい。インターリーブ表現も、決定された１乃至４つのカラープレーン出力値の第２のセット、および決定された１乃至４つのカラープレーン出力値の第３のセットを含んでもよい。
【０２３２】
実施形態によっては、属性プレーン出力値およびカラープレーン出力値の各々は、それぞれオペコードおよびデータを含む。さらに、４つの属性プレーン出力値は、それぞれ４つの非オーバーラップｍ×ｎ属性セルの（例えば、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、Ｐ４、又はＤ６４圧縮を使用した）可逆圧縮に基づいて決定されてもよい。
【０２３３】
場合によって、非オーバーラップｍ×ｎ画素セルに対するカラープレーン出力値の決定には、４つの非オーバーラップｍ×ｎ画素セルの各々が（例えば、Ｄ１、Ｄ１Ｄ、Ｐ２、Ｐ２Ｄ、Ｐ４、又はＤＣＴＰ圧縮を使用して）非可逆又は可逆で別々に圧縮されることの決定、および４つのカラープレーン出力値、つまり４つの非オーバーラップｍ×ｎ画素セルの各々に対する１つのカラープレーン出力値の決定を含んでもよい。代わりに、非オーバーラップｍ×ｎ画素セルに対するカラープレーン出力値の決定には、ａ×ｂ画素マクロセルがダウンサンプリングされ、（例えば、ＤＣＴＱ圧縮を使用して）非可逆で圧縮されることの決定、およびダウンサンプリングされ、圧縮されたａ×ｂ画素マクロセルに対する１つの出力値の決定を含んでもよい。
【０２３４】
実施形態によっては、少なくとも２つのカラープレーン出力値が（例えば、Ｄ１、Ｄ１Ｄ、Ｐ２、又はＰ２Ｄ圧縮を使用して）決定される。４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、カラープレーン出力値の第１のカラープレーン出力値および第２のカラープレーン出力値が同一の方法により可逆で圧縮されることの決定、およびオペコード、キャッシュミスインディケータ、およびデータフィールドを有する第１のカラープレーン出力値による表現、およびオペコードおよびキャッシュヒットインディケータを有する第２のカラープレーン出力値による表現を含んでもよい。キャッシュヒットインディケータは、第２のカラープレーン出力値が第１のカラープレーン出力値のデータフィールドを使用することを示してもよい。
【０２３５】
代わりに、又は加えて、４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、カラープレーン出力値のうち特定のカラープレーン出力値が、（１）ｎ−１ビット線図、（２）第１のｍビットライン、および（３）１の値を取るｎ−１ビット線図の各ビット当たりの、別の各ｍビットライン、を使用して、可逆で圧縮されることの決定を含んでもよい。そして、特定のカラープレーン出力値は、オペコード、少なくとも２つの異なる画素値、ｎ−１ビット線図、第１のｍビットライン、および各ｍビットラインで（例えば、Ｐ２圧縮を使用して）表されてもよい。
【０２３６】
別の場合、４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、カラープレーン出力値のうち特定のカラープレーン出力値が、（１）ｎ−１ビット線図、（２）第１の２ｍビットライン、および（３）１の値を取るｎ−１ビット線図の各ビット当たりの、別の各２ｍビットライン、を使用して、可逆で圧縮されることの決定を含んでもよい。そして、特定のカラープレーン出力値は、オペコード、少なくとも４つの異なる画素値、ｎ−１ビット線図、第１の２ｍビットライン、および各２ｍビットラインで（例えば、Ｐ４圧縮を使用して）表されてもよい。
【０２３７】
実施形態によっては、４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、第１の出力値および第２の出力値がコンピュータ読み取り可能な出力媒体で表され、第１の出力値および第２の出力値に関連付けられているｍ×ｎセルが（例えば、キャッシングを伴うＰ２圧縮を使用して）同一のビットマップで表されることの決定を含んでもよい。そして、第２の出力値は、第２の出力値が専用のビットマップを含まない場合、オペコード、２つ以上の色値、および第１の出力値の第１のビットマップへの参照で表されてもよい。
【０２３８】
さらに、４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、ｐが１、２、３、又は４である、（１）４つの非オーバーラップｍ×ｎ画素セルのうちのｐが、同一の方法により可逆で圧縮されること、および（２）色値を互いに同一の場所で含むことの決定を含んでもよい（例えば、ｑＣｅｌｌ内のＤ１・ｐＣｅｌｌの実行）。そして、決定されたカラープレーン出力値は、少なくともオペコードおよびｐの値として表されてもよい。
【０２３９】
場合によって、４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、４つの非オーバーラップｍ×ｎ画素セルが、相互に同一の方法で、および同一のカラープレーンの予め書き込まれたｍ×ｎ画素セルで、可逆で圧縮されることの決定を含んでもよい。そして、決定されたカラープレーン出力値は、決定されたカラープレーン出力値が（例えば、Ｄ１Ｃ圧縮を使用した）同一の符号化の実行であることを示すオペコードとして表されてもよい。４つの属性プレーン出力値および決定されたカラープレーン出力値のインターリーブ表現の書き込みには、さらに、ｐが０、１、２、又は３である、４つの非オーバーラップｍ×ｎ画素セルのうちのｐは、（１）前のｍ×ｎ画素セルが同一の符号化の実行として表された場合、コンピュータ読み取り可能な出力媒体に書き込まれた、前のｍ×ｎ画素セルとして同一の方法により可逆で圧縮されること、および（２）任意の残りの４−ｐ非オーバーラップｍ×ｎ画素セルより前に、コンピュータ読み取り可能な出力媒体に書き込まれること、の決定を含んでもよい。そして、決定されたカラープレーン出力値は、（１）（例えば、Ｄ１Ｅ符号化を使用した）同一の符号化の実行の終了を示す第１のオペコード、および（２）ｐが０よりも大きい場合、第２のオペコードおよびｐの値（例えば、ｑＣｅｌｌ内のＤ１・ｐＣｅｌｌの実行）として表されてもよい。
［１４．結論］
【０２４０】
本出願において記述されている具体的な実施形態に関して、本開示は限定されるべきではなく、それらはいろいろな態様の実例として意図されている。当業者にとって明白であるように、本開示の主旨と範囲から逸脱することなく多くの変更および変形をすることが可能である。本記載に列挙されていることに加え、本開示の範囲内の機能的に等価な方法および装置は前述の記載から明白であろう。そのような変更および変形は、添付された請求項の範囲内に入るように意図されている。
【０２４１】
図面における、任意のすなわち全てのラダー図、シナリオ、およびフローチャートに関しておよび本記載で述べられたように、各ブロックおよび／または通信は、例示の実施形態に従って情報を処理しおよび／または情報を送信することを表してもよい。他の実施形態もそのような例示の実施形態の範囲に含まれてもよい。さらに、より多くの又はより少ないブロックおよび／または機能が、本記載に記述されているどのラダー図、シナリオ、およびフローチャートと共に使用されてもよいし、また当該ラダー図、シナリオ、およびフローチャートは、部分的に又は全体的にお互いに結合されてもよい。
【０２４２】
情報の処理を表すステップ又はブロックは、本記載の方法又は技術の具体的な論理機能を実行するように構成することが可能な回路に相当してもよい。それに代えてまたはさらに、情報の処理を表すステップ又はブロックは、モジュール、セグメント、又はプログラムコードの一部分（関連するデータを含めて）に相当してもよい。プログラムコードは、方法又は技術における具体的な論理機能又は動作を実行するための、処理部により実行可能な一つ以上の命令を含んでもよい。プログラムコードおよび／または関連するデータは、ディスクドライブ、ハードドライブ、又はその他の記憶媒体を含む記憶装置等の任意の種類のコンピュータ読み取り可能な媒体に格納してもよい。
【０２４３】
コンピュータ読み取り可能な媒体は、また、レジスタメモリ、プロセッサキャッシュ、および／またはランダムアクセスメモリ（ＲＡＭ）のような短期間データを格納するコンピュータ読み取り可能な媒体等の、非一時的でコンピュータ読み取り可能な媒体を含んでもよい。コンピュータ読み取り可能な媒体は、また、例えば、リードオンリーメモリー（ＲＯＭ）、光学又は磁気ディスク、および／またはコンパクトディスク・リードオンリーメモリー（ＣＤ―ＲＯＭ）のような、二次的又は持続的長期記憶装置等、より長期間プログラムコードおよび／またはデータを格納する非一時的でコンピュータ読み取り可能な媒体を含んでもよい。コンピュータ読み取り可能な媒体は、また、他の揮発性又は不揮発性記憶システムでもあってもよい。コンピュータ読み取り可能な媒体は、例えば、コンピュータ読み取り可能な記憶媒体および／または有形の記憶デバイスと考えてもよい。
【０２４４】
加えて、本明細書、図面、請求項内のいずれの構成要素、ブロック、又はステップの列挙も、明確さを目的としたものである。従って、このような列挙は、これらの構成要素、ブロック、又はステップが特定の配置にこだわる、又は特定の順序で実行されることを要求又は意味すると解釈すべきではない。
【０２４５】
本記載においてさまざまな態様および実施形態が開示されてきたが、他の態様および実施形態も当業者にとって明白であろう。本記載において開示されたさまざまな態様および実施形態は、例示目的であって限定することを意図するものではなく、真の範囲と主旨は以下の請求項により示されている。
【符号の説明】
【０２４６】
１００  印刷デバイス
２００  コンピューティング・デバイス構成要素
２０２  処理部
２０４  メモリ
２０６  入出力部
２０８  システムバス
３００  コンピューティング・デバイス
３０２  スキャナ部
３０４  印刷部
３０６  スキャン〜ホストデータパス
３０８  ホスト〜印刷データパス
３１０  スキャン〜印刷データパス
【図１】
2016149762.tif 000013
【図２】
2016149762.tif 000014
【図３】
2016149762.tif 000015
【図４】
2016149762.tif 000016
【図５】
2016149762.tif 000017
【図６】
2016149762.tif 000018
【図７】
2016149762.tif 000019
【図８】
2016149762.tif 000020
【図９】
2016149762.tif 000021
【図１０】
2016149762.tif 000022
【図１１Ａ】
2016149762.tif 000023
【図１１Ｂ】
2016149762.tif 000024
【図１２Ａ】
2016149762.tif 000025
【図１２Ｂ】
2016149762.tif 000026
【図１３】
2016149762.tif 000027
【図１４】
2016149762.tif 000028
【図１５】
2016149762.tif 000029
【外国語明細書】
COMPUTING 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 an m x n pixel cell from an input image. The input image may contain more than m x n pixels, and each of the m x n pixels in the m x n pixel cell may be associated with at least one color value.  The first example embodiment may also involve, possibly based on the m x n pixel cell, obtaining an m x n attribute cell.  Elements of the m x n attribute cell may be associated in a one-to-one fashion with respective pixels in the m x n pixel cell, and the elements may identify respective control data related to their associated pixels.  The first example embodiment may further involve compressing the m x n pixel cell in a lossy fashion, and the m x n attribute cell in a lossless fashion.  Compression of the m x n pixel cell may be based on at least part of the m x n attribute cell.  The first example embodiment may additionally involve writing an interleaved representation of the compressed m x n pixel cell and the compressed m x n attribute cell to an output medium.
[0004]       A second example embodiment may involve obtaining an a x b pixel macro-cell from an input image.  The a x b pixel macro-cell may contain 4 non-overlapping m x n pixel cells, where the a x b pixels in the a x b pixel macro-cell have respective color values and are associated with respective object type tags.  The second example embodiment may also involve, possibly based on the respective color values and the respective object type tags, selecting a compression technique to either (i) compress the a x b pixel macro-cell as a whole, or (ii) compress the a x b pixel macro-cell by compressing each of the 4 non-overlapping m x n pixel cells separately.  The second example embodiment may further involve compressing the a x b pixel macro-cell according to the selected compression technique.  The second example embodiment may additionally involve writing a representation of the compressed a x b pixel macro-cell to a computer-readable output medium.
[0005]       A third example embodiment may involve obtaining an a x b pixel macro-cell from an input image with one or more color planes, and an a x b attribute macro-cell.  The a x b pixel macro-cell may contain 4 non-overlapping m x n pixel cells and the a x b attribute macro-cell may contain 4 non-overlapping m x n attribute cells.  The a x b pixels in the a x b pixel macro-cell may be associated with respective color values, and elements of the a x b attribute macro-cell may be associated in a one-to-one fashion with respective pixels in the a x b pixel macro-cell.  The third example embodiment may also include determining 4 attribute-plane output values associated respectively with the 4 non-overlapping m x n attribute cells.  The third example embodiment may further include determining 1 to 4 color-plane output values for the non-overlapping m x n pixel cells.  The third example embodiment may additionally include writing an interleaved representation of the 4 attribute-plane output values and the determined color-plane output values 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 an attribute plane decision tree, according to example embodiments.
Figure 10 depicts pseudo-code for interleaved encoding, 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 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.  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.
[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, or being used as part of a printing or a copying feature.  Other attributes may include a reference to a neutral color preservation technique, 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. 
[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, two neutral color preservation bits 504, 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]       Neutral color preservation bits 504, 506 may indicate whether a pixel is a “neutral” color, such as white, black, or gray, or a non-neutral color.  For instance, neutral color preservation bits 504, 506 may take on a value of “00” for white, “01” for black, “10” for other neutral grays, or “11” for non-neutral colors.  
[0067]       Performing neutral color preservation may improve the color conversion process from the CMY color model to the CMYK color model, and/or the color conversion process between other color models.  Printers may perform this conversion so that neutral colors can be expressed entirely using the K color channel, resulting in the use of only black toner.  Thus, it is desirable for white pixels to remain white, black pixels to remain black, and gray pixels to be expressed in the CMYK color model as (0, 0, 0, K).  However, the lossy compression and decompression techniques herein can result in neutral pixels being represented as non-neutral colors.  
[0068]        In the CMY color model, a color is a neutral gray when all three channels have the same value, and such a neutral color can be converted to the CMYK color model as (0, 0, 0, K).  As an example, a gray CMY pixel (73, 73, 73) may be changed by a lossy compression / decompression technique to a non-gray pixel (73, 74, 72).  Thus, the color neutrality of this pixel is lost, and color toner would be used to print this pixel.  To overcome this drawback, neutral color preservation bits 504, 506 can be used to force the decompressed CMY pixel back to a neutral state.  One possible way of doing this would be to take the average value of the C, M, and Y pixels, round that value off to the nearest integer, and use the resulting value for all three color channels.
[0069]       Conversely, in some cases, the values of a pixel may indicate that it is neutral (e.g., the C, M, and Y pixels all have the same value), but the neutral color preservation bits may take on a value of “11”.  In this case, the least-significant bit of one of the color planes may be flipped (from 0 to 1 or from 1 to 0) in order to change the pixel into a non-neutral color.
[0070]       Additionally, a CMY pixel that is pure white will take on the values (0, 0, 0), and the associated neutral color preservation bits may be “00”.  After compression and decompression, the pixels may take on non-pure-white values, such as (0, 2, 1).  In this case, the neutral color preservation bits may be examined, and it may be determined the pixel should be pure white.  Accordingly, the pixel’s values may be changed to (0, 0, 0) to preserve its pure white characteristics.
[0071]       Similarly, a CMY pixel that is pure black will take on the values (255, 255, 255), and the associated neutral color preservation bits may be “01”.  After compression and decompression, the pixels may take on non-pure-black values, such as (255, 253, 253).  In this case, the neutral color preservation bits may be examined, and it may be determined the pixel should be pure black.  Accordingly, the pixel’s values may be changed to (255, 255, 255) to preserve its pure black characteristics.
[0072]       Herein, pure white pixels with values of (0, 0, 0) and pure black pixels with values of (255, 255, 255) may be referred to as pixels with “pure extreme” values.  In implementations where more than eight bits are used to represent color values, respective pixel values other than (0, 0, 0) and (255, 255, 255) may represent pure white and pure black.  The pixels with “pure extreme” values may include a pixel with any combination of “pure extreme” values, such as (255, 0, 0) and (0, 255, 0).
[0073]       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.  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.
[0074]       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.
[0075]       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.  
[0076]       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.
[0077]       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.
[0078]       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.
[0079]       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, 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 
[0080]       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.
[0081]       At block 602 of Figure 6, an electronic document may be represented as one or more images formatted according to the KA or CMYA color models.  However, these color models are chosen for purposes of illustration, and other color models may be used.  The KA or CMYA pixels may be derived from a PDL representation of the electronic document.  
[0082]       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 KA or CMYA color model, for instance.
[0083]       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 KA electronic documents, cell-based compression may be applied to the gray plane and the attribute plane.  For CMYA electronic documents, cell-based compression may be applied separately for each of the C, M, Y, 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.
[0084]       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 the storage may be reduced accordingly.  As a result, printing devices incorporating the embodiments herein may be less expensive to produce.
[0085]       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 KA or CMYA 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.
[0086]       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.
[0087]       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.
[0088]       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.  
[0089]       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 KA, CMYA, or CMYKA representation of the electronic document.  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.  
[0090]       At block 620, further processing may be applied to the electronic document.  After block 620, the electronic document may be ready for printing, or additional processing may be applied.
[0091]       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.  
[0092]       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 may be compressed at block 604.  Since color conversion, neutral color preservation, overlay processing, and halftoning may take place after block 604, each bit in attribute array 500 should be preserved.  
[0093]       However, after block 612, overlay bit 502, neutral color preservation bits 504, 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.
[0094]       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.
[0095]       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.
[0096]       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 
[0097]       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.  
[0098]       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.
[0099]       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. 
[00100]      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.
[00101]      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).
[00102]      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. 
[00103]      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.
[00104]      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 
2016149762.tif 000030
[00105]      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.
a. D1 and D1D Compression  
[00106]      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.  
[00107]      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.
[00108]      For the attribute plane, the D1D default value may be predetermined (e.g., 0 or 128) or set manually by a user.
[00109]      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.
2016149762.tif 000031
[00110]      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.
[00111]      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  
[00112]      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.
[00113]      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. 
[00114]      For the attribute plane, one or both P2D default values may be predetermined (e.g., 0 and 128) or set manually by a user.
2016149762.tif 000032
[00115]      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.
[00116]      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.
[00117]      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 absent, and the previous line repeats, while a 1 indicates that the corresponding line is present.
c. P4 Compression  
[00118]      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.
2016149762.tif 000033
[00119]      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.  
[00120]      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. DCTP Compression  
[00121]      DCTP compression refers to using discrete cosine transform (DCT) techniques to compress a pCell.  In some embodiments, DCTP compression may be used when D1, D1D, P2, P2D, and P4 compression are inappropriate for a particular pCell of a color plane.  DCTP compression might not be used on the attribute plane because DCTP compression is lossy, and it is desirable for the attribute plane to be losslessly compressed.  DCTP compression may involve: a DCT transform, scaling, quantization, reordering from a two-dimensional coefficient array to one-dimensional data, and Huffman entropy coding.  
2016149762.tif 000034
[00122]      Table 5 provides an example binary encoding for DCTP compression.  For DCTP compression, a compressed representation of a pCell begins with the opcode 11, and the remaining part of the representation is a DCT encoding.  In some embodiments, the DCT encoding may be a collection of quantized DCT coefficients packaged according to a subset of the Joint Picture Experts Group (JPEG) standard, with Huffman encoding.  
e. DCTQ Compression  
[00123]      DCTQ compression refers to using DCT techniques to compress a qCell as a whole by downsampling it to the size of a pCell, and then applying DCTP encoding to the resulting pCell.  In some embodiments, DCTQ compression may be used when D1, D1D, P2, P2D, and P4 compression are inappropriate for one or more particular pCells of a color plane.  DCTQ compression might not be used on the attribute plane because DCT-based compression is lossy, and it is desirable for the attribute plane to be losslessly compressed.  
[00124]      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.  The resulting 64 average values make up the 8 x 8 cell.  Notably, this downsampling provides an initial 4:1 compression ratio, and then DCTP encoding provides additional compression on top of that.
2016149762.tif 000035
[00125]      Table 6 provides an example binary encoding for DCTQ compression.  For DCTQ compression, a compressed representation of a qCell begins with the opcode 101, and the remaining part of the representation is a DCT encoding.  Similar to the DCTP case, the DCT encoding may be a collection of quantized DCT coefficients packaged according to a subset of the JPEG standard, with Huffman encoding.  
f. D1C and D1E Compression 
[00126]      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.
[00127]      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.  
[00128]      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, DCTP or DCTQ encodings for the present qCell are emitted. 
[00129]      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.
2016149762.tif 000036
[00130]      Table 7 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.
g. D64 Compression
[00131]      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.  
[00132]      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.  
[00133]      Nonetheless, depending of 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.
2016149762.tif 000037
[00134]      Table 8 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.  Note that DCTP and D64 compression share the same opcode.  However, since DCTP is used only for color planes and D64 is used only for attribute planes, these encodings can be differentiated based on the plane of the pCell being compressed.
h. End of File (EOF)
[00135]      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.  
[00136]      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.
2016149762.tif 000038
[00137]      Table 9 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.
9.         Example Decision Trees
[00138]      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 and color 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) in a lossless fashion, but compress other portions of color planes (e.g., image graphics portions) in a lossy fashion.  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
[00139]      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.
[00140]      It is assumed that the each pixel in the qCell is tagged with an indication of the type of object of which the pixel is part - e.g., text, vector (e.g., line art), or raster (e.g., image).  These tags may reside in the attribute plane for the qCell.  
[00141]      Further, decision tree 800 may be used for 1200 dpi and/or 600 dpi images.  However, in some cases, when processing 600 dpi images, the DCTQ method may be omitted in order to avoid downsampling to 300 dpi.  For instance, the decision tree for 600 dpi images may include only blocks 804, 806, and 808 of Figure 8.
[00142]      In each decision block 802, 804, 810, 812, 816, 818, 820, 822, 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.  However, each of the compression techniques is applied per plane.
[00143]      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 in the image defined by the qCell.  
[00144]      For purposes of simplicity, D1D and P2D compression are not referenced explicitly in decision tree 800.  However, wherever D1 or P2 compression are considered or used, D1D and P2D compression may be considered or used as well.  Thus, blocks 804 and 806 may consider and use D1D and P2D compression, while block 824 may apply D1D compression.  Runs of consecutive D1 or D1D encodings are also not explicitly considered in decision tree 800, but may be used regardless.
[00145]      Blocks 802, 810, 816, and 820 each represent composite decisions made on the basis of a qCell.  For each of these decisions, the ranges of values on all color planes of the qCell are considered, as is the number of object types represented by the qCell.  To determine whether the range is broad or narrow, the range of values for each plane may be determined (thus, for instance, if there are three color planes, three ranges are determined).  Each range may be calculated by taking the difference of the highest pixel value in the qCell for that plane, and subtracting the lowest pixel value in the qCell for that plane.  If any of these ranges exceeds a predetermined threshold, the range is classified as broad.  Otherwise, the range is classified as narrow.  The predetermined threshold may be 4, 8, 16, 32, or some other value.
[00146]      Further, a mix of tags indicates that two or more objects meet in a qCell, and therefore the qCell may contain an edge.  It is desirable to preserve edges, in order to maintain the sharpness of the image.  If all 256 tag values of a qCell are the same, then it is unlikely that there is an edge in the qCell.
[00147]      A broad range indicates detail worth preserving, while a narrow range indicates a good qCell candidate for downsampling.  A broad range and mixed tags, taken together, may be evidence of a qCell with an edge.  In this case, and as reflected by block 802, downsampling should be avoided.  When the inquiry of block 802 is answered in the affirmative, block 804 is considered next.  
[00148]      At block 804, the qCells may have edge detail to preserve, so each plane is encoded pCell-by-pCell to best preserve this detail.  A pCell qualifies for encoding as a D1, P2, or P4 if it has 1, 2, or 4 colors, respectively.  If one of D1, P2, or P4 compression is selected, this technique may be applied at block 806.  Otherwise DCTP compression may be applied at block 808.  In some embodiments, block 804 may involve the general process of determining whether the respective color values of the m x n pixels of each pCell of each color plane include at least d colors, where d is at least 2.
[00149]      On the other hand, if the qCell exhibits a broad range and the same tag throughout, then the inquiry of block 810 is answered in the affirmative, and block 812 is considered next.  On a composite basis, it is determined whether there are 5 or more colors in the qCell, and all of the tags indicate a raster.  If this condition is true, then the qCell contains only image data, and may be compressed using the DCTQ technique at block 814.  If this condition is not true, the qCell either contains text or line art that should not be downsampled, or contains image data with a very small number of values.  In either case, D1, P2, P4, or DCTP compression may either be better at preserving the information in the qCell, or may provide a better compression ratio.  Thus, the qCell may be considered further at block 804, and compressed at either block 806 or block 808.  
[00150]      Alternatively, if the qCell exhibits a narrow range and mixed tags, the qCell may be a candidate for downsampling, because little information should be lost in this process.  However, if there are 4 or fewer colors in the qCell, one of D1, P2, or P4 compression may provide a better compression ratio than DCT-based compression.  
[00151]      Accordingly, if the inquiry of block 816 is answered in the affirmative, block 818 is reached.  At block 818, it is determined, on a composite basis, whether the qCell contains 5 or more colors.  If so, then the qCell is likely to contain mostly image data, and may be compressed using the DCTQ technique at block 814.  If not, the qCell may be considered further at block 804, and compressed at block 806.  Since the qCell has 4 or fewer colors, one of D1, P2, or P4 compression will be applicable, and block 808 might not be reached in this scenario.
[00152]      If a qCell exhibits a narrow range the same tag throughout, this is strong evidence of no edge in the qCell.  If the inquiry of block 820 is answered in the affirmative, block 822 may be considered next.  At block 822, it may be determined whether all pixels in each plane of the qCell have the same value.  If so, using D1 compression will be more efficient than DCT-based compression.  Accordingly, the plane of the qCell may be compressed, on a pCell-by-pCell basis, at block 824.  Otherwise, DCTQ is applied to the plane of the qCell at block 814.
[00153]      Figure 8 depicts one possible color plane decision tree.  Other such decision trees are possible.  For instance, when compressing a 600 dpi image, only blocks 804, 806, and 808 might be used.
b. Attribute Plane Decision Tree
[00154]      Figure 9 depicts an attribute plane decision tree 900, 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 900 are made on a planar basis.  However, alternative embodiments could take different approaches. 
[00155]      Similar to decision tree 800, D1D and P2D compression are not referenced explicitly in decision tree 900.  However, wherever D1 or P2 compression is considered or used, D1D and P2D compression may be considered or used as well.  Thus, blocks 902, 904, 906, and 908 may consider and/or use D1D and P2D compression.  Runs of consecutive D1 or D1D encodings are also not explicitly considered in decision tree 900, but may be used regardless.
[00156]      At block 902, it is determined whether the attribute plane pCell qualifies for D1 compression.  If so, D1 compression is applied at block 904.  Otherwise, at block 906, it is determined whether the pCell qualifies for P2 compression.  If so, P2 compression may be applied at block 908.  
[00157]      If the pCell does not qualify for either D1 or P2 compression, at block 910 it may be determined whether the pCell qualifies for P4 compression.  If so, P4 compression may be applied at block 912.  Otherwise, D64 compression may be applied at block 914.
[00158]      Figure 9 depicts one possible attribute plane decision tree.  Other such decision trees are possible.  
c.  Fallback Mode
[00159]      In some cases, the behavior of a printing device’s pipeline, such as the pipeline of Figure 6, may be dynamically modified based on various performance goals.  In particular, a printing device can be configured to enter a fallback mode when either its compression ratio or its decompression speed is not meeting pre-established thresholds.  
[00160]      Compression size may be a goal because, as discussed above, the storage of block 616 may be designed to store a small number of pages (e.g., two 1200 dpi A3 CMYKA pages). Decompression speed may also be a goal because the cell-based decompression of block 618 should not operate more slowly than the printing device can print the decompressed data.  
[00161]      Accordingly, the printing device may be configured to detect compression buffer overflow, and/or decompression speed underruns.  A compression buffer overflow occurs when the number of bytes written to memory (e.g., storage of block 616) exceeds a predetermined threshold, indicating that the achieved compression ratio is poor.  A decompression speed underrun occurs when the number of DCT encodings of qCell per part or all of a page exceeds a predetermined threshold.  
[00162]      After detecting a compression buffer overflow, the decision trees of Figures 8 and/or 9 may be modified so that compression techniques that always achieve at least 4:1 compression are used.  For instance, on the color planes, the use of P4 compression may be eliminated and replaced with DCTQ compression for a pCell that would normally be encoded with P4 compression, as well as the remaining pCells in the same qCell.  In a similar fashion, DCTP compression may also be replaced by DCTQ compression.  On the attribute plane, P4 compression may be replaced with D64 compression when only 1 or 2 bits per attribute element are maintained.
[00163]      After detecting a decompression speed underrun, the color plane decision tree of Figure 8 may be modified to force no more than t DCT operations of qCell, where t is 1, 2, or 3.
10.        Interleaved Encoding
[00164]      The encoded output of cell-based compression may be interleaved.  In some cases, an interleaved encoding may be superior to a non-interleaved encoding.
[00165]      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.  
[00166]      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 CMYA, then the ordering of encoded pCells may be an attribute pCell, then a cyan pCell, then a magenta pCell, then a yellow pCell, then another attribute pCell, then another cyan pCell, then another magenta pCell, then another yellow pCell, and so on.
[00167]      A pseudo-code representation 1000 of such an operation is shown in Figure 10.  At line 1 of pseudo-code representation 1000, each composite (multi-planar) qCell in an input image is considered.  At line 3, the composite qCell is sorted in planar order so that the attribute plane is first, the cyan plane is second, the magenta plane is third, the yellow plane is fourth, and the K plane (if present) is fifth.  
[00168]      At lines 4 and 5, each plane of each pCell is considered.  At line 7, it is determined whether the planar qCell should be subsampled (downsampled).  If, so, then at lines 8-11, a single pCell for the entire planar qCell is encoded and emitted (e.g. written to the output medium).  If the planar qCell is not to be downsampled, then at line 13, each of its planar pCells (encoded using a non-DCT technique) are emitted.
[00169]      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, cyan, magenta, and yellow 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.  
[00170]      Throughout the four qCells, the attribute plane is consistently encoded using P2 compression, the cyan plane is encoded using P4 compression, and the yellow plane is encoded using DCTP compression.  The magenta plane, however, is encoded using a mix of P2 and D1 compression.  Notably, 13 consecutive, identical pCells of the magenta plane are encoded in a run of D1 compression.  
[00171]      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 with the pCells of the first qCell.  First is the 1a pCell of the attribute plane, then the 1a pCell of the cyan plane, the 1a pCell of the magenta plane, the 1a pCell of the yellow plane, the 1b pCell of the attribute plane, the 1b pCell of the cyan plane, and so on.  
[00172]      With respect to the run of 13 magenta cells using D1 compression, the 7th pCell in the output sequence indicates that a D1 run begins.  Particularly, this pCell is one of three pCells in the D1 run that are from the first qCell.  Thus, this pCell may be encoded using D1 compression and may include a length field with a value of 3 to indicate that it represents three consecutive, identical D1 pCells.  Accordingly, the 1b, 1c, and 1d magenta pCells are encoded as a single pCell, and the 1c and 1d magenta pCells are omitted from the output sequence.  
[00173]      For the second qCell, the first magenta pCell therein appears in the 17th position in the output sequence.  However, a D1C encoding is used to indicate that the run of magenta D1 pCells continues through this qCell.  Similarly, for the third qCell, the first magenta pCell therein appears in the 30th position in the output sequence.  Here, a D1C encoding is also used to indicate that the run of magenta D1 pCells continues through this qCell.  Other magenta pCells in the second and third qCells are omitted in this encoding.
[00174]      In the fourth qCell, the run of magenta D1 pCells continues for two more pCells, and then ends.  Therefore, at the 43rd position in the output sequence, a D1E encoding is used to indicate the end of the D1 run.  But, since there actually are two remaining consecutive, identical magenta D1 pCells in the run, a second D1 run is encoded.  In the 44th positon in the output sequence, a magenta pCell may be encoded using D1 compression.  This pCell may include a length field with a value of 2 to indicate that it represents two consecutive identical D1 pCells.  Thus, the 4b magenta pCell is omitted from the encoding, but the 4c and 4d magenta pCells are included.
[00175]      The final encoding, in the 57th output position, is an end-of-file (EOF) used to indicate the end of this section of the compressed representation.
[00176]      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, cyan, magenta, and yellow planes.  However, unlike the example of Figures 11A and 11B, the example of Figure 12A includes DCTQ encodings, as well as an implicit D1 run.
[00177]      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.  With respect to the DCTQ encodings, since such an encoding encompasses four actual pCells, only one DCTQ encoding per qCell may be used.  Therefore, in Figure 12B, cyan DCTQ encodings appear at the 2nd, 13th, 23rd, and 33rd output positions, respectively.  
[00178]      Like Figure 11B, the run of 13 magenta D1 pCells are compressed into two logical runs in Figure 12B.  However, the run of six consecutive, identical attribute D1 pCells are encoded in a slightly different fashion.  Since the run begins with the b and d pCells of a qCell, the beginning of the run is considered to be implicit.  Thus, these two pCells are encoded as expected at the 26th and 30th output positions, respectively.  However, at the 32nd output position, a D1C encoding is used for the four D1 cells of this run that are in the fourth qCell.  Then, at the 42nd output position, a D1E encoding is used to indicate the end of the run, and at the 43rd output position an EOF encoding is used to indicate the end of this section of the compressed representation.
[00179]      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 
[00180]      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.  
[00181]      The pCells and/or qCells encoded with the compression encodings described above can be decoded and decompressed as follows.  For a particular pCell or qCell encoding, the opcode is read.  Based on the value of the 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.
[00182]      For example, 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. 
[00183]      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. 
[00184]      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.  
[00185]      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.  
[00186]      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.
[00187]      If the opcode is 11, indicating DCTP compression, the bitmap of the DCTP compression method may be read and a cell may be created in accordance with this DCTP encoding.
[00188]      If the opcode is 101, indicating DCTQ compression, the bitmap of the DCTQ compression method may be read and a pCell may be created in accordance with this DCTQ encoding.  Then, each element in pCell may be replaced by a 2 x 2 block of elements with the same value.  The result is a qCell that is an approximate reversal of the DCTQ downsampling process.
[00189]      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.
[00190]      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.
12.        Example Performance Results
[00191]      Compression performance of the cell-based compression (CBC) techniques disclosed herein were compared to that of JPEG-based compression and split run length encoding (SRLE) based compression (a lossless technique).  The test suite consisted of 408 pages with varying amounts of text, line art, and image content.  
2016149762.tif 000039
[00192]      Table 10 provides the compression ratios achieved by CBC, JPEG, and SRLE for both 600 dpi and 1200 dpi images.  These results include the maximum, minimum, average, and median compression ratios achieved for each technique.  
[00193]      The CBC technique disclosed herein provides the best maximum compression ratio for both 600 dpi and 1200 dpi images by quite a margin.  The CBC technique also provides the best minimum compression ratio for 1200 dpi images, but the JPEG technique provides a slightly better minimum compression ratio for 600 dpi images.  
[00194]      More importantly, the CBC technique disclosed herein provides significantly better average and median compression ratios than JPEG and SRLE, while providing superior image quality over that of JPEG.  Consequently, the CBC technique is a significant improvement in printing and printing device technology.
13.        Example Operations
[00195]      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. 
[00196]      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.
[00197]      Figure 13 generally depicts steps for interleaved compression of cells of an attribute plane and cells of 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 13 could take place at blocks 604 and/or 614 of Figure 6, in other locations of a printing device’s pipeline, or by a host computer.
[00198]      At step 1300, an m x n pixel cell from an input image may be obtained.  The input image may contain more than m x n pixels, and each of the m x n pixels in the m x n pixel cell may be associated with at least one color value.
[00199]      At step 1302, possibly based on the m x n pixel cell, an m x n attribute cell may be obtained.  Elements of the m x n attribute cell may be associated in a one-to-one fashion with respective pixels in the m x n pixel cell, and the elements may identify respective control data related to their associated pixels.  The attribute cell elements may be attribute arrays and/or attribute bytes.
[00200]      At step 1304, the m x n pixel cell may be compressed in a lossy fashion, and the m x n attribute cell may be compressed in a lossless fashion.  The lossy compression may be DCT-based compression, and the lossless compression may be any of the other compression techniques described herein.  Compression of the m x n pixel cell may be based on at least part of the m x n attribute cell (e.g., the compression may depend upon the type of object(s) that the m x n pixel cell represents, as encode by the m x n attribute cell).  At step 1306, an interleaved representation of the compressed m x n pixel cell and the compressed m x n attribute cell may be written to an output medium.  This interleaved representation may take a form in accordance with the disclosure of Figure 11A, 11B, 12A, and 12B, or another form.
[00201]      In some embodiments, a unit of the control data may be associated with a particular pixel in the m x n pixel cell.  The control data may be one or more bits indicating whether the particular pixel represents an image object type, a vector object type, or a text object type.  The compressed m x n pixel cell and the compressed m x n attribute cell may be decompressed, and a halftone screen may be selected based on the one or more bits.  The m x n pixel cell may be printed (possibly along with the rest of the input image) with the selected halftone screen applied to the particular pixel.  
[00202]      Alternatively or additionally, the control data associated with a particular pixel in the m x n pixel cell may contain one or more bits indicating whether the particular pixel was formed as part of a printing procedure or a scanning procedure.  The compressed m x n pixel cell and the compressed m x n attribute cell may be decompressed, and halftone screen may be selected based on the one or more bits.   The m x n pixel cell may be printed (possibly along with the rest of the input image) with the selected halftone screen applied to the particular pixel.
[00203]      Alternatively or additionally, the control data associated with a particular pixel in the m x n pixel cell may contain one or more bits indicating that the particular pixel took on neutral color values before compression.  The compressed m x n pixel cell and the compressed m x n attribute cell may be decompressed.  Possibly as a result of the one or more bits indicating that the particular pixel took on neutral color values before compression, it may be determined that color values of the particular pixel are not identical, and at least one of the color values may be changed so that the color values are identical.
[00204]      Alternatively or additionally, the control data associated with a particular pixel in the m x n pixel cell may contain one or more bits indicating that the particular pixel took on non-neutral color values before compression.  The compressed m x n pixel cell and the compressed m x n attribute cell may be decompressed.  Possibly as a result of the one or more bits indicating that the particular pixel took on non-neutral color values before compression, it may be determined that color values of the particular pixel are identical, and at least one of the color values may be changed so that the color values are not identical.
[00205]      Alternatively or additionally, the control data associated with a particular pixel in the m x n pixel cell may contain one or more bits indicating that the particular pixel took on identical pure extreme color values before compression.  The compressed m x n pixel cell and the compressed m x n attribute cell may be decompressed.  Possibly as a result of the one or more bits indicating that the particular pixel took on identical pure extreme color values before compression, it may be determined that color values of the particular pixel are not the identical pure extreme color values, and at least one of the color values may be changed so that the color values are the identical pure extreme color values.
[00206]      Alternatively or additionally, the control data associated with a particular pixel in the m x n pixel cell may contain one or more bits indicating whether the particular pixel is to be overlaid with a digital object.  Compressing the m x n pixel cell in the lossy fashion may involve selecting either (i) the particular pixel, or (ii) a replacement pixel from the digital object, and compressing the selected pixel.  The selection may be based on the one or more bits.  In some cases, the one or more bits may be omitted from the lossless compression of the m x n attribute cell.
[00207]      Alternatively or additionally, the control data associated with a particular pixel in the m x n pixel cell may contain one or more bits indicating whether a particular color conversion is to be applied to the particular pixel.  Before compressing the m x n pixel cell in the lossy fashion, the particular pixel may be converted from one color model to another color model based on the particular color conversion.  In some cases, the one or more bits may be omitted from the lossless compression of the m x n attribute cell.
[00208]      Compressing the m x n attribute cell in the lossless fashion may involve determining that each element of the m x n attribute cell takes on the same value, and possibly based on this determination, encoding the m x n attribute cell using a single-value opcode (e.g., using D1 or D1D compression) and an indication of the same value.  Alternatively, compressing the m x n attribute cell in the lossless fashion may involve determining that each element of the m x n attribute cell takes on one of two different values, and possibly based on this determination, encoding the m x n attribute cell using a two-value opcode (e.g., using P2 or P2D compression), an indication of the two different values, and a bitmap indicating which elements take on each of the two different values.
[00209]      In yet another aspect, compressing the m x n attribute cell in the lossless fashion may involve determining that each element of the m x n attribute cell takes on one of three or four different values, and possibly based on this determination, encoding the m x n attribute cell using a four-value opcode (e.g., using P4 compression), an indication of the three or four different values, and a bitmap indicating which elements take on each of the three or four different values.  In another alternative, compressing the m x n attribute cell in the lossless fashion may involve determining that the elements of the m x n attribute cell take on at least five different values, and possibly based on this determination, encoding the m x n attribute cell using a multi-value opcode (e.g., using D64 compression) and indications of values taken on by each of the elements of the m x n attribute cell.
[00210]      Figure 14 generally depicts steps for compression of cells 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 blocks 604 and/or 614 of Figure 6, in other locations of a printing device’s pipeline, or by a host computer.  
[00211]      Since this flow chart involves the compression of a single color plane, decisions (such as the decisions of color plane decision tree 800) are taken on a planar basis.  Nonetheless, the steps in Figure 14 could be performed as part of a composite operation that considers multiple color planes simultaneously. 
[00212]      At step 1400, an a x b pixel macro-cell from an input image may be obtained.  The a x b pixel macro-cell may contain 4 non-overlapping m x n pixel cells.  The a x b pixels in the a x b pixel macro-cell may have respective color values, and may be associated with respective object type tags.  These object type tags may each be, for example, one or more bits of an attribute array.
[00213]      At step 1402, possibly based on the respective color values and the respective object type tags, a compression technique may be selected to either (i) compress the a x b pixel macro-cell as a whole, or (ii) compress the a x b pixel macro-cell by compressing each of the 4 non-overlapping m x n pixel cells separately.
[00214]      At step 1404, the a x b pixel macro-cell may be compressed according to the selected compression technique.  At step 1406, a representation of the compressed a x b pixel macro-cell may be written to a computer-readable output medium.
[00215]      In some embodiments, the selected compression technique compresses the a x b pixel macro-cell as a whole.  This process may involve downsampling the a x b pixel macro-cell to a downsampled m x n pixel cell, and compressing the downsampled m x n pixel cell in a lossy fashion (e.g., using DCTQ compression).
[00216]      When the a x b pixel macro-cell is compressed as a whole, selecting the compression technique may include (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels each represent the same object type, (iii) determining that the respective color values of the a x b pixels include at least d colors, where d is at least 2, and (iv) selecting to compress the a x b pixel macro-cell as a whole.
[00217]      Alternatively, when the a x b pixel macro-cell is compressed as a whole, selecting the compression technique may include (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (iii) determining that the respective color values of the a x b pixels include at least d colors, where d is at least 2, and (iv) selecting to compress the a x b pixel macro-cell as a whole.
[00218]      In another alternative, when the a x b pixel macro-cell is compressed as a whole, selecting the compression technique may include (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels each represent an identical object type, (iii) determining that the respective color values of the a x b pixels include more than one color, and (iv) selecting to compress the a x b pixel macro-cell as a whole.
[00219]      In additional embodiments, the selected compression technique compresses each of the 4 non-overlapping m x n pixel cells separately in a lossless fashion (e.g., using D1, D1D, P2, P2D, or P4 compression).
[00220]      When the 4 non-overlapping m x n pixel cells are compressed separately in a lossless fashion, selecting the compression technique may involve (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels each represent the same object type, (iii) determining that the respective color values for each of the one or more m x n pixel cells include less than d colors, where d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossless fashion.
[00221]      Alternatively, selecting the compression technique may involve (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (iii) determining that the respective color values for each of the one or more m x n pixel cells include less than d colors, where d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossless fashion.
[00222]      In another alternative, selecting the compression technique may involve (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (iii) determining that the respective color values for each of the one or more m x n pixel cells include less than d colors, where d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossless fashion.
[00223]      In yet another alternative, selecting the compression technique may involve (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels represent an identical object type, (iii) determining that the respective color values of the a x b pixels each represent an identical color value, and (iv) selecting to compress each of the 4 non-overlapping m x n pixel cells separately in a lossless fashion.
[00224]      In some embodiments, the selected compression technique may compress one or more m x n pixel cells of the 4 non-overlapping m x n pixel cells separately in a lossy fashion (e.g., DCTP compression).
[00225]      When the 4 non-overlapping m x n pixel cells are compressed separately in a lossy fashion, selecting the compression technique may involve (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value or that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (ii) determining that the respective color values for the a x b pixels include less than 5 colors, (iii) determining that the respective color values for each of the one or more m x n pixel cells include at least d colors, where d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossy fashion.
[00226]      The compressed a x b pixel macro-cell may be decompressed by reversing the compression technique used to compress the a x b pixel macro-cell.  Thus, decompressing the compressed a x b pixel macro-cell may result in a second a x b pixel macro-cell, and pixel values of the second a x b pixel macro-cell may be either identical to or may approximate the pixel values of the a x b pixel macro-cell.  
[00227]      In some embodiments, a second a x b pixel macro-cell and a third a x b pixel macro-cell may be obtained from the input image.  The second and third a x b pixel macro-cells may each contain 4 non-overlapping m x n pixel cells, and the pixels in each of the second and third a x b pixel macro-cells may also have respective color values and may also be associated with the respective object type tags.  In these embodiments, a compression technique may be selected to compress each of the second and third a x b pixel macro-cells by compressing each of the 4 non-overlapping m x n pixel cells of the second a x b pixel macro-cell and the 4 non-overlapping m x n pixel cells of the third a x b pixel macro-cell separately from one another and from the 4 non-overlapping m x n pixel cells of the a x b pixel macro-cell.  Accordingly, each of the 4 non-overlapping m x n pixel cells of the second a x b pixel macro-cell and the 4 non-overlapping m x n pixel cells of the third a x b pixel macro-cell may be compressed separately from one another and from the 4 non-overlapping m x n pixel cells of the a x b pixel macro-cell.  Representations of the compressed second a x b pixel macro-cell and the compressed third a x b pixel macro-cell may be written to the computer-readable output medium.  
[00228]      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 blocks 604 and/or 614 of Figure 6, in other locations of a printing device’s pipeline, or by a host computer.
[00229]      At step 1500, an a x b pixel macro-cell may be obtained from an input image with one or more color planes.  An a x b attribute macro-cell may also be obtained.  The a x b pixel macro-cell may contain 4 non-overlapping m x n pixel cells, and the a x b attribute macro-cell may contain 4 non-overlapping m x n attribute cells.  The a x b pixels in the a x b pixel macro-cell may be associated with respective color values, and elements of the a x b attribute macro-cell may be associated in a one-to-one fashion with respective pixels in the a x b pixel macro-cell.
[00230]      At step 1502, 4 attribute-plane output values associated respectively with the 4 non-overlapping m x n attribute cells may be determined.  At step 1504, 1 to 4 color-plane output values for the non-overlapping m x n pixel cells may be determined.  At step 1506, an interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may be written to a computer-readable output medium. This interleaved representation may take a form in accordance with the disclosure of Figure 11A, 11B, 12A, and/or 12B, or another form.
[00231]      Further, a second a x b pixel macro-cell may also be obtained from the input image.  The second a x b pixel macro-cell may contain a second set of 4 non-overlapping m x n pixel cells, where the a x b pixels in the second a x b pixel macro-cell are also associated with respective color values, and where elements of the a x b attribute macro-cell are associated in a one-to-one fashion with respective pixels in the second a x b pixel macro-cell.  A third a x b pixel macro-cell may also be obtained from the input image.  The third a x b pixel macro-cell may contain a third set of 4 non-overlapping m x n pixel cells, where the a x b pixels in the third a x b pixel macro-cell are also associated with respective color values, and where elements of the a x b attribute macro-cell are associated in a one-to-one fashion with respective pixels in the third a x b pixel macro-cell.  The operations may further involve determining a second set of 1 to 4 color-plane output values for the second set of 4 non-overlapping m x n pixel cells, and determining a third set of 1 to 4 color-plane output values for the third set of 4 non-overlapping m x n pixel cells.  The interleaved representation may also include the determined second set of 1 to 4 color-plane output values and the determined third set of 1 to 4 color-plane output values.
[00232]      In some embodiments, each of the attribute-plane output values and color-plane output values contain respective opcodes and data.  Further, the 4 attribute-plane output values may be determined based on lossless compression of the respective 4 non-overlapping m x n attribute cells (e.g., using D1, D1D, P2, P2D, P4, or D64 compression).
[00233]      In some cases, determining the color-plane output values for the non-overlapping m x n pixel cells may involve determining that each of the 4 non-overlapping m x n pixel cells are compressed separately in a lossy or lossless fashion (e.g., using D1, D1D, P2, P2D, P4, or DCTP compression), and determining 4 color-plane output values, one color-plane output value for each of the 4 non-overlapping m x n pixel cells.  Alternatively, determining the color-plane output values for the non-overlapping m x n pixel cells may involve determining that the a x b pixel macro-cell is downsampled and compressed in a lossy fashion (e.g., using DCTQ compression), and determining one output value for the downsampled and compressed a x b pixel macro-cell.  
[00234]      In some embodiments, at least 2 color-plane output values are determined (e.g., using D1, D1D, P2, or P2D compression).  Writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may involve determining that a first color-plane output value and a second color-plane output value of the color-plane output values are losslessly compressed in the same fashion, and representing the first color-plane output value with an opcode, a cache miss indicator, and a data field, and representing the second color-plane output value with the opcode and a cache hit indicator.  The cache hit indicator may indicate that the second color-plane output value uses the data field of the first color-plane output value.
[00235]      Alternatively or additionally, writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may involve determining that a particular color-plane output value of the color-plane output values is losslessly compressed using (i) an n-1 bit line map, (ii) a first m-bit line, and (iii) for each bit in the n-1 bit line map that takes on a value of 1, another respective m-bit line.  Then, the particular color-plane output value may be represented with an opcode, at least 2 different pixel values, the n-1 bit line map, the first m-bit line, and the respective m-bit lines (e.g., using P2 compression).
[00236]      In other cases, writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may involve determining that a particular color-plane output value of the color-plane output values is losslessly compressed using (i) an n-1 bit line map, (ii) a first 2m-bit line, and (iii) for each bit in the n-1 bit line map that takes on a value of 1, another respective 2m-bit line.  Then, the particular color-plane output value may be represented with an opcode, at least 4 different pixel values, the n-1 bit line map, the first 2m-bit line, and the respective 2m-bit lines (e.g., using P4 compression).
[00237]      In some embodiments, writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may involve determining that a first output value and a second output value are to be represented on the computer-readable output medium, and that the m x n cells associated with the first output value and the second output value to be represented with identical bitmaps (e.g., using P2 compression with caching).  Then, the second output value may be represented with an opcode, two or more color values, and a reference to a first bitmap of the first output value, where the second output value does not include a dedicated bitmap.
[00238]      Moreover, writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may involve determining that (i) p of the 4 non-overlapping m x n pixel cells are losslessly compressed in an identical fashion, and (ii) contain color values in identical locations as one another, where p is 1, 2, 3, or 4 (e.g., a run of D1 pCells within a qCell).  Then, the determined color-plane output values may be represented as at least an opcode and a value of p.
[00239]      In some situations, writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may involve determining that the 4 non-overlapping m x n pixel cells are losslessly compressed in an identical fashion as one another and a previously-written m x n pixel cell of the same color plane.  Then, the determined color-plane output values may be represented as an opcode indicating that the determined color-plane output values are a run of identical encodings (e.g., using D1C compression).  Writing the interleaved representation of the 4 attribute-plane output values and the determined color-plane output values may further involve determining that p of the 4 non-overlapping m x n pixel cells (i) are losslessly compressed in an identical fashion as previous m x n pixel cells written to the computer-readable output medium, where the previous m x n pixel cells were represented as the run of identical encodings, and (ii) are to be written to the computer-readable output medium before any remaining 4-p non-overlapping m x n pixel cells, where p is 0, 1, 2, or 3.  Then, determined color-plane output values may be represented as (i) a first opcode indicating an end to the run of identical encodings (e.g., using a D1E encoding), and (ii) when p is greater than 0, a second opcode and a value of p (e.g., a run of D1 pCells within a qCell).
14.        Conclusion 
[00240]      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.  
[00241]      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.    
[00242]      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.
[00243]      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.
[00244]      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.
[00245]      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.
[00246]       
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
We claim:
1.      A computing 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 computing device to perform operations comprising:
obtaining an a x b pixel macro-cell from an input image, wherein the a x b pixel macro-cell contains 4 non-overlapping m x n pixel cells, and wherein the a x b pixels in the a x b pixel macro-cell have respective color values and are associated with respective object type tags;
based on the respective color values and the respective object type tags, selecting a compression technique to either (i) compress the a x b pixel macro-cell as a whole, or (ii) compress the a x b pixel macro-cell by compressing each of the 4 non-overlapping m x n pixel cells separately; 
compressing the a x b pixel macro-cell according to the selected compression technique; and
writing a representation of the compressed a x b pixel macro-cell to a computer-readable output medium.
2.      The computing device of claim 1, wherein the selected compression technique compresses the a x b pixel macro-cell as a whole, and wherein compressing the a x b pixel macro-cell as a whole comprises:
downsampling the a x b pixel macro-cell to a downsampled m x n pixel cell; and 
compressing the downsampled m x n pixel cell in a lossy fashion.
3.      The computing device of claim 2, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels each represent the same object type, (iii) determining that the respective color values of the a x b pixels include at least d colors, wherein d is at least 2, and (iv) selecting to compress the a x b pixel macro-cell as a whole.
4.      The computing device of claim 2 or 3, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (iii) determining that the respective color values of the a x b pixels include at least d colors, wherein d is at least 2, and (iv) selecting to compress the a x b pixel macro-cell as a whole.
5.      The computing device of any of claims 2 to 4, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels each represent an identical object type, (iii) determining that the respective color values of the a x b pixels include more than one color, and (iv) selecting to compress the a x b pixel macro-cell as a whole.
6.      The computing device of any of claims 1 to 5, wherein the selected compression technique compresses one or more m x n pixel cells of the 4 non-overlapping m x n pixel cells separately in a lossless fashion.
7.      The computing device of claim 6, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels each represent the same object type, (iii) determining that the respective color values for each of the one or more m x n pixel cells include less than d colors, wherein d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossless fashion.
8.      The computing device of claim 6 or 7, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (iii) determining that the respective color values for each of the one or more m x n pixel cells include less than d colors, wherein d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossless fashion.
9.      The computing device of any of claims 6 to 8, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (iii) determining that the respective color values for each of the one or more m x n pixel cells include less than d colors, wherein d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossless fashion.
10.     The computing device of any of claims 6 to 9, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels is within a predetermined non-zero threshold value, (ii) determining that the respective object type tags for the a x b pixels indicate that the a x b pixels represent an identical object type, (iii) determining that the respective color values of the a x b pixels each represent an identical color value, and (iv) selecting to compress each of the 4 non-overlapping m x n pixel cells separately in a lossless fashion.
11.     The computing device of any of claims 1 to 10, wherein the selected compression technique compresses one or more m x n pixel cells of the 4 non-overlapping m x n pixel cells separately in a lossy fashion.
12.     The computing device of claim 11, wherein selecting the compression technique comprises (i) determining that a range of the respective color values of the a x b pixels exceeds a predetermined non-zero threshold value or that the respective object type tags for the a x b pixels indicate that some of the a x b pixels represent different object types, (ii) determining that the respective color values for the a x b pixels include less than 5 colors, (iii) determining that the respective color values for each of the one or more m x n pixel cells include at least d colors, wherein d is at least 2, and (iv) selecting to compress each of the one or more m x n pixel cells separately in a lossy fashion.
13.     The computing device of any of claims 1 to 12, further comprising:
decompressing the compressed a x b pixel macro-cell by reversing the compression technique used to compress the a x b pixel macro-cell, wherein decompressing the compressed a x b pixel macro-cell results in a second a x b pixel macro-cell, and wherein pixel values of the second a x b pixel macro-cell is either identical to or approximates the pixel values of the a x b pixel macro-cell.
14.     The computing device of any of claims 1 to 13, further comprising:
obtaining a second a x b pixel macro-cell and a third a x b pixel macro-cell from the input image, wherein the second and third a x b pixel macro-cells each contain 4 non-overlapping m x n pixel cells, and wherein the pixels in each of the second and third a x b pixel macro-cells also have respective color values and are also associated with the respective object type tags;
selecting a compression technique to compress each of the second and third a x b pixel macro-cells by compressing each of the 4 non-overlapping m x n pixel cells of the second a x b pixel macro-cell and the 4 non-overlapping m x n pixel cells of the third a x b pixel macro-cell separately from one another and from the 4 non-overlapping m x n pixel cells of the a x b pixel macro-cell; 
compressing each of the 4 non-overlapping m x n pixel cells of the second a x b pixel macro-cell and the 4 non-overlapping m x n pixel cells of the third a x b pixel macro-cell separately from one another and from the 4 non-overlapping m x n pixel cells of the a x b pixel macro-cell; and
writing representations of the compressed second a x b pixel macro-cell and the compressed third a x b pixel macro-cell to the computer-readable output medium.  
15.     The computing device of any of claims 1 to 14, wherein the selected compression technique compresses each of the 4 non-overlapping m x n pixel cells separately in a lossless fashion.
16.     A computer program causing a computing device to perform operations comprising:
obtaining an a x b pixel macro-cell from an input image, wherein the a x b pixel macro-cell contains 4 non-overlapping m x n pixel cells, and wherein the a x b pixels in the a x b pixel macro-cell have respective color values and are associated with respective object type tags;
based on the respective color values and the respective object type tags, selecting a compression technique to either (i) compress the a x b pixel macro-cell as a whole, or (ii) compress the a x b pixel macro-cell by compressing each of the 4 non-overlapping m x n pixel cells separately; 
compressing the a x b pixel macro-cell according to the selected compression technique; and
writing a representation of the compressed a x b pixel macro-cell to a computer-readable output medium.
17.     A method comprising:
obtaining, by a computing device, an a x b pixel macro-cell from an input image, wherein the a x b pixel macro-cell contains 4 non-overlapping m x n pixel cells, and wherein the a x b pixels in the a x b pixel macro-cell have respective color values and are associated with respective object type tags;
based on the respective color values and the respective object type tags, selecting, by the computing device, a compression technique to either (i) compress the a x b pixel macro-cell as a whole, or (ii) compress the a x b pixel macro-cell by compressing each of the 4 non-overlapping m x n pixel cells separately;
compressing, by the computing device, the a x b pixel macro-cell according to the selected compression technique; and
writing, by the computing device, a representation of the compressed a x b pixel macro-cell to a computer-readable output medium.
1. Abstract
PROBLEM TO BE SOLVED
To provide a technique for a digital image color plane compression.
2. SOLUTION
An example embodiment may involve obtaining an a x b pixel macro-cell from an input image.  The a x b pixel macro-cell may contain 4 non-overlapping m x n pixel cells.  The a x b pixels in the a x b pixel macro-cell may have respective color values and may be associated with respective object type tags.  The example embodiment may also include selecting a compression technique to either (i) compress the a x b pixel macro-cell as a whole, or (ii) compress the a x b pixel macro-cell by compressing each of the 4 non-overlapping m x n pixel cells separately.  The example embodiment may further include compressing the a x b pixel macro-cell according to the selected compression technique, and writing a representation of the compressed a x b pixel macro-cell to a computer-readable output medium.
3. Representative Drawing: Fig. 1
2016149762.tif 000040
2016149762.tif 000041
2016149762.tif 000042
2016149762.tif 000043
2016149762.tif 000044
2016149762.tif 000045
2016149762.tif 000046
2016149762.tif 000047
2016149762.tif 000048
2016149762.tif 000049
2016149762.tif 000050
2016149762.tif 000051
2016149762.tif 000052
2016149762.tif 000053
2016149762.tif 000054