JPH0884260A - ２次元画像データの圧縮方式および伸長方式 - 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)とする。先ず、図４（ａ）の場合、０
行目は参照する辞書が存在しないのでランレングス圧縮
を行う。画像データ（０，０）から（３，０）のデータ
は２で同じなので、符号は［０，２，４］となる。
（４，０）の３は１つだけなので符号は［１，３，１］
となる。（５，０）から（７，０）のデータは４で同じ
なので符号は［１，４，３］となる。（８，０）の６は
１つだけなので符号は［１，６，１］となる。（９，
０）及び（Ａ，０）のデータはＣで同じなので符号は
［２，Ｃ，２］となる。（Ｂ，０）及び（Ｃ，０）のデ
ータは６で同じなので符号は［４，６，２］となる。
（Ｄ，０）から（Ｆ，０）のデータは３で同じなので符
号は［６，３，３］となる。したがって、０行目の符号
は、図５の０行目に示すように、［０，２，４］［１，
３，１］［１，４，３］［１，６，１］［２，Ｃ，２］
［４，６，２］［６，３，３］となる。

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

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

【００３３】次に、図５の符号列を図６乃至図１４に示
すテーブルを用いて実際のコードに割り当ててみる。図
６乃至図１４は、Ｔの値毎に用意された、ｙの値及びｚ
の値に応じて異なるコードが割り当てられたテーブルを
示す。ここで、Ｔは処理２８で注目画素の現ライン上で
の位置ｘから求めた値、ｙ及びｚは処理２５又は処理２
７で符号生成器８に入力された値であり、ｙは圧縮対象
部分列の長さ、ｚは、符号列が鍵括弧［ ］で囲まれて
いる場合、すなわちランレングス圧縮の場合は０、符号
列が中括弧｛ ｝で囲まれている場合、すなわち本発明
による辞書圧縮の場合は、相対位置に２を加えた値であ
る。

【００３４】各テーブルに記憶されたコードは、生起確
立の高いデータに短い符号を割当てて圧縮率を上げるた
め、固定長符号とはせずに可変長符号としている。尚、
テーブルをＴの値毎に用意したのは以下の理由による。
原理的には用意するテーブルは１つでもよい。しかし、
テーブルを１つにまとめると、ｙ及びｚが採りうる全て
の値に応じて異なる符号を割り当てなければならない。
ところで、ｙ及びｚが採りうる値は、注目画素の現ライ
ン上での先頭画素からの位置ｘによって異なる。たとえ
ば、各テーブルにおけるｙの最大値は、注目画素から現
ラインの最終端に位置する画素までのビット列長とな
る。また、ｘ＝０ではｚ＝１（相対位置が−１の場合）
に符号を割り当てる必要はない。したがって、テーブル
を１つにまとめると、符号の冗長性が大きくなる。一
方、注目画素の現ライン上での先頭画素からの位置ｘ毎
にテーブルを用意した場合、各テーブルにおけるｙの最
大値を、注目画素から現ラインの最終端に位置する画素
までのビット列長に制限することにより、符号の冗長性
を改善することができる。しかし、２次元画像データの
１ラインの画素数Ｈを増やした場合、新たにテーブルを
追加しなければならず、テーブルの容量が増大し、この
ため、圧縮・伸長速度が低下する。そこで、本実施例で
は、予め圧縮対象部分列の最大検出列長Ｎを設定した。
そして、ｘ＝０ではｚ＝１に符号を割り当てる必要がな
いので専用のテーブルを用意し、１≦ｘ≦Ｈ−Ｎではｙ
の採りうる最大値は全てＮとなり、また、ｚの採りうる
値は全て０〜３となるのでまとめて１つのテーブルを用
意し、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１ではｚの採りうる値は全
て０〜３であるが、ｙの採りうる最大値は注目画素から
現ラインの最終端に位置する画素までのビット列長とな
るので、ｘの各値毎に専用のテーブルを用意した。すな
わち、ｘ＝０のときはＴ＝０、１≦ｘ≦Ｈ−Ｎのときは
Ｔ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のときはＴ＝ｘ−Ｈ＋
Ｎ＋１、とし、Ｔの各値毎にテーブルを用意した。この
ようにＴの値を設定することにより、Ｔの採りうる値の
範囲は、 最大検出列長Ｎ＜１ラインの画素数Ｈ であれば１ラインの画素数Ｈの値にかかわらず一定とな
る。すなわち、Ｔの採りうる値は０≦Ｔ≦ｘ−Ｈ＋Ｎ＋
１であるが、注目画素の現ライン上での位置ｘの採りう
る最大値はＨ−１であるので、結局、０≦Ｔ≦Ｎとな
る。したがって、２次元画像データの１ラインの画素数
Ｈを増加したときでも、テーブルの数は常にＮ＋１とな
るので、テーブルの容量が増大して、圧縮・伸長速度が
低下するのを防止することができる。

【００３５】また、本実施例では、画像データの圧縮を
対象としているので、辞書圧縮の場合において、注目画
素のあるラインの直前ラインであって注目画素に隣接す
るデータ（相対位置が−１，０，＋１のデータ）のみに
ついて辞書圧縮を行うことにより、テーブルのサイズを
小さくしている。これにより、高い圧縮率を期待でき
る。テーブル群７０に用意されているテーブルは、予め
圧縮伸長するデータに合わせて構成されたハフマン符号
のテーブル、あるいは、圧縮伸長に伴い、冗長性が少な
くなるように最適化されていくテーブルであることが望
ましい。尚、図６乃至図１４において、ハイフン「─」
で示すものは可変長符号が割り当てられていないことを
示す。

【００３６】先ず、Ｔの値に基づき、図６乃至図１４に
示すテーブルの中からいずれかのテーブルを選択する。
たとえば、［０，２，４］を符号化する場合は図６に示
すＴ＝０のテーブルを選択し、｛１，−１，１｝を符号
化する場合は図７に示すＴ＝１のテーブルを選択する。
次に、選択したテーブルの中からｙ及びｚの値に応じた
コードを選択する。たとえば、［０，２，４］を符号化
する場合は図６に示すＴ＝０のテーブルからｙ＝４、ｚ
＝０に応じたコード0110110111を選択し、｛１，−１，
１｝を符号化する場合は図７に示すＴ＝１のテーブルか
らｙ＝１、ｚ＝１に応じたコード0111を選択する。尚、
ｚ＝０の場合、すなわちランレングス圧縮が行われてい
る場合は、テーブルから選択されたコードの後に繰り返
すべき生データ（本実施例では４ビット固定のカラーコ
ード情報である。画像によっては各色毎の輝度データの
場合もあり得る。）が加えられる。たとえば、［０，
２，４］を符号化する場合は図６に示すＴ＝０のテーブ
ルから選択されたｙ＝４、ｚ＝０に応じたコード011011
0111の後に、0010が加えられる。したがって、［０，
２，４］のコードは01101101110010となる。

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

【００３８】次に、図１６乃至図１８を用いて上記の手
法で圧縮した符号を伸長する手順を示す。図１６は伸長
回路の構成例、図１７及び図１８はデータ伸長アルゴリ
ズムのフローチャートである。図１６において、２９は
入力バッファ、３０はデコーダ、３２はモードレジス
タ、３３はデータレジスタ、３４は相対位置レジスタ、
３５は辞書アドレス計算部、３６はセレクタ、３７は長
さカウンタ、３８は伸長するデータの２次元空間上の位
置を特定するＸ，Ｙカウンタ、３９は辞書コピーの際に
参照すべきデータが記憶された辞書バッファ、７１はＴ
の各値毎に用意されたテーブル群、４３は入力バッファ
２９への入力信号線、４４は出力信号線を示す。尚、テ
ーブル群７１におけるＴの値は、Ｘ，Ｙカウンタ３８に
よって特定される注目画素（伸長しようとしている部分
列の先頭画素）のＸ座標上の位置をｘとしたときに、図
３に示すフローの処理２８と同じ手法によって求められ
る。各テーブルには、注目画素のＸ座標上の位置ｘに基
づいて求めたＴの各値毎に、図６乃至図１４に示すテー
ブルと同じ情報が記憶されている。また、Ｘ，Ｙカウン
タ３８が採りうるＹ座標上の値に制限はないが、Ｘ座標
上の値は伸長しようとする２次元画像データの１ライン
の画素数をＨとした場合、０〜Ｈ−１に制限される。本
実施例では、２次元画像データの１ラインの画素数Ｈを
１６としたので、Ｘ，Ｙカウンタ３８が採りうるＸ座標
上の値は０〜１５となる。

【００３９】次に、上記のように構成された伸長回路の
動作の概要を示す。先ず、処理４４で伸長しようとする
２次元画像データの１ラインの画素数ＨをＸ，Ｙカウン
タ３８及びデコーダ３０に入力する。次に、処理４５で
Ｘ，Ｙカウンタ３８を初期化した後、入力信号線４３を
通して、入力バッファ２９に圧縮されたデータを取り込
む（処理４６）。尚、２回目以降の伸長処理において
は、入力バッファ２９に貯えられたデータのうち未処理
のビット列の後に圧縮されたデータが取り込まれる。入
力バッファ２９は、ＦＩＦＯ、シフトレジスタ等で構成
される。処理４７では、入力バッファ２９に貯えられた
ビット列長が１５ビット以上であるか否かを判断する。
これは、入力バッファ２９からデコーダ１１に渡される
ビット列長が、データ圧縮回路で圧縮されたデータの最
長ビット列長以上でなければならないからである。本実
施例による圧縮方式では、ランレングス圧縮を行った場
合において、図６乃至図１４に示すテーブルから選択さ
れたコードが１１ビットのときに、これに生データ（４
ビット固定）が加えられることにより、ビット列長が最
長の１５ビットとなる。入力バッファ２９に貯えられた
ビット列長が１５ビット以上のときは処理４８に移行
し、１５ビット未満のときは処理４６に戻る。

【００４０】処理４８では、入力バッファ２９に貯えら
れたビット列の先頭から１５ビット部分をデコーダ３０
に渡す。デコーダ３０は、Ｘ，Ｙカウンタ３８によって
特定される注目画素のＸ座標上での位置ｘ、処理４４で
入力された伸長しようとする２次元画像データの１ライ
ンの画素数Ｈ（本実施例ではＨ＝１６）、および、圧縮
回路で用いた最大検出列長Ｎ（本実施例ではＮ＝８）に
基づき、図３に示すフローの処理２８と同じ手法によっ
てＴの値を求め、その後、テーブル群７１の中からＴの
値に応じたテーブルを選択する。そして、選択したテー
ブルの中から受け取ったビット列と先頭位置からのビッ
ト列長が最も長く一致する可変長符号を検索する。たと
えば、図１５に示す符号列の０行目において、先頭位置
から１５ビットまでのデータ011011011100101 が入力バ
ッフア２９からデコーダ３０に渡された場合、Ｘ，Ｙカ
ウンタ３８によって特定される注目画素のＸ座標上での
位置ｘから求めたＴの値（この場合ｘ＝０なので、Ｔ＝
０である）に基づき、テーブル群７１の中から図６に示
すテーブルと同じ情報が記憶されたテーブルを選択す
る。そして、選択したテーブルに保持された全ての可変
長符号と入力データ011011011100101 を先頭ビットから
１ビットずつ比較していき、どの可変長符号も一致しな
くなる直前まで一致していた可変長符号をこの１５ビッ
トの入力データに隠された求める可変長符号とする。す
なわち、入力データの先頭位置からのビット列長が最も
長く一致する可変長符号をテーブル内から検索する。こ
の場合、図６から推測できるように、伸長モードがラン
レングスモード、長さが４の可変長符号0110110111が検
索される。また、図１５に示す符号列の２行目におい
て、先頭位置から１５ビットまでのデータ011011100111
100 が、入力バッフア２９からデコーダ３０に渡された
場合、Ｘ，Ｙカウンタ３８によって特定される注目画素
のＸ座標上での位置ｘから求めたＴの値（この場合ｘ＝
０なので、Ｔ＝０である）に基づき、テーブル群７１の
中から図６に示すテーブルと同じ情報が記憶されたテー
ブルを選択する。そして、選択したテーブルの中からデ
ータ011011100111100 と先頭位置からのビット列長が最
も長く一致する可変長符号を検索する。この場合、図６
から推測できるように、伸長モードが辞書コピーモー
ド、相対位置１、長さが５の可変長符号01101110が検索
される。

【００４１】処理４９では、デコーダ３０は、選択され
たテーブルの中から検索された可変長符号に基づき、ラ
ンレングスモードであるか又は辞書コピーモードである
かを識別するモードフラグをモードレジスタ３２に、長
さデータを長さカウンタ３７に、そして、モードフラグ
が辞書コピーモードの場合は相対位置データを相対位置
レジスタ３４に出力する。また、デコーダ３０は、デコ
ードしたビット列長を入力バッファ２９に、そして、モ
ードフラグがランレングスモードの場合は生データをデ
ータレジスタ３３に出力する。たとえば、図１５に示す
符号列の０行目において、先頭位置から１５ビットまで
のデータ011011011100101 が、入力バッフア２９からデ
コーダ３０に渡された場合、処理４８で検索された可変
長符号0110110111のパラメータは、伸長モードがランレ
ングスモード、長さが４である。したがって、デコーダ
３０は、ランレングスモードのモードフラグをモードレ
ジスタ３２に、長さデータの値４を長さカウンタ３７
に、処理４８で検索された可変長符号0110110111に続く
４ビット部分0010（生データ）をデータレジスタ３３
に、そして、検索された可変長符号のビット列長（１０
ビット）に生データのビット列長（４ビット固定）を加
えた１４ビット（デコードしたビット列長）を入力バッ
ファ２９に出力する。また、図１５に示す符号列の２行
目において、先頭位置から１５ビットまでのデータ0110
11100111100 が、入力バッフア２９からデコーダ３０に
渡された場合、処理４８で検索された可変長符号011011
10の各パラメータは、伸長モードが辞書コピーモード、
相対位置が１、長さが５である。したがって、デコーダ
３０は、辞書コピーモードのモードフラグをモードレジ
スタ３２に、長さデータの値５を長さカウンタ３７に、
相対位置データの値１を相対位置レジスタ３４に、そし
て、検索された可変長符号01101110のビット列長である
８ビット（デコードしたビット列長）を入力バッファ２
９に出力する。尚、デコードしたビット列長を入力バッ
ファ２９に出力するのは、入力バッファ２９に貯えられ
たデータのうち未処理のビット列の後に、デコーダ３０
でデコードされたビット列長と同じビット列長のデータ
を追加するためである。

【００４２】デコーダ３０から出力されたモードフラグ
がランレングスモードの場合は処理５０を介して処理５
１に移行し、辞書コピーモードの場合は処理５０を介し
て処理５３に移行する。尚、デコーダ３０から出力され
たモードフラグは、１つの伸長動作が完了するまでモー
ドレジスタ３２に保持される。そして、１つの伸長動作
が完了したときに、デコーダ３０から出力された新たな
モードフラグがモードレジスタ３２に保持されて、次の
伸長動作が開始される。

【００４３】処理５１では、ランレングスモードの伸長
処理を行う。尚、ランレングスモードの伸長処理では、
図２０に示すように、相対位置レジスタ３４及び辞書ア
ドレス計算部３５は作動しない。先ず、データレジスタ
３３がデコーダ３０から出力された生データを保持する
と共に、長さカウンタ３７がデコーダ３０から出力され
た長さデータを初期値としてロードする。次に、モード
レジスタ３２に保持されたランレングスのモードフラグ
に基づき、データレジスタ３３に保持された生データを
セレクタ３６を介して出力信号線４４に出力する（動作
１）。次に、次のラインデータの伸長処理を行う際に参
照すべき辞書を作成するため、出力したデータと同じも
のを、辞書バッファ３９のＸ，Ｙカウンタ３８が特定す
るＸ，Ｙ座標値に相当するアドレスに登録し（動作
２）、長さカウンタ３７をディクリメントし（動作
３）、Ｘ，Ｙカウンタ３８のＸ座標値を１つ更新する
（動作４）。尚、本実施例の場合、上述したように、
Ｘ，Ｙカウンタ３８のＸ座標値の採りうる範囲は０〜１
５である。したがって、Ｘ，Ｙカウンタ３８のＸ座標値
が１５の場合、Ｘ座標値を１つ更新するとＸ座標値は０
になり、Ｙ座標値が１つ更新される。処理５２では、上
記の動作１〜動作４を、長さカウンタ３７の値が０にな
るまで繰り返す。これにより、デコーダ３０から出力さ
れた生データがデコーダ３０から出力された長さデータ
分連続した伸長データが生成される。

【００４４】処理５３では、辞書コピーモードの伸長処
理を行う。尚、辞書コピーモードの伸長処理では、図２
０に示すように、データレジスタ３３は作動しない。先
ず、相対位置レジスタ５３がデコーダ３０から出力され
た相対位置データを保持すると共に、長さカウンタ３７
がデコーダ３０から出力された長さデータを初期値とし
てロードする。次に、辞書アドレス計算部３５により、
Ｘ，Ｙカウンタ３８が特定するＸ座標値と相対位置レジ
スタ５３に保持された相対位置データに基づき、辞書バ
ッファ３９に記憶されたデータのうち参照すべきデータ
のアドレスを求める（動作５）。そして、モードレジス
タ３２に保持された辞書コピーのモードフラグに基づ
き、辞書バッファ３９に記憶されたデータのうち辞書ア
ドレス計算部３５により特定されたアドレスのデータを
セレクタ３６を介して出力信号線４４に出力する（動作
６）。次に、次のラインデータの伸長処理を行う際に参
照すべき辞書を作成するため、出力したデータと同じも
のを、辞書バッファ３９のＸ，Ｙカウンタ３８が特定す
るＸ，Ｙ座標値に相当するアドレスに登録し（動作
７）、長さカウンタ３７をディクリメントし（動作
８）、Ｘ，Ｙカウンタ３８のＸ座標値を１つ更新する
（動作９）。処理５４では、上記の動作５〜動作９を、
長さカウンタ３７の値が０になるまで繰り返す。これに
より、辞書バッファ３９からコピーされたデータがデコ
ーダ３０から出力された長さデータ分連続した伸長デー
タが生成される。

【００４５】処理５５では、入力バッファ２９に貯えら
れたビット列の先頭からデコーダ３０でデコードされた
ビット列を捨てる。そして、伸長すべきデータが未だあ
る場合は処理４７に戻り、ない場合はこのフローを終了
する（処理５６）。

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

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

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

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

【００５０】

【発明の効果】以上詳細に説明したように、本発明によ
れば、辞書の容量は直前ラインのみを格納すれば良いの
で非常に小さく、類似度の高い範囲内で辞書を参照し、
最大検出列長の範囲内でできるだけ長い部分列を参照す
るので、圧縮率が高く且つ圧縮及び伸長を高速に処理す
ることが可能である。また、２次元画像データの１ライ
ンの画素数をＨ、最大検出列長をＮ（１≦Ｎ≦Ｈ）、注
目画素の現ライン上での先頭画素からの位置をｘ（０≦
ｘ≦Ｈ−１）とすると共に、ｘ＝０のときはＴ＝０、１
≦ｘ≦Ｈ−ＮのときはＴ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１
のときはＴ＝ｘ−Ｈ＋Ｎ＋１、とし、Ｔの各値毎に、直
前ライン上での部分列の先頭画素と注目画素との相対位
置と、直前ライン上での部分列の長さとに応じて異なる
コードが割り当てられたテーブルを用意し、注目画素の
現ライン上での先頭画素からの位置ｘに基づいてＴの値
を求め、このＴの値に応じて選択したテーブルから、相
対位置と部分列の長さに応じたコードを出力することに
よりデータ圧縮を行うので、各テーブルを予め圧縮伸長
するデータに合わせて構成されたハフマン符号のテーブ
ル、あるいは、圧縮伸長に伴い、冗長性が少なくなるよ
うに最適化されていくテーブルとすることにより、更
に、高い圧縮率が得られる。さらに、画像データの１ラ
イン目や辞書参照が不可能な部分列にランレングス圧縮
などを適用することで、更に、より高い圧縮率が得られ
る。加えて、Ｔの採りうる値は常に０≦Ｔ≦最大検出列
長Ｎとなるので、２次元画像データの１ラインの画素数
Ｈを増加したときに、テーブルの容量が増大して圧縮・
伸長速度が低下するのを防止することができる。

【図面の簡単な説明】

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

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

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

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

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

【図６】Ｔ＝０のテーブルを表した図である。

【図７】Ｔ＝１のテーブルを表した図である。

【図８】Ｔ＝２のテーブルを表した図である。

【図９】Ｔ＝３のテーブルを表した図である。

【図１０】Ｔ＝４のテーブルを表した図である。

【図１１】Ｔ＝５のテーブルを表した図である。

【図１２】Ｔ＝６のテーブルを表した図である。

【図１３】Ｔ＝７のテーブルを表した図である。

【図１４】Ｔ＝８のテーブルを表した図である。

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

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

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

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

【図１９】ランレングスモードにおけるデータ伸長回路
の動作を説明するための図である。

【図２０】辞書コピーモードにおけるデータ伸長回路の
動作を説明するための図である。

【符号の説明】

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

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成６年１１月２５日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】００３１

【補正方法】変更

【補正内容】

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

Claims (14)

【特許請求の範囲】
1. 【請求項１】 順次スキャンされる２次元画像データに
   対して直前ラインのデータを参照し、現ラインに直前ラ
   インと少なくとも１画素分以上同じ部分データ列を検出
   した場合に圧縮処理を行う２次元画像データの圧縮方式
   において、 前記２次元画像データの１ラインの画素数をＨ、前記部
   分データ列の最大検出列長をＮ（１≦Ｎ≦Ｈ）、注目画
   素の現ライン上での先頭画素からの位置をｘ（０≦ｘ≦
   Ｈ−１）とすると共に、ｘ＝０のときはＴ＝０、１≦ｘ
   ≦Ｈ−ＮのときはＴ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のと
   きはＴ＝ｘ−Ｈ＋Ｎ＋１、とし、 前記Ｔの各値毎に、直前ライン上での前記部分データ列
   の先頭画素と前記注目画素との相対位置と、前記部分デ
   ータ列の長さとに応じて異なるコードが割り当てられた
   テーブルを用意し、 現ラインに直前ラインと少なくとも１画素分以上同じ部
   分データ列を検出した場合に、前記注目画素の現ライン
   上での位置ｘに基づいて前記Ｔの値を求め、このＴの値
   に基づき対応する前記テーブルを選択し、直前ライン上
   での部分データ列の先頭位置と長さとに応じたコードを
   出力することを特徴とするデータ圧縮方式。
2. 【請求項２】 請求項１記載の発明において、前記テー
   ブルは、現ラインの入力データの注目画素と１ライン前
   の同一部分データ列の先頭画素との相対位置として、少
   なくとも同一画素位置の場合、一画素左にずれた場合、
   および一画素右にずれた場合の異なる３つの場合のコー
   ドが可変長符号で記憶されていることを特徴とするデー
   タ圧縮方式。
3. 【請求項３】 請求項１又は２記載の発明において、現
   ラインに直前ラインと同じ部分データ列を検出できなか
   った場合に、前記Ｔの各値毎に用意された、連続する同
   一データの長さに応じて異なるコードが割り当てられた
   ランレングステーブルを参照し、対応するコードを出力
   することを特徴とするデータ圧縮方式。
4. 【請求項４】 請求項３記載の発明において、前記ラン
   レングステーブルに記憶されたコードは、前記テーブル
   に記憶されたコードと異なるコードが割り当てられてい
   ることを特徴とするデータ圧縮方式。
5. 【請求項５】 請求項４記載の発明において、前記テー
   ブルと前記ランレングステーブルとを一体とし、相対位
   置として同一画素位置の場合、一画素左にずれた場合、
   一画素右にずれた場合の異なる３つの場合の同一部分デ
   ータ列の長さのコードと、ランレングスの場合の連続す
   る同一データの長さのコードとが互いに異なる可変長符
   号で記憶されていることを特徴とするデータ圧縮方式。
6. 【請求項６】 順次スキャンされる２次元画像データに
   対して直前ラインのデータを参照し、現ラインに直前ラ
   インと少なくとも１画素分以上同じ部分データ列を検出
   した場合に、重複する部分の圧縮データとして、前記２
   次元画像データの１ラインの画素数をＨ、前記部分デー
   タ列の最大検出列長をＮ（１≦Ｎ≦Ｈ）、注目画素の現
   ライン上での先頭画素からの位置をｘ（０≦ｘ≦Ｈ−
   １）とすると共に、ｘ＝０のときはＴ＝０、１≦ｘ≦Ｈ
   −ＮのときはＴ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のときは
   Ｔ＝ｘ−Ｈ＋Ｎ＋１とし、前記Ｔの各値毎に、直前ライ
   ン上での前記部分データ列の先頭画素と前記注目画素と
   の相対位置と、長さとに応じて異なるコードが順次入力
   される２次元画像圧縮データの伸長方式であって、 少なくとも直前ラインの伸長されたデータをバッファに
   保持し、 伸長しようとする前記注目画素の現ライン上での位置ｘ
   に基づいて前記Ｔの値を求め、このＴの値に基づき、前
   記Ｔの各値毎に用意された、前記相対位置と前記長さと
   に応じて異なるコードが割り当てられたテーブルから対
   応するテーブルを選択し、 入力された圧縮データから前記コードを抽出し、このコ
   ードに基づいて選択されたテーブルを参照し、入力され
   た現ラインのデータに対して、前記バッファから前記部
   分データ列の先頭位置に対応するビットに続く前記部分
   データ列の長さ分のデータを抽出し、伸長データとして
   出力することを特徴とするデータ伸長方式。
7. 【請求項７】 送信側において、順次スキャンされる２
   次元画像データに対して直前ラインのデータを参照し、
   現ラインに直前ラインと少なくとも１画素分以上同じ部
   分データ列を検出した場合に、直前ライン上にある前記
   部分データ列の先頭画素と現ライン上にある注目画素と
   の相対位置と、前記部分データ列の長さとを求め、前記
   ２次元画像データの１ラインの画素数をＨ、前記部分デ
   ータ列の最大検出列長をＮ（１≦Ｎ≦Ｈ）、注目画素の
   現ライン上での位置をｘ（０≦ｘ≦Ｈ−１）とすると共
   に、ｘ＝０のときはＴ＝０、１≦ｘ≦Ｈ−ＮのときはＴ
   ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のときはＴ＝ｘ−Ｈ＋Ｎ
   ＋１とし、前記Ｔの各値毎に用意された、前記相対位置
   と前記長さとに応じて異なるコードが割り当てられたテ
   ーブルを参照し、対応するコードを圧縮データとして出
   力し、 受信側において、少なくとも直前ラインの伸長されたデ
   ータをバッファに保持し、 伸長しようとする圧縮データの注目画素の現ライン上で
   の先頭画素からの位置ｘに基づいて前記Ｔの値を求め、
   このＴの値に対応する前記テーブルを選択し、 入力された圧縮データから前記コードを抽出し、このコ
   ードに基づいて選択されたテーブルを参照し、入力され
   た現ラインのデータに対して、前記バッファから前記部
   分データ列の先頭位置に対応するビットに続く前記部分
   データ列の長さ分のデータを抽出し、伸長データとして
   出力することを特徴とするデータ圧縮・伸長方式。
8. 【請求項８】 請求項７において、前記テーブルは、現
   ラインの入力データの注目画素と１ライン前の同一部分
   データ列の先頭画素のと相対位置として、少なくとも同
   一画素位置の場合、一画素左にずれた場合、および一画
   素右にずれた場合の異なる３つの場合のコードが記憶さ
   れていることを特徴とするデータ圧縮・伸長方式。
9. 【請求項９】 順次入力される２次元画像データに対し
   て１ライン前のデータを保持する参照メモリ手段と、 入力された現ラインの信号から、所定の長さの範囲内で
   連続する複数のデータ列を抽出し圧縮対象部分データ列
   として記憶するバッファ手段と、 前記参照メモリ手段に記憶されたデータに、前記圧縮対
   象部分データ列の注目画素に続く部分データ列と同じ部
   分データ列が存在するか否かを検出する走査比較手段
   と、 前記走査比較手段が同じ部分データ列を検出した場合
   に、前記参照メモリ手段に記憶された１ライン前のデー
   タ上での前記部分データ列の先頭画素と前記注目画素と
   の相対位置と、前記部分データ列の長さとを求め、前記
   ２次元画像データの１ラインの画素数をＨ、前記部分デ
   ータ列の最大検出列長をＮ（１≦Ｎ≦Ｈ）、注目画素の
   現ライン上での先頭画素からの位置をｘ（０≦ｘ≦Ｈ−
   １）とすると共に、ｘ＝０のときはＴ＝０、１≦ｘ≦Ｈ
   −ＮのときはＴ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のときは
   Ｔ＝ｘ−Ｈ＋Ｎ＋１、とし、前記Ｔの各値毎に用意され
   た、前記相対位置と前記部分データ列の長さとに応じて
   異なるコードが割り当てられたテーブルを参照し、対応
   するコードを現ラインのその部分データ列の圧縮データ
   として出力する符号生成手段と、 を備えたことを特徴とするデータ圧縮装置。
10. 【請求項１０】 請求項９において、前記テーブルは、
    現ラインの入力データの注目画素と１ライン前の同一部
    分データ列の先頭画素との相対位置として、少なくとも
    同一画素位置の場合、一画素左にずれた場合、一画素右
    にずれた場合の異なる３つの場合の可変長符号コードが
    記憶されていることを特徴とするデータ圧縮装置。
11. 【請求項１１】 請求項９又は１０において、現ライン
    に直前ラインと同じ部分データ列を検出できなかった場
    合に、前記Ｔの各値毎に用意された、連続する同一デー
    タの長さに応じて異なる可変長符号コードが割り当てら
    れたランレングステーブルを参照し、対応するコードを
    出力することを特徴とするデータ圧縮装置。
12. 【請求項１２】 請求項１１において、前記ランレング
    ステーブルに記憶された可変長符号コードは前記テーブ
    ルの記憶された可変長符号コードとは異なる可変長符号
    コードが割り当てられていることを特徴とするデータ圧
    縮装置。
13. 【請求項１３】 順次入力される２次元画像データに対
    して直前データを参照し、現ラインに直前ラインと少な
    くとも１画素分以上同じ部分データ列を検出した場合
    に、重複する部分の圧縮データとして、前記２次元画像
    データの１ラインの画素数をＨ、前記部分データ列の最
    大検出列長をＮ（１≦Ｎ≦Ｈ）、注目画素の現ライン上
    での先頭画素からの位置をｘ（０≦ｘ≦Ｈ−１）とする
    と共に、ｘ＝０のときはＴ＝０、１≦ｘ≦Ｈ−Ｎのとき
    はＴ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のときはＴ＝ｘ−Ｈ
    ＋Ｎ＋１とし、前記Ｔの各値毎に、直前ライン上での前
    記部分データ列の先頭画素と前記注目画素との相対位置
    と、長さとに応じて異なるコードが順次入力される２次
    元画像圧縮データの伸長装置であって、 １ライン前の伸長されたデータを保持するバッファメモ
    リ手段と、 前記Ｔの各値毎に用意された、前記コードに応じて直前
    ライン上での前記部分データ列の先頭画素と前記注目画
    素との相対位置と、前記部分データ列の長さとが割り当
    てられた逆変換テーブルと、 伸長しようとする圧縮データの注目画素の現ライン上に
    おける先頭画素からの位置ｘに基づいて前記Ｔの値を求
    め、このＴの値に対応する前記逆変換テーブルを選択
    し、入力されたデータから前記コードを抽出し、前記コ
    ードに基づいて選択された前記逆変換テーブルを参照
    し、前記逆変換テーブルから直前ライン上での前記部分
    データ列の先頭位置と長さとのデータを取り出し、前記
    バッファメモリ手段から前記部分データ列の先頭位置に
    対応するビットに続く前記部分データ列の長さ分のデー
    タを抽出し、伸長データとして出力する復号手段と、 を備えたことを特徴とするデータ伸長装置。
14. 【請求項１４】 順次入力される２次元画像データに対
    して直前ラインのデータを参照し、現ラインに直前ライ
    ンと少なくとも１画素分以上同じ部分データ列を検出し
    た場合には、重複する部分の圧縮データとして、前記２
    次元画像データの１ラインの画素数をＨ、前記部分デー
    タ列の最大検出列長をＮ（１≦Ｎ≦Ｈ）、注目画素の現
    ライン上での先頭画素からの位置をｘ（０≦ｘ≦Ｈ−
    １）とすると共に、ｘ＝０のときはＴ＝０、１≦ｘ≦Ｈ
    −ＮのときはＴ＝１、Ｈ−Ｎ＋１≦ｘ≦Ｈ−１のときは
    Ｔ＝ｘ−Ｈ＋Ｎ＋１とし、前記Ｔの各値毎に、直前ライ
    ン上での前記部分データ列の先頭画素と前記注目画素と
    の相対位置と、長さとに応じて異なるコードが順次入力
    され、また、現ラインに直前ラインと同じ部分データ列
    を検出できなかった場合には、ランレングスの圧縮デー
    タとして、前記Ｔの各値毎に、連続する同一データの長
    さに応じて異なるコードとその同一データが順次入力さ
    れる２次元画像圧縮データの伸長装置であって、 伸長しようとする圧縮データの注目画素の現ライン上に
    おける先頭画素からの位置ｘを計数するカウンタと、 １ライン前の伸長されたデータを保持するバッファメモ
    リ手段と、 前記Ｔの値毎に用意された、入力されるコードに応じ
    て、直前ライン上での前記部分データ列の先頭画素と前
    記注目画素との相対位置と、前記部分データ列の長さと
    のデータ、またはランレングス長が割り当てられた逆変
    換テーブルと、 前記カウンタの計数値によって計数された前記注目画素
    の現ライン上での先頭画素からの位置ｘに基づいて前記
    Ｔの値を求め、このＴの値に対応する前記逆変換テーブ
    ルを選択し、入力されたデータから前記コードを抽出
    し、前記コードに基づいて選択された前記逆変換テーブ
    ルを参照し、現ラインに直前ラインと同じ部分データ列
    を検出したか否かを識別するモードフラグを出力すると
    共に、前記逆変換テーブルから前記相対位置及び長さの
    データ、又は連続する同一データの長さのデータを取り
    出すデコーダと、 現ラインに直前ラインと同じ部分データ列を検出した場
    合に、前記バッファメモリ手段から前記相対位置に対応
    するビットに続く前記部分データ列の長さ分のデータを
    抽出し、伸長データとして出力する第１の復号手段と、 現ラインに直前ラインと同じ部分データ列を検出できな
    かった場合に、前記コードに続くデータを連続する同一
    データの長さ分だけ連続して出力する第２の復号手段
    と、 を備えたことを特徴とするデータ伸長装置。