1、l第三章第三章 邊緣檢測邊緣檢測 ( (Edge Detection) )l第四章第四章 圖象分割圖象分割 ( (Image Segmentation) )l第五章第五章 模板匹配模板匹配 ( (Template Matching) )圖象分割圖象分割特征抽取特征抽取分類分類輸入圖象輸入圖象輸出類別輸出類別物體圖象物體圖象特征向量特征向量X1X2.XNl3.1 3.1 邊緣增強算子邊緣增強算子l3.2 3.2 邊緣擬合邊緣擬合l3.3 3.3 邊緣搜索邊緣搜索l3.4 3.4 松弛法松弛法邊緣是圖象中對象的基本的特征之一，邊緣是圖象中對象的基本的特征之一，可以通過檢測物體邊緣來提取所需物體?？?/p>

2、以通過檢測物體邊緣來提取所需物體。l3.1.1 3.1.1 邊緣模型邊緣模型l3.1.2 3.1.2 邊緣檢測常用算子邊緣檢測常用算子一階差分一階差分各向同性算子各向同性算子二階差分二階差分方向算子方向算子l3.1.3 Marr3.1.3 Marr邊緣檢測算子邊緣檢測算子l3.1.4 Canny3.1.4 Canny邊緣檢測算子邊緣檢測算子yGxGyxfGyx),(22|yxGGG)/(tan1yxGG梯度運算梯度運算 :數字差分數字差分 :), 1(),(jifjifGGix) 1,(),(jifjifGGjy), 1() 1,(),(2),(jifjifjifGGjifji-11-11i,

3、j-1i-1,ji,j 1 0 0 -1 0 1-1 0 1 0 -1 1 0 -1 1 0 -1-1 -1 -1 0 0 0 1 1 1 1 0 -1 2 0 -2 1 0 -1-1 -2 -1 0 0 0 1 2 1Gx GyRobertsPrewittSobel一階一階二階二階 0 1 0 1 4 1 0 1 0Laplace 0 -1 0 -1 8 -1 0 -1 012345678 3 3 5 3 0 5 3 3 -5 3 -5 5 3 0 5 3 3 3-5 -5 5 3 0 3 3 3 3-5 -5 3-5 0 3 3 3 3 3 3 3 3 0 5 3 -5 -5 3 3 3-

4、5 0 3-5 -5 3-5 3 3-5 0 3-5 3 3 3 3 3 3 0 3-5 -5 -5G1G5G3G4G6G7G8G2f(x-1, y-1)f(x, y-1)f(x+1, y-1)f(x-1, y)f(x+1, y)f(x-1, y+1)f(x, y+1)f(x+1, y+1)0000222200002222000022220000222200002222000022220000222200002222000-20000000-20000000-20000000-20000000-20000000-20000000-20000000-20000100-10002000000020

5、00000020000000200000002000000020000000200000002000001-100004000000040000000400000004000000040000000400000004000000040000000-8-8000000-8-8000000-8-8000000-8-8000000-8-8000000-8-8000000-8-8000000-8-800010-120-210-10000000000000000000000000000000000000000000000000000000000000000121000-1-2-1000880000008

6、80000008800000088000000880000008800000088000000880000002-20000002-20000002-20000002-20000002-20000002-20000002-20000002-20000101-41010取正態(tài)函數取正態(tài)函數作卷積作卷積取零交叉取零交叉 2222exp21rrG),()(),(jifrGjiI0),(2jiIlCanny算子算子把邊緣檢測轉化為檢測單位函數極大值的問題把邊緣檢測轉化為檢測單位函數極大值的問題做法：做法：高斯濾波平滑高斯濾波平滑計算梯度大小與方向計算梯度大小與方向非極大值抑制非極大值抑制雙閾值檢測和連

7、接雙閾值檢測和連接l對圖象中一個子區(qū)域，用理對圖象中一個子區(qū)域，用理想灰度階躍或斜變去擬合實想灰度階躍或斜變去擬合實際圖象數據，從而求出擬合際圖象數據，從而求出擬合的理想模型參數，如階躍幅的理想模型參數，如階躍幅度、斜變傾角等，并以此為度、斜變傾角等，并以此為這個子區(qū)域的邊緣強度和方這個子區(qū)域的邊緣強度和方向度量向度量l從某種意上說，擬合是匹配從某種意上說，擬合是匹配濾波，旨在從失真和噪聲中濾波，旨在從失真和噪聲中檢測出理想邊緣來。因此，檢測出理想邊緣來。因此，有較強的抗噪聲能力有較強的抗噪聲能力 l構造原圖象（或子圖、小構造原圖象（或子圖、小區(qū)域）的擬合曲面，再在區(qū)域）的擬合曲面，再在擬合曲

8、面上利用曲面的參擬合曲面上利用曲面的參數檢測出邊緣數檢測出邊緣l如如: :灰度階躍邊緣擬合?；叶入A躍邊緣擬合。用理想灰度階躍模型去擬用理想灰度階躍模型去擬合一個合一個2 22 2的子圖。將子的子圖。將子圖圖f(x,y)f(x,y)展開成基函數表展開成基函數表達式。由均方誤差最小求達式。由均方誤差最小求邊緣幅度和角度邊緣幅度和角度ACab)1 (4DACB24DASa24DASb式中式中DCBASAC邊緣幅度：邊緣幅度：|DAba與與RobertsRoberts算子算子的結果相同的結果相同在第一象限，在第一象限，有：有：1 1、擬合模型擬合模型l將將M MN N的數字圖象劃分為相連接的區(qū)域集合的

9、數字圖象劃分為相連接的區(qū)域集合P P， P=( PP=( P1 1,P,P2 2,P,Pi i,),)P Pi i的大小設為的大小設為R RC C（通常為（通常為3 33 3）l對每一個小區(qū)域對每一個小區(qū)域 ，用一個斜平面來近似用一個斜平面來近似l擬合誤差擬合誤差yxyxf),(22),(RCyxfyxel由均方誤差最小來求由均方誤差最小來求 、 、 ，l區(qū)域區(qū)域 3 33,3,原點取在中心點時，有：原點取在中心點時，有：CRxyxfx2),(CRyyxfy2),(XY-1 0 1-1 0 1-1 0 1-1 -1 -1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1代入誤差算式，

10、得出誤差值。代入誤差算式，得出誤差值。誤差較小時，認為擬合可靠。誤差較小時，認為擬合可靠。CRyxf1),(l對于對于“可靠可靠”的斜面，把該擬合斜平面的斜面，把該擬合斜平面的參數作為小區(qū)域的參數（不重疊劃分的參數作為小區(qū)域的參數（不重疊劃分) ) 或小區(qū)域中心點的參數或小區(qū)域中心點的參數( (重疊劃分）。重疊劃分）。 有：梯度值為有：梯度值為 方向為方向為l然后用斜面參數判斷各個然后用斜面參數判斷各個 斜面間是否有邊緣存在。斜面間是否有邊緣存在。即考察即考察12？ 12？ 12？1tan22l1)1)選取適合的擬合區(qū)域選取適合的擬合區(qū)域l2)2)根據模型求解擬合系數根據模型求解擬合系數l3)

11、3)求擬合斜面各點灰度值求擬合斜面各點灰度值l4)4)計算誤差，判斷斜面的可靠性計算誤差，判斷斜面的可靠性l5)5)對于可靠的斜面，對于可靠的斜面， 計算相鄰點或區(qū)域不在同一斜面上的度量計算相鄰點或區(qū)域不在同一斜面上的度量l6)6)選出邊緣度量值局部最大的點，定為邊選出邊緣度量值局部最大的點，定為邊緣點緣點l選定領域，用多項式作為擬合曲面；選定領域，用多項式作為擬合曲面；l求解多項式系數，獲得最佳擬合；求解多項式系數，獲得最佳擬合；l將擬合曲面的參數作為考察點的參數，將擬合曲面的參數作為考察點的參數， 用二階方向導數檢測邊緣。用二階方向導數檢測邊緣。 （求二階方向導數的零交叉）（求二階方向導數

12、的零交叉）用構造技術在二維領域構造離散正交多項式用構造技術在二維領域構造離散正交多項式),(crHn當離散鄰域為當離散鄰域為-1,0,1-1,0,1-1,0,1-1,0,1時（記為時（記為R RC C或或R RR R）1),(0crHrcrH),(1ccrH),(2rccrH),(432),(25 ccrH)32(),(26crcrH)32(),(27rccrH)32)(32(),(228crcrH32),(23 rcrH離散正交多項式：離散正交多項式：KnnncrHacjrigf0),(),()(icrj鄰域坐標鄰域坐標圖象坐標圖象坐標KnnncrHacjrigf0),(),()(由均方誤差

13、最小由均方誤差最小),(),(cjrifcranRXRn得得 ：min(.)(.)22RXRfge 1 1 1 1 1 1 1 1 1-1 0 1-1 0 1-1 0 1-1 -1 -1 0 0 0 1 1 1 1 -2 1 1 -2 1 1 -2 1-1 0 1 2 0 -2 -1 0 1 1 0 -1 0 0 0-1 1 1 1 1 1-2 -2 -2 1 1 1 1 -2 1-2 4 -2 1 -2 1-1 2 -1 0 0 0 1 -2 10 1/91 1/62 1/65 1/68 1/44 1/43 1/66 1/47 1/4RRnRXRnncrHcjrifcrHa),(),(),(

14、2n1),(0crHRRcrHcrH),(),(2000 1 1 1 1 1 1 1 1 10 1/9l331 331 跟蹤方法跟蹤方法l332 332 啟發(fā)式圖搜索啟發(fā)式圖搜索l333 333 應用啟發(fā)式圖搜索作物應用啟發(fā)式圖搜索作物體體 邊界跟蹤邊界跟蹤l334 334 邊緣搜索的評價函數邊緣搜索的評價函數l跟蹤跟蹤的一般步驟：的一般步驟： l1 1、確定搜索的起點，對于邊緣跟蹤則確定搜索的起點，對于邊緣跟蹤則起點是某一邊緣點。起點是某一邊緣點。l2 2、采取一種合適的數據結構和搜索機采取一種合適的數據結構和搜索機理，在已有邊緣點的基礎上進行理，在已有邊緣點的基礎上進行搜索，搜索，不斷不斷

15、確定新的邊緣點。確定新的邊緣點。 l3 3、規(guī)定搜索終止的條件，在滿足條件規(guī)定搜索終止的條件，在滿足條件時停止搜索。時停止搜索。l光柵跟蹤光柵跟蹤l輪廓跟蹤輪廓跟蹤985 5564 49564736294643526647l1、基本概念、基本概念啟發(fā)式圖搜索（動態(tài)規(guī)劃）是尋求達到某一啟發(fā)式圖搜索（動態(tài)規(guī)劃）是尋求達到某一目標的最佳路徑（最短路徑，最小消耗路徑）目標的最佳路徑（最短路徑，最小消耗路徑） 路徑的路徑的“消耗消耗”用評價函數來表示，評價函用評價函數來表示，評價函數數f f 往往由多個因素（往往由多個因素（N N個變量）決定。個變量）決定。如果如果N N個變量不同時有聯(lián)系，評價函數個變

16、量不同時有聯(lián)系，評價函數 f f 能能分解成幾個二元函數之和，則可分別求出各分解成幾個二元函數之和，則可分別求出各個函數的最佳值，最后求得到達目標的最佳個函數的最佳值，最后求得到達目標的最佳路徑。路徑。這是一種解決多元評價函數最優(yōu)化問題的求這是一種解決多元評價函數最優(yōu)化問題的求解方法。解方法。0)(11xh)(),(min)(22322332xhxxfxhx),(min)(211221xxfxhx)(),(min)(111kkkkkxkkxhxxfxhk)(),(min)(1111NNNNNxNNxhxxfxhN),.,(min)(min21NNNxxxfxh),(.),(),(),.,(11

17、32221121NNNNxxfxxfxxfxxxff1(x1,x2)H2(x2)f2(x2,x3)H3(x3)3(0,0)5(0,0)7(0)2(1,0)2(0)7(1,0)4(0,1)4(1)6(0,1)5(1,1)2(1,1)6(1)f(x1,x2,x3) = f1(x1,x2) + f2(x2,x3) x1, x2 , x3 各取兩個值：各取兩個值：0，1)(),(min)(111kkkkkxkkxhxxfxhk 7 6 2 4 3 S 5 0 1 2 5 X1 X2 X3 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5l評價函數可以定義為：評價函數可以定義為： )()(

18、)(nhngnf式中：式中： 表示搜索過程進行到的節(jié)點，稱為當前節(jié)點，表示搜索過程進行到的節(jié)點，稱為當前節(jié)點， 為從起始節(jié)點到當前節(jié)點所有路徑的為從起始節(jié)點到當前節(jié)點所有路徑的“耗費值耗費值” 是當前節(jié)點到目標節(jié)點將要經過的所有路徑的是當前節(jié)點到目標節(jié)點將要經過的所有路徑的 “耗費值耗費值”。)(ng)(nhnnl灰度梯度的幅度灰度梯度的幅度l灰度梯度的方向灰度梯度的方向l路徑的曲率路徑的曲率l路徑與某一函數路徑與某一函數 的近似程度的近似程度l到目標點的距離等到目標點的距離等A,D,F,H 權重均為權重均為2121A,D,F,I 但是但是ADEGA,D,E,G 曲率太大曲率太大l使用使用“啟

19、發(fā)啟發(fā)”信息，構造評價函數，計信息，構造評價函數，計算路徑的耗費，是啟發(fā)式搜索的關鍵。算路徑的耗費，是啟發(fā)式搜索的關鍵。l具體如何構造則要分析該問題的具體情具體如何構造則要分析該問題的具體情況，將多種因素合理的分離開來，把實況，將多種因素合理的分離開來，把實際情況中的約束轉化為計算機可操作的際情況中的約束轉化為計算機可操作的表達式。表達式。l3.4.1 3.4.1 一般概念一般概念一種動態(tài)調優(yōu)的標號方法一種動態(tài)調優(yōu)的標號方法l3.4.2 3.4.2 松弛法邊緣提取松弛法邊緣提取獲得初始邊緣獲得初始邊緣計算邊緣可信度計算邊緣可信度 相容模型相容模型迭代，刷新邊緣可信度迭代，刷新邊緣可信度 調整模

20、型調整模型l是一種動態(tài)調優(yōu)的迭代方法是一種動態(tài)調優(yōu)的迭代方法初始結果初始結果 不斷迭代不斷迭代 更好的結果更好的結果l松弛法要建立一種相容模型，給出合理的相容松弛法要建立一種相容模型，給出合理的相容系數（往往根據空間結構來建立）。系數（往往根據空間結構來建立）。l同時要建立動態(tài)調整的模型，同時要建立動態(tài)調整的模型， 給出能收斂到確定狀態(tài)的迭代運算的公式。給出能收斂到確定狀態(tài)的迭代運算的公式。通過多次迭代，收斂到最終結果。通過多次迭代，收斂到最終結果。 因有噪聲等干擾，以致物體圖象部分缺損，因有噪聲等干擾，以致物體圖象部分缺損，或物體之間相互重疊，此時，用松弛法可以得或物體之間相互重疊，此時，用

21、松弛法可以得到較一般方法更滿意的結果。到較一般方法更滿意的結果。 松弛法利用有關對象的先驗信息，特別是空松弛法利用有關對象的先驗信息，特別是空間相關性方面的知識，有獨到之處。（如圖象間相關性方面的知識，有獨到之處。（如圖象遭受干擾，有關對象的輪廓或其它信息損失或遭受干擾，有關對象的輪廓或其它信息損失或減少時，要想得到對象完整的輪廓，必須進一減少時，要想得到對象完整的輪廓，必須進一步考慮關于對象的一些先驗信息。）步考慮關于對象的一些先驗信息。）對象集合：對象集合：標號集合：標號集合：將標號將標號 賦給賦給 的概率為：的概率為：將標號將標號 賦給賦給 的概率為：的概率為：相容系數：相容系數：（條件

22、概率）（條件概率）相容總量：相容總量：迭代公式：迭代公式：,21NuuuU,21MlllLpliu)(pilPqlju)(qjlP),;,(qjpiluluCC在01之間取值 )()(),;,()(1)(lVuLlqjqjpipipiijqlPluluClVlQLmnininininimQmPlQlPlP)()()()()()()()()()1(假定假定：l邊邊緣緣是灰度階躍；是灰度階躍；l只有水平、垂直的邊只有水平、垂直的邊緣；緣；（4鄰近，市區(qū)距離）鄰近，市區(qū)距離）l已獲得初始結果，已獲得初始結果，有初始邊有初始邊緣。緣。 動態(tài)調優(yōu)的標號方法動態(tài)調優(yōu)的標號方法本例只區(qū)分本例只區(qū)分“邊緣邊緣

23、”和和“背景背景”，其標號分別為，其標號分別為“1”1”、“0”0”100ec),(max),(0yxfGyxfGce（1 1）按與之相鄰的三個邊緣存在與否分成：）按與之相鄰的三個邊緣存在與否分成： 0 0、1 1、2 2、3 3四類。四類。（2 2）定義節(jié)點的可信度：）定義節(jié)點的可信度：Conf(O) Conf(O) Conf(1) Conf(1) Conf(2) Conf(2) Conf(3) Conf(3) 0 0 類類 1 1 類類 2 2 類類 3 3 類類 abcConf(0) = (m-a)(m-b)(m-c)Conf(0) = (m-a)(m-b)(m-c)其中其中: m =

24、max(a,b,c,q) : m = max(a,b,c,q) Conf(1) = a(m-b)(m-c) Conf(1) = a(m-b)(m-c) q q是一常數，可以取是一常數，可以取0.10.1左右左右Conf(2) = ab(m-c) Conf(2) = ab(m-c) a a，b b，c c 取歸一化梯度的模取歸一化梯度的模Conf(3) = abc Conf(3) = abc 令令 a b ca b c 對每一點，計算對每一點，計算Conf(i),Conf(i),節(jié)點類別號節(jié)點類別號i i對應對應Conf(i)Conf(i)的最大值的最大值 q 取取 0.1 a=0.25 b=0.01 c=0.01則有則有 conf(0)=0 conf(1)=0.0144conf(2)=0.0006conf(3)=0.000025故該點類型為故該點類型為1類類 邊緣的可信度按其兩端節(jié)點的類別進行迭代調整，刷新。邊緣的可信度按其兩端節(jié)點的類別進行迭代調整，刷新。 四種節(jié)點類型，形成十種邊緣狀況，分成三種情況：四種節(jié)點類型，形成十種邊緣狀況，分成三種情況： a a）待調整處很可能是邊