JPH02184171A

JPH02184171A - データ圧縮方法および装置

Info

Publication number: JPH02184171A
Application number: JP1303448A
Authority: JP
Inventors: Richard A Kirk; リチャード　アンソニー　カーク
Original assignee: Crosfield Electronics Ltd
Current assignee: Crosfield Electronics Ltd
Priority date: 1988-11-25
Filing date: 1989-11-24
Publication date: 1990-07-18
Also published as: EP0370718A1; EP0370718B1; DE68915957D1; DE68915957T2; GB8827556D0; US5057939A

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、ディジタル画像又は、画像様画素データを圧
縮する方法及び装置に関する。

〔従来の技術及び発明が解決しようとする課題〕本文に
おいて、画像データは、色の指定を含んだ画像の画素と
定義され、画像様画素データは、処理前又は処理後（即
ち、ろ過後又は、圧縮後）の画像データと定義される。

従来の電気的画像生成は、比較的高分解能の絵又は原文
の電気的画像を生成するために、元の絵又は原文を走査
することを含む。１インチ平方光たり３００　Ｘ　３０
０から１８００　Ｘ　１８００画素の分解能が一般的で
ある。モノクローム画像の場合には、各画素は、その画
素の明度に応じた、標準的には、零から２５５までの、
一つのディジタル値により符号化される。色付きの画像
の場合には、各画素は、例えばシアン、マゼンタ、黄色
、黒の色の要素又は輝度と色信号により定義される３か
ら４のディジタル値により標準的には符号化される。こ
れら全ての場合において、大量のディジタルデータは、
記憶装置の問題を引き起こし、又データが離れた場所に
伝送されるときには、伝送時間が長いという問題を引き
起こす。

従来から、これらの問題は、データに対しデータ圧縮技
術を適用することにより解決されてきた。

このような技術の例としては、ラン　レングス符号化（
ｒｕｎ　ｌｅｎｇｔｈ　ｅｎｃｏｄｉｎｇ）がある。他
の技術としては、変換符号（ｔｒａｎｓｆｏｒｍ　ｃｏ
ｄｉｎｇ）として知られているものがあり、これは、テ
クスチャを巧く符号化するが、鮮明な区切りの符号化に
はそれ程効率が良くない。ごく最近、鮮明な区切りを巧
（符号化するセグメント化技術（ｓｅｇａ＋ｅｎｔａｔ
ｉｏｎ　ｔｅｃｈｎｉｑｕｅ）が開発されたが、円滑な
陰影を表現するには至っていない。

〔課題を解決するだめの手段及び作用〕本発明の一面に
よれば、ディジタル画像又は画像様画素データの圧縮方
法は、画素の小プロンクについて以下の処理を実行する
ことからなる。

ａ）相対的結合重みを定義するために、ブロック中の隣
接した画素のディジタル値間の偏差を決定すること。

ｂ）ブロック中の全画素を結合する木を、木の結合重み
の合計が、最小となるように決定すること。

ｃ）しきい値より大きい重みを有する結合を切り離すこ
とにより、木をセグメントに分割し、結合された画素の
セグメントにブロックを分割すること。

ｄ）各セグメント中の全画素の値を、一つの相対的な代
表値に設定することにより、そのブロックのセグメント
化された表現を発生すること。

ｅ）圧縮されたデータを発生するために、セグメント化
された表現を圧縮すること。

本発明の第二の面によれば、ディジタル画像又は画像様
画素データを、圧縮する装置は、相対的な結合重みを定
義するために、そのブロック中の隣接した画素のディジ
タル値間の偏差を決定する手段；木のなかの結合重みの
合計が最小となるように、ブロック中の全画素を結合す
る木を決定する手段；しきい値より大きい重みを有する
結合を切り離すことによって、木をセグメントに分割し
、結合された画素のセグメントにブロックを分割する手
段；各セグメント中の全画素の値を、一つの相対的な代
表値に設定することにより、そのブロックのセグメント
化された表現を発生する手段；圧縮されたデータを発生
するために、セグメント化された表現を圧縮する手段；
よりなる。

この画像データを分析する新手法及び装置は、詳しくは
、モリス（Ｍｏｒｒｉｓ）他著、”Ｇｒａｐｈ　Ｔｈｅ
ｏｒｙｆｏｒ　ｉｍａｇｅ　ａｎａｌｙｓｉｓ：ａｎ　
ａｐｐｒｏａｃｈ　ｂａｓｅｄ　ｏｎ　ｔｈｅｓｈｏｒ
ｔｅｓｔ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　　、　ＩＥＥ
Ｅ出版、１３３巻、Ｆ部、Ｎｏ、２．４月１９８６年、
１４６−１５２真に記載されている、ある種のグラフ理
論を使用する。

しかしながら、我々は、この周知の技術が画像全体をセ
グメント化するために適用できるほどには十分簡易でな
いことを幸いとした。何故ならば、隣接した画素間の個
々の偏差（又は、結合重み）は、小さい画素の連続にし
た、非常に異なった形式の画素を結合した、大規模なパ
ス　ネットワーク（又は、木）を組み立てることは、容
易に可能であるからである。例えば、白い背景の輪郭の
はっきりしないビグネットを考えると、ビグネットは純
白から真っ黒へ滑らかに変化する。このビグネットに対
するショーテスト　スパニング　ツリー（ｓｈｏｒｔｅ
ｓｔ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ）技術の直接的な通
は、純白から真っ黒まで広がった全て異なった明度を有
する小さなリンクの結合した、ショーテストスパニング
　ツリー（ｓｈｏｒｔｅｓｔ　ｓｐａｎｎｉｎｇ　ｔｒ
ｅｅ）となるであろう。しきい値以上の重みを有する木
の中の結合を切り離すことにより、像がセグメントに分
割されたならば、ビグネット及び背景は、ビグネットの
黒の縁と背景の間に鮮明な区切りがあるにも係わらず、
一つの大きなセグメントを形成してしまうであろう。

再帰的セグメント（Ｒｅｃｕｒｓｉｖｅ　ｓｅｇ＋＋＋
ｅｎｔａｔｉｏｎ）技術は、二つの隣接したセグメント
を、最も接近した値出結合し、元の画素値から出発して
、セグメントを整値に分割するまで続けることによりこ
の問題を解決している。これによりセグメント化された
画像は、元の画像が持っている鮮明な区切りを持ってい
るが、ビグネットは、連続したセグメントに分割される
。

ある場合には、各セグメントに設定された値は、実際の
値に十分近いため、退化は殆ど無いのでテクスチャデー
タの偏差を記憶する必要はない。

しかしながら他の場合に対し、この発明はさらに、ブロ
ック中の各画素の実の値と、これに対応したセグメント
化された画像の画素値の間の偏差によって構成された、
ブロックのテクスチャ表現を発生することを含む。

この発明は、元のショーテスト　スバニングツリ−（ｓ
ｈｏｒｔｅｓｔ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ）技術を
使用するが、拡大された画像におけるビグネットの問題
を避けるために、その適用を小さい区域又はブロックに
制限している。テクスチャ表現はそのビグネット化され
た区域には、いかなる区切りをも含んでおらず、典型的
には、少ないが緩やかな変化を含み、それ故、例えば変
換符号（ｔｒａｎｓｆｏｒｍ　ｃｏｄｉｎｇ）によって
容易に符号化できるであろう。しかしながら、ある場合
には、テクスチャ表現は圧縮される必要はない。

゛木′°という言葉は、閉ループのない技別れした道を
意味する。

′°小さい”という言葉は、ブロックが画像よりも小さ
いばかりでなく、画像の輪郭がはっきりしていないとい
う事を示すことを意図している。

画素の各ブロックの大きさは、実際上経験的に選ばれる
が、典型的には８×８画素であろう。

典型的には、セグメントの画像的値は、他の値を使用す
ることもできるが、セグメント中の画素値の平均値が選
ばれるであろう。

セグメント化された画像およびテクスチャ表現に適用さ
れる圧縮技術は、それぞれ達成された圧縮が最適となる
ように選ばれ、典型的には、セグメント化された画像は
、ラン　レングス　符号化（ｒｕｎ　ｌｅｎｇｔｈ　ｅ
ｎｃｏｄｉｎｇ）または四本木圧縮軸ｕａｄｔｒｅｅ　
ｃｏｍｐｒｅｓｓｉｏｎ）を使用して圧縮され、テクス
チャ表現は、しきい値技術（ｔｈｒｅｓｈｏｌｄｉｎｇ
　ｔｅｃｈｎｉｑｕｅ）を使用して圧縮可能である。

他の考慮点は、セグメント化に先立ち、区切りを明瞭に
するため及び雑音を除去するために、前処理段階を有す
ることである。

更に他の考慮点は、本発明による方法により達成された
圧縮の成果は、他のブロックを圧縮する方法及び最良に
選択された方法に比肩しうることである０例えば、本発
明による方法は、画素値を周波数領域に変換することを
含む方法に比肩しうる。

典型的には、処理手段は、種々の段階は、対応するハー
ドウェア要素で処理されるかもしれないが、適切にプロ
グラムされたマイクロコンピュータからなりたつであろ
う。

〔実施例〕

本発明による方法及び装置の実施例は、添付された図を
参照することにより以下に説明される。

第１図は、４×４の画素ブロックに対応するディジタル
値を、ダイヤグラム形式で描いた図である。この例では
、値の一列は、例えば、モノクローム画像又は、単一色
分離に対応していると考えることができる。実際上は、
カラー画像の場合には、ブロックのセグメント化は、単
一の色要素について実行され、そして各色要素に対する
画素値が、事前の決定にしたがって圧縮される。

第１図に示した値は明度を表し、最初は、ディスク記憶
装置１の中に記憶されるであろう（第６図）。これらの
値は、電気的に、もしくはＣｒｏｓｆｉｅｌｄ　Ｅｌｅ
ｃｔｒｏｎｉｃｓ　Ｍａｇｎａｓｃａｎシステムのよう
な従来からある電気的スキャニング装置を使用して、原
画像を走査することによって発生されるであろう。ディ
ジタル値の処理は、ディスク記憶装置１も又接続された
、データーバス３に接続されたマイクロコンピュータ２
によって制御される。最初、データ値のブロックが、画
素の隣接する一組間の偏差又は結合重みを決定するため
に走査される（第７図におけるステップ２０）。この決
定に続き、ブロック内の全画素間の、閉じていない道又
は木が、道に沿った請接した画素間の結合重みの合計に
よって定義される長さ、及び画素を結合される道の長さ
が最小となるように決定されるように選択された道、と
なるように決定される。この道は、ショーテスト　スパ
ニング　ツリー（ｓｈｏｒｔｅｓｔｓｐａｎｎｉｎｇ　
ｔｒｅｅ（ＳＳＴ））として周知であり、上述の文献の
述べられた技法により決定することができる。このステ
ップは、第７図においてステップ２１として示されてお
り、第２図は、第１図に示した画素ブロックに対するＳ
ＳＴを示している。第２図の結合重みは、括弧内の値で
示されている。

第２図を参照することにより、画像の区切りは、ブロッ
クの右半分の一般的に大きい画素値と左半分の小さい値
の間に識別することができる。しかしながら、区切りの
存在に加えて、区切りによっては、容易に記述できない
画素値の変動がある。

次の段階は、マイクロコンピュータ２がしきい値、この
例では８に設定されているが、以上の結合を切り離すこ
とにより、ブロックをセグメント化する（ステップ２２
）。このしきい値は、経験的に設定される。この例では
、一つの結合が切り離され、二つのセグメントが作り出
されている（第３図）。セグメント化後、画素値が、セ
グメント内の平均値に最も近い整数（Ａ又はＢ）に設定
される。この場合は、Ａ＝４、Ｂ＝２０（第４図）であ
る。Ａ及びＢは、もし適当なら他の値を設定するこ亡が
できる。第４図から解るように、ブロックの右半分のセ
グメントと左半分のセグメントの間に定義された明確な
区切りが存在するが、全ての細かい構造は、失われてい
る。

そして、マイクロコンピュータは、第５図に示すテクス
チャ表現を発生するために、区切り表現の画素値と、第
１図に示す画素の実際の値の間の偏差を決定する（ステ
ップ２５）。第４図及び第５図の一対の画素値の合計は
、第１図に示す元の画素データから導かれることが望ま
しい。ごの二っの表現は、別々の記憶素子又は共通の記
憶装置の異なった部分からなる、それぞれの記憶装置４
゜５に記憶される。

第４図の区切り表現のデータは、ラン　レングス（ｒｕ
ｎ　ｌｅｎｇｔｈ）、四本木（ｑｕａｄ　ｔｒｅｅ）、
又は区切りを圧縮するのに適した他の符号化形式に適し
ており、マイクロコンピュータは、記憶装置４の中で、
データを、その様な技法で処理する（ステップ２４）。

記憶装置２５の中のテクスチャ表現は、要素が同じよう
な大きさであるためにしきい値符号化に、よす適してお
り、マイクロコンピュータは、このデータに対して、異
なった圧縮方法を通用する。このようにして得られた圧
縮データは、ディスク記す、α装置６の中に記憶される
ステップ（２５）。

区切り及びテクスチャ表現を発生するためには、上述の
ステップを逆に実行することにより、再現され、そして
加算される。

【図面の簡単な説明】

第１図は、画素ブロックから作られたディジタル値を示
す図。第２図は、第１図の画素ブロックのショーテスト　スバ
ニング　ツリー（ｓｈｏｒｔｅｓｔ　ｓｐａｎｎｉｎｇ
　Ｌｒｅｅ）を示す図。第３図は、画素ブロックのセグメント化を示す図。第４図は、セグメント化されたブロック内の画素値を示
す図。第５図は、ブロックのテクスチャ表現を示す図。第６図は、装置のブロックダイヤグラム図。第６図に示す装置の操作を示す流れ第７図は、線図。図において１・・・ディスク記憶装置、２・・・マイクロコンピュータ、３・・・データバス、　　　４．５６・・・ディスク記憶装置。・・・記憶装置、

Claims

【特許請求の範囲】１、ディジタル画像又は画像様画素データを圧縮する方
法において、画素の小ブロックに対し、ａ）相対的な結
合重みを定義するために、隣接した画素のディジタル値
間の偏差を決定し（２０）、ｂ）木の中の結合重みの合
計が、最小となるように、ブロック中の全画素を接続す
る木を決定し（２１）、ｃ）しきい値以上の重みを持つ結合を切り離すことによ
り、木をセグメントに分割し（２２）、そしてブロック
を結合された画素のセグメントに分割し、ｄ）各セグメント中の全ての画素の値を、一つの、相対
的な、代表値に設定することにより、ブロックのセグメ
ント化された表現を発生し、ｅ）圧縮されたデータを発
生するためにセグメント化された表現を圧縮する、ステップを実行するデータ圧縮方法。２、ブロック中の各実際の画素値と対応するセグメント
化された画素値間の偏差によって構成される、ブロック
のテクスチャ表現を発生することを更に含む、請求項１
記載の方法。３、テクスチャ表現を圧縮することを更に含む、請求項
２記載の方法。４、しきい値法（ｔｈｒｅｓｈｏｌｄｉｎｇ　ｔｅｃｈ
ｎｉｑｕｅ）によりテクスチャ表現を圧縮する請求項３
記載の方法。５、ランリンク（ｒｕｎ　ｌｉｎｋ）又は四本木（ｑｕ
ａｄ−ｔｒｅｅ）圧縮により、セグメント化された表現
を圧縮する先行するいずれかの請求項記載の方法。６、代表値がセグメント中の画素値の平均値である先行
するいずれかの請求項記載の方法。７、ディジタル画像又は画像様画素データを圧縮する装
置において、相対的な結合重みを定義するために、隣接
した画素のディジタル値間の偏差を決定する（２０）手
段と；木の中の結合重みの合計が、最小となるように、
ブロック中の全画素を接続する木を決定する（２１）手
段と；しきい値以上の重みを持つ結合を切り離すことに
より、木をセグメントに分割（２２）し、そしてブロッ
クを結合された画素のセグメントに分割する手段と；各
セグメント中の全ての画素の値を、一つの、相対的な、
代表値に設定することにより、ブロックのセグメント化
された表現を発生する手段と；圧縮されたデータを発生
するためにセグメント化された表現を圧縮する（２４）
手段からなる装置。８、ブロック中の各実際の画素値と対応するセグメント
化された画素値間の偏差によって構成される、ブロック
のテクスチャ表現を発生する手段を更に含む請求項７記
載の装置。９、テクスチャ表現を圧縮する手段を更に含む請求項８
記載の装置。