JPH07336696A - ２次元画像データの圧縮方式および伸長方式 - Google Patents

Abstract

(57)【要約】 【目的】 本発明は、画像データのデータ圧縮率を高め
情報量を低減し且つ高速に圧縮、伸長するデータ圧縮方
式、伸長方式を提供することを目的とする。 【構成】 本発明のデータ圧縮方式を実現するデータ圧
縮装置は、順次入力される２次元画像データに対して１
ライン前のデータを保持する辞書バッファ６と、入力さ
れた現ラインの信号から、連続する複数のデータ列を抽
出し圧縮対象部分データ列として記憶するバッファ１６
と、辞書バッファ６に記憶されたデータに圧縮対象部分
データ列と同じデータ列が存在するか否かを検出する走
査比較手段７、１５と、走査比較手段によって同じデー
タ列の存在が検出された場合に、辞書バッファ６に記憶
された１ライン前のデータ上での部分データ列の位置と
長さのデータを現ラインのその部分データ列のデータと
して出力する符号生成器８を備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、２次元画像データにお
けるデータ圧縮方式及び伸長方式に関するものである。

【０００２】

【従来の技術】従来の画像圧縮方式としては、非可逆性
のデータ圧縮方式と可逆性のデータ圧縮方式がある。前
者の例として挙げることのできる離散コサイン変換（DC
T ）を用いたJPEGやMPEGなどの非可逆性のデータ圧縮方
式では、カラーコード（カラーパレットの呼び出し符
号）を使用した画像データを圧縮する場合に情報落ちが
生じるため使用することができない。後者の可逆性のデ
ータ圧縮方式の代表的な方式が、情報のランレングス
（run length）を用いてデータ圧縮を行う方式（ランレ
ングス圧縮）、頻繁に現れる情報を辞書に登録しデータ
圧縮を行う方式（辞書圧縮）である。後者の方式は、IE
EE Transactions on Information Theory IT-24 、pp.5
30〜536 に掲載されたZiv 及びLempelによる論文"Compr
ession of Individual Sequenes via Variable Rate Co
ding" に開示されている。

【０００３】

【発明が解決しようとする課題】上記圧縮方式には、そ
れぞれ下記のような問題点がある。ランレングス圧縮
は、連続した同じ情報が多く含まれる画像データには効
果を発揮するが、そうでない画像データに対しては効果
が無く、圧縮の効果が全く現れない場合もある。

【０００４】辞書圧縮は、辞書に対するヒット率が高い
画像データには効果を発揮するが、そうでない画像デー
タに対しては効果が無い。また、ヒット率は辞書を記憶
するための記憶容量に依存するため、高いヒット率を得
たいならば容量の大きな格納場所が必要となる。更に、
容量の大きな辞書を持つことで辞書参照回数が増大し、
圧縮速度が低下する。そこで、本発明は、上記圧縮方式
の問題点を補い、画像データのデータ圧縮率を高め情報
量を低減し且つ高速に圧縮することができるデータ圧縮
方式及びその圧縮されたデータを高速に伸長することが
できる伸長方式を提供することを目的とする。

【０００５】

【課題を解決するための手段】上記目的を達成するため
に本発明のデータ圧縮方式では、順次スキャンされる２
次元画像データに対して直前ラインのデータを参照しな
がら直前のラインと少なくとも１画素分以上同じ部分デ
ータ列が存在する場合に、直前ライン上での部分データ
列の位置と長さのデータをその部分データ列のデータと
して出力する。

【０００６】また本発明のデータ伸長方式では、直前の
ラインと少なくとも１画素分以上同じ部分データ列が存
在する場合に重複する部分のデータとして直前ライン上
での部分データ列の位置と長さの情報が順次入力される
２次元画像圧縮データの伸長方式において、少なくとも
直前ラインのデータを保持し、入力された圧縮データか
ら部分データ列の位置と長さに関する情報を抽出し、こ
の情報に基づいて、入力された現ラインのデータに対し
て、保持された直前ラインのデータの前記部分データ列
の位置から前記部分データ列の長さ分のデータを抽出
し、伸長データとして出力する。

【０００７】また、上記データ圧縮方式を実現するデー
タ圧縮装置は、順次入力される２次元画像データに対し
て１ライン前のデータを保持する参照メモリ手段と、入
力された現ラインの信号から、連続する複数のデータ列
を抽出し圧縮対象部分データ列として記憶するバッファ
手段と、参照メモリ手段に記憶されたデータに圧縮対象
部分データ列と同じデータ列が存在するか否かを検出す
る走査比較手段と、走査比較手段によって同じデータ列
の存在が検出された場合に、参照メモリ手段に記憶され
た１ライン前のデータ上での部分データ列の位置と長さ
のデータを現ラインのその部分データ列のデータとして
出力する符号生成手段を備える。

【０００８】更に、上記データ伸長方式を実現するデー
タ伸長装置は、順次入力される２次元画像データに対し
て１ライン前のデータを保持するバッファメモリ手段
と、入力された圧縮データから部分データ列の位置と長
さに関する情報を抽出する抽出手段と、この情報に基づ
いて、入力された現ラインのデータに対して、バッファ
メモリに保持された直前ラインのデータの部分データ列
の位置から部分データ列の長さ分のデータを抽出し、伸
長データとして出力する復号手段を備える。

【０００９】

【作用】本発明の理解を容易にするため、本発明の原理
を図面を用いて説明する。本発明では画像データのある
画素は近傍の画素群に類似するという性質を利用し、順
次スキャンされる２次元画像データ（図１に示す）にお
いて、直前ラインのデータを参照データ（これを記憶す
るバッファを「辞書」１と言う事にする。）として保持
し、圧縮対象とするラインデータの部分列２で直前ライ
ンの辞書１を参照し、その参照において部分列ができる
だけ長く且つ直前ラインの辞書１の部分列と一致した
時、その辞書１上の部分列３の位置４と部分列の長さを
符号化することによりデータ圧縮を行う。この時、辞書
１上の部分列３の位置４を圧縮対象部分列２からの２次
元空間上の相対位置として表し、この相対位置と部分列
３の長さを符号化する。また、辞書１に対する参照範囲
を、圧縮対象部分列２と辞書１上の部分列との類似度が
高い範囲内に限定する。更に、圧縮対象部分列２が辞書
１上の部分列と一致しない場合は、圧縮対象部分列２に
ランレングス圧縮などを適用する。上記符号は、固定長
符号とはせず生起確立の高いデータに短い符号を割当て
圧縮率を上げるために可変長符号とする事が望ましい。

【００１０】本発明は、上記のように、辞書の容量は直
前ラインのみを格納すれば良いので非常に小さく、類似
度の高い範囲内で辞書を参照し、できるだけ長い部分列
を参照するので、圧縮率が高く且つ圧縮及び伸長を高速
に処理することが可能である。画像データの１ライン目
や辞書参照が不可能な部分列にランレングス圧縮などを
適用することで、更に、高い圧縮率が得られる。

【００１１】

【実施例】以下に、本発明の実施例を図２乃至図６にし
たがって詳述する。図２は本発明のデータ圧縮回路の構
成例である。図３は本発明のデータ圧縮アルゴリズムの
フローチャートである。図２において、５はラインバッ
ファ、６は１ライン前のデータを保持する辞書バッフ
ァ、７は比較器、８は符号生成器、９は加算器、１０は
ポインタ、１１は相対位置カウンタ、１２はポインタバ
ッファ、１３は長さカウンタ、１４は相対位置・長さバ
ッファ、１５はセレクタ、１６は部分列バッファを示
す。また、１７はラインバッファへの入力信号線、１８
は辞書バッファへの入力信号線、１９は符号出力線を示
す。

【００１２】次に、上記のように構成されたデータ圧縮
回路の動作の概要を示す。先ず、処理２０でポインタ１
０等を初期化し、順次入力される画像データをラインバ
ッファ入力信号線１７を通してラインバッファ５へ格納
する。この際、辞書バッファ入力信号線１８を通してラ
インバッファ５から押し出されるデータを辞書バッファ
６に格納する。次に、処理２１でラインバッファ５に入
力されたラインデータが１ライン目のデータであるなら
ば、処理２５に遷移し、ポインタ１０の指すラインバッ
ファ５のデータを部分列バッファ１６に格納し、ポイン
タ１０を１つ進め、ラインバッファ５のデータをセレク
タ１５を通して、比較器７に入力し、部分列バッファ１
６のデータと比較する。比較の結果一致するならば、長
さカウンタ１３をインクリメントし、次のポインタの指
すデータをセレクタ１５を通して比較器７に入力し部分
列バッファ１６のデータと比較し、一致しなくなるまで
ポインタを１つずつ進め部分列バッファ１６のデータと
の比較を繰り返す。一致しなくなったところで、処理２
６で長さカウンタ１３のデータと部分列バッファ１６の
データを符号生成器８に入力し、符号出力線１９を通し
て、符号を出力する。このようにして１ライン目の全て
のデータを処理する。

【００１３】処理２１でラインバッファ５に入力された
ラインデータが２ライン目以降のデータならば、処理２
２に遷移し、最長部分列の検索を行う。この最長部分列
の検索は図３には処理２２として１つのフローで示して
有るが、以下の手順で行われる。最長部分列の検索の概
念を８×８の画像データを示す図４を例として説明す
る。本実施例では、検索対象部分列（現ラインのデータ
から選択された連続する画素のデータをこう定義する）
に対して１ライン前のラインにその検索対象部分列と同
じ部分列が存在するか否かを、検索対象部分列の先頭画
素位置から−１戻った位置（相対位置−１と定義する）
から＋１進んだ位置（相対位置＋１と定義する）に検索
対象部分列の先頭画素と同じ画素が存在するか否かを検
索する事によって判定している。即ち、１ライン前に左
右１画素分ずれた範囲内に同じ画素列が存在する場合に
処理２２の圧縮を行う事になる。

【００１４】図４（ａ）で言えば、（１）相対位置−１
の例としては、３行１列目の「５」に続く部分列「５５
４」がある。この部分列「５５４」は２行の１列目の
「５」に続く部分列「５５４」と同じデータ列であるの
で左に１画素ずれた位置に同一部分列が存在すると判定
される。（２）相対位置０の例としては、１行４列目の
「３」に続く部分列「３４」がある。この部分列「３
４」は０行の４列目の「３」に続く部分列「３４」と同
じデータ列であるので０画素ずれた位置に同一部分列が
存在すると判定される。（３）相対位置＋１の例として
は、２行０列目の「５」に続く部分列「５５４３４」が
ある。この部分列「５５４３４」は１行１列目の「５」
に続く部分列「５５４３４」と同じデータ列であるので
右に１画素ずれた位置に同一部分列が存在すると判定さ
れる。

【００１５】処理２２では先ず、ポインタ１０のデータ
をポインタバッファ１２に格納し、相対位置カウンタ１
１を初期化する。次に、ポインタ１０の指すラインバッ
ファ５から１画素分のデータが部分列バッファ１６に取
り込まれる。ラインバッファ５から部分列バッファ１６
に取り込まれた現ラインの１画素のデータについて辞書
バッファに記憶された１ライン前の相対位置−１の画
素、相対位置０の画素、相対位置＋１の画素について一
致する画素が有るか無いかを検索し、無い場合は、相対
位置・長さバッファ１４にそれぞれの相対位置毎に長さ
「０」を書き込んで処理２３に進む。図４（ａ）では１
行３列の「４」は、０行２列、０行３列は「２」であ
り、０行４列は「３」であるので、相対位置・長さバッ
ファ１４にポイント（１、３）の長さデータとして相対
位置−１、０、＋１ともに「０」が書き込まれる。一致
する画素が存在する場合は、ポインタ１０と長さカウン
タ１５をインクリメントし、隣の画素のデータを部分列
バッファ１６に取り込む。このときポインタバッファ１
２には今回の検索で検索中の検索対象部分列の先頭番地
が残されている。

【００１６】検索対象部分列の先頭画素が相対位置−１
に一致を発見した場合は、隣の画素については１ライン
前のデータの相対位置−１の画素のデータと部分列バッ
ファ１６に取り込まれた画素との比較が行われ、相対位
置０に一致を発見した場合は、隣の画素については１ラ
イン前のデータの相対位置０の画素のデータと部分列バ
ッファ１６に取り込まれた画素との比較が行われ、相対
位置＋１に一致を発見した場合は、隣の画素については
１ライン前のデータの相対位置＋１の画素のデータと部
分列バッファ１６に取り込まれた画素との比較が行われ
る。上記それぞれの比較結果が一致を示す場合には、更
に隣の画素ポインタ１０をインクリメントし、隣の画素
のデータを部分列バッファ１６に取り込み、長さカウン
タ１５をインクリメントし一致しなくなるまで繰り返
す。これにより一致しなくなった時点で長さカウンタ１
５に計数されている値が１ライン前のデータに同じデー
タ列を持つ部分データ列の長さＬとして計測される。こ
の長さ情報は相対位置−１、相対位置０、相対位置＋１
のそれぞれについて計数される。即ち、相対位置−１に
ついて上記のようにして長さＬを計数した後その長さＬ
を相対位置−１についての長さ情報として相対位置・長
さバッファの相対位置−１の欄に記憶し、続いて相対位
置０についての検索を行う為、ポインタバッファ１２に
一時保存しておいた検索対象部分列の先頭番地を画素ポ
インタ１０に戻し、相対位置カウンタ１１をインクリメ
ントし、検索対象部分列の先頭番地の右隣のデータにつ
いて同様に相対位置０のデータが一致しなくなるまで画
素ポインタ１０をインクリメントしながら比較を行い、
長さ情報Ｌを求める。続いて相対位置＋１について同様
の検索を行う。

【００１７】図４（ａ）の２行０列の「５」を先頭画素
とする部分列を考えると、この画素はライン先頭なので
前のラインの相対位置−１にデータが存在しないので長
さＬは０となる。相対位置０については１行０列に
「５」が存在するので、長さカウンタ１３をインクリメ
ントして２行０列の「５」の隣接する２行１列のデータ
「５」が部分列バッファ１６に取り込まれ１行１列の
「５」と比較される。これも一致するので、長さカウン
タ１３をインクリメントするとともに２行１列の「５」
の隣接する２行２列のデータ「４」が部分列バッファ１
６に取り込まれ１行２列の「５」と比較される。これは
異なるのでこのときまでに一致したデータの数「２」が
２行０列の「５」を先頭画素とする部分列の相対位置０
についての長さＬ＝２となる。

【００１８】２行０列の「５」を先頭画素とする部分列
については、１行１列に「５」が存在し先頭画素と一致
するので相対位置＋１についても隣接画素の比較を行
う。２行０列の「５」の隣接する２行１列のデータ
「５」が部分列バッファ１６に取り込まれ、相対位置＋
１の１行２列の「５」と比較される。一致するので順次
右側の画素を取り込み比較を続けると、２行５列の
「３」と１行６列の「１」の比較を行った時に不一致に
なる。従って、このときの長さカウンタ１３の値「５」
が２行０列の「５」を先頭画素とする部分列の相対位置
０についての長さＬ＝５となる。

【００１９】以上により、２行０列の「５」を先頭画素
とする部分列の長さＬとしては、Ｌ（相対位置−１）＝
０，Ｌ（相対位置０）＝２，Ｌ（相対位置＋１）＝５の
３つが相対位置・長さバッファに記憶されることにな
る。この中で最長の５を長さＬとする部分列を選択す
る。図４（ａ）の場合、同図（ｂ）に示すように部分列
ａ（５５）は相対位置０の同一部分列を示し、部分列ｂ
（５５４３４）は相対位置＋１の同一部分列を示す。部
分列ａは長さ２、部分列ｂは長さ５であるので圧縮効率
の高い部分列ｂを選択する。

【００２０】すなわち、処理２４に遷移し、相対位置・
長さバッファ１４の中に格納されているデータの中で最
長のデータとそれに対する相対位置を符号生成器８に入
力し、符号出力線１９を通して、符号を出力する。ま
た、処理２３で、相対位置・長さバッファ１４に格納さ
れている長さが全て０なら、つまり辞書の中に一致する
部分列が見つからなかったら、処理２５に遷移し、ラン
レングス圧縮を行う。尚、ランレングス圧縮については
従来のランレングス圧縮方式と異ならないのでその詳細
な説明は省略する。上記操作を画像データの最終ライン
まで繰り返し、データ圧縮を行い符号化する。

【００２１】次に、図４に示す８×８の画像データのデ
ータ圧縮過程を説明する。各データは４ビットで表現さ
れるものとする。以下では、便宜的に、画像データの座
標を（列，行）、符号化されたコードを、｛相対位置，
長さ｝あるいは［データの種類，長さ］で表すことにす
る。即ち、中括弧｛ ｝で囲まれている部分は本発明に
よる圧縮がおこなわれている部分であり、鍵括弧［ ］
で囲まれている部分はランレングスによる圧縮が行われ
ている部分を示すことになる。

【００２２】例えば、相対位置が１、長さが３の符号コ
ードは［１，３］、データの種類が５、長さが２の符号
コードは［５，２］となる。また、注目データの座標を
(x,y)とすると、辞書参照範囲を相対位置で(x-1, y-
1)、(x, y-1)、(x+1, y-1)とする。先ず、１ライン目は
参照する辞書が存在しないのでランレングス圧縮を行
う。画像データ（０，０）から（３，０）のデータは２
で同じなので、符号は［２，４］となる。（４，０）の
３は１つだけなので符号は［３，１］となる。（５，
０）から（７，０）のデータは４で同じなので符号は
［４，３］となり、１ライン目の符号は、図５の１ライ
ン目のように、［２，４］［３，１］［４，３］とな
る。

【００２３】２ライン目の処理は、１ライン目を辞書と
して扱う。（０，１）と（０，０）を比較し一致しない
ので、次に（０，１）と（１，０）と比較し、これも一
致しないので、辞書には一致する部分列がないと判断
し、ランレングス圧縮を適用し、（０，１）から（２，
１) が５であるので符号は［５，３］となる。（３，
１）の４は（２，０）、（３，０）、（４，０）と一致
しないので、ランレングス圧縮を適用し、符号は［４，
１］となる。（４，１）の３は（３，０）、（４，
０）、（５，０）の中の（４，０）と一致し、（４，
１）から（５，１）と辞書の（４，０）から（５，０）
が一致するので、符号は｛０，２｝となる。（６，１）
と（７，１）はそれぞれ辞書のデータと一致しないので
符号は、それぞれ［１，１］、［３，１］となり、２ラ
イン目の符号は、図５の２ライン目のように、［５，
３］［４，１］｛０，２｝［１，１］［３，１］とな
る。

【００２４】３ライン目の処理は２ライン目を辞書とし
て扱う。（０，２）は相対位置０の辞書（０，１）と相
対位置１の辞書（１，１）と一致するが、相対位置０の
場合は一致する辞書の部分列の長さが（０，１）から
（１，１）と２であるが、相対位置１の場合は一致する
辞書の部分列の長さが（１，１）から（５，１）と５で
あり、相対位置１の辞書の部分列の方が長いので、符号
は｛１，５｝となり、上記の処理を最終ラインまで繰り
返すと図４の画像データに対して図５の符号列が得られ
る。次に、図５の符号列を図６の符号を用いて実際のコ
ードに割り当ててみる。ランレングス圧縮の場合の符号
は、図６の６１のように識別子＋データの種類＋長さか
ら構成され、例えば、［２，４］は２進数の000101110
となる。辞書圧縮の場合の符号は、図６の６２のように
識別子＋相対位置＋長さから構成され、例えば、｛−
１，３｝は２進数の11110 となる。但し、１ライン目は
ランレングス圧縮のみなので符号の識別子は取り除く。
図５の符号列を実際の符号に変換した結果が図７にな
り、図４の画像データの容量が２５６ビットであるのに
対し、図７のデータ容量は、１７１ビットであり、本発
明のアルゴリズムを用いてもとの画像データの約６７％
に圧縮できたことになる。

【００２５】図８乃至図９を用いて上記の手法で圧縮し
た符号を伸長する手順を示す。図８は伸長回路の構成例
である。図９はデータ伸長アルゴリズムのフローチャー
トである。図８において、２９は入力バッファ、３０は
識別子バッファ、３１はランレングスデコーダ、３２は
辞書デコーダ、３３と３４はセレクタ、３５は長さバッ
ファ、３６は比較器、３７は長さカウンタ、３８は加算
器、３９は伸長バッファ、４０はポインタ、４１は辞書
ポインタ、４２は辞書バッファ、４３は入力信号線、４
４は出力信号線である。

【００２６】先ず、入力信号線４３を通して入力バッフ
ァ２９に圧縮されたデータを取り込み、初めの１ビット
を識別子バッファに格納し、処理４５でポインタ４０及
び長さカウンタ３７を０に初期化する。処理４６に遷移
し、識別子バッファの内容が１であるなら、後に続くデ
ータは辞書圧縮されたデータなので、辞書デコーダ３２
を通し、デコードされた長さの情報を長さバッファに格
納し（処理４７）、デコードされた相対位置の情報とポ
インタの内容を加算器３８に入力し結果を辞書ポインタ
に格納する（処理４８）。処理４９に遷移し、辞書ポイ
ンタ４１の指す辞書バッファ４２のデータをポインタ４
０の指す伸長バッファ３９に格納する。辞書ポインタ及
びポインタを１つ進め（処理５０、５３）、長さカウン
タ３７をインクリメントし、長さバッファ３５の内容と
比較器３６を通して比較する（処理５４）。長さバッフ
ァの内容と長さカウンタの内容が一致しないなら（処理
５５）、処理５６で処理４９に遷移し、一致するまで処
理４９、５０、５３、５４を順に繰り返し処理する。も
し一致するなら処理４５に遷移し、新しい符号を伸長す
る。

【００２７】処理４６で識別子が０の場合は、処理５１
に遷移し、長さバッファ３５にデコードされた長さを格
納する。次にデータの種類をポインタ４０の指す伸長バ
ッファ３９に格納する（処理５２）。ポインタを１つ進
め（処理５３）、長さカウンタ３７をインクリメント
し、長さバッファ３５の内容と比較器３６を通して比較
する（処理５４）。長さバッファの内容と長さカウンタ
の内容が一致しないなら（処理５５）、処理５６で処理
５２に遷移し、一致するまで処理５２、５３、５４を順
に繰り返し処理する。上記の処理を最後の符号まで繰り
返す。また、伸長バッファ３９に格納したデータが画像
データ１ライン分に達したら、辞書バッファ４２に伸長
バッファ３９の内容をすべて複写し、辞書バッファの内
容、つまり復元されたデータを出力信号線４４を通して
出力する。

【００２８】上記圧縮の実施例では、辞書上に存在する
最長部分列を辞書参照範囲内から検索し、符号化してい
るが、その他にも、最長部分列を複数の部分列に分割し
他の部分列と合成して圧縮する場合や、最長ではない部
分列を組み合わせて圧縮する場合などが考えられる。

【００２９】前者の場合、例えば、図４（ｂ）の部分列
ｂを図４（ｃ）の２つの部分列ｃ「５５４３」と部分列
ｄ「４」に分割し、部分列ｄ「４」と２行５列の「３」
を合成し部分列ｅ「４３」とする。部分列ｃの符号は
｛１，４｝、部分列ｅ「４３」は１ライン前の１行４列
に続く「４３」と一致しているので、符号は｛−１，
２｝となる。従って、２行目の符号は｛１，４｝｛−
１，２｝［５，１］［４，１］（この符号を符号ａとす
る）となる。後者の場合は、例えば、２行０列では相対
位置０の部分列「５５」を選択し、２行２列では相対位
置＋１の部分列「４３４」を選択する。これにより、２
行目の符号は、｛０，２｝｛１，３｝｛−１，１｝
［５，１］［４，１］（この符号を符号ｂとする）とな
る。

【００３０】ここで、上記圧縮の実施例で示した図４
（ａ）の２行目に対する符号が実施例を含め３パターン
できたことになる。図５の２行目の符号を符号ｃとす
る。これらの符号ａ、ｂ、ｃを図６に示した実際の符号
に割り当ててみると、符号ａ、ｃが２４ビット、符号ｂ
が２６ビットとなり、符号ａ、ｃの効率が良い。しか
し、図６に示した以外の符号を符号ａ、ｂ、ｃに割り当
てた場合は、また違った結果になり、符号ｂが最短の符
号になる場合も考えられる。従って、辞書上の最長部分
列を検索して符号化することが必ずしも最良ではなく、
実際の符号を割り当てた時に最短になる、辞書上の部分
列の組み合わせを選択したほうが好ましい。

【００３１】上記のように符号が最短になるように辞書
上の部分列の組み合わせ方を変更しても、符号化のルー
ル（前ラインでの同一部分列の先頭位置と長さを用い
る）が変わらないのであれば、データ伸長方式に影響を
及ぼすことはない。

【００３２】

【発明の効果】以上詳細に説明したように、本発明によ
れば、辞書の容量は直前ラインのみを格納すれば良いの
で非常に小さく、類似度の高い範囲内で辞書を参照し、
できるだけ長い部分列を参照するので、圧縮率が高く且
つ圧縮及び伸長を高速に処理することが可能である。画
像データの１ライン目や辞書参照が不可能な部分列にラ
ンレングス圧縮などを適用することで、更に、高い圧縮
率が得られる。

【図面の簡単な説明】

【図１】２次元画像データ示す説明図である。

【図２】データ圧縮回路の構成例を示す図である。

【図３】データ圧縮の動作を示す流れ図である。

【図４】圧縮前の画像データを示す説明図である。

【図５】圧縮後の画像データを示す説明図である。

【図６】実際の符号を表した図である。

【図７】実際の符号を割り当てた圧縮後の画像データ示
す説明図である。

【図８】データ伸長回路の構成例を示す図である。

【図９】データ伸長の動作を示す流れ図である。

【符号の説明】

１ 辞書 ２ 圧縮対象部分列 ３ 辞書上の部分列 ４ 相対位置 １７ ラインバッファ入力信号線 １８ 辞書バッファ入力信号線 １９ 符号出力信号線 ４３ 入力信号線 ４４ 出力信号線

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０４Ｎ 1/41 Ｂ 1/417

Claims (9)

【特許請求の範囲】
1. 【請求項１】 順次スキャンされる２次元画像データに
   対して直前ラインのデータを参照しながら直前のライン
   と少なくとも１画素分以上同じ部分データ列が存在する
   場合に、直前ライン上での部分データ列の位置と長さの
   データをその部分データ列のデータとして出力すること
   を特徴とするデータ圧縮方式。
2. 【請求項２】 直前のラインと少なくとも１画素分以上
   同じ部分データ列が存在する場合に重複する部分のデー
   タとして直前ライン上での部分データ列の位置と長さの
   情報が順次入力される２次元画像圧縮データの伸長方式
   であって、 少なくとも直前ラインのデータを保持し、 入力された圧縮データから前記部分データ列の位置と長
   さに関する情報を抽出し、 この情報に基づいて、入力された現ラインのデータに対
   して、保持された直前ラインのデータの前記部分データ
   列の位置から前記部分データ列の長さ分のデータを抽出
   し、伸長データとして出力することを特徴とするデータ
   伸長方式。
3. 【請求項３】 送信側において、順次スキャンされる２
   次元画像データに対して直前ラインのデータを参照しな
   がら直前のラインと少なくとも１画素分以上同じ部分デ
   ータ列が存在する場合に、直前ライン上での部分データ
   列の位置と長さに関する情報をその部分データ列のデー
   タとして出力し、 受信側において、少なくとも直前ラインのデータを保持
   し、入力された圧縮データから前記部分データ列の位置
   と長さに関する情報を抽出し、この情報に基づいて、入
   力された現ラインのデータに対して、保持された直前ラ
   インのデータの前記部分データ列の位置から前記部分デ
   ータ列の長さ分のデータを抽出し、伸長データとして出
   力することを特徴とするデータ圧縮・伸長方式。
4. 【請求項４】 請求項１乃至３において、前記部分デー
   タ列の位置に関する情報は、直前ラインの現ラインの圧
   縮対象部分データ列からの２次元空間における相対位置
   として表わされることを特徴とするデータ圧縮方式。
5. 【請求項５】 請求項４において、直前ラインの参照範
   囲を現ラインの圧縮対象部分データ列からの距離が予め
   定められた画素範囲内に制限されている事を特徴とする
   データ圧縮方式。
6. 【請求項６】 順次入力される２次元画像データに対し
   て１ライン前のデータを保持する参照メモリ手段と、 入力された現ラインの信号から、連続する複数のデータ
   列を抽出し圧縮対象部分データ列として記憶するバッフ
   ァ手段と、 前記参照メモリ手段に記憶されたデータに前記圧縮対象
   部分データ列と同じ部分データ列が存在するか否かを検
   出する走査比較手段と、 前記走査比較手段によって同じ部分データ列の存在が検
   出された場合に、前記参照メモリ手段に記憶された１ラ
   イン前のデータ上での前記部分データ列の位置と長さの
   データを現ラインのその部分データ列のデータとして出
   力する符号生成手段を備えたことを特徴とするデータ圧
   縮装置。
7. 【請求項７】 請求項６において、前記バッファ手段は
   前記走査比較手段によって同じデータ列の存在が検出さ
   れた場合に、現ラインの信号から抽出するデータのビッ
   ト数を順次増加させ、前記走査比較手段によって同じデ
   ータ列の存在が検出されなくなるまで繰り返し、 前記符号生成手段は前記走査比較手段によって同じデー
   タ列の存在が検出されなくなった時点の前記参照メモリ
   手段に記憶された１ライン前のデータ上での前記部分デ
   ータ列の位置と長さのデータを現ラインのその部分デー
   タ列のデータとして出力することを特徴とするデータ圧
   縮装置。
8. 【請求項８】 請求項６乃至７において、前記走査比較
   手段は前記参照メモリ手段に記憶された１ライン前のデ
   ータの中で現ラインの圧縮対象部分データ列の画素位置
   から予め定められた画素範囲内にあるデータを抽出して
   比較を行う事を特徴とするデータ圧縮装置。
9. 【請求項９】 直前のラインと少なくとも１画素分以上
   同じ部分データ列が存在する場合に重複する部分のデー
   タとして直前ライン上での部分データ列の位置と長さの
   情報が順次入力される２次元画像圧縮データの伸長装置
   であって、 順次入力される２次元画像データに対して１ライン前の
   データを保持するバッファメモリ手段と、 入力された圧縮データから前記部分データ列の位置と長
   さに関する情報を抽出する抽出手段と、 この情報に基づいて、入力された現ラインのデータに対
   して、前記バッファメモリ手段に保持された直前ライン
   のデータの前記部分データ列の位置から前記部分データ
   列の長さ分のデータを抽出し、伸長データとして出力す
   る復号手段を備えたことを特徴とするデータ伸長装置。