JPS6282724A - 冗長度抑圧符号化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は例えばｚ値化された画像信号の如き２値信萼の
冗長度を抑圧する冗長度抑圧符号化方式％式％ ［従来の技術］ ｚ値画像信号に代表される２値信号の冗長度抑圧符号化
方式においては、元の２値信号列よりも統計的性質の偏
りの大きな信号列を得る事と、そのようにして得られた
信号列を簡単な符号化によって、高い圧縮比を得ること
が大きな課題である。統計的性質の偏りの大きな信号列
においては、同じ論理値を持つ連続長がより長くなるか
ら、例えばランレングス符号化を行えば、いわゆるエン
トロピーが減り、極めて高い圧縮比が得られるからであ
る。

ところが、画像通信、特にファクシミリ通信の分野での
符号化法、例えばＣＣＩＴＴが勧告するＭＨ（モディフ
ァイド・ハフマン）符号化、及びＭＲ（モディファイド
ＲＥＡＤ）符号化、ＭＭＲ（モディファイド、モディフ
ァイドＲＥＡＤ）符号化等はファクシミリだけでなく、
電子ファイル等にも使用されているのは周知の事である
が、これらの符号化法は、文字等の文書情報には木質的
に“白″ランが多い事に着目して、かかる画像信号の伝
送を前提としたものである。一方、一般の文書画像に加
え、写真等の中間調画像の２値画像については、例えば
ディザ法等により２値化した疑似中間調画像が考えられ
る。しかし、疑似中間調画像は面積階調法により階調性
を出すものである事から、その性質上印字ドツト（“黒
”）は分散する事になる。即ち、疑似中間長両像は、元
の中間調画像よりも短いｒラン長」が増える事となり、
このままでは符号化に不都合である。

この事情を第２図（ａ）、（ｂ）及び第３図（ａ）、（
ｂ）を用いて説明する。第２図（ａ）及び（ｂ）のマト
リックスは閾値マトリックス、特にドツト集中型のディ
ザマトリックスを示す。

第３図（５Ｌ）の実線は第２図（ｂ）の第１列目の閾値
変化を表わす、このような閾値に対して図の点線のよう
な中間調画像が入力すると、第３図（ｂ）に示されたよ
うな離散的な分布をもつ疑似中間調画像信号が得られる
。このように“白″゛黒”がバラバラになると、ランレ
ングス符号化では圧縮率が低下するのに説明を要しない
であろう、又、この様な疑似中間調画像に対してＭＨ符
号化等を行うと、高能率な抑圧が望めないばかりか、逆
にデータ量が増加する場合があった。

従来、上記問題を解消する手段として、ビットインタリ
ーブ法が知られている。ビットインタリーブ法では、互
いに近接した閾値に対応する画素をグループ化し、複数
系列のビットパターンへ変換し、或いは同一の閾値のも
の同志をグループ化して複数系列のビットパターンへ変
換し、それぞれのビットパターンに対しＭＨ符号化を行
っているが、大幅な効率化は望めないものであった。

［発明の目的］ 本発明は上述従来例の欠点に鑑みなされたものでその目
的は、高い効率で２値信号の冗長度を抑圧する冗長度抑
圧符号化方式を提案する事にある。

Ｅ問題点を解決するための手段］ 上記問題点を解決するために、２値信号の一例である２
値画像データの冗長度を抑圧するのに適用されたところ
の第１図に示す実施例の冗長度抑圧符号化方式は、例え
ばＭＨ符号化を行うランレングス符号化部２のための前
処理として、ｚ値画像データ４を所定の周期のビットイ
ンタリーブにて並べ換えて２値信号列５を得るビットイ
ンターリーブ再構成部３と、更にこの並べ換えられた２
値信号列５の論理値の変化及び非変化を新たなｚ値とす
る２値信号列１３に変換するための変化点抽出部６とか
らなる前処理部１を有す。

［作用］ 上記の構成の下で、入力の２値画像データ４が例えば第
３図（ｂ）の示した如き中間調画像をディザ法で面積変
調したものであれば、先ずビットインタリーブ再構成部
３により、白又は黒の偏りの大きな２値信号列５が得ら
れる。その理由は、ディザマトリクスが例えば第２図（
ｂ）のような４×４であれば、ディザ処理後の画像デー
タには第３図（ｂ）のような周期性が含まれるので、４
ビツト毎のビットインタリーブにより２値信号列５には
白又は黒が偏在し、白ラン長、及び黒ラン長が長くなる
なるからである。

更に変化点抽出部６により、変化点抽出によるｚ値化、
例えば、信号列５の論理値変化点を“ｌ”とし、その他
の無変化点を“Ｏ１１とするｚ値化をすれば、論理値“
ｌ”は上記変化点のみとなる。そうすると、“０”ラン
が更に増えるので、ランレングス符号化部２によるラン
レングス符号化が効率的となり、高いデータ圧縮率が得
られる。ランレングス符号化部２では例えば、２値信号
列１３を“Ｏ”ラン“１”ラン振り分は部７により０”
ランと“１”ランとに振り分け、夫々をランレングス符
号化部８，９によりランレングス符号化する。

［実施例］ 以下添付図面を参照しながら本発明に係る実施例を更に
詳細に説明する。実施例は前述の如く、前処理部１と、
符号化部２との組合せからなる。

前処理部ｌはビットインタリーブ再構成部３と、変化点
抽出部６からなる。又符号化部２は後述する符号化法の
違いによりその内部構成を異にする（第９図と第１１図
）。先ず前処理部１について説明しよう。

くビットインタリーブ再構成部〉 第４図（ａ）及び（ｂ）更に第５図（ａ）〜（Ｃ）、第
６図を用いて、ビットインタリーブの手法を説明する。

第４図（ａ）は例えば第２図（ａ）又は（ｂ）のディザ
マトリックスにより２値化された原画像データ４であっ
て、主走査方向へ４００画素副走査方向へ４画素分の大
きさを持つものを示す０図に付された番号は主走査方向
には画素の番号を、副走査方向にラインの番号を便宜上
付したものである。この画像データ４は４ビツト周期の
周期性をもつ、前述したように、このようなディザ画像
は中間調を表現するにはすぐれるが、ラン長が短くなっ
てしまっているのは図をみても明らかである。この画像
データ４に対して４ビツトのインタリーブを行うと、第
４図（ａ）の１．２，３，４．・・・の画素配列が第４
図（ｂ）の如き１，５，９，１３，１７．・・・なる配
列となり、“白”ラン及び“黒”ラン長が増加している
のがわかる。４ビツトとしたのは、閾値処理に用いたデ
ィザマトリックスが４ビツトであるからであるが、上記
ビットインタリーブはディザマトリックスと同一の長さ
で行った。このようなビットインタリーブ長の決定の他
に、マトリックスの大きさの整数倍又は整数分の１の大
きさに設定する事もできれば、又は閾値マトリックス内
の近似した値をもつ閾値に対応した周期でグループ化す
る手法もある。

さてこのようなビットインタリーブを行う回路を第６図
に示す、第６図のビットインタリーブ再構成部３は、２
値画像データ４の並べ換えるために２つのラインメモリ
４０．４１を用いる。２つ用いるのは２値画像データ４
の入力と並べ換え動作と並べ換えられた信号列５を読み
出す動作とを同時に行うためである０則ち、１つのライ
ンメモリに入力（書込み）するときは、他方のラインメ
モリは出力（読み出し）に使われる。１つのラインメモ
リが同時に書込みと読出しに使われるのを防ぐために、
書込み用のアドレスカウンタ２５と、読み出し用のアド
レスカウンタ２６と、これらカウンタ２５．２６の出力
を各ラインメモリ４０．４１に振り分けるセレクタ２７
，２８，２９．３０，３１．３２及び排他制御を行うラ
インメモリ制御部４２等がある。ラインメモリ制御部４
２は１ライン毎に発生するＢＤ信号３８に同期して第２
ラインメモリ書込み信号３６又は第１ラインメモリ書込
み信号３７を交互に“°１”とする、又セレクタ２７，
２８．３１は、第２ラインメモリ書込み信号３６又は第
１ラインメモリ書込み信号３７の論理値に応じて出力を
選択するセレクタであり、一方、セレクタ２９，３０．
３２は同じく、第２ラインメモリ書込み信号３６又は第
１ラインメモリ書込み信号３７の論理値に応じて入力を
選択するものである。このようにすると、第１ラインメ
モリ書込み信号３７が“１”のどきは、第２ラインメモ
リ書込み信号３６は“Ｏ”であり、セレクタ２７は出力
“０”を、セレクタ２９は入力“ＯＮを、セレクタ３１
は出力“θ″を選ぶために２値画像データ４が第１ライ
ンメモリ４０に書き込まれ、一方読み出しアドレスカウ
ンタ２６の出力はセレクタ２８及びセレクタ３０により
第２ラインメモリ４１に入力し、セレクタ３２は第２ラ
インメモリ４１を選ぶ。こうして書込みと読み出しの同
時処理が行え、高速化に寄与する。

各アドレスカウンタ２５．２６のアドレス発生方法を第
５図に示す、ラインメモリの容量を例えば第５図（ａ）
に示す如＜０００〜ＦＦＦとする。書込みアドレスカウ
ンタ２５は第５図（ｂ）の如く、ＯＯＯからＦＦＦまで
のシーケンシャルに昇順に増やせばよい、又、読み出し
アドレスカウンタ２６は第５図（Ｃ）のようにする。読
み出しカウンタ２６のこのようなアドレス発生回路は、
例えば書込みアドレスカウンタ２５と同一なカウンタと
、オフセット用の“１　”〜″４″の出力のカウンタと
、加算器とを用いれば容易に構成できる。尚１本実施例
のＢＤ信号３８は本冗長度抑圧符号化方式を例えばレー
ザビームプリンタ等に適用すればビームデテクト信号を
用い、ファクシミリ等に適用すれば水平同期信号を用い
るものである。

又、アドレスカウンタ２５．２６及びラインメモリ４０
．４１の駆動クロックは同期クロック３５である。この
同期クロック３５は符号化部２で生成されるもので、符
号化部２での符号化の際に、信号列があるパターンのと
きは強制的に所定のコードを挿入する必要が生じ、その
場合、その強制挿入コードを合成部１０が送出し終るま
で、ピットインタリーグ再構成部３の動作を停止するた
めに用いられる（詳しくは後述する）。

く変化点抽出〉 第７図（ｂ）に変化点抽出のための回路の一例□を、同
図（ａ）にその結果を示す、第７図（ｂ）の変化点抽出
部６の一例は主走査方向に１画素隣接する画素同士の間
の変化点を抽出する場合である。１つ隣接する画素を検
出するためにフリップフロップ２を用い、変化点を検出
するためＥＸ−ＯＲゲート（排他論理和ゲート）２１を
用いる。

４ビツトインタリーブをかけた信号列５に対し、注目画
素と同一走査線にあるその直前の画素とＥＸ−ＯＲをと
る。即ち、第２図（ａ）の閾値Ｄｉｊに画素を対応させ
れば、 Ｄ　ｘｉｊ　＝　Ｄ　ｉｊ　　■　Ｉ）１−＋＊ｊであ
る。第４図（ｂ）と第７図（ａ）を比較してもわかるよ
うに、“Ｏ“ラン（このような°゛Ｏ”ランを°白”ラ
ンということもある）が長くなっていて、ランレングス
符号化に適する事が一目瞭然である。

以上、冗長度抑圧符号化のための前処理について説明し
た。そこで、次に、符号化部２について、実施例を２つ
説明する。その２つとは、第８図（ａ）、（ｂ）及び第
１１図に示されたところの、各“ｌ”ランと“Ｏｎラン
毎に１次元符号化によるランレングス符号化処理を行う
実施例と、第１０図（Ｌ）〜（Ｃ）及び第９図に示され
たブロック切出しを行ってランレングス符号化を行う実
施例である。

（ランレングス符号化〉・・・１次元符号化による実施
例 第８図（ａ）に、第７図（ａ）の変化点抽出された信号
列１３における、４０′ランと１”ランとの注目のし方
を示す。尚、図中慣例に従い１１０　ＩＴを°゛白″“
１″を“黒”と称して表わす。桁数を表示し易いからで
ある。このようなランを例えばＭＨ符号化によって符号
化すると、第８図（ｂ）の如くなる。第８図（ａ）の第
２ラインは°゛黒“から始まっている。ＭＨ符号化法に
おいては、゛白″ランから始める事としている。

従って、このような場合“黒”の前に強制的に１つの°
“白′°を挿入する。

第９図はかかるランレングス符号化のための回路の一例
である８図中、ＲＬ（ランレングス）カウンタ５１．セ
レクタ５２．”白”ＭＨ符号化ＲＯＭ５３等が“Ｏ°゛
　（“白パ）ランを符号化して、ラッチ５４に符号コー
ドをラッチする。又、ＲＬカウ７タ７２　、”黒”Ｍ）
（符号化ＲＯＭ７３等が“ｌ°′　（“黒″）ランを符
号化して、ラッチ６１に符号コードをラッチする。振り
分は回路７１は信号列１３の変化（“０°′→″ＯＩｔ
、′Ｏ″→“１”、“１”→“Ｏ”、“ｌ”→“１”）
を検出する。ＲＬカウンタ５１，７２はＣＬＫを駆動ク
ロックとするカウンタで、そのＥＮ（付勢）端子に“１
”が入力すると、カウント可となり、ＣＬ（クリア）端
子に“１”が入力するとクリアされる。従って、例えば
ＲＬカウンタ５１は、信号列１３が“Ｏｎである間はカ
ウントし続け、そのカウント値に応じたＭＨ符号コード
をラッチ５４に入力する。信号列１３が“Ｏ”から“ｌ
”に変化すれば、その時のカウント値の符号コードがラ
ッチ５４にラッチされ、同時にカウンタ５１はクリアさ
れる０合成器６２は、“白”符号コードと黒符号コード
を合成してシフトレジスタ６３に格納するためのもので
ある。ＭＨ符号は可変長であるからこのような合成器が
必要となる。シフトレジスタ６３はパラレル−シリアル
変換を行う。

白“ＯＩＩ挿入部５５は、前述したように、各ラインの
先頭（ＢＤ信号３８が“ｌ”）が“ｌ′′（黒）のとき
に１つの“白”を挿入するためである。このために、Ａ
ＮＤゲート７０が開くと、白″Ｏ”挿入部５５はセレク
タ５２に“０”を出力する。こうして、自ＭＨ符号化Ｒ
ＯＭ５３は“０”に対するＭＨコード＝“００１１０１
０１”を出力する。こうして、白“０”が強制的に挿入
される。尚、クロックコントロール５８は前述のビット
インタリーブ部の同期クロック３５を生成する回路であ
るが、上記強制挿入のタイミングに、この’００１１０
１０１”がシフトレジスタ６３から出力され終るまで、
同期クロック３５の発生を止める。ラインメモリ４０又
は４１への入力とシフトレジスタ６３からの出力の同期
取りのためである。こうして、第４図（ａ）の原画像デ
ータ４から、圧縮率の高い圧縮データ１２が得られる。

尚、第９図の回路ではＭＨ符号化法が用いられたが、１
次元符号化として、例えばＷｙｌｅ符号等でもよい、又
、１次元符号化に限らず、ＭＲ記号、ＭＭＲ記号のよう
な２次元符号処理にも簡単に応用できる事は明らかであ
ろう、基本的には符号化法を選ばないのである。又更に
、カラー画像について、Ｒ，Ｇ、Ｂ又はＹ、Ｍ、Ｃ，Ｂ
の夫々に適用可能である。

次に、符号化処理の他の実施例について説明する。

くランレングス符号化〉・・・ブロック切り出しによる
実施例 本実施例のブロック切出しの手法は次のような事実に基
づく０則ち、信号列５は“白”ランと“黒°”ランのラ
ン長が長い、このような信号列５から変化点を抽出した
信号列１３に表われる特徴は次のようである。

■：論理値“ｌ”が前後を“Ｏ゛に囲まれて孤立的に偏
在する（則ち、“１０００　”となる）確率が高くなる
。これは、′白”ラン、′黒”ランが長ければ、それら
の両端にのみ変化点“１”が発生するからである。

■ニ一方、長い“白”ラン中の孤立した“黒”。

及び長い黒”ラン中の孤立した°゛白″その変化点を捕
えると、“１１００”となる。

上記■及び■から、信号列１３には“１０００”と“１
１００”が多く発生する事がわかる。

この事は第７図（ａ）をみれば自のずと明らかである。

そこで、このように多数発生するパターンに注目して、
所定の符号化を行ってビット長をそのパターン長より短
くすれば、符号化による圧縮率は向上する。

本実施例では、この所定の符号化を゛０″ラン中に“ｌ
”が発生すると、その“１”から所定の長さのブロック
を切出して、例えば第１０図（ｂ）の例では４ビツト長
のブロックを切出して、前述の“１ｏｏｏ”、”１１０
０”に対してそれぞれ、２ビツトの符号゛００”、”ｏ
ｉ”を割当てるというものである。一方、“Ｏ＋ｔシラ
ン対してはＭＨ符号化を行う事とする。

第１θ図（ａ）はそのブロック切出しの概念を説明する
図である。切出し方法は、１４　Ｑ　ＩＴシランら新た
に゛ｌパが発生すると、そこから４ビツトのブロックを
切出すというものである。従って。

その４ビツトパターンは第１０図（ｂ）の１６通りしか
ない、そこで、第１０図（ｂ）の如く、各ブロックパタ
ーンに対して、名称ＣＢ＋・・・Ｂ１６）及び割付は符
号を割当てる。ここで、“Ｏｎランと上記のブロックが
交互に並ぶようにするために、ブロックの次にすぐブロ
ックが発生するような場合（第１ラインの１１番目と１
５番目の間、及び第４ラインの３４番目と３８番目“の
画素の間）は、強制的に１つの“ＯＩｆを挿入する。こ
の“０”はＭＨ符号化されると“００１１０１０１″と
なる。更に各ラインの先頭がブロックで始まる場合（第
２ライン）も、同様に１つの°°０”を挿入する。第１
０図（Ｃ）は第ｉｏ図（ａ）の信号列を第１０図（ｂ）
の規則の基づいて符号化した場合を示す、尚、前述の実
施例と同様に第１０図（Ｃ）中、慣例にならい°゛０”
を“白”と称して示す。

第１１図にこのような実施例の回路構成図を示す０図中
、第９図に示された実施例の構成要素と実質的に同一で
あるものには同一番号を付す、主な相違点は４ビツトの
ブロック切出し及びブロックの符号化の為の回路である
。４ビツトシフトレジスタ５９は信号列１３を４ビツト
長保持する。

４ビツトシフトレジスタ５９の出力をブロック符号化Ｒ
ＯＭ６０は第１Ｏ図（ｂ）のような規則に従った符号化
を行う、一方、４ビツトカウンタ５６は検出器５０が、
信号列１３の“Ｑ　Ｉｆから“ｌ”への変化をとらえて
、その変化から４ビツトタイム後に信号６５を付勢する
。このタイミングにブロック符号化ＲＯＭ６０の出力を
ラッチ６１にラッチする。

ＡＮＤゲート５７は１つのブロックに続いて、Ｉｔ　Ｏ
ＩＩプラン入力せずに直ちに“ｌ”の信号が入力したと
き（信号列１３が“１′°であり、かつ信号６４が°”
　ｔ　”　）に、１つの“白パを挿入するためにある。

白°“Ｏ”挿入部５５、クロックコントロール部５８、
ゲート７０め役割等は第９図の場合と同様である。こう
して、所定のパターンが発生するとブロック切り出しに
より符号化を行うので、高圧縮化か達成できる。

上記の実施例では、ブロック長を４ビツトとしたが、こ
れには何ら限定はなく、回路規模及び原画像データの種
類に応じて決定される。ちなみに、８ビツト長に設定す
ると多少効率が向上する。又更に、′Ｏ″ランに対する
ＭＨ符号化も符号化のＲＯＭテーブルを多少変更するこ
とにより効率が更に向上する。又第９図の実施例と同様
、カラー画像にも適用できれば、符号化法もＭＨ符号化
法に限らず、他の１次元符号化法にも適用できる。

（実施例の効果〉 以上説明した種々の実施例の効果をまとめると以下のよ
うになる。

■：２値画像データにビットインタリーブ処理を施すの
で、白ラン及び黒ランがバラバラになったものであって
も、ラン長が復元されて長くなる。

特に閾値マトリックスによって中間調処理した画像デー
タに有効である。

■：ビットインタリーブ処理を施した信号列に対して更
に変化点抽出処理を施すので、”１”のラン調が短く、
“Ｏｔｌのラン長が長くなり、そのため符号化処理の高
圧縮化が期待できる。結果的には文書画像を対象とした
符号化アルゴリズムをそのまま使用しつつ、疑似中間調
画像を高能率で圧縮できる。

特に、ＭＨ符号化等の既存の符号化を行えば従来の回路
にわずかの変更を加えるだけで、高圧縮率の冗長度抑圧
方式が得られる。

■：前記■の変化点抽出により、所定のパターンをもっ
た信号列（ブロック）が多く発生する。そこで、このパ
ターンを短いビット長のコードに符号化する。又、′０
”ランに対しては従来通りＭＨ符号化等の１次元符号化
を適用して符号化する０則ち、原画像データの種類によ
っては、変化点抽出された信号列には“ｌＯ・・・”又
は“１１００・・・”が多発するので、このようなブロ
ックを短いビットの符号化により圧縮率を高める事がで
きる。

［発明の効果］ 以上説明したように本発明によると、ビットインタリー
ブによる並べ換えと、変化点の抽出によりラン長を長く
する事との組合せにより、高能率の冗長度抑圧符号化方
式が得られる。

【図面の簡単な説明】

第１図は本発明に係る実施例の原理構成図、第２図（ａ
）、（ｂ）は本発明に係る実施例及び従来例に供される
ディザマトリックス図、第３図（ａ）、（ｂ）は従来例
における中間調処理によるビット分散度が高くなる様子
を説明する図、 第４図（ａ）、（ｂ）はビットインタリーブの原理を説
明する図。 第５図（ａ）〜（Ｃ）はビットインタリーブのアドレス
生成の原理を説明する図。 第６図はビットインタリーブ再構成部の回路図、 第７図（ａ）、（ｂ）は変化点抽出部の動作及び回路構
成を説明する図、 第８図（ａ）、（ｂ）は本発明に係る１実施例の符号化
法の原理を説明する図、 第９図は第８図（ａ）、（ｂ）に示された動作を実現す
る実施例の回路図、 第１０図（１ｉＬ）〜（Ｃ）は本発明に係る１実施例の
符号化法の原理を説明する図、 第１１図は第１０図（ａ）〜（Ｃ）に示された動作を実
現する実施例の回路図である。 図中、 １・・・前処理部、２・・・符号化部、３・・・ビット
インタリーブ再構成部、４・・・２値画像データ、５・
・・ビットインタリーブされた信号列、６・・・変化点
抽出部、７・・・０”ラン゛′″１″ラン振り分は部、
８．９・・・ランレングス符号化部、ｌＯ・・・合成部
、１２・・・冗長度抑圧された２個性号である。 第 （Ｇ’）（ｂ） ５図 １−　　ＭＪＢ　　　５−　　瘤σ 二：二　　　ａｏｑ　　　　−σＡ　　　　ｔｌＮ３θ
（ＩＱ　　　　　　　　　　（ＩＩと　　　　　　　　
　ａａｐ（Ｃ）

Claims (4)

【特許請求の範囲】
1. （１）第１の２値信号列を前処理して符号化を行う冗長
   度抑圧符号化方式において、該前処理は、前記第１の２
   値信号列を所定の周期のビットインタリーブにて並べ換
   えて第２の２値信号列とし、更に第２の２値信号列を、
   該第２の２値信号列の論理値の変化及び非変化を新たな
   ２値とする第３の２値信号列に変換する事を特徴とする
   冗長度抑圧符号化方式。
2. （２）第１の２値信号列は画像信号を閾値マトリックス
   で２値化した２値画像信号列である事を特徴とする特許
   請求の範囲第１項に記載の冗長度抑圧符号化方式。
3. （３）論理値の変化を、第２の２値信号列の隣接する２
   つの２値信号の排他論理和により検出する事を特徴とす
   る特許請求の範囲第１項に記載の冗長度抑圧符号化方式
   。
4. （４）符号化は１次元符号化である事を特徴とする特許
   請求の範囲第１項に記載の冗長度抑圧符号化方式。