Thursday, April 22, 2010

如何找研究題目(二):結合兩種以上不同的主題 - 結合不同的方法

如何找研究題目?
(How to come up with new research ideas?)

Jia-Bin Huang 
jbhuang0604@gmail.com
                                                                              
Latest update: April 3rd, 2010


To steal ideas from one person is plagiarism. To steal from many is research. - Wilson Mizner


二、結合兩種以上不同的主題     neXt = X+Y


 這一類應該算是最為廣泛運用的找新問題的方法,也因為如此,這一類方法常會與其他五類有重疊,在這裡我所討論的"結合兩種以上不同的主題"會比較狹義一些,免得其他類別沒東西可寫 XD
  結合兩種東西時,我們手上的X, Y可以是A. 某種方法,B. 某類問題,或是C. 某個領域,上頭說的"狹義"指得是方法和方法或是問題與問題的結合,而不討論某方法應用在某問題之類的創新。接下來會由這三個層面分別舉實例來討論。
  運用這種方法時有個兩個中心思想:
1. X, Y的性質越不相似,則所產生的效果就越具有影響力。
2. X, Y的結合必須是因為對於待解決的問題本質上有透徹的了解,也就是找出了問題的根本核心。

A.  X,Y為方法時

  這類研究題目在於尋找兩種已知的工具結合的可能,進而產生新的工具來解決問題,有時候將不起眼的老掉牙的方法經過恰當的結合可以產生相當有效的結果。

EX 1. Viola-Jones object detection framework

  Viola-Jones object detection framework [1]是第一個即時的物件偵測架構,最早相當成功地被應用在影像中的人臉偵測。傳統上的人臉偵測,需要使用Sliding window來掃描整張影像的所有區域,而每一個window中又必須計算一組特徵(feature)來表示,用分類器(Classifier)一一去檢驗每個window是否有人臉非常沒有效率。
  為什麼這個方法會成功?我們大致可以歸納為三個因素

1. Haar-like features的快速計算
    當時描述物件相當有效的特徵為Haar-like features [2],但是在一個24x24的小小window裡頭,便有45,396個可能的特徵,雖然說有Integral Images的幫助可以使得每一個維度的計算複雜度為O(1) (constant time),計算上萬次仍然沒有效率。

2. Adaptive Boosting的理論逐漸成熟
    1997AdaBoosting [3] 的提出使得一群弱分類器(weak classifier)的線性組合可以形成準確的分類結果。

3. 對於人臉偵測這個問題本質上的了解 (關鍵因素!)
    在一般的自然影像裡,含有人臉的window僅佔影像中所有可能的window的極少數(甚至沒有),所以在檢驗每個window是否有人臉時,決大多數的window可以容易就先刪選掉。這使得作者採用決策樹(Decision Tree)中的Cascade架構,讓大多數的window可以在前幾個階段就被篩選掉。
總的來說,Viola-Jones object detection frameworkIntegral Images (simple feature) + AdaBoost Cascade Architecture,是不是完全可以從論文的標題就看出來了呢?Rapid Object Detection using "a Boosted Cascade of Simple Features"

用這個例子回頭來驗證一下開頭說的兩個中心思想:

1. 不相似性:Integral Images (1984年被提出)AdaBoost (1997年被提出Cascade 架構 (年代久遠不可考)2000年的時候都是已知的工具,一個為計算Haar-like features的方法,一個為結合許多weak classifiersmeta-algorithm,另一個則是決策樹中的簡單架構,這三種方法確實相當不一樣。

2. 問題核心的了解:也就是上頭第三個因素--人臉的window通常佔影像中的所有window極少部分,這篇論文就是根據這個看似直覺的觀察才將上面三個方法結合起來,產生了極為成功的方法,能夠快速有效率地偵測影像中的人臉。


EX 2. SIFT Flow

  在 如何找研究題目 ():尋找不一樣的維度 中介紹Scene Alignment曾經提到SIFT Flow [1],當時是從Alignment的角度來切入,現在則將SIFT Flow看成是SIFTOptical Flow的結合。 
  處理Scene Alignment的時候,兩張影像差異包括不同的視角(Perspective)、潛在的遮蔽(Occlusion)、多個物體(Multiple objects, no global transform)、雜亂的背景干擾(Background clutter)還有即使是同類主題或物件裡頭Intra-class的差異性。這些差異使得找尋影像之間的dense correspondence非常困難。我們的確可以使用Optical Flow來計算任意兩張影像的Pixel Correspondence,但是計算出來的場(Field)並不具有特別的意義。我們必須先了解到計算Optical Flow時的一個基本假設為兩張影像在時間上是非常相近的(dense sampling in time),但對於任意的影像,我們要怎麼做到dense sampling呢?直覺的想法便是蒐集一大堆的影像資料庫,使得任意取一張影像,該影像都可以在此資料庫裡頭找到很接近的相鄰(dense sampling in world images)。滿足了這個假設,SIFT Flow所產生的場即有了意義,所以SIFT flowOptical flow的類比是

Dense sampling in time : optical flow :: dense sampling in world images : SIFT flow

  場景跟場景之間的Alignment有甚麼用處呢?作者在[1]中提出了三個可能應用(有興趣可以直接看底下的連結)
1) Large database-driven approach for image processing and understanding [2]
2) Motion Hallucination
3) Motion Synthesis via Moving Objects Transfer


在這個例子我們再驗證一下兩個中心思想
1. 不相似性:Optical flow 計算兩張時間上相鄰影像之間的Pixel correspondenceSIFT則是一種偵測和描述影像區域性特徵的方法,兩者各自的應用都非常廣,但直到2008年才被做有效的結合
2. 問題的本質:將Alignment/RegistrationObject level推廣到Scene Level


EX 3. Visual Tracking with Online Multiple Instance Boosting

  Visual Tracking這個問題的一般定義是,在一段影片中,給定任意物件(e.g, a face, a toy)一個初始的位置(A bounding box),然後在接下來影片穩定地追蹤該物件,這個問題常常會遇到許多困難,比如光線產生變化、相似物件干擾、嚴重遮蔽等等問題 [1]
  拜物件偵測(Object detection)[2]的進步所賜,Tracking的方法開始加入detector的幫忙 [3-4],其中可以online learning來動態地來學習新環境的Online boosting [4] 方法相當受歡迎。然而除了初始位置是準確確定的之外,之後的位置都是由Tracking演算法所預測,也因此每當有一點點小誤差出現時,錯誤的訓練資料會使得detector失準,慢慢地誤差會開始累積而產生所謂的飄移現象(Drifting,白話一點就是追蹤不到了)。類似的問題在學習Object detector的時候也產生,因為即使使用人工來標是訓練資料仍然會有不準確的情況,於是就提出了使用Multiple Instance Learning來訓練Object detector [5],解決了資料不確定性的問題。
  於是在這篇作品裡,作者觀察到了Trackingonline learning會遇到的drifting問題(問題核心),於是結合了Online Boosting [4] Multiple Instance Boosting [5] 這兩個方法(online boosting + MIL boosting = Online MIL boosting for Tracking [6]),而提升了Tracking的效能。




[1] Object tracking: A surveyACM Computing Surveys 2006
[6] Visual Tracking with Online Multiple Instance BoostingCVPR 2009

1 comment :