一種基于元胞自動(dòng)機(jī)變換的圖像邊緣檢測(cè)方法

1、收稿日期:2007210212作者簡(jiǎn)介:金軍(19702,女,講師,博士生,從事計(jì)算機(jī)應(yīng)用、數(shù)字圖像處理研究;e 2mail :jsjxxqj 。第26卷第1期2008年2月石河子大學(xué)學(xué)報(bào)(自然科學(xué)版Journal of Shihezi University (Natural Science Vol.26No.1Feb.2008文章編號(hào):100727383(20080120113204一種基于元胞自動(dòng)機(jī)變換的圖像邊緣檢測(cè)方法金軍(四川大學(xué)計(jì)算機(jī)學(xué)院,四川成都610065摘要:提出了一種新的基于元胞自動(dòng)機(jī)變換的圖像邊緣檢測(cè)方法。應(yīng)用二維元胞自動(dòng)機(jī),首先確定合適的二維變換基函數(shù),然后對(duì)圖像進(jìn)行元胞

2、自動(dòng)機(jī)變換,將變換系數(shù)進(jìn)行子帶編碼,再根據(jù)基函數(shù)的性質(zhì),分離出變換系數(shù)中的高頻部分,最后經(jīng)過反變換得到圖像的邊緣信息。此算法簡(jiǎn)單實(shí)用,仿真實(shí)驗(yàn)結(jié)果較好。關(guān)鍵詞:邊緣檢測(cè);元胞自動(dòng)機(jī);元胞自動(dòng)機(jī)變換中圖分類號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A 邊緣是圖像對(duì)視覺的最主要的特征。邊緣檢測(cè)是圖像處理的關(guān)鍵,廣泛應(yīng)用于輪廓、特征的提取、紋理分析等領(lǐng)域,所以在圖像識(shí)別和分析中,物體邊緣的檢測(cè)和提取技術(shù)一直深受學(xué)者們的關(guān)注。元胞自動(dòng)機(jī)變換提供了一種把已知的現(xiàn)象和元胞自動(dòng)機(jī)演化聯(lián)系起來的直接方法,本文把元胞自動(dòng)機(jī)模型引入到圖像處理中,提出了一種新的基于元胞自動(dòng)機(jī)變換的圖像邊緣檢測(cè)方法。1元胞自動(dòng)機(jī)元胞自動(dòng)機(jī)(cell

3、ular automata ,C A 13是描述自然界復(fù)雜現(xiàn)象的一種簡(jiǎn)化數(shù)學(xué)模型,可以定義為在一個(gè)由離散、有限狀態(tài)的元胞組成的元胞空間上,并按照一定局部規(guī)則,在離散的時(shí)間維上演化的動(dòng)力學(xué)系統(tǒng)。元胞自動(dòng)機(jī)模型是以20世紀(jì)50年代馮諾依曼為模擬生物學(xué)中的自我復(fù)制而提出的。20世紀(jì)80年代W olfram 3對(duì)一維C A 模型做了深入全面的研究。但是關(guān)于C A 的基本理論從數(shù)學(xué)上深入研究十分困難,目前還處在通過大量的計(jì)算機(jī)實(shí)驗(yàn)來獲得經(jīng)驗(yàn)性規(guī)律和尋求具體應(yīng)用的階段,同時(shí)也出現(xiàn)了不少相關(guān)的應(yīng)用39。元胞自動(dòng)機(jī)按其元胞空間的維數(shù)可分為一維C A 、二維C A 和三維C A 。1個(gè)k 個(gè)狀態(tài)的一維C A由1

4、行元胞組成,每個(gè)元胞的狀態(tài)取0到k -1的任意1個(gè)整數(shù)值,局部規(guī)則控制r 鄰域內(nèi)m 個(gè)元胞在離散時(shí)間里同步演化,我們稱之為k 個(gè)狀態(tài)、m 個(gè)鄰居的元胞自動(dòng)機(jī);二維C A 不同于一維C A 的是,它是一個(gè)均勻的網(wǎng)格,網(wǎng)格形狀可以是三角形、正方形和六邊形,為便于計(jì)算機(jī)實(shí)現(xiàn),通常把網(wǎng)格限制為有限大小,運(yùn)用周期邊界來解決格子有限問題,鄰域類型通常是Von Neumann 型或M oore 型,如圖1所示,黑色元胞為中心元胞,灰色元胞為其鄰居。最簡(jiǎn)單的一維C A 的元胞個(gè)數(shù)為3,每個(gè)元胞的狀態(tài)值取0或1。設(shè)a it 、a i -1t 、a i +1t 分別表示第i 個(gè)、i -1個(gè)、i +1個(gè)元胞在t 時(shí)

5、刻的狀態(tài),在指定的局部規(guī)則下,可以根據(jù)t 時(shí)刻第i 個(gè)元胞的2個(gè)鄰居的狀態(tài)計(jì)算出t +1時(shí)刻第i 個(gè)元胞的狀態(tài)。元胞自動(dòng)機(jī)的演化過程可以表示為:a it +1=F (a i 21t ,a it ,a i +1t ,其中F 是布爾函數(shù)定義的局部規(guī)則。一個(gè)狀態(tài)數(shù)是2,鄰居個(gè)數(shù)是3的自動(dòng)機(jī),每個(gè)鄰居有 23=8個(gè)可能的構(gòu)型。按照W olfram 對(duì)規(guī)則的定義:R =67n =0C n 2n,(1式(1中,R 是0到255之間的1個(gè)整數(shù),表示規(guī)則,C n 是第n 個(gè)構(gòu)型通過規(guī)則作用產(chǎn)生的布爾值。圖1二維元胞自動(dòng)機(jī)的鄰域類型2元胞自動(dòng)機(jī)變換元胞自動(dòng)機(jī)變換(cellular automata trans

6、form, C AT由Olu Lafe4提出,目前已應(yīng)用于數(shù)據(jù)加密、解密和圖像壓縮10。在元胞空間中選擇1個(gè)合適的局部規(guī)則,將其作用于元胞自動(dòng)機(jī)的狀態(tài)演化域,從而產(chǎn)生1個(gè)“正交”的變換基函數(shù)(也稱為C A濾波器,可對(duì)數(shù)據(jù)或圖像進(jìn)行元胞自動(dòng)機(jī)變換?；瘮?shù)由一系列的“結(jié)構(gòu)塊”組成,也稱為“元素”或“變換基”。C AT能演化出大量不同性質(zhì)的基函數(shù),有些基函數(shù)所表現(xiàn)出的自生功能的性質(zhì)是其它變換(如小波變換所無法比擬的4,這些基函數(shù)可以適應(yīng)一些特定問題的要求。例如在圖像的邊緣檢測(cè)中,我們可以選擇這樣的基函數(shù)A,利用A對(duì)圖像進(jìn)行C AT,能得到圖像的高頻系數(shù)。應(yīng)用C AT來建立模型,方法和傳統(tǒng)的變換(傅立

7、葉變換、拉普拉斯變換和小波變換相同。假如數(shù)據(jù)序列f i表示1個(gè)圖像,f是定義在物理網(wǎng)格空間上的函數(shù),我們希望尋找定義在C A網(wǎng)格空間網(wǎng)格k上的基函數(shù)A和與基函數(shù)相關(guān)的變換系數(shù)C。C AT可表示為如下公式:f i=6kC k A ik,(2C k=6if i B ik。(3在物理網(wǎng)格i上的每一個(gè)點(diǎn)都有一個(gè)相應(yīng)的基函數(shù)A(跨越整個(gè)C A空間。式(2表示從過程f(在物理域到系數(shù)C(在C A域的一個(gè)映射,這個(gè)映射將基函數(shù)A作為傳遞函數(shù)。在許多應(yīng)用中,人們?cè)噲D得到一些變換系數(shù)C,使這些系數(shù)具有原函數(shù)f不具備的性質(zhì),或者能夠揭示函數(shù)f在物理域中沒有被觀察到的性質(zhì)。例如,在數(shù)據(jù)壓縮中,可以通過C A T揭示

8、原始數(shù)據(jù)的冗余,變換系數(shù)C中具有無意義或零的元素的數(shù)量,揭示了由C A檢測(cè)到的冗余的程度。有大量不同性質(zhì)的基函數(shù)存在,C AT的實(shí)質(zhì)是,對(duì)于一個(gè)特定的問題,總能找到一個(gè)合適的C A,它由其動(dòng)力學(xué)系統(tǒng)參數(shù)確定。C A按照給定的系統(tǒng)參數(shù)進(jìn)行離散時(shí)間演化,演化域被映射成變換基(即“結(jié)構(gòu)塊”,即針對(duì)特定的問題,總能夠得到期望的基函數(shù)和變換系數(shù)。典型的元胞自動(dòng)機(jī)系統(tǒng)參數(shù)見表1。對(duì)于N個(gè)元胞組成的一維元胞自動(dòng)機(jī),有無窮多種方法可以將A ik表示成C A狀態(tài)演化a it(其中, i,t=0,1,2,N-1的函數(shù)。對(duì)于二值狀態(tài)C A,Olu Lafe4給出了7類正交基函數(shù),其中T ype2型類非窗口C A基函

9、數(shù)為:A ik=2ikki-1。(4表1元胞自動(dòng)機(jī)系統(tǒng)參數(shù)K ey Description1在定義好的鄰居范圍內(nèi),元胞相互作用的規(guī)則2每個(gè)元胞允許的狀態(tài)范圍3每個(gè)鄰居內(nèi)的元胞個(gè)數(shù)4整個(gè)網(wǎng)格總共的元胞個(gè)數(shù)5元胞的初始構(gòu)型6元胞的邊界構(gòu)型7元胞空間或結(jié)構(gòu)的形狀8元胞空間的維度9元胞自動(dòng)機(jī)變換的種類10元胞自動(dòng)機(jī)的基的類型3二維元胞自動(dòng)機(jī)在由N×N個(gè)元胞組成的二維元胞空間中,設(shè)變換基AA ijkl,其中,i,j,k,l=0,1,N-1,數(shù)據(jù)序列f ij(i,j=0,1,N-1的C AT可表示為:f ij=6N-1k=06N-1l=0C kl A ijkl,(5其中,i,j=0,1,2,N-

10、1,c kl是變換系數(shù)。我們稱A ijkl為二維基。有二種產(chǎn)生二維基的方式:由二維C A狀態(tài)演化得到;由一維C A的基衍生得到二維C A的基:A ijkl=A ik A jl。本文采用第二種方式產(chǎn)生一種類二維基(T ype8型基:A ijkl=L w(ikki+jlljm od L w-(L w-1(6其中,L w2是C A的狀態(tài)數(shù)。當(dāng)元胞狀態(tài)取0或1時(shí),L w=2,則T ype8型二維基A ijkl可由T ype2型一維基A ik演化計(jì)算得到。目前,對(duì)C A T的研究還處于初級(jí)階段,并沒有像小波基那樣提出具體的命名基函數(shù)。本文基于邊緣檢測(cè)的目的,需要找到有利于獲取圖像高頻系數(shù)的A ijkl,

11、經(jīng)過多次實(shí)驗(yàn),選擇了C A系統(tǒng)參數(shù)(表2。表2產(chǎn)生Type8型A ijkl的CA系統(tǒng)參數(shù)元胞自動(dòng)機(jī)的基類型T ype8塊的大小8規(guī)則號(hào)43初始構(gòu)型01111110邊界構(gòu)型循環(huán)(cyclic演化出的64×8×8的基函數(shù)為見圖2,其中A00kl 表示左上角的塊,最上面一行表示0j<8,i=0;最左邊一列表示j=0,0i<8。A ij00表示每一個(gè)小塊的左上角點(diǎn),白色代表1(加,黑色代表-1(減。411石河子大學(xué)學(xué)報(bào)(自然科學(xué)版第26卷 圖2 類Type 8型二維基函數(shù)對(duì)應(yīng)的變換公式為:C kl =67i =067j =0f ij A jikl /8,(7f ij =

12、67k =067l =0C kl A jikl /8。(84基于元胞自動(dòng)機(jī)變換的邊緣檢測(cè)圖像元胞自動(dòng)機(jī)變換的許多特性可以在變換系數(shù)中得到體現(xiàn)。對(duì)一幅圖像進(jìn)行C A T ,得到的變換系數(shù)C 劃分成高頻部分和低頻部分,高頻部分反映的是圖像的邊緣變化與分布,代表圖像的邊緣信息,因此利用C A T 的高頻系數(shù)分量可以得到圖像的邊緣11。假設(shè)w 、h 為圖像f 的長(zhǎng)寬,滿足w =2n ,h =2m ,n 、m 都是整數(shù)。如果圖像的長(zhǎng)寬不滿足上述條件,則采用填充0的方法補(bǔ)充。a :一級(jí)C AT 變換系數(shù)b :二級(jí)C AT 變換系數(shù)圖3CAT 變換系數(shù)的分解設(shè)A 為N ×N 的二維基函數(shù),圖像f

13、的長(zhǎng)度為L(zhǎng) ,首先將f 分割成L/N 個(gè)不重疊的分割塊:f i =6N -1k =0C kj A (i m odN k,(9其中,i =0,1,2,L -1,j =0,1,2,(L/N -1。再將每個(gè)分割塊劃分成2(m +n /64個(gè)子塊,子塊由8×8個(gè)像素組成。對(duì)每個(gè)子塊利用如圖2所示的A ijkl 進(jìn)行C A T 變換 ,將得到的變換系數(shù)ckl 進(jìn)行子帶編碼,分解成、4個(gè)子帶:處于k 和l 都是偶數(shù)位置上的系數(shù)屬于子帶,處于k 是偶數(shù)l 是奇數(shù)位置上的系數(shù)屬于子帶,處于k 是奇數(shù)l 是偶數(shù)位置上的系數(shù)屬于子帶,處于k 和 l 都是奇數(shù)位置上的系數(shù)屬于子帶(圖3a 。根據(jù)二維基的性

14、質(zhì),4個(gè)子帶系數(shù)又分為二組:一組為低頻系數(shù),另一組為高頻系數(shù)。低頻系數(shù)存儲(chǔ)了大量的原圖像信息,將低頻系數(shù)分離出來進(jìn)行IC A T 變換可形成與原始圖像近似的低分辨率圖像,大小為2(n -12(m -1,可再次對(duì)其進(jìn)行C A T 變換,得到的變換系數(shù)再分解成4個(gè)子帶(圖3b ;將高頻系數(shù)分離出來進(jìn)行IC A T 變換形成原始圖像的邊緣圖像。5仿真實(shí)驗(yàn)對(duì)圖4a 的256×256的灰度圖像按上述方法進(jìn)行一級(jí)C AT ,得到4個(gè)子帶系數(shù),根據(jù)本文所用的A ijkl 的性質(zhì),子帶的系數(shù)是圖像的低頻系數(shù),子帶、的系數(shù)是圖像的高頻系數(shù)。分離出圖像的低頻系數(shù)進(jìn)行IC AT ,形成的原始圖像的低分辨率

15、近似圖像(圖4b 。a :原始圖像b :低分辨率近似圖像圖4原始圖像與低頻近似圖像分離出圖像的高頻系數(shù)進(jìn)行IC AT ,形成原始圖像的邊緣圖像,并與傳統(tǒng)的邊緣檢測(cè)算子得到的邊緣圖像進(jìn)行比較(圖5。從實(shí)驗(yàn)的仿真結(jié)果可以看到,C A T 檢測(cè)到的圖像邊緣比較細(xì)膩,邊緣定位比較準(zhǔn)確,丟失的邊緣信息少,視覺效果也較好,是一種實(shí)用的邊緣檢測(cè)方法。a :prewitt 算子邊緣圖像;b :roberts 算子邊緣圖像;c :s obel 算子邊緣圖像;d :log 算子邊緣圖像;e :本文C AT 邊緣圖像圖5邊緣圖像511第1期金軍:一種基于元胞自動(dòng)機(jī)變換的圖像邊緣檢測(cè)方法6小結(jié)本文提出了一種新的基于元

16、胞自動(dòng)機(jī)變換的圖像邊緣檢測(cè)方法,在未作其它處理的情況下,僅利用C AT變換系數(shù)的高頻部分來檢測(cè)圖像邊緣,取得了初步結(jié)果。仿真實(shí)驗(yàn)結(jié)果顯示,C AT的邊緣檢測(cè)結(jié)果優(yōu)于大多數(shù)傳統(tǒng)的邊緣檢測(cè)算子的檢測(cè)結(jié)果,并且C AT方法所運(yùn)用的C A模型及運(yùn)算操作都很簡(jiǎn)單,避免了大量的計(jì)算,是一種實(shí)用的圖像處理方法,其有效性使其具有良好的應(yīng)用前景。本文因只單純的利用了變換系數(shù)的高頻部分進(jìn)行邊緣檢測(cè),所以該方法對(duì)噪聲較為敏感。我們下一步的工作就是繼續(xù)對(duì)二維C A及C AT進(jìn)行研究,以期提高本文算法的抗噪性和提取邊緣的連續(xù)性。參考文獻(xiàn):1謝惠民.復(fù)雜性與動(dòng)力系統(tǒng)M.上海:上?？萍冀逃霭嫔?1994.2祝玉學(xué).物理系

17、統(tǒng)的元胞自動(dòng)機(jī)模擬M.北京:清華大學(xué)出版社,2003.3W olfram S.Theory and Applications of Cellular AutomataM.S ingapore:W orld Scientific Publishing C ompany,1986.4Olu Lafe.Cellular automata trans forms:Theory and applicationsin multimedia compression,encryption,and m odelingM.Bos2 ton D ordrecht London:K luwer Academic Pu

18、blishers,2000. 5李才偉.元胞自動(dòng)機(jī)及復(fù)雜系統(tǒng)的時(shí)空演化模擬D.武漢:華中理工大學(xué),1997.6葉瑞芳,黃春暉.基于摩爾近鄰模型的二維元胞自動(dòng)機(jī)在圖像處理中的應(yīng)用J.現(xiàn)代電子技術(shù),2006,(8:55257.7張傳武.細(xì)胞自動(dòng)機(jī)及其理論研究進(jìn)展J.貴州大學(xué)學(xué)報(bào),2004,21(3:2892293.8A K Das,A G anguly,A Dasgupta,et al,E fficient characteris2ation of cellular puter simulation,Digital comput2 ers and computationJ.IEE Proceedi

19、ngs,1990,137(1:81287.9Amr Badr.An alternative cellular automata cryptogramJ.S tudies in In formatics and C ontrol,2002,11(4:3392347. 10Olu Lafe.Data compression and encryption using cellular au2tomata trans formsJ.Engng Applic Artif Intell,1997,10(6: 5812591.11唐良瑞.基于小波高頻分量的邊緣檢測(cè)方法J.北方工業(yè)大學(xué)學(xué)報(bào),2002,14(1:13216.A Method of Edge DetectionB ased on Cellular Automata TransformsJ I N Jun(C ollege of C omputer Science,S ichuan University,Chengdu,S ichuan610065,ChinaAbstract:A new edge detection method based on cellular autom