(57)【要約】強健な指紋システムを開示する。そのようなシステムは未知のマルチメディア・コンテンツ(U(t))を、該コンテンツから指紋（ハッシュ・ワードの列）を抽出し、複数の既知のコンテンツ(K(t))の指紋が格納されるデータベースにおいて類似した指紋をサーチすることによって、認識することが可能である。データベースにおいて指紋を効率的に格納し、該サーチを迅速化するために、既知の信号(K(t))のハッシュ・ワード（H(n)）が係数Mによってデータベース(14)における格納の前に副次標本化される(13)。未知の信号(U(t))のハッシュ・ワード（H(n)）はMのインタリーブされたサブ列（H0(n),  H1(n),  …HM-1(n)）に分割される(16)。該インタリーブされたサブ列は選択的に(17)コンピュータ（１５）のもとでデータベース（１４）に入力される。サブ列の１つのみが十分に格納された指紋に整合する場合、該信号が識別される。
2005517211.tif 000002
【特許請求の範囲】
【請求項１】
オーディオ映像メディア信号を識別する指紋をデータベースに格納する方法であって、オーディオ映像メディア信号毎に：
該オーディオ映像メディア信号をフレーム列に分割する工程；
該フレーム列を係数Mによって、副次標本化フレーム列を得るよう、副次標本化する工程；
該副次標本化フレーム列のフレーム毎に、該フレーム内の該信号の知覚的に本質的な特性を表すハッシュ・ワードを、対象副次標本化ハッシュ・ワード列を得るよう、抽出する工程；及び
該副次標本化ハッシュ・ワード列を指紋として該データベースに格納する工程；
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、該フレーム列が一部重なり合うことを特徴とする方法。
【請求項３】
オーディオ映像メディア信号を識別する指紋をデータベースに格納する装置であって：
該オーディオ映像メディア信号をフレーム列に分割するフレーミング手段；
該フレーム列を係数Mによって、副次標本化フレーム列を得るよう、副次標本化する副次標本化手段；
該副次標本化フレーム列のフレーム毎に、該フレーム内の該信号の知覚的に本質的な特性を表すハッシュ・ワードを、対象副次標本化ハッシュ・ワード列を得るよう、抽出する手段；及び
該副次標本化ハッシュ・ワード列を指紋として該データベースに格納するデータベース；
を有することを特徴とする装置。
【請求項４】
未知のオーディオ映像メディア信号を識別する方法であって：
該未知のオーディオ映像メディア信号の少なくとも一部分をフレーム列に分割する工程；
フレーム毎に、該フレーム内の該信号の知覚的に本質的な特性を表すハッシュ・ワードを、対象ハッシュ・ワード列を得るよう、抽出する工程；
該ハッシュ・ワード列をMのインタリーブされたハッシュ・ワードのサブ列に分割する工程；
連続して該Mのサブ列をデータベースに入力する、該データベースにおいて、複数のマルチメディア信号について、副次標本化ハッシュ・ワード列が格納された、工程；及び
該未知の信号を該マルチメディア信号として識別し、該マルチメディア信号のうち、該格納された副次標本化ハッシュ・ワード列の少なくとも一部分がかなり、該Mの入力ハッシュ・ワードのサブ列の少なくとも１つに整合する、工程；
を有することを特徴とする方法。
【請求項５】
請求項４記載の方法であって、該フレーム列が一部重なり合うことを特徴とする方法。
【請求項６】
未知のオーディオ映像メディア信号を識別する装置であって：
該未知のオーディオ映像メディア信号の少なくとも一部分をフレーム列に分割するフレーミング手段；
フレーム毎に、該フレーム内の該信号の知覚的に本質的な特性を表すハッシュ・ワードを、対象ハッシュ・ワード列を得るよう、抽出する手段；
該ハッシュ・ワード列をMのインタリーブされたハッシュ・ワードのサブ列に分割するインタリーブ手段；
連続して該Mのサブ列をデータベースに入力する、該データベースにおいて、複数のマルチメディア信号について、副次標本化ハッシュ・ワード列が格納された、選定手段；及び
該未知の信号を該マルチメディア信号として識別し、該マルチメディア信号のうち、該格納された副次標本化ハッシュ・ワード列の少なくとも一部分がかなり、該Mの入力ハッシュ・ワードのサブ列の少なくとも１つに整合する、コンピュータ手段；
を有することを特徴とする装置。
【請求項７】
未知のオーディオ映像メディア信号を識別する方法であって：
遠隔局から、該未知のオーディオ映像メディア信号の少なくとも一部分をフレーム列に分割することによって生成されたハッシュ・ワード列を受信し、フレーム毎に、該フレーム内の該信号の知覚的に本質的な特性を表すハッシュ・ワードを抽出する工程；
該ハッシュ・ワード列をMのインタリーブされたハッシュ・ワードのサブ列に分割する工程；
連続して該Mのサブ列をデータベースに入力する、該データベースにおいて、複数のマルチメディア信号について、副次標本化ハッシュ・ワード列が格納された、工程；及び
該未知の信号を該マルチメディア信号として識別し、該信号のうち、該格納された副次標本化ハッシュ・ワード列の少なくとも一部分がかなり、該Mの入力ハッシュ・ワードのサブ列の少なくとも１つに整合する、工程；
を有することを特徴とする方法。
【請求項８】
請求項７記載の方法であって、該フレーム列が一部重なり合うことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーディオ映像メディア信号を識別する指紋をデータベースに格納する方法及び装置に関する。本発明は更に、未知のオーディオ映像メディア信号を識別する方法及び装置に関する。
【背景技術】
【０００２】
（文献においてシグネチャ又はハッシュとも呼ばれる）指紋は情報信号をディジタル的に要約したものである。暗号法において、ハッシュは長い間、大容量ファイルの正確な受信を検証するのに用いられてきた。近年、ハッシングの考え方がマルチメディアのコンテンツを識別するのに取り入れられている。オーディオ又は映像のクリップのような未知のコンテンツは該クリップから抽出された指紋とデータベースに格納された指紋群とを比較することによって認識される。大変脆弱である（大容量ファイルにおいて単一ビットを反転させることによって完全に異なったハッシュを結果として生じる）暗号法のハッシュに対して、オーディオ映像コンテンツから抽出された指紋は強健でなければならない。該指紋は大いに、圧縮又は復元、A/D又はD/A変換のような処理に対して不変でなければならない。
【０００３】
従来技術の指紋システムを開示したものがある（非特許文献１参照。）。該文献に記載されているように、該指紋はコンテンツの知覚的に本質的な特性、すなわち、可聴周波数スペクトル帯域におけるエネルギの分布、から導出される。映像信号については、ビデオ画像における輝度レベルの分布が強健な指紋の根拠を構成するものとして提案されている。
【０００４】
指紋は信号を（ことによると重なり合う）フレーム列に分割し、各フレーム中の該信号の知覚的に本質的な特性を表すハッシュ・ワードを、当該ハッシュ・ワード列を得るよう、抽出することによって生成される。未知のクリップを識別するよう、データベースは当該ハッシュ・ワード列を受信し、格納された最も類似したハッシュ・ワード列をサーチする。類似性は該データベースにおける該列のハッシュ・ワード列と整合するビット数を判定することによって測定される。BER（ビット誤り率、非整合ビットの割合）が特定の閾値を下回る場合、該クリップは該データベースにおける最も類似したハッシュ・ワード列のもととなる歌又は映画として識別される。
【非特許文献１】Haitsma  et  al.:Robust  Hashing  for  Content  Identification,  Content-Based  Multimedia  Indexing  (CBMI)  conference,  Brescia  (Italy),  2001
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来技術の指紋法の問題はデータベースのサイズにある。該文献においては、オーディオ信号は31/32のオーバラップのある、０．４秒のフレームに分割される。これによって新しいフレームは１１．６(=0.4/32)ｍｓ毎にもたらされる。フレーム毎に、32ビットのハッシュ・ワードが抽出される。したがって、5分の歌は約１００ｋバイト、すなわち、５（分）ｘ６０（秒）ｘ４（バイト/ハッシュ・ワード）/0.0116(秒/ハッシュ・ワード)、を要する。言うまでもなく、データベースは歌の大きなリパートリを認識することを可能にするよう大容量を有していなければならない。同様な考慮点が映像指紋システムにもあてはまる。
【課題を解決するための手段】
【０００６】
本発明の目的は指紋をデータベースに格納する、上記の課題を軽減する方法及びシステムを備えることにある。本発明の目的は更に、未知のオーディオ映像信号をそのようなデータベースにおいて識別する方法及びシステムを備えることにある。
【０００７】
この目的のために、本発明は本特許請求の範囲に規定されたようなデータベースにおいて指紋を格納する方法を備えるものである。該方法は従来技術とは、ハッシュ・ワードの副次標本列（すなわち、M毎に１つのハッシュ・ワード）がデータベースに格納されるという点で異なる。本明細書及び特許請求の範囲の原文における「sequence」の語はフルレングスの信号（歌又は映画）を表すのに用いられる。記憶容量のM分の１だけの削減が実現される。
【０００８】
未知のオーディオ映像信号をそのようなデータベースにおいて識別する方法は本特許請求の範囲に規定されている。Mの考えられる副次標本化ハッシュ・ワード列のどれがデータベースに格納されているかについては不確実性があるので、完全な（すなわち、非副次標本化）ハッシュ・ワード列が本方法によって未知のクリップから抽出される。「series」の語は本明細書及び特許請求の範囲の原文においては、未知の信号の、ことによると、短いセグメント又はクリップを表すのに用いられる。ハッシュ・ワードのインタリーブされたサブ列は次に、連続してデータベースに入力され、該データベースに格納された副次標本化列と突合される。該入力サブ列の少なくとも１つが特定の閾値を下回るBER（ビット誤り率）を有する場合、該信号が識別される。
【０００９】
本発明によって、所要記憶容量は、従来技術の識別方法の強健性及び信頼性が維持されると同時に、（M分の１に）削減される。
【発明を実施するための最良の形態】
【００１０】
該方法の別の効果的実施例は本特許請求の範囲に規定する。
【実施例】
【００１１】
本発明はオーディオ信号について説明する。図１は本発明による装置の概略図を表す。該装置は既知のオーディオ信号の指紋をデータベースに格納すること（第１動作モード）に加えて未知のオーディオ信号を識別すること（第２動作モード）において用いられる。
【００１２】
該装置の第１動作モード（格納）を最初に説明する。このモードでは、該装置はフルレングスの歌K(t)を受信する。該信号は、フレーミング回路１１において、おおよそ０．４秒の長さを有する時間間隔すなわちフレームF(n)に分割され、31/32のオーバラップのあるハミング・ウィンドウによって重み付けされる。該オーバラップは後続フレーム間の相関関係を大きくするのに用いられる。オーディオ信号については、これは認識される未知の信号に形成されるフレーミングが異なり得るため、不可欠のものである。
【００１３】
フレーミング回路１１は新しいフレームを１１．６ｍｓ（=0.4/32）毎に生成する。ハッシュ抽出回路１２はフレーム毎に32ビットのハッシュ・ワードH(n)を生成する。そのようなハッシュ抽出回路の実用的な実施例が上記非特許文献１に記載されている。要約すれば、該回路は各オーディオ信号フレームの周波数スペクトルを周波数帯域に分割し、帯域毎に、該帯域におけるエネルギが特定閾値を上回るか下回るかを示す、ハッシュ・ビットを生成する。図２はそのように得られたハッシュ・ワード２１の列を表す。
【００１４】
本発明によれば、ハッシュ・ワードの列は、副次標本器１３によってMの係数で副次標本化され、該副次標本器はサブ列H’(n)を生成する。ハッシュ・ワードのサブ列は、歌の題名、アーチストの名前、等のような識別データとともに、既知の歌の指紋を構成する。そのような指紋は図２に表し、番号２２はハッシュ・ワードのサブ列を表し、番号２３は、歌を識別する、題名、アーチスト、等、を表す。指紋はコンピュータ１５の制御のもとにあるデータベース１４に格納される。この例では、副次標本化係数M=４が例示として用いられ、5分の歌はおおよそ6,000x32ビットの記憶容量を必要とする。これは、副次標本化が適用されない従来技術のシステムと比較すると７５％の節減である。実際には、上記の格納動作は莫大な数の既知の歌について行われる。ハッシュ・ワード抽出（１２）及び副次標本化（１３）の動作の順序を反対にし得ることがわかる。
【００１５】
該装置の第２動作モード（識別）を次に説明する。このモードでは、該装置は未知の歌、すなわち、オーディオ・クリップU(t)、の一部分（例えば、3秒）を受信する。該クリップは上記と類似した（又は同一の）フレーミング回路１１及びハッシュ抽出回路１２によって処理される。ハッシュ抽出回路１３は該クリップの完全な（非副次標本化）ハッシュ・ブロックを抽出する。3秒のクリップについて、この動作はおおよそ２５６のハッシュ・ワードH(n)の列をもたらす。未知のオーディオ・クリップを表すそのようなハッシュ・ワード列はハッシュ・ブロックとしても表される。別の実施例では、ハッシュ・ブロックは遠隔局によって抽出され、単に該装置によって受信される。
【００１６】
ハッシュ・ブロックはインタリーブ回路１６に入力され、該回路は該ハッシュ・ブロックをMのインタリーブされたサブ列又はサブ・ブロックH0(n),  H1(n),  …HM-1(n)に分割し、Mは上記副次標本器１３において用いられたのと同じ整数である。図３はM＝４の場合のインタリーブ処理を示す。この図では、番号３１は該ハッシュ・ブロックの連続したハッシュ・ワードを表し、番号３２はサブ・ブロックH0(n)を表し、番号３３はサブ・ブロックH1(n)を表し、番号３４はサブ・ブロックHM-1(n)を表す。
【００１７】
サブ・ブロックは選定回路１７の各入力に入力される。コンピュータ１５の制御のもとで、サブ・ブロックH0(n),  H1(n),  …HM-1(n)は連続してデータベース１４に、識別するよう、入力される。ハッシュ・ワードの列が該データベースにおいて見出され、ビット誤り率（BER）（すなわち、該列と入力サブ・ブロックとの間での非整合ビットの割合）が特定閾値を下回る場合、該ハッシュ・ワード列を有する指紋が未知のオーディオ・クリップを識別する。
【００１８】
図４はコンピュータ１５によって行われるこの識別処理の流れ図を表す。工程４１では、指数ｍは初期値０を得る。該指数ｍは選定回路１７に入力されて、ハッシュ・ワードの第１インタリーブ・サブ・ブロックH0(n)が識別するよう選定される。工程４２では、選定サブ・ブロックHm(n)がデータベースに入力される。工程４３では、データベースにおいてハッシュ・ワードの類似した列が見出されたかをチェックする。本明細書及び特許請求の範囲の原文における「resembling」の語は、最低のBERを有するハッシュ・ワード列を表すものとして、該BERが特定の閾値Tよりも少ないということを前提にして、解釈される。データベースにおいて最も類似したハッシュ・ワードの列をサーチするストラテジの実際の例は上記の非特許文献１に開示される。サーチ・ストラテジの効果的実施例は更に、本出願人による係属中で非公表の欧州特許出願第01200505.4号（代理人管理番号PHNL010110号）及び欧州特許出願第01202720.7号（代理人管理番号PHNL010510号）において提案されている。
【００１９】
BERが閾値を下回る場合、該オーディオ・クリップは識別されている。データベース（図２における２３）に格納されたような歌の題名及び歌手は次に、工程４４でユーザに向けて伝達される。そうでない場合、指数ｍは増加され（工程４５）、インタリーブされたサブ・ブロックの別の１つがデータベースに入力される。全てのMのインタリーブされたサブ・ブロックを対象にサーチされたが成功裏に終わらなかった場合（工程４６）、該オーディオ・クリップは識別されなかったことになる。工程４７で、この結果がユーザに対して伝達される。
【００２０】
本発明によって、データベース容量がM分の１に削減されることが実現される。同様な削減は本例において、別のフレーム・オーバラップ、すなわち、7/8、を選択することによって効果的に実現し得ることを特筆する。これは第１動作モード（格納）に関する限りあてはまる。しかしながら、インタリーブなしの同様の7/8のオーバラップが識別処理において選択された場合、該識別の強健性及び信頼性は大いに左右される。本発明は第２動作モード（識別）におけるインタリーブの考え方において存在し、それによってインタリーブされたサブ・ブロックの少なくとも１つが、フレーム列から導出されることが実現され、該フレーム列は該格納ハッシュ・ワードが導出された該フレーム列にかなり（時間的に）整合するものである。本発明による識別処理は31/32のオーバラップのある従来技術の（非インタリーブの）方法とかなり同様な強健性及び信頼性をもたらすものである。該処理の数学的根拠を次に表す。
【００２１】
係数Mの副次標本化が適用され、ハッシュ・ブロックにおけるビットが無作為に抽出され、独立で同一な分析に従うものである場合、BERの標準偏差は√M倍に増加する。これは、強健性及び/又は信頼性が左右されることを暗に意味する。BERの閾値が同一に保たれる場合、強健性は左右されないが信頼性は低下する。一方、閾値が適切量だけ低減される場合、信頼性は同じままであるが、強健性は低下する。
【００２２】
しかしながら、オーディオ映像メディア信号のハッシュ・ブロックにおけるビットは時間軸に沿って大きな相関関係を有し、該相関関係はフレーミングの大きなオーバラップ及び音楽に固有の相関関係によってもたらされる。したがって、標準偏差ｓが、係数Mの副次標本化が適用される場合、√M倍増加するということはない。実験の結果、Mの値が小さい場合、標準偏差はわずかにも増加するということはない。副次標本化のない実用システムにおいては、BERの閾値は０．３５に設定される。係数M=4の副次標本化が適用される場合、閾値は０．３４２に低減すればよいだけである。したがって、強健性の低下はわずかなものである一方、データベースにおける所要記憶容量は4分の１に削減される。更に、ハッシュ・データベースをサーチするのに必要な時間は、単に、データベースにおけるハッシュ値が4分の１にも削減されるという理由で、減少する。
【００２３】
サーチ速度は、データベースに別のサブ・ブロックを入力することを、１つの（一般に第１の）サブ・ブロックが（閾値Tよりもかなり大きな）別の閾値よりも大きいBERを有するようである場合に、差し控えることによって、更に増加させることも可能である。（フレームのオーバラップ及び音楽に固有の相関関係による）サブ・ブロック間の大きな相関関係のために、別のサブ・ブロックがかなり低いBERを有することになることはありそうもない。
【００２４】
強健な指紋システムが開示される。そのようなシステムは未知のマルチメディア・コンテンツ（U(t)）を、該コンテンツから指紋（ハッシュ・ワード列）を抽出し、複数の既知のコンテンツ（K(t)）の指紋が格納されるデータベースにおいて類似した指紋をサーチすることによって、認識し得る。データベースにおいて指紋を効率的に格納し、該サーチを迅速化するよう、既知の信号（K(t)）のハッシュ・ワード（H(n)）がデータベース(14)に格納される前にMの係数によって副次標本化(13)される。未知の信号（U(t)）のハッシュ・ワード（H(n)）はMのインタリーブされたサブ列（H0(n),  H1(n),  …HM-1(n)）に分割される(16)。該インタリーブされたサブ列が選択的に(17)コンピュータ(15)の制御のもとでデータベース（14）に入力される。該サブ列の１つのみが十分に格納された指紋と整合する場合、該信号が識別される。
【図面の簡単な説明】
【００２５】
【図１】本発明によってデータベースにおいてオーディオ映像メディア信号の指紋を格納及び識別する装置の概略図である。
【図２】図１に表す装置の第１動作モードを示す図である。
【図３】図１に表す装置の第２動作モードを示す図である。
【図４】図１に表すコンピュータによって行われる動作工程の流れ図である。
【図１】
2005517211.tif 000003
【図２】
2005517211.tif 000004
【図３】
2005517211.tif 000005
【図４】
2005517211.tif 000006
【国際調査報告】
2005517211.tif 000007
2005517211.tif 000008