(57)【要約】  メディア・コンテンツ・ストリームがスケジュールされていないメディアセグメントを再生しているときにメディア・コンテンツ・ストリームを識別するためのシステム、方法、およびコンピュータプログラム製品が提供される。コンピューティング機器が複数のメディア・コンテンツ・ストリームを受信し、複数のメディア・コンテンツ・ストリームのうちの少なくとも２つは同じスケジュールされていないメディアセグメントを同時に含む。コンピューティング機器は、複数のメディア・コンテンツ・ストリームの各々において現時点で利用可能なメディアコンテンツを調べることによって、メディア表示装置はスケジュールされていないメディアセグメントを再生していると判定する。コンピューティング機器は、メディア・コンテンツ・ストリームに含まれるメディアコンテンツから識別情報を決定する。コンピューティング機器は、スケジュールされていないメディアセグメントがメディア表示装置によって再生されている間は無効とされる、コンテキスト的関連コンテンツを決定する。コンピューティング機器は、スケジュールされていないメディアセグメントが再生された後に、メディア・コンテンツ・ストリームおよびコンテキスト的関連コンテンツを表示する。
2018530273.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティング機器で、複数のメディア・コンテンツ・ストリームを受信するステップであって、前記コンピューティング機器は特定のときにメディア表示装置によって再生されているメディアコンテンツを識別するように構成され、前記複数のメディア・コンテンツ・ストリームのうちの少なくとも２つが同じスケジュールされていないメディアセグメントを同時に含む、複数のメディア・コンテンツ・ストリームを受信する前記ステップと、
前記メディア表示装置が現時点においてメディア・コンテンツ・ストリーム内の前記スケジュールされていないメディアセグメントを再生していると判定するステップであって、前記複数のメディア・コンテンツ・ストリームの各々において前記現時点で利用可能な前記メディアコンテンツを調べることを含む、前記スケジュールされていないメディアセグメントを再生していると判定する前記ステップと、
前記現時点において前記メディア表示装置によって再生されている前記メディア・コンテンツ・ストリームに含まれる前記メディアコンテンツから、前記メディア・コンテンツ・ストリームを識別する識別情報を決定するステップと、
前記スケジュールされていないメディアセグメントが前記メディア表示装置によって再生されている間は無効とされる、コンテキスト的関連コンテンツを決定するステップと、
前記スケジュールされていないメディアセグメントが再生された後に、前記メディア・コンテンツ・ストリームおよび前記コンテキスト的関連コンテンツを表示するステップと
を含む、方法。
【請求項２】
前記コンテキスト的関連コンテンツは前記識別情報を用いて選択され、前記コンテキスト的関連コンテンツは前記メディア表示装置に提供される、請求項１に記載の方法。
【請求項３】
前記メディア・コンテンツ・ストリームを識別することは、前記スケジュールされていないメディアセグメントが前記メディア表示装置によって再生されている間に、前記メディア・コンテンツ・ストリームについての追加識別情報を提供する前記スケジュールされていないメディアセグメントに重ね合あわされたグラフィックを検出することを含む、請求項１に記載の方法。
【請求項４】
前記識別情報を決定するのに用いられる前記メディアコンテンツは、前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの前または後に含まれるメディアコンテンツを含む、請求項１に記載の方法。
【請求項５】
前記メディア表示装置は前記スケジュールされていないメディアセグメントを、前記スケジュールされていないメディアセグメントの始めから再生していると判定するステップと、
前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの前に含まれるメディアコンテンツについて決定された識別情報を用いて前記メディア・コンテンツ・ストリームを識別するステップと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記メディア表示装置は前記スケジュールされていないメディアセグメントを、前記スケジュールされていないメディアセグメントの始めより後の時点から再生していると判定するステップと、
前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの後に含まれるメディアコンテンツについての識別情報を用いて前記メディア・コンテンツ・ストリームを識別するステップと
をさらに含む、請求項１に記載の方法。
【請求項７】
１つまたは複数のプロセッサと、
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに動作を行わせる命令を含む非一時的なコンピュータ可読媒体であって、前記動作は、
複数のメディア・コンテンツ・ストリームを受信する動作であって、コンピューティング機器は特定のときにメディア表示装置によって再生されているメディアコンテンツを識別するように構成され、前記複数のメディア・コンテンツ・ストリームのうちの少なくとも２つが同じスケジュールされていないメディアセグメントを同時に含む、複数のメディア・コンテンツ・ストリームを受信する前記動作と、
前記メディア表示装置が現時点においてメディア・コンテンツ・ストリーム内の前記スケジュールされていないメディアセグメントを再生していると判定する動作であって、前記複数のメディア・コンテンツ・ストリームの各々において前記現時点で利用可能な前記メディアコンテンツを調べることを含む、前記スケジュールされていないメディアセグメントを再生していると判定する前記動作と、
前記現時点において前記メディア表示装置によって再生されている前記メディア・コンテンツ・ストリームに含まれる前記メディアコンテンツから、前記メディア・コンテンツ・ストリームを識別する識別情報を決定する動作と、
前記スケジュールされていないメディアセグメントが前記メディア表示装置によって再生されている間は無効とされる、コンテキスト的関連コンテンツを決定する動作と、
前記スケジュールされていないメディアセグメントが再生された後に、前記メディア・コンテンツ・ストリームおよび前記コンテキスト的関連コンテンツを表示する動作と
を含む、前記非一時的なコンピュータ可読媒体と
を含む、コンピューティング機器。
【請求項８】
前記コンテキスト的関連コンテンツは前記識別情報を用いて選択され、前記コンテキスト的関連コンテンツは前記メディア表示装置に提供される、請求項７に記載のコンピューティング機器。
【請求項９】
前記メディア・コンテンツ・ストリームを識別するための前記命令は、前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記スケジュールされていないメディアセグメントが前記メディア表示装置によって再生されている間に、前記メディア・コンテンツ・ストリームについての追加識別情報を提供する前記スケジュールされていないメディアセグメントに重ね合あわされたグラフィックを検出する動作
を含む動作を行わせる命令を含む、請求項７に記載のコンピューティング機器。
【請求項１０】
前記識別情報を決定するのに用いられる前記メディアコンテンツは、前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの前または後に含まれるメディアコンテンツを含む、請求項７に記載のコンピューティング機器。
【請求項１１】
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記メディア表示装置は前記スケジュールされていないメディアセグメントを、前記スケジュールされていないメディアセグメントの始めから再生していると判定する動作と、
前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの前に含まれるメディアコンテンツについて決定された識別情報を用いて前記メディア・コンテンツ・ストリームを識別する動作と
を含む動作を行わせる命令をさらに含む、請求項７に記載のコンピューティング機器。
【請求項１２】
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記メディア表示装置は前記スケジュールされていないメディアセグメントを、前記スケジュールされていないメディアセグメントの始めより後の時点から再生していると判定する動作と、
前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの後に含まれるメディアコンテンツについての識別情報を用いて前記メディア・コンテンツ・ストリームを識別する動作と
を含む動作を行わせる命令をさらに含む、請求項７に記載のコンピューティング機器。
【請求項１３】
特定のときに前記メディア表示装置によって再生されているメディアコンテンツを識別するための前記命令は、前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記メディアコンテンツからサンプルを取得する動作と、
前記サンプルからキューを生成する動作と、
前記キューを、識別情報を含むキューのデータベースと照合する動作と
を含む動作を行わせる命令を含む、請求項７に記載のコンピューティング機器。
【請求項１４】
特定のときに前記メディア表示装置によって再生されているメディアコンテンツを識別するための前記命令は、前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記メディアコンテンツからのデータを使用する動作であって、前記コンピューティング機器は前記メディアコンテンツに含まれる映像データまたは音声データから前記データを取得することができる、前記メディアコンテンツからのデータを使用する前記動作
を含む動作を行わせる命令を含む、請求項７に記載のコンピューティング機器。
【請求項１５】
１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
複数のメディア・コンテンツ・ストリームを受信させる命令であって、コンピューティング機器は特定のときにメディア表示装置によって再生されているメディアコンテンツを識別するように構成され、前記複数のメディア・コンテンツ・ストリームのうちの少なくとも２つが同じスケジュールされていないメディアセグメントを同時に含む、複数のメディア・コンテンツ・ストリームを受信させる前記命令と、
前記メディア表示装置が現時点においてメディア・コンテンツ・ストリーム内の前記スケジュールされていないメディアセグメントを再生していると判定させる命令であって、前記複数のメディア・コンテンツ・ストリームの各々において前記現時点で利用可能な前記メディアコンテンツを調べることを含む、前記スケジュールされていないメディアセグメントを再生していると判定させる前記命令と、
前記現時点において前記メディア表示装置によって再生されている前記メディア・コンテンツ・ストリームに含まれる前記メディアコンテンツから、前記メディア・コンテンツ・ストリームを識別する識別情報を決定させる命令と、
前記スケジュールされていないメディアセグメントが前記メディア表示装置によって再生されている間は無効とされる、コンテキスト的関連コンテンツを決定させる命令と、
前記スケジュールされていないメディアセグメントが再生された後に、前記メディア・コンテンツ・ストリームおよび前記コンテキスト的関連コンテンツを表示させる命令と
を含む、非一時的な機械可読記憶媒体において有形に具体化されたコンピュータプログラム製品。
【請求項１６】
前記コンテキスト的関連コンテンツは前記識別情報を用いて選択され、前記コンテキスト的関連コンテンツは前記メディア表示装置に提供される、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
前記メディア・コンテンツ・ストリームを識別するための前記命令は、前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記スケジュールされていないメディアセグメントが前記メディア表示装置によって再生されている間に、前記メディア・コンテンツ・ストリームについての追加識別情報を提供する前記スケジュールされていないメディアセグメントに重ね合あわされたグラフィックを検出させる命令
を含む、請求項１５に記載のコンピュータプログラム製品。
【請求項１８】
前記識別情報を決定するのに用いられる前記メディアコンテンツは、前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの前または後に含まれるメディアコンテンツを含む、請求項１５に記載のコンピュータプログラム製品。
【請求項１９】
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記メディア表示装置は前記スケジュールされていないメディアセグメントを、前記スケジュールされていないメディアセグメントの始めから再生していると判定させる命令と、
前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの前に含まれるメディアコンテンツについて決定された識別情報を用いて前記メディア・コンテンツ・ストリームを識別させる命令と
をさらに含む、請求項１５に記載のコンピュータプログラム製品。
【請求項２０】
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記メディア表示装置は前記スケジュールされていないメディアセグメントを、前記スケジュールされていないメディアセグメントの始めより後の時点から再生していると判定させる命令と、
前記メディア・コンテンツ・ストリームにおいて前記スケジュールされていないメディアセグメントの後に含まれるメディアコンテンツについての識別情報を用いて前記メディア・コンテンツ・ストリームを識別させる命令と
をさらに含む、請求項１５に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]関連出願の相互参照
本出願は、参照によりその全体が組み入れられる、２０１５年７月１６日に出願された米国仮特許出願第６２／１９３３２２号の米国特許法１１９（ｅ）条の下での恩典を主張するものである。
【０００２】
[0002]本出願は、２０１３年１１月２５日に出願された米国特許出願第１４／０８９００３号、２０１４年１１月２５日に発行された現在の米国特許第８８９８７１４号；米国特許出願第１４／２１７０７５号、２０１５年６月９日に発行された現在の米国特許第９０５５３０９号；２００９年５月２９日に出願された米国仮特許出願第６１／１８２３３４号；２００９年１２月２９日に出願された米国仮特許出願第６１／２９０７１４号；米国特許出願第１２／７８８７４８号、２０１４年７月１日に発行された現在の米国特許第８７６９５８４号；および米国特許出願第１２／７８８７２１号、２０１３年１１月２６日に発行された現在の米国特許第５９５７８１号に関連するものであり、これらの出願はすべて、参照によりその全体が本明細書に組み入れられる。
【発明の概要】
【課題を解決するための手段】
【０００３】
[0003]自動コンテンツ認識（ＡＣＲ）システムは、特定の時点において特定のメディア表示装置によって表示されているコンテンツに関する情報を提供する。ＡＣＲシステムは、映像照合システムとして実施することができる。一般に、映像照合システムは、既知の映像データソースからデータサンプルを取得し、これらのサンプルから識別情報を生成し、識別情報を映像に関する既知の情報と共にデータベースに格納することによって動作する。特定のメディア装置は、表示されている未知の映像からデータサンプルを取得し、サンプルから識別情報を生成し、識別情報をデータベースに格納された識別情報と照合しようと試みる。一致が見つかると、特定のメディア装置は、データベースから、その映像について既知である情報を受信することができる。一般に、メディア装置が実行する照合動作は、リアルタイムで、すなわち映像が装置上で表示されているときに同時に実行することができる。
【０００４】
[0004]メディア・コンテンツ・ストリームがスケジュールされていない共通メディアセグメントを再生しているときにメディア・コンテンツ・ストリームを識別するためのシステム、方法、およびコンピュータプログラム製品が提供される。様々な実施態様において、コンピューティング機器は、特定のときにメディア表示装置によって再生されているメディアコンテンツを識別するように構成される。コンピューティング機器は、映像照合システムを実施するように構成される。コンピューティング機器は、複数のメディア・コンテンツ・ストリームを受信し、複数のメディア・コンテンツ・ストリームのうちの少なくとも２つは同じスケジュールされていないメディアセグメントを同時に含む。コンピューティング機器は、メディア表示装置が現時点においてスケジュールされていないメディアセグメントを再生していると判定するように構成される。この判定を行うために、コンピューティング機器は、複数のメディア・コンテンツ・ストリームの各々において現時点で利用可能なメディアコンテンツを調べる。コンピューティング機器は、現時点においてメディア表示装置によって再生されているメディア・コンテンツ・ストリームに含まれるメディアコンテンツから識別情報を決定するようにさらに構成される。識別情報はメディア・コンテンツ・ストリームを識別する。コンピューティング機器は、コンテキスト的関連コンテンツをさらに決定する。コンテキスト的関連コンテンツは、スケジュールされていないメディアセグメントがメディア表示装置によって再生されている間は無効とされる。コンピューティング機器は、スケジュールされていないメディアセグメントが再生された後に、メディア・コンテンツ・ストリームおよびコンテキスト的関連コンテンツを表示するようにさらに構成される。
【０００５】
[0005]様々な実施態様において、コンテキスト的関連コンテンツは、メディア・コンテンツ・ストリームを識別する識別情報を用いて選択される。コンテキスト的関連コンテンツは、メディア表示装置に提供される。
【０００６】
[0006]様々な実施態様において、メディア・コンテンツ・ストリームを識別することは、スケジュールされていないメディアセグメントがメディア表示装置によって再生されている間にスケジュールされていないメディアセグメントに重ね合あわされたグラフィックを検出することを含む。グラフィックは、メディア・コンテンツ・ストリームについての追加識別情報を提供する。
【０００７】
[0007]様々な実施態様において、識別情報を決定するのに用いられるメディアコンテンツは、メディア・コンテンツ・ストリームにおいてスケジュールされていないメディアセグメントの前または後に含まれるメディアコンテンツを含む。
【０００８】
[0008]様々な実施態様において、コンピューティング機器は、メディア表示装置がスケジュールされていないメディアセグメントを、スケジュールされていないメディアセグメントの始めから再生していると判定するように構成される。これらの実施態様では、コンピューティング機器は、メディア・コンテンツ・ストリームにおいてスケジュールされていないメディアセグメントの前に含まれるメディアコンテンツについて決定された識別情報を用いてメディア・コンテンツ・ストリームを識別する。
【０００９】
[0009]様々な実施態様において、コンピューティング機器は、メディア表示装置がスケジュールされていないメディアセグメントを、スケジュールされていないメディアセグメントの始めより後の時点から再生していると判定するように構成される。これらの実施態様では、コンピューティング機器は、メディア・コンテンツ・ストリームにおいてスケジュールされていないメディアセグメントの後に含まれるメディアコンテンツの識別情報を用いてメディア・コンテンツ・ストリームを識別する。
【図面の簡単な説明】
【００１０】
[0010]下記の図に関連して以下で例示的な実施形態を詳細に説明する。
【図１】未知のコンテンツを識別することができる照合システムを示す図である。
【図２】未知のデータを識別するための照合システムの構成要素を示す図である。
【図３】復号器のメモリバッファ３０２を含む映像インジェスト・キャプチャ・システムの一例を示す図である。
【図４】復号器のメモリバッファを含む映像インジェスト・キャプチャ・システムを示す図である。
【図５】インタラクティブ・テレビ・システムのための映像照合システムの一例を示す図である。
【図６】複数のコンテンツストリームが同じメディアセグメントを同時に搬送している一例を示す図である。
【図７】テレビチャンネルとして例示された複数のメディアストリームが同じメディアコンテンツを同時に表示する別の例を示す図である。
【図８】複数のメディア・コンテンツ・ストリームが同じ共通メディアセグメントをほぼ同時に搬送している一例を示す図である。
【図９】メディア表示装置によって再生されている共通メディアセグメントに重ね合わされているグラフィックの一例を示す図である。
【図１０】複数のメディア・コンテンツ・ストリームが同じスケジュールされていないメディアセグメントを含む場合に実施されうるプロセスの一例を示す図である。
【図１１】点位置とそれらの周りの経路点とを示す図である。
【図１２】クエリ点「ｘ」から半径「ｒ」の距離内に位置する点の集合を示す図である。
【図１３】「ｎ」次元空間における角度が候補点適格性の一部として計算される可能な点の値を示す図である。
【図１４】クエリ点「ｘ」からの距離および角度を適用して経路追跡の次の照合システムステップに提出するための候補「被疑点」が決定される、図１２と図１３との組み合わせを示す図である。
【図１５】自己交差経路とクエリ点とを示す図である。
【図１６】３つの連続した点位置とそれらの周りの経路点とを示す図である。
【発明を実施するための形態】
【００１１】
[0027]自動コンテンツ認識（ＡＣＲ）システムは、特定の時点において特定のメディア表示装置によって表示されているコンテンツに関する情報を提供する。例えば、ＡＣＲシステムは、視聴されているチャンネル、映像のタイトル、映像または映像のコンテンツを識別する何らかのテキスト、視聴されている映像の部分、映像の１つまたは複数のカテゴリ、映像の作成者および／または製作者などといった情報を提供することができる。この情報は、後で、例えば、映像の視聴率統計を提供するのに（例えば、映像がどの程度の頻度で何人の人に、いつ視聴されたかなど）、かつ／または広告やインタラクティブコンテンツなど、視聴者にターゲットコンテンツを勧めるのに使用することができる。
【００１２】
[0028]ＡＣＲシステムは、映像照合システムとして実施することができる。一般に、映像照合システムは、既知の映像データソースからデータサンプルを取得し、これらのサンプルから識別情報を生成し、識別情報を映像に関する既知の情報と共にデータベースに格納することによって動作する。特定のメディア装置は、同様のプロセスを用いて未知の映像コンテンツを識別することができる。具体的には、メディア装置は、表示されている未知の映像からデータサンプルを取得し、サンプルから識別情報を生成し、識別情報をデータベースに格納された識別情報と照合しようと試みる。一致が見つかると、特定のメディア装置は、データベースから、その映像について既知である情報を受信することができる。一般に、メディア装置が実行する照合動作は、リアルタイムで、すなわち映像が装置上で表示されているときに同時に実行することができる。
【００１３】
[0029]しかし、上述の映像照合システムでは、同じコンテンツが複数のチャンネルで同時に表示されているときにメディア装置によって表示されているメディアコンテンツを識別するのが困難な場合がある。さらに、このシステムは、例えば、視聴者がどのチャンネルを視聴しているかや、どんなコンテキスト的関連情報を提供すべきかを判定することができない場合もある。
【００１４】
[0030]複数のチャンネルが同じコンテンツを同時に表示する１つの例は、複数のローカルテレビ局が「ニュース速報」記事をサポートするシンジケートコンテンツを提供する場合に発生する。例えば、全国放送提供会社（例えば、ＡＢＣ（Ａｍｅｒｉｃａｎ  Ｂｒｏａｄｃａｓｔｉｎｇ  Ｃｏｍｐａｎｙ）、ＣＢＳ（Ｃｏｌｕｍｂｉａ  Ｂｒｏａｄｃａｓｔｉｎｇ  Ｓｙｓｔｅｍ）、ＮＢＣ（Ｎａｔｉｏｎａｌ  Ｂｒｏａｄｃａｓｔｉｎｇ  Ｃｏｍｐａｎｙ）、ＦＯＸネットワーク、ＣＮＮ（Ｃａｂｌｅ  Ｎｅｗｓ  Ｎｅｔｗｏｒｋ）など）は、政治的発言、自然災害、人為的事件が発生したときに映像配信を提供する。この例では、複数の全国放送チャンネルおよび／またはローカル放送チャンネルは、映像配信が全国放送局によって放送されているときに同時にその映像配信をピックアップし、その配信をローカル視聴者に中継放送する。その結果、複数のチャンネルが映像コンテンツを同時に全く同様に表示することになる。同じ状況は、複数のチャンネルが同じコマーシャルまたはスポーツイベントを同時に表示する場合など、他のコンテキストでも発生しうる。
【００１５】
[0031]上記のように、映像照合システムは、番組情報で映像コンテンツのタイトルや他の識別文字列などの情報、および映像コンテンツに関する他の情報を提供する、ローカルチャンネルや全国チャンネルなどの既知の映像ソースから収集されたデータサンプルに依拠することができる。しかし、複数のチャンネルが同じコンテンツを表示する場合には、映像照合システムが映像コンテンツを一意に識別できない可能性もある。例えば、映像照合システムは１つの映像を２つ以上のチャンネルと関連付ける。続いて、メディア装置が同じコンテンツを流しているチャンネルのうちの１つに同調した場合、映像照合システムは、メディア装置がどのチャンネルに同調したか判定することができない可能性もある。
【００１６】
[0032]様々な実施態様において、映像照合システムは、複数のチャンネルで同時に現れる共通映像セグメントによって生じる曖昧さの存在下で自動コンテンツ認識の精度を改善するように構成される。精度が改善されないと、複数のチャンネルで同時に表示されている共通映像セグメントが存在しているために、メディア装置によって表示されているコンテンツの識別が曖昧になる可能性がある。様々な実施態様において、映像照合システムは、メディア装置が共通映像セグメントを表示し始める前および／または後にメディア表示装置で表示されたメディアコンテンツからの情報を使用する。この情報を用いて、映像照合システムは、共通映像セグメントから取得したサンプルに識別情報を添付することができる。
【００１７】
[0033]ある時点で共通映像セグメントを表示する可能性のある全国チャンネルおよびローカルチャンネルでは、チャンネルは、共通映像セグメントを表示する前にある一意に識別可能なコンテンツを提供する場合がある。様々な実施態様において、この一意のコンテンツを用いて共通映像セグメントの識別を支援することができる。例えば、ある放送ニュースには、ローカルチャンネルからのものであることが知られているニュース番組の部分がある。例えば、このニュース番組では、共通映像セグメントが表示される前に共通映像セグメントを紹介し、かつ／または共通映像セグメントについてコメントする。紹介セグメントを、「トーキングヘッド」セグメント、すなわち、２人以上の人が机の後ろに座り、その中央胸部から上が映像内に収まるセグメントと呼ぶことができる。「トーキングヘッド」セグメントが検出されると、映像照合システムは、例えば、共通映像セグメントの識別を支援するのに使用できる新しいタイムライン信号またはイベントを追加することができる。
【００１８】
[0034]様々な実施態様において、映像照合システムを用いるように構成されたメディア表示装置は、「トーキングヘッド」セグメントのために生成されるようなタイムライン信号またはイベントを取得し、追跡する。これらの実施態様では、メディア装置は、メディア装置が未知の、おそらくは共通映像セグメントに遭遇すると、タイムラインイベントがないかチェックする。ある場合には、メディア装置はタイムラインイベントを見つけられず、これは、メディア装置が電源投入されたばかりであり、または共通映像コンテンツを表示しているチャンネルに同調したばかりであることをメディア装置に指示する。この場合、メディア装置のデータ収集プロセスは、識別目的でその共通映像セグメントを使用することを避けるように構成される。他の場合には、メディア装置は、共通映像セグメントの前および／または後に受信されたタイムラインイベントを用いて共通映像セグメントの識別情報を生成する。
【００１９】
[0035]様々な実施態様において、映像照合では、コマーシャルをより迅速に識別するのにもタイムラインイベントを用いる。一般に、映像照合システムが、高度の確率で既知のコマーシャルを照合するのに十分なサンプルを取得するのに要する時間量を、「コマーシャル信頼区間」と呼ぶ。本明細書に記載する技術を用いると、メディア装置が指定された過去時間ウインドウ内のタイムラインイベントを使用した場合にコマーシャル信頼区間は低減する。
【００２０】
[0036]Ｉ．音声・映像コンテンツ
様々な実施態様において、映像コンテンツ照合システムは、メディア表示装置によって表示されているメディアコンテンツを識別するように構成される。様々な実施態様において、映像コンテンツシステムは、メディア表示装置にコンテキスト的ターゲットコンテンツを提供するのに用いることができ、ターゲットコンテンツは識別されたメディアコンテンツに基づいて選択される。
【００２１】
[0037]メディアコンテンツは、映像、音声、テキスト、グラフィック、視覚データおよび／または可聴データの触覚表現、ならびに視覚情報、可聴情報または触覚情報の様々な組み合わせを含む。例えば、メディアコンテンツは、映画やテレビ番組など、同期された音声と映像を含むことができる。別の例として、メディアコンテンツは、ウェブページなど、テキストとグラフィックを含むことができる。別の例として、メディアコンテンツは、サウンドトラックを伴った写真スライドショーなど、写真と音楽を含むことができる。
【００２２】
[0038]メディア表示装置は、様々なメディアコンテンツを表示することができる装置とすることができる。メディア表示装置には、例えば、テレビシステムが含まれる。テレビ（ＴＶ）システムには、例えば、ウェブＴＶや接続ＴＶ（「スマートＴＶ」としても知られている）などのテレビ、ならびに任意選択で、セットトップボックス（ＳＴＢ）、デジタル・ビデオ・ディスク（ＤＶＤ）・プレーヤ、および／またはデジタル・ビデオ・レコーダ（ＤＶＲ）などといった、ＴＶに組み込まれた、またはＴＶと同じ場所に置かれる機器が含まれる。
【００２３】
[0039]接続ＴＶは、インターネットなどのネットワークに接続されたＴＶである。様々な実施態様において、ネットワーク接続ＴＶは、例えば、家庭や企業のオフィスなどにおいて、ローカルの有線または無線ネットワークに接続されている。接続ＴＶは、ＧｏｏｇｌｅのＡｎｄｒｏｉｄなどのアプリケーションプラットフォームや、「アプリ」とも呼ばれる、インタラクティブなスマートフォンまたはタブレット様のソフトウェアアプリケーションを提供するように構成された何らかの他のプラットフォームを実行することができる。
【００２４】
[0040]様々な実施態様において、メディア表示装置は、テレビ信号などの信号を受信する。テレビ信号には、例えば、一緒に放送され、同時に表示するために同期された映像および音声データを表す信号が含まれる。例えば、テレビ信号は、テレビ番組および／またはコマーシャルを含む。場合によっては、テレビ信号は、テレビ信号内の音声・映像コンテンツに関する追加情報を含む。この追加データを「メタデータ」と呼ぶ。「メタデータ」という用語は、テレビ信号として以外に送信される（例えば、ネットワーク上でデジタル化データおよび／またはパケット化データとして送信される）映像または音声・映像コンテンツと関連付けられた情報を記述するのにも用いられる。メタデータは、コンテンツを識別する情報、コンテンツの記述、コンテンツの１つまたは複数のカテゴリ、コンテンツの作成者および／または発行者などといった、コンテンツに関する情報を含む。メタデータは、メタデータが関連付けられているコンテンツと共に送信されるので、メタデータを用いて、コンテンツが視聴され、または再生されているときに同時にコンテンツに関する情報を提供することができる。
【００２５】
[0041]すべてのメディア表示装置がメタデータにアクセスできるとは限らない。よって、すべてのメディア表示装置が、任意の瞬間に何を表示しており、または再生しているか判定できるとは限らない。この情報がなければ、メディア表示装置は、特定の視聴者のためにカスタマイズされ、または個別化されたコンテンツまたは広告を提供することができない可能性もある。メディア表示装置に提供されているコンテンツに関する若干の情報が配信パイプラインにおいて入手できる場合もあるが、この情報は、コンテンツがメディア表示装置に到着するまでに失われ、または除去される可能性がある。
【００２６】
[0042]いくつかの実施態様では、メタデータが様々な方法を用いて音声・映像コンテンツと共に提供される。例えば、いくつかの実施態様では、識別情報がウォーターマークを用いてコンテンツに符号化される。これらの実施態様では、識別情報は、コンテンツが送信のために圧縮され、表示のために伸張されるときに情報が失われないように符号化される。しかし、このような方法では、受信側メディア表示装置がコンテンツから識別情報を抽出できることが必要となりうる。加えて、これらの方法では、１秒の何分の１の識別能力で、再生されている特定の映像の現在の瞬間までの識別を行うことができない場合もある。
【００２７】
[0043]様々な実施態様において、光ファイバおよびデジタル伝送技術の進歩により、メディア産業は大きなチャンネル容量を提供することができるようになっており、「チャンネル」には、従来の放送チャンネル、衛星信号、デジタルチャンネル、ストリーミングコンテンツ、および／またはユーザ生成コンテンツが含まれる。場合によっては、衛星システムなどのメディアプロバイダを、多チャンネル映像番組配信事業者（Ｍｕｌｔｉｃｈａｎｎｅｌ  Ｖｉｄｅｏ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｄｉｓｔｒｉｂｕｔｏｒ（ＭＶＰＤ））と呼ぶこともある。いくつかの実施態様において、メディアプロバイダは、最新の伝送システムの増加したデータ容量を用いてインタラクティブテレビ（ＩＴＶ）などのインタラクティブコンテンツの一部を提供することもできる。スマートＴＶ、セットトップボックス、および類似した装置の処理能力が増加すればさらなるインタラクティブコンテンツ使用が可能になる。
【００２８】
[0044]インタラクティブテレビは、テレビシステムがワールド・ワイド・ウェブと同様に双方向情報配信機構として機能することを可能にすることができる。インタラクティブテレビは、例えば、視聴者が宣伝された製品やサービスを注文する、ゲーム番組で競技者と対戦する、ライブの授業セッションに参加するなどといった、様々なマーケティング機能、娯楽機能、および教育機能を提供することができる。いくつかの実施態様では、インタラクティブ機能は、セットトップボックスによって制御される。これらの実施態様では、セットトップボックスは、ＴＶ放送などの映像コンテンツと関連付けられたインタラクティブプログラムを実行する。インタラクティブ機能はＴＶの画面上に表示され、視聴者がＴＶのリモートコントローラまたはキーボードを介して選択できるアイコンまたはメニューを含む。
【００２９】
[0045]様々な実施態様において、インタラクティブコンテンツが音声・映像コンテンツに組み込まれる。いくつかの実施態様では、音声・映像コンテンツは、放送ストリームからなる。放送ストリームを「チャンネル」または「ネットワークフィード」とも呼ぶ。「放送ストリーム」という用語は、例えば、アンテナ、衛星、同軸ケーブル、デジタル加入者回線（ＤＳＬ）ケーブル、光ファイバケーブル、または何らかの他の伝送媒体上でテレビによって受信される放送信号をいう。様々な実施態様において、インタラクティブコンテンツが、「トリガ」を用いて音声・映像コンテンツに組み込まれる。トリガは、特定の番組のコンテンツに挿入される。トリガを含むコンテンツを、「強化型番組コンテンツ」または「強化型テレビ番組」または「強化型映像信号」と呼ぶこともある。トリガは、（例えば、セットトップボックスやスマートＴＶのプロセッサのところの）メディア表示装置にインタラクティブコンテンツが利用可能であることを通知するのに用いられる。トリガは、利用可能なコンテンツに関する情報、およびインタラクティブコンテンツがどこにあるか（例えば、メモリアドレス、ネットワークアドレス、および／またはウェブサイトアドレス）を含む。トリガはまた、メディア表示装置上で視聴者に表示することができる情報も含む。例えば、トリガによって提供される情報は、メディア表示装置によって提供される画面の下部に表示される。表示された情報は、視聴者に何らかのアクションを行い、または複数のオプションの中から選択するよう促す。
【００３０】
[0046]ＩＩ．映像照合
様々な実施態様において、映像コンテンツシステムは、メディア表示装置によって表示または再生されているメディアコンテンツを識別するように構成される。様々な実施態様において、特定の瞬間に視聴されているコンテンツを識別する情報を用いて、コンテンツの巻き戻しを要求する、映像をその始めから再開するよう要求するといった、視聴者の特定の反応を取得し、これに適切に応答することができる。代替として、または加えて、識別情報を用いて、コンテンツプロバイダまたは広告主によって提供されうる、広告などのターゲットコンテンツをトリガすることもできる。よって、音声・映像コンテンツを識別する情報を用いて、通常はスマートＴＶ機能を備えていない装置に視聴者ごとにカスタマイズされたビデオオンデマンド（ＶｏＤ）機能を提供することができる。
【００３１】
[0047]様々な実施態様において、メディア表示装置の画面上に表示されている画素データのサブセットを定期的な間隔でサンプリングし、次いで、コンテンツデータベースにおいて類似した画素データを見つけることによって、映像セグメントが識別される。いくつかの実施態様では、映像セグメントと関連付けられた音声データを抽出し、コンテンツデータベースにおいて類似した音声データを見つけることによって、映像セグメントが識別される。いくつかの実施態様では、自動音声認識技術を用いて映像セグメントと関連付けられた音声データを処理し、既知の映像コンテンツからのテキスト転写を探索して一致するテキストフレーズを捜し出すことによって映像セグメントが識別される。いくつかの実施態様では、映像セグメントと関連付けられたメタデータを処理することによって映像セグメントが識別される。
【００３２】
[0048]様々な実施態様において、映像照合システムは、インタラクティブメディア表示システムにコンテキスト的ターゲットコンテンツを提供するのに用いられる。コンテキスト的ターゲットコンテンツは、表示されている映像セグメントの識別に基づくと共に、映像セグメントが再生されている時間（昼または夜、午後３：００など）および／または現在表示されている映像セグメントの部分（例えば、映像の始めからの現在のオフセット）にも基づくものとすることができる。本明細書では、現在表示されている映像の部分を記述するのに「再生時間」と「オフセット時間」とを区別なく用いる。
【００３３】
[0049]様々な実施態様において、メディア表示装置によって現在表示または再生されているコンテンツを識別したコンテンツ照合システムを備えるメディア表示装置は、コンテンツの主題を推論し、それに応じて視聴者とインタラクションすることができる。例えば、メディア表示装置は、コンテンツのビデオオンデマンドバージョンおよび／またはより高い解像度もしくは３Ｄフォーマットの当該コンテンツへの即座のアクセスを提供することができる。加えて、メディア表示装置は、コンテンツを最初から再生、早送り、一時停止、および巻き戻しできる機能も提供する。様々な実施態様において、コンテンツに広告を含めることができる。これらの実施態様では、例えば、視聴者の地理的位置や、人口統計群や、買い物履歴に合わせて一部または全部の広告メッセージをカスタマイズすることができる。代替として、または加えて、広告の数または長さを減らすこともでき、完全に取り除くこともできる。
【００３４】
[0050]様々な実施態様において、映像セグメントが識別されると、メディア表示装置によって表示または再生されている画素データ（または関連付けられた音声データ）のサブセットをサンプリングし、コンテンツデータベースにおいて類似した画素（または音声）データを見つけることによって、オフセット時間が決定される。様々な実施態様において、オフセット時間は、そのような映像セグメントと関連付けられた音声または画像データを抽出し、コンテンツデータベースにおいて類似した音声または画像データを見つけることによって決定することができる。様々な実施態様において、オフセット時間は、自動音声認識技術を用いてそのような映像セグメントと関連付けられた音声データを処理することによって決定することができる。様々な実施態様において、オフセット時間は、そのような映像セグメントと関連付けられたメタデータを処理することによって決定することができる。
【００３５】
[0051]様々な実施態様において、映像照合のためのシステムをテレビシステムに含めることができる。様々な実施態様において、テレビシステムは接続ＴＶを含む。様々な実施態様において、映像照合システムは、一部は接続テレビに、一部はインターネット上で接続テレビに接続されたサーバ上に含まれる。
【００３６】
[0052]図１に、未知のコンテンツを識別することができる照合システム１００を示す。いくつかの例では、未知のコンテンツは１つまたは複数の未知のデータ点を含むことができる。そのような例では、照合システム１００は、未知のデータ点を基準データ点と照合して、未知のデータ点と関連付けられた未知の映像セグメントを識別することができる。基準データ点は基準データベース１１６に含めることができる。
【００３７】
[0053]照合システム１００は、クライアント機器１０２と照合サーバ１０４とを含む。クライアント機器１０２は、メディアクライアント１０６と、入力装置１０８と、出力装置１１０と、１つまたは複数のコンテキストアプリケーション１２６とを含む。メディアクライアント１０６（テレビシステム、コンピュータシステム、またはインターネットに接続できる他の電子機器を含むことができる）は、映像番組１２８と関連付けられたデータ（例えば、放送信号、データパケット、他のフレームデータ）を復号することができる。メディアクライアント１０６は、映像の各フレームの復号されたコンテンツを、映像フレームの画素情報の表示またはさらなる処理に備えて映像フレームバッファに入れることができる。クライアント機器１０２は、映像信号を受信し、復号することができる任意の電子復号システムとすることができる。クライアント機器１０２は、映像番組１２８を受信し、映像情報を映像バッファ（図示せず）に格納することができる。クライアント機器１０２は、映像バッファ情報を処理し、図３に関連して以下でより詳細に説明する未知のデータ点（「キュー」と呼ぶことができる）を生成することができる。メディアクライアント１０６は、基準データベース１１６内の基準データ点と比較するために、未知のデータ点を照合サーバ１０４に送信することができる。
【００３８】
[0054]入力装置１０８には、メディアクライアント１０６に要求または他の情報が入力されることを可能にする任意の適切な装置を含むことができる。例えば、入力装置１０８には、キーボード、マウス、音声認識入力装置、無線機器からの（例えば、リモートコントローラ、モバイル機器、他の適切な無線機器からの）無線入力を受信するための無線インターフェース）、または任意の他の適切な入力装置を含むことができる。出力装置１１０には、ディスプレイ、無線機器（例えば、モバイル機器や他の適切な無線機器）に無線出力を送信するための無線インターフェース、プリンタ、または他の適切な出力装置など、情報を提示し、またはそれ以外に出力することができる任意の適切な装置を含むことができる。
【００３９】
[0055]照合システム１００は、最初に既知の映像データソース１１８からデータサンプルを収集することによって映像セグメントを識別するプロセスを開始することができる。例えば、照合サーバ１０４は、様々な映像データソース１１８から基準データベース１１６を構築し、維持するためにデータを収集する。映像データソース１１８には、テレビ番組、映画、または任意の他の適切な映像ソースのメディアプロバイダを含むことができる。映像データソース１１８からの映像データは、無線放送として、ケーブルＴＶチャンネルとして、インターネットからのストリーミングソースとして、また任意の他の映像データソースから提供することができる。いくつかの例では、照合サーバ１０４は、後述するように、映像データソース１１８からの受信映像を、基準データベース１１６において基準映像データ点を生成、収集するように処理することができる。いくつかの例では、映像データソース１１８からの映像番組を基準映像番組インジェストシステム（図示せず）によって処理することができ、基準映像番組インジェストシステムは、基準映像データ点を生成し、それらを格納するために基準データベース１１６に送ることができる。基準データ点は、上述のように、後で未知のデータ点を分析するのに用いられる情報を決定するのに用いることができる。
【００４０】
[0056]照合サーバ１０４は、ある期間（例えば、日数、週数、月数、または任意の他の適切な期間）にわたって受信された映像番組ごとの基準映像データ点を基準データベース１１６に格納することができる。照合サーバ１０４は、（例えば、キューまたはキュー値とも呼ばれる基準データ点を含む）テレビ番組サンプルの基準データベース１１６を構築し、絶えず、または定期的に更新することができる。いくつかの例では、収集されたデータは、周期的な映像フレーム（例えば、５番目ごとの映像フレーム、１０番目ごとの映像フレーム、１５番目ごとの映像フレーム、他の適切な数のフレーム）からサンプリングされた映像情報の圧縮表現である。いくつかの例では、１フレーム当たりのデータのバイト数（例えば、１フレーム当たり２５バイト、５０バイト、７５バイト、１００バイト、または任意の他のバイト数）が番組ソースごとに収集される。２５チャンネル、５０チャンネル、７５チャンネル、１００チャンネル、２００チャンネル、または任意の他の数の番組ソースなど、任意の数の番組ソースを用いて映像を取得することができる。例示のデータ量を用いると、３日間にわたって２４時間に収集される合計データは非常に大きくなる。したがって、実際の基準データ点集合の数を減らすことが、照合サーバ１０４の記憶負荷を低減させる上で有利である。
【００４１】
[0057]メディアクライアント１０６は、照合サーバ１０４の照合エンジン１１２に通信１２２を送信することができる。通信１２２は、照合エンジン１１２が未知のコンテンツを識別することを求める要求を含むことができる。例えば、未知のコンテンツは、１つまたは複数の未知のデータ点を含むことができ、基準データベース１１６は、複数の基準データ点を含むことができる。照合エンジン１１２は、未知のデータ点を基準データベース１１６内の基準データと照合することによって未知のコンテンツを識別することができる。いくつかの例では、未知のコンテンツは、（映像ベースのＡＣＲの場合の）ディスプレイによって提示されている未知の映像データ、（ＭａｐＲｅｄｕｃｅシステム、Ｂｉｇｔａｂｌｅシステム、または他のデータ・ストレージ・システムの場合の）探索クエリ、（顔認識の場合の）未知の顔の画像、（パターン認識の場合の）未知のパターンの画像、または基準データのデータベースと照合することができる任意の他の未知のデータを含むことができる。基準データ点は、映像データソース１１８から受信したデータから導出することができる。例えば、映像データソース１１８から提供された情報からデータ点を抽出することができ、それらのデータ点に索引付けして基準データベース１１６に格納することができる。
【００４２】
[0058]照合エンジン１１２は、候補決定エンジン１１４に、基準データベース１１６から候補データ点を決定するよう求める要求を送信することができる。候補データ点は、未知のデータ点からある決められた距離である基準データ点とすることができる。いくつかの例では、基準データ点と未知のデータ点との距離は、基準データ点の１つまたは複数の画素（例えば、単一の画素、画素群を代表する値（例えば、算術平均値、平均値、中央値、他の値）、または他の適切な数の画素）を、未知のデータ点の１つまたは複数の画素と比較することによって決定することができる。いくつかの例では、基準データ点は、各サンプル位置のところの画素が特定の画素値範囲内にある場合に未知のデータ点からある決められた距離とすることができる。
【００４３】
[0059]ある説明例では、画素の画素値は、（赤緑青（ＲＧＢ）色空間における）赤色値、緑色値、および青色値を含むことができる。このような例では、対応する赤色値、緑色値、および青色値をそれぞれ比較し、各値がある一定の値範囲内（例えば、０〜５値内）にあるようにすることによって、第１の画素（または第１の画素群を表す値）を第２の画素（または第２の画素群を表す値、第２の画素群は第１の画素群と同じ表示バッファ位置内に位置する）と比較することができる。例えば、（１）第１の画素の赤色値が第２の画素の赤色値の０〜２５５の値範囲の５値内（プラスまたはマイナス）にあり、（２）第１の画素の緑色値が第２の画素の緑色値の０〜２５５の値範囲の５値内（プラスまたはマイナス）にあり、（３）第１の画素の青色値が第２の画素の青色値の０〜２５５の値範囲の５値内（プラスまたはマイナス）にある場合に、第１の画素を第２の画素と照合することができる。そのような例では、候補データ点は、未知のデータ点に対する近似一致である基準データ点であり、未知のデータ点について（異なるメディアセグメントに関連した）複数の候補データ点が識別されることになる。候補決定エンジン１１４は、候補データ点を照合エンジン１１２に返すことができる。
【００４４】
[0060]ある候補データ点について、照合エンジン１１２は、その候補データ点と関連付けられた、候補データ点の導出元である識別された映像セグメントに割り当てられたビンにトークンを付加することができる。対応するトークンを、識別された候補データ点に対応するすべてのビンに付加することができる。（視聴されている未知のコンテンツに対応する）さらに多くの未知のデータ点がクライアント機器１０２から照合サーバ１０４によって受信される際に、同様の候補データ点決定プロセスを行うことができ、識別された候補データ点に対応するビンにトークンを付加することができる。ビンのうちの１つだけが視聴されている未知の映像コンテンツのセグメントに対応し、その他のビンは、データ点値が類似しているために（例えば、類似した画素色値を有するために）照合されるが、視聴されている実際のセグメントは対応しない候補データ点に対応する。視聴されている未知の映像セグメントに対応する候補映像コンテンツセグメントのビンには、未知の映像セグメントに対応しないセグメントの他のビンよりも多くのトークンが割り当てられていることになる。例えば、より多くの未知のデータ点が受信されると、ビンに対応するより多数の基準データ点が候補データ点として識別され、より多くのトークンがビンに付加されることになる。ビンに特定の数のトークンが含められると、すなわち、ビンが所定の閾値に達すると、照合エンジン１１２は、ビンと関連付けられた映像セグメントはクライアント機器１０２に現在表示されていると判定することができる。映像セグメントは、映像番組全体または映像番組の一部を含むことができる。例えば、映像セグメントは、映像番組、映像番組の場面、映像番組の１つもしくは複数のフレーム、または映像番組の任意の他の部分とすることができる。
【００４５】
[0061]図２に、未知のデータを識別するための照合システム２００の構成要素を示す。例えば、照合エンジン２１２は、既知のコンテンツ（例えば、既知のメディアセグメント、探索対象としてデータベースに格納された情報、既知の顔やパターンなど）のデータベースを用いて未知のコンテンツ（例えば、未知のメディアセグメント、探索クエリ、顔の画像やパターンなど）を識別するための照合プロセスを行うことができる。例えば、照合エンジン２１２は、基準データベース内の基準データ点２０４のうちの基準データ点と照合されるべき未知のデータコンテンツ２０２（「キュー」と呼ぶことができる）を受け取る。未知のデータコンテンツ２０２は、候補決定エンジン２１４が受け取ることもでき、照合エンジン２１２から候補決定エンジン２１４に送ることもできる。候補決定エンジン２１４は、探索プロセスを実行して、基準データベース内の基準データ点２０４を探索することによって候補データ点２０６を識別することができる。一例では、探索プロセスは、（未知のデータコンテンツ２０２の未知の値からある一定の距離である）近傍値の集合を生成する最近傍探索プロセスを含むことができる。最近傍探索プロセスについて以下でさらに詳細に論じる。候補データ点２０６は、照合プロセスを実行して照合結果２０８を生成するために照合エンジン２１２に入力される。アプリケーションに応じて、照合結果２０８には、ディスプレイによって提示されている映像データ、探索結果、顔認識を用いて判定された顔、パターン認識を用いて判定されたパターン、または他の任意の結果を含むことができる。
【００４６】
[0062]未知のデータ点（例えば、未知のデータコンテンツ２０２）の候補データ点２０６を決定する際に、候補決定エンジン２１４は、未知のデータ点と基準データベース内の基準データ点２０４との距離を決定する。未知のデータ点からある一定の距離である基準データ点は、候補データ点２０６として識別される。いくつかの例では、基準データ点と未知のデータ点との距離を、図１に関連して上述したように、基準データ点の１つまたは複数の画素を未知のデータ点の１つまたは複数の画素と比較することによって決定することができる。いくつかの例では、基準データ点は、各サンプル位置のところの画素が特定の値範囲内にある場合に未知のデータ点からある一定の距離とすることができる。上述したように、候補データ点は、未知のデータ点に対する近似一致である基準データ点であり、近似一致であるため、未知のデータ点について（異なるメディアセグメントに関連した）複数の候補データ点が識別される。候補決定エンジン１１４は、候補データ点を照合エンジン１１２に返すことができる。
【００４７】
[0063]図３に、復号器のメモリバッファ３０２を含む映像インジェスト・キャプチャ・システム４００の一例を示す。復号器は、照合サーバ１０４またはメディアクライアント１０６の一部とすることができる。復号器は、物理的なテレビ表示パネルまたはテレビ表示装置と共に動作せず、またはこれを必要としない場合もある。復号器は、デジタル映像番組を復号し、必要に応じて解読して、テレビ番組の非圧縮ビットマップ表現にすることができる。基準映像データの基準データベース（例えば、基準データベース３１６）を構築するために、照合サーバ１０４は、映像フレームバッファから読み出される映像画素の１つまたは複数の配列を取得することができる。映像画素の配列を映像パッチと呼ぶ。映像パッチは、任意の形状またはパターンとすることができるが、この具体例では、水平方向に１０画素×垂直方向に１０画素を含む、１０×１０画素配列として説明する。また、この例では、映像フレームバッファの境界内に均等に分布している、映像フレームバッファ内から抽出された２５個の画素パッチ位置があるものと仮定する。
【００４８】
[0064]図３には画素パッチ割り振りの例（例えば、画素パッチ３０４）が示されている。上述のように、画素パッチは１０×１０配列などの画素の配列を含むことができる。例えば、画素パッチ３０４は１０×１０の画素配列を含む。画素は、赤色値、緑色値、青色値などの色値を含むことができる。例えば、赤緑青（ＲＧＢ）色値を有する画素３０６が示されている。画素の色値は、色ごとに８ビットの２進値で表すことができる。画素の色を表すのに使用できる他の適切な色値には、輝度および彩度（Ｙ、Ｃｂ、Ｃｒ、ＹＵＶとも呼ばれる）の値や任意の他の適切な色値が含まれる。
【００４９】
[0065]各画素パッチの算術平均値（または場合によっては平均値）が取られ、結果として得られたデータレコードが作成され、タイムコード（またはタイムスタンプ）でタグ付けされる。例えば、１０×１０画素パッチ配列ごとに算術平均値が求められ、この場合、２５個の表示バッファ位置当たり２４ビットのデータが１フレーム当たり合計６００ビットの画素情報のために生成される。一例では、画素パッチ３０４の算術平均値が計算され、これが画素パッチ算術平均値３０８によって示されている。ある説明例では、タイムコードは、１９７０年１月１日の午前零時からの総経過時間（何分１秒単位）を表す「エポックタイム」を含むことができる。例えば、画素パッチ算術平均値３０８はタイムコード３１２と共にアセンブルされる。エポックタイムは、例えばＵｎｉｘベースのシステムを含むコンピューティングシステムで受け入れられている規約である。データレコードにはメタデータと呼ばれる映像番組に関する情報が添付される。メタデータは、番組識別子、番組時間、番組長、任意の他の情報など、番組に関する任意の情報を含むことができる。画素パッチの算術平均値、タイムコード、およびメタデータを含むデータレコードは、「データ点」（「キュー」とも呼ばれる）を形成する。データ点３１０は、基準映像データ点の一例である。
【００５０】
[0066]未知の映像セグメントを識別するプロセスは、基準データベースを作成するのと同様のステップから始まる。例えば、図４に、復号器のメモリバッファ４０２を含む映像インジェスト・キャプチャ・システム４００を示す。映像インジェスト・キャプチャ・システム４００は、（例えば、スマートＴＶ、モバイル機器、他のテレビ視聴機器など、インターネット接続テレビモニタ上で）ディスプレイによって提示されたデータを処理するクライアント機器１０２の一部とすることができる。映像インジェスト・キャプチャ・システム４００は、システム３００によって基準映像データ点３１０を作成するために用いられるプロセスと同様の未知の映像データ点４１０を生成するプロセスを利用することができる。一例では、メディアクライアント１０６は、照合サーバ１０４が未知の映像データ点４１０と関連付けられた映像セグメントを識別するように、未知の映像データ点４１０を照合エンジン１１２に送信することができる。
【００５１】
[0067]図４に示すように、映像パッチ４０４は、１０×１０の画素配列を含むことができる。映像パッチ４０４は、ディスプレイによって提示されている映像フレームから抽出することができる。映像フレームから複数のこのような画素パッチを抽出することができる。ある説明例では、映像フレームから２５個のこのような画素パッチが抽出された場合、その結果は７５次元空間内の位置を表す点になる。配列の色値（例えば、ＲＧＢ色値、Ｙ、Ｃｒ、Ｃｂ色値など）ごとに、算術平均値（または平均値）を計算することができる。算術平均画素値からデータレコード（例えば、未知の映像データ点４１０）が形成され、データに現在時刻が添付される。上述の技術を用いて基準データベース１１６からのデータと照合されるように、照合サーバ１０４に１つまたは複数の未知の映像データ点を送信することができる。
【００５２】
[0068]ＩＩＩ．共通映像セグメント
図５に、インタラクティブ・テレビ（ＴＶ）・システム５０１のための映像照合システム５００の一例を示す。インタラクティブ・テレビ・システム５０１はメディア表示装置の一例として示すものである。この例では、インタラクティブ・テレビ・システム５０１は、ＴＶクライアント５０３と、コンテキスト・ターゲティング・クライアント５０２とを含む。ＴＶクライアント５０３はテレビ番組５０５を受信する。テレビ番組５０５は音声・映像コンテンツを含み、音声・映像コンテンツは、音声データ、映像データ、および／または同期された音声データを伴った映像データを含む。場合によっては、テレビ番組５０５はメタデータを含む。ＴＶクライアント５０３は、映像コンテンツを画面上に表示すること、および／またはスピーカを介して音声コンテンツを再生することを含めて、音声・映像コンテンツを表示するように構成される。テレビ番組５０５は、テレビ放送プロバイダ、衛星テレビプロバイダ、インターネット・メディア・プロバイダ、音声・映像再生機器（例えば、ＤＶＤプレーヤ、ＤＶＲプレーヤ、ＶＣＲプレーヤなど）といったものを含む様々なソースから受信することができる。
【００５３】
[0069]様々な実施態様において、映像照合システムは照合サーバ５０９を含む。照合サーバ５０９は、インタラクティブ・テレビ・システム５０１によって表示または再生されているメディアを認識する。映像照合サービスを提供するために、照合サーバ５０９は、インジェストサーバ５２０から既知のメディア・キュー・データ５１７を受信する。インジェストサーバ５２０は、ビデオオンデマンド（ＶｏＤ）・コンテンツ・フィード５１５ａ、ローカル・チャンネル・フィード５１５ｂ、および全国チャンネルフィード５１５ｃなど、様々な既知のソースからデータを取得する。これら既知のソースの各々は、メディアデータ（例えば、映像および／または音声）、ならびに番組ガイドやメタデータなどのメディアデータを識別する情報を提供する。様々な実施態様において、インジェストサーバ５２０は、様々なソースから受信したメディアデータから既知のメディア・キュー・データ５１７を生成する。インジェストサーバ５２０は、既知のメディア・キュー・データ５１７を、照合サーバ５０９を含む様々な受け手に提供する。
【００５４】
[0070]様々な実施態様において、インジェストサーバ５２０は、番組識別および時間データ５１４も提供する。様々な実施態様において、番組識別および時間データ５１４は既知のメディア・キュー・データ５１７と同期される。これは、番組識別および時間データ５１４が既知のメディアキュー５１７を識別し、かつ／または既知のメディアキューと関連付けられたメディアが表示されることが予期される時間を提供することを意味する。番組識別および時間データ５１４をメタデータとも呼ぶ。
【００５５】
[0071]様々な実施態様において、既知のメディア・キュー・データ５１７は、映像および／または音声データを識別するためのキューまたはキーを提供する。既知のメディア・キュー・データ５１７は既知の音声・映像メディアから取得されており、そのため、既知のメディアキュー５１７は、既知の音声・映像メディアの名前および／または何らかの他の識別情報と関連付けることができる。以下でさらに詳細に説明するように、既知のメディアキュー５１７は、インタラクティブ・テレビ・システム５０１によって表示または再生されているメディアから取得された類似したキューに対して照合することができる。照合サーバ５０９は、既知のメディア・キュー・データ５１７および番組識別データ５１４をデータベース５１２に格納することができる。
【００５６】
[0072]様々な実施態様において、照合サーバ５０９はチャンネル認識システム５１０を含む。チャンネル認識システム５１０は、インタラクティブ・テレビ・システム５０１から未知のメディアキュー５０７ａを受信する。例えば、ＴＶクライアント５０３は、任意の所与の時間に表示または再生されている音声・映像データからサンプルを取得し、サンプルからキューを生成する。ＴＶクライアント５０３はこれらのキューを、未知のメディアキュー５０７ａとして、照合サーバ５０９内のチャンネル認識システム５１０に提供する。次いで、チャンネル認識システム５１０は、未知のメディアキュー５０７ａを既知のメディアキュー５１７と照合して、インタラクティブ・テレビ・システム５０１によって表示または再生されているメディアを識別する。
【００５７】
[0073]様々な実施態様において、チャンネル認識システム５１０は、未知のメディアキュー５０７ａの番組識別を決定する。番組識別は、名前または記述、またはインタラクティブ・テレビ・システム５０１によって表示されているメディアコンテンツを識別する何らかの他の情報を含む。チャンネル認識システム５１０は時間も提供し、時間は、メディアがインタラクティブ・テレビ・システム５０１によって再生された時間を指示する。
【００５８】
[0074]様々な実施態様において、チャンネル認識システム５１０は、番組識別および時間データ５１３をコンテキスト・ターゲティング・マネージャ５１１に提供する。コンテキスト・ターゲティング・マネージャ５１１は、番組識別および時間データ５１３を用いて、例えばアプリケーションや広告を含むコンテキスト的関連コンテンツ５０７ｂを決定する。コンテキスト・ターゲティング・マネージャ５１１は、コンテキスト的関連コンテンツ５０７ｂをインタラクティブ・テレビ・システム５０１に提供する。例えば、インタラクティブ・テレビ・システム５０１は、コンテキスト的関連コンテンツ５０７ｂを管理するためのコンテキスト・ターゲティング・エンジン５０２を含む。いくつかの実施態様では、コンテキスト・ターゲティング・マネージャ５１１はまた、コンテキスト・ターゲティング・システム５０２にイベントトリガ５０７ｃを提供する。イベントトリガ５０７ｃは、コンテキスト・ターゲティング・エンジン５０２に、コンテキスト的関連コンテンツ５０７ｂを再生または表示するよう命令する。例えば、イベントトリガ５０７ｃはコンテキスト・ターゲティング・エンジン５０２にコンテキスト的関連情報オーバレイを表示するよう命令し、情報オーバレイは、情報オーバレイが関連する映像コンテンツの表示と適合するように調整される。代替として、または加えて、イベントトリガ５０７ｃは、ターゲット広告などの置換メディアを表示させることもできる。いくつかの実施態様では、コンテキスト・ターゲティング・エンジン５０２はコンテキスト・ターゲティング・マネージャ５１１に、イベントトリガ５０７ｃによって提供された命令が実行されたことを指示するイベント確認５０７ｄを提供する。
【００５９】
[0075]様々な実施態様において、コンテキスト・ターゲティング・クライアント５０２は、代替として、または加えて、照合サーバ５０９に視聴率情報を提供することもできる。例えば、コンテキスト・ターゲティング・クライアント５０２は、イベント確認５０７ｄに加えて、またはイベント確認５０７ｄの代わりに視聴率情報を提供する。この実施態様では、視聴率情報は、例えば、特定のメディアセグメントが再生された頻度、メディアセグメントが再生された時刻もしくは曜日、メディアセグメントの前および／もしくは後に再生された内容、ならびに／またはメディアセグメントが再生されたチャンネルを含む。場合によっては、視聴率情報は、人口統計情報など、視聴者に関する情報も含む。
【００６０】
[0076]様々な実施態様において、メディア表示装置は、映像照合システムと共に構成され、または映像照合システムに接続される。映像照合システムは、任意の所与の瞬間に、メディア表示装置によって表示または再生されているメディアを識別することができる。上述したように、映像照合システムは、装置によって再生されているメディアの映像サンプルおよび／または音声サンプルを取得し、サンプルから識別子または「キュー」を生成し、次いで、メディア表示装置上に表示または再生されているメディアを識別することによってキューをデータベースと照合し、映像照合システムは、アプリケーション、広告、および／または代替のメディアコンテンツを含むコンテキスト的関連コンテンツを提供することができる。
【００６１】
[0077]メディア表示装置から利用可能な複数のコンテンツストリームまたはチャンネルが、例えば「ニュース速報」など、同じコンテンツを再生するときには、コンテンツを一意に識別できない場合がある。例えば、追加情報がないと、メディア表示装置によってどのチャンネルが表示されているのかが明確にならない場合がある。
【００６２】
[0078]図６に、複数のコンテンツストリームが同じメディアセグメントを同時に搬送している一例を示す。図６には、映像照合システムが同じメディアセグメントを搬送している複数のチャンネルに対応するための方法の例がさらに示されている。図示の例では、複数のコンテンツストリームの例として３つのチャンネルが示されている。３つのチャンネルは、例えば、３つのテレビ放送チャンネルとすることができる。
【００６３】
[0079]この例では、チャンネル２  ６０１は、通常通りスケジュールされた番組の２つのセグメント６０２、６０４を再生する。メディア表示装置がチャンネル２  ６０１を再生していると仮定すると、２つの時間間隔ｔ１  ６０３およびｔ２  ６０５の間に、メディア表示装置は映像照合システムにセグメント１  ６０２およびセグメント２  ６０４からのサンプルを送信する。時間間隔ｔ１  ６０３の終わりまでに、映像照合システムはセグメント１  ６０２を識別することができ、時間間隔ｔ２  ６０５の終わりまでに、映像照合システムはセグメント２  ６０４を識別することができる。
【００６４】
[0080]第３のセグメント６０６の間、チャンネル２  ６０１は、共通メディアセグメント、ここではライブ・プール・フィード・セグメント６０８によって中断される。この例のライブ・プール・フィード・セグメント６０８は、例えば全国放送局によって提供されている共通メディアセグメントである。ライブ・プール・フィード・セグメント６０８は、その各シンジケート局に供与される。ライブ・プール・フィード・セグメントの一例が、「ニュース速報」、すなわち全国ニュース記事である。ライブ・プール・フィード・セグメントの他の例には、スポーツイベント、シンジケート番組、およびコマーシャルが含まれる。時間間隔ｔ３  ６０７の間に、メディア表示装置は映像照合システムにライブ・プール・フィード・セグメント６０８からのサンプルを送信する。
【００６５】
[0081]映像照合システムは、時間間隔ｔ３  ６０７の間に提供されたサンプルがライブ・プール・フィード・セグメント６０８のものであったと判定する。様々な実施態様において、映像照合システムはこの判定を、複数のチャンネルと関連付けられているライブ・プール・フィード・セグメントの照合キューを見つけたことに基づいて行うことができる。いくつかの実施態様では、チャンネル２  ６０１がライブ・プール・フィード・セグメント６０８を表示していると判定すると、映像照合システムは、ライブ・プール・セグメント６０８を、チャンネル２  ６０１でごく最近検出された番組の続きとして扱う。これらの実施態様では、映像照合システムはこの判定を、ライブ・プール・フィード・セグメント６０８が開始したまさにその瞬間に視聴者がチャンネルを変更した確率が低いことに基づいて行う。いくつかの実施態様では、映像照合システムは、予期しないライブ・プール・フィード・セグメント６０８がスケジュールされたインタラクティブコンテンツまたはターゲットコンテンツに関連している可能性は低いとさらに判定する。したがって、これらの実施態様では、スケジュールされたインタラクティブコンテンツまたはターゲットコンテンツは非表示または無効とされる。ターゲットコンテンツは、スケジュールされていないライブ・プール・フィード・セグメント６０８に関連しておらず、したがって、例えば、インタラクティブオーバレイを表示することは視聴者にとって有用ではない。
【００６６】
[0082]ライブ・プール・フィード・セグメント６０８の終わりに、チャンネル２  ６０１はセグメント４  ６０９を表示する。場合によっては、セグメント４  ６０９はスケジュールされた番組であり、これは、ライブ・プール・フィード・セグメント６０８がセグメント３  ６０６を中断しており、またはセグメント３  ６０６の終わりに流されたものであり、セグメント３  ６０６の後に続くようにスケジュールされたものの代わりに再生されていることを意味する。例えば、セグメント４  ６０９はセグメント３  ６０６の番組の続きであり、ライブ・プール・セグメント６０８が再生しなかった場合に番組が再生していたはずの番組の時点でピックアップする。別の例として、セグメント４  ６０９は、セグメント３  ６０６の後に開始するようにスケジュールされた新しい番組である。セグメント４  ６０９は、新しい番組の始めから開始し、または始めの若干の部分がライブ・プール・フィード・セグメントで置き換えられる。
【００６７】
[0083]場合によっては、セグメント３  ６０６とセグメント４  ６０９との間に表示されるはずであった番組を置き換えるのではなく、セグメント３  ６０６の番組は代わりに一時停止される。ライブ・プール・フィード・セグメント６０８が終了すると、セグメント３  ６０６の番組はセグメント４  ６０９で再開し、番組がセグメント３で停止したところからピックアップする。あるいは、セグメント３  ６０６の番組はセグメント４  ６０９で再開してもよい。いくつかの実施態様では、ライブ・プール・フィード・セグメント６０８の終わりに、視聴者は、セグメント３  ６０６の番組を再開するか、それとも番組を始めから再生し直すかのオプションを与えられる。
【００６８】
[0084]図６の別の例は、チャンネル７  ６１０によって提供されている。チャンネル７  ６１０では、セグメント１  ６１１およびセグメント２  ６１２が通常通りスケジュールされている。その後、チャンネル７  ６１０は、ライブ・プール・セグメント６１３によって中断される。この例では、メディア表示装置は、ライブ・プール・セグメント６１３が開始した直後に、またはライブ・プール・セグメント６１３が放送している間にチャンネル７  ６１０に同調する。２つのタイマ間隔ｔ１  ６１４およびｔ２  ６１５の間に、メディア表示装置は映像照合システムにライブ・プール・フィード・セグメント６１３からのサンプルを送信する。映像照合システムは、続いて、チャンネル７  ６１０はライブ・プール・フィード・セグメント６１３を再生していると判定する。様々な実施態様において、映像照合システムはこの判定を、例えば、複数のチャンネルと関連付けられているライブ・プール・フィード・セグメント６１３の照合キューを見つけたことに基づいて行うことができる。この例では、映像照合システムは、メディア表示装置が現在どのチャンネルを再生しているか判定することができない可能性もある。いくつかの実施態様では、映像照合システムは、ライブ・プール・フィード・セグメントが放送されている間にコンテキスト的関連コンテンツを提供することを控える。
【００６９】
[0085]ライブ・プール・フィード・セグメント６１３の終わりに、チャンネル７  ６１０は、セグメント３  ６１６でスケジュールされたプログラムに戻る。時間間隔ｔ３  ６１７の間に、メディア表示装置は映像照合システムにセグメント３  ６１６からのサンプルを送信し、この時点で、映像照合システムは、メディア表示装置はチャンネル７  ６１０に同調していると判定することができる。いくつかの実施態様では、映像照合システムは、時間間隔ｔ１  ６１４およびｔ２  ６１５の間に取得されたサンプルをチャンネル７  ６１０と関連付ける。映像照合システムは、視聴者にチャンネル７  ６１０に関連するコンテキスト的関連コンテンツをさらに提供する。
【００７０】
[0086]別の例が図６にチャンネル９  ６１８で示されている。この例では、チャンネル９  ６１８は、通常通りスケジュールされたセグメント１  ６１９、セグメント２  ６２０、セグメント３  ６２２、セグメント４  ６２４およびセグメント５  ６２６を表示する。メディア表示装置がチャンネル９  ６１８に同調していると仮定すると、時間間隔ｔ１  ６２１、ｔ２  ６２３、およびｔ３  ６２５の間に、メディア表示装置は映像照合システムに、セグメント６２０、セグメント６２２、セグメント６２４からのサンプルを送信する。いくつかの実施態様では、映像照合システムは、チャンネル９  ６１８はライブ・プール・フィード・セグメントを含まなかったと判定する。映像照合システムは、例えば、コマーシャルを視聴者にとって特に関心のあるコマーシャルで置き換えるなど、コンテキスト的関連コンテンツをさらに提供し、置換コマーシャルは、メディア表示装置から前に収集された情報に基づくものとすることができる。
【００７１】
[0087]状況によっては、共通プール・フィード・セグメントが開始した後にチャンネルが共通プールフィードの表示を開始することがある。図７に、テレビチャンネルとして例示された複数のメディアストリームが同じメディアコンテンツを同時に表示する別の例を示す。この例では、チャンネル２  ７０１は、ライブ・プール・フィード・セグメント７０８に切り替わる前に通常通りスケジュールされたセグメント１  ７０２、セグメント２  ７０４、およびセグメント３  ７０６を表示する。ライブ・プール・フィード・セグメント７０８が開始する頃にメディア表示装置がチャンネル２  ７０１に同調された場合、メディア表示装置は、映像照合システムに、時間間隔ｔ１  ７０３、時間間隔ｔ２  ７０５、時間間隔ｔ３  ７０７、および後続のセグメント４  ７０９の時間間隔ｔ４  ７１７の間にサンプルを送信する。上述したように、映像照合システムは、セグメント４  ７０９からのサンプルを受信すると、メディア表示装置はチャンネル２  ７０１に同調していると判定する。
【００７２】
[0088]この例のチャンネル７  ７１０は、通常通りスケジュールされたセグメント１  ７１１およびセグメント２  ７１２を表示する。ライブ・プール・フィード・セグメント７１３は時点７２１から開始するが、チャンネル７  ７１０はライブ・プール・フィード・セグメント７１３への切り替えを遅延させる。この遅延の理由は、例えば、セグメント２  ７１２が時間を超過して流れたため、チャンネル７  ７１０の番組編成担当者がセグメント２  ７１２を完了させることに決定したため、かつ／またはセグメント２  ７１２がライブ・プール・フィード・セグメント７１３への導入部を含んでいたためである。メディア表示装置が時間７２１頃にチャンネル７  ７１０に同調していたと仮定すると、メディア表示装置は、時間間隔ｔ１  ７１４および時間間隔ｔ２  ７１５の間に、映像照合システムにサンプルを送信する。映像照合システムは、チャンネル７  ７１０はライブ・プール・フィード・セグメント７１３を再生していると判定するが、メディア表示装置がどのチャンネルを再生しているか判定することができない可能性がある。
【００７３】
[0089]別の例示的シナリオでは、メディア表示装置は、最初にチャンネル７  ７１０に同調しており、次いで、時間７２１にチャンネル２  ７０１に切り替わる。時間７２１で、チャンネル２  ７０１はライブ・プール・フィード・セグメント７０８をすでに再生している。ライブ・プール・フィード・セグメント７０８は複数のチャンネルと関連付けられているため、時間間隔ｔ２  ７０５および時間間隔ｔ３  ７０７の間に、映像照合システムは、メディア表示装置がどのチャンネルに変更したか判定することができない可能性がある。セグメント４  ７０９が表示されると、映像照合装置は、メディア表示装置がチャンネル２  ７０１に同調していると判定することができる。この判定を行うと、映像照合システムは、ｔ２  ７０５およびｔ３  ７０７からのサンプルをチャンネル２  ７０１と関連付ける。
【００７４】
[0090]図８に、複数のメディア・コンテンツ・ストリームが同じ共通メディアセグメント８１０をほぼ同時に搬送している一例を示す。この例では、２つのメディア・コンテンツ・ストリーム８０４ａ、８０４ｂが２台の異なるメディア表示装置８０６ａ、８０６ｂに配信されている。他の例では、各々が同じメディアコンテンツを搬送する多くの異なるメディア・コンテンツ・ストリームが、同時に多くの異なるメディア表示装置に配信されている。この例では、２台のメディア表示装置８０６ａ、８０６ｂは、例えば同じ世帯内にあり、同じ家族の２人の異なる人物８０８ａ、８０８ｂによって使用されている。例えば、１人の家族８０８ａは居間にあるＴＶ８０６ａでテレビ番組を見ており、別の家族８０８ｂは勉強部屋にあるラップトップでテレビ番組を見ている。あるいは、２台のメディア表示装置８０６ａ、８０６ｂおよびそれらを使用している人物８０８ａ、８０８ｂは、無関係であり、異なる場所にいてもよい。
【００７５】
[0091]２人の人物８０８ａ、８０８ｂは、ほぼ同時に、表示装置８０６ａ、８０６ｂを同じメディアセグメント８１０に同調させる。例えば、２人の人物８０８ａ、８０８ｂは、同じ映画を見ることを個別に決定する。その結果、２台のメディア表示装置８０６ａ、８０６ｂは、所与の瞬間に全く同じメディアセグメント８１０を表示していることになる。あるいは、所与の瞬間に、各装置８０６ａ、８０６ｂによって表示されているコンテンツの間に数秒または数分の時間差が生じる場合もある。例えば、映画ではＴＶ８０６ａはラップトップ８０６ｂの数秒前にある。
【００７６】
[0092]この例では、メディア・コンテンツ・ストリーム８０４ａ、８０４ｂは、インターネット８５０上で配信されているデジタル音声・映像ストリームおよび／または音声ストリームである。例えば、メディア・コンテンツ・ストリームは、ウェブサイトによって提供されている映画、テレビ番組、音楽、テキスト、および／または画像を含む。メディア・コンテンツ・ストリーム８０４ａ、８０４ｂは、各々、異なるコンテンツプロバイダ、プロバイダＡ８０２ａおよびプロバイダＢ８０２ｂによって提供される。プロバイダＡ８０２ａおよびプロバイダＢ８０２ｂは、例えば、インターネット映画、音楽および／またはテレビのプロバイダである。あるいは、場合によっては、プロバイダＡ８０２ａとプロバイダＢ８０２ｂとは同じコンテンツプロバイダであってもよい。
【００７７】
[0093]図８の例では、メディア表示装置８０６ａ、８０６ｂはどちらも、映像照合システムと共に構成されたコンピューティング機器（図示せず）に接続されている。映像照合システムは、再生中に、再生中のメディアコンテンツから取得したキューを用いて、装置８０６ａ、装置８０６ｂの各々によって再生されているメディアコンテンツを識別しようと試みる。映像照合システムは、これらのキューをデータベースと照合し、データベースから、再生されているメディアコンテンツのタイトル、メディアコンテンツの作成者、製作者、および／または配信者の識別情報、メディアコンテンツを視聴している人物の識別情報、および／または視聴者の機器の識別情報といった情報を判定する。例えば、この例では、映像照合システムは、メディア・コンテンツ・ストリーム８０４ａを調べることによってプロバイダＡ８０２ａの識別情報を取得することができる。別の例として、映像照合システムは、ＴＶ８０６ａを同じ人物８０８ａが所有するスマートフォンと区別することができる。加えて、映像照合システムは、人物の８０８ａのＴＶ８０６ａとスマートフォンが異なる場所に位置していると判定することもできる。映像照合システムは、この情報をさらに用いて、メディア表示装置にインタラクティブ情報および／または広告などのコンテキスト的関連コンテンツを提供し、メディア表示装置はコンテキスト的関連コンテンツを視聴者に表示する。
【００７８】
[0094]上述のように、２つの例示的なメディア・コンテンツ・ストリーム８０４ａ、８０４ｂがほぼ同じ時間に同じメディアセグメント８１０を表示しているとき、映像照合システムはある情報を決定できない場合がある。例えば、映像照合システムは、共通メディアセグメント８１０を再生しているＴＶ８０６ａおよびラップトップ８０６ｂを識別することはできるが、映像照合システムが各機器に固有のコンテキスト的関連コンテンツを決定するにはこの情報だけでは不十分である。例えば、映像照合システムに、２台の機器を見ている個々の人物８０８ａ、８０８ｂの特徴や識別情報などの情報が提供された場合には、映像照合システムは、第１の人物８０８ａにコンテキスト的関連コンテンツを調整し、第２の人物８０８ｂには異なるコンテキスト的関連コンテンツを提供することができる。
【００７９】
[0095]コンテキスト的関連コンテンツを決定するために、映像照合システムは、図６および図７に関連して上述した方法を用いることができる。様々な実施態様において、映像照合システムは、図８のメディア・コンテンツ・ストリーム８０４ａ、８０４ｂに含まれる他のメディアコンテンツの識別情報を決定する。例えば、ある場合には、ＴＶ８０６ａを視聴している人物８０８ａは、共通メディアセグメント８１０に同調する前にスポーツニュースを見ていたとする。映像照合システムは、この前のメディアコンテンツの識別情報を用いてメディア・コンテンツ・ストリーム８０４ａを識別する。例えば、映像照合システムは、メディア・コンテンツ・ストリーム８０４ａを、ＴＶ８０６ａおよび／またはＴＶ８０６ａを見ている人物８０８ａと関連付けられているものとして識別することができる。映像照合システムはさらに、ＴＶ８０６ａにコンテキスト的関連コンテンツを提供することができる。例えば、映像照合システムは、人物８０８ａのお気に入りのチームのニュースおよび／またはスポーツイベントもしくはスポーツ用具の広告を提供する。
【００８０】
[0096]別の例として、ラップトップ８０６ｂを見ている人物８０８ｂは、共通メディアセグメント８１０に同調する前にはラップトップ８０６ｂを用いてメディアコンテンツを見ていなかったとする。そうではなく、この人物８０８ｂは、共通メディアセグメント８１０の途中またはその後に、他のメディアコンテンツを視聴する。例えば、共通メディアセグメント８１０のコマーシャルによる中断の間に、人物８０８ｂは、ラップトップ８０６ｂを用いて学用品を購入する。映像照合システムは、共通メディアセグメント８１０の途中または後に表示されるこの他のメディアコンテンツを用いてメディア・コンテンツ・ストリーム８０４ｂを識別する。例えば、映像照合システムはメディア・コンテンツ・ストリームを、ラップトップ８０６ｂおよび／またはラップトップ８０６ｂを使用している人物８０８ｂと関連付けられたものとして識別する。映像照合システムはさらに、ラップトップ８０６ｂにコンテキスト的関連コンテンツを提供する。例えば、映像照合システムは、学用品に関連した広告、買い物先の提案、および／または特売が見つかる場所の提案を提供する。
【００８１】
[0097]様々な実施態様において、映像照合システムは、メディア・コンテンツ・ストリームが共通メディアセグメントを再生しているときに他の方法を用いてメディア・コンテンツ・ストリームを識別する。場合によっては、メディア・コンテンツ・ストリームのプロバイダは、共通メディアセグメント上に重ね合わされたグラフィック要素を提供する。図９に、メディア表示装置９００によって再生されている共通メディアセグメントに重ね合わされているグラフィック９０２の一例を示す。様々な実施態様において、グラフィック９０２は、特に複数のコンテンツプロバイダが共通メディアセグメントを再生している場合に、コンテンツプロバイダによってコンテンツプロバイダを識別するのに用いられる。例えば、複数のローカル・テレビ・チャンネルが同じ全国ニュースセグメントを同時に放映しているとする。ローカル放送局は、それ自体を識別するために、ニュースセグメントにグラフィック９０２を付加する。グラフィック９０２は、例えば、ロゴや、番組情報や、他の情報とすることができる。
【００８２】
[0098]図９には、あるコンテンツプロバイダによって使用されるグラフィックのサイズおよび位置の一例が示されている。他の例では、グラフィック９０２は、画面の下部もしくは上部を横切るバナーやティッカ、画面の左もしくは右の欄、または画面中央に重ね合わせて表示される。
【００８３】
[0099]様々な実施態様において、グラフィックオーバレイを検出するための方法では、映像表示を調べ、映像画像エッジを見つける。映像画像エッジは、メディア表示装置の画面のセクション間の高コントラスト差を探すことによって検出することができる。この方法は、検出されたエッジが静止したままであるかどうか監視することをさらに含む。検出されたエッジが短期間よりも長く特定の位置に留まる場合、映像照合システムは、画面上のグラフィックが見つかったと判定する。例えば、映像照合システムは、画面上のバナーの存在を指示する、画面の下部領域を横切る高コントラスト差を探す。
【００８４】
[0100]様々な実施態様において、上述の映像照合システムは、グラフィックオーバレイを検出するための方法を含むことができる。例えば、上述したように、メディア表示装置の画面について画素パッチを定義することができる。「画素パッチ」は、メディア表示装置の画面からサンプリングされる画素ブロックとして定義される。画素パッチはある数の画素を含み、各画素は、例えば、ＲＧＢ色値（またはＹＵＶや何らかの他の形式で表された色値）を有することができる。画素パッチは、グラフィックオーバレイ検出のために、例えば、幅３２画素×高さ３２画素や、３２画素の倍数、例えば、幅６４画素×高さ６４画素などとされる。これらの例示的サイズでは、離散コサイン変換（ＤＣＴ）を利用する。離散コサイン変換関数は映像照合システムによって行うことができる。グラフィックオーバレイのエッジは、画素パッチごとの離散コサイン変換の右下象限内の係数を調べることによって検出することができる
【００８５】
[0101]様々な実施態様において、検出プロセスは、所定の長さの時間にわたって、離散コサイン変換からの高周波情報が不変であるかどうか検出することを含むこともできる。高周波情報が変化しない場合、グラフィックオーバレイが存在する。これらの実施態様では、スクロールバナーなど、いくつかの画面上グラフィックを識別することができる。
【００８６】
[0102]様々な実施態様において、他の画面上グラフィック検出方法は、ＳｏｂｅｌやＳｈａｒｒといったアルゴリズムを使用することもでき、知覚ハッシュファミリの画像解析からのアルゴリズムを使用することもできる。離散コサイン変換の場合と同様に、これらのアルゴリズムは、映像信号内のグラフィック要素のエッジおよびコーナの検出にも使用することができる。場合によっては、エッジを探索するために、３画素×３画素など、奇数の画素を有する画素パッチが、関心対象の映像領域にわたる畳み込み符号化段階的掃引において使用される。
【００８７】
[0103]様々な実施態様において、画面上グラフィックを検出することは、画素パッチ内の画素情報を８ビットの赤緑青（ＲＧＢ）色値から８ビットのモノクロ値に低減させることから開始する。次に、ガウスぼかしを適用して映像情報内のノイズを低減させる。次に、画素マトリクス（すなわち、結果として得られる画素パッチ）が、関心対象の映像領域上で受け渡しされる。次いで、このマトリクスを用いて、映像画面の垂直軸または水平軸のどちらかに対する画素値の１次微分を計算することができる。計算された差分はそれぞれの画素位置に残される。この差分を調べて、エッジを指示する最大値を求めることができる。
【００８８】
[0104]様々な実施態様において、グラフィックオーバレイを検出するための別の方法は、グラフィックオーバレイに使用できる様々なグラフィックで映像照合システムを訓練することである。次いで、画像照合アルゴリズムを用いて、訓練された、または学習されたグラフィックを画面上の画素と照合することができる。例えば、映像照合システムは、知覚ハッシュ（ｐＨａｓｈ）法を用いて照合を行うことができる。他のフレーム比較方法の例には、ＳＩＦＴ（Ｓｃａｌｅ−ｉｎｖａｒｉａｎｔ  ｆｅａｔｕｒｅ  ｔｒａｎｓｆｏｒｍ（スケール不変特徴変換））およびＳＵＲＦ（Ｓｐｅｅｄｅｄ  Ｕｐ  Ｒｏｂｕｓｔ  Ｆｅａｔｕｒｅｓ（高速化されたロバストな特徴）が含まれる。ｐＨａｓｈを用いる実施態様では、映像フレーム全体を迅速に処理することができる。結果として得られるハッシュ値は基準映像画像と比較される。これらの基準映像画像も、ｐＨａｓｈを用いて処理され、中央サーバから供給されてよい。ｐＨａｓｈを用いる利点の１つは、コントラスト、明るさ、または色変化に対する不感性が比較的高い粗い特徴（例えば、大きな矩形やグラフィックオーバレイによって用いられうる他の形状）を確実に照合することができることである。ｐＨａｓｈのもう１つの利点は、詳細な個々の映像フレームを照合することもできることである。
【００８９】
[0105]様々な実施態様において、映像照合システムはさらに、異なる可能なグラフィックオーバレイ比較候補のライブラリを維持する。さらに、映像照合システムは、時間単位内に実行される画像探索全体の総数を増加させることなく、ライブラリを使用することができる。具体的には、いくつかの実施態様では、映像照合システムは、成功した検出を追跡する。頻繁に一致に成功するグラフィックオーバレイ比較候補は、将来において一致する可能性が高く、まれにしか一致せず、または一致に成功したことのない候補は将来において一致する可能性が低い。
【００９０】
[0106]様々な実施態様において、グラフィックオーバレイ検出は、自動コンテンツ認識のプロセスとインタリーブさせることができる。
【００９１】
[0107]図１０に、複数のメディア・コンテンツ・ストリームが同じスケジュールされていないメディアセグメントを含む場合に実施されるプロセス１０００の一例を示す。プロセス１０００はコンピューティング機器によって実施され、コンピューティング機器は上述したような映像照合システムと共に構成されている。
【００９２】
[0108]ステップ１００２で、コンピューティング機器は、複数のメディア・コンテンツ・ストリームを受信する。コンピューティング機器は、特定の時間に特定のメディア表示装置（例えば、テレビ、タブレットコンピュータ、ラップトップなど）によって再生されているメディアコンテンツを識別するように構成される。複数のメディア・コンテンツ・ストリームのうちの少なくとも２つは同じスケジュールされていないセグメントを同時に含む。例えば、２つのメディア・コンテンツ・ストリームはどちらも、「ニュース速報」セグメント、すなわち重要イベントの全国放送を含む。別の例として、２つのメディア・コンテンツ・ストリームはどちらも同じストリーミング映画を含み、映画は異なるメディア表示装置を用いて異なる人物によって要求されたものである。この例では、メディアセグメントは、メディア表示装置と関連付けられた番組のスケジュールがないので、「スケジュールされていない」。
【００９３】
[0109]ステップ１００４で、コンピューティング機器は、特定のメディア表示装置は現時点においてメディア・コンテンツ・ストリーム内のスケジュールされていないメディアセグメントを再生していると判定する。コンピューティング機器はこの判定を、複数のメディア・コンテンツ・ストリームの各々において現時点で利用可能なメディアコンテンツを調べることによって行う。例えば、複数のメディア・コンテンツ・ストリームは２つ以上のローカル・テレビ・チャンネルを含み、これらのローカル・テレビ・チャンネルのうちの２つ以上がどれも、ニュース速報フィードを受信している。
【００９４】
[0110]ステップ１００６で、コンピューティング機器は、現時点において特定のメディア表示装置によって再生されているメディア・コンテンツ・ストリームに含まれるメディアコンテンツから識別情報を決定する。例えば、コンピューティング機器は、スケジュールされていないメディアセグメントの前に特定のメディア表示装置によって再生されたメディアコンテンツによって提供された識別情報を用いる。代替として、または加えて、コンピューティング機器は、スケジュールされていないメディアセグメントの後に再生されるメディアコンテンツによって提供される識別情報を用いてもよい。識別情報はメディア・コンテンツ・ストリームを識別する。例えば、識別情報は、チャンネル、サービスプロバイダ、特定のメディア表示装置、および／または特定のメディア表示装置を使用する人物を識別する。
【００９５】
[0111]ステップ１００８で、コンピューティング機器は、コンテキスト的関連コンテンツを決定する。コンテキスト的関連コンテンツには、例えば、特に、インタラクティブ情報、広告、および／または追加コンテンツの提案が含まれる。コンテキスト的関連コンテンツは、スケジュールされていないメディアセグメントが特定のメディア表示装置によって再生されている間は無効とされる。
【００９６】
[0112]ステップ１０１０で、コンピューティング機器は、スケジュールされていないメディアセグメントが再生された後に、メディア・コンテンツ・ストリームおよびコンテキスト的関連コンテンツを表示する。例えば、コンピューティング機器は、スケジュールされていないメディアセグメントに続くメディアコンテンツ上にコンテキスト的関連情報をオーバレイする。代替として、または加えて、コンピューティング機器は、スケジュールされていないメディアセグメントの後で、追加のメディアコンテンツが再生される前に、コンテキスト的関連情報を挿入してもよい。
【００９７】
[0113]次に、未知のメディアコンテンツからのキューを基準データベース内の候補と照合することに関連した様々な方法について詳細に論じる。これらの方法は、図２に関連して上述した最近傍探索プロセスを含む。
【００９８】
[0114]上述したように、映像照合システムは、メディア・コンテンツ・ストリームがスケジュールされていないメディアセグメントを含む場合にメディア・コンテンツ・ストリームを識別するように構成することができる。さらに上述したように、メディア・コンテンツ・ストリームを識別することは、スケジュールされていないメディアセグメントの前または後にメディア表示装置によって再生されるメディアコンテンツを識別することを含む。メディアコンテンツを識別するためのプロセスについては、図１に関連して上述した。具体的には、映像コンテンツシステムは、メディアコンテンツ装置の表示機構から取得したサンプル（例えば、グラフィックサンプルおよび／または音声サンプル）を使用し、これらのサンプルからキューを生成する。次いで、映像照合システムはそれらのキューを、既知のメディアコンテンツのキューを含む基準データベースと照合する。
【００９９】
[0115]映像照合システムは、データベースにおいて一致を見つける効率を高める様々な方法をさらに含む。データベースは膨大な数のキューを含み、よって、映像照合システムは、潜在的な一致、すなわち照合すべき「候補」を見つけるためのアルゴリズムを含む。映像照合システムは、どの候補キューがメディアコンテンツ装置の表示機構から生成されたキューと実際に一致するか判定するアルゴリズムをさらに含む。候補キューを捜し出すことは、キューをデータベース内のすべてのエントリと照合するなど、キュー値をデータベース内の値と照合するための他の方法よりも効率がよい。
【０１００】
[0116]最近傍および経路追跡は、未知のキューを基準データベース内の候補キューと照合するのに使用できる技術の例である。経路追跡は、多くの可能な点の中から関連する点列を識別するための数学的方法である。最近傍は、経路追跡を実行するための候補点を識別するのに使用できる方法である。以下では、曖昧なキューを用いた映像送信の追跡に経路最近傍および経路追跡を適用する例が示されているが、この一般概念は、一致候補が基準データベースの中から選択される任意の分野に適用することができる。
【０１０１】
[0117]効率的な映像追跡のための方法を提示する。映像追跡は、未知の映像キューが与えられた場合に映像基準データベース内の照合候補を捜し出す問題に対するアプリケーション経路追跡技術である。多数の映像セグメントが与えられる場合、システムは、所与のクエリ映像入力が、どんなセグメントから、どんな時間オフセットで取得されるか識別できなければならない。セグメントとオフセットを併せて位置と呼ぶ。この方法を映像追跡と呼ぶのは、この方法は、一時停止、早送り、巻き戻し、他のセグメントへの急な切り替え、および未知のセグメントへの切り替えを効率的に検出し、適応させることができなければならないからである。ライブ映像を追跡する前に、データベースが処理される。視覚的キュー（少数の画素値）が、１秒の一定比率ごとにフレームから取得され、専用のデータ構造に入れられる（これもリアルタイムで行うことができることに留意されたい）。映像追跡は、入力映像からキューを連続して受信し、その現在位置に関する信頼値または推定値の集合を更新することによって行われる。各キューは推定値と合致し、または合致せず、新しい証拠を反映するよう調整される。この映像位置が真である信頼度が十分に高い場合、映像位置は正しい位置であると想定される。ごく少数の可能な「被疑点」位置を追跡することによって、これを効率的に行うことができる。
【０１０２】
[0118]映像追跡のための方法を説明しているが、数学的構造を用いてこの方法を説明し、考察する。この導入部の目的は、読者に２つのドメインを変換するのに必要なツールを提供することである。映像信号は連続するフレームで構成される。各フレームは静止画とみなすことができる。すべてのフレームは画素のラスタである。各画素は、その画素の色の赤、緑、および青（ＲＧＢ）の構成に対応する３つの強度値からなる。本明細書で用いる用語では、キューとは、フレーム内の画素のサブセットのＲＧＢ値および対応するタイムスタンプのリストである。キュー内の画素数はフレーム内の画素数よりも大幅に小さく、通常は５〜１５の間である。スカラ値の順序付きリストであるため、キュー値は、実際にはベクトルである。このベクトルを点とも呼ぶ。
【０１０３】
[0119]これらの点は高次元であり、通常は１５〜１５０の間であるが、２次元の点と仮定することができる。その証拠に各説明図を２次元プロットとして示す。次に、映像の進行とそれに対応するキュー点を考察する。通常、時間がわずかに変化すると画素値もわずかに変化する。画素点はフレーム間でわずかに「移動している」とみなすことができる。フレーム間でのこれらのわずかな移動に従い、キューは、ビーズが曲がったワイヤ上をたどるように空間内の経路をたどる。
【０１０４】
[0120]この例えで言うと、映像追跡では空間内のビーズの位置（キュー点）が受け取られ、ビーズがたどるワイヤ（経路）の部分が探される。これは２つの事実により著しく困難になる。第１に、ビーズはワイヤを正確にたどらず、むしろワイヤからある変化する未知の距離を保つ。第２に、ワイヤはすべて相互に絡み合っている。これらの記述はセクション２で正確に述べられている。以下に記載するアルゴリズムは、これを２つの概念的ステップで行う。キューが受け取られると、アルゴリズムは、キュー点に十分に近いすべての既知の経路上のすべての点を探す。これらを被疑点と呼ぶ。これは、ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ（等しいボール内での確率論的点位置決定））アルゴリズムを用いて効率的に行われる。これらの被疑点は履歴データ構造に追加され、各被疑点が真の位置を指示している確率が計算される。このステップは、十分に可能性の低い被疑点位置を除去することも含む。この履歴更新プロセスは、一方ではわずかな履歴だけが保持され、他方では確度の高い位置がすっと削除されないようにする。汎用アルゴリズムはアルゴリズム１で与えられ、図１１に例示されている。
【表１】
2018530273.tif 000003
【０１０５】
[0121]以下の各セクションでは、最初にセクション１でＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ）アルゴリズムについて説明する。ＰＰＬＥＢアルゴリズムは、上記のアルゴリズム１の第５行を効率的に行うために用いられる。この被疑点の探索を迅速に行える能力は、この方法の適用性にとって非常に重要である。セクション２では、第６行および第７行を行うための１つの可能な統計モデルについて説明する。説明するモデルは、このセットアップのための自然な選択である。またモデルをどのようにして非常に効率的に使用できるかも示す。
【０１０６】
[0122]セクション１  ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ）
【０１０７】
[0123]以下のセクションでは、ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ）を行うための簡単なアルゴリズムについて説明する。従来のＰＬＥＢ（ｐｏｉｎｔ  ｌｏｃａｔｉｏｎ  ｉｎ  ｅｑｕａｌ  ｂａｌｌｓ）では、１Ｒ  ｄおよび半径ｒの指定されたボールにおける、ｎ個の点ｘの集合から開始する。アルゴリズムは、効率的なデータ構造を生成するためにＯ（ｐｏｌｙ（ｎ））の前処理時間を与えられる。次いで、クエリ点ｘが与えられた場合、アルゴリズムは、｜｜ｘ−ｘｉ｜｜≦ｒになるようにすべての点ｘを返す必要がある。｜｜ｘ−ｘｉ｜｜≦ｒになるような点の集合は、幾何学的には、クエリｘを取り囲む半径ｒのボール内に位置する（図１２参照）。この関係をｘ、ｘに近い、またはｘ、およびｘは近傍であるという。
【０１０８】
[0124]ＰＰＬＥＢの問題と最近傍探索の問題とは、学界で大きな注目を集めている２つの類似した問題である。実際、これらの問題は計算幾何学の分野で最初に研究されたものであった。周囲の次元が小さいかまたは一定である場合には多くの異なる方法が要求を満たす。これらの方法は、空間を異なるやり方で区分し、各部分を再帰的に探索する。これらの方法には、ＫＤツリー、カバーツリーなどが含まれる。低次元では非常に効率的であるが、周囲の次元が高い場合、これらの方法は非常に不十分にしか機能しない傾向にある。これは「次元の呪い」として知られている。様々な手法が、次元の呪いを克服しつつこの問題を解決しようと試みている。本明細書で用いるアルゴリズムは、アルゴリズムのより単純で高速なバージョンを使用し、局所性鋭敏型ハッシュを利用することができる。
【０１０９】
[0125]セクション１．１  局所性鋭敏型ハッシュ
【０１１０】
[0126]局所性鋭敏型ハッシュの方式では、以下になるようなハッシュ関数Ｈのファミリが考案される。
【数１】
2018530273.tif 000004
【０１１１】
[0127]言葉で説明すると、ｘとｙがｈによって同じ値にマップされる確率は、ｘとｙとが互いに近い場合には著しく高くなる。
【０１１２】
[0128]明確にするために、最初に、すべての入力ベクトルが同じ長さｒ’のものであり、ｒ’＞
【数２】
2018530273.tif 000005
である単純化されたシナリオを扱う。後者の条件の理由は後で明らかになる。最初に、ｘとｙの間の角度に応じてｘとｙを分離するランダム関数ｕ∈Ｕを定義する。
【数３】
2018530273.tif 000006
を単位球Ｓｄ−１から一様に選ばれたランダムベクトルとし、ｕ（ｘ）＝ｓｉｇｎ（
【数４】
2018530273.tif 000007
）とする（図１３参照）。Ｐｒｕ−Ｕ（ｕ（ｘ））≠ｕ（ｙ））＝０ｘ，ｙ／πであることを検証することは容易である。さらに、円上の任意の点ｘ、ｙ、ｘ’、ｙ’について、よって以下の通りである。
【数５】
2018530273.tif 000008
【０１１３】
[0129]関数Ｈのファミリは、ｕのｔ個の独立したコピーの外積となるように設定され、すなわちｈ（ｘ）＝［ｕ１（ｘ），．．．，ｕｔ（ｘ）］である。直観的には、ｈ（ｘ）＝ｈ（ｙ）の場合、ｘとｙとが互いに近い可能性が高くなるようにしたい。これを定量化する。最初に、予期されるフォールスポジティブ誤りの数ｎｆｐを計算する。これらは、ｈ（ｘ）＝ｈ（ｙ）であるが、｜｜ｘ−ｙ｜｜＞２ｒの場合である。ｎｆｐが１以下である値ｔが見つかる。すなわち、１は間違っているとは予期されていない。
Ｅ［ｎｆｔ］≦ｎ（１−２ｐ）ｔ≦１
→ｔ≧ｌｏｇ（１／ｎ）／ｌｏｇ（１−２ｐ）
【０１１４】
[0130]次に、ｘとｙとが近傍である場合のｈ（ｘ）＝ｈ（ｙ）の確率を計算する。
【数６】
2018530273.tif 000009
【０１１５】
[0131]ここでは、２ｐ＜１でなければならず、これにはｒ’＞
【数７】
2018530273.tif 000010
が必要であることに留意されたい。これはあまり高い成功確率のようには思われないであろう。確かに、１／
【数８】
2018530273.tif 000011
は１／２より著しく小さい。次のセクションでは、どのようにしてこの確率を１／２まで上げるかについて説明する。
【０１１６】
[0132]セクション１．２  点探索アルゴリズム
【０１１７】
[0133]関数ｈは、空間内のすべての点をバケットにマップする。ハッシュ関数ｈに関連する点ｘのバケット関数
【数９】
2018530273.tif 000012
をＢｈ（ｘ）≡｛ｘｉ｜ｈ（ｘｉ）＝ｈ（ｘ）｝として定義する。維持されるデータ構造は、バケット関数のｍ＝Ｏ（
【数１０】
2018530273.tif 000013
）個のインスタンス［Ｂｈ１，…，Ｂｈｍ］である。点ｘを探索すると、関数は
【数１１】
2018530273.tif 000014
を返す。前セクションによれば、２つの望ましい結果が生じる。
【数１２】
2018530273.tif 000015
【０１１８】
[0134]言い換えると、少なくとも１／２の確率でｘの各近傍が見つかるが、多くの非近傍を見つける可能性は低い。
【０１１９】
[0135]セクション１．３  異なる半径の入力ベクトルの処理
【０１２０】
[0136]前セクションでは、同じ長さ、すなわちｒ’のベクトルを探索することのみを扱った。次に、この構造をビルディングブロックとして用いて異なる半径での探索をどのようにサポートできるかについて説明する。図１４に示すように、空間は指数関数的に増加する幅の環に分割される。Ｒｉと表記されている環ｉは、ｘｉ∈［２ｒ（１＋∈）ｉ，２ｒ（１＋∈）ｉ＋１］になるようなすべての点ｘｉを含む。これを行うことで２つの目的が達成される。第１に、ｘｉとｘｊが同じ環に属している場合には、｜｜ｘｊ｜｜／（１＋∈）≦｜｜ｘｉ｜｜≦｜｜ｘｊ｜｜（１＋∈）である。第２に、いかなる探索もせいぜい１／∈のそのような環で行うことができる。さらに、データセット内の最大長ベクトルがｒ’である場合には、システム内の環の総数はＯ（ｌｏｇ（ｒ’／ｒ））である。
【０１２１】
[0137]セクション２  経路追跡問題
【０１２２】
[0138]経路追跡問題では、空間内の固定経路が、時点列内の粒子の位置と共に与えられる。粒子、キュー、および点という用語は、区別なく用いられる。アルゴリズムは、経路上の粒子の位置を出力する必要がある。これは以下のいくつかの要因、すなわち、粒子は、経路を近似的にたどるにすぎないこと、経路は不連続であり、何度も自己交差する可能性があること、粒子位置と経路位置の両方が（それぞれに異なる）時点列として与えられること、によってより困難になる。
【０１２３】
[0139]この問題は、任意の数の経路上の粒子の追跡をシミュレートできることに留意することが重要である。これは、各経路を連結して１本の長い経路にし、結果として得られる位置を個々の経路上の位置として解釈することによって簡単に行われる。
【０１２４】
[0140]より正確には、経路Ｐをパラメトリック曲線
【数１３】
2018530273.tif 000016
とする。曲線パラメータを時間と呼ぶ。既知である経路上の点は任意の時点ｔｉにおいて与えられ、すなわちｎ対の（ｔｉ，Ｐ（ｔｉ））が与えられる。粒子は経路をたどるが、その位置は図１５に示すように異なる時点において与えられる。さらに、ｍ対の（ｔ’ｊ，ｘ（ｔ’ｊ））が与えられ、ｘ（ｔ’ｊ）は時間ｔ’ｊにおける粒子の位置である。
【０１２５】
[0141]セクション２．１  尤度推定
【０１２６】
[0142]粒子は経路を正確にたどらず、経路は何度も自己交差する可能性があるため、粒子が実際にある経路上の位置を確実に識別することは通常は不可能である。したがって、すべての可能な経路位置上で確率分布が計算される。位置確率の確度が著しく高い場合、粒子位置は既知であると想定される。以下のセクションでは、これを効率的に行う方法について説明する。
【０１２７】
[0143]粒子が経路をたどっている場合には、粒子のタイムスタンプとＰ上の対応する点のオフセットとの間の時間差は比較的一定になるはずである。言い換えると、ｘ（ｔ’）が経路上で現在オフセットｔにある場合には、ｘ（ｔ’）はＰ（ｔ）に近いはずである。また、τ秒前には、ｘ（ｔ’）はオフセットｔ−τにあったはずである。よって、ｘ（ｔ’−τ）はＰ（ｔ−τ）に近いはずである（粒子が経路と交差しており、ｘ（ｔ’）がＰ（ｔ）に一時的に近い場合、ｘ（ｔ’−τ）とＰ（ｔ−τ）も近い可能性は低いことに留意されたい）。相対オフセットをΔ＝ｔ−ｔ’と定義する。粒子が経路をたどっている限り、相対オフセットΔは変化しないままであることに留意されたい。すなわち、ｘ（ｔ’）はＰ（ｔ’＋Δ）に近い。
【０１２８】
[0144]最尤相対オフセットは、以下を計算することによって得られる。
【数１４】
2018530273.tif 000017
【０１２９】
[0145]言葉で説明すると、最も可能性が高い相対オフセットは、粒子の履歴の可能性が最も高いオフセットである。しかし、この方程式は統計モデルなしでは解くことができない。このモデルは、ｘが経路をどれほど厳密にたどるか、ｘが位置間をジャンプする可能性がどれほど高いか、ならびに経路および粒子曲線が測定された点間でどれほど滑らかであるかを定量化しなければならない。
【０１３０】
[0146]セクション２．２  時間割引ビニング
【０１３１】
[0147]次に、尤度関数を推定するための統計モデルについて説明する。このモデルでは、経路からの粒子の逸脱が標準偏差ａｒで正規分布していると仮定する。またこのモデルでは、任意の所与の時点で、粒子が急に別の経路に切り替わるある非ゼロの確率があるとも仮定する。これは、過去の点の時間による指数関数的な割引によって明示される。モデル化の観点から合理的な選択であること以外に、このモデルには効率的に更新可能であるという利点もある。ある一定の時間単位１にわたって、尤度関数を、以下のように定義されるｆに比例するように設定する。
【数１５】
2018530273.tif 000018
【０１３２】
[0148]式中、α＜＜１はスケール係数であり、粒子が所与の時間単位において経路上のランダムな位置にジャンプする確率である。
【０１３３】
[0149]関数ｆの効率的な更新は、以下の簡単な知見を用いて達成することができる。
【数１６】
2018530273.tif 000019
【０１３４】
[0150]さらに、α＜＜１であるため、｜｜ｘ（ｔ´ｍ）−Ｐ（ｔｉ）｜｜≧ｒの場合、以下の式が生じる。
【数１７】
2018530273.tif 000020
【０１３５】
[0151]これは尤度関数の重要な特性である。というのは、合計の更新を、経路全体にわたってではなくｘ（ｔ’ｊ）の近傍にわたってのみ行うことができるようになるからである。Ｓで、｜｜ｘ（ｔ´ｍ）−Ｐ（ｔｉ）｜｜≧ｒになるような（ｔｉ，Ｐ（ｔｉ））の集合を表す。以下の式が生じる。
【数１８】
2018530273.tif 000021
【０１３６】
[0152]これについては以下のアルゴリズム２．２に記載する。項ｆは、負の整数インデックスも受け取る疎ベクトルとして用いられる。集合Ｓは、経路上のｘ（ｔｉ）のすべての近傍の集合であり、ＰＰＬＥＢアルゴリズムを用いて迅速に計算することができる。ｘ（ｔｉ）の近傍の数がある定数ｎｎｅａｒによって制限される場合には、ベクトルｆの非ゼロの数は一定の係数だけ大きいｎｎｅａｒ／ζによって制限されることを検証することは容易である。アルゴリズムの最終段階は、
【数１９】
2018530273.tif 000022
がある閾値を上回る場合のδの特定の値を出力することである。
【表２】
2018530273.tif 000023
【０１３７】
[0153]図１１に、３つの連続した点位置とそれらの周りの経路点を示す。最下点だけでも中間点だけでも経路の正しい部分を十分に識別できなかったはずであることに留意されたい。しかし、これらの点を併せれば十分に識別できる。最上点を追加すれば、粒子が実際に経路の最終（左）曲線のものである確実性が増す。
【０１３８】
[0154]図１２では、ｎ個の（灰色の）点の集合が与えられた場合、アルゴリズムはクエリ点（黒）を与えられ、クエリ点から距離ｒ内にある点の集合（円内の点）を返す。従来の設定では、アルゴリズムはそのようなすべての点を返さなければならない。確率的設定では、そのような各点がある一定の確率でのみ返されるはずである。
【０１３９】
[0155]図１３に、ｕ（ｘ１）、ｕ（ｘ２）、およびｕ（ｘ）の各値を示す。直感的には、関数ｕは、破線がｘ１とｘ２との間を通る場合はｘ１とｘ２とに異なる値を与え、そうでない場合は同じ値を与える。破線をランダムな方向に通せば、これが起こる確率は、ｘ１とｘ２との角度に正比例するようになる。
【０１４０】
[0156]図１４に、環Ｒｉが半径２ｒ（１＋∈）ｉと２ｒ（１＋∈）ｉ＋１との間にあるように空間を環に分割することによって、環内の任意の２つのベクトルが最大（１＋∈）因子まで同じ長さであり、任意の探索がせいぜい１＋∈環において行われることを確実にできることを示す。
【０１４１】
[0157]図１５に、自己交差経路とクエリ点（黒）とを示す。粒子位置の履歴がなければ、粒子が経路上のどこにあるか知ることは不可能であることが例示されている。
【０１４２】
[0158]図１６に、３つの連続した点位置とそれらの周りの経路点とを示す。ｘ（ｔ１）だけでもｘ（ｔ２）だけでも経路の正しい部分を十分に識別できなかったはずであることに留意されたい。しかし、これらの点を併せれば十分に識別できる。ｘ（ｔ３）を追加すれば、粒子が実際に経路の最終（左）曲線のものである確実性が増す。
【０１４３】
[0159]以上の記述では、説明を目的として、様々な例の十分な理解を提供するために具体的詳細が示されている。しかし、これらの具体的詳細なしでも様々な例が実施されうることは明らかであろう。例えば、回路、システム、ネットワーク、プロセス、および他の構成要素は、不必要な詳細で例を不明瞭にしないようにブロック図形式の構成要素として示される場合がある。場合によっては、各例を不明瞭にしないように、周知の回路、プロセス、アルゴリズム、構造、および技術が不必要な詳細なしで示されることがある。図および説明は限定のためのものではない。
【０１４４】
[0160]以上の記述は、例示を提供するものにすぎず、本開示の範囲、適用性、または構成を限定するためのものではない。むしろ、各例の前述の説明は、当業者に、様々な例の実施可能要件を提供するものである。添付の特許請求の範囲に記載されている本発明の趣旨および範囲を逸脱することなく要素の機能および構成の様々な変更を行いうることを理解されたい。
【０１４５】
[0161]また、個々の例を、流れ図、フロー図、データフロー図、構造図、またはブロック図として図示されるプロセスとして記述することができることにも留意されたい。流れ図は各動作を順次的なプロセスとして記述している場合もあるが、動作の多くは、並列に、または同時に行うことができる。加えて、動作の順序を並べ替えることもできる。プロセスは、その動作が完了したときに打ち切られるが、図には含まれていない追加のステップを有する可能性もある。プロセスは、方法、関数、プロシージャ、サブルーチン、サブプログラムなどに対応させることができる。プロセスが関数に対応する場合、その打ち切りは呼び出した関数またはメイン関数への関数の戻りに対応させることができる。
【０１４６】
[0162]「機械可読記憶媒体」または「コンピュータ可読記憶媒体」という用語には、可搬型または非可搬型の記憶装置、光記憶装置、ならびに（１つまたは複数の）命令および／またはデータを記憶、収容、または担持することができる様々な他の媒体が含まれるが、これらに限定されない。機械可読記憶媒体またはコンピュータ可読記憶媒体には、データを格納することができ、搬送波および／または無線で、または有線接続上で伝搬する一時的な電子信号を含まない非一時的な媒体が含まれる。非一時的な媒体の例には、磁気ディスクや磁気テープ、コンパクトディスク（ＣＤ）やデジタル多用途ディスク（ＤＶＤ）などの光記憶媒体、フラッシュメモリ、メモリまたはメモリデバイスが含まれるが、これらに限定されない。コンピュータプログラム製品には、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、もしくは命令を表すコードセグメントもしくは機械実行可能命令、または命令、データ構造、もしくはプログラム文の任意の組み合わせが含まれる。コードセグメントは、情報、データ、引数、パラメータ、またはメモリコンテンツを渡し、かつ／または受け取ることによって、別のコードセグメントまたはハードウェア回路に結合されてよい。情報、引数、パラメータ、データ、または他の情報は、メモリ共有、メッセージパッシング、トークンパッシング、ネットワーク伝送、または他の伝送技術を含む任意の適切な手段を用いて、受け渡され、転送され、または伝送されてよい。
【０１４７】
[0163]さらに、各例は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、またはこれらの任意の組み合わせによって実施されてよい。ソフトウェア、ファームウェア、ミドルウェア、またはマイクロコードとして実施される場合、必要なタスクを行うプログラムコードまたはコードセグメント（例えば、コンピュータプログラム製品）は、機械可読媒体に格納されてよい。（１つまたは複数の）プロセッサは必要なタスクを行うことができる。
【０１４８】
[0164]図のいくつかに示されるシステムは、様々な構成で提供されうる。いくつかの例では、システムは、システムの１つまたは複数の構成要素がクラウド・コンピューティング・システムとして１つまたは複数のネットワークにわたって分散されている分散システムとして構成される。
【０１４９】
[0165]さらに詳細に上述したように、本開示のある特定の態様および特徴は、未知のデータ点を１つまたは複数の基準データ点と比較することによって未知のデータ点を識別することに関するものである。本明細書に記載するシステムおよび方法は、未知のデータ点を識別するのに使用される大規模なデータセットの格納および探索の効率を改善する。例えば、これらのシステムおよび方法は、識別を行うのに必要な大規模なデータセットの密度を低減しつつ、未知のデータ点の識別を可能にする。この技術は、大量のデータを収集し、操作する任意のシステムに適用することができる。これらのシステムの実例には、自動化されたコンテンツベースの探索システム（例えば、映像関連アプリケーションや他の適切なアプリケーションの自動コンテンツ認識）、ＭａｐＲｅｄｕｃｅシステム、Ｂｉｇｔａｂｌｅシステム、パターン認識システム、顔認識システム、分類システム、コンピュータ・ビジョン・システム、データ圧縮システム、クラスタ分析、または任意の他の適切なシステムが含まれる。当業者であれば、本明細書に記載する技術は、未知のデータと比較されるデータを格納する任意の他のシステムに適用できることを理解するであろう。自動コンテンツ認識（ＡＣＲ）のコンテキストでは、例えば、これらのシステムおよび方法は、照合システムが未知のデータグループと既知のデータグループとの間の関係を探索し、発見するために格納しなければならないデータ量を削減する。
【０１５０】
[0166]限定ではなく例示にすぎないが、本明細書に記載するいくつかの例では、説明のために自動音声および／または映像コンテンツ認識システムを使用している。しかし、その他のシステムも同じ技術を使用できることを当業者は理解するであろう。
【０１５１】
[0167]具体的な要件に応じて大幅な変更がなされてもよい。例えば、カスタマイズされたハードウェアが使用されてもよく、かつ／または特定の要素がハードウェア、ソフトウェア（アプレットなどのポータブルソフトウェアを含む）、もしくはその両方で実装されてもよい。さらに、他のアクセスまたはネットワーク入力装置／出力装置などのコンピューティング機器への接続が用いられてもよい。
【０１５２】
[0168]以上の明細書では、様々な実施態様がその具体例に関連して説明されているが、実施態様はそれらだけに限定されないことを当業者は理解するであろう。上述の実施態様の様々な特徴および態様は、個別に用いられても一緒に用いられてもよい。さらに、本明細書の幅広い趣旨および範囲から逸脱することなく、本明細書に記載した以外の任意の数の環境および用途において各例を利用することができる。したがって、本明細書および図面は、限定ではなく例示とみなすべきである。
【０１５３】
[0169]以上の説明では、例示を目的として、方法を特定の順序で記載した。別の例では、方法は記載した順序と異なる順序で行われてもよいことを理解されたい。また、上述の方法は、ハードウェア構成要素によって行われてもよく、機械実行可能命令でプログラムされた汎用または専用プロセッサや論理回路などの機械に方法を行わせるのに用いられる機械実行可能命令のシーケンスとして具体化されてもよいことも理解されたい。これらの機械実行可能命令は、ＣＤ−ＲＯＭや他の種類の光ディスク、フロッピーディスケット、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードや光カード、フラッシュメモリ、または電子命令を格納するのに適した他の種類の機械可読媒体など、１つまたは複数の機械可読媒体に格納されていてよい。あるいは、これらの方法は、ハードウェアとソフトウェアの組み合わせによって行われてもよい。
【０１５４】
[0170]構成要素がある特定の動作を行うように構成されているものとして記述される場合、そのような構成は、例えば、その動作を行う電子回路または他のハードウェアを設計することによって、その動作を行うプログラマブル電子回路（例えば、マイクロプロセッサや他の適切な電子回路）をプログラムすることによって、またはそれらの任意の組み合わせによって実現することができる。
【０１５５】
[0171]本明細書では本出願の説明例を記載したが、本発明の概念は、それ以外にも様々に具体化され、用いられること、および添付の特許請求の範囲は、先行技術による限定を除いて、そうした変形を含むものと解釈すべきであることを理解されたい。
【図１】
2018530273.tif 000024
【図２】
2018530273.tif 000025
【図３】
2018530273.tif 000026
【図４】
2018530273.tif 000027
【図５】
2018530273.tif 000028
【図６】
2018530273.tif 000029
【図７】
2018530273.tif 000030
【図８】
2018530273.tif 000031
【図９】
2018530273.tif 000032
【図１０】
2018530273.tif 000033
【図１１】
2018530273.tif 000034
【図１２】
2018530273.tif 000035
【図１３】
2018530273.tif 000036
【図１４】
2018530273.tif 000037
【図１５】
2018530273.tif 000038
【図１６】
2018530273.tif 000039
【国際調査報告】
2018530273.tif 000040
2018530273.tif 000041