1、1第三章第三章測邊測邊2內容n3.1 前言n3.2 拉普拉斯算子n3.3 Marr-Hildreth算子n3.4 鬆弛法n3.5 基底投射法n3.6 輪廓追蹤法n3.7 動態規劃法 n3.9 作業33.1 前言n在影像的前置處理(Preprocessing)中，如何做好測邊(Edge Detection)的工作是非常重要的。 4通過零點(Zero-crossing)n灰階的突然變化(Abrupt Change)即是測邊的主要觀念之一。n一次微分後形成的波峰(Peak)，正代表著兩個區域的邊緣處。若波峰夠高，也就是已超過門檻值(Threshold)，已足以說明在該處有邊點形成的邊線(Edge L

2、ine)。 n二次微分引出的通過零點(Zero Crossing)觀念。 白黑abcyxabcyx圖3.2.1 兩個同質但不同色的區域圖3.2.2 圖3.2.1的一次微分結果圖3.2.3通過零點示意圖5n通過零點的另一個示意圖 。白黑xf(x)xf(x)xf(x)(a)(c)(b)兩個同質但不同色的區域一次微分結果通過零點示意圖63.2 拉普拉斯算子對 f(x, y) 沿著 x 軸微分得差分：再進而對 x 軸微分 (可和差分交換使用)得：令 x=x+1 以進行參數變換，可得：同理，沿著 y 軸微分二次得：合併二個軸的二次微分效應，可得拉普拉斯算子如下：),(), 1(yxfyxffx),(),

3、 1(2), 2(),(), 1(), 1(), 2(2yxfyxfyxfyxfyxfyxfyxffx), 1(),(2), 1(2yxfyxfyxffx) 1,(),(2) 1,(2yxfyxfyxffy),(4), 1() 1,(), 1() 1,(222yxfyxfyxfyxfyxffffyx(3.2.1)7n使用拉普拉斯算子來測邊：), 1(2yxf首先利用拉普拉斯算子，我們可得到影像 f 的二次微分結果 。接下來檢查 中每一位置的值來決定邊點的位置，假設我們目前正在檢查(x, y)這個位置，如果能滿足 和 的值呈現一個是正數另一個為負數，且 大於門檻值 T 的情況，我們就宣稱(x,

4、y)的位置上有一個邊點。相同的，若是 和 滿足上述條件，我們也可以將位置(x, y)上的像素視為一個邊點。需注意的是，只要 和 或 和 其中一組滿足一正一負和兩值差大於 T 的條件，我們就可以確定(x, y)的位置上存在一個邊點。f2), 1(2yxf), 1(2yxf), 1(), 1(22yxfyxf) 1,(2yxf) 1,(2yxf), 1(2yxff2) 1,(2yxf) 1,(2yxf8Sobel測邊算子nSobel測邊算子，其對應的面罩有兩個，一個為x方向，另一個為y方向。n從 和 的兩個分量，我們可知合成的量(Magnitude)為 ， 而角度 。 n為了計算更快速， 以的運算

5、取代 的運算。n另外有一個很類似Sobel測邊算子的方法 - Prewitt算子。110201102110201102圖3.2.8 Sobel測邊算子 (a) 測 x 方向的灰階變化 (b) 測 y 方向的灰階變化 22)()(ffyx ffxy 1tan fx fy ffyx 2y2x)f()f(110101101110101101圖3.2.9 Prewitt算子 (a) 測 x 方向的灰階變化 (b) 測 y 方向的灰階變化 93：給一如下的55子影像，請使用Prewitt算子來測邊，這裡 假設門檻值T為78。1539422712122148159921271231815331818456

6、0572421ANS：我們只針對下面的九個像素來決定他們是否為邊點: 10(1)(2)(3)(4)(5)(6)(7)(8)(9)ffyxx方向的灰階化y方向的灰階化(1) 6+18+15=39(2) 18+15+15=48(3) 15+15+9=39(4) -6+6+15=15(5) 6+15-3=18(6) 15-3-9=3(7) -36-39-30=-105(8) -39-30-12=-81(9) -30-12-18=-6027+36+18=81-12-6-24=-27-30-39-24=-9336+18+15=69-6-9+3=-12-38-24-15=-7718+15+12=45-9+

7、3-3-42-24-15-36=-7539+81 = 120 T48+27 = 75 39+93 = 132 T15+69 = 84 T18+12 = 30 3+78 = 81 T105+45 = 150 T81+42 = 123 T60+75 = 135 T圖3.2.10為使用Prewitt算子得到的相關資訊 圖3.2.10利用Prewitt算子得到的結果 11 從圖3.2.10中可得知像素(1)、(3)、(4)、(6)、(7)、(8)和(9)皆為邊點，所以最後測邊結果為一個如下的倒字型。EOA123.3 Marr-Hildreth算子nMarr-Hildreth測邊算子結合了高斯平滑算子和

8、拉普拉斯算子的雙重技巧。n高斯平滑算子(Gaussian Smoothing Operator)：nLOG (Laplacian of Gaussian)： 表迴積運算，而 表拉普拉斯算子。 2222),( yxeyxG ),(),(2yxfyxGLOG 2 (3.3.2)結合性),(),(2yxfyxGLOG(3.3.3)(3.3.1)13為得到一個面罩且其面罩內的加權和為零，我們令LOG的面罩形式如下所示，這裡的常數C是用來正規化用的。 ：222yxr 222),(reyxG2222rexxG222222222222222222)(1)(1rrrexexxexG2222reyyG22222

9、2222)(1reyyG22222),(yGxGyxG22222222)2(1reyx),(*)2(12222222yxfeyxLOGr2222)(4222)2(yxeyxcLOG令 ，則 ，對 x 微分一次，得再對 x 微分一次，得同理，我們可推得綜合以上推演，可得代入式子(3.3.3) ，可得14Q1： 可否對式(3.3.4)的得來多做解釋?ANS：假設我們使用的面罩大小仍為5x5，面罩內各像素的位置定 義如下： (-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)(

10、-1,-1)(0,-1)(1,-1)(2,-1)(-2,-2)(-1,-2)(0,-2)(1,-2)(2,-2)我們將面罩內25個位置座標代入下面式子中的(x, y)內2222)(42222yxeyx15如此一來，可得到25個值，我們根據這25個值的大小，可 將它們分為4類： *O*OxO*OxxO*OxO*O*上面的分類中，打 * 號的值為趨近於零;打 、x、和O號的值都不大，但是以16：-2：-1的比例呈現。如此一來，我們就得到式(3.3.4)的墨西哥帽子式樣的面罩。 EOA1600100012101216210121000100圖3.3.1 測試影像 圖3.3.2 利用Marr-Hild

11、reth算子測邊後的結果 (3.3.4)面罩大小為55，正規化後則可得下列面罩： 17nCanny首先利用高斯平滑算子去除過多的細紋，然後在每個像素上計算其梯度方向和梯度量。假若在這梯度方向上，該像素的梯度量大於二個鄰居的量，則該像素為邊點，否則為非邊點。較弱的邊點可利用磁滯(Hysteresis)門檻化予以去除。圖3.3.3 利用Canny測邊法所得到 的邊圖(Edge Map) 183.4 鬆弛法n有些邊是由稀稀疏疏的邊點構成，而這些邊點並非連接的。n 端點類型：圖3.4.1二個小例子 (a) 強邊線例子 (b) 弱邊線例子 (a) 無邊型端點 (b) 一邊型端點 (c) 二邊型端點 (d

12、) 三邊型端點 圖3.4.2端點的四個類型 19n開始的信賴度：n信賴度的疊代式：)()()(所有eSMaxeSeCe),(),()(yxfyxfeS ，此處 代表鄰近 的像素灰階值。 ),(yxf),(yxf(3.4.1)(3.4.2)DedeCUeeCIedeCeCkkkk若)(, 0max(若)(若)(, 1min()(1符號 I 代表需增加其強度d；符號U代表不改變其強度d；符號D則代表需減弱其強度d。直到對所有的e而言， 時，就可停止這疊代的過程。也可自行設定疊代的次數限制。 )()(1eCeCkkI(加強)0-1，1-01-2 ，2-11-3 ，3-11-1D(減弱)0-2，2-0

13、0-3，3-00-0U(不動)2-2，2-33-3，3-2圖3.4.3強度增減表0代表無邊型端點，1代表一邊型端點，2代表二邊型端點，而3代表三邊型端點。 20Q1：可否舉一個小例子以說明式(3.4.1)?ANS：首先將各像素以節點的型式表示，而鄰近兩兩像素的灰階差之絕對值以圖論符號的邊表示，我們由是得到下面的灰階差異圖：將S(e)集合中的最大值挑出，可得到 ，根據信賴度的定義，上面的灰階差異圖轉換為下面的信賴圖： ( )eMaxS e21假設邊的門檻值定為0.5，則對端點A和端點B而言，可得到EOA223.5 基底投射法n在圖3.5.1中任挑二個不同向量，皆可檢定出內積為零，從而知道這九個向

14、量兩兩為正交的。n令圖3.5.1中的九個向量分為 、 、 和 ，則 、 、 和可另外構成一組正交且單位化的基底。221111000221111000211110002221111000111100000111100000114222211114222211111111111(a) (b) (c) (d) (e) (f) (g) (h) (i) 圖3.5.1 基底 1v2v9v111vvw 222vvw 999vvw 23n視窗所框住的子影像，依列優先(Row Major Order)的順序得向量 。對上述九個正交且單位化的基底投影，可得 、 、 和 。令 假設m對應的基底之向量為圖3.5.1(

15、a)，則代表有類似圖3.2.8(a)所測得的邊點。若對應的為圖3.5.1(i)，則表z的紋理頗平滑的。n實作時，也需引入門檻值，依迴積的方式進行。n基底投射法的缺點是，有些基底向量的代表意義不是很明確。33tzzzz),.,(92111wzmt22wzmt99wzmt,.,921mmmMaxm 24Q1：以上的九個基底向量為何要化成單位正交向量? 可否給一個示 意圖以明示基底投射法的觀念? ANS：每個基底的向量經過單位正交化後，我們在進行基底投射 (其實就是做內積運算)時，才有比較公平的尺度。令自影像中 取出的3x3子影像為S，而 代表子影像S和單位正交 基底向量進行向量內積運算。當完成了所

16、有的九個內積運算 後，我們再從中排出最大內積值所對應的 。如果最大內積值 大於門檻值，則 能讓我們更了解該邊點(子影像的正中央像 素)的紋理特性。以上的運算可以用下面的示意圖來解釋： SiWiWiW25EOA263.6 輪廓追蹤法(蛇行法)n在物體邊緣的外側些標識一圈控制點集(可利用雲形曲線集 )。n能量函數 dtEtEtEtEimagecurvcont )()()( (3.6.1)212)( iicontbbdttdcE2112222)( iiicurvbbbdttcdEIEimage 微分一次後連續項能量微分二次後平滑項能量輪廓受到往影像邊點處的拉力為影像中初步用雲形曲線框住的輪廓且輪廓上

17、構成的點為 、 、 和 。通常 、 和 可定為1，但是若碰到角點(Corner Point)時， 可定為0。)(tc1b2b3bnbi i i i 27雲形曲線(B-spline Curve)iv1iv2iv3iv)(3,0tN)(3, 1tN)(3,2tN)(3,3tN)()(3,0tNvtPii )()()(3,333,223, 11tNvtNvtNviii 10 t)0()1(3, 13,0NN )0()1(3,23, 1NN )0()1(3,33,2NN )0()1(3, 13, 0NN )0()1(3, 23, 1NN )0()1(3, 33, 2NN )0()1( 3, 1 3,

18、0NN )0()1( 3, 2 3, 1NN )0()1( 3, 3 3, 2NN 0)0(3,0 N0)0(3,0 N0)0( 3,0 N0)1(3,3 N0)1(3,3 N0)1( 3,3 N33,061)(ttN) 1333(61)(233, 1ttttN)463(61)(233,2tttN) 133(61)(233, 3ttttN 321230141030303631331161)(iiiiivvvvttttP給定四個控制點， ， 和 ，令四個接續的彎曲函數為 ，和 。且該雲形曲線 ，利用四個彎曲函數(Blending Function)的下列十六個等式關係雲形曲線可表示為：28圖3.6.1 輸入的影像 圖3.6.3 最終所找到的輪廓 圖3.6.2 初始輪廓 n正規化能量項： 和 可除以視窗內相關能量的最大值。 中的 可改為 ，這裡m代表鄰近 的最小值，而M代表鄰近 的最大值。n從 出發，首先以 視窗將點 框住，針對視窗內的每一點計算其能量。移往能量和所得為最小的點。直到n個點都處理完。不斷地進行疊代直到輪廓不再改變為止。 contEcurvEimageEI mMmI I I 1b33 1b293.7 動態規劃法n假設我們給定起始像素集為 如圖3.7.1(a)所示。另外，假設我們想在最終像素 集中找到一個像素 使得 到 之間有一條路徑為邊點形成的最佳