JPH0918717A - データ圧縮装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】高い圧縮率の可逆圧縮方式のデータ圧縮装置を
提供する。 【構成】２次元的に配列された複数の２値画素から成る
２次元画像データを、２次元画像が縦横両方向に複数に
分割され、複数の画素から成る各画素ブロック毎に、各
画素ブロックの画素値パターンを符号化する第１の符号
化手段と、符号化された各符号のうち隣接した符号同志
を、横方向に並ぶ符号について順次比較し、隣接した符
号と同一の符号の画素ブロックの符号を第１の同一指標
符号に置換する第２の符号化手段と、符号化された各符
号のうち隣接した符号どうしを、縦方向に並ぶ符号につ
いて順次比較し、隣接した符号と同一の符号の画素ブロ
ックの符号を第２の同一指標符号に置換する第３の符号
化手段と、得られた符号群を構成する符号のうち第１及
び第２の同一指標符号に、符号群を構成する他の符号よ
りも符号長の短い符号を当て嵌めた可逆的な符号化によ
り符号化する第４の符号化手段を備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、２次元画像を表す画像
データを可逆的に圧縮するデータ圧縮装置に関するもの
である。

【０００２】

【従来の技術】データ圧縮には、データの符号化及び復
号化の過程で原データの情報損失が許容されない可逆的
データ圧縮方式と、多少の情報損失が許容される非可逆
圧縮方式とがある。このうち、可逆的データ圧縮法とし
ては、ランレングス（Ｒｕｎ Ｌｅｎｇｔｈ）法、ハフ
マン圧縮（Ｈｕｆｆｍａｎ Ｅｎｃｏｄｉｎｇ）法等が
よく知られている。前者は、連続して現れる同一データ
を特定の圧縮コードに変換することにより冗長性を減ら
してデータ量を圧縮するものであり、後者は、出現頻度
の高い文字に短いビット数の符号を与え、出現頻度の低
い文字に長いビット数の符号を与えることによりデータ
量を圧縮するものである。

【０００３】これらの代表的な可逆的データ圧縮法を基
に開発された画像データの圧縮法として、一次元符号化
方式及び二次元符号化方式がある。一次元符号化方式
は、ＭＨ（Ｍｏｄｉｆｉｅｄ Ｈｕｆｆｍａｎ）符号化
方式とも呼ばれ、上記のハフマン圧縮法を改良したもの
で、一走査線内の２値画素間の相関を利用するものであ
る。即ち、２次元的に配列された白黒の２値画素から成
る画像データにおいては白または黒の画素が連続するこ
とが多いので走査線方向に連続した白または黒の画素を
ランレングスで置き換えることにより画像データを圧縮
する。

【０００４】また、二次元符号化方式は、ＭＲ（Ｍｏｄ
ｉｆｉｅｄ Ｒｅａｄ）符号化方式とも呼ばれ、処理中
の走査線と参照用走査線とを比較し、どの位置で画素の
変化があるかにより符号化／複合化を行う方式である。
この方式では、１つの走査線の符号化が終わると、その
走査線を次の符号化のための参照用走査線として同様の
符号化を行うという処理が繰り返される。

【０００５】これら一次元符号化方式及び二次元符号化
方式はファクシミリの分野において、Ｇ３規格及びＧ４
規格として国際的にも広く用いられている。

【０００６】

【発明が解決しようとする課題】しかし、これらの従来
の可逆的データ圧縮方式には、それほど高い圧縮率（圧
縮データ列の長さに対する原データ列の長さの比率）が
得られないという問題がある。非可逆圧縮の分野では、
静止画像データ符号化用としてＪＰＥＧ（ＪｏｉｎｔＰ
ｈｏｔｏｇｒａｐｈｉｃ Ｅｘｐｅｒｔｓ Ｇｒｏｕ
ｐ）方式、動画像データ符号化用としてＭＰＥＧ（Ｍｏ
ｖｉｎｇ Ｐｉｃｔｕｒｅ ＥｘｐｅｒｔｓＧｒｏｕ
ｐ）方式等、高い圧縮率のデータ圧縮方法が開発され実
用化されているが、画像データを更に高い圧縮率で可逆
的にデータ圧縮を行いたいというニーズが強まってい
る。

【０００７】特に、特定の画像パターンが縦または横方
向の広い範囲に亘って連続して現れるような２次元画
像、例えば半導体プリント基板のパターンのように、縦
または横方向に長く延びた線状画像を主体とする２次元
画像を、高い圧縮率で可逆的にデータ圧縮することので
きるデータ圧縮装置が切望されている。本発明は、上記
の事情に鑑み、高い圧縮率の可逆圧縮方式のデータ圧縮
装置を提供することを目的とする。

【０００８】

【課題を解決するための手段】上記の目的を達成する本
発明のデータ圧縮装置は、互いに交わる第１の方向及び
第２の方向にそれぞれ複数ずつ並ぶ、２次元的に配列さ
れた複数の２値画素から成る２次元画像を表す画像デー
タを可逆的に圧縮するデータ圧縮装置において、上記２
次元画像が第１の方向及び第２の方向にそれぞれ複数に
分割されて成る、それぞれが複数の画素から成る各画素
ブロック毎に、これら各画素ブロックの画素値パターン
を符号化する第１の符号化手段と、第１の符号化手段に
より符号化された上記各画素ブロック毎の符号のうち隣
接した画素ブロックに付された符号どうしを、第１の方
向に並ぶ各画素ブロック列内の画素ブロックについて順
次比較し隣接した画素ブロックに付された符号と同一の
符号が付された画素ブロックについてその画素ブロック
の符号を隣接した画素ブロックの符号と同一の符号であ
る旨を表す第１の同一指標符号に置換する第２の符号化
手段と、第２の符号化手段により符号化された上記各画
素ブロック毎の符号のうち隣接した画素ブロックに付さ
れた符号どうしを、第２の方向に並ぶ各画素ブロック列
内の画素ブロックについて順次比較し隣接した画素ブロ
ックに付された符号と同一の符号が付された画素ブロッ
クについてその画素ブロックの符号を隣接した画素ブロ
ックの符号と同一の符号である旨を表す第２の同一指標
符号に置換する第３の符号化手段と、第３の符号化手段
による符号化により得られた符号群を構成する符号のう
ち第１の同一指標符号及び第２の同一指標符号に、これ
らの符号群を構成する他の符号よりも符号長の短い符号
を当て嵌めた可逆的な符号化により、これらの符号群を
符号化する第４の符号化手段とを備えたことを特徴とす
る。

【０００９】

【作用】本発明のデータ圧縮装置は、上記のように、互
いに交わる２つの方向にそれぞれ複数ずつ並ぶ２次元的
に配列された複数の２値画素から成る２次元画像を表す
画像データを圧縮するために、次のような第１、第２、
第３、及び第４の符号化手段を備えている。

【００１０】即ち、第１の符号化手段が、上記画像デー
タから第１及び第２の方向にそれぞれ複数に分割されて
成る、それぞれが複数の画素から成る各画素ブロック毎
に、これら各画素ブロックの画素値パターンを符号化す
る。こうすることにより、上記画像データが、２次元的
に配列され、符号化された複数の画素ブロックに変換さ
れる。

【００１１】次に、第２の符号化手段が、これらの符号
のうち隣接した画素ブロックに付された符号どうしを、
第１の方向に並ぶ各画素ブロック列内の画素ブロックに
ついて順次比較し、隣接した画素ブロックに付された符
号と同一の符号が付された画素ブロックについてその画
素ブロックの符号を、隣接した画素ブロックの符号と同
一の符号である旨を表す第１の同一指標符号に置換す
る。こうすることにより、画像データを構成する複数の
符号のうち、第１の方向に連続している同一の符号が第
１の同一指標符号に変換される。

【００１２】次に、第３の符号化手段が、これらの符号
のうち隣接した画素ブロックに付された符号どうしを、
第２の方向に並ぶ各画素ブロック列内の画素ブロックに
ついて順次比較し、隣接した画素ブロックに付された符
号と同一の符号が付された画素ブロックについてその画
素ブロックの符号を、隣接した画素ブロックの符号と同
一の符号である旨を表す第２の同一指標符号に置換す
る。こうすることにより、画像データを構成する複数の
符号のうちの、第２の方向に連続している同一の符号が
第２の同一指標符号に変換される。

【００１３】次に、第４の符号化手段が、このような符
号群を構成する符号のうち第１の同一指標符号及び第２
の同一指標符号に、これらの符号群を構成する他の符号
よりも符号長の短い符号を当て嵌めた可逆的な符号化を
行う。ここで、上記のように第１及び第２の同一指標符
号の出現確率が高く、それ以外の符号の出現確率が低い
ような確率分布を持つ画像データの場合、第４の符号化
手段にハフマン圧縮法を適用することにより、高い圧縮
率で画像データが圧縮される。

【００１４】このように、特定の画像パターンが縦また
は横方向の広い範囲に亘って連続して現れるような２次
元画像の場合、本発明のデータ圧縮装置を用いることに
より高い圧縮率でデータを圧縮することができる。

【００１５】

【実施例】以下、本発明の一実施例について説明する。
本実施例では、半導体プリント基板のパターン画像を対
象としてデータ圧縮を行う。この画像は、縦または横方
向に長く延びた線状画像が主体の２次元画像である。こ
の２次元画像を表す画像データがラスターデータとして
本実施例のデータ圧縮装置に入力される。

【００１６】図１は、本実施例のデータ圧縮装置に入力
された画像データが順次符号化されていく過程を示す説
明図である。図１（ａ）には、本実施例のデータ圧縮装
置の第１の符号化手段により１つのグループとして符号
化される、第１及び第２の方向にそれぞれ４ビット、合
計１６ビットの２値画素２０から成る画素ブロック３０
が示されている。

【００１７】１６ビットの２値画素データから成る画素
ブロック３０は、理論的には２¹⁶種類（６５５３６種
類）の画素値パターンを有するが、予めデータ圧縮の対
象となる２次元画像について解析を行い、その画像デー
タ中には出現し得ない画素値パターンを洗い出し、それ
らを除き、出現し得る画素値パターンのみを選び出して
画素値パターンを所定の符号に変換するパターン変換テ
ーブル（図示せず）を作成しておく。

【００１８】本実施例で取り扱う半導体プリント基板の
パターンの場合最狭の線幅が４画素幅分であり、白と黒
の市松模様の画素パターンや、１６画素の中に１画素だ
けが白で周りが全て黒というような画素パターン等はこ
の画像データ中には出現するはずのない画素パターンな
のでこれらを除き、出現し得る画素値パターンのみを選
び出すと、ここではその出現し得る画素パターンの種類
は２５６以下、即ち２ ⁸ 種類以下である。そこで、これ
らの出現し得る画素値パターンを８ビットの符号に変換
するパターン変換テーブルを作成しておく。これらの符
号は、例えば、１６ビット全てが白１色から構成されて
いる画素値パターンに対応する符号を”Ｘ”とし、１６
ビット全てが黒１色から構成されている画素値パターン
に対応する符号を”Ｙ”とし、第１列の４ビットのみが
黒である画素値パターンに対応する符号を”Ｚ”とし、
・・・というように設定する。

【００１９】図１（ｂ）には、このパターン変換テーブ
ルを用いて、２次元画像を構成する各画素ブロック３０
の画素値パターンが、８ビットの各符号４０（”
Ａ”，”Ｂ”，”Ｃ”，・・・）にそれぞれ変換され、
複数の符号列５１，５２，５３，・・・から成る符号群
５０が生成された様子が示されている。なお、これらの
８ビットの各符号４０は、本来２進数で表記すべきもの
であるが、図１では、説明の都合上、”Ａ”，”
Ｂ”，”Ｃ”，・・・というように、文字として表記し
た。但し、”０１”及び”００”の符号は、後述する特
別の符号として割り当てるため、ここでの符号化には、
これら２種類の符号は使用しないでおく。

【００２０】このように、ブロック化により形成された
画素値パターンの種類を特定の少数の種類に限定した上
で、各画素ブロックを、画素ブロックを構成する画素の
数より少ないビット数の符号に変換することにより、画
像データを圧縮することができる。上記の例では、４ビ
ット×４ビット＝１６ビットの画素ブロックが８ビット
の符号に変換されているのでこの段階でデータ量は５０
％に圧縮される。

【００２１】次に、図１（ｂ）の符号群５０について、
第２の符号化処理を行う。即ち、上記各画素ブロック毎
の符号のうち隣接した画素ブロックに付された符号どう
しを、第１の方向に並ぶ各画素ブロック列内の画素ブロ
ックについて順次比較し、隣接した画素ブロックに付さ
れた符号と同一の符号が付された画素ブロックについて
その画素ブロックの符号を隣接した画素ブロックの符号
と同一の符号である旨を表す第１の同一指標符号に置換
する。なお、本実施例では、第１の同一指標符号は”０
１”としている。

【００２２】例えば、図１（ｂ）の第１の符号列５１に
ついて説明すると、先ず、先頭の符号”Ａ”はそのまま
とし、符号列５１の２番目の符号から符号化処理を開始
する。即ち、符号列５１の２番目の符号”Ａ”を先頭の
符号”Ａ”と比較し、比較の結果、先頭の符号と同一の
符号なので２番目の符号”Ａ”は第１の同一指標符
号（”０１”）に置換し、以下同様に、符号列５１の最
後の符号まで第２の符号化処理を行う。次に、符号列５
２，５３，・・についても符号列５１と同様に第２の符
号化処理を続ける。

【００２３】図１（ｃ）は、第２の符号化処理により、
符号群５０を構成する各符号列５１，５２，５３，・・
・が、それぞれ各符号列６１，６２，６３，・・・に置
換された後の様子を示している。次に、図１（ｃ）の各
符号列６１，６２，６３，・・・から成る符号群６０に
ついて、第３の符号化処理を行う。即ち、上記各画素ブ
ロック毎の符号のうち隣接した画素ブロックに付された
符号どうしを、第２の方向に並ぶ各画素ブロック列内の
画素ブロックについて順次比較し、隣接した画素ブロッ
クに付された符号と同一の符号が付された画素ブロック
についてその画素ブロックの符号を隣接した画素ブロッ
クの符号と同一の符号である旨を表す第２の同一指標符
号に置換する。なお、本実施例では、第２の同一指標符
号は”００”としている。

【００２４】例えば、図１（ｃ）の縦方向（第２の方
向）の符号列について説明すると、先ず先頭の符号”
Ａ”はそのままとし、縦方向の２番目の符号から符号化
処理を開始する。即ち、縦方向の２番目の符号”Ａ”を
先頭の符号”Ａ”と比較し、比較の結果、先頭の符号と
同一の符号なので、縦方向の２番目の符号”Ａ”を第２
の同一指標符号（”００”）に置換する。次に、縦方向
の３番目の符号”Ａ”もまた、縦方向の２番目の符号”
Ａ”と同一の符号なので、縦方向の２番目の符号”Ａ”
を第２の同一指標符号（”００”）に置換し、以下同様
に、縦方向の最後の符号まで第３の符号化処理を行う。
次に、縦方向の２番目の符号列，３番目の符号列，・・
・についても縦方向の先頭の符号列と同様に、第３の符
号化処理を続ける。

【００２５】図１（ｄ）は、第３の符号化処理により、
符号群６０を構成する各符号列６１，６２，６３，・・
・が、それぞれ各符号列７１，７２，７３，・・・に置
換された後の様子を示している。次に、図１（ｄ）の各
符号列７１，７２，７３，・・・から成る符号群７０に
ついて、第４の符号化処理を行う。

【００２６】第４の符号化処理においては、図１（ｄ）
に示された符号群７０を構成する符号のうち第１の同一
指標符号”０１”及び第２の同一指標符号”００”に、
これらの符号群７０を構成する他の符号よりも符号長の
短い符号を当て嵌めた上で、いわゆるハフマン圧縮によ
る符号化が行われる。このように、第１の方向または第
２の方向に同一の画素パターンが連続して現れたことを
示す第１の同一指標符号または第２の同一指標符号に、
他の符号よりも短い符号を当て嵌めるのは、前述のよう
に、半導体プリント基板のパターンのような、特定の画
像パターンが縦または横方向に広範囲に亘って連続する
ような２次元画像の場合、全体の符号群の中に占める第
１の同一指標符号及び第２の同一指標符号の割合が極め
て高いため、この２つの同一指標符号に他の符号よりも
符号長の短い符号を当て嵌めた上でハフマン圧縮法を適
用することにより高い圧縮率でデータ圧縮するためであ
る。

【００２７】更に、第４の符号化手段にランレングス圧
縮機能を付加することにより、圧縮率を一層高めること
ができる。次に、本発明の一実施例のデータ圧縮装置の
構成とその動作について説明する。本実施例で圧縮され
る２次元画像データは、半導体プリント基板１枚のパタ
ーンにつき、画素５０００のＣＣＤラインセンサ３台か
ら並列に出力される１５０００×１５０００画素のビッ
トマップ形式の２値画素から成る画像データである。な
お、１画素の大きさは約４０ミクロンである。

【００２８】この画像データがラスターデータとしてリ
アルタイムで本実施例のデータ圧縮装置に入力される。
本実施例のデータ圧縮装置には、予め、半導体プリント
基板についての過去のパターンを解析した結果に基づき
作成されたパターン変換テーブルが組み込まれている。
このパターン変換テーブルは、４０ミクロンの画素４個
を１辺とする１６個の画素から成る正方形の画素ブロッ
ク（図１（ａ）参照）単位の各画素値パターンについて
作成されたものである。従って、１画素ブロックの１辺
の長さは１６０ミクロンであり、処理対象の半導体プリ
ント基板の最小線幅に相当する。

【００２９】入力された画像データは、４ビット×４ビ
ットの画素ブロックに分割された後、第１の符号化手段
（図示せず）により、上記のパターン変換テーブルを用
いた符号化処理が行われ、図１（ｂ）に示したように、
複数の８ビットの符号４０から成る、複数の符号列５
１，５２，５３，・・・に変換される。次いで、以下に
説明する符号化・復号化装置により、図１（ｃ）に示さ
れた第２の符号化処理及び図１（ｄ）に示された第３の
符号化処理が行われる。

【００３０】図２は、本実施例の符号化・復号化装置の
ブロック図である。図２に示すように、この符号化・復
号化装置１００には、横方向符号化部１１０と、縦方向
符号化部１２０と、スイッチ１３０と、縦方向復号化部
１４０と、横方向復号化部１５０と、マルチプレクサ１
６０と、入力端子２００と、出力端子２１０と、ライン
メモリへの出力端子２２０と、ラインメモリからの入力
端子２３０と、ハフマンコーダの入出力端子２４０と、
制御信号入力端子２５０とが備えられている。

【００３１】これらのうち、横方向符号化装置１１０が
本発明の第２の符号化手段に相当するものであり、縦方
向符号化装置１２０が本発明の第３の符号化手段に相当
するものである。なお、この符号化・復号化装置１００
には、符号化機能と復号化機能の双方が備えられている
が、図２には、符号化時の接続状態が実線で示されてい
る。破線で示された部分は復号化時に機能する。

【００３２】図３は、図２に示した符号化・復号化装置
のうちの横方向符号化部のブロック図である。図３に示
すように、横方向符号化部１１０には、８ビットのレジ
スタ３００と、８ビットのコンパレータ３１０と、８ビ
ットのマルチプレクサ３２０とが備えられている。

【００３３】図４は、図２に示した符号化・復号化装置
のうちの縦方向符号化部のブロック図である。図４に示
すように、縦方向符号化部１２０には、８ビットのコン
パレータ３３０と、８ビットのマルチプレクサ３４０と
が備えられている。以下、図２乃至図４を参照しながら
符号化・復号化装置１００の符号化時の動作について説
明する。

【００３４】図１（ｂ）に示されたような、８ビットの
符号に変換された符号データ３００ａが横方向符号化部
１１０の入力端子２００から入力されると、符号データ
３００ａは横方向符号化部１１０内のレジスタ３００及
びコンパレータ３１０にそれぞれ供給される。レジスタ
３００は、入力された符号データ３００ａをデータ１個
分だけ遅延させてからコンパレータ３１０に向けて出力
する。従ってコンパレータ３１０には、レジスタ３００
から受け取った１つ前の符号データ３００ｂと今回入力
された符号データ３００ａとが同時に入力される。

【００３５】コンパレータ３１０は、これら２つの符号
データを比較し、両者が同一である時は、信号３００ｃ
の値を”１”にセットし、両者が互いに相違している時
は、信号３００ｃの値を”０”にセットする。横方向符
号化部１１０は所定のタイミングで符号データ３００ｅ
を出力するが、符号データ３００ｅの内容は、符号デー
タ３００ｅが出力される時の信号３００ｃの値により決
定される。即ち、マルチプレクサ３２０は、信号３００
ｃの値が”１”である時は予め用意されている第１の同
一指標符号（”０１”）３００ｄを出力し、信号３００
ｃの値が”０”である時は、マルチプレクサ３２０に入
力された符号データ３００ａをそのまま出力する。この
ようにして、横方向符号化部１１０により第２の符号化
処理が行われ、図１（ｃ）に示されたような符号列６
１，６２，６３，・・・が得られる。

【００３６】横方向符号化部１１０から出力された符号
データ３００ｅは、図２の縦方向符号化部１２０及びマ
ルチプレクサ１６０にそれぞれ入力される。マルチプレ
クサ１６０は、図示しない制御装置から図２の制御信号
入力端子２５０経由で入力された制御信号が符号化動作
を指示する信号である場合、入力された符号データ３０
０ｅを出力端子２２０に向かって出力する。出力端子２
２０には図示しないラインメモリが接続されており、符
号データ３００ｅは、このラインメモリによって１ライ
ン分、即ち１符号列分だけ遅延された後、入力端子２３
０を経由して符号化・復号化装置１００に戻り、図２の
縦方向符号化部１２０に入力される。

【００３７】図４の縦方向符号化部１２０のコンパレー
タ３３０では、上記の遅延データ３００ｆと、横方向符
号化部１１０から直接入力された符号データ３００ｅと
が比較され、両者が同一である時は、信号３００ｇの値
を”１”にセットし、両者が互いに相違している時は、
信号３００ｇの値を”０”にセットする。縦方向符号化
部１２０は所定のタイミングで符号データ３００ｈを出
力するが、符号データ３００ｈの内容は、符号データ３
００ｈが出力される時の信号３００ｇの値により決定さ
れる。即ち、マルチプレクサ３４０は、信号３００ｇの
値が”１”である時は予め用意されている第２の同一指
標符号（”００”）３００ｉを出力し、信号３００ｇの
値が”０”である時はマルチプレクサ３４０に入力され
た符号データ３００ｅをそのまま出力する。このように
して、縦方向符号化部１２０により第３の符号化処理が
行われ、図１（ｄ）に示されたような符号列７１，７
２，７３，・・・が得られる。

【００３８】図２の符号化・復号化装置１００のスイッ
チ１３０は、図示しない制御装置から制御信号入力端子
２５０経由で入力された制御信号が符号化動作を指示す
る信号である場合、縦方向符号化部１２０により得られ
た符号データ３００ｈを入出力端子２４０から出力す
る。符号データ３００ｈは、図１（ｄ）の符号列７１，
７２，７３，・・・から成る符号群７０に相当する。

【００３９】入出力端子２４０は、図示しない第４の符
号化手段と接続されている。第４の符号化手段として
は、いわゆるハフマンコーダと呼ばれる可変長符号圧縮
装置が用いられる。第４の符号化手段では、既に図１
（ｄ）を参照して説明したように、符号群７０を構成す
る符号のうち第１の同一指標符号及び第２の同一指標符
号に、これらの符号群７０を構成する他の符号よりも符
号長の短い符号を当て嵌めることにより、画像データが
高い圧縮率で圧縮される。

【００４０】第４の符号化手段として用いられる可変長
符号圧縮装置には、通常、ランレングス圧縮機能が組み
込まれているので、この機能を利用することにより更に
圧縮率を高めることができる。次に、上記の符号化・復
号化装置１００によって圧縮されたデータを、再び元の
画像データに復号化する過程について説明する。

【００４１】図５は、本実施例に用いられる符号化・復
号化装置の、復号化時の接続状態が実線で示されたブロ
ック図である。図６は、図５に示した符号化・復号化装
置のうちの縦方向復号化部のブロック図である。図６に
示すように、縦方向復号化部１４０には、８ビットのコ
ンパレータ４３０と、８ビットのマルチプレクサ４４０
とが備えられている。

【００４２】図７は、図５に示した符号化・復号化装置
のうちの横方向復号化部のブロック図である。図７に示
すように、横方向符号化部１５０には、８ビットのレジ
スタ４００と、８ビットのコンパレータ４１０と、８ビ
ットのマルチプレクサ４２０とが備えられている。

【００４３】以下、図５乃至図７を参照しながら符号化
・復号化装置１００の復号化時の動作について説明す
る。前述のように、第４の符号化手段により符号化され
たデータはいわゆるハフマン符号化が施されている。そ
こでこの符号化されたデータを復号化するには先ず、ハ
フマン復号化を行う必要がある。

【００４４】次に、ハフマン復号化された符号データ４
００ａは、図５の入出力端子２４０から符号化・復号化
装置１００に入力される。復号化時には、図示しない制
御装置から図５の制御信号入力端子２５０経由で入力さ
れた制御信号によってスイッチ１３０は閉じられてお
り、入力された符号データ４００ａは縦方向符号化部１
２０には入力されず、縦方向復号化部１４０に入力され
る。

【００４５】縦方向復号化部１４０に入力された符号デ
ータ４００ａは、図６のコンパレータ４３０に入力され
る。コンパレータ４３０では、符号データ４００ａが、
予め用意されている第２の同一指標符号（”００”）４
００ｉと比較され、両者が同一である時は信号４００ｇ
の値を”１”にセットし、両者が互いに相違している時
は信号４００ｇの値を”０”にセットする。

【００４６】縦方向復号化部１４０は所定のタイミング
で符号データ４００ｈを出力するが、符号データ４００
ｈの内容は、符号データ４００ｈが出力される時の信号
４００ｇの値により決定される。即ち、マルチプレクサ
４４０は、信号４００ｇの値が”１”の時はマルチプレ
クサ４４０は後述する遅延データ４００ｆを出力し、信
号４００ｇの値が”０”の時はマルチプレクサ４４０に
入力された符号データ４００ａを出力する。こうして、
図１（ｄ）に示されたような、第２の同一指標符号（”
００”）が含まれた符号群７０は、図１（ｃ）に示され
たような符号群６０に復号化される。

【００４７】縦方向復号化部１４０から出力された符号
データ４００ｅは、横方向復号化部１５０及びマルチプ
レクサ１６０にそれぞれ入力される。マルチプレクサ１
６０は、図示しない制御装置から図５の制御信号入力端
子２５０経由で入力された制御信号が復号化動作を指示
する信号である場合、入力されたデータ４００ｅを出力
端子２２０に向かって出力する。出力端子２２０には図
示しないラインメモリが接続されており、データ４００
ｅは、このラインメモリによって１ライン分、即ち１符
号列分だけ遅延された後、入力端子２３０を経由して符
号化・復号化装置１００に戻り、前述したように、遅延
データ４００ｆとして、図５の縦方向復号化部１４０に
入力される。

【００４８】一方、横方向復号化部１５０に入力された
符号データ４００ｅは、図７のコンパレータ４１０に供
給される。コンパレータ４１０では、符号データ４００
ｅと、予め用意されている第１の同一指標符号（”０
１”）４００ｄとが比較され、両者が同一である時は信
号４００ｃの値を”１”にセットし、両者が互いに相違
している時は信号４００ｃの値を”０”にセットする。

【００４９】横方向復号化部１５０からは所定のタイミ
ングで出力端子２１０から符号データ４００ｊが出力さ
れるが、符号データ４００ｊの内容は、横方向復号化部
１５０から符号データ４００ｊが出力される時の信号４
００ｃの値により決定される。即ち、信号４００ｃの値
が”１”である時はレジスタ４００にラッチされた、１
つ前の符号データと同じ値が出力され、信号４００ｃの
値が”０”である時は横方向復号化部１５０に入力され
た符号データ４００ｅの値がレジスタ４００にラッチさ
れると共に出力される。

【００５０】こうして、図１（ｃ）に示されたような、
第１の同一指標符号（”０１”）が含まれた符号群６０
は、図１（ｂ）に示されたような符号群５０に復号化さ
れる。次に、符号群５０を構成する各符号４０を、前述
したパターン変換テーブルを用いて各符号に対応する画
素値パターンの画素ブロックに変換する。次に、これら
１６ビットの画素データから成る各画素ブロックを１ビ
ット単位の画素データとして読み出すことにより元の２
次元画像が復元される。

【００５１】このようにして、半導体プリント基板のパ
ターンの画像データを圧縮すると、例えば、約１０％と
いう極めて高い圧縮率でデータ圧縮することができる。
ちなみに、従来のＭＲ方式により同一データを圧縮する
と、約５０％という低い圧縮率しか得られない。また、
本実施例においては、符号化・復号化処理による原デー
タの情報損失がなく、可逆的な符号化・復号化を行うこ
とができた。

【００５２】

【発明の効果】以上説明したように、本発明のデータ圧
縮装置によれば、高い圧縮率の可逆圧縮方式のデータ圧
縮装置を得ることができる。特に、特定の画像パターン
が縦または横方向の広い範囲に亘って連続して現れるよ
うな２次元画像の場合、特に高い圧縮率でデータを圧縮
することができる。

【図面の簡単な説明】

【図１】本実施例のデータ圧縮装置に入力された画像デ
ータが順次符号化処理されていく過程を示す説明図であ
る。

【図２】本実施例に用いられる符号化・復号化装置の符
号化動作時のブロック図である。

【図３】図２に示した符号化・復号化装置のうちの横方
向符号化部のブロック図である。

【図４】図２に示した符号化・復号化装置のうちの縦方
向符号化部のブロック図である。

【図５】本実施例に用いられる符号化・復号化装置の、
復号化時の接続状態を示すブロック図である。

【図６】図５に示した符号化・復号化装置のうちの縦方
向復号化部のブロック図である。

【図７】図５に示した符号化・復号化装置のうちの横方
向復号化部のブロック図である。

【符号の説明】

１０ 画像データ ２０ 画素 ３０ 画素ブロック ４０ 符号 ５０ 符号群 ５１，５２，５３ 符号列 ６０ 符号群 ６１，６２，６３ 符号列 ７０ 符号群 ７１，７２，７３ 符号列 １００ 符号化・復号化装置 １１０ 横方向符号化部 １２０ 縦方向符号化部 １３０ スイッチ １４０ 縦方向復号化部 １５０ 横方向復号化部 １６０ マルチプレクサ ２００，２３０ 入力端子 ２１０，２２０ 出力端子 ２４０ 入出力端子 ２５０ 制御信号入力端子 ３００ レジスタ ３００ａ，３００ｂ，３００ｅ，３００ｈ 符号デー
タ ３００ｃ，３００ｇ 信号 ３００ｄ 第１の同一指標符号 ３００ｆ 遅延データ ３００ｉ 第２の同一指標符号 ３１０ コンパレータ ３２０ マルチプレクサ ３３０ コンパレータ ３４０ マルチプレクサ ４００ レジスタ ４００ａ，４００ｂ，４００ｅ，４００ｈ，４００ｊ
符号データ ４００ｃ，４００ｇ 信号 ４００ｄ 第１の同一指標符号 ４００ｆ 遅延データ ４００ｉ 第２の同一指標符号 ４１０ コンパレータ ４２０ マルチプレクサ ４３０ コンパレータ ４４０ マルチプレクサ

Claims (1)

【特許請求の範囲】
1. 【請求項１】 互いに交わる第１の方向及び第２の方向
   にそれぞれ複数ずつ並ぶ、２次元的に配列された複数の
   ２値画素から成る２次元画像を表す画像データを可逆的
   に圧縮するデータ圧縮装置において、 前記２次元画像が前記第１の方向及び前記第２の方向に
   それぞれ複数に分割されて成る、それぞれが複数の画素
   から成る各画素ブロック毎に、該各画素ブロックの画素
   値パターンを符号化する第１の符号化手段と、 前記第１の符号化手段により符号化された前記各画素ブ
   ロック毎の符号のうち隣接した画素ブロックに付された
   符号どうしを、前記第１の方向に並ぶ各画素ブロック列
   内の画素ブロックについて順次比較し隣接した画素ブロ
   ックに付された符号と同一の符号が付された画素ブロッ
   クについて該画素ブロックの符号を隣接した画素ブロッ
   クの符号と同一の符号である旨を表す第１の同一指標符
   号に置換する第２の符号化手段と、 前記第２の符号化手段により符号化された前記各画素ブ
   ロック毎の符号のうち隣接した画素ブロックに付された
   符号どうしを、前記第２の方向に並ぶ各画素ブロック列
   内の画素ブロックについて順次比較し隣接した画素ブロ
   ックに付された符号と同一の符号が付された画素ブロッ
   クについて該画素ブロックの符号を隣接した画素ブロッ
   クの符号と同一の符号である旨を表す第２の同一指標符
   号に置換する第３の符号化手段と、 前記第３の符号化手段による符号化により得られた符号
   群を構成する符号のうち前記第１の同一指標符号及び前
   記第２の同一指標符号に、該符号群を構成する他の符号
   よりも符号長の短い符号を当て嵌めた可逆的な符号化に
   より、前記符号群を符号化する第４の符号化手段とを備
   えたことを特徴とするデータ圧縮装置。