JP2006502604A

JP2006502604A - 任意形状オブジェクトの画像圧縮方法

Info

Publication number: JP2006502604A
Application number: JP2003559158A
Authority: JP
Inventors: デバーガ・ムカージー
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 2001-12-31
Filing date: 2002-12-18
Publication date: 2006-01-19
Also published as: US6862371B2; EP1464181A2; WO2003058975A3; AU2002364092A1; US20030123740A1; WO2003058975A2

Abstract

【課題】改良されたソース画像を圧縮する方法および装置を提供する。
【解決手段】圧縮するピクセルブロックのスペクトルの内容を操作する方法は、選択されたピクセルブロック（１１０）内の各ピクセルを関係ピクセル（１１４）または無関係ピクセル（１１２）として分類するステップ（６２０）を含む。この選択されたブロックに、フォワード変換が適用されて（７２０）、係数ブロックが生成される。１組の所定の制約条件に従って、係数値が変更され（７５４）、変更された係数ブロックが生成される。この１組の所定の制約条件は、関係ピクセルが、変更された係数ブロックを逆変換したものにおいて、選択されたブロックにおける値と同じ値を有するという制約条件を含む。逆のジグザグの係数の順序で進んで（７４０）、この方法は、非ゼロの量子化値を有する他の係数に対して繰り返される。

Description

［発明の分野］
この発明は、データ圧縮の分野に関する。
特に、この発明は、レートを最適化するデータ圧縮に向けられている。

［発明の背景］
連続階調画像とは、実質的に無制限の範囲の色またはグレーの濃淡を有する画像を指す。
例えば、写真は、連続階調画像である。
しかしながら、デジタルハードウェアは、有限のビット数、さらには単一のビット（すなわち「オン」または「オフ」）内で色または階調を表現することに制限される。
通常、連続階調画像は、画像要素（ピクセル）の配列に分解される。
各画素は、有限個の色または濃淡を表現することができる。
グレースケール化およびディザリングは、デジタルハードウェアの制限内で連続階調画像に近づけるために使用される２つのプロセスである。
画像をデジタル表現することにより、その画像の再現、記憶、変更、および分配が簡単になる。

連続階調画像が、デジタル形式に離散化されると、そのデジタル形式を圧縮を通じてさらに処理し、記憶必要量を削減することができる。
圧縮は、デジタル化されたソース画像と復元画像との間の相違が視覚的に知覚できないように、または、視覚的に許容できるものとなるように情報を除去する。

画像圧縮手法の中には、スペクトルの内容を直接操作することを伴うものがある。
他のファクタを考慮せずにスペクトルエネルギーを削減すると、スペクトルの内容を操作する圧縮プロセスに存在する量子化やエントロピー符号化などのレートに影響を与える要素が原因となって、最適な記憶結果は達成されないことが多い。

［発明の概要］
既知のシステムおよび方法の限界に鑑み、ソース画像を圧縮する方法および装置が提供される。

圧縮するピクセルブロックのスペクトルの内容を操作する方法は、選択されたピクセルブロック内の各ピクセルを関係ピクセルまたは無関係ピクセルとして分類するステップを含む。
この選択されたブロックに、フォワード変換が適用されて、係数ブロックが生成される。
１組の所定の制約条件に従って、係数値が変更され、変更された係数ブロックが生成される。
この１組の所定の制約条件は、関係ピクセルが、変更された係数ブロックを逆変換したものにおいて、選択されたブロックにおける値と同じ値を有するという制約条件を含む。

圧縮するピクセルブロックのスペクトルの内容を操作する別の方法は、ソース画像からソースピクセルブロックを提供するステップを含む。
これらのピクセルは、変更可能ピクセルまたは変更不能ピクセルのいずれかとして分類される。
選択されたブロックに対してフォワード変換が実行され、係数ブロックが生成される。
この係数ブロックは量子化される。
少なくとも１つの係数は、その後、複数の制約条件に従って変更され、対応するゼロの量子化係数が生成される。
特に、この係数は、選択されたブロック内の変更不能ピクセルに対応する、逆変換したもののピクセル値を変えることなく変更される。

本発明の他の特徴および利点は、添付図面および以下の詳細な説明から明らかになる。

本発明は、添付図面の図に、限定ではなく例として図示される。
これらの図において、同じ参照符号は、同様の要素を示す。

［詳細な説明］
画像処理の用途においては、ブロック圧縮アルゴリズムが普及している。
画像の形状を問わず、画像データは、ブロック圧縮アルゴリズムにより、ブロックで取り込まれて処理される。
一部のブロックは、その全体がソース画像の部分を表すピクセルから成ることがある。
他のブロックは、ブロックの形状が画像の形状と一致しないことの結果として、ソース画像の部分を表すピクセルと、ソース画像に関連しないピクセルとを含むことがある。
さらに他のブロックは、その全体がソース画像に全く関連しないピクセルから成ることがある。

図１は、任意形状のオブジェクト１０２を含んだサンプルの離散化ソース画像から選択された８×８ピクセルブロック１１０を示している。
この任意形状のオブジェクトに対応する選択されたブロックの部分は、陰影付きピクセルによって示されている。
一実施の形態では、最大２５６個の異なる色またはグレーレベル（すなわち０〜２５５）を実現できるように、各ピクセルは、関連した８ビット値を有する。

この選択されたブロックは、符号化可能平面に分解される。
選択されたブロック１１０がグレーレベルの場合、ブロック１２０およびマスク１３０に分解することができる。
代替的な実施の形態では、ソース画像ブロックは、複数の平面および関連したマスクに分解することができる。
これらのそれぞれは、画像の異なる色平面に関連付けられている。

ブロック１２０は、ソースブロック１１０そのものである。
マスク１３０は、ブロック１２０の特定のピクセルが、任意形状のオブジェクトの一部（例えばピクセル１４４）を形成するのか、それとも背景（例えばピクセル１１２）を形成するのかを示す複数の「１」および「０」からなる。
マスクは、保存されるべきブロック１２０のピクセルを効果的に特定し、任意形状のオブジェクトをその背景から弁別することを可能にする。
したがって、マスクは、本質的には、対象となっている任意形状のオブジェクトに関して、選択されたブロックのピクセルを「関係」ピクセルまたは「無関係」ピクセルとして特定するものである。

ブロック圧縮アルゴリズムは、ブロック１２０に対して適用される。
通常、マスクは、圧縮データと共に記憶されて、圧縮データからソース画像を復元することを助ける。
ソースブロックが、圧縮データから復元される際に、マスクは、関係ピクセルを特定するために使用される。
達成可能な圧縮量は、ソースブロックの許容可能な情報損失量と、選択された圧縮アルゴリズムと、ブロック内の画像の特徴との関数となる。
ピクセル値の特定の組み合わせおよび配置が、圧縮量に影響を及ぼすことを認識すると、データ圧縮の一方法は、無関係ピクセルの値を効果的に変更して、より大きな圧縮を達成するものとなる。

ブロック１２０は、マスク１３０に基づいて「ドントケア」ピクセルまたは「無関係」ピクセルの位置を強調するために「×」が使用されたブロック１４０として描き直される。
「×」のマークを付けられたピクセルの値は、いずれにしてもマスク１３０で除外されないことになるので、重要ではない。
これらの「ドントケア」ピクセルの値は、任意形状のオブジェクトの復元には無関係であるが、それらのピクセルの値は、ブロック１２０の圧縮レートに影響することがある。
したがって、より大きな圧縮効率を達成するために、これらの「ドントケア」ピクセルの値を変えるように符号化技法を変更することができる。
この手法は、再生品質に影響せず、復号アルゴリズムの変更を必要としない。

いくつかのピクセルが、ソース画像の復元に無関係であることから変更可能であるとみなすことができる多くの状況が存在する。
多くの場合、元のソース画像は、複数の平面に分解されて圧縮される。
例えば、画像を個々の色平面に分解して処理することができる。
画像を前景平面／背景平面に分解することができ、これらの平面は、ソース画像の復元中にどの平面からピクセルを供給すべきかを指定するマスクと共に使用される。
例えば、背景の前面にある任意形状のオブジェクトは、背景ではなく任意形状のオブジェクトの一部を形成するピクセルを特定するマスクの使用を通じて、背景から弁別することができる。
このようなマスクは、背景自体が対象となっていない場合に有益である。
この場合、マスクは、本質的に、関係ピクセルおよび無関係ピクセルを特定し、したがって、変更可能なピクセルを示す。

図２は、空間領域においてオペレーションを行うことができる場合のデータ圧縮の一方法を示している。
ステップ２１０において、複数のピクセルからなるソースブロックが、ソース画像から選択される。
ステップ２２０において、これらの複数のピクセルが、少なくとも２つのクラスに分類される。
第１のクラスのピクセルは、無関係または変更可能と指定される。
第２のクラスは、関係または変更不能と指定される。
例えば、任意形状のオブジェクトに関連したピクセルは、変更不能と指定される。
背景に関連したピクセル、またはそれ以外に、対象となっているオブジェクトに関連しないピクセルは、変更可能と指定される。
図１を参照して、マスク１３０は、本質的に、ソースブロックにおけるそれぞれの対応するピクセルが属するクラス（例えば、１＝変更不能、０＝変更可能）を決定する。

ソース画像データのデジタル表現を圧縮する一技法は、空間領域の画像データを周波数領域のデータに変換するステップを含む。
空間領域から周波数領域への変換は、フォワード変換とも呼ばれる。

フォワード変換は、ソース画像の調和分析に類似している。
フォワード変換を使用すると、空間画像データは、基底関数の線形結合として表される。
これらの基底関数の係数は、変換プロセス中に求められる。

次いで、これらの基底係数は、量子化または閾値処理を受けて、対応する基底関数からの寄与が除去され、あるレベルの圧縮が達成される。
次いで、残りの係数は、並べ替えられるかまたは連長符号化され、そうでない場合には画像データのさらなる圧縮を容易にするように処理される。
次いで、その結果生成された圧縮画像データは、記憶、分配、またはさらなる処理のために利用可能とされる。
これは、ジョイントフォトグラフィックエキスパートグループ（ＪＰＥＧ）によって公表された基本的技法である。

通常、ゼロの値の量子化係数の個数が多くなるほど、圧縮レートは大きくなる。
したがって、ステップ２３０において、変更可能ピクセルの値を変更して、非ゼロの量子化係数の個数を減少させることができる。
変更可能ピクセルは、変更されたブロックを量子化フォワード変換したものが、選択されたブロックを量子化フォワード変換したものよりも多くの個数のゼロの値を有するように変更される。
「レート」が圧縮画像の記憶必要量を指す場合に、このオペレーションは、圧縮画像の「レート」を削減する。
したがって、このオペレーションは、画像エンコーダの圧縮効率またはレート効率を増大させる。

ピクセルを変更する方法は、圧縮アルゴリズムの仕様に依存する。
ジョイントフォトグラフィックエキスパートグループおよびモーションピクチャエキスパートグループ（ＭＰＥＧ）は、それぞれ、スペクトルの内容を操作してデータ圧縮を行う、よく知られている奨励された画像圧縮／符号化アーキテクチャを有する。
ＪＰＥＧ圧縮は、ファクシミリの用途や標準的な印刷の用途で生じる画像など、静的な画像に多く使用される。
ＭＰＥＧフォーマットは、動的な画像または映画に使用される。
基本的なプロセスは、ＪＰＥＧによって公表されており、今日、広範囲で使用されている。
ＪＰＥＧは、離散コサイン変換（ＤＣＴ）を利用するが、フォワード変換、量子化、およびエントロピー符号化ブロックの具体的な実施は、実施者に任せられている。

図３は、画像を圧縮するブロックベースのプロセスの一実施の形態をより詳細に示している。
画像エンコーダ３２０は、離散化されたソース画像３１０を処理して、圧縮画像データ３９０を生成する。

エンコーダ３２０は、複数の８×８ソースブロックとしてソース画像３１０を処理する。
フォワード変換は、各８×８ソースブロックに対して実行される。
各８×８ソースブロックは、ｘおよびｙの２次元空間関数である６４点離散信号である。
ＤＣＴは、信号を基底関数の線形結合として表すのに使用できる多くの変換の１つである。
ＤＣＴが、ＪＰＥＧ圧縮用に選択された変換であるが、フーリエ変換や離散サイン変換（ＤＳＴ）などの他の線形フォワード変換を使用することもできる。

フォワードＤＣＴは、６４点離散信号を６４個の直交基底信号に変換する調和分析器である。
各直交基底信号は、８×８ソースブロックのスペクトルを形成する２次元空間周波数を表す。
フォワードＤＣＴの出力は、これらの直交基底信号のそれぞれの振幅を特定する係数ブロックである。
これらの振幅は、ＤＣＴ係数と呼ばれ、その値は、離散的な６４点入力信号によって決定される。

ソース画像は、離散値ｓ（ｘ，ｙ）の２次元配列としてサンプリングされる。
２次元フォワード変換を実行すると、ｓ（ｘ，ｙ）を基底関数の線形結合として表現できるように、基底係数ｃ（ｕ，ｖ）を計算することを伴う。
一実施の形態（ＤＣＴ）では、フォワード変換は、以下のようにｃ（ｕ，ｖ）を計算することを含む。

ＤＣＴの一実施の形態では、係数ｃ（ｕ，ｖ）は、次のように計算される。

２次元ＤＣＴ変換は、画像を集合的に構成する１組の基底関数の係数を特定することを含む。

図３を再び参照して、量子化器３４０は、量子化テーブル３４２に従ってＤＣＴ係数を量子化する。
量子化テーブル３４２によって特定されるように、さまざまな量子をさまざまな空間周波数と共に使用することができる。
量子化されたｃ（ｕ，ｖ）は、次のように計算することができる。

上記方程式において、「ＩＮＴ」は、結果が整数となることを確保するための整数関数である。

量子化テーブルは、異なる基底関数に対して異なるステップサイズを許容している。
したがって、量子化テーブルは、６４要素テーブルであり、各空間周波数に対して１つの要素が対応する。
一般に、周波数の高い基底関数のステップサイズは、周波数の低い基底関数のステップサイズよりも大きい。
ステップサイズは、通常、対応するコサイン基底関数の視覚的寄与の知覚閾値で選ばれる。
知覚閾値は、ソース画像の特性、表示特性、観察距離などの関数である。
したがって、量子化テーブルの選択は、用途に依存し得る。

量子化の後、エントロピー符号化が使用されて、量子化係数が効率的に表現される。
エントロピーエンコーダ３５０は、エントロピー符号化テーブル３５２を使用して、圧縮画像データ３９０を生成する。

簡単に言えば、前のゼロの個数と、現時点の量子化係数の値を表すのに必要なビットとが、ペアを形成する。
各ペアには、可変長符号を通じてそれ自身の符号語が割り当てられる。
ハフマン符号化、シャノン−ファノ符号化、および算術符号化が、一般に使用される可変長コーダの例である。
所与の要素が多く生起するほど、その対応するコードに使用されるビット数は少なくなる。
ＪＰＥＧエンコーダは、ペアの符号語を出力し、次いで、現時点の量子化係数の（可変長コーダによっても割り当てられた）符号語を出力する。

量子化ＤＣＴ係数のブロックを処理した後、ＪＰＥＧエンコーダは、ブロック列の一意のエンドを書き込み、次いで、次のブロックに移る。
すべてのブロックが終了した後、ＪＰＥＧエンコーダは、エンドオブファイルマーカを書き込む。
テーブル３５２および３４２は、復元を容易にするために、圧縮画像データ内に組み込むことができる。

量子化の結果は、ＤＣＴ係数の多くがゼロに縮小されたものとなる。
特に、周波数の高いコサイン基底関数に対応する係数ほど、ゼロになる傾向がある。
量子化ＤＣＴ係数を配列して、ゼロ値要素のより長い列を得ることにより、エントロピーエンコーダのレート効率が改善され、特に、残りの符号化対象のあらゆる量子化ＤＣＴ係数がすべてゼロである箇所でレート効率が改善される。
したがって、エントロピーエンコーダは、図４に示すように、周波数の低い基底関数に関連した量子化係数から周波数の高い基底関数に関連した量子化係数に進むジグザグ形式で、量子化ＤＣＴ係数ブロックを符号化する。

ブロック４１０の左上のコーナは、ＤＣ項（ｕ，ｖ＝０）に対応する。
このＤＣ項は、個々の符号化ブロック全体にわたって差分符号化（differentially encoded）される。
残りのＡＣ項は、右下のコーナに向かって進むほど周波数が高くなるコサイン基底関数を表す。
ＪＰＥＧエントロピーエンコーダは、ブロックエンドを書き込む前に、最高周波数の非ゼロの量子化係数までを符号化することのみ必要とされる。
他のあらゆる係数は、ゼロと仮定される。

このジグザグスキャンの順序は、符号化対象の要素列の一方の端に多数の非ゼロの要素をグループ化する傾向がある。
周波数の高い基底係数がゼロである場合に、このジグザグスキャンの順序は、符号化される量子化係数の列の端にゼロの要素をグループ化する。
したがって、エントロピーエンコーダのレート効率が改善される。
ＪＰＥＧエンコーダは、このスキャンの順序で最後の非ゼロの量子化係数を越えて符号化を行う必要はない。
高位の周波数ほどゼロになる確率が高いことから、このジグザグスキャンの順序は、このように、ＪＰＥＧエンコーダの圧縮効率を増大させる。

図５は、圧縮画像データ５１０から復元ソース画像５９０を生成するデコーダ５２０を示している。
エントロピーデコーダ５３０およびエントロピーデコーダテーブル５３２が使用されて、量子化ＤＣＴ係数が元に戻される。
逆量子化器５４０は、逆量子化器テーブル５４２を使用して、逆量子化ＤＣＴ係数を生成する。
一実施の形態では、逆量子化器テーブル５４２は、量子化器テーブル３４２と同じである。
逆量子化係数に対して、逆変換が実行されて、復元ソース画像が生成される。
ＪＰＥＧが適用される場合、ブロック５５０が、逆量子化ＤＣＴ係数に対して逆ＤＣＴ変換を実行し、復元ソース画像５９０が得られる。

基本スペクトル操作符号化プロセスを変更して、ソース画像の復元に無関係であるが、レート効率に大きな影響を及ぼし得るピクセル値の変更を許容することができる。

ブロックの６４個のピクセルを、ベクトルｚと表記する。
このベクトルは、
ｚ ^Ｔ＝｛ｙ ^Ｔ，ｘ ^Ｔ｝
となるような、より小さな２つのベクトルｙおよびｘから構成される。
ここで、ｙは、Ｎ_ｙ個の関係ピクセルの集合であり、ｘは、６４−Ｎ_ｙ個の無関係ピクセルの集合である。
このベクトルの６４×６４の２ＤのＤＣＴ変換行列は、係数の集合ｃがｃ＝Ｔｚによって与えられるようなＴで表記される。

１つの手法として、既知のベクトルｙに影響を及ぼさずに、ＡＣ係数のエネルギーを最小にするベクトルｚのベクトルｘについて解くものを挙げることができる。
次いで、最小にすべきコスト関数が、以下の方程式によって与えられる。

２ＤのＤＣＴのＤＣ係数は、以下の方程式によって与えられる。

Ｊ（ｘ）が、ｘの各要素ｘ_ｉに関して部分的に導出され、ゼロと同等をみなされると、各要素は、以下の方程式によって与えられる同じ最適値を生成するように求められる。

したがって、ＡＣ係数のエネルギーを最小にする観点からの変更可能ピクセルの最適な補間は、すべての変更可能ピクセルの値を変更不能ピクセルの平均に設定する解となる。
この手法は、良い開始点とはなり得るが、差分ＤＣ符号化の影響およびブロック圧縮アルゴリズムエントロピーエンコーダの詳細を無視する。

目的は、他の制約条件を満たしつつ、逆のジグザグスキャンパスに沿ったゼロの連続を最大にすることにより、レートを最小にするｚを求めることである。
例えば、いずれの変更可能なｚ_ｉにも、実現可能な範囲内のピクセル値を割り当てなければならず、変更不能ピクセルのｚ_ｉは、以下の方程式で与えられるように、変更されるべきではない。
ｚ_ｉ＝ｙ_ｉｉ＝｛０，１，…，Ｎ_ｙ−１｝
０≦ｚ_ｉ≦２５５ｉ＝｛Ｎ_ｙ，…，６３｝

変更されたブロックのＤＣＴ係数について考察する。
いくつかの係数は、ゼロに量子化される一方、それ以外の係数は、非ゼロの値に量子化される。
ゼロに量子化できる係数の位置（すなわちインデックス）は、以下のような集合Ｉ_ｚｅｒｏを形成する。

係数は、逆のジグザグスキャンの順序でスキャンされ、ゼロに量子化されない最初の係数ｃ_ｊが検出される。
他の制約条件に違反することなく、その係数をゼロに「プッシュ（push）」することが可能な場合には、上記制約条件
ｚ_ｉ＝ｙ_ｉｉ＝｛０，１，…，Ｎ_ｙ−１｝
０≦ｚ_ｉ≦２５５ｉ＝｛Ｎ_ｙ，…，６３｝
に加えて、Ｉ_ｚｅｒｏ集合から得られる以下の制約を満たす解ｚが存在する。

（すなわち、以下の制約条件をも満たす場合に、ゼロに量子化されるどの係数も、非ゼロに量子化することはできない。）

項ｔ _ｉは、ＤＣＴ行列Ｔの第ｉ行を表す。
それぞれのゼロ量子化の制約条件は、１次不等式の制約条件である。
実現可能な解の存在は、シンプレックス法などの技法を使用して容易に解くことができるフェーズ１線形計画問題である。
係数値の変更は、このような変更を制限する等式制約条件の結果として、関係ピクセルの値に影響を与えるものではない。
選択されたブロックの関係ピクセルは、変更された係数ブロックを逆変換したものの対応するピクセルと同じ値を有することになる。
変更された係数ブロックを逆変換したものは、選択されたブロックを変更したものである。

解が存在すると、新たなゼロの量子化係数のインデックスが、Ｉ_ｚｅｒｏ集合に加えられ、ｚは、実現可能な解に更新される。
ｃ_ｊがゼロに量子化できない場合には、この方法は、逆のジグザグの順序で進んだ次の非ゼロの係数に進む。
このプロセスは、すべての非ゼロの量子化係数が検査されるまで繰り返すことができる。

その結果生成された解は、すべての制約条件を満たすものではあるが、この解は、係数のエネルギーを最小にするという意味で最適でないことがある。
ゼロの連続の長さまたは個数を最大にすることに加えて、非ゼロの量子化係数のエネルギーを最小にして、最も低いレートに到達すべきである。
各段階における最小エネルギーの解は、以下のものを最小にする。

これは、上記に規定した以下の制約条件に従う。

ＤＣ値は、関係ピクセル値の平均に関して差動的であるとみなされる。
上記問題は、一連の１次等式および１次不等式の制約条件に従う２次コスト関数となる。
解を特定するために、２次計画法を適用することができる。
この２次解法は、一連のフェーズ１線形計画法の後にのみ起動する必要がある。

一連の線形計画法は、ゼロの量子化係数の個数を増加させるが、残りのＤＣＴ係数のエネルギーが、補間された最適な平均ブロックのものより高くなることがある解を生成する。
エネルギーがあまり増加しすぎると、ゼロの連続が最大になった場合であっても、レートは増加することがある。

この結果を回避するために、２次計画法を、実現可能な解が求められた後の各段階で起動することができる。
この場合、２次計画法は、補間された平均ブロックの係数エネルギーに対する変更された最も新しいブロックの係数エネルギーの比に基づいた停止判断基準を使用する。
選択されたブロックを変更したもののエネルギーＥが、補間された平均ブロックのエネルギーＥ_０の所定の比Ｔ_Ｅ（Ｔ_Ｅ>１）を越える場合には、最適化は終了して、レートが高くなることが回避される。

図６および図７は、このプロセスを図の形で示している。
ステップ６１０において、ソース画像の少なくとも一部を含むピクセルブロックが選択される。
この選択されたブロックのピクセルは、ステップ６２０において、関係ピクセルまたは無関係ピクセルとして分類される。

ステップ６３０によって判断されるように、ブロックが、関係ピクセルおよび無関係ピクセルを混合したものを含む場合には、標準的なブロック圧縮アルゴリズム（例えばＪＰＥＧ）がステップ６７０において適用される前に、図７の最適化プロセスが、ステップ６５０において起動される。
ステップ６５０によって判断されるように、ブロックが無関係ピクセルのみから成る場合には、ステップ６７０において処理される前に、ステップ６６０において、０などの共通の所定値、または、前のブロックからの関係ピクセルの平均をすべてのピクセルに割り当てることにより、ブロックは変更される。
ブロックが関係ピクセル（すなわち変更不能）のみから成る場合には、選択されたブロックを変更することなく、標準的なブロック圧縮アルゴリズムが、ステップ６７０において適用される。

図７は、関係ピクセルおよび無関係ピクセルの混合したものを有するブロックの圧縮前の最適化プロセスを示している。
ステップ７１０において、無関係ピクセルが初期化される。
一実施の形態では、無関係ピクセルは、選択されたブロックの関係ピクセルの平均ピクセル値に対応する値に設定される。
ステップ７１２において、選択されたブロックのエネルギー（初期化後）が、Ｅ_０として計算される。

ステップ７２０において、選択されたブロックに対してフォワード変換を適用することにより、係数ブロックが生成される。
ステップ７３０において、すべてのゼロの量子化係数の位置が、配列Ｉ_ｚｅｒｏに記憶される。

逆のジグザグの順序で進んで、選択された非ゼロの量子化係数の位置が、ステップ７４０において特定される。
ステップ７５０において、選択された係数の値が、現時点のｚ用に計算される。

ステップ７５２は、選択された係数がゼロに量子化されるかどうかを判断する。
ゼロに量子化される場合には、ステップ７７０において、その係数の位置が、他のゼロの量子化係数からなるＩ_ｚｅｒｏ集合に追加される。

選択された係数がゼロに量子化されない場合には、ステップ７５４は、上記で特定した制約条件に従って、量子化係数がゼロとなる実現可能な解が存在するかどうかを判断する。
一実施の形態では、フェーズ１線形計画法が使用されて、このような実現可能な解が特定される。
一実施の形態では、シンプレックス法が使用されて、実現可能な解が特定される。
実現可能な解が存在しない場合には、処理は、ステップ７８０に続く。

実現可能な解が存在する場合には、ステップ７６０において、２次計画法が使用されて、ｚの極小エネルギー解が特定される。
この新たなｚは、ステップ７６２において計算される関連したエネルギーＥを有する。

ステップ７６４は、Ｅ／Ｅ_０>Ｔ_Ｅであるかどうかを判断する。
ここで、Ｔ_Ｅは、Ｅ_０に対するＥの比の許容可能な閾値である。
Ｅ／Ｅ_０≦Ｔ_Ｅである場合には、ステップ７７０において、その係数の位置が、他のゼロの量子化係数からなるＩ_ｚｅｒｏ集合に追加され、処理は、ステップ７８０に続く。

ステップ７５４またはステップ７７０のいずれかから進んで、ステップ７８０において、処理すべき係数がさらに存在するかどうかを判断するチェックが行われる。
存在しない場合には、係数ブロックの変更プロセスは、ステップ７９０において完了する。
存在する場合には、プロセスは、ステップ７４０に戻ることによって、次の非ゼロの量子化係数で継続される。

この最適化プロセスは、すべての非ゼロの量子化係数が処理されるまで、または、結果のエネルギーが所定の閾値を越えるまで、ステップ７４０〜７８０を繰り返す。

上記プロセスは、関係ピクセルの平均値を無関係ピクセルのすべてに割り当てることによってブロックが初期化される場合の基本的な方法を説明しているが、変換領域（translated domain）で動作する場合に、これらの計算の複雑さを減少させることができる。
以下の並進変換（translational transformation）を使用することによって、２次コスト関数を簡単なエネルギー関数に変換することができる。

他の制約条件のすべても、同様にして、関係ピクセルの平均値分だけ適切にシフトしなければならない。
例えば、無関係ピクセルは、ゼロに初期化される。

一実施の形態では、このプロセスは、処理すべき係数がさらに残っているかどうかにかかわらず、最初に実現可能な解を求めることができない時に停止する。
この手法は、ゼロについて最後に連続したものの長さを最大にする。
最後に連続したものは、エントロピーエンコーダのオペレーションの原理により、ＪＰＥＧエンコーダの符号化レートに最も大きな影響を及ぼす。

図８は、図７の方法の代替的な実施の形態を示している。
この代替的な実施の形態は、実現可能なゼロの量子化解が存在しない係数に遭遇した後に、非ゼロの量子化係数をさらに探索することを停止するものである。
図７と図８とを比較すると、実現可能な解が存在しないとステップ８５４が判断すると、プロセスは、ステップ８８０において後続の非ゼロの量子化係数を処理する準備をするのではなく、ステップ８９０において終了する。

図９は、２次計画法が、終了段階（すなわち、すべての係数が処理された後）においてのみ実行される別の変形を示している。
したがって、実現可能な解が存在するとステップ９５４が判断すると、上記同様に、ステップ９７０において、その係数の位置がＩ_ｚｅｒｏに追加される。
しかしながら、ステップ９８０によって判断されるように、処理すべき係数がもはや存在しなくなった後にのみ、２次計画法が、ステップ９６０において適用される。
次いで、プロセスは、ステップ９９０において完了する。

このスペクトル内容操作の方法は、１）ゼロの量子化係数の個数を増加させる傾向を有し、２）周波数の高い基底関数に関連した連続するゼロの量子化係数の個数を増加させることを優先する傾向を有する。
このエントロピーエンコーダの特異性を考えると、これにより、ＪＰＥＧエンコーダは、ブロックエンドを発行する前に、より少ないデータを使用して関係画像を表現することができる。

この改良されたプロセスの１つの特定の利点は、デコーダに変更を行う必要がないということである。
したがって、圧縮画像データの生成には、計算資源がより多く必要となることはあるが、圧縮データの復号には、資源を追加する必要はない。
さらに、関係ピクセルは保存されるので、ピクセル操作を伴わない圧縮から復元された画像と、ピクセル操作を伴った圧縮から復元された画像との該当する部分には、相違は存在しない。

上記詳細な説明では、本発明を、その特定の例示の実施の形態に関して説明している。
特許請求項に記載される本発明のより広い精神および範囲から逸脱することなく、さまざまな変更および変形をそれらの実施の形態に対して行うことができる。
したがって、明細書および図面は、限定する意味ではなく、例示の意味で考慮されるべきである。

任意形状のオブジェクトのソース画像からの８×８ブロックの画像平面およびマスクへの分解を示す図である。選択されたピクセル値を変えて、圧縮レートを改善する方法を示す図である。ブロック指向型圧縮プロセスの一実施の形態を示す図である。エントロピー符号化係数のジグザグ処理順序を示す図である。図３の方法で圧縮された画像を伸張するプロセスの一実施の形態を示す図である。圧縮するブロックのルーティングを示す図である。複数の制約条件に従って、選択されたピクセルブロックのスペクトルの内容を変更する方法を示す図である。複数の制約条件に従って、選択されたピクセルブロックのスペクトルの内容を変更する方法の代替的な実施の形態を示す図である。複数の制約条件に従って、選択されたピクセルブロックのスペクトルの内容を変更する方法の別の実施の形態を示す図である。

符号の説明

３１０・・・ソース画像、
３３０・・・フォワード離散コサイン変換（ＦＤＣＴ）、
３４０・・・量子化器、
３４２、３５２・・・テーブル、
３５０・・・エントロピーエンコーダ、
３９０・・・圧縮画像データ、
５１０・・・ソース画像、
５３０・・・フォワード離散コサイン変換（ＦＤＣＴ）、
５４０・・・量子化器、
５４２，５５２・・・テーブル、
５５０・・・エントロピーエンコーダ、
５９０・・・圧縮画像データ、

Claims

圧縮するピクセルブロックのスペクトルの内容を操作する方法であって、
ａ）選択されたピクセルブロック（１１０）内の各ピクセルを関係ピクセルまたは無関係ピクセルとして分類するステップ（６２０）と、
ｂ）前記選択されたブロックのフォワード変換を表す係数ブロックを生成するステップ（７２０）と、
ｃ）係数値を変更するステップ（７５４）であって、それによって、前記関係ピクセルが、変更された係数ブロックを逆変換したものにおいて、前記選択されたブロックにおける値と同じ値を有するという制約条件を含む１組の所定の制約条件に従って、前記変更された係数ブロックを生成する、変更するステップ（７５４）と
を含む方法。
ｄ）ソース画像のすべてのピクセルブロックに対して、前記ステップａ）〜ｃ）を繰り返すステップ
をさらに含む請求項１に記載の方法。
前記ステップｃ）は、
ｉ）逆のジグザグの順序で前記係数ブロックから係数を選択するステップ（７４０）であって、該選択した係数は非ゼロの値を有する、選択するステップ（７４０）と、
ｉｉ）前記所定の制約条件に従って、選択した係数をゼロに量子化可能とする実現可能な解を求めるステップと
を含む
請求項１に記載の方法。
前記逆のジグザグの順序で前記選択した係数に先行するゼロに量子化可能な任意の係数は、非ゼロに量子化可能になることが許容されないという制約条件に従って変更される
請求項３に記載の方法。
ｄ）前記係数ブロックをエントロピー符号化するステップ（５５０）であって、前記選択されたブロックに対応する圧縮データを生成するステップ
をさらに含む請求項１に記載の方法。
マスク（１３０）の個々の要素の値は、前記選択されたブロック内の対応する位置のピクセルを関係ピクセルまたは無関係ピクセルとして分類する
請求項１に記載の方法。
前記選択されたブロック（１１０）は、
オブジェクトに関連した関係ピクセル（１１４）と、
オブジェクトに関連しない無関係ピクセル（１１２）とを含む
請求項１に記載の圧縮方法。
ｄ）前記変更された係数ブロックをブロック圧縮プロセスに提供するステップ（６７０）
をさらに含む請求項１に記載の方法。
前記ステップｄ）は、
線形計画法を適用するステップであって、前記制約条件に従って係数をゼロに量子化可能とする実現可能な解を特定するステップ
をさらに含む
請求項１に記載の方法。
２次計画法を適用するステップ（７６０）であって、極小のエネルギーを有する選択されたブロックを変更したものを生成するステップ
をさらに含む請求項９に記載の方法。