JPH03208471A - 画像データ圧縮方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概要］ 読取ライン走査で得られた２値画像データを圧縮する際
に、隣接する走査線間での変化画素の接続関係を求めた
後（ＭＭＲ符号化）に、輪郭線に沿って並べ替えてユニ
バーサル符号化により圧縮する画像データ圧縮方式に関
し、 網点など完全な再現が不要な画像データの圧縮率を向上
することを目的とし、 ユニバーサル符号化に際し、符号化しようとする接続関
係と既に登録済みの接続関係の部分列との差異が所定の
近似範囲にある場合には、完全に一致しなくとも登録済
みの部分列の複製として符号化するように構成する。

［産業上の利用分野］ 本発明は、読取ライン走査で得られた２値の画像データ
を圧縮する際に、隣接する走査ライン間の変化画素の接
続関係を求めた後に、輪郭線に沿って並べ替えてユニバ
ーサル符号化により圧縮する画像データ圧縮方式に関す
る。

近年、ＯＡが発展し、文書が白黒２値の画像情報として
ファクシミリや光ディスクファイル・システムなどで扱
われるようになっている。文書情報をディジタルデータ
として利用するとき、画像情報のデータ量は、文字画像
に比べ非常に大きく１０数〜数１０倍になる。また、最
近は、画像の品位を向上させるため、ファクシミリにお
いては、従来の６３機の約２００ｄｐｉから、次の６４
機では３００ｄｐｉや４００ｄｐ　ｉへと解像度が上が
り、データ量は増加する方向にある。したがって、蓄積
や伝送等で画像情報を効率良く扱うには、効率的なデー
タ圧縮を加えることでデータ量を減らすことが必須とな
る。

［従来の技術］ 白黒２値画像を効率良く圧縮する画像データ圧縮方式と
して本願発明者等は、所謂輪郭線ユニバーサル符号化を
提案している。

この輪郭線ユニバーサル符号化方式は、ＭＭＲ符号化を
変形した方式により求めた水平モードのランレングス、
および変化点のモード（変化画素の接続関係）を、それ
ぞれ輪郭線の始点および接続点情報とみて、輪郭線に沿
って並べ替えた後、ユニバーサル符号化するものである
。

この方式によれば、輪郭線の直線性や曲り具合などの統
計的性質をユニバーサル符号化の手法により学習しなが
ら符号の最良化を図り、種々の性質の画像において効率
の良い圧縮が行える。

元来、ユニバーサル符号化方式は、情報保存型のデータ
圧縮方法であり、データ圧縮時に情報源の統計的な性質
を予め仮定しないため、種々のタイプ（文字コード，オ
ブジェクトコードなど）のデータＣこ適用することがで
きる。文書画像では、文字の文字線の直線性や曲り具合
には類似性がある。また、網点画像は、画像全体が網点
分散するため膨大な数の変化点が出現するが、網点周期
性、網点形状の同一性から輪郭線の接続関係は類似して
いる。この類似性のもつ冗長性をユニバーサル符号化に
より削減し、有効な圧縮を行うことができる。

輪郭線ユニバーサル符号化方式では、輪郭線の接続関係
を求めるため、変形したＭＭＲ方式を変化画素のモード
の検出を前処理として用い、ラインごとの変化画素の接
続関係を輪郭線自体の接続関係に直し、このデータにユ
ニバーサル符号化（２ｉ▼−Ｌｅｍｐｅｌ符号化）を適
用し、輪郭線の直線性や曲り具合の大域的性質をユニバ
ーサル符号のインデックスで表すようにしている。

ユニバーサル符号の代表的な方法として、ｚｉ▼−Ｌｅ
ｍｐｅｌ符号がある（詳しくは、例えば宗像「ｚｉ▼一
Ｌｅｍｐｃｌのデータ圧縮法」、情報処理、Ｖｏｌ．　
２６，　Ｎｏ．１．　１９８５年を参照のこと）。

Ｘｉｙ−Ｌｅｍｐｅｌ符号では ■ユニバーサル型と、 ■増分分解型（Ｉｎｃｒｅｍｅｍｔｓｌ　ｐ１ｒｓｉｓ
ｔ）０２つのアルゴリズムが提案されている。

更に、ユニバーサル型アルゴリズムの改良として、ＬＺ
ＳＳ符号がある（Ｔ．　Ｃ．Ｂｅ　Ｉ　ｌ，　’　Ｂｅ
目ｅｒ　ＯＰＭ／Ｌ　Ｔｅｘｔ　Ｃｏｍｐｒｅｓｓｉｏ
ｎ’，　ＩＥＥＥ　Ｔｔｓｎｓ，　ｏｎ　ＣＯ！１１１
１１１１１．，　Ｖｏ１，　ＣＯＭ−３４，　Ｎｏ．　
１２，　Ｄｅｃ．　１９８６参照）。また、増分分解型
アルゴリズムの改良としては、ＬｚＷ符号がある（Ｔ．
Ａ．Ｗｃｌｃｈ，’Ａ　Ｔｅｃｌ＋ｎｉｑａｅ　ｆｏｒ
旧１ｈ７Ｐｅｔｆｏｔｍｔｎｃｅ　Ｄｌｌｌ　Ｃｏｍｐ
ｒｅｓｓｉａａ’，Ｃｏｍｐａｔｅｒ，Ｊｕｎｅ　１９
１１４参照）。

第３図に輪郭線ユニバーサル符号化の画像データ圧縮の
手順を示す。

まずステップ（以下「ステップ」は省略）Ｓｌで、入力
した画像データを第４図に示すＭＭＲを変形した方式に
より、固定長のモード符号と固定長のＲＬ符号（ランレ
ングス符号）とに変換する。

例えば、画像上で第５図（ａ）のように示される輪郭線
情報は、第４図の手順により第５図（ｂ）のようにライ
ンごとに符号化される。この固定長符号の並びをライン
単位から、第５図（ｃ）のように輪郭線ごとに並べ替え
た後、ユニバーサル符号化の手法により、圧縮符号化す
るものである。

変形ＭＭＲ符号化方式による固定長符号は、第６図のよ
うに符号化時に２バイト単位で表し、並べ替え後、学習
効率を高めるため第７図のように１バイト単位の固定長
符号に変換してユニバーサル符号化する。

第４図の変形ＭＭＲ符号化方式が標準方式と異なる点は
、ＳＩＯにおいて、 ａ２＜ｂ， が不成立のとき垂直モードとすることである。即ち、輪
郭線が接続している場合は、全て垂直モードで表される
ことになる。その結果、輪郭線は次のようなモードを遷
移することになるものである。

水平モード　→垂直モード　→パスモード（始点）　　
　（接続点）　　　（終点）［発明が解決しようとする
課題］ 本願発明者らが先に提案している輪郭線ユニバーサル符
号化方式は、２値画像の文字線の曲がり具合や、図表の
直線を輪郭線の接続関係をユニバーサル符号化すること
により、画像の種類によらず効率良くデータ圧縮しよう
とするものである。

しかし、網点画像では、網の形状はマクロ的には類似性
をもつが、ミクロ的にみると量子化ノイズの影響などで
ユニバーサル符号化によって必ずしも規則性を捉えるこ
とができず、圧縮率が低下する問題があった。

本発明は、網点画像の網点は黒画素の密度で階調を表す
ものであり、量子化ノイズまで完全に再現しなくとも人
間の目には分からない点に着目し、網点など完全な再現
が不要な画像データについて輪郭線ユニバーサル符号化
により高い圧縮率を得ることかできる画像データ圧縮方
式を提供することを目的とする。

［課題を解決するための手段］ 第１図は本発明の原理説明図である。

まず本発明は、読取ライン走査で得られた２値の画像デ
ータを圧縮する際に、第１符号化手段（変形ＭＭＲ符号
化手段）１１により隣接する走査線間における変化画素
の接続関係を走査線単位に求めた後、並べ替え手段１２
により輪郭線に沿った変化画素の接続関係に並び替え、
この並び替えた変化画素の接続関係を第２符号化手段（
ユニバーサル符号化手段）によりパターンメモリ１４−
４に登録されている既に符号化済みの変化画素の接続関
係の複製としての部分列に分け、該部分列の番号で指定
することにより圧縮符号化する画像データ圧縮方式、即
ち本願発明者等が既に提案している輪郭線ユニバーサル
符号化方式を対象とする。

このような画像データ圧縮方式につき本発明にあっては
、並べ替え手段１２により輪郭線に沿って並べ替えられ
た変化画素の接続関係と、パターンメモリ１４−４から
得られた符号化済みの変化画素の接続関係の部分列との
差異を検出し、この差異が所定の近似範囲内にあれば、
該符号化済みの部分列による圧縮符号化を第２符号化手
段１４に指令するように構成する。

ここで第２符号化手段１４によるユニバーサル符号化と
しては、輪郭線に沿ったＭＭＲ固定長符号の系列を例え
ば増分分解するようにし、既成分の系列と符号化すべき
系列の一致をとる際に、概略一致判別手段１５において
各接続点のずれの差異が所定の閾値Ｔ，以下であり、か
つ、各接続点のずれの差異の和が所定の閾値Ｔ２以下の
ときは、同一の系列とみて一致と同様に扱い、不一致の
回数が前記閾値を越えたとき初めて不一致と見なして異
なる部分列として分解する。

［作用］ このような構成を備えた本発明の画像データ圧縮方式に
よれば、輪郭線の接続関係を過去に出現した接続関係と
の概略一致を取り、類似している輪郭線同士を一纏めに
して情報非保存型のユニバーサル符号化を行うため、網
点画像に対しても輪郭線の接続関係のユニバーサル符号
化により高い圧縮率を達成できる。

この結果、網点画像等の完全な再現が不要な画像データ
についても、本願発明者等が先に提案している輪郭線ユ
ニバーサル符号化方式の利点である輪郭線情報からその
直線性や曲がり具合などの統計的性質をユニバーサル符
号化の手法により学習しながら符号の最良化を図り、種
々の性質の画像において情報非保存型の効率の良い圧縮
を行なうことができる。

［実施例］ 第１図は本発明の一実施例を示した実施例構成図である
。

まず本発明の画像データ圧縮方式は、走査線単位にＭＭ
Ｒ変形方式により求めた固定長のモード符号とＲＬ符号
とを輪郭線に沿って並べ替えた後、固定長符号をユニバ
ーサル符号化するときに既に辞書に登録されている系列
との差異を求め、差異が許容範囲内なら辞書中の系列で
近似するものである。ユニバーサル符号化に当たっては
、輪郭線の始点以降の接続点と終点とを一つのデータ系
列とみるものである。

第２図において、読取装置等のライン走査で読取られた
画像信号の各画素の２値化データが端子１から入力され
、連続して接続されている２ライン分のバッファを備え
たバッファメモリ１０に順次、格納される。バッファメ
モリ１０では２ライン分のデータがバッファに揃うと、
２ラインの上下に続く２画素を第１符号化手段としての
ＭＭＲ固定長算出回路１１に順次入力する。

ＭＭＲ固定長算出回路１１は、入力した２ライン分の２
画素の系列から第４図の手順に従いＭＭＲモードの分類
を行い、第６図に示す固定長符号を求める。

ＭＭＲ固定長符号並べ替え回路１２は、ＭＭＲ固定長算
出回路１１から固定長符号を受け、第５図に示すように
固定長符号を輪郭線に沿って並べ替え、バッファメモリ
１３に出力する。

１４は第２の符号化手段としてのユニバーサル符号器で
あり、アドレス制御回路１４−１．１４−２、終点検出
回路１４−３及びパターンメモリ１４−４、最大一致長
検出回路１４−５，符号化回路１４−６を備える。また
１５は概略一致判定回路であり、減算回路１５−１、比
較回路１５−２及び累算回路１５−３を備える。

アドレス制御回路１４−１．１４−２はそれぞれバッフ
ァメモリ１３とパターンメモリ１４−４の読出しを制御
し、パターンメモリ１４−４中に登録されている輪郭線
に沿う固定長符号の系列と、バッファメモリ１３中の固
定長符号の系列との照合を概略一致判定回路１５の判定
結果に基づき次のようにして行う。

アドレス制御回路１４−２はパターンメモリ１４−４か
ら登録されている固定長符号の系列について、この系列
の先頭の固定長符号より順に続出し、同時にアドレス制
御回路１４−１はバッファメモリ１３の先頭より固定長
符号を順に読出す。

読出された２つの固定長符号は減算回路１５−１で差Δ
ｉを求め、この差Δｉを閾値回路１５−２と累算回路１
５−３に加える。累算回路１５−３では、この系列の固
定長符号の総和ΣΔｉを求めて閾値回路１５−２に加え
る。閾値回路１５−２は２つの閾値Ｔ１とＴ２が予め定
められており、１Δ１１≦Ｔ１且つ ΣΔｉ≦Ｔ２ なら同一の固定長符号の系列として、系列の照合を続行
する。

また、 １Δｉｌ＞Ｔ，又は ΣΔｆ　＞’ｒ２ なら、その系列は不一致になったとして、次の固定長符
号系列の照合に移る。

バッファメモリ１３から入力される固定長符号の系列の
各輪郭線は、始点、接続点、終点の系列として現れる。

終点検出回路１４−３は系列の終点を検出し、アドレス
制御回路１４−２および、パターンメモリ１４−４に１
つの輪郭線が終了した旨を知らせ、入力する固定長符号
系列に強制的に区切りを入れ、部分列に区切る。

最大長一致検出回路１４−５は、アドレス制御回路１４
−２とバッファメモリ１３とから入力されており、求め
た固定長符号系列のパターンメモＵ　１　４　−　４中
の登録順序を表すインデックス、長さ（固定長符号数＝
　ＷＤｒ　ｄ数）、次の固定長符号の内容Ｃｊを保持し
ておき、系列の長さが最大のものを検出し、そのインデ
ックスと次の固定長符号を出力する。符号化回路１４−
６は最大一致検出回路１４−５から入力した情報を可変
長符号化し、圧縮符号として出力する。

最大一致長の固定長符号系列の符号化が符号化回路１４
−６で終了すると、符号化された固定長符号系列のデー
タによりパターンメモリ１４−４中の固定長系列が伸び
た分がパターンメモリ１４−４に登録されると共に、そ
の符号化済み固定長符号系列がバッファメモリ１３から
捨てられ、同一個数の固定長符号が新たにバッファメモ
リ１３に入力されて蓄積されるメモリ更新処理が行われ
る。

尚、上記の実施例では、ユニバーサル符号化として増分
分解型の２ｉ▼−Ｌｅｍｐｅｌ符号を用いる場合につい
て示したが、これ以外にＬＺＷ符号など他の型のユニバ
ーサル符号でモ良い。

また上記の実施例では、概略一致を全ての部分列につい
て行うようにしたが、他の実施例として部分列が所定の
長さより小さい場合完全一致とし、大きい場合には概略
一致とするように切り換えて使うようにしても良い。

更に、各固定長符号の概略一致範囲を判定する閾値Ｔ１
を固定とせず、概略一致がとれた系列の固定長符号の個
数が増えるとともに少しづつ閾値Ｔ１を大きくとるとか
、個数に応じて変えるようにしても良い。

更にまた、上記の実施例ではパターンメモリの系列と入
力系列との差分をとり、概略一致を判定したが、単なる
差分の代わりに２乗誤差を用いても良い。

［効果］ 以上説明したように本発明によれば、網点画像のように
完全な再現が不要な画像データにっていも、輪郭線の直
線性、曲がり具合の規則性を対象画像に合わせて学習し
ながら符号化するため（情報非保存型符号化）、画像の
種類によらず、有効なデータ圧縮を行って画像劣化を目
立たせることなく圧縮率を向上できる。

また輪郭線は始点情報と接続点情報、終点情報と輪郭線
を表現する異なる情報ごとにまとめられるので、輪郭線
の規則について効率の良い学習ができ、高い圧縮率が得
られる。

更に、輪郭線の規則性は、符号化済の輪郭線の規則性か
らの複製として指定されるため、解像度が上がった場合
でも、規則性をひとまとまりとして促えられ、符号量が
解像度に比例して増加することはない。

【図面の簡単な説明】 第１図は本発明の原理説明図； 第２図は本発明の実施例構成図； 第３図は先行技術の画像データ圧縮手順の説明図；第４
図は変形ＭＭＲ符号化方式の処理フロー図；第５図は先
行技術の配列変換説明図； 第６図は変形ＭＭＲ符号化方式の２バイトの固定長符号
割当て説明図； 第７図は変形ＭＭＲ符号化方式の１バイト単位の固定長
符号割当て説明図である。 図中、 １０：２ラインバッファメモリ １１：ＭＭＲ固定長符号算出回路 （第１符号化手段） １２：ＭＭＲ固定長符号並べ替え回路 （並べ替え手段） １３：バッファメモリ １４：ユニバーサル符号器（第２符号化手段）１４−１
．１４−２：アドレス制御回路１４−３：終点検出回路 １４−４：パターンメモリ １４−５二最大長一致検出回路 １４−６：符号化回路 １５：概略一致判定回路（手段） １５−１：減算回路 １５−２：累算回路 １５−３：比較回路

Claims (2)

【特許請求の範囲】
1. （１）読取ライン走査で得られた２値の画像データを圧
   縮する際に、第１符号化手段（１１）により隣接する走
   査線間の変化画素の接続関係を走査線単位に求めた後、
   並べ替え手段（１２）により輪郭線に沿った変化画素の
   接続関係に並び替え、該並び替えた変化画素の接続関係
   を第２符号化手段（１４）によりパターンメモリ（１４
   −４）に登録されている既に符号化済みの接続関係の複
   製としての部分列に分け、該部分列の番号で指定するこ
   とにより符号化圧縮する画像データ圧縮方式に於いて、 前記並べ替え手段（１２）により輪郭線に沿って並べ替
   えられた変化画素の該接続関係と、前記パターンメモリ
   （１４−４）から得られた登録済みの変化画素の接続関
   係の部分列との差異を検出し、該差異が所定の近似範囲
   内にあれば該符号化済みの部分列による圧縮符号化を前
   記第２符号化手段（１４）に指令する概略一致判定手段
   （１５）を設けたことを特徴とする画像データ圧縮方式
   。
2. （２）前記概略一致判定手段（１５）は、符号化しよう
   する接続関係と符号化済みの接続関係との差異が第１閾
   値（Ｔ１）以下で、且つ各接続関係の差異の和が第２閾
   値（ｔ２）以下のとき、同一の接続関係の系列と判断す
   ることを特徴とする請求項１記載の画像データ圧縮方式
   。