(57)【特許請求の範囲】
【請求項１】
所定の最大数内の複数のサブピクセルを各々が含む複数のピクセルによって表現される画像を符号化する方法であって、上記複数のピクセルから１つのピクセル集合を定義するステップと、当該ピクセル集合の中で、サブピクセルの部分集合が１にセットされたハーフトーン・ピクセルが多くとも１つとなるように、当該ピクセル集合内のサブピクセルの総数を変えずに、当該ピクセル集合内でサブピクセルを移動するステップと、すべてのサブピクセルが１にセットされたピクセルを第１の識別子によってメモリ上で表し、すべてのサブピクセルが０にセットされたピクセルを第２の識別子によってメモリ上で表すステップと、上記多くとも１つのハーフトーン・ピクセルが存在すればそのハーフトーン・ピクセルを符号化するステップと、を含む画像符号化方法。
【請求項２】
上記ピクセルを識別子によって表すステップが上記ピクセル集合のビットマップ値をメモリに記憶することを含み、上記第１の識別子がビットマップ値の１に対応し、上記第２の識別子がビットマップ値の０に対応し、上記ハーフトーン・ピクセルを符号化するステップが、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数と等しい場合、上記ビットマップの対応するビットを１にセットし、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数を越えている場合、上記ビットマップの対応するビットを１にセットし、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数未満の場合、上記ビットマップの対応するビットを０にセットするステップと、上記メモリに上記ピクセル集合における上記多くとも１つのハーフトーン・ピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記多くとも１つのハーフトーン・ピクセル内で１にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、請求項１に記載の画像符号化方法。
【請求項３】
上記ピクセルを識別子によって表すステップが上記集合のビットマップ値をメモリに記憶することを含み、上記第１の識別子がビットマップ値の１に対応し、上記第２の識別子がビットマップ値の０に対応し、上記ハーフトーン・ピクセルを符号化するステップが、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数を越えている場合、上記ビットマップの対応するビットを１にセットし、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数と等しい場合、上記ビットマップの対応するビットを０にセットし、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数未満の場合、上記ビットマップの対応するビットを０にセットするステップと、上記メモリに上記集合における上記多くとも１つのハーフトーン・ピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記多くとも１つのハーフトーン・ピクセル内で１にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、請求項１に記載の画像符号化方法。
【請求項４】
複数のサブピクセルを各々が含む複数のピクセルによって表現される画像を符号化および復号化する方法であって、上記複数のピクセルから１つのピクセル集合を定義するステップと、当該ピクセル集合の中で、サブピクセルの部分集合が１にセットされた部分ピクセルが多くともＮ個となるように、当該ピクセル集合内のサブピクセルの総数を変えずに、当該ピクセル集合内でサブピクセルを移動するステップと、すべてのサブピクセルが１にセットされた、上記ピクセル集合内のピクセルをメモリ上で第１の識別子によって表し、すべてのサブピクセルが０にセットされた、上記ピクセル集合内のピクセルを第２の識別子によって表すステップと、サブピクセルの部分集合が１にセットされた部分ピクセルが存在する場合その部分ピクセルについて、上記ピクセル集合内の位置および１にセットされたサブピクセルの数を符号化して上記メモリに記憶するステップと、上記メモリに記憶されている上記部分ピクセルを復号するステップと、上記ピクセル集合を取り出すステップと、を含む、画像符号復号方法。
【請求項５】
上記ピクセルを識別子によって表すステップが上記ピクセル集合のビットマップ値をメモリに記憶することを含み、上記第１の識別子がビットマップの１に対応し、上記第２の識別子がビットマップの０に対応し、上記ピクセルを符号化するステップが、Ｎ個の部分ピクセルの各々毎に、対応する部分ピクセルに対する上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数を越えている場合、上記ビットマップの対応するビットを１にセットし、上記部分集合のサブピクセルの数がサブピクセルの所定の最大数の半数未満である場合、上記ビットマップの対応するビットを０にセットするステップと、上記メモリに上記ピクセル集合の上記Ｎ個の部分ピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記Ｎ個の部分ピクセルの各々において１にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、請求項４に記載の画像符号復号方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連続階調グレイスケール画像のデジタル・ハーフトーン化および印刷に関するもので、特に、ハーフトーン化された画像を表すデジタル情報を効率的に符号化し記憶する方法に関するものである。
【０００２】
【従来の技術】
連続階調グレイスケール画像のデジタル・ハーフトーン化および印刷のプロセスにおいて、ハーフトーン解像度と生成される階調数の間でトレードオフが一般的に存在する。より大きな辺細部を達成するため解像度を増大すれば、使用可能な階調度数は減少し、輪郭の深みおよび円滑性がそれに応じて劣化する。例えば、６００ｄｐｉ印刷装置について、１インチ当たり７０行（＠４５度）の古典的スクリーンから１インチ当たり１０６行スクリーンへ変更すれば、非ゼロの階調度数は７２から３２へ減少する。ハーフトーン化技術に関する詳細情報は、 R. Ulichney氏著"Digital halftoning"(ISBN 0-262-21009-6)に記載されている。
【０００３】
最も直接的な解決方法は、印刷装置の解像度を増加させることである。例えば、６００ｄｐｉから１２００ｄｐｉの印刷装置へ変更することによって、使用可能階調度数は４倍となる。しかしながら、より高い解像度のための印刷メカニズムのコスト増および４倍に増加したビットマップのためのメモリ容量の増加という問題が派生する。
【０００４】
インクジェットおよびレーザ印刷装置のようなハードコピー・ラスタ出力装置は、プリント・ヘッドまたはレーザ走査方向の装置解像度を拡張することによって階調度の増加を達成することがきる。この拡張解像度方式におけるハーフトーン化された画像の品質は最高である。しかし、その結果のハーフトーンは、メモリおよび記憶のための圧縮動作を相応に必要とする。６００×２４００ｄｐｉ装置として使用されるレーザ印刷装置は、所与のハーフトーン画面について４倍の階調度数を印刷することができる。しかし、ビットマップのメモリ要求容量は、１２００ｄｐｉに関する場合と同様に４倍増大する。
【０００５】
拡張解像度を使用するためのビットマップ・メモリ増大を回避するため、画像をリアルタイムでハーフトーン化し、ビットマップ・メモリでの中間記憶を省略して印刷装置へ直接送ることができる。しかし、テキストや図形のような非画像エレメントが印刷ページに含まれていることがある。それらのエレメントは、ハーフトーン画像に上重ねされたり、マスクしたり、またはハーフトーン画像に論理的動作を行ってハーフトーンン画像と共にメモリに記憶されている場合がある。データ圧縮が、ハーフトーン画像に適用され、必要なビットマップ・メモリ容量を減らし、リアルタイムで伸張された出力が印刷装置へ送られる。しかし、非画像ページ・エレメントに関する動作が、頻繁な伸張、修正および再圧縮を必要として、このため処理性能が顕著に劣化する。加えて、両面ページ印刷は、ビットマップを逆順にアクセスすることが多いのでほとんどの伸張方式を使用できない。
【０００６】
【発明が解決しようとする課題】
従って、必要メモリ容量の増加に比較してハーフトーン画像の階調度数が飛躍的に拡大する効率的画像符号化方法および装置が必要とされる。
【０００７】
【課題を解決するための手段】
本発明は、画像を符号化する方法である。画像は、複数のピクセルによって表現され、各ピクセルは多数のサブピクセルを含む。最初に、複数ピクセルから１つのピクセル集合が定義される。該集合の中の多くとも１つのピクセルが第１の値に設定された複数のサブピクセル部分集合を持つように、該ピクセル集合は統合される。（このように第１の値に設定された複数のサブピクセルを持つピクセルを本明細書では部分集合と呼ぶ）。上記第１の値に設定されたサブピクセルのすべてを持つ該集合中の部分ピクセル、および、上記第１の値に設定されてないサブピクセルのすべてを持つ該集合中のピクセルが、メモリ上のビットマップに記憶される。最後に、部分ピクセルがメモリ上で符号化される。
【０００８】
符号化プロセスを実行するため、第１に、部分ピクセルが、設定されたサブピクセルの半分以上を持つ場合、ビットマップの対応するビットがオンに設定され、当該部分ピクセルが、設定されたサブピクセルの半分以上を持っていない場合には、ビットマップの対応するビットはゼロにされる。次に、部分ピクセルの位置がメモリに記憶される。最後に、識別子がメモリに記憶される。この識別子は、対応するビットとの組み合わせで、当該部分ピクセル中のオンにセットされたサブピクセルの数を記述する。
【０００９】
発明の課題を解決する手段として、本発明は、複数のサブピクセルを各々が含む複数のピクセルによって表現される画像を符号化するため、上記複数のピクセルから１つのピクセル集合を定義し、当該ピクセル集合の中の多くとも１つのピクセルが第１の値にセットされたサブピクセルの部分集合を有するように、上記ピクセル集合を統合し、上記第１の値にセットされたすべてのサブピクセルを持つピクセルを第１の識別子によってメモリ上で表し、第２の値にセットされたすべてのサブピクセルを持つピクセルを第２の識別子によって表し、上記多くとも１つのピクセルが存在すればそのピクセルを符号化する画像符号化方法を含む。
【００１０】
【発明の実施の形態】
本発明は、拡張解像度を使用して、所与のハーフトーン・スクリーンに関して、通常使用可能なものより７倍の階調度を提供することによって、ハーフトーン化された画像品質を劇的に改善する。しかも、本発明は、圧縮を行わずに通常の場合に比較してわずかに２倍のビットマップ・メモリを必要とするにすぎない。また、本発明は、テキストおよび図形のような非画像エレメントに対して完全な互換性を持つ。
【００１１】
本発明の核心は、以下に記述するように、通常のビットマップ・メモリと同サイズの２次メモリにある。通常のビットマップ・メモリは、テキストと図形のような非画像エレメントと共に、通常解像度のハーフトーン画像を含む。２次メモリは、通常解像度のハーフトーン画像とその対応する拡張解像度のハーフトーン画像の間の差分の情報を含む。印刷時に、この情報を使用して通常の解像度画像を補正することによって、画像が印刷される場合、拡張解像度が復元される。
【００１２】
本発明の好ましい実施形態に関する以下の記述において、「部分ピクセル符号化」方法は、通常の６００ｄｐｉビットマップ・メモリおよび６００×４２００ｄｐｉ拡張解像度ハーフトーン画像を記憶する２次メモリを使用する。
【００１３】
部分ピクセル符号化の基本が図１に示されている。拡張解像度（６００×４２００ｄｐｉ）ドット群の高解像度情報は、その辺における部分ピクセルに含まれ、その他のピクセルは、粗めの解像度で表される。部分ピクセル符号化は、ハーフトーン画像を２つのコンポーネントに分割する。第１は、通常の出力装置解像度（６００ｄｐｉ）の画像の粗め表示、すなわち図１の(Ｂ)である。該ページの非画像エレメントとともにそれは通常のビットマップ・メモリに収納される。第２のコンポーネントは、粗め表示と拡張解像度画像の間の部分ピクセル差、すなわち図１の(Ｃ)であり、これは２次メモリ内に符号化される。
【００１４】
部分ピクセル符号化は、１次元（行）プロセスであり、１度に６００ｄｐｉピクセルの連続する４個の位置（本明細書でこれを１つの集合と呼ぶ）に対して作用する。２次元の適用も可能であるが、（ハーフトーン化を含む）ほとんどの画像処理および記憶は行単位で行われる。図２は、図１の（Ａ）のドット群の最上行を符号化する場合の最初のステップを示す。完全オン（７／７）および完全オフ（０／７）ピクセルが通常ビットマップ・ニブルに記憶され、正確に表現される。（注：以下の記述において、上記完全オンおよび完全オフのピクセルを完全ピクセル、その両者の間(１／７−６／７)のハーフトーン・ピクセルを部分ピクセルと呼称する）。
【００１５】
図３は、部分ピクセル符号化を示す。各ピクセルは、７つのサブピクセルに分割されるので、１２８種類の組み合わせが可能である。しかし、部分ピクセルは、１／７から６／７の範囲の総体的平均階調度として解釈される。従って、部分ピクセル符号化は６段階だけの符号化を必要とする。符号化は、先ず、サブピクセル・セットの数に基づいて対応する粗めのピクセルを設定する。サブピクセル・セットの数が３を超えていれば、通常のビットマップ・ニブルの中の対応する粗めピクセルはオン（すなわち１）にセットされる。反対に、サブピクセル・セットの数が３以下であれば、通常のビットマップ・ニブルの中の対応する粗めピクセルはリセットされる（すなわち０にセットされる）。図３の場合ピクセル３００はサブピクセルを３個有している。部分ピクセル３００のサブピクセルは４未満であるので、対応する粗めピクセル３０３はリセットされる(すなわちゼロとされる)。
【００１６】
次に、粗めピクセルと部分ピクセルの間の誤差が、符号化されたニブルにおける誤差ビット・ペアによって表現され、符号化される。部分ピクセル３００とピクセル３０３の間の誤差は、(粗めピクセル)−(部分ピクセル)＝０−３＝−３のように定義される。次の表１は、上記誤差値を誤差ビット・ペアに符号化する際に使用される参照テーブルである。
【００１７】
【表１】
0003744610.tif 000002
【００１８】
表１を参照すると、誤差−３はビット・ペア"１１"で表される。この符号化されたビット・ペアが、図３の誤差ビット・ペア３０７および３０８に記憶される。
【００１９】
最後に、部分ピクセルの位置が符号化ニブルに記憶される。最左端ピクセル位置を０、最右端位置を３と仮定して、ピクセル位置は２ビットの２進数で表すことができ、その２ビットを符号化ニブルの最初の２ビットに記憶する。図３の例を完成させるには、ビット・ペアに符号化された部分ピクセルの元は、ピクセル位置２から出たものであるので、２進数"２"(すなわち１０)が、位置３０５および３０６に符号化される。
【００２０】
符号化ニブルの値がゼロであればそれは誤差ゼロすなわち部分ピクセルが存在しないことを示すことに注意する必要がある。従って、テキストのような非画像エレメントは（符号化ニブルがゼロに初期化されていると仮定して）符号化を必要とせず、通常ビットマップで正確に表現される。
【００２１】
図４および５は、復号プロセスを示す。復号プロセスの間、通常ビットマップは無修正で渡される。従って、テキストのような非画像エレメントは、正確に通常ビットマップで表されているので、復号を必要としない。非ゼロに符号化されたニブルについて、部分ピクセルのピクセル位置が、左側ビット・ペアによって示される。その他の３つのピクセルは、定義によって完全ピクセルであって、図４に示されるように無修正のまま渡される。
【００２２】
図５は、部分ピクセル復号化を示す。部分ピクセルのサブピクセルの数が、通常ビットマップ・ニブルの粗めピクセルおよび符号化ニブルの誤差ビット・ペアを基に決定される（すなわち上述の符号化の際の対応付けの逆操作である）。部分ピクセルの原形に関連する失われた情報が復元された点に注意する必要がある。部分ピクセルは、ドット群の仮定に基づいて、この情報を取り戻すことを試行する。復号器は、ビットマップ・ニブル中の隣接する完全ピクセルの状態に基づいて、サブピクセルを左また右側に配列して、粗め画像の辺を拡張する。隣接する粗め画像の辺が検出されない場合は、デフォルトの配列が使用される。
【００２３】
上記の部分ピクセル符号化方法は、対象となる４つの連続するピクセル部分においてただ１つの部分ピクセルの発生しかサポートしない点は当業者に理解されるであろう。しかし、４つのピクセル区間における複数の部分ピクセル発生は、拡張解像度ハーフトーン方式で処理することができる。複数部分ピクセル発生は、(1)ハーフトーンしきい値(ディザ)アレイの設計、(2)連続階調ソース画像における強度勾配という２つの理由を持つ。
【００２４】
図６の(Ａ)および(Ｂ)は、互換性のあるしきい値アレイおよびそれらの部分ピクセル・コンポーネントによってそれぞれ生成されるドット群を示し、一方、図６の(Ｃ)および(Ｄ)は、互換性のないしきい値アレイおよびそれらの部分ピクセル・コンポーネントによって生成されるドット群を示す。
【００２５】
部分ピクセル符号化と互換性のあるハーフトーンしきい値アレイを設計することができる。唯一の制約は、任意の一定の階調度に関して、結果として生ずるハーフトーン・ドット群の部分ピクセルは、処理する（行）でそれらを分離する少くとも３つの完全ピクセルを持つ点である。このような制約があっても、（６００ｄｐｉの通常の解像度を仮定して）＠４５度の１インチ当たり２１２行までの中間調スクリーン頻度のための互換しきい値アレイを生成することができる。
【００２６】
互換しきい値アレイを用いても、なお、ソース画像の強度勾配によって複数の部分ピクセルが発生することがある。解決策は、符号化の前の部分ピクセル統合フィルタの使用である。複数の部分ピクセルが存在する場合、フィルタは、最隣接の部分ピクセルを犠牲にして最大部分ピクセルを「成長」させ、その最大ピクセルが全体ピクセルまたは唯一の残存ピクセルのいずれかになるまで続ける。フィルタ処理は、１つ以上の部分ピクセルが残っていない状態になるまで繰り返される。
【００２７】
部分ピクセル統合は、許容できぬほどハーフトーン画像品質を劣化させない。複数部分ピクセルを発生させる程に大きい強度勾配に関しては、強度は、しきい値アレイの区間にわたって大幅にに変化し、従って、どのようにしても正確に表現することはできないので、部分ピクセル統合が付加する影響は無視できるほどのものである。
【００２８】
４つのピクセルすべてを統合することは可能であるが、本発明の好ましい実施形態は、１度に２つのピクセルに作用する。このようなアプローチは、２つの部分ピクセルは、より大きい部分ピクセルをそれが完全オンになるまで増加させ、一方、より小さい部分ピクセルをそれが完全オフになるまで減少させることによって、１つに「凝縮する」ことができるという理解に基づいている。統合の詳細が図１１に示されている。統合動作に使用される凝縮サブルーチンが図１２に示されている。部分ピクセルが等しい場合、デフォルトとして、ｂが大きい方として選択される。また、いずれのピクセルも部分ピクセルでなければ凝縮動作は作用しない。
【００２９】
統合フィルタは、左側ピクセル・ペアおよび右側ピクセル・ペアを凝縮して、２つの部分ピクセルを生成する。２つの部分ピクセルが残っているならば、フィルタはそれらを凝縮して１つの部分ピクセルを生成するかまたは部分ピクセルをなくす。その時点で、統合は完了し、符号化が実行される。逐次的処理として記述しているが、統合フィルタは、組み合わせ論理回路、ハードウェアＲＯＭまたはソフトウェア照合テーブルを用いる単一パスで実行することができる。
【００３０】
改めて図１１を参照して説明すれば、最初に、左のピクセル・ペア（位置０、位置１）が凝縮される（ステップ１２０２）。次に、右のピクセル・ペア（位置２、位置３）が凝縮される（ステップ１２０３）。これら２つの初期ピクセル・ペアが凝縮された後、残る部分ピクセルは多くとも２つである。１つ以上の部分ピクセルが残っているか否かを判断するため、位置０が部分ピクセルであるか否かを判断するため、位置０が調べられる（ステップ１２０４）。ピクセル０が部分ピクセルであると仮定して、それは残りの部分的ピクセルと凝縮される。先ず、位置２が部分ピクセルであるか否かを判断するため、位置２が調べられる（ステップ１２０５）。ピクセル２が部分ピクセルでなければ、ピクセル０がピクセル３と凝縮される（ステップ１２０６）。ステップ１２０５でピクセル２が部分ピクセルであれば、ピクセル０とピクセル２が凝縮される（ステップ１２０７）。ステップ１２０４でピクセル０が部分ピクセルでなかった場合、ピクセル１は部分ピクセルと仮定され、位置２が部分ピクセルであるか否かを判断するため、位置２が調べられる（ステップ１２０５）。ピクセル２が部分ピクセルでないとすれば、ピクセル１がピクセル３と凝縮される（ステップ１２１０）。ステップ１２０８でピクセル２が部分ピクセルであると判断されれば、ピクセル１とピクセル２が凝縮される（ステップ１２０９）。
【００３１】
このように、本発明の好ましい実施形態において、４つのピクセルは先ず２つのグループに分割される。各グループは以下に述べる凝縮サブルチーンに渡される。凝縮サブルチーンは、多くとも１つの部分ピクセルを戻す。最初の２つのピクセル・ペアを凝縮した後、部分ピクセルであるか否かを判断するため各ピクセルが調べられる。いずれの部分ピクセルも再び凝縮サブルーチンへ渡され、残りの部分ピクセルが凝縮される。
【００３２】
図１２を参照して説明すれば、先ず、凝縮プロシージャの結果、１つの完全ピクセルが生成されるかまたは１つの空のピクセルが生成されるか判断される（ステップ１１０２）。７個を越えるサブピクセルが存在するので１つの完全ピクセルが生成されたと仮定して、次にどちらのピクセルのサブピクセルの数が多いかが判断される（ステップ１１０３）。
【００３３】
ピクセルａがピクセルｂよりサブピクセルを多数持っているとすれば、ｂ=(ａ＋ｂ）−７のサブピクセルとされ（ステップ１１０４）、ａは完全オンとされる（ステップ１１０５）。要約すれば、ピクセルａを完全ピクセルにする十分なサブピクセルがピクセルｂからピクセルａへ移される。同様の方法で、ステップ１１０３で、ピクセルｂのサブピクセルがサブピクセルａより多いと判断されると、ピクセルｂを完全ピクセルにする十分なサブピクセルがピクセルａからピクセルｂへ移される。
【００３４】
最初のステップ１１０２が少くとも１つの空のピクセルが生成されたと判断すると、どちらのピクセルのサブピクセルの数が多いかが判断される（ステップ１１０８）。ピクセルａがサブピクセルを多数有していると判断されると、ｂのサブピクセルのすべてがピクセルａへ移され（ステップ１１０９）、ｂのサブピクセルのすべては削除される（ステップ１１１０）。ステップ１１０８でピクセルｂがサブピクセルを多数有していると判断されると、ａのサブピクセルのすべてがピクセルｂへ移され（ステップ１１１１）、ａのサブピクセルのすべては削除される（ステップ１１１２）。
【００３５】
図７を使用して、本発明の統合手順の１例を示す。図７に示されるように、ピクセル位置７０１は空であり、位置７０２は５個のサブピクセルを持ち、位置７０３は７個のサブピクセルを持ち、ピクセル７０４は３個のサブピクセルを持つ。本発明がこのグループを符号化することを試みる場合、ピクセル７０３は完全に占められるているので、ビットマップで完全に表現される。しかし、２つの部分ピクセル（７０２、７０４）が残る。図６に関連して上述したように、本発明は、１グループにつき２つ以上の部分ピクセルを符号化することができない。従って、図７のグループは統合されなければならない。
【００３６】
図１１の統合プロセスを図７の（Ａ）に適用すれば、最初に、ピクセル７０１および７０２が、凝縮サブルーチン１２０２へ渡される。図１２に示されているように、ピクセル７０１および７０２が７個未満のサブピクセルを有しているかが先ず判断される（ステップ１１０２）。持っていないので、次にどちらのピクセルのサブピクセルが多いかが判断される（ステップ１１０８）。ここで、ピクセル７０２は５つのサブピクセルを有しているので、ｂ（７０２）はａ（７０１）よりサブピクセルの数が多い。ステップ１１１１でピクセル７０１および７０２の内容が結合されピクセルｂに記憶される。また、ピクセルａ（７０２）はゼロにセットされる（ステップ１１１２）。サブルチーンからの戻りに際して、ピクセル７０１および７０２のサブピクセルの内容は不変である点は当業者に理解されるであろう。次に、ピクセル７０３および７０４が凝縮サブルーチン１２０３に渡される。図１２の凝縮サブルチーンの論理に従って、ピクセル７０１および７０２のサブピクセルの内容もまた不変である点は当業者に理解されるであろう。
【００３７】
次に図１１に戻って、位置０が部分ピクセルであるか否かを判断するためテストされる。本例においては、位置０(７０１)は、サブピクセルを全く有していないので、ステップ１２０４の判断は偽（すなわちＮＯ）である。次に、ステップ１２０８で、位置２(７０３)が部分ピクセルであるか否かを判断するためテストされる。ここではピクセル２は完全ピクセルであるので、ピクセル１(７０２)およびピクセル３(７０４)が凝縮サブルーチンへ渡される(ステップ１２１０)。図１２の凝縮サブルーチンにおいて、渡された２つのピクセルのサブピクセルの和が７個より大であるか否かが先ず判断される(ステップ１１０２)。次に、どちらのピクセルのサブピクセル数が多いかが判断される(ステップ１１０３)。この例では、ピクセルａ(７０２)のサブピクセルの数がピクセルｂより多いので、ピクセルｂはステップ１１０４の方程式に従って埋められ、ピクセルａは７個のサブピクセルで完全に埋められる。図７の(Ｂ)は、図１１の統合プロセスの終了結果を示す。
【００３８】
図７に示されている統合プロセスはかなり単純な構成を表す。図８に示されるような一層複雑な構成も処理可能である。図８の（Ａ）に示されるように、ピクセル８０１が２つのサブピクセルを含み、ピクセル８０２が１つのサブピクセルを含み、ピクセル８０３が４つのサブピクセルを含み、ピクセル８０４が３つのサブピクセルを含む。図１１の処理プロセスに従えば、ピクセル８０１および８０２が先ず凝縮サブルーチン１２０２へ渡される。サブルーチンから戻されると、ピクセル８０１は３つのサブピクセルを含みピクセル８０２は空となる。次に、ピクセル８０３および８０４がステップ１２０３で凝縮される。その結果、ピクセル８０３は完全オンを形成する７つのサブピクセルを含み、ピクセル８０４は空となる。凝縮ルーチンから戻された後、図８のピクセル８０３が完全オンとなっているが更に処理が必要か否かを判断するチェックは、図１１の実施形態では行われていない。
【００３９】
そのようなチェックを行うように図１１の実施形態を修正することは当業者によって容易に実施することができよう。図１１の実施形態の処理を継続すれば、位置２(８０３)が７つのサブピクセルを含むので、位置０(８０１)および位置３(８０４)が凝縮サブルーチン１２０６へ渡される。位置３は空であるので変更は行われず、かくしてピクセル集合は図８の（Ｂ）に示されるように完全に統合される。
【００４０】
上記の処理を逐次的に記述したが、上記フィルタ・プロセスを組み合わせ論理回路またはソフトウェア照合テーブルを用いて１回パスで実施することは可能である。部分ピクセル統合および後続の符号化は、その入力オペランドとして４つのピクセルの総和階調度(すなわち０／７ないし７／７）を使用する。従って、上記２つの機能を１回パスで実施する場合、１２ビット入力照合テーブルまたは組合せ論理回路が使用されるであろう。部分ピクセル復号機能は、その入力オペランドのため２つのニブルを持っているので、８ビット入力照合テーブルまたは組合せ論理回路で実施することができる。
【００４１】
図９には、本発明を実現する典型的ハードウェア実施形態が示されている。７つのサブピクセルを含むピクセルの各々が加算器９０２−９０５に提示される。７ビット数は通常１２８の可能な組合せを表現することができるが、図９に示される実施形態では、各ピクセルが順次成長するので各ピクセルは８つの可能な組合せだけを持つ。例えば、加算器９０２は、７個の到来ビットをサブピクセル・セットの数を表現する２進数に変換する。従って、加算器９０２は、セットされた３つのサブピクセルがあるので、２進数３を出力する。同じように、加算器９０３は２進数７を、加算器９０４は２進数４を、加算器９０５は２進数２をそれぞれ出力する。
【００４２】
加算された出力の各々が３ビットの２進数で８個の可能な入力を正確に表現することができることは当業者に理解されることであろう。このようにして、加算器９０２−９０５が結合されると、合計１２ビットが生成される。次に、この１２ビット数、ＲＯＭ９０６におけるアドレスとして使用される。ピクセル集合９０１のデータを使用すると、加算器９０５が下位有効ビットを出力すると仮定すれば、この１２ビット数は、（１６進数表記で）０７Ｅ２である。最後に、ＲＯＭ９０６は、２個のニブルを含む１バイトを出力する。第１のニブルは通常のビットマップ情報を含み、第２のニブルは、前述のように、対応する符号化情報を含む。上記の例は最終的に、ＲＯＭ９０６の位置０７Ｅ２は、６（すなわち０１１Ｏビット）が通常のビットマップで、２（すなわち００１Ｏビット）が部分ピクセル符号化である１６進数６２を含む。図１０は、最初に集合９０１の統合、次に部分ピクセル情報の符号化という離散的ステップを示す。
【００４３】
図１４は、本発明を実行するために使用される論理ステップを示す。特定のピクセル集合が与えられ(ステップ１４０１）、この集合が上述のように統合される（ステップ１４０２）。次に、完全ピクセルがビットマップ・メモリに無修正で記憶される（ステップ１４０３）。最後に、残りの部分ピクセルが符号化され、メモリ１４０４に記憶される。
【００４４】
部分ピクセルの復号化はそのオペランドのため２つのニブルを使用するので、符号化に用いられたものと同じ８ビット入力照合テーブルまたは組合せ論理回路で実施することができる。２ビットを追加して、復号される４個のピクセルの個々のピクセルにアクセスするように構成することも可能である。図１３は、復号器のための１つの可能な実施形態である。データ・メモリ１３０１が、最初のニブルにビットマップ（０１００）を、第２ニブルにサブピクセル符号化(１０１１)を含む８ビット数を出力する。１０２４×７のマトリックスとして示されているＲＯＭ１３０２は２５６×２８とすることもできるが、アプリケーションによっては、個々のピクセルへのアクセスを一層制御された形態で行うことを必要とする。従って、図１３の実施形態は、個々のピクセルの内容にアクセスできるように２ビットを追加使用する。０１００１０１１ビットの入力を所与とすれば、各ピクセルの内容は図１３の１３０３−１３０６に示される通りである。
【００４５】
本明細書に例示していないが、図９および図１３のハードウェアと同等に動作するソフトウェア・プログラムを当業者が生成することができるであろう。また、そのようなプログラムを使用して、４０９６の可能な統合／符号化入力の組み合わせおよび２５６の可能な復号入力の組み合わせに対処できる照合テーブルを作成することも可能である点は明らかであろう。そのような照合テーブルは、ハードウェア実施形態の場合はＲＯＭに、あるいは、ソフトウェア実施形態の場合はプログラムの一部として、記憶されることができる。
【００４６】
画像品質の点である程度の妥協を許容することによって、当業者が本発明の統合プロセスを修正して単純化することは可能であろう。例えば、最大値に関する誤差および位置情報だけを符号化し、最大値以外の情報を破棄することによって、ある１つの集合の中の複数の部分ピクセルを処理することもできるであろう。また別の例として、ある１つの集合内に複数の部分ピクセルがある場合すべての部分ピクセル情報を破棄することもできよう。
【００４７】
更に、ピクセルのより大きい集合のサブセットである複数の部分ピクセルを符号化することも可能であろう。例えば、１２ビット（各４ビットで２つの位置を符号化し、２つの誤差ビット・ペアの計１２ビット）を使用して、１６個のピクセルからなる集合が２つの部分ピクセルを含むこともできる。２つ以上の部分ピクセルが残っていない場合対応する部分ピクセル統合プロセスは終了する。そのような修正の１例が図１５に示されている。オリジナルの１６個のピクセル１５０１が、ビットマップ１５０２に先ず符号化される。位置１にある最初の部分ピクセルの位置が、４ビット（１５０４）に記憶される。第２の部分ピクセルの位置(７)は４ビット(１５０３)に記憶される。各部分ピクセルに関する２つの誤差ビット・ペアが１５０５および１５０６に記憶される。
【００４８】
本発明の特定の実施形態を以上記述したが、本発明の精神を逸脱することなく上記実施形態に種々の変更を行うことができる点は当業者に明らかであろう。
【００４９】
本発明には、例として次のような実施様態が含まれる。
（１）複数のサブピクセルを各々が含む複数のピクセルによって表現される画像を符号化する方法であって、上記複数のピクセルから１つのピクセル集合を定義するステップと、当該ピクセル集合の中の多くとも１つのピクセルが第１の値にセットされたサブピクセルの部分集合を有するように、上記ピクセル集合を統合するステップと、上記第１の値にセットされたすべてのサブピクセルを持つピクセルを第１の識別子によってメモリ上で表し、第２の値にセットされたすべてのサブピクセルを持つピクセルを第２の識別子によって表すステップと、上記多くとも１つのピクセルが存在すればそのピクセルを符号化するステップと、を含む画像符号化方法。
（２）上記メモリに記憶されている上記多くとも１つのピクセルを復号し、上記１つのピクセル集合を取り出すステップを含む、上記（１）に記載の画像符号化方法。
（３）上記ピクセルを識別子によって表すステップが上記集合のビットマップ値をメモリに記憶することを含み、上記ピクセルを符号化するステップが、上記部分集合が上記複数のサブピクセルの半数と等しい場合、上記ビットマップの対応するビットを上記第１の値にセットし、上記部分集合が上記複数のサブピクセルの半数を越えている場合、上記ビットマップの対応するビットを上記第１の値にセットし、上記部分集合が上記複数のサブピクセルの半数未満の場合、上記ビットマップの対応するビットを上記第２の値にセットするステップと、上記メモリに上記集合の上記多くとも１つのピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記多くとも１つのピクセル内で上記第１の値にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、上記（１）に記載の画像符号化方法。
（４）上記ピクセルを識別子によって表すステップが上記集合のビットマップ値をメモリに記憶することを含み、上記ピクセルを符号化するステップが、上記部分集合が上記複数のサブピクセルの半数を越えている場合、上記ビットマップの対応するビットを上記第１の値にセットし、上記部分集合が上記複数のサブピクセルの半数と等しい場合、上記ビットマップの対応するビットを上記第２の値にセットし、上記部分集合が上記複数のサブピクセルの半数未満の場合、上記ビットマップの対応するビットを上記第２の値にセットするステップと、上記メモリに上記集合の上記多くとも１つのピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記多くとも１つのピクセル内で上記第１の値にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、上記（１）に記載の画像符号化方法。
【００５０】
（５）複数のサブピクセルを各々が含む複数のピクセルによって表現される画像を符号化および復号化する方法であって、上記複数のピクセルから１つのピクセル集合を選択するステップと、第１の値にセットされたすべてのサブピクセルを持つ上記集合内のピクセルをメモリ上で第１の識別子によって表し、第２の値にセットされたすべてのサブピクセルを持つ上記集合内のピクセルを第２の識別子によって表すステップと、上記第１の値にセットされた上記複数のサブピクセルの部分集合を持つ部分ピクセルが存在する場合その部分ピクセルについて上記第１の値にセットされたサブピクセルの位置および数を符号化して上記メモリに記憶するステップと、上記メモリに記憶されている上記部分ピクセルを復号するステップと、ピクセルの上記集合を取り出すステップと、を含む画像符号復号方法。
（６）上記ピクセル集合がＭ個のピクセルを含み、 上記画像符号復号方法が、ＮがＭより小であるとして、多くともＮ個のピクセルが残るように上記ピクセル集合を統合するステップを更に含み、上記符号化ステップが上記Ｎ個の部分ピクセルのみを符号化することを含む、上記（５）に記載の画像符号復号方法。
（７）上記画像符号復号方法が、１個の部分ピクセルが残るように上記ピクセル集合を統合するステップを更に含み、上記符号化ステップが上記１個の部分ピクセルのみを符号化することを含む、上記（５）に記載の画像符号復号方法。
（８）上記符号化ステップが、上記集合内の上記部分ピクセルの位置および上記第１の値にセットされた上記サブピクセル数を上記メモリに記憶するステップと、を含む上記（７）に記載の画像符号復号方法。
【００５１】
（９）上記ピクセルを識別子によって表すステップが上記集合のビットマップ値をメモリに記憶することを含み、上記ピクセルを符号化するステップが、上記部分集合が上記複数のサブピクセルの半数を越えている場合、上記ビットマップの対応するビットを上記第１の値にセットし、上記部分集合が上記複数のサブピクセルの半数未満である場合、上記ビットマップの対応するビットを上記第２の値にセットし、上記メモリに上記集合の上記部分ピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記部分ピクセル内で上記第１の値にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、上記（７）に記載の画像符号復号方法。
【００５２】
（１０）上記ピクセルを識別子によって表すステップが上記集合のビットマップ値をメモリに記憶することを含み、上記ピクセルを符号化するステップが、Ｎ個の部分ピクセルの各々毎に、上記部分集合が上記複数のサブピクセルの半数を越えている場合、上記ビットマップの対応するビットを上記第１の値にセットし、上記部分集合が上記複数のサブピクセルの半数未満である場合、上記ビットマップの対応するビットを上記第２の値にセットし、上記メモリに上記集合の上記Ｎ個の部分ピクセルの位置を記憶するステップと、上記対応するビットとの組み合わせで、上記Ｎ個の部分ピクセルの各々において上記第１の値にセットされているサブピクセルの数を示す第３の識別子を上記メモリに記憶するステップと、を更に含む、上記（６）に記載の画像符号復号方法。
【００５３】
【発明の効果】
本発明は、拡張解像度を使用して、所与のハーフトーン画像に関して、通常使用可能なものより７倍の階調度を提供することによって、ハーフトーン化された画像品質を大幅に改善し、しかも、通常の場合に比較してわずかに２倍のビットマップ・メモリを必要とするにすぎないという効果を奏する。
【図面の簡単な説明】
【図１】拡張解像度ハーフトーンのドットの処理様態を示す図式である。
【図２】完全ピクセルの情報の記憶形態を示す図式である。
【図３】ビットマップ・ニブル、サブピクセル誤差および部分ピクセル位置を含む部分ピクセル符号化を示す図式である。
【図４】復号プロセスにおける無修正の完全ピクセルの処理を示す図式である。
【図５】部分ピクセル情報が復号される形態を示す図式である。
【図６】互換性のある拡張解像度ドットの処理様態を示す図式である。
【図７】単純な部分ピクセル統合を示す図式である。
【図８】複雑な部分ピクセル統合を示す図式である。
【図９】本発明の実施形態の符号化部分を実行するハードウェア実施形態のブロック図である。
【図１０】統合および符号化プロセスとその結果の値がＲＯＭに記憶される形態を示す図式である。
【図１１】統合プロセスに関する実施形態を示す流れ図である。
【図１２】図１１の実施形態によって使用されるサブルーチンの流れ図である。
【図１３】本発明の復号化部分を実行するハードウェア実施形態のブロック図である。
【図１４】本発明に従う好ましい実施形態を示す流れ図である。
【図１５】代替実施形態のための、ビットマップ・ニブル、サブピクセル誤差および部分ピクセル位置を含む部分ピクセル符号化を示す図式である。
【符号の説明】
３００、７０２、７０４、８０１、８０２、８０３、８０４  部分ピクセル
３０１、３０２、３０４、７０１、７０３  完全ピクセル
３０３  粗めピクセル
３０５、３０６、１５０３、１５０４  部分ピクセル位置
３０７、３０８、１５０５、１５０６  誤差ビット・ペア
９０１、１５０１  ピクセル集合
９０２、９０３、９０４、９０５  加算器
９０６、１３０２  ＲＯＭ
１３０１  データ・メモリ
１５０２  ビットマップ
【図１】
0003744610.tif 000003
【図２】
0003744610.tif 000004
【図３】
0003744610.tif 000005
【図４】
0003744610.tif 000006
【図５】
0003744610.tif 000007
【図６】
0003744610.tif 000008
【図７】
0003744610.tif 000009
【図８】
0003744610.tif 000010
【図９】
0003744610.tif 000011
【図１０】
0003744610.tif 000012
【図１１】
0003744610.tif 000013
【図１２】
0003744610.tif 000014
【図１３】
0003744610.tif 000015
【図１４】
0003744610.tif 000016
【図１５】
0003744610.tif 000017