Efficient visual search of videos cast as text retrieval

Efficient visual search of videos cast as text retrieval

Josef Sivic and Andrew Zisserman

===================================================

這篇paper主要的目的是能用運像 text search 的技術來作 image search
實驗的部分是找出電影中含有query object 的 keyframes，當然要在real-time完成

一開始看的時候就想說怎麼跟「Video Google」這篇這麼像，後來查了才知道原來作者一樣

主要的步驟可以分為以下幾個：
1. 找出 viewpoint invariant descriptor
2. 利用SA及MS找出重要的橢圓形region
3. 用SIFT去找出橢圓形的descriptor
4. 用SIFT descriptor建立visual word 再用K-means 去建 visual vocabulary
5. visual indexing by text retrieval
以下將分別敘述

1. 找出 viewpoint invariant descriptor
viewpoint invariant 是想找出不會因為拍攝角度變化而改變的一些feature
所以就假設用不同視角去找，取出不變的那些feature
這部分在paper是引用其他paper的技術，沒有詳述

2. 利用SA及MS找出重要的橢圓形region
利用Harris interest point 來找出Shape Adapted (SA) region
以及找出反差很大的區域 Maximally Stable (MS) region
前者主要會出現在細節變化很多的部分，後者則是找出一個region 跟週圍顏色反差很大之處
用這兩個方法去標出所要的橢園region

3. 用SIFT去找出橢圓形的descriptor
在所有的橢圓都找出 SIFT descriptor
(SIFT 的取法在另一篇有提到)
paper裡也提到這裡的SIFT沒用到顏色

4. 用SIFT descriptor建立visual word 再用K-means 去建 visual vocabulary
以SIFTdescriptor 當feature把每個橢圓當成visual word
就像text search 的 word 一樣
因為要把類似的 visual word 分為同一群，否則 visual word 不會像 text word 一樣會有相同
所以要用K-means 去建 visual volcabulary

5. visual indexing by text retrieval
有了word 跟 volcabulary 就可以像text search 一樣
利用 stop word list 及 tf-idf 等方法來ranking
這裡的spatial consistency 就是看visual word 彼此的spatial 距離

另外video 有 temporal information 所以可以參考neighbor frame  去過濾一些比較不確定的

實驗的部分
作者用了三部影片，每1秒取一個keyframe
然後在realtime找出指定object出現的keyframes
這篇paper有著重在time efficiency
retrieval time baseline就是把每個frame  用linear search 去比對
作者提出的方法是像text search 有作indexing (tf-idf system)
另外也舉了一些比較麻煩的case，像是平滑的地方取不出feature
最後合併了很多 text search 的ranking方法測試它們的效果

最後在結論裡有提到
像這篇所用的vector-quantizing  方法跟nearest neighbor matching 的相比其實差不多
但 nearest neighbor matching 是很花時間的(目前不存在有效的演算法)
也提到可以用像 hierarchical tree 來 indexing 增加效率
spatial consistency re-ranking 很重要
另外作者提出說text retrieval 在 web search上可以用 web page 本身的內容來決定它的預設分數，image可能也可以這樣做，靠著 visual word 來判斷這是否是一個很有意義的frame

=======================================

優點：
1. 能夠串連已成熟的技術(text retrieval)來運用，直接就跨出很大一步
2. real-time 所以很強調 time efficiency ，所以才要用text retrieval idea
3. 作者提到的一些觀點很有趣，像是結論裡所說的判斷image本身的meaning，以及把很平淡的東西當作object來測試

缺點：
1. 只利用3部電影當data，而且search的時候好像侷限在同一部影片，這個assumption太強
2. 好像是為了運用temporal relation 所以才每秒取一張keyframe，而不是用適合的shot detection，但這樣pre-processing的運算量就很大。但如果只取shot frame 就要再另外找出一個frame 來作 temporal reference。這個問題是tradeoff，所以也不能僅僅看成是缺點。
3. 最後用了很多不同ranking方法(tf-idf, Bhatta, KL, L2, chi-square, ....)，沒有分析出它們的好壞在哪裡