(57)【要約】【課題】  本発明は、ハーフトーンのデジタル画像の圧縮方法を提供する。【解決手段】  ｍ×ｎハーフトーンマトリックスおよび画像のｍ×ｎピクセルブロックに基づいて、ｍ×ｎピクセルブロックのｍ×ｎハーフトーンバージョンが決定される。ｎ箇所のインターリーブが、ｍ×ｎのハーフトーンバージョンの行に実行され、ｍｎ×１のハーフトーンセグメントを生成する。ｍｎ×１のハーフトーンセグメントは、バッファ内の１つ以上のハーフトーンセグメントと比較される。比較に基づいて、リテラルコードワードおよびｍｎ×１のハーフトーンセグメントの表現が出力され、ｍｎ×１のハーフトーンセグメントの表現がバッファに書き込まれる。リピートコードワードおよびリピート値が出力されてもよく、ｍｎ×１のハーフトーンセグメントの少なくとも１つの表現がバッファに書き込まれる。【選択図】図２０
2014087066.tif 000002
【特許請求の範囲】
【請求項１】
ｍ×ｎハーフトーンマトリックス、および画像内の第１のｍ×ｎピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの、第１のｍ×ｎのハーフトーン処理されたピクセルブロックを決定する工程と、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたピクセルブロックの複数の行に対してｎ箇所の交互配置工程（ｎ−ｗａｙ  ｉｎｔｅｒｌｅａｖｅ）を行い、第１のｍｎ×１のハーフトーンセグメントを生成する工程と、
前記第１のｍｎ×１のハーフトーンセグメントを、ＦＩＦＯ（Ｆｉｒｓｔ  ｉｎ  Ｆｉｒｓｔ  ｏｕｔ）バッファの一つ以上のハーフトーンセグメントと比較する工程と、
前記第１のｍｎ×１のハーフトーンセグメントが、ＦＩＦＯバッファのいずれのハーフトーンセグメントにもマッチングしない場合、（ｉ）リテラルコードワードと、前記第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの前記表現を前記ＦＩＦＯバッファに書き込む工程と、
前記第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現をＦＩＦＯバッファに書き込む工程と、
を含む、方法。
【請求項２】
前記第１のｍｎ×１のハーフトーンセグメントは、ｋ−１の他のハーフトーンセグメントと共に、ルックアヘッドバッファーに保存されており、
ｊ−１≧ｋの他のｍｎ×１のハーフトーンセグメントは、ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングし、
前記ｊのマッチングするハーフトーンセグメントは、少なくとも前記ルックアヘッドバッファに隣接しており、
前記リピート値はｊの指標であり、
前記第１のハーフトーンセグメントの少なくとも１つの前記表現をＦＩＦＯバッファに書き込む工程は、ＦＩＦＯバッファに、ｊの前記第１のｍｎ×１のハーフトーンセグメントを書き込む工程を含む、請求項１に記載の方法。
【請求項３】
前記ｋ―１の他のｍｎ×１のハーフトーンセグメントは、前記画像の他のｍ×ｎピクセルブロックから得られる、請求項２に記載の方法。
【請求項４】
前記ｊのマッチングするハーフトーンセグメントを前記ルックアヘッドバッファから削除する工程をさらに含む、請求項２に記載の方法。
【請求項５】
前記リピートコードワードはショートリピートコードワードまたは拡張リピートコードワードである、請求項２に記載の方法。
【請求項６】
ｊをｋと比較する工程と、
ｊ＜ｋである場合、前記リピートコードワードとして、ショートリピートコードワードを用いる工程と、
ｊ≧ｋである場合、前記リピートコードワードとして、拡張リピートコードワードを使用する工程と、をさらに含む、請求項５に記載の方法。
【請求項７】
前記拡張リピートコードワードは、前記リピートコードワードであり、
前記方法は、
前記第１のｍｎ×１のハーフトーンセグメントのｊの前記表現を前記ＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを第２のｍｎ×１のハーフトーンセグメントと置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、前記画像の第２のｍ×ｎピクセルブロックから得られる工程をさらに含む、請求項６に記載の方法。
【請求項８】
前記第１のｍｎ×１のハーフトーンセグメントを、前記ＦＩＦＯバッファの前記１以上のハーフトーンセグメントと比較する前記工程は、前記第１のｍｎ×１のハーフトーンセグメントにマッチする、ＦＩＦＯバッファ内の最も長く連続するハーフトーンセグメントと、前記第１のｍｎ×１のハーフトーンセグメントに隣接して続いている任意の他のハーフトーンセグメントを決定する工程を含む、請求項１から請求項７のいずれか１つに記載の方法。
【請求項９】
前記第１のｍｎ×１のハーフトーンセグメントは、前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングしており、
前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントの位置の指標である、リピート位置を出力する工程をさらに含む、請求項１から８のいずれか１つに記載の方法。
【請求項１０】
前記ｍ×ｎのハーフトーンマトリックスの各セルは、ｉ―１の閾値を含み、
前記ｉ―１の閾値は、ｉの画素値の範囲を定義し、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックの各セルは、ｌｏｇ２（ｉ）のビット値を含む、請求項１から９のいずれか１つに記載の方法。
【請求項１１】
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックを決定する工程は、前記第１のｍ×ｎピクセルブロックの各特定のセルについて、
前記第１のｍ×ｎピクセルブロックの前記特定のセルの特定のピクセル値を決定する工程と、
前記ｍ×ｎハーフトーンマトリックスの特定のセル内における、ｉの画素値範囲のうちの１つが、前記特定の画素値を含んでいると決定する工程であって、前記第１のｍ×ｎピクセルブロックの前記特定のセルは、前記ｍ×ｎハーフトーンマトリックスの前記特定のセルに対応している、工程と、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックの特定のセルに対し、前記決定された前記ｉの画素値範囲のうちの１つを表すｌｏｇ２（ｉ）ビットの値を書き込む工程と、
を含む、請求項１０に記載の方法。
【請求項１２】
前記第１のｍ×ｎのピクセルブロックの前記第１のハーフトーンのピクセルブロックを決定する工程は、
前記ｍ×ｎのハーフトーンマトリックスの縦に連続するタイルの初期位置がｑピクセルのオフセットを呈するように、前記画像上に前記ｍ×ｎのハーフトーンマトリックスを割り当てる工程を含み、
前記方法は、
前記画像の最も右の列に、ｒ１×ｎのパディング画素列を追加する工程をさらに含む、請求項１から１１のいずれか１つに記載の方法。
【請求項１３】
ｐは、前記ｒ１×ｎのパディング画素列を追加する工程の前における、前記画像の画素値での幅であり、ｒはｍ―（ｐ―ｑ）ｍｏｄ  ｍ  である、請求項１２に記載の方法。
【請求項１４】
非一時的なコンピュータ読み取り可能な記録媒体を含む製造物であって、コンピュータによる実行において、コンピュータに、
ｍ×ｎのハーフトーンマトリックス、および、第１のｍ×ｎのピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程と、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンバージョンの複数の行に対して、ｎ箇所の交互配置工程を施して、第１のｍｎ×１のハーフトーンセグメントを作成する工程と、
前記第１のｍｎ×１のハーフトーンセグメントを、ファーストインファーストアウトバッファ（ＦＩＦＯバッファ）内の１以上のハーフトーンセグメントと比較する工程と、
前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の任意のハーフトーンセグメントにマッチングしない場合、（ｉ）リテラルコードワードおよび第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの表現を前記ＦＩＦＯバッファに書き込む工程と、
前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程と、を含む動作を実行させるプログラム命令を格納する製造物。
【請求項１５】
前記第１のｍｎ×１のハーフトーンセグメントが、ｋ−１の他のｍｎ×１のハーフトーンセグメントと共にルックアヘッドバッファに格納されており、
ｊ−１≧ｋの他のハーフトーンセグメントも、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングし、
前記ｊのマッチングするハーフトーンセグメントは、前記ルックアヘッドバッファ内において隣接し、
前記リピート値はｊを示し、
前記第１のｍｎ×１のハーフトーンセグメントの前記少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程は、前記第１のｍｎ×１のハーフトーンセグメントのｊの表現を前記ＦＩＦＯバッファに書き込む工程を含む、請求項１４に記載の製造物。
【請求項１６】
前記リピートコードワードがショートリピートコードワードまたは拡張リピートコードワードである、請求項１４または１５に記載の製造物。
【請求項１７】
前記動作は、
ｊをｋと比較する工程と、
ｊ＜ｋである場合に、前記リピートコードワードとして前記ショートリピートコードワードを用い、
ｊ≧ｋである場合、前記リピートコードワードとして前記拡張リピートコードワードを用いる工程と、
をさらに含む、請求項１６に記載の製造物。
【請求項１８】
前記拡張リピートコードワードは、前記リピートコードワードであり、
前記動作は、
前記第１のｍｎ×１のハーフトーンセグメントのｊの表現をＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを、第２のｍｎ×１のハーフトーンセグメントに置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、画像の第２のｍ×ｎピクセルブロックから得られる、工程をさらに含む、請求項１６に記載の製造物。
【請求項１９】
プロセッサと、
データ記憶装置と、
前記データ記憶装置に記憶され、プロセッサによる実行において、コンピュータに、請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させる、プログラム命令と、
を備えるコンピュータ。
【請求項２０】
コンピュータによる実行において、コンピュータに請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はハーフトーンのデジタル画像の圧縮方法に関する。
【背景技術】
【０００２】
ハーフトーン処理は、サイズ、形状または間隔において異なる複数のドットを用いることにより、連続した色調のイメージをシミュレーションする技術である。これらの、基本的な２値（バイナリ）のハーフトーン処理の単一のトーンレベルの複数のドットにより、中間調のドットパターンを形成する。中間調のドットパターンを適切に設計することによって、単一のトーンレベルのオン／オフ動作のマーキングを介して、複数の色調（トーン）および滑らかなシェーディング（濃淡）がハーフトーンの画像に表示される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】ＵＳ２００７／０１１６３６７
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、ハーフトーン処理されたデジタル画像の圧縮方法を提供する。
【課題を解決するための手段】
【０００５】
例示の実施形態において、ｍ×ｎのハーフトーンマトリックスおよび画像の第１のｍ×ｎピクセルブロックに基づいて、第１のｍ×ｎピクセルブロックの第１のｍ×ｎハーフトーンバージョンが、決定されてもよい。ｎ箇所のインターリーブが、第１のｍｎ×１ハーフトーンセグメントを作成するために、第１のｍ×ｎのピクセルブロックの第１のｍ×ｎハーフトーンバージョンの行に実行されてもよい。第１のｍｎ×１のハーフトーンセグメントは、ファーストインファーストアウト（ＦＩＦＯ）バッファの１つ以上のハーフトーンセグメントと比較されてもよい。第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファのいずれのハーフトーンセグメントにもマッチングしない場合、リテラルコードワードおよび第１のｍｎ×１のハーフトーンセグメントの表現が出力されてもよく、第１のｍｎ×１のハーフトーンセグメントの表現が、ＦＩＦＯバッファに書き込まれてもよい。第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファの特定のハーフトーンセグメントにマッチングする場合、リピートコードワードおよびリピート値が出力されてもよく、そして、第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現が、ＦＩＦＯバッファに書き込まれてもよい。
【０００６】
追加の実施形態は、コンピュータによる実行に応じて、コンピュータに上記の、または他の例示の実施形態における動作を実行させるプログラム命令を格納した非一時的コンピュータ読み取り可能な記録媒体を含んでいてもよい。
【０００７】
さらなる実施形態は、少なくとも１つのプロセッサと、データ格納部と、コンピュータによる実行に応じて、コンピュータに上記の、または他の例示の実施形態における動作を実行させる、データ収納部に格納されたプログラム命令を含むコンピュータを含んでいてもよい。
【０００８】
さらに他の実施形態は、コンピュータによる実行に応じて、コンピュータに上記の例示の実施形態の少なくとも１つに従って動作を実行させるプログラムを含んでいてもよい。
【０００９】
必要に応じて添付の図面を参照して示される以下の詳細な説明を読むことによって、これら、および同様の他の態様、利点および変形例が、当業者にとって明らかになる。更に、この概要およびこの文書の他の部分で提供される説明は実施例により請求項に記載の構成を説明することが意図され、限定を目的とするものではないことを理解されたい。
【発明の効果】
【００１０】
本発明によれば、ハーフトーン処理されたデジタル画像の圧縮方法が提供される。
【図面の簡単な説明】
【００１１】
【図１】図１は、例示の実施形態における印刷装置を表す。
【図２】図２は、例示の実施形態における、印刷装置のコンピュータの構成要素を示すブロック図である。
【図３】図３は、例示の実施形態における、印刷装置に関する様々なデータ経路を例示するブロック図である。
【図４】図４は、例示の実施形態における、画像中の画素への、ハーフトーンマトリックスの適用を表す図である。
【図５Ａ】図５Ａは、例示の実施形態における、画像上に適用されるハーフトーンマトリックスを表す図である。
【図５Ｂ】図５Ｂは、例示の実施形態における、画像上に列を追加して適用されるハーフトーンマトリックスを表す図である。
【図６】図６は、例示の実施形態における、画像及び前記画像の拡大された部分を表す図である。
【図７】図７は、例示の実施形態における、列を追加する画像のハーフトーン処理を表す図である。
【図８】図８は、例示の実施形態における、ハーフトーン処理された画像の一部の１６進数による表現を表す図である。
【図９】図９は、例示の実施形態における、ハーフトーン処理された画像に対する交互配置（インターリービング（ｉｎｔｅｒｌｅａｖｉｎｇ））を表す図である。
【図１０】図１０は、例示の実施形態における、ヒストリーバッファ、ルックアヘッドバッファ、および新しいセグメントバッファを表す図である。
【図１１】図１１は、例示の実施形態における、圧縮後のハーフトーン処理されたセグメントのフォーマットを表す図である。
【図１２】図１２は、例示の実施形態におけるフローチャートである。
【図１３】図１３は、例示の実施形態において、前記ルックアップバッファ内のセグメントに対しマッチングが見出されなかった場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１４】図１４は、例示の実施形態において、前記ルックアップバッファ内の２つのセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１５】図１５は、例示の実施形態において、前記ルックアップバッファ内の複数のセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１６】図１６は、例示の実施形態において、前記ルックアップバッファ内の１つのセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１７】図１７は、例示の実施形態において、列の追加が実行により、前記ルックアップバッファ内の３つのセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１８】図１８は、例示の実施形態において、前記ルックアップバッファおよび前記新しいセグメントバッファ内の全てのセグメントに対しマッチングが見出され、拡張されたリピートコードワードの使用が促進される場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１９】図１９Ａ、１９Ｂ、１９Ｃ、および１９Ｄは、列の追加の使用により、より効果的にハーフトーン画像圧縮が可能となるというシナリオを表す図である。
【図２０】図２０は、例示の実施形態におけるフローチャートである。
【発明を実施するための形態】
【００１２】
以下、例示の実施形態における方法および装置が、本願明細書において説明される。他の例示の実施形態または特徴が、本願明細書において提示される主題の範囲および精神を逸脱しない範囲で、さらに利用されてもよい。以下の詳細な説明においては、添付の図面が参照され、その図面は詳細な説明の一部を構成する。
【００１３】
本願明細書において記載されている例示の実施形態は、限定を意図したものではない。一般的に本願明細書において記載され、図示されているように、本発明の態様が多種多様な異なる構成において配置される、置換される、結合される、分離される、そして設計されることができることが理解され、その全ては本願明細書において明確に考察される。
１．イントロダクション
印刷技術は、白黒の画像だけを形成する単純なドットマトリクスベースの出力装置から高解像度のカラー画像を形成することができる今日の高度なレーザーベースの印刷装置まで、最近の３０年ほどで進化してきている。さらに、最新の印刷装置は、複写機、スキャナ、およびファックスとして機能することもできる。そのために、これらの装置は、印刷またはファックスするためにキューイングされる、または、走査された多数の電子文書を格納することが可能となっていることがある。このように、多くの印刷装置は、例えば、一つ以上のプロセッサ、データ格納部、および入出力インタフェースを含むことができるコンピュータの特別な形態である。
【００１４】
印刷装置が、住宅において、ビジネスにおいて、または、他の種類の場所において用いられるかどうかにかかわらず、印刷装置は様々な他のコンピュータに通信可能な状態で接続されることができる共用されたリソースであってもよい。従って、ある環境においては、多数のコンピュータが、印刷するための電子文書を印刷装置に発信することができるようになるにつれて、印刷装置の記憶容量に対する要件が非常になってくる。一般に、印刷装置は、先着順の方法で、一度に１つの電子文書を印刷、複製、ファックス、および／またはスキャンする。従って、印刷装置は、潜在的に、処理されるために待っているかなりの数の電子文書を格納することができる。データ格納部（例えば、ランダムアクセスメモリ（ＲＡＭ）、ソリッドステートメモリ、ハードディスクメモリ、および／またはフラッシュメモリ等のメモリ）のコストが高価でありえるので、印刷装置のデータ格納部において必要とされる容量を減らすことを目的として、格納された電子文書を圧縮することは有益でもよい。加えて、いくつかの電子文書が印刷装置およびコンピュータに、および／またはそれから送信されることができるので、これらの電子文書を圧縮することは転送をより速くすることができ、また、使用するネットワーク容量を少なくすることができる。
【００１５】
さらに、印刷ジョブが大きくなることがある（例えば、印刷ジョブは数百ページも含んでいる１または複数の電子文書を含むことがある）ので、各ジョブが印刷される前に、キューに入れられた印刷ジョブを圧縮することは短期記憶領域を節約することができる。加えて、ユーザは、後ほど印刷するために長期間記憶装置の印刷ジョブを保存したいと考えることがある。したがって、印刷ジョブを圧縮することによって、より多くの印刷ジョブを保存するることができる。さらにまた、長期記憶からサイズの大きい印刷ジョブを格納あるいは引き出しは遅くなることがあるが、印刷ジョブを圧縮し、サイズを小さくすることによって、迅速に処理することが可能となる。
２．例示の実施形態の印刷装置
図１は、例示の実施形態における印刷装置１００を示す。印刷装置１００は、部分的に格納された、および／または全体が格納された電子文書を様々な形の物理的な出力メディアに印刷するように構成されていてもよい。これらの出力メディアは、紙、ＯＨＰの透光性のスライド、その他の様々なサイズおよびタイプを含むが、これに限定されるものではない。印刷装置１００は、「プリンタ」と呼ばれてもよい。
【００１６】
印刷装置１００は、パーソナルコンピュータ、サーバ装置、プリントサーバ等のコンピュータに対するローカル周辺機器として機能することができる。これらの場合には、印刷装置１００は、例えばシリアルポートケーブル、パラレルポートケーブル、ユニバーサルシリアルバス（ＵＳＢ）ケーブル、Ｆｉｒｅｗｉｒｅ（ＩＥＥＥ  １３９４）ケーブル、またはＨｉｇｈ―Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ（ＨＤＭＩ）ケーブル等のケーブルにより、コンピュータに取り付けられてもよい。このように、コンピュータは、印刷装置１００のための電子文書の出所（ソース（ｓｏｕｒｃｅ））としての機能を果たすことができる。
【００１７】
一方、印刷装置１００は、例えばイーサネットまたは８０２．１１の（Ｗｉｆｉ）インタフェースのような、有線または無線のネットワークインタフェースを含んでいてもよい。このように配置されることにより、印刷装置１００は、ネットワークの上の印刷装置１００と通信することができる任意の数のコンピュータ用の印刷装置として機能することができる。いくつかの実施形態においては、印刷装置１００は、同時に、ローカル周辺機器およびネットワーク上のプリンタとしての機能を果たすことができる。
【００１８】
印刷装置１００を使用するために、コンピュータは、１つ以上のプリンタドライバをインストールしてもよい。これらのプリンタドライバは、印刷される電子文書を、コンピュータに格納される様々なローカルな表現から、印刷装置１００によってサポートされる１つ以上の表現に、変換するソフトウェア構成要素を含んでいてもよい。
【００１９】
これらにかかわらず、印刷装置１００は、コンピュータであると考慮されてもよく、印刷に関連する、および印刷に関連しない作業を実行してもよい。
【００２０】
上記の如く、印刷装置１００は、複写機能、ファックス機能、およびスキャナ機能を含んでいてもよい。いくつかの実施形態においては、複写機および／またはファックス機能を促進することを目的として、印刷装置１００は、スキャナ機能を使用してもよい。例えば、印刷装置１００は、物理的な文書を電子的なフォーマットにするようにスキャンすることができて、そしてそれから、結果として得られる電子文書を印刷してコピーとしての機能を提供し、および／または電話インターフェースを介して結果として得られる電子文書を送信してファックスとしての機能を提供することができる。
【００２１】
その様々な機能をサポートするために、印刷装置１００は、ドキュメントフィーダ／排出トレイ１０２、用紙収容部１０４、ユーザインタフェース１０６、スキャナー素子１０８、および筐体１１０を含んでいてもよい。印刷装置は多種多様な形態をとり得ることができる。従って、印刷装置１００は、図１において表されるより多くであるかあるいはより少しの構成要素を含んでいてもよく、および／または、図１において表されるのとは異なる方法で構成要素が配置されていてもよい。
【００２２】
ドキュメントフィーダ／排出トレイ１０２は、スキャンされることになっているか、複製されることになっているかまたは、ファックスされることになっている物理的な文書（例えば、１枚以上の紙の束）を保持することができる。好ましくは、ドキュメントフィーダ／排出トレイ１０２により、ユーザの手動作業を必要とすることなく、印刷装置１００によって処理される複数の物理的な文書を自動的に供給することができてもよい。ドキュメントフィーダ／排出トレイ１０２は、また、印刷装置１００によって処理された物理的な文書を保持するための１つ以上の独立の排出トレイを含んでいてもよい。これらは、例えば、印刷装置１００のファックスおよび／またはコピー機能によって形成された物理的な文書と同様に、印刷装置１００によってスキャンされたか、コピーされたか、またはファックスされた物理的な文書を含んでいてもよい。
【００２３】
用紙カセット１０４は、様々な形態の物理的なメディア用のトレイおよび／または供給部を含んでいてもよい。例えば、用紙カセット１０４は、８  １／２×１１インチの用紙、Ａ４紙、レターヘッド紙、封筒、その他について、別々のトレイを含んでいてもよい。物理的なメディアを出力する（例えば、印刷、複製、および／またはファックスを受け取る）印刷装置１００のいかなる機能のためにも、用紙カセット１０４は、物理的なメディアを供給することができる。
【００２４】
ユーザインタフェース１０６は、例えばユーザからの入力の受け取りや、出力をユーザへの供給のような、人間または人間以外のユーザと、印刷装置１００との相互作用を促進することができる。このように、ユーザ・インタフェース１０６は、例えばキーパッド、キーボード、タッチセンシティブまたはプレゼンスセンシティブのパネル、ジョイスティック、マイクロホン、スチールカメラおよび／またはビデオ・カメラのような、入力素子を含んでいてもよい。ユーザインタフェース１０６は、また、例えば、ディスプレイスクリーン（例えば、プレゼンスセンシティブなパネルと組み合わされてもよい）、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ベースのディスプレイ、デジタルライトプロセッシング（ＤＬＰ（登録商標））を使用するディスプレイ技術、電球、および／または１つ以上の他の類似の、現在知られているあるいは今後開発される装置等の、１つ以上の出力素子を含んでいてもよい。ユーザインタフェース１０６は、また、スピーカ、スピーカ・ジャッキ、オーディオ出力ポート、オーディオ出力デバイス、イヤホン、および／または他の類似の、現在公知であるかまたは将来開発される装置を介して、聞き取り可能な出力を生成することが可能に構成されていてもよい。
【００２５】
スキャナ素子１０８は、ガラスパネルであってもよく、ガラスパネルの下側においては、移動可能な光源が、ガラスパネル上に配置される物理的なメディアをスキャンするために作動してもよい。
あるいは、ガラスパネルの下側に配置されたデジタルカメラが、物理的なメディアの画像を撮影することによって、ガラスパネルの上に配置される物理的なメディアを「走査」してもよい。走査された物理的なメディアの画像は、印刷装置１００と関連したデータ格納部に格納されてもよい。
【００２６】
筐体１１０は、例えばドキュメントフィーダ／排出トレイ１０２、用紙カセット１０４、ユーザインタフェース１０６、およびスキャナ素子１０８のような、印刷装置１００の種々の構成要素を包含する、および／または相互接続する物理的なハウジングを含んでいてもよい。加えて、筐体１１０は、図１に示されない他の構成要素を格納していてもよい。例えば、筐体１１０は、１つ以上のトナーカートリッジ、液体インクジェット、ベルト、ローラー、および／または電源を含んでいてもよい。更に、筐体１１０は、例えば有線および／または無線のネットワークインタフェース、電話通信インタフェース（例えば、ＲＪ４５ジャッキ）、ＵＳＢインターフェース、ＢＬＵＥＴＯＯＴＨ（登録商標）インタフェース、カード読取りポートなどのコミュニケーションインターフェースを含んでいてもよい。
【００２７】
印刷装置１００は、汎用の、および／または特別に設計されたコンピュータの構成要素に基づいていてもよいので、筐体１１０は、これらの構成要素のいくつかあるいは全てを含んでいてもよい。その点に関して、図２は、印刷装置１００に含まれることができるコンピュータ装置の構成要素２００（例えば、コンピュータの機能素子）の例示の実施形態を示す。
【００２８】
コンピュータ装置の構成要素２００は、プロセッサ２０２、データ格納部２０４、および入出力機能素子２０６を含んでいてもよく、その全てはシステムバス２０８または類似の機構によって連結されていてもよい。プロセッサ２０２は、例えば１つ以上の汎用プロセッサおよび／または１つ以上の専用プロセッサ（例えば、特定用途向け集積回路（ＡＳＩＣ）またはデジタル信号プロセッサ（ＤＳＰ）、その他））のような、１つ以上の中央演算処理装置（ＣＰＵ）を含んでいてもよい。
【００２９】
次に、データ格納部２０４は、揮発性および／または不揮発性のデータ格納部を含んでいてもよく、全体的にあるいは部分的にプロセッサ２０２と統合されていてもよい。データ格納部２０４は、プロセッサ２０２によって実行可能なプログラム命令を含んでいてもよく、本願明細書において記載されているさまざまな方法、プロセス、または機能を実行するこれらの命令によって操作されるデータを格納していてもよい。あるいは、これらの方法、プロセス、または機能は、ハードウェア、ファームウェア、および／またはハードウェア、ファームウェアおよびソフトウェアの任意の組合せによっても定義されることができる。従って、データ格納部２０４は、１つ以上のプロセッサによる実行に応じて、本願明細書または添付の図面に開示されている任意の方法、プロセス、または機能を印刷装置１００に実行させる、プログラム命令を格納している有形の、非一時的なコンピュータ読み取り可能な記録媒体を含んでいてもよい。
【００３０】
入出力機能２０６は、ユーザインタフェース１０６に関して記載されている任意の機能および／または構成要素を含んでいてもよい。このように、入出力機能２０６は、プロセッサ２０２の動作を構成し、および／または制御する役割を果たしていてよい。入出力機能２０６は、プロセッサ２０２によって実行される動作に基づいて、出力を提供してもよい。
【００３１】
印刷装置のこれらの実施形態は、説明の便宜上設けられていることを理解されたい。更に、これらに加えておよび／または代えて、上記の実施形態に、本願明細書における実施形態の要旨を逸脱しない範囲で、他の可能な、プリンタおよびコンピュータ技術の他の組合せおよび／または補足的な組合せが、存在してもよい。
【００３２】
図３は、印刷装置１００によって処理される電子文書の表現が通信されることができる可能なデータ経路のいくつかを示す。図３においては、印刷装置１００は、スキャナー機能３０２および印刷機能３０４を含んでいると仮定されている。これらの機能の各々は、ハードウェア、ファームウェア、ソフトウェア、またはハードウェア、ファームウェアおよび／またはソフトウェアの任意の組合せで実行することができる。加えて、スキャン機能３０２および印刷機能３０４の各々は、コンピュータ３００に通信することができ、そしておそらく他のコンピュータにも通信することができる。いくつかの場合において、印刷装置１００でサポートされるデータ経路は、「パイプライン」と称されることもある。
【００３３】
スキャン−プリントデータ経路３１０は、スキャン機能３０２および印刷機能３０４によってサポートされていてもよい。スキャン−プリントデータ経路３１０は、例えば、ユーザが印刷装置１００に物理的な文書を複製するように指示する場合に使われることができる。この指示に応答して、スキャン機能３０２は、物理的な文書を電子文書にスキャンすることができ、電子文書を印刷機能３０４に、スキャン−プリントデータ経路３１０を介して送信することができる。スキャン−プリントデータ経路３１０を使用することにより、少なくとも一時的に、電子文書の一部もしくは全部を印刷装置１００のデータ格納部に格納してもよい。それから、印刷機能３０４は、物理的なメディア（例えば、１つ以上の用紙）に、電子文書を印刷することができる。
【００３４】
スキャン−ホストデータ経路３０６は、スキャン機能３０２およびコンピュータ３００によってサポートされてもよい。スキャン−ホストデータ経路３０６は、例えば、ユーザが印刷装置１００に物理的な文書をスキャンするように指示する際に使われることができる。ユーザは、印刷装置１００に、結果として生じる電子文書の表現をコンピュータ１００に送信するように指示することもできるし、または、自動的に電子文書をコンピュータ３００に送信するように、印刷装置１００が予め設定されていてもよい。このように、この指示に応答して、スキャン機能３０２は、物理的な文書を電子文書にスキャンすることができ、コンピュータ３００にスキャン−ホストデータ経路３０６を介して、結果として生じる電子文書を送信することができる。スキャン−プリントデータ経路３１０の使用により、少なくとも一時的に、電子文書の一部もしくは全部を印刷装置１００のデータ格納部に格納して、結果として生じる電子文書の表現をコンピュータ３００に送信してもよい。
【００３５】
ホスト−プリントデータ経路３０８は、コンピュータ３００および印刷機能３０４によってサポートされていてもよい。ホスト−プリントデータ経路３０８は、ユーザが、コンピュータ３００に電子文書を印刷装置１００に印刷するように指示する際に使われてもよい。この指示に応答して、コンピュータ３００は、電子文書の表現を印刷機能３０４に送信してもよい。印刷装置１００は、印刷機能３０４を介して、物理的な媒体に電子文書を印刷することができる。電子文書を印刷する前におよび／または印刷する間、電子文書の一部もしくは全部が、印刷装置１００のデータ格納部に格納されてもよい。
【００３６】
明らかに、印刷装置１００でサポートされる他のデータ経路と恐らく同様に、上述したデータ経路のうちの少なくとも１つに対し、電子文書が、ネットワークまたはケーブル上の記憶および／または送信が必要となってもよい。電子文書の蓄積および／または送信の効率は、これらの電子文書を圧縮することによって改善されることができる。例えば、電子文書が、平均して、初期のサイズの１／４のサイズに圧縮されることができる場合、データ格納部内の一定の容量において、約４倍の電子文書を格納することができる。更に、圧縮されていない電子文書の送信する場合に比べ、ネットワークまたはケーブルの上において、これらの圧縮された電子文書を、約４倍の速さで送信することが可能となりうる。
【００３７】
以下、印刷装置１００によって処理される電子文書の圧縮を提供する各種実施形態を説明する。
３．例示の実施形態の画像のカラーモデル
電子文書は、多くのカラーモデルを使用して表現されることができる。従って、有効な圧縮技術が、これらのモデルの一部もしくは全部に作用することが可能であるべきである。更に、ハーフトーン圧縮が、個々のカラーモデルに特有であってもよいし、あるいはカラーモデルの各チャネルに別に作用することができてもよい。
【００３８】
例えば、赤―緑―青（ＲＧＢ）のカラーモデルが、例えばテレビ、モニタ、およびコンピュータスクリーンのような電子出力装置上の画像の表示に用いられてもよい。ＲＧＢは、可視光域の色を表現する様々な方法において、赤色光、緑色光、および青色光が互いに足し合わされる加法混色のカラーモデルである。例えば、シアンは緑および青を混合することによって表現することができ、黄色は赤および緑を混合することによって表現することができ、マゼンタは赤および青を混合することによって表現することができ、白は、赤・緑・青を混合することによって表現されることができる。
【００３９】
ＲＧＢ画像における画素は、３つのチャネルのタプル（Ｒ，Ｇ，Ｂ）として表されることができる。各チャネルはゼロから所定の最大値（例えば、２５５）まで変化することができる。もし、チャネルの全てがゼロである場合、黒が表現されてもよい。チャネルの全てが最大値である場合、再現可能な最も明るい白が表現されてもよい。
【００４０】
異なる出力装置においては、同じＲＧＢ画像を異なる方式により表示することができるという点で、ＲＧＢの出力は典型的にはデバイスに依存する。ある場合には、これらの違いは、人間によって知覚されることがある。いくつかの実施形態においては、スキャン−ホストデータ経路３０６を使用して印刷装置１００にスキャンされる物理的な文書が、ＲＧＢカラーモデルを使用して符号化されることができる。
【００４１】
シアン・マゼンタの黄色（ＣＭＹ）カラーモデルが、印刷装置によって色画像を印刷するために用いられることができる。ＣＭＹは、可視光域の色を表現する様々な方法において、白色表面上に、シアン、イエローおよびマゼンタが付与される減法混色のカラーモデルである。例えば、赤はマゼンタおよびイエローを混合することによって表現することができ、青はシアンおよびマゼンタを混合させることによって表現することができ、そして、緑はシアンおよびイエローを混合することによって表現することができる。このように、ＣＭＹカラーモデルは、ＲＧＢカラーモデルを補うもの（補色の関係にある）と考えてもよい。
【００４２】
ＣＭＹ画像における画素は３つのチャネルのタプル（Ｃ，Ｍ，Ｙ）として表されることができる。そして、各チャネルはゼロから所定の最大値まで変化することができる。ャネルの全てがゼロである場合、白が表現されてもよい。チャネルの全てが最大値である場合、黒が表現されてもよい。
【００４３】
ＲＧＢカラーモデルと同様に、同じＣＭＹの画像が、異なる印刷装置上では、異なるように見える可能性があるという点で、ＣＭＹ出力は、典型的には、デバイスに依存する。ある場合には、これらの違いは、人間によって知覚される可能性がある。いくつかの実施形態においては、ホスト−プリントデータ経路３０８および／またはスキャン−プリントデータ経路３１０を使用している印刷装置１００によって印刷される電子文書が、ＣＭＹカラーモデルを使用して符号化されることができる。
【００４４】
いくつかの実施形態では、４つのチャネルを用いるＣＭＹＫカラーモデルが用いられることもできる。この４つのチャネルを用いたＣＭＹＫカラーモデルは、キー（ｋｅｙ）チャネル（黒チャネル）も使われるという点以外、ＣＭＹカラーモデルとほぼ同様または同じであってもよい。黒を形成するためにシアン、マゼンタおよび黄色を混合することに加えて、別のキーの（黒の）インク源が、黒を形成するために用いられることができる。このように、ＣＭＹＫ画像の画素は４つのチャネルのタプル（Ｃ，Ｍ，Ｙ，Ｋ）として表することができ、各チャネルはゼロから所定の最大値まで変化することができる。
【００４５】
ＣＭＹＫカラーモデルを使用して、ＣＭＹモデルと同じ色がサポートされることができるが、Ｋの色剤がＣ、ＭおよびＹの色剤の混合物と置き換えることができるので、典型的には、色剤（インク）の使用量をより少なくすることができる。しかしながら、ＣＭＹＫカラーモデルの、他のカラーモデルへの変換や、他のカラーモデルからの変換は、必ずしも都合よくは可能とならないことがある。なぜなら、Ｋの色剤の追加により、例えば、同じ色がＣ、Ｍ、ＹおよびＫの異なる組合せにより表現できることから、冗長性が付加される可能性があるからである。
【００４６】
他のカラーモデルはグレー（中間調）、または、グレースケールとも呼ばれ、モノクロの画像の表現に使われることができる。ＲＧＢおよびＣＭＹ／ＣＭＹＫカラーモデルとは異なり、グレースケールカラーモデルの各画素は、画素の強度を符号化する単一のチャネルを使用して表される。グレーチャネルによって使用される値は、黒に対応するゼロから、白（例えば、２５５）に対応する所定の最大値まで、変化することができる。いくつかの実施形態では、印刷装置１００でサポートされる１つ以上のデータ経路において、グレースケールのカラーモデルを使用して、画像を符号化することが可能となってもよい。
【００４７】
他のカラーモデルとしては、例えばＹＣｂＣｒがある。ある実施態様においては、このカラーモデルが、画像の代替の表現として用いられることができる。具体的には、Ｙチャネルは画素の輝度を表し、ＣｂおよびＣｒチャネルが、それぞれ、青−黄クロミナンス（ｂｌｕｅ−ｙｅｌｌｏｗ  ｃｈｒｏｍｉｎａｎｃｅ）および赤−緑クロミナンス（ｒｅｄ−ｂｌｕｅ  ｃｈｒｏｍｉｎａｎｃｅ）を表すことができる。ＹＣｂＣｒカラーモデルは、ＲＧＢカラーモデルおよびＣＭＹカラーモデルとの関係性が明確であり、比較的容易に、これらのカラーモデルからの変換およびこれらのカラーモデルへの変換が可能である。
【００４８】
ＹＣｂＣｒカラーモデルに対する更なる利点としては、ＹＣｂＣｒカラーモデルを用いて符号化される画像の圧縮は、ＲＧＢまたはＣＭＹ／ＣＭＹＫカラーモデルを用いて符号化される画像の圧縮より効率的であるという傾向がある点がある。特に、人間の眼は、画像における高周波（例えば、急速に変化する）成分のクロミナンスに関する情報の検知が得意ではない。従って、ＣｂおよびＣｒチャネルの高周波成分を無視することによっても、ＹＣｂＣｒカラーモデルを用いて符号化された画像は、この情報（クロミナンスの情報）を十分に利用したものとすることができる。このように、以下に詳述するように、特定のカラーモデルに符号化される画像は、圧縮のパフォーマンスを向上させる目的で、圧縮の前にＹＣｂＣｒカラーモデルに変換されてもよい。
４．例示の実施形態の画像ハーフトーン処理
多くのデジタル画像は、画像の色またはグレイスケールの部分がより明るいトーンからより暗いトーンまで滑らかに移行する、あるいは逆の関係になる連続する色調を含んでいてもよい。しかしながら、多くのプリンタは、連続する色調をサポートしていない。その代わりに、プリンタは、最も明るいトーンから最も暗いトーンまでの離散的な数のトーンをサポートしていてもよい。例えば、単純な白黒のプリンタは、画像の任意の注目ピクセルに対し、黒または白のいずれかの出力だけをサポートしていてもよい。
【００４９】
ハーフトーン処理は、連続階調の画像を複数のパターンの画素の濃淡に解体し、滑らかに移行するグレーまたはカラーの錯覚的な表現を生成する方法を含む。本願明細書においては、「画像」という用語が完全な画像（ｆｕｌｌ  ｉｍａｇｅ）または画像ブロックのような部分的な画像を指すことがある。下記の実施形態のいくつかにおいては、簡単のために、動作は、完全な画像よりもむしろ画像ブロックについて例示される。
【００５０】
ハーフトーンマトリックスはｍ×ｎブロックのセルであってもよく、そして、各セルが１つ以上の閾値を含んでいてもよい。ハーフトーンマトリックスを画像に適用するときには、ハーフトーンマトリックスは、画像の各画素が適用されたハーフトーンマトリックスのうちの１つにあるセルと、それぞれ対応付けられるように、画像に適用される。ハーフトーンマトリックスは、特定のプリンタの特性に基づいて定義されることができ、従って、出力装置固有であってもよい。ハーフトーンマトリックスは、ハーフトーンスクリーン、閾値テーブル、またはディザテーブルと称されてもよい。
【００５１】
画像の各画素は、画素に対するハーフトーン値を決定する目的で、その対応するセルの閾値と比較されてもよい。例えば、ある特定のカラーチャネルにおいて、画素は、０―２５５の、例えばその画素の強度または輝度を表す値を呈していてもよい。対応付けられているセルは、３つの閾値、６４、１２８および２４０を含んでいてもよく、これにより４つの範囲：０―６４、６５―１２８、１２９―２４０および２４１―２５５が定義されてもよい。画素の値はこれらの範囲のうちの１つに該当し、画素が該当する範囲により、画素のハーフトーン値が定義されてもよい。従って、画素のハーフトーン値は、２ビットの値によって定義されることができる。例えば、００は０―６４の範囲を示し、０１は範囲６５―１２８の範囲を示し、１０は１２９―２４０の範囲を示し、そして、１１は２４１―２５５の範囲を示していてもよい。
【００５２】
より形式的には、ハーフトーンマトリックス内の各セルに対して定められる閾値がある場合、これらの閾値はｉの範囲を定めることができ、そして、画素値が該当する範囲は、ｌｏｇ２（ｉ）のビット値によって表されることができる。画像の各画素にハーフトーンマトリックスを適用することにより、各画素がｌｏｇ２（ｉ）ビット値によって表される画像のハーフトーンバージョンが得られてもよい。それから、このハーフトーン処理された画像は、ｉの色調をサポートするプリンタに送られてもよい。
【００５３】
このプロセスは、図４に図示される。画像の画素マトリックス４００は、多くの個々の画素を含み、各々が８ビット値（すなわち、０―２５５）を呈する例示の画素４０２および４０４を含む。ハーフトーンマトリックス４０６は、各々が１５の閾値（すなわち、０−２５５の全体の範囲内において、０から１５までで表される１６の範囲）を示す表現を含む、例示のセル４０８および４１０を含むパターンを含んでいる。
【００５４】
ハーフトーンマトリックス４０６は、例示のセル４０８が例示の画素４０２と関連付けられ、例示のセル４１０が例示の画素４０４と関連付けられるように、画像の画素マトリックス４００の上に覆わせることができる。例示の画素４０２の値は、例示のセル４０８の閾値によって定義される範囲にマッピングされ、例示の画素４０２の値は、例示のセル４１０の閾値によって定義される範囲にマッピングされてもよい。
【００５５】
例示のセルのそれぞれは、異なる閾値を定義していてもよい。例えば、例示のセル４０８は閾値４１２を定義し、例示のセル４１０は閾値４１４を定義してもよい。このように、画素をこれらの各閾値にマッピングすることにより、例示の画素４０２の値が、閾値４１２のうち、第４の閾値と第５の閾値との間に該当し、例示の画素４０４の値が、閾値４１４のうちの第１５の閾値を上回っていると決定される。このように、例示の画素４０２のハーフトーン値は４として表現され、その一方で、例示の画素４０４のハーフトーン値が１５として表現されることができる。
【００５６】
さらに一般的にいえば、ハーフトーンマトリックスのセルが閾値を定義すると仮定する。画素値が最も高い閾値以上である場合、ハーフトーン値は最も高い。画素値が最も低い閾値より小さい場合、ハーフトーン値は０である。画素値がｃ番目の閾値以上であるが、（ｃ＋１）番目の閾値より小さい場合、ハーフトーン値はｃである。
【００５７】
例示の画像ブロックに適用される例示のハーフトーンマトリックスが、図５Ａにおいて表される。
ハーフトーンマトリックスの各セルは、Ａ１…Ａ８またはＢ１…Ｂ８のうちの１つとしてラベルが付される。これらのラベルの各々は、閾値の、潜在的に異なるセットを示す。このように、Ａ１とラベルが付されているセルは、Ａ２やその他のラベルが付されているセルとは異なる閾値のセットを備えていてもよい。
【００５８】
ハーフトーンマトリックスのオーバーレイパターンは、垂直方向に隣接するタイルの初期位置が、２セルで相殺される（オフセットされる）ように、左側にシフトされる。例えば、ハーフトーンマトリックス５０２のＡ１セルは、ハーフトーンマトリックス５００のＡ１セルより２つのセル分だけ左にシフトしている。同様に、ハーフトーンマトリックス５０４のＡ１セルは、ハーフトーンマトリックス５０２のＡ１セルより２つのセル分だけ左にシフトしている。このオフセットにより、審美的に魅力的な角度を有するプリンタによって、ハーフトーンパターンが形成される。
【００５９】
ハーフトーンマトリックスをタイリングするときの１つの考えられる不利な点としては、画像の幅が、ハーフトーンマトリックスの非整数倍である場合に画像の各列に適用することが必要となる場合である。例えば、図５Ａにおいては、画像ブロックは１２×８画素であり、ハーフトーンマトリックスは８×２セルである。このように、１  １／２のハーフトーンマトリックスが、画像ブロックの幅にわたることが必要とされる。以下で更に詳細に説明される理由により、画像の列をパディングする（詰め物をする、埋め込む）ことにより、ハーフトーン処理された画像の圧縮効率の向上につながる。特に、整数のハーフトーンマトリックスの整数が各列に適用されることができるように、画像ブロックは画素の追加の列を用いてパディングされることができる。これらのパディングのコラム（列（埋め込み画素列））は、画像ブロックの最も右にあるコラムの画素のコピーを含んでいてもよい。
【００６０】
パディングのコラムの数は、様々な方法で決定されることができる。パディングの柱の数（ｒ）を決定する１つの可能な方法は、方程式：ｒ＝ｍ  ｒ−（ｐ―ｑ）ｍｏｄ  ｍに従い、ここで、ｍは、セル内のハーフトーンマトリックスの幅であり、ｐは複数の画素の画像ブロックの幅であり、そして、ｑはオフセットである。図５Ａの例においては、ｍ＝８、ｐ＝１２、およびｑ＝２である。
従って、ｒ＝６である。
【００６１】
図５Ｂは、図５Ａの画像ブロックを、６の列をパディングし、ハーフトーンマトリックスをタイリングして示している。図５Ｂに示されるタイリングされたハーフトーンマトリックスに加えて、さらなるハーフトーンマトリックスが、パディングされた画像ブロックに対し、１対の行の右端から行の次の下側の一対の左端までハーフトーンマトリックスで覆うことによって、タイリングされることができる。このように、ハーフトーンマトリックスは、右上角のＡ１…Ａ６およびＢ１…Ｂ６のセルに適用されてもよく、そして、次の２つの行の左側にあるＡ７…Ａ８およびＢ７…Ｂ８セルに包み込ませてもよい。従って、一対の行のそれぞれが左から右へ隣接すると読み込まれる場合に、ハーフトーンマトリックスは順次繰り返される。
【００６２】
実際の画像に基づいて他の実施例を提供するために、図６は、実施例の画像６００および画像６００の１画像ブロック６０２を示す。簡単のため、画像６００は、単一のカラーチャネルを含む。画像ブロック６０２は、画像６００の一部、すなわち、「Ｒ」描写の一の領域の拡大図を表す。
【００６３】
例として、画像ブロック６０２が１２８×１２８の画素の大きさであると仮定する。さらに、図５Ａの８×２のハーフトーンマトリックスが画像ブロック６０２を覆うのに用いられ、そして、オフセットが２、ｍ＝８、ｐ＝１２８、およびｑ＝２であると仮定する。従って、パディングの列の数（ｒ）は、２である。
【００６４】
図７は、再び画像ブロック６０２を、今度は２ピクセルのパディングの列７００が配置して示す。パディングの列７００は、画像ブロック６０２の右側に追加され、１３０×１２８ピクセルのブロックを形成していてもよい。パディングの列７００の画素は画像ブロック６０２の２本の最も右の列から得られることができ、そして、ハーフトーン処理がこれらの画素に適用されてもよい。このように、ハーフトーン処理の後、パディングの列７００の画素は、それらが抽出された画素に類似しなくなる可能性がある。
【００６５】
加えて、図７は、画像ブロック６０２を少し拡大し、ハーフトーン処理が施された画像ブロック７０２を含む。同様に、列７０４は、列７００を少し拡大し、ハーフトーン処理されている。適当な距離から見られると、画像ブロック７０２は、画像ブロック６０２に濃淡としては近い。この効果は、画像ブロック６０２に適切なハーフトーンマトリックスを適用することによって得られる。
【００６６】
図８のハーフトーン処理が施された画素８００は、ハーフトーン処理が適用された後における画像ブロック６０２の右上角の画素を表す。このように、ハーフトーン処理が施された画素８００は、画像ブロック７０２の一部を表していてもよい。ハーフトーン処理された画素８００においては、１６進数の表記法で、個々のハーフトーン処理された画素が、０からＦの値を呈していてもよい。０は最も明るいハーフトーン処理された画素（例えば、白い）を表し、Ｆが最も暗いハーフトーン処理された画素（例えば、黒）を表していてもよい。０とＦとの間におけるハーフトーンの画素値は、ハーフトーン画素値が１の淡い灰色から始まり、その大きさが増加するにつれて、次第により暗くなるグレーの濃淡を表していていもよい。
【００６７】
画像ブロック６０２の右上角は同一調の色であるので、ハーフトーン処理された画素８００の値は、画像ブロック７０２の右上角に現れる斜めのパターンを反映する。これにより、ハーフトーン処理がどのように特定の色合いを表すのに用いることができるかについて、説明される。
【００６８】
画像ブロックのハーフトーン処理された画素において、これらの画素は複数のセグメントに配列されてもよい。この配置を実行する１つの可能な方法が、図９に示される。図９においては、画像ブロックに適用されるハーフトーンマトリックスは、幅８セルおよび高さ２セルであると仮定される。それにもかかわらず、ハーフトーンマトリックスの他のサイズが、使われてもよい。例えば、他の実施例においては、幅がｍセルで高さがｎセルのｍ×ｎ画素のハーフトーンマトリクスを使用することができる。これらのセグメントは、パディング列内の画素を含んでいてもよい。
【００６９】
具体的に、図９は、セグメント９００Ａ、９０２Ａ、９０４Ａおよび９０６Ａに配列されたハーフトーン処理された画素８００の上部の２列を示す。各セグメントは、ハーフトーンマトリックスのサイズ、すなわち、幅８ピクセル、高さ２ピクセルのサイズである。しかしながら、概して、ｍ×ｎセルのハーフトーンマトリックスが用いられる場合、ｍ×ｎ画素のセグメントがそれに応じて用いられてもよい。
【００７０】
図９は、各セグメントの２ウェイのインターリービング（２−ｗａｙ  ｉｎｔｅｒｌｅａｖｉｎｇ）も示す。例えば、セグメント９００Ａにおいて、上部の複数の画素は、そのセグメントの下部の画素を用いて、１つずつインターリービングされる（交互に配置される）。この結果は、インターリービングが施されたセグメント９００Ｂであってもよく、そしてそれは幅１６ピクセルおよび高さ１ピクセルである。同じように、セグメント９０２Ａはインターリービングされたセグメント９０２Ｂを形成するためにインターリービングが施され、セグメント９０４Ａは、インターリービングされたセグメント９０４Ｂを形成するためにインターリービングが施され、そして、セグメント９０６Ａは、インターリービングが施されたセグメント９０６Ｂを形成するためにインターリービングが施されてもよい。一般に、セグメントの高さがｎピクセルである場合、ｎ箇所のインターリービングが施されることができる。かくして、明確化のため、これらのインターリービングが施されたセグメントは、ｍｎ×１のハーフトーンセグメントと称されてもよい。
【００７１】
インターリービングが施されたセグメント９００Ｂ、９０２Ｂ、９０４Ｂ、および９０６Ｂが形成されると、これらのセグメントは、図９に示される順番、すなわち、インターリービングされた最も左のセグメントは、インターリービングされた最も左から２番目のセグメントに続くというように配置されてもよい。これらのインターリービングが施されたセグメントは、その特定の順番で、更なる処理のためにこれらのセグメントを格納するように調整される１つ以上のバッファに、提供されてもよい。このように、以下の説明においては、「セグメント」は、インターリービングが施されたセグメントであると仮定する。更に、これらのセグメントのシーケンスは、バッファの「入力ストリーム」と称されてもよい。
【００７２】
図１０は、１２のセグメントの履歴バッファ（ヒストリバッファ（ｈｉｓｔｏｒｙ  ｂｕｆｆｅｒ））１００２（ＨＢ＿１０〜ＨＢ＿１１のエントリ）と、４つのセグメントの先取りバッファ（ルックアヘッドバッファ（Ｌｏｏｋａｈｅａｄ  ｂｕｆｆｅｒ））１００４（ＬＢ＿０〜ＬＢ＿３のエントリ）および「新しい」バッファ（ニューバッファ（ｎｅｗ  ｂｕｆｆｅｒ））１００６を含む、バッファーにおける配列１０００を示す。そのセグメントにおいては、一端のヒストリバッファ１００２（例えば、ＨＢ＿１１）が、他端のヒストリバッファ１００２（例えば、ＨＢ＿０）に広がるように順番に挿入されるという点で、ヒストリバッファ１００２は、ＦＩＦＯバッファであってもよい。データフローの一般的な方向は、図１０に示されるように、一番下から上部の方向である。すなわち、セグメントは、ニューバッファ１００６にまず配置され、ルックアヘッドバッファ１００４に、そして、ヒストリバッファ１００２に配置されてもよい。
【００７３】
便宜のため、ヒストリバッファ１００２は「ＦＩＦＯバッファ」と称され、ｋのエントリから構成されていてもよく、そして、ルックアヘッドバッファ１００４は、ｋのエントリから構成されていてもよい。ニューバッファ１００６は、図１０に示されるように、単一またはより多くのエントリから構成されていてもよい。従って、バッファアレンジメント１０００の個々のバッファは、それぞれ、任意の数のエントリを含むことができ、そして、図１０に示される具体的な配置は、例示の目的のために示されいてるということを理解されたい。例えば、いくつかの実施態様においては、ニューバッファ１００６のエントリは、ルックアヘッドバッファ１００４の一部であると処理されてもよい。
【００７４】
一般に、ハーフトーンセグメントは、ヒストリバッファ１００２においてマッチングするセグメントを見出すことによって、圧縮されることができる。具体的に、それぞれのシーケンスのうちで最長のマッチングを決定するために、ルックアヘッドバッファ１００４のセグメントの現在のシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと比較されてもよい。ルックアヘッドバッファ１００４に含まれるセグメントは、ＨＢ＿９、ＨＢ＿１０またはＨＢ＿１１から始めるマッチングを考がえるときに、ヒストリバッファ１００２の一部であるとみなされてもよい。
【００７５】
図１１は、圧縮後のハーフトーンセグメントを表すために用いることができるいくつかの異なるフォーマットを表す。図１１は、図１０のバッファ配列１０００、すなわち、６４ビットのセグメント、ヒストリバッファの１２のエントリ、ルックアヘッドバッファの４つのエントリ、およびニューバッファの１つのエントリに基づく。それにもかかわらず、他のバッファ配列が、図１１のフォーマットを調整することによって、サポートされてもよい。図示の目的で、フォーマット１１００、１１０２および１１０４のサイズは、一定の比率で示されていない。
【００７６】
フォーマット１１００は、セグメントの文字通りの符号化を表していてもよく、特定のセグメントがバッファ配列１０００の情報に基づいて圧縮することができないときに使われることができる。従って、フォーマット１１００は、文字通りのコードワード（リテラルコードワード（ｌｉｔｅｒａｌ  ｃｏｄｅ  ｗｏｒｄ））から開始され、そして、それは１に設定される単一のビットであってもよい。リテラルコードワードは、次のフィールドが圧縮されていないセグメントを含んでいることを示すことができる。具体的に、この次のフィールドは、６４ビットであってもよく、圧縮されることができないセグメントのコピーであってもよい。
【００７７】
フォーマット１１０２は、リピートフォーマットまたはショートリピートフォーマットと称されてもよい。フォーマット１１０２はリピートコードワードから開始され、そして、そのコードワードは０に設定される単一のビットであってもよい。このフィールドには、４ビットのリピート位置フィールドと、２ビットのリピート長フィールドが続いてもよい。リピート位置フィールドは、ヒストリバッファにおけるリピートするセグメントが開始する位置を示していてもよい。リピート長フィールドは、その位置から始まっている繰り返されたセグメントの数を示すことができる。リピート長フィールドのビットを効率的に利用するために、このフィールドは、繰り返されたセグメントの数から１を差し引いた数を含むことができる。リピート長フィールドが「００」を含む場合、リピート長が「１」であることを表す。リピート長フィールドが「０１」を含む場合、リピート長が２であることを表す、等である。
【００７８】
フォーマット１１０４は、拡張リピートフォーマットまたはロングリピートフォーマットと呼ばれてもよい。フォーマット１１０４は、拡張リピートコードワードから開始されてもよく、それは３ビットで１にセットされてもよい。このフィールドの後に、ＨＢ＿１１のセグメントがルックアヘッドバッファ１００４、ニューバッファ１００６、および／または入力ストリームにおいて繰り返される回数、を示す５ビットのリピート長フィールドが続いてもよい。リピート長フィールドのビットを効率的に利用をするために、このフィールドは、繰り返されたセグメントの数から５を差し引いた数を含むことができる。したがって、リピート長フィールドが「０００００」の値を含む場合、繰り返し長さが５であることを表す。リピート長フィールドが「００００１」の値を含む場合、繰り返し長さが６であることを表していてもよい、等である。
【００７９】
図１２は、ある特定のシナリオにおいて、図１１のフォーマットのいずれを使用するべきかについて決定するために実行される全プロセスのフローチャートである。上記の如く、ステップ１２００において、セグメントのそれぞれのシーケンスの間において最長のマッチングを決定するために、ルックアヘッドバッファ１００４のセグメントの現在のシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと比較されてもよい。ニューバッファ１００６は、入力ストリームから読み込まれる次のセグメントを含んでいてもよい。
【００８０】
ステップ１２０２において、マッチングが見つからなかったことを示す、マッチング長がゼロであるかどうかが決定される。マッチング長がゼロである場合、以降、ステップ１２０４で、以下の処理がとられてもよい：（１）ＬＢ＿０のセグメントを、フォーマット１１００にコード化して出力する、（２）ヒストリバッファからエントリＨＢ＿０の以前のセグメントを落とし、１つのセグメントをヒストリバッファにシフトする、（３）エントリＬＢ＿０のセグメントをエントリＨＢ１１に移す、そして、（４）ＬＢ＿３に新しいセグメントをシフトする。
【００８１】
マッチング長がゼロでない場合、とられる措置はマッチングの長さに依存していてもよい。ステップ１２０６で、以下の条件が真かどうかが決定される：マッチングは、ＨＢ＿１１から始まっており、長さは５でる（全てのルックアヘッドバッファのセグメントは同じであり、ＨＢ＿１１のセグメントに等しく、そして、ニューバッファ１００６のセグメントもＨＢ＿１１の値にマッチする）。
【００８２】
条件が真である場合、それから、ステップ１２０８で、以下の措置がとられることができる：（１）拡張カウント値を５にセットする、（２）拡張カウント値が３６未満で、ニューバッファ１００６のセグメントがＨＢ＿１１のセグメントにマッチする限り、ニューバッファ１００６のセグメントを捨て、拡張カウント値をインクリメントする、（３）フォーマット１１０４を用いて、リピート長フィールドにエンコードされた拡張長さの最終値と共に拡張リピートコードを出力する、（４）ヒストリバッファ１００２を更新することなく、ルックアヘッドバッファ１００４の全４値を破棄する、そして、（５）入力ストリームからの次のセグメントを有するルックアヘッドバッファ１００４をリロードする。
【００８３】
条件が真でない場合、ステップ１２１０において、以下の措置がとられてもよい：（１）マッチするヒストリバッファの位置と、コード化されたマッチする長さと共に、フォーマット１１０２を出力する、（２）マッチしている長さの分、実行ウインドウをシフトする、そして、（３）入力データストリームからの次のセグメントを有するルックアヘッドバッファ１００６をリロードする。同じゼロ以外の最適なのマッチング長を有する複数のマッチングが存在する場合、最も低いヒストリバッファ１００２のインデックスで始まるマッチングが用いられてもよい。
【００８４】
なお、伸張モジュール（ｄｅｃｏｍｐｒｅｓｓｏｒ  ｍｏｄｕｌｅ）が圧縮モジュール（ｃｏｍｐｒｅｓｓｏｒ  ｍｏｄｕｌｅ）と同じヒストリバッファの初期値から始め、同じルールを使用している実行ウインドウを維持してもよい。加えて、もし圧縮される画像が、セグメントサイズの整数倍でない場合、入力ストリームが使い果たされているときは、最後のセグメントには０ビットが記入されてもよい。
【００８５】
ハーフトーンの画像または画像ブロックが圧縮されることができる様々な方法のいくつかをさらに説明するために、図１０のバッファ、図１１のフォーマットおよび図１２の方法がこの種の圧縮を容易にするためにどのように操作されることができるかという実施例を、図１３―１８により提供する。
【００８６】
図１３は、入力ストリームからのセグメントがどのようにニューバッファ１００６およびルックアヘッドバッファ１００４に加えられることができるかについて示す。初期化において、ヒストリバッファ１００２は、エントリＨＢ＿０からエントリＨＢ＿１０に対して全て「Ｆ」値（すなわち、二進数の１１１１）およびエントリＨＢ＿１１に対して全て「０」値（すなわち、二進数の００００）をロードされてもよい。ルックアヘッドバッファ１００４には、入力ストリームから最初の４つのセグメントをロードすることができる。
【００８７】
図１３に示されるシナリオにおいては、マッチングが見出されない。従って、フォーマット１１００の出力が、出力セグメントは圧縮されていないことを示すリテラルコードワードおよび出力セグメントのコピー（例えば、ＬＢ＿０「０００００Ｆ９Ｆ０００００Ｆ９」で表される６４ビット）のコピーを含んで生成される。このように、このセグメントの出力は、合計６５ビットとなる。
【００８８】
加えて、ヒストリバッファ１００２のセグメントが１つのエントリだけ上側にシフトされ、それはエントリＨＢ＿０のセグメントを破棄することを含む。出力セグメントは、エントリＨＢ＿１１に書かれてもよい。
【００８９】
図１４は、ルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメント間に２つのマッチングが見出される例示のシナリオを示す。図１４の例示のシナリオは、ほぼ、
図１３の例示のシナリオが捨てられたところから続く。このように、ルックアヘッドバッファ１００４のセグメントは１つのエントリによって上にシフトされ、ニューバッファ１００６のセグメントはＬＢ＿３にシフトされ、そして、入力ストリームからの次のセグメントはニューバッファ１００６に置かれる。
【００９０】
それらのバッファ内のセグメントのそれぞれのシーケンスの間において最長のマッチングを決定するために、ルックアヘッドバッファ１００４のセグメントのシーケンスは、ヒストリバッファ１００２のセグメントのシーケンスと再び比較されてもよい。今回、ＬＢ＿０およびＬＢ＿１のセグメントは、２つのセグメントのマッチングについて、セグメントＨＢ＿１１およびＬＢ＿０にマッチングする（上記の如く、マッチングを捜すときには、ルックアヘッドバッファ１００４の内容はヒストリバッファ１００２の一部であるとみなされることができる）。
【００９１】
２つのセグメントのマッチがあると決定することに応答して、フォーマット１１０２の出力が生成されてもよい。この出力は、０（バイナリの）のリピートコードワードと、マッチングがＨＢ＿１１、すなわち、１１番目のバッファエントリ、から始まることを示す、１０１１（バイナリの）のリピート位置、およびＨＢ＿１１のセグメントが２回繰り返されることを示している０１（バイナリ）のリピート長さを、含むことができる（上記の如く、効率化のために、リピート長コードは１が差し引かれた繰り返し長さを示していてもよい。）。このように、２つの６４ビットのセグメントの代わりに、１つの７ビットの値が使われることができる。
【００９２】
加えて、ヒストリバッファ１００２のセグメントは２つのエントリだけ上にシフトされることができ、そして、それによりエントリＨＢ＿０およびＨＢ＿１のセグメントを破棄することを含んでいてもよい。更に、ルックアヘッドバッファのセグメントは２つのエントリだけ上にシフトされることができ、そして、それはエントリＨＢ＿１０およびＨＢ＿１１へシフトされるエントリＬＢ＿０およびＬＢ＿１のセグメントを含むことができる。加えて、ニューバッファ１００６のセグメントはエントリＬＢ＿２にシフトされることができ、そして、それぞれ、入力ストリームからの次の２つのセグメントが、エントリＬＢ＿３およびニューバッファ１００６に格納されることができる。
【００９３】
図１５は、図１４の実施例のシナリオが破棄されたところからほぼ続く他のシナリオを表す。もう一度、ルックアヘッドバッファ１００４のセグメントのシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと比較され、それらのバッファのセグメントのそれぞれのシーケンスの間における最長のマッチングを決定する。このシナリオにおいては、図１３のシナリオの様に、マッチングは、見つからない（ゼロ長マッチング（ｚｅｒｏ―ｌｅｎｇｔｈ  ｍａｔｃｈ）。
【００９４】
従って、フォーマット１１００の出力が生成される。この出力は、出力セグメントが圧縮されていない（１バイナリ）ことを示すリテラルコードワードおよび出力セグメントのコピー（例えば、ＬＢ＿０のセグメント、「ＦＡＥ００ＦＦＦＦＡＥ００ＦＦＦ」によって表される６４ビット）を含んでいてもよい。このように、合計６５ビットが、このセグメントのために出力される。加えて、ヒストリバッファ１００２のセグメントは１つのエントリだけ上側にシフトされ、そして、それにより、エントリＨＢ＿０のセグメントを捨てることになる。出力セグメントは、エントリＨＢ＿１１に書かれることもできる。
【００９５】
図１６は、ルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメントの間に１のセグメントのマッチングが見出される実施例のシナリオを示す。図１６の実施例のシナリオは、図１５の実施例シナリオが捨てられたところからほぼ続く。
【００９６】
ルックアヘッドバッファ１００４のセグメントのシーケンスは、ヒストリバッファ１００２のセグメントのシーケンスと再び比較され、それらのバッファのセグメントのそれぞれのシーケンスの間における最長のマッチングを決定してもよい。今回、最長のマッチングは、エントリＬＢ＿０のセグメントとエントリＨＢ＿１１のセグメントとの間にある。
【００９７】
１つのセグメントのマッチングがあると決定することに応じて、フォーマット１１０２の出力が生成されてもよい。この出力は、リピートコードワード（０バイナリ）、ＨＢ＿１１、すなわち、１１番目のバッファエントリにおいてマッチングが始まることを示すリピート位置の１０１１（バイナリ）、およびマッチングが１つのセグメントの長さであることを示す（再び、リピート長は１を差し引いた実際の繰り返し長を意味していてもよい。）００（バイナリ）のリピート長さを含んでいてもよい。このように、６４ビットのセグメントの代わりに、１つの７ビット値が使われることができる。
【００９８】
加えて、ヒストリバッファ１００２のセグメントは１つのエントリ分、上側にシフトされてもよく、そして、それによりエントリＨＢ＿０のセグメントが破棄されてもよい。更に、ルックアヘッドバッファのセグメントが１つのエントリ分、上にシフトされてもよく、そして、それにより、エントリＬＢ＿０のセグメントをエントリＨＢ＿１１へシフトされてもよい。ニューバッファ１００６のセグメントはルックアヘッドバッファ１００４のエントリＬＢ＿３にシフトされることができ、そして、それぞれ、入力ストリームからの次のセグメントが、ニューバッファ１００６に格納されてもよい。
【００９９】
図１７は、ルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメントの間に、３つのセグメントのマッチングが見出される実施例のシナリオを示す。ルックアヘッドバッファ１００４のセグメントのシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと再び比較され、それらのバッファのセグメントのそれぞれのシーケンスの間における最長のマッチングを決定してもよい。今回、最長のマッチングは、エントリＬＢ＿０、ＬＢ＿１およびＬＢ＿２の部分と、エントリＨＢ＿４、ＨＢ＿５およびＨＢ＿６のセグメントとの間にある。図１７において楕円で囲まれる値は、パディングの列の値を表す。
【０１００】
３つのセグメントのマッチングがあると決定することに応答して、フォーマット１１０２の出力が生成されることができる。この出力は、リピートコードワード（０バイナリ）と、ＨＢ＿４、すなわち、ヒストリバッファ１００２の４番目のエントリにおいてマッチングが始まることを示す、リピート位置の０１００（バイナリ）、およびマッチングが３セグメント続くことを示すリピート長さの０バイナリを含んでいてもよい。このように、３つの６４ビットのセグメントの代わりに、１つの７ビットの値が使われることができる。
【０１０１】
加えて、ヒストリバッファ１００２のセグメントが、３つのエントリ分、上側にシフトされることができ、そして、それにより、エントリＨＢ＿０、ＨＢ＿１およびＨＢ＿２のセグメントが破棄されてもよい。更に、ルックアヘッドバッファのセグメントは３つのエントリ分、上側にシフトされることもでき、そして、それにより、エントリＨＢ＿９、ＨＢ＿１０およびＨＢ＿１１へ、エントリＬＢ＿０、ＬＢ＿１およびＬＢ＿２のセグメントがシフトされることができる。ニューバッファ１００６のセグメントはエントリＬＢ＿１にシフトされることができ、そして、それぞれ、入力ストリームからの次の３つのセグメントが、ＬＢ＿２、ＬＢ＿３およびニューバッファ１００６に格納されることができる。
【０１０２】
図１８は、５つのセグメントのマッチングがルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメントの間に見出される実施例のシナリオを示す。このシナリオは、エントリＨＢ＿１１のセグメントがルックアヘッドバッファ１００４およびニューバッファ１００６のエントリの全てにマッチングするとう、「拡張リピート」の実施例である。このように、最長のマッチングは、エントリＨＢ１１、ＬＢ＿０、ＬＢ＿１、ＬＢ＿２およびＬＢ＿３のセグメントとエントリＬＢ＿０、ＬＢ＿１、ＬＢ＿２、ＬＢ＿３およびニューバッファ１００６のセグメントの間にある。
【０１０３】
５つのセグメントの拡張リピートマッチングがあると決定することに応じて、フォーマット１１０４を使用する出力が生成されることができる。この出力は、拡張リピートコードワードの１１１（バイナリ）、マッチングが５つのセグメントにおいて続くことを示すリピート長０００００（バイナリ）を含んでいてもよい（拡張リピートコードワードについて、リピート長コードが、５を差し引いた繰り返し長さを意味していてもよい）。このように、５つの６４ビットのセグメントの代わりに、１つの８ビットの値が使われることができる。リピートがさらなるセグメントにわたって続くシナリオにおいては、入力ストリームが読み込まれ続け、そして、繰り返し長さがそれに応じてインクリメントされてもよい。
【０１０４】
図１９Ａ、１９Ｂ、１９Ｃおよび１９Ｄは、上記の列のパディングのメカニズムの可能な利点の更なる例を提供する。図１９Ａは、例示の８×２のハーフトーンマトリックスに覆われた実施例の画像ブロック１９００を表す。特に、ハーフトーン処理の後、位置１９０２から始まり３つのハーフトーンマトリックスに合わせられる複数の画素と、位置１９０４から始まり３つのハーフトーンマトリックスに合わせられる複数の画素は同一である。
【０１０５】
図１９Ｂは、交互の配置（インターリービング）の後の図１９Ａのハーフトーンマトリックスを含むバッファ配列１９０６を表す。図１９Ｂで分かるように、位置１９０２から始まる３つのハーフトーンマトリックスに合わせられる画素群と位置１９０４から始まる３つのハーフトーンマトリックスに合わせられる画素群が同一である場合であっても、それらはバッファ配列１９０６において互いにオフセットされている。従って、マッチングが、ルックアヘッドバッファおよびヒストリバッファのエントリの間にはない。
【０１０６】
図１９Ｃは、８×２のハーフトーンマトリックスで覆われた実施例の画像ブロック１９０８を表す。実施例の画像ブロック１９０８は、実施例の画像ブロック１９００と、２本のパディング列１９１０が右側に適用されている点以外、類似している。パディング列１９１０を入れることによってなされる変化以外、位置１９０４から始まる３つのハーフトーンマトリックスに合わせられる画素群と、位置１９０２から始まる３つのハーフトーンマトリックスに合わせられる画素群とは同一である。
【０１０７】
図１９Ｄは、交互配置（インターリービング）の後の、図１９Ｃのハーフトーンマトリックスを含むバッファ配列１９１２を表す。パディング列の最初の２画素１９１４（一番上のパディングピクセル）は楕円で囲われており、パディング列の２番目の２画素１９１６（一番上から２番目のパディングピクセル）についても同様に囲われている。図１９Ｄで分かるように、パディング列の挿入により、ヒストリバッファとルックアヘッドバッファとの間に３つのマッチングがある。具体的には、エントリＨＢ＿５、ＨＢ＿６およびＨＢ＿７は、エントリＬＢ＿０、ＬＢ＿１およびＬＢ＿２にマッチングする。このようにして、パディング列は、ハーフトーンの画像のより効果的な圧縮という結果を得ることができる。
５．例示の実施形態の動作
図２０は、例示の実施形態のフローチャートである。このフローチャートで例示されるステップは、印刷装置１００のような１つ以上の印刷装置、および／またはコンピュータ３００のようなコンピュータによって実行されることができる。個々のステップの態様は、単一のデバイスによって実行されることができ、あるいは複数のコンピュータに配布されることができる。図２０の例示の実施形態は、本明細書および／または添付の図面の全体にわたって開示される任意の１または複数の特徴を含んでいてもよい。
【０１０８】
ステップ２０００において、ｍ×ｎのハーフトーンマトリックスおよび画像の第１のｍ×ｎ画素ブロック（ピクセルブロック）に基づいて、第１のｍ×ｎ画素ブロックの第１のｍ×ｎハーフトーン処理された画素ブロックが決定されてもよい。この決定は、ハーフトーンマトリックスの垂直方向に隣接するタイルの開始位置がｑ画素分オフセットするように、画像の上にｍ×ｎハーフトーンマトリックスをタイリングする工程を含んでいてもよい。加えて、ｒ１×ｎのパディング画素列が、画像の最も右の列に追加されてもよい。いくつかの実施形態においては、ｐは、ｒ１×ｎのパディング画素列を追加する前における、画像の画素で現される幅であってもよく、ｒは、ｍ−（ｐ―ｑ）ｍｏｄ  ｍであってもよい。
【０１０９】
ステップ２００２においては、ｎ回のインターリーブが、第１のｍ×ｎの画素ブロックについての第１のｍ×ｎのハーフトーン処理された画素ブロックの複数の行に対して実行され、第１のｍｎ×１のハーフトーンセグメントが生成されてもよい。
【０１１０】
ステップ２００４においては、第１のｍｎ×１のハーフトーンセグメントが、ファースト−イン−ファースト−アウトバッファ（ＦＩＦＯバッファ）内の１つ以上のセグメントと比較――されてもよい。この比較は、第１のｍｎ×１のハーフトーンセグメントおよび隣接して第のｍｎ×１のハーフトーンセグメントに続く他の任意のハーフトーンセグメントにもマッチングするＦＩＦＯバッファ内のハーフトーンセグメントの最も長く連続する範囲を決定する工程を含んでいてもよい。
【０１１１】
ステップ２００６においては、第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の任意のハーフトーンセグメントにマッチングするかどうかが、決定されてもよい。第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、ステップ２００８においては、リピートコードワードおよびリピート値が出力されてもよく、そして、第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現が、ＦＩＦＯバッファに書き込まれてもよい。いくつかの実施形態においては、この特定ハーフトーンセグメントが、ＦＩＦＯバッファ内における位置を示すリピート位置が出力に含まれていてもよい。
【０１１２】
第１のｍｎ×１のハーフトーンセグメントが、ＦＩＦＯバッファ内のいずれのハーフトーンセグメントにもマッチングを見出せない場合には、ステップ２０１０において、リテラルコードワードおよび最初のｍｎ×１のハーフトーンセグメントの表現が出力されてもよく、そして、第１のｍｎ×１のハーフトーンセグメントの表現が、ＦＩＦＯバッファに書き込まれてもよい。
【０１１３】
いくつかの実施形態においては、第１のｍｎ×１のハーフトーンセグメントが、他のｍｎ×１のハーフトーンセグメントと共に、１つ以上のルックアヘッドバッファに格納されてもよい。加えて、ＦＩＦＯバッファ内の他のｍｎ×１のハーフトーンセグメントに、特定のハーフトーン部分にマッチするものがあってもよい。ハーフトーンセグメントにｊのマッチングがある場合には、ルックアヘッドバッファにおいて隣接していてもよく、および／または、リピート値がｊを表していてもよい。第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現をＦＩＦＯバッファに書き込むことは、ＦＩＦＯバッファに第１のｍｎ×１のハーフトーンセグメントのｊの表現を書き込む工程を含んでいてもよい。更に、他のｍｎ×１のハーフトーンセグメントが、画像の他のｍ×ｎ画素ブロックから得られることができる。いくつかの実施態様においては、ｊのマッチングするハーフトーンセグメントが、ルックアヘッドバッファから削除されてもよい。
【０１１４】
加えて、リピートコードワードは、ショートリピートコードワードまたは拡張リピートコードワードであってもよい。いずれにせよ、ｊは、ｋと比較されることができる。ｊ＜ｋである場合、リピートコードワードとしてショートリピートコードワードが用いられ、ｊ≧ｋである場合、リピートコードワードとして拡張リピートコードワードが使われることができる。拡張リピートコードワードがリピートコードワードである場合、ＦＩＦＯバッファに第１のｍｎ×１のハーフトーンセグメントのｊの表現を書き込んだ後、ルックアヘッドバッファの少なくとも１つのエントリが、第２のｍｎ×１のハーフトーンセグメントと置き換えられてもよい。第２のｍｎ×１のハーフトーンセグメントは、画像の第２のｍ×ｎ画素ブロックから抽出可能である。
【０１１５】
さらに、ｍ×ｎハーフトーンマトリックスの各セルは、閾値を含んでいてもよい。閾値はｉの画素値の範囲を定めることができ、そして、第１のｍ×ｎ画素ブロックの第１のｍ×ｎハーフトーンバージョンの各セルはｌｏｇ２（ｉ）のビット値を含んでいてもよい。ｍ×ｎの画素ブロックの第１のｍ×ｎのハーフトーンバージョンを決定する工程は、第１のｍ×ｎの画素ブロック内の特定のセルのそれぞれに対して、（ｉ）第１のｍ×ｎ画素ブロックの特定のセルの特定の画素値を決定する工程と、（ｉｉ）ｍ×ｎのハーフトーンマトリックスの特定のセルのｉの画素値の範囲のうちの１つが、特定の画素値を含むか決定する工程であって、第１のｍ×ｎの画素ブロック内の特定のセルは、ｍ×ｎのハーフトーンマトリックスの特定のセルに対応している、工程と、（ｉｉｉ）第１のｍ×ｎ画素ブロックの第１のハーフトーンバージョンの特定のセルに対し、ｉの画素値の範囲のうちの１つを決定することを表すｌｏｇ２（ｉ）のビット値を書き込む工程と、を含んでいてもよい。
６．結論
本発明は、種々の局面を表現することを意図した本願に記載された特定の実施形態の用語に限定されない。当業者に明らかであるように、多くの修正変更が、その趣旨および範囲を逸脱しない範囲でなされることができる。本発明の範囲内の機能的に等価な方法および装置は、本願明細書において列挙されるそれらに加えて、前述の説明から明らかである。この種の修正変更は、添付の請求の範囲内であることを意図する。
【０１１６】
任意のまたは全ての、図示され又は説明された梯子図、シナリオおよびフローチャートに関して、各ブロックおよび／または通信は、例示の実施形態における、情報の処理および／または情報の送受信を表すことができる。別の実施形態は、この種の例示の実施形態の範囲内に含まれることができる。さらに、本願明細書において述べられる任意の梯子図、シナリオおよびフローチャートにおいて、より多くであるか、あるいはより少しのブロックまたは機能が用いられてもよく、そして、部分的に、または、全体で、これらの梯子図、シナリオおよびフローチャートは互いに組み合わされることができる。
【０１１７】
情報の処理を示すステップやブロックは、本願で説明された具体的な方法または技術の論理的特性を実行するように構成されることができる回路に対応することができる。あるいは、または、さらに、情報の処理を表すステップまたはブロックは、モジュール、セグメント、または一部のプログラムコード（関連したデータを含む）に対応することができる。方法または技術の特定の論理的機能または処理を実行するためのプロセッサによって実行可能な１つ以上の指示を、プログラムコードは含むことができる。プログラムコードおよび／または関連したデータは、ディスク駆動装置、ハードディスクまたは他の記憶媒体を含む、記憶装置のような、任意のタイプのコンピュータ読み取り可能な記録媒体に格納されることもできる。
【０１１８】
コンピュータ読み取り可能な記録媒体は、例えばレジスタメモリ、プロセッサキャッシュおよび／またはランダムアクセスメモリ（ＲＡＭ）のような短い期間にデータを格納するコンピュータ読み取り可能な記録媒体のような、非一時的なコンピュータ読み取り可能な記録媒体を含むこともできる。コンピュータ読み取り可能な記録媒体は、例えば、読出し専用メモリ（ＲＯＭ）、光学であるか磁気のディスクおよび／またはＣＤ―ＲＯＭのような、例えば第２であるか持続性の長期記憶媒体のような、より長い期間、プログラムコードおよび／またはデータを格納する非一時的なコンピュータ読み取り可能な記録媒体を含むこともできる。コンピュータ読み取り可能な記録媒体は、他の任意の揮発性、あるいは不揮発性の記憶装置でもあってもよい。コンピュータ読み取り可能な記録媒体は、例えば、コンピュータ読み取り可能な記録媒体および／または有形の記憶装置と考えられることができる。
【０１１９】
様々な態様および実施例が本願明細書において開示されると共に、他の態様および実施例が当業者にとって明らかである。本願明細書において開示されるさまざまな態様および実施形態は、真の範囲および趣旨が以下の請求項によって示される、説明のためのものであって、制限することを目的としない。
【０１２０】
方法は、ｍ×ｎハーフトーンマトリックス、および画像内の第１のｍ×ｎピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの、第１のｍ×ｎのハーフトーン処理されたピクセルブロックを決定する工程と、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたピクセルブロックの複数の行に対してｎ箇所の交互配置工程（ｎ−ｗａｙ  ｉｎｔｅｒｌｅａｖｅ）を行い、第１のｍｎ×１のハーフトーンセグメントを生成する工程と、前記第１のｍｎ×１のハーフトーンセグメントを、ＦＩＦＯ（Ｆｉｒｓｔ  ｉｎ  Ｆｉｒｓｔ  ｏｕｔ）バッファの一つ以上のハーフトーンセグメントと比較する工程と、前記第１のｍｎ×１のハーフトーンセグメントが、ＦＩＦＯバッファのいずれのハーフトーンセグメントにもマッチングしない場合、（ｉ）リテラルコードワードと、前記第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの前記表現を前記ＦＩＦＯバッファに書き込む工程と、前記第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現をＦＩＦＯバッファに書き込む工程と、を含む。
【０１２１】
上記の方法において、前記第１のｍｎ×１のハーフトーンセグメントは、ｋ−１の他のハーフトーンセグメントと共に、ルックアヘッドバッファーに保存されており、ｊ−１≧ｋの他のｍｎ×１のハーフトーンセグメントは、ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングし、前記ｊのマッチングするハーフトーンセグメントは、少なくとも前記ルックアヘッドバッファに隣接しており、前記リピート値はｊの指標であり、前記第１のハーフトーンセグメントの少なくとも１つの前記表現をＦＩＦＯバッファに書き込む工程は、ＦＩＦＯバッファに、ｊの前記第１のｍｎ×１のハーフトーンセグメントを書き込む工程を含む。
【０１２２】
上記の方法において、前記ｋ―１の他のｍｎ×１のハーフトーンセグメントは、前記画像の他のｍ×ｎピクセルブロックから得られる。
【０１２３】
上記の方法は、更に以下を含む：
ルックアヘッドバッファからハーフトーンに部分に合うものを見つけているｊを削除すること。
上記の方法において、前記リピートコードワードはショートリピートコードワードまたは拡張リピートコードワードである。
【０１２４】
上記の方法は、ｊをｋと比較する工程と、ｊ＜ｋである場合、前記リピートコードワードとして、ショートリピートコードワードを用いる工程と、ｊ≧ｋである場合、前記リピートコードワードとして、拡張リピートコードワードを使用する工程と、をさらに含む。
【０１２５】
上記の方法において、前記拡張リピートコードワードは、前記リピートコードワードであり、前記方法は、前記第１のｍｎ×１のハーフトーンセグメントのｊの前記表現を前記ＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを第２のｍｎ×１のハーフトーンセグメントと置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、前記画像の第２のｍ×ｎピクセルブロックから得られる工程をさらに含む。
【０１２６】
上記の方法において、前記第１のｍｎ×１のハーフトーンセグメントを、前記ＦＩＦＯバッファの前記１以上のハーフトーンセグメントと比較する前記工程は、前記第１のｍｎ×１のハーフトーンセグメントにマッチする、ＦＩＦＯバッファ内の最も長く連続するハーフトーンセグメントと、前記第１のｍｎ×１のハーフトーンセグメントに隣接して続いている任意の他のハーフトーンセグメントを決定する工程を含む。
【０１２７】
上記の方法において、前記第１のｍｎ×１のハーフトーンセグメントは、前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングしており、前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントの位置の指標である、リピート位置を出力する工程をさらに含む。
【０１２８】
上記の方法において、前記ｍ×ｎのハーフトーンマトリックスの各セルは、ｉ―１の閾値を含み、前記ｉ―１の閾値は、ｉの画素値の範囲を定義し、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックの各セルは、ｌｏｇ２（ｉ）のビット値を含む。
【０１２９】
上記の方法において、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックを決定する工程は、前記第１のｍ×ｎピクセルブロックの各特定のセルについて、前記第１のｍ×ｎピクセルブロックの前記特定のセルの特定のピクセル値を決定する工程と、前記ｍ×ｎハーフトーンマトリックスの特定のセル内における、ｉの画素値範囲のうちの１つが、前記特定の画素値を含んでいると決定する工程であって、前記第１のｍ×ｎピクセルブロックの前記特定のセルは、前記ｍ×ｎハーフトーンマトリックスの前記特定のセルに対応している、工程と、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックの特定のセルに対し、前記決定された前記ｉの画素値範囲のうちの１つを表すｌｏｇ２（ｉ）ビットの値を書き込む工程と、を含む。
【０１３０】
上記の方法において、前記第１のｍ×ｎのピクセルブロックの前記第１のハーフトーンのピクセルブロックを決定する工程は、前記ｍ×ｎのハーフトーンマトリックスの縦に連続するタイルの初期位置がｑピクセルのオフセットを呈するように、前記画像上に前記ｍ×ｎのハーフトーンマトリックスを割り当てる工程を含み、上記の方法は、前記画像の最も右の列に、ｒ１×ｎのパディング画素列を追加する工程をさらに含む。
【０１３１】
上記の方法において、ｐは、前記ｒ１×ｎのパディング画素列を追加する工程の前における、前記画像の画素値での幅であり、ｒはｍ―（ｐ―ｑ）ｍｏｄ  ｍ  である。
【０１３２】
非一時的なコンピュータ読み取り可能な記録媒体を含む製造物は、コンピュータによる実行において、コンピュータに、ｍ×ｎのハーフトーンマトリックス、および、第１のｍ×ｎのピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程と、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンバージョンの複数の行に対して、ｎ箇所の交互配置工程を施して、第１のｍｎ×１のハーフトーンセグメントを作成する工程と、前記第１のｍｎ×１のハーフトーンセグメントを、ファーストインファーストアウトバッファ（ＦＩＦＯバッファ）内の１以上のハーフトーンセグメントと比較する工程と、前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の任意のハーフトーンセグメントにマッチングしない場合、（ｉ）リテラルコードワードおよび第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの表現を前記ＦＩＦＯバッファに書き込む工程と、前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程と、を含む動作を実行させるプログラム命令を格納する。
【０１３３】
上記の製造物において、前記第１のｍｎ×１のハーフトーンセグメントが、ｋ−１の他のｍｎ×１のハーフトーンセグメントと共にルックアヘッドバッファに格納されており、ｊ−１≧ｋの他のハーフトーンセグメントも、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングし、前記ｊのマッチングするハーフトーンセグメントは、前記ルックアヘッドバッファ内において隣接し、前記リピート値はｊを示し、前記第１のｍｎ×１のハーフトーンセグメントの前記少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程は、前記第１のｍｎ×１のハーフトーンセグメントのｊの表現を前記ＦＩＦＯバッファに書き込む工程を含む。
【０１３４】
上記の製造物において、前記リピートコードワードがショートリピートコードワードまたは拡張リピートコードワードである。
【０１３５】
上記の製造物において、前記動作は、ｊをｋと比較する工程と、ｊ＜ｋである場合に、前記リピートコードワードとして前記ショートリピートコードワードを用い、ｊ≧ｋである場合、前記リピートコードワードとして前記拡張リピートコードワードを用いる工程と、をさらに含む。
【０１３６】
上記の製造物において、前記拡張リピートコードワードは、前記リピートコードワードであり、前記動作は、前記第１のｍｎ×１のハーフトーンセグメントのｊの表現をＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを、第２のｍｎ×１のハーフトーンセグメントに置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、画像の第２のｍ×ｎピクセルブロックから得られる、工程をさらに含む。
【０１３７】
コンピュータは、プロセッサと、データ記憶装置と、前記データ記憶装置に記憶され、プロセッサによる実行において、コンピュータに、請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させる、プログラム命令と、を備える。
【０１３８】
プログラムは、コンピュータによる実行において、コンピュータに請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させる。
【産業上の利用可能性】
【０１３９】
本発明は、半分トーンのデジタル画像の圧縮に適用できてもよい。
【符号の説明】
【０１４０】
１００  印刷装置
１０２  ドキュメントフィーダ／排出トレイ
１０４  給紙カセット
１０６  ユーザインターフェイス
１０８  スキャナー素子
１１０  筐体
２００  コンピュータ
２０２  プロセッサ
２０４  データ格納部
２０６  入力／出力機能
２０８  システムバス
３００  コンピュータ
３０２  スキャン機能
３０４  印刷機能
３０６  スキャン−ホストデータ経路
３０８  ホスト−プリントデータ経路
３１０  スキャン−プリントデータ経路
【図１】
2014087066.tif 000003
【図２】
2014087066.tif 000004
【図３】
2014087066.tif 000005
【図４】
2014087066.tif 000006
【図５Ａ】
2014087066.tif 000007
【図５Ｂ】
2014087066.tif 000008
【図６】
2014087066.tif 000009
【図７】
2014087066.tif 000010
【図８】
2014087066.tif 000011
【図９】
2014087066.tif 000012
【図１０】
2014087066.tif 000013
【図１１】
2014087066.tif 000014
【図１２】
2014087066.tif 000015
【図１３】
2014087066.tif 000016
【図１４】
2014087066.tif 000017
【図１５】
2014087066.tif 000018
【図１６】
2014087066.tif 000019
【図１７】
2014087066.tif 000020
【図１８】
2014087066.tif 000021
【図１９Ａ】
2014087066.tif 000022
【図１９Ｂ】
2014087066.tif 000023
【図１９Ｃ】
2014087066.tif 000024
【図１９Ｄ】
2014087066.tif 000025
【図２０】
2014087066.tif 000026
【外国語明細書】
Title:            Method, Article of Manufacture Including Non-transitory Computer-Readable Medium, Computing Device, and Program
FIELD OF THE INVENTION
[0001]      The present invention relates to method for compression of halftoned digital images. 
Background
[0002]      Halftoning is a technique that simulates continuous-tone imagery through the use of dots that vary in size, shape, or spacing.  These dots, of a single tone level in fundamental binary halftoning, form halftone dot patterns.  The proper design of halftone dot patterns provides, via only on/off marking of a single tone level, the appearance of multiple tones and smooth shadings in halftoned images.  
CITATION LIST
PATENT LITERATURE
[0003]      
US2007/0116367
Summary
TECHNICAL PROBLEM
[0004]      The present invention may provide method formethod for compression of halftoned digital images. 
SOLUTION TO PROBLEM
[0005]      In an example embodiment, based on an m x n halftone matrix and a first m x n pixel block of an image, a first m x n halftone version of the first m x n pixel block may be determined.  An n-way interleave may be performed on rows of the first m x n halftone version of the first m x n pixel block to create a first mn x 1 halftone segment.  The first mn x 1 halftone segment may be compared to one or more halftone segments in a first-in-first-out (FIFO) buffer.  If the first mn x 1 halftone segment does not match any halftone segments in the FIFO buffer, a literal code word and a representation of the first mn x 1 halftone segment may be output, and the representation of the first mn x 1 halftone segment may be written to the FIFO buffer.  If the first mn x 1 halftone segment matches a particular halftone segment in the FIFO buffer, a repeat code word and a repeat value may be output, and at least one representation of the first mn x 1 halftone segment may be written to the FIFO buffer.
[0006]      Additional embodiments may include a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations in accordance with the above or other example embodiments.  
[0007]      Further embodiments may include a computing device comprising at least one processor, data storage, and program instructions in the data storage that, upon execution by the at least one processor, cause the computing device to operate in accordance with the above or other example embodiments.
[0008]      Yet further embodiments may include a program that, upon execution by a computing device, causes the computing device to perform operations in accordance with at least one of the example embodiments above.
[0009]      These as well as other aspects, advantages, and alternatives will become apparent to those of ordinary skill in the art by reading the following detailed description with reference where appropriate to the accompanying drawings.  Further, it should be understood that the description provided in this summary section and elsewhere in this document is intended to illustrate the claimed subject matter by way of example and not by way of limitation.
ADVANTAGEOUS EFFECTS
[0010]      According to the present invention, method for method for compression of halftoned digital images may be provided.
Brief Description of the Drawings
[0011]      Figure 1 depicts a printing device, according to an example embodiment.
[0012]      Figure 2 is a block diagram illustrating computing components of a printing device, according to an example embodiment.
[0013]      Figure 3 is a block diagram illustrating various data paths involving a printing device, according to an example embodiment.
[0014]      Figure 4 depicts application of a halftone matrix to pixels of an image, according to an example embodiment.
[0015]      Figure 5A depicts a halftone matrix tiled over an image, according to an example embodiment.
[0016]      Figure 5B depicts a halftone matrix tiled over an image with column padding, according to an example embodiment.
[0017]      Figure 6 depicts an image and a magnified section of the image, according to an example embodiment.
[0018]      Figure 7 depicts halftoning of an image with column padding, according to an example embodiment.
[0019]      Figure 8 depicts a hexadecimal representation of part of a halftoned version of an image, according to an example embodiment.
[0020]      Figure 9 depicts interleaving a halftoned version of an image, according to an example embodiment.
[0021]      Figure 10 depicts a history buffer, a lookahead buffer, and new segment buffer, according to an example embodiment.
[0022]      Figure 11 depicts formats of halftoned segments after compression, according to an example embodiment.
[0023]      Figure 12 is a flow chart, according to an example embodiment.
[0024]      Figure 13 depicts operation of a history buffer, a lookahead buffer, and new segment buffer in which no match is found for segments of the lookahead buffer, according to an example embodiment.
[0025]      Figure 14 depicts operation of a history buffer, a lookahead buffer, and new segment buffer in which a match is found for two segments of the lookahead buffer, according to an example embodiment.
[0026]      Figure 15 depicts operation of a history buffer, a lookahead buffer, and new segment buffer in which no match is found for segments of the lookahead buffer, according to an example embodiment.
[0027]      Figure 16 depicts operation of a history buffer, a lookahead buffer, and new segment buffer in which a match is found for one segment of the lookahead buffer, according to an example embodiment.
[0028]      Figure 17 depicts operation of a history buffer, a lookahead buffer, and new segment buffer in which a match is found for three segments of the lookahead buffer because column padding was used, according to an example embodiment.
[0029]      Figure 18 depicts operation of a history buffer, a lookahead buffer, and new segment buffer in which a match is found for all segments of the lookahead buffer and the new segment buffer, facilitating use of an extended repeat code word, according to an example embodiment.
[0030]      Figures 19A, 19B, 19C, and 19D depict scenarios in which use of column padding results in more efficient halftoned image compression.
[0031]      Figure 20 is a flow chart, according to an example embodiment.
Detailed Description
[0032]      Example methods and systems are described herein.  Other example embodiments or features may further be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein.  In the following detailed description, reference is made to the accompanying figures, which form a part thereof.   
[0033]      The example embodiments described herein are not meant to be limiting.  It will be readily understood that the aspects of the present invention, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein.
1.    Introduction
[0034]      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.
[0035]      Regardless of whether a printing device is used in a residence, a business, or in another type of location, the printing device may be a shared resource that can be communicatively coupled to various other computing devices.  Consequently, in some environments, the storage requirements of a printing device may be quite high, as numerous computing devices may be transmitting electronic documents to the printing device for printing.  Typically, a printing device will print, copy, fax, and/or scan one electronic document at a time, in a first-come-first-served fashion.  Therefore, the printing device may store a potentially large number of electronic documents that are waiting to be serviced.  Since the cost of data storage (e.g., memory such as random access memory (RAM), solid-state memory, hard-drive memory, and/or flash memory) can be expensive, it may be beneficial to compress the stored electronic documents, in order to reduce the data storage requirements of the printing device.  Additionally, since some electronic documents may be transferred to and/or from the printing device and a computing device, compressing these electronic documents may make transfers faster and use less network capacity.  
[0036]      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  
[0037]      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.”
[0038]      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. 
[0039]      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.  
[0040]      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.
[0041]      Regardless, printing device 100 may be considered to be a computing device, and may carry out both printing-related and non-printing-related tasks.
[0042]      As noted above, printing device 100 may also include copier, fax, and scanner functions.  In some embodiments, printing device 100 may use a scanner function to facilitate copier and/or fax functions.  For instance, printing device 100 may scan a physical document into an electronic format, and then print the resulting electronic document to provide a copy, and/or transmit the resulting electronic document via a telephone interface to provide a fax function.
[0043]      In order to support its various functions, printing device 100 may include a document feeder / output tray 102, paper storage 104, user interface 106, scanning element 108, and chassis 110.  It should be understood that printing devices may take on a wide variety of forms.  Therefore printing device 100 may include more or fewer components than depicted in Figure 1, and/or components arranged in a different fashion than depicted in Figure 1.
[0044]      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 invention.  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.
[0045]      Paper storage 104 may include trays and/or feeding elements for various types of physical media.  For instance, paper storage 104 may include separate trays for 8 1/2 x 11 inch paper, A4 paper, letterhead paper, envelopes, and so on.  For any function of printing device 100 that involves outputting physical media (e.g., printing, copying, and/or receiving a fax), paper storage 104 may supply the physical media.
[0046]      User interface 106 may facilitate the interaction of printing device 100 with a human or non-human user, such as to receive input from a user and to provide output to the user.  Thus, user interface 106 may include input components such as a keypad, keyboard, touch-sensitive or presence-sensitive panel, joystick, microphone, still camera and/or video camera.  User interface 106 may also include one or more output components such as a display screen (which, for example, may be combined with a presence-sensitive panel), a cathode ray tube (CRT), a liquid crystal display (LCD), a light emitting diode (LED) based display, a display using digital light processing (DLP(R)) technology, a light bulb, and/or one or more other similar devices, now known or later developed.  User interface 106 may also be configured to be able to generate audible output(s), via a speaker, speaker jack, audio output port, audio output device, earphones, and/or other similar devices, now known or later developed in the future.
[0047]      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.  
[0048]      Chassis 110 may include a physical housing that contains and or interconnects various components of printing device 100, such as document feeder / output tray 102, paper storage 104, user interface 106, and scanning element 108.  Additionally, chassis 110 may house other components not shown in Figure 1.  For example, chassis 110 may contain one or more toner cartridges, liquid ink jets, belts, rollers, and/or power supplies.  Further, chassis 110 may include communication interfaces, such as a wireline and/or wireless network interfaces, a telephony interface (e.g., a RJ45 jack), a USB interface, a BLUETOOTH(R) interface, a card reader port, etc.
[0049]      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 of computing device components 200 (e.g., functional elements of a computing device) that may be included in printing device 100.  
[0050]      Computing device components 200 may include a processor 202, data storage 204, and input/output function 206, all of which may be coupled by a system bus 208 or a similar mechanism.  Processor 202 may include one or more central processing units (CPUs), such as one or more general purpose processors and/or one or more dedicated processors (e.g., application specific integrated circuits (ASICs) or digital signal processors (DSPs), etc.). 
[0051]      Data storage 204, in turn, may comprise volatile and/or non-volatile data storage and can be integrated in whole or in part with processor 202.  Data storage 204 may store program instructions, executable by processor 202, and data that are manipulated by these instructions to carry out the various methods, processes, or functions described herein.  Alternatively, these methods, processes, or functions can be defined by hardware, firmware, and/or any combination of hardware, firmware and software.  Therefore, data storage 204 may include a tangible, non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by one or more processors, cause printing device 100 to carry out any of the methods, processes, or functions disclosed in this specification or the accompanying drawings.  
[0052]      Input/output function 206 may include any of the functions and/or elements described in reference to user interface 106.  Thus, input/output function 206 may serve to configure and/or control the operation of processor 202.  Input/output function 206 may also provide output based on the operations performed by processor 202.
[0053]      It should be understood that these examples of a printing device are provided for illustrative purposes.  Further, in addition to and/or alternatively to the examples above, other combinations and/or sub-combinations of printer and computer technologies may also exist, amongst other possibilities, without departing from the scope of the embodiments herein.  
[0054]      Figure 3 depicts some of the possible data paths through which a representation of an electronic document processed by printing device 100 may pass.  In Figure 3 it is assumed that printing device 100 may include a scanning function 302 and a printing function 304.  Each of these functions may be implemented in hardware, firmware, software, or any combination of hardware, firmware and/or software.    Additionally, each of scanning function 302 and printing function 304 may communicate with computing device 300, and possibly with other computing devices as well.  In some situations, the data paths supported by printing device 100 may be referred to a “pipelines.”
[0055]      A scan-to-print data path 310 may be supported by scanning function 302 and printing function 304.  Scan-to-print data path 310 may be used, e.g., when a user instructs printing device 100 to copy a physical document.  In response to this instruction, scanning function 302 may scan the physical document into an electronic document, and transmit the electronic document via scan-to-print data path 310 to printing function 304.  Use of scan-to-print data path 310 may involve at least temporarily storing some or all of the electronic document in the data storage of printing device 100.  Then, printing function 304 may print the electronic document to physical media (e.g., one or more sheets of paper).  
[0056]      A scan-to-host data path 306 may also be supported by scanning function 302 and computing device 300.  Scan-to-host data path 306 may be used, e.g., when a user instructs printing device 100 to scan a physical document.  The user may also instruct printing device 100 to transmit a representation of the resulting electronic document to computing device 100, or printing device 100 may be pre-configured to automatically transmit the electronic document to computing device 300.  Thus, in response to this instruction, scanning function 302 may scan the physical document into an electronic document, and transmit the resulting electronic document via scan-to-host data path 306 to computing device 300.  Use of scan-to-print data path 310 may involve at least temporarily storing some or all of the electronic document in the data storage of printing device 100, and transmitting a representation of the resulting electronic document to computing device 300.  
[0057] A host-to-print data path 308 may be supported by computing device 300 and printing function 304.  Host-to-print data path 308 may be used, e.g., when a user instructs computing device 300 to print an electronic document on printing device 100.  In response to this instruction, computing device 300 may transmit a representation of the electronic document to printing function 304.  Printing device 100, via printing function 304, may print the electronic document to physical media.  Some or all of the electronic document may be stored in the data storage of printing device 100 before and/or during the printing of the electronic document.
[0058] 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/or transmission of electronic documents can be improved by compressing these electronic documents.  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.  
[0059] The following sections describe various embodiments that provide compression of electronic documents handled by printing device 100.
3.    Example Image Color Models
[0060] 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, halftone compression may be specific to individual color models or may operate separately on each channel of a color model.
[0061] 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.  
[0062] A particular pixel of an RGB image may be expressed as a three-channel tuple (R,G,B), each channel of which can vary from zero to a pre-defined maximum value (e.g., 255).  If all of the channels are at zero, the result may be black.  If all of the channels are at the maximum value, the result may be the brightest representable white.
[0063] 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.
[0064] 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 as a complement of the RGB color model.
[0065] A particular pixel of a CMY image may be expressed as a three-channel tuple (C,M,Y), each channel of which can vary from zero to a pre-defined maximum value.  If all of the channels are at zero, the result may be white.  If all of the channels are at the maximum value, the result may be black.  
[0066] 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.
[0067] In some embodiments, a four-channel CMYK color model can also be used.  This four-channel model of CMYK may be similar to or the same as the CMY color model, with the exception that a key (black) channel is also used.  In addition to possibly combining cyan, magenta, and yellow to form black, the separate key (black) ink source may be used to form black.  Thus, a particular pixel of a CMYK image may be expressed as a four-channel tuple (C,M,Y,K), each channel of which can vary from zero to a pre-defined maximum value.  
[0068] 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.  
[0069] An additional color model is gray, also referred to as grayscale, which may be used for the representation of black and white images.  Unlike the RGB and CMY/CMYK color models, each pixel of the gray color model is expressed using a single channel that encodes the pixel’s intensity.  The values used by the gray channel can vary from zero for black, to a pre-defined maximum value for white (e.g., 255).  In some embodiments, one or more of the data paths supported by printing device 100 may be able to encode images using the gray color model.
[0070] Another color model is YCbCr.  In some implementations, this color model may be used as an alternative representation of an image.  Particularly, the Y channel may represent the brightness of a pixel, and the Cb and Cr channels may represent the blue-yellow chrominance and red-green chrominance, respectively.  The YCbCr color model has a well-defined relationship with the RGB and CMY colors models and can be converted to and from either of these color models with relative ease.
[0071]      An additional advantage to the YCbCr color model is that compression of images encoded using the YCbCr color model tends to be more efficient than compression of images encoded in the RGB or CMY/CMYK color models.  Particularly, the human eye is not very good at detecting high-frequency (e.g., rapidly varying) chrominance information in an image.  Thus, images encoded using the YCbCr color model can exploit this information by ignoring high-frequency components of the Cb and Cr channels.  Thus, as discussed in more detail below, images encoded in a particular color model may be converted to the YCbCr color model before compression in order to improve compression performance.
4.          Example Image Halftoning
[0072]      Many digital images contain continuous tones, in which a color or grayscale section of the image smoothly transitions from a lighter tone to a darker tone, or vice versa.  However, many printers do not support continuous tones.   Instead, a printer may support a discrete number of tones from the lightest tone to the darkest tone.  For instance, a simple black and white printer may support only outputting either black or white for any given pixel of the image.  
[0073]      Halftoning includes the process of breaking down a continuous tone image into patterns of pixel shading to create the illusion of smoothly transitioning grays or colors.  It should be noted that herein the term “image” may refer to a full image or part of an image, such as an image block.  In some of the examples below, for sake of simplicity, operations may be illustrated on image blocks rather than full images.
[0074]      A halftone matrix may be an m x n block of cells, each cell containing one or more threshold values.  When applying the halftone matrix to an image, the halftone matrix may be tiled over the image, such that each pixel in the image is pairwise associated with a cell in one of the tiled halftone matrices.  The halftone matrix may be defined based on the characteristics of a particular printer, and therefore may be output-device specific.  Halftone matrices may also be referred to as halftone screens, threshold tables, or dither tables.
[0075]      Each pixel from the image may be compared to the threshold value(s) in its associated cell to determine a halftone value for the pixel.  For instance, in a particular color channel, the pixels may take on a value of 0-255, indicative of the intensity or brightness of that pixel.  The associated cell may contain three threshold values, 64, 128, and 240, thus defining four ranges: 0-64, 65-128, 129-240, and 241-255.  The value of the pixel falls into one of these ranges, and the range that the pixel falls in may define the halftone value of the pixel.  Therefore, the halftone value of the pixel may be defined with a 2-bit value.  For example, 00 may indicate the range 0-64, 01 may indicate the range 65-128, 10 may indicate the range 129-240, and 11 may indicate the range 241-255.  
[0076]      More formally, if there are  thresholds defined for each cell in the halftone matrix, then these thresholds may define i ranges, and the range in which a pixel value falls may be represented by a log2(i) -bit value.  Applying the halftone matrix to each pixel in the image may result in a halftone version of the image in which each pixel is represented by the log2(i)-bit value.  This halftone version may then be sent to a printer that supports i tones.  
[0077]      This process is illustrated in Figure 4.  Image pixel matrix 400 contains a number of individual pixels, including example pixels 402 and 404, each taking on an 8-bit value (i.e., 0-255).  Halftone matrix 406 contains a pattern of cells, including example cells 408 and 410, each including representations of 15 threshold values (i.e., indicating 16 ranges, indexed from 0 to 15, within the overall range of 0-255).  
[0078]      Halftone matrix 406 may be overlaid on image pixel matrix 400 such that example cell 408 is associated with example pixel 402, and example cell 410 is associated with example pixel 404.  The value of example pixel 402 may be mapped to a range defined by the thresholds of example cell 408, and the value of example pixel 404 may be mapped to a range defined by the thresholds of example cell 410.  
[0079]      Each example cell may define different thresholds.  For instance, example cell 408 may define thresholds 412, while example cell 410 may define thresholds 414.  Thus, mapping the pixels to these respective thresholds may result in determining that the value of example pixel 402 falls between the fourth and fifth threshold of thresholds 412, and the value of example pixel 404 falls above the fifteenth threshold of thresholds 414.  Thus, the halftone value of example pixel 402 may be represented as 4, while the halftone value of example pixel 404 may be represented as 15.  
[0080]      More generally, suppose that a cell of the halftone matrix defines  thresholds.  If the pixel value is greater than or equal to the highest threshold, the halftone value is highest.  If the pixel value is less than the lowest threshold, the halftone value is 0.  If the pixel value is greater than or equal to the c th threshold but less than the (c+1)th threshold, the halftone value is c.
[0081]      An example halftone matrix overlaying an example image block is depicted in Figure 5A.  Each cell of the halftone matrix is labeled as one of A1…A8 or B1…B8.  Each of these labels indicates potentially different sets of threshold values.  Thus, a cell labeled A1 may have a different set of threshold values than a cell labeled A2, and so on.  
[0082]      The overlay pattern of the halftone matrix is shifted left such that starting positions of vertically contiguous tiles of the halftone matrix are offset by two cells.  For instance, the A1 cell of halftone matrix 502 is two cells further left than the A1 cell of halftone matrix 500.  Similarly, the A1 cell of halftone matrix 504 is two cells further left than the A1 cell of halftone matrix 502.  This offset may result in the halftone pattern produced by a printer having an esthetically appealing angle. 
[0083]      One possible disadvantage of tiling the halftone matrices is when the width of the image is such that a non-integral number of halftone matrices are required to overlay each row of the image.  For instance, in Figure 5A, the image block is 12 x 8 pixels, and the halftone matrix is 8 x 2 cells.  Thus, 1 1/2 halftone matrices are required to span the width of the image block.  
For reasons that will be explained in more detail below, padding the rows of the image block may lead to increased compression efficiency for the halftone version of the image.  Particularly, the image block may be padded with extra columns of pixels so that an integral number of halftone matrices may be overlaid upon each row.  These padding columns may contain copies of the pixels in the rightmost column of the image block.  
[0084]      The number of padding columns may be determined in various ways.  One possible way of determining the number of padding columns, r, is according to the equation:
r = m -(p - q) mod m
where m is the width of the halftone matrix in cells, p is the width of the image block in pixels, and q is the offset.   For Figure 5A, m=8, p=12, and q=2.  Therefore, r=6.
[0085]      Figure 5B depicts the image block of 5A, with 6 columns of padding, and tiled with the halftone matrix.  In addition to the tiled halftone matrices shown in Figure 5B, further halftone matrices may be tiled over the padded image block by wrapping the halftone matrix from the right end of one pair of rows to the left end of the next lower pair of rows.  Thus, a halftone matrix can be laid over the A1…A6 and B1…B6 cells in the upper-right corner and then “wrapped around” to the A7…A8 and B7…B8 cells that are at the left side of the next-lowest two rows.  Therefore, when each pair of rows is read contiguously left to right, the halftone matrix is repeated sequentially.
[0086]      In order to provide another example based on an actual image, Figure 6 depicts an example image 600, and an image block 602 of image 600.  For purposes of simplicity and illustration, image 600 includes a single color channel.  Image block 602 represents an expansion of an area of image 600 - namely, the stylized “R”.  
[0087]      As an example, it may be assumed that image block 602 is 128 x 128 pixels in size.  Further assuming that the 8 x 2 halftone matrix of Figure 5A is used to overlay image block 602, and that the offset is 2, then m=8, p=128, and q=2.  Therefore, the number of padding columns, r, is 2.
[0088]      Figure 7 depicts image block 602 again, this time aligned with a 2-pixel padding column 700.  Padding column 700 may be appended to the right side of image block 602 to form a 130 x 128 pixel block.  The pixels of padding column 700 may be derived from the two rightmost columns of image block 602, and halftoning may be applied to these pixels.  Thus, after halftoning, the pixels of padding column 700 might not resemble the pixels from which they were derived.
[0089]      Additionally, Figure 7 also includes image block 702, a slightly enlarged, halftoned version of image block 602.  Similarly, column 704 is a slightly enlarged, halftoned version of column 700.  When viewed at an appropriate distance, image block 702 approximates the shading of image block 602.  This effect may be achieved by applying an appropriate halftone matrix to image block 602.  
[0090]      Halftoned pixels 800 in Figure 8 depict the pixels of the upper right corner of image block 602 after halftoning is applied.  Thus, halftoned pixels 800 may represent part of image block 702.  In halftoned pixels 800, individual halftoned pixels may take on values from 0 through F, in hexadecimal notation.  A 0 may represent the lightest halftoned pixel (e.g., white) while F may represent the darkest halftoned pixel (e.g., black).  Halftone pixel values between 0 and F may represent shades of gray starting with light gray for a halftone pixel value of 1, and becoming progressively darker as the halftone pixel value increases.  
[0091]      Since the upper right corner of image block 602 is a solid color, the values of halftoned pixels 800 reflect the diagonal pattern evident in the upper right corner of image block 702.  This illustrates how halftoning can be used to represent a particular shade of a color.
[0092]      Given the halftoned pixels of an image block, these pixels can be arranged into segments.  One possible way of making such an arrangement is illustrated in Figure 9.  In Figure 9 it is assumed that the halftone matrix applied to the image block is 8 cells wide and 2 cells high.  Nonetheless, other sizes of halftone matrices may be used.  For example, some embodiments may use m x n pixel halftone matrices that are m cells wide and n cells high.   These segments may include pixels in padding columns.
[0093]      Particularly, Figure 9 shows a portion of the top two rows of halftoned pixels 800 arranged into segments 900A, 902A, 904A, and 906A.  Each segment is the size of the halftone matrix - that is, 8 pixels wide and 2 pixels high, or 8 x 2.  However, in full generality, if an m x n cell halftone matrix is used, m x n pixel segments may be used accordingly.
[0094]      Figure 9 also shows a 2-way interleaving of each segment.  For instance, in segment 900A the top pixels of that segment are interleaved, one-by-one with the bottom pixels of that segment.  The result may be interleaved segment 900B, which is 16 pixels wide and 1 pixel high.  In a similar fashion, segment 902A may be interleaved to form interleaved segment 902B, segment 904A may be interleaved to form interleaved segment 904B, and segment 906A may be interleaved to form interleaved segment 906B.  In general, if the height of a segment is n pixels, then an n-way interleaving may be used.  Thus, for sake of clarity, these interleaved segments may be optionally referred to as mn x 1 halftone segments. 
[0095]      Once they are formed, interleaved segments 900B, 902B, 904B, and 906B may be arranged in the order shown in Figure 9, in which the interleaved leftmost segment is followed by the interleaved second-leftmost segment, and so on.  These interleaved segments may be provided, in that particular order, to one or more buffers arranged to store these segments for further processing.   Thus, references to a “segment” in the following discussion may presume that the segment is an interleaved segment.  Further, the sequence of these segments may be referred to as the “input stream” of the buffers.
[0096]      Figure 10 depicts buffer arrangement 1000, containing a 12-segment history buffer 1002 (entries HB_0 through HB_11) a 4-segment lookahead buffer 1004 (entries LB_0 through LB_3) and a “new” buffer 1006.  History buffer 1002 may be a FIFO buffer, in that segments inserted at one end of history buffer 1002 (e.g., HB_11) may be propagated through to the other end of history buffer 1002 (e.g., HB_0) in their order of insertion.  The general direction of data flow is shown in Figure 10 as from bottom to top; that is, a segment may first be placed in the “new” buffer 1006, moved to lookahead buffer 1004, and then to history buffer 1002.
[0097]      For sake of convenience, history buffer 1002 may be referred to as “the FIFO buffer” and may consist of kentries, while lookahead buffer 1004 may consist of k entries.  “New” buffer 1006 may consist of a single entry as shown in Figure 10, or more entries.  Therefore, it should be appreciated that the individual buffers of buffer arrangement 1000 may each contain any number of entries, and that the specific arrangement shown in Figure 10 is for purpose of example.  For instance, in some implementations, the entry of “new” buffer 1006 may be considered to be part of lookahead buffer 1004.
[0098]      In general, halftone segments may be compressed by finding matching segments in history buffer 1002.  Particularly, the current sequence of segments in lookahead buffer 1004 may be compared with the segment sequences in history buffer 1002 to determine the longest match between the respective sequences of segments that can be made.  The segments included in lookahead buffer 1004 may be considered to be part of history buffer 1002 when considering matches starting with HB_9, HB_10, or HB_11.
[0099]      Figure 11 depicts several different formats that may be used to represent halftone segments after compression.  Figure 11 is based on buffer arrangement 1000 of Figure 10; that is, 64-bit segments, 12 entries in the history buffer, 4 entries in the lookahead buffer, and one entry in the “new” buffer.  Nonetheless, other buffer arrangements may be supported, possibly by adjusting the formats of Figure 11 accordingly.  For purposes of illustration, the sizes of formats 1100, 1102, and 1104 are not shown to scale.
[0100]      Format 1100 may represent a literal encoding of a segment, and may be used when a particular segment cannot be compressed based on information in buffer arrangement 1000.  Therefore, format 1100 may begin with a literal code word, which may be a single bit set to 1.  The literal code word may indicate that the next field includes an uncompressed segment.  Particularly, this next field may be 64 bits and may be a copy of a segment that could not be compressed.
[0101]      Format 1102 may be referred to as a repeat or short repeat format.  Format 1102 may begin with a repeat code word, which may be a single bit set to 0.  This field may be followed by a 4-bit repeat position field, and a 2-bit repeat length field.  The repeat position field may indicate where in the history buffer the repeated segments begin.  The repeat length field may indicate the number of repeated segments starting from that position.  To make efficient use of the bits in the repeat length field, this field may contain the number of repeated segments minus 1.  Thus, if the repeat length field contains a value of “00”, a repeat length of 1 may be represented.  If the repeat length field contains a value of “01”, a repeat length of 2 may be represented, and so on.
[0102]      Format 1104 may be referred to as an extended repeat or long repeat format.  Format 1104 may begin with an extended repeat code word, which may be three bits set to 1.  This field may be followed by a 5-bit repeat length field, indicating the number of times the segment in entry HB_11 is repeated in lookahead buffer 1004, “new” buffer 1006, and/or the input stream.  To make efficient use of the bits in the repeat length field, this field may contain the number of repeated segments minus 5.  Thus, if the repeat length field contains a value of “00000”, a repeat length of 5 may be represented.  If the repeat length field contains a value of “00001”, a repeat length of 6 may be represented, and so on.
[0103]      Figure 12 is a flow chart of the overall process that may be followed to determine which of the formats of Figure 11 to use in a particular scenario.  As noted above, at step 1200, the current sequence of segments in lookahead buffer 1004 may be compared with the segment sequences in history buffer 1002 to determine the longest match between the respective sequences of segments that can be made.  “New” buffer 1006 may contain the next segment that will be read from the input stream.  
[0104]      At step 1202, it is determined whether the match length is zero, indicating that no match has been found.  If the match length is zero, then, at step 1204, the following actions may be taken: (1) output the segment in LB_0, encoded in format 1100, (2) shift the history buffer by one segment, dropping the previous segment in entry HB_0 from the history buffer, (3) move the segment in entry LB_0 into entry HB11, and (4) shift a new segment into LB_3.  
[0105]      If the match length is a non-zero, the actions taken may depend on the length of the match.  At step 1206, it is determined whether to following condition is true: the match starts at HB_11 and has a length of five (all lookahead buffer segments are the same and equal to the segment HB_11, and the segment in “new” buffer 1006 also matches the value in HB_11).  
[0106]      If the condition is true, then, at step 1208, the following actions may be taken: (1) set an extended count value to 5, (2) as long as the extended count value is less than 36 and the segment in “new” buffer 1006 matches the segment at HB_11, discard the segment in “new” buffer 1006 and increment the extended count value, (3) using format 1104, output an extended repeat code with the final extended length encoded in the repeat length field, (4) discard all four values in lookahead buffer 1004 without updating history buffer 1002 , and (5) reload lookahead buffer 1004 with the next segments from the input stream.  
[0107]      If the condition is not true, then, at step 1210, the following actions may be taken: (1) output format 1102 with the matching history buffer 1002 position and matching length encoded, (2) shift the run window by the matching length, and (3) reload lookahead buffer 1006 with the next segments from the input data stream.  If multiple matches with the same non-zero best match length exist, then the match beginning with the lowest history buffer 1002 index number may be used.  
[0108]      Note that the decompressor module may start with the same initial history buffer values and may maintain the run window using the same rules as the compressor module.  Additionally, if the image to be compressed is not an integral multiple of the segment size, the last segment may be filled out with 0 bits when the input stream is exhausted.
[0109]      In order to further illustrate some of the various ways that halftoned images or image blocks can be compressed, Figures 13-18 provide examples of how the buffers of Figure 10, formats of Figure 11, and process of Figure 12 can be operated to facilitate such compression.
[0110]      Figure 13 shows how segments from the input stream may be added to “new” buffer 1006 and lookahead buffer 1004.  Upon initialization, history buffer 1002 may be loaded with all “F” values (i.e., 1111 in binary) for the entries HB_0 through HB_10 and all “0” values (i.e., 0000 in binary) for the entry HB_11.  Lookahead buffer 1004 may be loaded with the first four segments from the input stream.  
[0111]      In the scenario shown in Figure 13, no match can be found.  Accordingly, the output in format 1100 may be generated, including a literal code word indicating that the output segment is uncompressed, and a copy of the output segment (e.g., the 64 bits represented by the segment at LB_0, “00000F9F00000F9”).  Thus, a total of 65 bits may be output for this segment.
[0112]      Additionally, the segments of history buffer 1002 may be shifted up by one entry, which includes discarding the segment in entry HB_0.  The output segment may also be written entry HB_11.  
[0113]      Figure 14 illustrates an example scenario in which a two-segment match is found between segments in lookahead buffer 1004 and history buffer 1002.  The example scenario of Figure 14 continues approximately from where the example scenario of Figure 13 left off.  Thus, the segments of lookahead buffer 1004 have been shifted up by one entry, the segment in “new” buffer 1006 has been shifted into LB_3, and the next segment from the input stream has been placed in “new” buffer 1006.  
[0114]      The sequence of segments in lookahead buffer 1004 again may be compared with the segment sequences in history buffer 1002 to determine the longest match between the respective sequences of segments in those buffers.  This time, the segments of LB_0 and LB_1 match the segments HB_11 and LB_0 for a match of 2 segments (as noted above, when searching for matches, the contents of lookahead buffer 1004 may be considered to be part of history buffer 1002).  
[0115]      In response to determining that there is a match of two segments, output in format 1102 may be generated.  This output may include a repeat code word of 0 (binary), a repeat position of 1011 (binary), indicating that the match begins at HB_11, the 11th buffer entry, and a repeat length of 01 (binary) indicating that the segment at HB_11 is repeated twice (as noted above, for purposes of efficiency, the repeat length codes may denote the repeat length minus 1).   Thus, in place of two 64-bit segments, one 7-bit value may be used.
[0116]      Additionally, the segments in history buffer 1002 may be shifted up by two entries, which may include discarding the segments in entries HB_0 and HB_1.  Further, the segments in lookahead buffer may be shifted up by two entries, which may involve the segments in entries LB_0 and LB_1 being shifted to entries HB_10 and HB_11.  Additionally, the segment in “new” buffer 1006 may be shifted into entry LB_2, and the next two segments from the input stream may be stored in entry LB_3 and “new” buffer 1006, respectively.  
[0117]      Figure 15 depicts another scenario that continues approximately from where the example scenario of Figure 14 left off.  Once more, the sequence of segments in lookahead buffer 1004 may be compared with the segment sequences in history buffer 1002 to determine the longest match between the respective sequences of segments in those buffers. In this scenario, like that of the scenario of Figure 13, no match (a zero-length match) is found. 
[0118]      Accordingly, output in format 1100 may be generated.  This output may include a literal code word indicating that the output segment is uncompressed (1 binary), and a copy of the output segment (e.g., the 64 bits represented by the segment at LB_0, “FAE00FFFFAE00FFF”).  Thus, a total of 65 bits may be output for this segment.  Additionally, the segments of history buffer 1002 may be shifted up by one entry, which includes discarding the segment in entry HB_0.  The output segment may also be written entry HB_11.  
[0119]      Figure 16 illustrates an example scenario in which a one-segment match is found between segments in lookahead buffer 1004 and history buffer 1002.  The example scenario of Figure 16 continues approximately from where the example scenario of Figure 15 left off.  
[0120]      The sequence of segments in lookahead buffer 1004 again may be compared with the segment sequences in history buffer 1002 to determine the longest match between the respective sequences of segments in those buffers.  This time, the longest match is between the segment in entry LB_0 and the segment in entry HB_11.  
[0121]      In response to determining that there is a match of one segment, output in format 1102 may be generated.  This output may include a repeat code word (0 binary), a repeat position of 1011 (binary), indicating that the match begins at HB_11, the 11th buffer entry, and a repeat length of 00 (binary) indicating that the match is one segment long (again, the repeat length may denote the actual repeat length minus 1).   Thus, in place of a 64-bit segment, one 7-bit value may be used.
[0122]      Additionally, the segments in history buffer 1002 may be shifted up by one entry, which may include discarding the segment in entry HB_0.  Further, the segments in lookahead buffer may also be shifted up by one entry, which may involve the segment in entry LB_0 being shifted to entry HB_11.  The segment in “new” buffer 1006 may be shifted into entry LB_3 of lookahead buffer 1004, and the next segments from the input stream may be stored in “new” buffer 1006, respectively.
[0123]      Figure 17 illustrates an example scenario in which a three-segment match is found between segments in lookahead buffer 1004 and history buffer 1002.  The sequence of segments in lookahead buffer 1004 again may be compared with the segment sequences in history buffer 1002 to determine the longest match between the respective sequences of segments in those buffers.  This time, the longest match is between the segments in entries LB_0, LB_1, and LB_2 and the segments in entries HB_4, HB_5, and HB_6.  The values circled in Figure 17 represent values from padding columns.
[0124]      In response to determining that there is a match of three segments, output in format 1102 may be generated.  This output may include a repeat code word (0 binary), a repeat position of 0100 (binary), indicating that the match begins at HB_4, the fourth entry of history buffer 1002, and a repeat length of 10 (binary) indicating that the match continues for three segments.   Thus, in place of three 64-bit segments, one 7-bit value may be used.
[0125]      Additionally, the segments in history buffer 1002 may be shifted up by three entries, which may include discarding the segments in entries HB_0, HB_1, and HB_2.  Further, the segments in lookahead buffer may also be shifted up by three entries, which may involve the segments in entries LB_0, LB_1, and LB_2 being shifted to entries HB_9, HB_10, and HB_11.  The segment in “new” buffer 1006 may be shifted into entry LB_1, and the next three segments from the input stream may be stored in LB_2, LB_3, and “new” buffer 1006, respectively.
[0126]      Figure 18 illustrates an example scenario in which a five-segment match is found between segments in lookahead buffer 1004 and history buffer 1002.  This scenario is an example of an “extended repeat” in which the segment in entry HB_11 matches all of the entries in lookahead buffer 1004 and “new” buffer 1006.  Thus, the longest match is between the segments in entries HB11, LB_0, LB_1, LB_2, and LB_3, and the segments in entries LB_0, LB_1, LB_2, LB_3, and “new” buffer 1006.
[0127]      In response to determining that there is an extended repeat match of five segments, output using format 1104 may be generated.  This output may include an extended repeat code word of 111 (binary), and a repeat length of 00000 (binary) indicating that the match continues for five segments (for extended repeat code words, the repeat length codes may denote the repeat length minus 5).   Thus, in place of five 64-bit segments, one 8-bit value may be used.  In scenarios in which the repeat continues for additional segments, the input stream may continue to be read and the repeat length may be incremented accordingly.
[0128]      Figures 19A, 19B, 19C, and 19D provide further illustration of the possible benefits of the column padding mechanisms described above.  Figure 19A depicts example image block 1900 with overlaid example 8 x 2 halftone matrices.   Notably, after halftoning, the pixels aligned with the three halftone matrices that begin at point 1902 are identical to the pixels aligned with the three halftone matrices that begin at point 1904.  
[0129]      Figure 19B depicts buffer arrangement 1906, containing the halftone matrices of Figure 19A after interleaving.  As can be seen in Figure 19B, even though the pixels aligned with the three halftone matrices that begin at point 1902 are identical to the pixels aligned with the three halftone matrices that begin at point 1904, they are offset from one another in buffer arrangement 1906.  Consequently, there is no match between entries in the lookahead buffer and the history buffer.
[0130]      Figure 19C depicts example image block 1908 with overlaid example 8 x 2 halftone matrices.   Example image block 1908 is similar to that of example image block 1900, except that two padding columns 1910 are applied to the right-hand side.  The pixels aligned with the three halftone matrices that begin at point 1902 are identical to the pixels aligned with the three halftone matrices that begin at point 1904 except for the changes made by the incorporation of padding columns 1910.
[0131]      Figure 19D depicts buffer arrangement 1912, containing the halftone matrices of Figure 19C after interleaving.  The first two pixels 1914 of the padding columns (the top-most padding pixels) are circled, as are the second two pixels 1916 of the padding columns (the second top-most padding pixels).  As can be seen in Figure 19D, the incorporation of the padding columns result in three matches between the history buffer and the lookahead buffer.  Particularly, entries HB_5, HB_6, and HB_7 match entries LB_0, LB_1, and LB_2.  In this way, padding columns may result in more efficient compression of halftoned images.
5.    Example Operation 
[0132]      Figure 20 is a flow chart of an example embodiment. The steps illustrated by this flow chart may be carried out by one or more printing devices, such as printing device 100, and/or computing devices, such as computing device 300.  Aspects of each individual step may be performed by a single device or distributed between multiple computing devices.  The example embodiment of Figure 20 may also include any feature or features disclosed throughout this specification and/or the accompanying drawings.
[0133]      At step 2000, based on an m x n halftone matrix and a first m x n pixel block of an image, a first m x n halftone version of the first m x n pixel block may be determined.  This determination may involve tiling the m x n halftone matrix over the image such that starting positions of vertically contiguous tiles of the m x nhalftone matrix are offset by qpixels.  Additionally, r 1 x n padding pixel columns may be appended to the rightmost column of the image.  In some embodiments, p may be the width of the image in pixels before appending the r 1 x n padding pixel columns, and r may be m - (p - q) mod m.
[0134]      At step 2002, an n-way interleave may be performed on rows of the first m x n halftone version of the first m x n pixel block to create a first mn x 1 halftone segment.
[0135]      At step 2004, the first mn x 1 halftone segment may be compared to one or more halftone segments in a first-in-first-out (FIFO) buffer.  This comparison may involve determining the longest consecutive extent of halftone segments in the FIFO buffer that match the first mn x 1 halftone segment and any other halftone segments contiguously following the first mn x 1 halftone segment.
[0136]      At step 2006, it may be determined whether the first mn x 1 halftone segment matches any halftone segments in the FIFO buffer.  If the first mn x 1 halftone segment matches a particular halftone segment in the FIFO buffer, then at step 2008 a repeat code word and a repeat value may be output, and at least one representation of the first mn x 1 halftone segment may be written to the FIFO buffer.  In some embodiments, a repeat position indicative of a location of the particular halftone segment in the FIFO buffer may be included in this output.
[0137]      If the first mn x 1 halftone segment does not match any halftone segments in the FIFO buffer, then at step 2010 a literal code word and a representation of the first mn x 1 halftone segment may be output, and the representation of the first mn x 1 halftone segment may be written to the FIFO buffer.
[0138]      In some embodiments, the first mn x 1 halftone segment may be stored in one or more lookahead buffers with  other mn x 1 halftone segments.  Additionally, of the other mn x 1 halftone segments in the FIFO buffer may also match the particular halftone segment.  The j matching halftone segments may be contiguous in the lookahead buffer(s), and/or the repeat value is indicative of j.  Writing the at least one representation of the first mn x 1 halftone segment to the FIFO buffer may involve writing j representations of the first mn x 1 halftone segment to the FIFO buffer.  Further, the other mn x 1 halftone segments may be derived from other m x n pixel blocks of the image.  In some implementations, the j matching halftone segments may be removed from the lookahead buffer(s).
[0139]      In addition, the repeat code word may be either a short repeat code word or an extended repeat code word.  In either case, j may be compared to k. If j<k, the short repeat code word may be used as the repeat code word, and if j ? k, the extended repeat code word may be used as the repeat code word.  If the extended repeat code word is the repeat code word, then after writing j representations of the first mn x 1 halftone segment to the FIFO buffer, at least one entry in the lookahead buffer may be replaced with a second mn x 1 halftone segment.  The second mn x 1 halftone segment may be derived from a second m x n pixel block of the image.
[0140]      Moreover, each cell of the m x n halftone matrix may contain  threshold values.  The  threshold values may define i pixel value ranges, and each cell of the first m x n halftone version of the first m x n pixel block may contain a log2(i) -bit value.  Determining the first m x n halftone version of the first m x n pixel block may involve, for each particular cell in the first m x n pixel block, (i) determining a particular pixel value of the particular cell in the first m x n pixel block, (ii) determining that one of the i pixel value ranges in a particular cell of the m x nhalftone matrix encompasses the particular pixel value, where the particular cell in the first m x n pixel block corresponds to the particular cell of the m x n halftone matrix, and (iii) writing, to a particular cell of the first m x n halftone version of the first m x n pixel block, a log2(i)-bit value that represents the determining one of the i pixel value ranges.
6.    Conclusion 
[0141]      The present invention is not to be limited in terms of the particular embodiments described in this application, which are intended as illustrations of various aspects.  Many modifications and variations can be made without departing from its spirit and scope, as will be apparent to those skilled in the art.  Functionally equivalent methods and apparatuses within the scope of the invention, in addition to those enumerated herein, will be apparent from the foregoing descriptions.  Such modifications and variations are intended to fall within the scope of the appended claims.  
[0142]      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.    
[0143]      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.
[0144]      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.
[0145]      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.
[0146]      A method comprises: based on an m x n halftone matrix and a first m x n pixel block of an image, determining, by a computing device,  a first m x n halftone version of the first m x n pixel block; performing an n-way interleave on rows of the first m x n halftone version of the first m x n pixel block to create a first mn x 1 halftone segment; comparing the first mn x 1 halftone segment to one or more halftone segments in a first-in-first-out (FIFO) buffer; if the first mn x 1 halftone segment does not match any halftone segments in the FIFO buffer, (i) outputting a literal code word and a representation of the first mn x 1 halftone segment, and (ii) writing the representation of the first mn x 1 halftone segment to the FIFO buffer; and if the first mn x 1 halftone segment matches a particular halftone segment in the FIFO buffer, (i) outputting a repeat code word and a repeat value, and (ii) writing at least one representation of the first mn x 1 halftone segment to the FIFO buffer.
[0147]      In the above method, the first mn x 1 halftone segment is stored in a lookahead buffer with k-1 other mn x 1 halftone segments, wherein j-1 ? k of the other mn x 1 halftone segments also match the particular halftone segment in the FIFO buffer, wherein the j matching halftone segments are contiguous in at least the lookahead buffer, wherein the repeat value is indicative of j, and wherein writing the at least one representation of the first mn x 1 halftone segment to the FIFO buffer comprises writing j representations of the first mn x 1 halftone segment to the FIFO buffer.
[0148]      In the above method, the k-1 other mn x 1 halftone segments are derived from other m x n pixel blocks of the image.
[0149]      The above method further comprises: removing the j matching halftone segments from the lookahead buffer.
[0150]      In the above method, the repeat code word is either a short repeat code word or an extended repeat code word. 
[0151]      The above method further comprises:comparing j to k; if j < k, using the short repeat code word as the repeat code word; and if j ? k, using the extended repeat code word as the repeat code word. 
[0152]      In the above method, the extended repeat code word is the repeat code word, the method further comprises: after writing j representations of the first mn x 1 halftone segment to the FIFO buffer, replacing at least one entry in the lookahead buffer with a second mn x 1 halftone segment, wherein the second mn x 1 halftone segment was derived from a second m x n pixel block of the image.
[0153]      In the above method, comparing the first mn x 1 halftone segment to the one or more halftone segments in the FIFO buffer comprises determining the longest consecutive extent of halftone segments in the FIFO buffer that match the first mn x 1 halftone segment and any other halftone segments contiguously following the first mn x 1 halftone segment.
[0154]      In the above method, the first mn x 1 halftone segment matches the particular halftone segment in the FIFO buffer, the method further comprises: outputting a repeat position that is indicative of a location of the particular halftone segment in the FIFO buffer.  
[0155]      In the above method, each cell of the m x n halftone matrix contains i-1 threshold values, wherein the i-1 threshold values define i pixel value ranges, and wherein each cell of the first m x n halftone version of the first m x n pixel block contains a log2(i)-bit value.
[0156]      In the above method, determining the first m x n halftone version of the first m x n pixel block comprises, for each particular cell in the first m x n pixel block: determining a particular pixel value of the particular cell in the first m x n pixel block; determining that one of the i pixel value ranges in a particular cell of the m x n halftone matrix encompasses the particular pixel value, wherein the particular cell in the first m x n pixel block corresponds to the particular cell of the m x n halftone matrix; and writing, to a particular cell of the first m x n halftone version of the first m x n pixel block, a log2(i)-bit value that represents the determining one of the i pixel value ranges. 
[0157]      In the above method, determining the first m x n halftone version of the first m x n pixel block comprises      tiling the m x n halftone matrix over the image such that starting positions of vertically contiguous tiles of the m x n halftone matrix are offset by q pixels, the method further comprises: appending r 1 x n padding pixel columns to the rightmost column of the image.
[0158]      In the above method, p is the width of the image in pixels before appending the r 1 x n padding pixel columns, and r is m - (p-q) mod m.
[0159]      An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations comprises:   based on an m x n halftone matrix and a first m x n pixel block of an image, determining, by a computing device,  a first m x n halftone version of the first m x n pixel block; performing an n-way interleave on rows of the first m x n halftone version of the first m x n pixel block to create a first mn x 1 halftone segment; comparing the first mn x 1 halftone segment to one or more halftone segments in a first-in-first-out (FIFO) buffer; if the first mn x 1 halftone segment does not match any halftone segments in the FIFO buffer, (i) outputting a literal code word and a representation of the first mn x 1 halftone segment, and (ii) writing the representation of the first mn x 1 halftone segment to the FIFO buffer; and if the first mn x 1 halftone segment matches a particular halftone segment in the FIFO buffer, (i) outputting a repeat code word and a repeat value, and (ii) writing at least one representation of the first mn x 1 halftone segment to the FIFO buffer.
[0160]      In the above article of manufacture, the first mn x 1 halftone segment is stored in a lookahead buffer with k-1 other mn x 1 halftone segments, wherein j-1 ? k of the other mn x 1 halftone segments also match the particular halftone segment in the FIFO buffer, wherein the j matching halftone segments are contiguous in the lookahead buffer, wherein the repeat value is indicative of j, and wherein writing the at least one representation of the first mn x 1 halftone segment to the FIFO buffer comprises writing j representations of the first mn x 1 halftone segment to the FIFO buffer. 
[0161]      In the above article of manufacture, the repeat code word is either a short repeat code word or an extended repeat code word. 
[0162]      In the above article of manufacture, the operationsfurther comprises: comparing j to k; if j < k, using the short repeat code word as the repeat code word; and if j ? k, using the extended repeat code word as the repeat code word. 
[0163]      In the above article of manufacture, the extended repeat code word is the repeat code word, the method further comprises: after writing j representations of the first mn x 1 halftone segment to the FIFO buffer, replacing at least one entry in the lookahead buffer with a second mn x 1 halftone segment, wherein the second mn x 1 halftone segment was derived from a second m x n pixel block of the image.
[0164]      A computing device comprises: a processor;    data storage; and program instructions, stored in the data storage, that upon execution by the processor cause the computing device to perform operations of the above mentioned method.
[0165]      A program that, upon execution by a computing device, causes the computing device to perform operations of the above mentioned method.
INDUSTRIAL APPLICABILITY
[0166]      The present invention may be applicable to compression of halftoned digital images.
REFFERENCE SIGNS LIST
[0167]      
100   Printing Device
102   Document Feeder / Output Tray
104   Paper Storage
106   User Interface 10
108   Scanning Element
110   Chassis
200   Computing Device Components
202   Processor
204   Data Storage
206   Input / Output Function
208   System Bus
300   Computing Device
302   Scanning Function
304   Printing Function
306   Scan-to-Host Data Path
308   Host-to-Print Data Path
310   Scan-to-Print Data Path
1.    A method comprising:
based on an m x n halftone matrix and a first m x n pixel block of an image, determining, by a computing device,  a first m x n halftone version of the first m x n pixel block;
performing an n-way interleave on rows of the first m x n halftone version of the first m x n pixel block to create a first mn x 1 halftone segment;
comparing the first mn x 1 halftone segment to one or more halftone segments in a first-in-first-out (FIFO) buffer;
if the first mn x 1 halftone segment does not match any halftone segments in the FIFO buffer, (i) outputting a literal code word and a representation of the first mn x 1 halftone segment, and (ii) writing the representation of the first mn x 1 halftone segment to the FIFO buffer; and
if the first mn x 1 halftone segment matches a particular halftone segment in the FIFO buffer, (i) outputting a repeat code word and a repeat value, and (ii) writing at least one representation of the first mn x 1 halftone segment to the FIFO buffer.
2.    The method of claim 1, wherein the first mn x 1 halftone segment is stored in a lookahead buffer with k-1 other mn x 1 halftone segments, wherein j-1 ? k of the other mn x 1 halftone segments also match the particular halftone segment in the FIFO buffer, wherein the j matching halftone segments are contiguous in at least the lookahead buffer, wherein the repeat value is indicative of j, and wherein writing the at least one representation of the first mn x 1 halftone segment to the FIFO buffer comprises writing j representations of the first mn x 1 halftone segment to the FIFO buffer.
3.    The method of claim 2, wherein the k-1 other mn x 1 halftone segments are derived from other m x n pixel blocks of the image.
4.    The method of claim 2, further comprising:
removing the j matching halftone segments from the lookahead buffer.
5.    The method of claim 2, wherein the repeat code word is either a short repeat code word or an extended repeat code word.
6.    The method of claim 5, the method further comprising:
comparing j to k;
if j < k, using the short repeat code word as the repeat code word; and
if j ? k, using the extended repeat code word as the repeat code word. 
7.    The method of claim 6, wherein the extended repeat code word is the repeat code word, the method further comprising:
after writing j representations of the first mn x 1 halftone segment to the FIFO buffer, replacing at least one entry in the lookahead buffer with a second mn x 1 halftone segment, wherein the second mn x 1 halftone segment was derived from a second m x n pixel block of the image.
8.    The method of any one of claim 1 to claim 7, wherein comparing the first mn x 1 halftone segment to the one or more halftone segments in the FIFO buffer comprises determining the longest consecutive extent of halftone segments in the FIFO buffer that match the first mn x 1 halftone segment and any other halftone segments contiguously following the first mn x 1 halftone segment.
9.    The method of any one of claim 1 to claim 8, wherein the first mn x 1 halftone segment matches the particular halftone segment in the FIFO buffer, the method further comprising:
outputting a repeat position that is indicative of a location of the particular halftone segment in the FIFO buffer.  
10.   The method of any one of claim 1 to claim 9, wherein each cell of the m x n halftone matrix contains i-1 threshold values, wherein the i-1 threshold values define i pixel value ranges, and wherein each cell of the first m x n halftone version of the first m x n pixel block contains a log2(i)-bit value.
11.   The method of claim 10, wherein determining the first m x n halftone version of the first m x n pixel block comprises, for each particular cell in the first m x n pixel block:
determining a particular pixel value of the particular cell in the first m x n pixel block;
determining that one of the i pixel value ranges in a particular cell of the m x n halftone matrix encompasses the particular pixel value, wherein the particular cell in the first m x n pixel block corresponds to the particular cell of the m x n halftone matrix; and
writing, to a particular cell of the first m x n halftone version of the first m x n pixel block, a log2(i)-bit value that represents the determining one of the i pixel value ranges.
12.   The method of any one of claim 1 to claim 11, wherein determining the first m x n halftone version of the first m x n pixel block comprises     tiling the m x n halftone matrix over the image such that starting positions of vertically contiguous tiles of the m x n halftone matrix are offset by q pixels, the method further comprising:
appending r 1 x n padding pixel columns to the rightmost column of the image.
13.   The method of claim 12, wherein p is the width of the image in pixels before appending the r 1 x n padding pixel columns, and wherein r is m - (p-q) mod m.
14.   An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations comprising:
based on an m x n halftone matrix and a first m x n pixel block of an image, determining, by a computing device,  a first m x n halftone version of the first m x n pixel block;
performing an n-way interleave on rows of the first m x n halftone version of the first m x n pixel block to create a first mn x 1 halftone segment;
comparing the first mn x 1 halftone segment to one or more halftone segments in a first-in-first-out (FIFO) buffer;
if the first mn x 1 halftone segment does not match any halftone segments in the FIFO buffer, (i) outputting a literal code word and a representation of the first mn x 1 halftone segment, and (ii) writing the representation of the first mn x 1 halftone segment to the FIFO buffer; and
if the first mn x 1 halftone segment matches a particular halftone segment in the FIFO buffer, (i) outputting a repeat code word and a repeat value, and (ii) writing at least one representation of the first mn x 1 halftone segment to the FIFO buffer.
15.   The article of manufacture of claim 14, wherein the first mn x 1 halftone segment is stored in a lookahead buffer with k-1 other mn x 1 halftone segments, wherein j-1 ? k of the other mn x 1 halftone segments also match the particular halftone segment in the FIFO buffer, wherein the j matching halftone segments are contiguous in the lookahead buffer, wherein the repeat value is indicative of j, and wherein writing the at least one representation of the first mn x 1 halftone segment to the FIFO buffer comprises writing j representations of the first mn x 1 halftone segment to the FIFO buffer.
16.   The article of manufacture of claim 14 or claim 15, wherein the repeat code word is either a short repeat code word or an extended repeat code word.
17.   The article of manufacture of claim 16, the operations further comprising:
comparing j to k;
if j < k, using the short repeat code word as the repeat code word; and
if j ? k, using the extended repeat code word as the repeat code word. 
18.   The article of manufacture of claim 16, wherein the extended repeat code word is the repeat code word, the operations further comprising:
after writing j representations of the first mn x 1 halftone segment to the FIFO buffer, replacing at least one entry in the lookahead buffer with a second mn x 1 halftone segment, wherein the second mn x 1 halftone segment was derived from a second m x n pixel block of the image.
19.   A computing device comprising:
a processor;
data storage; and
program instructions, stored in the data storage, that upon execution by the processor cause the computing device to perform operations of the method according to any one of claim 1 to claim 13.
20.   A program that, upon execution by a computing device, causes the computing device to perform operations of the method of any one of claim 1 to claim 13.
PROBLEM TO BE SOLVED
The present invention may provide method for compression of halftoned digital images.
SOLUTION
Based on an m x n halftone matrix and an m x n pixel block of an image, an m x n halftone version of the m x n pixel block may be determined.  An n-way interleave may be performed on rows of the m x n halftone version to create an mn x 1 halftone segment.  The mn x 1 halftone segment may be compared to one or more halftone segments in a buffer.  Based on the comparison, a literal code word and a representation of the mn x 1 halftone segment may be output, and the representation of the mn x 1 halftone segment may be written to the buffer.  Alternatively, a repeat code word and a repeat value may be output, and at least one representation of the mn x 1 halftone segment may be written to the buffer.
REPRESENTATIVE DRAWING: Fig. 20
2014087066.tif 000027
2014087066.tif 000028
2014087066.tif 000029
2014087066.tif 000030
2014087066.tif 000031
2014087066.tif 000032
2014087066.tif 000033
2014087066.tif 000034
2014087066.tif 000035
2014087066.tif 000036
2014087066.tif 000037
2014087066.tif 000038
2014087066.tif 000039
2014087066.tif 000040
2014087066.tif 000041
2014087066.tif 000042
2014087066.tif 000043
2014087066.tif 000044
2014087066.tif 000045
2014087066.tif 000046
2014087066.tif 000047
2014087066.tif 000048
2014087066.tif 000049
2014087066.tif 000050