saguar1

YANAI Lab.

電気通信大学 総合情報学科/大学院 総合情報学専攻 メディア情報学コース 柳井研究室
電気通信大学 > 情報工学科 > コンピュータ学講座 > 柳井研究室 > 研究紹介  

Earth Mover's Distance $B$rMQ$$$?N`;w(B Web $BF02h8!:w(B

$B9bED(B $B2BM$(B

2008$BG/(B 2$B7n(B 7$BF|(B

1 $B$O$8$a$K(B

$B6aG/!$(BWeb$B>e$G$O$+$D$F$J$$$[$IKDBg$JNL$NF02h$r1\Mw$G$-$k>u67$K$J$C$F$$$k!%(B $B$7$+$7$J$,$i!$$=$l$i$N8!:w%7%9%F%`$K$D$$$F$O%F%-%9%H%Y!<%9%H$J$b$N$,MxMQ$5$l$F$$$k$N$,8=>u$G$"$k!%(B $B$3$N>l9g!$%f!<%6$K$h$C$FIU2C$5$l$?%?%0$H8F$P$l$k%-!<%o!<%I$r4p$K8!:w$r9T$J$&$N$,0lHLE*$G$"$k$,!$(B $BIU2C$9$k%?%0$NA*Br$O%f!<%6$N $B$3$l$i%?%0$@$1$G$OH=JL$G$-$J$$FbMF$N:90[$rG'<1$9$k$?$a$K$O!$(B $BF02h<+?H$NFCD'NL$r9MN8$9$k$3$H$,=EMW$G$"$j!$(B $B$3$l$i$N8&5f$O(B TRECVID [1]$B$rCf?4$K@9$s$K?J$a$i$l$F$$$k!%(B $BK\8&5f$G$O!$$3$l$i$NFCD'NL$NHf3S4p=`$K(B Earth Mover's Distance $B$rMxMQ$7!$(B $B%-!<%U%l!<%`?t$N0[$J$kF02h4V$G$NN`;wEY;;=P$r2DG=$H$9$k$3$H$G!$(B $B%-!<%U%l!<%`$4$H$NFCD'NL$r4p$K$7$?N`;wF02h8!:w$r;n$_$k!%(B $B$^$?!$(BYouTube [2]$B$+$iF02h$r<}=8$7!$I>2A

2 $BJ}?K(B

$B2hA|4V$NN`;wEY$r;;=P$9$k$?$a$N4p=`$H$7$F!$(B Rubner $B$i$K$h$C$FDs0F$5$l$?(B Earth Mover's Distance (EMD) [3]$B$,$"$k$,!$(B Peng $B$i$O!$$3$l$rF02h$N%/%j%C%W4V$NN`;wEY$r;;=P$9$k$?$a$N4p=`$H$7$FMxMQ$9$k$3$H$G!$(B $B%7%g%C%H?t$,0[$J$k%/%j%C%W4V$NN`;wEY;;=P$r2DG=$H$7$?(B[4]$B!%(B $BK\8&5f$G$O!$(BPeng $B$i$N

3 $BDs0F

$BK\8&5f$N8!:w

\begin{table}\begin{center}
\begin{tabular*}{79mm}{cp{60mm}} \hline\hline
\multi...
...$B$r4p$KN`;wF02h$r8!:w$9$k!%(B \\ \hline\hline
\end{tabular*}\end{center}\end{table}

$B0J2\:Y$r@bL@$9$k!%(B

3.1 $BFCD'NLCj=P(B

$BK\8&5f$G$O!$0J2<$K<($9(B4$B$D$NFCD'NL$rMxMQ$9$k!%(B $B$J$*!$$=$l$>$l$NCM$O(B$[0,1]$$B$K$J$k$h$&$K@55,2=$r9T$J$&!%(B

3.1.0.1 0. $B?'FCD'(B

$B%-!<%U%l!<%`$r(B4$BJ,3d$7!$$=$l$>$l$K$D$$$F%+%i!<%R%9%H%0%i%`$r:n@.$9$k!%(B $B?'6u4V$O(B L*a*b* $BI=?'7O$rMxMQ$7!$ $5\times3\times3=45$$B

3.1.0.2 i. $B2;FCD'(B

$B%-!<%U%l!<%`$NA08e9g7W(B1$BIC4V$N2;@<$NBg$-$5$r2r@O$7!$(B $B$=$l$i$NJ?6QCM$rCj=P$9$k!%(B

3.1.0.3 ii. $B%*%W%F%#%+%k%U%m!<(B

$B%-!<%U%l!<%`$NA08e9g7W(B1$BIC4V$K$D$$$F!$(B $BA4NY@\%U%l!<%`4V$N%*%W%F%#%+%k%U%m!<$r;;=P$7!$(B $B$=$l$i$NJ?6QCM$rCj=P$9$k!%(B $B%*%W%F%#%+%k%U%m!<$N;;=P$K$O(BLucas-Kanade$BK!(B[5]$B$rMxMQ$9$k!%(B

3.1.0.4 iii. $B%-!<%U%l!<%`%]%8%7%g%s(B

$BF02h$NCf$G$N%-!<%U%l!<%`$N:F@80LCV$r!$;O$a$r(B0$B!$=*$j$r(B1$B$H$7$F!$(B$[0,1]$$B$NFCD'NL$H$7$FCj=P$9$k!%(B

3.2 $BN`;wEY7W;;(B

$BCj=P$7$?FCD'NL$r4p$K!$A4F02h4V$N(B EMD $B$K4p$E$/N`;wEY$N;;=P$r9T$J$&!%(B $BK\8&5f$G$O!$%-!<%U%l!<%`$NFCD'NL$G%7%0%M%A%c$r:n@.$7!$(B $B$=$N%-!<%U%l!<%`$,4^$^$l$k%7!<%s$ND9$5$r3F%7%0%M%A%c$N=E$_$H$9$k$3$H$G!$(BEMD $B$K4p$E$$$?N`;wEY$r;;=P$9$k!%(B $BN`;wEY$NCM$O(B$[0,1]$$B$G;;=P$5$l!$(B2$B$D$NF02h$,N`;w$7$F$$$k$[$I(B1$B$K6a$$CM$r$H$k!%(B

3.3 $BN`;wF02h8!:w(B

$B;;=P$7$?N`;wEY$r4p$KN`;wF02h$N8!:w$r9T$J$&!%(B $BK\8&5f$G$O!$(B2$B

3.3.0.1 0. $B%i%s%-%s%08!:w(B

$B%/%(%jF02h$KBP$7$F$NN`;wEY$r4p$K!$7k2L$r%i%s%-%s%07A<0$GI=<($9$k(B($B?^(B1)$B!%(B $BFCD'NL$N=E$_IU$1$O!$%f!<%6$,9T$J$($k$b$N$H$9$k!%(B

$B?^(B 1: =75mm $B%i%s%-%s%08!:w$NNc(B($B0lHV>e$,%/%(%jF02h$G$"$j!$0J2
\includegraphics[clip,width=1.00\hsize]{eps/similarity_ranking.eps}

3.3.0.2 i. $B%/%i%9%?%j%s%08!:w(B

$B8!:wBP>]$NF02h$r!$3,AXE*%/%i%9%?%j%s%0$r9T$J$&$3$H$GJ#?t$N%0%k!<%W$KJ,3d$7!$(B $BF02h$rJ,N`$7$?>uBV$GI=<($9$k(B($B?^(B2)$B!%(B $BK\8&5f$G$O!$N`;wEY$NBg$-$$$b$N$+$i=g$K%0%k!<%W2=$7$F$$$-!$(B $B$=$NN`;wEY$,ogCM$h$j>.$5$/$J$k$^$GB3$1$k$3$H$G%/%i%9%?%j%s%0$r9T$J$&!%(B $B%0%k!<%W4V$NN`;wEY$N;;=P$K$O72J?6QK!(B(group average method)$B!$(B $B:GC;5wN%K!(B(nearest neighbor method)$B!$:GD95wN%K!(B(furthest neighbor method) [6]$B$N(B3$B$D$rMxMQ$7!$%f!<%6$,A*Br$G$-$k$b$N$H$9$k!%(B

$B?^(B 2: =75mm $B%/%i%9%?%j%s%08!:w$NNc(B($B3F2hA|$,3FF02h$N%5%`%M%$%k$G$"$j!$F02h?t$N9_=g$KJ,N`7k2L$,JB$V(B)
\includegraphics[clip,width=1.00\hsize]{eps/hierarchical_clustering.eps}

4 $BI>2A

$B%i%s%-%s%08!:w$H%/%i%9%?%j%s%08!:w$=$l$>$l$NJ}K!$K$D$$$F!$I>2A

4.1 $B

$B$l(B20$B8D$N@52rF02h$H!$;D$j(B80$B8D$NIT@52rF02h$+$i9=@.$5$l$F$$$k!%(B $B$J$*!$K\8&5f$G$O;n9gF02h$r@52rF02h!$$=$l0J30$rIT@52rF02h$H$7$F!$$=$l$>$l$NF02h$r<}=8$7$?!%(B

4.2 $B%i%s%-%s%08!:w(B

4.2.1 $B

$B3F@52rF02h$K$D$$$F!$F10l%?%0$N;D$jA4(B99$B8D$NF02h$KBP$7$F$N%i%s%-%s%08!:w$r9T$J$$!$(B $B$=$l$>$l$N%?%0$NA4@52rF02h$KBP$9$kJ?6QE,9gN((B(AP: average precision)$B$H!$(B $B$=$NJ?6QCM(B(MAP: mean average precision)$B$r5a$a$k!%(B $BJ?6QE,9gN($H$O!$8!:w7k2L$K$*$1$k3F:F8=N((B(recall)$B%l%Y%k$G$NE,9gN((B(precision)$B$NJ?6QCM$G$"$j!$(B

  $\textstyle AP = \frac{1}{n} \sum^{}_{n} P_i$   (1)
  $\textstyle \hspace{0mm} {\scriptstyle n:\ } \mbox{\scriptsize $B@52rF02h$N?t(B}$    
  $\textstyle \hspace{0mm} {\scriptstyle P_i:\ } \mbox{\scriptsize$i$$BHVL\$N@52rF02h$,8!:w$5$l$?;~E@$G$NE,9gN((B}$    
       

$B$N<0$GI=$5$l$k!%(B $B$lC1BN$GMxMQ$7$?>l9g$H!$(B $B%?%0$4$H$K:GE,$J=E$_IU$1$GA4FCD'NL$rMxMQ$7$?>l9g$N9g7W(B5$B$D$K$D$$$F$NCM$r5a$a$k!%(B

4.2.2 $B

$B3$B$K<($9!%(B $B:G$b7k2L$,NI$+$C$?$N$O!V(Bvolleyball$B!W$GA4FCD'NL$rMxMQ$7$?$H$-$G!$J?6QE,9gN($O(B$0.98$$B$H$J$C$?!%(B $B$^$?!$(BMAP$B$G$b(B$0.68$$B$H$$$&?tCM$r;D$;$F$*$j!$(B $BK\

$B?^(B 3: =75mm $B%i%s%-%s%08!:w$NJ?6QE,9gN((B(AP)$B$H$=$NJ?6QCM(B(MAP)
\includegraphics[clip,width=1.00\hsize]{eps/similarity_ranking_result.eps}

4.3 $B%/%i%9%?%j%s%08!:w(B

4.3.1 $B

$BF10l%?%0$NF02h$r%/%i%9%?%j%s%0$7!$3F%0%k!<%W$N(BF$BCM(B(F-measure)$B$r5a$a$k!%(B F$BCM$H$O!$E,9gN($H:F8=N($ND4OBJ?6Q$G$"$j!$(B

  $\textstyle F = \frac{2 \cdot P \cdot R}{P \raisebox{0zw}{+} R}$   (2)
  $\textstyle \hspace{0mm} {\scriptstyle P:\ } \mbox{\scriptsize $BE,9gN((B\ \ \ } {\scriptstyle R:\ } \mbox{\scriptsize $B:F8=N((B}$    
       

$B$N<0$GI=$5$l$k!%(B $BK\8&5f$G$O!$(BF$BCM$N:G$bBg$-$$%0%k!<%W$r@52rF02h%0%k!<%W$H$7!$(B $B$=$N(BF$BCM$rHf3S$9$k$3$H$K$h$C$F!$7k2L$NI>2A$r9T$J$&!%(B $Bl9g$NN`;wEY$r4p$K!$(B $BogCM$r(B$1.000$$B$+$i(B$0.500$$B$^$G(B$0.025$$B9o$_$GJQ2=$5$;$F9T$J$C$?!%(B

4.3.2 $B

$B:G$b7k2L$NNI$+$C$?!$%0%k!<%W4V$NN`;wEY;;=P$K72J?6QK!$rMQ$$$?>l9g$N7k2L$H!$(B $BBP>]$NA4F02h$r0lEY$KI=<($7$?>l9g(B($BA4I=<((B)$B$N(BF$BCM$r?^(B4$B$K<($9!%(B $B7k2L$,:GBg$H$J$C$?$N$O!V(Bvolleyball$B!W$K$*$$$FogCM$,(B$0.725$$B$N$H$-$G!$(B F$BCM$O(B$0.95$$B$H$J$C$?!%(B $BA4I=<($N>l9g$N(BF$BCM$O(B$0.33$$B$G$"$j!$%/%i%9%?%j%s%08!:w$r9T$J$&$3$H$K$h$j!$(B $BN`;wF02h$rM-8zE*$KI=<($G$-$?$3$H$,8+$F$H$l$k!%(B

$B?^(B 4: =75mm $B%/%i%9%?%j%s%08!:w$N3FogCM$G$N@52rF02h%0%k!<%W$N(BF$BCM$HA4I=<($7$?>l9g$N(BF$BCM(B
\includegraphics[clip,width=1.00\hsize]{eps/hierarchical_clustering_result.eps}

5 $B9M;!(B

$B!V(Bsoccer$B!W$H!V(Bvolleyball$B!W$N7k2L$,NI$+$C$?$N$O!$(B $B$I$N@52rF02h$b%3!<%H$N?'$,;wDL$C$F$$$?$?$a$H9M$($i$l$k!%(B $B0lJ}$G!$!V(Btennis$B!W$G$O;n9g$K$h$C$F%3!<%H$N?'$,A4$/0[$J$j!$(B $B?'FCD'$h$j$b%*%W%F%#%+%k%U%m!<$NJ}$,NI$$@:EY$r;D$7$?!%(B $B$3$N$h$&$K!$!V(Bsports$B!W$H$$$&F10l%+%F%4%jFb$K$*$$$F$b=EMW$JFCD'NL$O0l0U$K7hDj$G$-$:!$(B $B$I$N$h$&$JFCD'NL$r$I$N$h$&$KMxMQ$9$k$+$OFq$7$$LdBj$G$"$k!%(B

6 $B$^$H$a(B

$BK\8&5f$G$O!$(BEMD $B$rMQ$$$?N`;w(BWeb$BF02h$N8!:w2Ar7o$K$h$C$F$O!$$I$A$i$NJ}K!$bHs>o$KM-8z$G$"$k$3$H$,<($5$l$?!%(B $B:#8e$O!$?7$?$JFCD'NL$rDI2C$7$F$$$/$H6&$K!$(B $B%-!<%U%l!<%`$NCj=PJ}K!$d%/%i%9%?%j%s%02A2A$b9T$J$C$F$$$-$?$$9M$($G$"$k!%(B

$BJ88%L\O?(B

1
TRECVID, http://www-nlpir.nist.gov/projects/trecvid/

2
YouTube, http://www.youtube.com/

3
Rubner, Y., Tomasi, C. and Guibas, L.: The Earth Mover's Distance as a Metric for Image Retrieval, IJCV, Vol. 40, No. 2, pp. 99-121 (2000).

4
Peng, Y. and Ngo, C.: EMD-Based Video Clip Retrieval by Many-to-Many Matching, in Proc. of CIVR, LNCS 3568, pp. 71-81 (2005).

5
Lucas, B. and Kanade, T.: An Iterative Image Registration Technique with an Application to Stereo Vision, in Proc. of IJCAI, pp. 674-679 (1981).

6
Jain, A., Murty, M. and Flynn, P.: Data Clustering: A Review, ACM Computing Surveys, Vol. 31, No. 3, pp. 264-323 (1999).