基于K-means聚類和Harris特征的水印算法?

鄭秋梅 楊亞男 曹寶琴 王風華 張萌萌

（中國石油大學（華東）計算機與通信工程學院 青島 266580）

1 引言

隨著互聯網、多媒體技術的迅速發展，使得多媒體內容分發、通訊、再現變得容易，隨之而來也出現了很多問題，如內容的篡改、非法復制、發行、再傳輸。數字水印技術［1～2］是解決這些問題的有效手段之一。數字水印是以不易察覺的方式將水印嵌入作品所有權版權信息（企業標識、作品信息等），來保護版權所有者的合法利益。目前數字水印算法大多數以灰度圖像為研究載體，而彩色圖像在實際的應用場景中占主導地位。目前彩色圖像數字水印算法大多利用人類視覺系統的特性，在載體圖像的頻域系數中嵌入水印，然而由于頻域系數沒有幾何不變性，不能有效抵抗幾何攻擊，因此，設計彩色圖像能夠抵抗幾何攻擊的水印算法成為研究熱點和難點。

近幾年抗幾何攻擊的水印算法主要采用第二代數字水印技術［3～4］。第二代數字水印技術利用圖像內在特征進行水印嵌入在抗幾何攻擊中具有良好的魯棒性。其基本思想是利用提取圖像中具有幾何不變性的特征點，利用這些特征點來構造特征區域，將水印信息嵌入其中，從而提高水印算法對幾何攻擊的魯棒性。目前針對抗幾何攻擊，國內外學者利用Harris 角點具有RST 不變性的特性做了大量研究。Qi等［5］提出，圖像內容由基于圖像紋理的自適應Harris 角檢測器獲得的重要特征點表示，這些重要的特征點具有幾何意義，因此能夠利用基于Delaunay三角形匹配方法去同步攻擊。陳青等［6］利用Harris 算子提取并篩選穩定的特征點，在特征區域的小波域嵌入水印，該算法抗旋轉攻擊魯棒性較好，但水印圖像和載體圖像像素大小受特征區域個數限制。周廣州等［7］利用Harris算子提取出歸一化圖像的特征點，選取部分穩定特征點確定特征區域，對特征區域進行一次小波分解，利用分塊加權奇異值分解法提高水印的魯棒性，該算法對剪切攻擊魯棒性良好，但對中值濾波、縮放攻擊、旋轉攻擊等水印攻擊魯棒性不佳。

單一地使用Harris 算子提取特征點，通過這些特征點選定的特征區域，特征點個數較少，當圖像旋轉角度較大時，遭受攻擊后點位移或剪切時，特征區域不穩定，水印無法恢復。本文根據人眼視覺特性，采用彩色圖像作為載體圖像，利用具有旋轉不變性的Harris 算子，提出一種新的基于聚類算法的特征構造算法，使得到的特征區域不但盡可能多地包含穩定的特征點又互不重疊，采用DC 系數自適應的水印嵌入算法，保證了對常規圖像處理攻擊的魯棒性。

2 背景及相關理論知識

2.1 Harris角點檢測

Harris 角點檢測函數計算簡單，同時該響應函數具有旋轉不變性。Harris［8～9］在1988 年改良并優化Moravec 算子，考慮角點與方向的差值，提出了Harris 角點檢測算法。Moravec 算法［10］的窗口移動方向都是45°或45°的整數倍，而Harris 算法將窗口沿各個方向進行移動，計算出各個方向上的像素梯度變化，定義灰度值的變化如式（1）：

其中，Iu，v為圖像的灰度函數，wu，v=e-(u2+v2)/ο2為窗口函數。

對于局部微小的移動量[x，y] ，可以近似得到下面的表達：

其中，k是一個經驗常量，一般k∈[0 .04，0.06] ，Tr(M)和Det(M)分別是矩陣M的行列式和跡。

R值與M的特征值有關，當R為大數值正數、大數值負數和小數值，對應檢測到的是角點、邊緣和平坦區。圖1 為對Lena 圖和Baboon 圖進行Har?ris特征檢測后得到的結果。

圖1 Harris特征檢測結果

由圖1 可以看出，Harris 角點的檢測算法提取出的角點數目較多且密集，分布較廣，聚類算法構造特征區域具有局限性，因此本文采用一種加權Harris 角點檢測算法［11］，給每個檢測到的角點分配權值，通過權值大小來進行角點篩選。

將式（5）中計算得到的R值歸一化，作為其初始權值，Harris 角點檢測算法提取出的角點作為窗口的中心點，每一個角點用窗口（尺寸為7×7）進行遍歷。根據式（6）計算中心角點的權值。

其中value 為權值，(x，y)為中心角點的坐標，(x'，y')為窗口覆蓋區域坐標。

根據value 的大小對提取到的角點進行劃分，權值大的角點比權值小的角點更為重要，利用特征權值對特征點進行初步篩選后，采用K-means聚類算法構造特征區域。

2.2 K-means聚類算法

K-means 是解決眾所周知的聚類問題最簡單的無監督學習算法之一。其基本思想［12］為將n個數據點劃分為K個不相交的類，其類簇中心為μi，把數據點劃分至與μi距離最小的類簇中，以便最小化等式（7）的平方誤差函數：

K-means算法詳細流程如下。

步驟1初始化質心μi，i=1，2，...k；

步驟2按照距離最近原則，將數據點劃分到最近的聚類中心那一類中；

步驟3當分配完所有點后，計算K 個質心的位置；

步驟4循環步驟2 和步驟3，直至質心不再改變。

對K 值和初始質心的選取方面，K-means 算法需要選取K 個初始質心，常見的方法是隨機選取，但這種方法得到的聚類劃分效果較差；K-means算法選取初始質心需要不停地計算距離平方和，以得到最佳聚類中心，若數據集里面的數據量很大時，需要耗費大量的時間。本文采用與層次聚類結合的方法［13］，首先對特征點進行層次聚類，根據層次聚類結果選取K值和初始質心。

3 基于K-means 聚類和Harris 角點的特征區域構造算法

不同特征區域內可能會含有相同的特征點，若構造方法不得當不僅會導致特征區域重疊反復，還容易導致水印信息的交錯相互影響，因此利用K-means聚類算法設計特征區域構造算法，使得到的特征區域不但包含穩定的特征點又互不重疊。

本文提出一種新的基于K-means 聚類和Har?ris角點的特征區域構造算法，通過加權Harris角點檢測提取圖像的特征點，選取響應值R較大的特征點，利用K-means聚類算法設計特征區域構造算法，使得到的特征區域不但盡可能多的包含穩定的特征點又互不重疊。

構造算法具體流程如下。

步驟1通過加權Harris 角點檢測算法給每個檢測到的角點分配權值value，權值較大的點周圍的角點分布密集，權值較小的點周圍的角點數量少；

步驟2根據需要構造的特征區域數TN 選取合適的K 值，根據角點value 值的大小初步篩選后，利用層次聚類法對特征點初次聚類，得到K 個層次聚類中心，以求得的K 個中心點作為K-means聚類初始中心，進行K-means 聚類得到最終的K 個K-means聚類中心；

步驟3根據K 個聚類中心與嵌入區域半徑大小r 對中心角點進行篩選，去掉區域超過載體圖片大小的角點，得到K1個中心點；

步驟4比較距離中心點最近的角點的value值大小，value 值最大中心點作為區域中心進行特征區域構造，以此方法構造特征區域內焦點數目，權值較大的點周圍的角點分布密集；

步驟5刪除位于步驟4 構造的特征區域內的中心點，得到新的中心點序列；

步驟6判斷已構造的特征區域數是否為TN，若小于則執行步驟4，若等于，則構造完成，使得到的特征區域不但盡可能多的包含穩定的特征點又互不重疊。

4 水印嵌入和提取算法

4.1 水印嵌入算法

水印的嵌入流程圖如圖2，本文嵌入算法基本流程如下。

步驟1水印預處理

大小為m×m的二值圖像作為水印圖像，采用Arnold 變換和Logistic 混沌序列［14］相結合的方法對水印進行預處理，將Arnold 變換次數n、Logistic 映射的迭代初始值x0、迭代控制參數μ以及去除序列項數t作為密鑰保存。

今天，三北的生態狀況依然脆弱，三北的生態建設任務依然任重道遠。也許，就在未來的某一天，沙暴或者沙魔還會來襲，如果防沙不力，已有的成果可能葬身沙海，被無情地埋葬。

步驟2提取Harris角點構造局部特征區域

構造嵌入區域，將構造特征區域的中心點坐標信息、嵌入區域半徑r 及載體圖像尺寸S 作為密鑰保存，此外選取權值大的u 個特征點信息作為密鑰保存。然后將求得的局部特征區域進行合并，將合并后的區域作為水印的嵌入區域。

圖2 本文算法水印嵌入流程圖

步驟3水印位判斷取反

將上述得到的嵌入區域B 分量作為水印嵌入區域，下采樣為EB1 和EB2 兩部分。分別對區域EB1 和區域EB2 進行8×8 分塊DCT 變換，得到DC系數分別記為DCi與DCj，根據式（8）對要嵌入的1bit水印信息W進行取反判斷：

其中，α為水印的嵌入強度，將紋理不同的8×8子塊經過DCT變換得到兩個AC系數帶入式（10），判斷子塊類型，然后根據式（11）選取對應的嵌入強度。這里閾值β的選取參照了Wang［15］中的經驗閾值0.05。具體判斷方法如下所示：

式中的λ1，λ2取經驗閾值：λ1=50，λ2=65。

其中，αsmooth＜αedge＜αtexture，通過實驗驗證，對于RGB 模 型 設 置 為：αsmooth=0.07 ，αtexture=0.2 ，αedge=0.1。

嵌入區域圖像的RGB 模型的G 分量進行和B分量相同的操作，G 分量嵌入另一半水印，然后進行DCT逆變換，得到最終嵌入水印的圖像。

4.2 水印提取算法

本文在水印提取前，首先利用密鑰中保存的權值較大的特征點信息進行幾何校正［16］，利用密鑰中保存的特征區域中心點坐標構造特征區域，對校正后的圖像提取水印，其具體步驟如下。

步驟1通過加權Harris 角點檢測算法提取遭受攻擊后的圖像特征，保存權值較大的u 個特征點信息，與密鑰中保存的特征進行匹配；

步驟2圖像幾何校正，對圖像縮放攻擊的矯正直接根據密鑰中保存的載體圖像尺寸S 進行縮放攻擊校正。對圖像旋轉攻擊的矯正通過式（12）計算逆旋轉角度Θ 進行旋轉攻擊校正。計算公式如下：

θ為旋轉角度。

步驟3根據密鑰中保存的區域中心點構造局部區域，轉化為RGB 模型，提取B 分量下采樣記為TB1和TB2；

步驟4分別對TB1與TB2進行8×8分塊DCT變換，得到對應的DC 系數DCi與DCj，根據式（13）進行水印提取。

根據密鑰中保存的取反坐標序列，對提取到的水印信息進行取反處理，得到一半水印信息。

步驟5取RGB 模型中的G 分量，下采樣為TG1 和TG2，分別對TG1 與TG2 進行8×8 分塊DCT變換，得到對應的DC 系數DCj與DCj，利用式（13），根據密鑰中保存的取反坐標序列，對提取到的水印信息進行取反處理，提取到另一半水印。

步驟6將步驟4和步驟5水印信息合并，利用密鑰進行解密，合并得到最終的水印圖像。

5 實驗結果分析

實驗使用Matlab 2017b 作為驗證平臺，實驗中采用512 pixel×512 pixel 彩色Lena 圖像作為載體圖像，選擇30 pixel ×30 pixel的二值圖像作為嵌入的水印圖像，圖3為實驗使用的載體圖像及水印圖像，圖4為原始圖像及嵌入水印后的圖像。

采用峰值信噪比（PSNR）作為算法不可見性的評價指標［17］，通過實驗仿真，本文算法的PSNR 值為45dB，遠遠高于人眼可感知程度的33dB，具有很好的不可見性。

圖3 載體圖像和水印圖像

圖4 原始圖像和嵌入水印后的圖像

1）用歸一化系數（NC）值客觀評價原始圖像與提取水印后圖像的相關度［18］。常規信號攻擊包括不同強度的壓縮、噪聲和濾波等，本文算法和馬婷等［19］提取出的水印信息與原始水印信息的NC值見表1，實驗數據表明本文提出的水印算法對常規信號攻擊的魯棒性上要明顯優于對比算法。

表1 常規圖像攻擊下的NC值

2）旋轉攻擊。本文算法和陳青等［20］提取出的水印信息與原始水印信息的NC 值見表2，本文算法經旋轉攻擊后提取的NC 值接近1，實驗數據表明本文提出的水印算法在抗旋轉攻擊下的魯棒性上要明顯優于對比算法。

表2 旋轉攻擊下的NC值

3）縮放攻擊。采用雙三次插值方法對水印進行同等比例縮放攻擊（縮放比例分別為0.5，0.75，1.25，1.5 倍）。表3 為本文算法和文獻［20］提取出的水印信息與原始水印信息的NC 值，對比文獻［20］可知，本文算法在抵抗縮放攻擊更有優勢。

表3 縮放攻擊下的NC值

6 結語

本文針對彩色圖像數字水印算法對幾何攻擊魯棒性較差的問題，提出一種基于K-means聚類和Harris 特征的第二代數字水印算法。選取具有旋轉不變性的Harris 角點來構造水印嵌入區域。通過對特征的區域構造算法進行改進，采用K-means聚類算法確定嵌入區域的中心，保證了嵌入區域內特征點的最大化。由Matlab仿真實驗分析，本文算法的PSNR 值達到45dB，遠遠高于人眼可感知程度的33dB，具有很好的不可見性；此外本文算法在不同圖像攻擊下，計算得到的NC 值接近1，不僅對常規圖像處理具有魯棒性，能夠很好地抵抗幾何攻擊。而相較于大部分的基于特征區域的水印算法，本文提出的算法具有更高的水印容量。