(57)【要約】【課題】動画像そのものをクエリとする検索やグループ化を、従来よりも計算コストを低く抑えて高い精度で容易に行なう。【解決手段】特徴量抽出部２２は、クエリ動画像と対象動画像の特徴量をそれぞれ抽出する。動画像代表フレーム選出部２３が、クエリ動画像と対象動画像について、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れか用いて、前記特徴量の関係から時系列で代表フレームを取得する。さらに類似度算出部２４が、クエリ動画像と対象動画像との間の代表フレーム間類似度から、クエリ動画像と対象動画像との間の類似度を求めて、その結果を基にクエリ動画像に類似する動画像を検索する。【選択図】図１
2017021606.tif 000002
【特許請求の範囲】
【請求項１】
クエリ動画像に対して対象動画像の類似度を算出して、前記クエリ動画像に類似する動画像を検索する動画像検索装置による動画像検索方法であって、
クエリ動画像のフレームから、フレームごとに第１の特徴量を抽出し、
対象動画像のフレームから、フレームごとに第２の特徴量を抽出し、
前記クエリ動画像について、抽出された第１の特徴量に対して、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れか用いて時系列で第１の代表フレームを取得し、
前記対象動画像について、抽出された第２の特徴量に対して、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れかを用いて時系列で第２の代表フレームを取得し、
前記クエリ動画像における前記第１の代表フレームと、前記対象動画像における前記第２の代表フレームとの間の類似度から、前記クエリ動画像と前記対象動画像との間の類似度を求めて、前記クエリ動画像に類似する前記動画像を検索する、
ことを特徴とする動画像検索方法。
【請求項２】
前記第１の特徴量、及び前記第２の特徴量としてフレームシグネチャを用いることを特徴とする請求項１に記載の動画像検索方法。
【請求項３】
前記第１の代表フレームの取得と前記第２の代表フレームの取得を同一の方法を用いて行なうことを特徴とする請求項１又は２記載の動画像検索方法。
【請求項４】
前記類似する動画像の検索では、
前記クエリ動画像におけるｉ番目の前記第１の代表フレームが表わすフレーム数ＥＡｉと、前記対象動画像におけるｊ番目の前記第２の代表フレームが表わすフレーム数ＥＢｊと、前記クエリ動画像におけるｉ番目の前記第１の代表フレームと前記対象動画像におけるｊ番目の前記第２の代表フレームとの間の前記代表フレーム間類似度ｓ（ｉ，ｊ）と、をそれぞれ取得し、
ギャップペナルティーｇを設定し、
前記クエリ動画像における前記第１の代表フレームの数がｍであり、前記対象動画像における前記第２の代表フレームの数がｎであるときに、（ｍ＋１）×（ｎ＋１）の行列の各成分ｆ（ｉ，ｊ）について、
ｉ＝０の行の各成分ｆ（０，ｊ）を、次の数１に基づいて算出し、
【数１】
2017021606.tif 000019
ｊ＝０の列の各成分ｆ（ｉ，０）を、次の数２に基づいて算出し、
【数２】
2017021606.tif 000020
前記フレーム数ＥＡｉ，ＥＢｊに応じて算出される重みをｒ（ｉ，ｊ）としたときに、ｉ＝０の行とｊ＝０の列以外の残りの行列成分ｆ（ｉ，ｊ）を、次の数３に基づいて算出し、
【数３】
2017021606.tif 000021
前記行列の最終行最終列の数値を利用して、前記クエリ動画像と前記対象動画像との間の前記類似度を算出することを特徴とする請求項１〜３の何れか１項に記載の動画像検索方法。
【請求項５】
前記類似する動画像の検索では、
前記クエリ動画像におけるｉ番目の前記第１の代表フレームが表わすフレーム数ＥＡｉと、前記対象動画像におけるｊ番目の前記第２の代表フレームが表わすフレーム数ＥＢｊと、前記クエリ動画像におけるｉ番目の前記第１の代表フレームと前記対象動画像におけるｊ番目の前記第２の代表フレームとの間の前記代表フレーム間類似度ｓ（ｉ，ｊ）と、をそれぞれ取得し、
ギャップペナルティーｇを設定し、
前記クエリ動画像における前記第１の代表フレームの数がｍであり、前記対象動画像における前記第２の代表フレームの数がｎであるときに、（ｍ＋１）×（ｎ＋１）の行列の各成分ｆ（ｉ，ｊ）について、
ｉ＝０の行の各成分ｆ（０，ｊ）と、ｊ＝０の列の各成分ｆ（ｉ，０）を、全て０に設定し、
前記フレーム数ＥＡｉ，ＥＢｊに応じて算出される重みをｒ（ｉ，ｊ）としたときに、ｉ＝０の行とｊ＝０の列以外の残りの行列成分ｆ（ｉ，ｊ）を、次の数４に基づいて算出し、
【数４】
2017021606.tif 000022
前記行列の各成分の中の最大値を利用して、前記クエリ動画像と前記対象動画像との間の前記類似度を算出することを特徴とする請求項１〜３の何れか１項に記載の動画像検索方法。
【請求項６】
クエリ動画像に対して検索対象となる対象動画像の類似度を算出して、前記クエリ動画像に類似する動画像を検索する動画像検索装置であって、
前記クエリ動画像と前記対象動画像のフレームから、前記クエリ動画像に係るフレームごとの第１の特徴量と、前記対象動画像に係るフレームごとの第２の特徴量を抽出する特徴量抽出部と、
前記クエリ動画像と前記対象動画像について、抽出された第１の特徴量、及び第２の特徴量に対して、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れか用いて時系列で、第１の特徴量に係る第１の代表フレームと、第２の特徴量に係る第２の代表フレームを取得する代表フレーム選出部と、
前記クエリ動画像における前記第１の代表フレームと、前記対象動画像における前記第２の代表フレームとの間の類似度から、前記クエリ動画像と前記対象動画像との間の類似度を求めて、前記クエリ動画像に類似する前記動画像を検索する動画像検索部と、を備えたことを特徴とする動画像検索装置。
【請求項７】
前記特徴量抽出部は、前記第１の特徴量、及び前記第２の特徴量としてフレームシグネチャを用いることを特徴とする請求項６に記載の動画像検索装置。
【請求項８】
前記動画像検索部は、
前記クエリ動画像におけるｉ番目の前記第１の代表フレームが表わすフレーム数ＥＡｉと、前記対象動画像におけるｊ番目の前記第２の代表フレームが表わすフレーム数ＥＢｊと、前記クエリ動画像におけるｉ番目の前記第１の代表フレームと前記対象動画像におけるｊ番目の前記第２の代表フレームとの間の前記代表フレーム間類似度ｓ（ｉ，ｊ）と、をそれぞれ取得し、
ギャップペナルティーｇを設定し、
前記クエリ動画像における前記第１の代表フレームの数がｍであり、前記対象動画像における前記第２の代表フレームの数がｎであるときに、（ｍ＋１）×（ｎ＋１）の行列の各成分ｆ（ｉ，ｊ）について、
ｉ＝０の行の各成分ｆ（０，ｊ）を、次の数５に基づいて算出し、
【数５】
2017021606.tif 000023
ｊ＝０の列の各成分ｆ（ｉ，０）を、次の数６に基づいて算出し、
【数６】
2017021606.tif 000024
前記フレーム数ＥＡｉ，ＥＢｊに応じて算出される重みをｒ（ｉ，ｊ）としたときに、ｉ＝０の行とｊ＝０の列以外の残りの行列成分ｆ（ｉ，ｊ）を、次の数７に基づいて算出し、
【数７】
2017021606.tif 000025
前記行列の最終行最終列の数値を利用して、前記クエリ動画像と前記対象動画像との間の前記類似度を算出する構成としたことを特徴とする請求項６又は７に記載の動画像検索装置。
【請求項９】
前記動画像検索部は、
前記クエリ動画像におけるｉ番目の前記第１の代表フレームが表わすフレーム数ＥＡｉと、前記対象動画像におけるｊ番目の前記第２の代表フレームが表わすフレーム数ＥＢｊと、前記クエリ動画像におけるｉ番目の前記第１の代表フレームと前記対象動画像におけるｊ番目の前記第２の代表フレームとの間の前記代表フレーム間類似度ｓ（ｉ，ｊ）と、をそれぞれ取得し、
ギャップペナルティーｇを設定し、
前記クエリ動画像における前記第１の代表フレームの数がｍであり、前記対象動画像における前記第２の代表フレームの数がｎであるときに、（ｍ＋１）×（ｎ＋１）の行列の各成分ｆ（ｉ，ｊ）について、
ｉ＝０の行の各成分ｆ（０，ｊ）と、ｊ＝０の列の各成分ｆ（ｉ，０）を、全て０に設定し、
前記フレーム数ＥＡｉ，ＥＢｊに応じて算出される重みをｒ（ｉ，ｊ）としたときに、ｉ＝０の行とｊ＝０の列以外の残りの行列成分ｆ（ｉ，ｊ）を、次の数８に基づいて算出し、
【数８】
2017021606.tif 000026
前記行列の各成分の中の最大値を利用して、前記クエリ動画像と前記対象動画像との間の前記類似度を算出する構成としたことを特徴とする請求項６又は７に記載の動画像検索装置。
【請求項１０】
コンピュータに、請求項１〜５の何れか１項に記載の動画像検索処理を実行させるための動画像検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像検索方法、動画像検索装置及びそのプログラムに関する。
【背景技術】
【０００２】
インターネット上には、莫大な量の動画像データが蓄積されている。これらの動画像の検索に関してよく使われる方法として、テキストベースの検索手法が知られている。このテキストベースの検索手法は、動画像のそれぞれに適切なテキスト情報を対応させ、テキスト検索を行なうことで所望の動画像を検索するものである。しかしながら、このような手法では、以下のような問題がある。
（ａ）動画像とテキスト情報の対応付け（ラベル付け）は手作業で行なう必要があり、コストがかかる。
（ｂ）汎用性が乏しい不適切なラベルが付けられることにより、検索の精度や効率が低下する可能性がある。
【０００３】
上記問題点を解決する手法として、画像の内容（コンテンツ）そのものをクエリとして用いるコンテンツベースの検索が期待される。
【０００４】
コンテンツベースの検索方法として、画像全体の輝度の変化と複雑度、エッジ量の複雑度、輝度分布を用いた簡易構図情報など画像全体に関する情報、またはそれらの組み合わせで、クエリ画像と検索対象画像との類似度を計算する手法が提案されている（例えば特許文献１参照）。また、複数の検索対象画像をそれぞれ所定の大きさの要素画像に分割し、分割された要素画像から代表的な要素画像を選択し、この代表的な要素画像を用いて描画した検索参照画像による画像の検索を行なう手法も提案されている（例えは特許文献２参照）。
【０００５】
しかしながらこれらの提案手法は、静止画像をクエリとして用いて静止画像の検索を行なうものであり、動画像をクエリとして検索する手法については考慮されていない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００１−５６８２０号公報
【特許文献２】特開２００２−１４０３３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記したように、従来技術においてはテキストベース又は静止画像をクエリとして用いる手法について開示があるのみであり、動画像をクエリとする、動画像のコンテンツに基づいた動画像検索について開示されたものはなく、検討されていなかった。本発明は、動画像そのものをクエリとする検索を、計算コストを低く抑えつつ精度良く行なうことが可能な動画像検索方法、動画像検索装置及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、クエリ動画像に対して対象動画像の類似度を算出して、前記クエリ動画像に類似する動画像を検索する動画像検索装置による動画像検索方法であって、クエリ動画像のフレームから、フレームごとに第１の特徴量を抽出し、対象動画像のフレームから、フレームごとに第２の特徴量を抽出し、前記クエリ動画像について、抽出された第１の特徴量に対して、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れかを用いて時系列で第１の代表フレームを取得し、前記対象動画像について、抽出された第２の特徴量に対して、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れかを用いて時系列で第２の代表フレームを取得し、前記クエリ動画像における前記第１の代表フレームと、前記対象動画像における前記第２の代表フレームとの間の類似度から、前記クエリ動画像と前記対象動画像との間の類似度を求めて、前記クエリ動画像に類似する前記動画像を検索することを特徴とする。
【０００９】
また本発明は、クエリ動画像に対して検索対象となる対象動画像の類似度を算出して、前記クエリ動画像に類似する動画像を検索する動画像検索装置であって、前記クエリ動画像と前記対象動画像のフレームから、前記クエリ動画像に係るフレームごとの第１の特徴量と、前記対象動画像に係るフレームごとの第２の特徴量を抽出する特徴量抽出部と、前記クエリ動画像と前記対象動画像について、抽出された第１の特徴量、及び第２の特徴量に対して、時間区分ｋ平均法、時間分割ｋ平均法、時間拘束ペアワイズ・ニアレスト・ネイバー法、又は時間区分ペアワイズ・ニアレスト・ネイバー法の何れか用いて時系列で、第１の特徴量に係る第１の代表フレームと、第２の特徴量に係る第２の代表フレームを取得する代表フレーム選出部と、前記クエリ動画像における前記第１の代表フレームと、前記対象動画像における前記第２の代表フレームとの間の類似度から、前記クエリ動画像と前記対象動画像との間の類似度を求めて、前記クエリ動画像に類似する前記動画像を検索する動画像検索部と、を備えたことを特徴とする。
【発明の効果】
【００１０】
上述した本発明の動画像検索方法、動画像検索装置およびそのプログラムにより、動画像をクエリとする検索を、計算コストを低く抑えつつ精度良く行なうことができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態による、動画像検索装置のシステム構成を示すブロック図である。
【図２】本発明の実施の形態による動画像検索装置の動作フローの説明図である。
【図３】本発明の実施の形態で適用する時系列情報を考慮したクラスタリングと、従来技術の時系列情報を考慮していないクラスタリングとの違いを示す説明図である。
【図４】本発明の実施の形態において、時間窓を用いたaffinity propagation 法（TB-AP，Time-Bound Affinity Propagation）による代表フレーム選出アルゴリズムを示すフローチャートである。
【図５】本発明の実施の形態と従来技術において、メッセージ交換の違いを説明する説明図である。
【図６】本発明の実施の形態において、メッセージ交換のリンク行列を示す説明図である。
【図７】本発明の実施の形態において、TB-APにおける時間窓と、改良したk-means法やharmonic competition法における時間ブロックを、それぞれ時間軸上で示した説明図である。
【図８】本発明の実施の形態における時間区分ｋ平均法（TP k-means）の説明図である。
【図９Ａ】本発明の実施の形態における時間分割ｋ平均法（Time-Split k-means：TS k-means）について、全フレームを時系列にｋ等分して割り振り、各クラスターで重心を求めた状態を示す説明図である。
【図９Ｂ】本発明の実施の形態における時間分割ｋ平均法（Time-Split k-means：TS k-means）について、各フレームで現在属するクラスターの重心と、時系列的に隣接する前後のクラスターの重心との間の距離を計算した状態を示す説明図である。
【図９Ｃ】本発明の実施の形態における時間分割ｋ平均法（Time-Split k-means：TS k-means）について、再クラスタリングを行なった状態を示す説明図である。
【図９Ｄ】本発明の実施の形態における時間分割ｋ平均法（Time-Split k-means：TS k-means）について、時系列が不連続なフレームの間で、クラスターを分割した状態を示す説明図である。
【図９Ｅ】本発明の実施の形態における時間分割ｋ平均法（Time-Split k-means：TS k-means）について、クラスターを分割した後に、各クラスターで重心を算出した状態を示す説明図である。
【図１０】本発明の実施の形態におけるペアワイズ・ニアレスト・ネイバー法（PNN）におけるデータポイントの併合を示す説明図である。
【図１１】本発明の実施の形態における時間区分ペアワイズ・ニアレスト・ネイバー法（TP-PNN）の説明図である。
【図１２】本発明の実施の形態における時間拘束ペアワイズ・ニアレスト・ネイバー法（TB-PNN）の説明図である。
【図１３】本発明の実施の形態において、Ｍ距離による類似度算出アルゴリズムを示すフローチャートである。
【図１４】実験で使用した元の動画像データの生成過程を表わす説明図である。
【図１５】実験で使用した動画像データの構造を示す説明図である。
【図１６】５つのガウス型クラスターのそれぞれを、時間方向で２つに分けて１０集団としたプロットであり、時間性を反映した代表点（典型静止画）の出現と計算速度を調べるために使用した図である。
【図１７】動画像ｖＡと動画像ｖＢの各典型静止画の距離を行列として表した図である。
【図１８】実験で得られた大域アライメント用テーブルの一例を示す図である。
【図１９】実験で得られた局所アライメント用テーブルの一例を示す図である。
【図２０】大域アライメント用テーブルに対応して、計算を省略した個所を黒く塗り潰した図である。
【図２１】実験で得られた動画像検索における適合率−再現率曲線を示すグラフである。
【図２２Ａ】他の実験例として、異なる代表フレーム選出アルゴリズムを用いた実験で得られた、動画像検索における適合率−再現率曲線を示すグラフであって、クラスタリング時に冗長代表フレーム削除の事後処理を行なうことなく、そのまま類似度の算出を行なった場合の５つのクラスタリング手法における適合率−再現率曲線を表す。
【図２２Ｂ】他の実験例として、異なる代表フレーム選出アルゴリズムを用いた実験で得られた、動画像検索における適合率−再現率曲線を示すグラフであって、クラスタリング時に冗長代表フレーム削除の事後処理を行なったときの５つのクラスタリング手法における適合率−再現率曲線を表す。
【図２３Ａ】他の実験例として、特徴量としてCSDを用いた実験で得られた、動画像検索における適合率−再現率曲線を示すグラフである。
【図２３Ｂ】他の実験例として、特徴量としてFrame Signatureを用いた実験で得られた、動画像検索における適合率−再現率曲線を示すグラフである。
【図２４】本発明の実施の形態による、動画検索装置の処理装置としてコンピュータを用いた場合のハードウェア構成図の例である。
【発明を実施するための形態】
【００１２】
以下、添付図面に基づき、本発明における動画像検索方法と、動画像検索装置について説明する。
【００１３】
図１は、本実施の形態における動画像検索装置のシステム構成の一例を模式的に示すものである。同図において、１は動画像の集合を記憶保存するデータベースとして用いるハードディスクドライブなどの記憶装置、２は類似画像の検索を行なうコンピュータなどの処理装置、３は検索に用いる動画像や検索対象の動画像を表示したり、検索結果を表示するディスプレイ、４はマウスやキーボード等の入力装置である。記憶装置１は処理装置２に読み出し可能な状態に接続される。処理装置２は、必要に応じて記憶装置１に蓄積された動画像を表示装置であるディスプレイ３に表示できるようになっている。なお、記憶装置１は処理装置２に内蔵されていても、また、処理装置２に通信手段を介して接続されるサーバ等のコンピュータ上に構築されていてもよい。また、クエリ画像と検索対象画像とを別々の記憶装置に記憶させておくこともでき、どのような形態であるかは特に限定されない。なお、処理装置２は入力装置４と接続されており、ユーザーによる入力を適宜受け付けることができる。
【００１４】
処理装置２は、クエリ動画像及び対象動画像の処理を行なうため、動画像取込み部２１と、特徴量抽出部２２と、動画像代表フレーム選出部２３とを備えている。動画像取込み部２１は、記憶装置１に保存された動画像の中から、入力装置４を介してユーザーが選択したクエリ動画像、あるいは検索の対象となる対象動画像を取込むものである。特徴量抽出部２２は、動画像取込み部２１で取込んだクエリ動画像、あるいは対象動画像の特徴量を抽出する。動画像代表フレーム選出部２３は、特徴量抽出部２２で抽出した、クエリ動画像あるいは対象動画像の特徴量に基づき、クエリ動画像あるいは対象動画像内における一乃至複数の代表フレームをそれぞれ選出する。なお、上記動画像取込み部２１、特徴量抽出部２２、及び動画像代表フレーム選出部２３は、クエリ動画像用と対象動画像用とに分けて構成しても構わない。
【００１５】
処理装置２はその他に、クエリ動画像に類似する対象動画像を検索するため、類似度算出部２４と、類似動画像表示制御部２５とを備えている。類似度算出部２４は、クエリ動画像内における各代表フレームの特徴量と対象動画像内における各代表フレームの特徴量とをそれぞれ比較し、類似度を算出するものである。類似動画像表示制御部２５は、類似度算出部２４で算出した類似度の高い順に、対象動画像をディスプレイ３に一乃至複数表示することができる。
【００１６】
処理装置２としてコンピュータを用いる場合、類似動画像検索を行なうためのアプリケーションソフトウェアをインストールすることで、処理を行なうための各機能の一部または全部を実現することができ、処理装置２は、インストールされたアプリケーションソフトウェアに従った処理を実行することができる。
【００１７】
図２は、本実施の形態における処理装置２の処理概要を示したものである。図中、左経路はクエリ動画像に対する処理フローを表し、右経路は対象動画像に対する処理フローを表す。図２の処理により、最終的にクエリ動画像に対する対象動画像の類似度が算出される。
【００１８】
図２の左経路のクエリ動画像の処理フローを説明する。Ｓ１１０で、記憶装置１のデータベースからクエリ動画像を取り込む。次にＳ１２０で、クエリ動画像の特徴量を抽出する。特徴量としては、MPEG-7で提案されている画像特徴量の一つである色構造記述子（Color Structure Descriptor；CSD）や、ISO/IECで規定されているVideo Signature（Multimedia content description interface, International Standard of ISO/IEC 15938-3, Amendment 4 (2010)）を用いることができる。次にＳ１３０で、典型静止画としてクエリ動画像の代表フレームを決める。このとき、動画像の経過時間の要素を考慮した手法を用いて代表フレームは決められる。クエリ動画像のフレーム数にもよるが、通常は複数の代表フレームが選択され、選択された代表フレームに対応するそれぞれの典型静止画が持つ特徴量の集合がクエリ動画像の特徴量とされる。
【００１９】
図２の右経路の対象動画像の処理フローもクエリ動画像の処理フローと同様の手順で行なわれる。すなわち、Ｓ１４０で、記憶装置１のデータベースから対象動画像を取り込む。次にＳ１５０で、対象動画像の特徴量を抽出する。特徴量として前記したCSDやVideo Signatureを用いることができる。次にＳ１６０で、対象動画像の典型静止画となる代表フレームを決める。このとき、前記したように、動画像の経過時間の要素を考慮した手法を用いて代表フレームは決められる。対象動画像のフレーム数にもよるが、通常は複数の代表フレームが選択され、選択された代表フレームに対応するそれぞれの典型静止画が持つ特徴量の集合が対象動画像の特徴量とされる。図２の左経路の処理と右経路の処理は、どちらを先に行なっても、また、並列的に行なっても構わない。
【００２０】
なお、動画像代表フレーム選出部２３は、動画像の経過時間の要素を考慮した技術として、時間拘束アフィニティ伝播法（Time-Bound Affinity propagation：TB-AP）、時間区分ｋ平均法（Time-Partition k-means：TP-k-means）、時間分割ｋ平均法（Time-Split k-means：TS-k-means）、時間拘束ペアワイズ・ニアレスト・ネイバー法（Time-Bound pairwise nearest neighbor：TB-PNN）、あるいは時間区分ペアワイズ・ニアレスト・ネイバー法（Time-Partition pairwise nearest neighbor：TP-PNN）を用いることができる。これらについては後程詳しく説明する。
【００２１】
また、TP-k-means法の代わりに、その一般化である時間ブロックを導入したharmonic competitionを適用することも可能である。harmonic competition法については、「Matsuyama, Yasuo, “Harmonic Competition: A Self-Organizing Multiple Criteria Optimization,” IEEE Transactions on Neural Networks, Vol.7, No.3, pp.652-668, MAY 1996」などに記載されている。
【００２２】
こうして、クエリ動画像と対象動画像について、それぞれの代表フレーム（典型静止画）が選出されると、Ｓ１７０の類似度算出の処理が行なわれる。ここでの典型静止画の数は各動画像に依存するので、クエリ動画像と対象動画像との類似度は、ギャップの挿入が可能な重み付きＭ距離によって算出される。なお、Ｍ距離については後程詳しく説明する。Ｓ１８０において、Ｓ１７０で算出した類似度スコアを基に、類似度の高い対象動画像を検索してディスプレイ３に表示する。
【００２３】
上述の処理フローで、Ｓ１２０，Ｓ１５０における特徴量の抽出、Ｓ１３０，Ｓ１６０における代表フレームの選出、及びＳ１７０における類似度の算出の３つの処理について以下に説明する。
【００２４】
・フレームに対する特徴量の抽出
本実施の形態では、始めに動画像に含まれる各フレームの特徴量の抽出が実行される。ここで抽出された特徴量は、時系列を考慮したベクトル｛ｘｔ｝ｎｔ＝１として表現される。例えば、類似画像検索で用いるアプリケーションソフトフェアによる処理が色情報を持つ動画像を扱えるように、当該ベクトルを先に述べたMPEG-7のCSDによって表現し、ベクトルをすべて正規化されたCSDヒストグラムとすることができる。
【００２５】
ただし、動画像の各フレームの特徴量はCSDを用いたものに限らず、当該特徴量はベクトル量であればどのようなものでも構わない。前述したCSDヒストグラムの特徴量は以下の条件を適用して正規化している。
・正規化の条件
（ｉ）各ベクトルの成分は非負とする。
（ｉｉ）ベクトル成分全部の和は、1.0となるようにする。
これは、次の手順で得られる。
（ａ）動画像の各フレームについて、その特徴を表すベクトル量に変えておく（特徴量抽出）。
（ｂ）類似度の比較法およびそれをソフトウェアとして実現した時の汎用性を確保できるように、各ベクトルを正規化できる手法を採用する。
【００２６】
上記手順（ｂ）は、実質的に各ベクトルの最小値と総和を使うことで常に可能になる。また、CSDは手順（ａ）における特徴ベクトルの単なる一例で、画像フレーム全体だけを対象にするさらに簡単なものがヒストグラムである。
【００２７】
CSDは簡単な特徴量ではあるが、良好な結果を得ることができて好ましい。また、CSDの代わりに、計算量が多くなるものの、別な手法による特徴量を用いることも可能である。例えば、動画像の各フレームの特徴量は、SIFT（Scale-Invariant Feature Transform）や、SURF（Speeded Up Robust Features）や、FREAK（Fast Retina Keypoint）や、bag of visual wordsなどを用いることができる。また、先に述べたVideo Signatureを用いることもできる。これらCSD以外の特徴量や、CSDを含む特徴量を組み合わせることも可能である。
【００２８】
例えば、前述した｛CSD，FREAK，bag of visual words，SIFT，Video Signature…｝などを個別の正規化済み特徴量の集団として、個別の正規化済み特徴量をNormalizedFeatureVector（ｉ）と表記すると、動画像フレームの特徴量として、以下の数１に定義される合成特徴量ベクトルCompositeFeatureVectorを利用することもできる。ただし、正規化を行なう必要がない特徴量を用いる場合、NormalizedFeatureVectorは入力された特徴量をそのまま出力する。
【００２９】
【数１】
2017021606.tif 000003
【００３０】
ただし、合成特徴量ベクトルCompositeFeatureVectorは上式において正規化条件：ｗｉ≧０、ΣＮｉ＝０ｗｉ＝１を満たすものとする。上記数１の式は、合成特徴量ベクトルCompositeFeatureVectorを得る一例に過ぎず、例えば特徴量同士を掛け算したものも、合成特徴量ベクトルCompositeFeatureVectorとして利用できる。したがって、合成特徴量ベクトルCompositeFeatureVectorは、次の数２の一般式で得られる。これは、幾つかの個別の特徴量FeatureVector（ｉ）を組み合わせて最終的に正規化したものが、合成特徴量ベクトルCompositeFeatureVectorになるという表現を、数式化したものである。
【００３１】
【数２】
2017021606.tif 000004
【００３２】
・時系列を保つ代表フレームの選出
各フレームに対する特徴量を抽出した後、代表フレームの選出が行なわれる。ここでは、処理装置２が動画像内の各フレームを抽出した特徴量に基づいてクラスター化し、各クラスターを代表するフレームを選出する。各クラスターを代表するフレームを典型静止画と呼ぶが、本実施の形態では、典型静止画の選出には時系列情報が加味されている。
【００３３】
図３は、本実施の形態で用いる時系列情報を考慮した時間拘束アフィニティ伝播法（TB-AP）と通常のアフィニティ伝播法（AP）におけるクラスタリングの違いを説明する図である。図中上段にある時系列データは、特徴量として抽出した時間ｔ＝１から時間ｔ＝１０までのｎ＝１０個の時系列の特徴ベクトル｛ｘｔ｝１０ｔ＝１を表している。ここでの各ボックスは各時間ｔにおけるフレームを表し、例えば時間ｔ＝１のフレームには１の数字を、時間ｔ＝５のフレームには５の数字が付してある。また、図で同じグラデーションで描いたフレームは、互いに類似しているフレーム（例えば動画の中の１シーン等）を表し、同じクラスに属するものとする。図示の例では、｛１，２，１０｝のクラス、｛３，４，５｝のクラス、｛６，７，８，９｝のクラスと、類似フレームのセットが３種類存在する。
【００３４】
これらのフレームを特徴量別にクラスター化する際、通常のアフィニティ伝播法（AP）を用いた場合には、図中左側下段に示すように、典型静止画として例えばフレーム｛２，４，７｝が選出される。しかし、これは時系列情報が考慮されておらず、動画像を検索するラベルとして適切ではない。時系列が正しく考慮されることにより、図中右側下段に示すように、典型静止画は｛２，４，７，１０｝と選出される。動画像の経過時間を考慮する時間拘束アフィニティ伝播法（TB-AP）では、そのような時系列を考慮したクラスタリングが可能となる。つまり図３の例では、時間拘束アフィニティ伝播法を適用すると、典型静止画が正しく｛（１，２，０）（１，４，１），（１，７，２），（０，１０，０）｝と選出される。
【００３５】
なお、これらの典型静止画のフレーム数は動画像の長さやコンテンツに応じて可変する。したがって、各々の典型静止画は、時間順序におけるその左右に、責任のある（responsible）フレームを含んでいる。
【００３６】
以下、時系列を保つ典型静止画を選出するためのアルゴリズムの一つであるTB-APのアルゴリズムについて、図４のフローチャートを参照しながら説明する。
【００３７】
Ｓ２１０：Similarityの計算
ここでは、時間ｔ＝１から時間ｔ＝ｎまでの動画像フレームについて、特徴量として抽出されたｎ個の時系列の特徴ベクトル｛ｘｔ｝ｎｔ＝１が与えられる。前述のように、各々の特徴ベクトル｛ｘｔ｝ｎｔ＝１は、合計が１となる正規化されたCSDヒストグラムである。時間ｔ＝ｉの特徴ベクトルｘｉから、時間ｔ＝ｊの特徴ベクトルｘｊへの関係性を表わすSimilarity測度ｓ（ｘｉ，ｘｊ）を、ｓ（ｉ，ｊ）として定義する。そして、特徴ベクトルｘｉが特徴ベクトルｘｊよりも時間ｔ＝ｋの特徴ベクトルｘｋに類似している時かつその時に限り、ｓ（ｋ，ｉ）＞ｓ（ｋ，ｊ）を満たすような性質を持つものとする。
【００３８】
本実施の形態では、以下の数３の式で計算したSimilarity測度ｓ（ｉ，ｊ）を用いることとする。
【００３９】
【数３】
2017021606.tif 000005
【００４０】
ただし、bar（Ｄ）（以下、数３の右辺第１項のように、記号Ｄにオーバーラインが付いたものを、本文中ではbar（Ｄ）と表記する）は、例えば入力装置４によりユーザーが設定可能な定数パラメータである。
【００４１】
Similarityは、「値が大きいほど関係性も大きく、値が小さいほど関係性も小さい」というルールに則った値の設定であれば、数３の式に限らずどのようなものでも構わない。また、bar（Ｄ）の選び方はTB-APの結果に影響しないので、ここでは０としておくが、当該パラメータは動画像間を比較する上では重要な要素となり、０以外の値をとりうる。
【００４２】
Ｓ２２０：行列Ａを初期化
ここでは、初期値を零行列にした行列Ａ＝［ａｉｊ］を用意する（ａｉｊ←０）。この行列Ａは、availabilityを表す行列である。availabilityは、典型静止画候補のデータポイントｊからデータポイントｉへ送られるメッセージで、データポイントｉがデータポイントｊの典型静止画として選ぶことがどれだけ適切かを表す値である。
【００４３】
Ｓ２３０：行列Ａを用いて行列Ｒを算出（または更新）
ここでは先ず、スライドする時間窓の長さを、その中心が対角成分に位置するように、Ｗ＝２ω−１に設定した後、時間窓内での時系列を考慮して、特徴ベクトルｘｉ，ｘｊ，ｘｋを選択する。
【００４４】
次に、responsibilityを表す行列Ｒの成分ｒｉｊを、先に説明したavailability行列Ａを利用して計算更新する。responsibilityは、データポイントｉから典型静止画候補のデータポイントｊへ送られるメッセージで、データポイントｉがデータポイントｊの典型静止画としてどのくらい適切かを表す値である。このresponsibility行列Ｒの計算と、後述するavailability行列Ａの計算では、データポイントｉ，ｊを次の数４の範囲に設定して算出する。つまりTB-APでは、メッセージ交換を行なう範囲に数４に示す制限を設けている。
【００４５】
【数４】
2017021606.tif 000006
【００４６】
responsibility行列Ｒは通常対称的であり、行列Ａを用いて数５に示すように更新される。
【００４７】
【数５】
2017021606.tif 000007
【００４８】
数５において、ρｉｊは、データポイントｉとデータポイントｊとの間のresponsibilityの伝播値である。また、λ∈（０，１）は設計パラメータとしてのダンピング係数であり、これを用いて後述するＳ２５０での収束を遅らせ、安定した結果を得ることができる。行列Ｒも初期値は零行列とされるが、例えばダンピング係数λが０であれば、responsibilityの伝播値ρｉｊがそのまま行列Ｒの値として更新される。
【００４９】
Ｓ２４０：行列Ａを算出
ここでは、データポイントｉ，ｊを数４で示した範囲に制限し、次の数６を用いてavailability行列Ａの成分ａｉｊを更新する。
【００５０】
【数６】
2017021606.tif 000008
【００５１】
数６において、αｉｊは、データポイントｉとデータポイントｊとの間のavailabilityの伝播値である。
【００５２】
Ｓ２５０：行列Ａと行列Ｒの総和が収束したか否かを判定
以上のように算出した行列Ａの成分ａｉｊと行列Ｒの成分ｒｉｊとを加算し、その値ａｉｊ＋ｒｉｊが収束の基準を満たすまで、Ｓ２３０とＳ２４０の手順を繰り返す。一方、ａｉｊ＋ｒｉｊの値が収束の基準を満たすと、次のＳ２６０の手順に移行する。
【００５３】
Ｓ２６０：代表フレーム選出
ここでは、以下の数７に定義されるインデックスが、典型静止画のインデックスとして採用される。
【００５４】
【数７】
2017021606.tif 000009
【００５５】
つまり、ａｉｊ＋ｒｉｊの値が最大となるデータポイントでの静止画が、典型静止画として採用される。例えば、データポイントｉは、ａｉｊ＋ｒｉｊの値が最大となるデータポイントｊを中心とするクラスターに属する。最終的に代表フレームとして選出される典型静止画の集合は、こうしたインデックスを収集して見つけ出される。
【００５６】
上記一連のＳ２３０〜Ｓ２６０のフローの中で、時間窓を設定する上で必要なωは、行列Ａや行列Ｒを算出する際のメッセージ交換の範囲を制限するパラメータとなる。この制限下におけるメッセージ交換の様子を、図５に示す。同図において、上段の「AP」は、従来技術となるアフィニティ伝播法によるメッセージ交換の範囲を示している。また下段の「TB-AP」は、本実施の形態における時間拘束アフィニティ伝播法によるメッセージ交換の範囲を示している。ここでは、前記図３で説明したものと同じフレームが時系列に並べられているものとする。
【００５７】
通常の「AP」では、全てのデータポイントに対して、メッセージの交換が行われるが、本実施の形態では、時間窓で制限された近傍のデータポイントに対して、メッセージの交換が行なわれる。具体的には、図５に示す「AP」の例では、データポイントｉ＝５を中心として、データポイントｊ＝１からｊ＝１０の全範囲にデータ交換が行なわれる。一方、同図「TB-AP」の例では、パラメータω＝４に設定して、時間窓２ω―１＝７の範囲でメッセージ交換を行なう構成になっている。そのため、データポイントｉ＝５を中心として、データポイントｊ＝２からｊ＝８の範囲にメッセージ交換の範囲が制限される。
【００５８】
図６は、本実施の形態のTB-APを適用したメッセージ交換のリンク行列を示している。ここでもパラメータω＝４に設定しており、データポイントｉを１から１０の何れかに選択したときに、どのデータポイントｊとの間でメッセージ交換が行なわれるのかを塗り潰して示している。
【００５９】
通常のAPの特性として、メッセージ交換を行なったデータポイントのみが典型静止画の候補として最終的に選出される。これは、本実施の形態のTB-APでも同じことがいえる。本実施の形態のTB-APでは、メッセージを交換する範囲を時系列を考慮して制限しているため、結果としてメッセージ交換を行なわない時系列的に遠いデータポイント（例えば、図３に示す時間ｔ＝１０）の典型静止画も、クラスタリングにより代表フレームの一つとして選出できる。
【００６０】
また、TB-APにおける典型静止画の採用に関して、連続する類似フレームについては時間窓を越えても同じ典型静止画をとることができる。具体的には、いま第ｉフレームに対する典型静止画ｅｉを決定するとする。このとき、第ｉフレームより前にある第ｋフレームから第ｉ−１フレームまでの特徴ベクトルが、閾値などを用いて類似していると判定され、そして第ｋフレームに対する典型静止画ｅｋと第ｉフレームに対する典型静止画ｅｉも類似していると判定される場合、新たな典型静止画ｅｉを生成せずに典型静止画ｅｋをそのまま用いることができる。これによって、本発明の性能を向上させることができる。
【００６１】
以上のように、本実施の形態では上記TB-APに基づく処理を類似動画像検索処理装置２が実行することにより、時系列を考慮した典型静止画の集合を、クエリ動画像および対象動画像よりそれぞれ抽出することができる。そしてこの抽出された代表フレームの特徴量を、当該動画像の特徴量として決定する。特に、本実施の形態で採用するTB-APでは、選択したデータポイントと共にスライドする時間窓を設けているので、メッセージ交換の回数が制限され、メッセージ伝達の複雑さはＯ（ωｎ）となる。一方、通常のAPでの複雑さはＯ（ｎ２）である。つまり、APの計算コストはデータポイントの数の２乗に比例するため、データポイントの数が多くなると計算時間を要するといった問題点がある。それに対して、本実施の形態では一般的にω＜ｎであるため、TB-APはAPよりも計算コストを低く抑えることができる。
【００６２】
なお、類似度に関するデータの正規化と距離測度に関して、上記Similarity測度ｓ（ｉ，ｊ）は、アルゴリズムが収束すればどのようなものを用いてもよい。パラメータλを適切に設定すれば、数３におけるSimilarity測度ｓ（ｉ，ｊ）の形式は、アルゴリズムの収束をもたらす。
【００６３】
bar（Ｄ）の基準となる選択肢は次の通りである：
（ａ）全データ距離の平均値：これは、データのサイズが小さい場合にのみ許される。
（ｂ）各々の特徴ベクトルｘｔが各成分の総和が１になる非負成分だけを有するように正規化されている場合、bar（Ｄ）は√２，√（（ｄ−２）／（２ｄ）），または√（１−（１／ｄ））のいずれかである：
ただし、ｄはシンプレックスに存在する特徴ベクトルｘｔの次元を表わす。√２はシンプレックスのエッジであり、√（（ｄ−２）／（２ｄ））≒１／√２は内球の半径であり、√（１−（１／ｄ））≒１は外球の半径を表す。なお、≒は近似記号を意味し、ｄが十分大きい場合に当該近似が有効となる。
また、以上の基準の他にシステムの用途に応じた最適な値を実験的に求めることもできる。
【００６４】
例えば、前述のCSDではHSV（色相−彩度−明度）色空間表現を用いており、Ｈ，Ｓ，Ｖの各値の比率を、Ｈ：Ｓ：Ｖ＝１２：８：８に量子化するのが好ましいとされる。この場合、各画像は１２×８×８＝７６８色で表現され、CSDによる特徴量は768次元のヒストグラムとなるので、ｄ＝768となり、外球の半径を表す値をbar（Ｄ）として用いる。
【００６５】
次に、TB-APの代替手法として、動画像の経過時間の要素を考慮したクラスタリング手法について説明する。始めに改良したk-means法（ｋ平均法）やharmonic competition法について、図７を参照しながら説明する。図７左側には、TB-APにおける時間軸上でスライドする時間窓Ｗが示されており、図７右側には、改良したk-means法やharmonic competition法における時間軸上でスライドする時間窓Ｗが示されている。
【００６６】
TB-APは、時間軸に沿って重なり合うようにスライドする時間窓Ｗ中の一連の画像フレームを計算対象とする。これに対して、代替技術である改良したk-meansやharmonic competitionでは、重なりの無い時間窓Ｗの画像フレームを計算対象としている。つまりTB-APでは、時間窓Ｗのずらし幅が時間窓Ｗのフレーム長さよりも小さく、一乃至複数フレームずつ時間窓Ｗがスライディングするのに対し、改良したk-meansやharmonic competitionでは、時間窓Ｗのずらし幅と時間窓Ｗのフレーム長さが一致し、時間窓Ｗの単位で時間窓Ｗがスライディングしている。このような手法を時間拘束（Time-Bound）に対して時間区分（Time-Partition）と記載し、前記改良したk-meansを時間区分ｋ平均法（Time-Partition k-means：TP k-means）と適宜記載する。
【００６７】
改良したk-means（TP k-means）やharmonic competitionを用いた場合、時間軸に沿って画像フレームを時間窓Ｗに分割し、分割された時間窓Ｗの中でクラスタリングがなされる。ここで得られる代表点ベクトルは、元の画像そのものに対応するものではなく、k-meansやharmonic competitionに基づく計算により生成された類似画像（人工画像）の特徴ベクトルである。したがって、その代表点ベクトルと最も類似した特徴を持つフレームを、典型静止画として選出するという、二段階の計算手順が必要となる。この二段階の計算により得られた典型静止画は、TB-APの典型静止画と近似している。
【００６８】
以下にTP k-meansの処理フローについて、図８を参照して説明する。始めに時間軸に沿って時間窓Ｗで動画像を分割し、時間窓Ｗで区切られた複数のフレームに区分けする。区分けされた時間窓Ｗ内でフレームをｋ等分し、それぞれのクラスターにフレームを割り振る。続いて、それぞれのクラスターに属するフレームの特徴ベクトルを基にクラスターの重心を求める。重心は特徴ベクトルの算術平均により求めることができる。各フレームについて、フレームの特徴ベクトルと、時間窓内全ての重心との間の距離を計算し、その結果を基に再クラスタリングする。再クラスタリング後、再度クラスターの重心を求め、時間窓内全ての重心と各フレームとの間の距離の再計算と再クラスタリングを、処理が収束するまで行なう。各クラスターにおいて、収束後の重心に最も近いフレームを典型静止画として選出する。この処理を、時間窓を移動させつつ行なう。
【００６９】
次に、k-meansを用いた他のクラスタリング法である時間分割ｋ平均法（Time-Split k-means：TS k-means）について、図９Ａ〜図９Ｅを参照して説明する。なお、これらの各図において、１〜25の連続する数字は、時系列な動画像フレームの時間ｔに相当する。前記TP k-meansでは、あらかじめ決められたサイズの時間窓Ｗで動画像を区切り、その時間窓Ｗの中でk-meansに基づくクラスタリングを行なっている。これに対して、このTS k-meansは、動画像の全フレームに対してk-meansに基づくクラスタリングを行なう手法である。ただし、時系列を考慮したフレームの割り振りとクラスターの再分割を行なう点が、一般的なk-meansと異なる。
【００７０】
TS k-meansでは以下のような処理が行なわれる。始めに、動画像の全フレームを時系列に基づいてｋ等分し、それぞれのクラスターにフレームを割り振る。続いて、それぞれのクラスターに属するフレームの特徴ベクトルを基にクラスターの重心を求める。重心は特徴ベクトルの算術平均により求めることができる。例として図９Ａでは、全部で25個の動画像フレームを時系列に５等分し（ｋ＝５）、曲線で囲まれたそれぞれのクラスターで重心１〜重心５を算出している。次に各フレームについて、フレームの特徴ベクトルと、現在属するクラスターの重心、及び、時系列の近い前後のクラスターの重心との間の距離を計算し、その結果を基に再クラスタリングする。これは図９Ｂに示すように、例えば時間ｔ＝18のフレームについて、現在属するクラスターの重心４と、時系列的に隣接する前後のクラスターの重心３及び重心５との間の距離をそれぞれ計算する。その結果、このフレームは重心３との間の距離が最も近いので、再クラスタリングでは図９Ｃに示すように、重心４ではなく重心３のクラスターに割り振られる。
【００７１】
次に、再クラスタリングされた各クラスター内で時系列の不連続性を判断し、不連続がある場合にはクラスターを分割する。これは図９Ｄに示すように、例えば重心３と重心４のクラスターについて、これらのクラスターが時系列的に不連続なフレームの間で分割される。クラスターが分割された場合にはクラスターの数はｋより増えるが、再クラスタリングによりクラスターが消滅した場合には数が減ることもありうる。再クラスタリング及び分割後、再度クラスターの重心を求め、重心の属するクラスター及び、時系列が前後のクラスターに属する各フレームとの間の距離の再計算と再クラスタリングを、処理が収束するまで行なう。図９Ｅに示す例では、重心３と重心４のクラスターを分割した後に、７つのクラスターでそれぞれ重心１〜重心７を算出し、時間ｔ＝１〜25の各フレームについて、上述した距離の計算と再クラスタリングを収束するまで繰り返す。そして、各クラスターにおいて収束後の重心に最も近いフレームを典型静止画として選出する。
【００７２】
続いて、改良したペアワイズ・ニアレスト・ネイバー法（pairwise nearest neighbor：PNN）を用いたクラスタリング手法について説明する。PNNはまず、与えられた全てのデータポイント間の距離を計算する。次に、距離の近いデータポイント同士から順に併合する。これを併合後のデータポイントが全て一定の距離以上になるまで繰り返していく。これにより、類似度の高いデータポイント群を一つの集合としてまとめたクラスター群を求めるアルゴリズムである。通常のPNNについては「W. Equitz, “A new vector quantization clustering algorithm,” IEEE Trans ASSP, vol. 37, pp. 1568-1575, 1989」などに記載されている。通常のPNNでは、ペアの特徴量の平均値がそのペアを表すものとして用いられるが、本実施の形態で説明する改良したPNNでは、後述するようにペアの一方を残し、他方を除去する点が異なる。また、時系列を考慮した時間窓Ｗの設定のやり方に応じて、Time-Bound PNN（TB-PNN）とTime-Partition PNN（TP-PNN）とがある。
【００７３】
図１０は、改良したPNNの併合を説明する図である。図中、○や●は各々のフレームの特徴量に対応したデータポイントｘｉを表し、■は全データポイントの重心を表す。PNNでは、与えられた全データポイント間の距離を計算した後、それらのデータポイントの組み合わせの中で、最も距離の近いペアを見つける。図１０に示す例では、ａとｂのデータポイントが、最も距離の近いペアに相当する。次に、そのペアを併合する。本実施の形態に係る改良されたPNNにおける「併合」とは、全データポイントの重心に近いものをそのまま残し、遠いものを削除することをいう。図１０に示す例では、ｂのデータポイントを削除して、ａのデータポイントを残す。なお、通常のPNNでは、ａのデータポイントとｂのデータポイントの重心（中点）を計算し、それをａとｂの代表値としている。その後、残ったデータポイント間の距離が一定値（δ）以上になるまで繰り返し、残ったデータポイントに対応するフレームが典型静止画となる。それぞれの典型静止画は、その典型静止画に併合されたフレームを、それぞれのメンバーであるとして扱う。
【００７４】
図１１は、上述のTP-PNNを説明する図である。TP k-meansと同様に、改良したTP-PNNでは、あらかじめ決められたサイズの時間窓Ｗで動画像を区切り、その時間窓Ｗの中でPNNに基づくクラスタリングを行なっている。このとき通常のPNNと異なる点は、まず時間窓Ｗごとに重心（各フレームの特徴量の算術平均）を求め、２つのデータポイント(フレームの特徴量)を併合する際に、その重心に距離の近いデータポイントをそのまま残し、遠いデータポイントを削除することである。この処理を隣接するペアの距離が所定の値δより大きくなるまで繰り返し、残ったデータポイントに対応するフレームを典型静止画とする。各典型静止画には、それまでに併合によって削除されたフレーム群が属する。TP-PNNでは、この処理を各時間窓（重複しない）に対して行なう。
【００７５】
これに対し、TB-PNNでは図１２に示すように、TB-APと同様にスライドする時間窓の制限をかけ、各データポイントの時間窓の範囲のみとの距離計算を行なう。そして、時間窓により制限されたデータポイントの組み合わせのうち、距離の近いものから順にデータポイントの併合を行なう。ただし、併合を行なう際、TP-PNNと異なり、動画フレーム全体の重心に近いものをそのまま残し、遠いものを削除する。この処理を隣接するペアの距離が所定の値δ以上となるまで繰り返す。これもTP-PNNと同様に残ったデータポイントに対応するフレームを典型静止画とする。各典型静止画には、それまでに併合によって削除されたフレーム群が属する。
【００７６】
以上説明したように、動画像の経過時間の要素を考慮した時間的な制限を導入して１乃至複数の代表フレームを取得することで、通常のAPよりも検索精度を上げることができる。また、通常のk-means及びPNNの各手法に対しても同様の結果が期待できる。TB-APでは、時間窓の中の一連の画像フレームを計算対象として、そこから一段階で代表フレームを選出することが可能となり、計算手順を簡素化できる。他のTP-k-means、TS k-means、TB-PNN、TP-PNNの４手法は、TB-APに比べ計算量が少ないという利点がある。精度に関して、TB-APより若干劣る場合もあるが些少であり、いずれも高い精度を保つことが可能である。
【００７７】
上記した時系列を保つ代表フレームの選出に際して、時間窓の幅が小さすぎる場合や、動画像中でほとんど変化の無いシーンが続く場合などで、連続する類似のフレームにより必要以上に代表フレームが選出される可能性がある。このような場合には、時間順序が連続する代表フレーム同士の差を求め、その差が閾値ε以下となるような場合は、後続の代表フレームを消去し、グループをまとめることで、冗長な代表フレームを削除することができる。
【００７８】
・動画像間の解析による類似度の算出
次に、異なる典型静止画の集合を有する異なる動画像同士の比較を行なうときに用いる動画像間の解析による類似度の算出手法について説明する。コンテンツに基づいた動画像間の検索をするためには、クエリの動画像とターゲットの動画像の類似度を比較する必要がある。ここでは、以下に説明する２つの方法の何れかで行なう。本実施の形態では比較対象を動画像とするが、代表フレームのようなexemplarを持つ時系列データであれば、これに限るものではない。
【００７９】
（１）大域アライメントを求めるＭ距離を適用した類似度の比較
本実施の形態では、類似度を比較するための尺度としてＭ距離（M-distance）と呼ぶ距離を用いる。大域アライメント用のＭ距離は、文字列の類似度を測るためのレーベンシュタイン距離（L-distance）や、生命情報学において大域アライメントを求めるためのNeedleman−Wunschアルゴリズムを一般化したものである。したがって、この大域アライメント用のＭ距離は、レーベンシュタイン距離や、Needleman−Wunschアルゴリズムのそれぞれを特例として含んでいる。
【００８０】
以下、大域アライメント用のＭ距離を利用したアルゴリズムについて、図１３のフローチャートを参照しながら詳しく説明する。
【００８１】
Ｓ３１０：クエリ動画像と対象動画像の各典型静止画を用意
クエリ動画像に相当する動画像ｖＡに対して、典型静止画の集合｛ｅＡｉ｝と、当該典型静止画が所有するフレーム数の集合｛ＥＡｉ｝（ｉ＝１，２，…）が与えられる。また、動画像ｖＡと比較される対象動画像に相当する動画像ｖＢに対しても、同様の集合｛ｅＢｊ｝，｛ＥＢｊ｝（ｊ＝１，２，…）が与えられる。ここでは、数３におけるSimilarity測度ｓ（ｉ，ｊ）が、代表フレーム間類似度として選択される。
【００８２】
Ｓ３２０：テーブルを作成し、次の動的計画法の手順に従って経路を元に辿る。
動画像ｖＡの典型静止画の数をｍとし、動画像ｖＢの典型静止画の数をｎとしたときに、（ｍ＋１）×（ｎ＋１）の行列を大域アライメントのテーブルとして作成する。行列の各成分ｆ（ｉ，ｊ）は、動的計画法により次の手順で算出される。
【００８３】
先ず、Ｓ３２１では、設計パラメータとして設定したギャップペナルティーｇが選択される。このギャップペナルティーｇを導入することで、クエリ動画像の典型静止画の数ｍと、対象動画像の典型静止画の数ｎが異なっていても、これらの時系列を考慮した典型静止画同士の類似性を、正しく判定できるようになる。
【００８４】
次のＳ３２２では、｛ｉ＝０｝の行と、｛ｊ＝０｝の列について、ギャップｇにフレームの総数を掛け合わせて、段階的に値が下降するように、テーブルを構成する行列の各成分を計算する。具体的には、｛ｉ＝０｝の行は、次の数８に基づいて行列成分ｆ（０，ｊ）を算出する。
【００８５】
【数８】
2017021606.tif 000010
【００８６】
また、｛ｊ＝０｝の列は、次の数９に基づいて行列成分ｆ（ｉ，０）を算出する。
【００８７】
【数９】
2017021606.tif 000011
【００８８】
さらにＳ３２３では、（ｉ，ｊ）＝（１，１）の位置から開始し、｛ｉ＝０｝の行と｛ｊ＝０｝の列以外の残りの行列成分ｆ（ｉ，ｊ）を、次の数１０に基づいて算出する。
【００８９】
【数１０】
2017021606.tif 000012
【００９０】
その後、最大値を与える成分に向かって矢印を描く。この計算は、全ての行列成分が算出されるまで続けられる。ここでｒ（ｉ，ｊ）は、典型静止画の所有度を反映する重みを表し、その値は例えば、次の数１１に基づいて算出される。
【００９１】
【数１１】
2017021606.tif 000013
【００９２】
数１０に示すように、ここでの行列成分ｆ（ｉ，ｊ）は、行または列の数が大きくなる順に向けて逐次的に生成される。そして、ｉ行ｊ列の行列成分ｆ（ｉ，ｊ）は、（ｉ−１）行ｊ列を経由しｉ行ｊ列に至る経路、ｉ行（ｊ−１）列を経由しｉ行ｊ列に至る経路、（ｉ−１）行（ｊ−１）列を経由しｉ行ｊ列に至る経路のうち、コストの最も大きい経路が最適経路として選択され、そのときの数値が当該行列の成分として逐次的に決められていく。
【００９３】
Ｓ３３０：大域アライメントの決定
テーブルを構成する全ての行列成分の算出が終了した後、行列ｆ（ｉ，ｊ）の最終行最終列の成分から矢印を元に辿ることで、大域アライメントの経路を得ることができる。
【００９４】
Ｓ３４０：類似度の算出
動画像ｖＡと動画像ｖＢの類似度ｕ（Ａ，Ｂ）を、次の数１２に基づいて算出する。
【００９５】
【数１２】
2017021606.tif 000014
【００９６】
ただしｈ（ｘ）は正の増加関数とし、ｆｌａｓｔは当該行列の最終行最終列の数値である。また、ｗは平均化関数とする。当該平均化関数は例えば、ΣｉＥｉＡとΣｉＥｉＢとの算術平均とすることができる。
【００９７】
（２）局所アライメントを求めるＭ距離を適用した類似度の比較
比較すべき動画像が互いに大きく相違している場合、上述した大域アライメントは人間の感覚からずれたものとなる。このような場合には、局所アライメントが利用できる。局所アライメントは、配列が全体としては似ておらず、部分的類似を見つけたい場合に有効である。以下に記述するアルゴリズムは、上記の大域的アライメントによる方法を、局所アライメントに適応させたもので、類似度の尺度として局所アライメント用のＭ距離を用いる。この局所アライメント用のＭ距離は、生命情報学における局所アライメントを求めるためのSmith-Watermanアルゴリズムの一般化となっている。したがって、本実施の形態で適用する局所アライメント用のＭ距離は、Smith-Watermanアルゴリズムを特例として含んでいる。
【００９８】
以下、局所アライメント用のＭ距離を利用したアルゴリズムについて、図８のフローチャートを参照しながら詳しく説明する。ただし、既に説明した大域アライメント用のＭ距離と重複する手順が多いため、違いを記述するに留める。
【００９９】
Ｓ３１０：クエリ動画像と対象動画像の各典型静止画を用意
これは、大域アライメント用のＭ距離と同じ処理手順である。
【０１００】
Ｓ３２０：テーブルを作成し、次の動的計画法の手順に従って経路を元に辿る。
動画像ｖＡの典型静止画の数をｍとし、動画像ｖＢの典型静止画の数をｎとしたときに、（ｍ＋１）×（ｎ＋１）の行列を局所アライメントのテーブルとして作成する。行列の各成分は、動的計画法により次の手順で算出される。
【０１０１】
先ず、Ｓ３２１では、設計パラメータとして設定したギャップペナルティーｇが選択される。これは、大域アライメント用のＭ距離と同じ処理手順である。
【０１０２】
次のＳ３２２では、｛ｉ＝０｝の行と、｛ｊ＝０｝の列について、各成分をすべて０に設定する。
【０１０３】
さらにＳ３２３では、（ｉ，ｊ）＝（１，１）の位置から開始し、｛ｉ＝０｝の行と｛ｊ＝０｝の列以外の残りの行列成分ｆ（ｉ，ｊ）を、次の数１３に基づいて算出する。
【０１０４】
【数１３】
2017021606.tif 000015
【０１０５】
その後、０ではない最大値を与える成分に向かって矢印を描く。数１３の右辺では数１０と異なり、ｍａｘ記号の中の最左成分を０としている。これにより、スコア値が負になった場合に値を０にリセットし、アライメントを新しく始めることができる。
【０１０６】
Ｓ３３０：局所アライメントの決定
テーブルを構成する全ての行列成分の算出が終了した後、行列ｆ（ｉ，ｊ）の中の最大値ｆｍａｘの成分から矢印を元に辿ることで、局所アライメントの経路を得ることができる。
【０１０７】
Ｓ３４０：類似度の算出
大域アライメント用のＭ距離と同じ処理手順を用い、動画像ｖＡと動画像ｖＢの類似度ｕ（Ａ，Ｂ）を、数１２に基づいて算出する。
【０１０８】
以上述べたように、フレームに対する特徴量の抽出、時系列を保つ代表フレームの選出、及び、動画像間の解析による類似度の算出の手順を、類似動画像検索処理装置２が処理実行して、動画像ｖＡに対する個々の動画像ｖＢの類似度ｕ（Ａ，Ｂ）を算出する。これにより、クエリ動画像に類似する類似動画像を対象動画像の中から検索することができる。
【０１０９】
次に、上記動画像検索装置を用いた実験の詳細と結果を述べる。
【０１１０】
先ず、実験データについて、検索のエンドユーザーは人間であるので、類似度の最終判断は人間のもつ感性に強く依存する。したがって、類似度の判断は、題目にできるだけ依存しないことが望ましい。しかし、単なるセットでは、プレーンな機器でも判断するのが容易になり過ぎるので、実験では次の条件を満足するデータセットを用意した。
【０１１１】
・元の動画像データは、ラベル付けされていないものとする。
・検索における適合率および再現率を、自動的に判断できるものとする。
・図３の右下に示すような時間に依存する性質を判別できるように、各動画像は、シーンの時間変化を捉えた情報を有するものとする。
【０１１２】
図１４は、元の動画像データの生成過程を表したものである。グループＡの動画像は「鳥瞰図」を表し、グループＢの動画像は「鳥」を表す。実験において、これらのグループＡ，Ｂより20の動画クラスが作られる（図１５を参照）。各クラス１〜２０はそれぞれ21個の動画像を構成するので、互いに異なる合計で420個のテスト動画を使用した。
【０１１３】
・事前実験
APアルゴリズムの収束はデータに依存するので、数５と数６におけるパラメータλの範囲を確認する必要がある。試行データの集合として、５集団のガウス型クラスターを生成し、さらに、それぞれの時間方向について２集団に分け、１０集団とした。図１６は、これらのデータを図示したものである。
【０１１４】
図１６に示す試行データの集合に関して、本実施の形態で提案するTB-APと、通常のAPに対して実験を行なった。主な目的は収束のためのパラメータλの範囲と、時間窓パラメータωの効果とを確認することにある。繰り返しの実験により、パラメータλ∈［0.3，1.0−ε］の選択はデータの特徴に依存する。ただしεは正の微少量であり、図１６の実験ではε＝0.02とした。
【０１１５】
表１は、収束の傾向と計算時間を示したものである。収束は、初期値で正規化されたａ（ｉ，ｋ）およびｒ（ｉ，ｋ）の総和により、それが10−５未満であるか否かによりチェックされた。表１では、時間窓Ｗのパラメータωを変化させたときの典型静止画の数「exemplars」、反復回数「iterations」、メッセージ伝達数「message passing」をそれぞれ示している。表１より、例えばω＝10のとき、本実施の形態のTB-APは通常のAPのメッセージ伝達と比べて６倍高速であることがわかる。
【０１１６】
【表１】
2017021606.tif 000016
【０１１７】
ω＝１の場合は、全フレームが典型静止画であることを意味する。ω＝ｎ＝100は、時間依存性のある典型静止画抽出を含まない通常のAPの場合に相当する。これは収束傾向を見るため比較例として求めた。ω＝５，１０，２０，５０とした場合を見ると、メッセージ伝達数に単調増加が認められ、これは時間窓のサイズに起因するためＣＰＵタイムに直接関わる。しかし、通常のAPのメッセージ伝達数に対して、TB-APのメッセージ伝達数の比率は小さいまま保たれているので、これらは望ましい範囲にあるといえる。
【０１１８】
準備した図１５の動画像セット（クラス１〜２０）に対して、信頼できるフレームを伴う典型静止画を見つけ出すのにTB-APを適用した。これは、各動画像に「数値的な注釈」を付与するのに重要な手順であり、図１５に示す整理されていない動画像の集合を、数値的なタグという観点から構造化することと等価である。こうしたタグは、オンラインとオフラインの何れかで算出できる。
【０１１９】
こうして、TB-APにより得られた、比較対象とする二つのクラスの動画像（動画像ｖＡと動画像ｖＢ）の各典型静止画について、それらのSimilarity測度ｓ（ｉ，ｊ）から得られる距離行列の一例を図１７に示す。同図において、動画像ｖＡは４つの典型静止画を有し、動画像ｖＢは３つの典型静止画を有するので、当該行列は３×４行列である。表中の数字は、動画像ｖＡと動画像ｖＢとの典型静止画（代表フレーム）間の距離行列の各成分を表し、例えば動画像ｖＡの代表フレーム２と、動画像ｖＢの代表フレーム３との距離は0.26となる。当該距離は各代表フレーム間の類似度に対応して数値化したもので、ここでは距離が小さいほど代表フレーム同士が類似したものとなり、反対に距離が大きいほど代表フレーム同士が互いに相違したものとなる。
【０１２０】
図１８は、上述した大域アライメント用のＭ距離を適用して作成したテーブルの一例である。この大域アライメント用のテーブルを作成する上で、アルゴリズムのパラメータは、bar（Ｄ）＝１／√（１−（１／ｄ）），ｄ＝３×256＝768，ｇ＝0.05にそれぞれ設定した。同図において、テーブルの右下に記載される数字26.60が最終成分の数値ｆｌａｓｔであり、そこから元に辿る最適経路を大域アライメントとして網掛けで示している。その後、動画像ｖＡと動画像ｖＢの類似度ｕ（Ａ，Ｂ）を求めるために、算出された数値ｆｌａｓｔは平均化関数で正規化される。例えば、ギャップペナルティーｇとフレーム数の集合との積の総和で正規化する場合、図１８において、その総和は、0.05×（８＋12＋10＋７）＋0.05×（12＋７＋10）＝1.85＋1.45＝3.30であるので、正規化された類似度ｕ（Ａ，Ｂ）は26.60／（1.85＋1.45）＝8.06と算出される。また適合パターンは、当該行列の最終行最終列より矢印を辿って探すことができる。こうして、動画像ｖＡと動画像ｖＢとの間で、大域アライメント用の重み付きＭ距離による適切な類似度ｕ（Ａ，Ｂ）の算出が可能となる。
【０１２１】
図１９は、上述した局所アライメント用のＭ距離を適用して作成したテーブルの一例である。アルゴリズムのパラメータは、bar（Ｄ）＝√（１−（１／ｄ）），ｄ＝３×256＝768，ｇ＝0.05と設定した。局所アライメント用のテーブルでは、大域アライメント用のテーブルでスコアがマイナスになる成分、すなわち数８や数９で算出した成分が、すべて０にリセットされることが確認できる。ここでは最大値ｆｍａｘが26.95であり、その最大値ｆｍａｘの成分から元に辿る最適経路を、局所アライメントとして網掛けで示している。こうして、比較する動画像が大きく異なるものであっても、動画像ｖＡと動画像ｖＢとの間で、局所アライメント用の重み付きＭ距離による適切な類似度ｕ（Ａ，Ｂ）の算出が可能となる。
【０１２２】
なお、大域アライメントにおける好ましい変形例として、上述したＭ距離による類似度の算出は、その計算量を削減するために、図２０に示すように、シーケンス全体の割合に対して任意の幅ｒだけを計算に用いることもできる。これは、Ｍ距離をコンテンツベースの動画像検索の類似度算出に特化させることで高速化した算出手法である。図２０において、黒く塗りつぶされた部分は、計算を省略した個所を示す。またこの図は、大域アライメントによる図１８のテーブルに対応する。この場合、計算の範囲は以下の数１４によって定められる。
【０１２３】
【数１４】
2017021606.tif 000017
【０１２４】
上記数１４において、ｍは動画像ｖＡの代表フレーム数であり、ｎは動画像ｖＢの代表フレーム数である。幅ｒは、類似度比較における計算範囲の絞り具合を表すパラメータであって、計算範囲を数１４のように絞ることで、通常の全ての行列成分を算出する計算と比べて、100×（１−ｒ）２％の計算量削減が可能となる。図２０の例では、計算範囲を絞ったにもかかわらず、計算範囲を絞っていない図１８の計算結果と同じ結果を算出していることが確認できる。
【０１２５】
次に、前述した時間窓のパラメータωと、類似度ｕ（Ａ，Ｂ）を算出した後の再現率や適合率との関係について説明する。ここでは、全ての動画像が類似度の高い順に分類された後、再現率と適合率が次の数１５のように定義される。
【０１２６】
【数１５】
2017021606.tif 000018
【０１２７】
再現率（recall）：＝  検索によって見つかった正解動画像の数／同じクラスに属する動画像数
適合率（precision）：＝  検索によって見つかった正解動画像の数／検索された上位動画像数
【０１２８】
再現率とは、検索要求を満たす全動画像に対しての、検索要求を満たす検索結果の割合を意味し、検索の網羅性を表す指標である。一方、適合率とは、全検索結果に対しての、検索要求を満たす検索結果の割合を表し、検索の正確さを表す指標である。一般に再現率や適合率が高いほど検索の性能が高いとみなされる。
【０１２９】
図２１は、実験で得られた適合率−再現率曲線の結果を示している。同図において、縦軸は適合率を表し、横軸は再現率を表す。曲線がグラフ中右上に行くほど、検索性能が高い。ここでは、TB-APを適用した時間窓パラメータが「ω＝５」と「ω＝10」の各実験を載せている。図中枠内に記載されるように、数１２で示した関数ｈ（ｘ）を定義し、そこで使用する係数ａをａ＝１に設定した。また比較として、通常のAPを適用した「Plain AP」の実験結果も併せて掲載した。
【０１３０】
これらの実験結果から、再現率として20％までを要求する関心領域（図中「ROI」で囲んだ領域）において、本実施の形態のTB-APによる適合率は非常に高く、処理能力は満足のいくものであることが読み取れる。一方、通常のAPは時間軸を考慮していないため、本発明のTB-APと比べてその性能は劣ることが見てとれる。
【０１３１】
次に、代表フレームを選出する際に用いたクラスタリング手法の違いによる検索結果の違いについて示す。図２２Ａおよび図２２Ｂは、前述した５つのクラスタリング手法における適合率−再現率曲線の実験結果を示している。
【０１３２】
実験データとして、互いに異なる2100個の動画像を用意した。次にこれらを21個ずつに分け、合計100個の動画セットにする。各セットにおいて、21個の動画像のうちの一つをクエリとし、このクエリの10％以上のフレームを残りの20個の動画像の中にそれぞれ一様乱数によって得られた位置に挿入した。これによりクエリを除く2000個のテスト動画を被検索対象群とした。
【０１３３】
上記の実験データに対して、フレームに対する特徴量の抽出、時系列を保つ代表フレームの選出、及び動画像間の解析による類似度の算出を行ない、クエリに関連する動画像の検索を行なった。特徴量はCSDを用い、類似度は局所アライメントを基に求めた。
【０１３４】
図２２Ａは、クラスタリング時に冗長代表フレームの削除の事後処理を行なうことなく、そのまま類似度の算出を行なった場合の５つのクラスタリング手法における適合率−再現率曲線を表す。５つの手法とも概ね良好な結果が得られており、差はほとんど見られない。
【０１３５】
図２２Ｂは、クラスタリング時に冗長代表フレームの削除の事後処理を行なったときの５つのクラスタリング手法における適合率−再現率曲線を表す。このとき閾値ε＝0.05としている。代表フレームの数が概ね半分に減ることで、事後処理の無いものに比べれば適合率が下がっているが差は小さい。
【０１３６】
上記５つのクラスタリング手法では、TB-APに比べて他のTP k-means、TS k-means、TP-PNN、及びTB-PNNは計算量が少ないため、処理速度を大幅に早くできる。また、局所最適化を避けるためには、初期値の設定で工夫する必要があるが、TB-AP、TP-PNN、及びTB-PNNについては、そのアルゴリズムから不適切な局所最適化は生じない。
【０１３７】
次に、別の実験例として、前記実験例において用いたCSDのかわりに、Video Signatureに係る特徴量を本発明に適用した実験例を以下に示す。Video SignatureはISO/IEC標準の中で仕様が公開されているものであり（Multimedia content description interface, International Standard of ISO/IEC 15938-3, Amendment 4 (2010)）、コンテンツの同一性を判断するための一意に識別可能な特徴量を規定している。コンテンツの複製（コピー）を高精度に検知することができるため，インターネット上の不正コピーや不正流通の検知に用いることができるものと期待されている。
【０１３８】
Video Signatureの規格では、特徴量のデータは、フレーム単位の特徴を記述するFrame Signature、Frame Confidence及びWord、並びに連続する複数フレームから構成される区間単位の特徴を記述するBagOfWordsから構成されている。本実験例では、この中のFrame Signature（フレームシグネチャ）に着目して計算を行なっている。なお、これはFrame Signatureに限定するという意味ではなく、Video Signatureの規格にある他の特徴量を用いたり、また、先に述べたように複数の特徴量を合成特徴量ベクトルとして利用することもできる。
【０１３９】
Frame Signature は、特徴量として、映像の各フレームを部分領域に分割し、部分領域間の輝度の差分を三値化し、380次元のベクトルとして表わすものである。このとき、フレーム内の中央領域の方を周辺領域よりも密に部分領域としてサンプリングするようにしている。本実験例では、各フレームを32×32の部分領域に分割し、ＹＣｂＣｒの色彩空間の中のＹの輝度の平均値を各部分領域の輝度情報として用いた。
【０１４０】
先のクラスタリングの実験と同様に、実験データとして、まず互いに異なる2100個の動画像を用意した。次にこれらを21個ずつに分け、合計100個の動画セットにする。各セットにおいて、21個の動画像のうちの一つをクエリとし、このクエリの10％以上のフレームを残りの20個の動画像の中にそれぞれ一様乱数によって得られた位置に挿入した。これによりクエリを除く2000個のテスト動画を被検索対象群とした。また、単純にクエリの一部を挿入するのではなく、挿入する動画像に以下のような５つの処理を施して検索しにくくしている。
１）フレームレートを増加（フレームの削除）（frame）
挿入する動画像の２または３または６フレーム毎(一様乱数により決定)に１フレームを削除することにより、フレームレートの増加を施している。
２）グレースケール化（gray）
挿入する動画像の各フレーム画像に対して、
Ｙ＝0.11448×Ｒ＋0.58661×Ｇ＋0.29891×Ｂ
の式によりグレースケール変換を施している。ここで、Ｒ、Ｇ、Ｂ（赤、緑、青）は各フレーム画像を表現する色彩空間を表し、値はそれぞれ０〜255の整数値を取る。
３）輝度を低下（br）
挿入する動画像の各フレーム画像のＲ、Ｇ、Ｂの値に輝度の低下率を表す変数Ｐを乗ずる。Ｐの値は0.6〜0.9の中で一様乱数を取る。
４）サイズ変化（縮小及び拡大）（resize）
挿入する動画像の各フレーム画像サイズを、0.5〜2.0倍の範囲から一様乱数を取り変更を施している。
５）JPEG（Joint Photographic Experts Group）変換（jpeg）
JPEG変換は、画像の周波数成分のうち一部の情報を削減することで圧縮を施している。
実験ではこの圧縮率を高めることで、挿入する動画像の品質を低下させた。本実験中では画像処理ライブラリのOpenCVを使用しており、この中でJPEGの品質を決定する変数CV_IMWRITE_JPEG_QUALITYに対して、20〜80の中から一様乱数を取って設定することで、圧縮を行なった。この変数CV_IMWRITE_JPEG_QUALITYは0〜100の値を取り、100のとき画像の品質が最高となる。
【０１４１】
上記の実験データに対して、フレームに対する特徴量の抽出、時系列を保つ代表フレームの選出、及び、動画像間の解析による類似度の算出を行ない、クエリに関連する動画像の検索を行なった。また、比較例として、特徴量としてCSDを用いた実験も行なった。
【０１４２】
図２３Ａおよび図２３Ｂは、実験で得られた適合率−再現率曲線の結果を示している。図２３ＡはCSDを用いた場合、図２３ＢはFrame Signatureを用いた場合である。典型静止画の取得方法はTP-PNNを用い、各パラメータの値はギャップペナルティーｇ＝0.2、CSDを用いた場合δ＝0.1、bar（Ｄ）＝0.05、距離計算はユークリッド距離、Frame Signatureを用いた場合δ=320、bar（Ｄ）＝15、距離計算は絶対値距離を用いた。このときδはTP-PNNで併合する条件の閾値である。各パラメータについては、適正な比較のため、圧縮率（代表フレームの取得数）が同等となるようにδを設定し、また、それぞれの方法で結果が最良となるようにbar（Ｄ）の値を選択している。
【０１４３】
図２３Ａに示すように、輝度が落ちている場合は、CSDによる検索は難しくなる。グレースケール化された場合にはほとんど検索できない。また、JPEG変換によっても精度が低下した。ただし、フレームレートの変換とサイズ変換に関しては高い精度を保っていた。一方、図２３Ｂに示すように、Video Frame Signatureを用いた場合、CSDに比べ実験を行なったすべての変換に対して精度低下の差異が少なくなることが確認できた。
【０１４４】
以上述べたように、Frame Signatureを採用することで、CSDを用いた場合と比較して、輝度変化などの変更に強いという利点がある。また、特徴ベクトルのデータ量がCSDと比べて小さいため、比較時の距離計算を高速に行なうことが可能となる利点がある。
【０１４５】
以上、本実施の形態における動画像検索装置のシステム構成とアルゴリズムを提示したが、動画像は大きな容量サイズであり、各典型静止画とそれらの責任のあるフレームの集合は、通常オフラインで算出される。そのため、大きなデータ集合の構造情報に対する数値ラベルとして、こうした集合を利用できる。また本実施の形態では、各々の典型静止画が責任のあるフレームを含んでいることを考慮して、レーベンシュタイン距離を含む新規な類似度の算出方法を、Ｍ距離として提案している。このＭ距離は、選出した典型静止画に対して、大域アライメントと局所アライメントの両方で利用が可能である。
【０１４６】
また、上述した５つのクラスタリング手法による検索結果の違いを調べた実験例では、クエリ動画像と対象動画像に対して同じクラスタリング手法を用いて代表フレームを選出している。このようにすることで、同一の規範で代表フレームを選出することができ、類似度比較の際に、異なる規範を用いて代表フレームを選出することによる不整合の発生を防ぐことができる。ただし、必ずしも同じクラスタリング手法をとる必要があるとは限らず、検索する動画像のデータサイズやクラスタリングの処理速度、検索精度等を考慮して、クエリ動画像と対象動画像とで異なるクラスタリング手法を用いて代表フレームを選出しても構わない。
【０１４７】
なお、上述した処理装置２による動画像検索処理は、ＦＰＧＡ（field-programmable gate array）等を用いた電子回路により実行することができるが、その機能の全部又は一部をコンピュータにより実行することができる。図２４は、処理装置２としてコンピュータ１００を用いる場合のハードウェア構成の一例である。コンピュータ１００には、各種制御を行なうＣＰＵ（Central Processing Unit）１０２、主記憶装置１０３、補助記憶装置１０４、通信インターフェース１０５、及びドライブ装置１０６などがバス１０１を介して相互に接続されている。
【０１４８】
ＣＰＵ１０２は、補助記憶装置１０４に格納されているプログラムを読み出し、その指示に従って本発明に係る動画検索処理を実行することができる。主記憶装置１０３はランダムアクセスメモリ等からなる記憶装置であり、補助記憶装置１０４に格納されているプログラムやデータ等の一部を一時的に記憶し、また、ＣＰＵ１０２による処理結果を一時的に記憶するものである。補助記憶装置１０４は、例えばハードディスクドライブやＳＳＤ（Solid State Drive）等からなる記憶装置であり、本発明に係る動画検索処理を実行するためのプログラムや処理に用いるデータを記憶する。通信インターフェース１０５は、ネットワークを介して外部のサーバや外部の記憶装置と通信を行なうためのものである。コンピュータ１００は通信インターフェース１０５を介して、外部のサーバからプログラムをダウンロードしたり、外部の記憶装置に対してデータの読み出しや書き込みを行なったりすることができる。ドライブ装置１０６は、記録媒体１０７に対してデータの読み出しや書き込みを行うために用いるものである。記録媒体１０７はプログラムやデータを記録するものであり、ＣＤ（Compact Disk ）やＤＶＤ（Digital Versatile Disk）等を用いたＲＯＭ（Read only Memory）等がある。また、記録媒体１０７としては、その他ＵＳＢ（Universal Serial Bus）メモリ等の電子デバイスメモリを用いることも可能である。なお、これらのハードウェアは一例として示したものであり、必要に応じて取捨選択可能であり、また、他の要素を加えても構わない。
【０１４９】
以上を纏めると、本実施の形態では、クエリ動画像に対して検索対象となる対象動画像の類似度を算出して、クエリ動画像に類似する動画像を検索する動画像検索装置のシステムを用いた動画像検索方法を提案する。
【０１５０】
特にこの方法では、処理装置２に組み込んだ特徴量抽出部２２が、クエリ動画像のフレームから、フレームごとに第１の特徴量を抽出し、対象動画像のフレームから、フレームごとに第２の特徴量を抽出する。次に、処理装置２に組み込んだ動画像代表フレーム選出部２３が、クエリ動画像について、特徴量抽出部２２で抽出された第１の特徴量に対して、TP k-means、TS k-means、TB-PNN、又はTP-PNNの何れか用いて、時系列で第１の代表フレームを取得し、対象動画像について、特徴量抽出部２２で抽出された第２の特徴量に対して、TP k-means、TS k-means、TB-PNN、又はTP-PNNの何れかを用いて、時系列で第２の代表フレームを取得する。そして、処理装置２に組み込まれた動画像検索部としての類似度算出部２４や類似動画像表示制御部２５が、クエリ動画像における第１の代表フレームと、対象動画像における第２の代表フレームとの間の代表フレーム間類似度から、クエリ動画像と対象動画像との間の類似度を求めて、クエリ動画像に類似する動画像を検索する。
【０１５１】
このような方法を採用すると、クエリ動画像と対象動画像に対して、動画像の経過時間の要素を考慮した時間的な制限を導入して、１乃至複数の第１の代表フレームと第２の代表フレームをそれぞれ取得することが可能になる。そして、この時系列の第１の代表フレームと第２の代表フレームを利用して、クエリ動画像と対象動画像との間で類似性を判定することで、対象動画像の中からクエリ動画像に類似する動画像を、通常のAPよりも精度を上げて検索できる。また、k-means、及びPNNの各手法においても同様の結果が期待できる。また、TP k-means、TS k-means、TB-PNN、TP-PNNの各手法は、TB-APに比べ計算量が少なく、結果的に動画像そのものをクエリとする検索やグループ化を、計算コストを低く抑えて高い精度で容易に行なうことが可能になる。
【０１５２】
上記の方法では、特徴量抽出部２２が第１の特徴量及び第２の特徴量として、Video Signatureに係る特徴量として規定されるFrame Signatureを用いるのが好ましい。これにより、CSDを用いた場合と比較して、輝度変化などの変更があっても高い検索精度を維持できる。また、データ量がCSDと比べて小さいため、比較時の距離計算を高速に行なうことができる。
【０１５３】
上記クエリ動画像に類似する動画像の検索では、クエリ画像におけるｉ番目の第１の代表フレームが表わすフレーム数ＥＡｉと、対象動画像におけるｊ番目の第２の代表フレームが表わすフレーム数ＥＢｊを取得し、クエリ画像におけるｉ番目の第１の代表フレームと対象動画像におけるｊ番目の第２の代表フレームとの間のSimilarity測度ｓ（ｉ，ｊ）を、前記代表フレーム間類似度として取得する。
【０１５４】
そして、ギャップペナルティーｇを設定した上で、クエリ動画像における第１の代表フレームの数がｍであり、対象動画像における第２の代表フレームの数がｎであるときに、（ｍ＋１）×（ｎ＋１）の行列の各成分ｆ（ｉ，ｊ）について、ｉ＝０の行の各成分ｆ（０，ｊ）を数８に基づいて算出し、ｊ＝０の列の各成分ｆ（ｉ，０）を、数９に基づいて算出する。さらに、フレーム数ＥＡｉ，ＥＢｊに応じて算出される重みをｒ（ｉ，ｊ）としたときに、ｉ＝０の行とｊ＝０の列以外の残りの行列成分ｆ（ｉ，ｊ）を、数１０に基づいて算出する。こうして、行列の最終行最終列の数値ｆｌａｓｔを算出したら、その数値ｆｌａｓｔを利用してクエリ動画像と対象動画像との間の類似度ｕ（Ａ，Ｂ）を、例えば数１１で算出し、クエリ動画像に類似する動画像を検索する。
【０１５５】
このような方法を採用すれば、クエリ動画像と対象動画像との間で第１の代表フレームと第２の代表フレームの数が異なっていても、ギャップペナルティーｇを導入することで、双方の代表フレーム同士の類似性とその時系列の類似性を、正しく判定して検索を行なうことができる。また、こうして得られた行列ｆ（ｉ，ｊ）の各成分から、大域アライメントの経路を得ることができる。しかも、ここで得られる動画像データに適合した類似度の算出は、レーベンシュタイン距離や、Needleman−Wunschアルゴリズムのそれぞれを単なる特例として含んでおり、生命情報配列の類似度を測る手法にも適用できる。
【０１５６】
また別な手法として、上記クエリ動画像に類似する動画像の検索では、フレーム数ＥＡｉ，ＥＢｊと、Similarity測度ｓ（ｉ，ｊ）をそれぞれ取得し、ギャップペナルティーｇを設定した上で、（ｍ＋１）×（ｎ＋１）の行列の各成分ｆ（ｉ，ｊ）について、ｉ＝０の行の各成分ｆ（０，ｊ）と、ｊ＝０の列の各成分ｆ（ｉ，０）を、全て０に設定する。そして、フレーム数ＥＡｉ，ＥＢｊに応じて算出される重みをｒ（ｉ，ｊ）としたときに、ｉ＝０の行とｊ＝０の列以外の残りの行列成分ｆ（ｉ，ｊ）を、数１３に基づいて算出する。こうして、行列の各要素の中で最大値ｆｍａｘを算出したら、その数値ｆｍａｘを利用してクエリ動画像と対象動画像との間の類似度ｕ（Ａ，Ｂ）を、例えば数１２でｆｌａｓｔをｆｍａｘに代えて算出し、クエリ動画像に類似する動画像を検索してもよい。
【０１５７】
この場合も、クエリ動画像と対象動画像との間で第１の代表フレームと第２の代表フレームの数が異なっていても、ギャップペナルティーｇを導入することで、双方の代表フレーム同士の類似性とその時系列の類似性を、正しく判定して検索を行なうことができる。また、こうして得られた行列ｆ（ｉ，ｊ）の各成分から、局所アライメントの経路を得ることができる。しかも、ここで得られる動画像データに適合した類似度の算出は、Smith-Watermanアルゴリズムを単なる特例として含んでおり、生命情報配列の類似度を測る手法にも適用できる。
【０１５８】
そして、上述した作用効果は、上記の処理を実行することができる動画像検索装置や、上記の処理をコンピュータに実行させるための動画像検索プログラムにおいても同様に実現する。
【０１５９】
以上、本発明の実施の形態について説明したが、本発明はこうした実施の形態に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において、種々なる形態で実施し得ることは勿論である。例えば上述した各パラメータ値の設定は、入力装置４を介して適宜変更することも可能である。
【符号の説明】
【０１６０】
２２  特徴量抽出部
２３  動画像代表フレーム選出部
２４  類似度算出部（動画像検索部）
２５  類似動画像表示制御部（動画像検索部）
【図１】
2017021606.tif 000027
【図２】
2017021606.tif 000028
【図３】
2017021606.tif 000029
【図４】
2017021606.tif 000030
【図５】
2017021606.tif 000031
【図６】
2017021606.tif 000032
【図７】
2017021606.tif 000033
【図９Ａ】
2017021606.tif 000034
【図９Ｂ】
2017021606.tif 000035
【図９Ｃ】
2017021606.tif 000036
【図９Ｄ】
2017021606.tif 000037
【図９Ｅ】
2017021606.tif 000038
【図１３】
2017021606.tif 000039
【図１６】
2017021606.tif 000040
【図１７】
2017021606.tif 000041
【図１８】
2017021606.tif 000042
【図１９】
2017021606.tif 000043
【図２０】
2017021606.tif 000044
【図２１】
2017021606.tif 000045
【図２２Ａ】
2017021606.tif 000046
【図２２Ｂ】
2017021606.tif 000047
【図２３Ａ】
2017021606.tif 000048
【図２３Ｂ】
2017021606.tif 000049
【図２４】
2017021606.tif 000050
【図８】
2017021606.tif 000051
【図１０】
2017021606.tif 000052
【図１１】
2017021606.tif 000053
【図１２】
2017021606.tif 000054
【図１４】
2017021606.tif 000055
【図１５】
2017021606.tif 000056