JPEGアプリケーションにおける可変長符号の復号
【課題】JPEG画像ファイルにおけるハフマン符号を復号する手法を提供する。
【解決手段】ビットストリームサンプルは、ハフマングループ番号を特定するために閾値と比較される。ハフマングループに関連付けられた情報が取り出され、ビットストリームから現在のハフマンシンボルを抽出するために使用される。次いで、対応するシンボル値を、現在のハフマンシンボル及びグループ情報を使用して取得することができる。
【解決手段】ビットストリームサンプルは、ハフマングループ番号を特定するために閾値と比較される。ハフマングループに関連付けられた情報が取り出され、ビットストリームから現在のハフマンシンボルを抽出するために使用される。次いで、対応するシンボル値を、現在のハフマンシンボル及びグループ情報を使用して取得することができる。
【発明の詳細な説明】
【発明の分野】
【0001】
[0001]本発明の実施形態は、JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルで使用される可変長符号(VLC)の復号に関するものである。
【関連技術の説明】
【0002】
[0002]コンピューティングアプリケーションでは、可変長符号化(VLC)の符号化方式によって可逆的データ圧縮が可能となっている。一般に、VLC符号化方式は、確率論的手法を利用する。この手法では、より頻度の大きいシンボルを表現するために必要なビット数が、より頻度の低いシンボルを表現するために必要なビット数より少なくて済む。VLC符号化は、コンピューティングにおいて広く用いられており、特に、非圧縮情報がその圧縮情報よりもはるかに大きい記憶空間を必要とする画像、音楽、ビデオ等のようなメディアアプリケーションにおいて使用されている。
【0003】
[0003]VLC符号化方式の一つにハフマン符号化がある。ハフマン符号化は、データを圧縮する極めて有効な手段であり、特に、ソースマテリアル内の値の出現を利用して、ハフマン木における各シンボル値がどこに出現するべきかを決定することにより、圧縮すべきアイテムが、対応するハフマン木の生成を支援するように使用される場合に有効である。ハフマン符号化はまた、接頭符号と呼ばれることもあるプレフィックスフリー符号(語頭符号)を生成すること、即ち、ハフマン木によって生成されるシンボルは、そのハフマン木によって生成される他の如何なるシンボルの接頭部に対応しないという利点がある。
【0004】
[0004]ハフマン符号化は、様々なメディアアプリケーションで広く用いられており、特に、JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイル形式において用いられている。ハフマン符号化は全てのJPEGで使用されるので、各JPEGビューワは、画像を圧縮解除するためにハフマン符号化の処理をする必要がある。JPEGビューワがハフマン符号化をより効率的に処理できると、符号化処理がより速くなる。
【0005】
[0005]JPEG規格では、各画像に対して異なるハフマンテーブルを準備することができる。画像における全値の出現頻度を決定し、それら頻度を使用して、その画像の固有のハフマンテーブルを生成する。したがって、ビューワがJPEG画像を復号するために、ハフマンテーブルの再構成に必要な情報が、ファイルそれ自体にファイルヘッダとして含まれる。
【発明の概要】
【0006】
[0006]JPEG画像におけるハフマンシンボルを復号する手法について説明する。一つの手法は、JPEG画像ファイルにおけるハフマン符号を復号する方法に関するものである。この方法は、JPEG画像ファイルに関連付けられたビットストリームからビットストリームサンプルを取得することを含む。ビットストリームサンプルは、ハフマングループ番号を特定するために閾値と比較される。ハフマングループに関連付けられた情報が取り出され、ビットストリームから現在のハフマンシンボルを抽出するために使用される。次いで、対応するシンボル値を、現在のハフマンシンボル及びグループ情報を使用して取得することができる。
【0007】
[0007]JPEGファイルにおけるハフマン符号を復号するためのシステムを使用する別の手法についても説明する。このシステムは、JPEG画像ファイルに対するオペレーション(走査を実行するための制御モジュールを含む。ハフマンテーブル生成器が、JPEG画像ファイルに含まれる情報から基本テーブル及び二次テーブルを生成するために使用される。次いで、ビットストリームバッファを使用して、JPEG画像ファイルに含まれる画像データからデータ抜粋を格納することができ、複数の閾値比較器を使用して、現在のハフマンシンボルに対応するハフマングループを特定する。制御モジュールは、ハフマングループに関連付けられたグループ情報を取得し、このグループ情報を使用して、現在のハフマンシンボルに対応するシンボル値を取得することができる。
【0008】
[0008]更に他の手法として、JPEG画像ファイルにおけるハフマン可変長符号を復号する方法を述べる。この方法は、JPEG画像ファイルに関連付けられたビットストリームから16ビットをスキャンしてビットストリームバッファ内に取り込むことを含む。現在のハフマンシンボルに対応するハフマングループが特定され、このハフマングループに関連付けられたグループ情報が基本テーブルから取り出される。このグループ情報を参照して、現在のハフマンシンボルのシンボル値が二次テーブルから取得される。
【0009】
[0009]添付の図面は、本明細書に組み込まれその一部となるものであり、本発明の実施形態を示しており、本明細書の説明と共に本発明の原理を説明する役目を果たしている。
【発明を実施するための最良の形態】
【0010】
[0019]ここで、本発明の幾つかの実施形態を詳細に示す。代替的な実施形態と共に本発明を説明するが、本発明がこれらの実施形態に限定されるものではないことは理解されよう。それどころか、本発明は、添付の特許請求の範囲で定義される本発明の趣旨及び範囲に含まれうる代替形態、修正形態、及び均等物を含むものである。
【0011】
[0020]さらに、以下の詳細な説明においては、特許請求の範囲に記載された主題の完全な理解のために多数の具体的な細部を示す。しかしながら、これら特定の細部又はそれらの均等物なしに実施形態が実施され得ることが当業者には認識されよう。他の例では、周知の方法、手順、構成要素、及び回路については詳細には述べていないが、これは、本発明の主題の態様及び特徴を不必要に分かりにくくしないためである。
【0012】
[0021]以下の詳細な説明の幾つかの部分を、方法の観点で提示して論じる。この方法の動作を説明する添付の図面(例えば、図5)には、そのステップ及びシーケンスが開示されているが、このようなステップ及びシーケンスは例示的なものである。実施形態は、添付の図面のフローチャートに記載されるステップの変形形態や他の様々なステップ、並びに本明細書に記載される以外のシーケンスにおける様々なステップを実施するのにも適する。
【0013】
[0022]詳細な説明の幾つかの部分は、手順、ステップ、論理ブロック、処理、及び、コンピュータメモリ上で実行されうるデータビットに対する操作の他の記号表現として提示される。これらの記述及び表現は、データ処理技術の当業者がその作業の内容を最も効果的に他のデータ処理技術の当業者に伝えるために使用する手段である。手順、コンピュータ実行ステップ、論理ブロック、及びプロセス等は、本明細書においても、また一般的にも、望ましい結果を導く一連の首尾一貫したステップ又は命令として考えられる。これらのステップは、物理量の物理的操作を要するステップである。必須ではないが通常は、これらの量は、コンピュータシステムにおいて格納、転送、結合、比較、及び他の操作がなされ得る電気又は磁気信号の形態をとる。これらの信号を、主に一般的な用法であるという理由で、ビット、値、要素、シンボル、文字、項、又は番号などとして呼ぶことが時として好都合であることが分かっている。
【0014】
[0023]しかし、上記及び類似の用語の全ては、該当する物理量に関連付けられるべきであり、これらの物理量に適用される便利なラベルに過ぎないことに留意する必要がある。以下の説明において明らかなように、特にことわりがない限り、「アクセス」、「書き込み」、「含有」、「格納」、「送信」、「トラバース」、「関連付け」、「識別」などの用語を使用する説明は、全体を通して、コンピュータシステム又は類似の電子計算デバイスの動作及びプロセスを指していることを理解されたい。それらは、コンピュータシステムのレジスタ及びメモリにおける物理量(電子的量)として表現されるデータを操作して、同様にコンピュータシステムのメモリ又はレジスタ、或いは他のそうした情報記憶装置、伝送装置、又は表示装置における物理量として表現される他のデータに変形するものである。
【0015】
[0024]計算デバイスは通常、少なくとも何らかの形態のコンピュータ可読媒体を含む。コンピュータ可読媒体は、計算デバイスによってアクセスできる任意の利用可能な媒体とすることができる。コンピュータ可読媒体としては、限定するものではないが、例として、コンピュータ記憶媒体及び通信媒体がある。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、また他のデータ等の情報を格納するための任意の方法又は技術で実装された揮発性及び不揮発性のリムーバブル及び非リムーバブルの媒体を含む。コンピュータ記憶媒体は、以下に限定されないが、RAM、ROM、EEPROM、フラッシュメモリ、又は他のメモリ技術、或いは、CD−ROM、DVD(デジタル多用途ディスク)、又は他の光ストレージ、或いは、磁気カセット、磁気テープ、磁気ディスクストレージ、又は他の磁気記憶装置、或いは、所望の情報を格納するために使用することができコンピューティングデバイスによってアクセスすることができる他の任意の媒体を含む。通信媒体は、通常、搬送波又は他の移送メカニズムなどの変調されたデータ信号としてコンピュータ可読命令、データ構造、プログラムモジュール、又は他のデータを具体化し、また任意の情報送達媒体を含む。用語「変調されたデータ信号」は、信号内で情報を符号化するように一つ又は複数の信号特性が設定又は変更された信号を意味する。通信媒体には、限定ではなく例として、有線ネットワーク又は直接配線接続などの有線媒体、並びに、音響、RF、赤外線、及び他の無線媒体などの無線媒体が含まれる。上記の任意の組合せも、コンピュータ可読媒体の範囲に含まれるものとする。
【0016】
[0025]幾つかの実施形態は、一以上のコンピュータ又は他の装置で実行されるプログラムモジュール等のコンピュータ実行可能命令の一般的コンテキストにおいて記述することができる。一般に、プログラムモジュールには、特定のタスクを実行する又は特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、及びデータ構造などが含まれる。通常、プログラムモジュールの機能は、様々な実施形態で所望に応じて組み合わせたり分散させることができる。
【0017】
[0026]本明細書で説明する実施形態では、コンピュータシステムにおける別個のコンポーネントCPU及びGPUを参照することがあるが、CPUとGPUは単一の装置に統合することができ、命令ロジック、バッファ、及び機能ユニット等の様々なリソースをCPUとGPUが共用してもよく、又は、別々のリソースをグラフィックスオペレーションと汎用オペレーションに提供してもよいことが、当業者には認識されよう。したがって、本明細書でGPUに関連するように説明される回路及び/又は機能の何れか又は全てを、適宜に構成したCPUにて実施及び実行することも可能である。
【0018】
[0027]また、本明細書で説明する実施形態ではGPUを参照することがあるが、本明細書に記載の回路及び/又は機能は、汎用プロセッサ又は他の専用コプロセッサのような他のタイプのプロセッサ、或いはCPU内に実装され得ることを理解されたい。
【0019】
<基本計算システム>
[0028]まず図1を参照する。同図は、例示的なコンピュータシステム112のブロック図を示している。本明細書に記載のコンピュータシステム112は、実施形態を好適に実施し得る動作プラットフォームの例示的構成を示していることを理解されたい。しかしながら、異なる構成を有する他のコンピュータシステムを、コンピュータシステム112の代わりに、本発明の範囲内で使用することもできる。即ち、コンピュータシステム112は、図1に関連して説明する要素以外の要素を含むことができる。更に、実施形態は、コンピュータシステム112のようなコンピュータシステムだけでなく、実施形態を実施可能にするように構成できる任意のシステム上で実施されうる。実施形態は、異なる多くのタイプのコンピュータシステム112上で実施され得ることを理解されたい。システム112は、例えば、専用グラッフィックスレンダリングGPUに連結された強力な汎用CPUを有するデスクトップコンピュータ又はサーバコンピュータシステムとして実施することができる。このような実施形態では、周辺機器バス、専用オーディオ/ビデオコンポーネント、及び入出力装置等を追加するコンポーネントを含むことができる。
【0020】
[0029]同様に、システム112は、携帯端末(例えば、携帯電話など)、或いは、例えば、ワシントン州レドモンドのマクロソフト社から入手可能なXbox(登録商標)や日本の東京のソニー・コンピュータエンタテインメント社から入手可能なPLAYSTATION3(登録商標)のようなセットトップビデオゲーム機として実施可能である。また、システム112は、計算デバイスの電子装置(例えば、コンポーネント101、103、105、106等)が単一の集積回路チップ内に完全に含まれる「システムオンチップ」として実施することもできる。例としては、ディスプレイ、カーナビゲーションシステム、携帯エンターテイメントシステム等を有する携帯装置等がある。
【0021】
[0030]コンピュータシステム112は、情報を伝達するためのアドレス/データバス100と、バス100と結合されており情報及び命令を処理するための中央処理装置101と、バス100と結合されており中央処理装置101に対する情報及び命令を格納するための揮発性メモリ装置102(例えば、RAM(ランダムアクセスメモリ)、スタティックRAM、ダイナミックRAM等)と、バス100と結合されており処理装置101に対する静的な情報及び命令を格納するための不揮発性メモリ装置103(例えば、ROM(読取り専用メモリ)、プログラマブルROM、フラッシュメモリ等)と、を備える。更に、コンピュータシステム112はまた、情報及び命令を格納するためのデータ記憶装置104(例えば、ハードディスクドライブ)を備える。
【0022】
[0031]コンピュータシステム112はまた、オプションのグラッフィックスサブシステム105と、オプションの英数字入力装置106と、オプションのカーソル制御又は指示装置107と、信号通信インターフェース(入出力装置)108と、を備える。オプションの英数字入力装置106は、情報及びコマンド選択を中央処理装置101に伝達することができる。オプションのカーソル制御又は指示装置107は、ユーザ入力情報及びコマンド選択を中央処理装置101に伝達するためにバス100に結合されている。信号通信インターフェース(入出力装置)108は、シリアルポートとすることができ、バス100にやはり結合されている。また、通信インターフェース108は、無線通信メカニズムを含むことができる。通信インターフェース108を使用して、コンピュータシステム112は、インターネット又はイントラネット(例えば、ローカルエリアネットワーク)のような通信ネットワークを介して他のコンピュータシステムに通信可能に結合することができ、或いは、データ(例えば、デジタルテレビ信号)を受け取ることができる。コンピュータシステム112はまた、例えば、ビデオケーブル111によって接続された付属の表示装置110上に情報を表示することによってコンピュータユーザに情報を提示するグラッフィックスサブシステム105を備えることもできる。ある実施形態では、グラッフィックスサブシステム105は、中央処理装置101内に組み込まれる。別の実施形態では、グラッフィックスサブシステム105は、分離した別個のコンポーネントである。別の実施形態では、グラッフィックスサブシステム105は、別のコンポーネントに組み込まれる。別の実施形態では、グラッフィックスサブシステム105は、他の態様でシステム112に含まれる。
【0023】
[0032]<JPEGアプリケーションにおける効率的なVLC処理>
【0024】
[0033]以下の実施形態では、JPEG画像表示アプリケーションにおける可変長符号化(VLC)、特にハフマン符号化を効率的に処理するための手法を説明する。一実施形態では、JPEG画像におけるハフマン符号を処理するための方法が、JPEGビットストリームからVLCシンボルを効率的に抽出し、VLCシンボルをそれに対応するシンボル値と突き合わせることを含む。
【0025】
[0034]本明細書に記載する幾つかの実施形態では、JPEGファイル形式の幾つかの特徴及びそれに対応するハフマンテーブルの使用法を活用する。第1に、JPEGに対して許容されるハフマン符号の最大長は、16ビットである。第2に、JPEG画像と共に使用される各ハフマンテーブルは、16個のハフマングループを定義する。グループは各グループ内のシンボルの長さによって定義される。例えば、第1のグループは、1ビット長のシンボルからなり、第2のグループは、2ビット長のシンボルからなり、以下同様に、長さが16ビットのシンボルからなる第16のグループまで定義される。第3に、前述したように、ハフマン符号はプレフィックスフリー符号である。第4に、各ハフマングループ内で、符号値は、連続している。上記の特徴を活用することにより、ハフマン符号化の処理のための効率的な手法が可能となる。
【0026】
<例示的ハフマン符号>
[0035]JPEG規格では、各画像がそれ自体の固有の計算されたハフマンテーブルを有することが可能であるが、幾つかの「典型的」テーブルがJPEG委員会によって提供されている。そのような典型的なテーブルの一つは、下記の表1の配列によって指定されるDC輝度(DCluminance)テーブルである。
【表1】
【0027】
[0036]第1の配列dc_luminance bits[]は、JPEGによって使用される16個の各ハフマングループ内に幾つのシンボルが存在するかを示すことによって、ハフマン符号が対応するテーブル内にどのように割り当てられるかを指定する。このテーブルでは、2ビット長から9ビット長のシンボルに対応するグループ2〜9のみがエントリを有する。3ビット長のシンボルからなるグループ3は、5個のシンボルを有し、残りのグループは、それぞれ1個のシンボルを有する。グループ1及びグループ10〜16は、それぞれ、エントリがゼロとして定義されている。
【0028】
[0037]第2の配列dc_luminance_val[]は、シンボルに関連付けられる値をそれらが割り当てられる順序で示している。このテーブルでは、0が第1のシンボルに関連付けられ、1が第2のシンボルに関連付けられ、以下同様に行われる。
【0029】
[0038]次に図2を参照する。同図は、例示的なハフマンテーブル200を示している。ハフマンテーブル200は、図示のように、表1で定義されたDC輝度テーブルに対応している。左の列は、dc_luminance bits[]配列によって指定されたハフマンシンボル、即ち、シンボル201、203、205、207、209、211、213、215、217、219、221、及び223からなる。右の列は、dc_luminance_val[]配列によってシンボルに関連付けられた値、即ち、シンボル値202、204、206、208、210、212、214、216、218、220、222、及び224からなる。前述したように、ハフマン符号は、プレフィックスフリー符号であり、図2に示すようにそれらを左揃えに示すと、他のシンボルの接頭部と同一のシンボルが存在しない、例えば、シンボル201は00であり、他には00で始まるシンボルがないことが容易に分かる。
【0030】
<JPEGファイル形式>
[0039]次に図3を参照する。同図は、一実施形態に係るJPEG画像ファイル300を示している。図示するように、JPEG画像ファイル300は、ヘッダ310と画像データ320の二つの部分からなる。ヘッダ310は、JPEG画像ファイル300に含まれる画像を復号するために必要な情報を含み、一方、画像データ320は、実際の圧縮画像データを含んでいる。例えば、ヘッダ310は、JPEG画像ファイル300をJPEG画像ファイルとして識別する最初のシーケンスと、表1に示す配列のようなJPEG画像ファイル300に関するハフマンテーブル情報を含む部分とを含むことができる。
【0031】
[0040]図示するように、画像データ320は、圧縮シンボルデータのビットストリームからなる。このビットストリームデータの例示的な抜粋を、ビットストリーム抜粋325として示す。図示の実施形態におけるビットストリーム抜粋325は、一続きの幾つかのVLCシンボル、例えば、シンボル331、333、及び335から構成される。シンボルが可変長であるので、JPEGビューワは、それぞれの完全なシンボルを、長さにかかわらず認識する必要がある。
【0032】
<従来の手法>
[0041]JPEG画像ファイルにおけるハフマン符号を処理するための一般的な従来技術の手法は、幾つかのビット(多くの場合、3ビット)をビットストリームから読み取り、それらのビットをメモリに格納されたテーブルと比較することを含む。それらビットが完全なシンボルを構成する場合、テーブルはそのことを指し示し、そのシンボルに関連付けられた値を提供する。それらのビットが完全なシンボルでない場合、テーブルはやはりそのことを指し示し、また別のテーブルへの参照を含める。ビットストリームから更なるビットが読み取られ、第2のテーブルが参照され、同様の結果が生じ得る。この繰り返しのループサイクルは、最も些細な事例を除いてほとんどの場合、処理時間、繰り返しメモリアクセス、及び、複数のテーブルを格納するメモリの利用法の観点から非効率である。
【0033】
<基本テーブルと二次テーブル>
[0042]以下の実施形態では、より効率的なJPEG画像のハフマン復号のための手法を説明する。この手法の特徴の一つは、メモリテーブルの利用法を限定することにより、より効率的にメモリを利用することである。最も些細な事例を除いてほとんどの場合、基本及び二次テーブルの使用により、メモリの利用法の点で大幅な改善が見られる。
【0034】
[0043]以下、図4を参照する。同図は、一実施形態に係る基本テーブル400を示している。基本テーブル400は、上記で表1に示したDC輝度の「典型的」テーブル情報から導かれる。基本テーブル400は、JPEG規格によって定義される16個のハフマングループに対応する16個のグループに分割される。各グループは、以下の三つの情報、即ち、個々のグループにおけるエントリのビットの長さに対応するnビットと、図示の実施形態にではそのグループ内のエントリの最小値に対応する閾値と、そのグループ内のエントリのシンボル値が格納される第2のテーブルにおける位置を指すメモリポインタであるオフセットと、を含む。前述のように、グループ2〜9のみが、DC輝度の典型的テーブルにおいてエントリを有する。
【0035】
[0044]基本テーブル400内に示される閾値は、閾値を16ビット長まで埋めるために、ゼロで「パディング」されている。幾つかの実施形態では、後により詳細に述べるように、閾値は、同じ長さであり、例えば、とり得る最長のハフマン符号と同じ長さであることが好都合である。
【0036】
[0045]次に、図5を参照する。同図は、一実施形態に係る二次テーブル500を示している。図示の実施形態において、二次テーブル500は、上記で表1に示したDC輝度の「典型的」テーブル情報から導かれる。二次テーブル500は、JPEGビットストリームに符号化されたハフマンシンボルに対応するシンボル値のリストである。幾つかの実施形態では、これらの値は、オフセット値とインデックスの組合せにより任意の特定のエントリを取り出すことができるようにメモリに順次格納される。例えば、図示のように二次テーブル500がメモリアドレス<Table 2 Address>から始まる場合、オフセットとしての<Table 2 Address>と、インデックスとしての<2*value_length>(value_lengthは、二次テーブルにおけるエントリのバイト長に対応する)とを使用して、二次テーブル500に格納された第3のシンボル値を取り出す。
【0037】
<JPEG画像のハフマン値の復号>
[0046]以下、図6を参照する。同図は、一実施形態に係る、JPEG画像ファイルにおけるハフマン符号を復号する方法のフローチャート600を示している。フローチャート600で具体的なステップを開示するが、これらのステップは例示的なものである。即ち、本発明の実施形態は、様々な他の(追加の)ステップ又はフローチャート600に記載のステップの変形形態を実施するのにも適する。フローチャート600のステップは、与えられた順序と異なる順序で行われてもよく、フローチャート600のステップの全てが行われなくてもよいことを理解されたい。
【0038】
[0047]図示するように、ステップ610は、ビットストリームから16ビットをスキャンすることを含む。この実施形態では、VLC符号の可能な最大の長さは、16ビットである。したがって、この単一のスキャン動作により、ビットストリームから完全なシンボルが確実に取り出される。幾つかの実施形態では、これらのビットは、ビットストリームバッファ内に収納される。
【0039】
[0048]図示の実施形態におけるステップ620は、ビットストリームバッファにおける第1のシンボルについて該当するハフマングループを決定することを含む。前述のように、ハフマン符号は、プレフィックスフリー符号である。したがって、ある特定のハフマンシンボルが属するグループを特定することにより、そのシンボルのビット長も示される。ある手法では、ビットストリームバッファは、16個の異なる閾値と比較される。これら16個の閾値は、JPEG符号化で使用される16個の候補のハフマングループの何れかとそれぞれ関連付けられている。この比較は、並列に非常に迅速に行うことが可能であり、この比較により、適切なグループが決定されて、シンボルそれ自体が容易に決定される。
【0040】
[0049]次にステップ630に示すように、基本テーブルにアクセスし、シンボル情報を取り出す。幾つかの実施形態では、ハフマンシンボルを復号する際に二つのテーブルが利用される。第1のテーブル、即ち、基本テーブルは、JPEG符号化で使用される16個のハフマングループに関する情報を含む。そのような一実施形態では、16個のグループのそれぞれについて「ベーストリプレット(basetriplet)」が使用される。このトリプレットは、そのグループ内のエントリの長さ(例えば、ビット数での長さ)と、ステップ620で行われる比較のために使用することができるそのグループについての閾値と、そのグループでのエントリが開始しうる第2のメモリテーブルの部分を指し示すメモリオフセットと、を含む。第2のテーブルは、ビットストリームに符号化された様々なハフマンシンボルに対するシンボル値を含む。
【0041】
[0050]次にステップ640に示すように、対応するシンボル値を取り出す。幾つかの実施形態では、基本テーブルが、二次テーブルにアクセスするための適切なオフセット情報を提供する。次いで、シンボルそれ自体を使用してインデックスを提供することができ、オフセットと組み合わせたインデックスにより、二次テーブルにおける特定のシンボル値をその位置から取り出すことが可能になる。
【0042】
[0051]次に図7を参照する。同図は、一実施形態に係る、可変長符号(VLC)シンボルを復号する方法のフローチャート700を示している。フローチャート700に具体的なステップを開示するが、これらのステップは例示的なものである。即ち、本発明の実施形態は、様々な他の(追加の)ステップ又はフローチャート700に記載のステップの変形形態を実施するのにも適する。フローチャート700のステップは、与えられた順序と異なる順序で行われてもよく、そのステップの全てが行われなくてもよいことを理解されたい。
【0043】
[0052]ステップ710に示すように、符号化の際に使用されるVLCグループについての閾値情報を取り出す。幾つかの実施形態では、この閾値情報は、図4を参照して上記で説明したような基本テーブルから取得される。幾つかの実施形態では、ある所与のグループについての閾値情報は、そのグループ内のエントリの最小値からなる。更に、幾つかの実施形態では、全ての閾値が等しい長さになるように、特定のグループの閾値に対し「充填」、即ち「パディング」がなされ得る。
【0044】
[0053]ステップ720に示すように、ビットストリームにアクセスし、幾つかのビットをビットストリームから取得する。JPEGビットストリームの場合、可能な最大のVLCシンボル長は、16ビットであり、したがって、ステップ720において、16ビットがビットストリームから取得され、ビットストリームバッファに格納される。他の実施形態では、ビットを取得するために異なる手法が利用される。例えば、ある実施形態では、これら16ビットを取得するためにビットストリームが最初にスキャンされ、また、別の実施形態では、それらのビットをビットストリームから読み取ることができる。
【0045】
[0054]次にステップ730に示すように、ビットストリームバッファを閾値情報と比較して、現在のシンボルが属するVLCグループを決定する。他の実施形態では、このステップは、異なる態様で行われる。例えば、一実施形態では、ビットストリームバッファに格納された値は、各グループの閾値と比較され、特定のグループに対してビットストリームバッファが閾値よりも大きい場合、比較結果として「真」が返される。真の結果の数を合計することにより、現在のシンボルに対するグループ番号が与えられる。幾つかの実施形態では、第1のVLCグループについての閾値は、ビットストリームバッファと比較する必要が無く、このような実施形態では、ビットストリームバッファの全ての候補の値が、第1のVLCグループについての閾値以上となる。
【0046】
[0055]次にステップ740に示すように、グループ番号を使用してグループ情報を取り出す。幾つかの実施形態では、グループ番号は、基本テーブルに対するインデックスの役割を果たす。また、基本テーブルは、特定のグループにおけるシンボルの長さのビット数、そのグループにおける最小のエントリに対応する閾値、及びそのグループにおけるエントリのシンボル値が格納される二次テーブルにおける位置のメモリオフセットに関する情報を含む。
【0047】
[0056]次にステップ750に示すように、ビットストリームから現在のシンボルを抽出する。幾つかの実施形態では、このステップは、基本テーブルによって示されるビット数をビットストリームから読み取ることによって行われる。他の実施形態では、例えば、ステップ720は、「スキャン」動作ではなく「読取り」動作を含み、このステップは、基本テーブルによって示されるビット数をビットストリームバッファから読み取ることによって行われる。
【0048】
[0057]次にステップ760に示すように、現在のシンボルに対応するシンボル値を取得する。幾つかの実施形態では、シンボル値は、二次テーブルに格納される。そのような一実施形態では、現在のシンボル、そのグループについての閾値、及びそのグループについてのオフセット値を用いて、二次テーブルに対するインデックスが算出される。このような計算の例を、下記の表2に示す。
【表2】
【0049】
<例示的VLC復号>
[0058]次に、図8A〜8Dを参照する。同図は、一実施形態に係る例示的VLC復号プロセスを示している。図8A〜8Dは、フローチャート700の方法によるビットストリーム825に対するオペレーションを示している。
【0050】
[0059]図8Aに示すように、ビットストリーム825は、一続きの幾つかの可変長シンボルから構成される。ビットストリーム825の最初の16ビットがスキャンされて、バッファ845内に取り込まれる。図示の実施形態では、スキャンオペレーションが用いられるため、ビットストリームメモリポインタ827は移動しない。別の実施形態で、例えば、読取り動作が用いられる場合、ビットストリームメモリポインタ827は、ビットストリームのアクセスされる部分の終端まで移動し得る。
【0051】
[0060]次いで、バッファ845の内容が、幾つかの閾値、例えば、基本テーブル400に示される閾値432〜439と比較される。バッファ845が閾値以上である場合の全比較により、1(真)が返される。図示の実施形態では、前述のように、グループ1についての閾値とバッファを比較する必要がなく、このような実施形態では、バッファ845の全てのとり得る値が、グループ1についての閾値より大きく、したがって、この比較は自動的に1として扱われることに留意されたい。
【0052】
[0061]これらの真の結果の和が、現在のシンボルのVLCグループを示す。図8Aに示される実施形態では、バッファ845は、閾値432及び433より大きいが閾値434よりも小さく、したがって、現在のシンボルは、VLCグループ3に属する。
【0053】
[0062]VLCグループは、基本テーブル、例えば、基本テーブル400のアドレス指定をして、該当するベーストリプレットを取り出すために使用される。図示の実施形態では、ベーストリプレットは、nビット値423、閾値433、及びオフセット443から構成される。
【0054】
[0063]図8Bに示すように、現在のシンボルは、ビットストリーム825から読み取られ、シンボルレジスタ855に格納される。ベーストリプレット、具体的には、現在のシンボルのシンボル831で示されるnビット値423は、3ビットの長さである。したがって、ビットストリーム825の最初の3ビットが、メモリに読み込まれる。図示の実施形態は、読取りオペレーションを伴うため、ビットストリームポインタ827は、読取り動作の終端の位置まで進む。別の実施形態では、ビットストリーム825からではなくバッファ845からシンボル831を取り出すことができる。そのような一実施形態では、ビットストリームポインタ827を移動させるためにフラッシュオペレーションが用いられる。
【0055】
[0064]シンボル831は、閾値433及びオフセット443と共に、二次テーブル500のアドレス指定のために使用される。オフセット443は、グループ3におけるエントリの二次テーブル500内での開始位置を示し、シンボル831は、閾値433と共にインデックス値を提供する。図示の実施形態では、シンボル831は、グループ3における第1のエントリに対応し、そのシンボル値は、メモリ位置<Table 2 Address +1>に格納されている。このシンボル831のシンボル値は、1である。
【0056】
[0065]図8Cに示すように、ビットストリーム825における次のVLCシンボル、例えば、シンボル833を復号するとき、同様のプロセスが行われる。即ち、ビットストリーム825の最初の16ビットが、バッファ845に読み込まれ、基本テーブル400に示されるような閾値と比較される。この比較により、現在のシンボルが、グループ6の要素であり6ビット長であることが示される。次いで、図8Dに示すように、最初の6ビットは、シンボルレジスタ855に読み込まれ、ビットストリームポインタ827が、シンボル833の終端まで進む。グループ6に関連付けられたベーストリプレット、例えば、nビット値426、閾値436、及びオフセット446を使用して、二次テーブル500に対するインデックスが算出され、対応するシンボル値である8が取り出される。
【0057】
<JPEG復号のためのシステム>
[0066]以下、図9を参照する。同図は、一実施形態に係るJPEG復号のためのシステム900を示している。システム900は、特定の列挙した特徴及び要素を組み込んだものとして示されているが、他の実施形態が、追加の、より少ない、若しくは、異なる特徴、要素、又は構成を含む適用例に適することを理解されたい。さらに、システム900は、例えば、専用電子部品を用いてハードウェアに、例えば、プログラムによるモジュールの集合体としてソフトウェアによって、又はこれらの組合せとして実装され得ることを理解されたい。
【0058】
[0067]システム900は、記憶要素910を含むように示されている。記憶要素910は、異なる実施形態では異なる形態をとることができる。例えば、一実施形態では、記憶要素910は、磁気ハードディスクドライブである。図示の実施形態では、記憶要素910は、JPEGファイル915を格納するものとして示されている。JPEGファイル915は、図に示すようにヘッダ916及びビットストリーム918を含む。
【0059】
[0068]システム900はまた、メモリ920を含むように示されている。メモリ920は、異なる実施形態では異なる形態をとることができる。図示の実施形態では、メモリ920は、基本テーブル922及び二次テーブル924を格納するために使用される。
【0060】
[0069]システム900はまた、JPEG復号エンジン950を含むように示されている。図示の実施形態では、JPEG復号エンジン950は、JPEG制御モジュール951、ハフマンテーブル生成器952、ビットストリームバッファ954、複数の閾値比較器956、シンボルバッファ958、及びシンボル値バッファ959を含む。
【0061】
[0070]図示の実施形態によるシステム900の動作は、JPEGファイル915をJPEG復号エンジン950に渡すことを含み、ここでは、JPEGファイル915はJPEG制御モジュール951によって受け取られる。ヘッダ916は、ハフマンテーブル生成器952に渡され、ハフマンテーブル生成器952は、ヘッダ916に含まれる情報、例えば、JPEGファイル915の一部分として符号化されたハフマンテーブル情報を使用して、基本テーブル922及び二次テーブル924を生成する。JPEG制御モジュール951は、基本テーブル922にアクセスし、そこに記述されている各ハフマングループの閾値情報を取得する。この閾値情報は、複数の閾値比較器956に読み込まれる。
【0062】
[0071]ビットストリーム918の一部分、例えば、最初の16ビットは、ビットストリームバッファ954に読み込まれる。次いで、ビットストリームバッファ954の内容が、各閾値比較器956と比較され、これらの比較の結果により、現在のシンボルのハフマングループが特定される。該当するハフマングループがいったん決定されると、グループ情報を基本テーブル922から取得することが可能になる。そして、このグループ情報により、ビットストリーム918から現在のシンボルの抽出が可能になり、現在のシンボルが、シンボルバッファ958に格納される。
【0063】
[0072]これらのグループ情報とシンボルの組合せは、二次テーブル924にアクセスし、現在のシンボルのシンボル値を抽出するために使用される。次いで、抽出されたシンボル値はシンボル値バッファ959に格納される。
【0064】
[0073]以上に本発明の実施形態を説明した。具体的な実施形態として本発明を説明したが、本発明は、それら実施形態により限定されて解釈されるべきでなく、添付の特許請求の範囲によって解釈されるべきことを理解すべきである。
【図面の簡単な説明】
【0065】
【図1】本発明の実施形態を実施し得る例示的なコンピュータシステムを示すブロック図である。
【図2】一実施形態に係る例示的なハフマンテーブルを示す図である。
【図3】一実施形態に係るJPEG画像ファイルを示す図である。
【図4】一実施形態に係る基本テーブルを示す図である。
【図5】一実施形態に係る二次テーブルを示す図である。
【図6】一実施形態に係る、JPEG画像ファイルにおけるハフマン符号を復号する方法を示すフローチャートである。
【図7】一実施形態に係る、可変長符号(VLC)を復号する方法を示すフローチャートである。
【図8A】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図8B】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図8C】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図8D】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図9】一実施形態に係るJPEG復号のためのシステムを示すブロック図である。
【符号の説明】
【0066】
100…バス、101…中央処理装置、102…RAM、103…ROM、104…データ記憶装置、105…グラッフィックスサブシステム、106…英数字入力装置、107…カーソル制御装置、108…入出力装置、110…表示装置、112…コンピュータシステム、200…ハフマンテーブル、300…JPEG画像ファイル、310…ヘッダ、320…画像データ、325…ビットストリーム抜粋、400…基本テーブル、500…二次テーブル、825…ビットストリーム、827…ビットストリームポインタ、845…バッファ、855…シンボルレジスタ、900…システム、910…記憶要素、915…JPEGファイル、916…ヘッダ、918…ビットストリーム、920…メモリ、922…基本テーブル、924…二次テーブル、950…JPEG復号エンジン、951…JPEG制御モジュール、952…テーブル生成器、954…ビットストリームバッファ、956…閾値比較器、958…シンボルバッファ、959…シンボル値バッファ。
【発明の分野】
【0001】
[0001]本発明の実施形態は、JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルで使用される可変長符号(VLC)の復号に関するものである。
【関連技術の説明】
【0002】
[0002]コンピューティングアプリケーションでは、可変長符号化(VLC)の符号化方式によって可逆的データ圧縮が可能となっている。一般に、VLC符号化方式は、確率論的手法を利用する。この手法では、より頻度の大きいシンボルを表現するために必要なビット数が、より頻度の低いシンボルを表現するために必要なビット数より少なくて済む。VLC符号化は、コンピューティングにおいて広く用いられており、特に、非圧縮情報がその圧縮情報よりもはるかに大きい記憶空間を必要とする画像、音楽、ビデオ等のようなメディアアプリケーションにおいて使用されている。
【0003】
[0003]VLC符号化方式の一つにハフマン符号化がある。ハフマン符号化は、データを圧縮する極めて有効な手段であり、特に、ソースマテリアル内の値の出現を利用して、ハフマン木における各シンボル値がどこに出現するべきかを決定することにより、圧縮すべきアイテムが、対応するハフマン木の生成を支援するように使用される場合に有効である。ハフマン符号化はまた、接頭符号と呼ばれることもあるプレフィックスフリー符号(語頭符号)を生成すること、即ち、ハフマン木によって生成されるシンボルは、そのハフマン木によって生成される他の如何なるシンボルの接頭部に対応しないという利点がある。
【0004】
[0004]ハフマン符号化は、様々なメディアアプリケーションで広く用いられており、特に、JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイル形式において用いられている。ハフマン符号化は全てのJPEGで使用されるので、各JPEGビューワは、画像を圧縮解除するためにハフマン符号化の処理をする必要がある。JPEGビューワがハフマン符号化をより効率的に処理できると、符号化処理がより速くなる。
【0005】
[0005]JPEG規格では、各画像に対して異なるハフマンテーブルを準備することができる。画像における全値の出現頻度を決定し、それら頻度を使用して、その画像の固有のハフマンテーブルを生成する。したがって、ビューワがJPEG画像を復号するために、ハフマンテーブルの再構成に必要な情報が、ファイルそれ自体にファイルヘッダとして含まれる。
【発明の概要】
【0006】
[0006]JPEG画像におけるハフマンシンボルを復号する手法について説明する。一つの手法は、JPEG画像ファイルにおけるハフマン符号を復号する方法に関するものである。この方法は、JPEG画像ファイルに関連付けられたビットストリームからビットストリームサンプルを取得することを含む。ビットストリームサンプルは、ハフマングループ番号を特定するために閾値と比較される。ハフマングループに関連付けられた情報が取り出され、ビットストリームから現在のハフマンシンボルを抽出するために使用される。次いで、対応するシンボル値を、現在のハフマンシンボル及びグループ情報を使用して取得することができる。
【0007】
[0007]JPEGファイルにおけるハフマン符号を復号するためのシステムを使用する別の手法についても説明する。このシステムは、JPEG画像ファイルに対するオペレーション(走査を実行するための制御モジュールを含む。ハフマンテーブル生成器が、JPEG画像ファイルに含まれる情報から基本テーブル及び二次テーブルを生成するために使用される。次いで、ビットストリームバッファを使用して、JPEG画像ファイルに含まれる画像データからデータ抜粋を格納することができ、複数の閾値比較器を使用して、現在のハフマンシンボルに対応するハフマングループを特定する。制御モジュールは、ハフマングループに関連付けられたグループ情報を取得し、このグループ情報を使用して、現在のハフマンシンボルに対応するシンボル値を取得することができる。
【0008】
[0008]更に他の手法として、JPEG画像ファイルにおけるハフマン可変長符号を復号する方法を述べる。この方法は、JPEG画像ファイルに関連付けられたビットストリームから16ビットをスキャンしてビットストリームバッファ内に取り込むことを含む。現在のハフマンシンボルに対応するハフマングループが特定され、このハフマングループに関連付けられたグループ情報が基本テーブルから取り出される。このグループ情報を参照して、現在のハフマンシンボルのシンボル値が二次テーブルから取得される。
【0009】
[0009]添付の図面は、本明細書に組み込まれその一部となるものであり、本発明の実施形態を示しており、本明細書の説明と共に本発明の原理を説明する役目を果たしている。
【発明を実施するための最良の形態】
【0010】
[0019]ここで、本発明の幾つかの実施形態を詳細に示す。代替的な実施形態と共に本発明を説明するが、本発明がこれらの実施形態に限定されるものではないことは理解されよう。それどころか、本発明は、添付の特許請求の範囲で定義される本発明の趣旨及び範囲に含まれうる代替形態、修正形態、及び均等物を含むものである。
【0011】
[0020]さらに、以下の詳細な説明においては、特許請求の範囲に記載された主題の完全な理解のために多数の具体的な細部を示す。しかしながら、これら特定の細部又はそれらの均等物なしに実施形態が実施され得ることが当業者には認識されよう。他の例では、周知の方法、手順、構成要素、及び回路については詳細には述べていないが、これは、本発明の主題の態様及び特徴を不必要に分かりにくくしないためである。
【0012】
[0021]以下の詳細な説明の幾つかの部分を、方法の観点で提示して論じる。この方法の動作を説明する添付の図面(例えば、図5)には、そのステップ及びシーケンスが開示されているが、このようなステップ及びシーケンスは例示的なものである。実施形態は、添付の図面のフローチャートに記載されるステップの変形形態や他の様々なステップ、並びに本明細書に記載される以外のシーケンスにおける様々なステップを実施するのにも適する。
【0013】
[0022]詳細な説明の幾つかの部分は、手順、ステップ、論理ブロック、処理、及び、コンピュータメモリ上で実行されうるデータビットに対する操作の他の記号表現として提示される。これらの記述及び表現は、データ処理技術の当業者がその作業の内容を最も効果的に他のデータ処理技術の当業者に伝えるために使用する手段である。手順、コンピュータ実行ステップ、論理ブロック、及びプロセス等は、本明細書においても、また一般的にも、望ましい結果を導く一連の首尾一貫したステップ又は命令として考えられる。これらのステップは、物理量の物理的操作を要するステップである。必須ではないが通常は、これらの量は、コンピュータシステムにおいて格納、転送、結合、比較、及び他の操作がなされ得る電気又は磁気信号の形態をとる。これらの信号を、主に一般的な用法であるという理由で、ビット、値、要素、シンボル、文字、項、又は番号などとして呼ぶことが時として好都合であることが分かっている。
【0014】
[0023]しかし、上記及び類似の用語の全ては、該当する物理量に関連付けられるべきであり、これらの物理量に適用される便利なラベルに過ぎないことに留意する必要がある。以下の説明において明らかなように、特にことわりがない限り、「アクセス」、「書き込み」、「含有」、「格納」、「送信」、「トラバース」、「関連付け」、「識別」などの用語を使用する説明は、全体を通して、コンピュータシステム又は類似の電子計算デバイスの動作及びプロセスを指していることを理解されたい。それらは、コンピュータシステムのレジスタ及びメモリにおける物理量(電子的量)として表現されるデータを操作して、同様にコンピュータシステムのメモリ又はレジスタ、或いは他のそうした情報記憶装置、伝送装置、又は表示装置における物理量として表現される他のデータに変形するものである。
【0015】
[0024]計算デバイスは通常、少なくとも何らかの形態のコンピュータ可読媒体を含む。コンピュータ可読媒体は、計算デバイスによってアクセスできる任意の利用可能な媒体とすることができる。コンピュータ可読媒体としては、限定するものではないが、例として、コンピュータ記憶媒体及び通信媒体がある。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、また他のデータ等の情報を格納するための任意の方法又は技術で実装された揮発性及び不揮発性のリムーバブル及び非リムーバブルの媒体を含む。コンピュータ記憶媒体は、以下に限定されないが、RAM、ROM、EEPROM、フラッシュメモリ、又は他のメモリ技術、或いは、CD−ROM、DVD(デジタル多用途ディスク)、又は他の光ストレージ、或いは、磁気カセット、磁気テープ、磁気ディスクストレージ、又は他の磁気記憶装置、或いは、所望の情報を格納するために使用することができコンピューティングデバイスによってアクセスすることができる他の任意の媒体を含む。通信媒体は、通常、搬送波又は他の移送メカニズムなどの変調されたデータ信号としてコンピュータ可読命令、データ構造、プログラムモジュール、又は他のデータを具体化し、また任意の情報送達媒体を含む。用語「変調されたデータ信号」は、信号内で情報を符号化するように一つ又は複数の信号特性が設定又は変更された信号を意味する。通信媒体には、限定ではなく例として、有線ネットワーク又は直接配線接続などの有線媒体、並びに、音響、RF、赤外線、及び他の無線媒体などの無線媒体が含まれる。上記の任意の組合せも、コンピュータ可読媒体の範囲に含まれるものとする。
【0016】
[0025]幾つかの実施形態は、一以上のコンピュータ又は他の装置で実行されるプログラムモジュール等のコンピュータ実行可能命令の一般的コンテキストにおいて記述することができる。一般に、プログラムモジュールには、特定のタスクを実行する又は特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、及びデータ構造などが含まれる。通常、プログラムモジュールの機能は、様々な実施形態で所望に応じて組み合わせたり分散させることができる。
【0017】
[0026]本明細書で説明する実施形態では、コンピュータシステムにおける別個のコンポーネントCPU及びGPUを参照することがあるが、CPUとGPUは単一の装置に統合することができ、命令ロジック、バッファ、及び機能ユニット等の様々なリソースをCPUとGPUが共用してもよく、又は、別々のリソースをグラフィックスオペレーションと汎用オペレーションに提供してもよいことが、当業者には認識されよう。したがって、本明細書でGPUに関連するように説明される回路及び/又は機能の何れか又は全てを、適宜に構成したCPUにて実施及び実行することも可能である。
【0018】
[0027]また、本明細書で説明する実施形態ではGPUを参照することがあるが、本明細書に記載の回路及び/又は機能は、汎用プロセッサ又は他の専用コプロセッサのような他のタイプのプロセッサ、或いはCPU内に実装され得ることを理解されたい。
【0019】
<基本計算システム>
[0028]まず図1を参照する。同図は、例示的なコンピュータシステム112のブロック図を示している。本明細書に記載のコンピュータシステム112は、実施形態を好適に実施し得る動作プラットフォームの例示的構成を示していることを理解されたい。しかしながら、異なる構成を有する他のコンピュータシステムを、コンピュータシステム112の代わりに、本発明の範囲内で使用することもできる。即ち、コンピュータシステム112は、図1に関連して説明する要素以外の要素を含むことができる。更に、実施形態は、コンピュータシステム112のようなコンピュータシステムだけでなく、実施形態を実施可能にするように構成できる任意のシステム上で実施されうる。実施形態は、異なる多くのタイプのコンピュータシステム112上で実施され得ることを理解されたい。システム112は、例えば、専用グラッフィックスレンダリングGPUに連結された強力な汎用CPUを有するデスクトップコンピュータ又はサーバコンピュータシステムとして実施することができる。このような実施形態では、周辺機器バス、専用オーディオ/ビデオコンポーネント、及び入出力装置等を追加するコンポーネントを含むことができる。
【0020】
[0029]同様に、システム112は、携帯端末(例えば、携帯電話など)、或いは、例えば、ワシントン州レドモンドのマクロソフト社から入手可能なXbox(登録商標)や日本の東京のソニー・コンピュータエンタテインメント社から入手可能なPLAYSTATION3(登録商標)のようなセットトップビデオゲーム機として実施可能である。また、システム112は、計算デバイスの電子装置(例えば、コンポーネント101、103、105、106等)が単一の集積回路チップ内に完全に含まれる「システムオンチップ」として実施することもできる。例としては、ディスプレイ、カーナビゲーションシステム、携帯エンターテイメントシステム等を有する携帯装置等がある。
【0021】
[0030]コンピュータシステム112は、情報を伝達するためのアドレス/データバス100と、バス100と結合されており情報及び命令を処理するための中央処理装置101と、バス100と結合されており中央処理装置101に対する情報及び命令を格納するための揮発性メモリ装置102(例えば、RAM(ランダムアクセスメモリ)、スタティックRAM、ダイナミックRAM等)と、バス100と結合されており処理装置101に対する静的な情報及び命令を格納するための不揮発性メモリ装置103(例えば、ROM(読取り専用メモリ)、プログラマブルROM、フラッシュメモリ等)と、を備える。更に、コンピュータシステム112はまた、情報及び命令を格納するためのデータ記憶装置104(例えば、ハードディスクドライブ)を備える。
【0022】
[0031]コンピュータシステム112はまた、オプションのグラッフィックスサブシステム105と、オプションの英数字入力装置106と、オプションのカーソル制御又は指示装置107と、信号通信インターフェース(入出力装置)108と、を備える。オプションの英数字入力装置106は、情報及びコマンド選択を中央処理装置101に伝達することができる。オプションのカーソル制御又は指示装置107は、ユーザ入力情報及びコマンド選択を中央処理装置101に伝達するためにバス100に結合されている。信号通信インターフェース(入出力装置)108は、シリアルポートとすることができ、バス100にやはり結合されている。また、通信インターフェース108は、無線通信メカニズムを含むことができる。通信インターフェース108を使用して、コンピュータシステム112は、インターネット又はイントラネット(例えば、ローカルエリアネットワーク)のような通信ネットワークを介して他のコンピュータシステムに通信可能に結合することができ、或いは、データ(例えば、デジタルテレビ信号)を受け取ることができる。コンピュータシステム112はまた、例えば、ビデオケーブル111によって接続された付属の表示装置110上に情報を表示することによってコンピュータユーザに情報を提示するグラッフィックスサブシステム105を備えることもできる。ある実施形態では、グラッフィックスサブシステム105は、中央処理装置101内に組み込まれる。別の実施形態では、グラッフィックスサブシステム105は、分離した別個のコンポーネントである。別の実施形態では、グラッフィックスサブシステム105は、別のコンポーネントに組み込まれる。別の実施形態では、グラッフィックスサブシステム105は、他の態様でシステム112に含まれる。
【0023】
[0032]<JPEGアプリケーションにおける効率的なVLC処理>
【0024】
[0033]以下の実施形態では、JPEG画像表示アプリケーションにおける可変長符号化(VLC)、特にハフマン符号化を効率的に処理するための手法を説明する。一実施形態では、JPEG画像におけるハフマン符号を処理するための方法が、JPEGビットストリームからVLCシンボルを効率的に抽出し、VLCシンボルをそれに対応するシンボル値と突き合わせることを含む。
【0025】
[0034]本明細書に記載する幾つかの実施形態では、JPEGファイル形式の幾つかの特徴及びそれに対応するハフマンテーブルの使用法を活用する。第1に、JPEGに対して許容されるハフマン符号の最大長は、16ビットである。第2に、JPEG画像と共に使用される各ハフマンテーブルは、16個のハフマングループを定義する。グループは各グループ内のシンボルの長さによって定義される。例えば、第1のグループは、1ビット長のシンボルからなり、第2のグループは、2ビット長のシンボルからなり、以下同様に、長さが16ビットのシンボルからなる第16のグループまで定義される。第3に、前述したように、ハフマン符号はプレフィックスフリー符号である。第4に、各ハフマングループ内で、符号値は、連続している。上記の特徴を活用することにより、ハフマン符号化の処理のための効率的な手法が可能となる。
【0026】
<例示的ハフマン符号>
[0035]JPEG規格では、各画像がそれ自体の固有の計算されたハフマンテーブルを有することが可能であるが、幾つかの「典型的」テーブルがJPEG委員会によって提供されている。そのような典型的なテーブルの一つは、下記の表1の配列によって指定されるDC輝度(DCluminance)テーブルである。
【表1】
【0027】
[0036]第1の配列dc_luminance bits[]は、JPEGによって使用される16個の各ハフマングループ内に幾つのシンボルが存在するかを示すことによって、ハフマン符号が対応するテーブル内にどのように割り当てられるかを指定する。このテーブルでは、2ビット長から9ビット長のシンボルに対応するグループ2〜9のみがエントリを有する。3ビット長のシンボルからなるグループ3は、5個のシンボルを有し、残りのグループは、それぞれ1個のシンボルを有する。グループ1及びグループ10〜16は、それぞれ、エントリがゼロとして定義されている。
【0028】
[0037]第2の配列dc_luminance_val[]は、シンボルに関連付けられる値をそれらが割り当てられる順序で示している。このテーブルでは、0が第1のシンボルに関連付けられ、1が第2のシンボルに関連付けられ、以下同様に行われる。
【0029】
[0038]次に図2を参照する。同図は、例示的なハフマンテーブル200を示している。ハフマンテーブル200は、図示のように、表1で定義されたDC輝度テーブルに対応している。左の列は、dc_luminance bits[]配列によって指定されたハフマンシンボル、即ち、シンボル201、203、205、207、209、211、213、215、217、219、221、及び223からなる。右の列は、dc_luminance_val[]配列によってシンボルに関連付けられた値、即ち、シンボル値202、204、206、208、210、212、214、216、218、220、222、及び224からなる。前述したように、ハフマン符号は、プレフィックスフリー符号であり、図2に示すようにそれらを左揃えに示すと、他のシンボルの接頭部と同一のシンボルが存在しない、例えば、シンボル201は00であり、他には00で始まるシンボルがないことが容易に分かる。
【0030】
<JPEGファイル形式>
[0039]次に図3を参照する。同図は、一実施形態に係るJPEG画像ファイル300を示している。図示するように、JPEG画像ファイル300は、ヘッダ310と画像データ320の二つの部分からなる。ヘッダ310は、JPEG画像ファイル300に含まれる画像を復号するために必要な情報を含み、一方、画像データ320は、実際の圧縮画像データを含んでいる。例えば、ヘッダ310は、JPEG画像ファイル300をJPEG画像ファイルとして識別する最初のシーケンスと、表1に示す配列のようなJPEG画像ファイル300に関するハフマンテーブル情報を含む部分とを含むことができる。
【0031】
[0040]図示するように、画像データ320は、圧縮シンボルデータのビットストリームからなる。このビットストリームデータの例示的な抜粋を、ビットストリーム抜粋325として示す。図示の実施形態におけるビットストリーム抜粋325は、一続きの幾つかのVLCシンボル、例えば、シンボル331、333、及び335から構成される。シンボルが可変長であるので、JPEGビューワは、それぞれの完全なシンボルを、長さにかかわらず認識する必要がある。
【0032】
<従来の手法>
[0041]JPEG画像ファイルにおけるハフマン符号を処理するための一般的な従来技術の手法は、幾つかのビット(多くの場合、3ビット)をビットストリームから読み取り、それらのビットをメモリに格納されたテーブルと比較することを含む。それらビットが完全なシンボルを構成する場合、テーブルはそのことを指し示し、そのシンボルに関連付けられた値を提供する。それらのビットが完全なシンボルでない場合、テーブルはやはりそのことを指し示し、また別のテーブルへの参照を含める。ビットストリームから更なるビットが読み取られ、第2のテーブルが参照され、同様の結果が生じ得る。この繰り返しのループサイクルは、最も些細な事例を除いてほとんどの場合、処理時間、繰り返しメモリアクセス、及び、複数のテーブルを格納するメモリの利用法の観点から非効率である。
【0033】
<基本テーブルと二次テーブル>
[0042]以下の実施形態では、より効率的なJPEG画像のハフマン復号のための手法を説明する。この手法の特徴の一つは、メモリテーブルの利用法を限定することにより、より効率的にメモリを利用することである。最も些細な事例を除いてほとんどの場合、基本及び二次テーブルの使用により、メモリの利用法の点で大幅な改善が見られる。
【0034】
[0043]以下、図4を参照する。同図は、一実施形態に係る基本テーブル400を示している。基本テーブル400は、上記で表1に示したDC輝度の「典型的」テーブル情報から導かれる。基本テーブル400は、JPEG規格によって定義される16個のハフマングループに対応する16個のグループに分割される。各グループは、以下の三つの情報、即ち、個々のグループにおけるエントリのビットの長さに対応するnビットと、図示の実施形態にではそのグループ内のエントリの最小値に対応する閾値と、そのグループ内のエントリのシンボル値が格納される第2のテーブルにおける位置を指すメモリポインタであるオフセットと、を含む。前述のように、グループ2〜9のみが、DC輝度の典型的テーブルにおいてエントリを有する。
【0035】
[0044]基本テーブル400内に示される閾値は、閾値を16ビット長まで埋めるために、ゼロで「パディング」されている。幾つかの実施形態では、後により詳細に述べるように、閾値は、同じ長さであり、例えば、とり得る最長のハフマン符号と同じ長さであることが好都合である。
【0036】
[0045]次に、図5を参照する。同図は、一実施形態に係る二次テーブル500を示している。図示の実施形態において、二次テーブル500は、上記で表1に示したDC輝度の「典型的」テーブル情報から導かれる。二次テーブル500は、JPEGビットストリームに符号化されたハフマンシンボルに対応するシンボル値のリストである。幾つかの実施形態では、これらの値は、オフセット値とインデックスの組合せにより任意の特定のエントリを取り出すことができるようにメモリに順次格納される。例えば、図示のように二次テーブル500がメモリアドレス<Table 2 Address>から始まる場合、オフセットとしての<Table 2 Address>と、インデックスとしての<2*value_length>(value_lengthは、二次テーブルにおけるエントリのバイト長に対応する)とを使用して、二次テーブル500に格納された第3のシンボル値を取り出す。
【0037】
<JPEG画像のハフマン値の復号>
[0046]以下、図6を参照する。同図は、一実施形態に係る、JPEG画像ファイルにおけるハフマン符号を復号する方法のフローチャート600を示している。フローチャート600で具体的なステップを開示するが、これらのステップは例示的なものである。即ち、本発明の実施形態は、様々な他の(追加の)ステップ又はフローチャート600に記載のステップの変形形態を実施するのにも適する。フローチャート600のステップは、与えられた順序と異なる順序で行われてもよく、フローチャート600のステップの全てが行われなくてもよいことを理解されたい。
【0038】
[0047]図示するように、ステップ610は、ビットストリームから16ビットをスキャンすることを含む。この実施形態では、VLC符号の可能な最大の長さは、16ビットである。したがって、この単一のスキャン動作により、ビットストリームから完全なシンボルが確実に取り出される。幾つかの実施形態では、これらのビットは、ビットストリームバッファ内に収納される。
【0039】
[0048]図示の実施形態におけるステップ620は、ビットストリームバッファにおける第1のシンボルについて該当するハフマングループを決定することを含む。前述のように、ハフマン符号は、プレフィックスフリー符号である。したがって、ある特定のハフマンシンボルが属するグループを特定することにより、そのシンボルのビット長も示される。ある手法では、ビットストリームバッファは、16個の異なる閾値と比較される。これら16個の閾値は、JPEG符号化で使用される16個の候補のハフマングループの何れかとそれぞれ関連付けられている。この比較は、並列に非常に迅速に行うことが可能であり、この比較により、適切なグループが決定されて、シンボルそれ自体が容易に決定される。
【0040】
[0049]次にステップ630に示すように、基本テーブルにアクセスし、シンボル情報を取り出す。幾つかの実施形態では、ハフマンシンボルを復号する際に二つのテーブルが利用される。第1のテーブル、即ち、基本テーブルは、JPEG符号化で使用される16個のハフマングループに関する情報を含む。そのような一実施形態では、16個のグループのそれぞれについて「ベーストリプレット(basetriplet)」が使用される。このトリプレットは、そのグループ内のエントリの長さ(例えば、ビット数での長さ)と、ステップ620で行われる比較のために使用することができるそのグループについての閾値と、そのグループでのエントリが開始しうる第2のメモリテーブルの部分を指し示すメモリオフセットと、を含む。第2のテーブルは、ビットストリームに符号化された様々なハフマンシンボルに対するシンボル値を含む。
【0041】
[0050]次にステップ640に示すように、対応するシンボル値を取り出す。幾つかの実施形態では、基本テーブルが、二次テーブルにアクセスするための適切なオフセット情報を提供する。次いで、シンボルそれ自体を使用してインデックスを提供することができ、オフセットと組み合わせたインデックスにより、二次テーブルにおける特定のシンボル値をその位置から取り出すことが可能になる。
【0042】
[0051]次に図7を参照する。同図は、一実施形態に係る、可変長符号(VLC)シンボルを復号する方法のフローチャート700を示している。フローチャート700に具体的なステップを開示するが、これらのステップは例示的なものである。即ち、本発明の実施形態は、様々な他の(追加の)ステップ又はフローチャート700に記載のステップの変形形態を実施するのにも適する。フローチャート700のステップは、与えられた順序と異なる順序で行われてもよく、そのステップの全てが行われなくてもよいことを理解されたい。
【0043】
[0052]ステップ710に示すように、符号化の際に使用されるVLCグループについての閾値情報を取り出す。幾つかの実施形態では、この閾値情報は、図4を参照して上記で説明したような基本テーブルから取得される。幾つかの実施形態では、ある所与のグループについての閾値情報は、そのグループ内のエントリの最小値からなる。更に、幾つかの実施形態では、全ての閾値が等しい長さになるように、特定のグループの閾値に対し「充填」、即ち「パディング」がなされ得る。
【0044】
[0053]ステップ720に示すように、ビットストリームにアクセスし、幾つかのビットをビットストリームから取得する。JPEGビットストリームの場合、可能な最大のVLCシンボル長は、16ビットであり、したがって、ステップ720において、16ビットがビットストリームから取得され、ビットストリームバッファに格納される。他の実施形態では、ビットを取得するために異なる手法が利用される。例えば、ある実施形態では、これら16ビットを取得するためにビットストリームが最初にスキャンされ、また、別の実施形態では、それらのビットをビットストリームから読み取ることができる。
【0045】
[0054]次にステップ730に示すように、ビットストリームバッファを閾値情報と比較して、現在のシンボルが属するVLCグループを決定する。他の実施形態では、このステップは、異なる態様で行われる。例えば、一実施形態では、ビットストリームバッファに格納された値は、各グループの閾値と比較され、特定のグループに対してビットストリームバッファが閾値よりも大きい場合、比較結果として「真」が返される。真の結果の数を合計することにより、現在のシンボルに対するグループ番号が与えられる。幾つかの実施形態では、第1のVLCグループについての閾値は、ビットストリームバッファと比較する必要が無く、このような実施形態では、ビットストリームバッファの全ての候補の値が、第1のVLCグループについての閾値以上となる。
【0046】
[0055]次にステップ740に示すように、グループ番号を使用してグループ情報を取り出す。幾つかの実施形態では、グループ番号は、基本テーブルに対するインデックスの役割を果たす。また、基本テーブルは、特定のグループにおけるシンボルの長さのビット数、そのグループにおける最小のエントリに対応する閾値、及びそのグループにおけるエントリのシンボル値が格納される二次テーブルにおける位置のメモリオフセットに関する情報を含む。
【0047】
[0056]次にステップ750に示すように、ビットストリームから現在のシンボルを抽出する。幾つかの実施形態では、このステップは、基本テーブルによって示されるビット数をビットストリームから読み取ることによって行われる。他の実施形態では、例えば、ステップ720は、「スキャン」動作ではなく「読取り」動作を含み、このステップは、基本テーブルによって示されるビット数をビットストリームバッファから読み取ることによって行われる。
【0048】
[0057]次にステップ760に示すように、現在のシンボルに対応するシンボル値を取得する。幾つかの実施形態では、シンボル値は、二次テーブルに格納される。そのような一実施形態では、現在のシンボル、そのグループについての閾値、及びそのグループについてのオフセット値を用いて、二次テーブルに対するインデックスが算出される。このような計算の例を、下記の表2に示す。
【表2】
【0049】
<例示的VLC復号>
[0058]次に、図8A〜8Dを参照する。同図は、一実施形態に係る例示的VLC復号プロセスを示している。図8A〜8Dは、フローチャート700の方法によるビットストリーム825に対するオペレーションを示している。
【0050】
[0059]図8Aに示すように、ビットストリーム825は、一続きの幾つかの可変長シンボルから構成される。ビットストリーム825の最初の16ビットがスキャンされて、バッファ845内に取り込まれる。図示の実施形態では、スキャンオペレーションが用いられるため、ビットストリームメモリポインタ827は移動しない。別の実施形態で、例えば、読取り動作が用いられる場合、ビットストリームメモリポインタ827は、ビットストリームのアクセスされる部分の終端まで移動し得る。
【0051】
[0060]次いで、バッファ845の内容が、幾つかの閾値、例えば、基本テーブル400に示される閾値432〜439と比較される。バッファ845が閾値以上である場合の全比較により、1(真)が返される。図示の実施形態では、前述のように、グループ1についての閾値とバッファを比較する必要がなく、このような実施形態では、バッファ845の全てのとり得る値が、グループ1についての閾値より大きく、したがって、この比較は自動的に1として扱われることに留意されたい。
【0052】
[0061]これらの真の結果の和が、現在のシンボルのVLCグループを示す。図8Aに示される実施形態では、バッファ845は、閾値432及び433より大きいが閾値434よりも小さく、したがって、現在のシンボルは、VLCグループ3に属する。
【0053】
[0062]VLCグループは、基本テーブル、例えば、基本テーブル400のアドレス指定をして、該当するベーストリプレットを取り出すために使用される。図示の実施形態では、ベーストリプレットは、nビット値423、閾値433、及びオフセット443から構成される。
【0054】
[0063]図8Bに示すように、現在のシンボルは、ビットストリーム825から読み取られ、シンボルレジスタ855に格納される。ベーストリプレット、具体的には、現在のシンボルのシンボル831で示されるnビット値423は、3ビットの長さである。したがって、ビットストリーム825の最初の3ビットが、メモリに読み込まれる。図示の実施形態は、読取りオペレーションを伴うため、ビットストリームポインタ827は、読取り動作の終端の位置まで進む。別の実施形態では、ビットストリーム825からではなくバッファ845からシンボル831を取り出すことができる。そのような一実施形態では、ビットストリームポインタ827を移動させるためにフラッシュオペレーションが用いられる。
【0055】
[0064]シンボル831は、閾値433及びオフセット443と共に、二次テーブル500のアドレス指定のために使用される。オフセット443は、グループ3におけるエントリの二次テーブル500内での開始位置を示し、シンボル831は、閾値433と共にインデックス値を提供する。図示の実施形態では、シンボル831は、グループ3における第1のエントリに対応し、そのシンボル値は、メモリ位置<Table 2 Address +1>に格納されている。このシンボル831のシンボル値は、1である。
【0056】
[0065]図8Cに示すように、ビットストリーム825における次のVLCシンボル、例えば、シンボル833を復号するとき、同様のプロセスが行われる。即ち、ビットストリーム825の最初の16ビットが、バッファ845に読み込まれ、基本テーブル400に示されるような閾値と比較される。この比較により、現在のシンボルが、グループ6の要素であり6ビット長であることが示される。次いで、図8Dに示すように、最初の6ビットは、シンボルレジスタ855に読み込まれ、ビットストリームポインタ827が、シンボル833の終端まで進む。グループ6に関連付けられたベーストリプレット、例えば、nビット値426、閾値436、及びオフセット446を使用して、二次テーブル500に対するインデックスが算出され、対応するシンボル値である8が取り出される。
【0057】
<JPEG復号のためのシステム>
[0066]以下、図9を参照する。同図は、一実施形態に係るJPEG復号のためのシステム900を示している。システム900は、特定の列挙した特徴及び要素を組み込んだものとして示されているが、他の実施形態が、追加の、より少ない、若しくは、異なる特徴、要素、又は構成を含む適用例に適することを理解されたい。さらに、システム900は、例えば、専用電子部品を用いてハードウェアに、例えば、プログラムによるモジュールの集合体としてソフトウェアによって、又はこれらの組合せとして実装され得ることを理解されたい。
【0058】
[0067]システム900は、記憶要素910を含むように示されている。記憶要素910は、異なる実施形態では異なる形態をとることができる。例えば、一実施形態では、記憶要素910は、磁気ハードディスクドライブである。図示の実施形態では、記憶要素910は、JPEGファイル915を格納するものとして示されている。JPEGファイル915は、図に示すようにヘッダ916及びビットストリーム918を含む。
【0059】
[0068]システム900はまた、メモリ920を含むように示されている。メモリ920は、異なる実施形態では異なる形態をとることができる。図示の実施形態では、メモリ920は、基本テーブル922及び二次テーブル924を格納するために使用される。
【0060】
[0069]システム900はまた、JPEG復号エンジン950を含むように示されている。図示の実施形態では、JPEG復号エンジン950は、JPEG制御モジュール951、ハフマンテーブル生成器952、ビットストリームバッファ954、複数の閾値比較器956、シンボルバッファ958、及びシンボル値バッファ959を含む。
【0061】
[0070]図示の実施形態によるシステム900の動作は、JPEGファイル915をJPEG復号エンジン950に渡すことを含み、ここでは、JPEGファイル915はJPEG制御モジュール951によって受け取られる。ヘッダ916は、ハフマンテーブル生成器952に渡され、ハフマンテーブル生成器952は、ヘッダ916に含まれる情報、例えば、JPEGファイル915の一部分として符号化されたハフマンテーブル情報を使用して、基本テーブル922及び二次テーブル924を生成する。JPEG制御モジュール951は、基本テーブル922にアクセスし、そこに記述されている各ハフマングループの閾値情報を取得する。この閾値情報は、複数の閾値比較器956に読み込まれる。
【0062】
[0071]ビットストリーム918の一部分、例えば、最初の16ビットは、ビットストリームバッファ954に読み込まれる。次いで、ビットストリームバッファ954の内容が、各閾値比較器956と比較され、これらの比較の結果により、現在のシンボルのハフマングループが特定される。該当するハフマングループがいったん決定されると、グループ情報を基本テーブル922から取得することが可能になる。そして、このグループ情報により、ビットストリーム918から現在のシンボルの抽出が可能になり、現在のシンボルが、シンボルバッファ958に格納される。
【0063】
[0072]これらのグループ情報とシンボルの組合せは、二次テーブル924にアクセスし、現在のシンボルのシンボル値を抽出するために使用される。次いで、抽出されたシンボル値はシンボル値バッファ959に格納される。
【0064】
[0073]以上に本発明の実施形態を説明した。具体的な実施形態として本発明を説明したが、本発明は、それら実施形態により限定されて解釈されるべきでなく、添付の特許請求の範囲によって解釈されるべきことを理解すべきである。
【図面の簡単な説明】
【0065】
【図1】本発明の実施形態を実施し得る例示的なコンピュータシステムを示すブロック図である。
【図2】一実施形態に係る例示的なハフマンテーブルを示す図である。
【図3】一実施形態に係るJPEG画像ファイルを示す図である。
【図4】一実施形態に係る基本テーブルを示す図である。
【図5】一実施形態に係る二次テーブルを示す図である。
【図6】一実施形態に係る、JPEG画像ファイルにおけるハフマン符号を復号する方法を示すフローチャートである。
【図7】一実施形態に係る、可変長符号(VLC)を復号する方法を示すフローチャートである。
【図8A】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図8B】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図8C】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図8D】一実施形態に係る、ビットストリームに対する例示的なVLC復号プロセスを示す図である。
【図9】一実施形態に係るJPEG復号のためのシステムを示すブロック図である。
【符号の説明】
【0066】
100…バス、101…中央処理装置、102…RAM、103…ROM、104…データ記憶装置、105…グラッフィックスサブシステム、106…英数字入力装置、107…カーソル制御装置、108…入出力装置、110…表示装置、112…コンピュータシステム、200…ハフマンテーブル、300…JPEG画像ファイル、310…ヘッダ、320…画像データ、325…ビットストリーム抜粋、400…基本テーブル、500…二次テーブル、825…ビットストリーム、827…ビットストリームポインタ、845…バッファ、855…シンボルレジスタ、900…システム、910…記憶要素、915…JPEGファイル、916…ヘッダ、918…ビットストリーム、920…メモリ、922…基本テーブル、924…二次テーブル、950…JPEG復号エンジン、951…JPEG制御モジュール、952…テーブル生成器、954…ビットストリームバッファ、956…閾値比較器、958…シンボルバッファ、959…シンボル値バッファ。
【特許請求の範囲】
【請求項1】
JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルにおけるハフマン符号を復号する方法であって、
前記JPEG画像ファイルのビットストリームからビットストリームサンプルを取得するステップと、
ハフマングループ番号を取得するために、前記ビットストリームサンプルを閾値と比較するステップと、
前記ハフマングループ番号を使用して、ハフマングループの情報を取り出すステップと、
前記ハフマングループの情報を使用して、前記ビットストリームから現在のハフマンシンボルを抽出するステップと、
前記現在のハフマンシンボル及び前記ハフマングループの情報を使用してシンボル値を取得するステップと、
を含む方法。
【請求項2】
前記閾値にアクセスするステップを更に含む、請求項1に記載の方法。
【請求項3】
前記ハフマングループの情報は、
前記ハフマングループにおけるエントリのビット長を示すビット長情報と、
前記ハフマングループにおける最小のハフマンシンボルを特定する前記閾値と、
メモリ内の位置から前記シンボル値を取得する際に使用するためのメモリオフセットと、
を含む、請求項1に記載の方法。
【請求項4】
前記閾値が、前記ビットストリームからの前記ビットストリームサンプルと長さを等しくするために、ゼロでパディングされる、請求項3に記載の方法。
【請求項5】
前記ビットストリームサンプルを取得するステップは、
前記ビットストリームサンプルを取得するために前記ビットストリームに対してスキャンオペレーションを行うステップと、
前記ビットストリームサンプルをメモリバッファにロードするステップと、
を含む、請求項3に記載の方法。
【請求項6】
前記抽出するステップは、前記現在のハフマンシンボルを取得するために、前記ビット長情報を参照して、前記ビットストリームに対して読取りオペレーションを行うステップを含む、請求項5に記載の方法。
【請求項7】
前記ビットストリームサンプルを取得するステップは、
前記ビットストリームサンプルを取得するために前記ビットストリームに対して読取りオペレーションを行うステップと、
前記ビットストリームサンプルをメモリバッファにロードするステップと、
を含む、請求項3に記載の方法。
【請求項8】
前記抽出するステップは、前記ビット長情報を参照して前記メモリバッファから前記現在のハフマンシンボルを取得するステップを含む、請求項7に記載の方法。
【請求項9】
前記ビットストリームサンプルを複数の閾値と比較するステップを更に含み、
前記複数の閾値の各々が、複数のハフマングループの何れか一つに関連付けられている、
請求項1に記載の方法。
【請求項10】
複数のハフマングループに関する情報を含む基本テーブルから前記複数の閾値を取得するステップを更に含む、請求項9に記載の方法。
【請求項11】
JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルにおけるハフマン符号を復号するためのシステムであって、
前記JPEG画像に対するオペレーションを行うための制御モジュールと、
前記制御モジュールに結合されたハフマンテーブル生成器であって、前記JPEG画像ファイルに含まれるハフマンテーブル情報から基本テーブル及び二次テーブルを生成するための該ハフマンテーブル生成器と、
前記制御モジュールに結合されたビットストリームバッファであって、前記JPEG画像ファイルに含まれる画像データからのデータ抜粋を格納するための該ビットストリームバッファと、
前記制御モジュールに結合された複数の閾値比較器であって、現在のハフマンシンボルに対応するハフマングループを特定するための該複数の閾値比較器と、
を備え、
前記制御モジュールが、前記基本テーブルから前記ハフマングループに関連付けられたグループ情報を取得し、前記グループ情報を使用して前記現在のハフマンシンボルに対応するシンボル値を取得する、システム。
【請求項12】
前記基本テーブルは、複数のハフマングループに対応する複数のハフマングループ情報を備える、請求項11に記載のシステム。
【請求項13】
前記複数のハフマングループは、16個のハフマングループを備える、請求項12に記載のシステム。
【請求項14】
前記複数のハフマングループ情報の各々が、
前記対応するハフマングループにおける各エントリのビット長情報と、
前記対応するハフマングループにおける最小のシンボルに対応する閾値と、
前記二次テーブルにおける位置に対応するオフセットと
を備える、請求項12に記載のシステム。
【請求項15】
前記複数の閾値が、前記複数の閾値比較器にロードされ、前記ビットストリームバッファに格納された前記データ抜粋と比較される、請求項14に記載のシステム。
【請求項16】
JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルにおけるハフマン可変長符号を復号する方法であって、
前記JPEG画像ファイルに関連付けられたビットストリームから16ビットをスキャンしてビットストリームバッファ内に取り込むステップと、
前記ビットストリームバッファに格納された現在のハフマンシンボルに対応するハフマングループを特定するステップと、
基本テーブルから、前記ハフマングループに関連付けられたグループ情報を取り出すステップと、
前記グループ情報を参照して、二次テーブルから前記現在のハフマンシンボルのシンボル値を取得するステップと、
を含む方法。
【請求項17】
前記特定するステップは、
前記基本テーブルから、複数のハフマングループに関連付けられた複数の閾値を取り出すステップと、
前記複数の閾値の各々を前記ビットストリームバッファと比較して、複数の結果を作成するステップと、
前記複数の結果を参照して前記ハフマングループを特定するステップと、
を含む、請求項16に記載の方法。
【請求項18】
前記グループ情報は、
前記ハフマングループにおけるエントリのビット長と、
前記ハフマングループにおける最小のエントリに対応する閾値と、
前記二次テーブルにおける位置に対応するメモリオフセットと、
を含む、請求項16に記載の方法。
【請求項19】
前記基本テーブルは、複数のハフマングループに関連付けられた複数のグループ情報を含む、請求項18に記載の方法。
【請求項20】
前記取得するステップは、前記メモリオフセット、前記閾値、及び前記現在のハフマンシンボルを参照してメモリアドレスを算出するステップを含む、請求項18に記載の方法。
【請求項1】
JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルにおけるハフマン符号を復号する方法であって、
前記JPEG画像ファイルのビットストリームからビットストリームサンプルを取得するステップと、
ハフマングループ番号を取得するために、前記ビットストリームサンプルを閾値と比較するステップと、
前記ハフマングループ番号を使用して、ハフマングループの情報を取り出すステップと、
前記ハフマングループの情報を使用して、前記ビットストリームから現在のハフマンシンボルを抽出するステップと、
前記現在のハフマンシンボル及び前記ハフマングループの情報を使用してシンボル値を取得するステップと、
を含む方法。
【請求項2】
前記閾値にアクセスするステップを更に含む、請求項1に記載の方法。
【請求項3】
前記ハフマングループの情報は、
前記ハフマングループにおけるエントリのビット長を示すビット長情報と、
前記ハフマングループにおける最小のハフマンシンボルを特定する前記閾値と、
メモリ内の位置から前記シンボル値を取得する際に使用するためのメモリオフセットと、
を含む、請求項1に記載の方法。
【請求項4】
前記閾値が、前記ビットストリームからの前記ビットストリームサンプルと長さを等しくするために、ゼロでパディングされる、請求項3に記載の方法。
【請求項5】
前記ビットストリームサンプルを取得するステップは、
前記ビットストリームサンプルを取得するために前記ビットストリームに対してスキャンオペレーションを行うステップと、
前記ビットストリームサンプルをメモリバッファにロードするステップと、
を含む、請求項3に記載の方法。
【請求項6】
前記抽出するステップは、前記現在のハフマンシンボルを取得するために、前記ビット長情報を参照して、前記ビットストリームに対して読取りオペレーションを行うステップを含む、請求項5に記載の方法。
【請求項7】
前記ビットストリームサンプルを取得するステップは、
前記ビットストリームサンプルを取得するために前記ビットストリームに対して読取りオペレーションを行うステップと、
前記ビットストリームサンプルをメモリバッファにロードするステップと、
を含む、請求項3に記載の方法。
【請求項8】
前記抽出するステップは、前記ビット長情報を参照して前記メモリバッファから前記現在のハフマンシンボルを取得するステップを含む、請求項7に記載の方法。
【請求項9】
前記ビットストリームサンプルを複数の閾値と比較するステップを更に含み、
前記複数の閾値の各々が、複数のハフマングループの何れか一つに関連付けられている、
請求項1に記載の方法。
【請求項10】
複数のハフマングループに関する情報を含む基本テーブルから前記複数の閾値を取得するステップを更に含む、請求項9に記載の方法。
【請求項11】
JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルにおけるハフマン符号を復号するためのシステムであって、
前記JPEG画像に対するオペレーションを行うための制御モジュールと、
前記制御モジュールに結合されたハフマンテーブル生成器であって、前記JPEG画像ファイルに含まれるハフマンテーブル情報から基本テーブル及び二次テーブルを生成するための該ハフマンテーブル生成器と、
前記制御モジュールに結合されたビットストリームバッファであって、前記JPEG画像ファイルに含まれる画像データからのデータ抜粋を格納するための該ビットストリームバッファと、
前記制御モジュールに結合された複数の閾値比較器であって、現在のハフマンシンボルに対応するハフマングループを特定するための該複数の閾値比較器と、
を備え、
前記制御モジュールが、前記基本テーブルから前記ハフマングループに関連付けられたグループ情報を取得し、前記グループ情報を使用して前記現在のハフマンシンボルに対応するシンボル値を取得する、システム。
【請求項12】
前記基本テーブルは、複数のハフマングループに対応する複数のハフマングループ情報を備える、請求項11に記載のシステム。
【請求項13】
前記複数のハフマングループは、16個のハフマングループを備える、請求項12に記載のシステム。
【請求項14】
前記複数のハフマングループ情報の各々が、
前記対応するハフマングループにおける各エントリのビット長情報と、
前記対応するハフマングループにおける最小のシンボルに対応する閾値と、
前記二次テーブルにおける位置に対応するオフセットと
を備える、請求項12に記載のシステム。
【請求項15】
前記複数の閾値が、前記複数の閾値比較器にロードされ、前記ビットストリームバッファに格納された前記データ抜粋と比較される、請求項14に記載のシステム。
【請求項16】
JPEG(ジョイントフォトグラフィックエキスパートグループ)画像ファイルにおけるハフマン可変長符号を復号する方法であって、
前記JPEG画像ファイルに関連付けられたビットストリームから16ビットをスキャンしてビットストリームバッファ内に取り込むステップと、
前記ビットストリームバッファに格納された現在のハフマンシンボルに対応するハフマングループを特定するステップと、
基本テーブルから、前記ハフマングループに関連付けられたグループ情報を取り出すステップと、
前記グループ情報を参照して、二次テーブルから前記現在のハフマンシンボルのシンボル値を取得するステップと、
を含む方法。
【請求項17】
前記特定するステップは、
前記基本テーブルから、複数のハフマングループに関連付けられた複数の閾値を取り出すステップと、
前記複数の閾値の各々を前記ビットストリームバッファと比較して、複数の結果を作成するステップと、
前記複数の結果を参照して前記ハフマングループを特定するステップと、
を含む、請求項16に記載の方法。
【請求項18】
前記グループ情報は、
前記ハフマングループにおけるエントリのビット長と、
前記ハフマングループにおける最小のエントリに対応する閾値と、
前記二次テーブルにおける位置に対応するメモリオフセットと、
を含む、請求項16に記載の方法。
【請求項19】
前記基本テーブルは、複数のハフマングループに関連付けられた複数のグループ情報を含む、請求項18に記載の方法。
【請求項20】
前記取得するステップは、前記メモリオフセット、前記閾値、及び前記現在のハフマンシンボルを参照してメモリアドレスを算出するステップを含む、請求項18に記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8A】
【図8B】
【図8C】
【図8D】
【図9】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8A】
【図8B】
【図8C】
【図8D】
【図9】
【公開番号】特開2009−118464(P2009−118464A)
【公開日】平成21年5月28日(2009.5.28)
【国際特許分類】
【外国語出願】
【出願番号】特願2008−238211(P2008−238211)
【出願日】平成20年9月17日(2008.9.17)
【出願人】(501261300)エヌヴィディア コーポレイション (166)
【Fターム(参考)】
【公開日】平成21年5月28日(2009.5.28)
【国際特許分類】
【出願番号】特願2008−238211(P2008−238211)
【出願日】平成20年9月17日(2008.9.17)
【出願人】(501261300)エヌヴィディア コーポレイション (166)
【Fターム(参考)】
[ Back to top ]