(57)【要約】【課題】コンテンツ集合が含む代表的なコンセプトを可能な限り包含した質の高い要約を出力することができるコンテンツ要約装置を提供する。【解決手段】複数画像から構成されるコンテンツ集合を入力する入力手段と、入力されたコンテンツ集合から、要約に含まれる候補となる要約要素を生成する要約要素定義手段と、得られた要約要素それぞれに帰属する概念的要素単位であるコンセプトを抽出し、該コンセプト毎の代表度を算出するコンセプト抽出手段と、得られた要約要素それぞれに帰属するコンセプトおよびコンセプト毎の代表度に基づき、重要なコンセプトを最大限含むような部分集合を選択する最適化処理手段と、選択した部分集合をコンテンツ集合の要約として出力する出力手段とを備える。【選択図】図１
2015001834.tif 000002
【特許請求の範囲】
【請求項１】
複数画像から構成されるコンテンツ集合を入力する入力手段と、
入力された前記コンテンツ集合から、要約に含まれる候補となる要約要素を生成する要約要素定義手段と、
得られた前記要約要素それぞれに帰属する概念的要素単位であるコンセプトを抽出し、該コンセプト毎の代表度を算出するコンセプト抽出手段と、
得られた前記要約要素それぞれに帰属するコンセプトおよびコンセプト毎の前記代表度に基づき、重要なコンセプトを最大限含むような部分集合を選択する最適化処理手段と、
選択した前記部分集合を前記コンテンツ集合の要約として出力する出力手段と
を備えることを特徴とするコンテンツ要約装置。
【請求項２】
前記コンセプト抽出手段は、
前記コンテンツ集合の各要素の見た目の特徴に基づく画像コンセプト要素抽出手段と、前記コンテンツ集合の各要素の音の特徴に基づく音コンセプト要素抽出手段と、前記コンテンツ集合の各要素のメタデータの特徴に基づくメタデータコンセプト要素抽出手段とのうち、少なくとも一つを含むことを特徴とする請求項１に記載のコンテンツ要約装置。
【請求項３】
前記画像コンセプト要素抽出手段または前記音コンセプト要素抽出手段は、
予め用意されたコンセプト要素識別器に基づいて、各コンセプト要素への帰属度から構成される帰属度ベクトルを各要約要素について算出するコンセプト要素帰属度算出手段と、
得られた前記コンセプト要素帰属度ベクトルの集合からスパースな表現を与える基底関数を学習し、各要約要素に帰属するコンセプトを決定するスパース表現手段と、
得られた前記基底関数および各帰属度ベクトルとから、各コンセプトの前記代表度を算出するコンセプト代表度算出手段と
を含むことを特徴とする請求項２に記載のコンテンツ要約装置。
【請求項４】
前記最適化処理手段は、
決定された前記要約要素それぞれに帰属するコンセプトおよび各コンセプトの前記代表度を用いて最適化処理を行うことを特徴とする請求項３に記載のコンテンツ要約装置。
【請求項５】
入力されたコンテンツ集合の要約を作成するコンテンツ要約装置が行うコンテンツ要約方法であって、
複数画像から構成されるコンテンツ集合を入力する入力ステップと、
入力された前記コンテンツ集合から、要約に含まれる候補となる要約要素を生成する要約要素定義ステップと、
得られた前記要約要素それぞれに帰属する概念的要素単位であるコンセプトを抽出し、該コンセプト毎の代表度を算出するコンセプト抽出ステップと、
得られた前記要約要素それぞれに帰属するコンセプトおよびコンセプト毎の前記代表度に基づき、重要なコンセプトを最大限含むような部分集合を選択する最適化処理ステップと、
選択した前記部分集合を前記コンテンツ集合の要約として出力する出力ステップと
を有することを特徴とするコンテンツ要約方法。
【請求項６】
コンピュータを、請求項１から４のいずれか１項に記載のコンテンツ要約装置として機能させるためのコンテンツ要約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像などのコンテンツを要約するコンテンツ要約装置、コンテンツ要約方法及びコンテンツ要約プログラムに関する。
【背景技術】
【０００２】
インターネットを介してユーザがアクセス可能な画像・映像コンテンツは膨大な数にのぼる。例えばある画像共有サイトでは、６０億枚もの画像が既にアップロードされていると報告されており、またある動画共有サイトでは、１分間に７２時間分もの動画が新たにアップロードされているとの報告がある。
【０００３】
このような、膨大な数が既に存在し、また爆発的に増加し続けている画像・映像コンテンツ群を俯瞰したり、その概要を短時間で把握したりすることを可能にする技術として、種々の画像群要約技術・映像要約技術が提案されている。例えば、複数の映像をまとめて要約処理にかけ、可能な限り冗長性を排除した一本の要約映像を生成する技術がある（例えば、特許文献１参照）。また、要約対象の各画像から得られる特徴量に基づき類似画像をクラスタリングでまとめ、各クラスタ内画像が共有する物体や景観を代表画像領域として抽出し、それらから構成される要約を生成する技術がある（例えば、非特許文献１参照）。また、タグが付与された複数の映像から、見た目とタグに基づく特徴量を算出し、それらから算出される要素間類似度に基づいて、クラスタリングおよび要約を行う技術がある（例えば、非特許文献２参照）。
【０００４】
ここで、膨大な数の画像・映像コンテンツの俯瞰・短時間での概要把握を可能にする要約に求められる要件について考える。要件を満たす理想的な要約は、限られた要約サイズのなかで、コンテンツ全体の内容を可能な限り含んでいるべきである。同時に、例えばコンテンツ全体の中で出現頻度の高い内容といった、いわゆる「代表的な」コンテンツが要約に盛り込まれているべきである。コンテンツの内容は様々な観点から定義できるが、例えば画像中に映った被写体（「海」「ボール」など）や、風景写真や肖像画といった画像の表現形式、映像中の音楽や発話や特徴的な音イベント、付与されたタグ等のメタデータといった要素から構成される「概念」を可能な限り多く含むような要約は、要件を満たす要約の指標の一つであると言える。この概念をコンセプトと定義するならば、膨大なコンテンツの俯瞰・短時間での概要把握を可能とする要約は、代表的なコンセプトを可能な限り多く含んでいるべきであると言うことができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２−１９３０５号公報
【非特許文献】
【０００６】
【非特許文献１】C.-H. Li, C.-Y. Chiu, C.-R. Huang, C.-S. Chen, and L.-F. Chien: Image Content Clustering and Summarization for Photo Collections, In Proc. ICME, pp.1033-1036, 2006
【非特許文献２】W.-T. Chu, C.-C. Huang, W.-F. Cheng, News Story Clustering from Both What and How Aspects: Using Bag of Word Model and Affinity Propagation, in Proc. AIEMPro, pp.7-12, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に記載の技術にあっては、得られる要約の冗長性排除については考慮されているものの、要約に含まれる内容の代表性が考慮されていないという問題がある。したがって、得られる要約は、コンテンツ集合のなかで代表度の低い内容ばかりを含んだものとなる可能性がある。
【０００８】
一方、非特許文献１および非特許文献２では、類似要素をクラスタリングでまとめるという処理が行われているため、コンテンツ集合全体の内容包含という要件について、一定の考慮はなされている。しかし、非特許文献１で行われているクラスタリングは、Ｌｏｗ−ｌｅｖｅｌな特徴量に基づくものである。Ｌｏｗ−ｌｅｖｅｌな特徴量とコンセプトとの間には、いわゆるセマンティックギャップと呼ばれる溝が存在することが指摘されている。したがってＬｏｗ−ｌｅｖｅｌな特徴量を考慮したのみでは、コンテンツ集合に含まれるコンセプトを包含するという観点での最適化がなされておらず、各コンセプトの代表度も考慮されていないという問題がある。
【０００９】
また、非特許文献２では、タグに基づく特徴が考慮されているため、コンセプトの包含という観点では非特許文献１よりも質の高い要約が生成できると考えられる。しかしながらタグは基本的に人手により付与されるものであるため、コンテンツに帰属するコンセプトの網羅性とその質は保証されていないという問題がある。また、非特許文献２においても、各コンセプトの代表度はなんら考慮されてはいない。
【００１０】
以上から、先行技術によって得られる要約では、元のコンテンツ集合に含まれる代表的なコンセプトを可能な限り含んでいるべきであるという観点に立ったとき、必ずしも質の高い要約が得られないという問題がある。
【００１１】
本発明は、このような事情に鑑みてなされたもので、コンテンツ集合が含む代表的なコンセプトをより多く包含した要約を出力することができるコンテンツ要約装置、コンテンツ要約方法及びコンテンツ要約プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、複数画像から構成されるコンテンツ集合を入力する入力手段と、入力された前記コンテンツ集合から、要約に含まれる候補となる要約要素を生成する要約要素定義手段と、得られた前記要約要素それぞれに帰属する概念的要素単位であるコンセプトを抽出し、該コンセプト毎の代表度を算出するコンセプト抽出手段と、得られた前記要約要素それぞれに帰属するコンセプトおよびコンセプト毎の前記代表度に基づき、重要なコンセプトを最大限含むような部分集合を選択する最適化処理手段と、選択した前記部分集合を前記コンテンツ集合の要約として出力する出力手段とを備えることを特徴とする。
【００１３】
本発明は、前記コンセプト抽出部は、前記コンテンツ集合の各要素の見た目の特徴に基づく画像コンセプト要素抽出手段と、前記コンテンツ集合の各要素の音の特徴に基づく音コンセプト要素抽出手段と、前記コンテンツ集合の各要素のメタデータの特徴に基づくメタデータコンセプト要素抽出手段とのうち、少なくとも一つを含むことを特徴とする。
【００１４】
本発明は、前記画像コンセプト要素抽出手段または前記音コンセプト要素抽出手段は、予め用意されたコンセプト要素識別器に基づいて、各コンセプト要素への帰属度から構成される帰属度ベクトルを各要約要素について算出するコンセプト要素帰属度算出手段と、得られた前記コンセプト要素帰属度ベクトルの集合からスパースな表現を与える基底関数を学習し、各要約要素に帰属するコンセプトを決定するスパース表現手段と、得られた前記基底関数および各帰属度ベクトルとから、各コンセプトの前記代表度を算出するコンセプト代表度算出手段とを含むことを特徴とする。
【００１５】
本発明は、前記最適化処理手段は、決定された前記要約要素それぞれに帰属するコンセプトおよび各コンセプトの前記代表度を用いて最適化処理を行うことを特徴とする。
【００１６】
本発明は、入力されたコンテンツ集合の要約を作成するコンテンツ要約装置が行うコンテンツ要約方法であって、複数画像から構成されるコンテンツ集合を入力する入力ステップと、入力された前記コンテンツ集合から、要約に含まれる候補となる要約要素を生成する要約要素定義ステップと、得られた前記要約要素それぞれに帰属する概念的要素単位であるコンセプトを抽出し、該コンセプト毎の代表度を算出するコンセプト抽出ステップと、得られた前記要約要素それぞれに帰属するコンセプトおよびコンセプト毎の前記代表度に基づき、重要なコンセプトを最大限含むような部分集合を選択する最適化処理ステップと、選択した前記部分集合を前記コンテンツ集合の要約として出力する出力ステップとを有することを特徴とする。
【００１７】
本発明は、コンピュータを、前記コンテンツ要約装置として機能させるためのコンテンツ要約プログラムである。
【発明の効果】
【００１８】
本発明によれば、コンテンツ集合が含む代表的なコンセプトをより多く包含した要約を出力することができるという効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１実施形態の構成を示すブロック図である。
【図２】図１に示すコンテンツ要約装置１の動作を示すフローチャートである。
【図３】図１に示す画像コンセプト抽出部１４とメタデータコンセプト抽出部１５の動作を示す図である。
【図４】図１に示す最適化処理部１６の処理動作を示す図である。
【図５】本発明の第２実施形態の構成を示すブロック図である。
【図６】図５に示すコンテンツ要約装置１の動作を示すフローチャートである。
【図７】図５に示す画像／音コンセプト抽出部１４ａの動作を図である。
【発明を実施するための形態】
【００２０】
＜第１実施形態＞
以下、図面を参照して、本発明の第１実施形態によるコンテンツ要約装置を説明する。図１は同実施形態の構成を示すブロック図である。この図において、符号１は、コンピュータ装置で構成するコンテンツ要約装置である。符号２は、要約を作成する対象のコンテンツ集合である。符号３は、コンテンツ要約装置１の出力である要約コンテンツである。
【００２１】
符号１１は、コンテンツ集合２を入力する入力部である。符号１２は、入力部１１において入力したコンテンツ集合を記憶しておく記憶部である。符号１３は、要約要素の定義を行う要約要素定義部である。符号１４は、画像のコンセプトを抽出する画像コンセプト抽出部である。符号１４１は、コンセプト要素の帰属度を算出するコンセプト要素帰属度算出部である。符号１４２は、スパース表現を行うスパース表現部である。符号１４３は、コンセプトの代表度を算出するコンセプト代表度算出部である。符号１５は、メタデータのコンセプトを抽出するメタデータコンセプト抽出部である。符号１６は、最適化処理を行う最適化処理部である。符号１７は、要約コンテンツを出力する出力部である。
【００２２】
第１実施形態によるコンテンツ要約装置は、見た目（画像）の特徴とメタデータの特徴に基づく画像群の要約を行う。ここでは、コンテンツ集合として画像群が与えられたときに、画像群の内容を俯瞰することが可能であるような画像群の部分集合（Ｋ枚の画像）を要約として出力する。以下ではコンセプト抽出のために見た目の特徴（画像特徴）および各画像に付与されているメタデータ特徴に基づいて要約コンテンツを作成する。
【００２３】
なお、本明細書において、画像とは、静止画像、または動画像を構成する１フレーム分の画像のことをいう。また映像とは、動画像とそれに同期する音声から構成されるものである。
【００２４】
次に、図２を参照して、図１に示すコンテンツ要約装置１の動作を説明する。図２は、図１に示すコンテンツ要約装置１の動作を示すフローチャートである。まず、入力部１１は、要約対象のコンテンツ集合を入力し、記憶部１２に記憶する（ステップＳ１）。このとき入力されるコンテンツ集合を構成する各画像には、メタデータとしてタグが付与されているものとする。
【００２５】
次に、要約要素定義部１３は、記憶部１２に記憶された画像群に基づき、要約要素ｖｉ∈Ｖを定義する（ステップＳ２）。ｖｉは要約に含まれうる要素であり、Ｖは要約要素の集合全体を表す。後述する最適化処理部１６において解くべき問題は、予め指定された要約サイズＫ（ここでは、Ｋは画像の枚数）のもとで目的関数を最大化するような要素集合Ｖの部分集合Ｖ＊を選択する問題として定義することができる。本実施形態では、各要約要素ｖｉは入力部１１において入力された各画像と対応づけるものとする。
【００２６】
次に、画像コンセプト抽出部１４は、要約要素定義部１３において定義された各要約要素ｖｉに帰属するコンセプトを抽出する。ここでいうコンセプトの抽出とは、予め決めておいたコンセプト集合Ｃに含まれる各コンセプトｃｊ∈Ｃに、各要約要素ｖｉがどの程度帰属するかを算出することを指す。以下では、要約要素について算出されたコンセプトへの帰属度合を、要約要素に対するコンセプトの帰属度と定義する。
【００２７】
各要約要素に対する各コンセプトの帰属度は、コンテンツ集合から得られるいくつかの情報に基づいて算出することができる。本実施形態では、コンテンツ集合に含まれる各要素から得られる見た目の特徴（以下、画像特徴という）、音の特徴（以下、音特徴という）、付与されているメタデータの特徴（以下、メタデータ特徴という）のうち、少なくとも一つ以上を用いてコンセプトの帰属度を算出する。
【００２８】
コンセプトの抽出処理では、まず、コンセプト要素帰属度算出部１４１がコンセプト要素の帰属度を算出する（ステップＳ３）。ここでいうコンセプト要素とは、画像中に含まれる物体や、画像が捉えているイベントのことであり、例えば「山」、「ボール」、「スイミング」といったものを挙げることができる。コンセプトは、これらのコンセプト要素を少なくとも一つ以上含む集合として定義される。一般的に、用意するコンセプト要素の数が多いほど、検出可能なコンセプトの多様性が増すことが知られている。ここでも例外ではなく、予め定義されたコンセプト要素集合は十分な数のコンセプト要素から構成されていることが望ましい。画像が各コンセプト要素に帰属するか否かは、識別器を用いて判断することができる。
【００２９】
識別器はコンセプト要素毎に一つ用意され、画像の特徴量を入力として、その画像があるコンセプト要素に帰属しているか否かを帰属レベルとして出力する。識別器は予め学習して獲得しておくものであり、決められた画像特徴、例えば（参考文献１）で開示されているＳＩＦＴのような局所特徴と、その画像がどのコンセプト要素に帰属しているかを人手で判定した正解ラベルとの関係を学習することで獲得する。
参考文献１:D. Lowe, Distinctive Image Features from Scale-invariant Keypoints, International Journal on Computer Vision, Vol. 60 pp.91-110, 2004.
【００３０】
学習器としては、例えばサポートベクターマシンなどを用いればよい。これにより、各要約要素ｖｉに対して、予め定義したコンセプト要素の数の次元を持つ帰属ベクトルｙｉが得られる。ここで、帰属ベクトルｙｉの各要素ｙｉｊは、識別器によって得られるコンセプト要素ｅｊに対する要約要素ｖｉの帰属度を表す。
【００３１】
次に、スパース表現部１４２は、スパース表現を行うことで各コンセプトｃｊに対する要約要素ｖｉの帰属度を算出する（ステップＳ４）。ここで各コンセプトは、コンセプト要素の集合として定義されるが、各画像に実際に出現している各コンセプトは、コンセプト集合に含まれるコンセプトの総数に比べ十分少ない可能性が高いと考えられる。前述の例を用いるならば、「山」と「スイミング」のコンセプト要素が同時に出現するような画像が経験的に非常に稀であることを考えると、「山」と「スイミング」各々を要素に含むコンセプトが同時に出現することは稀であることは明らかである。
【００３２】
そこで、要約要素集合Ｖに含まれる各要約要素ｖｉに対応する帰属ベクトルｙｉからスパースな表現を与える基底関数Ｄを学習し、各要約要素ｖｉの各コンセプトへの帰属度を表したコンセプト帰属ベクトルαｉを推定する。コンセプト帰属ベクトルαｉは疎なベクトルであり、その次元数はあらかじめ定義したコンセプトの数に等しい。疎なベクトルを推定する方法としては、例えば以下の（１）式で定式化されるスパースコーディングを用いればよい。
【数１】
2015001834.tif 000003
【００３３】
上式の目的関数は、ＮＰ困難であることが知られている。スパースコーディングを解くアルゴリズムは様々なものが提案されており、例えば以下の（参考文献２）で開示されているfeature-signアルゴリズムを用いることができる。ここで得られたαｉが続く処理で用いられる要約要素ｖｉのコンセプト帰属ベクトルである。
参考文献２：H. Lee et al., Efficient Sparse Coding Algorithms, in Proc. NIPS, 19, 2007
【００３４】
次に、コンセプト代表度算出部１４３は、スパース表現部１４２において得られたコンセプト帰属ベクトルαｉを用いて、各コンセプトｃｊの代表度ｗｊを算出する（ステップＳ５）。各コンセプトの代表度は、該当コンセプトに属する帰属度の高い要約要素が多く存在するものほど高い値をとる値として定義される。実際に代表度ｗｊ算出する方法は様々なものが適用できるが、例えば（２）式のようにコンセプトｃｊに対応する疎ベクトルαｉの要素αｉｊを、全ての要約要素に対して加算することで算出することができる。
【数２】
2015001834.tif 000004
【００３５】
次に、メタデータコンセプト抽出部１５は、画像に付随するメタデータからコンセプトを抽出する（ステップＳ６）。タグからのコンセプト抽出は、タグそのものがコンセプトを表現したものと捉えることができるため、各画像に付与された各タグを、画像の帰属コンセプトと捉えればよい。タグの重要度については、各タグの出現頻度に基づいてその重要度を算出することができる。重要度が低いタグについては、一定の閾値に基づいてフィルタリングを行うなどすればよい。
【００３６】
ここで、画像コンセプト抽出部１４とメタデータコンセプト抽出部１５の動作を図３を参照して説明する。図３は、画像コンセプト抽出部１４とメタデータコンセプト抽出部１５の動作を示す図である。図３に示すように、コンテンツ集合の中にコンテンツＡ、Ｂ、Ｃ、Ｄがあり、それぞれにメタデータが付随している。コンセプト要素帰属度算出部１４１は、画像に基づくコンセプト要素帰属度を算出する。続いて、スパース表現部１４２は、スパース表現を行うことでコンセプト帰属度を算出する。そして、コンセプト代表度算出部１４３は、コンセプト代表値を算出する。一方、メタデータコンセプト抽出部１５は、メタデータからコンセプト代表値を算出する。
【００３７】
この処理によって、コンテンツＡについて、コンセプト１、２、３が抽出され、それぞれのコンセプトの代表度ｗ１，ｗ２，ｗ３が得られる。同様に、コンテンツＢについて、コンセプト３、４が抽出され、それぞれのコンセプトの代表度ｗ３，ｗ４が得られる。また、コンテンツＣについて、コンセプト３、４、５が抽出され、それぞれのコンセプトの代表度ｗ３，ｗ４，ｗ５が得られる。さらに、コンテンツＤについて、コンセプト１、２が抽出され、それぞれのコンセプトの代表度ｗ１，ｗ２が得られる。
【００３８】
図３に示すように、コンテンツの見た目（画像特徴）については、まず各要素の特徴に基づき、予め定義しておいた各コンセプトへの帰属度を算出する。このとき要約の質を高めるためには、コンセプトは十分な数定義しておくことが望ましいが、一方で各要素が実際に帰属するコンセプトは、そのごく一部であると考えられる。そこで、各要素が帰属するコンセプトが、予め定義されたコンセプトの数に比べスパースであるという仮定のもと、各要素で定義されるコンセプト要素帰属ベクトルの集合からスパースな表現を与える基底関数を学習し、各要素に対する各要素のコンセプト帰属度を精度よく算出し、更には得られたコンセプトへの帰属度に基づき各コンセプトの代表度を算出する。これとメタデータ特徴に基づき得られたコンセプトとを統合することで、各要素が帰属するコンセプトを高い精度で算出する。
【００３９】
図２に戻り、次に、最適化処理部１６は、見た目の特徴に基づくコンセプトとタグに基づくコンセプトを統合し最適化処理を行う（ステップＳ７）。その際に用いる各コンセプトの代表度は、特徴毎に正規化することとする。正規化には任意の方法を用いることが可能であり、例えば各特徴の重要度の標準偏差を求め、その値で代表度を割った値を新たな代表度として用いればよい。
【００４０】
最適化処理部１６は、画像コンセプト抽出部１４とメタデータコンセプト抽出部１５において得られた各要約要素ｖｉに帰属するコンセプトおよび各コンセプトの代表度に基づいて、一定の要約サイズの中で代表的なコンセプトを可能な限り被覆することが可能な集合Ｖの部分集合Ｖ＊を出力する。変数ｘｉをｖｉが要約に含まれていたら１、含まれていなければ０をとる決定変数とおけば、Ｖ＊はｘｉが１をとるようなｖｉの集合として定義することができ、Ｖ＊は組合せ最適化を解くことによって得られることがわかる。ここで解く最適化の目的関数は、重要なコンセプトを可能な限り被覆することを実現するものであれば任意のものを用いることが可能である。例えば目的関数とその制約条件は（３）式のように定義することができる。
【数３】
2015001834.tif 000005
【００４１】
ここで、ｊ番目のコンセプトｅｊの重要度をｗｊ、要約要素をｖｉ∈Ｖ、ｚｊをコンセプトｅｊが要約に含まれる画像のいずれかに含まれる場合は１、そうでなければ０をとる決定変数とする。ａｉｊはコンセプトｅｊが要約要素ｖｉに含まれている場合は１であり、そうでない場合はゼロをとる。
【００４２】
この問題は、要約サイズＫのもと目的関数を最大化するナップサック制約付き最大被覆問題として知られている。この問題はＮＰ困難問題であるため、特に要素集合Ｖの要素数が大きい場合実時間で最適解を得ることは難しい。しかしながらナップサック制約付き最大被覆問題の近似解を得る公知のアルゴリズムはいくつか存在する（参考文献３〜６）ため、それらを用いればよい。
参考文献３：E. Filatova et al., A Formal Model for Information Selection in Multi-sentence Text Extraction, in Proc. COLING, pp.397-403, 2004
参考文献４：S. Khuller et al., The Budgeted Maximum Coverage Problem, Information Processing Letters, Vol. 70, No.1, pp39-45, 1999
参考文献５：W. Yih et al., Multi-document Summarization by Maximizing Informative Content-Words, in Proc. IJCAI, pp.1776-1782, 2007
参考文献６：S. Khuller et al., Randomized Rounding for Maximum Coverage Problem and Mimum Set Cover with Threshold Problem, Technical Report CS-TR-4805, The University of Maryland, 2006
【００４３】
これらのアルゴリズムを用いることにより、目的関数を最大化する決定変数ｘｉを得ることができ、これにより部分集合Ｖ＊を出力することができる。
【００４４】
ここで、最適化処理部１６の処理動作を図４を参照して説明する。図４は、最適化処理部１６の処理動作を示す図である。図３に示す処理によって、コンテンツＡ、Ｂ、Ｃ、Ｄのそれぞれについて、コンセプトの抽出と代表度の算出ができると、最適化処理部１６は、部分集合と被覆コンセプトの対毎にスコアを求める。図４に示す例では、要約サイズを２とした場合、部分集合Ａ，Ｃ、被覆コンセプトｗ１，ｗ２，ｗ３，ｗ５，ｗ６がスコア１．５となり最も高くなる。この部分集合（図４において、破線で囲った部分）、すなわち、コンテンツＡ，Ｃ、被覆コンセプト１，２，３，５，６が要約として得られることになる。
【００４５】
図２に戻り、次に、出力部１７は、最適化処理部１６において得られた部分集合Ｖ＊を出力する（ステップＳ８）。本実施形態ではＶ＊の各要素は画像であるため、Ｖ＊に含まれる全画像をディスプレイ上に一覧表示するなどすればよい。画像の並び順は、任意の方法でランキングした結果を用いることで決定することができる。例えば代表度の高いコンセプトを多く含む画像から順に表示するのであれば、以下の（４）式で得られるスコアｓｉに基づいてｖ＊ｉ∈Ｖ＊をランキングすればよい。
【数４】
2015001834.tif 000006
ここでδ（αｉｊ＞０）は、αｉｊが非負であったときに１、そうでなければゼロをとる値である。
【００４６】
このように、出力部１７から部分集合Ｖ＊を出力することにより、要約コンテンツ３を出力することが可能となり、コンテンツ集合を要約した要約コンテンツを得ることができる。
【００４７】
＜第２実施形態＞
次に、本発明の第２実施形態によるコンテンツ要約装置を説明する。図５は同実施形態の構成を示すブロック図である。この図において、図１に示す装置と同一の部分には同一の符号を付し、その説明を簡単に行う。図５に示す装置が図１に示す装置と異なる点は、画像コンセプト抽出部１４、メタデータコンセプト抽出部１５に代えて、画像／音コンセプト抽出部１４ａが設けられている点である。第２実施形態では、見た目の特徴、音の特徴に基づく映像の要約を行う。本実施形態では、コンテンツ集合として一つ以上の映像が与えられたときに、それら映像の概要を短時間で視聴可能な映像の部分集合（映像長Ｋ以下）を要約として出力する。以下ではコンセプト抽出のために見た目の特徴（画像特徴）および音の特徴に基づいて要約コンテンツを作成する。
【００４８】
次に、図６を参照して、図５に示すコンテンツ要約装置１の動作を説明する。図６は、図５に示すコンテンツ要約装置１の動作を示すフローチャートである。まず、入力部１１は、要約対象のコンテンツ集合を入力し、記憶部１２に記憶する（ステップＳ１１）。このとき、入力されるコンテンツの映像にはタグなどのメタデータがついていてもよい。
【００４９】
次に、要約要素定義部１３は、記憶部１２に記憶された一つ以上の映像から、要約要素ｖｉ∈Ｖを定義する（ステップＳ１２）。ｖｉは要約に含まれうる要素であり、Ｖは要約要素の集合全体を表す。後述する最適化処理部１６において解くべき問題は、予め指定された要約サイズＫ（ここでは、Ｋは映像長）のもとで目的関数を最大化するような要素集合Ｖの部分集合Ｖ＊を選択する問題として定式化することができる。本実施形態では、記憶部１２に記憶された各映像を分割し、得られた各映像区間をｖｉと定義する。各映像を映像区間群に分割する方法は様々なものを用いることが可能であり、例えば一定の時間間隔で分割する方法や、（参考文献７）に開示されている、見た目が大きく切り替わる部分で分割するといった方法を用いることができる。
参考文献７：Y. Tonomura, A. Akutsu, Y. Taniguchi and G. Suzuki: Structured Video Computing, IEEE Multimedia, pp.34-43, 1994.
【００５０】
次に、画像／音コンセプト抽出部１４ａは、要約要素定義部１３において定義された各要約要素ｖｉに帰属するコンセプトを抽出する。ここでいうコンセプトの抽出とは、予め決めておいたコンセプト集合Ｃに含まれる各コンセプトｃｊ∈Ｃに、要約要素がどの程度帰属するかを算出することを指す。以下では、要約要素について算出されたコンセプトへの帰属度合を、要約要素に対するコンセプトの帰属度と定義する。
【００５１】
各要約要素に対する各コンセプトの帰属度は、コンテンツ集合から得られるいくつかの情報に基づいて算出することができる。本実施形態では、コンテンツ集合に含まれる各要素から得られる見た目の特徴（以下、画像特徴）、音の特徴（以下、音特徴）、付与されているメタデータの特徴（以下、メタデータ特徴）のうち、少なくとも一つ以上を用いてコンセプトの帰属度を算出する。
【００５２】
コンセプトの抽出処理では、まず、コンセプト要素帰属度算出部１４１がコンセプトの帰属度を算出する（ステップＳ１３）。ここでいうコンセプトとは、映像中に含まれる物体や音、映像が捉えているイベントを指す。見た目から定義可能なコンセプトとして、例えば「山」、「ボール」、「スイミング」といったものを挙げることができる。音から定義可能なコンセプトとしては「笑い声」「（爆発音などの）突発音」「会話」といったものを挙げることができる。一般的に、用意するコンセプト要素の数が多いほど、検出可能なコンセプトの多様性が増すことが知られている。ここでも例外ではなく、予め定義されたコンセプト集合は十分な数のコンセプトから構成されていることが望ましい。画像が各コンセプトに帰属するか否かは、識別器を用いて判断することができる。
【００５３】
識別器は、要約要素から得られる特徴量を入力として、その映像区間があるコンセプト要素に帰属しているか否かを帰属レベルとして出力する。識別器は予め学習して獲得しておく。本実施形態における要約要素は、一定の時間長を有する映像区間であるが、この要約要素から得られる特徴量は、見た目から得られる特徴量（画像特徴）および音から得られる特徴量（音特徴量）を挙げることが可能で、これらのうち少なくとも一つ以上を用いて識別器の学習を行う。映像区間から画像特徴を得る方法は任意の方法を用いることが可能であり、例えば映像区間の先頭キーフレームを代表画像とし、（参考文献１）で開示されているＳＩＦＴのような局所特徴の抽出を行えばよい。
参考文献１（再掲）：D. Lowe, Distinctive Image Features from Scale-invariant Keypoints, International Journal on Computer Vision, Vol. 60 pp.91-110, 2004.
【００５４】
音特徴の抽出も任意の方法を用いることが可能であり、例えば映像区間開始から一定時間の音声波形からＭＦＣＣのような音声特徴量を抽出すればよい。これらから得られた少なくとも一つ以上の特徴と、その映像区間がどのコンセプトに帰属しているかを人手で判定した正解ラベルとの関係を学習することで、識別器を構築することができる。識別器としては、例えばサポートベクターマシンなどを用いればよい。特徴は画像特徴と音特徴を個々に評価して識別器を構築してもよいし、あるいは（参考文献８）に開示される技術を用い、画像特徴と音特徴を同時に考慮して識別器を構築してもよい。得られた識別器群を各要約要素ｖｉに施すことによって、予め定義したコンセプト要素の数の次元を持つ帰属ベクトルｙｉが得られる。ここで、帰属ベクトルｙｉの各要素ｙｉｊは、識別器によって得られるコンセプト要素ｅｊに対する要約要素ｖｉの帰属度を表す。
参考文献８：  M. Gonen, Multiple Kernel Learning Algorithms, Journal of Machine Learning Research, Vol. 12, pp.2211-2268, 2011
【００５５】
次に、スパース表現部１４２は、スパース表現を行うことで各コンセプトｃｊに対する要約要素ｖｉの帰属度を算出する（ステップＳ４）。ここで各コンセプトは、コンセプト要素の集合として定義されるが、各画像に実際に出現している各コンセプトは、コンセプト集合に含まれるコンセプトの総数に比べ十分少ない可能性が高いと考えられる。前述の例を用いるならば、「山」と「スイミング」のコンセプト要素が同時に出現するような画像が経験的に非常に稀であることを考えると、「山」と「スイミング」各々を要素に含むコンセプトが同時に出現することは稀であることは明らかである。
【００５６】
そこで、要約要素集合Ｖに含まれる各要約要素ｖｉに対応する帰属ベクトルｙｉからスパースな表現を与える基底関数Ｄを学習し、各要約要素ｖｉの各コンセプトへの帰属度を表したコンセプト帰属ベクトルαｉを推定する。コンセプト帰属ベクトルαｉは疎なベクトルであり、その次元数はあらかじめ定義したコンセプトの数に等しい。疎なベクトルを推定する方法としては、例えば以下の（１）式で定式化されるスパースコーディングを用いればよい。
【数５】
2015001834.tif 000007
【００５７】
上式の目的関数はＬ０ノルムの最小化となっており、これはＮＰ困難であることが知られている。スパースコーディングを解くアルゴリズムは様々なものが提案されており、例えば以下の（参考文献２）で開示されているfeature-signアルゴリズムを用いることができる。ここで得られたαｉが続く処理で用いられる要約要素ｖｉのコンセプト帰属ベクトルである。
参考文献２（再掲）：H. Lee et al., Efficient Sparse Coding Algorithms, in Proc. NIPS, 19, 2007
【００５８】
なお、本実施形態において、一つの要約要素からは画像特徴および音特徴を抽出することが可能である。そのため、要約要素あたりに複数の識別器が構築された場合、得られる疎ベクトルもまた複数要素あたりに複数定義される。以下では、要約要素あたりに定義される疎ベクトルの数をＮｆとして、疎ベクトル群を｛αｋｉ｝＾（Ｎｆ）＿（ｋ＝０）とする。
【００５９】
次に、コンセプト代表度算出部１４３は、スパース表現部１４２において得られた疎ベクトル群｛αｋｉ｝＾（Ｎｆ）＿（ｋ＝０）を用いて、各コンセプトｃｊの代表度ｗｊを算出する（ステップＳ１５）。各コンセプトの代表度は、該当コンセプトに属する帰属度の高い要約要素が多く存在するものほど高い値をとる値として定義される。実際に代表度ｗｊ算出する方法は様々なものが考えられるが、例えば、（５）式のようにコンセプトｃｊに対応する疎ベクトルαｋｉの要素αｋｉｊを、全ての要約要素および全疎ベクトルに対して加算することで算出することができる。
【数６】
2015001834.tif 000008
【００６０】
ここで、画像コンセプト抽出部１４とメタデータコンセプト抽出部１５の動作を図７を参照して説明する。図７は、画像／音コンセプト抽出部１４ａの動作を図である。図７に示すように、コンテンツ集合の中にコンテンツＡ、Ｂ、Ｃ、Ｄがあり、それぞれにメタデータが付随している。コンセプト帰属度算出部１４１は、画像に基づくコンセプト帰属度を算出する。続いて、スパース表現部１４２は、帰属度ベクトルのスパース表現を行う。そして、コンセプト代表度算出部１４３は、コンセプト代表値を算出する。
【００６１】
この処理によって、コンテンツＡについて、コンセプト１、２、３が抽出され、それぞれのコンセプトの代表度ｗ１，ｗ２，ｗ３が得られる。同様に、コンテンツＢについて、コンセプト３、４が抽出され、それぞれのコンセプトの代表度ｗ３，ｗ４が得られる。また、コンテンツＣについて、コンセプト３、４、５が抽出され、それぞれのコンセプトの代表度ｗ３，ｗ４，ｗ５が得られる。さらに、コンテンツＤについて、コンセプト１、２が抽出され、それぞれのコンセプトの代表度ｗ１，ｗ２が得られる。
【００６２】
図７に示すように、コンテンツの見た目（画像特徴）および音（音特徴）については、まず各要素の特徴に基づき、予め定義しておいた各コンセプトへの帰属度を算出する。このとき要約の質を高めるためには、コンセプトは十分な数定義しておくことが望ましいが、一方で各要素が実際に帰属するコンセプトは、そのごく一部であると考えられる。そこで、各要素が帰属するコンセプトが、予め定義されたコンセプトの数に比べスパースであるという仮定のもと、各要素で定義されるコンセプト要素帰属ベクトルの集合からスパースな表現を与える基底関数を学習し、得られた基底関数から、各要素に対するコンセプト帰属度を精度よく算出し、更には得られたコンセプト帰属度に基づき各コンセプトの代表度を算出する。
【００６３】
図６に戻り、次に、最適化処理部１６は、最適化処理を行う（ステップＳ１６）。最適化処理部１６は、画像／音コンセプト抽出部１４ａにおいて得られた各要約要素ｖｉに帰属するコンセプトおよび各コンセプトの代表度に基づいて、一定の要約サイズの中で代表的なコンセプトを可能な限り被覆することが可能な集合Ｖの部分集合Ｖ＊を出力する。ｘｉをｖｉが要約に含まれていたら１、いなければ０をとる決定変数とおけば、Ｖ＊はｘｉが１をとるようなｖｉの集合として定義することができ、Ｖ＊は組合せ最適化を解くことによって得られることがわかる。ここで解く最適化の目的関数は、重要なコンセプトを可能な限り被覆することを実現するものであれば任意のものを用いることが可能である。例えば目的関数とその制約条件は、（３）式のように定義することができる。
【数７】
2015001834.tif 000009
【００６４】
ｊ番目のコンセプトｅｊの重要度をｗｊ、要約要素をｖｉ∈Ｖ、ｚｊをコンセプトｅｊが要約に含まれる画像のいずれかに含まれる場合は１、そうでなければ０をとる決定変数とする。ａｉｊはコンセプトｅｊが要約要素ｖｉに含まれている場合は１であり、そうでない場合はゼロをとる。
【００６５】
この問題は、要約サイズＫのもと目的関数を最大化するナップサック制約付き最大被覆問題として知られている。この問題はＮＰ困難問題であるため、特に要素集合Ｖの要素数が大きい場合実時間で最適解を得ることは難しい。しかしながらナップサック制約付き最大被覆問題の近似解を得る公知のアルゴリズムはいくつか存在する（参考文献３〜６）ため、それらを用いればよい。
参考文献３（再掲）：E. Filatova et al., A Formal Model for Information Selection in Multi-sentence Text Extraction, in Proc. COLING, pp.397-403, 2004
参考文献４（再掲）：S. Khuller et al., The Budgeted Maximum Coverage Problem, Information Processing Letters, Vol. 70, No.1, pp39-45, 1999
参考文献５（再掲）：W. Yih et al., Multi-document Summarization by Maximizing Informative Content-Words, in Proc. IJCAI, pp.1776-1782, 2007
参考文献６（再掲）：S. Khuller et al., Randomized Rounding for Maximum Coverage Problem and Mimum Set Cover with Threshold Problem, Technical Report CS-TR-4805, The University of Maryland, 2006
【００６６】
これらのアルゴリズムを用いることにより、目的関数を最大化する決定変数ｘｉを得ることができ、これにより部分集合Ｖ＊を出力することができる。
【００６７】
次に、出力部１７は、最適化処理部１６において得られた部分集合Ｖ＊を出力する（ステップＳ１７）。本実施形態ではＶ＊の各要素は映像区間であるため、それらを一定の順序で結合し、順次提示するなどすればよい。映像区間の並び順は任意の方法でランキングした結果を用いることで決定することができる。例えば代表度の高いコンセプトを多く含む映像区間から順に表示するのであれば、以下の（４）で得られるスコアｓｉに基づいてｖ＊ｉ∈Ｖ＊をランキングすればよい。
【数８】
2015001834.tif 000010
ここでδ（αｉｊ＞０）は、αｉｊが非負であったときに１、そうでなければゼロをとる値である。
【００６８】
このように、出力部１７から部分集合Ｖ＊を出力することにより、要約コンテンツ３を出力することが可能となり、コンテンツ集合を要約した要約コンテンツを得ることができる。
【００６９】
以上説明したように、画像・映像コンテンツ群から、全体を俯瞰したり、短時間で概要を把握したりすることを可能とする要約を生成するにあたり、まず各要素に帰属するコンセプトおよび各コンセプトの代表度を精度よく抽出するようにした。このときコンセプトは、画像もしくは映像の見た目、音、付与されているメタデータのうち少なくとも一つ以上に基づいて抽出する。そして得られたコンセプトの中から、代表的なものを可能な限り多く含められるように要素を選択し、得られた部分集合を要約として出力するようにした。このため、要約がコンテンツ集合全体の代表的なコンセプトを可能な限り包含しているべきであるという要件を直接的に満たす要約を出力することが可能になっている。これにより、先行技術で生じていた種々の問題を回避することが可能となり、結果より質の高い要約を生成することができる。
【００７０】
前述した実施形態におけるコンテンツ要約装置をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＰＬＤ（Programmable Logic Device）やＦＰＧＡ（Field Programmable Gate Array）等のハードウェアを用いて実現されるものであってもよい。
【００７１】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。したがって、本発明の技術思想及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行ってもよい。
【産業上の利用可能性】
【００７２】
コンテンツ集合が含む代表的なコンセプトを可能な限り包含した質の高い要約を出力することが不可欠な用途に適用できる。
【符号の説明】
【００７３】
１・・・コンテンツ要約装置、１１・・・入力部、１２・・・記憶部、１３・・・要約要素定義部、１４・・・画像コンセプト抽出部、１４１・・・コンセプト帰属度算出部、１４２・・・スパース表現部、１４３・・・コンセプト代表度算出部、１４ａ・・・画像／音コンセプト抽出部、１５・・・メタデータコンセプト抽出部、１６・・・最適化処理部、１７・・・出力部、２・・・コンテンツ集合、３・・・要約コンテンツ
【図１】
2015001834.tif 000011
【図２】
2015001834.tif 000012
【図３】
2015001834.tif 000013
【図４】
2015001834.tif 000014
【図５】
2015001834.tif 000015
【図６】
2015001834.tif 000016
【図７】
2015001834.tif 000017