一种基于LU分解和置乱的脆弱水印算法

纪老平

(山西警察学院刑事科学技术系，山西太原030006)

一种基于LU分解和置乱的脆弱水印算法

纪老平

(山西警察学院刑事科学技术系，山西太原030006)

信息技术和网络技术的迅猛发展使人类的生产和生活产生了巨大的变化，比如在数字多媒体信息方面，数字信息的存储、复制和传播变得容易和便捷。这给我们带来便利的同时也提出了挑战，例如在数字信息的版权保护和真实性、完整性鉴定方面，我们面临严重的问题。为解决上述问题提出了一种新的技术——数字水印。本文给出了一种用于数字图像完整性认证的脆弱水印算法：基于矩阵的LU分解和Arnold置乱变换的脆弱水印算法。该算法采用空间域的LSB嵌入算法，具有灵敏度高、透明性好、抗攻击能力强等优点。

数字水印；置乱技术；LU分解

信息技术和网络技术的飞速发展使人类的生产和生活发生了巨大的变化，多媒体技术越来越深入到我们的生活，给我们带来便利的同时也带来了很多问题。多媒体信息在传播和使用的过程中很容易被有意的或无意的篡改、破坏或复制等。因此，对数字信息产品的版权保护和内容真实性、完整性的认定成为了目前多媒体信息处理领域的一个重要问题。为了解决上述问题，数字水印技术被提了出来。

数字水印是以可感知或不可感知的形式，利用数字内嵌的方式隐藏到数字产品中的数字信号，可以是图像、文字、符号、数字、音频等一切可以作为标记、标识的信息，用于证实数字产品的版权归属和保证数字产品的真实性和完整性。[1]根据鲁棒性的不同，数字水印可以分为鲁棒性水印和脆弱水印，脆弱水印又可以分为半脆弱水印和完全脆弱水印。[2]虽然大多数的学者都致力于研究鲁棒性水印和半脆弱水印。但在某些特殊领域中，例如在国家安全、军事、医学图像、法庭物证等领域中，信息微小的变化都可能引发严重的后果，因此我们希望图像是完全完整，没有经过任何改动的。在这些领域中，必须要用到完全脆弱水印。对于应用于精确认证的脆弱性数字水印，灵敏度是个极其重要的考查指标，就是只要原始图像发生了变化，水印就一定要反映出来。一般来讲，变换域水印的鲁棒性较好，而空间域水印的灵敏度更高，由此，本文提出的是采用空间域方法的一种完全脆弱水印算法。

1 置乱技术

所谓的“置乱技术”，就是利用某种算法将图像信息的次序打乱，使其变换成杂乱无章难以辨认的图像。[3]置乱以后的图像没有纹理和形状特征。置乱实际上就是一种加密技术，但与一般加密技术相比，置乱具有安全性高、嵌入可见性好、抗攻击能力强等优点。数字图像的置乱变换是可逆的，置乱的方法很多，假如不知道置乱的方法是是什么，就很难恢复原始图像。

置乱技术在数字水印中的应用是：先对水印信息进行置乱处理，然后将置乱后的水印信息嵌入到宿主图像中，检测水印时，先提取出水印信息，再进行对应的反置乱变换即可。这样水印信息的安全性较强。现在有很多的置乱方法，其中Arnold变换算法简单，容易实现，本文采用Arnold变换对水印信息进行置乱处理。

1.1 Arnold变换基本原理

Arnold变换定义为：[4]

上述公式中，（X,Y）表示像素的原始位置，(X′,Y′)表示经过置乱以后像素新的位置。Arnold变换实质就是点的位置的移动。当图像中所有点的位置都发生了一次移动，整个图像就完成了一次Arnold变换。

Arnold变换的逆变换公式为:

我们可以将一幅数字图像看成一个矩阵，矩阵元素的值就是图像中点的灰度值（灰度图像）或是RGB颜色分量值（彩色图像）。数字图像的置乱变换，就是对图像中点的灰度值进行移动，只要经过一次Arnold置乱，图像就与原始图像不同。Arnold变换是可以迭代进行的，经过若干次Arnold变换后，图像就会变得面目全非，与原始图像完全不同。

1.2 Arnold变换的周期性

Arnold变换有一个特点就是具有周期性，即点在经过多次的移动后又回到了原来的位置。对于任意的正整数N，当N＞2时，周期M满足:M≤N2/2。[5]

2 矩阵的LU分解

从矩阵论的角度来看，我们可以把一幅灰度图像看成一个非负矩阵，将此矩阵记为B。矩阵的LU分解是指:对任何一个方阵B可表示成一个下三角矩阵L和一个上三角矩阵U的乘积:B=L*U。

在这里我们要求灰度图像的长和宽相等，若灰度图像的长和宽不相等，可将其扩展为方阵，嵌入算法一样可以适用。[6]

3 基于LU分解和置乱变换的脆弱水印嵌入算法

水印嵌入算法的关键步骤是:先对像素矩阵划分图像块，对划分好的每一图像块进行LU分解后求水印值，然后用Arnold置乱变换后交叉嵌入水印信息。其具体步骤如下:

（1）读入并打开图片文件。

（2）对像素值矩阵划分图像块。

（3）对每一个图像块分别进行处理。分三步进行，即嵌入位置的确定；调整嵌入位置的元素值；求该图像块的水印值。

（4）交叉嵌入水印信息。

4 嵌入算法的实现

4.1 像素值矩阵图像块的划分

在大多数的图像处理算法中，对图像进行分块时一般都选取8*8像素大小作为一个分块。在本文中，也采用这种分块方法。当像素矩阵的行列数不是8的倍数时，分块后会有余数，我们将余数与离其最近的像素块合并为一个像素块。那也就意味着不是所有的像素块都是8*8，通过计算可以得出，最大的像素块是右下角的那个分块，大小为15*15。

4.2 嵌入位置的确定

在每个划分好的图像块内，比较四个顶点的值，从中选择最大的一个。最大值可能不只一个，我们可以按左上、左下、右上、右下的顺序来进行比较，其中第一个遇到的最大值为最大值。

最大值的位置可能是以下所列的其一:

（1）左上。则选择以该图像块矩阵内(2，2)元素为水印信息嵌入5*5矩阵的左上角；

（2）左下，则选择以该图像块矩阵内(m-1，2)即(7，2)元素为水印信息嵌入5*5矩阵的左下角；

（3）右上。则选择以该图像块矩阵内(2，n-1)即(2，7)元素为水印信息嵌入5*5矩阵的右上角；

（4）右下，则选择以该图像块矩阵内(m-l，n-1)即(7，7)元素为水印信息嵌入5*5矩阵的右下角。

本算法是一种空间域方法，水印信息被嵌入到所选位置的LSB中。嵌入水印之前，需要把选定的5×5方阵的25个元素的LSB都清空，置为0。

在水印检测时，还需要比较判断四个顶点的大小，因此，四个顶点不能被清空置0，也即四个顶点的元素值必须保持不变，不能作为水印的嵌入位置。

4.3 嵌入水印值的计算

（1）对每一图像块矩阵进行LU分解。

（2）求分解后的U矩阵的迹，作为该图像块的水印值。

（3）将该水印值化为二进制。

通过图像块的划分方法我们可以知道，最大的图像分块为15*15。灰度图像中，点的像素值都在0～255之间。通过实验证明，这样的图像分块计算出的水印值不会超过25位，不够25位的在高位用0补足。

4.4 水印值的嵌入

先把所有图像块按照公式进行Arnold置乱，再将25位的二进制水印值排成5*5的方阵，嵌入到对应的图像块中：即若置乱后图像某图像块为p，即将p图像块计算得到的水印值，嵌入到原始图像中对应p位置的图像块q中。

进行置乱变换，可以有效的提高算法抵抗“伪认证”攻击的能力。如果不进行置乱变换，那么每个图像块嵌入的水印就是其自身求出的水印值，每个图像块都是独立的，这样也可以实现对篡改的定位，但不能抵抗拼贴，即攻击者用一个伪造的图像块来替换图像中的某个图像块，并用水印的嵌入算法伪造了水印，但图像仍然能通过认证。使用置乱技术以后，每个图像块嵌入的是别的图像块求出的水印，这就增强了各图像块间的依赖性，可以有效的抵抗拼贴攻击。

5 水印检测算法及注意事项

1）算法

水印检测算法的步骤与嵌入算法是相对应的，其基本步骤如下:

（1）读入并打开被检测图片文件。

（2）对像素值矩阵划分图像块。

（3）对所有的图像块都进行如下操作：根据嵌入水印的位置取出图像块嵌入的水印值；求图像块自身的水印值，作为待检测水印值。

（4）根据Arnold置乱的逆变换，计算每一个图像块的原始水印值。

（5）对每一图像块进行篡改检测判断。

（6）生成检测结果图。

在检测算法中，图像块的划分、嵌入水印位置的确定、矩阵的LU分解和求U矩阵的迹等操作和嵌入算法的方法是一致的，在这里就不再做详细的论述，需要注意以下几点。

2）已嵌入水印信息的提取

在每个图像块内，按照和嵌入时一样的方法确定嵌入水印的位置，将选定的5*5方阵中的25个元素的LSB值依次取出，构成一个25的二进制数值，然后将此二进制数化为十进制，该十进制数即为该图像块的嵌入水印值。

3）待检测图像块水印值的计算

待检测水印值的算法与嵌入算法中求水印值的方法是一致的，其求解过程如下:

（1）将选定的5*5方阵的元素值强制偶化，即清空最低位值，使得此25位的最低都为0。

（2）对视窗矩阵进行LU分解。求分解后的U矩阵的迹，作为该图像块的水印值。

4）图像块的原始水印值计算

我们在嵌入水印的过程中为了增强算法的安全性，采用了置乱技术。每个图像块嵌入的水印值不是自身的水印值。所以需要再根据嵌入水印时的Arnold置乱的逆变换，将嵌入水印值重新调整顺序，得到每一个图像块的原始水印值。

5）图像块篡改判定

循环依次比较每一个图像块的原始水印值和待检测水印值，如果此二值相等，那么该图像块就没有被篡改；如果这两个值不相等，则该图像块已被篡改。用此算法不仅能检测出是否被篡改，还能对篡改进行准确定位。

6)生成检测结果图

为了能清晰直观地看到水印检测的结果，可以在算法的最后一步生成一个检测结果图。检测结果图只有黑色和白色两种颜色构成，其中白色表示该区域没有被篡改，黑色来标记已被篡改的地方，其具体操作步骤如下:

（1）创建一个检测结果图像，要求与待检测图像一样大小。

（2）对创建的检测结果图划分图像块，划分的方法与待检测图像的一样。

（3）对检测结果图的像素值进行设置。

（a）如果图像块没有被篡改，就将检测结果图的对应位置标记为白色，即其像素值为255;

（b）如果图像块被篡改，就将检测结果图的对应位置标记为黑色，即其像素值为0。[7]

6 数字水印存在的问题

数字水印技术作为一种新技术，目前还处在研究阶段，尚未成熟，还存在许多问题需要深入细致的研究：

（1）数字水印算法的研究。许多水印算法倾向于提取与图像内容相关的信息作为嵌入内容，但是在应该提取图像的什么特征上、生成的水印长度和原始图像的匹配问题上和嵌入水印后如何不引起原始图像不发生变化等方面，还需要深入研究。

（2）系统的安全性。一个好的认证系统，除了要有好的算法，还需要安全有效的协议。为了提高认证系统的实用性，应结合密码学和数字签名技术。

（3）图像认证技术和图像压缩技术的结合。数字信息在存储和传输中大多会进行压缩，在压缩的过程中，如何使水印不发生变化是一个问题。当前也有专门针对JEPG压缩的认证水印算法，但是还是非常很少。

（4）音频、视频水印技术的研究。目前，静态图像水印技术正在迅速发展，但在视频、音频领域的水印技术发展还比较缓慢，还有待于进一步的加强研究。

（5）数字水印的严重缺陷。在嵌入水印的过程中，不可避免的会改变原始的数字作品。而在某些应用中，是不允许对原始图像进行任何的改动，例如医学图像、法庭物证。因此，在这些应用方面，嵌入的水印必须能够完全被去除。

（6）评测标准的建立。目前，认证水印还没有统一的标准，无法对认证系统进行比较和评价。

[1]金国华.基于小波和混沌的数字水印算法研究[D].大连:大连海事大学,2006.

[2]江林升.基于数字水印技术的图片内容认证实现[J].福建电脑，2008（2）:15.

[3]郑秋梅，顾国民,王玉菲,等.一种新的抗几何攻击的数字算法[J].中国石油大学学报(自然科学版),2012(1):188-192.

[4]金聪.数字水印理论与技术[M].北京：清华大学出版社，2008：130-13.

[5]徐德海.基于图像内容认证的数字水印技术研究[D].武汉：华中师范大学，2008.

[6]胡云，赵辉.一种基于LU分解的脆弱水印算法[J].电视技术，2003（8）：67-69.

[7]田佳卉.数字水印算法研究及其在公安图像处理系统中的应用[D].大连:大连海事大学，2005.

A Fragile Watermarking Algorithm Based on Lu Decomposition and Scrambling

JI Lao-ping
(Department of Criminal Science and Techmology,Shanxi Police Academy,Taiyuan Shanxi,030006)

With the rapid development of information technology and network technology,great changes have taken place in people's production and life.For example,in the aspect of multimedia information,it is very easy to be stored,copied and distributed.This brings us convenience as well as challenges.In the field of copyright protection and authenticity and integrity of digital information,we face serious challenges.In this paper,a fragile watermarking algorithm for digital image integrity identification is proposed.That is a fragile watermarking algorithm based on matrix LU decomposition and Arnold scrambling.The algorithm uses the spatial domain LSB embedding algorithm,which has the advantages of high sensitivity,good transparency and strong anti attack ability.

digital watermarking;scrambling technology;LU decomposition

TP751

A

〔责任编辑 高海〕

1674-0874(2017)04-0014-03

2017-04-26

纪老平（1974-），女，山西天镇人，硕士，讲师，研究方向:图像处理。