适用于不规则三角网数字高程模型的信息伪装及还原方法

摘要

本发明涉及一种适用于不规则三角网数字高程模型的信息伪装及还原方法，属于数字高程数据处理技术领域。本发明的信息伪装方法主要包括空间置乱和数值代换两个部分，其中空间置乱采用Tent混沌映射的方式实现，数值代换采用中国剩余定理进行。与传统的信息保护方法相比，本发明采用上述信息伪装的方式进行信息保护具有迷惑性强，安全性能高的突出优点，能够为不规则三角网数字高程模型中的重要高程信息提供安全防护，可以有效保障不规则三角网数字高程模型数据的存储和传输。

说明书

技术领域

本发明涉及一种适用于不规则三角网数字高程模型的信息伪装及还原方法， 属于数字高程数据处理技术领域。

背景技术

不规则三角网(Triangulated Irregular Netting,TIN)是数字高程模型(Digital  Elevation Model,DEM)的一种重要表现形式，通过连接离散的高程采样点，将地 形表达成不重叠的连续三角面，具有数据量小、地形细节表达详细等优点，特别 适用于高精度的地形建模与仿真，在国防和经济领域应用广泛。

数据共享是信息时代的一个重要标志，目前用户可以在开放的网络环境中下 载到全球大部分地区的不同精度的高程数据，但是重点地区尤其是这些地区的高 精度数据，仍具有重要的保护价值。例如，美国将全球90m的SRTM数字高程数 据进行共享，却将更高精度的DEM数据列为本国的重要机密，用于更好的部署 部队、研究高精确制导武器等军事目的。我国生产的各种分辨率的DEM数据， 也仅向公众开放提供1：100万的数据，其他分辨率数据的申领必须经过行政审 批。由于代表了精确的空间定位信息，重要地区的高程数据一旦泄露，会对国家 安全和经济建设造成巨大的损失。

目前针对TIN模型的信息保护主要有信息加密和数字水印两种。信息加密能 够为所有数据提供通用的保护模式，结果一般是无法理解的数据流，加密后数据 在公开信道中传输主要存在以下问题：(1)目标明显，特别容易受到关注。由于 加密成了乱码，这些数据更容易引起注意，受到专门攻击；(2)安全性有待提高。 研究证明，没有任何一种加密算法完全可靠，高性能计算机的出现更为密码分析 提供了极大方便。即使攻击者不能在短时间内进行破译，也可以对原始信息进行 破坏和篡改数，影响数据使用。不规则三角网的数字水印技术是在三维网格水印 的基础上发展而来，近年出现了多种更具有针对性的TIN水印算法。但是由于能 够处理的数据量较小，数字水印更注重版权保护，很少直接用于保护高数数据内 容本身。

发明内容

本发明的目的是提供一种适用于不规则三角网数字高程模型的信息伪装 及还原方法，以解决目前不规则三角网数字高程模型信息保护安全性能不高以 及迷惑性不强的问题。

本发明为解决上述技术问题提供了一种适用于不规则三角网数字高程模型 的信息伪装方法，该信息伪装方法包括以下步骤：

1)将TIN模型高程数据按照高程节点的横坐标大小进行排序，形成只含有高 程数据的一维序列；

2)采用混沌映射将上述一维序列中的数据进行置乱；

3)采用中国剩余定理在空间域上将置乱后的数据进行数值代换，代换后的 数据即为伪装后的三角网数字高程模型数据。

所述步骤2)中的混沌映射采用Tent映射。

所述采用Tent映射进行置乱包括以下步骤：

A.以给定Tent映射的参数和初值作为置乱密钥产生混沌序列X；

B.将混沌序列中要素按照从小到大的顺序排列形成X，并记录其中各要素在 序列X中的原始地址，形成置换序列P；

C.利用一维离散余弦变换将规范化后的高程数据一位序列中的各高程数值 转换到频率域中，形成频率系数序列W；

D.将系数序列W进行分组，对每一组中的频域系数按照置换序列P进行变换， 使每组中第i个位置的数据置换到第p_i个位置上，组合后得到置乱频率系数集合 W'；

E.利用一维离散余弦逆变换将W'转换到空间域上，完成数据置乱。

所述采用中国剩余定理进行数值代换的步骤如下：

a.将经过置乱的所有高程数值进行规范化处理，并将每个高程值h_i分为两部 分：

b_i＝[h_i/1000]

c_i＝h_i(mod1000)

形成数据集合：

B_i＝{b_i|i＝1,2,3,...,L}和C_i＝{c_i|i＝1,2,3,...,L}

其中L表示TIN中高程结点的数量；

b.选择四个的正的素数m₁,m₂,m₃,m₄＞1000作为代换密钥，利用m₁和m₂依 次转换B_2n-1和C_2n-1得到D_2n-1，利用m₃和m₄依次转换B_2n和C_2n得到D_2n，将集合 D_2n-1和D_2n合并形成集合D，其中n＝1,2,3,...,[L/2]；

c.将集合D内的数据归化到原始数据的取值范围内：

${d_i}^{\prime }=H_{\min }+\frac{(d_i-D_{\min })\times (H_{\max }-H_{\min })}{D_{\max }-D_{\min }}$

其中，H_max和H_min分别表示原始高程数据的最大值和最小值，d_i为集合D内 的数据，D_max和D_min表示经中国剩余定理处理后得到代换数组中的最大值和最小 值；

d.将得到的d'_i形成最终的数据集合D'，即得到了经过中国剩余定理伪装的 三角网数字高程数据。

本发明还提供了一种数据还原方法，该数据还原方法包括代换还原和置乱还 原，

所述代换还原是将伪装数据在空间域上利用中国剩余定理还原到代换伪装 之前的状态，是伪装代换的逆过程；

所述置乱还原是将伪装数据在频率域中利用Tent映射还原到原始位置，是伪 装置乱的逆过程。

所述代换还原包括以下步骤：

1)将伪装数据进行规范化处理；

2)利用密钥D_max和D_min，将伪装数据中所有的高程数值利用下式进行转换：

$d_i=D_{\min }+\frac{({d_i}^{\prime }-{H^{\prime }}_{\min })\times (D_{max}-D_{\min })}{({H^{\prime }}_{max}-{H^{\prime }}_{\min })},$

其中，H'_max和H'_min分别表示伪装数据中的最大值和最小值，得到转换后的 数据集合D；

3)利用代换密钥m₁、m₂、m₃、m₄，按照中国剩余定理，对得到的集合D中 的每一个元素进行处理，每一个元素解密可以得到两个原始数据，依次加入数据 集合E；

4)对E中的元素，作如下处理

$\left(\begin{array}{c}{F}_{2n-1}=1000E_{4n-3}+E_{4n-1}\\ F_{2n}=1000E_{4n-2}+E_{4n}\end{array}\right)$

组合得到集合F，为TIN伪装数据进行数据代换前、高程置乱后的结果。

所述置乱还原包括以下步骤：

(1)利用置乱密钥a、x₀和N，根据式1生成混沌序列X，按照置乱方法 得到置乱序列P；

(2)利用一维离散余弦变换将代换还原后的高程集合F转换到频率域中， 得到频率系数集合W'，利用P对其进行反置乱，得到原始频率系数集合W；

(3)利用一维离散余弦逆变换将W转换到空间域上，完成置换还原，得到 原始的高程数据集合，并将其一一对应于原始的空间坐标，得到最终结果即为还 原后的三角网数字高程模型数据。

本发明的有益效果是:本发明的信息伪装方法主要包括空间置乱和数值代换 两个部分，其中空间置乱采用Tent混沌映射的方式实现，数值代换采用中国剩余 定理进行。与传统的信息保护方法相比，本发明采用上述信息伪装的方式进行信 息保护具有迷惑性强，安全性能高的突出优点，能够为不规则三角网数字高程模 型中的重要高程信息提供安全防护，可以有效保障不规则三角网数字高程模型数 据的存储和传输。

附图说明

图1是本发明适用于不规则三角网数字高程模型信息伪装方法的原理示意 图；

图2是Tent映射的分叉图；

图3是原始不规则三角网数字高程模型规范化后的结果；

图4是采用Tent映射空间置乱后的结果图；

图5是采用中国剩余定理代换后的最终伪装数据的示意图；

图6是代换还原后的数据示意图；

图7是经置乱还原后的最终还原数据示意图；

图8是选取不同初值得到的置乱结果示意图；

图9是选取不同初值得到的伪装数据示意图。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步的说明。

本发明的适用于不规则三角网数字高程模型的信息伪装方法的实施例

本实施例中以一幅包含853个离散高程点的TIN DEM数据作为待伪装的信 息，实验条件为Intel Core i3 CPU，2.94GHz，内存2G，显卡缓存256M。为了实 现对上述数据的信息伪装，本发明首先在频率域上利用Tent混沌映射进行数据置 乱，然后在空间域上利用中国剩余定理进行数值代换，共同完成信息伪装，如图 1所示。具体的实施步骤如下：

1.对TIN模型高程数据进行规范化处理

不规则三角网数字高程模型中的数据分布毫无规律，不能直接进行矩阵运算 等数学处理。在进行信息伪装之前，需要先将TIN数据所表示三维空间中不的不 规则高程点转化成能够直接进行处理的形式。一般情况下，TIN模型中结点数据 包含两个坐标值和一个高程值，坐标数据排列不规则，很难归化到类似格网数据 的二维空间中，但规范到一维空间中相对简单。本发明首先将原始的TIN DEM 数据按照高程节点的横坐标大小进行排序，横坐标相同的纵坐标大的为先，可以 将所有结点规范到只含有高程数据的一维序列中，得到结果如附图3所示。

2.利用Tent映射进行空间置乱

混沌映射是一种确定性的非线性伪随机系统，可以利用相同的初始参数重复 产生，但是对初值表现出极端的敏感性，极小的差异所形成的混沌序列大不相同。 由于产生的混沌序列结构极其复杂，很难进行重构和解析，因此特别适用于信息 加密和保密通信，Tent映射构造简单而且搜索效率很高，特别适用于进行一维高 程数值的置乱。

Tent映射又称帐篷映射，是一种分段的一维映射，其表达式如下：

$x_{n+1}=\left(\begin{array}{cc}{\mathrm{\mu x}}_n& 0<x_n<0.5\\ \mu (1-x_n)& 0.5\le x_n\le 1\end{array}\right)---\left(1\right)$

其中，μ∈(0,2)，x_n∈(0,1)可以产生一个序列，其分岔图如附图2所示。通 过分析Tent映射的分岔图可以发现：当大约μ＞1.4以后，改映射进入混沌状态。

频率域上的空间置乱可以通过一点位置变化影响全局变化，能够改变数据的 统计特性，可以抵制相关统计分析的攻击，得到的置乱效果更好。本实施例中利 用Tent映射进行空间置乱的具体步骤如下：

A.给定Tent映射的参数a和初值x₀，作为置乱密钥，将其带入到式1中迭 代N次(大于100)产生混沌序列X＝{x_i|i＝1,2,3,...,N}。本实施例中Tent混沌 映射的初始值分别选择μ＝1.7，x₀＝0.8为置乱密钥，将其带入到公式(1)中迭 代100次产生混沌序列X，表1表示的是该序列的具体内容。

表1

B.比较X中各要素的大小，将其从小到大依次排列形成 X'＝{x'_i|i＝1,2,3,...,N}，并记录其中各要素在序列X中的原始地址，形成置换 序列P＝{p_i|i＝1,2,3,...,N}，p_i表示X'中第i个元素在原始序列X中的位置，本 实施例中得到置换序列P的内容如表2所示。

表2

C.利用一维离散余弦变换将规范化后的高程数值转换到频率域中，形成频率 系数序列W＝{w_i|i＝1,2,3,...,L}，其中L表示TIN中高程结点的数量，将其分成 n＝[L/N]组，本实施例中n为8，对每一组中的频域系数按照置换序列P进行变 换，将其第i个位置的数据置换到第p_i个位置上，组合得到置乱频率系数集合W'。

D.利用一维离散余弦逆变换将W'转换到空间域上，完成数据置乱。

3.利用中国剩余定理进行数值代换

中国剩余定理具体描述如下：

设正整数m₁,m₂,m₃,...,m_k两两互素，m＝m₁m₂m₃...m_k，M_i＝m/m_i，是M_i模m_i的乘法逆元，满足其中i＝1,2,3,...,k。则对于任意k个 整数a₁,a₂,a₃,...,a_k(k≥2)构成的同余方程：

$\left(\begin{array}{c}x\equiv a_1\left({\mathrm{modm}}_1\right)\\ x\equiv a_2\left({\mathrm{modm}}_2\right)\\ .\\ .\\ .\\ x\equiv a_k\left({\mathrm{modm}}_k\right)\end{array}\right)---\left(2\right)$       (式2)

在模m下有唯一解：

$x=M_1{M_1}^{-1}{a}_1+M_2{M_2}^{-1}{a}_1+...+M_i{M_i}^{-1}{a}_i\left(\mathrm{mod}m\right)$            (式3)

根据中国剩余定理的解算过程可知，利用互素的正整数可以将若干个整数转 换成一个大数。同时，根据式2可知：x≡a_i(modm_i)，当m_i＞a_i时，a_i有唯一解， a_i＝x(modm_i),由此可以推定，利用中国剩余定理加密正整数集合 A_i＝{a_i|i＝1,2,3,...,k}时，选用k个大于max(A_i)两两互素的整数，可以得到唯一 结果。

本发明利用中国剩余定理进行数值代换的过程如下：

a.数据预处理

将经过置乱的所有高程值转换成厘米级后取整数，根据陆地高程的取值范 围，保留到厘米级整数时正整数的位数最多为6(小于884443cm)。将每个高程 值h_i分为两部分：

b_i＝[h_i/1000]                (3)

c_i＝h_i(mod 1000)                 (4)

形成数据集合：

B_i＝{b_i|i＝1,2,3,...,L}

C_i＝{c_i|i＝1,2,3,...,L}

其中L表示TIN中高程结点的数量，将高程数据转换成厘米级不仅可以增加 数据伪装的精度，还能够尽量减少b_i等于0的可能性，避免代换过程中0值的参 与，使得计算结果趋于合理。本实施例中所形成的形成集合B_i和C_i的部分内容如 表3所示。

表3

b.利用中国剩余定理进行数值代换

选择四个的正的素数m₁,m₂,m₃,m₄＞1000，作为代换密钥，本实施例中选择 的四个正的素数代换密钥(m₁,m₂,m₃,m₄)为(1021,4597,1039,2351)，利用中国剩 余定理，按照规范化后形成的顺序，利用m₁和m₂依次转换B_2n-1和C_2n-1得到D_2n-1， 利用m₃和m₄依次转换B_2n和C_2n得到D_2n，其中n＝1,2,3,...,[L/2]，D为转换后的 数值集合，即每次利用密码可以加密两个高程值，得到两个新的整数。同时密钥 的个数可以根据实际情况选择，数量越多，计算的复杂度就越高，安全性也越强。 得到的集合D的部分内容如表4所示。

表4

c.归化数值到合理的高程取值范围

通过中国剩余定理转换得到的数值d_i∈D的取值范围为[0,H_m)，其中 H_m＝max(m₁m₂,m₃m₄，)为了增加伪装数据的迷惑性，避免不符合该坐标范围内 高程数值的出现，将其数据归化到原始数据的取值范围内，采用方法如下：

${d_i}^{\prime }=H_{\min }+\frac{(d_i-D_{\min })\times (H_{\max }-H_{\min })}{D_{\max }-D_{\min }}---\left(5\right)$

其中，H_max和H_min分别表示原始高程数据的最大值和最小值；D_max和D_min表 示经中国剩余定理处理后得到代换数组中的最大值和最小值，记录D_max和D_min作 为密钥的一部分。

d.将得到的d'_i形成最终的数据集合D'，即得到了经过中国剩余定理伪装的 TIN数据，如图5所示。

将经过置换和代换的一维离散高程数据按照数据规范化的逆过程依次分配 给TIN模型数据中对应的各个高程结点，就完成了整个信息伪装过程。

TIN DEM的信息伪装除了能够达到预期的伪装效果，具有一定的迷惑性外， 更应该具有足够高的安全性能。为了保证伪装数据的绝对安全，设计的伪装算法 应当具有尽可能的大密钥空间，能够抵抗高速度计算机的穷举分析。只有密钥空 间大于2¹⁰⁰时，才认为该算法是安全的。表面上看，利用Tent映射和中国剩余定 理密钥的选择范围很小，但是其具有极度的敏感性。当其他条件不变，仅将图3 实验中的密钥改为x₀＝0.800001时，得到的结果如附图8和附图9所示。通过分 析可以发现：即使密钥发生极小的变化，得到的伪装数据就有极大的不同。说明 设计的算法对密钥具有极大的敏感性，虽然取值范围有限，但仍具有很大的密钥 空间。

本发明的适用于不规则三角网数字高程模型的信息伪装还原方法的实施例

本实施例针对的是上个实施例中所提供的信息伪装方法，信息还原方法是信 息伪装的逆过程，根据上述实施例中的信息伪装方法，本实施例中的信息伪装还 原方法主要包括代换还原和置乱还原两部分。

1.代换还原

代换还原是指将伪装数据在空间域在利用中国剩余定理还原到代换伪装之 前的状态，是伪装代换的逆过程，伪装数据的信息还原过程和信息伪装过程完全 相反，该过程包括以下步骤：

1)首先按照相同方法将伪装数据进行规范化，方便进行还原处理；

2)利用密钥D_max和D_min，将伪装数据中所有的高程数值利用下式进行转换：

$d_i=D_{\min }+\frac{({d_i}^{\prime }-{H^{\prime }}_{\min })\times (D_{max}-D_{\min })}{({H^{\prime }}_{max}-{H^{\prime }}_{\min })}---\left(6\right)$

其中，H'_max和H'_min分别表示伪装数据中的最大值和最小值，得到转换后的 数据集合D。

3)利用代换密钥m₁、m₂、m₃、m₄，按照中国剩余定理，对得到的集合D中 的每一个元素进行处理，根据式3，每一个元素解密可以得到两个原始数据，依 次加入数据集合E；

4)对E中的元素，作如下处理

$\left(\begin{array}{c}{F}_{2n-1}=1000E_{4n-3}+E_{4n-1}\\ F_{2n}=1000E_{4n-2}+E_{4n}\end{array}\right)---\left(7\right)$

组合得到集合F，为TIN伪装数据进行数据代换前、高程置乱后的结果。

2.置乱还原

置乱还原是指将伪装数据在频率域中利用Tent映射还原到原始位置，是伪装 置乱的逆过程，步骤如下：

1)利用置乱密钥a、x₀和N，根据式1生成混沌序列X，按照置乱步骤B 的方法得到置乱序列P；

2)利用一维离散余弦变换将代换还原后的高程集合F转换到频率域中，得 到频率系数集合W'，利用P对其进行反置乱，得到原始频率系数集合W；

3)利用一维离散余弦逆变换将W转换到空间域上，完成置换还原，得到原 始的高程数据集合，并将其一一对应于原始的空间坐标，得到最终还原后的TIN 数据。

本实施例中选用混沌映射的初始值μ＝1.7，x₀＝0.8以及代换密钥 (m₁,m₂,m₃,m₄)为(1021,4597,1039,2351)，可以依次得到代换还原和置乱还原的 数据，结果如附图6和附图7所示。