(57)【特許請求の範囲】
【請求項１】
プロセッサ及びメモリを備えるコンピュータと、前記コンピュータに接続されるディスプレイ及び入力デバイスからなる映像フレーム検索システムの前記プロセッサにより実行される方法であり、
映像のフレームを前記ディスプレイに表示させるステップと、
前記入力デバイスの操作による前記フレーム内の第１位置でのポイントの選択を受け取るステップと、
前記ポイントに重複するか又は重複しない前記フレーム内の映像の一部を示し、連続したフレームを通して継続するパーティクルを決定するステップと、
前記入力デバイスの操作による前記ポイントの第２位置への動きを受け取るステップと、
前記パーティクルを含む前記映像の第２フレームを決定するステップと、
前記ディスプレイに前記映像の第２フレームのインディケーションを出力するステップと
を備え、
前記パーティクルを含む映像の第２フレームを決定するステップは、前記ポイントに関連し、かつ無効にされていない前記継続するパーティクルを含む複数の候補フレームを決定し、これら候補フレームの内から、前記ポイントの第２位置と前記パーティクルとの間の間隔上の少なくとも一部に基づいて第２フレームを決定する、
方法。
【請求項２】
前記映像の第２フレームのインディケーションを出力するステップは、前記第２フレームを表示するステップを含む請求項１記載の方法。
【請求項３】
前記映像の第２フレームのインディケーションを出力するステップは、前記第２フレームのフレーム番号を表示するステップを含む請求項１記載の方法。
【請求項４】
さらに、時間的な重みつけを定める変数を受け取るステップを備え、
前記パーティクルを含む映像の第２フレームを決定するステップは前記時間的な重みつけ上の少なくとも一部に基づいて、映像のフレームの第２フレームを決定するステップをさらに含む請求項１記載の方法。
【請求項５】
前記第１フレームと候補フレームとの間の時間が増すと前記時間的な重みつけは減少する請求項４記載の方法。
【請求項６】
最大間隔を受け取るステップをさらに備え、
前記パーティクルを含む映像の第２フレームを決定するステップは、前記最大間隔の少なくとも一部に基づいた映像の第２フレームを決定するステップをさらに含む請求項１記載の方法。
【請求項７】
前記映像の第２フレームを決定するステップは、前記パーティクルが前記最大間隔よりも大きい前記第２位置からの間隔を有するところの映像のフレームを除去するステップをさらに含む請求項６記載の方法。
【請求項８】
前記映像の一つ以上のフレーム内の一つ以上のパーティクルを決定するために前記映像を前処理するステップをさらに含む請求項１記載の方法。
【請求項９】
第１位置で第１ポイントを受け取るステップは、複数の位置で複数のポイントを受け取るステップをさらに含む請求項１記載の方法。
【請求項１０】
前記ポイントに関連する前記フレーム内でパーティクルを決定するステップは、前記複数のポイントに関連する前記フレーム内の複数のパーティクルを決定するステップを含む請求項９記載の方法。
【請求項１１】
第２位置への前記ポイントの動きを受け取るステップは、新しい位置への前記複数のポイントの少なくとも一つの動きを受け取るステップを含む請求項１０記載の方法。
【請求項１２】
前記映像の前記第２フレームを決定するステップは、前記複数のポイントと前記複数の関連されたパーティクルの間の最小自乗距離を決定するステップを含む請求項１１記載の方法。
【請求項１３】
プロセッサ及びメモリを備えるコンピュータと、前記コンピュータに接続されるディスプレイ及び入力デバイスからなる映像フレーム検索システムの前記プロセッサにて実行されるプログラムコードがエンコードされているところのコンピュータ読み取り可能な記録媒体であり、そのプログラムコードは、
映像のフレームを表示させるプログラムコードと、
前記フレーム内の第１位置でのポイントの選択を受け取るためのプログラムコードと、
前記ポイントに重複するか又は重複しない前記フレーム内の映像の一部を示し、連続したフレームを通して継続するパーティクルを決定するためのプログラムコードと、
前記ポイントの第２位置への動きを受け取るためのプログラムコードと、
前記パーティクルを含む前記映像の第２フレームを決定するためのプログラムコードと、
前記映像の第２フレームのインディケーションを出力するためのプログラムコードと
を備え、
前記パーティクルを含む前記映像の第２フレームを決定するためのプログラムコードは、
前記ポイントに関連し、かつ無効にされていない前記継続するパーティクルを含む複数の候補フレームを決定し、これら候補フレームの内から、前記ポイントの第２位置と前記パーティクルとの間の間隔上の少なくとも一部に基づいて第２フレームを決定する
コンピュータ読み取り可能な記録媒体。
【請求項１４】
さらに、時間的な重みつけを定める変数を受け取るためのプログラムコードを備え、
前記パーティクルを含む映像の第２フレームを決定することは前記時間的な重みつけ上の少なくとも一部に基づいた映像のフレームの第２フレームを決定することをさらに含む請求項１３記載のコンピュータ読み取り可能な記録媒体。
【請求項１５】
最大間隔を受け取るためのプログラムコードをさらに備え、
前記パーティクルを含む映像の第２フレームを決定することは、前記最大間隔の一部に基づいた映像の第２フレームを決定することをさらに含む請求項１３記載のコンピュータ読み取り可能な記録媒体。
【請求項１６】
前記映像の一つ以上のフレーム内の一つ以上のパーティクルを決定するために前記映像を前処理するためのプログラムコードをさらに含む請求項１３記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
第１位置で第１ポイントを受け取るためのプログラムコードは、複数の位置で複数のポイントを受け取るためのプログラムコードをさらに含む請求項１３記載のコンピュータ読み取り可能な記録媒体。
【請求項１８】
前記ポイントに関連する前記フレーム内でパーティクルを決定するためのプログラムコードは、前記複数のポイントに関連する前記フレーム内の複数のパーティクルを決定するためのコードを含む請求項１７記載のコンピュータ読み取り可能な記録媒体。
【請求項１９】
第２位置への前記ポイントの動きを受け取るためのプログラムコードは、新しい位置への前記複数のポイントの少なくとも一つの動きを受け取るためのプログラムコードを含む請求項１８記載のコンピュータ読み取り可能な記録媒体。
【請求項２０】
前記映像の前記第２フレームを決定するためのプログラムコードは、前記複数のポイントと前記複数の関連されたパーティクルの間の最小自乗距離を決定するためのプログラムコードを含む請求項１９記載のコンピュータ読み取り可能な記録媒体。
【請求項２１】
プロセッサ及びメモリを備えるコンピュータと、前記コンピュータに接続されるディスプレイ及び入力デバイスを備える映像フレーム検索システムであり、
前記プロセッサは、
映像のフレームを前記ディスプレイに表示させる、
前記フレーム内の第１位置での前記入力デバイスによるポイントの選択を受け取る、
前記ポイントに重複するか又は重複しない前記フレーム内の映像の一部を示し、連続したフレームを通して継続するパーティクルを決定する、
前記入力デバイスによる前記ポイントの第２位置への動きを受け取る、
前記パーティクルを含む前記映像の第２フレームを決定する、及び
前記映像の第２フレームのインディケーションを前記ディスプレイに出力し、
さらに、前記パーティクルを含む映像の第２フレームを決定する際に、前記ポイントに関連し、かつ無効にされていない前記継続するパーティクルを含む複数の候補フレームを決定し、これら候補フレームの内から、前記ポイントの第２位置と前記パーティクルとの間の間隔上の少なくとも一部に基づいて第２フレームを決定する、
ために構成されるシステム。
【請求項２２】
前記プロセッサは、さらに複数の位置で複数のポイントを受け取るために構成される請求項２１記載のシステム。
【請求項２３】
前記プロセッサは、さらに前記複数のポイントに関連するフレーム内の複数のパーティクルを決定するために構成される請求項２２記載のシステム。
【請求項２４】
前記プロセッサは、さらに新しい位置への複数のポイントのうちの少なくとも一つの動きを受け取るために構成される請求項２３記載のシステム。
【請求項２５】
前記プロセッサは、さらに前記複数のポイントと前記複数の関連されたパーティクルの間の最小自乗距離を決定するために構成される請求項２４記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像の検索に関する。本発明は、さらに詳しくは１つ以上のフレームにおける映像場面の検索に関する。
【背景技術】
【０００２】
従来の映像検索及び編集は、特定のフレーム又はいくつかのフレームを探すために映像シーケンスの個々のフレームにわたる探索を必要としていた。例えば、パーキングロットの監視カメラからの映像は長時間の場面を記録しているが、特定の車の駐車スペースからの出庫を示すフレームが必要なだけかもしれない。従来の編集技術を用いるのであれば、使用者は前記車がその駐車スペースから出る時間を探し出すために全ての映像を順を追って検索しなければならない。この原始的な素朴な力任せの検索は、時間を浪費し、非効率的である。さらに、所望の場面が前記映像には存在していないかもしれない。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は前記実情に鑑みてなされたものであり、時間を浪費することなく、かつ効率よく所望の映像を検索することができる双方向映像フレーム検索システム及び方法の提供を目的とする。
【課題を解決するための手段】
【０００４】
本発明の具体例は、前記課題を解決するために、双方向の映像フレームの検索のためのシステム及び方法を含む。例えば、本発明の一実施例は、映像のフレームを表示させるステップ、前記フレーム内の第１位置での一ポイントの選択を受け取るステップ、及び前記ポイントに関するフレーム内のパーティクル（particle）を決定するステップを備える方法を含む。この方法は、さらに前記ポイントの第２位置への動きを受けるステップ、前記パーティクルと第２フレーム内の前記ポイントの第２位置との間の間隔（或いは距離）上の少なくとも一部に基づいた前記パーティクルを備える映像の第２フレームを決定するステップ、及び前記映像の第２フレームの指示を出力するステップを含む。
【０００５】
これらの実施例は、発明を限定するものでも及び特定するものでもなく、その理解を助けるための例を提供する。実施例は、詳細な説明のなかで説明され、さらに発明の説明はそこに提供される。本発明の種々の実施例によって提案される長所は、この明細書を検証することによってさらに理解される。
【発明の効果】
【０００６】
本発明によれば、時間を浪費することなく、かつ効率よく所望の映像を検索することができる双方向映像フレーム検索システム及び方法を提供できる。
【発明を実施するための最良の形態】
【０００７】
本発明の具体例は双方向映像フレーム検索のための方法、システム及び製品を提供する。本発明に係る方法、システム及び製品は多数の様式で具現化される。本発明のある具現化例は、例えば、映像制作編集のワークフローにおける非能率さを減少又は削除する。例えば、本発明の一実施例は、「これ編集して、そこ見て」などとして非能率さが一般に言及されるような、ユーザにインターフェースオブジェクトを操作させること及び結果を見るためにユーザに焦点を変えさせることよりも、映像それ自体を見せ及び編集させる。
【０００８】
（実例となる映像編集ツール）
本発明の一つの実例となる具現化例にあっては、映像を編集するためのコンピュータソフトウェアを作動するコンピュータシステムが編集用ウィンドウを表示する。前記ウィンドウ内にて、映像のフレームが表示される。前記映像フレームは、スクリーン上に一つ以上の視認される物体を含む。映像を編集するユーザは、特別な特徴を有している映像内で映像を通して手動的に検索することなしに、あるフレームを見つけることを所望する。本発明の実例となる具現化例を用いることで、ユーザは映像の一フレーム内にて関心のあるポイントを選び出す。例えば、ユーザはそのポイントを選ぶためにマウスを使う。ユーザは、それから、そのシーン内の新しい位置にそのポイントをドラッグする。前記具体例は、前記選択されたポイントが新しい位置に動いたところの映像内の一フレームを見つけることができる。例えば、ユーザが前記フレームの右側上の俳優に対応する一ポイントを選択したとする。ユーザは、その後、前記フレームの左側上新しい位置へ前記ポイントをドラッグすると、前記具体例は、前記俳優上の前記選択されたポイントが前記フレームの左側上の新規に選択された位置に最も近いところの映像のフレームを探す。例えば、前記映像のなかで、前記俳優は右から左へそのシーンを横切っており、さらに前記フレームの左側から去ったとする。一旦、前記具体例が前記映像内で適切なフレームを見つけると、前記システムは前記選択されたポイントのためのユーザに所望された位置に最も対応するフレームを表示する。
【０００９】
或いは、ユーザが選択した新しい位置に選択された位置が動くところの映像のフレームがなかったとする。例えば、前記俳優が前記スクリーンの左側上に現れないとする。そのような場合にあって、前記具体例は、ユーザによって選択された新しい位置に最も近い前記俳優のいるところのフレームを出力する。例えば、前記俳優は、前記左端部への全道筋よりもむしろ、そのシーンの中央にのみ歩く。ある場合において、前記具体例は前記俳優が、前記スクリーンの中央に前記俳優がいるような、前記左端での前記選択された位置の最も近くにいるところのフレームを表示する。
【００１０】
本発明の具現化例は、一つの映像を通して前方及び後方に迅速に移動するために用いられる。例えば、一つの具現化例は一つのコンピュータアプリケーションを備えており、ユーザは映像の一フレーム内で一つのポイントを選択し、さらに新しい位置に前記ポイントをドラッグする。ユーザが前記ポイントをドラッグすると、前記アプリケーションは、前記ポイントの位置に対応するフレームを出力する。これは、前記アプリケーションが前記映像を迅速に先送り又は巻き戻しするためである。例えば、ユーザが駐車している車上のポイントを選択し、そのポイントを駐車場所から離れて別の方向へドラッグすると、本発明の具体例は前記ポイントの動きに対応する映像のフレームを連続して出力する。したがって、ユーザが冗長な監視映像を調査している場合にあって、ユーザが関心のある車上のポイントを選択し、ユーザがその車が前記駐車場所から発車したときに通過したと思う方向に前記ポイントをドラッグしたとする。本発明の具体例は、前記駐車スポットを離れた前記車に関するフレームを発見し、さらに出力する。前記ユーザが、その後、前記駐車場所の出口に向けてポインタをドラッグすると、立ち去る車の知覚されたアニメーションが生じるので、連続したフレームが発見され、さらに出力される。これは、いつ特定の車が駐車場所から出たのかを発見するために、例えば、前記映像全体を通して早送りしたり、立ち去る車を見続けるというような、従来の探索技術を使用することなく、ユーザに冗長な監視映像からの探索を可能とさせる。
【００１１】
本発明の具体例は、さらに映像につながる一つの映像セグメントを充てるフレームを迅速に探しだすためにも使用される。対象物の所望の位置が周知であれば、ユーザは映像中の対象物に関するポイントを選択し、さらに前記所望の位置に前記ポイントをドラッグさせるだけでよい。前記所望のフレームは速やかに探しだされ、前記映像セグメントは前記映像中の適切な位置に簡単に挿入される。
【００１２】
この例は、ここで述べる全体的な主題を読者に紹介するために提供される。本発明は、この例に限定されるものではない。双方向映像フレーム検索のための製品及び方法の種々の具現化例に関するさらなる詳細は、以下に記述される。
【００１３】
（実例となるシステム）
いくつかの図を通して同様の要素に同様の数字を当てる図面を参照すると、図１は双方向映像フレーム検索のためのシステムを示す。システム１００は、コンピュータ１０１、表示デバイス１０２及び入力デバイス１０３を備える。コンピュータ１０１は、プロセッサ１１０及びメモリ１１１のようなコンピュータ読み取り可能な記録媒体を備え、前記表示デバイス１０２及び前記入力デバイス１０３と通信する。メモリ１１１は、双方向映像フレーム検索のためのアプリケーション１２０、前処理プログラム（プリ−プロセッサ）１３０、映像１２１及びパーティクル情報１２２を備える。プロセッサ１１０は、前記映像１２１を分析するプリ−プロセッサ１３０を実行し、パーティクル情報１２２を生成する。
【００１４】
この実例となる具現化例にあって、ユーザが前記アプリケーション１２０により前記映像を編集する前に、前記映像１２１は前処理される。前記プリ−プロセッサ１３０は前記映像１２１を分析し、さらに前記映像のフレーム内の特徴及び物体に関する情報を含むところのパーティクル情報１２２を生成する。前記プリ−プロセッサ１３０は、前記アプリケーション１２０による後での使用のために、コンピュータ読み取り可能な媒体上にパーティクル情報１２２を蓄積する。
【００１５】
パーティクルは、特定可能な、はっきりしている映像の一部を示し、さらに一つ以上の連続した映像フレームを通して継続する。例えば、俳優の腕上の光る領域内のピクセルに関係する。前記俳優の腕が動いたとき、前記関係する光る領域も同様に動く。プリ−プロセッサは、前記光る領域の動きも分析し、前記パーティクルが前記光る領域の動きに追従するように、前記映像の連続するフレームにわたって前記パーティクルの位置を変更する。前記光る領域がぼやけるか、或いはフレームの外に移動すると、前記関連パーティクルは無効となる。前記光る領域が後ほど再度現れたときには、新しいパーティクルが作りだされ、光る領域に関連付けられる。パーティクルが無効とされたときは、追従されるところの早期フレームが存続していても、前記映像の後のフレームにはそのパーティクルがもはや存在しないということに気づくべきである。例え新しいパーティクルが新しいフレームの同じ特徴に関連しているとしても、その代わりに新しいパーティクルが作りだされる。一具体例にあって、パーティクルは、見て明らかな特徴があるところの継続するフレームを通してのみ継続する。パーティクルのより詳しい説明は後述する。
【００１６】
前記プリ−プロセッサが前記映像の各フレームを分析すると、それは一つ以上の異なるパーティクルを作り出し、更新し、或いは無効にする。複雑なシーンを有する映像のフレームは、それぞれがそのフレーム内の特徴に関係付けられる、多くのパーティクルを有する。特徴が現れ、移動し、さらに消えると、前記プリ−プロセッサはその特徴に対応するパーティクルを作り出し、移動し、無効にする。前記プリ−プロセッサはまた前記映像の各フレーム用の各パーティクルの位置を記憶する。このように、作成された各パーティクルのために、パーティクルが内部に現れた映像の各フレームにわたって、パーティクルの位置が蓄積される。パーティクルの連続する位置（すなわち、パーティクルの動き）は、ここでは、その「トラック」として言及される。パーティクル情報１２２として蓄積された前記パーティクルトラックは、ユーザによって所望される特徴を有するフレームを見つけるために前記映像のフレームを検索するように本発明の具現化例にて用いられる。
【００１７】
一旦、パーティクル情報が決定され、蓄積されると、システム１００のユーザは、映像１２１及びパーティクル情報１２２を記憶媒体から取り出すため及びそれらをメモリ１１１にロードするために前記アプリケーション１２０を使用する。前記アプリケーション１２０は、前記映像１２１の第１フレームを表示デバイス１０２上に表示する。前記システム１００のユーザは、前記映像１２１のフレーム内の第１位置にてポイントを選択する。そのユーザは、その後、異なる位置に前記ポイントを動かすかもしれない。前記アプリケーション１２０は、前記入力デバイス１０３から第１位置での前記ポイントの選択情報を受け取ると、前記ポインタに関係するパーティクルを決定する。前記アプリケーション１２０はさらに、前記入力デバイス１０３から前記ポイントの異なる位置への移動情報を受け取る。前記アプリケーション１２０は、その後、前記第２フレームのパーティクルの位置とユーザによって選択された前記ポイントの第２位置との間の間隔にある程度基づいて、前記ポイントに関係するパーティクルを有する映像１２１の第２フレームを決定する。一旦、前記アプリケーション１２０が前記第２フレームを決定すると、前記アプリケーション１２０は、第２フレームを表示することにより、又は第２フレームのフレーム番号を表示することによるような、第２フレームのインディケーションを出力する。
【００１８】
ここで、さらにはこの詳細な説明を通して用いられる「第１フレーム」及び「第２フレーム」なる用語は、前記映像内の任意のフレームを言及するものであり、必ずしも前記映像の最初の二つのフレームではないことに留意されたい。
【００１９】
本発明の他の具体例が図２乃至６を参照して以下に詳細に説明される。図２は、本発明の一つの具体例に係る双方向映像フレーム検索のための方法２００を示す。図２に示した前記方法２００は、図１に示した前記システム１００に関して検討される。図３乃至６は、映像１２１の第１及び第２フレームの表示を示す。
【００２０】
前記方法２００は、前記システム１００が映像１２１の第１フレームを表示するところの、ブロック２０１で始まる。例えば、ユーザは前記表示デバイス１０２上に映像の第１フレームを表示するためにコンピュータ１０１上で映像編集アプリケーション１２０を実行する。前記映像編集アプリケーション１２０はコンピュータ−読み取り可能な媒体のような記憶媒体から映像１２１をメモリ１１１にロードする。前記アプリケーション１２０は、また、記憶媒体からパーティクル情報１２２をメモリ１１１にロードする。前記パーティクル情報１２２は、前記映像１２１を分析するためにプリ−プロセッサ１３０を実行することによって事前に生成されている。前記コンピュータ１０１は、その後、前記表示デバイス１０２上に前記映像の第１フレームを表示する。
【００２１】
図３に示された具現化例にあっては、前記映像１２１の第１フレーム３００が示されている。前記第１フレーム３００は、俳優３０１と同様に、例えば、木、鳥、及び歩道を含んでいる。図３に示された具現化例にあっては、第１フレームが示されているが、パーティクル情報１２２は表示されていない。パーティクル情報１２２は通常、前記方法２００を実行するときにシステム１００によって用いられ、ユーザにとっては通常有用ではない。けれども一具現化例にあっては、フレーム内のパーティクルは表示され、又は任意に表示されてもよい。
【００２２】
ブロック２０２にて、前記システム１００は映像の第１フレーム３００内の第１位置におけるポイント３０２の選択を受ける。システム１００を使用することで、ユーザは、マウス、タッチスクリーンあるいは他のデバイスのような入力デバイス１０３を、前記フレーム３００内のポイントを選択するために、利用することができる。例えば、図４に見られるように、ポイント３０２が俳優３０１の頭部に選択される。図４に示される具現化例にあって、ユーザによって選択された前記ポイント３０２は、その位置、選択されたフレームの番号、及び対象位置のような、ポイント３０２に関係する情報を含む。前記ポイントが初期に選択されると、前記ポイントの位置がデカルト座標として記憶される。前記対象の位置は、前記ポイントの位置として同じ座量にセットされるか、或いは“未定義の”値のようなデフォルト値としてセットされる。対象の位置は、前記ポイントの所望された新しい位置を後で記憶する。
【００２３】
ブロック２０３にて、一旦ユーザがポイントを選択すると、前記システム１００は前記ポイント３０２に関係するフレームのパーティクルを決定する。前記映像内の各フレームは、そのフレームに関係する０以上のパーティクルを有する。以下に十分に記述されるところの、前記パーティクルは、全般的に、前記フレーム内の特徴又は詳細に対応し、前記映像の連続したいくつかのフレームにわたって位置を変更する。前記システム１００がポイント３０２の選択を受け取ると、前記システム１００は前記選択されたポイント３０２に最も近接する前記フレーム３００範囲内でパーティクルを決定する。図４に示される具現化例にあって、前記ポイント３０２に最も近接するパーティクルは、前記選択されたポイント３０２と重複する。しかしながら、ユーザは、いかなるパーティクルとも重複しないポイントを選択するかもしれない。例えば、一具現化例にあって、一つのフレーム内のパーティクルは、ユーザには表示されない。そのような具現化例にあって、ユーザはパーティクルの位置に気がつかないかもしれないし、さらにパーティクルに関係のない任意のポイントを選択するかもしれない。
【００２４】
パーティクルに重複しないポイントをユーザが選択したところのシナリオにあって、本発明の一つの具現化例は前記ポイントに最も接近しているパーティクルを決定する。例えば、前記具現化例は前記ポイントから各前記フレーム内のパーティクルへのデカルト距離を算出し、前記ポイントに最も近いパーティクルを選択する。他の具現化例にあって、前記システムは前記ポイントと前記フレーム内の各パーティクルとの自乗距離を、前記パーティクル及びポイントのｘ座標及びｙ座標間の距離を自乗し、差分を加算することによって計算する。最も小さな自乗距離のパーティクルが最も近いパーティクルとして選択される。
【００２５】
前述した具現化例にあって、ユーザは一つのポイント３０２を選択した。しかしながら、他の具現化例にあって、ユーザはフレーム内の複数のポイントを選択できる。例えば、本発明の一つの具現化例にあって、入力デバイス１０３はマルチタッチタッチスクリーンのような、マルチタッチ入力デバイスを有し、ユーザに同時に複数のポイントを選択させる。そのような具現化例にあって、フレーム内で選択される各ポイントは異なるパーティクルにそれぞれ関連付けされる。或いは、選択されたポイントのいくつかは、同一のパーティクルに関連付けされる。例えば、二つの選択されたポイントが、同一のパーティクルに最も近いと、前記ポイントは同一のパーティクルにそれぞれ関連する。
【００２６】
一つ以上の選択されたポイントが前記関連パーティクルとして同一の座標に位置されないところのシナリオにあって、前記システムは前記ポイントと前記パーティクル間の間隔に関連されるオフセットを決定する。一つの具現化例にあって、前記オフセットは前記ポイントと前記パーティクル間の間隔であり、さらに詳しくは後述するように、前記映像内のフレームを検索するときに前記システムによって利用される。
【００２７】
ブロック２０４にて、前記システム１００は前記ポイント３０２の第２位置３０４への動きを受理する。図５に示されるように、ユーザは、ポイント３０２が矢印３０３の方向の新しい位置３０４に移動したのを指定する。一具現化例にあって、図５の矢印３０３は前記ポイント３０２の動きを示すが、ユーザには実際に表示されないことに留意すべきである。
【００２８】
ポイント３０２を動かすため、システム１００のユーザはフレーム内のカーソルを新しい位置３０４に動かし、さらに前記新しい位置３０４を選択するためにマウスボタンをクリックする。一つの具現化例にあって、ユーザはポイント上でクリックし、そのポイントを新しい位置にドラッグする。他の具現化例にあって、ユーザは複数の新しい位置或いは単一の位置よりもむしろ一つの区域を選択する。そのような具現化例は、ユーザに前記選択されたポイントが選択された位置に移動されたところの複数のフレームを見つけさせる。
【００２９】
図５に示された具現化例にあって、新しい位置３０４への動きは単一の動きとして受け取られる。しかしながら、一具現化例にあって、ユーザがポイント３０２を新しい位置にドラッグすると、前記システムは前記位置３０２の複数の動きを受け取る。そのような、具現化例にあって、前記システム１００は受信された各動きのために方法２００を実行する。そのような具現化例を用いると、前記システムは前記ポイントの各検出された動きに基づいたフレームの遷移を表示する。
【００３０】
ユーザが複数のポイントを選択した具現化例にあって、ユーザは選択された各ポイントを動かす代わりに、残っているポイントを適当なところにホールディングしている間、一つ以上のポイントを動かすことを選択する。そのような具体例は、フレーム内の特徴の相対的な動きを捜すときに有効である。そのような具現化例にあって、ユーザはポイントのうちの一つの対象の位置は対象の現在の位置であることを示す。例えば、ユーザはそのポイントでコンテキスト−センシティブメニューを開くことができ、さらに適切な場所にポイントを保持するというオプションを選択することができる。そのような場合、受け取られる動きは、ポイントが動かされないというインディケーションである。
【００３１】
ブロック２０５にあって、前記システム１００は、前記パーティクルと第２フレーム内のポイント３０２の第２位置との間の間隔上の少なくともある一部分に基づいたパーティクルを備える映像１２１の第２フレームを決定する。ポイント３０２の第２位置３０４への移動を受け取った後、前記システム１００はポイント３０２に関連するパーティクルを有する全てのフレームのパーティクル情報をフレーム候補セットの決定のために検索する。各候補フレームのため、前記システム１００はパーティクルと第２位置３０４との間の距離である間隔を計算する。その後、前記システムは、ポイント３０２の第２位置３０４に最も近い位置で前記パーティクルを有する候補フレームのどちらかを決定する。
【００３２】
前述したように、システム１００が、選択されたポイントに最も近いパーティクルを決定したときにシステム１００によってオフセットが計算される。オフセットが前記選択されたポイント及び最も近いパーティクルに基づいて決定された具現化例にあって、前記パーティクルと前記第２位置との間の距離間隔は前記オフセット値の補正量を含んでいる。例えば、前記パーティクルが元の位置で前記ポイントの１０単位上方にあったとすると、第２位置は選択されたポイントとパーティクル間の初期の間隔を補正するために加算された１０単位オフセットを有する。
【００３３】
「最も近い」は前記パーティクルと第２位置と間の間隔が０であることを必ずしも意味しないことに留意すべきである。「最も近い」は前記パーティクルと第２フレームの第２位置との間の距離間隔がパーティクルと、パーティクルが存在するいかなるフレームの第２位置との間の距離間隔よりも短いことを意味する。さらに、パーティクルが第２位置に最も近い一つ以上のフレームがあるかもしれない。例えば、映像がブランコのスィングの場面を含むとき、パーティクルが第２位置に最も近いという映像内には複数のフレームが存在する。そのような場合、本発明の一具現化例は、パーティクルが第２位置に最も近いフレームの一つを任意に選択する。本発明の他の具現化例にあって、前記システムはパーティクルが第２位置に最も近い二つ以上のフレームを選択する。前記具現化例はさらにユーザに複数のフレームの一つを選択させるかもしれない。
【００３４】
一つの具現化例にあって、ユーザはパーティクルが位置される新しい位置からの最大距離間隔を具体的に指定するかもしれない。前記最大距離間隔は、パーティクルが最大距離間隔よりも第２位置からもっと遠いフレームを無視するためにシステムによって用いられる。そのような具体例にあって、システムは最大距離間隔内であって第２位置に最も近いパーティクルを含む映像内にフレームが無いと決定することが可能である。
【００３５】
前述したように、本発明の一実施の形態に係るシステムは、ユーザにフレーム内で複数のポイントを選択させ、かつ移動させる。そのような場合、システムは初めに選択されたポイントに関連されるパーティクルの全てを含む映像のフレームを判断する。システムは、その後、複数のポイントに関連されるパーティクルの位置と、選択されたポイントのために指定された新しい位置との間の最小自乗距離を計算することによって映像の第２フレームを決定する。システムは、その後、前記パーティクルと前記選択されたポイントとの間の最も低い最小自乗距離を有するフレームを選択することによって前記第２フレームを決定する。
【００３６】
前記パーティクルと前記選択された位置との間の距離間隔に加えて、他の要素が映像の最適な第２フレームの選択を適切に判断するために用いられる。例えば、本発明の一具現化例にあっては、第１フレームに関連して第２フレームが生じるときに基づいて、前記判断に重み付け要素が組み込まれる。例えば、映像の第１フレームの後に生じるところのフレームであることが第２フレームには望ましい。そのような場合、ユーザは第１フレームの後に生じるフレームを探すためのみに具体例を設定する。或いは、ユーザは、第１フレームに近いフレーム番号を有するフレームを指定する。そのような具体例にあって、システムは第１フレームの後の５００フレームに生じるフレームよりむしろ第１フレームの前の１０フレームに生じる第２フレームを選択する。引き続き他の重み付け要素が組み込まれる。
【００３７】
例えば、上述にて説明したいくつかの具体例は、前記第２フレームを判断するために、前記パーティクルと前記選択されたポイントの第２位置との間の物理的間隔にもっぱら依存していた。しかしながら、例えばフレーム番号或いは時間系列のような他の変数に基づいて判断されるところの具体例にあって、物理的間隔にはなおその上、重み係数も与えられる。例えば、本発明の一具現化例は、各変数の値にそれらの重み係数を掛けて、さらにその値を各候補フレームのスコアを判断するために合計する。最も高いスコアを有する候補が選択されることになる。そのような場合、前記選択されたポイントの新しい位置に最も近いわけではないベストフレームが選択されるかもしれない。なおいっそうの具体例が、当業者によって推論されるのは明白である。
【００３８】
ブロック２０６にあって、システム１００が第２フレーム４００を決定した後、システム１００は映像の第２フレーム４００のインディケーション（indication）を出力する。図６は前記パーティクルが前記ポイント３０２の第２位置３０４に最も近いところの、システム１００によって出力される映像の第２フレームを示す。図６に示される具現化例にあって、システム１００はユーザが眺める映像の第２フレーム４００を表示する。一具現化例にあって、システムは前記第２フレーム４００のフレーム番号を出力することにより前記映像の第２フレームのインディケーションを出力する。他の具現化例にあって、システムは第２位置に最も近いパーティクルを有するいくつかのフレームに対応する複数のフレーム番号を出力することもできる。一具現化例にあって、システムは第２フレーム４００のサムネイルを出力することもできる。
【００３９】
一旦、システム１００が映像の第２フレーム４００のインディケーションを出力すると、システム１００は前記方法２００内の他のブロックに戻る。例えば、システム１００は前記ポイントの新しい位置への第２の動きを受けるためにブロック２０４に戻り、さらに前記アルゴリズムの残りのステップを続けるかもしれない。さらに、システム１００は、第２位置の選択を受けるためにブロック２０２に戻るかもしれない。
【００４０】
本発明のさらなる具現化例は、パーティクル情報を組み込まずに、映像内の特徴を特定する他の情報を含むことができる。例えば、一具現化例にあって、システムはパーティクルよりも映像内の物体についての情報を含む。例えば、映像は前処理され、さらに仮想上の物体が特徴又は映像内の視覚要素に関連付けられる。例えば、物体は作りだされ、俳優に関連付けられる。物体はその後、映像のフレーム内に俳優が現れるたびに、使用される。例えば、俳優が映像内のシーンに早く現れるかもしれない。彼は、映像の中間のシーンには現れず、映像の終わりのシーンに再び現れるかもしれない。前記システムは、例え、映像の中間部分で、その俳優がいかなるフレームに現れなくとも、映像の早期のシーンと同様に終わりのシーンにあっても同一の物体を俳優に関連付ける。さらに、映像の追跡に関する部分のための他の方法が、本発明の具現化例の中で用いられるかもしれない。例えば、一つ以上の明確なテンプレートが映像内の特別の物体を追跡するために用いられるところの、テンプレートトラッキングが使用される。例えば、車を特定するという能力があるテンプレートトラッキングシステムは、映像内の車の位置を特定及び追跡するために用いられる。トラッキング情報は、本発明の一具現化例によって、パーティクル情報よりもむしろ、用いられる。
【００４１】
前述したような、パーティクル情報を用いる本発明の具現化例に戻ると、パーティクルはプリ−プロセッサによって決定され、さらに映像内の一つ以上のフレーム内でポイントを表す。
【００４２】
まず第一に、プリ−プロセッサは、画像勾配度によって変調される円滑期間を含むエネルギー変数及び閉塞する境界線を示すために使われる閉塞係数を用い、オプティカルフローフィールドの発散及び画素投影差に基づいて、連続した対のフレームのオプティカルフローフィールドを計算する。二方向性フィルタリングがその後、境界線の鮮明度を向上するために、閉塞境界の近くに適用される。次に、第１フレームで特定されたパーティクルは、前記オプティカルフローフィールド、画像強度、色チャンネル、及びパーティクルの近くについて重み付けられた円滑期間を考慮にいれる最適化処理を用いる連続するフレームに伝達される。各フレームのための、パーティクルが伝達されたのち、高最適化後誤差を伴うパーティクルが取り除かれ、既存のパーティクル間のギャップに新しいパーティクルが挿入される。例えば、一フレーム内のあるエリアからひとつのパーティクルが取り除かれると、一つ以上のパーティクルがパーティクル密度を高めるためにその領域に加えられる。この分析は、映像上の両方の前方時刻方向（第１フレームから最後のフレーム）内、同様に逆転（最後のフレームから第１フレーム）にもっと正確なパーティクル追跡情報を提供するために、行われる。
【００４３】
映像の前処理のためのアルゴリズムの具体的な例は、ピーター・サンド（Peter Sand）及びセス・テラー（Seth Teller）、ＭＩＴコンピュータ科学及び人口知能研究所、ＩＥＥＥコンフェランス・オン・コンピュータ・ビジョン・アンド・パターン・認識、２００６(“Sand”）,による「パーティクルビデオ：ポイント経路を用いた長距離動き予測」（”Particle Video: Long-Range Motion Estimation using Point Trajectories” by Peter Sand and Seth Teller, MIT Computer Science and Artificial Intelligence Laboratory, IEEE Conference on Computer Vision and Pattern Recognition, 2006(“Sand”)）全体をここに参照として組み入れることによって、説明される。
【００４４】
前記パーティクルビデオアプローチは、空間的密度及び時間的に長い区間の両方に有利である。これに対して、他の方法は長い区間であるが、空間的に貧弱である傾向であったり、空間的に密度があるが時間的に短い区間である傾向がある。このように、パーティクルビデオデータは、我々が近くのパーティクルを見つけることによって映像のフレームを通して任意に選択された画素の動きを予測できるので、選択されたフレームを探すために映像を通して探索することに適切である。
【００４５】
再度、図１を参照すると、本発明の具現化例は、デジタル電子回路、或いはコンピュータハードウェア、ファームウェア、ソフトウェア、又はそれらの組み合わせに適用することができる。一実施例にあって、コンピュータ１０１は、プロセッサ１１０又はいくつかのプロセッサを備える。前記プロセッサ１１０は、プロセッサに接続されたランダムアクセスメモリ（ＲＡＭ）のようなコンピュータ読み取り可能な媒体を備える。前記プロセッサ１１０は、画像を編集するための一つ以上のコンピュータプログラムを実行するように、メモリ１１１に格納されているコンピュータ実行可能なプログラムインストラクションを実行する。そのようなプロセッサは、マイクロプロセッサ、デジタルシグナルプロセッサ（ＤＳＰ）、特定用途向けＩＣ（application-specific integrated circuit：ＡＳＩＣ）、プログラマブル（理論）ゲート配列（field programmable gate arrays：ＦＰＧＡｓ）、及びステートマシン（state machines）を備える。そのようなプロセッサは、ＰＬＣｓ、プログラマブル双方向コントローラ（programmable interrupt controllers：ＰＩＣｓ）、プログラバブルロジックデバイス（programmable logic devices：ＰＬＤｓ）、プログラマブルリードオンリイメモリ（programmable read-only memories：ＰＲＯＭｓ）、電子的プログラマブルリードオンリイメモリ（electronically programmable read-only memories：ＥＰＲＯＭｓ or ＥＥＰＲＯＭｓ）のようなプログラマブル電子デバイス、又は他の同様のデバイスを備える。
【００４６】
そのようなプロセッサは、例えばコンピュータ読み取り可能な媒体のような記録媒体を備えるか、或いはそのような記録媒体と信号のやりとりを行う。その記録媒体は、命令を記録し、プロセッサによりその命令が実行されるとき、その命令は、一つのプロセッサにより実行され、或いは支援されるものとして、前記プロセッサに本明細書で説明された各ステップを行わせることができる。コンピュータ読み取り可能な具体例は、限定されるものではないが、電子的、光学的、磁気的、或いは他の記録媒体、又はコンピュータ読み取り可能な命令を伴って、ウェブサーバのプロセッサのようなプロセッサによって能力が発揮される情報転送デバイスを備える。記録媒体の他の具体例は、限定されるものではないが、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、磁気ディスク、メモリーチップ、ＲＯＭ、ＲＡＭ、ＡＳＩＣ、コンフィギャードプロセッサ、全ての光学的記録媒体、全ての磁気テープ又は他の磁気媒体、又はコンピュータプロセッサがそこから読み取りできるいかなる他の記録媒体を含む。さらに、例えばルーター、私有の又は公共のネットワーク、又は他の伝送デバイス或いはチャンネルのような、種々の他の形式のコンピュータ読み取り可能な記録媒体も、コンピュータに命令を通信又は伝送する。説明された前記プロセッサ、及びプロセッシングは、一つ以上の構成であり、一つ以上の構成で分散されてもよい。プロセッサは、この明細書にて説明された一つ以上の方法（又は方法の一部）を実行するためのコードを含む。
【００４７】
（全般的に）
好ましい具現化例を含む、本発明の具現化例の前記説明は、説明図と説明の目的のために示されたものであり、網羅的なこと又は発明を開示された寸分たがわぬものとして制限することを意図したものではない。本発明の趣旨及び範囲をはずれることなく当業者による、多くの変形例及び適用がありえるのは明白である。
【図面の簡単な説明】
【００４８】
本発明のこれらの及び他の特徴、局面、及び長所は、次の詳細な説明を添付された以下の図面を参照しながら読むことでより理解される。
【００４９】
【図１】本発明の一実施例に係る双方向映像フレーム検索システムを示す図である。
【図２】本発明の一実施例に係る双方向映像フレーム検索方法を示す図である。
【図３】映像の第１及び第２フレームの様子を示す図である。
【図４】映像の第１及び第２フレームの様子を示す図である。
【図５】映像の第１及び第２フレームの様子を示す図である。
【図６】映像の第１及び第２フレームの様子を示す図である。
【符号の説明】
【００５０】
１００    システム
１０１    コンピュータ
１０２    ディスプレイ
１０３    入力デバイス
１１０    プロセッサ
１１１    メモリ
１２０    アプリケーション
１２１    映像
１２２  パーティクル情報
１３０  プリ−プロセッサ
２０１  映像フレームを表示するステップ
２０２  ポイントの選択を受けとるステップ
２０３  前記ポイントに関連するパーティクルを決定するステップ
２０４  前記ポイントの動きを受けとるステップ
２０５  第２の映像フレームを決定するステップ
２０６  第２の映像フレームを出力するステップ
【図１】
0005520459.tif 000002
【図２】
0005520459.tif 000003
【図３】
0005520459.tif 000004
【図４】
0005520459.tif 000005
【図５】
0005520459.tif 000006
【図６】
0005520459.tif 000007