(57)【要約】  再生時に視聴する側から違和感を低減しつつ、複数のコンテンツ（例えば、ビデオ）から各コンテンツのストーリー性をできる限り維持してコンテンツを結合することができる画像処理装置を提供する。画像処理装置は、複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは別のコンテンツに含まれ、時間的に連続する複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出し、前記第１処理手段で検出された類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する。
2012137493.tif 000002
【特許請求の範囲】
【請求項１】
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理手段と、
前記第１処理手段で検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記第１処理手段は、
前記複数のコンテンツそれぞれについて、所定の特徴変換法により、当該コンテンツと、前記複数のコンテンツに含まれる他のコンテンツとのフレーム類似度を算出し、当該フレーム類似度に基づいて、概要レベルで当該コンテンツと類似する前記検出対象コンテンツを特定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記所定の特徴変換法は、Ｐａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇ手法であり、
前記第１処理手段は、
前記複数のコンテンツそれぞれについて、当該コンテンツに含まれる全てのフレームに対してＰａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇアルゴリズムを施し、前記全てのフレームそれぞれのハッシュ値を算出し、
当該コンテンツについて算出された各ハッシュ値と、前記複数のコンテンツに含まれる残りのコンテンツそれぞれについて算出された各ハッシュ値との一致数により、前記残りのコンテンツから当該コンテンツと類似する前記検出対象コンテンツを特定する
ことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記第２部分コンテンツは、当該コンテンツの終了部位に含まれており、
前記検出対象コンテンツにおける前記複数の部分コンテンツは、当該検出対象コンテンツの開始部位を構成している
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記第２部分コンテンツの再生時間と、前記複数の部分コンテンツそれぞれの再生時間とは、同一時間長であり、
前記第１処理手段は、
前記第２部分コンテンツに含まれる所定枚数のフレームそれぞれについて、前記複数の部分コンテンツそれぞれに含まれる各フレームとのフレーム類似度を算出し、前記フレーム類似度を用いて、前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記第２部分コンテンツにおける前記所定枚数のフレームは、前記第２部分コンテンツの開始位置から等間隔に存在する
ことを特徴とする請求項５に記載の画像処理装置。
【請求項７】
前記第２処理手段が生成する前記情報は、前記複数のコンテンツそれぞれについて、当該コンテンツと、当該コンテンツの連結先であるコンテンツとの関係を示すグラフである
ことを特徴とする請求項１に記載の画像処理装置。
【請求項８】
前記第２処理手段は、
前記複数のコンテンツそれぞれについて当該コンテンツと、当該コンテンツの第２部分コンテンツと類似する前記第３部分コンテンツを含むコンテンツとに対してエッジで関連付けがされ、当該エッジに対して前記第２部分コンテンツと前記第３部分コンテンツとの類似度に応じた重みが付加された有向重み付グラフを生成し、
前記エッジそれぞれに付された前記重みに基づいて、前記有向重み付グラフから前記複数のコンテンツに含まれる第１コンテンツから第２コンテンツまでの経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツの組それぞれに対して、当該組におけるエッジの派生元のコンテンツに含まれる前記第１部分コンテンツ及び前記第２部分コンテンツと、エッジの派生先であるコンテンツに含まれる前記第３部分コンテンツとを連結する
ことを特徴とする請求項７に記載の画像処理装置。
【請求項９】
前記第２処理手段は、さらに、
前記経路を検出すると、検出した前記経路に存在する各エッジに対する重みに対して他の経路検出時において当該経路に存在する各コンテンツが検出対象外となるよう当該重みの値を補正し、
前記経路検出及び前記補正を、検出された経路に対するエッジの重みの合計値が所定値以下となるまで繰り返す
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１０】
前記第２処理手段は、
ユーザーから指定された一のコンテンツが、開始位置、終了位置及び経路途中に存在するよう前記経路を検出する
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１１】
前記第２処理手段は、
ユーザーから２つ以上のコンテンツからなるコンテンツグループが指定された場合、前記コンテンツグループを含む前記２つ以上のコンテンツ全てを通過する前記経路を検出する
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１２】
前記第２処理手段は、
ユーザーからオブジェクトが指定された場合、指定された前記オブジェクトを含む２つのコンテンツを特定し、特定した一のコンテンツを前記第１コンテンツとし、特定した他のコンテンツを前記第２コンテンツとして前記経路を特定する
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１３】
前記第２処理手段は、
前記第１部分コンテンツ、前記第２部分コンテンツ、前記第３部分コンテンツ、及び前記検出対象コンテンツに含まれ、且つ前記第３部分コンテンツに時間的に後続する第４部分コンテンツの順に連結して１つの連結コンテンツを生成する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１４】
前記第１処理手段は、さらに、
前記コンテンツの前記第２部分コンテンツと前記第３部分コンテンツとから、一致するオブジェクトが存在するフレームを検出し、
前記第２処理手段は、
前記オブジェクトが存在する前記第２部分コンテンツの第１フレームと前記第３部分コンテンツの第２フレームとにおいて、当該オブジェクトが存在する一致領域を検出し、
前記第１フレーム及び前記第１フレームの前方に所定枚数分連続して存在するフレームからなる第１フレーム群について前記一致領域に含まれる前記オブジェクトに対してズームイン手法による画像処理を施し、前記第２フレーム及び前記第２フレームの後方に所定枚数分連続して存在するフレームからなる第２フレーム群について前記一致領域に含まれる前記オブジェクトに対してズームアウト手法による画像処理を施し、
前記第１フレームと前記第２フレームとの間で、モーフィング処理を施して１つ以上の中間フレームを生成し、
前記第１フレーム群、前記第２フレーム群及び前記１つ以上の中間フレームについて、前記オブジェクトを含む領域を除く残りの領域に対してフェザリング処理を施し、
各処理が施された後に前記第１フレームと前記第２フレームとの間に、フェザリング処理が施された前記１つ以上の中間フレームを配置して連結することで前記連結コンテンツを生成する
ことを特徴とする請求項１３に記載の画像処理装置。
【請求項１５】
前記第１処理手段は、
前記第２部分コンテンツ及び前記第３部分コンテンツに対して、共通パターン検出処理、顔検出処理、人体検出処理及びこれらの組み合わせの処理の何れかを施して、前記一致するオブジェクトを検出する
ことを特徴とする請求項１４に記載の画像処理装置。
【請求項１６】
画像処理装置で用いられる画像処理方法であって、
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理ステップと、
前記第１処理ステップで検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理ステップと
を含むことを特徴とする画像処理方法。
【請求項１７】
画像処理装置で用いられる画像処理プログラムであって、
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理ステップと、
前記第１処理ステップで検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理ステップと
を含むことを特徴とする画像処理プログラム。
【請求項１８】
画像処理装置で用いられる集積回路であって、
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理手段と、
前記第１処理手段で検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理手段と
を含むことを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチメディア処理及び画像処理に関し、特に複数のコンテンツから類似する部分を有するコンテンツを抽出し、連結する技術に関する。
【背景技術】
【０００２】
個人用デジタル機器（例えば、デジタルカメラ、デジタルビデオカメラ等）の人気が高まるにつれ、撮影された家庭用のデジタルビデオの数は爆発的に増加している。これは、（１）撮影されたビデオ（ビデオクリップ）を記憶する記憶装置の記憶容量が大きくなったこと、（２）撮影されたビデオは、シングル・ショットの映像のみを含み、その撮影時間（再生時間）は非常に短いこと、（３）多種多様なテーマやイベントについて撮影がなされること、等に起因している。そのため、ユーザーは、異なる場所や時間に撮影した自分のビデオのコレクションを、頻繁に保守・管理する必要があるが、その数が膨大になると管理したり操作したりするのが難しい。例えば、ユーザーが自分で撮影した、大量に存在するビデオから所望のビデオを閲覧することは、容易ではない。【０００３】
従来、このような大量のビデオを効率的に閲覧できるようにするために、ビデオを要約する技術がある。ビデオの要約技術では、要約に用いるべき特徴がビデオのストーリーと関係ないものの場合には元のビデオの詳細が失われたり、要約に用いるべき特徴がビデオのほとんどの画像に含まれている場合には要約できなかったりする。このような場合、要約自体が不正確なものとなってしまう可能性がある。【０００４】
また、上記の技術とは別の技術として、ビデオを合成（連結）する技術がある（非特許文献１〜３参照）。例えば、非特許文献１は、ビデオセグメントに関連付けられた、ドメイン固有メタデータが存在する場合には、自動的に一貫性のあるビデオとなるよう合成する技術が開示されている。また、非特許文献２で開示されたシステムは、ホームビデオセグメントを選択し、それを音楽に沿って並べることにより、編集ビデオセグメントを作成するものである。【０００５】
ここで、ショットとは、ビデオのもっとも基本的な物理的エンティティであり、一台のカメラで記録した、中断を含まないビデオクリップのことを示す。上述したシングル・ショット（ショート・ショットともいう。）とは、継続時間が比較的短い、中断を含まないビデオクリップを意味する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Automatic composition techniques for video production. Knowledge and Data Engineering,1998,G. Ahanger
【非特許文献２】Optimization-Based Automated Home Video Editing System. IEEE Transactions on Circuits and Systems for Video Technology, 2004, X. S. Hua, L. Lu, and H. J. Zhang
【非特許文献３】Systematic evaluation of logical story unit segmentation. IEEE Transactions on Multimedia, 2002,J. Vendrig and M. Worring
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記各非特許文献で示される技術では、一のビデオと他のビデオとを結合して再生すると、一のビデオから他のビデオへと再生対象が切り替わる際に、場面が急に変化する可能性が高い。このような場合、視聴している側からすると、一のビデオと他のビデオとの繋がりに違和感を覚えることがある。【０００８】
そこで、本発明は、上記問題に鑑みて、再生時に視聴する側から違和感を低減しつつ、複数のコンテンツ（例えば、ビデオ）から各コンテンツのストーリー性をできる限り維持してコンテンツを結合することができる画像処理装置、画像処理方法、画像処理プログラム及び集積回路を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明は、画像処理装置であって、動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理手段と、前記第１処理手段で検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理手段とを備えることを特徴とする。
【発明の効果】
【００１０】
この構成によると、画像処理装置は、生成した情報を用いることで、第２部分コンテンツと、複数の部分コンテンツのうち類似度が最も高い第３部分コンテンツとの結合を可能としている。そのため、結合されたコンテンツを再生すると類似する部分で繋がっているので視聴する側は違和感なく視聴することができる。また、結合の際には、第１部分コンテンツをも含んでいるので、第１部分コンテンツを含むコンテンツのストーリー性は維持されている。
【図面の簡単な説明】
【００１１】
【図１】画像処理装置１の構成を示すブロック図である。
【図２】選好係数を用いてフレームシーケンス対応性の計算方法を説明する図である。
【図３】人物検出処理に用いるモデル及び検出結果の一例を示す図である。
【図４】顔検出処理におけるマッチングの例を示す図である。
【図５】生成されたビデオ類似グラフＧ１００及び経路探索結果の一例を示す図である。
【図６】自動経路探索による検出結果をユーザーに提示するインターフェースの一例を示す図である。
【図７】ユーザーによりビデオクリップが固定された場合の探索による検出結果をユーザーに提示するインターフェースの一例を示す図である。
【図８】ユーザーによりオブジェクトが固定された場合の探索による検出結果をユーザーに提示するインターフェースの一例を示す図である。
【図９】ビデオＶiとビデオＶjとを連結する際の手順を説明する図である。
【図１０】本実施の形態によるトランジションと、他の手法によるトランジションとを比較した一例を示す図である。
【図１１】画像処理装置１の処理概要を示す流れ図である。
【図１２】類似するビデオのペアを検出する処理を示す流れ図である。
【図１３】連結ビデオ生成処理を示す流れ図である。
【図１４】具体例を用いて画像処理装置１の処理を説明する図である。
【図１５】画像処理装置１の処理例を説明する図である。
【発明を実施するための形態】
【００１２】
１．実施の形態
以下本発明の実施形態について、図面を参照しながら説明する。
【００１３】
１．１  概要
本発明に係る画像処理装置は、類似する複数のビデオ（動画像からなるコンテンツ）から、仮想的なワンショット・プレゼンテーション（１つのコンテンツ）を自動的に生成するものである。なお、以下において、ワンショット・プレゼンテーションをワンショット・ビデオ、連結ビデオともいう。ここで、仮想的なワンショット・プレゼンテーションを構成する各コンテンツの再生順序（再生経路）を「ビデオパズル」という。本発明の画像処理装置は、複数のビデオから、類似する主要なトピックを有するビデオの集合を抽出する。トピックとしては、人物、物、あるいはシーンがその対象となり得る。トピックは、ユーザーによって指定されるか、あるいは自動発見法によって見つけられる。そして、以下に説明する粗細法（ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ  ｍｅｔｈｏｄ）を用いてビデオ間の開始・終端フレームの対応をとり、それらをシームレスに合成（連結）して、長時間からなるワンショット・プレゼンテーションを生成する。したがって、本発明は、複数のビデオにおけるストーリーについて、ユーザーがより深い印象を得ることができるような、ビデオ・コンテンツの新たなプレゼンテーション法を提供するものである。
【００１４】
１．２  構成
本発明に係る画像処理装置１の構成について、図１を参照しながら説明する。
【００１５】
画像処理装置１は、図１に示すように、ビデオ記憶部１０、検出処理部１１、グラフ生成部１２及び連結ビデオ生成部１３から構成されている。
【００１６】
なお、画像処理装置１は、プロセッサ及びメモリを含んで構成されており、検出処理部１１、グラフ生成部１２及び連結ビデオ生成部１３それぞれの機能は、メモリに記憶されているプログラムをプロセッサが実行することにより実現される。
【００１７】
検出処理部１１は、複数のビデオ（コンテンツ）それぞれについて、当該ビデオの一部分であって、時間的に連続する２つの部分（第１部分コンテンツ及び第２部分コンテンツ）のうち第２部分コンテンツとの類似度が高い部分（第３部分コンテンツ）を、他のビデオの一部を構成し、時間的に連続する複数の部分（部分コンテンツ）から検出する。
【００１８】
また、グラフ生成部１２は、前記複数のビデオについて、当該ビデオと連結するビデオとの関係をグラフ化する。連結ビデオ生成部１３は、第１部分コンテンツ、第２部分コンテンツ、第３部分コンテンツ、及び前記他のビデオに含まれ、且つ前記第３部分コンテンツに時間的に後続する部分（第４部分コンテンツ）の順に連結する。
【００１９】
以降、各構成要素について、詳細に説明する。
【００２０】
（１）ビデオ記憶部１０
ビデオ記憶部１０は、複数のビデオ（動画像に係るコンテンツ）を記憶するためのメモリ領域である。なお、ビデオ記憶部１０に記憶されているビデオそれぞれを、ビデオクリップともいう。
【００２１】
（２）検出処理部１１
検出処理部１１は、ビデオ記憶部１０に記憶されている複数のビデオについてマッチング・グラフを生成するために、ビデオ記憶部１０に記憶されている各ビデオを入力とし、類似する主要なトピックを有するビデオの集合を生成し、出力するものである。
【００２２】
検出処理部１１は、図１に示すように、第１検出部１００、第２検出部１０１及びマッチング処理部１０２から構成されている。
【００２３】
（２−１）第１検出部１００
第１検出部１００は、所定の特徴変換法に基づいて算出される類似度を用いて、ビデオ記憶部１０に記憶されている全てのビデオのペアにおいてフレームの部分的類似性を算出する。第１検出部１００は、所定の特徴変換法として、例えば、Ｐａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇ（ＰｍＨ）アルゴリズムを用いる。そして、第１検出部１００は、算出したフレームの部分的類似性を用いて、ビデオのペアから概要レベルで類似性の高いビデオのペアを、候補ペアとして選択し、選択結果に基づいてビデオ類似性のグループを生成する。具体的には、第１検出部１００は、類似度が所定の閾値以下となる類似性の低いビデオのペアを除外し、最大４つのビデオのペアを、各ビデオのマッチング候補として選択する。これにより、例えば画像特徴量のような指標を用いて厳密に一致するフレームを検出するのではなく、概要レベルで一致するフレームを検出することが可能となるので、ビデオマッチング工程を行うとしたときの計算コストが、大幅に削減される。
【００２４】
通常、一般的なｍｉｎ−ｈａｓｈは、ほとんど重複したテキストドキュメントやウェブページを発見するのに利用される手法である。近年、ｍｉｎ−ｈａｓｈ及びその変種は、ほとんど重複した画像の検出、画像クラスタリング、画像の取得、及びオブジェクトの検出に適用されている。ここで、オブジェクトとは、人物や物を含む概念である。ｍｉｎ−ｈａｓｈアルゴリズムにおいては、ハッシュ関数が画像におけるすべてのＶｉｓｕａｌ  Ｗｏｒｄに対し適用され、それらの位置は無視される。そして、最小ハッシュ値を有するＶｉｓｕａｌ  Ｗｏｒｄが、その画像のグローバル記述子として選択される。しかし、通常、語の集合（ｂａｇ−ｏｆ−ｗｏｒｄｓ）によって表現されるテキストドキュメントとは異なり、画像は、２Ｄで構成されたオブジェクトによって大きく特徴づけられ、これらは画像内において、空間的に局在することが多い。そして、ＰｍＨは、この局在性を利用したハッシュ手法である。ＰｍＨを利用した第１検出部１００の基本的な処理は、以下のとおりである。なお、Ｖｉｓｕａｌ  Ｗｏｒｄについては、既知の技術であるため、ここでの説明は省略する。
【００２５】
ａ）ビデオを構成する各フレームを取得する。
【００２６】
ｂ）取得した各フレームそれぞれについて、当該フレームを同一サイズのｐ個の矩形領域に分割する。
【００２７】
ｃ）各部分領域ごとに、同一のハッシュ関数を施してｍｉｎ−ｈａｓｈ ｓｋｅｔｃｈを抽出し、ハッシュテーブルに格納する。ここで、ハッシュテーブルは、ハッシュ関数が取り得る変域を所定の範囲毎に分割したテーブルである。そして、ｍｉｎ−ｈａｓｈ ｓｋｅｔｃｈは、当該ｍｉｎ−ｈａｓｈ ｓｋｅｔｃｈが示す値が属する範囲に格納される。
【００２８】
ｄ）ビデオの各ペアについて、ハッシュテーブルからｍｉｎ−ｈａｓｈ ｓｋｅｔｃｈが衝突する個数に基づいたビデオ間の類似度を算出する。具体的には、以下の数式１により、算出される。
【００２９】
ｅ）ビデオの各ペアのうち、算出された値が大きい（ビデオ間の類似度が高い）、上位４つを候補ペアとして選択する。
【００３０】
【数１】
2012137493.tif 000003
【００３１】
ここで、Ｖi、mは、ビデオＶiのｍ番目のフレームを、Ｖj、nは、ビデオＶjのｎ番目のフレームを示す。δ（Ｖi、m、Ｖj、n）は、ビデオＶiのｍ番目のフレームにおける部分領域の一つのｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈがビデオＶjのｎ番目のフレームにおける複数の部分領域それぞれのｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈの何れかと衝突する場合には“１”と定義され、衝突しない場合には“０”と定義される。また、｜Ｖi｜及び｜Ｖj｜それぞれは、ビデオＶi及びＶjそれぞれのフレーム数を示す。
【００３２】
（２−２）第２検出部１０１
第２検出部１０１は、第１検出部１００で選択された候補ペアを入力とし、入力された候補ペアのビデオそれぞれに含まれるサブシーケンス（以下、フレームシーケンスともいう。）の類似性を検出するものである。
【００３３】
以下、第２検出部１０１の機能の詳細について説明する。
【００３４】
第２検出部１０１は、第１検出部１００で選択された候補ペア（例えば、ビデオＶiとＶj）の各ビデオについて、ビデオＶiの終了部分からなるビデオ終了部分を、ビデオＶjの開始部分からなるビデオ開始部分を抽出し、シーケンス対応性Ｓi、jを検出する。ここで、例えば、ビデオ終了部分とはビデオの再生時間を２分割した場合の後半部分であり、ビデオ開始部分とはビデオの再生時間を２分割した場合の前半部分である。
【００３５】
第２検出部１０１は、シーケンス対応性Ｓi、jを算出するために、先ず、ビデオＶiのビデオ終了部分、ビデオＶjのビデオ開始部分において同一の長さ（再生時間）からなるサブシーケンス（フレームシーケンス）に分割する。ここでは、ビデオＶiのビデオ終了部分はＳｅｑi、1、Ｓｅｑi、2、・・・、Ｓｅｑi、pに、ビデオＶjのビデオ開始部分はＳｅｑj、1、Ｓｅｑj、2、・・・、Ｓｅｑj、qにそれぞれ分割される。ここで、Ｓｅｑi、1、Ｓｅｑi、2、・・・、Ｓｅｑi、p及びＳｅｑj、1、Ｓｅｑj、2、・・・、Ｓｅｑj、qの長さ（再生時間）は同一である。また、Ｓｅｑi、1、Ｓｅｑi、2、・・・、Ｓｅｑi、pは、ビデオＶiの終了部分に位置するものと、Ｓｅｑj、1、Ｓｅｑj、2、・・・、Ｓｅｑj、qは、ビデオＶjの開始部分に位置するものである。
【００３６】
第２検出部１０１は、予め定められた定率に基づいて、ビデオ終了部分Ｓｅｑi、sについて（ｓは１以上ｐ以下の整数）、ビデオ開始部分Ｓｅｑj、1、Ｓｅｑj、2、・・・、Ｓｅｑj、qそれぞれとの類似性を検出する。例えば、第２検出部１０１は、予め定められた定率に基づいて、フレームシーケンスＳｅｑi、sについて、フレームシーケンスＳｅｑj、tとのフレームの類似性を検出する（ｔは１以上ｑ以下の整数）。
【００３７】
ここで、定率とは、ビデオのフレームレートに基づいて類似性を検出する（サンプリングする）ためのサンプリングレートを示すものである。例えば、ビデオのフレームレートが３０Ｆｌａｍｅｓ／ｓｅｃであるとき、定率を３０とすると、第２検出部１０１は、１秒に１枚分のフレームについて類似性を検出する。また、上記と同一のフレームレートである場合において、定率が１５であるときには１秒に２枚分のフレームを、定率が６であるときには１秒に５枚分のフレームについて類似性を検出する。例えば、再生時間を５秒、フレームレートを３０Ｆｌａｍｅｓ／ｓｅｃ、及び定率３０とした場合、フレームシーケンスＳｅｑi、sとフレームシーケンスＳｅｑj、tのそれぞれには、１５０（３０Ｆｌａｍｅｓ／ｓｅｃ  ×  ５秒）枚のフレームが含まれる。第２検出部１０１は、フレームシーケンスＳｅｑi、sにおいて、先頭フレームと、当該先頭フレーム後において１秒ごとに存在する各フレームとを検出対象フレームとして、これら検出対象フレームそれぞれについて、フレームシーケンスＳｅｑj、tに含まれる各フレームとの類似性を検出する。なお、定率を１とした場合、フレームシーケンスＳｅｑi、sに含まれる全てのフレームが類似性の検出対象となる。
【００３８】
第２検出部１０１は、定率に応じて検出対象となった各フレームとフレームシーケンスＳｅｑj、tに含まれるフレームとからシーケンス類似性ＶＳi、jを、以下に示す数式２を用いて算出する。
【００３９】
【数２】
2012137493.tif 000004
【００４０】
ここで、ｓｃｏｒｅx、yは、後述するフレーム類似値である。また、ｘはＳｅｑi、sに属するフレームのフレーム番号を示し、ｙは、Ｓｅｑj、tに属するフレームのフレーム番号を示す。また、｜ｋ｜は、Ｓｅｑi、sにおいて、検出対象となったフレームの個数を示す。従って、数式２で得られるフレームの類似性とは、Ｓｅｑi、sのうち検出対象となるフレーム毎に得られるｓｃｏｒｅx、yの最大値の平均値であることが分かる。
【００４１】
第２検出部１０１は、フレーム間の類似度を算出するために、画像局所キ−ポイント・マッチングを行う。マッチング処理としては、Ｄｉｆｆｅｒｅｎｃｅ  ｏｆ  Ｇａｕｓｓｉａｎｓ  （ＤＯＧ）  ｋｅｙｐｏｉｎｔ  ｄｅｔｅｃｔｏｒを有するＳＩＦＴ＋Ｃｏｌｏｒ  Ｍｏｍｅｎｔｓが用いられる。ＳＩＦＴ記述子とＣｏｌｏｒ  Ｍｏｍｅｎｔｓは、互いに補完関係にあり、ＳＩＦＴ記述子が局所構造を記述し、Ｃｏｌｏｒ  Ｍｏｍｅｎｔｓが局所差分の構造を記述することで、より高次の情報を示している。第２検出部１０１は、これらの手法を用いて、画像の特徴点である局所キーポイントを取得する。
【００４２】
第２検出部１０１は、異なるビデオクリップから得た所定の２つのフレームの局所一致を判定するために、ソース画像（例えばＶiのフレーム）の局所キーポイントごとの最適なマッチング候補を、ターゲット画像（例えばＶjのフレーム）の局所キーポイント中で最も近接するものを特定することによって検出する。
【００４３】
ここで、最も近接する局所キーポイントとは、ユークリッド距離が最小の局所キーポイントである。ソース画像には、背景に雑然と存在するものやターゲット画像からは検出できないものの局所キーポイントなど、ターゲット画像中に一致するものがない局所キーポイントが多く存在するため、それらは廃棄するのが有効である。第２検出部１０１は、最も近い局所キーポイントと、二番目に近い局所キーポイントとを比較することによって、有効測定値を取得する。そして、第２検出部１０１は、一致する局所キーポイントの数を示すキーポイント・マッチング・セットＫＳと、一致する局所キーポイントにおける一致の度合を示すマッチング・スコアＴを取得する。
【００４４】
第２検出部１０１は、局所マッチングにより得られたキーポイント・マッチング・セットＫＳと、マッチング・スコアＴとを用いて、フレーム間の類似値を以下に示す数式３により算出する。
【００４５】
【数３】
2012137493.tif 000005
【００４６】
ここで、｜ＫＳ｜は、キーポイント・マッチング・セットのサイズ、つまりキーポイント・マッチング・セットに含まれる要素の個数を示す。また、ｊは、１以上｜ＫＳ｜以下の整数である。ここで、キーポイント・マッチング・セットに属する各要素（キーポイント・マッチング）には、１以上｜ＫＳ｜以下の整数のうち互いに異なる整数が割り当てられている。そして、Ｔjは整数ｊが割り当てられたキーポイント・マッチングのマッチング・スコアを示す。
【００４７】
そして、第２検出部１０１は、数式３で算出した類似値と上記数式２とを用いて、フレーム類似性を算出することとなる。
【００４８】
第２検出部１０１は、フレームシーケンスのペアそれぞれについて、数式２で算出したフレーム類似性に対し選好係数でスケーリングして、フレームシーケンスのペアのシーケンス類似性を取得する。第２検出部１０１は、例えば、取得したシーケンス類似性に選好係数を乗算して、フレームシーケンスのペアのシーケンス類似性を取得する。ここで、選好係数とは、フレームシーケンス間で算出されたフレーム類似性に対する重みであり、その重みは各フレームシーケンスが存在する位置に応じて設定される。例えば、図２に示すように、ビデオＶjの再生開始位置を含むＳｅｑj、1について、ビデオＶiの再生終了位置Ｓｅｑi、pとの選好係数として値“１”が設定され、ビデオＶiの再生終了位置から順次離れていくＳｅｑi、p-1、Ｓｅｑi、p-2、・・・、Ｓｅｑi、2、Ｓｅｑi、1に対して設定される選好係数の値は、０に近づいていく。
【００４９】
なお、シーケンス類似性の算出は、先ず、ビデオＶiのＳｅｑi,pを固定し、ビデオＶjのＳｅｑj,1、・・・、Ｓｅｑj,qそれぞれとのシーケンス類似性を算出する。その後、ビデオＶiのＳｅｑi,p-1、・・・、Ｓｅｑi,1の順に、ビデオＶjのＳｅｑj,1、・・・、Ｓｅｑj,qそれぞれとのシーケンス類似性を算出する。
【００５０】
第２検出部１０１は、候補ペアごとに、シーケンス類似性（選好係数によりスケーリングされた値）が最も高いシーケンス・ペアを検出する。そして、第２検出部１０１は、検出したシーケンス・ペアのシーケンス類似性をシーケンス対応性Ｓi、jとして取得する。
【００５１】
第２検出部１０１は、全ての候補ペアについて、シーケンス類似性（選好係数によりスケーリングされた値）が最も高いシーケンス・ペアを検出するとともに、当該シーケンス・ペアのシーケンス対応性をも取得する。これにより、ビデオクリップが他のビデオと合成可能であるかを判断することができる。
【００５２】
（２−３）マッチング処理部１０２
マッチング処理部１０２は、第２検出部１０１で検出されたシーケンス・ペアを用いて、類似性の高いビデオのペア内におけるトランジションの候補を検出するものである。フレームレベルのトランジションを直接生成すると、不自然になってしまう。そこで、マッチング処理部１０２は、第２検出部１０１で検出されたシーケンス・ペアにおいて、類似度が高いフレームのペアをマッチング処理により検出する。
【００５３】
マッチング処理部１０２は、図１に示すように、共通パターン検出部１１０、人物検出部１１１及び顔検出部１１２を有している。
【００５４】
マッチング処理部１０２は、共通パターン検出部１１０、人物検出部１１１及び顔検出部１１２を用いて、第２検出部で検出された２つのシーケンス内で類似度の高いフレームのペアであるキー・フレーム・ペア候補を特定する。特定されたキー・フレーム・ペア候補のフレームのペアが、後述する連結ビデオ生成部１３で生成される連結ビデオの連結すべき箇所となる。
【００５５】
ここで、マッチング処理部１０２は、対象となる２つのシーケンスに対して、共通パターン検出部１１０、人物検出部１１１及び顔検出部１１２及びこれら組み合わせのうち何れか１つを実行する。
【００５６】
（２−３−１）共通パターン検出部１１０
共通パターン検出部１１０は、局所的視覚パターン検知を用いた特徴オブジェクト（ｓａｌｉｅｎｔ  ｏｂｊｅｃｔ）マッチングを行うものである。なお、局所的視覚パターン検知を用いたマッチングは公知であるため、ここでの説明は省略する。
【００５７】
共通パターン検出部１１０は、対応シーケンス内のフレーム・ペアごとに、共通パターン検出を行い、最大パターンによる裏付けがあるフレーム組をキー・フレーム・ペア候補として選択する。
【００５８】
共通パターン検出部１１０は、第２検出部１０１で行ったシーケンス・マッチング用のキーポイントに基づくマッチングとは異なる画像マッチングに基づいて、類似度の高いシーケンスのペアについてフレーム間で共通するパターン（オブジェクト）、例えばおもちゃ、車、風景を検出する。
【００５９】
通常、画像マッチングは、大量の異常値を含むものが多いため、共通パターンを検出するために、ロバスト・フィッティング法が必要となる。具体的には、共通パターンとは、同一あるいは類似の同次変換パラメータを共有するマッチング・ペアを示す。共通パターン検出部１１０は、画像マッチングの一例として、Ｇｒａｐｈ  Ｓｈｉｆｔ法を適用して、一致したペアに空間的制約を導入し、高密度の共通パターンを検出する。
【００６０】
（２−３−２）人物検出部１１１
人物検出部１１１は、人間の自動特定法に基づいた自動人体検出処理を用いて、人物の外観マッチングを行うものである。なお、自動人体検出処理は、公知の技術であるので、以下簡単に省略する。
【００６１】
人物検出部１１１は、人物検出用のデータセットから得た注釈つき人物画像で学習させたｐａｒｔ−ｂａｓｅｄモデルを予め保持している。人物検出部１１１は、シーケンスのペアについての各フレームに対して、予め保持しているｐａｒｔ−ｂａｓｅｄモデルとのマッチング処理を行い、人物を検出する。
【００６２】
その後、人物検出部１１１は、自動人体検出処理における検出結果を用いて、シーケンスのペアのフレーム間において共通する人物を検出する。
【００６３】
人物検出部１１１は、検出結果に基づいて、あるフレーム・ペアの人物の類似度が所定の閾値よりも高ければ、そのフレーム・ペアをキー・フレーム・ペア候補として選択する。
【００６４】
図３は、ｐａｒｔ−ｂａｓｅｄモデルの一例と、それを用いた検出結果の一例を示している。
【００６５】
ｐａｒｔ−ｂａｓｅｄモデルは、２つの部分を含むものである。一つは、完全なビュー（ルートモデルとして示される）を描くもので、もう一方は、部分ビュー（部分モデルとして示される）を描くものである。
【００６６】
図３（ａ）、（ｂ）では、ｐａｒｔ−ｂａｓｅｄモデルは、二つのルートモデル（それぞれ上半身とと全身）と、ルートモデルごとに四つの部分モデルを含む。図３（ｃ）は、いくつかのフレームにおける数個の検出結果例を示している。検出された人体の外見は、カラーヒストグラムで表され、異なるフレーム／ビデオに出現する同一の人物を探すためにマッチングが行われる。
【００６７】
なお、ｐａｒｔ−ｂａｓｅｄモデルを用いたマッチング処理、カラーヒストグラムを用いたマッチング処理は、公知の技術であるため、ここでの説明は省略する。
【００６８】
（２−３−３）顔検出部１１２
顔検出部１１２は、人の顔の自動特定法に基づいた自動顔検出処理を用いて、顔の外観マッチングを行うものである。
【００６９】
顔検出部１１２は、シーケンスのペアについての各フレームに対して自動顔検出処理を行う。顔検出部１１２は、自動顔検出処理における検出結果に基づいて、あるフレーム・ペアの顔の類似度が所定の閾値よりも高ければ、そのフレーム・ペアをキー・フレーム・ペア候補として選択する。
【００７０】
自動顔検出処理の一例を、以下に示す。
【００７１】
顔検出部１１２は、マルチビュー検出処理及びアクティブシェイプモデルを用いて顔の位置合わせを行う。顔検出部１１２は、フレームごとに、ほぼ正面の顔の認識を行い、顔領域の位置を、いくつかの顔の部分、例えば目、口、輪郭などとともに特定する。顔の含まれるフレームは以下の基準に基づいて、顔を含む別のフレームとマッチングされる。
【００７２】
基準１）顔領域が十分に大きいこと。小さな領域におけるビデオマッチング及びトランジションは、不自然になってしまうことが多いため、小さな顔領域は重要性が低い。例えば、顔領域の閾値を３６００ピクセルとする。
【００７３】
基準２）顔が同一人物のものであること。まず、顔位置合わせを行って顔の位置を合わせ、顔のペアごとに抽出した特徴ベクターについて、ユークリッド距離を算出する。なお、顔領域の閾値は、大部分のミスマッチ候補を除外できるよう、経験的に設定する。
【００７４】
基準３）二つの顔の姿勢があまり違わないこと。顔検出の出力は姿勢ビュー情報を含む。また、正面を向いていない顔のマッチングよりも、正面を向いた顔のマッチングが好ましい。
【００７５】
顔検出処理におけるマッチングの例を図４に示す。フレームＦ１００及びフレームＦ１０１それぞれにおける顔領域Ｆ１１０、Ｆ１１１は、所定の以上の大きさであり、基準１を満たしている。また、顔領域Ｆ１１０、Ｆ１１１それぞれにおける顔は同一人物であるので、基準２を満たしている。最後に、顔領域Ｆ１１０、Ｆ１１１それぞれにおける顔の姿勢もほぼ同じであり、基準３を満たしている。
【００７６】
よって、顔検出部１１２は、フレームＦ１００及びフレームＦ１０１から共通する人物の顔を検出する。
【００７７】
（３）グラフ生成部１２
グラフ生成部１２は、ビデオ記憶部１０に記憶されているＮ個のビデオクリップ（Ｖ1、Ｖ2、・・・、Ｖn）について、第２検出部１０１で検出されたシーケンス・ペア及び当該シーケンス・ペアのシーケンス対応性を用いて、有向重み付のマッチング・グラフＧ＝（Ｖ、Ｅ）を生成する。ここで、Ｖはノード（ビデオ）を示し、Ｅは有向重み付のエッジを示す。ここで、エッジＥの有向重みは、Ｅi、jと表記され、ビデオＶiからビデオＶjへの有向重みを示す。そして、Ｅi、jで示される値は第２検出部１０１で検出されたシーケンス・ペアのシーケンス対応性Ｓi、jに基づいて算出された値である。なお、算出方法については後述する。なお、有向重みそのものをエッジともいう。
【００７８】
そして、グラフ生成部１２は、生成した有向重み付グラフＧから最適な経路Ｐを検出する。ここで、グラフにおける経路を見つける際には、以下の基準が考慮される。
【００７９】
（基準１）連続性：  経路の各エッジは、所定の閾値より大きい重みを有すること。そうでない場合には、そのエッジは選択されない。
【００８０】
（基準２）完全性：  経路全体が十分に長いこと。ビデオの完全性を確保するため、組み合わせるクリップの数が多いことが好ましい。最長経路の検出については、後述する。
【００８１】
（基準３）多様性：  ノードは多様であること。マッチングされたクリップは、ほぼ重複するバージョンを多く含む可能性があるため、合成したビデオが小さくなるように、それらを除外する必要がある。なお、多様性は、ビデオ間の類似性を調査することによって達成される。つまり、ビデオ間の類似性として、ＰｍＨ手法により候補ペアの検出を行い、一のビデオに対して、候補ペアを４つ検出している。これにより、前記一のビデオについては、後続に連結するビデオとして４パターン存在することとなり、多様である。そして、このうちの１パターンが経路として選択されると、以後の経路検出には、そのパターンを除外するよう、当該経路を示すエッジの重みを後述するような方法でスケーリングする。
【００８２】
以下、グラフ生成部１２についての詳細な機能構成について説明する。
【００８３】
グラフ生成部１２は、図１に示すように、グラフ構成処理部１２０、エッジ剪定部１２１及び経路検出部１２２を有している。
【００８４】
（３−１）グラフ構成処理部１２０
グラフ構成処理部１２０は、第１検出部１００で選択されたビデオの候補ペアそれぞれについて、第２検出部１０１で算出された当該候補ペアに対応するシーケンス対応性を用いて有向重みを付与する。これにより、各ビデオのペアについて有向なエッジが付与されることとなり、有向重み付グラフＧが生成されることとなる。以下、候補ペアをビデオＶｉ及びビデオＶｊとして、グラフ構成処理部１２０の機能の詳細について説明する。
【００８５】
グラフ構成処理部１２０は、ビデオＶｉ及びビデオＶｊについて第２検出部１０１で算出されたシーケンス対応性Ｓi、jと、以下の数式４とを用いて、ビデオＶｉからビデオＶｊへの有向重みＥi、jを算出する。
【００８６】
【数４】
2012137493.tif 000006
【００８７】
ここで、Ｗi、jは、ビデオＶｉ及びビデオＶｊについて上記数式１で算出された値であり、θは、候補ペア全てについて数式１により算出された値の平均値である。
【００８８】
（３−２）エッジ剪定部１２１
エッジ剪定部１２１は、グラフ構成処理部１２０で構成された有向重み付グラフＧを入力とし、当該グラフＧにおける閉経路を検出し、検出した閉経路を構成する少なくとも１つのエッジを剪定、つまり当該１つのエッジをグラフＧから除外するものである。これにより、類似性のある複数のビデオを連結したビデオにおいて、繰り返し再生されるのを防ぐことができる。
【００８９】
具体的には、エッジ剪定部１２１は、Ｄｅｐｔｈ−Ｆｉｒｓｔ−Ｓｅａｒｃｈ手法を用いてグラフＧにおける閉経路を検出する。エッジ剪定部１２１は、検出した閉経路について当該閉経路を構成するエッジのうち有向重みの値が最も小さいエッジをグラフＧから除外する。Ｄｅｐｔｈ−Ｆｉｒｓｔ−Ｓｅａｒｃｈ手法は公知であるため、ここでの説明は省略する。
【００９０】
（３−３）経路検出部１２２
経路検出部１２２は、エッジ剪定部１２１によりエッジ剪定がなされたグラフＧを入力として、エッジ剪定がなされたグラフＧから１つ以上の最適な経路を検出する。
【００９１】
経路検出部１２２は、グラフＧ＝（Ｖ、Ｅ）から、最も長い経路Ｐを検出する。ここで、グラフ理論における最長経路問題は、最適化の二重性を調査することにより、最短路問題に変換できることが知られている。最長路問題に対する入力グラフがＧである場合、グラフＧ’上の最短単純路は、エッジの重みが逆数である以外、Ｇと全く同じである。しかし、元のグラフＧにおける正閉路は、Ｇ’における負閉路となる。したがって、負閉路を有するグラフにおいて最短単純路を見つけることは、ＮＰ完全問題である。Ｇに閉路がない場合、Ｇ’には負閉路がなく、多項式時間の元々の問題を解決するのに、いかなる最短経路探索アルゴリズムでもＧ上に実装可能である。したがって、閉経路が存在しなグラフにおける最長経路問題は、非巡回グラフでは容易に解決できる。本実施形態では、エッジ剪定部１２１の機能により剪定後のグラフＧには閉経路は存在していないので、剪定後のグラフＧから最長経路Ｐを検出することを、剪定後のグラフＧの各重みの逆数からなるＧ’から最短経路を検出することに置き換えることで、最長経路Ｐが検出される。
【００９２】
最長経路の生成手法は種々の手法が存在する。
【００９３】
図５は、剪定後のグラフ（ビデオ類似グラフ）Ｇ１００から、自動経路探索手法、対話型経路探索（ビデオグループ固定）及び対話型経路探索（オブジェクト固定）による経路探索（経路検出）の結果を示している。これら手法について、以下に説明する。
【００９４】
（３−３−１）自動経路探索について
この手法は、自動的に１つ以上の最大経路を見つけ出すものである。経路検出部１２２は、グラフＧから各有向重み（各エッジ）が所定値以上からなる最長経路を検出すると、その経路のノードに付された全て有向重み（エッジの重み）を、係数λ（例えば、λ＝０．２）でスケーリング（乗算）し、それらのノードが再び選択される可能性を低くする。そして、経路検出部１２２は、更新したグラフＧにおいて、再度、別の最長経路を探索する。この処理は、最終的な経路の重みの合計が閾値未満であるという条件が満たされるまで、繰り返される。
【００９５】
例えば、図５に示すビデオ類似グラフＧ１００において、エッジの重みが０．５以上となるエッジで構成される最長経路を求め場合について説明する。まず経路検出部１２２は、エッジの重みが０．５以上となるエッジで構成される最長経路として、ノード７、１２、１４、１８、１９、１６の順序からなる経路Ｇ２００を検出する。そして、この経路Ｇ２００における各エッジの重みにλ（＝０．２）を乗算する。そうすることで、これらエッジの重みは０．５より小さい値となるので、これらエッジが再度探索により検出されることはない。その後、経路検出部１２２は、経路Ｇ２０１を検出し、経路Ｇ２０１に存在するエッジの重みについて、経路Ｇ２００の場合と同様にスケーリングする。そして、経路検出部１２２は、経路Ｇ２０２を検出し、経路Ｇ２０２について同様のスケーリングを行う。
【００９６】
また、図６において、ユーザーに提示するインターフェースの一例を示す。この例では、システムがビデオクリップのグループの経路を自動的に見つけ出した後には、３つの最長経路（ビデオパズル）Ｇ３００、Ｇ３０１、Ｇ３０２が存在することを示している。ここで、エッジのよる２つのビデオクリップのリンクはそれらの類似性を示し、エッジの太さは、それらがどの程度類似しているかを示す。例えば、ユーザーがビデオパズルＧ３００、Ｇ３０１、Ｇ３０２の何れかのインジケータを押せばいつでも、ユーザーに対して、インジケータが押下されたビデオパズルを構成する各ビデオクリップを用いて合成したワンショット・ビデオが再生される。
【００９７】
（３−３−２）対話型の探索手法
対話型の探索手法は、個人的な利用において、人による対話型操作により連続したビデオクリップを検索するものである。当該探索手法は、ユーザーが特定のビデオクリップまたは特定のオブジェクトやシーンへのフォーカスを含むワンショット・ビデオを求める場合に有効である。
【００９８】
（ａ）ユーザーによりビデオクリップが固定された場合
この場合における探索手法は、一のノードから他のノードへの最長経路であって、当該最長経路にユーザーにより指定されたビデオクリップ（ノードＶi）を含む経路を検出するものである。構成されるグラフは非巡回グラフであるので、検出される経路において、二度以上選択されるノードがないことが保証されている。なお、ユーザーにより指定されるビデオクリップは１つ以上であればよく、複数のビデオクリップが指定された場合には、指定された全てのビデオクリップを含む最長経路を検出することとなる。また、ユーザーに指定された一のビデオクリップが最長経路の先頭であってもよいし、最後尾であってもよい。
【００９９】
例えば、図５に示すビデオ類似グラフＧ１００において、ノード（ビデオクリップ）９、１１、１３がユーザーにより指定された場合について説明する。
【０１００】
経路検出部１２２は、指定されたノードからなる経路を生成する。例えば、経路検出部１２２は、ノード９、ノード１３、ノード１１の順路となるよう経路Ｇ２１０を生成する。その後、経路検出部１２２は、ノード９までに至る最長経路（ノード１、３、４、９の順路の経路）を検出する。また、経路検出部１２２は、ノード１１を先頭とする最長経路を探索する。この場合、ノード１１と類似するノードは存在しないため、ノード１１を先頭とする最長経路は検出されない。経路検出部１２２は、検出された経路（ノード１、３、４、９の順路の経路）と、生成した経路Ｇ２１０を結合して、最終的な最長経路（ノード１、３、４、９、１３、１１の順路の経路）Ｇ２１１を生成する。
【０１０１】
ユーザーにより指定されたノードが１つの場合には（指定されたノードをＶkとする）、あるノードＶiから当該ノードＶkまでに至る最長経路、及び当該ノードＶkから他のノードＶjに至るまでの最長経路をそれぞれ検出し、検出した経路それぞれを結合し、１つの最長経路（Ｖi〜Ｖk〜Ｖjの順路の経路）を生成する。このとき、あるノードＶiから当該ノードＶkまでに至る最長経路が存在しないときに生成される経路はＶk〜Ｖjの順路の経路となり、当該ノードＶkから他のノードＶjに至るまでの最長経路が存在しないときに生成される経路はＶj〜Ｖkの順路の経路となる。
【０１０２】
図７は、ユーザーにより３つのビデオクリップが固定された場合において、ユーザーに提示するインターフェースの一例を示す。この例では、ユーザーの指定により、ビデオクリップＧ３１０、Ｇ３１１、Ｇ３１２が選択されている。この場合、経路検出部１２２は、指定されたビデオクリップ（ノード）Ｇ３１０、Ｇ３１１、Ｇ３１２からなる経路、例えばＧ３１０、Ｇ３１１、Ｇ３１２を順路とする経路を生成する。経路検出部１２２は、ビデオクリップＧ３１２を先頭とする最長経路を探索し、その結果としてビデオクリップＧ３１２、Ｇ３１３、Ｇ３１４、Ｇ３１５、Ｇ３１６を順路とする経路を検出する。ビデオクリップＧ３１０と類似する他のビデオクリップは存在しないため、Ｇ３１０までに至る経路は検出されない。経路検出部１２２は、指定されたビデオクリップからなる経路と、検出した経路とを結合して、１つの最長経路（ビデオクリップＧ３１０、Ｇ３１１、・・・、Ｇ３１６を順路とする経路）を生成する。
【０１０３】
（ｂ）ユーザーによりオブジェクトが固定された場合
この場合における探索手法は、ユーザーが指定したオブジェクトを含むワンショット・ビデオを検出するものである。
【０１０４】
経路検出部１２２は、ユーザーにより選択されたオブジェクトを含む２つのビデオＶi及びＶjを特定する。そして、特定した一のノードＶiを先頭とし、特定したノードＶjを最後尾とする最長経路を探索する。
【０１０５】
例えば、図５に示すビデオ類似グラフＧ１００において、ユーザーによりあるオブジェクトが指定され、さらに、指定したオブジェクトを含むノード１７、１９が指定された場合について説明する。
【０１０６】
経路検出部１２２は、指定されたオブジェクトを含むノード５、及びノード１６を検出する。そして、ノード５からノード１６までに至る最長経路であって、ノード１７、１９からなる経路Ｇ２２０を含み、経路途中のノードにおいても指定されたオブジェクトを含む経路を探索する。ここでは、経路検出部１２２は、探索結果として、経路Ｇ２１１を検出する。
【０１０７】
なお、指定されたオブジェクトを含むノード５、及びノード１６の少なくとも１のノードが最長経路の途中にあってもよい。この場合の経路検出は、例えば、ノード５、ノード１６とも途中に存在する経路を検出場合には、ビデオクリップが固定された場合と同様に、ノード５、とノード１６とからなる経路を生成し、生成した経路までに至る最長経路及び生成した経路から続く最長経路を検出し、これら３つの経路を結合する。最長経路を検出する際には、指定されたオブジェクト、又は指定されたオブジェクトとは異なるが生成した経路（ノード５、ノード１６からなる経路）に含まれるオブジェクトを含む最長経路を検出する。
【０１０８】
また、図８では、ユーザーによりオブジェクトが固定された場合において、ユーザーに提示するインターフェースの一例を示す。この例では、ユーザーの指定により、ビデオクリップＧ３５０、Ｇ３５１それぞれに共通する人物ＯＢＪ１、ＯＢＪ２が選択されている。
【０１０９】
そして、経路検出部１２２は、選択された人物を含み、ビデオクリップＧ３５０までに至る最長経路を、例えばビデオクリップＧ３５２、Ｇ３５３、Ｇ３５４、Ｇ３５０を順路する経路を検出する。経路検出部１２２は、ビデオクリップＧ３５０、Ｇ３５１それぞれに共通する人物を含み、ビデオクリップＧ３５１に後続するビデオクリップは存在しないため、ビデオクリップＧ３５１に含まれる他のオブジェクトＯＪＢ１０を含み、ビデオクリップＧ３５１に後続するビデオクリップを探索する。その結果としてオブジェクトＯＪＢ１０と共通するオブジェクトＯＢＪ１１を含むビデオクリップＧ３５５が検出される。そして、経路検出部１２２は、オブジェクトＯＢＪ１０、ＯＢＪ１１に共通するオブジェクトを含み、ビデオクリップＧ３５５に後続するビデオクリップは存在しないため、ビデオクリップＧ３５５に含まれる他のオブジェクトＯＪＢ１２を含み、ビデオクリップＧ３５５に後続するビデオクリップを探索する。その結果としてオブジェクトＯＪＢ１２と共通するオブジェクトＯＢＪ１３を含むビデオクリップＧ３５６が検出される。
【０１１０】
最後に、経路検出部１２２は、ビデオクリップＧ３５２、Ｇ３５３、Ｇ３５４、Ｇ３５０、Ｇ３５１、Ｇ３５５、Ｇ３５６を順路とする最長経路を生成する。
【０１１１】
（４）連結ビデオ生成部１３
連結ビデオ生成部１３は、経路検出部１２２で検出された経路を用いて、当該経路上に存在する各ビデオクリップを連結してワンショット・ビデオを生成するものである。
【０１１２】
フレームレベルでトランジションを直接生成すると、視覚的な途切れが生じ、不自然になってしまう。また、マッチング処理部１０２でキー・フレーム・ペア候補が特定された場合には、これらを単に連結することも考えられる。しかしながら、キー・フレーム・ペア候補である２つのフレームにおいては、一致する部分が、共通パターン、人体、顔などのように局部的である。これら２つのフレームに基づいて、２つのビデオを直接繋ぎ合わせると、唐突に変化することになってしまい、この場合においても不自然な繋がりとなってしまう。
【０１１３】
（キー・フレーム・ペア候補が存在する場合）
そこで、連結ビデオ生成部１３は、経路検出部１２２で検出された経路上の隣り合う２つのビデオ間においてキー・フレーム・ペア候補が特定された場合には、特定されたキー・フレーム・ペア候補を用いて２つのビデオ間について自然なトランジションとなるよう２つのビデオを連結する。このとき、ビデオＶiにビデオＶjが後続するように連結する場合、連結ビデオ生成部１３が生成する連結ビデオは、キー・フレーム・ペア候補であるフレームそれぞれを含むフレームシーケンスＳｅｑi、sと、フレームシーケンスＳｅｑj、tとのみからなるものではない。連結ビデオ生成部１３が生成する連結ビデオは、フレームシーケンスＳｅｑi、sと時間的に連続し、先行する部分（以下、先行部分）、及びフレームシーケンスＳｅｑj、tと時間的に連続し、後続する部分（以下、後続部分）とを含む。さらに連結ビデオは、前記先行部分、フレームシーケンスＳｅｑi、s、フレームシーケンスＳｅｑj、t及び後続部分の順に連結される。
【０１１４】
具体的には、連結ビデオ生成部１３は、キー・フレーム・ペア候補となる２つのフレームに対してイメージ・モーフィング手法を適用して、キー・フレーム・ペア候補に対応する２つのビデオを連結する。
【０１１５】
通常、イメージ・モーフィング手法は、  ビデオ・アニメーションにおけるトランジショに用いられることが多い。モーフィングの目的は、補間テクスチャ・スムージングを用いて、元の形から目的の形にスムーズに変形する中間ジオメトリを生成することである。
【０１１６】
連結ビデオ生成部１３は、以下の手順により、イメージ・モーフィング手法が適用された連結ビデオを生成する。
【０１１７】
（手順１）最小一致領域を探す：  ２つのフレームにおける一致したオブジェクト間のトランジションは、スムーズかつ連続的でなければならないことが多い。そこで、連結ビデオ生成部１３は、類似するビデオＶi及びＶjにおけるキー・フレーム・ペア候補であるフレームＦk及びＦlにおけるトランジションを単純に生成する代わりに、最小一致領域間のトランジションを生成する。ここで、ＦkはビデオＶiにおけるｋ番目のフレームであり、ＦlはビデオＶjにおけるｌ番目のフレームである。連結ビデオ生成部１３は、スムーズさを保証するため、次の３つの手順により、最小一致領域を選択する：（手順１−１）検出する領域の縦横比率を決定する。決定される縦横比率は、ビデオＶi及びビデオＶjにおいて同一である。（手順１−２）決定された縦横比率の領域で局所一致ポイントの大部分をカバーするか否かを判断し、カバーすると判断した場合には、決定された縦横比率の領域を最小一致領域として検出する。“手順１−１”で決定された縦横比率の領域で最小一致領域が検出されないときには、再度“手順１−１”により縦横比率が決定され、再度決定された縦横比率の領域で最小一致領域を探す。（手順１−３）フレームＦk、Ｆlについての最小一致領域内の局所一致ポイントの中心間のオフセットは、最小化される。
【０１１８】
（手順２）一致したオブジェクトにフォーカスをあてる：  連結ビデオ生成部１３は、最小一致領域を特定した後、ビデオＶiにおけるフレームＦkより前のｍ個のフレームを探し、ｍ個のフレーム及びフレームＦkからなるシーケンスに含まれる一致したオブジェクトに対してズーム・イン手法を適用する。ここで、ｍは、フレームＦkと、フレームＦkで特定された最小一致領域の面積比率とにより決定される。同様に、連結ビデオ生成部１３は、ビデオＶjにおいてフレームＦlより後のｎ個のフレームを探し、ｎ個のフレーム及びフレームＦlからなるシーケンスに含まれる一致したオブジェクトに対してズーム・アウト手法を適用する。ここで、ｍは、フレームＦlと、フレームＦlで特定された最小一致領域の面積比率とにより決定される。
【０１１９】
（手順３）局所位置合わせ及び局所テクスチャ・シェイプ・マッピングを行う：  連結ビデオ生成部１３は、フレームＦk、Ｆlについての最小一致領域間でモーフィングの処理を行い、中間フレームを生成する。まず、連結ビデオ生成部１３は、一致するオブジェクトに対するマッチングセットポイントを前提として、ドロネー三角分割セットを生成する。そして、連結ビデオ生成部１３は、ドロネー三角分割セットと対応する要素を用いて、中間三角形を算出する。そして、三角形分割内のテクスチャについて線形補間が行われる。なお、ドロネー三角分割セットを用いた線形補間は公知であるため、ここでの説明は省略する。
【０１２０】
（手順４）不一致領域に対しフェザリングを行う：  最小一致領域間のトランジションは、不一致領域について、まだゴースト現象が残っている可能性がある。 そこで、連結ビデオ生成部１３は、不一致領域に対して画像モザイクに一般的に用いられるフェザリング法を適用する。すなわち、連結ビデオ生成部１３は、各フレーム中のピクセルについて、エッジと、マッチングポイントの中心までの距離に対して比例的に重み付を行う。
【０１２１】
（キー・フレーム・ペア候補が存在しない場合）
２つのビデオの間でキー・フレーム・ペア候補が存在しない場合について説明する。この場合、「コンテクストを無視した」合成とみなし、連結ビデオ生成部１３は、直接的な合成を行う。
【０１２２】
なお、直接的な合成ではなく、連結ビデオ生成部１３は、フェード・イン、フェード・アウトなど他のトランジション法を適用、又は、ピクチャ・イン・ピクチャ技術を用いてもよい。２つのビデオについてピクチャ・イン・ピクチャ技術を用いる場合、連結ビデオ生成部１３は、一のビデオの終了部分におけるフラットな領域を見つけ、他のビデオを、仮想ＴＶフレームを用いてこの領域に埋め込むことによって連結でき、トランジションについてはＴＶフレームへのズーム・インによって実現できる。
【０１２３】
（４−１）具体例
通常、モーフィング手法は、一致したオブジェクトについては魅力的な効果を生み出すが、一致していない部分については、ゴースト現象をおこす可能性がある。本実施の形態においては、フレームの部分領域についての一致に基づいているため、ゴースト現象が生じる可能性は高い。そのため、上述したように、不一致領域に対してフェザリングを施すことで、ゴースト現象を回避することができる。
【０１２４】
図９は、ビデオＶiとビデオＶjとを連結する際の上記手順１から手順３までの具体例を示している。
【０１２５】
連結ビデオ生成部１３は、ビデオＶiとビデオＶjとにおける最小一致領域を検出する。図９では、ビデオＶiの画像（フレーム）Ｆ１００に含まれる領域Ｆ１１０と、ビデオＶjの画像（フレーム）Ｆ２００に含まれる領域Ｆ２１０とが、最小一致領域として検出される。ここまでが上記手順１に相当する。
【０１２６】
連結ビデオ生成部１３は、フレームＦ１００及び当該フレームＦ１００より前方に所定枚数存在するフレームＦ１０１、Ｆ１０２に対して検出した最小一致領域Ｆ１１０にフォーカスをあてズーム・イン手法を適用する。また、連結ビデオ生成部１３は、フレームＦ２００及び当該フレームＦ１００より後方に所定枚数存在するフレームＦ２０１、Ｆ２０２に対して検出した最小一致領域Ｆ２１０にフォーカスをあてズーム・アウト手法を適用する。ここまでが上記手順２に相当する。
【０１２７】
そして、連結ビデオ生成部１３は、フレームＦ１００とフレームＦ２００における最小一致領域Ｆ１１０、Ｆ２１０について、マッチングセットポイントを検出する。図９の上段に示すフレームＦ１００、Ｆ２００について両者間を結ぶ複数の線分それぞれの両端の組がマッチングセットポイントとなる。連結ビデオ生成部１３は、検出したマッチングセットポイントを用いて中間フレームＦ３００、Ｆ３０１、・・・、Ｆ３０２、Ｆ３０３を生成する。ここまでが上記手順３に相当する。
【０１２８】
また、図１０は、家族／風景のビデオクリップの本実施の形態によるトランジションと、他の手法によるトランジションとを比較した例である。
【０１２９】
図１０においてトランジション１〜４それぞれに示す両端のフレームのペア（フレームＦ４００とフレームＦ４５０、フレームＦ５００とフレームＦ５５０、フレームＦ６００とフレームＦ６５０、フレームＦ７００とフレームＦ７５０）は、合致した開始・終了フレームである。各トランジション（例えば５個フレームを選択）の一列目は、本実施の形態で提案した手法で得られたものである。各トランジションの二列目は、一般的に用いられているトランジション（ここでは、フェード・イン／フェード・アウト）によって得られたものである。
【０１３０】
トランジション１は、フェザリングを行わずに、合致キーポイントによって生成された。トランジション２〜４は、提案した手法によって、トランジション用の異なる手掛かりを用いて得られたものである。例えば、トランジション２では、トランジションの手掛かりとして“人の顔”を、トランジション３では、トランジションの手掛かりとして“人体（上半身）”を、トランジション４では、トランジションの手掛かりとして“建物（塔）”を、それぞれ用いた場合の一例である。
【０１３１】
１．３  動作
（１）動作概要
ここでは、画像処理装置１の動作概要について、図１１に示す流れ図を用いて説明する。
【０１３２】
検出処理部１１は、ビデオ記憶部１０に記憶されている複数のビデオクリップについて、類似するビデオクリップのペアを検出する（ステップＳ５）。なお、この処理の詳細については、後述する。
【０１３３】
グラフ生成部１２は、ステップＳ５の処理により検出されたビデオクリップのペア及び当該ペアの類似性を用いて、有向重み付グラフを生成する（ステップＳ１０）。
【０１３４】
グラフ生成部１２は、生成した有向重み付グラフから最適な経路を検出する（ステップＳ１５）。
【０１３５】
連結ビデオ生成部１３は、ステップＳ１５で検出された経路上に存在する各ビデオクリップを連結してワンショット・ビデオを生成する（ステップＳ２０）。なお、この処理の詳細については、後述する。
【０１３６】
（２）ビデオのペア検出処理
ここでは、図１１に示すステップＳ５のビデオのペア検出処理について、図１２に示す流れ図を用いて説明する。
【０１３７】
第１検出部１００は、ビデオ記憶部１０に記憶されている各ビデオについて、ＰｍＨ手法を用いて、ビデオＶi（基準ビデオＶi）と類似する類似ビデオとからなる１つ以上の候補ペアを選択する（ステップＳ１００）。
【０１３８】
第２検出部１０１は、選択された各候補ペアについて、基準ビデオＶiのビデオ終了部分から１つ以上のフレームシーケンスを、類似ビデオそれぞれかのビデオ開始部分から１つ以上のフレームシーケンスを、それぞれ取得する（ステップＳ１０５）。ここで、基準ビデオＶiのビデオ終了部分から１つ以上のフレームシーケンスのそれぞれのサイズと、類似ビデオそれぞれかのビデオ開始部分から１つ以上のフレームシーケンスのそれぞれのサイズとは同一である。
【０１３９】
第２検出部１０１は、類似ビデオのフレームシーケンス毎に、予め定められた定率を用いて基準ビデオの各フレームシーケンスとのサンプリングを行い、当該サンプリング結果、及びサンプリングの対象となった類似ビデオのサブシーケンスと基準ビデオのサブシーケンスとの組に割り当てられた選好係数を用いて、フレームシーケンスの類似度を算出する（ステップＳ１１０）。
【０１４０】
第２検出部１０１は、候補ペア毎に、フレームシーケンスの類似度が最も高いフレームシーケンスの組を取得する（ステップＳ１１５）。
【０１４１】
マッチング処理部１０２は、取得したフレームシーケンスの組それぞれについてキー・フレーム・ペア候補を取得する（ステップＳ１２０）。
【０１４２】
（３）連結ビデオ生成処理
ここでは、図１１に示すステップＳ２０の連結ビデオ生成処理について、図１３に示す流れ図を用いて説明する。ここでは、連結対象のビデオをＶi、Ｖjとし、ＶiからＶjへ方向に有向グラフが設定されているものとして、以下説明する。
【０１４３】
連結ビデオ生成部１３は、連結対象のビデオ間、つまり図１１に示すステップＳ１５で検出された最長経路上の隣り合うノード（ビデオ）間について図１２で示すステップＳ１２０の実行によりキー・フレーム・ペア候補が取得されているか否かを判断する。つまり、連結ビデオ生成部１３は、最長経路上の隣り合うノード（ビデオ）間についてキー・フレーム・ペア候補が存在するか否かを判断する（ステップＳ２００）。
【０１４４】
キー・フレーム・ペア候補が存在すると判断する場合（ステップＳ２００における「Ｙｅｓ」）、連結ビデオ生成部１３は、キー・フレーム・ペア候補を用いて、連結対象のビデオそれぞれについて合致するオブジェクトの最小一致領域を検出する（ステップＳ２０５）。
【０１４５】
連結ビデオ生成部１３は、検出した最小一致領域内において、ビデオＶi、Ｖjで一致するオブジェクトにフォーカスをあてる（ステップＳ２１０）。具体的には、ビデオＶiにおけるフレームＦkとビデオＶjにおけるフレームＦlとをキー・フレーム・ペア候補とした場合、連結ビデオ生成部１３は、ビデオＶiにおけるフレームＦkより前のｍ個のフレームを探し、ｍ個のフレーム及びフレームＦkからなるシーケンスに含まれる一致したオブジェクトに対してズーム・イン手法を適用する。また、連結ビデオ生成部１３は、ビデオＶjにおいてフレームＦlより後のｎ個のフレームを探し、ｎ個のフレーム及びフレームＦlからなるシーケンスに含まれる一致したオブジェクトに対してズーム・アウト手法を適用する。
【０１４６】
連結ビデオ生成部１３は、局所位置合わせ及び局所テクスチャ・シェイプ・マッピングを行う（ステップＳ２１５）。具体的には、連結ビデオ生成部１３は、キー・フレーム・ペア候補のフレームＦk、Ｆlについての最大一致サブウィンドウ間でモーフィングの処理を行い、中間フレームを生成する。
【０１４７】
連結ビデオ生成部１３は、不一致領域に対しフェザリングを行う（ステップＳ２２０）。具体的には、連結ビデオ生成部１３は、不一致領域に対して画像モザイクに一般的に用いられるフェザリング法を適用する。
【０１４８】
キー・フレーム・ペア候補が存在しないと判断する場合（ステップＳ２００における「Ｎｏ」）、連結ビデオ生成部１３は、「コンテクストを無視した」合成、例えば直接的な合成を行う（ステップＳ２２５）。
【０１４９】
１．４  具体例
ここでは、画像処理装置１の処理について図１４に示す具体例を用いて説明する。
【０１５０】
ビデオ記憶部１０に記憶されている複数のビデオクリップが、検出処理部１１に入力される。
【０１５１】
そして、検出処理部１１で、粗密な部分一致スキーム手法により、類似するビデオペアが検出される。具体的には、検出処理部１１の第１検出部１００が、ＰｍＨ手法により類似するビデオのペアを粗く検出する。そして、粗く検出されたビデオのペアそれぞれについて、第２検出部１０１は、フレーム類似性により類似するシーケンスを検出する。その後、マッチング処理部１０２が、最も類似するシーケンス間において、フレーム類似により一致するオブジェクトを検出する。検出処理部１１による処理により、類似するビデオクリップのグループの形成、類似するビデオクリップ間で類似度の高い部分（シーケンス）の特定、及び類似度の高い部分において一致するオブジェクトの特定がなされる。
【０１５２】
類似するビデオクリップのグループが形成されると、グラフ生成部１２で、有向重みグラフを生成し、生成したグラフからビデオを連結するのに最適な経路を検出する。具体的には、グラフ生成部１２のグラフ構成処理部１２０が、検出処理部１１で生成された類似ビデオクリップのグループから有向重みグラフを生成する。このとき、生成された有向重みグラフに閉経路が存在する場合には、エッジ剪定部１２１により当該閉経路を構成する少なくとも１つのエッジを削除する。経路検出部１２２では、閉経路が存在しない有向重みグラフから、例えば自動経路探索により最適な経路を検出する。
【０１５３】
検出された最適な経路に対して、連結ビデオ生成部１３は、経路上の隣り合うビデオクリップを順次結合することで、結合ビデオを生成する。具体的には、連結ビデオ生成部１３は、隣り合うビデオ間にキー・フレーム・ペア候補が存在する場合にはマッチングにより導かれた連結（シームレスな連結）を行い、キー・フレーム・ペア候補が存在しない場合にはコンテクストを無視した連結（例えば、直接的な連結）を行う。
【０１５４】
上記の各処理を経ることにより、連結されたビデオが生成される。
【０１５５】
以上、説明したように、画像処理装置１は、ビデオ・アルバムにおいて「類似・継続するトピック」を有するビデオクリップを自動的に検出し、それらを自然な形で繋ぎ合わせて、一つの仮想的な長回しビデオにすることにより、包括的なプレゼンテーションを生成し、一貫性のある潜在的なストーリーを伝えることができる。図１５は、その一例を示すものであり、画像処理装置１を用いることで、ビデオ記憶部１０に記憶されている複数のビデオクリップから２つのトピック（シーントピック、人物トピック）を自動で検出し、それぞれのトピックに応じて、結合されたビデオを生成する。
【０１５６】
１．５  変形例
以上、実施の形態に基づいて説明したが、本発明は上記の実施に限られない。例えば、以下のような変形例が考えられる。
【０１５７】
（１）上記実施の形態において、エッジ剪定部１２１は、検出した閉経路について当該閉経路を構成するエッジのうち有向重みの値が最も小さいエッジをグラフＧから除外するとしたが、これに限定されない。
【０１５８】
エッジ剪定部１２１は、時間の制約により、有向重みグラフから閉経路を除外してもよい。通常、ビデオ、特にホームビデオのブラウジングでは、時間の順に視聴するのが普通である。そこで、エッジ剪定部１２１は、閉経路においてビデオクリップのタイムスタンプ・メタデータを用いて、エッジによる対応付けがビデオクリップの撮影日時の順序が維持されるよう、エッジの除去（ビデオ間の関係を断つ）を行う。例えば、閉経路において、エッジの方向が一のビデオから当該一のビデオよりも撮影日時が古い他のビデオへと向いている場合、撮影日時の順序が保たれないので、当該エッジを除去する。こうすることで、有向重みグラフから閉経路が除外される。
【０１５９】
（２）上記実施の形態では、複数のフレームからなる動画像（ビデオ）を処理の対象としたが、これに限定されない。
【０１６０】
処理対象として、単一の画像（静止画像）を用いてもよい。この場合、開始フレームと終了フレームとは同一とみなし、上記で説明した動作により、動画像と静止画像が混在した連結ビデオ（例えば、動画像（ｖｉｄｅｏ０１）−動画像（ｖｉｄｅｏ０２）−静止画像（ｉｍａｇｅ０１）−動画像（ｖｉｄｅｏ０３））を生成することができる。
【０１６１】
（３）上記実施の形態において、ビデオ記憶部１０は、画像処理装置１が備えることとしたが、これに限定されない。
【０１６２】
画像処理装置１とネットワークを介して接続される外部の装置がビデオ記憶部１０を備えてもよい。
【０１６３】
画像処理装置１は、外部の装置からネットワークを介して、処理対象となるビデオクリップを取得することとなる。
【０１６４】
（４）上記実施の形態において、画像処理装置１は、複数の類似するビデオから１つの連結ビデオを作成するものとして説明したが、これに限定されない。
【０１６５】
画像処理装置１は、１つのビデオから要約されたビデオを作成する際に利用されてもよい。
【０１６６】
この場合、１つのビデオを複数に分割し、部分ビデオを生成する。この複数の部分ビデオを、本実施の形態のビデオクリップとして扱うことで、これら部分ビデオのうち類似する部分ビデオをシームレスに連結することができる。
【０１６７】
（５）上記実施の形態で示すＰｍＨ手法は、画像をｐ個の矩形領域に分割し、各領域について同一のハッシュ関数を用いたが、これに限定されない。
【０１６８】
ＰｍＨは、次のような手法でもよい。
【０１６９】
第１検出部１００は、画像をグリッド要素ごとに分割し、分割したグリッド要素ごとに、ハッシュ関数を用いてｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈを算出する。ここで、グリッド要素とは、領域をカバーする部分領域のうち最も大きな共通の領域であり、例えば、画像に含まれるオブジェクトごとの領域である。
【０１７０】
そして、ある部分領域と関連付けられた要素を検索し、検索された要素に対して、算出されたｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈのうち、真であるｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈを選択する。そして、選択したｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈを、当該画像のｍｉｎ−ｈａｓｈ  ｓｋｅｔｃｈとする。
【０１７１】
（６）上記の実施の形態及び変形例で説明した手法の手順を記述したプログラムをメモリに記憶しておき、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などがメモリからプログラムを読み出して、読み出したプログラムを実行することによって、上記の手法が実現されるようにしてもよい。
【０１７２】
また、当該手法の手順を記述したプログラムを記録媒体に格納して、頒布するようにしてもよい。なお、上記プログラムを記憶する媒体としては、例えば、フラッシュメモリや、ＵＳＢメモリやＳＤカード（登録商標）などの外部メモリを一例として挙げることができる。
【０１７３】
（７）上記の実施の形態にかかる各構成は、集積回路であるＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）として実現されてもよい。これらの構成は、１チップ化されても良いし、一部又は全てを含むように１チップ化されてもよい。ここでは、ＬＳＩと表現したが、回路の集積度の違いによっては、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと称呼されることもある。また、集積回路化の手法は、ＬＳＩに限られるものではなく、専用回路または汎用プロセッサで集積回路化を行ってもよい。また、ＬＳＩ製造後にプログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサー（ＲｅＣｏｎｆｉｇｕｒａｂｌｅ  Ｐｒｏｃｅｓｓｏｒ）を用いてもよい。あるいは、これらの機能ブロックの演算は、例えば、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）やＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などを用いて演算することもできる。さらに、これらの処理ステップはプログラムとして記録媒体に記録して実行することで処理することもできる。
【０１７４】
（８）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【０１７５】
１．７  まとめ
上記にて示す画像処理装置は、従来から存在する、類似するビデオのグループを探したり、合成したビデオを音楽やメタデータなどの追加情報に合わせたりする装置とは異なり、いくつかの関連するビデオクリップを合成して、時間的・空間的に一貫性のある、仮想的な長回しビデオ（連結ビデオ）を生成する装置である。
【０１７６】
そして、上記にて説明したように、画像処理装置は、主に三つの主要コンポーネント（検出処理部、グラフ生成部、連結ビデオ生成部）を含んでいる。
【０１７７】
検出処理部は、（ａ）生成されるワンショット・ビデオが、重複を含まない完全な品質となることを保証する根拠となる、ビデオ類似性測定値を取得する機能、（ｂ）コンテンツの開始・終了の対応関係を有するビデオ・ペア内のシーケンスを高速かつ正確に特定する機能、（ｃ）対応シーケンス内においてトランジションの手掛かりとなるキー・フレーム・ペア候補を探し出す機能とを有している。
【０１７８】
グラフ生成部は、構成されたビデオ・マッチング・グラフから最適なビデオ合成を選択する機能、つまり最適な再生順序となる経路を検出する機能を有している。この機能は、全体にわたって最適なコンテンツ一貫性を有するワンショット・ビデオを作成することによって完全に自動で動作することもできるし、任意のトピック（例えば、特定した主要オブジェクトや人物）を有するワンショット・ビデオを生成することにより、ユーザーに対してインタラクティブに動作することも可能である。
【０１７９】
連結ビデオ生成部は、最適な経路の隣り合うビデオ対応ペアを１つずつ結合する機能を有する。このとき、結合される箇所においては、一致するオブジェクトについてはズーム・イン、ズーム・アウトを施し、一致しない領域についてはフェザリングを施すことにより、フェード・イン、フェード・アウト、ワイプ、ディゾルブなどのような従来のトランジションと比較して、より自然なものとなっている。画像レベル及びシーケンスレベルの両方でビデオ・ペアのマッチングが可能であるため、コンテンツに基づく連続的トランジションが実現できる。そのため、連結ビデオ生成部は、一貫性を有するリンクを仮想的に生成する。
【０１８０】
また、これらの機能を適用した具体例を以下に紹介する。
【０１８１】
（適用１）個人ビデオ・プレゼンテーション。大量の個人用ビデオ・コンテンツから、ビデオにおける、コンテンツに関して連続的な関係を明確に示すビデオ・マッチング・グラフを生成できる。複数のビデオクリップから検出されたストーリー・ライン（有向重み付具グラフでの最適な経路）は、自動的にポップアップ表示される。さらに、ユーザーに必要なのは特定の人物やシーンを指定することだけであり、ビデオグラフをマイニングすることによって、対応する人物やシーンを描いたワンショット・プレゼンテーションを生成することができる。
【０１８２】
（適用２）包括的なランドマーク・ビデオの生成。同じランドマークを描いた複数のウェブビデオを用いて、ランドマークの、ワンショットの視覚的描写を生成することができる。これには、たとえば異なる視野から撮影された視覚的コンテンツのような、ランドマークのより包括的な視覚的描写が含まれる。
【０１８３】
（適用３）ユーザーがネットワーク上からビデオクリップを取得した場合、システムは自動的に類似のクリップを合成し、ユーザーは、効率的にワンショット・プレゼンテーションを視聴できる。
【０１８４】
これらの適用例で示すように、本実施の形態を用いることで、例えば、ホームビデオ・プレゼンテーション、ランドマーク・ビデオの生成、ソーシャル・ネットワークを中心とする個人用ビデオクリップ（例えば、インターネットから入手したビデオクリップ）の体系化などが可能となる。そして、従来のビデオ抽出・表示技術よりも新しいプレゼンテーション法（仮想ワンショット・ビデオ）を提供するだけでなく、編集など、さらなるサービスも容易にすることができる。
【０１８５】
また、本実施の形態の画像処理装置は、複数のビデオクリップから仮想ワンショット・プレゼンテーションを自動的に生成できるものであり、ビデオ・コンテンツの新たなプレゼンテーションを提供し、複数のビデオクリップからのストーリーに対し、ユーザーがより深い印象を得ることができるようにするものである。
【０１８６】
そして、画像処理装置の特徴は、以下のように要約できる。
【０１８７】
（１）上記実施の形態で示す「ビデオパズル」によるワンショット・プレゼンテーションの生成方法により、特定のトピックに関するビデオクリップを抽出し、それよって仮想的なワンショット・プレゼンテーションを合成することができる。この方法はフレキシブルであり、いくつかのコンポーネントは、カスタマイズして異なるかたちに応用できる。
【０１８８】
（２）複数のビデオにおける対応するフレーム（類似するフレーム）を検出し、それらを最適な方法で合成する。
【０１８９】
従来、ロング・ショットは、包括的なコンテンツを継続的かつ一貫性をもって提示するというそのユニークな特徴により、プロフェッショナルなフィルム産業、ＭＴＶビデオ、及び、その他の特定のビデオ分野において幅広く用いられてきた。また、ロング・ショットのビデオ編集を行うことは容易である。なぜなら、ロング・ショットから短いクリップを切り出すことができるが、短いクリップからロング・ショットを生成するのは容易ではないからである。しかし、高品質のロング・ショットのビデオを撮影するには、カメラの動きと撮影対象のオブジェクトとを、長時間にわたって正確に連係させる必要があり、これは通常、プロフェッショナルにとってさえ困難である。
【０１９０】
長回しビデオやワンショット・ビデオとしても知られるロング・ショットのビデオとは、継続時間が比較的長いビデオ・ショットを意味する。
【０１９１】
本実施の形態で示す画像処理装置は、複数のビデオクリップから一貫性のあるビデオクリップのグループを効率的に検索し、かつ、オブジェクトの高度なマッチング技術により、ビデオクリップ間において、自然に結合することができるビデオ合成技術を提示し、見た目にも魅力的なワンショット・プレゼンテーションを実現するものである。つまり、この画像処理装置を用いることで、ショート・ショットのビデオからロング・ショットのビデオを容易に生成することができる。
【０１９２】
１．５  補足
（１）本発明の一態様である、画像処理装置は、動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理手段と、前記第１処理手段で検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理手段とを備えることを特徴とする。
【０１９３】
この構成によると、画像処理装置は、生成した情報を用いることで、第２部分コンテンツと、複数の部分コンテンツのうち類似度が最も高い第３部分コンテンツとの結合を可能としている。そのため、結合されたコンテンツを再生すると類似する部分で繋がっているので視聴する側は違和感なく視聴することができる。また、結合の際には、第１部分コンテンツをも含んでいるので、第１部分コンテンツを含むコンテンツのストーリー性は維持されている。
【０１９４】
なお、前記第１処理手段が、上記実施の形態の検出処理部１１に相当する。また、前記第２処理手段が、上記実施の形態のグラフ生成部１２及び連結ビデオ生成部１３の組み合わせに相当する。
【０１９５】
（２）ここで、前記第１処理手段は、前記複数のコンテンツそれぞれについて、所定の特徴変換法により、当該コンテンツと、前記複数のコンテンツに含まれる他のコンテンツとのフレーム類似度を算出し、当該フレーム類似度に基づいて、概要レベルで当該コンテンツと類似する前記検出対象コンテンツを特定するとしてもよい。
【０１９６】
この構成によると、画像処理装置は、所定の特徴変換法を用いることで、物体検出と比較して粗い類似検出を行うことができる。
【０１９７】
（３）ここで、前記所定の特徴変換法は、Ｐａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇ手法であり、前記第１処理手段は、前記複数のコンテンツそれぞれについて、当該コンテンツに含まれる全てのフレームに対してＰａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇアルゴリズムを施し、前記全てのフレームそれぞれのハッシュ値を算出し、当該コンテンツについて算出された各ハッシュ値と、前記複数のコンテンツに含まれる残りのコンテンツそれぞれについて算出された各ハッシュ値との一致数により、前記残りのコンテンツから当該コンテンツと類似する前記検出対象コンテンツを特定するとしてもよい。
【０１９８】
この構成によると、画像処理装置は、Ｐａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇアルゴリズムを用いた粗い類似検出を行うことにより、当該コンテンツと類似する検出対象コンテンツを高速に検出することができる。
【０１９９】
（４）ここで、前記第２部分コンテンツは、当該コンテンツの終了部位に含まれており、前記検出対象コンテンツにおける前記複数の部分コンテンツは、当該検出対象コンテンツの開始部位を構成しているとしてもよい。
【０２００】
この構成によると、第２部分コンテンツをコンテンツの終了部位に含まれるとすることで、連結後には第２部分コンテンツに先行する部分の存在を、前記複数の部分コンテンツが開始部分コンテンツを構成することで、連結後には第３部分コンテンツに後続する部分の存在を確かなものとすることができる。そのため、各コンテンツのストーリー性の維持を確実なものとすることができる。
【０２０１】
（５）ここで、前記第２部分コンテンツの再生時間と、前記複数の部分コンテンツそれぞれの再生時間とは、同一時間長であり、前記第１処理手段は、前記第２部分コンテンツに含まれる所定枚数のフレームそれぞれについて、前記複数の部分コンテンツそれぞれに含まれる各フレームとのフレーム類似度を算出し、前記フレーム類似度を用いて、前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出するとしてもよい。
【０２０２】
この構成によると、画像処理装置は、類似度を検出する際に、基準となる第２部分コンテンツと、検出対象となる前記複数の部分コンテンツとの再生時間が同じとすることで、正確な類似度を検出することができる。
【０２０３】
（６）ここで、前記第２部分コンテンツにおける前記所定枚数のフレームは、前記第２部分コンテンツの開始位置から等間隔に存在するとしてもよい。
【０２０４】
この構成によると、画像処理装置は、類似度を検出する際に用いられる所定枚数のフレームを等間隔で存在するものとしているので、第２部分コンテンツから万遍なく類似度を検出することができる。
【０２０５】
（７）ここで、前記第２処理手段が生成する前記情報は、前記複数のコンテンツそれぞれについて、当該コンテンツと、当該コンテンツの連結先であるコンテンツとの関係を示すグラフであるとしてもよい。
【０２０６】
この構成によると、画像処理装置は、連結を行う際のコンテンツ間の関係をグラフ化することで、連結対象となるコンテンツを容易に特定することができる。ま
（８）ここで、前記第２処理手段は、前記複数のコンテンツそれぞれについて当該コンテンツと、当該コンテンツの第２部分コンテンツと類似する前記第３部分コンテンツを含むコンテンツとに対してエッジで関連付けがされ、当該エッジに対して前記第２部分コンテンツと前記第３部分コンテンツとの類似度に応じた重みが付加された有向重み付グラフを生成し、前記エッジそれぞれに付された前記重みに基づいて、前記有向重み付グラフから前記複数のコンテンツに含まれる第１コンテンツから第２コンテンツまでの経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツの組それぞれに対して、当該組におけるエッジの派生元のコンテンツに含まれる前記第１部分コンテンツ及び前記第２部分コンテンツと、エッジの派生先であるコンテンツに含まれる前記第３部分コンテンツとを連結するとしてもよい。
【０２０７】
この構成によると、画像処理装置は、経路上に存在するコンテンツを連結するので、類似性のあるコンテンツについて視聴することができるので、ユーザーは類似性のあるコンテンツの視聴を効率的に行うことができる。
【０２０８】
（９）ここで、前記第２処理手段は、さらに、前記経路を検出すると、検出した前記経路に存在する各エッジに対する重みに対して他の経路検出時において当該経路に存在する各コンテンツが検出対象外となるよう当該重みの値を補正し、前記経路検出及び前記補正を、検出された経路に対するエッジの重みの合計値が所定値以下となるまで繰り返すとしてもよい。
【０２０９】
この構成によると、画像処理装置は、一度検出された経路上に存在するコンテンツを再度の検出により検出される他の最長経路に含めることはない。そのため、ユーザーは経路に存在するコンテンツからなる連結コンテンツを視聴した後、他の経路に存在するコンテンツからなる他の連結コンテンツを視聴する際には、先に視聴した連結コンテンツに含まれるコンテンツを視聴することはないので、効率よく視聴できる。
【０２１０】
（１０）ここで、前記第２処理手段は、ユーザーから指定された一のコンテンツが、開始位置、終了位置及び経路途中に存在するよう前記経路を検出するとしてもよい。
【０２１１】
または、前記第２処理手段は、ユーザーから２つ以上のコンテンツからなるコンテンツグループが指定された場合、前記コンテンツグループを含む前記２つ以上のコンテンツ全てを通過する前記経路を検出するとしてもよい。
【０２１２】
または、前記第２処理手段は、ユーザーからオブジェクトが指定された場合、指定された前記オブジェクトを含む２つのコンテンツを特定し、特定した一のコンテンツを前記第１コンテンツとし、特定した他のコンテンツを前記第２コンテンツとして前記経路を特定するとしてもよい。
【０２１３】
これらの構成によると、画像処理装置は、ユーザーから指定されたコンテンツ、コンテンツグループ及びオブジェクトを含むよう連結コンテンツを生成するので、ユーザーは自身が所望する類似性を有する連結コンテンツを視聴することができる。
【０２１４】
（１１）ここで、前記第２処理手段は、前記第１部分コンテンツ、前記第２部分コンテンツ、前記第３部分コンテンツ、及び前記検出対象コンテンツに含まれ、且つ前記第３部分コンテンツに時間的に後続する第４部分コンテンツの順に連結して１つの連結コンテンツを生成するとしてもよい。
【０２１５】
この構成によると、画像処理装置は、各コンテンツのストーリー性を維持させて連結コンテンツを生成することができる。なぜなら、連結コンテンツは、類似する部分だけでなく、第２部分コンテンツに先行する第１部分コンテンツ及び、第３部分コンテンツに後続する第４部分コンテンツを含んでいるからである。従って、視聴者は、連結コンテンツが生成元となる各コンテンツのストーリーを把握するとともに、繋がり部分に違和感を抱くことなく、連結コンテンツを視聴することができる。
【０２１６】
（１２）ここで、前記第１処理手段は、さらに、前記コンテンツの前記第２部分コンテンツと前記第３部分コンテンツとから、一致するオブジェクトが存在するフレームを検出し、前記第２処理手段は、前記オブジェクトが存在する前記第２部分コンテンツの第１フレームと前記第３部分コンテンツの第２フレームとにおいて、当該オブジェクトが存在する一致領域を検出し、前記第１フレーム及び前記第１フレームの前方に所定枚数分連続して存在するフレームからなる第１フレーム群について前記一致領域に含まれる前記オブジェクトに対してズームイン手法による画像処理を施し、前記第２フレーム及び前記第２フレームの後方に所定枚数分連続して存在するフレームからなる第２フレーム群について前記一致領域に含まれる前記オブジェクトに対してズームアウト手法による画像処理を施し、前記第１フレームと前記第２フレームとの間で、モーフィング処理を施して１つ以上の中間フレームを生成し、前記第１フレーム群、前記第２フレーム群及び前記１つ以上の中間フレームについて、前記オブジェクトを含む領域を除く残りの領域に対してフェザリング処理を施し、各処理が施された後に前記第１フレームと前記第２フレームとの間に、フェザリング処理が施された前記１つ以上の中間フレームを配置して連結することで前記連結コンテンツを生成するとしてもよい。
【０２１７】
この構成によると、画像処理装置は、連結する箇所にズームイン、ズームアウト、モーフィング、及びフェザリングを施すので、単に連結する場合よりも連結箇所の画像の変化を滑らかなものすることができる。
【０２１８】
（１３）ここで、前記第１処理手段は、前記第２部分コンテンツ及び前記第３部分コンテンツに対して、共通パターン検出処理、顔検出処理、人体検出処理及びこれらの組み合わせの処理の何れかを施して、前記一致するオブジェクトを検出するとしてもよい。
【０２１９】
この構成によると、画像処理装置は、共通パターン検出処理、顔検出処理、人体検出処理及びこれら組み合わせの処理の何れかを施すことで、一致するオブジェクトを確実に検出することができる。
【産業上の利用可能性】
【０２２０】
本発明における画像処理装置は、複数のビデオを１つのビデオに編集する際に有効である。
【符号の説明】
【０２２１】
１    画像処理装置
１０    ビデオ記憶部
１１    検出処理部
１２    グラフ生成部
１３    連結ビデオ生成部
１００    第１検出部
１０１    第２検出部
１０２    マッチング処理部
１１０    共通パターン検出部
１１１    人物検出部
１１２    顔検出部
１２０    グラフ構成処理部
１２１    エッジ剪定部
１２２    経路検出部
【図１】
2012137493.tif 000007
【図２】
2012137493.tif 000008
【図３】
2012137493.tif 000009
【図４】
2012137493.tif 000010
【図５】
2012137493.tif 000011
【図６】
2012137493.tif 000012
【図７】
2012137493.tif 000013
【図８】
2012137493.tif 000014
【図９】
2012137493.tif 000015
【図１０】
2012137493.tif 000016
【図１１】
2012137493.tif 000017
【図１２】
2012137493.tif 000018
【図１３】
2012137493.tif 000019
【図１４】
2012137493.tif 000020
【図１５】
2012137493.tif 000021
【手続補正書】
【提出日】平成24年8月27日(2012.8.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理手段と、
前記第１処理手段で検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理手段とを備え、
前記第２処理手段が生成する前記情報は、前記複数のコンテンツそれぞれについて、当該コンテンツと、当該コンテンツの連結先であるコンテンツとの関係を示すグラフであり、
前記第２処理手段は、さらに、生成した前記グラフを用いて、前記複数のコンテンツに含まれる第１コンテンツから第２コンテンツまでの経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツを連結する
ことを特徴とする画像処理装置。
【請求項２】
前記第１処理手段は、
前記複数のコンテンツそれぞれについて、所定の特徴変換法により、当該コンテンツと、前記複数のコンテンツに含まれる他のコンテンツとのフレーム類似度を算出し、当該フレーム類似度に基づいて、概要レベルで当該コンテンツと類似する前記検出対象コンテンツを特定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記所定の特徴変換法は、Ｐａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇ手法であり、
前記第１処理手段は、
前記複数のコンテンツそれぞれについて、当該コンテンツに含まれる全てのフレームに対してＰａｒｔｉｔｉｏｎ  Ｍｉｎ−Ｈａｓｈｉｎｇアルゴリズムを施し、前記全てのフレームそれぞれのハッシュ値を算出し、
当該コンテンツについて算出された各ハッシュ値と、前記複数のコンテンツに含まれる残りのコンテンツそれぞれについて算出された各ハッシュ値との一致数により、前記残りのコンテンツから当該コンテンツと類似する前記検出対象コンテンツを特定する
ことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記第２部分コンテンツは、当該コンテンツの終了部位に含まれており、
前記検出対象コンテンツにおける前記複数の部分コンテンツは、当該検出対象コンテンツの開始部位を構成している
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記第２部分コンテンツの再生時間と、前記複数の部分コンテンツそれぞれの再生時間とは、同一時間長であり、
前記第１処理手段は、
前記第２部分コンテンツに含まれる所定枚数のフレームそれぞれについて、前記複数の部分コンテンツそれぞれに含まれる各フレームとのフレーム類似度を算出し、前記フレーム類似度を用いて、前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記第２部分コンテンツにおける前記所定枚数のフレームは、前記第２部分コンテンツの開始位置から等間隔に存在する
ことを特徴とする請求項５に記載の画像処理装置。
【請求項７】
前記第２処理手段は、
前記複数のコンテンツそれぞれについて当該コンテンツと、当該コンテンツの第２部分コンテンツと類似する前記第３部分コンテンツを含むコンテンツとに対してエッジで関連付けがされ、当該エッジに対して前記第２部分コンテンツと前記第３部分コンテンツとの類似度に応じた重みが付加された有向重み付グラフを生成し、
前記エッジそれぞれに付された前記重みに基づいて、前記有向重み付グラフから前記第１コンテンツから前記第２コンテンツまでの前記経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツの組それぞれに対して、当該組におけるエッジの派生元のコンテンツに含まれる前記第１部分コンテンツ及び前記第２部分コンテンツと、エッジの派生先であるコンテンツに含まれる前記第３部分コンテンツとを連結する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項８】
前記第２処理手段は、
前記エッジそれぞれに付された前記重みを反転させ、前記重みが反転された有向重み付グラフにおける最短経路問題により、前記経路を検出する
ことを特徴とする請求項７に記載の画像処理装置。
【請求項９】
前記第２処理手段は、さらに、
前記経路を検出すると、検出した前記経路に存在する各エッジに対する重みに対して他の経路検出時において当該経路に存在する各コンテンツが検出対象外となるよう当該重みの値を補正し、
前記経路検出及び前記補正を、検出された経路に対するエッジの重みの合計値が所定値以下となるまで繰り返す
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１０】
前記第２処理手段は、
ユーザーから指定された一のコンテンツが、開始位置、終了位置及び経路途中に存在するよう前記経路を検出する
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１１】
前記第２処理手段は、
ユーザーから２つ以上のコンテンツからなるコンテンツグループが指定された場合、前記コンテンツグループを含む前記２つ以上のコンテンツ全てを通過する前記経路を検出する
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１２】
前記第２処理手段は、
ユーザーからオブジェクトが指定された場合、指定された前記オブジェクトを含む２つのコンテンツを特定し、特定した一のコンテンツを前記第１コンテンツとし、特定した他のコンテンツを前記第２コンテンツとして前記経路を特定する
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１３】
前記第２処理手段は、
前記第１部分コンテンツ、前記第２部分コンテンツ、前記第３部分コンテンツ、及び前記検出対象コンテンツに含まれ、且つ前記第３部分コンテンツに時間的に後続する第４部分コンテンツの順に連結して１つの連結コンテンツを生成する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１４】
前記第１処理手段は、さらに、
前記コンテンツの前記第２部分コンテンツと前記第３部分コンテンツとから、一致するオブジェクトが存在するフレームを検出し、
前記第２処理手段は、
前記オブジェクトが存在する前記第２部分コンテンツの第１フレームと前記第３部分コンテンツの第２フレームとにおいて、当該オブジェクトが存在する一致領域を検出し、
前記第１フレーム及び前記第１フレームの前方に所定枚数分連続して存在するフレームからなる第１フレーム群について前記一致領域に含まれる前記オブジェクトに対してズームイン手法による画像処理を施し、前記第２フレーム及び前記第２フレームの後方に所定枚数分連続して存在するフレームからなる第２フレーム群について前記一致領域に含まれる前記オブジェクトに対してズームアウト手法による画像処理を施し、
前記第１フレームと前記第２フレームとの間で、モーフィング処理を施して１つ以上の中間フレームを生成し、
前記第１フレーム群、前記第２フレーム群及び前記１つ以上の中間フレームについて、前記オブジェクトを含む領域を除く残りの領域に対してフェザリング処理を施し、
各処理が施された後に前記第１フレームと前記第２フレームとの間に、フェザリング処理が施された前記１つ以上の中間フレームを配置して連結することで前記連結コンテンツを生成する
ことを特徴とする請求項１３に記載の画像処理装置。
【請求項１５】
前記第１処理手段は、
前記第２部分コンテンツ及び前記第３部分コンテンツに対して、共通パターン検出処理、顔検出処理、人体検出処理及びこれらの組み合わせの処理の何れかを施して、前記一致するオブジェクトを検出する
ことを特徴とする請求項１４に記載の画像処理装置。
【請求項１６】
画像処理装置で用いられる画像処理方法であって、
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理ステップと、
前記第１処理ステップで検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理ステップとを含み、
前記第２処理ステップが生成する前記情報は、前記複数のコンテンツそれぞれについて、当該コンテンツと、当該コンテンツの連結先であるコンテンツとの関係を示すグラフであり、
前記第２処理ステップは、さらに、生成した前記グラフを用いて、前記複数のコンテンツに含まれる第１コンテンツから第２コンテンツまでの経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツを連結する
ことを特徴とする画像処理方法。
【請求項１７】
画像処理装置で用いられる画像処理プログラムであって、
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理ステップと、
前記第１処理ステップで検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理ステップとを含み、
前記第２処理ステップが生成する前記情報は、前記複数のコンテンツそれぞれについて、当該コンテンツと、当該コンテンツの連結先であるコンテンツとの関係を示すグラフであり、
前記第２処理ステップは、さらに、生成した前記グラフを用いて、前記複数のコンテンツに含まれる第１コンテンツから第２コンテンツまでの経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツを連結する
ことを特徴とする画像処理プログラム。
【請求項１８】
画像処理装置で用いられる集積回路であって、
動画像に係る複数のコンテンツそれぞれについて、当該コンテンツに含まれる第１部分コンテンツに時間的に後続する第２部分コンテンツと、前記複数のコンテンツのうち当該コンテンツとは異なる検出対象コンテンツの一部を構成し、時間的に連続する複数の部分コンテンツとの類似度を検出し、当該複数の部分コンテンツのうち前記第２部分コンテンツとの類似度が高い第３部分コンテンツを検出する第１処理手段と、
前記第１処理手段で検出された前記第２部分コンテンツと前記第３部分コンテンツとの類似度を用いて、前記第１部分コンテンツ、前記第２部分コンテンツ及び前記第３部分コンテンツとを連結するための関係を示す情報を生成する第２処理手段とを備え、
前記第２処理手段が生成する前記情報は、前記複数のコンテンツそれぞれについて、当該コンテンツと、当該コンテンツの連結先であるコンテンツとの関係を示すグラフであり、
前記第２処理手段は、さらに、生成した前記グラフを用いて、前記複数のコンテンツに含まれる第１コンテンツから第２コンテンツまでの経路を検出し、検出された前記経路上に存在する各コンテンツのうち隣り合うコンテンツを連結する
ことを特徴とする集積回路。
【国際調査報告】
2012137493.tif 000022
2012137493.tif 000023
2012137493.tif 000024
2012137493.tif 000025
2012137493.tif 000026
2012137493.tif 000027
2012137493.tif 000028
2012137493.tif 000029