(57)【特許請求の範囲】
【請求項１】
各々が各画素値を有する複数の画素（６）のタイル（１）を符号化する方法であって、前記方法は、
ｉ）前記タイル（１）の各サブセットを構成する複数の画素（６）のＮ個のブロック（４，５）を、前記Ｎ個のブロック（４，５）における前記複数の画素（６）の画素値の符号化表現としてのシンボルのＮ個のシーケンス（１０，２０，３０，４０，５０，６０）を形成するために可変長符号化する工程（Ｓ１）と、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）の前記シンボルを、シンボルの組み合わせシーケンス（７０）へと合同編成する工程（Ｓ２）と、
Ｎが奇数である場合には（Ｎ−１）／２個のポインタ（１１，１３）を、Ｎが偶数である場合にはＮ／２−１個のポインタ（１１，１３）を決定する工程（Ｓ３０）と、
前記組み合わせシーケンス（７０）と前記ポインタとをメモリ（１４０，３４０）へ格納する工程（Ｓ３）とを有し、
Ｎが３以上の整数である場合、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｍ＋１（１０，３０，５０）の前記シンボルは第１の読出し方向に読出し可能であり、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｎ（２０，４０）の前記シンボルは前記第１の読出し方向とは逆の第２の読出し方向に読出し可能であり、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号Ｎの前記シンボルは前記第２の読出し方向に読出し可能であり、
前記ポインタの各々は、前記組み合わせシーケンス（７０）におけるシーケンス番号２ｎ（２０，４０）の最上位シンボルのシンボル位置を規定し、
前記ｍは整数であり、かつ、ｍ∈［０，（Ｎ−２）／２］であり、
前記ｎは整数であり、かつ、ｎ∈［１，（Ｎ−１）／２］であり、
前記方法はさらに、
前記シーケンス番号２ｍ＋１（１０、３０）の最下位シンボルと前記シーケンス番号２ｎ（２０、４０）の最下位シンボルとの間に少なくとも１つのパッディングシンボル（２１，２３）を付加し、前記ポインタの全てが奇数又は偶数シンボル位置を示し、前記シンボル位置がシンボル位置２k又は２kに近接するシンボル位置を示すようにする工程を有し、
ｋ＝０又は自然数であることを特徴とする方法。
【請求項２】
グラフィック処理ユニット（３００）における前記メモリ（３４０）からバッファメモリ（４３０）へデータバス（３８０）により前記組み合わせシーケンス（７０）を送信する工程（Ｓ１０）をさらに有することを特徴とする請求項１に記載の方法。
【請求項３】
前記合同編成する工程（Ｓ２）は、Ｎ＝２である場合、
前記組み合わせシーケンス（７０）の第１の部分（７Ａ）において、前記第１の読出し方向に第１のシーケンス（１０）の前記シンボルを編成する工程（Ｓ２０）と、
前記組み合わせシーケンス（７０）の第１の部分に続く第２の部分（８Ａ）において、前記第２の読出し方向に第２のシーケンス（２０）の前記シンボルを編成する工程（Ｓ２１）とを有することを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記組み合わせシーケンス（７０）を送信する工程（Ｓ１０）は、
グラフィック処理ユニット（３００）における前記メモリ（３４０）からバッファメモリ（４３０）へ前記データバス（３８０）により前記組み合わせシーケンス（７０）を送信する工程（Ｓ１０）と、
前記グラフィック処理ユニット（３００）における前記メモリ（３４０）からディスプレイユニット（４００）におけるメモリ（２３０）へ前記データバス（３８０）により前記ポインタ（２１，２３）を送信する工程（Ｓ１０）とさらに有することを特徴とする請求項２に記載の方法。
【請求項５】
前記第２のシーケンス（２０）は前記第１のシーケンス（１０）より多くのシンボルを含み、
前記合同編成する工程（Ｓ２）は、前記第１のシーケンス（１０）の前記シンボルと前記第２のシーケンス（２０）の前記シンボルとを、シンボルの前記組み合わせシーケンス（７０）へと合同編成し、
前記組み合わせシーケンス（７０）において、
前記第１のシーケンス（１０）の前記シンボルは、前記組み合わせシーケンス（７０）の第１の部分（７Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の一方を占有し、
前記第２のシーケンス（２０）の前記シンボルの第１の部分は、前記組み合わせシーケンス（７０）の第１の部分（７Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の他方を占有し、
前記第２のシーケンス（２０）の前記シンボルの残りの第２の部分は、前記組み合わせシーケンス（７０）の残りの第２の部分（８Ｂ）における各奇数シンボル位置と各偶数シンボル位置との両方を占有し、
前記第１の部分（７Ｂ）におけるシンボルと前記残りの第２の部分（８Ｂ）における各奇数位置と各偶数位置との内の一方を占有するシンボルとは前記第１の読出し方向に読出し可能であり、
前記残りの第２の部分（８Ｂ）における各奇数位置と各偶数位置との内の他方を占有するシンボルは前記第２の読出し方向に読出し可能であることを特徴とする請求項３に記載の方法。
【請求項６】
各々が各画素値を有する複数の画素（６）のタイル（１）を符号化する装置（１００）であって、前記装置（１００）は、
前記タイル（１）の各サブセットを構成する複数の画素（６）のＮ個のブロック（４，５）を、前記Ｎ個のブロック（４，５）における前記複数の画素（６）の画素値の符号化表現としてのシンボルのＮ個のシーケンス（１０，２０，３０，４０，５０，６０）を形成するために可変長符号化するよう構成された可変長符号化器（１１０）と、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）の前記シンボルをシンボルの組み合わせシーケンス（７０）へと合同編成するよう構成されたシンボル編成器（１２０）と、
Ｎが奇数である場合には（Ｎ−１）／２個のポインタを、Ｎが偶数である場合にはＮ／２−１個のポインタを決定するよう構成されたポイント生成器（１６０）と、
前記組み合わせシーケンス（７０）をメモリ（１４０）へ格納するよう構成されたメモリコントローラ（１３０）とを有し、
Ｎが３以上の整数である場合、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｍ＋１（１０，３０，５０）の前記シンボルは第１の読出し方向に読出し可能であり、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｎ（２０，４０）の前記シンボルは前記第１の読出し方向とは逆の第２の読出し方向に読出し可能であり、
前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号Ｎの前記シンボルは前記第２の読出し方向に読出し可能であり、
前記ポインタの各々は、前記組み合わせシーケンス（７０）におけるシーケンス番号２ｎ（２０，４０）の最上位シンボルのシンボル位置を規定し、
前記ｍは整数であり、かつ、ｍ∈［０，（Ｎ−２）／２］であり、
前記ｎは整数であり、かつ、ｎ∈［１，（Ｎ−１）／２］であり、
前記装置はさらに、
前記シーケンス番号２ｍ＋１（１０、３０）の最下位シンボルと前記シーケンス番号２ｎ（２０、４０）の最下位シンボルとの間に少なくとも１つのパッディングシンボル（２１，２３）を付加し、前記ポインタの全てが奇数又は偶数シンボル位置を示し、前記シンボル位置がシンボル位置２k又は２kに近接するシンボル位置を示すようにするパッディングプロバイダ（１７０）を有し、
ｋ＝０又は自然数である
ことを特徴とする装置。
【請求項７】
前記メモリ（１４０）からバッファメモリ（４３０）へデータバス（３８０）により前記組み合わせシーケンス（７０）を送信するよう構成された出力ユニット（１５０）をさらに有することを特徴とする請求項６に記載の装置。
【請求項８】
前記シンボル編成器（１２０）は、Ｎ＝２である場合、
ｉ）前記組み合わせシーケンス（７０）の第１の部分（７Ａ）において、前記第１の読出し方向に第１のシーケンス（１０）の前記シンボルを編成し、
ｉｉ）前記組み合わせシーケンス（７０）の第１の部分に続く第２の部分（８Ａ）において、前記第２の読出し方向に第２のシーケンス（２０）の前記シンボルを編成するよう構成されることを特徴とする請求項６又は７に記載の装置。
【請求項９】
前記出力ユニット（１５０）は、
ｉ）前記メモリ（１４０）からバッファメモリ（４３０）へデータバス（３８０）により前記組み合わせシーケンス（７０）を送信し、
ｉｉ）前記メモリ（３４０）からディスプレイユニット（４００）におけるメモリ（２３０）へ前記データバス（３８０）により前記ポインタ（２１，２３）を送信するよう構成されることを特徴とする請求項７に記載の装置。
【請求項１０】
前記第２のシーケンス（２０）は前記第１のシーケンス（１０）より多くのシンボルを含み、
前記シンボル編成器（１２０）は、前記第１のシーケンス（１０）の前記シンボルと前記第２のシーケンス（２０）の前記シンボルとを、シンボルの前記組み合わせシーケンス（７０）へと合同編成するよう構成され、
前記組み合わせシーケンス（７０）において、
前記第１のシーケンス（１０）の前記シンボルは、前記組み合わせシーケンス（７０）の第１の部分（７Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の一方を占有し、
前記第２のシーケンス（２０）の前記シンボルの第１の部分は、前記組み合わせシーケンス（７０）の第１の部分（７Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の他方を占有し、
前記第２のシーケンス（２０）の前記シンボルの残りの第２の部分は、前記組み合わせシーケンス（７０）の残りの第２の部分（８Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の両方を占有し、
前記第１の部分（７Ｂ）におけるシンボルと前記残りの第２の部分（８Ｂ）における各奇数位置と各偶数位置との内の一方を占有するシンボルとは前記第１の読出し方向に読出し可能であり、
前記残りの第２の部分（８Ｂ）における各奇数位置と各偶数位置との内の他方を占有するシンボルは前記第２の読出し方向に読出し可能であることを特徴とする請求項８に記載の装置。
【請求項１１】
各々が各画素値を有する複数の画素（６）のタイル（１）を復号化する方法であって、前記方法は、
バッファメモリ（４３０）から、前記タイル（１）の各サブセットを構成する複数の画素（６）のＮ個のブロック（４，５）における複数の画素（６）の画素値の可変長符号化表現としてのシンボルのＮ個のシーケンス（１０，２０，３０，４０，５０，６０）を含むシンボルの組み合わせシーケンス（７０）を取り出す工程（Ｓ５０）と、
Ｎが奇数である場合には（Ｎ−１）／２個のポインタから、Ｎが偶数である場合にはＮ／２−１個のポインタからとられたポインタ（１１，１３）に基づいて、ｉ）前記取り出された組み合わせシーケンス（７０）における各定義されたシンボル位置から始まり第１の読出し方向に前記取り出された組み合わせシーケンス（７０）の各部を読み出すことにより前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｍ＋１（１０，３０，５０）を識別し、ｉｉ）前記取り出された組み合わせシーケンス（７０）における各定義されたシンボル位置から始まり前記第１の読出し方向とは逆の第２の読出し方向に前記取り出された組み合わせシーケンス（７０）の各部を読み出すことにより前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｎ（２０，４０）を識別し、ｉｉｉ）前記取り出された組み合わせシーケンス（７０）における最下位シンボルから始まり前記第２の読出し方向に前記取り出された組み合わせシーケンス（７０）のシーケンス番号Ｎを読み出すことにより前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号Ｎを識別する工程（Ｓ５１）と、
前記識別されたＮ個のシーケンス（１０，２０，３０，４０，５０，６０）を復号化して（Ｓ５２，Ｓ５３）、前記Ｎ個のブロック（４，５）における前記複数の画素（６）の前記画素値の復号化表現を取得する工程とを有し、
前記Ｎは３以上の整数である場合、
前記ｍは整数であり、かつ、ｍ∈［０，（Ｎ−２）／２］であり、
前記ｎは整数であり、かつ、ｎ∈［１，（Ｎ−１）／２］であり、
前記ポインタの各々は、前記取り出された組み合わせシーケンス（７０）におけるシーケンス番号２ｎ（２０，４０）の最上位シンボルのシンボル位置を規定し、
前記シーケンス番号２ｍ＋１（１０，３０）の最下位シンボルと前記シーケンス番号２ｎ（２０，４０）の最下位シンボルとの間には少なくとも１つのパッディングシンボル（２１，２３）を付加され、前記ポインタの全てが奇数又は偶数シンボル位置を示し、前記シンボル位置がシンボル位置２k又は２kに近接するシンボル位置を示すようにされており、
ｋ＝０又は自然数であることを特徴とする方法。
【請求項１２】
Ｎ＝２である場合、
識別された第２のシーケンス（２０）の復号化（Ｓ５３）と、識別された第１のシーケンス（１０）の復号化とは少なくとも部分的には並行に実行されることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記識別する工程（Ｓ５１）は、
前記取り出された組み合わせシーケンス（７０）の最上位シンボル位置から始まり前記第１の読出し方向に前記取り出された組み合わせシーケンス（７０）の第１の部分（７Ａ）を読み出すことにより前記第１のシーケンス（１０）を識別する工程（Ｓ６０）と、
前記取り出された組み合わせシーケンス（７０）における前記第１の部分に続く第２の部分（８Ａ）を、前記第２の部分（８Ａ）の最下位シンボル位置から始まり前記第２の読出し方向に読み出すことにより前記第２のシーケンス（２０）を識別する工程（Ｓ６１）とを有することを特徴とする請求項１２に記載の方法。
【請求項１４】
前記第２のシーケンス（２０）は前記第１のシーケンス（１０）より多くのシンボルを含み、
前記識別する工程（Ｓ５１）は、
前記第１の読出し方向に、前記取り出された組み合わせシーケンス（７０）の第１の部分（７Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の一方を読み出すことによって前記第１のシーケンス（１０）を識別する工程（Ｓ５１）と、
前記第１の読出し方向に、前記取り出された組み合わせシーケンス（７０）における各奇数シンボル位置と各偶数シンボル位置との内の他方を読み出すことによって、そして、前記第２の読出し方向に、前記取り出された組み合わせシーケンス（７０）の第２の部分（８Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の前記一方を読み出すことによって、前記第２のシーケンス（２０）を識別する工程（Ｓ５１）とを有することを特徴とする請求項１２に記載の方法。
【請求項１５】
各々が各画素値を有する複数の画素（６）のタイル（１）を復号化する装置（２００）であって、前記装置（２００）は、
バッファメモリ（４３０）から、前記タイル（１）の各サブセットを構成する複数の画素（６）のＮ個のブロック（４，５）における複数の画素（６）の画素値の可変長符号化表現としてのシンボルのＮ個のシーケンス（１０，２０，３０，４０，５０，６０）を含むシンボルの組み合わせシーケンス（７０）を取り出すよう構成されたシーケンス取り出し器（２１０）と、
Ｎが奇数である場合には（Ｎ−１）／２個のポインタから、Ｎが偶数である場合にはＮ／２−１個のポインタからとられたポインタ（１１，１３）に基づいて、ｉ）前記取り出された組み合わせシーケンス（７０）における各定義されたシンボル位置から始まり第１の読出し方向に前記取り出された組み合わせシーケンス（７０）の各部を読み出すことにより前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｍ＋１（１０，３０，５０）を識別し、ｉｉ）前記取り出された組み合わせシーケンス（７０）における各定義されたシンボル位置から始まり前記第１の読出し方向とは逆の第２の読出し方向に前記取り出された組み合わせシーケンス（７０）の各部を読み出すことにより前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号２ｎ（２０，４０）を識別し、ｉｉｉ）前記取り出された組み合わせシーケンス（７０）における最下位シンボルから始まり前記第２の読出し方向に前記取り出された組み合わせシーケンス（７０）のシーケンス番号Ｎを読み出すことにより前記Ｎ個のシーケンス（１０，２０，３０，４０，５０，６０）のシーケンス番号Ｎを識別するよう構成されたシーケンス識別器（２２０）と、
前記識別されたＮ個のシーケンス（１０，２０，３０，４０，５０，６０）を復号化して、前記Ｎ個のブロック（４，５）における前記複数の画素（６）の前記画素値の復号化表現を取得するよう構成された復号化器（２４０，２５０）とを有し、
前記Ｎは３以上の整数である場合、
前記ｍは整数であり、かつ、ｍ∈［０，（Ｎ−２）／２］であり、
前記ｎは整数であり、かつ、ｎ∈［１，（Ｎ−１）／２］であり、
前記ポインタの各々は、前記取り出された組み合わせシーケンス（７０）におけるシーケンス番号２ｎ（２０，４０）の最上位シンボルのシンボル位置を規定し、
前記シーケンス番号２ｍ＋１（１０，３０）の最下位シンボルと前記シーケンス番号２ｎ（２０，４０）の最下位シンボルとの間には少なくとも１つのパッディングシンボル（２１，２３）を付加され、前記ポインタの全てが奇数又は偶数シンボル位置を示し、前記シンボル位置がシンボル位置２k又は２kに近接するシンボル位置を示すようにされており、
ｋ＝０又は自然数である
ことを特徴とする装置。
【請求項１６】
Ｎ＝２である場合、
前記復号化器（２４０，２５０）は、
第１のシーケンス（１０）を復号化する第１の復号化器（２４０）と、
第２のシーケンス（２０）を復号化する第２の復号化器（２５０）とを含み、
前記第２の復号化器（２５０）は、前記第１の復号化器（２４０）が前記第１のシーケンス（１０）を復号化するのと少なくとも部分的には並行に前記第２のシーケンス（２０）を復号化するよう構成されたことを特徴とする請求項１５に記載の装置。
【請求項１７】
前記シーケンス識別器（２２０）は、
ｉ）前記取り出された組み合わせシーケンス（７０）の最上位シンボル位置から始まり前記第１の読出し方向に前記取り出された組み合わせシーケンス（７０）の第１の部分（７Ａ）を読み出すことにより前記第１のシーケンス（１０）を識別し、
ｉｉ）前記取り出された組み合わせシーケンス（７０）における前記第１の部分に続く第２の部分（８Ａ）を、前記第２の部分（８Ａ）の最下位シンボル位置から始まり前記第２の読出し方向に読み出すことにより前記第２のシーケンス（２０）を識別するよう構成されたことを特徴とする請求項１６に記載の装置。
【請求項１８】
前記第２のシーケンス（２０）は前記第１のシーケンス（１０）より多くのシンボルを含み、
前記シーケンス識別器（２２０）は、
ｉ）  前記第１の読出し方向に、前記取り出された組み合わせシーケンス（７０）の第１の部分（７Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の一方を読み出すことによって前記第１のシーケンス（１０）を識別し、
ｉｉ）前記第１の読出し方向に、前記取り出された組み合わせシーケンス（７０）における各奇数シンボル位置と各偶数シンボル位置との内の他方を読み出すことによって、そして、前記第２の読出し方向に、前記取り出された組み合わせシーケンス（７０）の第２の部分（８Ｂ）における各奇数シンボル位置と各偶数シンボル位置との内の前記一方を読み出すことによって、前記第２のシーケンス（２０）を識別するよう構成されたことを特徴とする請求項１６に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に画像処理に関し、特にタイルの符号化及び復号化に関する。
【背景技術】
【０００２】
コンピュータグラフィックスシステムにおいて帯域幅を消費しているタスクのうちの１つは、バッファ、特にカラーバッファの更新である。カラーバッファは、最終的に表示されるデータ、すなわち出力画素を含む。従来のアーキテクチャにおいて、カラーバッファは三角形毎に更新される。最初に、第１の三角形がラスタ化され、カラーバッファの対応する画素が更新される。次に、第２の三角形がラスタ化され、カラーバッファにおけるその画素に書き込む。それらの画素は、場合によっては第１の三角形の画素と重なり合っている。これは、カラーバッファにおける各画素が複数回書き込み可能であることを意味する。一般的な適応例では、カラーバッファにおける全ての画素を平均でおそらく３回〜１０回上書きする。これは、この技術分野内で３回〜１０回のオーバードローを有するものとして知られている。これは、カラーバッファに対する書き込み帯域幅が、各画素が１回しか書き込まれなかった場合の３〜１０倍になることを意味する。
【０００３】
カラーバッファの帯域幅に対する要求を軽減する１つの方法は、タイルアーキテクチャとして知られているものを使用する方法である。三角形毎にシーンをラスタ化するのではなく、カラーバッファは重なり合わないタイルに分割される。その後、シーンはタイル毎にレンダリングされる。第１のタイルに対しては、第１のタイルと重なり合っている三角形のみがラスタ化のために使用される。タイルは、タイル全体がグラフィックス処理ユニット（ＧＰＵ）上のオンチップで適合できるように十分に小さくされる。従って、タイルの三角形のレンダリング中に外部メモリはカラーバッファにアクセスする必要はない。タイルにおける全ての三角形がラスタ化されると、タイルはカラーバッファメモリに送出され、次のタイルが処理される。尚、タイルアーキテクチャにおいて、カラーバッファにおける各画素は外部メモリに１回しか書き込まれない。これは、タイルアーキテクチャが多くの場合、カラーバッファに対する書き込み帯域幅１／３〜１／１０に低減できることを意味する。
【０００４】
カラーバッファ帯域幅を低減する別の技術をバッファ圧縮と呼ぶ。これは、バッファデータのブロックが圧縮形式でメモリに格納されることを意味する。シーンが依然として三角形毎に処理されるが、画素のブロックをカラーバッファメモリに送出する前に画素は圧縮される。ＧＰＵに格納又はキャッシュされたサイズビットと呼ばれる少数のビットは、データの圧縮具合、例えば元のビット長の２５％、５０％又は７５％に対応するビット長まで圧縮されたかあるいは全く圧縮されなかったかを追跡するために使用される。後続の三角形を画素の同一のブロックに書き込みたい場合、読み出されるべきデータ量を知るためにサイズビットが使用される。ブロックは伸張され、新しい三角形はブロックにおける画素のうちのいくつかを上書きし、その後ブロックは再度圧縮され格納される。非特許文献１と非特許文献２はそれぞれ、カラーバッファ圧縮及びデプスバッファ圧縮の適切な概要を与えている。
【０００５】
タイルアーキテクチャの限界は、１回しか行われない各画素の書き込みが依然として非常にコストがかかることである。更にディスプレイコントローラは、各画素を読出してディスプレイに出力しなければならなくなる。これは、各画素が非圧縮形式で少なくとも１回カラーバッファから読み出され且つカラーバッファに書き込まれなければならず、コストがかかることを意味する。
【０００６】
カラーバッファ圧縮の解決策に関する問題は、５０％の圧縮率を達成できる場合でも、それは依然として帯域幅が大きすぎることである。例えば６回のオーバドローにより、全ての画素は依然として平均６回書き込まれる。５０％の圧縮率は有効な帯域幅を画素数の３倍に低下させるが、それでは依然としてタイルアーキテクチャに対する帯域幅より大きい。
【０００７】
従って、コンピュータグラフィックスシステムと組み合わせて画素値バッファを効率的に処理できる技術が必要である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】ハセグレン（Hasselgren）及びアケニネ−モレル（Akenine-Moller）、効率的な深さバッファの圧縮（Efficient Depth Buffer Compression）、グラフィックスハードウェア（In Graphics Hardware）、２００６年、１０３〜１１０ページ
【非特許文献２】正確で誤り限界のある近似的色バッファ圧縮と復元（Exact and Error-bounded Approximate Color Buffer Compression and Decompression）、ラスムッソン（Rasmusson）、ハセグレン（Hasselgren）及びアケニネ−モレル（Akenine-Moller）、２００７年、グラフィックスハードウェア（In Graphics Hardware）、４１〜４８ページ
【発明の概要】
【０００９】
実施形態の一般的な目的は、グラフィックスシステムと組み合わせて画素値バッファを効率的に処理する技術を提供することである。
【００１０】
この目的及び他の目的は、本明細書において開示されるような実施形態により達成される。
【００１１】
実施形態の一態様は、各々がそれぞれの画素値を有する画素のタイルを符号化する方法を規定する。この方法は、少なくとも複数の画素の第１のブロックをシンボルの第１のシーケンスに可変長符号化し、複数の画素の第２のブロックをシンボルの第２のシーケンスに可変長符号化する工程を備える。第１のブロックと第２のブロックとは、タイルの異なるサブセットを構成する。第１のシーケンスは、第１のブロックにおける複数の画素の画素値の符号化表現であり、第２のシーケンスは、第２のブロックにおける画素値の対応する符号化表現である。
【００１２】
第１のシーケンスと第２のシーケンスのシンボルは、シンボルの組み合わせシーケンスに合同編成される。第１のシーケンスのシンボルは、組み合わせシーケンスにおいて第１の読出し方向に読出し可能である。組み合わせシーケンスは、第２のシーケンスのシンボルの少なくとも一部が第１の読出し方向とは逆の第２の読出し方向に読出し可能であるように更に生成される。その後、生成された組み合わせシーケンスはメモリに格納される。
【００１３】
タイルのブロックの符号化は、タイルを画素値バッファに書き込む際に帯域幅に対する要求を軽減する。組み合わせシーケンスのシンボルの合同編成により、少なくとも第１のシーケンスと第２のシーケンスのそれぞれのシーケンスに属するシンボルの識別が更に容易になる。これは、たとえシーケンスが可変長符号化から取得されていても可能であり、場合によっては結果としてシーケンスの種々のシンボル長が得られる。これは、組み合わせシーケンスからの第１のシーケンスと第２のシーケンスの復号化を同時に実行することにより、あらゆる復号化遅延時間を短縮できることを意味する。
【００１４】
実施形態の別の態様は、タイルを符号化する装置に関する。その装置は、少なくとも第１のブロックと第２のブロックをシンボルの第１のシーケンスと第２のシーケンスに可変長符号化するように構成された可変長符号器を備える。シンボル編成器は、第１のシーケンスのシンボルが組み合わせシーケンスから第１の読出し方向に読出し可能であり、そして第２のシーケンスのシンボルの少なくとも一部が第１の読出し方向とは逆の第２の読出し方向に読出し可能であるように、第１のシーケンスと第２のシーケンスのシンボルを組み合わせシーケンスに合同編成するように構成される。その装置のメモリコントローラは、生成された組み合わせシーケンスをメモリに格納するように構成される。
【００１５】
実施形態の更なる態様は、タイルを復号化する方法を規定する。その方法は、シンボルの組み合わせシーケンスをバッファメモリから取り出す工程を備える。シンボルの第１のシーケンスは、組み合わせシーケンスにおける第１の規定のシンボル位置から開始して第１の読出し方向に取り出された組み合わせシーケンスの第１の部分を読出すことにより識別される。シンボルの第２のシーケンスは、組み合わせシーケンスにおける第２の規定のシンボル位置から開始して第１の読出し方向とは逆の第２の読出し方向に取り出された組み合わせシーケンスの第２の部分を読み出すことにより同様に識別される。識別された第１のシーケンスを復号化して、第１のブロックにおける複数の画素の画素値の復号化表現を取得する。第２のシーケンスを復号化して、タイルの第２のブロックにおける画素値の復号化表現を取得する。
【００１６】
実施形態の更に別の態様は、タイルを復号化する装置に関する。その装置は、バッファメモリから組み合わせシーケンスを取り出するように構成されたシーケンス取り出し器を備える。シーケンス識別器は、第１の読出し方向に取り出された組み合わせシーケンスの第１の部分を読み出すことにより第１のシーケンスを識別するように実現される。シーケンス識別器は、組み合わせシーケンスから第２のシーケンスを識別するために第１の読出し方向とは逆の第２の読出し方向に組み合わせシーケンスの第２の部分を更に読み出す。第１の復号器は、第１のシーケンスを復号化してタイルの第１のブロックにおける画素値の復号化表現を取得し、第２の復号器は、第２のシーケンスを復号化して第２のブロックにおける画素値の復号化表現を取得する。
【００１７】
本発明は、添付図面と共に以下の説明を参照することにより、本発明の更なる目的及び利点と共に最善の理解が得られるだろう。
【図面の簡単な説明】
【００１８】
【図１】一実施形態に係るタイルを符号化する方法を示すフローチャートである。
【図２】一実施形態に係るタイル及びタイルをより小さな単位へ分割することを概略的に示す図である。
【図３】図１の方法の更なるオプションのステップを示すフローチャートである。
【図４】図１の合同編成ステップの一実施形態を示すフローチャートである。
【図５】一実施形態に係るシンボルの組み合わせシーケンスを概略的に示す図である。
【図６】図１の方法の更なるオプションのステップを示すフローチャートである。
【図７Ａ】、
【図７Ｂ】、
【図７Ｃ】、
【図７Ｄ】種々の実施形態に係るシンボルの組み合わせシーケンスを概略的に示す図である。
【図８】図１の方法の更なるオプションのステップを示すフローチャートである。
【図９】一実施形態に係るパディングシンボルを含むシンボルの組み合わせシーケンスを示す概略図である。
【図１０】一実施形態に係るシンボルの組み合わせシーケンスを概略的に示す図である。
【図１１】一実施形態に係るタイルを復号化する方法を示すフローチャートである。
【図１２】図１１のシーケンス識別ステップの一実施形態を示すフローチャートである。
【図１３】図１１の方法の更なるオプションのステップを示すフローチャートである。
【図１４】一実施形態に係る画像を表示するシステムを示す概略図である。
【図１５】一実施形態に係るタイルを符号化する装置を示す概略ブロック図である。
【図１６】一実施形態に係るタイルを復号化する装置を示す概略ブロック図である。
【発明を実施するための形態】
【００１９】
図中、同一の図中符号は、同様の要素又は対応する要素に対して使用される。
【００２０】
実施形態は、一般に画像処理に関し、特に画素値バッファの少なくとも一部を構成する画素のタイルの符号化及び復号化に関する。それにより実施形態は、画素値バッファをバッファメモリに書き込んで更新する際に書き込み帯域幅を更に低減するために、バッファ圧縮に対する従来技術をタイルアーキテクチャと組み合わせる。タイルの符号化及び復号化は、符号化タイルの種々の部分を同時に復号化できるようにすることで復号化時間の短縮を可能にする特定の方法で更に実行される。
【００２１】
実施形態によると、画素のタイルは、画素値バッファの少なくとも一部を表す。従って、画素値バッファは、１つ又は一般に複数、すなわち少なくとも２つのこの技術分野においてタイルで示される重なり合わない部分に分割される。特に非常に小さな画素値バッファの場合、単一のタイルが画素値バッファ全体を占有できる。しかし、最も実際的な実施例において、画素値バッファは、別個の重なり合わないタイルに分割されるものとして考えられる。
【００２２】
しかしながら、タイル全体を符号化することは、一般に、長時間の符号化及び復号化、並びに符号化効率の低下により実現不可能である。従って、タイルを複数の画素からなる多数のブロックに分割したいという要望があり、その場合、画素数に関するそのようなブロックのサイズは、符号化及び復号化の観点から効率的に処理されるように選択される。
【００２３】
しかしながら、符号化及び復号化の効率に対してタイルを多数のより小さなブロックに分割することにより、データ転送に関する問題が発生する。結果として得られる符号化表現のシンボルサイズ又はシンボル長は、一般に、データバスを介した効率的な転送にはあまり適応しない。従って、グラフィックスシステムのデータバスは、一般に、符号化及び復号化の観点から所望されるものより長いシンボル長に対して効率的なバースト転送を実現するように設計される。
【００２４】
実施形態において、多数のブロックを符号化することで取得されたシンボルのシーケンスを、データバスを介して効率的に転送可能な組み合わせシーケンスに合同編成することによりこれらの相反する要望を解決するが、シンボルの個別のシーケンスは、符号化及び復号化の要件に非常に適応するサイズを有する。
【００２５】
実施形態に従えば、組み合わせシーケンスへのシンボルのシーケンスの合同編成は、ブロックを符号化するために可変長符号化方式が採用される場合でもシンボルの個別のシーケンスを同時に復号化できるようにする方法で実行される。
【００２６】
可変長符号化は、シンボルのシーケンスが、単一の固定のシンボル長を有さないが種々のシンボル長を採用できることを示唆する。シンボルのシーケンスが組み合わせシーケンスにおいて開始及び終了する場所について復号器が全く知らないため、組み合わせシーケンスにおいて互いに隣接するシンボルのシーケンスを編成することにより、復号化側における特定のブロックのシンボルのシーケンスへのランダムアクセスを防止する。従って、組み合わせシーケンスにおいてシンボルのシーケンス毎にそれぞれの開始シンボル及び終了シンボルを識別する唯一の手段は、最上位シンボルから開始して最下位シンボルに向けて継続して組み合わせシーケンスを構文解析して復号化することである。しかし、そのような手法では、シンボルの個別のシーケンスを同時に復号化できず、且つ単一の復号器のみが組み合わせシーケンス毎に動作できることを示唆している。
【００２７】
実施形態は、多数の復号器が組み合わせシーケンスに対して同時に動作できるようにすることで単一の連続した復号化ラインと比較して復号化遅延時間を大幅に短縮するように、組み合わせシーケンスにおけるシンボルのシーケンスの特定の合同編成によりこの問題を解決する。
【００２８】
実施形態によると、各画素はそれぞれの画素値を有する。種々のそのような画素値は、特定の適応例に依存して、この技術分野において使用される。そのような画素値の一般的な例は、色値であり、より好ましくは複数の構成要素から成る色値である。後者の場合、画素の色は多数の色成分から構成される。そのような色の一般的な例は、３つの色成分を有する赤色、緑色、青色（ＲＧＢ）である。ＹＵＶ、ＹＣｏＣｇ又はＹＣｒＣｂ等の他の複数の構成要素から成る色は、この技術分野においても知られており、実施形態に従って使用可能である。
【００２９】
実施形態に従って使用可能な画素値の別の例は、奥行き値又はいわゆるＺ値である。この特徴は、特定の画素に対する眼までの奥行き又は距離を表し、レンダリング中に実際にどの画素が表示されるのかを制御する。
【００３０】
タイルは、カラーバッファ又はデプスバッファの少なくとも一部を構成できる。
【００３１】
カラーバッファ及びデプスバッファに加えて実施形態を適用できる画素値バッファの別の例は、いわゆるステンシルバッファである。ステンシルバッファは、レンダリングの領域を制限するために使用可能であり、この技術分野においてステンシリングとして示される。ステンシルバッファは、レンダリングパイプラインにおいてデプスバッファと組み合わせても使用可能である。例えば、ステンシル値は、デプステストに不合格又は合格する全ての画素に対して自動的に更新、すなわち増加又は減少される。ステンシルバッファは、シャドウ、複雑なプリミティブ間の交点のオンラインでの描画又は強調表示等の種々の効果の実現に応用される。そのような場合、タイルは、ステンシルバッファの少なくとも一部を構成でき、画素値は、ステンシルバッファのステンシル値である。
【００３２】
実際には、画素値は、画素毎に割り当てられることが望ましいあらゆるプロパティであり、複数の画素は複数のタイルにグループ化される。グラフィックスシステム内でプログラマブルシェーダーを使用することにより、種々の画素値バッファの作成と使用を可能にしており、実施形態は、そのような画素値バッファにも適用可能である。例えば、遅延レンダリングにおいて、法線は、各画素が法線（Ｘ、Ｙ、Ｚ座標又は単位法線が採用される場合に２つの座標しか必要ない）を表すようにバッファに書き込まれる。また、そのような適応例はその実施形態では利点がある。
【００３３】
符号化
図１は、画素のタイルを符号化する方法の一実施形態を示すフローチャートであり、各画素はそれぞれの画素値を有する。この方法はステップＳ１において開始し、少なくとも複数の画素の第１のブロックと複数の画素の第２のブロックは可変長符号化される。第１のブロックはタイルの第１のサブセットを構成し、第２のブロックは、そのタイルの第２の異なるサブセット、すなわち第２の重なり合わないサブセットを同様に構成する。ステップＳ１の可変長符号化は、第１のブロックにおける複数の画素の画素値の符号化表現としてシンボルの第１のシーケンスを生成する。ステップＳ１は、第２のブロックにおける複数の画素の画素値の符号化表現としてシンボルの第２のシーケンスを更に生成する。シンボルの第１のシーケンスと第２のシーケンスは、データ符号化内で従来より採用されているシンボルアルファベットのうちのいずれかに従うものであってよい。例えば、シンボルのアルファベットは二進のアルファベットであってよい。そのような場合、シンボルは０bin又は１binであってよい。使用可能なシンボルの他のアルファベットは、１６進シンボル、すなわち０−９hex及びＡ−Ｆhex、１０進シンボル、すなわち０−９decを含む。好適な適応例において、ビットのシーケンスを含む二進アルファベットは、シンボルアルファベットの例示的な一実施形態として使用される。本明細書において使用されるようなシンボルは、ブロックの終了等の特定の事象を示すために採用されることもあるＶＬＣシンボル、すなわち可変長符号化シンボルを表さない。
【００３４】
可変長符号化は、従来カラーバッファデータ又はデプスバッファデータ、あるいは他の画素値バッファを符号化するために採用されたあらゆる可変長符号化方式に従って実行可能である。しかし、これらの可変長符号化方式の従来の使用法と比較して重要な差異は、ここでそれらが完全な画素値バッファではなくタイルのブロックに対して動作することである。従って、実施形態は、タイルアーキテクチャとバッファの符号化又は圧縮との組合せに基づいている。実施形態に従って採用可能な適切な可変長符号化方式の例は、非特許文献１、非特許文献２、国際公開第２００９／０９２４５５号、国際公開第２００９／０９２４５４号及び国際公開第２００９／０９３９４７号において開示されている、可変長符号化方式に対するそれらの教示は、ここで参照により本明細書に組み込まれる。しかし、実施形態は、いずれの特定の可変長符号化方式にも限定されず、画素値を有する画素のブロックをシンボルのシーケンスに符号化できるあらゆる既知のそのような可変長符号化方式と組み合わせて適用及び使用可能である。
【００３５】
図２はタイル１の概略図であり、タイル１を画素６のより小さな単位に分割できる方法の一例を示す。タイル１は、非限定的であり、例示的な例において、３２画素×３２画素のサイズを有する。そのような場合、タイル１は、例えば３２画素×８画素の４つの垂直スライス２に分割可能である。オプションの手法において、スライス２は、結果として例えば１６画素×８画素の２つのチャンク３に分割される。チャンク３は、平均でデータバスを介した効率的なバースト転送を可能にするシンボル長を有するチャンク３の符号化表現としてシンボルのシーケンスを生成する画素６数に関するサイズを有することが好ましい。しかし、チャンク３における画素６の符号化表現のシンボル長が効率的なバースト転送に適応可能であるが、結果として得られる相対的に長いシンボル長は、復号器遅延時間の観点から最適ではない。実施形態によると、従って、チャンク３は、画素６の複数のブロック４、５に分割されるものとして考えられる。一例において、そのようなブロック４、５は、４画素×４画素を含むことができ、結果としてチャンク３毎に８個のブロック４、５が得られる。
【００３６】
画素６毎に１クロックサイクルの割合で符号化を実行できる場合、スライス２の符号化及び復号化は、この例において結果的に３２×８＝２５６クロックサイクルの遅延時間になる。しかし、復号化のために最大６４クロックサイクルしか使用可能でないことは稀である。従って、効率的な復号化を達成するという点で、スライス２は大きすぎる可能性がある。一方、４×４＝１６画素のブロック４、５は、この例において復号化のために１６クロックサイクルしか必要ないだろう。しかし、ブロック４、５の符号化表現のシンボル長は、一般に、効率的なバースト転送に対しては小さすぎる。実際に、各画素が色成分毎に８ビットを有するＲＧＢ色値と関連付けられる場合、ブロック４、５の圧縮されていないシーケンスでさえ結果として４×４×３×８＝３８４シンボル又はビットとなる。しかし、これは、一般に４サイクルで５１２ビットを転送できてもよい効率的なバーストサイズに対しては既に小さすぎる。可変長符号化が更に結果として例えば１／６の圧縮となりうる場合、結果として得られるビット長はたった６４ビットである。これは、効率的なバースト転送に対してはあまりにも小さすぎる。
【００３７】
しかし、例えば８個のブロック４、５のチャンク３は、非圧縮の場合には結果として８×３８４＝３０７２ビットの総ビット長となる。圧縮が平均で１／６となる場合、総ビット長は、本発明の例においてバースト転送に対して最適化される５１２ビットとなる。従って、タイル１は、データバスを介して転送される場合に少なくとも２つのブロック４、５のチャンク３において個々に可変長符号化されるが共に処理される複数のより小さなブロック４、５に分割されるという利点がある。
【００３８】
図１の方法の次のステップＳ２は、可変長符号化ステップＳ１から取得された第１のシーケンスのシンボルと第２のシーケンスのシンボルを合同編成にする。これらのシンボルはそれぞれ、第１のシーケンスと第２のシーケンスに属するシンボルの読出しを容易にするために、特定の方法でシンボルの組み合わせシーケンスに組み合わされる。従って、第１のシーケンスのシンボルは、組み合わせシーケンスから第１の読出し方向、すなわちデフォルトの読出し方向に読出し可能である。しかし、第２のシーケンスのシンボルの少なくとも一部は、組み合わせシーケンスから第１の読出し方向とは逆の第２の読出し方向に読出し可能である。この特定のシンボルの合同編成により、第１のシーケンス又は第２のシーケンスに属するそれぞれのシンボルを同時に読出せるようになるため、第１のシーケンスと第２のシーケンスを同時に復号化できるようになる。可変長符号化の結果第１のシーケンス及び第２のシーケンスが得られる場合でも、同時に読出し、復号化できる。従って、第１のシーケンスと第２のシーケンスのそれぞれの長さを事前に認識していなくても、同時に読出し、復号化できる。
【００３９】
次のステップＳ３は、組み合わせシーケンスをメモリに格納する。一般にメモリは、いわゆるオンチップメモリであり、特にグラフィカル処理ユニットのオンチップメモリである。そのような場合、ステップＳ１〜Ｓ３の方法は、オンチップメモリに格納されたデータに対して動作でき、シンボルの組み合わせシーケンスを生成するために、外部メモリへの時間のかかる外部メモリへのフェッチは必要ない。
【００４０】
ステップＳ１〜Ｓ３の方法は、タイルの前のチャンクのブロック等の多数のブロックに対して共に実行される。多数のブロックの次のチャンクが処理されると、ステップＳ１〜Ｓ３の動作は、そのチャンクの多数のブロックに対してもう１度実行される。特定の実施例に依存して、少なくとも部分的に同時に少なくとも２つのチャンクを処理することも可能である。どちらの場合でも、ステップＳ１〜Ｓ３のループは、全タイルを符号化するために同時に又は順次十分な回数実行されることが好ましい。タイルのサイズに依存して、これは、タイルの全てのブロックが符号化されるまでステップＳ１〜Ｓ３のループが１回又は一般には複数回実行可能であることを示す。
【００４１】
図３は、図１の方法の更なるステップを示すフローチャートである。この方法は、図１のステップＳ３から続く。次のステップＳ１０は、グラフィカル処理ユニットのメモリからディスプレイユニットのバッファメモリあるいはそれに接続されたバッファメモリに組み合わせシーケンスを送信する。組み合わせシーケンスの送信は、多数のブロックから取得されたシンボルのシーケンスを組み合わせることによりバースト転送が効率的な方法で実行可能である。シンボルの１つのそのようなシーケンスは、一般に、効率的なバースト転送をするにはサイズが小さすぎる。
【００４２】
実施形態のタイル手法は、バッファメモリにおける各画素を１回しか書き込む必要がないために帯域幅消費量が減少することを示す。また、符号化及びそれにより圧縮された画素値データをバッファメモリに転送できるため、画素のブロックの可変長符号化により、この帯域幅消費量は更に減少する。
【００４３】
次に、種々の実現例の実施形態を更に詳細に説明する。
【００４４】
図４は、図１の合同編成ステップの特定の一実施形態を示すフローチャートである。この方法は、図１のステップＳ１から続く。次のステップＳ２０は、組み合わせシーケンスの第１の部分において第１の読出し方向に第１のシーケンスのシンボルを編成する。ステップＳ２１は、組み合わせシーケンスにおける第２のシーケンスのシンボルを編成する。これらのシンボルは、組み合わせシーケンスの後続部分である第２の部分において第１の読出し方向とは逆の第２の読出し方向に編成される。
【００４５】
図５は、本実施形態を更に詳細に示す。組み合わせシーケンス７０は、第１のシーケンス１０のシンボルを含む第１の部分７Ａと、後続の第２の部分８Ａとを含む。これは、組み合わせシーケンス７０の最上位シンボルが、図５の左側に対して見出され、一般に第１のシーケンス１０の最上位シンボルと一致することを意味する。第２の部分８Ａは、第１の読出し方向に従って第１の部分７Ａの後に続く。第１のシーケンス１０とは明らかに対照的に、第２のシーケンス２０におけるシンボルは、第１の読出し方向とは逆の第２の読出し方向に編成される。図５において、それぞれの読出し方向を矢印で示す。第２のシーケンス２０に対して第１の読出し方向とは逆の第２の読出し方向を使用することは、第２のシーケンス２０の最上位シンボルが組み合わせシーケンス７０の最下位シンボルになることを意味する。
【００４６】
図５に示されたように第１のシーケンス１０と第２のシーケンス２０におけるシンボルを逆の読出し方向に編成することにより、双方のシーケンス１０、２０を同時に読出し、復号化できるようになる。従って、第１のシーケンス１０のシンボルは、組み合わせシーケンス７０の最上位シンボルから開始し、組み合わせシーケンス７０の最下位シンボルに向けて読出しを続けるが、第１のシーケンス１０の最終部に到達すると読出しを停止するようにして読み出される。あるいは、第２のシーケンス２０におけるシンボルは、本実施形態において、組み合わせシーケンス７０の最下位シンボルから開始し、組み合わせシーケンス７０の最上位シンボルに向けて読出しを続け、第２のシーケンス２０の最終部において読出しを停止するようにして読み出される。従って、組み合わせシーケンス７０における２つのシーケンス１０、２０に対するそれぞれの開始位置を見つけるために、第１のシーケンス１０と第２のシーケンス２０それぞれのシンボル長の情報は必要ない。
【００４７】
組み合わせシーケンスにおける２つの逆の読出し方向を利用するこのような概念は、３つ以上のブロックが可変長符号化され且つ結果として得られるシンボルのシーケンスが組み合わせシーケンスに合同編成される場合にも適用可能である。
【００４８】
そのような場合、タイルのそれぞれのサブセット又は一部分を構成する画素のＮ個のブロックは、可変長符号化されてＮ個のブロックにおける画素値の符号化表現としてシンボルのＮ個のシーケンスを形成する。ここで、パラメータＮは３以上の整数である。Ｎ個のシーケンスのシンボルは組み合わせシーケンスに合同編成される。
【００４９】
一実施形態において、Ｎ個のシーケンスのうちの最初のシーケンスにおけるシンボルが第１の読出し方向に読出し可能であり、且つＮ個のシーケンスのうちの最後のシーケンス、すなわちシーケンス番号Ｎのシンボルが第１の読出し方向とは逆の第２の読出し方向に読出し可能であるように、シンボルは組み合わせシーケンスに合同編成される。残りのシーケンスの全ての偶数シーケンスが第１の読出し方向とは逆の第２の読出し方向に読出し可能であるのに対し、Ｎ個のシーケンスの残りのシーケンスの全ての奇数シーケンスのシンボルが第１の読出し方向に読出し可能であるように、残りの（Ｎ−２）個のシーケンスのシンボルは組み合わせシーケンスに編成される。
【００５０】
従って、この実施形態において、（Ｎ−１）個の最初のシーケンスのシンボルは、互いに順番に且つ交互の読出し方向に編成される。最後のシーケンスのシンボルは、第１の方向とは逆の第２の方向に常に読出し可能であることが好ましい。そのような例において、組み合わせシーケンスが奇数のシーケンスを含む場合、最後の２つのシーケンスが第１の方向とは逆の第２の方向に編成されたシンボルを有するのに対し、Ｎが偶数の場合、読出し方向は、組み合わせシーケンスにおける全てのシーケンスに対して交互になる。
【００５１】
シーケンス番号Ｎ、すなわち最後のシーケンスのシンボルが第１の読出し方向とは逆の第２の読出し方向に読出し可能であるように、Ｎ個のシーケンスのシンボルを組み合わせシーケンスに合同編成するものとして上述の実施形態を規定できる。Ｎ個のシーケンスのシーケンス番号２ｍ＋１のシンボルは、第１の読出し方向に読出し可能である。Ｎ個のシーケンスのシーケンス番号２ｎのシンボルは、第１の読出し方向とは逆の第２の読出し方向に読出し可能である。
【００５２】
パラメータｍは整数であり、かつ、ｍ∈［０，（Ｎ−２）／２］、即ち、ｍ＝０，……，［（Ｎ−２）／２］であり、［…］は床関数を示す。本明細書において、整数は、自然数の負数と共にゼロを含む自然数に対応する。しかし、ｍは閉区間［０，（Ｎ−２）／２］から選択された整数であるため、負数にはなり得ない。例えば、Ｎ＝３はｍ＝０を与え、Ｎ＝４はｍ＝０、１を与え、Ｎ＝５はｍ＝０、１を与え、Ｎ＝６はｍ＝０、１、２を与える等である。パラメータｎは整数であり、かつ、ｎ∈［１，（Ｎ−１）／２］である。従って、Ｎ＝３はｎ＝１を与え、Ｎ＝４はｎ＝１を与え、Ｎ＝５はｎ＝１、２を与え、Ｎ＝６はｎ＝１、２を与える等である。
【００５３】
シーケンスが正しい順序で提供されるように、Ｎ個のシーケンスにおけるシンボルは組み合わせシーケンスに合同編成されることが好ましい。従って、シーケンス番号ｉは、組み合わせシーケンスにおいてシーケンス番号ｉ＋１に先行する。ここで、ｉ＝１，２，……，Ｎ−１である。
【００５４】
先に提示された実施形態において、組み合わせシーケンスにおける最初のシーケンス及び最後のシーケンスのシンボルは、組み合わせシーケンスから同時に読出し、復号化可能である。しかし、最初のシーケンスと最後のシーケンスのそれぞれの最終部、すなわち他のシーケンスとの組み合わせシーケンスにおける開始位置は、何らかの追加情報を提供しなければ認識されない。
【００５５】
一実施形態において、そのような追加情報は提供されない。そのような場合、第１のラウンドにおいて、最初のシーケンスと最後のシーケンスは読出し、復号化可能である。復号化には、更なるシーケンスの読出しと復号化のために少なくとも１つの更なるラウンドが必要である。しかし、そのような場合、第２のシーケンスは第１のシーケンスと同一の第１の読出し方向に配置され、最後から２番目のシーケンスは、最後のシーケンスとして第１の読出し方向とは逆の第２の読出し方向に提供される。それに対応して、組み合わせシーケンスがシンボルの３つのシーケンスを含む場合、最初の３つが第１の読出し方向に配置されることが好ましいのに対し、最後の３つは第１の読出し方向とは逆の第２の読出し方向に配置されることが好ましい。そのような場合、３つの復号化ラウンドは、組み合わせシーケンスにおける全てのシーケンスを復号化するために必要である。
【００５６】
別の一実施形態において、少なくとも１つのポインタは、追加情報として提供され、第１のラウンド中に組み合わせシーケンスにおける中間シーケンスの読出しと復号化も容易にする。本実施形態を図６に更に詳細に示す。この方法は、図１のステップＳ２から継続する。次のステップＳ３０は、組み合わせシーケンスにおける中間シーケンスの最上位シンボルを規定する少なくとも１つのポインタを判定する。ステップＳ３０は、各々がそれぞれの中間シーケンスの最上位シンボルを規定する１つ以上のそのようなポインタを判定する。ステップＳ３０で判定されたポインタの実際の数は、パラメータＮ、すなわち組み合わせシーケンスにおけるシーケンスの総数に依存する。Ｎが奇数の場合、ステップＳ３０は、（Ｎ−１）／２個のポインタ、即ち、例えばＮ＝３の場合に１個のポインタ、Ｎ＝５の場合に２個のポインタを判定することを含むことが好ましい。同様に、Ｎが偶数の場合、ステップＳ３０は、Ｎ／２−１個のポインタ、即ち、例えばＮ＝４の場合に１個のポインタ、Ｎ＝６の場合に２個のポインタを判定することが好ましい。（Ｎ−１）／２個又はＮ／２−１個のポインタのポインタ番号ｋは、組み合わせシーケンスにおけるシーケンス番号２ｋの最上位シンボル位置を規定する。例えば、これは、第１のポインタが最上位シンボルを識別することで組み合わせシーケンスにおけるシーケンス番号２の開始を識別し、且つ第２のポインタがシーケンス番号４の最上位シンボルを識別することなどを意味する。パラメータｋは整数であり、Ｎが奇数の場合にはｋ∈［１，（Ｎ−１）／２］であり、Ｎが偶数の場合にはｋ∈［１，Ｎ／２−１］である。
【００５７】
図７Ａ〜図７Ｄは、Ｎ＝３〜６である組み合わせシーケンス７０を示す。図７Ａにおいて、組み合わせシーケンス７０は、シンボルの３つのシーケンス１０、２０、３０を含む。第１のシーケンス１０のシンボルが第１の読出し方向に読出し可能であるのに対し、第２のシーケンス２０と最後のシーケンス３０のシンボルは、第１の読出し方向とは逆の第２の読出し方向に読出し可能である。ポインタ１１は、組み合わせシーケンス７０に対して決定され、第２のシーケンス２０の最上位シンボル位置を規定する。
【００５８】
図７Ｂは、組み合わせシーケンス７０における４つのシーケンス１０、２０、３０、４０を含む例を示す。第１のシーケンス１０と第３のシーケンス３０が第１の読出し方向にシンボルを有するのに対し、第２のシーケンス２０と最後のシーケンス４０におけるシンボルは第１の読出し方向とは逆の第２の読出し方向に読出し可能である。ポインタ１１により、第２のシーケンス２０の最上位シンボル位置を識別できるようになる。更にポインタ１１により、第３のシーケンス３０の最上位シンボル位置を識別できるようになる。従って、第２のシーケンス２０と第３のシーケンス３０が逆の方向に読出し可能であるため、第３のシーケンス３０の最上位シンボルは、この実施形態においては、第２のシーケンス２０の最上位シンボルの後の組み合わせシーケンス７０における次のシンボル位置を占有する。これは、ポインタ１１が組み合わせシーケンス７０におけるシンボル位置Ｓ1の方向を指し示す場合（第１の読出し方向に従って）、第３のシーケンス３０の最上位シンボルがシンボル位置Ｓ1＋１を占有することを意味する。従って、ポインタ１１により、この例において第２のシーケンス２０と第３のシーケンス３０の双方の開始を識別できるようになる。あるいは、ポインタ１１は、第３のシーケンス３０の最上位シンボルに対応する組み合わせシーケンス７０におけるシンボル位置Ｓ1の方向を指し示す。第２のシーケンス２０の開始位置は、読出し方向に従って組み合わせシーケンス７０における先行するシンボル位置Ｓ1−１となる。
【００５９】
図７Ｃは、図７Ｂと比較して１つの更なるシーケンス５０を有する。第１のシーケンス１０と第３のシーケンス３０のシンボルが第１の読出し方向に読出し可能であるのに対し、第２のシーケンス２０と第４のシーケンス４０と最後のシーケンス５０とは第１の方向とは逆の第２の方向に読出し可能である。第１のポインタ１１は、図７Ｂの例と同様に第２のシーケンス２０と第３のシーケンス３０の開始を規定する。第２のポインタ１３は、図７Ｃにおいて組み合わせシーケンス７０に対しても決定される。第２のポインタ１３は、第４のシーケンス４０の最上位シンボル位置を規定する。
【００６０】
図７Ｄにおいて、第１の読出し方向は、第１のシーケンス１０と第３のシーケンス３０と第５のシーケンス５０とにより採用される。残りのシーケンス、すなわち第２のシーケンス２０と第４のシーケンス４０と第６のシーケンス６０とにおけるシンボルは、第１の読出し方向とは逆の第２の読出し方向に読出し可能である。上述したように、第１のポインタ１１は、第２のシーケンス２０と第３のシーケンス３０の開始を規定する。第２のポインタ１３により、第４のシーケンス４０の開始だけではなく、第５のシーケンス５０の開始も識別できるようになる。そのような場合、第２のポインタ１３は、組み合わせシーケンス７０内の第４のシーケンス４０の最上位シンボル位置Ｓ2を規定することが好ましい。そのような場合、第５のシーケンス５０の最上位シンボル及び開始は、第１の読出し方向に従って組み合わせシーケンス７０における次のシンボル位置Ｓ2＋１であることが好ましい。
【００６１】
図７Ａ〜図７Ｄにおける組み合わせシーケンス７０に対する１つ以上のポインタ１１、１３の決定と種々の読出し方向でのシンボルの特定の編成により、組み合わせシーケンス７０の全てのシーケンス１０、２０、３０、４０、５０、６０を同時に読出し、復号化できる。それにより、全組み合わせシーケンス７０を復号化するために並列の復号器と共に単一の復号化ラウンドを使用できるため、復号化側の遅延時間は最小限になる。
【００６２】
図７Ａ〜図７Ｄは、可変長符号化の結果、すなわち全てのシーケンス１０、２０、３０、４０、５０、６０が必ずしもシンボルの数に関して同一のサイズを有さなくてもよいことを更に示している。
【００６３】
図７Ａ及び図７Ｃに最適に示されるように、ポインタ１１、１３が採用される場合、組み合わせシーケンス７０の最後のシーケンス３０、５０は、必ずしも第１の読出し方向とは逆の第２の読出し方向に編成されなければならないことはない。そのような場合、図７Ａのポインタ１１及び図７Ｃのポインタ１３は、最後のシーケンス３０、５０の最上位シンボルのシンボル位置に先行するシンボル位置の方向を指し示すことにより、最後のシーケンス３０、５０の開始位置を規定できる。
【００６４】
しかし、復号化側が偶数Ｎを含む組み合わせシーケンスに対してだけではなく第１の方向とは逆の第２の方向に読み出すことにより常に最後のシーケンスを取り出するように予め設定可能であるため、一般に第１の方向とは逆の第２の方向に従って常に最後のシーケンスを有することが好ましい。また、第１の方向とは逆の第２の方向に最後のシーケンスを有することは、ポインタが採用されない場合でもシンボルの少なくとも２つのシーケンスが組み合わせシーケンスから読出し可能であることを示唆する。
【００６５】
ステップＳ３０の一実施形態において、ポインタは、組み合わせシーケンスにおけるシーケンス番号２ｋの最上位シンボルのシンボル位置に対応する値を有するように決定される。例えば、組み合わせシーケンスの長さが最大３０７２ビットである場合、ポインタは１２ビットとなる。しかし、ポインタが独立していないという事実を使用することにより、ポインタのサイズを小さくできる。従って、第２のポインタ及び更なるポインタのシンボル位置は、第１のポインタ及び前のポインタのビット位置より小さくなり得ない。別の一実施形態において、ポインタは、必ずしも組み合わせシーケンスにおける絶対位置ではなく、前のポインタに対するシンボル位置に等しい。
【００６６】
そのような場合、第１のポインタは、第２のシーケンスの最上位シンボルのシンボル位置に等しいようにステップＳ３０で決定される。ステップＳ３０は、組み合わせシーケンスにおけるシーケンス番号２ｊ＋２の最上位シンボルのシンボル位置とシーケンス番号２ｊの最上位シンボルのシンボル位置との差に等しいポインタ番号ｊ＋１を判定することを更に含む。これは、図７Ｃ及び図７Ｄから分かるように、第２のポインタ１３が組み合わせシーケンス７０における第４のシーケンス４０と第２のシーケンス２０の最上位シンボルのシンボル位置の差に等しくなることを意味する。パラメータｊは整数であり、Ｎが奇数の場合にｊ∈［１，（Ｎ−２）／２］、（Ｎ−１）／２≧２であり、Ｎが偶数の場合に ｊ∈［１，（Ｎ−１）／２−１］、Ｎ／２−１≧２である。
【００６７】
この実施形態において、各ポインタを個々に判定する場合と比較して、ビット数又はシンボル数に関する第２のポインタ及び更なるポインタの長さを短縮できる。
【００６８】
ステップＳ３０で決定された少なくとも１つのポインタは、ステップＳ３１でメモリに格納される。このメモリは、グラフィカル処理ユニットのオンチップメモリであるという利点があり、組み合わせシーケンスが格納される同一のメモリであることが好ましい。ステップＳ３１でポインタをメモリに格納することは、メモリが２つ以上の組み合わせシーケンスを含むことができる場合にポインタが属する組み合わせシーケンスを識別できるような方法で実行される。
【００６９】
別の又は更なる一実施形態において、ある特定のシンボル位置の方向を指し示すようにポインタを制限することにより、ポインタのサイズを更に縮小できる。例えば、強制的に組み合わせシーケンスのポインタが組み合わせシーケンスにおける偶数のシンボル位置又は奇数のシンボル位置の方向のみを指し示すようにすることにより、ポインタの長さを短縮できる。これは、シーケンスの少なくとも１つの開始位置を移動させるために組み合わせシーケンスに追加されるいわゆるパディングシンボルを使用することにより可能である。これは、４、８又は他の何らかの固定の数で除算可能なシンボル位置及びアドレスのみを指し示すことができるようポインタを制限するように更に拡張可能である。
【００７０】
図８は、この概念を示すフローチャートである。この方法は、図１のステップＳ２から継続する。次のステップＳ４０は、少なくとも１つのパディングシンボルを組み合わせシーケンスに追加する。ステップＳ４０は、組み合わせシーケンスにおけるシーケンス番号２ｋ−１の最下位シンボルとシーケンス番号２ｋとの間に少なくとも１つのパディングシンボルを追加することを含むことが好ましい。それにより、少なくとも１つのパディングシンボルは、既に偶数又は奇数のシンボル位置にない限り、シーケンス番号２ｋの最上位シンボルのシンボル位置を強制的に組み合わせシーケンスにおける偶数のシンボル位置又は奇数のシンボル位置にする。従って、ポインタが偶数（又は奇数）のシンボル位置においてのみ開始すると判定される場合、組み合わせシーケンスにおける第２及び第４等のシーケンス番号２ｋの最上位シンボルのシンボル位置が調べられる。シンボル位置が偶数（又は奇数）の場合、パディングシンボルは追加されない。しかし、シンボル位置が代わりに奇数（又は偶数）になる場合、少なくとも１つのパディングシンボルは、組み合わせシーケンスにおける現在のシーケンス番号２ｋと前のシーケンス番号２ｋ−１の最下位シンボルの間に追加される。それにより、パディングシンボルは、最上位シンボルに対するシンボル位置を移動させ、ポインタの位置を偶数（又は奇数）のシンボル位置へと移動する。
【００７１】
図９は、この概念を概略的に示す。図９において、パディングシンボル２１は、第１のシーケンス１０と第２のシーケンス２０の最下位シンボルの間に追加されていることにより、第２のシーケンス２０の開始位置に移動し、これにより第１のポインタ１１のシンボル位置を所望のシンボル位置に移動させる。同様に、パディングシンボル２３は、第３のシーケンス３０と第４のシーケンス４０の最下位シンボルの間に追加されており、第４のシーケンス４０の開始位置と第２のポインタ１３のシンボル位置を移動させる。
【００７２】
パディングシンボルは、組み合わせシーケンスにおけるポインタの位置を移動させるためだけに使用されなくてもよい。パディングシンボルは、効率的なバースト転送のために所望のシンボル長に正確に一致するパディングシンボルを含む組み合わせシーケンスの合計サイズを得るように組み合わせシーケンスにも追加可能である。例えば、バースト転送の観点からの組み合わせシーケンスの最適な長さが５１２個のシンボルである場合、パディングシンボルは、ブロックの可変長符号化の結果、符号化ブロックの組み合わせシンボルに対する長さが短くなった場合にこの目標の長さに到達するように組み合わせシーケンスに追加可能である。これらのパディングシンボルは、例えば、組み合わせシーケンスにおける最後のシーケンスと最後から２番目のシーケンスとの間の連続シーケンスに全て追加可能である。あるいは、パディングシンボルは、連続したシーケンス間で組み合わせシーケンスにおける多数の位置において分散される。余分なパディングシンボルは、あらゆるポインタに対するシンボル位置が効率的に容易に表現可能な位置に進むような方法で挿入可能である。例えばパディングシンボルは、ポインタ位置を予め定義されたシンボル位置に近接させるように追加可能である。この概念を以下に示す。即ち、
A.......B.......C...............D..............................E
00000xaaaa11111xbb2222cccc33333xxxxxxxxxxxxxxxxxxxxxxxxxxxxddddd
^       ^     ^
である。
【００７３】
上記のシーケンスにおいて、Ａはシンボル位置０を表し、Ｂはシンボル位置８を表し、Ｃはシンボル位置１６を表し、Ｄはシンボル位置３２を表し、Ｅはシンボル位置６３である。数字は、第１、第３、第５及び第７のシーケンスのシンボルを表し、アルファベットは、第２、第４、第６及び第８のシーケンスのシンボルを表す。ｘはパディングシンボルを表し、＾はポインタのシンボル位置を示す。
【００７４】
この例示的な例において、パディングシンボルは、強制的にポインタが奇数のシンボル位置を指し示すように追加されている。更にパディングシンボルは、この例においては６４個のシンボルの最適な長さに到達するように第７のシーケンスと第８のシーケンスとの間に追加されている。しかし、余分なパディングシンボルが異なる方法で分散される場合、ポインタはシンボル位置Ｂ、Ｃ及びＤに対してより近くへ動かされる。即ち、
A.......B.......C...............D..............................E
00000aaaa11111xbb2222xxxxxxxxcccc33333xxxxxxxxxxxxxxxxxxxxxddddd
^       ^               ^
である。
【００７５】
この場合、パディングシンボルは、ポインタがシンボル位置Ｂ、Ｃ、Ｄ、すなわち８、１６及び３２に近接するようにシーケンス間に追加されている。その場合、これらの又は他のいくつかの規定のシンボル位置に関連してポインタを規定することがより効率的だろう。従って、各ポインタは、この例においては第２、第４又は第６のシーケンスの最上位シンボルと規定のシンボル位置８、１６又は３２とのシンボル長の差分を示す。ポインタを表すために６ビットを必要とするのではなく、この手法は、代わりに位置の差分を示すことでパディングシンボルを用いてポインタ長を６ビットより短くなるように削減できる。
【００７６】
再度図３を参照すると、ステップＳ１０は、データバスを介してグラフィカルユニットのメモリからディスプレイユニットのバッファメモリに組み合わせシーケンスを送信することを含む。ステップＳ１０は、この実施形態において、データバスを介してグラフィカルユニットのメモリからディスプレイユニットのメモリあるいはそれに接続されたメモリに組み合わせシーケンスに対して決定されたポインタを送信することを更に含む。このメモリは、バッファメモリ又は別のメモリであってよい。
【００７７】
別の一実施形態において、少なくとも２つのシーケンスのシンボルは、多重化技術又はインタリービング技術と同様に合同編成される。この実施形態は、第１のシーケンスと第２のシーケンスのうちの一方の全てのシンボルが第１の読出し方向に読出し可能であるのに対し、第１のシーケンスと第２のシーケンスのうちの他方のシンボルの第１の部分が第１の読出し方向に読出し可能であり、そのシンボルの残りの第２の部分が第１の読出し方向とは逆の第２の読出し方向に読出し可能であるようにシンボルを合同編成する。双方の読出し方向に読出し可能なシンボルを有するシーケンスは、他のシーケンスより多くのシンボルを含む。
【００７８】
例えば、第２のシンボルシーケンスが第１のシンボルシーケンスより多くのシンボルを含むと仮定する。第１のシーケンスのシンボルが組み合わせシーケンスの第１の部分における全ての奇数又は偶数のシンボル位置を占有するように、シンボルの合同編成は、第１のシーケンスと第２のシーケンスにおけるシンボルをシンボルの組み合わせシーケンスに合同編成することを含む。第２のシーケンスのシンボルの第１の部分は、組み合わせシーケンスの第１の部分における全ての偶数又は奇数のシンボル位置を占有し、組み合わせシーケンスの残りの第２の部分における全ての偶数又は奇数のシンボル位置も占有する。第１のシーケンスのシンボルと第２のシーケンスにおけるシンボルの第１の部分は、第１の読出し方向に読出し可能である。第２のシーケンスにおけるシンボルの残りの第２の部分は、組み合わせシーケンスの残りの第２の部分における全ての奇数又は偶数のシンボル位置を占有し、第１の読出し方向とは逆の第２の読出し方向に読出し可能である。
【００７９】
図１０は、この概念を視覚的に示す。図１０において、第１のシーケンス１０のシンボルが白色であるのに対し、第２のシーケンス２０のシンボルは斜線が施されて示される。図１０は、シンボル毎のそれぞれの読出し方向を更に示している。図示された例において、第１のシーケンス１０のシンボルは、組み合わせシーケンス７０の第１の部分７Ｂにおける偶数のシンボル位置（０，２，４，……）を占有する。第１の部分７Ｂにおける奇数のシンボル位置（１，３，５，……）は、第２のシーケンス２０の最上位シンボルにより占有される。第２のシーケンス２０は、組み合わせシーケンス７０の残りの第２の部分８Ｂにおける奇数のシンボル位置を更に占有する。組み合わせシーケンス７０におけるこれらの全てのシンボル、すなわち奇数のシンボル位置における第１のシーケンス１０の全てのシンボルと第２のシーケンス２０のシンボルは、第１の読出し方向に読出し可能である。組み合わせシーケンス７０の最終部に到達すると、第２のシーケンス２０の残りのシンボルは、組み合わせシーケンス７０の残りの第２の部分８Ｂにおける偶数の位置を占有する。その後、第２のシーケンス２０は、最初に組み合わせシーケンス７０における奇数のシンボル位置を占有するシンボルを第１の読出し方向に読出し、次に第１の読出し方向とは逆の第２の読出し方向にではあるが組み合わせシーケンス７０の残りの第２の部分８Ｂにおける偶数のシンボル位置を読出すことに続くようにして読み出される。
【００８０】
例えば、第１のシーケンスが０１２３４５により示され、且つ第２のシーケンスがａｂｃｄｅｆｇｈｉｊであると仮定すると、結果として得られる組み合わせシーケンスは、０ａ１ｂ２ｃ３ｄ４ｅ５ｆｊｇｉｈのように見えるだろう。第１のシーケンスは、第１のシーケンスの最終部に到達するまで第１の読出し方向に偶数のシンボル位置を読出す、すなわち組み合わせシーケンスにおけるシンボル位置０、２、４、６、８を読出すことで取得される。第２のシーケンスは、最初に組み合わせシーケンスの最終部まで第１の読出し方向に奇数のシンボル位置を読出すことで、すなわちシンボル位置１、３、５、７、９、１１、１３、１５を読出すことで取得される。その場合、第２のシーケンスのこれらの第１のシンボルはａｂｃｄｅｆｇｈである。第２のシーケンスの残りのシンボルは、第２のシーケンスの最終部に到達するまで第１の読出し方向とは逆の第２の読出し方向に偶数のシンボル位置、すなわち最後の２つのシンボルｉｊを与える読出しシンボル位置１４、１２から読出される。
【００８１】
更にこの実施形態において、双方のシーケンスは同時に読出し、復号化可能である。
【００８２】
この実施形態は、逆の読出し方向にシーケンスを配置することで組み合わされる。そのような場合、図１０に示されたような組み合わせシーケンスは基本的には、ミラー型のインタリーブされたシーケンスで補完される。組み合わせシーケンスは少なくとも４つのシーケンスを含む。最初の２つのシーケンスはインタリーブされ、それらのうちの一方のシーケンスは第１の読出し方向にだけ読出される。他方のシーケンスが第１の読出し方向に従って部分的に読出されるのに対し、残りのシンボルは、第１の読出し方向とは逆の第２の読出し方向に従って読出される。残りの２つのシーケンスもインタリーブされるが、それらのうちの一方のシーケンスは、第１の読出し方向とは逆の第２の読出し方向にだけ読出される。他方のシーケンスが第１の読出し方向とは逆の第２の読出し方向に部分的に読み出されるのに対し、残りのシンボルは第１の読出し方向に従って読み出される。
【００８３】
そのような組み合わせシーケンスの一例は、０ａ１ｂ２ｃ３ｄ４ｅ５ｆｊｇｉｈｑｒｐｓｏ９ｎ８ｍ７ｌｋ６であってよい。上記のように、第１のシーケンスは０１２３４５であり、第２のシーケンスはａｂｃｄｅｆｇｈｉｊである。第３のシーケンスは６７８９であり、第４のシーケンスはｋｌｍｎｏｐｑｒｓである。
【００８４】
復号化
図１１は、画素のタイルを復号化する方法を示すフローチャートである。その方法はステップＳ５０において開始し、組み合わせシーケンスはバッファメモリから取り出される。組み合わせシーケンスは、上述したように、少なくとも第１のブロックにおける複数の画素の画素値の可変長符号化表現であるシンボルの第１のシーケンスと第２のブロックにおける複数の画素の画素値の可変長符号化表現であるシンボルの第２のシーケンスを含む。第１のブロックと第２のブロックとは、タイルの異なるサブセットを構成する。
【００８５】
次のステップＳ５１は、組み合わせシーケンスにおける規定の第１のシンボル位置から開始して第１の読出し方向に取り出された組み合わせシーケンスの一部を読出すことにより、第１のシーケンスを識別する。ステップＳ５１は、組み合わせシーケンスにおける規定の第２のシンボル位置から開始して第１の読出し方向とは逆の第２の読出し方向に取り出された組み合わせシーケンスの一部を読出すことにより、第２のシーケンスを識別することを更に含む。
【００８６】
以下のステップＳ５２とＳ５３では、識別された第１のシーケンスと第２のシーケンスを復号化して、第１のブロックと第２のブロックとにおける複数の画素の画素値の復号化表現を取得する。ステップＳ５２、Ｓ５３で実行された復号化は基本的には、上述した可変長符号化の逆の処理であり、可変長符号化方式に関して本明細書において引用された参考文献は、この実施形態に従って採用される種々の対応する復号化方式を更に開示している。
【００８７】
ステップＳ５１は、第１のシーケンスと第２のシーケンスの双方が組み合わせシーケンスから同時に識別され、読出されるように実行されることが好ましい。また。第２のシーケンスを復号化する復号化ステップＳ５３は、第１のシーケンスを復号化する復号化ステップＳ５２と少なくとも部分的に同時に実行されることが好ましい。そのような場合、それぞれのシーケンスを識別し復号化する合計時間を短縮することにより、復号化遅延時間を最短にできる。
【００８８】
図１２は、図１１の識別ステップの一実施形態を示すフローチャートである。この実施形態は、特に図５に示されたような組み合わせシーケンスに適している。この方法は、図１１のステップＳ５０から継続する。次のステップＳ６０は、組み合わせシーケンス７０の最上位シンボル位置から開始して第１の読出し方向に組み合わせシーケンス７０の第１の部分７Ａを読出すことにより、第１のシーケンス１０を識別する。可変長符号化は、規定の開始シンボル位置から開始してシーケンスのシンボル位置によりシンボル位置を読出すことにより、シーケンスの最終部に到達する時を識別できるように実行される。これは、この実施形態により採用された可変長符号化方式の固有の特性である。従って、ステップＳ６０は、最下位シンボルに向かって第１の読出し方向に最上位シンボル位置からシンボルを読み出すことと、第１のシーケンス１０の最終部に到達すると読出しを停止することとを含む。
【００８９】
同様に、ステップＳ６１は、一般に組み合わせシーケンス７０の後続部分である第２の部分８Ａの最下位シンボルから開始して第１の読出し方向とは逆の第２の読出し方向に組み合わせシーケンス７０の後続部分である第２の部分８Ａを読み出すことにより、第２のシーケンス２０を識別することを含む。
【００９０】
２つのステップＳ６０とＳ６１では、組み合わせシーケンス７０の両端から開始して双方の読出し方向に組み合わせシーケンス７０を読出すことにより、少なくとも部分的に同時に実行されることが好ましい。その後、この方法はステップＳ５２とＳ５３に続き、識別されたシーケンスが復号化される。
【００９１】
組み合わせシーケンスが本明細書において上述したように編成されたＮ個のシーケンスを含む場合、図１１の識別ステップは、組み合わせシーケンスにおける最上位シンボル位置から開始して第１の読出し方向に組み合わせシーケンスを読出すことにより、Ｎ個のシーケンスのうちの最初のシーケンスを識別することを含むことが好ましい。識別ステップは、組み合わせシーケンスの最下位シンボル位置から開始して第１の読出し方向とは逆の第２の読出し方向に組み合わせシーケンスを読出すことにより、Ｎ個のシーケンスのうちの最後のシーケンスを識別することを更に含む。組み合わせシーケンスにおける残りのシーケンスは、それぞれの規定のシンボル位置において開始して第１の読出し方向とは逆の第２の読出し方向に残りのシーケンスの偶数の番号を付けられた全てのシーケンスに対して組み合わせシーケンスを読出すことにより識別される。残りのシーケンスの奇数の番号を付けられたそれぞれのシーケンスは、それぞれの規定のシンボル位置において開始して第１の読出し方向に組み合わせシーケンスを読出すことにより識別される。
【００９２】
従って、この場合、Ｎ個のシーケンスのシーケンス番号Ｎは、前記組み合わせシーケンスの最下位シンボルから開始して第１の読出し方向とは逆の第２の読出し方向の読出し位置における組み合わせシーケンスの一部を読み出すことにより識別される。Ｎ個のシーケンスのシーケンス番号２ｍ＋１は、それぞれの規定のシンボル位置から第１の読出し方向に組み合わせシーケンスのそれぞれの部分を読出すことにより識別される。パラメータｍは整数であり、かつ、ｍ∈［０，（Ｎ−２）／２］である。その識別は、それぞれの規定のシンボル位置から第１の読出し方向とは逆の第２の読出し方向に組み合わせシーケンスのそれぞれの部分を読み出すことにより、Ｎ個のシーケンスのシーケンス番号２ｎを識別することを更に含む。パラメータｎは整数であり、ｎ∈［１，（Ｎ−１）／２］である。
【００９３】
第１のラウンドにおける最初のシーケンスと最後のシーケンスの識別に続いて、組み合わせシーケンスにおける中間シーケンス又は残りのシーケンスのそれぞれの規定のシンボル位置を取得できる。従って、第１の読出し方向に最初のシーケンスの最終部に後続するかあるいは第１の読出し方向とは逆の第２の読出し方向に最後のシーケンスの最終部に続く次のシンボル位置は、組み合わせシーケンスにおける別のシーケンスに対する規定のシンボル位置及び開始シンボルであってよい。別の手法において、少なくとも１つのポインタが、規定のシンボル位置を見つけるために採用される。
【００９４】
図１３は、組み合わせシーケンスにおけるシーケンスに対する規定のシンボル位置を識別するためにポインタを使用する方法を示すフローチャートである。その方法は、図１１のステップＳ５０から続く。一実施形態において、ステップＳ７０が省略されるため、この方法はステップＳ７１に直接続く。ステップＳ７１は、組み合わせシーケンスと関連付けられたポインタに基づいてシーケンスに対する規定のシンボル位置を識別する。特定の一実施形態では、ステップＳ７１は、Ｎが奇数の場合には（Ｎ−１）／２個のポインタから、そして、Ｎが偶数の場合にはＮ／２−１個のポインタからとられたポインタに基づいて、シーケンス番号２ｋそしてオプションとしては２ｋ＋１の最上位シンボルに対応する規定のシンボル位置を識別することを含む。ポインタは、Ｎ個のシーケンスのシーケンス番号２ｋに対する最上位シンボルのシンボル位置を規定することが好ましい。第１の読出し方向の次のシンボル位置は、次のシーケンス、すなわちシーケンス番号２ｋ＋１に対する最上位シンボルであることが好ましい。従って、各ポインタにより、１つ又は２つのシーケンスに対する開始位置を識別できる。例えば、図７Ｃにおいて、第１のポインタ１１により、第２のシーケンス２０と第３のシーケンス３０の双方に対する開始位置を識別できるようになる。しかし、第５のシーケンス５０の開始位置がこの実施形態において組み合わせシーケンス７０の最下位シンボルと一致するため、第２のポインタ１３により、第４のシーケンス４０に対する開始位置のみを識別できる。組み合わせシーケンスにおけるＮ個のシーケンスが読出し方向に対して全て交互になっている場合、各ポインタは、２つのシーケンス、すなわちシーケンス番号２ｋ及び２ｋ＋１に対するそれぞれの規定のシンボル位置を規定する。パラメータｋは整数であり、Ｎが奇数の場合にはｋ∈［１，（Ｎ−１）／２］であり、Ｎが偶数の場合にはｋ∈［１，Ｎ／２−１］である。
【００９５】
シーケンスが図７Ａ〜図７Ｄに示された技術に従って合同編成される場合、Ｎが奇数の場合に最後のポインタを除く各ポインタにより、組み合わせシーケンスにおける２つのシーケンスに対する規定のシンボル位置を識別できる。従って、このことは、ポインタが単一のシーケンスの開始位置のみを識別する２ｋ＋１＝Ｎの場合を除くパラメータｋの全ての許容値に対して生じる。
【００９６】
規定のシンボル位置を識別するためにステップＳ７１で採用されたポインタは、それぞれの規定のシンボル位置を直接規定できる。別の手法において、ポインタは、図１３のステップＳ７０で最初に算出される。そのような場合、シーケンスの規定のシンボル位置は、組み合わせシーケンスに対する現在のポインタと全ての前のポインタとの和を算出することによりうまく取得される。これは、その後組み合わせシーケンスにおける関連するシーケンスに対する開始位置を直接規定する最初のポインタを除く全てのポインタに当てはまることが好ましい。
【００９７】
従って、特に一実施形態において、ステップＳ７０は、ポインタ番号ｊ＋１とポインタ番号ｊとの和に基づいてシーケンス番号２ｊ＋２、そして、オプションとしては２ｊ＋３に対する規定のシンボル位置を算出することを含む。パラメータｊは整数であり、Ｎが奇数の場合にｊ∈［１，（Ｎ−３）／２］であり、Ｎが偶数の場合にｊ∈［１，Ｎ／２−２］ である。この場合、パラメータＮのより小さな値に対しては単一のポインタしか必要とされないため、Ｎ≧５である。
【００９８】
別の一実施形態において、組み合わせシーケンス７０は、図１０に示されたように編成される。そのような場合、図１１の識別ステップは、組み合わせシーケンス７０の第１の部分７Ｂにおける全ての奇数と偶数のシンボル位置のうちの一方を第１の読出し方向に読み出すことにより、第１のシーケンス１０を識別することを含む。第２のシーケンス２０は、組み合わせシーケンス７０における全ての奇数又は偶数のシンボル位置、すなわち第１の部分７Ｂと残りの第２の部分８Ｂの双方のうちの他方を第１の読出し方向に読出すことにより識別される。また、組み合わせシーケンス７０の最終部に到達すると、組み合わせシーケンスの残りの第２の部分における全ての奇数と偶数のシンボル位置のうちの一方を第１の読出し方向とは逆の第２の読出し方向に読出すことで読出しは継続する。
【００９９】
双方の読出し方向に従って読出されるように提供されたインタリーブされたシーケンスを含む組み合わせシーケンスを使用することも可能である。従って、第１のシーケンスと第２のシーケンスとは第１の読出し方向から読み出され、第２のシーケンスの最後のシンボルは第１の読出し方向とは逆の第２の読出し方向から読み出される。第３のシーケンスと第４のシーケンスとは第１の読出し方向とは逆の第２の読出し方向から読み出され、代わりに、第４のシーケンスの最後のシンボルは上述したように第１の読出し方向から読み出される。
【０１００】
実装の特徴
図１４は、一実施形態に係るグラフィックスシステムを示す概略図である。グラフィックスシステムは、３つの主要なユニット又はエンティティ、すなわちデータバス３８０、３８５を介して相互接続された図１４においてＧＰＵで示されたグラフィカル処理ユニット３００、バッファメモリ４３０及びディスプレイ装置４００を備える。グラフィックスシステムは、あらゆるデータ処理ユニット又はデータ処理端末において実現される。非限定的な例には、ラップトップを含むコンピュータ、ゲーム機、移動電話、並びに情報携帯端末（ＰＤＡ）、ｉＰａｄ（登録商標）及び他のタブレットコンピュータ等の他の移動処理ユニットが含まれる。
【０１０１】
グラフィカル処理ユニット３００は、可変長符号器３１０により符号化されている時にタイル１を格納するように構成されたオンチップメモリ３４０を含む。結果として得られるそれぞれの組み合わせシーケンスは、データバス３８０を介してオンチップメモリ３４０からバッファメモリ４３０に転送される。バッファメモリ４３０は、符号化圧縮形式で提供された画素値バッファ９を含む。ディスプレイ装置４００のディスプレイ４７０あるいはディスプレイ装置４００に接続されたディスプレイ４７０上にデータを表示する際、圧縮された画素値バッファ９の少なくとも一部に対応する符号化データは、バッファメモリ４３０から読出され、データバス３８５を介して並列の復号器４４０のセットに提供される。次にこれらの復号器４４０は、ディスプレイ４７０上に表示可能な画素値を取得するためにフェッチされた符号化データを復号化する。
【０１０２】
別の実装例の実施形態において、単一のデータバスは、ＧＰＵ３００からバッファメモリ４３０に、そしてバッファメモリ４３０からディスプレイ装置４００にデータを転送するために採用される。ディスプレイ装置４００の一部としてバッファメモリ４３０を配置することも可能である。
【０１０３】
特定の一実施形態において、ＧＰＵ３００は、チャンクにおける全てのブロックを可変長符号化し圧縮する。ブロックを表すために必要とされ、選択的にあらゆるポインタビット及びあらゆるパディングビットを含む一般的には複数のビットからなる全てのシンボルの和は、チャンクの合計サイズを規定する。例えば、チャンクにおける８個の４ブロック×４ブロックを仮定する。圧縮されていないチャンクは、ＲＧＢ８８８のカラーバッファの場合に４×４×８×３＝３０７２ビットのサイズを有する。圧縮によりサイズを６６％、３３％又は１／６まで縮小できる場合、対応する合計サイズは、２０４８ビット、１０２４ビット又は５１２ビットとなる。これは、２つのサイズビット００bin〜１１binを使用することで信号が送られる。タイル１の符号化中、チャンクに対するこれらのサイズビットは、オンチップメモリ３４０におけるＧＰＵ３００に格納される。全タイル１は、符号化されるとデータバス３８０を介してＧＰＵ３００からバッファメモリ４３０に送出される。サイズビットは、好ましくはディスプレイ装置４００又はバッファメモリ４３０の別の部分におけるサイズメモリ等の別のメモリ領域に更に転送される。サイズビットは、例えば、第１のタイル１における全てのチャンク、次に第２のタイルに対する全てのサイズビットから開始するサイズメモリに互いに後で格納されることが好ましい。
【０１０４】
ディスプレイ装置４００は、バッファメモリ４３０からデータを読出そうとしている場合、バッファメモリ４３０からバーストインされるべきデータ量を判定するために適切なサイズビットを最初に読み出す。例えば、０１binのサイズビットは、現在のチャンクに対して２０４８ビットバーストインすることを示せる。これらの２０４８ビットの全てが必ずしもディスプレイ装置４００の復号器４４０により使用され復号化されなくてもよい。
【０１０５】
ＧＰＵ３００は、タイルの符号化後に全てのサイズビットをサイズメモリに必ずしも転送する必要はない。格納されたこれらのサイズビットの合計サイズがデータバス３８０、３８５を介した効率的な転送のために所望のバーストサイズに適切に適合するまで、多くのサイズビットをオンチップメモリ３４０に格納できるとよい。
【０１０６】
代わりに、サイズビットは、ディスプレイ装置４００の復号器４４０に直接送出されてよい。復号器４４０は、ディスプレイ４７０上に表示される全てのタイルに対する全てのサイズビットを格納するのに十分に大きなオンチップメモリを含むか、あるいはそれに接続される。
【０１０７】
符号器
図１５は、一実施形態に係るタイルを符号化する装置１００を示す概略ブロック図である。装置１００は、少なくとも複数の画素の第１のブロックと複数の画素の第２のブロックを可変長符号化してシンボルの第１のシーケンスとシンボルの第２のシーケンスを形成するように構成された可変長符号器１１０を備える。装置１００は、少なくとも第１のブロックと第２のブロックの画素値に対して連続して動作する単一の可変長符号器１１０を備えると良い。あるいは、装置１００は、タイルにおける種々のブロックからの画素データに対して同時に動作できる多数の可変長符号器１１０のセットを含んでも良い。
【０１０８】
シンボル編成器１２０が、装置１００に実装され、可変長符号器１１０からの第１のシーケンスと第２のシーケンスのシンボルをシンボルの組み合わせシーケンスに合同編成するように構成される。第１のシーケンスのシンボルが第１の読出し方向に読出し可能であるのに対し、第２のシーケンスにおけるシンボルの少なくとも一部が第１の読出し方向とは逆の第２の読出し方向に読出し可能であるように、シンボル編成器１２０はシンボルを合同編成するように構成される。シンボル編成器１２０により生成された組み合わせシーケンスは、装置１００のメモリ１４０にデータを書込み、メモリ１４０からデータを読出すように構成されたメモリコントローラ１３０によりメモリ１４０に格納される。
【０１０９】
装置１００は、一般的な入出力（Ｉ／Ｏ）ユニット１５０として図示された出力ユニット１５０を備えることが好ましい。出力ユニット１５０は、図１４に示されたデータバスを介してメモリ１４０からバッファメモリに組み合わせシーケンスを送信又は転送するように構成される。Ｉ／Ｏユニット１５０は、Ｉ／Ｏユニット１５０をデータバスと相互接続する１つ以上のＩ／Ｏポートを含むことが好ましい。
【０１１０】
特定の一実施形態において、シンボル編成器１２０は、組み合わせシーケンスの第１の部分において第１の読出し方向に第１のシーケンスのシンボルを編成するように構成される。シンボル編成器１２０は、組み合わせシーケンスの後続部分である第２の部分において第１の読出し方向とは逆の第２の読出し方向に第２のシーケンスのシンボルを更に編成する。
【０１１１】
可変長符号器１１０は、一実施形態において画素の３つ以上のブロックを符号化して、すなわちタイルのＮ個のブロックを可変長符号化して、Ｎ個のブロックの画素値の符号化表現としてシンボルのＮ個のシーケンスを形成する。ここで、Ｎは３以上の整数である。シーケンス番号Ｎ、すなわち最後のシーケンスのシンボルが第１の読出し方向とは逆の第２の読出し方向に読出し可能であるように、シンボル編成器１２０は、この実施形態においてＮ個のシーケンスのシンボルを組み合わせシーケンスに合同編成するように構成されることが好ましい。更にシンボル編成器１２０は、第１の読出し方向に読出し可能となるようにＮ個のシーケンスのシーケンス番号２ｍ＋１のシンボルを編成し、前記第１の読出し方向とは逆の第２の読出し方向に読出し可能となるようにＮ個のシーケンスのシーケンス番号２ｎのシンボルを編成する。パラメータｍ，ｎは、前に規定されたようなパラメータである。更にシンボル編成器１２０は、昇順にシーケンスを編成することが好ましい。従って、シーケンス番号ｉが組み合わせシーケンスにおいてシーケンス番号ｉ＋１に先行するように、シンボル編成器１２０は、組み合わせシーケンスにおけるＮ個のシーケンスを提供する。ここで、ｉ＝１，２，……，Ｎ−１である。
【０１１２】
オプションの一実施形態において、装置１００は、組み合わせシーケンスにおける少なくとも１つのシーケンスの開始位置を識別できる少なくとも１つのポインタを決定するように構成されたポインタ生成器１６０を備える。ポインタ生成器１６０は、Ｎが奇数の場合には（Ｎ−１）／２個のポインタを、Ｎが偶数の場合にはＮ／２−１個のポインタを決定するように構成されることが好ましい。ポイント生成器１６０は、ポインタ番号ｋが組み合わせシーケンスにおけるシーケンス番号２ｋの最上位シンボルのシンボル位置を規定するように少なくとも１つのポインタを決定する。パラメータｋは、前に規定されたようなパラメータである。メモリコントローラ１３０は、組み合わせシーケンスと共に決定されたポインタをメモリ１４０に格納することが好ましい。また、出力ユニット１５０は、データバスを介して組み合わせシーケンスをバッファメモリに送信することに加えて、データバスを介してメモリ１４０から例えばディスプレイユニットのメモリにポインタを更に送信する。
【０１１３】
一実施形態において、ポインタ生成器１６０は、それぞれのシーケンス番号２ｋの最上位シンボルに対応する組み合わせシーケンスにおけるそれぞれのシンボル位置を示すポインタを決定する。別の一実施形態において、ポインタ生成器１６０は、それぞれのシーケンスのうちの１つと組み合わせシーケンスにおける先行するそれぞれのシーケンスとの最上位シンボルのシンボル位置の差分に等しい少なくとも１つのポインタを決定する。ポインタ生成器１６０は、組み合わせシーケンスにおけるシーケンス番号２ｊ＋２の最上位シンボルのシンボル位置とシーケンス番号２ｊの最上位シンボルのシンボル位置との差分に等しいポインタ番号ｊ＋１を決定するように構成されることが好ましい。パラメータｊは、前に規定されたようなパラメータである。
【０１１４】
オプションのパディング提供器１７０は、少なくとも１つのパディングシンボルを組み合わせシーケンスに追加する装置１００において実現可能である。パディング提供器１７０は、既に規定のシンボル位置にない限り、強制的にシーケンス番号２ｋの最上位シンボルが組み合わせシーケンスにおける規定のシンボル位置にあるようにするために、シーケンス番号２ｋ−１の最下位シンボルとシーケンス番号２ｋの最下位シンボルとの間に少なくとも１つのパディングシンボルを追加するように構成される。従って、パディング提供器１７０は、シーケンス番号２ｋの最上位シンボル及びこの最上位シンボルと関連付けられたポインタを効率的に、すなわちポインタに対してシンボル又はビットを殆ど必要としないポインタにより容易に表現可能な規定のシンボル位置に移動するためにパディングシンボルを使用できる。特定の一実施形態において、パディング提供器１７０は、パディングシンボルを追加し、強制的にポインタが規定する全てのシンボル位置が偶数のシンボル位置又は奇数のシンボル位置にあるようにする。
【０１１５】
追加的に、或いは、代替的に、パディング提供器１７０は、シンボルの数に関する組み合わせシーケンスの目標の長さに到達するために、少なくとも１つのパディングシンボルを組み合わせシーケンスに追加できる。結果として得られる目標の長さは、データバスを介した効率的なバースト転送に適応可能である。
【０１１６】
装置１００は、必ずしも組み合わせシーケンスにおけるシーケンスを互いに順番に編成しなくてもよい。別の手法において、例えば、第１のシーケンスのシンボルが組み合わせシーケンスの第１の部分における全ての奇数（又は偶数）のシンボル位置を占有するように、シンボル編成器１２０は、少なくとも第１のシーケンスと第２のシーケンスのシンボルを組み合わせシーケンスに合同編成するように構成される。シンボル編成器１２０は、組み合わせシーケンス、すなわち組み合わせシーケンスの第１の部分と残りの第２の部分の双方における全ての偶数（又は奇数）のシンボル位置を占有するように第２のシーケンスにおけるシンボルの第１の部分を更に編成する。第１のシーケンスのシンボルと第２のシーケンスにおけるシンボルの第１の部分は、第１の読出し方向、すなわちデフォルトの読出し方向に読出し可能である。第２のシーケンスにおけるシンボルの残りの第２の部分は、組み合わせシーケンスの残りの第２の部分における奇数（又は偶数）のシンボル位置を占有するようにシンボル編成器１２０により代わりに編成される。第２のシーケンスにおけるシンボルのこの残りの第２の部分は、第１の読出し方向とは逆の第２の読出し方向に読出し可能である。この概念は、上述したような４つ以上のシーケンスを含む場合に拡張可能である。
【０１１７】
装置１００のユニット１１０〜１３０、１４０〜１７０は、ハードウェア又はハードウェアとソフトウェアとの組合せとして実現又は提供されてもよい。ソフトウェアによる実装例の場合、装置１００又はその一部を実現するコンピュータプログラムは、汎用又は専用のコンピュータ、プロセッサ又はマイクロプロセッサ上で実行されたソフトウェア又はコンピュータプログラムを含む。ソフトウェアは、図１５に示されたコンピュータプログラムコード要素又はソフトウェアコード部分を含む。プログラムの全て又は一部は、ＲＡＭ等の１つ以上の適切な揮発性コンピュータ可読媒体又はデータ記憶媒体、あるいは磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤディスク、ハードディスク等の１つ以上の不揮発性コンピュータ可読媒体又はデータ記憶手段上又はそれらに格納されてもよく、あるいはＲＯＭ又はフラッシュメモリに格納されてもよい。データ記憶手段は、ローカルデータ記憶手段であってよく、あるいはデータサーバ等にリモートで提供される。
【０１１８】
装置１００のユニット１１０〜１７０は、図１４に示されたようなグラフィカル処理ユニットにおいて実装されることが好ましく、グラフィックスチップ上にあって良い。そのような場合、ユニット１１０〜１７０はハードウェアで実現されるという利点がある。
【０１１９】
復号器
図１６は、画素のタイルを復号化する装置２００を示す概略ブロック図である。装置２００は、データバスを介して符号化形式でタイルを格納するように構成されたバッファメモリに接続されるか、あるいはそれを含む。ここで、タイルは、バッファメモリに格納された画素値バッファの少なくとも一部を構成する。
【０１２０】
装置２００のシーケンス取り出し器２１０は、選択的に汎用Ｉ／Ｏユニット２７０として図示された入力ユニット２７０を使用してデータバスを介してバッファメモリからシンボルの組み合わせシーケンスを取り出すように構成される。Ｉ／Ｏユニット２７０は、Ｉ／Ｏユニット２７０をデータバスと相互接続する１つ以上のＩ／Ｏポートを含むことが好ましい。読み出された組み合わせシーケンスは、一般に装置２００のメモリ２３０に入力される。組み合わせシーケンスは、それぞれ、少なくとも複数の画素の第１のブロックと第２のブロックにおける画素値の可変長符号化表現としてシンボルの第１のシーケンスと第２のシーケンスとを含む。これらの第１のブロックと第２のブロックは、タイルの異なるサブセット又は一部分を構成する。
【０１２１】
オプション的なアプローチにおいて、シーケンス取り出し器２１０は、組み合わせシーケンスの最大サイズ及びバッファメモリから読み出されるべきシンボルの数を判定するために、メモリ２３０又は他の何らかのサイズメモリからサイズビット又はサイズ表示を最初に読み出す。
【０１２２】
シーケンス識別器２２０は、組み合わせシーケンスにおける規定された第１のシンボル位置から開始して第１の読出し方向にシーケンス取り出し器２１０により取り出された組み合わせシーケンスを読出すことにより、第１のシーケンスを識別するように装置２００において実現される。シーケンス識別器２２０は、組み合わせシーケンスにおける規定された第２のシンボル位置から開始して第１の読出し方向とは逆の第２の読出し方向に取り出された組み合わせシーケンスの少なくとも一部を読出すことにより第２のシーケンスを更に識別する。
【０１２３】
装置２００は、シーケンス識別器２２０により識別されたシンボルのそれぞれのシーケンスを処理して復号化するように構成された少なくとも２つの復号器２４０、２５０のセットを更に含む。複数の復号器２４０、２５０を有することにより、装置２００は、同時に多数のシーケンスを復号化でき、それにより合計復号化時間が高速化され、復号化遅延時間が短くなる。
【０１２４】
第１の復号器２４０は、シーケンス識別器２２０により識別された第１のシーケンスを復号化して、第１のブロックにおける複数の画素の画素値の復号化表現を取得するように構成される。第２の復号器２５０は、識別された第２のシーケンスを復号化して、第２のブロックにおける複数の画素の画素値の復号化表現を取得するように同様に構成される。第２の復号器２５０が識別された第１のシーケンスを復号化する第１の復号器２４０と少なくとも部分的に同時に第２のシーケンスを復号化するように、第１の復号器２４０と第２の復号器２５０とは、少なくとも部分的に同時に動作するように構成されることが好ましい。
【０１２５】
一実施形態において、シーケンス識別器２２０は、組み合わせシーケンスの最上位シンボルから開始して第１の読出し方向に組み合わせシーケンスの第１の部分を読出すことにより、第１のシーケンスを識別するように構成される。シーケンス識別器２２０は、好ましくは第１のシーケンスの識別と同時に、組み合わせシーケンスから第２のシーケンスを更に識別する。第２のシーケンスは、一般に組み合わせシーケンスの後続部分である第２の部分の最下位シンボル位置から開始して第１の読出し方向とは逆の第２の読出し方向に組み合わせシーケンスの後続部分である第２の部分を読出すことにより識別される。
【０１２６】
組み合わせシーケンスが３つ以上のシーケンス、すなわち３以上の整数であるＮ個のシーケンスを含む場合、シーケンス識別器２２０は、組み合わせシーケンスの最下位シンボルから開始して第１の読出し方向とは逆の第２の読出し方向の読出し位置における組み合わせシーケンスの一部を読み出すことにより、Ｎ個のシーケンスのうちの最後のシーケンス、すなわちシーケンス番号Ｎを識別することが好ましい。シーケンス識別器２２０は、それぞれの規定のシンボル位置から第１の読出し方向に組み合わせシーケンスのそれぞれの部分を読み出すことにより、Ｎ個のシーケンスのシーケンス番号２ｍ＋１を更に識別する。Ｎ個のシーケンスの残りのシーケンス、すなわちシーケンス番号２ｎは、それぞれの規定のシンボル位置から第１の読出し方向とは逆の第２の読出し方向に組み合わせシーケンスのそれぞれの部分を読み出すことによりシーケンス識別器２２０により識別される。パラメータｍ，ｎは、前に規定されたようなパラメータである。装置２００は、Ｎ個の復号器２４０、２５０を備えることが好ましい。これらの復号器２４０、２５０の各々は、シーケンス識別器により識別されたそれぞれのシーケンスを復号化して、タイルにおけるＮ個のブロックからのそれぞれのブロックにおける複数の画素の画素値の復号化表現を取得するように構成される。あるいは、装置２００は、例えば、第１の復号化ラウンドにおいて組み合わせシーケンスにおけるシーケンス番号１とシーケンス番号Ｎを復号化し、そして、第２のラウンド以降においてシーケンス番号２とシーケンス番号Ｎ−１を復号化する第１の復号器２４０及び第２の復号器２５０を備える。
【０１２７】
特定の一実施形態において、シーケンス識別器２２０は、組み合わせシーケンスと関連付けられ、且つ装置２００のバッファメモリあるいはそれに接続されたバッファメモリ又は別のメモリ２３０に格納されたポインタに少なくとも基づいて、組み合わせシーケンスにおけるシーケンスのうちの少なくとも１つに対する規定のシンボル位置、すなわち開始位置を識別するように構成される。そのような場合、シーケンス識別器２３０は、Ｎが奇数の場合には（Ｎ−１）／２個のポインタから、そして、Ｎが偶数の場合にはＮ／２−１個のポインタからのポインタに基づいてシーケンス番号２ｋとオプション的には２ｋ＋１に対する規定のシンボル位置を識別するように構成される。パラメータｋは、前に規定されたようなパラメータである。
【０１２８】
組み合わせシーケンスと関連付けられたポインタは、シーケンス識別器２２０によりメモリ２３０から取り出されたものとして直接使用可能である。別の一実施形態において、ポインタの実際値は、最初に装置２００の計算器２６０により算出される必要がある。計算器２６０は、ポインタ番号ｊ＋１とポインタ番号ｊとの和に基づいてシーケンス番号２ｊ＋２とオプション的には２ｊ＋３に対する規定のシンボル位置を算出するように構成される。パラメータｊは、前に規定されたようなパラメータである。従って、所定のポインタの規定のシンボル位置は、組み合わせシーケンスに対する第１の読出し方向に所定のポインタの値と前のポインタの値とを合計することで取得されることが好ましい。この手法は、追加のポインタを全く使用しない場合と比較して、ポインタ上で使用されたシンボルの数に関する長さを短縮できることを意味する。
【０１２９】
別の一実施形態において、第１のシーケンスと第２のシーケンスは、図１０に示されたような組み合わせシーケンスに編成される。シーケンス識別器２２０は、組み合わせシーケンスの第１の部分において第１の読出し方向に全ての奇数（又は偶数）のシンボル位置を読出すことにより、第１のシーケンスを識別するように構成される。シーケンス識別器２２０は、組み合わせシーケンスの第１の部分と残りの第２の部分において第１の読出し方向に全ての偶数（又は奇数）のシンボル位置を読出すことにより第２のシーケンスを更に識別する。これらの読出されたシンボルは、第２のシーケンスの第１の部分に対応する。第２のシーケンスにおけるシンボルの残りの第２の部分は、組み合わせシーケンスの残りの第２の部分において第１の読出し方向とは逆の第２の読出し方向に全ての奇数（又は偶数）のシンボル位置を読出すことでシーケンス識別器２２０により取得される。
【０１３０】
装置２００のユニット２１０、２２０、２４０〜２６０は、ハードウェア又はハードウェアとソフトウェアとの組合せとして実現又は提供されてもよい。ソフトウェアによる実装例の場合、装置２００又はその一部を実現するコンピュータプログラムは、汎用又は専用のコンピュータ、プロセッサ又はマイクロプロセッサ上で実行されたソフトウェア又はコンピュータプログラムを含む。ソフトウェアは、図１６に示されたコンピュータプログラムコード要素又はソフトウェアコード部分を含む。プログラムの全て又は一部は、ＲＡＭ等の１つ以上の適切な揮発性コンピュータ可読媒体又はデータ記憶媒体、あるいは磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤディスク、ハードディスク等の１つ以上の不揮発性コンピュータ可読媒体又はデータ記憶手段上又はそれらに格納されてもよく、あるいはＲＯＭ又はフラッシュメモリに格納されてもよい。データ記憶手段は、ローカルデータ記憶手段であってよく、あるいはデータサーバ等にリモートで提供される。
【０１３１】
装置２００のユニット２１０〜２６０は、図１４に示されたようなディスプレイユニットにおいて実現されることが好ましい。特定の一実施形態では、ユニット２１０〜２６０はハードウェアでうまく実現される。
【０１３２】
上述の実施形態は、本発明のいくつかの例示的な例として理解されるべきものである。本発明の範囲を逸脱することなく種々の変形、組合せ及び変更が実施形態に対して行われてもよいことは、当業者により理解されるだろう。特に、技術的に可能である場合、種々の実施形態における種々の部分的な解決方法は、他の構成において組み合わされてよい。しかし、本発明の範囲は添付の請求の範囲により規定される。
【図１】
0005894605.tif 000002
【図２】
0005894605.tif 000003
【図３】
0005894605.tif 000004
【図４】
0005894605.tif 000005
【図５】
0005894605.tif 000006
【図６】
0005894605.tif 000007
【図７Ａ】
0005894605.tif 000008
【図７Ｂ】
0005894605.tif 000009
【図７Ｃ】
0005894605.tif 000010
【図７Ｄ】
0005894605.tif 000011
【図８】
0005894605.tif 000012
【図９】
0005894605.tif 000013
【図１０】
0005894605.tif 000014
【図１１】
0005894605.tif 000015
【図１２】
0005894605.tif 000016
【図１３】
0005894605.tif 000017
【図１４】
0005894605.tif 000018
【図１５】
0005894605.tif 000019
【図１６】
0005894605.tif 000020