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

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は例えばカラー２進多値ディザ画像データのよう
な、複数行の２進多値化号の冗長度を抑圧する冗長度抑
圧符号化方式に関するものである。

［従来の技術］ ２値画像データに代表される２値信号の冗長度抑圧符号
化方式においては、元の要素列よりも統計的性質の偏り
の大きな信号列を得る事と、そのようにして得られた信
号列を簡単な符号化によって、高い圧縮比を得ることが
大きな課題である。

統計的性質の偏りの大きな信号列においては、同じ論理
値を持つ連続長がより長くなるから、例えはランレング
ス符号化を行えば、いわゆるエントロピーが減り、極め
て高い圧縮比が得られるからである。

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

この事情を、２進多値デイザの一例として４値デイザに
ついて、第２図（ａ）〜（ｃ）及び第３図（ａ）、（ｂ
）を用いて説明する。第２図（ａ）及び（ｂ）のマトリ
ックスは閾値マトリックス、特にドツト集中型のディザ
マトリックスを示す。同図（Ｃ）は、４値デイザにおけ
るドツト（画素）とデータ（２ビツトのパルス幅変調）
との関係を示している。第３図（ａ）の実線は第２図（
ｂ）の第１行目の閾値変化を表わす。このような閾値に
対して図の点線のような中間調画像が人力すると、第３
図（ｂ）に示されたような離散的な分布をもつ疑似中間
調画像データが得られる。このように゛白°゛゛黒゛°
がバラバラになると、ランレングス符号化では圧縮率が
低下するのに説明を要しないであろう。又、この様な疑
似中間調画像に対してＭＨ符号化等を行うと、高能率な
抑圧が望めないばかりか、逆にデータ量が増加する場合
があった。

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

一方、上記白／黒画像に比べるとカラー画像の情報量は
３〜４倍と膨大なものであり、又、最近は商品化のため
、１画素当りの情報も２進多値化の傾向にある。従って
、この情報を伝送、又は記憶するには高能率な冗長度抑
圧符号化方式が必要となるのは白／黒画像の比ではない
。しかし、現在カラー画像情報に対する有効な冗長度抑
圧符号化方式が無く、前述の白／黒画像に対する従来方
式を組み合わせたもの、即ち各色の画像データに対して
ピットインタリープ、ＭＨ符号化等を行っているのが実
状であり、これではあまり高能率化は望めないものであ
った。

［発明が解決しようとする問題点コ 上述の特にカラー画像データの問題はそれのみに留まら
ず、とりも直さず複数行で同時に発生する２進多値の要
素列にもあり得る問題である。

そこで、本発明は上述従来例の欠点に鑑みなされたもの
でその目的は、複数行であって各行の要素が２進多値で
ある要素列の冗長度を、効率よく抑圧する冗長度抑圧符
号化方式を提案する事にある。

［問題点を解決するための手段］ 上記課題を達成するための本発明の１つの構成は、Ｍ行
の要素列であって各行の１要素が２Ｎ値の２進多値デー
タで表わされる要素列の中から、“°０°°でない要素
を少なくとも１つ含み固定長の長さをもつＭ×Ｎ行の固
定長非ゼロブロックと、°′“０”である要素のみを含
むＭ×Ｎ行の可変長ゼロブロックとを切出す切出し手段
と、前記Ｍ×Ｎ行の可変長ゼロブロックに対してはラン
レングス符号化によりランレングス符号に変換するラン
レングス符号化部と、前記Ｍ×Ｎ行の固定長非ゼロブロ
ックの各行に対して所定の符号化を行ってＭ×Ｎ個の符
号化コードを生成するブロック符号化部と、前記ランレ
ングス符号と前記所定の符号化コードとを所定の順序で
合成して出力する合成部とからなる。

他の本発明の構成によると、Ｍ行の要素列であって各行
の１要素が２Ｎ値の２進多値データで表わされるＭ×Ｎ
行の第１の要素列を、行毎に所定の周期のビットインタ
リーブにて並べ換えてＭ×Ｎ行の第２の要素列とし、更
に第２の要素列を、行毎に該第２の要素列の論理値の変
化及び非変化を新たな２値とするＭ×Ｎ行の第３の要素
列に変換する前処理部と、前記Ｍ×Ｎ行の第３の要素列
の中から、“０”でない要素を少なくとも１つ含み固定
長の長さをもつＭ×Ｎ行の固定長非ゼロブロックと、”
　ｏ　”である要素のみを含むＭ×Ｎ行の可変長ゼロブ
ロックとを切出す切出し手段と、前記Ｍ×Ｎ行の可変長
ゼロブロックに対してはランレングス符号化によりラン
レングス符号に変換するランレングス符号化部と、前記
Ｍ×Ｎ行の固定長非セロブロックの各行に対して所定の
符号化を行ってＭ×Ｎ個の符号化コードを生成するブロ
ック符号化部と、前記ランレングス符号と前記所定の符
号化コートとを所定の順序で合成して出力する合成部と
からなる。

［作用コ 上記本発明の１つの構成によると、Ｍ行の２Ｎ値の可変
長ゼロブロックはランレングス符号化によりビット長が
短くされ、固定長非ゼロブロックのＭ×Ｎ個のブロック
については、ブロック符号化によりビット長が短くなる
。

本発明の他の構成によると、前処理部によるビットイン
タリーブ処理と変化点抽出処理により、符号化処理され
る前のデータのラン長が長くなり、符号化による圧縮効
率が」二る。

［実施例コ 以下添付図面を参照しつつ本発明に係る実施例を詳細に
説明する。本発明を適用した実施例は、符号化の手法そ
のものに特徴がある実施例と、符号化を行う前段階であ
る前処理及び前記符号化との組合せに特徴がある実施例
等である。

〈実施例の原理〉 そこで、本発明の概念の概略を簡単に把握するために、
前記前処理及び符号化を組合せたものを４値のカラー画
像データに適用した実施例について、第１図（ａ）、（
ｂ）を用いて説明する。同図（ａ）と（ｂ）の実施例の
相違は符号化の相違となって表われる。

く第１実施例の概略）・・・第１図（ａ）先ず、第１図
（ａ）の実施例から説明する。本実施例に人力される要
素列は、−例としてカラー画像データであって、例えば
４Ｘ２　（＝ａ）行のカラ−２値画像データ列（７ｃｕ
、　７　ＣＬ、　　７　ＭＬ＋。

７　ＭＬ、　７　ＹＵ＋　７　ＹＬ、　７　ＫＬＩ＋　
７　ＫＬ）である。ここで、Ｃはシアンを、Ｍはマゼン
タを、Ｙはイエローを、Ｋはブラックを表わし、又、Ｕ
は上位ビットを、Ｌは下位ビットを表わすものとする。

一方、本実施例においては、１画素はＣＭＹＫの４要素
からなるのであるが、ＣとＭの２つの画像データを１ま
とめにし、ＹとＫの２つの画像データを１まとめにする
。又、１要素は上位（Ｕ）、下位（Ｌ）の２ビツトであ
り、全体として、４（ＣＭＹＫ）Ｘ２　（ＬＩＬ）行の
要素列となる。又、列というときは主走査方向を言い、
行とは各要素の深さ方向及び各要素列の列に対する直角
方向を言うものとする。第１図（ａ）に示す符号化は前
記４行の２進画像データを上位、下位の各ビットづつ前
処理し、この前処理後のデータを更に符号化するもので
あるが、前述したように、ＣとＭ、ＹとＫを夫々１まと
めにして（即ち、４行と４行）前処理し、更に符号化す
るのであるから、ＣとＭ、ＹとＫは夫々処理としては同
じものであり、そのため以下の説明ではＣ，Ｍの組合せ
について説明する。

さて、ＣとＭの前処理部の構成は２×２の２進画像デー
タ（４ｃｕ、　４　ｃｂ、　４　Ｍｌｌ、　４　ＭＬ）
を各行毎に、所定周期のビットインタリーブにて並べ変
えるビットインタリーブ再構成部（３Ｃ，３Ｍ）と、更
にこの並べ変えられた２進画像データ（５ＣＵ＋　５　
ｃＬ、５ＭＵ、　５　ＭＬ）の夫々について、その論理
値の変化、非変化を新たな論理値とする２進画像データ
（７ｃｕ、　７　ＣＬ、　７　Ｍｕ、　７　ＭＬ）に変
換するための変化点抽出部（６Ｃ，６Ｍ）とからなる。

このような構成によると、入力の２×２行の２進カラー
画像データ（４ｃｕ、　　４ＣＬ、　　４Ｍ１１．　４
Ｍ＋、）が例えば第３図（ｂ）に示した如き中間調画像
をディザ法で面積変調したものであれば、先ずビットイ
ンタリーブ再構成部３Ｃ，３Ｍにより、白又は黒の偏り
の大きな４つの二進カラー画像データ（５ＣＵ＋　”　
ＣＬ＋　５ＭＬ１．”　ＭＬ）が得られる。その理由は
、ディザマトリクスが例えば第２図（ｂ）のような４ｘ
４であれば、ディザ処理後の画像データには第３図（ｂ
）のような周期性が含まれるので、主走査方向の４ビツ
ト毎のビットインタリーブにより、２つの二進信号列（
５ｃｕ、　５　ＣＬ＋５　Ｍｕ、　５　ＭＬ）には０°
°又は１°°が偏在し、”　ｏ　”ラン長、及び゛１°
°ラン長が長くなるなるからである。

更に変化点抽出部（６Ｃ，６Ｍ）により変化点抽出によ
る二値化、例えば信号列（５ｃｕ、　５　ｃｌ、。

５　Ｍ１１＋　５　ＭＬ）の論理値変化点を１°゛とし
、その他の無変化点を“°０°°とする二値化をすれば
、論理値”　１　”は上記変化点のみとなる。そうする
と、゛０゛ランが更に増えるので、ランレングス符号化
部１１ＣＨによるランレングス符号化か効率的となり、
高いデータ圧縮率が得られる。

第１実施例に係る符号化の概略を更に説明する。符号下
部２ＣＭについてはその構成は、２つの二進画像データ
列（７ＣＬＩ＋　７　ＣＬ＋　７　ＭＬＩ、　７　ＭＬ
）で表わされる要素列中で、いずれかが′１°°である
ピットを検出する０−１検出部９ＣＭと、０→１検出部
９ｃＭが°゛０°°→“°１゛の変化を検出した時点で
、それまでのゼロ要素のみを含む２Ｘ２　（＝４行）の
可変長ゼロブロックを切出すランレングス符号化部１１
ＣＭと、前記４行の可変長ゼロブロックに続いて、４行
の２進化号列（７ｃυ＋７ＣＩ−＋７　ｙｕ、　７　Ｍ
Ｌ）について、所定の長さく例えば４列）の固定長非ゼ
ロブロック（４つの１行４列ブロック）を切出すブロッ
ク符号化部８ＣＭとこれらの符号化コードを合成する合
成部１２ｃＭとからなる。

ランレングス符号化部１１ＣＭは、４行の可変長ゼロブ
ロックに対してランレングス符号化により冗長度を抑圧
し、前記ブロック符号化部８ＣＭは夫々の切出された４
つの１行４列の固定長非ゼロブロックの夫々に所定の符
号化を施して、４つのブロック符号を得る。合成部１２
ＣＭではランレングス符号、４つのブロック符号を所定
の順て並ぺて合成し、画像データ列１３ｃ、を出力する
。

第１図（ａ）に示した実施例の構成によると、゛“０”
ランについてはランレングス符号化により高能率に圧縮
される。又、４つの二進カラー画像データ列（７Ｃ１，
７ＣＬ、　　７　ＭＵ、　７　ＭＬ）の信号源の種類（
例えば、画像データであれば原画像の種類）によっては
、非ゼロブロックが特定のパターンを多く含む場合があ
る。このような特定パターンに対して、例えばブロック
の固定長より短い符号長の符号コードを各１行４列のブ
ロックに割当てるような符号化をブロック符号化部ａｃ
ｉｉで行えば、１°゛を含む画像データ列に対しても高
能率に圧縮できる。例えば第８図（ａ）には上記非ゼロ
ブロックが取得るパターンを示し、そのパターンをもつ
１行４列のブロックに対して行う符号化の例を示す。

〈第２実施例の概略〉・・・第１図（ｂ）第１図（ｂ）
の実施例は前処理については同図（ａ）の実施例と同じ
であるので、その説明を省略する。符号化部２ＣＭにつ
いては、前記４つの１行４列の非ゼロブロックのパター
ンを調べるパターン判別部１７ｃＭと、そのようなブロ
ックに対しては、そのようなパターンを有している事を
示すフラグを生成するフラグ生成部１４ｃＭを有してい
るところに、差異がある。

さて、第１実施例でのブロック符号化は、多く発生する
パターンに対して、そのブロック長よりも短い符号長の
符号にすることで、データ圧縮を達成するものであった
が、第２実施例では、そのような特定のパターンもった
ことを示すフラグをフラグ生成部１４ｃＭにて発生し、
符号化後の圧縮信号１３ｃＭにもたせることにより、更
なる圧縮を目指すものである。尚、フラグの例を第１２
図（ａ）、（ｂ）に示す。

１　　ソ 〈各構成部分の説明〉 以下順次図面に従って説明するものであるが、第１図（
ａ）、（ｂ）にも示されているように、Ｃ信号とＭ信号
との組合せはＹ信号とに信号との組合せに同等である。

そこでＣ信号とＭ信号との組合せで説明を行う。又、第
１図（ａ）、（ｂ）に示した実施例の各構成要素は共通
部分を多くもつので、説明の重複を防ぐために、以下説
明する添付の図面は各１色又は２色に対する回路例等で
ある。

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

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

第４図（ａ）は例えば第２図（ａ）又は（ｂ）のディザ
マトリックスにより４値化されたＣ信号４　ＣＵ＋　４
　ＣＬ％及びＭ信号４ＭＬＩ＋４ＭＬであって、主走査
方向（即ち、列方向）へ４０画素分の大きさを持つもの
を示す。図に付された番号は主走査方向には画素の番号
を便宜上付したものである。このＣ信号４　ＣＵ＋　４
　ＣＬ及びＭ信号４ＭＵ＋　４ＭＬは、夫々４ビツト周
期の周期性をもつ。前述したように、このようなディザ
画像は中間調を表現するにはすぐれるが、ラン長が短く
なってしまっているのは図をみても明らかである。

この２進化号４　ＣＵ＋　４　ＣＬ及び４ＭＵ＋　　４
ＭＬに対して夫々４ビツトのインタリーブを行うと、第
４図（ａ）の１．２，３，４．・・・の画素配列が第４
図（ｂ）の如き１，５，９，１３．１７．・・・なる配
列となり、°゛白゛°ラン及び°゛黒゛′ラン長が増加
しているのがわかる。４ビツトとしたのは、閾値処理に
用いたディザマトリックスが４ビツトであるからである
が、上記ビットインタリーブはディザマトリックスと同
一の長さで行った。このようなビットインタリーブ長の
決定の他に、マトリックスの大きさの整数倍又は整数分
の１の大きさに設定する事もできれば、又は閾値マトリ
ックス内の近似した値をもつ閾値に対応した周期でグル
ープ化する手法もある。

さてこのようなビットインタリーブを行う回路を第６図
（但し、Ｃ信号に対するもののみ）に示す。第６図のビ
ットインタリーブ再構成部３゜は、Ｃ信号４Ｃｕｒ　４
　ＣＬの並べ換えのために２組のラインメモリ４０．４
１を用いる。１組のラインメモリは不図示であるが、上
位ビット用と下位ビット用のラインメモリを有するもの
とする。２組用いるのはＣ信号４　ＣＵ、　４　ＣＬの
入力と並べ換え動作と並べ換えられた画像データ列”Ｃ
Ｕ＋５ＣＬを読み出す動作とを同時に行うためである。

即ち、１組のラインメモリに入力（書込み）するときは
、他方の組ラインメモリは出力（読み出し）に使われる
。１つのラインメモリが同時に書込みと読出しに使われ
るのを防ぐために、書込み用のアドレスカウンタ２５と
、読み出し用のアドレスカウンタ２６と、これらカウン
タ２５，２６の出力を各ラインメモリ４０．４１に振り
分けるセレクタ２７．２８，２９．３０，３１．３２及
び排他制御を行うラインメモリ制御部４２等がある。ラ
インメモリ制御部４２は１ライン毎に発生するＢＤ信号
３８に同期して第２ラインメモリ書込み信号３６又は第
１ラインメモリ書込み信号３７を交互に１°°とする。

又セレクタ２７．２８．３１は、第２ラインメモリ書込
み信号３６又は第１ラインメモリ書込み信号３７の論理
値に応じて出力を選択するセレクタであり、一方、セレ
クタ２９．３０．３２は同じく、第２ラインメモリ書込
み信号３６又は第１ラインメモリ書込み信号３７の論理
値に応じて入力を選択するものである。このようにする
と、第１ラインメモリ書込み信号３７が°“１゛のとき
は、第２ラインメモリ書込み信号３６は０″であり、セ
レクタ２７は出力”　ｏ　”を、セレクタ２９は入力“
“０”を、セレクタ３１は出力“ｏ　”を選ぶために２
進化号４ＣＵ＋　４　ＣＬ及び４ＭＵ＋　　４ＭＬが第
１ラインメモリ４０に書き込まれ、一方読み出しアドレ
スカウンタ２６の出力はセレクタ２８及びセレクタ３０
により第２ラインメモリ４１に入力し、セレクタ３２は
第２ラインメモリ４１を選ぶ。こうして書込みと読み出
しの同時処理が行え、高速化に寄与する。

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

又、アドレスカウンタ２５．２６及びラインメモリ４０
．４１の駆動クロックは同期クロック３５ＣＭである。

この同期クロック３５ｃＭは符号化部２ＣＭで生成され
るもので、符号化部２ＣＭでの符号化の際に、画像デー
タ列があるパターンのときは同期を取るために、強制的
に所定のコードを挿入する必要が生じ、その場合、その
強制挿入コードを合成部１０が送出し終るまで、ビット
インタリーブ再構成部３ｃ、３ｖの動作を停止するため
に用いられる（詳しくは後述する）。

以上述べたようなビットインタリーブ再構成部がカラー
信号の各色の各上位、下位ビットについてビットインタ
リーブを行う。ところで、第１図（ａ）等をみてもわか
るように、２進化号７ｃ０゜７ｃＬ及び７ＭＬ＋＋　　
７ＭＬとは同時に符号化部２　ＣＭ　テ符号化される。

又、後述するように、ランレングス符号化部１１ｃＭで
はＣ信号とＭ信号をまとめてランレングス符号化する。

又、°“ビ′を含む１行４列のブロックの符号化は所定
の長さ毎に行う。即ち、Ｃ信号とＹ信号のビットインタ
リーブ前処理は同期しており、従って第６図に示した構
成要素のうち、第１ラインメモリ４ｏと第２ラインメモ
リ４１以外は共通化でき、この共通化により回路の小規
模化に寄与する。信号Ｙと信号にとの組合せについても
同様である。

〈変化点抽出〉 第７図（ｂ）に２進化号７　ＣＬｌ＋　７　ＣＬ、につ
ぃての変化点抽出のための回路の一例を、同図（ａ）に
その結果を示す。第７図（ｂ）の変化点抽出部６ｃの一
例は信号Ｃの主走査方向に１画素隣接する画素同士の間
の変化点を抽出する場合である。

１つ隣接する画素を検出するためにフリップフロップ２
０ｕ又は２０Ｌを用い、変化点を検出するためＥＸ−Ｏ
Ｒゲート（排他論理和ゲート）２ｔｕ　　（又は２１Ｌ
）を用いる。４ビツトインタリーブをかけられた２進化
号列５ＣＬＩ１５ＣＬに対し、注目画素と同一走査線に
あるその直前の画素とＥＸ−ＯＲをとる。即ち、第２図
（ａ）の閾値ＤＩＪに２進化号列５　Ｃｕｒ　５　ＣＬ
の各画素を対応させれば、ＥＸ−ＯＲゲート２１０　　
（２１Ｌ　）（７）出力ＤＸＩＪ　（７ＣＵ、　７ＣＬ
）は Ｄ　ｘｌＪ　”　Ｄ　ｌｊ　　■　Ｄ　Ｉ−１，Ｊであ
る。第４図（ｂ）と第７図（ａ）を比較してもわかるよ
うに、”　ｏ　”ラン（このような０°。

ランを゛白′°ランとも呼ぶ）が長くなっていて、ラン
レングス符号化に適する事が一目瞭然である。又、ビッ
トインタリーブされた画像データ列５　ＣＬＩ＋　　５
ＣＬは°゛白°゛ランと゛°黒°°ランのラン長が長い
。このような画像データ列５　Ｃｕｒ　５　ＣＬから変
化点を抽出した画像データ列（７Ｃｕｒ　７ＣＬ）に表
われる特徴は次のようである。

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

■；一方、長い゛白°゛ラン中の孤立した゛°黒″°。

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

上記■及び■から、画像データ列（７ｃｕ。

７　Ｃｕｔ　７　ＭＵ、　７　ＭＬ）には”　１０００
　”と”１１０“０”か多く発生する事がわかる。この
事は第７図（ａ）をみれば自ずと明らかである。上記の
事実は、後述する符号化と大きく関わる。

以上、冗長度抑圧符号化のための前処理について説明し
た。そこで、次に、符号化部について、第１図（ａ）、
（ｂ）に対応した実施例を２つ説明する。上記の前処理
部はある意味では、各２進画像データに対して独立して
処理するものであった。以下説明する符号化の実施例は
、２色の信号（例えば、信号Ｃと信号Ｍ）を１つの信号
として処理するものである。

〈第１実施例の符号化〉 第９図（ａ）に、第７図（ａ）の変化点抽出された画像
データ列（７ＣＵ、　７ＣＬ、　７ＭＵ、　７ＭＬ。

７　ＹＬＩ、　　７　ＹＬＩ　　７　ＫＵ＋　　７　Ｋ
Ｌ）が１ライン分示されていて、この画像データ列から
の可変長ゼロブロック（又は固定長非ゼロブロック）の
切出し方が示されている。図中、慣例に従い°０°′を
°“白°°、“ビを“黒″と称して表わす。桁数を表示
し易いからである。２進化号（７Ｃｕｔ　７　ＣＬ、　
７　ＭＵ、　７ＭＬ）に対しては、これらの信号中で同
時に０゛。

のみしか含まないものを白（“’ｏ”）ランとして切出
す。例えば“白６°°は４行の白のランが６個続くとい
う意味である。このような白（°°０″゛）ランに対し
て例えば１４Ｈ符号化による圧縮を行う。

一方、いずれかの行に１つでも１°°が表われると、そ
こから４ビツト長で４つの１行４列の固定長非ゼロブロ
ックを切出す。このようなブロックは必ずどこかに１つ
以上の１′′を含むものであるが、１行全てが０′°で
あるものもあり得る。前述したような前処理を行うと、
各色毎に全体で“°Ｏ°゛ランが多くなるが、上記のよ
うな全色をまとめたブロックの切出しを行うと、１行全
てがｏ　ｏ　ｏ　ｏ’”であるにも関わらず非ブロック
に含まれてしまうものが多くなる。例えば、６個目のブ
ロック（Ｂｏ）にはゼロのみの１行４列のブロック（＝
ｏｏＯＯ）が３つも含まれてしまう。

これは同一画素においては、Ｃ信号とＭ信号の確率過程
は独立であるから、色間で“０”°と１°。

の発生がランダムであるためである。この°００００゛
°のパターンが多いという事は、更なる圧縮の可能性を
示唆している。これについては、別の実施例の説明に譲
る。

こうして得られた固定長非ゼロブロック内の発生し得る
パターンは第８図（ａ）に示した１６種類のパターンの
組合せである。このような１６種類のパターンに対して
便宜上Ｂ。−Ｂ＋５の記号名称を付け、第９図（ａ）に
示す。この規約に従って、例えば第９図（ａ）中の最初
の固定長非ゼロブロックは（Ｂｏ　、Ｂ＋　、Ｂａ　、
Ｂ９　）と表わせる。

尚、画像データによっては、第９図（ａ）のＣ信号の如
く、可変長ゼロブロックから始まらない場合がある。こ
のような場合、非ゼロブロック（本例では、Ｂｏ、Ｂ＋
、Ｂａ、Ｂ９のブロック）の前に強制的に１つの゛白０
”（ＭＨ符号では“’００１１０１０１°°）を挿入す
る。又、非ゼロのブロックが連続するような場合も同様
にする。可変長ゼロブロックと固定長非ゼロブロックと
が必ず交互に発生して、復号化の際に同期がとれるよう
にするためである。

ところで前述したように、前処理によりプロツり中には
’１０００”及び“’ｔｔｏｏ”が多く発生する。又、
いずれか一方の色に°゛１°°が発生すると、そこをブ
ロックの一部としたから、００００°′も多い。そこで
、このように多数発生するパターンに注目して、所定の
符号化を行ってビット長をそのパターン長より短くすれ
ば、符号化による圧縮率は向上する。さて、前記例では
００ｏｏ”、　　“”ｔｏｏｏ”及び“”ｔｔｏｏｏｏ
の３種類のパターンが多く発生する。第８図（ａ）の例
では、２ビツトの符号゛０“０”をＢ。＝°“００００
”に、０１°°をＢ３＝　”ｔ　ｔ　ｏ　ｏ”に割当て
るというものである。このようにして高圧縮化を達成す
る。

又、第８図（ａ）中のいずれのコードも互いにユニーク
なものであって、混同は生じない組合せになっている。

圧縮コード“１０°°はＢ。、Ｂ３以外のパターンと判
別できなくなるから採用しない。このようにすると、多
く発生するパターン“’ｏ　ｏ　ｏ　ｏ″及び“ｔｔｏ
ｏ”が２ビツトに圧縮される。一方、“ｏ　ｏ　ｏ　ｏ
　”、”　１１００　”、゛１０００°°以外のパター
ンが同一確率で多数発生するような画像にあっては、圧
縮符号コードを３ビツトとする。そうすると、“ｏ　ｏ
　ｏ　”、゛。

０１１゛、”０１０”　、　　”０１１　”　（７）４
種類の圧縮コードが可能となる。個々の圧縮では２ビツ
トの例よりも圧縮率が悪化するが、全体の圧縮率は更に
向上する。第９図（ｂ）は上記の規約に従って各信号の
圧縮パターンを表した図である。第９図（ｂ）中、ＭＨ
とはＭＨ符号化を表す。このような符号化を各ライン毎
に行う。第９図（ｂ）をみれば本実施例の符号化が単な
るＭＨ符号化よりもはるかに圧縮率を向上しているのが
わかる。

第１０図（ａ）はかかる符号化のための回路（第１図（
ａ）の８ＣＭ）の−例である。図中、ＲＬ（ランレング
ス）カウンタ５１．セレクタ５２、°°白”ＭＨ符号化
ＲＯＭ５３等が゛０゛ラン、即ち可変長ゼロブロックを
、ＭＨ符号化により符号化してラッチ５４に符号コード
をラッチする。検出回路５０は第１０図（ｂ）にその詳
細図を示すように４つの信号列（７ｃｕ、　７　ｃｔ＋
　７　ＭＵ＋７　ＭＬ）のいずれかの変化（“０パ→“
０°°、“ｏ　”　→゛１°゛、”　ｔ　”　→“０°
°、”　１　”→”　１　”　）を検出する。ＲＬカウ
ンタ５１はＣＬＫを駆動クロックとするカウンタで、そ
のＥＮ（付勢）端子に１゛°が人力するとカウント可と
なり、ＣＬ（クリア）端子に１°゛が入力するとクリア
される。従って、ＲＬカウンタ５１は、信号列（７ｃｕ
、　７　ＣＬ、　７　ＭＩＪ＋　７　ＭＬ）全てが°０
°°である間はカウントし続け、そのカウント値に応じ
たＭＨ符号コニドをラッチ５４に人力する。２進化号列
（７ＣＵ＋　７　ＣＬ＋　７ＭＬ＋＋　７ＭＬ）のいず
れかが°゛０°°から１゛°に変化すれば、その時のカ
ウント値の符号コードが信号７２を介してラッチ５４に
ラッチされ、同時にカウンタ５１はクリアされる。　一
方、４ビットシフトレジスタ６ｏ、６３．６６．６９は
夫々、信号列（７ｃｕ　＋　７　ｃい７　ＭＵ、　７　
ＭＬ）を４ビツト長の間保持する。ブロック符号化ＲＯ
Ｍ６１，６４，６７．７０は４ビツトシフトレジスタ６
０〜６９の出力を夫々第８図（ａ）のような規則に従っ
た符号化を行う。一方、４ビツトカウンタ５５は検出回
路５ｏが、信号列（７ｃｕ、　７　ＣＬ＋　７　ＭＵ＋
　７　ＭＬ）の”　ｏ　”から１°゛への変化をとらえ
て、その変化から４ビツトタイム後に信号７３を付勢す
る。このタイミングにブロック符号化ＲＯＭＢ１，６４
，６７．７０の出力を夫々ラッチ６２，６５，６８．７
１にラッチする。合成器７４は、夫々符号化したコード
を合成してシフトレジスタ７５に格納するためのもので
ある。、ＭＨ符号は可変長であるからこのような合成器
が必要となる。シフトレジスタ７５はパラレル−シリア
ル変換を行う。

ＡＮＤゲート７６は非ゼロブロックがラインの先頭から
開始するときに、前述したように白”　ｏ　”に対応す
るＭＨコードを挿入するためにある。ＡＮＤゲート５９
は、１つの非ゼロブロックに続いて゛°０″°ランが入
力せずに直ちに°゛１°′の信号が入力したとき（信号
列７　ＣＬＩＩ　７　ＣＬ、７ＭＵ＋７ＭＬのいずれか
が“°１°°であり、かつ信号７７が１°゛）に、白”
　ｏ　”に対応するＭＨコードを挿入するためにある。

白”　ｏ　”挿入部５６はこの１つの“白゛°を挿入す
るためにあり、ＡＮＤゲート５９．７７のいずれかが開
くと、セレクタ５２に”　ｏ　”を出力する。こうして
、白ＭＨ符号化ＲＱＭ５３は°゛０″に対応するＭＨコ
ード＝”ｏｏｉｌｏｌｏｌｏｏを出力し、白゛“０”が
強制的に挿入される。尚、クロックコントロール５７は
前述のビットインタリーブ再構成部３ｃ、３Ｍの同期ク
ロック３５ｃＭを生成する回路であるが、上記強制挿入
のタイミングに、この°’００１１０１０１°。

がシフトレジスタ７５から出力され終るまで、同期クロ
ック３５０Ｍの発生を止める。ラインメモリ４０又は４
１への人力とシフトレジスタ７５からの出力の同期取り
のためである。こうして、第４図（ａ）のＣ信号及びＭ
信号から圧縮率の高い圧縮データ１３ｃＭが得られる。

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

〈第２実施例の符号化〉 前述の実施例は、第８図（ａ）に示した圧縮規約に基す
き、ブロック中に多数発生する”　ｏ　ｏ　。

Ｏ°゛、１１００°°を夫々コード”ｏ　ｏ”　、　　
”。

ｌｏｏに圧縮するものであった。本実施例は、この００
００°′を更に効率良く圧縮しようというものである。

そのために、４つの１行４列の非ゼロブロックの切出し
については、前記実施例と同様に第９図（ａ）のように
行う。そして、１″゛を含む４つの１行４列のブロック
のいずれかの中に４ビツトの００００°′　（これを便
宜上、“′ゼロパターン°°と呼ぶ）があれば、それを
前記実施例のように００°°とコード化せずに、その代
りに“’ｏ　ｏ　ｏ　ｏｏｏがあった事を示すフラグを
設け、そのフラグの値を°“Ｏｏｏにする。１行４列中
に１つでも１°゛を含むもの（そのような１行４列のブ
ロックを便宜上、°゛非ゼロパターン°゛と呼ぶ）に対
応するフラグは１′°とする。このようなフラグな各列
に対して設ける。又、非ゼロパターンに対応するコード
は第８図（ｂ）の如く行う。

第１１図（ａ）は圧縮後のフォーマットを示す。Ｃ信号
の上位ビットである信号７ｃＵに対応する符号コードを
＃１コード、下位ビットに対応する信号７ＣＬに対する
符号コードを＃２コード、Ｍ信号の上位ビットに対応す
る信号７＋ｉｔｕのそれを＃３コード、下位ビットに対
応する信号７ＭＬのそれを＃４コードとし、これらの符
号コードに夫々対応するフラグを＃ＩＦ、＃２Ｆ、＃３
Ｆ、＃４Ｆとする。例えば、＃ＩＦが“′“０”であれ
ば、１行４列の信号７ｃｕがゼロパターン＝ｏｏｏｏで
あり、更に対応する＃１コードは無い事を示す。

４行４列のブロックはいかなる組合せでも、必ずゼロパ
ターンと非ゼロパターンとの組合せであるから、そのフ
ラグの組合せは’１０００°°。

“０１００′’、”００１０°’、”０００１°゛。

”　１１００°°、“’１００１°°、“１０１０°°
。

”ｏｔｏｔ”、’“００１１°°、“’０１１０”。

“１１１０”、’“１１０１°°、“１０１１　”　。

“０１１１°”、”１１１１’“０１５通りである。

第１１図（ｂ）に、フラグと符号コードをも含めたフォ
ーマット例を示す。

データ圧縮をこのように行うと、ゼロパターンはコード
としては現われないので、復号化時に同期ずれが生ずる
恐れがある。しかし、先頭には必ずフラグがあり、その
長さは必ず４ビツトであり、そのフラグの論理値により
フラグに続＜＃１コード〜＃４コードの長さくつまり、
４行４列のブロック内にいくつゼロパターンがあるかが
）がわかる。又第８図（ｂ）をみてもわかるように、８
１〜ＢＩ５に対応する符号コードは全てユニークである
。従って、ゼロパターンを、それに対応するコードが無
いものとして変換しても、復号化に際し同期がずれる事
は全くない。

第９図（ａ）に示したブロックの切出しを、本実施例の
圧縮化に従って圧縮化すると、第１３図のようになる。

図中の例えばＢ。／Ｂ　ｌ　／ｓａ　／Ｂ９はフラグ部
が°“０１１１”、＃１コードは無く、＃２コードは’
ｏｏ″′、＃３コードが１０００１°°、＃３コードが
°’１１００１°”である。

さてこのようなフラグによる符号化を行う回路の一例を
第１２図に示す。即ち、前述の第１の実施例（第１０図
（ａ）及び（ｂ））と基本的構成を同等にし、ブロック
符号化ＲＯＭ６１，６４゜６７．７０を第１２図のよう
にして、その出力の一部にフラグ出力を追加するのであ
る。そして、例えばゼロパターンがこのブロック符号化
ＲＯＭに人力したら、レングスは“”１”（フラグの１
ビツトのみであるから）、フラグは“’ｏ”、コードは
”　ｏ　”とする。ＲＯＭのレングス出力は合成器７４
に入力され、合成するときの情報となる。即ち、合成器
７４では’ｏ　ｏ　ｏ　ｏ″′を”　１　”としてしか
出力しない。こうして、ｏ　ｏ　ｏ　ｏ　”を多く含む
ような画像信号に対しては更に効果的な圧縮が可能とな
る。

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

又、２値のカラー信号Ｃ，Ｍ、Ｙ、には周知のように不
図示のメモリに蓄えられているものを読み出すが、又は
リアルタイムで画像を読取って２値化処理したものであ
ってもよい。

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

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

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

■二ビットインタリーブ処理を施した画像データ列に対
して更に変化点抽出処理を施すので°°１°。

のラン調が短く、“′０゛のラン長が長くなり、そのた
め符号化処理の高圧縮化が期待できる。結果的には文書
画像を対象とした符号化アルゴリズムをそのまま使用し
つつ、疑似中間調画像を高能率で圧縮できる。

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

■：前記■の変化点抽出により、所定のパターンをもっ
た画像データ列（ブロック）が多く発生する。そこで、
このブロック内のパターンを各行毎に短いビット長のコ
ードに符号化して、合成する。又、゛０°′ランに対し
ては従来通りＭＷ符号化等の１次元符号化を適用して符
号化する。即ち、原画像データの種類によっては、変化
点抽出された画像データ列には００００”、”１００“
０”又は’１１００°°が多発するので、このようなブ
ロックを短いピットの符号化により圧縮率を高める事が
できると共に、２行以上の信号を一本化できる。

■二更に°’ｏ　ｏ　ｏ　ｏ”°なるゼロパターンを１
ビツトのフラグにおきかえる事によって、より高度の圧
縮化が可能となる。

［以下余白］ ［発明の効果］ 以上説明したように本発明によると、同時に発生するＭ
行の要素列であって、その要素列中の１要素は２Ｎの多
値である要素列について、列方向にＮＸＭ行の可変長ゼ
ロブロックと、いずれかに１°°を含むＮＸＭ行の固定
長非ゼロブロックとを切出して、ゼロブロックに対して
はランレングス符号化を行い、固定長非ゼロブロックに
対しては所定の符号コードに変換して圧縮する事により
高能率に冗長度を抑圧した信号が得られる。

本発明の他の構成によると、各行の要素列に対して、ビ
ットインタリーブによる並べ換えと変化点の抽出とによ
る゛“０”ラン長を長尺化に、更に上記符号化を加える
と、特定のバラツキをもつ２値化号に対して、更に高能
率の冗長度抑圧符号化方式が得られる。

【図面の簡単な説明】

第１図（ａ）は第１実施例野原理構成図、第１図（ｂ）
は第２実施例の原理構成図、第２図（ａ）、（ｂ）は本
発明に係る実施例及び従来例に供されるディザマトリッ
クス図、第２図（Ｃ）は４値画像データのデータとピッ
トの対応を説明する図、 第３図（ａ）、（ｂ）は従来例における中間調処理によ
るビット分散度が高くなる様子を説明する図、 第４図（ａ）、（ｂ）は第１．２実施例に共通なビット
インタリーブの原理を説明する図、第５図（ａ）〜（Ｃ
）はビットインタリーブのアドレス生成の原理を説明す
る図、 第６図はビットインタリーブ再構成部の回路図、 第７図（ａ）、（ｂ）は第１．２実施例に共通な変化点
抽出部の動作及び回路構成を説明する図、 第８図（ａ）第１実施例に係る符号化の符号コードの一
例を説明する図、 第８図（ｂ）第２実施例に係る符号化の符号コードの一
例を説明する図、 第９図（ａ）は夫々実施例におけるブロック切出しの手
法を説明する図、 第９図（ｂ）は第１実施例における符号化後のコード配
列を説明する図、 第１０図（ａ）、（ｂ）は第１．２実施例に共通な符号
化のための回路図、 第１１図（ａ）、（ｂ）は第２実施例における符号化の
フォーマットを説明する図、 第１２図は第２実施例における符号化に供されるＲＯＭ
の構成図、 第１３図は第２実施例の符号化の一例を説明する図であ
る。 図中、 ＩＣＭ＋ＩＹＫ・・・前処理部、２ＣＭ＋　　２ＹＫ・
・’符号化部、３　ＣＭ＋　　３　ＹＫ・・・ビットイ
ンタリーブ再構成部、４　ＣＬＩ　＋　４　ＣＬＩ　４
　Ｍｔｌ＋　４　ＭＬＩ　４　ＹＬＩ＋　４　ＹＬ＋　
４　ＫＵ＋４ＫＬ・・・４値力ラー２進画像データ、５
　ＣＬＩＩ　５　ＣＬ。 ５ＭＵ・　５ＭＬ・　５Ｙυ・　５Ｙｂ・　５にυ・　
５にし・・・ビットインタリーブされた画像データ列％
　６　ＣＭ＋　　６　ＹＫ・・・変化点抽出部、７　ｃ
ｕ、　７　ＣＬＩ　７　ＭＬＩ、　７　Ｍい７ＹＵ＋７
７い　７ｘｕ、７に、・・・変化点抽出された信号、８
　ＣＭ＋　”　ＹＫ’・・ブロック符号化部、１４ＣＭ
、　　１４ＹＫ・・・フラグ生成部、９　ＣＭ＋　９　
ＹＫ・・・０→１検出部、１１ＣＭ、１１ＹＫ・・・ラ
ンレングス符号化部、１２ｃｉｉ。 １２ＹＫ・・・合成部、１３ｃＭ、１３Ｙに・・・冗長
度抑圧された２値化号、１７ＣＭ、　　１７ＹＫ・・・
パターン判別部である。 第２図（ａ） 第２ −　　ロ ー　　口 −ロ 図（ｃ） （ａ）　　　　　　　（ｂ） 第５ Ａ 劇［と出しマトレ２ｉｊウンク １回目　　　　２回目　　　３回目　　　４回目（ｃ） 図 Ｑ− ロコ］コ−８１−−−１１０００ ロコ］コ一　８２−−−　１０１００ 田ｌ］コー　８３−−−　０１ ０コｌコー　８４−−−　１００１０ ロコＩコー　８５−−−　１１０１０ 口ｍｌコ一　８６−−−　１０１１０ 日ｍコー　８７−−−　１１１１０ 第８図（０） 口］＝コロ−−８１−−−００ ［匡［１−８２−１０１００ 国Ｉ＝ロー　８３−−−　０１

Claims (6)

【特許請求の範囲】
1. （１）Ｍ行の要素列であつて各行の１要素が２＾Ｎ値の
   ２進多値データで表わされる要素列の中から、“０”で
   ない要素を少なくとも１つ含み固定長の長さをもつＭ×
   Ｎ行の固定長非ゼロブロックと、“０”である要素のみ
   を含むＭ×Ｎ行の可変長ゼロブロックとを切出す切出し
   手段と、 前記Ｍ×Ｎ行の可変長ゼロブロックに対してはランレン
   グス符号化によりランレングス符号に変換するランレン
   グス符号化部と、 前記Ｍ×Ｎ行の固定長非ゼロブロックの各行に対して所
   定の符号化を行つてＭ×Ｎ個の符号化コードを生成する
   ブロック符号化部と、 前記ランレングス符号と前記所定の符号化コードとを所
   定の順序で合成して出力する合成部とを有する冗長度抑
   圧符号化方式。
2. （２）各要素はカラー画像データである事を特徴とする
   特許請求の範囲第１項に記載の冗長度抑圧符号化方式。
3. （３）ランレングス符号化部はＭ×Ｎ行の可変長ゼロブ
   ロックの１行毎の又は複数行毎の要素数をランレングス
   符号化する事を特徴とする特許請求の範囲第１項に記載
   の冗長度抑圧符号化方式。
4. （４）ブロック符号化部における符号コードの長さは、
   少なくとも固定長非ゼロブロックの長さより短い符号コ
   ードを一部に含む事を特徴とする特許請求の範囲第１項
   に記載の冗長度抑圧符号化方式。
5. （５）Ｍ行の要素列であつて各行の１要素が２＾Ｎ値の
   ２進多値データで表わされるＭ×Ｎ行の第１の要素列を
   、行毎に所定の周期のビットインタリーブにて並べ換え
   てＭ×Ｎ行の第２の要素列とし、更に第２の要素列を、
   行毎に該第２の要素列の論理値の変化及び非変化を新た
   な２値とするＭ×Ｎ行の第３の要素列に変換する前処理
   部と、前記Ｍ×Ｎ行の第３の要素列の中から、“０”で
   ない要素を少なくとも１つ含み固定長の長さをもつＭ×
   Ｎ行の固定長非ゼロブロックと、“０”である要素のみ
   を含むＭ×Ｎ行の可変長ゼロブロックとを切出す切出し
   手段と、 前記Ｍ×Ｎ行の可変長ゼロブロックに対してはランレン
   グス符号化によりランレングス符号に変換するランレン
   グス符号化部と、 前記Ｍ×Ｎ行の固定長非ゼロブロックの各行に対して所
   定の符号化を行つてＭ×Ｎ個の符号化コードを生成する
   ブロック符号化部と、 前記ランレングス符号と前記所定の符号化コードとを所
   定の順序で合成して出力する合成部とを有する冗長度抑
   圧符号化方式。
6. （６）第１の要素列は画像信号を閾値マトリックスで２
   進多値化したカラー画像データ列である事を特徴とする
   特許請求の範囲第５項に記載の冗長度抑圧符号化方式。