數(shù)字圖像分析第3章

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

2、以通過(guò)檢測(cè)物體邊緣來(lái)提取所需物體。l3.1.1 3.1.1 邊緣模型邊緣模型l3.1.2 3.1.2 邊緣檢測(cè)常用算子邊緣檢測(cè)常用算子一階差分一階差分各向同性算子各向同性算子二階差分二階差分方向算子方向算子l3.1.3 Marr3.1.3 Marr邊緣檢測(cè)算子邊緣檢測(cè)算子l3.1.4 Canny3.1.4 Canny邊緣檢測(cè)算子邊緣檢測(cè)算子yGxGyxfGyx),(22|yxGGG)/(tan1yxGG梯度運(yùn)算梯度運(yùn)算 :數(shù)字差分?jǐn)?shù)字差分 :), 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)函數(shù)取正態(tài)函數(shù)作卷積作卷積取零交叉取零交叉 2222exp21rrG),()(),(jifrGjiI0),(2jiIlCanny算子算子把邊緣檢測(cè)轉(zhuǎn)化為檢測(cè)單位函數(shù)極大值的問(wèn)題把邊緣檢測(cè)轉(zhuǎn)化為檢測(cè)單位函數(shù)極大值的問(wèn)題做法：做法：高斯濾波平滑高斯濾波平滑計(jì)算梯度大小與方向計(jì)算梯度大小與方向非極大值抑制非極大值抑制雙閾值檢測(cè)和連

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

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

9、數(shù)字圖象劃分為相連接的區(qū)域集合P P， P=( PP=( P1 1,P,P2 2,P,Pi i,),)P Pi i的大小設(shè)為的大小設(shè)為R RC C（通常為（通常為3 33 3）l對(duì)每一個(gè)小區(qū)域?qū)γ恳粋€(gè)小區(qū)域 ，用一個(gè)斜平面來(lái)近似用一個(gè)斜平面來(lái)近似l擬合誤差擬合誤差yxyxf),(22),(RCyxfyxel由均方誤差最小來(lái)求由均方誤差最小來(lái)求 、 、 ，l區(qū)域區(qū)域 3 33,3,原點(diǎn)取在中心點(diǎn)時(shí)，有：原點(diǎn)取在中心點(diǎn)時(shí)，有：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、得出誤差值。代入誤差算式，得出誤差值。誤差較小時(shí)，認(rèn)為擬合可靠。誤差較小時(shí)，認(rèn)為擬合可靠。CRyxf1),(l對(duì)于對(duì)于“可靠可靠”的斜面，把該擬合斜平面的斜面，把該擬合斜平面的參數(shù)作為小區(qū)域的參數(shù)（不重疊劃分的參數(shù)作為小區(qū)域的參數(shù)（不重疊劃分) ) 或小區(qū)域中心點(diǎn)的參數(shù)或小區(qū)域中心點(diǎn)的參數(shù)( (重疊劃分）。重疊劃分）。 有：梯度值為有：梯度值為 方向?yàn)榉较驗(yàn)閘然后用斜面參數(shù)判斷各個(gè)然后用斜面參數(shù)判斷各個(gè) 斜面間是否有邊緣存在。斜面間是否有邊緣存在。即考察即考察12？ 12？ 12？1tan22l1)1)選取適合的擬合區(qū)域選取適合的擬合區(qū)域l2)2)根據(jù)模型求解擬合系數(shù)根據(jù)模型求解擬合系數(shù)l3)

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

12、的零交叉）用構(gòu)造技術(shù)在二維領(lǐng)域構(gòu)造離散正交多項(xiàng)式用構(gòu)造技術(shù)在二維領(lǐng)域構(gòu)造離散正交多項(xiàng)式),(crHn當(dāng)離散鄰域?yàn)楫?dāng)離散鄰域?yàn)?1,0,1-1,0,1-1,0,1-1,0,1時(shí)（記為時(shí)（記為R RC C或或R RR R）1),(0crHrcrH),(1ccrH),(2rccrH),(432),(25 ccrH)32(),(26crcrH)32(),(27rccrH)32)(32(),(228crcrH32),(23 rcrH離散正交多項(xiàng)式：離散正交多項(xiàng)式：KnnncrHacjrigf0),(),()(icrj鄰域坐標(biāo)鄰域坐標(biāo)圖象坐標(biāo)圖象坐標(biāo)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 應(yīng)用啟發(fā)式圖搜索作物應(yīng)用啟發(fā)式圖搜索作物體體 邊界跟蹤邊界跟蹤l334 334 邊緣搜索的評(píng)價(jià)函數(shù)邊緣搜索的評(píng)價(jià)函數(shù)l跟蹤跟蹤的一般步驟：的一般步驟： l1 1、確定搜索的起點(diǎn)，對(duì)于邊緣跟蹤則確定搜索的起點(diǎn)，對(duì)于邊緣跟蹤則起點(diǎn)是某一邊緣點(diǎn)。起點(diǎn)是某一邊緣點(diǎn)。l2 2、采取一種合適的數(shù)據(jù)結(jié)構(gòu)和搜索機(jī)采取一種合適的數(shù)據(jù)結(jié)構(gòu)和搜索機(jī)理，在已有邊緣點(diǎn)的基礎(chǔ)上進(jìn)行理，在已有邊緣點(diǎn)的基礎(chǔ)上進(jìn)行搜索，搜索，不斷不斷

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

16、量不同時(shí)有聯(lián)系，評(píng)價(jià)函數(shù) f f 能能分解成幾個(gè)二元函數(shù)之和，則可分別求出各分解成幾個(gè)二元函數(shù)之和，則可分別求出各個(gè)函數(shù)的最佳值，最后求得到達(dá)目標(biāo)的最佳個(gè)函數(shù)的最佳值，最后求得到達(dá)目標(biāo)的最佳路徑。路徑。這是一種解決多元評(píng)價(jià)函數(shù)最優(yōu)化問(wèn)題的求這是一種解決多元評(píng)價(jià)函數(shù)最優(yōu)化問(wèn)題的求解方法。解方法。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 各取兩個(gè)值：各取兩個(gè)值：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評(píng)價(jià)函數(shù)可以定義為：評(píng)價(jià)函數(shù)可以定義為： )()(

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

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

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

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

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

23、”和和“背景背景”，其標(biāo)號(hào)分別為，其標(biāo)號(hào)分別為“1”1”、“0”0”100ec),(max),(0yxfGyxfGce（1 1）按與之相鄰的三個(gè)邊緣存在與否分成：）按與之相鄰的三個(gè)邊緣存在與否分成： 0 0、1 1、2 2、3 3四類。四類。（2 2）定義節(jié)點(diǎn)的可信度：）定義節(jié)點(diǎn)的可信度：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是一常數(shù)，可以取是一常數(shù)，可以取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 對(duì)每一點(diǎn)，計(jì)算對(duì)每一點(diǎn)，計(jì)算Conf(i),Conf(i),節(jié)點(diǎn)類別號(hào)節(jié)點(diǎn)類別號(hào)i i對(duì)應(yīng)對(duì)應(yīng)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故該點(diǎn)類型為故該點(diǎn)類型為1類類 邊緣的可信度按其兩端節(jié)點(diǎn)的類別進(jìn)行迭代調(diào)整，刷新。邊緣的可信度按其兩端節(jié)點(diǎn)的類別進(jìn)行迭代調(diào)整，刷新。 四種節(jié)點(diǎn)類型，形成十種邊緣狀況，分成三種情況：四種節(jié)點(diǎn)類型，形成十種邊緣狀況，分成三種情況： a a）待調(diào)整處很可能是邊