(57)【要約】【課題】  ビデオ内の位置を信頼可能に識別するためにビデオを処理するためのプロセスおよびシステムを提供する。【解決手段】  ビデオ位置識別プロセスおよびシステムは、コンテンツベースのビデオタイムラインを使用する。これらのタイムラインは、ビデオコンテンツのビデオ「フィンガプリント」または「シグネチャ」の順序付きシーケンスから構成され、これらは、ビデオのフレームイメージにおける空間特性を活用し、ビデオが挿入または削除などにより修正されている場合でも、位置を信頼可能に識別する。【選択図】  図１
2004357302.tif 000002
【特許請求の範囲】
【請求項１】
ビデオを処理するための方法であって、
第１のシグネチャシーケンスを、前記ビデオの第１のバージョンのコンテンツから生成するステップと、
第２のシグネチャシーケンスを、前記ビデオの第２のバージョンのコンテンツから生成するステップと、
前記第１および第２のシグネチャシーケンスを比較して、マッチを決定するステップと
を備えることを特徴とする方法。
【請求項２】
コンテンツは、（ａ）ビデオフレーム内のビジュアルコンテンツ、（ｂ）オーディオトラックビデオフレームコンテンツ、（ｃ）前記ビデオと同期化されているオーディオ、（ｄ）クローズドキャプショニング情報のうち少なくとも１つを含むことを特徴とする請求項１に記載の方法。
【請求項３】
第１のシグネチャシーケンスを生成するステップは、アノテーションを、前記ビデオの前記第１のバージョン内の関心範囲内の位置で生成するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
前記関心範囲は、少なくとも１つのビデオフレームを含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記第１のシグネチャシーケンスは、前記関心範囲内のフレームのコンテンツを表現するシグネチャを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記第２のシグネチャシーケンスは、前記ビデオの前記第２のバージョンの全体の長さのコンテンツから生成されることを特徴とする請求項１に記載の方法。
【請求項７】
前記第１および第２のシグネチャシーケンスを比較するステップは、前記ビデオの前記第１のバージョン内の前記アノテーションの前記位置に対応する、前記ビデオの前記第２のバージョン内の前記アノテーションの位置を回復するステップをさらに備えることを特徴とする請求項３に記載の方法。
【請求項８】
請求項１に記載の方法を実行するためのコンピュータ実行可能命令を有することを特徴とするコンピュータにより読み取り可能な記録媒体。
【請求項９】
ビデオを処理するための方法であって、
前記ビデオ内で、少なくとも１つのビデオフレームを含む関心範囲を選択するステップと、
第１のシグネチャシーケンスを、前記少なくとも１つのビデオフレームのコンテンツから生成するステップと、
前記第１のシグネチャシーケンスを使用して、前記関心範囲の少なくとも一部を後に回復するステップと
を備えることを特徴とする方法。
【請求項１０】
前記第１のシグネチャシーケンスは、前記ビデオの第１のバージョンのコンテンツから生成されることを特徴とする請求項９に記載の方法。
【請求項１１】
第２のシグネチャシーケンスを前記ビデオの第２のバージョンのコンテンツから生成するステップをさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記第１のシグネチャシーケンスおよび前記第２のシグネチャシーケンスをマッチさせるステップをさらに備えることを特徴とする請求項１１に記載の方法。
【請求項１３】
ビデオ内の位置を識別するための方法であって、
前記ビデオの第１のバージョン内の位置に置かれたビデオフレームにアノテーションを付けて、ビデオアノテーションを生成するステップと、
ビデオアノテーションアンカーを前記ビデオフレームのコンテンツに基づいて生成し、前記ビデオアノテーションを頑強にアンカーするステップと、
前記ビデオアノテーションアンカーを使用して、前記ビデオアノテーションを配置する、前記ビデオの第２のバージョン内の前記位置を回復するステップと
を備えることを特徴とする方法。
【請求項１４】
前記ビデオアノテーションアンカーは、コンテンツベースのビデオタイムラインを使用して生成されることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記ビデオアノテーションアンカーを生成するステップは、
前記ビデオの前記第１のバージョン内のビデオフレームのセットに対応する、一時的な関心範囲を定義するステップと、
第１のシグネチャシーケンスを、前記関心範囲内のコンテンツから生成するステップと
をさらに備えることを特徴とする請求項１３に記載の方法。
【請求項１６】
１つまたは複数のプロセッサによって実行されるとき、前記１つまたは複数のプロセッサに請求項１３に記載の方法を実行させるためのコンピュータ読み取り可能命令を有することを特徴とする１つまたは複数のコンピュータにより読み取り可能な記録媒体。
【請求項１７】
第１の場所でビデオの第１のバージョン内でアノテーションを作成し、第２の場所で前記ビデオの第２のバージョン内で前記アノテーションを見るための方法であって、
ビデオフレームのアノテーションを、前記ビデオの前記第１のバージョン内の位置で作成するステップと、
第１のシグネチャシーケンスを、前記ビデオフレーム内のコンテンツから生成するステップと、
第２のシグネチャシーケンスを、前記ビデオの前記第２のバージョン内のすべてのビデオフレームから生成および抽出するステップと、
前記アノテーションおよび前記第１のシグネチャシーケンスを、前記第１の場所から前記第２の場所に送信するステップと、
前記第１のシグネチャシーケンスを前記第２のシグネチャシーケンスとマッチさせて、前記ビデオの第２のバージョン内の前記アノテーションの前記位置を回復するステップと
を備えることを特徴とする方法。
【請求項１８】
前記アノテーションおよび前記第１のシグネチャシーケンスは、前記第１の場所から前記第２の場所に、ナロー通信チャネルによって送信されることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記ナロー通信チャネルは、（ａ）電子メール、（ｂ）携帯電話、（ｃ）インターネット、（ｄ）インスタントメッセージングサービスのうち、少なくとも１つであることを特徴とする請求項１８に記載の方法。
【請求項２０】
前記アノテーションおよび前記第１のシグネチャシーケンスを前記第１の場所から前記第２の場所に送信するステップは、ユーザによって実行されることを特徴とする請求項１７に記載の方法。
【請求項２１】
前記アノテーションおよび前記第１のシグネチャシーケンスを前記第１の場所から前記第２の場所に送信するステップは、自動的に実行されることを特徴とする請求項１７に記載の方法。
【請求項２２】
ビデオ内のビデオフレームの位置を識別するための方法であって、
前記ビデオの第１のバージョン内の位置でのビデオフレームにマークを付けて、マーク付きビデオフレームを作成するステップと、
シグネチャを前記ビデオフレームの各々のコンテンツから生成して、第１のシグネチャシーケンスを作成するステップと、
第２のシグネチャシーケンスを、前記ビデオの第２のバージョンのコンテンツ全体から生成するステップと、
前記第１および第２のシグネチャシーケンスをマッチさせて、前記ビデオの前記第２のバージョン内の前記マーク付きビデオフレームの前記位置を回復するステップと
を備えることを特徴とする方法。
【請求項２３】
前記マーク付きビデオフレームを、前記ビデオの前記第２のバージョンから除去して、ビデオサマリを作成するステップをさらに備えることを特徴とする請求項２２に記載の方法。
【請求項２４】
サードパーティコンテンツを前記マーク付きフレームに追加するステップと、
前記マーク付きビデオフレームの前記回復された位置を使用して、前記サードパーティコンテンツを前記ビデオの前記第２のバージョンに同期化させるステップと
をさらに備えることを特徴とする請求項２２に記載の方法。
【請求項２５】
前記マーク付きビデオフレームを、前記ビデオの前記第２のバージョンから除去するステップをさらに備え、前記マーク付きフレームは、コマーシャルなど、商業関連コンテンツを含むことを特徴とする請求項２２に記載の方法。
【請求項２６】
前記方法は、（ａ）前記ビデオのインデクシング、（ｂ）ビデオデジタル権利管理、（ｃ）ビデオデータベースクエリのうち、少なくとも１つのために使用されることを特徴とする請求項２２に記載の方法。
【請求項２７】
ビデオのビデオフレーム内に含まれたコンテンツの表現を得るためのコンピュータ実行可能命令を有するコンピュータにより読み取り可能な記録媒体であって、
前記ビデオフレーム内のいずれかの色情報を廃棄して、結果として生じるイメージを生成するステップと、
前記結果として生じるイメージをダウンサンプルして、グレースケールイメージを生成するステップと、
中間しきい値化を前記グレースケールイメージ上で実行して、前記ビデオフレームの０／１ビットマップバージョンを生成するステップと、
前記ビデオフレームの前記０／１ビットマップバージョンを、モーフォロジカルクリーニングを使用してクリーニングして、前記ビデオフレームのロングシグネチャを生成するステップと
を備えることを特徴とするコンピュータにより読み取り可能な記録媒体。
【請求項２８】
前記ビデオフレームを４：３アスペクト比に正規化するステップをさらに備えることを特徴とする請求項２７に記載のコンピュータにより読み取り可能な記録媒体。
【請求項２９】
前記グレースケールイメージは３０ピクセル×４０ピクセルであることを特徴とする請求項２７に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３０】
前記０／１ビットマップ内の各ピクセルは、（ａ）０、（ｂ）１のうち一方の値を有することを特徴とする請求項２７に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３１】
中間しきい値化を実行するステップは、
前記グレースケールイメージの中間グレー値を決定するステップと、
前記中間グレー値をしきい値として定義するステップと
をさらに備えることを特徴とする請求項２７に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３２】
前記しきい値より上の輝度値を有する前記ビデオフレーム内のピクセルを、「１」として定義するステップと、
前記しきい値より下の輝度値を有する前記ビデオフレーム内のピクセルを、「０」として定義するステップと
をさらに備えることを特徴とする請求項３１に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３３】
モーフォロジカルクリーニングは、ライン詳細アーチファクトおよび他の雑音を前記ビデオフレームの前記０／１ビットマップバージョンから除去するために、カーネルフィルタリング（ｋフィルタリング）を含むことを特徴とする請求項２７に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３４】
前記ビデオフレームの前記０／１ビットマップバージョンを、モーフォロジカルクリーニングを使用してクリーニングするステップは、３×３のｋ―フィルタを前記ビデオフレームの前記０／１ビットマップバージョンに適用して、前記ビデオフレーム内のピクセルのうちｋより多い数が１である場合に前記フィルタの出力が１に等しくなり、そうでない場合は前記フィルタの出力が０に等しくなるようにするステップをさらに備えることを特徴とする請求項３３に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３５】
各反復の後に前記ｋの値を調整するステップをさらに備えることを特徴とする請求項３４に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３６】
前記ｋの値を調整するステップは、
１の数が減る場合、前記ｋの値を減らして、次の反復においてより多くの１を生じるステップと、
前記１の数が増す場合、前記ｋの値を増やして、次の反復においてより少ない１を生じるステップと
をさらに備えることを特徴とする請求項３５に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３７】
最初の反復での前記ｋの値は４．５に等しいことを特徴とする請求項３５に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３８】
所与の反復におけるピクセルの数がエプシロンより下に下がるとき、ｋフィルタリングを終了するステップをさらに備えることを特徴とする請求項３５に記載のコンピュータにより読み取り可能な記録媒体。
【請求項３９】
前記エプシロンの値は５に等しいことを特徴とする請求項３８に記載のコンピュータにより読み取り可能な記録媒体。
【請求項４０】
ビデオフレームのコンテンツを表現するいくつかのビットを含むロングシグネチャの次元を減らすための方法であって、
前記ロングシグネチャについての固有ベクトルおよび対応する固有値を決定するステップと、
前記固有値から、前記ロングシグネチャを特徴付ける主成分を選択するステップと、
前記ロングシグネチャ内の前記いくつかのビットより少ないものを有するショートシグネチャを、前記主成分から生成するステップと
を備えることを特徴とする方法。
【請求項４１】
主成分を選択するステップは、最高値を有する固有値を発見するステップと、
これらの最高値の固有値を前記主成分として定義するステップと
をさらに備えることを特徴とする請求項４０に記載の方法。
【請求項４２】
ｎビットを有するロングシグネチャを、ｎより少ないビットを有するショートシグネチャにダウンサンプルするための方法であって、
ｎビン(bin)を含むヒストグラムを生成するステップであって、各ビンは１ビットを表すステップと、
各ビットが１に等しくなる回数、および各ビットが０に等しくなる回数をカウントするステップと、
前記ヒストグラム内で最も識別的なビットを決定してマスクを生成するステップと、
前記ロングシグネチャを、前記マスクを使用してダウンサンプルして、前記ショートシグネチャを生成するステップと
を備えることを特徴とする方法。
【請求項４３】
前記最も識別的なビットを決定するステップは、どのビットが、１に等しくなる前記回数の半分および０に等しくなる前記回数の半分に最も近いかを発見するステップをさらに備えることを特徴とする請求項４２に記載の方法。
【請求項４４】
ビデオの第１のバージョンから生成された第１のシグネチャシーケンスと前記ビデオの第２のバージョンから生成された第２のシグネチャシーケンスをマッチさせるための方法であって、
比較するため連続シグネチャの数を表現する連続シグネチャ数を決定するステップと、
前記ビデオの前記第２のバージョンの開始を発見するステップと、
前記第１のシグネチャシーケンスの前記連続シグネチャ数を、前記第２のシグネチャシーケンスの前記連続シグネチャ数と比較することによって、マッチを決定するステップと
を備えることを特徴とする方法。
【請求項４５】
より小さい連続シグネチャ数は、より少量の情報およびほとんどない詳細を示し、より大きい連続シグネチャ数は、より大量の情報およびより大きい詳細を示すことを特徴とする請求項４４に記載の方法。
【請求項４６】
前記連続シグネチャ数は１０に等しいことを特徴とする請求項４４に記載の方法。
【請求項４７】
マッチを決定するステップは、
前記第１および前記第２のシグネチャシーケンスの間で異なるビットの数をカウントするステップと、
前記ビットの数がマッチングしきい値より下であるとき、マッチを発見するステップと
をさらに備えることを特徴とする請求項４４に記載の方法。
【請求項４８】
前記マッチングしきい値は約１２５ビットであることを特徴とする請求項４７に記載の方法。
【請求項４９】
前記ビデオ内の各フレームについての信頼性スコアを計算するステップをさらに備えることを特徴とする請求項４４に記載の方法。
【請求項５０】
前記信頼性スコアは各フレーム内の分散の量を表現し、
前記信頼性スコアが高く、前記マッチ内で使用された各フレーム内の前記分散が高い場合、前記マッチはより信頼性があると決定するステップと、
前記信頼性スコアが低く、前記マッチ内で使用された各フレーム内の前記分散が低い場合、前記マッチはより信頼性がないと決定するステップと
をさらに備えることを特徴とする請求項４９に記載の方法。
【請求項５１】
ビデオ位置識別システムであって、
第１のシグネチャシーケンスをビデオの第１のバージョンからのコンテンツに基づいて、かつ、第２のシグネチャシーケンスを前記ビデオの第２のバージョンからのコンテンツに基づいて生成する、シグネチャ生成および抽出モジュールと、
前記第１のシグネチャシーケンスおよび前記第２のシグネチャシーケンスをマッチさせて、関心範囲を回復する、シグネチャマッチングモジュールと
を備えることを特徴とするビデオ位置識別システム。
【請求項５２】
前記シグネチャ生成および抽出モジュールは、前記ビデオのビデオフレームをグレースケールに、現在の解像度で変換して、グレースケールビデオフレームを生成する、グレースケールコンバータをさらに備えることを特徴とする請求項５１に記載のビデオ位置識別システム。
【請求項５３】
前記シグネチャ生成および抽出モジュールは、前記グレースケールビデオフレームをダウンサンプルして、低解像度グレースケールビデオフレームを作成する、ダウンサンプルモジュールをさらに備えることを特徴とする請求項５２に記載のビデオ位置識別システム。
【請求項５４】
ダウンサンプルモジュールはガウスピラミッドを構築することを特徴とする請求項５３に記載のビデオ位置識別システム。
【請求項５５】
前記シグネチャ生成および抽出モジュールは、前記低解像度グレースケールビデオフレームを０／１ビットマップに変換する、中間しきい値ビットマップコンバータをさらに備えることを特徴とする請求項５３に記載のビデオ位置識別システム。
【請求項５６】
前記シグネチャ生成および抽出モジュールは、ビデオフレームの中間グレーレベルをしきい値として使用して、０および１の値を有するピクセルの数がほぼ前記ビデオフレームについて等しいことを保証することによって、ロングシグネチャを生成する、モーフォロジカルクリーニングモジュールをさらに備えることを特徴とする請求項５５に記載のビデオ位置識別システム。
【請求項５７】
前記シグネチャ生成および抽出モジュールは、前記ロングシグネチャをダウンサンプルして、前記ロングシグネチャより少ないビットを含むショートシグネチャを生成する、ショートシグネチャモジュールをさらに備えることを特徴とする請求項５６に記載のビデオ位置識別システム。
【請求項５８】
前記シグネチャマッチングモジュールは、シグネチャの連続シーケンスを前記第１および第２のシグネチャシーケンスから得る、連続シグネチャモジュールをさらに備えることを特徴とする請求項５１に記載のビデオ位置識別システム。
【請求項５９】
前記シグネチャマッチングモジュールは、マッチングしきい値を決定するマッチングしきい値モジュールをさらに備えることを特徴とする請求項５８に記載のビデオ位置識別システム。
【請求項６０】
前記シグネチャマッチングモジュールは、前記連続シグネチャのシーケンスおよび前記マッチングしきい値を使用してシグネチャの間の距離を比較する、距離比較モジュールをさらに備えることを特徴とする請求項５９に記載のビデオ位置識別システム。
【請求項６１】
前記シグネチャマッチングモジュールは、前記第１および第２のシグネチャシーケンス内の各シグネチャの信頼性を決定する、信頼性モジュールをさらに備えることを特徴とする請求項５８に記載のビデオ位置識別システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にビデオ処理に関し、より詳細には、コンテンツベースのビデオタイムラインを使用してビデオ内の位置を信頼可能に識別するためのプロセスおよびシステムに関する。これらのタイムラインは、ビデオコンテンツのビデオ「フィンガプリント」または「シグネチャ」の順序付きシーケンスから構成され、これらは、ビデオのフレームイメージにおける空間特性を活用し、ビデオが挿入または削除などにより修正されている場合でも、位置を信頼可能に識別する。
【背景技術】
【０００２】
ビデオはよく知られた普及しているメディアである。ビデオは、ほぼあらゆる居間、および増加する数のエンドユーザのパーソナルコンピュータ（ＰＣ）において見つけることができる。ビデオは、膨大な種類の形式、フォーマットおよび圧縮された形で提供され、その種類は毎年増大し続けている。この種類は、ビデオストリーム内の位置を信頼可能に識別する必要のあるビデオソフトウェアアプリケーションにとって、莫大な課題を与える。例として、これらのビデオソフトウェアアプリケーションには、集大成（サマライゼーション:summarization）、データベースインデクシング、コンテンツ同期化、およびビデオストリームのアノテーション(annotation）が含まれる。
【０００３】
ビデオストリーム内の位置を信頼可能に識別することは困難であり、これは、ビデオストリーム内の「同じ」ビデオコンテンツがそのライフタイムの全体に渡って微妙な修正を受ける可能性があるからである。これにより、フレーム番号または埋め込みタイムコードを使用して位置を信頼可能に識別することは、不可能になる可能性がある。これは特に、商業テレビ（ＴＶ）番組について当てはまり、これについての修正にはショートクリップの挿入および削除が含まれる可能性がある。例えば、同じ映画の異なる放送にはしばしば、異なるセットのコマーシャルが含まれる。加えて、他の一般的な修正にはフォーマット変換が含まれ、これは、米国で使用されているフォーマットであるＮａｔｉｏｎａｌ  Ｔｅｌｅｖｉｓｉｏｎ  Ｓｔａｎｄａｒｄｓ  Ｃｏｍｍｉｔｔｅｅ（ＮＴＳＣ）から、ヨーロッパにおける主要な規格であるＰｈａｓｅ  Ａｌｔｅｒｎａｔｉｎｇ  Ｌｉｎｅ（ＰＡＬ）へのフォーマット変換などである。さらに、他の修正には、ストレージ変更（圧縮フォーマット、圧縮パラメータ、または両方への変更など）、および、選択的にフレームを飛ばす（ドロップ:drop）ことができる時間圧縮が含まれる可能性がある。
【０００４】
ビデオストリーム内の位置を信頼可能に識別する必要性のある１つの応用例は、インターネット対応テレビシステム(web-enabled television system)におけるものである。一般に、インターネット対応テレビシステムは、ユーザがテレビを使用してワールドワイドウェブ（または「ウェブ」）をサーフ(surf)できるようにする製品および技術のグループを指す。これにより、ビデオ（またはＴＶ放送）に関連付けられたコンテンツ（または情報）をテレビ画面上に配置させることができると同時に、ウェブの使用が可能となる。したがって、ユーザはバスケットボールの試合を見て、試合の下で、ある選手についてのさらなる情報についてのハイパーリンクを見ることができる。同様に、ユーザは自分の好きなチームのスウェットシャツまたは帽子の購入に関する情報についてのハイパーリンクを見ることができる。このコンテンツは、あるビデオに関連付けられる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
コンテンツをビデオ放送に関連付けることについての１つの問題は、国内および世界の異なる地域において通常は異なるバージョンのビデオ放送が存在することである。異なるバージョンは、上述の一般的な修正に従って異なる可能性がある。これには、ビデオ放送の各バージョンについてのビデオ放送の手動のアノテーション（ハイパーリンクの挿入など）が必要となる。ビデオ放送の各バージョンについての手動のアノテーションは、時間がかかり、費用がかかり、誤りのある傾向がある。
【０００６】
ビデオ放送の各バージョンの手動のアノテーションを回避するために、コンテンツをビデオ放送に直接埋め込むことができる。埋め込みは、コンテンツをビデオ放送内の所望の位置、または同じデジタルビデオファイル内の同期化ストリーム内にくっつける(アタッチ:attach)することを伴う。しかし、１つの問題は、埋め込み技術に非常に柔軟性がないことである。それらのコンテンツをビデオ放送に埋め込むことを望むいくつかのソースがある場合、ビデオファイルは急速に非常に大きくなる。埋め込み技術についての他の問題には、セキュリティのリスク、および、所望のコンテンツについてのフィルタリングおよびサーチが困難であることが含まれる。
【０００７】
したがって、ビデオ内の位置の信頼可能な識別を提供して、フレーム番号および埋め込みタイムコードが必要とされないようにする、プロセスおよびシステムについての必要性が存在する。さらに、ビデオの異なるバージョンの間でコンテンツを同期化する、柔軟性のあるプロセスを提供する、プロセスおよびシステムについての必要性が存在する。また、ビデオ内の位置を頑強に識別することができ、フレームの追加および削除、異なる種類の圧縮、および異なる放送フォーマットによるビデオの修正を切り抜けることができる、プロセスおよびシステムについての必要性が存在する。
【課題を解決するための手段】
【０００８】
本明細書で開示する本発明は、ビデオコンテンツの異なるバージョン内で同じ位置を信頼可能に識別するためのプロセスおよびシステムを含む。
【０００９】
このプロセスおよびシステムは、フレーム毎のコンテンツベースのビデオ「シグネチャ」(signature)に依拠する。これらのビデオシグネチャは、ビデオについてのコンテンツベースのビデオタイムライン(video timeline)を形成する。コンテンツベースのビデオタイムラインは、フレーム番号または埋め込みタイムコードに依拠することなく、ビデオストリーム内の位置を頑強に識別するためのメカニズムである。コンテンツベースのビデオタイムラインは、ビデオシグネチャの順序付きシーケンスから構成される。ビデオ内のフレームのコンテンツに基づいて、コンテンツベースのビデオタイムラインはビデオシグネチャを使用して、特定のフレームまたはフレームのシーケンスを識別する。これらのコンテンツベースのビデオタイムラインは小型であり、生成およびサーチが速く、フレーム番号および埋め込みタイムコードを信頼不可能にする可能性のあるビデオへの一般的な修正に対して頑強である。これらの一般的な修正には、挿入、削除、時間圧縮、データ圧縮（Ｉｎｄｅｏ、ＣｉｎｅｐａｋおよびＭＰＥＧ４圧縮など）、放送フォーマット（ＮＴＳＣおよびＰＡＬなど）、センチレーション（ｓｅｎｔｉｌａｔｉｏｎｓ）（ホワイトノイズおよびブラックノイズなど）、３：２プルダウンエラー（テレビで表示された映画など）、およびカラーシフトが含まれる。ビデオ位置識別プロセスおよびシステムは、ビデオ内の位置の信頼可能な識別を提供して、フレーム番号および埋め込みタイムコードが必要とされないようにする。加えて、本明細書で開示するプロセスおよびシステムは頑強であり、上記に列挙した修正によるビデオの修正を切り抜けることができる。
【００１０】
コンテンツベースのビデオタイムラインは、重要な種類の問題に対処する。例えば、ビデオサマライゼーションおよびデータベースインデクシングにおいて、コンテンツベースのビデオタイムラインは、ビデオストリーム内の重要なオブジェクトおよびイベントの位置のマーキングおよび回復のための効率的なメカニズムを提供する。また、タイムラインが頑強であるため、これらをビデオストリーム自体から切り離して格納することができる。これは、コンテンツベースのビデオタイムラインを使用して、サードパーティのコンテンツの同期化およびアノテーションの位置決めをサポートできることを意味する。
【００１１】
例えば、以下の問題を考察する。ニューヨーク市内のユーザが、テレビ番組の地方バージョンにアノテーションを付けて、重要な部分を指摘する。すなわち、ニューヨーク市のユーザが、アノテーションを使用して番組のサマリを作成する。後に、ニューヨーク市のユーザは、シカゴにいる友人とこのアノテーションを共有することを望む。しかし、この友人は、この番組の地方のシカゴバージョンへのアクセスしか有していない。このバージョンは異なるセットのコマーシャルを含んでいるため、番組内で数分後に開始する。これはスポーツ放送の後に続いて「すでに進行中で」結合されたからである。シカゴのユーザはどのようにして、ニューヨークのユーザのアノテーションを、この番組の自分の地方のバージョン内の正確な位置で見ることができるだろうか。
【００１２】
本明細書で説明するビデオ位置識別プロセスおよびシステムを使用することによって、シカゴのユーザは、ニューヨーク市のユーザによって作成されたアノテーションを、この番組の地方のシカゴバージョン内の正確な位置に配置することができる。コンテンツベースのビデオタイムラインを生成することによって、ニューヨークのユーザは、番組の重要な部分を、非常に正確で頑強な方法において識別することができる。ニューヨークのユーザは自分のアノテーションを、関連部分またはタイムラインのフラグメントと共に、シカゴにいる自分の友人に電子メールを介して送信することができる。シカゴのユーザのマシン上のソフトウェアはこのビデオタイムラインのフラグメントを使用して、この番組の地方のシカゴバージョン内の正確な位置を位置付けることができる。これは、たとえシカゴバージョンがニューヨークバージョンとは著しく異なるとしても、当てはまる。
【発明を実施するための最良の形態】
【００１３】
本発明の態様を例示する以下の説明および添付の図面を参照することによって、本発明をさらに理解することができる。他の特徴および利点は、以下の本発明の詳細な説明を、例として本発明の原理を例示する添付の図面と共に考慮することから、明らかになるであろう。
【００１４】
このとき図面を参照し、図面においては全体に渡って類似の参照番号は対応する部分を表す。
【００１５】
以下の本発明の説明では添付の図面を参照し、これは本発明の一部を形成し、これにおいて、例として、それにより本発明を実施することができる具体的な実施例が示される。本発明の範囲から逸脱することなく、他の実施形態を利用することができ、構造の変更を行うことができることを理解されたい。
【００１６】
Ｉ．はじめに
幅広い多数のマルチメディアアプリケーションは、ビデオストリーム内の位置を信頼可能に識別するための頑強な技術を必要とする。いくつかの状況では、フレーム番号または埋め込みタイムコードなどのメタデータは、位置を決定するために十分である。しかし、頻繁に、ビデオストリームへの修正はこのメタデータを変更し、メタデータを役に立たなくする。例として、商業テレビは一般に、広告の挿入および削除、フォーマット変換および時間圧縮などの修正を経験する。
【００１７】
本明細書で説明するビデオ位置識別プロセスおよびシステムは、コンテンツベースのビデオタイムラインを使用して、ビデオストリーム内の位置を識別するための頑強な技術を含む。コンテンツベースのビデオタイムラインは、ビデオコンテンツから抽出された低次元ビデオシグネチャの順序付きシーケンスからなる。これらのシグネチャは統計技術（カラーヒストグラムなど）に基づいていない。その代わりに、シグネチャはビデオストリームのフレーム内の空間特性を活用する。各シグネチャは、単一のフレームイメージの小型の表現であり、これは、これを他のフレームイメージから最良に区別するために選択される。１０個から１００個までのシグネチャの連続するシーケンスにおいて、ビデオストリーム内の位置を一意に識別することができる。シグネチャは非常に識別的であり、ビデオにおいて実行することができる修正の多数の一般的な形式に対して頑強である。本明細書で説明するビデオ位置識別プロセスおよびシステムは効率的であり、リアルタイムで実行することができる。
【００１８】
ＩＩ．全体的な概要
本明細書で説明する本発明をどのように実施することができるかの一実施例として、以下の実施例を提供する。以下の実施態様は、それにおいて本発明を使用することができるいくつかの方法の１つにすぎないことに留意されたい。図１は、アノテーションシステムに組み込まれた、本明細書で開示するビデオ位置識別プロセスおよびシステムの全体的な概要を示すブロック図であり、例示のためにのみ示す。一般に、アノテーションシステム１００により、第１のユーザは、アノテーションを第１のビデオに基づいて作成し、このアノテーションを第２のユーザに送信し、第１のユーザによって作成されたアノテーションを第２のビデオ内に配置することができる。これは、第１のビデオが第２のビデオとは著しく異なる可能性があるとしても、当てはまる。
【００１９】
具体的には、図１を参照すると、ソースビデオ１０５は、複数のフレーム（フレーム（１）からフレーム（Ｎ）まで）を含む。このソースビデオは、２つの異なるアウトレット(outlet)から放送されており、これらはすなわち、ＮＴＳＣフォーマットで放送する第１の放送局１１０、およびＰＡＬフォーマットで放送する第２の放送局１１５である。例えば、これらの２つの放送局１１０、１１５を２つの異なるテレビネットワークにして、一方は米国に位置し（ＮＴＳＣフォーマットを使用）、一方はヨーロッパに位置する（ＰＡＬフォーマットを使用）ようにすることができる。異なるコマーシャルがソースビデオ１０５に追加される。ＮＴＳＣフォーマット放送局１１０は第１のセットのコマーシャル１２０をソースビデオ１０５に追加する。この第１のセットのコマーシャル１２０は、規格および地方の視聴者の好みに合わせて調整される。同様に、第２のセットのコマーシャル１２５がＰＡＬフォーマット放送局１１５によってソースビデオ１０５に追加される。
【００２０】
図１のように、これは結果として、（ソースビデオ＋第１のセットのコマーシャル）１３０、および（ソースビデオ＋第２のセットのコマーシャル）１３５となる。コマーシャルを追加することによって得られた、結果として生じるビデオ１３０、１３５が、異なる長さである可能性があることに留意されたい。さらに、第１の結果として生じるビデオ１３０は、第１の種類の圧縮１４０によって圧縮され、第２の結果として生じるビデオ１３５は、第２の種類の圧縮１４５によって圧縮される。例えば、第１の種類の圧縮１４０を、Ｉｎｄｅｏというビデオ圧縮／復元（コーデック）技術とし、第２の種類の圧縮１４５を、ＭＰＥＧ４という、競合するコーデック技術にしてもよい。
【００２１】
ソースビデオ１０５の最終的な放送バージョンは、誰が放送を行っているかに応じて異なる。すなわち、第１のビデオ放送１５０は、異なるコマーシャルが追加されること、異なる種類の圧縮が使用されること、異なる放送フォーマット、および異なる放送雑音のために、第２のビデオ放送１５５とは異なる。したがって、ユーザ＃１がＮＴＳＣフォーマット放送局１１０によって送信された第１のビデオ放送１５０を見るときに見るものは、ユーザ＃２がＰＡＬフォーマット放送局１１５によって送信された第２のビデオ放送１５５を見るときに見るものとは異なる。
【００２２】
ユーザ＃１は、自分のビデオ位置識別システム１６０を使用して、第１のビデオ放送上のアノテーション１６５において生成する。例として、第１のビデオ放送１５０は、背景に複数の家がある浜辺のシーンを含むことができる。ユーザ＃１は、第１のビデオ放送１５０にアノテーションを付けて、背景にある家の１つの周りに円を描いて、これがユーザ＃１の「海岸の家」であることを示すようにすることができる。このアノテーションがユーザ＃２に、ナロー通信チャネル(narrow communication channel)を介して送信される。例として、このナロー通信チャネルには、電子メール、携帯電話、インターネットおよびインスタントメッセージング（ＩＭ）サービスが含まれる。ユーザ＃２は、自分のビデオ位置識別システム１７０を使用して、このアノテーションを、ソースビデオ１０５の第２のビデオ放送１５５バージョン内の正しい位置に調和(match up)させる。これにより、対応するアノテーションを有する第２のビデオ放送１７５が作成される。したがって、本明細書で説明するビデオ位置識別システムおよびプロセスを使用して、ユーザ＃１はユーザ＃２に、ソースビデオ１０５の自分のバージョンの自分のアノテーションを送信することができ、ユーザ＃２はそのアノテーションを、ソースビデオ１０５の自分のバージョン内の正しい位置に調和させることができる。
【００２３】
図２は、図１に例示するビデオ位置識別プロセスおよびシステムの全体的な概観を例示するブロック図である。この全体的な概観において使用するシナリオは、異なるマーケットで見せられる民放テレビ番組である。民放テレビ番組は、実際に視聴者のテレビセットに表示される前に、驚くべき数の微妙な修正を受ける。したがって、フレーム番号およびタイムオフセットは、ビデオストリーム内で位置を識別する手段として信頼できないことが多い。
【００２４】
図２に示すビデオ位置識別プロセスおよびシステム２００は、多数の一般的な修正に対して頑強であり、さらに軽量かつ安価である。ユーザ＃１用のビデオ位置識別システム１６０およびユーザ＃２用のビデオ位置識別システム１７０は、図２に示すビデオ位置識別システム２００の特定の実施態様であることに留意されたい。一般に、ビデオ位置識別プロセスおよびシステム２００により、元のテレビ番組２１０の第１のバージョン２０５内の位置を、元のテレビ番組２１０の第２のバージョン２１５内の位置とマッチさせることができる。このプロセスおよびシステム２００は多数の種類の修正に対して頑強であるので、第１のバージョン２０５および第２のバージョン２１５が互いに異なる場合でさえ、図２の場合のように、これが当てはまる。
【００２５】
詳細には、図２に例示するように、第１のバージョン２０５は、元のテレビ番組２１０を取り、第１のセットのコマーシャル２２０を追加することによって作成される。この第１のバージョン２０５はＮＢＣ２２５によってＮＴＳＣ放送フォーマットで放送され、Ｉｎｄｅｏ圧縮２３０を使用して圧縮される。放送された第１のバージョン２０５は、シアトルのJaneによって、彼女のテレビセット上で受信される。
【００２６】
その間に、第２のバージョン２１５が、元のテレビ番組２１０を取り、第２のセットのコマーシャル２３５を追加することによって作成される。この第２のバージョン２１５はＣＢＳ２４０によってＰＡＬ放送フォーマットで放送され、ＭＰＥＧ４圧縮２４５を使用して圧縮される。放送された第２のバージョン２１５は、パリのJohnによって、彼のテレビセット上で受信される。
【００２７】
Janeが第１のバージョン２０５を受信するとき、Janeは、第１のバージョン２０５に望むようにアノテーションを付けることができる。図２は、Janeが、第１のバージョン２０５のあるフレーム（図２では最終フレームとして表す）内のオブジェクトのまわりに円２５０を作成することによって、第１のバージョン２０５にアノテーションを付けていることを例示する。このアノテーション化は、アノテーション付きの第１のバージョン２５５を作成する。一つのアノテーションが例示されているが、通常は、アノテーション付きの第１のバージョン２５５内には、多数のアノテーションが存在するようになることに留意されたい。アノテーション付きの第１のバージョン２５５内に含まれたアノテーション２６０は、電子メールによってシアトルにいるJaneからパリにいるJohnに送信される。Johnは、アノテーション２６０を受信し、本明細書で開示するビデオ位置識別プロセスおよびシステム２００を使用して、自分の第２のバージョン２１５内で、Janeが彼女の第１のバージョン２０５内で作成したアノテーション２６０の位置を回復することができる。これにより、パリにいるJohnのために、アノテーション付きの第２のバージョン２６５が生成され、これには、各フレーム内のオブジェクトを囲む円２５０を含んだJaneのアノテーション２６０が含まれる。
【００２８】
ＩＩＩ．システムの概観およびコンポーネントの詳細
ビデオ位置識別プロセスおよびシステム２００によりJaneがアノテーション２６０を作成できるようにし、JohnがJaneのアノテーション２６０についての正確な位置を回復できるようにするプロセスの概要を、以下で論じる。最初に、システムの概要を提供する。次に、システム内の各コンポーネントの詳細を論じる。
【００２９】
図３Ａ〜Ｃは、図２に示すビデオ位置識別システム２００の概観を例示する。ビデオ位置識別システム２００は、コンピューティングデバイス上で動作するように設計され、その詳細を以下で説明する。一般に、ビデオ位置識別システム２００は、ユーザがビデオの第１のバージョン内でアノテーションを作成できるようにし、ビデオの第１のバージョンおよび第２のバージョンのコンテンツに基づいてシグネチャを生成し、次いでこれらのシグネチャをマッチさせて、第１のバージョン内でアノテーションが付けられた位置を第２のバージョン内で回復する。シグネチャはビデオ自体のコンテンツから生成され、メタデータ（フレーム番号およびタイムオフセットなど）は無視される。ビデオコンテンツは、コンテンツベースであるいかなる情報を含むこともでき、これは例として、ビデオフレーム内のビジュアルコンテンツ、いずれかのオーディオトラックビデオフレームコンテンツ、ビデオと同期化されたオーディオコンテンツ、およびクローズドキャプショニング（ｃｌｏｓｅｄ  ｃａｐｔｉｏｎｉｎｇ）情報などである。シグネチャは、これらの種類のビデオフレームコンテンツを使用して生成される。
【００３０】
図３Ａは、ビデオの第１のバージョン３２０についてのシグネチャを生成するための、ビデオ位置識別システム２００の概観を例示するブロック図である。ビデオ位置識別システム２００は、第１の場所にある第１のコンピューティングデバイス３００上に存在する。例えば、図２の例を使用すると、第１の場所はシアトルにいるJaneのコンピュータ上になるであろう。ジェーンは、ビデオの第１のバージョン３２０にアノテーションを付け、関心範囲(a range of interest)３３０がこれらのアノテーションによって定義される。関心範囲３３０は、第１のバージョン３２０の少なくとも一部であり、少なくとも１つのフレームを含む。シグネチャ生成および抽出モジュール３１０は、ビデオの第１のバージョン３２０を処理し、関心範囲内のビデオフレームのコンテンツに基づいて、第１のシグネチャシーケンス３４０を生成する。第１のシグネチャシーケンス３４０は、第１のバージョン３２０から生成および抽出することができるシグネチャの全部の一部のみである。すなわち、第１のシグネチャシーケンスは、関心範囲３３０内に含まれたフレームのみのコンテンツを表現するシグネチャを含む。代替実施形態では、前処理ステップを使用して、すべてのシグネチャを第１のバージョン３２０から抽出して、関心範囲が識別されるたびにこれらのシグネチャを抽出しなくてもよいようにすることができる。
【００３１】
図３Ｂは、ビデオの第２のバージョン３５０についてのシグネチャを生成するための、ビデオ位置識別システム２００の概観を例示するブロック図である。ビデオ位置識別システム２００は、第２の場所にある第２のコンピューティングデバイス３０５上に存在する。再度、図２の例を使用すると、第２の場所はパリにいるJohnのコンピュータ上になるであろう。Johnのコンピュータ上のビデオ位置識別システム２００は、Johnが見るビデオの第２のバージョン３５０を入力する。シグネチャ生成および抽出モジュール３１０は、第２のバージョン３５０を処理し、フレームコンテンツに基づいて、第２のシグネチャシーケンス３６０を生成する。第２のシグネチャシーケンスは、第２のバージョン３５０のフレームコンテンツから生成および抽出することができるすべてのシグネチャを含む。
【００３２】
図３Ｃは、図３ＡおよびＢで生成されたシグネチャをマッチさせるための、ビデオ位置識別システムの概観を例示するブロック図である。このシグネチャマッチングは、第２のコンピューティングデバイス３０５上で、あるいは、再度図２の例を使用すると、パリにいるJohnのコンピュータ上で起こる。Johnは第１のシグネチャシーケンス３４０をJaneから受信する。第１のバージョン３２０からのビデオコンテンツに基づいてジェーンのコンピュータ上で作成された第１のシグネチャシーケンス３４０、および、第２のバージョン３５０からのビデオコンテンツに基づいてジョンのコンピュータ上で作成された第２のシグネチャシーケンス３６０は、シグネチャマッチングモジュール３７０によって処理される。この結果は、回復された関心範囲３８０であり、これは、Janeが第１のバージョン３２０内で作成したアノテーションの位置を、Johnによって見られるビデオの第２のバージョン３５０内で回復する。
【００３３】
ビデオ位置識別システム２００は、異なるバージョンのビデオ間で位置を識別するための信頼可能かつ頑強なシステムを提供する。実際には、このシステムはいかなる素材（アノテーションなど）をもこれらの位置へ「固定」(アンカー:anchor)する。これにより、素材を、類似であるが厳密に同じではないコンテンツを有する可能性のある異なるバージョン間で渡すことができる。図３Ａ〜Ｃに示すビデオ位置識別システム２００のコンポーネントを、これから詳細に論じる。
【００３４】
ビデオ位置識別システム２００は、シグネチャ生成および抽出モジュール３１０およびシグネチャマッチングモジュール３７０を含む。シグネチャ生成および抽出モジュール３１０はビデオフレームを入力し、シグネチャを、これらのフレームのコンテンツに基づいて抽出する。これらのシグネチャは、ビデオフレーム上に含まれたコンテンツを表す。
【００３５】
図４は、シグネチャ生成および抽出モジュール３１０の詳細を例示するブロック図である。一般に、シグネチャ生成および抽出モジュール３１０は、ビデオフレーム４００を入力し、ビデオフレーム４００を処理してシグネチャ４１０を生成する。シグネチャは、フレーム内に含まれたコンテンツを表す。シグネチャ生成および抽出モジュール３１０は、グレースケールコンバータ４２０、ダウンサンプルモジュール４３０および中間しきい値(メディアンスレシホールド:median threshold)ビットマップコンバータ４４０を含む。シグネチャ生成および抽出モジュール３１０はさらに、形態的クリーニング（モーフォロジカルクリーニング:morphological cleaning）モジュール４５０、オプショナルの（破線により示す）ショートシグネチャ(short signature)モジュール４６０、およびシグネチャパッケージングモジュール４７０を含む。
【００３６】
グレースケールコンバータ４２０は、各フレームの現在の解像度で、ビデオフレーム４００をグレースケール（白から黒までの間を様々な濃さの灰色で表現すること）へ変換し、グレースケールフレームを生成する。ダウンサンプルモジュール４３０が使用されて、より低い解像度のグレースケールフレームが作成されるまで、グレースケールフレームがダウンサンプルされる。一実施形態では、ダウンサンプルモジュール４３０は、標準のＳＩＦＦビデオフレームサイズから３０×４０フレームサイズまで、ガウスピラミッド（Goussian pyramid）を構築することによってダウンサンプルする。結果として生じる低解像度グレースケールフレームは、中間しきい値ビットマップコンバータ４４０に送信される。中間しきい値ビットマップコンバータ４４０が使用されて、低解像度グレースケールフレームが、０および１からなるビットマップ（またはフレームの０／１ビットマップバージョン）に変換される。中間しきい値ビットマップコンバータ４４０は、フレームの中間グレーレベルをしきい値として使用して、各フレームについての０および１の数がほぼ等しいことを保証する。これは、シグネチャについての最大の識別力を提供する。
【００３７】
中間しきい値ビットマップコンバータ４４０による処理の後に残されるものは、ほぼ等しい数の０および１を含むシグネチャフレームである。このシグネチャフレームがモーフォロジカルクリーニングモジュール４５０によって処理されて、シグネチャフレーム内に存在する可能性のある雑音が低減および平滑化される。モーフォロジカルクリーニングモジュール４５０は反復モジュールであり、それによりカーネル調整が実行されて、０および１のバランスが維持される。モーフォロジカルクリーニングモジュール４５０はイニシャルの、または「ロング」シグネチャ(”long”signature)を各フレームについて生成する。ダウンサンプリングモジュール４３０の結果が３０×４０フレームイメージである一実施形態では、「ロング」シグネチャは３０×４０＝１２００ビットである。
【００３８】
いくつかの状況では、以下で説明するように、ロングシグネチャは必要とされず、ショートシグネチャで十分となる。ショートシグネチャの使用により、ビデオ位置識別システム２００の速度が増す。オプショナルのモジュールはショートシグネチャモジュール４６０であり、これはロングシグネチャを、より少数のビットを含むショートシグネチャにダウンサンプルする。例えば、ショートシグネチャは、ロングシグネチャに含まれる可能性のある１２００ビットではなく、１２８ビットを含む可能性がある。以下で詳細に説明するように、ショートシグネチャモジュール４６０は２つの異なる技術を使用して、ロングシグネチャに適用されるマスクを生成することができる。一般に、ショートシグネチャモジュール４６０は次元削減を実行して、ロングシグネチャ内のビットの数を減らしてショートシグネチャを作成する。次に、ロングおよびショートシグネチャが、ビデオの別のバージョンとマッチングをとるために、所望の場所に送信される。
【００３９】
例として、限定ではなく、これらのシグネチャを、シグネチャパッケージングモジュール４７０を使用して送信することができる。シグネチャパッケージングモジュール４７０は、各シグネチャを他のアイテム（関心範囲３３０、または、関心範囲３３０に関連付けられたいずれかのアノテーションなど）と共にパッケージし、これらの各アイテムを含む単一のファイルを生成する。次いで、このシグネチャファイルを別の場所に送信することができる。例えば、図２を参照すると、シグネチャファイルは、シグネチャシーケンスおよびアノテーションを含むことができ、これらは電子メールによってシアトルのJaneからパリのJohnに送信される。パリのJohnによって受信されるとすぐに、送信されたシグネチャシーケンスは、Johnのコンピューティングデバイス３０５上のビデオ位置識別システム２００で処理される。
【００４０】
図５は、図４に示すモーフォロジカルクリーニングモジュール４５０の詳細なブロック図である。一般に、モーフォロジカルクリーニングモジュール４５０は、フレームの０／１ビットマップバージョン５００を入力し、フレームのロングシグネチャ５１０を出力する。モーフォロジカルクリーニングモジュール４５０は、ｋ-フィルタジェネレータ５２０、ｋ-フィルタ適用モジュール５３０、バイナリバランスモジュール５４０および更新ピクセル査定(アセスメント:assessment)モジュール５５０を含む。
【００４１】
ｋ-フィルタジェネレータ５２０は、フレームの０／１ビットマップバージョン５００内のピクセルを処理するk-フィルタに対する適切なしきい値を生成する。k-フィルタ適用モジュール５３０は、ｋ-フィルタをフレームシグネチャ内の各ピクセルに適用し、すでに１に等しい隣接ピクセルの数に応じて、その出力値を「０」または「１」に設定する。バイナリバランスモジュール５４０は、前の２つのモジュール５２０、５３０を反復し続け、０の数および１の数がほぼ等しくなるまでｋ-フィルタしきい値を上下に調整する。更新ピクセル査定モジュール５５０は、各反復についての更新ピクセルの数を、その数が更新ピクセルしきい値より下がるまで連続的に監視する。これが起こると、更新ピクセル査定モジュール５５０は、反復プロセスを終了し、ロングシグネチャ５１０を出力する。モーフォロジカルクリーニングモジュール４５０の正味の効果は、きめの細かい細部を入力ビットマップシグネチャから除去すること、および、シグネチャが生成される元のフレームイメージの全体の空間詳細を取り込む修正「ロング」シグネチャを生成することである。
【００４２】
図６ＡおよびＢは、図４に示すショートシグネチャモジュール４６０の２つの実施形態を例示する。一般に、ショートシグネチャモジュール４６０は、ロングシグネチャ５１０を入力し、ロングシグネチャ５１０をダウンサンプルするためにサンプリングマスクを作成し、そのサンプリングマスクを適用してショートシグネチャ６００を作成する。どのようにサンプリングマスクが決定されるかにかかわらず、サンプリングマスクは、対応するショートシグネチャを構成するために使用される各ロングシグネチャからビットを選択するために使用される。
【００４３】
サンプリングマスクを作成するための２つの実施形態を、次に論じる。図６Ａは、図４に示すショートシグネチャモジュール４６０の第１の実施形態を例示する詳細なブロック図である。この第１の実施形態では、ショートシグネチャモジュール４６０は、ランダムマスクを生成してシグネチャのすべてをサンプリングするランダムマスクモジュール６１０を含む。ショートシグネチャモジュール４６０はロングシグネチャ５１０を入力し、ランダムマスクモジュール６１０はロングシグネチャ５１０を処理して、ショートシグネチャ６００を作成する。図６Ｂは、図４に示すショートシグネチャモジュール４６０の第２の実施形態を例示する詳細なブロック図である。この第２の実施形態では、ショートシグネチャモジュール４６０は、修正主成分分析（ＰＣＡ）モジュール６２０を含む。修正主成分分析モジュール６２０は、ロングシグネチャ５１０のヒストグラムを検査して、最も識別的であるビットを決定する。ショートシグネチャモジュール４６０は、ロングシグネチャ５１０を入力し、ロングシグネチャ５１０は、修正ＰＣＡモジュール６２０によって処理される。この結果は、ショートシグネチャ６００である。
【００４４】
図７は、図６Ｂに示す、修正ＰＣＡモジュール６２０のさらなる詳細を例示するブロック図である。修正ＰＣＡモジュール６２０は、ヒストグラムジェネレータ７００、ビット計算モジュール７１０、識別決定モジュール７２０およびマスク適用モジュール７３０を含む。ヒストグラムジェネレータ７００は、ロングシグネチャ５１０内に含まれたあらゆるビットを検査するヒストグラムを生成する。次いで、ビット計算モジュール７１０は、各ビットを検査し、ロングシグネチャのシーケンス内で、各ビットが「０」である回数、および各ビットが「１」である回数を計算する。識別決定モジュール７２０は、「０」に等しい回数の約５０％、および「１」に等しい回数の約５０％である、ビットを選択する。これらのビットは最も識別的なビットとして定義される。次いで、マスクが、最も識別的なビットを使用して生成される。次いで、マスク適用モジュール７３０は、このマスクをロングシグネチャ５１０に適用して、ショートシグネチャ６００を生成する。
【００４５】
図８は、図３Ｃに示すシグネチャマッチングモジュール３７０の詳細を例示するブロック図である。一般に、シグネチャマッチングモジュール３７０は、２つのシグネチャシーケンスを入力し、シグネチャをそれらの正しい位置にマッチさせる。具体的には、シグネチャマッチングモジュール３７０は、第１のシグネチャシーケンス３４０および第２のシグネチャシーケンス３６０を入力する。第１のシグネチャシーケンス３４０は、ビデオの第１のバージョン内のコンテンツのある一意の領域（または関心範囲）を表現する。第２のシグネチャシーケンス３６０は、ビデオの第２のバージョン全体のコンテンツを表現する。
【００４６】
次いで、第１のシグネチャシーケンス３４０の少なくとも一部が第２のシグネチャシーケンス３６０と比較されて、マッチがあるかどうかが決定される。マッチがない場合、これは、関心範囲３３０がビデオの第２のバージョンから除去されていることを意味する。マッチがある場合、回復された関心範囲３８０が出力として送信される。シグネチャマッチングモジュール３７０によって行われたマッチに応じて、回復された関心範囲３８０は、元の関心範囲３３０の全部または一部である可能性があることに留意されたい。例えば、関心範囲３３０が１００個のフレームを含み、ビデオの第２のバージョンが、元の１００個のフレームのうち５０個を除去している場合、シグネチャマッチングモジュール３７０は、５０個のフレームが除去されていること、および、残りの５０個のフレームが回復された関心範囲３８０内に含まれることを決定できるようになる。第１のシグネチャシーケンス３４０を第２のシグネチャシーケンス３６０にマッチさせることによって、ビデオ位置識別システム２００は、ビデオの第２のバージョン内のどこに第１のシグネチャシーケンス３４０が属するかを決定することができる。したがって、ビデオ位置識別システム２００は、ビデオの第２のバージョン内で、ビデオの第１のバージョン内の関心範囲３３０に対応する位置を識別する。
【００４７】
シグネチャマッチングモジュール３７０は、連続シグネチャモジュール８３０、マッチングしきい値モジュール８４０、距離比較モジュール８５０および信頼性モジュール８６０を含む。連続シグネチャモジュール８３０は、連続シグネチャのシーケンスを取る。マッチングしきい値モジュール８４０は、使用されるべきマッチングしきい値を決定する。距離比較モジュール８５０は、連続シグネチャのシーケンスおよびマッチングしきい値を使用し、２つのシグネチャを比較する。距離がマッチングしきい値を超える場合、２つのシグネチャはマッチしない。そうでない場合、これらのシグネチャはマッチする。信頼性モジュール８６０は、これらのシグネチャが信頼できるかどうかを決定する。信頼できない場合、マッチ（またはマッチの欠如）は疑わしい。
【００４８】
図９は、図８に示す信頼性モジュール８６０の詳細なブロック図である。一般に、信頼性モジュール８６０は、シグネチャフレーム９００を入力し、信頼可能な結果のために必要とされたシグネチャの数９１０およびフレーム信頼性９１５を出力する。信頼性モジュール８６０は、グレー値ヒストグラムジェネレータ９２０、ヒストグラム分析モジュール９３０およびシグネチャシーケンス決定モジュール９４０を含む。グレー値ヒストグラムジェネレータ９２０は、シグネチャフレーム９００内の各ピクセルのグレー値を提供し、これらの値のヒストグラムを生成する。ヒストグラム分析モジュール９３０はこのヒストグラムを分析して、シグネチャフレーム９００の安定性を決定する。ヒストグラムの形状が単一の「スパイク」(spike)形状である場合、シグネチャフレーム９００は、それほど信用可能ではない。スパイク形状は、イメージ内のすべてのピクセルが類似の輝度(intensity)を有することを示し、これは、イメージ内に多くの識別可能な詳細がないことを意味する。
【００４９】
シグネチャについての計算された信頼性に基づいて、シグネチャシーケンス決定モジュール９４０は、頑強なマッチのために必要となる、シグネチャシーケンスの最も有益な部分を決定する。好ましい実施形態では、シグネチャ全体が使用される。しかし、代替実施形態では、シグネチャシーケンス決定モジュール９４０は、シグネチャの一部のみ（フレームの右上の４分の１など）が必要と決定してもよい。一般に、より低い信頼性のエリアでは、シグネチャシーケンスは、頑強なマッチを提供するために、より多数のシグネチャを含むことを要する。ヒストグラムがより広げられると、シグネチャはより対照的な細部を含む。非常に対照的な細部は、より信頼できるシグネチャが、それが生成された元のフレームイメージを識別することを意味する。
【００５０】
ＩＶ．オペレーションの概観
上述のビデオ位置識別システム２００は、ビデオ位置識別プロセスを使用して、ビデオ内の位置を信頼可能かつ頑強に識別する。図１０は、図３Ａ〜Ｃに示すビデオ位置識別システム２００のオペレーションを例示する全体的な流れ図である。このプロセスは、関心範囲をビデオの第１のバージョン内で選択することによって開始する（ボックス１０００）。この関心範囲を、ユーザによって、あるいは自動システムによって選択することができる。関心範囲は少なくとも１つのフレームを含むが、通常はずっと多くを含む。加えて、情報（アノテーションなど）が関心範囲内で作成される。次に、第１のシグネチャシーケンスが、関心範囲内の１つまたは複数のフレームのコンテンツから生成される（ボックス１０１０）。生成された第１のシグネチャシーケンス（またはビデオアンカー）は、アノテーションを関心範囲に頑強にアンカーする。最後に、第１のシグネチャシーケンスが使用されて、後に、ビデオの第２のバージョンから関心範囲を回復する（ボックス１０２０）。一実施形態では、ビデオの第１のバージョンおよび第２のバージョンは同じビデオであり、関心範囲は、同じビデオについて後に回復されることになる。もう１つのより典型的な実施形態では、ビデオの２つのバージョンは異なり、回復された関心範囲は、第１のシグネチャシーケンスが生成されたビデオの第１のバージョン上にない。このビデオ位置識別プロセスは、ビデオへの修正を切り抜けることができ、この修正は、フレームの除去または追加、および、関心範囲内の各フレームが何らかの形で変更されること（各フレームの色のスペクトルの変化、圧縮パラメータの変化、または雑音の追加など）などである。加えて、このプロセスは、フレームのスケーリングおよび少量のクロッピングを切り抜けることができる。
【００５１】
図１１は、図１０に示すビデオ位置識別システムのオペレーションの追加の詳細を例示する流れ図である。このプロセスは、第１の場所で、ビデオの第１のバージョンのフレームの一部のコンテンツからアノテーション及び第１のシグネチャシーケンスを生成することから開始される（ボックス１１００）。次に、第１のシグネチャシーケンスおよびアノテーションが第２の場所に送信される（ボックス１１２０）。アノテーションがビデオの特定の部分についてのものである場合、いくつかのシグネチャのみを抽出する必要があることに留意されたい。すべてのシグネチャを生成または抽出する必要はない。これは、第１の場所でのユーザが、ビデオのどの部分がユーザに関心を起こさせるかを選択しているからである。次いで、ビデオのその部分についてのシグネチャが生成され、これはビデオのその部分についての一意の識別としての機能を果たす。
【００５２】
次に、第２の場所で、ビデオの第２のバージョン内のすべてのフレームのコンテンツから第２のシグネチャシーケンスが生成される（ボックス１１３０）。ある意味では、このプロセスはビデオの第２のバージョンの地理的な図形(topographical map)を生成する。これは、第２のシグネチャシーケンスが第２のビデオバージョンの異なる特徴を決定するからである。最後に、第１のシグネチャシーケンスおよび第２のシグネチャシーケンスが、第２の場所でマッチされる。これにより、関心範囲およびアノテーションの位置がビデオの第２のバージョン内で回復される（ボックス１１４０）。このマッチングにより、アノテーションを第２のビデオバージョン内の正しい位置に配置することができる。マッチングは、第２のビデオバージョンの始めで開始すること、および第１のシグネチャシーケンスを第２のシグネチャシーケンス内の各シグネチャと比較することによって、実行される。このプロセスで、所望のシグネチャ（およびしたがって、所望の場所）が第２のビデオバージョン内に含まれる場合、これを発見することができる。
【００５３】
Ｖ．実施例のオペレーションの詳細
次に、ビデオ位置識別プロセスの一実施形態を詳細に説明する。以下の実施例は単に本発明の一実施形態であり、例示のためにのみ提示されることに留意されたい。この考察はビデオ位置識別プロセスの２つの主なプロセスに分割され、これはすなわち、（ａ）シグネチャ生成および抽出（または特徴抽出）、および（ｂ）シグネチャマッチングである。
【００５４】
（シグネチャ生成および抽出）
図１２は、実施例においてシグネチャを生成するために使用されるシグネチャ生成および抽出（または特徴抽出）プロセスの詳細を例示する。シグネチャは、各ビデオフレーム内に含まれたコンテンツの表現である。シグネチャは、統計技術（カラーヒストグラムなど）に基づいておらず、むしろビデオフレーム内の空間特性を活用する。一般に、この実施例におけるシグネチャ生成および抽出プロセスは、連続的に各ビデオフレームを以下のように単純化する。すなわち、原寸カラーイメージから白黒のイメージへ、白黒の原寸から小さいサイズのイメージへ下げるように、小さいサイズのイメージから１および０のビットマップへ、ノイズを有する小さい０／１ビットマップから、雑音のない平滑化された小さい０／１ビットマップへと、単純化する。
【００５５】
具体的には、図１２を参照すると、この実施例のシグネチャ生成および抽出プロセスは、フレームシーケンス内の各フレームを４：３のアスペクト比に正規化することによって開始し、いかなる色情報をも廃棄した（丸１）。次に、結果として生じるイメージがダウンサンプルされて、３０×４０グレースケールイメージが生成された（丸２）。３０×４０というサイズは、これが標準サイズのビデオからのダウンサンプリングの終点であるために選択された。
【００５６】
次に、中間しきい値化が実行されて、０／１ビットマップが生成された（丸３）。この実施例では、「１」のピクセル値＝白、「０」＝黒である。しかし、このピクセル値の割り当ては重要ではなく、ピクセル値を容易に反転させておくことができた。中間しきい値化は、ダウンサンプルされたイメージの中間グレー値を決定することによって実行された。この中間グレー値がしきい値として定義された。したがって、しきい値（すなわち、中間グレー値）より上のあらゆるものが「１」であり、しきい値（すなわち、中間グレー値）より下のあらゆるものが「０」であった。中間グレー値が各フレームについて選択されたことに留意されたい。したがって、このしきい値は各フレームについて変わる可能性があった。
【００５７】
各フレームについてのしきい値の中間グレー値を選択することは重要であり、これは、単一のしきい値がすべてのフレームについて選択された場合、フレームのいくつかはそれほど識別的ではなく、他のフレームはより大きい識別力を有したであろうからである。一般に、最大の識別力は、１および０の数がほぼ等しいときに発生する。したがって、フレームが等しい数の１および０を有することに近づくほど、そのフレームが最大の識別力を有することに近い。これは、フレーム内の１および０のバランスが、フレームの最も変化のある情報を与えるからである。例えば、フレームが大部分は０を含んだ場合、フレームは大部分が黒となり（「０」が黒に等しく設定されたと仮定する）、情報をほとんど含まなくなる。同様に、フレームが大部分は１を含んだ場合、フレームは大部分が白となり、情報をほとんど含まなくなる。
【００５８】
残されたものは、ほぼ等しい数の１および０を含んだシグネチャフレームであった。しかし、典型的に、フレームに対する多くの雑音アスペクトもあった。例えば、黒のピクセルによって囲まれた白のピクセルがあり、これらは「ごま塩」効果(”salt and pepper” effect)を与えた。これは識別的であるが、過度に識別的である。すなわち、このイメージは、特定のフレーム内で発生していたものに関して過剰の細部を与えた。
【００５９】
雑音を平滑化するために、モーフォロジカルクリーニングが使用されてイメージが「クリーン」にされ、ライン詳細アーチファクト（line detail artifacts）が除去された（丸４）。モーフォロジカルクリーニング（「カーネルフィルタリング」または略して「ｋフィルタリング」）が０／１ビットマップにおいて実行されたが、これは、しきい値化が典型的でない雑音を導入する可能性があるからである。この実施例では、３×３「ｋ-フィルタ」が適用された。この３×３ｋ-フィルタは、ｋより多いピクセルが１である場合、ピクセル出力を１に設定し、そうでない場合は０に設定する。これは０／１ビットマップ全体に渡って数回、反復的に実行された。各反復の後、モーフォロジカルクリーニングについて使用されたカーネル（ｋ）が調整された。最初に、ｋ＝４．５であり、これは、反復が３×３メジアンフィルタにより開始したことを意味した。反復中に、１の数が減少した場合、次の反復においてより多くの１を生じるためにｋの値が減少された。同様に、１の数が増えた場合、ｋの値が増加された。これは、１および０のバランスが維持されたことを保証し、したがって、各シグネチャについての最大識別力を維持した。
【００６０】
ｋ-フィルタリングは、所与の反復において更新されたピクセルの数があるエプシロン(epsilon)より低くなったとき、終了された。この実施例では、エプシロンの値は５であった。実際には、この終了は一般に５回から８回の反復の後に発生する。この結果は１２００ビットの０／１ビットマップであり、これは「ロング」シグネチャであった。
【００６１】
この実施例は２つの異なる技術を使用してロングシグネチャをダウンサンプルし、ショートシグネチャを作成した。この実施例では、ロングシグネチャは１２００ビットを含み、ショートシグネチャは１２８ビットを含む。使用された第１のダウンサンプル技術は、ランダムマスク技術であった。使用された単一のランダムマスクは、シグネチャのすべてをサンプリングしていた。ランダムマスク技術は、異なるシグネチャの各々についての異なるランダムな集まりのビットを使用することを伴わないことに留意されたい。その代わりに、異なるシグネチャの各々からの同じランダムな集まりのビットが取られる。例えば、ランダムマスクが、第１、第５および第７ビットを取るように示す場合、第１、第５および第７ビットがシグネチャのすべてから取られる。
【００６２】
この実施例で使用された第２のダウンサンプル技術は、修正主成分分析（ＰＣＡ）であった。ＰＣＡ技術は多数のデータポイント（この場合、ビデオシグネチャ）を得て、データを特徴付けた主な次元を決定した。具体的には、ＰＣＡは、データについての固有ベクトルおよび対応する固有値を決定することによって実行された。固有ベクトルがどれを有したとしても、最大の固有値が、データを特徴付けるための主要な次元または主成分として選択された。固有ベクトルは、データの平面(plane)を定義する直線である。これは、３次元（３Ｄ）問題から２次元（２Ｄ）問題へと問題を単純化する。これはまた次元削減としても知られる。この実施例では、次元削減が１２００ビット（ロングシグネチャ内のビットの数）から１２８ビット（ショートシグネチャ内のビットの数）へと実行された。
【００６３】
ＰＣＡを実行するための従来の方法は、ビデオからロングフィンガプリントの例のすべてを取り、ＰＣＡをそれらにおいて実行し、すべての固有ベクトルおよびすべての固有値を識別し、次いでそのうちの上位１２８個を選択することである。次いで、これらは１２８ビットであり、これは１２００ビットからショートシグネチャとして選択されるべきである。しかし、このＰＣＡを実行する従来の方法は、計算的に高価である。
【００６４】
その代わりに、この実施例は、本発明で使用された修正ＰＣＡを使用し、ここではロングシグネチャのすべての１２００ビットが検査され、１２００ビンのヒストグラムが生成された。次に、各ビットが「１」であった回数、および、各ビットが「０」であった回数が記録された。その値が回数「１」の半分および回数「０」の半分（すなわち、５０−５０）であることに最も近かった、ロングシグネチャ内のビットが、最も識別的として定義された。最も識別的ということによって、その特定のビットが大部分の情報、より識別的でないビットよりも多くの情報を生じるようになることが、意味される。
【００６５】
ヒストグラムが構築された後、上記の基準に基づいた１２８の最も識別的なビットが決定された。これらの１２８ビットが使用されて、ショートシグネチャについてのマスクが生成された。次いで、マスクがロングシグネチャに適用されて、ロングシグネチャのビットがサンプリングされてショートシグネチャが生成されるようにされた。
【００６６】
他の実施形態には、各ビットについての「分散の頻度」(frequency of variance)の基準が含まれる可能性があることに留意されたい。分散の頻度は、ロングシグネチャのビットの各々がある頻度により変わらなければならないことを意味する。例えば、この分散の頻度の特徴により、あるビットがビデオの最初の５００フレームについて「１」であり、次いで次の５００フレームについて「０」であることが可能でなくなる。
【００６７】
（シグネチャマッチング）
シグネチャがビデオの第１のバージョンおよびビデオの第２のバージョン内で生成された後、ビデオの第２のバージョン内で所望の位置を識別するためにこれらのシグネチャがマッチされなければならない。第１のバージョンのビデオ内である一意の領域（または関心範囲）を識別する第１のシグネチャシーケンスが与えられ、第２のバージョンのビデオの第２のシグネチャシーケンスが与えられると、ビデオ位置識別プロセスは、第２のバージョンのビデオ内の関心領域内で、最初は第１のバージョンのビデオからのものであった位置を回復する。
【００６８】
図１３は、実施例において位置を回復するために使用されるシグネチャマッチングプロセスの詳細を例示する。この実施例では、ユーザは最初にアノテーション（丸１３００によって示す）を、ビデオの第１のバージョン内のローカルの関心範囲から作成した。次いで、第１のシグネチャシーケンスが上述のように生成および抽出された（丸１）。次いで、アノテーション情報が第１のシグネチャシーケンスと共にアノテーションコンシューマに送信された（丸２）。第２のシグネチャシーケンスが上述のように、第２のバージョンのビデオ、またはビデオのコンシューマのバージョンの全長から生成および抽出された（丸３）。シグネチャマッチングプロセスが使用されて、第１のシグネチャシーケンスが第２のシグネチャシーケンス内のシグネチャの各々と、最も近いマッチが発見されるまで比較された（丸４）。
【００６９】
シグネチャマッチングは、第１のシグネチャシーケンスを取り、先頭から開始する第２のバージョンのビデオに添ってマッチさせ、これらを比較することによって実行された。この実施例では、１０個の連続シグネチャが第１のシグネチャシーケンスから得られ、第２のシグネチャシーケンス内の各シグネチャと、第２のバージョンのビデオの始めから開始して、比較された。以下で詳細に説明するように、２つのシグネチャがほぼマッチングしきい値より下であったとき、マッチが発生した。これが起こった時、このシーケンスのシグネチャがマッチングとして定義された。第２のシグネチャシーケンス内で、マッチが発生した所に対応する位置が、第２のバージョンのビデオ内の所望の位置であった。すなわち、第２のバージョンのビデオ内の所望の位置は、ユーザによって第１のバージョンのビデオ内で選択された位置または関心範囲に対応した。
【００７０】
この実施例では、シグネチャシーケンス内の連続シグネチャの数が１０に等しかったが、他の実施態様では、この数は異なる可能性がある。例えば、シーケンス数を１０より大きくすることができる（例えば、１００または１０００）。シーケンス数は、サーチされている情報の量を決定する。例えば、１０個のシグネチャのシーケンスが選択され、第２のビデオがサーチされる場合、１００のシーケンス数が選択された場合よりも少量の情報がサーチされている。より少数のシグネチャがサーチされていると、サーチはより柔軟であるが、入手可能な詳細情報はほとんどない。他方では、シーケンス数が１０００に等しく、１０００個のシグネチャのブロックが使用される場合、はるかにより大量の情報およびより大きい詳細がある。
【００７１】
（マッチングおよび信頼性）
以下で説明するように、マッチの信頼性が高いとき、シーケンス数を低くして、より小さいブロックのシグネチャがシグネチャマッチングプロセスで使用されるようにすることができる。これは詳細をほとんど提供しないが、より大きい柔軟性を提供する。しかし、マッチの信頼性が低い場合、シーケンス数をより高くしてより大きい詳細を提供し、マッチの信頼性を向上させることができる。
【００７２】
この実施例では、２つのシグネチャがマッチしたかどうかを決定するために、各フレームのロングシグネチャの間で異なったビットの数がカウントされた。これは、ハミング距離として知られる。ハミング距離がマッチングしきい値より上であった場合、これらのシグネチャはマッチしなかった。他方では、ハミング距離がマッチングしきい値より下であった場合、これらの２つのシグネチャはマッチした。実証的テストは、１２５ビットより近いフレームは同じであるが、１２５ビットより多く離れているフレームは異なることを示した。
【００７３】
マッチングの実行に加えて、この実施例は、本発明の信頼性の特徴を使用して、各フレームについての信頼性スコアを計算した。この信頼性スコアはフレーム内の分散の量を反映する。高い分散がある場合、フレームのシグネチャを伴うことにおけるマッチはより信頼可能である。
【００７４】
図１４は、実施例において使用される信頼性の特徴を例示するグラフである。図１４を参照すると、２つのビデオが使用され、これらを人は同じビデオとして識別するが、これらは、異なるコマーシャルおよび異なる圧縮技術を含むなど、微妙な方法で異なっていた。ビデオの第１のバージョンは野球の試合であり、ビデオのみを含んだ。ビデオの第２のバージョンはこの野球の試合であったが、最初の部分が一連のコマーシャルで置き換えられていた。第１および第２のビデオの全体の長さは等しかった。最初のＮ個のフレームはマッチしなかったが、Ｎ個のフレームの後のフレームのすべては等しく、互いに対応した。第１のバージョンのビデオからの第１のシグネチャシーケンス、および、第２のバージョンのビデオからの第２のシグネチャシーケンスはパラライズされ(parallized)、ペアにされた。最初の１２００個程度のフレームについて、ペアでの距離の線（暗い実線であり、フレームの対応するペアの間の距離である）は、しきい値の線（薄い実線、またはハミング距離しきい値）より上の長い距離であった。この場合、ペアでの距離の線がしきい値の線より上であったとき、シグネチャのペアはマッチしなかった。同様に、ペアでの距離の線がしきい値の線より下であったとき、シグネチャのペアはマッチした。対応するペアがマッチするとき、それらの距離は常にゼロとは限らなかったことに留意されたい。これは、ビデオの２つのバージョンが、ある圧縮比または他の追加の雑音により異なるからである。
【００７５】
図１４のグラフ上の破線は、信頼性の線である。信頼性の線は、信頼可能なシグネチャの測度および指標である。図１４を参照すると、グラフの始めのフレームで、信頼性の線が下降する。同様に、ほぼフレーム５１００および５３００で、信頼性の線が著しく下落する。これらの下落は、シグネチャが信頼可能でなかったことを示す。誤ったマッチまたは非マッチがあるのが、これらのポイントである。例えば、ほぼフレーム１で偽陽性のマッチがあり、ここでは、実際には２つのシグネチャがマッチしなかったときにマッチが指示された。このミスは、信頼性の線によって示すように、信頼性が低かったために行われた。フレーム５１００および５３００で、偽陰性がある。ここで、２つのシグネチャの間のマッチは、実験の設計によってこれらがマッチしなかったことが知られるとしても、指示された。この誤りは、これらのフレームのシグネチャの信頼性が低かったために行われた。
【００７６】
したがって信頼性は、測度であり、それにより、近くにおいて比較的より多くの情報（すなわち、より多くのシグネチャ）が、領域がビデオ内のどこに属するかについての決定を行うために必要とされると言うことができる。すなわち、シーケンス内で有するシグネチャの信頼性が低い場合、ビデオ内でそれを位置付けるために、比較的より長いシーケンスが必要とされる。シグネチャがすべて高い信頼性を有する場合、比較的短いシグネチャシーケンスを使用することができ、マッチをなお正確に識別できるようになる。したがって、より低い信頼性のエリアでは、より大きい連続シグネチャシーケンスを使用することができる（１０個の連続シグネチャの代わりに、約１００個の連続シグネチャを使用するなど）。
【００７７】
ＶＩ．例示的オペレーティング環境
上述のビデオ位置識別プロセスおよびシステムは、コンピューティング環境内で動作するように設計される。以下の考察では、ビデオ位置識別プロセスおよびシステムを実施することができる適切なコンピューティング環境の簡潔で全体的な説明を提供するつもりである。
【００７８】
図１５は、ビデオ位置識別プロセスおよびシステムを実施することができる適切なコンピューティングシステム環境１５００の一実施例を例示する。コンピューティングシステム環境１５００は、適切なコンピューティング環境の一実施例に過ぎず、本発明の使用または機能性の範囲についてのいかなる限定をも示唆するように意図されない。コンピューティング環境１５００は、例示的オペレーティング環境１５００において例示したコンポーネントのいずれか１つまたは組合せに関係するいかなる依存性も要件も有するものとして解釈されるべきではない。
【００７９】
ビデオ位置識別プロセスおよびシステムは、多数の他の汎用または専用コンピューティングシステム環境または構成と共に動作可能である。ビデオ位置識別プロセスおよびシステムと共に使用するために適切である可能性のある周知のコンピューティングシステム、環境および／または構成の例には、それだけに限定されないが、パーソナルコンピュータ、サーバコンピュータ、携帯電話およびＰＤＡなどのハンドヘルド、ラップトップもしくはモバイルコンピュータまたは通信デバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブルなコンシューマエレクトロニクス、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれる。
【００８０】
ビデオ位置識別プロセスを一般に、プログラムモジュールなど、コンピュータによって実行されるコンピュータ実行可能命令に関連して説明することができる。一般に、プログラムモジュールには、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれ、これらは特定のタスクを実行するか、あるいは特定の抽象データ型を実施する。本発明をまた分散コンピューティング環境において実施することもでき、ここでは、通信ネットワークを通じてリンクされるリモート処理デバイスによってタスクが実行される。分散コンピューティング環境では、プログラムモジュールは、メモリストレージデバイスを含む、ローカルおよびリモートのコンピュータストレージメディアに位置することができる。図１５を参照すると、ビデオ位置識別プロセスおよびシステムを実施するための例示的システムは、コンピュータ１５１０の形態における汎用コンピューティングデバイスを含む。
【００８１】
コンピュータ１５１０のコンポーネントは、それだけに限定されないが、処理装置１５２０、システムメモリ１５３０、および、システムメモリを含む様々なシステムコンポーネントを処理装置１５２０に結合するシステムバス１５２１を含むことができる。システムバス１５２１は、いくつかの種類のバス構造のいずれかにすることができ、これには、様々なバスアーキテクチャのいずれかを使用する、メモリバスまたはメモリコントローラ、周辺バスおよびローカルバスが含まれる。例として、限定ではなく、このようなアーキテクチャには、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）ローカルバス、およびメザニンバスとしても知られるＰｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスが含まれる。
【００８２】
コンピュータ１５１０は通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１５１０によってアクセスすることができるいかなる使用可能なメディアにすることもでき、これには、揮発性および不揮発性のメディア、リムーバブルおよび非リムーバブルのメディアが含まれる。例として、限定ではなく、コンピュータ可読媒体は、コンピュータストレージメディアおよび通信メディアを含むことができる。コンピュータストレージメディアは、揮発性および不揮発性、リムーバブルおよび非リムーバブルのメディアを含み、これらはコンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータなど、情報の格納のためのいずれかの方法または技術において実施される。
【００８３】
コンピュータストレージメディアには、それだけに限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または、所望の情報を格納するために使用することができ、コンピュータ１５１０によってアクセスすることができる他のいかなるメディアもが含まれる。通信メディアは通常、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを、搬送波もしくは他の移送メカニズムなどの変調データ信号において実施し、いかなる情報配信メディアをも含む。
【００８４】
「変調データ信号」という用語は、信号における情報を符号化するような方法でその特性の１つまたは複数が設定または変更されている信号を意味する。例として、限定ではなく、通信メディアには、有線ネットワークまたは直接有線接続などの有線メディア、ならびに、音響、ＲＦ、赤外線および他の無線メディアなどの無線メディアが含まれる。上記のいずれの組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。
【００８５】
システムメモリ１５３０は、揮発性および／または不揮発性メモリの形態におけるコンピュータストレージメディアを含み、これは読み取り専用メモリ（ＲＯＭ）１５３１およびランダムアクセスメモリ（ＲＡＭ）１５３２などである。基本入出力システム１５３３（ＢＩＯＳ）は、起動中など、コンピュータ１５１０内の複数の要素の間で情報を転送する助けとなる基本ルーチンを含み、通常はＲＯＭ１５３１に格納される。ＲＡＭ１５３２は通常、処理装置１５２０によって即時アクセス可能および／または現在動作中であるデータおよび／またはプログラムモジュールを含む。例として、限定ではなく、図１５は、オペレーティングシステム１５３４、アプリケーションプログラム１５３５、他のプログラムモジュール１５３６およびプログラムデータ１５３７を例示する。
【００８６】
コンピュータ１５１０はまた、他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージメディアも含むことができる。例としてのみ、図１５は、非リムーバブル、不揮発性の磁気メディアに対する読み書きを行うハードディスクドライブ１５４１、リムーバブル、不揮発性磁気ディスク１５５２に対する読み書きを行う磁気ディスクドライブ１５５１、および、ＣＤ  ＲＯＭまたは他の光メディアなど、リムーバブル、不揮発性の光ディスク１５５６に対する読み書きを行う光ディスクドライブ１５５５を例示する。
【００８７】
例示的オペレーティング環境で使用することができる他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージメディアには、それだけに限定されないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどが含まれる。ハードディスクドライブ１５４１は通常システムバス１５２１に、インターフェース１５４０などの非リムーバブルメモリインターフェースを通じて接続され、磁気ディスクドライブ１５５１および光ディスクドライブ１５５５は通常システムバス１５２１に、インターフェース１５５０などのリムーバブルメモリインターフェースによって接続される。
【００８８】
上述し、図１５に例示したドライブおよびそれらの関連付けられたコンピュータストレージメディアは、コンピュータ１５１０用のコンピュータ可読命令、データ構造、プログラムモジュールおよび他のデータのストレージを提供する。図１５では、例えば、ハードディスクドライブ１５４１が、オペレーティングシステム１５４４、アプリケーションプログラム１５４５、他のプログラムモジュール１５４６およびプログラムデータ１５４７を格納するものとして例示される。これらのコンポーネントを、オペレーティングシステム１５３４、アプリケーションプログラム１５３５、他のプログラムモジュール１５３６およびプログラムデータ１５３７と同じものにも異なるものにもすることができることに留意されたい。オペレーティングシステム１５４４、アプリケーションプログラム１５４５、他のプログラムモジュール１５４６およびプログラムデータ１５４７にはここで異なる番号が与えられて、最低でも、それらが異なるコピーであることが例示される。ユーザはコマンドおよび情報をコンピュータ１５１０へ、キーボード１５６２、および、一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティングデバイス１５６１などの入力デバイスを通じて、入力することができる。
【００８９】
他の入力デバイス（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナ、ラジオ受信器、または、テレビもしくは放送ビデオ受信器などが含まれる可能性がある。これらおよび他の入力デバイスがしばしば、システムバス１５２１に結合されるユーザ入力インターフェース１５６０を通じて処理装置１５２０に接続されるが、これを例えば、パラレルポート、ゲームポートまたはユニバーサルシリアルバス（ＵＳＢ）など、他のインターフェースおよびバス構造によって接続することができる。モニタ１５９１または他の種類の表示デバイスもまたシステムバス１５２１へ、ビデオインターフェース１５９０などのインターフェースを介して接続される。モニタ１５９１に加えて、コンピュータはまた、スピーカ１５９７およびプリンタ１５９６など、出力周辺インターフェース１５９５を通じて接続することができる他の周辺出力デバイスを含むこともできる。
【００９０】
コンピュータ１５１０はネットワーク環境において、リモートコンピュータ１５８０など、１つまたは複数のリモートコンピュータへの論理接続を使用して動作することができる。リモートコンピュータ１５８０は、パーソナルコンピュータ、サーバー、ルーター、ネットワークＰＣ、ピアデバイスまたは他の共通ネットワークノードにすることができ、通常は、コンピュータ１５１０に関連して上述した要素の多数またはすべてを含むが、メモリストレージデバイス１５８１のみを図１５に例示した。図１５に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）１５７１およびワイドエリアネットワーク（ＷＡＮ）１５７３を含むが、他のネットワークも含むことができる。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネットおよびインターネットにおいて一般的である。
【００９１】
ＬＡＮネットワーキング環境において使用するとき、コンピュータ１５１０がＬＡＮ１５７１へ、ネットワークインターフェースまたはアダプタ１５７０を通じて接続される。ＷＡＮネットワーキング環境において使用するとき、コンピュータ１５１０は通常、モデム１５７２、またはインターネットなどのＷＡＮ１５７３を介して通信を確立するための他の手段を含む。モデム１５７２を内部または外部にすることができ、ユーザ入力インターフェース１５６０または他の適切なメカニズムを介してシステムバス１５２１に接続することができる。ネットワーク環境では、コンピュータ１５１０に関連して示したプログラムモジュールまたはその一部を、リモートメモリストレージデバイスに格納することができる。例として、限定ではなく、図１５はリモートアプリケーションプログラム１５８５をメモリデバイス１５８１上に存在するものとして例示する。図示のネットワーク接続は例示的であり、複数のコンピュータの間で通信リンクを確立する他の手段を使用できることは理解されよう。
【００９２】
本発明の前述の説明は、例示および説明のために提示されている。これは網羅的であるように、あるいは、本発明を開示された正確な形態に限定するように意図されない。多数の修正および変形形態は上記の教示に照らして可能である。本発明の範囲はこの本発明の詳細な説明によって限定されないが、むしろ本明細書に付属の特許請求の範囲によって限定されるように意図される。
【図面の簡単な説明】
【００９３】
【図１】アノテーションシステムに組み込まれた、本明細書で開示するビデオ位置識別プロセスおよびシステムの全体的な概観を例示するブロック図である。
【図２】図１に示すビデオ位置識別プロセスおよびシステムの全体的な概観を例示するブロック図である。
【図３Ａ】ビデオの第１のバージョンについてのシグネチャを生成するための、図１および２に示すビデオ位置識別システムの概観を例示するブロック図である。
【図３Ｂ】ビデオの第２のバージョンについてのシグネチャを生成するための、図１および２に示すビデオ位置識別システムの概観を例示するブロック図である。
【図３Ｃ】図３ＡおよびＢで生成されたシグネチャをマッチさせるためのビデオ位置識別システムの概観を例示するブロック図である。
【図４】図３ＡおよびＢに示すシグネチャ生成および抽出モジュールの詳細を例示するブロック図である。
【図５】図４に示すモーフォロジカルクリーニングモジュール４５０の詳細なブロック図である。
【図６Ａ】図４に示すショートシグネチャモジュールの第１の実施形態を例示する詳細なブロック図である。
【図６Ｂ】図４に示すショートシグネチャモジュールの第２の実施形態を例示する詳細なブロック図である。
【図７】図６Ｂに示す、修正ＰＣＡモジュールのさらなる詳細を例示する詳細なブロック図である。
【図８】図３Ｃに示すシグネチャマッチングモジュールの詳細を例示するブロック図である。
【図９】図８に示す信頼性モジュールの詳細なブロック図である。
【図１０】図３Ａ〜Ｃに示すビデオ位置識別システムのオペレーションを例示する全体的な流れ図である。
【図１１】図１０に示すビデオ位置識別システムのオペレーションの追加の詳細を例示する流れ図である。
【図１２】実施例においてシグネチャを生成するために使用されるシグネチャ生成および抽出（または特徴抽出）プロセスの詳細を例示する図である。
【図１３】実施例において位置を回復するために使用されるシグネチャマッチングプロセスの詳細を例示する図である。
【図１４】実施例において使用される信頼性の特徴を例示するグラフである。
【図１５】ビデオ位置識別プロセスおよびシステムを実施することができる、適切なコンピューティングシステム環境の一実施例を例示する図である。
【符号の説明】
【００９４】
２００  ビデオ位置識別システム
３００  第１のコンピューティングデバイス
３０５  第２のコンピューティングデバイス
３１０  シグネチャ生成および抽出モジュール
３２０  ビデオの第１のバージョン
３３０  関心範囲
３４０  第１のシグネチャシーケンス
３５０  ビデオの第２のバージョン
３６０  第２のシグネチャシーケンス
３７０  シグネチャマッチングモジュール
３８０  回復された関心範囲
４００  ビデオフレーム
４１０  シグネチャ
４２０  グレースケールコンバータ
４３０  ダウンサンプルモジュール
４４０  中間しきい値ビットマップコンバータ
４５０  モーフォロジカルクリーニングモジュール
４６０  ショートシグネチャモジュール
４７０  シグネチャパッケージングモジュール
５００  フレームの０／１ビットマップバージョン
５１０  ロングシグネチャ
５２０  ｋ-フィルタジェネレータ
５３０  ｋ-フィルタ適用モジュール
５４０  バイナリバランスモジュール
５５０  更新ピクセル査定モジュール
６００  ショートシグネチャ
６１０  ランダムマスクモジュール
６２０  修正主成分分析（ＰＣＡ）モジュール
７００  ヒストグラムジェネレータ
７１０  ビット計算モジュール
７２０  識別決定モジュール
７３０  マスク適用モジュール
８３０  連続シグネチャモジュール
８４０  マッチングしきい値モジュール
８５０  距離比較モジュール
８６０  信頼性モジュール
９００  シグネチャフレーム
９１０  信頼可能な結果のために必要とされたシグネチャの数
９１５  フレーム信頼性
９２０  グレー値ヒストグラムジェネレータ
９３０  ヒストグラム分析モジュール
９４０  シグネチャシーケンス決定モジュール
【図１】
2004357302.tif 000003
【図３Ａ】
2004357302.tif 000004
【図３Ｂ】
2004357302.tif 000005
【図３Ｃ】
2004357302.tif 000006
【図４】
2004357302.tif 000007
【図５】
2004357302.tif 000008
【図６Ａ】
2004357302.tif 000009
【図６Ｂ】
2004357302.tif 000010
【図７】
2004357302.tif 000011
【図８】
2004357302.tif 000012
【図９】
2004357302.tif 000013
【図１０】
2004357302.tif 000014
【図１１】
2004357302.tif 000015
【図１４】
2004357302.tif 000016
【図１５】
2004357302.tif 000017
【図２】
2004357302.tif 000018
【図１２】
2004357302.tif 000019
【図１３】
2004357302.tif 000020