形状与纹理描述

1、1第七章第七章形狀與紋理描述形狀與紋理描述2內容n7.1 前言n7.2 鍊碼n7.3 多邊形估計n7.4 對稱軸偵測n7.6 利用小波係數進行三角化n7.7 細化和Co矩陣描述法n7.9 作業n7.3.1 PA-#n7.3.2 PA-n7.7.1 細化n7.7.2 Co矩陣描述法n7.7.3 SVM式的紋理分類 37.1 前言n描述一張影像內物體的形狀和其紋理是很難的工作，影像的形狀和紋理描述在影像資料庫的檢索和圖形識別上都直接的影響其方法的適用性。 47.2 鍊碼n鍊碼(Chain codes)很適合用來描述影像中物體的外圍。 n常用的方位有四方位和八方位。 102310237465圖7.2

2、.1 四方位鍊碼 圖7.2.2 八方位鍊碼 5n差分鍊碼 差分鍊碼上的第 i 個碼為原先得到的鍊碼上之第 i 個碼減去第 (i-1) 個碼而得到。 n形狀數(Shape Number) 將差分鍊碼看成環型的鍊碼，針對每一個碼將環型鍊碼剪開，比較每一個鍊碼的大小，最小的鍊碼謂之。形狀數是唯一的。 1023S76566653122圖7.2.3 一個鍊碼的例子 n一個鍊碼的例子： 八方位鍊碼的字串為212120766665533 差分鍊碼為771716770007060 形狀數為000706077171677 67.3. 多邊形估計7.3.1 PA-#n問題定義 只允許用最少量的連續線段來表示該物體

3、的外緣，但必需滿足事先設定的誤差。這個多邊形估計的問題叫PA-#問題。n誤差量度 區域平方累積誤差(Local Integral Square Error)，簡稱LISE。 LISE也可以看成所有， ，到line 的距離平方和。11jki),(jiPP7假設在二維空間上有n個點形成的物體外緣，我們以集合Pk = (xk, yk), k = 1, 2, 3, n 代表之。令112),(jikjikijPPPdd上式中的距離量度就是LISE。8*Construct a graph such that the LISE of each edge (denoting the possible segm

4、ent) is less than the specified error bound. (see pp. 258)*For open object boundary, find the shortest path from the starting point to the ending point. The determined path is the constructed polygonal approximation.*For closed object boundary, for each point we find its own shortest path. Among the

5、se found shortest pathes, we find the minimal one as the solution. 9圖 7.3.1.2 PA-#的實作結果 (a) = 10，=27(b) = 20，=19107.3.2 PA-n問題定義 如何在事先設定的線段數量下，找出一個多邊形估計以便達到最小誤差的要求。這個問題叫PA-問題。n實驗結果圖 7.3.2.1PA-的實作結果 (a) =6 ， = 650.6 (b) =11， = 70117.4 對稱軸偵測n梯度方向柱狀圖(Gradient Orientation Histogram) 利用測邊時和二個梯度量。二個梯度量的合成

6、大小為二個梯度的夾角又可表示為 針對每一個，它代表物體表面的走勢。將 分割成若干份，找到對應的角度 i ，然後在柱狀圖中投下一票，即完成hi=hi+1的動作。影像上，每一個像素的皆在 h 陣列投票。 fxfy22)()(ffmyx ffxy arctan20， 2 , 012圖7.4.1 一物體的二個對稱軸 n對稱軸偵測 有一物體如圖7.4.1所示，這物體在 角度和 角度有二個對稱軸。 我們針對每一個x，求出其得到的S(x)。若將 分成1024份，這時，可得S(0)、S(1)、和S(1023) 共1024個分數，從這1024個分數中，挑出最高的二個分數，其對應的角度就是我們要的和。 0)()(

7、)(xhxhxS 20 x定義一得分函數)2()( nxhxh 0Nn h(x)以 為週期循環 22 , 013圖7.4.2 輸入的影像 圖7.4.3梯度方向柱狀圖 圖7.4.4所得對稱軸 147.6 利用小波係數進行三角化n小波轉換(以Haar為基底)步驟一：小波轉換步驟二：產生 EWC三角化小波係數EWC三角化的結果輸入地形影像 圖7.6.1 流程圖 給一個 22 影像如下：我們先對列做小波轉換，得再來對行做小波轉換，得 3579 1418235235279279 0216211248211248152)(wH)(wG221mLL2)(wH22)(wH2)(wG)(wGmLLmLHmHLm

8、HH2LL2HL2LH2HH1HL1LH1HH(a) 二維小波轉換 (b) 七個頻帶 圖7.6.2 二階段小波轉換 pqMmmpqmpqmpqmpqmpqmpqMpqMpqyxcyxcyxcyxayxf13,23,2,22,1 ,21 ,2),(),(),(),(),( )2()2(2)2()2(2)2()2(2)2()2(23,22,21 ,22qypxqypxqypxqypxmmmmpqmmmmpqmmmmpqmmmmpq 其中M代表小波轉換的總階段數m代表階數p和q代表水平和垂直方向的下標 16+2,mpqmpqfa+1 , 21 ,mpqmpqfc+2, 22,mpqmpqfc+3 ,

9、 23 ,mpqmpqfc+無邊訊息垂直邊訊息水平邊訊息對角邊訊息maLLmpqmcHLmpq1 ,mcLHmpq2,mcHHmpq3,(a) 四個基底函數 (b) 邊訊息 圖7.6.3 四個基底函數與邊訊息 211a212a1 , 211c1 , 212c1 , 221c1 , 222c221a222a2, 211c2, 212c2, 221c2, 222c3 , 211c3 , 212c3 , 221c3 , 222c1 , 111c1 , 112c1 , 114c1 , 113c1 , 121c1 , 122c1 , 124c1 , 123c1 , 131c1 , 132c1 , 134

10、c1 , 133c1 , 141c1 , 142c1 , 144c1 , 143c2, 111c2, 112c2, 114c2, 113c2, 121c2, 122c2, 124c2, 123c2, 131c2, 132c2, 134c2, 133c2, 141c2, 142c2, 144c2, 143c3 , 111c3 , 112c3 , 114c3 , 113c3 , 121c3 , 122c3 , 124c3 , 123c3 , 131c3 , 132c3 , 134c3 , 133c3 , 141c3 , 142c3 , 144c3 , 143c211a212a221a222a1 ,

11、 111c1 , 112c1 , 114c1 , 113c1 , 121c1 , 122c1 , 124c1 , 123c1 , 131c1 , 132c1 , 134c1 , 133c1 , 141c1 , 142c1 , 144c1 , 143c2, 111c2, 112c2, 114c2, 113c2, 121c2, 122c2, 124c2, 123c2, 131c2, 132c2, 134c2, 133c2, 141c2, 142c2, 144c2, 143c3 , 111c3 , 112c3 , 114c3 , 113c3 , 121c3 , 122c3 , 124c3 , 123

12、c3 , 131c3 , 132c3 , 134c3 , 133c3 , 141c3 , 142c3 , 144c3 , 143c2, 211c2, 212c2, 221c2, 222c1 , 211c1 , 212c1 , 221c1 , 222c3 , 211c3 , 212c3 , 221c3 , 222c(a) 小波係數值 (b)重新安排後的小波係數值 圖7.6.4 重新安排後的小波係數 17n產生EWC01 , 111c1 , 112c1 , 114c1 , 113c1 , 121c1 , 122c1 , 124c1 , 123c1 , 131c1 , 132c1 , 134c1 ,

13、 133c1 , 141c1 , 142c1 , 144c1 , 143c2, 111c2, 112c2, 114c2, 113c2, 121c2, 122c2, 124c2, 123c2, 131c2, 132c2, 134c2, 133c2, 141c2, 142c2, 144c2, 143c3 , 111c3 , 112c3 , 114c3 , 113c3 , 121c3 , 122c3 , 124c3 , 123c3 , 131c3 , 132c3 , 134c3 , 133c3 , 141c3 , 142c3 , 144c3 , 143c2, 211c2, 212c2, 221c2,

14、 222c1 , 211c1 , 212c1 , 221c1 , 222c3 , 211c3 , 212c3 , 221c3 , 222c000000000000000000005533決定點圖7.6.5 修正後的小波係數 LLm頻帶上並無邊的訊息，放零的值。其餘頻帶上的小波係數值一律取絕對值。 為了讓邊的訊息被相鄰兩塊區塊分享，我們將原圖最後一列和最後一行補零。原地形影像大小為2n2n, 補零於最後一列和最後一行後，大小變為(2n+1)(2n+1)。由於鄰近兩區塊分享彼此的邊緣，所以小波轉換後，每個區塊大小為(2m+1)(2m+1)，1mn。一個區塊的四個邊之中心所在的小波係數稱為決定點。1

15、8EWC將從所有33大小的區塊中得到，接著從所有55大小的區塊中得到上一層的EWC；依此由下往上的方式，直到(2n+1)(2n+1)的區塊之EWC被得到。 nwneswsep1p3p2p4nw1ne1ne2se2ne3/se1se3sw2/se4nw3/sw1nw2/ne4nw4sw4sw3圖7.6.6 決定點 /* for nw sub-block */let l be max(nw1, nw2, nw3,nw4);if p4 l then p4 := l;if p1 l then p1 := l;/* for ne sub-block */let l be max(ne1, ne2, ne

16、3,ne4);if p1 l then p1 := l;if p2 l then p2 := l;/* for se sub-block */let l be max(se1, se2, se3,se4);if p2 l then p2 := l;if p3 l then p3 := l;/* for sw sub-block */let l be max(sw1, sw2, sw3,sw4);if p3 l then p3 := l;if p4 =25圖7.6.9 留下重要的 EWC (a)(b)n四分樹式三角化程序1a2a3a4a5a6a7a8a9a重要EWC1b2b3b4b5b6b7b8

17、b9b(a) 九個外部節點的組合 (b) 九個內部節點的組合 圖7.6.10 十八個三角化的法則 21(a)(b)(c)(d)(e)圖7.6.11 三角化過程 四分樹三角化的過程是採由上而下的方式。從第一層(最上層)的四個重要EWC著手。重要EWC顯示於圖7.21(a)，圖7.21(a)上的四個重要EWC顯示於圖7.21(b)。依照圖7.20的b-9法則，將圖7.21(a)分成四個較小區塊。在第二層時，左上角的小區塊有一個重要EWC，依據a-6的法則，將該小區塊再細分成五個小的三角形。依此方式，一直往下層進行三角化的動作，最後得到圖7.21(e)的三角化結果。 22n實驗結果(b) 河流的影像

18、(a) 山的影像圖7.6.12 二張測試影像 (b) 共有17490個三角片(山的影像)(d) 共有20960個三角片(河流的影像)圖7.6.13 用我們的方法得到的實驗結果 237.7 細化和Co矩陣描述法 7.7.1 細化n細化(Thinning)其實就是在找物體的骨架(Skeleton)。n骨架的定義 令物體表示為O且物體的外圍輪廓為B。在O內，若能找到一個像素t且在B上能找到二個邊點，e1和e2，使得d(t,e1)=d(t,e2)，則t就可為O的骨架中之一個元素。這裡距離函數 d(t,ei)，1i2，表示像素t和邊點ei的距離。圖7.7.1.2 輸入之影像 圖7.7.1.3 細化後的結

19、果 24n細化Z7Z8Z9Z4Z5Z6Z1Z2Z30011Z51101考慮黑白影像的O ，以圖7.7.1.1為例 圖7.7.1.1 33子影像 N(Z5)為非零像素個數T(Z5)為灰階由0(1)變到1(0)的個數N(Z5)=5T(Z5)=2(1) 2 N(Z5) 6(2) T(Z5) = 1(3) Z2Z6Z8 = 0(4) Z2Z4Z6 = 0(7.7.1.1)當N(Z5)=0或1時，Z5可能為孤立點或最外圍的端點，Z5不必改為0。以東南方的方向進行細化：(1) 2 N(Z5) 6(2) T(Z5) = 1(3) Z4Z6Z8 = 0(4) Z2Z4Z8 = 0(7.7.1.2)利用(7.3

20、)式和(7.4)式在物體O的外圍不斷地進行細化工作，直到無法再細化為止。 以東南方的方向進行細化：25給定如下所示的小影像011111101000試問上述小影像中間的兩個像素經細化後可否被移除？Q1： Ans：先檢查下面的33子影像 0111111005)(5ZN2)(5ZT2612)(5ZT3315Z05Z由於，所以子影像中的不可改為。我們檢查下面的33子影像 1111101004)(5ZN1)(5ZT0862ZZZ0642ZZZ 由於滿足移除的四個條件 3315Z05Z所以上述的子影像中的可改為。EOA277.7.2 Co矩陣描述法n同時出現矩陣(Co-Occurrence Matrix)是一種用來表示紋理的方法。nCo矩陣可表示為Coi,j,d,，i和j代表灰階值；d代表i和