Fast Similarity Search and Clustering of Video Sequences on the World-Wide-Web

Fast Similarity Search and Clustering of Video Sequences on the World-Wide-Web
Sen-ching S. Cheung, Member, IEEE, and Avideh Zakhor, Fellow, IEEE

Abstract -

• 這篇基本上是延續上一篇論文，上一篇提出的一個方法
  
• randomized technique called the video signature (ViSig) method for video similarity
  measurement.
• 拿 4 種方式比較，ViSig 比這四種好.
• PCA, Fastmap, Triangle-Inequality Pruning, and Haar wavelet
  
• 在這篇paper, 主要兩個重點
• 特徵提取的快速相似性搜索
• 以及clustering algorithm來確定類似集群
• 最後提到的方式是針對 local data 找出某個 threshold，在比較相似的圖.

Introduction-

• 他的目的也是想利用搜索引擎來找出類似視頻版權內容的法律 issue.
• 又提到（ ViSig ），兩幀之間部分類似的共同序列。 ViSig產生一個 簽名並以database儲存.並可以處裡序列時間大不相同的問題.
• 公式: ( 看來也是要分類進行)
  
• warping distance[3]–[5]
• Hausdorff distance [6]
• template matching[7]
• 他也拿以下公式比較，他的更優，複雜度更低
• 密度參數[ 8 ] -[ 1 0]
• 關鍵幀或中心點[ 6 ]
  
• 基於上一篇ViSig ，本文提出兩個重點
• A. Fast Similarity Search
• 針對大型DB的比對，Elaborate data structures 統稱為spatial access methods（ SAM ）有提出一些公式 [11]–[13].但對於高維度的空間資料並不方便.
• Principal Component Analysis (PCA)已被證明是最佳的近似Euclidean distance[ 15 ].
• Multidimensional dimension scaling (MDS) 可用在高維度相似搜尋並解決了非線性優化問題, 但過於複雜.
• Fastmap mapping 是一種低覆雜度的演算法，由Faloutsos and Lin [18].提出，使用heuristics algorithm 求歐幾里德的近似值. 產生 Fastmap mapping時，時間的覆雜性對於DataBase 的大小呈線性的關系.
• 
  
• 
  
• B. Similarity Clustering
  
• SectionII-A 討論如何做出一個簽名.
• SectionII-B 在 A 架構之下，如何快速搜尋.
• SectionII-C 對於他的公式建議.

Algorithms-

• SectionII A:
• 
  

Memo:

• PCM(Principle Component Analysis:主要成分分析法
• ICA(Independent Component Analysis):獨立成份分析法
• 上面兩種用意皆類似DCT，用意再捨棄變異小的變數，一樣是失真，屬於非高斯分布( nongaussian)實作方式常見於KLT(Karhunan-Loeve Transform)，相較於複雜度高於DCT.
• PCA - Principal Component Analysis with Missing Data
• http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/PCAMissingData.pdf
  

Questions:

• Fellow - 研究員?...是指 Avideh Zakhor 是IEEE的 Fellow , Cheung 是 IEEE Member? 很有名氣的意思嗎? 這樣算是 Avideh Zakhor 掛名嗎?
• 在Introduction 有提到受到兩個單位贊助，這個放Introduction?
• Air Force Office of Scientific Research (AFOSR)
• National Science Foundation (NSF).
•