(57)【要約】【課題】  所定のコンテンツの存在についてメディア情報ストリームを評価するためのアルゴリズムを実行し、アルゴリズムが所定のコンテンツを最大の精度で検出することができる値が確定されるまで、アルゴリズムのパラメータを自動的に変化させる、方法、装置、およびプログラムを提供すること。【解決手段】  メディア情報ストリーム内の所定のコンテンツを検出するためのアルゴリズムのパフォーマンスを最適化するための方法と、この方法に従って動作するプログラムおよび装置。アルゴリズムは、パラメータセットの関数である。この方法は、アルゴリズムの各実行ごとにアルゴリズムにおいてそれぞれのパラメータセットを使用しながらアルゴリズムを少なくとも一回実行し、メディア情報ストリーム内の所定のコンテンツを検出するステップと、アルゴリズムがメディア情報ストリーム内の所定のコンテンツを検出する精度の程度を最大にするために、アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるステップと、を有する。
2005513967.tif 000002
【特許請求の範囲】
【請求項１】
メディア情報ストリーム内の所定のコンテンツを検出するためのアルゴリズムのパフォーマンスを最適化するための方法であって、前記アルゴリズムが、パラメータセットの関数であり、前記方法が、
−  前記アルゴリズムの各実行ごとに前記アルゴリズムにおいてそれぞれのパラメータセットを使用しながら、前記アルゴリズムを少なくとも一回実行し、前記メディア情報ストリーム内の前記所定のコンテンツを検出するステップと、
−  前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する精度の程度を最大にするために、前記アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるステップと、
を有する、方法。
【請求項２】
前記メディア情報ストリームが、少なくとも1つのビデオおよびオーディオ情報を含んでおり、かつ、前記所定のコンテンツが、望ましいコンテンツまたは望ましくないコンテンツを含んでいる、請求項1に記載の方法。
【請求項３】
前記アルゴリズムが、前記メディア情報ストリームから導かれる少なくとも1つの所定の特徴の検出に基づいて、前記所定のコンテンツを検出する、請求項1に記載の方法。
【請求項４】
前記自動的に進化させるステップが、遺伝的アルゴリズムを実行して前記少なくとも一組のそれぞれのパラメータセットを進化させるステップを含む、請求項1に記載の方法。
【請求項５】
前記メディア情報ストリームが、複数のフレームに分割されているビデオ情報ストリームを含んでおり、前記所定のコンテンツが、少なくとも1つのコマーシャルを含んでおり、かつ、前記アルゴリズムが、
−  前記ビデオ情報ストリーム内の複数の黒または単色フレームを検出するステップと、
−  コマーシャルの最初の部分の存在を、少なくとも1つの前記複数の黒または単色フレームの検出に基づいて識別するステップと、
−  前記コマーシャルの最後の部分の存在を、少なくとも1つの別の前記複数の黒または単色フレームの検出に基づいて識別するステップと、
を含んでいる、請求項1に記載の方法。
【請求項６】
前記自動的に進化させるステップが、
−  前記アルゴリズムの各実行について、前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する前記精度を確定するステップと、
−  前記精度を確定する前記ステップの結果に基づいて、前記それぞれのパラメータセットの少なくとも1つを選択するステップと、
−  前記選択するステップにおいて選択された前記少なくとも一組のパラメータセットに基づいて、少なくとも1つの子孫パラメータセットを生成するステップと、
を有する、請求項1に記載の方法。
【請求項７】
前記自動的に進化させるステップが、
−  前記生成するステップにおいて生成されたそれぞれの子孫パラメータセットを、前記アルゴリズムのさらなる各実行時に前記アルゴリズムにおいて使用しながら、前記アルゴリズムを少なくとも一回実行し、前記メディア情報ストリーム内の前記所定のコンテンツを検出するステップと、
−  前記アルゴリズムのさらなる各実行について、前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する前記精度を確定するステップと、
−  前記選択するステップにおいて選択された少なくとも一組のそれぞれのパラメータセットのうちの1つ以上と、前記生成するステップにおいて生成された少なくとも1つの子孫パラメータセットとを、前記確定するステップの結果に基づいてさらに選択するステップと、
をさらに有する、請求項6に記載の方法。
【請求項８】
前記自動的に進化させるステップが、
−  前記さらに選択するステップの後に残っているすべてのパラメータセットの収束性があるかを判断するステップと、
−  収束性がある場合、前記さらに選択するステップにおいて選択されたパラメータセットのうちの少なくとも1つのレコードを格納するステップと、
をさらに有する、請求項7に記載の方法。
【請求項９】
前記生成するステップが、
−  前記選択するステップにおいて選択された前記パラメータセットのうちランダムに選択されたパラメータセットを対にするステップと、
−  前記対にするステップにおいて対にされた前記パラメータセットが排他的であるかを判断するステップと、
−  排他的ではないと判断された対にされている各パラメータセットについて、これらのパラメータセットの前記パラメータの1つ以上の値を別の値に交換するステップと、
を有する、請求項6に記載の方法。
【請求項１０】
前記対にするステップにおいて対にされた前記パラメータセットが排他的であるかを判断する前記ステップが、
−  対にされている各パラメータセットの対応するパラメータ値のうち、互いに異なる対応するパラメータ値（存在時）の数を確定するステップと、
−  互いに異なると判断された対応するパラメータ値の前記数が、所定の排他的しきい値より小さいかを判断するステップと、
を有する、請求項9に記載の方法。
【請求項１１】
前記自動的に進化させるステップが、
−  前記さらに選択するステップの後に残っているすべてのパラメータセットの収束性があるかを判断するステップと、
−  収束性がない場合、
−  前記さらに選択するステップの後に残っている前記すべてのパラメータセットのうちの最適なパラメータセットの少なくとも1つの値を突然変異させて、前記最適なパラメータセットの複数の突然変異されたバージョンを生成するステップと、
−  前記方法の少なくともいくつかのステップを、前記アルゴリズムを複数回実行することから始めて再び実行し、前記メディア情報ストリーム内の前記所定のコンテンツの存在を検出するステップであって、前記アルゴリズムのそれぞれ実行において、前記最適なパラメータセットと、前記最適なパラメータセットの前記突然変異されたバージョンとを使用する、前記ステップと、
をさらに有する、請求項7に記載の方法。
【請求項１２】
前記突然変異させるステップが、
−  前記最適なパラメータセットの複数のコピーを生成するステップと、
−  前記最適なパラメータセットの前記複数のコピーのそれぞれの少なくとも1つのパラメータ値を変化させるステップと、
を有する、請求項11に記載の方法。
【請求項１３】
前記生成するステップが、
−  前記選択するステップにおいて選択された前記パラメータセットのうちランダムに選択されたパラメータセットを対にするステップと、
−  前記対にするステップにおいて対にされた前記パラメータセットが排他的であるかを、
−  対にされている各パラメータセットの対応するパラメータ値のうち、互いに異なる対応するパラメータ値（存在時）の数を確定するステップと、
−  互いに異なると判断された対応するパラメータ値の前記数が、所定の排他的しきい値より小さいかを判断するステップと、
によって判断するステップと、
−  排他的ではないと判断された対にされている各パラメータセットについて、これらのパラメータセットの前記パラメータの1つ以上の値を別の値に交換するステップと、
を有する、請求項8に記載の方法であって、
−  収束性があるかを判断する前記ステップが、
−  前記所定の排他的しきい値が所定の値に等しいかを判断するステップと、
−  前記さらに選択するステップの後に残っている前記パラメータセットを使用する前記アルゴリズム(112)を実行する結果として、前記所定のコンテンツが実質的に同じ程度の精度で検出されるかを判断するステップ、
のうちの少なくとも1つを有する、
方法。
【請求項１４】
−  前記さらに選択するステップが実行された後に子孫パラメータセットが残っているかを判断するステップと、
−  子孫パラメータセットが残っていない場合、前記所定の排他的しきい値を所定の減少値だけ減らすステップと、
をさらに有する、請求項13に記載の方法。
【請求項１５】
請求項8に記載の方法であって、前記さらに選択するステップの後に残っている前記パラメータセットのすべての収束性がある場合、
−  前記方法が所定の回数実行されたかを判断するステップと、
−  所定の数の子孫パラメータセットが生成されたかを判断するステップと、
の少なくとも1つを実行する、方法であって、
−  これらの判断ステップのいずれかが肯定の判断結果となる場合に、前記格納するステップを実行する、
方法。
【請求項１６】
前記自動的に進化させるステップが、前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを最大の程度の精度で検出することができるように最適化されている進化したパラメータセットを生成するために、前記アルゴリズムにおいて使用されている前記少なくとも一組のそれぞれのパラメータセットを進化させるステップ、を含んでいる、請求項1に記載の方法。
【請求項１７】
前記アルゴリズムの少なくとも1つと、前記進化したパラメータセットとを、所定の受信先に転送するステップをさらに有する、請求項16に記載の方法。
【請求項１８】
メディア情報ストリームを評価するための方法であって、前記方法が、
−  それぞれ前記メディア情報ストリーム内の所定のコンテンツの存在を検出するための1つ以上のアルゴリズムを実行するステップであって、当該各アルゴリズムが、対応する染色体の関数である、前記ステップと、
−  少なくとも1つの前記アルゴリズムの前記染色体の値を自動的に確定するステップであって、当該値が、前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツの存在を、別の値が使用されているときに達成される精度よりも高い程度の前記精度で検出することができる値である、前記ステップと、
を有する、方法。
【請求項１９】
メディア情報ストリーム内の所定のコンテンツを検出するためのアルゴリズムのパフォーマンスを最適化するための装置であって、前記アルゴリズムが、パラメータセットの関数であり、前記装置が、
−  前記アルゴリズムの各実行ごとに前記アルゴリズムにおいてそれぞれのパラメータセットを使用しながら、前記アルゴリズムを少なくとも一回実行し、前記メディア情報ストリーム内の前記所定のコンテンツを検出するための手段と、
−  前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する精度の程度を最大にするために、前記アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるための手段と、
を有する、装置。
【請求項２０】
コンピュータ可読コードを有するプログラム製品であって、当該コンピュータ可読コードが、実行されたときに、メディア情報ストリーム内の所定のコンテンツを検出するためのアルゴリズムのパフォーマンスを最適化するための方法を実行し、前記アルゴリズムが、パラメータセットの関数であり、前記方法が、
−  前記アルゴリズムの各実行ごとに前記アルゴリズムにおいてそれぞれのパラメータセットを使用しながら、前記アルゴリズムを少なくとも一回実行し、前記メディア情報ストリーム内の前記所定のコンテンツを検出するステップと、
−  前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する精度の程度を最大にするために、前記アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるステップと、
を有する、プログラム製品。
【請求項２１】
コンピュータ可読コードを有するプログラムを格納する記憶媒体であって、当該コンピュータ可読コードが、実行されたときに、メディア情報ストリーム内の所定のコンテンツを検出するためのアルゴリズムのパフォーマンスを最適化するための方法を実行し、前記アルゴリズムが、パラメータセットの関数であり、前記方法が、
−  前記アルゴリズムの各実行ごとに前記アルゴリズムにおいてそれぞれのパラメータセットを使用しながら、前記アルゴリズムを少なくとも一回実行し、前記メディア情報ストリーム内の前記所定のコンテンツを検出するステップと、
−  前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する精度の程度を最大にするために、前記アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるステップと、
を有する、
記憶媒体。
【請求項２２】
情報を交換するためのシステムであって、
−  少なくとも1つの第一情報装置と、
−  少なくとも1つの第二情報装置であって、
−  外部通信インタフェースを通じて当該第一情報装置に結合されているインタフェースと、
−  少なくとも1つのプログラムを格納しているメモリと、
−  当該メモリと当該インタフェースとに結合されているコントローラであって、当該コントローラが、当該メモリに格納されている前記プログラムの制御下で動作して方法を実行し、当該方法が、(a)前記アルゴリズムの各実行ごとに前記アルゴリズムにおいてそれぞれのパラメータセットを使用しながら、アルゴリズムを少なくとも一回実行し、供給されるメディア情報ストリーム内の所定のコンテンツを検出するステップであって、前記アルゴリズムが前記パラメータセットの関数である、前記ステップと、(b)前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する精度の程度を最大にする最適なパラメータセットを確定するために、前記アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるステップと、(c)前記アルゴリズムの少なくとも1つに相当する情報と前記最適なパラメータセットとを、前記インタフェースと前記外部通信インタフェース(6)とを通じて前記少なくとも1つの第一情報装置に転送するステップと、を有する、前記コントローラと、
を有する、前記第二情報装置と、
を有するシステム。
【請求項２３】
前記第一情報装置が、
−  当該第二情報装置の当該インタフェースに前記外部通信インタフェースを通じて結合されている、さらなるインタフェースと、
−  当該さらなるインタフェースに結合されているさらなるコントローラであって、当該さらなるコントローラが、当該さらなるインタフェースに応答して前記第二情報装置から前記情報を受信し、以下のステップ、すなわち、関連付けられているさらなるメモリに前記情報を格納するステップと、前記アルゴリズムにおいて前記最適なパラメータセットを使用しながら、前記アルゴリズムを実行し、供給される情報ストリーム内の前記所定のコンテンツを検出するステップ、のうちの少なくとも一方を行う、前記さらなるコントローラと、
を有する、請求項22に記載のシステム。
【請求項２４】
前記第一情報装置が、前記情報ストリームを当該インタフェースと当該外部通信インタフェースとを通じて当該コントローラに供給するように動作し、かつ、当該コントローラが、当該供給された情報ストリームを受信した後に前記方法を実行する、請求項22に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、ビデオ情報ストリーム内のコマーシャルまたはその他の所定のコンテンツを検索アルゴリズムを使用して検出することに関し、具体的には、遺伝的アルゴリズムなどの検索アルゴリズムを使用して1つのタイプのコンテンツから別のタイプのコンテンツへのトランジションを正確に検出するために、アルゴリズムのパラメータを進化させるための方法、装置、およびプログラムに関する。
【背景技術】
【０００２】
ブロードキャストビデオのコンテンツを編集および／または記録するパーソナルビデオレシーバ／レコーダおよびデバイスがますます普及しつつある。一つの例は、ユーザの好みに基づいて番組をハードディスクに自動的に記録するパーソナルビデオレコーダである。このようなシステムにおける調査に関する機能の一つは、コンテンツ検出である。例えば、コマーシャルを検出することのできるシステムでは、ビデオストリームに挿入される広告を置き換えたり（「コマーシャル交換」）、コマーシャルの最後でビデオを一時的に停止させて、コマーシャルの間に集中力をそらされたユーザが主番組のコンテンツを見逃すことを防ぐことが可能になる。また、コンテンツ検出によって、記録されたテレビ番組に挿入されているコマーシャルまたは宣伝の内容に興味のないユーザが、手動によって、またはスキップを自動的に実行するように設計されているデバイス（例えば、特許文献１を参照）を使用することによって、それらのコマーシャルを飛ばすことも可能になる。
【０００３】
コマーシャルを検出するための公知の方法は、多数ある。一つの方法は、高いカット速度、または、時間的に隣接するフレーム間のフェードや動作のトランジションなしでのシーンの突然の変化を検出することである。カットにはフェードを含めることができ、従ってカットは急激に切り替わるカットであるとは限らない。より確実な基準は、高いトランジション速度である。もう一つの指標は、音声のない黒フレーム（または単色／白黒フレーム）の存在であり、これはコマーシャル時間の最初を示すことがある。個々のコマーシャルセグメント(commercial segment)の前後には、通常、1つ以上の黒フレームが存在する。コマーシャルの別の公知の指標は、高い「アクティビティ(activity)」であり、この場合のアクティビティとは、2つの異なるフレームセットの間の輝度レベルの変化速度である。コマーシャルでは、コマーシャルではないビデオセグメントの間よりも、一般的にオブジェクトとシーンがより高速に動き、かつ、より頻繁に変化し、従って、コマーシャルは一般に「アクティビティ」で満たされている。少量のアクティビティが検出されると、コマーシャルが終了したと判断され、記録を再開することができる。
【０００４】
もう一つの公知の手法は、連続する黒フレームの間の時間的距離を測定し、測定された時間的距離が所定のしきい値より大きいかまたは小さいかに基づいてコマーシャルの存在を判断することである。さらに別の手法では、イメージのマッチングに基づいてコマーシャルが識別される。この場合、イメージのコンテンツの品質の差が指標として使用される。
【０００５】
Bonnerらによる特許文献２に開示されている手法など、黒フレームを識別するための別の手法では、入力信号の電圧レベルがしきい値以下に降下するときを感知する。Igguldenらによる特許文献３に開示されている手法など、さらに別の手法では、コマーシャルを含めて番組全体を記録する。黒フレームがブロードキャストされると、マークが付される。記録の後、プロセッサが、黒フレームの間の時間間隔がコマーシャルなのか番組なのかを判断する。この判断は、単純な方式によって達成される。時間間隔が、5分のしきい値より短い場合には、コマーシャルであると判断される。再生時、デバイスは、コマーシャルであると判断された領域を過ぎるまでテープを早送りする。残念なことに、5分の中に2つの黒フレームのそれぞれが存在することは、照明が薄暗かったり暗いシーンの間にも起こりうるため、必ずしもコマーシャルを表さない。
【０００６】
上記に参照されている手法のすべては、有望な結果を示し、それぞれの意図された目的には良好に適合しうるが、少なくともいくつかの場合には、コマーシャルなどのコンテンツを検出するときにおける信頼性と正確さが不足することがある。この問題の一因となりうる一つの重要な要因は、これらの手法において、しきい値など、不適切または最適ではないアルゴリズムパラメータが使用されることである。コンテンツ検出手法において使用するための最適なパラメータ値をあらかじめ選択すること（特に、パラメータの選択が手動で行われるとき）は難しいことがあるため、これらの手法で極めて正確な結果が得られるようにするための最適な値を確実に選択することはできない。また、最適なパラメータ値が使用されている場合でさえも、コマーシャルの製作者は、それらの値が無効になるようにコマーシャルの様々な特徴を変化させて、コマーシャルコンテンツがコマーシャル検出アルゴリズムによって正しく検出されないようにすることができる。従って、ビデオコンテンツ検出アルゴリズムにおいて使用される最適なパラメータ値を、選択されたビデオストリームにそのアルゴリズムを適用することに基づいて自動的に認識することによって、これらの問題を克服し、これによって、ビデオストリームに含まれている所定のコンテンツを正確かつ高い信頼性で検出することのできる手法を提供する必要性がある。
【０００７】
【特許文献１】米国特許第5,151,788号明細書
【特許文献２】米国特許第4,314,285号明細書
【特許文献３】米国特許第5,333,091号明細書
【特許文献４】米国特許第6,100,941号明細書
【特許文献５】米国特許出願第09／417,288号明細書
【特許文献６】米国特許出願第09／854,511号明細書
【特許文献７】米国特許第5,390,283号明細書
【非特許文献１】「遺伝的アルゴリズムと進化的プログラミング（Genetic Algorithms And Evolutionary Programming）」（Stuart Russellら、Artificial Intelligence: A Modern Approach、1995年、第20.8章、p.619〜621）
【非特許文献２】「CHC適応検索アルゴリズム：非伝統的な遺伝子組み換えに従事するときの安全な検索方法（The CHC Adaptive Search Algorithm: How To Have Safe Search When Engaging In Nontraditional Genetic Recombination）」（Larry Eshelman、Foundations Of Genetic Algorithms、1991年、p.265〜283）
【発明の開示】
【課題を解決するための手段】
【０００８】
本発明の目的は、パラメータの関数であるメディアコンテンツ検出アルゴリズムがメディア情報ストリーム内の所定のコンテンツを検出することができるように最適化されたこれらのパラメータ値を自動的に認識するための方法、装置、およびプログラムを提供することである。
【０００９】
本発明の別の目的は、コマーシャルなどの所定のコンテンツの存在についてビデオストリームまたはその他のメディア情報ストリームを評価するためのアルゴリズムを実行し、かつ、アルゴリズムが所定のコンテンツを最大の精度で検出することができる値が確定されるまで、アルゴリズムのパラメータを自動的に変化させる、方法、装置、およびプログラムを提供することである。
【００１０】
本発明のさらなる目的と利点は、図面と以下の説明を考慮することによって明らかになるであろう。
【００１１】
本発明の前述の目的は、メディア情報ストリーム（例：複数のフレームに分割されているビデオ情報、および／またはオーディオ情報など）内の1つ以上のコマーシャルなど所定のコンテンツを検出するためのアルゴリズムのパフォーマンスを最適化するための方法と、この方法に従って動作するプログラムおよび装置によって達成される。このアルゴリズムは、パラメータセットの関数であり、この場合に、各パラメータセットは本文書においては染色体とも称される。各パラメータは、所定の検出対象（例：コマーシャルまたはその他の検出対象）がメディア情報ストリーム内に存在しているか否かを、満たされているか否かに応じて示す傾向にある条件を表すしきい値であることが好ましい。
【００１２】
本発明の実施例によると、前記方法は、前記アルゴリズムの各実行時に前記アルゴリズムにおいてそれぞれのパラメータセットを使用しながら、前記アルゴリズムを少なくとも一回実行し、前記メディア情報ストリーム内の前記所定のコンテンツを検出するステップと、前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する精度の程度を最大にするために、前記アルゴリズムにおいて使用されている少なくとも一組のそれぞれのパラメータセットを自動的に進化させるステップと、を有する。
【００１３】
本発明の1つの観点によると、前記アルゴリズムは、複数のフレームの中の少なくとも1つの黒フレーム／単色フレーム、平均カットフレーム距離、平均カットフレーム距離の傾向、商標名、カット／黒フレーム、平均強度カラーヒストグラム、無音声部分、ボリュームの変化、フレームの類似、文字検出、静止画像、あるいはビデオストリームまたはその他のタイプのメディア情報ストリーム内の所定のコンテンツの存在を示すことのできるその他のタイプの該当する特徴、のうちの少なくとも1つの検出に基づいて、所定のコンテンツを検出し、当該コンテンツは、望ましいコンテンツまたは望ましくないコンテンツでよい。
【００１４】
本発明の別の観点によると、自動的に進化させる前記ステップは、検索アルゴリズム（好ましくは遺伝的アルゴリズム）を実行して前記少なくとも一組のそれぞれのパラメータセットを進化させるステップを含む。
【００１５】
本発明の1つの実施例においては、前記進化させるステップは、前記アルゴリズムの各実行について、前記アルゴリズムが前記メディア情報ストリーム内の前記所定のコンテンツを検出する前記精度を確定するステップと、前記精度を確定する前記ステップの結果に基づいて、前記それぞれのパラメータセットのうちの少なくとも1つを選択するステップと、前記選択するステップにおいて選択された前記少なくとも一組のパラメータセットに基づいて、少なくとも1つの子孫パラメータセットを生成するステップと、を含む。次に、最も正確な結果をもたらすように確定された（1つ以上の）子孫パラメータセットおよび／または（1つ以上の）元のパラメータセットが、アルゴリズムのさらなるそれぞれの実行において使用され、必要な場合、アルゴリズムのパフォーマンスの精度を実質的に最大にするパラメータセットが確定されるまで、1つ以上のさらなる子孫パラメータセットが再び生成される。
【００１６】
このような高パフォーマンスの（「最適な」とも称される）パラメータセットが識別された後、そのセットは、メディア情報ストリーム内の所定のコンテンツが正しくかつ正確に検出され得るように、任意のデバイス内の対応するアルゴリズムにおいて使用することができる。アルゴリズムは、サーバおよび／またはローカルの情報機器に属していることができ、パラメータセットおよび／またはアルゴリズム自体は、サーバからローカルの情報機器に、またはこの逆にダウンロードすることができる。
【００１７】
本発明は、添付されている図面に関連している好ましい実施例の詳細な説明から、より容易に理解されるであろう。
【００１８】
異なる図面内に登場する同じ参照数字の要素は、同じ要素を指すが、すべての図面の説明の中で参照されていないことがある。
【発明を実施するための最良の形態】
【００１９】
本発明を実施するのに適しているハードウェアシステム1のブロック図である。図示されている実施例においては、システム1は、サーバ2と少なくとも1つのユーザ情報機器4とを有する。サーバ2と情報機器4は、インタフェース6を通じて互いに双方向に結合されている。インタフェース6は、サーバ2を情報機器4に結合するための様々なタイプの相互接続機器とインタフェースを含むことができ、例えば、適用されるシステム設計と動作基準とに応じて、1本以上のワイヤ、ケーブル、スイッチ、ルータ、光ファイバ、無線インタフェース、1つ以上のネットワーク（例：インターネットおよび／または所有権の保持されているその他のネットワーク）、モデム、および／または、その他の適切なタイプの通信機器／インタフェースを含むことができる。ただし、便宜上、このような機器は図1には示されていない。
【００２０】
個々の情報機器4は、例えば、PC、パーソナルビデオレコーダ（PVR）、ビデオカセットレコーダ（VCR）、デジタルビデオレコーダ（DVR）、パーソナルテレビジョン受信機（PTR）、DVDプレイヤー等を含むことができる。ただし、その他の適切なタイプのユーザ情報機器を使用することもできる。図1には1つのサーバ2と1つのユーザ情報機器4のみが示されているが、サーバ2と通信することのできるユーザ情報機器の数と種類は、幅広く変えることができる。同様に、個々のユーザ情報機器と通信するサーバ2の数は、例えば、ユーザのニーズおよび地理的な場所、適用されるシステム設計、動作基準などに応じて、変えることができる。留意すべき点として、本発明の教えは、特定のタイプのサーバコンピュータまたは情報機器での使用に制限されるものとして解釈されないものとする。一般的には、本発明の教えは、ビデオ情報、オーディオ情報、および／または、ビデオとオーディオを組み合わせた情報などのメディア情報を処理できる適合するタイプのデバイスと組み合わせて使用することができる。
【００２１】
サーバ2は、異なるポイント間での情報の送信、格納、および受信を支援するコンピュータ、またはコンピュータファームである。サーバ2は、プログラムを実行するのに必要な算術および／または論理演算を実行するためのコントローラ（1つ以上のマイクロプロセッサおよび／またはロジックアレイなど）（CPU）10を有することが好ましい。コントローラ10は、コンピュータ可読コード、すなわち、後述されているものなど、格納されているアプリケーションを実行する。サーバ2は、外部インタフェースに結合されている外部のソースデバイスおよび受信側デバイス（例：情報機器4）と情報を送受信することができるように、これらの外部インタフェース（インタフェース6や、サーバ2を結合することのできるその他の任意のインタフェース（図示されていない）など）にコントローラ10を双方向に結合するための少なくとも1つの通信インタフェース8も有する。ただし、便宜上、インタフェース6と機器4のみが示されている。この情報は、使用されている外部インタフェースに適用される規格に従うシグナリング情報と、ビデオデータ、オーディオデータ、およびその他のデータとを含むことができる。
【００２２】
サーバ2は、それぞれコントローラ10に結合されている1つ以上の入力ユーザインタフェース11と、同様にコントローラ10に結合されている少なくとも1つの出力ユーザインタフェース13も有することが好ましい。入力ユーザインタフェース11は、例えば、キーボード、マウス、トラックボール、タッチスクリーン、および／またはユーザが作動させることのできるその他の適切なタイプの入力デバイスを含むことができ、出力ユーザインタフェース13は、例えば、ビデオディスプレイ、液晶またはその他のフラットパネルディスプレイ、スピーカ、プリンタ、および／または、ユーザが出力情報を認識できるようにする他の任意の適切なタイプの出力デバイス、を含むことができる。
【００２３】
サーバ2は、コントローラ10に双方向に結合されている1つ以上の関連付けられているメモリ（例：ディスクドライブ、CD−ROMドライブ、ROM、および／またはRAM）も有することが好ましい。メモリ15は、一時的なデータと命令を格納し、さまざまなアプリケーションプログラムと、ルーチンと、コントローラ10がサーバ2の全体的な動作を制御するために使用するオペレーティングプログラムも格納する。例えば、UNIXまたはWindows NTなどのオペレーティングシステム17は、メモリ15に格納されていることが好ましく、例えばビデオエンコーダ19、ビデオデコーダ21、フレームグラバー23、カット検出器24などの多数のアプリケーションも、このメモリ15に格納することができる。ただし、その他のタイプのオペレーティングシステムとアプリケーションソフトウェアも使用することができ、および／または、アプリケーション19, 21, 23などの1つ以上のアプリケーションをアプリケーションソフトウェアとしてではなくサーバ2の中の個別のハードウェアコンポーネントとして具体化することができる。ビデオエンコーダ19は、コントローラ10によって必要性が認識されたときに使用され、従来の方法でビデオ情報を符号化する。ビデオデコーダ21は、コントローラ10によって必要性が認識されたときに使用され、圧縮されているビデオデータを従来の方法でデコードする。フレームグラバー23は、ビデオ情報ストリームから1つのフレームをキャプチャする目的でコントローラ10によって使用されるソフトウェアを含んでおり、キャプチャされたフレームは以降に処理することが可能である。カット検出器24は、例えば、シーンの変化が起きたかを公知の方法で検出する。
【００２４】
本発明の1つの実施例によると、メモリ15は、さまざまなカウンタと変数を格納する。これらには、例えば、変数Actual#CommFrames、変数CommercialProbability、カウンタTotalIdentified、変数LastUniColor、カウンタ#CorrIdentifiedなどがあり、これらの使われ方については後から説明されている。また、メモリ15は、本発明による方法を実施するためのルーチン、すなわち、ビデオ情報ストリーム内の所定のコンテンツ（例：コマーシャルまたはその他のコンテンツ）を、多数のパラメータ（例：しきい値）の関数である所定のコンテンツ検出アルゴリズムを使用して検出するためのルーチンと、コンテンツ検出アルゴリズムが所定のコンテンツを少なくとも所定のレベルの精度で検出することができるように最適化されたパラメータの値を自動的に認識するためのルーチンも格納していることが好ましい。この方法は、図3および図4a, 4bに関連して後から説明される。
【００２５】
本発明の観点によると、メモリ15は、本発明の方法を実施するためにルーチンにおいて使用される複数の染色体も格納していることが好ましい。各染色体は、上述されている所定のコンテンツ検出アルゴリズムにおいて使用するのに適合するタイプの1つ以上のパラメータを含んでいることが好ましい。本発明の観点によると、コンテンツ検出アルゴリズムの少なくとも一部は、1つの手法、例えば、平均カットフレーム距離検出手法、平均カットフレーム距離傾向検出手法、商標名検出手法、黒フレーム検出手法、カット／黒フレーム検出手法、フレーム類似性検出手法、文字検出手法、平均強度カラーヒストグラム手法、静止画像検出手法、または、メディア情報ストリーム内の所定のコンテンツを検出する目的で使用できる既存または今後開発される他の任意の手法、を実行する。これらの手法の少なくともいくつかの説明のため、(1) Nevenka Dimitrova、Thomas McGee、Herman Elenbaas、Eugene Leyvi、Carolyn Ramsey、およびDavid Berkowitzによる特許文献４「ビデオデータストリーム内に配置されているコマーシャルを特定するための装置および方法（Apparatus and Method for Locating a Commercial Disposed Within a Video Data Stream）」（公開日：2000年8月8日）（以下、「特許文献４」と称する）、(2) Nevenka Dimitrova、Thomas McGee、およびLalitha Agnihotriによる特許文献５「コマーシャルおよび他のビデオコンテンツの自動的なシグネチャベースの発見、認識、および抽出（Automatic Signature−Base Spotting, Learning and Extracting of Commercials and Other Video Content）」（出願日1999年10月13日）（以下、「特許文献５」と称する）、(3)特許文献６「データ圧縮構造を利用してのビデオコンテンツ検出方法およびシステム（Video Content Detection Method And System Leveraging Data−Compression Constructs）」（出願日2001年5月14日）を参照することができ、各文書は、本文書内で完全に記載されているかのように、その全体が本文書に参照文献として組み込まれている。
【００２６】
図2を参照すると、メモリ15に格納されている複数の染色体の例が示されている。この例においては、染色体はCr1〜Crnとして識別されており、ビデオ情報ストリーム内のコマーシャルコンテンツを黒フレーム／単色フレーム検出手法に基づいて検出するためのアルゴリズムにおいて使用するのに適している。各染色体Cr1〜Crnは、複数のパラメータ、すなわちしきい値を含んでおり、アルゴリズムはこれらのパラメータの関数である。しきい値は、コマーシャルコンテンツが存在する、または存在しないことを、満たされているか否かに応じて示す条件を表す。しきい値は、所定のビット長（例：9ビット）を持つビット文字列によって表されていることが好ましいが、別の実施例においては、ビット文字列の代わりに、適用される動作基準に応じて他の適合するタイプの値を使用することができる。以下は、ビデオ情報ストリーム内のコマーシャルコンテンツを検出するためのアルゴリズムにおいて使用されるしきい値の例であるが、留意すべき点として、以下に定義されているもの以外に、例えば使用されているコンテンツ検出アルゴリズムのタイプに応じて、これらのしきい値の代わりに、および／または、これらのしきい値に加えて、別のしきい値を使用することができる。
【００２７】
SeparationThreshold（間隔しきい値）（図2には「SeparationThld」として示されている） − このしきい値は、2つのコマーシャルの間に存在することが予測できる所定の最小時間的距離であり、ビデオ情報ストリーム内のコマーシャルセグメントの最初のフレーム（すなわちコマーシャルコンテンツを含んでいるフレーム）である可能性のあるフレームに先行する黒／単色フレームの検出を可能にする。後から説明されているように、黒／単色フレームは、このフレームと、最後に検出されたコマーシャルセグメントの直後として前に検出された黒／単色フレームとの間の時間的距離が、SeparationThresholdの値より大きい場合、コマーシャルに先行するフレームとして予備的に識別することができる（本文書において使用される場合、用語「コマーシャルセグメント」は、コマーシャルコンテンツを含んでおりかつ1つのコマーシャルを形成する連続するフレームの集合を意味する）。
【００２８】
UnicolorlnSuccThreshold（連続単色フレームしきい値）（図2には「UnicolorlnSuccThld」として示されている） − このしきい値は、コマーシャルセグメント同士、またはコマーシャルセグメントとコマーシャル番組ではないセグメントとを隔てていることが予測される黒／単色フレームの最小数を表す。後から説明されているように、（コマーシャルセグメントの最後のフレームの後に）連続して検出される黒／単色フレームの数がUnicolorInSuccThresholdより大きい場合、コマーシャルの最後である可能性のあるフレームの出現を認識することができる。
【００２９】
MinCommercialThreshold（最小コマーシャルしきい値）（図2には「MinCommercialThld」として示されている） − このしきい値は、個々のコマーシャルセグメントの所定の予測される最小時間長を表し、コマーシャルの最初である可能性のあるフレームとコマーシャルの最後である可能性のあるフレームの判断を確認する必要がないかを判断するために使用される。コマーシャルの最初および最後である可能性のあるフレームは、これらを隔てている時間的距離がMinCommercialThresholdの値より小さいと判断される場合、確認されない。
【００３０】
MaxCommercialThreshold（最大コマーシャルしきい値）（図2には「MaxCommercialThld」として示されている） − このしきい値は、個々のコマーシャルセグメントの所定の予測される最大時間長を表し、このしきい値も、潜在的なコマーシャルの最初と潜在的なコマーシャルの最後の判断を確認する必要がないかを判断するために使用される。潜在的なコマーシャルの最初と最後は、これらを隔てている時間的距離がMinCommercialThresholdの値より大きいと判断される場合、確認されない。
【００３１】
RestartThreshold（再スタートしきい値）（図2には「RestartThld」として示されている） − このしきい値は、（コマーシャルセグメントが開始された後に）コマーシャルセグメントに一般的に含まれていることが予測される所定のフレーム数を表す。後から説明されている方法の実行中、現在のフレームと最後に検出されたコマーシャルとの間の時間的距離がこのしきい値を超える場合、潜在的なコマーシャルセグメントが確かにコマーシャルであるかの確認は行われない。
【００３２】
DistForSuccThreshold（連続黒フレーム間距離しきい値）（図2には「DistForSuccThld」として示されている） − このしきい値は、予測される最大のコマーシャル持続時間に相当し、連続的に検出されるコマーシャルを隔てている2つの連続する黒／単色フレームの間の所定の予測される最大時間的距離を表す。後から詳細に説明されているように、このしきい値は、(1)検出された黒／単色フレームが、以前に検出された黒／単色フレームの直後であるか否かを判断するためと（検出された黒／単色フレームと、以前に検出された黒／単色フレームの1つとの時間的な隔たりがDistForSuccThresholdの値より小さい場合、これらの黒／単色フレームは連続するとみなされる）、(2)コマーシャルの最後のフレームの直後の最初の黒／単色フレームを検出する（この検出は、連続的に検出された2つの黒フレームの間の時間的距離が積2*DistForSuccThresholdよりも大きい場合に起こる）ためと、(3)潜在的なコマーシャルの最初または最後の判断を確認する必要があるか否かを判断するため、に使用される。
【００３３】
上述されている様々な染色体しきい値を本発明の模範的な実施例において使用する方法については、以下に詳細に説明されている。
【００３４】
図1を参照して、サーバ2のその他のコンポーネントについて説明する。情報機器4またはその他のデバイス（例：ビデオカメラなど）（図示されていない）などのソースデバイスから供給されるビデオ情報をサーバ2に送信し、少なくとも1つの通信インタフェース8を通じてサーバ2に入力することができる。入力されるビデオ情報は、例えば、使用されているソースデバイスや関連する外部インタフェースのタイプに応じて、デジタル情報またはアナログ情報でよく、また、圧縮形式または非圧縮形式でよい。サーバ2には、A／Dコンバータ9aとD／Aコンバータ9bも、コントローラ10の一部、または個別のコンポーネントのいずれかとして含まれていることが好ましい。A／Dコンバータ9aは、インタフェース6などの外部インタフェースから受信されたアナログ情報をデジタル形式に変換できるように、コントローラ10によってプログラムすることができる。D／Aコンバータ9bは、デジタル情報が外部インタフェース6に出力される前に、この情報を対応するアナログ情報に変換するために、コントローラ10によって使用することができる。ただし、使用されるインタフェースのタイプによっては、情報は、インタフェース6に転送させる前にアナログに変換させる必要がない。
【００３５】
上記に指摘されているように、コントローラ10は、適用されるパフォーマンス基準によっては、入力される圧縮ビデオ情報をビデオデコーダ21を使用してデコードすることもでき、また、適用されるパフォーマンス基準によっては、ビデオ情報が通信インタフェース8を通じて送信される前にビデオエンコーダ19を使用してビデオ情報を符号化することができる。
【００３６】
サーバ2について説明したので、次にユーザ情報機器4について説明する。ユーザ情報機器4は、少なくとも1つの通信インタフェース14と、そこに双方向に結合されているコントローラ16（CPU）とを有することが好ましい。インタフェース14は、1つ以上の外部通信インタフェース、例えば、インタフェース6や、情報機器4を結合できるその他の任意の外部インタフェース（図示されていない）に機器4を双方向に結合する。インタフェース14によって、機器4は、自身に結合できる外部ソースおよび受信側デバイス（例：サーバ2）と情報を送受信できるようになる。ただし、便宜上、サーバ2と1つの外部インタフェース6のみが示されている。この情報は、使用される外部インタフェースに適用される規格に従うシグナリング情報と、ビデオデータと、オーディオデータと、その他のデータとを含むことができる。
【００３７】
ユーザ情報機器4のユーザインタフェースには、出力ユーザインタフェース（ディスプレイ36など）と、入力ユーザデバイス（代表的にはキーマトリクス20）が含まれ、これらはすべてコントローラ16に結合されている。ただし、別の実施例においては、別の適合するタイプの出力および入力ユーザインタフェースを使用することもできる。キーマトリクス20には、ユーザ情報機器4の動作を開始するために使用されるさまざまなユーザインタフェースキー（例：PLAY、FAST FORWARD、STOP、REWIND、PAUSEキー）と、さまざまなメニュースクロールキーなどが含まれる。コマーシャルコンテンツをマークするためのMARKキーも、キーマトリクス20に含めることができる。
【００３８】
ユーザ情報機器4には、RAM、ROMなどのさまざまなメモリも含まれており、これらは一括的にメモリ18として示されている。メモリ18は、一時的なデータおよび命令と、さまざまなカウンタおよびその他の変数を格納することができ、また、さまざまなアプリケーション、ルーチン、およびオペレーティングプログラム27も格納していることが好ましい。例えば、情報機器4の1つの実施例によると、メモリ18は、ビデオエンコーダ33と、ビデオデコーダ35と、カット検出器29と、フレームグラバー31を格納することができる。ただし、これらの代わりに別のタイプのオペレーティングシステムとアプリケーションソフトウェアを使用する、および／または、機器33, 35, 31などの1つ以上のアプリケーションを、アプリケーションソフトウェアとしてではなく機器4の中の個別のハードウェアコンポーネントとして具体化することができる。サーバ2に格納されているビデオエンコーダ19とビデオデコーダ21に関連して、コントローラ16は、情報機器4に格納されているビデオエンコーダ33を使用してビデオ情報を符号化することができ、また、ビデオデコーダ35を使用して、圧縮されているビデオデータを従来の方法でデコードすることができる。フレームグラバー31には、コントローラ16がビデオ信号ストリームからの1つのフレームをキャプチャするために使用するソフトウェアが含まれており、キャプチャされたフレームは以後処理することができる。カット検出器29は、例えば、シーンの変化が起きたかを公知の方法で検出する。本発明の1つの実施例によると、メモリ18に格納されている少なくともいくつかのルーチンは、本発明による方法を実施し、この方法については図3および図4a, 4bに関連して後から説明されている。さらに、本発明の1つの実施例においては、メモリ18は、サーバ2に関連して上述されているさまざまなカウンタ、変数、および／または染色体の少なくともいくつかも格納するが、便宜上、これらについてはここではこれ以上説明しない。
【００３９】
サーバ2などのソースデバイス、またはその他のソースデバイス（例：ビデオカメラなど）（図示されていない）から供給される入力ビデオ情報は、少なくとも1つの通信インタフェース14を通じて機器4の中で受信することができる。情報機器4に入力されるビデオ情報は、サーバ2に入力される情報と同様に、使用されているソースデバイスや関連する外部インタフェースのタイプに応じて、圧縮または圧縮されていないデジタルまたはアナログ形式でよい。また、サーバ2と同様に、A／Dコンバータ11aとD／Aコンバータ11bも、コントローラ16の一部、または個別のコンポーネントのいずれかとして、情報機器4に含めることができる。A／Dコンバータ11aは、インタフェース6などの外部インタフェースから機器4によって受信されたアナログ情報を、コントローラ16に送られる前にデジタル形式に変換できるように、コントローラ16によってプログラムすることができる。D／Aコンバータ11bは、デジタル情報が外部インタフェース6に出力される前に、このデジタル情報を対応するアナログ情報に変換するために使用することができる。ただし、使用されるインタフェース6のタイプによっては、情報がインタフェース6に転送される前に情報をアナログに変換する必要がない。
【００４０】
システム1のさまざまなコンポーネントについて説明したので、次に、図3のフロー図を参照しながら本発明の1つの観点について説明する。本発明のこの観点によると、ユーザは、サンプルビデオクリップの中の選択される個々のフレームまたはその他のセグメントを、検出対象であるコマーシャルなどの所定のコンテンツを含むものとして、またはこのような所定のコンテンツを含んでいないものとして識別することができる。その後、サンプルビデオクリップは、上述されている染色体しきい値など多数のパラメータの関数である所定のコンテンツ検出アルゴリズムを使用して、このような所定のコンテンツの存在について自動的に評価される。次いで、必要な場合、検出の精度を高めるため、これらのしきい値のうち選択されたしきい値が、アルゴリズムの連続的な繰り返しの中で進化する（進化は遺伝的アルゴリズムなどのスーパーアルゴリズムの使用により起こる）。この進化は、アルゴリズムが所定のコンテンツを最大の精度で検出することができるように、使用されているすべての値の中でしきい値が最適化されたとみなされるまで、行われる。留意すべき点として、以下では、コマーシャルコンテンツの存在についてサンプルビデオクリップが評価される例に照らして本発明が説明されているが、本発明は、コマーシャルコンテンツを検出する用途のみで使用するようには意図されていない。例えば、別の実施例においては、本発明の方法は、例えば、対象とする用途に応じて、性描写、暴力またはその他のコンテンツタイプなど、コマーシャル以外の対象のタイプの情報コンテンツの検出に使用する目的で採用することもできる。
【００４１】
次に、図3を参照して、本方法は、ステップ100において開始される。この場合に想定されていることとして、メモリ15に格納されている少なくとも1つのサンプルビデオクリップがサーバ2に供給され、サンプルビデオクリップには、少なくとも1つのコマーシャルセグメント（上記に指摘されているように、本文書において使用される場合、用語「コマーシャルセグメント」は、コマーシャルコンテンツを有しかつ1つのコマーシャルを形成する1つ以上の連続するビデオフレームを意味する）と、コマーシャルセグメントの境界とが含まれている（通例、アルゴリズムの強力な染色体が確実に求められるように、さまざまなコマーシャルを有する内容豊富なサンプルビデオクリップが使用される）。一例として、これらの境界は、本文書に説明されているような黒／単色フレームを含むことができる。この場合、1つ以上の黒／単色フレームが各コマーシャルセグメントの（時間的な）直前に現れ、別の1つ以上の黒／単色フレームが直後に現れる。ただし、使用されるコンテンツ検出アルゴリズムのタイプに応じて、代わりに他の適合するタイプの境界を使用することができる。さらに想定されていることとして、サンプルビデオクリップは、(1)クリップのフレームのうち、コマーシャルコンテンツを含んでいるフレーム、および／または、含んでいないフレーム、(2)これらのフレームを識別するフレーム番号、および(3)コマーシャルコンテンツを含んでいるフレームの総数を表す変数Actual#CommFrames、を指定するコンテンツ識別子情報に関連付けられた状態でメモリ15に格納されている。例えば、サンプルビデオクリップとコンテンツ識別子情報は、任意の外部ソースからインタフェース8を通じてダウンロードすることができる。この場合、ビデオクリップとコンテンツ識別子情報は、コントローラ10に転送され、コントローラ10によってメモリ15に格納される。ビデオクリップは、例えば、テレビ信号の一部、インタフェース6からブロードキャスト式にダウンロードされるインターネットファイルの一部、ユーザ情報機器4からアップロードされるビデオクリップ、特定のWebサイトからダウンロードされるビデオクリップ、または、サーバ2に結合することのできる他の任意のソース（図示されてない）から供給されるビデオ信号でよい。別の例として、コンテンツ識別子情報は、サンプルビデオクリップがメモリ15に格納された後に、このメモリに格納させることができる。例えば、ユーザは、サンプルビデオの個々のフレームをディスプレイ13で見ながら、個々の各フレームにコマーシャルコンテンツが含まれているか否かを指定するコンテンツ識別子情報を入力ユーザインタフェース11を通じてサーバのメモリ15に入力することができ、その情報はフレーム情報に関連付けられて格納される。ステップ100においてさらに想定されていることとして、個々の染色体Cr1〜Crnのしきい値は、ユーザによって、またはメモリ15に格納されているルーチンによって指定される所定の（例えば、ビット文字列によって表されている）値に初期化されており、従って、染色体の最初の母集団P(t)が形成されており、本明細書において、「t」は母集団レベルを表す変数である。
【００４２】
その後、ステップ110においては、想定されていることとして、例えば、ユーザは、所定のコンテンツ、すなわちこの例においては検出対象であるコマーシャルの存在についてサンプルビデオクリップが検査されるように指定するコマンド情報を、入力ユーザインタフェース11を使用してコントローラ11に入力する。ステップ110においてコントローラ10に入力されるコマンド情報に応答して、コントローラ10は、図3にはステップ112として識別されている所定のコンテンツ検出アルゴリズムを実行する。この模範的な実施例の場合、このアルゴリズムは、図4a, 4bに示されている本方法のステップによってさらに詳細に示されており、このアルゴリズムは、実行されると、母集団P(t)の各染色体の中のしきい値に基づいて、コマーシャルコンテンツの存在についてサンプルビデオクリップを評価する。本発明の好ましい実施例においては、アルゴリズムは、母集団P(t)の各染色体に対して個別に実行され、従って、アルゴリズムは互いに平行して、または連続的に実行され、各染色体に対してアルゴリズムが少なくとも1回実行される。便宜上、以下では、1つのみの染色体に対してコンテンツ検出アルゴリズムが実行されるというコンテキストにおいて説明されているが、理解すべき点として、アルゴリズムは各染色体に対して個別に実行される。
【００４３】
図4aのステップ200において、コンテンツ検出アルゴリズムに入る。ここで想定されていることとして、フレームグラバー23が、公知のフレーム検出手法を使用して、サンプルビデオクリップ内の最初のビデオフレームを検出する（ステップ200における「Yes」）。その後、制御がステップ202に移動する。このステップにおいては、カット検出器24が、カット（すなわちシーンの変化またはコンテンツの変化）が起きたか否かを、検出された直前のフレーム（存在時）のコンテンツを基準としたときの検出されたフレームのコンテンツに基づいて、公知のカット検出手法を使用して判断する。ステップ202においてカットが検出されない場合（ステップ202における「No」）、制御はステップ206に移動し、このステップにおいては、後から説明されているように本方法が続行される。そうでない場合、すなわちステップ202においてカットが検出された場合、制御はステップ204に移動し、このステップにおいては、コントローラ10は、変数CommercialProbabilityを値「1」に設定する。次いで、制御はステップ206に移動する。留意すべき点として、フレーム検出ステップ220とカット検出ステップ202は、それぞれ、任意の適合する公知のフレーム検出手法とカット検出手法を使用して実行することができる。例えば、特許文献４に説明されている手法などがあげられ、この特許文書は、上記に指摘されているように、本文書に参照文献として組み込まれている。
【００４４】
ステップ206においては、コントローラ10は、ステップ200において検出されたフレームが黒または単色フレームであるか否かを、公知の黒フレーム／単色フレーム検出手法（例：特許文献４または特許文献５に説明されている黒フレーム／単色フレーム手法、または任意の他の適合する黒フレーム／単色フレーム検出手法）を使用して判断する。ステップ206の実行の結果として、ステップ200において検出されたフレームが黒または単色フレームではないと判断された場合（ステップ206における「No」）、制御は連結部Aを経て図4bのステップ220に移動する。ステップ220においては、後から説明されているように本方法が続行される。ステップ206の実行の結果として、ステップ200において検出されたフレームが黒または単色フレームであると判断された場合（ステップ206における「Yes」）、制御はステップ208に移動し、このステップにおいては、コントローラ10は、メモリ15に格納されているカウンタUniColorInSuccessionの値（ステップ112においてアルゴリズムに最初に入ったときには当初「0」に初期化されている）を「1」だけ大きくし、さらに、変数LastUniColorの値を、現在のフレームの番号を表すように更新する。その後、多数のステップが実行されて、ビデオクリップ内の検出された黒／単色フレーム付近にコマーシャルの最初または最後である可能性のあるフレームが存在するか否かが判断される。
【００４５】
ステップ210において、コントローラ10は、新たに検出された黒または単色のフレームと、最後に検出された黒／単色フレーム（存在時）との間の時間的距離が、DistForSuccThresholdの値を超えないか否かを判断する。この時間的距離は、例えば、最後に検出された黒／単色フレーム（存在時）の番号から、新たに検出された（例えばLastUniColorによって識別される）黒／単色フレームの番号を最初に減じた後、その減算結果に、適用される所定のフレーム速度の逆数（例：25フレーム／秒、30フレーム／秒、または24フレーム／秒の逆数）を乗じて、減算結果を時間の単位に変換することによって計算することができる。この乗算の積は、問題の時間的距離を表しており、DistForSuccThresholdの値と比較され、時間的距離がこのしきい値を超えているか否かが判断される。ステップ210の実行の結果として、「No」と判断される、すなわち、現在のフレームが、コマーシャルコンテンツを含んでいるフレームの直前にはおそらくは位置していないことが示される場合、制御はステップ214に移動する。このステップは、後述されているように実行される。ステップ210の実行の結果として、「Yes」と判断される場合、制御はステップ212に移動し、このステップにおいては、コントローラ10は、最後に検出されたコマーシャル（存在時）と新たに検出された黒／単色フレームとの間の時間的距離が、SeparationThresholdの値を超えているか否か、または以前にサンプルビデオクリップ内でコマーシャルセグメントが検出されていない（例：最初のコマーシャルセグメントが存在する）かを判断する。この時間的距離は、例えば、（図4bのステップ228の以前の実行に基づいてコマーシャルセグメントが確定されている場合）最後に検出されたコマーシャルセグメントの最後のフレーム（前のコマーシャルの最後の黒フレーム）の番号から、新たに検出された黒／単色フレームの番号を最初に減じた後、その減算結果に、適用される所定のフレーム速度の逆数を掛けることによって計算することができる。この乗算の積は、新たに検出された黒／単色フレームと、最後に検出されたコマーシャルの最後のフレームとの間の時間的距離を表しており、SeparationThresholdの値と比較され、時間的距離がこのしきい値を超えているか否かが判断される。
【００４６】
ステップ212の実行の結果として「Yes」と判断される場合には、制御はステップ216に移動し、このステップにおいては、コントローラ10は、ステップ200において検出されたフレームが、次のコマーシャルセグメントの最初のフレームに隣接している可能性があることを認識する。ステップ212の実行の結果として「No」と判断される、すなわち、現在のフレームが、次のコマーシャルセグメントの最初のフレームにおそらくは隣接していないことが示される場合、制御はステップ214に移動する。以下にこのステップについて説明する。
【００４７】
ステップ214において、コントローラ10は、ステップ112（図3）においてアルゴリズムが開始された以降に検出された黒／単色フレームの数（例：UniColorInSuccession）が、UnicolorInSuccThresholdを超えているか否かを判断する。ステップ214の実行の結果として「Yes」と判断される場合、制御はステップ218に移動する。このステップにおいては、コントローラ10は、ステップ200において検出されたフレームが、コマーシャルセグメントの最後の後に続く一連の黒／単色フレームの1つである可能性があることを認識する（すなわち、コマーシャルセグメントの最後である可能性のあるフレームが認識される）。ステップ214の実行の結果として「No」と判断される場合には、制御は連結部Aを経て図4bのステップ220に移動する。
【００４８】
図4bを参照して、ステップ220においては、コマーシャルセグメントの存在の可能性が前に確定されたか否かに関して判断される。制御は、この判断の結果に基づいて、ステップ232（後から説明されている）またはステップ222に移動する。例えば、ステップ206において「No」と判断されてステップ220に入った場合、ステップ220の実行の結果として、制御はステップ232に移動する。ステップ216においてコマーシャルセグメントの最初である可能性のあるフレームが認識された後に、またはステップ218においてコマーシャルセグメントの最後である可能性のあるフレームが認識された後に、ステップ220に入った場合には、ステップ220の実行の結果として、制御はステップ222に移動する。以下にこのステップについて説明する。
【００４９】
ステップ222においては、コントローラ10は、コマーシャルセグメントである可能性のあるセグメントのおよその持続時間が所定の時間期間以内であるかを判断する。例えば、ステップ222は、コントローラ10によって実行されて、（ステップ218の最後の実行において）コマーシャルセグメントの最後の後に続く可能性のある黒／単色フレームであると最後に判断されたフレームと、（それより前のステップ216の実行において）次のコマーシャルセグメントの最初のフレームに隣接している可能性があると判断されたそれより前のフレームとを隔てている時間的距離が、MinCommercialThresholdの値より大きく、かつMaxCommercialThresholdの値より小さいかを判断する。ステップ222の実行の結果として「No」と判断される場合、制御はステップ232に移動する。そうでない場合、すなわちステップ222の実行の結果として「Yes」と判断される場合は、制御はステップ224に移動し、このステップにおいては、コントローラ10は、変数CommercialProbabilityの値を調べて、これが「1」に等しいか否かを判断する。ステップ224において、変数CommercialProbabilityの値が「1」に等しいと判断される場合には、制御はステップ230に移動し、このステップにおいては、コントローラ10は、ステップ200において検出されたフレームが次のコマーシャルセグメントの最初のフレームに時間的に隣接する位置にあることを確認するレコードを、メモリ15に格納する。ステップ224において、変数CommercialProbabilityの値が「1」に等しくないと判断される場合には、制御はステップ226に移動する。このステップにおいては、コントローラ10は、（ステップ206において検出された）現在の黒または単色のフレームと、最後に検出された黒／単色フレーム（存在時）との間の時間的距離が、積2*DistForSuccThresholdを超えているか否かを判断する。ステップ226の実行の結果として「Yes」と判断される、すなわち、現在の黒／単色フレームが、コマーシャルセグメントの（コマーシャルコンテンツを含む）最後のフレームの直後に現れる最初の黒／単色フレームであることが確認される場合には、制御はステップ228に移動する。このステップにおいては、コントローラ10は、コマーシャルセグメントの最後の存在が検出されたことを示して確認するレコードをメモリ15に格納する。ステップ226の実行の結果として「No」と判断される場合には、制御はステップ232に移動する。以下にこのステップについて説明する。
【００５０】
ステップ232においては、コントローラ10は、(1)ステップ228または230において確認されたフレーム（存在時）と、それ以前のステップ228または230の実行において最後に確認されたそれより前のフレーム（存在時）との間の時間的距離が、RestartThresholdの値を超えているか否かと、(2)現在の黒／単色フレームと最後に検出された黒／単色フレーム（存在時）との間の時間的距離がDistForSuccThresholdの値を超えているか否か、を判断する。これらの時間的距離は、上述されている方法によって求められ、対応するしきい値と比較される。ステップ232の実行の結果として「Yes」と判断される場合、制御はステップ234に移動する。このステップにおいては、コントローラ10は、上述されている本方法のステップにおいてコマーシャルセグメントが検出されたなかったことを示すために、変数CommercialProbabilityの値を「0」に設定する。その後、制御は、連結部Bを経て図4aのステップ200に戻される。
【００５１】
これに対して、ステップ232の実行の結果として「No」と判断される場合、制御はステップ233に移動する。このステップにおいては、実行された最後の確認ステップがステップ228である場合（ステップ233における「Yes」）、制御はステップ233’に移動する。このステップにおいては、コントローラ10は、ステップ228において（コマーシャルセグメントの最後のフレームの直後に位置していると）確認された黒／単色フレームと、それより前のステップ230において（コマーシャルセグメントの最初のフレームの直前に位置していると）最後に確認された黒／単色フレームとの間の時間内の現れる（対応するフレーム番号によって識別される）フレーム群が、コマーシャルコンテンツを含んでおり、全体としてコマーシャルセグメントを表すことを指定する情報を、メモリ15に格納する。その後、ステップ236において、コントローラ10は、メモリ15に格納されているカウンタTotalIdentifiedの値（ステップ112に入ったときには当初「0」に初期化されている）を、ステップ233’においてコマーシャルコンテンツを含んでいるものとして識別されたフレームの数だけ増加させ、制御は、連結部Bを経て図4aのステップ200に戻される。これに対して、実行された最後の確認ステップがステップ230である場合（ステップ233における「No」）、制御は連結部Bを経て図4aのステップ200に直接戻される。
【００５２】
制御がステップ233, 234, 236のいずれかから連結部Bを経てステップ200に戻された後、ステップ200が上述されている方法で実行される。このステップの実行の結果として、サンプルビデオクリップ内の次のビデオフレームが検出された場合（ステップ200における「Yes」）には、制御はステップ202に移動し、このステップにおいては、上述されているように本方法が続行される。他のフレームが検出されない場合（ステップ200における「No」）、制御は図3のステップ114に移動し、このステップにおいては、本方法は以下のように続行される。
【００５３】
図3のステップ114には、メモリ15に格納されている母集団P(t)の一連の染色体の各染色体に対してステップ112のアルゴリズムが実行された後に入る。例えば、母集団P(t)の最初の染色体Cr1〜Crnのそれぞれに対してステップ112が実行される結果として、各染色体に対して、それぞれの染色体を使用してコマーシャル検出アルゴリズムによってステップ112においてコマーシャルコンテンツを含んでいるとして識別されたサンプルビデオクリップ内のフレーム（存在時）の総数を表す、それぞれのカウンタTotalIdentified（例えば、図4bのステップ236を参照）の値と、これらの1つ以上のフレームセットのフレーム番号とを指定する情報（例えば、ステップ233’を参照）とが、メモリ15に格納される。次に、ステップ114において、コントローラ10は、母集団P(t)の個々の各染色体について、それぞれの染色体に対してステップ112の実行時にステップ233’において識別されたフレーム（存在時）が、コマーシャルコンテンツを含んでいるものとして正しく識別されたか否かを判断する。この判断は、識別されたフレームを、図3のステップ100においてメモリ15にもともと格納されていた対応するコンテンツ識別子情報（フレームがコマーシャルコンテンツを含んでいるか否かを指定する）に関連させることによって行われる。例えば、特定の染色体に対するステップ112のアルゴリズムの以前の実行時に、特定のフレームがコマーシャルコンテンツを含んでいるとして識別され、かつ、メモリ15に格納されているコンテンツ識別子情報が、その同じフレームが確かにコマーシャルコンテンツを含んでいることを指定しているならば、そのフレームは、ステップ114において、コマーシャルコンテンツを含んでいるものとして正しく識別されていると判断される。ステップ114においては、各染色体に対して以前のステップ233’において識別された各フレームに対して、同様の判断が行われる。次いで、制御はステップ115に移動し、このステップにおいては、コントローラ10は、各染色体について、それぞれの染色体に対して（ステップ112の実行時にコマーシャルコンテンツを含んでいるものとして）正しく識別されているとステップ114において判断されたフレームの数を更新後の値が指定するように、メモリ15に格納されている母集団P(t)の最初の染色体Cr1〜Crnそれぞれに関連する#CorrIdentifiedの値を更新する。この結果として、各染色体について、（それぞれの染色体を使用して実行されたアルゴリズムの間に正しく識別されたフレームの数を示す）#CorrIdentifiedの個別の値が生成される。ステップ115が実行された後、制御はステップ116に移動し、このステップにおいては、コントローラ10は、（ステップ115において更新された）カウンタ#CorrIdentifiedの値と、各染色体に関連付けられている（ステップ112において更新された）TotalIdentifiedの値を使用して、それぞれの染色体のリコール(recall)と精度を、それぞれ、以下の公式F1とF2を使用して求める。
Recall = #CorrIdentified / Actual#CommFrames      (F1)
Precision = #CorrIdentified / TotalIdentified      (F2)
【００５４】
例えば、最初の母集団P(t)の各染色体C1〜Cnに対するステップ112と115の以前の実行の結果として、これらの染色体のカウンタ値#CorrIdentifiedとTotalIdentifiedが表Iに示されているように求められ、かつ、各染色体のActual#CommFramesの値が90であると想定すると、ステップ116において公式F1とF2を実行する結果として、対応する染色体Cr1〜Crnについて、表Iに示されているリコールと精度の値が計算される。これらの値は、コントローラ10によってメモリ15に格納される。
(表I)
2005513967.tif 000003
【００５５】
ステップ116が実行された後、制御はステップ117に移動する。このステップにおいては、本発明の1つの実施例によると、コントローラ10は、ステップ116において確定されたリコールと精度の値に基づく所定の選択方式を使用することによって、特定の染色体を選択する。ステップ117においては、所定の動作基準に応じて、任意の適合するタイプの選択方式を使用することができる。これらは、例えば、確率論的選択プロセス、選択の確率が適応度に比例するランダムプロセス、ステップ116において確定された精度とリコールのすべてのうちの上位50 %を与える染色体を選択する方式、所定の値に等しいかまたはそれより大きいリコールと精度の値が得られる染色体を選択する方式、または別の適合する適応度選択方式などである。この点について、ステップ117において使用することのできる適応度選択方式の例を説明する目的で、Stuart Russellらの論文「遺伝的アルゴリズムと進化的プログラミング（Genetic Algorithms And Evolutionary Programming）」（Artificial Intelligence: A Modern Approach、1995年、第20.8章、p.619〜621）（以下「遺伝的アルゴリズムの論文」と称する）と、Larry Eshelmanによる「CHC適応検索アルゴリズム：非伝統的な遺伝子組み換えに従事するときの安全な検索方法（The CHC Adaptive Search Algorithm: How To Have Safe Search When Engaging In Nontraditional Genetic Recombination）」（Foundations Of Genetic Algorithms、1991年、p.265〜283）（以下、「Eshelmanの論文」と称する）を参照することができるが、これらの代わりに他の適合する方式を使用することもできる。このような方式が実行されるようにコントローラ10をプログラムする方法は、本明細書の内容に関連する技術分野の当業者には容易に理解されるであろう。また、「ピックアンドプレイス(pick and place)」マシンにおけるコンポーネントのほぼ最適な配置を求めるためにCHCアルゴリズムを使用することの説明を目的として、Larry EshelmanとJames D. Schafferによる特許文献７「ピックアンドプレイスマシンを最適化するための方法（Method for Optimizing of a Pick and Place Machine）」（公開日：1995年2月14日）を参照することができる。この特許文献は、その全体が本文書に参照文献として組み込まれている。
【００５６】
この模範的な実施例においては、本明細書の場合、ステップ117は、次の公式（F3）を使用して各染色体の適応度（F）を求めた後、計算された適応度値（F）のすべてのうちの上位50 %を与える染色体を選択することによって、実行される。
(F) = (2*(精度)(リコール))/(精度+リコール)    (F3)
【００５７】
ステップ117が実行された後、制御はステップ118に移動する。このステップにおいては、本発明の1つの実施例によると、ステップ117において選択された個々の各染色体が、これらの選択された染色体のうちの別の染色体とランダムに対にされる。対にされた染色体が排他的でないと判断される場合、選択された別の染色体と対にされる。例えば、1つの実施例においては、ステップ118において染色体が対にされた後（図5a）はランダムに対にされた2つの染色体Cr1およびCrnの例を示す）、対にされた染色体が排他的であるか否かが判断される。この判断は、各対について、対の染色体の（例えば、ハミング距離によって測定される）値が、少なくとも排他的しきい値（例えば、所定のビット文字列長または何らかの他の適合する値）だけ互いに異なっているか否かを調べることによって行われる。一例として、図5aにおける染色体の対の対応するビットのうちの6個は互いに異なっており、従って、排他的しきい値がビット文字列長の1/4である場合、ステップ118のこの部分を実行すると、その結果、これらの染色体は排他的ではないと判断される。その後、本発明の1つの実施例によると、排他的ではないと判断された染色体が、交差ポイント300をランダムに選択することによって対にされた後、子孫の染色体が生成されるように（またはこれはHUXを使用して達成することができ、Eshelmanの論文を参照）、対のビットのうち交差ポイントの後に現れるビットが交換される。図5bは、図5aの親染色体によって生成された（ステップ118）このような子孫染色体Crk1, Crk2の例を示す。交差操作は、上記に参照されているEshelmanの論文の該当する部分に説明されている方法など、この技術分野において公知の任意の適合する方法によって実行することができる。
【００５８】
本発明の別の実施例によると、ステップ118における子孫の生成は、例えば、各染色体のビットの所定の部分（例：35 %）を、この技術分野において公知の方法によってランダムに（独立した確率で）反転させることにより、各染色体の値をランダムに突然変異させることによって行うことができる。図5cは、図5aの親染色体のうちの1つCr1と、この親染色体の突然変異の結果である子孫染色体Crk1の例を示している。本発明のさらに別の実施例においては、ステップ118において実行される突然変位は、交差ポイントをランダムに選択し、上述されている方法によってビットを交換した後、その結果のビット文字列（個々のビット）を上述されている方法によってランダムに突然変異させる、またはこの逆を行うことによって、実行することができる。
【００５９】
ステップ118を実行する結果として、複数の子孫染色体Crk1〜Crki（以下、まとめて子孫母集団K(t)とも称する）が生成される（有性生殖の場合、このステップにおいて親染色体の対の少なくとも1つが排他的ではないと判断されたものと想定され、この実施例の場合、子孫染色体の各対は親染色体の対応する対から生成されたものである）。ステップ118が実行された後、制御はステップ120に移動し、このステップにおいては、ステップ112に関連して上述されているコンテンツ検出アルゴリズムにおいて、最初の母集団P(t)の親染色体Cr1〜Crnの代わりに染色体Crk1〜Crkiのそれぞれが使用される。各染色体Crk1〜Crkiに対してこのアルゴリズムが実行された後、これらの染色体Crk1〜Crkiのそれぞれに対して、ステップ113〜116と同じステップが実行される。すなわち、ステップ120は、これらのステップにおいて最初の母集団P(t)の親染色体Cr1〜Crnの代わりに子孫染色体Crk1〜Crkiが使用されることを除いて、上述されているステップ112〜116と同じ方法によって実行される。ステップ112〜116についてはすでに上記に説明されているため、便宜上、これらのステップについてここではこれ以上詳しく説明しない。しかしながら、子孫染色体Crk1〜Crkiを使用してこれらのステップを実行する方法は、本明細書の内容に関連する技術分野の当業者には明らかであろう。ステップ120を実行すると、その結果として、（ステップ116の場合のように）各子孫染色体Crk1〜Crkiに対して与えられる適応度値（F）が、上述されているのと同じ方法によって求められる。
【００６０】
その後、制御はステップ122に移動し、このステップにおいては、本発明の1つの実施例によると、染色体が再び選択される。しかしながら、この選択は、前の染色体母集団P(t)のすべての染色体（例：Cr1〜Crn）と、子孫母集団K(t)のすべての染色体（例：Crk1〜Crki）との中から、ステップ117に関連して上述されているのと同じ染色体適応度選択方式、または既存あるいは今後開発される任意の他の適合する選択方式を使用することによって行われ、新しい母集団P(t=t+1)が生成される。その後、ステップ124において、(a)排他的しきい値が「0」に等しいか、および、(b)ステップ122において選択された各染色体の適応度値（F）が同じであるか、を判断することによって、収束性が判断される。(a)または(b)のいずれかが真でない場合、ステップ122において母集団K(t)から染色体が選択されていない（すなわちいずれの染色体も生き残らない）かについて、判断が行われる。このステップにおいて染色体が選択されなかった場合、排他的しきい値が「1」だけ減じられ（ステップ124における「N」）、制御はステップ118に戻される。このステップからは、前述されているように本方法が進行するが、この場合には、新たに生成された母集団の染色体が対にされる。これに対して、ステップ124において(a)と(b)の両方が真であると判断される場合（ステップ124における「Y」）、制御はステップ126に移動する。
【００６１】
ステップ126においては、本方法を終了する必要があるか否かが判断される。本発明の1つの実施例によると、このステップは、(i)本方法が最初にステップ100において開始された以降に、子孫母集団K(t)の所定の数の染色体がステップ120において評価された、または、(ii)本方法が最初にステップ100において開始された以降に、再スタートステップ130（後述されている）が所定の回数だけ実行された、のいずれかを判断することによって実行される。本発明の別の実施例においては、ステップ126は、条件(i)と(ii)の両方が満たされているかを判断するように実行することができ、または、別の実施例においては、条件(i)と(ii)の一方のみについて判断することができる。ただし、留意すべき点として、本文書に説明されている決定以外に、適用される動作基準に応じて、代わりに別の適合するタイプの決定を使用することができる。
【００６２】
ステップ126を実行した結果として「Yes」と判断される場合（ステップ126における「Y」）、制御はステップ128に移動し、このステップについては後から説明されている。そうではなく、ステップ126を実行した結果として「No」と判断される場合（ステップ126における「N」）は、制御はステップ130に移動し、このステップにおいては、ソフト再スタート手順が実行される。本発明の好ましい実施例においては、ステップ130のソフト再スタート手順は、ステップ116の前の実行において評価された母集団P(t)の染色体のすべてと、ステップ120の前の実行において評価された子孫の母集団K(t)のすべて（母集団P(t=t+1)）のうち（新たに生成された母集団P(t=t+1)のすべての染色体のうち）、最高の適応度（F）値を与える染色体（本文書においては、すべての染色体のうちの現在の最良染色体とも称する）をコピーし、複数（例：50）のコピーを生成することによって実行される。次いで、コピーのビットのうち所定の比率（例：35 %）を置き換え(replacement)なしにランダムに反転させることによって、結果のコピーのうち1つを除く各コピーを突然変異させることが好ましい。ステップ130の結果として、最高の適応度（F）値を与えた1つの突然変異されていない染色体のコピーと、そのコピーされた染色体を突然変異させた複数のバージョンとが、生成される。これらの（突然変異させていないコピーと突然変異させたコピーを含む）染色体は、まとまって新しい染色体母集団P(t)を形成する。その後、制御はステップ130からステップ112に戻され、このステップにおいては、前述されているように本方法が続行されるが、この場合には、アルゴリズムのさまざまなしきい値に対して、新しい染色体母集団P(t)が使用される。
【００６３】
次に、図3のステップ128について説明する。ステップ128においては、コントローラ10は、ステップ124とステップ126の両方が連続して結果「Yes」と判断された後に、母集団P(t=t+1)の中に残っている現在の最良染色体のしきい値を指定する情報をメモリ15に格納する。この情報は、ビデオストリーム内のコマーシャルコンテンツの存在を検出するための以降の動作に使用される。これらのしきい値は、この例においてはST2, UIST2, MinCT2, MaxCT2, RT2, およびDFST2（図2）である。これらは、図4a, 4bに表されているコンテンツ検出アルゴリズムがビデオ情報ストリーム内のコマーシャルコンテンツを最大の精度で検出できるようにすることを目的としたときに、それぞれ、染色体のすべてのしきい値UIST1〜UISTn, MinCT1〜MinCTn, MaxCT1〜MaxCTn, RT1〜RTn, DFST1〜DFSTnのうちの最良（例えば、「最適」または高パフォーマンス）であるとみなされる。
【００６４】
その後、サーバ2のユーザが、選択されたビデオストリーム、例えば、ステップ100においてメモリ15の中にもともと用意されていたビデオクリップ、または、サーバ2に供給される別のビデオ情報信号（例：ダウンロードまたはアップロードされたビデオクリップ、受信されたブロードキャストビデオ情報ストリーム、それ以外の方法で提供されるビデオクリップまたはその他のビデオセグメントなど）、を指定する情報を、入力ユーザインタフェース11を使用してサーバ2に入力し、このストリームが、例えば、検出対象であるコマーシャルの存在について評価されると想定する。この結果として、コントローラ10は、ステップ128において識別された、最適化された染色体しきい値ST2, UIST2, MinCT2, MaxCT2, RT2, およびDFST2を取得した後、図4a, 4bに示されているコンテンツ検出アルゴリズムを実行することによって、応答する。この場合、このアルゴリズムにおいて使用される適切なしきい値SeparationThreshold, UniColorInSuccThreshold, MinCommercialThreshold, MaxCommercialThreshold, RestartThreshold, およびDistForSuccThresholdそれぞれの値として、取得された値が使用される。このようにして、ビデオ情報は、これらのしきい値に基づいてコマーシャルコンテンツの存在について評価される。これらの最適化されたしきい値を使用することによって、コンテンツ検出アルゴリズムは、ビデオ情報内のコマーシャルコンテンツを最大の精度で検出することが可能になる。その後、ビデオ情報の評価の結果を、必要な目的（例えば、信号からコマーシャルコンテンツを削除する、または置き換える、など）に使用することができる。
【００６５】
ステップ128において識別された最適化されたしきい値は、ユーザ情報機器4など他のデバイスにも供給して、これらのデバイスにおけるコンテンツ検出アルゴリズムにおいてこれらのしきい値を使用できるようにすることができる。例えば、最適化された染色体しきい値をサーバ2の中のコンテンツ検出アルゴリズムにおいて使用する代わりに、または使用することに加えて、これらの値をユーザ情報機器4にダウンロードするかまたはそれ以外の方法で供給し、この機器4のメモリ18に格納することができる。その後、コントローラ16は、（図4a, 4bの）コンテンツ検出アルゴリズムの実行に使用する目的でこれらの値を取得し、機器4に送られる選択されたビデオストリームを、サーバ2に関連して上述されている方法と同様の方法によって、コマーシャルコンテンツの存在について評価することができる。別の実施例においては、例えば、図4a, 4bに示されているコマーシャル検出アルゴリズムなどのコンテンツ検出アルゴリズムに相当するソフトウェアを、最適化された染色体しきい値と組み合わせて、または個別に、サーバ2からユーザ情報機器4にダウンロードする、またはそれ以外の方法で提供することができる。次いで、これらの値を情報機器内のアルゴリズムにおいて使用し、情報ストリーム内の所定のコンテンツを検出することができる。図3の方法全体に相当するソフトウェアも、サーバ2から情報機器4にダウンロードするかまたはそれ以外の方法で提供する、あるいはこれらの機器4にあらかじめ格納しておき、この方法をこれらのデバイスにおいて実行して最適な染色体しきい値を求められるようにすることができる。求められた最適な染色体しきい値は、必要な場合、サーバ2にアップロードするかまたはそれ以外の方法で提供したり、あるいは、機器4における適合するコンテンツ検出アルゴリズムにおいて使用することができる。
【００６６】
留意すべき点として、本発明は、リコールおよび精度の値の関数として与えられる適応度に基づいて染色体を選択するように、ステップ117（およびステップ120の一部）が実行されるというコンテキストにおいて説明されているが、別の実施例においては、この選択は、染色体によって与えられるリコール値のみまたは精度値のみの評価に基づいて行う、または、精度の他の適切な測度に基づいて行うことができ、測度はスカラー型またはベクトル型でよい。
【００６７】
さらに留意すべき点として、本発明は、黒フレームまたは単色フレーム検出手法に基づいてコマーシャルの存在を識別するように、コンテンツ検出アルゴリズムが実行されるというコンテキストにおいて説明されているが、本発明は、この手法のみでの使用に限定されず、また、コマーシャルコンテンツのみの検出に限定されない。ビデオ情報（ビデオ情報に関連する少なくともいくつかの別の手法の例が上述されている）以外に、またはこれに加えて、アナログまたはデジタルビデオ信号、またはその他の任意のタイプのメディア情報（例：オーディオ）の中の任意のタイプの所定のコンテンツを検出するために使用できる、既存または今後開発される任意の別の適合するタイプの方法を使用することは、本発明の範囲内である。これらの手法においては、圧縮形式または非圧縮形式のいずれかにおいて取り出すことのできる、低レベル、中レベル、または高レベルの任意のタイプの特徴（例：複数の黒フレームの連続的な存在）を使用することができる。当業者には本明細書に照らして理解できるように、上記の説明において参照されている黒／単色フレーム検出手法以外の別のタイプの手法が使用される場合、各手法では、それぞれの手法においてパラメータとして使用するのに好適な適切なタイプの染色体が使用される。従って、理解すべき点として、本発明の方法は、任意のタイプのメディア情報に含まれている、任意のタイプの望ましいまたは不要なコンテンツの検出を最適化するために使用することができ、本発明の方法は、ビデオ情報内のコマーシャルコンテンツの検出のみに関連する使用に限定されない。さらに、本文書において使用されている句「情報ストリーム」は、本発明をオンライン用途に限定することを意図していない。実際に、オンラインまたはオフラインを問わず任意の適合するタイプの環境内で、例えば、ビデオ情報、オーディオ情報、ビデオとオーディオの組み合わせ情報など、任意の適用可能なタイプのメディア情報を評価することは、本発明の範囲内であり、情報ストリームは、対象の用途と所定の動作基準とに応じて、上記の情報のタイプの1つ以上を含むことができる。
【００６８】
さらに、本発明の1つの実施例においては、各染色体は、パラメータの複数のセットを含むことができ、各セットを対応する手法において使用することができる。例えば、各染色体Cr1〜Crn（および子孫染色体）は、図2に示されているさまざまなしきい値（これらは上述されているステップ112のアルゴリズムにおいて使用できる）に加えて、平均カットフレーム距離検出手法、平均カットフレーム距離トレンド検出手法、商標名検出手法、別のタイプの黒フレーム検出手法など、別のタイプの手法において使用するための適切なパラメータ値も含むことができる。各染色体に対する各手法は、それぞれの手法の適切なパラメータ値を使用して個別に実行することができる。1つの実施例においては、ユーザは、使用することが望ましい手法を（最初のステップ100において）選択し、次いで、その結果として、選択されていない手法からは結果が得られないように、選択された手法において使用するのに適する個々の染色体のパラメータ値以外のパラメータ値すべて（例：図4a, 4bに示されているアルゴリズムが選択されている場合、図2に示されている値以外のすべての値）が、「0」に初期化される。別の実施例においては、これらのパラメータ値を「0」に設定する必要がなく、各手法を個別のコンテンツ検出アルゴリズムとして実行して個別の結果をもたらすことができる。しきい値以外の別のタイプの情報を指定する遺伝子を含む染色体も、本発明に従って使用することができる。例えば、1つの遺伝子が、カラーヒストグラムをアルゴリズムA, B, C, またはD（図示されていない）によって計算すべきであることを指定することができる。別の遺伝子が、選択された特徴を組み合わせてコンテンツ分類に関する最終的な決定を行うための代替方法を指定することができる。また、染色体の値はビット文字列形式で表す必要はなく、代わりに、任意の別の適合する形式で表すことができる。従って、明確にすべき点として、本発明は、本文書に説明されているようにビット文字列によって表されているしきい値を含む染色体と組み合わせて使用されることに限定されない。
【００６９】
さらに留意すべき点として、本発明は、広義に解釈すれば、高パフォーマンスの染色体しきい値がサーバ2によって求められるというコンテキストにおいて説明されているが、本発明はこの用途に限定されない。例えば、上述されているように、図3および図4a, 4bに描かれている方法がユーザ情報機器4などの別の適合するデバイス内で実行されることも、本発明の範囲内である。これらの実施例においては、本方法は、デバイス（例：機器4）内でサンプルビデオクリップを上述されている方法によって評価することによって実行することができ、サンプルビデオクリップは、サーバ2などの任意のソースからデバイスに供給することができる。また、別の実施例においては、サーバ2の中のアルゴリズムにおいて使用されるしきい値は、情報機器4などの外部ソースからサーバ2に提供することができる。
【００７０】
上記の説明は、本発明の方法がソフトウェア命令を使用して実施されているというコンテキストにおいて説明されているが、別の実施例においては、本発明の方法を実施するために、このような命令の代わりにハードウェア回路を使用することができる。使用される回路の具体的なタイプは、通常の技能を有する者には本明細書に照らして容易に理解されるであろう。また、本発明は、上述されている遺伝的アルゴリズムを使用して、コンテンツ検出アルゴリズムにおいて使用される染色体値を進化させるというコンテキストにおいて説明されているが、別の実施例においては、対象の用途に応じて、別の適合するタイプの遺伝的アルゴリズムまたはその他のタイプの検索アルゴリズムを代わりに使用することができる。本発明に従って使用することのできる進化的アルゴリズムは多数存在し、本発明において使用する特定の進化的アルゴリズムは、任意に選択することができる。従って、理解すべき点として、本発明は、本文書に説明されている遺伝的アルゴリズムのみでの使用に限定されず、通常の技能を有する者には、本開示に照らして別のタイプの進化的アルゴリズムの使用が明らかであろう。
【００７１】
さらに留意すべき点として、本発明は、本方法が図3のステップ117において適応度に基づいて染色体を選択するというコンテキストにおいて説明されているが、本発明の別の実施例においては、このような選択を実行する必要はなく、染色体の選択は、ステップ122において親および子孫染色体の現在のグループの中から選択する目的で実行されるのみである。本明細書に照らして理解できるように、この実施例においては、ステップ118は、評価される現在の母集団内の染色体を対にするように実行される。
【００７２】
上記の説明に説明されているように、本発明は、パラメータの関数であるメディアコンテンツ検出アルゴリズムの精度を実質的に最大にするパラメータ値が得られるまで、パラメータ値を自動的に進化させるための新規の方法を提供する。この結果として、しきい値によって、アルゴリズムがメディア情報ストリーム内の所定のコンテンツを最大の精度で検出することが可能になる。この方法は、このようなコンテンツ検出アルゴリズムの精度が自動的に向上し、従ってユーザが適切なしきい値を手動で選択する作業が不要になることにおいて、有利である。さらに、最適なしきい値が自動的に決定されるため、本発明の方法は、コマーシャルの製作者がブロードキャストコマーシャルを編集することによってコマーシャルの正しい検出を妨げようとする試みを無効にすることができる。
【００７３】
本発明は、その好ましい実施例に関連して具体的に図示および説明されているが、当業者には、本発明における形式および細部を、本発明の範囲および精神から逸脱することなく変更できることが理解されるであろう。
【図面の簡単な説明】
【００７４】
【図１】サーバ2と少なくとも1つのユーザ情報機器4とを有する、本発明を実施するのに適しているハードウェアシステム1のブロック図である。サーバ2とユーザ情報機器4は、本発明に従って構築されかつ動作し、インタフェース6を通じて互いに双方向に結合されている。
【図２】図1のサーバ2のメモリ15、および／または、ユーザ情報機器4のメモリ18に格納することのできる複数の染色体Cr1〜Crnの例である。染色体Cr1〜Crnそれぞれは、ビデオストリームまたはその他のメディア情報ストリーム内のコマーシャルなどの所定のコンテンツを検出するためのアルゴリズムにおいて使用するのに適しているパラメータまたはしきい値を含んでいる。
【図３】所定のコンテンツの存在についてビデオ情報ストリームを評価するためと、アルゴリズムが所定のコンテンツを最大の精度で検出することができるようにアルゴリズムのパラメータを自動的に変化させるための、本発明による方法の論理フロー図である。
【図４ａ】図3のステップ112の間に実行されるサブステップを詳細に示している論理フロー図である。
【図４ｂ】図3のステップ112の間に実行されるサブステップを詳細に示している論理フロー図である。
【符号の説明】
【００７５】
1  システム
2  サーバ
4  ユーザ情報機器
6  インタフェース
8  通信インタフェース
9a, 9b  コンバータ
10  コントローラ
11  入力ユーザインタフェース
11a, 11b  コンバータ
13  出力ユーザインタフェース
14  通信インタフェース
15  メモリ
16  コントローラ
17  オペレーティングシステム
18  メモリ
19  ビデオエンコーダ
20  キーマトリクス
21  ビデオデコーダ
23  フレームグラバー
24  カット検出器
29  カット検出器
31  フレームグラバー
33  ビデオエンコーダ
35  ビデオデコーダ
36  ディスプレイ
100, 110, 112, 114, 115, 116, 117, 118, 120, 122, 124, 126, 128, 130, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 224, 226, 228, 230, 232, 233, 233’, 234, 236  ステップ
Cr1〜Crn  染色体
Crk1〜Crki  子孫染色体
【図１】
2005513967.tif 000004
【図２】
2005513967.tif 000005
【図３】
2005513967.tif 000006
【図４ａ】
2005513967.tif 000007
【図４ｂ】
2005513967.tif 000008
【国際調査報告】
2005513967.tif 000009
2005513967.tif 000010
2005513967.tif 000011