基于LASSO的可逆图像水印算法

郑鸿昌，王春桃，王俊祥

(1.华南农业大学 数学与信息学院，广州 510642； 2.景德镇陶瓷大学 机械电子工程学院，江西 景德镇 333403)(*通信作者电子邮箱wangct@scau.edu.cn)

0 引言

数字水印是保护信息安全、实现防伪溯源及版权保护的有效办法，是信息隐藏技术研究领域的重要分支和研究方向。美中不足的是，数字水印技术在嵌入水印的同时会给原始载体带来不可擦除的失真。为了在解码端得到嵌入数据的同时将原始载体也无失真地恢复出来，一些学者提出了可逆水印技术。可逆水印技术也称为无损水印技术、可翻转水印技术或者可擦除水印技术。该技术最早由Honsinger在2001年的一项美国专利中提出[1]，此后得到了广泛的研究。可逆水印作为数字水印技术的一个重要分支，在带宽受限系统、医疗领域、军事领域能发挥出其他数字水印无法替代的功能[2]。

可逆水印的主要目标是在无误提取水印信息及无损重构原图像的基础上，以更小的失真获得更大的嵌入容量。事实上，嵌入的数据越多，失真就越大，因此这两个目标实际上是相互矛盾的。为了解决这一问题，众多研究人员提出了各种各样的算法。这些算法大致可以分为三类：最低位平面(Least Significant Bits, LSBs)无损压缩的可逆水印[3-4]、基于差值扩展的可逆水印[5-11]和基于预测误差的直方图平移可逆水印[12-25]。

对于最低位平面无损压缩的可逆水印算法，其主要思路就是将图像最低位平面的数据提取出来，然后进行压缩以腾出空间来隐藏数据[3]。Celek等[4]进一步对这种思路进行了推广，将图像的若干个最低有效位平面提取出来后进行压缩，并用压缩后的LSBs以及待嵌入数据对原图像的LSBs进行替换。此类可逆水印算法实现起来比较简单，但是由于图像像素的分布并不规律，因此图像的数据压缩率不高，水印的嵌入容量有限。

基于差值扩展的可逆水印算法最先由Tian[5]提出。该算法将图像分为很多像素对，对于每个像素对，先计算出它们的平均值以及差值，并将需要嵌入的数据放到差值的最低有效位。如果根据新的差值计算出的像素值没有产生溢出则将1位数据嵌入到这一像素对中。因此，该算法的最大嵌入容量为0.5位/像素。由于Tian提出的差值扩展算法能够以较小的失真实现较大的嵌入容量，因此得到了众多研究人员的广泛研究，并提出了多种改进算法[6-11]。例如，为了压缩位置图的大小，Alattar将嵌入单元的像素个数从2个增加到了3个[6]和4个[7]，并在每个嵌入单元中分别嵌入3个和4个信息位，这样嵌入单元的数目大幅减少，使得压缩前的位置图也大幅缩小。文献[8]中，Kamstra和Heijmans对嵌入单元进行排序，以提高位置图的压缩效率。程淼[9]提出了一种预测误差重叠嵌入算法，在逐行嵌入数据的过程中，利用当前像素左方与上方的像素作为当前像素的上下文来进行菱形预测。吴万琴等[10]提出了一种基于邻域像素差值的算法，通过计算邻域像素差值的绝对值来决定是否嵌入水印，以确保较小的图像失真。此外，文献[11]中通过加入一个快速查找表来提高水印嵌入速度。

第三类可逆水印算法是基于预测误差的直方图平移可逆水印算法[12-22]。该算法最初由Thodi提出，能够在同等失真时嵌入更大的容量。对于某一像素，该算法用其周围的像素值来较为准确地预测该像素值，并将真实值减去预测值而得到预测误差。随后，利用预测误差构造统计直方图，进而将直方图零点为中心的区域对应的像素作为待嵌入系数，并用差值扩展方法进行信息嵌入；对于直方图中的其余预测误差则进行平移，以便接收端能正确识别出哪些像素嵌入了信息。由于其良好的率失真性能，后来又有很多研究人员对直方图平移算法进行了改进[13-16]。李可[13]通过将自适应嵌入方式与直方图平移技术结合起来使用，将图像分为平滑区域与粗糙区域，在平滑区域的像素嵌入2比特数据，而粗糙区域的像素嵌入1比特的数据，减小了像素值的最大修改量，进而在提高嵌入容量的同时有效减小了图像的失真。李建伟等[14]通过选择交错平移直方图以控制差值移动的个数,利用直方图零点对直方图进行分段以减小在创造嵌入空间时直方图平移的位移量,并提出了一种与直方图平移技术相适应并随负载变化压缩尺寸的溢出位置图。熊志勇等提出了基于双直方图[15]、三直方图平移[16]的彩色图像可逆数据隐藏算法。Qi等[17]提出了一个通过分析彩色图像中不同颜色分量的相关性来对像素进行预测，然后得出预测误差来进行信息嵌入的算法。此外，Vinoth等[18]提出了基于局部预测的医学图像可逆水印算法。该算法把图像分为多个互不重合的块，块边缘的像素使用中值边缘检测预测器(Median Edge Detection predictor，MED)，其他像素则使用局部预测来对像素进行预测。Panyindee[19]提出了一个基于二次嵌入测试的CT图像可逆水印方案。他们先把图像分为两个相互独立的集合，对每一个像素进行两次水印嵌入测试，把它们分为三类，并用不同的方法进行水印嵌入。

由于第三类算法的良好率失真性能，这一类算法得到了广泛的研究，是目前可逆数字水印研究的主要研究方向。对于这一类算法，其性能很大程度上取决于直方图的分布，若直方图零点处的尖峰越高，则嵌入效果越好。因此，通过改进预测算法，将能减小预测误差，进而提高可逆水印算法的性能，为此，学者们提出了众多的预测器[20-25]。其中，Thodi等[20]使用MED来进行预测，即用当前像素的右边、下方及右下方三个像素来预测当前值。Wu等[21]使用梯度调整预测器(Gradient Adjusted Predictor，GAP)进行预测，即通过当前像素上方和左方的七个像素来预测当前像素。该预测器复杂性比MED高，但预测性能更好。Sachnev等[22]将图像分为两个相互独立的集合，分别对两个集合的像素采用菱形(即上下左右4个相邻像素)预测算法来计算预测误差，获得了良好的预测性能。近期，Dragoi等[23]提出了局部预测算法，它通过最小二乘方法计算出在以当前像素为中心的一定区域内的最优加权系数，并以此预测当前像素值。结果表明，此方法以增大计算法复杂度为基础较好地降低了预测误差，因此成为当前各类预测器中性能比较好的一个[24]。随后他们又将局部预测应用在一组像素中来降低计算的时间复杂度[25]。

虽然Dragoi等[23]提出的基于最小二乘方法的局部预测器取得了良好的预测性能，但该预测器在预测时并没有充分考虑图像中存在的边缘、纹理等特性。对于存在边缘、纹理等的局部区域，如果沿着边缘、纹理等方向进行预测，将有利于进一步提升预测性能。这是因为边缘、纹理等方向的像素值比较接近，用这些比较接近的像素值来进行预测，有利于获得更为准确的预测值；反之，若像最小二乘方法那样用该局部区域内的全部像素来进行预测，则容易因像素值之间差别比较大而导致预测准确度下降。这就意味着，对存在边缘、纹理等的局部区域进行预测时，在边缘、纹理方向上的加权系数应该较大，而在其他方向上的加权系数应该较小甚至为0。也就是说，局部预测用的加权系数应该具有一定的稀疏特性。根据这种特性，本文把图像像素的预测问题表征为在加权系数稀疏化约束下最小化预测误差的LASSO优化问题，并通过LASSO优化求解而提升预测准确度，进而降低预测误差。利用LASSO优化来表征图像像素的预测问题，有利于根据图像的局部特性自适应地找到图像的纹理、边缘等方向，从而有利于减少预测误差而提升可逆水印的性能。这与传统的、具有方向选择性(如MED、GAP等)的预测器形成较明显的对比，因为这些传统的方向选择性预测器需要通过强制分类来实现方向选择。

基于LASSO优化获得预测误差后，结合差值扩展-直方图平移方法，本文提出了一种基于LASSO的可逆图像水印算法。仿真实验表明，本文算法性能与基于最小二乘局部预测器的可逆水印算法[23]性能相当或更好。由于文献[23]中基于最小二乘的局部预测器是性能相对较好的一个预测器，因此实验结果表明了本文算法的有效性和可行性。

1 背景知识

1.1 直方图平移算法

设zi,j为像素xi,j经某种预测方式得到的预测值，则像素xi,j的预测误差为：

ei,j=xi,j-zi,j

(1)

若ei,j∈[Tn,Tp]，则尝试嵌入1位数据b(b=0,1)，其中Tn(Tn≤0)和Tp(Tp≥0)为预设的正负阈值。如果嵌入数据后的像素没有溢出(即超过像素值的正常范围)，则用新计算出的像素值替换原像素；否则保留原像素值，并利用位置图标记该像素因溢出而未进行任何处理。如果ei,j∉[Tn,Tp]，则对该像素进行平移；平移后的溢出处理方式与数据嵌入时的处理方式类似。综上，具体的嵌入方法为：

(2)

把嵌入数据或平移后的误差Ei,j加到预测值zi,j中，即可得到嵌入水印后的像素：

(3)

水印提取是水印嵌入的逆过程。首先按相同的预测方法获得Yi,j的预测值zi,j,然后两者相减得到预测误差Ei,j。若位置图表明像素Yi,j没有发生溢出，且Ei,j∈[2Tn,2Tp+1]，则Ei,j中嵌入有1位水印信息，通过模2得到原始水印信息，即:

b=Ei,jmod 2

(4)

否则，Ei,j为平移后的误差，无需从中提取水印信息。对相关的Ei,j进行逐一处理，即可提取嵌入端嵌入的水印信息。

在提取完水印后，尚需恢复原始图像。首先根据下式获得原始预测误差，即：

(5)

然后再根据下式还原出原像素值，即有:

(6)

在直方图平移法中，嵌入容量以及嵌入失真均可以通过阈值Tn和Tp来控制，因此阈值的选择很重要。此阈值可以通过预设的方法来确定，也可以根据嵌入容量自适应地确定。

1.2 LASSO模型

LASSO (Least Absolute Shrinkage and Selection Operator)[26]是一种回归分析方法，它于1996年由Robert Tibshirani首次提出。LASSO的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下，使残差平方和最小化，从而产生某些严格等于0的回归系数，得到解释力较强的模型。

设某样本包含N种情况，每一种情况由p个协变量的向量xi={xi,1,xi,2, …,xi,p} (i=1, 2, …,N)(如预测样本)和一个输出yi(如预测值)组成。LASSO的目标是找到一组系数v={v1,v2, …,vp}，满足下列的约束，即：

(7)

s.t. ‖v‖1≤t

(8)

则式(7)可以简化为：

(9)

其中，t′为与t类似的一个预设常量。

式(9)是一个约束优化问题，可以通过引入拉格朗日乘子λ而将其转变为非约束优化问题，即:

(10)

式(10)的优化问题，可以通过文献[27]中的方法进行求解。

2 本文算法

本章首先根据图像的特性把像素预测问题表征为基于LASSO的优化问题，然后给出水印嵌入和水印检测算法，本文算法的流程如图1所示。

图1 本文算法流程

2.1 结合图像特性的像素预测问题表征

尽管基于最小二乘法的局部预测器[23]能够相对准确地预测图像像素，但该预测器并没有充分考虑图像的边缘、纹理等内在结构特性。事实上，图像中存在着或多或少的边缘、纹理等区域。对这部分区域进行预测时，若沿边缘或纹理方向进行预测，当能获得更好的预测性能。这是因为边缘或纹理方向的像素值近似一致，利用近似一致的像素来进行线性加权预测，会比用差别比较大的像素进行线性加权预测的性能要好。此时，边缘或纹理方向的加权系数应具有较大的值，而其他方向的加权系数应该较小或近似为0。也就是说，加权系数应该具有一定的稀疏特性。鉴于此，可以把图像像素的预测问题表征为基于LASSO的优化问题，借助LASSO的优化求解就可以使得非边缘或纹理方向的系数减小甚至为0。把图像像素预测问题表征为基于LASSO的优化问题，有利于根据图像局部特征自适应地找到边缘、纹理等方向，进而有利于减小预测误差和提升可逆水印的性能，其自适应特性与传统的预测器形成较明显的对比。

设xi,j是图像I(u,v)的某一像素，以xi,j为中心的B×B块内的各像素简记为y=[x1,x2, …,xB×B]。注意，y中的xi,j需用它上下左右的平均值(即菱形预测值)来替代，以便嵌入端和接收端能够进行同步。对于B×B块内的任一像素xk(k=1, 2, …,B2)，由其邻域像素组成的预测上下文记为：

(11)

其中p>0为邻域像素的个数。例如，若采用xk的上下左右像素作为预测上下文，那么p=4。预测上下文的取法可以根据实际预测效果来确定。令预测上下文构成的矩阵为：

X={x1,x2,…,xB2}T

(12)

线性加权系数向量为：

v={v0,v1,…,vp}T

(13)

则结合图像特性的像素预测问题可以表征为如下的优化问题：

(14)

式(14)即是LASSO优化问题，利用文献[27]中的LASSO优化求解算法即可以进行求解，从而得到当前像素的最优加权系数vopt。把vopt代入式(1)中，即可计算出当前像素的预测误差，有:

ei,j=xi,j-Xvopt

(15)

2.2 水印嵌入

本文算法利用1.1节得到的预测误差构造直方图，并结合差值扩展-直方图平移方法实现水印的嵌入。水印嵌入流程具体描述如下：

1)产生嵌入信息：假设在给出的图像载体中嵌入长度为L的水印信息，则产生L位的伪随机序列m={m1,m2,…,mL}作为待嵌入的水印信息。此外，为便于接收端提取水印信息及恢复原图像，嵌入端需要将直方图平移法中的阈值Tn和Tp、预测块大小B、嵌入结束时的行列位置(xe,ye)作为边信息发送给接收端。对于阈值Tn和Tp,边信息中只需记录其数值而无须记录其符号，因为其符号可以通过记录顺序而确定，分别用7位来表示这两个阈值的数值；B用7位来表示；xe和ye分别用20位来表示。实际上，这些位数对应的数值范围足以满足现实需求。因此，所有这些边信息的总长为61位。为便于接收方提取这些边信息，本文将这些边信息存放于图像载体最后一行的最后61个像素的最低有效位(LSB)中。为了能无误地重构原图像，需要把这61个LSB作为额外信息mLSB附加到水印m的后面，然后就可以形成完整的待嵌入信息m′={m,mLSB}，一起嵌入到图像载体中。为便于描述，仍然将m′看作待嵌入的水印信息，尽管里面包含了边信息。

2)设置Tn和Tp：为尽可能减小嵌入失真，在开始嵌入水印前，设置直方图平移阈值Tn和Tp为0。

3)逐像素嵌入水印信息：从原始图像I(x,y)的第一个像素x1,1=I(1,1)开始，按照顺序逐个像素嵌入m′中的各位水印信息m′(q) (q=1, 2, …,L+61)。首先按照1.1节的方法求得当前像素xi,j的预测误差ei,j,然后按照式(2)嵌入水印信息或进行平移，接着根据式(3)获得嵌入水印信息或平移后的像素Yi,j。若Yi,j<0或者Yi,j>255,则由于水印信息的嵌入或平移操作而导致溢出，此像素不能用作水印信息的嵌入及平移，为此在下一个可嵌入单元里插入0作为标记，随后开始处理下一个像素。若0≤Yi,j≤|Tn|或者255-Tp≤Yi,j≤255，则在下一个可嵌入单元里嵌入1作为标记，否则直接处理下一像素。

4)调整阈值：重复步骤3，直到m′中的所有水印信息以及为防止溢出而额外插入的所有辅助信息嵌入为止。若在当前阈值Tn和Tp情况下，能够嵌入所有待嵌入信息，则跳到步骤5；若直到载体图像最后一行倒数第62个像素时，仍然无法嵌入所有这些比特信息，则要调整阈值。若Tn=Tp,则Tn=Tn-1否则，Tp=Tp+1。然后重复步骤3和4，直到所有需嵌入的信息嵌入为止。此时，记录最后一个进行嵌入或平移的像素的位置(xe,ye)。

5)嵌入边信息：完成上述的嵌入后，将参数Tn、Tp、B以及(xe,ye)转成二进制，获得总长为61位的二值序列。随后将这些二值序列用作水印解码的边信息，并将边信息替换载体图像最后一行最后61个像素的LSB位，实现边信息的嵌入。

完成上述的嵌入流程后，获得嵌入水印信息和边信息的图像Iw(x,y)。

2.3 水印解码

水印解码是水印嵌入的逆过程，具体流程为：

1)提取边信息：从接收到的水印图像Iw(x,y)最后一行的最后61个像素的LSB位中提取边信息，通过二进制到十进制的转换，获得嵌入时的相关参数Tn、Tp、B以及(xe,ye)。

2)逐像素解码：从带水印图像Iw(x,y)中位置为(xe,ye)的像素开始，至Iw(x,y)图像的Iw(1,1)像素(亦即原图像的第一个像素)为止，逐像素进行水印解码。首先利用1.1节的方法获得当前处理像素Yi,j的预测值Ei,j,然后利用1.1节的水印解码方法提取嵌入后的水印信息m′(q) (q=L+61, …, 2, 1)并恢复原始像素值xi,j。溢出检测与水印嵌入时的相似。即若0≤Yi,j≤|Tn|或者255-Tp≤Yi,j≤255，且前一个还原出的信息位为0，则此像素为由于溢出而未进行水印嵌入或平移操作的像素，因此令Yi,j=xi,j。若前一个还原的信息位为1，则此像素为平移后的像素，进行逆向平移即可恢复xi,j。

3)恢复最后61个像素的LSB位：完成水印解码后，从提取到的水印信息中获取原始载体最后61个像素的LSB位，并将其替换Iw(x,y)最后一行最后61个像素的LSB位，从而真正恢复原始图像。

3 实验仿真与分析

本章对本文算法的性能进行评估，以验证其可行性和有效性。下面首先给出本文算法的参数设置及测试图像，然后通过与文献[23]中基于最小二乘局部预测器的可逆水印算法进行比较来评估本文算法的性能。

3.1 测试图像及参数设置

本文主要使用USC-SIPI图像数据库[28]中512×512的灰度图像对本文算法进行性能评估。这些图像为具有不同纹理特性的图像，包括Splash、Tiffany、F16、Lake、Airplane以及House，如图2所示。

图2 六幅测试图

本文算法涉及的参数包括直方图平移阈值Tn和Tp、预测块大小B和预测上下文系数个数p。其中，Tn和Tp由嵌入算法根据图像特性和嵌入量大小自动确定；本文采用菱形预测器构造预测上下文向量xk,并用它得出当前像素xi,j的预测值zi,j,因此p确定为4。因此，需要预先设置的参数主要为B。对于这个参数，实验仿真时以大小为512×512的Tiffany图像为例，设置嵌入数据量为{2 000, 4 000, 6 000, 8 000, 10 000}，然后设置B为B={3, 5, 7, 9, 11, 13, 15, 17, 19}，评估不同B和嵌入数据量组合时的嵌入量——峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)性能。其中，PSNR的计算公式如下：

其中：Ei为第i个像素嵌入数据前后的差值，N为存储像素总数，n为深度(如灰度图像n=8)。PSNR的单位为dB，其值越大则失真越少。

表1给出了不同B和嵌入数据量组合时的嵌入量-PSNR性能。由表1可知，当预测块大小B取值为17时，各嵌入数据量时均能获得最好的PSNR值。因此，本文后续的实验仿真中设置B=17。

3.2 算法性能评估

鉴于本文的侧重点在于改进图像像素的预测器以减小预测误差，因此评估本文算法性能时，本节主要与同样侧重于预测器性能改进的、基于最小二乘局部预测器的可逆图像水印算法[23]进行比较。其中，基于最小二乘的局部预测器是当前预测性能较好的一种预测器，其他可逆水印技术(如排序等)可以相应地与本文算法的预测器结合起来，以提升水印算法的整体性能。以下将文献[23]中的算法记为L2。

实验仿真时，两种算法都对相同的测试图像嵌入相同容量的水印信息，然后比较两种算法的PSNR性能。其中，L2算法采用文献[23]中的设置，即用于最小二乘局部预测时的块大小为12。表2给出了针对图2各个测试图像的嵌入量-PSNR性能结果。

由表2可知，在嵌入数据量为2 000～4 000位时，本文算法对六幅测试图像的PSNR值均比L2高0.1 dB左右；当嵌入量大于4 000位时，本文算法与L2的性能相当。这表明了本文算法的可行性和有效性。因为在嵌入数据量较小时，本文基于LASSO优化的预测器能够比文献[23]中基于最小二乘的局部预测器预测得更加准确。这是因为采用由上至下、由左至右的方式逐像素嵌入同等较少量水印信息时，两种算法

的阈值Tn和Tp均设置为0仍足以嵌入所有水印信息；但本文基于LASSO优化的预测器能够比文献[23]中基于最小二乘的局部预测器预测得更加准确，从而使得本文利用更少量的像素即可嵌入同量的水印信息，进而减少平移像素的数量而获得更好的PSNR值。

另一方面，由于本文算法采用当前像素为中心的B×B块来进行预测，其中上半部分为已经嵌入或平移过后的像素，因此平移像素的数量减少，也意味着同一B×B块内的像素以及其对应的预测上下文X因嵌入而改动的像素更多。由于嵌入导致的像素改动量比平移导致的像素改动量大，因此相对于L2算法各像素的预测上下文，本文算法各像素的预测上下文偏离原始像素值的程度将随着嵌入数据量的增加而增大，使得基于LASSO的预测器准确性逐渐降低，从而最终导致性能比L2差。

进行像素预测时，L2算法能够经理论推导而得到预测系数的解析表达式，本文算法则需要通过数值优化方式获得最优预测系数，因此本文算法的计算复杂度将比L2的高。为了评估两种算法的计算时间，本文在具有2.50 GHz CPU和8 GB内存的个人电脑上进行仿真。这两种算法的平均预测时间见表2最后一列所示，其中的预测时间是对整幅图像所有像素进行预测所需的总时间。由表2最后一列可知，两种算法的平均嵌入时间总体较低，但本文算法的计算复杂度比L2的高。也就是说，本文算法以适当增加计算复杂度为代价而提升了本文算法的嵌入量-PSNR性能。

表1 Tiffany图像不同B值和嵌入数据量时的PSNR值 dB

表2 6幅图像不同嵌入数据量时的PSNR值与图像的平均预测时间 dB

4 结语

本文提出了一种基于LASSO的可逆图像水印算法。根据图像存在边缘、纹理方向的特点，将图像像素预测问题表征为基于LASSO的优化问题，并通过LASSO优化求解以提高预测的准确性，进而降低相应的预测误差。在获得预测误差后，结合差值扩展-直方图平移方法，设计了一种基于LASSO的可逆图像水印算法。实验仿真结果表明，本文算法在嵌入少量水印信息时比基于最小二乘局部预测器的可逆图像水印算法性能[23]要好，在水印信息量较大时性能相当。本文算法侧重于预测器性能的提升，后续的工作中可结合可逆水印的其他技术(如排序等)以进一步提升算法的整体性能。