(57)【特許請求の範囲】
【請求項１】
入力ビデオ・シーケンスのコンテンツを要約する方法であって、前記入力ビデオ・シーケンスは複数のフレームから成り、前記複数のフレームは複数のビデオ・セグメントにグループ分けされ、前記方法は下記要件を備える。
（ａ）前記入力ビデオ・シーケンスにおいて、各フレームについて作成されるフィーチャー・フレーム行列に対して特異値分解を実行することにより得られるフィーチャー空間である洗練フィーチャー空間の原点に最も近いフレーム・クラスターを選択し、
（ｂ）前記洗練フィーチャー空間の原点からの距離に基づいて前記選択フレーム・クラスターにおける視覚的変化の度合いを示すコンテンツ値を算出し、
（ｃ）前記算出コンテンツ値をしきい値として使用して、前記入力ビデオ・シーケンスの残りのフレームを選択することによりクラスター化する。
【請求項２】
請求項１に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記（ａ）において、複数のフレームの各々について前記複数のフレームの各々における空間色分布を示すヒストグラムが作成され、当該ヒストグラムが連結されて形成されるフィーチャー・ベクトルを列として使用して前記フィーチャー・フレーム行列が作成される。
【請求項３】
請求項２の方法であって、
前記（ａ）において、前記複数のフレームの各々が複数のブロックに分割され、前記複数のブロックの各々について、前記複数のブロックの各々における色の分布を示す色空間のヒストグラムが作成される。
【請求項４】
請求項２に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記複数のフレームの各々が複数のブロックに分割され、前記フィーチャー・ベクトルの各々は１つの色空間における複数のヒストグラムから成り、前記複数のヒストグラムの各々は前記複数のブロックの１つに対応する。
【請求項５】
請求項１に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記特異値分解は、前記入力ビデオ・シーケンスから固定の間隔で選択されたフレームを使用して実行される。
【請求項６】
請求項５に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記選択フレームは、フレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に配列され、前記フィーチャー・フレーム行列に対して前記特異値分解が実行される。
【請求項７】
請求項１に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記特異値分解が行列を生成し、前記行列の各列は、前記入力ビデオ・シーケンスのフレームに対応する洗練フィーチャー空間内の１つのフレームを表す。
【請求項８】
請求項１に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、以下のステップをさらに備える。
（ｄ）前記クラスター化フレームを使用して前記入力ビデオ・シーケンスの要約を表すモーション・ビデオを出力する。
【請求項９】
請求項１に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
（ｅ）複数のキーフレームを出力するステップをさらに備え、前記複数のキーフレームの各々は前記クラスター化フレームを表す。
【請求項１０】
請求項１に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、前記（ｃ）は下記を備える。
（ｃ）（１）前記洗練フィーチャー空間内の複数のベクトルを、前記ベクトルの各々から前記洗練フィーチャー空間表現の原点までの距離に基づいて昇順にソートする。
（ｃ）（２）前記洗練フィーチャー空間表現の原点に最も近い前記ソート済みベクトルから１つのベクトルを選択し、前記選択ベクトルを第１のクラスターに含める。
（ｃ）（３）前記洗練フィーチャー空間内の複数のソート済みベクトルについて、前記複数のソート済みベクトルの各々と前記複数のクラスターの各々に含まれるベクトルとの距離と、前記複数のクラスターの各々に含まれる前記コンテンツ値に基づいて選択することにより、複数のクラスターにクラスター化する。
【請求項１１】
請求項１０に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記（ｃ）（３）において、前記複数のソート済みベクトルが、前記複数のクラスターの各々に含まれるコンテンツ値が前記第１のクラスターに含まれるコンテンツ値を超えないように、前記複数のクラスターにクラスター化される。
【請求項１２】
請求項１０に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記複数のソート済みベクトルの各々と前記複数のクラスターの各々に含まれるベクトルとの距離の差異と、前記第１のクラスターに含まれるベクトル間の平均距離に基づいて、前記第１のクラスターがフレームで構成される。
【請求項１３】
請求項１０に記載の入力ビデオ・シーケンスのコンテンツを要約する方法であって、
前記複数のソート済みベクトルの各々と前記複数のクラスターの各々に含まれるベクトルとの距離の差異と、前記複数のクラスターの前記各々に含まれるフレーム間の平均距離に基づいて、前記複数のクラスターの各々がフレームで構成される。
【請求項１４】
入力ビデオ・シーケンスを要約する方法であって、前記方法は下記要件を備える。
（ａ）前記入力ビデオ・シーケンスからフレームを選択し、前記選択フレームは固定の間隔で抽出され、
（ｂ）前記選択フレームを使用して、フレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列を作成し、
（ｃ）各フレームについて作成される前記フィーチャー・フレーム行列に対して特異値分解を実行することにより得られるフィーチャー空間である洗練フィーチャー空間内の前記ビデオ・シーケンスを表現する行列を取得し、
（ｄ）前記洗練フィーチャー空間内の、原点に最も近いビデオ・セグメントに対応する１つのクラスターを選択し、
（ｅ）前記洗練フィーチャー空間の原点からの距離に基づいて前記選択フレーム・クラスターにおける視覚的変化の度合いを示すコンテンツ値を算出し、
（ｆ）前記算出コンテンツ値をしきい値として使用して、前記入力ビデオ・シーケンス内のフレームを選択することによりクラスター化する。
【請求項１５】
入力ビデオ・シーケンスを分割する方法であって、前記入力ビデオ・シーケンスは複数のフレームから成り、前記複数のフレームは複数のビデオ・ショットにグループ化され、前記方法は下記要件を備える。
（ａ）前記複数のフレームの各々と、前記複数のフレームの各々に時間において先行するフレームとの間の類似度を算出し、
（ｂ）前記算出類似度に基づいて、前記入力ビデオ・シーケンスを前記複数のビデオ・ショットに分割し、
前記類似度が、前記入力ビデオ・シーケンスの洗練フィーチャー空間を使用して算出され、
前記入力ビデオ・シーケンスの洗練フィーチャー空間が、前記入力ビデオ・シーケンスのフレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に対して特異値分解を実行して作成される。
【請求項１６】
請求項１５に記載の入力ビデオ・シーケンスを分割する方法であって、
前記特異値分解が前記入力ビデオ・シーケンスから固定の間隔で選択されたフレームを使用して実行される。
【請求項１７】
請求項１６に記載の入力ビデオ・シーケンスを分割する方法であって、
前記選択フレームは、フレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に配列され、前記フィーチャー・フレーム行列に対して前記特異値分解が実行される。
【請求項１８】
請求項１７に記載の入力ビデオ・シーケンスを分割する方法であって、
前記実行済み特異値分解が行列を生成し、前記生成行列の各列が、前記入力ビデオ・シーケンス内の１つのフレームを表す前記洗練フィーチャー空間内の１つのフレームから成る。
【請求項１９】
入力ビデオ・シーケンス内における第１および第２のフレーム間の類似度を決定するための方法であって、前記方法は下記要件を備える。
（ａ）前記入力ビデオ・シーケンスの洗練フィーチャー空間を算出する。
（ｂ）前記洗練フィーチャー空間を使用して、前記第１および第２のフレーム間の前記類似度を算出する。
前記（ａ）において、前記洗練フィーチャー空間が、前記入力ビデオ・シーケンスのフレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に対して特異値分解を実行して算出される。
【請求項２０】
請求項１５に記載の入力ビデオ・シーケンスを分割する方法であって、
前記（ｂ）において前記算出類似度が第１のしきい値類似度を下回る場合は、前記複数のフレームの各々が、前記時間において先行するフレームを含む前記複数のビデオ・ショットの１つに挿入される。
【請求項２１】
請求項１５に記載の入力ビデオ・シーケンスを分割する方法であって、
前記（ｂ）において前記算出類似度が第２のしきい値類似度を上回る場合は、前記複数のフレームの各々がショット境界として指定される。
【請求項２２】
請求項１５に記載の入力ビデオ・シーケンスを分割する方法であって、
前記（ｂ）において前記算出類似度が第１のしきい値類似度と第２のしきい値類似度との中間の場合は、前記複数のフレームから選択した追加のフレームを使用して実行されたさらなる解析に基づいて、前記複数のフレームの各々が前記複数のビデオ・ショットの１つに挿入される。
【請求項２３】
入力ビデオ・シーケンスのコンテンツを要約するためのプログラムを格納するコンピューター読み取り可能な記録媒体であって、前記入力ビデオ・シーケンスは複数のフレームから成り、前記複数のフレームは複数のビデオ・セグメントにグループ分けされ、前記プログラムは下記要件を備える。
（ａ）前記入力ビデオ・シーケンスにおいて、各フレームについて作成されるフィーチャー・フレーム行列に対して特異値分解を実行することにより得られるフィーチャー空間である洗練フィーチャー空間の原点に最も近いフレーム・クラスターを選択し、
（ｂ）前記洗練フィーチャー空間の原点からの距離に基づいて前記選択フレーム・クラスターにおける視覚的変化の度合いを示すコンテンツ値を算出し、
（ｃ）前記算出コンテンツ値をしきい値として使用して、前記入力ビデオ・シーケンス内の残りのフレームを選択することによりクラスター化する。
【請求項２４】
請求項２３に記載のコンピューター読み取り可能な記録媒体であって、
前記（ａ）において、複数のフレームの各々について前記複数のフレームの各々における空間色分布を示すヒストグラムが作成され、当該ヒストグラムが連結されて形成されるフィーチャー・ベクトルを列として使用して前記フィーチャー・フレーム行列が作成される。
【請求項２５】
請求項２４に記載のコンピューター読み取り可能な記録媒体であって、
前記（ａ）において、前記複数のフレームの各々が複数のブロックに分割され、前記複数のブロックの各々について、前記複数のブロックの各々における色の分布を示す色空間のヒストグラムが作成される。
【請求項２６】
請求項２４に記載のコンピューター読み取り可能な記録媒体であって、
前記複数のフレームの各々が複数のブロックに分割され、前記フィーチャー・ベクトルの各々は１つの色空間における複数のヒストグラムから成り、前記複数のヒストグラムの各々は前記複数のブロックの１つに対応する。
【請求項２７】
請求項２３に記載のコンピューター読み取り可能な記録媒体であって、
前記特異値分解は、前記入力ビデオ・シーケンスから固定の間隔で選択されたフレームを使用して実行される。
【請求項２８】
請求項２７に記載のコンピューター読み取り可能な記録媒体であって、
前記選択フレームは、フレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に配列され、前記フィーチャー・フレーム行列に対して前記特異値分解が実行される。
【請求項２９】
請求項２４に記載のコンピューター読み取り可能な記録媒体であって、
前記特異値分解が行列を生成し、前記行列の各列は、前記入力ビデオ・シーケンスのフレームに対応する洗練フィーチャー空間内の１つのフレームを表す。
【請求項３０】
請求項２３に記載のコンピューター読み取り可能な記録媒体であって、
（ｄ）前記クラスター化フレームを使用して前記入力ビデオ・シーケンスの要約を表すビデオを出力するステップをさらに備える。
【請求項３１】
請求項２３に記載のコンピューター読み取り可能な記録媒体であって、
（ｅ）複数のキーフレームを出力するステップをさらに備え、前記複数のキーフレームの各々は前記クラスター化フレームを表す。
【請求項３２】
請求項２３に記載のコンピューター読み取り可能な記録媒体であって、前記（ｃ）は下記を備える。
（１）前記洗練フィーチャー空間内の複数のベクトルを、前記ベクトルの各々から前記洗練フィーチャー空間の原点までの距離に基づいて昇順にソートする。
（２）前記洗練フィーチャー空間の原点に最も近い前記ソート済みベクトルから１つのベクトルを選択し、前記選択ベクトルを第１のクラスターに含める。
（３）前記洗練フィーチャー空間内の複数のソート済みベクトルについて、前記複数のソート済みベクトルの各々と前記複数のクラスターの各々に含まれるベクトルとの距離と、前記複数のクラスターの各々に含まれる前記コンテンツ値に基づいて選択することにより、複数のクラスターにクラスター化する。
【請求項３３】
請求項２８に記載のコンピューター読み取り可能な記録媒体であって、
前記（３）において、前記複数のソート済みベクトルが、前記複数のクラスターの各々に含まれるコンテンツ値が前記第１のクラスターに含まれるコンテンツ値を超えないように、前記複数のクラスターにクラスター化される。
【請求項３４】
請求項２８に記載のコンピューター読み取り可能な記録媒体であって、
前記複数のソート済みベクトルの各々と前記複数のクラスターの各々に含まれるベクトルとの距離の差異と、前記第１のクラスターに含まれるベクトル間の平均距離に基づいて、前記第１のクラスターがフレームで構成される。
【請求項３５】
請求項２８に記載のコンピューター読み取り可能な記録媒体であって、
前記複数のソート済みベクトルの各々と前記複数のクラスターの各々に含まれるベクトルとの距離の差異と、前記複数のクラスターの前記各々に含まれるフレーム間の平均距離に基づいて、前記複数のクラスターの各々がフレームで構成される。
【請求項３６】
入力ビデオ・シーケンスのコンテンツを要約するためのプログラムを格納するコンピューター読み取り可能媒体であって、前記プログラムは下記要件を備える。
（ａ）前記入力ビデオ・シーケンスから固定の間隔でフレームを選択し、
（ｂ）前記選択フレームを使用して、フレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列を作成し、
（ｃ）各フレームについて作成される前記フィーチャー・フレーム行列に対して特異値分解を実行することにより得られるフィーチャー空間である洗練フィーチャー空間内の前記ビデオ・シーケンスを表現する行列を取得し、
（ｄ）前記洗練フィーチャー空間内の、原点に最も近いビデオ・セグメントに対応する１つのクラスターを選択し、
（ｅ）前記洗練フィーチャー空間の原点からの距離に基づいて前記選択フレーム・クラスターにおける視覚的変化の度合いを示すコンテンツ値を算出し、
（ｆ）前記算出コンテンツ値をしきい値として使用して、前記入力ビデオ・シーケンス内のフレームを選択することによりクラスター化する。
【請求項３７】
入力ビデオ・シーケンスを分割するためのプログラムを格納するコンピューター読み取り可能媒体であって、前記入力ビデオ・シーケンスは複数のフレームから成り、前記複数のフレームは複数のビデオ・ショットにグループ化され、前記プログラムは下記要件を備える。
（ａ）前記複数のフレームの各々と時間において後続のフレームとの間の類似度を算出し、
（ｂ）前記算出類似度に基づいて、前記入力ビデオ・シーケンスを前記複数のビデオ・ショットに分割し、
前記類似度が、前記入力ビデオ・シーケンスの洗練フィーチャー空間を使用して算出され、
前記洗練フィーチャー空間が、前記入力ビデオ・シーケンスのフレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に対して特異値分解を実行して作成される。
【請求項３８】
請求項３７に記載のコンピューター読み取り可能な記録媒体であって、
前記特異値分解が前記入力ビデオ・シーケンスから固定の間隔で選択されたフレームを使用して実行される。
【請求項３９】
請求項３８に記載のコンピューター読み取り可能な記録媒体であって、
前記選択フレームは、フレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に配列され、前記フィーチャー・フレーム行列に対して前記特異値分解が実行される。
【請求項４０】
請求項３９に記載のコンピューター読み取り可能な記録媒体であって、
前記実行済み特異値分解が行列を生成し、前記生成行列の各列が、前記入力ビデオ・シーケンス内の１つのフレームを表す前記洗練フィーチャー空間内の１つのフレームから成る。
【請求項４１】
入力ビデオ・シーケンス内における第１および第２のフレーム間の類似度を決定するためのプログラムを格納するコンピューター読み取り可能媒体であって、前記プログラムは下記要件を備える。
（ａ）前記入力ビデオ・シーケンスの洗練フィーチャー空間を算出する。
（ｂ）前記洗練フィーチャー空間を使用して、前記第１および第２のフレーム間の前記類似度を算出し、
前記（ａ）において、前記洗練フィーチャー空間が、前記入力ビデオ・シーケンスのフレームに対して作成されるフィーチャー・ベクトルを列として使用して得られるフィーチャー・フレーム行列に対して特異値分解を実行して算出される。
【請求項４２】
請求項３７に記載のコンピューター読み取り可能な記録媒体であって、
前記（ｂ）において前記算出類似度が第１のしきい値類似度を下回る場合は、前記複数のフレームの各々が、前記時間において先行するフレームを含む前記複数のビデオ・ショットの１つに入れられる。
【請求項４３】
請求項３７に記載のコンピューター読み取り可能な記録媒体であって、
前記（ｂ）において前記算出類似度が第２のしきい値類似度を上回る場合は、前記複数のフレームの各々がショット境界として指定される。
【請求項４４】
請求項３７に記載のコンピューター読み取り可能な記録媒体であって、
前記（ｂ）において前記算出類似度が第１のしきい値類似度と第２のしきい値類似度との中間の場合は、前記複数のフレームから選択した追加のフレームを使用して実行されたさらなる解析に基づいて、前記複数のフレームの各々が前記複数のフレームの１つに挿入される。
【請求項４５】
ビデオ・ショットにおける視覚的変化の度合いを算出する方法であって、前記ビデオ・ショットは複数のフレームから成り、前記方法は下記要件を備える。
（ａ）前記複数のフレームについて作成されるフィーチャー・フレーム行列に対して特異値分解を実行し、前記特異値分解は行列を生成し、前記生成行列の各列が、前記複数のフレームのうち１つのフレームに対応する前記特異値分解の実行により得られる洗練フィーチャー空間内の１つのフレームを表し、
（ｂ）前記フレームの前記洗練フィーチャー空間の原点からの距離に基づいて前記ビデオ・ショットにおける視覚的変化の度合いを算出する。
【請求項４６】
請求項４５に記載のビデオ・ショットにおける視覚的変化の度合いを算出する方法であって、
前記（ｂ）が前記ビデオ・ショットにおける視覚的変化の度合いを和
【数１】
0003568117.tif 000017
として算出するステップを備え、ここで、Ｖｉｊは前記行列の要素、rank(A)は前記行列の列数である。
【請求項４７】
ビデオ・ショットにおける視覚的変化の度合いを算出するためのプログラムを格納するコンピューター読み取り可能媒体であって、前記ビデオ・ショットは複数のフレームから成り、前記プログラムは下記要件を備える。
（ａ）前記複数のフレームについて作成されるフィーチャー・フレーム行列に対して特異値分解を実行し、前記特異値分解は行列を生成し、前記生成行列の各列が、前記複数のフレームのうち１つのフレームに対応する前記特異値分解の実行により得られる洗練フィーチャー空間内の１つのフレームを表し、
（ｂ）前記フレームの前記洗練フィーチャー空間の原点からの距離に基づいて前記ビデオ・ショットにおける視覚的変化の度合いを算出する。
【請求項４８】
請求項４７に記載のコンピューター読み取り可能な記録媒体であって、
前記（ｂ）が前記ビデオ・ショットにおける視覚的変化の度合いを和
【数２】
0003568117.tif 000018
として算出するステップを備え、ここで、Ｖｉｆは前記行列の要素、rank(A)は前記行列の列数である。
【請求項４９】
ビデオ・ショットにおける色分布の均等性を算出するための方法であって、前記ビデオ・ショットは複数のフレームから成り、前記方法は下記要件を備える。
（ａ）前記複数のフレームについて作成されるフィーチャー・フレーム行列に対して特異値分解を実行し、前記特異値分解は行列を生成し、前記生成行列の各列が、前記複数のフレームのうち１つのフレームに対応する前記特異値分解の実行により得られる洗練フィーチャー空間内の１つのフレームを表し、
（ｂ）前記フレームの前記洗練フィーチャー空間の原点からの距離に基づいて前記ビデオ・ショットにおける色分布の均等性を算出する。
【請求項５０】
請求項４９に記載のビデオ・ショットにおける色分布の均等性を算出するための方法であって、
前記（ｂ）が前記ビデオ・ショットにおける色分布の均等性を和
【数３】
0003568117.tif 000019
として算出するステップを備え、ここで、前記Ｖｉｊは前記行列の要素、rank(A)は前記行列の列数であり、前記σｊは前記特異値分解において得られた特異値である。
【請求項５１】
ビデオ・ショットにおける色分布の均等性を算出するためのプログラムを格納するコンピューター読み取り可能媒体であって、前記ビデオ・ショットは複数のフレームから成り、前記方法は下記要件を備える。
（ａ）前記複数のフレームについて作成されるフィーチャー・フレーム行列に対して特異値分解を実行し、前記特異値分解は行列を生成し、前記生成行列の各列が、前記複数のフレームのうち１つのフレームに対応する前記特異値分解の実行により得られる洗練フィーチャー空間内の１つのフレームを表し、
（ｂ）前記フレームの前記洗練フィーチャー空間の原点からの距離に基づいて前記ビデオ・ショットにおける色分布の均等性を算出する。
【請求項５２】
請求項５１に記載のコンピューター読み取り可能な記録媒体であって、
前記（ｂ）が前記ビデオ・ショットにおける色分布の均等性を和
【数４】
0003568117.tif 000020
として算出するステップを備え、ここで、前記Ｖｉｊは前記行列の要素、rank(A)は前記行列の列数であり、前記σｊは前記特異値分解において得られた特異値である。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、特異値分解（ＳＶＤ：ｓｉｎｇｕｌａｒ  ｖａｌｕｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）手法に基づくビデオ要約の手法に関する。本発明はさらに、ユーザーが指定した照会に基づいてビデオ・シーケンスを効果的に検索して取り込むためのツールの提供に関する。本発明は特に、自動検索、索引付け、およびアクセスを目的とするビデオ・シーケンスのショット（ｓｈｏｔ）への分割に関する。最後に、本発明は、ビデオ・ショットの分類と検索を可能にするためにビデオ・ショットからフィーチャーとメタデータを抽出する方法に関する。
【０００２】
【従来の技術】
広範囲にわたるビデオ情報のコンピューター・システムとネットワークへの浸透には、魅力と挑戦の両方が潜む。ビデオには、実世界の光景を最も鮮明かつ忠実に伝えるという魅力がある。その一方で、ビデオ画像は時間シーケンス全体に及ぶ大量で、冗長な、そして構造化されていないデータ・ストリームにより表現されるため、その取り扱いには様々な困難が伴う。多くの場合、膨大なビデオ・データ・コレクションから該当するビデオ・シーケンスやビデオ情報の必要部分を探し出すことはきわめて煩雑な作業となる。インターネットではこの状況はさらに悪化する。現在まで、ニュース放送、エンターテインメント、または製品プロモーションのビデオ画像を提供するウェブサイトは増加の一途をたどってきた。しかし、大多数のホーム・ユーザーが使用できるネットワーク帯域はきわめて限られているため、大量なビデオ画像を数分間、ときには数十分間もかけてやっとダウンロードしたと思ったら、無関係な情報だった、ということが少なくない。
【０００３】
膨大なデータ・コレクションを管理する上で重要なことは、ビデオの特定場面（ｖｉｄｅｏ  ｆｏｏｔａｇｅ）のコンテンツを短くまとめた要約をユーザーに提供し、膨大なビデオ資源を一目で閲覧できるようにすることである。したがって、構造化されていない大量のビデオ画像を魅力的で有益な情報資源にするには、ビデオの特定場面のコンテンツを見渡す全体象を迅速に把握できる閲覧および要約ツール（ｂｒｏｗｓｉｎｇ  ａｎｄ  ｓｕｍｍａｒｉｚａｔｉｏｎ  ｔｏｏｌｓ）が不可欠である。
【０００４】
現在のビデオ閲覧ツールのほとんどは、一連のキーフレームを使用してビデオ・シーケンスのコンテンツの要約を提供する。多数のシステムでは、検出された各シーン・ショット（ｓｃｅｎｅ  ｓｈｏｔ）に対して一定数のキーフレームが使用されている。また、シーン・ショットの変化の量に応じて割り当てるキーフレームを増やすシステムもある。さらに、視覚的な類似度に基づいてキーフレームをクラスター化することにより、キーフレーム間の冗長部分を除去するシステムも見受けられる。既存のビデオ閲覧および要約ツールには、１つの重要な構成要素が欠けている。それは、冗長部分のない良好なビデオ・シーケンス表現を提供するために不可欠なキーフレーム数を推定するメカニズムである。
【０００５】
各シーン・ショットに一定のキーフレーム数を割り当てるだけの簡略な方法には、ビデオ・コンテンツ（ｖｉｄｅｏ  ｃｏｎｔｅｎｔ）の表現の質が低いという欠点がある。一方、活動レベルに応じてキーフレームを調整して割り当てるさらに高度な方法では、生成するキーフレーム数またはキーフレームの生成に使用されるしきい値（例えば、キーフレーム間の類似度の距離または時間間隔など）の供給をユーザーに頼らざるを得ないという欠点がある。この場合、ユーザーは適切な一連のキーフレームを取得するために、システムとの対話を何度も繰り返さなければならない。この方法は、ローカル・ワークステーションに格納された短い一連のビデオ画像を閲覧するには有効である。しかし、インタ−ネット上のビデオ画像にごく狭い帯域幅を使ってネットワークを介してアクセスする場合や、大規模なビデオ・データベース内の各ビデオ画像についてビデオ要約を作成する場合には、この方法ではまったく対処できない。
【０００６】
上記で述べたように、既存のビデオ閲覧およびコンテンツ概覧ツール（ｖｉｄｅｏ  ｂｒｏｗｓｉｎｇ  ａｎｄ  ｃｏｎｔｅｎｔ  ｏｖｅｒｖｉｅｗ  ｔｏｏｌｓ）は、オリジナルのビデオ・シーケンスから抽出されたキーフレームを利用する。これに関連する多数の研究は、ビデオをショットに分割し、検出された各ショットに使用すべき固定キーフレーム数を決定することに集中している。例えば、Ｔｏｎｏｍｕｒａらは各ショットの最初のフレームをキーフレームとして使用する（Ｙ．Ｔｏｎｏｍｕｒａ，Ａ．Ａｋｕｔｓｕ，Ｋ．Ｏｔｓｕｊｉ，ａｎｄ  Ｔ．Ｓａｄａｋａｔａ、「Ｖｉｄｅｏｍａｐａｎｄ  ｖｉｄｅｏｓｐａｃｅｉｃｏｎ：Ｔｏｏｌｓ  ｆｏｒ  ａｎａｔｏｒｍｉｚｉｎｇ  ｖｉｄｅｏ  ｃｏｎｔｅｎｔ（ビデオマップとビデオスペースアイコン：ビデオ・コンテンツを詳細に解析するためのツール）」、Ｐｒｏｃ．ＡＣＭ  ＩＮＴＥＲＣＨＩ‘９３、１９９３年参照）。Ｕｅｄａらは、最初と最後のフレームを使用して各ショットを表現している（Ｈ．Ｕｅｄａ，Ｔ．Ｍｉｙａｔａｋｅ，ａｎｄ  Ｓ．Ｙｏｓｈｉｚａｗａ、「Ｉｍｐａｃｔ：Ａｎ  ｉｎｔｅｒａｃｔｉｖｅ  ｎａｔｕｒａｌ−ｍｏｔｉｏｎ−ｐｉｃｔｕｒｅ  ｄｅｄｉｃａｔｅｄ  ｍｕｌｔｉｍｅｄｉａ  ａｕｔｈｏｒｉｎｇ  ｓｙｓｔｅｍ（インパクト：対話式自然動画像専用マルチメディア・オーサリング・システム）」、Ｐｒｏｃ．ＡＣＭ  ＳＩＧＣＨＩ’９１（ニューオーリンズ）、１９９１年４月参照）。ＦｅｒｍａｎとＴｅｋａｌｐは、各ショット内のフレームをクラスター化し、キーフレームとして最大クラスターの中心に最も近いフレームを選択した（Ａ．Ｆｅｒｍａｉｎ  ａｎｄ  Ａ．Ｔｅｋａｌｐ、「Ｍｕｌｔｉｓｃａｌｅ  ｃｏｎｔｅｎｔ  ｅｘｔｒａｃｔｉｏｎ  ａｎｄ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎｆｏｒ  ｖｉｄｅｏ  ｉｎｄｅｘｉｎｇ（マルチスケール・コンテンツ抽出およびビデオ索引付けのための表現）」、Ｐｒｏｃ．ＳＰＩＥ  ３２２９  Ｍｕｌｔｉｍｅｄｉａ  Ｓｔｏｒａｇｅ  ａｎｄ  Ａｒｃｈｉｖｉｎｇ  ＳｙｓｔｅｍｓＩＩ（マルチメディア記憶およびアーカイブ・システムに関するＳＰＩＥ講演集３２２９）  １９９７年参照）。
【０００７】
上記の同密度キーフレーム割り当てには、カメラのパンやズーム、物体の動きを伴う長いショットが十分に表現されないという明白な欠点がある。この問題に取り組むため、ＤｅＭｅｎｔｈｏｎらは対応するシーン・ショットの活動レベルに基づいて異なる数のキーフレームを割り当てる方法を提案した（Ｄ．ＤｅＭｅｎｔｈｏｎ，Ｖ．Ｋｏｂｌａ，ａｎｄ  Ｄ．Ｄｏｅｒｍａｎｎ、「Ｖｉｄｅｏ  ｓｕｍｍａｒｉｚａｔｉｏｎ  ｂｙ  ｃｕｒｖｅ  ｓｉｍｐｌｉｆｉｃａｔｉｏｎ（曲線の簡素化によるビデオ要約）」、Ｔｅｃｈ．Ｒｅｐ．ＬＡＭＰ−ＴＲ−０１８、Ｌａｎｇｕａｇｅ  ａｎｄ  Ｍｅｄｉａ  Ｐｒｏｃｅｓｓｉｎｇ  Ｌａｂｏｒａｔｏｒｙ（言語およびメディア処理研究所）、メリーランド大学、１９９８年参照）。この文書で説明される方法は、ビデオ・シーケンスを高次元フィーチャー空間（ｈｉｇｈ  ｄｉｍｅｎｓｉｏｎａｌ  ｆｅａｔｕｒｅ  ｓｐａｃｅ）の軌道曲線として表現し、帰納的バイナリ曲線分割アルゴリズム（ｒｅｃｕｒｓｉｖｅ  ｂｉｎａｒｙ  ｃｕｒｖｅ  ｓｐｌｉｔｔｉｎｇ  ａｌｇｏｒｉｔｈｍ）を使用して知覚的に有意な一連のポイントを検出するというものである。これらのポイントは、ビデオ曲線の概算に利用できる。曲線概算は、概算エラーがユーザー指定値を下回るまで繰り返される。これらの知覚的に有意なポイントに対応するフレームが、ビデオ・コンテンツを要約するためのキーフレームとして使用される。曲線分割アルゴリズムは曲率が大きいセグメントほど多数のポイントを割り当てるため、変化の多いショットに割り当てられるキーフレーム数は必然的に多くなる。
【０００８】
ビデオ・シーケンスから抽出されたキーフレームには、重複と冗長部分が含まれることがある。例えば、２人が会話しているＴＶプログラムでは、ビデオカメラは通常２人のショットを交互に切り替え、シーンの全体的な光景を挿入する。上記のキーフレーム選択方法をこのビデオ・シーケンスに適用すると、ほぼ同一のキーフレームが多数生成される。生成されたキーフレームから冗長部分を取り除くため、Ｙｅｕｎｇらは各ビデオショットから１つのキーフレームを選択し、視覚的な類似度と時間の距離に基づいてこれらのキーフレームの階層クラスター化を行い、その後各クラスターにつき１つのキーフレームのみを保持した（Ｍ．Ｙｅｕｎｇ，Ｂ．Ｙｅｏ，Ｗ．Ｗｏｌｆ  ａｎｄ  Ｂ．Ｌｉｕ、「Ｖｉｄｅｏ  ｂｒｏｗｓｉｎｇ  ｕｓｉｎｇ  ｃｌｕｓｔｅｒｉｎｇ  ａｎｄ  ｓｃｅｎｅ  ｔｒａｎｓｉｔｉｏｎｓ  ｏｎ  ｃｏｍｐｒｅｓｓｅｄ  ｓｅｑｕｅｎｃｅｓ（圧縮シーケンスのクラスター化とシーン推移を使用したビデオ閲覧）」Ｐｒｏｃ．ＳＰＩＥ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｎｅｔｗｏｒｋｉｎｇ（マルチメディアのコンピューティングおよびネットワーキングに関するＳＰＩＥ講演集）、ｖｏｌ．２４１７、１９９５年参照）。ＧｉｒｇｅｎｓｏｈｎとＢｏｒｅｃｚｋｙも、階層クラスター化手法を使用してユーザーが指定した数のクラスターにキーフレームをグループ分けした。この方法では、各クラスターについて単一のキーフレームが、ビデオ全長にわたるキーフレームの均等配分とキーフレーム間の最短所要距離の要件により課せられる制約が満たされるように選択される（Ａ．Ｇｉｒｇｅｎｓｏｈｎ  ａｎｄ  Ｊ．Ｂｏｒｅｃｚｌｙ、「Ｔｉｍｅ−ｃｏｎｓｔｒａｉｎｅｄ  ｋｅｙｆｒａｍｅ  ｓｅｌｅｃｔｉｏｎ  ｔｅｃｈｎｉｑｕｅ（時間制約キーフレーム選択手法）」、Ｐｒｏｃ．ＩＥＥＥ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｓｙｓｔｅｍｓ（マルチメディアのコンピューティングおよびシステムに関するＩＥＥＥ講演集）（ＩＣＭＣＳ’９９）１９９９年参照）。
【０００９】
ビデオ・コンテンツの簡潔な要約を作成する上では、オリジナル・ビデオの要約表現が、（１）ほとんど冗長を含まないこと、および（２）同量のコンテンツに同程度の関心を向けること、という２つの条件を満たすことがきわめて重要である。一部の高度なキーフレーム選択方法は変化の度合いに関するこれら２つの課題に取り組んでいるが、キーフレームの生成のために使用される生成すべきキーフレーム数またはしきい値（例えば、キーフレーム間の類似度の距離または概算エラーなど）の供給をユーザーに頼るものが多い。そのため、最適な一連のキーフレームが生成されるまでに、数回の試行を繰り返さなければならないこともある。多数回の試行が必要なことは、ビデオ画像が限られた帯域幅による接続を介してアクセスされる場合や、大規模なビデオ・データベース内の各ビデオ画像について一連のキーフレームを作成する必要がある場合には、決定的な欠点となりうる。
【００１０】
キーフレームを使用したビデオ要約では、上記のキーフレームの選択に関する問題のほかに、キーフレーム自体の限界も問題となる。ビデオ画像は実世界のシーンの連続的な記録である。一連の静的キーフレームでは、その動きやビデオ画像の連続性を捉えることは決してできない。例えば、映画やＴＶプログラムを観ているユーザーは、一連の静的キーフレームよりも、時間の長さが指定された要約モーション・ビデオ（ｓｕｍｍａｒｉｚｅｄ  ｍｏｔｉｏｎ  ｖｉｄｅｏ）の方を望むことは大いに考えられる。
【００１１】
ビデオ・データ管理に重要な第２の側面は、ユーザー指定の照会に基づいてビデオ・シーケンスを効率的に検索して取り込むためのツールの提供である。膨大なビデオ・データ・コレクションから該当するビデオ・シーケンスやビデオ情報の必要部分を探し出すことはきわめて煩雑な作業となる。従来のテキスト索引付けおよび検索手法は、ビデオ画像の索引付けと検索には無力であることがすでに判明している。豊富で有益なビデオ資源を活用するには、ビデオ画像を構造化され、管理可能で、かつ検索可能な媒体に変換する必要がある。
【００１２】
前述の目標に向けた初期ステップには、索引付けとアクセスを可能にするためにビデオ・シーケンスをショットに分割するステップと、および分類、検索、および取り込みを可能にするためにショットからフィーチャー／メタデータを抽出するステップが含まれる。ビデオ・ショットの分割については、これまで多数の方法が提案されてきた。代表的なビデオ・ショット分割方法には、ピクセル値を使用したショット分割がある（Ｋ．Ｏｔｓｕｊｉ，Ｙ．Ｔｏｎｏｍｕｒａ，ａｎｄ  Ｙ．Ｏｈｂａ、「Ｖｉｄｅｏ  ｂｒｏｗｓｉｎｇ  ｕｓｉｎｇ  ｂｒｉｇｈｔｎｅｓｓ  ｄａｔａ（輝度データを使用したビデオ閲覧）」、ＳＰＩＥ  Ｐｒｏｃ．Ｖｉｓｕａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ（ビジュアル通信および画像処理に関するＳＰＩＥ講演集）（ボストン）、ｐｐ．９８０−９８９、１９９１年、およびＡ．Ｈａｍｐａｐｕｒ，Ｒ．Ｊａｉｎ  ａｎｄ  Ｔ．Ｗｅｙｍｏｕｔｈ、「Ｄｉｇｉｔａｌ  ｖｉｄｅｏ  ｓｅｇｍｅｎｔａｔｉｏｎ（デジタル・ビデオ分割）」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ９４（ＡＣＭマルチメディア９４の講演集）（サンフランシスコ）１９９４年１０月参照）。もう１つのビデオ分割方法は、グローバルまたはローカル・ヒストグラムを使用するものである（Ｈ．Ｕｅｄａ，Ｔ．Ｍｉｙａｔａｋｅ，Ｓ．Ｙｏｓｈｉｚａｗａ、「Ｉｍｐａｃｔ：Ａｎ  ｉｎｔｅｒａｃｔｉｖｅ  ｎａｔｕｒａｌ−ｍｏｔｉｏｎ−ｐｉｃｔｕｒｅ  ｄｅｄｉｃａｔｅｄ  ｍｕｌｔｉｍｅｄｉａ  ａｕｔｈｏｒｉｎｇ  ｓｙｓｔｅｍ（影響：対話式自然動画像専用マルチメディア・オーサリング・システム）」、Ｐｒｏｃ．ＡＣＭ  ＳＩＧＣＨＩ’９１（ニューオーリンズ）、１９９１年４月参照）。ビデオ分割における運動ベクトルの使用については、Ｈ．Ｕｅｄａらの文書で説明されている（上記参照）。ＭＰＥＧファイルからの離散コサイン変換（ＤＣＴ）係数もビデオショット分割に使用できる（Ｆ．Ａｒｍａｎ，Ａ．Ｈｓｕ，ａｎｄ  Ｍ．Ｙ．Ｃｈｉｕ、「Ｉｍａｇｅ  ｐｒｏｃｅｓｓｉｎｇ  ｏｎ  ｅｎｃｏｄｅｄ  ｖｉｄｅｏ  ｓｅｑｕｎｅｃｅｓ（コード化ビデオ・シーケンスの画像処理）」Ｍｕｌｔｉｍｅｄｉａ  Ｓｙｓｔｅｍｓ（マルチメディア・システム）、ｖｏｌ．ｎｏ．５、ｐｐ．２１１−２１９、１９９４年参照）。
【００１３】
最近では、前述の方法のほかにも多数のビデオ分割手法が開発されている。大多数のビデオ分割方法はフレームペアを比較する単純なアプローチを使用しているため、急なショット境界しか検出できないが、前述の比較操作において追加フレームを使用することにより緩やかなシーン変化を可能にしたさらに高度な分割手法もある（Ｈ．Ｚｈａｎｇ，Ａ．Ｋａｎｋａｎｈａｌｌｉ，ａｎｄ  Ｓ．Ｓｍｏｌｉａｒ、「Ａｕｔｏｍａｔｉｃ  ｐａｒｔｉｔｉｏｎｉｎｇ  ｏｆ  ｆｕｌｌ−ｍｏｔｉｏｎ  ｖｉｄｅｏ（フルモーション・ビデオの自動分割）」、Ｍｕｌｔｉｍｅｄｉａ  Ｓｙｓｔｅｍｓ（マルチメディア・システム）、ｖｏｌ．１、ｐｐ．１０−２８、１９９３年参照）。
【００１４】
【発明が解決しようとする課題】
ビデオ・ショットの取り込みと分類において現在までに最も普及した方法は、最初にビデオ・ショット分割を実行し、次に検出された各ショットからフィーチャーを抽出する追加作業を行い、さらに抽出されたフィーチャーを使用して索引および測定基準を作成することにより、ショットの取り込みおよび分類を行うというものである。この方法をベースとしたシステムでは、前述の複数の処理ステップを同時に行う必要がある。そのため、通常これらのシステムは、計算費用がかさみ、処理時間が長くなるという欠点を持つ。
【００１５】
こうした背景から、入力ビデオ・シーケンスの最適で冗長部分のない要約を自動作成するとともに、最適な一連のキーフレームかまたはユーザー指定の時間にわたるオリジナル・ビデオの要約版を出力することによって、ビデオ閲覧およびコンテンツ概覧に対するユーザーの異なる要件をサポートすることのできる改良手法の必要性が認識されており、その実現が数々の利点をもたらすことは明らかである。
【００１６】
また、索引付けおよびアクセスのためにビデオ・シーケンスをショットに分割するとともに、分類、検索、および取り込みのために分割されたショットからフィーチャー／メタデータを抽出することのできる改良手法の開発も待たれており、その実現が数々の利点をもたらすことは明らかである。
【００１７】
したがって、本発明の１つの目的は、最適で冗長部分のないビデオ・シーケンスを自動作成するためのビデオ画像の分割、分類、および要約のための方法およびシステムを提供することである。
【００１８】
本発明の他の目的は、ビデオの分割および分類を効率的に行うための方法およびシステムを提供することである。
【００１９】
【課題を解決するための手段】
上記および他の機能を達成し、本発明の恩典と利点を実現するため、特異値分解を使用したビデオ要約のための方法とシステムが提供される。本発明の方法は、入力ビデオ・シーケンスに関してフィーチャー−フレーム行列Ａを作成し、それに対して特異値分解を実行する。本発明は、この特異値分解から、次元数の少ない洗練フィーチャー空間（ｒｅｆｉｎｅｄ  ｆｅａｔｕｒｅ  ｓｐａｃｅ）と、入力ビデオ・シーケンスにおける各ビデオ・セグメントの視覚的変化の度合を測定するための測定基準とを導出する。洗練フィーチャー空間では、視覚的変化の度合いを使用してビデオ・セグメントのコンテンツ値（ｃｏｎｔｅｎｔ  ｖａｌｕｅ）が測定される。
【００２０】
本発明の方法は、入力ビデオ・シーケンスに関して最も静的なビデオ・セグメントを検出し、それを情報単位として定義し、このセグメントから計算されたコンテンツ値をビデオ・シーケンスの残存フレームをクラスター化するためのしきい値として使用する。このクラスター化を使用して、最適な一連のキーフレームまたはユーザー指定時間にわたる要約モーション・ビデオのいずれかが生成される。
【００２１】
本発明の他の態様は、ビデオ分割および分類のための方法およびシステムである。本発明の方法によると、入力ビデオ・シーケンスの各フレームと、その先行または後続フレームの間の類似度が計算される。入力ビデオ・シーケンスは次に、計算された類似値に基づいて複数のショットに分割される。類似度の測定基準は、特異値分解特性を使用して定義される。この類似度の測定基準は、視覚的に類似したビデオ・フレームを取り込む用途にも使用される。
【００２２】
上記の類似度測定基準に加えて、ビデオ分類を容易にするため、フレームの色分布の均等性を測定するための測定基準も特異値分解の特性から導出される。
【００２３】
本発明の方法における他の態様には、選択されたフレームをフィーチャー・フレーム行列に配列すること、およびこのフィーチャー・フレーム行列に対して特異値分解を実行することが含まれる。特異値分解の実行により、各列が入力ビデオ・シーケンス内のフレームに対応する洗練フィーチャー空間内のフレームを表現する行列も生成される。
【００２４】
他の態様では、各ショットからフィーチャーが抽出される。
【００２５】
本発明の方法によると、入力ビデオ・シーケンス内のフレーム間の類似度は、入力ビデオ・シーケンスの洗練フィーチャー空間表現を使用して決定される。
【００２６】
さらなる改良には、計算された類似度を少なくとも２つのしきい値類似度と比較すること、およびこの比較の結果に基づいて入力ビデオ・シーケンスの分割を行なうことが含まれる。
【００２７】
【発明の実施の形態】
本発明のビデオ要約手法は、最適で冗長部分のないビデオ要約の自動作成を目的とする。本発明はさらに、入力ビデオ・シーケンスを表現する最適な一連のキーフレーム、またはユーザー指定の時間にわたるオリジナル・ビデオの要約モーション・ビデオのいずれかを出力することによるビデオ閲覧とコンテンツ概覧など、異なるユーザー要件に対応することも目指す。
【００２８】
本発明のビデオ要約方法は、前述の特異値分解を基本的な作業手段として使用する。特異値分解は、高次元の未処理フィーチャー空間から低次元の洗練フィーチャー空間を導出できること、およびフィーチャー空間におけるデータ・セットの本質的な構造を捕捉できることで知られている（Ｓ．Ｄｅｅｒｗｅｓｔｅｒ，Ｓ．Ｄｕｍａｉｓ，Ｇ．Ｐｕｒｎａｓ、Ｔ．Ｌａｎｄａｕｅｒ  ａｎｄ  Ｒ．Ｈａｒｓｈｍａｎ、「Ｉｎｄｅｘｉｎｇ  ｂｙ  ｌａｔｅｎｔ  ｓｅｍａｎｔｉｃａｎａｌｙｓｉｓ（潜在意味論分析による索引付け）」、Ｊｏｕｒｎａｌ  ｏｆ  Ａｍｅｒｉｃａｎ  Ｓｏｃｅｉｔｙ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅ、ｖｏｌ．４１、ｐｐ．３９１−４０７、１９９０年参照）。特異値分解で処理すべきフレーム数を減少させるため、本発明では入力ビデオ・シーケンス内に均等な間隔で配置された一連のフレームが選択される（１０フレームごとに１フレームの割合が望ましい）。本発明の手法では、このサンプル・セット内の各フレームｉに対して、ｍ次元のフィーチャー・ベクトルＡｉが作成される。このＡｉを列として使用して、フィーチャー・フレーム行列Ａ＝［Ａ１、Ａ２．．．Ａｎ］が得られる。その後この行列Ａに対して特異値分解を実行することにより、ｍ次元の未処理フィーチャー空間からｋ次元の洗練フィーチャー空間に各フレームｉが投影される（通常ｋ＜＜ｍ、ただし必須ではない）。この新規のフィーチャー空間では、ビデオ・フレームのノイズと些細な変化は無視され、類似した色分布パターンを持つフレームが互いに近接して配置される。したがって、洗練フィーチャー空間内の各フレームを表すｋ次元のベクトルは、コンテンツ要約用として視覚的に類似したフレームをクラスター化する目的だけでなく、ビデオ・フレームをショットに正確に分割する目的や、検出されたショット間の類似度を照合する目的にも使用できる。
【００２９】
また、当該技術に精通した当業者には明らかなように、洗練フィーチャー空間では、フレーム・クラスターにおける視覚的変化の度合いとその構成フレームが投影される場所との間に強い相関関係が存在する。多数のビデオ画像においては、視覚的な変化の度合いが画像における活動レベルの有効な指標となる。ビデオの特定場面だけに限っても、ほとんど変化のない静的ビデオは豊富な変化を含む動的ビデオよりも伝達する情報量が少ない。これを反映するため、洗練フィーチャー空間の前述の特性に基づいて、洗練フィーチャー空間における構成フレームの場所を使用してビデオ・セグメントのコンテンツ値が決定される。
【００３０】
したがって、コンテンツ値を基に入力ビデオを要約するために、本発明の方法では最初に最も静的なビデオ・セグメントに対応する洗練フィーチャー空間内のフレーム・クラスターを検出し、それを情報単位として定義し、このフレーム・クラスターから計算されたコンテンツ値をしきい値として使用して、洗練フィーチャー空間内の残りのフレームをクラスター化する。クラスター化が完了すると、本発明の方法は各クラスターからキーフレームを選択する。選択されたキーフレームは、クラスターの中心に最も近いフレームである。このように、本発明の方法では、取得した一連のキーフレームに冗長部分がほとんどなくなり、同量のコンテンツに同等の関心が向けられるようになる。ビデオ閲覧とコンテンツ概覧に対する異なるユーザー要件をサポートするため、本発明のシステムは、最適な一連のキーフレームまたはユーザー指定の時間にわたるオリジナル・ビデオの要約モーション・ビデオのいずれかを出力する機能を備える。
【００３１】
ビデオ・セグメントにおける視覚的変化の度合いと洗練フィーチャー空間におけるビデオ・セグメントの構成フレームが投影される場所との強い相関関係に加えて、ビデオ・フレームにおける色分布の均等性とフレーム投影場所の間にも同様の相関関係が存在する。この重要な特性によって、特異値分解がビデオ・ショット分類においてきわめて有用なものとなる。視覚的変化の度合いはビデオ・セグメントの動的レベルを表し、一方、色分布の均等性は色の見え方（ｃｏｌｏｒ  ａｐｐｅａｒａｎｃｅ）を反映する。また、特異値分解の前述の特性により、最適なビデオ要約、正確なビデオ・ショット分割、および視覚的な内容に基づく効果的なショット分類が実現される。
【００３２】
本発明のビデオ要約およびショット分割方法の好適な実施の形態について、以下に詳細に説明する。
「フィーチャー・ベクトルの構成例」
入力ビデオ・シーケンスのビデオ・フレームは、色ヒストグラムを使用した本発明の実施の形態による方法において表現される。このようなヒストグラムを使用することにより、画像フレームにおける全体的な相違をきわめて効果的に検出できるようになる。さらに、ヒストグラムを伴う計算は非常にコスト効果が高いことで知られている。この特性により、長いビデオ・シーケンスの処理において本発明の方法が実行可能となり、またスケーラビリティも確保される。
【００３３】
本発明の方法における１つの実施の形態では、それぞれ原色であるＲ、Ｇ、Ｂの各々について、各５つのビン（合計１２５ビン）を使用して赤緑青（ＲＧＢ）色空間に３次元ヒストグラムが作成される。ビデオ・フレームにおける空間色分布に関する情報を組み込むため、各フレームは９つのブロック（望ましくは３×３の形式）に分割される。前述の３次元色ヒストグラムは９ブロックの各々について作成される。これら９つのヒストグラムはその後互いに連結されて、フレームに関する１１２５次元のフィーチャー・ベクトルを形成する。本発明方法では、フレームｉのフィーチャー・ベクトルをｉ番目の列として使用して、入力ビデオ・シーケンスを表現するフィーチャー−フレーム行列Ａが作成される。通常、小さな画像ブロックには完全な色パレットが含まれないため、行列Ａの内容は過疎である。そのため本発明では、過疎な行列に対しては、従来の特異値分解アルゴリズムと比較してはるかに高速でメモリー効率の良い特異値分解アルゴリズムが使用される。
【００３４】
固定長ベクトルへのコード化が可能な画像フィーチャーであれば、いずれも本発明の方法に利用できる。一方、画像フレームのフィーチャー・ベクトルはフーリエ変換を使用して構成できる。当該技術に精通した当業者には明らかなように、フーリエ・フィーチャー・ベクトルは、サインやコサインなどの一連のフーリエ・カーネルを使用した画像色情報の畳み込みによって構成される。この場合、フィーチャー・ベクトルの座標は画像内における色分布の繰り返し頻度（ｆｒｅｑｕｅｎｃｉｅｓ  ｏｆ  ｔｈｅ  ｃｏｌｏｒ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ）を示すものとなると考えられる。
【００３５】
あるいは、このようなフィーチャー・ベクトルはウェーブレット手順を使用して構成することも可能である。これは異なるカーネル関数を利用する点を除いては前述のフーリエ変換と同じであり、その構造は当該技術ではよく知られている。
「特異値分解」
本発明のビデオ要約、ショット分割、および分類の方法は、以下に定義するように特異値分解をベースとしたものである。ｍ×ｎの行列Ａとし、ｍ≧ｎであるとすると、Ａの特異値分解は以下のように定義される。
【数５】
0003568117.tif 000002
Ｕ＝［Ｕｉｊ］はｍ×ｎ列の正規直交行列（ｍ×ｎ  ｃｏｌｕｍｎ−ｏｒｔｈｏｎｏｒｍａｌ  ｍａｔｒｉｘ）であり、その列は左特異ベクトル（ｌｅｆｔ  ｓｉｎｇｕｌａｒ  ｖｅｃｔｏｒｓ）と呼ばれる。Σ＝ｄｉａｇ（σ１、σ２、．．．σｎ）はｎ×ｎの対角行列であり、その対角要素は降順で並び替えられた非負特異値（ｎｏｎ−ｎｅｇａｔｉｖｅ  ｓｉｎｇｕｌａｒ  ｖｅｃｔｏｒｓ）である。Ｖ＝［Ｖｉｊ］はｎ×ｎの正規直交行列であり、その列は右特異ベクトルと呼ばれる。特異値分解に関する詳細情報は、Ｗ．Ｐｒｅｓｓ  ｅｔ  ａｌ、「Ｎｕｍｅｒｉｃａｌ  Ｒｅｃｉｐｅｓ  ｉｎ  Ｃ：Ｔｈｅ  Ａｒｔ  ｏｆ  Ｓｃｉｅｎｔｉｆｉｃ  Ｃｏｍｐｕｔｉｎｇ（Ｃ言語における数値のレシピ：科学的コンピューティングの技術）」、イギリス、ケンブリッジ、Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ、２ｅｄ．、１９９２年に記載されている。ｒａｎｋ（Ａ）＝ｒの場合、Σは以下の条件を満たす。
【数６】
0003568117.tif 000003
本発明のビデオ要約方法では、フィーチャー・フレーム行列Ａに特異値分解を適用することは以下のように解釈できる。特異値分解によって、色ヒストグラムが占めるｍ次元の未処理フィーチャー空間と、すべての線形独立軸（ａｘｅｓ  ｌｉｎｅａｒｌｙ  ｉｎｄｅｐｅｎｄｅｎｔ）を含むｒ次元洗練フィーチャー空間との間のマッピングが導出される。すなわち、特異値分解は、フレームｉの連結色ヒストグラムである行列Ａ各列ベクトルｉを、行列Ｖの行ベクトル［Ｖｉ１、Ｖｉ２．．．Ｖｉｎ］に変換する。特異値分解はさらに、行列Ａの各行ベクトルｊをマッピングする。これにより、各ビデオ・フレームの連結ヒストグラム入力値ｊの発生カウント情報が、行列Ｕの行ベクトル［ｕｊ１、ｕｊ２．．．ｕｊｎ］に伝達される。
【００３６】
特異値分解では、行列Ａの行数ｍが列数ｎよりも大きいか等しいことが求められる。入力ビデオ・シーケンス内の選択されたフレーム数が各連結色ヒストグラム内の要素数よりも多い場合、特異値分解はＡＴに対して実行されなければならない。その結果、行列ＵとＶの役割が入れ替わる。一般性を保ちながら説明を簡素にするため、以下では行列Ａの処理についてのみ説明する。
【００３７】
特異値分解は上記以外に以下の重要な特性があり、テキストの索引付けと取り込みに広く利用されている。この特性の有効性に関する正式な証明については、Ｇ．Ｇｏｌｕｂ  ａｎｄ  Ｃ．Ｌｏａｎ、「Ｍａｔｒｉｘ  Ｃｏｍｐｕｔａｔｉｏｎｓ（行列の計算）」、バルチモア、Ｊｏｈｎｓ−Ｈｏｐｋｉｎｓ、２ｅｄ．、１９８９年を参照されたい。
【００３８】
特性１：行列Ａの特異値分解が、方程式（１）、Ｕ＝［Ｕ１Ｕ２．．．Ｕｎ］、Ｖ＝［Ｖ１Ｖ２．．．Ｖｎ］、およびσ１≧σ２．．．≧σｒ＞σｒ＋１＝．．．＝σｎ＝０で与えられるとする。この場合、以下に定義される行列Ａｋは、ユークリッドおよびフロベーニウス正規形（Ｅｕｃｌｉｄｅａｎ  ａｎｄ  Ｆｒｏｂｅｎｉｕｓ  ｎｏｒｍｓ）のＡに最も近いランクｋ行列である。
【数７】
0003568117.tif 000004
方程式（３）の式で元の行列の概算値を得るためにｋ個の最大特異値を使用することには重要な意味がある。小さな特異値を切り捨てることは、フィーチャー空間の線形半従属軸（ｌｉｎｅａｒｌｙ  ｓｅｍｉ−ｄｅｐｅｎｄｅｎｔ  ａｘｅｓ）を切り捨てることと同じである。切り捨てられた軸に対応する画像フィーチャーは、ビデオ・シーケンス内の画像のコンテンツを表現する上では実質的に重要ではない。
【００３９】
一方、短縮された洗練フィーチャー空間は、色ヒストグラムと関連ビデオ・フレームの最も重要な基礎構造を捕捉するが、同時にビデオ・フレームのノイズや些細な変化の除去も行う。色ヒストグラム間の小さな相違は無視され、類似した色分布パターンを持つビデオ・フレームがＫ次元の洗練フィーチャー空間内の近接した場所にマッピングされる。値Ｋは、設計パラメーターである。ｋ＝１５０が望ましい。実験により、ｋをこの値にすると満足のいくビデオ要約結果が得られることが判明している。
「特異値分解に基づくビデオ要約」
前述の特性のほかに、特異値分解には本発明のビデオ要約システムの基礎となる以下の重要な特性がある。
特性２：Ａの特異値分解は方程式（１）によって得られる。ここで、Ａ＝［Ａ１．．．Ａｉ．．．Ａｎ］、Ｖｔ＝［Ψ１．．．Ψｉ．．．Ψｎ］、Ψｉ＝［ｖｉ１ｖｉ２．．．ｖｉｎ］Ｔである。洗練フィーチャー空間の原点までの距離Ψｉは、以下により定義される。
【数８】
0003568117.tif 000005
ランク（Ａ）＝ｎの場合、行列Ｖの正規直行特性により、‖Ψｉ‖２＝１となる。ここで、ｉ＝１、２、．．．、ｎである。
【数９】
0003568117.tif 000006
が列ベクトルＡｉをＡｋ回（Ａｉ（１）＝．．．＝Ａｉ（ｋ）＝Ａｉ）にわたり複製することより得られた行列であり、Ｖ’Ｔ＝［Ψ’１．．．φ’１．．．φ’ｋ．．．Ψ’ｎ］が特異値分解から得られた対応する右特異ベクトル行列である場合、‖φ’ｊ‖２＝１／ｋとなる。ここで、ｊ＝１、２、．．．、ｋである。
【００４０】
上記の特性は、行列Ａの列ベクトルＡｉが線形従属する場合、特異値分解の演算によって、方程式（４）で定義される洗練フィーチャー空間内における距離が１に等しいベクトルΨｉに投影されることを示す。Ａｉにいくつかの複製Ａｉ（ｊ）が含まれる場合、投影されたベクトルφ’ｊの距離は減少する。Ａｉに含まれる複製が多いほど、距離φ’ｊは短くなる。
【００４１】
ビデオ・ドメインに関連して、上記の特異値分解特性は静的ビデオ・セグメント（ニュースキャスターや天気図などを映すセグメント）のフレームは、洗練フィーチャー空間の原点に近い場所に投影され、多数の変化（移動する物体、カメラのパンおよびズームを含むセグメント）を含むビデオ・セグメントは原点から遠いポイントに投影される。換言すると、ビデオ・セグメントが投影される場所により、セグメントに含まれる視覚的変化の度合いに関する情報を得ることができるのである。
コンテンツ値の観点からは、視覚的変化をほとんど含まない静的ビデオによって伝達される情報は、多数の変化を含む動的ビデオによって伝達される情報よりも少ない。ビデオ・セグメントＳｉにおける視覚的変化の度合いは、洗練フィーチャー空間内で構成フレームが投影される場所と強い相関関係があることから、以下の数量をクラスター（ビデオ・セグメント）Ｓｉに含まれるコンテンツ値の測定値として使用できる。
【数１０】
0003568117.tif 000007
本発明のシステムは、上記方程式（５）に従って以下の方法で定義されたコンテンツ値を利用する。本発明のシステムは、最初に、入力ビデオ・シーケンス内で最も静的なビデオ・セグメントに対応する、洗練フィーチャー空間の原点に最も近いクラスターを検出する。この最も静的なビデオ・セグメントはその後情報単位として定義され、セグメントから算出されたコンテンツ値は、入力ビデオ・シーケンスの残りのフレームをクラスター化するのためしきい値として使用される。このように、本発明の方法により、オリジナル・ビデオの要約表現に冗長部分がほとんどなくなり、同量のコンテンツに同程度の関心が向けられるようになる。
【００４２】
したがって、本発明のビデオ要約方法の実施の形態は、図１に示される以下の処理手順で構成される。
ステップ１０１：入力ビデオ・シーケンスから固定の間隔（１０フレームに１フレームの間隔が望ましい）でフレームを選択し、これらの選択フレームを使用してフィーチャー・フレーム行列Ａを作成する。
【００４３】
ステップ１０２：行列Ａに特異値分解を実行して行列ＶＴを得る。この行列の各列ベクトルΨｉは、洗練フィーチャー空間内のフレームｉを表す。
【００４４】
ステップ１０３：洗練フィーチャー空間内で最も静的なクラスターを検出し、方程式（５）を用いてこのクラスターのコンテンツ値を算出し、この値をしきい値として使用して、入力ビデオ・シーケンス内の残りのフレームをクラスター化する。
【００４５】
ステップ１０４：導出したクラスターＳｉの各々につき、クラスターに含まれる最長のビデオ・ショットΘｉを検出する。Θｉが１秒間よりも短いクラスターを切り捨てる。
【００４６】
ステップ１０５：ユーザーの要求に応じて、各キーフレームがビデオ・クラスターを表す一連のキーフレームか、またはユーザー指定の時間にわたる要約モーション・ビデオのいずれかを出力する。
【００４７】
当該技術に精通した当業者には明らかなように、上記手順のステップ１０３で最も静的なクラスターを検出することは、洗練フィーチャー空間の原点に最も近いクラスターを検出することに等しい。使用される表記を参照する場合、クラスター化のプロセス全体は図２を参照して以下のように説明できる。
【００４８】
ステップ２０１：洗練フィーチャー空間で、方程式（４）によって定義された距離を使用して全ベクトルΨｉを昇順にソートする。全ベクトルをクラスター化されていないベクトルとして初期化し、クラスター・カウンターＣ＝１に設定する。
【００４９】
ステップ２０２：クラスター化されていないベクトルから、洗練フィーチャー空間の原点に最も近いベクトルを検出し、このベクトルをクラスターＳｃを形成するためのシード・ベクトルとして選択する。クラスターの平均内部距離Ｒ（Ｓｃ）＝０、フレーム・カウントＰｃ＝１に設定する。
【００５０】
ステップ２０３：クラスター化されていないベクトルΨｉの各々について、クラスターＳｃへの最短距離を算出する。これは、以下のように定義される。
【数１１】
0003568117.tif 000008
ここで、Ｄ（Ψｉ、Ψｋ）は、前述の特異値により加重されたユークリッド距離として定義される。方程式（１）に関連する表記を使用すると、前述のユークリッド距離は以下のように表現される。
【数１２】
0003568117.tif 000009
ここで、ｋは洗練フィーチャー空間の減少後の次元数を示す。
ステップ２０４で、クラスター・カウンターＣ＝１の場合は下記のステップ２０５に進む。それ以外の場合はステップ２０７に進む。
【００５１】
ステップ２０５で以下となった場合、ステップ２０６でクラスターＳｉにフレームΨｉを追加する。
Ｒ（Ｓ１）＝０  または
ｄｍｉｎ（Ψｉ、Ｓ１）／Ｒ（Ｓ１）＜５．０
ステップ２０７で以下となった場合、ステップ２０８でクラスターＳｃにフレームΨｉを追加する。
Ｒ（Ｓｃ）＝０  または
ＩＮＦ（Ｓｃ）＜ＩＮＦ（Ｓ１）  または
ｄｍｉｎ（Ψｉ、Ｓｃ）／Ｒ（Ｓｃ）＜２．０
フレームΨｉがクラスターＳｃに追加された場合、フレーム・カウントＰｃを１増やし、コンテンツ値ＩＮＦ（Ｓｃ）を方程式（５）を用いて更新し、Ｒ（Ｓｃ）を以下のように更新する。
【数１３】
0003568117.tif 000010
ステップ２０９：クラスター化されていないポイントが存在する場合、クラスター・カウンターＣを１増やし、ステップ２０２に進む。それ以外の場合は、演算を終了する。
【００５２】
上記の演算では、最初のクラスターと残りのクラスターの増大には異なる条件が使用されていることに留意する必要がある。最初のクラスターは増大の条件として距離の変動ｄｍｉｎ（Ψｉ，Ｓ１）／Ｒ（Ｓ１）を使用し、残りのクラスターは増大プロセスにおいてコンテンツ値と距離の変動とを吟味する。ステップ２０７の条件２は、処理中のクラスターに最初のクラスターと同量の情報が確実に含まれるようにし、条件３は、非常に近接した２つのフレームが分離されて異なるクラスターに入るのを防止する。条件２では、大きな視覚的変動を含む長いビデオ・ショットの一部が複数のクラスターにクラスター化されることがある。この状況が発生すると、複数のキーフレームがこれらのショットに割り当てられる。一方、条件２と３を組み合わせた場合は、コンテンツが視覚的に非常に類似したビデオ・ショットは同じクラスターにクラスター化され、このビデオ・ショットのグループに対して１つのキーフレームだけが割り当てられる。上記の特徴により、本発明のクラスター化方法は既存のクラスター化手法にはない重要な利点を提供する。
【００５３】
さらに本発明のシステムは、上記で説明した要約プロセスのステップ１０５により、もう１つの独自の特徴を提供する。この特徴とは、最適な一連のオリジナル・ビデオのキーフレームか、ユーザー指定の時間にわたる要約バージョンのいずれかを出力できることである。キーフレームの出力モードがユーザーにより選択されると、本発明のシステムは上記で説明された特異値分解とクラスター化の演算を実行する。このシステムは、これにより得られた各クラスターから、クラスターの中心に最も近いフィーチャー・ベクトルを持つフレームを選択し、選択されたフレームをキーフレームとして指定する。
【００５４】
要約ビデオの出力には、さらなる演算が必要である。本発明のシステムはユーザー指定による２つのパラメーターに基づいて要約ビデオを構成する。これらのパラメーターとは、要約ビデオの時間の長さＴｌｅｎ、および要約ビデオに含まれる各ショットの最小表示時間Ｔｍｉｎである。このプロセスは、図３を参照して説明される以下の主演算で構成される。
【００５５】
ステップ３０１：上記のクラスター化プロセスで得られたクラスターの数をＣとし、Ｎ＝Ｔｌｅｎ／Ｔｍｉｎとする。各クラスターＳｉについて、最長のビデオショットΘｉを検出する。
【００５６】
ステップ３０２：Ｃ≦Ｎの場合は下記ステップ３０３に進む。それ以外の場合は、ステップ３０４に進む。
【００５７】
ステップ３０３：ｉ＝１、２、．．．、Ｃに該当する全ショットΘｉを選択し、各ショットに等しい時間長Ｔｌｅｎ／Ｃを割り当てる。
【００５８】
ステップ３０４：ショットΘｉを長さに基づいて降順でソートし、最上位からＮ個のショットを選択し、選択された各ショットに等しい時間長Ｔｍｉｎを割り当てる。
【００５９】
ステップ３０５：時間コードに基づいて選択されたショットをソートし、ソート後の順序に基づいて選択された各ショットから割り当てられた時間長の一部分を取得し、その部分を要約ビデオに挿入する。
【００６０】
ユーザー指定のパラメーターをＴｌｅｎおよびＴｍｉｎとすると、要約ビデオに挿入することのできる最大ビデオ・ショット数はＮ＝Ｔｌｅｎ／Ｔｍｉｎとなる。ショットの総数がＣ≦Ｎの場合、要約ビデオにおける全ショットには１つのスロットが割り当てられる（ステップ３０４）。これ以外の場合は、要約ビデオを満たすためのショットが長さに基づく降順で選択される（ステップ３０４）。ここでは、パラメーターＴｍｉｎは、ユーザーが深さ中心の要約と幅中心の要約のいずれかを選択するための調節ノブとみなすことができる。Ｔｍｉｎの値が小さい場合は、多数の短いショットから成る幅中心のビデオ要約が生成される。Ｔｍｉｎの値が大きい場合は、少数の長いショットから成る深さ中心のビデオ要約が生成される。さらに、クラスター化処理は生成される全クラスターにほぼ同量の情報が含まれるように実行されるため、要約ビデオ内の各選択ショットには必然的に同じ時間長が割り当てられる。
【００６１】
本発明のビデオ要約システムをＣ＋＋のプログラミング言語を使用して実装し、多様な入力ビデオ・シーケンスを使用して評価を行った。本発明のシステムのテストで使用された入力ビデオ・シーケンスは、ニュース報道、ドキュメンタリー、政治討論、および各種イベントの報道などである。各テスト・ビデオ・シーケンスの長さは５分〜３０分である。本発明のビデオ要約システムにより作成された５分間のドキュメンタリーの要約では、テスト入力ビデオ・シーケンスは２９のショットで構成されていた。この２９ショットのうち、１５の主要ショットが複数の行に配置された。画像の各行はオリジナル入力ビデオ・シーケンスの１つのショットを表し、各行の画像数は対応するショットの時間長に比例する。数行の画像は、ショットに割り当てられたキーフレームである。１３番目のショット（行１３に対応）が最も静的なショットとして選択され、残りのショットをクラスターするための情報単位として使用された。ニュースキャスターは、シーケンスの最初（行１）に１回と最後（行１５）に１回の計２回映された。しかし、これら２つのショットは、画像コンテンツの観点からは非常に類似しており、しかも動きがほとんどないため、同じクラスターにまとめられ、右側行１の１つのキーフレームだけが割り当てれらた。ショット２と１４も同じような状況であった。ショット１２はシーケンス内で最長のショットであり、多数の視覚的変化が含まれていた。したがって、ショット１２はショット１０とともに３つのクラスターに分けられ、３つのキーフレームが割り当てられた。同様に、ショット５には多数の視覚的変化が含まれていたため、１つではなく２つのキーフレームが割り当てられた。ここに示したキーフレーム要約のほかに、本発明のビデオ要約システムは、ユーザー指定による時間長のモーション・ビデオ要約を生成する機能も備える。ここに説明した実験では、本発明のシステムにより生成された３０秒間のビデオ要約には、オリジナル・ビデオ・シーケンスの最も重要なショットが含まれていることが実証された。
【００６２】
ビデオ・シーケンスを使用した実験では、本発明のビデオ要約システムには、静的な複製ショットを効果的に抑制しながら、長い動的なビデオ・ショットにはより多くのキーフレームを割り当てる能力があることが示された。
「特異値分解に基づくビデオ分割および分類」
上記で説明した特異値分解手法は、本発明のビデオ分割および分類システムでも使用された。本発明は、特異値分解の前述の特性に基づき、以下に示すショット分割と照合を目的として、方程式（７）により定義される距離測定基準を使用する。
【数１４】
0003568117.tif 000011
ここで、Ψｉ、Ψｊは、洗練フィーチャー空間におけるフレームｉとｊをそれぞれ表すベクトルであり、σｌは特異値分解で得られた特異値を示す。
特異値分解には、前述の重要な特徴のほかに以下の特性がある。
特性３：Ａの特異値分解は方程式（１）で与えられる。ここで、Ａ＝［Ａ１．．．Ａｉ．．．Ａｎ］、ＶＴ＝［Ψ１．．．Ψｉ．．．Ψｎ］、Ａｉ＝［ａ１ｉ、ａ２ｉ．．．ａｍｉ］Ｔ、およびΨｉ＝［ｖｉ１、ｖｉ２．．．ｖｉｎ］Ｔである。Ψｉの特異値加重長を以下のように定義する。
【数１５】
0003568117.tif 000012
ここで、σｊは特異値である。                  （１０）
すると、
【数１６】
0003568117.tif 000013
となる。
特性３は、フレームとショットにおける色分布の均等性の指標として使用できる。Ａｉはフレームｉの連結ヒストグラム・ベクトルであるため、その要素ａｊｉの合計は定数Ｃ（フレームの内のピクセル数に等しい）である。そのため‖Ψｉ‖２Σは、ａ１ｉ＝ａ２ｉ．．．ａｍｉのときに最小になり、要素ａｋｉの１つがＣに等しく、残りの要素がすべてゼロのときには最大になる。したがって、特異値加重長‖Ψｉ‖２Σは対応するフレームｉの色分布の均等性に比例する。この長さは、実質的にすべての色がフレームｉ内に実質的に同量に存在する（すなわち、フレームｉが実質的に均等な色分布のとき）ときに最短になり、フレームｉに１色だけが含まれるときに最長になる。
【００６３】
本発明のビデオ分割および分類方法の好適な実施の形態は、図４に示される以下の主要ステップから成る。
【００６４】
ステップ４０１：入力ビデオ・シーケンスを固定率（１０フレーム／秒が望ましい）でサンプリングし、上記で説明したフィーチャー・フレーム行列Ａを作成する。
【００６５】
ステップ４０２：行列Ａに対して特異値分解を実行して、以下の行列を得る。
Σ＝ｄｉａｇ（σ１、σ２、．．．σｎ）、ＶＴ＝［Ψ１．．．Ψ２．．．Ψｎ］
ステップ４０３：サンプル・セットの全フレームについて方程式（９）により定義された類似度ＳＩＭ（ｉ，ｉ＋１）を算出し、ビデオ・シーケンスを時間軸に沿ってビデオ・ショットに分割する（詳細については以下の分割アルゴリズムを参照）。
【００６６】
ステップ４０４：各ビデオ・ショットΘｓについて、以下の２つの平均長を算出する。
【数１７】
0003568117.tif 000014
【数１８】
0003568117.tif 000015
ここで、Ψｉ∈Θｓ、およびＰ（Θｓ）はショットΘｓに含まれるフレーム数である。上記の２つの値は視覚的変化の度合いと、ショットΘｓにおける色分布の均等性をそれぞれ示す。
【００６７】
ステップ４０５：各ショットΘｓについて平均フィーチャー・ベクトルΨｓを算出する。距離Ｄ（ΨＸ，ΨＹ）はショットΘＸとΘＹとの間の視覚的類似度を定義する。
本発明のアルゴリズムの上記実施の形態では、ステップ４０１と４０２はショット分割のために特異値分解を実行し、ステップ４０３はショット分割そのものを実行する。ステップ４０４と４０５は、ビデオ・シーケンスにおける全ショットの色分布、動的レベル、および視覚的類似度の評価で使用される、検出された各ショットの測定基準を算出する。
【００６８】
ショット分割のステップ（ステップ４０３）では、ＴｌｏｗとＴｈｉｇｈという２つのしきい値が使用される。２つの連続するフレーム間の距離がＴｌｏｗを下回る場合、２つのフレームはそれ以上の吟味を行うことなく同じショットにグループ化される。この距離がＴｈｉｇｈを上回る場合、ショット境界が宣言される。この距離がＴｌｏｗとＴｈｉｇｈの中間である場合、さらに多数のビデオ・フレームを対象とした吟味が追加実行され、検出されたその大きな距離は一時的な変動によるものか、あるいは漸次的なシーンの推移によるものかを決定する。以下のアルゴリズムは、図５に示される本発明のショット分割方法の好適な実施の形態の実装を示す。
【００６９】
ステップ５０１：ショット・カウンターＳ＝１、フレーム索引Ｉ＝１に設定する。
【００７０】
ステップ５０２：フレームＩを持つショットΘｓを最初の要素として作成する。
【００７１】
ステップ５０３：Ｄ（ΨＩ，ΨＩ＋１）≦Ｔｌｏｗの場合は、フレームＩ＋１をショットΘｓに挿入し、Ｉを１増やす（ステップ５０４）。Ｉが最終フレームでない場合はこのステップを繰り返す（ステップ５０５）。最後のフレームの場合は、ステップ５１４に進む。
【００７２】
ステップ５０６：Ｄ（ΨＩ，ΨＩ＋１）＞Ｔｈｉｇｈの場合は、フレームＩとフレームＩ＋１との中間の場所をショット境界としてマークし、ＳとＩを１ずつ増やす。次に、ステップ５０２に戻る。Ｔｌｏｗ＜Ｄ（ΨＩ、ΨＩ＋１）≦Ｔｈｉｇｈの場合は、以下を実行する。
【００７３】
ステップ５０７：条件Ｄ（ΨＩ，ΨＩ＋１）≦Ｔｌｏｗを満足するフレームＸ＞Ｉ＋１を検出する（ステップ５０７）。
【００７４】
ステップ５１０：Ｄ（ΨＸ，Ψ１）＞Ｔｈｉｇｈの場合は、Ｉ＋１とＸの間のフレームを２つのシーン・ショット間の漸次的推移としてマークする（ステップ５０８）。Ｉ＝Ｘ＋１に設定し、ショット・カウンターＳを１増やす（ステップ５０８）。次にステップ５１４に進む。Ｄ（ΨＩ，Ψ１＋１）≦Ｔｈｉｇｈの場合、Ｉ＋１からＸまでのフレームをショットΘｓにグループ化し、Ｉ＝Ｘ＋１に設定する（ステップ５１３）。次にステップ５０３に戻る。
【００７５】
ステップ５１４：最後のフレームに達したら、演算を終了する。達しない場合は、ステップ５０２に戻る。
【００７６】
【表１】
0003568117.tif 000016
本発明のビデオ・ショット分割および分類システムの好適な実施の形態を、合計２時間のＣＮＮニュース・ビデオ・プログラムを使用して評価した。使用されたビデオの特定場面には、急なシーン変化、フェード、ワイプ、ディゾルブなど、考えられるほぼすべての編集効果が含まれていた。また、シーン・カテゴリーも、顔写真、風景、インタビュー、群衆、移動するカメラ／物体など、きわめて多様であった。比較のため、ローカル・ヒストグラムに基づくショット分割方法を同じビデオ・プログラム・セットを使用して実装し、評価した。前述のローカル・ヒストグラム方法を本発明の方法との比較対象に選択したのは、既存の分割手法の間では最も優れたものの１つとして報告されていたためである。Ｊ．Ｂｏｒｅｃｚｋｙ  ａｎｄ  Ｌ．Ｒｏｗｅ、「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｖｉｄｅｏ  ｓｈｏｔ  ｂｏｕｎｄａｒｙ  ｄｅｔｅｃｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ（ビデオ・ショット境界検出手法の比較）」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆＳＰＩＥ：Ｓｔｏｒａｇｅ  ａｎｄ  Ｒｅｔｒｉｅｖａｌ  ｆｏｒ  Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｄａｔａｂａｓｅｓ  ＩＶ（ＳＰＩＥ講演集：イメージおよびビデオ・データベースの記憶および取り込みｉＶ）、ｖｏｌ．２６７０、１９９６を参照のこと。実験結果を表１に示す。
【００７７】
当該技術に精通した当業者には当然明らかなように、急なショット・カット検出については、本発明システムによって再呼び出し（ｒｅｃａｌｌ）と精度が従来の手法に比較して著しく改善される。この劇的な改善は、特異値分解から導出された短縮フィーチャー空間においてフレーム比較を実行し、フレーム距離のドメイン全体を低、灰色、高のゾーンに分割するＴｈｉｇｈとＴｌｏｗの２つのしきい値を使用することによって達成される。上記で明示したように、２つの連続するフレームの距離が灰色ゾーンの場合は、その長い距離がビデオ・ノイズ、カメラ／物体の動きによるジッター、または純粋なシーン変化のいずれによるものかを決定するために、さらに多数のフレームが吟味される。本発明の方法は、異常値を大幅に減少させることにより、ショット境界検出において高レベルな再呼び出し率と精度を実現する。当該技術における通常の知識を持つ当業者には明らかなように、「異常値」という用語は、ビデオ・コンテンツの変化ではなく、カメラ・ジッターなどの二次的な影響により引き起こされて検出されるシーン変化を意味する。
【００７８】
また、本発明システムは、漸次的なシーン推移を検出し、検出したショットを４つのカテゴリーに分類することができる。これらのカテゴリーとは、例えば、同一ショット、激しい変化を含むショット、著しい変化のない静的なショット、均等な色分布（黒／白フレームなど）のショットなどである。多数のビデオ番組では、同じ人物や同じシーンが繰り返し登場する（ニュースキャスター、インタビューを行う人、インタビューを受ける人など）。これらの同一のシーンを検出することは、重複や冗長部分の検出および除去に不可欠であり、この検出および除去は簡潔なビデオ・コンテンツ要約を生成する上できわめて重要な役割を果たす。一方、豊富な変化を含む動的なショットには、出来事全体を捉えるために行われるカメラ・パンおよびズーム、または高度に動的なシーンに出現する物体の劇的な動きのいずれかが含まれる可能性が高い。動的なショットを識別できることは、最終的な目標である視角的に重要なシーンを検出する上で非常に重要である。
【００７９】
最後に、黒または白のフレームは、ＴＶコマーシャルの直前または直後などのシーン・ショット境界の付近に出現することが多いため、これらのフレームを検出することは多数の用途で有用である。また、メモリー資源の無駄遣いを避けるため、前述の４つのショット・カテゴリーの再呼び出し値と精度値を平均することにより、ショット分類の再呼び出し値と精度値が得られる。
【００８０】
上記の表から、本発明のシステムでは、漸次的シーン推移とショット分類において他のシステムと比較して遜色のない性能が実現されることが当該技術に精通した当業者には明らかとなるであろう。従来のショット分類システムでは発見的手法のルールといくつものしきい値が多用されるのに対し、本発明のシステムは特異値分解の特性から導出された測定基準に基づいて分類される。本発明のこの機能により、ビデオ・ショットの分類を容易に、安定して、そして正確に実行することが可能になる。
【００８１】
したがって、当該技術に精通した当業者には明らかなように、特異値分解による本発明のショット分割および分類システムによって、正確なビデオ・ショット分割およびコンテンツに基づく視覚的なショット分類という前述の目的が十分に達成される。
【００８２】
本書では本発明は好適な実施の形態を使用して説明されたが、当該技術に精通した当業者には明らかなように、付記された請求項に定義される本発明の範囲および精神から乖離することなく、形式および細部においてさまざまな変更を行うことが可能である。
【００８３】
【発明の効果】
以上説明したように、本発明によれば、入力ビデオ・シーケンスの最適で冗長部分のない要約を自動作成するとともに、最適な一連のキーフレームかまたはユーザー指定の時間にわたるオリジナル・ビデオの要約版を出力することによって、ビデオ閲覧およびコンテンツ概覧に対するユーザーの異なる要件をサポートすることができるようになる。
【００８４】
また、本発明によれば、索引付けおよびアクセスのためにビデオ・シーケンスをショットに分割するとともに、分類、検索、および取り込みのために分割されたショットからフィーチャー／メタデータを抽出することができる。
【図面の簡単な説明】
【図１】本発明のビデオ要約方法のブロック・ダイアグラムである。
【図２】本発明のクラスター化方法のブロック・ダイアグラムである。
【図３】本発明の要約作成方法のブロック・ダイアグラムである。
【図４】本発明のビデオ分割および分類方法のブロック・ダイアグラムである。
【図５】本発明のショット分割方法のブロック・ダイアグラムである。
【図１】
0003568117.tif 000021
【図２】
0003568117.tif 000022
【図３】
0003568117.tif 000023
【図４】
0003568117.tif 000024
【図５】
0003568117.tif 000025