(57)【要約】【課題】符号化を向上させること。【解決手段】ビットシーケンスを符号化する方法は、前記ビットシーケンスに含まれる「１」の各ランに対して、前記「１」の各ランの長さの単項表現を生成するステップと、前記生成された「１」の各ランの長さの単項表現を連結することによって、第１シーケンスを生成するステップと、前記ビットシーケンスに含まれる「０」の各ランに対して、前記「０」の各ランの長さの単項表現を生成するステップと、前記生成された「０」の各ランの長さの単項表現を連結することによって、第２シーケンスを生成するステップと、前記生成された第１シーケンスと前記第２シーケンスとをビットプレーン符号化するステップとを有する。【選択図】図１
2010178339.tif 000002
【特許請求の範囲】
【請求項１】
ビットシーケンスを符号化する方法であって、
前記ビットシーケンスに含まれる「１」の各ランに対して、前記「１」の各ランの長さの単項表現を生成するステップと、
前記生成された「１」の各ランの長さの単項表現を連結することによって、第１シーケンスを生成するステップと、
前記ビットシーケンスに含まれる「０」の各ランに対して、前記「０」の各ランの長さの単項表現を生成するステップと、
前記生成された「０」の各ランの長さの単項表現を連結することによって、第２シーケンスを生成するステップと、
前記生成された第１シーケンスと前記第２シーケンスとをビットプレーン符号化するステップと、
を有する方法。
【請求項２】
前記第１シーケンスのビットプレーンと前記第２シーケンスのビットプレーンとは、別々に符号化される、請求項１記載の方法。
【請求項３】
前記ビットプレーン符号化は、
ビットプレーンにおける「１」のランの長さの単項表現の第３シーケンスを生成するステップと、
前記ビットプレーンにおける「０」のランの長さの単項表現の第４シーケンスを生成するステップと、
前記生成された単項表現の第３シーケンスと第４シーケンスとをビットプレーン符号化するステップと、
を有する、請求項１又は２記載の方法。
【請求項４】
当該方法は、
（ａ）前記ビットシーケンスの現在のビットを受信するステップと、
（ｂ）前記ビットシーケンスの次のビットを受信するステップと、
（ｃ）前記次のビットが好適な可能であるビット値を有する場合、前記現在のビットの値と異なる値を有するビットを出力し、そうでない場合、前記現在のビットの値を有するビットを出力するステップと、
（ｄ）前記ビットシーケンスのエンドに到達するまで、前記次のビットが現在のビットとして使用され、ステップ（ｂ）及び（ｃ）を繰り返すステップと、
（ｅ）前記出力されたビットを圧縮するステップと、
を有する、請求項１乃至３何れか一項記載の方法。
【請求項５】
第１及び第２符号化ビットプレーンからビットシーケンスを生成する方法であって、
前記第１ビットプレーンを復号化し、単項表現の第１シーケンスを取得するステップと、
前記第２ビットプレーンを復号化し、単項表現の第２シーケンスを取得するステップと、
「１」のランを生成するため、前記第１シーケンスを利用するステップと、
「０」のランを生成するため、前記第２シーケンスを利用するステップと、
前記生成された「０」のランと前記生成された「１」のランとを交互にすることによって、前記ビットシーケンスを生成するステップと、
を有し、
前記第１シーケンスに含まれる各単項表現に対して、対応する長さの「１」のランが生成され、
前記第２シーケンスに含まれる各単項表現に対して、対応する長さの「０」のランが生成される方法。
【請求項６】
当該方法は、
（ａ）好適な可能であるビット値を現在値として使用するステップと、
（ｂ）前記ビットシーケンスの現在のビットを受信するステップと、
（ｃ）前記現在値のビットを出力するステップと、
（ｄ）前記現在のビットが前記好適な可能であるビット値を有する場合、前記現在値を変更するステップと、
（ｅ）前記ステップ（ｂ）〜（ｄ）を繰り返すステップと、
を有する、請求項５記載の方法。
【請求項７】
ビットシーケンスを符号化する装置であって、
前記ビットシーケンスに含まれる「１」の各ランに対して、前記「１」の各ランの長さの単項表現を生成し、前記ビットシーケンスに含まれる「０」の各ランに対して、前記「０」の各ランの長さの単項表現を生成する生成手段と、
前記生成された「１」のランの長さの単項表現を連結することによって、第１シーケンスを生成し、前記生成された「０」のランの長さの単項表現を連結することによって、第２シーケンスを生成する連結手段と、
前記生成された単項表現の第１シーケンスと第２シーケンスとをビットプレーン符号化する手段と、
を有する装置。
【請求項８】
第１及び第２符号化ビットプレーンからビットシーケンスを復号化する装置であって、
前記第１ビットプレーンを復号化し、単項表現の第１シーケンスを取得し、前記第２ビットプレーンを復号化し、単項表現の第２シーケンスを取得する復号化手段と、
「１」のランを生成するため前記第１シーケンスを利用し、「０」のランを生成するため前記第２シーケンスを利用する生成手段と、
前記生成された「０」のランと前記生成された「１」のランとを交互にすることによって、前記ビットシーケンスを構成する構成手段と、
を有し、
前記第１シーケンスに含まれる各単項表現に対して、対応する長さの「１」のランが生成され、
前記第２シーケンスに含まれる各単項表現に対して、対応する長さの「０」のランが生成される装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビットシーケンスを符号化するための方法及び装置に関する。
【背景技術】
【０００２】
ビットシーケンスは、例えば、オーディオ、ビデオ、これらの組み合わせ又はこのようなコンテンツに付随するサイド情報など、デジタルマルチメディアコンテンツの符号化から得られる。符号化されたコンテンツ及びサイド情報の少なくとも１つをコンパクトに表現するためのビットシーケンスの符号化は、記憶容量と伝送帯域を効率的に使用するため重要である。
【０００３】
「０」のみ又は「１」のみの何れかから構成される単純なビットシーケンスでない各ビットシーケンスはまた、１以上の「０」の連続又はラン（ｒｕｎ）と１以上の「１」のランとを交互に有すると理解されてもよく、ここでは、ビットシーケンスの最初のラン又は最後のランでない限り、各ランがそれぞれ異なるビット値を有するビットの他のランの直前及び直後にある１以上の同じ値のビットの連続するサブシーケンスとなる。
【０００４】
ビットシーケンスでは、第１の可能なビット値のビットと、異なる第２の可能なビット値のビットとが、有意に異なる頻度により通常出現する。例えば、「０」が「１」より高い確率で出現し、又はその反対もある。このとき、ビットシーケンスのエントロピーは、ビットシーケンスに含まれるビット数より小さくなる。
【０００５】
この場合、可逆圧縮により削除可能な冗長性がビットシーケンスに存在する。
【０００６】
ビットシーケンスを可逆圧縮するためにエントロピー符号化方法を利用することが知られている。基本的には、（１）ハフマン符号化などの可変長符号化（ＶＬＣ）、（２）算術符号化、及びＬｅｍｐｅｌ−Ｚｉｖ圧縮やＬｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ圧縮などの辞書ベース圧縮の３種類のエントロピー符号化方法が存在する。
【０００７】
エントロピー符号化の効果は、圧縮されたビットシーケンスのエントロピーと圧縮されたビットシーケンスに含まれるビット数との差が、圧縮前のビットシーケンスのエントリピーと当該ビットシーケンスに含まれるビット数との差より小さくなることである。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
符号化を向上させるための新たなアプローチが、検討される。
【課題を解決するための手段】
【０００９】
このような向上を実現させるため、本発明は、請求項１記載のビットシーケンスを符号化する方法と、請求項７記載の対応する装置とを提案する。
【００１０】
ビットシーケンスを符号化する方法は、前記ビットシーケンスに含まれる「１」の各ランに対して、前記「１」の各ランの長さの単項表現を生成するステップと、前記生成された「１」の各ランの長さの単項表現を連結することによって、第１シーケンスを生成するステップと、前記ビットシーケンスに含まれる「０」の各ランに対して、前記「０」の各ランの長さの単項表現を生成するステップと、前記生成された「０」の各ランの長さの単項表現を連結することによって、第２シーケンスを生成するステップと、前記生成された第１シーケンスと前記第２シーケンスとをビットプレーン符号化するステップとを有する。
【００１１】
大部分のケースにおいて、ランレングスの単項表現（ｕｎａｒｙ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）のビットプレーンの全体的なエントロピーは、ビットシーケンスのエントロピーより小さい。従って、よりコンパクトな符号化が実現可能である。確かに、ビットプレーンの全体的なエントロピーは、ビットシーケンスのエントロピーを超えない。
【００１２】
一実施例では、前記第１シーケンスのビットプレーンと前記第２シーケンスのビットプレーンとは、別々に符号化される。
【００１３】
他の実施例では、前記ビットプレーン符号化は、ビットプレーンにおける「１」のランの長さの単項表現の第３シーケンスを生成するステップと、前記ビットプレーンにおける「０」のランの長さの単項表現の第４シーケンスを生成するステップと、前記生成された単項表現の第３シーケンスと第４シーケンスとをビットプレーン符号化するステップと、
を有する。
【００１４】
さらなる他の実施例では、当該方法は、（ａ）前記ビットシーケンスの現在のビットを受信するステップと、（ｂ）前記ビットシーケンスの次のビットを受信するステップと、（ｃ）前記次のビットが好適な可能であるビット値を有する場合、前記現在のビットの値と異なる値を有するビットを出力し、そうでない場合、前記現在のビットの値を有するビットを出力するステップと、（ｄ）前記ビットシーケンスのエンドに到達するまで、前記次のビットが現在のビットとして使用され、ステップ（ｂ）及び（ｃ）を繰り返すステップと、（ｅ）前記出力されたビットを圧縮するステップとを有する。
【００１５】
本方法の上記さらなる実施例では、ビットは、現在ビットが好適な可能であるビット値を有する場合には補助シーケンスに出力され、そうでない場合にはさらなる補助シーケンスに出力されてもよい。
【００１６】
補助シーケンスとさらなる補助シーケンスはそれぞれ、ランのビットの異なる可能な位置に対応するサブシーケンスを有してもよい。このとき、本方法のさらなる他の実施例はさらに、現在ランにおける現在ビット及びその位置に対応するサブシーケンスの１つにビットを出力するステップを有してもよい。
【００１７】
本発明はさらに、請求項５記載の第１及び第２符号化ビットプレーンからビットシーケンスを生成する方法と、請求項８記載の対応する装置とを提案する。
【００１８】
ビットシーケンスを生成する方法は、前記第１ビットプレーンを復号化し、単項表現の第１シーケンスを取得するステップと、前記第２ビットプレーンを復号化し、単項表現の第２シーケンスを取得するステップと、「１」のランを生成するため、前記第１シーケンスを利用するステップと、「０」のランを生成するため、前記第２シーケンスを利用するステップと、前記生成された「０」のランと前記生成された「１」のランとを交互にすることによって、前記ビットシーケンスを生成するステップとを有し、前記第１シーケンスに含まれる各単項表現に対して、対応する長さの「１」のランが生成され、前記第２シーケンスに含まれる各単項表現に対して、対応する長さの「０」のランが生成される。
【００１９】
一実施例では、当該方法は、（ａ）好適な可能であるビット値を現在値として使用するステップと、（ｂ）前記ビットシーケンスの現在のビットを受信するステップと、（ｃ）前記現在値のビットを出力するステップと、（ｄ）前記現在のビットが前記好適な可能であるビット値を有する場合、前記現在値を変更するステップと、（ｅ）前記ステップ（ｂ）〜（ｄ）を繰り返すステップとを有する。
【発明の効果】
【００２０】
本発明によると、符号化を向上させることができる。
【図面の簡単な説明】
【００２１】
【図１】図１は、一例となる第１入力シーケンスと、本発明の方法の一実施例の適用において生成される一例となるランレングスシーケンスと、さらなる一例となるランレングスシーケンスと、第１及び第２ビットプレーンセットとを示す。
【図２】図２は、本発明の方法の一実施例の適用において生成される一例となるさらなる一例となるランレングスシーケンスとさらなる一例となるビットプレーンシーケンスとを示す。
【図３】図３は、第２入力シーケンスと、本発明の方法の一実施例の適用において生成される一例となる他の一例となるランレングスシーケンスとを示す。
【発明を実施するための形態】
【００２２】
図１において、３０ビット長の一例となる第１入力ビットシーケンスＢＳが示される。図１の例では、「０」と「１」とがＢＳにおいて等しい頻度で出現し、すなわち、ＢＳには１５個の「０」と１５個の「１」とがある。一例となる第１入力ビットシーケンスＢＳのエントロピーは、
Ｈ（Ｂ）＝−１５＊ｌｏｇ２（１５／３０）−１５＊ｌｏｇ２（１５／３０）＝３０
として計算できる。
【００２３】
このため、ＢＳを表現するため３０ビットが必要であるかのように見える。
【００２４】
しかしながら、一例となる第１入力ビットシーケンスＢＳから、一例となるランレングスシーケンスＲＬＳが生成可能であり、ここでは、ＢＳはＲＬＳから再構成可能である。
【００２５】
ＲＬＳは、例えば、以下の方法の出力ビットから生成される。すなわち、（ａ）入力ビットシーケンスＢＳの現在ビットを受信し、（ｂ）入力ビットシーケンスＢＳの次のビットを受信し、（ｃ）次のビットが、本例では「１」である好適な可能であるビット値を有する場合、現在のビット値と異なる値を有するビットを出力し、そうでない場合には現在のビット値を有するビットを出力し、（ｄ）ビットシーケンスのエンドに到達するまで、次のビットが現在ビットとして使用され、ステップ（ｂ）及び（ｃ）を繰り返す。
【００２６】
ＲＬＳでは、「１」の直前のＢＳの各「０」に対して「１」がある。さらにＲＬＳでは、「１」の直前のＢＳの各「１」に対して「０」がある。
【００２７】
ＢＳは「１」の直前に８個の「０」と、「１」の直前に７個の「１」しか有さないため、「０」と「１」はＢＳとＲＬＳにおいて異なる頻度により出現する。
【００２８】
すなわち、ＲＬＳでは、１４個の「０」しかないが、１６個の「１」がある。このため、ＲＬＳのエントロピーは、
Ｈ（ＲＬＳ）＝−１４＊ｌｏｇ２（１４／３０）−１６＊ｌｏｇ２（１６／３０）＝２９．９０３７６
となる。
【００２９】
このため、ＲＬＳを表現するため、依然として３０ビットが必要となる。
【００３０】
現在ビットが好適な可能であるビット値を有し、ステップ（ｃ）において、さらなる一例となる２つのランレングスシーケンスが、ビットがさらなる第１ランレングスシーケンスである場合、さらなる一例となる２つのランレングスシーケンスはＲＬＳから生成され、そうでない場合には、ビットはさらなる第２ランレングスシーケンスに出力される。
【００３１】
さらなる第１ランレングスシーケンスＲＬＳ０は、ＢＳの対応するビットが「０」であるＲＬＳのビットを有する。また、さらなる第２ランレングスシーケンスＲＬＳ１は、ＢＳの対応するビットが「１」であるＲＬＳのビットを有する。
【００３２】
ＲＬＳ０から、３つの一例となるビットプレーンＣＳ０１，ＣＳ０２，ＣＳ０３の第１セットが生成される。
【００３３】
ＣＳ０１は、「０」値のビットが直前にないＲＬＳ０のビットを含む。
【００３４】
ＣＳ０２は、ＣＳ０１にソートされたＲＬＳ０における「０」値のビットが直前になるＲＬＳ０のビットを含む。このため、ＣＳ０２に含まれるビット数は、ＣＳ０１に含まれる「０」の個数に等しくなる。
【００３５】
最後に、ＣＳ０３は、ＣＳ０２にソートされたＲＬＳ０における「０」値のビットが直前にあるＲＬＳ０のビットを含む。ＣＳ０２について、ＣＳ０３に含まれるビット数は、ＣＳ０２に含まれる「０」の個数に等しい。
【００３６】
ＣＳ０３は「０」を含まないため、ＣＳ０４は存在しない。
【００３７】
ＣＳ０１，ＣＳ０２，ＣＳ０３は、ＣＳ０１，ＣＳ０２，ＣＳ０３の連結から構成される追加的な補助的ビットシーケンスのサブシーケンスであってもよい。第１セットの全体的なエントロピーは、
Ｈ（ＣＳ０１）＋Ｈ（ＣＳ０２）＋Ｈ（ＣＳ０３）＝１１．２４５１
である。
【００３８】
同様に、４つの一例となるビットプレーンＣＳ１１，ＣＳ１２，ＣＳ１３，ＣＳ１４の第２セットが、ＲＬＳ１から生成される。
【００３９】
第２セットの全体的なエントロピーは、
Ｈ（ＣＳ１１）＋Ｈ（ＣＳ１２）＋Ｈ（ＣＳ１３）＋Ｈ（ＣＳ１４）＝１０．３９０３６
である。
【００４０】
従って、ＢＳは依然として第１及び第２セットから再構成可能であるが、第１セットと第２セットの全体的なエントロピーは、ＢＳのエントロピーよりはるかに小さい。
【００４１】
この原理が繰り返し適用されてもよい。すなわち、ＣＳ０１とＣＳ１１の少なくとも１つが入力シーケンスとして選択されてもよい。これは、例えば、図２に示される。ＣＳ０１及びＣＳ１１から、シーケンス０ＲＬＳ及び１ＲＬＳが生成される。０ＲＬＳ及び１ＲＬＳのビットは、２つのシーケンスペア、すなわち、０ＲＬＳ０，０ＲＬＳ１，１ＲＬＳ０，１ＲＬＳ１に分けられる。０ＲＬＳ０，０ＲＬＳ１，１ＲＬＳ０，１ＲＬＳ１のビットは、異なるコンテクストにソートされる。
【００４２】
０ＲＬＳ０のビットは、コンテクスト０ＣＳ０１，０ＣＳ０２，０ＣＳ０３にソートされ、０ＲＬＳ１のビットは、コンテクスト０ＣＳ１１，０ＣＳ１２にソートされる。
【００４３】
また、１ＲＬＳ０のビットは、コンテクスト１ＣＳ０１，１ＣＳ０２にソートされ、１ＲＬＳ１のビットは、コンテクスト１ＣＳ１１，１ＣＳ１２，１ＣＳ１３にソートされる。
【００４４】
従って、ＣＳ０１は、０ＣＳ０１，０ＣＳ０２，０ＣＳ０３，０ＣＳ１１，０ＣＳ１２と置換される。また、ＣＳ１１は、１ＣＳ０１，１ＣＳ０２，１ＣＳ１１，１ＣＳ１２，１ＣＳ１３と置換される。
【００４５】
このため、ＢＳは、ＣＳ０２，ＣＳ０３，ＣＳ１２，ＣＳ１３，ＣＳ１４，０ＣＳ０１，０ＣＳ０２，０ＣＳ０３，０ＣＳ１１，０ＣＳ１２，１ＣＳ０１，１ＣＳ０２，１ＣＳ１１，１ＣＳ１２，１ＣＳ１３により表される。これらのビットプレーンシーケンスを利用することによって、ＢＳの表現の全体的なエントロピーは、１５．５０９７７５となり、ＢＳのエントロピーのほぼ１／２である。
【００４６】
エントロピーの減少は、例えば、ビットプレーンシーケンスのさらなる圧縮のため、コンテクストベースエントロピー符号化又はビットプレーン符号化などを利用することによって、少なくともある程度まで利用可能である。例えば、コンテクストベース算術符号化、コンテクストベースハフマン符号化又は辞書ベース圧縮が利用されてもよい。
【００４７】
エントロピーは符号化性能の単なる概算的な推定値であるが、算術符号化などは、特に入力データサイズが１０２４ビットなどの十分大きなものであるとき、エントロピーをほぼ達成できる。
【００４８】
本発明は、大部分のシーケンスにおいて、連続する「０」の個数又は連続する「１」の個数が大きく相関していることを利用する。
【００４９】
提案された方法は、何れか従来のエントロピー符号化方法と共に利用可能である。エントロピー符号化方法がビットシーケンスに直接適用されたか、又はエントロピー符号化方法が提案された方法において利用されたか示すため、フラグビットがビットストリームに挿入可能である。
【００５０】
図３において、３０ビット長の一例となる第２入力ビットシーケンスＢＳ’が示される。再び、ＢＳ’において「０」と「１」が等しい頻度により出現する。すなわち、ＢＳには１５個の「０」と１５個の「１」とが存在する。この一例となる第２入力ビットシーケンスＢＳ’のエントロピーは３０であり、ＢＳ’は、さらなる圧縮はできないように見える。
【００５１】
しかしながら、ランレングスシーケンスＲＬＳがＢＳから生成された方法と同様にして、他のランレングスシーケンスＲＳ’が一例となる第２入力ビットシーケンスＢＳ’から生成される場合、有意なエントロピーの減少がＲＬＳ’を生成することによって達成できる。
【００５２】
すなわち、ＲＬＳ’は、６個の「０」と２４個の「１」を有し、２１．６５７８４のエントロピーを有する。
【００５３】
「１１１１」から「１」への、「１００１」から「０１」への、「１１１０」から「００１」への、「１１から「０００１」への（最後の２ビットを表すストップシーケンスとして）辞書的マッピングシーケンスを利用することによって、ＲＬＳ’は、約１６．９６のエントロピーを有する８個の「１」と９個の「０」とによる１７ビットのみから構成される圧縮された出力シーケンスＣＯＳ’に変換可能である。
【００５４】
入力ビットシーケンスＢＳは、圧縮対象のより長いビットシーケンスから構成されてもよいし、又は圧縮対象のビットシーケンス全体であってもよい。
【００５５】
長い圧縮対象ビットシーケンスについて、ビットシーケンスをランレングスシーケンスにビット単位により変換することを可能にする本発明の実施例が提案される。すなわち、ビットシーケンスの各ビットを順次生成する第１エンコーダに接続され、これら生成されたビットを受信し、受信した各ビットに対して出力ビットを出力する変換装置があってもよい。これにより、ビットシーケンスのランレングスシーケンスへの変換は、１ビットの遅延のみにより即座に実行可能である。
【００５６】
上記変換装置は、シーケンスＢＳ，ＢＳ’のビットを受信する手段と、出力ビットを符号化する第２エンコーダにビットを出力する手段とを有する。ビット出力手段は、出力ビットの値が以前に受信したビットと現在受信したビットとの値に依存するように構成され、ここで、以前に受信したビットは、ビットシーケンスＢＳ，ＢＳ’において現在受信したビットの直前にある。すなわち、出力されたビットは、現在受信したビットが好適な可能であるビット値を有する場合には以前に受信したビットの値と異なる値を有し、そうでない場合には以前に受信したビットの値を有する。当該装置は、ビット出力後に現在受信いたビットを以前に受信したビットとして使用し、ビットシーケンスＢＳのエンドに到達するまで、ビットの受信及び出力を繰り返すよう構成される。従って、以前に受信した各ビットに対して、対応する出力ビットが存在する。以降のビットを有さず、以前に受信したビットとならないビットシーケンスの最後のビットに対して、好適な可能となるビット値のビットが当該装置により出力される。
【００５７】
当該装置は、「１」に初期化された値を有するカウンターを有してもよく、カウンター値は、以前に受信したビットの値が現在受信したビットの値に等しい場合には１だけ増加し、以前に受信したビットの値が現在受信したビットの値と異なる場合には「１」にリセットされる。
【００５８】
その後、第２エンコーダが、出力ビットのコンテクストベース算術符号化のため構成されてもよく、出力されたビットのコンテクストは、対応する以前に受信したビットの値とカウンター値の少なくとも１つにより規定される。
【符号の説明】
【００５９】
ＢＳ  ビットシーケンス
ＲＬＳ  ランレングスシーケンス
ＣＳ  コンテクストシーケンス
【図１】
2010178339.tif 000003
【図２】
2010178339.tif 000004
【図３】
2010178339.tif 000005
【外国語明細書】
2010178339000001.pdf