第七章 紋理描述與分類.

Presentation on theme: "第七章 紋理描述與分類."— Presentation transcript:

1 第七章 紋理描述與分類

2 內容 7.1 前言 7.2 鍊碼 7.3 多邊形估計 7.4 對稱軸偵測 7.5 細化 7.6 同現矩陣 7.7 支持向量式的紋理分類
7.8 Adaboost分類法 7.3.1 PA-# 7.3.2 PA-ε

3 7.1 前言 描述一張影像內物體的形狀和其紋理。影像的形狀和紋理描述在影像資料庫的檢索和圖形識別上都直接的影響其方法的適用性。

4 7.2 鍊碼 鍊碼(Chain Codes)用來描述影像中物體的外圍。 常用的方位有四方位和八方位。 圖7.2.1 四方位鍊碼
圖7.2.2 八方位鍊碼

5 差分鍊碼上的第 i 個碼為原先鍊碼上之第 i 個碼減去第 (i-1) 個碼。 形狀數(Shape Number)
將差分鍊碼看成環型，針對每一個碼將環型鍊碼剪開，比較每一個鍊碼的大小，最小的鍊碼謂之。 一個例子： 　 八方位鍊碼的字串為 　 差分鍊碼為 形狀數為 圖 一個鍊碼的例子

6 7.3. 多邊形估計 PA-# 問題定義 只允許用最少量的連續線段來表示該物體的外緣，但必需滿足事先設定的誤差。這個多邊形估計的問題叫PA-#問題。 誤差量度 區域平方累積誤差(Local Integral Square Error)，簡稱LISE。 LISE也可以看成所有， ，到直線 的距離平方和。

7 假設在二維空間上有n個點形成的物體外緣，我們以集合{Pk = (xk , yk), k = 1, 2, 3,…, n} 代表之。令LISE為

8 (a)  = 10，＃=27 (b)  = 20，＃=19 圖 PA-#的實作結果

9 7.3.2 PA-ε 問題定義 在事先設定的線段數量下，找出一個多邊形估計以便達到最小誤差的要求。這個問題叫PA-問題。 實驗結果
圖 PA-的實作結果 (a) ＃=6 ， = 650.6 (b) ＃=11，  = 70

10 7.4 對稱軸偵測 梯度方向柱狀圖(Gradient Orientation Histogram) 利用得到的 和 二個梯度量，合成大小為
利用得到的　　和　　二個梯度量，合成大小為 夾角為 針對每一個　，它代表物體表面的走勢。將　　 分割成 若干份，找到 　對應的角度 x 。 ，

11 圖7.4.1所示物體在 α 角度和 β 角度有二個對稱軸。
圖7.4.1 一物體的二個對稱軸 對稱軸偵測 圖7.4.1所示物體在 α 角度和 β 角度有二個對稱軸。 針對每一個x，求出其得到的S(x)。 若將　　 分成1024份，可得S(0)、S(1)、…和S(1023) 共1024個數，從這1024個分數中，挑出最高的二個分數，其對應的角度就是我們要的 α 和 β 。 定義一得分函數 h(x)以 為週期循環

12 圖7.4.3 梯度方向柱狀圖 圖7.4.2 輸入的影像 圖7.4.4 所得對稱軸

13 7.5 細化 細化(Thinning):找物體的骨架(Skeleton)。 骨架的定義
物體 O 的外圍輪廓為 B 。在O內，若能找到一個像素 t 且在 B上能找到二個邊點，e1 和 e2，使得 d(t,e1) = d(t,e2)，則 t 就可為 O 的骨架中之一個元素。這裡距離函數 d(t,ei)，1i2，表示像素 t 和邊點 ei 的距離。 圖7.5.2 輸入之影像 圖7.5.3 細化後的結果

14 當N(Z5)=0或1時，Z5可能為孤立點或最外圍的端點，Z5不必改為0。以東南方的方向進行細化：
考慮黑白影像的O ，以圖7.5.1為例 N(Z5) :Z5鄰近非零像素個數 T(Z5):灰階由0(1)變到1(0)的個數 N(Z5)=5 T(Z5)=2 (1) 2  N(Z5)  6 (2) T(Z5) = 1 (3) Z2Z6Z8 = 0 (4) Z2Z4Z6 = 0 (7.5.1) 當N(Z5)=0或1時，Z5可能為孤立點或最外圍的端點，Z5不必改為0。以東南方的方向進行細化： (3) Z4Z6Z8 = 0 (4) Z2Z4Z8 = 0 (7.5.2) 以東南方的方向進行細化： 1 Z7 Z8 Z9 Z4 Z5 Z6 Z1 Z2 Z3 圖 ×3子影像 利用(7.5.1)式和(7.5.2)式在物體O的外圍不斷地進行細化工作，直到無法再細化為止。

15 試問上述小影像中間的兩個像素經細化後可否被移除？
範例1：給定如下所示的小影像 試問上述小影像中間的兩個像素經細化後可否被移除？ 解答：先檢查下面的3×3子影像 1 1

16 由於 ，3×3子影像中的 不可改為 。 我們檢查下面的3×3子影像 1 由於滿足移除的四個條件，所以上述的3×3子影像中的 可改為 。 解答完畢

17 7.6 同現矩陣 同現矩陣(Co-occurrence Matrix):表示紋理的方法。
Co矩陣可表示為Co[i, j, d, ]，i 和 j 代表灰階值；d代表 i 和 j 的距離而 表示 i 到 j 的角度。 圖7.6.1 輸入的影像 d=1和=0時的Co矩陣 d=1和=90時的Co矩陣 Co矩陣可描述出影像中有等距離且呈某種角度走向的規則紋理。

18 7.7 支持向量式的紋理分類 利用支持向量(Support Vector Machine, SVM)的方法來進行紋理分類(Texture Classification)。 給二張訓練用紋理影像如圖7.7.1(a)和圖7.7.1(b)所示。 (a) A類 (b)B類 圖7.7.1 訓綀用的二類影像

19 首先在訓綀用的二張影像上，將其分割成L份，假設每份的訓綀 小模組爲一張
的子影像，則可先將其轉換成 。 圖7.7.2 抽樣

20 。 接著，我們將這些為數L個的小模組代入下列的二次數學規劃的問題(Quadratic Programming Problem)上以解得係數
滿足 這些解出的正係數所對應的小模組向量集也稱作Support Vectors。 令 ，若 f(x)>0，則 x 代表+1那類 否則 x 代表-1那類。這裡 x 為待測小模組。

21 圖7.7.3 分類後的結果 中值法後的分類結果 (b) 二類的分割結果 圖7.7.4 後處理的結果

22 Adaboost分類法是一種機器學習法，這個分類法常與其他的機器學習法混合著使用，有時候也稱作meta分類法。以下我們以血管識別為例。
首先，我們輸入 個訓練樣本 ，令 代表第 個訓練樣本的特徵，此特徵可以是一個 維的向量， 的大小取決於我們在像素點上取了多少種特性，以 表示之。若 為血管上的特徵，則令 ；反之，則令 。 圖 個訓練樣本 7.8 Adaboost分類法

23 在Adaboost分類法中，我們首先設定疊代次數。令疊代數為 K ，每經過一次疊代後，我們將會得到一個弱分類器(Weak Classifier)，符號定義為 h )。完成 K 次疊代後，即可將此 K 個弱分類器組成一個強分類器(Strong Classifier，符號定義為 H )，並透過所得到的強分類器來判斷輸入之像素是否為一血管上的像素。 令 為第 k， 1≦k≦K，次疊代中第 i 個訓練樣本的權重。 首先我們初始化 m 個訓練樣本 的權重分別為 (7.8.2)

24 在 m 個向量 中，令 為分別從每個向量取出第 j 個元素之集合，即 ，其中 。把 中的元素進行排序後，可得到排序後的結果 。
經過 n 次的排序後，我們可得到 ，如圖7.8.2所示： 接下來利用下述的門檻值進行粗略的分類 圖7.8.2 排序後的向量 (7.8.3) 排序為 ...

25 把門檻值與 中的元素進行比較，可以得到比較後的結果
其中 ， 上式中，我們可以得知當 小於等於 ，就認定 是血管上 之特徵並定義 ；反之，則 並非為血管上之特徵並定 義 。另外，由式(7.8.3)可以得知，每一個 可以產 生出 個門檻值。因此，針對 而言，我們可以得到 個比較後的結果，即為 。 (7.8.4)

26 得到 m-1 個結果後，分別計算出每個結果的錯誤率：
其中 而後，透過下式得知針對每個特徵向量第 j 個元素之 最佳門檻值 及其所對應之錯誤率 ： 其中 。 (7.8.5) (7.8.6)

27 求得 個最佳門檻值後，我們將可以求得此次疊代的弱分類器 及其對應的錯誤率 ：
其中 。 而後每一次的疊代會透過弱分類器的錯誤率來更新權重： 其中 ， ，而 為所有的權重 和(即 )。 (7.8.7) (7.8.8)

28 當完成 K 次疊代後，我們將可得到 K 個弱分類器。最後根據求得的弱分類器進行權重重組以得到一個強分類器，其公式如下：
Adaboost分類法的演算流程圖表示於圖7.8.3中。 (7.8.9)

29 圖7.8.3 Adaboost流程圖

30 (a) (b) 圖7.8.4 兩張待測影像 (a) (b) 圖7.8.5 實驗結果