(57)【要約】【課題】  ラスタコンテンツの混合したものを表現するために複合文書を分解する方法を提供する。【解決手段】  画像を分解する方法は、画像を複数のストライプ（２２０）に分解するステップを含む。各ストライプ（３１０）は、前景レイヤ（１２０）、背景レイヤ（１３０）、およびマスクレイヤ（１４０）に分解される（４５０）。これらのレイヤは、より効率的な圧縮を達成するために、無関係ピクセルの値を変更するように補間される（４６０）。これらのレイヤは、その後、コーダで圧縮することができる。
2005516553.tif 000002
【特許請求の範囲】
【請求項１】
画像を分解する方法であって、
ａ）前記画像を複数のストライプに分解するステップ（２２０）と、
ｂ）各ストライプを前景画像レイヤ（１２０）および背景画像レイヤ（１３０）ならびにマスクレイヤ（１４０）に分解するステップ（４４０）と、
ｃ）前記前景レイヤおよび前記背景レイヤの無関係ピクセル値を、コーダの効率性が得られるように補間するステップ（４６０）と
を含む画像を分解する方法。
【請求項２】
ｄ）前記前景レイヤ、前記背景レイヤ、および前記マスクレイヤを符号化するステップ（４７０）
をさらに含む請求項１に記載の画像を分解する方法。
【請求項３】
前記前景および前記背景はＪＰＥＧで符号化され、前記マスクはＪＢＩＧで符号化される
請求項２に記載の画像を分解する方法。
【請求項４】
前記ステップｃ）は、
ｉ）レイヤベース色と、各レイヤの縮小された共通領域（７２２、７３２）へのオフセットとを求めるステップ（４５０）であって、縮小された共通領域の重なり合った部分（７３２）を除くすべての領域の画像レイヤの値およびマスクレイヤの値を求めるステップと、
ｉｉ）前記縮小された共通領域の重なり合った部分を、前記前景レイヤと、前記背景レイヤとに分離するステップ（４５０）と
をさらに含む請求項１に記載の画像を分解する方法。
【請求項５】
前記ステップｃ）は、
ｉ）選択されたレイヤの選択されたブロック内の各ピクセルを関係ピクセルまたは無関係ピクセルとして分類するステップ（１０２０）と、
ｉｉ）前記選択されたブロックのフォワード変換を表す係数ブロックを生成するステップ（１３２０）と、
ｉｉｉ）係数値を変更するステップ（１３５４）であって、前記関係ピクセルが、前記変更された係数ブロックを逆変換したものにおいて、前記選択されたブロックにおける値と同じ値を有するという制約条件を含む１組の所定の制約条件に従って、変更された係数ブロックを生成するステップと、
をさらに含む請求項１に記載の画像を分解する方法。
【請求項６】
前記ステップｃ）ｉｉｉ）は、
ａ）逆のジグザグの順序で前記係数ブロックから係数を選択するステップ（１３４０）であって、該選択した係数は非ゼロの値を有するステップと、
ｂ）前記所定の制約条件に従って、選択した係数をゼロに量子化可能とする実現可能な解を求めるステップと
を含む請求項５に記載の画像を分解する方法。
【請求項７】
前記逆のジグザグの順序で、前記選択した係数に先行するゼロに量子化可能な係数は、非ゼロに量子化可能になることが許容されないという制約条件に従って変更される
請求項５に記載の画像を分解する方法。
【請求項８】
マスクの個々の要素の値は、前記選択したブロック内の対応する位置のピクセルを関係ピクセルまたは無関係ピクセルとして分類する
請求項５に記載の画像を分解する方法。
【請求項９】
ｄ）前記変更された係数ブロックをブロック圧縮プロセス（１１５０）に提供するステップ
をさらに含む請求項５に記載の画像を分解する方法。
【請求項１０】
前記ステップｃ）は、
線形計画法を適用するステップであって、前記制約条件に従って係数をゼロに量子化可能とする実現可能な解を求めるステップ
をさらに含む
請求項５に記載の画像を分解する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
この発明は、データ圧縮の分野に関する。
特に、この発明は、複合文書の表現および圧縮に向けられている。
【背景技術】
【０００２】
［発明の背景］
複合文書は、カラー画像、カラーテキスト、およびカラー図形を含むことができる。
複合ラスタコンテンツ（ＭＲＣ（mixed raster content））は、複合文書を、複数のレイヤを融合したものとして効率的に表現するための方法を指定する国際電気通信連合の標準規格（ＩＴＵ  Ｔ．４４  ０４／１９９９）である。
また、ＭＲＣは、個々のレイヤ用の所定のエンコーダを使用して文書を圧縮する方法も指定する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ＩＴＵ  Ｔ．４４標準規格は、レイヤが特定された際の文書の効率的な表現方法を説明しているが、この標準規格は、ＭＲＣ文書を個々のレイヤに分解することに対処していない。
しかしながら、分解手法は、その結果生成されるレイヤの圧縮レートに大きな影響を及ぼすことがあり、したがって、圧縮文書のサイズに大きな影響を及ぼすことがある。
したがって、いくつかの異なる文書分解が存在し得るが、それらは、すべてが同じレベルの分解をもたらすとは限らない。
最適なレートおよび品質を有する分解を特定するために各分解を試してみることは困難である。
【非特許文献１】ＩＴＵ  Ｔ．４４標準規格
【課題を解決するための手段】
【０００４】
［発明の概要］
既知のシステムおよび方法の限界に鑑み、ラスタコンテンツの混合したものの表現および圧縮を行うために複合文書を分解する方法および装置が提供される。
【０００５】
画像を分解する方法は、画像を複数のストライプに分解するステップを含む。
各ストライプは、前景レイヤ、背景レイヤ、およびマスクレイヤに分解される。
これらのレイヤは、より効率的な圧縮を達成するために、無関係（irrelevant）ピクセルの値を変更するように補間される。
これらのレイヤは、その後、コーダで圧縮することができる。
【０００６】
一実施の形態では、外周部検出機能が、共通領域縮小機能と共に使用され、各レイヤのベース色と、縮小された共通領域へのオフセットとが特定される。
したがって、ストライプは、前景の縮小された共通領域と背景の縮小された共通領域とが重なり合った部分を除くすべての領域について、前景レイヤと背景レイヤとに効果的に分離される。
補間前に、コーダに整合したレイヤ分離プロセスが、縮小された共通領域の重なり合った部分に適用され、この重なり合った部分は、前景レイヤと背景レイヤとに分離される。
【０００７】
本発明は、添付図面の図に、限定ではなく例として図示される。
これらの図において、同じ参照符号は同様の要素を示す。
【発明を実施するための最良の形態】
【０００８】
［詳細な説明］
一実施の形態では、ＭＲＣは、図１に示すように、３つのレイヤ（背景１３０、前景１２０、およびマスク１４０）を使用して複合文書１１０を表現する。
背景および前景は画像レイヤであり、マスクレイヤはバイナリ（すなわち１ピクセルあたり１ビット）である。
文書は、レイヤとして表現されると、圧縮することができる。
背景レイヤおよび前景レイヤは、オリジナルよりも低い解像度で符号化されることがあるが、マスクは、常に、最大解像度で損失のない方法で符号化される。
３レイヤモデルは、（画像、マスクの）ペアでレイヤを追加することにより、Ｎレイヤに拡張することができる。
【０００９】
オリジナルの文書を復元するために、背景レイヤおよび前景レイヤは、その対応する圧縮されたレイヤデータから復元される。
マスクは、復元される文書のピクセルが、復元される背景レイヤによって提供されるのか、それとも復元される前景レイヤによって提供されるのかを特定する。
【００１０】
標準規格は、前景画像レイヤおよび背景画像レイヤ用にＪＰＥＧ（ジョイントフォトグラフィックエキスパートグループ）圧縮またはＪＢＩＧ（ジョイントバイレベルイメージエキスパートグループ）圧縮の使用をサポートする。
標準規格は、マスクレイヤ用にグループ３（Ｇ３）圧縮、グループ４（Ｇ４）圧縮、およびＪＢＩＧ圧縮をサポートする。
【００１１】
ＭＲＣは、一連のストライプとして文書を符号化することをサポートする。
図２は、複合文書２１０のストライプ分解を示している。
文書は、分析のためにストライプにされる。
ストライプにされた文書２２０のストライプは、分析されて、ブロック２３０に分解される。
各ストライプの背景データ２３６、前景データ２３８、およびマスクデータ２３４、ならびにストライプパラメータ２３２は、ストライプデータ２４２として、ＭＲＣビットストリーム２４０にカプセル化される。
ＭＲＣ標準規格は、ブロック２３０によって提供される分析の仕様にも、分解の仕様にも対処していない。
【００１２】
分解プロセスの１つの目的は、妥当な複雑さの制約内に留まりつつ、符号化されたビットストリームのコンパクト性および復元される画像の品質の観点で新しい最適な分解を得ることである。
符号化されたビットストリームを最適化するには、個々のレイヤデータに適用されるエンコーダの特性を考慮する必要がある。
図示した実施の形態では、ブロック２３０は、ＪＰＥＧを使用して、前景レイヤおよび背景レイヤを符号化し、したがって、圧縮のために、ストライプを個々のレイヤにどのように分解するべきかを決定する際に、ＪＰＥＧコーダの詳細を考慮しなければならない。
【００１３】
ＭＲＣの構文により、各ストライプにつき１組のパラメータを送信することが可能になる。
これらのパラメータは、符号化された前景レイヤおよび背景レイヤのサイズおよび位置を規定する空間オフセットおよびサイズを含む。
前景レイヤおよび背景レイヤは、ストライプよりも小さくなることがある。
一方、マスクレイヤは、常に、最大解像度および最大サイズである。
【００１４】
図３は、ストライプよりも小さな符号化された前景レイヤ３２０および背景レイヤ３３０を有するストライプ３１０を示している。
２つのパラメータは、前景ベース色および背景ベース色を表す。
これらの前景ベース色および背景ベース色は、それぞれ、オフセットパラメータおよびサイズパラメータによって指定された符号化領域の外部の部分３２２および３３２において前景レイヤおよび背景レイヤを満たすために使用される。
【００１５】
マスクが導出されると、前記レイヤおよび背景レイヤは共に、マスクによって決定された他方のレイヤに属するピクセルに対応した「ホール」または「ドントケアピクセル」を有する。
したがって、特定のピクセルが前景レイヤから供給されることを、マスクが示しているときはつねに、背景レイヤの同じ位置には、対応するホールが存在する。
このようなホールまたはドントケアピクセルは、復元には無関係であるが、それらの値に応じて圧縮には大きな影響を及ぼす可能性がある。
それらの値は、復元に無関係であることから、圧縮をより効率的に行うために変更することができる。
【００１６】
ブロック２３０は、ストライプを分析して、次の情報を決定しなければならない。
すなわち、１）符号化された前景レイヤおよび背景レイヤのオフセットおよびサイズ、２）前景ベース色および背景ベース色、３）最大解像度マスク、４）前景レイヤおよび背景レイヤのドントケアピクセルの補間値（すなわち、ＪＰＥＧに整合した補間）、５）前景レイヤおよび背景レイヤのＪＰＥＧパラメータ、ならびに６）マスクレイヤのＪＢＩＧパラメータを決定しなければならない。
【００１７】
図４は、ストライプ分析プロセスを含むＭＲＣコーダプロセスの一実施の形態を示している。
このＭＲＣコーダプロセスは、ストライプにされた複合文書のストライプに対して操作を行っている。
ステップ４１０は、さらに処理すべきストライプが存在するかどうかを判断する。
存在しない場合には、プロセスは、ステップ４９０において完了する。
そうでない場合には、ステップ４２０が、分析用のストライプを得る。
ストライプ分析部４３０は、概念的には、３つのコンポーネントに分割することができる。
ステップ４４０において、レイヤのオフセット、サイズ、およびベース色が決定される。
ステップ４５０は、コーダに整合したレイヤ分離を行う。
図示した実施の形態では、これは、ＪＰＥＧに整合したレイヤ分離である。
次いで、ステップ４６０は、無関係のドントケアピクセルを補間して、ＪＰＥＧ圧縮を円滑にする。
ステップ４７０において、画像（前景および背景）レイヤがＪＰＥＧで符号化され、マスクレイヤがＪＢＩＧで符号化される。
プロセスは、すべてのストライプが処理されるまで継続される。
【００１８】
ストライプ分析プロセスの最初のステップの目的は、ベース色ならびにレイヤのサイズおよびオフセットの適当な選択を通じて画像レイヤの符号化されたサイズを縮小することである。
複合文書が、例えば、一定の色のマージンを有する場合に、このような情報は、ＪＰＥＧ符号化とは対照的に、オフセットパラメータおよびベース色パラメータの使用を通じてより経済的に搬送することができる。
この最初のステップは、外周部検出機能および共通領域縮小機能にさらに分割することができる。
これらの機能は、ほぼ同時に実行することができる。
【００１９】
外周部検出機能は、画像レイヤの残りの符号化領域が最小化されるように、２つの色のみからなるストライプのエッジに沿って最も太いマージンを検出しようと試みる。
ストライプ行およびストライプ列の系統的な分析は、この機能に対して行われる。
【００２０】
図５は、外周部検出機能を示している。
集合｛上部，底部，左，右｝を与えると、ステップ５１０は、開始するエッジを選択する。
４つすべてが結局処理されることになる。
そこで、どのエッジを最初に選択してもよい。
例として、上部エッジが、最初に選択されたエッジであると仮定される。
【００２１】
ステップ５２０によって示すように、選択されたエッジから開始して、選択されたエッジの対向エッジに進むスキャンがストライプに対して行われる。
このスキャンは、３つ以上の異なる色に遭遇するまで続けられる。
最初の２つの異なる色は、ベース色ペアの候補となる。
例えば、上部エッジが最初に選択されると、上部エッジから開始して、底部エッジに向かって進む行スキャンが、第３の色に遭遇するまで行われる。
このスキャンは、第１の境界にマークを付ける。
【００２２】
反時計方向に進んで、別のエッジが、ステップ５２２において選択される。
上部エッジが最初に選択された場合に、次のエッジは、一実施の形態では左エッジである。
この新たなエッジから開始して、その対向エッジに向かって進むスキャンが、ステップ５３０において行われる。
左エッジが選択された場合に、スキャンは、候補のベース色ペアの構成要素でない色に遭遇するまで、列に沿って進む。
このスキャンは、第２の境界にマークを付ける。
【００２３】
反時計方向に進んで、第３のエッジが、ステップ５３２において選択される。
上部エッジが最初に選択された場合に、第３のエッジは、一実施の形態では底部エッジである。
この第３のエッジから開始して、その対向エッジに向かって進むスキャンが、候補のベース色ペアの構成要素でない色に遭遇するまで、ステップ５４０において行われる。
このスキャンは、第３の境界にマークを付ける。
【００２４】
反時計方向に進んで、第４のエッジが、スキャン５４２において選択される。
上部エッジが最初に選択された場合に、第４のエッジは、一実施の形態では右エッジである。
この第４のエッジから開始して、その対向エッジに向かって進むスキャンが、候補のベース色ペアの構成要素でない色に遭遇するまで、ステップ５５０において行われる。
このスキャンは、第４の境界にマークを付ける。
【００２５】
スキャンを通じて得られた境界に基づいて、前景レイヤのオフセットおよびサイズならびに背景レイヤのオフセットおよびサイズをステップ５５２において決定することができる。
候補のベース色ペアの２つの色の一方が、前景のベース色に割り当てられる一方、そのペアの他方の構成要素は、背景のベース色に割り当てられる。
【００２６】
これまでに得られた情報は、ベース色の１つの候補ペアおよび関連したオフセットのみを表す。
この解は最適でないことがある。
例えば、最初のスキャンエッジが異なると、候補のベース色ペアおよび関連したオフセットが異なることがあり、これによって、より小さな符号化領域が生成されることがある。
したがって、候補のベース色ペアおよび関連したオフセットが、それぞれの可能な開始エッジに対して決定されるまで、プロセスが繰り返されることをステップ５６０は保証する。
【００２７】
ストライプの各エッジが開始エッジとなった後、４つの候補のベース色ペアが関連したオフセットと共に存在することになる。
したがって、ステップ５６０によって判断されるように、可能なすべての開始エッジが処理された後、ステップ５７０は、符号化領域が最小となる、候補のベース色ペア（および関連したオフセット）を選択する。
【００２８】
この時点で、前景レイヤおよび背景レイヤは、同じサイズであり、結果として前景レイヤおよび背景レイヤの共通領域となる同じオフセットを有する。
共通領域縮小機能は、符号化された前景レイヤおよび背景レイヤのサイズをこの共通領域を越えて縮小するように試みる。
【００２９】
一般に、共通領域は、あるエッジからその対向エッジに向かって列方向にスキャンされる。
選択されたレイヤのベース色を有するピクセル部分は、列ごとに合計される。
この値は、通常、０．７５に設定される閾値ＴＦと比較される。
変数ＮＦは、文書の解像度の関数である。
一実施の形態では、ＮＦは、０．２５インチ幅に必要とされる列数に対応するように選択される。
選択されたレイヤのベース色を有するピクセル部分の一続きのＮＦ列がＴＦ未満であるとすぐに、スキャンは停止され、背景レイヤは、その一続きの開始点で開始するように調整される。
【００３０】
図６は、共通領域縮小機能の一実施の形態を示している。ステップ６１０において、閾値変数ＴＦおよびＮＦが初期化される。ＴＦは、ピクセル閾値であり、一実施の形態では０．７５に設定される。ＮＦは、連続した行または列の個数の閾値を表し、文書の解像度の関数である。一実施の形態では、ＮＦは、約０．２５インチに対応する値に初期化される。
【００３１】
ステップ６１２において、共通領域縮小用のレイヤが選択される。
一実施の形態では、共通領域縮小機能は背景レイヤから開始する。
ステップ６１４において、ストライプの開始エッジが選択される。
一実施の形態では、この開始エッジは、左エッジおよび右エッジの一方から選択される。
【００３２】
ステップ６２０において、列数変数ＮＣＯＬがゼロに設定される。
ステップ６３０は、１列をスキャンして、選択されたレイヤに関連したベース色を有するピクセル部分ＰＦを特定する。
ＰＦ<ＴＦ（例えば、ピクセルの７５％未満が背景のベース色に関連している）の場合には、ＮＣＯＬは、ステップ６４０においてインクリメントされ、そうでない場合には、ＮＣＯＬは、ステップ６３４において０に設定される。
ステップ６４２は、ＮＣＯＬ＝ＮＦであるかどうかを判断し、したがって、ＰＦ<ＴＦとなる少なくともＮＦ個の連続した列が存在するかどうかを判断する。
【００３３】
ＮＣＯＬ＝ＮＦでない場合には、ステップ６６０が、処理すべき列がさらに存在するかどうかをチェックする。
存在する場合には、ステップ６６２が次の列を選択し、プロセスは、この新たな列を使用してステップ６２０に続く。
【００３４】
ＮＣＯＬ＝ＮＦである場合には、ステップ６５０が、選択されたレイヤの符号化領域をＮＦ列だけ縮小する。
これにより、選択されたレイヤの符号化に必要な共通領域の量が効果的に減少する。
したがって、ステップ６５２において、共通領域の廃棄された部分のマスク値は、選択されたレイヤに関連した値に設定される。
背景が０であり、前景が１であるというマスク規約の場合に、背景レイヤから廃棄された領域では、マスク値は、背景色を有するすべてのピクセルに対して０（背景）に割り当てられ、それ以外は１に割り当てられる。
次いで、ステップ６６０は、処理すべき列がさらに存在するかどうかを判断する。
【００３５】
ステップ６６０が、処理すべき列が共通領域にもはや存在しないと判断すると、ステップ６７０が、処理すべき別の開始エッジが存在するかどうかを判断する。
存在しない場合には、プロセスは、ステップ６９０において完了する。
存在する場合には、次のエッジが、ステップ６７２において、処理のために選択され、プロセスは、この新たなエッジでステップ６２０から繰り返される。
【００３６】
図６の共通領域の縮小が、一方のレイヤ（例えば背景）に対して実行されると、このプロセスを他方のレイヤ（例えば前景）に対して繰り返すことができる。
しかしながら、前景レイヤおよび背景レイヤを共に、同じ側から縮小することはできない。
したがって、背景レイヤが、共通領域の左エッジから縮小されていると、前景は、左エッジから縮小することができない。
一方、右エッジからの縮小が、背景レイヤに対して先に行われていないならば、前景は右エッジから縮小することができる。
このように、１つのレイヤの一方または双方のエッジのスキャンを完全に省略することができる。
したがって、次のレイヤの同じエッジのそのような縮小の試みを省くには、選択されたレイヤの縮小が成功したエッジを特定することが必要である。
【００３７】
一実施の形態では、外周部検出機能および共通領域縮小機能は、ほぼ同時に実行される。
第１候補のベース色ペアの共通領域が、第２のベース色ペアの共通領域よりも大きい場合であっても、第１候補のベース色ペアは、共通領域縮小後の前景レイヤのサイズおよび背景レイヤのサイズの合計を小さくすることができる。
外周部検出機能および共通領域縮小機能を同時に実行することにより、候補色のペアを特定した直後に、レイヤのいずれかまたは双方をさらに縮小できるかどうかを調べることが可能になる。
４つの可能な候補ペアのうち、背景レイヤおよび前景レイヤの領域の合計が最小となるペアが選ばれる。
【００３８】
次に、マスク値が分析結果に基づいて割り当てられる。
一実施の形態では、ベース色ペアの明るい方（すなわち高輝度の方）の色が背景ベース色とみなされる一方、暗い方の色が前景ベース色とみなされる。
次いで、マスクには、そのピクセルの色が背景ベース色であるのか、それとも前景ベース色であるのかに応じて、それぞれ０または１が割り当てられる。
さらに、レイヤが、共通領域を越えて縮小された場合には、それに応じてマスク値が割り当てられる（ステップ６５２参照）。
例えば、前景レイヤが縮小されていると、廃棄された領域のマスクは、前景ベース色を有するピクセルに１が割り当てられる一方、それ以外のすべてのピクセルには０が割り当てられるように割り当てを受ける。
したがって、双方のレイヤを処理した後には、前景レイヤと背景レイヤとの交わり部分を構成するピクセル以外のすべてのピクセルのマスク値が求められていることになる。
その結果、縮小された共通領域の重なり合ったものによって表される部分を除き、ストライプのすべての領域の前景値、背景値、およびマスク値が求められている。
【００３９】
図７は、共通領域縮小前の共通領域７１２を有するストライプ７１０を示している。
このストライプは、縮小された共通領域７２２を有する前景レイヤ７２０と、縮小された共通領域７３２を有する背景レイヤ７３０とに分解される。
前景の縮小された共通領域は、縮小前の共通領域７１２と同じである。
一方、背景の縮小された共通領域７３２は、サイズが小さく、共通領域の縮小が背景レイヤに対して成功したことを示している。
この時点で、前景の縮小された共通領域と背景の縮小された共通領域との交わり部分を除くすべての領域に、マスク値が割り当てられている。
図示した例では、これら２つの領域の交わり部分は、実際には、背景の共通領域７３２となる。
【００４０】
一実施の形態では、縮小された共通領域の境界が、効率的なコーダのオペレーションの円滑化を確保するために調整される。
ＪＰＥＧコーダの場合、縮小された共通領域の境界は、縮小前の共通領域７１２の左エッジから８Ｎピクセルとなることを確保するために調整される。
ここで、Ｎは整数（すなわち、０、１、２…）である。
したがって、２つの領域の交わり部分は、符号化される領域の左エッジから、８Ｎピクセルの倍数となるように設計される。
この場合、背景の縮小された共通領域の左エッジは、前景の縮小された共通領域の左エッジから８Ｎピクセルの倍数となることを確保するために調整される。
【００４１】
図４を参照して、ストライプ分析ブロック４３０が、ベース色およびオフセットを特定した（ステップ４４０）後、コーダに整合したレイヤ分離が実行される（ステップ４５０）。
図８および図９は、コーダに整合したレイヤ分離プロセスを示している。
一実施の形態では、このコーダに整合したレイヤ分離は、交わり部分の領域を、交わり部分の領域自体よりも効率的に符号化を行う２つの分離したレイヤに分解するように試みる。
【００４２】
ＪＰＥＧで符号化されたブロックの内部のエッジは、高い符号化レートをもたらす。
しかしながら、エッジがブロック境界に移動されると、この符号化レートは小さくなる。
したがって、連続したブロックにおいてＤＣ値でジャンプすることによって生じる高い差分符号化（differentially coded）ＤＣ値は、ブロック内部のエッジによって生じる高いＡＣ係数よりも効率的に符号化される。
【００４３】
一般に、コーダに整合したレイヤ分離は、コーダがスキャンする順序で、交わり部分の領域のピクセルブロックを処理する。
したがって、ＪＰＥＧコーダの場合、ブロックは、行スキャンの順序で処理される。
各ブロック内では、３つの可能なレイヤの組み合わせが存在する。
各ブロックは、
１）前景レイヤにのみ属するピクセル、
２）背景レイヤにのみ属するピクセル、または
３）いくつかは前景レイヤに属し、それ以外は背景レイヤに属するピクセル
から構成することができる。
【００４４】
ブロックの変動が十分低い場合には、当該ブロックのピクセルが、前に符号化された前景ブロックのＤＣ値に近いのか、それとも、前に符号化された背景ブロックのＤＣ値に近いのかに応じて、当該ブロックは、前景レイヤまたは背景レイヤに全面的に割り当てられる。
コントラストの高いブロックの場合、そのピクセルは２つのグループに分離される。
一実施の形態では、明るいグループは、常に背景レイヤに割り当てられる一方、暗い色は、前景レイヤに割り当てられる。
マスク値は、それに応じて割り当てられる。
【００４５】
図８および図９は、交わり部分の領域または縮小された共通領域の重なり合った部分に適用される、コーダに整合したレイヤ分離プロセスを示している。
ステップ８０２は、補間された前景ブロックおよび背景ブロックのＤＣ値を初期化する（補間については、ブロック４６０に関連して説明する）。
変数ＰＲＥＶ＿ＡＶＧ＿ＦＧおよびＰＲＥＶ＿ＡＶＧ＿ＢＧは、それぞれ、補間され符号化された前の前景ブロックおよび背景ブロックの各色平面の平均値を表すベクトルである。
これらのベクトルは、ステップ８０２において、適当なレイヤベース色に初期化される。
【００４６】
ステップ８１０において、ピクセルブロックが、交わり部分の領域から選択される。
ステップ８１２において、値ＲＭＡＸが計算される。
ＲＧＢ色空間の画像の場合、ＲＭＡＸは、選択されたブロックに見られるＲ成分の範囲、Ｇ成分の範囲、およびＢ成分の範囲の最大値に対応するスカラー値である。
ステップ８１４によって判断されるように、ＲＭＡＸが、所定の閾値ＴＭＡＸよりも大きい場合には（すなわちＲＭＡＸ＞ＴＭＡＸ）、ステップ８２０〜８５２によって定められるように、いくつかのピクセルが前景に割り当てられ、それ以外のピクセルが背景に割り当てられる。
そうでない場合、すなわちＲＭＡＭ≦ＴＭＡＸの場合には、図９のステップ９１０〜９４２によって定められるように、ブロック全体が、そのブロックの平均輝度値に基づいて背景レイヤまたは前景レイヤのいずれかに割り当てられる。
【００４７】
ＲＭＡＸ＞ＴＭＡＸの場合には、ピクセルは２つのグループに分離される。
一実施の形態では、２平均アルゴリズム（2 means algorithm）を使用して、ピクセルが、２つのグループＧＲＯＵＰ＿１およびＧＲＯＵＰ＿２に分離される。
次いで、各グループの平均ＡＶＧ＿１およびＡＶＧ＿２が、ステップ８３０において計算される。
ＡＶＧ＿１およびＡＶＧ＿２はベクトルであり、これらのベクトルの要素は、それぞれＧＲＯＵＰ＿１およびＧＲＯＵＰ＿２の関連した色平面の平均ピクセル値を表す。
【００４８】
ステップ８３２において、ピクセルグループの平均輝度が比較される。
一実施の形態では、暗いグループは前景に割り当てられ、明るいグループは背景に割り当てられる。
【００４９】
したがって、ステップ８３２によって判断されるように、ＧＲＯＵＰ＿１の平均輝度が、ＧＲＯＵＰ＿２の平均輝度よりも大きい場合には、ステップ８４０において、ＧＲＯＵＰ＿１が背景に割り当てられ、ＧＲＯＵＰ＿２が前景に割り当てられる。
ベクトル変数ＰＲＥＶ＿ＡＶＧ＿ＢＧの成分には、ＧＲＯＵＰ＿１のピクセルの関連した色平面の平均値が割り当てられる（すなわち、ＰＲＥＶ＿ＡＶＧ＿ＢＧ＝ＡＶＧ＿１）。
同様に、ベクトル変数ＰＲＥＶ＿ＡＶＧ＿ＦＧの成分には、ＧＲＯＵＰ＿２のピクセルの関連した色平面の平均値が割り当てられる（すなわち、ＰＲＥＶ＿ＡＶＧ＿ＦＧ＝ＡＶＧ＿２）。
【００５０】
あるいは、ＧＲＯＵＰ＿１の平均輝度が、ＧＲＯＵＰ＿２の平均輝度よりも大きくない場合には、ステップ８５０において、ＧＲＯＵＰ＿１が前景に割り当てられ、ＧＲＯＵＰ＿２が背景に割り当てられる。
変数ＰＲＥＶ＿ＡＶＧ＿ＢＧおよびＰＲＥＶ＿ＡＶＧ＿ＦＧには、それぞれ、ＧＲＯＵＰ＿２およびＧＲＯＵＰ＿１のピクセルの平均値が割り当てられる（ＰＲＥＶ＿ＡＶＧ＿ＢＧ＝ＡＶＧ＿２およびＰＲＥＶ＿ＡＶＧ＿ＦＧ＝ＡＶＧ＿１）。
【００５１】
ピクセルが適当なレイヤに割り当てられた後、ステップ８６０は、処理すべきブロックが残っているかどうかを判断する。
残っている場合には、プロセスは、ステップ８１０において別のブロックで処理を続ける。
残っていない場合には、プロセスは、ステップ８９０において完了する。
【００５２】
ＲＭＡＸ≦ＴＭＡＸの場合に、ブロック平均Ｂ＿ＡＶＧが、図８のステップ８１４の後の図９のステップ９１０において計算される。
ベクトルＢ＿ＡＶＧの要素は、画像の各色平面の平均を表す。
平均ブロック輝度が、ステップ９２０において計算される。
平均ブロック輝度値が、前の背景の平均輝度に近いのか、それとも前の前景の平均輝度に近いのかに応じて、ブロック全体が、背景または前景に割り当てられる。
したがって、選択されたブロックの平均輝度が、前の背景の平均輝度に近い場合には、そのブロックは、ステップ９３０において背景に割り当てられ、ベクトルＰＲＥＶ＿ＡＶＧ＿ＢＧは、ステップ９３２においてＢ＿ＡＶＧに設定される。
【００５３】
一方、選択されたブロックの平均輝度が、前の前景の平均輝度に近い場合には、そのブロックは、ステップ９４０において前景に割り当てられ、ベクトルＰＲＥＶ＿ＡＶＧ＿ＦＧは、ステップ９４２においてＢ＿ＡＶＧに設定される。
【００５４】
ブロック全体が、前景レイヤまたは背景レイヤのいずれかに割り当てられると、ステップ８６０は、処理すべきブロックがさらに存在するかどうかを判断する。
存在する場合には、処理はステップ８１０で続けられる。
存在しない場合には、処理はステップ８９０において完了する。
【００５５】
図４を参照して、コーダに整合したレイヤ分離が、ステップ４５０において行われた後、それらのレイヤは、ステップ４６０において補間される。
レイヤ補間の目的は、ピクセルが他方のレイヤに割り当てられる場合に背景レイヤおよび前景レイヤに生成される「ホール」を、効率的に符号化する値で満たすことである。
画像レイヤごとに、８×８ブロックが、行−列の順序でスキャンされ、ホールを満たすために補間される。
【００５６】
これらのホールの値は、画像の復元には無関係である（ホールはマスクされる）が、その対応するピクセルに割り当てられた値は、ブロック圧縮レートに大きな影響を及ぼすことがある。
したがって、これらの「ホール」ピクセルまたは「ドントケア」ピクセルの値は、より大きな圧縮効率を達成するために変更される。
この手法は、再生品質に影響せず、復号アルゴリズムの変更を必要としない。
ドントケアピクセルは、別名、「無関係」ピクセルまたは「変更可能」ピクセルと呼ばれる。
残りのピクセルは、「関係（relevant）」ピクセルまたは「変更不能」ピクセルと呼ばれる。
【００５７】
上述したように、ストライプの各ブロックは、
１）前景レイヤにのみ属するピクセル、
２）背景レイヤにのみ属するピクセル、または
３）いくつかは前景レイヤに属し、それ以外は背景レイヤに属するピクセル
から構成することができる。
選択された画像レイヤの場合、このことは、その選択された画像レイヤのブロックが、
１）関係ピクセルのみ、
２）無関係ピクセルのみ、または
３）関係ピクセルおよび無関係ピクセルの組み合わせ
から構成できることを意味する。
【００５８】
図１０は、ストライプの選択された画像レイヤのブロックが、補間のためにどのように選択されるかを示している。
ステップ１００２において、集合｛前景，背景｝から、画像レイヤが選択される。
変数ＰＲＥＶ＿ＡＶＧが、ステップ１００４において、その対応する選択されたレイヤに応じて、背景ベース色または前景ベース色のいずれかに初期化される。
選択されたレイヤのピクセルブロックが、ステップ１０１０において選択される。
これらのピクセルは、ステップ１０２０において、関係または無関係として分類される。
マスクレイヤは、本来、所与の画像レイヤについて、ピクセルを関係または無関係に分類する。
【００５９】
ステップ１０３０によって判断されるように、選択されたブロックが、関係ピクセルおよび無関係ピクセルの混合したものを含む場合には、ステップ１０５０によって示されるように、そのブロックは補間される。
ステップ１０４０によって判断されるように、選択されたブロック全体が、無関係ピクセルから構成される場合には、ピクセル値は、ステップ１０６０において所定の値に設定される。
一実施の形態では、この所定の値は、関連した処理中のレイヤに応じて前景色または背景色に初期値として設定されるＰＲＥＶ＿ＡＶＧである。
一方、ブロック全体が、関係ピクセルから構成される場合には、補間は行われない。
【００６０】
ステップ１０５０または１０４０の後、ステップ１０６２において、ＰＲＥＶ＿ＡＶＧが、選択されたブロックの関係ピクセルの平均値により更新される。
選択されたブロック全体が、最初に、無関係ピクセルから構成されていた場合には、更新は必要ない。
ＰＲＥＶ＿ＡＶＧが必要に応じて更新された後、ステップ１０７０は、選択されたレイヤが、処理すべきブロックをさらに有するかどうかを判断する。
処理すべきブロックをさらに有する場合には、プロセスは、ステップ１０１０に戻り、新たなブロックで自身を繰り返す。
【００６１】
一実施の形態では、ステップ１０５０の補間は、無関係ピクセルに、選択されたブロックの関係ピクセルの平均値を割り当てる。
この補間手順は、以下に説明する補間手順よりもかなり高速になる傾向があるが、同じ圧縮レートを達成することができない。
【００６２】
代替的な実施の形態では、ステップ１０５０の補間プロセスは、簡単で高速な平均化のプロセスよりもかなり複雑になるが、高い頻度で大きな圧縮レートになる。
この代替的な補間プロセスを理解するには、コーダのプロセスを多少理解する必要がある。
【００６３】
ブロック圧縮アルゴリズムが、画像処理の用途に普及している。
デジタル表現のソース画像データを圧縮する１つの技法は、空間領域の画像データを周波数領域のデータに変換するステップを含む。
空間領域から周波数領域への変換は、フォワード変換とも呼ばれる。
【００６４】
フォワード変換は、ソース画像の調和分析に類似している。
フォワード変換を使用すると、空間画像データは、基底関数の線形結合として表される。
これらの基底関数の係数は、変換プロセス中に求められる。
【００６５】
次いで、これらの基底係数は、量子化または閾値処理を受けて、対応する基底関数からの寄与が除去され、あるレベルの圧縮が達成される。
次いで、残りの係数は、並べ替えられるかまたは連長符号化され、そうでない場合には、画像データのさらなる圧縮を容易にするように処理される。
次いで、その結果生成された圧縮画像データは、記憶、分配、またはさらなる処理のために利用可能とされる。
【００６６】
通常、ゼロの値の量子化係数の個数が多くなるほど、圧縮レートは大きくなる。
したがって、無関係ピクセルの値を変更して、非ゼロの量子化係数の個数を減少させることができる。
変更可能ピクセルは、変更されたブロックを量子化フォワード変換したものが、選択されたブロックを量子化フォワード変換したものよりも多くの個数のゼロの値を有するように変更される。
「レート」が圧縮画像の記憶必要量を指す場合に、このオペレーションは、圧縮画像の「レート」を縮小する。
したがって、このオペレーションは、画像エンコーダの圧縮効率またはレート効率を増大させる。
【００６７】
ピクセルを変更する方法は、圧縮アルゴリズムの仕様に依存する。
ジョイントフォトグラフィックエキスパートグループおよびモーションピクチャエキスパートグループ（ＭＰＥＧ）は、それぞれ、スペクトルの内容を操作してデータ圧縮を行う、よく知られている奨励された画像圧縮／符号化アーキテクチャを有する。
ＪＰＥＧ圧縮は、ファクシミリの用途や標準的な印刷の用途で生じる画像など、静的な画像に高い頻度で使用される。
ＭＰＥＧフォーマットは、動的な画像または映画に使用される。
基本的なプロセスは、ＪＰＥＧによって公表されており、今日、広範囲で使用されている。
ＪＰＥＧは、離散コサイン変換（ＤＣＴ）を利用するが、フォーマット変換、量子化、およびエントロピー符号化ブロックの具体的な実施は、実施者に任せられている。
【００６８】
図１１は、画像を圧縮するブロックベースのプロセスの一実施の形態をより詳細に示している。
画像エンコーダ１１２０は、離散化されたソース画像１１１０を処理して、圧縮画像データ１１９０を生成する。
【００６９】
エンコーダ１１２０は、複数の８×８ソースブロックとしてソース画像１１１０を処理する。
フォワード変換は、各８×８ソースブロックに対して実行される。
各８×８ソースブロックは、ｘおよびｙの２次元空間関数である６４点離散信号である。
ＤＣＴは、信号を基底関数の線形結合として表すのに使用できる多くの変換の１つである。
ＤＣＴが、ＪＰＥＧ圧縮用に選択された変換であるが、フーリエ変換や離散サイン変換（ＤＳＴ）などの他の線形フォワード変換を使用することもできる。
【００７０】
フォワードＤＣＴは、６４点離散信号を６４個の直交基底信号に変換する調和分析器である。
各直交基底信号は、８×８ソースブロックのスペクトルを形成する２次元空間周波数を表す。
フォワードＤＣＴの出力は、これらの直交基底信号のそれぞれの振幅を特定する係数ブロックである。
これらの振幅は、ＤＣＴ係数と呼ばれ、その値は、離散的な６４点入力信号によって求められる。
【００７１】
図１１を再び参照して、量子化器１１４０は、量子化テーブル１１４２に従ってＤＣＴ係数を量子化する。
量子化テーブル１１４２によって特定されるように、さまざまな量子をさまざまな空間周波数と共に使用することができる。
量子化されたｃ（ｕ，ｖ）は、次のように計算することができる。
【００７２】
【数１】
2005516553.tif 000003
【００７３】
上記式において、「ＩＮＴ」は、結果が整数であることを確保するための整数関数である。
【００７４】
量子化テーブルは、異なる基底関数に対して異なるステップサイズを許容している。
したがって、量子化テーブルは、６４要素テーブルであり、各空間周波数に対して１つの要素が対応する。
一般に、周波数の高い基底関数のステップサイズは、周波数の低い基底関数のステップサイズよりも大きい。
ステップサイズは、通常、対応するコサイン基底関数の視覚的寄与の知覚閾値で選ばれる。
知覚閾値は、ソース画像の特性、表示特性、観察距離などの関数である。
したがって、量子化テーブルの選択は、用途に依存し得る。
【００７５】
量子化の後、エントロピー符号化が使用されて、量子化係数が効率的に表現される。
エントロピーエンコーダ１１５０は、エントロピー符号化テーブル１１５２を使用して、圧縮画像データ１１９０を生成する。
【００７６】
簡潔に言えば、前のゼロの個数と、現時点の量子化係数の値を表すのに必要なビットとが、ペアを形成する。
各ペアには、可変長符号を通じてそれ自身の符号語が割り当てられる。
ハフマン符号化、シャノン−ファノ符号化、および算術符号化が、一般に使用される可変長コーダの例である。
所与の要素が多く生起するほど、その対応するコードに使用されるビット数は少なくなる。
ＪＰＥＧエンコーダは、ペアの符号語を出力し、次いで、現時点の量子化係数の（可変長コーダによっても割り当てられた）符号語を出力する。
【００７７】
量子化ＤＣＴ係数のブロックを処理した後、ＪＰＥＧエンコーダは、ブロック列の一意のエンドを書き込み、次いで、次のブロックに移る。
すべてのブロックが終了した後、ＪＰＥＧエンコーダは、エンドオブファイルマーカを書き込む。
テーブル１１５２および１１４２は、復元を容易にするために、圧縮画像データ内に組み込むことができる。
【００７８】
量子化の結果は、ＤＣＴ係数の多くがゼロに縮小されたものとなる。
特に、周波数の高いコサイン基底関数に対応する係数ほど、ゼロになりやすい。
量子化ＤＣＴ係数を配列して、ゼロ値要素のより長い列を得ることにより、エントロピーエンコーダのレート効率が改善され、特に、残っている符号化対象のあらゆる量子化ＤＣＴ係数がすべてゼロである点において、レート効率が改善される。
したがって、エントロピーエンコーダは、図１２に示すように、周波数の低い基底関数に関連した量子化係数から周波数の高い基底関数に関連した量子化係数に進むジグザグ形式で、量子化ＤＣＴ係数ブロックを符号化する。
【００７９】
ブロック１２１０の左上のコーナは、ＤＣ項（ｕ，ｖ＝０）に対応する。
このＤＣ項は、個々の符号化ブロック全体にわたって差分符号化（differentially encoded）される。
残りのＡＣ項は、右下のコーナに向かって進むほど周波数が高くなるコサイン基底関数を表す。
ＪＰＥＧエントロピーエンコーダは、ブロックエンドを書き込む前に、最高周波数の非ゼロの量子化係数までを符号化することが必要とされるだけである。
他のあらゆる係数は、ゼロと仮定される。
【００８０】
このジグザグスキャンの順序は、符号化対象の要素の列の一方の端に複数の非ゼロの要素をグループ化する傾向がある。
周波数の高い基底係数がゼロである場合に、このジグザグスキャンの順序は、符号化される量子化係数の列の端にゼロの要素をグループ化する。
したがって、エントロピーエンコーダのレート効率が改善される。
ＪＰＥＧエンコーダは、このスキャンの順序で最後の非ゼロの量子化係数を越えて符号化を行う必要はない。
高位の周波数ほどゼロになる確率が高いことから、このジグザグスキャンの順序は、このように、ＪＰＥＧエンコーダの圧縮効率を増加させる。
【００８１】
基本スペクトル操作符号化プロセスを変更して、ソース画像の復元に無関係であるが、レート効率に大きな影響を及ぼし得るピクセル値の変更を許容することができる。
【００８２】
ブロックの６４個のピクセルを、ベクトルｚと表記する。
このベクトルは、
ｚＴ＝｛ｙＴ，ｘＴ｝
となるような、より小さな２つのベクトルｙおよびｘから構成される。
ここで、ｙは、Ｎｙ個の関係ピクセルの集合であり、ｘは、６４−Ｎｙ個の無関係ピクセルの集合である。
このベクトルの６４×６４の２ＤのＤＣＴ変換行列は、係数の集合ｃがｃ＝Ｔｚによって与えられるようなＴで表記される。
【００８３】
１つの手法として、既知のベクトルｙに影響を及ぼさずに、ＡＣ係数のエネルギーを最小にするベクトルｚのベクトルｘについて解くものを挙げることができる。
次いで、最小にするコスト関数が、以下の式によって与えられる。
【００８４】
【数２】
2005516553.tif 000004
【００８５】
２ＤのＤＣＴのＤＣ係数は、以下の式によって与えられる。
【００８６】
【数３】
2005516553.tif 000005
【００８７】
Ｊ（ｘ）が、ｘの各要素ｘｉに関して部分的に導出され、ゼロと同等をみなされると、各要素は、以下の式によって与えられる同じ最適値を生成するように求められる。
【００８８】
【数４】
2005516553.tif 000006
【００８９】
したがって、ＡＣ係数のエネルギーを最小にする観点からの変更可能ピクセルの最適な補間は、すべての変更可能ピクセルの値を変更不能ピクセルの平均に設定する解となる。
この手法は、良い開始点とはなり得るが、差分ＤＣ符号化の影響およびブロック圧縮アルゴリズムエントロピーエンコーダの詳細を無視する。
【００９０】
目的は、他の制約条件を満たしつつ、逆のジグザグスキャンパスに沿ったゼロの連続を最大にすることにより、レートを最小にするｚを求めることである。
例えば、いずれの変更可能なｚｉにも、実現可能な範囲内のピクセル値を割り当てなければならず、変更不能ピクセルのｚｉは、以下の式で与えられるように、変更されるべきではない。
ｚｉ＝ｙｉ    ｉ＝｛０，１，…，Ｎｙ−１｝
０≦ｚｉ≦２５５    ｉ＝｛Ｎｙ，…，６３｝
【００９１】
変更されたブロックのＤＣＴ係数について考察する。いくつかの係数は、ゼロに量子化される一方、それ以外の係数は、非ゼロの値に量子化される。ゼロに量子化できる係数の位置（すなわちインデックス）は、以下のような集合Ｉｚｅｒｏを形成する。
【００９２】
【数５】
2005516553.tif 000007
【００９３】
係数は、逆のジグザグスキャンの順序でスキャンされ、ゼロに量子化されない最初の係数ｃｊが求められる。
他の制約条件に違反することなく、その係数をゼロに「プッシュする（push）」ことが可能な場合には、上記制約条件
ｚｉ＝ｙｉ    ｉ＝｛０，１，…，Ｎｙ−１｝
０≦ｚｉ≦２５５    ｉ＝｛Ｎｙ，…，６３｝
に加えて、Ｉｚｅｒｏ集合から得られる以下の制約を満たす解ｚが存在する。
【００９４】
【数６】
2005516553.tif 000008
【００９５】
（すなわち、以下の制約条件をも満たす場合に、ゼロに量子化されるどの係数も、非ゼロに量子化することはできない。）
【００９６】
【数７】
2005516553.tif 000009
【００９７】
項ｔｉは、ＤＣＴ行列Ｔの第ｉ行を表す。それぞれのゼロ量子化の制約条件は、１次不等式の制約条件である。
実現可能な解の存在は、シンプレックス法などの技法を使用して容易に解くことができるフェーズ１線形計画問題である。
係数値の変更は、このような変更を制限する等式制約条件の結果として、関係ピクセルの値に影響を与えるものではない。
選択されたブロックの関係ピクセルは、変更された係数ブロックを逆変換したものの対応するピクセルと同じ値を有することになる。
変更された係数ブロックを逆変換したものは、選択されたブロックを変更したものである。
【００９８】
解が存在すると、新たなゼロの量子化係数のインデックスが、Ｉｚｅｒｏ集合に加えられ、ｚは、実現可能な解に更新される。
ｃｊがゼロに量子化できない場合には、この方法は、逆のジグザグの順序で進んだ次の非ゼロの係数に進む。
このプロセスは、すべての非ゼロの量子化係数が検査されるまで繰り返すことができる。
【００９９】
その結果生成された解は、すべての制約条件を満たすものではあるが、この解は、係数のエネルギーを最小にするという意味で最適でないことがある。
ゼロの連続の長さまたは個数を最大にすることに加えて、非ゼロの量子化係数のエネルギーを最小にして、最も低いレートに到達すべきである。
各段階における最小エネルギーの解は、以下のものを最小にする。
【０１００】
【数８】
2005516553.tif 000010
【０１０１】
これは、上記に規定した以下の制約条件に従う。
【０１０２】
【数９】
2005516553.tif 000011
【０１０３】
ＤＣ値は、関係ピクセル値の平均に対する差分とみなされる。
上記問題は、一連の１次等式および１次不等式の制約条件に従う２次コスト関数となる。
解を求めるために、２次計画法を適用することができる。
この２次解法は、一連のフェーズ１線形計画法の後にのみ起動する必要がある。
【０１０４】
一連の線形計画法は、ゼロの量子化係数の個数を増加させるが、残りのＤＣＴ係数のエネルギーが、補間された最適な平均ブロックのものより高くなることがある解を生成する。
エネルギーがあまり増加しすぎると、ゼロの連続が最大になった場合であっても、レートは増加することがある。
【０１０５】
この結果を回避するために、２次計画法は、実現可能な解が求められた後の各段階で起動することができる。
この場合、２次計画法は、補間された平均ブロックの係数エネルギーに対する変更された最も新しいブロックの係数エネルギーの比に基づいた停止判断基準を使用する。
選択されたブロックを変更したもののエネルギーＥが、補間された平均ブロックのエネルギーＥ０の所定の比ＴＥ（ＴＥ>１）を越える場合には、最適化は終了して、レートが高くなることが回避される。
【０１０６】
図１３は、関係ピクセルおよび無関係ピクセルの混合したものを有するブロックの事前圧縮最適化プロセスを示している。
ステップ１３１０において、無関係ピクセルが初期化される。
一実施の形態では、無関係ピクセルは、選択されたブロックの関係ピクセルの平均ピクセル値に対応する値に設定される。
ステップ１３１２において、選択されたブロックのエネルギー（初期化後）が、Ｅ０として計算される。
【０１０７】
ステップ１３２０において、選択されたブロックに対してフォワード変換を適用することにより、係数ブロックが生成される。
ステップ１３３０において、すべてのゼロの量子化係数の位置が、配列Ｉｚｅｒｏに記憶される。
【０１０８】
逆のジグザグの順序で進んで、選択された非ゼロの量子化係数の位置が、ステップ１３４０において特定される。
ステップ１３５０において、選択された係数の値が、現時点のｚ用に計算される。
【０１０９】
ステップ１３５２は、選択された係数がゼロに量子化されるかどうかを判断する。
ゼロに量子化される場合には、ステップ１３７０において、その係数の位置が、他のゼロの量子化係数からなるＩｚｅｒｏ集合に追加される。
【０１１０】
選択された係数がゼロに量子化されない場合には、ステップ１３５４は、上記で特定した制約条件に従って、量子化係数がゼロとなる実現可能な解が存在するかどうかを判断する。
一実施の形態では、フェーズ１線形計画法が使用されて、このような実現可能な解が求められる。
一実施の形態では、シンプレックス法が使用されて、実現可能な解が求められる。
実現可能な解が存在しない場合には、処理はステップ１３８０に続く。
【０１１１】
実現可能な解が存在する場合に、ステップ１３６０において、２次計画法が使用されて、ｚの極小エネルギー解が求められる。
この新たなｚは、ステップ１３６２において計算される関連したエネルギーＥを有する。
【０１１２】
ステップ１３６４は、Ｅ／Ｅ０>ＴＥであるかどうかを判断する。
ここで、ＴＥは、Ｅ０に対するＥの比の許容可能な閾値である。
Ｅ／Ｅ０≦ＴＥである場合には、ステップ１３７０において、その係数の位置が、他のゼロの量子化係数からなるＩｚｅｒｏ集合に追加され、処理はステップ１３８０に続く。
【０１１３】
ステップ１３５４またはステップ１３７０のいずれかから進んで、ステップ１３８０において、処理すべき係数がさらに存在するかどうかのチェックが行われる。
存在しない場合には、係数ブロックの変更プロセスは、ステップ１３９０において完了する。
存在する場合には、プロセスは、ステップ１３４０に戻ることによって、次の非ゼロの量子化係数で継続される。
【０１１４】
この最適化プロセスは、すべての非ゼロの量子化係数が処理されるまで、または、結果のエネルギーが所定の閾値を越えるまで、ステップ１３４０〜１３８０を繰り返す。
【０１１５】
一実施の形態では、このプロセスは、処理すべき係数がさらに残っているかどうかにかかわらず、最初に実現可能な解を求めることができない時に停止する。
この手法は、ゼロについて最後に連続したものの長さを最大にする。
最後に連続したものは、エントロピーエンコーダのオペレーションの原理により、ＪＰＥＧエンコーダの符号化レートに最も大きな影響を及ぼす。
【０１１６】
スペクトル内容操作の方法は、１）ゼロの量子化係数の個数を増加させる傾向を有し、２）周波数の高い基底関数に関連した連続するゼロの量子化係数の個数を増加させることを優先する傾向を有する。
このエントロピーエンコーダの特異性を考えると、これにより、ＪＰＥＧエンコーダは、ブロックエンドを発行する前に、より少ないデータを使用して関係画像を表現することができる。
【０１１７】
図４を再び参照して、レイヤの補間が実行されると、背景レイヤ、前景レイヤ、およびマスクレイヤの符号化が、ステップ４７０において実行される。
一実施の形態では、前景レイヤおよび背景レイヤは、ＪＰＥＧで符号化され（図１１参照）、マスクレイヤは、ＪＢＩＧで符号化される。
【０１１８】
上記詳細な説明では、本発明を、その特定の例示的な実施の形態に関して説明している。
特許請求の範囲で主張される本発明のより広い精神および範囲から逸脱することなく、さまざまな変更および変形をそれらの実施の形態に対して行うことができる。
したがって、明細書および図面は、限定する意味ではなく、例示の意味で考慮されるべきである。
【図面の簡単な説明】
【０１１９】
【図１】複合文書のマルチレイヤ表現を示す図である。
【図２】複合文書のストライプ分解を示す図である。
【図３】ストライプの符号化された前景レイヤおよび背景レイヤを示す図である。
【図４】ストライプ分析プロセスを含むＭＲＣコーダプロセスの一実施の形態を示す図である。
【図５】外周部検出機能を示す図である。
【図６】共通領域縮小機能の一実施の形態を示す図である。
【図７】共通領域縮小後に前景レイヤと背景レイヤとに分解された共通領域を有するストライプを示す図である。
【図８】コーダに整合したレイヤ分離プロセスを示す図である。
【図９】コーダに整合したレイヤ分離プロセスを示す図である。
【図１０】ピクセルの補間または変更を行うためのブロックの選択を示す図である。
【図１１】ブロック指向型圧縮プロセスの一実施の形態を示す図である。
【図１２】エントロピー符号化係数のジグザグ処理順序を示す図である。
【図１３】複数の制約条件に従って、選択されたピクセルブロックのスペクトル内容を変更する方法を示す図である。
【符号の説明】
【０１２０】
１２０・・・前景、
１３０・・・背景、
１４０・・・マスク、
２３０・・・ストライプ分析／分解、
２３２・・・ストライプパラメータ、
２３４・・・マスク（ＪＢＩＧ）、
２３６・・・背景（ＪＰＥＧ）、
２３８・・・前景（ＪＰＥＧ）、
２４２・・・ストライプデータ、
３３０・・・符号化された背景レイヤ、
３３２・・・背景ベース色、
３２０・・・符号化された前景レイヤ、
３２２・・・前景ベース色、
７１０・・・共通領域を有するストライプ、
７２０・・・前景レイヤ、
７３０・・・背景レイヤ、
１１１０・・・ソース画像、
１１３０・・・フォワード離散コサイン変換（ＦＤＣＴ）、
１１４０・・・量子化器、
１１４２，１１５２・・・テーブル、
１１５０・・・エントロピーエンコーダ、
１１９０・・・圧縮画像データ、
【図１】
2005516553.tif 000012
【図２】
2005516553.tif 000013
【図３】
2005516553.tif 000014
【図４】
2005516553.tif 000015
【図５】
2005516553.tif 000016
【図６】
2005516553.tif 000017
【図７】
2005516553.tif 000018
【図８】
2005516553.tif 000019
【図９】
2005516553.tif 000020
【図１０】
2005516553.tif 000021
【図１１】
2005516553.tif 000022
【図１２】
2005516553.tif 000023
【図１３】
2005516553.tif 000024
【国際調査報告】
2005516553.tif 000025
2005516553.tif 000026
2005516553.tif 000027