约束下考虑坐标分量误差相关性的直线拟合

宋占峰; 郭捷佳; 李军

doi:10.3969/j.issn.0258-2724.20200120

约束下考虑坐标分量误差相关性的直线拟合

doi: 10.3969/j.issn.0258-2724.20200120

中南大学土木工程学院，湖南长沙 410075

基金项目: 国家自然科学基金（51678574）

详细信息

作者简介:
宋占峰（1973—），男，副教授，博士，研究方向为道路与铁道线路优化设计方法，E-mail：songzhanfeng@csu.edu.cn

通讯作者:
李军（1973—），男，副教授，博士，研究方向为道路与铁道工程信息化及优化，E-mail：lijun_csu@csu.edu.cn

中图分类号: U212.3
计量
- 文章访问数: 498
- HTML全文浏览量: 275
- PDF下载量: 23
- 被引次数: 0
出版历程
- 收稿日期: 2020-03-24
- 修回日期: 2020-08-03
- 网络出版日期: 2020-08-24
- 刊出日期: 2020-08-24

Fitting a Straight-Line to Data Points with Correlated Noise Between Coordinate Components under Constraints

School of Civil Engineering，Central South University，Changsha 410075，China

摘要

摘要:
直线拟合在曲线拟合研究及工程实践中受到广泛关注，常用的普通最小二乘和正交最小二乘忽略了坐标分量误差相关性的存在. 基于此，首先论证了在铁路线路整正中全站仪测量坐标点的纵横坐标间存在误差相关性，同时线路中直线的拟合受到相邻线元的约束；然后，基于极大似然估计及拉格朗日条件极值原理，推导出了顾及约束和坐标分量误差相关性的直线拟合通用模型，并给出了高斯-牛顿迭代算法搜索最优解；最后，采用了实测的数据进行了验证及测试. 试验结果表明：该方法能在任何误差分布情况下考虑约束估计直线参数及其精度；考虑坐标相关误差时，参数估计精度在约束及无约束下分别提高了9.2%和2.7%；高斯-牛顿算法在约束及无约束情况下分别仅6次及3次迭代就搜索出最优直线.
- 直线 /
- 曲线拟合 /
- 参数估计 /
- 误差相关 /
- 条件极值 /
- 算法
Abstract:
Straight-line fitting has received extensive attention both in curve fitting research and engineering practice. The methods of ordinary least squares and orthogonal least squares fitting ignore the existence of the observation error correlation. The coordinate pairs of surveying points, obtained by a total station in railway realignment, not only have different levels of precision but also have correlated noise. Meanwhile, straight-line fitting is usually under constraints in the realignment. Thus, a straight-line fitting model was derived based on the maximum likelihood estimation and Lagrange conditional extremum theory, considering constraints and correlated noise between coordinate components, and a Gauss-Newton algorithm was presented to search for the optimum. The method was tested with the field surveying data. Experimental results show that the proposed fitting method is capable of estimating straight-line parameters and their precisions in all circumstances by specifying stochastic models. When considering correlated noise, the precision of estimated parameters improve 9.2% with a constraint and improve 2.7% without constraints, respectively. The Gauss-Newton algorithm takes only 6 and 3 iteration times with a constraint and without constraints respectively, for locating the optimum straight-line.
- straight-line /
- curve fitting /
- parameter estimation /
- correlated noise /
- conditional extremum /
- algorithm

HTML全文

混沌与密码学之间存在着普遍的相似性，这使得基于混沌的密码学成为热门研究之一，如混沌流密码^[1]、混沌Hash函数^[2]、混沌S盒^[3]和混沌图像加密^[4-10]. 由于数字图像在军事、医疗、商业等各领域的普遍应用，其安全性研究受到广泛重视. 而传统的加密方案，如AES （advanced encryption standard）、DES（data encryption standard）等，对数字图像并不适用，使得基于混沌的图像加密方案逐渐受到研究者们的青睐.

混沌系统的选择对于混沌图像加密算法来说至关重要. 混沌系统一般可以分为一维混沌系统^[11-12]和高维混沌系统^[13-14]两大类. 时空混沌是一种复杂的混淆系统，它在图像加密中的应用日益广泛. 文献[15]运用耦合映像格子设计伪随机位序列生成器，并提出了一种基于伪随机比特序列和DNA （deoxyribo nucleic acid）编码的加密算法. 文献[16]提出了一种基于自适应动态密钥流提取技术的块混沌图像加密算法，该算法将时空混沌系统与Tent-Sine系统相结合来生成混沌序列，并以此为基础加密图像. 从当前的研究看，从混沌系统中抽取的混沌序列在图像加密过程中发挥了重要的作用，对整个加密算法的安全性至关重要. 虽然选择高维或者复杂的混沌系统能够保证所产生序列的复杂性，有效防止攻击者对序列的预测与重构，但是，这些复杂混沌系统的状态值在相空间的分布往往是不均匀的，从而为攻击者进行统计攻击或者暴力攻击提供了便利. 文献[17]正是利用了这种不足，对一种基于DNA编码和时空混沌的图像加密算法实施了有效的攻击.

针对上述安全问题，本文将分段时空混沌与暂态变换结合，构造了一个新的混沌模型T2DCML（T-2D coupled map lattices）. 该模型以分段混沌系统作为局部映射，很好地平衡了系统复杂性和效率之间的关系. 同时，利用暂态变换实现了模型状态值的均匀分布，保证了其所产生的混沌序列的高度安全性. 基于T2DCML模型，本文进一步提出了一种图像加密算法. 该算法依据矩阵变换简化了图像的置乱操作，无需如传统的混沌置乱方法那样对矩形图像预处理，增强了算法的适用性. 仿真实验及性能分析表明，该算法能够有效保证图像加密的安全性，满足图像在网络中安全传输的需求.

1. 混沌模型

1.1 二维耦合映像格子模型

耦合映像格子（coupled map lattices，CML）模型是一类典型的时空混沌模型，在混沌密码中得到逐步广泛的应用. 为了进一步增强模型的复杂性，一维CML模型被扩展到了二维CML （2DCML）模型，其常用的数学表达式如式（1）.

$\begin{split} &y_{n + 1}^{\left( {i,j} \right)} = \left( {1 - \varepsilon } \right)f\left( {y_n^{\left( {i,j} \right)}} \right) +\frac{\varepsilon }{4}\left[ f\left( {y_n^{\left( {i + 1,j} \right)}} \right) +\right. \\ &\quad \left. f\left( {y_n^{\left( {i - 1,j} \right)}} \right) + f\left( {y_n^{\left( {i,j + 1} \right)}} \right) + f\left( {y_n^{\left( {i,j - 1} \right)}} \right) \right], \end{split}$

(1)

式中：n为耦合映像格子模型中格子状态值的时间维度； $y_{n + 1}^{\left( {i,j} \right)}$ 为第i行、第j列的格子在第n + 1时刻的状态值，i=1, 2, ···, R，j=1, 2, ···, L， $R,L\in {\mathbb N}_+$ ； $\varepsilon \in$ (0,1)为耦合强度；f(•)为局部混沌函数. 　　对尺寸为R × L的2DCML，规定其周期边界条件为 $y_{n + 1}^{\left( {i + R,j} \right)} = y_{n + 1}^{\left( {i,j} \right)},\;\;y_{n + 1}^{\left( {i,j + L} \right)} = y_{n + 1}^{\left( {i,j} \right)}$ .

为了减少迭代f (•)的计算量，将上述2DCML简化为式（2）.

$\begin{split} &y_{n + 1}^{\left( {i,j} \right)} = \left( {1 - \varepsilon } \right)f\left( {y_n^{\left( {i,j} \right)}} \right) + \\ &\quad\frac{\varepsilon }{2}\left[ {f\left( {y_n^{\left( {i + 1,j} \right)}} \right) + f\left( {y_n^{\left( {i,j + 1} \right)}} \right)} \right]. \end{split}$

(2)

将式（3）所示的分段Logistic映射（piecewise logistic map，PLM）选为2DCML模型的局部混沌函数，因为它具有比Logistic映射更大的李雅普诺夫指数（Lyapunov exponent，LE）^[18]，能够更好地保证模型的复杂性.

${x_{n + 1}} = \left\{ {\begin{array}{*{20}{l}} {{N^2}\mu \left( {{x_n} - \dfrac{{i - 1}}{N}} \right)\left( {\dfrac{i}{N} - {x_n}} \right),}\quad{\dfrac{{i - 1}}{N} < {x_n} < \dfrac{i}{N},}\\ {1 - {N^2}\mu \left( {{x_n} - \dfrac{i}{N}} \right)\left( {\dfrac{{i + 1}}{N} - {x_n}} \right),}\\ \quad{\dfrac{i}{N} < {x_n} < \dfrac{{i + 1}}{N},}\\ {{x_n} + \dfrac{1}{{100N}},}\quad{{\rm{ }}{x_n} = 0,\dfrac{1}{N},\dfrac{2}{N}, \cdots ,\dfrac{{N - 1}}{N},}\\ {{x_n} - \dfrac{1}{{100N}},}\quad{{x_n} = 1,} \end{array}} \right.$

(3)

式中：x_n $\in$ (0,1)为PLM第n时刻的状态值； $\mu \in$ (0,4]为控制参数；N为函数的分段总数.

1.2 2DCML模型的性能分析

1.2.1 李雅普诺夫指数

根据文献[19]的研究结果，可得式（2）所描述的2DCML模型的LE解析式为

$\begin{split} &{e_{{\rm{LE}}}} = {\lambda _{f\left( y \right)}} +\frac{1}{2}\ln \left| {1 + \frac{3}{2}{\varepsilon ^2} - 2\varepsilon + \varepsilon \left( {1 - \varepsilon } \right)} \right. \times\\ &\quad \left. {\left( {\cos \frac{{2i{\text{π}} }}{R} + \cos \frac{{2j{\text{π}} }}{L}} \right) + \frac{{{\varepsilon ^2}}}{2}\cos \left( {\cos \frac{{2i{\text{π}} }}{R} - \cos \frac{{2j{\text{π}} }}{L}} \right)} \right|, \end{split}$

(4)

式中： $\lambda$ _{f (y)}为局部函数f (y)的LE.

由式（4）知，当i=R， j=L时，模型的LE取得最大值. 即2DCML的最大LE由局部混沌函数PLM的LE决定. 为了保证模型具有复杂的动力学行为，本文设置 $\mu$ = 4. 同时，PLM模型的LE与分段数N的关系如图1所示. 由图1中可知：不论N取何值，PLM的LE均为正数，并且随着N的增大而增大. 这说明PLM作为2DCML的局部函数能够很好保持该模型整体的混沌特性. 在权衡PLM的保持良好非线性和具有较大LE值的情况下，本文设置N = 64.

图 1 局部混沌函数PLM的LE

Figure 1. LE of local chaotic function PLM

下载: 全尺寸图片幻灯片

1.2.2 分叉图

由式（4）可知，模型的最大LE与其尺寸无关. 为了便于硬件实现，设置R = L = 8. 在兼顾格子之间必要耦合强度且LE取得较大值的条件下，设置 $\varepsilon$ = 0.1. 在2DCML模型中，每个格子的动力学性能相似，所以以格子(4,4)为代表分析模型的分叉情况，如图2所示.

图 2 2DCML模型中格子（4,4）的分叉图

Figure 2. Bifurcation diagram of lattice (4,4) in 2DCML

下载: 全尺寸图片幻灯片

在中，无论 $\mu$ 为何值模型都处于混沌状态，并且随着 $\mu$ 的增加，其分叉行为变得更加复杂，在 $\mu$ = 4时其分叉行为最复杂，混沌性能最好. 因此，本文将 $\mu$ 设置为4.

1.2.3 遍历区间

遍历区间的大小与密码学中混沌的不可预测性密切相关. 在 $\mu$ = 4，N = 64时，绘制2DCML模型中格子(4,4)的遍历区间，如图3所示. 从图3中可以看出：模型能够遍历整个相空间区间(0,1). 这说明2DCML模型具有良好的遍历性.

图 3 2DCML模型中格子(4,4)的遍历图

Figure 3. Ergodic diagram of lattice (4,4) in 2DCML

下载: 全尺寸图片幻灯片

1.2.4 概率密度分布

概率密度分布描述了状态值在相空间中的分布情况. 2DCML模型的状态值的概率密度分布如图4所示. 从图4中可以看出：该模型状态值的概率密度分布是不均匀的. 这种现象为统计攻击提供了便利，容易产生安全问题，因此不利于该模型在信息安全中的应用.

图 4 2DCML的概率密度分布

Figure 4. Probability density distribution of 2DCML

下载: 全尺寸图片幻灯片

1.3 均匀化处理

为了在2DCML模型中获得更均匀的状态值分布，本文设计了一个基于暂态数据的转换函数T. 假设计算机中一个定点数的精度是2A位（A为定点数精度的一半），对于任意定点数u $\in$ (0,1)，其二进制格式可以表示为

$u = 0.{u_1}{u_2} \cdots {u_{2A}},$

(5)

式中：u_k $\in$ {0,1}，k = 1，2，···，2A表示小数点后面的第k位.

变换函数T的定义如下：

函数名称：T

输入：u //在区间(0,1)上的定点数

输出：o //转换后的输出定点数

过程：

//根据 $u$ 的二进制格式构造v

v = 0.u_{A + 1} u_{A + 2}···u_2Au₁u₂···u_A

//将二者乘积 $t$ 表示成二进制格式

t = u × v = 0.t₁t₂···t_2At_{2A + 1}···t_4A

//将 $t$ 的二进制序列分为前、后两部分并按位异或

o = 0.（ t₁ $\oplus$ t_{2A + 1}）（ t₂ $\oplus$ t_{2A + 2}）···（t_2A $\oplus$ t_4A）

END

在函数T中，所有的变量都是长度为2A的定点数. 对于乘积t，只保留了小数点后的前2A位，舍弃的后2A位为暂态数据. 文献[]研究表明，暂态数据拥有良好的随机性质. 因此，通过与暂态数据进行异或操作，输出结果o具有很好的随机性. 由于精度有限，函数 $T$ 在计算机实现过程中不能直接通过将u和v相乘. 但通过大整数之间的乘法规则，即将二进制整数u₁u₂···u_2A和u_{A + 1}u_{A + 2}···u_2Au₁u₂···u_A 的乘法代替定点数乘法u × v，即可得到暂态数据.

1.4 T2DCML模型的性能分析

以1.2节中2DCML模型为基础，将该模型迭代后产生的状态值使用暂态函数T进行变换，进而得到新的暂态均匀化的混沌模型，为描述方便将其称为T2DCML模型.

在T2DCML模型中，设置模型中的参数R = L = 8，N = 64. 采用同样的方法，测试其分叉情况如所示. 从中可以看出：无论 $\mu$ 取何值，T2DCML都具有复杂的分叉情况. 同时对比图2，可以看出：T2DCML模型具有更复杂的分叉行为. 这说明T2DCML模型的混沌性能得到了增强.

图 5 T2DCML模型中格子(4,4)的分叉图

Figure 5. Bifurcation diagram of lattice (4,4) in T2DCML

下载: 全尺寸图片幻灯片

T2DCML产生混沌序列的概率密度分布如图6所示. 与图4相比，T2DCML模型的概率密度已趋于均匀分布. 这表明T2DCML模型所产生的序列具有良好均匀性，能够有效满足相应的安全要求.

图 6 T2DCML的概率密度分布

Figure 6. Probability density distribution of T2DCML

下载: 全尺寸图片幻灯片

为了进一步说明T2DCML模型产生的序列的随机性，本文采用NIST （National Institute of Standards and Technology）随机性检测标准对其进行测试. 设置参数 $\alpha$ = 0.01， $\beta$ = 1 000，序列长度为10⁶位，得到的测试结果如所示. 从中可以看出：P值均大于 $\alpha$ 且通过率都在区间 $\left( {1 - \alpha } \right) \pm 3\sqrt {\alpha /\beta }$ 内，T2DCML所产生的序列通过了全部的测试项（其中带 * 的测试指标的P值代表的是平均值）. 测试结果说明，T2DCML所产生的序列具有良好的随机性，为图像加密奠定了良好的基础.

表 1 NIST套件的测试结果

Table 1. Test results of NIST suites

测试指标	P 值	通过率	结果
Frequency	0.719 747	0.993	通过
BlockFrequency	0.996 335	0.988	通过
CumulativeSums*	0.817 162	0.995	通过
Runs	0.765 632	0.988	通过
LongestRun	0.071 620	0.987	通过
Rank	0.179 584	0.990	通过
FFT	0.492 436	0.992	通过
NonOverlappingTemplate*	0.496 164	0.990	通过
OverlappingTemplate	0.209 948	0.983	通过
Universal	0.755 819	0.989	通过
ApproximateEntropy	0.075 719	0.986	通过
RandomExcursions*	0.627 887	0.989	通过
RandomExcursionsVariant*	0.540 402	0.992	通过
Serial*	0.676 598	0.986	通过
LinearComplexity	0.096 000	0.997	通过

下载: 导出CSV

| 显示表格

2. 算法设计

2.1 图像加密算法

本文采用置乱扩散结构作为图像加密的框架. 在该算法中，加密后的像素点不仅取决于其原始位置和值，还取决于其周围的其他像素点. 在置乱阶段，利用T2DCML模型所产生的序列构造了两个初等变换矩阵，对像素点矩阵进行置乱. 在扩散阶段，从T2DCML模型状态值中提取整数序列，对置乱后的像素点矩阵进行扩散，并利用明文反馈调整T2DCML模型的状态值，增强加密算法抵抗选择明文攻击的能力. 在交替进行多伦置乱与扩散操作后，输出生成密文图像. 加密算法的具体步骤如下：

步骤1　假定图像大小H × W，将其转化为一个像素点矩阵 ${\boldsymbol{V}} \in {\mathbb N}_+ ^{H \times W}$ .

步骤2　假定T2DCML模型的大小是R × L. 输入PLM的初始状态值x₀，对PLM迭代100次以消除初值x₀的影响. 然后，继续迭代PLM模型R × L次，获得每次迭代产生的状态值序列. 按照从左到右、从上到下的顺序赋值给T2DCML模型，完成初始化，如式（6）所示.

$\left\{ {\begin{array}{l} y_0^{\left( {0,0} \right)} = {x_{101}},\; y_0^{\left( {0,1} \right)} = {x_{102}},\;\cdots ,\;y_0^{(0,R - 1)} ={x_{100 + R}},\\ \cdots \\ y_0^{\left( {i,j} \right)} = {x_{100 + iL + j + 1}},\;\cdots ,\;y_0^{\left( {L - 1,R - 1} \right)} = {x_{100 + LR}}, \end{array}} \right.$

(6)

式中： $y_0^{\left( {i,j} \right)}$ 为T2DCML模型中第i行、第j列格子的初始状态值；x_100+n为PLM的第100 + n个状态值.

步骤3　构造两个初等矩阵P和Q，包括以下4个子步骤：

1）迭代一次置乱T2DCML模型并将产生的R × L个状态值依次存储到序列p中，继续迭代该模型直到p存储了H个浮点数，记作p = {p_h}，h = 1，2，···，H.

2）将p中的元素按照从大到小的顺序排序，排序后的序列记作p′.

3）按式（7）、（8）构造大小为H × H的矩阵P.

${P_{h_1,h_2}} = \delta \left( {{p_{h_1}},{p_{h_2}}} \right),\;\;\;\;h_1,h_2 = 1,2, \cdots,H,$

(7)

$\delta \left( {x,y} \right) = \left\{ \begin{gathered} 1,\quad x = y , \\ 0,\quad x \ne y , \\ \end{gathered} \right.$

(8)

式中： $P_{{h_1},{h_2}}$ 为矩阵P中的第h₁行、第h₂列的元素.

4）类似地，继续迭代T2DCML模型直到序列q存储了W个浮点数，然后排序得到序列q′. 接着按式（9）构造大小为W × W的矩阵Q.

${Q_{w_1,w_2}} = \delta \left( {{q_{w_1}},{q_{w_2}}} \right),\;\;\;\;w_1,w_2 = 1,2, \cdots,W,$

(9)

式中： $Q_{{w_1},{w_2}}$ 为矩阵Q中的第w₁行、第w₂列的元素.

步骤4　置乱像素点矩阵V. 按式（10）得到置乱后的像素点矩阵V′.

${{\boldsymbol{V}}{{'}}}{\boldsymbol{ = PVQ}}.$

(10)

不难发现，所构造两个初等矩阵的逆矩阵与转置矩阵相等，即P′=P^T，Q′=Q^T，这一特性将会用于图像解密的逆置乱，即V = P^TV′Q^T.

步骤5　将V′按从左到右、从上到下的顺序转换为整数序列I. 另外构造一个T2DCML模型，其初始状态与步骤2中的T2DCML模型相同. 每迭代一次T2DCML模型，就从该模型的每个格子中依次提取当前状态值的前8比特，得到整数序列Y. 利用序列Y对序列I进行扩散，如式（11）.

$\begin{split} &{C_m} = {Y_m} \oplus \left[ {\left( {{Y_m} + {I_m}} \right)\text{mod} 256} \right] \oplus \\ &\quad\left[ {\left( {{Y_m} + {C_{m - 1}}} \right)\text{mod} 256} \right], \end{split}$

(11)

式中：I_m为序列I中的第m个字节对应的整数值；Y_m为序列Y中的第m个字节对应的整数值；C₀ $\in$ [0,255]为预设的扩散常数.

若序列I中数据尚未被完全处理，则利用明文反馈的形式调整T2DCML模型的状态值如下：

$Z_m^{\left( {i,j} \right)} = \left( {{{{I_m}}}/{{256}} + Z_m^{\left( {i,j} \right)}} \right)\,\text{mod} \,1,$

(12)

式中： $Z_m^{\left( {i,j} \right)}$ 为抽取Y_m的格子所对应的状态值.

调整状态值后，再次迭代混沌模型并抽取新的状态值补充到序列Y中. 重复该过程，直至序列I中的所有值被处理完.

步骤6　重复步骤3～5的置乱扩散操作M次，最终输出密文图像. 重复的次数越多，加密的效果越好，同时，需要的时间也越多.

2.2 图像解密算法

解密算法的过程与加密算法相反，主要步骤相似，此处不再详述. 需要注意的是，解密所需的所有混沌序列都应该提前生成，以方便与每轮解密所需的序列配对. 式（13）为与式（11）对应的解密公式.

$\begin{split} &{I_m} = \left\{ \left[ {{C_m} \oplus {Y_m} \oplus \left( {{Y_m} + {C_{m - 1}}} \right)\text{mod} 256} \right] - \right.\\ &\left.\quad{Y_m} \right\}\text{mod} 256. \end{split}$

(13)

3. 算法性能分析

3.1 加解密测试

选取典型的标准图像Lena、Baboon、Pepper以及全白（White）和全黑（Black）作为明文图像，对本文提出的图像加密算法进行测试，设置加密次数M = 2，结果如图7所示. 从图7中可以看出：密文图像很好地隐藏了明文图像的有用信息，在视觉上有良好的加密效果；解密算法能够无损地恢复出明文图像. 测试结果表明，本文算法能够有效正常工作，满足通常的图像加解密需求.

图 7 明文图像和密文图像

Figure 7. Plaintext images and ciphertext images

下载: 全尺寸图片幻灯片

3.2 统计分析

从直方图分析和相关性分析两个方面测试了算法的加密效果. 绘制灰度图像Lena、Baboon、Pepper、White和Black的直方图如图8所示. 同时，为了便于对比，在图8中还绘制了加密这些图像后得到的密文图像的直方图. 从如图8可以看出：加密后的图像很好地隐藏了明文图像中的统计信息，使得算法能够有效地抵御统计攻击.

图 8 图像加密前、后的直方图

Figure 8. Histograms before and after image encryption

下载: 全尺寸图片幻灯片

相关性分析的具体测试方法是首先从水平、垂直和对角线3个方向随机选出1 000对相邻的明文像素点和密文像素点，然后计算其相关系数，如式（14）.

${r_{x,y}} = \frac{{{{\rm{cov}}} \left( {x,y} \right)}}{{\sqrt {D\left( x \right)} \sqrt {D\left( y \right)} }},$

(14)

式中：cov(x,y)为序列x与序列y的协方差；D(•)为序列的方差.

得到Lena、Baboon、Pepper、White和Black图像在加密前后相邻像素点之间的相关系数如表2所示：从表2中可以看出：虽然明文图像的像素点之间存在明显的相关性，但是被本文算法加密之后，密文图像的像素点之间的相关系数非常小，不存在相关关系.

表 2 加密前后相邻像素间的相关系数

Table 2. Correlation coefficients between adjacent pixels

图像	水平方向	垂直方向	对角方向
Lena 明文	0.975 1	0.983 1	0.958 2
Lena 密文	0.001 2	0.000 6	0.001 6
Baboon 明文	0.888 0	0.746 8	0.716 0
Baboon 密文	0.001 1	0.000 4	0.003 3
Pepper 明文	0.977 4	0.975 8	0.962 7
Pepper 密文	0.000 8	0.002 6	0.001 2
White 明文	1.000 0	1.000 0	1.000 0
White 密文	−0.001 4	−0.000 1	0.002 9
Black 明文	1.000 0	1.000 0	1.000 0
Black 密文	0.003 0	−0.000 5	−0.002 2

下载: 导出CSV

| 显示表格

直方图分析和相关性分析的结果表明本文提出的图像加密算法具有良好的抗统计攻击能力.

3.3 信息熵

信息熵表征图像中所包含信息的累积和分散，其计算如式（15）.

$H\left( m \right) = - \sum\limits_{l = 0}^{{2^t} - 1} {p\left( {{m_l}} \right)\log p\left( {{m_l}} \right)},$

(15)

式中：p(m_l)为信息值出现的概率；t为自然数.

由于像素点的值使用字节表示，所以其取值范围为[0,255]，对应的信息熵的理想值为8. 加密后图像的信息熵越接近理想值，表明图像中包含的有效信息越少. 表3列出了使用本文算法加密图像Lena、Baboon、Pepper、White和Black前、后的信息熵.

表 3 加密前后图像的信息熵

Table 3. Information entropies of images

图像	明文信息熵	密文信息熵
Lena	7.445 5	7.999 3
Baboon	7.222 2	7.999 2
Pepper	7.364 4	7.999 3
White	0	7.999 3
Black	0	7.999 2

下载: 导出CSV

| 显示表格

从表3中可以看出：无论什么明文图像，在加密之后，其密文图像的信息熵都接近理想值. 这说明本文提出的加密算法能够有效防止密文图像的信息泄露，可以有效地抵抗基于信息熵的攻击.

3.4 密钥分析

3.4.1 密钥空间

对于加密算法，应该有足够的密钥空间（> 2¹²⁸）来抵抗蛮力攻击. 在本文算法中，密钥包括初始状态值x₀ $\in$ (0,1)、控制参数 $\mu \in$ (0,4]、耦合强度 $\varepsilon \in$ (0,1)和扩散常数C₀ $\in$ [0,255]. 假设计算机中的浮点数计算精度为10⁻¹⁴，则算法的秘钥空间大小为10¹⁴ × (4 × 10¹⁴) × 10¹⁴ × 2⁸ $\approx$ 2¹⁵⁰. 根据IEEE浮点数标准， 64位双精度数的精度高于10⁻¹⁴，所以，本文算法的密钥空间大于2¹⁵⁰，能够满足抵抗暴力攻击的要求.

3.4.2 密钥敏感度

对于密钥敏感度，进行以下测试.

测试1：将初始状态值x₀变为x₀ + 10⁻¹⁵；

测试2：将控制参数 $\mu$ 变为 $\mu$ −10⁻¹⁵；

测试3：将耦合强度 $\varepsilon$ 变为 $\varepsilon$ + 10⁻¹⁵；

测试4：将扩散常数C₀变为(C₀ + 1) mod 256；

在上述4种不同的情况下，对图像采用2轮加密，比较密钥变化前后的密文之间的差异. 结果如表4所示. 从表4中可以看出：密钥的微小变化会使密文产生巨大的变化，密文图像的差异都在99.5%以上. 说明该算法具有良好的密钥敏感性.

表 4 密文图像的差异

Table 4. Differences between ciphertext images %

图像	测试 1	测试 2	测试 3	测试 4
Lena	99.592	99.614	99.598	99.602
Baboon	99.619	99.599	99.592	99.598
Pepper	99.621	99.622	99.615	99.619
White	99.623	99.618	99.613	99.617
Black	99.607	99.611	99.617	99.579

下载: 导出CSV

| 显示表格

3.5 差分攻击

在差分攻击中，攻击者通常对明文进行轻微的调整，然后比较调整前后产生的密文之间的差异来进行攻击. 对于图像加密的差异攻击，通常使用像素变化率（number of pixel change rate，NPCR）和统一平均变化强度（unified average change intensity，UACI）这两个指标进行评估，相应的计算如式（16）、（17）.

${I_{{\rm{NPCR}}}} = \frac {1}{{HW}} {{\displaystyle\sum\limits_{h,w} {D\left( {h,w} \right)} }}\times 100{\text{%}} ,$

(16)

${I_{{\rm{UACI}}}} = \frac{1}{{HW}} {\frac{{\left| {{C_1}\left( {h,w} \right) - {C_2}\left( {h,w} \right)} \right|}}{{255}}} \times 100{\text{%}} ,$

(17)

式中：C₁、C₂为两个密文图像，它们对应的明文图像只有一个像素点的值不同；w = 1,2,···,W；D(h,w)定义为

$D\left( {h,w} \right) = \left\{ \begin{gathered} 1,{\text{ }}{C_1}\left( {h,w} \right) \ne {C_2}\left( {h,w} \right) , \\ 2,{\text{ }}{C_1}\left( {h,w} \right) = {C_2}\left( {h,w} \right) .\\ \end{gathered} \right.$

(18)

NPCR和UACI理想值分别为99.6%和33.3%. 表5展示了不同图像在2轮加密轮加密后的NPCR和UACI. 从表5中可以看出：NPCR和UACI的计算值已经达到各自的理想值. 说明所提出的算法具有有效抵抗差分攻击的能力.

表 5 密文图像的NPCR和UACI

Table 5. NPCR and UACI of ciphertext images %

图像	NPCR	UACI
Lena	99.59	33.44
Baboon	99.64	33.50
Pepper	99.60	33.50
White	99.59	33.53
Black	99.60	33.49

下载: 导出CSV

| 显示表格

3.6 安全性分析

在本文算法中，T2DCML模型所产生的混沌序列具有至关重要的作用，它驱动着置乱操作和扩散操作的执行. 首先，T2DCML模型属于高维混沌系统，具有良好的混沌性能和复杂的动态行为，能够有效防止攻击者通过相空间的重构的方式来预测它所产生的混沌序列；其次，T2DCML模型有效利用了暂态数据特点，保证了数据分布的均匀性，提高了其所产生序列的随机性，NIST测试的结果进一步验证了这一点. 由于T2DCML产生的序列具有良好的随机性，因此可以有效保证置乱阶段所构造的变换矩阵的随机性，进而保证了置乱变换的安全.

在扩散阶段，本文算法采用明文反馈的方式，对T2DCML的状态值进行了调整. 这种处理方式使得扩散阶段所使用的伪随机序列不仅与混沌系统相关，也与加密的图像相关，从而可以有效防御已知明文攻击和选择明文攻击. NPCR和UACI的测试也有效证实了这一点.

此外，本文算法具有足够大的密钥空间，能满足暴力攻击的要求. 实验测试的结果反映出由本文算法加密的图像，其直方图分布均匀，像素点间没有相关性，密文图像的信息熵非常接近理想值8，能够有效抵抗统计攻击和信息熵攻击能力.

3.7 效率分析

在本文算法中，首先需要不断迭代T2DCML模型，并从中抽取出相应的状态值构造变换矩阵，进行置乱操作，然后，再迭代混沌映射产生扩散操作所需要的伪随机序列. 与2DCML模型相比，T2DCML在混沌系统迭代之后还需要进行1次T变换操作. 在T变换操作中，需要对状态值进行1次移位操作，1次乘法操作和1次异或操作. 虽然本文算法中引入了T变换操作，但由于该操作增加的计算量仅为少量的几次基本运算，所以对运算效率的影响很小. 因此本文算法的运算效率与已有的基于时空混沌模型的图像加密算法^[15-16]相当. 使用Python语言实现算法，在CPU为Intel(R) Core(TM) i3-4005U的笔记本电脑上测试加密速度，得到加密时间与加密像素点之间的关系如图9所示. 从图9中可以看出：加密时间与加密图像的尺寸之间是呈线性变化关系的. 这表明本文算法中所采用加密变换能够很好适应图像尺寸的变化，能够满足在Internet网中进行图像加密的效率需求.

图 9 加密时间与加密像素点数量的关系

Figure 9. Relation between encryption time and number of pixels

下载: 全尺寸图片幻灯片

同时，T2DCML模型是一个高维的复杂混沌系统，它能产生具有非常良好加密性能的混沌序列，但是迭代该模型的计算量要高于迭代简单混沌系统的计算量，因此本文算法的效率要略低于这类图像加密算法^[21]. 此外，由于T2DCML模型是由多个格子组成，每个格子相对独立且计算量相当，在未来的工作中可以考虑引入并行处理措施，进一步提高本文算法的效率.

3.8 对比分析

为了进一步说明本文算法的性能，将该算法与同样基于混沌映射的算法^[4-10]比较了512 × 512的Lena图像的性能，结果如表6所示. 在所有算法中，本文算法的相关系数的平均值更接近0，信息熵的性能也略大，且NPCR和UACI均已达到理想值. 说明该算法足够安全，能够应用于网络图像的安全传输.

表 6 算法性能对比

Table 6. Comparison of algorithm performance

加密算法	相关系数				信息熵	NPCR/%	UACI/%
加密算法	水平	垂直	对角	绝对平均值	信息熵	NPCR/%	UACI/%
本文算法	−0.002 5	−0.000 2	0.001 1	0.001 3	7.999 3	99.63	33.60
文献[4]	−0.022 3	−0.008 4	−0.008 6	0.013 1	7.997 4	99.61	33.46
文献[5]	−0.038 1	−0.029 1	0.002 7	0.023 3	7.999 2	99.61	33.45
文献[6]	0.069 3	0.061 0	−0.024 2	0.051 5	7.999 1	99.57	33.41
文献[7]	0.001 4	0.003 8	0.001 1	0.002 1	7.999 3	99.59
文献[8]	−0.023 0	0.001 9	−0.003 4	0.009 4	7.969 6	99.62	33.51
文献[9]	−0.014 4	−0.003 4	0.010 7	0.009 5	7.997 0	99.60	32.91
文献[10]	0.016 3	−0.002 9	0.030 9	0.016 7	7.999 3	99.60	33.45

下载: 导出CSV

| 显示表格

4. 结　论

本文提出了一种基于均匀化时空混沌的图像加密方案.

1）提出了一类分段时空混沌系统，以较小的计算代价换来较大的性能提升.

2）对模型的输出序列进行暂态变换，使生成的序列服从均匀分布，增强了混沌模型状态值的不可预测性，保证了混沌序列的高度安全性.

3）提出一类混沌图像加密算法，利用矩阵的初等变换简化图像置乱阶段，弥补了上述两点对加密方案增加的时间复杂度.

4）仿真实验及性能分析表明该算法具有良好的安全性，能够有效地满足图像在网络中安全传输的需求.

致谢：广西密码学与信息安全重点实验室基金（GCIS201908）.

图 1 全站仪测量原理

Figure 1. Measuring principle

下载: 全尺寸图片幻灯片

图 2 拟合原理

Figure 2. Fitting principle

下载: 全尺寸图片幻灯片

图 3 高斯-牛顿迭代算法

Figure 3. Gauss-Newton iteration algorithm

下载: 全尺寸图片幻灯片

图 4 约束及无约束的直线拟合

Figure 4. Straight-line fitting with a constraint and without constraint

下载: 全尺寸图片幻灯片

表 1 实地观测点坐标及采用的3种随机模型

Table 1. Coordinate pairs of field surveying data and three stochastic models for fitting

点号	x/m	y/m	C 中非零元素			P₁中非零元素			P₂中非零元素	P₃中非零元素
点号	x/m	y/m	$\sigma _x^2$ /mm²	$\sigma _y^2$ /mm²	${\sigma _{xy}}$ /mm²	p_x	p_y	p_xy	${p_x}/{p_y}$	${p_x}/{p_y}$
1	688.639	1398.869	7.3371	9.7881	−0.8902	0.1378	0.1033	0.0125	1	10000
2	701.467	1383.525	7.3289	9.3014	−0.9080	0.1381	0.1088	0.0135	1	10000
3	714.294	1368.180	7.3340	8.8888	−0.9115	0.1381	0.1140	0.0142	1	10000
4	727.121	1352.835	7.3547	8.5485	−0.9080	0.1378	0.1185	0.0146	1	10000
5	739.953	1337.495	7.3948	8.2767	−0.9044	0.1371	0.1225	0.0150	1	10000
6	752.783	1322.152	7.4602	8.0684	−0.9071	0.1359	0.1257	0.0153	1	10000
7	765.609	1306.806	7.5584	7.9166	−0.9210	0.1342	0.1281	0.0156	1	10000
8	778.434	1291.460	7.6977	7.8126	−0.9487	0.1319	0.1299	0.0160	1	10000
9	791.262	1276.115	7.8867	7.7477	−0.9909	0.1289	0.1312	0.0165	1	10000
10	804.088	1260.770	8.1340	7.7132	−1.0462	0.1251	0.1320	0.0170	1	10000
11	816.915	1245.425	8.4471	7.7012	−1.1111	0.1207	0.1324	0.0174	1	10000
12	829.740	1230.078	8.8323	7.7054	−1.1805	0.1156	0.1325	0.0177	1	10000
13	842.564	1214.731	9.2939	7.7206	−1.2485	0.1100	0.1324	0.0178	1	10000
14	855.389	1199.384	9.8346	7.7437	−1.3087	0.1040	0.1321	0.0176	1	10000
15	868.213	1184.036	10.4556	7.7729	−1.3546	0.0979	0.1316	0.0171	1	10000
16	881.043	1168.694	11.1562	7.8077	−1.3803	0.0916	0.1309	0.0162	1	10000
17	893.875	1153.353	11.9355	7.8489	−1.3806	0.0855	0.1301	0.0150	1	10000
18	906.703	1138.009	12.7917	7.8981	−1.3511	0.0796	0.1289	0.0136	1	10000
19	919.537	1122.670	13.7218	7.9569	−1.2880	0.0740	0.1276	0.0120	1	10000
20	932.371	1107.331	14.7236	8.0277	−1.1886	0.0687	0.1261	0.0102	1	10000

下载: 导出CSV

表 2 顾及约束和相关误差的直线拟合过程

Table 2. Process of straight-line fitting with both a constraint and correlated noise

迭代数/次	$\hat a$	$\hat b$ /m	${\hat \sigma _0}$ /mm	${\sigma _a}$	${\sigma _b}$ /mm	w/mm
0	−0.681654264	2210.153480	59093.318880	6.14777 × 10⁻²	93044.287650	−479524.603400
1	−0.935165106	2013.498778	5844.096808	6.07990 × 10⁻³	9201.714082	−59428.755230
2	−1.146887043	2183.687057	448.743795	9.66425 × 10⁻⁴	1148.244207	−9789.990571
3	−1.195130784	2221.779805	10.362946	3.19907 × 10⁻⁵	35.137584	−394.045005
4	−1.197201392	2223.403509	16.492003	5.52543 × 10⁻⁵	59.714483	−0.691388
5	−1.197204886	2223.406205	16.525002	5.55595 × 10⁻⁵	60.003229	−0.000002
6	−1.197204886	2223.406205	16.525002	5.55598 × 10⁻⁵	60.003515	0

下载: 导出CSV

表 3 约束下3种随机模型拟合直线的参数估值及其精度

Table 3. Parameter estimation of fitting line and their precisions of three stochastic models with constraints

随机模型	$\hat a$	$\hat b$ /m	${\hat \sigma _0}$ /mm	${\sigma _a}$	${\sigma _b}$ /mm	x_Z/m	y_Z/m	迭代数/次	耗时/s
P₁	−1.19720489	2223.4062	16.525	5.55598 × 10⁻⁵	60.0	1079.9809	930.4478	6	0.494
P₂	−1.19722236	2223.4251	49.031	6.12012 × 10⁻⁵	66.1	1079.9772	930.4522	6	0.503
P₃	−1.19722233	2223.4250	76.478	6.12012 × 10⁻⁵	66.1	1079.9772	930.4522	6	0.496

下载: 导出CSV

表 4 无约束下3种随机模型拟合直线的参数估值及其精度

Table 4. Parameter estimation of line fitting and their precisions of three stochastic models without constraint

随机模型	$\hat a$	$\hat b$ /m	${\hat \sigma _0}$ /mm	${\sigma _a}$	${\sigma _b}$ /mm	迭代数/次	耗时/s
P₁	−1.196269322	2222.672000	2.293655	3.10233 × 10⁻⁵	25.008852	3	0.461
P₂	−1.196259074	2222.663879	6.710739	3.16316 × 10⁻⁵	25.743943	3	0.414
P₃	−1.196259065	2222.663872	0.462488	3.16316 × 10⁻⁵	25.743942	3	0.438

下载: 导出CSV

参考文献(12)

[1]	KRYSTEK M, ANTON M. A least-squares algorithm for fitting data points with mutually correlated coordinates to a straight line[J]. Measurement Science and Technology, 2011, 22(3): 035101.1-035101.9.
[2]	PETROLINI A. Linear least squares fit when both variables are affected by equal uncorrelated errors[J]. American Journal of Physics, 2014, 82(12): 1178-1185.
[3]	丁克良,沈云中,欧吉坤. 整体最小二乘法直线拟合[J]. 辽宁工程技术大学学报(自然科学版),2010,29(1): 44-47. DING Keliang, SHEN Yunzhong, OU Jikun. Methods of line-fitting based on total least-squares[J]. Journal of Liaoning Technical University (Natural Science), 2010, 29(1): 44-47.
[4]	宋占峰,彭欣,吴清华. 基于中线坐标的地铁调线优化算法[J]. 西南交通大学学报,2014,49(4): 656-661. doi: 10.3969/j.issn.0258-2724.2014.04.015 SONG Zhanfeng, PENG Xin, WU Qinghua. Optimization algorithm for horizontal realignment based on coordinate of metro centerline[J]. Journal of Southwest Jiaotong University, 2014, 49(4): 656-661. doi: 10.3969/j.issn.0258-2724.2014.04.015
[5]	宋占峰,王健,李军. 缓和曲线正交拟合的Levenberg-Marquardt算法[J]. 西南交通大学学报,2020,55(1): 144-149. doi: 10.3969/j.issn.0258-2724.20190130 SONG Zhanfeng, WANG Jian, LI Jun. Levenberg-Marquardt algorithm for orthogonal fitting of transition curves[J]. Journal of Southwest Jiaotong University, 2020, 55(1): 144-149. doi: 10.3969/j.issn.0258-2724.20190130
[6]	KARL P. On lines and planes of closest fit to systems of points in space[J]. Philosophical Magazine, 1901, 2(11): 559-572.
[7]	刘经南,曾文宪,徐培亮. 整体最小二乘估计的研究进展[J]. 武汉大学学报(信息科学版),2013,38(5): 505-512. LIU Jingnan, ZENG Wenxian, XU Peiliang. Overview of total least squares methods[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5): 505-512.
[8]	KRYSTEK M, ANTON M. A weighted total least-squares algorithm for fitting a straight line[J]. Measurement Science and Technology, 2007, 18(11): 3438-3442. doi: 10.1088/0957-0233/18/11/025
[9]	SONG Z F, DING H, LI J, et al. Circular curve-fitting method for field surveying data with correlated noise[J]. Journal of Surveying Engineering, 2018, 144(4): 04018010.1-04018010.9.
[10]	AMIRI-SIMKOOEI A R, ZANGENEH-NEJAD F, ASGARI J, et al. Estimation of straight line parameters with fully correlated coordinates[J]. Measurement, 2014, 48: 378-386. doi: 10.1016/j.measurement.2013.11.005
[11]	SHEN Y F, LI B F, CHEN Y. An iterative solution of weighted total least-squares adjustment[J]. Journal of Geodesy, 2011, 85(4): 229-238. doi: 10.1007/s00190-010-0431-1
[12]	鲁铁定,陶本藻,周世健. 基于整体最小二乘法的线性回归建模和解法[J]. 武汉大学学报(信息科学版),2008,33(5): 504-507. LU Tieding, TAO Benzao, ZHOU Shijian. Modeling and algorithm of linear regression based on total least squares[J]. Geomatics and Information Science of Wuhan University, 2008, 33(5): 504-507.

施引文献

附加材料(0)

访问统计

点击查看大图

图(4) / 表(4)

计量

文章访问数: 498
HTML全文浏览量: 275
PDF下载量: 23
被引次数: 0

1. 混沌模型
1.1 二维耦合映像格子模型
1.2 2DCML模型的性能分析
1.3 均匀化处理
1.4 T2DCML模型的性能分析
2. 算法设计
2.1 图像加密算法
2.2 图像解密算法
3. 算法性能分析
3.1 加解密测试
3.2 统计分析
3.3 信息熵
3.4 密钥分析
3.5 差分攻击
3.6 安全性分析
3.7 效率分析
3.8 对比分析
4. 结　论

1. 混沌模型
1.1 二维耦合映像格子模型
1.2 2DCML模型的性能分析
1.3 均匀化处理
1.4 T2DCML模型的性能分析
2. 算法设计
2.1 图像加密算法
2.2 图像解密算法
3. 算法性能分析
3.1 加解密测试
3.2 统计分析
3.3 信息熵
3.4 密钥分析
3.5 差分攻击
3.6 安全性分析
3.7 效率分析
3.8 对比分析
4. 结　论

参考文献(12)

施引文献

附加材料(0)

访问统计

约束下考虑坐标分量误差相关性的直线拟合

doi: 10.3969/j.issn.0258-2724.20200120

作者简介: 宋占峰（1973—），男，副教授，博士，研究方向为道路与铁道线路优化设计方法，E-mail：songzhanfeng@csu.edu.cn

通讯作者: 李军（1973—），男，副教授，博士，研究方向为道路与铁道工程信息化及优化，E-mail：lijun_csu@csu.edu.cn

计量

出版历程

Fitting a Straight-Line to Data Points with Correlated Noise Between Coordinate Components under Constraints

1. 混沌模型

1.1 二维耦合映像格子模型

1.2 2DCML模型的性能分析

1.2.1 李雅普诺夫指数

1.2.2 分叉图

1.2.3 遍历区间

1.2.4 概率密度分布

1.3 均匀化处理

1.4 T2DCML模型的性能分析

2. 算法设计

2.1 图像加密算法

2.2 图像解密算法

3. 算法性能分析

3.1 加解密测试

3.2 统计分析

3.3 信息熵

3.4 密钥分析

3.4.1 密钥空间

3.4.2 密钥敏感度

3.5 差分攻击

3.6 安全性分析

3.7 效率分析

3.8 对比分析

4. 结 论

计量

出版历程

目录

1. 混沌模型

1.1 二维耦合映像格子模型

1.2 2DCML模型的性能分析

1.3 均匀化处理

1.4 T2DCML模型的性能分析

2. 算法设计

2.1 图像加密算法

2.2 图像解密算法

3. 算法性能分析

3.1 加解密测试

3.2 统计分析

3.3 信息熵

3.4 密钥分析

3.5 差分攻击

3.6 安全性分析

3.7 效率分析

3.8 对比分析

4. 结 论

作者简介:
宋占峰（1973—），男，副教授，博士，研究方向为道路与铁道线路优化设计方法，E-mail：songzhanfeng@csu.edu.cn

通讯作者:
李军（1973—），男，副教授，博士，研究方向为道路与铁道工程信息化及优化，E-mail：lijun_csu@csu.edu.cn

4. 结　论

4. 结　论