JP7650264B2 - パレットテーブル導出への適用による並列ヒストグラム計算 - Google Patents

Description

ビデオデータの圧縮性を高めるために、いくつかのビデオ圧縮標準技術（例えば、ＨＥＶＣ（high efficiency video coding）標準技術、ＡＶ１（Alliance for Open Media video 1）コーディング標準技術）においてパレットコーディングが使用される。パレットコーディングは、候補パレットレベルを判定するようにヒストグラムを計算及び分類することを含む。パレットテーブル導出のためにヒストグラム計算に必要な記憶のサイズは、画素ビット深度と共に指数関数的に高まる。本明細書で使用される「パレットテーブル」という用語は、複数のエントリを記憶したデータ構造として定義され、各エントリは、画素成分値にマッピングするインデックスを記憶する。８ビット、１０ビット及び１２ビットのビデオについて、ヒストグラムビン（histogram bins）の必要とされる数は、従来のパレットコーディング技術に対して、２５６、１０２４及び４０９６である。

添付図面と共に以下の説明を参照することによって、本明細書で説明する方法及びメカニズムの利点をより良好に理解することができる。

コンピューティングシステムの一実施形態のブロック図である。 画像及び対応する画素分布の図である。 コンピュータにより生成されたスクリーンコンテンツ画像及び対応する画素分布の図である。 メモリに結合されたエンコーダの一実施形態のブロック図である。 一実施形態による、所与のブロックについてのサンプルヒストグラムを示す図である。 一実施形態による、画素の所与のブロックについての間引きした（decimated）サンプルヒストグラムを示す図である。 一実施形態による、最上位の間引きした候補ビンの選択を示す図である。 画素成分のビットの一実施形態の図である。 メモリ効率的にパレットテーブルモード符号化を実行する方法の一実施形態を示す一般化されたフローチャートである。 パレットテーブル生成のための複数のヒストグラムを計算する方法の一実施形態を示す一般化されたフローチャートである。 パレットテーブル導出の一部としてヒストグラムを並列に生成する方法の一実施形態を示す一般化されたフローチャートである。 パレットテーブルを使用してビデオ／画像ブロックを符号化する方法の一実施形態を示す一般化されたフローチャートである。

以下の説明では、本明細書で提示される方法及びメカニズムの十分な理解を提供するために、多数の詳細が示される。しかしながら、当業者は、それらの特定の詳細無しに様々な実施形態が実施されてもよいことを認識すべきである。いくつかの例では、本明細書で説明するアプローチを曖昧にすることを回避するために、周知の構造、構成要素、信号、コンピュータプログラム命令、及び、技術が詳細に示されていない。説明を簡潔及び明確にするために、図に示す要素は、必ずしも同じ縮尺で描かれていない。例えば、いくつかの要素の寸法は、他の要素に対して誇張されてもよい。

パレットテーブル導出への適用により並列ヒストグラム計算を実行する様々なシステム、装置及び方法が本明細書で開示される。一実施形態では、エンコーダは、画像又はビデオフレームのブロックの画素成分値（すなわち、色値）のビットの第１の部分についての第１のヒストグラムを計算する。次いで、エンコーダは、第１のヒストグラムから第１の数の最高画素総数ビン（highest pixel count bins）を選択する。また、エンコーダは、ブロックの画素成分値ビットの第２の部分についての第２のヒストグラムを計算し、エンコーダは、第２のヒストグラムから第２の数の最高画素総数ビンを選択する。一実施形態では、第２のヒストグラムは、第１のヒストグラムと並列に計算される。第３のヒストグラムは、第１の数のビンに割り当てられたビットと、第２の数のビンに割り当てられたビットとの連結から計算され、最高画素総数ビンは、第３のヒストグラムから選択される。パレットテーブルは、第３のヒストグラムから選択された最高画素総数ビンに基づいて導出され、ブロックは、パレットテーブルを使用して符号化される。並列マルチヒストグラムアプローチを使用することによって、従来のパレットテーブル導出技術と比較して、メモリ要件が低減する。

一実施形態では、並列演算のために、所与の画素成分のビットが２つのグループに分割される。「ｍ」最上位ビット（ＭＳＢ）は、第１のグループを形成し、「ｎ」最下位ビット（ＬＳＢ）は、第２のグループを形成し、「ｍ」及び「ｎ」は、正の整数である。第１のヒストグラムは、「ｍ」ＭＳＢに対して計算され、次いで、第１のヒストグラムからの最上位ビンが選択される。第２のヒストグラムは、「ｎ」ＬＳＢに対して計算され、次いで、第２のヒストグラムからの最上位ビンが選択される。第３のヒストグラムは、第２のヒストグラムからの最上位ビンに割り当てられたビットと第１のヒストグラムからの最上位ビンに割り当てられたビットとの連結に対して計算される。例えば、「１０１」が第１のヒストグラムからの最上位ビンに割り当てられており、「００１」が第２のヒストグラムからの最上位ビンに割り当てられている場合、第３のヒストグラムは、ビン「１０１００１」を含む。この例では、所与の画素成分が６ビットの画素ビット深度を有することが想定される。他の実施形態では、他の画素ビット深度が使用されてもよい。第３のヒストグラムは、第１のヒストグラムからの最上位ビンと第２のヒストグラムからの最上位ビンとの全ての置換を含む。第３のヒストグラムからの最上位ビンは、パレットテーブル導出のために選択及び使用される。「ｍ」及び「ｎ」の値について、選択される最上位ビンの数、及び、計算される最上位ビンの数は、柔軟であり、実施形態に応じて変化してもよいことに留意されたい。それらの値は、単純なハードウェア実施形態と性能との間のトレードオフに基づいて調整される。

図１を参照すると、コンピューティングシステム１００の一実施形態のブロック図が示されている。一実施形態では、コンピューティングシステム１００は、少なくともエンコーダ１０５と、プロセッサ（複数可）１１０と、入力／出力（Ｉ／Ｏ）インタフェース１２０と、バス１２５と、メモリデバイス（複数可）１３０と、を含む。他の実施形態では、コンピューティングシステム１００は、他の構成要素を含んでもよく、及び／又は、コンピューティングシステム１００は、異なるように構成されてもよい。一実施形態では、エンコーダ１０５は、ビデオコーデック実装するための論理要素及び／又は処理要素を含む。ビデオコーデックは、圧縮されていないビデオストリームを符号化し、及び／又は、圧縮されたビデオストリームを復号する。一実施形態では、ビデオコーデックは、１つ以上のビデオ圧縮標準技術に従って動作する。本明細書で使用される「エンコーダ」及び「ビデオコーデック」という用語は、ビデオ／画像デコーダ、ビデオ／画像エンコーダ、又は、ビデオコーデックを指してもよいことに留意されたい。エンコーダ１０５は、ハードウェア及び／又はソフトウェアの任意の適切な組み合わせを表す。エンコーダ１０５が、プロセッサ（複数可）１１０とは異なる別のユニットとして示されているが、エンコーダ１０５の一部又は全体がプロセッサ（複数可）１１０上で実行されてもよいし、プロセッサ（複数可）１１０上に実装されてもよいことを理解されたい。

プロセッサ（複数可）１１０は、任意の数及びタイプのプロセシングユニット（例えば、セントラルプロセシングユニット（ＣＰＵ）、グラフィックプロセシングユニット（ＧＰＵ）、デジタルシグナルプロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ））を表す。一実施形態では、エンコーダ１０５に関連する処理の一部は、プロセッサ（複数可）１１０によって実行される。メモリデバイス（複数可）１３０は、任意の数及びタイプのメモリデバイスを表す。例えば、メモリデバイス（複数可）１３０におけるメモリのタイプは、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、ＮＡＮＤフラッシュメモリ、ＮＯＲフラッシュメモリ、又は、強誘電体ランダムアクセスメモリ（ＦｅＲＡＭ）等を含んでもよい。メモリデバイス（複数可）１３０は、エンコーダ１０５及びプロセッサ（複数可）１１０によってアクセス可能である。Ｉ／Ｏインタフェース１２０は、任意の数及びタイプのＩ／Ｏインタフェース（例えば、ペリフェラルコンポーネントインターコネクト（ＰＣＩ）バス、ＰＣＩ－Ｘ（PCI-Extended）、ＰＣＩＥ（PCI Express）バス、ギガビットイーサネット（登録商標）（ＧＢＥ）バス、ユニバーサルシリアルバス（ＵＳＢ））を表す。様々なタイプの周辺デバイスがＩ／Ｏインタフェース１２０に結合されてもよい。そのような周辺デバイスは、（限定されないが）ディスプレイ、キーボード、マウス、プリンタ、スキャナ、ジョイスティック又は他のタイプのゲームコントローラ、メディア記録デバイス、外部記憶装置、及び、ネットワークインタフェースカード等を含む。

様々な実施形態では、コンピューティングシステム１００は、コンピュータ、ラップトップ、モバイルデバイス、ゲームコンソール、サーバ、グラフィックカード、システムオンチップ、集積回路、ストリーミングデバイス、ウェアラブルデバイス、これらのデバイス若しくはシステムの一部、又は、様々な他のタイプのコンピューティングシステム若しくはデバイスの何れかであってもよいし、これらの一部であってもよい。コンピューティングシステム１００の構成要素の数は、実施形態毎に変化することに留意されたい。例えば、他の実施形態では、図１に示す数よりも多い又は少ない構成要素が存在する。また、他の実施形態では、コンピューティングシステム１００は、図１に示されていない他の構成要素を含むことに留意されたい。さらに、他の実施形態では、コンピューティングシステム１００は、図１に示す以外の方法で構成されている。

図２を参照すると、画像２０５及び対応する画素分布２１０の図が示されている。図２に示す画像２０５は、画像処理において試験画像として広く使用される公知のレナ画像である。この６４×６４のレナ画像２０５についての画素分布２１０が、図２の下部に示されている。画素分布２１０は、画像２０５内の画素が異なる画素値にわたってどのように分布するかを示す。画素分布２１０に示すような連続した色調を有することは、カメラによってキャプチャされた自然画像又はビデオフレームに対して一般的である。

図３を参照すると、コンピュータにより生成されたスクリーンコンテンツ画像３０５及び対応する画素分布３１０の図が示されている。画像３０５は、コンピュータにより生成されたスクリーンショットの一例であり、画素分布３１０は、比較的少数の画素レベル（すなわち、画素成分値）にわたって画素の狭い分布がどのように存在するかを示す。画素分布に示すように、画像３０５は、制限された少数の区別可能な色を含む。これは、コンピュータにより生成されたスクリーンコンテンツにおいて一般的なタイプの分布であり、そこのようなタイプのコンピュータにより生成された画像について、パレットコーディングは、高圧縮比を達成するために効率的な符号化方法である。コンピュータにより生成されたスクリーンショット以外の他のタイプの画像についても、パレットコーディングが有効である。

図４を参照すると、メモリ４３０に結合されたエンコーダ４０５の一実施形態のブロック図が示されている。一実施形態では、エンコーダ４０５は、ビニングコントローラ４１５と、選択ユニット４２０と、パレットテーブル生成ユニット４２５と、を有する制御ロジック４１０を含む。別の実施形態では、エンコーダ４０５は、プログラム命令を実行するプロセッサによって実装されており、この実施形態では、ビニングコントローラ４１５と、選択ユニット４２０と、パレットテーブル生成ユニット４２５とは、制御ロジックではなくプログラム命令によって実装される。他の実施形態では、ビニングコントローラ４１５と、選択ユニット４２０と、パレットテーブル生成ユニット４２５とは、ハードウェア及びソフトウェアの組み合わせを使用して実装される。

エンコーダ４０５は、任意の数及びタイプのメモリデバイスを表すメモリ４３０に結合されている。一実施形態では、メモリ４３０は、エンコーダ４０５によって符号化されるビデオフレームを記憶する。ビデオブロック４３５は、このビデオフレームの１つのブロックを表す。ビデオブロック４３５を符号化するために使用される技術は、ビデオフレームの他のブロックに対して、及び、ビデオシーケンス内の他のビデオフレームに対して使用されてもよい。或いは、ビデオブロック４３５は、画像の単一のブロックであってもよい。一実施形態では、ビデオブロック４３５は、複数の画素成分値としてメモリ４３０に記憶される。符号化処理の一部として、ビニングコントローラ４１５は、ビデオブロック４３５の画素成分値の第１のビットのサブセットから、第１のビットグループヒストグラム４４０Ａを生成する。一実施形態では、第１のビットのサブセットは、画素成分値のいくつかの数のＭＳＢである。一実施形態では、ビニングコントローラ４１５は、個別の画素成分（例えば、赤、緑、青）毎に個別の第１のビットグループヒストグラム４４０Ａを生成する。第１のビットグループヒストグラム４４０Ａを生成するために、ビニングコントローラ４１５は、第１のビットのサブセットについての異なる取り得るビット値の全てに対応する複数のビンを定義する。次に、ビニングコントローラ４１５は、ビデオブロック４３５からの何個の画素成分値が各ビンに収まるかを集計する。例えば、一実施形態では、ビニングコントローラ４１５は、ビデオブロック４３５の画素成分値を取り出し、次いで、ビニングコントローラ４１５は、その対応するビンに各画素成分値を割り当てる。一実施形態では、各ビンは、各ビンに画素が割り当てられる毎に増分するカウンタを使用して実装される。

一実施形態では、第１のビットグループヒストグラム４４０Ａの各ビンは、所与の数のＭＳＢに対応する画素成分値の範囲を表す。所与の数のＭＳＢは、実施形態に応じて変化してもよい。例えば、一実施形態では、第１のビットグループヒストグラム４４０Ａの各ビンは、画素成分値毎に８ビットの合計からの４つのＭＳＢに対応する範囲を表す。第１のビットグループヒストグラム４４０Ａのビンを生成するために総数未満のビットを使用することによって、第１のビットグループヒストグラム４４０Ａをメモリ４３０に記憶するための記憶要件が低減する。例えば、８ビットからの４つのＭＳＢが第１のビットグループヒストグラム４４０Ａを生成するために使用される場合、８ビット全てが使用された場合の２５６ビンと比較して、１６個のビンのみが生成される。この例では、各画素成分値は、値の４つのＭＳＢに基づいて、ビニングコントローラ４１５によってその各々のビンに割り当てられる。

第１のビットグループヒストグラム４４０Ａが生成され、メモリ４３０に記憶された後に、第１のビットグループヒストグラム４４０Ａのビンは、選択ユニット４２０によって分類される。例えば、ビンは、何個の画素値が各ビンに収まるかに基づいて、最高から最低に分類される。次いで、選択ユニット４２０は、最高画素値を有する所与の数のビンを選択する。例えば、一実施形態では、選択ユニット４２０は、最高画素値を有する８個のビンを選択する。他の実施形態では、選択ユニット４２０は、第１のビットグループヒストグラム４４０Ａ内のビンの全てにわたって最高画素総数（すなわち、最高数の画素値）を有する他の数のビンを選択する。第１のビットグループヒストグラム４４０Ａを計算することと並列に、第２のビットグループヒストグラム４４０Ｂは、画素成分値第２のビットのサブセットに対して生成される。例えば、一実施形態では、第２のビットグループヒストグラム４４０Ｂを計算するために、４つのＬＳＢが使用される。第１のビットグループヒストグラム４４０Ａと同様に、第２のビットグループヒストグラム４４０Ｂのビンは、何個の画素値が各ビンに収まるかに従って分類される。次いで、最上位ビンは、画素値総数に従って選択される。選択される最上位ビンの数は、実施形態に応じて変化する。一実施形態では、最上位８ビットは、選択ユニット４２０によって第２のビットグループヒストグラム４４０Ｂから選択される。

一実施形態では、第１のビットグループヒストグラム４４０Ａから選択された最上位ビンは、第２のビットグループヒストグラム４４０Ｂから選択された最上位ビンと組み合わされ、組み合わされたビットグループヒストグラム４４０Ｃを生成するために使用される。例えば、一実施形態では、第１のビットグループヒストグラム４４０Ａから最上位ビンに割り当てられたＭＳＢは、組み合わされたビットグループヒストグラム４４０Ｃのビンを形成するために、第２のビットグループヒストグラム４４０Ｂから最上位ビンに割り当てられたＬＳＢと連結される。各ビンに収まる画素の数が集計され、次いで、画素総数に関して、最上位ビンが選択される。それらの最上位ビンは、パレットテーブル４５０を導出するためにパレットテーブル生成ユニット４２５によって使用され、パレットテーブル４５０は、ビデオブロック４３５を符号化して、符号化されたブロック４５５を生成するために使用される。いくつかのケースでは、自然の（すなわち、コンピュータにより生成されていない）ビデオフレームにおいて一般的に見られるように多数のビンにわたって画素値の分布が広がる場合、エンコーダ４０５は、ビデオブロック４３５に対してパレットモード符号化を使用しないと決定する。実施形態に応じて、パレットモード符号化を使用しないとの決定は、第１のビットグループヒストグラム４４０Ａが生成された後、第２のビットグループヒストグラム４４０Ｂが生成された後、又は、組み合わされたビットグループヒストグラム４４０Ｃが生成された後に行われてもよい。それらのヒストグラム４４０Ａ～４４０Ｃのうちの１つ以上の分析は、パレットモード符号化がビデオブロック４３５に対して適切であるかどうかを判定することができる。パレットモード符号化が使用されないケースでは、ビデオブロック４３５を符号化するために、様々な他のタイプの従来の符号化技術のうち何れかが使用されてもよい。

上述した処理は、ビデオフレームの全体又はその一部に対して実行されてもよいことに留意されたい。また、ビデオフレーム全体に対して生成されたパレットテーブルは、ビデオストリーム内の後続のビデオフレームを符号化するために使用されてもよい。また、別の実施形態では、ビデオブロック４３５は、画像のブロックであってもよいことに留意されたい。制御ロジック４１０をビニングコントローラ４１５、選択ユニット４２０及びパレットテーブル生成ユニット４２５に区画化することは、一実施形態を示すに過ぎないことに留意されたい。別の実施形態では、単一の制御ユニットは、ビニングコントローラ４１５、選択ユニット４２０及びパレットテーブル生成ユニット４２５の機能を実行してもよい。他の実施形態では、制御ロジック４１０を個別のユニットに区画化する他の方式が展開されてもよい。

一実施形態では、符号化されたブロック４５５は、符号化されたバージョンのパレットテーブル４５０と、パレットテーブル４５０にビデオブロック４３５の画素をマッピングするインデックス値を有するカラーインデックスマップと、を含む。パレットテーブル４５０は、ビデオブロック４３５の画素成分を符号化するための任意の数のパレットテーブルを表す。例えば、一実施形態では、パレットテーブル４５０は、赤成分についての第１のテーブルと、緑成分についての第２のテーブルと、青成分についての第３のテーブルと、を含む。別の実施形態では、パレットテーブル４５０は、異なる画素成分の組み合わせを表す単一のテーブルである。生成されたカラーインデックスマップは、任意の適切な符号化技術を使用して符号化されてもよい。例えば、個々のインデックス値は、一実施形態では、ランレングス符号化技術を使用して符号化される。個々のインデックス値を符号化する他の方式が可能であり、企図される。

図５を参照すると、所与のブロックについてのサンプルヒストグラム５００の一実施形態が示されている。ヒストグラム５００は、６４個の取り得る画素レベルに対応する６４個の異なるビンを有するヒストグラムの一例である。本明細書で使用される「ヒストグラム」という用語は、画像／フレームの所与のブロックについての各画素成分値の発生頻度として定義される。ブロックが、実施形態に応じて変化するコーディングユニットのサイズを有する、「コーディングユニット」としてより一般的に呼ばれ得ることに留意されたい。一実施形態では、コーディングユニットは、画素の８×８のブロックである。別の実施形態では、コーディングユニットは、画像／フレーム全体である。他の実施形態では、コーディングユニットは、画素の他のサイズ及び／又は配列であってもよい。説明のために、ヒストグラム５００の例示的な分布が示されている。Ｙ軸は、対応する画素レベルを有する所与のブロック内の画素数を測定する。この説明のために、所与のブロックが複数の画素を有し、各画素が１つ以上のチャネル（例えば、赤、緑、青）の各々についての数値を有することが想定される。

ヒストグラム５００を生成するために、６４個の個別のビンについての記憶が必要とされる。画素成分毎に他の数のビットを有する他のヒストグラムについて、取り得る画素レベル毎にヒストグラムを生成する場合に、他の数のビンが必要とされる。例えば、１０ビットの画素成分の場合、１０２４個の記憶ビンが必要である。１２ビットの画素成分の場合、４０９６個の記憶ビンが必要である。画素成分レベル（すなわち、画素ビット深度）毎のビットの数が増加するにつれて、記憶要件が指数関数的に増加する。しかしながら、本明細書で提示される技術により、高ビット深度ビデオについてのヒストグラムを生成するための記憶要件が実質的に低減する。

図６を参照すると、画素の所与のブロックについての間引きしたサンプルヒストグラム６００の一実施形態の図が示されている。図６の説明は、図５のヒストグラム５００の説明の続きである。ヒストグラム６００は、各ビンが複数の画素成分レベルを包含することを除いて、ヒストグラム５００に示す画素成分レベルにわたる画素の同一の分布を含む。したがって、ヒストグラム６００は、各画素のビットのサブセットのみを評価することによって、低減した数のビンを有する。

ヒストグラム６００に示すように、各矩形は、４個のビンの集合である中間ビンである。この例では、ヒストグラム６００は、画素成分値の４最上位ビット（ＭＳＢ）を評価する。４つのＭＳＢのみを使用することは、１６個のビンの合計に対応する。これは、６４個のビン（図５のヒストグラム５００の場合）の記憶要件を、ヒストグラム６００についての１６個のビンに低減させることをサポートする。他の実施形態では、第１のヒストグラムは、他の数のＭＳＢを評価してもよい。一実施形態では、第１のヒストグラム６００が、ＭＳＢに対して生成されているが、第２のヒストグラム（図示省略）が、ＬＳＢに対して生成される。

図７を参照すると、サンプルヒストグラムからの最上位の間引きした候補ビンの選択の一実施形態の図が示されている。図７の説明は、図６のヒストグラム６００の説明の続きである。ヒストグラム６００に示すような画素ＭＳＢのサブセットに基づいて候補ビンを生成した後に、最高画素総数を有する最上位の４個の候補ビンが選択される。それらの４個の選択された間引きした候補ビン７０５Ａ～７０５Ｄが、ヒストグラム７００内の棒グラフとして示されている。最上位の４個の間引きした候補ビン７０５Ａ～７０５Ｄの選択は、一実施形態を示しているに過ぎないことを理解されたい。他の実施形態では、別の数（例えば、２、８）の最上位の間引きした候補ビンが、間引きしたヒストグラムから選択されてもよい。一実施形態では、最上位の４個の間引きした候補ビン７０５Ａ～７０５Ｄが第１のヒストグラムに対して選択されると共に、最上位の４個の間引きした候補ビンが第２のヒストグラムに対して選択される。次に、２つのヒストグラムからのそれらの最上位ビンは、第３のヒストグラムを形成するよう組み合わされる。次いで、パレットテーブルを導出するために、第３のヒストグラムからの最上位ビンが選択及び使用される。

図８を参照すると、画素成分８００のビットの一実施形態の図が示されている。画素成分８００は、ソース画像又はビデオフレームの特定の色空間についての異なる色値の１つを記憶するための任意の数のビットを表す。例えば、一実施形態では、赤、緑及び青（ＲＧＢ）色空間内の画像についての画素毎の赤色値、緑色値及び青色値を符号化するために、画素成分８００の３つの個別のインスタンスが使用される。代わりに、別の実施形態では、画素成分８００の３つの別個のインスタンスは、（ＹＵＶ）色空間内の画素毎のルミナンス値及びクロミナンス値を記憶する。他の実施形態では、画素成分８００は、他のタイプの色空間内の画素の各画素成分値を符号化することができる。より一般的に、画素成分８００は、色空間へのインデックスと呼ばれてもよい。

一実施形態では、第１のヒストグラムは、画素成分８００のグループ１ビットを使用して、画像／フレームの画素ブロックに対して計算されると共に、画素成分８００のグループ２ビットを排除する。図示するように、グループ１ビットが６ビットを含むが、これは一実施形態を示しているに過ぎないことを理解されたい。最上位候補ビンは、実施形態に応じて変化して選択される最上位候補ビンの数により、第１のヒストグラムから選択される。第１のヒストグラムが計算されることと並列に、第２のヒストグラムは、画素成分８００のグループ２ビットを使用して、画素ブロックに対して計算されると共に、画素成分８００のグループ１ビットを排除する。図示するように、グループ２ビットが６ビットを含むが、これは一実施形態を示しているに過ぎないことを理解されたい。第１のヒストグラムと同じように、最上位候補ビンは、実施形態に応じて変化して選択される最上位候補ビンの数により、第２のヒストグラムから選択される。

次に、第３のヒストグラムは、第１のヒストグラム及び第２のヒストグラムの間に選択されたそれらの最上位候補ビンに対してのみであるが、画素成分８００のビットの全てを使用して計算される。第１のヒストグラムから選択された各ビンは、第３のヒストグラムのビンを生成するために、第２のヒストグラムからのビンと組み合わされる。第３のヒストグラムからの最上位ビンは、パレットテーブルを導出するために選択及び使用される。このパレットテーブルは、画像／ビデオブロックを符号化するために使用される。

図９を参照すると、メモリ効率的にパレットテーブルモード符号化を実行する方法９００の一実施形態が示されている。説明のために、この実施形態におけるステップ及び図１０～図１２のステップが順番に示されている。しかしながら、説明する方法の様々な実施形態では、説明する要素のうち１つ以上が同時に実行されてもよいし、図示した順序とは異なる順序で実行されてもよいし、完全に省略されてもよいことに留意されたい。必要に応じて他の追加の要素も実行される。本明細書で説明する様々なシステム又は装置の何れも、方法９００を実施するように構成されている。

エンコーダは、画像又はビデオフレームの画素のブロックの所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算する（ブロック９０５）。ブロック９０５を実施する方法の例は、図１０の方法１０００及び図１１の方法１１００において説明する。ブロック９０５を実施するための他の技術も採用されてもよい。次に、エンコーダは、複数のヒストグラムに基づいて、画素のブロックの所与の画素成分についての所与の数の最頻発生画素成分値を識別する（ブロック９１０）。次いで、エンコーダは、所与の数の最頻発生画素成分値からパレットテーブルを導出する（ブロック９１５）。次に、エンコーダは、パレットテーブルに基づいて、画素のブロックの所与の画素成分を符号化する（ブロック９２０）。ブロック９２０の後に、方法９００は終了する。方法９００が、画素のブロックの別の画素成分（例えば、ルミナンス、クロミナンス）毎に繰り返されてもよいことに留意されたい。方法９００は、画像／フレームの他のブロックに対し、及び、ビデオシーケンスの後続のビデオフレーム対して繰り返されてもよい。

図１０を参照すると、パレットテーブル生成のための複数のヒストグラムを計算する方法１０００の一実施形態が示されている。エンコーダは、画素のブロックの所与の画素成分の第１のビットのサブセットについての第１のヒストグラムを計算する（ブロック１００５）。一実施形態では、所与の画素成分は、赤画素成分、緑画素成分又は青画素成分であり、ブロックは、ＲＧＢ色空間において表される。別の実施形態では、所与の画素成分は、ルミナンス画素成分又はクロミナンス画素成分であり、ブロックは、ＹＣｂＣｒ色空間において表される。更なる実施形態では、所与の画素成分は、２つ以上の画素成分の組み合わせである。例えば、一実施形態では、所与の画素成分は、赤成分に対して８ビット、緑成分に対して８ビット、青成分に対して８ビットの２４ビット値である。他の実施形態では、所与の画素成分は、画素のブロックを表す他のタイプの値を記憶することができる。

エンコーダは、画素のブロックの所与の画素成分の第２のビットのサブセットについての第２のヒストグラムを計算し、第１のサブセットは、第２のサブセットとは重ならない（ブロック１０１０）。例えば、一実施形態では、各画素が１２ビット値で表される場合、第１のビットのサブセットは、１２ビット値の６最上位ビット（ＭＳＢ）であり、第２のビットのサブセットは、１２ビット値の６最下位ビット（ＬＳＢ）である。他の実施形態では、第１のサブセット及び第２のサブセットは、画素成分値の他の数のビットに対応してもよい。一実施形態では、ブロック１００５，１０１０は、並列に実行される。

次に、エンコーダは、第１のヒストグラムからの最高画素総数を有する第１のビンのセットを選択する（ブロック１０１５）。また、エンコーダは、第２のヒストグラムからの最高画素総数を有する第２のビンのセットを選択する（ブロック１０２０）。次いで、エンコーダは、第３のビンのセットについての第３のヒストグラムを計算し、第３のビンのセットの各ビンは、第１のビンのセットからの第１のビンに割り当てられたビットと、第２のビンのセットからの第２のビンに割り当てられたビットと、の連結に対応する（ブロック１０２５）。第３のビンのセットは、第１のビンのセットと第２のビンのセットの全ての取り得る組み合わせを含む。例えば、第１のビンのセットが８個のビンを含み、第２のビンのセットが８個のビンを含む場合、第３のビンのセットは、６４個のビンを含む。言い換えると、第１のビンのセットからの各ビンは、第３のビンのセットを生成するために、第２のビンのセットからの各ビンと連結される。次に、エンコーダは、第３のヒストグラムからの第３のビンのセットの中で最高画素総数を有する第４のビンのセットを選択する（ブロック１０３０）。第４のビンのセットに含まれるビンの数は、実施形態に応じて変化してもよい。次いで、エンコーダは、第４のビンのセットに割り当てられた画素成分値からパレットテーブルを導出する（ブロック１０３５）。次に、エンコーダは、パレットテーブルに基づいて、画素のブロックの所与の画素成分を符号化する（ブロック１０４０）。ブロック１０４０の後に、方法１０００は終了する。方法１０００が画像又はビデオフレームの画素のブロック毎に繰り返されてもよいことに留意されたい。

図１１を参照すると、パレットテーブル導出の一部としてヒストグラムを並列に生成する方法１１００の一実施形態が示されている。エンコーダは、画像又はビデオフレームのブロックに対してＭＳＢグループ及びＬＳＢグループに画素成分値ビットを分割する（ブロック１１０５）。ブロックがより一般的に「コーディングユニット」と呼ばれ得ることに留意されたい。コーディングユニットのサイズ（例えば、８×８のブロック）は、実施形態に応じて変化してもよい。別の実施形態では、コーディングユニットは、画像又はビデオフレーム全体である。他の実施形態では、コーディングユニットは、画像の様々な他の部分であり、又は、コーディングユニットは、複数の画像（例えば、ビデオシーケンスのビデオフレーム）に対応してもよい。

次に、エンコーダは、ＭＳＢグループについてのヒストグラムを計算すると共に（ブロック１１１０）、ＬＳＢグループについてのヒストグラムを並列に計算する（ブロック１１１５）。各ビンは、ビンに割り当てられたビットの部分に整合するそれらの画素成分値を含む。例えば、一実施形態では、画素成分値のビット幅は８であり、ＭＳＢ部分は４ビットであり、第１のビンにはビット「１１１１」が割り当てられ、第２のビンにはビット「１１１０」が割り当てられる等である。この実施形態では、「１１１１１１１１」、「１１１１１１１０」、「１１１１１１０１」、「１１１１１１００」、「１１１１１０１１」、「１１１１１０１０」、「１１１１１００１」、「１１１１１０００」、「１１１１０１１１」、「１１１１０１１０」、「１１１１０１０１」、「１１１１０１００」、「１１１１００１１」、「１１１１００１０」、「１１１１０００１」、「１１１１００００」の画素成分値が第１のビンに割り当てられる。また、「１１１０１１１１」、「１１１０１１１０」、「１１１０１１０１」、「１１１０１１００」、「１１１０１０１１」、「１１１０１０１０」、「１１１０１００１」、「１１１０１０００」、「１１１００１１１」、「１１１００１１０」、「１１１００１０１」、「１１１００１００」、「１１１０００１１」、「１１１０００１０」、「１１１００００１」、「１１１０００００」の画素成分値が第２のビンに割り当てられる。このパターンは、ＭＳＢグループヒストグラムの他のビンに対して続く。ＬＳＢグループの画素成分値は、同様の方法でＬＳＢグループヒストグラムのビンに割り当てられてもよい。

次いで、エンコーダは、ＭＳＢグループヒストグラムから最上位８個のビンを選択し（ブロック１１２０）、エンコーダは、ＬＳＢグループヒストグラムから最上位８個のビンを選択する（ブロック１１２５）。他の実施形態では、エンコーダは、ＭＳＢグループヒストグラム及びＬＳＢグループヒストグラムから他の数の最上位（すなわち、最高画素総数）ビンを選択してもよい。本明細書で使用される「ビン」という用語は、特定のビット割り当てに整合する画素成分値を有するコーディングユニットからの画素の集合として定義される。ＭＳＢグループヒストグラム及びＬＳＢグループヒストグラムについて、所与のビンについての各々の特定のビット割り当ては、画素成分値のビット幅未満であるいくつかのビットを含む。

ブロック１１２０，１１２５の後に、エンコーダは、６４個のビンの組み合わされたヒストグラムを形成するために、８個のＭＳＢビンと８個のＬＳＢビンとを組み合わせる（ブロック１１３０）。次に、エンコーダは、組み合わされたヒストグラムから最上位８個のビンを選択する（ブロック１１３５）。他の実施形態では、エンコーダは、組み合わされたヒストグラムから他の数の最上位ビンを選択する。次いで、エンコーダは、最上位８個のビンからパレットテーブルを導出する（ブロック１１４０）。ブロック１１４０の後に、方法１１００は終了する。

図１２を参照すると、パレットテーブルを使用してビデオ／画像ブロックを符号化する方法１２００の一実施形態が示されている。エンコーダは、並列ヒストグラム生成処理及び／又は階層ヒストグラム生成処理を使用して、ブロック内の所与の数の最頻発生画素成分値を識別する（ブロック１２０５）。ブロック内の所与の数の最頻発生画素成分値（すなわち、最高位色）を識別するために並列ヒストグラム生成処理及び／又は階層ヒストグラム生成処理を使用する異なる例は、方法１０００，１１００（図１０～１１の）において説明されている。それらの方法又は他の同様の方法は、ブロック１２０５を実施するために使用されてもよい。所与の数は、実施形態に応じて変化する値を有する任意の適切な整数値（例えば、８、１６、３２）であってもよい。

次に、エンコーダは、所与の数の最頻発生画素成分値に基づいて、パレットテーブルを選択する（ブロック１２１０）。一実施形態では、パレットテーブルは、３ビットによりテーブルへのインデックスが符号化されることを可能にする、７個の最頻発生画素成分値を含み、８番目のインデックスは、パレットテーブル内の何れの値にもマッピングしないエスケープ画素に対して使用される。他の実施形態では、パレットテーブルは、他の数の最頻発生画素成分値についての他の数のエントリを有する。一実施形態では、各画素成分（例えば、ルミナンス、クロミナンス）は、それ自身のパレットテーブルを有する。別の実施形態では、単一のパレットテーブルは、個別の画素成分の代表的な組み合わせとして生成される。更なる実施形態では、パレットテーブルは、単一の画素成分（例えば、赤）に対して生成され、次いで、他の画素成分（例えば、青、緑）と共有され、又は、他の画素成分により修正される。上記の代替例が可能であり、企図される。

次いで、パレットテーブル内のエントリに画素のブロックをマッピングするインデックス値によりカラーインデックスマップが生成される（ブロック１２１５）。例えば、一実施形態では、ブロック内の各画素は、ブロック内の画素毎のインデックスを含むカラーインデックスマップにより、パレットテーブルへのインデックスに変換される。画素がパレットテーブルに含まれない値を有する場合、画素は、エスケープ画素として符号化されてもよく、画素の実際の値は、カラーインデックスマップ又は個別の構造に含まれてもよい。次に、パレットテーブル及びカラーインデックスマップは、ブロックの表現として符号化される（ブロック１２２０）。パレットテーブルを符号化し、カラーインデックスマップを符号化するための様々な符号化技術の何れかが使用されてもよい。次いで、符号化されたパレットテーブル及びカラーインデックスマップは、記憶され、及び／又は、受信機に伝達される（ブロック１２２５）。ブロック１２２５の後に、方法１２００は終了する。方法１２００が単に画像／フレームのブロックではなく画像又はビデオフレームの全体を符号化するためにも使用され得ることを理解されたい。

符号化されたパレットテーブル及びカラーインデックスマップを受信機に送信することを含む実施形態について、受信機は、符号化されたパレットテーブル及びカラーインデックスマップからブロックを再生成するために、上記ステップを反転させるデコーダを含む。次に、再生成されたブロックは、ディスプレイに送られてもよい。一実施形態では、この処理は、ビデオシーケンスの各ビデオフレームのブロックに対して繰り返されてもよい。代わりに、符号化されたパレットテーブルは、第１のビデオフレーム全体に対して送信されてもよく、次いで、いくつかの数の後続のビデオフレームは、このパレットテーブルを再使用してもよい。後続のビデオフレームについて、ビデオフレームについてのカラーインデックスマップのみが受信機に送信される。更なる実施形態では、フレームのブロックに対して生成された符号化されたパレットテーブルは、フレームの他のブロック及び／又は他のフレームのブロックに対して再使用される。いくつかのケースでは、所与のブロックについてのパレットテーブルは、別のブロックに対応するパレットテーブルから駆動される。例えば、一実施形態では、所与のブロックについてのパレットテーブルを生成するために、隣接ブロックのパレットテーブルにデルタパレットテーブル（すなわち、差分パレットテーブル）が適用される。以前に使用されたパレットテーブルから新たなパレットテーブルを導出する他の方法が可能であり、企図される。

様々な実施形態では、ソフトウェアアプリケーションのプログラム命令を使用して、本明細書で説明する方法及び／又はメカニズムを実施する。例えば、汎用プロセッサ又は専用プロセッサによって実行可能なプログラム命令が考えられる。様々な実施形態では、そのようなプログラム命令は、高水準プログラミング言語によって表される。他の実施形態では、プログラム命令は、高水準プログラミング言語からバイナリ形式、中間形式又は他の形式にコンパイルされる。或いは、プログラム命令は、ハードウェアの動作又は設計を記述するように書き込まれる。そのようなプログラム命令は、Ｃ言語等の高水準プログラミング言語によって表される。或いは、Ｖｅｒｉｌｏｇ等のハードウェア設計言語（ＨＤＬ）が使用される。様々な実施形態では、プログラム命令は、様々な非一時的なコンピュータ可読記憶媒体の何れかに記憶される。記憶媒体は、プログラム実行のためにプログラム命令をコンピューティングシステムに提供するために、使用中にコンピューティングシステムによってアクセス可能である。一般的に、そのようなコンピューティングシステムは、少なくとも１つ以上のメモリと、プログラム命令を実行するように構成された１つ以上のプロセッサと、を含む。

上述した実施形態は、実施形態の非限定的な例示に過ぎないことを強調しておきたい。上記の開示が十分に理解されれば、多くの変形及び修正が当業者に明らかになる。以下の特許請求の範囲は、このような変形及び修正の全てを包含すると解釈されることが意図されている。

Claims (20)

1. メモリと、
   前記メモリに結合されたエンコーダと、を備え、
   前記エンコーダは、
   画素のブロックの所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算することであって、前記複数のヒストグラムは、前記所与の画素成分の第１のビットのサブセットについてのヒストグラムと、前記所与の画素成分の第２のビットのサブセットについてのヒストグラムと、を含む、ことと、
   前記複数のヒストグラムに基づいて、前記画素のブロックの前記所与の画素成分についての所与数の最頻発生値を識別することと、
   前記所与数の最頻発生値からパレットテーブルを導出することと、
   前記パレットテーブルに基づいて、前記画素のブロックの前記所与の画素成分を符号化することと、
   を行うように構成されている、
   システム。
2. 前記画素のブロックの前記所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算することは、
   前記画素のブロックの前記所与の画素成分の前記第１のビットのサブセットについての第１のヒストグラムを計算することと、
   前記画素のブロックの前記所与の画素成分の前記第２のビットのサブセットについての第２のヒストグラムを計算することであって、前記第１のビットのサブセットは、前記第２のビットのサブセットと重ならない、ことと、を含む、
   請求項１のシステム。
3. 前記複数のヒストグラムに基づいて、前記画素のブロックの前記所与の画素成分についての所与数の最頻発生値を識別することは、
   前記第１のヒストグラムから最高画素総数を有する第１のビンのセットを選択し、前記第２のヒストグラムから最高画素総数を有する第２のビンのセットを選択することと、
   第３のビンのセットについての第３のヒストグラムを計算することであって、前記第３のビンのセットの各ビンは、前記第１のビンのセットからの第１のビンに割り当てられたビットと、前記第２のビンのセットからの第２のビンに割り当てられたビットとの連結に対応しており、前記連結は、前記第２のビンのビットを前記第１のビンのビットに付加することを含む、ことと、
   前記第３のビンのセットのうち最高画素総数を有する第４のビンのセットを選択することであって、前記第４のビンのセットに割り当てられた画素成分値は、前記画素のブロックの前記所与の画素成分についての前記所与数の最頻発生値である、ことと、を含む、
   請求項２のシステム。
4. 前記第１のビットのサブセット及び前記第２のビットのサブセットの組み合わせは、前記所与の画素成分の全体を含む、
   請求項１のシステム。
5. 前記所与の画素成分は、Ｎビットを有し、
   前記第１のビットのサブセットは、前記所与の画素成分のＮ／２最上位ビットを含み、
   前記第２のビットのサブセットは、前記所与の画素成分のＮ／２最下位ビットを含み、
   Ｎは、正の偶数の整数である、
   請求項１のシステム。
6. 前記所与の画素成分は、赤画素成分、緑画素成分又は青画素成分であり、
   前記ブロックは、画素又はビデオフレームの一部である、
   請求項１のシステム。
7. 前記所与の画素成分は、ルミナンス画素成分又はクロミナンス画素成分であり、
   前記ブロックは、画素又はビデオフレームの一部である、
   請求項１のシステム。
8. エンコーダが、画素のブロックの所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算することであって、前記複数のヒストグラムは、前記所与の画素成分の第１のビットのサブセットについてのヒストグラムと、前記所与の画素成分の第２のビットのサブセットについてのヒストグラムと、を含む、ことと、
   前記複数のヒストグラムに基づいて、前記画素のブロックの前記所与の画素成分についての所与数の最頻発生値を識別することと、
   前記所与数の最頻発生値からパレットテーブルを導出することと、
   前記パレットテーブルに基づいて、前記画素のブロックの前記所与の画素成分を符号化することと、を含む、
   方法。
9. 前記画素のブロックの前記所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算することは、
   前記画素のブロックの前記所与の画素成分の前記第１のビットのサブセットについての第１のヒストグラムを計算することと、
   前記画素のブロックの前記所与の画素成分の前記第２のビットのサブセットについての第２のヒストグラムを計算することであって、前記第１のビットのサブセットは、前記第２のビットのサブセットと重ならない、ことと、を含む、
   請求項８の方法。
10. 前記複数のヒストグラムに基づいて、前記画素のブロックの前記所与の画素成分についての所与数の最頻発生値を識別することは、
    前記第１のヒストグラムから最高画素総数を有する第１のビンのセットを選択し、前記第２のヒストグラムから最高画素総数を有する第２のビンのセットを選択することと、
    第３のビンのセットについての第３のヒストグラムを計算することであって、前記第３のビンのセットの各ビンは、前記第１のビンのセットからの第１のビンに割り当てられたビットと、前記第２のビンのセットからの第２のビンに割り当てられたビットとの連結に対応しており、前記連結は、前記第２のビンのビットを前記第１のビンのビットに付加することを含む、ことと、
    前記第３のビンのセットのうち最高画素総数を有する第４のビンのセットを選択することであって、前記第４のビンのセットに割り当てられた画素成分値は、前記画素のブロックの前記所与の画素成分についての前記所与数の最頻発生値である、ことと、を含む、
    請求項９の方法。
11. 前記第１のビットのサブセット及び前記第２のビットのサブセットの組み合わせは、前記所与の画素成分の全体を含む、
    請求項８の方法。
12. 前記所与の画素成分は、Ｎビットを有し、
    前記第１のビットのサブセットは、前記所与の画素成分のＮ／２最上位ビットを含み、
    前記第２のビットのサブセットは、前記所与の画素成分のＮ／２最下位ビットを含み、
    Ｎは、正の偶数の整数である、
    請求項８の方法。
13. 前記所与の画素成分は、赤画素成分、緑画素成分又は青画素成分であり、
    前記ブロックは、画素又はビデオフレームの一部である、
    請求項８の方法。
14. 前記所与の画素成分は、ルミナンス画素成分又はクロミナンス画素成分であり、
    前記ブロックは、画素又はビデオフレームの一部である、
    請求項８の方法。
15. 画素のブロック及びプログラム命令を記憶するメモリと、
    前記メモリに結合されたプロセッサと、を備え、
    前記プログラム命令は、
    画素のブロックの所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算することであって、前記複数のヒストグラムは、前記所与の画素成分の第１のビットのサブセットについてのヒストグラムと、前記所与の画素成分の第２のビットのサブセットについてのヒストグラムと、を含む、ことと、
    前記複数のヒストグラムに基づいて、前記画素のブロックの前記所与の画素成分についての所与数の最頻発生値を識別することと、
    前記所与数の最頻発生値からパレットテーブルを導出することと、
    前記パレットテーブルに基づいて、前記画素のブロックの前記所与の画素成分を符号化することと、
    を前記プロセッサに実行させる、
    装置。
16. 前記画素のブロックの前記所与の画素成分の異なるビットのサブセットについての複数のヒストグラムを計算することは、
    前記画素のブロックの前記所与の画素成分の前記第１のビットのサブセットについての第１のヒストグラムを計算することと、
    前記画素のブロックの前記所与の画素成分の前記第２のビットのサブセットについての第２のヒストグラムを計算することであって、前記第１のビットのサブセットは、前記第２のビットのサブセットと重ならない、ことと、を含む、
    請求項１５の装置。
17. 前記複数のヒストグラムに基づいて、前記画素のブロックの前記所与の画素成分についての所与数の最頻発生値を識別することは、
    前記第１のヒストグラムから最高画素総数を有する第１のビンのセットを選択し、前記第２のヒストグラムから最高画素総数を有する第２のビンのセットを選択することと、
    第３のビンのセットについての第３のヒストグラムを計算することであって、前記第３のビンのセットの各ビンは、前記第１のビンのセットからの第１のビンに割り当てられたビットと、前記第２のビンのセットからの第２のビンに割り当てられたビットとの連結に対応しており、前記連結は、前記第２のビンのビットを前記第１のビンのビットに付加することを含む、ことと、
    前記第３のビンのセットのうち最高画素総数を有する第４のビンのセットを選択することであって、前記第４のビンのセットに割り当てられた画素成分値は、前記画素のブロックの前記所与の画素成分についての前記所与数の最頻発生値である、ことと、を含む、
    請求項１６の装置。
18. 前記第１のビットのサブセット及び前記第２のビットのサブセットの組み合わせは、前記所与の画素成分の全体を含む、
    請求項１５の装置。
19. 前記所与の画素成分は、Ｎビットを有し、
    前記第１のビットのサブセットは、前記所与の画素成分のＮ／２最上位ビットを含み、
    前記第２のビットのサブセットは、前記所与の画素成分のＮ／２最下位ビットを含み、
    Ｎは、正の偶数の整数である、
    請求項１５の装置。
20. 前記所与の画素成分は、赤画素成分、緑画素成分又は青画素成分であり、
    前記ブロックは、画素又はビデオフレームの一部である、
    請求項１５の装置。

Images