基于混沌映射的图像置乱算法

图形图像　／　基于混沌映射的图像置乱算法　方子毅　．　童卫青　（华东师范大学信息科学技术学院，上海２０００６２）　摘要：混沌映射具有对初始条件的敏感性、良好的随机性、相关性和复杂性等特性。基于此提　出了一种快速、安全的图像混沌置乱算法，实验表明，该算法达到了很好的效果。尤其在　大型图像数据库的应用中，该算法在保证安全性的前提下，能在极短的时间内对大量图　像进行置乱与恢复。　关键词：混沌映射；图像置乱；图像恢复　０引言　在大型图像数据库的实际应用中．图像置乱和恢　复的时间更是个至关重要的因素．如果因为过分强调　安全型，而没足够考虑效率的话．有可能使图像数据　库无法满足应用系统的要求　本文的出发点。即是在　保证安全性的同时．从置乱与恢复的时间角度考虑对　算法进行优化　其中Ｐ（　）是不依赖于初始值‰的，它对混沌系　统具有普遍适用性　（２）混沌序列轨迹点的均值：　ｉ＝　Ｒ（ｒ）　ｒ　１　＝』　印（　）ｄｘ＝０．５　（　）（‰　）　（３）　（３）自相关函数：　１混沌置乱算法　１．１混沌原理　混沌现象最早是由美国气象学家　ｒｅｎｚ　在研究　模拟天气预报时发现的　混沌是一种有界的内在的随　机过程，具有时间遍历性，这种过程既非周期性，又不　　１ｘｆ　（　（　）ｄｘ－０＝０　（４）　（４）互相关函数：　设两个序列的初始值ｘｏ，Ｙ。，则：　ｃ（ｒ）　ｆ　１　ｆ　１　收敛。任意相近的两点经过若干次混沌迭代之后。都　会呈现指数发散．所以很难预测混沌系统的初值和参　数。另外。混沌轨道极其不规则，经过系统局部扩展、　压缩、折叠之后，系统的输出类似于随机噪声。英国数　学家Ｍａｔｈｅｗｓ　Ｅｓｌ首先提出以Ｌｏｇｉｓｔｉｃ映射作为序列密　钥生成器．将混沌系统用于加密　Ｌｏｇｉｓｔｉｃ映射的定义为　Ｘｎ＋ｌ：￣：ＡＸｎ（１　）　（　）　Ｊ。Ｊ　０ｐ（　，．），）（ｘ－ｘ）ｆ　（ｙ－ｙ）ｄｘｄｙ＝Ｏ　（５）　Ｌｏｇｉｓｔｉｃ序列的遍历统计特性等同于零均值白噪　声，具有良好的随机性、相关性和复杂性，因此Ｌｏｇｉｓ—　ｔｉｃ混沌序列很适合应用于图像的置乱　１．２图像置乱算法　现以一８位ＢＭＰ图像为例．说明本文提出的图　现　其中３．５６９９４５６　≤４时　，Ｌｏｇｉｓｔｉｃ映射呈现混沌　状态，　∈（０，１）。混沌系统有如下几个特征：　（１）概率分布密度函数：　代　计　（１）生成混沌映射序列，接着对图像进行预处理，把每　算　行的奇数列像素灰度值减去相邻的偶数列像素灰度　机　像置乱和恢复算法的基本原理　图像置乱时先按照式　值．结果赋给奇数列像素，偶数列像素保持不变：再把　＾　ｊ　１０　＝．Ｘｎ∈（０。１）　（２）　Ｐｆ　）＝｛仃、／　（１—　）　Ｘｎ隹（０，１）　每个偶数列的奇数行像素灰度值减去同一列相邻的　偶数行像素灰度值．结果赋给奇数行像素．偶数行像　二　上　总　第　，、　收稿日期：２００７－０８－１７修稿日期：２００７—０９－０９　作者简介：方子毅（１９８４一），男，浙江奉化人，硕士，研究方向为数字图像处理　九　期　ＭＯＤＥＲＮ　ＣＯＭ　ＰＵＴＥＲ姗－ｌ０回　维普资讯 http://www.cqvip.com ＼＼＼＼　素保持不变。这样做的目的是通过相邻像素灰度值的　变化起到与像素位置移动同样的效果（在进行混沌映　射之前已经改变了图像７５％的像素点的灰度分布）。　最后把开始时生成的混沌序列映射到【０，２５５］后，分别　表异或操作）　｝ｅｎｄ　ｌｏｐｊ　截断的方式取整）　１　ｄ　ｌｏｏｐ　ｉ　（上述乘法的结果以　步骤３：　Ｆｏｒ　ｍ＝Ｏ　ｏ（ｔＭ－ｔ）／２｛　Ｆｏｒ　ｎ＝Ｏ　ｏｔ　—Ｉ　ｙ２　Ｉ　ｌ（２ｎ＋ｌ，２ｍ）＝ｌ（２ｎ＋ｌ，２ｍ）＋ｌ（２ｎ，　与每个像素的灰度值进行异或操作完成图像置乱。图　像恢复是图像置乱的逆过程．首先以同样的方式生成　混沌序列和进行灰度值的异或操作．只是在相邻像素　预处理这步．相邻像素灰度值执行的不是减法操作而　是加法操作。　下面以空间分辨率为ＭｘＮ的Ｐ位图像为例对算　法进行详尽阐述（Ｍ为宽，Ｎ为高）。　设图像像素点表示为Ｌ（ｉ√），其中ｉ－０，１，２，…，　Ｎ－１；ｊ＝０，１，２，…，　１。　ｗ＝０，１，２，…，ｐ１８—１。以下算法中对，（　√）的操作　就是依次对各个　的Ｌ（　Ｊ）的操作。　步骤１：任意指定在式（１）定义域内的初值　。和系　数　作为密钥，代入式（１）进行迭代，生成长为Ｍ＊Ｎ＊ｐ／　８的混沌映射序列ｘ　｛ｘｏ，ｘＩ，ｘ　一，　ｌ。　步骤２：　Ｆｏｒｉ＝Ｏｔｏ　Ｎ—ｌ　ｌ　Ｆｏｒ　ｍ＝Ｏ　ｔｏ（Ｍ－ｔ）／２　Ｉ　，２ｍ＋１）＝ｌ（ｉ，２ｍ＋ｔ）－Ｉ　２ｍｋ　ｌ　６２　不变　１ｅｎｄｌｏｏｐｍ　１ｅｎｄｌｏｏｐｉ　步骤３：　Ｆｏｒｍ＝Ｏｔｏ（Ｍ—Ｉｙ２、　Ｆｏｒ　ｎ＝Ｏ　ｔｏ（ｍ－ｔ）／２｛ｌ（２ｎ＋ｌ，２ｍ）＝ｌ（２ｎ＋ｌ，２ｍ）－Ｉ　ｆ２　２州｝Ｉ（２ｎ，２　不变　１ｅｎｄｌｏｏｐ　ｎ　１ｅｎｄｌｏｏｐｍ　步骤４：使用步骤１生成的序列‰对每个像素点　分别进行变换：　Ｆｏｒ　ｉ＝Ｏ　ｔｏ　Ｎ一１　ｌ　Ｆｏｒｊ＝Ｏ　ｏｔ　Ｍ—Ｉ　Ｉ　Ｉ　）＝Ｉ　０　（　２５５）　其中…代　表异或操作）　｝ｅｎｄ　ｌｏｐｊ　Ｊｅｎｄ　ｌｏｏｐ　Ｉ　（上述乘法的结果以截　现　代　断的方式取整）　计　１．３图像恢复算法　算　步骤１：按照置乱时选的初值　。和　系数作为密　机　钥，代入式（１）进行迭代，生成长为　木Ⅳ　，８的混沌映　＾　总　射序列戈　｛戈ｏ，戈１，戈　一，戈　８）。　第　步骤２：使用步骤１生成的序列‰对每个像素点　二　上　分别进行变换：　八　九　Ｆｏｒ／＝０ｔｏ　Ｎ—ｌ　ｌ　期　Ｆｏｒｊ＝ｏｔｏ　Ｍ—ｌ　Ｉ　Ｉ　Ｉ　＊２５５）　其中…代　＠ＭＯＤＥＲＮ　ＣＯＭＰＵＴＥＲ　２　１ｏ　２　Ｉ（２ｎ，２ｍＪ不变　Ｊｅｎｄｌｏｐ　ｎ　Ｊｅｎｄｌｏｐｍ　步骤４：　Ｆｏｒｉ＝Ｏｔｏ　Ｎ—ｌ　ｌ　Ｆｏｒ　ｍ＝Ｏ　ｏｔ（Ｍ—ｔ）／２　Ｉ　Ｉ　２ｍ＋Ｉ　２ｍ＋Ｉ　２ｍｋ　ｉ　２　不变　Ｊｅｎｄｌｏｐｍ　Ｊｅｎｄｌｏｐｉ　从以上算法的阐述中可见。此算法对于图像的置　乱和恢复是具有普遍适用性。　２实验与评价　通过对大量各种类型的图像进行了置乱测试，表　明置乱算法在效果、安全性和速度等方面都达到了令　人满意的效果。这里以典型的２４位色，２５６ｘ２５６的　ＬＥＮＡ图像为例（见图１）。图中的置乱密钥为：图１　（ｂ）　：４，　０＝０．７８。如果按照置乱时的系数和初始值　（相当于是密钥），进行恢复，结果和原图是完全一样　的，如图１（ｃ）所示。如果输入的密钥是错误的，即使　与正确密钥差距很小，也无法恢复图像。例如，图１　（ｄ）取ｇ＝４，ｘＯ＝Ｏ．７８０ｏ００００００００ｏ００１。　一■■■　（ａ）　（ｂ）　（ｃ）　（ｄ）　图１　Ｌｅｎａ图　由此可见．此算法的安全性很高，即使解密密钥　只与加密密钥有大约１＊ｅ－－１５的偏差．也完全无法恢　恢复始图像。　另外．此算法也达到了预期的快速的图像置乱与　恢复时间这一要求．对于６４０ｘ４８０的２４位图像（标准　ＶＧＡ视频图像）．此算法能达到每秒置乱１６０幅图像　左右的速度，平均６ｍｓ／图像，完全达到了视频要求。表　１是对几种典型空间分辨率的图像的置乱速度测试　数据：　维普资讯 http://www.cqvip.com

袁１图像置乱速度测试数据　参考文献　『１］Ｐｅｔｉｔｃｏｌａｓ　Ｆ　Ａ　Ｐ，Ａｎｄｅｒｓｏｎ　Ｒ　Ｊ，Ｋｕｈｎ　Ｍ　Ｇ．Ｉｎｆｏｒｍａｔｉｏｎ　Ｈｉｄｉｎｇ—ａ　Ｓｕｒｖｅｙ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ，１９９９，８７（７）：１０６２－１０７８　［２１Ｔ玮．闫伟齐，齐东旭．基于Ａｒｎｏｌｄ变换的数字图像置　乱技术．计算机辅助设计与图形学学报，２００１，１３（４）：　３３８～３４１　【３】林雪辉，蔡利栋．基于Ｈｉｌｂｅｒｔ曲线的数字图像置乱方法　此算法之所以能达到如此快的速度．是因为所有　的操作都是最基本的运算．例如加减法．异或等。唯一　研究．中国体视学与图像分析，２００４，９（４）：２２４～２２７　［４】胥亮，童卫青．基于仿射和流密码的图像置乱算法．现　代计算机，２０ｏ６，２３１（３）：８３～８５　占用大量时间的混沌映射序列的生成（因为有多项式　乘法和浮点数运算）。而在实际使用中，混沌映射序列　的生成这一耗时的操作是只做一次．大量图像置乱和　恢复时只需要使用序列生成的结果．对于每幅图像每　［５】顾勤龙，姚明海．基于Ｌｏｇｉｓｔｉｃ混沌序列的数字图像加密　研究．计算机工程与应用，２００３，２３：１１４～１１６　［６］Ｍｉｌａｎ　Ｓｏｎｋａ，Ｖａｃｌａｖ　Ｈｌａｖａｃ，Ｒｏｇｅｒ　Ｂｏｙｌｅ．Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　Ａｎａｌｙｓｉｓ。ａｎｄ　Ｍａｃｈｉｎｅ　Ｖｉｓｉｏｎ，ＳｅＣＯｎｄ　Ｅｄｉｔｉｏｎ．北京：人民　次要做的只是简单的像素移位和与混沌序列异或。　３结语　本文提出了一种基于Ｌｏｇｉｓｔｉｃ混沌映射的图像置　乱算法，本算法具有速度快、安全性高的特点。在实际　的大型图像数据库使用中．此算法起到了良好的效　果．既保证了图像的安全。又能在极短的时间内对大　邮电出版社，２０ｏ２，１：４１４～４１７　【７］ＬＯＲＥＮＺ［Ｅ　Ｎ】．混沌的本质．北京：气象出版社，１９９７，１：　附录１　【８１Ｒ．Ｍ　ｄ　ＨＥＷＳ．Ｏｎ　ｔｈｅ　Ｄｅｒｉｖａｔｉｏｎ　ｏｆ　ａ　Ｃｈａｏｔｉｃ　Ｅｎｃｒｙｐｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ．Ｃｒｙｐｔｏｇｉａ，１９８９，１３　）：２９－４２　量图像进行置乱和恢复。　Ｉｍａｇｅ　Ｓｃｒａｍｂｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｃｈａｏｓ　Ｍａｐｐｉｎｇ　ＦＡＮＧ　Ｚｉ－ｙｉ　，ＴＯＮＧ　Ｗｅｉ－ｑｉｎｇ　（Ｉｎｆｏｒｍａｔｉｏｎ，Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｄｅｐａｒｔｍｅｎｔ，Ｅａｓｔ　Ｃｈｉｎａ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０００６２）　现　Ａｂｓｔｒａｃｔ：Ｃｈａｏｓ　ｍａｐｐｉｎｇ　ｉｓ　ｓｅｎｓｉｔｉｖｅ　ｔｏ　ｔｈｅ　ｉｎｉｔｉａｌ　ｃｏｎｄｉｔｉｏｎ，ｒａｎｄｏｍ，ｃｏｒｒｅｌａｔｉｖｅ　ａｎｄ　ｃｏｍｐｌｅｘ．Ｂａｓｅｄ　ｏｎ　ｔｈａｔ，ｐｒｅｓｅｎｔｓ　ａ　ｒａｐｉｄ　ａｎｄ　ｓａｆｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｉｍａｇｅ　ｓｃｒａｍｂｌｉｎｇ　ｗｈｉｃｈ　ｈａｓ　ｓａｔｉｓｆｙｉｎｇ　ｅｆｆｅｃｔ．　Ｅｓｐｅｃｉａｌｌｙ，ｉｎ　ｔｈｅ　ｉｍａｇｅ　ｄａｔａｂａｓｅ　ａｐｐｌｉｃａｔｉｏｎ，ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｓｃｒａｍｂｌｅ　ａｎｄ　ｕｎｓｃｒａｍｂｌｅ　ｍａｎｙ　ｉｍａｇｅｓ　ｉｎ　ｓｈｏｒｔ　ｔｉｍｅ．　代　计　算　机　＾　总　Ｋｅｙｗｏｒｄｓ：Ｃｈａｏｓ　Ｍａｐｐｉｎｇ；Ｉｍａｇｅ　Ｓｃｒａｍｂｌｉｎｇ；Ｉｍａｇｅ　Ｕｎｓｃｒａｍｂｌｉｎｇ　第　二　上　八　九　期　、，　ＭＯＤＥＲＮ　ＣＯＭＰＵＴＥＲ　２ｏ０７－ｌ０回