10. Feature extraction

Introduction

         特徵萃取(Feature Extraction)是將有利於物件分類的特徵分割出來,然後再利用這些特徵來描述或是表示某一物件之形狀及顏色。

         特徵萃取的目的,主要是讓我們能夠利用這些特徵對物件種類進行判別。

Content

         特徵的種類繁多可分成全域特徵、局部特徵、及關聯性特徵三大類。

         在樣本識別上,常用的特徵包括:位置、幾何形狀、色彩、對比、成份、及表面紋路等。其中幾何形狀特徵的種類還包括:周長、面積、離心率(橢圓長短軸比)、縱橫比、真圓度(緊密度)、粗糙度、簽名、長短距離比,…等。

         灰階影像之色階特徵包括:最大灰階值、最小灰階值、平均灰階值、灰階值標準差等。

         對輸入模式的原始測量數據(信號)所進行的一組變換,以便在比原始信號為數較低的特徵空間對模式進行有效的描述或分類(見統計模式識別)

         特徵萃取可以用一級或多級變換實現,在多級的情況下,上一級的輸出就成為下一級的輸入。

         較低維的輸出信號可以是較高維輸入信號的某種線性或非線性組合,也可以僅僅是輸入信號的一個子集。

         在後一情況下,這種變換也叫做特徵選擇。根據識別系統的實際要求,通過特徵萃取可以從原始信號中得到為產生或表示模式所必需的關鍵特徵,例如可以從景物的原始灰度圖像中抽取出目標的輪廓和形狀,也可以抽取那些只對分類有效的鑑別特徵。

         通常原始信號所組成的測量空間具有很高的維數,如攝影機所獲取的灰度圖像,其維數可以達到256 X 256以上。直接用它進行分類一方面計算量很大,更重要的是不同的測量條件,如攝影機位置的微小移動、照明的強弱變化等,都可能使在測量空間中表示同一模式的向量發生極大的變化。

         因此在很多情況下直接在測量空間中進行分類有很大的困難。在實際問題中,原始數據經常包含一些多餘的或重複的信息,為了減少整個識別系統或取測量數據的費用和相應的計算工作量以及改善識別系統的性能,也有必要通過特徵萃取和選擇把模式變換到較低維數的特徵空間中去。可以認為特徵萃取式模式辨別的關鍵步驟。

Summary

         特徵萃取是計算機視覺和圖像處理中的一個概念。

 

         至今為止特徵沒有萬能和精確的定義。

 

         特徵萃取是圖象處理中的一個初級運算,也就是說它是對一個圖像進行的第一個運算處理。

 

         有時,假如特徵萃取需要許多的計算時間,而可以使用的時間有限制,一個高層次演算法可以用來控制特徵萃取階層,這樣僅圖像的部分被用來尋找特徵。

 

         由於許多計算機圖像演算法使用特徵萃取作為其初級計算步驟,因此有大量特徵萃取演算法被發展,其提取的特徵各種各樣,它們的計算複雜性和可重複性也非常不同。

 

 

特徵粹取(feature extraction)事實上乃特徵選取(feature selection的延伸,希望將資料群由高維度的空間中投影到低維度的空間,最大的不同在於挑選出的投影空間基底(base)可以由原本的特徵基底經過線性或非線性的運算組合而成。
假設我們有一組特徵W = {v1 , v2 , v3 , … . , vD},我們希望透過某種評估方式J(例如:錯誤率),找出一組最佳的集合S,使得J(S)≦J(T)。其中,T與S 中的元素均由vi 經由線性或非線性的運算組合而成,其中,i=1~D,S 與T 長度均為d,d<D。

在這裡,我們簡單將特徵粹取劃分成「包含類別資訊」和「不包含類別資訊」兩大類。包含類別資訊指的是我們已經知道哪些資料分別歸屬於哪一類;而不包含類別資訊的特徵粹取則適用於我們不知道手上的資料點分別該歸屬於哪一類,甚至
連該劃分成幾類都不知道的情況。

特徵粹取事實上乃特徵選取的延伸,希望將資料群由高維度的空間中投影到低維度的空間,其與特徵選取最大的不同在於挑選出的投影空間基底可以由原本的特徵基底經過線性或非線性的運算組合而成。假設我們將每一筆資料的各個特徵視為它的座標,那麼我們就可以將全部的資料視為一群分佈在高維度空間中的點,而每筆資料的特徵數目便可視為該筆資料的維度。主成分分析之主要目的是希望用較少的變數去解釋原來資料中的大部份變異,更期望能將我們手中許多相關性很高的變數轉化成彼此互相獨立的變數,能由其中選取較原始變數個數少,能解釋大部份資料中的變異的幾個新變數,也就是所謂的主成分。主成份分析所著重的在於如何「轉換」原始變項使之成為一些互相獨立的線性組合變數,而且經由線性組合而得的主成分仍保有原變數最多的資訊,其關鍵在「變異數」問題,利用求特徵值及特徵向量之方法,過濾出佔最大變異數的型態,此為最主要之型態。線性區別分析之特徵萃取目的在於找到一個轉換矩陣A,使得經轉換計算後的新資料矩陣具有最大的類組分離量(class separability)。通常類組分離的準則公式須用到組內分散矩陣(within-class scatter matrix)、組間分散矩陣(between-class scatter matrix)及混合分散矩陣(mixture scatter matrix)。 

因此在那麼
大維度的空間去training 是很沒有效率的事,這時我們就需要把資料降維。最常用的降維方式有兩種,分別是PCA 和LDA

以下簡介一下傳統PCA 跟LDA 各別的特性 :

PCA

擁有Euclidean space vector norm 最小的特性。簡單來說,就是當我們用PCA
把資料降維後,用傳統的vector norm 下來看,誤差會是最小的。

LDA

使用典型的統計方式來對資料做維度降低與分類,擁有降維後能將各群data 分開的特性,但是以vector norm 來看,誤差不保證是最小的。

當分類的資料包含分類資訊時,監督式的方法像是LDA,通常比非監督式的方法有用(像是PCA分類),所以如果要做資料壓縮,那麼PCA一定是最佳的選擇。如果是要做pattern classification,LDA就是比較好的選擇。

---影像特徵擷取---

這裡我們將針對「物體追蹤」(Object Tracking)的部分做簡單的介紹。物體追蹤是透過比對連續影像間物體的相似度來完成,其中的議題涵蓋要如何建立物體的特徵,相似程度的判別,還有如何在影像中快速尋找目標物。常用的數學工具有Kalman Filter、Condensation Algorithm、Dynamic Bayesian Network等。而物體交錯時產生的遮蔽現象,是追蹤過程最常見也最不易解決的問題

目前的追蹤方法大致可分為四類:

1.      區域式追蹤 (Region-Based Tracking)

2.      主動式輪廓追蹤(Active Contour-Based Tracking)

3.      特徵追蹤 (Feature-Based Tracking)

4.      模型追蹤 (Model-Based Tracking)

 不過要注意的是,此種分類方式只是大致的區分,並不是絕對的,而往往在一個追蹤系統中會同時包含數種不同的追蹤技術。


特徵追蹤(Feature-Based Tracking)

以物體特徵為基礎的追蹤方法,是萃取影像中形成目標物的各種成分,再將這些成分集合成較高階的特徵資訊,藉由比對連續影像間的特徵資訊來追蹤目標物。根據不同的特徵,可粗分為:整體性特徵(global feature-based),如重心、色彩、面積等;局部性特徵(local feature-based),如線段、頂點等;相依圖形特徵(dependence-graph-based),如特徵間的結構變化等。此外,像是Jane等人[\,利用紋路、顏色、邊界等資訊建立追蹤物體的特徵模型,以Kalman filter的技術進行追蹤。Comaniciu等人設計出平均值移動(Mean Shift)的追蹤技術,統計移動區域內的亮度值,依不同位置給予不同的亮度比重,組合成目標物的特徵模型,找出影像中和目標物模型最相像的區域,藉此達到追蹤的目的。一般而言,特徵追蹤方法可以利用運動特徵、局部特徵或相依的結構特徵來解決交錯的問題,但是前者穩定性不高,而後者則比較耗時費力。