(57)【特許請求の範囲】
【請求項１】
圧縮ビットストリームを作成するためにデジタル静止画像をエンコードする方法であって、以下の工程：
ａ）前記デジタル静止画像データを多重解像度画像分解階層に分解する工程であって、前記多重解像度画像はそれぞれ１若しくはそれ以上の変換係数のセットを有し、各変換係数は大きさを有し、且つ前記各変換係数は前記デジタル静止画像のピクセルを代表するものであり、
ｂ）重要度の低いブロックのリスト（ＬＩＢ）、重要度の低いブロックの一時リスト（ＴＬＩＢ）、重要度の高いピクセルのリスト（ＬＳＰ）を空のセットとして初期化する工程であって、前記初期化後及びその後の処理の間、前記重要度の低いブロックのリスト（ＬＩＢ）は、２若しくはそれ以上の変換係数が特定のしきい値において重要度が低いと評価されてなる１若しくはそれ以上の変換係数のブロックおよび未だ重要度が評価されていない１若しくはそれ以上の変換係数のブロックを格納するために使用されるものであり、前記重要度の低いブロックの一時リスト（ＴＬＩＢ）は、全ての変換係数が特定のしきい値において重要度が低いと判断された１若しくはそれ以上の変換係数のブロックを格納するために使用されるものであり、前記重要度の高いピクセルのリスト（ＬＳＰ）は、特定のしきい値について重要度が高いものであると評価された１若しくはそれ以上の変換係数を有するものであり、
ｃ）各多重解像度画像を、変換係数のセットとして前記重要度の低いブロックのリスト（ＬＩＢ）に任意の順序で入力する工程と、
ｄ）最も大きい変換係数に基づいて初期選択しきい値を決定する工程と、
ｅ）前記選択されたしきい値に関連する重要度マップを生成し、クワッドツリーコーディングを使用して前記重要度マップをエンコードする工程であって、前記重要度マップは前記重要度の低いブロックのリスト（ＬＩＢ）内の前記変換係数のブロックの重要度を前記選択されたしきい値との関係で評価することで決定されるものであり、前記評価は前記重要度の低いブロックのリスト（ＬＩＢ）に前記変換係数が入力されている順序に従って実行されるものであり、且つ、前記選択されたしきい値よりも大きいか等しい変換係数が前記選択されたしきい値との関係で重要度が高いと判断されるものであり、
ｆ）圧縮されたビットストリームを生成する工程であって、このビットストリームは前記圧縮ビットストリームの生成方法に関する情報を有するビットストリームヘッダーを有し、前記圧縮ビットストリームはさらに１若しくはそれ以上の重要度マップを有するものである、
を有する方法。
【請求項２】
請求項１記載の方法において、前記重要度マップの決定方法は以下の工程：
ａ）前記重要度の低いブロックのリスト（ＬＩＢ）中に含まれる変換係数のブロックを評価する工程であって、変換係数のブロックの評価はそれらが前記重要度の低いブロックのリスト（ＬＩＢ）に最初に入力された順序に従って実行され、
ｂ）各変換係数の大きさを選択したしきい値と比較しその変換係数のブロックが重要であるかを比較する工程であって、重要度の低い変換係数のみを含むブロックは前記重要度の低いブロックの一時リスト（ＴＬＩＢ）に転送され、
ｃ）前記変換係数のブロックが重要度の高い変換係数１つのみ含む場合に、前記変換係数のブロックを前記重要度の高いピクセルのリスト（ＬＳＰ）に転送する工程、
ｄ）前記変換係数のブロックが２以上の重要度の高い変換係数を有する場合、前記変換係数のブロックを変換係数のサブブロックにサブ分割し、それらのサブブロックを前記重要度の低いブロックのリスト（ＬＩＢ）に入力する工程、
ｅ）前記重要度の低いブロックのリスト（ＬＩＢ）内の前記変換係数の各ブロックに関してその重要度の低いブロックのリスト（ＬＩＢ）が空になるまで工程ａ）〜ｄ）を順次繰り返す工程、
ｆ）前記重要度の高いピクセルのリスト（ＬＳＰ）を使用して出力ビットを生成する工程、
ｇ）前記重要度の低いブロックの一時リスト（ＴＬＩＢ）内に含まれる変換係数のブロックを特定された基準に基づいて配列する工程、
ｈ）前記重要度の低いブロックのリスト（ＬＩＢ）を前記重要度の低いブロックの一時リスト（ＴＬＩＢ）と置き換える工程、
ｉ）前記選択されたしきい値を所定の値に減らし、この新たな選択されたしきい値のための重要度マップを生成する工程であって、前記選択されたしきい値は所定のレベルまで順次減らされていくものである工程
を有するものである。
【請求項３】
請求項１に記載の方法において、前記特定のしきい値のための前記重要度の高いピクセルのリスト中の各変換係数の修正されたビットが、前記特に特定された値のための重要度マップの後で前記ビットストリーム中で決定され且つ一体化されるものであり、修正されたビットは前記変換係数の所定のビットである、方法。
【請求項４】
請求項１に記載の方法において、前記デジタル静止画像の分解は、ウェーブレット変換を利用して行われるものである、方法。
【請求項５】
請求項１記載の方法であって、この方法は、さらに、
異なる領域および異なる解像度からの圧縮データを圧縮ビットストリームにアセンブルすることにより、エンコーダが選択的およびインタラクティブに、ビットバジェット（ｂｉｔ  ｂｕｄｇｅｔ）および圧縮デジタル静止画像の画質を制御できるようにする、多重化プロトコルの工程を有するものである、方法。
【請求項６】
圧縮ビットストリームを作成するデジタル静止画像をエンコードする装置であって、
ａ）前記デジタル静止画像データを多重解像度画像分解階層に分解する手段であって、多重解像度画像はそれぞれ１若しくはそれ以上の変換係数のセットを有し、各変換係数は大きさを有し、且つ前記各変換係数は前記デジタル静止画像のピクセルを代表するものである、手段と、
ｂ）重要度の低いブロックのリスト（ＬＩＢ）と、重要度の低いブロックの一時リスト（ＴＬＩＢ）と、重要度の高いピクセルのリスト（ＬＳＰ）とを空のセットとして初期化する手段であって、前記初期化の後及び処理の間、前記重要度の低いブロックのリスト（ＬＩＢ）は、２若しくはそれ以上の変換係数が特定のしきい値において重要度が低いと評価されてなる１若しくはそれ以上の変換係数のブロックおよび未だ重要度が評価されていない１若しくはそれ以上の変換係数のブロックを格納するために使用されるものであり、前記重要度の低いブロックの一時リスト（ＴＬＩＢ）は、全ての変換係数が特定のしきい値において重要度が低いと評価されてなる１若しくはそれ以上の変換係数のブロックを格納するために使用されるものであり、前記重要度の高いピクセルのリスト（ＬＳＰ）は、特定のしきい値において重要度が高いものであると評価された１若しくはそれ以上の変換係数を格納するものである、手段と、
ｃ）各多重解像度画像を変換係数のセットとして前記重要度の低いブロックのリスト（ＬＩＢ）に任意の順序で入力する手段と、
ｄ）最も大きい変換係数に基づいて初期選択しきい値を決定する手段と、
ｅ）前記選択されたしきい値に関連する重要度マップを生成し、クワッドツリーコーディングを使用して前記重要度マップをエンコードする手段であって、前記重要度マップは前記重要度の低いブロックのリスト（ＬＩＢ）内の前記変換係数のブロックの重要度を前記選択されたしきい値との関係で評価することで決定されるものであり、前記評価の順序は前記重要度の低いブロックのリスト（ＬＩＢ）に前記変換係数が入力されている順序に従って実行されるものであり、且つ、前記選択しきい値よりも大きいか等しい変換係数は前記選択されたしきい値との関係で重要度が高いと判断されるものである、手段と、
ｆ）圧縮されたビットストリームを生成する工程であって、このビットストリームは前記圧縮ビットストリームの生成方法に関する情報を有するビットストリームヘッダーを有し、前記圧縮ビットストリームはさらに１若しくはそれ以上の重要度マップを有するものである、手段と、
を有する装置。
【請求項７】
請求項６記載の装置において、前記重要度マップの決定手段は以下の手段を含む：
ａ）前記重要度の低いブロックのリスト（ＬＩＢ）中に含まれる変換係数のブロックを評価する手段であって、変換係数のブロックの評価はそれらが前記重要度の低いブロックのリスト（ＬＩＢ）に最初に入力された順序に従って実行される、手段と、
ｂ）各変換係数の大きさを選択したしきい値と比較し、その変換係数のブロックが重要であるかを比較する手段であって、重要度の低い変換係数のみを含むブロックは前記重要度の低いブロックの一時リスト（ＴＬＩＢ）に転送される、手段と、
ｃ）前記変換係数のブロックが重要度の高い変換係数１つのみ含む場合に、前記変換係数のブロックを前記重要度の高いピクセルのリスト（ＬＳＰ）に転送する手段と、
ｄ）前記変換係数のブロックが２以上の重要度の高い変換係数を有する場合、前記変換係数のブロックを変換係数のサブブロックにサブ分割し、それらのサブブロックを前記重要度の低いブロックのリスト（ＬＩＢ）に入力する手段と、
ｅ）前記重要度の低いブロックのリスト（ＬＩＢ）内の前記変換係数の各ブロックに関してその重要度の低いブロックのリスト（ＬＩＢ）が空になるまで工程ａ）〜ｄ）を順次繰り返す手段と、
ｆ）前記重要度の高いピクセルのリスト（ＬＳＰ）を使用して出力ビットを生成する手段と、
ｇ）前記重要度の低いブロックの一時リスト（ＴＬＩＢ）内に含まれる変換係数のブロックを特定された基準に基づいて配列する手段と、
ｈ）前記重要度の低いブロックのリスト（ＬＩＢ）を前記重要度の低いブロックの一時リスト（ＴＬＩＢ）と置き換える手段と、
ｉ）前記選択されたしきい値を所定の値に減らし、この新たな選択されたしきい値のための重要度マップを生成する手段であって、前記選択されたしきい値は所定のレベルまで順次減らされていくものである、手段と
を有するものである装置。
【請求項８】
請求項６に記載の装置において、前記特定のしきい値のための前記重要度の高いピクセルのリスト中の各変換係数の修正されたビットが、前記特に特定された値のための重要度マップの後で前記ビットストリーム中で決定され且つ一体化されるものであり、修正されたビットは前記変換係数の所定のビットである、装置。
【請求項９】
請求項６に記載の装置において、前記デジタル静止画像の分解は、ウェーブレット変換を利用して行われるものである。
【請求項１０】
請求項６記載の装置であって、この装置は、さらに、
異なる領域および異なる解像度からの圧縮データを圧縮ビットストリームにアセンブル  異なる領域および異なる解像度からの圧縮データを圧縮ビットストリームにアセンブルすることにより、エンコーダが選択的およびインタラクティブに、ビットバジェット（ｂｉｔ  ｂｕｄｇｅｔ）および圧縮デジタル静止画像の画質を制御できるようにする、多重化プロトコルの手段を有するものである。
【請求項１１】
圧縮ビットストリームをデコードしてデジタル静止画像を生成する方法であって、以下の工程：
ａ）前記圧縮ビットストリームと関連付けれたビットストリームヘッダーをデコードする工程であって、前記ビットストリームヘッダーは前記圧縮したビットストリームの生成方法に関する情報を有し、
ｂ）前記デコードされたビットストリームヘッダーに基づいて重要度の低いブロックの最初のリスト（ＬＩＢ）を生成する工程、
ｃ）重要度の高いピクセルの空のリスト（ＬＳＰ）を初期化する工程と、
ｄ）前記デコードされたビットストリームヘッダーに基づいてウェーブレット変換配列を初期化する工程、
ｅ）前記デコードされたビットストリームヘッダーに基づいて現在のしきい値を生成する工程、
ｆ）前記現在のしきい値に基づいて前記重要度の低いブロックのリスト（ＬＩＢ）からクワッドツリーエンコードされた重要度マップをデコードする工程、
ｇ）前記重要度の高いピクセルのリスト（ＬＳＰ）および前記重要度の低いブロックのリスト（ＬＩＢ）を工程ｆ）の前記デコードに従って修正する工程、
ｈ）ウェーブレット係数の前記修正ビットをデコードする工程であって、前記重要度の高いピクセルのリスト（ＬＳＰ）に移動した全ピクセルの係数が、前記デコードされた修正ビットに基づいて更新され、
ｉ）前記現在のしきい値を減らしながら、工程ｆ）〜ｉ）を繰り返し、前記減らされたしきい値を使用して、前記圧縮ビットストリームの全ての重要度マップがデコードされるまで更なる重要度マップをデコードする工程、
ｊ）ウェーブレット係数の配列を構築する工程、
ｋ）逆ウェーブレット変換を使用して１若しくはそれ以上のデコードされた重要度マップからデジタル静止画像を再構築する工程
を有する方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に画像コーディングに関し、より正確にはデジタル画像の圧縮および解凍に関する。
【０００２】
【従来の技術】
マルチメディアコンピューティングの到来は、高パフォーマンスの画像圧縮システムに対する需要をもたらした。近年では、ウェーブレット変換が主流となり、画像圧縮コーディングの基礎技術として使われている。ウェーブレット変換は階層サブバンド分解としても知られ、図１に示すように、オリジナル画像に対し多重解像度の分解階層（ＭＤＨ）表現を生成する。ＭＤＨデータの作成時に生成されるウェーブレット変換係数を効率的にコーディングすることにより、１ビット／ピクセル未満のビットレートが実現可能となる。
【０００３】
ウェーブレット変換で生成されるウェーブレット係数の最も重要かつ有益な特性は、この係数の大部分の絶対値が非常に小さい値となり、これらはスカラー定量化を行なうとゼロになることである。多数の画像処理でのウェーブレット変換係数の重要度と意義は、その絶対値と所定のしきい値との関係に見られる。ウェーブレット係数は、その絶対値と特定のしきい値との大小関係により、重要であるかそうでないかが決定される。ウェーブレット係数のセットの重要度は、「重要度マップ」を使って集合的に決定される。「重要度マップ」は、重要な係数の位置を記録したビットマップである。ビットバジェットの大部分は重要度マップのエンコーディングに使われる可能性がある。したがって、画像コーディングシステムの圧縮パフォーマンスは、重要度マップコーディングの効率に大きく依存する。
【０００４】
米国特許第５４１２７４１号において、Ｊ．  Ｍ．  Ｓｈａｐｉｒｏは埋込みゼロツリーウェーブレットアルゴリズム、略称「ＥＺＷ」を開示している。本発明をより効率的に実現した階層ツリーにおけるセットパーティショニング（ｓｅｔ  ｐａｒｔｉｔｉｏｎｉｎｇ  ｉｎ  ｈｉｅｒａｒｃｈｉｃａｌ  ｔｒｅｅｓ、略称「ＳＰＩＨＴ」）は、Ｓａｉｄ  ｅｔ  ａｌ．により"Ａ  Ｎｅｗ，  Ｆａｓｔ，  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｉｍａｇｅ  Ｃｏｄｅｃ  Ｂａｓｅｄ  ｏｎ  Ｓｅｔ  Ｐａｒｔｉｔｉｏｎｉｎｇ  ｉｎ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｔｒｅｅｓ"，  Ａ．  Ｓａｉｄ  ａｎｄ  Ｗ．  Ｐｅａｒｌｍａｎ，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  Ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ，  Ｖｏｌ．  ６，  Ｎｏ．  ３，  Ｊｕｎｅ，  １９９６．で開示されている。
【０００５】
その特有な単純さと、他の技術と比較したパフォーマンスの効率および競争力とにより、ＥＺＷベースのコーディングは画像圧縮研究分野で最高技術の１つと考えられている。さらに、この技術は新世代国際標準画像（ＪＰＥＧ  ２０００）およびビデオ（ＭＰＥＧ  ４）コーディングの候補技術として選ばれている。
【０００６】
ＥＺＷベースのコーディング技術は、３つの基本的な方法論的要素から構成されている。その第１要素は振幅によるＭＤＨデータの部分的な順序付けである。デコーダにおいて、比較的大きな振幅を持つＭＤＨデータが最初に送信されるよう順序付け情報を複製することにより、画像を再構築する際、より大量の情報を持つ変換係数がより高い確率で利用できるようになる。通常、この部分的な順序付けは桁数の異なる数値を持つしきい値のセットを使って実行される。第２の要素は、埋込みを定量化するための、修正ビットの順序付け済みビット面の送信である。第３の要素は、重要度マップをコーディングするための、ＭＤＨデータの振幅間のサブバンド相関関係の利用である。
【０００７】
前記ゼロツリー構造はＭＤＨデータのコーディングにおいて効果的なことが実証されたが、これは必ずしもデータセット固有の規則性を活用する唯一の論理的方法ではない。ＥＺＷは、結果として得られるコードのコンパクトさを考慮した場合には最も効率的な表現ではなく、また、ゼロツリー方法の構造は完全に閉じているため、独立処理または並列処理が不可能である。ゼロツリーでコード化された、ＭＰＥＧ−４オブジェクトなどのビジュアルオブジェクトの多重層表現の場合は、ベース層のみが独立にデコードされ、すべてのエンハンスメント層のデコーディングはそれ以前にデコードされた層の情報に依存する。すなわち、オブジェクトのゼロツリー表現は、独立したデコードを本質的に不可能にしてしまう。この不可分性により、ビットエラーも起りやすくなる。潜在的には一度でもビットエラーが起ると、各後続解像度レベルでの解釈を経たのち、デコーダが失敗することもあり、結果的にはゼロツリー表現の閉じた構造が新たなコーディング方法または機能の追加を困難にする。
【０００８】
【課題を解決するための手段】
本発明は、高度な圧縮パフォーマンスにより、グレースケール画像データおよびカラー画像データを圧縮する方法である。本発明の目的は、ウェーブレット変換係数の重要度情報を圧縮およびコード化する、効率的かつ高速な方法およびシステムを提供することにある。本発明のさらなる目的は、スケーラブルで領域ベースでアクセスが可能な、エラーに対する堅牢性を持つ、独立してデコードが可能な圧縮ビットストリームを作成するための方法およびシステムを提供することにある。本発明は、ハードウェアでの処理実行に高度な並行性をもたらす、論理的に単純で高速なコーディング方法を提供する。本発明のシステムにより作成されたビットストリームでは、すべてのサブバンドブロックが独立してエンコードされており、１スケールでのエラーが他スケールへのエラーにつながらないため、従来技術と比べ、ビットエラーに対しより高い堅牢性を持つ。
【０００９】
本発明の観点によれば、スケーラブルでコンテントへのアクセスが可能な圧縮ビットストリームを作成するための、デジタル静止画像をエンコーディングおよびデコーディングの方法であって、生画像データを分解し、多重解像度サブイメージの階層内に順序付ける工程と、重要度の初期しきい値を設定し、重要度インデックスを作成する工程と、重要でないブロックの初期リストを決定する工程と、クワッドツリー表現を使って重要なマップをエンコードすることにより、重要な係数のリストを形成する工程と、再帰的にしきい値を低減し、各しきい値についてエンコード工程を繰り返す工程と、重要な係数の修正ビットを送信する工程とを有する、デジタル静止画像をエンコーディングおよびデコーディングの方法が提供される。
【００１０】
本発明の異なる他の観点によれば、スケーラブルでコンテントへのアクセスが可能な圧縮ビットストリームを作成するための、デジタル静止画像を領域ベースでエンコードおよびデコードする装置であって、生画像データを分解し、多重解像度サブイメージの階層内に順序付ける手段と、重要度の初期しきい値を設定し、重要度インデックスを作成する手段と、重要でないブロックの初期リストを決定する手段と、クワッドツリー表現を使って重要なマップをエンコードすることにより、重要な係数のリストを形成する手段と、再帰的にしきい値を低減し、各しきい値についてエンコード工程を繰り返す手段と、重要な係数の修正ビットを送信する手段とを有する、デジタル静止画像を領域ベースでエンコードおよびデコードする装置が提供される。
【００１１】
本発明のさらに異なる他の観点によれば、スケーラブルでコンテントへのアクセスが可能な圧縮ビットストリームを作成するための、デジタル静止画像をデコードする方法であって、ビットストリームヘッダをデコードする工程と、初期しきい値を決定し、初期重要ピクセルと、重要でないビットと、ウェーブレット係数との配列を決定する工程と、重要度マップをデコードする工程と、重要度リストを修正し、各しきい値レベルについて修正ビットをデコードする工程と、ウェーブレット係数配列を再構築する工程と、逆ウェーブレット変換を実行する工程と、画像を再構築する工程とを有するデジタル静止画像をデコードする方法が提供される。
【００１２】
【発明の実施の形態】
好適な実施例に係るウェーブレット変換が画像の分解に適用されると、その結果４つの周波数サブバンドでの信号が得られる。これらの周波数サブバンドは、高水平高垂直（または「ＨＨ」）周波数サブバンド、高水平低垂直（または「ＨＬ」）周波数サブバンド、低水平高垂直（または「ＬＨ」）周波数サブバンド、および低水平低垂直（または「ＬＬ」）周波数サブバンドである。ＬＬサブバンドは、さらにウェーブレット変換され、後続セットであるＨＨサブバンド、ＨＬサブバンド、ＨＬサブバンド、およびＬＬサブバンドの作成に使われる。この手順は、オリジナル画像の多重解像度分解階層（ＭＤＨ）を作成するため、再帰的に行われる。図１に示すように、この手順では３レベルの変換が適用される。言うまでもなく、サブバンド分解が任意の回数だけ適用可能なことは当該技術における技術者にとって自明である。
【００１３】
図１では、最低の周波数サブバンド、すなわち最も粗い解像度スケールを提供するサブバンドが、左上のブロックＬＬ３（１０１）で示されている。最高の周波数サブバンド、すなわち最高の解像度スケールを提供するサブバンドは、ブロックＨＬ  １（１０２）、ＬＨ１（１０３）、およびＨＨ１（１０４）である。
【００１４】
図１ａは、本発明によるテスト画像「リナ」の３層ウェーブレット分解を示す図である。オリジナルの画像１ａ０１が分解された画像ｌａ０２では、３レベルの解像度が見られる。ブロック１ａ０３に示された高周波数データＨＨ１（１０４）では、最も詳細な画像が得られていることがわかる。
【００１５】
ウェーブレット変換後、各ピクセルはウェーブレット変換係数により表現される。本発明の好適な実施例では、これらの係数はそれぞれ固定小数点のバイナリ形式（最も典型的には１６ビット未満）で記述され、整数として取り扱われる。図２は、一般的なウェーブレット変換係数のバイナリ表現を示す図である。このシステムでは、第１ビット２０１は符号（正または負）の記述のみ使われる。符号ビット後の第１非ゼロビット２０２は先行１ビットまたはＬＯＢと呼ばれる。ＬＯＢの位置は係数の絶対値により決定される。すなわち、係数の値が大きいほど、その位置は符号ビットに近くなる。ＬＯＢ２０２以後の全ビットは修正ビット２０３と呼ばれる。
【００１６】
ウェーブレット変換で係数が生成され、これらがバイナリ表現で記述されると、３つのリストが初期化される。その第１リストは重要度の高いピクセルのリストまたはＬＳＰと呼ばれる。ＬＳＰの各エントリはＭＤＨ面の各々のピクセルに対応しており、一対の座標（ｉｊ）により識別される。この時点で各々のピクセルの重要度は未決定であるため、ＬＳＰは空のリストとして初期化される。第２のリストは重要でないブロックのリストまたはＬＩＢと呼ばれる。このリストのエントリは、ピクセル内で測定された座標のブロックの左上角のピクセル座標（ｉ１，ｊ１）と、そのブロックの幅および高さ（ｉ２，ｊ２）とからなる。ｉ２＝ｊ２＝１の場合、ＬＩＢの各エントリは各々のピクセルからなる各ブロックを表している。第１回の初期化時、ＴＬＩＢ（一時ＬＩＢ）は空である。このリストが初期化されると、各サブバンドブロックがＬＩＢのエントリとなる。初期ＬＩＢにおけるエントリは任意に順序付けされるが、サブバンドエントリのデフォルト順序はＬＬ３、ＬＨ３、ＨＬ３、ＨＨ３、ＬＨ２、ＨＬ２、ＨＨ２、ＬＨ１、ＨＬ１、ＨＨ１である。図４はＬＩＢにおけるＬＳＰおよびデフォルトエントリの作成に関する意思決定樹図形である。
【００１７】
リスト作成における次のステップは、係数の重要度を決定するためのしきい値の計算である。ウェーブレット変換後には、すべての変換係数の最大値「Ｍ」が計算されなければならない。当核技術における技術者にとっては、効率的に実施されたＭＤＨからの係数であればほとんど比較的低い値を持つ事実はよく知られている。前記Ｍが決定されたら、２Ｎ≦Ｍ<２Ｎ＋１の条件を満たす値Ｎが算出される。初期しきい値は２Ｎに設定され、多様なＮ値のセットはしきい値インデックスと呼ばれる。これらのしきい値は、次にビット数の便宜上２の累乗分で低減される。各しきい値では、前記係数をしきい値と比較することにより、重要度マップが作成される。しきい値より大きい係数は、値１が与えられて重要な係数のマップに加えられる。しきい値未満の係数は、値ゼロが与えられて重要な係数のマップ加えられる。各しきい値についてのバイナリ画像形式での重要度マップは、このようにして作成される。
【００１８】
ＬＩＢは前述のようにまずＭＤＨのサブバンドブロックにより作成されるため、本発明の好適な実施例では、まず重要度データのクワッドツリーエンコーディングが行われる。ブロックが与えられると、このブロックに含まれる重要な係数の数が数えられる。その数がゼロの場合、このブロックの座標が識別され、ＴＬＩＢに追加される。このブロック（「親ブロック」）に重要な係数が少なくとも１つある場合、このブロックは「子ブロック」と呼ばれる４つの同サイズのサブブロックに分けられ、ＬＩＢから除去される。重要な係数の数が１で、ブロックのサイズが１である場合、このエントリは単一係数となり、その座標はＬＳＰへ移動される。
【００１９】
サブブロックの処理法は２つある。第１の方法は、深度第１クワッドツリーコーディングとして知られており、ＬＩＢにおいて４つのサブブロックをそれらの親ブロックの直後の位置に挿入するものである。これら４つの子ブロックは、直ちにその重要度について調べられ、この処理は再分割がこれ以上できなくなるまで再帰的に行われる。このブロックで重要な係数がすべて見出され、ＬＳＰへ移動されたら、その現在のエントリのコーディングは完了する。次に、この工程はＬＩＢ内の次のブロックについて行われる。
【００２０】
サブブロック処理の第２の方法は、幅第１クワッドツリーコーディングと呼ばれ、これら４つのサブブロックをＬＩＢの末尾に追加し、そこで同じパスが終了するまでそれらのサブブロックが評価されるものである。幅第１コーディングの工程では、次のレベルのブロックが現れるまで、同レベルの全親ブロックが処理される。
【００２１】
１レベルの重要度において処理中のＬＩＢに含まれるエントリがすべて処理されると、ＴＬＩＢ内のエントリはブロックのサイズに応じて再順序付けされる。この順序付けでは、より大きいブロックが次のしきい値について最初に処理されるよう、ブロックはサイズの小さい順に配列される。重要度の高いピクセルに隣接する大部分のピクセルが、その時点のしきい値と比べて重要でない場合、ピクセルレベルエントリとしてＴＬＩＢへ移動される。隣接する係数間の相関関係により、これらの隣接ピクセルは、次のしきい値レベルで重要になる可能性が高い。ビットバジェットが非常に限られている場合は、貴重なビットが大きなブロックから重要な係数を見つけるために使われて、ピクセルレベルの重要な係数が失われないよう、これらのピクセルレベルブロックが優先されなければならない。このように、ＴＬＩＢの再順序付けは、少ないビット数でより重要な係数をエンコーディングする際に役立つ。参考までに補足すると、この再順序付けスキームを使った場合、より高いＰＳＮＲが達成されることが実験により知られている。このクワッドツリー工程における最終ステップは、この次に行われる次レベルの重要度についてのスキャン用にＬＩＢをＴＬＩＢで置換し、ＴＬＩＢを空にリセットすることである。ただし、次のしきい値に移行する前に、重要な係数についての修正データが回収される。
【００２２】
図７は画像データのクワッドツリーエンコーディングにおける修正パスを示す図である。しきい値２Ｎ＋１（｜Ｃｉ．ｊ｜≦２Ｎ＋１）で重要度の高いピクセルのリスト（ＬＳＰ）の係数エントリにおいて、そのＮ番目のビットが出力される。そして、次のＬＳＰのエントリに移行する。図３に示すようにまた前述のように、前記修正パスの後、そのしきい値は２で割られ、この新しいしきい値と更新したＬＩＢ（前ＴＬＩＢ）で前記の工程が繰り返される。
【００２３】
前記工程で作成されたビットストリームの算術的コーディングは必須ではない。ビットストリームに含まれるデータには、クワッドツリーでコードされた重要度マップエンコーディングビットと、完全に埋込みコードを形成する修正ビットとの２タイプがある。このビットストリームには多数の編成法がある。理論的には、重要度マップデータおよび修正ビットデータはいかなる順序で配置されてもよい。この編成は、ユーザ指定の優先順位に従いデータを圧縮するマルチプレクサにより行われる。データ圧縮のデフォルト順序は図９に示すとおりで、これにより高ＰＳＮＲを追求する場合に最適な結果が得られる。
【００２４】
デコーディングの第１段階では、開始しきい値インデックスＮと、ウェーブレットスケールの数と、画像サイズとがヘッダビットから再構築される必要がある。この情報に基づき、初期ＬＳＰおよび初期ＴＬＩＢは空に設定された状態で、ＬＩＢを初期化し、これに入力を行なうことができる。ウェーブレット係数の初期値はすべてゼロに設定されている。
【００２５】
デコーディングの主要工程は図１１に示すとおりで、与えられたしきい値レベルでの重要度マップは受け取られたビットに基づいてデコードされる。その時点のしきい値インデックスをＮとすると、この工程ではまずＬＩＢのエントリがロードされ、ビットストリームから１ビットが読み込まれる。そのビット値がゼロの場合、このエントリはＴＬＩＢに移動される。その代替処理では、エントリのサイズが１であるかどうかが確認される。そのエントリが単一ピクセルである場合は、その位置でウェーブレット係数が２Ｎ＋２Ｎ−１に更新され、もう１つのビットが読み込まれる。そのビットが１である場合、ウェーブレット係数はその位置で−（２Ｎ＋２Ｎ−１）に更新される。このエントリは次にＬＳＰへ移動される。このエントリは、ピクセルレベルでない場合、同サイズの４サブブロックに分解される。エンコーダで深度第１方法が使われている場合（この使用方法の決定と、どの情報をビットストリームのヘッダ部分に含めるかの決定はエンコーダで行われる）、サブブロックはその親ブロックの位置でＬＩＢへ挿入される。エンコーダで幅第１方法が使われている場合、サブブロックはＬＩＢの末尾へ追加される。ＬＩＢ内の全エントリがデコードされた時点で、ＬＩＢはＴＬＩＢで置換され、ＬＩＢは次のしきい値レベルで処理される。ＬＩＢはエンコーディングと同じ規則で再順序付けされ、ＴＬＩＢは空としてリセットされる。
【００２６】
デコーディングの修正パスでは、ＬＳＰへ移動されたすべての係数は、次の規則に従い更新される。すなわち、係数が負の場合、受け取られたビットが０であれば２Ｎ−１を足し、受け取られたビットが１であれば２Ｎ−１を差し引く。逆に係数が正の場合は、受け取られたビットが１であれば２Ｎ−１を足し、受け取られたビットが０であれば、２Ｎ−１を差し引く。
【００２７】
本発明のエンコーディング工程またはデコーディング工程では、どの時点でもビット消費を計算してビットバジェットと比較し、必要に応じて工程を中断することができる。このように、ビットストリームに算術的コーディングを行なわなければ、ビットレートの制御は精確かつ容易に行なえる。算術的コーディングを使った場合、結果として得られるビットストリームは通常望ましい長さより短くなる。
【図面の簡単な説明】
【図１】  ３層ウェーブレット分解の模式図。
【図１ａ】  テスト画像「リナ」に適用された３層ウェーブレット分解を示す図。
【図２】  整数形式に変換された後のウェーブレット変換係数のバイナリ表現を示す図。
【図３】  本発明に係る画像エンコーダのブロック図。
【図４】  リストＬＳＰおよびリストＬＩＢの初期化工程を示す図。
【図５】  初期のしきい値を決定するアルゴリズムを示す図。
【図６】  重要度マップのクワッドツリーコーディングを示すフローチャート。
【図７】  修正工程を示すフローチャート。
【図８】  マルチプレクサを示すブロック図。
【図９】  データ圧縮のデフォルト順序を示す図。
【図１０】  本発明に係る画像デコーダを示すブロック図。
【図１１】  重要度マップのクワッドツリーデコーディングを示すフローチャート。
【図１】
0003970521.tif 000002
【図１ａ】
0003970521.tif 000003
【図２】
0003970521.tif 000004
【図３】
0003970521.tif 000005
【図４】
0003970521.tif 000006
【図５】
0003970521.tif 000007
【図６】
0003970521.tif 000008
【図７】
0003970521.tif 000009
【図８】
0003970521.tif 000010
【図９】
0003970521.tif 000011
【図１０】
0003970521.tif 000012
【図１１】
0003970521.tif 000013