随着数字内容的生成,存储和通信技术的进步,在过去的二十年里,数字信息的安全性问题受到了越来越多的关注。数字水印是用于篡改检测和数字内容保护的有效解决方案之一。由于能够精确地恢复数字载体以及提取出嵌入数据,可逆数字水印已经成为数据隐藏的一个重要分支,并已被应用于许多质量敏感的领域,如医学成像,遥感和军事。在现有的诸多可逆水印方案中,基于像素值排序(PVO)的可逆水印方案由于其块内像素的紧密相关性取得了在中低嵌入容量下的优异表现。在这种方法中,只有分块中像素最大和最小的像素点被预测和修改以嵌入数据,而像素值排序的不变保证了可逆性。此外,还测量了像素块的复杂度以实现嵌入单元的选择以提高性能。通过对现有相关方案的研究与学习,本文提出了一种基于梯度复杂度的像素值排序(PVO)可逆水印方案。该方案首先对图像进行预分块处理,将图像以两种不同大小的分块方案进行分块,分别计算大小两种分块的梯度复杂度,使用大尺寸分块的复杂度数据来对较小尺寸的分块进行辅助排序,优化嵌入顺序。然后通过计算各分块的梯度复杂度大小,来动态的选择不同的嵌入分块大小。梯度复杂度越低表示着该分块所处的区域越平滑,因此使用较小的分块来提高嵌入容量,位于较粗糙区域的分块则使用较大的分块来保证预测准确性,从而实现动态分块策略,更好的利用到图像的冗余信息。最后,通过构建预测精确度矩阵(PAM)来对不同嵌入容量下的最佳嵌入阈值组合进行迭代,大幅减少了算法的时间复杂度。本文提出的算法是针对灰度图像在中低嵌入量情况下的可逆水印算法。通过实验仿真验证了该算法在不同嵌入容量下,相比现有算法均有着明显的性能提升。同时通过对该算法和传统方案运行时间的统计分析,论证了提出的算法在时间复杂度上的优化,大幅减少了动态分块策略中阈值迭代的耗时。本文提出的算法对于在中低嵌入容量下的可逆水印算法的性能提升有着重要的意义。