Beyond sliding windows

CV

授業で他人が紹介した論文。巧妙で、さすがBest paperの貫禄。
コア部分(式変形)がなかなか簡潔に説明できない。。
２、３の基本事項。

識別器

機械学習界隈では"識別器"を良く使う。識別器は多くの場合、入力が「そうであるか、ないか」を識別するために使われ、そのような識別器は例えばSVMのような手法で大量の学習データから作り出される。

例えば大量の猫画像を元に"猫識別器"を作ったのならば、その"猫識別器"は、ある画像が猫であるか、そうでないかを出力することが出来る。

bag of visual words(bovw)

識別器を作る方法として、論文のsection3で使用しているのはbovwと呼ばれる手法。
bovwは、画像を何らかの手法でヒストグラム(= 1次元の波形)に変換し、識別するために用いる。
イメージとしては、「無料」だとか「出会い」といったキーワードが入ったメールをspamと判定し、そうでないものをspamでないと判定することに近い。単語ごとにヒストグラムを考えることができるように、画像のキーポイントを適当な種類にまで圧縮し(これにはベクトル量子化を用いる)、そのヒストグラムを取り、学習させる。
非常に重要なのは3.1に述べられている式変形により、ある領域中のdecision functionの上限(quality bound)は一定時間で計算できる点。この変形が可能であるという着眼。

sliding window

画像が猫かどうかだけを識別できても、画像の"どこ"に猫がいるのかを決定することはできない。
単純な解決としてsliding windowがある。要するに、画像を任意の矩形に分割して、そのすべての部分画像について識別を行えば良い。これはn×nの画像ならばO(n^4)クラスの問題となる(ので、通常は手を抜く必要が有る)。
本研究は、上記の変形によってこれをO(n^2)にまでちぢめた。