一种基于3D Growing Tree迷宫的数字置乱方法

摘要

本发明提供一种基于3D Growing Tree迷宫的数字置乱方法，预先对Growing Tree迷宫生成区域进行人为限定，从而可用于人为指定的任意3D封闭连通区域，同时按迷宫节点更新顺序对迷宫设定区域的每个节点赋予唯一的编号，由此产生迷宫设定区域所有节点的排列，在此基础上构造了基于3D Growing Tree迷宫节点更新序列和节点更新序列复合的置乱方法，从而可将所有节点置乱。本发明所给出的置乱方法具有普适性和灵活性，在使用过程中不存在任何限制，不仅能应用于传统置乱方法所针对的规则区域，例如正方形和矩形区域，也可用于任意选定的3D封闭连通不规则区域置乱。本发明也给出了用于图像位面立方体，RGB立方体和RGB通道立方体的图像置乱方法。

说明书

技术领域

本发明主要涉及信息安全和数字信号处理等交叉研究领域，具体为基于 Growing Tree迷宫生成策略的数字置乱方法，特别涉及基于3D Growing Tree迷 宫的数字置乱方法。

背景技术

近年来，伴随着计算机和网络技术的发展，越来越多的图像在网络中传输， 在给用户提供方便的同时，也带来了一系列的安全隐患。对图像的不当使用和 恶意篡改，不仅涉及个人隐私，也会给社会带来严重负面影响。保障图像的核 心技术是数字图像加密。

在数字图像加密领域，研究最为广泛和灵活的一类图像加密方法，就是在 同一空间内，对图像的重编码技术，即图像置乱技术。

随着计算机技术的飞速发展，数字图像置乱技术已成为数字安全传输和保 密的主要手段。其基本思路就是把一幅图像经过一定的数学变换，转变成面目 全非的另一幅图像，以起到对图像的安全保密作用。

数字图像置乱也是目前隐密术、数字水印、信息分存和可视密码技术中一 项关键预处理技术。已受到了国内外学者的普遍重视，并取得了丰硕的研究成 果。

数字图像置乱最初来源于有线电视信号加密，早期的置乱在位置空间进行， 用于对图像像素位置打乱，这些置乱方法包括行倒置置乱、行平移置乱、行置 换置乱、行循环置乱、行分量切割置乱等。随着置乱技术的不断发展，目前已 提出的置乱方法多种多样，既可用于位置置换，也可用于灰度替代。

当前已提出的置乱方法主要有：基于离散元素序列的置乱方法、基于扫描 路线的置乱方法、基于遍历矩阵的置乱方法、基于迭代函数系统的置乱方法、 基于离散混沌映射的置乱方法、基于中国拼图的置乱方法和基于矩阵变换的置 乱方法等。

目前尽管已提出了多种置乱方法，但传统置乱方法大多只能用于规则区域 置乱，例如正方形和长方形区域，而不能对图像选定的任意不规则区域进行置 乱。

例如基于Fibonacci序列和Lucas序列的置乱方法将置乱图像的宽、高拘泥 为Fibonacci序列和Lucas序列元素；基于SCAN语言和Hilbert曲线的置乱方法 将置换图像的大小约束为2ⁿ×2ⁿ的正方形图像；由于并非所有图像都存在骑士 巡游路径，由此导致了基于骑士巡游的置乱方法只能用于图像宽、高在特定尺 度上的图像；对于奇数阶幻方，其置乱图像边长为奇数，对于双偶阶幻方，其 置乱图像边长为4的整数倍；由于任意阶的拉丁方并非都存在，基于拉丁方的 置乱方法只能用于置乱图像边长为特定尺度的图像，例如边长为pⁿ且p为素数 的图像；对于离散Kolmogorov Flows Map和亚仿射变换，只能用于置乱正方形 图像；传统的基于矩阵的图像置乱方法，其基本表示形式为 X^[i]＝(AX^[i-1])mod N，但由于只有一个尺度参数N，由此决定了基于矩阵的图像 置乱方法只能用于置乱特定尺度的图像，例如正方形图像和对矩形图像的灰度 进行置乱。

在文献二维非等长图像置乱变换(电子学报,2007,35(7):1290-1294)，二维 三角映射及其在图像置乱上的应用(Information Technology Journal,2008,7(1): 40-47),二维双尺度矩形映射及其在图像置乱上的应用(计算机辅助设计与图 形学报,2009,21(7):1026-1034)和多尺度三角映射及其在变尺度置乱上的应用 (International Journal of Computer Applications in Technology,2010, 38(1-3):74-85)，我们将X^[i]＝(AX^[i-1])mod N拓展为X^[i]＝(AX^[i-1])modN，N为有 限个尺度构成的尺度向量，提出了2维非等长变换存在性判据，2维双尺度矩形 映射的特殊形式-2维三角映射，以及2维双尺度矩形映射一般性构造方法和多 尺度三角映射。尽管X^[i]＝(AX^[i-1])modN可用于任意矩形图像置乱，并可对图像 位置和灰度同时置乱，但所提出的方法只能对规则区域进行置乱，不能用于对 选定的任意不规则区域进行置乱。

传统的迷宫生成方法在人工智能和优化计算领域应用较广，一般用于动态 复杂场景的模拟和仿真，在信息安全领域涉及较少，在文献基于迷宫置换和 Logistic混沌映射的图像加密算法(计算机应用，2014,34(7):1902-1908)，我们 探讨了基于DFS迷宫节点入栈顺序和行优先扫描顺序高效产生置换的方法，将 迷宫生成方法应用于任意矩形图像加密，但所提出的方法不能应用于图像的任 意连通不规则封闭区域加密。

发明内容

本发明的目的在于克服现有技术缺陷，提供一种基于3D Growing Tree迷宫 的数字置乱方法，该方法可用于3D任意连通封闭区域数据置乱。

为实现上述目的，本发明采用以下技术方案：

一种基于3D Growing Tree迷宫的数字置乱方法，包括以下步骤：

第1步：设定迷宫初始范围S_init＝()_m×n×l和迷宫有效区域S_maze＝(s_i,j,k)_m×n×l，对 于i＝0,…,m-1,j＝0,…,n-1,k＝0,…,l-1，若则标记s_i,j,k＝-1，反 之则标记s_i,j,k＝0表示该节点未访问，若s_i,j,k>0表示该节点已访问；

第2步：对于i＝0,…,m-1,j＝0,…,n-1,k＝0,…,l-1，记 s_i,j,k.d,d＝0,1,2,3,4,5依次为节点s_i,j,k的下方、右方、上方、左方、底部和顶部墙， 初始化s_i,j,k.d＝-1,d＝0,1,2,3,4,5，-1表示为有墙，0表示无墙；

第3步：选择随机数发生器y＝RG(x)，设定随机数发生器初始值 RG.init＝seed，初始化迷宫节点列表A_maze＝Φ，节点更新序列A_update＝Φ，按随机 数发生器随机产生2个概率P_recent,P_oldest∈[0,1)；

第4步：选取x＝x₀,y＝y₀,z＝z₀，将s_x,y,z分别加到A_maze和A_update， 即A_maze＝A_maze.add(s_x,y,z)A_update＝A_update.add(s_x,y,z)；

第5步：若A_maze≠Φ，则循环执行第6步～第8步

第6步：产生1个随机数P∈[0,1)，若P∈[0,P_recent]，则取A_maze尾部元素作 为当前节点s_x,y,z，反之若P∈[P_recent,P_recent+P_oldest]，则取A_maze头部元素作为当前节 点s_x,y,z，反之则从A_maze中随机取一个元素作为当前节点s_x,y,z， s_x,y,z＝A_maze.at(index),index＝random(A_maze.length)；

第7步：若s_x,y,z周围的邻近节点中s_x+1,y,z,s_x,y+1,z,s_x-1,y,z,s_x,y-1,z,s_x,y,z-1,s_x,y,z+1存在 未访问的有效节点s_{x′,y′,z′}∈S_maze，则将s_{x′,y′,z′}加入到A_maze，即A_maze＝A_maze.add(s_{x′,y′,z′})， A_update＝A_update.add(s_{x′,y′,z′})；

第8步：若s_x,y周围的邻近节点中s_x+1,y,z,s_x,y+1,z,s_x-1,y,z,s_x,y-1,z,s_x,y,z-1,s_x,y,z+1不存在未访问的有效节点s_{x′,y′,z′}∈S_maze，则删除A_maze索引位置为Index位置的元 素，即A_maze.delete(index)；

第9步：利用A_update构造S_maze＝(s_i,j,k)_m×n×l范围内所有节点间的映射关系，从而 将S_maze＝(s_i,j,k)_m×n×l范围内的所有节点置乱。

作为本发明进一步优选方案，第9步中映射方法具体包括以下步骤：

第9.1步选整数作为映射偏移量ll，ll mod A_update.length≠0，将其按式(1)规 范到(-A_update.length,A_update.length)范围内的整数，按式(2)计算index；

ll＝llmodA_update.length   (1)

$\mathrm{index}=\left(\begin{array}{cc}(\mathrm{ll}+A_{\mathrm{update}}.\mathrm{length})\mathrm{mod}{A}_{\mathrm{update}}.\mathrm{length}& \mathrm{ll}<0\\ \mathrm{ll}& \mathrm{ll}>0\end{array}\right)---\left(2\right)$

第9.2步：将S_init复制为T＝(t_i,j,k)_m×n×l；

第9.3步：对于按式(3)将s_i,j,k赋值给t_x,y,z；

(i,j,k)＝A_update(ii),ii＝0,…,A_update.length-1

(x,y,z)＝A_update(kk),kk＝0,…,A_update.length-1   (3)

kk＝(ii+index)modA_update.length

第9.4步：输出T＝(t_i,j,k)_m×n×l。

作为本发明进一步优选方案，选取两个随机初始值 RG₀.init＝seed₀，RG₁.init＝seed₁分别生成迷宫节点更新序列

第9步中映射方法具体包括以下步骤：

第9.1步：输入任意整数作为映射偏移量ll，并将其按式(4)规范到 范围内的整数，按式(5)计算index；

$\mathrm{index}=\left(\begin{array}{cc}(\mathrm{ll}+A_{\mathrm{update}}^0.\mathrm{length})\mathrm{mod}{A}_{\mathrm{update}}^0.\mathrm{length}& \mathrm{ll}<0\\ \mathrm{ll}& \mathrm{ll}>0\end{array}\right)---\left(5\right)$

第9.2步：将S_init复制为T＝(t_i,j,k)_m×n×l；

第9.3：对于按式(6)将s_i,j,k赋值给t_x,y,z；

$\left(\begin{array}{c}(i,j,k)=A_{\mathrm{update}}^0\left(\mathrm{ii}\right),\mathrm{ii}=0,...,A_{\mathrm{update}}^0.\mathrm{length}-1\\ (x,y,z)=A_{\mathrm{update}}^1\left(\mathrm{kk}\right),\mathrm{kk}=0,...,A_{\mathrm{update}}^1.\mathrm{length}-1\\ \mathrm{kk}=(\mathrm{ii}+\mathrm{index})\mathrm{mod}{A}_{\mathrm{update}}^1.\mathrm{length}\end{array}\right)---\left(6\right)$

第9.4步：输出T＝(t_i,j,k)_m×n×l。

作为本发明进一步优选方案，在进行图像置乱时，具体包括以下步骤：

第(1)步：读取待置乱图像的位面立方体，对于8位图像P₈，将 P₈.W＝(w_i,j,k)_m×n×8作为S_init，对于24位图像，将P₂₄.W＝(w_i,j,k)_m×n×24作为S_init，在S_init上选取特定区域作为S_maze；

第(2)步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG(x)，设定初始值RG.init＝seed和映射偏移量ll；

第(3)步：输出置乱后的位面立方体，对于8位图像，将(w′_i,j,k)_m×n×8写为置 乱后的图像，对于24位图像，将(w′_i,j,k)_m×n×24写为置乱后的图像。

作为本发明进一步优选方案，在进行图像置乱时，具体包括以下步骤：

第(1)步：读取待置乱图像的位面立方体，对于8位图像P₈，将P₈.W＝(w_i,j,k)_m×n×8作为S_init，对于24位图像，将P₂₄.W＝(w_i,j,k)_m×n×24作为S_init，在S_init上选取特定区 域作为S_maze；

第(2)步：选取作为迷宫的初始节点，选取随机数发生 器y＝RG₀(x),y＝RG₁(x)，设定初始值RG₀.init＝seed₀,RG₁.init＝seed₁和映射偏移量 ll；

第(3)步：输出置乱后的位面立方体，对于8位图像，将(w′_i,j,k)_m×n×8写为置 乱后的图像，对于24位图像，将(w′_i,j,k)_m×n×24写为置乱后的图像。

作为本发明进一步优选方案，在进行图像置乱时，具体包括以下步骤：

第(1)步：读取待置乱24位图像P₂₄的RGB立方体P₂₄.C＝(c_i,j,k)_m×n×3作为S_init， 在S_init上选取特定区域作为S_maze；

第(2)步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG(x)，设定初始值RG.init＝seed和映射偏移量ll；

第(3)步：输出置乱后的RGB立方体(c′_i,j,k)_m×n×3，将其写为置乱后的图像。

作为本发明进一步优选方案，在进行图像置乱时，具体包括以下步骤：

第(1)步：读取待置乱24位图像P₂₄的RGB立方体P₂₄.C＝(c_i,j,k)_m×n×3作为S_init， 在S_init上选取特定区域作为S_maze；

第(2)步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG₀(x),y＝RG₁(x)，设定初始值RG₀.init＝seed₀,RG₁.init＝seed₁和映射偏移量ll；

第(3)步：输出置乱后的RGB立方体(c′_i,j,k)_m×n×3，将其写为置乱后的图像。

作为本发明进一步优选方案，在进行图像置乱时，具体包括以下步骤：

第(1)步：读取待置乱24位图像P₂₄的RGB通道立方体和将其分别作为初始范围在 选取特定区域作为有效区域

第(2)步：选取作为迷宫的初始节点， 选取随机数发生器y＝RG^R(x),y＝RG^G(x),y＝RG^B(x)，设定初始值 RG^R.init＝seed^R,RG^G.init＝seed^G,RG^B.init＝seed^B和映射偏移量ll^R,ll^G,ll^B；

第(3)步：输出置乱后的R、G、B通道立方体和将其写为置乱后的图像。

作为本发明进一步优选方案，在进行图像置乱时，具体包括以下步骤：

第(1)步：读取待置乱24位图像P₂₄的RGB通道立方体和将其分别作为初始范围在 选取特定区域作为有效区域

第(2)步：选取$\forall s_{x_0,y_0,z_0}^R,s_{x_1,y_1,z_1}^R\in S_{\mathrm{maze}}^R,\forall s_{x_0,y_0,z_0}^G,s_{x_1,y_1,z_1}^G\in S_{\mathrm{maze}}^G,\forall s_{x_0,y_0,z_0}^B,s_{x_1,y_1,z_1}^B\in S_{\mathrm{maze}}^B$作为迷宫 的初始节点，选取随机数发生器 $y={\mathrm{RG}}_0^R\left(x\right),y={\mathrm{RG}}_1^R\left(x\right),y=R{G}_0^G\left(x\right),y={\mathrm{RG}}_1^G\left(x\right),y=R{G}_0^B\left(x\right),y={\mathrm{RG}}_1^B\left(x\right),$设定初始值 ${\mathrm{RG}}_0^R.\mathrm{init}={\mathrm{seed}}_0^R,{\mathrm{RG}}_1^R.\mathrm{init}={\mathrm{seed}}_1^R,{\mathrm{RG}}_0^G.\mathrm{init}={\mathrm{seed}}_0^G,{\mathrm{RG}}_1^G.\mathrm{init}={\mathrm{seed}}_1^G,$${\mathrm{RG}}_0^B.\mathrm{init}={\mathrm{seed}}_0^B,{\mathrm{RG}}_1^B.\mathrm{init}={\mathrm{seed}}_1^B$和映射偏移量ll^R,ll^G,ll^B；

第(3)步：输出置乱后的R、G、B通道立方体和将其写为置乱后的图像。

本发明同现有技术优点分析：

(1)传统的迷宫生成方法在人工智能和优化计算领域应用较广，一般用于 动态复杂场景的模拟和仿真，但在信息安全领域涉及较少，而传统的置乱方法 一般将置乱空间局限在特定的尺度上，用于图像规则区域置乱，例如正方形图 像和矩形图像以及仅适用于特定尺度图像的规则区域加密，方法不具有普适性， 在实施过程中存在使用限制。本发明则将传统的迷宫生成方法引入到信息安全 中的置乱处理方法中，在Growing Tree迷宫生成方法中添加了迷宫有效区域 S_maze约束限制，使其仅在事先选定的3D任意封闭连通区域S_maze上产生迷宫， 同时将Growing Tree迷宫节点更新顺序以节点更新序列A_update输出用于生成排 列，利用该排列构造所有节点之间的映射关系，从而将所有节点置乱。

在此基础上本发明还给出了结合具体节点更新序列和节点更新序列复合的 数字置乱方法。本发明所给出的置乱方法具有普适性和灵活性，在使用过程中 不存在使用限制，不仅可以用于置乱传统置乱方法的规则区域，例如正方形和 矩形区域，也可以用于任意选定的3D任意封闭连通的选择性区域。

(2)本发明所给出的置乱方法可单独使用，也可多次迭代，还可将不同方 法联合使用，也可和现有的信息隐藏、数字水印、秘密共享和加密策略相结合， 结合任意设定的随机数发生器对任意3D连通封闭区域数据提供不同安全级别 的多重保护，具备较高的实际应用价值。

(3)同时本发明所针对的对象也不仅仅是图像，可以用于任意封闭连通区 域数据的置乱和恢复。

附图说明

图1是本发明具体实施例：方法1一种基于3D Growing Tree迷宫的数字置 乱方法流程图；

图2是本发明具体实施例：方法2结合具体映射方法的数字置乱方法流程 图；

图3是本发明具体实施例：方法3结合另一种映射方法的数字置乱方法流 程图；

图4本发明实施例：测试图像(含24位真彩色人像照片和迷宫有效区域设 定图像包括五边形、六边形、五角星、心形、闪电形、空心云状图和人像前景 等单色图像，其中黑色为迷宫有效区域，所有图像分辨率均为80×60)；

图5是传统的Growing Tree方法生成80×60迷宫；

图6是本发明对传统的Growing Tree方法添加有效区域限制的Growing Tree 方法生成的迷宫(以图4中的人像前景区域为设定区域，3D迷宫的第3维设定 为2)；

图7本发明实施例：由图4五边形设定区域产生的排列按方法1中Growing  Tree法产生的前30个元素排列；

图8本发明实施例：以5×2×3迷宫为例验证方法2(原始矩阵、迷宫生成排 列、正映射、逆映射、置乱矩阵和恢复矩阵)；

图9本发明实施例：以5×2×3迷宫为例验证方法3(原始矩阵、迷宫生成排 列1、迷宫生成排列2、正映射、逆映射、置乱矩阵和恢复矩阵)；

图10本方法实施例：以图4测试例为基础对方法4的验证图样；

图11本方法实施例：以图4测试例为基础对方法5的验证图样；

图12本方法实施例：以图4测试例为基础对方法6的验证图样；

图13本方法实施例：以图4测试例为基础对方法7的验证图样；

图14本方法实施例：以图4测试例为基础对方法8的验证图样；

图15本方法实施例：以图4测试例为基础对方法9的验证图样。

具体实施方式

以下结合附图具体实施例对本发明方法进行详细描述：

Growing Tree生成策略是一种典型的迷宫生成策略，其基本思路是将已访问 的节点形成一个列表，不断从列表中取元素，将其邻近节点的未访问元素加入 列表，如果邻近的节点不存在未访问的元素，则将其从列表中删除，直至列表 为空。Growing Tree迷宫生成策略可根据所取元素的策略，例如最近添加，最先 添加和随机选择，产生不同纹理的迷宫。传统的Growing Tree迷宫是在m×n规 模网格上的任意节点出发，产生一条连接所有网络节点且具有复杂迂回通道的 迷宫。

经典Growing Tree迷宫生成方法在人工智能和优化计算领域应用较广，一 般用于动态复杂场景的模拟和仿真，但在信息安全领域涉及较少。

本发明预先对Growing Tree迷宫生成区域进行人为限定，则Growing Tree 生成迷宫不光可以应用于规则区域，例如正方形区域和矩形区域等，同时也可 应用于人为指定的任意区域，例如3D封闭连通区域，同时可按迷宫节点更新顺 序对迷宫限定区域的每个节点赋予一个唯一的编号，由此可产生一个排列，利 用该排列构造所有节点之间的映射关系，从而将所有节点置乱。

本发明一种基于3D Growing Tree迷宫的数字置乱方法(记为方法1)具体 步骤如下：

第1步：设定迷宫初始范围S_init＝()_m×n×l和迷宫有效区域S_maze＝(s_i,j,k)_m×n×l，对 于i＝0,…,m-1,j＝0,…,n-1,k＝0,…,l-1，若则标记s_i,j,k＝-1，反 之则标记s_i,j,k＝0表示该节点未访问，若s_i,j,k>0表示该节点已访问；

第2步：记s_i,j,k.0,s_i,j,k.1,s_i,j,k.2,s_i,j,k.3,s_i,j,k.4,s_i,j,k.5依次为节点s_i,j,k的下方、 右方、上方、左方、底部和顶部墙，初始化s_i,j,k.d＝-1,d＝0,1,2,3,4,5，-1表示为 有墙，0表示无墙；

第3步：选择随机数发生器y＝RG(x)，设定初始值RG.init＝seed，初始化 迷宫节点列表A_maze＝Φ，节点更新序列A_update＝Φ，按随机数发生器随机产生2个 概率P_recent,P_oldest∈[0,1)；

第4步：选取x＝x₀,y＝y₀,z＝z₀，将s_x,y,z分别加到A_maze和A_update， 即A_maze＝A_maze.add(s_x,y,z)A_update＝A_update.add(s_x,y,z)；

第5步：若A_maze≠Φ，则循环执行第6步～第8步

第6步：产生1个随机数P∈[0,1)，若P∈[0,P_recent]，则取A_maze尾部元素作 为当前节点s_x,y,z，反之若P∈[P_recent,P_recent+P_oldest]，则取A_maze头部元素作为当前节 点s_x,y,z，反之则从A_maze中随机取一个元素作为当前节点s_x,y,z， s_x,y,z＝A_maze.at(index),index＝random(A_maze.length)；

第7步：若s_x,y,z周围的邻近节点中s_x+1,y,z,s_x,y+1,z,s_x-1,y,z,s_x,y-1,z,s_x,y,z-1,s_x,y,z+1存在 未访问的有效节点s_{x′,y′,z′}∈S_maze，则将s_{x′,y′,z′}加入到A_maze，即A_maze＝A_maze.add(s_{x′,y′,z′})， A_update＝A_update.add(s_{x′,y′,z′})；

第8步：若s_x,y,z周围的邻近节点中s_x+1,y,z,s_x,y+1,z,s_x-1,y,z,s_x,y-1,z,s_x,y,z-1,s_x,y,z+1不存 在未访问的有效节点s_{x′,y′,z′}∈S_maze，则删除A_maze索引位置为Index位置的元素， 即A_maze.delete(index)；

第9步：利用A_update构造S_maze＝(s_i,j,k)_m×n×l范围内的所有节点间的映射关系， 从而将S_maze＝(s_i,j,k)_m×n×l范围内的所有节点置乱。

本发明方法1中的A_update(0)为序列中的第1个元素，为迷宫的初始节点， A_update.length等价为迷宫有效区域内的所有节点数量。对于同样的S_maze，输入不 同的选定不同的y＝RG(x)和RG.init，将产生不同的A_update。

结合上述方法和不同映射方法得到用于任意封闭连通区域的置乱方法，如 方法2和方法3。

方法2基于3D Growing Tree迷宫节点更新序列的置乱方法，包括以下步 骤：

第1步：设定S_init＝()_m×n×l和S_maze＝(s_i,j,k)_m×n×l，对于 i＝0,…,m-1,j＝0,…,n-1,k＝0,…,l-1，若s_i,j,k∈S_maze，则初始s_i,j,k＝0，反之 则标记s_i,j,k＝-1，将S_init复制为T＝(t_i,j,k)_m×n×l；

第2步：随机选取作为迷宫的初始节点，选取随机数发生器 y＝RG(x)，设定初始值RG.init＝seed按方法1生成A_update；

第3步：输入整数作为映射偏移量ll，llmodA_update.length≠0，将其按式(1) 规范到(-A_update.length,A_update.length)范围内的整数，按式(2)计算index；

ll＝llmodA_update.length(1)

$\mathrm{index}=\left(\begin{array}{cc}(\mathrm{ll}+A_{\mathrm{update}}.\mathrm{length})\mathrm{mod}{A}_{\mathrm{update}}.\mathrm{length}& \mathrm{ll}<0\\ \mathrm{ll}& \mathrm{ll}>0\end{array}\right)---\left(2\right)$

第4步：对于按式(3)将t_x,y,z＝s_i,j,k(若将t_x,y,z＝s_i,j,k修改为s_i,j,k＝t_x,y,z，则对应为方法2的逆变换)；

(i,j,k)＝A_update(ii),ii＝0,…,A_update.length-1

(x,y,z)＝A_update(kk),kk＝0,…,A_update.length-1   (3)

kk＝(ii+index)modA_update.length

第5步：输出T＝(t_i,j,k)_m×n×l。

方法2第3步若llmodA_update.length＝0，则对应为s_i,j,k＝t_i,j,k,为自身到自身的映 射，不能用于置乱。

方法3基于3D Growing Tree迷宫节点更新序列复合的置乱方法，包括以下 步骤：

第1步：设定S_init＝()_m×n×l和S_maze＝(s_i,j,k)_m×n×l，对于 i＝0,…,m-1,j＝0,…,n-1,k＝0,…,l-1，若s_i,j,k∈S_maze，则初始s_i,j,k＝0，反之 则标记s_i,j,k＝-1，将S_init复制为T＝(t_i,j,k)_m×n×l；

第2步：随机选取作为迷宫的初始节点，选取随机数发生 器y＝RG₀(x)，y＝RG₁(x)，设定随机初始值RG₀.init＝seed₀，RG₁.init＝seed₁按方法1 分别生成迷宫节点更新序列

第3步：输入任意整数作为映射偏移量ll，并将其按式(4)规范到 范围内的整数，按式(5)计算index；

$\mathrm{index}=\left(\begin{array}{cc}(\mathrm{ll}+A_{\mathrm{update}}^0.\mathrm{length})\mathrm{mod}{A}_{\mathrm{update}}^0.\mathrm{length}& \mathrm{ll}<0\\ \mathrm{ll}& \mathrm{ll}>0\end{array}\right)---\left(5\right)$

第4步：对于按式(6)将t_x,y,z＝s_i,j,k(若将t_x,y,z＝s_i,j,k修改为s_i,j,k＝t_x,y,z，则对应为方法3的逆变换)；

$\left(\begin{array}{c}(i,j,k)=A_{\mathrm{update}}^0\left(\mathrm{ii}\right),\mathrm{ii}=0,...,A_{\mathrm{update}}^0.\mathrm{length}-1\\ (x,y,z)=A_{\mathrm{update}}^1\left(\mathrm{kk}\right),\mathrm{kk}=0,...,A_{\mathrm{update}}^1.\mathrm{length}-1\\ \mathrm{kk}=(\mathrm{ii}+\mathrm{index})\mathrm{mod}{A}_{\mathrm{update}}^1.\mathrm{length}\end{array}\right)---\left(6\right)$

第5步：输出T＝(t_i,j,k)_m×n×l。

若方法3第2步中输入相同的迷宫初始节点，选取同1个随机发生器，设 定相同的初始值，则方法3退化为方法2。

传统的置乱研究，针对的对象一般为数字图像。数字图像是自然图像的离 散采样化。记图像P的像素矩阵为P＝(p_i,j)_m×n，记24位图像P₂₄的R、G、B 通道矩阵分别为P₂₄.R＝(r_i,j)_m×n、P₂₄.G＝(g_i,j)_m×n和P₂₄.B＝(b_i,j)_m×n；记8位和24 位图像P₈,P₂₄的位面立方体分别为P₈.W＝(w_i,j,k)_m×n×8和P₂₄.W＝(w_i,j,k)_m×n×24；对于8 位图像P₈，其对应的位面可依次记为kk＝0,1,…,7；对于24位图像 P₂₄，其对应的位面可依次记为kk＝0,1,…,23，其中每个位面等价为 单色图像的像素矩阵；记24位图像P₂₄对应的RGB立方体为P₂₄.C＝(c_i,j,k)_m×n×3； 记24位图像P₂₄对应的RGB通道立方体分别为和$P_{24}.C_B={\left(c_{i,j,k}^B\right)}_{m\times n\times 8}.$

本发明结合方法2、方法3基于3D Growing Tree迷宫更新序列和复合更新 序列的数字置乱方法，提出6种图像置乱方法，如方法4～方法9所示：

方法4基于3D Growing Tree迷宫更新序列的图像位面立方体置乱方法：

第1步：读取待置乱图像的位面立方体，对于8位图像P₈，将P₈.W＝(w_i,j,k)_m×n×8作为S_init，对于24位图像，将P₂₄.W＝(w_i,j,k)_m×n×24作为S_init，在S_init上选取特定区 域作为S_maze；

第2步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG(x)，设定初始值RG.init＝seed和映射偏移量ll；

第3步：利用方法2输出置乱后的位面立方体，对于8位图像，将(w′_i,j,k)_m×n×8写为置乱后的图像，对于24位图像，将(w′_i,j,k)_m×n×24写为置乱后的图像(若将步 骤3方法2修改为方法2逆变换，则对应为方法4的逆变换)。

方法5基于3D Growing Tree迷宫更新序列复合的图像位面立方体置乱方 法：

第1步：读取待置乱图像的位面立方体，对于8位图像P₈，将 P₈.W＝(w_i,j,k)_m×n×8作为S_init，对于24位图像，将P₂₄.W＝(w_i,j,k)_m×n×24作为S_init，在S_init 上选取特定区域作为S_maze；

第2步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG₀(x),y＝RG₁(x)，设定初始值RG₀.init＝seed₀,RG₁.init＝seed₁和映射偏移量ll；

第3步：利用方法3输出置乱后的位面立方体，对于8位图像，将(w′_i,j,k)_m×n×8写为置乱后的图像，对于24位图像，将(w′_i,j,k)_m×n×24写为置乱后的图像(若将步 骤3方法3修改为方法3逆变换，则对应为方法5的逆变换)。

方法6基于3D Growing Tree迷宫更新序列的图像RGB立方体置乱方法：

第1步：读取待置乱24位图像P₂₄的RGB立方体P₂₄.C＝(c_i,j,k)_m×n×3作为S_init， 在S_init上选取特定区域作为S_maze；

第2步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG(x)，设定初始值RG.init＝seed和映射偏移量ll；

第3步：利用方法2输出置乱后的RGB立方体(c′_i,j,k)_m×n×3，将其写为置乱后 的图像(若将步骤3方法2修改为方法2逆变换，则对应为方法6的逆变换)。

方法7基于3D Growing Tree迷宫更新序列复合的图像RGB立方体置乱方 法，包括以下步骤：

第1步：读取待置乱24位图像P₂₄的RGB立方体P₂₄.C＝(c_i,j,k)_m×n×3作为S_init， 在S_init上选取特定区域作为S_maze；

第2步：选取作为迷宫的初始节点，选取随机数发生器 y＝RG₀(x),y＝RG₁(x)，设定初始值RG₀.init＝seed₀,RG₁.init＝seed₁和映射偏移量ll；

第3步：利用方法3输出置乱后的RGB立方体(c′_i,j,k)_m×n×3，将其写为置乱后 的图像(若将步骤3方法3修改为方法3逆变换，则对应为方法7的逆变换)。

方法8基于3D Growing Tree迷宫更新序列的图像R、G、B通道立方体置 乱方法：

第1步：读取待置乱24位图像P₂₄的RGB通道立方体和将其分别作为在选取 特定区域作为

第2步：选取作为迷宫的初始节点，选 取随机数发生器y＝RG^R(x),y＝RG^G(x),y＝RG^B(x)，设定初始值 RG^R.init＝seed^R,RG^G.init＝seed^G,RG^B.init＝seed^B和映射偏移量ll^R,ll^G,ll^B；

第3步：利用方法2输出置乱后的R、G、B通道立方体和将其写为置乱后的图像(若将步骤3方法2修改 为方法2逆变换，则对应为方法8的逆变换)。

方法9基于3D Growing Tree迷宫更新序列复合的图像R、G、B通道立方 体置乱方法：

第1步：读取待置乱24位图像P₂₄的RGB通道立方体和将其分别作为在选取 特定区域作为

第2步：选取$\forall s_{x_0,y_0,z_0}^R,s_{x_1,y_1,z_1}^R\in S_{\mathrm{maze}}^R,\forall s_{x_0,y_0,z_0}^G,s_{x_1,y_1,z_1}^G\in S_{\mathrm{maze}}^G,\forall s_{x_0,y_0,z_0}^B,s_{x_1,y_1,z_1}^B\in S_{\mathrm{maze}}^B$作为迷宫的 初始节点，选取随机数发生器 $y={\mathrm{RG}}_0^R\left(x\right),y={\mathrm{RG}}_1^R\left(x\right),y=R{G}_0^G\left(x\right),y={\mathrm{RG}}_1^G\left(x\right),y=R{G}_0^B\left(x\right),y={\mathrm{RG}}_1^B\left(x\right),$设定初始值 ${\mathrm{RG}}_0^R.\mathrm{init}={\mathrm{seed}}_0^R,{\mathrm{RG}}_1^R.\mathrm{init}={\mathrm{seed}}_1^R,{\mathrm{RG}}_0^G.\mathrm{init}={\mathrm{seed}}_0^G,{\mathrm{RG}}_1^G.\mathrm{init}={\mathrm{seed}}_1^G,$${\mathrm{RG}}_0^B.\mathrm{init}={\mathrm{seed}}_0^B,{\mathrm{RG}}_1^B.\mathrm{init}={\mathrm{seed}}_1^B$和映射偏移量ll^R,ll^G,ll^B；

第3步：利用方法3输出置乱后的R、G、B通道立方体和将其写为置乱后的图像(若将步骤3方法3修改 为方法3逆变换，则对应为方法9的逆变换)。

以下结合附图具体实施例对本发明方法进行详细说明：

以Delphi XE5为案例实施环境，结合附图对本发明实施方式进行详细说明， 但不局限于本实施案例，其中图1是方法1流程图，图2是方法2流程图，图3 是方法3流程图。

参考图1的过程如下：

第1步：假定迷宫的初始范围设置为S_init＝()_3×3×2，迷宫的有效区域 S_maze＝(s_i,j,k)_3×3×2设置为S_init左上角2×2×2网格区域内，则：

$S_{\mathrm{maze}(k=0)}=\left(\begin{array}{ccc}0& 0& -1\\ 0& 0& -1\\ -1& -1& -1\end{array}\right),S_{\mathrm{maze}(k=1)}=\left(\begin{array}{ccc}0& 0& -1\\ 0& 0& -1\\ -1& -1& -1\end{array}\right);$

第2步：对于i＝0,…,2,j＝0,…,2,k＝0,1，初始化 s_i,j,k.d＝-1,d＝0,1,2,3,4,5且由于s_0,0,0,s_0,1,0,s_1,0,0,s_1,1,0,s_0,0,1,s_0,1,1,s_1,0,1,s_1,1,1∈S_maze，所以 (i,j,k)＝{(0,0,0),(0,1,0),(1,0,0),(1,1,0),(0,0,1),(0,1,1),(1,0,1),(1,1,1)}；

第3步：选择y＝RG(x)，设定初始值RG.init＝seed，这里以Delphi XE5线 性同余发生器为例，线性同余发生器的随机初始值为randseed，可将其设置为不 同的整数，不同的随机数发生器将导致生成不同的伪随机数，从而产生不同的 迷宫，对应不同的迷宫排列，按随机数发生器随机产生2个概率P_recent,P_oldest∈[0,1)， 假设P_recent＝0.2,P_oldest＝0.4；

第4步：选取x＝x₀,y＝y₀,z＝z₀，这里以s_0,0,0为迷宫初始节点， 则x＝0,y＝0,z＝0，将s_x,y,z加入A_update和A_maze，则A_update＝<s_0,0,0>，A_maze＝<s_0,0,0>；

第5步：若A_maze≠Φ，则循环执行第6步～第8步；

第6步：产生1个随机数P∈[0,1)，若P∈[0,P_recent]，则取A_maze尾部元素作 为当前节点s_x,y,z，反之若P∈[P_recent,P_recent+P_oldest]，则取A_maze头部元素作为当前节 点s_x,y,z，反之则从A_maze中随机取一个元素作为当前节点s_x,y,z， s_x,y,z＝A_maze(index),index＝random(A_maze.length)，假设A_maze＝<s_0,0,0,s_1,0,0,s_0,1,0>，若产生 的P＝0.1，则(P＝0.1)≤(P_recent＝0.2)，故取A_maze尾部元素s_0,1,0作为s_x,y,z，若产生的 P＝0.3，则(P_recent＝0.2)≤(P＝0.3)≤(P_recent+P_oldest＝0.6)，故取A_maze头部元素s_0,0,0作为 s_x,y,z，此外则从A_maze＝<s_0,0,0,s_1,0,0,s_0,1,0>随机取一个元素作为s_x,y,z；

第7步：若s_x,y,z周围的邻近节点中s_x+1,y,z,s_x,y+1,z,s_x-1,y,z,s_x,y-1,z,s_x,y,z-1,s_x,y,z+1存在 未访问的有效节点s_{x′,y′,z′}∈S_maze，假设s_x,y＝s_0,0,0且s_0,0,0周围存在未访问的节点s_1,0,0和s_0,1，0且A_update＝<s_0,0,0>，A_maze＝<s_0,0,0>，则经过A_maze＝A_maze.add(s_{x′,y′,z′})， A_update＝A_update.add(s_{x′,y′,z′})后，A_update＝<s_0,0,0,s_1,0,0,s_0,1,0>A_maze＝<s_0,0,0,s_1,0,0,s_0,1,0>；

第8步：若随机选择的节点s_x,y,z周围的邻近节点中 s_x+1,y,z,s_x,y+1,z,s_x-1,y,z,s_x,y-1,z,s_x,y,z-1,s_x,y,z+1不存在未访问的有效节点s_{x′,y′,z′}∈S_maze，则将 A_maze对应位置的节点删除，

不断地执行第6步～第8步，直至第5步不被满足，此时可由A_update给出所 有节点的排列，可在此基础上进一步构造节点之间的映射关系，从而用于置乱。 由于传统的Growing Tree迷宫生成方法往往不限制迷宫生成区域，产生的迷宫 往往是规则区域迷宫如图5所示；图6是对传统的Growing Tree迷宫生成方法 以图4的人像前景为设定区域产生的3D连通封闭区域迷宫，第3维l取2(由于 图像本身是2D图像，因此在本发明中没有用复杂的3D验证实例，仅简单将第 3维l设置为2，其中灰色方块表明顶部或底部只有一面墙，黑色方块表明底部 和顶部都有墙，白色表明无墙，黑色线段表明有墙)；图7则是以图4五边形设 定区域(l取8)按方法1产生的排列对应的前30个元素。

参考图2的过程如下：

第1步：假设将S_init设定为图8a对应的5×2×3矩阵(第0行为x坐标，第 1行为y坐标，第2行为z坐标，第3行为矩阵元素值)，将S_maze设置为S_init整个 区域，则S_maze＝(0)_5×2×3，将S_init复制为T＝(t_i,j,k)_5×2×3，则T＝(t_i,j,k)_5×2×3对应为图8a矩 阵；

第2步：假定按方法1生成的A_update如图8b所示，图8b第0行是x坐标， 第1行是y坐标，第2行是z坐标，第3行是A_update中的节点序号；

第3步：假定输入ll＝3，则按式(1)和式(2)得ll＝3 mod 30＝3，由于ll>0，故 index＝3；

第4步：由A_update和index＝3，则式(3)构造的映射规则可描述为图8c，前3 行对应为(x,y,z)，后3行对应为(i,j,k)，与之等价的逆映射可描述为图8d，前3 行对应为(i,j,k)，后3行对应为(x,y,z)，则按式(3)可将图8a置乱为图8e，则按式 (3)对应的逆映射可将图8e置乱为图8f，图8a和图8f等价，即置乱后的矩阵可 完整恢复；

第5步：将映射后的结果T＝(t_i,j,k)_5×2×3输出。

参考图3的过程如下：

第1步：假设将S_init设定为图9a对应的5×2×3矩阵，将S_maze设置为S_init整 个区域，则S_maze＝(0)_5×2×3，将S_init复制为T＝(t_i,j,k)_5×2×3，则T＝(t_i,j,k)_5×2×3对应为图9a 矩阵；

第2步：假定按方法1生成的如图9b和9c所示，图9b和9c第 0行是x坐标，第1行是y坐标，第2行是z坐标，第3行分别是中 的节点序号；

第3步：假定输入ll＝3，则按式(4)和式(5)得ll＝3 mod 30＝3，由于ll>0，故 index＝3；

第4步：由和index＝3，则式(6)构造的映射规则可描述为图9d， 前3行对应为(x,y,z)，后3行对应为(i,j,k)，与之等价的逆映射可描述为图9e，前 3行对应为(i,j,k)，后3行对应为(x,y,z)，则按式(6)可将图9a置乱为图9f，则按 式(6)对应的逆映射可将图9f置乱为图9g，图9a和图9g等价，即置乱后的矩阵 可完整恢复；

第5步：将映射后的结果T＝(t_i,j,k)_5×2×3输出。

方法4是将待置乱图像的位面立方体作为S_init，在S_init上选取特定区域作为 S_maze，在此基础上应用方法2置乱的结果，图10a～10g是以图4b～4h为测试例 对方法4验证的结果，图10h对应的是恢复结果。

方法5是将待置乱图像的位面立方体作为S_init，在S_init上选取特定区域作为 S_maze，在此基础上应用方法3置乱的结果，图11a～11g是以图4b～4h为测试例 对方法5验证的结果，图11h对应的是恢复结果。

方法6是将待置乱24位图像P₂₄的RGB立方体P₂₄.C＝(c_i,j,k)_m×n×3作为S_init，在 S_init上选取特定区域作为S_maze，在此基础上应用方法2置乱的结果，图12a～12g 是以图4b～4h为测试例对方法6验证的结果，图12h对应的是恢复结果。

方法7是将待置乱24位图像P₂₄的RGB立方体P₂₄.C＝(c_i,j,k)_m×n×3作为S_init，在 S_init上选取特定区域作为S_maze，在此基础上应用方法3置乱的结果，图13a～13g 是以图4b～4h为测试例对方法7验证的结果，图13h对应的是恢复结果。

方法8是将待置乱24位图像P₂₄的RGB通道立方体和分别作为在选取特定 区域作为在此基础上应用方法2置乱的结果，图14a～14g是以图 4b～4h为测试例对方法8验证的结果，图14h对应的是恢复结果。

方法9是将待置乱24位图像P₂₄的RGB通道立方体和分别作为在选取特定 区域作为在此基础上应用方法3置乱的结果，图15a～15g是以图 4b～4h为测试例对方法9验证的结果，图15h对应的是恢复结果。