基于LSB的QR碼數字水印算法研究

朱本威, 萬武南, 陳 運

（成都信息工程學院信息安全研究所,四川成都 610225）

0 引言

快速響應矩陣碼（QR Code,QR碼[1]）是二維碼中的一種,具有信息容量大、可靠性高、高速全方位識讀等特點。QR碼被廣泛應用于電子票證、火車票驗證以及移動支付等領域,是當前防偽和保密技術的研究熱點之一。

目前,國內外關于二維碼信息隱藏技術的文獻不是很多,研究對象主要是四一七條碼（Portable Data File417,PDF417碼）和QR碼。在國內,針對PDF417碼的研究較多且以空域水印為主,在國外,以研究QR碼居多,以頻域水印為主。牛夏牧等[2]利用變形技術對PDF417碼中的各組成單元寬度加以適量的變動,采用誤差累積的方式實現隱藏信息的嵌入和提取。陳崢等[3]針對PDF417碼,提出了基于邊界移位的隱藏信息嵌入算法。趙博等[4]提出一種基于結構微調法的水印算法,對PDF417碼的組成條空進行適量的微調,將信息隱藏進二維碼中。晁玉海等[5]提出一種對隱藏信息進行擴頻和映射處理,根據PDF417碼自身結構特點,通過微調條碼中的條和空將信息隱藏的方法。Ming Sun等[6]提出兩種基于離散小波變換（Discrete Wavelet Transform,DWT）變換的QR碼數字水印,分別可以嵌入隨機序列和圖片。Jau-Ji Shen等[7]針對PDF417碼提出一種稱作關聯水印的盲水印算法,該算法可以提高水印的嵌入容量并可將PDF417碼用于數據認證。Vongpradhip S等[8]針對QR碼提出一種基于離散余弦變換（Discrete Cosine T ransform,DCT）變換的數字水印算法,可以將秘密信息隱藏于DCT域的中頻系數中。Suppat Rungraungsilp[9-10]針對QR碼,對比了在DCT域、DWT域和離散傅里葉變換（Discrete Fourier Transform,DFT）域上的數字水印算法優缺點。

總結起來,基于二維碼的數字水印可以分為空域水印和頻域水印。其中,空域水印的基本思想是對二維碼的深淺圖形模塊的邊緣像素進行擴展或者縮減,利用二維碼識別算法對深淺模塊圖形有一定的誤差允許,而不會影響到二維碼的正確識別的特點,實現秘密信息嵌入。頻域水印的基本思想是對二維碼圖像進行DCT、DWT或DFT域的變換處理后,修改不同頻的系數來嵌入水印。由于空域水印算法對二維碼的圖形結構進行了修改,而頻域水印會使二維碼圖像變得模糊不清,導致兩種算法都只適合用于打印的二維碼。當采用電子文件形式保存二維碼,或者二維碼圖像的清晰度很高并且信息容量低時,則這些算法并不太適合。

針對目前基于二維碼的空域數字水印算法的研究對象以PDF417碼為主,對QR碼的研究較少,并且以微調圖形結構的方法為主。文中將根據QR碼的結構特點,結合結構微調水印算法的基本思想,采用改進的最不重要位（Least Significant Bit,LSB）算法實現一種適合QR碼的脆弱數字水印算法。相對于基于圖形結構微調的算法,該算法嵌入的水印具有更好的隱蔽性,同時對QR碼的信息容量沒有要求,能夠解決目前嵌入水印的二維碼不適合以電子形式保存的問題。

1 基礎理論

1.1 QR碼

QR碼是由日本Denso公司于1994年9月研制的一種矩陣式二維碼符號,除具有一維條碼及其他二維碼所具有的信息容量大、可靠性高、可表示漢字及圖像等多種信息的優點以外,還具有高速全方位識讀、有效表示漢字等特點。圖1是一個版本號為2,糾錯等級為L的QR碼圖像。

1.2 改進的LSB算法

基于LSB嵌入秘密信息的方法是信息偽裝技術中最經典的一類方法,能夠較易的應用于圖像和語音文件中,只需要對載體文件做很小且不易被覺察的改變就能隱藏大量的秘密信息。

然而,傳統的LSB算法比較簡單,在信息隱藏技術領域被研究的比較透徹。在QR碼中,對LSB算法的直接使用并不一定能夠非常有效的提高水印嵌入的效果。

Jessica Fridrich[11]最早提出將矩陣編碼應用到基于LSB替換的信息偽裝系統中以提高水印的嵌入效率。蘇亞娟[12]提出一種空域信息的隱藏算法,將矩陣編碼引入空域水印算法中,有效提高水印嵌入效率。

使用矩陣編碼的LSB算法能夠做到在2k-1位LSB中只需要修改一位LSB,就可以表示一個k bit大小的數據。

對于計算機中的一張彩色圖像,其每一個像素點是由R（紅）、G（綠）、B（藍）3個分量組成,每個分量分別占用8 bit的數據大小,也就是說每個分量擁有256級灰階。根據LSB的思想,水印的嵌入位置選擇像素點RGB分量的最低位。那么,一個像素點就可以提供至少3位可替換的LSB,根據矩陣編碼思想,即表明一個像素點可以表示至少2 bit大小的信息。

QR碼圖像是一種二值圖,圖像中深色和淺色的模塊圖形,在實驗中用黑色和白色像素表示。如果對白色像素的LSB進行修改,一般情況下會引起明顯變化,為了減少人眼的對圖像發生的變化產生明顯的差異感,選擇修改黑色像素的LSB值。黑色像素的原始RGB值及修改最低位之后的RGB值如表1所示。

圖1 版本號是2的QR碼圖形

表1 黑色像素RGB分量的值

運用矩陣編碼的方式,設k=2,則2k-1=3,定義操作如下:

其中a1表示R的最低位,a2表示G的最低位,a3表示B的最低位,x1表示2 bit信息中的高一位,x2表示2 bit信息中的低一位。分別修改RGB 3個分量的LSB值,得到的計算結果如表2所示。

表2 RGB分量最低位的矩陣編碼結果

表3 黑色像素 RGB分量的矩陣編碼結果

從表2中可以看出,只需要修改像素RGB分量的3個最低位的其中一位,就可以嵌入1個2 bit大小的信息。針對QR碼圖像,需要修改黑色像素點的LSB值,黑色像素點的RGB值是#000000。于是,對黑色像素進行處理,得到的對應結果如表3,其中RGB分量用8位二進制表示,X1X 2表示得到的編碼信息。根據此表,在進行具體的水印嵌入操作時,根據水印信息,修改對應像素的RGB分量的最低位。反之,在進行具體的水印提取操作時,根據像素信息,得到對應像素的水印信息。

2 適用于QR碼的數字水印算法

2.1 水印嵌入算法

設QR碼的一個模塊圖形的大小為 M*M,其中M 為模塊的長度（高度）,單位是像素。每2 bit的水印信息嵌入的位置是QR碼圖形中除去位置探測圖形以外的若干個滿足下方是白色模塊圖形的黑色模塊圖形的下邊界像素,像素個數為n*M,n為連續模塊的個數,即表示通過修改 n*M 個像素的LSB值嵌入2 bit信息,如圖2所示,左邊是含有水印的QR碼,右邊是水印嵌入位置的展示圖。

QR碼圖像是由N*N個深色或者淺色的模塊圖形組成,實驗中是黑色和白色模塊。根據QR碼的特點,讀取QR碼圖像中連續的兩行像素的像素值,如果兩行像素不同,則說明是第1行像素屬于上一層（行）的模塊圖形,第2行的像素屬于下一層（行）的模塊圖形。圖3是QR碼水印嵌入算法的步驟描述。

圖2 水印位置

表4 水印算法的條件描述

依據此特點,文中的嵌入水印算法描述如下:

（1）從QR碼圖像的第1行像素開始,讀取連續兩行像素的像素值,如果相同,則向下移動一行,繼續讀取連續兩行像素的像素值。以此類推,當讀取到兩行像素,不相同時,則進入步驟（2）。

（2）若從步驟（1）進入（2）,則從左到右,讀取當前兩行像素中,第1行像素的每一個像素點,當該行像素中某一個像素點滿足條件a或者條件b時,見表4,則記錄該像素點的坐標（XS,YS）,進入步驟（3）,否則繼續讀取第1行中的下一個像素。若從步驟（4）進入（2）,則從步驟（4）所在的坐標位置開始,繼續尋找新的坐標（XS,YS）,然后進入步驟（3）。

（3）從步驟（2）中讀取的像素點的位置開始,繼續讀取第1行中后面的像素,當尋找到某一個像素點滿足條件c或者條件d時,見表4,則記錄該像素點的坐標（XE,YE）,并進入步驟（4）,否則繼續讀取第1行的下一個像素點。

（4）將待嵌入的水印信息依順序取出2 bit大小的信息,并根據表3,選擇對應需要修改的LSB值,修改坐標（XS,YS）到坐標（XE,YE）上的連續n*M 個像素的LSB值。至此,完成一次大小為2 bit的水印嵌入。然后轉入步驟（2）,繼續尋找該行剩余的水印嵌入位置。當此行像素讀取完成,進入步驟（1）,繼續尋找可嵌入水印的像素,直到完成所有水印的嵌入。

2.2 水印提取算法

由于嵌入水印的QR碼和原始的QR碼不同,所以如果依舊采用讀取兩行像素的方式,并不能正確的找到含有水印的像素點。

此時,要尋找到正確的水印信息,需要讀取連續的3行像素,當這3行像素滿足第2行和第3行的像素相同,而第1行與第2行、第3行的像素不同時,讀取到的第1行像素就包含了要找的水印像素點。圖4是QR碼水印提取算法的步驟描述。

水印提取算法描述如下:

（1）從QR碼圖像的第1行像素開始,讀取連續3行像素的像素值,當滿足第2行和第3行的像素相同,而第1行與第2行、第3行的像素不同時,進入步驟（2）,否則向下移動一行繼續讀取連續3行的像素值,以此類推。

（2）若從步驟（1）進入,則從左到右,讀取當前第1行中的每一個像素,當第1行中某一個像素點是黑色像素并且滿足條件a或者條件b時,或者當第1行中某一個像素點為非黑白色像素并且滿足條件a或者條件b時,條件描述見表4,則記錄該像素點的坐標（XS,YS）,進入步驟（3）,否則繼續讀取第1行的下一個像素。若從步驟（4）進入,則繼續步驟（4）的坐標位置,繼續尋找新的坐標（XS,YS）。

（3）接著步驟（2）中讀取的像素點位置,繼續讀取第1行中后面的像素值,當尋找到某一個像素點是黑色像素點并且滿足條件c或者滿足條件d時,或者是非黑白色像素點并且滿足條件c或者條件d時,見表4,則記錄該像素點的坐標（XE,YE）,并進入步驟（4）,否則繼續讀取第1行的下一個像素。

（4）讀取坐標（XS,YS）到坐標（XE,YE）上的連續n*M個像素的LSB值,比較選擇出n*M 個像素中重復最多的LSB值。根據表3,輸出對應的水印信息。然后轉入步驟（2）,繼續尋找該行剩余的水印。當本行像素讀取完成,進入步驟（1）,讀取下面的3行連續像素,直到完成所有水印信息的提取。

圖3 水印嵌入算法步驟描述

圖4 水印提取算法步驟描述

3 實驗和結論

3.1 對比結構微調的水印算法

目前,大多數基于二維碼的數字水印算法都是在不影響識讀的條件下,通過適量的修改二維碼的圖形結構,嵌入水印信息。以PDF417為例,有通過修改條和空的寬度嵌入水印的算法[2-5],如圖5所示。另外也有修改兩行條碼中某一行的高度來嵌入水印的算法[13]。而針對QR碼,有通過擴展點陣模塊的左右側和上下側的邊緣寬度嵌入水印信息[14],如圖6所示。

圖5 修改PDF417的條和空的寬度和高度的水印算法效果圖

圖6 修改QR碼的黑色模塊邊緣像素的水印算法效果圖

圖5中,針對PDF417碼,從上至下的第1個圖形不含水印,第2個圖形是縱向修改邊緣像素,第3個圖形是橫向修改邊緣像素。圖6中的上方圖形是無水印的QR碼,下方圖形是修改深淺模塊的邊緣像素的QR碼。

3.2 含有水印的QR碼的識別和水印提取實驗

圖7 無水印QR碼和含水印QR碼

根據QR碼識別的原理,識別算法會選擇圖像像素RGB值的最大值和最小值的中值作為閾值,使用該閾值將圖像劃分為一系列深色和淺色的模塊。因對QR碼像素LSB的修改不會影響到閾值的正確選擇,從而不會影響到QR碼的正確識別。圖7是水印算法的實現效果圖,（a）圖是不含水印的QR碼,（b）圖是含有水印的QR碼。

圖8 一次實驗的工作流程

算法穩定性實驗,流程如下:

（1）產生一段隨機長度和隨機內容的文本T1。

（2）將文本T1編碼為QR碼圖形Q1。

（3）計算Q1的水印容量大小。

（4）產生一個滿足Q1水印容量的隨機水印信息W（二進制信息）。（5）向Q1中嵌入水印信息W得到含有水印的QR碼圖形Q2。

（6）識讀Q2得到T2,并與原始編碼內容T1對比,記錄對比結果。

（7）從含有水印的QR碼圖形Q2中提取水印信息WR。

（8）比較W和WR,記錄對比結果。

（9）重復10000次步驟（1）～（8）的試驗,并計算QR碼的識別正確率和水印嵌入和提取的正確率。

圖8是步驟（1）～（8）的一次完整實驗的工作流程。實驗中QR碼圖像的大小為500*500像素,文件格式為BMP,糾錯級別隨機。隨機文本T包含英文字母、數字和常用標點符號。重復試驗的次數為10000次,最后記錄實驗結果并計算正確率。實驗最終得到的數據是QR碼的識別正確率為100%,嵌入和提取水印的正確率為100%。該實驗表明,水印算法非常穩定,嵌入的水印不會影響到QR碼的正確識別,并且水印信息的嵌入和提取不受水印內容和QR碼載體圖像的影響。

3.3 結論

提出了一種適用于QR碼的脆弱水印算法,該算法運用一種改進的LSB算法嵌入水印信息,保證水印信息不會改變QR碼的圖形結構,并確保嵌入的水印信息不會影響到QR碼的正確識別。與現有的利用誤差特性進行信息隱藏的算法相比,該算法極大程度增強了數字水印的隱蔽性,提高了水印信息的嵌入量。同時算法不會受到QR碼的容量限制,并且能夠解決目前嵌入水印的二維碼不適合電子文件形式保存的問題,可以將嵌入水印的QR碼廣泛應用于終端設備對電子票的防偽及驗證。

致謝:感謝成都市科技攻關項目（10GGYB368GX023）;成都信息工程學院自然科學基金項目（CSRF2001）對本文的資助。

[1] 中國物品編碼中心.二維條碼技術與應用[M].北京:中國計量出版社,2007:324-325.

[2] 牛夏牧,黃文軍.基于二維條碼的信息隱藏技術[J].中山大學學報（自然科學版）,2004,43（S2）:21-25.

[3] 陳崢,姚宇紅.一種基于二維圖形碼的數字水印技術[J].計算機應用,2006,26（8）:1998-2000.

[4] 趙博,黃進.基于PDF417條碼的信息隱藏方法[J].計算機工程與設計,2007,28（19）:4806-4809.

[5] 晁玉海,劉連山.基于PDF417條碼的信息隱藏算法[J].計算機工程,2010,9:131-133.

[6] Ming Sun,Jibo Si,Shuhuai Zhang.Research on embedding and extracting methods for digital watermarks applied to QR code images[J].New Zealand Journal of Agricultural Research,2007,50（5）:861-867.

[7] Jau-Ji Shen,Po-Wei Hsu.A Fragile Associative Watermarking on 2D Barcode for Data Authentication[J].International Journal of Network Security,2008,7（3）:301-309.

[8] Vongpradhip S,Rungraungsilp S.QR code using invisible watermarking in frequency domain[J].ICT and Knowledge Engineering（ICT&Knowledge Engineering）,2012:47-52.

[9] Suppat Rungraungsilp,Mahasak Ketcham,Pruch Surakote.Data Hiding Method for QR Code Based on Watermark by comparing DCT with DWT Domain[J].International Conference on Computer and Communication Technologies（ICCCT′2012）,2012:149-153.

[10] Suppat Rungraungsilp,Mahasak Ketcham,Pruch Surakote.Data Hiding Method for QR Code Based on Watermark by compare DCT with DFT Domain[J].International Conference on Computer and Communication Technologies（ICCCT′2012）,2012:144-148.

[11] Jessica Fridrich,Miroslav Goljan,Rui Du.Detecting LSB steganography in color and gray-scale images[J].IEEE Computer Society,2001,10:22-28.

[12] 蘇亞娟.基于矩陣編碼的空域信息隱藏算法[J].計算機工程與設計,2009,30（23）:5344-5347.

[13] 魏偉光.二維條碼空間域數字水印嵌入方法研究[J].北方工業大學學報,2010,（3）:131-133.

[14] 孫丙,高美鳳.基于QR碼的數字水印算法研究[J].計算機與現代化,2011（11）:74-77.