JPH0834545B2

JPH0834545B2 - 画像デ−タ符号化装置

Info

Publication number: JPH0834545B2
Application number: JP61219309A
Authority: JP
Inventors: 佳弘横山; 康雄黒須; 宏一岡澤
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1986-09-19
Filing date: 1986-09-19
Publication date: 1996-03-29
Anticipated expiration: 2011-03-29
Also published as: JPS6376579A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は画像データの符号化および圧縮に係り、特に
ファクシミリ装置等で使用されているランレングス符号
化処理の高速化に好適な画像データ符号化装置の回路に
関する。

〔従来の技術〕

画像データの圧縮符号化においては、従来多くの方式
が提案されている。それらの中で最も基本的な方式は、
画像データが白画素から黒画素あるいは黒画素から白画
素に変化する点（変化点）間の画素数（ランレングス）
を符号化するものである。

第２図はランレングス符号化の一例である。画像デー
タ201の走査線205を符号化する場合、黒画素202は黒画
素が１点であるのでランレングスが１であり、２進符号
010に符号化する。また、白画素203から白画素204まで
は白画素が５点あるのでランレングスが５であり、２進
符号1100に符号化する。従って、黒画素202から白画素2
04までの２進符号は２つを結合して0101100となる。こ
こでは黒画素ランレングス１の２進符号を010とした
が、符号化の規格によって様々な符号となる。

ランレングス符号の代表的なものにはファクシミリで
使用されているMH（モディファイドホフマン:Modifie
d Huffman）符号がある。

ランレングス符号化装置の代表的な構成を第３図に示
す。一般的にランレングス符号化装置は画像データのラ
ンレングスを計数する部分と符号テーブルを用いて算出
したランレングスを符号に変換する部分から成る。第３
図において、パラレル／シリアル変換回路101、１ビッ
ト変化点検出回路102、ランレングスカウンタ301がラン
レングスを計数する部分であり、符号発生回路106がラ
ンレングスを符号に変換する部分である。

画像データが８ビットパラレルの形式で供給される場
合、最初にパラレル／シリアル変換回路101で１ビット
シリアルデータに変換する。これは第２図において画素
列206の左から右へ１点ずつ画素を調べて行くためであ
る。もちろん、最初から１ビットシリアルの形式で画像
データが供給される場合はパラレル／シリアル変換回路
101は不要である。

１ビット変化点検出回路102は１ビットシリアルの画
像データを入力し、ある点の画素の色と次の点の画素の
色を比較することにより変化点を検出する。これは第２
図において黒画素202と次の白画素203の色を比較し、黒
画素202と白画素203の間の変化点を検出するというもの
である。

ランレングスカウンタ301はパラレル／シリアル変換
回路101のシリアルデータ出力に同期して計数を行う。
すなわち、１画素供給するタイミングで１ずつカウント
アップする。また、１ビット変化点検出回路102より変
化点検出の信号を受けると、それまでの計数結果である
ランレングスを符号発生回路106へ送り、次の計数のた
めにカウンタを０または１に初期化する。

符号発生回路106はランレングスカウンタ301からラン
レングスを受け取ると、その値に対応した符号を符号テ
ーブルより求めて出力する。

従来、ランレングス符号化装置は主にファクシミリ装
置に使用されてきた。これまでのファクシミリ装置では
回線速度や画像データの読み取り速度が遅いためランレ
ングス符号化装置の高速化はほとんど行われてこなかっ
た。ところが最近では高速ファクシミリ装置や画像ファ
イリング装置の登場によりランレングス符号化装置の高
速化も必要となってきている。

このような状況の中で特開昭59−58971号公報のよう
に、ランレングスを計数する部分の高速化を図るものが
現われている。これは第３図のパラレル／シリアル変換
回路101と１ビット変化点検出回路102を特殊な回路に変
更したものである。その効果は、与えられた８ビットパ
ラレル画像データ内の１つの変化点を検出するために、
第３図の構成では１ビットシリアルデータに変換するの
で最小１サイクルから最大８サイクル必要とするのに対
して、特殊な回路を用いることにより変化点の位置にか
かわらず常に１サイクルを必要とするだけである。

その具体的な構成はパラレル／シリアル変換回路がな
く、与えられた８ビットパラレル画像データの各ビット
に対して８個の１ビット変化点検出回路を備えることに
より一度にすべての変化点を検出する。このようにして
一度にすべての変化点を検出してしまうと、変化点間の
ランレングスを計数することができないので、テキサス
インスツルメント社製TTL−IC（SN74LS148）のようなプ
ライオリティエンコーダという回路を用い、画像データ
の左方優先で変化点の８ビット内の位置を１つずつ算出
している。このプライオリティエンコーダは組合せ回路
のみで構成されており、ゲート遅延を伴うだけであるの
で、変化点の位置を画像データの左側から常に１サイク
ルで算出できる。

以上のようにランレングスを計数する画像データ処理
部を高速化するのは、画像データの圧縮のために符号化
しており、画像データ量が符号データ量より多く、高速
化の効果が大きいからである。

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

上記従来技術の中で第３図の構成は画像データを１画
素ずつ処理しているので、符号化の高速化は回路の高速
化により１サイクルの処理時間を短縮するしかないが、
回路の高速化は素子技術等の限界により制限されてしま
う。また、特開昭59−58971号公報の手段は与えられた
８ビットパラレル画像データ内の処理は非常に高速であ
るが、更に高速化を図るために処理のデータ幅を32ビッ
ト、64ビットと広げて行くには回路規模が増加し過ぎる
という問題点があった。これはプライオリティエンコー
ダ内の回路で、与えられた複数ビットのデータに対して
優先順位を付けるため、ある点を決定するのにそれより
優先順位の高い点の信号をすべて使用するからである。

本発明の目的は第３図の構成に簡単な回路を追加し、
処理データ幅を増加させてもプライオリティエンコーダ
のように回路規模を増加させず、それに近い高速化を行
うことにある。

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

上記目的はパラレル／シリアル変換回路の前段に2ⁿビ
ット変化点検出回路、2ⁿ⁺¹ビット変化点検出回路、2ⁿ⁺²
ビット変化点検出回路を設けるとともに、ランレングス
カウンタを下位２進ｎ桁と中位２進１桁（ｎ＋１桁目）
と中位２進１桁（ｎ＋２桁目）とそれより上の桁（ｎ＋
３桁目以上）に分離し、中位２進１桁（ｎ＋１桁目）の
カウンタは下位２進ｎ桁のキャリーあるいは2ⁿビット変
化点検出回路の出力によりカウントアップでき、中位２
進１桁（ｎ＋２桁目）のカウンタは中位２進１桁（ｎ＋
１桁目）のキャリーあるいは2ⁿ⁺¹ビット変化点検出回路
の出力によりカウントアップでき、上の桁（ｎ＋３桁目
以上）のカウンタは中位２進１桁（ｎ＋２桁目）のキャ
リーあるいは2ⁿ⁺²ビット変化点検出回路の出力によりカ
ウントアップできるようにすることにより達成される。

１ビット変化点検出回路が１ビットシリアル画素デー
タを入力し、連続する２画素の色を調べて変化点を検出
するのに対して、2ⁿビット変化点検出回路は2ⁿビットパ
ラレル画像データを入力し、連続する2ⁿ画素内の変化点
を検出する。ただし、2ⁿ画素内の変化点の存在を示すだ
けであり、変化点の位置は特定できない。

〔作用〕

第４図は一走査線の画素列を表わしたものである。こ
こで2ⁿ⁺²を８だとする。また、説明を単純にするため、
2ⁿビットと2ⁿ⁺¹ビットの変化点検出器および中位２進１
桁（ｎ＋１桁目とｎ＋２桁目）のカウンタはないものと
する。ここで2ⁿを８だとする。８ビットパラレル画像デ
ータとして８画素データ401が入力されると、８ビット
変化点検出回路は白画素405の前の変化点を検出する。
８画素内に変化点が存在する場合はランレングスカウン
タの上位桁をカウントアップせず、第３図の構成と同じ
動作を行い、８サイクルで処理する。

次の８画素データ402が入力されると８ビット変化点
検出回路は変化点がないのでランレングスカウンタの上
位桁をカウントアップする信号を出す。この上位桁の最
下位は２の３乗すなわち８を表わしているのでランレン
グスカウンタに８を加え、８画素を１サイクルで処理し
たことになる。このときランレングスカウンタの下位３
桁は停止する。

８画素データ403までは８画素データ402と同様に処理
し、各８画素を１サイクルで処理する。

そして８画素データ404が入力されると、８ビット変
化点検出回路は白画素406の後の変化点を検出し、８画
素データ401と同様に一画素ずつ処理する。

結局、白画素405から白画素406までのランレングスは
90であり、第３図の構成では91サイクルで処理するのに
対して本発明では21サイクルで処理する。

また、通常の文書等を画像データとした場合、画像デ
ータ内に空白の部分が多いことから、かなりの高速化が
期待できる。

〔実施例〕

以下、本発明の一実施例を説明する。

第１図は本実施例の動作原理を説明するためのランレ
ングス符号化装置のブロック図である。説明を単純にす
るため、2ⁿビットと2ⁿ⁺¹ビットの変化点検出器および中
位２進１桁（ｎ＋１桁目とｎ＋２桁目）のカウンタはな
いものとする。

第３図のランレングス符号化装置のパラレル／シリア
ル変換回路101の前に８ビット変化点検出回路100を加
え、ランレングスカウンタ301を９ビットカウンタ103と
３ビットカウンタ104に分け、各々簡単な制御回路で接
続している。本実施例では2ⁿを８とし、上位桁のカウン
タを９ビット、ランレングス値を12ビットとして4096画
素まで対応した。

第５図は一走査線の画素列とその処理タイミングを示
した図である。なお、ここではビット桁位置を明確にす
るためランレングスカウンタ値として16進数を使用す
る。

黒画素501まで符号化が終了しており、白画素502より
符号化する。最初にスタート信号が入力されるとランレ
ングスカウンタを１からカウントアップする。ここでラ
ンレングス０は白画素502が黒であることを意味し矛盾
するので、ランレングスカウンタの初期値は１である。
もし白画素503が黒であるならば、スタート信号の入力
と同時に１ビット変化点検出回路102の出力が“1"とな
り、ランレングス１が符号発生回路106で符号化される
のであるが、本実施例では白であるのでカウントアップ
を続ける。

ランレングスカウンタが５から６へカウントアップす
るときに次の新しい８ビットパラレル画像データが必要
となるので、８ビット変化点検出回路100へ入力する。
ランレングス６からＤに対応する画素はすべて白である
ので、８ビット変化点検出回路100の出力は“1"にな
る。この出力を受けるイネーブル制御回路105は２つの
入力のどちらかが“1"であれば９ビットカウンタ103の
イネーブル入力を“1"にするので、この場合はイネーブ
ル入力が“1"となり９ビットカウンタ103がカウントア
ップする。また、イネーブル制御回路107は８ビット変
化点検出回路100の出力が“0"であり、１ビット変化点
検出回路102の出力が“1"の場合のみ３ビットカウンタ1
04のイネーブル入力を“1"とするので、この場合は８ビ
ット変化点検出回路100の出力が“1"であるため１ビッ
ト変化点検出回路102の出力に関係なくイネーブル入力
が“0"となりカウントアップしない。従って、ランレン
グスカウンタとしては８増加しＥとなる。

ところで、ランレングスがＥの場合もランレングス６
と同様に次の新しい８ビットパラレル画像データが必要
となるので、８ビット変化点検出回路100へ入力する。
これも同様に８画素はすべて白であるのでランレングス
カウンタを８増加させ16となる。

そして次の新しい８ビットパラレル画像データを入力
すると、白画素504と黒画素505の間に変化点があるため
８ビット変化点検出回路100の出力は“0"となる。これ
により９ビットカウンタ103のカウントアップが停止す
る。入力した８ビットパラレル画像データは８ビット変
化点検出回路100で検査されると同時にパラレル／シリ
アル変換回路101に取り込まれ、１ビットシリアル画像
データに変換されて１ビット変化点検出回路102へ順次
入力される。

３ビットカウンタ104のみがカウントアップの途中で
ランレングスカウンタの値が17となったときは３ビット
カウンタ104のキャリー（桁上り）が“1"となるので、
イネーブル制御回路105を介して９ビットカウンタ103の
イネーブルも“1"となり、次のランレングスカウンタ値
が18となる。

最後に白画素504が１ビットシリアル画像データとし
て１ビット変化点検出回路102へ入力された時点で、１
ビット変化点検出回路102は白画素504と黒画素505の間
の変化点を検出し、出力を“0"にする。これに対してイ
ネーブル制御回路107は３ビットカウンタ104のイネーブ
ル入力を“0"としてランレングスカウンタを停止させ
る。このときのカウンタ値は1Bであり、白画素502から
白画素504までの画素数を表わしている。これと同時に
ストップ信号が出力され、ランレングスカウンタの値1B
が符号発生回路106へ送られて該当する符号データが出
力される。

以上述べたきたように第５図の画素列処理に第３図の
構成では27サイクル（16進数1B）必要とするのに対し
て、第１図の構成では13サイクルとなり、符号化処理速
度を向上させられる。

第７図は８ビット変化点検出回路の構成である。素子
701はENORと呼ばれる素子で２つの入力が共に“0"ある
いは“1"のときだけ“1"を出力し、他の場合は“0"を出
力する。素子702はANDと呼ばれる素子であり、すべての
入力が“1"のときのみ“1"を出力し、他の場合は“0"を
出力する。この回路によれば、８ビットパラレル画素デ
ータがすべて同じ色すなわちすべて“1"か“0"の場合に
“1"を出力する。

この回路は素子701の入力第一段目で隣接する画素を
調べて変化点の存在を検出し、素子702の第２段目では
その検出位置にかかわらず、まとめているだけであるの
で、処理データ幅を増す場合は素子701の個数と素子702
の入力数をふやすだけで済む。これに対してプライオリ
ティエンコーダを使用すると、第１段目が変化点を検出
したときにその検出位置より優先順位の高い位置で変化
点検出がないのを確める必要があり、素子701であれば
その左側６個のENORの出力も入力しなければならず、素
子703は左側５個の出力も入力し、第１段目の入力数が
処理データ幅の２乗に比例して増加してしまう。従って
本発明の多数ビット変化点検出回路は構成素子を極端に
増加させる必要なく、処理データ幅をふやすことができ
る。

第６図は多数ビット変化点検出回路を他段構造にした
本発明の一実施例である。ｎを３として８ビット変化点
検出回路、16ビット変化点検出回路、32ビット変化点検
出回路を設けるとともにランレングスカウンタを下位３
ビット、中位１ビット、中位１ビット、上位７ビットに
分離したものである。第５図の画像において、ランレン
グスカウンタが５から６へカウントアップするときに次
の新しい32ビットパラレル画像データが必要となるの
で、32ビット変化点検出回路601へ入力する。ランレン
グス1Bに対応する画素が黒であり、32画素に白と黒が混
在しているので32ビット変化点検出回路601の出力は
“0"になり、７ビットカウンタ608はカウントしない。
このため、画像データは16ビット変化点検出回路603へ
送られる。ランレングス６から15に対応する16画素はす
べて白であるので、16ビット変化点検出回路603の出力
は“1"になる。この出力をイネーブル制御回路614を経
由して１ビットカウンタ609は受け取りカウントアップ
する。しかし、ランレングス16に対応する画素から16画
素内には白と黒が混在しているので、16ビット変化点検
出回路603の出力は“0"になる。また、ランレングス16
に対応する画素から８画素内にも白と黒が混在している
ので、８ビット変化点検出回路605の出力も“0"にな
る。従って、ランレングス１から５と16から1Bは１画素
ずつカウントアップするが、ランレングス６から15は16
画素を１サイクルでカウントアップするので、12サイク
ルで処理でき、第１図の構成よりも高速である。

以上の説明で明らかなように、本発明によれば簡単な
回路の追加により符号化処理の高速化を達成できる。

〔発明の効果〕

本発明によれば、複数ビット変化点検出器により画像
データの黒あるいは白一色の領域を複数ビット変化点検
出器の処理データビット幅倍の速度で検査できるので、
画像データ符号化の高速化の効果がある。

また、処理データビット幅の拡大はそのビット幅個数
の素子と少々の制御回路の増加のみで容易に実現でき
る。

【図面の簡単な説明】

第１図は本発明の一実施例で用いた８ビット変化点検出
器付画像データ符号化装置の構成図、第２図はランレン
グス符号化の例を示す図、第３図は一般的なランレング
ス符号化装置の構成図、第４図は一走査線の画素列を示
す図、第５図は本発明の一実施例で用いた処理タイミン
グの図、第６図は多段複数ビット変化点検出器付画像デ
ータ符号化装置の構成図、第７図は８ビット変化点検出
器の構成図である。 100…８ビット変化点検出回路、101…パラレル／シリア
ル変換回路、102…１ビット変化点検出回路、103…９ビ
ットカウンタ、104…３ビットカウンタ、106…符号発生
回路。

───────────────────────────────────────────────────── フロントページの続き (72)発明者岡澤宏一神奈川県横浜市戸塚区吉田町292番地株式会社日立製作所マイクロエレクトロニクス機器開発研究所内 (56)参考文献特開昭61−208371（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】白画素から黒画素あるいは黒画素から白画
素に変化する点（変化点）間の画素数（ランレングス）
を符号化するために、変化点検出器とランレングスカウ
ンタおよび該ランレングスカウンタから得られるランレ
ングスを符号に変化する回路より成る画素データ符号化
装置において、２のｎ＋２乗複数ビット内の変化点を検出する第１の検
出手段と、前記第１の検出手段により変化点が検出された場合に前
記２のｎ＋２乗複数ビットの内の２のｎ＋１乗複数ビッ
ト内の変化点を検出する第２の検出手段と、前記第２の検出手段により変化点が検出された場合に前
記２のｎ＋１乗複数ビットの内の２のｎ乗複数ビット内
の変化点を検出する第３の検出手段と、前記第３の検出手段により変化点が検出された場合に前
記２のｎ乗複数ビットの内の各ビットを１画素単位で変
化点を検出する第４の検出手段と、前記第４の検出手段が２のｎ乗複数ビット内の変化点を
検出するまで、２のｎ乗複数ビットのランレングスを計
数する２進ｎ桁カウンタと、前記第３の検出手段が２のｎ乗複数ビット内の変化点を
検出するまで、あるいは前記２進ｎ桁カウンタの桁上が
りがあったときにランレングスを計数する第１の２進１
桁カウンタと、前記第２の検出手段が２のｎ＋１乗複数ビット内の変化
点を検出するまで、あるいは前記第１の２進１桁カウン
タの桁上がりがあったときにランレングスを計数する第
２の２進１桁カウンタと、前記第１の検出手段が２のｎ＋２乗複数ビット内の変化
点を検出するまで、あるいは前記第２の２進１桁カウン
タの桁上がりがあったときにランレングスを計数する２
進ｍ桁カウンタと、上記４個のカウンタ手段を１個のカウンタとして計数す
るように桁上がり情報を伝達する手段を設けたことを特
徴とする複数ビット変化点検出器付画像データ符号化装
置。