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