三维IFS分形插值算法研究及其在DEM生成中的应用

摘要

在DEM(数字高程模型)生成中，插值是一个重要环节。要从原始稀疏、低分辨率的高程数据获取稠密、高分辨率的高程数据，就必须进行插值计算，插值的质量直接影响到地形三维模拟的效果。 本文对表面插值问题进行了较深入全面的探讨。特别地，由于本论文的研究背景为自然地表的DEM生成，所以重点对自然地表的特征及其三维插值进行分析。自然地表的特征是表面粗糙起伏不定，传统表面插值方法由于对高频分量的平滑作用插值效果不理想，只有分形插值才能更好地反映地表自相似统计特征。 目前流行的基于fBm(分数布朗运动)三维分形插值算法，虽然比传统插值有更好的重建效果，但由于无标度区选择困难、地表多分形特征和算法随机性等原因，并不能完全满足实际研究工作的需要。在本文中，重点研究的是基于IFS(迭代函数系统)的确定分形插值。 Barnsley基于IFS建立了二维分形插值理论，但目前三维分形插值的成功应用还不多。目前基于IFS的三维分形插值算法，可以分为三角剖分和矩形剖分两类，为便于DEM生成的实际应用，更需要的是采用矩形剖分的三维IFS分形插值。但目前基于矩形剖分的三维IFS分形插值存在着边界连续性的困难，需要加上限制条件才能生成连续分形曲面，影响了其应用范围;同时，当前这类算法参数计算相当复杂，也不利于实际应用。 本文在综合现有三角形剖分和矩形剖分两类三维分形插值算法各自合理有益部分的基础上，从分析压缩映射的几何意义入手，通过引入换序和变压缩因子，对目前基于矩形剖分的三维IFS分形插值给出了一种改进简洁格式，能够在有很高自由度的情况下解决边界连续性问题，生成连续的三维分形曲面；同时，新格式具有很明确的几何意义，便于实际应用。而在分形插值曲面的生成过程中，本文利用分形插值的固有特点，提出了一种多分辨率快速生成算法，可以把通常费时的分形迭代生成过程转化为简单的递推过程，使得分形插值曲面的生成速度大大提高。 分形逆问题求解一直是分形研究中的难点，目前流行的分形压缩编码算法，由于需要大量的块搜索匹配过程，普通存在编码时间过长这一主要困难。本文从提高压缩变换复杂程度以减少搜索匹配计算量的思路出发，探讨了将三维分形插值应用于分形逆问题的可行性。在分形插值逆问题求解时，提出一种局部迭代算法，解决了利用拼贴定理确定分形参数时出现的无法分离求解问题。实验结果表明算法无论是重建质量还是计算时间上都有很好的实用性。利用本文分形插值能够快速准确生成的特点，本文还提出了一种分形插值逆问题求解的遗传算法，能够不应用拼贴定理而直接利用遗传算法求解分形参数。该算法可以快速精确地求取种群中个体的适应度，并能有效收敛到全局最优。 为了提高三维分形插值的曲面逼近能力，本文对三维分形插值的推广格式做了进一步的研究。构造了新的B-样条三维分形插值和一种非线性插值格式。对新变换的吸引子存在条件给出了证明，并给出了其逆问题求解算法。通过放宽插值限制条件，本文还进一步提出了三维分形数值逼近的概念，扩展了分形插值的应用范围。通过建立一种有限维分形函数线性空间，将分形数值逼近问题转化为关于该空间的最佳逼近求解问题，并提出相应的分形数值逼近算法。相比分形插值算法，分形数值逼近算法具有更好的曲面逼近效果。 本文最后，将本文中研究的各种三维IFS分形插值算法在实际的DEM生成过程中加以应用。表面插值的实验中，与基于fBm的分形插值算法相比，本文基于IFS的三维分形插值能够更灵活地反映地表分形维数从一处到另一处变化的特点;对于标准DEM数据进行压缩编码的实验中，与一般的块搜索匹配算法相比，本文算法在保证重建质量和编码压缩比的情况下，编、解码时间都大为减少。另外，面向网络传输DEM数据的需要，本文还提出了一种渐进分级的分形插值编码方案，实现DEM压缩数据的分级传输和重建。综合实验结果表明：基于IFS的三维分形插值算法很适合于DEM生成的应用，进一步改进后将具有广泛的实用前景。

目录

文摘

英文文摘

论文说明：英文缩略语和符号说明及及上海交通大学学位论文答辩决议书

上海交通大学学位论文原创性声明及版权使用授权书

第一章绪论

第二章基于IFS的三维分形插值

2.1引言

2.2分形概述

2.3 IFS分形的数学基础

2.4 二维IFS分形插值及其几何解释

2.5基于三角形剖分的三维分形插值

2.6基于矩形剖分的三维分形插值改进格式

2.7分形生成算法

2.8实验

2.9本章小结

第三章三维IFS分形插值逆问题求解

3.1引言

3.2拼贴定理

3.3分形编码算法

3.4分形插值逆问题的局部迭代算法

3.5分形插值逆问题的遗传算法

3.6本章小结

第四章分形插值的推广形式

4.1引言

4.2 B-样条分形插值

4.3一种非线性分形插值格式

4.4分形数值逼近

4.5实验比较

4-6本章小结

第五章三维分形插值在DEM生成中的应用

5.1引言

5.2 DEM表面插值

5.3分形插值在DEM压缩存储中的应用

5.4面向传输的渐进编码方案

5.5本章小结

第六章总结与展望

参考文献

致谢

作者攻读博士学位期间发表和录用的论文