第六講圖像分割

1、第六講 圖像分割劉春國(guó)劉春國(guó)河南理工大學(xué)測(cè)繪與國(guó)土信息工程學(xué)院圖像分析概述n在數(shù)字圖像處理與應(yīng)用中，人們可能對(duì)圖像中的某部分目標(biāo)或?qū)ο蟾信d趣。圖像分析主要是針對(duì)圖像中感興趣的特定目標(biāo)進(jìn)行檢測(cè)和測(cè)量以獲得目標(biāo)的客觀信息，建立對(duì)圖像的一種描述。圖像分析步驟n圖像分析步驟q從圖像中找到感興趣的目標(biāo)。把圖像分割成不同的區(qū)域或把不同的對(duì)象分開。n必須進(jìn)行圖像分割的研究q找出分開的各區(qū)域的特征。每個(gè)目標(biāo)或區(qū)域由于某些特征的不同于其他區(qū)域區(qū)別開來，邊緣、紋理、形狀、顏色等是重要的圖像特征。n圖像分割離不開圖像特征及其提取的研究q識(shí)別圖像中要找的對(duì)象或?qū)D像進(jìn)行分類。n圖像模式識(shí)別研究q對(duì)不同區(qū)域進(jìn)行描述或?qū)?/p>

2、找出不同區(qū)域的相互聯(lián)系，進(jìn)而找出相似結(jié)構(gòu)或?qū)⑾嚓P(guān)區(qū)域連成一個(gè)有意義的結(jié)構(gòu)n對(duì)每個(gè)提取出的目標(biāo)或區(qū)域要進(jìn)行有效的表示，需要研究形狀分析、表示與描述方法圖像分割n圖像分割的概念：把圖像分成互不重疊的區(qū)域并提取感興趣目標(biāo)的技術(shù)q分割目的是把圖像空間分成一些有意義的區(qū)域。n例如一幅航空照片，分割成工業(yè)區(qū)、住宅區(qū)、湖泊、森林等n可以逐個(gè)像素為基礎(chǔ)去研究圖像分割，也可以利用在規(guī)定領(lǐng)域中的某些圖像信息去分割。圖像分割解釋n圖像分割滿足以下條件：q1、對(duì)一幅圖像的分割結(jié)果中，全部區(qū)域的總和（并集）應(yīng)能包括圖像中所有像素q2、分割結(jié)果中各個(gè)區(qū)域是互不重疊的，或者說一個(gè)像素不能同時(shí)屬于兩個(gè)區(qū)域q3、屬于同一區(qū)域的

3、像素應(yīng)該具有某些共同的性質(zhì)q4、屬于不同區(qū)域的像素應(yīng)該具有不同的性質(zhì)q5、要求分割結(jié)果中同一個(gè)區(qū)域的任意兩個(gè)像素在該區(qū)域內(nèi)互相連通圖像分割方法n基于不同的圖像，已經(jīng)出現(xiàn)很多圖像分割方法，從分割途徑上有：q基于邊緣的分割方法n先提取區(qū)域邊界，再確定邊界限定的區(qū)域。先提取區(qū)域邊界，再確定邊界限定的區(qū)域。q區(qū)域分割n確定每個(gè)像素的歸屬區(qū)域，從而形成一個(gè)區(qū)域圖。確定每個(gè)像素的歸屬區(qū)域，從而形成一個(gè)區(qū)域圖。q區(qū)域生長(zhǎng)n將屬性接近的連通像素聚集成區(qū)域?qū)傩越咏倪B通像素聚集成區(qū)域q分裂合并分割n綜合利用前兩種方法，既存在圖像的劃分，又有圖像的合綜合利用前兩種方法，既存在圖像的劃分，又有圖像的合并。并。7.

4、2 邊緣檢測(cè)算子基于邊緣的分割方法：先提取區(qū)域邊界，先提取區(qū)域邊界，再確定邊界限定的區(qū)域。再確定邊界限定的區(qū)域。邊緣檢測(cè)的基本原理n邊緣檢測(cè)的基本原理q邊緣檢測(cè)是所有基于邊界的圖像分割的第一步。兩個(gè)具有不同灰度值的相鄰區(qū)域之間總存在邊緣。邊緣是灰度不連續(xù)的結(jié)果，這種不連續(xù)可利用求導(dǎo)數(shù)方便地檢測(cè)到，一般常用一階和二階導(dǎo)數(shù)來檢測(cè)邊緣。圖像邊緣n邊緣的定義q圖像中像素灰度有階躍變化或屋頂變化的那些像素圖像中像素灰度有階躍變化或屋頂變化的那些像素的集合，或者說的集合，或者說邊緣是灰度不連續(xù)的結(jié)果。n邊緣的分類q階躍狀階躍狀n階躍狀邊緣處于圖像中兩個(gè)具有不同灰度值的相嶺區(qū)域之階躍狀邊緣處于圖像中兩個(gè)具有

5、不同灰度值的相嶺區(qū)域之間間q屋頂狀屋頂狀n屋頂狀邊緣的上升下降沿都比較緩慢。屋頂狀邊緣的上升下降沿都比較緩慢。兩種圖像邊緣和邊緣點(diǎn)近旁灰度方向?qū)?shù)變化規(guī)律階躍狀屋頂狀圖像邊緣7.2 邊緣檢測(cè)算子n對(duì)邊緣的檢測(cè)可借助空域微分算子（導(dǎo)數(shù)）通過卷積來完成。實(shí)際數(shù)字圖像處理中是利用差分近似微分來進(jìn)行的n計(jì)算局部微分算子q一階微分：用梯度算子來計(jì)算q二階微分：通過拉普拉斯來計(jì)算邊緣檢測(cè)算子：幾種常用的邊緣檢測(cè)算子n梯度算子nRoberts算子nPrewitt算子nSobel算子nKirsch算子nLaplacian算子nMarr算子梯度算子n梯度算子是一階導(dǎo)數(shù)算子。n對(duì)一個(gè)連續(xù)函數(shù)f(x,y)，它在(x

6、,y)處的梯度為一個(gè)向量：qf = f / x , f / yn計(jì)算這個(gè)向量的大小為：qG = (f / x)2 +(f / y)21/2q近似為:G |fx| + |fy| 或 G max(|fx|, |fy|)n梯度的方向角為：q(x,y) = tan-1(fy / fx)n可用下圖所示的模板表示-111-1梯度算子n為了檢測(cè)邊緣點(diǎn)，選取適當(dāng)?shù)拈撝礣，對(duì)梯度圖像進(jìn)行二值化，則有：其它 0)Grad( 1),(Tx,yyxgn這樣形成了一幅邊緣二值圖像g(x,y)n特點(diǎn)：僅計(jì)算相鄰像素的灰度差，對(duì)噪聲比較敏感，無法抑止噪聲的影響。梯度算子原始圖像Roberts算子Roberts對(duì)應(yīng)的模板如圖

7、所示：-1 -1 11 Roberts梯度算子差分計(jì)算式如下：fx =|f(x+1,y+1)-f(x,y)|fy =|f(x+1,y)-f(x,y+1)|特點(diǎn)：與梯度算子檢測(cè)邊緣的方法類似，對(duì)噪聲敏感，但效果較梯度算子略好梯度算子Roberts算子原始圖像Roberts算子計(jì)算示例Prewitt算子n為減少噪聲的影響，Prewitt從加大邊緣增強(qiáng)算子的模板大小出發(fā)，由2x2擴(kuò)大到3x3來計(jì)算差分n模板：0-110-110-11-1-1-1000111n公式) 1, 1() 1,() 1, 1() 1, 1() 1,() 1, 1() 1, 1(), 1() 1, 1() 1, 1(), 1()

8、 1, 1(yxfyxfyxfyxfyxfyxffyxfyxfyxfyxfyxfyxffyxn特點(diǎn)：在檢測(cè)邊緣的同時(shí)，能抑止噪聲的影響Prewitt算子計(jì)算示例Sobel算子nSobel在Prewitt算子的基礎(chǔ)上，對(duì)4-鄰域采用加加權(quán)權(quán)的方法計(jì)算差分，對(duì)應(yīng)的模板如圖。n模板：n公式n特點(diǎn)：對(duì)4鄰域采用帶權(quán)方法計(jì)算差分，能進(jìn)一步抑止噪聲，但檢測(cè)的邊緣較寬-220-110-110000-1-1-2112) 1, 1() 1,(2) 1, 1() 1, 1() 1,(2) 1, 1() 1, 1(), 1(2) 1, 1() 1, 1(), 1(2) 1, 1(yxfyxfyxfyxfyxfyxf

9、fyxfyxfyxfyxfyxfyxffyxSobel算子示例不同算子的圖像邊緣檢測(cè)結(jié)果原始圖像robertprewittsobel專門檢測(cè)對(duì)角線邊緣的prewitt和sobel算子用于檢測(cè)對(duì)角線邊緣的prewitt和sobel算子方向微分算子n方向微分算子是基于特定方向上的微分來檢測(cè)邊緣，它先辨認(rèn)像素為可能的邊緣元素，再給它賦予預(yù)先定義的若干個(gè)方向之一。q空域中，方向微分算子利用一組模板與圖像進(jìn)行卷積來分別計(jì)算不同方向上的差分值，取其中最大的值作為邊緣強(qiáng)度，而將與之相應(yīng)的方向作為邊緣方向。q實(shí)際上每個(gè)模板會(huì)對(duì)應(yīng)兩個(gè)相反的方向，所以最后還需要根據(jù)卷積值的符號(hào)來確定其中之一Kirsch算子及特點(diǎn)

10、分析nKirsch算子是一種方向算子，利用一組8個(gè)模板對(duì)圖像中的同一像素作卷積，選取其中最大的值作為邊緣強(qiáng)度，而將與之相應(yīng)的方向作為邊緣方向q如果取最大值的絕對(duì)值為邊緣強(qiáng)度，并用考慮最大值符號(hào)的方法來確定相應(yīng)的邊緣方向，則考慮到各模板的對(duì)稱性，只要有前四個(gè)模板就可以了。nKirsch算子的特點(diǎn)q在計(jì)算邊緣強(qiáng)度的同時(shí)可以得到邊緣的方向q各方向間的夾角為45Kirsch算子模板3-530-533-533330-53-5-53333033-5-5-533303-5-53-533-503-533-5-53-503-5333-5-5-5033333-5-530-53333Kirsch算子的方向模板可以有

11、不同的尺寸，如5*5模板Nevitia算子Nevitia算子也是一種方向算子，共有12個(gè)5*5的模板，其中前6個(gè)如上圖所示，另6個(gè)可由對(duì)稱性得到，方向夾角30度。方向微分算子的方向也可以不局限于8個(gè)，也可以有12方向模板等Laplacian算子nLaplacian算子是一種常用的二階導(dǎo)數(shù)算子，實(shí)際中可根據(jù)二階導(dǎo)數(shù)過0點(diǎn)的性質(zhì)確定邊緣的位置；并且邊緣點(diǎn)兩旁像素的二階導(dǎo)數(shù)異號(hào)。n二維函數(shù)f(x,y)在(x,y)點(diǎn)的拉普拉斯值是定義為： 2f= 2f / x2 + 2f / y2n在數(shù)字圖像中，可由下式計(jì)算每個(gè)像素的x方向和y方向上的二階偏導(dǎo)數(shù)之和：q2f =f(x+1,y)+f(x-1,y)+f(

12、x,y+1)+f(x,y-1)-4f(x,y)q該式即為著名的Laplacian算子，它是一個(gè)與方向無關(guān)的各向同性的邊緣檢測(cè)算子，對(duì)應(yīng)的模板如下圖（見下頁）：拉普拉斯算子n定義數(shù)字形式的拉普拉斯的基本要求是：系數(shù)之和必為0。n可以用多種方式被表示為數(shù)字形式。對(duì)于一個(gè)3x3的區(qū)域，上式是經(jīng)驗(yàn)上被推薦最多的形式。11-4001001-1-1400-100-111-8111111-1-18-1-1-1-1-1-1拉普拉斯算子n拉普拉斯算子的分析：q優(yōu)點(diǎn)：n各向同性、線性和位移不變的；n對(duì)細(xì)線和孤立點(diǎn)檢測(cè)效果較好。q缺點(diǎn)：n對(duì)噪音的敏感，對(duì)噪聲有雙倍加強(qiáng)作用；n不能檢測(cè)出邊的方向；n常產(chǎn)生雙像素的邊緣

13、。q由于梯度算子和Laplace算子都對(duì)噪聲敏感，因此一般在用它們檢測(cè)邊緣前要先對(duì)圖像進(jìn)行平滑。檢測(cè)效果分析n利用Laplacian算子檢測(cè)圖像Laplacian算子原始圖像Marr算子nMarr算子是在Laplacian算子的基礎(chǔ)上實(shí)現(xiàn)的，它得益于對(duì)人的視覺機(jī)理的研究，有一定的生物學(xué)和生理學(xué)意義。n由于Laplacian算子對(duì)噪聲比較敏感，為了減少噪聲影響，可先對(duì)圖像進(jìn)行平滑，然后再用Laplacian算子檢測(cè)邊緣。n平滑函數(shù)應(yīng)能反映不同遠(yuǎn)近的周圍點(diǎn)對(duì)給定像素具有不同的平滑作用，因此，平滑函數(shù)采用正態(tài)分布的高斯函數(shù)，即：2222),(yxeyxh其中是方差。用h(x,y)對(duì)圖像f(x,y)的

14、平滑可表示為：*代表卷積。令r是離原點(diǎn)的徑向距離，即r2=x2+y2。對(duì)圖像g(x,y)采用Laplacian算子進(jìn)行邊緣檢測(cè)，并根據(jù)卷積微分/導(dǎo)數(shù)性質(zhì)，可得：這樣，利用二階導(dǎo)數(shù)算子過零點(diǎn)的性質(zhì)，可確定圖像中階躍邊緣的位置。 稱為高斯拉普拉斯濾波算子，也稱為L(zhǎng)OG濾波器，或“墨西哥草帽”。),(*),(),(yxfyxhyxg22r2222242( , )*( , )()*( , ) *( , )rgh x yf x yef x yhf x y h2Marr算子一維LOG函數(shù)及其變換函數(shù)二維LOG函數(shù)Marr算子2h-由于的平滑性質(zhì)能減少噪聲的影響，所以當(dāng)邊緣模糊或噪聲較大時(shí)，利用 檢測(cè)過零點(diǎn)

15、能提供較可靠的邊緣位置。在該算子中，的選擇很重要， 小時(shí)邊緣位置精度高，但邊緣細(xì)節(jié)變化多； 大時(shí)平滑作用大，但細(xì)節(jié)損失大，邊緣點(diǎn)定位精度低。應(yīng)根據(jù)噪聲水平和邊緣點(diǎn)定位精度要求適當(dāng)選取。Marr算子h2(a)原圖 (b)2h結(jié)果(c)正值為白，負(fù)值為黑 (d)過零點(diǎn) (邊緣所在處)利用2h檢測(cè)過零點(diǎn)曲面擬合法n出發(fā)點(diǎn)q基于差分檢測(cè)圖像邊緣的算子往往對(duì)噪聲敏感。因此對(duì)一些噪聲比較嚴(yán)重的圖像就難以取得滿意的效果。q在噪聲比較嚴(yán)重的圖像中，可以取某像素點(diǎn)(i,j)的一些鄰域點(diǎn)做曲面擬合，然后用曲面中心點(diǎn)(i,j)的梯度來近似代替該點(diǎn)的梯度，從而減輕噪聲的影響。n四點(diǎn)擬合灰度表面法q用一平面p(x,y)

16、=ax+by+c來擬合空間四鄰像素的灰度值f(x,y)、f(x,y+1)、f(x+1,y)、f(x+1,y+1)。q取擬合誤差為： 2),(),(yxfyxp按擬合測(cè)度誤差最小準(zhǔn)則，將上式分別對(duì)a,b,c求導(dǎo)，并令其等于0，可解出參數(shù)a , b , c?？赏茖?dǎo)出：按梯度的定義，由平面p(x,y)=ax+by+c的偏導(dǎo)數(shù)很容易求得梯度。可得梯度值為(a2+b2)1/2,可用(|a|+|b|)來近似，或者max(|a|,|b|)來近似。由a和b的表達(dá)式可以看出，a為兩行像元平均值的差分，b為兩列像元平均值的差分。相當(dāng)于先平滑再求差分，所以對(duì)噪聲不敏感。 ) 1,(), 1(),(341), 1()

17、,() 1, 1() 1,(21) 1,(),() 1, 1(), 1(21yxfyxfyxfcyxfyxfyxfyxfbyxfyxfyxfyxfa曲面擬合法這種運(yùn)算可簡(jiǎn)化為模板求卷積進(jìn)行，計(jì)算a和b對(duì)應(yīng)的模板如下：111/211111/211曲面擬合法n特點(diǎn)q其過程是求平均后再求差分，因而對(duì)噪聲有抑制作用。例子梯度算子Roberts算子Prewitt算子Sobel算子Kirsch算子原始圖像例子Laplacian算子Marr算子曲面擬合法7.3 邊緣跟蹤將檢測(cè)的邊緣點(diǎn)連接成線就是邊緣跟蹤。一般地做法是：從梯度圖像中一個(gè)邊緣點(diǎn)出發(fā)，依次搜索并連接相鄰邊緣點(diǎn)，逐步檢測(cè)出邊界。7.3 邊緣跟蹤n出

18、發(fā)點(diǎn)q由于噪音的原因，邊界的特征很少能夠被完整地描述，在亮度不一致的地方會(huì)中斷。q因此典型的邊檢測(cè)算法后面總要跟隨著連接過程和其它邊界檢測(cè)過程，用來歸整邊像素，成為有意義的邊。n由邊緣形成線特征的兩個(gè)過程q可構(gòu)成線特征的邊緣提取q將邊緣連接成線n連接邊緣的方法q光柵跟蹤掃描q全向跟蹤光柵掃描跟蹤n是一種采用電視光柵行掃描順序，結(jié)合門限檢測(cè)，對(duì)遇到的像素進(jìn)行分析，從而確定是否為邊緣的跟蹤方法。n具體步驟：q(1)確定一個(gè)比較高的閾值d，把高于該閾值的像素作為對(duì)象點(diǎn)。稱該閾值為“檢測(cè)閾值” 。q(2)用檢測(cè)閾值d對(duì)圖像第一行像素進(jìn)行檢測(cè)，凡超過d的點(diǎn)都接受為對(duì)象點(diǎn)，并作為下一步跟蹤的起始點(diǎn)。q(3

19、)選取一個(gè)比較低的閾值作為跟蹤閾值，該閾值可以根據(jù)不同準(zhǔn)則來選擇。例如，取相鄰對(duì)象點(diǎn)之灰度差的最大值作為跟蹤閾值，有時(shí)還利用其他參考準(zhǔn)則，如梯度方向、對(duì)比度等。q(4)確定跟蹤?quán)徲颉Ｈ∠袼?i，j)的下一行像素(i+1，j-1)，(i+1，j)，(i+1，j+1)為跟蹤?quán)徲?。光柵掃描跟蹤q(5)掃描下一行像素，凡和上一行已檢測(cè)出來的對(duì)像點(diǎn)相鄰接的像素，其灰度差小于跟蹤閾值的，都接受為對(duì)象點(diǎn)，反之去除。q(6)對(duì)于已檢測(cè)出的某一對(duì)象點(diǎn)，如果在下一行跟蹤領(lǐng)域中，沒有任何一個(gè)像素被接受為對(duì)象點(diǎn)，那么，這一條曲線的跟蹤便可結(jié)束。如果同時(shí)有兩個(gè)，甚至三個(gè)鄰域點(diǎn)均被接受為對(duì)象點(diǎn)，則說明曲線發(fā)生分支，跟蹤將

20、對(duì)各分支同時(shí)進(jìn)行。如果若干分支曲線合并成一條曲線，則跟蹤可集中于一條曲線上進(jìn)行。一曲線跟蹤結(jié)束后，采用類似上述步驟從第一行的其他檢出點(diǎn)開始下一條曲線的跟蹤。q(7)對(duì)于未被接受為對(duì)象點(diǎn)的其他各行像素，再次用檢測(cè)閾值進(jìn)行檢測(cè)，并以新檢出的點(diǎn)為起始點(diǎn)，重新使用跟蹤閾值程序，以檢測(cè)出不是從第一行開始的其他曲線。q(8)當(dāng)掃描完最后一行時(shí)，跟蹤便可結(jié)束。光柵掃描跟蹤光柵掃描跟蹤n由結(jié)果可以看出，本例原圖像中存在著三條曲線，兩條從頂端開始，一條從中間開始。然而，如果不用跟蹤法，只用一種閾值d或t檢測(cè)均不能得到滿意的結(jié)果。光柵掃描跟蹤n檢測(cè)和跟蹤所選擇的特征可以是其他反映局部性質(zhì)的量，例如對(duì)比度、梯度等。

21、n每個(gè)點(diǎn)所對(duì)應(yīng)的鄰域也可以取其他的定義，不一定是緊鄰的下一行像素，稍遠(yuǎn)一些的領(lǐng)域也許對(duì)于彌合曲線的間隙更有好處。n跟蹤準(zhǔn)則也可以不僅僅針對(duì)每個(gè)已檢測(cè)出的點(diǎn)，而是針對(duì)已檢出的一組點(diǎn)。根據(jù)情況決定檢測(cè)點(diǎn)是決定接收或拒絕。光柵掃描跟蹤n光柵掃描跟蹤和掃描方向有關(guān)，因此最好沿其他方向再跟蹤一次，例如逆向跟蹤，并將兩種跟蹤的結(jié)合綜合起來能得到更好的結(jié)果。另外，若邊緣和光柵掃描方向平行時(shí)效果不好，則最好在垂直掃描方向跟蹤一次，它相當(dāng)于把圖像轉(zhuǎn)置90o后再進(jìn)行光柵掃描跟蹤。全向跟蹤n能使跟蹤方向不僅局限于逐行(或列)的光柵式掃描，譬如說，在從上而下(或自左而右)的掃描過程中，也可以向上(或向左)跟蹤，那么就

22、會(huì)克服光柵跟蹤依賴于掃描方向的缺點(diǎn)。這可以通過定義不同鄰域的方法來實(shí)現(xiàn)。同樣，如果我們選取的跟蹤準(zhǔn)則能夠辨別遠(yuǎn)非緊鄰的像素，那么光柵跟蹤會(huì)漏掉平行于掃描方向曲線的缺點(diǎn)也能得到適當(dāng)?shù)乜朔?。n全向跟蹤就是跟蹤方向可以是任意方向，并且有足夠大的跟蹤距離的跟蹤方法。顯然，全向跟蹤是改變了鄰域定義和跟蹤準(zhǔn)則的一種光柵跟蹤法。全向跟蹤n具體步驟：q(1)按光柵掃描方式對(duì)圖像進(jìn)行掃描，用檢測(cè)閾值找出一個(gè)起始跟蹤的流動(dòng)點(diǎn)(沿被檢測(cè)曲線流動(dòng))。q(2)選取一個(gè)適當(dāng)?shù)摹⒛苓M(jìn)行全向跟蹤的鄰域定義(例如八鄰域)和一個(gè)適當(dāng)?shù)母櫆?zhǔn)則(例如灰度閾值、對(duì)比度和相對(duì)流動(dòng)點(diǎn)的距離等)，對(duì)流動(dòng)點(diǎn)進(jìn)行跟蹤。在跟蹤過程中，若：n(a

23、)遇到了分支點(diǎn)或者若干曲線的交點(diǎn)(即同時(shí)有幾個(gè)點(diǎn)都跟蹤一個(gè)流動(dòng)點(diǎn))，則先取其中和當(dāng)前流動(dòng)點(diǎn)性質(zhì)最接近的作為新的流動(dòng)點(diǎn)，繼續(xù)進(jìn)行跟蹤。而把其余諸點(diǎn)存儲(chǔ)起來，以備后面繼續(xù)跟蹤。如果在跟蹤過程中又遇到了新的分支或交叉點(diǎn)，則重復(fù)上面的處理步驟。當(dāng)按照跟蹤準(zhǔn)則沒有未被檢測(cè)過的點(diǎn)可接受為對(duì)象點(diǎn)時(shí)，一個(gè)分支曲線的跟蹤便已結(jié)束。n(b)在一個(gè)分支曲線跟蹤完畢以后，回到最近的一個(gè)分支點(diǎn)處，取出另一個(gè)性質(zhì)最接近該分支點(diǎn)的像素作為新的流動(dòng)點(diǎn)，重復(fù)上述跟蹤程序。n(c)當(dāng)全部分支點(diǎn)處的全部待跟蹤點(diǎn)均已跟蹤完畢，便返回第一步，繼續(xù)掃描，以選取新的流動(dòng)點(diǎn)(不應(yīng)是已接收為對(duì)象的點(diǎn))。q(3)當(dāng)整幅圖像掃描完成時(shí)，跟蹤程序便

24、結(jié)束。全向跟蹤n特點(diǎn)：q全向跟蹤改進(jìn)了光柵掃描跟蹤法，跟蹤時(shí)把初始點(diǎn)的八鄰點(diǎn)全部考慮進(jìn)行跟蹤。n改變了跟蹤方向n改變了跟蹤?quán)徲?.4 Hough變換線檢測(cè)法Hough變換方法是利用圖像全局特征而直接檢測(cè)目標(biāo)輪廓，其在預(yù)先知道區(qū)域形狀的情況下，可以方便地得到邊界曲線而將不連續(xù)的邊緣像素點(diǎn)連接起來基本Hough原理nHough變換是一種特殊的在不同空間之間進(jìn)行的變換。設(shè)在圖像空間有一個(gè)目標(biāo)，其輪廓可用代數(shù)方程表示，代數(shù)方程中既有圖像空間坐標(biāo)的變量也有屬于參數(shù)空間的參數(shù)。 Hough變換就是圖像空間和參數(shù)空間之間的一種變換?；綡ough原理n在圖像空間X-Y中，所有過點(diǎn)(x,y)的直線都滿足方程：

25、y=px+qn式中，參數(shù)p和q分別代表斜率和截距。如果已知參數(shù)值，則該點(diǎn)坐標(biāo)之間的關(guān)系即可確定。上述方程重新可表示為：q=-px+yn假定p和q是人們感興趣的參量，而x和y是參數(shù)，q=-px+y是參數(shù)空間P-Q中過Q點(diǎn)(p,q)點(diǎn)的一條直線。n因此，圖像空間X-Y中的一條直線和參數(shù)空間P-Q中的一點(diǎn)有一一對(duì)應(yīng)關(guān)系，這種關(guān)系稱為Hough變換。同理參數(shù)空間P-Q中的一條直線和圖像空間X-Y中的一點(diǎn)也有一一對(duì)應(yīng)關(guān)系基本Hough原理n假設(shè)給定直線y=p0 x+q0上任意3個(gè)點(diǎn)(xi,yi)，i=1,2,3，其中(x1,y1) (x2,y2)所對(duì)應(yīng)的參數(shù)空間中的兩條直線為、qq=-px1+y1qq=

26、-px2+y2n可以得到這兩條直線的交點(diǎn)為(p0,q0)n同理可以得到點(diǎn)(x2,y2)、 (x3,y3)這兩條直線的交點(diǎn)為(p0,q0)n由此可知，如果直線y=px+q上有n個(gè)點(diǎn)，那么這些點(diǎn)對(duì)應(yīng)參數(shù)空間P-Q上的一個(gè)直線簇，且所有直線相交于一點(diǎn)。利用這個(gè)性質(zhì)可以檢測(cè)共線點(diǎn)。n如果點(diǎn)(x,y)被映射到極坐標(biāo)上，那么直線上有n個(gè)點(diǎn)，這些點(diǎn)對(duì)應(yīng)極坐標(biāo)空間的n條正弦曲線，且所有正弦曲線交于一點(diǎn)。7.4 Hough變換檢測(cè)法n基本思想Hough變換檢測(cè)法基本思想1、對(duì)于邊界上的n個(gè)點(diǎn)的點(diǎn)集，找出共線的點(diǎn)集和直線方程。2、對(duì)于直角坐標(biāo)系中的一條直線l，可用、來表示該直線，且直線方程為： 。sincosyx

27、其中，為原點(diǎn)到該直線的垂直距離，為垂線與x軸的夾角，這條直線是唯一的。3、構(gòu)造一個(gè)參數(shù)(,) 的平面，從而有如下結(jié)論：對(duì)應(yīng)一條直線(,)直角坐標(biāo)系中的一條直線對(duì)應(yīng)極坐標(biāo)系中的一點(diǎn)，這種線到點(diǎn)的變換就是HoughHough變換變換 Hough變換檢測(cè)法基本思想nHough變換可以實(shí)現(xiàn)圖像直角坐標(biāo)空間和直線極坐標(biāo)空間之間的變換n這種圖像直角坐標(biāo)空間和直線極坐標(biāo)空間之間的變換具有以下性質(zhì)：q（1）(x,y)域中的一點(diǎn)對(duì)應(yīng)于變換域(,) 中的一條正弦曲線q（2）變換域(,) 中的一點(diǎn)對(duì)應(yīng)于(x,y)域中的一條直線q（3） (x,y)域中一條直線上的n個(gè)點(diǎn)對(duì)應(yīng)于變換域(,) 中經(jīng)過一個(gè)公共點(diǎn)的n條正弦曲

28、線。q（4）變換域(,) 中一條曲線上的n個(gè)點(diǎn)對(duì)應(yīng)于(x,y)域中過一個(gè)公共點(diǎn)的n條直線。Hough變換檢測(cè)法基本思想n綜上所述，由圖像空間的一點(diǎn)可以在參數(shù)空間做一曲線，如果由多個(gè)間斷點(diǎn)所做的多條曲線交于一點(diǎn)，則這些間斷點(diǎn)共線。Hough變換檢測(cè)法n算法實(shí)現(xiàn)思路q使用交點(diǎn)累加器，或交點(diǎn)統(tǒng)計(jì)直方圖，找出相交線段最多的參數(shù)空間的點(diǎn)，然后找出該點(diǎn)對(duì)應(yīng)的xy平面的直線線段。n算法步驟q1在、的極值范圍內(nèi)對(duì)其分別進(jìn)行m，n等分，形成一個(gè)二維數(shù)組，設(shè)一個(gè)二維數(shù)組的下標(biāo)（即每一個(gè)元素）對(duì)應(yīng)空間(,)中的一個(gè)網(wǎng)格(與i、j的取值對(duì)應(yīng))；q2數(shù)組中每個(gè)元素置初值0q3對(duì)空間(x,y)中的每個(gè)間斷點(diǎn)作Hough變

29、換，在對(duì)應(yīng)的空間(,)中產(chǎn)生一條曲線，曲線所經(jīng)過的每個(gè)網(wǎng)格的對(duì)應(yīng)數(shù)組元素，其值增加1。q4如果這些圖像空間點(diǎn)共線，則參數(shù)空間中的曲線必有交點(diǎn)，那么找出數(shù)組中的極大元素，該元素坐標(biāo)(,)所對(duì)應(yīng)的空間(x,y)中的直線就是所要檢測(cè)的少數(shù)間斷點(diǎn)形成的直線。q檢測(cè)出(x,y)平面上n點(diǎn)后，將曲線交點(diǎn)坐標(biāo)(0,0)帶入0 =xcos0+ysin0?？傻玫奖平黱點(diǎn)的直線方程。7.4 Hough變換檢測(cè)法n算法特點(diǎn)：q對(duì)、量化過粗，直線參數(shù)就不精確，過細(xì)則計(jì)算量增加。因此，對(duì)、量化要兼顧參數(shù)量化精度和計(jì)算量。qHough變換檢測(cè)直線的抗噪性能強(qiáng)，能將斷開的邊緣連接起來。q此外Hough變換也可用來檢測(cè)曲線。

30、 Hough變換曲線檢測(cè)n有hough變換值直線檢測(cè)可推導(dǎo)知，圖像空間中的一條已知的曲線方程也可以建立相應(yīng)的參數(shù)空間。所以圖形空間的一點(diǎn)，可經(jīng)過變換運(yùn)算在參數(shù)空間中產(chǎn)生相應(yīng)的軌跡曲線或曲面。n如果，對(duì)應(yīng)各個(gè)間斷點(diǎn)的曲線或曲面能夠相交，則表明圖像空間的諸間斷點(diǎn)的連線符合已知曲線。最后尋找參數(shù)空間的極大值，便可檢測(cè)出來。n如果曲線或曲面不相交，則表明圖像空間的諸間斷點(diǎn)的連線不符合某已知曲線。7.4 Hough變換檢測(cè)法nHough變換的擴(kuò)展qHough變換檢測(cè)曲線的關(guān)鍵是寫出由圖像空間到參數(shù)空間的變換公式。q如Hough變換用于圓曲線：（x a）2 + (y - b)2 = R2q參數(shù)空間可以表示

31、為(a,b,R)，這時(shí)需要三個(gè)參數(shù)(a,b,R)的參數(shù)空間。于是空間(x,y)的一個(gè)圓對(duì)應(yīng)參數(shù)空間的一個(gè)點(diǎn)(a,b,R)。q現(xiàn)在考慮空間(x,y)中的一個(gè)特定點(diǎn)(x0,y0),通過該點(diǎn)可以有許多圓，每一個(gè)圓都對(duì)應(yīng)參數(shù)空間(a,b,R)的一個(gè)點(diǎn)，所以圖像空間(x,y)中共點(diǎn)的多個(gè)圓在參數(shù)空間中對(duì)應(yīng)多個(gè)點(diǎn)，這些點(diǎn)便組成一圓錐曲面。q另外，通過空間(x,y)中的任一個(gè)點(diǎn)(xi,yi),可以有許多圓,共點(diǎn)(xi,yi)的多個(gè)圓在參數(shù)空間(a,b,R)中對(duì)應(yīng)多個(gè)點(diǎn)，也滿足（x a）2 + (y - b)2 = R2q而點(diǎn) (xi,yi)又是圓（x a0）2 + (y b0)2 =r02上的點(diǎn)，所以多個(gè)點(diǎn)

32、構(gòu)成的圓錐曲面必滿足（x a0）2 + (y b0)2 =r02。于是空間(x,y)中共圓的不同點(diǎn)(xi,yi)所對(duì)應(yīng)的圓錐曲面必在參數(shù)空間(a,b,R)中交于一點(diǎn)(a0, b0, r0)。因此該點(diǎn)(a0, b0, r0)所對(duì)應(yīng)的空間(x,y)中的圓便是所要檢測(cè)的圓。7.5 區(qū)域分割一幅圖像中屬于同一區(qū)域的像素應(yīng)具有相同或相似的屬性，不同區(qū)域的像素屬性不同。圖像的分割就要尋求具有代表性的屬性，利用這類屬性進(jìn)行劃分，使具有相同屬性的像素歸屬同一區(qū)域，不同屬性的像素歸屬不同區(qū)域。閾值分割法n閾值分割法是一種只利用一個(gè)圖像屬性的圖像分割方法。q閾值分割法的基本思想：n確定一個(gè)合適的閾值T。n將大于等

33、于閾值的像素作為物體或背景，生成一個(gè)二值圖像。If f(x,y) T set 255else set 0閾值分割法n閾值分割法q閾值分割法的特點(diǎn)：n適用于物體與背景有較強(qiáng)對(duì)比的情況，重要的是背景或物體的灰度比較單一。（可通過先求背景，然后求反得到物體）n這種方法總可以得到封閉且連通區(qū)域的邊界。峰谷法閾值分割n通過直方圖得到閾值Tq缺點(diǎn)：會(huì)受到噪音的干擾，最小值不是預(yù)期的閾值，而偏離期望的值；假定最簡(jiǎn)單圖像f(i,j)的灰度區(qū)間為0,l-1,選擇一閾值t將圖像的像素分為c1,c2兩組。判斷分析法閾值分割22111222( , )w ,m12( , )w ,mf i jtccf i jt像素?cái)?shù)為灰

34、度平均值為，方差為像素?cái)?shù)為灰度平均值為，方差為222211221212()()()bw mmw mmw w mm圖像總像素?cái)?shù)為w1+w2,灰度均值為m=(m1w1+m2w2)/(w1+w2)則組內(nèi)方差：則組間方差：2221122www顯然組內(nèi)方差越小，則組內(nèi)像素越相似，組間方差越大，則兩組的差別越大所以需要找一個(gè)閾值t使得t滿足22/bw最大閾值分割法：最佳熵自動(dòng)閾值法n最佳熵自動(dòng)閾值法q研究圖形灰度直方圖的熵測(cè)量，從此自動(dòng)找出最佳門限分割圖像。q從不同的角度出發(fā)，可以定義不同的熵測(cè)量以及選擇最佳門限方法。nKSW最佳熵自動(dòng)閾值法qKSW最佳熵自動(dòng)閾值法：Kapur提出的基于兩個(gè)分布假設(shè)的方法

35、n如果一幅圖像各灰度級(jí)出現(xiàn)的概率是p0,p1,p2,pn-1,根據(jù)信息論，各灰度級(jí)像素具有的信息量分別為：-log2p0,-log2p1,-log2p2,-log2pn-1,則該圖像的熵（平均信息量）為：102logniiippH閾值分割法：最佳熵自動(dòng)閾值法n假設(shè)圖像只含有背景和目標(biāo)，目標(biāo)的平均灰度大于背景的平均灰度。設(shè)分割閾值為t，pi為灰度i出現(xiàn)的概率。則對(duì)于圖像的灰度范圍0,l-1,0，t的像素分布和t+1,l-1的像素分布分別是：n設(shè)兩個(gè)分布分別對(duì)應(yīng)的熵為Hw(t)和HB(t),則0121231titit=0:,.,;:,.,;1111pPpttttttttLttttppppBPPPP

36、ppppWPPPP式中， 是各灰度級(jí)出現(xiàn)的頻率，其中 =011( )lnln/( )lnln(1)()/(1)11HH=-lni0,L1=-lni0,ttiiBtttttiLiittttti tiittiippH tPHPPPppHw tPHHPPPppHHpp 其中 為圖像總的信息熵 為背景物的信息熵。閾值分割法：最佳熵自動(dòng)閾值法nH為圖像總的信息熵，即為背景信息熵和目標(biāo)物信息熵之和。設(shè)兩個(gè)分布分別對(duì)應(yīng)的熵為Hw(t)和HB(t),011( )lnln/( )lnln(1)()/(1)11H=-lni0,L1=-lni0,t( )=( )( )ln/ln(1)()/(1)tiiBttttti

37、Liittttti tiitiiBttttttppH tPHPPPppHw tPHHPPPppHppH tHw tH tPHPPHHP 其中 n使得H(t)取最大值的t，就是分割目標(biāo)與背景的最佳閾值特征空間聚類n根據(jù)特征進(jìn)行模式分類是指根據(jù)提取的特征值將一組目標(biāo)劃分到各類中的技術(shù)。n將圖像空間中的元素按照從它們測(cè)得的特征值用對(duì)應(yīng)的特征空間點(diǎn)表示，將特征空間的點(diǎn)聚集成不同區(qū)域的類團(tuán)，再將它們分割開，并映射回原圖像空間得到分割的結(jié)果。n一般地閾值分割可視作是以像素的灰度為特征，灰度直方圖代表特征空間，用閾值將灰度直方圖特征空間劃分，把得到的特征類映射到圖像空間，不同灰度的像素構(gòu)成不同的區(qū)域。特征空

38、間聚類 k-均值聚類n將一個(gè)特征空間分成K個(gè)聚類的一種常用方法是k-均值聚類法。n令x=(x1,x2)代表一個(gè)特征空間的坐標(biāo)，g(x)代表在這個(gè)位置的特征值，k-均值聚類法主要是要最小化如下指標(biāo)：( )(1)21( )|( )|ijjijkijix QijjEg xuQu 式中，代表在第 次迭代后賦予類 的特征值表示第 類的均值。n上式的指標(biāo)給出每一個(gè)特征點(diǎn)與其對(duì)應(yīng)類均質(zhì)的距離和空間聚類 k-均值聚類nk-均值聚類步驟如下：n（1）任意選k個(gè)初始類均值，1(1), 2(1), 3(1), k(1).n（2）在第i次迭代時(shí)，根據(jù)下述準(zhǔn)則將每個(gè)特征點(diǎn)都賦予k類之一(j=1,2,k; l=1,2,k

39、,jl).( )(1)(1)l|( )|( )|iiiljxQg xug xu 如果即將每個(gè)特征點(diǎn)賦予均值離它最近的類n（3）使用步驟(2)中分類結(jié)果，對(duì)j=1,2,k, 更新類均值：( )j(1)( )j1g(x)iijx QjijuNNQ其中是中的特征點(diǎn)個(gè)數(shù)空間聚類 k-均值聚類n（4）如果對(duì)所有的j=1,2,k，有(1)( )iijjuu則算法收斂，結(jié)束；否則退回到步驟（ 2 ）繼續(xù)下一次迭代。7.6 區(qū)域增長(zhǎng)區(qū)域增長(zhǎng)n區(qū)域增長(zhǎng)是把圖像分割成若干小區(qū)域，比較相鄰小區(qū)域特征的相似性，若它們足夠相似，則作為同一區(qū)域合并，以此方式將特征相似的小區(qū)域不斷合并，直到不能合并為止，最后形成特征不同的

40、各區(qū)域。這種分割方式也稱區(qū)域擴(kuò)張法區(qū)域增長(zhǎng)n進(jìn)行區(qū)域增長(zhǎng)要解決三個(gè)問題q確定區(qū)域數(shù)目q選擇有意義的特征q確定相似性準(zhǔn)則n特征相似性是構(gòu)成與合并區(qū)域的基本準(zhǔn)則，相鄰性是指所采取的鄰域方式。區(qū)域增長(zhǎng)根據(jù)所采用的鄰域方式和相似性準(zhǔn)則的不同?？煞譃槿N區(qū)域增長(zhǎng)法：q單一型（像素與像素）q質(zhì)心型（像素與區(qū)域）q混合型（區(qū)域與區(qū)域）簡(jiǎn)單區(qū)域擴(kuò)張法n以圖像的某個(gè)像素為出發(fā)點(diǎn)，比較相鄰像素的特征，將特征相似的相鄰像素合并為同一區(qū)域；以合并的像素為生長(zhǎng)點(diǎn)，繼續(xù)重復(fù)以上的操作，最終形成具有相似特征的像素的最大連通集合。這種方法稱簡(jiǎn)單（單一型）區(qū)域擴(kuò)張法。n步驟：q（1）對(duì)圖像進(jìn)行光柵掃描，求出不屬于任何區(qū)域的像素，當(dāng)尋找不到這樣的像素時(shí)結(jié)束操作。q（2）把這個(gè)像素灰度同周圍（4-鄰域或8-鄰域）不屬于任何其他區(qū)域的像素進(jìn)行比較，若灰度差值小于閾值，則合并到同一區(qū)