デジタルコンテンツ符号器、復号器、検索装置、符号化方法、検索方法、記録担体、信号、および記憶装置
【課題】ビデオまたはオーディオ等のマルチメディアアイテムの指紋の符号化および復号化を行う方法および装置を提供する。
【解決手段】ビデオセグメントまたはオーディオセグメント等のマルチメディアコンテンツの時間間隔が、１つの低精細指紋および複数の高精細指紋により記述され、各高精細指紋は、前記時間間隔の下位時間間隔に対応し、前記下位時間間隔は、通常、前記時間間隔よりも短い。１つまたは複数の高精細指紋は、時間的に隣り合う署名を参照せずに非予測的に符号化され、１つまたは複数の高精細指紋は、時間的に隣り合う署名から予測的に符号化される。予測符号化は、隣り合う高精細指紋間の差分を計算して、予測差分行列を構成すること、走査パターンに沿ってベクトル化し、一次元ベクトルにすること、および使用される走査方法に基づいて選択される適切な方法により、一次元ベクトルに可逆的符号化を実行することを伴う。
【解決手段】ビデオセグメントまたはオーディオセグメント等のマルチメディアコンテンツの時間間隔が、１つの低精細指紋および複数の高精細指紋により記述され、各高精細指紋は、前記時間間隔の下位時間間隔に対応し、前記下位時間間隔は、通常、前記時間間隔よりも短い。１つまたは複数の高精細指紋は、時間的に隣り合う署名を参照せずに非予測的に符号化され、１つまたは複数の高精細指紋は、時間的に隣り合う署名から予測的に符号化される。予測符号化は、隣り合う高精細指紋間の差分を計算して、予測差分行列を構成すること、走査パターンに沿ってベクトル化し、一次元ベクトルにすること、および使用される走査方法に基づいて選択される適切な方法により、一次元ベクトルに可逆的符号化を実行することを伴う。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本願は、２００９年１０月５日に出願された英国特許出願第０９１７４１７．８号明細書からの優先権を主張するものであり、この英国特許出願は、そのすべてが参照により本明細書に援用される。
【０００２】
本発明は、ビデオまたはオーディオ等のマルチメディアアイテムの署名または指紋の符号化および復号化に関する。
【背景技術】
【０００３】
マルチメディアコンテンツ（オーディオ、イメージ、およびビデオ）を一意に識別する方法として、マルチメディア指紋（一般に署名（シグネチャ）またはロバストハッシュとも呼ばれる）が提案されている。
典型的な指紋方法は、信号処理技法をマルチメディアコンテンツに適用して、記述子を抽出する。これら記述子は、時間サンプル点での空間情報、時間情報、および／または時空間を表すことができる。通常、記述子は、例えば、２（二進数）、３（三進数）、４（四進数）等の少数の値に量子化し得る特徴の高次元ベクトルである。記述子は、例えば、特異値分解(Singular Value Decomposition)（ＳＶＤ）等により、より低次元のある空間に射影することもできる。異なるマルチメディア指紋方法の差別化に使用される重要な特性としては、一意性、ロバスト性、記述子サイズ、検索速度、および時間粒度が挙げられる。
【０００４】
フレーム毎、ある既知の期間、または時間位置でサンプリングする従来の方法により抽出されるビデオ指紋は、何等かの有意性（significance）（例えば、キーフレーム）を有すると考えられる。フレーム毎のサンプリングでは、大きな指紋が生成されることになり、記憶コストおよび伝送コストが高くなる。サンプリング間隔が低いほど、小さな指紋が生成されることになるが、この方法により達成可能な時間粒度に損失が生じる。同様の制限がオーディオ指紋に対しても存在することが当業者には明らかであろう。
【０００５】
通常、可逆符号化方式は、ランレングス符号化(run-length coding)と可変長接頭符号化との何等かの組み合わせを利用する。例えば、可逆符号化は、ファックス機メッセージの符号化およびデジタルイメージファイル形式の圧縮に用途を有する。符号化方式の語頭属性は、他のある符号語に等しい接頭部を有する符号語がないことを指す。ハフマン符号が特定の一例であり、符号語長は、符号化シンボルの確率に従って適応的に選択される。
特定のシンボルセットに対して最適なエントロピーの限界を達成するために、符号語の長さはｌi＝−ｌｏｇ2ｐiである必要がある。但し、ｐiはｉ番目のシンボルの確率である。
しかし、確率が符号器（送信器）には既知であるが、復号器（受信器）には既知ではない場合、ハフマン符号化では、信号伝送時に特定の符号語を特定のシンボルに割り当てることに関してのオーバーヘッドが必要である。これは、いくつかの所定の確率表が使用される場合に、少数のビットを使用して行うことができるため、表へのインデックスのみが送信される。
可変長符号化の別の変形である算術符号化は、シンボルの確率が非整数符号語長に対応する場合、最適な符号語長を達成することができる。一般に、算術符号化は、ハフマン符号化よりも複雑であり、ハフマン符号化は、符号語のセットが固定されるユニバーサル符号よりも複雑である。
ユニバーサル符号は、単調減少分布（ｐi≧ｐi+1）の場合、期待符号語長が、最適な符号語長よりも一定の係数(constant factor)だけ長いという属性を有する。一般に使用される１つのユニバーサル符号は、指数ゴロム（Ｅｘｐ−ゴロムとしても知られている）であり、指数ゴロムは、両裾が広い（大きなインデックスｉを有するシンボルの確率が比較的大きい）指数確率分布の場合に上手く機能する。この符号は、非負整数ｓ(non-negative integer s)により符号語長
【数１】
を使用してパラメータ化される。ｓ＝０，１，２の場合の最初の８つの符号語を以下の表１に示す。
【０００６】
【表１】
【０００７】
ランレングス符号化は、単一のシンボル表現およびその後に続くそのシンボルのカウント（ランレングス）を使用して、符号化シンボルの連なり(runs)を表す。ランレングス自体は、上述した任意の方法によりエントロピー符号化することができ、その選択は、根本にある確率分布に依存する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
「Ｖｉｄｅｏ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」という名称の本出願人等の同時係属中の日本国特許出願第２０１０−０１４２７９号明細書には、マルチメディア指紋を、低精細指紋（coarse fingerprint）（日本国特許出願第２０１０−０１４２７９号明細書では「ワードヒストグラム」と呼ばれる）、および高精細指紋（fine fingerprint）（日本国特許出願第２０１０−０１４２７９号明細書では「フレーム記述子」と呼ばれる）で構成する方法が開示されており、この日本国特許出願の内容全体は、相互参照により本明細書に援用される。低精細指紋の期間は、複数の高精細指紋の期間に相当する。
典型的な検索アルゴリズムでは、低精細記述子を使用して、一致する時間領域を低い誤検出率で非常に高速に特定する。次に、高精細記述子を使用して、より詳細な検索を時間領域候補に対して実行し得る。
通常、あるマルチメディアコンテンツの高精細指紋の全体サイズは、同じコンテンツの低精細指紋のサイズよりもはるかに大きい。例えば、通常、サイズ比は約１０：１であり得る。他方、高精細指紋へのアクセスは頻繁ではない。すなわち、低精細指紋が一致した時間領域を示す場合のみ、高精細指紋にアクセスする。
したがって、頻繁に使用されない部分の高率圧縮およびその部分への容易なアクセスの両方を可能にする、効率的で柔軟なマルチメディア指紋の符号化方式を案出することが望ましい。
【課題を解決するための手段】
【０００９】
本願は、マルチメディア指紋を効率的かつ柔軟に符号化する装置／方法を開示する。対応する復号化装置／方法も開示される。開示される装置／方法は、高精細記述子の圧縮を導入することを含む。これにより提供される技術的な利点は、全体の指紋サイズがかなり低減することである。ハードウェアコストの低減、または実際に使用できるデータベースサイズの増大において、これが非常に望ましいことは明らかであろう。インデックス付けおよび検索速度が顕著に増大しないことを保証するために、効率的であり、かつ複雑性が低い符号化／復号化方式が開示される。
【００１０】
一般に、この方法は、好ましくは動的に選択される圧縮方式に従って、署名のより大きくかつ使用頻度の低い部分を、効率的に、柔軟かつ高速に符号化する一方で、署名のより小さくかつ使用頻度の高い部分を圧縮しないことを含む。この符号化方式は、一方では、高圧縮率に繋がり、他方では、符号化データへの容易なアクセスおよび符号化データの容易な復号化を可能にするように設計される。
【００１１】
より詳細には、本発明の実施形態は、マルチメディア署名符号化の方法および装置を提供し、この方法および装置は、
・記述子のより大きくかつ使用頻度の低い部分の効率的、かつ柔軟、かつ高速の符号化を実現しながら、記述子のより小さくかつ使用頻度の高い部分を圧縮せず、
・一方では、高圧縮率に繋がり、他方では、符号化データへの容易なアクセスおよび符号化データの容易な復号化を可能にし、
・どのデータを圧縮するかを非符号化データの処理に基づいて判断するようにして、復号化の計算負荷を必要最低限まで低減し、
・より効率的なマルチメディア署名の記憶および伝送を可能にする。
【００１２】
マルチメディアコンテンツの時間間隔(temporal interval)（時間セグメントまたはフラグメントとも呼ばれる）、例えば、ビデオセグメントまたはオーディオセグメントは、１つの低精細指紋および複数の高精細指紋により記述され、各高精細指紋は、前記時間間隔の下位時間間隔(sub-interval)に対応し、通常、前記下位時間間隔は前記時間間隔よりも短い。
【００１３】
１つまたは複数の高精細指紋は、時間的に隣り合う署名を参照せずに非予測的に符号化され、１つまたは複数の高精細指紋は、予測的に、時間的に隣り合う署名から符号化される。
【００１４】
好ましくは、予測符号化は、
隣り合う高精細指紋同士の差分を計算して、予測差分行列を構成すること、
前記予測差分行列を走査し、行、列、対角線、または任意の適した走査パターンに沿ってベクトル化することにより一次元ベクトルにすること、および
適切な方法により一次元ベクトルに対して可逆的符号化を実行すること
を伴い、
適切な方法は、好ましくは、少なくとも部分的に、使用される走査方法に基づいて選択される。しかし、他の形態の予測符号化を代わりに使用してもよいことが理解されるであろう。
【００１５】
より具体的には、本発明によれば、デジタルデータの時間シーケンスを符号化するように動作可能なデジタルコンテンツ符号器が提供され、
この符号器は、
時間シーケンスの間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋を生成するように動作可能な低精細デジタル指紋生成器と、
間隔について複数の高精細デジタル指紋を生成するように動作可能な高精細デジタル指紋生成器であって、各高精細デジタル指紋が、間隔の各下位間隔中のデジタルデータを特徴付ける、高精細デジタル指紋生成器と、
間隔についての高精細デジタル指紋のサブセットに予測符号化を適用するように動作可能な予測符号器と、
を備える。
【００１６】
本発明は、デジタルデータの時間シーケンスのデジタル指紋を符号化するように動作可能なデジタルコンテンツ符号器も提供し、デジタル指紋が、時間シーケンスの間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔についての複数の高精細デジタル指紋とを含み、各高精細デジタル指紋が、間隔の各下位間隔中のデジタルデータを特徴付け、
デジタルコンテンツ符号器は、
間隔の高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細指紋に予測符号化を適用するように構成される予測符号器を備える。
【００１７】
本発明は、符号化デジタルコンテンツを復号化するように動作可能な復号器も提供し、
復号器は、
デジタルデータの時間シーケンスの符号化データを受信するように動作可能な受信器であって、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付けるとともに、予測符号化されている少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む、受信器と、
予測符号化されている高精細デジタル指紋を復号化するように動作可能な予測復号器と、
を備える。
【００１８】
本発明は、デジタルデータの時間シーケンスの符号化データのデータベースを検索するように動作可能な検索装置も提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化された少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含み、
検索装置は、
入力された低精細デジタル指紋をデータベース内の低精細デジタル指紋と比較して、入力された低精細デジタル指紋に一致するデータベース内の低精細デジタル指紋を識別するように動作可能な指紋照合器と、
予測符号化された高精細デジタル指紋を復号化するように動作可能な予測復号器を含む復号器とを備え、
復号器は、入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する間隔のみの高精細デジタル指紋を復号化するように構成される。
【００１９】
本発明は、デジタルデータの時間シーケンスを符号化する方法も提供し、
この方法は、
時間シーケンスの間隔中のデジタルデータを特徴付ける低精細デジタル指紋を生成すること、
間隔について複数の高精細デジタル指紋を生成することであって、各高精細デジタル指紋は、間隔の各下位間隔中のデジタルデータを特徴付ける、生成すること、および
間隔の高精細デジタル指紋のサブセットにのみ予測符号化を適用すること
を含む。
【００２０】
本発明は、デジタルデータの時間シーケンスのデジタル指紋を符号化する方法も提供し、デジタル指紋は、時間シーケンスの間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔についての複数の高精細デジタル指紋とを含み、各高精細デジタル指紋は、間隔中の各下位間隔中のデジタルデータを特徴付け、
この方法は、
間隔についての高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細指紋に予測符号化を適用することを含む。
【００２１】
本発明は、符号化デジタルコンテンツを復号化する方法も提供し、
この方法は、
デジタルデータの時間シーケンスの符号化データを受信することであって、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む、受信すること、および
予測符号化された高精細デジタル指紋を復号化すること
を含む。
【００２２】
本発明は、デジタルデータの時間シーケンスの符号化データのデータベースを検索する方法も提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含み、
この方法は、
入力された低精細デジタル指紋をデータベース内の低精細デジタル指紋と比較して、入力された低精細デジタル指紋に一致するデータベース内の低精細デジタル指紋を識別する検索プロセスと、
間隔について予測符号化された高精細デジタル指紋を復号化する復号化プロセスと
を含み、
復号化プロセスは、入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する間隔についてのみ、高精細デジタル指紋を復号化するように実行される。
【００２３】
本発明は、上述した符号化方法、復号化方法、および／または検索方法の実行が動作可能となるようにプログラマブル処理装置をプログラムするコンピュータ可読プログラミング命令を記憶する物理的に具現されるコンピュータプログラム記憶装置も提供する。
【００２４】
本発明は、上述した符号化方法、復号化方法、および／または検索方法の実行が動作可能となるようにプログラマブル処理装置をプログラムするコンピュータ可読プログラミング命令を搬送する信号も提供する。
【００２５】
本発明は、デジタルデータの時間シーケンスの符号化データを搬送する記録担体をさらに提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む。
【００２６】
本発明は、デジタルデータの時間シーケンスの符号化データを搬送する信号をさらに提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む。
【００２７】
これより、添付図面を参照して、本発明の実施形態を例としてのみ説明する。
【図面の簡単な説明】
【００２８】
【図１】実施形態における符号装置のブロック図を示す。
【図２】実施形態におけるデジタル署名を符号化する動作のフローチャートを示す。
【図３】実施形態における復号装置のブロック図を示す。
【図４】実施形態における予測差分行列の列走査を示す。
【図５】実施形態におけるベクトル化された予測差分行列の符号方式を示す。
【図６】裾の広い分布を有するゼロランレングスへの良好な適合を提供するために、指数ゴロム符号が実施形態においてどのように使用されるかを示す。
【図７】８９×１７０三進値と８９×２７２二進値との比較を示す。
【図８】８９×１７０三進値と８９×２７２二進値との比較を示す。
【発明を実施するための形態】
【００２９】
図１は、実施形態における符号装置のブロック図を示し、図２は、マルチメディア署名を符号化するために装置により実行される処理動作を示す。
【００３０】
図３は、実施形態における復号装置のブロック図を示す。
【００３１】
図１および図３に示される装置はそれぞれ、コンピュータプログラム命令に従って処理動作を実行するようにプログラムされたプログラマブル処理装置を備える。
したがって、本発明の実施形態は、ＣＤ−ＲＯＭもしくは他の記憶装置等のコンピュータプログラム製品（図１では２８で示され、図３では１２２で示される）またはプログラマブル処理装置をプログラムするコンピュータプログラム命令を供給する信号（図１では３０で示され、図３では１２４で示される）を含む。
しかし、図１および／または図３に示される装置の構成要素が、代替として、ハードウェア構成要素であってもよいことが理解されるであろう。
【００３２】
開示される符号化方法では、マルチメディアコンテンツの時間間隔（時間セグメントまたはフラグメントとも呼ばれる）、例えば、ビデオセグメントまたはオーディオセグメントは、１つの低精細指紋および複数の高精細指紋により記述され、各高精細指紋は、前記時間間隔の下位時間間隔に対応し、通常、前記下位時間間隔は前記時間間隔よりも短い。
【００３３】
限定ではなく例として、そのようなマルチメディア指紋抽出方法が、「Ｖｉｄｅｏ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」という名称の上で参照した同時係属中の日本国特許出願第２０１０−０１４２７９号明細書に記載されており、この特許では、時間ビデオセグメント全体は、１つの低精細指紋と、時間セグメントの各フレームにつき１つずつの複数の高精細指紋とにより記述される。
【００３４】
コンテンツ署名を抽出するために、マルチメディアコンテンツを同じ長さの時間セグメントに分割し得るが、または代替として、可変長セグメントを使用してもよい。例えば、可変長は、ビデオもしくはオーディオのショット境界または顕著な変化を検出することにより決定し得る。
【００３５】
好ましい実施形態では、低精細指紋は高精細指紋から抽出される。したがって、可変長セグメントが使用される場合、すべての高精細記述子をマルチメディアコンテンツから抽出した後、時間セグメントを決定することが可能である。そのような実施形態では、高精細記述子の解析を使用して、適した時間セグメントを決定し得る。
【００３６】
ビデオ署名の場合の本発明の好ましい実施形態では、ビデオは時間セグメントに分割され、各時間セグメントの全体は、１つの低精細指紋と、時間セグメントのフレームまたはピクチャ毎に１つずつの複数の高精細指紋とにより記述される。時間セグメントの複数の高精細指紋は、ピクチャグループ(groups of pictures)（ＧＯＰs）にグループ化される。
【００３７】
本発明の好ましい実施形態では、ｔｅｍｐｏｒａｌ＿ｓｅｇｍｅｎｔ（ ）と示される時間セグメントの圧縮表現を符号化するために必要なシンタックスを表２に概説する。
【００３８】
【表２】
【００３９】
シンタックス要素の説明
・ｇｒｏｕｐ＿ｏｆ＿ｐｉｃｔｕｒｅｓ（ ）−少なくとも１つの符号化されたピクチャ指紋で構成されるピクチャグループを指定する。
・ｓｅｇｍｅｎｔ＿ｌｅｎｇｔｈ−ピクチャ数単位で時間セグメントの長さを指定する。マルチメディア署名シンタックスの上位レベル部で指定される（時間セグメントに対して定義されるか、またはコンテンツ全体で一定）。
【００４０】
キーピクチャ指紋は、時間的に隣り合うピクチャを参照せずに、非予測的に符号化されるピクチャ指紋であり、これはＫＰと記される。予測ピクチャ指紋は、時間的に隣り合うピクチャから予測的に符号化され、これはＰＰと記される。ＧＯＰは、時間的に最初のＫＰおよび次のＫＰ前のすべてのＰＰを含む、２つのＫＰ間のピクチャ指紋の集合であると定義される。したがって、ＧＯＰは、キーピクチャおよび０以上の予測ピクチャからなる。
【００４１】
本発明の好ましい実施形態では、ピクチャ指紋はＭ個の要素のベクトルであり、各要素はＮ＝３個の可能な値をとる。すなわち、要素は三進数である。単一のキーピクチャ内の情報の冗長性は非常に小さいため、これらピクチャ指紋には圧縮が適用されず、符号化は二進表現を使用して行われる。
【００４２】
本発明の好ましい実施形態では、三進数指紋の２つの異なる二進表現が考えられる。
１．連続した５つの三進数要素のそれぞれが、１バイトにパッキングされる（３5＝２４３＜２５６＝２8）。例えば、Ｍ＝３４０の場合、ピクチャ指紋全体では、８×３４０／５＝５４４ビットが必要である（６８バイト）。この方法の実施は、８ビット算術を使用して容易に行うことができる。このパッキング方法は５ｔ→８ｂと記される。別の例として、Ｍ＝３８４の場合、ピクチャ指紋全体では、８×３８０／５（５ｔ→８ｂ）＋７×４／４（４ｔ→７ｂ）＝６１５ビットが必要である（１ビットの予備を有する７６バイト）。
２．連続した１７の三進数要素のそれぞれが、２７ビットにパッキングされる（３17＝１２９１４０１６３＜１３４２１７７２８＝２27）。最後のバイト列へのパッキングは、取得した２７ビットを、特定のバイト位置で、必要なビット量だけビットシフトすることにより達成される。例えば、Ｍ＝３４０の場合、２７×３４０／１７＝５４０であるため、この方法では、ピクチャ毎に４ビットが節約され、その４ビットを追加の情報（例えば、フラグ）の送信に使用することができる。２７ビットが一変換で使用されるため、３２ビット算術ベースの実施が可能である。追加の４ビットを有することは、現在のＧＯＰ内のすべてゼロの差分ベクトルを、追加のバイトを費やさずに信号伝送することができるようなバイト位置合わせが要求される場合、有用である。このパッキング方法は１７ｔ→２７ｂと記される。別の例として、Ｍ＝３８４の場合、ピクチャ指紋全体では、２７×３７４／１７（１７ｔ→２７ｂ）＋８×１０／５（５ｔ→８ｂ）＝６１０ビットが必要である（６ビットの予備を有する７６バイト）。
【００４３】
あるいは、他の二進表現も可能であり、三進数要素の数に応じて、パッキングの効率と実施の複雑性とのトレードオフを図ることができる。例えば、Ｍ＝２９０の場合、三進数パッキング方法２９ｔ→４６ｂを使用することができ、５ｔ→８ｂパッキングと比較して、４ビットが節約される。
【００４４】
以下、ＫＰの表現に使用されるビット数は、パッキング方法に関係なく「ＫＰビット」と呼ばれる。
【００４５】
本発明の好ましい実施形態では、ｇｒｏｕｐ＿ｏｆ＿ｐｉｃｔｕｒｅｓ（ ）と記されるＧＯＰの圧縮表現を符号化するために必要なシンタックスを表３に概説する。
【００４６】
【表３】
【００４７】
シンタックス要素の説明
・ｋｅｙ＿ｐｉｃｔｕｒｅ−ＫＰビットにパッキングされたキーピクチャ。
・ＫＰ＿ＧＯＰ＿ｆｌａｇ−１に等しい場合、現在のＧＯＰは単一のキーピクチャからなる（ＧＯＰ内に予測ピクチャがない）。そうではなく、０に等しい場合、予測ピクチャが現在のＧＯＰ内に存在する。
・ｌａｓｔ＿ＧＯＰ＿ｆｌａｇ−０に等しい場合、現在のＧＯＰは時間セグメント内の最後のＧＯＰではない。１に等しい場合、現在のＧＯＰはセグメント内の最後のＧＯＰであり、その長さが導出される。
・ＧＯＰ＿ｌｅｎｇｔｈ＿ｍｉｎｕｓ２−ピクチャ数単位のＧＯＰ長から２ピクチャを差し引いたもの。例えば、１つのＫＰおよび１つのＰＰからなるＧＯＰは、０に等しいこのシンタックス要素値を有する。
・ｎｏｎｚｅｒｏ＿ＧＯＰ＿ｆｌａｇ−０に等しい場合、ＰＰが現在のＧＯＰに存在するときは、すべてのＰＰはＫＰに等しく、復号化はスキップされる（ＫＰはｐｐｌｅｎ回、繰り返される）。１に等しい場合、ＰＰは復号化される。
・ｐｒｅｄｉｃｔｅｄ＿ｐｉｃｔｕｒｅｓ（ ）−符号化されたＰＰを有するビットストリームの部分。
【００４８】
本発明の好ましい実施形態では、予測ピクチャは、現在の指紋内の要素と前の指紋内の要素とのモジュロ３差分（modulo 3 difference）を計算することにより変換される。そのように変換された予測ピクチャが予測差分行列を構成し、予測差分行列は、いわゆる「ベクトル化」ステップで走査されて、一次元ベクトルになる。
ベクトル化ステップは、予測差分行列の列を連結することにより行われる場合、１つのＧＯＰ内で、指紋の位置は他のものに比べて変化しない可能性が高いことを利用する。これにより、ゼロランがより長くなり、よりコンパクトな表現になる。
他の代替は、予測差分行列の行を連結し、ジグザグ走査または任意の他の走査パターンで走査することである。ベクトル化走査パターンの選択に応じて、エントロピー符号化方法の異なる選択を行い得る。この選択は、符号化された指紋の統計に応じて、ビデオシーケンス内で動的に行い得る。
符号化されるＧＯＰの構造（ＫＰおよび予測差分行列に変換されたＰＰで構成される）を図４に示す。図４は、予測差分行列の列走査を示すが、上述したように、他の走査方法を使用してもよい。
【００４９】
三進値は、バイトにパッキングされた二進表現を暗黙的に相関付け解除するため、予測差分の生成に使用されている。
これは、図７（８９×１７０三進値であり、白が三進数「０」を表し、グレーが三進数「１」を表し、黒が三進数「２」を表す）と、
図８（８９×２７２二進値であり、白が二進数「０」を表し、黒が二進数「１」を表す）とを比較することにより結論付けることができる。
図８では、ピクチャ内の相関が図７よりもはるかに高く、両方とも、同じＧＯＰ内の指紋要素の最初の半分を表す。
【００５０】
指紋の三進数要素間のモジュロ３差分演算はここでも、３つの三進数シンボル−「０」、「１」、および「２」になる。したがって、予測差分行列は、これら３つの三進数シンボルで構成され、これらは別様に符号化される。
・三進数「１」および「２」−それぞれ１ビットを使用して符号化され、三進数「１」には二進数「０」、三進数「２」には二進数「１」が使用される。各三進数シンボル後、ゼロランのランレングス符号語が挿入される。ゼロが続かない場合、ゼロ長の符号語が使用される。
・三進数「０」−各非ゼロ三進数シンボル後には、ゼロランが続かなければならないため、三進数シンボルは暗黙的に符号化される。
【００５１】
本発明の好ましい実施形態では、ｐｒｅｄｉｃｔｅｄ＿ｐｉｃｔｕｒｅｓ（ ）と記される、予測差分行列の圧縮表現を符号化するために必要なシンタックスを表４に概説する。
【００５２】
【表４】
【００５３】
シンタックス要素の説明
・ｚｅｒｏ＿ｒｌｅ−指数ゴロム符号化(exp-Golomb coding)を使用して符号化される三進数「０」のラン長。
・ｎｏｎ＿ｚｅｒｏ＿ｓｙｍｂｏｌ−０に等しい場合、現在のシンボルは三進数「１」である。１に等しい場合、現在のシンボルは三進数「２」である。
【００５４】
ベクトル化された予測差分行列のこの符号化方式を図５に示し、「ｖｂ」は可変ビット数(variable number of bits)を指し、「１ｂ」は１ビット長を指す。しかし、この符号化方式が唯一の符号化方式ではない。例えば、三進数シンボルを符号化する２つの代替の方法は以下のように進められる。
１．ゼロのゼロ長ランレングスは使用されず、個々の非ゼロシンボルは１ビットを使用して符号化され、追加の１ビットが、次のシンボルの種類（非ゼロまたはゼロ）を信号伝送するために使用される。
２．ゼロのゼロ長ランレングスは使用されず、非ゼロシンボルのランは、ランレングス符号化を使用して符号化される。さらに、１ビットが、次のランのシンボルを信号伝送するために使用される。
【００５５】
ゼロランレングスは、裾が広い分布（裾が広い指数分布またはべき乗分布）を有する。このため、好ましい実施形態では、パラメータｓ＝２を有する指数ゴロム符号が使用される。これは、指数ゴロム符号が、ゼロランレングスの分布に良好な適合性を提供し、複雑性の非常に低い実施に通じるためである。
これは図６に示され、図６は、経験的に取得されたゼロランレングスの確率分布を示す。本発明の代替の実施形態では、パラメータｓが適応的に選択されるとともに、その選択がその他のパラメータを使用して符号化される適応指数ゴロム方式を使用することができ、または代替として、ハフマン符号化または算術符号化のような他の何等かの適した符号化方式を使用してもよい。
【００５６】
符号器の要件は、生成されるビットストリームが前の項で概説したシンタックスに従うことである。したがって、潜在的にそれぞれが異なる圧縮性能に繋がる多くの可能な符号化方法がある。以下に、符号器の好ましい実施形態を説明する。
１．各時間セグメントのピクチャ指紋を、その他の時間セグメントから独立して符号化する。
２．セグメントの最初のピクチャ指紋をＫＰとして符号化する。
３．１ピクチャ分先に進む。現在のピクチャがセグメント内の最後のピクチャである場合、ステップ６に進む。
４．前のピクチャとの相関性について現在のピクチャをテストし、テスト結果が低相関性を示す場合、現在のピクチャ指紋をＫＰとして符号化する。
５．ステップ４において、ＫＰが挿入されなかった場合、予測差分を予測差分行列に記憶し、ステップ３に戻る。その他の場合、ステップ６に進む。予測差分は、現在のピクチャ指紋と前のピクチャ指紋との間のモジュロ３減算により取得される。
６．記憶された予測差分行列をベクトルに変換し（ベクトル化ステップ）、エントロピー符号化をそのようなベクトルに適用することにより、前のＫＰから現在のピクチャ前の最後のピクチャまでのすべての指紋を１つのＧＯＰとして符号化する。ＧＯＰの冒頭に、必要なすべてのパラメータ、例えば、ＧＯＰ長、エントロピー符号化パラメータ等を符号化する。任意的に、ベクトル化方法およびエントロピー符号化の選択が行われ、これもパラメータとして符号化される。
【００５７】
ステップ４での相関テストは、予測差分がランレングス符号器を使用して符号化され、そのようなデータのビット長がＫＰのビット長（ＫＰビット）と比較される、単純な圧縮効率性テストからなり得る。別の例は、単に差分ピクチャ内の三進数ゼロをカウントし、それを閾値と比較することによる。
【００５８】
好ましい実施形態では、フラグが使用されて、圧縮された高精細指紋の存在が示され、好ましくは、１ビットフラグが使用される。
好ましい実施形態では、単一の圧縮フラグが、複数の時間セグメントを含むマルチメディアアイテム全体の指紋に使用される。代替の実施形態では、マルチメディアアイテムの時間セグメント毎に１つずつ、高精細指紋の各セグメントの圧縮の存在を示す複数の圧縮フラグがあってもよい。圧縮フラグは、計算リソースが記憶／送信リソースよりもはるかに少ない場合に圧縮を使用しないという選択肢を許容する。
さらに、システム内で、最も頻繁にアクセスされるコンテンツを圧縮せず、他のすべてのコンテンツを圧縮することが望ましい場合がある。これにより、利用可能な計算リソース（ＣＰＵ時間、メモリサイズ、ハードディスク帯域幅等）のより最適なバランスを達成することが可能である。例えば、最後の７日間のＴＶのインデックスを圧縮しない状態で記憶し得る一方で、すべてのより古いコンテンツが圧縮された状態で記憶される。
単一のマルチメディアコンテンツの指紋のうちのいくつかを圧縮形式で記憶し、指紋のうちのいくつかを非圧縮形式で記憶することが望ましい場合もある。
【００５９】
好ましい実施形態では、圧縮フラグが「１」に設定される場合、対応する高精細記述子は圧縮される。圧縮フラグが「０」に設定される場合、圧縮は対応する高精細記述子に適用されない。
【００６０】
符号化は、抽出方法の一環をなしてもよく、または随時適用される別個の方法であってもよく、例えば、高精細指紋を抽出し、ローカルシステムに記憶し、次に、低速接続を介して送信する前に符号化される。
【００６１】
本発明の代替の実施形態では、予測符号化または任意の他の適した符号化方法を使用して、低精細記述子を圧縮することもできる。これは、全体の指紋サイズをさらに低減するが、例えば、照合用途で署名を使用する計算複雑性も増大させることになる。
【００６２】
本発明の代替の実施形態では、ＫＰはいかなるパッキングもなく記憶し得る。例えば、三進値を含むＫＰを、ピクセル毎に２ビットを使用して「行」形式で記憶し得る。これは、全体の署名サイズを少し増大させるが、高精細署名ブロックを復号化する全体の複雑性の低減にも繋がる。
【００６３】
さらに、低精細署名に加えて、高精細署名の圧縮ブロックの特徴を時間セグメントの高速照合に使用することもできる。そのような特徴としては、ＫＰ（キーピクチャ）の絶対位置および相対位置、平均および最大等のゼロランの統計等が挙げられる。
【００６４】
検索速度は、多くのマルチメディア指紋用途で非常に重要である。この理由により、圧縮方式が効率的であることが非常に重要である。本明細書において概説した圧縮方式は、低複雑性という目標を達成する。
【技術分野】
【０００１】
関連出願
本願は、２００９年１０月５日に出願された英国特許出願第０９１７４１７．８号明細書からの優先権を主張するものであり、この英国特許出願は、そのすべてが参照により本明細書に援用される。
【０００２】
本発明は、ビデオまたはオーディオ等のマルチメディアアイテムの署名または指紋の符号化および復号化に関する。
【背景技術】
【０００３】
マルチメディアコンテンツ（オーディオ、イメージ、およびビデオ）を一意に識別する方法として、マルチメディア指紋（一般に署名（シグネチャ）またはロバストハッシュとも呼ばれる）が提案されている。
典型的な指紋方法は、信号処理技法をマルチメディアコンテンツに適用して、記述子を抽出する。これら記述子は、時間サンプル点での空間情報、時間情報、および／または時空間を表すことができる。通常、記述子は、例えば、２（二進数）、３（三進数）、４（四進数）等の少数の値に量子化し得る特徴の高次元ベクトルである。記述子は、例えば、特異値分解(Singular Value Decomposition)（ＳＶＤ）等により、より低次元のある空間に射影することもできる。異なるマルチメディア指紋方法の差別化に使用される重要な特性としては、一意性、ロバスト性、記述子サイズ、検索速度、および時間粒度が挙げられる。
【０００４】
フレーム毎、ある既知の期間、または時間位置でサンプリングする従来の方法により抽出されるビデオ指紋は、何等かの有意性（significance）（例えば、キーフレーム）を有すると考えられる。フレーム毎のサンプリングでは、大きな指紋が生成されることになり、記憶コストおよび伝送コストが高くなる。サンプリング間隔が低いほど、小さな指紋が生成されることになるが、この方法により達成可能な時間粒度に損失が生じる。同様の制限がオーディオ指紋に対しても存在することが当業者には明らかであろう。
【０００５】
通常、可逆符号化方式は、ランレングス符号化(run-length coding)と可変長接頭符号化との何等かの組み合わせを利用する。例えば、可逆符号化は、ファックス機メッセージの符号化およびデジタルイメージファイル形式の圧縮に用途を有する。符号化方式の語頭属性は、他のある符号語に等しい接頭部を有する符号語がないことを指す。ハフマン符号が特定の一例であり、符号語長は、符号化シンボルの確率に従って適応的に選択される。
特定のシンボルセットに対して最適なエントロピーの限界を達成するために、符号語の長さはｌi＝−ｌｏｇ2ｐiである必要がある。但し、ｐiはｉ番目のシンボルの確率である。
しかし、確率が符号器（送信器）には既知であるが、復号器（受信器）には既知ではない場合、ハフマン符号化では、信号伝送時に特定の符号語を特定のシンボルに割り当てることに関してのオーバーヘッドが必要である。これは、いくつかの所定の確率表が使用される場合に、少数のビットを使用して行うことができるため、表へのインデックスのみが送信される。
可変長符号化の別の変形である算術符号化は、シンボルの確率が非整数符号語長に対応する場合、最適な符号語長を達成することができる。一般に、算術符号化は、ハフマン符号化よりも複雑であり、ハフマン符号化は、符号語のセットが固定されるユニバーサル符号よりも複雑である。
ユニバーサル符号は、単調減少分布（ｐi≧ｐi+1）の場合、期待符号語長が、最適な符号語長よりも一定の係数(constant factor)だけ長いという属性を有する。一般に使用される１つのユニバーサル符号は、指数ゴロム（Ｅｘｐ−ゴロムとしても知られている）であり、指数ゴロムは、両裾が広い（大きなインデックスｉを有するシンボルの確率が比較的大きい）指数確率分布の場合に上手く機能する。この符号は、非負整数ｓ(non-negative integer s)により符号語長
【数１】
を使用してパラメータ化される。ｓ＝０，１，２の場合の最初の８つの符号語を以下の表１に示す。
【０００６】
【表１】
【０００７】
ランレングス符号化は、単一のシンボル表現およびその後に続くそのシンボルのカウント（ランレングス）を使用して、符号化シンボルの連なり(runs)を表す。ランレングス自体は、上述した任意の方法によりエントロピー符号化することができ、その選択は、根本にある確率分布に依存する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
「Ｖｉｄｅｏ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」という名称の本出願人等の同時係属中の日本国特許出願第２０１０−０１４２７９号明細書には、マルチメディア指紋を、低精細指紋（coarse fingerprint）（日本国特許出願第２０１０−０１４２７９号明細書では「ワードヒストグラム」と呼ばれる）、および高精細指紋（fine fingerprint）（日本国特許出願第２０１０−０１４２７９号明細書では「フレーム記述子」と呼ばれる）で構成する方法が開示されており、この日本国特許出願の内容全体は、相互参照により本明細書に援用される。低精細指紋の期間は、複数の高精細指紋の期間に相当する。
典型的な検索アルゴリズムでは、低精細記述子を使用して、一致する時間領域を低い誤検出率で非常に高速に特定する。次に、高精細記述子を使用して、より詳細な検索を時間領域候補に対して実行し得る。
通常、あるマルチメディアコンテンツの高精細指紋の全体サイズは、同じコンテンツの低精細指紋のサイズよりもはるかに大きい。例えば、通常、サイズ比は約１０：１であり得る。他方、高精細指紋へのアクセスは頻繁ではない。すなわち、低精細指紋が一致した時間領域を示す場合のみ、高精細指紋にアクセスする。
したがって、頻繁に使用されない部分の高率圧縮およびその部分への容易なアクセスの両方を可能にする、効率的で柔軟なマルチメディア指紋の符号化方式を案出することが望ましい。
【課題を解決するための手段】
【０００９】
本願は、マルチメディア指紋を効率的かつ柔軟に符号化する装置／方法を開示する。対応する復号化装置／方法も開示される。開示される装置／方法は、高精細記述子の圧縮を導入することを含む。これにより提供される技術的な利点は、全体の指紋サイズがかなり低減することである。ハードウェアコストの低減、または実際に使用できるデータベースサイズの増大において、これが非常に望ましいことは明らかであろう。インデックス付けおよび検索速度が顕著に増大しないことを保証するために、効率的であり、かつ複雑性が低い符号化／復号化方式が開示される。
【００１０】
一般に、この方法は、好ましくは動的に選択される圧縮方式に従って、署名のより大きくかつ使用頻度の低い部分を、効率的に、柔軟かつ高速に符号化する一方で、署名のより小さくかつ使用頻度の高い部分を圧縮しないことを含む。この符号化方式は、一方では、高圧縮率に繋がり、他方では、符号化データへの容易なアクセスおよび符号化データの容易な復号化を可能にするように設計される。
【００１１】
より詳細には、本発明の実施形態は、マルチメディア署名符号化の方法および装置を提供し、この方法および装置は、
・記述子のより大きくかつ使用頻度の低い部分の効率的、かつ柔軟、かつ高速の符号化を実現しながら、記述子のより小さくかつ使用頻度の高い部分を圧縮せず、
・一方では、高圧縮率に繋がり、他方では、符号化データへの容易なアクセスおよび符号化データの容易な復号化を可能にし、
・どのデータを圧縮するかを非符号化データの処理に基づいて判断するようにして、復号化の計算負荷を必要最低限まで低減し、
・より効率的なマルチメディア署名の記憶および伝送を可能にする。
【００１２】
マルチメディアコンテンツの時間間隔(temporal interval)（時間セグメントまたはフラグメントとも呼ばれる）、例えば、ビデオセグメントまたはオーディオセグメントは、１つの低精細指紋および複数の高精細指紋により記述され、各高精細指紋は、前記時間間隔の下位時間間隔(sub-interval)に対応し、通常、前記下位時間間隔は前記時間間隔よりも短い。
【００１３】
１つまたは複数の高精細指紋は、時間的に隣り合う署名を参照せずに非予測的に符号化され、１つまたは複数の高精細指紋は、予測的に、時間的に隣り合う署名から符号化される。
【００１４】
好ましくは、予測符号化は、
隣り合う高精細指紋同士の差分を計算して、予測差分行列を構成すること、
前記予測差分行列を走査し、行、列、対角線、または任意の適した走査パターンに沿ってベクトル化することにより一次元ベクトルにすること、および
適切な方法により一次元ベクトルに対して可逆的符号化を実行すること
を伴い、
適切な方法は、好ましくは、少なくとも部分的に、使用される走査方法に基づいて選択される。しかし、他の形態の予測符号化を代わりに使用してもよいことが理解されるであろう。
【００１５】
より具体的には、本発明によれば、デジタルデータの時間シーケンスを符号化するように動作可能なデジタルコンテンツ符号器が提供され、
この符号器は、
時間シーケンスの間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋を生成するように動作可能な低精細デジタル指紋生成器と、
間隔について複数の高精細デジタル指紋を生成するように動作可能な高精細デジタル指紋生成器であって、各高精細デジタル指紋が、間隔の各下位間隔中のデジタルデータを特徴付ける、高精細デジタル指紋生成器と、
間隔についての高精細デジタル指紋のサブセットに予測符号化を適用するように動作可能な予測符号器と、
を備える。
【００１６】
本発明は、デジタルデータの時間シーケンスのデジタル指紋を符号化するように動作可能なデジタルコンテンツ符号器も提供し、デジタル指紋が、時間シーケンスの間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔についての複数の高精細デジタル指紋とを含み、各高精細デジタル指紋が、間隔の各下位間隔中のデジタルデータを特徴付け、
デジタルコンテンツ符号器は、
間隔の高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細指紋に予測符号化を適用するように構成される予測符号器を備える。
【００１７】
本発明は、符号化デジタルコンテンツを復号化するように動作可能な復号器も提供し、
復号器は、
デジタルデータの時間シーケンスの符号化データを受信するように動作可能な受信器であって、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付けるとともに、予測符号化されている少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む、受信器と、
予測符号化されている高精細デジタル指紋を復号化するように動作可能な予測復号器と、
を備える。
【００１８】
本発明は、デジタルデータの時間シーケンスの符号化データのデータベースを検索するように動作可能な検索装置も提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化された少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含み、
検索装置は、
入力された低精細デジタル指紋をデータベース内の低精細デジタル指紋と比較して、入力された低精細デジタル指紋に一致するデータベース内の低精細デジタル指紋を識別するように動作可能な指紋照合器と、
予測符号化された高精細デジタル指紋を復号化するように動作可能な予測復号器を含む復号器とを備え、
復号器は、入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する間隔のみの高精細デジタル指紋を復号化するように構成される。
【００１９】
本発明は、デジタルデータの時間シーケンスを符号化する方法も提供し、
この方法は、
時間シーケンスの間隔中のデジタルデータを特徴付ける低精細デジタル指紋を生成すること、
間隔について複数の高精細デジタル指紋を生成することであって、各高精細デジタル指紋は、間隔の各下位間隔中のデジタルデータを特徴付ける、生成すること、および
間隔の高精細デジタル指紋のサブセットにのみ予測符号化を適用すること
を含む。
【００２０】
本発明は、デジタルデータの時間シーケンスのデジタル指紋を符号化する方法も提供し、デジタル指紋は、時間シーケンスの間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔についての複数の高精細デジタル指紋とを含み、各高精細デジタル指紋は、間隔中の各下位間隔中のデジタルデータを特徴付け、
この方法は、
間隔についての高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細指紋に予測符号化を適用することを含む。
【００２１】
本発明は、符号化デジタルコンテンツを復号化する方法も提供し、
この方法は、
デジタルデータの時間シーケンスの符号化データを受信することであって、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む、受信すること、および
予測符号化された高精細デジタル指紋を復号化すること
を含む。
【００２２】
本発明は、デジタルデータの時間シーケンスの符号化データのデータベースを検索する方法も提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含み、
この方法は、
入力された低精細デジタル指紋をデータベース内の低精細デジタル指紋と比較して、入力された低精細デジタル指紋に一致するデータベース内の低精細デジタル指紋を識別する検索プロセスと、
間隔について予測符号化された高精細デジタル指紋を復号化する復号化プロセスと
を含み、
復号化プロセスは、入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する間隔についてのみ、高精細デジタル指紋を復号化するように実行される。
【００２３】
本発明は、上述した符号化方法、復号化方法、および／または検索方法の実行が動作可能となるようにプログラマブル処理装置をプログラムするコンピュータ可読プログラミング命令を記憶する物理的に具現されるコンピュータプログラム記憶装置も提供する。
【００２４】
本発明は、上述した符号化方法、復号化方法、および／または検索方法の実行が動作可能となるようにプログラマブル処理装置をプログラムするコンピュータ可読プログラミング命令を搬送する信号も提供する。
【００２５】
本発明は、デジタルデータの時間シーケンスの符号化データを搬送する記録担体をさらに提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける１つの低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む。
【００２６】
本発明は、デジタルデータの時間シーケンスの符号化データを搬送する信号をさらに提供し、符号化データは、時間シーケンスの複数の間隔のそれぞれにつき、間隔中のデジタルデータを特徴付ける低精細デジタル指紋と、間隔の第１の下位間隔中のデジタルデータを特徴付け、予測符号化される少なくとも１つの高精細デジタル指紋と、間隔の第２の下位間隔中のデジタルデータを特徴付ける少なくとも１つの高精細デジタル指紋とを含む。
【００２７】
これより、添付図面を参照して、本発明の実施形態を例としてのみ説明する。
【図面の簡単な説明】
【００２８】
【図１】実施形態における符号装置のブロック図を示す。
【図２】実施形態におけるデジタル署名を符号化する動作のフローチャートを示す。
【図３】実施形態における復号装置のブロック図を示す。
【図４】実施形態における予測差分行列の列走査を示す。
【図５】実施形態におけるベクトル化された予測差分行列の符号方式を示す。
【図６】裾の広い分布を有するゼロランレングスへの良好な適合を提供するために、指数ゴロム符号が実施形態においてどのように使用されるかを示す。
【図７】８９×１７０三進値と８９×２７２二進値との比較を示す。
【図８】８９×１７０三進値と８９×２７２二進値との比較を示す。
【発明を実施するための形態】
【００２９】
図１は、実施形態における符号装置のブロック図を示し、図２は、マルチメディア署名を符号化するために装置により実行される処理動作を示す。
【００３０】
図３は、実施形態における復号装置のブロック図を示す。
【００３１】
図１および図３に示される装置はそれぞれ、コンピュータプログラム命令に従って処理動作を実行するようにプログラムされたプログラマブル処理装置を備える。
したがって、本発明の実施形態は、ＣＤ−ＲＯＭもしくは他の記憶装置等のコンピュータプログラム製品（図１では２８で示され、図３では１２２で示される）またはプログラマブル処理装置をプログラムするコンピュータプログラム命令を供給する信号（図１では３０で示され、図３では１２４で示される）を含む。
しかし、図１および／または図３に示される装置の構成要素が、代替として、ハードウェア構成要素であってもよいことが理解されるであろう。
【００３２】
開示される符号化方法では、マルチメディアコンテンツの時間間隔（時間セグメントまたはフラグメントとも呼ばれる）、例えば、ビデオセグメントまたはオーディオセグメントは、１つの低精細指紋および複数の高精細指紋により記述され、各高精細指紋は、前記時間間隔の下位時間間隔に対応し、通常、前記下位時間間隔は前記時間間隔よりも短い。
【００３３】
限定ではなく例として、そのようなマルチメディア指紋抽出方法が、「Ｖｉｄｅｏ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」という名称の上で参照した同時係属中の日本国特許出願第２０１０−０１４２７９号明細書に記載されており、この特許では、時間ビデオセグメント全体は、１つの低精細指紋と、時間セグメントの各フレームにつき１つずつの複数の高精細指紋とにより記述される。
【００３４】
コンテンツ署名を抽出するために、マルチメディアコンテンツを同じ長さの時間セグメントに分割し得るが、または代替として、可変長セグメントを使用してもよい。例えば、可変長は、ビデオもしくはオーディオのショット境界または顕著な変化を検出することにより決定し得る。
【００３５】
好ましい実施形態では、低精細指紋は高精細指紋から抽出される。したがって、可変長セグメントが使用される場合、すべての高精細記述子をマルチメディアコンテンツから抽出した後、時間セグメントを決定することが可能である。そのような実施形態では、高精細記述子の解析を使用して、適した時間セグメントを決定し得る。
【００３６】
ビデオ署名の場合の本発明の好ましい実施形態では、ビデオは時間セグメントに分割され、各時間セグメントの全体は、１つの低精細指紋と、時間セグメントのフレームまたはピクチャ毎に１つずつの複数の高精細指紋とにより記述される。時間セグメントの複数の高精細指紋は、ピクチャグループ(groups of pictures)（ＧＯＰs）にグループ化される。
【００３７】
本発明の好ましい実施形態では、ｔｅｍｐｏｒａｌ＿ｓｅｇｍｅｎｔ（ ）と示される時間セグメントの圧縮表現を符号化するために必要なシンタックスを表２に概説する。
【００３８】
【表２】
【００３９】
シンタックス要素の説明
・ｇｒｏｕｐ＿ｏｆ＿ｐｉｃｔｕｒｅｓ（ ）−少なくとも１つの符号化されたピクチャ指紋で構成されるピクチャグループを指定する。
・ｓｅｇｍｅｎｔ＿ｌｅｎｇｔｈ−ピクチャ数単位で時間セグメントの長さを指定する。マルチメディア署名シンタックスの上位レベル部で指定される（時間セグメントに対して定義されるか、またはコンテンツ全体で一定）。
【００４０】
キーピクチャ指紋は、時間的に隣り合うピクチャを参照せずに、非予測的に符号化されるピクチャ指紋であり、これはＫＰと記される。予測ピクチャ指紋は、時間的に隣り合うピクチャから予測的に符号化され、これはＰＰと記される。ＧＯＰは、時間的に最初のＫＰおよび次のＫＰ前のすべてのＰＰを含む、２つのＫＰ間のピクチャ指紋の集合であると定義される。したがって、ＧＯＰは、キーピクチャおよび０以上の予測ピクチャからなる。
【００４１】
本発明の好ましい実施形態では、ピクチャ指紋はＭ個の要素のベクトルであり、各要素はＮ＝３個の可能な値をとる。すなわち、要素は三進数である。単一のキーピクチャ内の情報の冗長性は非常に小さいため、これらピクチャ指紋には圧縮が適用されず、符号化は二進表現を使用して行われる。
【００４２】
本発明の好ましい実施形態では、三進数指紋の２つの異なる二進表現が考えられる。
１．連続した５つの三進数要素のそれぞれが、１バイトにパッキングされる（３5＝２４３＜２５６＝２8）。例えば、Ｍ＝３４０の場合、ピクチャ指紋全体では、８×３４０／５＝５４４ビットが必要である（６８バイト）。この方法の実施は、８ビット算術を使用して容易に行うことができる。このパッキング方法は５ｔ→８ｂと記される。別の例として、Ｍ＝３８４の場合、ピクチャ指紋全体では、８×３８０／５（５ｔ→８ｂ）＋７×４／４（４ｔ→７ｂ）＝６１５ビットが必要である（１ビットの予備を有する７６バイト）。
２．連続した１７の三進数要素のそれぞれが、２７ビットにパッキングされる（３17＝１２９１４０１６３＜１３４２１７７２８＝２27）。最後のバイト列へのパッキングは、取得した２７ビットを、特定のバイト位置で、必要なビット量だけビットシフトすることにより達成される。例えば、Ｍ＝３４０の場合、２７×３４０／１７＝５４０であるため、この方法では、ピクチャ毎に４ビットが節約され、その４ビットを追加の情報（例えば、フラグ）の送信に使用することができる。２７ビットが一変換で使用されるため、３２ビット算術ベースの実施が可能である。追加の４ビットを有することは、現在のＧＯＰ内のすべてゼロの差分ベクトルを、追加のバイトを費やさずに信号伝送することができるようなバイト位置合わせが要求される場合、有用である。このパッキング方法は１７ｔ→２７ｂと記される。別の例として、Ｍ＝３８４の場合、ピクチャ指紋全体では、２７×３７４／１７（１７ｔ→２７ｂ）＋８×１０／５（５ｔ→８ｂ）＝６１０ビットが必要である（６ビットの予備を有する７６バイト）。
【００４３】
あるいは、他の二進表現も可能であり、三進数要素の数に応じて、パッキングの効率と実施の複雑性とのトレードオフを図ることができる。例えば、Ｍ＝２９０の場合、三進数パッキング方法２９ｔ→４６ｂを使用することができ、５ｔ→８ｂパッキングと比較して、４ビットが節約される。
【００４４】
以下、ＫＰの表現に使用されるビット数は、パッキング方法に関係なく「ＫＰビット」と呼ばれる。
【００４５】
本発明の好ましい実施形態では、ｇｒｏｕｐ＿ｏｆ＿ｐｉｃｔｕｒｅｓ（ ）と記されるＧＯＰの圧縮表現を符号化するために必要なシンタックスを表３に概説する。
【００４６】
【表３】
【００４７】
シンタックス要素の説明
・ｋｅｙ＿ｐｉｃｔｕｒｅ−ＫＰビットにパッキングされたキーピクチャ。
・ＫＰ＿ＧＯＰ＿ｆｌａｇ−１に等しい場合、現在のＧＯＰは単一のキーピクチャからなる（ＧＯＰ内に予測ピクチャがない）。そうではなく、０に等しい場合、予測ピクチャが現在のＧＯＰ内に存在する。
・ｌａｓｔ＿ＧＯＰ＿ｆｌａｇ−０に等しい場合、現在のＧＯＰは時間セグメント内の最後のＧＯＰではない。１に等しい場合、現在のＧＯＰはセグメント内の最後のＧＯＰであり、その長さが導出される。
・ＧＯＰ＿ｌｅｎｇｔｈ＿ｍｉｎｕｓ２−ピクチャ数単位のＧＯＰ長から２ピクチャを差し引いたもの。例えば、１つのＫＰおよび１つのＰＰからなるＧＯＰは、０に等しいこのシンタックス要素値を有する。
・ｎｏｎｚｅｒｏ＿ＧＯＰ＿ｆｌａｇ−０に等しい場合、ＰＰが現在のＧＯＰに存在するときは、すべてのＰＰはＫＰに等しく、復号化はスキップされる（ＫＰはｐｐｌｅｎ回、繰り返される）。１に等しい場合、ＰＰは復号化される。
・ｐｒｅｄｉｃｔｅｄ＿ｐｉｃｔｕｒｅｓ（ ）−符号化されたＰＰを有するビットストリームの部分。
【００４８】
本発明の好ましい実施形態では、予測ピクチャは、現在の指紋内の要素と前の指紋内の要素とのモジュロ３差分（modulo 3 difference）を計算することにより変換される。そのように変換された予測ピクチャが予測差分行列を構成し、予測差分行列は、いわゆる「ベクトル化」ステップで走査されて、一次元ベクトルになる。
ベクトル化ステップは、予測差分行列の列を連結することにより行われる場合、１つのＧＯＰ内で、指紋の位置は他のものに比べて変化しない可能性が高いことを利用する。これにより、ゼロランがより長くなり、よりコンパクトな表現になる。
他の代替は、予測差分行列の行を連結し、ジグザグ走査または任意の他の走査パターンで走査することである。ベクトル化走査パターンの選択に応じて、エントロピー符号化方法の異なる選択を行い得る。この選択は、符号化された指紋の統計に応じて、ビデオシーケンス内で動的に行い得る。
符号化されるＧＯＰの構造（ＫＰおよび予測差分行列に変換されたＰＰで構成される）を図４に示す。図４は、予測差分行列の列走査を示すが、上述したように、他の走査方法を使用してもよい。
【００４９】
三進値は、バイトにパッキングされた二進表現を暗黙的に相関付け解除するため、予測差分の生成に使用されている。
これは、図７（８９×１７０三進値であり、白が三進数「０」を表し、グレーが三進数「１」を表し、黒が三進数「２」を表す）と、
図８（８９×２７２二進値であり、白が二進数「０」を表し、黒が二進数「１」を表す）とを比較することにより結論付けることができる。
図８では、ピクチャ内の相関が図７よりもはるかに高く、両方とも、同じＧＯＰ内の指紋要素の最初の半分を表す。
【００５０】
指紋の三進数要素間のモジュロ３差分演算はここでも、３つの三進数シンボル−「０」、「１」、および「２」になる。したがって、予測差分行列は、これら３つの三進数シンボルで構成され、これらは別様に符号化される。
・三進数「１」および「２」−それぞれ１ビットを使用して符号化され、三進数「１」には二進数「０」、三進数「２」には二進数「１」が使用される。各三進数シンボル後、ゼロランのランレングス符号語が挿入される。ゼロが続かない場合、ゼロ長の符号語が使用される。
・三進数「０」−各非ゼロ三進数シンボル後には、ゼロランが続かなければならないため、三進数シンボルは暗黙的に符号化される。
【００５１】
本発明の好ましい実施形態では、ｐｒｅｄｉｃｔｅｄ＿ｐｉｃｔｕｒｅｓ（ ）と記される、予測差分行列の圧縮表現を符号化するために必要なシンタックスを表４に概説する。
【００５２】
【表４】
【００５３】
シンタックス要素の説明
・ｚｅｒｏ＿ｒｌｅ−指数ゴロム符号化(exp-Golomb coding)を使用して符号化される三進数「０」のラン長。
・ｎｏｎ＿ｚｅｒｏ＿ｓｙｍｂｏｌ−０に等しい場合、現在のシンボルは三進数「１」である。１に等しい場合、現在のシンボルは三進数「２」である。
【００５４】
ベクトル化された予測差分行列のこの符号化方式を図５に示し、「ｖｂ」は可変ビット数(variable number of bits)を指し、「１ｂ」は１ビット長を指す。しかし、この符号化方式が唯一の符号化方式ではない。例えば、三進数シンボルを符号化する２つの代替の方法は以下のように進められる。
１．ゼロのゼロ長ランレングスは使用されず、個々の非ゼロシンボルは１ビットを使用して符号化され、追加の１ビットが、次のシンボルの種類（非ゼロまたはゼロ）を信号伝送するために使用される。
２．ゼロのゼロ長ランレングスは使用されず、非ゼロシンボルのランは、ランレングス符号化を使用して符号化される。さらに、１ビットが、次のランのシンボルを信号伝送するために使用される。
【００５５】
ゼロランレングスは、裾が広い分布（裾が広い指数分布またはべき乗分布）を有する。このため、好ましい実施形態では、パラメータｓ＝２を有する指数ゴロム符号が使用される。これは、指数ゴロム符号が、ゼロランレングスの分布に良好な適合性を提供し、複雑性の非常に低い実施に通じるためである。
これは図６に示され、図６は、経験的に取得されたゼロランレングスの確率分布を示す。本発明の代替の実施形態では、パラメータｓが適応的に選択されるとともに、その選択がその他のパラメータを使用して符号化される適応指数ゴロム方式を使用することができ、または代替として、ハフマン符号化または算術符号化のような他の何等かの適した符号化方式を使用してもよい。
【００５６】
符号器の要件は、生成されるビットストリームが前の項で概説したシンタックスに従うことである。したがって、潜在的にそれぞれが異なる圧縮性能に繋がる多くの可能な符号化方法がある。以下に、符号器の好ましい実施形態を説明する。
１．各時間セグメントのピクチャ指紋を、その他の時間セグメントから独立して符号化する。
２．セグメントの最初のピクチャ指紋をＫＰとして符号化する。
３．１ピクチャ分先に進む。現在のピクチャがセグメント内の最後のピクチャである場合、ステップ６に進む。
４．前のピクチャとの相関性について現在のピクチャをテストし、テスト結果が低相関性を示す場合、現在のピクチャ指紋をＫＰとして符号化する。
５．ステップ４において、ＫＰが挿入されなかった場合、予測差分を予測差分行列に記憶し、ステップ３に戻る。その他の場合、ステップ６に進む。予測差分は、現在のピクチャ指紋と前のピクチャ指紋との間のモジュロ３減算により取得される。
６．記憶された予測差分行列をベクトルに変換し（ベクトル化ステップ）、エントロピー符号化をそのようなベクトルに適用することにより、前のＫＰから現在のピクチャ前の最後のピクチャまでのすべての指紋を１つのＧＯＰとして符号化する。ＧＯＰの冒頭に、必要なすべてのパラメータ、例えば、ＧＯＰ長、エントロピー符号化パラメータ等を符号化する。任意的に、ベクトル化方法およびエントロピー符号化の選択が行われ、これもパラメータとして符号化される。
【００５７】
ステップ４での相関テストは、予測差分がランレングス符号器を使用して符号化され、そのようなデータのビット長がＫＰのビット長（ＫＰビット）と比較される、単純な圧縮効率性テストからなり得る。別の例は、単に差分ピクチャ内の三進数ゼロをカウントし、それを閾値と比較することによる。
【００５８】
好ましい実施形態では、フラグが使用されて、圧縮された高精細指紋の存在が示され、好ましくは、１ビットフラグが使用される。
好ましい実施形態では、単一の圧縮フラグが、複数の時間セグメントを含むマルチメディアアイテム全体の指紋に使用される。代替の実施形態では、マルチメディアアイテムの時間セグメント毎に１つずつ、高精細指紋の各セグメントの圧縮の存在を示す複数の圧縮フラグがあってもよい。圧縮フラグは、計算リソースが記憶／送信リソースよりもはるかに少ない場合に圧縮を使用しないという選択肢を許容する。
さらに、システム内で、最も頻繁にアクセスされるコンテンツを圧縮せず、他のすべてのコンテンツを圧縮することが望ましい場合がある。これにより、利用可能な計算リソース（ＣＰＵ時間、メモリサイズ、ハードディスク帯域幅等）のより最適なバランスを達成することが可能である。例えば、最後の７日間のＴＶのインデックスを圧縮しない状態で記憶し得る一方で、すべてのより古いコンテンツが圧縮された状態で記憶される。
単一のマルチメディアコンテンツの指紋のうちのいくつかを圧縮形式で記憶し、指紋のうちのいくつかを非圧縮形式で記憶することが望ましい場合もある。
【００５９】
好ましい実施形態では、圧縮フラグが「１」に設定される場合、対応する高精細記述子は圧縮される。圧縮フラグが「０」に設定される場合、圧縮は対応する高精細記述子に適用されない。
【００６０】
符号化は、抽出方法の一環をなしてもよく、または随時適用される別個の方法であってもよく、例えば、高精細指紋を抽出し、ローカルシステムに記憶し、次に、低速接続を介して送信する前に符号化される。
【００６１】
本発明の代替の実施形態では、予測符号化または任意の他の適した符号化方法を使用して、低精細記述子を圧縮することもできる。これは、全体の指紋サイズをさらに低減するが、例えば、照合用途で署名を使用する計算複雑性も増大させることになる。
【００６２】
本発明の代替の実施形態では、ＫＰはいかなるパッキングもなく記憶し得る。例えば、三進値を含むＫＰを、ピクセル毎に２ビットを使用して「行」形式で記憶し得る。これは、全体の署名サイズを少し増大させるが、高精細署名ブロックを復号化する全体の複雑性の低減にも繋がる。
【００６３】
さらに、低精細署名に加えて、高精細署名の圧縮ブロックの特徴を時間セグメントの高速照合に使用することもできる。そのような特徴としては、ＫＰ（キーピクチャ）の絶対位置および相対位置、平均および最大等のゼロランの統計等が挙げられる。
【００６４】
検索速度は、多くのマルチメディア指紋用途で非常に重要である。この理由により、圧縮方式が効率的であることが非常に重要である。本明細書において概説した圧縮方式は、低複雑性という目標を達成する。
【特許請求の範囲】
【請求項１】
デジタルデータの時間シーケンスを符号化するように動作可能なデジタルコンテンツ符号器であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成するように動作可能な低精細デジタル指紋生成器と、
前記間隔について複数の高精細デジタル指紋を生成するように動作可能な高精細デジタル指紋生成器であって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付ける、高精細デジタル指紋生成器と、
前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋が圧縮符号化されるように、可逆圧縮符号化を前記間隔についての前記高精細デジタル指紋に選択的に適用するように動作可能であると共に、圧縮符号化されない少なくとも１つの高精細デジタル指紋に非圧縮符号化を適用するように動作可能な符号器と
を備える、デジタルコンテンツ符号器。
【請求項２】
デジタルデータの時間シーケンスを符号化するように動作可能なデジタルコンテンツ符号器であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成するように動作可能な低精細デジタル指紋生成器と、
前記間隔について複数の高精細デジタル指紋を生成するように動作可能な高精細デジタル指紋生成器であって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付ける、高精細デジタル指紋生成器と、
前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋に予測符号化を適用するように動作可能な予測符号器と
を備える、デジタルコンテンツ符号器。
【請求項３】
前記間隔の前記高精細デジタル指紋の少なくとも１つの他の高精細デジタル指紋に非予測符号化を適用するように動作可能な非予測符号器をさらに備える、請求項２に記載のデジタルコンテンツ符号器。
【請求項４】
前記高精細デジタル指紋生成器は、三進値のベクトルとして前記高精細デジタル指紋のそれぞれを生成するように動作可能であり、
前記非予測符号器は、前記高精細デジタル指紋の三進値の前記ベクトルの二進表現を生成することにより、前記非予測符号化を高精細デジタル指紋に適用するように動作可能である、請求項３に記載のデジタルコンテンツ符号器。
【請求項５】
前記デジタルコンテンツ符号器は、ピクチャの時間シーケンスを符号化するように動作可能であり、
前記デジタルコンテンツ符号器は、前記シーケンス内のピクチャをキーピクチャとして指定するように動作可能なキーピクチャ指定部をさらに備え、
前記予測符号器は、前記予測符号化を非キーピクチャの前記高精細デジタル指紋に適用するように動作可能である、請求項２から請求項４までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項６】
前記低精細指紋生成器は、前記間隔についての前記複数の高精細指紋から、前記間隔についての前記１つの低精細指紋を生成するように動作可能である、請求項２から請求項５までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項７】
前記デジタルコンテンツ符号器は、低精細デジタル指紋および高精細デジタル指紋を生成し、異なる長さの間隔の符号化を実行するように動作可能である、請求項２から請求項６までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項８】
前記高精細デジタル指紋に応じて、前記間隔のそれぞれの長さを計算するように動作可能な間隔長計算器をさらに備える、請求項７に記載のデジタルコンテンツ符号器。
【請求項９】
前記高精細デジタル指紋生成器は、三進値のベクトルとして前記高精細デジタル指紋のそれぞれを生成するように動作可能であり、
前記予測符号器は、
前記高精細デジタル指紋と異なる高精細デジタル指紋との差分を、それらのモジュロ３差分を計算して、予測差分行列を生成することにより計算し、
前記予測差分行列を走査して、三進値のベクトルとして一次元ベクトルを形成し、
三進値「１」および「２」が、１ビットを使用して符号化され、三進値「０」がゼロランを使用して暗黙的に符号化されるように、前記一次元ベクトルの符号化を実行する
ことにより、予測符号化を高精細デジタル指紋に適用するように動作可能であり、
前記予測符号器は、
前記予測差分行列の複数の異なる種類の走査を実行して、前記一次元ベクトルを形成し、
前記一次元ベクトルの複数の異なる種類の符号化を実行し、
前記複数の異なる種類の走査から、前記デジタルデータの時間シーケンス内の高精細デジタル指紋を符号化するものを選択し、
前記選択された走査の種類に応じて、前記複数の異なる種類の走査から、前記一次元ベクトルを符号化するものを選択する
ように動作可能である、請求項２から請求項８までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項１０】
符号化デジタルコンテンツを復号化するように動作可能な復号器であって、
デジタルデータの時間シーケンスの符号化データを受信するように動作可能な受信器であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋、及び前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋を含み、前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋が、予測符号化される、受信器と、
前記予測符号化された高精細デジタル指紋を復号化するように動作可能な予測復号器と
を備える、復号器。
【請求項１１】
前記受信器は、符号化データを受信するように動作可能であり、各間隔の少なくとも１つの高精細デジタル指紋は非予測的に符号化され、
前記復号器は、前記非予測的に符号化された高精細デジタル指紋を復号化するように動作可能である非予測復号器をさらに備える、請求項１０に記載の復号器。
【請求項１２】
前記受信器は符号化データを受信するように動作可能であり、前記非予測的に符号化された高精細デジタル指紋は三進値の二進表現を含み、
前記非予測復号器は、前記二進表現を復号化して、前記三進値を生成するように動作可能である、請求項１１に記載の復号器。
【請求項１３】
前記復号器は、異なる長さの間隔の符号化データを受信して復号化するように動作可能である、請求項１０から請求項１２までのいずれか１項に記載の復号器。
【請求項１４】
前記予測復号器は、
前記受信した予測符号化データを復号化して、一次元ベクトルを生成し、
前記一次元ベクトルからの値を予測差分行列内に配置し、
前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築する
ことにより、予測符号化された高精細デジタル指紋のそれぞれを復号化するように動作可能である、請求項１０から請求項１３までのいずれか１項に記載の復号器。
【請求項１５】
前記予測符号器は、モジュロ３加算を実行することにより、前記予測差分行列を前に復号化された高精細デジタル指紋と結合するように動作可能である、請求項１４に記載の復号器。
【請求項１６】
デジタルデータの時間シーケンスの符号化データのデータベースを検索するように動作可能な検索装置であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔内の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを備え、前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は予測符号化され、各間隔の前記符号化データは、非予測的に符号化されるとともに、三進値の二進表現を含む少なくとも１つの高精細デジタル指紋を含み、
前記検索装置は、
入力された低精細デジタル指紋と前記データベース内の前記低精細デジタル指紋とを比較して、前記入力された低精細デジタル指紋に一致する前記データベース内の低精細デジタル指紋を識別するように動作可能な指紋照合器と、
復号器と
を備え、
前記復号器は、
−前記予測符号化された高精細デジタル指紋を復号化するように動作可能な予測復号器と、
−前記二進表現を復号化して、前記三進値を生成することにより、前記非予測的に符号化された高精細デジタル指紋を復号化するように動作可能な非予測復号器と
を備え、
前記復号器は、前記入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する前記間隔の前記高精細デジタル指紋のみを復号化するように構成され、
前記予測復号器は、
前記受信した予測符号化データを復号化して、一次元ベクトルを生成し、
前記一次元ベクトルからの値を予測差分行列内に配置し、
モジュロ３加算を実行することにより、前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築する
ことにより、予測符号化された高精細デジタル指紋のそれぞれを復号化するように動作可能である、検索装置。
【請求項１７】
デジタルデータの時間シーケンスを符号化する方法であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成すること、
前記間隔について複数の高精細デジタル指紋を生成することであって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付けること、
前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋が圧縮符号化されるように、可逆圧縮符号化を前記間隔についての前記高精細デジタル指紋に選択的に適用すること、および
少なくとも１つの高精細デジタル指紋に非圧縮符号化を適用すること
を含む、方法。
【請求項１８】
デジタルデータの時間シーケンスを符号化する方法であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成すること、
前記間隔について複数の高精細デジタル指紋を生成することであって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付けること、および
前記間隔についての前記高精細デジタル指紋の少なくとも１つであるが、すべてではない高精細デジタル指紋を予測符号化すること
を含む、方法。
【請求項１９】
前記間隔の前記高精細デジタル指紋のうちの少なくとも１つの他の高精細デジタル指紋を非予測的に符号化することをさらに含む、請求項１８に記載の方法。
【請求項２０】
前記高精細デジタル指紋のそれぞれは、三進値のベクトルとして生成され、
前記高精細デジタル指紋を非予測的に符号化することは、前記高精細デジタル指紋の三進値のベクトルの二進表現を生成することを含む、請求項１９に記載の方法。
【請求項２１】
前記時間シーケンスは、ピクチャの時間シーケンスを含み、
前記方法は、前記シーケンス内のピクチャをキーピクチャとして指定することをさらに含み、
前記非キーピクチャの前記高精細デジタル指紋は、予測符号化される、請求項１８から請求項２０までのいずれか１項に記載の方法。
【請求項２２】
前記間隔の前記１つの低精細指紋は、前記間隔の前記複数の高精細指紋から生成される、請求項１８から請求項２１までのいずれか１項に記載の方法。
【請求項２３】
前記処理が繰り返されて、異なる長さの間隔の低精細デジタル指紋および高精細デジタル指紋を生成し符号化する、請求項１８から請求項２２までのいずれか１項に記載の方法。
【請求項２４】
前記高精細デジタル指紋に応じて、前記間隔のそれぞれの長さを計算することをさらに含む、請求項２３に記載の方法。
【請求項２５】
前記高精細デジタル指紋のそれぞれは、三進値のベクトルとして生成され、
前記高精細デジタル指紋の予測符号化は、
前記高精細デジタル指紋と異なる高精細デジタル指紋との差分を、それらのモジュロ３差分を計算することにより計算して、予測差分行列を生成すること、
複数の異なる種類の走査から、前記予測差分行列を走査するものを選択し、
前記予測差分行列を前記選択された種類の走査で走査して、三進値のベクトルとして一次元ベクトルを形成すること、
前記選択された走査の種類に応じて、複数の異なる種類の符号化から、前記高精細デジタル指紋の前記一次元ベクトルを符号化するものを選択すること、および
三進値「１」および「２」が１ビットを使用して符号化され、三進値「０」がゼロランを使用して暗黙的に符号化されるように、前記選択された種類の符号化を使用して前記一次元ベクトルの符号化を実行すること
を含む、請求項１８から請求項２４までのいずれか１項に記載の方法。
【請求項２６】
符号化デジタルコンテンツを復号化する方法であって、
デジタルデータの時間シーケンスの符号化データを受信することであって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は予測符号化される、受信すること、および
前記予測符号化された高精細デジタル指紋を復号化すること
を含む、方法。
【請求項２７】
符号化データが受信され、前記符号化データ内では、各間隔の少なくとも１つの高精細デジタル指紋が非予測的に符号化され、
前記方法は、前記非予測的に符号化された高精細デジタル指紋を復号化することをさらに含む、請求項２６に記載の方法。
【請求項２８】
受信した前記符号化データ内で、前記非予測的に符号化された高精細デジタル指紋は、三進値の二進表現を含み、
前記非予測的に復号化することは、前記二進表現を復号化して、前記三進値を生成することを含む、請求項２７に記載の方法。
【請求項２９】
異なる長さの間隔の符号化データが受信され復号化される、請求項２６から請求項２８までのいずれか１項に記載の方法。
【請求項３０】
予測符号化された高精細デジタル指紋のそれぞれを予測復号化することは、
前記受信した予測符号化データを復号化して、一次元ベクトルを生成すること、
前記一次元ベクトルからの値を予測差分行列内に配置すること、および
前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築すること
を含む、請求項２６から請求項２９までのいずれか１項に記載の方法。
【請求項３１】
前記予測差分行列は、モジュロ３加算を実行することにより、前に復号化された高精細デジタル指紋と結合される、請求項３０に記載の方法。
【請求項３２】
デジタルデータの時間シーケンスの符号化データのデータベースを検索する方法であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は、予測符号化され、各間隔の前記符号化データは、非予測的に符号化されるとともに、三進値の二進表現を含む少なくとも１つの高精細デジタル指紋を含み、前記方法は、
入力された低精細デジタル指紋を前記データベース内の前記低精細デジタル指紋と比較して、前記入力された低精細デジタル指紋に一致する前記データベース内の低精細デジタル指紋を識別する照合プロセスと、
復号化プロセスであって、
−前記予測符号化された高精細デジタル指紋を予測復号化すること、および
−前記二進表現を復号化することにより、前記非予測的に符号化された高精細デジタル指紋を復号化して、前記三進値を生成すること
を含む、復号化プロセスと
を含み、
前記復号化プロセスは、前記入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する間隔についての前記高精細デジタル指紋のみを復号化し、
予測符号化された高精細デジタル指紋のそれぞれは、
前記受信された予測符号化データを復号化して、一次元ベクトルを生成し、
前記一次元ベクトルからの値を予測差分行列内に配置し、
モジュロ３加算を実行することにより、前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築すること
により復号化される、方法。
【請求項３３】
デジタルデータの時間シーケンスの符号化データを搬送する記録担体であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は、予測符号化される、記録担体。
【請求項３４】
各間隔の少なくとも１つの高精細デジタル指紋は非予測的に符号化される、請求項３３に記載の記録担体。
【請求項３５】
デジタルデータの時間シーケンスの符号化データを搬送する信号であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は、予測符号化される、信号。
【請求項３６】
各間隔の少なくとも１つの高精細デジタル指紋は非予測的に符号化される、請求項３５に記載の信号。
【請求項３７】
請求項１７から請求項３２までの少なくとも一項に記載の方法の実行を動作可能にするように、プログラマブル処理装置をプログラムするコンピュータプログラム命令を記憶する記憶装置。
【請求項３８】
請求項１７から請求項３２までの少なくとも一項に記載の方法の実行を動作可能にするように、プログラマブル処理装置をプログラムするコンピュータプログラム命令を搬送する信号。
【請求項１】
デジタルデータの時間シーケンスを符号化するように動作可能なデジタルコンテンツ符号器であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成するように動作可能な低精細デジタル指紋生成器と、
前記間隔について複数の高精細デジタル指紋を生成するように動作可能な高精細デジタル指紋生成器であって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付ける、高精細デジタル指紋生成器と、
前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋が圧縮符号化されるように、可逆圧縮符号化を前記間隔についての前記高精細デジタル指紋に選択的に適用するように動作可能であると共に、圧縮符号化されない少なくとも１つの高精細デジタル指紋に非圧縮符号化を適用するように動作可能な符号器と
を備える、デジタルコンテンツ符号器。
【請求項２】
デジタルデータの時間シーケンスを符号化するように動作可能なデジタルコンテンツ符号器であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成するように動作可能な低精細デジタル指紋生成器と、
前記間隔について複数の高精細デジタル指紋を生成するように動作可能な高精細デジタル指紋生成器であって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付ける、高精細デジタル指紋生成器と、
前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋に予測符号化を適用するように動作可能な予測符号器と
を備える、デジタルコンテンツ符号器。
【請求項３】
前記間隔の前記高精細デジタル指紋の少なくとも１つの他の高精細デジタル指紋に非予測符号化を適用するように動作可能な非予測符号器をさらに備える、請求項２に記載のデジタルコンテンツ符号器。
【請求項４】
前記高精細デジタル指紋生成器は、三進値のベクトルとして前記高精細デジタル指紋のそれぞれを生成するように動作可能であり、
前記非予測符号器は、前記高精細デジタル指紋の三進値の前記ベクトルの二進表現を生成することにより、前記非予測符号化を高精細デジタル指紋に適用するように動作可能である、請求項３に記載のデジタルコンテンツ符号器。
【請求項５】
前記デジタルコンテンツ符号器は、ピクチャの時間シーケンスを符号化するように動作可能であり、
前記デジタルコンテンツ符号器は、前記シーケンス内のピクチャをキーピクチャとして指定するように動作可能なキーピクチャ指定部をさらに備え、
前記予測符号器は、前記予測符号化を非キーピクチャの前記高精細デジタル指紋に適用するように動作可能である、請求項２から請求項４までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項６】
前記低精細指紋生成器は、前記間隔についての前記複数の高精細指紋から、前記間隔についての前記１つの低精細指紋を生成するように動作可能である、請求項２から請求項５までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項７】
前記デジタルコンテンツ符号器は、低精細デジタル指紋および高精細デジタル指紋を生成し、異なる長さの間隔の符号化を実行するように動作可能である、請求項２から請求項６までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項８】
前記高精細デジタル指紋に応じて、前記間隔のそれぞれの長さを計算するように動作可能な間隔長計算器をさらに備える、請求項７に記載のデジタルコンテンツ符号器。
【請求項９】
前記高精細デジタル指紋生成器は、三進値のベクトルとして前記高精細デジタル指紋のそれぞれを生成するように動作可能であり、
前記予測符号器は、
前記高精細デジタル指紋と異なる高精細デジタル指紋との差分を、それらのモジュロ３差分を計算して、予測差分行列を生成することにより計算し、
前記予測差分行列を走査して、三進値のベクトルとして一次元ベクトルを形成し、
三進値「１」および「２」が、１ビットを使用して符号化され、三進値「０」がゼロランを使用して暗黙的に符号化されるように、前記一次元ベクトルの符号化を実行する
ことにより、予測符号化を高精細デジタル指紋に適用するように動作可能であり、
前記予測符号器は、
前記予測差分行列の複数の異なる種類の走査を実行して、前記一次元ベクトルを形成し、
前記一次元ベクトルの複数の異なる種類の符号化を実行し、
前記複数の異なる種類の走査から、前記デジタルデータの時間シーケンス内の高精細デジタル指紋を符号化するものを選択し、
前記選択された走査の種類に応じて、前記複数の異なる種類の走査から、前記一次元ベクトルを符号化するものを選択する
ように動作可能である、請求項２から請求項８までのいずれか１項に記載のデジタルコンテンツ符号器。
【請求項１０】
符号化デジタルコンテンツを復号化するように動作可能な復号器であって、
デジタルデータの時間シーケンスの符号化データを受信するように動作可能な受信器であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋、及び前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋を含み、前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋が、予測符号化される、受信器と、
前記予測符号化された高精細デジタル指紋を復号化するように動作可能な予測復号器と
を備える、復号器。
【請求項１１】
前記受信器は、符号化データを受信するように動作可能であり、各間隔の少なくとも１つの高精細デジタル指紋は非予測的に符号化され、
前記復号器は、前記非予測的に符号化された高精細デジタル指紋を復号化するように動作可能である非予測復号器をさらに備える、請求項１０に記載の復号器。
【請求項１２】
前記受信器は符号化データを受信するように動作可能であり、前記非予測的に符号化された高精細デジタル指紋は三進値の二進表現を含み、
前記非予測復号器は、前記二進表現を復号化して、前記三進値を生成するように動作可能である、請求項１１に記載の復号器。
【請求項１３】
前記復号器は、異なる長さの間隔の符号化データを受信して復号化するように動作可能である、請求項１０から請求項１２までのいずれか１項に記載の復号器。
【請求項１４】
前記予測復号器は、
前記受信した予測符号化データを復号化して、一次元ベクトルを生成し、
前記一次元ベクトルからの値を予測差分行列内に配置し、
前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築する
ことにより、予測符号化された高精細デジタル指紋のそれぞれを復号化するように動作可能である、請求項１０から請求項１３までのいずれか１項に記載の復号器。
【請求項１５】
前記予測符号器は、モジュロ３加算を実行することにより、前記予測差分行列を前に復号化された高精細デジタル指紋と結合するように動作可能である、請求項１４に記載の復号器。
【請求項１６】
デジタルデータの時間シーケンスの符号化データのデータベースを検索するように動作可能な検索装置であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔内の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを備え、前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は予測符号化され、各間隔の前記符号化データは、非予測的に符号化されるとともに、三進値の二進表現を含む少なくとも１つの高精細デジタル指紋を含み、
前記検索装置は、
入力された低精細デジタル指紋と前記データベース内の前記低精細デジタル指紋とを比較して、前記入力された低精細デジタル指紋に一致する前記データベース内の低精細デジタル指紋を識別するように動作可能な指紋照合器と、
復号器と
を備え、
前記復号器は、
−前記予測符号化された高精細デジタル指紋を復号化するように動作可能な予測復号器と、
−前記二進表現を復号化して、前記三進値を生成することにより、前記非予測的に符号化された高精細デジタル指紋を復号化するように動作可能な非予測復号器と
を備え、
前記復号器は、前記入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する前記間隔の前記高精細デジタル指紋のみを復号化するように構成され、
前記予測復号器は、
前記受信した予測符号化データを復号化して、一次元ベクトルを生成し、
前記一次元ベクトルからの値を予測差分行列内に配置し、
モジュロ３加算を実行することにより、前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築する
ことにより、予測符号化された高精細デジタル指紋のそれぞれを復号化するように動作可能である、検索装置。
【請求項１７】
デジタルデータの時間シーケンスを符号化する方法であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成すること、
前記間隔について複数の高精細デジタル指紋を生成することであって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付けること、
前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋が圧縮符号化されるように、可逆圧縮符号化を前記間隔についての前記高精細デジタル指紋に選択的に適用すること、および
少なくとも１つの高精細デジタル指紋に非圧縮符号化を適用すること
を含む、方法。
【請求項１８】
デジタルデータの時間シーケンスを符号化する方法であって、
前記時間シーケンスの間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋を生成すること、
前記間隔について複数の高精細デジタル指紋を生成することであって、前記高精細デジタル指紋のそれぞれは、前記間隔の各下位間隔中の前記デジタルデータを特徴付けること、および
前記間隔についての前記高精細デジタル指紋の少なくとも１つであるが、すべてではない高精細デジタル指紋を予測符号化すること
を含む、方法。
【請求項１９】
前記間隔の前記高精細デジタル指紋のうちの少なくとも１つの他の高精細デジタル指紋を非予測的に符号化することをさらに含む、請求項１８に記載の方法。
【請求項２０】
前記高精細デジタル指紋のそれぞれは、三進値のベクトルとして生成され、
前記高精細デジタル指紋を非予測的に符号化することは、前記高精細デジタル指紋の三進値のベクトルの二進表現を生成することを含む、請求項１９に記載の方法。
【請求項２１】
前記時間シーケンスは、ピクチャの時間シーケンスを含み、
前記方法は、前記シーケンス内のピクチャをキーピクチャとして指定することをさらに含み、
前記非キーピクチャの前記高精細デジタル指紋は、予測符号化される、請求項１８から請求項２０までのいずれか１項に記載の方法。
【請求項２２】
前記間隔の前記１つの低精細指紋は、前記間隔の前記複数の高精細指紋から生成される、請求項１８から請求項２１までのいずれか１項に記載の方法。
【請求項２３】
前記処理が繰り返されて、異なる長さの間隔の低精細デジタル指紋および高精細デジタル指紋を生成し符号化する、請求項１８から請求項２２までのいずれか１項に記載の方法。
【請求項２４】
前記高精細デジタル指紋に応じて、前記間隔のそれぞれの長さを計算することをさらに含む、請求項２３に記載の方法。
【請求項２５】
前記高精細デジタル指紋のそれぞれは、三進値のベクトルとして生成され、
前記高精細デジタル指紋の予測符号化は、
前記高精細デジタル指紋と異なる高精細デジタル指紋との差分を、それらのモジュロ３差分を計算することにより計算して、予測差分行列を生成すること、
複数の異なる種類の走査から、前記予測差分行列を走査するものを選択し、
前記予測差分行列を前記選択された種類の走査で走査して、三進値のベクトルとして一次元ベクトルを形成すること、
前記選択された走査の種類に応じて、複数の異なる種類の符号化から、前記高精細デジタル指紋の前記一次元ベクトルを符号化するものを選択すること、および
三進値「１」および「２」が１ビットを使用して符号化され、三進値「０」がゼロランを使用して暗黙的に符号化されるように、前記選択された種類の符号化を使用して前記一次元ベクトルの符号化を実行すること
を含む、請求項１８から請求項２４までのいずれか１項に記載の方法。
【請求項２６】
符号化デジタルコンテンツを復号化する方法であって、
デジタルデータの時間シーケンスの符号化データを受信することであって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は予測符号化される、受信すること、および
前記予測符号化された高精細デジタル指紋を復号化すること
を含む、方法。
【請求項２７】
符号化データが受信され、前記符号化データ内では、各間隔の少なくとも１つの高精細デジタル指紋が非予測的に符号化され、
前記方法は、前記非予測的に符号化された高精細デジタル指紋を復号化することをさらに含む、請求項２６に記載の方法。
【請求項２８】
受信した前記符号化データ内で、前記非予測的に符号化された高精細デジタル指紋は、三進値の二進表現を含み、
前記非予測的に復号化することは、前記二進表現を復号化して、前記三進値を生成することを含む、請求項２７に記載の方法。
【請求項２９】
異なる長さの間隔の符号化データが受信され復号化される、請求項２６から請求項２８までのいずれか１項に記載の方法。
【請求項３０】
予測符号化された高精細デジタル指紋のそれぞれを予測復号化することは、
前記受信した予測符号化データを復号化して、一次元ベクトルを生成すること、
前記一次元ベクトルからの値を予測差分行列内に配置すること、および
前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築すること
を含む、請求項２６から請求項２９までのいずれか１項に記載の方法。
【請求項３１】
前記予測差分行列は、モジュロ３加算を実行することにより、前に復号化された高精細デジタル指紋と結合される、請求項３０に記載の方法。
【請求項３２】
デジタルデータの時間シーケンスの符号化データのデータベースを検索する方法であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細デジタル指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は、予測符号化され、各間隔の前記符号化データは、非予測的に符号化されるとともに、三進値の二進表現を含む少なくとも１つの高精細デジタル指紋を含み、前記方法は、
入力された低精細デジタル指紋を前記データベース内の前記低精細デジタル指紋と比較して、前記入力された低精細デジタル指紋に一致する前記データベース内の低精細デジタル指紋を識別する照合プロセスと、
復号化プロセスであって、
−前記予測符号化された高精細デジタル指紋を予測復号化すること、および
−前記二進表現を復号化することにより、前記非予測的に符号化された高精細デジタル指紋を復号化して、前記三進値を生成すること
を含む、復号化プロセスと
を含み、
前記復号化プロセスは、前記入力された低精細デジタル指紋に一致する低精細デジタル指紋を有する間隔についての前記高精細デジタル指紋のみを復号化し、
予測符号化された高精細デジタル指紋のそれぞれは、
前記受信された予測符号化データを復号化して、一次元ベクトルを生成し、
前記一次元ベクトルからの値を予測差分行列内に配置し、
モジュロ３加算を実行することにより、前記予測差分行列を前に復号化された高精細デジタル指紋と結合して、復号化中の前記高精細デジタル指紋を再構築すること
により復号化される、方法。
【請求項３３】
デジタルデータの時間シーケンスの符号化データを搬送する記録担体であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は、予測符号化される、記録担体。
【請求項３４】
各間隔の少なくとも１つの高精細デジタル指紋は非予測的に符号化される、請求項３３に記載の記録担体。
【請求項３５】
デジタルデータの時間シーケンスの符号化データを搬送する信号であって、前記符号化データは、前記時間シーケンスの複数の間隔のそれぞれにつき、前記間隔中の前記デジタルデータを特徴付ける１つの低精細デジタル指紋と、前記間隔の各下位間隔中の前記デジタルデータをそれぞれ特徴付ける複数の高精細デジタル指紋とを含み、前記高精細指紋のうちの少なくとも１つであるが、すべてではない高精細デジタル指紋は、予測符号化される、信号。
【請求項３６】
各間隔の少なくとも１つの高精細デジタル指紋は非予測的に符号化される、請求項３５に記載の信号。
【請求項３７】
請求項１７から請求項３２までの少なくとも一項に記載の方法の実行を動作可能にするように、プログラマブル処理装置をプログラムするコンピュータプログラム命令を記憶する記憶装置。
【請求項３８】
請求項１７から請求項３２までの少なくとも一項に記載の方法の実行を動作可能にするように、プログラマブル処理装置をプログラムするコンピュータプログラム命令を搬送する信号。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−１３０４１３（Ｐ２０１１−１３０４１３Ａ）
【公開日】平成２３年６月３０日（２０１１．６．３０）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−２２１６２５（Ｐ２０１０−２２１６２５）
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公開日】平成２３年６月３０日（２０１１．６．３０）
【国際特許分類】
【出願番号】特願２０１０−２２１６２５（Ｐ２０１０−２２１６２５）
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]