置乱变换（精选4篇）
置乱变换 篇1
摘要：Arnold置乱由于其简单易懂被应用到数字水印、安全防伪、军事机密等各个领域,并得到了很好的效果。Gray码变换由于其在彩色空间和位置空间都能灵活运用等特点在信息安全中也得到了很好实际应用。但是,由于两种算法相对简单,很容易被入侵者破解,为了提高信息的加密程度和抗攻击性,提出一种Arnold与Gray码变换相融合的双置乱算法,使得加密信息在位置空间和灰度空间上都得到很好的隐藏。实验结果表明,该方法能很好地应用在图像处理方面,为信息隐蔽技术的预处理工作提供更好的保证。
关键词：Arnold变换,Gray码变换,图像置乱,信息隐蔽
0 引言
伴随着互联网的逐渐普及,多媒体技术、信息存储技术的不断发展,越来越多的数字图像信息在网络上传输,并且成为了人们日常生活中获取资源信息的主要途径之一,由此带来的信息安全问题也受到广泛关注。面对越来越多的数字产品的版权和数据安全得不到稳定的保护等现代问题,也因此成为一项备受关注的热点话题和亟待解决的问题。因此对网络中传输的大量数字图像信息如何进行可靠的加密处理,受到众多学者的关注,是网络信息时代一个值得深入研究和探索的课题[1,2,3,4]。
图像传输等过程中,为了安全保密,经常对图像进行编码然后解码,编码的目的是防止信息泄露,这就是图像加密。图像加密的方法很多都可以从图像变换方法中找到[5]。
图像置乱是通过相关的变换公式进行编码,从空域改变图像内部信息的排列分布或者从频域彻底改变图像信息内容的一种信息加密技术,主要应用在对数字图像加密的前期预处理和后续解密当中。在需要信息隐藏的网络传输中,置乱技术能很好地消除隐蔽信息间的相关性,增强通信的隐蔽性,设置相应的秘钥对隐蔽信息进行加密处理,还能减小错误比特率以增强秘密信息的鲁棒性[6,7,8,9]。目前运用比较广泛的置乱方法越来越多,如Logistic变换、Hilbert变换、仿射变换、Arnold变换、广义Gray码变换、幻方变换、Conway游戏、Fibonacci变换等方法。其中Arnold变换由于简单易懂等特点受到学者们的广泛应用。Gray码变换因应用灵活被运用在图像处理方面,它不仅可以从位置空间改变图像信息,还可以从色彩空间上改变图像灰度值达到处理图像的目的。但是,由于Arnold变换的简单性和周期性,破坏者在知道图像的置乱次数的条件下可以轻易破解加密信息,使得传输者的隐蔽信息被泄露,信息安全得不到保证。为了提高加密信息的安全性,提出首先运用Arnold算法进行置乱加密处理,打乱图像的原始载体信息,然后在此基础上利用后面提到的Gray码变换方法,使加密的图像信息彻底改变,达到双置乱效果。隐蔽信息能够得到更深度的加密保护,提高抗攻击能力,确保隐蔽信息的安全传输。
1 Arnold变换与Gray码变换
1. 1 Arnold变换
Arnold变换过程可以用矩阵表示如下:
其中x,y ∈ { 0,1,2,…,N - 1} ,N为图像的长和宽。mod是模运算,目的是确保置乱后的图像信息的位置范围不变,仍然落到图像区域内部。( x',y')T是图像( x,y)T位置的像素点经过置乱得到的新位置的坐标。经过一次Arnold变换后图像还留有许多原始信息,即并没有完全达到彻底置乱图像的作用。在实际应用中,Arnold变换是指经过多次迭代Arnold变换的结果[10]。运用等式( 1) ,经过多次反复变换,就得到最终理想的加密置乱图。
设定自然数N > 2,Arnold变换公式的周期用mN表示,根据Arnold变换具有周期性的特点,式( 2 ) 中的最小自然数n即为Arnold变换的最小正周期:
其中,对于矩阵阶数为N的数字图像来说,n是图像置乱实现周期变化的最小置乱次数。可以证明,Arnold变换式一一对应的,从而保证了经过变换的图像可以通过周期变换完全恢复原图像[10]。
图1 是一幅380 × 380 大小的图像,经过式( 2) 计算得到图像的置乱周期为90,对图1( a) 的原始图像分别进行10 次、90次Arnold置乱,得到图1( b) ,( c) 的变换结果。可见,图像经过周期变换再次恢复到初始图像。
依据Arnold算法的周期性特性,可以较容易实现对信息图像的加密与解密工作,是信息隐蔽技术的一种很好的预处理方法。但是由于Arnold的周期性强,编程实现简单,使攻击者能轻松地破译加密信息,达到拦截信息或篡改信息的目的。发生在一些政治军事上就会危害到国家利益,所以Arnold变换还存在被改进的空间。为此需要想办法加入其他的加密技术,以提高信息的保密度。
1. 2 Gray码变换
设定变量u为一个非负整数,其二进制形式的表达式对应为u = ( upup -1…u1u0)2,令:
得到一个二进制整数g( u) = ( gpgp -1…g1g0)2。式( 3) 就叫作Gray变换,二进制整数g( u)称为变量u的Gray码( 格雷码) 。其中运算“⊕”为模2 加法。
Gray码算法的优点是可以对像素编码进行置乱,从位置空间改变图像信息; 也可以不改变位置,对图像灰度值编码进行置乱,也就是从色彩空间上改变图像信息。此算法也可以推广到任意进制情况下的广义Gray码,适用性非常灵活。
根据Gray码变换原理对数字图像进行图像信息加密,也是一种实现图像信息隐藏预处理的方法。置乱变换过程也是加解密的过程,要想有效地进行信息的加密与恢复,得到传输信息,变换的可逆性是至关重要的,即处理的图像能够经过相应的反变换,最终得到复原。
Gray码变换实际上就是异或变换,同理得到Gray码反变换公式:
图2 是经过Gray码变换与相应的反变换置乱得到的变换图像。
2 Arnold和Gray码相融合的双置乱算法
前面具体讲述了Arnold变换算法的原理,可以改变数字图像灰度信息的分布,达到了信息加密的目的[11]。但是由于Arnold变换的局限性,其周期性强,容易被非法入侵者破解等弱点,使得Arnold变换在实际应用中受到限制[12]。为了使一些重要信息得到更好的隐蔽,就需要更好的加密技术,使得在原有的简单技术上实现深度加密,达到算法的简单易行,又同时提高信息的加密破解难度。本文在运用Arnold变换对图像进行置乱处理的情况下,又附加上另一种置乱方法—Gray码算法。此算法不仅是一种色彩空间域上的置乱方法,通过彻底改变图像的像素灰度值,直方图的总体分布,达到置乱; 也可以从位置空间上,通过改变图像信息中像素的具体位置坐标,得到加密处理的图像。基于Arnold和Gray码变换的双置乱变换( 为了便于描述,后面将简称“A&G”变换) 是基于Gray码在色彩空间上的置乱方法。
图3 为“A&G”变换的流程图。“A&G”变换是运用两者结合,首先图像的位置空间得到置乱,解除空间相关性,然后解除色彩相关性,达到改变直方图的效果,提高置乱的均匀度。
下面把需要加密处理的原始图像记作A,大小尺寸设定为,图像在RGB灰度图像条件下处理,对应的像素灰度值范围为0~255,经过置乱变换后的最终图像为B,尺寸大小为N×N(设定加密图像为方阵是为了与置乱前图像尺寸保持一致),根据提出的“A&G”变换的置乱思想,设计步骤描述如下:
步骤1已知图像A为需要加密处理的目标图像,根据Arnold算法的原理,置乱变换的映射关系可以用σ表示,。]置乱的次数用n表示,经过一次Arnold变换得到置乱结果用A1表示,则图像A1与原图A之间的映射关系,可表示为:
其中aij表示像素矩阵中第i行第j列位置上的灰度值,经过 σ 映射,改变像素坐标的位置。
得到置乱像素新坐标,并得到一次Arnold置乱结果,图像记作A1;
步骤2 图像的Arnold变换,是在图像像素位置上实现的置乱操作。Arnold置乱是对图像中的每一个像素点的坐标进行变换,即应用参考映射矩阵对坐标相乘,在与图像矩阵的宽度进行模除,经过有限次的置乱变换得到初步置乱后图像AN;
步骤3 对步骤2 中得到的置乱结果AN的各像素点的像素值,利用式( 3) 进行Gray码变换,得到最终要加密的目标图像B 。
图像置乱起到对图像信息隐蔽的作用,而还原操作也是一种置乱操作,是置乱处理的一个逆过程,是保证信息在安全的情况下能准确无误的传输到解密人手中的一种很好的处理方法。根据置乱的步骤要想恢复置乱图像,首先要对已经置乱的目标图像B进行Gray码反变换,解除Gray码置乱效果,再进行Arnold变换操作,得到原始信息。大体步骤如下:
步骤1 首先对得到的加密图像B利用式( 4) 给出的Gray码反变换公式进行置乱,初步处理结果得到图像AN;
步骤2 运用Arnold变换的逆变换公式或者Arnold算法的周期特性等方法,将步骤1 中得到的初步还原图像AN恢复到图像A'。对比恢复后的图像A' 与原图A的图像信息,证明变换是可恢复的。
3 仿真实验及验证结果分析
用图2 中的( a) 图作为仿真实验的原始图像,在10 × 10 的尺寸大小情况下对图像进行“A&G”算法处理。经过新算法的处理,得到图4 显示的仿真效果示意图。其中图4( a) 为原始图像的像素信息,图4( b) 显示的是经过Arnold算法后的像素信息,同理图4( c) 则是经过“A&G”变换后的像素信息。
由图4 的“A&G”变换可知,图像信息经过Arnold变换处理得到新的图像信息,新的图像信息内容没有发生改变,只是改变了原来信息的存储位置。但是经过双置乱变换后的图像,信息发生了改变,改变了原来图像携带的信息,起到了深度加密的目的,对信息隐蔽的深入研究提供了很好的方法。
根据Arnold变换与Gray码变换都具有可逆性的原理,在信息隐藏的后期处理中可以将置乱图像复原,解除加密隐藏。例如,一个程序员把加密信息发送给指定要接收的人员后,接收人要根据秘钥原理进行解密处理,实现信息的复原。
运用两种算法相结合的办法,不仅改变了图像的灰度分布,也使图像的灰度值发生了改变,实现了对图像深层加密的目的。对研究数字图像的信息隐蔽技术预处理的后续工作提供了很好的技术前提。
为测试算法的有效性,更加全面地衡量与比较所提算法的置乱效果,进行下面的仿真实验。图5 给出仿真实验的原始图像以及其灰度直方图信息,图6 为“A&G”算法对原始图像的变换效果图,并显示图像置乱后的直方图,同时还给出Arnold算法和Hilbert算法的两种置乱变换相对应的处理结果作为参照。
图6 显示,与作为参考的两种现有的方法相比,新提出的置乱方法——— “A&G”变换经过置乱后得到的图像纹理更细,颗粒更加均匀,更接近于理想的白噪声状态。从人类视觉系统的角度来说,加密图像的相关信息被完全打乱,看不出加密图像的相关内容,置乱效果最好; 对比三种变换方法置乱后的灰度直方图,Arnold变换和Hilbert变换处理得到的直方图信息置乱前后没有发生变化,与原始图像的直方图一致,破坏者容易根据截获的直方图信息破解加密信息,窃取重要的信息内容,而这个缺点对于所有基于位置空间变化的图像置乱方法来说也是一个目前急待解决和难以攻克的话题焦点。而经过“A&G”变换得到灰度直方图与前两种方法相比差距很大,不仅改变了灰度值,而且处理后的灰度值比原来分布的更加均匀,使整体上得到的置乱图像的灰度值在整个灰度空间上均匀分布。这就证明了在数字水印等需要进行信息隐藏的技术预处理中,新的置乱方法可以将加密信息更加均匀的嵌入到宿主信息中,使后续工作中得到的水印透明性更好,信息隐藏的更加难以察觉[13]。
下面根据文献[13]中定义的比较置乱程度的三个变量,从三个角度来衡量图像的置乱效果。
首先从位置空间域的角度,采用置乱均匀度作为参变量来衡量图像加密的效果。图像尺寸为M × N,m是图像某一点的m× m邻域的宽度,E是在m × m邻域内原始图像“老邻居”( “老邻居”: 相对原来位置不变的像素点) 的数学期望,P'k是有k个相邻不变像素的概率统计值,用与E的偏离程度来表示置乱“均匀度”ED。ED的值也随着m值大小的变化而相应的改变,得到归一化后的置乱均匀度ED :
从像素的位置空间上说,当变换后的图像像素位置与原图像的像素信息完全一样时,置乱均匀度ED = m2- 1 - E,此时归一化置乱均匀度ED为1; 当变换得到的最终结果达到“均匀”的最佳状态时,此时ED = 0。依据概率分布形式归一化处理,ED的取值范围: 0 ≤ ED ≤ 1。ED越接近0 仿真得到的置乱图像越均匀,加密效果越好,越接近1 则效果越差。
从相似度的角度来看,若把理论概率分布P( P0,P1,…,Pm2 -1) 和实际统计分布P'( P'0,P'1,…,P'm2 -1) 当成是两个m2维的向量,两个向量的相异度可以用绝对值距离来度量:
绝对值距离D的值越大说明两个向量的相异度越大,置乱处理后得到的图像的均匀度就越差; 反之D的值越小,置乱图像就越接近于置乱“均匀”状态,置乱达到的整体水平就越好。这是针对相异测量的方法。它的归一化形式为:
归一化后D的范围: 0 ≤ D ≤ 1 。
根据式( 8) 的原理,同理也可以运用两个向量夹角的余弦值来体现图像置乱前后变换的相关性,作为相似度进行比较:
S越小说明两个向量的相似度越小,置乱均匀度越差,得到的加密效果就越不明显; S越大说明两个向量的相似度就越大,置乱就越接近“均匀”的理想状态,得到的评比结果就越好。S的取值范围为0 ≤ S ≤ 1 ,这是针对相似测量的方法[14]。
依据图6 得到的置乱效果图,运用上述三种衡量置乱程度的变量比较三种置乱算法的置乱程度,结果见表1 所示。
从表1 中可知,随着加密次数的逐渐增加,图像越接近置乱“均匀”状态,只是三种方法的置乱速度不同,显示的效果也就不同。“A&G”变换ED趋近0、S趋近1 远远好于其他两种方法,D的值也比其他两种方法更加趋近于零。 可见,新提出的“A&G”算法的置乱效果,远远超出已有的Hilbert和Arnold两种算法所达到的最佳效果。充分证明了新提出的置乱算法能很好地实现对图像的均匀加密处理。且该算法与人类视觉的评价结果一致,能够更好地实现信息加密的目的,对以后在信息隐蔽的实际应用中有重要作用。
4 结语
在图像置乱技术的研究中,Arnold变换算法因其方法简单、运用方便等特点,被学者们广泛应用于图像加密技术的研究中。通常使用Arnold变换可以实现图像基于像素位置空间的变换,但不会改变图像携带的像素信息,使得加密图像的置乱效果不能达到理想的要求。而且,由于Arnold算法本身存在周期性强、易破解性等缺点,本文在上述方法的基础上又加入Gray码变换算法,提出一种新的置乱方法——— “A&G”变换,达到对图像进行双层置乱处理的目的。实验证明,运用Gray码变换在色彩空间上的应用,在Arnold置乱处理的基础上,采用两者相融合的方法,在保持原来优点的同时,很大程度上增加了信息的破译难度,实现了对加密图像的双重置乱处理。充分说明了本方法能更好地运用在信息隐蔽技术的预处理中,具有较高的实际应用价值。
置乱变换 篇2
随着计算机技术的发展和网络技术的推广，网络信息安全已经成为大众关注的热点。信息隐藏技术作为信息安全的新领域，在隐蔽通信和计算机网络取证方面发挥着越来越重要的作用，尤其在军事和国家安全等对信息的安全性和机密性有更高要求的领域，数字水印作为信息隐藏技术的重要分支前景更是广阔。
2 Arnold置乱变换
Arnold变换是在Arnold遍历理论研究中提出的一种变换。将数字化图像看成是一个函数在离散网格点处的采样值，就得到了一个表示图像的矩阵。矩阵中元素的值是对应点处的灰度值或RGB颜色分量值。采用基于Arnold变换的数字图像置乱技术，通过如下变换：
其中，N是矩阵的大小，(x,y)和(x',y')表示像素点在变换前后的位置。它定义的Arnold变换实际上是一种点的位置移动，这种位置移动实际上是对应点的灰度值或者RGB颜色值的移动，且这种变换是一一对应的。此外，这种变换可以迭代地做下去。
迭代的公式为：
Amold变换可以看作是裁剪和拼接的过程，通过这一过程将离散化的数字图像矩阵S中的点重新排列。由于离散数字图像是有限点集，这种反复逐次变换的结果，虽然在开始阶段S中像素点位置的变化出现相当程度的混乱，但是迭代进行到一定的步数，必然又恢复到原来的位置，即变换具有周期性。Dyson和Falk分析了离散Arnold变换的周期性，给出了对于任意N>2,Arnold变化的周期为。
对于给定的自然数N,Arnold变换周期T是使得下式成立的最小自然数n:
计算周期T的算法使n从1开始每次增加1，直至式成立，此时的n值即为图像阶数N所对应的Arnold变换周期T。不同阶数N下对应的Arnold变换周期T的部分结果如表1所示。可以看出，Arnold变换周期总的趋势是随着图像的增大而增长，但局部会有一些振荡。
图1是256×256的Lena图像经过不同次数Arnold变换的效果图。其中图b、c、d分别对其迭代了1次、20次、55次后的置乱图像，可以看出，迭代了1次的图像效果依稀还看到原始图像的部分信息，迭代了20次、55次的置乱图像则丝毫看不出原来的任何信息，具有很好的置乱效果。
3 小波变换
小波分析方法是一种窗口大小固定但其形状可改变，即时间窗和频率窗都可改变的时频局域化方法，在低频部分具有较高的频率分辨率和较低的时间分辨率，在高频部分具有较高的时间分辨率和较低的频率分辨率，所以被誉为数学显微镜。正是这种特性，使小波变换具有对信号的自适应性。
由于在实际应用过程中，所处理的数字图像是二维的离散信号，因而这里采用离散小波变换(DWT,Discrete Wavelet Transform)。它是采用对尺度参数和位置参数进行离散化处理。可以选取，j是整数，大于1的固定伸缩步长。取且与小波具体形式有关，k为整数。这种离散化的基本思想体现了小波变换作为“数学显微镜”的主要功能，选择适当的放大倍数，在特定位置研究信号，然后再平移到另一位置继续研究，若放大倍数不合适，可使尺度按小步长移动一个距离。
为适合计算机运算，常采用二进离散小波变换，即取=2，=1，则：
离散化的小波系数为：逆变换为：
4 算法原理
4.1 嵌入算法
这里利用Arnold置乱变换和小波变换对图像进行数字水印的嵌入。首先对载体图像进行多级小波变换，从而得到该载体图像在不同分辨率下的多个子图，同时将水印图像利用Amold变换进行置乱，完成之后对置乱图像进行一级小波变换，得到水印图像的一个低频和3个高频子图。分别对载体图像的分解子图与水印图像的分解子图线性相加，逆变换之后得到嵌入水印的载体图像。具体算法如下：
载体图像的小波变换
(1)水印图像的Amold置乱。
(2)水印图像的小波变换。
(3)两幅图像小波分解子图的线性相加。当完成了两幅图像的小波分解之后，利用下述公式相加。
其中为嵌入系数，IL为载体图的低频部分，IH为载体图的高频部分，为水印图的低频，为水印图的高频。I1,I2为嵌入后的水印图像。
(4)对于相加后得到的低频、高频子图进行小波逆变换，完成整个水印的嵌入。
4.2 水印提取算法
数字水印的提取过程即为水印嵌入的逆过程，首先对嵌入水印的图像进行小波变换，得到不同分辨率的子图，利用式，提取水印图像的小波系数，然后进行一级小波逆变换，并按照Amold置乱次数得到水印图像。
5 实验结果
本实验以Lena(256*256)灰度图像和baboon图像为实验源图像，将视觉上有现实意义的二值图像“水印”作为有意义水印，用haar小波对测试图像进行小波变换，实验结果中给出了相似度与攻击的关系图以及部分水印图像，统计结果显示，解密后的图像与加密前的原图像完全一样，解密效果非常好。实验环境为Matlab7.0，如图2所示。
6 结语
探讨了基于amold置乱和小波变换的数字水印算法，深入研究了基于该算法的数字水印实现过程，该算法利用小波变换将载体图像和水印图像进行不同级别的小波分解，利用分解后的小波系数将两幅图像进行了融合，并通过融合系数控制水印图像的载入强度。实验证明该算法具有较好的效果和鲁棒性。
参考文献
[1]Kim Young-Sik,O-Hyung Kwon and Rae-Hong Park.Wavelet-based watermarking method for digital images usingthe human vi-sual system[J],Electronics Letters,18th Marth1999:35(6):466-468.
[2]Mallat S1A theory for multires olution signal decompositi on:the wave2let rep resentation1 IEEE Trans Patt Recog And
[3]茅时群,高健.灰度图像水印的自适应二维数字水印算法[J].微计算机信息,2006,22(1):160-164.
[4]王道顺,梁敬弘,戴一奇,等.图像水印系统有效性的评价框架[J].计算机学报,2003,26(7):652-655.
[5]齐东旭,邹建成,韩效肴.一类新的置乱变换及其在图像信息隐蔽中的应用.中国科学(E辑),2000,30(5):440-447.
[6]孙新德,路玲.1Arnold变换在数字图像水印中的应用研究[J].信息技术,2006,10:129-132.
置乱变换 篇3
随着网络技术和多媒体技术的飞速发展,数字化信息面临着诸多的挑战—各种窃取和篡改等等,数字信息的安全性和版权保护越来越受到人们的关注[1]。仅靠传统的密码学知识已不能很好的解决这一问题。而综合了传统密码学的认证问题和鉴别问题的特点,又与被保护数据紧密结合的数字水印技术,则越来越受到人们的重视[2]。
所谓数字水印,就是将数字、序列号、文字、图像标志等表示或版权信息嵌入到多媒体数据中,然后在网络上发布,日后通过计算机对数字产品中嵌入的水印标记的读取与检测,起到防盗版,侵权和随意篡改的作用。为了达到信息隐藏目的,向数字作品中所嵌入的数字水印应该至少具有以下3个特性:透明性、鲁棒性和可证明性[3]。按照水印的嵌入过程,数字水印分为时域/空域水印和频域/变换域水印,频域水印比时域水印具有更强的鲁棒性与透明性.由于小波变换具有全局性的特点,它比其他变换域方法更能够有效地隐藏秘密信息,所以基于小波变换的频域水印技术是目前国内外研究的热点。
基于上述考虑,本文采用具有实际意义的二值图像为水印,在置乱方法上对传统的Arnold变换作了一定的改进,并提出了与JPEG 200和MPEG—4相兼容的基于DWT的水印算法。该算法消除了水印像素的空间相关性,能够抵抗常见的各种攻击,具有较好的不可见性和鲁棒性。
1算法的基本原理
在基于小波变换的数字水印算法中,利用人眼的视觉系统(humanvisualsystem)的特性,通过向小波变换域中加入水印,是目前公认的鲁棒性与透明性较强的算法之一。
基于图像置乱和小波变换的数字水印算法流
1.1 嵌入位置的选择
根据人类视觉系统(HVS)的纹理特性和照度掩蔽特性,图像的边缘和纹理部分,即图像小波变换的高频部分能隐藏较多的数据。将水印嵌入到该部分不易被察觉。具有较好的不可见性。但这样的水印却经受不住有损压缩、低通滤波等一些简单的图像处理,水印信息很可能在量化、压缩等处理中被删除。若将水印信息嵌入到图像的平滑部分,即图像DWT分解后的低频子带。 虽具有较好的鲁棒性,但是该部分集中了图像绝大部分能量,对噪声相对敏感。同时该频段的变化对人眼的视觉影响较大,很难保证图像重构后水印的透明性。
针对数字水印的鲁棒性和透明性存在的这一矛盾。本文能将水印嵌入高、低频带的特性相结合,得到效果较好的水印嵌入方案。
选择中、高频系数嵌入水印,如二、三层的中、高频小波系数。因为第二、三层的小波系数是上一层低频系数进一步分解得到的结果,水印嵌入在这一频段,既具有高频对视觉影响小的特点,又具有低频系数不易被修改、移除的特点,具有较好的鲁棒性。且最低分辨率子图像受压缩等变换的影响较小,因此,把水印信息嵌入到最低分辨率子图像中,水印具有了较好的透明性和鲁棒性。
1.2 水印图像的预处理
图像的预处理通常采用图像置乱的方法。图像置乱作为一种图像加密技术,已成为数字图像安全传输和保密存储的重要手段之一。近年来,随着数字水印技术的兴起,置乱技术又有了新的应用。由于代表版权信息的多为图像水印,因此在水印的预处理阶段,可以通过置乱消除水印图像像素间的相关性,使水印呈现出类似白噪声的特性,在载体被部分破坏时可以分散错误比特的分布,从而提高水印系统的鲁棒性[1]。通过算法比较Arnold变换算法简单且具有周期性,所以在数字水印方面得到了很好的应用。
Arnold 变换(Cat mapping) 是V.J.Arnold 在遍历理论的研究中提出的一种变换,俗称猫脸变换。根据文献[4],传统Arnold 变换为:
(1)式中,( x,y) 是像素在原图像的坐标,(x′,y′) 是变换后该像素在新图像的坐标,N是数字图像矩阵的阶数,即图像的大小,一般考虑正方形图像。当对一个图像进行Arnold 变换时,就是把图像的像素点位置按公式(1)进行移动,得到一个相对原图像混乱的图像。
传统Arnold 变换选取(1)式中的变换矩阵,主要是因为可以得到线性映射,算法简单,效果好,但是攻击者容易解密获得原始图像。因此,本文提出一种新的Arnold 变换。
根据文献[5],将变换矩阵变为:
,其中ad-bc=1(a,b,c,d随机生成)。
在数学理论上证明了其对平面坐标的变换可以作为一种置乱变换。但是由于a,b,c,d随机生成,计算量较大。因此本文在此基础上作了一些改进。将变换阵改为:
,其中q-(q+1) =1(仍然满足矩阵对角线乘积的差为1)。
做了改进后的Arnold算法相对于常见二维Arnold变换由于可以使用置乱次数k和变换矩阵中的随机数q作为隐藏系统的密钥,不容易被得知具体的值。因此,改进后的算法提高了抗攻击能力;而相对于文献[2]中算法需产生四个随机数,则减少了计算量。改进后的算法相应计算公式为:
由于Arnold变换呈周期性,水印图像的尺度是一定的。因此,置乱迭代一定次序后总可以恢复到原始水印图像。
对于给定的自然数N(本文中N为图像的阶数),根据文献[6]Arnold变换周期T是使得下式成立的最小自然数n:
计算周期T 的算法使n从1开始每次增加1,直至公式(3)成立,此时的n值即为图像阶数N所对应的Arnold 变换周期T。计算结果表明,Arnold变换周期总的趋势是随着图像的增大而增长,但局部会有一些振荡。
1.3 水印嵌入与提取
水印添加及提取都是在小波域中进行的。水印嵌入常用的公式为:
xw(k)= xo (k)+αw(k) (4)
(4)式中xo (k),xw(k)分别表示原始图像和加入水印后的图像,w(k)为水印信息,α为水印强度值,α取值大,鲁棒性好,不可见性差;反之,α取值小,不可见性好,但鲁棒性差。可根据实验情况,满足不可见性的前提下,通过提高α来加强水印信息。嵌入水印时,根据随机生成的0、1矩阵P来决定嵌入的水印信息[7]。同时矩阵P作为密钥保存。其逆过程即可提取出水印。
本文中,对随机P矩阵做了一定的改进,对随机生成的0、1矩阵中的1和0的个数进行控制,这样水印的嵌入和提取可以达到更好的效果。
2 算法实现
2.1 水印嵌入
根据Mallat[7,8]分解算法,图像在N个尺度上被分解为细节系数LHn、HLn、HHn和逼近系数LLn,且n=1,2,…,N。LL是最低频段滤波后的低尺度逼近,同级分辨率下,HL包含水平方向高通、垂直方向低通滤波后的细节信息,LH保留的是水平方向低通、垂直方向高通滤波后所得细节信息,HH保留的是水平方向和垂直方向都经过高通滤波后的细节信息。
若原图像Ic是大小为M×M的灰度图像,水印Im是大小为N×N的二值图像,其中:
M=A×2m,N=A×2n,m≥3,n≥2。水印嵌入步骤如下:
Step1:将原始图像进行L层小波分解得到3L+1个子带,分别为cAL、cHi、cVi、cDi,其中i= 1,2,…,L。其中cHi+1、cVi+1、cDi+1均由cAi分解得到;
Step2:使用改进的Arnold变换对对二值水印图像Im进行置乱,得到置乱后的水印图Im*;
Step3:对二值水印图像Im′ 进行K层小波分解得到3K+1个子带,分别为caK、ch i、cv i、cd i,i=1,2,…,K。同时,使size(cAL)=size(caK),即Ic与Im*分解到最后的子图系数矩阵大小相等;
Step4:生成随机的0、1矩阵P,根据情况控制0、1的个数,且size(P)=size(caK)。
Step5:如果P(i,j)值为0,则cHL(i,j)、cVL(i,j)、cDL(i,j)值不变,然后转入Step7。
Step6:如果P(i,j)值为1,则按如下公式计算cHL(i,j)、cVL(i,j)、cDL(i,j)的值:
Step7:重复Step5、Step6直到取完小波系数矩阵的所有点。
Step8:cAL以及其它尺度没有计算的小波系数以及随机矩阵P、水印强度因子α等均作为密钥保存。
Step9:利用修改后的系数矩阵进行小波逆变换,重构带有水印信息的原始图像。
2.2 水印提取与检测
提取过程就是上面嵌入过程的逆过程。并且根据密匙使用Arnold反变换,再根据解的范围,得到像素反置乱坐标,对提取的水印图像做反置乱变换就可以得到恢复的二值水印图像。
2.3 图像评价标准
由于采用的图像及水印在感知上是可视的,所以提取的水印信息很容易鉴别。为了定量分析提取水印的相似性,可采用归一化互相关系数 (Normalize Cross_Correlation,NC)来表征,同时采用峰值性噪比 (Peak Signal to Noise Ratios,PSNR)来评价原始图像和加水印后图像之间的差别。
NC=
其中W1(i,j)和W1′(i,j)为原始图像和嵌入水印前后图像的灰度值。W2(i,j)和W2*(i,j)为未嵌入的水印图像和提取后并反置乱水印图像的灰度值。
当NC值大于0.7时就认为提取出有效水印。当PSNR超过30 dB时,人的视觉很难分辨原始图像和嵌入水印的图像的差别。
3 实验结果及分析
本文以256×256的Lena灰度图像和64×64的二值水印图像做实验。
根据图像评价的标准,峰值性噪比PSNR=54.693 3,而归一化互相关系数NC=0.999 4。因此本算法满足水印信息的不可见性。
本文还对几种常见的水印的攻击进行了实验,并给出了实验结果(如表1):
由表1数据可知,在图像质量很差的时候,如在噪声攻击、拉伸攻击之后,图像PSNR值已经降到30 dB以下,但也能够有效的提取出水印。
其次,由于对水印进行置乱可以消除水印像素的空间相关性,因此在剪切攻击下,仍然能提取出比较强壮的水印。
再次,随着JPEG压缩比的降低,图像质量增加,PSNR值随着增加,提取的水印相似度也随之增加。在图像质量很差的情况下仍然能提取出水印图像。
4 总结
本文提出了一种基于离散小波变换的数字水印算法,在嵌入水印之前采用改进的Arnold置乱算法对水印进行置乱,将置乱后的水印信息嵌入图像小波分解的中高频。提取时先进行逆置乱,并且采用伪随机序列决定嵌入位置,将小波变换和密码学结合起来。
实验结果表明,该方案消除了水印像素的空间相关性,增强了安全性,较好的解决了水印的鲁棒性和不可见性的矛盾,不但数字水印图像隐蔽性好,满足水印的不可见性要求,而且所嵌入的数字图像具有较强的鲁棒性。
由于本文提取水印仍然需要原始载体图像,下一步的工作将是在这方面做出改进,使得提取水印不再需要原始图像,使之更加实用化。
参考文献
[1]Liu R Z,Tan T N.Watermarking for digital images.Proc of the IC-SP98.Beijing,China,1998
[2]Hartunf,K M.Multimedia watermarkingtechniques.Proc of IEEE,1999;87(7):1079—1107
[3]Cox J,Mill E.R L,Bloom A.Digital watermarking.Burlington:Elsevi-er Science,2002
[4]孙新德,路玲.Arnold变换在数字图像水印中的应用研究.信息技术,2006;10:129—132
[5]齐东旭,邹建成,韩效肴.一类新的置乱变换及其在图像信息隐蔽中的应用,中国科学(E辑),2000;30(5)440—447
[6]邹建成,铁小匀.数字图像的二维Arnold变换及其周期性.北方工业大学学报,2000;12(1):10—14
[7]Mallat S.A theory for multiresolution signal decomposition:the wave-let representation.IEEE Trans Patt Recog And Mach Intell,1989;11(7):674—693
置乱变换 篇4
视觉是人们了解外部世界的主要信息通道,随着多媒体技术和网络的迅速发展,过去曾因为数据量庞大而难以存储和传输的图像越来越多地出现在各种各样的应用中,如教育、医疗、军事、遥感等,人们也越来越多地依赖于图像来获得更直观的信息。同时,图像的安全性问题也日益突出。解决图像安全问题的主要手段包括:数字图像的置乱技术、分存技术、隐藏技术和水印技术等[1,2]。其中,数字图像的置乱技术就是将一幅数字图像经过变换, 使其成为面目全非的另一幅没有明显意义的混乱图像, 而操作者在知道算法的情况下, 又能通过特定的算法从混乱的图像中重构出原图像。目前常用的置乱算法有:Arnold 变换[3]、Hilbert曲线[4]、幻方变换[5]等。本文提出一种基于密钥的置乱变换,该方法按一定的方式组合使用Arnold变换和Hilbert变换,既可以达到较好的置乱效果,又可以增强抗攻击能力。
2 图像置乱算法及性能分析
2.1 Arnold变换及性能分析
2.1.1 Arnold变换
二维Arnold变换定义为:
undefined
(公式1)
此变换称作二维Arnold变换。其中公式右端的(x,y)为输入, 表示某一像素点的坐标,x,y∈(0,1,2…N-1),记变换矩阵为
undefined
,左端(x′,y′)为变换结果。
采用Arnold变换对图像进行置乱变换,改变了图像灰度值的布局,达到信息隐蔽的目的。以图1所示的图像(128×128象素灰度图)作为本文实验的原始图像,经14次Arnold变换后的结果如图2所示。
2.1.2 对经Arnold变换的置乱图像的破解
对经过Arnold变换实现置乱的图像的破解,可以利用Arnold变换的逆变换,也可以利用Arnold变换具有周期性这一特性。
根据Arnold变换的定义,可以推导出Arnold变换逆变换的公式(2):
undefined
modN (公式2)
图2是对图1的原始图像经过14次Arnold变换的结果,对图像2进行14次Arnold变换逆变换,就可以恢复出原图像。如果利用Arnold变换进行置乱,攻击者在获得置乱图像后,利用Arnold逆变换进行逐次变换,最终可以找到有意义的原始图像。
周期性是Arnold变换的一个重要特性。所谓周期性是指当算法迭代若干轮次后,将重新得到原始图像。通过实验检测,128×128图像的Arnold变换周期为96。即,对图2所得到的置乱图像,再进行82次Arnold变换后,又会恢复出原始图像。
综上所述,使用Arnold变换对图像进行置乱变换,虽然可以达到信息隐藏的目的,但是很容易被破解,安全性不能得到很好的保证。
2.2 Hilbert变换及性能分析
2.2.1 Hilbert变换
FASS 曲线是一种充满空间(Space-filling)、非自交(Self-avoiding)、自相似(Self -similar) 的简单( Simple) 曲线。Hilbert曲线是FASS曲线的一种,有二维或更高维情形,本文只考虑二维的Hilbert曲线。二维Hilbert曲线不自交地通过格形方块的每一个格点中心一次且仅一次,并且充满整个格形方块区域。按照Hilbert曲线的走向遍历图像中的所有点, 就可以生成一幅新的“杂乱”图像,这就是基于Hilbert曲线所做的数字图像置乱。
Hilbert曲线的入口点和出口点决定了它的走向,也就决定了像素点的遍历顺序,因此根据Hilbert曲线入口点和出口点的不同组合,可以把置乱路径分为八种类型,1阶Hilbert曲线路径如图3所示:
利用Hilbert 曲线进行置乱,影响其置乱效果的因素主要有两个:置乱路径和置乱周期。置乱路径不同,得到的置乱图像数据序列不同,而置乱周期的大小限定了考虑图像置乱次数的范围.
2.2.2 Hilbert曲线的构造考虑将2维格形变为1维序列函数f(x,y):X×Y→f(X,Y)
其中:
X={x:x=xL-1…xr…x2x1x0,xr=0,1,…,L-1}
Y={y:y=yL-1…yr…y2y1y0,yr=0,1,…,L-1}
f(x,y)=〈xL-1xL-1…xryr…x0y0〉=(2xL-1yL-1)4L-1+…(2xryr)4r+…+(2x1y1)41+(2x0y0)第一步 r=0,曲线初始化:
hundefined=0,1,3,2 hundefined=0,2,3,1
hundefined=3,2,0,1 hundefined=3,1,0,2
第二步 r≥1,递归产生r阶Hilbert曲线:
hundefined:0hundefined,1hundefined,3hundefined,2hundefined
hundefined:0hundefined,2hundefined,3hundefined,1hundefined
hundefined:3hundefined,2hundefined,0hundefined,1hundefined
hundefined:3hundefined,1hundefined,0hundefined,2hundefined
其中:,nhr-1(n)=n×4r+hr-1(m),3≥m,n≥0。
利用Hilbert变换对图1所示的原始图像进行置乱,效果图如图4所示。
2.2.3 对经Hilbert变换的置乱图像的破解
与对经Anorld变换的图像的破解方法相似,也有两种方法:一是利用Hilbert变换的周期性,一种是利用逆变换进行破解。但一般情况下,Hilbert变换的周期较大,并且同一类型的路径做置乱,置乱周期随着Hilbert曲线阶数的增大而显著增大。如,对应H1和H’1变换路径,2×2的图像的变换周期为3,4×4的图像的变换周期为30,16×16的图像的变换周期为9240。对于一般的图像利用周期性对Hilbert置乱图像进行复原比使用逆变换的开销大得多。
3 基于密钥的Arnold-Hilbert组合变换
3.1 Arnold-Hilbert组合变换
组合变换是指在图像的置乱变换中,按某一顺序组合使用两种变换,以达到更好的置乱效果。如图5(a)所示为原始图像经过4次Arnold变换后的效果图;图5(b)为原始图像经过4次Hilber变换后的效果;图5(c)是经过2次Arnold变换和2次Hilbert变换后的效果。从图中可以明显看出,通过组合两种不同的变换,置乱后的图像随机性大大增强。同时,由于使用组合变换,在不知道变换顺序的情况下,很难对图像进行复原。
3.2密钥的定义
在本文中,密钥定义为对组合变换序列的表示。如果Arnold变换(A)用0表示,Hilbert变换(H)用1表示。那么一个变换序列A-A-H-A-H-H-H-A,就可以表示为一个二进制序列:00101110,进而可以表示为一个字符。反之,我们选择一个密钥,如:h2q,则对应的二进制序列为:01101000 00110010 01110001,则共进行10次Hilbert变换和14次Arnold变换。
3.3 实验结果
在进行图像的置乱操作之前,用户输入一个密钥,由系统把密钥转换成二进制串,然后根据二进制串各个位的值来判断是调用Arnold算法还是Hilbert算法。如,选择如上所述的密钥h2q,那么调用算法的序列为:A-H-H-A-H-A-A-A-A-A-H-H-A-A-H-A-A-H-H-H -A-A-A-H。实验效果如图6所示:
3.4 对基于密钥的Arnold-Hilbert置乱的破解
单纯使用Arnold或Hilbert变换对图像进行置乱,虽起到了掩盖图像真实内容的目的,但并不具备足够的抗攻击能力。攻击者在知道算法的情况下,可以轻而易举地复原出原图像。引入密钥以后,即使攻击者知道所使用的算法,但在不知道密钥的情况下,很难恢复出原图像。如果攻击者采用穷举密钥的方法进行攻击,则攻击的有效性与密钥的长度和强度相关。假设采用的密钥要求至少为8字符,则可能的密钥空间至少为264,假设有足够的计算资源来保证每微秒可以试探100万个密钥,至少需要约2600个小时测试完所有的密钥;而实际上随着被置乱图像的尺寸的增加,计算速度会明显减慢。如果所使用的密钥长度达到128比特(或16字符),则从理论上使用穷举的攻击方法是不可行的,因为试探所有密钥至少需要5.4×1018年。因此,引入密钥后的置乱算法,极大地提高了破解的难度,对于使用简单有空域变换进行快速的图像隐藏具有现实意义。
4 结论
利用Hilbert曲线、Arnold变换的图像置乱算法具有算法简单、实现速度快等优点,但由于使用的变换参数少,很容易被破解。通过引入密钥来结合两种算法使用,在保持其优点的同时,大大增加了破解难度,具有较高的实际应用价值。
参考文献
[1]Fabien A,P Petitcolas,Ross J Anderson,Markus G Kuhn.Information hiding-a survey[J].Proc.of IEEE,1999,87(7):1062-1078.
[2]Mitchell D Swanson,Mei Kobayashi,Ahmed H Tewfik.Multimedia data embedding and wa-termarking technologies[J].Proc.of the IEEE,1998,86(6):1064-1087.
[3]丁玮,闫伟齐,齐东旭.基于Arnold变换的数字图像置乱技术[J].计算机辅助设计与图形学学报,2001,(04).
[4]林雪辉;蔡利栋.基于Hilbert曲线的数字图像置乱方法研究[J].中国体视学与图像分析,2004,(04)