稀疏圖像表示和自然計算

1、1稀疏圖像表示和自然計算焦李成西安電子科技大學(xué)智能信息處理研究所2006.82報告內(nèi)容報告內(nèi)容l稀疏圖像表示l稀疏幾何圖像表示;l稀疏幾何表示域隱馬模型;l過完全稀疏表示.l自然計算l人工免疫系統(tǒng);l協(xié)同進(jìn)化;l粒子群優(yōu)化.3第一部分：稀疏圖像表示4小波分析的局限性l尋求客觀事物的“稀疏”表示方法, 一直是計算機(jī)視覺、數(shù)學(xué)、數(shù)據(jù)壓縮等領(lǐng)域的專家學(xué)者致力于的研究目標(biāo).l對于含“點(diǎn)奇異”的一維信號, 小波能達(dá)到最優(yōu)的非線性逼近階. 而在處理二維或者更高維含“線奇異”的信號時, 由一維小波張成的高維小波基不能達(dá)到最優(yōu)逼近階.l小波變換的不足使人們開始尋求更好的非線性逼近工具.5邊緣在小波的各個尺度上

2、擴(kuò)散6稀疏幾何表示l過去幾年,在數(shù)學(xué)分析、計算機(jī)視覺、模式識別、統(tǒng)計分析等不同學(xué)科中,分別獨(dú)立地發(fā)展著一種彼此極其相似的理論:多尺度幾何分析.發(fā)展多尺度幾何分析的目的是為了檢測、表示、處理某些高維奇異性. l對于二維圖像,奇異性主要由邊緣所刻畫,因此主要的任務(wù)是處理邊緣。目前,提出的多尺度幾何分析方法主要有: Ridgelet、Curvelet、Bandelet、Contourlet等.7小波和稀疏幾何方法在處理邊緣上的差異小波稀疏幾何表示8Ridgeletl脊波理論由Cands 在1998 年提出,是一種非自適應(yīng)的高維函數(shù)表示方法. l脊波變換對于具有直線奇異的多變量函數(shù)有良好的逼近性能,但

3、是, 對于含曲線奇異的多變量函數(shù),其逼近性能只相當(dāng)于小波變換.l為了解決含曲線奇異的多變量函數(shù)的稀疏逼近問題, Cands提出了單尺度脊波變換.單尺度脊波對于具有曲線奇異的多變量函數(shù)的逼近性能比小波有明顯的提高.9正交Ridgelet的圖示三維視圖俯視圖10CurveletlCurvelet變換由Cands和Donoho在1999 年提出, 其由脊波理論衍生而來.l單尺度脊波的基本尺度是固定的,而Curvelet變換則不然,其在所有可能的尺度上進(jìn)行分解,實際上Curvelet變換是由一種特殊的濾波過程和多尺度脊波變換組合而成.lCurvelet對于具有曲線奇異的多變量函數(shù)的逼近性能比單尺度脊波

4、有明顯的提高.11Contourletl2002 年,Do和Vetterli提出了一種圖像二維表示方法: Contourlet變換,也稱塔型方向濾波器. lContourlet變換繼承了Curvelet變換的各向異性尺度關(guān)系,因此,在一定意義上,可以認(rèn)為是Curvelet變換的另一種實現(xiàn)方式.lContourlet變換的最終結(jié)果是用類似于線段的基結(jié)構(gòu)來逼近原圖像,這也是所以稱之為Contourlet變換的原因.12小波基和Contourlet基小波基Contourlet基13Bandeletl2000年,Pennec和Mallat提出了Bandelet換. Bandelet變換是一種基于邊緣的

5、圖像表示方法,能自適應(yīng)地跟蹤圖像的幾何正則方向. l構(gòu)造Bandelet 變換的中心思想是定義圖像中的幾何特征為矢量場,而不是看成普通的邊緣的集合. 矢量場表示了圖像空間結(jié)構(gòu)的灰度值變化的局部正則方向. lBandelet基并不是預(yù)先確定的,而是以優(yōu)化最終的應(yīng)用結(jié)果來自適應(yīng)的選擇具體的基的組成.14Bandelet中定義的矢量場15存在的問題和進(jìn)一步研究的方向存在的問題和進(jìn)一步研究的方向l自適應(yīng)與非自適應(yīng)方法：自適應(yīng)與非自適應(yīng)方法：近幾年中,對于高維奇異函數(shù)的的逼近問題,一些研究者有這樣一種認(rèn)識: 相對于非自適應(yīng)方法,自適應(yīng)方法應(yīng)該具有更好的逼近性能.l然而，回想一維情況,小波變換對含點(diǎn)奇異的

6、分段光滑函數(shù)的表示是最優(yōu)的.但一維小波變換并不需要先驗地知道點(diǎn)奇異的具體位置,小波基的構(gòu)建并沒有自適應(yīng)于函數(shù)本身,即小波變換是一種非自適應(yīng)的函數(shù)表示方法.l圖像的多尺度幾何分析將以一種什么方式發(fā)展呢? 最終為人們所廣泛采用的方法是自適應(yīng)的還是非自適應(yīng)的呢? 這些問題值得我們深思.16存在的問題和進(jìn)一步研究的方向存在的問題和進(jìn)一步研究的方向l自適應(yīng)方法存在的問題：自適應(yīng)方法存在的問題：自適應(yīng)的多尺度幾何表示方法,實際上是邊緣檢測和圖像表示方法的結(jié)合.比如, Bandelet變換根據(jù)圖像邊緣自適應(yīng)地構(gòu)造了一種局部彎曲小波變換.于是,問題的關(guān)鍵歸結(jié)為怎樣剖分圖像,局部區(qū)域中如何“跟蹤”奇異方向等.l

7、然而,在自然圖像中,灰度值的突變并不總是對應(yīng)著物體的邊緣,一方面,衍射效應(yīng)使得圖像中物體的邊緣可能并不明顯地表現(xiàn)出灰度的突變;另一方面,許多時候圖像的灰度值劇烈變化是由于紋理的變化而產(chǎn)生的. l所有基于邊緣的自適應(yīng)方法需要解決的一個共同的問題,是如何確定圖像中灰度值劇烈變化的區(qū)域?qū)?yīng)的是物體邊緣還是紋理的變化,實際上這是一個非常困難的問題.17存在的問題和進(jìn)一步研究的方向存在的問題和進(jìn)一步研究的方向lCurveletCurvelet變換存在的問題：變換存在的問題：Curvelet變換提出的初衷是為了對高維空間中含奇異曲線或者曲面的函數(shù)進(jìn)行”稀疏”表示.而目前Curvelet變換的數(shù)字實現(xiàn)算法冗

8、余度很高, 因此實際的實現(xiàn)與提出Curvelet變換時的初衷產(chǎn)生了背離.lCurvelet在頻域定義,其空域的采樣特性并不顯而易見.l對于高階正則的奇異邊緣, Curvelet變換不能達(dá)到最優(yōu)的非線性逼近階, 而當(dāng)奇異邊緣是非正則的,其逼近性能甚至不如小波。18存在的問題和進(jìn)一步研究的方向存在的問題和進(jìn)一步研究的方向lContourletContourlet變換存在的問題：變換存在的問題：Contourlet變換是一種近似的Curvelet變換數(shù)字實現(xiàn)方式,走的卻是一條與Curvelet變換截然相反的技術(shù)路線. lContourlet變換首先直接在數(shù)字域中定義,再將數(shù)字域和連續(xù)域聯(lián)系起來,在連

9、續(xù)域中討論Contourlet變換的逼近性能. lContourlet變換具有比Curvelet變換少得多的冗余度, 然而,對于Contourlet變換,其數(shù)學(xué)基礎(chǔ)還有待進(jìn)一步完善.19存在的問題和進(jìn)一步研究的方向存在的問題和進(jìn)一步研究的方向l圖像模型：圖像模型：多尺度分析的結(jié)論都是基于自然圖像的簡化模型（如左圖）, 然而, 真正的自然圖像遠(yuǎn)比這個簡化模型更復(fù)雜.l對于更復(fù)雜的圖像模型, 如包含紋理的模型, 我們怎么處理呢? 還需建立怎樣的多尺度幾何表示方法呢? 對這些問題的回答將推動之一領(lǐng)域的發(fā)展.20小波域隱馬爾科夫模型l在基于子波的統(tǒng)計信號處理方法研究之初,許多學(xué)者都是將子波系數(shù)建模為高

10、斯形式,但高斯模型的假設(shè)與子波變換的壓縮特性相沖突.l壓縮特性意味著只有少量的系數(shù)包含信號的絕大部分能量,其余的系數(shù)對信號能量貢獻(xiàn)很小.這一特性說明子波系數(shù)的概率密度分布比通常的高斯分布在零值位置更尖,并在分布的兩端呈現(xiàn)明顯拖尾的趨勢.l從理論上講,完全建模所有子波系數(shù)的聯(lián)合概率密度函數(shù)可以準(zhǔn)確地刻畫系數(shù)間的統(tǒng)計相關(guān)性,但實際應(yīng)用時相當(dāng)復(fù)雜,也難以估.21小波域隱馬爾科夫模型l在實際應(yīng)用時我們需要在上述兩種假設(shè)之間做出合理的折衷,對系數(shù)之間關(guān)鍵的相關(guān)性做出準(zhǔn)確的描述,同時忽略次要因素.子波域隱馬爾科夫模型正是在這一想法的啟發(fā)下應(yīng)運(yùn)而生的并開辟了多尺度變換域統(tǒng)計信號處理這一新的研究領(lǐng)域.l子波域

11、隱馬爾科夫作為一種概率圖模型,是子波域統(tǒng)計信號與圖像處理的一種有效的工具. 借助于概率圖技術(shù),這種模型可以有效地描述子波系數(shù)的各種統(tǒng)計相關(guān)性.l到目前為止, 眾多學(xué)者提出了許多不同的變換域隱馬爾科夫模型,并廣泛地將這些模型應(yīng)用于圖像恢復(fù)和重建、圖像分割、圖像紋理分析與合成、圖像檢索、邊緣檢測、自動目標(biāo)識別、貝葉斯圖像分析和圖像水印等領(lǐng)域.22稀疏幾何表示域隱馬模型l隨著多尺度幾何分析研究領(lǐng)域的發(fā)展, 一些學(xué)者也在一些多尺度幾何變換域比如Contourlet變換域建立了隱馬爾科夫模型.l然而，我們應(yīng)該清醒地認(rèn)識到: 多尺度幾何變換域隱馬爾科夫模型的研究還處于起步階段,很多基本的問題還有待認(rèn)識清楚

12、.l如隱馬爾科夫模型是不是理想的多尺度幾何變換域統(tǒng)計模型？在多尺度幾何域有沒有更好的統(tǒng)計模型？相信這些問題的回答將大大推動該領(lǐng)域的發(fā)展。23過完全稀疏表示l過完全稀疏表示采用過完全函數(shù)系統(tǒng)代替?zhèn)鹘y(tǒng)的正交基函數(shù)。從過完全系統(tǒng)中找到具有最佳線性組合的m項原子來表示一個信號，被稱作是過完全稀疏表示.l過完全稀疏表示方法始于上世紀(jì)九十年代，1993年Mallat和Zhang首次提出了應(yīng)用過完全函數(shù)系統(tǒng)對信號進(jìn)行稀疏分解的思想,并引入了匹配追蹤算法.24基函數(shù)選擇算法l匹配追蹤：匹配追蹤：匹配追蹤是一個迭代的貪婪算法.在每一次迭代過程中，匹配追蹤從字典里選擇最能匹配信號結(jié)構(gòu)的一個基函數(shù)來構(gòu)建稀疏逼近.在

13、統(tǒng)計學(xué)領(lǐng)域，匹配追蹤被稱作投影跟蹤.l基追蹤：基追蹤：基追蹤利用了1范數(shù)能促使小系數(shù)收縮的零的特點(diǎn)，將基函數(shù)選擇問題轉(zhuǎn)化成線性規(guī)劃問題。25存在的問題和進(jìn)一步研究的方向存在的問題和進(jìn)一步研究的方向l要找到最好的M個基函數(shù)是一個組合優(yōu)化問題,由于計算量的原因,窮舉法是不可行的.l但是,匹配追蹤和基追蹤只能獲得該問題的近似解,因此一個公開的問題就是有沒有更好的,計算上可行的原子選擇算法,如何實現(xiàn)?l各算法的收斂性理論問題的研究才剛剛開始,誤差與逼近速率的關(guān)系仍是一個開放的問題.26自然計算為基函數(shù)選擇l一方面，要找到最好的M個基函數(shù)是一個組合優(yōu)化問題；另一方面自然計算（見報告的下半部分）方法為組合

14、優(yōu)化問題的求解提供了新的途徑。l這兩點(diǎn)為自然計算方法應(yīng)用到基函數(shù)選擇提供了可能?；谧匀挥嬎愕幕瘮?shù)選擇方法能不能提供比匹配追蹤和基追蹤更好的性能？這有待我們進(jìn)一步研究。27第二部分：自然計算28人工免疫系統(tǒng)l生物體是一個復(fù)雜的大系統(tǒng),其信息處理功能是由時間和空間尺寸相異的三個子系統(tǒng)完成的,即:腦神經(jīng)系統(tǒng)、免疫系統(tǒng)和內(nèi)分泌系統(tǒng).l人工免疫系統(tǒng)是一種受生物免疫系統(tǒng)啟發(fā), 模仿自然免疫系統(tǒng)功能的一種智能方法.l人工智能對神經(jīng)系統(tǒng)的借鑒和模擬的成果很豐富,已經(jīng)有比較成熟的方法和模型以資利用,相比較而言,對免疫系統(tǒng)研究還處于初級階段.29克隆選擇過程的圖示30人工免疫系統(tǒng)的研究內(nèi)容l記憶學(xué)習(xí)記憶學(xué)習(xí)：

15、免疫系統(tǒng)的記憶作用是眾所周知的,如患了一次麻疹后,第二次感染了同樣的病毒也不致發(fā)病. 這是因為在一次免疫響應(yīng)后,如果同類抗原再刺激時,在短時間內(nèi),免疫系統(tǒng)會產(chǎn)生比上一次多得多的抗體,同時與該抗原的親和力也提高了.l免疫遺忘免疫遺忘：近年來的研究初步闡明，機(jī)體對多樣性外來抗原的選擇識別能力來源于機(jī)體在免疫系統(tǒng)發(fā)育分化過程中對淋巴細(xì)胞的選擇和刪除，通過基因重排產(chǎn)生多種多樣的T細(xì)胞和B細(xì)胞克隆。如果不嚴(yán)格地區(qū)分B細(xì)胞和抗體，可以認(rèn)為在免疫反應(yīng)過程中，抗體可能是擴(kuò)生、無反應(yīng)或者消亡。31人工免疫系統(tǒng)的研究內(nèi)容l多樣性遺傳機(jī)理多樣性遺傳機(jī)理：在免疫系統(tǒng)中,抗體的種類要遠(yuǎn)大于已知抗原的種類.其主要原因可能

16、是受基因片段多樣性的聯(lián)接以及重鏈和輕鏈配對時等復(fù)雜機(jī)制所控制.該機(jī)理可以用于搜索的優(yōu)化,從而提高全局搜索能力,避免陷入局部最優(yōu).l克隆選擇機(jī)理克隆選擇機(jī)理：細(xì)胞的無性繁殖稱為克隆.有機(jī)體內(nèi)免疫細(xì)胞的多樣性能達(dá)到這種程度,以至于當(dāng)每一種抗原侵入機(jī)體都能在機(jī)體內(nèi)選擇出能識別和消滅相應(yīng)抗原的免疫細(xì)胞克隆,使之激活、分化和增殖,進(jìn)行免疫應(yīng)答以最終清除抗原,這就是克隆選擇.但是,克隆中父代與子代間只有信息的簡單復(fù)制,而沒有不同信息的交流,無法促使進(jìn)化. 因此,需要對克隆后的子代進(jìn)行進(jìn)一步處理.32遺傳算法和克隆選擇算法找到了一個局部最優(yōu)找到了多個局部最優(yōu)包括全局最優(yōu)33人工免疫系統(tǒng)存在的問題人工免疫系統(tǒng)

17、存在的問題l由于對人工免疫系統(tǒng)的研究還處于起步階段且免疫機(jī)理復(fù)雜,系統(tǒng)龐大, 甚至連免疫學(xué)家對免疫現(xiàn)象的認(rèn)識和描述都比較困難,人工免疫系統(tǒng)可以借鑒的成果不多,人工免疫系統(tǒng)不論在模型建立,算法等方面都存在一定的問題.lGasper、Dasgupta等研究者認(rèn)為人工免疫系統(tǒng)現(xiàn)在沒有統(tǒng)一的基本框架, 難以象人工神經(jīng)網(wǎng)絡(luò)那樣用線性或非線性模型來對免疫機(jī)理進(jìn)行抽象描述.l就免疫系統(tǒng)機(jī)理本身來講,也存在缺憾. 為了構(gòu)造防御系統(tǒng), 獲得初始抗體,需要進(jìn)行大量計算.34人工免疫系統(tǒng)值得研究的方向人工免疫系統(tǒng)值得研究的方向l進(jìn)一步研究免疫系統(tǒng)的各種計算機(jī)理進(jìn)一步研究免疫系統(tǒng)的各種計算機(jī)理: : 只有對免疫機(jī)理有

18、了深入認(rèn)識,才能為算法構(gòu)造提供保障;而且,新機(jī)理的發(fā)現(xiàn)必將催化新算法的產(chǎn)生.l改進(jìn)已有的人工免疫系統(tǒng)模型改進(jìn)已有的人工免疫系統(tǒng)模型: : 如前所述,現(xiàn)有的人工免疫系統(tǒng)模型還比較簡單,不能滿足人工智能應(yīng)用的需要,具體地講,就是利用模型深入理解算法的執(zhí)行過程,分析算法的收斂性,計算量,為算法的評價和改進(jìn)提供依據(jù).35人工免疫系統(tǒng)值得研究的方向人工免疫系統(tǒng)值得研究的方向l為人工免疫系統(tǒng)開辟新的應(yīng)用領(lǐng)域為人工免疫系統(tǒng)開辟新的應(yīng)用領(lǐng)域: : 與其他人工智能方法一樣,應(yīng)用是方法研究的價值體現(xiàn),是檢驗算法優(yōu)劣的標(biāo)準(zhǔn). 人工免疫系統(tǒng)在短短10年間獲得了廣泛的應(yīng)用,但是在工程應(yīng)用中,還沒有取得和其他智能算法(如

19、模糊邏輯、神經(jīng)網(wǎng)絡(luò))一樣的地位.l基于人工免疫系統(tǒng)的智能整合集成方法研究基于人工免疫系統(tǒng)的智能整合集成方法研究: : 免疫系統(tǒng)的機(jī)理可以被用于改進(jìn)現(xiàn)有的方法,免疫-進(jìn)化、免疫-神經(jīng)網(wǎng)絡(luò)等已經(jīng)被提出,并有成功的應(yīng)用.在這一交叉整合過程中誕生的新思想,正把人工免疫系統(tǒng)的能力擴(kuò)展到能應(yīng)付越來越復(fù)雜的問題,人工免疫系統(tǒng)也正以全新的方式對人工智能等學(xué)科作出貢獻(xiàn).36協(xié)同進(jìn)化論l達(dá)爾文進(jìn)化論過分強(qiáng)調(diào)生存斗爭,而忽略了生物其它方面的種種聯(lián)系,具有片面性.l達(dá)爾文把繁殖過剩所引起的生存斗爭看做生物進(jìn)化的主要動力也不是很恰當(dāng).其實,即使沒有繁殖過剩,物種也會變異,變異的原因是多種多樣的。l近30年來,生物學(xué)上興

20、起了另一個重要理論,就是生物多樣性和協(xié)同進(jìn)化論.該理論已成為生態(tài)學(xué)的基礎(chǔ)理論.應(yīng)用生物多樣性協(xié)同進(jìn)化理論研究生物進(jìn)化和環(huán)境保護(hù),要比達(dá)爾文以生存斗爭為中心的進(jìn)化論更有效.37傳統(tǒng)進(jìn)化算法的不足l雖然進(jìn)化算法較傳統(tǒng)的方法具有巨大的優(yōu)勢，但也存在一些不足之處.l適應(yīng)度函數(shù)是預(yù)定義好的，而真正的適應(yīng)度應(yīng)該是局部的，是個體和環(huán)境作生存斗爭時自然形成的而且隨著環(huán)境變化而變化的。l進(jìn)化算法只考慮了生物之間的競爭，而沒有考慮生物之間協(xié)作的可能性，實際的情況應(yīng)該是競爭和協(xié)作共存，這就是協(xié)同進(jìn)化38協(xié)同進(jìn)化算法l協(xié)同進(jìn)化算法是近十幾年來在協(xié)同進(jìn)化論基礎(chǔ)上提出的一類新的進(jìn)化算法.l協(xié)同進(jìn)化算法考慮了種群與環(huán)境之間

21、,種群與種群之間在進(jìn)化過程中的協(xié)調(diào)。l雖然在這方面的研究起步較晚,但由于協(xié)同進(jìn)化算法的優(yōu)越性,越來越多的學(xué)者對此進(jìn)行了研究,目前協(xié)同進(jìn)化算法已成為自然計算法領(lǐng)域一個活躍的研究分支。39協(xié)同進(jìn)化算法的研究內(nèi)容l基于種間競爭機(jī)制的協(xié)同進(jìn)化算法：基于種間競爭機(jī)制的協(xié)同進(jìn)化算法：這類算法由幾個種群組成,這幾個種群處于競爭關(guān)系,但同時又存在合作行為.種群間通過個體的遷移來達(dá)到信息交流的目的.l基于捕食基于捕食- -獵物機(jī)制的協(xié)同進(jìn)化算法：獵物機(jī)制的協(xié)同進(jìn)化算法：捕食-獵物關(guān)系是一種遭受選擇壓力個體間的一種反饋機(jī)制,這種反饋機(jī)制為系統(tǒng)走向復(fù)雜提供了有力的驅(qū)動.獵物為了不被獵食,通過發(fā)展某些手段更好保護(hù)自己,但同時導(dǎo)致捕食者發(fā)展更好的襲擊策略.40協(xié)同進(jìn)化算法的研究內(nèi)容l基于共生機(jī)制的協(xié)同進(jìn)化算法：基于共生機(jī)制的協(xié)同進(jìn)化算法：這類算法把問題分解為幾個問題, 每個子問題對應(yīng)一個種群, 每個種群用一個進(jìn)化算法進(jìn)化. 面對一個待解問題, 每個進(jìn)化個體只對應(yīng)問題的部分解, 由不同種群個體構(gòu)成的一個共生體對應(yīng)問題的一個完整解. l基于病毒進(jìn)化理論的協(xié)同進(jìn)化算法：基