魔方矩阵置乱算法分析

时间：2024-09-03

◆胡冰楠

(江西财经大学软件与通信工程学院江西 330013)

魔方矩阵置乱算法分析

◆胡冰楠

(江西财经大学软件与通信工程学院江西 330013)

本文分析对比了三种不同维数的魔方矩阵对图像置乱的效果及其NPCR参数。

魔方矩阵；双偶矩阵；单偶矩阵；奇数矩阵；NPCR

0 引言

魔方矩阵是一个古老的数学问题，原指一个方阵中的每行、每列和对角线之和均相等。通过魔方算法很好的把原先按顺序排列的矩阵元素混淆了。本文借助魔方矩阵的思想，通过将方阵的像素点序号值实现行、列、对角线之和均相等，从而达到置乱图像像素点的目的[1-2]。

魔方矩阵按矩阵维数分为3种，双偶矩阵、奇数矩阵和单偶矩阵。它们由于矩阵维数不同，加密算法与实现结果都有所不同。本文对比了三种不同魔方矩阵算法的置乱效果，并分析了NPCR。

1 双偶矩阵

双偶矩阵特指矩阵维数N能被4整除的矩阵，即N=4n(n为正整数)。这种维数的魔方矩阵是实现算法最简单的一种。由于维数的特殊性，所以只需要将对角线上的元素略做调整即可实现。由4×4的矩阵可以发现，魔方矩阵置乱后的矩阵中仅有50%的元素位置发生了改变。

当矩阵维数扩大到N=200时，经过位置改变比例分析，矩阵中仍然有50%的元素位置未发生改变。位置改变比例是用来判断置乱前后的两个矩阵在相同坐标上元素是否改变的参数，如果置乱效果足够好，位置改变比例的理论值应为 100%，即所有位置上的元素都发生了变化。

使用大小为200×200的Lena图像和白底带黑色方块的图像Block(黑色方块大小为 20×20，占图像面积的1/100)，双偶魔方矩阵置乱的图像与原始图像如图1所示。

图1 双偶魔方矩阵置乱

图1置乱结果表明，这种双偶魔方算法并不能使图像得到良好的置乱。

2 奇数矩阵

奇数矩阵是指矩阵维数N为奇数的魔方矩阵，即N=2n+1(n为正整数)。当 N=5时，变换后的方阵与原方阵相比，只有中心一点的值没有发生位置变换，其余的值均发生了很大的变动。

理论上，对于一个N维(N=2n+1)的奇数魔方矩阵，经过魔方矩阵置乱之后仅有 1/N2的像素点没有改变位置(即中心点)，其余(N2-1)/N2个像素点均改变了原始位置。对比图3两个矩阵，魔方矩阵相对于原矩阵的位置改变比例为96%；对于维数为215的魔方矩阵，即N=215，其位置改变比例为99.9978%，可以看出矩阵中几乎所有元素的位置都发生了变化。

使用大小均为215×215的Lena图像和Block图像(黑色方块大小为20×20)，使用奇数魔方矩阵置乱的图像与原始图像如图2所示。

图2 奇数魔方矩阵置乱

从图2(c)和(d)看出，图像已经实现置乱，但在其对角线方向具有明显的条纹。

3 单偶矩阵

单偶矩阵特指矩阵维数N能被2整除但不能被4整除的矩阵，即N=4n+2(n为正整数)。当N=6时，魔方矩阵和原始矩阵相比，100%的元素位置发生了改变。

理论上，N维单偶矩阵(N=4n+2)中总有 100%的元素位置发生变化。对比图5两个矩阵，魔方矩阵相对于原矩阵的位置改变比例为100%；对于维数为210的魔方矩阵，即N=210，其位置改变比例仍为100%。

使用大小均为210×210的Lena图像和Block图像(黑色方块大小为20×20)，单偶魔方矩阵置乱图像与原始图像如图3所示。

图3 单偶魔方矩阵置乱

图3(b)和(d)表明，单偶矩阵具有良好的置乱效果，经过单偶矩阵置乱的图像像素点几乎全部发生了位置变动。原始图像中处于中心的小黑方块经过单偶魔方矩阵置乱算法，被分散到整个图像中去，而且图像不具有明显的规律性和相关性。

4 置乱算法的性能分析

为了比较3种置乱算法的效果，使用3种分辨率的Lena图像，即200×200，210×210，215×215，分别计算采用双偶、奇数、单偶矩阵算法置乱后图像的像素值改变比例（NPCR），公式如（1）所示，M为矩阵维数，Sign(x)为符号函数，C1和 C2表示被比较的两个图像 C(i，j)表示图像矩阵的坐标。4种算法的NPCR由表1所示。

表1 置乱算法的NPCR

NPCR(99.6094%) Lena 49.3050% 99.3012% 99.4308%

由表1看出，双偶矩阵算法的置乱效果差，奇数矩阵和单偶矩阵算法置乱的NPCR参数接近理论值。