(57)【要約】【課題】本方法は、映像の未知の内容を要約する。【解決手段】最初に、映像の低レベルの特徴が選択される。その後、その映像は低レベルの特徴に従ってセグメントに区分される。セグメントは互いに素なクラスタにグループ化され、各クラスタは類似のセグメントを含む。クラスタは低レベルの特徴に従ってラベルを付され、クラスタを特徴付けるパラメータが割り当てられる。ラベルの中の高レベルのパターンが見つけられ、これらのパターンを用いて、映像からフレームが抽出され、映像の未知の内容の、内容に適応した要約が形成される。
2006508565.tif 000002
【特許請求の範囲】
【請求項１】
映像の未知の内容を要約する方法であって、
前記映像の低レベルの特徴を選択するステップと、
前記映像を前記低レベルの特徴に従ってセグメントに区分するステップと、
前記セグメントを複数の互いに素なクラスタにグループ化するステップであって、前記クラスタがそれぞれ類似のセグメントを含む、グループ化するステップと、
前記低レベルの特徴に従って前記複数のクラスタにラベルを付けるステップと、
前記ラベルの中の高レベルのパターンを見い出すステップと、
前記高レベルのパターンに従って前記映像からフレームを抽出し、前記映像の未知の内容の、内容に適応した要約を形成するステップと
を含む、映像の未知の内容を要約する方法。
【請求項２】
前記要約は共通のパターンおよび共通でないパターンの組み合わせに基づく
請求項１記載の映像の未知の内容を要約する方法。
【請求項３】
前記映像の内容の製作形式は未知である
請求項１記載の映像の未知の内容を要約する方法。
【請求項４】
前記映像は視覚および可聴データを含む
請求項１記載の映像の未知の内容を要約する方法。
【請求項５】
前記低レベルの特徴は、モーションアクティビティ、色、テクスチャ、オーディオ、意味的記述子およびそれらの組み合わせからなるグループから選択される
請求項１記載の映像の未知の内容を要約する方法。
【請求項６】
前記映像の前記選択された低レベルの特徴に従って前記映像から時系列データを生成するステップと、
前記時系列データの自己相関をとり、前記類似のセグメントを判定するステップと
をさらに含む請求項１記載の映像の未知の内容を要約する方法。
【請求項７】
前記時系列データを平滑化するステップ
をさらに含む請求項６記載の映像の未知の内容を要約する方法。
【請求項８】
前記時系列データを重み付けするステップ
をさらに含む請求項６記載の映像の未知の内容を要約する方法。
【請求項９】
前記複数のクラスタを関連付けて、前記高レベルのパターンを推測するステップ
をさらに含む請求項１記載の映像の未知の内容を要約する方法。
【請求項１０】
全ての類似のセグメントが複数の時間分解能において見つけられる
請求項１記載の映像の未知の内容を要約する方法。
【請求項１１】
点横断距離マトリクスにおいて前記時系列データの自己相関をとり、前記セグメントの類似度を指示する点横断距離を測定するステップ
をさらに含む請求項６記載の映像の未知の内容を要約する方法。
【請求項１２】
前記点横断距離は、前記点横断距離マトリクスの概ね対角線によって表される
請求項１１記載の映像の未知の内容を要約する方法。
【請求項１３】
前記時系列データをタイムワーピングして、前記類似のセグメントを見い出すステップ
をさらに含む請求項６記載の映像の未知の内容を要約する方法。
【請求項１４】
前記タイムワーピングはダイナミックプログラミングによって実行される
請求項１３記載の映像の未知の内容を要約する方法。
【請求項１５】
時間に関して前記ラベルの相関をとるステップ
をさらに含む請求項１記載の映像の未知の内容を要約する方法。
【請求項１６】
前記時間相関は同時である
請求項１５記載の映像の未知の内容を要約する方法。
【請求項１７】
前記ラベルの発生の条件および結果を生成し、前記高レベルのパターンを発見するステップ
をさらに含む請求項１記載の映像の未知の内容を要約する方法。
【請求項１８】
強い関連は共通のパターンおよび共通でないパターンに対応する
請求項９記載の映像の未知の内容を要約する方法。
【請求項１９】
前記グループ化は、
重なり合うセグメントが同一の重なりを有するか、重なりがないように、前記重なり合うセグメントを分割するステップ
をさらに含む請求項１記載の映像の未知の内容を要約する方法。
【請求項２０】
各クラスタにパラメータを割り当てるステップをさらに含み、
前記クラスタパラメータは、クラスタのコンパクトさ、クラスタ内のセグメントの数、フレーム単位で測定されるクラスタ内のセグメントの全長、および前記映像内の前記セグメントの広がりを指示するためのセグメントの最も近い点間の平均距離を含む
請求項１記載の映像の未知の内容を要約する方法。
【請求項２１】
コスト関数を評価し、前記要約の必要とされる長さを求めるステップ
をさらに含む請求項１記載の映像の未知の内容を要約する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は包括的にはコンピュータ化された映像処理に関し、より詳細には、映像内容を要約するための方法およびシステムに関する。
【背景技術】
【０００２】
データマイニングは、大規模なデータベースおよびインターネットから情報を抽出する。データマイニングは、市場データ、金融データ、センサデータおよび生物学的データの分析に適用されてきた。データマイニングは、既知のパターンを得るためにデータが探索されるパターンマッチングと混同されるべきではない。
【０００３】
基本的には、データマイニングは、データ内の、「関心がある」が、予めわかっていないパターンを発見する。関心のあるパターンは、通常、ある特定のパターンの再出現率に関して定義される。データマイニングは、所定のパターンを全く仮定しないので、監視なし学習と呼ばれることも度々である。
【０００４】
データマイニングは、大量のデータから、ルール、傾向、規則性および相関を導出する。多くの場合に、データマイニングは、人工知能（ＡＩ）、記憶に基づく類推（ＭＢＲ）、相関ルール生成、決定木（ＤＴ）、ニューラル分析、統計分析、クラスタリングおよび時系列分析に基づく。
【０００５】
クラスタリングは、データ内の関連する情報からなる同種のグループを識別する。従来技術のクラスタリングは、データ間の関係が既にわかっているものと仮定する。クラスタリングは、統計、パターン認識および機械学習において広範に研究されてきた。クラスタリングの応用形態の例には、市場分析のための顧客のセグメンテーション、および読み取られたデータ内のシグナルデータベースのサブカテゴリの特定が含まれる。
【０００６】
クラスタリング技法は、分割技法および階層技法に大きく分類できる。分割クラスタリングは、各クラスタ内のデータが、異なるクラスタ内のデータとよりも互いに類似性が高くなるように、データをＫ個のクラスタに分類する。Ｋの値は、ユーザによって指定することができるか、あるいはクラスタリング判定基準を最小限に抑えるように反復的に求めることができる。
【０００７】
階層クラスタリングは、枝分かれを構成する一連の区分である。集積的階層クラスタリングは、データを初期クラスタに入れて、その後、全てのデータが１つの大きなクラスタに入るまで、初期クラスタを併合して、徐々により大きなクラスタを形成していく。分割型階層クラスタリングは、全てのデータが１つのクラスタ内にある状態で開始し、そのクラスタをより小さなクラスタに細分していくことより、その過程を逆に実施する。たとえば、Jain等著「Algorithms for Clustering Data」（Prentice Hall, 1988）、Piramuthu等著「Comparison of SOM neutral network and hierarchical clustering methods」（European Journal of Operational Research, 93 (2): 402-417, September 1996）、Michaud「Four clustering techniques」（FGCS Journal, Special Issue on Data Mining, 1997）およびZait等著「A Comparative study of clustering methods」（FGCS Journal, Special Issue on Data Mining, 1997）を参照されたい。
【０００８】
大部分のデータマイニング方法は、入力データの次元数を小さくする。高次元のデータ空間において形成されるクラスタは、高次元のデータ空間内のあらゆる場所において予想される点の平均密度が低いので、意味のあるクラスタである可能性が小さい。データの次元数を小さくするための既知の技法は、主成分分析（ＰＣＡ）、要因分析、特異値分解（ＳＶＤ）およびウェーブレットを含む。カルーネン−レーベ展開としても知られている主成分分析は、データ属性の偏差を説明する低次元の表現を見つけるのに対して、要因分析は、データ属性間の相関を見つける。Jain等著「Algorithms for feature selection: An evaluation, Technical report」（Department of Computer Science, Michigan State University, East Lansing, Mich., 1996）は、画像分析のための技法を記載する。
【０００９】
消費者購買パターンの分析のために用いられる一般的なデータマイニング方法は、自明でない関連性あるいは相関性のルールを特定することである。自明な関連性の一例は、粉ミルクを購入する消費者が同時におむつも購入することである。しかしながら、１９９２年に、夕方の時間帯にはビールとおむつが同時に購入されることが多いことが発見された。そのような関連性は、自明でない関連性の良い例である。標準的には、ビールは、通常は粉ミルクに相当するとは見なされないので、おむつとビールとは強い関連性のある購入品目（アイテム）として関連付けられないであろう。そのような手法はマーケット・バスケット分析とも呼ばれている。
【００１０】
関連性は、以下のように定義される。たとえば、データベースあるいはオペレーションのように、１組のｎ個のアイテムＩ１，．．．，Ｉｎと、ｎ個のアイテムの部分集合を選択するトランザクションとが存在する場合には、２つのアイテムＩｉとＩｊとの間の関連性は、アイテムＩｉとＩｊの両方が選択されて部分集合に入れられる任意のトランザクションのためのルールＲと定義される。ルールＲの条件は、アイテムＩｉの発生と定義される。ルールＲの結果は、アイテムＩｊの発生と定義される。ルールＲのサポートは、両方のアイテムＩｉおよびＩｊを有するトランザクションの比率と定義される。ルールＲの組み合わせは、同じトランザクションにおける両方のアイテムＩｉおよびＩｊの発生と定義される。アイテムＲの信頼度は、組み合わせのサポートと条件のサポートとの比と定義される。最後に、ルールＲの改善度は、条件Ｉｉのサポートと結果Ｉｊのサポートとの積よりも大きな、ルールのサポートの比と定義される。
【００１１】
ある関連性のサポートおよび信頼度の両方が高いときには、その関連性は強い。たとえば、食料品店の売買取引（トランザクション）の場合に、大部分の売買取引が１つの品目として牛乳を含むので、牛乳は、他の全ての販売される品目との強い相関があり、サポートは高い。しかしながら、挨拶状などのいくつかの品目の場合に、これらは、購入される頻度が低いので、信頼度は低い。
【００１２】
最後に、改善度が１より小さいことは、その条件が、組み合わせそのものの生の確率を用いる場合よりも、その組み合わせの予測が正確でないことを示すので、関連性の改善度も同じように強くなる必要がある。したがって、ルールのサポートおよび信頼度が高い場合であっても、対応する改善度が１以下である場合には、そのルールは、単なる見込みに勝る利点を提供しない。以下の説明では、消費者の「品目」の代わりに、映像特徴の「ラベルを付されたクラスタ」に対する関連性の使用が記載される。
【００１３】
時系列分析は、データ値をその時間的な分離の関数として関連付ける。たとえば、時系列分析を用いて、株価、売上高、気候データおよび心電図分析のパターンが発見されてきた。一般的に、時系列を生成した、根底をなす確定的過程が存在すること、およびその過程がランダムではないことが仮定される。しかしながら、現実世界の現象の時系列データは、多くの場合に、非確定的データ、たとえば不可避のランダムノイズと混合されている。
【００１４】
通常は、ユークリッド距離のような類似度の測度、あるいはそのある偏差を用いて時系列が比較される。しかしながら、ユークリッド距離測定は、信頼性が低い傾向がある。よりロバスト性のある類似度測度は、動的時間ワーピング法（ＤＴＷ）に基づく。Berndt等著「Finding patterns in time series: a dynamic programming approach」（Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, Menlo Park, CA. pp. 229-248, 1966）を参照されたい。ＤＴＷは、時間軸を選択的に伸長および圧縮することにより時系列データを揃えようとする。
【００１５】
これまで、大部分のデータマイニング技法は、テキストデータ、数値データおよび線形（一次元）シグナルに焦点を合わせてきた。しかしながら、現在では、空間および時間の両次元を有する多次元の画像、映画および映像の形態の莫大な情報を容易に入手することができる。
【００１６】
いくつかの従来技術による技法は、映像上で初歩的なタイプの内容分析を実行する。最も一般的な手法は、１組のラベルを付されたサンプルを用いてエキスパートシステムをトレーニングするので、それらの技法は、監視あり学習に基づいており、監視なしデータマイニングではない。Xu等著「Algorithms and Systems for Segmentation and Structure Analysis in Soccer Video」（IEEE International Conference on Multimedia and Expo, Tokyo, Japan, Aug. 22-25, 2001）、２００１年４月２０日にXu他によって出願された米国特許出願第０９／８３９，９２４号「Method and System for High-Level Structure Analysis and Event Detection in Domain Specific Videos」およびNaphade等著「Probabilistic multimedia objects (multijects): A novel approach to indexing and retrieval in multimedia systems」（Proceedings of the fifth IEEE International Conference on Image Processing, vol. 3, pp.536-540, 1998）を参照されたい。
【００１７】
従来技術の監視なし映像分析技法は、主に内容中立である。たとえば、特定されたセグメントからのキーフレームを選択することにより、映像が要約されている。その場合に、セグメントは、シーンあるいは「ショット」変化、たとえば次第に小さくなる音量あるいは音量の突然の変化を検出することにより決定される。そのシーンが何を示すかは無関係である。選択された特定のフレームは、通常、ある判定基準に従って、そのショット内の他のフレームを代表するフレームである。他の技法は、カメラのアングルあるいは視野の変化、たとえばズーミングを利用する。そのような内容中立技法は、ある程度の成功を収めているが、意味的に満足のいく性能を得るためには、内容固有の技法で補う必要がある。
【００１８】
しかしながら、一般的には、内容に基づく映像マイニングに関連する問題は、あまり理解されていない。
【００１９】
たとえば、よく知られている分類および回帰木（ＣＡＲＴ）が、大幅に変更することなく映像マイニングに適用できるか否かははっきりしない。ＣＡＲＴ法は、独立変数をデータセットの小さなグループに分割し、ある定数関数をその小さなデータセットに当てはめる。カテゴリ木では、その定数関数は、有限の小さな１組の値、たとえばイエスおよびノー、あるいは低、中および高をとる関数である。回帰木では、その応答の平均値が、小さな連結したデータセットに当てはめられる。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
それゆえ、あるシーン、すなわちカメラによって撮影された一連のフレーム、つまり映像から読み取られる多次元時系列データをマイニングするためのシステムおよび方法を提供することが望ましい。映像マイニングは、編集モデル、ニュース映像の特徴、あるいはスポーツ映像内のパターンのような、定義域および内容の事前モデルが容易に入手できない映像において、関心があるパターンを発見するために特に有用であろう。
【課題を解決するための手段】
【００２１】
本発明による方法は映像の未知の内容を要約する。最初に、その映像の低レベルの特徴が選択される。その後、その映像は、低レベルの特徴に従って、セグメントに区分される。
【００２２】
そのセグメントは、それぞれ類似のセグメントを含む、互いに素なクラスタにグループ化される。そのクラスタは低レベルの特徴に従ってラベルを付され、そのクラスタを特徴付けるパラメータが割り当てられる。
【００２３】
そのラベルの中の高レベルのパターンが見い出され、これらのパターンを用いて、その映像からフレームが抽出されて、映像の未知の内容の、内容に適応した要約が形成される。
【発明を実施するための最良の形態】
【００２４】
図１は、本発明による映像マイニング方法１００のためのステップを示す。本発明は、監視ビデオあるいはホームビデオのような、その内容のパターンが予めわかっていない映像をマイニングする場合に特に有用である。発見されたパターンは、映像を「盲目的に」要約するために用いることができる。盲目的な要約は、要約されることになる映像の内容あるいはジャンルを知る必要がないことを意味する。本方法は、ニュース放送、スポーツ放送、長編映画などの入念に準備された映像のためにも有用である。したがって、本方法によれば、内容および製作様式において、多様な範囲にわたる映像を盲目的に要約できるようになる。
【００２５】
本発明は、任意の、おそらく未知の内容および製作様式からなる映像１０１で開始する。その映像は、視覚および聴覚データを含む。最初に、その内容の低レベルの特徴１０２が選択される（１１０）。たとえば、一群の特徴は、ＭＰＥＧ−７記述子のような、動きの活発さ、色、音声、質感などによって構成され得る。マイニングは、１つあるいは複数の選択された特徴１０２で実行することができ、各マイニングパスの結果１５２を組み合わせて、入力映像１０１のさらに高いレベルの情報を推測することができる（１６０）。本発明は、選択された特徴を用いて、映像１０１のための時系列２００を生成する。
【００２６】
図２は、動きの活発さに基づくゴルフの試合の映像の時系列２００の一例である。図２は、ゴルフの映像内の動きの活発さのレベルを時間の関数としてプロットしている。時間は、フレーム番号としてｘ軸２０１上に示され、動きの活発さは、以前のフレームから、マクロブロックにおいて動かされたピクセルの平均数としてｙ軸２０２上に示される。生の動きの活発さは、プロット２０３によって示される。動きの活発さデータは、高レベル２１１、中レベル２１２および低レベル２１３の動きの活発さに閾値処理される。
【００２７】
動きの活発さが低い時間が長く続いた後に、動きの活発さの急激な上昇が観測され、図のようなスパイクを有する立ち上がりエッジが示される。ボールが打たれるまで、動きの活発さは、通常非常に低い。ボールが打たれた時点、あるいはその直後に、カメラが素早く動き、ボールを追跡するので、動きの活発さの「立ち上がりエッジ」が現れる。
【００２８】
本発明によれば、映像１０１の一連のフレーム内の動きの活発さが時系列を構成する。映像フレームの色ヒストグラムが別の多次元時系列である。映像内の時系列データは、意味ラベルのようなシンボル値、たとえばＭＰＥＧ−７記述子と、音声信号とを含むことができる。「時系列」という場合に、その系列データがｘ軸、たとえば時間に沿ってある種の順序を有することは理解されたい。空間のような他の系列の順序付けも実現可能であり、本発明は、多次元データの「空間」系列、あるいは他の順序付けされた系列にも同じく適用することができる。当然、空間系列では、全ての経路が多数の空間分解能で存在するであろう。
【００２９】
本発明の方法１００は、その映像の時系列２００、たとえば動きの事例では、高、中あるいは低に基づいて、低レベルの特徴の類似の表現を測定し（１３０）、支配的な青色、緑色あるいは茶色は、別の表現にすることができる。本発明は、「ソフト」マッチングを実現しており、それによれば、小さな差によっては、必ずしも不一致とはしない。本発明は、上記のように、低レベルの特徴１０２をデータ平滑化あるいは閾値処理することにより、これを果たす。多数の特徴が用いられる場合には、時系列データは、重み付けされることができる。たとえば、最終的な結果において、色が動きの活発さよりも大きな重みを与えられることができる。推測１６０における低レベルの特徴間の本発明による結び付きは緩やかであり、それゆえ、その特徴それぞれに対して、個別にデータマイニングが適用され、選択された低レベルの特徴１０２における映像マイニングによって、個別に得られるクラスタリングされたデータ１５１を融合する（１６０）ことにより、より高いレベルのパターン１６１が推測されることが好ましい。
【００３０】
所与の分解能において、類似の対のみを見つける従来技術とは対照的に、本発明のマッチングは、その映像から得られる時系列２００のような大きな時系列において、全ての時間的な分解能で全ての取り得るマッチング対を見つける（１４０）。
【００３１】
時系列Ｓ（ｉ）２００内の全ての時間的なパターン１３０に対してマイニングするために、種々のサイズｗからなる多分解能の窓が必要とされる。
ｗ：Ｓ（１：ｗ），Ｓ（２：ｗ＋１），．．．，Ｓ（Ｎ−ｗ＋１：Ｎ）
【００３２】
多分解能の窓ｗは、明示的には構成されないことに留意されたい。代わりに、本発明の窓ｗは、横断距離マトリクス３００によって暗黙のうちに定義されており、ここで行われるのは、これらの暗黙のうちに定義された窓を見つけることである。これにより、全ての分解能における全ての一致を見つけられるようになる。本発明の暗黙の窓による探索技法が、以下にさらに詳細に記載される。
【００３３】
時系列データ２００間の全ての点横断距離３００が測定され（１３０）、最小距離４００が見つけられ（１４０）、それに応じて映像１０１がクラスタリングされる（１５０）。問題は、多分解能の窓が種々のサイズを有する場合に類似度を如何にして見つけるかである。
【００３４】
図３に示されるように、本発明は、点距離マトリクス３００を用いてこの問題を解決する。サイズｗの２つの窓３０２−３０３の間の距離３０１が以下のように測定される。
【００３５】
【数１】
2006508565.tif 000003
【００３６】
図３は、１つの窓３０１がｘｉ−ｘｉ＋ｗであり、別の窓３０２がｘｊ−ｘｊ＋ｗである例示的な点距離マトリクス３００を示す。線３０１は、式（１）を表す。曲線３１１および３１２は、それぞれ時系列２００を表す。すなわち、同じ時系列がｘ軸およびｙ軸に沿っており、言い換えると、その測定は自己相関をとる。
【００３７】
点距離マトリクス３００は、短い点横断距離の対角線を得るために探索され得る。図３の表現では、距離がグレースケール上に表されており、距離が短いほど明るくなり、それゆえ、全ての距離が０である主対角線は白色になる。なぜなら、その測定が自己相関をとられているためである。
【００３８】
１つの利点として、マトリクス３００は、任意の所与の窓サイズｗには限定されない。それゆえ、短い距離値の全ての取り得る対角線経路を見つけることができる。ただし、ここで言う「短い」は、ある閾値距離値ＴＤよりも短いということである。時間ワーピングが用いられる場合には、その経路は、図３の主対角線３１０に対して、「ほぼ」あるいは概ね対角線にすることができる。
【００３９】
図４に示されるように、本発明は、本発明の映像内容マイニングに適合させたマルチスケール技法、たとえばウェーブレットを用いて時系列をサブサンプリングすることにより、多分解能の分析を実行する。これは、滑らかなマトリクス４００を生成する。本発明の方法は、種々の窓サイズｗにわたって自動的にマッチングし、時系列内の全ての繰返し時間パターン４０１−４０２を明らかにする。
【００４０】
動的時間ワーピング（ＤＴＷ）を用いて、ある特定の限度内で時間が「伸長」および「圧縮」され、異なる時間の長さを有する映像の類似のセグメントを良好に揃えることができる。セグメントは、一連のフレームを意味する。動的プログラミングを用いて、最も一致させることができるセグメントの時間ワーピングを見つけることができる。ＤＴＷは、以下に示される一定の制約の下で、格子内の最適経路を見つける。
（ｉ，ｊ）、１≦ｉ≦Ｎ、１≦ｊ≦Ｍ
ただしＮおよびＭは、２つのセグメントの長さであり、各格子点（ｉ，ｊ）は、それぞれ２つのセグメント内のｉ番目の点とｊ番目の点との間の距離である。
【００４１】
本発明は、動的プログラミングを用いて、点横断距離マトリクス内の点の対間の最小コスト経路を見つける。その経路は、概ね対角線方向である、すなわち主対角線３１０に対して概ね平行であることが望ましい。さらに、その経路は、そのマトリクス内の低い横断距離値を通ることが望ましい。ただし、「低い」は、ある閾値ＴＤによって定義される。これらの経路は、図３および図４における白色あるいはほぼ白色の対角曲線セグメントである。
【００４２】
最小コストに関して１つの取り得る定義は、その経路に沿った横断距離値の平均値である。また本発明は、許可される経路に関してある制約を課しており、すなわち経路５００は、対角線方向の向きを保持する。図５を参照されたい。取り得る１組の制約は、その経路に沿った各ステップにおいて、その経路が、図に示されるように、１つ下に、１つ右に、あるいは対角線方向に動くことができることである。
【００４３】
さらに、図６に示されるように、対角線と、その経路の２つの終点間に描かれる線との間の閾値角がα°未満でなければならない。ただし０≦α≦４５°である。その経路コスト判定基準および制約は、動的プログラミングによって定式化され、点横断距離マトリクス内の２点間の最小コスト有効経路を見つけることができる。
【００４４】
こうして得られる有効経路は、厳密には対角線方向ではない場合であっても、時系列内の２つの対応する部分列の動的時間ワーピングを規定する。それゆえ、本発明は、動的プログラミングを用いることにより、２つの部分列間を良好に一致させるのに適した時間ワーピングを見つけ、かつ横断距離マトリクス内の２点間の最小コスト経路を見つける。
【００４５】
動的プログラミングによって、マトリクス内の所与の２点間の最小コスト経路が見つけられるようになる。本発明は、マトリクス内の全ての取り得る点の対間の最小コスト経路を見つけることを目的にしており、所与の閾値未満のコストを有する経路を選択する。
【００４６】
これを果たすための強引な方法は、取り得る点の対毎に動的プログラミング過程を実行することによる。横断距離マトリクスは対称であり、すなわち時系列のｉ番目のサンプルとｊ番目のサンプルとの間の距離はｊ番目のサンプルとｉ番目のサンプルとの間の距離に等しいので、本発明は、Ｎ２／２点のみが存在し、Ｎ４／４点対が存在する、そのマトリクスの上半分を処理することしか必要としない。それゆえ、処理ステップの数を減らして、本方法の効率を高めることができる。
【００４７】
最初に図６に示されるように、本発明は、対角線と、その経路の２つの終点を通る線との間に、α°未満であるような角度を必要とする。その後、点毎に、対角線６０３から＋α°６０１および−α°６０２の線の間に配置される点に対する最小コスト経路が見つけられる。さらに、本発明は、１つの経路上の全ての点の値が閾値Ｔよりも低くならなければならないという制約を課す。この場合に、本発明は、マトリクス全体を閾値処理して、その閾値よりも大きな１組の点間にある最小コスト経路のみを見つけることができる。
【００４８】
全てのそのような点間の最小コスト経路が見つけられた後に、本発明は、短い経路を互いに近接した終点と併合し、より長い経路にする。また本発明は、あるものが別のものの上位集合である経路も併合する。本発明は、２つの終点間のユークリッド距離がある特定の長さよりも短い経路を削除する。残された１組の経路は、多分解能における映像内の類似の部分列の全ての対を与える。
【００４９】
従来技術では、動的時間ワーピングを用いる類似度（たとえば、動的プログラミングを用いて横断距離マトリクス内の最小コスト経路を見つけることによる）は、より大きな時系列内の所与の時系列パターンを問い合わせるために実施される。Park等著「Efficient search for similar subsequences of different lengths in sequence databases」（International Conference on Data Engineering (ICDE), pp. 23-32, 2000）を参照されたい。
【００５０】
本発明による技法は、別の分析の状況において、２つの系列間の良好な整合を見つけるために用いることもできる。スピーチ分析に関しては、Sakoe等著「Dynamic programming algorithm optimization for spoken word recognition」（IEEE Trans. Acoust., Speech, Signal Process., ASSP 26, pp.43-49, 1978）を、遺伝子およびタンパク質配列(sequence)の分析に関しては、Aach等著「Aligning gene expression time series with time warping algorithms」（Bioinformatics, 17: 495-508, 2001）を参照されたい。しかしながら、それらの方法は、所与の横断距離マトリクス内の所与の始点を有するただ１つの経路を見つけるのに対して、本発明は、全ての経路を見つける。
【００５１】
従来技術では、部分列の自己類似度は、通常、固定された窓サイズｗを用いて、元の系列上でシフトされた窓間の横断距離を計算することによって計算される。Agrawal等著「Efficient Similarity Search in Sequence Databases」（Proc. of the 4th Int'1 Conference on Foundations of Data Organization and Algorithms）および「Lecture Notes in Computer Science」（730, Springer Verlag, p., 69-84）を参照されたい。
【００５２】
横断距離マトリクスの他の従来技術の用途は、ドットプロットの形をとり、その場合に、マトリクス要素は１か０のいずれかであり、それは厳密に一致するか、一致しないかを示す。それらは、定性分析のために、および視覚化ツールとして用いられている。Church等著「Dotplot: A program for exploring self-similarity in millions of lines of text and code」（Journal of Computational and Graphical Statistics, 2(2): 153__174, 1993）を参照されたい。あるいは、それらは、対角線に沿って自己類似領域をセグメント化するために用いられているが、類似の部分列の対を自動的に見つけるためには用いられていない。Jeffry著「An Automatic Method of Finding Topic Boundaries」（Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics, 1994）を参照されたい。本発明の方法は、これらの応用形態のうちの任意の応用形態のために用いられることができる。
【００５３】
複数の短い経路を併合して曲線に、するためにハフ変換を適用することができる。ハフ変換は、マトリクス４００内のある特定の形状の特徴を分離する。それらの特徴の簡単な分析的記述が不可能であるので、本発明は、ハフ変換を用いることができる。１つの利点として、ハフ変換は、特徴境界の記述内の隙間を容認し、データ内のノイズによって比較的影響を及ぼされない。さらに、ハフ変換は、本明細書の事例のように、問題解決のクラスの数が予めわかっていない特徴の包括的な記述を発見するために特に有用である。
【００５４】
本発明においてハフ変換を用いる動機は、入力される距離の特徴がそれぞれ、全体的に一致するパターンへの寄与を示すことである。本発明は、特徴空間を有限の間隔に、あるいはアキュームレータセルに量子化することによりハフ変換を実施する。アキュームレータセルは、この経路に沿って存在するアキュームレータセルがインクリメントされるのに応じて、離散化された経路を明らかにする。アキュームレータアレイにおいて結果として生成されるピークは、対応する経路がその特徴空間内に存在するという強い証拠を表す。本発明は、ハフ変換を用いて、１組の所与のエッジに最もよく適合する経路を特定する。
【００５５】
当然、時系列の自己相関を用いて一致するセグメントを見つけるために他の技法を用いることができることは理解されたい。たとえば、ドット積を用いることができる。この事例では、積の大きさが類似度のレベルを示している。連続したフレームの色ヒストグラムのような多次元時系列の場合、ヒストグラムインターセクションを用いることができる。
【００５６】
ＤＴＷを用いて一致する窓を見つけた後に、本発明は、類似のセグメントをクラスタ１５１にグループ化し、ラベルを付ける（１５０）。セグメントは、類似の特徴を有する窓に直に対応する映像内の一連のフレームを意味する。こうして、時系列データを用いて類似のセグメントを特定することにより、実質的には、その映像を分割し、類似のセグメントをクラスタにグループ化できるようになる。
【００５７】
用語「ラベル」および「アイテム」は、関連性に対して先に定義されたのと同じように用いられる。クラスタに言及するとき、そのクラスタは、たとえば動きの活発さが高いフレームのクラスタ、あるいは映像のサウンドトラック内の大きなノイズのクラスタのようにラベルを付されることを意味する。種々の特徴を用いて得られたラベル１５２の関連性および融合を用いることにより、クラスタ１５１内の高レベルのパターン１６１を推測できるようになる（１６０）。その後、これらのパターンは、映像１０１を盲目的に要約して、要約１７１を生成するために用いることができる（１７０）。要約することによって実質的には、高レベルのパターン１６１に従って映像の選択されたフレームが抽出される。
【００５８】
ステップ１６０では、クラスタのラベル間の関連性が見つけられる。１つのタイプの関連性は、時間的に相関がある「ラベル」を探索する。その相関は同時か、あるいは時間的にシフトされることができ、たとえば、娯楽映像において、多数の動きおよび大きいノイズが「動作」イベントを示唆し、スポーツ映像において、多数の動きの後に拍手および歓声があることが「得点」イベントを示唆する。
【００５９】
本発明は、以下のようにラベル間の関連性を見つける。各クラスタのためのラベルは、先に述べられたような「アイテム」と同等と見なされる。したがって、本発明は、ラベルＬｉの出現を含む条件と、ラベルＬｊの出現を含む結果とを生成する。この事例では、時間軸上の全ての点が対応するトランザクションを有し、それは、映像特徴１０２の２つ以上に対応するラベルを含む。
【００６０】
たとえば、本発明は、２組のラベルを有することができ、第１のラベルは高、中あるいは低のような動きの活発さの記述に対応し、第２のラベルは、音声の意味クラスに関連付けられ、その場合にラベルは、拍手、歓声、音楽などの音声クラス内のメンバシップを指示するであろう。その後、本発明は、スポーツ映像内の高い動きの活発さと拍手／歓声との間の関連性を見つけることができる。さらに複雑なラベルが用いられる場合であっても、簡単な計算によって関連性を見つけることができることに留意されたい。ラベルの組み合わせの間の複雑な関係を見つけることもできる。
【００６１】
その後、強い関連性によって、映像１０１内の対応する、よく見られるパターンおよび稀なパターンを見つけやすくすることができる。なぜなら、そのパターンがよく見られるほど、そのサポートが高いためである。
【００６２】
その際、映像１０１の要約１７１は、ユーザの要件に応じて、よく見られるイベントおよび稀なイベントの組み合わせを含む。１つの極端な場合には、要約１７１は、強い関連性を有する稀なイベントを含む。別の極端な場合には、要約は強い関連性を有するありふれたイベントを含む。
【００６３】
それゆえ、クラスタリング１５０は、上記のような距離測定に基づいて全ての類似のセグメントをクラスタリングすることにより開始する。部分的に重なり合うセグメントは分割され、それらが全く同じ重なりを有するようにするか、あるいは全く重なりがないようにする。クラスタの対は集積的な手順を用いて融合され、より大きなクラスタを形成することができる。本発明は、集合Ｓを、クラスタの類似の対のうちの少なくとも１つの中にある全てのセグメントを含むものと定義する。その際、集合ＳＣ∪Ｓは、映像１０１全体であり、集合ＳＣは、集合Ｓの補集合である。クラスタは、たとえばＡ、Ｂ、Ｃ、．．．のようにラベルを付され、Ａ∪Ｂ∪Ｃ．．．＝Ｓである。集合ＳＣは、ラベルＡ、Ｂ、Ｃなどに関して「意味のある」ものではない「ジャンク」クラスタと見なすことができる。
【００６４】
こうして、クラスタリング１５０は、種々の長さ、およびその相互の距離からなる重なり合わないセグメントの集合Ｓを生成する。各クラスタ１５１は、関連するパラメータ、すなわちクラスタ緊密度、すなわちクラスタ内のセグメントが如何に類似であるかと、クラスタ内のセグメントの数と、クラスタ内のセグメントの全長（フレームあるいは時間）と、映像全体におけるセグメントの広がりを示す、セグメントの最近接点間の平均距離とを有する。
【００６５】
１つのクラスタ内の各セグメントは、パラメータ、すなわちセグメントが、そのセグメントが収容されるクラスタの如何に代表的なセグメントであるかを示す、他のクラスタ中心への平均距離と、その長さ（フレームあるいは時間）とを有する。
【００６６】
その後、要約化コスト関数Ｃ１７２が、必要とされる要約長と、要約１７１内に含まれることになる選択されたセグメントからなる集合Ｒの全長（すなわちＲ⊂Ｓ）と、Ｓ内の各セグメントと集合Ｒ内の最も近いセグメントとの間の距離の平均との間の絶対差をトレードオフすることができる。これは、集合Ｒ（要約１７１）が、当然、映像１０１全体である集合Ｓを如何によく表現しているかを示す。本発明は、Ｒの時間的な緊密度、あるいはその逆を都合よく表現するための用語を追加することができる。その際、要約１７１は、コスト関数１７２を最小限に抑える集合Ｓの部分集合Ｒである。
【００６７】
その後、その要約は、予め定義域がわからない場合であっても、「スマートな」早送りおよび巻戻し、ならびに即時リポジショニングなどの映像制御の新たな様式のために用いられることができる。
【００６８】
本発明の精神および範囲内で種々の他の改変および変更がなされることができることは理解されたい。それゆえ、添付の特許請求の範囲の目的は、本発明の真の精神および範囲に入るような全てのそのような変形および変更を網羅することである。
【図面の簡単な説明】
【００６９】
【図１】本発明による映像マイニング方法１００の流れ図である。
【図２】ゴルフ映像の時系列図である。
【図３】本発明によって用いられる点横断距離マトリクスを示す図である。
【図４】繰返しパターンを有する点横断距離マトリクスを示す図である。
【図５】概ね対角線方向の最小コスト経路のグラフである。
【図６】閾値角を用いる最小経路のグラフである。
【図１】
2006508565.tif 000004
【図２】
2006508565.tif 000005
【図３】
2006508565.tif 000006
【図４】
2006508565.tif 000007
【図５】
2006508565.tif 000008
【図６】
2006508565.tif 000009
【国際調査報告】
2006508565.tif 000010
2006508565.tif 000011
2006508565.tif 000012