非線性07分形及其在圖象處理中的應(yīng)用

197第七章分形理論及其在圖像處理中的應(yīng)用念及原理以及混沌的相關(guān)理論，本章我們介紹非線性科學(xué)的另一個重要的概念—分形。分形形態(tài)在自然界中是非常普遍的，分形理論為我們研究自然界的復(fù)雜事物的客觀規(guī)學(xué)家惠勒說過：今后誰不熟悉分形，誰就不能被稱為科學(xué)上的文化人。所以在本書中單獨把分形列為一章來討論和研究。是物理學(xué);分形學(xué)研究的是靜態(tài)圖形，是幾何學(xué)。本章的內(nèi)容是依據(jù)分形理論的產(chǎn)生、發(fā)展，及在圖像編碼中的應(yīng)用算法以及發(fā)展趨勢這樣一個流程而展開的。在本章最后介紹了分形與其它技術(shù)的有效的結(jié)合。如果讀者對分形理論已經(jīng)有了一定的了解，可以跳過第一第二節(jié)，直接閱讀第三節(jié)。第一節(jié)自然界的分形現(xiàn)象生的，那晶瑩剔透的雪花曾引起無數(shù)詩人的贊嘆。但講述了一種描述雪花的方法。角形邊長的三分之一的小等邊三角形選放在原來三角形的三條邊上，由此得到一個六角星；再將這個六角星的每個角上的小等邊三角形按上述同樣方法變成一個小六角星…如此一直進(jìn)行下去，就得到了雪花的形狀，如圖7-1示。從上面的描述過程我們可以看出：原來雪花的每一部分經(jīng)過放大都可以與它的整體一198模一樣，小小的雪花竟然有這么多學(xué)問?，F(xiàn)在已經(jīng)有了一個專門的數(shù)學(xué)學(xué)科來研究像雪花這樣的圖形，這就是20世紀(jì)70年代由美國計算機專家曼德布羅特(Mandelbrot)創(chuàng)立的分形幾何。所謂分形幾何就是研究不規(guī)則曲線的幾何學(xué)。目前分形幾何已經(jīng)在很多領(lǐng)域得到了應(yīng)用[16,18,162,163]。細(xì)心的讀者會發(fā)現(xiàn)這兩組圖形中包含了很多相似形(形狀相同，大小不一定相同)。這種圖形的特點就是圖形的每一部分都和它本身的形狀相同，我們叫它自相似形。自相似圖形屬于分形圖中的一種。通過計算機處理后，我們可以把一個簡單的圖形變成非常漂亮20眾所周知，基于傳統(tǒng)歐幾里得幾何學(xué)的各門自然科學(xué)總是把研究對象想象成一個個規(guī)則的形體，而人類雖然熟悉卻無法描述的自然界許許多多真實的圖形竟如此不規(guī)則和支離破碎，與歐幾里得幾何圖形相比，擁有完全不同層次的復(fù)雜性?，F(xiàn)代科學(xué)研究面對起伏蜿洼洼的地面、曲曲折折的海岸線、層層分叉的樹枝、支流縱橫的水系、翻魔鬼般跳躍的火焰、船尾湍急的渦流、拍岸的驚濤與浪花、金屬和非金屬材料的斷面、生分子結(jié)構(gòu)、分子光譜分布以及電磁波噪聲分布等等，急切要求得到精確和深入的理解。在這個傳統(tǒng)歐幾里得幾何學(xué)無能為力的領(lǐng)域，分形理論脫穎而出，它的研究和應(yīng)用成果大放異彩。目前，分形理論是非線性科學(xué)研究中十分活躍的一支，它的研究對象是自然界和非線系統(tǒng)中出現(xiàn)的不光滑和不規(guī)則的幾何形體，分形理論的數(shù)學(xué)基礎(chǔ)是分形幾何。什么是分形？分形是對沒有特征長度(特征長度是指所考慮的集合對象所含有的各種長度的代表徑作為它的特征長度。)但具有一定意義下的自相似圖形和199羅特創(chuàng)造性的思維形成了以分?jǐn)?shù)維、自相似性及無限可分為特點的、以迭代計算來描述的分形集合概念。從圖像處理的角度而言，在許多自然圖像中確實存在某種形式的分形自相提出了一種應(yīng)用迭代函數(shù)系統(tǒng)理論實現(xiàn)的分形圖像壓縮編碼。的分形圖像編碼算法，為分形圖像編碼的研究帶來了一次質(zhì)的飛躍，使利用分形編碼進(jìn)行圖像壓縮的方法開始進(jìn)入實用階段。分形的研究可追溯到十九世紀(jì)，一些科學(xué)家曾經(jīng)研究了大自然中物體和現(xiàn)象的幾何形究其原因，傳統(tǒng)的物理學(xué)以牛頓的確定論為基礎(chǔ)。1827年發(fā)現(xiàn)的布朗(Brown)運動軌跡科分形理論是現(xiàn)代非線性科學(xué)研究中的一個非?；钴S的一個分支，在地理、地質(zhì)、材料工程技術(shù)、信息科學(xué)、生命科學(xué)等各個領(lǐng)域中都有廣泛的應(yīng)用。特別是隨著計算機科學(xué)的迅速發(fā)展和廣泛應(yīng)用，分形的思想和方法在模式識別、自然圖像模擬、信息訊號處理以及藝術(shù)制作等領(lǐng)域都取得了巨大的成功。分形理論的研究對象是自然界中非線性系統(tǒng)中出現(xiàn)的不光滑和不規(guī)則的幾何形體，分形理論的數(shù)學(xué)基礎(chǔ)是分形幾何。一、分形理論的發(fā)展過程，是現(xiàn)代數(shù)學(xué)的一個新分支，但其本質(zhì)卻是一種新能在一定條件下、過程中，在某一方面(形態(tài)，結(jié)構(gòu)，信息，功能，時間，能量等)表現(xiàn)與整體的相似性;它承認(rèn)空間維數(shù)的變化既可以是離散的也可以是連續(xù)的，因而拓展了野。的是，近年分形理論的應(yīng)用發(fā)展遠(yuǎn)遠(yuǎn)超過了理論的發(fā)展，并且給分形的數(shù)學(xué)理論提出了更新更高的要求。各種分形維數(shù)計算方法和實驗方法的建立、改進(jìn)和完善，使之理論簡便，可操作性強，是眾多分形科學(xué)家們普遍關(guān)注的問題。而在理論研究上，維數(shù)的理推廣形式的性質(zhì)、動力學(xué)特征及維數(shù)研究將會成為數(shù)學(xué)工作者們十分活躍的研究領(lǐng)域。多重分形理論的完善、嚴(yán)格以及如何用這些理論來解決實際問題可能會引起科學(xué)家們廣泛的200興趣，而動力學(xué)特征、相變和子波變換可能會成為其中的幾個熱點?？偟膩碚f，分形理論的發(fā)展可分為三個階段。第一階段為1872—1925年。在此階段，數(shù)學(xué)家們已認(rèn)識到幾類典型的分形集，并力圖對這類集合與經(jīng)典幾何的差別進(jìn)行描述、分類和刻畫。十九世紀(jì)，雖然人們已認(rèn)識到了數(shù)學(xué)家Weierstrass構(gòu)造了一個連續(xù)但處處不可微的函數(shù)，這一結(jié)果在當(dāng)時曾引起曲線，現(xiàn)在稱為科和曲線。度為無窮大，具有嚴(yán)格的自相似性和無限精細(xì)結(jié)構(gòu)?？坪颓€段，而代之以被除去的線段長度為等邊三角形的另外兩條邊所得到的圖形；對E1的每個線段都進(jìn)行同一過程來構(gòu)造E2;以此類推，得到一個曲線序列{E},當(dāng)k充分大時，曲k線E和E只在精細(xì)的細(xì)節(jié)上不同;而當(dāng)K→∞時，曲線序列{E}趨于一個極限曲線F,我kk-1k們稱F為科和曲線。具有嚴(yán)格自相似性和無限精細(xì)性。另一個例子是德國數(shù)學(xué)家康托 過某個正方形內(nèi)所有點的曲線。這與傳統(tǒng)的維數(shù)觀念相矛盾，從而人們提出應(yīng)正確考慮以往的長度和面積的概念,豪斯道夫(Hausdroff)于1919年引入了集合的豪斯道夫測度和豪斯道夫維數(shù)，這些概念實際上指出了為了測量一個集合對象，必須依賴于測量方式以及測量所采用的尺度?？傊?，在第一階段，人們已經(jīng)認(rèn)識到分形集合的存在性，并為討論這些問題提供了最基本的工具。-1975年。在這個階段，人們對第一階段提出的例子及其它分形集合的性質(zhì)進(jìn)行了廣泛深入的研究，深化了第一階段的思想，并逐步形成了理論，而且研究范圍也擴展到了數(shù)學(xué)的許多分支里，取得了豐碩的成果。數(shù)定義被引入。眾多維數(shù)定義和理論的建立，使人們能從側(cè)面刻畫和分析分形集合的復(fù)雜性。對特定的分形集合，估計和計算它的各種維數(shù)及討論其相互關(guān)系便形成了分形理論的一個基本研究課題。在這個背景下，提出了用于計質(zhì)方面，Bosicovitch在此期間先后研究了曲線的維數(shù)、分形合的局部性質(zhì)、Kakeya集、分形集合的積。在隨機布朗運動方面，Levy建立了分式布Levy對自相似集合的研究在這一階段也占有重要的地位，現(xiàn)在對自相似集合的些研究可以追溯到他的研究成果。自相似集合是目前分形集合中研究最多最徹底的一類學(xué)的其它領(lǐng)域也找到了分形的例子，如在數(shù)論領(lǐng)域，人們研究了數(shù)的數(shù)字分布，連分?jǐn)?shù)的分形性質(zhì)。人們對分形理論的研究已取得了重要的成果，但其研究和應(yīng)用范圍仍只局限在數(shù)學(xué)理論方面，并未試圖去解釋其它學(xué)科中產(chǎn)生的大量分形問201隨著第二階段對分形理論研究的深入和其它學(xué)科分形問題的大量涌現(xiàn)，客觀上要求用一種新的思想和工具去處理有關(guān)的問題。正是這樣的時代背景下，曼德布羅特經(jīng)過在眾多領(lǐng)域的長期研究后，將自己和已有的研究成果進(jìn)行了總結(jié)和理論上的提升，從而揭示大到宇宙空間的星系分布，小至分子的布朗運動，這些不同尺度上看似無序的和不規(guī)則的物質(zhì)運動的本質(zhì)。簡單孕育著復(fù)雜，復(fù)雜的物質(zhì)運動背后往往有著簡單的數(shù)學(xué)規(guī)律。例如，科和曲線的生成規(guī)則十分簡單，但它的結(jié)構(gòu)卻很復(fù)雜，具有無限的精細(xì)性。在1975年，誕生的劃時代的專著《Fractal:Form,Chance,andDimension》使分形幾何的研究和發(fā)展進(jìn)入了一個新的時期。分形幾何產(chǎn)生對于不具有光滑性的復(fù)雜對象的研究，而且隨著分形理論本身的不斷完善，分形理論逐漸形成了描述和研究這種復(fù)雜對象的有力工具。而計算機的發(fā)展，客觀上使得人們表示和研究這種復(fù)雜對象成為可能。從1975年到現(xiàn)在為第三個階段。在這個階段，分形幾何的發(fā)展十分迅猛，分形幾何不僅在理論上得到了進(jìn)一步的完善，而且它的研究內(nèi)容也得到了擴展，如隨機分形、多重、迭代函數(shù)系統(tǒng)理論、復(fù)動力系統(tǒng)的吸引子理論、分形的數(shù)值方法、隨機布朗運動和布朗曲面等?，F(xiàn)在，人們已看到了分形的極強的應(yīng)用性，他的應(yīng)用范圍已擴展到了幾乎所有的應(yīng)用學(xué)科，物理學(xué)、計算機圖形學(xué)、圖像處理、分子化學(xué)、材料科學(xué)乃至經(jīng)濟、藝術(shù)域，并且已取得了令人矚目的成果。這也說明了分形理論在一定程度上反映客觀事物些非常本質(zhì)的東西。在這個階段，國內(nèi)外很多學(xué)者對分形理論及其在各個領(lǐng)域的應(yīng)用進(jìn)行了大量的研究，已有很多的有關(guān)專著出版，發(fā)表的論文數(shù)量以幾何級數(shù)逐年增加。二、分形的定義對分形還沒有嚴(yán)格的數(shù)學(xué)定義。曼德布羅特早期將分形義為其豪斯道夫維數(shù)嚴(yán)格大于其拓?fù)渚S數(shù)的集合。但Peano曲線明顯是分形卻被這個定義排除在外。后來，曼德布羅特又修改為局部和整體按某種方式相似的集合，相似可以是格意義下的，也可以是統(tǒng)計意義下的，這是目前基本認(rèn)可的分形的描述性定義?，F(xiàn)在人們普遍認(rèn)為無需對分形幾何下一個嚴(yán)格的數(shù)學(xué)定義，只需對分形集的特征進(jìn)行描述。一般認(rèn)為分形集合有以下幾個主要的特征：1)具有無限的精細(xì)結(jié)構(gòu)。2)具有某種自相似性。3)某種分形維數(shù)大于它的拓?fù)渚S數(shù)。4)不能用傳統(tǒng)的幾何語言描述。5)往往可以由遞歸迭代等簡單方法得到。第三節(jié)分形理論在圖像編碼中的應(yīng)用一、圖像壓縮技術(shù)的分類隨著科學(xué)的發(fā)展、社會的進(jìn)步，數(shù)字圖像已經(jīng)變成信息的重要來源，人們對圖像存儲202和通信的需求越來越大。從近期的發(fā)展來看，數(shù)字式電視、可視電話等的興起與普及已成為必然；高清晰電視的開發(fā)由于其巨大的市場需求和商業(yè)價值，已成為發(fā)達(dá)國家大力推進(jìn)的高科技項目。然而圖像的信息是模擬的，只有數(shù)字化后才能由計算機進(jìn)行各種處理和綜合。實現(xiàn)多媒體信息的交互處理，必須對各種媒體信息進(jìn)行數(shù)字化。然而圖像數(shù)字化后的數(shù)據(jù)量十分龐大，他們存儲時要占用大量的空間，處理時要占用大量的CPU時間，傳輸時所占用的時間和帶寬花費的成本更是讓人無法接受，盡管提出了很多種改進(jìn)辦法，但都不能徹底解決問題。實踐證明，根本的方法是對圖像的信息數(shù)據(jù)進(jìn)行壓縮。這樣做可以明顯HDTV彩色圖像信息，需要占用3Mb多的存儲容量，傳輸速率將達(dá)到數(shù)百Mbps。如果不經(jīng)過壓縮處理，將給存儲和傳輸帶來極大的困難，導(dǎo)致多媒體通信難以實現(xiàn)。圖像壓縮也是多媒體技術(shù)的關(guān)鍵和瓶頸技術(shù)之一。能夠?qū)D像進(jìn)行壓縮的原因是圖像中通常含有大量的數(shù)據(jù)冗余，一般包括以下幾種：這是靜態(tài)圖像最主要的一種數(shù)據(jù)冗余。一幅圖像記錄畫面上可見景物的灰度值，而同一景物表面上個采樣點的灰度值之間往往存在著空間連貫性，即相鄰像素間的關(guān)聯(lián)會產(chǎn)生空間冗余。2時間冗余這是序列圖像表示中經(jīng)常包含的冗余。序列圖像是由一組連續(xù)畫面組成，其中的相鄰幀往往包含相同的背景和移動物體，只不過移動物體所在空間位置略有不同，這就產(chǎn)生了大量的數(shù)據(jù)冗余，所以成為時間冗余。3視覺冗余性是非均勻和非線性的。然而，在記錄原始的圖像數(shù)據(jù)時，通常假定視覺系統(tǒng)是線性和均勻的，對視覺敏感和不敏感同樣對待，從而產(chǎn)生冗余據(jù)4統(tǒng)計冗余以減少表示圖像的數(shù)據(jù)量，因而稱之為統(tǒng)計冗余。多年來，人們根據(jù)圖像的這些冗余特點，對圖像的編碼技術(shù)進(jìn)行了廣泛的研究，提出了許多切實有效的圖像編碼方法。圖像壓縮技術(shù)可以分為兩大類，即無損圖像壓縮技術(shù)和有損壓縮技術(shù)。所謂無損壓縮技術(shù)是指在圖像編碼過程中沒有任何的失真，但是壓縮比不種壓縮技術(shù)主要應(yīng)用于醫(yī)療圖像和衛(wèi)星照片。有損壓縮技術(shù)也就是圖像編碼過程中有一部分信息損失。這些信息的損失對于人眼來說通常是可以容忍的，從而可以獲取高壓縮比。它主要應(yīng)用于多媒體通信中。二、分形圖像編碼及其發(fā)展分形編碼算法是一種有損圖像壓縮技術(shù)[163]。它是圖像壓縮的重要數(shù)學(xué)工具，有著廣闊的應(yīng)用前景。分形圖像壓縮是以迭代函數(shù)系統(tǒng)(IFS)為理論基礎(chǔ)，即用自然景物的自相似性來進(jìn)行數(shù)據(jù)壓縮。分形圖像壓縮算法具有高壓縮比、任意尺度下的重構(gòu)、快速編碼等203應(yīng)用于計算機圖形學(xué)上，對航空圖像進(jìn)行壓縮編碼，并獲得了1000：1的壓縮比。但其算法有很大的局限性，最主要的就是編碼過程需要人工干預(yù)。何中的自相似性原理來進(jìn)行圖像壓縮。所謂自相似性就是指無論幾何尺度如何變化，景物的任何一小部分的形狀都與較大部分的形狀極其相似。分形用于圖像編碼，總的來說可以分為兩大類。一類可稱作分形模型圖像壓縮編碼，即事先對一類景物建立分形模型。編碼時針對具體事物提取必要的分形參數(shù)，編碼傳送，后一種實現(xiàn)方法簡單，應(yīng)用較為廣泛。目前,圖像壓縮方法已有近百種,但是,壓縮效果、壓縮比以及編碼、解碼時間還不能滿足當(dāng)前信息時代的要求。傳統(tǒng)的壓縮算法一般已經(jīng)成了定式,發(fā)展?jié)摿Σ淮?而分形圖像壓縮的思想新穎,潛力很大,在人工干預(yù)條件下壓縮比10000：1時,解碼圖像還有很好的視覺效果,是一個很有發(fā)展前途的壓縮方法。到目前為止，用數(shù)學(xué)系統(tǒng)去解析地研究分形最成功的是函數(shù)迭代系統(tǒng)(IteratedFunctionSystem,簡稱IFS)，它既包含了確定性過程又包含了隨機過程。對現(xiàn)實世界中的圖像集合引入豪斯道夫度量，使其形成一個完備的度量空間，它的每1、豪斯道夫距離空間該距離空間被認(rèn)為是分形所在的空間，而分形之間的距離也正是由這種豪斯道夫距離度量的。2、仿射變換121212其中a,b,c,d,e,f均為實數(shù)，則稱w為二維仿射變換，在直角坐標(biāo)系中，我們可以寫成如 (y)(cd)(y)(f) (y)(cd)(y)(f)實際上這是一種最廣泛的線性變換,設(shè)矩陣 (c (cb)b)d)7-17-2則A的意義可分解為旋轉(zhuǎn)、伸縮、扭曲、反演等。| (| (cb)(d)(sin9tga)(ltga)(l2l)27-3出其中的仿射變換系數(shù)，這只要確定原圖上三點a*x+b*y+e=r111a*x+b*y+e=r222a*x+b*y+e=r333cxd*y+f=s111c*x+d*y+f=s2227-57-7c*x+d*y+f=s7-9333由以上六方程可求出a、b、c、d、e、f。分形圖像壓縮的理論基礎(chǔ)是迭代函數(shù)系統(tǒng)定理、收縮映像定理和拼貼定理。一個迭代函數(shù)系統(tǒng)由一個完備的度量空間和其上的一組收縮映2043、收縮映像定理函數(shù)空間中的每一個收斂映像都有一個固定點，使函數(shù)空間中的每一個點經(jīng)過這個收續(xù)作用后，形成的點列收斂于這個固定點。圖7-3是經(jīng)反復(fù)迭代最后收縮成一(a)(b)(c)(d)(e)(f)(g)(h)4、迭代函數(shù)系統(tǒng)定理每個迭代函數(shù)系統(tǒng)都可以構(gòu)成函數(shù)空間中的一個收縮映射。于是，我們得到結(jié)論,每樹葉的整體高度減小。從視覺效果上看，這就是一片風(fēng)中的葉子?，F(xiàn)在考慮反問題：給定一幅圖像，能否找到一個迭代函數(shù)系統(tǒng)，而使這個系統(tǒng)正好能決定給定的圖像?這個問題由下面的拼貼定理給出了回答。2055、拼貼定理N個收縮映像構(gòu)成的迭代函數(shù)系統(tǒng)所決定的圖像就任意地接近圖橡I。這就告訴了我們尋找迭代函數(shù)系統(tǒng)的方法。三、交互的分形圖像壓縮方法。在1990年，Jaquin提出了基于塊的分形圖像壓縮算法。雖然該算法的壓縮比低于M.Barnsley,但是他的編碼過程可自動進(jìn)行，因此此算法已經(jīng)成為這一研究方向的典型代了一種基于方塊劃分的分形圖像壓縮方案，在其方案中首先將原始圖像劃分為固定大小的方塊，然后對每一塊，通過反射變換在原始圖像的緊縮圖像中尋找最相似的部分。這些操作可由計算機自動完成，他為分形圖像壓縮的研究帶來了一次質(zhì)的飛躍。整個圖像壓縮的過程可以分成兩大部分，一是編碼過程，一是解碼過程。在分形壓縮后者主要是隨機迭代問題。：1、分割成適當(dāng)?shù)膲K這可以借助于傳統(tǒng)的圖像處理技術(shù)，如邊緣檢測、頻譜分析、紋理分析等，當(dāng)然也可以使用分?jǐn)?shù)維的方法。分割出的每部分可以是一棵樹、一片云等；也片海景，它包括泡沫、礁石、霧塵等；一般這每一部分都有比較直觀的自相似性特征。的地方，在這個過程中有一些必須注意的地方。(1)每一塊的“拷貝”必須小于原塊，這是為了保證仿射變換的收縮性，至于每個拷貝的大小要根據(jù)各塊圖像的性質(zhì)來確定。(2)用于拼貼的每個拷貝之間最好為不相連或緊相鄰的。而不要重疊或者有空缺。這一點對概率的確定很重要，它影響到重構(gòu)圖像的不變測度。所以對有重疊或空缺時，這部并最終要保證206i灰度分布的情況，拼貼結(jié)束時要求出各個p，Barnsley等人采取的方法仍然是下式：iArea((T))adbc7-10iiiii=1其中Ti=1m立在均勻測度的假設(shè)上的，即吸引子上相同大小的區(qū)域有相同的“質(zhì)量”。但是這在對實像處理過程中并不總是成立的，往往是經(jīng)過某個仿射變換后的區(qū)域可能面積很中三個小拷貝所占的面積一樣多，但各部分的測度顯然不同。為此，一般的方法是對灰度能量多的區(qū)域干脆多重疊的幾個相同的仿射變換。這在解碼的過程中可能造成的一個結(jié)果是重構(gòu)圖中存在偽灰度現(xiàn)象；同時在隨機迭代重構(gòu)時總的在拼貼的過程中重新定義了概率的求取，令圖像塊T能量為Q：Q=f(i,mj)m7-11m(i,j)Tf(i,j)表示點(i,j)處的圖像灰度,則可定義概m率：ofWTimiQm其中分子表示Tm經(jīng)w變換后區(qū)域中的能量。這時的p應(yīng)該說可以很好地反映出了圖ii像內(nèi)部灰度分配的信息，下面將看到，它還可以指導(dǎo)圖像重構(gòu)，即對每一圖像塊重構(gòu)時總的隨機迭代次數(shù)就可以設(shè)為該塊的總能量Q,而每一次迭代生成點的灰度能量為1個單位。m此時概率p計算稍微比前一種方法麻煩些，在計算中可以用w(T)與T的邏輯與來獲得iimmw(T)區(qū)域的能量。im4、分形庫的建立與使用對于分類的圖像，我們可以預(yù)知該類圖像中物體出現(xiàn)的范圍，在同樣使用上述的編碼現(xiàn)重復(fù)拼貼一些相似的區(qū)域，這種代價是無益的，為此可以使用分形庫的方即在庫中預(yù)存貯著許多有意義的小的形態(tài)，當(dāng)然它們不是以圖像格式存入的，否則庫巨大，同樣可以以IFS參數(shù)的形式來描述它們，則拼貼的過程就變成了用這由事先給出的度量公式來確定，這種公式有很多種形式，如均方誤差等。一旦匹配好了，就可以用這些IFS碼來替換圖像中的區(qū)域了。四、基于分?jǐn)?shù)維分割的圖像編碼數(shù)，也就是分?jǐn)?shù)維去測定其不平整度、復(fù)雜度或卷積度。分?jǐn)?shù)維的微小變化可以引起形狀的急劇改變。現(xiàn)實世界中,幾何形體可以分為兩大類。一類是規(guī)則、光滑的,可以用直線段、平面片或小六面體來逼近,研究這一范疇的學(xué)科為傳統(tǒng)幾何學(xué)。另一類的自然形態(tài)是不光滑、不規(guī)則的,具有精細(xì)的結(jié)構(gòu)或自相似特征,不能用傳統(tǒng)我們稱之為分形。如海岸線、山形、河川、樹木、閃電等自然景物,以及微觀世界中復(fù)雜且精細(xì)的結(jié)構(gòu)、宏觀世界里天體演變的各種形態(tài)。但這些例子在充分小的207比例下觀察時，其分形特征就消失了。但在一定比例下它們表現(xiàn)了許多分形特征，這時我作分形。分形學(xué)使人們對自然界和人類社會的認(rèn)識提高到一個嶄新的高度。例如,曾使網(wǎng)絡(luò)性能模型的研究人員感到震驚的是"以太網(wǎng)數(shù)據(jù)傳輸具有自相似的本性",這是由Bellcore和Boston大學(xué)的研究人員發(fā)現(xiàn)的。結(jié)果證明,Internet網(wǎng)絡(luò)上數(shù)據(jù)的傳輸服從分形特征,不要期望網(wǎng)上的數(shù)據(jù)流"光滑輸出",由統(tǒng)計多路技術(shù)或異步傳遞模式轉(zhuǎn)換的合并也不會有光滑輸出的數(shù)據(jù)流。這樣流量控制就要重新考慮了。這為網(wǎng)絡(luò)的合理設(shè)計與管理提供了理論的特性，比如對某些頻率分量比對其它的敏感些。因此，對不敏感的部分可以粗略編碼，碼圖像也不會有接受不了的質(zhì)量損失。所以，在編碼系統(tǒng)中考慮到了人的視覺特將有利于提高壓縮比?；诜指畹膱D像編碼就是這樣一種技術(shù)，它根據(jù)視覺特征，使用一些分割方法把圖像分成若干類區(qū)域，對不同的類再使用不同的編碼方法。但是傳統(tǒng)的分割技術(shù)有一些限制，比如它是按一定的灰度去劃分的，這對一個復(fù)雜的紋理區(qū)域，可能要分割成許多塊，然而為了得到較大的壓縮比我們必須限制分割的數(shù)目。因此可采用分?jǐn)?shù)維的方法。我們知道，分?jǐn)?shù)維是物質(zhì)的根本性質(zhì)之一，它直接反映了人眼對表面粗糙度的感可以把圖像分割成紋理上類似的區(qū)域，例如可以分成如下三類，第一類是平滑區(qū)類為平穩(wěn)的紋理，第三類是粗糙的紋理。這樣對圖像分割以后，對不同類的區(qū)域可以采用不同的編碼策略，對第一類只要有灰度均值以及邊界信息；第二類是要重點對待此處也可以用較高的壓縮比來完成。這種基于視覺特性的分?jǐn)?shù)維分割的圖像壓縮方法可以獲得相當(dāng)高的壓縮比。有關(guān)分?jǐn)?shù)維的具體含義及求法可參考相關(guān)的參考書[16,18]，分形是和混沌相聯(lián)系的，混的維數(shù)一般也是分?jǐn)?shù)維的，我們稱其為李雅普諾夫維數(shù)，該維數(shù)反映了信息丟失的程度。分形集是動力系統(tǒng)中那些不穩(wěn)定軌跡的初始點的集合，即混沌集?；煦缥泳褪欠中渭?。五、分形在視頻圖像壓縮中的應(yīng)用分形壓縮可以得到很高的壓縮比，但在編碼過程中計算量很大。一般是從兩個方面試圖解決這一問題，一是要考慮新的算法，二是要考慮用硬件實現(xiàn)。由Barnsley創(chuàng)立的迭代系統(tǒng)(IteratedSystem)公司已經(jīng)研制出了板級的可用于彩色圖像的分形壓縮的硬件，實時壓縮，還有待于進(jìn)一步的發(fā)展，但它仍然具有廣泛應(yīng)用的價值。分形圖像壓縮的編、解碼過程是極不對稱的。編碼比解碼要求多得多的時間，相應(yīng)的用戶在解碼端，因此，不用花費過多的硬件費用，甚至只有軟件也行。同時解碼過程還有獨立于分辨力的特性，在解碼端可以生成任何分辨率的圖像，這可能有助于今后HDTV與六、當(dāng)前分形圖像壓縮的發(fā)展?fàn)顩rJacquin提出的方案為分形壓縮編碼的研究注入了生機和活力，分形編碼成為目前編208碼研究的熱點。目前分形編碼方案大致有三個發(fā)展方向：加快分形的編解碼速度、提高分形的編碼質(zhì)量、基于分形的低碼率視頻編碼。發(fā)展方向之一：加快分形的編碼速度nCC假設(shè)值域子塊大小為K×K,定義域子塊大小為2K×2K,KCKCKC形編碼的計算復(fù)雜度為O(C4)。所以，減少搜索、加快編碼速度是研究的熱點之一。Jacquin根據(jù)子塊的復(fù)雜度將其分成四類，對每個值域子塊，僅在其同類的定義域子塊中進(jìn)行搜索；D.Saupr采用多維最近鄰搜索方法代替?zhèn)鹘y(tǒng)分形編碼中序列的匹配過程，其搜索匹配時間按指數(shù)級增長；K.F.Loe等將Jacquin方案中使用的分類器替換成模糊分類器，并使用遺傳算法進(jìn)行優(yōu)化，該算法比未分類的編碼方案快40%左右；C.K.Lee和W.K.Lee通過對匹配塊之間關(guān)系的研究發(fā)現(xiàn)，如果兩子塊的自身方差相差太遠(yuǎn)，則這兩個等將傳統(tǒng)編碼方案中每個值域子塊匹配的串行操作轉(zhuǎn)換為并行操作，計算復(fù)雜度下降，縮短了壓縮的時間。發(fā)展方向之二：提高分形編碼質(zhì)量度逼近能力等。分形與小波的結(jié)合編碼是目前分形研究的一個新的方向，在本章的第四節(jié)對此加以介紹，并附有實例，加深讀者們的理解。Jacquin用兩次分割，在提高進(jìn)，的劃分方法，使分形壓縮的質(zhì)量和壓縮速度有了較大的提高，是目前較為實用的壓縮方法。目前國內(nèi)外研究者還提出了基于區(qū)域的分割方案。在分形編碼中常用的灰度逼近式為w(z)=s*z+t,可把灰度逼近式變?yōu)閣(z)=t(z),t(z)可為任意形式，可以為二次以上的多項式，有效提高了編碼效果，改進(jìn)圖像質(zhì)量。發(fā)展方向之三：分形序列圖像編碼的引入，編分像恢復(fù)質(zhì)量、壓縮比及編碼實時上仍不是很理想。因此分形序列圖像編碼是當(dāng)今分形壓縮編碼的一個重要方向。第四節(jié)分形與其它理論的結(jié)合209到人類活動的各個方面，并已取得了令人矚目的成果。分形圖像壓縮既考慮局部與局部，又考慮局部與整體之間的相關(guān)性，適合于自相似或自仿射的圖像壓縮；分形圖像壓縮解碼時能放大到任意大的尺寸，且保持精細(xì)的結(jié)構(gòu)；在高壓縮比的情況下，分形圖像壓縮自動編碼能有很高的信噪比和很好的視覺效果。對于編碼雖然有許多的改進(jìn)措施，但是搜索匹配時間長還是不能滿足許多實際的需要，基于此，。常用的混合方案有與小波變換結(jié)合編碼、與DCT變換結(jié)合編碼、與加權(quán)有限自動機結(jié)合FFT型結(jié)合編碼、與算術(shù)結(jié)合編碼。近10年來，人們對于自適應(yīng)塊狀分形編碼進(jìn)行了不懈的研，G已經(jīng)開始顯露出它的優(yōu)勢。分形圖像編碼方法的實際應(yīng)用也初見端倪，如分形圖像壓縮解碼速度很快，當(dāng)前已經(jīng)適合于一次寫入、多次讀出的文檔。由于篇幅有限，這一節(jié)重點介紹小波與分形的結(jié)合編碼、與遺傳算法的混合編碼以及一、小波分形混合圖像編碼小波圖像編碼和分形圖像編碼是兩種不同的圖像編碼方法。其中，小波圖像編碼是把圖像分解成不同的空間方向和不同分辨率的子帶圖像，人們可以根據(jù)需要，對不同子帶圖一般的自然圖像自相似性并不是很強，但是經(jīng)過小波變換后的圖像，其相同方向但不同分辨率的子帶圖像卻具有較強的相似性。因此，人們可以利用這種相似性，結(jié)合分形碼已成為今后的發(fā)展趨勢。一系列尺度、方向、空間局部變化的子帶。由于小波變換能獲得很好的空間-頻率多分辨率表示，而且在低頻處有很好的頻率特性，在碼提供了條件。在傳統(tǒng)的分形圖像編碼中，由于尋找最佳匹配塊需要進(jìn)行大量計算，從而。而利用小波分解后，圖像塊所具有的獨特空間-頻率特性，可以構(gòu)造較好的分類和搜索方法，因而大大加快了分形編碼的速度。這種混合編碼基本思想簡述見實例演示。自從分形圖像壓縮作為一種實用的方法由Jacquin首次提出以來，大多的關(guān)于分形圖像壓縮研究都集中在時間域進(jìn)行，為了提高編碼性能，一些變換域變換編碼方法相繼由210Barthel等提出。其中離散余弦變換(Discreteconsinetransformation),余弦調(diào)制濾波器組(Cosinemodulatedfilterbanks)和小波變換等應(yīng)用最為廣泛。收斂的仿射變換來重建圖像，它利用同一圖像中一部分描述另外一部分，即利用圖形的自相似性來減少圖像的冗余度。頻域變換的一個突出優(yōu)點就是他的能量緊湊特性，一幅圖像經(jīng)過頻域變換后，總能量沒有變化，但能量的分布卻發(fā)生了變化。能量將集中在它的低頻部分，而高頻部分所占的能量非常少，能量的這種分布對分形壓縮十分有利，因為分形圖像壓縮的主要過程是對同樣大小的圖像塊進(jìn)行能量余弦變換就是其中的一種。近年來的研究表明，離散余弦變換是一種最接近K-L變換。(1)設(shè)原圖像的大小為N*N,,首先把它劃分為(N/8)2塊大小為8*8的區(qū)塊(rangekDCT成一個域塊庫。之所以只取圖像左上角是因為域塊在經(jīng)過變換后，主要信息都保存在低頻區(qū)，對應(yīng)于在構(gòu)成域塊時，我們只取左上角與區(qū)塊同樣大小的一部分。(2)下面則是利用圖像的自相似性進(jìn)行分形壓縮，其實質(zhì)是尋找一組仿射變換，即匹配過程。它與時域的塊匹配過程完全相同。但由于圖像經(jīng)過頻域變換后，具有與時域不同的特點，因此在具體的實現(xiàn)方法上存在著一些差別。首先，圖像在經(jīng)過DCT變換后,能量集中到低頻部分，特別是它的直流分量，占據(jù)了整幅圖像能量的很大一部分，這就使我們必須對它們單獨處理，而不把它帶入塊匹配的過程中。在匹配過程中，均值分量也熵編碼。這樣做不僅減少了塊匹配的誤差，而且在解碼時，在第一次迭代過程中，就可以得到直流分量，從而加快了解碼的收斂速度。其次，圖像塊在經(jīng)過DCT變換后，能量分具有一定的規(guī)律，不同于在時域中的雜亂無章的分布，因此在塊匹配過程中，旋轉(zhuǎn)所帶來的性能上的改進(jìn)將變得非常小，與此同時，它卻增加了所需的比特數(shù)，降低了壓縮比。(3)經(jīng)過塊匹配之后，將閾塊的位置信息和仿射變換的系數(shù)(這里只有收斂因子)步提高壓縮比。編碼算法可以選用哈夫曼編碼或是算術(shù)編碼。的復(fù)雜性，有人提出了選擇性塊匹配的編碼方案，也就不去進(jìn)行塊匹配，而是把它的直流分量直接編碼輸出。感興趣的讀者可以參閱相關(guān)的文獻(xiàn)介紹。三、基于遺傳算法的分形圖像編碼211遺傳算法是模仿生物界的進(jìn)化過程而得出的一種隨機優(yōu)化方法，對非線性、多極值的問題尤其有效，它將問題的解編碼表示成“染色體”，一群“染色體”組成初始種群，初始種群置于問題的“環(huán)境”中，根據(jù)自然競爭、優(yōu)勝劣汰的原則，種群通過遺傳、交叉、變異不斷地進(jìn)行演化，產(chǎn)生新的種群，這樣經(jīng)過若干代的進(jìn)化，求得適合問題的最優(yōu)解。分形圖像壓縮中的值域塊與定義域塊的匹配是典型的多極值問題，由于遺傳算法求解多極值問題的有效性，將其應(yīng)用于塊的匹配(也可稱為虛擬碼書的搜索)，可以大大降低壓縮編碼的復(fù)雜度，同時很好地保持圖像質(zhì)量。應(yīng)用于分形圖像壓縮中的遺傳算法主要步a物種的染色體編碼表示。c適宜函數(shù)的選取。d選擇策略。e交叉策略。f遺傳及變異策略。g終止準(zhǔn)則。經(jīng)過許多學(xué)者的研究證明，將遺傳算法應(yīng)用于分形圖像壓縮，效果良好，對每一定義O保持了圖像的質(zhì)量，同時利用遺傳算法的并行性可以進(jìn)一步提高運行的速度。由于分形壓縮編碼存在一定的失真度，其編碼時間和編碼效率與失真度密切相關(guān)。另外分形壓縮方法仍有許多尚待解決的問題：的劃分未免太勉強人意，需要進(jìn)一步討論相似性的提取。b失真率的研究現(xiàn)在很不全面，應(yīng)給出更好的度量相似性的方法。c考慮如何利用圖像塊本身的特點，更快更好地尋找到匹配塊，節(jié)省編碼時間。。目前，基于分形－小波混合編碼是研究的熱點，還有很多方面可以進(jìn)一步研究以充分挖掘其潛力：(1)深入研究小波－分形變換的內(nèi)在聯(lián)系，進(jìn)一步用分形集合的集合相似性來表示小波分解域內(nèi)子帶間的相似的特征。(2)對不同的小波基分解后頻帶的特性和差別加以研究，以挖掘出適合小波－分形編碼的小波基。(3)將傳統(tǒng)的分形編碼方法中一些行之有效的思想應(yīng)用于小波－分形編碼。(4)廣泛結(jié)合一些目前已經(jīng)相對完善的技術(shù)的優(yōu)勢(如子帶編碼、矢量量化)，充分利用信號處理的研究成果為圖像編碼領(lǐng)域注入新的活力。第五節(jié)實例分析—小波與分形混合編碼212小波圖像編碼和分形圖像編碼是二種不同的圖像編碼方法,二者各有其特點,又都存在一幅圖像經(jīng)過小波變換后,其相同方向但不同分辨率的子帶圖像具有較強的相似性。這種相似結(jié)構(gòu)正好與分形編碼的特點具有互補性。如果采用一些新的編碼方法,把二者有機地結(jié)合起來,便能大幅度地提高圖像編碼的壓縮比。Rinaldo和Calvagno提出了一種利用圖像小波分解后所表現(xiàn)出來子帶間相似性進(jìn)行分形編碼的方法，即所謂的塊預(yù)測法。這種方法的主要思想是用變換域低分辨率的子帶圖像Rinaldo潔，但由于分形塊搜索是在同方向每相鄰的兩個小波子帶內(nèi)進(jìn)行搜索，塊搜索范圍過大，耗時過長，且并沒有充分發(fā)掘和利用同方向各個子帶間的結(jié)構(gòu)性相似；同樣,Levy和Wilson也過類似的研究結(jié)果，后來Davis把小波子樹的概念引入到分形圖像編碼中,提出了小波子樹自量化方法(Self-QuatizationofSubtrees)，其主要編碼方法是把傳統(tǒng)分形圖像編碼中的圖像塊匹配轉(zhuǎn)化為圖像樹匹配。Davis的方法雖然把圖像塊擴大為圖像樹，但卻造成了子樹匹配過程中計算量的增大和分形搜索的困難。因此近年來,小波分形混合圖像編碼領(lǐng)域內(nèi)的研究主要是在這兩種方法的基礎(chǔ)上,進(jìn)行不斷的探討[114,116]。顯然，這兩種方法都只是從某一個側(cè)面揭示了小波分形的本質(zhì)特征。二、快速小波子帶分形編碼方法的提出鑒于以上兩類編碼方法的特點和不足,在小波變換同方向不同分辨率相鄰子帶塊預(yù)測編碼的基礎(chǔ)上,本書作者提出一種新的快速圖像編碼方法，主要編碼思想由以下四部分組1、子樹位搜索法相鄰子帶塊預(yù)測編碼在進(jìn)行塊匹配搜索時,對上一級分辨率子帶內(nèi)所有的塊進(jìn)行全面的搜索比較,直至找出最相似的匹配塊(誤差最小的塊)。這種塊搜索法雖然精度較高,但圍過大,搜索時間過長。小波子樹具有結(jié)構(gòu)上的相似性,即同方向不同分辨率相同位置的的相似性。根據(jù)小波子樹的這一特點,塊匹配時把搜索范圍限制在圖像樹附近,便能在保持一定的精度的情況下,大幅度縮小塊搜索時間,這種在小波子樹位置附近塊匹配搜索的方法即為子樹位搜索法。2、子帶恢復(fù)基礎(chǔ)編碼法相鄰子帶圖像編碼方法,編碼時在小波分解后相鄰的兩個子帶間進(jìn)行分形預(yù)測，但解碼時則在恢復(fù)子帶的基礎(chǔ)上進(jìn)行預(yù)測，這樣必然給最后恢復(fù)的圖像帶來失真。為此提出子帶恢復(fù)基礎(chǔ)編碼法，從最低分辨率子帶開始進(jìn)行編碼，然后逐級恢復(fù),在恢復(fù)子帶的基礎(chǔ)上逐級進(jìn)行分形預(yù)測編碼。3、大誤差塊直接編碼法較低分辨率的子帶在圖像恢復(fù)中起著重要的作用。在多次實驗中發(fā)現(xiàn)，越是低分辨率子帶,分形預(yù)測的誤差越大,而這些誤差較大的塊(兩個子帶間相似程度差的塊)，在圖像復(fù)中起著極為關(guān)鍵的作用。為了減少誤差,提高恢復(fù)圖像質(zhì)量,對一些低分辨率子帶進(jìn)行當(dāng)塊匹配誤差超過某一門限值時,不再對這些塊進(jìn)行分形預(yù)測編碼，而是直接記213錄其值，進(jìn)行無失真編碼，這種方法即為大誤差塊直接編碼法。大誤碼差塊直接編碼法雖然在一定程度上降低了壓縮比,但對保留圖像重要信息,提高圖像恢復(fù)質(zhì)量起著關(guān)鍵作用。整個編碼方案的實現(xiàn)如圖7-5所示(d1為塊匹配誤差門限值)。圖7-5快速小波子帶分形編碼流程圖三、計算機仿真實驗及結(jié)果分析在多次的實驗中,我們發(fā)現(xiàn)Bior4.4小波在圖像分解與恢復(fù)中有較好的效果,故這里用Bior4.4小波對512×512的Lena和testpat1兩個標(biāo)準(zhǔn)灰度圖進(jìn)行5級小波分解.實驗使用微2、實驗參數(shù)實驗用小波分解層數(shù)為五級,對第四級小波分解的低頻子帶直接進(jìn)行無失真編碼,塊匹配分形預(yù)測編碼從第四級三個高頻子帶開始。快速子帶算法匹配塊的大小根據(jù)子帶分辨率的不同從低到高分別為:4×4、8×8、12×12、26×26;相鄰子帶算法匹配塊的大小分別為:3×3、6×6、12×12、26×26?？焖僮訋惴ㄔ谛〔ǚ纸獾谒募?、第三級采用大誤差塊直接編碼法。實驗1中兩級的誤差門限值分別為6500、3000,直接進(jìn)行無失真編碼的塊數(shù)Lena圖為55、38,Testpat1圖為105、78;實驗2中兩級的誤差門限值分別為6500、3000,直接進(jìn)行無失真編碼的塊數(shù)Lena圖為92、38,Testpat1圖為141、78;實驗3中兩級的誤差門限值分別為6500、3000,直接進(jìn)行無失真編碼的塊數(shù)Lena圖為157、38,Testpat1圖為196、78。214表7-1和表7-2分別為對Lena實驗中所用峰值信噪比PSNR的計算公式為:7-13m=1n=1第四級小波分解子帶塊匹配誤差門限值,d2為第三級小波分解子帶塊匹配誤差門限值。Lena比較壓縮倍數(shù)PSNR/db編碼時間/S誤差門限值(d1,d2)6500,30003000,3000650,30006500,3000相鄰子帶編碼實驗31.51924.68052800a原始圖像b相鄰子帶編碼圖c快速子帶分形編碼圖d快速子帶分形編碼實驗2圖e快速子帶分形編碼實驗3圖f子帶恢復(fù)法對比實驗圖Testpat子帶編碼參數(shù)比較壓縮倍數(shù)PSNR(db)編碼時間(S)誤差門限值(d1,d2)215000g始圖像h相鄰子帶編碼圖i快速子帶分形編碼實驗4圖jk快速子帶分形編碼實驗6圖l子帶恢復(fù)法對比實驗圖4、實驗分析從以上對Lena和Testpat1兩個灰度圖所進(jìn)行的快速子帶編碼算法與基本的相鄰子帶算法對比結(jié)果來看,在壓縮倍數(shù)相近的情況下,快速子帶算法在編碼時間方面有500多倍的提高,反映恢復(fù)圖像質(zhì)量的PSNR值也有較大提高;從是否采用子帶恢復(fù)基礎(chǔ)編碼實驗對看,采用子帶恢復(fù)法后PSNR值有所增加。顯然,快速子帶算法較相鄰子帶算法在編碼時間和恢復(fù)圖像質(zhì)量方面均有較大提高。以上理論分析和實驗證明,本文提出的快速小波子帶分形圖像編碼算法,相對于相鄰子帶編碼算法,由于吸收了小波子樹分形編碼的優(yōu)點,有效地縮小了子帶塊搜索范圍,極大地減少了編碼時間;同時由于采用了子帶恢復(fù)基礎(chǔ)編碼法和大誤差塊直編法,對編碼過程帶來的誤差進(jìn)行了修正,使恢復(fù)圖像質(zhì)量有了較大的改善。結(jié)論：定理，通過給定的圖像，尋找一組收縮映射，使其組函數(shù)系統(tǒng)的吸引子逼近給定圖像，然后記錄下相應(yīng)參數(shù)。解碼過程是由相應(yīng)參數(shù)函數(shù)系統(tǒng)，并根據(jù)迭代函數(shù)系統(tǒng)定理，經(jīng)過迭代生成圖像。分形圖像壓縮的思想216在許多問題有待解決。本章對分形圖像壓縮的理論基礎(chǔ)和實現(xiàn)的關(guān)鍵技術(shù)進(jìn)行了全面綜述，介紹了具有代表性的各種新方法，闡明了各個方法的特點，最后簡要總結(jié)一下分形圖像壓縮的改進(jìn)以及發(fā)展趨勢：