(57)【要約】  複数の画像要素（６１０）を含む画像ブロック（６００）は、少なくとも１つの基準符号語（７２０；７５０）、間隔符号語（７１０；７４０）及びインデックスシーケンス（７３０；７６０）に圧縮される。結果として得られる圧縮ブロック（７００）の合計のビット長は一定であるが、それら符号語（７１０；７２０；７３０；７４０）及びインデックスシーケンス（７３０；７６０）のうち少なくとも２つのそれぞれのビット長は、画像要素（６１０）の元のベクトル成分に基づいて動的に規定される。基準符号語（７２０；７５０）は基準値（１０）を表し、間隔符号語（７１０；７４０）は間隔（２０）を表す。この間隔（２０）は、基準値（１０）と相関する複数の成分値（５０）を含む。インデックスシーケンス（７３０；７５０）は、複数の利用可能な値（５０）から選択された１つの成分値を画像要素（６１０）毎に表す。
2009534914.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像要素に関連付けられている特徴を表現するそれぞれの特徴ベクトルを有する当該複数の画像要素の画像ブロックを圧縮する方法であって、
前記それぞれの特徴ベクトルのベクトル成分の少なくとも一部に基づいて、基準符号語、間隔符号語、及びインデックスシーケンスのうち少なくとも２つのそれぞれのビット分解能を、それぞれのビット分解能の合計が固定であるように、規定する工程と、
前記それぞれのベクトル成分の少なくとも一部に基づいて、基準値の表現として前記基準符号語を決定する工程と、
前記それぞれのベクトル成分の少なくとも一部に基づいて、前記基準値と相関する複数の成分値を含む間隔の表現として、前記間隔符号語を決定する工程と、
前記複数の成分値から選択された１つの成分値を、前記複数の画像要素中の画像要素毎に示す、前記インデックスシーケンスを決定する工程と
を備えることを特徴とする方法。
【請求項２】
前記規定する工程は、前記それぞれの特徴ベクトルの前記ベクトル成分の分布に基づいて、前記それぞれのビット分解能を規定する工程を備えることを特徴とする、請求項１に記載の方法。
【請求項３】
前記規定する工程は、
前記それぞれの特徴ベクトルのうち最大のベクトル成分を識別する工程と、
前記それぞれの特徴ベクトルのうち最小のベクトル成分を識別する工程と、
前記最大のベクトル成分と前記最小のベクトル成分との比較に基づいて前記それぞれのビット分解能を規定する工程と
を備えることを特徴とする、請求項１又は２に記載の方法。
【請求項４】
前記規定する工程は、
前記それぞれのベクトル成分の前記少なくとも一部に基づいて前記間隔符号語に対する前記ビット分解能を規定する工程と、
事前定義済み最大分解能値と、前記間隔符号語に対して規定された前記ビット分解能と、の差分として前記基準符号語に対する前記ビット分解能を計算する工程と
を備えることを特徴とする、請求項１乃至３の何れか１項に記載の方法。
【請求項５】
前記間隔符号語を決定する前記工程は、前記それぞれのベクトル成分の少なくとも一部と、前記間隔符号語に対して規定された前記ビット分解能とに基づいて、前記間隔の表現として前記間隔符号語を決定する工程を備えることを特徴とする、請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記間隔符号語を決定する前記工程は、
前記それぞれの特徴ベクトルのうち最大のベクトル成分を識別する工程と、
前記それぞれの特徴ベクトルのうち最小のベクトル成分を識別する工程と、
前記最大のベクトル成分と、前記最小のベクトル成分と、の差分の表現として前記間隔符号語を決定する工程と
を備えることを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
前記間隔符号語を決定する前記工程は、前記最大のベクトル成分と前記最小のベクトル成分との前記差分に基づいて、複数の事前定義済み間隔符号語のセットから前記間隔符号語を識別する工程を備えることを特徴とする、請求項６に記載の方法。
【請求項８】
前記複数の事前定義済み間隔符号語の各々は事前定義済みビット分解能を有し、前記複数の事前定義済み間隔符号語のうちの第１の間隔符号語のビット分解能は、前記複数の事前定義済み間隔符号語のうちの第２の間隔符号語のビット分解能とは異なることを特徴とする、請求項７に記載の方法。
【請求項９】
前記基準符号語を決定する前記工程は、前記それぞれのベクトル成分の少なくとも一部と、前記基準符号語に対して規定された前記ビット分解能とに基づいて、前記基準値の表現として前記基準符号語を決定する工程を備えることを特徴とする、請求項１乃至８の何れか１項に記載の方法。
【請求項１０】
前記基準符号語を決定する前記工程は、前記それぞれのベクトル成分の前記少なくとも一部と、前記基準符号語に対して規定された前記ビット分解能に基づいて、前記間隔の開始点、前記間隔の中間点、及び前記間隔の終了点のうちの少なくとも１つとして、前記基準符号語を決定する工程を備えることを特徴とする、請求項１乃至９の何れか１項に記載の方法。
【請求項１１】
前記インデックスシーケンスを決定する前記工程は、前記複数の成分値から選択された１つの成分値を前記複数の画像要素の画像要素毎に示す前記インデックスシーケンスを、当該インデックスシーケンスに対して規定された前記ビット分解能に基づいて決定する工程を備えることを特徴とする、請求項１乃至１０の何れか１項に記載の方法。
【請求項１２】
前記インデックスシーケンスを決定する前記工程は、前記複数の成分値から選択された１つの成分値を表す成分インデックスを、前記複数の画像要素の画像要素毎に提供する工程を備えることを特徴とする、請求項１乃至１１の何れか１項に記載の方法。
【請求項１３】
前記インデックスシーケンスを決定する前記工程は、
前記複数の成分値のうち、前記画像要素の前記ベクトル成分を最適に表す成分値を、前記複数の画像要素の画像要素毎に選択する工程と、
ルックアップテーブルの複数の画像要素の集合に対する合成成分インデックスを、前記集合の前記画像要素に対する前記選択された成分値に基づいて識別する工程と
を備えることを特徴とする、請求項１乃至１１の何れか１項に記載の方法。
【請求項１４】
複数の画像要素を含む画像ブロックの圧縮表現を処理する方法であって、前記圧縮表現は基準符号語、間隔符号語及びインデックスシーケンスを含み、当該方法は、
前記圧縮表現の少なくとも一部のビットパターンに基づいて、前記圧縮表現の前記基準符号語及び前記圧縮表現の前記間隔符号語のうち、一方を識別する工程と、
前記基準符号語及び前記間隔符号語のうち前記識別された一方に基づいて、前記圧縮表現の前記基準符号語及び前記圧縮表現の前記間隔符号語のうち、他方を識別する工程と、
前記基準符号語に基づいて基準値を決定する工程と、
前記基準値及び前記間隔符号語に基づいて複数の成分値を決定する工程と、
前記画像ブロックの少なくとも１つの画像要素に対して、前記インデックスシーケンスに基づいて、前記複数の成分値から１つの成分値を選択する工程と
を備えることを特徴とする方法。
【請求項１５】
前記基準符号語及び前記間隔符号語のうち他方を識別する前記工程は、前記基準符号語及び前記間隔符号語のうち前記識別された一方の、決定されたビット長に基づいて、前記圧縮表現の前記基準符号語及び前記圧縮表現の前記間隔符号語のうち他方を識別する工程を備えることを特徴とする、請求項１４に記載の方法。
【請求項１６】
前記識別する工程は、
事前定義済みビットパターンに達するまで、前記圧縮表現を解析する工程と、
前記圧縮表現の前記解析部分に基づいて、前記基準符号語及び前記間隔符号語のうち前記一方を規定する工程と、
前記間隔符号語及び前記基準符号語のビット長は固定であり、前記基準符号語及び前記間隔符号語のうち前記他方として、前記圧縮表現の後続する部分を規定する工程と
をまとめて備えることを特徴とする、請求項１４又は１５に記載の方法。
【請求項１７】
前記複数の成分値を決定する前記工程は、
前記間隔符号語に基づいて間隔長を決定する工程と、
前記間隔長及び前記基準値に基づいて前記複数の成分値を計算する工程と
を備えることを特徴とする、請求項１４乃至１６の何れか１項に記載の方法。
【請求項１８】
前記計算する工程は、
前記間隔長及び前記基準値に基づいて前記間隔の開始点を決定する工程と、
前記間隔長及び前記基準値に基づいて前記間隔の終了点を決定する工程と、
前記開始点及び前記終了点に基づいて前記複数の成分値を計算する工程と
を備えることを特徴とする、請求項１７に記載の方法。
【請求項１９】
前記計算する工程は、前記開始点及び前記終了点の線形結合として前記複数の成分値を計算する工程を備えることを特徴とする、請求項１８に記載の方法。
【請求項２０】
複数の画像要素に関連付けられている特徴を表現するそれぞれの特徴ベクトルを有する当該複数の画像要素を含む画像ブロックを圧縮するブロック圧縮器であって、
前記それぞれの特徴ベクトルのベクトル成分の少なくとも一部に基づいて、基準符号語、間隔符号語及びインデックスシーケンスのうち少なくとも２つのそれぞれのビット分解能を規定するように構成され、前記それぞれのビット分解能の合計が固定されるようにする分解能定義器と、
前記それぞれのベクトル成分の少なくとも一部に基づいて、基準値の表現として前記基準符号語を決定するように構成された基準量子化器と、
前記それぞれのベクトル成分の少なくとも一部に基づいて、前記基準値と相関する複数の成分値を含む間隔の表現として、前記間隔符号語を決定するように構成された間隔量子化器と、
前記複数の成分値から選択された１つの成分値を、前記複数の画像要素の画像要素毎に示す前記インデックスシーケンスを決定するように構成されたインデックス量子化器と
を備えることを特徴とする、ブロック圧縮器。
【請求項２１】
前記分解能定義器は、前記それぞれの特徴ベクトルの前記ベクトル成分の分布に基づいて前記それぞれのビット分解能を規定するように構成されていることを特徴とする、請求項２０に記載のブロック圧縮器。
【請求項２２】
ｉ）前記それぞれの特徴ベクトルのうち最大のベクトル成分を識別し、ｉｉ）前記それぞれの特徴ベクトルのうち最小のベクトル成分を識別するように構成された成分識別器を更に備え、
前記分解能定義器は、前記成分識別器により識別された前記最大のベクトル成分と前記最小のベクトル成分との比較に基づいて、前記それぞれのビット分解能を規定するように構成されていることを特徴とする、請求項２０又は２１に記載のブロック圧縮器。
【請求項２３】
前記分解能定義器は、前記それぞれのベクトル成分のうち前記少なくとも一部に基づいて前記間隔符号語に対する前記ビット分解能を規定するように構成されており、
前記分解能定義器は、事前定義済み最大分解能値と、前記分解能定義器により前記間隔符号語に対して規定された前記ビット分解能との差分として、前記基準符号語に対する前記ビット分解能を計算するように構成された分解能計算器を更に備えることを特徴とする、請求項２０乃至２２の何れか１項に記載のブロック圧縮器。
【請求項２４】
前記間隔量子化器は、前記それぞれのベクトル成分のうち少なくとも一部と、前記分解能定義器により前記間隔符号語に対して規定された前記ビット分解能とに基づいて、前記基準値と相関する複数の成分値を含む間隔の表現として前記間隔符号語を決定するように構成されていることを特徴とする、請求項２０乃至２３の何れか１項に記載のブロック圧縮器。
【請求項２５】
ｉ）前記それぞれの特徴ベクトルの最大のうち最大のベクトル成分を識別し、ｉｉ）前記それぞれの特徴ベクトルのうち最小のベクトル成分を識別するように構成された成分識別器を更に備え、
前記間隔量子化器は、前記成分識別器により識別された前記最大のベクトル成分と前記最小のベクトル成分との差分の表現として、前記間隔符号語を決定するように構成されていることを特徴とする、請求項２０乃至２４の何れか１項に記載のブロック圧縮器。
【請求項２６】
前記基準量子化器は、前記それぞれのベクトル成分のうち少なくとも一部と、前記分解能定義器により前記基準符号語に対して規定された前記ビット分解能とに基づいて、前記基準値の表現として前記基準符号語を決定するように構成されていることを特徴とする、請求項２０乃至２５の何れか１項に記載のブロック圧縮器。
【請求項２７】
前記基準量子化器は、前記それぞれのベクトル成分のうち前記少なくとも一部と、前記基準符号語に対して規定された前記ビット分解能とに基づいて、前記間隔の開始点、前記間隔の中間点及び前記間隔の終了点のうちの少なくとも１つとして前記基準符号語を決定するように構成されていることを特徴とする、請求項２０乃至２６の何れか１項に記載のブロック圧縮器。
【請求項２８】
前記インデックス量子化器は、前記複数の成分値から選択された１つの成分値を前記複数の画像要素の画像要素毎に示す前記インデックスシーケンスを、前記分解能定義器により当該インデックスシーケンスに対して規定された前記ビット分解能に基づいて、決定するように構成されていることを特徴とする、請求項２０乃至２７の何れか１項に記載のブロック圧縮器。
【請求項２９】
前記インデックス量子化器は、前記複数の成分値から選択された１つの成分値を表す成分インデックスを、前記複数の画像要素の画像要素毎に提供するように構成されていることを特徴とする、請求項２０乃至２８の何れか１項に記載のブロック圧縮器。
【請求項３０】
前記インデックス量子化器は、
前記複数の成分値のうち前記画像要素の前記ベクトル成分を最適に表す成分値を、前記複数の画像要素の画像要素毎に選択するように構成された値選択器と、
ルックアップテーブルの複数の画像要素の集合に対する合成成分インデックスを、前記値選択器により選択された前記集合の前記画像要素に対する前記成分値に基づいて識別するように構成されたインデックス識別器と、
を備えることを特徴とする、請求項２０乃至２９の何れか１項に記載のブロック圧縮器。
【請求項３１】
複数の画像要素を備える画像ブロックの圧縮表現であって、当該圧縮表現が基準符号語、間隔符号語及びインデックスシーケンスを含むような圧縮表現、を処理するブロック伸張器であって、
ｉ）前記圧縮表現の少なくとも一部のビットパターンに基づいて、前記圧縮表現の前記基準符号語及び前記間隔符号語のうち一方を識別するように構成された符号語識別器であって、ｉｉ）前記圧縮表現において前記符号語識別器により識別された前記基準符号語及び前記間隔符号語のうち前記一方に基づいて、前記圧縮表現の前記基準符号語及び前記間隔符号語のうち他方を識別するように構成された、符号語識別器と、
前記基準符号語に基づいて基準値を決定するように構成された基準値生成器と、
前記基準値生成器により決定された前記基準値、及び前記間隔符号語に基づいて、複数の成分値を決定するように構成された成分値生成器と、
前記画像ブロックの少なくとも１つの画像要素に対して、前記インデックスシーケンスに基づいて、前記複数の成分値から１つの成分値を選択するように構成された値選択器と
を備えることを特徴とするブロック伸張器。
【請求項３２】
前記符号語識別器は、前記圧縮表現において前記符号語識別器により識別された前記基準符号語及び前記間隔符号語のうち前記一方の決定されたビット長に基づいて、前記圧縮表現の前記基準符号語及び前記間隔符号語のうち他方を識別するように構成されていることを特徴とする請求項３１に記載のブロック伸張器。
【請求項３３】
前記符号語識別器は、
事前定義済みビットパターンに達するまで、前記圧縮表現を解析するように構成されたビット解析器と、
ｉ）前記圧縮表現の前記解析部分に基づいて前記基準符号語及び前記間隔符号語のうち前記一方を規定し、ｉｉ）ビット長が固定の前記基準符号語及び前記間隔符号語のうち前記他方として前記圧縮表現の後続する部分を規定するように構成された符号語定義器と
を備えることを特徴とする、請求項３１又は３２記載にのブロック伸張器。
【請求項３４】
前記成分値生成器は、
前記間隔符号語に基づいて間隔長を決定するように構成された間隔生成器と、
前記間隔生成器により決定された前記間隔長及び前記基準値生成器により決定された前記基準値に基づいて、前記複数の成分値を計算するように構成された値計算器と
を備えることを特徴とする、請求項３１乃至３３の何れか１項に記載のブロック伸張器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に画像処理に関し、特に、画像を符号化及び復号化する方法及びシステムに関する。
【背景技術】
【０００２】
３次元グラフィックのリアルタイムレンダリングは、ゲーム、マンマシンインタフェース、メッセージング及びｍコマースを含む移動端末上でのいくつかの魅力的な応用例を有する。３次元レンダリングは計算コストの高いタスクであるため、多くの場合、十分な性能を達成するために専用のハードウェアが構築される必要がある。従って、そのハードウェアアーキテクチャの複雑さを軽減し且つそのハードウェアアーキテクチャの帯域幅の使用量を低減する革新的な方法が非常に重要である。
【０００３】
特に移動電話に対する主な障害はメモリ帯域幅である。メモリ帯域幅の使用量を低減する一般的な技術は、テクスチャ圧縮である。テクスチャリングとは、レンダリングされた三角形上に画像（ここでは、テクスチャと呼ばれる）を「貼り付ける」処理を示す。テクスチャがメモリにおいて圧縮され、アクセス中にそれらテクスチャが伸張される場合、大量の帯域幅の使用は回避される。
【０００４】
殆どのテクスチャ圧縮方式は、写真等の画像形式のデータを重視している。しかし、プログラマブルシェーダの出現により、従来の写真画像だけでなく他の多くの種類のデータに対してもテクスチャが使用され始めた。従って、バンプマッピングは、安価な方法で幾何学的物体に細部の錯覚を与える技術として普及した。より詳細には、バンプマップ又は法線マップと呼ばれるテクスチャが面法線を摂動するために各画素において使用される。法線マップを生成する一般的な方法では、ポリゴンの総数が多いモデルから開始し、幾何学的単純化アルゴリズムを使用して複雑さの低いモデルを作成する。それら２つのモデル間の「差分」は、法線マップに「焼き付け」られる。リアルタイムレンダリングの場合、法線マップは複雑さの低いモデルに適用され、より緻密な外観を与える。例えば文献［１］は、法線マップを使用して、三角形の総数が非常に多いモデル（１５０００個のポリゴン）から品質を維持しつつ三角形の総数が非常に少ないモデル（１０００個のポリゴン）にすることが可能な方法を示す。
【０００５】
移動デバイス及び移動端末はＰＣシステムより低い計算性能を有するため、ポリゴンの総数が少ないモデルを使用できることは、当然移動デバイス及び端末にとって非常に魅力的である。
【０００６】
しかし、１つの問題は、利用可能なテクスチャ圧縮方法が写真画像を念頭に作成されており、データが法線マップ等の他のデータである場合に適切に動作しないことである。例えば文献［１］を参照すると、Ｓ３ＴＣ（ＤＸＴＣと同一）［２］が法線マップを圧縮するために採用されたが、その結果、ブロックアーティファクトが発生した。
【０００７】
今日、殆どの場合、三角形等のレンダリング・プリミティブのローカル接空間（Ｘ，Ｙ，Ｚ）においてバンプマッピングが実行される。法線の長さは関係ないため、単位法線が採用される。従って、問題はトリプレット（Ｘ，Ｙ，Ｚ）を圧縮することである。ここで、Ｘ２＋Ｙ２＋Ｚ２＝１である。最も単純な方式は、Ｘ，Ｙ，ＺをＲＧＢ（赤色、緑色、青色）として処理し、Ｓ３ＴＣ／ＤＸＴ１を使用して圧縮することであるが、品質は非常に低下する。
【０００８】
別の方法は、Ｘ及びＹのみを圧縮し、式１を使用してＺを算出することである：
【０００９】
【数１】
2009534914.tif 000003
【００１０】
Ｘ及びＹに集中することにより、歪みを低下できる。品質を更に向上するために、ＤＸＴ５が使用できる。通常、ＤＸＴ５はアルファテクスチャ、すなわちＲＧＢＡテクスチャに対して使用されるバージョンのＳ３ＴＣである。ここで、ＲＧＢは共に符号化され、アルファ成分（Ａ）は個別に符号化される。従って、１つの方法では、アルファチャネルを使用してＸを符号化し且つＧチャネルを使用してＹを符号化する。Ｇに最高の品質を与えるために、Ｒ及びＢは使用されていない。しかし、これは依然として十分な品質を与えない。
【００１１】
実際、滑らかな表面の場合、非圧縮のＲＧＢ８８８／ＸＹＺ８８８でさえもいくつかの物体に対しては十分な品質を与えないことが分かる。特に、滑らかな表面に対しては、８ビットより多くのビット数が必要とされる。従って、ＡＴＩ  Ｔｅｃｈｎｏｌｏｇｉｅｓは、多くの場合にＸＹＺ８８８より高い品質を可能にする圧縮形式である３Ｄｃ（登録商標）［１］を開発した。
【００１２】
ＤＸＴ５と同様に、Ｘ及びＹのみが圧縮され、Ｚは計算される。Ｘ及びＹは別個に圧縮される。Ｘ値は４×４画素のブロックにグループ化される。それらの値の範囲は、−１２７．０００〜＋１２７．０００（あるいは、０〜２５５）であるが、多くの場合、それら値はある間隔でクラスタ化される。３Ｄｃはそのことを利用し、１６ビットを使用してその値を特定する。１６ビットのうち８ビットは間隔の開始に対するものであり、８ビットは間隔の終了に対するものである。
【００１３】
この間隔内において、各値は３ビットずつ使用して特定される。これは、間隔内の８つの再構成レベルが可能であることを意味する。多くの場合に間隔内の分布が略均等であるという仮定を反映して、再構成レベルは常に均等に離間される。
【００１４】
合計すると、間隔を特定するのに１６ビットが使用され、個々の画素に対する再構成レベルを特定する際に３×１６＝４８ビットが使用される。従って、Ｘデータの４×４ブロックは６４ビットに圧縮される。同一の符号化がＹに対しても有効であり、合計で１２８ビット、すなわち画素毎に８ビットが使用される。
【００１５】
３ＤｃはＤＸＴ１又はＤＸＴ５より非常に高い品質をもたらすが、その品質では依然として十分でない可能性がある。間隔は８ビットで特定され、可能な最小の間隔は、間隔の開始と終了との間に１だけ差分がある場合であり、例えば間隔［７７，７８］又は［−３，−４］である。この場合、それらの間に８つの再構成レベルが存在し、これは別の３ビットを意味する。従って、論理的には最大分解能は成分毎に８＋３＝１１ビットである。これは、ゆっくりと変動する表面に対しては不十分だろう。
【発明の開示】
【課題を解決するための手段】
【００１６】
従って、一般に、法線マップの形式の画像及び画像要素に関連する特性座標を有する他の種類の画像を圧縮及び伸張する時の品質を向上することに対する要求がある。
【００１７】
本発明の一般的な目的は、画像符号化／圧縮方法及びシステム、並びに画像復号化／伸張方法及びシステムを提供することである。
【００１８】
この目的及び他の目的は、添付の請求の範囲により規定されるような本発明により満たされる。
【００１９】
簡単に説明すると、本発明は、画像を圧縮（符号化）し、圧縮（符号化）画像を伸張（復号化）する形式の画像処理を含む。
【００２０】
本発明によると、圧縮される画像は、複数の画像要素（画素、テクスチャ要素すなわちテクセル、又は体素すなわちボクセル）を備える複数の画像ブロックに分解される。１つの画像ブロックは、１６個の画像要素を含むのが好ましく、ｍ＝４−ｎ及びｎ＝０，１，２，３，４として画像要素２ｍ×２ｎ個分のサイズを有するか、あるいはｍ、ｎ、ｐの全てがゼロではないという条件を伴ってｍ，ｎ，ｐ＝０，１，２，３，４として画像要素２ｍ×２ｎ２ｐ個分のサイズを有する。ブロック中の各画像要素は、２つ又は３つの特徴ベクトル成分を有する特徴ベクトルにより特徴付けられる。その後、画像ブロックは圧縮される。
【００２１】
ブロック圧縮において、各ビット分解能は、各ベクトル成分毎に、並びに基準符号語、間隔符号語及びインデックスシーケンスのうちの少なくとも２つ毎に動的に規定される。このビット分解能又はビット長の選択がブロック毎に実行され、これは、第１の画像ブロックが所定の長さの第１の基準符号語を有し、第２の画像ブロックが別のビット長の第１の基準符号語を有してもよいことを意味する。この可変ビット長符号化にも関わらず、圧縮ブロックの各合計サイズは一定であり同等である。例えばこれは、間隔符号語に更に多くのビットを使用することにより、同一のベクトル成分に関係する基準符号語に使用されうるビット数が少なくなることを意味する。
【００２２】
基準符号語は、ブロック中の画像要素のベクトル成分の少なくとも一部に基づいて基準値の表現として決定される。同様に、間隔符号語は、基準値と相関する複数の成分値を含む間隔の表現として決定される。この間隔符号語もまた、ブロック中のベクトル成分の少なくとも一部に基づいて決定される。インデックスシーケンスは、ブロック中の各画像要素に対して、複数の成分値から選択された１つの成分値を示すと決定される。
【００２３】
各画像要素がＸ成分及びＹ成分等の少なくとも２つのベクトル成分と関連付けられるのが好ましいため、第１の（Ｘ）基準符号語及び第２の（Ｙ）基準符号語、第１の（Ｘ）間隔符号語及び第２の（Ｙ）間隔符号語、並びに第１の（Ｘ）インデックスシーケンス及び第２の（Ｙ）インデックスシーケンスが生成され、共に圧縮画像ブロックを形成するのが好ましい。本発明の可変ビット長符号化により、第１の基準符号語及び第２の基準符号語のビット長は、所定のブロックに対して必ずしも同一である必要はなく、異なる画像ブロック間で異なってもよい。同様のことが、第１の間隔符号語及び第２の間隔符号語に当てはまる。
【００２４】
本発明の伸張において、基準符号語及び間隔符号語のうち一方が、圧縮ブロックを構成するビットシーケンスの少なくとも一部のビットパターンに基づいて圧縮ブロックにおいて識別される。この識別は、所定のビットパターンに達するまでビットシーケンスの選択部分を解析することにより行なわれるのが好ましい。解析部分は、基準符号語又は間隔符号語の基礎を形成又は構成するのが好ましい。そして、基準符号語及び間隔符号語の他方は、識別された他方の符号語シーケンスに基づいて識別される。
【００２５】
符号語が識別されると、基準値は基準符号語に基づいて決定され、間隔長は間隔符号語に基づいて決定される。現在のブロックに対して利用可能な複数の成分値は、間隔の位置を規定する基準値、及び間隔のサイズを規定する間隔長から計算される。インデックスシーケンスは、復号化される各画像要素に対して、複数の成分値のうち、その画像要素の元の（Ｘ又はＹ）ベクトル成分の表現として使用する成分値を識別するために使用される。
【発明を実施するための最良の形態】
【００２６】
添付の図面と共に以下の説明を参照することにより、本発明は、本発明の更なる目的及び利点と共に最もよく理解されるだろう。
【００２７】
複数の図面を通して、同一の図中符号は対応する要素又は同様の要素に対して使用される。
【００２８】
本発明は、画像処理及びグラフィック処理に関し、特に、画像及び画像ブロックの符号化又は圧縮、並びに符号化（圧縮）画像及び符号化（圧縮）画像ブロックの復号化又は伸張に関する。
【００２９】
一般に本発明によると、画像圧縮中、画像は複数の画像ブロック又はタイルに分解又は分割される。そのような各画像ブロックは、特性又は特徴に関連する特定の画像要素を有する、複数の画像要素を備える。画像ブロックは圧縮され、画像の圧縮表現を生成する。
【００３０】
その後、符号化画像又は符号化された図形基本要素がレンダリングされる場合、例えば画面上に表示される場合、圧縮画像ブロックの関連画像要素は識別及び伸張される。それら伸張画像要素は、元の画像又は元の図形基本要素の伸張表現を生成するために使用される。
【００３１】
本発明は、ゲーム、３Ｄマップ、３Ｄシーン、例えば動画メッセージのような３Ｄメッセージ、スクリーンセーバ、マンマシンインタフェース（ＭＭＩ）等、３次元（３Ｄ）グラフィックを伴う使用に非常に適しているが、それらに限定されない。更に本発明は、１次元（１Ｄ）画像、２次元（２Ｄ）画像又は３Ｄ画像等の他の種類の画像又はグラフィックを圧縮するために採用できる。
【００３２】
本発明は、バンプマップ、法線マップ又は画像を扱うのに特に適している。従来技術において周知のように、法線又は面法線は、面に対して垂直である（平面の場合）又は面の接平面に対して垂直である（平坦でない面の場合）、３Ｄベクトルを示す。
【００３３】
３Ｄグラフィック処理において、一般にいくつかの三角形が作成され、それら三角形の角の対応する画面座標が決定される。画像（又は画像の一部）、すなわち所謂テクスチャは、各三角形上にマップされる（「貼り付けられる」）。しかし、グラフィックシステムの場合、テクスチャを格納するのに利用されるメモリと、及びテクスチャがメモリから取り出される時のメモリアクセス中のメモリ帯域幅との双方に関してテクスチャの管理のコストは高い。これは、特に移動ユニット及び電話機等の、メモリ容量及び帯域幅が制限されているシンクライアントにとって問題である。その結果多くの場合に、テクスチャ又は画像の符号化方式が採用される。そのような方式において、一般にテクスチャは複数のテクセルを含む複数の画像ブロックに分解又は分割される。画像ブロックは圧縮され、メモリに格納される。尚、圧縮画像ブロック（圧縮されたバージョンの画像ブロック）のサイズは、画像ブロックの非圧縮バージョンの対応するサイズより小さい。
【００３４】
本発明において、表現「画像要素」は、画像ブロック又は画像ブロックの圧縮表現の要素を示す。そしてこの画像ブロックは、画像又はテクスチャの一部に対応する。従って本発明によると、画像要素は、（１Ｄ、２Ｄ、３Ｄ）テクスチャのテクセル（テクスチャ要素）、（１Ｄ又は２Ｄ）画像の画素（ピクセル）、又は３Ｄ画像のボクセル（体素）でありうる。一般に画像要素は、特定の画像要素の特性又は特徴により特徴付けられる。本発明において、各画像要素は、画像要素と関連付けられる特徴を表す特徴ベクトルを有する。この特徴は、画像要素の外観を制御してもよく、又は画像要素の外観に影響を及ぼしてもよい。そのような特徴ベクトルの好適な実施形態は面法線であり、更に好ましくは正規化面法線である。そのような面法線は３つのベクトル成分又は座標、すなわちＸ成分、Ｙ成分及びＺ成分を有する。しかし一般には、画像要素毎に、例えばＸ座標及びＹ座標の、２つの法線座標のみを特定するのみで十分である。これは、例えば上記式１を使用することで、残りの座標がそれらの座標から計算できるからである。
【００３５】
更に以下において、用語「画像」は、本発明を使用して符号化及び復号化されうる、１Ｄ、２Ｄ又は３Ｄの、任意の画像又はテクスチャを示すために使用される。それら画像又はテクスチャは、バンプマップ、法線マップ、写真、ゲーム形式のテクスチャ、テキスト、図面、ダイナミックレンジの広い画像及びテクスチャ、等を含むがそれらに限定されない。
【００３６】
本発明は、各画像要素が２次元特徴ベクトルを有する、画像及び画像ブロックを、圧縮及び伸張するのに特に適する画像処理を提供する。本発明の好適な実現例において、２つのベクトル成分は、正規化面法線の２つの座標、例えばＸ座標及びＹ座標（あるいは、Ｘ座標及びＺ座標又はＹ座標及びＺ座標）、を表す。以下において、Ｘ成分及びＹ成分を備える特徴ベクトルと共に本発明を説明する。しかし、Ｘ成分、Ｙ成分、Ｚ成分のうち２つの成分の他の任意の組み合わせが代わりに使用できるため、これは単なる説明としての例示と考えられるべきである。非正規化法線が採用される場合、第３の成分は、本明細書で説明されるように他の２つの成分と同様に単に追加及び処理される。
【００３７】
本発明は、３Ｄｃ［１］等の従来の法線マップ圧縮技術と比較して根本的に異なる方法を利用する。本発明は、固定圧縮率圧縮システム内において動的な可変ビット長符号化を利用する。これは、画像ブロックを表すために使用される符号語のサイズ（ビット分解能又はビット長）がそれぞれ可変であるが、圧縮ブロック表現のビット数に関して、合計サイズは一定のままであることを意味する。このことは、複数の成分値を含む間隔の位置決めの精度に関して動的に適応することを考慮に入れるだけでなく、その間隔の分解能に関しても動的に適応することを考慮に入れている。その結果、本発明は、それら画像ブロックに対して位置決め精度を向上し（間隔分解能と引き換えに）、それにより画質が向上され、また他の画像ブロックに対して間隔分解能を向上する（位置決め精度と引き換えに）。従って、要約すると、最適な位置決め精度及び間隔分解能は画像ブロック毎に個別に決定でき、結果として得られる伸張画像の全体の品質を向上する。
【００３８】
例えば３Ｄｃ［１］において、小さな間隔は、間隔の幅に関しては非常に粗い粒度を有する。３Ｄｃの表現可能な最小の間隔の幅は１であり、次に最小の間隔の幅は２である。従って、次に大きい間隔になった時、サイズは２倍である。これは、例えば間隔の幅が１００であり且つ次に大きい間隔の幅が１０１である状況と比較されるべきである。この場合、サイズは１００％ではなく１％だけ大きくなる。
【００３９】
３Ｄｃにおいて小さい間隔に関する別の問題は、間隔の位置が高精度で特定できないことである。最小の間隔が移動した場合、例えば［３，４］から［４，５］のようにステップ全体が移動される必要がある。このステップのサイズは、間隔内の８つの成分値間の距離の約８倍である。一方、［３，１０３］のように間隔の幅が１００の場合、［４，１０４］へのような最小の平行移動は、その間隔の８つの成分値間の距離より、大きさが１段階を超えて小さい。
【００４０】
本発明は、可変符号語長符号化によるこの問題及び他の同様の問題を解決できる。例えばこれにより、間隔の幅が特定される粒度及び間隔の平行移動が特定される粒度の双方が、可能なベクトル値間の距離と同等に設定可能である。
【００４１】
圧縮
図１は、本発明の１つの側面に係る、画像を圧縮する（不可逆的）方法を示す。第１のステップＳ１において、画像は複数の画像ブロックに分解又は分割される。そのような各画像ブロックは、複数の画像要素、すなわち少なくとも２つの画像要素を備える。本発明の好適な実施形態において、画像ブロックは１６個の画像要素（画素、テクセル又はボクセル）を含み、ｍ＝４−ｎ且つｎ＝０，１，２，３，４である場合に画像要素２ｍ×２ｎ個分のサイズを有する。ｍ及びｎが双方とも２であるのが更に好ましい。ｍ、ｎ、ｐの全てが同時にゼロではないという条件の下、ｍ、ｎ、ｐがゼロ又は正の整数である場合、画像要素２ｍ×２ｎ個又は２ｍ×２ｎ×２ｐ個分のサイズの画像ブロックを利用可能である。図２は、本発明に係る１６個の画像要素６１０を含む画像ブロック６００の一例を概略的に示す。更に図２は、画像要素６１０と関連付けられた種々の特徴ベクトル６１５を概略的に示す。図１に戻ると、ステップＳ１において、画像ブロック全体は（重なり合わない）画像ブロックに分解されるのが好ましい。しかし、応用例によっては、画像の一部のみが圧縮されるため、その部分のみが画像ブロックに分解される。
【００４２】
次のステップＳ２及びＳ５は、画像ブロックの圧縮を実行する。上述したように、画像ブロック中の各画像要素は、それぞれの特徴ベクトル、好ましくは２Ｄ特徴ベクトルを有する。それら特徴ベクトルの圧縮は、２種類の特徴ベクトル成分種類を個別に処理することにより実行される。換言すると、Ｘ成分の処理及びＹ成分の処理を平行して又は順次行う。以下において、ベクトル成分のうち１つ成分、例えばＸ成分、の圧縮について更に詳細に説明する。同一の手順が、Ｙ成分等、他方のベクトル成分に対しても実行可能であり、またＹ成分及びＺ成分等、他の複数のベクトル成分に対しても実行可能である。しかし、Ｘ及びＹの組み合わされた処理を実行することが可能である。これについては、更に詳細に説明する。
【００４３】
ステップＳ２において、決定される圧縮ブロック表現の包含成分の、それぞれのビット分解能が規定される。それらの包含成分は、Ｘ成分に対して、基準符号語、間隔符号語及びインデックスシーケンスを備える。このステップＳ２におけるビット分解能の規定は、ブロック中の特徴ベクトルのＸベクトル成分の少なくとも一部、更に好ましくは全てのＸベクトル成分に基づいて実行される。その結果、基準符号語、間隔符号語及びインデックスシーケンスのうち少なくとも２つのビット数に関して、それぞれのサイズが可変となることができ、ステップＳ２において規定される。しかし、そのような別々の符号語及びインデックスのうち少なくとも１つのビット長が、種々の画像ブロックに対して規定されるが、それら３つの成分の合計サイズ（ビット長）は固定される。従って、Ｌ（Ｂ）は基準符号語のビット長を示し、Ｌ（Ｗ）は間隔符号語の対応するビット長を示し、Ｌ（Ｉ）はインデックスシーケンスのビット長を示すものとする。第１の実施形態において、以下の式が与えられる：
Ｌ（Ｂ）  ＋  Ｌ（Ｗ）  ＋  Ｌ（Ｉ）  ＝  ｋ            （２）
式中、ｋは定数である。第２の実施形態において、以下の式が与えられる：
Ｌ（Ｂ）  ＋  Ｌ（Ｗ）  ＝  ｍ            （３）
Ｌ（Ｉ）  ＝  ｎ
式中、ｍ、ｎは定数である。好適な実現例において、ｋ＝６４ビット、ｍ＝１６ビット及びｎ＝４８ビットである。画像要素がＸ成分及びＹ成分の双方を含むため、これらの式２及び式３は以下のように書き換えられる：
Ｌ（ＢＸ）  ＋  Ｌ（ＢＹ）  ＋  Ｌ（ＷＸ）  ＋  Ｌ（ＷＹ）  ＋  Ｌ（ＩＸ）  ＋  Ｌ（ＩＹ）  ＝  ｐ            （４）
式中、添え字Ｘ又はＹはインデックスシーケンスの符号語の特定のベクトル成分を示す。ｐは定数であり、好ましくはｐ＝１２８ビットである。別の実施形態において、以下の式が与えられる：
Ｌ（ＢＸ）  ＋  Ｌ（ＢＹ）  ＋  Ｌ（ＷＸ）  ＋  Ｌ（ＷＹ）  ＝  ｑ
Ｌ（ＩＸ）  ＝  ｔ１            （５）
Ｌ（ＩＹ）  ＝  ｔ２
式中、ｑ、ｔ１、ｔ２は定数である。ｔ１はｔ２に等しいのが好ましく、好ましくはｑ＝３２ビット、ｔ１＝ｔ２＝４８ビットである。好適な実現例において、Ｌ（ＢＸ）  ＋  Ｌ（ＷＸ）  ＋  Ｌ（ＩＸ）  ＝  Ｌ（ＢＹ）  ＋  Ｌ（ＷＹ）  ＋  Ｌ（ＩＹ）である。
【００４４】
次のステップＳ３において、基準符号語は、（Ｘ）ベクトル成分の少なくとも一部に基づいて基準値の表現として決定される。このステップＳ３における決定は、基準符号語に対して規定されたビット分解能（Ｌ（Ｂ））に基づいて行なわれるのが好ましい。あるいは、基準符号語に対するビット分解能の規定及び実際のビット符号語の決定は、ベクトル成分の少なくとも一部に基づいて単一の手順で一括して行なわれてもよい。この基準値は、間隔符号語により規定される間隔の位置を規定する（Ｘ）値である。好適な実現例において、基準値は間隔の中間点を表す。他の実施形態において、基準値は間隔の開始点又は終了点を表すことができる。この概念は、基準値が実際には間隔内の任意の値でもよく、あるいは実際には［０，１］、［０，２５５］、［−１，１］、［−１２７，１２７］又は他の間隔のような、間隔を位置決めするのに使用されうる、許容される値の範囲内の任意の値でもよいように、更に拡張されることができる。
【００４５】
ステップＳ４は、基準値と相関する複数の成分値を含む間隔の表現として間隔符号語を決定する。この符号語の決定は、（Ｘ）ベクトル成分の少なくとも一部に基づいて行なわれる。好適な実施形態において、このステップＳ４における決定はまた、ステップＳ２で間隔符号語に対して規定されたビット分解能（Ｌ（Ｗ））に少なくとも部分的に基づいて行なわれる。あるいは、間隔符号語に対するビット分解能の規定及び間隔符号語の実際の決定は、単一の手順で一括して行なわれてもよい。この間隔符号語は、間隔の開始（Ｘ）値及び終了（Ｘ）値を特定するために、基準符号語により表される基準値と共に使用される、間隔長の表現であるのが好ましい。この間隔はその際、複数の成分値、例えば８つの成分値、を含む。
【００４６】
ステップＳ３及びＳ４を実行する順番は交換可能である。すなわち、最初に間隔符号語を決定し（ステップＳ４）、次に基準符号語を決定する（ステップＳ３）。更に、２つのステップＳ３及びＳ４は、代わりに並行して実行されてもよい。
【００４７】
次のステップＳ５において、インデックスシーケンスが決定される。この決定は、ステップＳ２でシーケンスに対して規定されたビット分解能に少なくとも部分的に基づいて行なわれるのが好ましい。あるいは、インデックスシーケンスの決定及びインデックスシーケンスに対するビット分解能の規定は単一の手順で一括して行なわれてもよい。インデックスシーケンスは、ブロック中の各画像要素に対して、間隔に含まれる複数の成分値から選択される１つの成分値を示す。このステップＳ５において、１つの（Ｘ）成分値はブロック中の１つの画像要素に対して選択され、その画像要素の「真」の（Ｘ）ベクトル成分の表現として使用される。
【００４８】
ステップＳ２〜Ｓ５の結果、画像要素の第１の（Ｘ）ベクトル成分が圧縮される。同一の手順が第２の（Ｙ）ベクトル成分に対して順次又は並行して実行されるのが好ましい。ステップＳ２〜Ｓ５の符号化の結果、圧縮画像ブロック、更に正確には画像ブロックの圧縮表現、が得られる。そのような圧縮ブロック表現７００を図３Ａ〜図３Ｃに示す。表現７００は、第１の（Ｘ）基準符号語７２０、第１の（Ｘ）間隔符号語７１０、第１の（Ｘ）成分インデックスシーケンス７３０、第２の（Ｙ）基準符号語７５０、第２の（Ｙ）間隔符号語７４０及び第２の（Ｙ）成分インデックスシーケンス７６０を備える。尚、圧縮画像ブロック７００の、符号語７１０、符号語７２０、符号語７４０、符号語７５０、インデックスシーケンス７３０、インデックスシーケンス７６０との相互の順番は、図示されるものとは異なってもよい。
【００４９】
本発明の動的な可変ビット分解能の決定は、図３Ａ〜図３Ｃの圧縮表現を比較すると明確に分かる。図３Ａ及び図３Ｂにおいて、Ｘインデックスシーケンス７３０及びＹインデックスシーケンス７６０は一定のビット長を有する。しかし、基準符号語７２０と、基準符号語７５０と、間隔符号語７１０と、間隔符号語７４０とのビット分解能は、種々の画像ブロックに対して、及び２つのベクトル成分に対しても、個別に規定される。図３Ｂを図３Ａと比較すると、図３ＢのＸ間隔符号語７１０のビット分解能が図３Ａより低いことが明らかである。一方、図３ＢのＸ基準符号語７２０のビット分解能は図３Ａより高いことが明らかである。この逆のことがＹ符号語７４０、７５０に当てはまる。
【００５０】
図３Ｃにおいて、Ｘインデックスシーケンス７３０及びＹインデックスシーケンス７４０に対して使用されたビット数を選択してもよい。図３Ａを図３Ｃと比較すると、図３Ｃの圧縮ブロックは、Ｘインデックスシーケンス７３０において、比較的多くのビットを使用する。
【００５１】
しかし、図中、２つの圧縮ブロック表現７００の合計サイズは同等である。このサイズは、１２８ビットであるのが好ましい。好適な実現例において、Ｘ符号語７１０、７２０及びＸインデックスシーケンス７３０に使用されるビット数は、Ｙ符号語７４０、７５０及びＹインデックスシーケンス７６０の合計ビット数と同一であるのが好ましく、すなわち６４ビットであるのが好ましい。
【００５２】
図１に戻って、ステップＳ２〜Ｓ５はステップＳ１の分解工程で与えられる全ての画像ブロックに対して繰り返されるのが好ましい（線Ｌ１により概略的に示される）。尚、それぞれの圧縮ブロックのビット換算の合計サイズは同一であるが、本発明の動的なビット分解能の選択のために、結果として得られる別々の圧縮ブロックは、符号語とインデックスシーケンスとの少なくとも一方に対して別々のビット数を使用できる。その結果、圧縮画像ブロックのシーケンス又はファイルが得られる。結果として得られる圧縮画像ブロックは、ステップＳ１のブロック分解において分解された順番と同一の順番で左から右及び上から下へ、ファイル中に配列されてもよい。そして、本方法は終了する。
【００５３】
圧縮画像は、後で画像がレンダリングされるまで、例えば表示されるまで格納しておくためにメモリに提供されることができる。更に圧縮画像は、別のユニットに（無線又は有線）送信するために圧縮ブロック表現の信号として送信機に提供されることができる。
【００５４】
図４は、図１の規定ステップの一実施形態を更に詳細に示すフローダイアグラムである。本実施形態において、基準符号語、間隔符号語及びインデックスシーケンスのうち少なくとも２つに対するビット分解能の規定は、画像ブロック中の特徴ベクトルの（Ｘ又はＹ）ベクトル成分の分布に基づいて行なわれる。従って、第１の成分分布の結果、基準符号語、間隔符号語のそれぞれの第１のビット長が得られるだろう。第１の成分分布の結果、インデックスシーケンスの第１のビット長を得ることも自由である。また第２の成分分布により、符号語のそれぞれの異なる第２のビット長が与えられてもよく、インデックスシーケンスの第２のビット長を与えることも自由である。
【００５５】
本方法は、図１のステップＳ１から継続する。次のステップＳ１０において、ブロック中の特徴ベクトルの最小の（Ｘ又はＹ）ベクトル成分が識別される。それに対応して次のステップＳ１１では、ブロック中の最大の（Ｘ又はＹ）ベクトル成分を識別する。それら２つのベクトル成分は、ブロック中の（Ｘ又はＹ）ベクトル成分の分布の表現として使用されることができる。従って、最小のベクトル成分と最大のベクトル成分との比較は、本発明に従って符号語とインデックスシーケンスとの少なくとも一方に対するビット分解能を規定するのに使用されることができる。
【００５６】
好適な実現例において、まず間隔符号語に対するビット分解能はまず、ブロック中のベクトル成分に基づいて、更に好ましくはステップＳ１０及びＳ１１で識別された最小のベクトル成分及び最大のベクトル成分に基づいて、規定される。これをステップＳ１２に示す。ステップＳ１２の間隔符号語分解能の規定は、種々の事前定義済み間隔長の、セット又はルックアップテーブルを調査することにより実行される。ここで、そのような各間隔長は、所定の間隔符号語と関連付けられている。更に、セット／テーブル中の間隔符号語の少なくとも一部は、それぞれ異なるビット分解能を有する。そのような場合、最大の成分値と最小の成分値との差分が計算されるのが好ましい。計算された差分に最も近い、セット又はテーブルの中の事前定義済みの幅長が選択される。これにより、現在の画像ブロックに対して使用する間隔符号語及びその符号語のビット分解能が与えられる。これについては以下に更に説明する。従って、本方法において、間隔符号語の決定及び間隔符号語分解能の決定が組み合わせて行われる。
【００５７】
別の方法において、最大のベクトル成分と最小のベクトル成分との差分は、関数に入力されるか、あるいは間隔符号語ビット分解能を決定するための、セット又はテーブルルックアップ手順への入力として使用される。そのような場合、関数又はテーブルは、差分のそれぞれの範囲に対するそれぞれの符号語分解能を特定できる。
【００５８】
次のステップＳ１３において、基準符号語に対するビット分解能は、ステップＳ１２で間隔符号語に対して決定されたビット分解能及び事前定義済み最大分解能値から計算される。基準符号語分解能が、この最大値と、決定された間隔符号語分解能との差分として取得されることを、このことは意味する。好適な実施形態において、この事前定義済み最大分解能値は１６である。従って、本実施形態において、間隔符号語分解能が高い（低い）場合に基準符号語のビット分解能は低く（高く）なる。その後、本方法は図１のステップＳ３に続く。
【００５９】
図５は、座標空間におけるＸＹ平面を示す図である。画像ブロックの各画像要素は、Ｘ座標及びＹ座標を有する特徴ベクトル６１５（面法線）をそれぞれ有する。図中、例えば図２に示すように、ブロック毎に１６個の画像要素が存在すると仮定する。従って、図は画像要素のＸ座標及びＹ座標を表す、１６個のマークされた点を備える。更に、図をより分かり易くするために特徴ベクトル６１５を２つのみ示している。図は、ブロック中の、最小（Ｘｍｉｎ，Ｙｍｉｎ）ベクトル成分及び最大（Ｘｍａｘ，Ｙｍａｘ）ベクトル成分を示す。
【００６０】
図６は、図１の間隔符号語の決定の一実施形態を示すフローダイアグラムである。本方法は、図１のステップＳ３から継続する。次のステップＳ２０において、画像ブロックの最小の（Ｘ又はＹ）ベクトル成分が識別される。このステップは、図４のステップＳ１０に対応する。次のステップＳ２１は図４のステップＳ１１に対応し、最大の（Ｘ又はＹ）ベクトル成分を識別する。次のステップＳ２２は、最大のベクトル成分と最小のベクトル成分との差分の表現として間隔符号語を決定する。
【００６１】
このステップＳ２２は、２つのベクトル成分間の差分を計算することにより実行されるのが好ましい。その後、ステップＳ２３は、複数の事前定義済み間隔符号語の、セット又はテーブルから、適切な間隔符号語を識別する。更に、成分の差分は、ステップＳ２３において所望の間隔符号語を出力する関数に入力されてもよい。その時、セット／テーブルは複数の異なる間隔符号語を含んでいる。又は、関数は複数の異なる間隔符号語へのアクセスを持っている。ここで、符号語の少なくとも一部は異なるビット長（分解能）を有する。以下のテーブルＩは、間隔符号語用のそのようなルックアップテーブルの一例である。
【００６２】
【表１】
2009534914.tif 000004
【００６３】
この例示するテーブルＩにおいて、間隔に含まれる成分値間の距離は、間隔が移動できる最小の距離と等しい。例えば、最大の成分値と最小の成分値との間の距離が１２８と等しいか又はほぼ１２８である場合、１２８の間隔長が選択される。複数の成分値間の距離は、８つの成分値の場合１２８／８＝１６である。基準値及び間隔の位置を特定するのに４ビットが利用可能であり、２５６／２４＝１６の精度で特定されることを意味する。従って、成分値間の距離は、間隔が移動できる最小の距離に等しい。このことは、テーブルＩの全ての可能な間隔長に当てはまる。
【００６４】
テーブルＩは、本発明に従って使用される単なる例示のテーブルとして考えられるべきである。例えば基準値により高い精度が所望される場合、表現可能な最小間隔は１／１６ではなく１／４であってもよく、そうすると基準符号語のビット分解能を向上するために使用されうる２ビットが解放される。
【００６５】
別の可能性は、間隔における粒度を向上させるために解放されたビットを使用することである。通常、一般に間隔の開始値及び間隔終了値の線形結合として、決定された間隔中において等間隔の８つの成分値が利用可能である。基準値が間隔の中間点（Ｍ）を表す場合、８つの成分値は以下のように計算される：
【００６６】
【数２】
2009534914.tif 000005
【００６７】
式６の括弧内に表される集合は別の集合と交換可能であり、解放されたビットは、使用されるべき特定の集合を信号伝送するために使用されることができる。その時、圧縮ブロックは、使用する特定の集合が使われるかを信号伝送するための符号語を含む。その符号語のための０ｂｉｎというビット値は、集合
【数３】
2009534914.tif 000006
を表し、１ｂｉｎは
【数４】
2009534914.tif 000007
を表す。これは、１ステップ毎ではなく２ステップ毎に間隔のサイズが２倍となることを意味する。信号伝送符号語が２ビットを備える場合、代わりに以下の集合がそれぞれの再構成レベルを計算するのに利用可能である：
【００６８】
【表２】
2009534914.tif 000008
【００６９】
これは、間隔長が４ステップで２倍となることを意味する。実際には、テーブルＩＩはテーブルＩ又は別のそのようなテーブルと共に使用される。ここで、テーブルＩは間隔長及び符号語を特定し、テーブルＩＩは、成分値が間隔長及び基準値から計算される方法を特定する。
【００７０】
この技術は、同一の幅を有する異なる種類の集合を使用するように拡張可能である。テーブルＩＩにおいて、結果として得られる全ての成分値は間隔において均等に離間される。しかし、ガウス分布、ラプラス分布又はｂｉｏｍｏｄａｌ等の、間隔内における他の成分値分布形式が代わりに使用されてもよい。好ましくは、間隔内における他の成分値分布形式は、均等に離間された分布を補完するものとして使用される。
【００７１】
基準符号語により符号化される基準値が、代わりに間隔の開始点又は間隔の終了点を表す場合、式６は式７（開始点）又は式８（終了点）で示されるように書き換えられるだろう。
【００７２】
【数５】
2009534914.tif 000009
【００７３】
【数６】
2009534914.tif 000010
【００７４】
テーブルＩに存在する間隔符号語は任意に選択されない。その代わりに、それら符号語はいわゆる接頭符号である。これは、テーブルＩの符号語が、テーブルＩの他のどの符号語に対する接頭語でもないことを意味する。そのような接頭符号である間隔符号語の使用により、圧縮ブロック中の、間隔符号語及び基準符号語の、伸張及び識別が簡単になる。これについては以下に更に説明する。テーブルＩで使用されうるそのような接頭符号である符号語の別の例は、以下のテーブルＩＩＩに示されるような、開示された符号語のビット単位の反転である。
【００７５】
【表３】
2009534914.tif 000011
【００７６】
利用可能な間隔長は必ずしも２又は１／２の因子である必要はない。間隔長が２又は１／２の因子である場合には、ステップ毎に間隔長が２倍になる。いくつかの画像において最も一般的な間隔の幅の統計を提供するためにそれら画像に対してテストを実行することが、例えば可能であるだろう。テーブルＩ及びテーブルＩＩＩに載っている幅を、それら最も頻繁に出現する間隔長で置換できるだろう。
【００７７】
テーブルＩ及びテーブルＩＩＩにおいて、間隔長が小さい程、間隔符号語に対するビット分解能は低くなる。これは、間隔を位置決めする精度、すなわち基準符号語の分解能が、より短い間隔に対しては向上されることを意味する。その結果、一般に、処理される殆どの画像の画質は良くなる。しかし、特定の画像に対してはその逆のことが当てはまりうる。そのような場合、このことは、最短の間隔符号語が最大の間隔を表し、且つ最長の間隔符号語が最小の間隔を表すように、テーブルＩ及びテーブルＩＩＩの間隔長の値の位置を切り替えることにより簡単に解決される。そのような場合、間隔の位置決めの精度は間隔長が長くなると共に向上する。
【００７８】
上述したように、様々な画像にける様々な間隔長の出現頻度を推定するためにそれらの画像に対してテストが実行されてもよい。その統計は、テーブルＩ及びテーブルＩＩＩのようなテーブルを設計する時に使用されうる。そのような場合、最も頻繁に出現する間隔長に最短の間隔符号語長が割り当てられるのが好ましい。これは、より多くのビットが最も頻繁に出現する間隔を正確に位置決めすることに対して使用されうることを意味する。その結果、画像処理の品質は向上するだろう。
【００７９】
そのような場合、最も一般的な間隔の幅に対応する間隔符号語のサイズは、最小となる。テーブルＩＶはこの原理を示す。尚、テーブルにおいて、間隔符号語のサイズはより出現しにくい間隔長に対して大きくなる。更に、符号語長はある特定の長さに達するとそれ以上長くならない。これは、同一の符号語長がいくつかの異なる間隔の幅に対して使われることを意味する。その理由は、同一の符号語長を採用しないと、最も出現しにくい幅と関連付けられる間隔符号語が非常に長くなり、基準符号語に殆どビットが残らなくなるからである。
【００８０】
【表４】
2009534914.tif 000012
【００８１】
間隔符号語が決定されると、基準符号語に対して利用可能なビット数は上述のように決定される。一般に基準符号語の決定は、ブロック中の最小のベクトル成分及び最大のベクトル成分を識別することを含む。それら成分の平均値が計算され、間隔の中間点を取得する。基準符号語は、Ｎ＝Ｌ（Ｂ）の場合、一般には平均値に最も近いＮビットの値を選択することにより、平均値と、符号語に対する利用可能なビット分解能とに基づいて決定される。基準値が間隔の開始点又は間隔の終了点である場合、基準符号語は、ブロック中の最小の成分値又は最大の成分値に最も近い、Ｎビットの値を選択することにより決定される。
【００８２】
図７は、図１のインデックスシーケンス決定ステップの一実施形態を更に詳細に示すフローダイアグラムである。方法は、ステップＳ４から継続する。次のステップＳ３０において、（Ｘ又はＹ）成分インデックスがブロック中の現在の画像要素に対して与えられる。この成分インデックスは、間隔符号語により表される間隔に含まれる複数の成分値から、選択された１つの成分値と関連付けられる。例えば成分インデックスは、式６、式７又は式８に従って取得可能な成分値のうちの１つと関連付けられる。選択された成分値は、画像要素の元の（Ｘ又はＹ）ベクトル成分と等しいか又は最も近い値であるのが好ましい。線Ｌ２により概略的に示されるように、ステップＳ３０は画像ブロック中の全ての画像要素に対して繰り返されるのが好ましい。
【００８３】
本発明の第１の実施形態において、Ｘインデックスシーケンス及びＹインデックスシーケンスは、全ての画像ブロックに対して同一ビット数を含む。８つの異なる成分値が画像要素毎に利用可能である場合、これはＸ成分インデックス及びＹ成分インデックスが３ビットを備えることを意味する。ブロックには１６個の画像要素が存在するのが好ましいため、Ｘインデックスシーケンス及びＹインデックスシーケンスはそれぞれ１６×３ビット含む。
【００８４】
基準符号語及び間隔符号語に加えて、インデックスシーケンスに対しても可変ビット分解能を有すると、成分インデックス毎に４ビット以上必要となる場合に問題が起こるかもしれない。圧縮画像ブロックの合計サイズは一定であるべきであり、好ましくは１２８ビットである。例えば一実現例において、成分値に対して８つではなく１２個の異なるレベルを有するのが有利であるかもしれない。画像要素が個別に処理される場合、結果的に４ビットの成分インデックス分解能を有することになるだろう。その結果、Ｘインデックスシーケンス及びＹインデックスシーケンスを表すのに合計１２８ビット使用され、圧縮ブロックの合計サイズが１２８ビットに限定される場合、基準符号語及び間隔符号語に対してビットが残されない。
【００８５】
本発明は、複数の画像要素の集合に対して合成成分インデックスを使用することによりその問題を解決する。図８はこの手順を示す。本方法は図１のステップＳ４から継続する。次のステップＳ４０において、複数の利用可能な成分値のうち、画像要素のベクトル成分を最適に表す１つの成分値が選択される。これは、線Ｌ３により表されるように、ブロック中の全て（１６個）の画像要素に対して実行される。
【００８６】
図７の状況とは異なり、利用可能な成分値の数は他の画像ブロックとは異なるかもしれず、８個を上回るかもしれない。インデックスが複数の、例えば３つの、インデックスの集合に符号化される場合には、更に少ないビット数しか要求されない。例えば次のような、３つの画像要素の集合を使用する、１２の異なったレベルを持つ組み合わせが可能である。すなわち、１２×１２×１２  ＝  ３×３×３×４×４×４  ＝  ２７×６４  ＜  ２５×２６  ＝  ２１１である。これは、この集合に対しては、別個に符号化される場合に必要とされる１２ビットではなく、１１ビットのみが必要とされることを意味する。そこでルックアップテーブルが、テーブルＶのように、可能な成分値の組合せ及び対応する合成成分インデックスを一覧表とするために使用されることができるだろう。
【００８７】
【表５】
2009534914.tif 000013
【００８８】
テーブルＶにおいて、ｖｉは成分値を表し、ｉ＝０〜１１である。
【００８９】
そして、画像要素の集合に対して使用する合成インデックスは、集合中の複数の画像要素に対して選択された複数の成分値に基づいてルックアップテーブルから識別される。この手順は、線Ｌ４により概略的に表されるように、ブロック中の画像要素の集合毎に繰り返される。結果として得られる合成インデックスは、本発明のインデックスシーケンスを形成する。合成インデックスは、端数であるいくつかの「普通の」成分インデックスと一緒に、本発明のインデックスシーケンスを形成することもあり得る。
【００９０】
上述において、Ｘベクトル成分及びＹベクトル成分の双方の処理を組み合わせて実行できることを説明した。第１のそのような例においては、間隔符号語ＷＸ及びＷＹ（図３Ａ〜図３Ｃを参照）がＸＹ平面における半径及び角度を表す。２つの基準符号語ＢＸ、ＢＹは上述のように決定され、ＸＹ平面におけるＸ基準値及びＹ基準値をそれぞれ表す。従って、それら２つの値は平面において点を形成する。半径は、例えばこの点で発する、又はこの点に達することにより、平面中のこの点と相関する位置に位置付けられる。半径の方向は、角度により規定され、この角度はＸ軸に対する角度であっても、Ｙ軸に対する角度であってもよい。（Ｘ，Ｙ）点、半径及び角度が与えられると、複数のＸ成分値又はＹ成分値をそれぞれ含む、Ｘ間隔及びＹ間隔を計算できる。
【００９１】
この組み合わされた符号化において、基準符号語及び半径を符号化している間隔符号語（ＷＸ）のビット分解能は本発明に従って動的に規定されてもよく、一方角度を表す間隔符号語（ＷＹ）は固定ビット長を有してもよい。
【００９２】
別の方法においては、２つの基準符号語が上述のように基準値を表す。第１の間隔符号語は対角線を符号化し、第２の間隔符号語はＸ間隔又はＹ間隔の表現である。この第２の符号語は、間隔［０，１］における重みを表せるだろう。この重みは、伸張工程中で、第１の（Ｘ又はＹ）間隔長を与えるための第１の間隔符号語により表される対角線長と乗算される。第１の間隔の位置は、例えば間隔の開始点又は終了点を規定できる２つの基準値により規定される。第２の（Ｙ又はＸ）間隔長は、ピタゴラスの定理
【数７】
2009534914.tif 000014
を使用して第１の間隔長及び対角線から計算されうる。式中、ｌ１、ｌ２は第１の間隔長及び第２の間隔長を表し、ｄは対角線である。
【００９３】
２つの基準符号語、及び対角線を符号化する間隔符号語のビット分解能は、本発明に従って動的に規定されうる。一方、重みを符号化する間隔符号語は固定ビット長であってもよい。圧縮画像ブロックは、対角線を重みと乗算することにより取得可能な間隔がＸ間隔であるか又はＹ間隔であるかを区別するために使用される、Ｘ／Ｙビットを更に含むのが好ましい。本実施形態の好適な実現例において、画像ブロック中の最大のＸベクトル成分と最小のＸベクトル成分との差分及び最大のＹベクトル成分と最小のＹベクトル成分との差分が比較される。Ｘ／Ｙビットは、その比較に基づいて規定される。例えば元のＸベクトル成分における分布が対応するＹベクトル成分の分布より小さい場合、Ｘ／Ｙビットは、重み及び対角線から直接計算可能な第１の間隔がＸ間隔、すなわち最小の分布を有する成分となるように設定される。より大きいＹ間隔は、Ｘ間隔及び対角線から計算可能である。
【００９４】
本発明の教示は、従来の３Ｄｃブロック処理と組み合わせ可能である。そのような場合、本発明は法線をゆっくり移動させるために使用されるのに対し、３Ｄｃは法線を迅速に移動させるのに使用されることができる。従来の３Ｄｃにおいて、圧縮ブロックは、Ｘ間隔の開始及び終了点であるＸ点を表す２つのＸ符号語（Ｘｆ，Ｘｌ）、並びにＹ間隔の開始及び終了点であるＹ点を表す２つのＹ符号語（Ｙｆ，Ｙｌ）を備える。以下において、説明はＸ成分のみに限定されるが、同一の説明がＹ成分にも適用可能である。３Ｄｃの場合は、Ｘｆ＜Ｘｌの場合及びＸｆ≧Ｘｌの場合の双方において、画像ブロックは従来に合致している。しかし、マルチモードの実施形態においては、Ｘｆ＜Ｘｌの場合、ブロックは３Ｄｃ（デフォルト）モードを使用して符号化される。それは、ブロックが３Ｄｃブロックと同様の方法で処理されることを意味する。しかし、Ｘｆ≧Ｘｌの場合、ブロックは本発明（補助モード）に従って処理される。
【００９５】
尚、３Ｄｃブロックは常にデフォルトモードで圧縮可能である。ＸｆがＸｌより大きくなった場合でも、２つの符号語ビットシーケンスは単純に入れ替えられることが可能であり、Ｘｆ＜Ｘｌが維持される。Ｘｆ＝Ｘｌの場合、第２の符号語ビットシーケンスはＸｌ＝Ｘｆ＋１に設定されることができ、全ての画像要素の特徴値は第１の符号語ビットシーケンスに従って量子化される。あるいは、第１のビットシーケンスはＸｆ＝Ｘｌ−１として設定されることができ、全ての画像要素値が第２の符号語ビットシーケンスに量子化される。これは、全ての現在の３Ｄｃ法線マップがデフォルトモードのみを使用して符号化されることを意味する。従って、補助モードは規定のペイロードビットを犠牲にすることなく、「無償」となる。
【００９６】
最初、Ｘｆ≧Ｘｌ又はＹｆ≧Ｙｌの少なくとも一方として使用されるブロック符号語及び間隔符号語の実際の値に制限が課されるように思われるだろう。しかし、実際には３Ｄｃにおける２つの（Ｘ又はＹ）符号語ビットシーケンスの合計１６ビットのうち１５ビットを自由に、すなわち基準符号語値及び間隔符号語値の制限なく使用可能である。使用する技術は、文献［３］及び文献［４］において詳細に説明される。その技術は、Ｘｆ≧Ｘｌ又はＹｆ≧Ｙｌの少なくとも一方を維持しながら、１６ビットという最大の数を活用することを可能とする。基本的に以下の動作は、補助モードにおいて使用されうる１５ビットを得るために使用される：
【００９７】
ｉｎｔ  ｇｅｔ＿１５ｂｉｔｓ＿ｂａｃｋ（Ｘｆ，Ｘｌ）
｛
ｉｆ  ＭＳＢ（Ｘｌ  ＝＝  ０）
ｒｅｔｕｒｎ  （Ｘｌ  ＜＜  ８）  ＯＲ  Ｘｆ；
ｅｌｓｅ
ｒｅｔｕｒｎ  （ＮＯＴ（Ｘｌ）  ＜＜  ８）  ＯＲ  ＮＯＴ（Ｘｆ）；
｝
【００９８】
尚、Ｘｆ≧Ｘｌ且つＹｆ＜Ｙｌであるか、Ｘｆ＜Ｘｌ且つＹｆ≧Ｙｌであるか、あるいはＸｆ≧Ｘｌ且つＹｆ≧Ｙｌであるかに依存して、３Ｄｃに加えて最大３つの補助モードを有することができる。最初の２つの補助モードにおいて、１２８ビットのうち１２７ビットが自由に設定でき、第３の例においては１２６ビットが自由に設定できる。
【００９９】
本発明のそのような補助モードにおいて、基準符号語は間隔の開始点となることが可能な基準値を表す。上述したものと同様に、間隔符号語は複数の成分値を含む間隔を表す。テーブルＶＩは、間隔符号語に使用可能なコードであり、異なるビット長を有し且ついわゆる接頭符号である、可能なコードを列挙する。
【０１００】
【表６】
2009534914.tif 000015
【０１０１】
このテーブルＶＩにおいて、基準値は整数ビット及び端数ビットの双方を有するだろう。従って、値の整数部を表すために８ビットが使用され、２〜５（実際のビット分解能に依存する）ビットが端数部を表す。これは、間隔が非常に高精度に位置決めされることを意味する。
【０１０２】
テーブルＶＩＩは、間隔符号語及び符号語に対するビット分解能を含むテーブルの別の例である。
【０１０３】
【表７】
2009534914.tif 000016
【０１０４】
テーブルＶＩＩにおいて、基準値表現の精度は、間隔Ｗの最小幅と比較して４倍である。
【０１０５】
テーブルＶＩＩＩは、間隔符号語及び符号語に対するビット分解能を含むテーブルの更なる例である。
【０１０６】
【表８】
2009534914.tif 000017
【０１０７】
テーブルＶＩＩＩにおいて、基準値の精度の各レベルにおいて、４つの異なる間隔の幅が利用可能である。
【０１０８】
テーブルＩＸは更に別の例である。
【０１０９】
【表９】
2009534914.tif 000018
【０１１０】
テーブルＩＸは、間隔の最小幅と比較して４倍の基準値の精度を有する。
【０１１１】
テーブルＸは、本発明に従って使用されうるテーブルの更なる一例である。
【０１１２】
【表１０】
2009534914.tif 000019
【０１１３】
上記のテーブルＶＩ〜Ｘの全ては、いくぶん短い間隔長を表す間隔符号語を含む。これは、より長い間隔長が画質の点で適切な結果を与えるであろう場合に規定の３Ｄｃモードが選択されるであろうことを意味する。その結果、圧縮ブロックの第１の（Ｘ又はＹ）符号語の８ビットが、後続する第２の（Ｘ又はＹ）符号語の８ビットよりも、整数として解釈される場合には小さいであろうことを、このことは意味する。しかし、より短い間隔長がよりよい品質となる結果を与えるであろう場合、ブロックは、例えば上記提示されたテーブルのいずれかを使用することにより本発明に従って圧縮される。そのような場合、最初の８ビットは後続する８ビットより、整数として解釈される場合には大きいだろう。
【０１１４】
伸張
図９は、本発明に係る圧縮画像を伸張する方法を示すフローダイアグラムである。圧縮画像は、基本的に画像ブロックのいくつかの圧縮表現を備える。それらブロック表現は、上述の画像圧縮方法により生成されるのが好ましい。
【０１１５】
一般に方法は、伸張する圧縮画像ブロックを識別することにより開始する。元の画像の伸張表現を生成するために、圧縮画像の全ての画像ブロックが伸張されるべきであってもよいだろう。あるいは、元の画像の一部のみがアクセスされる。その結果、選択された数の画像ブロックのみが伸張される必要がある（あるいは更に正確には、特定の画像ブロックの選択された数の画像要素が復号化される必要がある）。
【０１１６】
ブロック圧縮と同様に、本発明の伸張は、２つのベクトル成分Ｘ及びＹに対してそれぞれ、並行して又は順次実行されうる。まず、この方法を以下に説明する。しかし、圧縮を組み合わせることに対応して、伸張を組み合わせて行うことも可能であるだろう。
【０１１７】
正確な圧縮画像ブロックが識別されると、基準符号語及び間隔符号語の一方が圧縮表現の少なくとも一部に係るビットパターンに基づいて識別される。基準符号語及び間隔符号語のうちの他方は、識別された基準符号語又は間隔符号語の一方に基づいて決定される。好適な実現例において、圧縮表現の規定されたビットパターンに基づいて、まず間隔符号語がステップＳ５０において識別される。この実現例は、間隔符号語が接頭符号形式であるという知識を利用する。間隔符号語が圧縮ブロックを構成するビットシーケンスにおいて識別されると、現在のベクトル成分（Ｘ又はＹ）に対する対応する基準符号語が識別されうる。この識別は、識別された間隔符号語に後続するビットの集合を基準符号語として割り当てることにより行なわれるのが好ましい。この集合の合計のビット数＋間隔符号語のビット数は、事前定義済み最大値と等しいのが好ましい。従って、この事前定義済みの値を認識し、ステップＳ５０において間隔符号語のビット数を決定することにより、ステップ５１で、基準符号語を共に形成する後続するビットの数を決定できる。
【０１１８】
次のステップＳ５２は、ステップＳ５１で識別された基準符号語に基づいて基準値を決定する。この基準符号語が８ビット未満を備える場合、例えば５ビットの場合、符号語は８ビットに拡張又は拡大される。これは、符号語の最上位ビットを複製し、それらを最下位ビットとして追加して８ビットを形成することにより実現されうる。基準符号語が８ビットを備える場合、それは基準値として直接使用されうる。同様に、基準符号語が８ビットを超えるビットを備える場合、例えば８．３という形式で、最初の８ビットが整数値を表し、残りのビットが端数値であることが好ましい。
【０１１９】
後続するステップＳ５３は、ステップＳ５２において決定された基準値と、間隔符号語とに基づいて複数の成分値を決定する。従って基準値は、例えば間隔の開始点、間隔の終了点、又は間隔の中間点を特定することにより、間隔が（Ｘ又はＹ）軸に沿って位置決めされる場所を特定する。例えば関数、事前定義済みルックアップテーブル、又はセットに対する入力として、符号語を使用することにより、使用する間隔長は間隔符号語から取得される。
【０１２０】
次のステップＳ５４において、画像要素の元の（Ｘ又はＹ）ベクトル成分の表現として使用する成分値はインデックスシーケンスに基づいて選択される。このステップＳ５４において、現在の画像要素に関連付けられた（Ｘ又はＹ）成分インデックスは、ステップＳ５３で計算された複数の（Ｘ又はＹ）成分値から１つの成分値を選択するために使用される。
【０１２１】
ステップＳ５４は、画像ブロックのいくつかの画像要素に対して実行される（線Ｌ５により概略的に示される）。いくつかの応用例においては、単一の画像要素のみが特定の画像ブロックから復号化されること、特定の画像ブロックの複数の画像要素が復号化されること、又は特定のブロックの全ての画像要素が復号化されること、このうちの少なくとも１つであることが、本発明により期待される。
【０１２２】
ステップＳ５０〜Ｓ５４の手順は、他のベクトル成分に対して同様の方法で実行できる。又は、２つの成分は同時に処理されてもよい。これは、基本的にステップＳ５０〜Ｓ５４の各々を２回実行することにより（１回は第１の（Ｘ）ベクトル成分に対して実行し、１回は第２の（Ｙ）ベクトル成分に対して実行する）行われる。
【０１２３】
ステップＳ５０〜Ｓ５４は、復号化されるべき画像要素を備える全ての画像ブロックに対して繰り返されるのが好ましい（線Ｌ６により概略的に示される）。このことは、ステップＳ５０〜Ｓ５４のループが１回実行されることもあるが、殆どの場合は、このループが異なる圧縮画像ブロックに対して数回実行され、又は特定の圧縮画像ブロックに対して数回実行されることのうち少なくとも一方であることを意味する。尚、間隔符号語及び基準符号語のそれぞれのビット分解能（ビット長）は、図９に従って処理される異なる圧縮画像ブロック間で異なってもよい。また、インデックスシーケンスのビット分解能（ビット長）が、図９に従って処理される異なる圧縮画像ブロック間で異なっていることも自由である。
【０１２４】
任意のものであるステップＳ５５において、元の画像の伸張表現又はその一部は、復号化画像要素及びブロックに基づいて生成される。尚、いくつかの応用例において、復号化表現の単一画素をレンダリングするために、いくつかの画像要素が復号化される必要がある。例えば、３次元線形補間の際には８つの画像要素が復号化され、２次元線形補間の場合には対応する数は４つの画像要素である。このことは、当業者には周知である。そして、本方法は終了する。
【０１２５】
図１０は、図９の識別ステップの一実施形態を更に詳細に示すフローダイアグラムである。本実施形態において、基準符号語及び間隔符号語のうち識別された一方、好ましくは間隔符号語の決定されたビット長に基づいて、基準符号語及び間隔符号語のうちの他方、好ましくは基準符号語が識別される。
【０１２６】
本方法はステップＳ６０で開始し、事前定義済みビットパターンに達するまで、圧縮表現の選択した部分が解析される。このステップＳ６０の解析は、第１のベクトル成分に対する圧縮ブロックを構成するビットシーケンスの初めから開始し、第２のベクトル成分に対するビットシーケンスの中間から開始するのが好ましい。事前定義済みビットパターンに達するまで、解析は継続する。本実施形態は、特に接頭符号の使用に適している。そのような場合、複数ビットの組合せの定義済みビット値が識別されると、ビットシーケンスの先行する解析済みの部分、及び任意的ではあるが事前定義済みビット長の後続する部分は、基準符号語及び間隔符号語の一方、好ましくは間隔符号語を構成する。例えば、テーブルＩで表されるような間隔符号語が使用される場合、圧縮ブロックの解析は、最初にゼロに達するまで又は１２ビットが解析されるまで実行される。この解析部分は間隔符号語を構成する。テーブルＩＶにおいて、最初の１ｂｉｎの前に５つの０ｂｉｎがない限り、最初の１ｂｉｎを含む最初の１ｂｉｎまでの解析部分は間隔符号語を構成する。そのような場合、解析部分＋後続する３ビットが間隔符号語を構成する。
【０１２７】
次のステップＳ６１は、圧縮ブロックの解析部分（及び任意的ではあるが事前定義済み固定長の後続する部分）として間隔符号語を規定する。識別された間隔符号語に後続する圧縮ブロックの一部は、ステップＳ６２において基準符号語として規定される。間隔符号語及び基準符号語のビット長は固定であり、事前定義済み最大値に等しい。その後、本方法は図９のステップＳ５２に継続する。
【０１２８】
図１１は、図９の成分値決定ステップを更に詳細に示すフローダイアグラムである。方法は、図９のステップＳ５２から継続する。次のステップＳ７０は、間隔符号語に基づいて（Ｘ又はＹ）間隔長を決定する。この決定は、符号語から長さを直接計算することにより実行される。別の方法において符号語は、関数及びルックアップテーブル等に対する入力として使用され、対応する間隔長を与える。複数の成分値は、この間隔長及び基準値に基づいて計算される。
【０１２９】
好適な実現例において、方法はステップＳ７１に継続し、間隔の開始点が決定される。基準値が間隔の開始点を表す場合、この決定は基準値のみを使用して実行されうる。あるいは、決定は基準値及び間隔長の双方を使用して実行される。対応するステップＳ７２は、基準値、あるいは基準値及び間隔長を使用して間隔の終了点を決定する。複数の圧縮値は、ステップ７３において開始点及び終了点の線形結合として計算されるのが好ましい：
【０１３０】
【数８】
2009534914.tif 000020
式中、ＸｉはＸ成分値を示し、Ｘｍｉｎは間隔の開始点であり、Ｘｍａｘは間隔の終了点である。ＮＸはＸ成分値の数であり、ｉ＝０，１，．．．ＮＸ−１である。ＮＸは好ましくは８である。Ｘ基準値が間隔の開始点、間隔の中間点、間隔の終了点のいずれであるかに依存して、開始点及び終了点は式１０〜式１２のいずれかに従って計算されうる：
【０１３１】
【数９】
2009534914.tif 000021
【０１３２】
【数１０】
2009534914.tif 000022
【０１３３】
【数１１】
2009534914.tif 000023
【０１３４】
その後、方法は図９のステップＳ５４に継続する。
【０１３５】
図１２Ａ〜図１２Ｃは、間隔符号語により規定される間隔２０内の種々の成分値５０の概念を示す図である。図１２Ａにおいて、基準値１０は間隔２０の中間点を表す。間隔の開始点３０及び終了点４０は、上記式１１を使用して基準値１０及び間隔長２０から計算されうる。８つの成分値５０は、上記式９を使用して端点３０、４０から取得される。尚、当然、成分値は基準値１０及び間隔長２０から、最初に端点３０、４０を計算することなく、直接計算されうる。例えば、式６を参照せよ。
【０１３６】
図１２Ｂにおいて、間隔長２０は図１２Ａより比較的大きい。更に、基準値１０は間隔の開始点３０である。端点４０は式１０から取得可能である。間隔２０はここでは相対的に大きいため、成分値５０間の距離も図１２Ａと比較して増加する。図１２Ｃは、小さな間隔長２０を含む図を示す。ここで、基準値１０は間隔２０の端点４０を示す。
【０１３７】
本発明に従って、２つのベクトル成分の復号化が、組み合わせて実行されうる。例えば、２つの間隔符号語は角度及び半径を表すことができる。そのような場合、圧縮ブロックは半径を符号化する間隔符号語を見つけるために解析されるのが好ましい。その結果、２つの基準符号語の識別が可能になる。本実施形態の好適な実現例において、Ｘ基準符号語及びＹ基準符号語は同一のビット分解能を有する。更に、角度を符号化する間隔符号語は固定長を有する。ｒが第１の間隔符号語により表される半径であり、θが第２の符号語により表される角度である場合、Ｘ間隔長はｒ×ｃｏｓ（θ）として決定され、Ｙ間隔長はｒ×ｓｉｎ（θ）である。上述したように、異なるＸ成分値及びＹ成分値は、Ｘ間隔長及びＹ間隔長、並びにＸ基準値及びＹ基準値から計算される。
【０１３８】
図１２Ｄは、別の組み合わせ伸張を示す。図１２Ｄにおいて、間隔符号語の一方は対角線２５を表し、他方は間隔長２０を計算するために対角線２５と共に使用される重みを表す。Ｘ／Ｙビットは、間隔長２０がＸ間隔であるべきか又はＹ間隔であるべきかを決定する。もう一方の間隔は、対角線２５及び第１の間隔２０から計算される。基準値１０、１５は、２つの計算した間隔２０の位置を与える。図１２Ｄにおいて、Ｙ間隔の開始点３５及び終了点４５並びにＹ成分値５５が、対応するＸ点３０、４０及び値５０に加えて示される。
【０１３９】
伸張の例
本明細書において、図３Ａ〜図３Ｃに示したようなビットシーケンスのレイアウトを使用する伸張の例を次に示す。
【０１４０】
圧縮画像ブロックは、以下のビットシーケンスにより表される：
１１００１１００１１１１０１００  １１０  ００１  ．．．  ００１
１１１１１１１１０１０１１００１  １０１  １１０  ．．．  ０１０
【０１４１】
本明細書において、テーブルＩは種々の間隔符号語を与えるために使用される。Ｘベクトル成分から開始し、圧縮ブロックの最初の６４ビットは、Ｘ間隔符号語を見つけるために初めから終わりに向かって解析される。この場合、最初にゼロに到達した時に解析は終了される。このゼロ及び先行するビット、すなわち１１０ｂｉｎはＸ間隔符号語を構成する。テーブルＩにおいて、その符号語は１／４という間隔の幅に対応する。
【０１４２】
後続する１６−Ｌ（ＷＸ）＝１３ビットは基準符号語を形成する。最初の８ビットは整数ビットであり、残りの５ビットは端数ビットを形成する。
【０１４３】
整数：０１１００１１１ｂｉｎ  ＝  １０３
端数：１０１００ｂｉｎ  ＝  １／２＋１／８  ＝  ０．６２５
【０１４４】
従って、Ｘ基準値は１０３．６２５であり、Ｘ間隔長は０．２５である。
【０１４５】
同一の手順がＹ成分に対して実行され、６４ビット目から開始して、最後の６４ビットがまず解析される。この場合、Ｙ間隔符号語は１１１１１１１１０ｂｉｎであり、これはテーブルＩによると２４＝１６の間隔長に対応する。後続する１６−Ｌ（ＷＹ）＝７ビットはＹ基準符号語を形成する。符号語は、Ｙ基準値が計算されうる前にまず８ビットに拡大される：
【０１４６】
１０１１００１ｂｉｎ→１０１１００１１ｂｉｎ＝１７９
【０１４７】
よって、Ｙ基準値は１７９であり、Ｙ間隔長は１６である。
【０１４８】
この説明例において、基準値は間隔の中間点を表す。上記式６は可能なＸ成分値及びＹ成分値を与える：
【０１４９】
【数１２】
2009534914.tif 000024
【０１５０】
【数１３】
2009534914.tif 000025
【０１５１】
ＶａｌｕｅＸ  ＝  （１０３．５，  １０３．５３６，  １０３．５７１，  １０３．６０７，  １０３．６４３，  １０３．６７９，  １０３．７１４，  １０３．７５）
ＶａｌｕｅＹ  ＝  （１７１，  １７３．２８６，  １７５．５７１，  １７７．８５７，  １８０．１４３，  １８２．４２９，  １８４．７１４，  １８７）
【０１５２】
第１の画像要素はＸ成分インデックス１１０ｂｉｎ及びＹ成分インデックス１０１ｂｉｎを有する。これは、Ｘ成分値１０３．７１４及びＹ成分値１８２．４２９が選択されるべきであることを意味する。間隔［−１，１］への再マッピングが使用される場合、それらの値は２×１０３．７１４／２５５−１＝−０．１８７及び２×１８２．４２９／２５５−１＝０．４３１となる。画像要素に対するＺ座標表現は、式１を使用してそれら２つの再マッピング値から計算され、
【数１４】
2009534914.tif 000026
となる。従って、第１の画像要素に対する最終的な法線は、（Ｘ，Ｙ，Ｚ）＝（−０．１８７，０．４３１，０．４７０）である。
【０１５３】
第２の画像要素は、Ｘ成分値１０３．５３６に対応するＸインデックス００１ｂｉｎ及び値１８４．７１４に関連付けられるＹインデックス１１０ｂｉｎを有する。再マッピング後、値は−０．１８８及び０．４４９となる。Ｚ座標は０．４８７となる。第２の画像要素に対する法線は、（Ｘ，Ｙ，Ｚ）＝（−０．１８８，０．４４９，０．４８７）である。この手順は、復号化されるべきブロック中の残りの画像要素に対して継続される。
【０１５４】
実現例の様相
本発明に係る画像（ブロック）圧縮及び画像（ブロック）伸張方式は、汎用データ処理システム中で、例えばユーザ端末中で、あるいは画像の処理又はレンダリングの少なくとも片方をするように構成された他のユニット中で、提供されうる。そのような端末は、携帯情報端末（ＰＤＡ）、移動ユニット及び電話機のような、コンピュータであってもよい。このコンピュータは、例えばＰＣ、ゲームコンソール、又はシンクライアントである。
【０１５５】
ユーザ端末
図１３は、移動ユニットにより表されるユーザ端末１００を示す。しかし、本発明は移動ユニットに限定されず、データ処理ユニット及び他の端末において、例えばＰＣコンピュータ及びゲームコンソールにおいて、実現できる。本発明に直接関わる移動ユニット１００の手段及び要素のみを図示する。
【０１５６】
移動ユニット１００は、移動ユニット１００内で画像データを含むデータを処理するための（中央）処理装置（ＣＰＵ）２００を備える。グラフィックシステム１３０は、画像及びグラフィックデータを管理するために移動ユニット１００に提供される。特にグラフィックシステム１３０は、接続された画面１２０又は他の表示ユニット上に画像をレンダリング又は表示するように構成される。移動ユニット１００は、データを格納するために記憶装置又はメモリ１４０を更に備える。画像データ、特に本発明に係る圧縮画像データがこのメモリ１４０に格納されてもよい。
【０１５７】
本発明に係る画像圧縮器２１０は、一般に移動ユニット１００中で提供される。この圧縮器２１０は、画像又はテクスチャを画像の圧縮表現に圧縮するように構成される。上述したように、そのような圧縮表現は、複数の圧縮画像ブロックの、シーケンス又はファイルを備える。この画像圧縮器２１０は、図示されるように、ＣＰＵ２００上で実行するソフトウェアとして提供されてもよい。あるいは又はそれに加えて、圧縮器２１０は、グラフィックシステム１３０、又は移動ユニット１００の他の場所に、配置されてもよい。
【０１５８】
ブロック圧縮器２１０からの画像の圧縮表現は、画像を後でレンダリングするまで格納するために、（メモリ）バス１５０を介してメモリ１４０に提供されてもよい。あるいは又はそれに加えて、圧縮画像データは、他の外部端末又はユニットに（無線又は有線）送信するために入出力（Ｉ／Ｏ）ユニット１１０に転送されてもよい。Ｉ／Ｏユニット１１０は、例えばユーザ端末の、一続きの送信機及び受信機を表してもよい。Ｉ／Ｏユニット１１０は、外部ユニットから画像データを受信するように構成されてもよい。この画像データは、画像圧縮器２１０により圧縮されるべき画像、又は伸張されるべき圧縮画像データであってもよい。更に、例えばグラフィックシステム１３０中で提供される、専用テクスチャメモリに圧縮画像表現を格納することも可能である。また、圧縮画像の一部が、例えばグラフィックシステム１３０中の、テクスチャキャッシュメモリにも（一時的に）格納されてよく、あるいはテクスチャキャッシュメモリに代わりに（一時的に）格納されてもよい。
【０１５９】
伸張画像表現を生成するために圧縮画像を伸張するために、一般には本発明に係る画像伸張器２２０は移動ユニット１００に提供される。この伸張表現は、元の画像全体に対応しても良く、又はその一部に対応してもよい。画像伸張器２２０は伸張画像データをグラフィックシステム１３０に提供し、通常、レンダリング又は画面１２０上に提示される前に、グラフィックシステム１３０はデータを処理する。図示されるように、画像伸張器２２０はグラフィックスシステム１３０に配置されることができる。
【０１６０】
あるいは又はそれに加えて、ＣＰＵ２００、又は移動ユニット１００の他の場所で実行されるソフトウェアとして、復号器２００が提供されてもよい。
【０１６１】
図示するように、移動ユニット１００は、画像圧縮器２１０及び画像伸張器２２０の双方を装備してもよい。しかし、いくつかの端末１００については、画像圧縮器２１０のみを含むことが可能であるかもしれない。そのような場合、圧縮画像データは、画像の伸張、及び場合によってはレンダリングを実行する、別の端末に送信されてもよい。同様に、端末１００は画像伸張器２２０のみを含むことが可能であるかもしれない。これはすなわち、圧縮器を有さないということである。そのような端末１００は、別のエンティティからの圧縮画像データを備える信号を受信し、それを伸張して伸張画像表現を生成する。このように、圧縮画像信号は無線送信機及び無線受信機を使用して端末間で無線送信されてもよい。あるいは、本発明に従って端末間で画像及び圧縮画像表現を配信する他の技術が採用可能であり、例えばＢＬＵＥＴＯＯＴＨ（登録商標）、赤外線ポートを使用する赤外線技術、及び端末間の画像データの有線転送が採用可能である。更に、接続可能であり且つ端末間で交換可能である、ＵＳＢメモリを含むメモリカード又はチップが、この画像データ端末間配信に対して使用可能である。
【０１６２】
移動ユニット１００のユニット１１０、１３０、２００、２１０及び２２０は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。
【０１６３】
画像符号器
図１４は、本発明に係る画像圧縮器２１０の一実施形態を示すブロック図である。一般に圧縮器２１０は、入力画像をいくつかの画像ブロックに分解又は分割する画像分解器２１５を備える。分解器２１５は、１６個の画像要素（画素、テクセル又はボクセル）を備える画像ブロック、すなわち一般的に画像要素４×４個分のサイズを有する画像ブロック、に画像を分解するように構成されるのが好ましい。この分解器２１５は、異なる入力画像を異なるサイズの画像ブロックに分解するように構成されてもよい。そのような場合、分解器２１５は入力情報を受信するのが好ましく、それにより所定の画像に対して使用する画像ブロック形式の識別が可能になる。
【０１６４】
画像圧縮器２１０の本実施形態は、ブロック圧縮器３００を備える。このブロック圧縮器３００は、画像分解器から受信した画像ブロックを圧縮し、圧縮ブロック表現を生成する。ブロック表現の全体のサイズは、非符号化画像ブロックの対応するサイズより小さい。ブロック圧縮器３００は、分解器２１５からの各画像ブロックを順次処理（符号化）するように構成されるのが好ましい。
【０１６５】
別の実現例において、圧縮器２１０は、画像分解器２１５からの複数の画像ブロックを並列処理する複数のブロック圧縮器３００を含む。それにより、画像符号化時間の合計は短縮される。
【０１６６】
画像圧縮器２１０のユニット２１５及び３００は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット２１５及び３００は、画像圧縮器２１０に一緒に実装されてもよい。あるいは、いくつかのユニットが移動ユニットの他の場所に提供される、分散型の実装も可能である。
【０１６７】
ブロック符号器
図１５は、図１４の画像圧縮器のブロック圧縮器等の本発明に係るブロック圧縮器３００の一実施形態を示すブロック図である。圧縮器３００は、（Ｘ又はＹ）基準符号語、（Ｘ又はＹ）間隔符号語及び（Ｘ又はＹ）インデックスシーケンスのうち少なくとも２つに対する各ビット分解能を規定するように構成された分解能定義器３１０を備える。定義器３１０は、圧縮される画像ブロックの元のＸベクトル成分及びＹベクトル成分を受信し、それら成分の少なくとも一部に基づいてビット分解能の規定を行う。基準量子化器３２０は、（Ｘ又はＹ）基準値の表現として（Ｘ又はＹ）基準符号語を決定するように構成される。この符号語の決定は、（Ｘ又はＹ）ベクトル成分の少なくとも一部に基づいて、また好ましくは分解能定義器３２０により規定されるビット分解能、すなわちビット換算の符号語長にも基づいて、実行される。対応する間隔量子化器３３０は、ブロック符号器３００において、（Ｘ又はＹ）基準値と相関する複数の（Ｘ又はＹ）成分値を含む（Ｘ又はＹ）間隔の表現として（Ｘ又はＹ）間隔符号語を決定するように構成される。量子化器３３０は、（Ｘ又はＹ）ベクトル成分の少なくとも一部に基づいて、また好ましくは定義器３１０により符号語に割り当てられたビット分解能にも基づいて、その符号語の決定を実行する。圧縮器３００は、インデックス量子化器３４０を更に備える。この量子化器３４０は、（Ｘ又はＹ）間隔に含まれる（Ｘ又はＹ）値から選択された１つの（Ｘ又はＹ）成分値を、ブロック中の画像要素毎に示す、（Ｘ又はＹ）インデックスシーケンスを決定するように構成される。インデックス量子化器３４０は、複数の（Ｘ又はＹ）値のうち、ブロック中の画像要素の（Ｘ又はＹ）ベクトル成分を最適に表す（Ｘ又はＹ）成分値を識別するのが好ましい。この識別は、符号器に配置された誤差推定器３５０を使用して実行されるのが好ましい。識別された成分値と関連付けられる（Ｘ又はＹ）成分インデックスは、インデックス量子化器３４０により提供される。誤差推定器３５０は、その（Ｘ又はＹ）成分値を含む画像要素の（Ｘ又はＹ）ベクトル成分を表す誤差推定値を、複数の利用可能な（Ｘ又はＹ）値のうちの（Ｘ又はＹ）成分値毎に推定するように実装される。従って、提供される（Ｘ又はＹ）成分インデックスにより、その画像要素の特徴ベクトルの元の（Ｘ又はＹ）ベクトル成分を最適に表す（Ｘ又はＹ）成分値、すなわち最小の誤差と関連付けられる（Ｘ又はＹ）成分値の、識別が可能になる。異なるの（Ｘ又はＹ）成分インデックスが一緒に、（Ｘ又はＹ）インデックスシーケンスを形成する。
【０１６８】
ブロック圧縮器３００は、画像ブロックの最大の（Ｘ又はＹ）ベクトル成分及び最小の（Ｘ又はＹ）ベクトル成分を識別するように構成された成分識別器３６０を更に備えるのが好ましい。この情報は、分解能定義器３１０、基準量子化器３２０及び間隔量子化器３３０により使用される情報であればよい。例えば、間隔量子化器３３０は、最大の（Ｘ又はＹ）ベクトル成分と最小の（Ｘ又はＹ）ベクトル成分との差分の表現として（Ｘ又はＹ）間隔符号語を決定するように構成されることができる。量子化器３３０は、関数、事前定義済みセット、又は図示するように複数の事前定義済み（Ｘ又はＹ）間隔符号語を備えるルックアップテーブル３７０への入力として、差分を使用するのが好ましい。従って、量子化器３３０は、最大の（Ｘ及びＹ）成分値と最小の（Ｘ及びＹ）成分値との差分に最も近い間隔長と関連付けられる（Ｘ又はＹ）符号語を選択する。テーブル３７０の少なくとも一部の符号語は異なるビット長を有し、本発明の動的可変ビット分解能を提供する。
【０１６９】
基準量子化器３２０は、（Ｘ又はＹ）間隔符号語により表される間隔の開始点、間隔の中間点又は間隔の終了点として、（Ｘ又はＹ）基準符号語を決定するのが好ましい。開始点の場合、基準量子化器３２０は、成分識別器３６０からの最小（Ｘ又はＹ）値の情報を使用し、その最小値の表現として（Ｘ又はＹ）基準符号語を生成する。同様に、（Ｘ又はＹ）値が終了点である場合、基準量子化器３２０は最大（Ｘ又はＹ）値の情報を使用する。（Ｘ又はＹ）基準値が間隔の中間点になる場合、双方の（Ｘ又はＹ）値が量子化器３２０により使用される。
【０１７０】
分解能定義器３１０は、（Ｘ又はＹ）ベクトル成分の分布に基づいて各ビット分解能を規定するのが好ましい。この分布は、識別器３６０からの最大の（Ｘ又はＹ）成分及び最小の（Ｘ又はＹ）成分に基づいて決定される。定義器３１０は、例えば最大の（Ｘ又はＹ）ベクトル成分と最小の（Ｘ又はＹ）ベクトル成分との差分に基づいてビット分解能を規定できる。
【０１７１】
ブロック圧縮器３００のユニット３１０〜３６０は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット３１０〜３７０は、ブロック圧縮器３００に一緒に実装されてもよい。あるいは、いくつかのユニットが画像圧縮器の他の場所に提供される分散型の実装も可能である。
【０１７２】
図１６は、図１５の分解能定義器３１０の一実施形態を更に詳細に示す概略ブロック図である。この定義器３１０は、（Ｘ又はＹ）ベクトル成分の少なくとも一部に基づいて、好ましくは最大の（Ｘ又はＹ）ベクトル成分及び最小の（Ｘ又はＹ）ベクトル成分に基づいて、（Ｘ又はＹ）間隔符号語に対するビット分解能を規定するように構成される。分解能計算器３１２は、この間隔符号語分解能及び事前定義済み最大分解能値から（Ｘ又はＹ）基準符号語の対応するビット分解能を計算するために定義器３１０に実装される。
【０１７３】
分解能定義器３１０のユニット３１２は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット３１２は、ブロック圧縮器の他の場所に実装されてもよい。
【０１７４】
図１７は、図１５のインデックス量子化器３３０の一実施形態を更に詳細に示す概略ブロック図である。量子化器３３０は、（Ｘ又はＹ）間隔に含まれる複数の（Ｘ又はＹ）値のうち１つの（Ｘ又はＹ）成分値を、ブロック中の画像要素毎に選択するように構成された値選択器３３２を具備する。この選択された（Ｘ又はＹ）値は、利用可能な値の最小の誤差を与える。インデックス識別器３３４は、選択器３３２により選択された（Ｘ又はＹ）成分値に基づいて、複数の画像要素の集合に対して合成（Ｘ又はＹ）成分インデックスを識別する。これは、１つの（Ｘ又はＹ）インデックスがいくつかの画像要素に対して一括して使用されることを意味する。識別器３３４は、複数のそのような成分インデックスを備えるルックアップテーブル３３６にアクセスできるのが好ましい。従って、識別器３３４は、このテーブル３３６から最適な合成インデックスを選択する。結果として得られる（Ｘ又はＹ）インデックスシーケンスは、本実施形態において、少なくとも１つのそのような合成インデックスを含む。また、結果として得られる（Ｘ又はＹ）インデックスシーケンスは、本実施形態において、単一の画像要素のみに対して割り当てられた少なくとも１つの従来の（Ｘ又はＹ）成分インデックスを含むことも自由である。
【０１７５】
インデックス量子化器３３０のユニット３３２及び３３４は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット３３２、３３４及び３３６は、代わりにブロック圧縮器の他の場所に実装されてもよい。
【０１７６】
画像復号器
図１８は、本発明に係る画像伸張器２２０の一実施形態を示すブロック図である。画像伸張器２２０は、伸張のためにブロック伸張器４００に提供されるべき符号化画像ブロックを、例えばメモリから、選択するように構成されたブロック選択器２２２を備えることが好ましい。ブロック選択器２２２は、例えばヘッダ又はレンダリングエンジンから、圧縮画像データと関連付けられた入力情報を受信するのが好ましい。所望の画像要素を有する圧縮画像ブロックのアドレスは、入力情報に基づいて算出される。この算出されたアドレスは、画像内の画像要素（画素、テクセル又はボクセル）の座標に依存するのが好ましい。ブロック選択器２２２は、アドレスを使用してメモリからの圧縮画像ブロックを識別する。この識別された圧縮画像ブロックは、記憶装置から取り出され、ブロック伸張器４００に提供される。
【０１７７】
画像ブロックの画像要素への（ランダム）アクセスにより、必要とされる画像の部分のみを選択的に伸張することが可能となり、これは有利である。更に画像は、どのような順番でデータが要求されても、伸張されることが可能である。例えばテクスチャマッピングにおいて、テクスチャの一部のみが要求されるかもしれず、一般にはそれらテクスチャの一部は非連続的な順番で要求されるだろう。従って、本発明の画像伸張は、画像の一部又は一区分のみを処理するように適用されることで、有利となる。
【０１７８】
選択された圧縮画像ブロックは、ブロック伸張器４００に転送される。画像ブロックに加えて、伸張器４００は復号化されるべきブロックの画像要素を特定する情報を受信するのが好ましい。受信した情報は、画像ブロック全体、すなわち画像ブロック中の全ての画像要素が復号化されるべきであることを特定できるだろう。とはいえ、受信した情報は、復号化されるべき単一の画像要素又はいくつかの画像要素のみを識別できる。その後ブロック伸張器４００は、ブロック中の画像要素の伸張表現を生成する。
【０１７９】
画像合成器２２４が、画像伸張器２２０に提供されることも自由である。この合成器は、ブロック伸張器４００から復号化画像要素を受信し、それらを合成してレンダリングされうる、又は画面上に表示されうる画素を生成する。この画像合成器２２４は、代わりにグラフィックシステムに提供されてもよい。
【０１８０】
あるいは、画像伸張器２２０は複数のブロック伸張器４００を備える。複数のブロック伸張器４００へのアクセスを有することにより、画像復号器２２０は複数の符号化画像ブロックを並行して処理できる。それら複数のブロック伸張器４００は、画像伸張器２２０の処理性能及び効率を向上する並列処理を可能にする。
【０１８１】
画像伸張器２２０のユニット２２２、２２４及び４００は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット２２２、２２４及び４００は、画像伸張器２２０に一緒に実装されてもよい。あるいは、いくつかのユニットがユーザ端末の他の場所に提供される、分散型の実装も可能である。
【０１８２】
ブロック復号器
図１９は、本発明に係るブロック伸張器４００の一実施形態を示す。ブロック伸張器４００は、圧縮ブロックの少なくとも一部のビットパターンに基づいて、（Ｘ又はＹ）基準符号語及び（Ｘ又はＹ）間隔符号語の一方を識別するように構成された、符号語識別器４１０を備える。識別器４１０は、最初に識別した（Ｘ又はＹ）符号語に基づいて、（Ｘ又はＹ）基準符号語及び（Ｘ又はＹ）間隔符号語のの他方を更に識別する。好適な実現例において、識別器４１０は、（Ｘ又はＹ）基準符号語及び（Ｘ又はＹ）間隔符号語のうち最初の符号語を識別すると、その符号語のビット長を決定する。その長さ及び事前定義済み最大値を与えられると、識別器４１０は、圧縮ブロック中の後続する部分として（Ｘ又はＹ）基準符号語及び（Ｘ又はＹ）間隔符号語のうちの他方を見つけられる。
【０１８３】
上述したように、基準値生成器４２０は、（Ｘ又はＹ）基準値を決定するために識別された（Ｘ又はＹ）基準符号語を使用する。成分値生成器４３０は、決定された（Ｘ又はＹ）基準値及び識別された（Ｘ又はＹ）間隔符号語を、複数の（Ｘ又はＹ）成分値の生成のための入力として使用する。ブロック伸張器４００は、生成された複数の成分値から、１つの（Ｘ又はＹ）成分値を、少なくとも１つの画像要素に対して選択するために、（Ｘ又はＹ）インデックスシーケンスを使用する値選択器４４０を更に備える。一般的な方法において、選択器４４０は、１つの成分値を選択するために、現在の画像要素と関連付けられた（Ｘ又はＹ）成分インデックスを識別する。合成インデックスの場合、選択器４４０は、複数の画像要素に対する（Ｘ又はＹ）成分値を一括して同時に選択できる。この選択は、上記テーブルＶ等のルックアップテーブル４５０を使用して行なわれるのが好ましい。
【０１８４】
ブロック伸張器４００のユニット４１０〜４４０は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット４１０〜４５０は、ブロック伸張器４００中に一緒に実装されてもよい。あるいは、いくつかのユニットが画像伸張器の他の場所に提供される、分散型の実装も可能である。
【０１８５】
図２０は、図１９の符号語識別器４１０の一実施形態を更に詳細に示す概略ブロック図である。符号語識別器４１０は、事前定義済みビットパターンに達するまで圧縮ブロックの選択部分を解析するように構成された、ビット解析器４１２を備える。一般に解析器は、第１の（Ｘ）ベクトル成分に対する圧縮ブロックの初めから、また第２の（Ｙ）成分に対するブロックの中間から、解析を開始する。これについては、図３Ａ〜図３Ｃを参照せよ。このビットパターンは、最初が０ｂｉｎであっても、最初が１ｂｉｎであっても、若しくは最初が０又は１の組合せであってもよい。更にビットパターンは、最長の圧縮ブロックの一区分であってもよい。識別器４１０の符号語定義器４１４は、事前定義済みビットパターンまでの、好ましくは事前定義済みビットパターンを含む、圧縮ブロックの解析部分を、（Ｘ又はＹ）基準符号語及び（Ｘ又はＹ）間隔符号語のうちの一方として、好ましくは（Ｘ又はＹ）間隔符号語として、規定するように構成される。定義器４１４は、圧縮ブロックの後続する部分を、（Ｘ又はＹ）基準符号語及び（Ｘ又はＹ）間隔符号語のうちの他方として、好ましくは（Ｘ又はＹ）基準符号語として、更に規定する。（Ｘ又はＹ）間隔符号語として識別された部分、及び（Ｘ又はＹ）基準符号語として識別された部分のビット長は、全ての画像ブロックに対して固定であり、事前定義済み最大値と等しい。
【０１８６】
符号語識別器４１０のユニット４１２及び４１４は、ソフトウェア、ハードウェア又はそれらの組合せとして提供されてもよい。ユニット４１２及び４１４は、ブロック伸張器４００の他の場所に実装されてもよい。
【０１８７】
図２１は、図１９の成分値生成器４３０の一実施形態を更に詳細に示す概略ブロック図である。値生成器４３０は、間隔符号語に基づいて（Ｘ又はＹ）間隔長を決定するように構成された間隔生成器４３２を備える。この間隔長は、符号語から直接計算されうる。別の方法において生成器４３２は、値生成器４３０に配置されるか又はブロック復号器の他の場所に提供される、ルックアップテーブル又は関数を利用する（図１９のテーブル４５０を参照）。値生成器４３０の値計算器４３４は、間隔生成器４３２からの（Ｘ又はＹ）間隔長と、基準値生成器からの（Ｘ又はＹ）基準値とに基づいて複数の（Ｘ又はＹ）成分値を計算するように構成される。
【０１８８】
好適な実現例において、値生成器４３０は、開始点生成器４３６及び終了点生成器４３８を更に備える。それら生成器４３６、４３８は、間隔長及び基準値を使用して（Ｘ又はＹ）間隔の開始点及び終了点を計算する。値計算器４３４は、一般には開始点及び終了点の線形結合として、複数の（Ｘ又はＹ）成分値を計算するために、この２つの端点の情報を使用できる。
【０１８９】
上述において、法線、好ましくは正規化面法線、を特徴ベクトルとして有する画像ブロックの処理を参照して本発明を説明した。別の実現例において、特徴ベクトルは、ＲＧＢ（赤色、緑色、青色）空間等の色空間における色ベクトルであってもよい。そのような場合、圧縮画像ブロックは、ＲＧＢ点等の、色空間における基本色を表す１つの基準符号語を備える。間隔符号語は、基本色に対して色空間におけるベクトルを表すことができる。すなわち間隔符号語は、間隔長及び方向の双方を規定する。基本色及びベクトルは、色空間において開始点及び終了点を有する間隔を共に規定する。この間隔は、間隔の２つの端点の線形結合として取得可能であることが好ましい、複数の色値を含む。圧縮ブロックは、画像要素毎に色インデックスを有するインデックスシーケンスを更に備え、色インデックスは複数の色値のうちの１つとそれぞれ関連付けられる。本発明によると、圧縮ブロックの合計のビット長が同一のままで、間隔符号語及び基準符号語に対するビット分解能が適応及び変動可能である。例えば間隔長が大きい場合、間隔符号語は相対的に長いビット長を有することができ、基準符号語に対して残されるビット数はより少なくなる。しかし、間隔長が短い場合、それに対応してより多くのビットが基準符号語に対して使用され、間隔符号語に対するビット数はより少なくなる。
【０１９０】
間隔符号語が、例えば角度表現部分及び半径表現部分の２つの部分から構成可能であることは、本発明から予想される。そのような場合、角度表現部分に使用されるビット数は固定であり、一方、半径表現部分のビット長は色空間の画像要素の元の色ベクトルの分布に依存して調整されうる。
【０１９１】
添付の請求の範囲により規定される本発明の範囲から逸脱せずに、種々の変形及び変更が本発明に対して行なわれてもよいことが当業者には理解されるだろう。
【０１９２】
＜参考文献＞
［１］ｈｔｔｐ：／／ｗｗｗ．ａｔｉ．ｃｏｍ／ｐｒｏｄｕｃｔｓ／ｒａｄｅｏｎｘ８００／３ＤｃＷｈｉｔｅＰａｐｅｒ．ｐｄｆ  ＡＴＩ（登録商標）  Ｒａｄｅｏｎ（登録商標）  Ｘ８００  ３Ｄｃ（登録商標）  Ｗｈｉｔｅ  Ｐａｐｅｒ
［２］米国特許第５，９５６，４３１号明細書
［３］Ｍｕｎｋｂｅｒｇ他「Ｈｉｇｈ  ｑｕａｌｉｔｙ  ｎｏｒｍａｌ  ｍａｐ  ｃｏｍｐｒｅｓｓｉｏｎ」，Ｇｒａｐｈｉｃｓ  Ｈａｒｄｗａｒｅ  Ｓｅｐｔｅｍｂｅｒ  ２００６
［４］国際特許出願第ＰＣＴ／ＳＥ２００７／００００５３号
【図面の簡単な説明】
【０１９３】
【図１】本発明の一実施形態に係る画像圧縮方法及び画像ブロック圧縮方法を示すフローダイアグラムである。
【図２】本発明に係る画像ブロックの一実施形態を示す図である。
【図３Ａ】、
【図３Ｂ】、
【図３Ｃ】本発明に係る画像ブロックの圧縮表現の種々の実施形態を示す図である。
【図４】図１のビット分解能を規定するステップの一実施形態を更に詳細に示すフローダイアグラムである。
【図５】Ｘ，Ｙ平面におけるベクトル成分の分布を示す図である。
【図６】図１の間隔符号語を決定するステップの一実施形態を更に詳細に示すフローダイアグラムである。
【図７】図１のインデックスシーケンスを決定するステップの一実施形態を更に詳細に示すフローダイアグラムである。
【図８】図１のインデックスシーケンスを決定するステップの別の実施形態を更に詳細に示すフローダイアグラムである。
【図９】本発明の一実施形態に係る画像伸張方法及び画像ブロック伸張方法を示すフローダイアグラムである。
【図１０】図９の符号語を識別するステップの一実施形態を更に詳細に示すフローダイアグラムである。
【図１１】図９の成分値を決定するステップの一実施形態を更に詳細に示すフローダイアグラムである。
【図１２Ａ】、
【図１２Ｂ】、
【図１２Ｃ】第１のベクトル成分に対する成分値の計算を示す図である。
【図１２Ｄ】第１のベクトル成分及び第２のベクトル成分に対する成分値の計算を示す図である。
【図１３】本発明に係る画像圧縮器及び画像伸張器を有するユーザ端末の一例を概略的に示す図である。
【図１４】本発明に係る画像圧縮器の一実施形態を概略的に示すブロック図である。
【図１５】本発明に係るブロック圧縮器の一実施形態を概略的に示すブロック図である。
【図１６】図１５の分解能定義器の一実施形態を更に詳細に概略的に示すブロック図である。
【図１７】図１５のインデックス量子化器の一実施形態を更に詳細に概略的に示すブロック図である。
【図１８】本発明に係る画像伸張器の一実施形態を概略的に示すブロック図である。
【図１９】本発明に係るブロック伸張器の一実施形態を概略的に示すブロック図である。
【図２０】図１９の符号語識別器の一実施形態を更に詳細に概略的に示すブロック図である。
【図２１】図１９の成分値生成器の一実施形態を更に詳細に概略的に示すブロック図である。
【図１】
2009534914.tif 000027
【図２】
2009534914.tif 000028
【図３Ａ】
2009534914.tif 000029
【図３Ｂ】
2009534914.tif 000030
【図３Ｃ】
2009534914.tif 000031
【図４】
2009534914.tif 000032
【図５】
2009534914.tif 000033
【図６】
2009534914.tif 000034
【図７】
2009534914.tif 000035
【図８】
2009534914.tif 000036
【図９】
2009534914.tif 000037
【図１０】
2009534914.tif 000038
【図１１】
2009534914.tif 000039
【図１２Ａ】
2009534914.tif 000040
【図１２Ｂ】
2009534914.tif 000041
【図１２Ｃ】
2009534914.tif 000042
【図１２Ｄ】
2009534914.tif 000043
【図１３】
2009534914.tif 000044
【図１４】
2009534914.tif 000045
【図１５】
2009534914.tif 000046
【図１６】
2009534914.tif 000047
【図１７】
2009534914.tif 000048
【図１８】
2009534914.tif 000049
【図１９】
2009534914.tif 000050
【図２０】
2009534914.tif 000051
【図２１】
2009534914.tif 000052
【国際調査報告】
2009534914.tif 000053
2009534914.tif 000054
2009534914.tif 000055
2009534914.tif 000056
2009534914.tif 000057
2009534914.tif 000058
2009534914.tif 000059
2009534914.tif 000060
2009534914.tif 000061
2009534914.tif 000062
2009534914.tif 000063
2009534914.tif 000064
2009534914.tif 000065
2009534914.tif 000066
2009534914.tif 000067
2009534914.tif 000068
2009534914.tif 000069
2009534914.tif 000070
2009534914.tif 000071
2009534914.tif 000072