(57)【特許請求の範囲】
【請求項１】
ビデオ処理装置であって、
ビデオシーンセット中の各ビデオシーンの少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割する前処理ユニットであって、前記ビデオシーンセットの少なくとも一部のビデオシーンはラベル有りのビデオシーンである、前処理ユニットと、
前記ビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出する特徴抽出ユニットと、
前記シーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、前記フレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、前記領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成する重み付きグラフ形成ユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記各ビデオシーン中の各代表フレームのソフトラベル及び前記各代表フレーム中の各領域のソフトラベルを未知量とし、前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、及び、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、コスト関数を構築する関数構築ユニットと、
前記コスト関数の最適化問題を解くことにより、前記未知量の計算値を得る計算ユニットと、
前記未知量の計算値に基づいて、ビデオ処理を行うビデオ処理ユニットと、を含む、ビデオ処理装置。
【請求項２】
請求項1に記載のビデオ処理装置であって、
前記ビデオ処理装置は、ビデオ検索装置であり、
前記ビデオシーンセットは、ラベル有りの検索ビデオシーンを含み、
前記ビデオ処理ユニットは、前記未知量の計算値に基づいて、前記ビデオシーンセット中の前記検索ビデオシーン以外の、前記検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンを検索結果として判定する、ビデオ処理装置。
【請求項３】
請求項2に記載のビデオ処理装置であって、
前記ビデオシーンセット中の前記検索ビデオシーン以外の、前記検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンは、
そのソフトラベルが第一所定閾値よりも高いビデオシーンであって、該ビデオシーン中に最大ソフトラベルを有する代表フレームのソフトラベルが第二所定閾値よりも高く、且つ該代表フレーム中に最大ソフトラベルを有する領域のソフトラベルが第三所定閾値よりも高い、ビデオシーン、又は、
そのソフトラベル、その中に最大ソフトラベルを有する代表フレームのソフトラベル、及び該代表フレーム中に最大ソフトラベルを有する領域のソフトラベルの三者の重み付き和が最大である前のN個のビデオシーンであって、Nは正整数である、ビデオシーンである、ビデオ処理装置。
【請求項４】
請求項1に記載のビデオ処理装置であって、
前記ビデオ処理装置は、ビデオコンセプト検出装置であり、
前記ビデオ処理ユニットは、前記未知量の計算値に基づいて、ラベル無しの対象ビデオシーンに前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを判定する、ビデオ処理装置。
【請求項５】
請求項4に記載のビデオ処理装置であって、
前記ビデオ処理ユニットは、
前記対象ビデオシーンが前記ビデオシーンセットに含まれているかどうかを判定する第一判定サブユニットと、
前記対象ビデオシーンが前記ビデオシーンセットに含まれていない場合、前記対象ビデオシーンの少なくとも1つの代表フレームを抽出し、前記対象ビデオシーンの各代表フレームを複数の領域に分割し、前記未知量の計算値に基づいて、前記対象ビデオシーンのソフトラベルの計算値、前記対象ビデオシーン中の各代表フレームのソフトラベルの計算値、及び前記対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を得る第一計算サブユニットと、
前記第一計算サブユニットにより得られた結果に基づいて、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値を計算する第二計算サブユニットと、
前記第二計算サブユニットにより算出された前記程度の値が第四所定閾値以上である場合、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいると判定し、前記程度の値が前記第四所定閾値よりも小さい場合、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいないと判定する第二判定サブユニットと、を含む、ビデオ処理装置。
【請求項６】
請求項1乃至5の何れか１つに記載のビデオ処理装置であって、
前記関数構築ユニットは、
前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、２つのビデオシーンのシーンレベル視覚特徴が類似すればするほど、該２つのビデオシーンのソフトラベル間の差が小さいようにし、２つの代表フレームのフレームレベル視覚特徴が類似すればするほど、該２つの代表フレームのソフトラベル間の差が小さいようにし、及び、２つの領域の領域レベル視覚特徴が類似すればするほど、該２つの領域のソフトラベル間の差を小さいようにするという第一制約条件を設定する第一設定サブユニットと、
前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、負のラベルを持つビデオシーンのソフトラベル、負のラベルを持つビデオシーン中の全ての代表フレームのソフトラベル、及び負のラベルを持つビデオシーン中の全ての代表フレームの全ての領域のソフトラベルが-1にできるだけ接近するようにし、正のラベルを持つビデオシーンのソフトラベルが1にできるだけ接近するようにし、正のラベルを持つビデオシーンに最大ソフトラベルを有する代表フレームのソフトラベルが、該代表フレームが属するビデオシーンのソフトラベルにできるだけ接近するようにし、及び、正のラベルのビデオシーン中の各可能な正例フレームに最大ソフトラベルを有する領域のソフトラベルが、該領域が属する代表フレームのソフトラベルにできるだけ接近するようにするという第二制約条件を設定する第二設定サブユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記ビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベル、及び前記ビデオシーンセット中の各ビデオシーンの各代表フレームの各領域のソフトラベルを未知量とし、前記第一制約条件及び前記第二制約条件に基づいて、コスト関数を構築する関数構築サブユニットと、を含む、ビデオ処理装置。
【請求項７】
請求項6に記載のビデオ処理装置であって、
前記可能な正例フレームは、
そのソフトラベルの値が第五所定閾値よりも高いフレーム、又は、
その中にソフトラベルが第六所定閾値よりも高い領域を含むフレームである、ビデオ処理装置。
【請求項８】
請求項1乃至7の何れか１つに記載のビデオ処理装置であって、
前記計算ユニットは、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル及び前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルに初期値を与える初期化サブユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの現在値に基づいて、前記コスト関数を制約付き最小化問題に変換し、CCCP（constrained  concave  convex  procedure）を用いて該制約付き最小化問題を解き、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を求める第三計算サブユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値に基づいて、前記コスト関数を制約付き最小化問題に変換し、CCCPを用いて該制約付き最小化問題を解き、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの計算値を求める第四計算サブユニットと、
前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値に基づいて、前記コスト関数を用いて計算を行い、前記ビデオシーンセット中の各ビデオシーンのソフトラベルの計算値を求める第五計算サブユニットと、
第三計算サブユニット、第四計算サブユニット及び第五計算サブユニットがそれぞれ一回の計算を順次行った後に、前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベル、及び前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値が収斂になっているかどうかを判断する第三判定サブユニットであって、前者の場合、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの現在値を前記コスト関数中の未知量の計算値として保存し、後者の場合、前記第三判定サブユニットにより前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの現在値が収斂になっていると判断するまでに、再び第三計算サブユニット、第四計算サブユニット及び第五計算サブユニットをそれぞれ順次用いて次の反復計算を行う、第三判定サブユニットと、を含む、ビデオ処理装置。
【請求項９】
ビデオ処理方法であって、
ビデオシーンセット中の各ビデオシーンの少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割する前処理ステップであって、前記ビデオシーンセットの少なくとも一部のビデオシーンはラベル有りのビデオシーンである、前処理ステップと、
前記ビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出する特徴抽出ステップと、
前記シーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、前記フレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、前記領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成するグラフ形成ステップと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記各ビデオシーン中の各代表フレームのソフトラベル、及び前記各代表フレーム中の各領域のソフトラベルを未知量とし、前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、及び、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、コスト関数を構築する関数構築ステップと、
前記コスト関数の最適化問題を解き、前記未知量の計算値を得る未知量計算ステップと、
得られた前記未知量の計算値に基づいて、ビデオ処理を行うビデオ処理ステップと、を含む、ビデオ処理方法。
【請求項１０】
請求項1乃至8の何れか１つに記載のビデオ処理装置を含む設備。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ処理分野に関し、特に、ビデオ処理装置、ビデオ処理方法及び設備に関する。
【背景技術】
【０００２】
デジタルビデオの数の急激な増加に伴い、有効なビデオ処理技術の研究開発が必要になっている。通常、従来の幾つかのビデオ処理技術では、ユーザにより複数のトレーニングビデオシーン（訓練ビデオシーンとも称される）を提供し、そして、これらのトレーニングビデオシーンに基づいてそれ相応のビデオ処理を行うことを要する。そのうち、トレーニングビデオシーンは、ラベル（タグとも称される）有り（ラベルが付いている）のビデオシーン及びラベル無し（ラグが付かない）のビデオシーンを含む可能性があり、また、ラベル有りのビデオシーンは、通常、正例のビデオシーン（即ち、正のラベルが付いているビデオシーン）及び負例のビデオシーン（即ち、負のラベルが付いているビデオシーン）を含む。トレーニングビデオシーンの種類（タイプ）に基づいて、これらのビデオ処理技術は、監督型（supervised）ビデオ処理技術及び半監督型（semi-supervised）ビデオ処理技術の２種類に分けることができる。
【０００３】
監督型ビデオ処理技術について言えば、それが採用するトレーニングビデオシーンは、全て、ラベル有りのビデオシーンである。しかし、ラベル有りのビデオシーンの数は、通常、限られているので、この技術を利用して行った処理は、通常、効果が比較的に劣り、且つ、ラベル無しのビデオシーン中の情報を有効に利用することができない。
【０００４】
半監督型ビデオ処理技術について言えば、それが採用するトレーニングビデオシーンは、ラベル有りのビデオシーン及びラベル無しのビデオシーンの両方を含む。監督型ビデオ処理技術に比べ、半監督型ビデオ処理技術は、ラベル無しのビデオシーンに含まれる情報を有効に利用することができる。しかし、従来の半監督型ビデオ処理技術では、大多数がシーンレベル（scene-level又はscene-based）重み付きグラフのみ又はフレームレベル（frame-level又はframe-based）重み付きグラフのみを利用して行うビデオ処理技術である。また、シーンレベル重み付きグラフ及びフレームレベル重み付きグラフを同時に利用する幾つかの技術があっても、それらは、２種類の重み付きグラフをそれぞれ単独で利用して計算を行い、そして、両者の計算結果を簡単に結びつけるだけであり、計算処理の過程において両者間の関係を考慮していないので、処理効果が比較的に劣る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術中の上述の問題に鑑み、本発明の主な目的は、少なくとも、従来の監督型ビデオ処理技術及び半監督型ビデオ処理技術に存在するビデオ処理の処理効果が劣る問題を解決できるビデオ処理装置、ビデオ処理方法及び設備を提供することにある。
【課題を解決するための手段】
【０００６】
上述の目的を達成するために、本発明の一側面によれば、ビデオ処理装置が提供される。このビデオ処理装置は、ビデオシーンセット中の各ビデオシーンの少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割する前処理ユニットであって、前記ビデオシーンセットの少なくとも一部のビデオシーンはラベル有りのビデオシーンである、前処理ユニット；前記ビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル（region-level又はregion-based）視覚特徴を抽出する特徴抽出ユニット；前記シーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、前記フレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、前記領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成する重み付きグラフ形成ユニット；前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記各ビデオシーン中の各代表フレームのソフトラベル及び前記各代表フレーム中の各領域のソフトラベルを未知量とし、前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、及び、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、コスト関数を構築する関数構築ユニット；前記コスト関数の最適化問題を解くことにより、前記未知量の計算値を得る計算ユニット；及び、前記計算ユニットにより得られた計算値に基づいて、ビデオ処理を行うビデオ処理ユニットと、を含む。
【０００７】
開示の技術よれば、次のような利点の少なくとも1つを実現することができ、即ち、３種類の重み付きグラフによりビデオシーンの特徴情報を十分に利用し、３種類の重み付きグラフ間の関係を十分に探り出すことで、比較的よいビデオ処理の処理効果を取得し得ること；ラベル有りのビデオシーンを利用した上で、さらにラベル無しのビデオシーンを使用し、ビデオ処理を実現することで、ビデオ処理の処理効果を向上させ得ること；ビデオ検索の検索結果をより正確に取得し得ること；及び、ビデオのコンセプト検出結果をより正確に取得し得ることである。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施例によるビデオ処理装置の例示的な構造のブロック図である。
【図２】図1における重み付きグラフ形成ユニットの例示的な構造のブロック図である。
【図３】図1における関数構築ユニットの例示的な構造のブロック図である。
【図４】図1における計算ユニットの例示的な構造のブロック図である。
【図５】図1におけるビデオ処理ユニットの例示的な構造のブロック図である。
【図６】本発明の実施例によるビデオ処理方法の例示的な処理のフローチャートである。
【図７】図6に示すようなステップS660の例示的な処理のフローチャートである。
【図８】ビデオ処理がビデオのコンセプト検出である場合に、図6に示すステップS670の例示的な処理のフローチャートである。
【図９】本発明の実施例によるビデオ処理装置及びビデオ処理方法を実現し得る例示的な情報処理装置のハードウェア配置を示す図である。
【発明を実施するための形態】
【０００９】
以下、添付した図面を参照しながら本発明の好適な実施形態について説明する。
【００１０】
上述のように、従来技術中の監督型又は半監督型ビデオ処理技術では、ビデオシーンに対して処理を行う時に、上述の原因により、処理効果が比較的に劣ることを引き起こすことがある。ビデオ処理の効果を改善するために、本発明は、ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を同時に利用することができるビデオ処理装置を提供する。これにより、ビデオシーン中の情報を十分に利用することで、ビデオシーンの特徴、及び、ビデオシーンとビデオシーンとの間の関係をよりよく反映することができる。
【００１１】
かかるビデオ処理装置は、ビデオシーンセット（ビデオシーン集とも称される）中の各ビデオシーンの少なくとも１つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割するための前処理ユニットであって、このビデオシーンセット中の少なくとも一部のビデオシーンはラベル有りのビデオシーンである、前処理ユニット；上述のビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出するための特徴抽出ユニット；上述のシーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、上述のフレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、上述の領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成するための重み付きグラフ形成ユニット；上述のビデオシーンセット中の各ビデオシーンのソフトラベル（soft  label）、上述の各ビデオシーン中の各代表フレームのソフトラベル及び上述の各代表フレーム中の各領域のソフトラベルを未知量とし、上述のシーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの構造情報と、上述の各ビデオシーンのソフトラベル、上述の各代表フレームのソフトラベル及び上述の各領域のソフトラベルの三者間の関係と、に基づいて、コスト関数を構築するための関数構築ユニット；このコスト関数の最適化問題を解くことにより、上述の未知量の計算値を取得するための計算ユニット；及び、計算ユニットが取得した計算値によりビデオ処理を行うためのビデオ処理ユニットを含む。
【００１２】
次に、図1〜図5を参照して、本発明の実施例によるビデオ処理装置について説明する。
【００１３】
図1は、本発明の実施例によるビデオ処理装置100の１つの例示的な構造を示すブロック図である。図1に示すように、本発明の実施例によるビデオ処理装置100は、前処理ユニット110、特徴抽出ユニット120、重み付きグラフ形成ユニット130、関数構築ユニット140、計算ユニット150及びビデオ処理ユニット160を含む。
【００１４】
図1に示すように、ビデオ処理装置100中の前処理ユニット110は、ビデオシーンセット中の各ビデオシーンから、少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームに対して画像分割を行い、即ち、抽出した各ビデオシーンの各代表フレームをそれぞれ複数の領域に分割するために用いられる。そのうち、各ビデオシーンから抽出した代表フレームは、このビデオシーン中の任意の１つのフレーム又は任意の複数のフレームであってよく、従来の幾つかのフレーム抽出方法のうちの１つにより抽出したフレームであってもよい。また、ここで言う画像分割は、従来技術中の任意の画像分割方法により実現されてもよいので、ここでは、その説明を省略する。また、上述のビデオシーンセットは、複数のビデオシーンを含んでもよく、且つこれらのビデオシーン中の少なくとも一部のビデオシーンは、ラベル有りのビデオシーンである。言い換えると、このビデオシーンセット中のビデオシーンは、全てがラベル有りのビデオシーンであってもよく、一部がラベル有りのビデオシーンであり、残りの部分がラベル無しのビデオシーンであってもよい。そのうち、上述のラベル有りのビデオシーンは、正のラベルが付いているビデオシーン（以下、“正例ビデオシーン”と略称される）であってもよく、負のラベルが付いているビデオシーン（以下、“負例ビデオシーン”と略称される）であってもよい。なお、ここで言うビデオシーンが所持する“ラベル”（ハードラベル（hard  label）とも称される）は、１種の注釈情報であり、通常、例えば、ユーザにより予めオブジェクト（例えば、ビデオシーン）に注釈された、このオブジェクトの種類を表す１種の情報である。そのうち、正のラベルを所持するビデオシーン（即ち、正のハードラベルを所持するビデオシーン）は、通常、特定の種類に属するビデオシーンであり、負のラベルを所持するビデオシーン（即ち、負のハードラベルを所持するビデオシーン）は、通常、特定の種類に属しないビデオシーンである。例えば、正のラベルは、“A”の形式であってもよく、その対応する負のラベルは、“非A”の形式であってもよい。そのうち、1つの簡単な例は、“A”が“虎”であり、即ち、正のラベルを所持するビデオシーンは、ラベルが“虎”のビデオシーン（これらのビデオシーンは、“虎”の種類に属し、これらのビデオシーンに“虎”が含まれていることを表す）であり、負のラベルを所持するビデオシーンは、ラベルが“非虎”のビデオシーン（これらのビデオシーンは、“虎”の種類に属せず、これらのビデオシーンに“虎”が含まれていないことを表す）である。
【００１５】
なお、ビデオシーンセット中の各ビデオシーンから抽出した代表フレームの数は、同じであってもよく、異なってもよい。また、画像分割により、このビデオシーンセット中の各ビデオシーンの代表フレームを複数の領域に分割してもよいが、各代表フレームの分割後に得られた領域の数は、同じであってよく、異なってもよい。
【００１６】
その後、特徴抽出ユニット120により、上述のビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出する。そのうち、各ビデオシーンのシーンレベル視覚特徴とは、シーンレベル上で抽出したこのビデオシーンの視覚特徴のことを指し、各ビデオシーンのフレームレベル視覚特徴とは、フレームレベル上で抽出したこのビデオシーンの視覚特徴のことを指し、各ビデオシーンの領域レベル視覚特徴とは、領域レベル上で抽出したこのビデオシーンの視覚特徴のことを指す。そのうち、ここで言う“視覚特徴”とは、ビデオシーンの内容を一定程度反映することができる情報のことを指し、例えば、色特徴、テクスチャー特徴及び形状特徴などの視覚特徴中の任意の１つであってもよく、そのうちの任意の複数の組み合わせであってもよい。また、従来技術に存在する各種の視覚特徴の抽出方法は、全て、本発明に用いることができるので、ここでは、その説明を省略する。
【００１７】
特徴抽出ユニット120が抽出した上述のビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴に基づいて、重み付きグラフ形成ユニット130は、３種類の重み付きグラフを形成することができる。具体的には、重み付きグラフ形成ユニット130は、特徴抽出ユニット120が抽出した各ビデオシーンのシーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、特徴抽出ユニット120が抽出した各ビデオシーンのフレームレベル視覚特徴（即ち、各フレームの視覚特徴）に基づいてフレームレベル重み付きグラフを形成し、特徴抽出ユニット120が抽出した各ビデオシーンの領域レベル視覚特徴（即ち、各領域の視覚特徴）に基づいて領域レベル重み付きグラフを形成することができる。
【００１８】
本発明の実施例によるビデオ処理装置の１つの実現方式では、図1に示すような重み付きグラフ形成ユニット130は、図2に示すような構造を採用して実現されてもよい。図2は、図1における重み付きグラフ形成ユニット130の１つの例示的な構造を示すブロック図である。図2に示すように、重み付きグラフ形成ユニット130は、第一形成サブユニット210、第二形成サブユニット220及び第三形成サブユニット230を含んでもよい。
【００１９】
そのうち、第一形成サブユニット210は、上述のシーンレベル重み付きグラフを形成するために用いられてもよく、例えば、上述のビデオシーンセット中の各ビデオシーンをノードとし、２つのノード間のシーンレベル視覚特徴上の類似度をこの２つのノード間の重み付き辺の重み値とし、このシーンレベル重み付きグラフを形成することができる。換言すると、第一形成サブユニット210が形成したシーンレベル重み付きグラフでは、各ノードが、それぞれ、上述のビデオシーンセット中の1つのビデオシーンを表し、２つのノードが繋がる重み付き辺の重み値が、この２つのノードが対応する２つのビデオシーン間のシーンレベル視覚特徴に基づく類似度を表す。そのうち、このシーンレベル重み付きグラフ中のノードは、ビデオシーンセット中のビデオシーンと１対１対応する。
【００２０】
同様に、第二形成サブユニット220は、上述のフレームレベル重み付きグラフを形成するために用いられてもよく、例えば、上述のビデオシーンセット中の各ビデオシーンの各代表フレームをノードとし、２つのノード間のフレームレベル視覚特徴上の類似度をこの２つのノード間の重み付き辺の重み値とし、このフレームレベル重み付きグラフを形成することができる。換言すると、第二形成サブユニット220が形成したフレームレベル重み付きグラフでは、各ノードが、それぞれ、上述のビデオシーンセット中の1つのビデオシーンの1つの代表フレームを表し、２つのノードが繋がる重み付き辺の重み値が、この２つのノードが対応する２つの代表フレーム間のフレームレベル視覚特徴に基づく類似度を表す。そのうち、このフレームレベル重み付きグラフ中のノードは、ビデオシーンセット中のビデオシーンの代表フレームと１対１対応する。
【００２１】
また、第三形成サブユニット230は、上述の領域レベル重み付きグラフを形成するために用いられてもよく、例えば、上述のビデオシーンセット中の各ビデオシーンの各代表フレームの各領域をノードとし、２つのノード間の領域レベル視覚特徴上の類似度をこの２つのノード間の重み付き辺の重み値とし、この領域レベル重み付きグラフを形成することができる。換言すると、第三形成サブユニット230が形成した領域レベル重み付きグラフでは、各ノードが、それぞれ、上述のビデオシーンセット中の1つのビデオシーンの1つの代表フレームの1つの領域を表し、２つのノードが繋がる重み付き辺の重み値が、この２つのノードが対応する２つの領域間の領域レベル視覚特徴に基づく類似度を表す。そのうち、この領域レベル重み付きグラフ中のノードは、ビデオシーンセット中のビデオシーンの代表フレームに含まれる領域と１対１対応する。
【００２２】
再び図1を参照する。重み付きグラフ形成ユニット130によりシーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフを形成した後に、関数構築ユニット140によりコスト関数を構築することができる。そのうち、このコスト関数では、未知量が、上述のビデオシーンセット中の各ビデオシーンのソフトラベル、上述のビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベル及び上述のビデオシーンセット中の各ビデオシーンの各代表フレームの各領域のソフトラベルである。その後、重み付きグラフ形成ユニット130が構築したシーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの構造情報と、上述のビデオシーンセット中の各ビデオシーンのソフトラベル、各ビデオシーンの代表フレームのソフトラベル及び各ビデオシーンの代表フレーム中の領域のソフトラベルの関係とに基づいて、コスト関数を構築することができる。
【００２３】
なお、ソフトラベルは、ハードラベルというコンセプトに相対して定義された1つのコンセプトである。ハードラベルは、往々にして真の注釈情報であり、通常は、予め所定のサンプル（例えば、ビデオシーン）に注釈されたサンプルの種類を反映する１種の情報である。一方、ソフトラベルは、１種のバーチャル注釈情報であり、通常は、このソフトラベルが属するオブジェクト（例えば、ビデオシーン、フレーム又は領域）が、所定のサンプル中のハードラベルが表す種類情報に符合する程度を反映する。一般的には、ソフトラベルを-1から1までの間の任意の実数（-1及び1を含む）にしてもよく、この場合は、ソフトラベルの値が1に接近すればするほど（即ち、大きければ大きいほど）、このソフトラベルが対応するオブジェクトが、所定のサンプル中の、正のラベルを持つオブジェクトの種類に属することを表し、これに反して、ソフトラベルの値が-1に接近すればするほど（即ち、小さければ小さいほど）、このソフトラベルが対応するオブジェクトが、所定のサンプル中の、正のラベルを持つオブジェクトの種類に属しないことを表す。換言すると、ソフトラベルの値が大きければ大きいほど、このソフトラベルが対応するオブジェクトが、上述の正のラベルを持つオブジェクトの種類に属する可能性が大きいことを表し、ソフトラベルの値が小さければ小さいほど、このソフトラベルが対応するオブジェクトが、上述の正のラベルを持つオブジェクトの種類に属する可能性が小さいことを表す。なお、ソフトラベルは、他の実数に設定されてもよく、例えば、1よりも大きい又は-1よりも小さい実数に設定されてもよく、この場合は、同様に、ソフトラベルの値が大きければ大きいほど、その対応するオブジェクトが、所定のサンプル中の、正のラベルを持つオブジェクトの種類に属することを表す。
【００２４】
例えば、所定のサンプルが正のラベルを持つビデオシーン及び負のラベルを持つビデオシーンを含み、且つ、上述の正のラベルを持つビデオシーンが、ラベルが“虎”のビデオシーンであり、及び上述の負のラベルを持つビデオシーンが、ラベルが“非虎”のビデオシーンである場合は、あるビデオシーンのソフトラベルが0.1であり、他のビデオシーンのソフトラベルが0.8であれば、ソフトラベルが0.8であるビデオシーンに虎が含まれる可能性が、ソフトラベルが0.1であるビデオシーンに虎が含まれる可能性よりも遥かに大きい。
【００２５】
具体的には、図3に示すような構造を採用して関数構築ユニット140の機能及び処理を実現することができる。図3は、図1における関数構築ユニット140の１つの例示な構造を示すブロック図である。
【００２６】
図3に示すように、関数構築ユニット140は、第一設定サブユニット310、第二設定サブユニット320及び関数構築サブユニット330を含んでもよい。そのうち、第一設定サブユニット310は、重み付きグラフ形成ユニット130が形成したシーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの構造情報に基づいて、第一制約条件を設定するために用いられ、第二設定サブユニット320は、上述のビデオシーンセット中のラベル有りのビデオシーンのソフトラベル、このビデオシーンセット中のラベル有りのビデオシーンの代表フレームのソフトラベル及びこの代表フレーム中の領域のソフトラベルの間の関係に基づいて、第二制約条件を設定するために用いられ、そして、関数構築サブユニット330は、上述の２つの制約条件に基づいて、コスト関数を構築するために用いられる。上述のように、このコスト関数中の未知量は、上述のビデオシーンセット中の各ビデオシーンのソフトラベル、このビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベル、及びこのビデオシーンセット中の各ビデオシーンの各代表フレーム中の各領域のソフトラベルである。
【００２７】
具体的には、上述の３種類の重み付きグラフの構造情報を考慮して、第一設定サブユニット310により、次のような第一制約条件を設定してもよく、即ち、２つのビデオシーンのシーンレベル視覚特徴が類似すればするほど、この２つのビデオシーンのソフトラベル間の差が小さいようにし；２つの代表フレームのフレームレベル視覚特徴が類似すればするほど、この２つの代表フレームのソフトラベル間の差が小さいようにし；及び、２つの領域の領域レベル視覚特徴が類似すればするほど、この２つの領域のソフトラベル間の差が小さいようにする。
【００２８】
また、上述のビデオシーンセット中のそれらのラベル有りのビデオシーンについては、負のラベルを持つビデオシーンのソフトラベルが-1にできるだけ接近するようにし、正のラベルを持つビデオシーンのソフトラベルが1にできるだけ接近するようにしてもよい。なぜなら、正のラベルを持つビデオシーン中に、ある特定種類の内容が含まれ、負のラベルを持つビデオシーン中に、この特定種類の内容が含まれないため、ソフトラベルを-1から1までの間の任意の実数にした場合、ビデオシーンのソフトラベルが1に接近すればするほど、このビデオシーンがこの特定種類の内容を含む可能性が大きく、ビデオシーンのソフトラベルが-1に接近すればするほど、このビデオシーンがこの特定種類の内容を含む可能性が小さいからである。例えば、ラベルが“非虎”（即ち、負のラベル）であるビデオシーンについては、このビデオシーンのソフトラベルが-1にできるだけ接近するようにし、これに反して、ラベルが“虎”（即ち、正のラベル）であるビデオシーンについては、このビデオシーンのソフトラベルが1にできるだけ接近するようにしてもよい。
【００２９】
上述の負のラベルを持つビデオシーンの代表フレームについて言えば、あるビデオシーンが負のラベルを所持すれば、このビデオシーンが上述の“特定種類の内容”を含まないことを表し、即ち、このビデオシーン中の任意のフレームに上述の“特定種類の内容”が含まれず、且つこのビデオシーン中の任意のフレーム中の任意の領域に上述“特定種類の内容”が含まれないことを表す。よって、上述の負のラベルを持つビデオシーン中の各代表フレームのソフトラベルが-1にできるだけ接近し、及び上述の負のラベルを持つビデオシーン中の各代表フレームの各領域のソフトラベルも-1にできるだけ接近するようにしてもよい。
【００３０】
一方、上述の正のラベルを持つビデオシーンの代表フレーム及びその中の領域について言えば、状況はもっと複雑である。
【００３１】
例えば、正のラベルを持つビデオシーンの代表フレームについて言えば、あるビデオシーンが正のラベルを所持すれば、このビデオシーンが上述の“特定種類の内容”を含むことを示し、即ち、このビデオシーン中の少なくとも1つのフレームに上述の“特定種類の内容”が含まれているが、その中のどのフレームにこの情報が含まれているかを確定できないことを表す。ビデオシーンの代表フレームのみを考慮する場合は、上述の正のラベルを持つビデオシーン中の少なくとも1つの代表フレームに上述の“特定種類の内容”が含まれていると認めてもよいが、その中のどの代表フレームにこの情報が含まれているかを確定することができない。あるビデオシーンが正のラベルを所持すれば、このビデオシーン中の、ソフトラベルが最大である代表フレームのみを考慮し、この代表フレームのソフトラベルがこのビデオシーンのソフトラベルにできるだけ接近するようにしてもよい。このように、シーンレベル重み付きグラフと、フレームレベル重み付きグラフとを互いに関連付けさせることができる。
【００３２】
また、上述のように、上述の正のラベルを持つビデオシーン中の少なくとも1つの代表フレームに上述の“特定種類の内容”が含まれていると認めた場合は、この“少なくとも1つの代表フレーム”中の各代表フレームに、それぞれ、上述の“特定種類の内容”を含む少なくとも1つの領域が存在する。上述の“少なくとも1つの代表フレーム”中の各代表フレームについては、この代表フレーム中の、ソフトラベルが最大である領域のみを考慮し、この領域のソフトラベルがこの代表フレーム（即ち、この領域が属する代表フレーム）のソフトラベルにできるだけ接近するようにしてもよい。このように、フレームレベル重み付きグラフと、領域レベル重み付きグラフとを互いに関連付けさせることができる。
【００３３】
なお、通常は、正のラベルを持つビデオシーン中のどのフレームが正例であるか（即ち、どのフレームが、上述の“特定種類の内容”を含むものであるか）を知ることができない。よって、所定の基準に基づいて、正例フレームである可能性があるもの（即ち、上述の“特定種類の内容”を含む可能性があるフレームであり、以下、“可能な正例フレーム”と略称される）を選出することができる。例えば、上述の可能な正例フレームは、ソフトラベルの値が第五所定閾値よりも高い代表フレームであってもよく、ソフトラベルの値が第六所定閾値よりも高い領域を含む代表フレームであってよい。
【００３４】
これによって、第二設定サブユニット320により、次のような第二制約条件を設定してもよく、即ち、負のラベルを持つビデオシーンのソフトラベル、負のラベルを持つビデオシーン中の全ての代表フレームのソフトラベル、及び負のラベルを持つビデオシーン中の全ての代表フレームの全ての領域のソフトラベルが-1にできるだけ接近するようにし；正のラベルを持つビデオシーンのソフトラベルが1にできるだけ接近するようにし；正のラベルを持つビデオシーン中の、ソフトラベルが最大である代表フレームのソフトラベルが、この代表フレームが属するビデオシーンのソフトラベルにできるだけ接近するようにし；及び、正のラベルを持つビデオシーン中の各可能な正例フレーム中の、ソフトラベルが最大である領域のソフトラベルが、この領域が属する代表フレームのソフトラベルにできるだけ接近するようにする。
【００３５】
上述の２つの制約条件に基づいて、関数構築サブユニット330により、上述のコスト関数を構築することができる。例えば、関数構築サブユニット330は、上述の２つの制約条件に基づいて、次のようなコスト関数を構築することができる。
【数１】
0006015504.tif 000002
ここで、
（外１）
0006015504.tif 000003
及び
（外２）
0006015504.tif 000004
は、それぞれ、上述のビデオシーンセット中の第g個及び第h個のビデオシーンのソフトラベルを表し、そのうち、g=1、2、…、Lであり、h=1、2、…、Lであり、Lは、ビデオシーンセット中に含まれるビデオシーンの数である。
（外３）
0006015504.tif 000005
及び
（外４）
0006015504.tif 000006
は、それぞれ、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレーム中の第i個及び第j個の代表フレームのソフトラベルを表し、そのうち、i=1、2、…、Mであり、j=1、2、…、Mであり、Mは、上述のビデオシーンセット中の全てのビデオシーンが含む代表フレームの数である。
（外５）
0006015504.tif 000007
及び
（外６）
0006015504.tif 000008
は、それぞれ、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレームが含む全ての領域中の第k個及び第l個の領域のソフトラベルを表し、そのうち、k=1、2、…、Nであり、l=1、2、…、Nであり、Nは、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレームが含む領域の数である。また、fSは、上述のビデオシーンセット中の全てのビデオシーンのソフトラベルからなるベクトルを表し、fFは、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレームのソフトラベルからなるベクトルを表し、fRは、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレーム中の全ての領域のソフトラベルからなるベクトルを表す。
（外７）
0006015504.tif 000009
は、ビデオシーンセット中の第g個のビデオシーン及び第h個のビデオシーンがシーンレベル重み付きグラフにおいてそれぞれ対応するノード間の重み付き辺の重み値を表し、WSは、シーンレベル重み付きグラフ中の全ての重み付き辺の重み値からなるマトリックスを表し、即ち、
（外８）
0006015504.tif 000010
は、WSの第g行、第h列の要素であり、また、
（外９）
0006015504.tif 000011
及び
（外１０）
0006015504.tif 000012
は、それぞれ、WSの第g行の全ての要素の和、及び第h行の全ての要素の和を表す。
（外１１）
0006015504.tif 000013
は、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレーム中の第i個の代表フレーム及び第j個の代表フレームがフレームレベル重み付きグラフにおいてそれぞれ対応するノード間の重み付き辺の重み値を表し、WFは、フレームレベル重み付きグラフ中の全ての重み付き辺の重み値からなるマトリックスを表し、即ち、
（外１２）
0006015504.tif 000014
は、WFの第i行、第j列の要素であり、また、
（外１３）
0006015504.tif 000015
和
（外１４）
0006015504.tif 000016
は、それぞれ、WFの第i行の全ての要素の和、及び第j行の全ての要素の和を表す。同様に、
（外１５）
0006015504.tif 000017
は、上述のビデオシーンセット中の全てのビデオシーンの全ての代表フレームが含む全ての領域中の第k個の領域及び第l個の領域が領域レベル重み付きグラフにおいてそれぞれ対応するノード間の重み付き辺の重み値を表し、WRは、領域レベル重み付きグラフ中の全ての重み付き辺の重み値からなるマトリックスを表し、即ち、
（外１６）
0006015504.tif 000018
は、WRの第k行、第l列の要素であり、また、
（外１７）
0006015504.tif 000019
及び
（外１８）
0006015504.tif 000020
は、それぞれ、WRの第k行の全ての要素の和、及び第l行の全ての要素の和を表す。
【００３６】
また、上述の数１では、Sgは、ビデオシーンセット中の第g個のビデオシーンを表し、S+及びS-は、それぞれ、ビデオシーンセット中の正例ビデオシーンセット及び負例ビデオシーンセットを表し、Fiは、ビデオシーンセット中の全てのビデオシーンの全ての代表フレーム中の第i個の代表フレームを表し、F-は、ビデオシーンセット中の負例ビデオシーンセット中の全ての代表フレームのセットを表し、Rkは、示ビデオシーンセット中の全てのビデオシーンの全ての代表フレームの全ての領域中の第k個の領域を表し、R-は、ビデオシーンセット中の負例ビデオシーンセット中の全ての代表フレームの全ての領域のセットを表し、C+は、ビデオシーンセット中の全てのビデオシーンが含む全ての代表フレーム中の可能な正例フレームのセットを表し、H1(x,y)及びH2(x,y)は、２つの量の間の不一致性（即ち、x及びyの間の不一致性）を評価するための関数であり、H1(x,y)=(max(x-y,0))2及びH2(x,y)=(max(y-x,0))2を採用してもよい。また、
（外１９）
0006015504.tif 000021
は、それぞれ、上述の数１中の各対応コスト項の重み付き係数であり、その値は、それぞれ、経験値又は試験により予め設定されてもよい。
【００３７】
そのうち、上述の数１では、前の３項は、第一制約条件がこのコスト関数において対応するコスト項であり、後の４項は、第二制約条件がこのコスト関数において対応するコスト項である。また、上述の数１に現れる上添字“S”は、ビデオシーンを表し、上添字“F”は、フレームを表し、上添字“R”は、領域を表す。
【００３８】
なお、上述のコスト関数の具体的な式（即ち、数１）は、コスト関数の1つの例示的な式だけであり、本発明の範囲を限定するものではない。例えば、上述のコスト関数は、次のように構築されてもよい。
【数２】
0006015504.tif 000022
【００３９】
ここで、上述の数１と比べ、数２は、数１中の第１項中の
（外２０）
0006015504.tif 000023
第２項中の
（外２１）
0006015504.tif 000024
及び第３項中の
（外２２）
0006015504.tif 000025
が削除された。
【００４０】
なお、コスト関数の具体的な式は、他の変形を有してもよく、例えば、上述の数１及び数１中のH1(x,y)及びH2(x,y)は、H1(x,y)=(x,y) 2及びH2(x,y)=(x,y)
2であってもよい。なお、当業者が上述の開示内容及び/又は従来技術と組み合わせることにより取得した上述の式の変形、改良又は他の形式は、全て、本発明の範囲内に属すべきである。
【００４１】
次に、構築したコスト関数に基づいてその中の未知量を計算するために、即ち、上述のビデオシーンセット中の各ビデオシーンのソフトラベルの値、上述のビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベルの値、及び上述のビデオシーンセット中の各ビデオシーンの各代表フレーム中の各領域のソフトラベルの値を取得するために、計算ユニット150により、コスト関数の最適化問題を解くことができる。具体的には、図4に示すような構造により、計算ユニット150の機能及び処理を実現することができる。
【００４２】
図4は、図1における計算ユニット150の１つの例示的な構造を示すブロック図である。図4に示すように、計算ユニット150は、初期化サブユニット410、第三計算サブユニット420、第四計算サブユニット430、第五計算サブユニット440及び第三判定サブユニット450を含んでもよい。図4に示すような構造により、計算ユニット150は、反復（iteration）の計算方法を採用して、上述の最適化問題を解くことができ、即ち、ｆＳ及びｆＦに初期値を与え、上述のコスト関数を利用して反復計算を行い、最終的に、ｆＲ、ｆＦ及びｆＳの値を取得する。次に、図4に示す計算ユニット150の各サブユニットの具体的な機能及び処理を詳しく説明する。
【００４３】
図4に示すように、初期化サブユニット410は、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳ、及びビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦに初期値を与えるために用いられる。
【００４４】
例えば、初期化サブユニット410は、次にようにビデオシーンセット中の各ビデオシーンのソフトラベルの初始値fS(0)を設定してもよく、即ち、Ｓｇが正のラベルを持つビデオシーンであれば、
（外２３）
0006015504.tif 000026
のようにし；Ｓｇが負のラベルを持つビデオシーンであれば、
（外２４）
0006015504.tif 000027
のようにし；及び、Ｓｇがラベル無しのビデオシーンであれば、
（外２５）
0006015504.tif 000028
のようにする。
【００４５】
同様に、初期化サブユニット410により、次のようにビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの初始値fF(0)を設定してもよく、即ち、Ｆｉが正のラベルを持つビデオシーン中の代表フレームであれば、
（外２６）
0006015504.tif 000029
のようにし；Ｆｉが負のラベルを持つビデオシーン中の代表フレームであれば、
（外２７）
0006015504.tif 000030
のようにし；及び、Ｆｉがラベル無しのビデオシーン中の代表フレームであれば、
（外２８）
0006015504.tif 000031
のようにする。
【００４６】
図4に示すように、第三計算サブユニット420は、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳの現在値に基づいて、及び、ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦの現在値に基づいて、コスト関数を制約付き最小化問題に変換し、CCCP（constrained  concave  convex  procedure）を用いてこの制約付き最小化問題を解き、ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルｆＲの計算値を得てｆＲの現在値とすることができる。
【００４７】
例えば、初回計算時に、ｆＳ及びｆＦの現在値がそれらの初始値であり、ｆＳ及びｆＦの現在値に基づいて、上述の数１のようなコスト関数を次のような式に簡略化することができる。
【数３】
0006015504.tif 000032
【００４８】
ここで、上述の数３では、各量の意味が上述の数１と同じである。また、数３では、上述のビデオシーンセット中の全てのビデオシーンが含む全ての代表フレーム中の可能な正例フレームのセットＣ+が、
（外２９）
0006015504.tif 000033
と定義されてもよい。そのうち、ＴＨＦは、上述の第五所定閾値であり、且つＴＨＦの値は、次のような式により確定されてもよい。
【数４】
0006015504.tif 000034
【００４９】
弛緩因子（relaxation  factor）を導入することにより、上述の数３のようなコスト関数を制約付き最小化問題に変換すれば、CCCPを用いてこの最適化問題を解くことができる。CCCPの詳しい説明については、非特許文献である「A.  J.  Smola、S.  V.  N.  Vishwanathan、and  T.  Hofmann、“Kernel  Methods  for  Missing  Variables、”in  Proc.  Int.  Workshop  on  Artificial  Intelligence  and  Statistics、2005」を参照することができる。
【００５０】
このように、第三計算サブユニット420は、ｆＳ及びｆＦの現在値及びコスト関数を用いて、上述の方式により、ｆＲの計算値を得てｆＲの現在値とすることができる。
【００５１】
図4に示すように、第四計算サブユニット430は、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳの現在値に基づいて、及び、ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルｆＲの現在値に基づいて、コスト関数を制約付き最小化問題に変換し、CCCPを用いてこの制約付き最小化問題を解き、ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦの計算値を得てｆＦの現在値とすることができる。
【００５２】
具体的には、ビデオシーンのソフトラベルｆＳ及び領域のソフトラベルｆＲが確定されている場合は、上述の数１のようなコスト関数を次のような式に簡略化してもよい。
【数５】
0006015504.tif 000035
【００５３】
ここで、上述の数５では、各量の意味が上述の数１と同じである。また、上述の数５では、上述のビデオシーンセット中の全てのビデオシーンが含む全ての代表フレーム中の可能な正例フレームのセットＣ+が、
（外３０）
0006015504.tif 000036
と定義されてもよい。そのうち、ＴＨＲは、上述の第六所定閾値であり、且つＴＨＲの値は、次の式により確定されてもよい。
【数６】
0006015504.tif 000037
【００５４】
同様に、弛緩因子を導入することにより上述の数５のようなコスト関数を制約付き最小化問題に変換すれば、CCCPを用いてこの制約付き最小化問題を解くことができる。
【００５５】
このように、第四計算サブユニット430は、ｆＳ及びｆＲ現在値及びコスト関数を用いて、上述の方式により、ｆＦの計算値を得てｆＦの現在値とすることができる。
【００５６】
図4に示すように、第五計算サブユニット440は、ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦの現在値に基づいて、及び、ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルｆＲの現在値に基づいて、コスト関数を直接利用して計算を行い、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳの計算値を得てｆＳの現在値とすることができる。
【００５７】
具体的には、代表フレームのソフトラベルｆＦ及び領域のソフトラベルｆＲが確定されている場合は、上述の数１のようなコスト関数を次のような式に簡略化することができる。
【数７】
0006015504.tif 000038
【００５８】
ここで、上述の数７では、各量の意味が上述の数１と同じである。上述の数７に基づいて、第五計算サブユニット440は、直接解くことにより、ｆＳの値を得てｆＳの現在値とすることができる。
【００５９】
図4に示すように、第三判定サブユニット450は、毎回、第三計算サブユニット420、第四計算サブユニット430及び第五計算サブユニット440がそれぞれ順次に一回の計算を行った後に、ｆＲ、ｆＦ及びｆＳの現在の計算結果が収束（収斂）になっているかどうかを判断し、収束になっていると判断すれば、ｆＲ、ｆＦ及びｆＳの現在の計算結果を上述のコスト関数中の未知量の計算値として保存し、そうでなければ、第三計算サブユニット420、第四計算サブユニット430及び第五計算サブユニット440を再び利用してそれぞれにより次の反復計算を行い、そして、第三判定サブユニット450を再び利用して判断を行い、このようにして、第三判定サブユニット450により、ｆＲ、ｆＦ及びｆＳの現在の計算結果が収束になっていると判定するまでに、上述の反復計算を繰り返して行う。
【００６０】
上述のように、前処理ユニット110、特徴抽出ユニット120、重み付きグラフ形成ユニット130、関数構築ユニット140及び計算ユニット150の処理により、上述のビデオシーンセット中の各ビデオシーン、各代表フレーム及び各領域のソフトラベルの計算値を得ることができ、これにより、ビデオ処理ユニット160は、得られたこれらの計算値に基づいてビデオ処理を行うことができる。
【００６１】
そのうち、ビデオ処理ユニット160が行うビデオ処理は、上述のソフトラベルを利用して処理を行うことができる各種の処理であってよい。
【００６２】
例えば、本発明の実施例によるビデオ処理装置の1つの応用例では、上述の“ビデオ処理”は、ビデオ検索であってもよく、即ち、上述のビデオ処理装置は、ビデオ検索装置であってもよい。
【００６３】
一般的に言えば、所要のビデオシーンを検索するために、ユーザは、検索システムに幾つかのラベル有りのトレーニングビデオシーンを提供して検索ビデオシーンとする。このような技術は、日常生活のあらゆる面に応用することができ、例えば、デジタルビデオ図書館、ビデオ撮像、ビデオ管理、及びオンラインビデオ配信サイトなどに応用することができる。
【００６４】
この応用例では、ユーザが提供する検索ビデオシーンの数は、1つであってもよく、複数であってもよい。検索ビデオシーンの数が1つである時に、この検索ビデオシーンは、正のラベルを持つビデオシーンである。検索ビデオシーンの数が複数である時に、これらの検索ビデオシーンは、全て正のラベルを持つビデオシーンであってもよく、正のラベルを持つビデオシーン及び負のラベルを持つビデオシーンの組み合わせであってもよい。そのうち、検索ビデオシーンが１つのみのフレーム（画像）を含む特例の場合、この検索ビデオシーンは、検索画像であり、この検索ビデオシーンから抽出した代表フレームは、この検索画像そのものである。
【００６５】
上述のように、前処理ユニット110、特徴抽出ユニット120、重み付きグラフ形成ユニット130、関数構築ユニット140及び計算ユニット150の一連の処理により、ビデオシーンセット中の各ビデオシーンのソフトラベル、このビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベル及びこのビデオシーンセット中の各ビデオシーンの各代表フレームの各領域のソフトラベルの計算値を得ることができ、これにより、これらのソフトラベルの計算値を利用して、ビデオ処理ユニット160は、ビデオシーンセット中のビデオシーン（検索ビデオシーン以外のビデオシーン）と検索ビデオシーンとの間の類似度を確定し、検索ビデオシーンとの間の類似度が所定の範囲内にあるビデオシーンをビデオ検索の結果（即ち、検索結果）として判定することができる。
【００６６】
例えば、1つの例では、ビデオ処理ユニット160は、次のような条件を満たすビデオシーンをビデオ検索の結果として判定することができ、即ち、このビデオシーン自身のソフトラベルが第一所定閾値よりも高く、このビデオシーン中の、ソフトラベルが最大である代表フレームのソフトラベルが第二所定閾値よりも高く、且つこのビデオシーン中の上述の最大ソフトラベルを有する代表フレーム中の、ソフトラベルが最大である領域のソフトラベルが第三所定閾値よりも高い。そのうち、第一、第二及び第三所定閾値の値は、同じであってもよく、異なってもよい。例えば、ビデオ処理ユニット160は、最後の計算結果中の、ビデオシーンのソフトラベルが0.8よりも高く、その中の最大ソフトラベルを有する代表フレームのソフトラベルが0.75よりも高く、且つこの代表フレーム中の最大ソフトラベルを有する領域のソフトラベルが0.7よりも高いという条件を満たす一部のビデオシーンを検索結果として確定することができる。
【００６７】
他の例では、ビデオ処理ユニット160は、次のような条件を満たすビデオシーンをビデオ検索の結果として判定することができ、即ち、ビデオシーンのソフトラベル、ビデオシーン中の最大ソフトラベルを有する代表フレームのソフトラベル、及びこの最大ソフトラベルを有する代表フレーム中の、最大ソフトラベルを有する領域のソフトラベルの重み付き和が最大でる前のN個のビデオシーンであり、そのうち、Nは正整数である。例えば、この重み付き和の計算式は、
（外３１）
0006015504.tif 000039
であってもよい。即ち、各ビデオシーンＳｇ（g＝1、2、…、L）について、上述の計算式により、１つの対応する重み付き和の値をそれぞれ算出し、そして、重み付き和が最大である前のN個の重み付き和が対応するビデオシーンを最終の検索結果として選出することができる。そのうち、
（外３２）
0006015504.tif 000040
は、ビデオシーンＳｇ中の最大ソフトラベルを有する代表フレームのソフトラベルの値を表し、Ｆｉ0は、ビデオシーンＳｇ中の最大ソフトラベルを有する代表フレームを表し、
（外３３）
0006015504.tif 000041
は、上述のビデオシーンＳｇ中の最大ソフトラベルを有する代表フレームＦｉ0中の、最大ソフトラベルを有する領域のソフトラベルの値を表す。また、α及びβは、線形組み合わせ係数であり、且つ０＜α＜1、０＜β＜1及び０＜α＋β＜1である。
【００６８】
また、ビデオ処理ユニット160は、次の任意の順序に従って検索結果をユーザに出力することができ、即ち、検索結果が対応するビデオシーンのソフトラベルの大小の順序；検索結果が対応するビデオシーン中の最大ソフトラベルを有する代表フレームのソフトラベルの大小の順序；検索結果が対応するビデオシーン中の最大ソフトラベルを有する代表フレーム中の、最大ソフトラベルを有する領域のソフトラベルの大小の順序；又は、検索結果が対応するビデオシーンのソフトラベル、ビデオシーン中の最大ソフトラベルを有する代表フレームのソフトラベル、及びこの代表フレーム中の最大ソフトラベルを有する領域のソフトラベルの三者の重み付き和の大小の順序である。
【００６９】
この応用例では、ビデオ処理装置は、ユーザが提供する検索ビデオシーン及びそのラベル情報に基づいて、シーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの３種類の重み付きグラフの構造特徴及び三者間の関係を利用して、ビデオシーンセット中の各ビデオシーン、各ビデオシーンの各代表フレーム及び各代表フレームの各領域のソフトラベルを求め、これらのソフトラベルに基づいて、このビデオシーンセット中の検索ビデオシーン以外の各ビデオシーンと検索ビデオシーンとの間の関連性（又は類似度）を確定し、検索ビデオシーンと最も関連（又は最も類似）するビデオシーンを検索結果として確定する。従来のビデオ検索技術に比べ、本発明の実施例によるビデオ処理装置のこの応用例は、シーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの３種類の重み付きグラフを同時に利用してビデオ検索を実現し、この３種類の重み付きグラフ間の関係を十分に探り出し、且つラベル有りのビデオシーン及びラベル無しのビデオシーンを利用し、ラベル有りのビデオシーンのリソースが限られているという問題の影響を受けないので、よりよいビデオ処理の効果を得ることができ、即ち、より正確な検索結果を得ることができる。
【００７０】
また、発明の実施例によるビデオ処理装置の他の応用例では、上述の“ビデオ処理”は、ビデオのコンセプト検出であってもよく、即ち、上述のビデオ処理装置は、ビデオコンセプト検出装置であってもよい。
【００７１】
一般的に言えば、ビデオのコンセプトを検出する目的は、対象ビデオシーンに所定の語義概念（例えば、テーマや特定のコンテンツなど）が含まれているかどうか（又は、どの程度含まれているか）を確定することにある。このような技術は、日常生活のあらゆる面に応用することができ、例えば、ビデオ図書館、家庭ビデオ管理、又はビデオリクエストなどに応用することができる。
【００７２】
この応用例では、対象ビデオシーンは、ラベル無しのビデオシーンであり、上述のビデオシーンセットに含まれてもよく、上述のビデオシーンセットに含まれなくてもよい。そのうち、対象ビデオシーンの数は、1つであってもよく、複数であってもよい。また、上述のように、この応用例中のビデオシーンセット中の少なくとも一部のビデオシーンは、ラベル有りのビデオシーンであり、これは、対象ビデオシーンにビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを確定するためである。
【００７３】
上述と同様に、前処理ユニット110、特徴抽出ユニット120、重み付きグラフ形成ユニット130、関数構築ユニット140及び計算ユニット150の一連の処理により、ビデオシーンセット中の各ビデオシーンのソフトラベルの計算値、このビデオシーンセット中の各代表フレームのソフトラベルの計算値、及び各代表フレームの各領域のソフトラベルの計算値を得ることができ、これにより、これらのソフトラベルの計算値を利用して、ビデオ処理ユニット160は、対象ビデオシーンに上述の語義概念が含まれているかどうか、即ち、ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを確定することができる。例えば、上述のビデオシーンセットが、正のラベルを持つビデオシーン及び負のラベルを持つビデオシーンを含み、且つ正のラベルを持つビデオシーンが、ラベルが“虎”のビデオシーンであり及び負のラベルを持つビデオシーンが、ラベルが“非虎”のビデオシーンである場合は、“ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念”が“虎”であり、即ち、ビデオ処理ユニット160が、対象ビデオシーンの内容に虎が含まれているかどうかを判断する必要があるとのことが容易に分かる。具体的には、ビデオ処理ユニット160の機能及び処理は、図5に示すような構造により実現され得る。
【００７４】
図5は、この応用例における図1に示すようなビデオ処理ユニット160の１つの例示的な構造を示すブロック図である。図5に示すように、ビデオ処理ユニット160は、第一判定サブユニット510、第一計算サブユニット520、第二計算サブユニット530及び第二判定サブユニット540を含んでもよい。
【００７５】
対象ビデオシーンに“ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念”が含まれているかどうかを判断するために、まず、第一判定サブユニット510により、この対象ビデオシーンが上述のビデオシーンセットに含まれているかどうかを判断し、その後、２つの場合に分けて後続の計算処理を行う。
【００７６】
１つの場合、即ち、対象ビデオシーンが上述のビデオシーンセットに含まれていない場合は、第一計算サブユニット520により、この対象ビデオシーンの少なくとも1つの代表フレームを抽出し、そして、抽出した対象ビデオシーンの各代表フレームに対して画像分割を行い、各代表フレームの複数の領域をそれぞれ取得し、これにより、計算ユニット150が取得した結果（即ち、ビデオシーンセット中の各ビデオシーン、各ビデオシーンの各代表フレーム、及び各代表フレームの各領域のソフトラベルの計算値）に基づいて、対象ビデオシーンのソフトラベルの計算値、対象ビデオシーン中の各代表フレームのソフトラベルの計算値、及び対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値（具体的な計算プロセスについて後述する）を求めることができる。その後、対象ビデオシーン及びそのうちの各代表フレーム、各領域のソフトラベルの計算値に基づいて、第二計算サブユニット530により、対象ビデオシーンが上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値（即ち、どの程度含むか）を計算することができる。
【００７７】
そのうち、この場合は、次のような数８〜数１０により、対象ビデオシーンのソフトラベル及びそのうちの各代表フレーム、各領域のソフトラベルを計算することができる。
【数８】
0006015504.tif 000042
【数９】
0006015504.tif 000043
【数１０】
0006015504.tif 000044
【００７８】
ここで、Ｓｔは、対象ビデオシーンを表し、Ｆｔは、対象ビデオシーン中のある代表フレームを表し、Ｒｔは、対象ビデオシーン中のある代表フレーム中のある領域を表し、
（外３４）
0006015504.tif 000045
は、対象ビデオシーンのソフトラベルを表し、
（外３５）
0006015504.tif 000046
は、対象ビデオシーン中のある代表フレームＦｔのソフトラベルを表し、
（外３６）
0006015504.tif 000047
（外３７）
0006015504.tif 000048
は、上述の意味と同じである。
（外３８）
0006015504.tif 000049
は、対象ビデオシーンＳｔとビデオシーンセット中の第g個のビデオシーンＳｇの間におけるシーンレベル視覚特徴に基づく類似度を表し、
（外３９）
0006015504.tif 000050
は、ビデオシーンセット中の第g個のビデオシーンＳｇとシーンレベル重み付きグラフ中の全てのノードが対応するビデオシーンとの類似度の和を表し、
（外４０）
0006015504.tif 000051
は、対象ビデオシーンとシーンレベル重み付きグラフ中の全てのノードが対応するビデオシーンとの類似度の和を表す。
（外４１）
0006015504.tif 000052
は、対象ビデオシーン中のある代表フレームＦｔとビデオシーンセット中の全てのビデオシーンの全ての代表フレーム中の第i個の代表フレームＦiとの間におけるフレームレベル視覚特徴に基づく類似度を表し、
（外４２）
0006015504.tif 000053
は、上述の第i個の代表フレームＦiとフレームレベル重み付きグラフ中の全てのノードが対応する代表フレームとの類似度の和を表し、
（外４３）
0006015504.tif 000054
は、対象ビデオシーン中のある代表フレームＦｔとフレームレベル重み付きグラフ中の全てのノードが対応する代表フレームとの類似度の和を表す。
（外４４）
0006015504.tif 000055
は、対象ビデオシーン中のある代表フレームＦｔ中のある領域Ｒｔとビデオシーンセット中の全てのビデオシーンの全ての代表フレーム中に含まれる全ての領域中の第k個の領域Ｒｋの間における領域レベル視覚特徴に基づく類似度を表し、
（外４５）
0006015504.tif 000056
は、上述の第k個の領域Ｒｋと領域レベル重み付きグラフ中の全てのノードが対応する領域との類似度の和を表し、
（外４６）
0006015504.tif 000057
は、対象ビデオシーン中のある代表フレームＦｔ中のある領域Ｒｔと領域レベル重み付きグラフ中の全てのノードが対応する領域との類似度の和を表す。
【００７９】
また、他の実現方式では、次のような数１１〜数１３により、対象ビデオシーンのソフトラベル及びそのうちの各代表フレーム、各領域のソフトラベルを計算することもできる。
【数１１】
0006015504.tif 000058
【数１２】
0006015504.tif 000059
【数１３】
0006015504.tif 000060
【００８０】
なお、上述の数１によりコスト関数を構築する時に、上述の数８〜数１０により、対象ビデオシーンのソフトラベル及びそのうちの各代表フレーム、各領域のソフトラベルを計算してもよく、同様に、上述の数２によりコスト関数を構築する時に、上述の数１１〜数１３により、対象ビデオシーンのソフトラベル及びそのうちの各代表フレーム、各領域のソフトラベルを計算してもよい。
【００８１】
もう１つの場合、即ち、対象ビデオシーンが上述のビデオシーンセットに含まれている場合は、計算ユニット150の計算により、既に対象ビデオシーンのソフトラベルの計算値及び対象ビデオシーン中の各代表フレーム、各領域のソフトラベルの計算値を得たので、第二計算サブユニット530により、上述の方式で、対象ビデオシーンが上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値（即ち、どの程度含むか）を直接計算することができる。
【００８２】
そのうち、上述の２つの場合は、次のような式で、対象ビデオシーンが上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値を計算することでき、即ち、
（外４７）
0006015504.tif 000061
である。そのうち、式中のパラメータは、上述の定義と同じであるので、ここでは、その説明を省略する。
【００８３】
これによって、この応用例では、第一判定サブユニット510、第一計算サブユニット520及び第二計算サブユニット530により、対象ビデオシーンが上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値を計算することができる。例えば、正のラベルが“虎”である場合は、この３つのサブユニット510〜530により、対象ビデオシーンの内容に虎がどの程度含まれているかを計算することができる。
【００８４】
その後、上述の程度の値が第四所定閾値（例えば、第四所定閾値が0.75）以上であれば、第二判定サブユニット540は、この対象ビデオシーンの内容に“上述のビデオシーンセット中のラベル有りのビデオシーンと関する語義概念”が含まれていると判定することができる。上述の程度の値が第四所定閾値よりも小さければ、第二判定サブユニット540は、この対象ビデオシーンの内容に“上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念”が含まれていないと判定することができる。
【００８５】
上述の判定結果に基づいて、第二判定サブユニット540により、対象ビデオシーンが“上述のビデオシーンセット中のラベル有りのビデオシーンと関する語義概念”を含んでいると判定した場合は、第二判定サブユニット540は、さらに、この語義概念を用いて、上述の対象ビデオシーンに対して注釈することができ、即ち、上述のビデオシーンセット中の正のラベルのビデオシーンのラベル情報を用いて対象ビデオシーンに対して注釈することができる。例えば、第二判定サブユニット540により対象ビデオシーンが“虎”を含んでいると判定した時に、対象ビデオシーンに“虎”というラベルを付けることができる。
【００８６】
この応用例では、ビデオ処理装置は、シーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの３種類の重み付きグラフの構造特徴及び三者間の関係を利用して、ビデオシーンセット中の各ビデオシーン、各ビデオシーンの各代表フレーム及び各代表フレームの各領域のソフトラベルを求め、これらのソフトラベルに基づいて、対象ビデオシーンが上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいるかどうかを確定する。従来のビデオ検索技術に比べ、本発明の実施例によるビデオ処理装置のこの応用例により実現するビデオのコンセプト検出は、上述の３種類の重み付きグラフを同時に利用することによってビデオシーンの特徴情報をより十分に利用し、この３種類の重み付きグラフ間の関係を十分に探り出し、また、ラベル有りのビデオシーンを利用した上でラベル無しのビデオシーンをも同時に利用することができるので、よりよいビデオ処理の効果を得ることができ、即ち、より正確なビデオのコンセプト検出結果を得ることができる。
【００８７】
上述により、本発明の実施例によるビデオ処理装置は、シーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフの３種類の重み付きグラフを利用することによってビデオシーンの特徴情報をより十分に利用し、また、この３種類の重み付きグラフ間の関係を十分に探り出しているので、よりよいビデオ処理の効果を得ることができる。
【００８８】
また、発明の実施例によれば、ビデオ処理方法が提供される。次に、図6及び図7を参照して、この方法の１つの例示的な処理を説明する。
【００８９】
図6は、本発明の実施例によるビデオ処理方法の１つの例示的な処理のフローチャートである。図6に示すように、本発明の実施例によるビデオ処理方法の処理プロセス600は、ステップS610からスタートし、その後、ステップS620を行う。
【００９０】
ステップS620では、ビデオシーンセット中の各ビデオシーンの少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割し、そのうち、このビデオシーンセット中の少なくとも一部のビデオシーンは、ラベル有りのビデオシーンである。その後、ステップS630を行う。そのうち、ステップS620での画像分割は、上述の方法を採用してもよい。
【００９１】
ステップS630では、上述のビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出する。その後、ステップS640を行う。そのうち、上述の３種類の視覚特徴の特性、選択及び抽出方法などは、全て上述の対応する内容を参照することができるので、ここでは、その説明を省略する。
【００９２】
ステップS640では、上述のシーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、上述のフレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、及び上述の領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成する。その後、ステップS650を行う。
【００９３】
そのうち、１つの実現方式では、次のように上述のシーンレベル重み付きグラフ、フレームレベル重み付きグラフ及び領域レベル重み付きグラフを形成することができ、即ち、上述のビデオシーンセット中の各ビデオシーンをノードとし、２つのノード間におけるシーンレベル視覚特徴上の類似度をこの２つのノード間の重み付き辺の重み値とし、上述のシーンレベル重み付きグラフを形成し；上述のビデオシーンセット中の各ビデオシーンの各代表フレームをノードとし、２つのノード間におけるフレームレベル視覚特徴上の類似度をこの２つのノード間の重み付き辺の重み値とし、上述のフレームレベル重み付きグラフを形成し；及び、上述のビデオシーンセット中の各ビデオシーンの各代表フレーム中の各領域をノードとし、２つのノード間における領域レベル視覚特徴上の類似度をこの２つのノード間の重み付き辺の重み値とし、上述の領域レベル重み付きグラフを形成する。
【００９４】
ステップS650では、上述のビデオシーンセット中の各ビデオシーンのソフトラベル、上述の各ビデオシーン中の各代表フレームのソフトラベル、及び上述の各代表フレーム中の各領域のソフトラベルを未知量とし、上述のシーンレベル重み付きグラフ、フレームレベル重み付きグラフ、及び領域レベル重み付きグラフの構造情報に基づいて、及び、上述の各ビデオシーンのソフトラベル、上述の各代表フレームのソフトラベル、及び上述の各領域のソフトラベルの間の関係に基づいて、コスト関数を構築する。その後、ステップS660を行う。
【００９５】
具体的には、次のような方法で上述のコスト関数を構築することができる。
【００９６】
例えば、上述のシーンレベル重み付きグラフ、フレームレベル重み付きグラフ、及び領域レベル重み付きグラフの構造情報に基づいて、次のような第一制約条件を設定することができ、即ち、２つのビデオシーンのシーンレベル視覚特徴が類似すればするほど、この２つのビデオシーンのソフトラベルの間の差が小さいようにし；２つの代表フレームのフレームレベル視覚特徴が類似すればするほど、この２つの代表フレームのソフトラベルの間の差が小さいようにし；及び、２つの領域の領域レベル視覚特徴が類似すればするほど、この２つの領域のソフトラベルの間の差が小さいようにする。
【００９７】
また、上述のビデオシーンセット中のラベル有りのビデオシーンのソフトラベル、このビデオシーンセット中のラベル有りのビデオシーン中の代表フレームのソフトラベル、及びこの代表フレーム中の領域のソフトラベルとの間の関係に基づいて、次のような第二制約条件を設定することができ、即ち、負のラベルを持つビデオシーンのソフトラベル、負のラベルを持つビデオシーン中の全ての代表フレームのソフトラベル、及び負のラベルを持つビデオシーン中の全ての代表フレームの全ての領域のソフトラベルが-1にできるだけ接近するようにし；正のラベルを持つビデオシーンのソフトラベルが1にできるだけ接近するようにし；正のラベルを持つビデオシーン中の、最大ソフトラベルを有する代表フレームのソフトラベルが、この代表フレームが属するビデオシーンのソフトラベルにできるだけ接近するようにし；及び、正のラベルを持つビデオシーン中の各可能な正例フレーム中の、最大ソフトラベルを有する領域のソフトラベルが、この領域が属する代表フレームのソフトラベルにできるだけ接近するようにする。
【００９８】
なお、各可能な正例フレームは、そのソフトラベルの値が第五所定閾値よりも高いフレームであってもよく、又は、その中にソフトラベルの値が第六所定閾値よりも高い領域を含むフレームであってよい。
【００９９】
その後、上述の第一制約条件及び第二制約条件に基づいて、コスト関数を構築することができる。なお、このコスト関数は、上述の任意の具体的な式を採用することができるので、ここでは、その説明を省略する。
【０１００】
その後、ステップS660では、上述のコスト関数の最適化問題を解くことにより、上述の未知量の計算値を求める。その後、ステップS670を行う。
【０１０１】
そのうち、ステップS660では、１つの反復の計算方法により、上述の最適化問題を解くことができ、即ち、ｆＳ及びｆＦに初期値を与え、上述のコスト関数を利用して反復計算を行い、最終的に、ｆＲ、ｆＦ、及びｆＳの値を得ることができる。次に、図7を参照して、ステップS660の１つの例示的な計算プロセスを説明する。
【０１０２】
図7は、図6に示すようなステップS670の１つの例示的な処理のフローチャートである。図7に示すように、ステップS710では、まず、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳ及びビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦに初期値を与える。そのうち、ステップS710では、図4に基づいて説明した上述の初期化サブユニット410が行う処理の方法と同じ方法により、各ビデオシーンのソフトラベルｆＳ及び各代表フレームのソフトラベルｆＦに初期値を与えることができるので、ここでは、その説明を省略する。その後、ステップS720を行う。
【０１０３】
続いて、ステップS720〜S750の循環（ループ）処理により、ｆＲ、ｆＦ、及びｆＳの値を計算する。
【０１０４】
そのうち、ステップS720では、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳの現在値に基づいて、及び、ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦの現在値に基づいて、コスト関数を制約付き最小化問題に変換し、CCCPを利用してこの制約付き最小化問題を解くことにより、ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルｆＲの計算値を得てｆＲの現在値とすることができる。そのうち、ステップS720では、図4に基づいて説明した第三計算サブユニット420が行う処理の方法と同じ方法によりｆＲ計算値を得ることができるので、ここでは、その説明を省略する。その後、ステップS730を行う。
【０１０５】
ステップS730では、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳの現在値に基づいて、及び、ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルｆＲの現在値に基づいて、コスト関数を制約付き最小化問題に変換し、CCCPを利用してこの制約付き最小化問題を解くことにより、ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦの計算値を得てｆＦの現在値とする。そのうち、ステップS730では、図4に基づいて説明した第四計算サブユニット430が行う処理の方法と同じ方法によりｆＦの計算値を得ることができるので、ここでは、その説明を省略する。その後、ステップS740を行う。
【０１０６】
ステップS740では、ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルｆＦの現在値に基づいて、及び、ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルｆＲの現在値に基づいて、コスト関数を直接利用して計算を行うことにより、ビデオシーンセット中の各ビデオシーンのソフトラベルｆＳの計算値を得てｆＳの現在値とすることできる。そのうち、ステップS740では、図4に基づいて説明した第五計算サブユニット440が行う処理の方法と同じ方法によりｆＳの計算値を得ることができるので、ここでは、その説明を省略する。その後、ステップS750を行う。
【０１０７】
ステップS750では、ｆＲ、ｆＦ、及びｆＳの現在の計算結果が収束になっているかどうかを判断し、収束になっていると判断する場合、上述の各ビデオシーンのソフトラベル、上述の各代表フレームのソフトラベル、及び上述の各領域のソフトラベルの現在値を上述のコスト関数中の未知量の計算値として保存した後に、続いてステップS670を行い、そうではない場合、ステップS720に戻して次の反復計算を行う。
【０１０８】
このように、ステップS720〜750の循環反復計算により、ｆＲ、ｆＦ、及びｆＳのうちの２つがそれぞれ確定されている場合、残りの１つのベクトル中の要素を変量とし、残りの１つのベクトル中の要素の値を求めることができる。計算結果が収束になるまでに、上述の順序に従って反復計算を行い、即ち、ｆＲ→ｆＦ→ｆＳ→ｆＲ→ｆＦ→ｆＳ→…の順序に従って循環反復計算を行う。よって、ステップS650での上述のコスト関数中の未知量の計算値を得ることができる。
【０１０９】
再び図6を参照する。ステップS670では、算出した上述の未知量の計算値に基づいて、ビデオ処理を行う。その後、ステップS680を行う。
【０１１０】
そのうち、本発明の実施例によるビデオ処理方法の1つの例では、このビデオ処理方法でのビデオ処理がビデオ検索であってもよく、この場合、上述のビデオシーンセットは、ラベル有りの検索ビデオシーンを含む。また、この場合、ステップS670では、得られた計算値に基づいて、上述のビデオシーンセット中のこの検索ビデオシーン以外の、この検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンを検索結果として判定することができる。上述の検索結果は、次のようなビデオシーンであってもよく、即ち、そのソフトラベルが第一所定閾値よりも高いビデオシーンであって、このビデオシーン中の、最大ソフトラベルを有する代表フレームのソフトラベルが第二所定閾値よりも高く、且つ、この代表フレーム中の、最大ソフトラベルを有する領域のソフトラベルが第三所定閾値よりも高いものである。
【０１１１】
また、上述の検索結果は、次のようなビデオシーンであってよく、即ち、そのソフトラベル、その中の最大ソフトラベルを有する代表フレームのソフトラベル、及びこの代表フレーム中の最大ソフトラベルを有する領域のソフトラベルの三者の重み付き和が最大である前のN個のビデオシーンであり、そのうち、Nは、正整数である。そのうち、検索ビデオシーンが１つのみのフレーム（画像）を含む特例の場合、検索ビデオシーンは、検索画像であり、検索ビデオシーンから抽出した代表フレームは、この検索画像自身である。また、上述の検索結果は、一定の順序に従って出力されてもよく、例えば、上述の幾つかの順序のうちの任意の１つに従って出力されてもよいので、ここでは、その説明を省略する。
【０１１２】
また、本発明の実施例によるビデオ処理方法の他の例では、このビデオ処理方法でのビデオ処理がビデオのコンセプト検出であってもよい。この場合、ステップS670では、ステップS660にて得られたソフトラベルの計算値に基づいて、ラベル無しの対象ビデオシーンにビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを判定することができる。この場合、ステップS670の処理は、図8に示すようなステップS810〜S860により実現することができる。次に、その具体的な処理プロセスを説明する。
【０１１３】
図8は、ビデオ処理がビデオのコンセプト検出である場合に、図6に示すようなステップS670の１つの例示的な処理のフローチャートである。図8に示すように、ステップS810では、対象ビデオシーンが上述のビデオシーンセットに含まれているかどうかを判定し、含まれていると判定した場合、対象ビデオシーンのソフトラベル及びそのうちの各代表フレーム、各領域のソフトラベルが既に取得されているので、ステップS830を直接行って次の計算を行うことができ、そうでない場合、対象ビデオシーンのソフトラベル及びそのうちの各代表フレーム、各領域のソフトラベルが全て未知量であるので、ステップS820を行ってこれらのソフトラベルを求めることができる。
【０１１４】
ステップS820では、まず、対象ビデオシーン中の少なくとも１つのフレームを抽出してこの対象ビデオシーンの代表フレームとしてもよく、その後、対象ビデオシーンの各代表フレームを複数の領域に分割し、それから、得られた未知量の計算値に基づいて、対象ビデオシーンのソフトラベルの計算値、対象ビデオシーン中の各代表フレームのソフトラベルの計算値、及び対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を求めることができる。具体的な計算方法は、上述の対象ビデオシーンのソフトラベル、対象ビデオシーン中の各代表フレーム、及びそのうちの各領域のソフトラベルを計算するために用いる方法を参照することができるので、ここでは、その説明を省略する。ステップS820を行った後に、ステップS830を行う。
【０１１５】
ステップS830では、得られた対象ビデオシーンのソフトラベルの計算値、対象ビデオシーン中の各代表フレームのソフトラベルの計算値、及び対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値に基づいて、対象ビデオシーンが上述のビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値を計算し、そのうち、この計算プロセスは、上述のような程度の値の計算方法を参照することができるので、ここでは、その説明を省略する。その後、ステップS840を行う。
【０１１６】
ステップS840では、この程度の値が第四所定閾値以上であるかどうかを判断し、「はい」である場合、ステップS850を行い、即ち、ステップS850にて、対象ビデオシーンが“上述ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念”を含んでいると判断し、その後、後続のステップ（例えば、図6に示すようなステップS680）を行い、「いいえ」である場合、ステップS860を行い、即ち、ステップS860にて、対象ビデオシーンが“上述ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念”を含んでいないと判断し、その後、後続のステップ（例えば、図6に示すようなステップS680）を行う。
【０１１７】
なお、本発明の実施例による上述のビデオ処理方法中の各ステップの処理又はサブ子処理は、上述のビデオ処理装置のユニット、サブユニット、モジュール又はサブモジュールを実現し得る処理又は機能の処理プロセスを有してもよく、且つ、類似する技術的効果を達成することができる。ここでは、その詳しい説明を省略する。
【０１１８】
上述により、本発明の実施例によるビデオ処理方法を応用することにより、シーンレベル重み付きグラフ、フレームレベル重み付きグラフ、及び領域レベル重み付きグラフの３種類の重み付きグラフを用いて、ビデオシーンの特徴情報をより十分に利用し、３種類の重み付きグラフの間の関係を十分に探り出すことができるので、よりよいビデオ処理の効果を得ることができる。また、本発明の実施例によるビデオ処理方法は、ラベル有りのビデオシーン及びラベル無しのビデオシーンを同時に利用することができるので、利用可能なリソースを豊富にし、よりよい、より正確な処理効果を得ることができる。
【０１１９】
また、本発明の実施例によれば、設備が提供される。この設備は、上述のビデオ処理装置を含む。そのうち、この設備は、例えば、カメラ（例えば、デジタルカメラ）、ビデオカメラ、コンピュータ（例えば、デスクトップパソコン又はノットパソコン）、携帯電話（例えば、スマートフォン）、パーソナルデジタルアシスタント、及びマルチメディア処理設備（例えば、ビデオ再生機能付きのMP3、MP4）などであってもよい。
【０１２０】
本発明の実施例による上述の設備は、上述のビデオ処理装置を統合することにより、シーンレベル重み付きグラフ、フレームレベル重み付きグラフ、及び領域レベル重み付きグラフの３種類の重み付きグラフを用いて、ビデオシーンの特徴情報をより十分に利用し、３種類の重み付きグラフの間の関係を十分に探り出すことができるので、よりよいビデオ処理の効果を得ることができる。
【０１２１】
本発明の実施例による上述のビデオ処理装置における各構成ユニット、サブユニットなどは、ソフトウェア、ファームウェア、ハードウェア又はそれらの任意の組み合わせの方式で実現されてもよい。ソフトウェア又はファームウェアにより実現される場合は、記憶媒体又はネットワークから、専用ハードウェア構造を有する装置（例えば図9に示す汎用装置900）に、このソフトウェア又はファームウェアを構成するプログラムをインストールすることができる。この装置は、各種のプログラムがインストールされている時に、上述の各構成ユニットやサブユニットの各種の機能を行うことができる。
【０１２２】
図9は、本発明の実施例によるビデオ処理装置及び方法を実現するために用い得る計算装置の例示的な構造図である。
【０１２３】
図9では、中央処理ユニット（CPU）901は、ROM  902に記憶されているプログラム、又は、記憶部908からRAM  903にロードされているプログラムに基づいて、各種の処理を行う。RAM  903は、必要に応じて、CPU  901が各種の処理などを実行する時に必要なデータを記憶する。CPU  901、ROM  902及びRAM  903は、バス904により互いに接続される。入力/出力インタフェース905もバス904に接続される。
【０１２４】
また、入力/出力インタフェース905に接続されるのは、入力部906（キーボード、マウスなどを含み）、出力部907（例えばCRT、LCDのような表示器及びスピーカーなどを含み）、記憶部908（ハードディスクなどを含み）、通信部1309（例えばLANカード、モデムなどのネットワークアクセスカードを含み）をも含む。通信部1309は、ネットワーク、例えばインターネットを介して通信処理を行う。必要に応じて、ドライブ910も入力/出力インタフェース905に接続され得る。取り外し可能な媒体911、例えば磁気ディスク、光ディスク、光磁気ディスク、半導体記憶装置なども、必要に応じてドライブ910に取り付けされてもよく、その中から読み出されたコンピュータプログラムは、必要に応じて記憶部908にインストールされ得る。
【０１２５】
ソフトウェアにより上述の一連の処理を実現する場合、ネットワーク、例えばインターネット、又は、記憶媒体、例えば取り外し可能な媒体介質911からソフトウェアを構成するプログラムをインストールしてもよい。
【０１２６】
なお、当業者が理解すべきは、このような記憶媒体は、中にプログラムが記憶されており、ユーザにプログラムを提供するよう装置と独立して配られる図9に示すような取り外し可能な媒体911に限定されない。取り外し可能な媒体911の例としては、磁気ディスク（フロッピー（登録商標）ディスクを含む）、光ディスク（ＣＤ−ＲＯＭ及びＤＶＤを含む）、光磁気ディスク（ＭＤ（登録商標）を含む）、及び半導体メモリを含む。或いは、記憶媒体はROM902、記憶部908に含まれるハードディスクなどであってもよく、それらにはプログラムが記憶されており、且つそれらを含む装置とともにユーザに配られてもよい。
【０１２７】
また、本開示は、マシン（例えば、コンピュータ）読取可能な命令コードからなるプログラムプロダクトにも関する。この命令コードは、マシンに読み取られて実行される時に、上述の実施例によるビデオ処理方法を実行することができる。それ相応に、上述のマシン読取可能な命令コードからなるプログラムプロダクトを記憶している記憶媒体も本開示に含まれている。このような記憶媒体は、磁気ディスク（フロッピーディスク）、光ディスク、光磁気ディスク、メモリカード、メモリメモリスティックなどを含むが、これらに限定されない。
【０１２８】
また、本開示の一つの図面又は一つの実施例に記載の要素及び特徴は、一つ以上の他の図面又は実施例に示す要素及び特徴と組み合わせることができる。
【０１２９】
また、上述の一連の処理を行うステップは、上述に説明した順序に従って時間順に行ってもよいが、必ずしも時間順に行う必要がない。一部のステップは、並行又は互いに独立で行ってもよい。
【０１３０】
また、本開示による上述の方法の各処理プロセスは、各種のマシン読み取り可能な記憶媒体に記憶されるコンピュータ実行可能なプログラムで実現され得ることも明らかである。
【０１３１】
また、本開示の目的は、次の方法で実現されてもよい。即ち、上述の実行可能なプログラムコードを記憶している記憶媒体を直接又は間接的にシステム又は装置に提供し、且つ、このシステム又は装置内のコンピュータ又はCPUは、上述のプログラムコードを読み出して実行する。このとき、システム又は装置はプログラムを実行する機能を有すれば、本発明の実施形態はプログラムに限定されず、且つ、このプログラムは任意の形式であってもよく、例えば、オブジェクトプログラム、インタープリター実行可能なプログラム、又は、オペレーティングシステムへのスクリプトプログラムであってもよい。
【０１３２】
上述のマシン読み取り可能な記憶媒体は、各種の記憶器及び記憶ユニット、半導体装置、光、磁気及び光磁気ディスクのような磁気ディスクユニット、及び情報記憶に適する他の媒体等を含むが、これらに限定されない。
【０１３３】
また、クライントコンピュータは、インターネットを介して、対応するサーバに接続し、且つ、本発明によるコンピュータプログムラコードをコンピュータにダウンロードしてインストールし、それから、このプログラムを実行することにより、本発明を実現することもできる。
【０１３４】
最後に説明すべきは、本文では、例えば、「第一」及び「第二」などのような関係を表す語は、１つの実体又は操作と、もう１つの実体又は操作とを区分するためだけのものであり、これらの実体又は操作の間にそのような実際の関係又は順序が存在するとの意味又は示唆を有しない。また、「含む」、「有する」の語又はその他の変形語は、非排他的な「含む」を包括するため用いられ、これにより、一連の要素を含むプロセス、方法、物品又は装置は、これらの要素だけでなく、明記されていない他の要素を含んでもよく、或いは、このプロセス、方法、物品又は装置が所有する固有の要素を含むものである。より多くの限定が無い場合、「・・・を含む」という語句で限定される要素は、この要素を含むプロセス、方法、物品又は装置に存在する他の同じ要素を排除しない。
【０１３５】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１３６】
（付記1）
ビデオ処理装置であって、
ビデオシーンセット中の各ビデオシーンの少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割する前処理ユニットであって、前記ビデオシーンセットの少なくとも一部のビデオシーンはラベル有りのビデオシーンである、前処理ユニットと、
前記ビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出する特徴抽出ユニットと、
前記シーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、前記フレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、前記領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成する重み付きグラフ形成ユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記各ビデオシーン中の各代表フレームのソフトラベル及び前記各代表フレーム中の各領域のソフトラベルを未知量とし、前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、及び、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、コスト関数を構築する関数構築ユニットと、
前記コスト関数の最適化問題を解くことにより、前記未知量の計算値を得る計算ユニットと、
前記計算ユニットにより得られた計算値に基づいて、ビデオ処理を行うビデオ処理ユニットと、を含む、ビデオ処理装置。
【０１３７】
（付記2）
付記1に記載のビデオ処理装置であって、
前記ビデオ処理装置は、ビデオ検索装置であり、
前記ビデオシーンセットは、ラベル有りの検索ビデオシーンを含み、
前記ビデオ処理ユニットは、前記計算ユニットにより得られた計算値に基づいて、前記ビデオシーンセット中の前記検索ビデオシーン以外の、前記検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンを検索結果として判定する、ビデオ処理装置。
【０１３８】
（付記3）
付記2に記載のビデオ処理装置であって、
前記ビデオシーンセット中の前記検索ビデオシーン以外の、前記検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンは、
そのソフトラベルが第一所定閾値よりも高いビデオシーンであって、該ビデオシーン中に最大ソフトラベルを有する代表フレームのソフトラベルが第二所定閾値よりも高く、且つ該代表フレーム中に最大ソフトラベルを有する領域のソフトラベルが第三所定閾値よりも高い、ビデオシーン、又は、
そのソフトラベル、その中に最大ソフトラベルを有する代表フレームのソフトラベル、及び該代表フレーム中に最大ソフトラベルを有する領域のソフトラベルの三者の重み付き和が最大である前のN個のビデオシーンであって、Nは正整数である、ビデオシーンである、ビデオ処理装置。
【０１３９】
（付記4）
付記2又は3に記載のビデオ処理装置であって、
前記検索ビデオシーンが１つのみのフレーム（画像）を含む場合、前記検索ビデオシーンは、検索画像であり、前記検索ビデオシーン中の代表フレームは、前記検索画像そのものである、ビデオ処理装置。
【０１４０】
（付記5）
付記1に記載のビデオ処理装置であって、
前記ビデオ処理装置は、ビデオコンセプト検出装置であり、
前記ビデオ処理ユニットは、前記計算ユニットにより得られた結果に基づいて、ラベル無しの対象ビデオシーンに前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを判定する、ビデオ処理装置。
【０１４１】
（付記6）
付記5に記載のビデオ処理装置であって、
前記ビデオ処理ユニットは、
前記対象ビデオシーンが前記ビデオシーンセットに含まれているかどうかを判定する第一判定サブユニットと、
前記対象ビデオシーンが前記ビデオシーンセットに含まれていない場合、前記対象ビデオシーンの少なくとも1つの代表フレームを抽出し、前記対象ビデオシーンの各代表フレームを複数の領域に分割し、前記計算ユニットにより得られた結果に基づいて、前記対象ビデオシーンのソフトラベルの計算値、前記対象ビデオシーン中の各代表フレームのソフトラベルの計算値、及び前記対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を求める第一計算サブユニットと、
前記第一計算サブユニットにより得られた結果に基づいて、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値を計算する第二計算サブユニットと、
前記第二計算サブユニットにより算出された前記程度の値が第四所定閾値以上である場合、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいると判定し、前記程度の値が前記第四所定閾値よりも小さい場合、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいないと判定する第二判定サブユニットと、を含む、ビデオ処理装置。
【０１４２】
（付記7）
付記5又は6に記載のビデオ処理装置であって、
前記ビデオ処理ユニットは、さらに、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいると判定した場合、前記ビデオシーンセット中の、正のラベルを持つビデオシーンのラベルを用いて前記対象ビデオシーンに対して注釈を行う、ビデオ処理装置。
【０１４３】
（付記8）
付記1乃至7の何れか１つのビデオ処理装置であって、
前記重み付きグラフ形成ユニットは、
前記ビデオシーンセット中の各ビデオシーンをノードとし、任意の２つのノード間のシーンレベル視覚特徴上の類似度を該２つのノード間の重み付き辺の重み値とし、前記シーンレベル重み付きグラフを形成する第一形成サブユニットと、
前記ビデオシーンセット中の各ビデオシーンの各代表フレームをノードとし、任意の２つのノード間のフレームレベル視覚特徴上の類似度を該２つのノード間の重み付き辺の重み値とし、前記フレームレベル重み付きグラフを形成する第二形成サブユニットと、
前記ビデオシーンセット中の各ビデオシーンの各代表フレームの各領域をノードとし、任意の２つのノード間の領域レベル視覚特徴上の類似度を該２つのノード間の重み付き辺の重み値とし、前記領域レベル重み付きグラフを形成する第三形成サブユニットと、を含む、ビデオ処理装置。
【０１４４】
（付記9）
付記1乃至8に何れか１つに記載のビデオ処理装置であって、
前記関数構築ユニットは、
前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、２つのビデオシーンのシーンレベル視覚特徴が類似すればするほど、該２つのビデオシーンのソフトラベル間の差が小さいようにし、２つの代表フレームのフレームレベル視覚特徴が類似すればするほど、該２つの代表フレームのソフトラベル間の差が小さいようにし、及び、２つの領域の領域レベル視覚特徴が類似すればするほど、該２つの領域のソフトラベル間の差を小さいようにするという第一制約条件を設定する第一設定サブユニットと、
前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、負のラベルを持つビデオシーンのソフトラベル、負のラベルを持つビデオシーン中の全ての代表フレームのソフトラベル、及び負のラベルを持つビデオシーン中の全ての代表フレームの全ての領域のソフトラベルが-1にできるだけ接近するようにし、正のラベルを持つビデオシーンのソフトラベルが1にできるだけ接近するようにし、正のラベルを持つビデオシーンに最大ソフトラベルを有する代表フレームのソフトラベルが、該代表フレームが属するビデオシーンのソフトラベルにできるだけ接近するようにし、及び、正のラベルのビデオシーン中の各可能な正例フレームに最大ソフトラベルを有する領域のソフトラベルが、該領域が属する代表フレームのソフトラベルにできるだけ接近するようにするという第二制約条件を設定する第二設定サブユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記ビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベル、及び前記ビデオシーンセット中の各ビデオシーンの各代表フレームの各領域のソフトラベルを未知量とし、前記第一制約条件及び前記第二制約条件に基づいて、コスト関数を構築する関数構築サブユニットと、を含む、ビデオ処理装置。
【０１４５】
（付記10）
付記9に記載のビデオ処理装置であって、
前記可能な正例フレームは、そのソフトラベルの値が第五所定閾値よりも高いフレーム、又は、その中にソフトラベルが第六所定閾値よりも高い領域を含むフレームである、ビデオ処理装置。
【０１４６】
（付記11）
付記1乃至10の何れか１つに記載のビデオ処理装置であって、
前記計算ユニットは、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル及び前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルに初期値を与える初期化サブユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの現在値に基づいて、前記コスト関数を制約付き最小化問題に変換し、CCCPを用いて該制約付き最小化問題を解き、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を求める第三計算サブユニットと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値に基づいて、前記コスト関数を制約付き最小化問題に変換し、CCCPを用いて該制約付き最小化問題を解き、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの計算値を求める第四計算サブユニットと、
前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値に基づいて、前記コスト関数を用いて計算を行い、前記ビデオシーンセット中の各ビデオシーンのソフトラベルの計算値を求める第五計算サブユニットと、
第三計算サブユニット、第四計算サブユニット及び第五計算サブユニットがそれぞれ一回の計算を行った後に、前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベル、及び前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値が収斂になっているかどうかを判断する第三判定サブユニットであって、前者の場合、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの現在値を前記コスト関数中の未知量の計算値として保存し、後者の場合、前記第三判定サブユニットにより前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの現在値が収斂になっていると判断するまでに、再び第三計算サブユニット、第四計算サブユニット及び第五計算サブユニットをそれぞれ用いて次の反復計算を行う、第三判定サブユニットと、を含む、ビデオ処理装置。
【０１４７】
（付記12）
ビデオ処理方法であって、
ビデオシーンセット中の各ビデオシーンの少なくとも1つの代表フレームをそれぞれ抽出し、抽出した各代表フレームを複数の領域に分割する前処理ステップであって、前記ビデオシーンセットの少なくとも一部のビデオシーンはラベル有りのビデオシーンである、前処理ステップと、
前記ビデオシーンセット中の各ビデオシーンのシーンレベル視覚特徴、フレームレベル視覚特徴及び領域レベル視覚特徴を抽出する特徴抽出ステップと、
前記シーンレベル視覚特徴に基づいてシーンレベル重み付きグラフを形成し、前記フレームレベル視覚特徴に基づいてフレームレベル重み付きグラフを形成し、前記領域レベル視覚特徴に基づいて領域レベル重み付きグラフを形成するグラフ形成ステップと、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記各ビデオシーン中の各代表フレームのソフトラベル、及び前記各代表フレーム中の各領域のソフトラベルを未知量とし、前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、及び、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、コスト関数を構築する関数構築ステップと、
前記コスト関数の最適化問題を解き、前記未知量の計算値を得る未知量計算ステップと、
得られた前記未知量の計算値に基づいて、ビデオ処理を行うビデオ処理ステップと、を含む、ビデオ処理方法。
【０１４８】
（付記13）
付記12に記載のビデオ処理方法であって、
前記ビデオ処理は、ビデオ検索であり、
前記ビデオシーンセットは、ラベル有りの検索ビデオシーンを含み、
前記ビデオ処理ステップは、得られた前記未知量の計算値に基づいて、前記ビデオシーンセット中の前記検索ビデオシーン以外の、前記検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンを検索結果として判定することを含む、ビデオ処理方法。
【０１４９】
（付記14）
付記13に記載のビデオ処理方法であって、
前記ビデオシーンセット中の前記検索ビデオシーン以外の、前記検索ビデオシーンとの類似度が所定の範囲内にあるビデオシーンは、
そのソフトラベルが第一所定閾値よりも高いビデオシーンであって、該ビデオシーン中に最大ソフトラベルを有する代表フレームのソフトラベルが第二所定閾値よりも高く、且つ該代表フレーム中に最大ソフトラベルを有する領域のソフトラベルが第三所定閾値よりも高い、ビデオシーン、又は、
そのソフトラベル、その中に最大ソフトラベルを有する代表フレームのソフトラベル、及び該代表フレーム中に最大ソフトラベルを有する領域のソフトラベルの三者の重み付き和が最大である前のN個のビデオシーンであって、Nは正整数である、ビデオシーンである、ビデオ処理方法。
【０１５０】
（付記15）
付記13又は14に記載のビデオ処理方法であって、
前記検索ビデオシーンが１つのみのフレーム（画像）を含む場合、前記検索ビデオシーンは、検索画像であり、前記検索ビデオシーン中の代表フレームは、前記検索画像そのものである、ビデオ処理方法。
【０１５１】
（付記16）
付記12に記載のビデオ処理方法であって、
前記ビデオ処理は、ビデオコンセプト検出であり、
前記ビデオ処理ステップは、得られた前記未知量の計算値に基づいて、ラベル無しの対象ビデオシーンに前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを判定することを含む、ビデオ処理方法。
【０１５２】
（付記17）
付記16に記載のビデオ処理方法であって、
前記ラベル無しの対象ビデオシーンに前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念が含まれているかどうかを判定することは、
前記対象ビデオシーンが前記ビデオシーンセットに含まれているかどうかを判定し、
前記対象ビデオシーンが前記ビデオシーンセットに含まれていない場合、前記対象ビデオシーンの少なくとも1つの代表フレームを抽出し、前記対象ビデオシーンの各代表フレームを複数の領域に分割し、得られた前記未知量の計算値に基づいて、前記対象ビデオシーンのソフトラベルの計算値、前記対象ビデオシーン中の各代表フレームのソフトラベルの計算値及び前記対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を求め、
求められた前記対象ビデオシーンのソフトラベルの計算値、前記対象ビデオシーン中の各代表フレームのソフトラベルの計算値及び前記対象ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値に基づいて、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含む程度の値を計算し、及び、
算出された前記程度の値が第四所定閾値以上である場合、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいると判定し、前記程度の値が前記第四所定閾値よりも小さい場合、前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいないと判定することを含む、ビデオ処理方法。
【０１５３】
（付記18）
付記16又は17に記載のビデオ処理方法であって、さらに、
前記対象ビデオシーンが前記ビデオシーンセット中のラベル有りのビデオシーンと関連する語義概念を含んでいると判定した場合、前記ビデオシーンセット中の、正のラベルを持つビデオシーンのラベルを用いて前記対象ビデオシーンに対して注釈を行うことを含む、ビデオ処理方法。
【０１５４】
（付記19）
付記12乃至18の何れか１つに記載のビデオ処理方法であって、
前記グラフ形成ステップは、
前記ビデオシーンセット中の各ビデオシーンをノードとし、任意の２つのノード間のシーンレベル視覚特徴上の類似度を該２つのノード間の重み付き辺の重み値とし、前記シーンレベル重み付きグラフを形成し、
前記ビデオシーンセット中の各ビデオシーンの各代表フレームをノードとし、任意の２つのノード間のフレームレベル視覚特徴上の類似度を該２つのノード間の重み付き辺の重み値とし、前記フレームレベル重み付きグラフを形成し、及び、
前記ビデオシーンセット中の各ビデオシーンの各代表フレームの各領域をノードとし、任意の２つのノード間の領域レベル視覚特徴上の類似度を該２つのノード間の重み付き辺の重み値とし、前記領域レベル重み付きグラフを形成することを含む、ビデオ処理方法。
【０１５５】
（付記20）
付記12乃至19の何れか１つに記載のビデオ処理方法であって、
前記関数構築ステップは、
前記シーンレベル重み付きグラフ、前記フレームレベル重み付きグラフ及び前記領域レベル重み付きグラフの構造情報に基づいて、２つのビデオシーンのシーンレベル視覚特徴が類似すればするほど、該２つのビデオシーンのソフトラベル間の差が小さいようにし、２つの代表フレームのフレームレベル視覚特徴が類似すればするほど、該２つの代表フレームのソフトラベル間の差が小さいようにし、及び、２つの領域の領域レベル視覚特徴が類似すればするほど、該２つの領域のソフトラベル間の差を小さいようにするという第一制約条件を設定し、
前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの間の関係に基づいて、負のラベルを持つビデオシーンのソフトラベル、負のラベルを持つビデオシーン中の全ての代表フレームのソフトラベル、及び負のラベルを持つビデオシーン中の全ての代表フレームの全ての領域のソフトラベルが-1にできるだけ接近するようにし、正のラベルを持つビデオシーンのソフトラベルが1にできるだけ接近するようにし、正のラベルを持つビデオシーンに最大ソフトラベルを有する代表フレームのソフトラベルが、該代表フレームが属するビデオシーンのソフトラベルにできるだけ接近するようにし、及び、正のラベルのビデオシーン中の各可能な正例フレームに最大ソフトラベルを有する領域のソフトラベルが、該領域が属する代表フレームのソフトラベルにできるだけ接近するようにするという第二制約条件を設定し、及び、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記ビデオシーンセット中の各ビデオシーンの各代表フレームのソフトラベル、及び前記ビデオシーンセット中の各ビデオシーンの各代表フレームの各領域のソフトラベルを未知量とし、前記第一制約条件及び前記第二制約条件に基づいて、コスト関数を構築することを含む、ビデオ処理方法。
【０１５６】
（付記21）
付記20に記載のビデオ処理方法であって、
前記可能な正例フレームは、そのソフトラベルの値が第五所定閾値よりも高いフレーム、又は、その中にソフトラベルが第六所定閾値よりも高い領域を含むフレームである、ビデオ処理方法。
【０１５７】
（付記22）
付記12乃至21の何れか１つに記載のビデオ処理方法であって、
前記未知量計算ステップは、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル及び前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルに初期値を与え、
前記ビデオシーンセット中の各ビデオシーンのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの現在値に基づいて、前記コスト関数を制約付き最小化問題に変換し、CCCPを用いて該制約付き最小化問題を解き、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの計算値を求め、
前記ビデオシーンセット中の各ビデオシーンのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値に基づいて、前記コスト関数を制約付き最小化問題に変換し、CCCPを用いて該制約付き最小化問題を解き、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの計算値を求め、
前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベルの現在値に基づいて、及び、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値に基づいて、前記コスト関数を用いて計算を行い、前記ビデオシーンセット中の各ビデオシーンのソフトラベルの計算値を求め、
前記ビデオシーンセット中の各ビデオシーンのソフトラベル、前記ビデオシーンセット中の各ビデオシーン中の各代表フレームのソフトラベル、及び前記ビデオシーンセット中の各ビデオシーン中の各代表フレームの各領域のソフトラベルの現在値が収斂になっているかどうかを判断し、前者の場合、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの現在値を前記コスト関数中の未知量の計算値として保存し、後者の場合、前記各ビデオシーンのソフトラベル、前記各代表フレームのソフトラベル及び前記各領域のソフトラベルの現在値が収斂になっていると判断するまでに、再び反復計算を行い、前記各領域のソフトラベルの計算値、前記各代表フレームのソフトラベルの計算値及び前記各ビデオシーンのソフトラベルの計算値をそれぞれ順次計算することを含む、ビデオ処理方法。
【０１５８】
（付記23）
付記1乃至11の何れか１つに記載のビデオ処理装置を含む設備。
【０１５９】
（付記24）
付記23に記載の設備であって、
前記設備は、カメラ、ビデオカメラ、コンピュータ、携帯電話、パーソナルデジタルアシスタント、又はマルチメディア処理設備である、設備。
【０１６０】
（付記25）
コンピュータに、付記12乃至22の何れか１つに記載の方法の各ステップを実行させるためのプログラム。
【０１６１】
（付記26）
付記25に記載のプログラムを記録しているコンピュータ読み出し可能な記憶媒体。
【０１６２】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術の範囲に属する。
【図１】
0006015504.tif 000062
【図２】
0006015504.tif 000063
【図３】
0006015504.tif 000064
【図４】
0006015504.tif 000065
【図５】
0006015504.tif 000066
【図６】
0006015504.tif 000067
【図７】
0006015504.tif 000068
【図８】
0006015504.tif 000069
【図９】
0006015504.tif 000070