JPH03141776A - 画像符号化装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、画像情報の符号化手段に利用するっ特に、中
間調画像を誤差拡散法に基づき二値画像に変換した擬似
中間調画像の符号化手段に関する。

〔概要〕

本発明は、中間調画像を誤差拡散法に基づき生成した擬
似中間調画像データの符号化手段において、 注目画素とその隣接画素との値から注目画素の予測値を
決定し、この予測値と実際の注目画素の値とで予測誤差
信号を生皮してランレングス符号化を行うことにより、 良質の画像を短い伝送時間で伝送することができるよう
にしたものである。

〔従来の技術〕

従来の中間調画像の符号化方法として数多くが知られて
いる。その第１のものは多値符号化方法と呼ばれるもの
で、中間調画像をＡＤ変換してｎビット／画素で表現し
、これを圧縮符号化するものである。その圧縮符号化手
段には各種の手段があり、予測符号化、直交変換符号化
、プロツクトランケーション符号化、ビットプレーン符
号化、ベクトル量子化符号化などが知られている。第２
のものは二値符号化方法であり、まず中間調画像を二値
画像に変換し、さらにこの二値画像を圧縮符号化するも
のである。二値画像に変換された中間調画像を擬似中間
調画像という。

多値符号化と二値符号化とを比較すると、同一の線密度
（サンプリング密度〉で走査した画像では多値符号化の
方が情報量が多く、画質は良い。

一方、二値符号化方法では二値画像に変換した時点で既
に１ビット／画素の情報量に耐磁されており、多値画像
に比較して画質は劣下しているが符号化データ量は少な
く、したがって伝送時間は短かい。

ところで、受信側で画像を再生する記録デノくイスとし
ては、基本的に階調再現の可能な銀塩写真などの記録方
式もあるが、通常はファクシミリ装置や複写機などに用
いられている感熱記録方式、レーザビームプリンタなど
の記録デバイスや印刷機などでは記録デバイスの階調再
現能力は無いかまたは極めて低く、基本的には二値再現
を主としたものが多い。したがって、多値符号化を用い
て良質の画像を伝送しても記録時には二値画像に変換し
て擬似中間調画像として再現することが多いので、最近
二値符号化が多く用いられている。

さて、中間調画像を二値画像に変換する（疑似中間調手
段としても種々のものが知られているが、最も代表的な
ものとしてデイザ法を用いた手段がある。その中でも特
に良く使用されている組織的デイザ法は第６図（ａ）に
示すようにプロ・ツク内の各画素に対し異なる閾値を設
定上この閾値を用いて各画素を二値化する方法である。

一定濃度「７」の均一な画像をデイザ法で二値化して得
られた画像の例を第６図ら）に示す。この例で示される
ように、全体の中の黒画素の数に応じて中間調が擬似的
に表現される。

このようにして得られたデイザ画像をさらに圧縮符号化
する方式として予測符号化法が知られている。予測符号
化法の最も単純な例として、例えば、注目画素をそのｎ
画素（ｎは第６図（ａ）の閾値パターンの周期である第
５図の例ではｎ−４）前の画素と同じと予測する方法が
ある。第６図山）に示すように、ｎ画素前の画素は注目
画素と同じ閾値て二値化されているので、その間に原画
像の濃度変化がなければ二値化された画像における注目
画素はｎ画素前の画素と同じ値であり、したがって多く
の場合前述の予測は的中して予測値と実際の入力画素の
排他的論理和（予測誤差と呼ぶ。）は「０」になる。し
たがって、このようにして得られる予測誤差信号は「０
」が極めて多くて「１」が少ない。このような予測誤差
信号のエントロピは−ｐｌｏｇｐ−（１−ｐ）ｌｏｇ（
１−ｐ）［ｐ　：　ｒ　Ｉ　Ｊの発生確率〕で与えられ
、例えば、ランレングス符号化法（予測誤差「ｌ」の画
素から次の予測誤差「１」の画素までの距離を符号化す
る方法）により前記エントロピに限りなく近く圧縮でき
ることが知られている。実際のデイザ画像の予測符号化
ではさらに複雑な予測が用いられることが多いが、いず
れもデイザ閾値パターンの周期性を用いたものであって
原理的には前記の単純な例と同様である。

一方、擬似中間調画像の生成には誤差拡散法と呼ばれる
方法がある。この方法のアルゴリズムと第７図を参照し
て説明する。ここでは、原画像（中間調画像）は「０」
、ｒｌ／１５」、ｒ２／１５」、「１」の１６値をとる
ものとする。先ず、第１の画素を閾値ｒｌ／２　Ｊで二
値化する。その結果が黒（「１」とする。）であれば、
その画素以降の隣接画素に実際の画素値と「１」の誤差
（「０」〜「１／２」の値）を分散して加える。結果が
白（「０」とする。〉であれば、同様に実際の画素値と
「０」の誤差（「Ｏ」〜ｒｌ／２　Ｊの値）を分散して
加える。次の画素に対しても今加えられた誤差値で修正
された値を閾値ｒｌ／２　Ｊで二値化し、同様に誤差を
分散して隣接画素に加えて行く。第７図は一定濃度「７
／１５」の原画（ａ）に対して第１画素の二値化（ｂ）
、第２画素の二値化（Ｃ）を行った例である。この方法
はデイザ法と比較してデイザパターンの周期性がなく、
濃度変化部分で滑らかな階調変化が得られ解像度の低下
も少ないので、デイザ法よりも良好な画質の擬似中間調
画像が得られる。

〔発明が解決しようとする問題点〕

しかし、誤差拡散法はデイザ画像のような周期性がない
のでデイザ画像に適用された予測符号化法が適応できず
、したがって、効率的な圧縮符号化ができないためにデ
ータ量が多く通信時間が長くなる欠点がある。

本発明は、誤差拡散方法による擬似中間調画像生成に際
し、効率的な圧縮の可能な予測符号化法を利用して良質
な擬似中間調画像を短時間で送信可能にする画像符号化
装置を提供することを目的とする。

〔問題点を解決するための手段〕

本発明は、中間調画像データを誤差拡散法に従う手順で
処理して二値表現された擬似中間調画像データを生成す
る擬似中間調生成部を備えた画像符号化装置において、
上記擬似中間副生Ｔ＆部から与えられる擬似中間調画像
データの注目画素の周辺のあらかじめ定められた位置に
位置する周辺画素のうちの黒画素の個数を計数する計数
手段と、この計数手段の計数した黒画素の個数とこの黒
画素にかかわる周辺画素の個数とに基づきこの周辺画素
にかかわる注目画素が黒画素または白画素のいずれを示
す値の画素であるかを推定し、この推定された画素の値
と遅れて入力される擬似中間調画像データの注目画素の
値との不一致を演算する演算手段と、この演算手段の演
算繕果が不一致を検出した注目画素とこの不一致の次に
不一致を検出した注目画素との間のランレングスを符号
化するランレングス符号化部とを備えたことを特徴とす
る。

〔作用〕

注目画素のあらかじめ定められた周辺位置画素中の黒画
素の数を計数し、得られた黒画素数と注目画素に隣接す
る画素の値とから算術的に定まる関数として注目画素を
予測し、この予測値と入力擬似中間調画像における注目
画素の値の排他的論理和を予測誤差として゛出力し、こ
の予測誤差に基づき中間調画像を圧縮符号化する。

〔実施例〕

以下、本発明の一実施例について図面を参照して説明す
る。この実施例では領域Ｄ　（Ｘ、　　Ｙ）として第５
図に示す画素領域を採用する。第１図は本発明の実施例
のＭ４戊を示す構成図である。

この実施例は、第１図に示すように、原稿を走査し、そ
の画信号をＡＤ変換してディジタル中間調画信号を出力
する走査部ｌと、中間調画信号を誤差拡散法により擬似
中間調に変換する擬似中間調生成部２と、各々擬似中間
調に変換された１ビット画素の画信号を１走査線分遅延
するラインメモリ３および４と、各々擬似中間調生成部
２からの画信号、ラインメモリ３からの画信号およびラ
インメモリ４からの画信号を順次１画素分遅延させるＤ
フリップフロップ５１ないし５５．６１ないし６５．７
１ないし７５と、それぞれＤフリップフロップ５４およ
び５５．６１ないし６５．７１ないし７５に相当する画
素位置の黒画素数を計数する黒画素計数部８１ないし８
３と、Ｄフリップフロップ５４．６２．６３．６４に相
当する画素の値（黒または白）と黒画素計数部８１ない
し８３からの黒画素数との総和に対応して予測値を決定
する算術演算部９と、算術演算部９からの予測値とＤフ
リップフロップ５３からの出力である注目画素との排他
的論理和をとった信号（すなわち予測誤差信号）をラン
レングス符号化する符号化部１０とを備える。第２図に
黒画素計数部８１ないし８３の構成を示す。第１図に示
すように、注目画素（予測しようとしている画素）の値
はＤフリップフロップ５３から出力される。このときに
第８図の領域Ｄ　（Ｘ：　　Ｙ）に相当する画素はＤフ
リップフロップ５４．５５．６１ないし６５．７１ない
し７５の出力である。

すなわち、この実施例は、中間調画像データを誤差拡散
法に従う手順で処理して二値表現された擬似中間調画像
データを生成する擬似中間調生成部２を備え、さらに、
本発明の特徴とする手段として、擬似中間調生成部２か
ら与えられる擬似中間調画像データの注目画素の周辺の
あらかじめ定められた位置に位置する周辺画素のうちの
黒画素の個数を計数する計数手段であるラインメモリ３
．４、Ｄフリップフロップ５１〜５５．６１〜６５．７
１〜７５、黒画素計数部８１．８２．８３と、この計数
手段の計数した黒画素の個数とこの黒画素にかかわる周
辺画素の個数とに基づきこの周辺画素にかかわる注目画
素が黒画素または白画素のいずれを示す値の画素である
かを推定し、この推定された画素の値と遅れて入力され
る擬似中間調画像データの注目画素の値との不一致を演
算する演算手段である算術演算部９と、この演算手段の
演算結果が不一致を検出した注目画素とこの不一致の次
に不一致を検出した注目画素との間のランレングスを符
号化するランレングス符号化部ｌＯとを備える。

はじめに、この発明の詳細な説明する。

先ず、誤差拡散法の原理を説明する。第７図で画素位置
（ｘ、　ｙ）の原画像（中間調画像）での値をｆ（ｘ、
　ｙ）　（０≦ｆ（ｘ、ｙ）≦１）、誤差拡散法によっ
て得られた擬似中間調画像での値をｇ（ｘ、　ｙ）（ｇ
”（ｘ、ｙ）＝Ｏ１１）とすると、ｇ（に、　Ｖ）＝Ｑ
　（ｆ（Ｘ、　　ｙ）　＋Ｅ（Ｘ、　Ｖ））　　式（１
）と表せる。ここでＱ（・）は適当な固定の闇値（通常
は１／２）による二値化関数を示し、Ｅ（Ｘ、　ｙ）は
隣接する先行画素位置（Ｘ−１，ｙ）、（Ｘ−１，ｙ−
１）、（Ｘ、　ｙ−１）（ｘ＋１　、　ｙ−１）の二値
化により発生した誤差の拡散値の総和である。すなわち
、画素位置（Ｘ、　ｙ）の二値化による誤差をｅ（ｘ、
ｙ）＝ｆ（ｘ、ｙ）＋Ｅ（ｘ、　ｙ）−ｇ（ｘ　、　ｙ
）とすれば、 Ｅ（Ｘ、’　ｙ）＝　ａｌｏ　−ｅ（ｘ−１，ｙ）＋　
ａｌｌ　−ｅ（ｘ−ｔ、　ｙ−１）＋　ａｏｌ−ｅ（Ｘ
、　Ｖ　ｌ）＋ａ−ｚ　　Ｉ　ｅ（Ｘ＋ｌ　、　ｙ−１
）式（２） ％式％ は各方向への誤差拡散係数であり、 ａ＋ｏ＋ａ目　＋ａｏ＋＋　ａ−ｚ　＝　１である。表
記の簡便のため式（２）を Ｅ（Ｘ、Ｖ）＝Σａ　−ｅ（ｉ、　ｊ）Ｉｘ＋　ｙｌ 式（２）′ と書くことにする。

さて、画像領域り内の黒画素の数は ２ｇ（ｘ、ｙ）＝Σ（ｆ　（Ｘ、　ｙ）　＋　Ｅ　（ｘ
、　ｙ）　−ｅ（ｘ。

Ｄ　　　　　　　　　　　　　　　Ｄ ｙ） ） ＝Σｆ（ｘ、ｙ）十ΣＥ（Ｘ、　ｙ）−Σｅ（ｘ、　ｙ
）口Ｄ１１ になるが、ΣＥ（Ｘ、　ｙ）−Σｅ＜ｘ、　ｙ）は領域
り内で口０ はＥ（Ｘ、　ｙ）とｅ（ｘ、　ｙ）が相殺し、領域外か
らの拡散誤差流入量Ｅｌと領域外への拡散誤差流出量Ｅ
。

の差（Ｅｒ　　Ｅｏ）になる。領域りが大きくなるに従
い（Ｅｒ　　　Ｅｏ）は「０」に近づく。したがって、
ある程度広い領域りについて見れば２ｇ（ｘ、ｙ）幻Σ
ｆ（ｘ、ｙ） Ｏｆ＋ になり、領域内の黒画素の量によりその部分の平均濃度
が表現される。

次に、圧縮符号化の原理を説明する。前述のごとく、誤
差拡散法における擬似中間調画像の画素ｇ（ｘ、　ｙ）
は式（１）で表わされる。ここでｇ（Ｘ、　’りを予測
するためにはｆ（Ｘ、ｙ）とＥ（Ｘ、　ｙ）を予測すれ
ばよい。画素値Ｒ（ｘ、　ｙ）に対し適当なその周辺領
域Ｄ（Ｘ、　ｙ）をＤ（Ｘ、　ｙ）内の画素はすべて二
値化処理済であるように定めて２ｇ（ｘ、　ｙ）を求め
ると、Ｄ（に＋Ｙ］ 領域Ｄ（ｘ、　ｙ）内と位置（Ｘ、　ｙ）で大きな濃度
変化がなければ、 ｆ（ｘ、ｙ）＝Σｆ　（Ｘ、　ｙ）／Ｎ　（Ｄ）　　　
式（３）％式％ ただし、Ｎ　（Ｄ）は領域Ｄ（Ｘ、　ｙ）内の総画素数
であり、一方、先に述べたようにＤ（ｘ、　ｙ）が十分
に大きければ、 。（′！：：Ａ　（ｘ’　ｙ）””；と、ｆ、、（ｘ　
、　ｙ　）　　　　　　　式（４）であるから、式（３
）および（４）よりｆ（ｘ、ｙ）た２ｇ（ｘ、　ｙ）／
Ｎ　（Ｄ）［＋　（Ｘ、　ｙｌ になる。そこで、ｆ（ｘ、ｙ）の予測値ｆ（ｘ、ｙ）を
ｆ（ｘ、ｙ）＝Σｇａｙ、、　ｙ）／Ｎ　（Ｄ）　　　
式（５）％式％ とする。一方、一般にｅ（ｘ、　ｙ）＝　ｆ　（Ｘ、　
ｙ　）　＋Ｅ（ｘ、　ｙ）〜ｇ（ｘ、ｙ）の平均値ｅ（
ｘ、ｙ）は二値化の闇値をＬＴＨとし、原画像の濃度発
生確率が一様であると仮定すれば、 １−Ｌｔｎ ｇ（ｘ、　Ｖ）＝１のときｅ（ｘ、　ｙ）＝　−ＬＴ）
Ｉ ｇ（ｘ、ｙ）＝０のときｅ（ｘ、ｙ）＝になる。したが
って、式（２）よりＥ（Ｘ、　ｙ）の予測値Ｅ（ｘ、ｙ
）を式（２）′の簡便表記に基づき、と定める。式（１
）、（５）、（６）より、ｇ（ｘ、ｙ）の予測値ｇ（ｘ
、　　　ｙ）　　は、 （Ｌ、Ｔｏ　　ｇ（＋、　Ｊ））　　　　式（７）にな
る。このように定めた予測値ｇ（ｘ、　ｙ）はその定め
方から予測的中率ｐ＞０．５になり、エントロピーｐｌ
ｏｇｐ−（１−ｐ）　ｌｏｇ（１−ｐ）　＜　１になる
ので、予測誤差信号ｇ＜ｘ、　ｙ）０ｇ（ｘ、ｙ）を例
えばランレングス符号化することによりデータ量の削減
が実現できる。

次に、この実施例の動作を第３図のタイミングチャート
を参照して説明する。先ず、各走査線の動作の開始時に
図外のクリア信号によりカウンタ８０２およびすべての
Ｄフリップフロップは「０」クリアされる。したがって
、そのときにカウンタ８０２は対応する各走査線内の領
域Ｄ（Ｘ、　ｙ）内の黒画素の数を示す。さて、画素（
ｍ、　ｎ）の直前の画素＜ｆｉｌ−１，ｎ）が注目画素
位置すなわちＤフリップフロップ５３の出力にある状態
で各走査線の領域Ｄ　（ｍ−１，ｎ）の値が対応する黒
画素計数部８１ないし８３のカウンタ８０２から出力さ
れているとする。この状態で、各走査線の領域Ｄ　（ｍ
−１，ｎ）に含まれかつ領域Ｄ　（ｍ、　ｎ）に含まれ
ない画素が５ｉ２（ｉ　＝　１〜３）に、領域Ｄ＜＋ｒ
＋−１゜ｎ）に含まれずかつ領域Ｄ（ｍ、　ｎ）に含ま
れる画素がＳｉ、　（ｉ＝１〜３）に出力されている。

第１図および第２図に示されていないシフトクロックの
立上りで各画素はＤフリップフロップによりシフトされ
るが、そのときに、第２図に示すように、ＳＩｌ　と３
１□との値が等しければカウンタ８０２のイネーブル端
子ＥＮは「Ｌ」でカウンタの値は変化せず領域り内の走
査線毎の黒画素の数も変化しない。Ｓｉが「１」　（黒
〉でかつＳｉ２が「０」　（白）の場合はカウンタ８０
２のイネーブル端子ＥＮは「Ｈ」であり、また、ＤＮ／
ＵＰ端子はｒＬＪであるので、カウンタ８０２はアップ
カウント動作し「１」だけ増加し、一方、領域り内の黒
画素数も「１」増加する。同様に、Ｓｉ、が「０」　〈
白）、Ｓ１２が「１」（黒）のときはカウンタ８０２の
値、領域り内の黒画素数ともに「１」減少する。このよ
うに、カウンタ８０２は常に注目画素（ｘ、　ｙ）に対
して走査線毎の領域り内の黒画素数を示す。算術演算部
９は領域り内の走査線毎の黒画素数３４〜Ｓ６と注目画
素に隣接する画素（Ｄフリップフロップ５４．６２．６
３および６４の出力）の値とから式（７）の算術演算の
結果の予測値ｇ（ｘ、　ｙ）を発生する。この実施例で
は、この算術演算部９の入力は隣接画素値４本、３４２
本、Ｓ５、Ｓ６各３本の１２本であり、１つのＲＯＭに
あらかじめ演算結果値を書込んでおくことにより実現で
きる。領域りをより大きくとった場合は例えば第３図（
ａ）または（ｂ）に示すように２つのＲＯＭまたは加算
回路とＲＯＭに分離して構成することができる。

〔発明の効果〕

本発明は以上説明したように、注目画素の周辺領域の黒
画素数を計数し、この黒画素数を注目画素の隣接画素の
値とから算術演算により注目画素の予測値を決定し、こ
の予測値と実際の注目画素の値の排他的論理和である予
測誤差信号をランレングス符号化などの既知の圧縮符号
化手段により符号化するので、誤差拡散法による擬似中
間調画像を効率的に圧縮符号化してデータ量を減少し、
その伝送時間を短縮できる効果がある。

【図面の簡単な説明】

第１図は、本発明実施例の構成を示すブロック構成図。 第２図は、第１図の黒画素計数部の詳細を示すｍ成因。 第３図は第１図の算術演算部の構成を示す接続図。 第４図は実施例の動作を示すタイミングチャート。 第５図は本発明の実施例における参照画素領域を示す図
。 第６図、第７図、第８図は従来例の動作を説明する参考
図。 １・・・走査部、２・・・擬似中間調生成部、３．４・
・・ラインメモリ、９・・・算術演算部、１０・・・ラ
ンレングス符号化部、５１〜５５．６１〜６５．７１〜
７５・・・Ｄフリップフロップ、８１〜８３・・・黒画
素計数部、８０１・・・排他的論理和ゲート、８０２・
・・アップダウンカウンク。

Claims (1)

1. 【特許請求の範囲】 １、中間調画像データを誤差拡散法に従う手順で処理し
   て二値表現された擬似中間調画像データを生成する擬似
   中間調生成部を備えた画像符号化装置において、 上記擬似中間調生成部から与えられる擬似中間調画像デ
   ータの注目画素の周辺のあらかじめ定められた位置に位
   置する周辺画素のうちの黒画素の個数を計数する計数手
   段と、 この計数手段の計数した黒画素の個数とこの黒画素にか
   かわる周辺画素の個数とに基づきこの周辺画素にかかわ
   る注目画素が黒画素または白画素のいずれを示す値の画
   素であるかを推定し、この推定された画素の値と遅れて
   入力される擬似中間調画像データの注目画素の値との不
   一致を演算する演算手段と、 この演算手段の演算結果が不一致を検出した注目画素と
   この不一致の次に不一致を検出した注目画素との間のラ
   ンレングスを符号化するランレングス符号化部と を備えたことを特徴とする画像符号化装置。