圖像分割與邊緣檢測.ppt

第5章 圖像分割與邊緣檢測,5.1 閾值分割 5.2 基于區(qū)域的分割 5.3 邊緣檢測 5.4 區(qū)域標(biāo)記與輪廓跟蹤 5.5 分水嶺分割 5.6 投影法與差影法 5.7 圖像分割實例,5.1 閾值分割 5.1.1 概述 閾值化是最常用一種圖像分割技術(shù)， 其特點是操作簡單， 分割結(jié)果是一系列連續(xù)區(qū)域。灰度圖像的閾值分割一般基于如下假設(shè)： 圖像目標(biāo)或背景內(nèi)部的相鄰像素間的灰度值是高度相關(guān)的， 目標(biāo)與背景之間的邊界兩側(cè)像素的灰度值差別很大， 圖像目標(biāo)與背景的灰度分布都是單峰的。 如要圖像目標(biāo)與背景對應(yīng)的兩個單峰大小接近、 方差較小且均值相差較大， 則該圖像的直方圖具有雙峰性質(zhì)。 閾值化?？梢杂行Х指罹哂须p峰性質(zhì)的圖像。,閾值分割過程如下： 首先確定一個閾值T， 對于圖像中的每個像素， 若其灰度值大于T，則將其置為目標(biāo)點(值為1)， 否則置為背景點(值為0)， 或者相反， 從而將圖像分為目標(biāo)區(qū)域與背景區(qū)域。 用公式可表示為,(5-1),在編程實現(xiàn)時， 也可以將目標(biāo)像素置為255， 背景像素置為0， 或者相反。 當(dāng)圖像中含有多個目標(biāo)且灰度差別較大時， 可以設(shè)置多個閾值實現(xiàn)多閾值分割。 多閾值分割可表示為,(5-2),式中： Tk為一系列分割閾值； k為賦予每個目標(biāo)區(qū)域的標(biāo)號； m為分割后的目標(biāo)區(qū)域數(shù)減1。,閾值分割的關(guān)鍵是如何確定適合的閾值， 不同的閾值其處理結(jié)果差異很大， 會影響特征測量與分析等后續(xù)過程。如圖5-1所示， 閾值過大， 會過多地把背景像素錯分為目標(biāo)； 而閾值過小， 又會過多地把目標(biāo)像素錯分為背景。確定閾值的方法有多種， 可分為不同類型。如果選取的閾值僅與各個像素的灰度有關(guān)， 則稱其為全局閾值。如果選取的閾值與像素本身及其局部性質(zhì)(如鄰域的平均灰度值)有關(guān)， 則稱其為局部閾值。如果選取的閾值不僅與局部性質(zhì)有關(guān)， 還與像素的位置有關(guān)， 則稱其為動態(tài)閾值或自適應(yīng)閾值。閾值一般可用下式表示： T=Tx, y, f(x, y), p(x, y) (5-3) 式中： f(x， y)是點(x，y)處的像素灰度值：p(x，y)是該像素鄰域的某種局部性質(zhì)。,圖5-1 不同閾值對圖像分割的影響,當(dāng)圖像目標(biāo)和背景之間灰度對比較強時，閾值選取較為容易。實際上，由于不良的光照條件或過多的圖像噪聲的影響，目標(biāo)與背景之間的對比往往不夠明顯，此時閾值選取并不容易。一般需要對圖像進(jìn)行預(yù)處理，如圖像平滑去噪，再確定閾值進(jìn)行分割。 5.1.2 全局閾值 當(dāng)圖像目標(biāo)與背景之間具有高對比度時，利用全局閾值可以成功地分割圖像。如圖5-2(a)所示，點狀目標(biāo)與背景之間具有鮮明的對比，如圖5-2(b)所示的直方圖表現(xiàn)出雙峰性質(zhì)，左側(cè)峰對應(yīng)較暗的目標(biāo)，右側(cè)峰對應(yīng)較亮的背景，雙峰之間的波谷對應(yīng)目標(biāo)與背景之間的邊界。當(dāng)選擇雙峰之間的谷底點對應(yīng)的灰度值作為閾值時，便可以很好地將目標(biāo)從背景中分離出來。圖5-2(c)是用閾值124分割的結(jié)果。,圖5-2 直方圖具有雙峰性質(zhì)的閾值分割,確定全局閾值的方法很多，如極小點閾值法、迭代閾值法、最優(yōu)閾值法、Otsu閾值法、最大熵法、p參數(shù)法等。當(dāng)具有明顯的雙峰性質(zhì)時，可直接從直方圖的波谷處選取一 個閾值，也可以根據(jù)某個準(zhǔn)則自動計算出閾值。實際使用時，可根據(jù)圖像特點確定合適的閾值方法，一般需要用幾種方法進(jìn)行對比試驗，以確定分割效果最好的閾值。,1 極小點閾值法 如果將直方圖的包絡(luò)線看做一條曲線，則通過求取曲線極小值的方法可以找到直方圖的谷底點，并將其作為分割閾值。設(shè)p(z)代表直方圖，那么極小點應(yīng)滿足： p(z)=0 且 p(z)0 (5-4) 若在求極小值點之前對直方圖進(jìn)行平滑處理，則效果會更好。例如3點平滑，平滑后的灰度級i的相對頻數(shù)用灰度級i-1，i，i+1的相對頻數(shù)的平均值代替。,2 迭代閾值法 迭代閾值算法如下： (1) 選擇一個初始閾值T1。 (2) 根據(jù)閾值T1將圖像分割為G1和G2兩部分。G1包含所有小于等于T1的像素，G2包含所有大于T1的像素。分別求出G1和G2的平均灰度值1和2。 (3) 計算新的閾值T2=(1+2)/2。 (4) 如果|T2-T1|T0(T0為預(yù)先指定的很小的正數(shù))，即迭代過程中前后兩次閾值很接近時，終止迭代，否則T1= T2，重復(fù)(2)和(3)。最后的T2就是所求的閾值。,設(shè)定常數(shù)T0的目的是為了加快迭代速度，如果不關(guān)心迭代速度，則可以設(shè)置為0。當(dāng)目標(biāo)與背景的面積相當(dāng)時，可以將初始閾值T1置為整幅圖像的平均灰度。當(dāng)目標(biāo)與背景的面積相差較大時，更好的選擇是將初始閾值T1置為最大灰度值與最小灰度值的中間值。,程序?qū)崿F(xiàn)關(guān)鍵代碼獲取分割的迭代閾值 while(true) for(i=0;iT1+1;i+) /計算下一個迭代閾值 Temp0+=nNYi*i; Temp1+=nNYi; /灰度直方圖 for(i=T1+1;i256;i+) Temp2+=nNYi*i; Temp3+=nNYi; /灰度直方圖 T2=(Temp0/Temp1+Temp2/Temp3)/2; /平均灰度 if(T1=T2)break; /看迭代結(jié)果是否已收斂 else T1=T2; 演示,4. Otsu法 Otsu法是閾值化中常用的自動確定閾值的方法之一。Otsu法確定最佳閾值的準(zhǔn)則是使閾值分割后各個像素類的類內(nèi)方差最小。另一種確定閾值的準(zhǔn)則是使得閾值分割后的像素類的類間方差最大。這兩種準(zhǔn)則是等價的，因為類間方差與類內(nèi)方差之和即整幅圖像的方差，是一個常數(shù)。分割的目的就是要使類別之間的差別最大，類內(nèi)之間的差別最小。,設(shè)圖像總像素數(shù)為N，灰度級總數(shù)為L，灰度值為i的像素數(shù)為Ni。令(k)和(k)分別表示從灰度級0到灰度級k的像素的出現(xiàn)概率和平均灰度，分別表示為,(5-15),(5-16),由此可見，所有像素的總概率為(L-1)=1，圖像的平均灰度為T=(L-1)。,設(shè)有M-1個閾值(0t1t2tM-1L-1)，將圖像分成M個像素類Cj(Cjtj-1+1，tj； j=1，2，M； t0=0，tM=L-1)，則Cj的出現(xiàn)概率j、平均灰度j和方差j2為,(5-17),(5-18),(5-19),由此可得類內(nèi)方差為,(5-20),各類的類間方差為,(5-21),將使式(5-20)最小或使式(5-21)最大的閾值組(t1，t2， ，tM1)作為M閾值化的最佳閾值組。若取M為2，即分割成2類，則可用上述方法求出二值化的最佳閾值。,5. p參數(shù)法 p參數(shù)法的基本思想是選取一個閾值T，使得目標(biāo)面積在圖像中占的比例為p，背景所占的比例為1-p。p參數(shù)法僅適用于事先已知目標(biāo)所占全圖像百分比的場合。,5.2 基于區(qū)域的分割 5.2.1 區(qū)域生長 區(qū)域生長的基本思想是把具有相似性質(zhì)的像素集合起來構(gòu)成區(qū)域。首先對每個要分割的區(qū)域找出一個種子像素作為生長的起點，然后將種子像素鄰域中與種子像素有相同或相似性質(zhì)的像素合并到種子像素所在的區(qū)域中。將這些新像素當(dāng)作新的種子像素繼續(xù)上面的過程，直到?jīng)]有可接受的鄰域像素時停止生長。 圖5-7為區(qū)域生長的一個示例。圖5-7(a)為待分割的圖像，已知有1個種子像素(標(biāo)有下劃線)，相似性準(zhǔn)則是鄰近像素與種子像素的灰度值差小于3。圖5-7(b)、(c)分別是第一步、第二步接受的像素，圖5-7(d)是最后的生長結(jié)果。,算法實現(xiàn)： 1）根據(jù)圖像的不同應(yīng)用選擇一個或一組種子，它或者是最亮或最暗的點，或者是位于點簇中心的點。 2）定義適當(dāng)?shù)膮^(qū)域內(nèi)部相似性準(zhǔn)則 3）從該種子開始向外擴(kuò)張，首先把種子像素加入集合，然后不斷將與集合中各個像素連通、且滿足區(qū)域內(nèi)部相似性準(zhǔn)則的像素加入集合 4）上一過程進(jìn)行到不再有滿足條件的新的像素加入集合為止。 注：區(qū)域內(nèi)部相似性準(zhǔn)則是根據(jù)圖像的灰度特性、紋理特性以及顏色特性等多種因素確定的。區(qū)域生長成功與否的關(guān)鍵在于選擇合適的區(qū)域內(nèi)部相似性準(zhǔn)則,區(qū)域內(nèi)部相似性準(zhǔn)則是鄰近像素與種子像素的灰度值差小于3,圖5-7 區(qū)域生長示例,如：區(qū)域內(nèi)部相似性準(zhǔn)則定義為鄰點的灰度級相對于區(qū)域內(nèi)平均灰度級接近程度，灰度接近程序設(shè)為2。 Mean=9 8.25 8 終止 作業(yè)：若灰度接近程序設(shè)為3、4，區(qū)域生長情況又是怎樣？,區(qū)域生長法需要選擇一組能正確代表所需區(qū)域的種子像素，確定在生長過程中的相似性準(zhǔn)則，制定讓生長停止的條件或準(zhǔn)則。相似性準(zhǔn)則可以是灰度級、彩色、紋理、梯度等特性。選取的種子像素可以是單個像素，也可以是包含若干個像素的小區(qū)域。種子像素的選取一般需要先驗知識，若沒有則可借助生長準(zhǔn)則對每個像素進(jìn)行相應(yīng)計算。如果計算結(jié)果出現(xiàn)聚類，則接近聚類中心的像素可取為種子像素。生長準(zhǔn)則有時還需要考慮像素間的連通性，否則會出現(xiàn)無意義的分割結(jié)果。,5.2.2 區(qū)域分裂與合并 上面介紹的區(qū)域生長法需要根據(jù)先驗知識選取種子像素。當(dāng)沒有先驗知識時，區(qū)域生長法就存在困難。區(qū)域分裂與合并的核心思想是將圖像分成若干個子區(qū)域，對于任意一個子區(qū)域，如果不滿足某種一致性準(zhǔn)則(一般用灰度均值和方差來度量)，則將其繼續(xù)分裂成若干個子區(qū)域，否則該子區(qū)域不再分裂。如果相鄰的兩個子區(qū)域滿足某個相似性準(zhǔn)則，則合并為一個區(qū)域。直到?jīng)]有可以分裂和合并的子區(qū)域為止。通?；谌鐖D5-8所示的四叉樹來表示區(qū)域分裂與合并，每次將不滿足一致性準(zhǔn)則的區(qū)域分裂為四個大小相等且互不重疊的子區(qū)域。,圖5-8 區(qū)域分裂與合并的四叉樹表示,下面以一個簡單的例子來說明區(qū)域分裂與合并的過程。假設(shè)分裂時的一致性準(zhǔn)則為： 如果某個子區(qū)域的灰度均方差大于1.5，則將其分裂為4個子區(qū)域，否則不分裂。合并時的相似性準(zhǔn)則為： 若相鄰兩個子區(qū)域的灰度均值之差不大于2.5，則合并為一個區(qū)域?，F(xiàn)對圖5-7(a)進(jìn)行區(qū)域分裂與合并，結(jié)果如圖5-9所示。,圖5-9 區(qū)域分裂與合并示例,首先計算出全圖的灰度均方差為R=2.65，不滿足一致性準(zhǔn)則，需分裂為四個子區(qū)域。 分別計算出四個子塊的均值和方差：R1=5.5, R1=1.73; R2=7.5, R2=1.29；R3=2.5; R3=0; R4=3.75; R4=2.87。 根據(jù)一致性準(zhǔn)則判斷出R2和R3不需分裂，而R1和R4需要繼續(xù)分裂，剛好分裂為單個像素，如圖(b)所示。根據(jù)相似性準(zhǔn)則，先合并同節(jié)點下滿足一致性準(zhǔn)則的相鄰子區(qū)域，R11、R12和R13合并為一個區(qū)域(記為G1)，R42、R43和R44合并為另一個子區(qū)域(記為G2)，如圖(c)所示。最后合并具有相似性、不同節(jié)點下的相鄰區(qū)域，R14、R41和R2合并在一起，G1、G2和R3合并在一起，如圖(d)所示。,5.3 邊緣檢測 圖像的邊緣是圖像最基本的特征，它是灰度不連續(xù)的結(jié)果。通過計算一階導(dǎo)數(shù)或二階導(dǎo)數(shù)可以方便地檢測出圖像中每個像素在其鄰域內(nèi)的灰度變化，從而檢測出邊緣。圖像中具有不同灰度的相鄰區(qū)域之間總存在邊緣。常見的邊緣類型有階躍型、斜坡型、線狀型和屋頂型，如圖5-10所示(第一行為具有邊緣的圖像，第二行為其灰度表面圖)。階躍型邊緣是一種理想的邊緣，由于采樣等緣故，邊緣處總有一些模糊，因而邊緣處會有灰度斜坡，形成了斜坡型邊緣。斜坡型邊緣的坡度與被模糊的程度成反比，模糊程度高的邊緣往往表現(xiàn)為厚邊緣。線狀型邊緣有一個灰度突變，對應(yīng)圖像中的細(xì)線條； 而屋頂型邊緣兩側(cè)的灰度斜坡相對平緩，對應(yīng)粗邊緣。,圖5-10 圖像中不同類型的邊緣,5.3.1 微分算子 圖5-11給出了幾種典型的邊緣及其相應(yīng)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)。對于斜坡型邊緣，在灰度斜坡的起點和終點，其一階導(dǎo)數(shù)均有一個階躍，在斜坡處為常數(shù)，其它地方為零； 其二階導(dǎo)數(shù)在斜坡起點產(chǎn)生一個向上的脈沖，在終點產(chǎn)生一個向下的脈沖，其它地方為零，在兩個脈沖之間有一個過零點。因此，通過檢測一階導(dǎo)數(shù)的極大值，可以確定斜坡型邊緣; 通過檢測二階導(dǎo)數(shù)的過零點，可以確定邊緣的中心位置。,對于線狀型邊緣，在邊緣的起點與終點處，其一階導(dǎo)數(shù)都有一個階躍，分別對應(yīng)極大值和極小值； 在邊緣的起點與終點處，其二階導(dǎo)數(shù)都對應(yīng)一個向上的脈沖，在邊緣中心對應(yīng)一個向下的脈沖，在邊緣中心兩側(cè)存在兩個過零點。因此，通過檢測二階差分的兩個過零點，就可以確定線狀型邊緣的范圍； 檢測二階差分的極小值，可以確定邊緣中心位置。屋頂型邊緣的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)與線狀型類似，通過檢測其一階導(dǎo)數(shù)的過零點可以確定屋頂?shù)奈恢谩?圖5-11 典型邊緣的一階導(dǎo)數(shù)與二階導(dǎo)數(shù),由上述分析可以得出以下結(jié)論： 一階導(dǎo)數(shù)的幅度值可用來檢測邊緣的存在； 通過檢測二階導(dǎo)數(shù)的過零點可以確定邊緣的中心位置； 利用二階導(dǎo)數(shù)在過零點附近的符號可以確定邊緣像素位于邊緣的暗區(qū)還是亮區(qū)。另外，一階導(dǎo)數(shù)和二階導(dǎo)數(shù)對噪聲非常敏感，尤其是二階導(dǎo)數(shù)。因此，在邊緣檢測之前應(yīng)考慮圖像平滑，減弱噪聲的影響。在數(shù)字圖像處理中，常利用差分近似微分來求取導(dǎo)數(shù)。邊緣檢測可借助微分算子(包括梯度算子和拉普拉斯算子)在空間域通過模板卷積來實現(xiàn)。,1. 梯度算子 常用的梯度算子如表4-3所示(星號代表模板中心)。梯度算子一般由兩個模板組成，分別對應(yīng)梯度的兩個偏導(dǎo)數(shù)，用于計算兩個相互垂直方向上的邊緣響應(yīng)。在計算梯度幅度時，可使用式(4-25)或式(4-26)，在適當(dāng)?shù)拈撝迪?，對得到梯度圖像二值化即可檢測出有意義的邊緣。,Krisch算子由8個模板組成，其它模板可以由其中一個模板繞其中心旋轉(zhuǎn)得到，每個模板都對特定的邊緣方向作出最大響應(yīng)。當(dāng)把最大響應(yīng)的模板的序號輸出時，就構(gòu)成了邊緣方向的編碼。Prewitt算子和Sobel算子也可以像Krisch算子那樣，擴(kuò)展到兩個對角方向，使其在對角方向上作出最大響應(yīng)。Prewitt和Sobel算子在兩個對角方向上的模板如圖5-12所示。,圖5-12 Prewitt算子和Sobel算子檢測對角方向邊緣的模板,(a) Prewitt算子45度和-45度方向模板,(b) Sobel算子45度和-45度方向模板,圖5-13(b)為用Sobel水平模板(表4-3中的H1模板)對圖5-13(a)進(jìn)行卷積運算得到的水平梯度圖，它對垂直邊緣有較強的響應(yīng)。圖5-13(c)為用Sobel垂直模板(表4-3中的H2模板)對圖5-13(a)進(jìn)行卷積運算得到的垂直梯度圖，它對水平邊緣有較強的響應(yīng)。圖5-13(d)為根據(jù)式(4-25)得到的Sobel算子梯度圖。,圖5-13 Sobel算子邊緣檢測,作業(yè) 一幅圖像各象素灰度值分布如右圖： 用Robert、Prewitt、Sobel邊緣檢測算子對其進(jìn)行處理，請寫出三種邊緣檢測算子的一個模板以及原圖像方框中的像素經(jīng)其處理后的結(jié)果。,2. 高斯-拉普拉斯(LOG)算子 拉普拉斯算子由式(4-31)定義，常用的兩個拉普拉斯模板見圖4-16(a)和(b)。其中，第一個模板在水平和垂直4個方向上具有各向同性，而第二個模板在水平、垂直和對角8個方向上具有各向同性。然而，拉普拉斯算子一般不直接用于邊緣檢測，因為它作為一種二階微分算子對噪聲相當(dāng)敏感，常產(chǎn)生雙邊緣，且不能檢測邊緣方向。主要利用拉普拉斯算子的過零點性質(zhì)確定邊緣位置，以及根據(jù)其值的正負(fù)來確定邊緣像素位于邊緣的暗區(qū)還是明區(qū)。,高斯-拉普拉斯(LOG)算子把高斯平滑濾波器和拉普拉斯銳化濾波器結(jié)合起來實現(xiàn)邊緣檢測，即先通過高斯平滑抑制噪聲，以減輕噪聲對拉普拉斯算子的影響，再進(jìn)行拉普拉斯運算，通過檢測其過零點來確定邊緣位置。因此，高斯-拉普拉斯算子是一種性能較好的邊緣檢測器。二維高斯平滑函數(shù)表示如下：,(5-22),其中，是高斯分布的均方差，圖像被模糊的程度與其成正比。令r2=x2+y2，上式對r求二階導(dǎo)數(shù)來計算其拉普拉斯值，則有,(5-23),上式是一個軸對稱函數(shù)，由于其曲面形狀(圖5-14(a)是它的一個剖面)很像一頂墨西哥草帽，所以又叫墨西哥草帽函數(shù)。給定均方差后，對其離散化就可以得到相應(yīng)的LOG算子模板，圖5-14(b)是常用的55模板之一(模板并不唯一)。利用LOG算子檢測邊緣時，可直接用其模板與圖像卷積，也可以先與高斯函數(shù)卷積，再與拉普拉斯模板卷積，兩者是等價的。由于LOG算子模板一般比較大，因而用第二種方法可以提高速度。,圖5-14 LOG算子剖面及其常用的55模板,圖5-15是Prewitt算子、Sobel算子和LOG算子對圖5-15(a)的邊緣檢測結(jié)果。由圖可以看出，前兩種算子的檢測結(jié)果基本相同，而LOG算子則能提取對比度弱的邊緣(如后面的高樓)，邊緣定位精度高。,圖5-15 三種邊緣檢測算子的檢測結(jié)果,圖5-16 幾種邊緣檢測效果的比較,5.3.3 哈夫變換 在已知區(qū)域形狀的條件下，利用哈夫變換(Hough Transform)可以方便地檢測到邊界曲線。哈夫變換的主要優(yōu)點是受噪聲和曲線間斷的影響小，可以準(zhǔn)確的捕獲到目標(biāo)的邊界，并最終以連續(xù)曲線的形式輸出變換結(jié)果。但計算量較大，通常用于檢測已知形狀的目標(biāo)，如直線、圓等。,1. 直線檢測 在圖像空間xy里，過點(xi，yi)的直線方程可表示為yi=axi+b，其中a和b分別表示直線的斜率和截距。如果將直線方程改寫為b =-xia+yi，則它表示ab空間(稱之為參數(shù)空間)中斜率為-xi、截距為yi的一條直線，且經(jīng)過點(a，b)。對于圖像空間中與(xi，yi)共線的另一點(xj，yj)，它滿足方程yj=axj+b，對應(yīng)于參數(shù)空間中斜率為-xj、截距為yj的一條直線，也必然經(jīng)過點(a，b)。因此，可以推知，圖像空間中同一條直線(斜率為a，截距為b)上的點對應(yīng)于參數(shù)空間中相交于一點(坐標(biāo)為(a，b)的一系列直線。哈夫變換就是利用這種點線對應(yīng)關(guān)系，把圖像空間中的檢測問題轉(zhuǎn)換到參數(shù)空間中處理。,對應(yīng)一條直線,直角坐標(biāo)系中的一條直線對應(yīng)另一坐標(biāo)系中的一點，這種線到點的變換就是Hough變換,過定點P的直線的檢測 (a)中把P點作為原點，則過P點的直線方程為y=mx，圖中存在一條過P點夾角為45度的直線； (b)中有一維數(shù)組，數(shù)組的下標(biāo)對應(yīng)于過P點直線和水平方向間的夾角，每隔1度一個分量，共有360個分量。先全部置為0，逐步計算圖中每個點所成夾角，并把與這個角相對應(yīng)的數(shù)組分量的值加1； (c)中為計算完所有的像素點后夾角分量值，可見在下標(biāo)45度的位置上存在峰值5，其余不共線的點在數(shù)組中形不成峰點。,任意方向和任意位置直線的檢測 如圖：原始圖像空間（x,y），變換空間（u,v），直線方程為 對直線上的一個點在變換空間中應(yīng)滿足方程式： 也就是說，圖像空間中的一個點對應(yīng)于變換空間中的一條直線；而變換空間中的一個點對應(yīng)于圖像空間中的一條直線。 如圖： 圖(a)中直線上的點對應(yīng)到圖(b)中應(yīng)該是一條經(jīng)過點 的直線，那自然圖(a)中的直線 上的所有點都將經(jīng)過(b)中 點，變換空間中該點向量每經(jīng)過一次加1，自然而然將形成峰點，于是圖(a)中的直線也便由峰點 求出為,哈夫變換需要建立一個累加數(shù)組，數(shù)組的維數(shù)與所檢測的曲線方程中的未知參數(shù)個數(shù)相同。對于直線，它有a和b兩個未知參數(shù)，因而需要一個二維累加數(shù)組。具體計算時，需要對未知參數(shù)的可能取值進(jìn)行量化，以減少運算量。如果將參數(shù)a和b分別量化為m和n個數(shù)，則定義一個累加數(shù)組A(m，n) 并初始化為零。,假設(shè)a和b量化之后的可能取值分別為a0，a1，am-1和b0，b1，bn-1。對于圖像空間中的每個目標(biāo)點(xk，yk)，讓a取遍所有可能的值，根據(jù)b =-xka+yk計算出相應(yīng)的b，并將結(jié)果取為最接近的可能取值。根據(jù)每一對計算結(jié)果(ap，bq)(p0，m-1，q0，n-1)，對數(shù)組進(jìn)行累加： A(p，q) = A(p，q) + 1。處理完所有像素后，根據(jù)A(p，q)的值便可知道斜率為ap、截距為bq的直線上有多少個點。通過查找累加數(shù)組中的峰值，可以得知圖像中最有可能的直線參數(shù)。,如果需要檢測的直線接近豎直方向，則會由于斜率和截距的取值趨于無窮而需要很大的累加數(shù)組，導(dǎo)致計算量增大。解決方法之一就是用圖5-17(a)所示的極坐標(biāo)來表示直線方程：,(5-26),式中： 表示原點到直線的距離； 為垂線與x軸的夾角。對和量化后建立一個累加數(shù)組(見圖5-17(b)，其優(yōu)勢在于取值都是有限的。原先的點-直線對應(yīng)關(guān)系就變成了點-正弦曲線的對應(yīng)關(guān)系。計算方法與前面的相似。為了提高效率，可以先計算出每一點的梯度幅值和梯度方向。如果該點的梯度幅值小于某個閾值，即屬于邊緣點的可能性很小，則不計算該點的參數(shù)，否則將梯度方向角代入式(5-26)得出。這樣，對于每一個邊緣點，沒有必要將所有值代入方程求解，而只需根據(jù)梯度方向角計算一次。,圖5-17 直線的極坐標(biāo)表示及其對應(yīng)的累加數(shù)組,2. 圓的檢測 圓的直角坐標(biāo)系方程為 (x-a)2+(y-b)2=r2 (5-27) 由此可見， 方程中有3個未知參數(shù)： 圓心坐標(biāo)a和b， 半徑r。 需要建立一個三維數(shù)組，對于每一個像素， 依次變化a和b， 由式(5-27)計算出r。但計算量非常大。 不難發(fā)現(xiàn)， 圓周上任意一點的梯度方向均指向圓心或背離圓心。 因此， 只要知道了半徑和圓周上一點的梯度方向， 便可確定出圓心位置。,圓的極坐標(biāo)系方程為 x=a+r cos， y=b+r sin (5-28) 則圓的參數(shù)方程為 a=x-r cos， b=y-r sin (5-29) 式中： r為半徑； 為點(x， y)到圓心(a， b)的連線與水平軸的夾角。 有了某點的梯度方向之后，可讓r取遍所有值， 由式(5-29)計算出對應(yīng)的圓心坐標(biāo)。,3. 任意曲線檢測 哈夫變換可以推廣到具有解析形式f(x， a)=0的任意曲線， 其中， x表示圖像像素坐標(biāo)， a是參數(shù)向量。 任意曲線的檢測過程如下： (1) 根據(jù)參數(shù)個數(shù)建立并初始化累加數(shù)組Aa為0。 (2) 根據(jù)某個準(zhǔn)則， 如梯度幅值大于某個閾值，確定某點是否為邊緣點。對于每個邊緣點x， 確定a，使得f(x，a) =0， 并累加對應(yīng)的數(shù)組元素： Aa= Aa+1。,(3) A的局部最大值對應(yīng)圖像中的曲線， 它表示圖像中有多少個點滿足該曲線。 對A中某元素對應(yīng)的所有點的連通性進(jìn)行判斷， 可以將對應(yīng)的線段連接起來。 還可以利用最小二乘擬合法將這些點擬合成對應(yīng)的曲線。 哈夫變換能夠抽取明顯的斷線或虛線特征，如一排石子或者一條被下落樹枝分割的道路等。,5.4 區(qū)域標(biāo)記與輪廓跟蹤 5.4.1 區(qū)域標(biāo)記 圖像分割的結(jié)果通常是一幅二值圖像， 所有的目標(biāo)區(qū)域都被賦予同一種灰度值。 如果圖像中有多個目標(biāo)區(qū)域， 并且希望分析各個目標(biāo)的大小、 形狀等特征時， 就需要對目標(biāo)區(qū)域加以區(qū)分。 區(qū)域標(biāo)記是指對圖像中同一連通區(qū)域的所有像素賦予相同的標(biāo)記， 不同的連通區(qū)域賦予不同的標(biāo)記。 常用的區(qū)域標(biāo)記方法有兩種： 遞歸標(biāo)記和序貫標(biāo)記。,1. 遞歸標(biāo)記 遞歸標(biāo)記算法如下： (1) 從左到右， 從上到下逐行逐列掃描圖像， 尋找沒有標(biāo)記的目標(biāo)點P， 給該點分配一個新的標(biāo)記。 (2) 遞歸分配同一標(biāo)記給P點的鄰域目標(biāo)像素。 (3) 直到相互連接的像素全部標(biāo)記完畢， 一個連通區(qū)域就標(biāo)上了同樣的記號。 (4) 重復(fù)步驟(1)、 (2)和(3)， 尋找未標(biāo)記的目標(biāo)點并遞歸分配同一標(biāo)記給其鄰域目標(biāo)點； 若找不到未標(biāo)記的目標(biāo)點， 則圖像標(biāo)記完畢。 遞歸標(biāo)記算法在串行機上運行非常費時， 適用于并行機處理。,2. 序貫標(biāo)記 8連通區(qū)域的序貫標(biāo)記算法如下： (1) 從左到右、 從上到下掃描圖像， 尋找未標(biāo)記的目標(biāo)點P。 (2) 如果P點的左、 左上、 上、 右上4個鄰點都是背景點， 則賦予像素P一個新的標(biāo)記； 如果4個鄰點中有1個已標(biāo)記的目標(biāo)像素， 則把該像素的標(biāo)記賦給當(dāng)前像素P； 如果4個鄰點中有2個不同的標(biāo)記， 則把其中的1個標(biāo)記賦給當(dāng)前像素P，并把這兩個標(biāo)記記入一個等價表，表明它們等價。 (3) 第二次掃描圖像，將每個標(biāo)記修改為它在等價表中的最小標(biāo)記。,4連通區(qū)域的序貫標(biāo)記算法與8連通區(qū)域的相同， 只是在步驟(2)中僅判斷左鄰點和上鄰點。 序貫標(biāo)記算法通常要求對圖像進(jìn)行兩次掃描。 由于該算法一次僅運算圖像的兩行， 因此當(dāng)圖像以文件形式存儲且內(nèi)存空間不允許把整幅圖像全部載入時， 也能使用該算法。 它在第二次掃描圖像時， 利用等價表給同一連通區(qū)域的所有像素分配唯一的標(biāo)記。 但是， 當(dāng)圖像中的目標(biāo)區(qū)域十分不規(guī)則時， 會導(dǎo)致龐大的等價表。,5.4.2 輪廓提取 輪廓提取和輪廓跟蹤的目的都是為了獲取目標(biāo)區(qū)域的外部輪廓特征， 為形狀分析和目標(biāo)識別做準(zhǔn)備。 二值圖像的輪廓提取算法非常簡單， 就是掏空目標(biāo)區(qū)域的內(nèi)部點。 假設(shè)圖像的目標(biāo)像素為白色， 背景像素為黑色， 則如果圖像中某個像素為黑色， 且它的8個鄰點都是黑色時， 表明該點是內(nèi)部點， 否則為邊界點。 將判斷出的內(nèi)部像素置為背景色， 對所有內(nèi)部像素執(zhí)行該操作便可完成圖像輪廓的提取。,5.4.3 輪廓跟蹤 輪廓跟蹤就是順序找出邊界點，不僅可以跟蹤出邊界，還可以同時記錄邊界信息，如生成邊界鏈碼，為圖像分析做準(zhǔn)備。下面介紹一種二值圖像的輪廓跟蹤算法。 輪廓跟蹤可以基于4方向碼和8方向碼分別跟蹤出4連通的輪廓和8連通的輪廓，方向碼的定義如圖5-18所示。但對于大多數(shù)區(qū)域，不一定存在封閉的4連通輪廓，會導(dǎo)致基于4 方向碼的輪廓跟蹤失敗。因此，常用基于8方向碼的輪廓跟蹤。假設(shè)需要處理的圖像為二值圖像，且圖像中只有一個連通的目標(biāo)區(qū)域，則輪廓跟蹤算法如下。,圖5-18 輪廓跟蹤的方向碼,步驟1 首先從上到下、從左到右順序掃描圖像，尋找第一個目標(biāo)點作為邊界跟蹤的起始點，記為A。A點一定是最左角上的邊界點，其相鄰的邊界點只可能出現(xiàn)在它的左下、 下、右下、右四個鄰點中。定義一個搜索方向變量dir，用于記錄從當(dāng)前邊界點搜索下一個相鄰邊界點時所用的搜索方向碼。dir初始化為： (1) 對基于4方向的輪廓跟蹤，dir=3，即從方向3開始搜索與A相鄰的下一個邊界點。 (2) 對基于8方向的輪廓跟蹤，dir=5，即從方向5開始搜索與A相鄰的下一個邊界點。,如果當(dāng)前搜索方向dir上的鄰點不是邊界點，則依次使搜索方向逆時針旋轉(zhuǎn)一個方向，更新dir，直到搜索到一個邊界點為止。如果所有方向都未找到相鄰的邊界點，則該點是一個孤立點。dir的更新用公式可表示為：對基于8方向的輪廓跟蹤有dir=(dir+1) mod 8，對基于4方向的輪廓跟蹤有dir=(dir+1) mod 4。,步驟2 把上一次搜索到的邊界點作為當(dāng)前邊界點，在其33鄰域內(nèi)按逆時針方向搜索新的邊界點，它的起始搜索方向設(shè)定如下： (1) 對基于4方向的輪廓跟蹤，使dir=(dir + 3) mod 4，即將上一個邊界點到當(dāng)前邊界點的搜索方向dir順時針旋轉(zhuǎn)一個方向； (2) 對基于8方向的輪廓跟蹤，若上次搜索到邊界點的方向dir為奇數(shù)，則使dir=(dir + 6) mod 8，即將上次的搜索方向順時針旋轉(zhuǎn)兩個方向；若dir為偶數(shù)，則使dir=(dir + 7) mod 8，即將上次的搜索方向順時針旋轉(zhuǎn)一個方向。,如果起始搜索方向沒有找到邊界點，則依次使搜索方向逆時針旋轉(zhuǎn)一個方向，更新dir，直到搜索到一個新的邊界點為止。 步驟3 如果搜索到的邊界點就是第一個邊界點A，則停止搜索，結(jié)束跟蹤，否則重復(fù)步驟2繼續(xù)搜索。 由依次搜索到的邊界點系列就構(gòu)成了被跟蹤的邊界。步驟1中所采用的準(zhǔn)則稱為“探測準(zhǔn)則”，其作用是找出第一個邊界點；步驟2中所采用的準(zhǔn)則稱為“跟蹤準(zhǔn)則”，其作用是找出所有邊界點。,圖5-19為基于8方向的輪廓跟蹤示例。圖中的邊界像素用灰色表示，區(qū)域內(nèi)部像素用斜線填充，虛線箭頭表示從當(dāng)前邊界點搜索下一個邊界點的起始方向，實線箭頭表示搜索到下一個邊界點所用的方向。從最左上角點A開始，沿方向5搜索下一個邊界點為B。由于搜索到B的方向為奇數(shù)，則應(yīng)該將方向5順時針旋轉(zhuǎn)兩個方向，即從方向3開始在B的鄰域內(nèi)沿逆時針?biāo)阉餍碌倪吔琰c。方向3、4、5上都未找到邊界點，接著沿方向6查找，結(jié)果找到邊界點C。由于搜索到C點的方向為偶數(shù)，則應(yīng)該將方向6順時針旋轉(zhuǎn)一個方向，即從方向5開始在C的鄰域內(nèi)沿逆時針?biāo)阉餍碌倪吔琰c，該方向上未找到邊界點，繼續(xù)逆時針查找，在方向6上搜索到了一個邊界點D。繼續(xù)上述搜索，直到找到A點為止，即完成了邊