DEIM Forum 2017 G6-3

複数の特徴量に対する検索結果の多様化と要約
董テイテイ†

西村 祥治†

劉健全†† NEC システムプラットフォーム研究所 〒 211–8666 神奈川県川崎市中原区下沼部 1753
E-mail: †t-dong@ce.jp.nec.com, ††s-nishimura@bk.jp.nec.com, †††j-liu@ct.jp.nec.com
あらまし

本論文では，多種多様な情報があるマルチメディアデータから抽出された，複数の特徴量に対する検索結果の多様化と要約の手法を提案する．ユーザからの検索要求を処理する際に，重複または類似している結果同士を整理し，多様化された代表的な結果を提示することで，ユーザの情報検索を効率化することを目的とする．提案手法では，データ集合の統計的な情報や相関など隠れた知識を利用し，検索条件に指定した特徴量だけではなく，指定されなかった特徴量も考慮し，効果的に検索結果の多様化と要約を行う．これにより，ユーザが検索結果を確認するまたは検索結果から所望の情報を得られる時間を減らす．
キーワード 特徴量，検索，多様化，要約

1. は じ め にに適用できないという問題がある．例えば，Web と文書デー
タ [1–3, 12, 13] や，構造化データ [11]，グラフデータ [19] など

情報取得と記憶技術の進展に伴い，ユーザが利用できる情報を対象に，それぞれの多様化手法が提案されたが，複数種類のは膨大かつ多様になってきている．例えば，インターネット上情報があるマルチメディアデータが扱えられない．例えば，[6]の文書や画像データ，防犯カメラで撮影した映像データ，GPSでは，距離関数の定義が必要であるため，複数種類の情報におセンサーから取得した位置情報など，様々なデータが簡単に入ける距離関数が適切に定義できない場合には適用できない．ま手でき，活用できる状況下にある．

た，画像データを対象に，検索結果の候補に対し特徴量を抽出

さらに，これらのデータから，複数種類の情報が利用できる，

してクラスタリングを行い，各クラスタから代表的な結果を選または抽出できる．例えば，メタデータとしての文書情報や撮択する方法も存在する [18]．しかし，クラスタリング方法では，

影場所としての位置情報，撮影時刻としての時間情報などが付検索を処理する際に必要となる計算量が高いため，検索要求にいている画像データから，複数種類の情報が利用等できる．具

対応するのは困難であると，代表的な結果の選定はクラスタリ

体的には，メタデータから直接位置情報などを抽出するだけでングのパラメータ設定に依存するため調整が困難であるというなく，画像データから RGB や SIFT，LBP などの画素情報を抽二つの問題点がある．

出でき，顔などの属性情報も認識できる．特に，認識技術の進本研究は，複数種類の情報があるマルチメディアデータから

歩により，年齢や性別，服の色など様々な属性が抽出できるよ抽出された，複数の特徴量に対する検索結果の多様化と要約をうになった [5, 8]．

行い，ユーザの情報検索を効率化することを目的とする．さらこのように，情報の量と種類の増大に従い，それらの情報をに，ユーザからの指定される検索条件だけではなく，データ集管理する，特に検索する機能は非常に重要となってきた．本研合に内在する統計的な情報などを利用して，できるだけユーザ

究では，多種多様な情報が混在したマルチメディアデータに対が望んでいる情報を含むように，多様化された代表的な結果をして，新たな検索処理技術を提案する．

ユーザに提示する．その結果，ユーザの情報検索が加速される．

一方，近年では，単に関連度 (relevance) に基づいた検索提案手法では，抽出された各特徴量に対し，データ集合から処 理 で は な く，結 果 の 多 様 性 (diversity) も 考 慮 し ，検 索 結

オブジェクトを特定する際に，ある特徴量の重要度を示す特徴

果 の 多 様 化 (diversification) に 関 す る 研 究 活 動 が 盛 ん で あ

量の表現力と，特徴量間の相関により他の特徴量からある特徴

る [1–3, 6, 9, 11–14, 18, 19, 21]．ユーザからの検索要求を処理量を推定できないことを示す特徴量の独立力を定義する．さする際に，検索条件に合致する，又は，類似する結果を並べる

らに，各オブジェクトが各特徴量における類似度と表現力と独だけでは不十分である．重複または類似している結果同士を整立力に基づき，他のオブジェクトとの差異度を示す多様性スコ

理して，代表的な結果を提示することで，ユーザが検索結果をアを定義する．多様性スコアが高いオブジェクトを代表的な結確認するまたは検索結果から所望の情報を得られる時間を短縮

果として選択し，多様性スコアが低いオブジェクトを結果オブする．多様化された結果を提示することにより，ユーザに望ま

ジェクトに割り当てる．その結果，重複又は類似している結果れる情報を提供する可能性を高め，異なるユーザのニーズに対が排除され，多様化された代表的な結果が選択される．

応でき，ニーズが曖昧な検索要求にも対処できる．
検索結果の多様化において，既存研究では，主に単一種類の

2. 関 連 研 究

情報があるデータが対象であり，その種類の情報に特有の性質

人物認識技術の進展により，様々な特徴量 (属性) が抽出さに基づくため，他の種類の情報と複数種類の情報があるデータ

れ，人物照合に使われる [15, 17]．RGB や SIFT，LBP などの低レベル (low-level) の特徴量や，年齢や性別，服の色など中レベ
ル (mid-level) の特徴量などを利用して，画像又は映像から人物を特定する [7, 16]．大量なデータから入力した人物を検索する
際に，検索結果の重複性が大きな課題となる．そのため，ソーシャル画像の抽出結果の多様化に関する取り組みが行われている [9]．画像データから抽出された特徴量に対して，クラスタ

1

リングを行い，各クラスタから代表的な結果を選択する [4, 20]．

3

2

4

Q

図 1 対象データ画像 (4 件) と入力画像 Q

しかし，クラスタリング方法では，検索を処理する際に必要となる計算量が高いため，検索要求に対応するのは困難であると，

S im( f ace)

代表的な結果の選定はクラスタリングのパラメータ設定に依存

f ace1するため調整が困難であるという二つの問題点がある．

f ace20.92

f ace30.81

0.82

f ace4

0.58

0.56

0.5

S im(color) color1

color2color3color4colorQ

0.98

0.1

0.89

0.98

0.1

0.9

0.96

0.1

0.1

検索結果の多様化に関するサーベイは [14, 21] にある．大きく内容に基づく多様化 (content-based diversification) と，被覆率に基づく多様化 (coverage-based diversification) と，目新しさに

f ace1color1

基づく多様化 (novelty-based diversification) に分類される．内容

color2に基づく多様化では，お互いに類似しないオブジェクトを選択する．被覆率に基づく多様化では，ユーザの検索条件の異なる

f ace2f ace3f ace4f aceQ

0.92

0.81

0.58

0.95

0.82

0.56

0.9

0.5

0.8

0.98

color30.1

0.1

color4

0.89

0.9

0.6

0.1

0.9

カテゴリ又は解釈をカバーするオブジェクトを選択する．目新図 2 顔 (face) と服の色 (color) に関する類似度

しさに基づく多様化では，すでに抽出したオブジェクトより新しい情報を含むオブジェクトを選択する．本手法はそれらのハ
イブリッドである．
検索結果の多様化において，既存研究では，主に単一種類の情報があるデータが対象である．例えば，Web と文書デー
タ [1–3, 12, 13] や，構造化データ [11]，グラフデータ [19] などを対象に，それぞれの多様化手法が提案された．しかし，これ現力と独立力を定義する．本手法では，各特徴量の類似性スコ
アと表現力と独立力に基づき，オブジェクトの類似性スコアと，他のオブジェクトとの差異度を示す多様性スコアを定義し，各オブジェクトの類似性スコアと多様性スコアにより，検索結果の多様化と要約を行う．

らの手法は，それぞれの種類の情報に特有の性質に基づくため，

以下では，図 1 に示している，対象データである画像 4 件と，他の種類の情報と複数種類の情報があるデータに適用できない．

検索入力である画像 1 件 Q を用いて説明する．画像データから

7

例えば，[6] では，オブジェクト間の距離関数の定義が必要であるため，複数種類の情報における距離関数が適切に定義できない場合には適用できない．また，構造化データ又はグラフデー
タに対する多様化手法は，Web と文書データと画像データを扱© NEC Corporation 2016

NEC Group Internal Use Only

顔と服の色の特徴量を抽出し，検索要求では各特徴量に関する
閾値と結果件数 k を指定することとする．
本研究では，オブジェクト間の各特徴量における類似度の計
算をブラックボックスとして，コサイン (cosine) など公知の類えることができない．それに対して，本手法は，情報の種類に似度定義で計算する．図 2 は図 1 の対象画像間の顔 (face) と服依存しないため，複数の情報があるデータにも対応できる．

の色 (color) に関する類似度を示す．画像 i と画像 j の顔におけ3. 問 題 定 義
本研究では，文書や音声，時間，位置，画素，属性など，複る類似度と服の色における類似度を，それぞれ S imi, j ( f ace) とS imi, j (color) で表す．例えば，画像１と画像 Q の顔における類似度は S im1,Q ( f ace) で表され，0.95 である．

数種類の情報があるマルチメディアデータが対象である．対象

ここでは，顔と服の色に関する閾値 S imτ ( f ace) と S imτ (color)

データの各オブジェクトに対し，それぞれの情報抽出方法またと結果件数 k を，S imτ ( f ace) = 0.8 と S imτ (color) = 0.6 と k = 3，

は認識エンジンを用いて，その情報に関する特徴量を計算する．
例えば，画像データの各画像に対して，撮影場所から位置情報の座標を計算したり，顔認識エンジンで顔の特徴量を抽出したりする．
ユーザからの検索要求として，例示情報や指定条件，パターンなどが考えられる．例えば，ユーザがサンプル画像又は音声を入力する，撮影場所と撮影時間を指定する，顔画像を入力し顔の類似度の閾値を指定する，指定文書が現れた回数を指定す

ユーザにより指定されるものとする．

3. 1 特徴量とオブジェクトの類似性スコア
特徴量の類似性スコアについて，指定特徴量との類似度や，
指定特徴量に関する閾値がある場合，閾値を重みとして類似度に付けたものなどが考えられる．ここでは，オブジェクト oi とo j に対して，特徴量 f の類似性スコア S I Moi ,o j ( f ) は，
S I Moi ,o j ( f ) = S imτ ( f ) ∗ S imoi ,o j ( f )(1)るなどが挙げられる．受け取った検索要求を特徴量と各特徴量で定義する．S imτ ( f ) は特徴量 f に関する閾値，S imoi ,o j ( f ) はに関する検索条件に変換する．

oi と o j の特徴量 f における類似度である．検索要求に特徴量の各特徴量に対して，特徴量の類似度に基づき，特徴量の類似性スコアを定義し，特徴量の特性と相関に基づき，特徴量の表

閾値が指定されない場合，デフォルト閾値を設定するか，デー
タ集合から計算したものを使う．

オブジェクトの類似性スコアは，各特徴量の類似性スコアの対象のデータ集合により変化する．例えば，顔が似ている人の集約（例：和，最大，最小，平均など）で定義することができ

画像データ集合の場合，顔よりも年齢や性別などの表現力と独る．ここでは，特徴量 f1 , . . . , fd において，オブジェクト oi と立力が高い．本研究では，データ集合の統計的な情報など隠れo j の類似性スコア S I M(oi , o j ) は，た知識を利用し，各特徴量の表現力と独立力を計算して，でき

S I M(oi , o j ) =dXるだけユーザが望んでいる情報を含むように，多様化された代S I Moi ,o j ( fm )

(2)

m=1

で定義する．
例えば，入力画像 Q に対して，顔と服の色を指定した場合，画表的な結果をユーザに提示する．その結果，ユーザの情報検索を加速する．
特徴量の表現力について，特徴量が稀であるほど重要であるとする場合，この特徴量を持つオブジェクトの数の逆数で定義

像１の類似性スコアは S I M(1, Q) = S imτ ( f ace) ∗ S im1,Q ( f ace) +することができる．特徴量の独立力について，特徴量 A に対す

S imτ (color) ∗ S im1,Q (color) = 0.8 ∗ 0.95 + 0.6 ∗ 0.98 = 1.348 でる特徴量 B の独立力は，特徴量 A を持つオブジェクトのうち，ある．

特徴量 B を持たないオブジェクトの割合で定義することが考え

3. 2 特徴量の表現力と独立力られる．

特徴量の表現力 (RP: Representation Power) は，特徴量の重要

ここでは，各特徴量の閾値を用いて，表現力と独立力を定義

度を示す指標である．換言すると，特徴量の表現力とは，デーする．オブジェクト oi の特徴量 f の表現力 RP( fi ) は， f におけ

タからオブジェクトを特定する際の当該特徴量の重要度を示す．

る類似度が閾値以上であるオブジェクト (oi を含む) の数の逆数

特徴量の表現力は，オブジェクトから抽出される複数の特徴量それぞれに関して計算される．また，特徴量の表現力とは，「この特徴量でオブジェクトを表現できる可能性」と捉えることもできる．例えば，世の中に顔が似ている人が少ないに対し，年齢が近い人は多いということがある．このことから，年齢より
顔で人を識別する方が容易である，又は，人を表現できる可能性が高いと言うことができる．そのため，年齢より顔の表現力の方が高いと言える．
従って，画像データから指定した顔と年齢を持つ人に関する画像を探す場合，年齢よりも表現力が高い顔を優先して，指定RP( fi ) =1
kR = {o p |S imoi ,o p ( f ) >= S imτ ( f )}kで定義する．kRk は集合 R の基数である．
オブジェクト o j の特徴量 fa, j に対して，オブジェクト oi の
特徴量 fb,i の独立力 IP( fb,i ; fa, j ) は，特徴量 fa における類似度が閾値以上であるオブジェクト (オブジェクト oi を含む) のうち， fb における類似度が閾値以下であるオブジェクトの割合

IP( fb,i ; fa, j ) =kRb = {o p |S imoi ,o p ( fb ) < S imτ ( fb ), o p ∈ Ra }kkRa = {o p |S imo p ,o j ( fa ) >= S imτ ( fa )}k(4)

した顔と似ている画像を検索結果の上位に提示するほうがよい．このような提示により，ユーザは検索結果から望んでいる
画像を発見する可能性が高くて，より早く必要な情報を見つけ出せる．
特徴量の独立力 (IP: Independence Power) は，特徴量間の相関により，別の特徴量からある特徴量を推定できないことを示す指標である．特徴量の独立力とは，「ある特徴量は他の特徴量に相関されない可能性」と捉えることもできる．例えば，顔が似ている人の年齢と性別も似ている可能性は高いのに対し，年齢と性別が似ている人の顔が似ているとは限らないということがある．このことは，年齢，性別は顔から推定できる，又は，年
齢，性別は顔に相関される可能性が高いと言うことができる．
そのため，顔に対して，年齢と性別の独立力が低い．逆に，年齢と性別に対して，顔の独立力が高い．また，似ている顔同士(3)で定義する．特徴量の独立力は非対称である．つまり，一般にIP( fb,i ; fa, j ) , IP( fa, j ; fb,i ), IP( fb,i ; fa, j ) , IP( fb, j ; fa,i ) である．
例えば，画像１の顔 f ace1 における類似度が閾値以上である
画像は ３ 件（画像１，２，３）あるため，画像１の顔の表現
力は RP( f ace1 ) = 1/3 である．画像１の服の色における類似度が閾値以上である画像 ３ 件（画像１，２，４）のうち，画像
２の顔における類似度が閾値以下である画像は １ 件（画像４）あるため，画像１の服の色 color1 に対して，画像２の顔 f ace2の独立力は IP( f ace2 ; color1 ) = 1/3 である．
特に，同種の特徴量 fb に関する独立力はオブジェクト同士 oiと o j が f における非類似度

IP( fb,i ; fb, j ) = 1 − S imoi ,o j ( fb )(5)はお互いの独立力が低い．
それにより，画像データから指定した年齢と性別を持つ人にで定義する．例えば，画像１の顔 f ace1 に対して，画像２の顔関する画像を探す場合，年齢と性別が近い異なる顔を持つ画像

f ace2 の独立力は IP( f ace2 ; f ace1 ) = 1 − 0.92 = 0.08 である．

を検索結果として提示する方がよい．このような提示により，ユーザは検索結果から望んでいる画像を発見する可能性が高くなり，より早く必要な情報を見つけ出せる．さらに，検索結果にある画像と重複又は類似している画像の各特徴量（例えば，
年齢と性別と顔）は，既存の結果画像の各特徴量に対する独立力が低いので，代表的な結果とする優先度が低い．
なお，上記特徴量の表現力と独立力は，一般の常識ではなく，オブジェクト o j の複数種類の特徴量に対する特徴量の独立力は，各特徴量 f j に対する特徴量の独立力の乗算

IP( fb,i ; f j ) = IP( fb,i ; f1, j , . . . , fd, j )= IP( fb,i ; f1, j ) ∗ · · · ∗ IP( fb,i ; fd, j )(6)で定義する．例えば，画像１の顔 f ace1 と服の色 color1 に対して，画像２の顔 f ace2 の独立力は IP( f ace2 ; f ace1 , color1 ) =IP( f ace2 ; f ace1 ) ∗ IP( f ace2 ; color1 ) = 0.08 ∗ 1/3 ≈ 0.027 である．
複数のオブジェクト o j , . . . , ok の特徴量に対する特徴量の独

Algorithm 1 多様化 DIVERSIFY(O, Q, k)
1: s, o s ← 0; T, C, R ← ∅;立力は，各画像の特徴量 f j , . . . , fk に対する特徴量の独立力の最

2: for Each oi in O do

小値

3:
4:

IP( fb,i ; f j , . . . , fk ) = min{IP( fb,i ; f j ), . . . , IP( fb,i ; fk )}

(7)

5:
6:

. 初期化
. 類似オブジェクトの計算

if S I M(oi , Q) > s thens ← S I M(oi , Q); o s ← oi ;else
Insert oi into T ;で 定 義 す る ．例 え ば ，画 像 １ の 顔 f ace1 と 服 の 色 color17:と，画像３の顔 f ace3 と服の色 color3 に対して，画像２の8: end for

顔 f ace2 の 独 立 力 は, IP( f ace2 ; f ace1 , color1 , f ace3 , color3 ) =9: Insert o s into R;

min{IP( f ace2 ; f ace1 , color1 ), IP( f ace2 ; f ace3 , color3 )} = min{0.08∗

10: while |R| < k do

1/3, 0.18 ∗ 0/3} = 0 である．

11:

C ← T ; T ← ∅; s, o s ← 0;

12:

for Each oi in C do

3. 3 オブジェクトの多様性スコア
オブジェクトの多様性スコアは，指定した各特徴量における類似度と表現力と独立力の乗算を合計し，指定しない各特徴量13:

end ifs ← DIV(oi ; R); o s ← oi ;elseにおける表現力と独立力の乗算を合計し，それらの総和である

16:と定義する．また，指定しない各特徴量における類似度を１と17:

し，オブジェクトの多様性スコアは，各特徴量における類似度

18:

end forと表現力と独立力の乗算を合計したものであると考えても良い．

19:

Insert o s into R;

オブジェクト o j に対して，オブジェクト oi の多様性スコア

DIV(oi ; o j ) は
DIV(oi ; o j ) =dXS imoi ,Q ( fm ) ∗ RP( fm,i ) ∗ IP( fm,i ; f j )(8)で定義する．オブジェクト集合 S = {o j , . . . , ok } に対して，オブ

20: end while
21: return R;

表現力と独立力を考慮することで，検索条件を調整することが提示することで，検索条件に対する誘導もできる．
検索結果の多様化と要約を行う．検索結果の多様化では，類似

DIV(oi ; S ) = DIV(oi ; {o j , . . . , ok })S imoi ,Q ( fm ) ∗ RP( fm,i ) ∗ IP( fm,i ; f j , . . . , fk ). 計算した多様オブジェクトを R に挿入

本手法では，定義した類似性スコアと多様性スコアに基づき，ジェクト oi の多様性スコア DIV(oi ; o j , . . . , ok ) は=

Insert oi into T ;end if

できるだけではなく，指定しない特徴量を持つ探索的な結果を

m=1

d
X

. 初期化
. 多様オブジェクトの計算

if DIV(oi ; R) > s then

14:
15:

. 計算した類似オブジェクトを R に挿入

性スコアが高い類似オブジェクトと，多様性スコアが高い多様

(9)

m=1

オブジェクトを，結果オブジェクトとして選出する．具体的に，指定した結果件数 k に対して，類似オブジェクト 1 件と多様オ

で 定 義 す る ．例 え ば ，顔 を 指 定 し た 場 合 ，画 像 １ に 対

ブジェクト k − 1 件を選出することとする．場合によっては，類し て ，画 像 ２ の 多 様 性 ス コ ア DIV(2; 1) は ，DIV(2; 1) =似オブジェクトと多様オブジェクトの件数を調整しても良い．

S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace1 , color1 ) + RP(color2 ) ∗例えば，複数の類似性スコアを定義し，複数の類似オブジェク

IP(color2 ; f ace1 , color1 ) = 0.9 ∗ 1/3 ∗ 0.08 ∗ 1/3 + 1/3 ∗ 1/3 ∗ 0.02 ≈トを計算しても良い．

0.01 である．

4. 検索結果の多様化と要約

検索結果の要約では，オブジェクトが各結果オブジェクトに対する多様性スコアを計算し，最小となる結果オブジェクトにそのオブジェクトを割り当て従属させる．

従来の技術では，ユーザからの検索要求を変換した各特徴量

また，多様化と要約が必要な対象オブジェクトは抽出されたに対する検索条件に対して，指定した特徴量との適合性を示すこととする．ここでは，類似索引 Luigi [10] を用いて，各特徴

類似性スコアに基づき検索結果を計算する．本手法は，類似性量を格納し，各特徴量の閾値以上であるオブジェクトを対象オ

スコアだけではなく，指定した特徴量の表現力と独立力も考慮

ブジェクト集合 O として抽出する．具体的に，特徴量の種類

し，類似性スコアが高くて表現力と独立力が高い特徴量を持つごとに，データベースの各オブジェクトの特徴量を抽出し，抽結果を優先することで，重複又は類似している結果を排除し，出された特徴量とオブジェクトの索引を構築する．与えられた

代表的な結果を選択する．さらに，本手法は指定しない特徴量

検索要求に対して，各索引から各特徴量の閾値以上であるオブの表現力と独立力も考慮することで，検索条件に柔軟に対応でジェクトを計算して抽出する．抽出されたオブジェクトを統合

き，ユーザが検索条件を調整する手間を省くことができる．

し，対象オブジェクト集合とする．

例えば，ユーザの検索条件の設定は不適切または間違いがある場合や，抽出方法の精度が低いまたはデータに欠損があるな

次に，Algorithm 1 と Algorithm 2 のアルゴリズムを参照して，それぞれ検索結果の多様化と要約について詳細に説明する．

どにより，抽出された特徴量の質が低い場合など，データ集合

4. 1 検索結果の多様化の隠れた知識である特徴量の表現力と独立力を考慮することで，

まず，スコア変数 s と，オブジェクト o s と，オブジェクト集

自動的に検索条件を調整することができ，指定しない特徴量の合 T と，候補オブジェクト集合 C と，結果オブジェクト集合 R

て，s と o s を初期化し，R の結果オブジェクト R j に対する多様Algorithm 2 要約 SUMMARIZE(T , R)
1: for Each oi in T do

. オブジェクトの要約

性スコア DIV(oi ; R j ) を計算する．s と o s で最小の多様性スコア2:s ← ∞; o s ← 0;

. 初期化と対応するオブジェクトを保持する．計算した DIV(oi ; R j ) は s

3:for Each R j in R do

4:

if DIV(oi ; R j ) < s thens ← DIV(oi ; R j ); o s ← R j ;5:
6:

end if

7:

end for8:

oi を o s に割り当てる;

より小さい場合， s を DIV(oi ; R j ) に，o s を R j に，それぞれ更新する．そうでなければ，R の次のオブジェクトに続ける．多様性スコアが最小の結果オブジェクトを見つけるまで，この過程を繰り返す．また，多様性スコアが最小の結果オブジェクトを見つけた時点で反復を終了し，R の全てのオブジェクトに対

9: end for

して計算しなくても良い．場合により，T に残った全てのオブ

10: return R;

ジェクトを要約しなくても良い．最後に，R を出力し終了する．

4. 3 実 行 例を初期化する．また，k 件の結果を計算することとする．類似

次に，具体的な実行例１と２を用いて本手法を説明する．例

オブジェクトの計算では，類似性スコアが最大のオブジェクト

１は顔を指定した場合，例２は顔と服の色を指定した場合でを計算する．データベース O の各オブジェクト oi に対して，変ある．

換した検索条件に対する類似性スコア S I M(oi , Q) を計算する．

s と o s で最大の類似性スコアと対応するオブジェクトを保持する．計算した S I M(oi , Q) は s より大きい場合， s を S I M(oi , Q)

【例１】例１では，入力画像 Q の顔 f aceQ と顔に関する閾
値 S imτ ( f ace) = 0.8 の検索条件に基づき，結果 k = 3 件を出力する．まず，Algorithm 1 のアルゴリズムに示しているように，に，o s を oi に，それぞれ更新する．そうでなければ，oi をオ

各画像の類似性スコアを計算し，類似性スコアが最大である類

ブジェクト集合 T に挿入し保持する．類似性スコアが最大のオ似画像を選択する．

ブジェクトを見つけるまで，この過程を繰り返す．また，類似
オブジェクトを見つけた時点で反復を終了し，O の全てのオブジェクトに対して計算しなくても良い．

S I M(1, Q) = S imτ ( f ace) ∗ S im1,Q ( f ace) = 0.8 ∗ 0.95 = 0.76
S I M(2, Q) = S imτ ( f ace) ∗ S im2,Q ( f ace) = 0.8 ∗ 0.9 = 0.72

計算した類似オブジェクトを R に挿入し保持する．ここでは，

S I M(3, Q) = S imτ ( f ace) ∗ S im3,Q ( f ace) = 0.8 ∗ 0.8 = 0.64

類似性スコアが最大のオブジェクトを 1 件計算するが，場合にS I M(4, Q) = S imτ ( f ace) ∗ S im4,Q ( f ace) = 0.8 ∗ 0.6 = 0.48

より，複数の類似オブジェクトを計算し，R に保持しても良い．
例えば，複数の類似性スコアを定義し，複数の類似オブジェク
トを計算する．

により，画像１を類似画像として選択する．
次に，画像１に対して，画像２，３，４の多様性スコアを計
算し，多様性スコアが最大である多様画像を選択する．

多様オブジェクトの計算では，多様化性スコアが高いオブジェクトを計算する．候補オブジェクト集合 C を T に更新すDIV(2; 1) = S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace1 , color1 )る．また，T と s と o s を初期化する．C の各オブジェクト oi+ RP(color2 ) ∗ IP(color2 ; f ace1 , color1 )に対して，R のオブジェクトに対する多様性スコア DIV(oi ; R)

= 0.9 ∗ 1/3 ∗ 0.08 ∗ 1/3 + 1/3 ∗ 1/3 ∗ 0.02 ≈ 0.01を計算する． s と o s で最大の多様性スコアと対応するオブジェ
クトを保持する．計算した DIV(oi ; R) は s より大きい場合， s

DIV(3; 1) = S im3,Q ( f ace) ∗ RP( f ace3 ) ∗ IP( f ace3 ; f ace1 , color1 )を DIV(oi ; R) に，o s を oi に，それぞれ更新する．そうでなけ+ RP(color3 ) ∗ IP(color3 ; f ace1 , color1 )れば，oi をオブジェクト集合 T に挿入し保持する．多様性スコ= 0.8 ∗ 1/3 ∗ 0.19 ∗ 1/3 + 1/1 ∗ 2/3 ∗ 0.9 ≈ 0.62

アが最大のオブジェクトを見つけるまで，この過程を繰り返す．
また，多様オブジェクトを見つけた時点で反復を終了し，C の全てのオブジェクトに対して計算しなくても良い．
計算した多様オブジェクトを R に挿入し保持する．R の結果
オブジェクトの数は k 件に達する際に，検索結果の要約を行わない場合，R を出力し終了する．検索結果の要約も行う場合，

Algorithm 2 のオブジェクトの要約に続ける．k 件に達しない場
合，C を T に更新し， s と o s と T を初期化し，次の多様オブジェクトを計算する．

DIV(4; 1) = S im4,Q ( f ace) ∗ RP( f ace4 ) ∗ IP( f ace4 ; f ace1 , color1 )+ RP(color4 ) ∗ IP(color4 ; f ace1 , color1 )= 0.6 ∗ 1/1 ∗ 0.42 ∗ 2/3 + 1/3 ∗ 1/3 ∗ 0.11 ≈ 0.18
により，画像３を多様画像として選択する．
その次に，画像１と３に対して，画像２，４の多様性スコアを計算し，多様性スコアが最大である多様画像を選択する．

DIV(2; 1, 3) = S im2,Q ( f ace) ∗ RP( f ace2 )4. 2 検索結果の要約∗ IP( f ace2 ; f ace1 , color1 , f ace3 , color3 )

要約では，多様性スコアが低いオブジェクトをまとめて，代+ RP(color2 ) ∗ IP(color2 ; f ace1 , color1 , f ace3 , color3 )表的な結果に従属させ要約する．具体的に，T に残ったオブジェ
クトを R の結果オブジェクトに対する多様化性スコアが最小の結果オブジェクトに割り当てる．T の各オブジェクト oi に対し= 0.9 ∗ 1/3 ∗ min{0.08 ∗ 1/3, 0.18 ∗ 0/3}
+ 1/3 ∗ min{1/3 ∗ 0.02, 1/3 ∗ 0.9} ≈ 0.002

DIV(4; 1, 3) = S im4,Q ( f ace) ∗ RP( f ace4 )DIV(2; 1) = S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace1 , color1 )∗ IP( f ace4 ; f ace1 , color1 , f ace3 , color3 )+ S im2,Q (color) ∗ RP(color2 ) ∗ IP(color2 ; f ace1 , color1 )+ RP(color4 ) ∗ IP(color4 ; f ace1 , color1 , f ace3 , color3 )= 0.9 ∗ 1/3 ∗ 0.08 ∗ 1/3 + 0.96 ∗ 1/3 ∗ 1/3 ∗ 0.02 ≈ 0.01

= 0.6 ∗ 1/1 ∗ min{0.42 ∗ 2/3, 0.5 ∗ 1/1}

DIV(3; 1) = S im3,Q ( f ace) ∗ RP( f ace3 ) ∗ IP( f ace3 ; f ace1 , color1 )+ 1/3 ∗ min{1/3 ∗ 0.11, 1/3 ∗ 0.9} ≈ 0.18

+ S im3,Q (color) ∗ RP(color3 ) ∗ IP(color3 ; f ace1 , color1 )= 0.8 ∗ 1/3 ∗ 0.19 ∗ 1/3 + 0.1 ∗ 1/1 ∗ 2/3 ∗ 0.9 ≈ 0.08

により，画像４を多様画像として選択する．これで，結果画像

3 件を計算した．

DIV(4; 1) = S im4,Q ( f ace) ∗ RP( f ace4 ) ∗ IP( f ace4 ; f ace1 , color1 )

最後に，画像２の結果画像１と３と４に対する多様性スコア+ S im4,Q (color) ∗ RP(color4 ) ∗ IP(color4 ; f ace1 , color1 )を比較し，画像２を多様性スコアが最小である結果画像に要約= 0.6 ∗ 1/1 ∗ 0.42 ∗ 2/3 + 0.9 ∗ 1/3 ∗ 1/3 ∗ 0.11 ≈ 0.18

する．

DIV(2; 3) = S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace3 , color3 )+ RP(color2 ) ∗ IP(color2 ; f ace3 , color3 )= 0.9 ∗ 1/3 ∗ 0.18 ∗ 0/3 + 1/3 ∗ 1/3 ∗ 0.9= 0.1 > DIV(2; 1)

により，画像４を多様画像として選択する．
その次に，画像１と４に対して，画像２，３の多様性スコアを計算し，多様性スコアが最大である多様画像を選択する．

DIV(2; 1, 4) = S im2,Q ( f ace) ∗ RP( f ace2 )DIV(2; 4) = S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace4 , color4 )∗ IP( f ace2 ; f ace1 , color1 , f ace4 , color4 ) + S im2,Q (color)+ RP(color2 ) ∗ IP(color2 ; f ace4 , color4 )∗ RP(color2 ) ∗ IP(color2 ; f ace1 , color1 , f ace4 , color4 )= 0.9 ∗ 1/3 ∗ 0.44 ∗ 1/3 + 1/3 ∗ 1/1 ∗ 0.1= 0.9 ∗ 1/3 ∗ min{0.08 ∗ 1/3, 0.44 ∗ 1/3}

≈ 0.08 > DIV(2; 1)+ 0.96 ∗ 1/3 ∗ min{1/3 ∗ 0.02, 1/1 ∗ 0.9} ≈ 0.01

により，画像２を結果画像１に要約する．

DIV(3; 1, 4) = S im3,Q ( f ace) ∗ RP( f ace3 )【例２】例２では，入力画像 Q の顔と服の色である f aceQ と∗ IP( f ace3 ; f ace1 , color1 , f ace4 , color4 ) + S im3,Q (color)colorQ と，顔と服の色に関する閾値である S imτ ( f ace) = 0.8 と∗ RP(color3 ) ∗ IP(color3 ; f ace1 , color1 , f ace4 , color4 )S imτ (color) = 0.6 の検索条件に基づき，結果 k = 3 件を出力す= 0.8 ∗ 1/3 ∗ min{0.19 ∗ 1/3, 0.5 ∗ 1/3}

る．まず，Algorithm 1 のアルゴリズムに示しているように，各+ 0.1 ∗ 1/1 ∗ min{2/3 ∗ 0.9, 1/1 ∗ 0.9} ≈ 0.08

画像の類似性スコアを計算する．

S I M(1, Q) = S imτ ( f ace) ∗ S im1,Q ( f ace)
+ S imτ (color) ∗ S im1,Q (color)= 0.8 ∗ 0.95 + 0.6 ∗ 0.98 = 1.348
S I M(2, Q) = S imτ ( f ace) ∗ S im2,Q ( f ace)
+ S imτ (color) ∗ S im2,Q (color)

により，画像３を多様画像として選択する．これで，結果画像

3 件を計算した．
最後に，画像２の結果画像１と４と３に対する多様性スコアを比較し，画像２を多様性スコアが最小である結果画像に要約する．

DIV(2; 3) = S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace3 , color3 )= 0.8 ∗ 0.9 + 0.6 ∗ 0.96 = 1.296+ S im2,Q (color) ∗ RP(color2 ) ∗ IP(color2 ; f ace3 , color3 )S I M(3, Q) = S imτ ( f ace) ∗ S im3,Q ( f ace)

= 0.9 ∗ 1/3 ∗ 0.18 ∗ 0/3 + 0.96 ∗ 1/3 ∗ 1/3 ∗ 0.9+ S imτ (color) ∗ S im3,Q (color)= 0.096 > DIV(2; 1)= 0.8 ∗ 0.8 + 0.6 ∗ 0.1 = 0.7

DIV(2; 4) = S im2,Q ( f ace) ∗ RP( f ace2 ) ∗ IP( f ace2 ; f ace4 , color4 )S I M(4, Q) = S imτ ( f ace) ∗ S im4,Q ( f ace)

+ S im2,Q (color) ∗ RP(color2 ) ∗ IP(color2 ; f ace4 , color4 )+ S imτ (color) ∗ S im4,Q (color)= 0.9 ∗ 1/3 ∗ 0.44 ∗ 1/3 + 0.96 ∗ 1/3 ∗ 1/1 ∗ 0.1= 0.8 ∗ 0.6 + 0.6 ∗ 0.9 = 1.02

= 0.076 > DIV(2; 1)

により，画像１を類似画像として選択する．
次に，画像１に対して，画像２，３，４の多様性スコアを計
算し，多様性スコアが最大である多様画像を選択する．

により，画像２を結果画像１に要約する．

5. 考

察

本論文では，複数の情報があるマルチメディアデータから抽出された，複数の特徴量に対する検索結果の多様化と要約の手法を提案する．提案手法では，特徴量の表現力と独立力を定義

し，検索条件に指定した特徴量の類似性スコアだけではなく，全ての特徴量の表現力と独立力に基づき定義した多様性スコア
で検索結果の多様化と要約を行い，代表的な結果を選択することと，重複又は類似している結果をまとめることができる．さらに，本手法は指定しない特徴量の表現力と独立力を考慮することで，検索条件に柔軟に対応でき，ユーザが検索条件を調整する手間を省くことができる．
例えば，ユーザによる検索条件の設定が不適切又は間違いである場合や，抽出方法の精度が低い又はデータに欠損があるな
どにより，抽出された特徴量の質が低い場合などがある．このような場合であっても，データ集合の隠れた知識である特徴量の表現力と独立力を考慮することで，自動的に検索条件が調整される．さらに，指定しない特徴量の表現力と独立力を考慮することで，検索条件が調整されるだけではなく，指定しない特徴量を持つ探索的な結果を提示することで，検索条件に対する誘導も可能となる．つまり，検索処理では，ユーザからの検索条件により指定されない特徴量であって，代表的な結果オブジェクトの選択に使用された特徴量をユーザに提示すればよい．
例えば，ユーザが検索条件として「服の色」を指定したが，特徴量の表現力と独立力を考慮した結果，「服の色」とは異なる「顔」に係る特徴量を結果オブジェクトの選択に使用する場合には，「顔」や「顔の特徴量」をユーザに提示してもよい．その上，本手法は，特徴量に関する検索条件がない場合，全ての特徴量を考慮し，データ集合に対するクラスタリングにも使える．
今後は，手法の効率化と実証実験を行い，画像や動画データなどのマルチメディアデータに対する検索に実用できることを
目指す．

文

献

[1] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and SamuelIeong. Diversifying search results. In WSDM, pages 5–14, 2009.
[2] Gabriele Capannini, Franco Maria Nardini, Raffaele Perego, andFabrizio Silvestri. Efficient diversification of web search results.
PVLDB, 4(7):451–459, 2011.
[3] Van Dang and W. Bruce Croft. Diversity by proportionality: anelection-based approach to search result diversification. In ACM SIGIR, pages 65–74, 2012.
[4] Duc-Tien Dang-Nguyen, Giulia Boato, Francesco G. B. De Natale, Luca Piras, Giorgio Giacinto, Franco Tuveri, and Manuela Angioni. Multimodal-based diversified summarization in social image
retrieval. In MediaEval, 2015.
[5] Antitza Dantcheva, Petros Elia, and Arun Ross. What else does yourbiometric data reveal? A survey on soft biometrics. IEEE Trans.
Information Forensics and Security, 11(3):441–467, 2016.
[6] Marina Drosou and Evaggelia Pitoura. Multiple radii disc diversity: Result diversification based on dissimilarity and coverage. ACM
Trans. Database Syst., 40(1):4, 2015.
[7] Rogério Schmidt Feris, Russell Bobbitt, Lisa M. Brown, and Sharath
Pankanti. Attribute-based people search: Lessons learnt from a practical surveillance system. In International Conference on Multimedia
Retrieval (ICMR), page 153, 2014.
[8] Shaogang Gong, Marco Cristani, Shuicheng Yan, and Chen Change
Loy, editors. Person Re-Identification. Advances in Computer Vision
and Pattern Recognition. Springer, 2014.
[9] Bogdan Ionescu, Alexandru-Lucian Gı̂nsca, Maia Zaharieva, Bogdan Boteanu, Mihai Lupu, and Henning Müller. Retrieving diverse
social images at mediaeval 2016: Challenge, dataset and evaluation.

In MediaEval, 2016.
[10] Jianquan Liu, Shoji Nishimura, and Takuya Araki. Antiloiter: A loitering discovery system for longtime videos across multiple surveillance cameras. In ACM MM, pages 675–679, 2016.
[11] Ziyang Liu and Yi Chen. Differentiating search results on structured
data. ACM Trans. Database Syst., 37(1):4, 2012.
[12] Davood Rafiei, Krishna Bharat, and Anand Shukla. Diversifying web
search results. In WWW, pages 781–790, 2010.
[13] Rodrygo L. T. Santos, Craig Macdonald, and Iadh Ounis. Exploiting
query reformulations for web search result diversification. In WWW,
pages 881–890, 2010.
[14] Rodrygo L. T. Santos, Craig MacDonald, and Iadh Ounis. Search result diversification. Foundations and Trends in Information Retrieval,9(1):1–90, 2015.
[15] Walter J. Scheirer, Neeraj Kumar, Peter N. Belhumeur, and Terrance E. Boult. Multi-attribute spaces: Calibration for attribute fusionand similarity search. In CVPR, pages 2933–2940, 2012.
[16] Behjat Siddiquie, Rogério Schmidt Feris, and Larry S. Davis. Image ranking and retrieval based on multi-attribute queries. In CVPR,
pages 801–808, 2011.
[17] Chi Su, Shiliang Zhang, Junliang Xing, Wen Gao, and Qi Tian.
Deep attributes driven multi-camera person re-identification. CoRR,
abs/1605.03259, 2016.
[18] Reinier H. van Leuken, Lluis Garcia Pueyo, Ximena Olivares, andRoelof van Zwol. Visual diversification of image search results. In
WWW, pages 341–350, 2009.
[19] Zhengwei Yang, Ada Wai-Chee Fu, and Ruifeng Liu. Diversified
top-k subgraph querying in a large graph. In SIGMOD, pages 1167–
1182, 2016.
[20] Maia Zaharieva. An adaptive clustering approach for the diversification of image retrieval results. In MediaEval, 2016.
[21] Kaiping Zheng, Hongzhi Wang, Zhixin Qi, Jianzhong Li, and Hong
Gao. A survey of query result diversification. Knowledge and Information Systems, pages 1–36, 2016.