JPH07121068B2 - ランレングス符号化装置 - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は画像のデータ圧縮のために画像のランレングス
を符号化するランレングス符号化装置に関する。

従来の技術 画像データが持つ冗長度を抑圧し画像の伝送および蓄積
をより効率的に行うために，画像のランレングスを符号
化し画像データを圧縮する方式がある。これは画像のラ
イン方向に連続する白画素または黒画素（白ランまたは
黒ラン）の長さ（ランレングス）に対して，その発生頻
度に応じてそれぞれ適当な符号語を与えるものである。
すなわち発生確率の高いランレングスには短い符号語を
割り当て，発生確率の低いランレングスには長い符号語
を割り当てる。このようにランレングスを符号化する方
式の一つに符号語長がランレングスの対数の１次関数と
なる符号がある（吹抜 著「FAX.OAのための画像の信号
処理」日刊工業新聞社 p68）。このような符号には，
例えばWYLE符号,1−２符号等が知られている（遠藤，山
崎「会話型画像通信に適したファクシミリ信号の順次再
生符号化方式」電子通信学会論文誌′84/12 Vol.J67−B
No.12 pp.1462−1469）。

WYLE符号,1−２符号をそれぞれ第７図，第８図に示す。
これらの符号はそれぞれアドレス符号とリメインダ符号
とから成る。アドレス符号はランレングス（２進数）の
ビット数を基に符号語の符号長およびその符号長で表し
得るランレングスの最小値を表す。リメイング符号は前
記ランレングスの最小値と実際のランレングスとの差を
表す。例えばランレングスの２（２進数の10）をWYLE符
号で符号化する場合，ランレングスのビット数が２であ
ることからアドレス符号は１でありこの時前記最小ラン
レングスは１であるのでリメインダ符号は01（２進数）
となり符号語は101で与えられる。なお本明細書におい
てはアドレス符号のLSB以外の部分を符号語のヘッダ部
と定義する。第７図，第８図の符号では符号語のヘッダ
部は０によって構成され，またアドレス符号が１の時は
ヘッダ部は無いことになる。

次に従来の符号化の方法をWYLE符号を例にとって説明す
る。WYLE符号の場合ランレングスから１を引いた値（２
進数）とそのビット数を求め，このビット数から２を引
いた個数の０をヘッダとし，これを前記ランレングスか
ら１を引いた値（２進数）に付加したものがランレング
スに対応した符号語となる。ただしランレングスが１か
ら４までは例外で，ランレングスから１を引いた値（２
進数）を２ビットで表現したものに１をヘッダとしては
付加したものとなる。符号化には以上の性質を利用す
る。

第９図はWYLE符号の符号化装置の従来例の一つである。
ランレングスはカウンタ101により計数される。ただし
ランレングスから１を引いた値を得るためカウンタ101
の初期値は−１をセットする。画像の白黒変化により１
つのランを検出するとカウンタ101の値はシフトレジス
タ102にロードされる。制御部108はこの時のロードデー
タのLSB（最下位ビット）を反転した値をシフトレジス
タ102の入力として設定する。さらにシフトレジスタ102
の内容は左へシフトされコード作成部106のシフトレジ
スタ107へ送られる。ゲート103によりシフトレジスタ10
2の内容がすべて等しくなるのを検出した時点でシフト
レジスタ102の内容がシフトレジスタ107に移されたこと
になる。

この間制御部108のカウンタ111はシフトレジスタ102か
ら最初に１が出力された以降のシフト数を計数すること
によりランレングスから１を引いた値（２進数）のビッ
ト数を求める。またWYLE符号の場合このビット数から２
を引いた値がヘッダ部の０の個数である。次の制御部10
8は前記ランレングスから１を引いた値（２進数）のビ
ット数をカウンタ104にセットし，前記ヘッダ部の０の
個数をカウンタ105にセットする。コード作成部106はシ
フトクロック109に同期して先ずカウンタ105をカウント
ダウンして０となるまでの間０を出力し，次にシフトレ
ジスタ107の内容を左にシフトして最初に１が現れる時
点からその出力をコードデータ110として出力するとと
もにカウンタ104をカウントダウンする。カウンタ104の
値が０になった時点でランレングスに応じた符号語が送
出されたことになる。またランレングスが１から４まで
の例外処理ではカウンタ104には1,カウンタ105には２を
セットカウンタ104により１を１ビット出力した後カウ
ンタ105を利用してシフトレジスタの下位２ビットを出
力して符号語を送出する。カウンタ104,カウンタ105,カ
ウンタ111を１つのアップダウンカウンタで共用してい
る例もある（たとえば，特開昭57−204681号公報）。

発明が解決しようとする問題点 従来の方式ではランレングスから１を引いた値（２進
数）のビット数をカウントし，このカウント値を基に符
号のヘッダ部の０の数を求めてこれをカウンタにセット
し，さらに符号語のヘッダ部に続く部分のビット数を求
めてこれをカウンタにセットしてこれらのカウンタを利
用してランレングスの符号化を行っていた。このために
カウンタおよびその周辺回路が必要となりまたこれらの
制御も複雑であった。さらにランの分布の統計的性質に
より異なる複数の符号を適応的に用いて画像データの圧
縮をより効率的に行おうとする際にはランレングス符号
化装置は複数の符号を符号化できるのが望ましいが，先
に述べた複雑さにより複数の符号に対応するには装置の
構成規模がさらに大きくなる欠点があった。

本発明はかかる点に鑑み，簡素な構成でランレングスの
符号を実現し，従つて複数の符号に対しても容易に適応
することができるランレングス符号化装置を提供するこ
とを目的とする。

問題点を解決するための手段 本発明は上記問題点を解決するために，データを読み込
みこれを入力した順に読み出し得るメモリ装置を２組準
備し，第１のメモリ装置はランレングスの計数値にオフ
セットを与えた値を入力とし第２のメモリ装置は符号の
ヘッダ部の値０を入力としてこれら２つのメモリ装置を
同時に動作させ，第１のメモリ装置へ前記ランレングス
の計数値にオフセットを与えた値の入力が完了した時点
で両者を結合することにより求める符号語を得るもので
ある。

作用 本発明は上記の構成とすることにより前記第１のメモリ
装置へ前記ランレングスの計数値にオフセットを与えた
値の入力が完了した時点で，前記第２のメモリ装置には
符号語のヘッダ部が前記第１のメモリ装置には符号語の
ヘッダ部以降がそれぞれ生成されることになり，ここで
前記第1,第２のメモリ装置を結合することによりメモリ
装置内に符号語を得ることになる。また前記メモリ装置
に生成された符号語の読み出しに際しては前記メモリ装
置がその内部のデータの有無を知らせるアウトプットレ
ディ信号を利用することにより，符号語のヘッダ部やそ
れに続く部分のビット数を計数するための各カウンタを
用いること無く符号語の送出終了を知ることができる。

実施例 第１図は本発明によるランレングス符号化装置の一実施
例を示すブロツク図であり，ランレングスを計数するカ
ウンタが16ビットの場合である。同図において,1はラン
レングスを計数するカウンタ,2はシフトレジスタ,3はシ
フトレジスタ２の上位12ビツトがすべて等しいか否かを
判定するゲート,4はリードオンリメモリ（ROM）,5はラ
ンレングスの短い所での例外処理のモードを設定するた
めのラッチ,6はタイミング制御部,7はマルチプレクサ,
8,9はファストイン・ファストアウトメモリ（FIFO）,10
はラングレスの短い所での例外処理と通常の処理とを選
択する例外処理切換回路,11はシフトレジスタ２へのロ
ード信号,12はスタート信号,13はWYLE符号や１−２符号
等の符号を選択するための制御信号,14は基本クロック,
15はコード作成終了信号,16はコード送出終了信号,17は
コードデータシフトクロック,18はコードデータであ
る。以下WYLE符号を例にとって第１図の符号化装置の動
作を説明する。同図の符号化装置はランレングスの短い
所での例外処理を行う部分と通常の処理を行う部分とに
分けられこれらのうち一方が例外処理切替回路10で選択
される。FIFO8,9,とマルチプレクサ７は通常の処理を行
う場合のみ用いられる。以下第１図の装置の動作をラン
レングスの短い所での例外処理を行う場合と通常の処理
を行う場合とに分けて説明を行う。

第２図は第１図の装置のうちランレングスの短い所での
例外処理を行う部分を示したものである。第２図の回路
の動作を第４図のタイミング図を参考にして説明する。
カウンタ１はランレングスを計数する。ただしランレン
グスから１を引いた値を得るため初期値としてのカウン
タの総てのビットに１を設定する。画素の白黒変化によ
り１つのランを検出するとカウンタ１の値はシフトレジ
スタロード信号11によりシフトレジスタ２に取り込まれ
る。更にシフトレジスタ２の上位12ビットはゲート３に
下位４ビットはROMに出力され，ゲート３はその入力12
ビットが総て０か否かの情報をROM4に出力する。またコ
ード選択信号13はWYLE符号モードであることを示すコー
ドをROM4に与える。ROM4はシフトレジスタ２の下位４ビ
ットおよびゲート３の出力を基に表１に従ってシフトレ
ジスタ２の値に応じた３ビットのコードをラッチ５に出
力する。ラッチ５は信号32の立ち上がりで前記３ビット
のコードを取り込む。

表においてラッチ５の値の最上位ビットが０の時はラン
レングスの短い所での例外処理であることを示し最上位
ビットが１の時はそれ以外の通常の処理であることを示
す。ROM4はラッチ５への出力の最上位ビットが０の場
合，既に符号化が終了しコードの送出が可能であること
を示すコード作成終了信号16を出力する。この信号16が
出力されると外部からコードデータシフトクロック17が
与えられこのシフトロックによりシフトレジスタ２の内
容がシフトされる。一方ラッチ５の出力はROM4にフィー
トバックされこのラッチ５の値とシフトレジスタ２の下
位４ビットの値51およびコード選択信号13を入力として
ROM4は第６図のテーブルに従ってコードデータ18,シフ
トレジスタ２のシリアル入力52およびコード送出終了信
号15を出力する。例えばWYLE符号でランレングスが４の
場合，シフトレジスタ２の下位４ビットは0011となり
（カウンタ１の初期設定が総てのビット＝１であるため
ランレングスの４をカウントアップした時点で0011とな
る）またこの時，表からラッチ３の値は011であるので
第６図からコードデータ18として1,シフトレジスタ２の
シリアル入力52として１を出力する。

次にコードデータシフトクロック17によりシフトレジス
タ２の内容が１ビットシフトされるとシフトレジスタ２
の下位４ビットは0111となりコードデータ18として1,シ
フトレジスタ２のシリアル入力52として１を出力する。
さらにシフトレジスタ２の内容の１ビットシフトにより
コードデータ18として1,シフトレジスタ２のシリアル入
力52としてＯを出力し次にシフトレジスタ２の内容が１
ビットシフトされた時点でシフトレジスタ２の下位４ビ
ットが1110となることによりコードデータ送出終了信号
15が出力され符号語の送出が終わったことを知らせる。
以上の過程でランレングス４に対応するコードデータと
して111が送出されたことになる。WYLE符号のランレン
グスが１から３の場合および１−２符号のランレングス
が１の場合も同様の手順で符号語を得ることができる。

第３図は第１図の装置のうち通常の処理（上記の例外処
理以外）を行う部分を示したものである。第３図の回路
の動作をWYLE符号でランレングスの６（２進表現の11
0）を符号化する場合を例にとって第５図のタイミング
図を参考に説明する。カウント１によるランレングスの
計数からラッチ５へのデータセットまでの動作は先の第
２図における例外処理の回路の動作と同じであり，今の
場合シフトレジスタ２には101がセットされておりラッ
チ５は表よりlXOを出力する（Ｘはdon't care）。ただ
しシフトレジスタロード信号11によりシフトレジスタ２
にデータがロードされた時点でフリップフロップ35,39
はリセットされており，またシフトレジスタ２にデータ
をロードした時のLSBの値の反転値が表１に示すように
ラッチ５のLSBにより与えられROM4を経由してシフトレ
ジスタ２のシリアル入力となっている。

さてスタート信号12が入力されるとフリップフロップ39
がセットされクロック14はフリップフロップ39の出力41
によりゲート34で有効となりシフトクロック42となって
シフトレジスタ２の内容の左シフトを開始する。さらに
シフトレジスタ２の出力43に最初に１が現れた時点でフ
リップフロップ35がセットされクロック14はフリップフ
ロップ35の出力44によりゲート36で有効となりFIFO8へ
のシフトインクロック45となる。またシフトインクロッ
ク45はクロックマスク制御部37により最初の数クロック
がマスクされてFIFO9へのシフトインクロック46とな
る。クロックマスク制御部37においてマスクされるクロ
ック数はWYLE符号の場合は最初の２クロック,1−２符号
の場合は最初の１クロックである。今の場合シフトレジ
スタ２には101がセットされているためシフトレジスタ
２の内容が13ビットシフトされた後14ビット目で初めて
１が出力され，以後のデータがFIFO8に取り込まれるこ
とになる。またFIFO9には２クロック遅れでマルチプレ
クサ７の出力が取り込まれる。

マルチプレクサ７はコード作成終了信号15が出力される
までは０レベルを選択するためFIFO9には０が取り込ま
れることになる。シフトレジスタ２のシフトはROMがコ
ード作成終了信号15を出力するまで続けられる。ここで
コード作成終了信号15はROM4がシフトレジスタ２の上位
12ビットがすべて等しいか否かを知らせるゲート３の出
力およびシフトレジスタ２の下位４ビットを監視してシ
フトレジスタ２のすべてのビットが等しくなるのを検出
した時点で出力される。シフトレジスタ２には最初のデ
ータロード時におけるLSBの反転値が入力されるためコ
ード作成終了信号15が出力された時点で最初にロードし
たデータ16ビットはすべてシフトレジスタ２より出力さ
れたことになる。コード作成終了信号15の出力によりフ
リップフロップ35はゲート33を介してリセットされ，フ
リップフロップ35の出力44によりゲート36においてFIFO
8,9のシフトインクロック45,46はマスクされる。この時
FIFO8にはシフトレジスタ２に最初にロードしたデータ
のうち最上位の１より以降が入力されている。またFIF0
9にはFIFO8に入力されたデータのビット数より２ビット
少ない（１−２符号の場合は１ビット少ない）０が入力
されている。すなわちFIFO9には符号語のヘッダ部の０
がFIFO8には符号語にのヘッダ部に続く部分が生成され
たことになる。今の場合，カウンタ１の最初のロードデ
ータのLSBが１であり，その反転値０がシフトレジスタ
２の入力であるので，シフトレジスタ２のすべてのビッ
トが０となった時点でROM4よりコード作成終了信号15が
出力されてFIFO8,9のシフトイン動作が停止し，この時F
IFO8には最初のロードデータの下位３ビットすなわち10
1が,FIFO9には０が１ビット入力されていることにな
る。この様子を第５図のタイミング図の８′,9′で示
す。さらにコード作成終了信号15が出力された時点でマ
ルチプレクサ７はFIFO8の出力を選択しFIFO8とFIFO9と
を結合する。これによりFIFO9における符号語のヘッダ
部とFIFO8における符号語のヘッダ部に続く部分とが結
合され求める符号語がFIFO内に生成されたことになる。

コード作成終了信号15が出力されるとコードを読み出す
ためのコードデータシフトクロック17が外部より入力さ
れる。コードデータシフトクロック17はシフトアウト制
御部38を経てFIFO8,9にシフトアウトロックとして与え
られこのシフトアウトクロックに同期してFIFO9はコー
ドデータ18を出力する。コードデータが順次出力されて
FIFO9のデータが空になった時点でFIFO9のアウトプット
レディ信号がOFFとなる。FIFO9のアウトプトレディ信号
がOFFになるとシフトアウト制御部38はコードデータ送
出終了信号15を外部に出力しFIFO8,9に生成された符号
語がすべて出力されたことを知らせる。今の場合FIFOに
は0101の符号語が生成されているため４ビットをシフト
アウトした時点でアウトプットレディ信号はOFFとなり
コードデータ送出終了信号15が出力されることになる。
このようにメモリ装置のアウトプットレディ信号を利用
すれば符号送出の際に送出ビット数をカウントする必要
が無くなりこのためのカウンタが不要となる。

以上第１図のランレングス符号化装置の動作をWYLE符号
を中心に述べてきたが,1−２符号の場合は第1,2,3図の
カウンタ１の初期設定値が０となり，表１および第９図
に示すごとくROMテーブルが変わり，また第３図におけ
るクロックマスク部37がシフトインクロック45の最初の
１クロックをマスクする（WYLE符号は２クロック）よう
になる点が異なるだけで他は,WYLE符号と１−２符号と
は共通の処理である。

発明の効果 従来，ランレングス符号の符号化に際してはランレング
スの２進表現におけるビット数の計数，符号語のヘッダ
部の０の数の計数および符号語のヘッダ部に続く部分の
ビット数の計数にそれぞれカウンタを必要としていた。
従ってカウンタを制御する周辺回路等も複雑になり装置
全体の規模が大きくなるきらいがあった。これに対して
本発明においては先に述べた構成をとることにより上記
の各カウンタをすべて不要とし装置の簡素化を可能とし
ている。さらに簡素な構成故に，複数のランレングス符
号に対しても装置の一部の制御で容易に対応することが
可能である。

【図面の簡単な説明】

第１図は本発明の一実施例のランレングス符号化装置の
ブロック図，第２図および第３図は異なる動作状態にお
ける同装置の要部構成図，第４図および第５図は各々第
３図および第４図の回路の動作説明用タイミング図，第
６図はランレングスの短い所での例外処理で利用するRO
Mテーブル図，第７図はWYLE符号説明図，第８図は１−
２符号説明図，第９図は従来のランレングス符号化装置
のブロツク図である。 １……カウンタ、２……シフトレジスタ、３……ゲー
ト、４……ROM、５……ラッチ、６……タイミング制御
部、７……マルチプレクサ、8,9……ファストイン・フ
ァストアウトメモリ（FIFO）、10……例外処理切換回
路、11……シフトレジスタ２へのロード信号、12……ス
タート信号、13……WYLE符号や１−２符号等の符号を選
択するための制御信号、14……基本クロック、15……コ
ード作成終了信号、16……コード送出終了信号、17……
コードデータシフトクロック、18……コードデータ

Claims (2)

【特許請求の範囲】
1. 【請求項１】画像データのランレングスを符号語長がラ
   ンレングスの対数の１次関数となる符号により符号化す
   るものであり，ランレングスを計数するカウンタと，前
   記カウンタの計数値を並列入力するシフトレジスタと，
   前記シフトレジスタの直列出力を読み込みこれを入力順
   に読み出し得る第１のメモリ装置と，前記第１のメモリ
   装置の出力または符号語のヘッダ部の値（符号語へのヘ
   ッダ部の値は０または１に固定されている）の一方を選
   択するマルチプレクサと，前記マルチプレクサの出力を
   読み込みこれを入力順に読み出し得る第２のメモリ装置
   と，前記第２のメモリ装置への読み込みクロックを前記
   第１のメモリ装置への読み込みクロックの一部をマスク
   して得る手段と，前記シフトレジスタの全ビットが等し
   くなるのを検出する手段と，例外処理が必要となる短い
   ランレングスを検出する手段と，例外処理における符号
   をテーブルにより生成する手段とを有し，前記ランレン
   グスの短い所での例外処理では前記符号テーブルを用い
   てランレングスの符号化を行い，それ以外は前記シフト
   レジスタに制御用のビット０または１を入力しつつ順次
   左シフトして最初に出力される１より以降を前記第１の
   メモリ装置に送出すると共に前記第２のメモリ装置には
   アドレス符号のヘッダ部の値を入力し，前記シフトレジ
   スタの全ビットが等しくなった時点で前記第１のメモリ
   装置にはアドレス符号のLSB（再下位ビット）とリメイ
   ンダ符号が，第２のメモリ装置には符号語のヘッダ部
   （アドレス符号のLSB以外）が生成されることを利用し
   てこの時点で前記第１および第２のメモリ装置を前記マ
   ルチプレクサを介して結合することによりランレングス
   の符号化を行うことを特徴とするランレングス符号化装
   置。
2. 【請求項２】符号語長がランレングスの対数の１次関数
   となる符号の複数に対して，第２のメモリ装置への読み
   込みクロックを第１のメモリ装置への読み込みクロック
   の一部をマスクして得る手段と，前記例外処理が必要に
   なる短いランレングスを検出する手段と，例外処理にお
   ける符号をテーブルにより生成する手段とをそれぞれの
   符号に応じて適応化させることにより，他の部分は一元
   的に利用して複数の符号に対して符号化を行えることを
   特徴とする特許請求の範囲第１項記載のランレングス符
   号化装置。