基于元胞自動機的圖像邊緣檢測

何志明　苗水清　柴榮軍　徐雪萌

摘要：將圖像的方向信息測度和元胞自動機引入到多灰度級圖像邊緣提取中，可減少噪聲的影響，同時盡可能的去處偽邊緣。

關(guān)鍵字：元胞自動機 ?邊緣檢測 ?方向信息測度

1 引言

邊緣檢測是圖像處理和計算機視覺的一個重要組成部分，是圖像分析、輪廓提取、機器視覺的基礎(chǔ)，因此，它在視覺工程應(yīng)用中占有舉足輕重的地位，是目前機器視覺、圖像處理研究領(lǐng)域中較為活躍的課題之一。目前，主要使用的邊緣檢測算子有：Robert算子、Sobel算子、Prewitt算子、Laplacian，Canny算子等，他們大都是根據(jù)每個象素在其領(lǐng)域內(nèi)的灰度變化，然后用邊緣鄰近一階或二階方向?qū)?shù)變化規(guī)律進(jìn)行檢測邊緣，因此面臨較多的約束問題，同時存在計算量過大、處理效果不理想、抗噪性能較差等許多方面的缺陷，所以尋求一種計算簡單、易于實現(xiàn)、效果比較理想的圖像處理方法，已經(jīng)成為人們關(guān)注的熱點。

元胞自動機（cellular automata），簡稱CA。它主要根據(jù)空間、時間和狀態(tài)都離散的動力學(xué)系統(tǒng)來模擬和解決實際問題：因為二維圖像的像點正好可以對應(yīng)于二維CA的正方形網(wǎng)格點。所以，CA模型能夠在圖像處理領(lǐng)域中發(fā)揮作用。

結(jié)合CA和圖像邊緣的特征，我們提出了一種基于邊緣方向性的邊緣檢測CA模型。該模型主要用于普通灰度圖象的邊緣檢測，它既能較準(zhǔn)確的提取邊緣輪廓，而且可以得到較好的視覺效果。

2 基于方向信息測度的CA邊緣檢測原理與算法

2.1 元胞自動機

元胞自動機是定義在一個由具有離散、有限狀態(tài)的元胞組成的元胞空間上，并按照一定局部進(jìn)化規(guī)則，在離散的時間維上演化的動力學(xué)系統(tǒng)。構(gòu)成元胞自動機的部件被稱為“元胞（cell）”，每個元胞就是一個狀態(tài)：對應(yīng)于有限狀態(tài)集中的某一個狀態(tài)，如或“黑”或“白”，它們規(guī)則地排列在 “元胞空間”中;并且，狀態(tài)會隨著時間的變化而變化，也就是局部更新。換句話說：一個元胞在某時刻的狀態(tài)僅取決于上一時刻該元胞的狀態(tài)該元胞的所有鄰居元胞的狀態(tài);元胞機主要由元胞空間、元胞狀態(tài)、鄰居及局部演化規(guī)則構(gòu)成。我們可以用一個四元組（）來表示：Zn是n 維歐式空間; S 是有限狀態(tài)集合， ?，Si代表元胞自動機的第i 個狀態(tài);N 為中心元胞的鄰域，，Xi為相鄰元胞位置集;f為的演化規(guī)則，代表元胞狀態(tài)由t 時刻進(jìn)化為t+1 時刻的規(guī)則。

2.1.1 鄰域

局部演化規(guī)則的主要作用是將元寶空間中的元胞靜態(tài)成分"動態(tài)"引入到了系統(tǒng)中。但是，在此之前，需定義元胞的“鄰居”：確定該元胞的鄰居主要有哪些元胞構(gòu)成。一維元胞機的鄰居定義一般較為簡單，常以固定半徑來確定鄰居，一般情況下，我們認(rèn)為在中心元胞半徑內(nèi)的所有元胞均是該元胞的鄰居。而二維元胞機的鄰居的確定較為復(fù)雜，我們常用的主要有以下幾種方式：在圖1，黑色元胞為中心元胞，它周圍的灰色元胞即為它的鄰居，黑色元胞下一時刻的狀態(tài)將由它本身鄰居們共同確定。

Von. Neumann型鄰域主要由要演化的元胞和四個正方位的元胞構(gòu)成，如圖1（a）所示。這里，鄰居半徑 r為1，相當(dāng)于圖像處理中的四鄰域?？捎檬剑?）來描述：

（1）

Moore鄰域型主要由要演化的中心元胞和它四周的8個元胞共同構(gòu)成，如圖1（b）所示。同樣，近鄰半徑r = 1 ，相當(dāng)于圖像處理的八鄰域。可用式（2）來描述：

（2）

將Moore鄰域的半徑擴展為2或者更大，即可得到擴展的Moore鄰域。其鄰居定義如式（3）所示：

（3）

試驗表明，鄰域類型的不同會引起圖像邊緣檢測的不同效果。一般，使用Moore鄰域檢測的邊緣結(jié)果會比使用Von. Neumannn鄰域的清晰，特征點也更多。因此，在本實驗中，我們選擇半徑為1的Moore鄰域。

2.1.2演化規(guī)則

邊緣是指周圍像素灰度有階躍變化或屋頂變化的那些像素的集合。因此，我們需設(shè)計一個函數(shù)來量化某一像素與其鄰居像素間的灰度變化。該表達(dá)式可以表示為：

（4）

這里 表示圖像中第（i，j）個像素的灰度值。

由上式可知：在圖像區(qū)，其灰度值較為接近，所以X（i，j）值接近于0，邊緣點存在區(qū)域的X（i，j）的值比較大，若X（i，j）的值極大，那么該點則可能是噪聲點，但我們可以利用圖像的方向性信息測度對噪聲進(jìn)行抑制。

在采用CA進(jìn)行邊緣檢測時，為了使CA的演化能以較快速度達(dá)到穩(wěn)定狀態(tài)，我們需要設(shè)定合理的演化規(guī)則。我們預(yù)先設(shè)定閾值：，將X（i，j）的值與 比較：若X（i，j）大于則保持中心元胞的狀態(tài)不變，否則中心元胞狀態(tài)取0。

2.2 方向信息測度

檢測出的邊緣一般包含兩種邊緣：有效邊緣和錯誤邊緣。有效邊緣在空間分布上會呈現(xiàn)出有序性，即方向性;而錯誤邊緣大多數(shù)由早生引起，是孤立點引起的，因此錯誤邊緣是無方向性的，大多為隨機分布。因此我們可以借助方向信息測度來增強其抗噪性能。具體的方向信息測度定義如圖2 所示：

假定X 是一幅 M×N 且具有L 個灰度級的單色圖像或圖像區(qū)域， 是圖像的第（i，j） 個像素點的灰度值（i=1，2，…，M，j=1， 2，…，N）。（i， j）是當(dāng)前像素位置，鄰域為，l是半鄰域長度;是過中心點，且角度為的一條直線，該直線將鄰域R分成兩半，即S1和S2，則方向性圖象信息測度的定義為：

矩陣M=[Mij]，i =1，2，…，M，n=1，2，…，N，為圖像（矩陣）X的方向信息測度矩陣。

根據(jù)圖像邊緣的方向性，我們可知：在與邊緣基本同向時取得極大值，而在垂直于邊緣軌跡時取得極小值。此時Mij值較大。若當(dāng)前點屬于平滑區(qū)，則由于平滑區(qū)像素灰度值較接近，那么無論方向如何，的值都較為接近，因而Mij值較小。且與觀察尺度無關(guān)。而圖像中的噪聲是隨機的，不具有方向性，因此，不管方向的方向如何，它對Mij值的影響都不會太大。因此，我們可以認(rèn)為圖像的方向信息測度能夠較好地幫助我們檢測圖像的邊緣信息，而且對噪聲不敏感，能一定程度上減小噪聲對檢測的影響。因此，我們把方向信息測度加到圖像邊緣檢測中。