JPH08204971A - 予測符号化と誤差拡散を用いた画像圧縮方法 - Google Patents

Abstract

(57)【要約】 【課題】 ランの短い誤差拡散画像を効率的に圧縮する
ことができなかった。 【解決手段】 損失のない状態で画像圧縮を行う方法に
おいて、複数の誤差拡散信号からなる誤差拡散画像を予
測を行いながら予測画像に符号化するステップと、前記
誤差拡散画像と前記予測画像とを比較するステップと、
前記比較により複数の予測誤差を生じさせるステップ
と、ランレングス符号化によって前記複数の予測誤差を
圧縮するステップを含む。画素値ではなく誤差を予測符
号化する。予測とランレングス符号化の有効な連携が実
現される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、誤差拡散により作
られた画像をランレングス符号化手法によって符号化す
る、損失のない画像圧縮方法に関するものである。

【０００２】

【従来の技術】データ圧縮装置は、画像データを記憶
し、伝達するのにかかる費用を削減するために使用され
てきた。圧縮手法としていくつかの技術が提案されてい
る。代表的な圧縮手法は、まず画像を画素単位の画素値
によって表現し、同じ画素値が連続する個所について圧
縮処理を施すことにより、データの総量を削減する。

【０００３】しかしながら、従来の圧縮手法は、入力画
像が誤差拡散手法によって予めハーフトーン処理されて
いる場合（すなわち画素値を量子化して表現した場合）
には、ほとんど圧縮効果を期待することができなかっ
た。ここで、誤差拡散手法による画像の表現方法を概説
する。

【０００４】一般的な誤差拡散は以下のステップで画像
を量子化する（ここでは２値化を例にとっている）。

【０００５】（１）各画素は０〜１の任意の所期画素値
を持つものとする。０は黒、１は白である。入力された
原画像を順に走査し、所期画素値が０．５未満なら０に
変更する。０．５以上なら１に変更する。この過程を画
像の最終画素まで通して行う。ここでは、０．５を量子
化のしきい値、１を量子化の幅としている。

【０００６】（２）このとき、例えば画素Ｘの所期画素
値が１／４であるとすれば、この画素値を０を量子化し
て変更するとともに、量子化に伴う誤差（以下「量子化
誤差」または単に「誤差」という）を−１／４と定義す
る。変更後の画素値は１／４だけ暗すぎるという意味で
ある。もちろん、画素値を１に変更するとともに、誤差
を＋３／４と定義してもよい。誤差は−１〜１の範囲の
値をとる。誤差は画素と関連づけて記憶しておく。

【０００７】（３）画素の誤差は隣接する画素間で相殺
する場合がある。例えば、上記の画素Ｘの隣に所期画素
値３／４、変換後の画素値が１となる画素Ｙがあるとす
る。画素Ｙの誤差は＋１／４であるから、両者の誤差の
和は０となる。従って、画素Ｘの画素値を０、画素Ｙの
画素値を１としてしまっても、全体的な明るさは影響を
受けず、ほぼ良好な画像が得られる。

【０００８】（４）逆にいえば、隣接する画素間で誤差
が相殺されるように修正することにより、良好な画像を
得ることができる。例えば、画素Ｘの周囲の画素の誤差
総和が０の場合、これが＋１／４となるよう、＋１／４
を周囲の画素に適切に配分する。これを「誤差拡散」と
いう。

【０００９】（５）誤差拡散の際の分配比は試行錯誤に
よって実験的に定められる。一例して、画像を左上から
ライン毎に順次走査する場合、前記画素Ｘの誤差を周囲
の４つの画素（これらは走査前）に、次の重み付けで分
配する。この操作を単に「修正」という。ここでは画素
Ｘの座標を（ｍ，ｎ）とする（ｍはライン右方向に増
え、ｎはライン下方向に増える）。

【００１０】 ・右の画素（ｍ＋１，ｎ）に対して７／１６ ・左下の画素（ｍ−１，ｎ＋１）に対して３／１６ ・真下の画素（ｍ，ｎ＋１）に対して５／１６ ・右下の画素（ｍ＋１，ｎ＋１）に対して１／１６ （６）こうしてある画素の誤差が周囲の画素に拡散さ
れ、誤差拡散画像が得られる。

【００１１】

【発明が解決しようとする課題】誤差拡散は、デジタル
ハーフトーン処理で大切な技術であり、優れた品質の画
像を生みだす。しかし、処理によって生じる不規則の高
周波ノイズパターンのため、誤差拡散によって得られた
画像（以下「誤差拡散画像」という）を圧縮することは
非常に困難である。例えば、ファクシミリ操作で使われ
るＣＣＩＴＴグループ３やグループ４フォーマットとい
った、従来のランレングスに基づく手法は、誤差拡散画
像の主要部分を占める短いランレングスに適切に対処す
ることができないので、誤差拡散画像の圧縮には向かな
い。

【００１２】従って、本発明の目的は、画像情報を失う
ことなく、誤差拡散画像を効率的に圧縮することにあ
る。このとき予測符号化手法を使用する。本発明は、損
失のない画像圧縮を実現するためランレングス符号化手
法を使い、予測を行いながら誤差拡散画像を符号化す
る。

【００１３】

【課題を解決するための手段】本発明は、損失のない状
態で画像圧縮を行う方法において、複数の誤差拡散信号
からなる誤差拡散画像を、予測を行いながら予測画像に
符号化するステップと、前記誤差拡散画像と前記予測画
像とを比較するステップと、前記比較により複数の予測
誤差を生じさせるステップと、ランレングス符号化によ
って前記複数の予測誤差を圧縮するステップと、を含む
ことを特徴とする。

【００１４】本発明は、予測を行いながら、誤差拡散画
像を転送等の方法で受信器または復号器に送ることので
きるランレングス符号化された誤差信号に符号化する。

【００１５】

【発明の実施の形態】特に表示のないかぎり、以後「信
号」という表現は、個別信号と、複数の個別信号から構
成される信号に対して、区別なしで使われるものとす
る。本明細書では、複数の個別信号の集合によって所定
の画像が表現されるものである。

【００１６】図１は本発明の圧縮方法を実行する基本装
置の例を示している。本実施形態では、誤差拡散画像自
体とその画像の生成過程で得られた誤差情報から後続の
画像の誤差を予測し、これを符号化する点に特徴があ
る。これらの情報を使用することで、損失のない符号化
と復号が可能になる。

【００１７】同図に示されるように、誤差拡散画像は、
ポイント１で圧縮器２の入力として受信される。その画
像は、通常１画素あたり１ないし２ビットで表される複
数の信号ｂ（ｍ，ｎ）（以後ｂと表記）から成ってい
る。すなわちｂは量子化値をとる。

【００１８】圧縮器２は、予測器等の予測回路３、比較
回路または減算回路４、およびランレングス符号化手段
すなわち符号化器５から成っている。圧縮器２はまた、
比較回路４の一部として、比較回路４の比較結果に基づ
く、複数の予測誤差６を発生する回路を含んでいる。信
号ｂは、予測回路３と比較回路４に入力される。予測回
路３は、前回の量子化誤差ｅ^* （ｍ−ｉ，ｎ−ｊ）の記
憶値および前回の信号ｂ（ｍ−ｉ，ｎ−ｊ）の平均値に
基づいて、後述の予測信号ｂ^* （ｍ，ｎ）（以後ｂ^* と
表記）を発生する。このｂ^* も量子化値をとる。なお、
ｉとｊは周辺画素の位置を示すインデックスである。

【００１９】信号ｂおよび信号ｂ^* は、比較回路４に入
力される。この回路は、予測画像と誤差拡散画像を比較
することにより、複数の予測誤差Ｅ（ｍ，ｎ）（以後Ｅ
と表記）を発生する。後述のように、予測誤差は予測画
像を誤差拡散画像から引くことにより求められる。

【００２０】予測誤差は、ポイント７で出力され、符号
化器５に入力される。従って、誤差拡散信号（すなわち
画像）と予測画像の差分または誤差だけが、ポイント８
に転送される。

【００２１】図２（Ａ）と（Ｂ）は、図１に示される圧
縮器２の動作を示すフローチャートである。まず、誤差
拡散信号ｂが、ステップＳ５０で圧縮器２に入力され
る。ステップＳ１００では、前回の予測信号を修正して
得られる予測信号（以下「修正予測信号」という）ｉ^*
_mod （ｍ，ｎ）（以後ｉ^* _mod ）が下式により予測回路
３で計算される。^* は評価値または予測値を表し、ａ
（ｉ，ｊ）は、誤差拡散に使われる重み付けの値（すな
わち誤差の分配比）を表す。ｂ、ｂ^* とは異なり、ｉ^*
は量子化値ではなく０〜１の任意の値をとる点に注意す
べきである。式（１）の右辺の２項は、過去の画素の組
（対象画素とその周辺画素）の前回の誤差拡散信号の平
均と、重み付けされた前回の量子化誤差の総和をそれぞ
れ表している。

【００２２】 （１） ｉ^* _mod （ｍ，ｎ）＝ ｉ^* （ｍ，ｎ）＋Σａ（ｉ，ｊ）ｅ^* （ｍ−ｉ，ｎ−ｊ） 右辺の２つの値は、圧縮器２に内蔵されるか、または外
部に取付けられるメモリーまたは記憶媒体（図１に図示
せず）に順次記憶されていく。

【００２３】一旦修正予測信号ｉ^* _mod が決められる
と、次にステップＳ２００で、ｉ^* _{mo d} の量子化値から
ｂ^* が予測される。数学的には、予測信号ｂ^* が、次の
式で計算される。

【００２４】 （２） ｂ^* （ｍ，ｎ）＝Ｑ［ｉ^* _mod （ｍ，ｎ）］ ここで、Ｑは量子化の演算を表す。

【００２５】ｂ^* が求められると、予測誤差Ｅが次のよ
うに計算される。

【００２６】 （３） Ｅ（ｍ，ｎ）＝ｂ（ｍ，ｎ）−ｂ^* （ｍ，ｎ） 比較の結果、ステップＳ３００で、比較回路４により、
画素ごとに複数の誤差が生じる。もしこのような比較で
予測誤差Ｅがゼロになった場合は、予測回路３が正しい
信号を予測したことになり、ｉ^* _mod を調整する必要が
ない。

【００２７】一方、このような比較でＥがゼロに等しく
ない場合は、ｉ^* _mod をステップ５１０で、次の２通り
の方法で調整しなければならない。

【００２８】（４ａ） Ｅ（ｍ，ｎ）＞０ならｉ^* _mod
＝｛ｂ（ｍ，ｎ）の量子化の幅における所定の最小値｝ （４ｂ） Ｅ（ｍ，ｎ）＜０ならｉ^* _mod ＝｛ｂ（ｍ，
ｎ）の量子化の幅における所定の最大値｝ 例えば、もし０．５が量子化のしきい値として使用され
る場合は、式（４ａ）に対応する最小値は、０．５１
（この場合ｂ＝１となり、量子化の幅は０．５より大き
い任意の数）等、０．５より大きくなければならない。
同様に、最大値は、０．４９（この場合ｂ＝０となり、
量子化間隔は０．５より小さい任意の数）等、０．５よ
り小さくなければならない。

【００２９】実際の調整は、調整回路によって実行され
るが、この調整回路は予測回路３の一部として用意され
てもよい。

【００３０】式（４ａ）または（４ｂ）のどちらかで、
最終的に新たな予測量子化誤差ｅ^*（ｍ，ｎ）（以後ｅ
^* ）が予測回路３により計算され、記憶されなければな
らない。この量子化誤差は次式で求められる。

【００３１】 （５） ｅ^* （ｍ，ｎ）＝ｉ^* _mod （ｍ，ｎ）−ｂ（ｍ，ｎ） この現在の予測量子化誤差はｅ^* 、次の誤差拡散が予測
回路３に入力されるとき、新たな修正予測信号を計算す
るためメモリに記憶される。

【００３２】予測誤差が発生させられると、それは図１
のポイント７に出力され、最終的にランレングス符号化
器５に入力される。

【００３３】通常、誤差拡散信号は短い「ランレング
ス」（ここでは同じ状態が連続する長さをいう）を有す
る。ランレングスは、連続的に符号化された画素のグル
ープで表される。すなわち、例えば１０個の白い画素は
２進法の「１」の列として表現される。予測回路３を使
用することによって、誤差拡散信号のランレングスを延
ばすことができる。

【００３４】ランレングス符号化器５を使用することに
より、この場合、例えば１ｘ、１ｘ、１ｘ…（ここでｘ
は無誤差）、と１つずつ１０の「誤差なし」を転送する
のではなく、列をなす１０の「誤差なし」（１０の白画
素とは対照的に）を１０ｘと示すコードを使うことかで
きる。このため、ランレングスを延ばすことが可能とな
り、これを転送またはその他の方法で出力することがで
きる。従って、誤差が全く発生しない場合は、「誤差な
し」の長い連続的流れが、ランレングス符号化器５に入
力されることになる。この連続的流れが、ランレングス
符号化器５によって符号化され、ポイント８で「誤差な
し」を表す１つのコードとして出力される。

【００３５】図３は、本発明の一実施形態による、図１
に示された装置から転送されるランレングス符号化画像
を受信し、復号し、伸張する装置のブロック図を示して
いる。

【００３６】図３に示されているように、伸張器９はラ
ンレングス復号手段すなわち復号器１１と、予測符号化
回路すなわち受信側の予測回路１２、さらに加算手段す
なわち加算回路１３から成っている。

【００３７】ランレングス復号器１１は、ポイント１０
からランレングス符号化された予測誤差信号を入力し、
これを復号して複数の予測信号としてポイント１４に出
力する。

【００３８】予測回路１２は、ポイント１５で加算回路
１３より出力された復号済みの信号を入力し、複数の予
測信号をポイント１６に出力する。これらの予測信号
は、予測回路１２内で修正予測信号ｉ^* _mod を量子化す
ることによって計算される。この信号、すなわちｉ^*
_mod の方は、好ましくは予測回路１２以外の場所にある
受信器メモリまたは記憶装置（図示せず）に記憶された
前回の受信器量子化誤差および周辺画素を含む過去の復
号信号の誤差の平均から式（１）および（２）と同様の
方法に従って計算される。受信器メモリまたは記憶装置
は、伸張器９の一部であってもよいし、外部に存在して
もよい。

【００３９】ポイント１６からの予測信号とポイント１
４からの予測誤差は、次に、加算回路１３に入力され、
その２つの信号が加算される。このようにして、予測回
路１２からの各予測信号は、ランレングス復号器１１に
よって復号された各予測誤差にそれぞれ加算される。圧
縮器２の場合と同様に、任意の時点で予測誤差が存在し
ない場合は、予測信号は、加算回路１３からの復号信号
として出力され、ポイント１７で画像を形成する。もし
誤差が存在する場合は、それに対応する修正予測信号が
式（４）と同様の方法で調整される。

【００４０】復号された画像は、プリンタ１８またはそ
の他の再生装置に出力させることが可能である。

【００４１】次の画像または信号を復号し、正しく予測
するため、現在の受信器量子化誤差が伸張器９内で計算
される。この誤差は受信器メモリに記憶される。

【００４２】同様に、図４（Ａ）、（Ｂ）、（Ｃ）は、
図３に示された装置の伸張操作を示すものである。伸張
器の操作のステップ（Ｓ１０５０からＳ１６００まで）
は、圧縮器の操作と同様であるが、ステップＳ１２００
で、復号出力ｂ’（ｍ，ｎ）が、最初に復号誤差から次
式で計算されることが異なっている。

【００４３】 ｂ’（ｍ，ｎ）＝Ｅ（ｍ，ｎ）＋ｂ^* （ｍ，ｎ）

【００４４】

【発明の効果】本発明によれば、画像情報を失うことな
く、誤差拡散画像を効率的に圧縮することができる。こ
のとき、ランレングス符号化手法を有効に活用する点に
特徴がある。

【図面の簡単な説明】

【図１】 実施形態の圧縮手法を使った装置のブロック
図である。

【図２】 （Ａ）および（Ｂ）は、本発明の実施形態の
圧縮手法のフローチャートである。

【図３】 本発明の実施形態の伸張手法を使った装置の
ブロック図である。

【図４】 （Ａ）、（Ｂ）および（Ｃ）は、本発明の実
施形態の伸張手法のフローチャートである。

【符号の説明】

２ 圧縮器、３，１２ 予測回路、４ 比較回路、５
ランレングス符号化手段、９ 伸張器、１１ ランレン
グス復号手段、１３ 加算手段。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 損失のない状態で画像圧縮を行う方法に
   おいて、 複数の誤差拡散信号からなる誤差拡散画像を、予測を行
   いながら予測画像に符号化するステップと、 前記誤差拡散画像と前記予測画像とを比較するステップ
   と、 前記比較により複数の予測誤差を生じさせるステップ
   と、 ランレングス符号化によって前記複数の予測誤差を圧縮
   するステップと、 を含むことを特徴とする画像圧縮方法。