第三章 測邊.

Presentation on theme: "第三章 測邊."— Presentation transcript:

1 第三章 測邊

2 內容 3.1 前言 3.2 拉普拉斯算子 3.3 Marr-Hildreth算子 3.4 基底投射法 3.5 輪廓追蹤法

3 3.1 前言 在前置處理(Preprocessing)中，做好測邊(Edge Detection)的工作是非常重要的。

4 通過零點(Zero-crossing) 主要觀念:灰階的突然變化(Abrupt Change) 。
一次微分後形成的波峰(Peak)超過門檻值(Threshold)，有邊點形成。 二次微分:通過零點(Zero Crossing)觀念。 a b c y x a b c y x 白 黑 圖3.2.1 兩個同質但不同色的區域 圖3.2.2 圖3.2.1的一次微分結果 圖3.2.3 通過零點示意圖

5 通過零點的另一個示意圖 。 x f(x) f’(x) f(x) (a)兩個同質但不同色的區域 (b)一次微分結果 (c)通過零點示意圖
白 黑 x f(x) f’(x) f(x) (a)兩個同質但不同色的區域 (b)一次微分結果 (c)通過零點示意圖 圖3.2.4 通過零點的另一個示意圖

6 3.2 拉普拉斯算子 對 f(x, y) 沿 x 軸差分： 再對 x 軸差分得： 令 x=x+1 ，可得： 同理，沿著 y 軸差分二次得：
合併可得拉普拉斯算子： (3.2.1)

7 如果能滿足 和 的值呈現一個是正數另一個為負數，且 大於門檻值 T 的情況，我們就宣稱(x, y)的位置上有一個邊點。
圖3.2.5面罩的數學背景來源為式(3.2.1) 使用拉普拉斯算子來測邊： 1 -4 圖3.2.5 拉普拉斯測邊算子 如果能滿足 和 的值呈現一個是正數另一個為負數，且 大於門檻值 T 的情況，我們就宣稱(x, y)的位置上有一個邊點。 相同的，若是 和 滿足上述條件，我們也 可以將位置(x, y)上的像素視為一個邊點。

8 Sobel測邊算子 Sobel測邊算子，其對應的面罩有兩個，一個為x方向，另一個為y方向。
從 和 的兩個分量，我們可知合成的量(Magnitude)為 ， 　 而角度為 。 為了計算更快速， 以　　　　　的運算取代　　　　　　　 的運算。 另外有一個很類似Sobel測邊算子的方法 - Prewitt算子。 圖3.2.8 Sobel測邊算子 (b) 測 x 方向的灰階變化 (a) 測 y 方向的灰階變化 圖3.2.9 Prewitt算子 (b) 測 x 方向的灰階變化 (a) 測 y 方向的灰階變化

9 範例3： 給一如下的5×5子影像，請使用Prewitt算子來測邊，這裡 假設門檻值T為78。
15 39 42 27 12 21 48 9 3 18 33 45 60 57 24 解答：

10 (1) (2) (3) (4) (5) (6) (7) (8) (9) 圖3.2.10(a) 為使用Prewitt算子得到的相關資訊 圖3.2.10(b)利用Prewitt算子得到的結果 (1) =-39 (2) =48 (3) =39 (4) =15 (5) =18 (6) =-3 (7) =105 (8) =81 (9) =60 =81 =-27 =-93 =69 -6-9+3=-12 =-78 =45 =-42 =-75 39+81 = 120 > T 48+27 = 75 39+93 = 132 > T 15+69 = 84 > T 18+12 = 30 3+78 = 81 > T = 150 > T 81+42 = 123 > T 60+75 = 135 > T

11 從圖3.2.10中可得知像素(1)、(3)、(4)、(6)、(7)、(8)和(9)皆為邊點，所以最後測邊結果為一個如下的倒ㄇ字型。
Ｘ 解答完畢

12 3.3 Marr-Hildreth算子 Marr-Hildreth測邊算子結合了高斯平滑算子和拉普拉斯算子的雙重技巧。
高斯平滑算子(Gaussian Smoothing Operator)： LOG (Laplacian of Gaussian)： 　 表迴積運算，而 表拉普拉斯算子。 (3.3.1) (3.3.2)  (3.3.3) 結合性

13 令 ，則 ，對 x 微分一次，得 再對 x 微分一次，得 同理，我們可推得 綜合以上推演，可得 代入式子(3.3.3) ，可得 為得到一個面罩且其面罩內的加權和為零， 我們令LOG的面罩形式如下所示，這裡的常數c是用來正規化用的。

14 將面罩內25個位置座標代入 (x, y)內 範例1：可否對式(3.3.4)的得來多做解釋?
解答：假設面罩大小為5×5，各像素的位置定 義如下： (-2,2) (-1,2) (0,2) (1,2) (2,2) (-2,1) (-1,1) (0,1) (1,1) (2,1) (-2,0) (-1,0) (0,0) (1,0) (2,0) (-2,-1) (-1,-1) (0,-1) (1,-1) (2,-1) (-2,-2) (-1,-2) (0,-2) (1,-2) (2,-2) 將面罩內25個位置座標代入 (x, y)內

15 上面的分類中，打 * 號的值為趨近於零;打 、x、和O號的 值都不大，但是以16：-2：-1的比例呈現。
解答完畢

16 正規化後則可得下列面罩： (3.3.4) 圖3.3.1 測試影像 圖3.3.2 利用Marr-Hildreth算子 測邊後的結果

17 圖3.3.3 利用Canny測邊法 所得到的邊圖(Edge Map)
Canny首先利用高斯平滑算子去除過多的細紋，然後在每個像素上計算其梯度方向和梯度量。假若在這梯度方向上，該像素的梯度量大於二個鄰居的量，則該像素為邊點，否則為非邊點。較弱的邊點可利用磁滯(Hysteresis)門檻化予以去除。 圖 利用Canny測邊法 所得到的邊圖(Edge Map)

18 3.4 基底投射法 在圖3.4.1中任挑二個不同向量，皆可檢定出內積為零，從而知道這九個向量兩兩為正交的。
(a) (b) (c) (d) (e) (f) (g) (h) (i) 在圖3.4.1中任挑二個不同向量，皆可檢定出內積為零，從而知道這九個向量兩兩為正交的。 令圖3.4.1中的九個向量分為 、 、 …和 ，則 、 、… 和可另外構成一組正交且單位化的基底。 圖3.4.1 基底

19 視窗所框住的　　子影像，依列優先(Row Major Order)的順序得向量 。對上述九個正交且單位化的基底投影，可得 、 、 … 和 。令
　 假設m對應的基底之向量為圖3.4.1(a)，則代表有水平紋理邊點。若對應的為圖3.4.1(i)，則表z在平滑區域。 實作時，引入門檻值，依迴積方式進行。 缺點:有些基底向量的意義不明確。

20 範例1：以上的九個基底向量為何要化成單位正交向量? 可否給一個示意圖以明示基底投射法的觀念?
解答： 解答完畢

21 3.5 輪廓追蹤法 在物體邊緣外側邊緣標識一圈控制點集(可利用雲形曲線集 )。 能量函數 (3.6.1)  微分一次後連續項能量 
微分二次後平滑項能量  輪廓受到往影像邊點處的拉力 　　為影像中初步用雲形曲線框住的輪廓且輪廓上構成的點為 、 、 …和 。通常 、 和 可定為1，但是若碰到角點(Corner Point)時， 可定為0。

22 雲形曲線(B-spline Curve) 給定四個控制點 vi，vi+1 ，vi+2 和 vi+3，令四個接續的彎曲函數為
，　　　，　　　和　　　 。且該雲形曲線 ， 利用四個彎曲函數(Blending Function)的下列十六個等式關係 雲形曲線可表示為： 

23 中的 可改為 ，這裡m代表鄰近 的最小值，而M代表鄰近 的最大值。
正規化能量項： 　 和 可除以視窗內相關能量的最大值。 　 中的 可改為 ，這裡m代表鄰近 的最小值，而M代表鄰近 的最大值。 從 出發，首先以3 × 3 視窗將點 框住，針對視窗內的每一點計算其能量。移往能量和所得為最小的點。直到n個點都處理完。不斷地進行疊代直到輪廓不再改變為止。 圖3.5.1 輸入的影像 圖3.5.2 初始輪廓 圖3.5.3 最終所找到的輪廓