(57)【特許請求の範囲】
【請求項１】
それらの各々が画像内の画素の頻度分布若しくは色ないし輝度分布における頻度を表している少なくとも２つのベクトル成分を用いたデータストリームにおけるベクトルの符号化と転送のための方法において、
各ベクトル成分を二進数字列として所定の数のビットプレーンを用いて表わし、その際に前記二進数字列の数字を、それらの優先度に応じて順次連続して配置すべく最下位のビットプレーンから始まって増加する優先度で、最上位ビットプレーンの最大優先度の方向にプレーン方式で占有させ、さらに、
ベクトルの二進数字列の数字を、最上位ビットプレーンから始まって低減するビットプレーンの優先度に応じて、そのつどの二進数字列の数字がデータストリームにファイルするビットプレーン内に存在する場合にのみデータストリームへ符号化し、
その際同じ優先度を有する異なる数字列の数字は、同じビットプレーンの順序で順次データストリームにファイルされることを特徴とする方法。
【請求項２】
前記ベクトルは、変換方式を用いて求められた係数を有する係数ベクトルである、請求項１記載の方法。
【請求項３】
前記係数ベクトルは量子化される、請求項２記載の方法。
【請求項４】
前記ベクトルは、ヒストグラムを表している、請求項１から３いずれか１項記載の方法。
【請求項５】
前記ヒストグラムは、ディジタル画像に基づいた画素の頻度分布若しくは色ないし輝度分布を表している、請求項４記載の方法。
【請求項６】
前記二進数字列の順序がビットデータストリームへの符号化前に再分類によって変更される、請求項１から５いずれか１項記載の方法。
【請求項７】
所定の数のビットプレーンだけを符号化する、請求項１から６いずれか１項記載の方法。
【請求項８】
前記二進数字列を、ビットプレーンの優先順位の低減に伴わせて符号化する、請求項１から７いずれか１項記載の方法。
【請求項９】
それらの各々が画像内の画素の頻度分布若しくは色ないし輝度分布における頻度を表している少なくとも２つのベクトル成分を用いたデータストリームにおけるベクトルの符号化と転送のための装置において、
プロセッサが設けられており、該プロセッサは、
各ベクトル成分を二進数字列として所定の数のビットプレーンを用いて表わし、その際に前記二進数字列の数字を、それらの優先度に応じて順次連続して配置すべく最下位のビットプレーンから始まって増加する優先度で、最上位ビットプレーンの最大優先度の方向にプレーン方式で占有させるステップと、
ベクトルの二進数字列の数字を、最上位ビットプレーンから始まって低減するビットプレーンの優先度に応じて、そのつどの二進数字列の数字がデータストリームにファイルするビットプレーン内に存在する場合にのみデータストリームへ符号化し、
その際同じ優先度を有する異なる数字列の数字は、同じビットプレーンの順序で順次データストリームにファイルするステップが実施できるように構成されていることを特徴とする装置。
【発明の詳細な説明】
【０００１】
本発明は、データストリームにおけるベクトルの符号化と転送のための方法および装置に関している。
【０００２】
このような手法は、公知文献［１］および［２］からも公知であり、そこではマルチメディア情報の処理の際に用いられている。
【０００３】
近年においては、マルチメディア情報、例えばビデオ情報やオーディオ情報の符号化のために、様々な標準規格が勧告されている。
【０００４】
そのような標準規格としては例えば画像符号化の国際標準方式であるＭＰＥＧ４が挙げられる（公知文献［３］参照）。
【０００５】
このような共通の標準規格は、より多くのマルチメディア情報が可用となるように導くものである。これらの情報をユーザーに可用にさせるためには、これらのマルチメディア情報の指標付けが必要である。
【０００６】
そのような指標付けは、通常はマルチメディア情報の特徴を表したいわゆる記述子によって行われている。そのような特徴には、例えばディジタル画像を有した色分布や輝度分布が挙げられる。
【０００７】
これらの記述子は、頻繁にヒストグラムに基づいており、そこでは表記すべき特徴を表す値の頻度が求められている。
【０００８】
文献［１］または［２］からは、そのようなヒストグラムが、ディジタル画像の色分布の説明の枠内で開示されている。このヒストグラム、すなわちカラーヒストグラムを用いることによって、所定の色値または色領域が画素として１つの画像内で現れている度数（頻度）が表される。
【０００９】
そのようなヒストグラムは通常では非常に多くのエントリを有しているので、そのようなヒストグラムの比較はコストがかかる。その上さらに隣接するエントリの多くは類似値を有している。
【００１０】
文献［１］または［２］からは、このようなケースにおいて１つのヒストグラムをハールウエーブレット変換を用いて変換することが開示されている。
【００１１】
図２には、文献［１］または［２］から公知のハールウエーブレット変換（２００）の一次元の４−Ｂｉｎ−ヒストグラムに対する適用例、すなわち４つの度数エントリを有するヒストグラムが概略的に示されている。
【００１２】
図２によれば、所定の演算、詳細には加算（２０１）と減算（２０２）の組合わされたこの変換（２００）によって、４−Ｂｉｎ−ヒストグラムの４つのエントリ、すなわちValue Bin ０（２１０）、Value Bin １（２２０）、Vlue Bin ２（２３０）Value Bin ３（２４０）が、４つのハールウエーブレット係数、すなわち Haar Coeff Index 0（２５０）、Haar Coeff Index 1（２６０） 、Haar Coeff Index 2 （２７０）Haar Coeff Index 3（２８０）に対してマッピングされる。
【００１３】
これらのハールウエーブレット係数は、文献［１］または［２］からも公知のように、引き続き量子化を施されて二進化される、すなわちそれぞれ量子化されたハールウエーブレット係数が、相応の二進数かないしは０か１の二進数字からなる予め設定可能な固定ビット長の数字列に変換されて、その後でビットデータストリームに符号化される。このビットデータストリームは、受信器に伝送される。受信器では、伝送された値が、相応の方式で符号化されヒストグラムで記述された参照ビットデータストリームと比較される。
【００１４】
この手法によれば、２つの所属のビットデータストリームの適用下で比較が可能となり、これらのビットデータストリームを再び所属のヒストグラムへ逆変換させる必要なく、
図３には、文献［１］または［２］による当該符号化の際の１つの手法が概略的に示されている。
【００１５】
図３には、４つの二進化され量子化されたハールウエーブレット係数（３０１〜３０４）のビットプレーン（ビットレベル）表記（３００）が示されており、これは図３の例では７つのビットプレーン（ビットレベル）（３１０〜３１６）を有している。
【００１６】
文献［４］から公知の符号化（３２０）のもとでは、４つのハールウエーブレット係数（３０１〜３０４）が、相前後して所属する二進数のビットプレーンの優先度の低減に応じてビットデータストリーム３５０に格納される。
【００１７】
このことは次のようにして行われる。すなわちハールウエーブレット係数（３０１〜３０４）の符号化（３２０）の際に、それぞれ最初に、所属する最上位のビットプレーンの二進数、いわゆる最上位ビット（ＭＳＢ）（３３１）が、ビットデータストリーム５０の中に格納される。そのつどの符号化すべきハールウエーブレット係数（３０１〜３０４）の最後に符号化すべきビットとして最下位のビットプレーン（０−ビットプレーン（３１０））の二進数、いわゆる最下位ビット（ＬＳＢ）３３２がビットデータストリーム３５０に格納される。
【００１８】
このことは、ビットデータストリーム（３５０）内において、符号化されるハールウエーブレット係数（３６１〜３６７）の二進数が、後続する符号化されたハールウエーブレット係数（３７１〜３７４）の二進数とは別個に格納されることを意味する。
【００１９】
さらに文献［１］または［２］からは、そのようなビットデータストリームを受信機に転送し、そこで比較すべきヒストグラムを表している符号化された同等のさらなるビットデータストリームと比較することが開示されている。
【００２０】
しかしながらこれらの公知の手法は次のような欠点を有している。すなわちビットデータストリームにおいて符号化された情報が次のように転送されること、すなわち２つのヒストグラムの粗い比較には不要なデータストリーム内の情報も一緒に転送されてしまうことである。このことは、使用される伝送帯域幅がそのような比較の際に低減できないことにつながる。
【００２１】
それゆえに本発明の基礎とする課題は、頻度を表す符号化された情報を、公知手法よりもさらに効率的に転送可能にする方法および装置を提供することである。
【００２２】
前記課題は、独立請求項の特徴部分に記載された本発明による方法並びに装置によって解決される。
【００２３】
それらの各々が画像内の画素の頻度分布若しくは色ないし輝度分布における頻度を表している少なくとも２つのベクトル成分を用いたデータストリームにおけるベクトルの符号化と転送のための方法においては、各ベクトル成分が二進数字列として所定の数のビットプレーンを用いて表わされ、その際に二進数字列の数字が、それらの優先度に応じて順次連続して配置されるように最下位のビットプレーンから始まって増加する優先度で、最上位ビットプレーンの最大優先度の方向にプレーン方式で占有させられる。さらにベクトルの二進数字列の数字は、最上位ビットプレーンから始まって低減するビットプレーンの優先度に応じて、そのつどの二進数字列の数字がデータストリームにファイルするビットプレーン内に存在する場合にのみデータストリームへ符号化され、その際同じ優先度を有する異なる数字列の数字は、同じビットプレーンの順序で順次データストリームにファイルされる。
【００２４】
それらの各々が画像内の画素の頻度分布若しくは色ないし輝度分布における頻度を表している少なくとも２つのベクトル成分を用いたデータストリームにおけるベクトルの符号化と転送のための装置においては、以下のステップすなわち、
各ベクトル成分を二進数字列として所定の数のビットプレーンを用いて表わし、その際に前記二進数字列の数字がそれらの優先度に応じて順次連続して配置されるように最下位のビットプレーンから始まって増加する優先度で、最上位ビットプレーンの最大優先度の方向にプレーン方式で占められるステップと、
ベクトルの二進数字列の数字を、最上位ビットプレーンから始まって低減するビットプレーンの優先度に応じて、そのつどの二進数字列の数字がデータストリームにファイルするビットプレーン内に存在する場合にのみデータストリームへ符号化し、その際同じ優先度を有する異なる数字列の数字は、同じビットプレーンの順序で順次データストリームにファイルするステップを実施できるように構成されたプロセッサを有している。
【００２５】
本発明の特筆すべき利点は、ビットデータストリームの二進数の記憶構造にある。これらの二進数は、ビットデータストリーム内に次のようにファイルされる。すなわち既に第１の二進数がビットデータストリーム内で２つのヒストグラムの粗い比較のために用いることができるようにファイルされている。それにより、そのような比較が迅速かつ効率的に実施できる。その上さらに使用する帯域幅は、ビットデータストリームの伝送の際に低減できる。
【００２６】
さらに本発明によれば、ベクトル表現の迅速なスケーリングが可能である。二進数の記憶構造は、正確なベクトル表現から最後の二進数の消去すなわち最下位ビットプレーンの二進数の消去により、粗いベクトル表現の形成を、二進数の再分類なしで可能にする。なぜならこれは転送とヒストグラムの比較の際の頻度の高い演算であるのでこの利点は大きな意味をなす。
【００２７】
その上さらに本発明は、迅速なベクトル比較を可能にする。ベクトルの重要な成分の二進数は、各ビットプレーンの始点において符号化され、直接の読出しが可能である。
【００２８】
本発明による装置は、特に本発明による方法の実施に適しており、以下の明細書で詳細に説明するさらなる別の実施例にも適している。
【００２９】
本発明の別の有利な実施例は、従属請求項に記載される。
【００３０】
以下でさらに説明する改善例は、本発明による方法のみならず、本発明による装置にも関連するものである。
【００３１】
本発明による実施例および以下でさらに詳細に説明する改善実施例は、ソフトウエアでもハードウエアでも、例えば特定の電子回路を利用することで実現可能である。
【００３２】
さらに本発明による実施例および以下で詳細に説明する改善実施例は、本発明による実施例ないし改善例を実施するコンピュータプログラムが記憶された記憶媒体を有したコンピュータプログラムの結果によって実現されてもよい。
【００３３】
別の有利な実施例によれば、ベクトルは、例えばハールウエーブレット変換を用いて求められた係数を備えた係数ベクトルである。
【００３４】
ベクトルの量子化は、ベクトル成分の二進化の前でも可能である。
【００３５】
有利には、ベクトルはヒストグラムで表現される。そのようなヒストグラムには一般にそれぞれ頻度を表したヒストグラムエントリが含まれている。
【００３６】
有利には、このヒストグラムには、ハールウエーブレット変換が施される。なぜなら、それによってデータが情報のロスなしで低減できるからである。データのさらなる低減は、変換されたヒストグラムが量子化される時に得られる。
【００３７】
ディジタル画像の符号化のもとで使用される、本発明による方法の別の有利な実施例によれば、ヒストグラムが頻度分布を表す（例えば当該ディジタル画像に基づく色分布または輝度分布など）。
【００３８】
有利には、ベクトル成分は予め定められた順序に応じて分類される。それにより、選択が符号化すべきデータないしは転送すべきデータから執り行われ、それに伴って符号化効率ないし転送効率がアップする。
【００３９】
符号化効率のさらなる改善は、所定の数のビットプレーンのみを符号化することによって達成される。その際には、最上位のビットプレーンを符号化すると有利である。なぜならそのようなビットプレーンでは最下位のビットプレーンよりも重要な符号化情報が記憶されているからである。
【００４０】
符号化効率のさらなる向上は、二進数字列をビットプレーンの価値の低減と共に符号化することによって得られる。
【００４１】
図面には本発明の実施例が示されており、これらの実施例は以下の明細書で詳細に説明する。この場合、
図１は、本発明の実施例による情報の符号化と転送の際の方法ステップを示したフローチャートであり、
図２は、ハールウエーブレット変換を概略的に表わした図であり、
図３は、従来技法によるハールウエーブレット係数の符号化を表わした図であり図４は、本発明の実施例によるハールウエーブレット変換を概略的に表わした図であり、
図５は、本発明の実施例によるハールウエーブレット係数の符号化を表わした図であり
図６は、本発明の実施例に対する第１変化例による符号化を表わした図であり、この場合二進数の順序が変更されており、
図７は、本発明の実施例に対する第２変化例による符号化を表わした図であり、この場合は、選択されたビットプレーンのみが符号化されている。
【００４２】
実施例：カラーヒストグラムの符号化と転送
以下の明細書に記載する実施例は、カラーヒストグラムの符号化と転送に関するものである。
【００４３】
図１には、カラーヒストグラムの符号化と転送を実施するための概略的な方法ステップが示されている。
【００４４】
以下ではその方法ステップを短くまとめて説明する。
【００４５】
第１の方法ステップ１０１では、カラーヒストグラムが求められる。第２の方法ステップではこのカラーヒストグラムに対してハールウエーブレット変換が適用される。続いて第３の方法ステップ１０３では、ハール変換されたヒストグラムが量子化される。第４の方法ステップ１０４では、ハール変換され量子化されたヒストグラムの値が二進化され、各二進値が所定の数のビットプレーンを有するようになされる。それに続いて第５の方法ステップ１０５では、それらの二進値がビットプレーンの優先度に従ってビットデータストリームにて符号化される。第６の方法ステップでは、ビットデータストリームが転送される。
【００４６】
図４には、このカラーヒストグラム、詳細には、４つのヒストグラムエントリ４０１〜４０４を有する一次元の４−Bin ヒストグラム４００が示されている。これはディジタル化されたカラー画像の色分布を表わしている。
【００４７】
この場合所定の色領域の頻度は、カラーヒストグラム４００の所属のエントリ４７１，４７２，４７３，４７４に相応する。
【００４８】
さらに図４では、文献［1］または［2］に記載されているように、ハールウエーブレット変換４１０の当該カラーヒストグラム４００への適用が概略的に示されている。
【００４９】
このハールウエーブレット変換（これは所定の演算、詳細には加算４１１と減算４１２の組合せである）４１０によって、カラーヒストグラムの４つのエントリ、"Value Bin 0"４０１、"Value Bin 1"４０２、"Value Bin 2"４０３、"Value Bin 3"４０４が、４つのハールウエーブレット係数、"Haar Coeff Index 0"４２０、"Haar Coeff Index 1"４２１、"Haar Coeff Index 2"４２２、"Haar Coeff Index 3"４２３にマッピングされる。
【００５０】
これらのハールウエーブレット係数４２０〜４２３は、文献［1］または［2］に記載されているように、量子化された後に続いて二進化される。すなわち量子化された各ハールウエーブレット係数が相応の二進数に変換されるか、ないしは二進数字０と１からなる予め設定可能な固定のビット長を有する数字列に変換される。
【００５１】
図５には、二進数字列５０１〜５０４がビットプレーン表記において示されている。
【００５２】
第１の数字列５０１は、７ビットのビット長を有しており、第２の数字列５０２は、４ビットのビット長を有し、第３の数字列５０３は、６ビットのビット長を有し、第４の数字列５０４は、３ビットのビット長を有している。
【００５３】
表示に用いられているビットプレーンの数は、全ての数字列の中の最大ビット長に合わせられている。そのため図５においては７つのビットプレーン５１０〜５１６が第１の数字列５０１のビット長に相応して示されている。これらのビットプレーン５１０〜５１６は、それらの優先度に応じて相互に配設されている、つまりビットプレーン５１１はビットプレーン５１０の上に配置され、ビットプレーン５１２はビットプレーン５１１の上に配置され、以下同様に配置されている。
【００５４】
それぞれのビット長に相応して、第１の数字列５０１によれば、７つの全てのビットプレーン５１０〜５１６を所有し、第２の数字列５０２によれば、４つのビットプレーン５１０〜５１３を所有し、第３の数字列５０３によれば、６つのビットプレーン５１０〜５１５を所有し、第４の数字列５０４によれば、３つのビットプレーン５１０〜５１２を所有している。
【００５５】
これらの二進数字列５０１〜５０４のビットデータストリーム５４０への符号化５３０の際には、最上位ビットプレーンの数字（このケースでは第７ビットプレーン５１６）が、最初にビットデータストリーム５４０に格納される。
【００５６】
このケースでは、第１の数字列５０１のみが、第７ビットプレーン５１６に属する数字５５０を有しているので、この数字５５０がビットデータストリーム５４０に格納される。
【００５７】
続いて数字５５１〜５５２（これらは次に高位のビットレベル５１５に対応している）がビットストリーム５４０に格納される。
【００５８】
このようにして残りのビットプレーン５１４，５１３，５１２，５１１，５１０もそれぞれ優先順位の低減に伴わせて処理される。最後に処理されるべきビットプレーンとしてビットプレーン５１０が処理される。
【００５９】
同じビットプレーンに所属している数字は、所属する二進数の順序、このケースでは５０１，５０２，５０３，５０４の順番でビットデータストリーム５４０に格納される。
【００６０】
それにより、ビットデータストリーム内の数字列５０１〜５０４の符号化５３０は、符号化すべき数字が所属しているビットプレーンの優先度に応じて行われる。このケースで優先させるべき特徴は二進数の順序に過ぎない。
【００６１】
最後にビットデータストリーム５４０が受信機に転送される。
【００６２】
以下では第１実施例の代替例を説明する。
【００６３】
第１の代替例：二進数ないしは二進数字列の符号化前の再分類。
【００６４】
図６には、第１実施例に対する第１の代替例が示されている。
【００６５】
この第１の代替例では、二進数ないしは二進数字列６０１〜６０４の順序がビットデータストリーム６４０への符号化６３０前に再分類によって変更される。
【００６６】
二進数ないし二進数字列のこの新たな順序は、６０３の前の６０１，６０４の前の６０２である。
【００６７】
二進数ないし二進数字列６０１〜６０４の再分類された新たな順序は、ディジタルカラー画像の色領域に関するヒストグラムでの二進数ないし二進数字列６０１〜６０４によって表される頻度変更の頻度を考慮する。
【００６８】
第１の新たな二進数字列６０１は、最小度数の頻度領域を表している。次に高い頻度領域は、第２の新たな二進数字列６０３によって表される。新たな第３の二進数字列６０２と新たな第４の二進数字列４０２は、最大頻度の頻度領域を表している。
【００６９】
この図からは、新たな順序が再分類の制約なしで表されていることが認められる。二進数字列の任意の順序も実現可能である。
【００７０】
新たに分類された二進数字列６０１〜６０４のビットデータストリーム６４０への符号化６３０は前記第１の実施例に相応して行われる。
【００７１】
このケースでも、ビットデータストリームへの二進数字列６０１〜６０４の符号化６３０は、符号化すべき数字が所属しているビットプレーンの優先度に応じて行われる。このケースでも優先させるべき特徴は、二進数ないし二進数字列６０１〜６０４の新たに再分類された順序に過ぎない。
【００７２】
第２の代替例：選択されたビットプレーンのみの符号化
図７には、第１の実施例に対する第２の代替例が示されている。
【００７３】
この第２の代替例では、符号化すべきビットプレーンの選択が行われる。この第２の代替例では、上方の４つのビットプレーン７１６，７１５，７１４，７１３の数字のみがビットデータストリーム７４０へ符号化される。
【００７４】
この選択は、符号化すべきビットプレーンの選択の制約とはみなされない。つまりこれは符号化すべきビットプレーンの任意の選択に該当するものである。
【００７５】
選択されたビットプレーン７１６，７１５，７１４，７１３の数字の符号化７３０は、第１の実施例に相応して行われる。
【００７６】
このケースにおいてもビットデータストリームへの二進数字列７０１〜７０４の符号化７３０は、符号化すべき数字が所属するビットプレーンの優先度に応じて行われる。優先させるべき特徴はこのケースにおいても二進数ないし二進数字列７０１〜７０４の順序にすぎない。
【００７７】
符号化すべきビットプレーンの選択に対してはさらに付加的に、二進数の再分類を第１の代替例のように行うことも可能である（第１の代替例と第２の代替例の組合せ）。
【００７８】
この明細書では以下の公知文献を参照した：
［１］  Jens-Rainer Ohm, Bela Makai, "Results of CE CT5 on scalable representation of color histograms", ISO/IEC JTC1/SC29/WG11 M6031, May 2000, Geneva
［２］  Jens-Rainer Ohm, Bela Makai, "Results of CE CT5 on scalable representation of color histograms", ISO/IEC JTC1/SC29/WG11 M6285, Julys 2000, Beijing
［３］  MPEG-4 applications, am 04.10.2000, http://www.cselt.it/mpeg/public/mpeg-4＿applications. zip
【図面の簡単な説明】
【図１】  図１は、本発明の実施例による情報の符号化と転送の際の方法ステップを示したフローチャートである。
【図２】  ハールウエーブレット変換を概略的に表した図である。
【図３】  従来技法によるハールウエーブレット係数の符号化を表した図である。
【図４】  本発明の実施例によるハールウエーブレット変換を概略的に表した図である。
【図５】  本発明の実施例によるハールウエーブレット係数の符号化を表した図である。
【図６】  本発明の実施例に対する第１変化例による符号化を表した図である。
【図７】  本発明の実施例に対する第２変化例による符号化を表した図であり、この場合は、選択されたビットプレーンのみが符号化されている。
【図１】
0004662688.tif 000002
【図２】
0004662688.tif 000003
【図３】
0004662688.tif 000004
【図４】
0004662688.tif 000005
【図５】
0004662688.tif 000006
【図６】
0004662688.tif 000007
【図７】
0004662688.tif 000008