Thursday, May 20, 2010

如何解電腦視覺中的研究題目? 前言



如何解電腦視覺中的研究題目? 前言
(How to solve problems in computer vision?)

Jia-Bin Huang 
jbhuang0604@gmail.com

Latest update: May 20, 2010

The Feynman Problem-Solving Algorithm:
             (1) Write down the problem
             (2) Think very hard
             (3) Write down the answer                                                                                                   
                                                        -Richard Feynman

在撰寫如何找研究題目(How to come up with new research ideas?)系列文章的同時,我個人認為還有另一個重要的過程是研究過程中所不可或缺的,那就是如何解題(How to solve problems?)。對問題的觀察和思考而提出抽象的新想法對許多人(尤其是想像力豐富的學生)也許已不是難事,但怎麼經由科學的方法分析及描述問題,統計與機率的方法來處理資料的不確定性,和工程的方法實現有效率的解法,仍然不曉得從何著手。以至於研究作品很容易就陷入別人所定義的問題框架下。

這種抽象的想法(ideas)和實際的問題解決(problem-solving)之間的差距常常是研究生與指導教授之間的溝通問題所在。舉例來說,學生常覺得指導教授們只會用抽象且零散的思考來回應(i.e., 嘴砲),對於他們手上問題的解決沒有幫助。另一方面教授可能對於學生埋首於實現技巧而忽略問題本質的現象感到憂心。而這兩者其實是互補的,彼此缺一不可的,正如MIT的格言:

Mens et Manus (Mind and Hand) - MIT's motto

在前頭如何找研究題目(How to come up with new research ideas?)中著墨的是Mens (Mind),而這系列如何解研究題目?(How to solve research problems?)則強調Manus (Hand) 的重要。

在前言中介紹的是電腦視覺的基本觀念,接下來會跟著費曼的解題演算法來達成三步解題的過程概略簡介,在之後的文章會做藉由實例做詳盡的介紹。



電腦視覺的三個層次

David Marr,電腦視覺研究的先驅者之一,對於描述電腦視覺系統提出了三種不同的層次:
1. 計算層級 (Computational Level)
電腦視覺系統要做甚麼(What)?為什麼要做這些事情(Why)?

2. 表示與演算法層級 (Representation and algorithm level)
輸入輸出和中間的影像資訊如何表示(How to represent)? 以及如何處理這些表式來解決一個問題 (Which algorithms)?

3. 實現層級 (Implementation level)
如何實現? (How is the system physically realized.)

儘管這已是將近三十年前的描述,在處理現代的電腦視覺問題仍然通用,首先要了解要做甚麼問題以及其動機(i.e., application-oriented)。接著定義輸入輸出的表示方式(representation),然後設計有效的方法去求得想得知的未知數(algorithm)。最後再利用程式或是硬體(software/hardware)來實現這個功能。



電腦視覺研究中有那些問題?

電腦視覺處理的是視覺資訊(e.g., image, videos),並且利用這些資訊經由處理來得到我們想知道的訊息。依照取得的訊息(output)層級來分類,可以分為Low-levelMid-level、以及High-level vision三類:

輸入:Visual information (e.g., image or video)

=====Low-level vision=====

輸出:label of every pixel
範例問題                                            Label表示
Depth estimation                       Depth from the viewer
Figure / ground estimation        Foreground or background
Edge detection                         Edge or non-edge
Segmentation                           Region membership
Motion (optical flow)                  Motion vector
Intrinsic image                          Reflectance
Restoration                        High-resolution, clear/clean image
(denoising,  emosaicking, 
deblurring, inpainting, 
contrast enhancement, 
dehazing, super-resolution)


=====Mid-level vision=====

輸出:representation of an image
範例問題
Shape reconstruction
Human/head pose estimation
Hand gesture representation
Face representation (Snakes / Active shape models / Active appearance models)
Texture representation and synthesis
Image representation (Bag-of-features / Spatial pyramid, i.e., coding and pooling of low-level features)

=====High-level vision=====

輸出:Label of a window or an image
範例問題:
Object detection / localization
Object recognition
Optical character recognition
Hand-written digit recognition
Event recognition
Scene understanding



電腦視覺與電腦圖學之間的關係為何?

從上面三層電腦視覺的問題我們可以把所有問題都看成是:經由觀察到的影像資訊(image, video) input X,去求得我們想要的訊息 output Y。也就是在電腦視覺中我們關心的是 P(Y|X),而電腦圖學則關心相反的事情:P(X|Y)

舉最近很紅的Natal Project為例,電腦視覺的問題是如何從影像資訊(image + depth sensor)來得到使用者的姿態(Pose estimation),而電腦圖學則將以知的(或是估計得來的)姿態表示來產生相對應的影像(Animation)


另一個實際的例子是Google Earth中的3D城市,這裡包含了從影像推估真實世界中的3D模型(電腦視覺-3D reconstruction),以及如何用此3D模型合成正確的影像(電腦圖學-rendering)





如何解題?

接下來要介紹的便是如何解決電腦視覺中的問題?Richard Feynman對於解題提出了一個很有趣的但是很有效的三步解題演算法 (The Feynman Problem-Solving Algorithm)

第一步:寫下問題 (Write down the problem)
第二步:想破頭 (Think very hard)
第三步:寫下解答 (Write down the answer)

這個解題演算法看似trival,但是仔細思考後發現我們解題的過程中怎麼也脫離不了這三個步驟,接下來便會依照這三個步驟來分析並解釋如何解決電腦視覺中的研究題目。



(1) Write down the problem (Scientific)

第一步,也是解題過程中最困難的一步,寫下問題。怎麼樣將題目寫下來呢?這部分通常都會採用科學(Scientific)的方法。將想要求得的資訊與觀察到的影像之間的關係用數學式來表示 (i.e., forward model)。其中必須要考量到的可能有
a. Image formation process
b. Physics of light and reflectance
c. Geometry properties and constraints
d. Simplifying assumptions
等等因素。

先舉個最簡單的例子來說明如何寫下一個問題:去除影像中的雜訊(image denoising)

要寫下這個問題,便需要假設我們觀察到的影像 y 是由乾淨無雜訊的影像 x 加上雜訊n (additive model),所以我們便可以寫下輸入與輸出之間的關係式為

y = x + n

上述式子便構成了最陽春的Inverse problem

有了這個式子(i.e., forward model),便知道Image denoising這個問題即是如何從y來推估x是甚麼。然而到這個階段第一步驟還沒完成。我們還必須給定明確的定義說明甚麼是好的x?也就是運用我們對於問題本身的了解加上prior來對於問題進行規範(constraint),以解決Inverse problem (否則有無限多組解)

Image denoising這個問題中常用的目標函數(objective function)便是

f(x) = 0.5*| y - x |^2 + Pr(x)

Pr(x)便是我們對於影像xPrior / regularization

到這裡我們便可以將Image denoising的問題用數學的語言描述成:找到一個x可以將f(x)最小化。



(2) Think very hard (Statistical / Probabilistic)

完成了第一步驟:寫下問題之後,接下來便是要思考如何解決該問題,在電腦視覺中我們取得的資料往往是noisy的甚或是corrupted的,加上真實世界中的種種不確定性,使得我們常常必須要以ProbabilisticStatistical的方法來處理電腦視覺中的問題。

藉由一些觀察(observation)來預測一些未知量(unknown parameter, i.e., labels),這樣的問題屬於Estimation Theory的研究範圍。在這邊我僅介紹電腦視覺中被廣泛運用的貝式模型與估測(Bayesian modeling and inference),如Maximum Likelihood (ML)Maximum a Posteriori (MAP)、和Minimum Mean Squared Error estimation (MMSE)等等。還有在沒有辦法得到close-form解法時所使用的一些逼近(Approaximation)方法,如Monte Carlo Methods, Variational methods, (loopy) belief propagation等等。


(3) Write down the answer (Engineering)

完成第二步驟之後,若沒有經過工程方法來得到一個有效並且有效率的實現方法的話,那麼問題還沒有真的解決。我們在第一步時有了問題的定義(forward model),以及第二步中找到了解決問題的工具(Inference algorithm to invert the image formation process),在第三步驟便是用程式語言(或硬體)有效率地將其實踐並做三個層次的測試。

a. Synthetic experiments

自己產生許多無雜訊的合成的影像,這個層次的測試目的在測試實現程式的正確性。

b. Noise or abbreviation from the model

在這個階段,試著將合成的影像加上一定程度的雜訊。若在第一步時做了許多問題的假設,在這個階段可以看看你的方法在假設不成立時發生甚麼事情?這個階段測試方法對於Noise或是Assumption敏感的程度。

c. Real-World Images

電腦視覺是應用的學門,所以測試一個方法的最後一個階段即是將他應用在真實世界中。40年前我們只有一張Lena,一張影像同時是訓練影像也是測試影像。隨著照相機的普及到現在Flickr上成上百萬上千萬的照片,因此若希望提出的方法具有實際的效用,最好的方法便是將你的方法在真實世界的照片(或是自己的照片)上做測試。

No comments :

Post a Comment