(57)【特許請求の範囲】
【請求項１】
ソース・デジタル・メディアのセグメントを代表するキーフレームの識別選択を行うプログラムであって、
コンピュータに、
複数のセグメントを含む前記ソース・デジタル・メディアを取得するステップと、
取得された前記ソース・デジタル・メディアを前処理して複数の特徴ベクトルを取得するステップと、
取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定するステップと、
取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定するステップと、
前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するステップと、
を実行させるためのプログラム。
【請求項２】
前記セグメント内の類似度と前記セグメント外の類似度との差分又は比率で表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが全フレームに対して最大となるように、前記キーフレームを識別選択する、請求項１に記載のプログラム。
【請求項３】
前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含む、請求項１に記載のプログラム。
【請求項４】
前記複数項目のソース・デジタル・メディアを１項目のソース・デジタル・メディアに連結するステップを含む、請求項３に記載のプログラム。
【請求項５】
前記ソース・デジタル・メディアを取得するステップに続いて、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含んでいるかを判定するステップをさらに含む、請求項１に記載のプログラム。
【請求項６】
前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含んでいると判定された場合、前記ソース・デジタル・メディアを１項目のソース・デジタル・メディアに連結するステップをさらに含む、請求項５に記載のプログラム。
【請求項７】
前記セグメント内の類似度を決定するステップが、候補キーフレームをセグメントに属するその他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント内の類似度を決定するステップと、をさらに含み、
前記セグメント外の類似度を決定するステップが、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント外の類似度を決定するステップと、をさらに含む、
請求項１に記載のプログラム。
【請求項８】
デジタル情報を代表するキーフレームの識別選択を行うプログラムであって、
コンピュータに、
デジタル情報を取得するステップと、
前記デジタル情報を複数のセグメントにセグメント化するステップと、
複数のセグメントにセグメント化された前記デジタル情報を前処理して複数の特徴ベクトルを取得するステップと、
取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定するステップと、
取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定するステップと、
前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するステップと、
を実行させるためのプログラム。
【請求項９】
前記セグメント内の類似度を決定するステップが、候補キーフレームをセグメントに属するその他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント内の類似度を決定するステップと、を含み、
前記セグメント外の類似度を決定するステップが、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント外の類似度を決定するステップと、を含み、
前記キーフレームを識別選択するステップにおいて、前記セグメント内の類似度と前記セグメント外の類似度とを用いて表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが、各セグメント内の全フレームに対して最大となるように、各セグメントのキーフレームを識別選択する、
請求項８に記載のプログラム。
【請求項１０】
前記キーフレームを識別選択するステップが、前記セグメント内の類似度と前記セグメント外の類似度とをバイアスするステップを含む、請求項９に記載のプログラム。
【請求項１１】
前記キーフレームを識別選択するステップが、複数のキーフレームを各セグメントの代表として識別選択するステップを含む、請求項８に記載のプログラム。
【請求項１２】
ソース・デジタル・メディアのセグメントを代表するキーフレームの識別選択システムであって、
複数のセグメントを含む前記ソース・デジタル・メディアを入力するメディア入力部と、
前記メディア入力部により入力された前記ソース・デジタル・メディアを前処理して複数の特徴ベクトルを取得する特徴ベクトル取得部と、
前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定する第１の類似度決定部と、
前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定する第２の類似度決定部と、
前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するキーフレーム選択部と、
を含む前記キーフレームの識別選択システム。
【請求項１３】
前記キーフレーム選択部が、前記セグメント内の類似度と前記セグメント外の類似度との差分又は比率で表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが全フレームに対して最大となるように、前記キーフレームを識別選択する、請求項１２に記載のキーフレームの識別選択システム。
【請求項１４】
前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含む、請求項１２に記載のキーフレームの識別選択システム。
【請求項１５】
前記複数項目のソース・デジタル・メディアを１項目のソース・デジタル・メディアに連結するメディア連結部を含む、請求項１４に記載のキーフレームの識別選択システム。
【請求項１６】
取得された前記ソース・デジタル・メディアに対し、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含んでいるか、を判定するメデイア判定部をさらに含む、請求項１２に記載のキーフレームの識別選択システム。
【請求項１７】
前記第１の類似度決定部が、候補キーフレームをセグメントに属するその他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント内の類似度を決定し、
前記第２の類似度決定部が、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント外の類似度を決定する、
請求項１２に記載のキーフレームの識別選択システム。
【請求項１８】
デジタル情報を代表するキーフレームの識別選択システムであって、
デジタル情報を取得するデジタル情報取得部と、
前記デジタル情報を複数のセグメントにセグメント化するセグメント処理部と、
複数のセグメントにセグメント化された前記デジタル情報を前処理して複数の特徴ベクトルを取得する特徴ベクトル取得部と、
前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定する第１の類似度決定部と、
前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定する第２の類似度決定部と、
前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するキーフレーム選択部と、
を含む、前記キーフレームの識別選択システム。
【請求項１９】
前記第１の類似度決定部が、候補キーフレームをセグメントに属するその他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント内の類似度を決定し、
前記第２の類似度決定部が、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント外の類似度を決定し、
前記キーフレーム選択部が、前記セグメント内の類似度と前記セグメント外の類似度とを用いて表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが、各セグメント内の全フレームに対して最大となるように、各セグメントのキーフレームを識別選択する、
請求項１８に記載のキーフレームの識別選択システム。
【請求項２０】
前記キーフレーム選択部が、前記セグメント内の類似度と前記セグメント外の類似度とをバイアスする、請求項１９に記載のキーフレームの識別選択システム。
【請求項２１】
前記キーフレーム選択部が、複数のキーフレームを各セグメントの代表として識別選択する、請求項１９に記載のキーフレームの識別選択システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル・メディア分析の分野に関し、より詳細には、デジタル・メディア自動識別分析の分野に関する。即ち、本発明は、キーフレーム識別選択方法、この方法をコンピュータに実行させるプログラム、およびキーフレーム識別選択システムに関する。
【背景技術】
【０００２】
インターネット、デジタル・スチルカメラ、及びデジタル・ビデオカメラの出現により、個人が大きな集合の「デジタル・メディア」を整理することは日常的なこととなっている。この集合が大きくなるほど、必要なメディア項目を迅速に捜して識別し、検討及び／又は編集することが困難になる。
【０００３】
この問題を解決しようと、いくつかの技法が考案されてきている。例えば、ある技法では、メディアのその特定項目の代表として「キーフレーム」が識別される。しかしながら、現在のキーフレーム選択技法には、デジタル・メディアの類似項目（即ち、類似した内容を含む項目）により区別不可能なほど類似したキーフレームがよく生じる、という問題がある。専門的に作製されたデジタル・ビデオでさえも、この状況は非常によく生じる。例えば、一般的なフィルム技法として、各話者のショットを交互につなぎ合わせて対話フロー図を構成する技法がある。セグメント化後、同じ話者の各ショットは、同じ対象を同じ角度から同じ照明、背景などで撮っているので、非常に類似している。デジタル・カメラから得られる短いビデオ・クリップや、セグメント・ベースのビデオ・リポジトリから得られるプリセグメントの結果のような、多数の一般的なビデオ・ソースが、この問題を共有している。このような従来技術に関するものとして、特許文献１には、音楽やスピーチの特徴点の抽出手法とセグメント化についての手法が記載されている。また、米国特許出願第１０／０８６，８１７号明細書には、ビデオ、オーディオ、テキスト等のメディアにおける、類似度を指標とした最適な要約作製手法が記載されている。
【０００４】
また、非特許文献１には、デジタル・ビデオの記録内容についてキーフレームを用いる３つの視覚的インターフェースにより、効率的なアクセスポイントを提供することが記載されている。非特許文献２も、やはり、キーフレームを利用するものであり、デジタル・ビデオ全体を的確に要約し、かつ、それぞれ、異なるキーフレームを決定することにより、適切なアクセスポイントを提供する技術を提供する。非特許文献３は、デジタル・ビデオにおける繰り返しを検出することにより、キーフレームにおける類似性を減少させるようにして、効率的なキーフレームを選択する、ショット分類法について記載している。
【特許文献１】米国特許第６，５４２，８６９号明細書
【非特許文献１】A．ギルゲンゾーン(A. Girgensohn)、J．ボレツキー(J. Boreczky)、L．ウィルコックス(L. Wilcox)著，「キーフレーム・ベースのデジタル・ビデオ用ユーザ・インタフェース(Keyframe-Based User Interfaces for Digital Video)」，IEEEコンピュータ(IEEE Computer)，２００１年９月
【非特許文献２】A．ギルゲンゾーン、J．ボレツキー著，「時間制約付きキーフレーム選択技法(Time-Constrained Keyframe Selection Technique)」，IEEEマルチメディア・システムズ会報(Proc. IEEE Multimedia Systems)，第１巻，p．７５６−７６１，１９９９年
【非特許文献３】H．アオキ(H. Aoki)、S．シモツジ(S. Shimotsuji)、O．ホリ(O. Hori)著，「ビデオ・ブラウジングに効果的なキーフレームを選択するショット分類法(A Shot Classification Method of Selecting Effective Key-Frames for Video Browsing)」，ACMマルチメディア会報(Proc. ACM Multimedia)，１９９６年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、デジタル・メディアを代表しその他の選択されたキーフレームとは異なるキーフレームを自動的に選択するシステム及び方法を提供することが望ましい。
【課題を解決するための手段】
【０００６】
概略的に述べると、本発明の実施形態によれば、ソース・デジタル・メディアのセグメントを代表するキーフレームを識別選択するシステム及び方法が提供される。キーフレームは、ソース・デジタル・メディアを前処理して、メディアのフレームに対する特徴ベクトルを取得することにより選択される。次に、ソース・デジタル・メディアの各セグメントに対する候補キーフレームを同じセグメントのその他のフレームと比較することにより、類似度(similarity value)が決定される。また、この候補キーフレームをソース・デジタル・メディアのその他のセグメントに属するフレームとも比較することによって、非類似度(dis-similarity measure)が決定される。次に、最良値を有する、即ち、セグメントの代表であると共にその他のキーフレームと区別可能である、候補キーフレームを選択することにより、代表キーフレームが選択される。
【０００７】
請求項１の発明は、ソース・デジタル・メディアのセグメントを代表するキーフレームの識別選択を行うプログラムであって、コンピュータに、複数のセグメントを含む前記ソース・デジタル・メディアを取得するステップと、取得された前記ソース・デジタル・メディアを前処理して複数の特徴ベクトルを取得するステップと、取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定するステップと、取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定するステップと、前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するステップと、を実行させるためのプログラムである。
請求項２の発明は、前記セグメント内の類似度と前記セグメント外の類似度との差分又は比率で表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが全フレームに対して最大となるように、前記キーフレームを識別選択する、請求項１に記載のプログラムである。
請求項３の発明は、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含む、請求項１に記載のプログラムである。
請求項４の発明は、前記複数項目のソース・デジタル・メディアを１項目のソース・デジタル・メディアに連結するステップを含む、請求項３に記載のプログラムである。
請求項５の発明は、前記ソース・デジタル・メディアを取得するステップに続いて、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含んでいるかを判定するステップをさらに含む、請求項１に記載のプログラムである。
請求項６の発明は、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含んでいると判定された場合、前記ソース・デジタル・メディアを１項目のソース・デジタル・メディアに連結するステップをさらに含む、請求項５に記載のプログラムである。
請求項７の発明は、前記セグメント内の類似度を決定するステップが、候補キーフレームをセグメントに属するその他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント内の類似度を決定するステップと、をさらに含み、前記セグメント外の類似度を決定するステップが、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント外の類似度を決定するステップと、をさらに含む、請求項１に記載のプログラムである。
請求項８の発明は、デジタル情報を代表するキーフレームの識別選択を行うプログラムであって、コンピュータに、デジタル情報を取得するステップと、前記デジタル情報を複数のセグメントにセグメント化するステップと、複数のセグメントにセグメント化された前記デジタル情報を前処理して複数の特徴ベクトルを取得するステップと、取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定するステップと、取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定するステップと、前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するステップと、を実行させるためのプログラムである。
請求項９の発明は、前記セグメント内の類似度を決定するステップが、候補キーフレームをセグメントに属するその他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント内の類似度を決定するステップと、を含み、前記セグメント外の類似度を決定するステップが、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較するステップと、前記比較ステップに応じて、前記候補キーフレームの前記セグメント外の類似度を決定するステップと、を含み、前記キーフレームを識別選択するステップにおいて、前記セグメント内の類似度と前記セグメント外の類似度とを用いて表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが、各セグメント内の全フレームに対して最大となるように、各セグメントのキーフレームを識別選択する、請求項８に記載のプログラムである。
請求項１０の発明は、前記キーフレームを識別選択するステップが、前記セグメント内の類似度と前記セグメント外の類似度とをバイアスするステップを含む、請求項９に記載のプログラムである。
請求項１１の発明は、前記キーフレームを識別選択するステップが、複数のキーフレームを各セグメントの代表として識別選択するステップを含む、請求項８に記載のプログラムである。
請求項１２の発明は、ソース・デジタル・メディアのセグメントを代表するキーフレームの識別選択システムであって、複数のセグメントを含む前記ソース・デジタル・メディアを入力するメディア入力部と、前記メディア入力部により入力された前記ソース・デジタル・メディアを前処理して複数の特徴ベクトルを取得する特徴ベクトル取得部と、前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定する第１の類似度決定部と、前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定する第２の類似度決定部と、前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するキーフレーム選択部と、を含む前記キーフレームの識別選択システムである。
請求項１３の発明は、前記キーフレーム選択部が、前記セグメント内の類似度と前記セグメント外の類似度との差分又は比率で表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが全フレームに対して最大となるように、前記キーフレームを識別選択する、請求項１２に記載のキーフレームの識別選択システムである。
請求項１４の発明は、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含む、請求項１２に記載のキーフレームの識別選択システムである。
請求項１５の発明は、前記複数項目のソース・デジタル・メディアを１項目のソース・デジタル・メディアに連結するメディア連結部を含む、請求項１４に記載のキーフレームの識別選択システムである。
請求項１６の発明は、取得された前記ソース・デジタル・メディアに対し、前記ソース・デジタル・メディアが複数項目のソース・デジタル・メディアを含んでいるか、を判定するメデイア判定部をさらに含む、請求項１２に記載のキーフレームの識別選択システムである。
請求項１７の発明は、前記第１の類似度決定部が、候補キーフレームをセグメントに属するその他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント内の類似度を決定し、前記第２の類似度決定部が、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント外の類似度を決定する、請求項１２に記載のキーフレームの識別選択システムである。
請求項１８の発明は、デジタル情報を代表するキーフレームの識別選択システムであって、デジタル情報を取得するデジタル情報取得部と、前記デジタル情報を複数のセグメントにセグメント化するセグメント処理部と、複数のセグメントにセグメント化された前記デジタル情報を前処理して複数の特徴ベクトルを取得する特徴ベクトル取得部と、前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記複数のセグメントの１つのセグメントに対する候補キーフレームに対する、前記１つのセグメントに属するその他のフレームとの間でのセグメント内の類似度を決定する第１の類似度決定部と、前記特徴ベクトル取得部により取得された前記複数の特徴ベクトルの分析結果に基づいて、前記候補キーフレームに対する、残りの複数のセグメントに属するフレームとの間でのセグメント外の類似度を決定する第２の類似度決定部と、前記セグメント内の類似度と前記セグメント外の類似度とに基づいて、前記１つのセグメント内のフレームとはできるだけ高い類似度を有しているという第１の基準、及び前記１つのセグメント外に属するフレームとはできるだけ類似していないという第２の基準を同時によく満たすフレームを、各セグメントのキーフレームとして識別選択するキーフレーム選択部と、を含む、前記キーフレームの識別選択システムである。
請求項１９の発明は、前記第１の類似度決定部が、候補キーフレームをセグメントに属するその他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント内の類似度を決定し、前記第２の類似度決定部が、１つのセグメントの候補キーフレームを残りの複数のセグメントに属する他のフレームと比較し、その比較の結果に応じて、前記候補キーフレームの前記セグメント外の類似度を決定し、前記キーフレーム選択部が、前記セグメント内の類似度と前記セグメント外の類似度とを用いて表され、最適な代表キーフレームであることを示す性能指標であるグッドネス・ファンクションＦが、各セグメント内の全フレームに対して最大となるように、各セグメントのキーフレームを識別選択する、請求項１８に記載のキーフレームの識別選択システムである。
請求項２０の発明は、前記キーフレーム選択部が、前記セグメント内の類似度と前記セグメント外の類似度とをバイアスする、請求項１９に記載のキーフレームの識別選択システムである。
請求項２１の発明は、前記キーフレーム選択部が、複数のキーフレームを各セグメントの代表として識別選択する、請求項１９に記載のキーフレームの識別選択システムである。
【発明を実施するための最良の形態】
【００４８】
本発明を、特定の実施形態に関して説明する。本発明のその他の目的、特徴、及び利点については、明細書及び図面を参照すれば明らかとなるであろう。
【００４９】
定義
本明細書中で用いられる「デジタル・メディア」とは、デジタル・ビデオ、デジタル画像、デジタル・オーディオ、テキスト、及び印刷可能ページを含むが、これらに限定されるわけではない。
【００５０】
本明細書中で用いられる「フレーム」とは、より大きな項目若しくは集合であるデジタル・メディアのあらゆる基本サブユニットである。例えば、デジタル・ビデオは静止画像のシーケンスであり、各静止画像を本明細書中ではフレームと呼んで説明する。デジタル・ビデオと同様に、デジタル写真の集合も、概念上、静止画像のシーケンスとみなすことができる。このようなシーケンス若しくは集合に対して、各単独の写真を本明細書中ではフレームと呼ぶ。オーディオ、テキスト、及び／若しくはその他のデジタル・メディアから構成されるストリーム、ドキュメント、又はドキュメント集合に対し、フレームとは、このような集合の部分集合である。このようなタイプのメディアは、どのような長さのサブユニットに分割して分析してもよい。本明細書中では、フレームには、より長いストリームから抜粋されたオーディオ又はテキストが含まれ得る。全体を通してフレームという語が用いられているが、この用語は、本発明の範囲をデジタル・ビデオ又はデジタル画像集合に限定することを意図しているわけではなく、あらゆる形態のデジタル・メディアのあらゆるサブユニットを指すために明細書の中で用いている。
【００５１】
本明細書中で用いられる「セグメント」とは、より大きな項目若しくは集合であるデジタル・メディアから選択されるフレームの集合である。例えば、デジタル・メディアを様々な基準に応じてフレームグループにセグメント化することによって、ブラウジング及びナビゲーションが容易になり得る。セグメントは、より大きな項目若しくは集合であるデジタル・メディアのどの部分若しくは部分集合であってもよい。或いは、セグメントは、デジタル・メディアの項目全体であってもよい。例えば、セグメントは、そのソース又は長さに関わらず、デジタル画像の集合であってもよいし、デジタル・ビデオのどの部分であってもよい（ビデオ全体であってもよい）。
【００５２】
本明細書中で用いられる「キーフレーム」とは、セグメント（フレームの集合）から、デジタル・メディアのそのセグメントの代表として選択されるフレームである。
【００５３】
上記定義における例は絶対的なものではなく、あらゆるその他の形態のデジタル・メディアを本発明の実施形態に同様に適用することができる。
【００５４】
概観
本発明の実施形態によれば、デジタル・メディアのセグメントの代表としてキーフレームを識別選択するシステム及び方法が提供される。セグメントを代表しその他のキーフレームと異なるキーフレームを選択することによって、キーフレームが視覚的に特有且つ独特となる。例えば、２つのビデオ・セグメントが同じ招待講演者のビデオを含んでいるが、一方のセグメントでその講演者が笑っているか又は違う方向を向いている場合、選択されたキーフレームがこのような変化を反映すれば、そのキーフレームが表すビデオ・セグメントがもう一方のビデオ・セグメントから容易に区別される。後でより詳細に説明するように、一実施形態では、キーフレームの選択は、そのキーフレームが属するセグメントとその他のセグメントとに対するキーフレームの類似度を測定することにより行われる。要するに、本発明の実施形態によれば、代表的且つ特徴的なキーフレームを選択する定量的方法が提供される。別の例では、デジタル・テキストブックの２つの章（各章はセグメントとみなされる）が類似した題材を含んでいるが、一方の章が要約を含んでいる場合、その章に対して選択されたキーフレームがその要約からのテキストを含んでいれば、それによりその章がもう一方の章から区別される。
【００５５】
図１は、本発明の実施形態によるキーフレーム識別選択処理を示している。当業者には明らかであるように、図１及び図４は、特定機能を行う論理ブロックを示している。別の実施形態では、より多くの又はより少ない論理ブロックを用いてもよい。本発明の実施形態では、論理ブロックは、ソフトウェア・プログラム、ソフトウェア・オブジェクト、ソフトウェア機能、ソフトウェア・サブルーチン、ソフトウェア・メソッド、ソフトウェア・インスタンス、コード・フラグメント、ハードウェア動作、又はユーザ操作を、単独で若しくは組み合わせて表し得る。例えば、この論理ブロックは、図６に示されたキーフレーム識別選択ソフトウェア５１２を表し得る。
【００５６】
図１の処理は論理ブロック１０１で開始し、この論理ブロック１０１では、システムがソース・デジタル・メディアを取得する。このデジタル・メディアは、デジタル・ビデオのようなどんな単独項目のデジタル・メディアであってもよいし、異なるメディアをどのように組み合わせたデジタル・メディアであってもよい。例えば、簡単に図２を参照すると、論理ブロック１０１で取得されるデジタル・メディアは、セグメント化されていないデジタル・ビデオ２０１1のような、単独項目のデジタル・メディアであってもよい。或いは、このソース・デジタル・メディアは、セグメント化された若しくはセグメント化されていないデジタル・ビデオやデジタル画像集合など（例えば、セグメント化されていないデジタル・ビデオ２０１1、セグメント化されたデジタル・ビデオ２０１2、デジタル画像２０１3、セグメント化されたデジタル画像集合２０１4、セグメント化されていないデジタル画像集合２０１5、セグメント化されていないデジタル・テキスト２０１6、セグメント化されたデジタル・テキスト２０１7、セグメント化されていないデジタル・オーディオ２０１8、セグメント化されたデジタル・オーディオ２０１9）のうちの１項目以上であってもよい。本発明の実施形態では、論理ブロック１０１で取得されるソース・デジタル・メディアとして、複数のタイプをどのように組み合わせたデジタル・メディアを用いてもよい。論理ブロック１０１でソース・デジタル・メディアが取得されると、制御は論理ブロック１０３へ進む。
【００５７】
論理ブロック１０３では、ソース・デジタル・メディアが複数項目のデジタル・メディアを含んでいるかということに関して、判定が行われる。ソース・デジタル・メディアが複数項目のデジタル・メディアを含んでいると判定された場合には、制御は論理ブロック１０５へ進む。一方、論理ブロック１０３で、ソース・デジタル・メディアが１項目のみのデジタル・メディアを含んでいると判定された場合には、制御は論理ブロック１０７へ進む。
【００５８】
論理ブロック１０５では、複数項目のデジタル・メディアが、分析のために、始めと終わりを有する単独ソースに連結される。例えば、図３に示されているように、ソース・デジタル・メディアが、セグメント化されていないデジタル・ビデオ２０１1、セグメント化されたデジタル・ビデオ２０１2、デジタル画像２０１3、及びセグメント化されたデジタル画像集合２０１4を含んでいる場合、論理ブロック１０５では、分析及び最終的なキーフレーム抽出のために、これらの項目のデジタル・メディアが全て連結され、単独項目のデジタル・メディア２１０として扱われる。各項目のデジタル・メディアの元の終了点と開始点は、連結されると、連結ソース・デジタル・メディアにおけるセグメント境界として扱われる。連結されると、制御は論理ブロック１０７へ進み、処理が続けられる。
【００５９】
論理ブロック１０７では、ソース・デジタル・メディアがセグメント化されているかということに関して、判定が行われる。後でより詳細に説明するように、本発明の実施形態では、多数の方法でセグメント化を行ってもよいし、どのようなセグメント化技法を用いてもよい。論理ブロック１０７で、ソース・デジタル・メディアがセグメント化されていると判定された場合には、制御は論理ブロック１０９へ進む。一方、ソース・デジタル・メディアがセグメント化されていないと判定された場合には、制御は論理ブロック１１１へ進む。
【００６０】
論理ブロック１０９では、ソース・デジタル・メディアのセグメント化がさらに必要であるか若しくは要求されているかということに関して、判定が行われる。この判定は、自動的に行われてもよいし、ユーザの要求に応じて行われてもよい。ユーザが単にさらなるセグメント化を要求する場合には、制御は論理ブロック１１１へ進み、処理が続けられる。セグメント化の自動判定は、既存のセグメントの長さに基づいて行われてもよいし、且つ／又は既存のセグメント全体にわたるシーン変化の計算値に基づいて行われてもよい。例えば、セグメント化されていないデジタル・ビデオ２０１1のために、ソース・デジタル・メディア２１０に対してさらなるセグメント化を決定してもよい。連結後、セグメント化されていないデジタル・ビデオ２０１1は、ソース・デジタル・メディア２１０の１つのセグメントとして扱われる。ソース・デジタル・メディア２１０の分析に基づいて、セグメント２０１全体にわたって数ヶ所のシーン変化を識別することによって、さらなるセグメント化の必要性を示してもよい。
【００６１】
説明の便宜上、セグメント化されていないデジタル・ビデオ２０１1は、誕生日会のシーン、ハワイへの休暇のシーン、及び山への休暇のシーンを含むと仮定する。連続フレーム間の差を算出することによって、セグメント化されていない複数のシーンがあるということが判定される。このような判定が為されたら、システムは、自動的に制御を論理ブロック１１１へ進めてもよいし、或いは、セグメント化をさらに行うことが有益であるということをユーザに示して、セグメント化を行うかということに関する判定を要求してもよい。セグメント化がさらに行われる場合には、制御は論理ブロック１１１へ進み、処理が続けられる。
【００６２】
或いは、自動的に又はユーザ入力により、さらなるセグメント化は必要でないと判定された場合には、制御は論理ブロック１１３へ進む。この判定におけるユーザ入力とは、さらなるセグメント化は望まないということをユーザが単に示したものである。判定が自動的に行われる場合には、このような結果が生じ得、その時点で全てのシーンがセグメント化されているか、シーンが１つしか存在しない。例えば、ソース・デジタル・メディアがセグメント化されたデジタル画像集合２０１4しか含んでいない場合、さらなるセグメント化は必要でないとシステムは判定し、制御は論理ブロック１１３へ進む。
【００６３】
論理ブロック１１１では、ソース・デジタル・メディアがセグメント化される。本発明の実施形態はいずれの特定のセグメント化技法にも依存することはなく、どのようなセグメント化技法が用いられてもよい。さらに、セグメント化は、全くセグメント化されていないソース・デジタル・メディアに対して行ってもよいし、部分的にのみセグメント化されているソース・デジタル・メディアに対して行ってもよい。本発明の実施形態で用いられ得るセグメント化技法の例としては、ユーザによる手動セグメント化や、フレーム間の差を閾値処理したり、ヒストグラムに基づいてフレーム差を測定したり、自己類似度(self-similarity)を用いたりすることによる自動セグメント化が挙げられるが、これらに限定されるわけではない。自己類似度については、「ビデオの自己類似度分析によるシーン境界検出(Scene Boundary Detection via Video Self-Similarity Analysis)」（マシュー・クーパー(Matthew Cooper)、ジョナサン・フート(Jonathan Foote)著，２００１年）に記載されており、この文献は参照により本明細書中に組み込まれる。さらに、米国特許第６，５４２，８６９号（発明の名称：音楽及びスピーチを含むオーディオの自動分析方法(Method For Automatic Analysis Of Audio Including Music And Speech)；発明者：ジョナサン・フート）（この特許文献は参照により本明細書中に組み込まれる）には、類似度に基づいたさらなるセグメント化技法が記載されており、この技法は本発明の実施形態で用いられ得る。ソース・デジタル・メディアがセグメント化されると、制御は論理ブロック１１３へ進む。
【００６４】
論理ブロック１１３では、デジタル・メディアのフレームがパラメータ化されて、これらのフレームを代表する特徴ベクトルが取得される。本発明の実施形態では、ソース・デジタル・メディアの各フレームをパラメータ化してもよい。或いは、処理時間を短縮するために、フレームの一部のみをパラメータ化してもよく、例えば、１フレームおきに、又は２フレームおきに、又はその他どのようなフレームの組み合わせでパラメータ化してもよい。さらに別の実施形態では、複数のフレーム集合を一緒にパラメータ化し、各フレーム集合に対して１つの特徴ベクトルを生成してもよい。
【００６５】
特徴ベクトルを取得するには、どのようなパラメータ化技法を用いてもよい。例えば、低次離散コサイン変換（「ＤＣＴ」）係数に基づいて、特徴ベクトルを算出してもよい。このような実施形態では、ソース・デジタル・メディアを特定周波数でサンプリングすることによってフレームを取得してもよく、これらのフレームは、３つのチャネルがほぼ相関しないオータ(Ohta)色空間に変換される。各変換チャネルのＤＣＴが算出され、得られた３つのチャネルの２５〜４９の低周波数係数を連結することによって特徴ベクトルが形成される。この変換方法は、低次化や忠実度よりも分析法（及び、必要であれば計算量）に応じて最適化される。結果として、サンプリングされた各ビデオ・フレームに対し、コンパクトな特徴ベクトル若しくは縮小した係数が得られる。このような手法は、類似度を定量化するのに適している。その理由は、類似したフレームは類似した変換係数（特徴ベクトル）を取得するからである。特徴ベクトルが決定されると、制御は論理ブロック１１５へ進む。
【００６６】
論理ブロック１１５では、特徴ベクトルが分析され、キーフレームが各セグメントの代表として選択される。キーフレームを選択する様々な技法については、後で詳細に説明する。キーフレームが選択されたら、システムは、これらのフレームをどのような構成技法でユーザに表示してもよい。
【００６７】
当然のことながら、図１に関して説明した処理は、論理ブロックで示したステップを異なる順序で行ったり、追加のステップを用いたり、より少ないステップを用いたりして、異なる構成若しくは構造で実施してもよい。例えば、一実施形態では、前処理ステップ１１３を、論理ブロック１０３及び１０５の後で、且つセグメント化に関する判定及びセグメント化を行う論理ブロック１０７、１０９、及び１１１の前に行ってもよい。
【００６８】
キーフレーム識別選択方法のさらに別の実施形態が、図４に示されている。処理３００は、論理ブロック３０１において、ソース・デジタル・メディアを取得することにより開始する。図１の論理ブロック１０１に関して上述したように、このソース・デジタル・メディアは、どのような形態及び組み合わせのデジタル・メディアであってもよいし、複数のソースから取得してもよい。デジタル・メディアが取得されると、制御は論理ブロック３０３へ進み、論理ブロック１０３に関して上述したように、このソース・デジタル・メディアが複数項目のデジタル・メディアを含んでいるかということに関して判定が行われる。ソース・デジタル・メディアが複数項目のデジタル・メディアを含んでいると判定された場合には、制御は論理ブロック３０５へ進む。一方、ソース・デジタル・メディアが複数項目のデジタル・メディアを含んでいないと判定された場合には、制御は論理ブロック３１３へ進む。
【００６９】
論理ブロック３０５では、論理ブロック１０５に関して上述したように、処理及びキーフレーム選択のために、複数項目のデジタル・メディアが１項目のソース・デジタル・メディアに連結される。メディアが連結されると、制御は論理ブロック３１３へ進み、この論理ブロック３１３では、論理ブロック１１３に関して上述した技法のいずれかを用いてソース・デジタル・メディアが前処理され、各フレーム、フレーム部分、又はフレームグループに対して特徴ベクトルが取得される。次に、制御は論理ブロック３１５へ進む。後で詳細に説明すると共に、前に論理ブロック１１５に関して略述したように、論理ブロック３１５では、様々なキーフレーム選択技法のうちの１つを用いて、キーフレームが識別選択される。
【００７０】
前述の実施形態とは異なり、図４に関して説明した実施形態はセグメント化を含んでいない。代わりに、ソース・デジタル・メディアは、既にセグメント化されているものと仮定される。しかしながら、この処理は、事前にセグメント化されていないデータにもやはり適用することができる。例えば、１項目のみのデジタル・メディアが取得された場合には、このデジタル・メディアは１つのセグメントとして扱われ、１つのキーフレームが生成される。複数項目のデジタル・メディアがソース・デジタル・メディアに含まれている場合には、連結後、元の各項目は個々のセグメントとみなされ、これらのセグメント及び／又はあらゆる他のセグメントのそれぞれに対するキーフレームが生成される。
【００７１】
図６は、本発明の実施形態を実施するのに適した計算機アーキテクチャ５００を示している。この計算機アーキテクチャ５００は、プロセッサ５０２、記憶装置５０３、及び表示モニタ５０４を備える。また、このアーキテクチャ５００は、モデムのようなインターネット・アクセス装置５１０、入出力装置５１３、カーソル制御装置５０５、ランダム・アクセス・メモリ（「ＲＡＭ」）５０７、読出し専用メモリ（「ＲＯＭ」）５０８、キーボード５０６、及びグラフィックス・コプロセッサ５０９を備えていてもよい。計算機アーキテクチャ５００のこれらの要素は全て、様々な要素間においてデータを搬送する共通バス５０１によって結合され得る。このバス５０１は、一般的には、データ信号、アドレス信号、及び制御信号を含む。
【００７２】
本発明の実施形態は、図６に示した計算機アーキテクチャ５００のような、あらゆる計算機アーキテクチャにおいて実行可能であるが、このようなアーキテクチャが本発明の実施形態を実行できる唯一のものである、と限定されるわけではない。
【００７３】
本発明の実施形態では、記憶装置５０３は、コンピュータ可読媒体のような製品であり得る。記憶装置５０３としては、例えば、磁気ハードディスク、光ディスク、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ（コンパクトディスク読出し専用メモリ）、ＲＡＭ（ランダム・アクセス・メモリ）、ＲＯＭ（読出し専用メモリ）、又は、その他の読取り可能若しくは書込み可能なデータ記憶技術を、単独で或いは組み合わせて用いてもよい。
【００７４】
この記憶装置５０３は、マイクロソフト・ウィンドウズ(Microsoft Windows)（登録商標）、アップル・マッキントッシュ(Apple Macintosh)ＯＳ（登録商標）、又はユニックス(Unix)（登録商標）のような、オペレーティング・システム５１１を備えていてもよく、このオペレーティング・システム５１１は、計算機アーキテクチャ５００を用いて、プログラム若しくはアプリケーションを実行することができる。本発明の実施形態は、キーフレーム選択ソフトウェア・プログラム５１２として実施され、記憶装置５０３に記憶される。
【００７５】
当然のことながら、キーフレーム選択ソフトウェア・プログラム５１２のような本発明の実施形態は、ソフトウェア・プログラム、ソフトウェア・オブジェクト、ソフトウェア機能、ソフトウェア・サブルーチン、ソフトウェア・メソッド、ソフトウェア・インスタンス、コード・フラグメント、ハードウェア動作、又はユーザ操作を、単独で若しくは組み合わせて用いた形態であってよい。さらに、このキーフレーム選択ソフトウェア・プログラム５１２は、１台、２台、又は何台の計算機５００を用いて実施してもよい。
【００７６】
キーフレーム識別選択
一実施形態によれば、論理ブロック１１５及び３１５によって行われるようなキーフレームの識別選択は、論理ブロック１１３及び３１３で生成された特徴ベクトルに基づいて行われる。類似度や線形の識別方法（手段）に基づく検討手法のうちのいずれか１つを用いて、特徴ベクトルを比較し、キーフレームを選択してもよい。
【００７７】
キーフレーム選択技法に関係なく、後の時点でキーフレームを再生するための計算上の留意事項がある。留意事項の１つは、集合にさらなるビデオ又は画像を追加する場合のキーフレーム更新コスト(costs)である。例えば、ライトテーブルにおいて、デジタル写真編成ソフトウェアは、通常、サムネイルを用いる。ユーザは、写真を「事象」にグループ化することが多く、これらの事象はそれぞれ、セグメントとして扱われ、集合をより高いレベルで観察する際にはキーフレームにより表され得る。さらなる写真が追加される場合には、キーフレームを更新して、さらなる識別を行うのが望ましい。
【００７８】
本発明の実施形態において用いられる類似度に基づく１つの方法では、類似度Ｏ(Ｎ)の複雑度（Ｎはフレームの総数である）がもたらされ、類似度マトリックスにさらなる行及び列が追加される。線形識別技法は、後述するように、以前に生成したキーフレームを更新するのによりコストがかかる。ＷFLDは、後述するように、一般固有ベクトルから構成されているので、フレームを追加して分析を更新するには、「インテリジェント情報検索に対する線形代数の使用(Using Linear Algebra For Intelligent Information Retrieval)」（Ｍ．Ｗ．ベリー(M. W. Berry)、Ｓ．Ｔ．デュメ(S. T. Dumais)、Ｇ．Ｗ．オブライエン(G. W. O'Brien)著，ＳＩＡＭ論評(SIAM Review)３７（４）：ｐ．５７３−５９５，１９９５年）に記載されているような「畳込み(folding-in)」技法が適用可能である。これらのコストは、ほぼＯ(ＮＤ)となる。
【００７９】
その他計算上の特徴は、クラス外平均類似度Ｃを算出又は更新する際に、全てのビデオ・フレームの部分集合のみが考慮される。１つの方法では、既に選択されたキーフレームの集合｛ｖk*｝のみを用いて、Ｃが再度算出される。その他の計算上の特徴についても、本発明の実施形態の中で考慮されている。
【００８０】
類似度に基づくキーフレーム識別選択
類似度に基づくインプリメンテーションを用いることによって、候補キーフレームをセグメント内の他のフレーム（本明細書中では「クラス内フレーム(in-class frames)」と呼ぶ）と比較して、候補キーフレームがそのセグメントをどの程度よく表しているか（類似度）を判定すると共に、候補キーフレームを他のセグメントのフレーム（本明細書中では「クラス外フレーム(out-of-class frames)」と呼ぶ）と比較して、候補キーフレームがこれらのフレームからどの程度区別可能であるか（非類似度）を判定することができる。
【００８１】
説明を簡略化するために、Ｎ個のフレームを有するソース・デジタル・ビデオについて述べる。この説明は決して限定することを意図したものではなく、あらゆるその他の形態のデジタル・メディアを用いてもよい。
【００８２】
上述した特徴ベクトルのフレーム索引付き集合は、Ｖ＝｛ｖi：ｉ＝１，…，Ｎ｝と示し得る。特徴ベクトルｖl〜ｖrから構成されるデジタル・ビデオのセグメントＱ、即ち、Ｑ＝｛ｖi：ｉ＝ｌ，…，ｒ｝⊂Ｖについて考える。距離測度ｄ（．，．）を選択することによって、２つのフレームの類似度が定量化される。あらゆる候補キーフレームｖj∈Ｑ及びセグメントＱに対する平均類似度Ｓは、以下の式で表される。
【００８３】
以下、主要な数式（１）から（２４）において、文字Ｓ，Ｑ，ｊ，ｖｉ，ｖｊ，ｖｍ・・・等一部の文字は斜体にて示されている。
【００８４】
【数１】
0004613569.tif 000002
Ｓは、キーフレームｖjのクラス内平均類似度、即ち、キーフレームｖjが属するセグメントに対するキーフレームｖjの類似度である。Ｃは、クラス外平均類似度、即ち、そのデジタル・メディアの他のセグメントに対するキーフレームｖjの類似度である。
【００８５】
【数２】
0004613569.tif 000003
Ｃを以下のように定義する。
【００８６】
【数３】
0004613569.tif 000004
図５に示されているように、要素Ｓ（ｉ，ｊ）＝ｄ（ｖi，ｖj）を有する類似度マトリックスを用いると、これらの計算が容易になる。好適な代表キーフレームｊ４０１は、高いクラス内平均類似度Ｓを有する。つまり、このキーフレームｊ４０１は、平均して、キーフレームｊ４０１が属するセグメントを構成しているフレームに非常に類似している。マトリックス４００を参照すると、候補キーフレームｊ４０１のクラス内平均類似度Ｓは、キーフレームｊをセグメントＣk４０３のその他のクラス内フレームのそれぞれと比較することによって決定される。このセグメントＣk４０３のクラス内フレームは、マトリックス４００の空白マス４０５で表されている。
【００８７】
また、識別するためには、候補キーフレームｊ４０１は、Ｃを最小化しなくてはならない。つまり、候補キーフレームｊ４０１は、その他のセグメントに属するフレーム及びゆえにキーフレームにできるだけ類似していてはならない。キーフレームｊ４０１のクラス外平均類似度Ｃは、キーフレームｊ４０１をデジタル・メディア４０２のクラス外フレームと比較することによって決定される。２つの値ＳとＣの差及び／又は比率の計算値は、候補キーフレームが両方の基準を同時にどの程度よく満たしているかを示す。
【００８８】
従って、差分の性能指数は以下の式で算出し得る。
【００８９】
【数４】
0004613569.tif 000005
一方、比率の性能指数は以下の式で算出し得る。
【００９０】
【数５】
0004613569.tif 000006
上記２つの式において、下付き文字Ｓ及びＲはそれぞれ、減算式及び除算式を表す。
【００９１】
別の実施形態では、識別度対自己類似度をトレードオフ又はバイアスするのが望ましい。これらの場合には、非負定数αs及びβsを用いて、重み付けの計算値を以下のように求めてもよい。
【００９２】
【数６】
0004613569.tif 000007
一方、定数αr及びβrを用いる比率の重み付け性能指数は、以下の式で算出される。
【００９３】
【数７】
0004613569.tif 000008
下付き文字ｓ及びｒはそれぞれ、この定数が減算式及び除算式に関するものであることを示している。どちらの場合にも、βに対するαの割合を高くすると、自己類似度の重要度が高くなり、逆にαに対するβの割合を高くすると、得られるキーフレームの識別度が高くなる。
【００９４】
セグメントＱに対して最適な代表キーフレームｖ*を選択するには、Ｑにおける全フレームに関するグッドネス・ファンクション(goodness function)Ｆを以下のように最大化する。
【００９５】
【数８】
0004613569.tif 000009
【００９６】
各セグメントに対する複数のキーフレーム
別の実施形態では、ユーザは、各セグメントを表すために複数のキーフレームを選択することができる。このような実施形態において、セグメントＱ＝｛ｖl，…，ｖr｝とサブセグメントＰ＝｛ｖj，…，ｖk｝⊂Ｑとの平均自己類似度Ｓは、以下の式で表される。
【００９７】
【数９】
0004613569.tif 000010
セグメント化に関し、相互類似度は以下のように定義される。
【００９８】
【数１０】
0004613569.tif 000011
上記等式（８）及び（９）の結果を利用するのであれば、それぞれ下記等式（１０）、（１１）、（１２）、及び（１３）で識別されているような、上記等式（３）、（４）、（５）、及び（６）の修正版のうちのいずれを用いて、所望のキーフレームを選択してもよい。
【００９９】
【数１１】
0004613569.tif 000012
【０１００】
【数１２】
0004613569.tif 000013
【０１０１】
【数１３】
0004613569.tif 000014
【０１０２】
【数１４】
0004613569.tif 000015
セグメントＱに対して代表キーフレームｖ*の最適なグループを選択するには、Ｑにおける全フレームに関するグッドネス・ファンクションＦを以下のように最大化する。
【０１０３】
【数１５】
0004613569.tif 000016
【０１０４】
キーフレーム線形識別選択
さらに別の実施形態では、線形識別法を利用してキーフレームを選択してもよい。情報検索のためのテキスト・ドキュメント集合の索引付けのために、非常に首尾よく、スペクトル法が用いられてきた。１つの例としては、潜在意味的索引付け（ＬＳＩ：latent semantic indexing）がある。このような技法は、特徴空間における非本質的な変化を無視することにより次元の縮小に用いられる。分類の過程において、次元を縮小させる線形手法を用いれば、ラベル付き訓練データをさらに利用することによって、次元が縮小された空間において分散を「形付け」、識別を容易にすることができる。
【０１０５】
フィッシャー(Fisher)の線形識別法は、このような技法の一例である。特徴ベクトルのフレーム索引付き集合Ｖ＝｛ｖ1，…，ｖN｝に話を戻すと、セグメント化後、ＶはＫ個のセグメントに分割され、特徴ベクトルは次式で表される。
【０１０６】
【数１６】
0004613569.tif 000017
ここで、各特徴ベクトルｖiは、正確に１セグメントＣkの１要素となっている。各セグメントに対し、平均特徴ベクトルμkが以下の式で算出される。
【０１０７】
【数１７】
0004613569.tif 000018
上記式において、Ｎkは、セグメントＣkにおけるフレームの数である。μは、ビデオ全体に関して算出される平均特徴ベクトルを示している。次に、クラス内分散マトリックスを以下のように定義する。
【０１０８】
【数１８】
0004613569.tif 000019
また、クラス外分散マトリックスを以下のように定義する。
【０１０９】
【数１９】
0004613569.tif 000020
所望の次元Ｄに関し、変換は以下の式で表される。
【０１１０】
【数２０】
0004613569.tif 000021
【０１１１】
【数２１】
0004613569.tif 000022
列ベクトルｗiは一般固有ベクトルであり、最大固有値Ｄは以下の式を満たす。
【０１１２】
【数２２】
0004613569.tif 000023
ＷFLDは、特徴フレームデータを、Ｄ×ＮマトリックスＵ＝ＷFLDTＶに投影する。変換が最適化されることによって、同じセグメントのフレームから抽出された特徴が集められると同時に、これらの特徴は他のセグメントの特徴と区別される。その結果、キーフレームの選択が簡単になり、特徴ベクトルが各セグメントの平均特徴ベクトルに最も近いフレームを決定すればよい。線形性により、以下の式が成り立つ。
【０１１３】
【数２３】
0004613569.tif 000024
次に、各セグメントに対するキーフレームが、以下の式に基づいて選択される。
【０１１４】
【数２４】
0004613569.tif 000025
或いは、各セグメントに対するキーフレームは、以下の式に基づいて選択されてもよい。
【０１１５】
【数２５】
0004613569.tif 000026
次元の縮小により、各クラスの特徴データ内の代表モードが強調され、特異な変化は無視される。同時に、この線形識別投影法は、特徴をクラスの中で区別しやすいように変換するようになっている。変換された特徴空間におけるモードは合わせて、識別に向けて最適化される。これにより、次元の縮小とキーフレームの選択を同時に行う、合理的な方法が提供される。
【実施例】
【０１１６】
説明のために、本発明の実施形態による、デジタル・メディア集合に対するキーフレーム識別選択の実施例を以下に示す。この実施例は、本発明の実施形態の使用法の理解を促すためのものであり、決して限定することを意図したものではない。
【０１１７】
図７及び図８は、ソース・デジタル・メディア（この実施例では、従来技術（図７）及び本発明の実施形態（図８）を利用したゴルフ指導用デジタル・ビデオ）に対するキーフレーム選択の結果を示している。このソース・デジタル・メディアは、７つの異なるセグメントにセグメント化され、各セグメントは、ソース・デジタル・メディア内に含まれた異なるゴルフのスイングを表している。このソース・デジタル・メディアは、わずかな細部のみが異なる非常に類似したショットをいくつか含んでいる。セグメント化後、各セグメントのフレームに対して特徴ベクトルが算出される。これらの特徴ベクトルが比較され、セグメントに対するキーフレームが選択されて識別される。
【０１１８】
図７は、従来技術、即ち、キーフレームの非識別選択技法を用いて、ソース・デジタル・メディアから選択されたキーフレーム６０１1、６０１2、６０１3、６０１4、６０１5、６０１6、６０１7を示している。これに対し、図８は、本発明の実施形態によって実施された、キーフレームの識別選択の結果を示している。この差は明らかである。つまり、識別選択されたキーフレーム６０２1、６０２2、６０２3、６０２4、６０２5、６０２6、６０２7は、７つのセグメントのうちの６つが明らかに異なっているのに対して、非識別技法により選択されたキーフレームは、図７に示されているように、４つしか区別がつかない。この実施例では、上記米国特許第６，５４２，８６９号に記載されていると共に、図５に示されているように、フレーム・パラメータに低次ＤＣＴ係数を用い、類似度マトリックスを生成するのにコサイン距離関数を用いた。
【０１１９】
従って、キーフレーム識別選択法を用いれば、各セグメントの代表であると同時に互いに区別可能であるキーフレームがユーザに提供される。
【産業上の利用可能性】
【０１２０】
本発明の実施形態は、デジタル・メディアが管理若しくは処理されるシナリオであれば、どのようなシナリオにも適用できる。例としては、ビデオ編集ソフトウェア、ビデオ・スチルカメラ、グラフィカル・ファイル・ブラウザ、並びに、セットトップ・ボックス及びＰＶＲが挙げられる。ビデオ編集用の多くのソフトウェア・パッケージでは、選択及び編集のために、キーフレームがアイコンとして用いられて、ビデオ・クリップが表示されている。図８から分かるように、同じショットの複数バージョン（「テイク」）から選択する場合には、特徴的なキーフレームがあると特に役に立つ。
【０１２１】
容量の大きなハードディスク記憶装置を備えたビデオ・スチルカメラがまさに市場に出始めたところであり、短いビデオ・クリップを記録することのできるデジタル・スチルカメラも人気がある。これらの装置は全て、通常、小さなディスプレイ上において、既に記録されたメディアをブラウジングする機能を一般的に有している。特徴的なキーフレームを用いることによって、記憶されたメディアを有効に表示することができると共に、記録されたシーンの適切な「テイク」を削除してしまうというような誤りをユーザが冒さないようにすることができる。
【０１２２】
ほとんどのデスクトップ・ウィンドウィング・システムは、グラフィカル・データファイルをサムネイル画像として見ることができるようにする「プレビュー」モードを含む。特に、この場合、即ち、多数のビデオ・セグメントを含み得る大きなディレクトリをブラウジングする場合には、キーフレーム識別選択法が有用である。上述したように、本発明の実施形態は、あらゆる集合及び／又は形態のデジタル・メディアに適している。例えば、特徴的なキーフレームを選択することによって、ビデオ・セグメントと全く同じ方法で、画像集合を表示することができる。画像グループ（例えば、画像フォルダや画像ディレクトリ）を扱う画像管理プログラムも、集合全体を１つの特徴的なキーフレームで表示することができるので、本発明の実施形態が有効である。
【０１２３】
パーソナル・ビデオ・レコーダ（及び昨今増えつつあるセットトップ・テレビジョン・デコーダ・ボックス）は、メディア管理に関する同様の難題、つまり、シンプル且つ簡単なインタフェースで、多数のビデオファイルをどのように表示し、そこからどのように選択するかという難題を抱えている。インタフェースに特徴的なキーフレームを追加すれば、ユーザは、例えば、カメラの配置、舞台装置及び照明、並びに司会者に関する内容が非常に類似したトーク番組の異なるエディションにおいても、より適切な選択を行うことができる。
【０１２４】
当然のことながら、上述した特定の実施形態は、本発明の原理を単に例示したものであって、本発明の範囲及び精神から逸脱しない限り、当業者によって様々な変更を行うことができる。従って、本発明の範囲は、添付の特許請求の範囲によってのみ制限される。
【図面の簡単な説明】
【０１２５】
【図１】本発明の実施形態におけるキーフレーム識別選択処理を示す図である。
【図２】本発明の実施形態における異なるタイプのデジタル・メディアを示すブロック図である。
【図３】本発明の実施形態における、数種類の異なる項目のデジタル・メディアを連結させたソース・デジタル・メディアを示すブロック図である。
【図４】本発明の実施形態における他のキーフレーム識別選択処理を示す図である。
【図５】本発明の実施形態において生成される類似度マトリックスＳを示す図である。
【図６】本発明の実施形態を実行するのに利用され得る汎用計算システムのブロック図である。
【図７】キーフレーム非識別選択法を用いて生成された、７つのビデオ・セグメントのキーフレーム・グループを示す図である。
【図８】本発明の実施形態におけるキーフレーム識別選択法を用いて生成された、７つのビデオ・セグメントのキーフレーム・グループを示す図である。
【符号の説明】
【０１２６】
１００、３００    処理
２１０、４０２    デジタル・メディア
４００    マトリックス
４０３    セグメント
４０５    空白マス
５００    計算機アーキテクチャ
５０１    共通バス
６０１、６０２    キーフレーム
【図１】
0004613569.tif 000027
【図２】
0004613569.tif 000028
【図３】
0004613569.tif 000029
【図４】
0004613569.tif 000030
【図５】
0004613569.tif 000031
【図６】
0004613569.tif 000032
【図７】
0004613569.tif 000033
【図８】
0004613569.tif 000034