(57)【要約】本発明は、カラー画像データの圧縮に関する。ハードディシジョンピクセルマッピングとソフトディシジョンピクセルマッピングとの組み合わせは、計算上の複雑性を低く維持し、例えばＧＩＦ／ＰＮＧデコーダのような標準的なデコーダとの互換性を維持する一方で、量子化ひずみと圧縮率とを同時に処理するように用いられる。本発明の第一の局面にしたがうと、データ処理システムを用いることにより、Ｎ個の異なる色を有するデジタル化されたカラー画像から、デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造パーティションを形成する方法が提供される。
2007534239.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムを用いることにより、Ｎ個の異なる色を有するデジタル化されたカラー画像から、該デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造のパーティショニングを形成する方法であって、ＭはＮ以下であり、Ｎ個の異なる色における各色は、カラーパレットにおける複数のＰビットのバイトによってデジタル的に表現され、各ＰビットのバイトにおけるＰビットは、最上位から最下位へと順序付けられており、該方法は、
（ａ）該Ｎ個の異なる色の全てを含むルートノードを提供するステップと、
（ｂ）該ルートノードにリンクされた兄弟ノードの第１のレベルを提供するステップであって、該Ｎ個の異なる色における各色は、該複数のＰビットのバイトにおける各Ｐビットのバイトの第１のビットの値に基づいて、該データ処理システムにより、兄弟ノードの該第１のレベルにおける関連のあるノードに割り当てられる、ステップと、
（ｃ）１色よりも多い色を含むノードのｋ番目のレベルにおける各ノードに対し、（ｋ＋１）番目のレベルの複数の兄弟ノードを提供するステップであって、そのノードにおける各色は、該Ｎ個の異なる色の各色に対してその色のみを含む異なるリーフノードが存在するように、その色に対する該複数のＰビットのバイトにおける各Ｐビットのバイトの（ｋ＋１）番目のビットの値に基づいて、該データ処理システムにより、該（ｋ＋１）番目のレベルの該複数の兄弟ノードにおける関連のある兄弟ノードに割り当てられる、ステップと、
（ｄ）Ｍ個のリーフノードのみが残されるまで、リーフノードを選択および統合するステップと
を含む、方法。
【請求項２】
ステップ（ｄ）は、Ｍ個のリーフノードのみが残されるまで、リーフ兄弟モードのペアを繰り返し選択および統合するステップを含む、請求項１に記載の方法。
【請求項３】
ステップ（ｄ）は、Ｍ個のリーフノードのみが残されるまで、その統合が最小のエントロピー制約コストインクリメントを有するリーフ兄弟モードのペアを繰り返し選択および統合するステップを含む、請求項１に記載の方法。
【請求項４】
ステップ（ｄ）は、統合前エントロピー制約総コストと統合後エントロピー制約総コストとの差を計算せずに、最小のエントロピー制約コストインクリメントを計算するステップを含む、請求項３に記載の方法。
【請求項５】
前記Ｎ個の異なる色の各色に対する前記複数のＰビットのバイトは、複数の原色の各原色に対するＰビットのバイトを含む、請求項１に記載の方法。
【請求項６】
前記複数の原色は、赤、緑、青を含む、請求項３に記載の方法。
【請求項７】
Ｍ個の異なる色を有するデジタル化された新しいカラー画像を形成するステップをさらに含み、ステップ（ｄ）が完了した後に、該Ｍ個の異なる色と前記Ｍ個のリーフノードとの間には、１対１の対応関係が存在する、請求項１に記載の方法。
【請求項８】
Ｎ個の異なる色を有するデジタル化されたカラー画像から、該デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造のパーティショニングを形成するデータ処理システムであって、ＭはＮ以下であり、Ｎ個の異なる色における各色は、カラーパレットにおける複数のＰビットのバイトによってデジタル的に表現され、各ＰビットのバイトにおけるＰビットは、最上位から最下位へと順序付けられており、該データ処理システムは、
（ａ）ノード生成手段であって、
（ｉ）該Ｎ個の異なる色の全てを含むルートノードを提供するステップと、
（ｉｉ）該ルートノードにリンクされた兄弟ノードの第１のレベルを提供するステップであって、該Ｎ個の異なる色における各色は、該複数のＰビットのバイトにおける各Ｐビットのバイトの第１のビットの値に基づいて、兄弟ノードの該第１のレベルにおける関連のあるノードへ割り当てられる、ステップと、
（ｉｉｉ）１色よりも多い色を含むノードのｋ番目のレベルにおける各ノードに対し、（ｋ＋１）番目のレベルの複数の兄弟ノードを提供するステップであって、そのノードにおける各色は、該Ｎ個の異なる色の各色に対してその色のみを含む異なるリーフノードが存在するように、その色に対する該複数のＰビットのバイトにおける各Ｐビットのバイトの（ｋ＋１）番目のビットの値に基づいて、該（ｋ＋１）番目のレベルの該複数の兄弟ノードにおける関連のある兄弟ノードに割り当てられる、ステップと
のための、ノード生成手段と、
（ｂ）Ｍ個のリーフノードのみが残されるまで、リーフノードを選択および統合するノード統合手段と
を含む、データ処理システム。
【請求項９】
前記ノード統合手段は、Ｍ個のリーフノードのみが残されるまで、リーフ兄弟モードのペアを繰り返し選択および統合するように動作することが可能である、請求項８に記載のデータ処理システム。
【請求項１０】
リーフノードのペアを潜在的に統合するために、そのような統合の各々に対するエントロピー制約コストインクリメントを計算するためのコスト計算手段をさらに含み、
該コスト計算手段は、前記ノード統合手段にリンクされており、該ノード統合手段は、Ｍ個のリーフノードのみが残されるまで、該コスト計算手段で決定されるような最小のエントロピー制約コストインクリメントをその統合が有するリーフ兄弟モードのペアを繰り返し選択および統合するように動作することが可能である、請求項８に記載のデータ処理システム。
【請求項１１】
前記コスト計算手段は、統合前総エントロピー制約コストと統合後総エントロピー制約コストとの差を計算せずに、最小のエントロピー制約コストインクリメントを計算するように動作することが可能である、請求項１０に記載のデータ処理システム。
【請求項１２】
前記Ｎ個の異なる色の各色に対する前記複数のＰビットのバイトは、複数の原色の各原色に対するＰビットのバイトを含む、請求項８に記載のデータ処理システム。
【請求項１３】
前記複数の原色は、赤、緑、青を含む、請求項１０に記載のデータ処理システム。
【請求項１４】
Ｍ個の異なる色を有するデジタル化された新しいカラー画像を形成するステップをさらに含み、ステップ（ｄ）が完了した後に、該Ｍ個の異なる色と前記Ｍ個のリーフノードとの間には、１対１の対応関係が存在する、請求項８に記載のデータ処理システム。
【請求項１５】
Ｎ個の異なる色を有するデジタル化されたカラー画像から、該デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造のパーティショニングを形成するように、コンピュータシステム上で用いられるコンピュータプログラム製品であって、ＭはＮ以下であり、Ｎ個の異なる色における各色は、カラーパレットにおける複数のＰビットのバイトによってデジタル的に表現され、各ＰビットのバイトにおけるＰビットは、最上位から最下位へと順序付けられており、該コンピュータプログラム製品は、
記録媒体と、
該媒体に記憶された手段であって、
（ａ）該Ｎ個の異なる色の全てを含むルートノードを提供するステップと、
（ｂ）該ルートノードにリンクされた兄弟ノードの第１のレベルを提供するステップであって、該Ｎ個の異なる色における各色は、該複数のＰビットのバイトにおける各Ｐビットのバイトの第１のビットの値に基づいて、兄弟ノードの該第１のレベルにおける関連のあるノードに割り当てられる、ステップと、
（ｃ）１色よりも多い色を含むノードのｋ番目のレベルにおける各ノードに対し、（ｋ＋１）番目のレベルの複数の兄弟ノードを提供するステップであって、そのノードにおける各色は、該Ｎ個の個別の色の各色に対してその色のみを含む異なるリーフノードが存在するように、その色に対する該複数のＰビットのバイトにおける各Ｐビットのバイトの（ｋ＋１）番目のビットの値に基づいて、該（ｋ＋１）番目のレベルの該複数の兄弟ノードにおける関連のある兄弟ノードに割り当てられる、ステップと、
（ｄ）Ｍ個のリーフノードのみが残されるまで、リーフノードを選択および統合するステップと
を実行するように該コンピュータシステムに命令する、手段と
を含む、コンピュータプログラム製品。
【請求項１６】
ステップ（ｄ）は、Ｍ個のリーフノードのみが残されるまで、リーフ兄弟モードのペアを繰り返し選択および統合するステップを含む、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
ステップ（ｄ）は、Ｍ個のリーフノードのみが残されるまで、その統合が最小のエントロピー制約コストインクリメントを有するリーフ兄弟モードのペアを繰り返し選択および統合するステップを含む、請求項１５に記載のコンピュータプログラム製品。
【請求項１８】
ステップ（ｄ）は、統合前総エントロピー制約コストと統合後総エントロピー制約コストとの差を計算せずに、最小のエントロピー制約コストインクリメントを計算するステップを含む、請求項１５に記載のコンピュータプログラム製品。
【請求項１９】
前記Ｎ個の異なる色の各色に対する前記複数のＰビットのバイトは、複数の原色の各原色に対するＰビットのバイトを含む、請求項１５に記載のコンピュータプログラム製品。
【請求項２０】
前記複数の原色は、赤、緑、青を含む、請求項１５に記載のコンピュータプログラム製品。
【請求項２１】
Ｍ個の異なる色を有するデジタル化された新しいカラー画像を形成するステップをさらに含み、ステップ（ｄ）が完了した後に、該Ｍ個の異なる色と前記Ｍ個のリーフノードの間には、１対１の対応関係が存在する、請求項１５に記載のコンピュータプログラム製品。
【請求項２２】
共にｎ個のピクセルで定義される、オリジナルのデジタル化されたカラー画像から導出された新しいデジタル化されたカラー画像に対し、ピクセルマッピングを表す新しいインデックスシーケンスと、カラーパレットを表す新しい出力関数とを導出する方法であって、該オリジナルのデジタル化されたカラー画像は、該ｎ個のピクセルに割り当てられたＮ個の異なる色によって提供されており、該新しいデジタル化されたカラー画像は、該ｎ個のピクセルに割り当てられたＭ個の異なる色によって提供されており、該新しいインデックスシーケンスは、該ｎ個のピクセルを表すためのｎ個のインデックスメンバーを有しており、該新しい出力関数は、該ｎ個のインデックスメンバーを該Ｍ個の色にマッピングするためのものであり、該方法は、
（ａ）該オリジナルのデジタル化されたカラー画像におけるピクセルの位置に関わらず、該オリジナルのデジタル化されたカラー画像における各ピクセルの色に基づいて、該オリジナルのデジタル化されたカラー画像における全てのピクセルをＭ個の互いに素なクラスタに分割することにより、第１の新しいインデックスシーケンスを提供するステップであって、ＭはＮ以下である、ステップと、
（ｂ）該Ｍ個の互いに素なクラスタにおけるピクセルへの該Ｍ個の異なる色の１対１のマッピングを提供するために、第１の新しい出力関数を提供するステップと、
（ｃ）該第１の新しいインデックスシーケンスの各メンバーに対し、該第１の新しい出力関数によってそのメンバーに割り当てられている色の値が、該第１の新しい出力関数によって該第１の新しいインデックスシーケンスの少なくとも１つの他のメンバーに割り当てられている色の値にどのように相関付けられているかに基づいて、該新しいインデックスシーケンスと該新しい出力関数とをそれぞれ提供するために、該第１の新しいインデックスシーケンスと該第１の新しい出力関数とにソフトディシジョン最適化プロセスを適用するステップと
を含む、方法。
【請求項２３】
前記新しいインデックスシーケンスは、前記新しいデジタル化されたカラー画像における各ピクセルに対し、該新しいインデックスシーケンスと前記新しい出力関数とによって該ピクセルに割り当てられた前記色の値が、該カラー画像の該ピクセルの位置に依存するように、ソフトディシジョンピクセルマッピングを提供する、請求項２２に記載の方法。
【請求項２４】
ステップ（ｃ）は、反復的なソフトディシジョン最適化プロセスを適用し、各反復後に、前記オリジナルのデジタル化されたカラー画像の圧縮およびひずみを表すコスト関数におけるインクリメントの低下を決定するステップ
を含み、該インクリメントの低下が選択された閾値を下回るときに、ステップ（ｃ）が終了し、前記新しいインデックスシーケンスと前記新しいカラーマッピングとが決定される、請求項２２に記載の方法。
【請求項２５】
ステップ（ｃ）は、
（ｉ）カウンタｋを１に設定するステップと、
（ｉｉ）ｋ番目のインデックスシーケンスに対し、全ての考えられるインデックスシーケンスにわたり、ｋ番目の出力関数とｋ番目の推移確率関数に対して前記コスト関数を最適化することにより、（ｋ＋１）番目のインデックスシーケンスを決定するステップと、
（ｉｉｉ）該（ｋ＋１）番目のインデックスシーケンスから（ｋ＋１）番目の出力関数と（ｋ＋１）番目の推移確率関数とを決定するステップと、
（ｉｖ）該（ｋ＋１）番目のインデックスシーケンスと、該（ｋ＋１）番目の出力関数と、該（ｋ＋１）番目の推移確率関数とから、（ｋ＋１）番目のコストを決定するステップと、
（ｖ）該（ｋ＋１）番目のコストと該ｋ番目のコストとの間の（ｋ＋１）番目のコスト差を計算し、該（ｋ＋１）番目のコスト差が選択された閾値を下回るときに、新しいインデックスシーケンスと新しい出力関数として、該（ｋ＋１）番目のインデックスシーケンスと該（ｋ＋１）番目の出力関数とをそれぞれ選択し、そうでない場合は、ｋを１だけ増加させ、サブステップ（ｉｉ）から（ｖ）を繰り返すステップと
を含む、請求項２４に記載の方法。
【請求項２６】
ステップ（ｉｉ）において、前記所定のｋ番目の出力関数とｋ番目の推移確率関数とに対し、全ての考えられるインデックスシーケンスにわたり、前記コスト関数を最適化することによって、前記（ｋ＋１）番目のインデックスシーケンスを決定するステップは、ビタビアルゴリズムを用いることを含む、請求項２５に記載の方法。
【請求項２７】
ステップ（ａ）は、前記Ｍ個の互いに素なクラスタをＭ’個の互いに素なグループにグループ分けするステップをさらに含み、Ｍ’はＭ未満であり、
ステップ（ｃ）は、該Ｍ’個の互いに素なグループに関するソフトディシジョン最適化プロセスを適用するステップを含む、請求項２６に記載の方法。
【請求項２８】
前記コスト関数は、ＭおよびＭ’の双方に依存する、請求項２７に記載の方法。
【請求項２９】
共にｎ個のピクセルで定義される、オリジナルのデジタル化されたカラー画像から導出された新しいデジタル化されたカラー画像に対し、ピクセルマッピングを表す新しいインデックスシーケンスと、カラーパレットを表す新しい出力関数とを導出するデータ処理システムであって、該オリジナルのデジタル化されたカラー画像は、該ｎ個のピクセルに割り当てられたＮ個の異なる色によって提供されており、該新しいデジタル化されたカラー画像は、該ｎ個のピクセルに割り当てられたＭ個の異なる色によって提供されており、該新しいインデックスシーケンスは、該ｎ個のピクセルを表すためのｎ個のインデックスメンバーを有しており、該新しい出力関数は、該ｎ個のインデックスメンバーを該Ｍ個の色にマッピングするためのものであり、該データ処理システムは、
（ａ）ハードディシジョンモジュールであって、
（ｉ）該オリジナルのデジタル化されたカラー画像におけるピクセルの位置に関わらず、該オリジナルのデジタル化されたカラー画像における各ピクセルの色に基づいて、該オリジナルのデジタル化されたカラー画像における全てのピクセルをＭ個の互いに素なクラスタに分割することにより、第１の新しいインデックスシーケンスを提供し、ＭはＮ以下であり、
（ｉｉ）該Ｍ個の互いに素なクラスタにおけるピクセルへの該Ｍ個の異なる色の１対１のマッピングを提供するために、第１の新しい出力関数を提供する、
ハードディシジョンモジュールと、
（ｂ）該第１の新しいインデックスシーケンスの各メンバーに対し、該第１の新しい出力関数によってそのメンバーに割り当てられている色の値が、該第１の新しい出力関数によって該第１の新しいインデックスシーケンスの少なくとも１つの他のメンバーに割り当てられている色の値にどのように相関付けられているかに基づいて、該新しいインデックスシーケンスと該新しい出力関数とをそれぞれ提供するために、該第１の新しいインデックスシーケンスと該第１の新しい出力関数とにソフトディシジョン最適化プロセスを適用するソフトディシジョンモジュールと
を含む、データ処理システム。
【請求項３０】
前記新しいインデックスシーケンスは、前記新しいデジタル化されたカラー画像における各ピクセルに対し、該新しいインデックスシーケンスと前記新しい出力関数とによって該ピクセルに割り当てられた前記色の値が、該カラー画像の該ピクセルの位置に依存するように、ソフトディシジョンピクセルマッピングを提供する、請求項２９に記載のデータ処理システム。
【請求項３１】
前記ソフトディシジョンモジュールは、（ｉ）反復的なソフトディシジョン最適化プロセスを適用し、（ｉｉ）各反復後に、前記オリジナルのデジタル化されたカラー画像の圧縮およびひずみを表すコスト関数のインクリメントの低下を決定し、（ｉｉｉ）該インクリメントの低下が選択した閾値を下回るときに、該反復的なソフトディシジョン最適化プロセスを終了し、前記新しいインデックスシーケンスと前記新しいカラーマッピングとを決定するように動作することが可能である、請求項２９に記載のデータ処理システム。
【請求項３２】
前記反復的なソフトディシジョン最適化プロセスは、
（ｉ）カウンタｋを１に設定するステップと、
（ｉｉ）ｋ番目のインデックスシーケンスに対し、全ての考えられるインデックスシーケンスにわたり、ｋ番目の出力関数とｋ番目の推移確率関数に対して前記コスト関数を最適化することにより、（ｋ＋１）番目のインデックスシーケンスを決定するステップと、
（ｉｉｉ）該（ｋ＋１）番目のインデックスシーケンスから（ｋ＋１）番目の出力関数と（ｋ＋１）番目の推移確率関数を決定するステップと、
（ｉｖ）該（ｋ＋１）番目のインデックスシーケンスと、該（ｋ＋１）番目の出力関数と、前記（ｋ＋１）番目の推移確率関数とから、（ｋ＋１）番目のコストを決定するステップと、
（ｖ）該（ｋ＋１）番目のコストと該ｋ番目のコストとの間の（ｋ＋１）番目のコスト差を計算し、該（ｋ＋１）番目のコスト差が選択した閾値を下回るときに、新しいインデックスシーケンスと前記新しい出力関数として、該（ｋ＋１）番目のインデックスシーケンスと該（ｋ＋１）番目の出力関数とをそれぞれ選択し、そうでない場合は、ｋを１だけ増加させ、サブステップ（ｉｉ）から（ｖ）を繰り返すステップと
を含む、請求項３１に記載のデータ処理システム。
【請求項３３】
ステップ（ｉｉ）において、前記所定のｋ番目の出力関数とｋ番目の推移確率関数とに対し、全ての考えられるインデックスシーケンスにわたり、前記コスト関数を最適化することによって、前記（ｋ＋１）番目のインデックスシーケンスを決定するステップは、ビタビアルゴリズムを用いることを含む、請求項３２に記載のデータ処理システム。
【請求項３４】
前記ハードディシジョンモジュールは、前記Ｍ個の互いに素なクラスタをＭ’個の互いに素なグループにグループ分けするように動作することが可能であり、Ｍ’はＭ未満であり、
前記ハードディシジョンモジュールは、該Ｍ’個の互いに素なグループに関するソフトディシジョン最適化プロセスを適用するように動作することが可能である、
請求項３３に記載のデータ処理システム。
【請求項３５】
前記コスト関数は、ＭおよびＭ’の双方に依存する、請求項３４に記載のデータ処理システム。
【請求項３６】
共にｎ個のピクセルで定義される、オリジナルのデジタル化されたカラー画像から導出された新しいデジタル化されたカラー画像に対し、ピクセルマッピングと、カラーパレットを表す新しい出力関数とを形成するように、コンピュータシステム上で用いられるコンピュータプログラム製品であって、該オリジナルのデジタル化されたカラー画像は、該ｎ個のピクセルに割り当てられたＮ個の異なる色によって提供されており、該新しいデジタル化されたカラー画像は、該ｎ個のピクセルに割り当てられたＭ個異なる色によって提供されており、該新しいインデックスシーケンスは、該ｎ個のピクセルを表すためのｎ個のインデックスメンバーを有しており、該新しい出力関数は、該Ｍ個の色に前記ｎ個のインデックスメンバーをマッピングするためのものであり、該コンピュータプログラム製品は、
記録媒体と、
該媒体に記憶された手段であって、
（ａ）該オリジナルのデジタル化されたカラー画像におけるピクセルの位置に関わらず、該オリジナルのデジタル化されたカラー画像における各ピクセルの色に基づいて、該オリジナルのデジタル化されたカラー画像における全てのピクセルをＭ個の互いに素なクラスタに分割することにより、第１の新しいインデックスシーケンスを提供するステップであって、ＭはＮ以下である、ステップと、
（ｂ）該Ｍ個の互いに素なクラスタにおけるピクセルへの該Ｍ個の異なる色の１対１のマッピングを提供するために、第１の新しい出力関数を提供するステップと、
（ｃ）該第１の新しいインデックスシーケンスの各メンバーに対し、該第１の新しい出力関数によってそのメンバーに割り当てられている色の値が、該第１の新しい出力関数によって該第１の新しいインデックスシーケンスの少なくとも１つの他のメンバーに割り当てられているカラーの値にどのように相関付けられているかに基づいて、該新しいインデックスシーケンスと該新しい出力関数とをそれぞれ提供するために、該第１の新しいインデックスシーケンスと該第１の新しい出力関数とにソフトディシジョン最適化プロセスを適用するステップと
を実行するように該コンピュータシステムに命令する、手段と
を含む、コンピュータプログラム製品。
【請求項３７】
前記新しいインデックスシーケンスは、前記新しいデジタル化されたカラー画像における各ピクセルに対し、該新しいインデックスシーケンスと前記新しい出力関数とによって該ピクセルに割り当てられた前記色の値が、該カラー画像の該ピクセルの位置に依存するように、ソフトディシジョンピクセルマッピングを提供する、請求項３６に記載の方法。
【請求項３８】
ステップ（ｃ）は、反復的なソフトディシジョン最適化プロセスを適用し、各反復後に、前記オリジナルのデジタル化されたカラー画像の圧縮およびひずみを表すコスト関数におけるインクリメントの低下を決定するステップ
を含み、該インクリメントの低下が選択された閾値を下回るときに、ステップ（ｃ）が終了し、前記新しいインデックスシーケンスと前記新しいカラーマッピングとが決定される、請求項３６に記載の方法。
【請求項３９】
ステップ（ｃ）は、
（ｉ）カウンタｋを１に設定するステップと、
（ｉｉ）ｋ番目のインデックスシーケンスに対し、全ての考えられるインデックスシーケンスにわたり、ｋ番目の出力関数とｋ番目の推移確率関数とに対して前記コスト関数を最適化することにより、（ｋ＋１）番目のインデックスシーケンスを決定するステップと、
（ｉｉｉ）該（ｋ＋１）番目のインデックスシーケンスから（ｋ＋１）番目の出力関数と（ｋ＋１）番目の推移確率関数とを決定するステップと、
（ｉｖ）該（ｋ＋１）番目のインデックスシーケンスと、該（ｋ＋１）番目の出力関数と、該（ｋ＋１）番目の推移確率関数とから、（ｋ＋１）番目のコストを決定するステップと、
（ｖ）該（ｋ＋１）番目のコストと該ｋ番目のコストとの間の（ｋ＋１）番目のコスト差を計算し、該（ｋ＋１）番目のコスト差が選択された閾値を下回るときに、新しいインデックスシーケンスと新しい出力関数として、該（ｋ＋１）番目のインデックスシーケンスと該（ｋ＋１）番目の出力関数とをそれぞれ選択し、そうでない場合は、ｋを１だけ増加させ、サブステップ（ｉｉ）から（ｖ）を繰り返すステップと
を含む、請求項３８に記載の方法。
【請求項４０】
ステップ（ｉｉ）において、前記所定のｋ番目の出力関数とｋ番目の推移確率関数とに対し、全ての考えられるインデックスシーケンスにわたり、前記コスト関数を最適化することによって、前記（ｋ＋１）番目のインデックスシーケンスを決定するステップは、ビタビアルゴリズムを用いることを含む、請求項３９に記載の方法。
【請求項４１】
ステップ（ａ）は、前記Ｍ個の互いに素なクラスタをＭ’個の互いに素なグループにグループ分けするステップをさらに含み、Ｍ’はＭ未満であり、
ステップ（ｃ）は、該Ｍ’個の互いに素なグループに関するソフトディシジョン最適化プロセスを適用するステップを含む、請求項４０に記載の方法。
【請求項４２】
前記コスト関数は、ＭおよびＭ’の双方に依存する、請求項４１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はカラー画像の符号化のための方法、システムおよびソフトウェア製品に関する。
【背景技術】
【０００２】
（本発明の背景）
近年、インターネットにおけるカラー画像データの量は爆発的に増大している。特に、ウェブサイト、デジタルカメラ、オンラインゲームの人気の高まりによって、カラー画像データは、インターネットトラフィックの中で大きな位置を占めるようになってきている。一方で、主に画像表示装置やデータ記憶装置および伝送帯域幅の限界のために、ワイヤレスチャンネルまたは低電力の小型機器を介するカラー画像へのアクセスは、依然として時間がかかると共に不便であり、多くのマルチメディアアプリケーションのボトルネックとなっている。（例えば、非特許文献１（以下「参考資料［１］」）、非特許文献２（以下「参考資料［２］」）、非特許文献３（以下「参考資料［３］」）、非特許文献４（以下「参考資料［４］」）、非特許文献５（以下「参考資料［５］」）および非特許文献６（以下「参考資料［６］」）を参照されたい。）
上記の制限を解決する一つの方法は、カラー画像を圧縮、最適化、または再符号化する効率的なカラー画像符号化スキームを適用することである。典型的なカラー画像符号化スキームは、カラーパレット、ピクセルマッピング、および可逆コード（ｌｏｓｓｌｅｓｓ  ｃｏｄｅ）から成る。カラーパレットは、ベクトル量子化コードブックとしての役割を果たし、オリジナルのカラー画像の全ての色を表現するために利用される。次に、ピクセルマッピングは、カラーパレットの色に対応するインデックスに画像の各ピクセルをマッピングする。このピクセルマッピングは、カラーパレットの色へのＲＧＢカラーベクトルの量子化が固定されており、一旦カラーパレットが与えられると画像のＲＧＢカラーベクトルのピクセル位置とは無関係となるハードディシジョンピクセルマッピングか、あるいは、ＲＧＢカラーベクトルが異なるピクセル位置でカラーパレットの異なる色に量子化され得るソフトディシジョンピクセルマッピングであり得る。最後に、ピクセルマッピングから生じたインデックスシーケンスが、可逆コードによって符号化される。
【０００３】
従来、カラーパレットデザイン、ピクセルマッピング、および符号化は、別々に考えられていた。カラーパレットおよびピクセルマッピングの設計において、符号化部分は多くの場合無視されており、主な目的は、量子化ゆがみを低減し、量子化された画像のクオリティを向上させ、計算上の複雑性を低減することにあった。例えば、参考資料［１］〜［６］の文献において、いくつかのツリー構造の分岐および統合を行うカラー画像量子化方法は、多かれ少なかれ、この目的を達成するように提案されている。
【０００４】
一方で、符号化を考えるとき、カラーパレットおよびピクセルマッピングは、多くの場合与えられているものと仮定されており、その目的は、圧縮率を低下させるようにインデックスシーケンスの効率的なコードを設計することにある。例えば、色量子化（ｃｏｌｏｒ−ｑｕａｎｔｉｚｅ）された画像のＬＵＶカラー空間の不可逆圧縮のアルゴリズムは、非特許文献７（以下「参考資料［７］」）に示されている。２つの発見的ソリューションは、非特許文献８（以下「参考資料［８］」）に、可逆予測的符号化技術によって画像を符号化する前にカラーマップを並び替えるように提案されている。非特許文献９（以下「参考資料［９］」）では、２分木構造およびコンテクストベースのエントロピー符号化に基づいて、色量子化された画像の革新的な符号化を提供するように、圧縮アルゴリズムが提案されている。こうしたアルゴリズムでは、ＧＩＦ／ＰＮＧデコーダなどの標準的なデコーダと互換性のない圧縮されたビットストリームを犠牲にすることにより、圧縮の効率性が達成される。
【非特許文献１】Ｊ．Ｂａｒｒｉｌｌｅａｕｘ、Ｒ．Ｈｉｎｋｌｅ、およびＳ．Ｗｅｌｌｓ、「Ｅｆｆｉｃｉｅｎｔ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ  ｆｏｒ  ｃｏｌｏｒ  ｉｍａｇｅ  ｅｎｃｏｄｉｎｇ」、Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ，ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ＩＣＡＳＳＰ’８７、ｖｏｌ．１２、７４０〜７４３ページ、１９８７年４月
【非特許文献２】Ｍ．Ｔ．ＯｒｃｈａｒｄおよびＣ．Ａ．Ｂｏｕｍａｎ、「Ｃｏｌｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ  ｏｆ  ｉｍａｇｅｓ」、Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ、ｖｏｌ．３９、ｎｏ．１２、２６７７〜２６９０ページ、１９９１年１２月
【非特許文献３】Ｉ．Ａｓｈｄｏｗｎ、「Ｏｃｔｒｅｅ  ｃｏｌｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ」、Ｃ／Ｃ＋＋  Ｕｓｅｒｓ  Ｊｏｕｒｎａｌ、ｖｏｌ．１３、ｎｏ．３、３１〜４３ページ、１９９４年
【非特許文献４】Ｘ．Ｗｕ、「Ｙｉｑ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ  ｉｎ  ａ  ｎｅｗ  ｃｏｌｏｒ  ｐａｌｅｔｔｅ  ａｒｃｈｉｔｅｃｔｕｒｅ」、ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、ｖｏｌ．５、ｎｏ．２、３２１〜３２９ページ、１９９６年
【非特許文献５】Ｌ．Ｖｅｌｈｏ、Ｊ．ＧｏｍｅｓおよびＭ．Ｖ．Ｒ．Ｓｏｂｒｅｉｒｏ、「Ｃｏｌｏｒ  ｉｍａｇｅ  ｑｕａｎｔｉｚａｔｉｏｎ  ｂｙ  ｐａｉｒｗｉｓｅ  ｃｌｕｓｔｅｒｉｎｇ」、Ｐｒｏｃ．Ｔｅｎｔｈ  Ｂｒａｚｉｌｉａｎ  Ｓｙｍｐ．Ｃｏｍｐｕｔ．Ｇｒａｐｈ．Ｉｍａｇｅ  Ｐｒｏｃｅｓｓ、Ｌ．Ｈ．ｄｅ  ＦｉｇｕｅｉｒｅｄｏおよびＭ．Ｌ．Ｎｅｔｔｏ、Ｅｄｓ．Ｃａｍｐｏｓ  ｄｏ  Ｊｏｒｄａｏ、Ｓｐａｉｎ、２０３〜２１０ページ、１９９７年
【非特許文献６】Ｓ．Ｗａｎ、Ｐ．ＰｒｕｓｉｎｋｉｅｗｉｃｚおよびＳ．Ｗｏｎｇ、「Ｖａｒｉａｎｃｅ−ｂａｓｅｄ  ｃｏｌｏｒ  ｉｍａｇｅ  ｑｕａｎｔｉｚａｔｉｏｎ  ｆｏｒ  ｆｒａｍｅ  ｂｕｆｆｅｒ  ｄｉｓｐｌａｙ」、Ｒｅｓ．Ａｐｐｌ．、ｖｏｌ．１５、５２〜５８ページ、１９９０年
【非特許文献７】Ａ．ＺａｃｃａｒｉｎおよびＢ．Ｌｉｕ、「Ａ  ｎｏｖｅｌ  ａｐｐｒｏａｃｈ  ｆｏｒ  ｃｏｄｉｎｇ  ｃｏｌｏｒ  ｑｕａｎｔｉｚｅｄ  ｉｍａｇｅ」、Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ、ｖｏｌ．２、ｎｏ．４、４４２〜４５３ページ、１９９３年１０月
【非特許文献８】Ｎ．Ｄ．ＭｅｍｏｎおよびＡ．Ｖｅｎｋａｔｅｓｗａｒａｎ、「Ｏｎ  ｏｒｄｅｒｉｎｇ  ｃｏｌｏｒ  ｍａｐｓ  ｆｏｒ  ｌｏｓｓｌｅｓｓ  ｐｒｅｄｉｃｔｉｖｅ  ｃｏｄｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、ｖｏｌ．５、ｎｏ．１１、１５２２〜１５２７ページ、１９９６年
【非特許文献９】Ｘ．Ｃｈｅｎ、Ｓ．ＫｗｏｎｇおよびＪ．ｆｕ  Ｆｅｎｇ、「Ａ  ｎｅｗ  ｃｏｍｐｒｅｓｓｉｏｎ  ｓｃｈｅｍｅ  ｆｏｒ  ｃｏｌｏｒ−ｑｕａｎｔｉｚｅｄ  ｉｍａｇｅｓ」、Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ、ｖｏｌ．１２、ｎｏ．１０、９０４〜９０８ページ、２００２年１０月
【発明の開示】
【課題を解決するための手段】
【０００５】
（本発明の要約）
本発明の第１の局面にしたがうと、データ処理システムを用いることにより、Ｎ個の異なる色を有するデジタル化されたカラー画像から、デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造パーティションを形成する方法が示されており、ＭはＮ以下であり、Ｎ個の異なる色における各色は、カラーパレットにおける複数のＰビットのバイトによってデジタル的に表現され、各ＰビットのバイトにおけるＰビットは、最上位から最下位へと順序付けられている。この方法は、（ａ）Ｎ個の異なる色の全てを含むルートノードを提供するステップと、（ｂ）該ルートノードにリンクされた兄弟ノードの第１のレベルを提供するステップであって、Ｎ個の異なる色における各色は、複数のＰビットのバイトにおける各Ｐビットのバイトの第１のビットの値に基づいて、データ処理システムにより、兄弟（ｓｉｂｌｉｎｇ）ノードの第１のレベルにおける関連のあるノードに割り当てられる、ステップと、（ｃ）１色よりも多い色を含むノードのｋ番目のレベルにおける各ノードに対し、（ｋ＋１）番目のレベルの複数の兄弟ノードを提供するステップであって、そのノードにおける各色は、Ｎ個の異なる色の各色に対してその色のみを含む異なるリーフノードが存在するように、その色に対する複数のＰビットのバイトにおける各Ｐビットのバイトの（ｋ＋１）番目のビットの値に基づいて、データ処理システムにより、（ｋ＋１）番目のレベルの複数の兄弟ノードの関連のある兄弟ノードに割り当てられる、ステップと、（ｄ）Ｍ個のリーフノードのみが残されるまで、リーフノードを選択および統合するステップとを含む。
【０００６】
本発明の第２の局面にしたがうと、Ｎ個の異なる色を有するデジタル化されたカラー画像から、デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造パーティショニングを形成するデータ処理システムが示されており、ＭはＮ以下であり、Ｎ個の異なる色における各色は、カラーパレットにおける複数のＰビットのバイトによってデジタル的に表現され、各ＰビットのバイトにおけるＰビットは、最上位から最下位へと順序付けられている。データ処理システムは、（ａ）ノード生成手段であって、（ｉ）Ｎ個の異なる色の全てを含むルートノードを提供するステップと、（ｉｉ）ルートノードにリンクされた兄弟ノードの第１のレベルを提供するステップであって、Ｎ個の異なる色における各色は、複数のＰビットのバイトにおける各Ｐビットのバイトの第１のビットの値に基づいて、兄弟ノードの第１のレベルにおける関連付のあるノードへとデータ処理システムによって割り当てられる、ステップと、（ｉｉｉ）１色よりも多い色を含むノードのｋ番目のレベルにおける各ノードに対し（ｋ+１)番目のレベルの複数の兄弟ノードを提供するステップであって、そのノードにおける各色は、Ｎ個の異なる色の各色に対してその色のみを含む異なるリーフノードが存在するように、その色に対する複数のＰビットのバイトにおける各Ｐビットのバイトの（ｋ＋１）番目のビットの値に基づいて、（ｋ＋１）番目のレベルの複数の兄弟ノードにおける関連のある兄弟ノードに割り当てられる、ステップとのための、ノード生成手段と、（ｂ）Ｍ個のリーフノードのみが残されるまで、リーフノードを選択および統合するノード統合手段とを含む。
【０００７】
本発明の第３の局面にしたがうと、Ｎ個の異なる色を有するデジタル化されたカラー画像から、デジタル化されたカラー画像における全ピクセルのＭ個の互いに素なクラスタへのツリー構造のパーティションを形成するように、コンピュータシステム上で用いられるコンピュータプログラム製品が示されており、ＭはＮ以下であり、Ｎ個の異なる色における各色は、カラーパレットにおける複数のＰビットのバイトによってデジタル的に表現され、各ＰビットのバイトのＰビットは、最上位から最下位へと順序付けられている。コンピュータプログラム製品は、記録媒体と、上記媒体に記録された手段であって、（ａ）Ｎ個の異なる色の全てを含むルートノードを提供するステップと、（ｂ）ルートノードにリンクされた兄弟ノードの第１のレベルを提供するステップであって、Ｎ個の異なる色の各色は、複数のＰビットバイトにおける各Ｐビットバイトの第１のビットの値に基づいて、兄弟ノードの第１のレベルにおける関連のあるノードに割り当てられる、ステップと、（ｃ）１色よりも多い色を含むノードのｋ番目のレベルの各ノードに対し、（ｋ＋１）番目のレベルの複数の兄弟ノードを提供するステップであって、そのノードにおける各色は、Ｎ個の異なる色の各色に対してその色のみを含む異なるリーフノードが存在するように、その色に対する複数のＰビットのバイトにおける各Ｐビットのバイトの（ｋ＋１）番目のビットの値に基づいて、（ｋ＋１）番目のレベルの複数の兄弟ノードにおける関連のある兄弟ノードに割り当てられる、ステップと、（ｄ）Ｍ個のリーフノードのみが残されるまで、リーフノードを選択および統合するステップを実行するようにコンピュータシステムに命令する、手段とを含む。
【０００８】
本発明の第４の局面にしたがうと、共にｎ個のピクセルで定義される、オリジナルのデジタル化されたカラー画像から導出されたデジタル化された新しいカラー画像に対し、ピクセルマッピングを表す新しいインデックスシーケンスと、カラーパレットを表す新しい出力関数とを導出する方法が提供されており、オリジナルのデジタル化されたカラー画像は、ｎ個のピクセルに割り当てられたＮ個の異なる色によって提供されており、新しいデジタル化されたカラー画像は、ｎ個のピクセルに割り当てられたＭ個の異なる色によって提供されており、新しいインデックスシーケンスは、ｎ個のピクセルを表すためのｎ個のインデックスメンバーを有しており、新しい出力関数は、Ｍ個の色にｎ個のインデックスメンバーをマッピングするためのものである。該方法は、（ａ）オリジナルのデジタル化されたカラー画像におけるピクセルの位置に関わらず、オリジナルのデジタル化されたカラー画像における各ピクセルの色に基づいて、オリジナルのデジタル化されたカラー画像における全てのピクセルをＭ個の互いに素なクラスタに分割することにより（ＭはＮ以下である）、第１の新しいインデックスシーケンスを提供するステップと、（ｂ）Ｍ個の互いに素なクラスタにおけるピクセルへのＭ個の異なる色の１対１のマッピングを提供するために、第１の新しい出力関数を提供するステップと、（ｃ）第１の新しいインデックスシーケンスの各メンバーに対し、第１の新しい出力関数によってそのメンバーに割り当てられている色の値が、第１の新しい出力関数によって第１の新しいインデックスシーケンスの少なくとも１つのその他のメンバーに割り当てられている色の値にどのように相関付けられているかに基づいて、新しいインデックスシーケンスと新しい出力関数とをそれぞれ提供するために、第１の新しいインデックスシーケンスと第１の新しい出力関数とにソフトディシジョン最適化プロセスを適用するステップとを含む。
【０００９】
本発明の第５の局面にしたがうと、共にｎ個のピクセルで定義される、オリジナルのデジタル化されたカラー画像から生成された新しいデジタルカラー画像に対し、ピクセルマッピングを表す新しいインデックスシーケンスと、カラーパレットを表す新しい出力関数とを導出するためのデータ処理システムが提供される。オリジナルのデジタル化されたカラー画像はｎ個のピクセルに割り当てられるＮ個の個別の色で成っており、新しいデジタル化されたカラー画像は、ｎ個のピクセルに割り当てられたＭ個の異なる色によって提供されており、新しいインデックスシーケンスは、ｎ個のピクセルを表すためのｎ個のインデックスメンバーを有しており、新しい出力関数は、Ｍ個の色にｎ個のインデックスメンバーをマッピングするためのものである。該データ処理システムは、（ａ）ハードディシジョンモジュールであって、（ｉ）オリジナルのデジタル化されたカラー画像におけるピクセルの位置に関わらず、オリジナルのデジタル化されたカラー画像の各ピクセルの色に基づいて、オリジナルのデジタル化されたカラー画像における全てのピクセルをＭ個の互いに素なクラスタに分割することにより（ＭはＮ以下である）、第１の新しいインデックスシーケンスを提供し、（ｉｉ）Ｍ個の互いに素なクラスタにおけるピクセルへのＭ個の異なる色の１対１のマッピングを提供するために、第１の新しい出力関数を提供する、ハードディシジョンモジュールと、（ｂ）第１の新しいインデックスシーケンスの各メンバーに対し、第１の新しい出力関数によってそのメンバーに割り当てられている色の値が、第１の新しい出力関数によって第１の新しいインデックスシーケンスの少なくとも１つのその他のメンバーに割り当てられている色の値にどのように相関付けられているかに基づいて、新しいインデックスシーケンスと新しい出力関数とをそれぞれ提供するために、第１の新しいインデックスシーケンスと第１の新しい出力関数とにソフトディシジョン最適化プロセスを適用するソフトディシジョンモジュールとを含む。
【００１０】
本発明の第６の局面にしたがうと、共にｎ個のピクセルで定義される、オリジナルのデジタル化されたカラー画像から導出された新しいデジタルカラー画像に対し、ピクセルマッピングと、カラーパレットを表す新しい出力関数とを形成するように、コンピュータシステム上で用いられるコンピュータプログラム製品が提供される。オリジナルのデジタル化されたカラー画像は、ｎ個のピクセルに割り当てられたＮ個の異なる色によって提供されており、新しいデジタル化されたカラー画像は、ｎ個のピクセルに割り当てられたＭ個の異なる色によって提供されており、新しいインデックスシーケンスは、ｎ個のピクセルを表すためのｎ個のインデックスメンバーを有しており、新しい出力関数は、Ｍ個の色にｎ個のインデックスメンバーをマッピングするためのものである。該コンピュータプログラム製品は、記録媒体と、記録媒体に記憶された手段であって、（ａ）オリジナルのデジタル化されたカラー画像におけるピクセルの位置に関わらず、オリジナルのデジタル化されたカラー画像における各ピクセルの色に基づいて、オリジナルのデジタル化されたカラー画像における全てのピクセルをＭ個の互いに素なクラスタに分割することにより（ＭはＮ以下である）、第１の新しいインデックスシーケンスを提供し、（ｂ）Ｍ個の互いに素なクラスタにおけるピクセルへのＭ個の異なる色の１対１のマッピングを提供するために、第１の新しい出力関数を提供し、（ｃ）第１の新しいインデックスシーケンスの各メンバーに対し、第１の新しい出力関数によってそのメンバーに割り当てられている色の値が、第１の新しい出力関数によって第１の新しいインデックスシーケンスの少なくとも１つのその他のメンバーに割り当てられている色の値にどのように相関付けられているかに基づいて、新しいインデックスシーケンスと新しい出力関数とをそれぞれ提供するために、第１の新しいインデックスシーケンスと第１の新しい出力関数とにソフトディシジョン最適化プロセスを適用するステップとを実行するようにコンピュータシステムに命令する、媒体に記録された手段とを含む。
【００１１】
本発明の好適な実施例の詳細な説明を、以下の図面を参照しながら、以下に説明する。
【発明を実施するための最良の形態】
【００１２】
（本発明の好ましい実施形態の詳細な記述）
図１を参照すると、ブロック図によって本発明の一局面にしたがうコンピュータシステムが１０が示されている。コンピュータシステムは、カラー画像データを保存するメモリ１２と、デジタルカラー画像を表示するモニター１４と、画像処理のための、および、計算上の複雑性を低く抑え、ＧＩＦ／ＰＮＧデコーダとの互換性を保つ一方で、量子化、ひずみおよび圧縮重量を同時に最適化するカラーデータの圧縮を提供するためのＣＰＵ１６と、伝送線２０によるコンピュータシステム１０からの伝送の前に、カラー画像データを符号化するＧＩＦエンコーダまたはＰＮＧエンコーダのような、エンコーダ２０とを含む。
【００１３】
カラー画像符号化の同時最適化の問題は、以下のように定義できる。Ω＝｛（ｒ，ｇ，ｂ）｜０≦ｒ，ｇ，ｂ≦２５５｝をＲＧＢ色空間とする。０＝｛ｏ０，ｏ１…，ｏＮ−１｝は、Ｎ個の異なる色を有するオリジナルのカラー画像のカラーパレットと仮定する。オリジナル画像における総ピクセル数がｎである場合、カラー画像を上下左右の全体にスキャンすることにより、インデックスシーケンスＩ＝（ｉ０，ｉ１，…，ｉｎ―１）が得られる。ｉｋは、ｋ番目のピクセルのカラーベクトルがｏｉｋであることを示す。制限的に、Ｍ個（Ｍ＜Ｎ）の色を有する新しいカラーパレットＣを用いることにより、オリジナルのカラー画像を再現する場合、同時最適化エンコーダは、新しいカラーパレットＣ＝｛ｃ０，ｃ１，．．．，ｃＭ−１｝、新しいインデックスシーケンスＵ＝（ｕ０，ｕ１，．．．，ｕｎ−１）、および可逆コードワード長関数を求めることにより、オリジナルの画像を再現し、コスト関数
【００１４】
【化１】
2007534239.tif 000003
を最小化することを目的とする。λはラグランジアン乗数であり、ｄは、
【００１５】
【化２】
2007534239.tif 000004
のように、ｃｕｋによってｏｉｋを表すことにより生じる２乗誤差である。
【００１６】
可逆コードワード長関数と可逆コードとの間には、１対１のマッピングが存在するため、可逆コードワード長関数の選択は、可逆コードの選択と等価である。
【００１７】
明らかに、
【００１８】
【化３】
2007534239.tif 000005
は全２乗誤差（ＴＳＥ；ｔｏｔａｌ  ｓｑｕａｒｅ  ｅｒｒｏｒ）であり、これは、量子化されたカラー画像のビジュアルクオリティに密接に関連する。ＴＳＥまたはその他同様のひずみの測定値の最小化は、参考資料［１］から［６］で考察されている量子化指向の方法の唯一の目的である。同様に、新しいカラーパレットＣおよびピクセルマッピング（したがって、インデックスシーケンスＵ）を考えると、考えられる可逆コードワード長関数ｌの全てにおけるビットレートｎ−１ｌ（Ｕ）の最小化は、参考資料［７］から［９］で考察されている色量子化された画像に対する符号化方法の唯一の目的である。上記のコスト関数により、圧縮率とひずみとの同時最適化という問題が前面に出される。量子化ひずみは、カラーパレットＣおよびピクセルマッピング（すなわち、インデックスシーケンスＵ）によって決定され、圧縮率は、ピクセルマッピングおよび可逆コードワード長関数ｌの両方によって決定される。ここで、当然ながら、ピクセルマッピングは、ソフトディシジョンピクセルマッピングである。したがって、可逆コードワード長関数ｌが決定されている場合でさえも、ＣおよびＵの両方を変更することにより、圧縮率およびひずみの両方を同時に最適化することが可能である。
【００１９】
可逆コードワード長関数は数多くあり、それぞれが例えば次のような異なるエントロピーコードに対応している。例えば、Ｈｕｆｆｍａｎコード、Ｄ．Ａ．Ｈｕｆｆｍａｎ、「Ａ  ｍｅｔｈｏｄ  ｆｏｒ  ｔｈｅ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ｍｉｎｉｍｕｍ−ｒｅｄｕｎｄａｎｃｙ  ｃｏｄｅｓ」、Ｐｒｏｃ．ＩＲＥ、ｖｏｌ．４０、ｎｏ．９、１０９８〜１１０１ページ、１９５２年（以下「参考資料［１２］」）、Ｌｅｍｐｅｌ−ｚｉｖコード、Ｊ．ＺｉｖおよびＡ．Ｌｅｍｐｅｌ、「Ａ  ｕｎｉｖｅｒｓａｌ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｓｅｑｕｅｎｔｉａｌ  ｄａｔａ  ｃｏｍｐｒｅｓｓｉｏｎ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．２３、３３７〜３４３ページ、１９７７年（以下「参考資料［１１］」）、Ｊ．ＺｉｖおよびＡ．Ｌｅｍｐｅｌ、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ（以下「参考資料［１０］」）、算術コード、Ｉ．Ｈ．Ｗｉｔｔｅｎ、Ｍ．Ｎｅａｌ、およびＪ．Ｇ．Ｃｌｅａｒｙ、「Ａｒｉｔｈｍｅｔｉｃ  ｃｏｄｉｎｇ  ｆｏｒ  ｄａｔａ  ｃｏｍｐｒｅｓｓｉｏｎ」、Ｃｏｍｍｕｎ．ＡＣＭ、ｖｏｌ．  ３０、５２０〜５４０ページ、１９８７年６月（以下「参考資料［１３］」）、文法ベースコード、Ｅ．−Ｈ．ＹａｎｇおよびＪ．Ｃ．Ｋｉｅｆｆｅｒ、「Ｅｆｆｉｃｉｅｎｔ  ｕｎｉｖｅｒｓａｌ  ｌｏｓｓｌｅｓｓ  ｄａｔａ  ｃｏｍｐｒｅｓｓｉｏｎ  ａｌｇｏｒｉｔｈｍｓ  ｂａｓｅｄ  ｏｎ  ａ  ｇｒｅｅｄｙ  ｓｅｑｕｅｎｔｉａｌ  ｇｒａｍｍａｒ  ｔｒａｎｓｆｏｒｍ−  ｐａｒｔ  ｏｎｅ：Ｗｉｔｈｏｕｔ  ｃｏｎｔｅｘｔ  ｍｏｄｅｌｓ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４６、ｎｏ．３、７５５〜７７７ページ、２０００年５月（以下「参考資料［１４］」）、Ｊ．Ｃ．ＫｉｅｆｆｅｒおよびＥ．−Ｈ．Ｙａｎｇ、「Ｇｒａｍｍａｒ  ｂａｓｅｄ  ｃｏｄｅｓ：  Ａ  ｎｅｗ  ｃｌａｓｓ  ｏｆ  ｕｎｉｖｅｒｓａｌ  ｌｏｓｓｌｅｓｓ  ｓｏｕｒｃｅ  ｃｏｄｅｓ」、ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４６、ｎｏ．３、７３７〜７５４ページ、２０００年５月（以下「参考資料［１５］」）、Ｅ．−Ｈ．ＹａｎｇおよびＤ．−Ｋ．Ｈｅ  ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４９、２８７４〜２８９４ページ、２００３年（以下「参考資料［１６］」）、およびカラー画像符号化のために特別に設計された可逆コード（参考資料［７］〜［９］を参照）。ＧＩＦ／ＰＮＧデコーダとの互換性を維持したいので、ＧＩＦデコーダの場合には、ＬＺ７８のコードワード長またはその変種、ＰＮＧデコーダの場合には、ＬＺ７７コードまたはその変種となるように選択する。Ｊ．Ｍｉａｎｏ、「Ｃｏｍｐｒｅｓｓｅｄ  ｉｍａｇｅ  ｆｉｌｅ  ｆｏｒｍａｔｓ：Ｊｐｅｇ，ｐｎｇ，ｇｉｆ，ｘｂｍ，ｂｍｐ」、ＡＣＭ  Ｐｒｅｓｓ、２０００年（以下「参考資料［１７］」）。これは、いずれの場合も、ｌＬＺ（Ｕ）と示される。したがって、この場合に最小化されるコスト関数は、
【００２０】
【化４】
2007534239.tif 000006
である。
【００２１】
上記のコスト関数は、エントロピー制約ベクトル量子化（ＥＣＶＱ；ｅｎｔｒｏｐｙ−ｃｏｎｓｔｒａｉｎｅｄ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ）で定義されるコスト関数、Ｐ．Ａ．Ｃｈｏｕ、Ｔ．Ｌｏｏｋａｂａｕｇｈ、およびＲ．Ｍ．Ｇｒａｙ、「Ｅｎｔｒｏｐｙ−ｃｏｎｓｔｒａｉｎｅｄ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ」、Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ，ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ［ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇも参照］、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ、ｖｏｌ．３７、ｎｏ．１、３１〜４２ページ、１９８９年１月（以下「参考資料［１８］」）、および、特に、変動比率トレリスソース符号化（ＶＲＴＳＥ；ｖａｒｉａｂｌｅ−ｒａｔｅ  ｔｒｅｌｌｉｓ  ｓｏｕｒｃｅ  ｅｎｃｏｄｉｎｇ）で定義されるコスト関数、Ｅ．−Ｈ．ＹａｎｇおよびＺ．Ｚｈａｎｇ、「Ｖａｒｉａｂｌｅ  ｒａｔｅ  ｔｒｅｌｌｉｓ  ｓｏｕｒｃｅ  ｅｎｃｏｄｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４５、ｎｏ．２、５８６〜６０８ページ、１９９９年３月（以下「参考資料［１９］」）と類似の形態である。ＶＲＴＳＥは、トレリス構造を利用し、生成される圧縮率、ひずみ、および選択された符号化パスを同時に最適化するという意味において、エントロピー制約スカラー量子化およびベクトル量子化の一般化［１８］と考えることができる。特に低圧縮率領域において、その効率的なパフォーマンスにより、ＶＲＴＳＥは、特に、格納スペースと伝送時間とを節約するために高い圧縮率がしばしば所望されるカラー画像の符号化に適用可能となる。
【００２２】
ＶＲＴＳＥに基づき、発明の一局面にしたがって、計算上の複雑性を低く抑え、ＧＩＦ／ＰＮＧデコーダとの互換性を維持する一方で、量子化ひずみと圧縮率との両方を同時に最適化する可変圧縮率トレリスカラー量子化（ＶＲＴＣＱ；ｖａｒｉａｂｌｅ−ｒａｔｅ  ｔｒｅｌｌｉｓ  ｃｏｌｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ）１およびＶＲＴＣＱ２という２つの方法を開発した。ＶＲＴＣＱ１とＶＲＴＣＱ２の両方は、ソフトディシジョンピクセルマッピングを利用し、反復性がある。加えて、本発明のさらなる局面により、ＶＲＴＣＱ１およびＶＲＴＣＱ２に対する初期のカラー画像符号化スキームを提供するために、ＲＧＢカラーに対する八分木データ構造を利用し、量子化されたカラー画像のエントロピー制約コストを部分的に最小化するエントロピー制約階層的統合量子化（ＥＣＨＭＱ；ｅｎｔｒｏｐｙ−ｃｏｎｓｔｒａｉｎｅｄ  ｈｉｅｒａｒｃｈｉｃａｌ  ｍｅｒｇｉｎｇ  ｑｕａｎｔｉｚａｔｉｏｎ）が開発された。ＥＣＨＭＱは、それ自身のみで、量子化されたカラー画像の圧縮率およびひずみをトレードオフする効率的な方法を提供する。
【００２３】
（可変圧縮率トレリスソースエンコーティングの概要）
［１９］で示される可変圧縮率トレリスソース符号化は、固定された勾配の不可逆符号化をトレリス構造のデコーダーの場合に拡大したものである。固定された勾配の不可逆符号化は、Ｅ．ｈｕｉ  Ｙａｎｇ、Ｚ．Ｚｈａｎｇ、およびＴ．Ｂｅｒｇｅｒ、「Ｆｉｘｅｄ−ｓｌｏｐｅ  ｕｎｉｖｅｒｓａｌ  ｌｏｓｓｙ  ｄａｔａ  ｃｏｍｐｒｅｓｓｉｏｎ」、ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４３、ｎｏ．５、１４６５〜１４７６ページ、１９９７年９月（以下「参考資料［２０］」）に示されている。各実数値のソースシーケンスｘｎ＝（ｘ０，ｘ１，．．．，ｘｎ−１）∈Ｒｎに対し、シーケンスｕｎ＝（ｕ０，ｕ１．．．ｕｎ−１）∈Ｍｎｓｅｔ，Ｍｓｅｔ＝｛０，１，．．．，Ｍ−１｝を求めることにより、コスト関数
【００２４】
【化５】
2007534239.tif 000007
を最小化することを目的としている。λは、一定のラグランジアン乗数であり、ｌは可逆コードワード長関数、β（ｕｎ）＝（ｚ０，ｚ１…，ｚｎ−１）はｕｎに対応する再現シーケンスであり、ｐは、任意のｘｎ＝（ｘ０，ｘ１，…，ｘｎ−１）およびｚｎ（ｚ０，ｚ１…，ｚｎ−１）に対し、
【００２５】
【化６】
2007534239.tif 000008
で定義される2乗誤差である。
【００２６】
再現シーケンスβ（ｕｎ）は、トレリス構造のデコーダβ＝（ｆ，ｇ）を介してｕｎから求められる。ここに、ｆ：ＳｘＭｓｅｔ→Ｓは状態推移関数であり、Ｓ＝｛ｓ０，ｓ１，．．．，ｓ｜Ｓ｜−１｝は状態の集合であり、ｇ：ＳｘＭｓｅｔ→Ｒは出力関数である。関数ｆおよびｇは、それぞれ、トレリス構造と、（カラーパレットと類似した）再現レベルの集合とを決定する。所与の初期状態ｓｉ０に対し、再現シーケンスβ（ｕｎ）＝（ｚ０，ｚ１，．．．ｚｎ−１）は、以下のように求められる。
【００２７】
【化７】
2007534239.tif 000009
換言すると、ｕｎを受け取ると、デコーダβは、状態のシーケンスｓｉｏ，ｓｉ１，．．．，ｓｉｎにトラバースする一方で、再現シーケンスβ（ｕｎ）＝（ｚ０，ｚ１，…，ｚｎ−１）を出力する。
【００２８】
βを固定する。ｌを、ｋ次の推移確率関数Ｗ（ｕ｜ｕｋ）によるｋ次の静的算術コードワード長関数（ｓｔａｔｉｃ  ａｒｉｔｈｍｅｔｉｃ  ｃｏｄｅｗａｒｄ  ｌｅｎｇｔｈ  ｆｕｎｃｔｉｏｎ）ＬＷｋとして選択する。次に、ビタビアルゴリズムを用いることにより、
【００２９】
【化８】
2007534239.tif 000010
のように、最適シーケンスｕｎが求められ得る。
【００３０】
ｆを固定する。ｇ、ｕｎ、およびＬＷｋ（同じことであるが、Ｗ（ｕ｜ｕｋ））の同時最適化は、
【００３１】
【化９】
2007534239.tif 000011
のように記述され得る。
【００３２】
同時最適化問題（２．５）を解決するための代替的なアルゴリズムは、［１９］に提案されている。この代替的なアルゴリズムの手順は、以下の通りである。
【００３３】
ステップ１：ｔ＝０と設定する。
【００３４】
【化１０】
2007534239.tif 000012
を満たす出力関数ｇ（ｏ）と推移確率関数Ｗ（０）とを選択する。
【００３５】
ステップ２：ｇ（ｔ）およびＷ（ｔ）を固定する。ビタビアルゴリズムを用いることにより、ｇをｇ（ｔ）に置換しＷをＷ（ｔ）に置換した等式（２．４）を満たすシーケンス（ｕｎ）（ｔ）＝（ｕ０（ｔ），ｕ１（ｔ），…ｕｎ−１（ｔ））を求める。
【００３６】
ステップ３：（ｕｎ）（ｔ）を固定する。インデックスシーケンス（ｕｎ）（ｔ）は、推移確率関数と出力関数とを
【００３７】
【化１１】
2007534239.tif 000013
および
【００３８】
【化１２】
2007534239.tif 000014
のように更新する。ここに、ｕｊ−ｋｊ−ｌ＝ｕｊ−ｋ…ｕｊ−１，ｓｉｊ，ｊ＝０，１，…ｎ−１は、（ｕｎ）（ｔ）に応答してトレリスデコーダ（ｆ，ｇ（ｔ））によってトラバースされる状態であり、Σｓ，ｕは、ｓｉｊ＝ｓおよびｕｊ（ｔ）＝ｕを満たすすべてのｊにわたって取られる。
【００３９】
ステップ４：ｔ＝０，１，２，．．．に対し、
【００４０】
【化１３】
2007534239.tif 000015
となるまで、ステップ２からステップ３を繰り返す。ξは、所定の小さい閾値であり、ＬｋＷ（ｔ）は、ｋ次の推移確率関数Ｗ（ｔ）（ｕ｜ｕｋ）に関連するｋ次の静的算術コードワード長関数である。その後、ｇ（ｔ＋ｌ）、（ｕｎ）（ｔ＋１）、およびＷ（ｔ＋１）を出力する。
【００４１】
ＶＲＴＳＥの性能は、参考資料［１９］の定理３および４に示されているように、圧縮率・ひずみの制限に漸近する。ガウシアン、ラプラシアン、ガウス・マルコフのソース上での実験結果は、ＶＲＴＳＥが特に低圧縮率符号化に適していることを示している。ＶＲＴＳＥをカラー画像符号化に適用するには、以下の問題に対処しなければならない。
【００４２】
問題１：ＶＲＴＳＥで用いられる可逆コードワード長関数は、ｋ次の静的算術コードワード長関数Ｌｋである。一方で、カラー画像の符号化の現在の例において、可逆コードワード長関数は、Ｌｅｍｐｅｌ−ｚｉｖコードワード長関数ｌＬＺである。
【００４３】
問題２：ＶＲＴＳＥにおいて、初期化ステップ、すなわちステップ１は指定されていない。すなわち、初期関数ｇ（０）とＷ（０）をいかにして選択するかは、ＶＲＴＳＥにおいては決定されていない。このことは、ここでのカラー画像符号化設定においては、初期のカラー画像符号化スキームをいかにして設計するかということに言い換えられる。
【００４４】
問題３：計算上の複雑性を低減するために、ＶＲＴＳＥにおけるインデックス集合Ｍｓｅｔは、しばしば２進的となるように、すなわちＭｓｅｔ＝２となるように選択される。これにより、高次の算術コードワード長が使用され得る。一方で、カラー画像符号化では、濃度Ｍは通常比較的大きく、おおよそ２５６くらいであり得る。したがって、計算上の複雑性を低減するための新しい方法が必要とされる。
【００４５】
問題１を回避するために、Ｌｅｍｐｅｌ−ｚｉｖコードワード長関数ｌＬＺを上から制限する。ｌＬＺがＬＺ７８のコードワード長関数である場合、可逆ソース符号化に関する文献（例えば、［１４］を参照）から、任意のシーケンスｕｎ＝（ｕ０，ｕ１，．．．，ｕｎ−１）に対し、
【００４６】
【化１４】
2007534239.tif 000016
がしたがう。ｒｋ（ｕｎ）は、シンボル毎のビットにおけるｕｎのｋ次の経験的エントロピーであり、ｑｋはｋのみに依存する定数であり、対数は底２に関する対数を示す。同様な上限は、ｌＬＺがＬＺ７７のコードワード長関数である場合にも有効である。ひずみの制約を受ける（１／ｎ）ｌＬＺ（ｕｎ）を最小化する代わりに、ＶＲＴＣＱ１において同じひずみ制約を受けるｒｋ（ｕｎ）が最小化され得る。ＶＲＴＣＱ２では異なる上限が使用される。問題２〜３は以下で扱われる。
【００４７】
（エントロピー制約階層的統合量子化）
本発明の一局面にしたがうと、ＶＲＴＳＥに対する初期カラー画像符号化スキームを提供するエントロピー制約階層的統合量子化（ＥＣＨＭＱ）を介することにより、問題２が扱われる。ＥＣＨＭＱは、ＶＲＴＣＱ１およびＶＲＴＣＱ２の双方に対して、第１のステージ、すなわちステージ１としての役割を果たす。
【００４８】
ＥＣＨＭＱはハードディシジョン量子化であり、オリジナルのＮ個の色をＭ個の重複しないクラスタに分割し、各クラスタに対する再現色を求め、２次元画像におけるオリジナルの色の位置に関わらず、各オリジナルの色の再現色を決定する。これは八分木データ構造［３］を活用したものであり、以下に定義されるエントロピー制約コストを部分的に最小化することにより、圧縮率およびひずみをトレードオフする。
【００４９】
カラーパレットＯ＝｛ｏ０，ｏ１，．．．，ｏＮ−１｝と新しいカラーパレットの所望のサイズＭ＜Ｎとを有するｎピクセルの所与のカラー画像に対し、ハードディシジョン量子化器ｑを用いることにより、ｉ≠ｊおよび０≦ｉ，ｊ＜Ｍに対し、Ｎ個の色を
【００５０】
【化１５】
2007534239.tif 000017
を満たすＭ個のクラスタＣ０，Ｃ１，．．．，ＣＭ−１に分割する。
【００５１】
クラスタの重心の整数形式は、カラーパレットＣ＝｛ｃ０，ｃ１，．．．，ｃＭ−１｝を構成し、オリジナルの色からクラスタへのマッピングは、各ピクセルをインデックスに明示的にマッピングする。ｕｎ＝（ｕ０，ｕ１，．．．，ｕｎ−１）∈Ｍｎｓｅｔを、全てのピクセルをインデックスにマッピングすることから得られるインデックスシーケンスとする。次に、量子化された画像のエントロピー制約コストは、次のように定義される。
【００５２】
【化１６】
2007534239.tif 000018
ここに、λはラグランジアン乗数である。（３．８）において、Ｄ（ｑ）は全２乗誤差
【００５３】
【化１７】
2007534239.tif 000019
である。ここに、Ｆ（ｏｉ），０≦ｉ＜Ｎは、オリジナルのカラー画像における色ｏｉの出現回数であり、ｄ（ｏｋ，ｃｊ）は、式（１．１）で定義されるように、ＲＧＢ空間における２色間のユークリッド距離の２乗である。Ｒ（ｑ）は、インデックスシーケンスｕｎのコードワード長である。色からインデックスへのマッピングは、カラー画像における色の位置とは独立であるため、コードワード長を計算するためには、１次のエントロピー
【００５４】
【化１８】
2007534239.tif 000020
が用いられる。
【００５５】
式（３．８）に定義されたコスト関数は、参考資料［１８］におけるエントロピー制約ベクトル量子化（ＥＣＶＱ）で定義されるラグランジアン関数と類似している。主な課題は、優れたレートのひずみのトレードオフと、低い符号化の複雑性とを用いて、ハードディシジョン量子化器ｑを設計することである。統合を高速化するために八分木構造が用いられ、量子化された画像の圧縮率とひずみとをトレードオフするために、等式（３．８）で定義されたコスト関数が用いられる。
【００５６】
各ピクセルの色を走査しツリー［３］にこれを挿入するオンザフライ（ｏｎ−ｔｈｅ−ｆｌｙ）八分木構築手順とは異なり、まず、オリジナルのカラー画像のヒストグラムを得ることにより、初期の八分木を構築する。図２を参照すると、オリジナルのカラー画像における異なる色の全てとその出現とを含む八分木２２がグラフに示されている。ルートノード２４、すなわち、レベル０は、カラー画像における異なるの色の全てを含む。ＲＧＢ色空間の各色は、３つの８ビットバイトで構成され、それらのうちの各々は主成分を示しているため、３つのバイトの最上位ビットは、レベル１の色の位置を決定する。１色よりも多い色がノードを通過する限り、そのノードは中間ノード２６であり、下位のＲＧＢビットの組み合わせによってさらに分岐し得る。リーフノード２８を通過する色は、そのリーフノード２８における色と呼ばれ、事実上、その色自体は、そのリーフノードの重心である。レベルｋにおける任意の２つのリーフ兄弟ノードの重心の間の各色成分の方向における距離は、（０，２９−ｋ）の範囲内となる。明らかに、ｋの値が大きいほど、それらの重心色はより類似する。図２に示される八分木２２は、２つの理由により非常に不均衡で非対称となっていることに留意されたい。第１に、通常のカラー画像に現れる色の個数は、ＲＧＢ空間で利用可能な全２２４色よりも遥かに少ない（参考資料［１７］を参照）ことと、第２に、一色しかこれを通過しない場合には、ノードは、分岐を停止するということである。
【００５７】
オリジナルのカラー画像における異なる各色ｏｉは、八分木の異なるリーフノードΘｉに表示される。常時２つのリーフ兄弟ノードを繰り返し統合することにより、リーフノードの数をＮからＭに減らすことが可能である。生成された各リーフノードの重心の整数形式は、新しいカラーパレットにおける色である。リーフ兄弟ノードを繰り返し統合した後、各リーフノードは、オリジナルのカラー画像のカラーパレットにおける色のサブセットに対応する。
【００５８】
Ｏ＝｛ｏ０，ｏ１，．．．，ｏＮ−１｝をオリジナルのカラー画像のカラーパレットであると仮定する。ΘｉおよびΘｊを、親ノードΘｒの下にある２つの兄弟ノードとし、Θｉ＝｛ｏｉ０，ｏｉ１，…，ｏｉｍ−１｝、Θｊ＝｛ｏｊ０，ｏｊ１，…，ｏｊｋ−１｝、およびΘｉ∩Θｊ≡φとする。ｃｉをΘｉに対する重心色とし、ｃｊをΘｊに対する重心色とする。ノードΘｉの出現回数ＦｉをノードのΘｉ各色の出現回数の合計として定義する。
【００５９】
【化１９】
2007534239.tif 000021
Ｆｉｔは、オリジナルの画像の色ｏｉｔの出現回数である。ノードΘｊの出現回数Ｆｊもまた、同様に計算される。
【００６０】
【化２０】
2007534239.tif 000022
Ｆｊｔは、オリジナルの画像の色ｏｊｔの出現回数を示す。２つのノードΘｉおよびΘｊを新しいノードΘｉｊに統合することにより、ΘｉおよびΘｊにおける全ての色を新しいノードΘｉｊに移動させる。すなわち、Θｉｊ＝Θｉ∪Θｊ＝｛ｏｉ０，ｏｉ１，．．．，ｏｉｍ−１，ｏｊ０，ｏｊ１，．．．，ｏｊｋ−１｝とする。したがって、ノードΘｉｊの出現回数は、Ｆｉｊ＝Ｆｉ＋Ｆｊ．となる。実数の色が許容されていると仮定する。次の補助定理は、ΘｉおよびΘｊをΘｉｊに統合することから生じるエントロピー制約コストインクリメントを与える。
【００６１】
補助定理１：ノードΘｉおよびΘｊを統合することにより、エントロピー制約コストは、
【００６２】
【化２１】
2007534239.tif 000023
によって増加する。
ここに、ｃｉｊは、ノードΘｉｊの重心、つまり
【００６３】
【化２２】
2007534239.tif 000024
である。
【００６４】
証明：セルの重心を用いてセルの全ての要素を再現するとき、最小全２乗誤差が得られる。これは、重心の条件、Ｓ．Ｐ．Ｌｌｏｙｄ、「Ｌｅａｓｔ  ｓｑｕａｒｅｓ  ｑｕａｎｔｉｚａｔｉｏｎ  ｉｎ  ｐｃｍ」、ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｎｏ．２８、１２７〜１３５ページ、１９８２年３月（以下「参考資料［２１］」）であり、量子化の方法で広く用いられている。この明細書では、リーフノードの重心を量子化のレベルとして、すなわち、そのノードにおける全ての色に対する再現色として用いる。このようにして、統合前のエントロピー制約コストと統合後の全エントロピー制約コストの間の差を計算しなくても、考えられる統合の各々に対するエントロピー制約コストが計算可能され得る。
【００６５】
Ｆｉｃｉ＝Σｐ＝０ｍ−１Ｆｉｐｏｉｐ、Ｆｊｃｊ＝Σｑ＝０ｋ−１Ｆｊｑｏｊｑであるため、新しいノード
Θｉｊの重心は、
【００６６】
【化２３】
2007534239.tif 000025
となる。
【００６７】
増加したエントロピー制約コストΔＪの等式（３．１１）は、増加した２乗誤差ΔＤおよび増加したコードワード長ΔＲを個別に計算することにより、証明可能である。ＤΘｉをΘｉに対する量子化レベルとしてｃｉを用いることにより生じた全２乗誤差を示すものとする。すると、ＤΘｉ＝Σｐ＝０ｍ−１Ｆｉｐ‖ｏｉｐ−ｃｉ‖２となる。同様に、ＤΘｊ＝Σｑ＝０ｋ−１Ｆｊｑ‖ｏｊｑ−ｃｊ‖ｏｊｑ−ｃｊ‖２およびＤΘｉｊ＝Σｐ＝０ｍ−１Ｆｉｐ‖ｏｉｐ−ｃｉｊ‖２＋Σｑ＝０ｋ−１Ｆｊｑ‖ｏｊｑ−ｃｉｊ‖２が得られる。ｃｉｊを等式（３．１２）の表示に代え、Ｄ（Θｉｊ）の表示を単純化することにより、ＤΘｉｊ＝ＤΘｉ＋ＤΘｊ＋Ｆｉｄ（ｃｉ，ｃｉｊ）＋Ｆｊｄ（ｃｊ，ｃｉｊ）が得られる。したがって、
【００６８】
【化２４】
2007534239.tif 000026
となる。
【００６９】
ＲΘｉをノードΘｉにおける色を有する全てのピクセルを符号化するエントロピーから生じるビットの総数を示すものとする。すると、
【００７０】
【化２５】
2007534239.tif 000027
となる。同様に、
【００７１】
【化２６】
2007534239.tif 000028
および
【００７２】
【化２７】
2007534239.tif 000029
が得られる。すると、
【００７３】
【化２８】
2007534239.tif 000030
となり、これは、ΔＤと共に、（３．１１）を示唆する。これにより、補助定理１の証明が完了する。
【００７４】
補助定理１は、２つのリーフ兄弟ノードを統合する規則を提供する。ステージ１の目的は、量子化された画像の圧縮率とひずみとの間の効率的なトレードオフを与え得るハードディシジョン量子化器を生成することである。オリジナルのカラーパレットは有限であるため、全ての考えられる組み合わせを介して探すことにより、大域的に最適なハードディシジョン量子化器を求めることができる。しかしながら、そのような方法は高い計算複雑性を有するものであるため、実時間の圧縮に対しては、実現不可能である。補助定理１は、ツリー構造のハードディシジョン量子化器を設計するための代わりの欲張りな（ｇｒｅｅｄｙ）方法を提案している。Ｎ個のリーフノードを有するオリジナルの八分木に基づいて、Ｍ個のリーフノードが残されるまで２つのリーフ兄弟ノードをエントロピー制約コストの最小インクリメントを用いて繰り返し統合することが可能である。エントロピー制約階層的統合量子化（ＥＣＨＭＱ）と呼ばれるこの方法は高速であり、量子化された画像の圧縮率とひずみとの間の良好なトレードオフを与える。ＥＣＨＭＱの詳細な手順は、以下の通りである。
【００７５】
ステップ１：ｎ−ピクセルのオリジナルのカラー画像Ｘ＝（ｘ０，ｘ１，．．．，ｘｎ−１）を読み込み、カラーパレットＯ＝｛ｏ０，ｏｌ，．．．，ｏＮ−１｝および各色ｏｉの出現回数ｆｉを得る。ここに、０≦ｉ＜Ｎである。
【００７６】
ステップ２：異なるリーフノードΘｉとしてツリーに各色ｏｉを挿入することにより、八分木を構築する。各リーフノードΘｉ，０≦ｉ＜Ｎに対し、その重心ｃｉ＝ｏｉ、ＴＳＥ  ＤΘｉ＝０、出現回数Ｆｉ＝ｆｉ，およびコードワード長
【００７７】
【化２９】
2007534239.tif 000031
を計算する。
【００７８】
ステップ３：ｋ＝Ｎとする。
【００７９】
ステップ４：２つのリーフ兄弟ノードΘｉおよびΘｊのそれぞれに対し、式（３．１２）によって重心ｃｉｊを、等式（３．１１）によって増加したエントロピー制約コストを計算する。
【００８０】
ステップ５：リーフ兄弟ノードの全てのペアから、以前のステップで計算された増加エントロピー制約コストを最小化する２つのリーフ兄弟ノードΘｐおよびΘｑを選択する。ΘｐおよびΘｑのみがそれらの親の下の兄弟である場合、ΘｐとΘｑとを、ΘｐとΘｑとの親ノードに等しい新しいΘｐｑに統合し、そうでない場合、ΘｐとΘｑとの親ノードの下の新しい組み合わせの兄弟ノードに統合する。Θｐｑの重心ｃｐｑ、
【００８１】
【化３０】
2007534239.tif 000032
および、
【００８２】
【化３１】
2007534239.tif 000033
を計算する。
【００８３】
ステップ６：八分木からリーフノードΘｐおよびΘｑを除く。
【００８４】
ステップ７：ｋから１を減算する。
【００８５】
ステップ８：ｋ＝Ｍとなるまでステップ４から７を繰り返す。次に、異なるインデックスｉ∈Ｍｓｅｔを最後の八分木における残りのＭ個のリーフノードのそれぞれに割り当てる。リーフノードの重心の整数形式は、新しいカラーパレットにおける異なる色であり、そのリーフノードの全ての色は、そのリーフノードに対応するインデックスにマッピングされる。
【００８６】
所望の色数に到達したとき、オリジナルの画像を量子化するための最終的なエントロピー制約コストは、
【００８７】
【化３２】
2007534239.tif 000034
となる。ここに、ＪＮはＮ個の個別の色を有するオリジナルの画像のコストであり、ΔＪｉは２つの選択されたリーフノードを統合し、八分木のリーフノードの数をｉからｉ−１に減らしたときの増加したコストである。八分木において２つのリーフ兄弟ノードを統合するとき、増加した最小のエントロピー制約コストを常時求めることにより、ＥＣＨＭＱは、エントロピー制約コストを最小化するための部分的に最適な方法を提供する。
【００８８】
ＥＣＨＭＱは、純粋なひずみＴＳＥよりもむしろ、エントロピー制約コストを部分的に最小化することを目的とする。したがって、量子化された画像の圧縮率およびひずみは、ラグランジアン乗数λによって制御およびトレードオフされる。λの値が大きくなると、平均のひずみの値は低くなり、対応する圧縮率が大きくなる。実際、−λは、結果的として生じる圧縮率ひずみ曲線の勾配として解釈され得る。このため、ＥＣＨＭＱにおいて、量子化された画像の圧縮率とひずみとを変動させるために、トレードオフ因子として、λを用いる柔軟性を有している。
【００８９】
ＥＣＨＭＱの別の利点は、その計算の複雑性の低さにある。これを説明するために、まず、レベル７の３２個の親ノードの下に、全てがレベル８に配置されている総数２５６個のリーフノードを有していると仮定する。リーフノードの個数を２５５に減らすために、
【００９０】
【化３３】
2007534239.tif 000035
個のペアのリーフ兄弟ノードに対し、増加したエントロピー制約コストを計算しなければならない。八分木構造が使用されない場合、
【００９１】
【化３４】
2007534239.tif 000036
個のペアに対して、増加したコストを計算しなければならない。これは、［５］において、対ごとのクラスタ化に基本的に用いられる。式（３．１１）を次のように書き替える。
【００９２】
【化３５】
2007534239.tif 000037
リーフ兄弟ノードの各ペアに対する増加したコストの計算は、８つの加算、７つの減算、１０の乗算、１つの除算、１つの対数演算が含まれていることを見ることができる。各分岐に対してヤコビ法を採用するＴＳＥベースの階層的分岐方法［２］のような、その他の方法で用いられる高度な計算と比較して、ＥＣＨＭＱの計算複雑性は、非常に低い。さらに、ステップ８において、パレットおよびピクセルマッピングが容易に得られる。これもまた、文献中のその他の方法、例えば、パレット設計およびピクセルマッピングに顕著に大きな計算が含まれる文献［５］および［６］に含まれている方法にひけをとらない。
【００９３】
以下で説明するさらなる最適化を省略する場合、ＥＣＨＭＱの最後に得られる新しいカラーパレットおよびピクセルマッピングは、ＧＩＦ／ＰＮＧエンコーダによって直接的に符号化され得る。具体的には、以下において、ＰＮＧエンコーダをエントロピーコーダとして用い得る。ＰＮＧエンコーダを利用可能なＧＩＦエンコーダに置換することにより、ＧＩＦデコーダと互換性のある出力を容易に得ることができる。
【００９４】
（ＶＲＴＣＱ１）
このセクションでは、ソフトディシジョン量子化を採用することにより、ＧＩＦ／ＰＮＧデコーダとの互換性を維持する一方で、量子化されたカラー画像の圧縮率とひずみとをさらに同時に最適化する。初期のカラー画像符号化スキームとしてＥＣＨＭＱの最後に得られるハードディシジョン量子化器を用いることにより、ＶＲＴＳＥをカラー画像符号化に拡大し、ＶＲＴＣＱ１を得る。
【００９５】
ＶＲＴＣＱ１のＶＲＴＳＥ設定から始める。ＧＩＦ／ＰＮＧデコーダとの互換性を維持したいため、出力関数ｇは、どんな状態にも依存し得ない。換言すると、状態の集合Ｓは、ｓ０のみから構成される。この場合、状態推移関数ｆは省略され得、出力関数ｇは単にＭｓｅｔからＲＧＢ空間へのマッピングであり、カラーパレットのインデックスと色の間の相関関係を定義する。トレリスデコーダは、β＝ｇに退化（ｄｅｇｒａｄｅ）し得る。オリジナルのカラー画像ｘｎ＝（ｘ０，ｘｌ，．．．，ｘｎ−１）が与えられたとき、任意のシーケンスｕｎ＝（ｕ０，ｕ１，．．．，ｕｎ−１）∈Ｍｓｅｔｎに対し、
【００９６】
【化３６】
2007534239.tif 000038
と定義する。
【００９７】
（２．６）で与えられた上限を用いることにより、ひずみ制限の影響を受けるｒｋ（ｕｎ）が最小化され得る。具体的には、ｋ＝１とする。しかしながら、以下で説明されている手順は、任意のｋに容易に拡張可能である。
【００９８】
初期の出力関数ｇ（０）および推移確率関数Ｗ（０）は、ＥＣＨＭＱの最後で得られるカラーパレットおよびピクセルマッピングから導出され得る。ＶＲＴＣＱ１の詳細な手順は、以下に記述される通りである。
【００９９】
ステップ１：ｔ＝０と設定する。ＥＣＨＭＱから（ｕｎ）（０）、ｇ（０）、Ｗ（０）を得る。（ｕｎ）（０）＝（ｕ０（０），ｕ１（０），…，ｕｎ−１（０））はハードディシジョン量子化器から生じた量子化された画像のインデックスシーケンスであり、ｇ（０）（ｊ），０≦ｊ＜Ｍは、ＥＣＨＭＱの最後に得られる新しいカラーパレットにおけるインデックスｊに対応する色であり、任意のα∈Ｍｓｅｔおよびｗ∈Ｍｓｅｔに対し、
【０１００】
【化３７】
2007534239.tif 000039
となる。さらに、初期コスト
【０１０１】
【化３８】
2007534239.tif 000040
を計算する。
【０１０２】
ステップ２：ｇ（ｔ）およびＷ（ｔ）を固定する。ビタビアルゴリズムを用いることにより、ｇをｇ（ｔ）に、ＷをＷ（ｔ）に置き換えた式（２．４）を満たすシーケンス（ｕｎ）（ｔ＋１）＝（ｕ０（ｔ＋１），ｕ１（ｔ＋１），…，ｕｎ−１（ｔ＋１））を求める。
【０１０３】
ステップ３：（ｕｎ）（ｔ＋１）を固定する。インデックスシーケンス（ｕｎ）（ｔ＋１）は、推移確率関数と出力関数とを、任意のα∈Ｍｓｅｔおよびｗ∈Ｍｓｅｔに対し、
【０１０４】
【化３９】
2007534239.tif 000041
のように、また、任意のｕ∈Ｍｓｅｔに対し、
【０１０５】
【化４０】
2007534239.tif 000042
のように更新する。ここに、ｕｉ（ｔ＋１）＝ｕであるすべてのｉにわたってΣｕが取られる。ｘｉは、オリジナルの画像におけるｉ番目のピクセルの色を示すことに留意されたい。
【０１０６】
ステップ４：更新されたコスト
【０１０７】
【化４１】
2007534239.tif 000043
を計算する。
【０１０８】
ステップ５：Ｊ（ｔ）−Ｊｔ＋１≦ξになるまで（ξは所定の閾値）、ｔ＝０，１，２，．．．に対し、ステップ２から４までを繰り返す。
【０１０９】
次に、ｇ（ｔ＋１）および（ｕｎ）（ｔ＋１）を出力する。
【０１１０】
ステップ６：［１７］で記述されているＰＮＧエンコーダを用いることにより、カラーパレットｇ（ｔ＋１）とインデックスシーケンス（ｕｎ）（ｔ＋１）とを符号化する。
【０１１１】
ステップ２〜６は、便宜上、ＶＲＴＣＱ１のステージ２と呼ばれる。ここで使用されるビタビアルゴリズムは、図３に示されるグラフに図示される。ステージからステージへの増加したコストは、
−ｌｏｇＷ（ｕｉ│ｕｉ−１）＋ｄ（ｘｉ，ｇ（ｕｉ））  （４．１３）
のように計算される。ここに、任意の０≦ｉ＜ｎに対し、ｓｉ＝ｕｉである。ステージｉで状態ｊに到達する生存経路（ｓｕｒｖｉｖｏｒ  ｐａｔｈ）を求めるために、それぞれ３回の加算、３回の減算、および乗算が必要なＭ個の累積コストを比較する必要がある。したがって、全計算複雑性は、Ｏ（ｎＭ２）となる。
【０１１２】
ステージ２の最適性は、［１９］の定理３に示される。全体的に、ＶＲＴＣＱ１は、ＧＩＦ／ＰＮＧデコーダとの互換性を維持する一方で、量子化されたカラー画像の圧縮率とひずみとを同時にある程度最適化する。実験は、収束がある程度高速であること、すなわち、典型的には２回または３回のイタレーションの後、Ｊ（ｔ）がその制限に非常に近くなることを示している。
【０１１３】
このセクションの最後に、ＶＲＴＣＱ１の全体的な計算複雑性を考察する。ステージ２と比較して、ＶＲＴＣＱ１のステージ１、すなわちＥＣＨＭＱは、はるかに低い計算複雑性を有している。したがって、ＶＲＴＣＱ１の主な計算複雑性は、ステージ２、特にビタビアルゴリズムに存在する。ビタビアルゴリズムの各イタレーションは、計算複雑性Ｏ（ｎＭ２）を有するため、ＶＲＴＣＱ１の全体的な計算複雑性は、Ｍが大きいときには、実時間圧縮に対しては、非実用的にまで高くなり得る。したがって、Ｍの値が大きい場合には、計算複雑性を低減することが望ましい。この問題は、ＶＲＴＣＱ２によって処理される。
【０１１４】
（ＶＲＴＣＱ２）
Ｍの値が大きい場合にＶＲＴＣＱ１の計算複雑性を低減するために、（２．６）とは異なる方法により、Ｌｅｍｐｅｌ−Ｚｉｖコードワード長関数の上限を設定する。このために、ｋ次の経験的エントロピーｒｋ（ｕｎ）とは異なる新しい情報量を定義する。Ｍ’は、Ｍ未満の整数とする。ｂ（・）は、Ｍｓｅｔ＝｛０，１，．．．，Ｍ−１｝からＭ’ｓｅｔ＝｛０，１，．．．，Ｍ’−１｝へのマッピングとする。ｂの言葉では、ＭｓｅｔをＭ’個のグループ｛ｉ∈Ｍｓｅｔ：ｂ（ｉ）＝ｊ｝ｊ＝０，１，．．．，Ｍ’−１に分割する。任意のｕｎ＝（ｕ０，ｕ１，．．．，ｕｎ−１）∈Ｍｓｅｔｎに対し、ｂ（ｕｎ）＝（ｂ（ｕ０），ｂ（ｕ１），．．．，ｂ（ｕｎ−１））とする。
【０１１５】
【化４２】
2007534239.tif 000044
と定義する。
【０１１６】
ｒ（ｕｎ｜ｂ（ｕｎ））の大きさは、所与のｂ（ｕｎ）に対し、ｕｎの条件付き経験的エントロピーと呼ばれる。所望の情報量は、
【０１１７】
【化４３】
2007534239.tif 000045
のように定義される。ここに、ｒｋ（ｂ（ｕｎ））は、ｂ（ｕｎ）のｋ次の経験的エントロピーである。
【０１１８】
【化４４】
2007534239.tif 000046
を示すことは、難しくない。
【０１１９】
このため（２．６）を考慮することにより、Ｌｅｍｐｅｌ−Ｚｉｖコードワード長関数ｌＬＺは、以下のように上から制限され得る。
【０１２０】
【化４５】
2007534239.tif 000047
ひずみの制限を受けるｒｋ（ｕｎ）を最小化する代わりに、ＶＲＴＣＱ２のひずみ制限を受けるｒｋ＊（ｕｎ）を最小化する。ｎｒｋ（ｕｎ）が全てのｋ次の静的算術コードワード長関数ＬｋＷによって産出（ａｆｆｏｒｄ）される最小のコードワード長であるのと同様に、ｎｒｋ＊（ｕｎ）もまた、コードワード長関数に関連する。ＷＳ（ｓ｜ｓｋ）をＭ’ｋｓｅｔからＭ’ｓｅｔへの確率推移関数とし、ＷＵ（ｕ｜ｓ）をＭ’ｓｅｔからＭｓｅｔへの確率推移関数とする。任意のｕｎ＝（ｕ０，ｕ１，．．．，ｕｎ−１）∈Ｍｓｅｔｎに対し、
【０１２１】
【化４６】
2007534239.tif 000048
とする。
【０１２２】
まずｋ次の静的算術コードを推移確率ＷＳと共に用いてｂ（ｕｎ）を符号化し、次に条件付きでｂ（ｕｎ）が与えられたときにｕｎを符号化することによってどのｕｎが符号化されるのかを介することにより、ＬＷＳＷＵが可逆コードに対応するコードワード長関数であることを見ることは容易である。さらに、
【０１２３】
【化４７】
2007534239.tif 000049
を示すことは、難しくない。
【０１２４】
したがって、マッピングｂが与えられたとき、ＶＲＴＣＱ２における同時最適化の問題は、
【０１２５】
【化４８】
2007534239.tif 000050
のようになる。
【０１２６】
具体的には、ｋ＝１とする。しかし、全ての引数および以下の手順は、一般的なｋにも同様に適用される。ｇ、ＷＳ、ＷＵが与えられたとき、（５．１６）における内部最小化は、Ｏ（ｎＭ２）ではなくＯ（ｎＭ’２）の複雑性を有するビタビアルゴリズムによって解決され得る。これがあてはまる場合には、（５．１５）を考慮すると、
−ｌｏｇＷｓ（ｂ（ｕｔ）│ｂ（ｕｔ−１））−ｌｏｇＷＵ（ｕｔ│ｂ（ｕｔ））＋λｄ（ｘｔ，ｇ（ｕｔ））  （５．１７）
によってｔが増大するのにともなって、常時コストが増大することに留意されたい。
【０１２７】
（５．１７）において、ｂ（ｕｔ−１）を介して、第１項のみが過去に依存する。したがって、状態の集合
【０１２８】
【化４９】
2007534239.tif 000051
と、２つの連続するステージの状態の間の完全な関連性とを有するトレリスを構築し、内部最小化問題を解決するためにトレリスにビタビアルゴリズムを実行することが可能である。ビタビアルゴリズムを実行する前に、最小のサブコスト
【０１２９】
【化５０】
2007534239.tif 000052
を計算する。（ｓ，ｘ）の各組み合わせに対し、ｓ∈Ｍ’ｓｅｔおよびｘ∈Ｏとなる。最小のサブコスト、および、そのペア（ｓ，ｘ）に対して最小のサブコストを達成する対応する色インデックスｕは、ルックアップテーブルに保持される。トレリスのステージｔ−１における状態ｓｔ−１∈Ｍ’ｓｅｔから、トレリスのステージｔにおける状態ｓｔへの推移にわたるコストは、−ｌｏｇＷｓ（ｓｔ│ｓｔ−１）＋ｃ（ｓｔ，ｘｔ）である。ｘｎ＝（ｘ０，ｘ１，．．．，ｘｎ−１）が与えられたとき、ｓｎ＝（ｓ０，ｓ１，．．．，ｓｎ−１）∈Ｍ’ｓｅｔｎトレリスの最適経路である場合に、ｕｎ＝（ｕ０，ｕ１，．．．，ｕｎ−１）は（５．１６）において内部最小値を実現する最適なインデックスシーケンスである。ここに、ｕｔ∈｛ｉ：０≦ｉ＜Ｍ，ｂ（ｉ）＝ｓｔ｝は、最小コストｃ（ｓｔ，ｘｔ），ｔ＝０，１，．．．，ｎ−１を達成する。
【０１３０】
ＶＲＴＣＱ１と同様に、ＶＲＴＣＱ２は、反復的な方法で同時最適化の問題（５．１６）を解決する。ＶＲＴＣＱ２のステージ１は、マッピングｂを決定し、初期の出力関数ｇ（０）と、推移確率関数ＷＵ（０）およびＷＳ（０）を提供する。その後、最小化の問題を解決するために、ＶＲＴＣＱ２のステージ２は、代替的な手順を用いる。ＶＲＴＣＱ２の詳細な手順は、以下で記述される。
【０１３１】
（Ａ．ステージ１の手順）
ステップ１：オリジナルの画像でＥＣＨＭＱを実行して、Ｍ個のリーフノードを有する八分木ＴＭと、そのサイズＭのカラーパレットと、対応するハードディシジョンピクセルマッピングとを得る。
【０１３２】
ステップ２：ＴＭに基づいて、Ｍ’個のリーフノードが残されるまで、ＥＣＨＭＱのステップ４から７を繰り返す。
【０１３３】
ステップ３：八分木ＴＭから八分木ＴＭ’へのマッピングｂを決定する。ここに、Ｍ’個のリーフノードは、ステップ２で得られ、ＴＭ’はＴＭのサブツリーである。特に、ＴＭのｉ番目のリーフノードがＴＭ’のｊ番目のリーフノードにルーティングされるＴＭのサブツリーに存在する場合、ｂ（ｉ）＝ｊ，ｉ∈Ｍｓｅｔ，ｊ∈Ｍ’ｓｅｔとなる。
【０１３４】
（Ｂ．ステージ２の手順）
ステップ１：ｔ＝０に設定する。ＶＲＴＣＱ２のステージ１から、ｂ、（ｕｎ）（０）、（ｓｎ）（０）、ｇ（０）、ＷＵ（０）、およびＷｓ（０）を得る。ここに、（ｕｎ）（０）＝（ｕ０（０），ｕ１（０），…，ｕｎ−１（０））は、ハードディシジョンピクセルマッピングから得られるインデックスシーケンスであり、０≦ｕ＜Ｍの（ｓｎ）（０）＝（ｓ０（０），ｓ１（０），…，ｓｎ−１（０））＝ｂ（（ｕｎ）（０），ｇ（０）（ｕ））は、ステージ１のステップ１で得られる新しいカラーパレットにおけるインデックスｕに対応する色であり、
【０１３５】
【化５１】
2007534239.tif 000053
および
【０１３６】
【化５２】
2007534239.tif 000054
となる。
【０１３７】
さらに、初期コスト
【０１３８】
【化５３】
2007534239.tif 000055
を計算する。
【０１３９】
ステップ２：ｇ（ｔ）およびＷＵ（ｔ）を固定する。ルックアップテーブルを構築する。（ｓ，ｘ）、但しｓ∈Ｍ’ｓｅｔおよびｘ∈Ｏの各ペアに対し、最小サブコスト
【０１４０】
【化５４】
2007534239.tif 000056
を計算する。ｃ（ｔ）（ｓ，ｘ）を達成するカラーインデックスｕ∈｛ｉ：０≦ｉ＜Ｍ，ｂ（ｉ）＝ｓ｝を記録する。
【０１４１】
ステップ３：ｇ（ｔ）、ＷＵ（ｔ）、およびＷＳ（ｔ）を決定する。ビタビアルゴリズムを用いることにより、トレリス（ｓｎ）（ｔ＋１）＝（ｓ０（ｔ＋１），ｓ１（ｔ＋１），．．．，ｓｎ−１（ｔ＋１））を通る最適パスを求める。上記最適パスは、ｂおよびルックアップテーブルと共に、ｇをｇ（ｔ）に、ＷＵをＷＵ（ｔ）に置換しＷｓをＷｓ（ｔ）に置換した（５．１６）における内部最小化を達成する最適なインデックスシーケンス（ｕｎ）（ｔ＋１）＝（ｕ０（ｔ＋１），ｕ１（ｔ＋１），．．．，ｕｎ−１（ｔ＋１））を決定する。
【０１４２】
ステップ４：（ｕｎ）（ｔ＋１）および（ｓｎ）（ｔ＋１）を固定する。これら２つのシーケンスは、以下のように推移確率関数と出力関数とを更新する。
【０１４３】
【化５５】
2007534239.tif 000057
および
【０１４４】
【化５６】
2007534239.tif 000058
ここに、ｕｉ（ｔ＋１）＝ｕである全てのｉにわたってΣｕを取る。
【０１４５】
ステップ５：更新されたコスト
【０１４６】
【化５７】
2007534239.tif 000059
を計算する。
【０１４７】
ステップ６：Ｊ（ｔ）−Ｊ（ｔ＋１）≦ξになるまで、ｔ＝０，１，２，．．．に対し、ステップ２から５を繰り返す。ここに、ξは所定の閾値である。
【０１４８】
次に、ｇ（ｔ＋１）および（ｕｎ）（ｔ＋１）を出力する。
【０１４９】
ステップ７：カラーパレットｇ（ｔ＋１）およびインデックスシーケンス（ｕｎ）（ｔ＋１）を［１７］からＰＮＧエンコーダによって符号化する。
【０１５０】
ステップ３で用いられるビタビアルゴリズムは、図４のグラフに図示されている。グラフにおいて、各円はグループを示し、円内の黒い点は、グループ内の全てのカラーインデックスｕ∈Ｍｓｅｔを示す。
【０１５１】
ＶＲＴＣＱ１と同様に、ＶＲＴＣＱ２の主な計算複雑性は、ステージ２に存在する。ＶＲＴＣＱ１のステージ２と比較すると、ＶＲＴＣＱ２のステージ２は、特別なステップであるステップ２を有しているが、このステップは、計算上は強いて用いられない。実際、その計算複雑性は、オリジナルの画像のサイズｎに依存しないＯ（ＮＭ）であるため、ｎの値が大きいときのビタビアルゴリズムの複雑性と比較して、ごくわずかである。ＶＲＴＣＱ２のステージ２のステップ３のビタビアルゴリズムは、Ｏ（ｎＭ’２）の計算複雑性を有し、これは、ＶＲＴＣＱ１で用いられるビタビアルゴリズムの計算複雑性Ｏ（ｎＭ２）と比べて悪くない。したがって、Ｍ’＜＜Ｍであるとき、ＶＲＴＣＱ２は、ＶＲＴＣＱ１よりもずっと高速になる。加えて、一旦Ｍ’が決定されると、ＶＲＴＣＱ２の計算複雑性は、Ｍとは多かれ少なかれ独立になる。このことは、ＶＲＴＣＱ２を色が豊富な画像に対して魅力のあるものにする。Ｌｅｍｐｅｌ−Ｚｉｖコードワード長関数を上から制限するには、緩い制限（ｌｏｏｓｅ  ｂｏｕｎｄ）が用いられるため、ＶＲＴＣＱ２で支払われる対価は、圧縮率とひずみとの間のトレードオフの言葉では、圧縮性能のわずかな損失である。
【０１５２】
図５を参照すると、図１のコンピュータシステム１０のＣＰＵ１６がブロック図で示されている。図示されているように、ＣＰＵ１６は、ハードディシジョンモジュール４０とソフトディシジョンモジュール４２とを含んでいる。ハードディシジョンモジュール４０は、上記で説明したように、ＥＣＨＭＱを提供する。ソフトディシジョンモジュール４２は、上記で説明したように、ＶＲＴＣＱ１とＶＲＴＣＱ２との両方を提供する。
【０１５３】
上記で説明したように、ハードディシジョンモジュール４０は、八分木構造を構築するためのノード作成サブモジュールと、リーフノードを選択および統合するためのノード統合サブモジュールと、リーフノードのペアの潜在的な統合に対して、そのような統合の各々に対するエントロピー制約コストインクリメントを計算するためのコスト計算サブモジュールとを含む。ハードディシジョンモジュール４０と同様に、ソフトディシジョンモジュール４２は、ソフトディシジョンモジュール４２によるソフトディシジョン最適化の各イタレーション後に、コストのインクリメントの低下を決定するためのコスト計算サブモジュールを含む。
【０１５４】
本発明のその他のバリエーションと改変とが可能である。例えば、上記で説明されたように、その他のソフトディシジョン最適化においてＶＲＴＣＱを使用せずに、ＥＣＨＭＱのみを使用し、ハードディシジョンピクセルマッピングが提供され得る。代替的に、初期のハードディシジョンピクセルマッピングを実行するために、ＥＣＨＭＱを使用せずに、ＶＲＴＣＱが使用され得る。代わりに、その他いくつかの初期のハードディシジョン手順が提供され得る。さらに、その他のソフトディシジョン最適化方法は、ＶＲＴＣＱの代わりにＥＣＨＭＱと組み合わせて使用され得る。さらに、上記の説明は、計算複雑性を抑え、例えばＧＩＦ／ＰＮＧデコーダのような標準的なデコーダとの互換性を維持する一方で、量子化ひずみと圧縮率との両方をいかにして同時に処理するかに主に向けられてきたが、当業者は、その他の文脈においても同様に、ＥＣＨＭＱとＶＲＴＣＱの両方がカラー画像データの圧縮に適用され得ることを理解し得る。このような全ての改変またはバリエーションは、本明細書に添付された請求項によって定義されるような本発明の領域および範囲内に存在すると考えることができる。
【図面の簡単な説明】
【０１５５】
【図１】図１は、ブロック図によって、本発明の好適な実施例にしたがうコンピュータシステムを示している。
【図２】図２は、グラフによって、本発明の好適な実施例にしたがう八分木構造を示す。
【図３】図３は、グラフによって、本発明のソフトディシジョン最適化に関する局面の第１の改変にしたがうビタビアルゴリズムを示す。
【図４】図４は、グラフによって、本発明のソフトディシジョン最適化に関する局面の第２の改変にしたがうビタビアルゴリズムを示す。
【図５】図５は、ブロック図によって、図１のコンピュータシステムのＣＰＵを示す。
【図１】
2007534239.tif 000060
【図２】
2007534239.tif 000061
【図３】
2007534239.tif 000062
【図４】
2007534239.tif 000063
【図５】
2007534239.tif 000064
【国際調査報告】
2007534239.tif 000065
2007534239.tif 000066
2007534239.tif 000067