圖像分析與識別課件5

1、123在對處理后的圖像數(shù)據(jù)進行分析之前，圖像分割是最重要的步驟之一。圖像分割的主要目標是將圖像劃分為與其中含有的真實世界的物體或區(qū)域有強相關(guān)性的組成部分。4我們可以將目標定位于完全分割，其結(jié)果是一組唯一對應(yīng)于輸入圖像中物體的互不相交的區(qū)域。我們也可以將目標定位于部分分割，其中的區(qū)域并不直接對應(yīng)于圖像物體。5為了獲得完全分割，必須與使用有關(guān)問題領(lǐng)域的專門知識相協(xié)作。 如果目標是部分分割，則圖像被劃分為分開的同態(tài)的區(qū)域。這樣部分分割的圖像必須經(jīng)過進一步處理，并借助高層知識找到最終的圖像分割。6圖像分割方法可以劃分為三組：1.基于圖像或圖像部分的全局知識，這種知識一般由圖像直方圖來表達；2.基于邊緣

2、的分割；3.基于區(qū)域的分割。78灰度級閾值化是最簡單的分割處理。很多物體或圖像區(qū)域表征為不變的反射率或其表面光的吸收率，因此可以確定一個亮度常量即閾值來分割物體和背景。閾值化計算代價小、速度快。9圖像R的完全分割是區(qū)域R1,RS的有限集合：jiRRRRjiSii0110算法：單閾值化單閾值化是輸入圖像f到輸出圖像g的如下變換，對于屬于物體的像素g(i,j)=0，對于屬于背景的像素g(i,j)=255（或反之亦然）。時當時當TjifTjifjig),(0),(255),(11原始圖像直方圖閾值T=6012算法：帶閾值化將圖像分割為具有一個集合D內(nèi)的灰度的區(qū)域而其它作為背景（帶閾值化）。這種閾值化

3、定義還可以用作邊界檢測子。 其它時當255),(0),(Djifjig13其它當25511055),(0),(jifjig14算法：半閾值化半閾值化的目的是屏蔽掉圖像背景，留下物體部分的灰度信息。 時當時當TjifTjifjifjig),(0),(),(),(15原始圖像直方圖閾值T=12516多閾值的閾值化，其處理后的結(jié)果圖像不再是二值的，而是由一個有限的灰度值集合組成的圖像。算法：多閾值的閾值化其它時當時當時當時當0),(),(3),(2),(1),(321nDjifnDjifDjifDjifjig17如果物體彼此不接觸，且它們的灰度與背景明顯地不同，則閾值化就是一個合適的分割方法。選擇正

4、確的閾值是閾值分割成功的關(guān)鍵，這種選擇可以通過人為交互的方式確定，也可以根據(jù)某個閾值檢測方法來確定。18全局閾值是根據(jù)整幅圖像圖像確定的。局部閾值是與位置相關(guān)的。使用局部閾值（自適應(yīng)閾值）進行分割可以產(chǎn)生較好的結(jié)果。這時的閾值是局部圖像特征的函數(shù)，在圖像范圍內(nèi)是變化的。19a)原始圖像b)經(jīng)全局閾值處理后的結(jié)果c)被細分為單個子圖的圖像d)經(jīng)自適應(yīng)處理后得到的結(jié)果20如果知道經(jīng)過分割后的圖像的某種性質(zhì)，就可以簡化閾值選擇的任務(wù)。因為閾值可以按照確保該性質(zhì)得以滿足的條件來選擇。21例如，當我們知道文本字符覆蓋1p的紙張面積時的印刷文本頁。使用這個有關(guān)紙張面積與字符面積的比率的先驗信息，很容易選擇

5、一個閾值T（基于圖像的直方圖）使得1p的圖像面積具有比T小的灰度值，而其余的面積具有比T大的灰度值。 22 如果圖像由有別于背景灰度值的具有近似相同灰度的物體所組成，所產(chǎn)生的直方圖是二模態(tài)的。物體像素構(gòu)成其中的一個峰，而背景像素構(gòu)成另一個峰，兩個峰之間的灰度數(shù)值可能是物體和背景間的邊界造成的。 2324二模態(tài)閾值檢測算法通常首先要尋找最大的局部極大值，然后取它們之間的極小值作為閾值。為了避免檢測到屬于同一全局極大值的兩個局部極大值，通常要求這兩個極大值對應(yīng)的灰度之間的間隔不小于一個最小值。25閾值化是圖像分割中非常流行的工具。對于閾值分割來說，一般都具有高處理速度，因此可以容易地實現(xiàn)實時圖像閾

6、值化處理。 26將圖像的直方圖用兩個或更多個正態(tài)分布的概率密度函數(shù)來近似的方法，稱之為最優(yōu)閾值化的方法。閾值取為離對應(yīng)于兩個或更多個正態(tài)分布最大值之間的最小概率處最近的灰度值，其結(jié)果是具有最小錯誤的分割（被錯誤分割的像素數(shù)目最?。?7 a)背景和物體的概率分布b)對應(yīng)的直方圖和最優(yōu)閾值 28這些方法的難點在于估計正態(tài)分布參數(shù)以及這些分布被當作正態(tài)分布所具有的不確定性。如下算法展示了這種方法的基本原理，這種方法假設(shè)圖像中出現(xiàn)兩種主要的灰度區(qū)域。29算法：迭代的(最優(yōu)的)閾值選擇 1.假設(shè)沒有有關(guān)物體確切位置的知識，作為第一步近似，考慮圖像四角含有背景像素而其它部分含有物體像素。 2.在第t步，

7、分別計算背景和物體的灰度平均值 和 ，其中在第t步將圖像分割為背景和物體的閾值是 ,它是在前一步確定的。 tBtOtT303.設(shè) 提供了一個更新了的背景與物體的區(qū)分。xelsobjects_pi#),(_pixelsbackground#),(objects),(background),(jifjifjijitOtB2)1(tOtBtT)1( tT314.如果 則停止，否則返回第2步。ttTT )1(32(a)3D-weighted MR腦圖像的全局直方圖(b)擬合的高斯分布(c)對應(yīng)于白質(zhì)(WM)，灰質(zhì)(GM)，腦脊髓流(CSF)的三個分布33(a)原始圖像(b)灰質(zhì)(c)白質(zhì)(d)腦脊髓流

8、(a) (b) (c) (d) 34許多實際的分割問題需要比單一譜段所含的更多的信息。例如，彩色圖像、多光譜遙感圖像、氣象衛(wèi)星圖像。 一種分割方法是在每個譜段中獨立地確定閾值，然后綜合形成單一的分割圖像。35算法：遞歸的多光譜閾值化1.將整個圖像初始化為單個區(qū)域；2.給每個譜段計算一個平滑的直方圖。在每個直方圖中找到一個最顯著的峰，確定兩個閾值分別對應(yīng)于該峰兩側(cè)的局部最小值； 363.根據(jù)這些閾值將各個譜段的每個區(qū)域分割為子區(qū)域；4.將各個譜段的每個分割投影到多光譜分割中，見下圖。下一步處理的區(qū)域是這些在多光譜圖像中的區(qū)域；375.對于圖像的每個區(qū)域重復(fù)第二步，直至每個區(qū)域的直方圖只含有一個顯

9、著的峰。38 (a) 譜段1閾值化 (b) 譜段2閾值化 (c) 多光譜分割39分層數(shù)據(jù)結(jié)構(gòu)下的閾值化的目的在于在低分辨率圖像中檢測區(qū)域的出現(xiàn)，在高層直至完全分辨率下給出更精確的區(qū)域。 從最低分辨率圖像（金字塔的最高層）開始進行分割。為了得到更好的分割精度，離邊界近的像素被再次分割為物體或者背景區(qū)域。40這種精度增長對于金字塔層重復(fù)進行，直至在完全分辨率層得到最終的分割。 這種方法的優(yōu)點是圖像噪聲對分割結(jié)果的影響明顯地小得多。41這是因為在較低分辨率下圖像的分割是基于平滑的圖像數(shù)據(jù)，其中噪聲被抑制。由平滑數(shù)據(jù)分割造成的不精確邊界，經(jīng)過在邊界附近利用高一層分辨率的數(shù)據(jù)再次分割而得以矯正。42a)

10、金字塔第n層，分割為物體和背景。b)金字塔第n+1層，為了得到更好的精度必須再次閾值化。4344基于邊緣的分割代表了一大類基于圖像邊緣信息的方法，它是最早的分割方法之一，且現(xiàn)在仍然是非常重要的。 基于邊緣的分割依賴于由邊緣檢測算子找到的圖像邊緣，這些邊緣標示出了圖像在灰度、色彩、紋理等方面不連續(xù)的位置。 45我們在第四章講述了各種邊緣檢測算子，但是由這些邊緣檢測算子得到的圖像結(jié)果并不能用作分割結(jié)果。必須采用后續(xù)的處理將邊緣合并為邊緣鏈，使它與圖像中的邊界對應(yīng)得更好?；蛘咧辽賹⒕植窟吘壘酆系狡饋?，得到對應(yīng)于物體部分邊界的邊緣鏈。46在分割處理中可獲得的先驗信息越多，能達到的分割結(jié)果就越好。如果能

11、夠獲得有關(guān)期望結(jié)果的大量先驗信息，邊界形狀就被詳細說明了，分割必須滿足所有這些說明。47如果關(guān)于邊界的先驗信息很少，分割方法就必須考慮更多的局部圖像信息。如果可獲得的先驗信息很少，就不能用于評價分割結(jié)果的信度，因此就沒有反饋矯正分割結(jié)果的基礎(chǔ)。48基于邊緣分割的最常見的問題是在沒有邊界的地方出現(xiàn)了邊緣以及在實際存在邊界的地方?jīng)]有出現(xiàn)邊緣，這是由圖像噪聲或圖像中的不當?shù)男畔⒃斐傻?。顯然這些情況對分割結(jié)果有負面影響。 49在邊緣圖像中小的邊緣值對應(yīng)于由量化噪聲、弱且不規(guī)則照明等引起的非顯著的灰度變化。可以對邊緣圖像做簡單的閾值化處理排除這些小的數(shù)值。這種方法是基于圖像的邊緣幅度由合適的閾值處理實現(xiàn)

12、，選擇合適的全局閾值一般是困難的。50q第四章講述的簡單邊緣檢測算子的一個問題是使邊界變粗。如果邊緣帶有方向信息，則可以通過施加某種形式的非最大抑制來抑制單個邊界鄰域內(nèi)的多個響應(yīng)，以實現(xiàn)部分矯正。q圖像中由噪聲產(chǎn)生的邊緣可以通過滯后過濾來去除。51算法：有方向的邊緣數(shù)據(jù)的非最大抑制 1.根據(jù)8-鄰接將邊緣方向量化為8個方向；2.對于每個非0幅值的像素，考察由邊緣方向指出的兩個鄰接像素（參見下圖）；3.如果兩個鄰接像素的幅值都超過當前考察像素的幅值，將它們標記出來刪除；4.當所有的像素都考察過后，重新掃描圖像，以0抹去所有的標記過的像素。52 （由邊緣方向確定的） 鄰接像素圖像中的邊界考察像素5

13、3算法：邊緣檢測算子輸出的滯后過濾1.假設(shè)超過t1的邊緣幅值為邊緣，小于t0為噪聲；2.將幅值超過t1的所有邊緣標注為正確；3.掃描幅值在區(qū)間t0, t1內(nèi)的所有像素；4.如果該像素與已經(jīng)標注為邊界的另一個像素接壤，則將它也標記出來?！敖尤馈笨梢远x為4-鄰接的或8-鄰接的；5.從第2步重復(fù)直至穩(wěn)定。54(a)非最大抑制的邊緣圖像。 (b)作用于(a)的滯后處理，高閾值是70，低閾值是10。55邊緣圖像閾值化得到的邊界受圖像噪聲的影響很大，經(jīng)常會遺漏重要的部分。在它們相互鄰域的上下文中考慮邊緣的性質(zhì)能夠增加結(jié)果圖像的品質(zhì)。 這種評價是基于指定局部鄰域內(nèi)的邊緣強度進行的，每個邊緣的信度或者被增加

14、或者被減小。56在兩個強邊緣間的一個弱邊緣構(gòu)成了一個上下文的例子；這個位于其間的弱邊緣有很高的可能性屬于結(jié)果邊界的一部分。如果一個邊緣置身于沒有支持的上下文中，它可能并不是任何邊界的一部分。邊緣松弛目的在于建立連續(xù)的邊界。 57中心邊緣e在每個端點處有一個頂點，兩個頂點處都有三種可能的邊界伸展方式。設(shè)不計邊緣e，以從頂點出發(fā)的邊緣數(shù)來評價每個頂點，稱這個數(shù)為頂點的類型。這樣，邊緣e的類型可以用描述每個頂點邊緣模式的數(shù)對i-j來表示。58環(huán)繞中心邊緣e的裂縫邊緣 59邊緣模式及相應(yīng)的邊緣類型60q0-0孤立邊緣：對邊緣信度產(chǎn)生負面影響。q0-1不確定：弱正面，或?qū)吘壭哦葻o影響。q0-2，0-3

15、死結(jié)：對邊緣信度產(chǎn)生負面影響。q1-1連續(xù)：對邊緣信度產(chǎn)生強正面影響。q1-2，l-3連續(xù)至邊界交叉：對邊緣信度產(chǎn)生中等正面影響。q2-2，2-3，3-3邊界間架橋：分割中不是必需的，對邊緣信度沒有影響。61邊緣松弛可以根據(jù)給定的上下文規(guī)則來定義，它可以看作是一個產(chǎn)生式系統(tǒng)。邊緣松弛是一個迭代的方法，其中邊緣的信度或者收斂到0（邊緣終結(jié)）或者收斂到1（邊緣形成邊界）。 62算法：邊緣松弛法1.對圖像中的所有裂縫邊緣計算一個信度c(1)(e)。2.在每個邊緣的鄰域內(nèi)，根據(jù)邊緣信度c(k)(e)確定其邊緣類型。3.根據(jù)每個邊緣的類型和前面的信度c(k)(e)，更新其信度c(k+1)(e)。4.如果

16、所有的邊緣信度都收斂到了0或者1，則停止。否則重復(fù)步驟2和3。63a)10步迭代后的邊界b)細化后邊界c)100步迭代后的細化邊界d)(c)重疊在原圖上64如果區(qū)域的邊界未知，但區(qū)域本身在圖像中已經(jīng)定義了，那么邊界可以唯一地被檢測出來。首先，我們假設(shè)含有區(qū)域的圖像或者是二值的或者區(qū)域已經(jīng)被標注出來了。65第一個目標是確定區(qū)域內(nèi)邊界。正如以前的定義，區(qū)域內(nèi)邊界是區(qū)域的一個子集。相反地，外邊界不是區(qū)域的一個子集。 66算法：內(nèi)邊界跟蹤1.從左上方開始搜索圖像直至找到一個新區(qū)域的一個像素，則該像素P0是這個新區(qū)域的所有像素中具有最小行數(shù)值的最小的列數(shù)的像素。像素P0是區(qū)域邊界的起始像素。定義一個變量

17、dir，存儲從前一個邊界元素到當前邊界元素沿著邊界的前一個移動方向。設(shè)置： (a) 當按照4-鄰接檢測邊界時 dir=3。 (b) 當按照8-鄰接檢測邊界時 dir=7。672.按照逆時針方向搜索當前像素的33鄰域，從以下的方向開始搜索鄰域。 (a) 取(dir+3)除以4的余數(shù)。 (b) 取(dir+7)除以8的余數(shù)，當dir是偶數(shù)時； 取(dir+6)除以8的余數(shù)，當dir是奇數(shù)時。 找到的第一個與當前像素值相同的像素是一個新的邊界元素Pn。更新dir的數(shù)值。 683.如果當前的邊界元素Pn等于第二個邊界元素P1，而且前一個邊界元素Pn-1等于P0，則停止。否則重復(fù)第2步。4.檢測到的內(nèi)邊

18、界由像素P0, , Pn-2構(gòu)成。 69內(nèi)邊界跟蹤的例子(a)4-鄰接方向符號(b)8-鄰接方向符號(c)4-鄰接中搜索順序(d)8-鄰接中搜索順序(e)8-鄰接中搜索順序(f)在8-鄰接中的邊界跟蹤701.根據(jù)4-鄰接跟蹤區(qū)域內(nèi)邊界直至完成。2.外邊界由所有的在搜索過程中測試過的非區(qū)域像素組成，如果某些像素被測試超過一次，它們就被在外邊界上列出超過一次。 算法：外邊界跟蹤71外邊界跟蹤：注意某些像素被列出幾次72內(nèi)邊界總是區(qū)域的一部分，而外邊界不是。因此，如果兩個區(qū)域相鄰，它們決不會有共同的邊界，這在區(qū)域描述、區(qū)域歸并等較高層的處理中會引起困難。擴展邊界定義的優(yōu)點是它定義了相鄰區(qū)域的單一的共

19、同邊界，可以用標準的像素坐標來標識。73 (a) 內(nèi)邊界 (b) 外邊界 (c) 擴展邊界741.按照標準的方法定義一個擴展邊界的起始像素（按照從左到右、從上到下一行一行地搜索圖像的方式找到第一個區(qū)域像素）。2.從起始像素沿著跟蹤邊界的第一個移動方向依賴于背景和區(qū)域點的局部結(jié)構(gòu)以及通向當前像素的方向。算法：擴展邊界跟蹤 753.按照下圖所示跟蹤擴展邊界時所有可能出現(xiàn)的12種情況的查找表跟蹤擴展邊界，直至得到一個封閉的擴展邊界。76q當前位置是中心像素。q下一步的移動方向依賴于背景和區(qū)域點的局部結(jié)構(gòu)以及通向當前像素的方向77如果要在沒有定義區(qū)域的灰度圖像中跟蹤邊界的話，就會遇到更為困難的情況。邊

20、界跟蹤應(yīng)該從作為邊界元素概率高的像素開始，把在最有可能的方向上的下一個元素加入。通常需要計算在可能邊界延續(xù)像素處的邊緣梯度的幅值和方向。78算法：灰度圖像中的邊界跟蹤 1.假設(shè)一直到邊界元素xi的邊界已經(jīng)確定。2.定義元素xj是在方向(xi)上與xi鄰接的像素。如果在xj處的梯度幅值比事先設(shè)置的閾值大，則把xj作為一個邊界元素；回到第1步。否則繼續(xù)到第3步。 793.計算像素xj的33鄰域的平均灰度值。將結(jié)果與某個事先設(shè)置的灰度值做比較，確定xj是在區(qū)域內(nèi)還是在區(qū)域外。繼續(xù)到第4步。804.根據(jù)第3步的結(jié)果確定方向選擇中的符號，考察相應(yīng)方向(xi)/4的xi的鄰接像素xk，以便延續(xù)邊界跟蹤。如

21、果找到了邊界延續(xù)，xk就是一個新的邊界元素，返回第1步。如果xk不是一個邊界元素，則從另一個有希望的像素開始跟蹤邊界。81只要有額外的邊界檢測知識，我們就應(yīng)該利用。利用先驗知識的一個例子是盡管我們不知道確切的邊界位置，但是我們知道邊界的起點和終點。 82圖是由一組節(jié)點ni和節(jié)點間的弧(ni,nj)構(gòu)成的一種普通結(jié)構(gòu)。我們考慮有方向的數(shù)值加權(quán)的弧，這些權(quán)稱為費用。邊界檢測過程被轉(zhuǎn)換為在加權(quán)圖中搜索最優(yōu)路徑的問題，目標是找到連接兩個指定節(jié)點即起點和終點的最好路徑。83假設(shè)在邊緣圖像中，既有邊緣幅度s(x)也有邊緣方向(x)的信息。每個圖像像素對應(yīng)于一個以值s(x)加權(quán)的圖節(jié)點。如果邊緣方向(xi)

22、和(xj)與局部邊界方向一致的話，對應(yīng)于8-鄰接像素xi和xj的兩個節(jié)點ni和nj就用弧連接起來。84我們可以用如下的規(guī)則建立圖：要連接代表像素xi的節(jié)點ni和代表像素xj的節(jié)點nj，像素xj必須是xi在方向d(xi)-/4， (xi)+/4內(nèi)的三個存在的鄰接點之一。85進一步，s(xi)和s(xj)必須比閾值T大，其中T是某個事先指定的反映邊緣顯著性的閾值。另一個常用的要求是只有當邊緣方向的差別小于2時才連接兩個節(jié)點。86 a)超過邊緣幅值閾值的像素的邊緣方向b)對應(yīng)的方向圖(a)(b)87設(shè)xA是開始的邊界元素，xB是結(jié)束的邊界元素。為了在區(qū)域邊界檢測中使用圖搜索技術(shù)，必須首先定義有向加權(quán)

23、圖的擴展方法。還必須定義一個費用函數(shù)f(xi)作為通過中間節(jié)點ni（像素xi）的節(jié)點nA和nB（像素xA和xB）間路徑的費用估計。88費用函數(shù)f(xi)典型地由兩部分組成，在開始的邊界元素xA和xi之間的最小路徑費用的估計g(xi)，以及在xi和結(jié)束的邊界元素xB之間的最小路徑費h(xi)。 從開始節(jié)點到節(jié)點ni的路徑的費用g(xi)一般是路徑中弧或節(jié)點費用的和。89費用函數(shù)相對于路徑的長度必須是可分離的和單調(diào)的，因此每個弧的局部費用必須是非負的。滿足給定條件的的g(xi)一個簡單例子是考慮從xA到xi的路徑距離。h(xi)的估計可以是從xi到xB的邊界的長度。90這有利于優(yōu)先選擇xA和xB間

24、較短的邊界作為費用低的路徑。如下的圖搜索算法（Nilsson的A-算法）可以用于邊界檢測。91用于邊界檢測的圖搜索算法（Nilsson的A-算法）1.展開起始節(jié)點nA，將其所有的后繼放入OPEN表中并帶有指向起始節(jié)點nA的指針。計算每個展開節(jié)點的費用函數(shù)f。2.如果OPEN表是空的，則失敗。確定OPEN表中具有最小費用f(ni)的節(jié)點ni，將它從表中除去。如果ni=nB，則通過指針回溯得到最優(yōu)路徑，然后停止。923.如果第2步?jīng)]有選擇停止，展開得到的節(jié)點ni，將其后繼放入OPEN表中并帶有指向ni的指針。計算它們的費用f，返回第2步。 93q當前在OPEN表中的節(jié)點加了陰影。q其中最小費用的節(jié)

25、點有陰影且輪廓加粗了。q最優(yōu)路徑由回溯定義94如果對于圖的建立和搜索沒有施加額外的限制，這一過程很容易會造成死循環(huán)。為了防止這種行為的發(fā)生，將已經(jīng)訪問過的且以前曾被放入OPEN表中的節(jié)點不再放入OPEN表中。一種解決死循環(huán)問題的簡單方法是不允許反向搜索。 95對于圖搜索邊界檢測，一個關(guān)鍵的問題是如何選擇評價費用的函數(shù)。一個好的費用函數(shù)應(yīng)該具有多數(shù)邊緣檢測問題共有的成分，也要有與具體應(yīng)用有關(guān)的特殊項。 一些通?？捎玫馁M用函數(shù)有： 961.形成邊界的邊緣強度：形成邊界的邊緣強度越強，邊界的概率就越高。這一啟發(fā)式是很自然的，并且?guī)缀蹩偸墙o出好的結(jié)果。注意如果邊界由強邊緣組成，邊界的費用就小。 972

26、.邊界曲率：有時要優(yōu)先選擇具有小曲率的邊界。如果是這種情況，整個邊界的曲率可以用局部曲率增量的單調(diào)函數(shù)來評價。 983.與一個近似邊界位置的接近度：如果知道一個近似邊界位置，支持與已知的近似相近的路徑是自然的。當一個邊界元素包含于邊界時，可以用與近似邊界的距離來加權(quán)邊界元素值。994.估計到目標（結(jié)束點）的距離：如果邊界是相當直的，優(yōu)先支持與目標節(jié)點接近的那些節(jié)點的展開是自然的。 100由于邊界檢測應(yīng)用的范圍相當廣泛，所以費用函數(shù)需要做些修改使其與特殊的任務(wù)相關(guān)。設(shè)計邊界檢測費用函數(shù)時常需要充分的經(jīng)驗和實驗。 101動態(tài)規(guī)劃是基于最優(yōu)化原理的一種最優(yōu)化方法。它搜索函數(shù)的最優(yōu)值，該函數(shù)的所有變量

27、不是同時內(nèi)在關(guān)聯(lián)的?？紤]如下的簡單邊界跟蹤問題。目標是找到存在于可能的起點A，B，C和可能的終點G，H，I之間的一個最好的路徑（最小費用）。102a)邊緣圖像；b)對應(yīng)的圖，分配了部分弧費用；c)從任何起點到E的可能路徑，A-E是最優(yōu)的；d)到節(jié)點D，E，F(xiàn)的最優(yōu)部分路徑；e)到節(jié)點G，H，I的最優(yōu)部分路徑；f)從H的回溯定義了最優(yōu)邊界103a)展開圖的第一層b)第2步c)第3步，標注出了最后層的最小費用節(jié)點d)最優(yōu)路徑由回溯定義104以上例子只有三層，如果圖具有更多的層，重復(fù)這一過程直至達到一個終點。每次重復(fù)由一個優(yōu)化組成：其中 是分配給節(jié)點 的最新費用， 是節(jié)點 和 之間的部分路徑費用。)

28、,()(min)(1kigxCxCmmiimk)(1mkxC1mkx),( kigmmix1mkx105 對于完全的優(yōu)化問題，有：其中 是終點節(jié)點，M是起始點和終止點間的數(shù)目。 表示在第一和最后M圖層間路徑的費用。)(min),(min, 121MknkMxCxxxCMkx),(21MxxxC106應(yīng)用動態(tài)規(guī)劃方法必須建立完整的圖，這可以按照前面章節(jié)中給出的一般規(guī)則來建立。目標函是可分離的、單調(diào)的（如同在A算法中那樣）。前面介紹的評價函數(shù)也可能適合于動態(tài)規(guī)劃。107q上：人肺部X射線CT原始代表性的圖像。q下：顯示成白色的檢測出的裂縫108算法：作為動態(tài)規(guī)劃的邊界跟蹤1.指定第1個圖層的所有節(jié)

29、點的初始費用 和部分路徑費用 。2.對于所有的m=1, , M-1重復(fù)第3步。 3.在圖層m中，對于所有的k=1, , n重復(fù)第4步。 1(),1,iC xin ( , )1,1mgi kmM1094.設(shè) 設(shè)指針從節(jié)點 指回節(jié)點 ，其中*指示最優(yōu)的前驅(qū)。5.在最后一層M找到最優(yōu)節(jié)點 。通過從 到 的指針回溯得到最優(yōu)路徑。 ),()(min)(1 , 0, 11kigxCxCmmikimk1mkxmixMkxMkx1ix110對于在圖中尋找兩個節(jié)點的路徑而言，啟發(fā)式搜索可能比動態(tài)規(guī)劃更為有效。而且，基于A-算法的圖搜索并不需要明確地定義圖。動態(tài)規(guī)劃給出了從多個起點和終點中同時搜索最優(yōu)路徑的一個有

30、效的方法。111在動態(tài)規(guī)劃中，待搜索的圖總是在搜索開始之前就完整地建立起來的，因此，交互地設(shè)置終點不會調(diào)用耗時的圖重建的過程，這一點不同于啟發(fā)搜索的情況。 112因此，在建立了完整的圖并分配了節(jié)點費用之后，連接固定的起點和交互地改變的終點的最優(yōu)路徑可以實時地確定。 在復(fù)雜的區(qū)域情況下，完整的區(qū)域邊界通常是從幾段邊界建立起來的。在定義了起點之后，操作者交互地引導(dǎo)終點使得計算出的最優(yōu)邊界在視覺上是正確的。 113如果操作者對當前的邊界滿意，以及如果終點進一步移動會導(dǎo)致邊界脫離期望位置的情況下，固定終點并將其作為一個新起點作為下段邊界的檢測。建立一個新的完整的圖，操作者交互地定義下一個終點。 114

31、盡管在響應(yīng)交互修改的終點時的邊界檢測是非常快的，但是搜索每段邊界所需的初始建立完整圖的過程是高計算代價的，這是因為圖是整幅圖像尺寸的。顯然，要獲得實時性能需要充分的計算能力。 115如果圖像由已知形狀和大小的物體組成，分割可以看成是在圖像中尋找該物體的問題。 典型的任務(wù)是在印刷電路板上定位圓形的襯底，或者是在航拍或衛(wèi)星數(shù)據(jù)中尋找特殊形狀的物體。 116一種方法是在圖像中移動一個合適形狀和大小的掩模，尋找圖像與掩模間的相關(guān)性。由于形狀變形、旋轉(zhuǎn)、縮放等原因，該特殊的掩模常常與在待處理的數(shù)據(jù)中物體的表示相差太大。 117一種非常有效的解決該問題的方法是Hough變換，它甚至可用于重疊的或部分遮擋的

32、物體的分割。118我們來考慮圓形檢測的例子。設(shè)任務(wù)是在均勻亮背景的圖像中，檢測一個已知半徑r的黑圓圈。該方法從搜索一個黑像素開始，一旦找到這樣的一個像素，就可以確定一條與其關(guān)聯(lián)的可能圓心點的軌跡。這樣的可能圓心點的軌跡構(gòu)成半徑為r的圓。119如果原始圖像中的所有黑像素關(guān)聯(lián)的軌跡都被構(gòu)建出來，就可以確定圖像空間中每個像素作為圓心軌跡元素出現(xiàn)的頻率。待尋找的真正圓心由具有最高出現(xiàn)頻率的像素表示。我們已知圓的半徑，這樣就完成了圖像分割。 120下圖直觀地證明了Hough變換可以成功地應(yīng)用于如下的圖像中：q含有有關(guān)待搜索物體（例子中是圓）不完全信息的圖像；q出現(xiàn)額外的結(jié)構(gòu)和噪聲的圖像；q兩種兼有的情況

33、。121 a)亮背景下黑圓圈（已知半徑r）的原始圖像b)每個黑像素定義了一個以它為中心半徑r的可能圓心點的軌跡c)確定圖像像素作為圓心軌跡元素出現(xiàn)的頻率，具有最高出現(xiàn)頻率的像素表示圓心（標記為）d)在不完全的圓信息和有重疊結(jié)構(gòu)出現(xiàn)時，Hough變換正確地檢測出了圓（標記為） 122最初的Hough變換是設(shè)計用來檢測直線和曲線的，起初的方法要求知道物體邊界線的解析方程，但不需要有關(guān)區(qū)域位置的先驗知識。這種方法的一個突出優(yōu)點是分割結(jié)果的魯棒性，即分割對數(shù)據(jù)的不完全或噪聲不是非常敏感。123直線由兩點A=(x1,y1)和B=(x2,y2)定義。通過點A的所有直線由y1=kx1+q表示，k和q是某些值

34、。這意味著同一個方程可以解釋為參數(shù)空間k和q的方程。124因此通過點A的所有直線可以表示為方程q=-x1k+y1。類似地通過點B的直線可以表示為q=-x2k+y2。在參數(shù)空間k和q中，兩條直線的唯一公共點是在原圖像空間中表示連接點A和B的唯一存在的直線。125(a) 圖像空間 (b) k和q的參數(shù)空間126圖像中的每條直線在參數(shù)空間k和q中由單獨一個點表示，直線的任何一部分都變換為同一個點。直線檢測的主要思想是確定圖像中所有的直線像素，將通過這些像素的所有直線變換到參數(shù)空間的對應(yīng)點。127在最一般的情況下，我們沒有任何有關(guān)圖像中的直線的信息。只考慮有限數(shù)目的直線方向。直線的可能方向定義了參數(shù)k

35、和q的一個離散化。參數(shù)空間被表示為矩形的單元，被稱為累計數(shù)組A，它的元素是累計單元A(k,q)。 128對于每個邊緣元素，確定其參數(shù)k和q，這些參數(shù)表示了通過該像素的允許方向的直線。對于每條這樣的直線，直線參數(shù)k和q的值用來增加累計單元A(k,q)的值。 129顯然，如果公式y(tǒng)=ax+b所表示的直線出現(xiàn)在圖像中，累計單元A(a,b)的值就會被增加很多次，次數(shù)等于直線y=ax+b作為可能通過某個邊緣像素的直線被檢測到的數(shù)目。130對于任意像素P，通過它的直線可能是任何的方向k（取自于允許方向的集合），但是第二個參數(shù)q受像素P的圖像坐標和方向k所約束。 131因此，存在于圖像中的直線會引起圖像中適

36、合的累計單元的值變大。而通過邊緣像素的其它直線，它們不對應(yīng)于圖像中存在的直線，對于每個邊緣像素具有不同的參數(shù)k和q，所以對應(yīng)的累計單元極少被增加。132換句話說，圖像中存在的直線可以作為累計數(shù)組中的高值累計單元被檢測出來，檢測到的直線參數(shù)由累計數(shù)組的坐標給出。結(jié)果是，圖像中直線的檢測被變換為累計空間中的局部極值的檢測。133Hough變換的重要性質(zhì)是，它對圖像中直線的殘缺部分、噪聲以及其它共存的非直線結(jié)構(gòu)不敏感。這是由從圖像空間到累計空間的變換的魯棒性引起的，直線殘缺的部分只會造成較低的局部極值。134Hough變換隨著曲線參數(shù)數(shù)目的增加導(dǎo)致累計器數(shù)據(jù)結(jié)構(gòu)成指數(shù)增長，限制了其實際應(yīng)用，使其只可

37、用在具有少量參數(shù)的曲線上。如果使用有關(guān)邊緣方向的先驗信息，就可以顯著地降低計算負擔，有了邊緣方向信息時，只需增大少數(shù)的累計單元。 135a)原始圖像b)邊緣圖像（很多邊緣并不屬于直線）c)參數(shù)空間d)檢測到的直線136算法：使用Hough變換的曲線檢測1.考慮用方程f(x,a)=0表示的任意曲線，其中a是曲線的參數(shù)向量。2.在參數(shù)a的范圍內(nèi)量化參數(shù)空間。參數(shù)空間的維數(shù)n由向量a的參數(shù)數(shù)目給出。 3.形成一個n維的累計數(shù)組A(a)，其結(jié)構(gòu)與參數(shù)空間的量化相匹配，并設(shè)置所有的元素為0。1374.在適當?shù)亻撝祷蟮奶荻葓D像中，對每個圖像點(x1,x2)，對于所有的在第1步使用范圍內(nèi)的a，增大所有的滿

38、足f(x, a)=0的累計單元A(a)：A(a)=A(a)+A5.累計數(shù)組A(a)中的局部極大值對應(yīng)于出現(xiàn)在原始圖像中的曲線f(x,a)的實現(xiàn)。 138a)原始圖像b)邊緣圖像（請注意邊緣信息遠不完美）c)參數(shù)空間d)檢測到的圓139然而，一般要獲得描述邊界的解析表達常常是不可能的。期望區(qū)域的邊界極少能表述為少量參數(shù)的邊界曲線，在這種情況下，廣義Hough變換可以提供解決方案，即使不知道邊界的解析表達也可以找到物體。140廣義Hough變換根據(jù)在學習階段中檢測到的樣本情形構(gòu)建一個參數(shù)曲線（區(qū)域邊界）描述。假設(shè)已知期望區(qū)域的形狀、尺寸和旋轉(zhuǎn)。在樣本區(qū)域內(nèi)任取一個位置作為參考點xR，則從該參考點出

39、發(fā)可以建立任意一條朝著區(qū)域邊界的直線（參見下圖）。141廣義Hough變換原理：創(chuàng)建R-表的幾何142邊界的方向（邊緣方向）在直線與區(qū)域邊界相交處得到。建立一個參考表（R-表），交點參數(shù)作為交點處邊界方向的函數(shù)來存儲。使用從參考點出發(fā)的不同直線，從參考點到區(qū)域邊界的所有距離和交點處的邊界方向都可以找到。143產(chǎn)生的表按照交點處的邊界方向排序。從上圖可以清楚地看到，區(qū)域邊界的不同 點 x 可 以 具 有 相 同 的 邊 界 方 向 ，(x)=(x)。這意味著對于每個有可能存在多于一對的(r,)，這可以用來確定潛在的參考點坐標。144123k),(,),(),(111121211111nnrrr)

40、,(,),(),(222222221212nnrrr),(,),(),(333323231313nnrrr),(,),(),(2211nkknkkkkkkrrr145算法：廣義Hough變換1.給期望物體構(gòu)建R-表描述。2.形成一個表示潛在參考點的數(shù)據(jù)結(jié)構(gòu)A： A(x1,x2,S,) 令所有的累計單元A(x1,x2,S,)為0。1463.在閾值化后的梯度圖像中，對每個像素(x1,x2)，確定其邊緣方向(x)，找到所有的潛在參考點xR，對于所有可能的旋轉(zhuǎn)和大小變化： 增大所有的A(xR,S,)：)(sin()()(cos()(2211SrxxSrxxRRASxASxARR),(),(1474.數(shù)

41、據(jù)結(jié)構(gòu)A中的局部極大值給出了適合區(qū)域的位置。148Hough變換最初的設(shè)計是用來檢測解析定義的形狀的，例如一般圖像中的直線、圓、橢圓，而廣義Hough變換可以用來檢測任意的形狀。即使是廣義Hough變換也需要完全定義目標物體的精確形狀，即前提是形狀是事先定義的，才能獲得精確的分割。149Hough變換有很多期望的性質(zhì)。它可以識別部分的或少許變形的形狀，因此在識別部分遮擋的物體時性能非常好。在圖像中出現(xiàn)額外結(jié)構(gòu)（其它直線、曲線或物體）時，Hough變換是非常魯棒的，同時對圖像噪聲也不敏感。150如果已知一些有關(guān)邊界位置或形狀的信息，使用它是有利的。例如，信息可以是基于某種高層知識或者是來自于在低

42、分辨率圖像上做分割的結(jié)果。 151一種可能是將圖像中的邊界作為接近假設(shè)邊界的顯著邊界的位置來確定，其中這些顯著邊界的邊緣方向與假設(shè)邊界的方向相匹配。新的邊界像素在與假設(shè)邊界方向垂直的方向上搜索。 152有關(guān)邊界位置的先驗信息153另一種可能是基于終點的先驗信息，這種方法假設(shè)圖像噪聲低且邊界相對比較直。這一過程迭代地將邊界劃分為部分，在與連接每部分終點的線的垂直方向上搜索最強的邊緣。154這些垂直方向位于連接線的中點。在與當前部分的終點連接線接近的垂直方向上最強的邊緣被接受為新的邊界元素。這一過程迭代地進行。155 分而治之迭代邊界檢測 數(shù)字指明分解的步數(shù)的序列 156輪廓檢測方法：其中的活動輪

43、廓（active contour）模型蛇(snake)利用用戶提供的有關(guān)所需輪廓的近似位置和形狀的知識，啟動輪廓的搜索。一個優(yōu)化方法改進起始輪廓的估計使其與期望的輪廓相匹配。157迄今考慮的所有方法都集中在邊界的檢測方面，這些邊界部分地或全部地對圖像進行了分割處理。如果獲得了完全的分割，邊界將圖像分割為區(qū)域。158但是如果僅產(chǎn)生了部分分割，區(qū)域并沒有唯一的定義，根據(jù)邊界確定區(qū)域的問題是一個非常復(fù)雜的任務(wù)。但是，存在一些能夠從不構(gòu)成封閉邊界的部分邊界構(gòu)建區(qū)域的方法。這些方法并不總是能找到可以接受的區(qū)域，但是它們在很多實際情況中很有用。159算法：從部分邊界形成區(qū)域1.對每個邊界像素x，在不超出給

44、定的最大值M的距離范圍內(nèi)，搜索一個反向邊緣像素。如果沒有找到反向邊緣像素，處理圖像中的下一個邊界像素。如果找到了一個反向邊緣像素，將連接直線上的每個像素標注為潛在的區(qū)域成員。1602.計算圖像中每個像素的標注次數(shù)（標注次數(shù)反映了一個像素出現(xiàn)在反向邊緣像素連接線上的頻繁程度）。設(shè)b(x)為像素x的標注次數(shù)。1613.加權(quán)的標注次數(shù)B(x)根據(jù)下式確定： 當b(x)=0, B(x)=0.0 當b(x)=1, B(x)=0.1 當b(x)=2, B(x)=0.2 當b(x)=3, B(x)=0.3 當b(x)=3, B(x)=1.0162一個像素x是一個區(qū)域成員的置信度定義為該像素x在其33鄰域內(nèi)的

45、求和式iB(xi)。如果x是區(qū)域成員的置信度為1或更大，則將x標注為區(qū)域像素，否則標記為背景像素。 163164在前面的章節(jié)中介紹的分割方法的目標是找到區(qū)域間的邊界，以下的方法將直接構(gòu)造區(qū)域。 由基于邊緣的方法產(chǎn)生的分割和由區(qū)域增長方法得到的分割，通常并不總是相同的。 165區(qū)域增長技術(shù)在有噪聲的圖像中一般會更好些，其中的邊界非常難以檢測。一致性是區(qū)域的一個重要性質(zhì)，在區(qū)域增長中用作主要的分割準則。它的基本思想是將圖像劃分為最大一致性的分區(qū)。一致性準則可以是基于灰度、色彩、紋理、形狀、模型等的標準。 166選擇出來的描述區(qū)域的性質(zhì)，對具體的區(qū)域增長分割方法的形式、復(fù)雜度、先驗信息的數(shù)量有影響。

46、 167一致性準則是需要特別關(guān)注的，它的選擇是影響所提方法的最重要的因素，還可以將特殊的啟發(fā)式信息結(jié)合進該標準之中。最簡單一致性準則使用區(qū)域的平均灰度、區(qū)域的色彩性質(zhì)、簡單的紋理性質(zhì)或多光譜圖像平均灰度值的m維向量。 168最自然的區(qū)域增長方法是在原始圖像數(shù)據(jù)上開始增長。最簡單的每個像素表示一個區(qū)域。169區(qū)域必須滿足以下條件： 其中S是圖像中區(qū)域的總數(shù)，H(Ri)是評價區(qū)域Ri的二值性的一致性度量。)2(, 2 , 1)(SiTRUERHi) 3(,)(jijiRRjiFALSERRH鄰接于) 1 (01jiRjRiRRSii170算法：區(qū)域歸并（大綱）1.定義某種初始化方法將圖像分割為滿足

47、公式(2)的很多小區(qū)域。2.為歸并兩個鄰接區(qū)域定義一個標準。1713.將滿足歸并標準的所有鄰接區(qū)域歸并起來。如果不再有兩個區(qū)域歸并后保持條件(2)，則停止。172該算法表示了區(qū)域歸并分割的一般方法。特殊的算法區(qū)別在于初始分割的定義和歸并標準。在隨后的描述中，區(qū)域是指可以順序地歸并為滿足公式(2)和公式(3)的更大區(qū)域的圖像的那些部分。 173算法：通過邊界溶解的區(qū)域歸并1.定義一個將圖像劃分為具有不變灰度區(qū)域的初始分割。存儲裂縫邊緣信息。2.從邊緣數(shù)據(jù)結(jié)構(gòu)中，刪除所有的弱裂縫邊緣。1743.如果滿足下式： 則迭代地刪除鄰接區(qū)域Ri和Rj的共同邊界，其中W是共同邊界上的弱邊緣數(shù)目， li和lj是

48、區(qū)域Ri和Rj的周長，T2是一個預(yù)先設(shè)定的閾值。2),min(TllWji1754.迭代地刪除鄰接區(qū)域Ri和Rj的共同邊界，如果滿足下式： 或者，使用一個更弱的標準 其中l(wèi)是共同邊界的長度，T3是閾值。3TlW3TW 176下圖給出了區(qū)域歸并方法的一個比較。圖a和圖b給出了原始圖像和其偽彩色表示（為了看到小的灰度變化）。原始圖像不能用閾值化來分割，因為其中的所有區(qū)域具有顯著的且連續(xù)的灰度梯度。177圖c給出了使用簡單歸并準則的迭代區(qū)域歸并方法的結(jié)果。注意產(chǎn)生的長條區(qū)域?qū)?yīng)于圖像灰度的縱向變化。如果使用通過邊界溶解的區(qū)域歸并，分割結(jié)果會有顯著的改善，參見圖d。178a)原始圖像b)原始圖像的偽彩

49、色表示c)迭代區(qū)域歸并d)通過邊界溶解的區(qū)域歸并179區(qū)域分裂與區(qū)域歸并相反，從將整個圖像表示為單個區(qū)域開始，該區(qū)域一般不能滿足條件(2)。因此存在的圖像區(qū)域順序地被分裂開以便滿足(1)、(2)和(3)。 180盡管這種方法好像是區(qū)域歸并的對偶，但即便是使用相同的一致性準則，區(qū)域分裂也不會產(chǎn)生與后者相同的分割結(jié)果。 然而，區(qū)域歸并和區(qū)域分裂不是對偶的。 181一個例子是精致的黑白棋盤：設(shè)以被評估區(qū)域的四分象限中的平均灰度變化為基礎(chǔ)建立一致性標準，該評估區(qū)域在下一個較低金字塔層上。 182如果分割過程是基于區(qū)域分裂的，那么圖像就不會被分裂為子區(qū)域，這是因為它的四個象限與由整個圖像構(gòu)成的開始區(qū)域具

50、有相同的度量值。 183而另一方面，區(qū)域歸并方法開始于將單個像素區(qū)域歸并為更大的區(qū)域，這一過程當區(qū)域與棋盤塊匹配時就會停止。 這樣，如果使用分裂，整個圖像將會被作為一個區(qū)域；而如果使用歸并，棋盤將會被分割為如下圖所示的塊。 184a)棋盤圖像，對應(yīng)的金字塔；b)區(qū)域分裂分割（較高金字塔層是一致的，不可能分裂）；c)區(qū)域歸并分割 （最低金字塔層由不能歸并的區(qū)域組成）。 185區(qū)域分裂方法一般使用與區(qū)域歸并方法相似的準則，區(qū)別僅在于應(yīng)用的方向上。 186分裂和歸并的結(jié)合可以產(chǎn)生兼有兩種方法優(yōu)點的一種新方法。分裂與歸并方法在金字塔圖像表示上進行，區(qū)域是方形的與合適的金字塔層元素對應(yīng)。 187如果在任

51、一金字塔層中的任意一個區(qū)域不是一致的（排除最底層），就將其分裂為4個子區(qū)域，它們是下一層的較高分辨率的元素。如果在金字塔的任意一層中有4個區(qū)域具有接近相同的一致性度量數(shù)值，就將它們歸并為金字塔的上一層中的單個區(qū)域。188分割過程可以理解為分割四叉樹的創(chuàng)建，其中的每個葉子節(jié)點代表一個一致區(qū)域，即某個金字塔層的元素。分裂與歸并對應(yīng)于分割四叉樹的刪除或建立部分。在分割過程結(jié)束之后，樹的葉節(jié)點數(shù)對應(yīng)于分割后的區(qū)域數(shù)。 189在分層數(shù)據(jù)結(jié)構(gòu)中的分裂與歸并 190分割四叉樹191起始的圖像區(qū)域既可以任意選擇，也可以根據(jù)先驗知識來確定。因為分裂和歸并的選擇都存在，起始分割不必滿足(2)和(3)中的任一條件。

52、在分裂與歸并算法中，一致性標準起主要作用，正如它在所有其它區(qū)域增長方法中一樣。 192如果要處理的圖像相當簡單，分裂與歸并方法可以基于局部圖像性質(zhì)。如果圖像十分復(fù)雜，即使是考慮了語義信息的精心制定的標準也未必可以產(chǎn)生可接受的結(jié)果。 193算法：分裂與歸并1.定義一個劃分為區(qū)域的初始分割、一致性準則和一個金字塔數(shù)據(jù)結(jié)構(gòu)。1942.如果在金字塔數(shù)據(jù)結(jié)構(gòu)中的任意一個區(qū)域不是一致的H(R)=FALSE，就將其分裂為4個子區(qū)域；如果具有相同父節(jié)點的任意4個區(qū)域可以歸并為單個一致性區(qū)域，則歸并它們。如果沒有區(qū)域可以分裂或歸并，則轉(zhuǎn)到第3步。1953.如果任意兩個鄰接區(qū)域Ri和Rj可以歸并為一個一致性區(qū)域（

53、即使它們在金字塔的不同層或沒有相同的父節(jié)點），則歸并它們。4.如果必須刪除小尺寸區(qū)域，則將小區(qū)域與其最相似的鄰接區(qū)域歸并。196分水嶺圖像分割算法借助地形學概念進行圖像分割，近年來得到廣泛應(yīng)用。該算法的計算過程是串行的，得到的是目標的邊界。為討論分水嶺的概念，可借助地形學概念進行。 197把圖像看成3D地形的表示，即2D的地基（對應(yīng)圖像空間）加上第三維的高度（對應(yīng)圖像灰度）。圖中黃線稱為分水線，該分水線將兩個重疊圓形目標分開并給出一個最優(yōu)的結(jié)果。198實際中建立不同目標間的分水嶺的過程常借助漲水法（水從低上漲）來討論分水嶺的求取技術(shù)。利用下圖來討論，為了簡便，僅畫出各個目標的1D刨面。199假

54、設(shè)有水從各谷底涌出并且水位逐漸增高。如果從兩個相鄰谷底涌出的水的水位高過其間的山峰，這些水就會匯合。如果要阻止這些水匯合，就需在該山峰上修筑水壩，且水壩的高度要隨水位的上升而增高。200這個過程隨著全部山峰都被水浸沒而結(jié)束。在這個過程中修筑的各個水壩將整片土地分割成很多區(qū)域，這些水壩就構(gòu)成了這片土地的分水嶺。201谷地孔分水嶺202a)原始圖像b)地形俯視圖c)被水淹沒的兩個不同階段之一d)被水淹沒的兩個不同階段之二203e)進一步淹沒的結(jié)果f)匯水盆地的水開始聚合（它們之間有一條短水壩）g)長一些的水壩h)最后的分水嶺204從上可見，如果能確定出分水嶺的位置，就能將圖像用一組各自封閉的曲線分

55、割成不同的區(qū)域。分水嶺圖像分割算法就是通過確定分水嶺的位置而進行圖像分割的。205一般考慮到各區(qū)域內(nèi)部像素的灰度比較接近，而相鄰區(qū)域像素間的灰度差距比較大。所以可先計算一幅圖像的梯度圖，再尋找梯度圖的分水嶺。206在梯度圖中，小梯度值像素對應(yīng)區(qū)域的內(nèi)部，而大梯度值像素對應(yīng)區(qū)域的邊界。分水嶺算法尋找大梯度值像素的位置，也就是尋找分割邊界的位置。207a)原始圖像b)取閾值后的結(jié)果（相鄰沙粒混在一起）c)應(yīng)用分水嶺算法分割的結(jié)果d)將圖(c)得到的輪廓線疊加到原始圖像上的效果(a)(b)(c)(d)208a)原始圖像b)梯度圖像c)分水線d)疊加于原圖像中的分水線209(a)(b)a)電泳現(xiàn)象的圖

56、像b)對梯度圖像使用分水嶺分割算法得到的結(jié)果，過度分割現(xiàn)象很明顯210直觀地說，由于梯度噪聲、量化誤差及物體內(nèi)部細密紋理的影響，在平坦區(qū)域內(nèi)部可能會產(chǎn)生許多局部的“谷底”和“山峰”，經(jīng)分水嶺變換后形成小的區(qū)域，很容易導(dǎo)致過分割，使希望得到的正確輪廓被大量不相關(guān)輪廓所淹沒。211a)小氣泡圖像b)梯度幅值圖像c)原始分水嶺分割的過分割圖像d)平滑梯度圖像后的分水嶺變換，一些過分割仍然比較明顯212為解決上述過分割的問題，一般可在分水嶺分割算法之前，對每一個目標區(qū)域進行標記。利用標記可將先驗知識加進分割過程，從這個角度來說，分水嶺算法提供了一個借用先驗知識幫助分割的框架。213這些目標區(qū)域的標記可

57、以從圖像中用特征檢測的方法提取出來，必要時也可手工確定標記。對每個目標區(qū)域都要確定一個標記，因為標記和最終的分割區(qū)域是一對一的。標記的尺寸可大可小（最小一個像素），如果處理噪聲大的圖像，標記也要較大。214標記控制分水嶺圖像分割方法的流程框圖215a)部分覆蓋的兩個生物細胞區(qū)域b)由區(qū)域內(nèi)距離邊界等距離點構(gòu)成的“等高線”圖。因為它的局部極小值和要分開的區(qū)域有一對一的關(guān)系，所以可以用作標記函數(shù)（這里取圍繞局部極小值的小區(qū)域為標記）c)檢測出的分水線可將兩個部分覆蓋的區(qū)域分割開來。216a)顯示有內(nèi)部標記（淺灰色區(qū)域）和外部標記（白色線）的圖像b)分割的結(jié)果(a)(b)217a)原始圖像b)梯度圖

58、像，33 Sobel邊緣檢測，直方圖均衡化c)原始分水嶺分割d)使用區(qū)域標記控制減少過分割現(xiàn)象的分水嶺分割218219使用區(qū)域增長方法分割后的圖像，時常是由于參數(shù)設(shè)置的非最優(yōu)性所造成，不是含有太多的區(qū)域（欠增長）就是含有過少的區(qū)域（過增長）。為了改進分割效果，可以在分割后的圖像中減少小區(qū)域的數(shù)目。 220這些小區(qū)域根據(jù)原來使用的一致性準則是不能與任何鄰接的區(qū)域歸并的。這些小區(qū)域在進一步的處理中通常并不重要，可以看作是分割噪聲?？梢愿鶕?jù)如下的算法將它們刪除。221算法：小圖像區(qū)域消解1.搜索最小的圖像區(qū)域Rmin。2.根據(jù)使用的一致性準則，尋找與Rmin最相似的鄰接區(qū)域R。將R與Rmin歸并起來

59、。3.重復(fù)步驟1和2，直至所有的比預(yù)先選擇的尺寸小的區(qū)域都被刪除為止。 222223匹配是分割的另一種基本方法，可以用于在圖像中定位已知的物體，也可以用于搜索特殊的模式等。下圖給出了一個期望的模式和其在圖像中發(fā)現(xiàn)的位置。 224使用匹配的分割，匹配的模式和最佳匹配的位置。 225匹配的用途很廣，如果有從不同位置拍攝的不止一幅同一場景的圖像，就可以用匹配的方法來確定立體場景的性質(zhì)。在動態(tài)圖像（例如，運動的汽車、云彩等）中的匹配是另一個應(yīng)用領(lǐng)域。 226一般來說，可以用一幅圖像抽取出物體或模式，指導(dǎo)在余下的圖像中搜索相同的（或相似的）模式。最好的匹配是基于某種最優(yōu)性準則的，該準則依賴于物體的性質(zhì)和

60、物體的關(guān)系。 227匹配的模式可以非常小，或者也可以表示整個感興趣的物體。盡管匹配常常建立在圖像子區(qū)域的灰度性質(zhì)的直接比較上，但是使用圖像導(dǎo)出的特征或高層圖像描述來建立匹配也可以同樣有效。228在這些情況下，匹配可能變得對圖像變換具有不變性。最優(yōu)性準則可以通過計算從簡單的相關(guān)性到復(fù)雜的圖匹配方法來實現(xiàn)。229如果可以期待在待處理的圖像中出現(xiàn)的是模式的精確的復(fù)制，基于匹配的分割就會非常容易。230然而，在實際的圖像中，模式的某部分通常會由于噪聲、幾何變形、遮擋等因素而損壞。因此，尋找絕對的匹配一般是不可能的，搜索最大匹配的位置更合適。231算法：基于匹配的分割1.對于模式在圖像中的每個位置和旋轉(zhuǎn)