(57)【要約】【課題】  画像とテキストを含む複合画像を圧縮する方法を改良する。【解決手段】  セグメンテーション・充填技術において多重解像度を用いる。本発明の実施形態では、前記方法は、複数の解像度からの画像データを使って複数のレイヤーを生成し、前記画像を得るために前記複数のレイヤーを合成する仕方を記述するマスクを生成し、前記複数のレイヤーのそれぞれにおいて、該複数のレイヤーを合成する際に画像に寄与しないピクセルを充填することを含む。【選択図】      図２
2006074770.tif 000002
【特許請求の範囲】
【請求項１】
複数の解像度からの画像データを使って複数のレイヤーを生成し、
画像を得るための前記複数のレイヤーの合成を記述するマスクを生成し、
前記複数のレイヤーのそれぞれにおいて、該複数のレイヤーを合成する際に画像に寄与しないピクセルを充填することを有することを特徴とする方法。
【請求項２】
前記レイヤー画像および前記マスクを圧縮することをさらに有することを特徴とする、請求項１記載の方法。
【請求項３】
前記複数のレイヤーが背景画像と前景画像からなることを特徴とする、請求項１記載の方法。
【請求項４】
前記レイヤー画像および前記マスクを圧縮することをさらに有する請求項１記載の方法であって、
前記背景画像および前景画像を連続階調圧縮手段を使って圧縮し、
前記マスクを二値データ圧縮手段を使って圧縮することを特徴とする、請求項３記載の方法。
【請求項５】
原画像の複数の低解像度版に関係する低解像度画像データから予備的前景画像と予備的背景画像を作成することをさらに有することを特徴とする、請求項１記載の方法。
【請求項６】
順変換を使って複数の変換レベルに対応する係数を生成し、
低域係数を前景または背景に割り振ることをさらに有することを特徴とする、請求項５記載の方法。
【請求項７】
低域係数の割り振りが：
前記複数の低解像度版の第一のものにおいて、複数の領域のそれぞれにおいて最も明るい低域係数と最も暗い低域係数とを比較し、
前記複数の領域のそれぞれについて、最も明るい低域係数と最も暗い低域係数との間の格差が第一の分解レベルについての閾値よりも大きければ、最も明るい低域係数を背景値または前景値の一方として割り振り、
前記複数の領域のそれぞれについて、最も明るい低域係数と最も暗い低域係数との間の前記格差が第一の分解レベルについての閾値よりも大きければ、最も暗い低域係数を背景値または前景値の他方として割り振ることを有することを特徴とする、請求項６記載の方法。
【請求項８】
システムによって実行されたときに、該システムをして：
複数の解像度からの画像データを使って複数のレイヤーを生成し、
画像を得るための前記複数のレイヤーの合成を記述するマスクを生成し、
前記複数のレイヤーのそれぞれにおいて、該複数のレイヤーを合成する際に画像に寄与しないピクセルを充填する、ことを有することを特徴とする方法を実行せしめるような命令を保存している一つ以上のデータ記録媒体を有する製造物。
【請求項９】
前記方法がさらに：
前記レイヤー画像および前記マスクを圧縮することを有することを特徴とする、請求項８記載の製造物。
【請求項１０】
前記複数のレイヤーが背景画像と前景画像からなることを特徴とする、請求項９記載の製造物。
【請求項１１】
前記レイヤー画像および前記マスクの圧縮が：
前記背景レイヤー画像および前景レイヤー画像を連続階調圧縮手段を使って圧縮し、
前記マスクを二値データ圧縮手段を使って圧縮することを特徴とする、請求項１０記載の製造物。
【請求項１２】
前記方法がさらに、原画像の複数の低解像度版に関係する低解像度画像データから予備的前景画像と予備的背景画像を作成することを有することを特徴とする、請求項８記載の製造物。
【請求項１３】
前記方法がさらに：
順変換を使って複数の変換レベルに対応する係数を生成し、
低域係数を前景または背景に割り振ることを有することを特徴とする、請求項１２記載の製造物。
【請求項１４】
低域係数の割り振りが：
前記複数の低解像度版の第一のものにおいて、複数の領域のそれぞれにおいて最も明るい低域係数と最も暗い低域係数とを比較し、
前記複数の領域のそれぞれについて、最も明るい低域係数と最も暗い低域係数との間の格差が第一の分解レベルについての閾値よりも大きければ、最も明るい低域係数を背景値または前景値の一方として割り振り、
前記複数の領域のそれぞれについて、最も明るい低域係数と最も暗い低域係数との間の前記格差が第一の分解レベルについての閾値よりも大きければ、最も暗い低域係数を背景値または前景値の他方として割り振ることを有することを特徴とする、請求項１３記載の製造物。
【請求項１５】
複数の解像度からの画像データを使って複数のレイヤーを生成する第一のユニットと、
画像を得るための前記複数のレイヤーの合成を記述するマスクを生成する第二のユニットと、
前記複数のレイヤーのそれぞれにおいて、該複数のレイヤーを合成する際に画像に寄与しないピクセルを充填する第三のユニットとを有することを特徴とする装置。
【請求項１６】
前記レイヤー画像および前記マスクを圧縮する圧縮手段をさらに有することを特徴とする、請求項１５記載の装置。
【請求項１７】
前記複数のレイヤーが背景画像と前景画像からなることを特徴とする、請求項１６記載の装置。
【請求項１８】
前記圧縮手段が：
前記背景画像および前景画像を圧縮する連続階調圧縮手段と、
前記マスクを圧縮する二値データ圧縮手段とを有することを特徴とする、請求項１７記載の装置。
【請求項１９】
前記第一のユニットが、原画像の複数の低解像度版に関係する低解像度画像データから予備的前景画像と予備的背景画像を生成することを特徴とする、請求項１５記載の装置。
【請求項２０】
前記第二のユニットが前記マスクを、部分的には原画像ならびに予備的背景および前景画像から予備的マスクを生成することによって生成することを特徴とする、請求項１９記載の装置。
【請求項２１】
前記第二のユニットが：
複数の変換レベルについて前景および背景に類別された値の低域係数を計算し、
前景と背景に対応する低域係数の逆変換値を、予備的マスク内の先に前景、背景、未決と類別されたピクセルの集合内のピクセルの数に基づいて計算することを特徴とする、請求項１５記載の装置。
【請求項２２】
前記第二のユニットが、最初の画像を、該最初の画像の複数の解像度からの画像データを使って作成された背景画像および前景画像と比較し、前記マスクが前景画像と背景画像を該マスクを使って合成すれば前記最初の画像になるようなものであることを特徴とする、請求項１５記載の装置。
【請求項２３】
前記第二のユニットが中間マスクを作成するような請求項２２記載の装置であって、該第二のユニットが：
当該画像中のピクセル値と前景画像および背景画像中の対応するピクセル位置の値との間の距離を計算し、
もし前景画像と背景画像にある値の間の差がある閾値よりも小さければ、当該中間マスク中の各ピクセル値を未決として類別し、
もし前景画像と背景画像にある値の間の差が前記閾値より大きければ、前記各ピクセル値を前景または背景として類別し、その際、前記各ピクセル値を、もし当該画像中の前記各ピクセルと前景画像との間の距離が当該画像中の前記各ピクセルと背景画像との距離よりも小さければ前景に設定し、もし当該画像中の前記各ピクセルと背景画像との間の距離が当該画像中の前記各ピクセルと前景画像との距離よりも小さければ背景に設定するものとし、
未決の値について、当該中間マスクにおける近隣のピクセル値の集合のうちのある数が前景または背景であるかどうかに基づいて、当該中間マスクにおける値をそれぞれ前景または背景に割り振り直し、
前景画像および背景画像における値を、もし当該中間マスクにおいてそれぞれ前景および背景に類別されていれば、当該画像の値に設定する、ことによって当該中間マスクを作成することを特徴とする装置。
【請求項２４】
複数の解像度からの画像データを使って複数のレイヤーを生成する手段と、
画像を得るための前記複数のレイヤーの合成を記述するマスクを生成する手段と、
前記複数のレイヤーのそれぞれにおいて、該複数のレイヤーを合成する際に画像に寄与しないピクセルを充填する手段とを有することを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理の分野に関するものである。より詳細には、本発明は画像のセグメンテーションおよびデータ充填に関するものである。
【背景技術】
【０００２】
ＪＰＭ（ＪＰＥＧ２０００パート６）は混合ラスタコンテンツ（ＭＲＣ：Ｍｉｘｅｄ  Ｒａｓｔｅｒ  Ｃｏｎｔｅｎｔ）のファイルフォーマットである。ＭＲＣは二値のテキストと連続階調画像の両方を含む複合画像を圧縮する方法である。ＭＲＣは、テキスト用や画像用に特別に開発されたものを含む複数の圧縮アルゴリズムの結果を表すために多重レイヤーによる画像構成を利用するものである。ＪＰＭでは、画像は、マスクに従って合成する複数のレイヤーに分解することによって圧縮される。分解後の画像およびマスクはＪＰＥＧ、ＪＰＥＧ２０００、ＪＢＩＧ、ＭＭＲのような適切な標準化された画像圧縮手段を用いて圧縮される。ＪＰＭとそのＭＲＣファイルフォーマットについての詳細は、“Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ―ＪＰＥＧ  ２０００  Ｉｍａｇｅ  Ｃｏｄｉｎｇ  Ｓｔａｎｄａｒｄ―Ｐａｒｔ  ６：Ｃｏｍｐｏｕｎｄ  Ｉｍａｇｅ  Ｆｉｌｅ  Ｆｏｒｍａｔ，”ＩＳＯ／ＩＥＣ  ＦＤＩＳ１５４４４−６、Ｂｏｌｉｅｋ＆Ｗｕ，“ＪＰＥＧ  ２０００−ｌｉｋｅ  Ａｃｃｅｓｓ  Ｕｓｉｎｇ  ｔｈｅ  ＪＰＭ  Ｃｏｍｐｏｕｎｄ  Ｄｏｃｕｍｅｎｔ  Ｆｉｌｅ  Ｆｏｒｍａｔ，”ＩＣＭＥ  ２００３  Ｐｒｏｃｅｅｄｉｎｇｓ，２００３  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ，  Ｖｏｌ．１，６−９  Ｊｕｌｙ  ２００３，ｄｅ  Ｑｕｅｉｒｏｚ，  Ｂｕｃｋｌｅｙ  ＆  Ｘｕ，“Ｍｉｘｅｄ  Ｒａｓｔｅｒ  Ｃｏｎｔｅｎｔ（ＭＲＣ）  Ｍｏｄｅｌ  ｆｏｒ  Ｃｏｍｐｏｕｎｄ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ，”Ｐｒｏｃ．ＩＳ＆Ｔ／ＳＰＩＥ  Ｓｙｍｐ．  ｏｎ  Ｅｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，Ｖｉｓｕａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，  Ｓａｎ  Ｊｏｓｅ，ＣＡ，ＳＰＩＥ  Ｖｏｌ．３６５３，ｐｐ．１１０６−１１１７，Ｆｅｂ．１９９９を参照。
【０００３】
ＪＰＭファイルは合成されるレイヤーをいくつでも持つことができる。ＪＰＭエンコーダはＪＰＭファイルフォーマットに従って保存されるデータを生成する。そのようなエンコーダは典型的には、背景や前景の画像に対応する連続階調画像を圧縮するための連続階調圧縮手段およびマスクを圧縮するための二値画像圧縮手段を有する。
【０００４】
従来技術においては、画像の二値化は光学式文字認識（ＯＣＲ）のための前処理操作として実行されている。たとえば、“Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｓｏｍｅ  Ｔｈｒｅｓｈｏｌｄｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｔｅｘｔ／Ｂａｃｋｇｒｏｕｎｄ  Ｓｅｇｍｅｎｔａｔｉｏｎ  ｉｎ  Ｄｉｆｆｉｃｕｌｔ  Ｄｏｃｕｍｅｎｔ  Ｉｍａｇｅｓ，”ＩＣＤＡＲ  ２００３：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄｏｃｕｍｅｎｔ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｒｅｃｏｇｎｉｔｉｏｎ，Ｖｏｌ．２，ｐｐ．８５９−８６３，２００３，Ｌｅｅｄｈａｍ  ｅｔ  ａｌ．を参照。
【０００５】
ＪＰＭエンコーダの二つの重要な機能は標準化されていない。それはセグメンテーションとデータ充填である。セグメンテーションというのは画像を前景レイヤーと背景レイヤーとに分解し、マスクを生成する方法である。一方、データ充填というのは、前景画像と背景画像の圧縮がスムーズにいくように前景画像および背景画像中の「どうでもいい」ピクセル（あるレイヤー中で、マスクを使って最終画像を合成する際に使用されないピクセル）に値を割り当てておくことである。
【０００６】
セグメンテーションとデータ充填に関しては従来技術においていくつかの技術が知られている。たとえば、従来技術のセグメンテーション法の多くはＫ平均クラスタリングを空間領域で画像処理のために使っている。この従来技術の方法の多くはブロックベースのものである。Ｋ平均クラスタリングは各色の生起回数を使うが色の空間的な関係は使わない。ページのセグメンテーションは形態的な変換に基づいて尺度空間において行われてきた。これについてはたとえば、Ｄ．Ｐ．Ｍｕｋｈｅｒｊｅｅ  ａｎｄ  Ｓ．Ｔ．Ａｃｔｏｎ，“Ｄｏｃｕｍｅｎｔ  ｐａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｕｓｉｎｇ  ｍｕｌｔｉｓｃａｌｅ  ｃｌｕｓｔｅｒｉｎｇ，”Ｐｒｏｃ．  ＩＥＥＥ  Ｉｎｔ．  Ｃｏｎｆ．  Ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，  Ｋｏｂｅ，  Ｊａｐａｎ，  Ｏｃｔ．２５−２９，１９９９を参照。
【０００７】
米国特許第６，６３３，６７０号は二つの異なるサイズのブロックに対する前景・背景セグメンテーションを開示しているが、クラスタリングのために反復処理によるＫ平均ではなく最大勾配からの値を使っている。
【０００８】
従来技術には、セグメンテーションのために複数のスケールを用いた方法がいくつか含まれるが、それはたとえばピクセルをグループ化するために複数のブロックサイズ使ったり確率を計算するのに複数のスケールにまたがるマルコフ鎖を使ったりといったような、多重解像度変換を伴うものではない。たとえば、Ｚｈａｏ  Ｊｉａｎ，  ｅｔ  ａｌ．，“Ａ  Ｎｅｗ  Ｗａｖｅｌｅｔ−Ｂａｓｅｄ  Ｄｏｃｕｍｅｎｔ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔａｔｉｏｎ  Ｓｃｈｅｍｅ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｓｙｓｔｅｍｓ  Ｅｎｇｉｎｅｅｒｉｎｇ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ，  ｖｏｌ．１３，ｎｏ．３，２００２，ｐｐ．８６−９０では、複数のブロックサイズが使われ、臨界サンプリングされた（すなわち冗長でない）ハール変換が単一の変換レベルで用いられている。
【０００９】
適応フィルタリング―エッジや中間階調の形状に基づくノイズ除去―はよく知られている。複合文書についてＭＲＣでない圧縮方法がある。たとえば、Ｇｕｏ  ｅｔ．  ａｌ，“Ｃｏｍｐｏｕｎｄ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｗａｖｅｌｅｔ  Ｔｒａｎｓｆｏｒｍ，”Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｉｍａｇｅ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ  ｏｆ  Ｊａｐａｎ，ｖｏｌ．３０，ｎｏ．２，ｐｐ．１３８−５０は、セグメンテーションに基づく適応ウェーブレット変換（二値データに対する５／３ウェーブレットおよびリフティングベースの変換）の使用を開示している。
【００１０】
ＤｊＶｕとはＡＴ＆Ｔとリザードテックの間の共同において開発された製品をいう。ＤｊＶｕでは前景・背景セグメンテーションはＫ平均クラスタリングの重み付き平均を可変サイズのブロックに対して用いて実行される。充填は圧縮（臨界サンプリングされ、ハールよりフィルタ長が長い）ウェーブレットシステムを用いて反復処理によって実行される。ＤｊＶｕについての詳細は、Ｂｏｔｔｏｕ  ｅｔ  ａｌ．，“Ｈｉｇｈ  Ｑｕａｌｉｔｙ  Ｄｏｃｕｍｅｎｔ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｗｉｔｈ  ＤｊＶｕ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｅｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，ｖｏｌ．７，ｎｏ．３，ｐｐ．４１０−４２５，ＳＰＩＥ，１９９８を参照。
【００１１】
これらの領域における従来技術の方法のいくつかは、中間階調ノイズのような微小スケールの細部を捕らえるように設計されている。ゼロックスはＭＲＣを用いた。たとえば、カラー版画の画像について、Ｋ平均セグメンテーションと適応領域ベース閾値処理との組み合わせに続いて人工効果の除去が行われる。詳細については、Ｍｉｓｉｃ，Ｂｕｃｋｌｅｙ＆Ｐａｒｋｅｒ，“Ｅｎｃｏｄｉｎｇ  ａｎｄ  Ｐｒｏｃｅｓｓｉｎｇ  ｏｆ  Ｃｏｌｏｒ  Ｅｎｇｒａｖｉｎｇｓ  （Ｕｓｉｎｇ  ＭＲＣ），”２００２  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，  Ｒｏｃｈｅｓｔｅｒ，Ｎｅｗ  Ｙｏｒｋ，Ｓｅｐｔ．２２−２５，２００２を参照。開示されている方法の一つは、初期マスクおよび最終マスクを用いての多段階法で、（中間階調ノイズのような）印刷工程での構造を除去するのではなく、保つことを目標としている。
【００１２】
従来技術文献の一つには、各ブロックについて背景と前景を分離するための閾値を選ぶという、ブロックベースのセグメンテーション法が開示されている。詳細については、ｄｅ  Ｑｕｅｉｒｏｚ，Ｆａｎ＆Ｔｒａｎ，“Ｏｐｔｉｍｉｚｉｎｇ  ｂｌｏｃｋ−ｔｈｒｅｓｈｏｌｄｉｎｇ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｆｏｒ  ＭＲＣ  ｃｏｍｐｒｅｓｓｉｏｎ，”Ｐｒｏｃ．  ＩＥＥＥ  Ｉｎｔｌ．  Ｃｏｎｆ．  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，ＩＣＩＰ，Ｖａｎｃｏｕｖｅｒ，Ｃａｎａｄａ，Ｖｏｌ．ＩＩ，ｐｐ．５９７−６００、Ｓｅｐｔ．２０００を参照。グレースケールとＮ×Ｎのブロックについては、閾値としては高々Ｎ２の可能な値しかない。ＪＰＥＧで使われているような８×８のブロックについては、高々６４通りの閾値の探索をすることで最良の閾値を見出すことができる。たとえば、米国特許第６，３７３，９８１号参照。さらに、米国特許第６，４００，８４４号は前景・背景セグメンテーションのためにブロックに対して単純な閾値を用いることを開示しており、あるブロックに対して前景・背景セグメンテーションを実行するかどうかを決定する他の類別方法を有している。
【００１３】
従来技術において用いられてきた充填方法にはいくつかある。たとえば、そのような充填技術の一つは、「どうでもいい」でないピクセルを四ピクセル近傍ごとに平均する処理を多段に実行し、「どうでもいい」ピクセルがすべて充填されるまで続けることを含んでいる。ｄｅ  Ｑｕｅｉｒｏｚ，“Ｏｎ  ｄａｔａ−ｆｉｌｌｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ＭＲＣ  ｌａｙｅｒｓ，”Ｐｒｏｃ．  ＩＥＥＥ  Ｉｎｔｌ．  Ｃｏｎｆ．  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，  ＩＣＩＰ，Ｖａｎｃｏｕｖｅｒ，Ｃａｎａｄａ，Ｖｏｌ．ＩＩ，ｐｐ．５８６−５８９，Ｓｅｐｔ．２０００を参照。別の従来技術の充填方法は低域フィルタを用い、「どうでもいい」でない位置についての係数を誇張することを含んでいる。さらに別の従来技術の充填方法は、ＤＣＴを使った反復処理による充填を含んでいる。関連する米国特許はいくつかある。たとえば、米国特許第６，３３４，００１号，第６，２７２，２５５号，第６，２７５，６２０号参照。
【００１４】
Ｍｕｋｈｅｒｊｅｅ  ｅｔ  ａｌ．，“ＪＰＥＧ２０００−Ｍａｔｃｈｅｄ  ＭＲＣ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  Ｃｏｍｐｏｕｎｄ  Ｄｏｃｕｍｅｎｔｓ，”２００２  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，  Ｒｏｃｈｅｓｔｅｒ，Ｎｅｗ  Ｙｏｒｋ，Ｓｅｐｔ．２２−２５，２００２ではあるセグメンテーションおよび充填方法が開示されている。そこで開示されている方法では、処理は縞に分けて実行され、セグメンテーションはブロックに対して行われ、一段で行われる。コントラストの高いブロックはＫ平均を用い、強度によって背景（より明るい）と前景（より暗い）とにセグメンテーションされる。コントラストが低いブロックは近隣のブロックに基づいて割り振られる。
【００１５】
ＬｕｒａＤｏｃｕｍｅｎｔはルーラテック（http://www.luratech.com/、Ａｌｇｏ  Ｖｉｓｉｏｎ  ＬｕｒａＴｅｃｈ  ＧｍｂＨ）からの、前景・背景セグメンテーションおよび充填を実行する、ＪＰＭ関連製品である。ＪＰＭと似ているが標準化されてはいない。それについての記述は、ＥＰＯ特許ＥＰ１１０４９１６Ａ１（ドイツ語）、Ｔｈｉｅｒｓｃｈｍａｎｎ  ｅｔ  ａｌ．，“Ａ  Ｓｃａｌａｂｌｅ  ＤＳＰ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｆｏｒ  Ｈｉｇｈ−Ｓｐｅｅｄ  Ｃｏｌｏｒ  Ｄｏｃｕｍｅｎｔ  Ｃｏｍｐｒｅｓｓｉｏｎ，”Ｄｏｃｕｍｅｎｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  ａｎｄ  Ｒｅｔｒｉｅｖａｌ  ＶＩＩＩ、およびＫａｎｔｏｒ  ｅｔ  ａｌ．，Ｅｄｉｔｏｒｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＳＰＩＥ  Ｖｏｌ．４３０７（２００１），Ｓａｎ  Ｊｏｓｅ，ＣＡ，Ｊａｎｕａｒｙ  ２００１。ＬｕｒａＤｏｃｕｍｅｎｔは二値化のための適応的な閾値を生成する。７５ｄｐｉの低減した解像度において、３×３最小フィルタおよび３×３最大フィルタが適用され、その差分が計算される。もし差分がある一定のパラメータよりも小さければ、閾値の初期値は「どうでもいい」となる。そうでなければ初期値は最小と最大との平均となる。「どうでもいい」でない初期閾値は３×３平均化フィルタを用いてフィルタ処理され、さらに５×５平均化フィルタを用いて伝搬される。「どうでもいい」の閾値には、「どうでもいい」でない値すべてを平均する７×７フィルタを使って割り当てが行われる。こうした閾値の値が双線形補間を用いて補間され、完全な解像度の画像となる。
【００１６】
ＬｕｒａＤｏｃｕｍｅｎｔは、文書解像度に基づく制限内の大きさの二値画像において連結した要素をみつけることによって、テキスト検出も行う。それぞれの連結要素は、その内部分散がある閾値未満であり、ソーベルフィルタおよびラプラスフィルタに基づいて強いエッジを有している場合にテキストとして類別される。テキストの連結要素はマスクにおいて前景として設定され、それ以外の位置が背景として設定される。
【００１７】
ＬｕｒａＤｏｃｕｍｅｎｔは、各方向において解像度が３分の１に低減された前景画像を生成する。マスクは１ピクセルぶん細くして境界でない前景ピクセルを選び出し、それ以外は「どうでもいい」ピクセルとする。各３×３ブロックについて、「どうでもいい」でないピクセルが平均され、９つのピクセルがみな「どうでもいい」の３×３ブロックは「どうでもいい」とラベル付けされる。５×５平均化フィルタを使って平均値を「どうでもいい」値の部分に伝搬させる。もう一つ５×５平均化フィルタを用いて非テキスト領域における前景色を灰色に近づくよう鈍らせる。背景についても同じようにして計算される。
【００１８】
充填およびセグメンテーション操作は小切手画像圧縮においても使われてきた。たとえば、（銀行業で使われる）完全な小切手システムがＨｕａｎｇ  ｅｔ  ａｌ．，“Ｃｈｅｃｋ  ｉｍａｇｅ  ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  ａ  ｌａｙｅｒｅｄ  ｃｏｄｉｎｇ  ｍｅｔｈｏｄ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｅｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，７（３），ｐｐ．４２６−４４２，Ｊｕｌｙ  １９９８で記述されている。そのシステムは、グレースケールでの形態の閉包化（ｃｌｏｓｉｎｇ）をセグメンテーションのための鍵となる操作として使う。システムは小さなブロックごとについて独立に構造化要素（ｓｔｒｕｃｔｕｒｉｎｇ  ｅｌｅｍｅｎｔ）のサイズ（尺度／解像度）を決定し、孤立ピクセルの除去を実行し、平均化を使って充填を実行する。
【００１９】
多重解像度セグメンテーションおよび充填方法ならびに装置が開示される。ある実施形態では、前記方法は、複数の解像度からの画像データを使って複数のレイヤーを生成し、前記画像を得るために前記複数のレイヤーを合成する仕方を記述するマスクを生成し、前記複数のレイヤーのそれぞれにおいて、該複数のレイヤーを合成する際に画像に寄与しないピクセルを充填することを含む。
【００２０】
本発明は下記の詳細な記述から、また本発明のさまざまな実施形態についての付属の図面からより十全に理解されることであろう。ただし、図面は本発明を特定の実施形態に限定するものと解釈してはならず、あくまでも説明と理解のためだけのものである。
【発明の開示】
【課題を解決するための手段】
【００２１】
多重解像度の前景・背景セグメンテーション技術および充填技術が開示される。ある実施形態では、これらの技術は画像処理工程（たとえばＪＰＭファイル生成など）の一部として組み合わされる。ある実施形態では、前景・背景セグメンテーションおよび充填技術は一つの入力画像を与えられ、前景画像、背景画像、二値のマスク画像を生成する。前記セグメンテーション技術は前記二値マスク画像の値を決定し、前記充填アルゴリズムは前記の二つの画像レイヤーのそれぞれにおいて充填される（「どうでもいい」）ピクセルの値を決定する。ある実施形態では、二値マスクが１のピクセル位置では前景画像は原画像と同じ値を持ち、背景画像は「どうでもいい」の値を持ち、この「どうでもいい」の部分は充填する必要がある。一方、二値マスクが０のところでは背景が原画像と同じで前景が充填を要する「どうでもいい」の値となる。前景画像、背景画像、マスク画像に量子化が行われなければ、原画像はマスクを使って前景画像と背景画像を合成することによって情報の損失なく復元することができる。
【００２２】
ここで記述されるセグメンテーションは多重解像度の仕方で実行される。ある実施形態では、多重解像度セグメンテーションはウェーブレット変換（たとえば冗長ハールウェーブレット変換）を画像データおよび係数に適用することによって実現される。
【発明の効果】
【００２３】
ここで記述されるセグメンテーション技術および充填技術と従来技術との間にはいくつもの相違がある。たとえば、線形フィルタリングと冗長ウェーブレット変換に基づく方法による類別（マスクの生成）ならびに異なる位相を組み合わせるための冗長ウェーブレットデータの流れおよび平均化法の使用は、従来技術には見られないものである。さらに、スキャンされた中間階調画像の前景・背景セグメンテーションを中間階調ノイズを無視して実行できる機能は先行技術の諸方法に比べての一つの利点である。
【発明を実施するための最良の形態】
【００２４】
以下の記述においては、数多くの詳細が述べられる。しかし、当業者には本発明はこれらの特定の詳細がなくても実施できることは明らかであろう。場合によっては、よく知られた構造や装置は詳細に示さずブロック図の形で示してあるが、これは本発明の焦点があいまいになることを避けるためにほかならない。
【００２５】
以下の詳細な記述のある部分は、データビットに対するコンピュータメモリ内での操作のアルゴリズムや記号的な表現によって提示されている。これらのアルゴリズム的な記述や表現は、データ処理技術における当業者が他の当業者に自らの作業の実質内容を最も効果的に伝えるために用いられている手段である。アルゴリズムとは、ここでは、そして一般にも、所望の結果を導くための自己無矛盾なステップの系列であると考えられている。それらのステップは物理量の物理的操作を必要とするものである。必須ではないが通例は、これらの量は保存、転送、組み合わせ、比較その他の処理の対象とすることができる電気信号または磁気信号の形をとる。しばしば主として慣用の理由から、こうした信号をビット、値、要素、シンボル、キャラクタ、項、数などと呼ぶことが便利であることが立証されている。
【００２６】
ただし、これらのあるいは同様の用語はすべて前記の適切な物理量と結びついたものであって、こうした量に適用される便利な呼称でしかないことは留意しておく必要がある。下記の記述から明らかな意味から離れる特別な断りのない限り、本記述全体にわたって、「処理」「計算」「算出」「決定」「表示」などといった用語を使っての議論は、コンピュータシステムのレジスタやメモリ内の（電子的な）物理量として表現されているデータを処理し、同様にコンピュータシステムメモリやレジスタやそのような他の情報記憶・送信・表示装置内の物理量として表現されるデータへと変換する、コンピュータシステムまたは同様の電子計算装置の作業や処理を言うものであるということを認識しておくものとする。
【００２７】
本発明はまた、ここで述べる作業を実行する装置にも関する。この装置は要求された目的のために特別に構築されたものでもよいし、汎用コンピュータを該コンピュータ中に保存されているコンピュータプログラムによって選択的に作動させたり再構成したりしたものを用いてもよい。そのようなコンピュータプログラムはコンピュータ読み取り可能な記憶媒体中に保存されていてもよく、その媒体としてはフロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含む各種のディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード、光カード、または電子的な命令を保存するのに適し、コンピュータのシステムバスにそれぞれ結合したいかなる媒体であってもよく、ここに挙げたものに限られない。
【００２８】
ここに提示されるアルゴリズムおよび表示は、いかなる特定のコンピュータその他の装置に本来的に関係しているものでもない。さまざまな汎用システムをここに述べる思想に従ったプログラムとともに用いることができるし、必要とされる方法ステップを実行するためにより特化した装置を構築することが好都合とわかる場合もありうる。そのようなさまざまなシステムに必要とされる構造については、下記の記述から明らかとなろう。さらに、本発明は、いかなる特定のプログラミング言語を基準に記述されているものでもない。さまざまなプログラミング言語がここで記述される本発明の思想を実装するのに用いうることは理解されるであろう。
【００２９】
機械読み取り可能な媒体としては、機械（たとえばコンピュータ）によって読み取り可能な形で情報を保存したり送信したりするためのあらゆる機構が含まれる。たとえば、機械読み取り可能な媒体は、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク保存媒体、光保存媒体、フラッシュメモリ素子、電気的・光学的・音響学的・その他の形で伝搬される信号（たとえば搬送波、赤外線信号、デジタル信号など）などを含む。
【００３０】
図１はエンコーダのブロック図である。図１を参照すると、原画像を一つの背景画像、一つの前景画像、一つのマスクに分解するセグメンテーション・充填手段を有するＪＰＭをベースとしたシステムの例が示されている。分解されたこれらの一つ一つが次いで圧縮される。背景画像と前景画像は連続階調圧縮手段（たとえばＪＰＥＧ２０００圧縮手段）を用いて圧縮され、一方、マスクは二値画像圧縮手段（たとえばＪＢＩＧまたはＪＢＩＧ２圧縮手段）を用いて圧縮される。現在技術の連続階調圧縮手段と二値画像圧縮手段とを組み合わせることによって、ＪＰＭは現行の連続階調圧縮方法または二値画像圧縮方法のどちらか一方よりもよい圧縮性能を提供することができる。
【００３１】
図２は、ここで記述される多重解像度のセグメンテーション技術および充填技術を実行するのに使うことができるセグメンテーション・充填手段の一つの実施形態のブロック図である。ある実施形態では、セグメンテーションと充填は冗長ハールウェーブレット変換を用いて実行することができる。ある実施形態では、当該方法は冗長ハールウェーブレット変換と同じメモリアクセスパターンを有する多重解像度変換を用いた三つの操作を利用する。
【００３２】
図２を参照すると、多重解像度前景・背景分解処理部２０１は、入力画像２１０に対して、多重解像度前景・背景分解に関連した操作を実行する（ここではステップＩと呼ぶ）。空間的予備的マスク処理部２０２は、空間的予備的マスクの生成に関連した操作を実行する（ここではステップＩＩと呼ぶ）。多重解像度前景・背景処理部２０３は多重解像度前景・背景生成に関連した操作を実行する（ここではステップＩＩＩと呼ぶ）。空間的最終マスク処理部２０４は空間的最終マスクの生成に関連した処理を実行する（ここではステップＩＶと呼ぶ）。そして多重解像度充填処理部２０５は多重解像度充填操作に関連した操作を実行する（ここではステップＶと呼ぶ）。多重解像度充填部の入力は、マスクおよび前景画像・背景画像である。
【００３３】
前記の多重解像度操作のいくつかは（ステップＩ、ＩＩＩ、Ｖ）「順変換」部（サブステップＩａ、ＩＩＩａ、Ｖａ）と「逆変換」部（サブステップＩｂ、ＩＩＩｂ、Ｖｂ）とを有する。ステップＩＶもまたいくつかの下位操作を有する。これらの操作については後述する。
【００３４】
図３は多重解像度セグメンテーションおよび充填を実行するための処理の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。
【００３５】
図３を参照すると、処理論理はまず多重解像度前景・背景分解を実行する（処理ブロック３０１）。この多重解像度前景・背景分解は低解像度画像データから予備的前景画像と予備的背景画像とを生成する。ある実施形態では前記低解像度データは、原画像より低い複数の解像度バージョンからのものである。
【００３６】
次に、処理論理は空間的予備的マスクを生成する（処理ブロック３０２）。ある実施形態では、この空間的予備的マスクの生成は、当該マスク中のピクセル位置を前景、背景またはその他のカテゴリーに類別することによって実行される。このその他のカテゴリーはここでは未決と呼ぶことにする。
【００３７】
空間的予備的マスクを生成したのち、処理論理は多重解像度前景・背景生成を実行する（処理ブロック３０３）。ある実施形態では、処理論理は前景ピクセルを近隣に伝搬させ、どの前景ピクセルからも遠い位置に対しては黒、白または原画像を平滑化したバージョンを利用する。前景生成に使われた処理は背景生成にも使うことができ、その場合、背景ピクセルを近隣に伝搬させ、どの背景ピクセルからも遠い位置に対しては黒、白または原画像を平滑化したバージョンを利用する。この操作の結果は、予備的背景画像および予備的前景画像の生成である。
【００３８】
多重解像度前景・背景画像生成ののち、処理論理は空間的最終マスクを生成する（処理ブロック３０４）。ある実施形態では、処理論理がこの空間的最終マスクを生成するのは、原画像と処理ブロック３０３（ステップＩＩＩ）で生成された背景画像・前景画像との比較に基づき、マスク中のノイズを低減させる処理を用いて最終マスクを生成することによって行う。ある実施形態では、処理論理はまたマスクを使って前景と背景を合成したときに厳密に原画像が復元されることを保証する。
【００３９】
空間的最終マスクを生成したのち、処理論理は多重解像度充填操作を実行する（処理ブロック３０５）。ある実施形態では、処理論理は多重解像度充填操作の実行を、前景画像と背景画像中の「どうでもいい」位置において、前景画像と背景画像中のピクセル（合成時に使われないピクセル）をそれぞれ前景の値、背景の値を伝播させることによって充填させる形で行う。
【００４０】
多重解像度前景・背景分解（ステップＩ）
ある実施形態では、多重解像度前景・背景分解は複数の操作を有する。多重解像度前景・背景分解の最初の部分（ここではサブステップＩａと称する）では、順変換を計算する。ある実施形態では、この変換は冗長ハール順ウェーブレット変換である。しかし、たとえば冗長または臨界サンプリングのウェーブレット変換のような他の変換を用いることもできる。ハールに加えて、ＪＰＥＧ２０００で使われる５／３フィルタや９／７フィルタだとかドブシー（Ｄａｕｂｅｃｈｉｅｓ）ウェーブレット、スプラインウェーブレットだとかいった、より長いウェーブレットフィルタを使うこともできる。ガウス関数その他の低域フィルタを使ったラプラシアンピラミッド変換を使うこともできる。
【００４１】
ある実施形態では、順ウェーブレット変換は三つの分解レベルを得るよう使われる。そのような場合、三つの変換レベルに対する低域係数が計算される。ある実施形態では、その低域係数はすべてのレベルについて保存され、高域係数（またはそれについての情報）は多重解像度前景・背景分解の第二の（逆変換の）部分の間に必要に応じて計算される。
【００４２】
多重解像度前景・背景分解操作の第二の操作（ここではサブステップＩｂと称する）は、低域係数を調べ、低域係数を前景と背景に割り振ることを低解像度に始まって高解像度に向けて進める。つまり、低解像度の低域係数（たとえば、ウェーブレット変換の第三レベルからの低域係数）を使ってそれを背景または前景の一部として割り振ろうとする試みがなされるのである。
【００４３】
低解像度レベルにおいて割り振りがなされたら、それは他の、より高い解像度レベルを通じて伝播される。ある実施形態では、他のより高い解像度レベルへの（四つの子係数への）割り振りの伝搬はより高い解像度に対する高域係数を０とすることによって行われ、なめらかな結果を得るために冗長ハール逆変換が使われる。親係数はある解像度レベルｍにおける係数である。この係数は原画像中である特定の局所領域からの情報を含んでいる。（ある親の子係数とは、その次のより高い解像度レベルｍ−１における一連の係数で、合わせたときにレベルｍでの親係数と同じ空間領域を覆うもののことである。）冗長ハール逆変換は、四つの位相の結果を平均することによってなめらかな結果を得る。別のある実施形態では、臨界サンプリング変換が用いられた場合、位相は一つしかなく、平均操作は実行されない。
【００４４】
最低分解解像度において、そして伝搬によって設定されないより高い解像度について、２×２領域における最も明るい低域係数と最も暗い低域係数とがみつけられる。両者の格差がある閾値よりも大きければ、最も明るい低域係数は背景値として予備的背景画像に割り振られ、最も暗い係数は前景値として予備的前景画像に割り振られる。もし両者の格差が前記閾値より小さければ、次のより高い解像度からの低域係数が予備的前景画像と予備的背景画像の両方に使われる。
【００４５】
０…２５５のデータに対するある実施形態では、Ｎを成分数として（たとえばＲＧＢデータであれば３）、レベル２とそれより高いレベルの低域係数の格差の閾値は３２Ｎで、レベル１の場合の係数の格差の閾値は８０Ｎである。ある実施形態では、原ピクセル値（レベル０）の場合の格差は考慮されない。ある実施形態では、格差はＬ１ノルムを使って計算される。
【００４６】
多重解像度前景・背景分解の出力は予備的前景画像と予備的背景画像である。
【００４７】
図４は多重解像度前景・背景分解を実行するための処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。
【００４８】
図４を参照すると、処理論理は多段階の変換レベルに対する係数を順変換を用いて生成する（処理ブロック４０１）。ある実施形態では、低域係数のみが使われ、したがって低域係数のみが保存される。ある実施形態では、前記変換は冗長ハール変換である。
【００４９】
実行する変換レベルは何段階あってもよい。ある実施形態では、処理論理は三レベルの変換に対する係数を生成する。変換レベルの数は、下記で生成される予備的マスクにおいて中間階調ノイズを除去するのに十分な数となるよう選んでもよい。こうして実行される変換レベルは、予備的前景および背景においてノイズを除去し、次の段階での予備的マスクにノイズがはいらないようにする。
【００５０】
順変換を使って多段階の変換レベルに対する係数を生成したのち、処理論理は低域係数を、前景、背景、または該処理論理が前景にするか背景にするかの割り振りにおいて未決である状態を示す値に割り振る（処理ブロック４０２）。
【００５１】
図５は低域係数を前景、背景、または未決値に割り振るための処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。図５を参照すると、この処理の始めにおいて、処理論理は現在の解像度を最低解像度に設定し、領域のおのおのについてあるフラグを「より低解像度での割り振りなし」に設定する（処理ブロック５１１）。
【００５２】
次いで処理論理は現在の解像度での各領域における最も明るい低域係数と最も暗い低域係数とを比較する。ここで、この比較は、これらの係数の格差がある閾値よりも大きい場合かつその場合にのみ有効である（処理ブロック５１２）。ある実施形態では、最も明るい係数は、輝度または色差の指標に従って最も白に近い係数とされる。同様に、最も暗い係数は最も黒に近い。その代わりのある実施形態では、処理論理は、第一の低解像度バージョンにおいて各領域中で最大の色差をもつ二つの低域係数を比較する。色差はΔＥ単位で測ってもよい。ある実施形態では、処理論理は距離尺度（たとえばＬ１ノルム、Ｌ２ノルム、Ｌ∞ノルム）を使って最も明るい低域係数と最も暗い低域係数とを比較する。
【００５３】
前記比較ののち、処理論理は、領域のそれぞれについて、最も明るい低域係数を、前記比較が有効でこの領域に対するフラグが「より低解像度での割り振りなし」であれば背景値として割り振り（処理ブロック５１３）、領域のそれぞれについて、最も暗い低域係数を、前記比較が有効でこの領域に対するフラグが「より低解像度での割り振りなし」であれば前景値として割り振る（処理ブロック５１４）。
【００５４】
処理論理はまた、領域のそれぞれについて、第二の低解像度バージョン、すなわち現在の低解像度バージョンの次のより高い解像度のバージョンからの低域係数を、前記比較が有効でなく、この領域に対する前記フラグが「より低解像度での割り振りなし」であれば前景値と背景値の両方に割り振る（処理ブロック５１５）。あるいはまた、この割り振りは、「どうでもいい」値としてもよい。ここで記述する（ステップＩＩＩ）多重解像度前景・背景生成との関連で記述される前景・背景生成と同じような仕方である。
【００５５】
次に、処理論理は、領域のそれぞれについて、この領域についての前記フラグが「より低解像度での割り振りあり」であれば、高域係数を０として逆ウェーブレット変換を計算する（処理ブロック５１６）。
【００５６】
次に、処理論理は、領域のそれぞれについて、前記比較が有効で、この領域に対する前記フラグが「より低解像度での割り振りなし」であれば、この領域についての前記フラグを「より低解像度での割り振りあり」に設定する（処理ブロック５１７）。
【００５７】
最後に、現在の解像度が二番目に高い解像度でなければ、処理論理は現在の解像度を現在の解像度よりも一つ高い解像度に設定し（処理ブロック５１８）、処理ブロック５１２から５１８を繰り返す。
【００５８】
こうして低域係数の割り振りはまず当該画像の多重の低解像度バージョンのうち第一のものの低域係数を調べることに始まり、次いで前記第一の低解像度バージョンより高い解像度をもつ少なくとももう一つの第二の低解像度バージョンへと進む。
【００５９】
こうして予備的前景画像と予備的背景画像が、原画像の多重低解像度バージョンに関係する低解像度画像データから生成された。
【００６０】
これに代わる別の実施形態では、最も明るい低域係数、最も暗い低域係数をみつける代わりに、Ｌ１色差またはその他の色差が最大になる対を用いることもできるし、最大のハールウェーブレット係数を閾値と比較することもできる。
【００６１】
繰り返すが、ハール以外の他のウェーブレット変換を用いることもできる。
【００６２】
空間的予備的マスク生成（ステップＩＩ）
ステップＩＩでは、原画像ならびに前記の多重解像度前景・背景分解（ステップＩ）の際に生成された予備的前景画像および予備的背景画像から予備的マスクが生成される。ある実施形態では、この予備的マスク中の各ピクセル位置は前景、背景、未決と呼ばれる三つの値のうちの一つをとる。ある特定のピクセル位置における予備的前景画像と予備的背景画像が閾値（たとえば６４Ｎ）ほどの違いがなければ、当該マスクにおける対応するピクセル位置でのマスクの値は未決となる。それ以外の場合には、そのピクセルに対する原画像の値が対応する位置における前景画像での値、背景画像での値、そして前景画像と背景画像中の対応する位置での値の間にある所定の値と比較される。ある実施形態では、前記の所定の値は前景画像と背景画像における対応する位置での値のちょうど中間の値とする（すなわち、前景値と背景値の平均）。他の実施形態では、前記の所定の値は前記の中間の値に十分近い値でよい。その値はセグメンテーションデータ（たとえば中間階調上にテキストがある場合、特定の濃淡値による階調特性など）に依存するものであってもよい。他の選択肢としては、適応閾値処理技術において使われるような局所的平均のような統計的測度などがある。
【００６３】
もし当該値が前景値または背景値により近ければ、前景または背景として類別される。前記の所定の値（たとえば平均値）により近ければ、当該マスク値は未決と類別される。「中間」値との比較を用いることによって前景と判定される領域と背景と判定される領域との間に「デッドゾーン」ができるのである。
【００６４】
図６は空間的予備的マスクを、原画像ならびに前記の予備的前景画像および予備的背景画像から、前記予備的マスク中の各ピクセル位置を類別することによって生成する処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。
【００６５】
図６を参照すると、処理論理は画像中の各ピクセル位置を、前景画像および背景画像中の対応するピクセル位置における値ならびに前景・背景画像中の対応するピクセル位置における値の間のある所定の値（たとえば中間値）と比較する（処理ブロック６０１）。前景と背景の間の差が前記閾値より小さければ、当該ピクセルは未決と類別される（処理ブロック６０２）。当該値が前景画像中の対応するピクセル位置におけるピクセル値により近い場合には、処理論理はそのピクセル位置を前景と類別する（処理ブロック６０３）。当該値が背景画像中の対応するピクセル位置におけるピクセル値により近い場合には、処理論理はそのピクセル位置を背景と類別する（処理ブロック６０４）。当該値が前記所定の値（たとえば中間値）により近い場合には、処理論理はそのピクセル位置を未決と類別する（処理ブロック６０５）。
【００６６】
多重解像度前景・背景生成（ステップＩＩＩ）
ステップＩＩＩでは、前記マスクに（そしてそのマスクの低解像度への伝搬に）基づき、前景・背景と類別された値の空間的な範囲がそれぞれ前景画像・背景画像においてそれぞれ非前景・非背景値を食う形で拡張される。空間的範囲の拡張は、まずはじめに、前景として類別された値および背景として類別された値に順変換を適用する。ある実施形態では、三つの変換レベルが用いられる。多重解像度前景・背景生成操作の最初の部分（ステップＩＩＩａ）は後述する冗長ハール順変換の適用と似ているが、フィルタ係数が予備的マスクに依存するという点で異なっている。ある実施形態では、低域係数のみが計算され、保存される。
【００６７】
より具体的には、前景に対する変換を実行することを考える。もしも四つの入力値すべてが先に空間的予備的マスクにおいて前景として類別されていたら、低域係数は普通に計算され、前景として類別される。もしも四つの入力値のうちどれも前景として類別されていなかったら（すなわち、背景または未決）、低域係数は普通に計算され、「どうでもいい」として類別される。（「どうでもいい」係数というのは、逆変換において寄与しない係数である。下記で議論するように、これらは０という重みをかけられる係数である。いくつかの場合には、これらの「どうでもいい」係数は鏡映の代わりに境界処理に使われることがある。一般に、「どうでもいい」係数は「どうでもいい」ピクセルに対応するサポートをもつ―それらは両方とも「どうでもいい」位置にあるのである。）もしも四つの入力値のすべてが先に前景として類別されているのではないが該入力値の少なくとも一つが前景として類別されていたら、前景として類別されている１ないし３個の入力値を平均して低域係数（これは通常のハール係数ではない）を求め、この係数が前景として類別される。同じ処理を背景についても使うことができる。その場合、前景が「どうでもいい」の範囲に含まれている部分では類別は背景か「どうでもいい」になる。
【００６８】
いくつかの場合には、係数は先に計算されている係数と同じになり、その値が記憶装置から得られる場合には計算しなおす必要がないことに注意しておく。
【００６９】
多重解像度前景・背景生成操作の第二の部分（ステップＩＩＩｂ）は前景・背景に類別された値を背景画像および前景画像の低解像度バージョンに伝搬させる。たとえば前景の場合、四つの入力値のすべてが前景と類別されていたら、すべての高域係数を０に設定しての逆冗長ハールウェーブレットによるなめらかな再構成が用いられる。もしも１ないし３個の入力が前景と類別されていたら、その平均が（通常のハール逆変換値の代わりに）逆変換値として使われる。（もしハール以外のフィルタが使われている場合には、平均の代わりにそのフィルタを適切に打ち切り・規格化したバージョンを使うことができる。）もしも前景として類別された入力がなかったら、新規の値は黒、白、または対応する通常のハール低域係数（あるいはまたレベル０に対する原サンプル）とする。背景として類別された入力についても同じ処理が適用される。ハール低域値から白への距離（たとえばＬ１ノルム）が当該信号のダイナミックレンジの３／８（たとえば９６Ｎ）未満なら前景には黒が選ばれる。同様に、ハール低域値から黒への距離がダイナミックレンジの３／８未満なら背景には白が選ばれる。３／８という閾値を用いることで、前景と背景は５０％閾値のあたりで似たような値になり、そのためセグメンテーションによる人工効果の見え方が減じることに注意しておく。
【００７０】
図７は多重解像度前景・背景生成を実行するための処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。
【００７１】
図７を参照すると、処理論理は最初に多段の変換レベルについて前景と類別された値および背景と類別された値の低域係数を計算している（処理ブロック７０１）。
【００７２】
多段の変換レベルについて低域係数を計算したのち、処理論理は前景と背景に対応する低域係数の逆変換値を、予備的マスク内の先に前景、背景、未決と類別されたピクセルの集合内のピクセルの数に基づいて計算する（処理ブロック７０２）。
【００７３】
図８は前景に対応する低域係数についての逆変換値を計算するための処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。
【００７４】
図８を参照すると、低域係数の各集合について、もしも前記各集合内の低域係数に対応するピクセル値がすべて予備的マスクにおいて前景として類別されていたら、処理論理は逆変換値を通常の逆ウェーブレット変換値として計算する（処理ブロック８０１）。もしも前記各集合内の低域係数に対応するピクセル値がどれも予備的マスクにおいて前景として類別されていなかったら、処理論理は低域係数の各集合に対する逆変換値を「どうでもいい」値として指定する（処理ブロック８０２）。もしも前記各集合内の低域係数に対応するピクセル値のうちの全部ではない一部が予備的マスクにおいて前景として類別されていたら、処理論理は低域係数の各集合に対する逆変換値を、前記予備的マスクにおいて前景として類別されていた前記各集合内のピクセル値に対応する低域係数の平均として計算する（処理ブロック８０３）。
【００７５】
図９は背景に対応する低域係数に対する逆変換値を計算する処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。図９を参照すると、低域係数の各集合について、もしもその集合内の低域係数に対応するピクセル値がすべて予備的マスクにおいて背景として類別されていたら、処理論理は逆変換値を通常の逆ウェーブレット変換値として計算する（処理ブロック９０１）。もしもその集合内の低域係数に対応するピクセル値がどれも予備的マスクにおいて背景として類別されていなかったら、処理論理は低域係数の各集合に対する逆変換値を「どうでもいい」値として指定する（処理ブロック９０２）。もしもその集合内の低域係数に対応するピクセル値のうちの全部ではない一部が予備的マスクにおいて背景として類別されていたら、処理論理は低域係数の各集合に対する逆変換値を、前記予備的マスクにおいて背景として類別されていたその集合内のピクセル値に対応する低域係数の平均として計算する（処理ブロック９０３）。
【００７６】
図７の参照に戻ると、類別ののち、処理論理は前景・背景と類別された値を前景画像および背景画像の低解像度バージョンに伝搬させる（処理ブロック７０２）。図１０は前景として類別された値を伝搬させるための処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。図１０を参照すると、処理論理は、四つの入力値のすべてが前景として類別されていたら、すべての高域係数を０に設定しての逆冗長ハールウェーブレットによるなめらかな再構成を実行することから帰結する値を使う（処理ブロック１００１）。もしも１ないし３の入力値だけが前景として類別されていたら、前景として類別されていた入力値の平均である値を逆変換値として使う（処理ブロック１００２）。もしも入力値のどれも前景として類別されていなければ、新規の値を使う（処理ブロック１００３）。ある実施形態では、その新規の値は黒、白、または対応する通常のハール低域係数からなる集合から選ばれる一つである。ある実施形態では、ハール低域値から白への距離を示すある距離指標が、黒に対応する値から白に対応する値の間で変化しうる当該信号のダイナミックレンジの３／８未満なら、その新規の値は前景に対しては黒となる。
【００７７】
図１１は背景として類別された値を伝搬させるための処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。図１１を参照すると、処理論理は、四つの入力値のすべてが背景として類別されていたら、すべての高域係数を０に設定しての逆冗長ハールウェーブレットによるなめらかな再構成を実行することから帰結する値を使う（処理ブロック１１０１）。もしも１ないし３の入力値だけが背景として類別されていたら、背景として類別されていた入力値の平均である値を逆変換値として使う（処理ブロック１１０２）。もしも入力値のどれも背景として類別されていなければ、新規の値を使う（処理ブロック１１０３）。その新規の値は黒、白、または対応する通常のハール低域係数からなる集合から選ばれる一つである。ある実施形態では、ハール低域値から黒への距離を示すある距離指標が、黒に対応する値から白に対応する値の間で変化しうる当該信号のダイナミックレンジの３／８未満なら、その新規の値は背景に対しては白となる。
【００７８】
最終マスク生成（ステップＩＶ）
ある実施形態では、最終マスク生成操作は三つの部分を有する。最終マスク生成操作の第一の部分（ここではサブステップＩＶａ「作成」と称する）は前景、背景または未決の値をもつマスクを作成する。ある実施形態では、前景、背景、または未決の値をもつ前記マスクの作成は、原ピクセル値とその対応する背景および前景ピクセルとの間の距離ならびにこれらの背景ピクセルと前景ピクセルとの間の距離を計算することを含む。前景距離と背景距離との差の絶対値がある閾値（たとえば３２Ｎ）より小さければ、その値は未決として類別される。そうでなければ前景距離と背景距離のいずれが小さいかに従ってその値を前景または背景に類別する。
【００７９】
図１２は最終マスク生成（ステップＩＶｂ）において使われる１２ピクセル近傍である。前記最終マスク生成の第二の部分（ここではサブステップＩＶｂ「近傍」と称する）では、前景または背景の割り振りを変更するためにマスク値の近傍が用いられる。ある実施形態では、図１２に示すようなマスク値の１２ピクセルの近傍が用いられる。未決の値は、６以上の近隣値が前景であれば前景、そうでなければ背景と割り振られる。近傍と異なる単独ピクセルは近傍の多数の値に合わせて変更される。多重解像度前景・背景分解操作において前景・背景が割り振られなかった位置については、最低の閾値（たとえば５）の数だけの近傍値と一致しない値は近傍の多数の値に合わせて変更される。
【００８０】
この最終マスク生成操作の第二の部分において用いられる操作は、Ｊ．Ｈｕａｎｇ，Ｙ．Ｗａｎｇ  ａｎｄ  Ｅ．Ｗｏｎｇ，“Ｃｈｅｃｋ  ｉｍａｇｅ  ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  ａ  ｌａｙｅｒｅｄ  ｃｏｄｉｎｇ  ｍｅｔｈｏｄ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｅｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，７（３），ｐｐ．４２６−４４２，Ｊｕｌｙ  １９９８において議論されている面積比アルゴリズムおよびメジアンフィルタ処理の拡張に関連している。
【００８１】
１２ピクセルの近傍を考える動機の一つは、文字「ｉ」の点が文字の他の部分から１ピクセルだけ離れた単一のピクセル点で表されているような非常に小さなフォントでも点が消えないようにすることである。
【００８２】
ウィンドウの形は追加的な情報（たとえばＯＣＲで文字の領域を表す矩形）に依存しうることを注意しておく。
【００８３】
最終マスク生成操作の第三の部分（ここではサブステップＩＶｃ「更新」と称する）は直前の操作からの前景画像および背景画像を更新して、マスクを用いて合成したときに損失のない画像が得られるようにする。ある実施形態では、これは前景または背景として類別されたピクセルをそれぞれ前景画像、背景画像においてそのピクセルの原画像での値に設定することによって実現される。
【００８４】
図１３は最終マスクを生成する処理の一つの実施形態の流れ図である。この処理を実行する処理論理は、ハードウェア（たとえば回路や専用論理素子など）であってもよいし、ソフトウェア（汎用コンピュータシステムや専用機で実行されるような）であってもよいし、両者の組み合わせであってもよい。
【００８５】
図１３を参照すると、処理論理は、当該画像中のピクセル値と前景画像および背景画像中の対応するピクセル位置の値との間の距離を計算することによって、中間マスクを作成し（処理ブロック１３０１Ａ）、もし前景画像と背景画像における値の間の差がある閾値よりも小さければ、該中間マスク中の各ピクセル値を未決として類別する（処理ブロック１３０１Ｂ）。
【００８６】
処理論理はまた、もし原画像のピクセル値と前景画像と背景画像における値の間の差が前記閾値より大きければ、各ピクセル値を前景または背景として類別する（処理ブロック１３０２）。ある実施形態では、各ピクセル値を、もし当該画像中の各ピクセルと前景画像との間の距離が当該画像中の各ピクセルと背景画像との距離よりも小さければ前景に設定し、もし当該画像中の各ピクセルと背景画像との間の距離が当該画像中の各ピクセルと前景画像との距離よりも小さければ背景に設定する。
【００８７】
処理論理は中間マスクでの未決の値について、出力される最終マスクにおける近隣のピクセル値の集合のうちのある数が前景または背景であるかどうかに基づいて、それぞれ前景または背景に割り振り直す（処理ブロック１３０３）。これにより最終マスクが作成される。
【００８８】
処理論理は次いで、前景画像および背景画像における値を、対応する位置が最終マスクにおいてそれぞれ前景・背景に類別されていれば、当該画像の値に設定する（処理ブロック１３０４）。
【００８９】
このように、前記処理論理は原画像を、該最初の画像の複数の解像度での画像データを使って作成された背景画像および前景画像と比較する。この操作によって生成されたマスクは、前景画像と背景画像をそのマスクを使って合成すれば最初の画像になるようなものになっている。
【００９０】
多重解像度充填（ステップＶ）
多重解像度充填操作は多重解像度前景・背景生成操作と同様である。その二つの操作の間の違いは次の通りである。この操作は前景画像と背景画像の作成を完成させる。ある実施形態では、五つの変換レベルが使用される。予備的マスクの代わりに最終マスクが使われる。第二の部分（サブステップＶｂ）では、どの入力も前景として類別されていなければ、新規の値は通常の逆ハール変換からの値とする。出力は最終的な前景画像と背景画像である。
【００９１】
一次元信号についての当該技術の数学的解説
上述した技術について、一次元信号とスカラー（グレースケール）入力の場合について数学的表記を用いて以下に説明する。数学的記述の目的のために、入力は０…２５５の範囲の整数値をとるものとする。
【００９２】
［サブステップＩａ］
図１４は３レベル（Ｊ＝３）の場合について、入力（ｘ）および低域係数（ｃ）を示している。多重解像度前景・背景分解（サブステップＩａ）の順変換部分である。
【００９３】
レベルｊ（ｊ＝１，…，Ｊ）、位置ｉにおける低域ハールウェーブレット係数ｃは、
【００９４】
【数１】
2006074770.tif 000003
となる。レベル０の低域係数の代わりに入力信号そのものが使われる。
【００９５】
【数２】
2006074770.tif 000004
また、必要に応じて、０≦ｉ＜Ｉについて信号が定義されているような境界での鏡映
【００９６】
【数３】
2006074770.tif 000005
を使うことができる。
レベルｊ、位置ｉにおける高域ハールウェーブレット係数ｄは、
【００９７】
【数４】
2006074770.tif 000006
となる。（冗長、すなわち過剰決定変換が計算されており、すべてのレベルについてｉ＝０，１，２，３，…となっていることに注意。式（１）および（４）の変換はここでは分母が２と１になっているが、１、√２、または２として計算することもできる。ある実施形態では、順変換と逆変換を合わせると利得が１になることを保証するために、逆変換が分母をもつようになっている。）
［ステップＩｂ］
多重解像度前景（ｆｏｒｅｇｒｏｕｎｄ）・背景（ｂａｃｋｇｒｏｕｎｄ）分解の逆変換部分（ステップＩｂ）はレベルｊ＝Ｊ，…，１にわたってループ処理される。
【００９８】
第一に、係数間の差分が考慮される。レベルに依存する閾値εｊが使われる（ｊは添え字であって指数ではない）。εｊについての値の一つの選び方は、ｊ＝１に対しては８０、ｊ＞１に対しては３２というものである。もし
【００９９】
【数５】
2006074770.tif 000007
であり、先のレベル（＞ｊ）については位置ｉでも位置ｉ−２ｊ＋１でもこれが成立していなかったとすると、
【０１００】
【数６】
2006074770.tif 000008
とする。ここで、ｋ＝１，…，ｊである。それ以外の場合には、
【０１０１】
【数７】
2006074770.tif 000009
とする。ここで、ｋ＝１，…，ｊである。
【０１０２】
第二に、逆ハールウェーブレット変換が適用される。前景に対する変換を下記に示す。背景に対する変換も同様に計算される。この変換は次のように記される。
【０１０３】
【数８】
2006074770.tif 000010
ただし、式（６）の場合には単純化されて
【０１０４】
【数９】
2006074770.tif 000011
とでき、式（７）の場合には単純化されて
【０１０５】
【数１０】
2006074770.tif 000012
とできる。レベルｊ＝１に対する結果は予備的前景画像ｘｆおよび予備的背景画像ｘｂである。ここで、背景画像に対して同じ変換計算が用いられる。
［ステップＩＩ］
ある実施形態では、ステップＩＩは次の三つの距離を用いる。
【０１０６】
【数１１】
2006074770.tif 000013
次の予備的マスクが作成される。
【０１０７】
【数１２】
2006074770.tif 000014
ここで値１が背景、値−１が前景、値０が未決を表し、たとえばｔ＝６４である。
［サブステップＩＩＩａ］
ある実施形態では、レベルｊ（ｊ＝１，…，Ｊ）についての前景および背景に対する重みｗｊｆ，ｉおよびｗｊｂ，ｉは次式によって計算される。
【０１０８】
【数１３】
2006074770.tif 000015
ここで、ｉ′は範囲０，…，２ｊ−１−１のすべての値を表し、たとえばＪ＝３である。
【０１０９】
ある実施形態では、前景について、
【０１１０】
【数１４】
2006074770.tif 000016
とおく。もしｓｊｆ，ｉ＞０であれば、
【０１１１】
【数１５】
2006074770.tif 000017
ここで、
ｃ′０ｆ，ｉ＝ｘｆ，ｉ                  （１５）
上記以外の場合には、ｃ′ｊｆ，ｉの値は「どうでもいい」とする（最終的には重み０を乗じられるか、境界条件値として使われるかだけであるので）。何か値を与えたければ、通常の順ハール変換の値ｃ′ｊｆ，ｉ＝ｃｊｉを使えばいい。
【０１１２】
背景は同様にして計算される。
【０１１３】
［サブステップＩＩＩｂ］
ある実施形態では、サブステップＩＩＩｂは、レベルｊ（ｊ＝Ｊ，…，１）について前景に関して次のように計算が行われる。更新重みを
【０１１４】
【数１６】
2006074770.tif 000018
とする。ここで＾の付いたｉ′は範囲０，…，２ｊ−１のすべての値を表す。
【０１１５】
【数１７】
2006074770.tif 000019
とおく。
場合１：式（１７）の値が＞０
【０１１６】
【数１８】
2006074770.tif 000020
場合２：式（１７）の値が０
【０１１７】
【数１９】
2006074770.tif 000021
背景については少し違う関数が用いられる。
【０１１８】
【数２０】
2006074770.tif 000022
ここでたとえばεｗ＝１６０、εｂ＝９６である。
場合３：ｊ＜Ｊのレベル
【０１１９】
【数２１】
2006074770.tif 000023
背景は同様にして計算される。ある実施形態では、前景と背景の結果は次のようになる。
【０１２０】
【数２２】
2006074770.tif 000024
［ステップＩＶａ］
ある実施形態では、次の三つの距離が計算される。
【０１２１】
【数２３】
2006074770.tif 000025
ある実施形態では、−１＝前景、１＝背景、０＝未決という値をとるマスクが次式によって作成される。
【０１２２】
【数２４】
2006074770.tif 000026
ここでたとえば
【０１２３】
【数２５】
2006074770.tif 000027
である。
【０１２４】
［サブステップＩＶｂ］
ある実施形態では、次の重みが計算される。
【０１２５】
【数２６】
2006074770.tif 000028
ある実施形態では、近傍Ｎ′（ｉ）にわたって重みが合計される。
【０１２６】
【数２７】
2006074770.tif 000029
１Ｄの場合には、Ｎ′（ｉ）として図１２の２Ｄ近傍の代わりにたとえば次のような１２ピクセル近傍を使えばよい。ｎは図１５に示すようにｉ−６，…，ｉ−１およびｉ＋１，…，ｉ＋６の値をとるのである。
【０１２７】
未決値のない二値マスクｍ″が作成される。
【０１２８】
【数２８】
2006074770.tif 000030
ここで、ｍ″＝１が前景、ｍ″＝０が背景で、たとえばεｍ１＝６である。
【０１２９】
ある実施形態では、更新重みが次のように計算される。
【０１３０】
【数２９】
2006074770.tif 000031
ある実施形態では、重みは近傍Ｎ′（ｊ）にわたって合計される。
【０１３１】
【数３０】
2006074770.tif 000032
ここで、Ｎ′ａ，（ｉ）およびＮ′ｂ，（ｉ）はＮ′（ｉ）を因果的（すなわちｎ＜ｉ）および非因果的（すなわちｎ＞ｉ）領域に分割したものである。
【０１３２】
ある実施形態では、最終マスクは次式によって与えられる。
【０１３３】
【数３１】
2006074770.tif 000033
ここでたとえば、ｘｆ，ｉ＝ｘｂ，ｉであればεｍ２，ｉ＝５（ｊ＝１についてサブステップＩｂの場合１および２）、ｘｆ，ｉ≠ｘｂ，ｉであればεｍ２，ｉ＝１（ｊ＝１についてサブステップＩｂの場合３）である。
【０１３４】
［サブステップＩＶｃ］
ある実施形態では、最終マスクが与えられた場合、更新前景画像と更新背景画像は次のようになる。
【０１３５】
【数３２】
2006074770.tif 000034
［サブステップＶａ］
新しい低域係数が計算される。ある実施形態では、レベルｊ（ｊ＝１，…，Ｊ）においての前景および背景についての重みｗ″ｆ，ｉｊおよびｗ″ｂ，ｉｊは次のように計算される。
【０１３６】
【数３３】
2006074770.tif 000035
ここで、ｉ′は範囲０，…，２ｊ−１−１のすべての値で、たとえばＪ＝５である。
【０１３７】
前景について、
【０１３８】
【数３４】
2006074770.tif 000036
とおく。もしｓ″ｊｆ，ｉ＞０であれば、
【０１３９】
【数３５】
2006074770.tif 000037
ここで、
ｃ″０ｆ，ｉ＝ｘ″ｆ，ｉ                （３５）
上記以外の場合には、通常の順ハール変換が使える（これは先のステップですでに計算済みかもしれない）
【０１４０】
【数３６】
2006074770.tif 000038
背景は同様にして計算される。
［サブステップＶｂ］
ある実施形態では、サブステップＶｂはレベルｊ＝Ｊ…１について、前景の場合、次のように計算される。
場合１：ｗ″ｊ−１ｆ，ｉ＝１の場合、
【０１４１】
【数３７】
2006074770.tif 000039
は不変である。
それ以外の場合は、ある実施例では更新重みが次式によって計算される。
【０１４２】
【数３８】
2006074770.tif 000040
ここで、＾付きのｉ″は範囲
【０１４３】
【数３９】
2006074770.tif 000041
のすべての数である。
【０１４４】
【数４０】
2006074770.tif 000042
場合２ａ：式（３８）が＞０の場合、
【０１４５】
【数４１】
2006074770.tif 000043
場合２ｂ：それ以外の場合、
【０１４６】
【数４２】
2006074770.tif 000044
背景は同様にして計算される。ある実施形態では、最終的な前景と背景の結果は、次式で与えられる。
【０１４７】
【数４３】
2006074770.tif 000045
【実施例】
【０１４８】
一次元の数値例
図１６は一次元信号ｘについてステップＩからＩＩＩａの数値例を示したものである。サブステップＩｂにおける差分は、閾値εｊを超えるものには下線を付し、直前のレベルでの対応する差分が該閾値を超えていた場合には計算していない（表では「−−−」としてある）。ステップＩＩにおける差分｜ｘｆ，ｉ−ｘｂ，ｉ｜は、閾値ｔを超えるものには下線を付してある。ステップＩＩＩａについては、「どうでもいい」値は「−−−」としてある。
【０１４９】
図１７は同じ例の続きで、サブステップＩＩＩａを繰り返し、ステップＩＩＩｂからＩＶを示している。
【０１５０】
図１８および図１９はステップＶをそれぞれ前景、背景について示している。「どうでもいい」値は「−−−」としてある。それまで「どうでもいい」だった位置（添え字ｉ）に初めて値が割り当てられたものには、サブステップＶａとサブステップＶｂの最初のレベルのところで下線を付してある。サブステップＶｂの残りのレベルについては、値が変わらなかった場合が下線で示してある。
【０１５１】
二次元およびカラーへの拡張
上述した一次元の数学的説明はいくつかの拡張が可能で、画像データ、カラーデータ、その他の高次元データを扱うことができるようになる。グレースケールデータの代わりにカラーデータを（より一般には、スカラーデータの代わりにベクトルデータを）処理するときには、距離として使われた絶対値はＬ１、Ｌ２、Ｌ∞のようなノルムで、あるいはΔＥのような色差の測度で置き換えることができる。セグメンテーションおよび充填の前に、ＲＧＢからＹＵＶのような色変換を適用してもよい。前記ノルムや色差の測度と一貫性をもつように閾値も調整される。たとえば、Ｌ１測度を使うときには閾値に色成分の数を乗じてもよい。
【０１５２】
一次元信号から画像のような二次元信号へ、あるいは体積データのようなより高次元信号への拡張は、それらの高次元でのハール変換を用いることができる。一般に、これまでの式における添え字ｉは各次元方向の添え字の組で置き換えられる。二次元の場合、ｉおよびｉ±２ｊでの計算は（ｉ，ｌ），（ｉ±２ｊ，ｌ），（ｉ，ｌ±２ｊ），（ｉ±２ｊ，ｌ±２ｊ）での計算で置き換えられる。
【０１５３】
代替手段と改良
テキストもしくは線画領域の一方または両方を見出すためのページセグメンテーションまたは文書レイアウト解析を使っているため、この方法はテキストもしくは線画領域の一方または両方に対してしか使えない。ページセグメンテーションが使われる場合、ＪＰＭ画像はそれぞれ前景画像、背景画像およびマスクをもつ複数の領域で作成できる。ＪＰＭファイルでは、背景画像は自己マスク画像オブジェクトとなり、マスクは前景画像と同じオブジェクト内になる。
【０１５４】
無地の背景を画像から孤立させると、主観的な画質が向上する場合がある。
【０１５５】
ステップＩ、ＩＩＩ、Ｖにおける解像レベルＪは追加的に得られる類別についてのデータ（たとえば類別が中間階調かそうでないか）によって変わることもある。
【０１５６】
マスクに基づくフィルタ係数修正の代替方法
これまでの式の記号法を使っていくつかの代替実装を記述することができる。ある実施形態では、ステップＩＩＩａの式１３におけるｗｊｆ，ｉおよびｗｊｂ，ｉの計算は下記の二つの代替方法のいずれかで置き換えることができる。ある実施形態では、
【０１５７】
【数４４】
2006074770.tif 000046
にも同様の変更が行われる。こうしたことによって、フィルタ係数がさまざまなマスクから影響を受ける仕方が変更を受ける。これらのステップ操作のそれぞれについて、三つの候補（式（１３）、（４２）、（４３））のうちのいずれも独立に選択することができる。
【０１５８】
【数４５】
2006074770.tif 000047
【０１５９】
【数４６】
2006074770.tif 000048
非可逆圧縮
多重解像度セグメンテーション・充填技術は可逆圧縮において有用であるが、非可逆圧縮や両者の組み合わせについても用いることができる。たとえば、前景・背景画像に非可逆圧縮につながるような追加的な処理ステップを適用することもできる（たとえばノイズ除去など）。
【０１６０】
上述したように、可逆圧縮については（あるいは可逆・非可逆圧縮については）、マスクによって前景として選択されたピクセルについては前景が原画像と一致し、背景として選択されたピクセルについては背景が原画像と一致する。そして前景、背景、マスクは可逆的に圧縮される。非可逆圧縮だけの場合には、前景や背景が原画像と一致するという要求を緩和することができる。これにより、特に非常に高い圧縮率において非可逆圧縮の場合にビットレートとゆがみのかねあいを改善することができる。
【０１６１】
ある実施例では、前景画像と背景画像の一方または両方がより低解像度にまびかれる。（前景・背景画像は、マスクによって選択された部分では原画像の低解像度バージョンの対応する部分に一致する。）印刷解像度の画像（たとえば３００、４００、６００、８００、１２００ｄｐｉまたはそれ以上）について、前景画像（そして背景画像）をまびいて７５、１００、１５０または２００ｄｐｉのような低解像度にすることができる。さらに、ここで記述された技術を適用する前に高解像度画像をまびいて低解像度にしてもよい。それにより前景、背景、マスクの解像度が低下する。
【０１６２】
別の実施形態では、厳密な一致の要求を満たす代わりに、前景（背景）の領域内部が一致し、エッジ部分での一致は要求しないようにしてもよい。エッジに対応する区域は、類別が異なるピクセルに隣接するピクセルのような画像構成系によって定義してもよいし、ｄｐｉ（解像度、コントラストおよびヒトの視覚系のコントラスト感度特性）に基づいて定義してもよい。領域のエッジでない部分が「内部」である。このような手法は「厳密な」充填に対して「非可逆エッジ」充填と呼ばれる。非可逆エッジ充填はヒトの視覚系の視覚マスキングの性質を活用することができる。その性質とは、強いエッジがあるとそうしたエッジ部位での圧縮に起因する他の弱い人工効果は見えにくくなるというものである。前景（そして背景）を生成する際、ある位置は次の条件が満たされたときに「どうでもいい」と判断される。
・（通常の場合）マスクがその位置を前景（背景）として選択していない。
・（非可逆エッジの場合）マスクがその位置を前景（背景）として選択しており、該マスクは隣接位置を選択しておらず、少なくとも一つの隣接位置はそのすべての隣接位置が選択されている。
【０１６３】
隣接位置の数は４のこともあれば８のこともあり、それ以外のなんらかの形態的構造化要素によって定義されていることもある。前記の条件の「少なくとも一つの隣接位置はそのすべての隣接位置が選択されている」の部分は、隣接位置どうしからなる近傍よりも小さな前景（背景）の領域が完全に「どうでもいい」となってしまうことを防ぐものである。（小さな領域が作成されないことを保証するよう、マスクを作成する際に小さな領域の作成を最低限にするか少なくとも減らすことが望ましいかもしれない。隣接位置どうしからなる近傍のサイズより小さな領域が作成されることがなければ、非可逆エッジ充填は単純化される。）図２０に例を示してある。これは形態的な拡張と似ているが、構造化要素よりも小さな領域を消してしまうことを回避している。別の実施例では、エッジ位置を「どうでもいい」として扱う代わりに、充填値を計算するのに重みが用いられ（たとえば式（３３）におけるｗ″ｆ，ｉとｗ″ｂ，ｉ）、それによってエッジ付近の位置が０（「どうでもいい」）か１（可逆）ではなく、その幅内について０．２５や０．５といった中間的な値をとるようになる。これにより領域が隣接位置どうしからなる近傍より小さくならないようにしたり、複雑な縁削りアルゴリズムを用いたりすることが回避できる（図２３参照）。エッジを「非可逆」にするとエッジが先鋭になるというしばしば好ましい効果を生む。図２１に例が示してある。これはスキャンしたテキストにはとりわけ望ましいことである。非可逆エッジの場合はコントラスト感度特性であり、これが前景画像と背景画像に適用されて視覚マスキングを実行することができる。非可逆エッジの場合はコントラスト感度特性であり、これが前景画像と背景画像に適用されて視覚マスキングを実行することができる。
【０１６４】
コンピュータシステムの例
図２２は、ここで記述されている操作の一つないし複数を実行しうる代表例としてのコンピュータシステムのブロック図である。図２２を参照すると、コンピュータシステム２２００は典型的なクライアント／サーバーコンピュータシステムを有していることができる。コンピュータシステム２２００は情報を通信するための通信機構すなわちバス２２１１と、バス２２１１と結合した情報を処理するプロセッサ２２１２とを有する。プロセッサ２２１２は、たとえばペンティアム（商標）、パワーＰＣ（商標）、アルファ（商標）などのようなマイクロプロセッサを有するが、このようなマイクロプロセッサには限らない。
【０１６５】
システム２２００はさらに、バス２２１１に結合し、情報やプロセッサ２２１２で実行される命令を保存するためのランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置２２０４（メインメモリと称する）を有する。メインメモリ２２０４はまた、一時変数や他の中間的な情報をプロセッサ２２１２による命令の実行中に保存するために使うこともできる。
【０１６６】
コンピュータシステム２２００はまた、バス２２１１に結合し、プロセッサ２２１２のための静的な情報や命令を保存するための読み出し専用記憶装置（ＲＯＭ）もしくはその他の静的記憶装置またはその両方２２０６、ならびに磁気ディスクや光ディスクおよびそれに対応するディスク駆動装置のようなデータ記憶装置２２０７を有する。データ記憶装置２２０７はバス２２１１に結合しており、情報や命令を保存するためのものである。
【０１６７】
コンピュータシステム２２００はさらに、バス２２１１に結合し、コンピュータユーザーに情報を表示する、陰極線管（ＣＲＴ）や液晶表示装置（ＬＣＤ）のような表示装置２２２１に結合していてもよい。情報やコマンドの選択をプロセッサ２２１２に通信するための、英数字その他のキーをもつ英数字入力装置２２２２もまたバス２２１１に結合していてもよい。追加的なユーザー入力装置は、マウス、トラックボール、トラックパッド、スタイラス、またはカーソル方向キーのようなカーソル制御装置２２２３であり、これもバス２２１１に結合しており、プロセッサ２２１２に方向情報やコマンドの選択を通信し、表示装置２２２１上でカーソルの動きを制御するためのものである。
【０１６８】
バス２２１１に結合している可能性のあるもう一つの装置はハードコピー装置２２２４である。これは命令やデータその他の情報を紙、フィルムまたは同様な媒体のような媒体上に印刷するために使われうるものである。さらに、スピーカーもしくはマイクまたはその両方のような音声録音・再生装置も任意的にバス２２１１に結合してコンピュータシステム２２００のオーディオインターフェースとなっていてもよい。バス２２１１に結合している可能性のあるもう一つの装置は、電話や携帯機器と通信するための有線・無線の通信機能装置２２２５である。
【０１６９】
本発明には、コンピュータシステム２２００および関連ハードウェアのいずれでも、またすべてでも用いることができることを注意しておく。ただし、該コンピュータシステムの他の構成が前記装置の一部または全部を含んでいてもよいことは認識できよう。
【０１７０】
これまでの記述を読めば、通常の技量を持った当業者には、本発明の多くの改変や修正が明らかとなることは間違いないと思われるものの、解説のために示され、記述された特定の実施形態のいずれも、本発明を限定するものとみなされることは決して意図していない。したがって、さまざまな実施形態の詳細への言及は、本発明に本質的とみなされる特徴のみを挙げている特許請求の範囲を限定するものと意図されてはいない。
【図面の簡単な説明】
【０１７１】
【図１】エンコーダのブロック図である。
【図２】多重解像度セグメンテーションおよび充填技術を実行するのに使うことのできるセグメンテーション・充填手段の一つの実施形態のブロック図である。
【図３】多重解像度セグメンテーションおよび充填を実行するための処理の流れ図である。
【図４】多重解像度前景・背景分解を実行するための処理の一つの実施形態の流れ図である。
【図５】低域係数を前景、背景または未決の値に割り振るための処理の一つの実施形態の流れ図である。
【図６】空間的予備的マスクを、該予備的マスク内の各ピクセル位置を類別することによって原画像、予備的背景画像、予備的前景画像から生成するための処理の一つの実施形態の流れ図である。
【図７】多重解像度前景・背景生成を実行するための処理の一つの実施形態の流れ図である。
【図８】前景に対応する低域係数に対する逆変換値を計算するための処理の一つの実施形態の流れ図である。
【図９】背景に対応する低域係数に対する逆変換値を計算するための処理の一つの実施形態の流れ図である。
【図１０】前景に類別された値を伝搬させるための処理の一つの実施形態の流れ図である。
【図１１】背景に類別された値を伝搬させるための処理の一つの実施形態の流れ図である。
【図１２】最終マスク生成操作において使われる１２ピクセル近傍を示す図である。
【図１３】最終マスクを生成するための処理の一つの実施形態の流れ図である。
【図１４】三つの変換レベルの場合の入力と低域係数を示す図である。
【図１５】１２ピクセル近傍の例を示す図である。
【図１６】一次元信号について数値的な例を示す図である。
【図１７】一部の操作を反復し、例が継続する様子を示す図である。
【図１８】一つの操作を前景に対して示す図である。
【図１９】一つの操作を背景に対して示す図である。
【図２０】２Ｄの非可逆エッジを示す図である。
【図２１】１Ｄの非可逆エッジを示す図である。
【図２２】ここに記載される操作の一つないし複数を実行することのできる代表例としてのコンピュータシステムのブロック図である。
【図２３】損失のあるエッジ充填において使う中間値をもつ重みの例の図解である。
【符号の説明】
【０１７２】
１００    エンコーダ
１０２    入力画像
１０４    セグメンテーション手段および充填手段
１０６    前景画像、背景画像
１０８    マスク
１１０    連続階調圧縮手段（ＪＰＥＧ２０００）
１１２    二値データ圧縮手段（ＪＢＩＧ）
１１４    ＪＰＭファイル
２００    セグメンテーション手段・充填手段
２１０    入力画像
２０１    多重解像度前景・背景分解部
２０２    空間的予備的マスク処理部
２０３    多重解像度前景・背景生成部
２０４    空間的最終マスク部
２０５    多重解像度充填部
２２０    前景画像、背景画像
２３０    マスク
２２０４  メインメモリ
２２０６  静的記憶装置
２２０７  大容量記憶装置
２２１１  バス
２２１２  プロセッサ
２２２１  表示装置
２２２２  キーボード
２２２３  カーソル制御装置
２２２４  ハードコピー装置
２２２５  無線・電話インターフェース
【図１】
2006074770.tif 000049
【図２】
2006074770.tif 000050
【図３】
2006074770.tif 000051
【図４】
2006074770.tif 000052
【図５】
2006074770.tif 000053
【図６】
2006074770.tif 000054
【図７】
2006074770.tif 000055
【図８】
2006074770.tif 000056
【図９】
2006074770.tif 000057
【図１０】
2006074770.tif 000058
【図１１】
2006074770.tif 000059
【図１２】
2006074770.tif 000060
【図１３】
2006074770.tif 000061
【図１４】
2006074770.tif 000062
【図１５】
2006074770.tif 000063
【図１６】
2006074770.tif 000064
【図１７】
2006074770.tif 000065
【図１８】
2006074770.tif 000066
【図１９】
2006074770.tif 000067
【図２０】
2006074770.tif 000068
【図２１】
2006074770.tif 000069
【図２２】
2006074770.tif 000070
【図２３】
2006074770.tif 000071