視頻監(jiān)控與視頻分析第五章 圖像分割1課件

1、圖像分割技術(shù) Image Segmentation1 圖像分割概述 2 邊緣檢測 3 閾值分割4 區(qū)域分割 5 彩色圖像分割7.1 圖像分割概述 圖像分割的概念 圖像分割的意義 圖像分割的基本思路 圖像分割的基本策略圖像分割：是指根據(jù)灰度、彩色、紋理等特征把圖像劃分成若干個互不相交的區(qū)域，使得這些特征在同一區(qū)域內(nèi)，表現(xiàn)出一致性或相似性，而在不同區(qū)域間表現(xiàn)出明顯的不同。 什么是圖像分割？彩色圖像分割為什么進行圖像分割 在對圖像的研究和應用中，人們往往僅對圖像中的某些部分或稱為目標感興趣。 為了辨識和分析目標，需要將有關(guān)區(qū)域分離提取出來，在此基礎(chǔ)上對目標進一步分析，如進行特征提取和識別等等。 圖像

2、分割是由圖像處理到圖像分析的關(guān)鍵步驟，只有在圖像分割的基礎(chǔ)上才能對目標進行特征提取、參數(shù)測量和識別，使得更高層的圖像分析和理解成為可能。例： 車牌識別蘇E7Y915圖像分割的依據(jù) 對圖像的分割主要基于象素的2個性質(zhì)： 不連續(xù)性和相似性； “相似性分割”就是將具有同一特性（特性可以是灰度、顏色、紋理等）的像素聚集在一起，形成圖像中的不同區(qū)域。 “非連續(xù)性分割”需要先檢測圖像的局部不連續(xù)性，然后將它們連接起來形成邊界，這些邊界將圖像分割成不同的區(qū)域。 圖像分割的算法分類 圖像分割的基本思路從簡到難，逐級分割；控制背景環(huán)境，降低分割難度；把焦點放在增強感興趣對象，縮小不相干圖像的干擾上。 圖像的大部

3、分信息都存在于圖像的邊緣中，主要表現(xiàn)為圖像局部特征的不連續(xù)性，即圖像中灰度變化比較劇烈的地方。因此，我們把邊緣定義為圖像中灰度發(fā)生急劇變化的區(qū)域邊界。 邊緣特點：沿邊緣的走向灰度變化平緩，垂直于邊緣走向的像素灰度變化劇烈 。 圖像的邊緣是圖像最基本也是最重要的特征之一。2 邊緣檢測 圖像邊緣：2.1 基本概念例圖像灰度剖面一階導數(shù)常見的邊緣二階導數(shù) Roberts算子 幾種常用的邊緣檢測微分算子， 0-110100-1模板 Prewitt算子 模板幾種常用的邊緣檢測微分算子， Sobel算子為： Py = (z7 + 2z8 + z9) - (z1 + 2z2 + z3) Px = (z3 +

4、 2z6 + z9) - (z1 + 2z4 + z7)梯度值：Roberts算子 Prewitt算子 Sobel算子-1-1400-100-1-1-18-1-1-1-1-1-1 LOG（Laplacian-Gauss）算子(或Marr) 將Gaussian濾波器和Laplacian邊緣檢測結(jié)合在一起，形成了LoG (Laplacian of Gaussian)算法。即先用高斯函數(shù)對圖像進行平滑，然后再用拉普拉斯算子進行運算，形成Laplacian-Gauss算法，它使用一個墨西哥草帽函數(shù)形式。，模板-20-1-10016-1-2-20-1-100-1000-2-1-1000LoG 函數(shù)的三維

5、曲線、橫截面 Canny（坎尼）算子 具體步驟：首先用2D高斯濾波模板進行卷積以平滑圖像；利用微分算子(如Roberts算子、Prewitt算子和Sobel算子等)，計算梯度的幅值和方向；對梯度幅值進行非極大值抑制。即遍歷圖像，若某個像素的灰度值與其梯度方向上前后兩個像素的灰度值相比不是最大，那么這個像素值置為0，即不是邊緣；使用雙閾值算法檢測和連接邊緣。即使用直方圖計算兩個閾值，凡是大于高閾值的一定是邊緣；凡是小于低閾值的一定不是邊緣。如果檢測結(jié)果大于低閾值但又小于高閾值，那就要看這個像素的鄰接像素中有沒有超過高閾值的邊緣像素，如果有，則該像素就是邊緣，否則就不是邊緣。， edg0.mVg=

6、edge(f,roberts);Vg=edge(f,sobel);Vg=edge(f,canny);Vg=edge(f,log,2);幾種常用邊緣檢測matlab 函數(shù)檢測邊緣：尋找零交叉點，檢測黑色和白色區(qū)域之間的過渡點LoG檢測結(jié)果Canny算子與LOG算子比較（a）原圖（b） LOG算子結(jié)果（c）Canny算子結(jié)果 由于噪聲的原因，邊緣算子得到的邊緣往往是孤立的或分段不連續(xù)的。且有些是真正的邊界象素，有些是噪聲點 ； 因此，邊檢測算法后面總要跟隨著連接過程和其它邊界檢測過程，用來歸整邊緣像素，使之成為有意義的邊； 目的是將邊緣象素連接起來組成區(qū)域的封閉邊界，使圖像中不同區(qū)域分開，以便下一

7、步分析。2.3 邊界跟蹤(boundary tracking)邊界跟蹤的目的： 邊界跟蹤也稱邊緣點連接，是指從梯度圖中一個邊界點出發(fā)，依次通過對前一個邊界點的考察而逐步確定出下一個新的邊界點，并將它們連接而逐步檢測出邊界的方法。 邊界跟蹤是基于梯度的圖像分割方法的基礎(chǔ)。 圖像的輪廓（邊界）跟蹤與邊緣檢測是密切相關(guān)的，因為輪廓跟蹤實質(zhì)上就是沿著圖像的外部邊緣“走”一圈。 邊界跟蹤基本概念：如何確定邊緣像素的相似性？ 邊緣像素梯度算子的響應強度（梯度值） 邊緣像素梯度算子的方向輪廓跟蹤的依據(jù)：邊界象素梯度的相似性 確定邊緣點的依據(jù) 輪廓跟蹤過程大致可分以下三步：(1) 確定輪廓跟蹤的起始邊界點。根

8、據(jù)算法的不同，選擇一個或多個邊緣點作為搜索的起始邊緣點；(2) 確定一種合適的搜索策略，在已發(fā)現(xiàn)的邊界點基礎(chǔ)上確定新的邊界點；(3) 制定出終止搜尋的準則(一般是將形成閉合邊界作為終止條件)，在滿足終止條件時結(jié)束搜尋。輪廓跟蹤過程： 跟蹤處理的分析方法： 利用邊緣像素梯度的相似性對做過邊檢測的圖象的每個點的特性進行分析分析在一個小的鄰域（33或55）中進行所有相似的點被連接，形成一個享有共同特性象素的邊界 用比較梯度值的幅度和梯度方向確定兩個點是否同屬一條邊。點(x,y)點 (x,y) 連接處理的分析方法：點(x,y)點 (x,y) 連接算法描述：1）設定A、E的閾值大小，確定鄰域的大小2）對

9、圖像上每一個像素的鄰域點進行分析， 判斷是否需要連接。3）記錄像素連接的情況，給不同的邊以不同的標記。4）最后，連接斷開的線段，刪除孤立線段。假設灰度圖像已經(jīng)完成梯度計算和二值化：(1) 發(fā)現(xiàn)像素從0開始變?yōu)?的像素時記為p0 ，存儲p0的坐標（i,j)值。(2)從像素(i,j-1)開始反時針方向研究8-鄰接像素，當?shù)谝淮纬霈F(xiàn)像素值為1的像素記為p1，也同樣存儲p1的坐標。(3)同上，反時針方向研究p1的8-鄰接像素，把最先發(fā)現(xiàn)像素值為1的像素記為p2 。(4)當pk= p0而且pk+1= p1時，跟蹤結(jié)束。 邊界跟蹤方法一：光柵掃描第一步，根據(jù)光柵掃描，發(fā)現(xiàn)灰度為1的像素p0。 第二步，反時

10、針方向研究像素p0的8-鄰接像素,由此發(fā)現(xiàn)像素p1。 反復以上操作，以p0, p1, pn的順序跟蹤8-鄰接的邊界像素。一直到pk= p0時終止搜索。00000010000000000000100101010110001000011010000000000000000101011000001001000001p0p1p2p3p4p5p6p7p8p9p10p11p12p13p14p15p16p17邊界跟蹤的順序示意 邊界跟蹤方法二PCPCCCCCCCPPPPPP3 閾值與圖像分割 3.1 閾值分割原理目標背景閾值分割是用一個或幾個閾值將圖像的灰度級分為幾個部分,認為屬于同一個部分的像素是屬于同一

11、個物體。閾值的選取是閾值分割方法中的關(guān)鍵技術(shù)。 閾值分割算法是區(qū)域分割算法中具有代表性的一類非常重要的分割算法。 以一定的圖像模型為依托，通過取閾值后得到的圖像，各個區(qū)域可以分離開。 最常用的圖像模型是假設圖由具有單峰灰度分布的目標和背景組成。目標背景 僅使用一個閾值分割的方法稱為單閾值分割方法 。 如果圖像中有多個灰度值不同的區(qū)域，那么可以選擇一系列的閾值以將每個像素分到合適的類別中去 ，這種用多個閾值分割的方法稱為多閾值分割方法。 當閾值T取決于空間坐標，閾值就是動態(tài)的或自適應的。3.2 閾值分割分類 多閾值的灰度直方圖 T2T1單閾值灰度直方圖 單閾值分割，多閾值分割，自適應閾值分割 單

12、閾值圖像分割 首先，確定一個合適的閾值T（閾值選定的好壞是此方法成敗的關(guān)鍵）；其次，將大于等于閾值的像素作為物體或背景，生成一個二值圖像。yuzhifenge.m例T=170T=170(加中值濾波）(a)(b)(c)(d)在圖像的閾值化處理過程中，選用不同的閾值其處理結(jié)果差異很大。閾值過大， 會提取多余的部分； 而閾值過小，又會丟失所需的部分。因此，閾值的選取非常重要。 不同閾值對閾值化結(jié)果的影響原始圖像閾值T=91閾值T=130閾值T=43yuzhifenge1.m閾值的選擇對于圖像分割結(jié)果至關(guān)重要。僅憑人 眼主觀上的感覺很難選擇到合適的閾值。四種比較經(jīng)典的閾值選取方法極小值點閾值選取方法最

13、優(yōu)閾值選取方法迭代閾值選取方法利用灰度統(tǒng)計直方圖的直方圖凹性分析的閾值選取方法。3.3 閾值選取方法 通過尋找直方圖的極小點確定分割閾值，在確定極小點過程中通常需要對直方圖進行平滑。 圖像的灰度直方圖是一種離散分布，其包絡曲線則是一條連續(xù)的曲線，求其包絡曲線h(z)極小值作為閾值。 實際圖像由于各種因素的影響，其灰度直方圖往往存在許多起伏，不經(jīng)預處理將會產(chǎn)生若干虛假的“谷” 。一般先對其進行平滑處理，然后再取包絡，這樣將在一定程度上消除虛假“谷”對分割閾值的影響。 極小值點閾值選取方法 極小值點閾值選取方法 在具體應用時，多使用高斯函數(shù)g(z,) 與直方圖的原始包絡函數(shù)h(z)相卷積而使包絡曲

14、線得到一定程度的平滑假設一幅圖像僅包含兩個主要的灰度級區(qū)域。令z表示灰度級值，則兩個灰度區(qū)域的直方圖可以看作它們概率密度函數(shù)(PDF)的估計p(z)； p(z)是兩個密度的和或混合。一個是圖像中亮區(qū)域的密度，另一個是暗區(qū)域的密度；如果p(z)已知或假設，則它能夠確定一個最佳閾值（具有最低的誤差）將圖像分割為兩個可區(qū)分的區(qū)域。 最佳閾值選取方法 p1(z)p2(z)假設概率密度函數(shù)p2(z)對應于背景的灰度級，而p1(z) 描述了圖像中目標的灰度級。則整體灰度級的混合概率密度函數(shù)可以表達成:這里P1和P2是分別是兩類像素出現(xiàn)的概率，并且滿足下列條件： p1(z)目標p2(z)背景p (z) 當我

15、們選取閾值T時，使得所有灰度值小于T的像素被認為是目標點，而所有灰度值大于T的像素可以被認為是背景點。此時，背景點誤判為目標點的概率為: 這表示在曲線p2(z)下方位于閾值左邊區(qū)域的面積。 將目標點誤判為背景點的概率為： p1(z)p2(z)目標背景 總的誤判概率為： 為了找到一個閾值T使得上述的誤判概率為最小，必須將E(T)對T求微分(應用萊布尼茲公式)，并令其結(jié)果等于零。由此可以得到如下的關(guān)系： 解出T，即為最佳閾值。 如果P1=P2，則最佳閾值位于曲線p1(z)和p2(z)的交點處。p1(z)p2(z) 迭代閾值選取方法 利用程序自動搜尋出比較合適的閾值。步驟為： 1）首先選取圖像灰度范

16、圍的中值作為初始估計值T；2）用T分割圖像。這樣便會生成兩組像素集合：G1由所有灰度值大于T的像素組成，而G2由所有灰度值小于或等于T的像素組成。3）對G1和G2中所有像素計算平均灰度值1和2。nk是灰度為k的像素點個數(shù)。 4）計算新的閾值：T= (1+2) /2。重復步驟（2）到（4），直到得到的T值之差小于一個事先定義的參數(shù)T0。yuzhifengediedai.mT=127.3984迭代法分割結(jié)果原圖迭代5次對于用單一全局閾值無法有效分割的直方圖，可以采用所謂基本自適應閾值進行分割。該類方法的基本步驟如下：1）將整幅圖像分成一系列的子圖像；2）做出每個子圖像的直方圖； 3）檢測各個子圖像

17、的直方圖是否為雙峰，如果是，則采用最佳閾值法確定一個閾值，否則就不進行處理。 基本自適應閾值解決的關(guān)鍵問題：如何將圖像進行細分和如何為得到的子圖像估計閾值一個全局閾值處理后的結(jié)果：人工設置直方圖的波谷為閾值分割為子圖像：4等分后再4等分自適應閾值處理的結(jié)果原圖基本自適應閾值舉例yuzhifengead.m原圖像自適應閾值分割結(jié)果Th=Th(x,y)4 基于區(qū)域的分割 基于區(qū)域的分割就是把具有某種相似性質(zhì)（可以是灰度、顏色、紋理等）的像素連通起來，形成圖像中的不同區(qū)域?；趨^(qū)域分割區(qū)域生長區(qū)域分裂區(qū)域合并 區(qū)域生長是一種根據(jù)事前定義的準則將像素或子區(qū)域聚合成更大區(qū)域的過程?；镜姆椒ㄊ且砸唤M“種

18、子”點開始將與種子性質(zhì)相似的相鄰像素附加到生長區(qū)域的種子上。7.4.1 區(qū)域生長 區(qū)域生長方法：1）確定區(qū)域的數(shù)目，也就是選擇一組能正確代表所需區(qū)域的生長起點，即種子，每個圖像區(qū)域至少要有一個種子。如最亮或最暗的點，或者是位于點簇中心的點。 2）選擇有意義的特征，也就是確定在生長過程中將相鄰區(qū)域像素包括進來依據(jù)的特征；3）確定生長規(guī)則，根據(jù)確定的生長規(guī)則將種子像素周圍鄰域中與種子像素有相同或相似性質(zhì)的像素合并到種子像素所在的區(qū)域中。將這些新像素當做新的種子像素繼續(xù)進行上面的過程，直到再沒有滿足條件的像素可被包括進來。這樣一個區(qū)域就長成了。以像素灰度為特征進行區(qū)域生長10475104770155

19、52056522564示例確定生長規(guī)則：如果像素與種子像素灰度值差小于閾值T，則將像素包括進種子像素所在的區(qū)域。要分割的圖像選擇種子像素：種子像素的選取可借助圖像的直方圖來進行，由直方圖可知具有灰度值為1和5的像素最多且處在聚類的中心，所以可各選一個具有聚類中心灰度值的像素作為種子。1047510477015552056522564示例生長規(guī)則：如果像素與種子像素灰度值差小于閾值T，則將像素包括進種子像素所在的區(qū)域。要分割的圖像1047510477015552056522564T=2分割1047510477015552056522564T=1分割151111111111555555555555

20、555111111155555555555閾值T的選擇非常重要生長規(guī)則: 灰度差Tregiongrow0.m示例clear all;close all;f=imread(1.jpg);f=rgb2gray(f);y,x=ginput(1); x=round(x); y=round(y); f1=double(f);S=f1(x,y); T=3;if numel(S)=1 SI=f=S; S1=S; else SI=bwmorph(S,shrink,Inf); J=find(SI); S1=f(J);. end TI=false(size(f); for K=1:length(S1) seedv

21、alue=S1(K); S=abs(f-seedvalue)=T; TI=TI|S; end g=bwlabel(imreconstruct(SI,TI);imshow(g) 優(yōu)缺點：這種方法簡單，但如果區(qū)域之間的邊緣灰度變化很平緩或邊緣交于一點時，如圖，兩個區(qū)域會合并起來。 一種解決方法：為消除這一點，在步驟搜索中不是比較相鄰像素灰度，而是比較已存在區(qū)域的像素灰度平均值與該區(qū)域鄰接的像素灰度值-質(zhì)心型區(qū)域生長。區(qū)域1區(qū)域2灰度平緩的邊緣 質(zhì)心型區(qū)域生長比較單個像素的特征與其相鄰區(qū)域的特征，若相似則將像素歸并到區(qū)域中。 操作步驟類似簡單區(qū)域生長法，唯一不同的是在前面閾值比較中，改為比較已存在區(qū)

22、域的像素灰度平均值與該像素灰度值。若差值小于閾值，則合并。 （a）原始圖像 （b）第一次生長結(jié)果 （c）第二次生長結(jié)果 （d）最終生長結(jié)果例子:T=2區(qū)域平均值8.25區(qū)域平均值7.83區(qū)域平均值7.574.2 區(qū)域分裂與合并 先將圖像分割成一系列任意不相交的區(qū)域，然后將他們進行合并或分裂得到各個區(qū)域。 在這類方法中，最常用的方法是四叉樹分解法. 四叉樹分解法 設R表示不具一致性的圖像區(qū)域。對R進行分割的一種方法是反復將分割得到的結(jié)果圖像再次分為四個區(qū)域，直到任何區(qū)域Ri達到一致性為止。RR1R2R3R4R11R12R13R14 如果僅使用分裂，最后得到的分割結(jié)果可能包含具有相同性質(zhì)的相鄰區(qū)域

23、。為此，可在分裂的同時進行區(qū)域合并。 合并規(guī)則： 只要兩個相鄰的區(qū)域Ri 、Rj，具有一致性，則可以將Ri和Rj進行合并。區(qū)域分裂與合并方法分割圖像圖示基于區(qū)域的分割是以直接尋找區(qū)域為基礎(chǔ)的分割技術(shù)。區(qū)域生長就是一種根據(jù)事先定義的準則將像素或者子區(qū)域聚合成更大區(qū)域的過程。 彩色圖像分割是數(shù)字圖像處理中的一種應用廣泛的技術(shù)。對彩色圖像的分割可以采取兩種方式，其一就是將彩色圖像的各個分量進行適當?shù)慕M合轉(zhuǎn)化為灰度圖像，然后利用對灰度圖像的分割方法進行分割；其二就是在彩色模型空間中直接進行圖像的分割。 基于形態(tài)學方法的圖像分割技術(shù)基本思想是用具有一定形態(tài)的結(jié)構(gòu)元素去量度和提取圖像中的對應形狀以達到對圖

24、像分析和識別的目的。 5 彩色圖像分割 彩色圖像分割與灰度圖像分割的算法相比，大部分算法在分割思想上是一致的，都是基于像素數(shù)值的相似性和空間的接近性，只是對像素屬性的考察以及特征提取等技術(shù)由一維空間轉(zhuǎn)向了高維空間。這是由于灰度圖像和彩色圖像存在一個主要的區(qū)別，即對于每一個像素的描述，前者是在一維亮度空間上，而后者是在三維顏色空間上。彩色圖像分割算法的關(guān)鍵在于如何利用豐富的彩色信息來達到分割的目的。 5.1 彩色圖像分割方法 彩色圖像分割方法分類基于邊緣檢測的方法基于區(qū)域的方法基于主動輪廓模型方法神經(jīng)網(wǎng)絡法其他技術(shù)方法。 彩色圖像分割可以采取兩種方式其一就是將彩色圖像的各個分量進行適當?shù)慕M合轉(zhuǎn)化

25、為灰度圖像，然后利用對灰度圖像的分割方法進行分割；其二就是在彩色模型空間中直接進行圖像的分割。 HSI彩色空間分割如果希望基于彩色分割一幅圖像，并且想在單獨的平面上執(zhí)行處理，會很自然地想到HSI空間。HSI空間在色調(diào)圖像中描述彩色是很方便的。其次在HSI空間進行彩色圖像分割，由于H、S和I三個分量是相互獨立的，所以有可能將這個3-D搜索的問題轉(zhuǎn)化為3個1-D搜索。5.2 彩色圖像分割策略 基于色調(diào)（H）直方圖分割算法色調(diào)是與混合光譜中主要光的波長相聯(lián)系的，或者說觀察者感覺到的主要顏色，反映顏色的種類，決定顏色的基本特性。如果以顏色作為主要分割依據(jù)，那么色調(diào)H具有單調(diào)唯一的特性。色調(diào)值H從0到3

26、60的變化范圍正好對應可見光從紅到紫的所有顏色。0o120o240o為此，可采用基于色調(diào)H直方圖統(tǒng)計的閾值化法對圖像進行分割。 基于色調(diào)（H）直方圖分割算法一般來說，某一特征顏色物體，其H值分布是在一個區(qū)域內(nèi)的，為此可選兩個閾值H1和H2，有H1HCH2將該顏色界定。但是，基于色調(diào)H直方圖統(tǒng)計的閾值化法對圖像進行分割方法僅僅利用了色調(diào)值，而沒有考慮光強和飽和度等對顏色的影響，對于原始圖像中顏色數(shù)較少，目標顏色單純，且波長分布相對分散的情況，可以得到較好的結(jié)果。當圖像中顏色數(shù)較多，且顏色比較接近，相似的圖像情況，很難得到較好的效果。如果閾值化處理只是在單個顏色分量上進行,則由于忽略了3個顏色分量

27、間的相關(guān)性,因此提取區(qū)域不能同時考慮3個顏色分量的信息。若能夠找到一條直線,使得投影在其上的3維空間的點能夠很好地分開,這樣既能對顏色空間進行降維處理,又可以同時利用3 個顏色分量的信息。基于色調(diào)直方圖分割算法的改進：在實際情況下，除了色度H外，飽和度S、光強I也是與物體呈現(xiàn)顏色相關(guān)的信息。飽和度S，光強I在人對顏色的感覺上起著重要的作用，很少有不同的物體具有相同的色度和飽和度。色調(diào)相同的物體，在飽和度和光強上也會有很大的區(qū)別。因此有必要構(gòu)造一種一維特征標量，包含更多的顏色信息，以改善顏色分割的效果，即一維特征標量C=w1H+w2S+w3I稱為基于一維特征標量C的閾值分割算法。 基于一維特征標

28、量C的閾值分割算法 基于紋理和神經(jīng)網(wǎng)絡的彩色圖像分割 該方法將彩色圖像由RGB空間轉(zhuǎn)換為HSI空間，采用彩色圖像的亮度計算分數(shù)維、多重分形廣義維數(shù)譜以及空隙特征等參數(shù)作為紋理特征，加上歸一化的色度和飽和度，這些參數(shù)作為分類特征，以BP神經(jīng)網(wǎng)絡作為分類器的彩色紋理圖像分割方法。這種方法不僅對由于亮度差異而形成彩色紋理圖像有效，對于亮度基本一致而在色彩上呈現(xiàn)差異的紋理圖像依然有效。 RGB空間圖像分割給定一個感興趣彩色的有代表性的彩色點樣品集，可得到一個彩色“平均”估計，這種彩色是我們希望分割的彩色。令這個平均彩色用RGB向量a來表示。分割的目標是對給定圖像中每一個RGB像素進行分類，因為在確定的

29、范圍會有某種顏色或者沒有這種顏色。為了進行這一分割，進行一個相似性度量是必要的。最簡單的度量之一是歐氏距離。令z代表RGB空間中的任意點，如果它們之間的距離小于特定的閾值D0，我們說z與a是相似的，z和a間的歐氏距離由下式給出： D(z，a)D0的點的軌道是半徑D0為的實心球(圖a)。包含在球內(nèi)部和表面上的點符合特定的彩色準則。 RGBRGBRGB(a)(b)(c)RGB空間圖像分割Colorseg1.m給定一個感興趣彩色的有代表性的彩色點樣品集，根據(jù)歐氏距離進行圖像分割。 習題1、解釋概念：圖像分割、區(qū)域生長、閾值分割2、簡述題（1）結(jié)合具體例子談談閾值分割的基本原理和選取閾值的方法（2）結(jié)

30、合具體例子談談利用區(qū)域生長方法實現(xiàn)圖像分割的基本原理和步驟?；趫D論的圖像分割(Graph-Cut) 2014.9于深圳The st-Mincut ProblemSourceSinkv1v2259421Graph (V, E, C)Vertices V = v1, v2 . vnEdges E = (v1, v2) .Costs C = c(1, 2) .The st-Mincut ProblemSourceSinkv1v2259421What is a st-cut?The st-Mincut ProblemSourceSinkv1v2259421What is a st-cut?An st

31、-cut (S,T) divides the nodes between source and sink.What is the cost of a st-cut?Sum of cost of all edges going from S to T5 + 2 + 9 = 16The st-Mincut ProblemWhat is a st-cut?An st-cut (S,T) divides the nodes between source and sink.What is the cost of a st-cut?Sum of cost of all edges going from S

32、 to TWhat is the st-mincut?st-cut with the minimum costSourceSinkv1v22594212 + 1 + 4 = 7How to compute the st-mincut?SourceSinkv1v2259421Solve the dual maximum flow problemIn every network, the maximum flow equals the cost of the st-mincutMin-cutMax-flow TheoremCompute the maximum flow between Sourc

33、e and SinkConstraints Edges: Flow Capacity Nodes: Flow in = Flow outMaxflow AlgorithmsAugmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundSourceSinkv1v2259421Algorithms assume non-negative ca

34、pacityFlow = 0Maxflow AlgorithmsAugmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundSourceSinkv1v2259421Algorithms assume non-negative capacityFlow = 0Maxflow AlgorithmsAugmenting Path Based

35、AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundSourceSinkv1v22-25-29421Algorithms assume non-negative capacityFlow = 0 + 2Maxflow AlgorithmsSourceSinkv1v2039421Augmenting Path Based AlgorithmsFind path from s

36、ource to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 2Maxflow AlgorithmsSourceSinkv1v2039421Augmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possi

37、ble flow through this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 2Maxflow AlgorithmsSourceSinkv1v2039421Augmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be

38、foundAlgorithms assume non-negative capacityFlow = 2Maxflow AlgorithmsSourceSinkv1v2035021Augmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 2 +

39、 4Maxflow AlgorithmsSourceSinkv1v2035021Augmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 6Maxflow AlgorithmsSourceSinkv1v2035021Augmenting Pat

40、h Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 6Maxflow AlgorithmsSourceSinkv1v202402+11-1Augmenting Path Based AlgorithmsFind path from source to sink wi

41、th positive capacityPush maximum possible flow through this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 6 + 1Maxflow AlgorithmsSourceSinkv1v2024030Augmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow thr

42、ough this pathRepeat until no path can be foundAlgorithms assume non-negative capacityFlow = 7Maxflow AlgorithmsSourceSinkv1v2024030Augmenting Path Based AlgorithmsFind path from source to sink with positive capacityPush maximum possible flow through this pathRepeat until no path can be foundAlgorit

43、hms assume non-negative capacityFlow = 7v0v5v4v3v1v2vn(0,10)(0,4)(0,5)(0,5)(0,5)(0,6)(0,10)(0,6)(0,3)(0,3)(0,3)(0,2)(0,3)(0,4)例9-14（流值，容量）v0v5v4v3v1v2vn(6,10)(0,4)(0,5)(0,5)(0,5)(6,6)(0,10)(6,6)(0,3)(0,3)(0,3)(0,2)(0,3)(0,4)例增流路：v0v1v2vn增流值=6Flow = 6v0v5v4v3v1v2vn(6,10)(4,4)(0,5)(0,5)(4,5)(6,6)(4,10

44、)(6,6)(0,3)(0,3)(0,3)(0,2)(0,3)(0,4)例增流路：v0v2V4vn增流值=4Flow = 10v0v5v4v3v1v2vn(6,10)(4,4)(5,5)(5,5)(4,5)(6,6)(4,10)(6,6)(0,3)(0,3)(0,3)(0,2)(0,3)(0,4)例增流路：v0v3vn增流值=4Flow = 15v0v5v4v3v1v2vn(9,10)(4,4)(5,5)(5,5)(4,5)(6,6)(7,10)(6,6)(3,3)(0,3)(3,3)(0,2)(0,3)(0,4)例增流路：v0v1v5v4vn增流值=3Flow = 18 判斷此時的流是否是最

45、大流，用定理尋找最小截集。v0v5v4v3v1v2vn(9,10)(4,4)(5,5)(5,5)(4,5)(6,6)(7,10)(6,6)(3,3)(0,3)(3,3)(0,2)(0,3)(0,4)f =18SS截量=5+3+4+6=18兩者相等為最大流v0v5v4v3v1v2vn(9,10)(4,4)(5,5)(5,5)(4,5)(6,6)(9,10)(6,6)(3,3)(0,3)(3,3)(0,2)(0,3)(0,4)f =18SS截量=5+3+4+6=18兩者相等為最大流或History of Maxflow AlgorithmsSlide credit: Andrew GoldbergAugmenting Path and Push-Relabeln: #nodesm: #edg