(57)【特許請求の範囲】
【請求項１】
画素のブロックを圧縮する方法であって、
画素のブロックに編成されたオリジナルの画素を生成する段階と、
それぞれの画素のブロックに関連付けられる画像形式信号を生成する段階であって、前記画像形式信号が、異なる画像形式データタイプのグループから選択された一つのタイプが画素のブロック内に存在するか否か、または、画素のブロックが二つの画像形式データタイプ間の境界を含んでいるか否かを示す段階と、
境界が検出された場合、その境界を形成する二つの画像形式データタイプを判定する段階と、
前記画像形式信号に応答し、二つの圧縮器のうち、前記判定された２つの画像形式データタイプ間の境界を含む画素のブロックの圧縮のために構成された一つの圧縮器を選択して使用する段階と、
前記選択された圧縮器によって画素のブロックを圧縮することにより圧縮ブロック信号を形成する段階とを含み、
圧縮器のうち少なくとも一つを階層的ベクトル量子化に使用し、さらに、前記画像形式データタイプのグループが、ハーフトーン画像データ、コントーン画像データ、テキスト画像データ及びグラフィック画像データを含む、画素のブロックを圧縮する方法。
【請求項２】
前記画像形式データタイプの一つが、ハーフトーン画像データより成る請求項１に記載の方法。
【請求項３】
前記画像形式データタイプの一つが、コントーン画像データより成る請求項１に記載の方法。
【請求項４】
前記画像形式データタイプの一つが、テキスト画像データより成る請求項１に記載の方法。
【請求項５】
前記画像形式データタイプの一つが、グラフィック画像データより成る請求項１に記載の方法。
【請求項６】
誤り信号を生成する段階をさらに含む請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
圧縮すべき画素のブロックが２種類の画像データのうちのいずれであるか、あるいは２種類のデータ間の境界を含んでいるかを判定することによって、ブロックを圧縮するために使用される損失圧縮器が第１または第２の種類のデータ用に、または双方のデータの過渡状態用に最適化されるようにするプロセスである。
【０００２】
【従来の技術】
データを伝送、または記憶しなければならない場合、伝送時間を短縮し、または記憶量を節減するために、通常は先ずデータが圧縮される。これは８ビット画素の４つの色分解からなることができる画像データの場合に特に当てはまる。
【０００３】
圧縮方法の１つは、データ・ブロックを多数のステップで単一のコード語へと縮小することができる“階層的ベクトル量子化(hierarchical vector quantization)”（ＨＶＱ）である。この方法は本明細書に参考文献として引用されている米国特許明細書第５，６０２，５８９号に記載されている。この手順は上記特許の図１ａに記載の数字の例を用いることで最も明解に説明することができる。画素当たり８ビットの、２×４画素のブロックを１つの９ビット数に圧縮する場合を想定してみる。先ず、段階１の参照用テーブル（ＬＵＴ）に各コード語が２画素ビット・パターンと関連している９ビット・コード語を含む各々一対の画素が入力される。テーブルは、入力された画素ビットが正確に整合しないない場合は、代わりに整合に最も近いコード語が出力されるように設定されている。このステップ１では、各々のコード語が入力された２つの画素のビット・パターンとの整合に最も近い４つのコード語が最終的に出力される。正確な整合は不可能である場合が多いので、生来この圧縮にはある程度の損失が伴う。第１段階の出力は４つの９ビットコード語である。
【０００４】
この圧縮量が不十分である場合は、次に、各々が１×２画素のブロックのビット・パターンを表す上記の４つのコード語が段階２の２つのテーブルに入力され、その結果、各々が２×２画素のブロックのビット・パターンを表す総計２つの９ビット出力コード語が生ずる。それでもなお圧縮が不十分である場合は、これらの２つのコード語が段階３のテーブルに入力され、２×４画素のブロックに関連する最終的な出力語が生成される。ここで、この方法が複数の段階が利用され、入力画素が互いに方向性の関係を有しているのでベクトルを含んでいる点で階層的な方法であり、かつ任意の圧縮度を達成するために多数のレベルの処理を実施できる点で量子化された方法であることがわかる。
【０００５】
復元するには、単に各コード語が２５６Ｋ×６４ビットのＬＵＴに入力され、これが８画素のブロック全体のビット・パターンを出力する。
【０００６】
【発明が解決しようとする課題】
ＨＶＱを利用するプリント・システムでは、データが画素のブロック内の損失圧縮器に供給され、各ブロックはテキスト、コントーン（contone)、ハーフトーン等である。受け取られるデータの種類に応じて圧縮器自体を最適に構成できるようにするため、データの前端部は圧縮器に対して、異なる種類のデータ間の境界を判定するマスクと、各マスク内に入るデータようにどのような構成を用いればよいかを指定するプリントのヒントとを供給できる。このシステムでは、マスクのエッジをブロックのエッジと位置合わせしてければならない。
【０００７】
【課題を解決するための手段】
このシテスムは過渡ブロックと呼ぶことができるブロック内に境界があるか否かを判定するシステムによって改良することができる。例えば、テキスト文字とコントーン（逆トーン）の画像との境界がブロックを通る場合は、プリントのヒントが圧縮器に送られ、過渡ブロック用に最適化されたテーブルの値をそのブロック用に選択することができる。それによって、圧縮器がより少ない損失で動作できるので、システムの効率が高まるであろう。
【０００８】
【発明の実施の形態】
基本的ＨＶＱシステムは図１に示したように誤りチャネルを加えることによって改良することができる。上方のチャネルでは、グレースケール・バイト・マップ１６が通常の方法でＨＶＱデコーダ１０に入力され、出力は損失なくＬＺエンコーダ１１で圧縮され、その結果が通常は８−１０ビット語の形式でデコーダに送られる。
【０００９】
加えて、ＨＶＱエンコーダの出力は走査線様式でデコーダ１２に送られ、このデコーダが、損失エンコーダで誤りが誘発されることがあるので、オリジナルのバイト・マップとは異なることがあるバイト・マップのバージョンを生成する。次に２つのバイト・マップが画素毎に減算されて（１３）、誤り項が生成される。これが出力コード語に付加されると、オリジナルのバイト・マップが生成される。この減算は排他的ＯＲを利用しても実行可能であり、この方が簡単かつ迅速であり、符号ビットを必要としない。各々が符号付き数量の８ビット幅またはそれ未満であるこれらの誤り項は次にＬＺエンコーダ１５内で圧縮され、オリジナルの出力と並行してデコーダに送られる。誤り項が大きい程、圧縮率は低くなる。実際には、少量の誤りは視覚的に知覚されない。圧縮率の劣化を制限するため、誤り項を量子化器１４内で少数の例えば３つの最上位ビットに制限することができる。通常は、画素当たりの誤りの量は僅かなＭＳＢ（最上位ビット）で目立つほどには大きくなく、この場合は誤り項は全くない。
【００１０】
量子化された誤りデコーダが図２に示されている。圧縮されたコード語はデコーダ２１内でＬＺ復号され、デコーダ２２内でＬＺ復号化されて、加算器２３の１つの項が生成される。圧縮され、量子化された誤りはデコーダ２４内でＬＺ復号され、加算器２３の別の項として入力される。この加算器の出力は出力ビデオである。加算器２３は符号ビットおよび７つのビットを加算する加算器でもよく、またはエンコーダで誤り語を生成するために用いられた場合は排他的ＯＲでもよい。
【００１１】
図３は単一コード語３１が最上位および最下位部分３２、３３へと分割された場合の、かつ最下位ビットだけが圧縮される構成を示している。この場合は、ビット０から４が損失圧縮器３５へと送出され、一方ビット５から７は送出されない。次に双方とも損失なしのＬＺ圧縮を用いて圧縮され、図４に示したデコーダへと出力される。この場合も、双方のチャネルがＬＺ復元され、一方、ＬＳＢ（最下位ビット）だけがＨＶＱ復号される。次に、結果として生じた２つの部分が排他的論理和され（４４）、復号参照用テーブルに入力される。
【００１２】
図５は単一画素が最下位セグメントと最上位セグヘントとに分離され、かつ各セグメント毎に別個の異なる圧縮プロセスが実行され、最下位ビットの方がより高い圧縮率で圧縮されるシステムである。オリジナルの画素は最上位ビット５２と最下位ビット５３とに分離される。その結果、最も重要である最上位ビットはより低い圧縮率で圧縮され、一方、最下位ビットの圧縮率は高い。プログラム可能な参照用テーブルを利用して、入力された画素を図示した３−５分割以外の任意の２つのセグメントへと分割することもできよう。
【００１３】
図６は図５のエンコーダ用のデコーダである。図５の圧縮された２つの出力はＬＺデコーダ６１、６２に入力され、かつ復号されてＨＶＱ６３、６４に入力される。次に、双方の出力が排他的ＯＲゲート６５に入力されて、画素全体が組立てられる。勿論、エンコーダがそれ以外の何らかのエンコーダの組合せを使用した場合は、デコーダは同じ復号形式を用いるであろう。すなわち、より一般的には、ストリング内のデータ語をより上位の、または下位のビットに分割して２つの平行ストリングを作成することができ、次に下位のビットにはより高い圧縮率での圧縮が行われる、２つの圧縮方法のいずれかを用いて圧縮することができる。
【００１４】
ＨＶＱ圧縮は図７に示すように画像の回転および鏡像写像に容易に適応する。この図には、高さが４画素で幅が１６画素であり、時計回り方向に９０°回転され、鏡像を写像しなければならないオリジナルの画像の例を用いたプロセスが示されている。
【００１５】
ステップ１は８つの８画素セグメントを８つのコード語Ｃw1からＣw8へと縮小する通常の圧縮プロセスである。ステップ２は、コード語を回転させ、鏡像形成された順に再構成するステップである。このハードウェアは、図示のように２番目の語イン、例えばＣw2が３番目の語アウトに接続される配線の形式でよい。ステップ２は各組の配線が異なる回転をもたらす数組の配線を有することができる。最後に、復号ステップ３は参照用テーブルを使用して、適切な向きにある各セグメント毎の画素パターンを作成する。ここでまた数個のテーブルを使用して各種の向きを生成することができる。
【００１６】
プリンタに対してデータの最良のプリント方法を指示するために、ユーザーによって供給されるオリジナルのデータにオリジナルのページ記述言語でプリントのためのヒントを組込んでもよい。例えば、ヒント語は２ビットの長さでよく、後続のデータがテキスト、コントーン(contone)、グラフィック等である４つの可能性の１つを指示する。例えば、プリンタがコンピュータで作成したグラフィックとして発信されたデータを受信した場合は、プリンタはオリジナルのデータが写真の形式でスクリーニングされている場合とは異なるハーフトーンのスクリーンを使用できる。
【００１７】
プリントのヒントは図５に示すようにどのＨＶＱチャネルに付加してもよい。ＨＶＱエンコーダ５４に入力される各々４画素・ブロック毎に、２つの８ビット・バイトに含まれている長さ９ビットの１つのコード語が作成され、従って、最初のバイトには最初の８ビットが含まれ、２番目のバイトには最後のビットが含まれているものと想定してみる。次に２ビットのヒントが付加される。この時点で、各コード語とヒントをプラスした１１ビットがなお２バイト内に含まれている。ＬＺエンコーダは恐らくは長さが２５６バイトのバイト・ストリングを探索し、最新の同一パターンの整合の位置とサイズとを判定する。このストリング内でヒントが一度または二度変化する範囲までは、ヒントがない場合に生ずる圧縮量と比較して圧縮量の減少は僅かである。しかし、この期間中にヒントが変化しない限りは、圧縮量は全く減少しない。その結果、プリントのヒントはＨＶＱ圧縮器の後に、しかし損失なしの圧縮器の前に供給することができ、そうしても圧縮率にはほとんど影響しない。出力側で、コード語がＬＺ復元された後で、しかし復号される前に、ヒントを事後に利用するために抽出することができる。
【００１８】
実際の入力データ・パターンと整合する最良のチャンスを有するコード語と出力データ・パターンを選択することによって、ＨＶＱ圧縮器の損失を更に最小限にすることができる。テキスト画素が４×２画素の群で符号化され、かつ１行の４つの入力画素が黒、ダークグレー、ライトグレーおよび白であり、また入力ビデオがスキャン・イン・テキストであった場合、オリジナルのデータは黒の文字と白の空白との境界であった公算が強く、従って出力画素パターンは黒、黒、白、白であろう。これに対して、オリジナルの入力データがスキャン・インされたコンピュータ作成グラフィックであった場合は、４つの画素は黒から白に密度がスムーズに低下している公算が強い。デコーダの参照用テーブル内のエンコーダコード語とパターンの実際の判定は統計的分析によって決定される。テキストおよびグラフィック文書の代表的な群がテスト・プログラムを通され、各タイプ毎に最良の値が生成される。
【００１９】
境界が画素の入力ブロックを通過する場合に混乱が生じ、この場合はブロック全体にテキスト値もグラフィック値も用いることができない。その解決方法は、このような境界状態のために特別に生成された第３組のコード語とパターンとを供給することである。この場合、テキストとグラフィックの双方を含む文書セットが分析されて、１組のパターンが作成され、これは境界の混合状態がブロック内にあるものと判定された場合に利用されよう。
【００２０】
境界状態はプリントのヒントを観察することによって検出される。例えば、方形のスキャン・イン画像は標準的にはテキストのページにそのｘ，ｙ座標によって位置決めされる。ラスタ出力スキャナ・ビームが座標内にある場合は、プリントのヒントはプリンタに対して、どのコード語、参照用テーブルの項目、およびハーフトーン・スクリーンを使用すべきかを指示する。ヒントが例えばブロック内で画像からテキストに変化した場合は、エンコーダはブロック内に境界が存在することを認識する。
【００２１】
いずれの場合もブロックのサイズは保持されなければならない。図８はテキストからコントーンへの移行の例を示している。ＨＶＱエンコーダでは異なる種類のデータ用に異なるブロック・サイズを用いることができるので、ここではテキスト用のブロック・サイズはエッジをより細密にできるように２×２画素として示されており、一方、コントーン用のブロック・サイズは圧縮率を高めることができるように４×２画素として示されている。
【００２２】
境界が２×２画素のブロック内にある場合は、このブロックは境界値を用いて符号化され、かつ復号される。加えて、画素８１のような境界の右にあるいずれかのコントーン画素も必要ならば境界画素として処理されるので、境界線の右にある残りの全ての画素は４×２画素のブロック内にくる。同様にして、テキストおよびコントーンの４×２画素のブロックの境界を示す図９では、２×２画素の境界ブロックが一対で用いられるので、残りのブロックすべては４×２画素のブロックとなる。
【図面の簡単な説明】
【図１】  並列の誤りチャネルを有するＨＶＱエンコーダである。
【図２】  図１の構成用のデコーダである。
【図３】  最上位ビットと最下位ビットとに分割された画素を符号化するための１チャネル構成図である。
【図４】  最上位ビットと最下位ビットとに分割された画素を復号するための１チャネル構成図である。
【図５】  最上位ビットと最下位ビットとに分割された画素を符号化するための２チャネル構成図である。
【図６】  図５のエンコーダ用のデコーダである。
【図７】  ＨＶＱ圧縮を利用して画像を回転写像、もしくは鏡像写像する３つのステップを示している。
【図８】  サイズが異なるブロック間の境界を示している。
【図９】  サイズが同じブロック間の境界を示している。
【符号の説明】
１０  ＨＶＱデコーダ、１１  ＬＺエンコーダ、１２  デコーダ、１３  減算器、１６  グレースケール・バイト・マップ、２１  デコーダ、２２  デコーダ、２３  加算器、２４  デコーダ、３１  単一コード語、３２  最上位部分、３３最下位部分、３４，３６  ＬＺエンコーダ、３５  圧縮器、４１，４２  ＬＺエンコーダ、４３  ＨＶＱ  デコーダ、４４  排他的ＯＲゲート、５２  最上位ビット、５３  最下位ビット、５４  ＨＶＱエンコーダ、６１  ＬＺデコーダ、６２  ＬＺデコーダ、６３  ＨＶＱ、６４  ＨＶＱ、６５  排他的ＯＲゲート
【図１】
0004216956.tif 000002
【図２】
0004216956.tif 000003
【図３】
0004216956.tif 000004
【図４】
0004216956.tif 000005
【図５】
0004216956.tif 000006
【図６】
0004216956.tif 000007
【図７】
0004216956.tif 000008
【図８】
0004216956.tif 000009
【図９】
0004216956.tif 000010