下载文档原格式
第11卷 第3期2006年3月中国图象图形学报Journa l o f I m age and G raphicsV o.l 11,N o .3M ar .,2006收稿日期:2004-05-19;改回日期:2005-05-16第一作者简介:范延军(1977~ ),男。
2004年获中国计量科学研究院硕士学位,现为中国计量学院计算机科学与技术系教师。
主要研究方向为计算机图形学、数字水印、图像置乱、分形几何等。
E-m ai:l fanyan j un2002@yahoo .co 一种基于混合混沌序列的图像置乱加密算法范延军 孙燮华 阎晓东 郑林涛(中国计量学院计算机科学与技术系,杭州 310034)摘 要 由Log istic 映射产生的混沌序列常被用来置乱加密数字图像,但迄今为止,在国内外有关文献中,均未提到由Log isti c 映射产生的混沌序列中存在/平凡密钥0和/拟平凡密钥0的现象。
如果用/平凡密钥0和/拟平凡密钥0作为L og i stic 映射的初始值,则将无法产生可用于图像置乱的混沌序列,并且在L og i stic 映射中存在无穷多个/平凡密钥0和/拟平凡密钥0,这可能会导致对图像置乱加密无效,这是值得注意的问题.针对该问题,在对由Log istic 映射产生的混沌序列中存在的/平凡密钥0和/拟平凡密钥0进行研究的基础上,提出了一种新的基于混合混沌序列的图像置乱加密算法,从而彻底解决了/平凡密钥0和/拟平凡密钥0对图像置乱加密无效的问题。
关键词 混沌 混合混沌序列 排列变换 加密 小波变换 平凡密钥 拟平凡密钥中图法分类号:TP309 文献标识码:A 文章编号:1006-8961(2006)03-0387-07An I mage -scra mb li ng A lgorith m Based on M i xed Chaoti c SequencesF AN Yan-j u n ,SUN X ie -hua ,YAN X iao -dong ,Z HENG L i n -tao(D e part m ent o f C o mputer Sc i ence and T e chnolo gy,Ch i na Instit u te of M etrology ,H angzh ou 310034)Abstrac t T he Log istic -M ap chao ti c sequence is o ften used to scramb l e and encrypt t he dig ital i m ag es .In t he f o r m erpapers ,the i nv ali d -keys and t he quasi i nv ali d -keys ex isting in t he Log istic -M ap hav e not yet been d i scussed .If using the inva lid -keys or t he quasi inva lid -keys as t he i n iti a l va l ue o f the L og i stic -M ap ,w e can .t get the chao ti c sequence t o scra mb le the d i g ita l i m ages .Furthe r mo re ,the re are infi nite i nva li d -keys and quasi inva lid -keys i n the L og i stic -M ap .So w e should take t he proble m s ser i ousl y .In this paper ,t he i nva li d -keys and the quas i i nva li d -keys ex i sti ng i n the L og isti c -M ap chao ti c sequence a re deep l y d i scussed .T hen ,an i m ag e -scra m bli ng a l gor it hm based on m i xed chaotic sequences i s proposed .U si ng t h is a l gor ith m,t he i nva li d ity of t he i nva li d -keys and the quas i i nva li d -key s is avo i ded thorough l y .K eywords chaos ,m i x ed chaotic sequences ,scra m bli ng transfor m ati on ,encrypti on ,w ave let ,i nva lid -key ,quasi inva lid -key1 引 言随着对多媒体信息安全重视程度的提高,图像加密技术的应用迫在眉睫,急需加强发展。
哈密顿圈算法案例
那咱就来说说哈密顿圈算法的一个简单案例吧。
想象你有一个小城堡，城堡里有好几个房间，每个房间就像是图里的一个节点。
这些房间之间有些是有门连通着的，这就相当于图里的边啦。
比如说这个城堡有5个房间，分别是A、B、C、D、E。
房间A和B之间有门，B和C、D之间有门，C和D、E之间有门，D和E之间也有门，A和E之间也有个秘密通道（也就是一条边啦）。
那哈密顿圈算法就像是一个特别聪明的小探险家在找路。
这个探险家要从一个房间出发，每个房间都只能经过一次，最后还能回到出发的房间。
我们先从A房间开始，探险家想啊，我可以去B，然后从B到C，接着C到D，D 到E，这时候发现E还能通过秘密通道回到A，哇，这样就找到了一个哈密顿圈，就是A B C D E A。
要是有更多复杂的连接情况呢，就像是一个超级大的迷宫城堡，有几十甚至上百个房间，那这个算法就更厉害了。
它就像个经验超级丰富的探险家，会仔细地去尝试各种可能的路径。
比如说它到了一个岔路口（一个节点有好几个连接的边），它得想清楚走哪条路才有机会走完所有房间再回来。
不过有时候也会碰到走不通的情况。
就像有几个房间布局特别奇怪，这个探险家试了好多路，发现按照规则走，怎么都没法回到起点。
那这个图可能就不存在哈密顿圈咯。
这就是哈密顿圈算法在这种简单城堡（图）例子里的大概情况啦。
实验一图像置乱与加密实验一、实验名称：图像置乱与加密实验二、实验目的1．了解图像置乱、加密的基本概念及一些实现算法2．掌握MA TLAB实现图像置乱和加密的算法3．掌握二值图象置乱算法、灰度图象置乱的Arnold变换算法三、实验内容所谓“置乱”，就是将图像的信息次序打乱，将a像素移动到b像素的位置上，b像素移动到c像素的位置上……使其变换成杂乱无章难以辨认的图像。
置乱实际上就是图像的加密，与加密保证安全性不同的是，将置乱的图像作为秘密信息再进行隐藏，可以很大限度地提高隐蔽载体的鲁棒性，所以图像置乱是信息隐藏中常用的一项技术。
1．二值图像置乱技术二值图像矩阵的像素值都是由0、1组成的，所以可以生成一个随机的二值图像，然后再与原图像进行异或即可实现原二值图像的置乱。
在提取恢复原图像时，随机二值图像即成为密钥，可以对置乱后的图像和随机图像进行异或则得到原始的二值图像。
2．二值图像置乱算法代码clear;close all;I=imread('text.png');[r,c]=size(I);R=rand(r,c); %生成(0,1)之间的随机矩阵J=round(R); %生成随机二值图像X=xor(I,J);Y=xor(X,J);figure;subplot(221);imshow(I);title('原二值图像');subplot(222);imshow(J);title('随机生成的二值图像');subplot(223);imshow(X);title('置乱后图像');subplot(224);imshow(Y);title('提取的原图像');原二值图像随机生成的二值图像置乱后图像提取的原图像3．Arnold 置乱技术Arnold 变换是俄国数学家Vladimir I Arnold 提出的一种变换，一幅N ×N 的数字图像的二维Arnold 变换定义为：''11(mod )12x x N y y ⎡⎤⎡⎤⎡⎤=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦ 其中x ，y ∈{0，1，2，…，N-1}表示变换前像素的位置，'x ，'y 表示变换之后的像素位置，mod 为模运算。
求马步图Hamilton圈的最优算法
柏森;杨晓帆
【期刊名称】《计算机工程与科学》
【年(卷),期】2000(022)002
【摘要】本文对骑士巡游问题进行了研究,提出了求棋盘马步图的Hamilton圈的"分治-回溯-合并"算法,其时间复杂度是O(n2).分析表明该算法是求棋盘马步图一条Hamilton圈的最优算法,对VLSI的布线问题具有一定的应用价值.
【总页数】4页(P8-11)
【作者】柏森;杨晓帆
【作者单位】重庆通信学院二系;重庆大学计算机研究所
【正文语种】中文
【中图分类】O157.6;TP302
【相关文献】
1.闭包是完全图的求Hamilton圈的新算法 [J], 彭丰斌;殷志祥
2.求有向图的所有Hamilton回路的新方法 [J], 牟廉明
3.利用Hopfield网络求Hamilton圈的算法 [J], 姜国均
4.3—正则3—连通无爪平面图的Hamilton圈问题和Hamilton路问题的NP—完全性 [J], 原晋江
5.关于Hamilton图的新的圈结构定理 [J], 李静云;任韩
因版权原因，仅展示原文概要，查看原文内容请购买。
马步遍历问题与骑士巡游问题的回溯算法【摘要】马步遍历问题与骑士巡游（knight's tour）问题是指在有8 8方格的国际象棋棋盘上进行奇异的骑士“L型”（L-shaped）移动的问题。
而骑士巡游问题实际是带有约束条件的马步遍历问题，因此在用程序求解的时候可以一并求解。
本文给出求解这一问题的回溯算法之C++语言程序。
论文关键词：骑士巡游,回溯算法,C++语言一般地说，我们用如下方法表示一个解：即把数字0，1， (63)入棋盘中的方格来表示到达这些方格的顺序。
解决骑士巡游问题更具创意的方法之一是由J. C. Warnsdorff在1823年提出的。
其规则是：骑士总是移向具有最少出口且没有到达过的方格之一。
由于骑士巡游问题实际是带有约束条件的马步遍历问题，因此在用程序求解的时候可以一起求解。
程序算法依然是回溯法，和皇后问题有相似之处。
马步遍历和骑士巡游问题的复杂度较高，求出一个解相对容易，但要求出所有的解是要花一定时间的。
一、回溯算法的实现1．为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j。
i 和j的取值范围是从１到SIZE。
当某个骑士占了位置(i，j)时，其在这个位置上可以向8个方向以“L型”移动，它们分别是：方向1：i+2，j+1；方向2：i+1，j+2；方向3：i-1，j+2；方向4：i-2，j+1；方向5：i-2，j-1；方向6：i-1，j-2；方向7：i+1，j+2；方向8：i+2，j-1。
2．棋盘以二维数组表示，其下标最大值8，将骑士的每一步按1，2，3 … 64填入数组相应单元。
其过程如下：………for(int i=0;i<8;i++)for(int j=0;j<8;j++)trajKT[i][j]=0;[作者简介] 王力强（1965-），江苏省常州市武进区人，陕西省城市经济学校财务科长，工程师。
………for(int e=0; e<=curPointSub; e++){trajKT[moveTraj[e].Location.x_pos][moveTraj[e].Location.y_pos] = e+1; }for(i=0;i<8;i++){for(int j=0;j<8;j++)cout<。
含空洞的马步型哈密顿圈探索杨克昌;刘志辉【摘要】通过搜索某些特殊的较小马步遍历,将其按照一元旋转与二元支撑两种组合模型构建成含空洞的马步型哈密顿圈,拓广了哈密顿圈图论课题的研究范围.【期刊名称】《湖南理工学院学报（自然科学版）》【年(卷),期】2011(024)001【总页数】5页(P12-16)【关键词】马步哈密顿圈;空洞;组合;递归;回溯【作者】杨克昌;刘志辉【作者单位】湖南理工学院计算机学院,湖南岳阳,414006;湖南电视台,长沙410000【正文语种】中文【中图分类】TP311.1;O157马步遍历与马步型哈密顿圈是一个集趣味性与学术性于一身的组合图论问题.在给定的方格棋盘中,马从棋盘的某一格出发,按马走“日”的规则经过棋盘中的每一个方格恰一次,该问题称为马步遍历问题,经过棋盘的每一个方格恰一次的线路称为马步遍历路径.马步遍历中若终点能与始点相衔接,即遍历路径的终点与始点也能形成一个“日”形关系,该遍历路径为一马步封闭圈,称为骑士巡游圈,或称马步型哈密顿圈,以下简称哈密顿圈.本文探讨含空洞的哈密顿圈,即探索在方格棋盘中含有一个马步不能踏入的空洞区域的哈密顿圈.这显然是一个比寻求一般意义上的马步遍历或哈密顿圈更具挑战性的课题.如果棋盘中的空洞只是某一单个空格,只需在搜索哈密顿圈的程序中加入“障碍空格”的条件限制即可.当棋盘中的空洞为一片空格区域时,因为此时棋盘参数必然比较大,同时空洞限制比较复杂,应用常规回溯或递归设计来探索很难切入.本文给出两个组合模型实施构建,即通过搜索棋盘参数较小的始点与终点满足某些特殊要求的马步遍历,用这些遍历按给定的组合模型构建成含空洞的哈密顿圈.一元旋转组合模型,即只一个特殊的马步遍历通过旋转组合成含空洞的哈密顿圈.设一元旋转组合模型的组合元素为n行m列的遍历A,按如图1所示的旋转模式实施组合:遍历A作为基础横放在棋盘下部,棋盘左边模块为组合元素A逆时针旋转270°后列倒置而成,右边的模块为组合元素A逆时针旋转90°后列倒置而成,横放棋盘上部的为A遍历旋转180°所得.按如图1所示的一元旋转组合模式,遍历A的始点与终点定为(1,1)与(2,m−1),注意到终点(2,m−1)既可与下一个同向遍历的始点(1,1)相衔接,也可以与逆时针旋转90°后列倒置遍历始点(1,1)相衔接,因而组合可以进行横竖两个方向的任意扩展.设棋盘的上下部各设置wh个遍历,左右部各设置wv个遍历,则所得含空洞的哈密顿圈共走2(wv+wh)mn步,棋盘为(2n+wvm)×whm,中央所含空洞为wvm× (whm-2n).注意到whm≤2n时组合时无空洞,而当n＜ 3时无遍历,显然要求whm＞2n≥6.应用回溯设计探索在nm广义棋盘中指定始点为(1,1)、终点为(2,m−1)的马步遍历. 设置数组x(i),y(i)记录遍历中第i步的行列位置,二维数组d(u,v)记录棋盘中位置(u,v)即第u行第v列所在格的步数值.例如第 9步走在棋盘的(3,2)格,则x(9)= 3,y(9)= 2;d(3,2)= 9.若d(i,j)= 0,表示棋盘中的 (i,j)格为空,可以走位.注意到马走“日”形最多可走8个方向,图2所示当马处在(x,y)时可选的8个方向. 设置控制马步规则的数组a(k)、b(k),若马的当前位置为(x,y),马步可跳的8个位置为(x+a(k),y+b(k)),k= 1,2,… ,8.其中在回溯过程中,需知第i步到第i+ 1步原已选取到哪一个方向,设置t(i)记录第i步到第i+1步已选取的方向数,回溯时只要从t(i)+1～8选取方向即可.回溯从i= 1开始进入条件循环,条件循环的条件为i＞0.当i＞0时还未完成回溯,可试探走马.设置k(t(i)+1～8)循环依次选取方向,并求出此方向的走马位置:u=x(i)+a(k),v=y(i)+b(k).判断:若1 ≤u≤n, 1≤v≤m,d(u,v)= 0,即所选位置在棋盘中且该位为空,可走马步d(u,v)=i+ 1;同时记录下此时的方向t(i)=k,q=1标志此步走马成功,退出选方向循环.第i步走马成功后,检测若i=mn- 1,且满足终点条件(u= 2,v=m- 1),标志已搜索到满足组合要求的遍历A,即进入组建并输出含空洞的哈密顿圈.第i步走马成功后,检测若i=mn- 1,还未完成遍历,经i=i+1继续下一步探索.第i步选取8个方向若保持q=0,即i时的8 个方向均不能走马,在此卡住,不能再向前了,于是方向t(i)与此时马位清“0”后,经i=i-1迭代回溯到前一步继续探索.当回溯到i=0时,所有结点搜索完成,结束.哈密顿圈是一个封闭圈,无所谓起点与终点.为方便查阅,习惯把棋盘的左上角置“1”进行规范化输出.棋盘左上角遍历按遍历A旋转180°实际输出,注意到此时棋盘左上角元素实为 A遍历的d(n,m).因而可设e=d(n,m)- 1,组合圈的每一步均减去e,这样使棋盘左上角置“1”.同时,为衔接必需,根据图1所示逆时针构建中各遍历所在位置进行调整:左边从上至下共wv个遍历的元素需分别加上mn、…、wvmn;下部从左至右横排的wh个 A同向遍历的元素需分别加上(wv+1)mn,…,(wv+wh)mn;右边从下至上共wv个遍历的元素需分别加上(wh+wv+ 1)mn, … ,(wh+2wv)mn;上部从右至左横排的wh-1个同向旋转遍历元素需分别加上(wh+ 2wv+ 1)mn, … , (2wh+ 2wv-1)mn;最后,棋盘左上角遍历中出现的所有非正项均需加上 (2wh+2wv)mn.遍历为n行m列 (m＞2n),请输入n,m:3,8选择wh=wv= 1,构建如图3所示,即得一个14行8列棋盘,中央含8行2列空洞的哈密顿圈.该含空洞的哈密顿圈共有96个马步！应用一元旋转组合模型构建,遍历A还可选3×7、3×9、3×10等.简单构建时选择wh=wv=1即可,若一般地扩展到横排wh个遍历、竖列wv个旋转遍历(这里wh与wv分别为从键盘输入的任意大于 1的正整数),此时要求whm ＞2n≥ 6,而构建元素除以上列举参数外,遍历A还可选5×5、5×6 等.二元支撑组合模式,即需用两个不同的马步遍历A,B通过支撑组合构建含空洞的哈密顿圈,如图4所示.二元支撑组合模式的组合元素遍历A同前,即为n行m列,始点为(1,1),终点为(2,m-1);设组合元素遍历 B为n1行m1列,始点为(1,1),终点为(n1,3).按如图4所示的二元支撑组合模式,遍历A终点(2,m-1)既可与下一个同向的A始点(1,1)相衔接,也可以与异向的 B始点(1,1)相衔接;而遍历B终点 (n1,3)既可与下一个同向的 B始点(1,1)相衔接,也可以与异向的 A始(1,1)相衔接,因而构建时可以进行横与竖两个方向的任意扩展.设上下部设置wh个遍历A,左右部设置wv个遍历B,则所构建的含空洞的哈密顿圈共走2whmn+2wvmn步,构建的棋盘为(2n+wvn1)×whm,所含空洞为wvn1× (whm-2m1).注意到whm≤2m1时组合无空洞,显然要求whm＞2m1.注意到构建需探索两个不同的遍历元素,拟采用递归设计实施探索.建立递归函数:探索在n×m棋盘中始点为(x,y)、终点为(x1,y1)的马步遍历.递归过程中,栈保留了递归过程中的各个状态的参数,因而可省略以上回溯设计中的t,x,y数组.控制马步规则的a、b数组与二维数组d(i,j)同前.在控制k循环中若对所有k= 1,2,… ,8,候选位置(u,v)均不满足走马条件(或位置出界,或位置非空),则通过实施回溯,继续前一步的检测.若第g步全部8个位置已走完,则回溯到g-1步.对于g-1步,k=k+1后继续检测,直到该步8个位置已走完时,又回溯到前一步.若第g步走步成功且g＜mn,则g+1后递归进入下一步探索.整个程序依此进行递归检测与回溯,直到回溯到第1步结束. 当走到第g步时,若mn且满足终点条件(u=x1且v=y1)时,即已搜索到指定遍历,标志量q=1,返回主程序.若 =mn但不满足终点条件时,则g=g- 1继续搜索.主程序两次带不同的始点 (x,y)与终点 (x1,y1)调用递归函数搜索遍历B、A.首先若探索B成功,则把d数组元素赋值给c数组,同时d数组元素清0,为接着探索A遍历作准备.若两次探索成功,则按左上角置“1”规范(同前,具体数据作相应修改)输出组建的含空洞哈密顿圈.两次调用若存在一次搜索不成功,输出“没有合适的遍历”而结束. 遍历B为n1行m1列,请输入n1,m1:4,3遍历A为n行m列(m>2m1),请输入n,m:3,10选择wh=wv= 1,得如图5所示棋盘为10行10列,中间空洞为4行4列的哈密顿圈.该含空洞的哈密顿圈共有84个马步.由输出结果看,马步从棋盘左上角开始,围绕中央空洞潇洒走一“回”(“回”字通道宽度为 3格),最后又回到出发点.应用二元支撑组合模型构建时,遍历A的参数同前列举,而遍历B可选3×9、3×11、4×3、4×5、5×5等.应用组合模型对含空洞的哈密顿圈的探索与构建,拓广了哈密顿圈图论课题的研究范围.以上提供的两个构建含空洞的哈密顿圈的组合模型也可以构建某些棋盘参数较大的不含空洞的哈密顿圈.应用一元构建组合模型时,如果参量m=n(例如m=n= 5),选择上下部各设置2个A,左右各设置wv个A时可构建棋盘为(wv+ 2)n×2n的不含空洞的哈密顿圈.应用二元构建组合模型时,如果输入的参量满足m=2m1(例如n1=4 ,m1=5,n= 3,m=10)时也有可能构建棋盘为(2n+n1)×m不含空洞的哈密顿圈.应用常规回溯或递归搜索哈密顿圈,当棋盘参数较大时,因相应回溯层次太多或递归深度太深而显得无能为力,采用以上组合方式是一个较好的解决途径.在给定棋盘的行与列,同时给定中央空洞的行与列的哈密顿圈搜索时,必须根据具体实际选择组合模型与运行参数.本文推出的两个组合模型只限空洞在棋盘中处于上下对称、同时左右也对称的正中央,如果要求空洞在棋盘上下或左右有偏移时,必须设计更复杂的多元组合模型.【相关文献】[1]宁安琪,宁宣熙.有洞棋盘的马步哈密顿圈问题及其实证研究[J].小型微型计算机系统,2004,(12):2126～2130[2]宁安琪,宁宣熙.正方棋盘中广义马步哈密顿圈问题的若干研究结果[J].小型微型计算机系统,2005,(09):1551～1555[3]徐尚进.有向图具有哈密顿圈的一个充要条件[J].广西大学学报(自然科学版),1999,(2)[4]宁宣熙.堵塞流理论及其应用[M].北京:科学出版社,2005[5]Zhu Yu-long,Shi Gang.Two new solutions for the Knight's tour problem[J].Mini-Micro Systems,1996,17(8):51～59.[6]Ning Xuan-xi.Study on application of blocking flow theory in determination of Hamiltonian Guaph[R].Report on Aeronautical Science and Technology of China,GF-99045.(1999)[7]Kevin McGown,Ananda Leininger.Knight'stour[EB/OL].http://oregonstate,edu/garityd/reu/.。
一种Arnold变换和骑士巡游算法相结合的医学图像置乱法邢益良;韩宝如;符石【摘要】图像加密对保护医学图像安全性具有重要意义.针对Arnold周期性安全问题,利用Arnold变换和骑士巡游算法结合解决此问题.先迭代Arnold变换置乱图像,再把置乱图分成大块和小块,最后骑士巡游算法从局部和全局对图像进行置乱加密.该方法具有置乱度高和安全性高等优点.%Image encryption is very important in protecting medical images. To solve the security problem of Arnold's periodicity,a method of combining Arnold and Knight's Tour algorithm is proposed. Firstly,an image is scrambled in an iterative process of Arnold. Secondly,it is cut into large and small areas,Lastly,it is scrambled by knight's tour algorithm locally and globally.The method enjoys the advantages of good scrambling and high security.【期刊名称】《苏州市职业大学学报》【年(卷),期】2015(026)004【总页数】3页(P7-9)【关键词】骑士巡游;Arnold;图像加密;医学图像【作者】邢益良;韩宝如;符石【作者单位】海南软件职业技术学院软件工程系,海南琼海 571400;海南软件职业技术学院软件工程系,海南琼海 571400;海南软件职业技术学院软件工程系,海南琼海 571400【正文语种】中文【中图分类】TP391.41随着网络和多媒体等技术快速发展，数字化图像越来越趋于网络化传输，数字化图像经常会涉及个人隐私、企业机密和国家安全，一旦图像的重要信息被人恶意地截取将带来无比巨大的损失甚至是灾难.在医疗领域，医疗系统的发展让医院每天都能产生数量庞大的医学图像，由于医学图像包含有病人的重要隐私，因此需要在存储和传输方面对医学图像进行安全性保护.对医学图像进行置乱加密使其能在网络上安全地传输已成为重要的研究方向.图像置乱技术是指通过破坏图像结构，将一幅数字图像变成一幅杂乱无章的图像，使人眼无法从中提取有价值的信息，即使第三者截获图像通过各种方法成功攻击图像，也将会付出沉重的高额代价，这在一定程度上保护了图像信息.Arnold变换[1-2]和骑士巡游[3]置乱法是常用的图像置乱法，Arnold变换虽然具有信息隐藏效果好等特点，但由于其周期性且密钥空间小，因此容易遭到攻击；骑士巡游置乱法虽然密钥空间巨大，但其置乱效果较差.本研究将Arnold和骑士巡游相结合，利用骑士巡游密钥空间大这一特点解决Arnold周期性安全问题. Arnold变换俗称猫脸变换，是俄国数学家Vladimir Arnold提出的一种变换.二维图像可作二维Arnold变换，Arnold变换原理是对图像的像素先做x轴方向的错切变换，再做y轴方向的错切变换，最后把原像素值回填至错切后的新像素位置.设f表示正方形图像，N(N≥5)为图像f的宽或高，f(x，y)表示某一像素，x和y 分别表示该像素的横纵坐标.可将图像f的二维Arnold变换定义为式中(x1，y1)是变换后新图像的像素点坐标，mod是模运算，模运算相当于切割回填操作，由于(x1，y1)会越界，需要切割回填到新图像边界内.Arnold变换实际上是将原图像某一像素点(x，y)的灰度值或RGB值移至变换后的另一像素点(x1，y1)处.对数字图像应用Arnold变换迭代计算一定次数，变换后的数字图像将变得“杂乱无章”，人们通过眼睛很难获取到原数字图像的信息.Arnold变换具有周期性，也是Arnold置乱后的图像再经一定迭代次数的Arnold 变换可还原回原数字图像.模N的Arnold变换的周期等于以N的两两互素的因数为模的变换的周期之最小公倍数[4-5].表1列出了不同规模图像的Arnold变换周期.从表1可知，Arnold变换周期随图像规模变化，虽然并不是正比关系，但可以程序计算出图像规模对应的Arnold变换周期.骑士巡游问题首次由著名瑞士数学家Euler提出.骑士巡游问题(knight's tour problem)：设有一个n×n的棋盘，任意指定一棋格放置一“马”，“马”按“日”字规则走，“马”从初始棋格出发并按“日”字移动不重复地遍历完棋格的巡游路径.一个8×8棋盘的巡游路径可通过回溯程序求解[6]，其棋盘巡游路径数量大约有1.305×1 035条，一条巡游路径即为一个矩阵，此矩阵即为一密钥，密钥数量起到了安全保障作用.一个5×5以上的棋盘，偶数格棋盘总存在对应的巡游路径.把一幅图像分解成若干个小图片，每个小图片即为一个棋盘，按巡游路径置换图片中的像素位置能起到图像置乱的效果.Arnold变换和骑士巡游相结合置乱图像的算法，思路是首先应用Arnold变换对图像进行迭代计算，然后把图像划分成小块和大块，使用骑士巡游算法对小块和大块进行置乱，对大块和小块置乱相当于从全局和局部对图像进行了置乱.设w(w≥5且w≤N)为小块的宽，w1(w1≥1且w1≤N/5)为大块的宽，matrix1是w×w的巡游矩阵，matrix2是w1×w1的巡游矩阵，算法置乱具体过程为：①对图像f应用Arnold变换迭代m次，计算生成图像f1；②局部置乱，按从左到右、从上至下为划分原则，把图像f1划分成个不重叠的尺寸为w×w的小方块，选用matrix1对小方块内的像素进行骑士巡游置乱生成图像f2；③全局置乱，按从左到右、从上至下划分原则，把图像f2划分成w1×w1个不重叠的尺寸为的大方块，选用matrix2和骑士巡游算法移动大方块的位置生成图像f3，f3即是最终生成的置乱图像.其逆运算过程即为Arnold变换和骑士巡游相结合置乱图像法逆向计算过程.将Arnold和骑士巡游相结合的方法在VS2005平台上通过运行.图1是Arnold和骑士巡游相结合的方法的置乱效果，其中：图1(a)是原图；图1(b)是对图1(a)迭代10次Arnold变换的置乱效果；图1(c)是对图1(b)进行骑士巡游局部和全局运算后的加密效果，也即是最终置乱效果图.图2是不同方法置乱效果比较图，其中：图2(a)是原图；图2(b)是5×5矩阵的骑士巡游法置乱效果；图2(c)是Arnold迭代5次的置乱效果；图2(d)是Arnold和骑士巡游法相结合的方法迭代5次的置乱效果.比较各图可知，Arnold和骑士巡游相结合的方法置乱效果最好，Arnold方法次之，骑士巡游置乱效果最差.骑士巡游拥有数量庞大的密钥，而Arnold密钥数量最少，因此，骑士巡游安全性较高，而Arnold安全性极低.将Arnold和骑士巡游方法结合具有置乱性好和安全性高等优点，适用于医学数字图像加密等应用领域.通过骑士巡游算法解决了Arnold密钥空间小、容易被外来攻击解密带来的安全性问题，通过Arnold方法解决了骑士巡游置乱效果差的问题，由于本研究算法没有对图像像素值进行置换，因此置乱前后的直方图相同，其安全性有待进一步研究.【相关文献】[1] 任洪娥，尚振伟，张健. 一种基于Arnold变换的数字图像加密算法[J]. 光学技术，2009，35(3)：384-387，390.[2] 孔涛，张亶. Arnold反变换的一种新算法[J]. 软件学报，2004，15(10)：1558-1564.[3] 邢益良，马亮，韩宝如，等. 基于骑士巡游的匀速移动图像置乱算法[J]. 计算机与现代化，2014(4)：41-46.[4] 黎罗罗. Arnold型置乱变换周期分析[J]. 中山大学学报：自然科学版，2005，44(2)：1-4.[5] 张俊. 基于分布式数据挖掘的隐私保护应用研究[J]. 长春大学学报：自然科学版，2014，24(12)：1666-1670.[6] 王力强. 马步遍历问题与骑士巡游问题的回溯算法[J]. 科技信息，2011(7)：70-72.。
