一、差分擴展

數字水印已經逐漸成為了一種有效的版權保護手段，它通過嵌入幾乎不可感知的水印信號到圖像、音頻、視頻數據中來保護這些媒體文件的版權不被非法利用、來認證來源或者增強其價值。水印化前后的作品之間的失真通常在視覺上是不可感知。但在一些特殊場合，即使是這些無法被感知的失真也是不能容忍的。因此就出現了可逆水印，其要求不能能抽取出水印，還能夠無損的將水印化作品恢復成原來的作品。

早期的可逆水印算法都是基于算數模的加法擴頻水印算法；另一種可逆水印是對圖像的某些特征進行無損壓縮，然后將水印加入由壓縮所留出來的空間中以達到可逆的目的。而基于差分擴展的可逆水印是通過對一對像素值的差值進行擴展來進行可逆變換的水印算法。該算法的主體思想是對相鄰兩個像素值的差值進行擴展或變換形成新的像素對以達到水印嵌入的目的，然后再從新的像素對的差值反變換即可還原出原始圖像和嵌入的水印。為了保證不可察覺性和圖像的質量，該算法將所有的像素對分為可擴展的、可改變的及不可改變的這三種類型，其中可擴展的也一定是可改變的。而只有可擴展的和可改變的像素對可以用于數字水印的嵌入。該算法的特點在于通過利用相鄰兩個像素對的差在不需要增加存儲空間消耗的情況下，將數字水印的信息碼流不可察覺的嵌入到載體圖像中；然后在通過相似的方法將嵌入的信息碼流從載體圖像中提取出來并將載體圖像無損的恢復以達到完整和可逆的效果。

為了更好的理解差分擴展的變換和還原，這里我們舉個例子：假設有一對像素對(x, y)，其中x=206，y=201.我們想要嵌入的信息比特b=1.那么這個像素對的平均值l和差h為：

我們把b添加到到h的二進制表示1012的最低有效位(LSB)中得到了一個新差h’=10112=11.用數學表達為：

最后根據這個新差可以得到這個像素對的新值作為嵌入之后的像素值：

通過以上的這些步驟我們可以得到嵌入信息之后的像素對(x’, y’). 如果我們想要恢復原始的像素對和嵌入的信息，我們可以根據上述公式再次計算嵌入信息之后像素對的平均值l’和差h’：

根據上述公式得出的像素對差h’可以計算出嵌入的信息b及原始的像素對差：

從公式(4)中和公式(5)中得到的l’和h就能恢復出原始的像素對：

在這個例子中我們將信息比特b嵌入到像素對差h的最低有效位上使得h的位數從三位擴展到四位，這種可逆信息嵌入的操作就叫做差分擴展(DE).

二、可逆數據轉換及限制

從1中我們可以了解到差分擴展的一些基本操作，不難想到可以將這種操作擴展到可逆水印的算法中。對于一副8比特的灰度圖像來說，其所包含的像素對可以得出它們的平均值l和差h為：

其反變換為：

由于x,y的區間范圍是[0, 255]，因此我們有:

當使用差分擴展將一個信息比特b嵌入到差值h中時，新的、可被擴展的差值h’將變成：

為了避免像素對超出取值范圍，也即溢出，h’必須滿足以下條件:

滿足上述條件的像素對的差稱之為可擴展的，因為該像素對可以使用差分擴展進行信息的嵌入且不會導致數據的溢出。由此同時，我們也可以不對像素值的差進行差分擴展，而是改為對其最低有效位進行直接修改。通過將其最低有效位直接修改成信息比特也可以達到信息嵌入的目的。這時的新差h’為:

同時為了滿足嵌入之后的數據不發生溢出，h’也必須滿足以下條件:

滿足上述條件的像素對的差稱之為可改變的，因為該像素對可以使用直接修改的方法進行信息的嵌入且不會導致數據的溢出。不難得出，可拓展的和可改變的像素值的差經過差分擴展或者直接修改后其新差仍然是可修改的，并且可擴展的差值一定也是可改變的。因此我們可以得出以下差值h的分類:

• 可擴展的差值h：可以對其最低有效位進行差分擴展而不會導致數據溢出。其應該滿足：
  
• 可改變的差值h：可以對其最低有效位進行直接修改而不會導致數據溢出。其應該滿足：
  
• 不可改變的差值h：既不可擴展也不可改變的差值h.

圖1 差值h的分類

同時還可以發現當h=0或者-1時，可擴展條件和可改變條件是相同的。因此我們可以按照上述對差值h的分類將像素對分成四個集合：

• EZ：包含了差值h為0或-1的所有可擴展像素對。
• EN：包含了差值h不為0或者-1的所有可擴展像素對。
• CN：包含了不是可擴展像素對的所有可改變像素對。
• NC：包含了所有不可改變的像素對。

由上文可得EZ、EN、CN是可以嵌入信息的像素對，而NC是不可以嵌入信息的像素對。因此我們首先應該先將可嵌入信息的像素對找出來形成一個location map信息集。并且為了無損的恢復出原始圖像，我們也應該記錄下可改變差值的那些被直接修改掉的最低有效位信息并形成一個最低有效位信息集。Location map信息集(L)、最低有效位信息集(C)以及想要嵌入的數字水印payload(P)共同構成了信息流(B)一并嵌入到了載體圖像中完成了可逆水印的嵌入。為了保證數據被有效嵌入而不發生信息的溢出，其B的體積必須滿足:

三、信息的嵌入和提取

按照2所述的基于差分擴展的數字水印的知識，我們可以得到數據嵌入的步驟，該步驟如下所示：

1. 將原始載體圖像分成一個像素對集合，再對每個像素對求平均值l和差值h。
2. 將差值h按照分類規則進行分組并形成四個不同的子集EZ、EN、CN、NC集，其中EN集還可以再分成EN1集(可二次擴展)和EN2集(不可二次擴展)。
3. 根據差值h四個不同子集的狀態對圖像的位置進行標記并形成location map信息集，再對該信息集進行壓縮存儲成L比特流。
4. 提取可改變差值h的最低有效位形成最低有效位集，然后再進行壓縮儲存形成C比特流。
5. 對有效負載(數字水印)進行壓縮儲存形成P比特流。
6. 將L、C、P比特流進行合并形成B比特流并按照差值h的狀態進行差分擴展或修改LSB以完成數據嵌入。

這些數據嵌入的算法步驟的流程圖如下所示：

圖2 基于差分擴展的水印嵌入的流程圖

通過以上步驟我們可以將水印嵌入到載體圖像上。如果我們想要提取出水印和復原出原始的圖像，可以逆著上述步驟進行數據的提取即可得到水印和原始的圖像。因此，其提取數據的方法和步驟如下所示：

1. 將新圖像進行像素對分組并求新像素對的差值h’和平均值l.
2. 提取出差值h’的最低有效位形成B比特流并將L比特流分離出來。
3. 將L比特流進行解壓還原成location map數據集。
4. 根據location map對差值h’進行篩選并分離出C比特流和P比特流。
5. 將P比特流進行解壓縮后恢復出水印信息。
6. 將C比特流解壓后得到的最低有效數據集并根據location map將其最低有效數據恢復到最低有效位上去。
7. 根據差值h’和location map恢復出原始的差值h，再根據差值h和平均值l得到原始的像素對數據并恢復出原始圖像。

這些水印的提取和原始圖像的恢復步驟可以用以下流程圖表示(見圖3)：

圖3 基于差分擴展的水印提取的流程圖