曲线信息隐藏特征约束可控分形插值算法仿真

陶雪娇，阚 洪，张晓颖，王 越

(1. 重庆工程学院软件学院，重庆 400056；2. 重庆理工大学，重庆 400054)

1 引言

分形插值是在迭代函数体系的基础上提出的一种构造分形曲线的方法。其原理是在给定的插值点上构造相应的 IFS，使 IFS的吸引子作为函数图通过这组插值点。分形几何有别于传统几何，具有其独特之处。第一，分形几何体整体上是处处不规则的。但在不同的尺度下，图形又有相同的规则。以海岸线为例，从远处来看，它的外形极为不规则，完全无法用传统的规则几何学来描绘它。在近距离观察其局部时，其局部形状又与整体具有某种几何相似性[1]。然而，并非所有的分形几何都是完全自相似的，其中有一些是用于描述混沌、非线性系统或一般随机现象。分形几何实际上就是自然几何，而分形插值函数就是利用自然中的许多现象具有精细的自相似结构这一特征来拟合波动较大的曲线，现在已经被证明是非常有效的工具。

分形插值算法经过几十年的发展，已在数据拟合，函数逼近，计算机视觉等领域得到了广泛的应用。GIS中的分形插值技术能够为地形模拟、地图曲线插值、绘图等应用提供技术支撑。经典的分形插值算法有布朗运动，随机中点位移，仿射变换等。对实际自然几何体的插值来说，这些分形插值算法虽然能有效地生成分形几何体，并且能够模拟自然几何曲线的分形特性，但都是以自然几何曲线为单纯的几何对象，通常采用的是整体均衡插值算法，而不受自然几何曲线弯曲特性的限制，实现了自然几何曲线的分形插值。地图上自然几何曲线并不是单纯的几何图形，它更是一种典型元素，体现了真实的自然地理特征形态。在自然几何曲线上的海岸线表现为多个海岸单元的特征，如弯度、弯度等，不同海岸单元的几何形状、复杂性、分维等特征是不一样的，若不仔细辨别而进行整体分形内部插入，上述地理特征信息就容易丢失[2]。

针对传统的分形插值算法存在的问题，提出了一种新的基于几何细节的地理弯曲特征分割和几何细节层次的分形插值约束，在考虑地理弯曲特性约束的情况下，实现了可控分形插值，并且对比分析与比例相同的实际目标海岸线要素形态，验证了所提算法的有效性和合理性。

2 曲线信息隐藏特征约束可控分形插值算法设计

由于四叉树结构在支持多分辨率地形网格模型快速生成的同时，可以很自然地对地形进行分割，使其在地形建模和绘制方面具有广泛的应用。所以设计了一种曲线信息隐藏特征约束控制分形插值算法，在分形迭代生成曲线时采用四叉树结构实现地形分割，具体分割过程如图1所示。

图1 四叉树曲线划分示意图

如图1所示，对于每一件自然事物，首先用四叉树的根节点表示整个轮廓曲线，然后将它平均分为左上、左下、右上和右下四个部分，并且每个子节点都代表一个节点。在四叉树结构中，每个子节点继续平均细分为下一层的四个子节点，并不断向下细分，直至满足细分约束[3]。从而可生成研究自然事物所对应的曲线高度数据。根据得到的曲线数据，结合曲线本身的信息隐藏特性和分形规律，得到曲线分形插值处理的最终结果。

2.1 分析曲线信息隐藏特征

信息隐藏即是将保密信息隐藏于另一非保密载体中，曲线信息隐藏的基本原理如图2所示。

图2 曲线信息隐藏基本原理图

因此分析曲线信息的隐含特性首先要得到信息密钥，然后通过反向解密得到曲线信息。各种自然曲线形态是在构造运动、海水动力、生物作用和气候因素等共同作用下形成的，自然几何曲线在抽象表达时表现出不同的弯曲特征[4]。各种地形类型的自然几何曲线都可以通过它们所表现的几何弯曲形态和复杂性来识别，形状复杂且弯曲度大的海岸线通常表示地貌单元，形状平直且弯曲度小的自然几何曲线则表示地貌单元。就天然中海岸线曲线而言，海岸线的弯曲特性取决于该区域内海岸地貌特征，提取曲线弯曲特性隐藏特征信息可以看出，全海岸由海蚀地貌单元和海积地貌单元组成。为了实现不同地形单元的不同插值，首先要按照弯曲特征对海岸线进行划分，对多个特征单元下的曲线隐含弯曲特征进行提取，提取结果如图3所示。

图3 曲线隐藏弯曲特征提取示意图

对图3中海岸线进行弯曲单元提取后的有序集为{C2，7，C8，10，C11，18，C18，22}，其中Ci，j表示提取的弯曲特征点。

2.2 设置分形插值约束控制参数

除了提取的隐藏弯曲特征之外，还可提取曲线隐弯的敏感性特征、保单调性特征和保凸特征，得到曲线信息的综合隐弯特征提取结果[5]。假设给定函数g(x)插值数据点集合为{(xi，fi)}并且满足如下关系式

fi≠g(xi)

(1)

φS(x)是三次有理样条分形插值函数，φ(x)为经典三次有理样条插值函数。如果φS(x)大于等于g(x)或小于等于g(x)，则φS(x)是关于g(x)的约束插值。由此可以得出如下关系

(2)

式中D0为常数参量。若要φS(x)小于等于g(x)，则存在

(3)

为了找到合适的约束条件，定义如下不等式

(4)

由于以上不等式对于i属于任何值都成立，则可以让隐藏特征向量满足如下约束条件

(5)

通过式(2)到式(5)的推导便可以得出曲线可控分形插值的信息隐藏特征约束条件[6]。

2.3 计算插值点基值

为了避免数据点集中在插值点的一侧，导致误差增大，采用方位加权平均法计算插值参考值。插值M点时，将平面分为以M为中心的四个象限，然后将每个象限平均划分为n个象限，即最终将平面划分为4n个象限[7]。并在每个区域中寻找最接近M的点，设该点的坐标为(xi，yi，zi)它到M点的距离为ri。则M点的插值表达式表示为

(6)

其中参数ci可以表示为

(7)

而rl表示的是j和m两点之间的距离值。如果M点的坐标正好与一个原始数据点B重合，那么M点的插值就等于B点的值[8]。计算实际插值点基值时，输入初始曲线数据点和n的值，并确定插值点的地理坐标。分别在4n个区域中寻找到最接近插值点的点，并计算它与插值点之间的距离，利用式(6)计算插值点的值，反复计算，最终得到全部插值点的值。

2.4 确定分形插值次数与维数

根据原始比例尺和目标比例尺之间的插值关系，结合各分划元的弯曲特性，分别计算各分划元对应目标分辨率的插值次数[9-10]。假设规则分形插值应用于图4中的线段AB，并且移动方向垂直于要插值的边缘。

图4 一维规则分形插值示意图

设原始线段AB的长度为l0，经第一个分形插值得到的移位点C与AB之间的角度是θ，即分形偏移角，并且每一次迭代之后产生的移位点与对应边所构成的角度都为θ。

利用原比例尺与目标比例尺的插值关系，结合各分划单元的弯曲特性，分别计算各分划单元对应目标分辨率的插值次数。此外，式(10)中应用分形插值维数，该参数的计算公式可表示为

(8)

式中ε表示测量单元的尺寸，而N(ε)为规则图形的测量单元数[11]。

2.5 实现曲线信息隐藏特征可控分形插值

分形插值函数产生于一类特殊的迭代函数系统。在IFS中，当映射为仿射变换时，分形插值函数中，如果平面上的点集连续函数f(x)满足如下关系式

f(xi)=yi

(9)

则称f(x)为插值函数。构造IFS为

IFS={R2|ωi}

(10)

其中ωi定义为

(11)

其中，ai、ci、di、ei和fi表示的是实系数。设定i则可求出以上五种实系数的实值，选di为常数，为保证为压缩映射，di的取值区间为[0，1]，那么di为ωi的纵向压缩因子。一般情况下，分形内插曲线的复杂性主要由纵向压缩因子di控制，当|di|较小时，曲线相对比较平滑。

利用分形插值函数，在信息隐藏特征约束下，以每个弯曲单元组成的平均线段作为弯曲单元规则分形的起始边长，得到了曲线边长与偏移量的关系，从而得到了曲线的分形插值结果[12]。对于非曲线部分，式(12)所示的插值函数仍可用于分形插值。也就是将各线段的中间点作为移位种子点，弯曲点随机分布在与线段方向垂直的线段两侧。在同一目标比例下，偏移值设置为所有弯曲的最小值，内插时间设置为所有弯曲的最小值。将曲线和非曲线部分分别实现了分形插值，并按海岸线坐标点的顺序将各段的插值连接起来，得到最终插值曲线

3 仿真分析

为了检测设计的曲线信息隐藏特征约束可控分形插值算法的分形插值质量，设计仿真。利用 MATLAB数学软件作为仿真的主要运行环境，其运行界面如图5所示。

图5 仿真运行界面

另外将 OpenGL开放图库作为实验样本的主要来源，为实验提供足够的数据样本，以保证实验结果的准确性。OpenGL设置编译环境，编译 OpenGL时，首先要添加 OpenGL的库文件，其中主要包括 OpenGL核心库和 OpenGL实用库，核心库以1开头，包含100多个图形处理函数为矩阵变换光照效果，以及物体的颜色添加等效果操作，而实用库 glu核心库则使用图形处理函数对地形的纹理映射坐标变化进行操作，等等。编写程序时，需要将这两个库文件添加到头文件中，以便在图形处理时添加各种图形处理函数，以便于绘图。

仿真期间，OpenGL数据库选取了一条曲线作为实验样本，选取沿海城市的海岸线数据，该样本对象长约45 km，尺度为1：200万。将所设计的曲线信息隐藏特征约束可控分形插值算法与传统分形插值算法及文献[9]中提出的多元多项式插值算法进行了比较，并与实际的1∶100万和1∶50万等要素海岸线数据进行了形态化和精度对比分析。一是对海岸线进行弯曲单元划分；图6显示了实验对象弯曲结构的基本单元。

图6 仿真对象弯曲结构单元

同理可以得出其它曲线样本的选择与设置情况，其中部分样本的设置数据如表1所示。

表1 仿真样本参数设置表

通过三种分形插值算法的运行，分别得出曲线处理结果如图7所示。

图7 曲线1：100万分形插值结果对比图

为了实现对分形插值结果质量的量化对比，将图7的插值处理结果转化成坐标点，并与收集的坐标点进行对比，从而得出插值结果与实际结果之间的误差，并计算出插值处理后研究样本曲线的分维数，经过相关参数的计算与对比，得出仿真结果如表2所示。

表2 仿真测试对比结果

综合图7中显示的直观插值结果和表2中的量化对比结果可以看出，相比于两个对比插值算法，设计算法得出的结果更加接近实际的1：100万曲线数据，且插值前后曲线的分维数相近，说明设计的分形插值算法能够最大程度的保留曲线的分形特征。

4 结束语

按照曲线所呈现的不同弯曲特征对曲线进行地貌单元划分，将传统的整体分形插值转换为将曲线分形特征作为划分单元的差分分段插值组合，分形内插每个单元，并结合每个划分单元的弯曲特性对分形参数进行约束控制，从而实现曲线不同单元的弯曲特性约束。在实际的制图工作中，采用所设计的分形插值算法，能有效地保留真实地形特征，保证了制图结果信息的完整性和准确性。但仿真中，设定的插值目标比较单一，所选实验样本数目较少，所得到的实验结果可信度不高，针对这一问题，今后仍需进一步优化和补充。