(57)【要約】  本発明は、プリフィックスがユナリ符号であるプリフィックス‐サフィックス符号のロスレス圧縮と、対応する圧縮解除とに関する。プリフィックス‐サフィックス符号（ＶＬＣ１，ＶＬＣ２，ＶＬＣ３）をロスレス圧縮する方法は、各プリフィックス（ＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３）から第１の連続的なビットシーケンス（ＦＢＳ）を生成するステップと、第１の連続的なビットシーケンス（ＦＢＳ）内の第１の値の頻度と第１の連続的なビットシーケンス（ＦＢＳ）内の第２の値の頻度との間の差に関する冗長性を取り除くことによって第１の連続的なビットシーケンス（ＦＢＳ）をロスレス圧縮するステップと、を含む。ビット値は、各プリフィックスに不均一に分布する一方で、各サフィックス内のビット値の分布はより均一である。従って、各プリフィックスが別々に圧縮された場合に、より良好な圧縮を得ることができる。【選択図】  図１
2012502573.tif 000002
【特許請求の範囲】
【請求項１】
各プリフィックス（ＰＲＦＸ，ＰＲＦＸ２，ＰＲＦＸ３）が、対応するサフィックス内に含まれるビットの数を表すユナリ符号である、プリフィックス‐サフィックス符号（ＶＬＣ１，ＶＬＣ２，ＶＬＣ３）をロスレス圧縮する方法であって、
前記各プリフィックス（ＰＲＦＸ，ＰＲＦＸ２，ＰＲＦＸ３）を第１の連続的なビットシーケンス（ＦＢＳ）にグループ化するステップと、
前記各サフィックスを第２の連続的なビットシーケンスにグループ化するステップと、
前記第１の連続的なビットシーケンスから冗長性を取り除くことによって、少なくとも前記第１の連続的なビットシーケンス（ＦＢＳ）をロスレス圧縮するステップと、を含む、前記方法。
【請求項２】
前記ロスレス圧縮を行うステップは、前記第１の連続的なビットシーケンスの算術符号化を含む、請求項１に記載の方法。
【請求項３】
前記第１の連続的なビットシーケンス（ＦＢＳ）の算術符号は、第１の連続的なビットシーケンス（ＦＢＳ）内の第１の値の頻度および／または第２の値の頻度に関する情報を含む、請求項２に記載の方法。
【請求項４】
前記ロスレス圧縮を行うステップは、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）圧縮またはレンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）圧縮のようなアダプティブなディクショナリに基づく圧縮を含む、請求項１に記載の方法。
【請求項５】
前記圧縮された第１のビットシーケンス（Ａ−Ｃ，ＬＺ−Ｃ）は、前記第１の連続的なビットシーケンス（ＦＢＳ）が圧縮されること、および／または、どの圧縮方法によって前記第１の連続的なビットシーケンス（ＦＢＳ）が圧縮されるか、を示す１つ以上のフラグ・ビットを含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表すビットシーケンスを圧縮解除する方法であって、前記プリフィックス‐サフィックス符号の各々について、前記プリフィックスは対応するサフィックス内に含まれるビットの数を表しており、前記方法は、
前記ビットシーケンスに含まれる第１の連続的なサブシーケンス（Ａ−Ｃ，ＬＺ−Ｃ）を圧縮解除するステップであって、前記圧縮解除された第１の連続的なサブシーケンス（ＦＢＳ）が、異なる第２の値を有するストップ・ビットで終了する同一の第１の値を有するビットのシーケンスを含んでいる、該ステップと、
前記圧縮解除された第１の連続的なサブシーケンス（ＦＢＳ）を前記ストップ・ビットで前記各プリフィックス（ＰＲＦＸ，ＰＲＦＸ２，ＰＲＦＸ３）にパーティション化するステップであって、各プリフィックス（ＰＲＦＸ，ＰＲＦＸ２，ＰＲＦＸ３）は、前記同一の第１の値を有するビットの前記ストップ・ビットで終了するシーケンスのうちの１つである、該ステップと、
前記各プリフィックス（ＰＲＦＸ，ＰＲＦＸ２，ＰＲＦＸ３）を使用して、前記ビットシーケンスの残りに含まれる第２の連続的なサブシーケンス（ＳＢＳ）を各サフィックス（ＳＦＦＸ１，ＳＦＦＸ２，ＳＦＦＸ３）にパーティション化するステップと、を含む前記方法。
【請求項７】
前記第１のサブシーケンス（ＦＢＳ）内のビット値の相対的な頻度に関する情報を抽出するステップをさらに含み、
前記第１のサブシーケンス（ＦＢＳ）は、前記抽出された情報を使用して算術復号によって圧縮解除される、請求項６に記載の方法。
【請求項８】
前記第１の連続的なサブシーケンス（ＦＢＳ）は、アダプティブなディクショナリに基づく圧縮解除の方法、例えば、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）圧縮解除の方法によって、またはレンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）圧縮解除の方法によって圧縮解除される、請求項６または７に記載の方法。
【請求項９】
前記第１の連続的なビットシーケンス（ＦＢＳ）が圧縮解除されなければならないこと、および／または、どの圧縮解除方法によって前記第１の連続的なビットシーケンス（ＦＢＳ）が圧縮解除されなければならないか、を示す１つ以上のフラッグ・ビットを評価するステップと、
当該評価に従って、前記第１の連続的なサブシーケンス（ＦＢＳ）を圧縮解除するステップと、をさらに含む、請求項６〜８のいずれか１項に記載の方法。
【請求項１０】
圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表すビットシーケンスを担持する記憶媒体または信号であって、前記整数またはシンボルは、オーディオおよび／またはビデオに関する情報を表し、前記ビットシーケンスは、圧縮された各プリフィックスを表す第１の連続的なサブシーケンスと、各サフィックスを表す別個の第２の連続的なサブシーケンスとを含んでいる、前記記憶媒体または信号。
【請求項１１】
前記圧縮されたプリフィックス‐サフィックス符号は、請求項１〜５のいずれか１項によって圧縮されている、請求項１０に記載の記録媒体または信号。
【請求項１２】
前記プリフィックス‐サフィックス符号は、オーディオおよび／またはビデオのデータに関する情報を表す整数の可変長符号（ＶＬＣ１，ＶＬＣ２，ＶＬＣ３）である、請求項１〜９のいずれか１項に記載の方法または請求項１０または１１に記載の記憶媒体または信号。
【請求項１３】
前記整数は、同一のタイプのシンタックス要素を表し、当該シンタックス要素は、画像またはビデオのフレームのマクロブロックに関連付けられている、請求項１２に記載の方法、記憶媒体または信号。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリフィックス‐サフィックス符号をロスレス圧縮する方法に関し、各プリフィックスは、異なる第２の値のストップ・ビットで終了する第１の値のビットシーケンスを有している。また、本発明は、圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表すビットシーケンスを圧縮解除する方法に関する。さらに、本発明は、圧縮されたプリフィックス‐サフィックス符号を担持する記憶媒体または信号に関する。
【背景技術】
【０００２】
例えば、プリフィックス‐サフィックス符号は、可変長符号化（ＶＬＣ：ｖａｒｉａｂｌｅ  ｌｅｎｇｔｈ  ｃｏｄｉｎｇ）において使用される。大抵のＶＬＣスキームにおいては、整数またはシンボルは、可変長の２つの部分のビットシーケンスによって表され、ビットシーケンスの先行する部分は、後続する部分のビット数を示すプリフィックスを担持し、後続する部分は、符号化されたペイロード・データを表すものをサフィックスとして担持する。プリフィックスは、このビット数を、ユナリ符号（ｕｎａｒｙ  ｃｏｄｅ）によって、即ち、異なる値のストップ・ビットで終了する等しい値を有する同じ数のビットによって示す。
【０００３】
ＶＬＣは、オーディオ、画像、ビデオ、マルチメディア、コンピュータ・ゲーム、３Ｄメッシュ・データ、テキスト、ファイルなどに関する情報の符号化において使用される。例えば、画像またはビデオのフレームのマクロブロックのシンタックス要素は、ＶＬＣを使用して符号化される。
【０００４】
ＶＬＣは、整数またはシンボルを非常にコンパクトに表すものを提供するが、より一層コンパクトに表すものが望まれている。
【発明の概要】
【０００５】
各プリフィックスが、異なる第２の値のストップ・ビットで終了する第１の値のビットシーケンスを有している、プリフィックス‐サフィックス符号のロスレス圧縮は、請求項１の各特徴事項を含む方法によって達成される。
【０００６】
この方法は、各プリフィックスから第１の連続的なビットシーケンスを生成するステップと、各サフィックスから第２の連続的なビットシーケンスを生成するステップと、第１の連続的なビットシーケンス内の第１の値の頻度と第１の連続的なビットシーケンス内の第２の値の頻度との間の差に関する冗長性を取り除くことによって第１の連続的なビットシーケンスをロスレス圧縮するステップと、を含む。
【０００７】
ビット値は、各プリフィックスに不均一に分布する一方で、各サフィックス内のビット値の分布はより均一である。従って、各プリフィックスが別々に圧縮された場合に、より良好な圧縮を得ることができる。
【０００８】
一態様においては、この方法は、各サフィックスから第２の連続的なビットシーケンスを生成するステップと、第２の連続的なビットシーケンスを圧縮された第１のビットシーケンスに付加するステップとをさらに含む。
【０００９】
他の態様においては、ロスレス圧縮を行うステップは、第１の連続的なビットシーケンスの算術符号化を含む。
【００１０】
第１の連続的なビットシーケンスの算術符号は、第１の連続的なビットシーケンス内の第１の値の頻度および／または第２の値の頻度に関する情報を含んでいてもよい。
【００１１】
他の態様においては、ロスレス圧縮を行うステップは、アダプティブなディクショナリに基づく圧縮を含む。
【００１２】
アダプティブなディクショナリに基づく圧縮は、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）圧縮またはレンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ）圧縮であってもよい。
【００１３】
さらに他の態様においては、圧縮された第１のビットシーケンスは、第１の連続的なビットシーケンスが圧縮されること、および／または、どの圧縮方法によって第１の連続的なビットシーケンスが圧縮されるか、を示す１つ以上のフラグ・ビットを含む。
【００１４】
圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表すビットシーケンスの圧縮解除は、請求項７の各特徴事項を含む方法によって達成される。
【００１５】
この圧縮解除方法は、ビットシーケンスに含まれる第１の連続的なサブシーケンスを圧縮解除するステップと、ストップ・ビットで圧縮解除された第１の連続的なサブシーケンスを各プリフィックスに分けるステップとを含む。
【００１６】
一態様においては、圧縮解除方法は、各プリフィックスを使用して、ビットシーケンスの残りに含まれる第２の連続的なサブシーケンスを各サフィックスに分けるステップをさらに含む。
【００１７】
他の態様においては、圧縮解除方法は、第１のサブシーケンス内のビット値の相対的な頻度に関する情報を抽出するステップをさらに含み、第１のサブシーケンスは、抽出された情報を使用して算術復号によって圧縮解除される。
【００１８】
圧縮解除方法の他の態様においては、第１の連続的なサブシーケンスは、アダプティブなディクショナリに基づく圧縮解除の方法、例えば、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）圧縮解除の方法によって、またはレンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ）圧縮解除の方法によって圧縮解除される。
【００１９】
さらに他の態様においては、圧縮解除方法は、第１のサブシーケンスが圧縮解除されなければならないこと、および／または、どの圧縮解除方法によってサブシーケンスが圧縮解除されなければならないか、を示す１つ以上のフラッグ・ビットを評価するステップと、この評価に従って、第１の連続的なサブシーケンスを圧縮解除するステップとをさらに含む。
【００２０】
本発明は、さらに、圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表すビットシーケンスを担持する記憶媒体または信号であって、整数またはシンボルは、オーディオおよび／またはビデオに関する情報を表し、ビットシーケンスは、圧縮された各プリフィックスを表す第１の連続的なサブシーケンスと、各サフィックスを表す別個の第２の連続するサブシーケンスとを含んでいる、記憶媒体または信号を提示する。
【００２１】
記憶媒体または信号の一態様において、圧縮されたプリフィックス‐サフィックス符号は、プリフィックス‐サフィックス符号をロスレス圧縮する本発明の方法、または、この方法の幾つかの態様のうちの１つに従って圧縮される。
【００２２】
記憶媒体または信号によって担持されるビットシーケンスは、第１の連続的なビットシーケンス内の第１の値の頻度および／または第１の連続的なビットシーケンス内の第２の値の頻度に関する情報を含んでいてもよい。
【００２３】
さらに／または、記憶媒体または信号によって担持されるビットシーケンスは、第１の連続的なサブシーケンスが圧縮されること、および／または、どの圧縮方法によって第１の連続的なサブシーケンスが圧縮されるか、を示す１つ以上のフラグ・ビットを含んでいてもよい。
【００２４】
記憶媒体は、ＤＶＤ、ＨＤ‐ＤＶＤ、ブルーレイ・ディスクなどのディスク状の光学媒体であってもよく、あるいはハードディスク又はテープ・ドライブなどの磁気媒体であってもよく、あるいは他のどのような種類の記憶媒体であってもよい。
【００２５】
プリフィックス‐サフィックス符号がオーディオおよび／またはビデオのデータに関する情報を表す整数の可変長符号であると、本発明の効果を良好に得ることができる。例えば、各整数は同一のタイプのシンタックス要素を表し、このシンタックス要素は、画像またはビデオのフレームのマクロブロックに関連付けられていてもよい。
【００２６】
本発明の例示的な実施の形態を、以下の記載においてより詳細に説明する。
【００２７】
本発明の例示的な実施の形態は、各図面に例示されており、以下の記載においてより詳細に説明されている。
【図面の簡単な説明】
【００２８】
【図１】図１は、プリフィックス‐サフィックス符号のロスレス圧縮の第１の例示的な実施の形態を示す図である。
【図２】図２は、プリイックス‐サフィックス符号のロスレス圧縮の第２の例示的な実施の形態を示す図である。
【発明を実施するための形態】
【００２９】
ＶＬＣ符号は、複数の異なるシンボルを表すために、可変の整数の数のビットを使用する。ハフマン符号化（Ｈｕｆｆｍａｎ  ｃｏｄｉｎｇ）は、最も広く使用されているＶＬＣの方法である。ハフマン符号化は、より大きな確率を有するシンボルに対してより少ないビットを割り当て、より小さな確率を有するシンボルに対してより多くのビットを割り当てる。ハフマン符号化は、ソース符号化のための最良のＶＬＣの方法であることが判明しているが、ハフマン・ツリーを構築するために複雑な処理を必要とする。さらに、ハフマン符号は、シンボルまたは値の数が有限である場合により適している。しかしながら、多くの場合ではシンボルの数は無限であり、例えば、シンボルは整数である。
【００３０】
従って、実際には、いくつかのシンプルなＶＬＣ符号、例えば、ゴロム符号（Ｇｏｌｏｍｂ‐ｃｏｄｅ）が提案されている。ゴロム符号から派生した幾つかの特定の派生物として、ゴロムライス符号（Ｇｏｌｏｍｂ‐Ｒｉｃｅ  ｃｏｄｅ）、指数ゴロム符号（Ｅｘｐ‐Ｇｏｌｏｍｂ  ｃｏｄｅ）、さらに、ハイブリッド・ゴロム符号などが存在する。ユナリ符号は、特定のゴロムライス符号である。表１は、種々のゴロム符号の例を示している。
【表１】
2012502573.tif 000003
表１：ゴロム符号の派生物
【００３１】
これらの上述した可変長符号は、シンプルであり、特定の統計的な確率分布を有する符号化信号ソースに適している。例えば、ユナリ符号は、シンボルｎがＰ∪（ｎ）＝２−（ｎ＋１）の確率で現れるときに最適である。同様に、確率分布ＰＲＣ（ｎ）、ＰＥＸＧ（ｎ）、およびＰＨＧ（ｎ）では、それぞれ、ゴロムライス符号、指数ゴロム符号、ハイブリッド・ゴロム符号が最適である。しかしながら、実際には、信号ソースは、上記の確率分布のいずれかに完全に従っているものではない。従って、ＶＬＣ符号内には冗長性が残っているが、これは、以前のオーディオまたは画像／ビデオの符号化スキームにおけるＶＬＣ符号化ツールにおいては考慮されていなかった。
【００３２】
指数ゴロム符号やハフマン符号（ユナリ符号でないもの）のようなＶＬＣ符号は、プリフィックス符号またはプリフィックス‐サフィックス符号とも呼ばれている。プリフィックス符号は、プリフィックス・プロパティを有する。セット（ｓｅｔ）内において、任意の他の符号語ＶＬＣ１，ＶＣＬ２，ＶＬ３のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３である符号語ＶＬＣ１，ＶＬＣ２，ＶＬＣ３は存在しない。通常、ゴロム符号およびハフマン符号は、以下のフォーマットで表すことができる。
００．．．０１ＸＸＸＸＸ      プリフィックス：００．．．０１      サフィックス：ＸＸＸＸＸ      （「Ｘ」は「１」または「０」をとりうる）
【００３３】
即ち、幾つかの連続した「０」および「１」は、プリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３を構成し、後続するＸＸＸＸＸは、サフィックスＳＦＦＸ１，ＳＦＦＸ２，ＳＦＦＸ３を構成する。一般に、各サフィックスＳＦＦＸ１，ＳＦＦＸ２，ＳＦＦＸ３における「０」と「１」の確率はほぼ同じ、即ち５０％である。従って、各サフィックスＳＦＦＸ１，ＳＦＦＸ２，ＳＦＦＸ３をさらに圧縮する余地はほとんどない。
【００３４】
しかしながら、各プリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３における「０」および「１」の確率は、多くの状況において同じではないし、全く異なるものでもない。これは、ハフマン符号が最適ではなく、最適のビット・レートを得ることができないことを意味する。
【００３５】
例えば、Ｈ．２６４／ＡＶＣ規格においては、コンテキスト適応型２値算術符号化（ＣＡＢＡＣ：Ｃｏｎｔｅｘｔ  ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｂｉｎａｒｙ  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ）が使用されない場合には、指数ゴロム符号を使用してヘッダ情報の全てを符号化する一方で、コンテキスト適応型可変長符号化（ＣＡＶＬＣ：Ｃｏｎｔｅｘｔ  ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｌｅｎｇｔｈ  Ｃｏｄｉｎｇ）を使用して変換係数情報を符号化する。ヘッダ情報は、複数の異なる確率分布を有するシンタックス要素の種類を含む。これらの確率分布は、正確には、指数ゴロム符号の予期されたものとはならないことがある。従って、指数ゴロム符号は、シャノン・エントロピー（Ｓｈａｎｎｏｎ  ｅｎｔｒｏｐｙ）に近づくことはできない。表２は、３つの異なるシンタックス要素のためのＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３のプリフィックスにおける「０」および「１」の数および確率を示している。
【表２】
2012502573.tif 000004
表２：異なるシンタックス要素のＶＬＣ符号のプリフィックスにおける０および１の確率分布
【００３６】
ＣＩＦシーケンスＦｏｒｅｍａｎ（３００フレーム、３０ｆ／ｓ）を統計データを得るために使用した。プロファイルはベースラインとし、レート制御を有効にし、目標ビット・レートを３０００２０ｂｐｓに設定した。符号化器パラメータ「ｎｕｍｂｅｒＲｅｆｅｒｅｎｃｅＦｒａｍｅｓ」を２に設定した。従って、シンタックス要素ｒｅｆ＿ｉｄｘは２つのオプションの値（０および１）のみを有していた（これは、指数ゴロム符号の例外的な場合、即ち、Ｈ．２６４／ＡＶＣ規格におけるトランケートされた指数ゴロム符号である。）。表２から理解できるように、０および１の確率は、シンタックス要素ごとに明らかに異なる。即ち、各プリフィックス内に冗長性が存在する。この現象は、以下の理由により発生する。
【００３７】
隣接するマクロブロックにおける量子化パラメータＱＰは、ほとんど同一である。即ち、「ｍｂ＿ｑｐ＿ｄｅｌｔａ＝０」の確率は、半分より多く、指数ゴロム符号によるプリフィックスにおいて「１」がより多く現れる。
【００３８】
大抵のマクロブロックはスキップされない。即ち、「ｍｂ＿ｓｋｉｐ＿ｒｕｎ＝０」の確率は、半分より大きく、指数ゴロム符号によるプリフィックスにおいて「１」がより多く現れる。
【００３９】
参照フレームは、大抵、直前のフレームであり、即ち、「ｒｅｆ＿ｉｄｘ＝０」の確率は、半分より大きく、トランケートされた指数ゴロム符号によるプリフィックスにおいて「０」がより多く現れる。
【００４０】
プリフィックスにおける「０」および「１」の不均一な分布を利用して、さらなる圧縮を行うことができる。
【００４１】
従って、例えば幾らかの特定のシンタックス要素の可変長符号の、プリフィックスにおけるバイナリ・シンボルの不均一な分布による冗長性を取り除くことが提案される。
【００４２】
これにより、可変長符号化の圧縮能力が改善される。
【００４３】
本発明は、従来の可変長符号化の後に幾つかの数のＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＣ３のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３を共にグループ化し、算術符号化、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）に基づく符号化方法、レンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）に基づく符号化方法、または、他のロスレス圧縮方法を使用して、バイナリ・シンボルの不均一な分布による多数のＶＣＬ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３内の冗長性をさらに取り除くことを提示する。
【００４４】
算術符号化は、ビットストリームにおける「０」または「１」の確率を符号化して、復号器に確率分布を示す。
【００４５】
レンペル・ジフ・ウェルチ（ＬＺＷ：Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）に基づく圧縮方法やレンペル・ジフ・ルノー（ＬＺＲ：Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｒｅｎａｕ）の圧縮方法のようなレンペル・ジフ（ＬＺ：Ｌｅｍｐｅｌ‐Ｚｉｖ）に基づく圧縮方法は、繰り返し文字列のディクショナリに基づくアダプティブなディクショナリ圧縮方法である。大抵のＬＺ方法では、このディクショナリは、符号化の間にアダプティブに構築され、また、ディクショナリは符号化の間と同様に復号の間に構築できるため、復号器に送信される必要はない。他の圧縮方法では、ビットストリーム内にディクショナリを挿入することが必要である。
【００４６】
一般に、ＬＺ圧縮法は、再び現れるデータの文字列をテーブル内のエントリを参照することによって置換するためにテーブルを利用する。大抵のＬＺ方法では、このテーブルは、入力における従前のデータから動的に作成される。テーブル自体は、ホフマン符号化されることが多い。ＬＺ圧縮の例は、レンペル・ジフ・ウェルチ（ＬＺＷ：Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）によって圧縮されたデータからなるＧＩＦ画像、および、レンペル・ジフ・ルノー（ＬＺＲ：Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｒｅｎａｕ）の圧縮方法を利用したｚｉｐ圧縮に存在している。
【００４７】
図１に示されている第１の例示的な実施の形態においては、ＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３の圧縮能力をさらに改善するために、バイナリ・アルファベットの算術符号化が使用される。この例示的な実施の形態は、以下の各ステップを含む。
【００４８】
（１）様々なシンタックス要素の符号化に従来のＶＬＣ、例えば、Ｈ．２６４／ＡＶＣを使用するステップ。
【００４９】
（２）幾つかの特定のＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３を共にグループ化するステップ。例えば、１つのスライス内のｍｂ＿ｑｐ＿ｄｅｌｔａの各プリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３の全てを共にグループ化し、１つのスライス内のｍｂ＿ｓｋｉｐ＿ｒｕｎの各プリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３の全てを共にグループ化する。ｒｅｆ＿ｉｄｘなどの他のシンタックス要素やシンタックス要素に関連する係数も、同様に取り扱うことができる。
【００５０】
（３）「０」および「１」の不均一な分布による冗長性を取り除くために各グループＦＢＳ内のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３の算術符号化を行うステップ。これにより、圧縮された符号Ａ‐Ｃが生成される。ホフマン符号化と比較して、算術符号化の主な利点は、バイナリ・アルファベットのためにさえも、更なるブロッキング（またはグループ化）が必要にならない点である。通常、バイナリ文字列の算術符号化は、そのシャノン・エントロピー・レート（Ｓｈａｎｎｏｎ  ｅｎｔｒｏｐｙ  ｒａｔｅ）にほぼ到達する。
【００５１】
（４）アダプティブなバイナリ・アルゴリズム符号化が使用されない場合、圧縮されたビットストリームＡ‐Ｃに「０」または「１」の確率に関する情報を追加すると有利である。算術復号器は、正確な復号のために、符号化器で使用されるものと同じ「０」および「１」のシンボル確率を使用する必要がある。デフォルトのシンボル確率が使用される場合、得られるビット・レートは、最適なものから逸脱することとなり、従って、依然として次善のものにすぎない。よって、符号化のために各シンタックス要素の実際のシンボル確率を使用し、使用したシンボル確率を圧縮されたデータと共に復号器に送信すると有利である。上述した例において使用した確率精度０．０１の場合には、表現を行うのに７ビット（１／１２８）で十分である。このオーバーヘッドは、算術符号化によるビット減少に対し、十分に無視できるものである。
【００５２】
アダプティブなバイナリ・アルゴリズム符号化が使用される場合、符号化処理の間および復号処理の間に確率がアダプティブに計算され、シンボル確率についてのサイド情報を符号化器から復号器に送信する必要はない。
【００５３】
例示的には、従来のＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３のさらなる算術符号化による表２のシンタックス要素のビット減少は、ｍｂ＿ｑｐ＿ｄｅｌｔａについては、約
【数１】
2012502573.tif 000005
ビットであり、これは、約１０．７％のビット・レートの減少に相当し、ｍｂ＿ｓｋｉｐ＿ｒｕｎについては、約
【数２】
2012502573.tif 000006
ビットであり、これは、約１４．５％のビット・レートの減少に相当し、ｒｅｆ＿ｉｄｘについては、約
【数３】
2012502573.tif 000007
ビットであり、これは、約１４．５％のビット減少に相当する。
【００５４】
（５）オプションとして、１つ以上のフラッグ・ビットを挿入するステップが上記例示的な実施の形態に含まれてもよい。このフラッグ・ビットは、各プリフィックスがさらに圧縮されること、および／または、どの圧縮方法によって各プリフィックスがさらに圧縮されるか、を示す。
【００５５】
サフィックスＳＦＦＸ１，ＳＦＦＸ２，ＳＦＦＸ３から形成されたビットシーケンスＳＢＳを、圧縮された符号Ａ‐Ｃに付加してもよい。
【００５６】
図２に示されている第２の例示的な実施の形態においては、プリフィックスをさらに圧縮するためにＬＺ、ＬＺＲ、またはＬＺＷ圧縮が使用される。この別の実施の形態は、以下の各ステップを含み得る。
【００５７】
（１）様々なシンタックス要素の符号化に従来のＶＬＣ、例えば、Ｈ．２６４／ＡＶＣを使用するステップ。
【００５８】
（２）幾つかの特定のＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３のプリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３を共にグループ化するステップ。例えば、１つのスライス内のｍｂ＿ｑｐ＿ｄｅｌｔａの各プリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＦＸ３の全てを共にグループ化し、１つのスライス内のｍｂ＿ｓｋｉｐ＿ｒｕｎの各プリフィックスＰＲＦＸ１，ＰＲＦＸ２，ＰＲＸ３の全てを共にグループ化する。ｒｅｆ＿ｉｄｘなどの他のシンタックス要素やシンタックス要素に関連する係数も、同様に取り扱うことができる。
【００５９】
（３）グループ化されたプリフィックスＦＢＳをさらに圧縮するために、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）に基づく方法（例えば、ｚｉｐ圧縮）、または、レンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）に基づく方法を使用するステップ。この結果として、別の圧縮された符号ＬＺ‐Ｃが得られる。
【００６０】
（４）オプションとして、１つ以上のフラッグ・ビットを挿入するステップが上記別の例示的な実施の形態に含まれてもよい。このフラッグ・ビットは、各プリフィックスがさらに圧縮されること、および／または、どの圧縮方法によって各プリフィックスがさらに圧縮されるか、を示す。
【００６１】
サフィックスＳＦＦＸ１，ＳＦＦＸ２，ＳＦＦＸ３から形成されたビットシーケンスＳＢＳを、別の圧縮された符号ＬＺ‐Ｃに付加してもよい。
【００６２】
プリフィックスまたは幾つかのＶＬＣ符号化された符号語を共にグループ化し、次に、バイナリ・シンボルの不均一な分布による冗長性を取り除くための第２のエントロピー符号化方法を使用する、可変長符号化方法が提示されている。
【００６３】
提示された可変長符号化方法は、ビットストリーム内の１つ以上のビットを使用して、新たなプリフィックス圧縮エントロピー符号化方法が使用されているか、あるいは、従来のエントロピー符号化方法が使用されているかを示す。
【００６４】
幾つかの可変長符号化された符号語のプリフィックスを圧縮するために算術符号化またはレンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）に基づく符号化を使用するアイディアは、オーディオ、画像、ビデオ、３Ｄメッシュ・データ、テキスト、ファイルなどを含むどのようなデータ圧縮の場合にも使用することができる。
【図１】
2012502573.tif 000008
【図２】
2012502573.tif 000009
【手続補正書】
【提出日】平成23年5月12日(2011.5.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
各プリフィックスが、対応するサフィックス内に含まれるビットの数を表すユナリ符号である、プリフィックス‐サフィックス符号のロスレス圧縮は、請求項１の各特徴事項を含む方法によって達成される。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
この方法は、各プリフィックスを第１の連続的なビットシーケンスにグループ化するステップと、各サフィックスを第２の連続的なビットシーケンスにグループ化するステップと、第１の連続的なビットシーケンスから冗長性を取り除くことによって少なくとも第１の連続的なビットシーケンスをロスレス圧縮するステップと、圧縮された第１の連続的なビットシーケンスに第２の連続的なビットシーケンスを付加するステップと、を含む。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
例えば、Ｈ．２６４／ＡＶＣ規格においては、コンテキスト適応型２値算術符号化（ＣＡＢＡＣ：Ｃｏｎｔｅｘｔ  ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｂｉｎａｒｙ  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ）が使用されない場合には、指数ゴロム符号を使用してヘッダ情報の全てを符号化する一方で、コンテキスト適応型可変長符号化（ＣＡＶＬＣ：Ｃｏｎｔｅｘｔ  ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｖａｒｉａｂｌｅ  Ｌｅｎｇｔｈ  Ｃｏｄｉｎｇ）を使用して変換係数情報を符号化する。ヘッダ情報は、複数の異なる確率分布を有するシンタックス要素の種類を含む。これらの確率分布は、正確には、指数ゴロム符号の予期されたものとはならないことがある。従って、指数ゴロム符号は、シャノン・エントロピー（Ｓｈａｎｎｏｎ  ｅｎｔｒｏｐｙ）に近づくことはできない。表２は、３つの異なるシンタックス要素のためのＶＬＣ符号ＶＬＣ１，ＶＬＣ２，ＶＬＣ３のプリフィックスにおける「０」および「１」の数および確率を示している。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
各プリフィックスが、対応するサフィックス内に含まれるビットの数を表すユナリ符号である、プリフィックス‐サフィックス符号をロスレス圧縮する方法であって、
前記各プリフィックスを第１の連続的なビットシーケンスにグループ化するステップと、
前記各サフィックスを第２の連続的なビットシーケンスにグループ化するステップと、
前記第１の連続的なビットシーケンスから冗長性を取り除くことによって、少なくとも前記第１の連続的なビットシーケンスをロスレス圧縮するステップと、
前記圧縮された第１の連続的なビットシーケンスに前記第２の連続的なビットシーケンスを付加するステップと、を含む、前記方法。
【請求項２】
前記ロスレス圧縮を行うステップは、前記第１の連続的なビットシーケンスの算術符号化を含む、請求項１に記載の方法。
【請求項３】
前記第１の連続的なビットシーケンスの算術符号は、第１の連続的なビットシーケンス内の第１の値の頻度および／または第２の値の頻度に関する情報を含む、請求項２に記載の方法。
【請求項４】
前記ロスレス圧縮を行うステップは、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）圧縮またはレンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）圧縮のようなアダプティブなディクショナリに基づく圧縮を含む、請求項１に記載の方法。
【請求項５】
前記圧縮された第１のビットシーケンスは、前記第１の連続的なビットシーケンスが圧縮されること、および／または、どの圧縮方法によって前記第１の連続的なビットシーケンスが圧縮されるか、を示す１つ以上のフラグ・ビットを含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
第２の連続的なビットシーケンスが付加されている圧縮された第１の連続的なビットシーケンスを含むビットシーケンスを圧縮解除する方法であって、前記ビットシーケンスは圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表しており、前記プリフィックス‐サフィックス符号の各々について、前記方法は、
前記第１の連続的なサブシーケンスを圧縮解除するステップであって、前記圧縮解除された第１の連続的なサブシーケンスが、異なる第２の値を有するストップ・ビットで終了する同一の第１の値を有するビットのシーケンスを含んでいる、該ステップと、
前記圧縮解除された第１の連続的なサブシーケンスを前記ストップ・ビットで前記各プリフィックスにパーティション化するステップであって、各プリフィックスは、前記同一の第１の値を有するビットの前記ストップ・ビットで終了するシーケンスのうちの１つであり、対応するサフィックス内に含まれるビットの数を表す、該ステップと、
前記各プリフィックスによって表される前記ビットの数を使用して、前記ビットシーケンスの残りに含まれる第２の連続的なサブシーケンスを対応する各サフィックスにパーティション化するステップと、を含む前記方法。
【請求項７】
前記第１のサブシーケンス内のビット値の相対的な頻度に関する情報を抽出するステップをさらに含み、
前記第１のサブシーケンスは、前記抽出された情報を使用して算術復号によって圧縮解除される、請求項６に記載の方法。
【請求項８】
前記第１の連続的なサブシーケンスは、アダプティブなディクショナリに基づく圧縮解除の方法、例えば、レンペル・ジフ（Ｌｅｍｐｅｌ‐Ｚｉｖ）圧縮解除の方法によって、またはレンペル・ジフ・ウェルチ（Ｌｅｍｐｅｌ‐Ｚｉｖ‐Ｗｅｌｃｈ）圧縮解除の方法によって圧縮解除される、請求項６または７に記載の方法。
【請求項９】
前記第１の連続的なビットシーケンスが圧縮解除されなければならないこと、および／または、どの圧縮解除方法によって前記第１の連続的なビットシーケンスが圧縮解除されなければならないか、を示す１つ以上のフラッグ・ビットを評価するステップと、
当該評価に従って、前記第１の連続的なサブシーケンスを圧縮解除するステップと、をさらに含む、請求項６〜８のいずれか１項に記載の方法。
【請求項１０】
前記プリフィックス‐サフィックス符号は、オーディオおよび／またはビデオのデータに関する情報を表す整数の可変長符号である、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
前記整数は、同一のタイプのシンタックス要素を表し、当該シンタックス要素は、画像またはビデオのフレームのマクロブロックに関連付けられている、請求項１０に記載の方法。
【請求項１２】
圧縮されたプリフィックス‐サフィックス符号内に符号化された整数またはシンボルを表すビットシーケンスを担持する記憶媒体であって、前記整数またはシンボルは、オーディオおよび／またはビデオに関する情報を表し、前記ビットシーケンスは、各サフィックスを表す第２の連続的なビットシーケンスが付加されている、圧縮された各プリフィックスを表す第１の連続的なサブシーケンスを含んでいる、前記記憶媒体。
【請求項１３】
前記圧縮されたプリフィックス‐サフィックス符号は、請求項１〜５のいずれか１項に記載の方法によって圧縮されている、請求項１２に記載の記録媒体。
【請求項１４】
前記プリフィックス‐サフィックス符号は、オーディオおよび／またはビデオのデータに関する情報を表す整数の可変長符号である、請求項１２または１３に記載の記憶媒体。
【請求項１５】
前記整数は、同一のタイプのシンタックス要素を表し、当該シンタックス要素は、画像またはビデオのフレームのマクロブロックに関連付けられている、請求項１４に記載の記憶媒体。
【国際調査報告】
2012502573.tif 000010
2012502573.tif 000011
2012502573.tif 000012