1.1典型的鲁棒性水印算法
多年来，无数的研究者为提高水印的鲁棒性提出了各式各样的水印算法。根据嵌入域的不同，鲁棒性水印算法可分为基于空域、变换域和压缩域三大类算法。下面我们将通过一些经典算法的简要介绍来了解水印算法从早期的空域算法，到传统的变换域算法，再到今天最新的多尺度几何变换域的历程。最后，我们对最新的带有方向性的“稀疏”表示方法——多尺度几何分析方法从产生背景、逼近性能、优缺点和发展方向做了全面概述。
1.1.1空域算法
早期，人们的研究重点主要集中在时空域算法。这类算法的特点是将水印直接嵌入图像的纹理、边缘或是一个随机区域的像素中。其算法简单，实效性强。由于只是对空间像素值的修改，所以嵌入水印后的图像质量较高。但是空域算法的鲁棒性较差，水印很容易被压缩、滤波等操作破坏。后来，空域算法常常用于脆弱和半脆弱水印的研究，主要原因在于空域算法能够对攻击实现空间位置的定位。
典型的空域算法包括最低有效位（LSB）算法、基于统计特征算法和纹理块映射编码算法等。Tirkel等最早提出了基于LSB位平面的水印算法“Electronic Watermark”，一年后提出了改进版“A Digital Watermark”，它们也是最早的水印算法之一。作者在文中提出了两种算法，第一种方法通过修改LSB的位平面实现了水印的嵌入，第二种方法在LSB位平面的基础上利用了线性加性方法实现水印的嵌入。虽然第二种方法较第一种复杂，但鲁棒性稍好。但是由于两种方法都是采用的基于LSB位平面的方法，所以水印在压缩、滤波、几何变换等操作后很容易被破坏，不过这种方法在后来的研究中却常常被用于内容认证。鉴于LSB方法的鲁棒性较弱，文献提出了一种将水印嵌入最后几位MSB（最高有效位）平面中去的方法，这种方法后来也在内容认证中得到了广泛应用。另一类典型的算法——基于统计特征的空域算法。这类方法的思想是通过修改载体信息的统计特征达到嵌入水印的目的。常用的统计量有平均值、标准方差等。其中，又以Bender等人提出的Patchwork算法最为有名。该算法基于统计的数据，任意选择N对像素点，在增加一点的像素值的同时，相应降低另一点的像素值，通过这种调整来完成水印的嵌入。Patchwork算法不易被察觉，而且对于JPEG压缩和一些恶意攻击处理具有一定的抵抗力，但嵌入的信息量有限。另外，文档结构微调的算法也属于空域算法，其调整的方法包括文字特性调整、水平调整字距、垂直移动行距等。此类方法可以抵抗一些标准的文档操作，对于攻击者任意改变其文档的行距或者字间距，水印就可能遭到破坏，而且该算法一般仅适用于文档图像类。
空域算法各有特点，但总的来说鲁棒性较差，在版权保护应用中受到限制，为此，研究者提出了基于变换域和压缩域的算法。与空域算法相比，变换域算法具有诸多优点。一是鲁棒性更强，原因是水印通常嵌入视觉感知的重要区域，即图像的中频区域；二是压缩技术与频率域的结合使得压缩域算法更能抵抗有损压缩操作，诸如，H.261、JPEG与DCT的结合，JEPG2000、MPEG7与DCT的结合；三是某些变化域算法更能抵抗一些特别的几何操作，比如DFT对仿射变换具有鲁棒性。鉴于以上原因，变化域算法更能吸引研究者的兴趣。其基本思想是将水印嵌入变换后的系数中去，嵌入方法可以采用替换、量化、关系、自适应、扩频通信等手段。常用的频率域包括离散余弦变换域（DCT）、离散傅立叶变换域（DFT）、离散小波变换域（DWT）以及最新的一些多尺度几何变换域。最后，我们简要的介绍其他几种不太常用的域。
1.1.2变换域算法
离散余弦变换（DCT）是一种次最优的正交变换，其性能很接近具有MSE意义上的最佳性能的K.L变换（Karhunen.Loeve Transform）。它具有很强的能量集中特性和去相关性，大多数自然信号的大部分能量都集中在DCT变换后的低频部分，加之与JEPG压缩标准的结合，基于DCT的水印算法可以较好地抵抗JPEG压缩。1997年，Cox等人利用序列扩频技术和人类视觉特性首先提出了将随机水印叠加在载体的DCT变换后的视觉最重要的系数中，这个观点已经被人们广泛接受并应用到其他变换域算法中。后来，有人提出了分块DCT变换水印算法，首先将原图分为互不重叠的8×8或16×16的块，再将水印嵌入每个块的中频系数中。文献都采用了基于分块的DCT域算法，其具体嵌入方式分别是抖动调制量化（dither modulation）方法、利用直流系数和交流系数关系的方法、基于DCT系数的零树结构。
离散Fourier变换（DFT）是数字信号处理领域中另一个很重要的正交变换，它与DCT变换一样具有快速算法。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分，其物理意义是将信号从时间域（time domain）变换到频率域（frequency domain）。在数字水印领域，由于DFT是复数变换，在幅度和相位满足一定的条件下，水印可以通过修改幅度、相位或整个复系数来完成水印嵌入。其修改方式也不过是量化、关系、替换等等。另外结合人类视觉系统和扩频通信技术也是常常采用的方法之一。文献利用DFT系数中的相位分量比幅度分量更重要和角度调制比噪声调制更鲁棒的性质，Ruanaidh等人最先提出了基于DFT的相位调制的水印算法。实验证明，此算法对图像对比度增强操作具有较好的鲁棒性。但是，基于Fourier变换的数字水印算法的抗剪切操作的能力却不如空域算法，而且对JPEG压缩攻击也不具有较好的鲁棒性，并且计算复杂，而且逆变换需要图像插值，这会引起图像的失真，因此很难被实际运用。
1986年，S.Mallat和Y.Meyer提出了多分辨率分析的概念，统一了正交小波基的构造，使得小波分析理论有了突破性的进展。同时，在多分辨率理论分析基础上，S.Mallat给出了离散二维小波变换（DWT）的算法，即着名的Mallat算法，从此小波变换被广泛地应用到数字图像处理中。基于小波变换的水印算法有三大优点。
