(57)【特許請求の範囲】
【請求項１】
ビデオシーケンスにおいて転換を識別するための方法であって、
（ａ）タイミングウインドウサイズｗのタイミングウインドウにより分離される前記ビデオシーケンスでの複数のフレーム対（ｍ，ｎ）の各々に対してフレーム非類似性測度（ＦＤＭ）値を生成するステップであって、前記ｗは１より大きい整数個のフレーム数を表し、前記複数のフレーム対（ｍ，ｎ）の各々に対する前記ＦＤＭ値は、非類似性測度と非類似性測度累積値の比であり、
前記非類似性測度は、フレームｍとｎにおける対応するヒストグラムのビンの値同士の差の絶対値ｘおよび規定される正の数γにより表される、絶対値ｘのγ乗を、全てのビンについて合計した値であり、
変数ｋを用いてフレームｋとフレーム（ｋ＋１）との間の非類似性測度をＤ（ｋ，ｋ＋１）とした場合、前記非類似性測度累積値は、
Σn-1k=mＤ（ｋ，ｋ＋１）
で表される、当該ステップと、
（ｂ）前記複数のフレーム対各々に対する前記ＦＤＭ値を解析することによって前記ビデオシーケンスでの転換を識別するステップであって、前記複数のフレーム対各々に対する前記ＦＤＭ値のうち第１のＦＤＭ値へ第１の閾値条件を適用することによって、対応するフレーム対におけるフレームが転換に該当するか否かを決定するサブステップと、前記第１の閾値条件が満足される場合、前記複数のフレーム対各々に対する前記ＦＤＭ値のうち、前記第１のＦＤＭ値とは異なる１つ以上のＦＤＭ値へ第２の閾値条件を適用することによって、前記転換における開始フレームと終了フレームとを識別するサブステップと、を含む、当該ステップと、
を含む方法。
【請求項２】
前記非類似性測度Ｄnet（ｍ，ｎ）が、
Ｄnet（ｍ，ｎ）≡Σi｜ｈi（ｍ）−ｈi（ｎ）｜γにより定義され、
ｈi（ｍ）はフレームｍに対応するヒストグラムのｉ番目のビン(bin)であり、
ｈi（ｎ）はフレームｎに対応するヒストグラムのｉ番目のビンであり、
γは規定される正の数であり、
前記累積の非類似性測度Ｄcum（ｍ，ｎ）が、
Ｄcum（ｍ，ｎ）≡Σn-1k=mＤnet（ｋ，ｋ＋１）により定義される、
請求項１の方法。
【請求項３】
識別された転換の各々について、前記ビデオシーケンスにおける前記識別された転換の開始フレームの位置と終了フレームの位置とを相対比較することで、前記識別された転換のうち、前記終了フレームが、前記開始フレームから、前記タイミングウインドウサイズｗよりも短い時間の期間で現れるような前記識別された転換を却下するステップ、を更に含む、
請求項１の方法。
【請求項４】
前記ビデオシーケンスに対する前記ＦＤＭ値におけるノイズを特徴付けるステップ、を更に含み、前記第１と第２の閾値条件は、前記ノイズの関数である、請求項１の方法。
【請求項５】
第１のフレーム対に対する前記ＦＤＭ値が、第１の閾値の値Ｔ1、及び前記第１のフレーム対に対する前記ノイズと第１の閾値乗数Ｍ1との積、の最大を超える場合、前記第１の閾値条件が満足され、
前記タイミングウインドウ内に少なくとも１つのフレームを持つ第２のフレーム対に対する前記ＦＤＭ値が、第２の閾値の値Ｔ2、及び前記第２のフレーム対に対する前記ノイズと第２の閾値乗数Ｍ2との積、の最大を下回る場合、前記第２の閾値条件が満足される、
請求項４の方法。
【請求項６】
前記第１のフレーム対に対する前記ＦＤＭ値が、第１の閾値レベルより大きい場合、前記第１の閾値条件が満足され、
前記第２のフレーム対に対する前記ＦＤＭ値が、第２の閾値レベルより小さい場合、前記第２の閾値条件が満足される、
請求項１の方法。
【請求項７】
前記第１の閾値条件は、前記複数のフレーム対の前記ＦＤＭ値におけるピークを識別することに使用され、
前記第２の閾値条件は、前記ピークに対する境界を決定することに使用される、
請求項１の方法。
【請求項８】
前記ステップ（ｂ）は、
（１）前記第１のフレーム対に対する前記ＦＤＭ値へ第１の閾値条件を適用することによって、第１のフレーム対でのフレームが、可能性の転換に対する開始フレームに該当するか否かを決定するステップと、
（２）前記第１の閾値条件が満足される場合、第２のフレーム対に対する前記ＦＤＭ値へ第２の閾値条件を適用することによって、前記可能性の転換が有望な転換であるか否かを決定するステップと、
（３）前記第２の閾値条件が満足される場合、第３のフレーム対に対する前記ＦＤＭ値へ第２の閾値条件を適用することによって、前記有望な転換に対する終了フレームを決定するステップと、
を含む、請求項１の方法。
【発明の詳細な説明】
【０００１】
発明の背景
発明の分野
本発明はビデオ処理に関し、詳細には、デジタルビデオ画像のシーケンスにおけるカット、ワイプ（wipe）、ディゾルブ（dissolve）等の転換の検出に関する。
【０００２】
連邦後援の研究又は開発に関する供述
米国政府は、政府契約番号ＭＤＡ−９０４−９５−Ｃ−３１２６に従い、本発明の少なくとも一部の一定の権利を有する。
【０００３】
関連技術の説明
デジタルビデオシーケンスにおいて、画像即ちフレームは、普通には画素即ちピクセルのアレイにより表され、各画素は、１つ以上の異なる成分により表される。例えば、単色のグレースケール画像では、各画素は、その値が画素の明暗度に相当する成分により表される。ＲＧＢカラーフォーマットでは、各画素は、レッド成分、グリーン成分、及びブルー成分により表される。同様に、ＹＵＶカラーフォーマットでは、各画素は、明暗度（又は輝度）成分Ｙと２つの色（又は色度）成分ＵとＶにより表される。このカラーフォーマットの２４ビットバージョンでは、各画素成分は８ビットの値により表される。
【０００４】
典型的なビデオシーケンスは、ショットと呼ばれる連続するフレームのセットで構成されており、所定ショットのフレームは、同じ基本場面に対応する。ショットは、１つのカメラからの途切れのないフレームのシーケンスである。現在、デジタルビデオをその構成ショットへ分解することへの大きな関心がある。これは、ビデオ材の急速に高まる入手性と、ビデオデータベースに対してインデックスを生成する必要性とにより駆り立てられている。解析は、ビデオの編集及び圧縮に対しても有用である。
【０００５】
デジタルビデオシーケンスにおける異なるショットを識別する１つの方法は、ビデオフレームに対応するヒストグラムを分析することである。フレームのヒストグラムは、ビデオデータのフレームに対する成分値の分布を表す。例えば、３２ビンのヒストグラムは、２４ビットＹＵＶカラーフォーマットで表されるビデオフレームの８ビットＹ成分に対して生成でき、ここで、第１のビンは、フレームで幾つの画素が０と７を含んで０と７間のＹ値を有するかを示し、第２のビンは、幾つの画素が８と１５を含んで８と１５間のＹ値を有するかを示し、以下同様であって、最後の第３２のビンは、幾つの画素が２４８と２５５を含んで２４８と２５５間のＹ値を有するかを示す。
【０００６】
多次元ヒストグラムも、異なる成分からのビットの組合せに基づき生成できる。例えば、３次元（３Ｄ）ヒストグラムが、ＹＵＶデータに対してＹ成分の４つの最上位桁（ＭＳＢ）及びＵとＶ成分の３つのＭＳＢを使用して生成でき、ここで、３Ｄヒストグラムでの各ビンは、Ｙの同じ４つのＭＳＢ、Ｕの同じ３つのＭＳＢ、及びＶの同じ３つのＭＳＢを有するフレームでの画素数に相当する。
【０００７】
ビデオシーケンスの一般的特性の１つは、一定の種類のヒストグラムに対して、所定ショット内のフレームに対するヒストグラムが、普通には、異なる場面に対応するショットでのフレームに対するヒストグラムよりも、より類似していることである。その場合、デジタルビデオをその構成ショットへ分解する１つの方法は、ビデオシーケンスにおけるフレームに対して生成されたヒストグラムを比較することによりショット間の転換を捜すことである。一般的に、類似のヒストグラムを持つフレームは、非類似のヒストグラムを持つフレームより同じ場面に対応する見込みが高い。
【０００８】
２つのヒストグラム間の差は、非類似性測度 (dissimilarity measures) と称する測定基準を使用して、数学的に表すことができる。１つの可能な非類似性測度Ｄabs（ｍ，ｎ）は、２つのフレームｍとｎに対して対応するヒストグラムのビン値間の差の絶対値の総和に相当し、以下の式（１）により表すことができる。
（１）    Ｄabs（ｍ，ｎ）≡Σi｜ｈi（ｍ）−ｈi（ｎ）｜
ここで、ｈi（ｍ）はフレームｍに対応するヒストグラムのｉ番目ビンの値であり、ｈi（ｎ）はフレームｎに対応するヒストグラムのｉ番目ビンの値である。別の可能な非類似性測度Ｄsq（ｍ，ｎ）は、対応するヒストグラムのビン値間の差の２乗の総和に相当し、以下の式（２）により表すことができる。
（２）    Ｄsq（ｍ，ｎ）≡Σi｜ｈi（ｍ）−ｈi（ｎ）｜2
これらの非類似性測度の各々は、２つのフレーム間の差、即ち非類似性、の数字表示を提供する。
【０００９】
カットは、２つの引続くショット間の突然の転換であり、第１のショットの最後のフレームは、第２のショットの最初のフレームに直接続く。そのようにな突然の転換は、ビデオシーケンスにおける各対の引続くフレーム間のヒストグラムの差を解析して、そのヒストグラムの差がビデオシーケンスでのカットに相当する規定の（及び普通には、経験的に生成された）閾値を超える対の引続くフレームを識別することにより高い信頼性をもって検出できる。
【００１０】
カットと異なり、ディゾルブ、フェード（fade）、ワイプ等の、ビデオシーケンスでの漸進的な転換は、引続くフレームに基づくヒストグラムの差を使用して充分な信頼性を持ち検出することができない。ディゾルブは、第２のショットの画素値が第１のショットの画素値を、数多くの転換フレームにわたり漸次置換える、２つのショット間の転換であり、そこでは、転換フレームの個々の画素は、２つの異なるショットに対応する画素を混合することにより生成される。混合される画素Ｐbは、以下の式（３）により定義できる。
（３）    Ｐb ≡（１−ｆ） * Ｐ1＋ｆ * Ｐ2    ０≦ｆ≦１
ここで、Ｐ1は第１のショットに対応する画素であり、 Ｐ2は第２のショットに対応する画素であり、ｆは混合割合である。ディゾルブが１つの転換フレームから次へ進行すると、混合割合ｆは増加する。その場合、第１のショットからの画素の影響は混合過程で徐々に小さくなる一方で、第２のショットからの画素の影響が増大し、転換の終りには、各画素は全て第２のショットからの画素に該当する。
【００１１】
フェードは、ショットの画素が数多くの転換フレームにわたり徐々に変化して、最後に画像は全て１つの色になる転換である。例えば、ブラックへのフェードでは、画素の明暗度即ち輝度が、画像が全てブラックになるまで漸次低減する。フェードは、第２のショットがソリッド色に相当するディゾルブの特定の種類とみなすことができる。
【００１２】
ワイプは、第２のショットの画素が第１のショットの画素を数多くの転換フレームにわたり漸次置換える転換であり、ここで、転換フレームの個々の画素は、第１のショットか又は第２のショットのいずれかから画素値を選択することにより生成される。ワイプが１つの転換フレームから次へ進むと、第１のショットから選択される画素値の数が減少する一方で、第２のショットからの画素値の数が増加して、転換の終りには、画素の全てが第２のショットからになる。
【００１３】
ディゾルブ、フェード、ワイプ等の、漸進的な転換では、式（１）と（２）で定義されるようにな非類似性測度により測定されるようにな、引続く転換フレーム間のヒストグラムの差は、所定のショット内の引続くフレーム間のヒストグラムの差と著しく違わないかもしれない。その場合、引続くフレームに基づくヒストグラムの差を使用することは、ビデオシーケンスにおいて漸進的な転換を検出するための信頼性のある測度を提供しないであろう。
【００１４】
漸進的な転換を検出するために、Zhang 他の「フルモーションビデオの自動仕切り (Automatic partitioning of full-motion video)」Multimedia Systems, Vol. 1, No. 1, pp. 10-28 (1993) が、２つの閾値を持つ２重比較法を提案する。この方法は、最初に隣接フレーム間の非類似性を評価し、２つの閾値の低い方を使用して、漸進的な転換の可能性のある開始フレームを指示する。次に、それは、Ｄ（ｓ＋ｋ−１，ｓ＋ｋ）がこの低い方の閾値を超える、各フレームｓ＋ｋに対するＤ（ｓ，ｓ＋ｋ）を評価する。漸進的転換は、Ｄ（ｓ，ｓ＋ｋ）が２つの閾値の高い方（即ち、突然の転換のために使用されるものに類似である）を超える場合を識別する。隣接フレーム間の変化を許容する幾つかの改良にも関らず、この方法は、モーションによって混乱させられる。カメラモーションはモーション解析により識別できるが、物体のモーションの影響は、非常に困難である。
【００１５】
Yeo 他の「圧縮ビデオに関する急速場面解析 (Rapid Scene Analysis on Compressed Video)」IEEE Transactions on Circuit and Systems for Video Technology, Vol. 5, No. 6, pp. 533-544 (1995) は、Ｄ（ｎ−ｗ，ｎ）を全てのｎに対して評価することにより転換を検出し、ここで、固定のタイミングウインドウｗが、転換におけるフレームの数より著しく大きいように選定される。この方法は、モーションに耐えるが、予測される転換の長さの情報を必要とする。
【００１６】
Shahraray の「ビデオシーケンスの場面変更検出と内容ベースのサンプリング (Scene change detection and content-based sampling of video sequences)」 Digital Video Compression: Algorithms and Technologies 1995, Proc. SPIE 2419, pp. 2-13 (1995) は、再帰時間形 (recursive temporal) フィルタをＤ（ｎ−ｗ，ｎ）へ適用する、ここでｗは１を超えてもよい。彼の解析は、順序統計 (order statistics) とモーションインジケータを含む。
【００１７】
Alattar の「ＤＶＩマルチメディア画像圧縮アルゴリズムを持つビデオシーケンスにおいてディゾルブ領域を検出し圧縮すること (Detecting and Compressing Dissolve Regions in Video Sequences with a DVI Multimedia Image Compression Algotithm)」 Proceedings of IEEE International Symposium on Circuits and Systems, May 3-6, 1993, Chicago, IL, pp. 13-16, は、ディゾルブを識別するために画素値の分散を使用する。この方法もモーションに耐えるが、ワイプのようにな他の種類の漸進的な転換へ適合するように見えない。
【００１８】
発明の要約
本発明は、デジタルビデオシーケンスにおいてショット間の転換を検出するためのスキームに向けられる。本発明は、ディゾルブやワイプ等の漸進的な転換と同様に、カットのようにな突然の転換の検出に使用することができる。その場合、本発明は、ビデオシーケンスをその構成ショットへ分解することにおける有用なツールであることができる。
【００１９】
実施の形態の１つでは、フレーム非類似性測度（ＦＤＭ）値が、タイミングウインドウサイズにより分離されたビデオシーケンスでの複数の対のフレームの各々に対して生成され、ここで、ＦＤＭ値は、正味の非類似性測度と累積の非類似性測度との比である。ＦＤＭ値は解析されて、ビデオシーケンスにおける転換を識別する。
【００２０】
代替の実施の形態では、ＦＤＭ値が、タイミングウインドウサイズにより分離されたビデオシーケンスでの複数の対のフレームの各々に対して生成される。第１の閾値条件がＦＤＭ値へ適用されて、該当する対のフレームが転換に該当するかを決定する。第１の閾値条件が満足される場合、次に、第２の閾値条件が１つ以上の他のＦＤＭ値へ適用されて、転換の開始と終了フレームを識別する。
【００２１】
詳細な説明
本発明によると、ビデオシーケンスは、規定されたタイミングウインドウサイズによりビデオシーケンスにおいて分離された対のフレームに対してフレーム非類似性測度（ＦＤＭ）を生成することにより解析される。ＦＤＭの値が第１の閾値条件を満足する場合、次に、該当する対のフレームは、ビデオシーケンスでの２つの引続くショット間の転換の一部分であると（少なくとも、暫定的に）識別される。その転換の開始と終了でのフレームは、次に、ＦＤＭ値へ第２の閾値条件を適用することにより識別される。
【００２２】
開始フレームは、転換が始まる直前のフレームとして定義され、終了フレームは、転換が完了した直後のフレームとして定義される。即ち、開始フレームは、第１のショットからだけで生成される最後のフレームであり、終了フレームは、第２のショットからだけで生成される最初のフレームである。開始と終了フレームとの間が転換フレームであり、それは、第１と第２のショットの両方から生成される。
【００２３】
本発明の実施の形態の１つでは、フレーム非類似性測度Ｒ（ｍ，ｎ）は、２つのフレームｍとｎに対して以下の式（４）により定義される。
（４）    Ｒ（ｍ，ｎ）≡Ｄnet（ｍ，ｎ）／Ｄcum（ｍ，ｎ）
ここで、Ｄnet（ｍ，ｎ）は、フレームｍとｎとの間の正味の非類似性であり、
Ｄcum（ｍ，ｎ）は、フレームｍとｎとの間の累積の非類似性である。
【００２４】
正味の非類似性Ｄnet（ｍ，ｎ）は、以下の式（５）により定義される。
（５）  Ｄnet（ｍ，ｎ）≡Σi｜ｈi（ｍ）−ｈi（ｎ）｜γ
ここで、ｈi（ｍ）はフレームｍに対応するヒストグラムのｉ番目ビンの値であり、ｈi（ｎ）はフレームｎに対応するヒストグラムのｉ番目ビンの値である。パラメータγは、通常２であると規定されるが、他の正のいずれの値も使用できる。γ＝２の場合、正味の非類似性Ｄnet（ｍ，ｎ）は、フレームｍとｎに対応するヒストグラムの該当するビン値間の差の２乗の総和であると言うことができる。
【００２５】
累積の非類似性Ｄcum（ｍ，ｎ）は、以下の式（６）により定義される。
（６）    Ｄcum（ｍ，ｎ）≡Σn-1k=mＤnet（ｋ，ｋ＋１）
その場合、累積の非類似性Ｄcum（ｍ，ｎ）は、フレームｍとフレームｎとを含みその間の対の引続くフレームの各々間の正味の非類似性の総和であると言うことができる。
【００２６】
図１は、本発明の実施の形態の１つによる、デジタルビデオシーケンスにおける転換を検出するための処理のフロー図を示す。図１の処理は、式（４）で定義されたフレーム非類似性測度Ｒ（ｍ，ｎ）を使用して、転換はＦＤＭデータでのピークとして現れる、ビデオシーケンスにおけるショット間の転換を識別する。第１の閾値条件が適用されて、ＦＤＭ値が規定された閾値を超えるか否かを決定することにより、可能性のあるピークを識別する。次に、第２の閾値条件が適用されて、ＦＤＭが規定されたより低い閾値より下回るか否かを決定することによりピークの境界（即ち、転換の開始と終了フレーム）を識別する。図１の処理は、ディゾルブやワイプ等の漸進的な転換と同様に、カットのようにな突然の転換の両方を識別するように設計されている。
【００２７】
図１の処理は、規定されたタイミングウインドウサイズｗにより時間で分離されるビデオシーケンスでの各対のフレームに対して式（４）のフレーム非類似性測度（ＦＤＭ）の生成で始まる（図１のステップ１０２）。換言すると、ビデオシーケンスが「左」から「右」へ進行し、時間が通常のＸＹグラフのＸ軸に沿いプロットされる場合、フレームｎがタイミングウインドウの右側にあるフレームである場合、フレームｍ＝（ｎ〜ｗ）は、タイミングウインドウの左側にあるフレームである。
【００２８】
ＦＤＭデータは、例えば、３タップのメディアンフィルタ (median filter) を使用してオプションでフィルタリングされる（ステップ１０４）。フィルタが適用される場合、処理の残りは、フィルタリングされたＦＤＭデータへ適用される。そうでない場合、元のＦＤＭデータが使用される。
【００２９】
平均のローカルノイズがフィルタリングされたＦＤＭデータに対して推定され、それにより、ＦＤＭデータでのピークの境界が識別できる（ステップ１０６）。ノイズは、好ましくは、ＦＤＭデータを小さな値の方向へバイアスして、次にバイアスされたデータをフィルタリングすることにより特徴付けられる。実施の形態の１つでは、バイアスすることは、バイアス関数 bias(R) の適用を含み、ここで、bias(R) = tanh(2R)/2 であり、フィルタリングすることは、exp[-(d/b)2] の形のガウスフィルタリング関数 (Gaussian filtering function) の適用を含み、ここで、ｄはフィルタリングされたフレームからのフレームの数であり、ｂは規定の定数（例えば、４０）である。
【００３０】
この初期処理のステップ１０２〜１０６の後に、ＦＤＭ値が解析され、ビデオシーケンスでのショット間の転換を識別する。このデータ解析は、ビデオシーケンスの始まりでのフレームで始まり、ビデオシーケンスの終りでのフレームまでデータを走査する処理ループである。図２は、図１の処理のこの解析フェーズに対応する疑似コードの一覧を提示する。
【００３１】
解析フェーズは、第１と第２の閾値条件を適用することに使用される一定のパラメータの初期化で始まり（図２での行１６参照）、ここでＴ1とＴ2は、第１と第２の閾値の値であり、Ｍ1とＭ2は、第１と第２の閾値の乗数である。図２に示す特定のパラメータ値は、異なる既知のビデオシーケンスを試験することにより経験的に引出された典型的な値である。
【００３２】
式（４）のＦＤＭは、サイズｗを有するスライドするタイミングウインドウの対向端での対のフレームに基づいているので、タイミングウインドウの右側でのフレームを指示する現在のフレーム指示子（ポインタ）ｎは、ｗへ初期化され（図１でのステップ１０８、及び図２での行１７）、ここで、フレームシーケンスでの最初のフレームはフレーム０であると仮定する。
【００３３】
処理は、次いで、転換を捜してビデオシーケンスを走査する。第１の閾値条件が適用されて、現在のフレームｎがビデオシーケンスでの２つのショット間の転換に該当するかを決定する（図１でのステップ１１０）。図２での行２０によると、現在のフレームｎに対するＦＤＭ値が２つの値、即ち（ａ）第１の閾値の値Ｔ1と（ｂ）第１の閾値乗数Ｍ1と現在のフレームｎでのノイズレベルとの積、の最大より大きい場合、この第１の閾値条件は満足される。固定タイミングウインドウサイズｗが使用されたので、式（４）のＦＤＭ値Ｒ（ｍ，ｎ）は、Ｒ（ｎ−ｗ，ｎ）であり、ｎがタイミングウインドウの右側でのフレームを規定する場合、それはＲ（ｎ）とも表せることに注意されたい。
【００３４】
第１の閾値条件が満足される場合、次に、ＦＤＭデータは、転換に対する開始と終了フレームを識別するように解析される（図１でのステップ１１２）。これは、（１）第２の閾値条件を満足する最初のフレームｓを現在のフレームｎの左で捜すようにビデオシーケンスにおいて左へ走査すること（図２での行２１）、及び（２）第２の閾値条件を満足する最初のフレームｅ'を現在のフレームｎの右で捜すようにビデオシーケンスにおいて右へ走査すること（図２での行２２）により完遂される。行２１と２２によると、フレームｍに対するＦＤＭ値が２つの値、即ち（ａ）第２の閾値の値Ｔ2と（ｂ）第２の閾値乗数Ｍ2とフレームｍでのノイズレベルとの積、の最大より小さい場合、この第２の閾値条件は満足される。
【００３５】
転換が検出される場合、次フレーム指示子は、ビデオシーケンスでのフレームｅ'に直接続くフレームに等しく設定される（図１でのステップ１１４、及び図２での行２３）。フレームｅ'は、第２のショットへの転換の完了直後のタイミングウインドウの右側でのフレームに該当する。先に記載の定義によると、終了フレームは、第２のショットからだけで生成される最初のフレームである。その場合、転換に対する終了フレームは、実際に、タイミングウインドウの左側でのフレームである。従って、終了フレームｅは、フレームｅ'に対するフレーム数からタイミングウインドウサイズｗを減算することにより識別される（図２の行２４参照）。
【００３６】
タイミングウインドウのサイズに対して調整した後に、転換の終了として識別されたフレーム（ｅ）が、転換の開始として識別されたフレーム（ｓ）の右に無いと判明する場合、検出された転換は却下される（図１でのステップ１１６、及び図２での行２５）。このステップは、タイミングウインドウサイズｗより短い時間の期間で場面に現れる、カメラのフラッシュ、又は非常に近接した物体のようにな他の変則、により引起されるかもしれないＦＤＭデータでの短期間ノイズを弁別する。そのようにな変則のフレームが検出される場合、式（６）のＤcumへの寄与を排除することによりそれを無視することが有利であろう。
【００３７】
そうでない場合、フレームｓとｅは、ビデオシーケンスにおけるショット間の転換に対する、それぞれ開始と終了フレームとして決定される（図１でのステップ１１８、及び図２での行２６）。次に、図１の処理は、ステップ１０８へ戻り、第１の閾値条件の次の適用のために現在のフレーム指示子ｎを更新する。図２の行１８〜１９、２３、及び２８は、ビデオシーケンスでの進行を実行するブックキーピング（簿記）のステップである。
【００３８】
図３は、図１及び図２の処理を実証するために、ビデオシーケンスの数多くのフレームに対するＦＤＭ値の例示セットを示す。この例示の目的のために、ＦＤＭデータにおけるノイズは充分に低く、それにより、選定された第１と第２の閾値の値、それぞれＴ1＝０．５０とＴ2＝０．２５は、第１と第２の閾値条件が満足されるか否かを常に決定すると仮定する。ＦＤＭ値は、タイミングウインドウサイズ６を使用して生成されるとも仮定する。これは、例えば、フレームｎ＝１１に対するフレーム非類似性測度Ｒ（ｎ）は、フレーム１１とフレーム（ｎ−６）即ち５との間の差を特徴付けることを意味する。
【００３９】
図１及び図２の処理を図３のデータへ適用すると、ＦＤＭデータは、フレームｎ＝６（タイミングウインドウサイズが６であるので）で始まる。処理は、第１の閾値条件をＦＤＭデータへ適用して左から右へ、フレームｎ＝１４に対するＲ（ｎ）が第１の閾値の値Ｔ1＝０．５０を超えることを決定するまで、継続する。処理でのこの点で、ＦＤＭデータは、フレームｎ＝１４から両方向に走査されて、第２の閾値条件を満足するフレームｎ＝１４の左への最初のフレーム（即ち、フレームｓ＝９）を見出し、第２の閾値条件を満足するフレームｎ＝１４の右への最初のフレーム（即ち、フレームｅ'＝３０）を見出す。フレームｅ'は、転換が完了した後にタイミングウインドウの右側に該当するので、フレームｅ＝ｅ'−ｗ＝３０−６＝２４が、転換の終了フレームとして識別される。
【００４０】
本発明は、主として漸進的な転換を検出するように設計されたが、転換フレームが無い、カットのようにな突然の転換を検出することでも有効である。これを、ビデオシーケンスにおいてフレーム２０と２１との間で起るカットに対応するＦＤＭ値の例示セットを示す図４において実証する、ここで、フレーム２０は、フレーム０〜２０に対応する第１のショットの最後のフレームであり、フレーム２１は、フレーム２１〜３６に対応する第２のショットの最初のフレームである。説明の目的のために、第１のショットでの各フレームは、単一の静止画像に対応すると仮定され、第２のショットでの各フレームは、別の単一の静止画像に対応すると仮定される。タイミングウインドウサイズｗ＝６であるとする。
【００４１】
図４に示すように、第１のショット内の各フレームは同一であるので、ｎ＝６からｎ＝２０に対するフレーム非類似性測度Ｒ（ｎ）は、全てゼロである。正味の非類似性Ｄnetがゼロの場合、累積の非類似性Ｄcumもゼロであっても、フレーム非類似性測度Ｒ（ｎ）は、ゼロであると定義される。Ｒ（ｎ＝２０）は、タイミングウインドウサイズ６に対するフレーム２０とフレーム１４との間の差を表すことに注意されたい。フレームｎ＝２１は、第２のショットの最初のフレームであるので、Ｒ（ｎ＝２１）は、第２のショットのフレーム２１と第１のショットのフレーム１５との間の差に相当する。その場合、フレーム非類似性測度Ｒ（ｎ＝２１）は、ゼロではないであろう。同様に、Ｒ（ｎ＝２２）は、第２のショットのフレーム２２と第１のショットのフレーム１６との間の差に相当し、等々フレームｎ＝２６まで同様であり、ここで、Ｒ（ｎ＝２６）は、第２のショットのフレーム２６と第１のショットのフレーム２０との間の差に相当する。しかし、フレームｎ＝２７で、フレーム２７と２１は、共に第２のショットからであるので、Ｒ（ｎ＝２７）はゼロであろう。第２のショット内のフレームを比較しているので、同じことが、図４の残りのＦＤＭ値に対して真である。
【００４２】
図１及び図２の処理を図４の例へ適用する場合、フレームｎ＝２１は、第１の閾値条件を満足する最初のフレームとして識別されるであろう。次に、フレームｓ＝２０とｅ'＝２７が、第２の閾値条件を満足する、それぞれフレームｎ＝２１の左と右への最初のフレームとして識別されるであろう。６のタイミングウインドウサイズに対してｅ'＝２７を調整すると、フレームｓ＝２０とフレームｅ＝２１は、第１と第２のショット間の転換に対して、それぞれ開始と終了フレームとして正しく識別される。
【００４３】
図５（Ａ）〜（Ｃ）は、３つの異なる試験シーケンスに対するＦＤＭ値を生成する実験結果を示す。３つの５０フレーム試験シーケンスを、ＭＰＥＧ４シーケンス Stefan（クラスＣ）と Foreman（クラスＢ）から生成した。これらの試験シーケンスは、全て同じ Stefan の１５フレームで始まり（フレーム０〜１４）、同じ Foreman の１５フレームで終わる（フレーム３５〜４９）。それらは、２０転換フレーム（フレーム１５〜３４）をどのように生成したかで異なる。３つの試験シーケンスを、３つの異なる種類の漸進的転換、即ちリニアワイプ(lin W)、２次元ワイプ(quad W)、及びリニアディゾルブ(lin D)、に基づき生成した。
【００４４】
リニアワイプは、第２のショットから選択された画素の数が転換フレームにわたり直線的に増大するワイプである。普通のリニアワイプは、第１のショットから選択された画素から、第２のショットから選択された画素を分離するワイプの端が、左から右へ転換フレームを横切り一定の速度で移動する垂直の線であるワイプである。図５（Ａ）〜（Ｃ）の試験シーケンス lin W を、左から右への垂直のワイプで Stefan を Foreman で置換えることにより生成した。
【００４５】
２次元のワイプは、第２のショットから選択された画素の数が転換フレームにわたり２次元で増大するワイプである。普通の２次元ワイプは、ワイプ端が方形を画成して、ここで、方形内の画素が第２のショットから選択され、方形の外側の画素が第１のショットから選択されて、方形の高さと巾両方が一定の速度で転換フレームにわたり増加するワイプである。図５（Ａ）〜（Ｃ）の試験シーケンス quad W を、Stefan の真中で増大する方形領域において Foreman に置換えることにより生成した。
【００４６】
リニアディゾルブは、式（３）の混合割合が０から１へ均一な速度で転換フレームにわたり変化するディゾルブである。
図５（Ａ）〜（Ｃ）の試験シーケンス lin D を、ｆを均一な速度でフレーム１４でｆ＝０からフレーム３５でｆ＝１まで変化させることにより生成した。
【００４７】
図５（Ａ）は、式（４）のフレーム非類似性測度Ｒ（０，ｎ）を示し、ここで、式（５）でのγ＝２であり、それにより、ビデオシーケンスでの各フレームは、ビデオシーケンスでの最初のフレーム（即ち、フレーム０）と比較する。図５（Ｂ）はγ＝４に対するＲ（０，ｎ）を示し、図５（Ｃ）はγ＝２と固定のタイミングウインドウサイズ５に対するＲ（ｎ−５，ｎ）を示す。各々の場合、ＦＤＭの計算は、Ｙデータの４ＭＳＢとＵ及びＶデータ両方の３ＭＳＢから生成された３Ｄヒストグラムに基づいた。γ＝２に対する図５（Ａ）での結果とγ＝４に対する図５（Ｂ）での結果との間の最も劇的な差は、ワイプ（lin W と quad W）に対する応答が、２桁増大して、それが、シーケンスの始まりで、ディゾルブ (lin D) に対する応答も一緒に、応答を完全に圧倒する (swamp) ことである。
【００４８】
図６（Ａ）〜（Ｃ）は、図１及び図２の処理を、１５フレーム／秒で符号化されたＭＰＥＧ−１である３５２Ｗｘ２４０Ｈ画像の３０，００１フレームのビデオシーケンスへ適用した結果を示す。図６（Ａ）〜（Ｃ）の各々では、グラフの上部は、γ＝２とタイミングウインドウサイズの６に対する式（４）のフレーム非類似性測度Ｒ（ｎ−６，ｎ）をプロットし、グラフの下部は、両データセットが同じグラフ上に明確に観察できるように適用された−５０の負のスケーリング係数を持つ式（２）の引続くフレームの非類似性測度Ｄsq（ｎ−１，ｎ）をプロットする。これらの結果の全ては、図５（Ａ）〜（Ｃ）に対して使用されたのと同じ種類の３Ｄヒストグラムを使用して生成した。
【００４９】
図６（Ａ）は３０，００１フレームのビデオシーケンス全体に対する結果をプロットする。図６（Ｂ）はフレーム２５００〜５０００に対する結果の引伸ばしを示し、図６（Ｃ）はフレーム２７０００〜２９０００に対する結果の引伸ばしを示す。図６（Ｂ）と６（Ｃ）の下半分における文字は、次の種類の手動で観測した転換の位置と種類を示す。Ｗ＝ワイプ、Ｆ＝フェード、Ｄ＝ディゾルブ、及びＣ＝カット。非類似性測度Ｄsq（ｎ−１，ｎ）は、大多数のワイプに対して殆ど応答を有せず、式（２）の引続くフレームの非類似性測度は充分な信頼性を持ちワイプを識別する見込がないであろうことを示すことに注意されたい。
【００５０】
図６（Ｂ）と６（Ｃ）の上部における円は、図１及び図２の処理により識別されたイベントに対する転換比を示す。転換比は、図１及び図２の処理中に識別された転換の開始と終了フレームに対するフレーム非類似性測度Ｒ（ｓ，ｅ）として定義される。ＦＤＭデータにおけるノイズレベルは、図６（Ｂ）と６（Ｃ）で平滑な曲線により示す。
【００５１】
一般的に、図１及び図２の処理は、ワイプ、フェード、ディゾルブ、又はカットであろうと、大多数の転換を識別することに成功し、少しだけの虚偽の否定（即ち、実際の転換を見落とす）と虚偽の実在（即ち、転換でないのを転換と識別する）を持つ。幾つかの明白なピークを拾い上げていない。図１及び図２のアルゴリズムは、非常に狭いピークをノイズとみなし、ここで、ピークの巾は、ピークの境界を決定する第２の閾値条件におけるＴ2やＭ2等の、一定のパラメータに対して選定される値に依存する。
【００５２】
大多数のワイプに対して、転換比Ｒ（ｓ，ｅ）の大きさは、固定のタイミングウインドウサイズｗの６を使用して生成された対応するＦＤＭデータと同等か、又はそれより大きい。これは、ｗより長いワイプに対して予測される。
【００５３】
無次元の比であるので、式（４）のＦＤＭは、一種の規格化関数として働く。ＦＤＭデータにおけるピークの範囲は、スケールされていないＤsq（ｎ−１，ｎ）データのそれよりはるかに小さい。これは、閾値の選定を容易にすることになる。
【００５４】
処理効率の点では、全てのｘ＞０に対して、式（６）のＤcum（０，ｘ）を生成することが有用かもしれない。いずれの対のフレームｍとｎに対して、累積の非類似性Ｄcum（ｍ，ｎ）は、Ｄcum（ｍ，ｎ）＝｜Ｄcum（０，ｎ）−Ｄcum（０，ｍ）｜の関係に基づき容易に生成できる。
【００５５】
代替の実施の形態
本発明を、図１及び図２の処理に沿って説明する。そこでは、転換は、ＦＤＭ値を規定された閾値の値と比較することにより検出される。本発明は、虚偽の実在を弁別する追加の条件を使用して補強するすることができる。例えば、転換比Ｒ（ｓ，ｅ）は、虚偽の実在を検出するように、規定された閾値と比較できる。別の可能性は、虚偽の実在を検出するように、ＦＤＭ曲線の下で規定された最小の領域を有する転換を要求することであろう。更に別の可能性は、転換の開始と終了フレーム間の正味の非類似性であるＤnet（ｓ，ｅ）へ閾値を適用することであろう。
【００５６】
図１及び図２のアルゴリズムは、ＦＤＭデータにおいてピークを検出して、対応する開始と終了フレームを識別する特定の解析スキームを適用する。図１及び図２のアルゴリズムは、２回通過の解析であり、それは、ビデオシーケンス全体がメモリに蓄積されている状況に特に適している。当業者は、ピークがＦＤＭデータへ異なる解析スキームを適用することにより検出及び／又は識別できることを理解するであろう。
【００５７】
例えば、代替の実施の形態では、本発明は、ビデオシーケンス全体をメモリに必ずしも蓄積せず、各フレームが遭遇されるに従いデータが解析される状況に適する１回通過の解析を使用して実行できる。図７は、可能な１回通過の解析のための疑似コードを示す。この１回通過の解析は、図１及び図２の２回通過の解析と類似であるが同一ではない。例えば、１回通過の解析では、可能性の転換は、高い方の閾値でなく２つの閾値の低い方により提起される。加えて、ノイズは少し異なって計算され、メディアンフィルタは無く、及び、閾値定数は少し異なる。
【００５８】
詳細には、図７の１回通過の解析は、３つの状態を有する状態マシンに対応する。noTrans（即ち、現在の状態は転換を指示しない）、possibleTrans（即ち、現在の状態は可能性の転換を指示する）、及び probableTrans（即ち、現在の状態は有望な転換を指示する）。ビデオシーケンスにおいてフレームが遭遇されるに従い、関数 Analyze(n) が、各現在のフレームｎへ適用される、ここで、ｎの初期値は、規定のタイミングウインドウサイズｗより大きいか等しいと仮定される。関数 Analyze(n) は、図７の行１〜５で定義され初期化されるグローバル変数に依頼する。現在フレームに対するフレーム非類似性測度Ｒを計算し（行１０）、ノイズレベルを特徴付けるように再帰形フィルタを適用し（行１２〜１３）、及び、低い方と高い方の閾値（ｔＬとｔＨ）を生成（行１５〜１６）した後に、関数 Analyze(n) は、１つ前のフレームの後のマシンの状態に依存して適切な処理を実行する。
【００５９】
noTrans 状態に対して（行１９）、行２０〜２８が実行される。詳細には、現在のフレームに対するＦＤＭのＲが低い方の閾値ｔＬより大きい場合（行２０）、可能性の転換の最初のフレームが１つ前のフレーム（ｎ−１）に設定され（行２１）、状態は possibleTrans へ変更される（行２２）。ＦＤＭが更に高い方の閾値ｔＨより大きい場合（行２４）、状態は直ちに probableTrans へ変更され（行２５）、高い方の閾値に対する最初と最後の両フレームは現在のフレームｎへ初期化される（行２６）。そうでない場合、状態は noTrans に留まる。
【００６０】
possibleTrans 状態に対して（行２９）、行３０〜３５が実行される。詳細には、現在のフレームに対するＦＤＭのＲが低い方の閾値ｔＬより低いか等しい場合（行３０）、状態は noTrans へ変更される（行３０）。これは、ＦＤＭ値が低い方の閾値を超えたが、しかし、高い方の閾値に決して達することなく低い方の閾値以内へ戻った状況に相当する。そうでなく、ＦＤＭが高い方の閾値ｔＨより大きい場合（行３１）、状態は probableTrans へ変更され（行３２）、高い方の閾値に対する最初と最後の両フレームは現在のフレームｎへ初期化される（行３３）。そうでない場合、状態は possibleTrans に留まる。
【００６１】
probableTrans 状態に対して（行３６）、行３７〜４６が実行される。詳細には、現在のフレームに対するＦＤＭのＲが低い方の閾値ｔＬより大きい場合（行３７）、Ｒが更に高い方の閾値ｔＨより大きい場合（行３８）、転換での最後のフレームは現在のフレームｎへ更新され（行３８）、そうでない場合現在のフレームｎに対する処理は終了される（行３９）。そうでなく、Ｒが低い方の閾値ｔＬより小さいか等しい場合、転換は終了する。その場合、状態は noTrans へ変更され（行４１）、上方と下方のピークの終りは、タイミングウインドウサイズに対して調整される（行４２〜４３）。ピークが狭過ぎる場合（行４４）、転換は却下される。そうでない場合、転換は Analyze(n) 関数により報告される（行４５）。行４４での狭いピークに対する試験は、２回通過の解析の対応する試験より複雑であり、可能性の転換の開始と終了をより対称的に処理するように試みる。
【００６２】
本発明は、フレーム全体に対して生成されるＦＤＭ値に対して説明された。場面間の漸進的な転換から場面内での対象のモーションを区別するために、フレームは、副フレームへ分割でき、各副フレームが別々に解析される。対象のモーションは、副フレームの幾つかだけに出現すると思われる一方で、転換は、全てではないにしても、大多数の副フレームで明白である筈である。
【００６３】
本発明は、ビデオシーケンスにおけるショット間の漸進的な転換を検出するように設計されたが、ショット間の突然の転換（即ち、カット）又はカメラのモーション（例えば、パン）でさえ検出することにも使用できる。パンは、特にパンが結果として著しい場面変更となる場合、ショット内の漸進的な転換の１種とみなされ得る。例えば、ビデオのインデックス付けの中に、ショット間の転換と同様にショット内のパンを検出できるユーティリティがあってもよい。代替として、パンは、パンのフレーム間の全体のグローバルモーションを検出するようにモーション解析を使用することによりショット間の転換から弁別できる。
【００６４】
実験結果の大多数は、式（５）でのγ＝２を使用することに基づいた。γを増加することは、無規則な活動の影響を低減し、図５（Ａ）と５（Ｂ）に示すように、他の漸進的な転換に対してワイプの影響を増大させる。しかし、アルゴリズムの安定性も低下させるかもしれない。γ＝１も有用であることに注意されたい。その場合、ＦＤＭ値は１を決して超えないであろうとはいえ、それは、他の場合より転換で依然はるかに大きい傾向である。タイミングウインドウサイズを変更することは、短時間尺度で系統的に現れる無規則なモーションの弁別を助けることになる。
【００６５】
タイミングウインドウサイズの選定は、かなり任意であるが、選定された特定の値は、特定のビデオシーケンスに対するＦＤＭデータにおけるノイズレベルに影響することができる。例えば、一定の周期性を持つ符号化スキームでは、符号化周期の整数倍に基づきタイミングウインドウサイズを選定することは、より少ないノイズを生じることができる。
【００６６】
式（４）のフレーム非類似性測度は、フレームのヒストグラムに基づく非類似性測度の比である。フレーム非類似性測度の代替のバージョンも使用できる。例えば、非類似性測度は、フレームのヒストグラムでなく、フレーム間の画素から画素への差（例えば、差の２乗の総和、又は絶対値差の総和）に基づくことができる。
【００６７】
本発明は、これらの方法を実施するための方法と装置の形態で具現化できる。本発明は、フロッピーディスケット、ＣＤ−ＲＯＭ，ハードドライブ、又はマシンが読み得るいずれか他の記憶媒体、等の有形の媒体内に実現されるプログラムコードの形態でも具現化でき、プログラムコードが、コンピュータのようになマシンへロードされ、マシンにより実行される場合、マシンは、本発明を実施するための装置となる。本発明は、例えば、記憶媒体に蓄積されるか否かに関らず、マシンへロードされ、マシンにより実行される、又は、電線又は電気ケーブル上で、光ファイバを通し、又は電磁波を介する等の、伝送媒体上で伝送されるプログラムコードの形態でも具現化でき、プログラムコードが、コンピュータのようになマシンへロードされ、マシンにより実行される場合、マシンは、本発明を実施するための装置となる。汎用プロセッサ上で実行される場合、プログラムコード部分はプロセッサと組合せて、特定のロジック回路に類似で動作する独特の装置を提供する。
【００６８】
本発明の性質を説明するために記述され図解された詳細、資料、及び部品の編成における種々の変更は、以下の特許請求の範囲に表示された発明の原理と範囲から逸脱することなく、当業者にはなされ得ることが更に理解されるであろう。
【図面の簡単な説明】
本発明の他の局面、特徴、及び利点は、以下の詳細な説明、付帯する特許請求の範囲、及び添付の図面からより充分に明らかになるであろう。
【図１】  本発明の実施の形態の１つによる、デジタルビデオシーケンスにおける転換を検出するための処理のフロー図を示す。
【図２】  図１の処理のこの解析フェーズに対応する疑似コードの一覧を提示する。
【図３】  図１及び図２の処理を実証するために、ビデオシーケンスの数多くのフレームに対するフレーム非類似性測度（ＦＤＭ）値の例示セットを示す。
【図４】  カットに対応するＦＤＭ値の例示セットを示す。
【図５】  Ａ〜Ｃは３つの異なる試験シーケンスに対するＦＤＭ値を生成する実験結果を示す。
【図６】  Ａ〜Ｃは図１及び図２の処理を、特定のビデオシーケンスへ適用した結果を示す。
【図７】  本発明の実施の形態の１つによる、１回通過の解析に対する疑似コードを示す。
【図１】
0004335440.tif 000002
【図２】
0004335440.tif 000003
【図３】
0004335440.tif 000004
【図４】
0004335440.tif 000005
【図５】
0004335440.tif 000006
【図６】
0004335440.tif 000007
【図７】
0004335440.tif 000008