一種基于LU分解和置亂的脆弱水印算法

紀老平

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

一種基于LU分解和置亂的脆弱水印算法

紀老平

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

信息技術和網絡技術的迅猛發展使人類的生產和生活產生了巨大的變化，比如在數字多媒體信息方面，數字信息的存儲、復制和傳播變得容易和便捷。這給我們帶來便利的同時也提出了挑戰，例如在數字信息的版權保護和真實性、完整性鑒定方面，我們面臨嚴重的問題。為解決上述問題提出了一種新的技術——數字水印。本文給出了一種用于數字圖像完整性認證的脆弱水印算法：基于矩陣的LU分解和Arnold置亂變換的脆弱水印算法。該算法采用空間域的LSB嵌入算法，具有靈敏度高、透明性好、抗攻擊能力強等優點。

數字水??；置亂技術；LU分解

信息技術和網絡技術的飛速發展使人類的生產和生活發生了巨大的變化，多媒體技術越來越深入到我們的生活，給我們帶來便利的同時也帶來了很多問題。多媒體信息在傳播和使用的過程中很容易被有意的或無意的篡改、破壞或復制等。因此，對數字信息產品的版權保護和內容真實性、完整性的認定成為了目前多媒體信息處理領域的一個重要問題。為了解決上述問題，數字水印技術被提了出來。

數字水印是以可感知或不可感知的形式，利用數字內嵌的方式隱藏到數字產品中的數字信號，可以是圖像、文字、符號、數字、音頻等一切可以作為標記、標識的信息，用于證實數字產品的版權歸屬和保證數字產品的真實性和完整性。[1]根據魯棒性的不同，數字水印可以分為魯棒性水印和脆弱水印，脆弱水印又可以分為半脆弱水印和完全脆弱水印。[2]雖然大多數的學者都致力于研究魯棒性水印和半脆弱水印。但在某些特殊領域中，例如在國家安全、軍事、醫學圖像、法庭物證等領域中，信息微小的變化都可能引發嚴重的后果，因此我們希望圖像是完全完整，沒有經過任何改動的。在這些領域中，必須要用到完全脆弱水印。對于應用于精確認證的脆弱性數字水印，靈敏度是個極其重要的考查指標，就是只要原始圖像發生了變化，水印就一定要反映出來。一般來講，變換域水印的魯棒性較好，而空間域水印的靈敏度更高，由此，本文提出的是采用空間域方法的一種完全脆弱水印算法。

1 置亂技術

所謂的“置亂技術”，就是利用某種算法將圖像信息的次序打亂，使其變換成雜亂無章難以辨認的圖像。[3]置亂以后的圖像沒有紋理和形狀特征。置亂實際上就是一種加密技術，但與一般加密技術相比，置亂具有安全性高、嵌入可見性好、抗攻擊能力強等優點。數字圖像的置亂變換是可逆的，置亂的方法很多，假如不知道置亂的方法是是什么，就很難恢復原始圖像。

置亂技術在數字水印中的應用是：先對水印信息進行置亂處理，然后將置亂后的水印信息嵌入到宿主圖像中，檢測水印時，先提取出水印信息，再進行對應的反置亂變換即可。這樣水印信息的安全性較強?，F在有很多的置亂方法，其中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

〔責任編輯 高?！?/p>

1674-0874(2017)04-0014-03

2017-04-26

紀老平（1974-），女，山西天鎮人，碩士，講師，研究方向:圖像處理。