46 分形编码.ppt

第11章 分形编码 分形压缩的基本思想是，利用数据的自相似或自仿射特征，构造相应的局部迭代函数系统 ，从而只需要少量的数据就可以恢复与原图象相近的图象，达到压缩图形数据的目的 本节先介绍分形和迭代函数系统的基本内容，然后讨论分形压缩的具体方法，最后给出若干图象的分形压缩的实例 一．分形 分形(fractal)是法国数学家Benoit B. Mandelbrot于1975年在创立分形几何学(fractal geometry)时所造的一个新词，指具有一定自相似性的复杂不规则形体，一般为自然界中的物体和形态 随机分形：如海岸线、云彩、山川、水系、树、烟雾、波浪、草坪、纹理和湍流等，这些都是随机分形，具有统计自相似性 数学分形：如Koch曲线、Sierpinski地毯、Mandelbrot集、Julia集、L系统和分数布朗运动等规则的数学分形，具有严格自相似性 1．Mandelbrot集和Julia集 复动力系统——Mandelbrot集和Julia集，是由复迭代公式 z = z 2 +C (1) 确定的收敛集，其中：z = x + i y, C = a + i b为复变量 Mandelbrot集：若固定C，让(1)式每次从某个固定z0 = x0 + i y0（如x0 = 0, y0 = 0）开始进行无穷迭代，当其发散到无穷大时（可用 | z |2 = x2 + y2 4来判断），用发散速度（迭代次数）来给C平面上所对应点着色，则在 a：-2.2 ~ 0.6、b：-1.25 ~ 1.25的区域内，可得到变幻无穷且能无穷放大的美丽图案 Julia集 若固定C，让Z0在一定区域（如 | x | 1.75, | y | 1.75）内变化，则(1)式迭代的收敛集为Julia集 也可以似前M集着色，所得图形也非常美丽 2．分维 分维(fractal dimension) 是分形的核心概念 要测量复杂的形状的长度、面积或体积不仅是非常困难的事，有时甚至是不可能的，如英格兰的海岸线长度，中国地表的面积，一棵大榕树的体积等等。解决办法之一，是测量它们的复杂程度，所用的度量工具就是形体的维数 一般来说，一个物体的维数D、线度（直径）l和测度（即一维形体的长度、二维形体的面积或三维形体的体积等等）m有如下关系式： l D = m (1) 如线度扩大一倍（2 l），则长度也扩大一倍（(2 l)1 = 2 l）、但面积则扩大到4倍（(2 l) 2 = 4 l 2）、而体积则扩大到8倍（(2 l) 3 = 8 l 3） 分维的计算 从(1)式容易推导出维数的计算公式： 这里的维数（分维）D不必是整数，可以是小数或分数，所以又叫分数维。如 Koch曲线的分维D = ln 4 / ln3 = 1.2618 Peano曲线的分维D = ln 4 / ln2 = 2 Sierpinski三角地毯的分维D = ln 3 / ln2 = 1.5850 复杂的不规则物体，其分维一般大于其拓扑维数，将这样的形体称为分形 二．迭代函数系统 Michael F. Barnsley于1985年提出的迭代函数系统 (Iterated Fuction Systems，IFS)是构造分形的有力工具，而分形压缩的图像是作为迭代函数系统的不变集出现的，它们本质上是一些压缩仿射变换 迭代函数系统的思想虽然早已见于J. Hutchinson于1981年所写的论文，但其命名及系统研究与应用却应归功于Barnsley。他不仅提出了IFS的随机迭代算法，还将IFS成功地用于分形插值函数的构造及分形图像的压缩 螺线 Koch曲线 三角Sierpinski垫 羊齿叶 青草 3．局部迭代函数系统 上面所介绍的IFS方法中，每个压缩仿射变换wi都作用于所有区域，所以只能生成全图是一整个严格自相似或自仿射分形的图形 但一般的图象显然不是一个整体分形，而只是它的一些部分之间存在某种相似或仿射性。解决这一问题的办法是将区域A分割成若干（可以相交的）小块Ri，并使每个压缩仿射变换wi都局限在一个小块区域Ri上 这需要将IFS定义中的 改为 即得局部迭代函数系统（LIFS = Local IFS） 由拼接定理可知，将各个局部仿射变换的结果拼接起来就能得到整个区域的仿射变换 三．分形压缩方法 由IFS可以生成各种分形图形，但是反过来如何从一个已有的图象找出生成它的IFS呢？这正是分形压缩所要解决的关键问题 虽然Barnsley早在1987年就提出了分形压缩的基本思想，但开始时需要借助于人工干涉来寻找每个图象的IFS，不适合计算机自动处理。后来虽然发展了若干分形压缩方法和技术，但出于商业考虑，一直不为外人所知 直到1993年Barnsley出版了分形图象压缩的专著，透漏了其中的一些基