JPH04240971A

JPH04240971A - 画像データ圧縮装置及びその方法

Info

Publication number: JPH04240971A
Application number: JP3007657A
Authority: JP
Inventors: Hirotaka Chiba; 広隆千葉; Yoshiyuki Okada; 佳之岡田; Shigeru Yoshida; 茂吉田; Yasuhiko Nakano; 泰彦中野
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1991-01-25
Filing date: 1991-01-25
Publication date: 1992-08-28
Anticipated expiration: 2015-10-10
Also published as: JP3098046B2

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、画像データを扱う装置
に係り、更に詳しくは画像データの記憶、伝送等におけ
る画像データの圧縮方式に関する。

【０００２】

【従来の技術】近年、ＯＡ化の発展、更にはＣＰＵの処
理技術の向上により、カラーや白黒階調画像情報等のデ
ータベースを計算機で扱うことが増えてきている。これ
らの画像情報のデータ量は１枚（１画面）あたり数Ｍバ
イトになり非常に大きいものである。このため蓄積や伝
送等における画像情報を効率良く扱うため、従来におい
てはデータ圧縮を加えてデータ量を減らしている。

【０００３】データ圧縮には様々な方式があるが、その
一方式としてユニバーサル符号化がある。なお、本発明
は文字コードの圧縮に限らず様々なデータに適用できる
が、以下では説明のため情報理論の分野で呼称されてい
るデータの１ワード単位を文字、データが複数ワードつ
ながったものを文字列と呼ぶ。

【０００４】前述のユニバーサル符号化の代表的な方法
として、Ｚｉｖ−Ｌｅｍｐｅｌ符号がある（詳しくは、
例えば、宗像『Ｚｉｖ−Ｌｅｍｐｅｌのデータ圧縮法』
、情報処理、Ｖｏｌ　．２６、Ｎｏ．１，１９８５年を
参照のこと）。このＺｉｖ−Ｌｅｍｐｅｌ符号では■ユ
ニバーサル型と、■増分分解型（Ｉｎｃｒｅｍｅｎｔａ
ｌ　ｐａｒｓｉｎｇ）の２つのアルゴリズムが提案され
ている。

【０００５】ユニバーサル型のアルゴリズムは、演算量
が多いが、高圧縮率が得られるという特徴を有している
。この方式は、符号化データを過去のデータ系列の任意
の位置から一致する最大長の系列に区切り（部分列）、
過去の系列の複製として符号化する方法である。第５図に示す如くＰバッファとＱバッファとが設けられ
、Ｐバッファには符号化済みの入力データを格納し、Ｑ
バッファにこれから符号化するデータを格納する。そし
て、Ｑバッファの系列はＰバッファの系列をサーチし、
Ｐバッファ中で一致する最大長の部分列を求める。そして、Ｐバッファ中でこの最大部分列を指定するため
の情報の組を符号化する。

【０００６】更に、ユニバーサル型アルゴリズムの改良
としてＬＺＳＳ符号がある。（Ｔ．Ｃ．Ｂｅｌｌ，　“
Ｂｅｔｔｅｒ　ＯＰＭ／Ｌ　Ｔｅｘｔ　Ｃｏｍｐｒｅｓ
ｓｉｏｎ　”，ＩＥＥＥ　Ｔｒａｎｓ．　ｏｎ　Ｃｏｍ
ｍｕｎ．，　Ｖｏｌ．ＣＯＭ−３４，Ｎｏ．１２，　Ｄ
ｅｃ．１９８６参照）　。このＬＺＳＳ符号では図４Ａ
に示す如くＰバッファ中の最大一致系列の開始位置を求
め、一致する長さの組と、次のシンボルとをフラグ区別
して符号量の少ない方で符号化するものである。

【０００７】一方、増分分解型アルゴリズムは、圧縮率
はユニバーサル型より劣るが、シンプルで計算も容易で
あるという特徴を有している。増分分解型Ｚｉｖ−Ｌｅ
ｍｐｅｌ符号では、入力シンボルの系列をｘ＝ａａｂａ
ｂａｂａａ・・・とすると、成分系列ｘ＝Ｘ０　Ｘ１　
Ｘ２　・・・への増分分解は次のようにしている。先ず
Ｘ１　を既成分の右端のシンボルを取り除いた最長の列
とし、Ｘ＝ａ・ａｂ・ａｂａ・ｂ・ａａ・・・としてい
る。従って、Ｘ０　＝λ（空列）、Ｘ１　＝Ｘ０　ａ，
Ｘ２　＝Ｘ１　ｂ，Ｘ３　＝Ｘ２　ａ，Ｘ４　＝Ｘ０　
ｂ，Ｘ５　＝Ｘ１　ａ，・・・・と分解できる。

【０００８】増分分解した各成分系列は既成分系列を用
いて、図４Ｂに示すごとく各成分のでた順番に成分のイ
ンデックスと次のシンボルを用いて符号化している。す
なわち増分分解型アルゴリズムは、符号化パターンにつ
いて、過去に分解した部分列の内最大長を意識するもの
を求め、過去に分解した部分列の複製として符号化する
ものである。

【０００９】さらに、前述の増分分解型アルゴリズムの
改良として、ＬＺＷ符号がある。（Ｔ．Ａ．　Ｗｅｌｃ
ｈ，　“Ａ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｈｉｇｈ−
Ｐｅｒｆｏｒｍａｎｃｅ　Ｄａｔａ　Ｃｏｍｐｒｅｓｓ
ｉｏｎ”，Ｃｏｍｐｕｔｅｒ，　Ｊｕｎｅ　１９８４参
照）。このＬＺＷ符号では、次のシンボルを次の部分列
に組み込むようにしてインデックススのみで符号化でき
るようにしている。

【００１０】図６は従来のＬＺＷ符号化による処理フロ
ー図である。ＬＺＷ符号化処理においては、書き換え可
能な辞書を有し、入力文字列を相異なる文字列（部分列
）に分け、この文字列を出現した順に参照番号を付けて
辞書に登録するとともに、現在入力している文字列を辞
書に登録してある最長一致文字列の参照番号で表わして
符号化するものである。

【００１１】先ず、処理Ｓ１で予め辞書に全文字につき
１文字からなる文字列を初期値として登録してから後述
する符号化を始める。また、処理Ｓ１では入力した最初
の文字Ｋにより辞書を検索して最小番号ωを求め、これ
を語頭文字列とする。続いて処理Ｓ２で入力データの次
の文字Ｋを読み込み、処理Ｓ３で全ての文字入力が終了
したか否かをチェックする。入力文字が存在する、すな
わち文字Ｋが存在する時（Ｙ）には語頭文字列ωに処理
Ｓ２で読み込んだ文字Ｋを加えた文字列（ωＫ）が辞書
に存在するか否かを求める。

【００１２】判別処理Ｓ４で文字列（ωＫ）が辞書に存
在しなければ（Ｎ）、処理Ｓ６によって処理１で求めた
文字Ｋの参照番号ωを符号語ｃｏｄｅ（ω）として出力
し、また文字列（ωＫ）を新たな参照番号として辞書に
登録し、更に処理Ｓ２の入力文字Ｋを参照番号ωに置き
換えると共に辞書アドレスｎをインクリメントして再度
処理Ｓ２より実行する。

【００１３】一方、処理Ｓ４で文字列（ωＫ）が辞書に
存在する時（Ｙ）には、文字列（ωＫ）を参照番号ωに
置き換え（Ｓ５）、再び処理Ｓ２に戻って処理Ｓ４にお
いて文字列ωＫが辞書から探せなくなるまで最大一致長
の検索を続ける。

【００１４】また、文字Ｋが判別処理Ｓ３において存在
しないと判別した時（Ｎ）には処理Ｓ７によってｃｏｄ
ｅ（ω）を出力し終了（ＥＮＤ）する。前述した処理を
図８，９を参照して具体的に説明する。

【００１５】図８の入力データＩＮＰＵＴ　ＳＹＭＢＯ
ＬＳ　は左から右へと順次読む。最初の文字ａを入力し
た時、辞書にはａの他に一致する文字列がないので、Ｏ
ＵＴＰＵＴ　ＣＯＤＥ　１（参照番号ω）を符号語とし
て出力する。そして、拡張した文字列ａｂに参照番号４
を付けて辞書に登録する。実際の辞書登録は図９の右側（ＡＬＴＥＲＮＡＴＥ　Ｔ
ＡＢＬＥ　）に示すように文字列１ｂとして登録する。続いて２番目の文字ｂが文字列の先頭になる。辞書には
ｂの他に一致する文字がないので参照番号２を符号文字
として出力し、同時に拡張した文字列ｂａも辞書にない
ので文字列ｂａを２ａで表わし、参照番号５を付けて辞
書に登録する。そして３番目のａが次の文字列の先頭に
なる。以下同様にこの処理を続ける。

【００１６】図７は図６の復号化処理によって求めた圧
縮データの復号化処理のフローチャートである。図７の
ＬＺＷ復号化処理においては、符号化と同様に予め辞書
に全文字につき１文字からなる文字列を初期値として登
録してから復号を始める。

【００１７】先ず処理Ｓ１１で最初の符号（参照番号）
を読み込み、現在のＣＯＤＥをＯＬＤｃｏｄｅとし、最
初の符号は既に辞書に登録された１文字の参照番号いず
れかに該当することから、入力符号ＣＯＤＥに一致する
文字ｃｏｄｅ（ｋ）を探し出し、文字Ｋを出力する。な
お、出力した文字Ｋは後の例外処理のためＦＩＮｃｈａ
ｒにセットする。

【００１８】次に処理Ｓ１２において、次の符号を読み
込んでＣＯＤＥをＩＮｃｏｄｅとしてセットする。続い
て新たな符号があるか否かを判別（Ｓ１３）し、新たな
符号がない時（Ｎ）には終了（ＥＮＤ）する。また、存
在する時（Ｙ）には処理Ｓ１３で入力した符号ＣＯＤＥ
が辞書に定義されているか否かをチェックする（Ｓ１４
）。通常入力した符号語は前回までの処理で辞書に登録
されているため、続いて符号ＣＯＤＥに対する文字列ｃ
ｏｄｅ（ωＫ）を辞書から読み出し、文字Ｋを一時的に
スタック（Ｓ１６）し、参照番号ｃｏｄｅ（ω）を新た
な符号ＣＯＤＥとして再度処理Ｓ１５より実行する。この処理Ｓ１５、Ｓ１６の手順を参照番号ωが１文字Ｋ
に至るまで繰り返し最後に処理Ｓ１７において処理Ｓ１
６でスタックした文字をＬＩＦＯ（Ｌａｓｔ　Ｉｎ　Ｆ
ａｓｔ　Ｏｕｔ）　形式でポップアップして出力する。また同時に前回使用した符号ωと今回復元した文字列の
最初の１文字Ｋを組（ω，Ｋ）と表わした文字列に、新
たな参照番号として辞書に登録する。

【００１９】図１０を参照してＬＺＷ復号化処理を具体
的に説明する。最初の入力符号（ＩＮＰＵＴ　　ＣＯＤ
Ｅ）は１であり、１文字ａ，ｂ，ｃについては既に参照
番号１，２，３として図９に示す如く辞書に登録されて
いる。よって辞書の参照により符号１に一致する参照番
号の文字列ａに置き換えて出力する。次の符号２につい
ても同様にし、文字ｂに置き換えて出力する。この時前
回処理した符号１と今回復号した最初の１文字ｂとを組
み合わせた文字列（１ｂ）に新たな参照番号４を付加し
て辞書に登録する。

【００２０】３番目の符号４は辞書の検索により求めた
文字列１ｂから文字列ａｂと置き換えて文字列ａｂを出
力する。同時に前回処理した符号２と今回復号した文字
列の１番目の文字ａとの組み合わせた文字列２ａ（＝ｂ
ａ）に新たな参照番号５を付加して辞書に登録する。そ
して以下同様に繰り返すことにより復号がなされる。

【００２１】図１０のＬＺＷ復号化においては次の例外
処理がある。この例外処理は例えば第６番目の入力符号
８の復号にて生ずる。復号８は復号時に辞書に定義され
ておらず復号できない。この場合には前回処理した符号
５に前回復号した文字列ｂａの最初の１文字ｂを加えた
文字列５ｂを求め、更に２ａｂ＝ｂａｂと置き換えて出
力する例外処理を行う。そして、文字列の出力後に前回
の符号５に今回復号した文字列の１番目の文字ｂを加え
た文字列５ｂに参照番号８を付加して辞書に登録する。

【００２２】この例外処理は図６の復号化処理フローの
処理Ｓ４，Ｓ８によって行われ、最終的に処理Ｓ７で文
字列の出力と新たな文字列に参照番号を付加した辞書へ
の登録が行われる。

【００２３】尚、図７，図１０のＬＺＷ復号化において
は、復号側で符号を解読しながら辞書をリアルタイムで
作り出す場合を説明しているが、符号化の際に作られた
辞書をそのまま復号化側にコピーして使用することで、
復号化している場合もあり、この場合には復号側での例
外処理は不要になる。

【００２４】

【発明が解決しようとする課題】前述した従来のユニバ
ーサル符号は可逆型符号方式であり、文字コード、オブ
ジェクトコードなどのデータの圧縮には適していた。従
来はこのユニバーサル符号を画像データの圧縮に用いて
いたが、圧縮率が低いため更に高い圧縮率が要求されて
いる。特に画像データにおいては、復元される画像が原
画像と完全に一致していなくても良いという条件、すな
わち、文字コードやオブジェクトコード等の圧縮とは異
なった条件があるため、非可逆型復号方式における大幅
なデータ方式が要求されている。

【００２５】本発明は可逆型符号化方式の前に特定の処
理を行い、画像データを有効に圧縮する画像データ圧縮
方式を提供することを目的とする。

【００２６】

【課題を解決するための手段とその作用】本発明は画像
データを圧縮する方式に係るものである。先ず、画像デ
ータを特定領域単位で単純化する。この単純化は例えば
ｎ×ｎドットの領域を特定領域とし、予め求めてある入
力パターンに対する単純化パターンにより変換するもの
である。この単純化した画像データを例えばユニバーサ
ル型符号化方式等により符号化し圧縮する。

【００２７】ユニバーサル型符号化方式等は可逆型符号
化方式であるが、特定領域単位で単純化する際、ユニバ
ーサル型符号化方式における圧縮率を高めるため単純化
パターンを用いている。すなわち可逆型符号化方である
ユニバーサル符号の前処理として、２値画像データのパ
ターン変換を行って単純なパターンに画像変換し、繰り
返し同じパターンが多くでるようにして、元情報である
画像データを有効に圧縮している。

【００２８】

【実　　　　施　　　　例】以下図面を用いて本発明を
詳細に説明する。ユニバーサル符号化においては、同一
なデータが存在するほど圧縮率は向上する。原画像のデ
ータの境界（２値画像においては白黒領域の境界、多値
画像においてはエッヂ部分）が少ないか、もしくは同一
形状である方が圧縮率は更に向上する。本発明はこの点
を効果的に用い、符号化前の処理において画像データパ
ターンのパターン変換を行い、ユニバーサル符号化にお
ける圧縮率を高めている。このパターン変換は非可逆変
換であるが、圧縮してデータを保存し元の画像データに
復元する時に完全に同一の画像とならなくても画像その
ものの情報が失われない等の場合には図形情報を効率良
く圧縮することができる。

【００２９】図１は本発明の実施例の構成図である。変
換率指定部１１には変換率（画像データの単純化情報へ
の変換の率を指定するデータ）が入力する。変換率は１
〜ｍまでのｍ段階であり、変換率１は原画像と同一であ
り、大となるほどその変換の度合いが大きい。変換率ｍ
は最高であるが、これは原画像の情報を大きく落として
いることを示している。

【００３０】入力した変換率は変換率指定部１１で記憶
されるとともに画像変換部１２に加わる。画像変換部１
２は次段に接続されたユニバーサル符号化１３で圧縮し
やすいデータに画像データを変換する回路である。この
画像変換部１２はｎ×ｎのマスクパターンについて予め
それらを変換するｍ段階のパターンを記憶し、入力する
全画素に対して変換率（レベル）に応じてパターンのマ
ッチングを行い、入力するパターンに対応したパターン
データを出力する。

【００３１】例えばｎ×ｎのマスクパターンが図２に示
す如く３×３のマスクパターンであった場合、図３に示
す２値画像のパターン変換図表の如く入力パターンＱ０
〜Ｑ８に対応してレベル１〜レベルｍの出力パターンＰ
０〜Ｐ８に変換している。この変換部１２は入力パター
ンが図２の９ドットでありレベルが８レベルまでである
ならば、ＲＯＭの下位アドレス端子に入力パターンＱ０
〜Ｑ８を加え、更に変換率指定部１１からレベル１〜８
に対応した３ビットの情報を上位アドレス端子に加え、
あらかじめそれらに対応した変換データを記憶しておく
ことにより９ビットの変換データを得ることができる。このＲＯＭにレベルに対応した各入力パターンに対する
効率的な出力変換パターンを格納しておくことによって
効率的な変換を行うことができる。

【００３２】以上本発明の実施例をユニバーサル符号化
方式に用いた場合について説明したが、本発明はユニバ
ーサル符号化に限定するものではない。また、画像変換
部１２は繰り返しを多くするパターンに限るものではな
く、可逆のデータ圧縮方式におけるデータの圧縮を高め
るものであればよい。

【００３３】

【発明の効果】以上本発明によれば情報を完全に保存す
る必要のない画像データを有効に圧縮できる画像データ
符号化方式を得ることができる。

【図面の簡単な説明】

【図１】圧縮方式の基本構成図である。

【図２】パターン中の画素位置を示す図である。

【図３】２値画像のパターン変換図表である。

【図４】ユニバーサル符号化のアルゴリズム

【図５】ユ
ニバーサル型ＺＬ符号の符号化の原理図である。

【図６】従来のＬＺＷ符号化処理フロー図である。

【図７】従来のＬＺＷ復号化処理フロー図である。

【図８】ＬＺＷ符号説明図である。

【図９】辞書構成例の説明図である。

【図１０】ＬＺＷ復号化説明図である。

【符号の説明】

１１　　　　交換率指定部１２　　　　画像変換部１３　　　　ユニバーサル符号化部

Claims

【特許請求の範囲】

【請求項１】　　　　画像データを特定領域単位で単純
化し、該単純化した画像データを符号化することを特徴
とする画像データ圧縮方式。
【請求項２】　　　　前記特定領域単位での単純化は、
ｎ×ｎドットの領域を特定領域とし、予め求めてある入
力パターンに対する単純化パターンによる変換であるこ
とを特徴とする請求項１記載の画像データ圧縮方式。
【請求項３】　　　　前記符号化はユニバーサル型符号
化方式によるのもであることを特徴とする請求項１記載
の画像データ圧縮方式。