12.4.2  利用Hilbert曲线置乱图像

Hilbert曲线是一种FASS曲线，即充满空间（space-filling）、非自交（self-avoiding）、自相似（self-similar）、简单（simple）曲线。这类曲线位于一个维数大于1的欧几里德空间中，并且在该空间内有一个非空的内部。意大利数学家Peano和德国数学家Hilbert分别于1890年和1891年给出了填满一个单位正方形S的FASS曲线，这类曲线都给出了利用一条连续曲线遍历整个单位正方形的方案。这就是所谓的Hilbert曲线，Hilbert曲线是一种分形曲线，如图12-6所示。

下面来讨论如何构造Hilbert曲线。Hilbert曲线的入口点和出口点决定了它的走向，也就决定了像素点的遍历顺序，因此根据Hilbert曲线的入口点和出口点的不同组合，可以把置乱路径分为8种类型，一阶Hilbert曲线路径如图12-7所示。图中首先将一个正方形均分为4个小正方形，并用一条线遍历4个小正方形。

把每种路径标上号。将每个小方形细分为4个小正方形，并选取一种路径，用这种路径去遍历细分出来的小正方形。在原图的第1个子图中将路径左旋90 ，并将走向反向；第2、3个子图与原路径相同；第4个子图中将路径右旋90 ，并将走向反向。按照这种规律不断细分下去，就得到了充满整个正方形的Hilbert曲线，如图12-8所示。

Hilbert曲线提供了一种遍历二维格点的方法，叫作Hilbert遍历。由于图像数据就是一个二维数组，因此我们可以利用Hilbert曲线来置乱图像。对一幅图像有8种遍历顺序，利用L系统的边改写与点改写规则，该曲线是很容易生成的。按照Hilbert曲线的走向遍历图像中的所有点，就可以生成一幅新的"杂乱"图像，这就是所谓的Hilbert曲线图像置乱方案的基本思想。这个过程可以重复多次而使得图像达到充分的混乱。

图12-9给出了一个利用Hilbert曲线对Lena图像进行置乱的示例，其中（a）为置乱前的Lena图像，（b）、（c）、（d）是分别对其进行1次、2次和3次置乱的结果。n阶Hilbert曲线填充的空间大小是长宽均为2n的正方形区域，这无疑存在一定的局限性。那么对于大小为   M×N（其中M ≠ N）的数字图像该如何处理呢？假设在m<n的情况下，有2m<M≤N<2n或2m<N≤M<2n，可采取的方法一是将图像数据矩阵补上（2n M）列、（2n N）行，选择某条n阶Hilbert置乱路径进行置乱；二是对图像左上角、右上角、左下角、右下角部分的2m×2m区域进行m阶Hilbert曲线置乱，如有必要还可以在中心2m×2m区域再做一次置乱处理。总之，使得图像的每一部分至少被置乱一次，解密则为其逆过程。

下面我们就来编程实现图像的Hilbert变换加密与解密。为了简化程序设计，这里仅考虑最基本的情况，即默认待处理的图像的宽和高相等。对于那些宽和高不等的情况，程序将截取其中的一个正方形部分进行处理。这里仍然以MagicHouse为基础进行开发。打开MagicHouse项目，并在其中添加一个对话框，如图12-10所示，该对话框将集Hilbert加/解密功能于一体。主程序菜单栏中的不同菜单项在调用该对话框时，通过传递一个布尔值来判断此时应选择启动加密过程还是解密过程。

为上述对话框创建一个类CDlgHilbert。基于Hilbert曲线的图像置乱算法的实现代码位于DlgHilbert.cpp文件中。该文件的完整源代码及项目中其他文件的代码清单请读者参看随书光盘，此处不再赘述。