JPH08130652A

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

Info

Publication number: JPH08130652A
Application number: JP28911094A
Authority: JP
Inventors: Yoshinori Narita; 喜則成田; Kazunori Matsuura; 一教松浦
Original assignee: Nippon Steel Corp
Current assignee: Nippon Steel Corp
Priority date: 1994-10-28
Filing date: 1994-10-28
Publication date: 1996-05-21

Abstract

(57)【要約】【目的】画像データの圧縮率を高め且つ高速に圧縮・
伸長するデータ圧縮・伸長方式を提供する。【構成】順次入力される画像データの直前ラインを保
持する辞書バッファ６と、現ラインから注目画素を先頭
画素とする複数の部分データ列を抽出するバッファ１６
と、複数の部分データ列のうち直前ラインと最も長く一
致する圧縮対象部分データ列を検出する比較器７と、注
目画素と直前ライン上の圧縮対象部分データ列に対応す
る直前部分データ列の相対位置に応じて異なるコード
と、直前部分データ列の長さに応じて異なるコードを出
力し、同一ライン上で連続して圧縮対象部分データ列を
検出した場合、２回目以降の圧縮対象部分データ列の相
対位置に応じたコードに前回の圧縮対象部分データ列の
相対位置の各値毎に異なるものを割り当てる符号生成器
８とを備える。

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

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

【０００３】

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

【０００４】辞書圧縮は、辞書に対するヒット率が高い
画像データには効果を発揮するが、そうでない画像デー
タに対しては効果が無い。また、ヒット率は辞書を記憶
するための記憶容量に依存するため、高いヒット率を得
たいならば容量の大きな格納場所が必要となる。更に、
容量の大きな辞書を持つことで辞書参照回数が増大し、
圧縮速度が低下する。

【０００５】そこで、本発明は、上記圧縮方式の問題点
を補い、画像データのデータ圧縮率を高め情報量を低減
し且つ高速に圧縮することができるデータ圧縮方式及び
その圧縮されたデータを高速に伸長することができる伸
長方式を提供することを目的とする。

【０００６】

【課題を解決するための手段】上記目的を達成するため
に本発明のデータ圧縮方式では、順次スキャンされる２
次元画像データに対して直前ラインのデータを参照し、
現ラインから、注目画素を先頭画素とする長さが１画素
以上の部分データ列であって直前ラインのデータと最も
長く一致する圧縮対象部分データ列を検出した場合に、
前記圧縮対象部分データ列の圧縮データとして、前記注
目画素と直前ライン上の前記圧縮対象部分データ列に対
応する直前部分データ列の先頭画素との相対位置に応じ
て異なるコードを出力すると共に、前記直前部分データ
列の長さに応じて異なるコードを出力するデータ圧縮方
式であって、同一ライン上で前記圧縮対象部分データ列
を２回以上連続して検出した場合に、２回目以降に検出
した圧縮対象部分データ列の圧縮データとして出力する
前記相対位置に応じたコードに、前回出力した圧縮デー
タの相対位置をＴとし、前記Ｔの各値毎に注目画素と直
前部分データ列の先頭画素との相対位置に応じて異なる
ものを割り当てる。

【０００７】また本発明のデータ伸長方式では、順次ス
キャンされる２次元画像データに対して直前ラインのデ
ータを参照し、現ラインから、注目画素を先頭画素とす
る長さが１画素以上の部分データ列であって直前ライン
のデータと最も長く一致する圧縮対象部分データ列を検
出した場合に、前記圧縮対象部分データ列の圧縮データ
として、前記注目画素と直前ライン上の前記圧縮対象部
分データ列に対応する直前部分データ列の先頭画素との
相対位置に応じて異なるコードと、前記直前部分データ
列の長さに応じて異なるコードが順次入力されると共
に、同一ライン上で前記圧縮対象部分データ列を２回以
上連続して検出した場合に、２回目以降に検出した圧縮
対象部分データ列の圧縮データとして入力される前記相
対位置に応じたコードに、前回入力された圧縮データの
相対位置の値をＴとし、前記Ｔの各値毎に注目画素と直
前部分データ列の先頭画素との相対位置に応じて異なる
ものが割り当てられている２次元画像圧縮データの伸長
方式であって、少なくとも直前ラインの伸長されたデー
タを保持し、入力された圧縮データから前記相対位置と
前記直前部分データ列の長さに関する情報を抽出し、ま
た、入力された圧縮データが前記２回目以降に検出した
圧縮対象部分データ列の圧縮データのときは、前記Ｔの
値に基づいて前記相対位置に関する情報を抽出し、抽出
された前記相対位置と前記直前部分データ列の長さに関
する情報に基づいて、保持された直前ラインの伸長され
たデータから前記直前部分データ列を抽出し、入力され
た圧縮データの伸長データとして出力する。

【０００８】また、上記データ圧縮方式を実現するデー
タ圧縮装置は、順次入力される２次元画像データに対し
て１ライン前のデータを保持する参照メモリ手段と、入
力された現ラインの信号から注目画素を先頭画素とする
長さが１画素以上の複数の部分データ列を抽出して記憶
するバッファ手段と、前記バッファ手段に記憶された前
記部分データ列のうち前記参照メモリ手段に記憶された
データと最も長く一致する部分データ列である圧縮対象
部分データ列を検出する走査比較手段と、前記走査比較
手段が前記圧縮対象部分データ列を検出した場合に、前
記圧縮対象部分データ列の圧縮データとして、前記注目
画素と前記参照メモリ手段に記憶されたデータ上の前記
圧縮対象部分データ列に対応する直前部分データ列の先
頭画素との相対位置に応じて異なるコードと、前記直前
部分データ列の長さに応じて異なるコードを出力すると
共に、前記走査比較手段が同一ライン上で前記圧縮対象
部分データ列を２回以上連続して検出した場合に、２回
目以降に検出した圧縮対象部分データ列の圧縮データと
して出力する前記相対位置に応じたコードに、前回出力
した圧縮データの相対位置をＴとし、前記Ｔの各値毎に
注目画素と直前部分データ列の先頭画素との相対位置に
応じて異なるものを割り当てる符号生成手段と、を備え
る。

【０００９】さらに、上記データ伸長方式を実現するデ
ータ伸長装置は、順次スキャンされる２次元画像データ
に対して直前ラインのデータを参照し、現ラインから、
注目画素を先頭画素とする長さが１画素以上の部分デー
タ列であって直前ラインのデータと最も長く一致する圧
縮対象部分データ列を検出した場合に、前記圧縮対象部
分データ列の圧縮データとして、前記注目画素と直前ラ
イン上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
が順次入力されると共に、同一ライン上で前記圧縮対象
部分データ列を２回以上連続して検出した場合に、２回
目以降に検出した圧縮対象部分データ列の圧縮データと
して入力される前記相対位置に応じたコードに、前回入
力された圧縮データの相対位置の値をＴとし、前記Ｔの
各値毎に注目画素と直前部分データ列の先頭画素との相
対位置に応じて異なるものが割り当てられている２次元
画像圧縮データの伸長装置であって、少なくとも直前ラ
インの伸長されたデータを保持するバッファメモリ手段
と、入力された圧縮データから前記相対位置と前記直前
部分データ列の長さに関する情報を抽出し、また、入力
された圧縮データが前記２回目以降に検出した圧縮対象
部分データ列の圧縮データのときは、前記Ｔの値に基づ
いて前記相対位置に関する情報を抽出する抽出手段と、
前記抽出手段により抽出された前記相対位置と前記直前
部分データ列の長さに関する情報に基づいて、前記バッ
ファメモリ手段に保持された直前ラインの伸長されたデ
ータから前記直前部分データ列を抽出し、入力された圧
縮データの伸長データとして出力する復号手段と、を備
えたことを特徴とする。

【００１０】

【作用】本発明の理解を容易にするため、本発明の原理
を図面を用いて説明する。本発明では画像データのある
画素は近傍の画素群に類似するという性質を利用し、順
次スキャンされる２次元画像データ（図１に示す）にお
いて、直前ラインのデータを参照データ（これを記憶す
るバッファを「辞書」ということにする）Ａとして保持
する。そして、辞書Ａを参照し、現ラインから、注目画
素Ｂを先頭画素とする長さが１画素以上の部分データ列
であって辞書Ａのデータと最も長く一致する圧縮対象部
分データ列Ｃを検出する。次に、注目画素Ｂと辞書Ａ上
の圧縮対象部分データ列Ｃに対応する直前部分データ列
Ｄの先頭画素Ｅとの２次元空間上の相対位置に応じて異
なるコードを出力すると共に、直前部分データ列Ｄの長
さ（ここでは２ドット）に応じて異なるコードを出力す
る。これにより、圧縮対象部分データ列Ｃのデータ圧縮
を行う。また、上記のデータ圧縮を２回以上連続して行
う場合、すなわち、圧縮対象部分データ列Ｃに続くデー
タＦを注目画素とする圧縮対象部分データ列Ｇを検出し
た場合、圧縮対象部分データ列Ｇの圧縮データとして出
力する相対位置に応じたコードに、前回出力した圧縮対
象部分データ列Ｃの圧縮データの相対位置をＴ（この場
合、注目画素Ｂと直前部分データ列Ｄの先頭画素Ｅは同
一画素位置にあるのでＴ＝０とする）とし、Ｔの各値毎
に注目画素Ｆと、辞書Ａ上の圧縮対象部分データ列Ｇに
対応する直前部分データ列Ｈの先頭画素Ｊとの２次元空
間上の相対位置に応じて異なるコードを割り当てる。上
記コードは、固定長符号とはせず生起確立の高いデータ
に短い符号を割当て圧縮率を上げるために可変長符号と
することが望ましい。尚、本発明では、現ラインから、
注目画素を先頭画素とする部分データ列であって辞書の
データと最も長く一致する圧縮対象部分データ列を検出
することとしているので、同一ライン上で上記のデータ
圧縮が２回以上連続する場合、２回目以降のデータ圧縮
における相対位置が直前に行われたデータ圧縮における
相対位置と一致することはない。たとえば、直前の圧縮
対象部分データ列の相対位置が同一画素位置（Ｔ＝０）
の場合、今回の圧縮対象部分データ列の相対位置が同一
画素位置となることはない。したがって、同一ライン上
で上記のデータ圧縮が２回以上連続する場合、２回目以
降のデータ圧縮において、直前に行われたデータ圧縮に
おける相対位置と同じ相対位置にコードを割り当てる必
要はない。このため、本発明では、同一ライン上で上記
のデータ圧縮が２回以上連続する場合、２回目以降のデ
ータ圧縮において、直前に行われたデータ圧縮における
相対位置をＴとし、今回行うデータ圧縮における相対位
置を表すコードをＴの各値毎に用意することにより、直
前に行われたデータ圧縮における相対位置にコードを割
り当てるという無駄を省き、これにより、符号の冗長性
を改善して圧縮率を高める。

【００１１】また、注目画素が現ラインの先頭に位置す
る場合、直前部分データ列の先頭画素が注目画素より左
側に位置することはない。したがって、上記のデータ圧
縮において、注目画素が現ラインの先頭に位置する場
合、直前部分データ列の先頭画素が注目画素より左側に
位置する相対位置にコードを割り当てる必要はない。ま
た、注目画素が現ラインの終端に位置する場合、直前部
分データ列の先頭画素が注目画素より右側に位置するこ
とはない。したがって、上記のデータ圧縮において、注
目画素が現ラインの終端に位置する場合、直前部分デー
タ列の先頭画素が注目画素より右側に位置する相対位置
にコードを割り当てる必要はない。このため、本発明で
は、２次元画像データの１ラインの画素数をＨ、注目画
素の現ラインの先頭画素からの位置をｘ（０≦ｘ≦Ｈ−
１）、ｘ＝０のときはＳ＝０、１≦ｘ≦Ｈ−２のときは
Ｓ＝１、ｘ＝Ｈ−１のときはＳ＝２とし、相対位置を表
すコードをＳの各値毎に用意すると共に、同一ライン上
で上記のデータ圧縮が２回以上連続する場合はＴ及びＳ
の各値毎に用意することにより、注目画素が現ラインの
先頭又は終端に位置する場合に、採り得ることのない相
対位置にコードを割り当てるという無駄を省き、これに
より、更に符号の冗長性を改善して圧縮率を高めるのが
望ましい。

【００１２】尚、辞書に対する参照範囲は、注目画素を
先頭画素とする部分データ列と辞書上の部分データ列と
の類似度が高い範囲内に限定するのが望ましい。また、
注目画素を先頭画素とする部分データ列が辞書上の部分
データ列と一致しない場合は、ランレングス圧縮などを
適用する。

【００１３】本発明は、上記のように、辞書の容量は直
前ラインのみを格納すれば良いので非常に小さい。ま
た、類似度の高い範囲内で辞書を参照すると共にできる
だけ長い部分データ列を参照するので、圧縮率が高く且
つ圧縮・伸長を高速に処理することが可能である。さら
に、同一ライン上で圧縮対象部分データ列を２回以上連
続して検出した場合に、２回目以降に検出した圧縮対象
部分データ列の圧縮データとして出力する相対位置に応
じたコードに、Ｔの各値毎に相対位置に応じて異なるも
のを割り当てることにより、相対位置を表す符号の冗長
性を改善し、圧縮率を高めることができる。また、画像
データの１ライン目や辞書参照が不可能な部分データ列
にランレングス圧縮などを適用することで、更に、高い
圧縮率が得られる。

【００１４】

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

【００１５】次に、図３に示すフローに基づいて上記の
ように構成されたデータ圧縮回路の動作の概要を示す。
先ず、処理２０でポインタ１０等を初期化し、順次入力
される画像データをラインバッファ入力信号線１７を通
してラインバッファ５へ格納する。この際、辞書バッフ
ァ入力信号線１８を通して辞書バッファ６にラインバッ
ファ５から押し出されるデータを格納する。次に、処理
２１でラインバッファ５に入力されたラインデータが１
ライン目のデータであるか否かを判断する。ラインバッ
ファ５に入力されたラインデータが１ライン目のデータ
である場合、参照すべきデータが辞書バッファ６に未だ
格納されていないので、ランレングス圧縮を行う（処理
２５）。すなわち、現ライン上に同一画素ができるだけ
長く連続する部分データ列を検索する。先ず、ポインタ
１０の指すラインバッファ５のデータを部分列バッファ
１６に格納し、ポインタ１０を１つ進め、ラインバッフ
ァ５のデータをセレクタ１５を通して、比較器７に入力
し、部分列バッファ１６のデータと比較する。比較の結
果が一致するならば、長さカウンタ１３をインクリメン
トし、次のポインタ１０の指すデータをセレクタ１５を
通して比較器７に入力し部分列バッファ１６のデータと
比較する。そして、比較の結果が一致しなくなるまでポ
インタ１０を１つずつ進め部分列バッファ１６のデータ
との比較を繰り返す。これにより、比較結果が一致しな
くなった時点で長さカウンタ１３に計数されている値が
現ライン上の同一画素が連続した部分データ列の長さＬ
として計数される。次に、長さカウンタ１３により計数
された部分データ列の長さＬのデータと部分列バッファ
１６に格納された生データとを符号生成器８に入力す
る。符号生成器８は、部分データ列の長さＬのデータと
その生データとをコード化し、符号出力線１９を通し
て、そのコードを出力する（処理２６）。このようにし
て１ライン目の全てのデータを処理する。

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

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

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

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

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

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

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

【００２３】処理２２で圧縮対象部分データ列が見つか
った場合は処理２３を介して処理２４に移行し、相対位
置・長さバッファ１４の中に格納されているデータの中
で最長のデータとそれに対する相対位置のデータを符号
生成器８に入力する。符号生成器８は、相対位置のデー
タと部分データ列の長さＬのデータとをコード化し、符
号出力線１９を通して、そのコードを出力する（処理２
６）。

【００２４】また、相対位置・長さバッファ１４に格納
されている長さが全て０の場合、すなわち圧縮対象部分
データ列が見つからなかった場合は、処理２３を介して
処理２５に移行し、上記のランレングス圧縮を行う。

【００２５】処理２７及び処理２８を介して上記操作を
２次元画像データの最終ラインまで繰り返し、データ圧
縮を行い符号化する。

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

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

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

【００２９】図４（ａ）の２行目の処理は、１行目を辞
書として扱う。（０，２）は相対位置０の辞書（０，
１）と相対位置１の辞書（１，１）と一致する。相対位
置０の場合は一致する辞書の部分データ列の長さが
（０，１）から（１，１）と２であるが、相対位置１の
場合は一致する辞書の部分データ列の長さが（１，１）
から（５，１）と５であり、相対位置１の辞書の部分デ
ータ列の方が長いので、画素データ（０，２）を注目画
素とする圧縮対象部分データ列は相対位置１、長さ５と
なる。したがって符号は｛１，５｝となる。上記の処理
を最終行まで繰り返すと図４の画像データに対して図５
の符号列が得られる。

【００３０】次に、図５の符号列を図６及び図７に示す
符号を用いて実際のコードに割り当ててみる。ランレン
グス圧縮の場合、符号は図６の６１に示すように識別子
＋データの種類＋長さで構成される。ここで、識別子は
１ビット固定で表現することとし、ランレングス圧縮の
場合は０が割り当てられる。但し、１ライン目はランレ
ングス圧縮のみなので識別子は取り除く。データの種類
とは生データのことである。本実施例では１画素を４ビ
ット固定で表現している。長さは可変長符号で表現する
こととし、長さに応じて図８（Ａ）に示すコードを割り
当てる。たとえば、図５に示す符号列の０行目の［２，
４］は000101110 となる。

【００３１】辞書圧縮の場合、符号は図６の６２に示す
ように識別子＋相対位置＋長さで構成される。辞書圧縮
の場合、識別子は１が割り当てられる。相対位置は可変
長符号で表現する。同一ライン上において、前回行った
圧縮が処理２５のランレングス圧縮によるものである場
合は、２次元画像データの一ラインの画素数をＨ（本実
施例ではＨ＝８）、注目画素の現ラインの先頭画素から
の位置をｘ₁（本実施例では０≦ｘ₁≦７）、ｘ₁＝０
のときはＳ＝０、ｘ₁＝１〜６のときはＳ＝１、ｘ₁＝
７のときはＳ＝２とし、Ｓの各値毎に、注目画素の相対
位置に応じて図７（Ａ）に示すコードを割り当てる。た
とえば、図５に示す符号列の４行目の｛−１，２｝は直
前に行われた圧縮が処理２５のランレングス圧縮なの
で、図７（Ａ）に示すコードを割り当てる。図５に示す
符号列の４行目の｛−１，２｝は、ｘ₁＝２なのでＳ＝
１となり、したがって相対位置−１の符号は11となる。
尚、Ｓの各値毎に、相対位置に応じて異なるコードを割
り当てたのは以下の理由による。原理的には、相対位置
に応じて異なるコードが割り当てられていれば、Ｓの各
値毎にコードを割り当てる必要はない。しかし、Ｓ＝０
の場合、すなわち、注目画素が現ラインの先頭に位置す
る場合、圧縮対象部分データ列と一致する辞書上の部分
データ列（これを直前部分データ列と定義する）の先頭
画素が注目画素より左側に位置することはない。したが
って、本実施例では、Ｓ＝０のときは相対位置が−１と
なることはないので、相対位置−１にコードを割り当て
る必要はない。また、Ｓ＝２の場合、すなわち、注目画
素が現ラインの終端に位置する場合、直前部分データ列
の先頭画素が注目画素より右側に位置することはない。
したがって、本実施例では、Ｓ＝２のときは相対位置が
１となることはないので、相対位置１にコードを割り当
てる必要はない。そこで、本発明では、Ｓの各値毎に相
対位置に応じて異なるコードを割り当てることにより、
注目画素が現ラインの先頭又は終端に位置する場合に、
相対位置の採り得る値外の値について符号が割り当てら
れるという無駄を省き、符号の冗長性を改善して圧縮率
を高めている。これにより、本実施例では、図７（Ａ）
に示すように、Ｓ＝０及びＳ＝２のときは相対位置を１
ビットで表現することができた。

【００３２】また、同一ライン上において、前回行った
圧縮が処理２４の圧縮によるものである場合、すなわち
処理２４の辞書圧縮が２回以上連続した場合は、前回出
力した圧縮データの相対位置をＴとし、上記Ｓ及びＴの
各値毎に、注目画素の相対位置に応じて図７（Ｂ）に示
すコードを割り当てる。たとえば、図５に示す符号列の
４行目の｛０，４｝は直前に行われた圧縮が処理２４の
辞書圧縮なので、図７（Ｂ）に示すコードを割り当て
る。図５に示す符号列の４行目の｛０，４｝は、ｘ₁＝
４なのでＳ＝１となり、また、直前に行われた処理２４
の圧縮によるデータの相対位置が−１なのでＴ＝−１と
なる。したがって相対位置０の符号は0 となる。本発明
では、現ラインから、注目画素を先頭画素とする長さが
１画素以上の部分データ列であって直前ラインのデータ
と最も長く一致する圧縮対象部分データ列を検出するこ
ととしているので、同一ライン上で処理２４の辞書圧縮
が２回以上連続する場合、２回目以降の圧縮における相
対位置が直前に行われた圧縮における相対位置と一致す
ることはない。たとえば、直前に行われた圧縮の相対位
置が０の場合、今回行う圧縮の相対位置が０となること
はない。したがって、同一ライン上で処理２４の辞書圧
縮が２回以上連続する場合、２回目以降の圧縮では直前
に行われた圧縮の相対位置と同じ相対位置にコードを割
り当てる必要はない。そこで、本発明では、同一ライン
上で処理２４の辞書圧縮が２回以上連続する場合、２回
目以降の圧縮においては、直前に行われた圧縮の相対位
置をＴとし、今回行う圧縮の相対位置を表すコードを上
記Ｓ及びＴの各値毎に用意することにより、相対位置の
採り得る値外の値について符号が割り当てられるという
無駄を省き、更に符号の冗長性を改善し圧縮率を高めて
いる。これにより、本実施例では、図７（Ｂ）に示すよ
うに、相対位置を１ビットで表現することができた。さ
らに、Ｓ＝２、Ｔ＝−１のときは相対位置は必ず０にな
り、また、Ｓ＝２、Ｔ＝０のときは相対位置は必ず−１
になるので符号を割り当てる必要がなくなった。尚、図
７において、ハイフン「−」で示すものは可変長符号が
割り当てられていないことを示す。図７（Ｂ）におい
て、Ｓ＝０のときに符号が割り当てられていないのは、
注目画素が現ラインの先頭に位置する場合、この注目画
素を先頭画素とする圧縮対象部分データ列は、同一ライ
ン上で行われる最初のデータ圧縮によるものだからであ
る。

【００３３】長さも可変長符号で表現する。直前部分デ
ータ列の先頭画素についての直前ラインの先頭画素から
の位置をｘ₂（本実施例では０≦ｘ₂≦７）、ｘ₁及び
ｘ₂のうち大きい方の値をＵ（Ｕ＝ＭＡＸ（ｘ₁，
ｘ₂））とし、Ｕの各値毎に、長さに応じて図８（Ｂ）
に示すコードを割り当てる。たとえば、図５に示す符号
列の４行目の｛−１，２｝はｘ₁＝２であり、また相対
位置は−１なのでｘ₂＝１である。したがって、Ｕ＝ｘ
₁＝２であるので、長さ２の符号は図８（Ｂ）より10と
なる。また、図５に示す符号列の４行目の｛０，４｝
は、ｘ₁＝４であり、また相対位置は０なのでｘ₂＝４
である。したがって、Ｕ＝ｘ₁＝ｘ₂＝４であるので、
長さ４の符号は図８（Ｂ）より111 となる。

【００３４】辞書圧縮の場合において、長さに応じたコ
ードをＵの各値毎に用意したのは以下の理由による。原
理的には、長さに応じて異なるコードが割り当てられて
いれば、Ｕの各値毎にコードを割り当てる必要はない。
しかし、圧縮対象部分データ列の長さ、すなわち、直前
部分データ列の長さの採り得る最大値は注目画素から現
ラインの終端に位置する画素までのドット長より大きく
なることはない。また、直前部分データ列の先頭画素か
ら直前ラインの終端に位置する画素までのドット長より
大きくなることもない。したがって長さの採り得る最大
値は、注目画素から現ラインの終端に位置する画素まで
のドット長及び直前部分データ列の先頭画素から直前ラ
インの終端に位置する画素までのドット長のうち短い方
の値となる。このため、本実施例では、ｘ₁及びｘ₂の
うち値の大きい方をＵとし、Ｕの各値毎に長さに応じて
異なるコードを割り当てることにより、長さの採り得る
範囲外の値についてコードが割り当てられるという無駄
を省き、符号の冗長性を改善して圧縮率を高めている。
尚、図８（Ｂ）において、ハイフン「−」で示すものは
可変長符号が割り当てられていないことを示す。Ｕ＝７
のときに可変長符号が割り当てられていないのは、Ｕ＝
７の場合、長さは必ず１となるからである。

【００３５】これにより、たとえば、図５に示す符号列
の４行目の｛−１，２｝は11110 となる。また、図５に
示す符号列の４行目の｛０，４｝は10111 となる。

【００３６】図５の符号列を実際の符号に変換した結果
が図９になり、図４の画像データの容量が２５６ビット
であるのに対し、図９のデータ容量は、１６０ビットで
あり、本発明のアルゴリズムを用いてもとの画像データ
の６２．５％に圧縮できたことになる。

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

【００３８】次に、図１１に示すフローに基づいて上記
のように構成された伸長回路の動作の概要を示す。先
ず、入力信号線４３を通して入力バッファ２９に圧縮さ
れたデータを取り込み、初めの１ビットを識別子バッフ
ァに格納し、処理４５でポインタ４０及び長さカウンタ
３７を０に初期化する。処理４６に移行し、識別子バッ
ファの内容が1 であるなら、後に続くデータは辞書圧縮
されたデータなので、辞書デコーダ３２を通し、相対位
置と長さの情報とをデコードする。先ず、初めの１ビッ
トに続く２ビット目以降のビット列長から相対位置の情
報（−１か０か１）を抽出する。同一ライン上で前回伸
長したデータが辞書圧縮されたデータである場合、すな
わち、前回伸長したデータの初めの１ビットが1 である
場合、同一ライン上で辞書圧縮されたデータが２回以上
連続して入力されたことになるので、ポインタ４０の指
す注目画素の現ライン上での位置ｘ₁に基づいて上述し
たＳの値を求める。そして、このＳの値及び前回辞書デ
コーダ３２でデコードした相対位置の情報Ｔの値に基づ
いて、図７（Ｂ）に示すテーブルから初めの１ビットに
続く２ビット目以降のビット列長に対応する相対位置の
情報を抽出する。同一ライン上で前回伸長したデータが
ランレングス圧縮されたデータである場合、すなわち、
前回伸長したデータの初めの１ビットが0 である場合、
または、今回伸長するデータが同一ライン上で最初のデ
ータである場合は、ポインタ４０の指す注目画素の現ラ
イン上での位置ｘ₁に基づいて上述したＳの値を求め
る。そして、このＳの値に基づいて図７（Ａ）に示すテ
ーブルから初めの１ビットに続く２ビット目以降のビッ
ト列長に対応する相対位置の情報を抽出する。次に、デ
コードされた相対位置の情報（−１か０か１）とポイン
タ４０の内容（注目画素の現ラインの先頭画素からの位
置ｘ₁）を加算器３８に入力して直前部分データ列の先
頭画素の直前ライン上での位置ｘ₂を求め、この位置ｘ
₂を辞書ポインタ４１に格納する（処理４７）。次に、
ポインタ４０の指す注目画素の現ライン上での位置ｘ₁
及び加算器３８で算出した直前部分データ列の先頭画素
の直前ライン上での位置ｘ₂に基づき、前述したＵの値
（Ｕ＝ＭＡＸ（ｘ₁，ｘ₂））を求める。そして、この
Ｕの値に基づき、相対位置を表すビット列長に続くビッ
ト列長から長さの情報を抽出し、長さバッファに格納す
る（処理４８）。

【００３９】処理４９では、辞書ポインタ４１の指す辞
書バッファ４２のデータをポインタ４０の指す伸長バッ
ファ３９に格納する。次に、辞書ポインタ４１及びポイ
ンタ４０を１つ進め（処理５０、５３）、長さカウンタ
３７をインクリメントし、長さカウンタ３７の内容を長
さバッファ３５の内容と比較器３６を通して比較する
（処理５４）。長さバッファの内容と長さカウンタの内
容が一致しないなら（処理５５）、処理５６を介して処
理４９に移行し、一致するまで処理４９、５０、５３、
５４を順に繰り返し処理する。一致する場合は、長さカ
ウンタ３７を０に初期化した後（処理５７）、処理４６
に移行し、新しい符号を伸長する。

【００４０】処理４６で識別子が０の場合は、後に続く
データはランレングス圧縮されたデータなので、ランレ
ングスデコーダ３１を通し、生データと長さの情報とを
デコードする。先ず、初めの１ビットに続く２ビット目
から５ビット目までのビット列長から生データを抽出す
る。次に、６ビット目以降のビット列長から長さの情報
を抽出する。そして、デコードされた長さの情報を長さ
バッファ３５に格納すると共に（処理５１）、生データ
をポインタ４０の指す伸長バッファ３９に格納する（処
理５２）。次に、ポインタ４０を１つ進め（処理５
３）、長さカウンタ３７をインクリメントし、長さカウ
ンタ３７の内容を長さバッファ３５の内容と比較器３６
を通して比較する（処理５４）。長さバッファの内容と
長さカウンタの内容が一致しないなら（処理５５）、処
理５６を介して処理５２に移行し、一致するまで処理５
２、５３、５４を順に繰り返し処理する。一致する場合
は、長さカウンタ３７を０に初期化した後（処理５
７）、処理４６に移行し、新しい符号を伸長する。尚、
入力された圧縮データが１ライン目の場合、識別子は取
り除かれているが、データはランレングス圧縮されたデ
ータのみなので、処理４６で識別子の判定をすることな
く処理５１に移行する。

【００４１】上記の処理を最後の符号まで繰り返して行
い、伸長バッファ３９に格納したデータが画像データ１
ライン分に達したら、辞書バッファ４２に伸長バッファ
３９の内容をすべて複写し、辞書バッファの内容、つま
り復元されたデータを出力信号線４４を通して出力す
る。そして、再び処理４６に戻り、次のラインの伸長を
行う。

【００４２】

【発明の効果】以上詳細に説明したように、本発明によ
れば、辞書の容量は直前ラインのみを格納すれば良いの
で非常に小さく、また、類似度の高い範囲内で辞書を参
照すると共にできるだけ長い部分データ列を参照するの
で、圧縮率が高く且つ圧縮・伸長を高速に処理すること
が可能である。さらに、同一ライン上で圧縮対象部分デ
ータ列を２回以上連続して検出した場合に、２回目以降
に検出した圧縮対象部分データ列の圧縮データとして出
力する相対位置に応じたコードに、Ｔの各値毎に相対位
置に応じて異なるものを割り当てることにより、相対位
置を表す符号の冗長性を改善し、圧縮率を高めることが
できる。また、画像データの１ライン目や辞書参照が不
可能な部分データ列にランレングス圧縮などを適用する
ことで、更に、高い圧縮率が得られる。

【図面の簡単な説明】

【図１】２次元画像データを説明するための図である。

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

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

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

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

【図６】実際の符号の構成を説明するための図である。

【図７】相対位置の符号のテーブルを示す図である。

【図８】長さの符号のテーブルを示す図である。

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

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

【図１１】データ伸長の動作の流れを説明するための図
である。

【符号の説明】

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

Claims

【特許請求の範囲】

【請求項１】順次スキャンされる２次元画像データに
対して直前ラインのデータを参照し、現ラインから、注
目画素を先頭画素とする長さが１画素以上の部分データ
列であって直前ラインのデータと最も長く一致する圧縮
対象部分データ列を検出した場合に、前記圧縮対象部分
データ列の圧縮データとして、前記注目画素と直前ライ
ン上の前記圧縮対象部分データ列に対応する直前部分デ
ータ列の先頭画素との相対位置に応じて異なるコードを
出力すると共に、前記直前部分データ列の長さに応じて
異なるコードを出力するデータ圧縮方式であって、同一ライン上で前記圧縮対象部分データ列を２回以上連
続して検出した場合に、２回目以降に検出した圧縮対象
部分データ列の圧縮データとして出力する前記相対位置
に応じたコードに、前回出力した圧縮データの相対位置
をＴとし、前記Ｔの各値毎に注目画素と直前部分データ
列の先頭画素との相対位置に応じて異なるものを割り当
てたことを特徴とするデータ圧縮方式。
【請求項２】順次スキャンされる２次元画像データに
対して直前ラインのデータを参照し、現ラインから、注
目画素を先頭画素とする長さが１画素以上の部分データ
列であって直前ラインのデータと最も長く一致する圧縮
対象部分データ列を検出した場合に、前記圧縮対象部分
データ列の圧縮データとして、２次元画像データの１ラ
インの画素数をＨ、注目画素の現ラインの先頭画素から
の位置をｘ（０≦ｘ≦Ｈ−１）、ｘ＝０のときはＳ＝
０、１≦ｘ≦Ｈ−２のときはＳ＝１、ｘ＝Ｈ−１のとき
はＳ＝２とし、前記Ｓの各値毎に前記注目画素と直前ラ
イン上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
を出力すると共に、前記直前部分データ列の長さに応じ
て異なるコードを出力することを特徴とするデータ圧縮
方式。
【請求項３】請求項２において、同一ライン上で前記
圧縮対象部分データ列を２回以上連続して検出した場合
に、２回目以降に検出した圧縮対象部分データ列の圧縮
データとして出力する前記相対位置に応じたコードに、
前回出力した圧縮データの相対位置の値をＴとし、前記
Ｔ及び前記Ｓの各値毎に、注目画素と直前部分データ列
の先頭画素との相対位置に応じて異なるものを割り当て
たことを特徴とするデータ圧縮方式。
【請求項４】請求項１，２又は３において、直前ライ
ンの参照範囲は、前記相対位置が同一画素位置の場合、
一画素ずれた位置の場合に制限されていること特徴とす
るデータ圧縮方式。
【請求項５】順次スキャンされる２次元画像データに
対して直前ラインのデータを参照し、現ラインから、注
目画素を先頭画素とする長さが１画素以上の部分データ
列であって直前ラインのデータと最も長く一致する圧縮
対象部分データ列を検出した場合に、前記圧縮対象部分
データ列の圧縮データとして、前記注目画素と直前ライ
ン上の前記圧縮対象部分データ列に対応する直前部分デ
ータ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
が順次入力されると共に、同一ライン上で前記圧縮対象
部分データ列を２回以上連続して検出した場合に、２回
目以降に検出した圧縮対象部分データ列の圧縮データと
して入力される前記相対位置に応じたコードに、前回入
力された圧縮データの相対位置の値をＴとし、前記Ｔの
各値毎に注目画素と直前部分データ列の先頭画素との相
対位置に応じて異なるものが割り当てられている２次元
画像圧縮データの伸長方式であって、少なくとも直前ラインの伸長されたデータを保持し、入力された圧縮データから前記相対位置と前記直前部分
データ列の長さに関する情報を抽出し、また、入力され
た圧縮データが前記２回目以降に検出した圧縮対象部分
データ列の圧縮データのときは、前記相対位置に関する
情報を前記Ｔの値に基づいて抽出し、抽出された前記相対位置と前記直前部分データ列の長さ
に関する情報に基づいて、保持された直前ラインの伸長
されたデータから前記直前部分データ列を抽出し、入力
された圧縮データの伸長データとして出力することを特
徴とするデータ伸長方式。
【請求項６】順次スキャンされる２次元画像データに
対して直前ラインのデータを参照し、現ラインから、注
目画素を先頭画素とする長さが１画素以上の部分データ
列であって直前ラインのデータと最も長く一致する圧縮
対象部分データ列を検出した場合に、前記圧縮対象部分
データ列の圧縮データとして、２次元画像データの１ラ
インの画素数をＨ、注目画素の現ラインの先頭画素から
の位置をｘ（０≦ｘ≦Ｈ−１）、ｘ＝０のときはＳ＝
０、１≦ｘ≦Ｈ−２のときはＳ＝１、ｘ＝Ｈ−１のとき
はＳ＝２とし、前記Ｓの各値毎に前記注目画素と直前ラ
イン上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
が順次入力される２次元画像圧縮データの伸長方式であ
って、少なくとも直前ラインの伸長されたデータを保持し、現ラインでの伸長しようとする注目画素の位置ｘに基づ
き前記Ｓの値を求め、入力された圧縮データから、前記
Ｓの値に基づいて前記相対位置に関する情報を抽出する
と共に前記直前部分データ列の長さに関する情報を抽出
し、抽出された前記相対位置と前記直前部分データ列の長さ
に関する情報に基づいて、保持された直前ラインの伸長
されたデータから前記直前部分データ列を抽出し、入力
された圧縮データの伸長データとして出力することを特
徴とするデータ伸長方式。
【請求項７】請求項６において、同一ライン上で前記
圧縮対象部分データ列を２回以上連続して検出した場合
に、２回目以降に検出した圧縮対象部分データ列の圧縮
データとして入力される前記相対位置に応じたコード
に、前回入力された圧縮データの相対位置をＴとし、前
記Ｔ及び前記Ｓの各値毎に注目画素と直前部分データ列
の先頭画素との相対位置に応じて異なるものが割り当て
られている２次元画像圧縮データの伸長方式であって、入力された圧縮データが前記２回目以降に検出した圧縮
対象部分データ列の圧縮データときは、前記相対位置に
関する情報を前記Ｔ及び前記Ｓの値に基づいて抽出する
ことを特徴とするデータ伸長方式。
【請求項８】送信側において、順次スキャンされる２
次元画像データに対して直前ラインのデータを参照し、
現ラインから、注目画素を先頭画素とする長さが１画素
以上の部分データ列であって直前ラインのデータと最も
長く一致する圧縮対象部分データ列を検出した場合に、
前記圧縮対象部分データ列の圧縮データとして、前記注
目画素と直前ライン上の前記圧縮対象部分データ列に対
応する直前部分データ列の先頭画素との相対位置に応じ
て異なるコードと、前記直前部分データ列の長さに応じ
て異なるコードを出力すると共に、同一ライン上で前記
圧縮対象部分データ列を２回以上連続して検出した場合
に、２回目以降に検出した圧縮対象部分データ列の圧縮
データとして出力する前記相対位置に応じたコードに、
前回出力した圧縮データの相対位置をＴとし、前記Ｔの
各値毎に注目画素と直前部分データ列の先頭画素との相
対位置に応じて異なるものを割り当て、受信側において、少なくとも直前ラインの伸長されたデ
ータを保持し、入力された圧縮データから前記相対位置
と前記直前部分データ列の長さに関する情報を抽出し、
また、入力された圧縮データが前記２回目以降に検出し
た圧縮対象部分データ列の圧縮データのときは、前記Ｔ
の値に基づいて前記相対位置に関する情報を抽出し、抽
出された前記相対位置と前記直前部分データ列の長さに
関する情報に基づいて、保持された直前ラインの伸長さ
れたデータから前記直前部分データ列を抽出し、入力さ
れた圧縮データの伸長データとして出力することを特徴
とするデータ圧縮・伸長方式。
【請求項９】送信側において、順次スキャンされる２
次元画像データに対して直前ラインのデータを参照し、
現ラインから、注目画素を先頭画素とする長さが１画素
以上の部分データ列であって直前ラインのデータと最も
長く一致する圧縮対象部分データ列を検出した場合に、
前記圧縮対象部分データ列の圧縮データとして、２次元
画像データの１ラインの画素数をＨ、注目画素の現ライ
ンの先頭画素からの位置をｘ（０≦ｘ≦Ｈ−１）、ｘ＝
０のときはＳ＝０、１≦ｘ≦Ｈ−２のときはＳ＝１、ｘ
＝Ｈ−１のときはＳ＝２とし、前記Ｓの各値毎に前記注
目画素と直前ライン上の前記圧縮対象部分データ列に対
応する直前部分データ列の先頭画素との相対位置に応じ
て異なるコードと、前記直前部分データ列の長さに応じ
て異なるコードを出力し、受信側において、少なくとも直前ラインの伸長されたデ
ータを保持し、現ラインでの伸長しようとする注目画素
の位置ｘに基づき前記Ｓの値を求め、入力された圧縮デ
ータから、前記Ｓの値に基づいて前記相対位置に関する
情報を抽出すると共に前記直前部分データ列の長さに関
する情報を抽出し、抽出された前記相対位置と前記直前
部分データ列の長さに関する情報に基づいて、保持され
た直前ラインの伸長されたデータから前記直前部分デー
タ列を抽出し、入力された圧縮データの伸長データとし
て出力することを特徴とするデータ圧縮・伸長方式。
【請求項１０】送信側において、順次スキャンされる
２次元画像データに対して直前ラインのデータを参照
し、現ラインから、注目画素を先頭画素とする長さが１
画素以上の部分データ列であって直前ライン上の部分デ
ータ列と最も長く一致する圧縮対象部分データ列を検出
した場合に、前記圧縮対象部分データ列の圧縮データと
して、２次元画像データの１ラインの画素数をＨ、注目
画素の現ラインの先頭画素からの位置をｘ（０≦ｘ≦Ｈ
−１）、ｘ＝０のときはＳ＝０、１≦ｘ≦Ｈ−２のとき
はＳ＝１、ｘ＝Ｈ−１のときはＳ＝２とし、前記Ｓの各
値毎に前記注目画素と直前ライン上の前記圧縮対象部分
データ列に対応する直前部分データ列の先頭画素との相
対位置に応じて異なるコードと、前記直前部分データ列
の長さに応じて異なるコードを出力すると共に、同一ラ
イン上で前記圧縮対象部分データ列を２回以上連続して
検出した場合に、２回目以降に検出した圧縮対象部分デ
ータ列の圧縮データとして出力する前記相対位置に応じ
たコードに、前回出力した圧縮データの相対位置をＴと
し、前記Ｔ及び前記Ｓの各値毎に注目画素と直前部分デ
ータ列の先頭画素との相対位置に応じて異なるものを割
り当て、受信側において、少なくとも直前ラインの伸長されたデ
ータを保持し、現ラインでの伸長しようとする注目画素
の位置ｘに基づき前記Ｓの値を求め、入力された圧縮デ
ータから、前記Ｓの値に基づいて前記相対位置に関する
情報を抽出すると共に前記直前部分データ列の長さに関
する情報を抽出し、また、入力された圧縮データが前記
２回目以降に検出した圧縮対象部分データ列の圧縮デー
タのときは、前記Ｔ及び前記Ｓの値に基づいて前記相対
位置に関する情報を抽出し、抽出された前記相対位置と
前記直前部分データ列の長さに関する情報に基づいて、
保持された直前ラインの伸長されたデータから前記直前
部分データ列を抽出し、入力された圧縮データの伸長デ
ータとして出力することを特徴とするデータ圧縮・伸長
方式。
【請求項１１】順次入力される２次元画像データに対
して１ライン前のデータを保持する参照メモリ手段と、入力された現ラインの信号から注目画素を先頭画素とす
る長さが１画素以上の複数の部分データ列を抽出して記
憶するバッファ手段と、前記バッファ手段に記憶された前記部分データ列のうち
前記参照メモリ手段に記憶されたデータと最も長く一致
する部分データ列である圧縮対象部分データ列を検出す
る走査比較手段と、前記走査比較手段が前記圧縮対象部分データ列を検出し
た場合に、前記圧縮対象部分データ列の圧縮データとし
て、前記注目画素と前記参照メモリ手段に記憶されたデ
ータ上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
を出力すると共に、前記走査比較手段が同一ライン上で
前記圧縮対象部分データ列を２回以上連続して検出した
場合に、２回目以降に検出した圧縮対象部分データ列の
圧縮データとして出力する前記相対位置に応じたコード
に、前回出力した圧縮データの相対位置をＴとし、前記
Ｔの各値毎に注目画素と直前部分データ列の先頭画素と
の相対位置に応じて異なるものを割り当てる符号生成手
段と、を備えたことを特徴とするデータ圧縮装置。
【請求項１２】順次入力される２次元画像データに対
して１ライン前のデータを保持する参照メモリ手段と、入力された現ラインの信号から注目画素を先頭画素とす
る長さが１画素以上の複数の部分データ列を抽出して記
憶するバッファ手段と、前記バッファ手段に記憶された前記部分データ列のうち
前記参照メモリ手段に記憶されたデータと最も長く一致
する圧縮対象部分データ列を検出する走査比較手段と、前記走査比較手段が前記圧縮対象部分データ列を検出し
た場合に、前記圧縮対象部分データ列の圧縮データとし
て、２次元画像データの１ラインの画素数をＨ、注目画
素の現ラインの先頭画素からの位置をｘ（０≦ｘ≦Ｈ−
１）、ｘ＝０のときはＳ＝０、１≦ｘ≦Ｈ−２のときは
Ｓ＝１、ｘ＝Ｈ−１のときはＳ＝２とし、前記Ｓの各値
毎に前記注目画素と前記参照メモリ手段に記憶されたデ
ータ上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
を出力する符号生成手段と、を備えたことを特徴とするデータ圧縮装置。
【請求項１３】順次入力される２次元画像データに対
して１ライン前のデータを保持する参照メモリ手段と、入力された現ラインの信号から注目画素を先頭画素とす
る長さが１画素以上の複数の部分データ列を抽出して記
憶するバッファ手段と、前記バッファ手段に記憶された前記部分データ列のうち
前記参照メモリ手段に記憶されたデータと最も長く一致
する圧縮対象部分データ列を検出する走査比較手段と、前記走査比較手段が前記圧縮対象部分データ列を検出し
た場合に、前記圧縮対象部分データ列の圧縮データとし
て、２次元画像データの１ラインの画素数をＨ、注目画
素の現ラインの先頭画素からの位置をｘ（０≦ｘ≦Ｈ−
１）、ｘ＝０のときはＳ＝０、１≦ｘ≦Ｈ−２のときは
Ｓ＝１、ｘ＝Ｈ−１のときはＳ＝２とし、前記Ｓの各値
毎に前記注目画素と前記参照メモリ手段に記憶されたデ
ータ上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
を出力すると共に、前記走査比較手段が同一ライン上で
前記圧縮対象部分データ列を２回以上連続して検出した
場合に、２回目以降に検出した圧縮対象部分データ列の
圧縮データとして出力する前記相対位置に応じたコード
に、前回出力した圧縮データの相対位置をＴとし、前記
Ｓの各値及び前記Ｔの各値毎に注目画素と直前部分デー
タ列の先頭画素との相対位置に応じて異なるものを割り
当てる符号生成手段と、を備えたことを特徴とするデータ圧縮装置。
【請求項１４】請求項１１乃至１３において、前記バ
ッファ手段は、前記走査比較手段が前記参照メモリ手段
に記憶されたデータから前記バッファ手段に記憶された
部分データ列と一致する部分データ列を検出した場合
に、現ラインの信号から前記バッファ手段に記憶された
前記部分データ列に続くデータを抽出して前記バッファ
手段に記憶する部分データ列の長さを順次増加させ、こ
れを前記走査比較手段が一致する部分データ列を検出し
なくなるまで繰り返し、前記走査比較手段は、一致する部分データ列を検出しな
くなる直前に前記バッファ手段に記憶された部分データ
列を前記圧縮対象部分データ列として検出することを特
徴とするデータ圧縮装置。
【請求項１５】請求項１１乃至１４において、前記走
査比較手段は、前記参照メモリ手段に記憶されたデータ
から前記相対位置が同一画素位置又は一画素ずれた位置
にあるデータを先頭画素とする部分データ列を抽出して
比較を行うことを特徴とするデータ圧縮装置。
【請求項１６】順次スキャンされる２次元画像データ
に対して直前ラインのデータを参照し、現ラインから、
注目画素を先頭画素とする長さが１画素以上の部分デー
タ列であって直前ラインのデータと最も長く一致する圧
縮対象部分データ列を検出した場合に、前記圧縮対象部
分データ列の圧縮データとして、前記注目画素と直前ラ
イン上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
が順次入力されると共に、同一ライン上で前記圧縮対象
部分データ列を２回以上連続して検出した場合に、２回
目以降に検出した圧縮対象部分データ列の圧縮データと
して入力される前記相対位置に応じたコードに、前回入
力された圧縮データの相対位置の値をＴとし、前記Ｔの
各値毎に注目画素と直前部分データ列の先頭画素との相
対位置に応じて異なるものが割り当てられている２次元
画像圧縮データの伸長装置であって、少なくとも直前ラインの伸長されたデータを保持するバ
ッファメモリ手段と、入力された圧縮データから前記相対位置と前記直前部分
データ列の長さに関する情報を抽出し、また、入力され
た圧縮データが前記２回目以降に検出した圧縮対象部分
データ列の圧縮データのときは、前記Ｔの値に基づいて
前記相対位置に関する情報を抽出する抽出手段と、前記抽出手段により抽出された前記相対位置と前記直前
部分データ列の長さに関する情報に基づいて、前記バッ
ファメモリ手段に保持された直前ラインの伸長されたデ
ータから前記直前部分データ列を抽出し、入力された圧
縮データの伸長データとして出力する復号手段と、を備えたことを特徴とするデータ伸長装置。
【請求項１７】順次スキャンされる２次元画像データ
に対して直前ラインのデータを参照し、現ラインから、
注目画素を先頭画素とする長さが１画素以上の部分デー
タ列であって直前ラインのデータと最も長く一致する圧
縮対象部分データ列を検出した場合に、前記圧縮対象部
分データ列の圧縮データとして、２次元画像データの１
ラインの画素数をＨ、注目画素の現ラインの先頭画素か
らの位置をｘ（０≦ｘ≦Ｈ−１）、ｘ＝０のときはＳ＝
０、１≦ｘ≦Ｈ−２のときはＳ＝１、ｘ＝Ｈ−１のとき
はＳ＝２とし、前記Ｓの各値毎に前記注目画素と直前ラ
イン上の前記圧縮対象部分データ列に対応する直前部分
データ列の先頭画素との相対位置に応じて異なるコード
と、前記直前部分データ列の長さに応じて異なるコード
が順次入力される２次元画像圧縮データの伸長装置であ
って、少なくとも直前ラインの伸長されたデータを保持するバ
ッファメモリ手段と、現ラインでの伸長しようとする注目画素の位置ｘに基づ
き前記Ｓの値を求め、入力された圧縮データから、前記
Ｓの値に基づいて前記相対位置に関する情報を抽出する
と共に前記直前部分データ列の長さに関する情報を抽出
する抽出手段と、前記抽出手段により抽出された前記相対位置と前記直前
部分データ列の長さに関する情報に基づいて、前記バッ
ファメモリ手段に保持された直前ラインの伸長されたデ
ータから前記直前部分データ列を抽出し、入力された圧
縮データの伸長データとして出力する複合手段と、を備えたことを特徴とするデータ伸長装置。
【請求項１８】請求項１７において、同一ライン上で
前記圧縮対象部分データ列を２回以上連続して検出した
場合に、２回目以降に検出した圧縮対象部分データ列の
圧縮データとして入力される前記相対位置に応じたコー
ドに、前回入力された圧縮データの相対位置をＴとし、
前記Ｔ及び前記Ｓの各値毎に注目画素と直前部分データ
列の先頭画素との相対位置に応じて異なるものが割り当
てられている２次元画像圧縮データの伸長装置であっ
て、前記抽出手段は、入力された圧縮データが前記２回目以
降に検出した圧縮対象部分データ列の圧縮データとき
に、前記相対位置に関する情報を前記Ｔ及び前記Ｓの値
に基づいて抽出することを特徴とするデータ伸長装置。