一種基于兩級閾值的像素不擴展視覺密碼方案*

孫 瑞, 付正欣, 李小鵬, 郁 濱

信息工程大學, 鄭州450001

1 引言

Naor 和Shamir[1]將秘密共享的思想運用到了數字圖像領域,形成了視覺密碼(visual cryptography,VC) 這一研究熱點. 有別于傳統密碼學大量繁復的解密運算, 視覺密碼的主要特點在于無條件安全性和重建圖像簡單性. 對于特定參與者集合, 不需要任何復雜運算, 通過人類視覺系統(human visual system,HVS) 即可重建秘密圖像, 而剩余參與者集合則無法獲取秘密圖像的任何內容. 視覺密碼方案設計主要圍繞降低像素擴展度、提升恢復質量和保證安全性等三個方面展開. 像素不擴展視覺密碼是在保證視覺密碼嚴格安全性的前提下, 利用隨機柵格、概率法、多像素加密法等像素不擴展分享方法, 結合數字圖像處理技術, 平衡恢復質量和圖像尺寸的固有矛盾, 實現恢復圖像質量提升的目標.

Kafri[2]等人以函數運算為基礎, 提出了(2,2) 門限結構隨機柵格(random grid, RG) 方案, 利用隨機化fran、相等fequ和取反fcom三個函數實現了秘密信息分享. 在此基礎上, Shyu[3]設計了(n,n) 門限結構和灰度/彩色空間下的隨機柵格方案, Chen 等人[4]將隨機柵格存取結構擴展到的(k,n) 門限結構,Wu 等人[5]通過定義彩色像素“異或” 運算, 生成通用存取結構下彩色共享份. 在恢復質量提高方面, Wu等人[6]設計了更一般化的隨機柵格方案, 通過調整首張共享份黑白占比, 提高恢復圖像對比度, Hou 等人[7]設計了逼近對比度理論極限的(2,n) 門限隨機柵格方案, Hu 等人[8]通過排布像素位置, 提高了門限方案的對比度.

Ito 等人[9]以確定型方案基矩陣作為分享矩陣, 隨機選取分享矩陣一列分享, 實現了恢復圖像尺寸不擴展. 在此基礎上, Yang[10]提出并正式定義了概率型視覺密碼(probabilistic VC, PVC), 構建了不依賴于確定型視覺密碼基矩陣的(2,n)、(n,n) 和(k,n) 門限結構分享矩陣. Hou 等人[11]利用基矩陣構建分享矩陣, 設計了共享份質量提升的漸進式視覺密碼方案, 然而恢復質量并未得到改善. Wu 等人[12]以彩色共享份替代黑白共享份實現了共享份尺寸不擴展. 隨機柵格法的恢復效果與概率法相似, Yang 等人[13]證明了隨機柵格法與概率法的等效性. 雖然隨機柵格法與概率法的恢復圖像被逐步優化, 但由于秘密圖像中每個像素被獨立處理, 沒有考慮像素鄰域特征關聯關系, 導致恢復圖像中少數像素分布不均勻, 恢復效果較差.

多像素加密視覺密碼(multi-pixel encryption VC, MEVC) 方案以多個像素為基本處理單元, 將包含一定數量的秘密像素塊作為加密對象, 映射到共享份中相同數量的像素, 從而實現像素不擴展. Hou 等人[14]首先提出了多像素分享思路, 以確定型方案基矩陣為分享矩陣, 每次分享固定數量的像素, 依據像素塊中黑色像素占比選擇相應加密矩陣. 基于相同條件, 多像素法恢復圖像的全局對比度與概率型全局對比度相同, 但黑白像素分布更加均勻, 視覺效果更優. 為了反映上述差別, Hou 等人[15]引入方差反映局部圖像的平滑程度, 與相對差一同作為恢復圖像效果的評價指標. 方案[14] 分享算法在選擇基矩陣時隨機性不強, 恢復圖像出現周期性的條紋. Liu 等人[16]優化了上述算法, 任一像素塊都以一定的概率選擇基矩陣, 消除了恢復圖像中的紋理. 張等人[17]提出了行掃描、列掃描、Zigzag 掃描等三種掃描方式的多像素編碼方案, 然而恢復質量提升有限.

為了提升多像素加密視覺密碼方案的恢復圖像質量, Chen 等人[18]提出了多灰度級基矩陣構建方法,灰度圖像中平均灰度級高的塊映射到恢復圖像中塊的平均灰度值也相應高, 由于不僅只有兩級灰度, 恢復圖像的表現力更強. Lee 等人[19]通過灰度秘密圖像的直方圖特征, 選取不同的映射關系, 間接實現了直方圖均衡化, 改善了恢復圖像的顯示效果. Yan 等人[20]面向灰度圖像, 采用融合了誤差擴散法與視覺密碼的AbS 架構, 將恢復圖像與秘密圖像之間的誤差擴散至高頻帶, 生成了具有藍噪聲特征的恢復圖像.Sun[21]等人提出基于快速直接二值搜索算法的像素不擴展視覺密碼方案, 將概率型視覺密碼分享算法嵌套于半色調尋優過程中, 以共享份疊加結果為優化對象, 最終實現尋優策略下的最優恢復圖像, 視覺質量得到進一步提升. 上述幾種方案僅適用于(n,n) 門限結構.

已有的像素不擴展視覺密碼方案中, 較優的恢復質量往往受限于(n,n) 門限結構, 且以復雜設計方案和高計算復雜度為代價, 而面向一般(k,n) 存取結構的方案, 處理細節內容的能力不足, 秘密圖像中細節內容恢復不佳. 像素不擴展視覺密碼中, 秘密像素只能以一定概率被恢復, 恢復概率與分享算法密切相關.多像素概率型視覺密碼方案設計的關鍵, 是確定秘密像素塊灰度集合到分享矩陣的映射關系, 通過調節映射關系可以強調圖像特定內容.

據此, 本文提出了一種面向一般(k,n) 存取結構的多像素加密視覺密碼方案. 方案從圖像的空域出發,依據秘密像素塊黑色像素密度, 采取塊尺寸由大到小調整、分類處理的方法, 以一級閾值區分秘密圖像中低頻和高頻區域, 進而采取不同的分享方法, 低頻區域作為純色像素塊分享, 以二級閾值調控高頻區域中單位塊灰度與分享矩陣的映射關系, 達到了增強恢復圖像中部分細節表現的效果. 理論證明本方案具有與確定型視覺密碼方案同等強度的安全性, 實驗結果和對比分析證明了方案的有效性.

2 基本概念

多像素加密方案一次分享若干個秘密像素, 已有的確定型視覺密碼定義和概率型視覺密碼定義無法涵蓋多像素加密方案, 本節給出了多像素加密視覺密碼的定義, 介紹了兩種典型的像素不擴展視覺密碼實現方案.

2.1 多像素加密視覺密碼定義

多像素加密視覺密碼分享一幅二值秘密圖像G產生n個共享份Si ∈ZM×N2(i ∈[1,n]), 并將n個共享份打印至透明膠片后分發給n個參與者, 只有特定組合的參與者即授權子集, 才能通過疊加共享份解密出視覺系統可直接識別的信息, 而對其他組合的參與者即禁止子集, 不能恢復出任何信息, 對(k,n) 方案,授權子集為參與者數量大于等于k的所有可能組合的集合.

定義1 一個(k,n)-MEVC 方案由基矩陣B1,B2,··· ,Bt組成, 秘密圖像和恢復圖像的塊灰度集合分別為D和E. 秘密圖像G中包含相同數量像素的任意兩個不重疊區域坐標索引集合Ω1和Ω2,不失一般性地, 設H(G[Ω1])>H(G[Ω2]),H表示平均灰度. 分享秘密圖像G生成n幅共享份Si ∈ZM×N2(i ∈[1,n]). 設d為參與者個數, 參與者集合P={i1,i2,··· ,id} ? {1,2,··· ,n},E={e:e=H(η(Bi?P?))}(i= 1,2,··· ,t),η(B?P?) 表示限制矩陣B行數至集合P得到新矩陣的行向疊加結果. 如果滿足以下兩個條件, 則秘密分享算法可稱為有效的(k,n)-MEVC.

(1) 對比性條件. 當d ≥k時,

對于實驗設定如下評判標準：（1）注重荷載-沉降曲線觀察，確定承載力陡降的同時，查看位移傳感器的顯示數據，確認總沉降量是否大于40mm；（2）基礎樁因受承載過大已經發生破壞，且破壞仍在不斷增加；（3）針對樁長超過25m的基礎樁，其荷載-沉降曲線緩慢變形的階段尚未出現；（4）實驗中，若發生下一次的沉降量是本次沉降量的2倍且此狀態還在持續，則表明基礎樁荷載受力還未穩定；（5）實驗中加載的最大荷載大于設計單樁承載力的2倍是實驗數據有效的基礎，若施加荷載不夠，則實驗無效。

滿足H(R1)≥H(R2), 符號V表示矩陣行向疊加運算.

(2) 安全性條件. 當d

滿足f1～f2, 即f1和f2有相同的矩陣集合和概率分布, 給定矩陣f?, 無法從中獲知秘密圖像G的任何信息, Pr{G?=g}=Pr{G?=g|f?}, g ∈D.

第一個條件保證參與者人數為不少于k個時, 秘密圖像能被正確恢復出來, 第二個條件保證參與者人數小于k時, 共享份疊加所得的圖像不會泄露秘密圖像的任何信息, 即使敵手具備無限計算資源和運算時間, 也無法得到有關秘密圖像的確定信息.

2.2 典型像素不擴展視覺密碼方案

Liu 等人[16](k,n)-MEVC: 設(k,n) 確定型視覺密碼的基矩陣為n×m的B0和B1,C0=〈B0〉,C1=〈B1〉, (〈A〉表示矩陣A 的列向全排列組成的矩陣集合). Liu 等人以像素數量m的塊為單位分享秘密圖像, 單位塊中含有的黑色像素數量表示為b, 像素塊選擇分享矩陣的規則如算法1:

算法1 1. E[b] ←b, b = 1,2,··· ,m 2. N [b] ←m, b = 1,2,··· ,m 3. 若Random(N[b]) < E[b]4. 隨機選取C1 中任一矩陣填至共享份相應位置5. E[b] ←E[b]?1 6. N [b] ←N [b]?1 7. 否則8. 隨機選取C0 中任一矩陣填至共享份相應位置9. N [b] ←N [b]?1 10. 若N [b] = 0,E[b] ←b,N [b] ←m

該方案采取了塊分類處理的思想, 對每一類塊, 分別設立記錄已分享次數的計數器E[b] 和N[b]. 對于含有b個黑色像素的塊, 以b?m概率選擇矩陣集合C1中元素加以分享, 以(m ?b)/m概率選擇矩陣集合C0中元素加以分享, 方案的對比性條件和安全性條件由確定型視覺密碼的基矩陣保證.

3 方案設計

本節針對之前方案處理細節內容能力不足和恢復效果較差的問題, 提出了基于兩級閾值的多像素加密分享算法, 并就算法的有效性進行了理論證明.

3.1 分享原理

方案流程如圖1, 在分享秘密圖像時, 首先以初始尺寸分割秘密圖像, 當檢測到當前塊黑色像素密度大于等于上閾值時, 將此塊作為黑色塊處理; 當檢測到當前塊黑色像素密度小于等于下閾值時, 將此塊作為白色塊處理; 當前塊灰度密度介于上閾值和下閾值之間時, 繼續分割并分享, 直至當前塊尺寸與單位塊尺寸相同且不滿足上閾值和下閾值, 不再繼續分割, 以二級閾值選擇基矩陣. 通過設定二級閾值取值, 進而調控分享矩陣選擇, 當意圖突出白色細節時, 閾值設置應大于0.5; 當意圖突出黑色細節時, 閾值設置應不大于0.5. 二級閾值與0.5 的偏離程度決定了強化效果, 偏離程度越大, 強化效果越明顯. 方案偽代碼表述如算法2.

圖1 方案流程圖Figure 1 Block diagram of proposed scheme

算法2 (k,n)-MEVC Input: (1) 二值秘密圖像G(2)(k,n) 門限分享矩陣集合Ci ∈Zn×m2 ,i ∈[0,1](3) 一級閾值level1_up 和level1_down, 二級閾值level2 Output: 共享份Si ∈ZM×N2 ,i ∈[1,n]1 確定單位塊和初始塊尺寸: x×y = m,k×l 2 以k×l 尺寸分割G 3 for 每一個當前塊B do 5 if H(B)/|B| ≥level1_up then 4 if |B| > m then 6以C1 中元素分享當前塊B 7 end 8 if H(B)/|B| ≤level1_down then以C0 中元素分享當前塊B 10 end 11 else 9 12 分割當前塊B, 轉步驟3 13 end 14 end 15 if |B| = m then 16 if H(B)/|B| ≥level2 then 17 以C1 中任一元素分享當前塊B 18 end 19 else 20 以C0 中任一元素分享當前塊B 21 end 22 end 23 end 24 return 共享份Si ∈ZM×N2 ,i ∈[1,n]

在分享算法中, 以單位塊作為共享份填充的基本單元. 首先依據基矩陣列長m確定x和y, 使得單位塊的縱橫比盡可能接近1, 最大程度接近正方形. 若無法滿足縱橫比要求, 可對基矩陣列作適當填充. 進一步確定初始塊的尺寸k和l, 使其長寬滿足單位塊長寬的整數倍.

3.2 有效性證明

每次分享的秘密像素塊是若干滿足閾值條件的像素, 且像素塊尺寸為單位塊尺寸的整數倍. 設|B| 代表秘密像素塊B包含的像素數量, 單位塊包含的像素數量為m, 可將秘密像素塊劃分為|B|/m個單位塊,對每個單位塊而言, 都由C0或C1中任意一個矩陣分享.

定理1 (k,n)-MEVC 算法滿足視覺密碼的對比性條件.

秘密分享的整個過程由若干單位塊分享構成, 算法的有效性建立在基矩陣的選取和基矩陣隨機重排上, 與分割方式和填充方式無關. 另外, 對單位塊而言, 填充方式的改變, 并不影響其對比性條件和安全性條件. 本方案的有效性與Naor-Shamir 視覺密碼方案的有效性是等價的.

4 實驗及結果分析

本節通過實驗驗證算法的有效性. 對比文獻選擇應面向同一類分享對象、解決同一問題. 本文的目的是提升恢復圖像的視覺質量, 而非共享份的視覺效果, 因此排除擴展型視覺密碼; 面向一般的(k,n) 門限結構, 排除只面向(n,n) 結構的分享方案. 同時本方案符合無條件安全性, 排除降低安全性條件從而提升視覺效果的設計方案. 基于以上考慮, 選取了Yang[10]、Hou 等人[14]、Liu 等人[16]的方案, 針對6 個指標作對比分析.

4.1 有效性驗證

為了證明本文方案的有效性, 給出了(3,3) 門限結構下分享圖像的實驗結果, 基矩陣為:

秘密圖像為一幅尺寸為384×384 的Lena 二值圖像, 參數設置如下: 單位塊尺寸2×2 像素、初始塊32×32 像素、上閾值0.95、下閾值0.1、二級閾值0.5.

如圖2, (3,3) 門限結構下恢復圖像對比度下降為秘密圖像的1/4, 圖(b) 所示為圖(a) 對比度下降1/4 所得圖像. 圖(c)(d) 和(e) 為分享秘密圖像(a) 生成的3 幅共享份, 任意一張共享份均為類噪聲圖像,視覺上無法從中獲得秘密圖像的任何信息, 圖(f) 為共享份1 和共享份2“或” 運算得到的圖像, 同樣無法從中識讀出任何信息, 驗證了安全性條件. 圖(g) 為三幅共享份進行“或” 運算得到的解密圖像, 疊加圖像輪廓顯現, 滿足了對比性條件. 相較于圖(b), 圖(g) 輪廓信息還原較為完整. 作為黑色像素塊分享的秘密像素塊可實現完全恢復, 而白色像素塊只有1/4 為白色, 觀察可見, 白色區域出現明顯的顆粒感.

圖2 (3,3) 門限結構下分享結果Figure 2 Encryption results on (3,3) threshold scheme

4.2 對比分析

通過對比參考文獻, 結合共享份填充方式、平均對比度、方差、細線問題和計算復雜度, 分析各方案的優劣. 秘密圖像尺寸為256×256 像素的二值圖像, 存取結構為(3,3) 門限結構, 分享條件設置同上一節.

圖3 和圖4 分別展示了不同方案對“龍” 圖和細線圖的恢復效果圖, 由實驗結果觀察可知, Yang 方案由于采用了基矩陣單列分享的方式, 反映在恢復圖像中, 視覺效果表現為黑白像素分布不均勻、低頻噪聲集中、顆粒感較強, 以致圖4(c) 中, 黑色線條掩蓋被完全掩蓋. Hou 等人和Liu 等人均采用定長m分享,由于改進了基矩陣選擇條件, 后者顯示質量較前者有所提升, 但改進效果不明顯.

圖3 “龍” 圖實驗結果對比Figure 3 Recovery results of competitive schemes on “dragon” image

圖4 細線圖實驗結果對比Figure 4 Recovery results of competitive schemes on “thin-line” image

相較于對比方案, 本方案秘密圖像白色區域相應于恢復圖像的位置, 黑白像素分布均勻, 無明顯少數像素集聚, 平滑度優于對比方案. 對于秘密圖像中的細節, 如龍須等部分, 對比方案的恢復結果均有明顯的斷續甚至消失, 本方案恢復結果較為連續, 處理細節的能力有所提升. 圖4 展示了各方案細線處理結果, 本方案恢復圖像的黑色線條比較清晰完整地恢復出來, 對橫線、豎線和斜線的處理效果都較佳, 細線效果整體上優于對比方案.

4.3 參數對比

參數對比如表1 所示.

表1 (3,3) 存取結構下各方案對比結果Table 1 Comparative results on (3,3) threshold

(1) 塊方差. 塊方差表征秘密像素塊映射到恢復圖像中塊灰度值的波動程度, 方差越小, 則圖像整體視覺感官越好. 令m代表基矩陣的列長,b代表列長為m的秘密像素塊中黑色像素數量,h代表黑色像素恢復后的灰度,l代表白色像素恢復后的灰度. Yang 方案、Zhang 等人方案、Hou 等人和Liu 等人方案的方差分別表示為:

本方案中, 單位塊尺寸x×y=m, 則灰度集合為ζ={0,1,2··· ,m}, 設滿足上閾值條件的灰度集合為P={0,1,··· ,p}, 滿足下閾值條件的灰度集合為Q={q,··· ,m}. 若秘密像素塊滿足上閾值和下閾值, 其方差為零; 若不滿足, 則以p1= (g ?|P|)/(|ζ|?|P|?|Q|) 的概率選擇C0, 以p2=(|ζ|?g ?|Q|)/(|ζ|?|P|?|Q|) 的概率選擇C1, 方差可以表示為

(2) 細線問題. 細線用以評估方案處理細節信息的能力, Liu 等人定義了三類細線問題(TLP), TLP-1 指在白色背景下黑色細線消失問題, TLP-2 指黑色背景下垂直線條消失問題, TLP-3 指細線變粗問題.Yang 方案和Zhang 等人方案存在TLP-1 問題, Hou 等人方案和Liu 等人方案存在TLP-1 和TLP-3 問題, 本方案存在TLP-3 問題. 雖然本方案帶來細線變粗的問題, 在相同條件下, 恢復效果較對比方案更優.

(3) 計算復雜度. 設灰度秘密圖像的行寬、列寬分別為M和N, 上述對比方案計算復雜度都是O(MN). 分享算法根據圖像內容動態調整每次分享的秘密像素塊尺寸, 如若考慮一般情況, 則復雜度計算較為困難, 因此考慮兩種極端情況. 一是秘密圖像全部按單位塊分享, 則該方案蛻化為定長多像素概率型視覺密碼, 根據已有知識, 定長多像素概率型視覺密碼方案的計算復雜度是秘密圖像尺寸的線性函數; 二是秘密圖像按一個整體分享, 分享矩陣級聯次數與秘密圖像的尺寸成正相關線性關系, 可知計算復雜度亦是秘密圖像尺寸的線性函數. 因此, 綜合上述兩種情況, 可知本方案的計算復雜為O(MN).

5 結論

針對現有像素不擴展視覺密碼方案恢復圖像細節信息損失以及視覺質量較差的問題, 在分析圖像的像素分布特征的基礎上, 采取塊尺寸由大到小調整、分類處理的方法, 區分秘密圖像中低頻和高頻區域, 采取不同的分享方法, 通過調控高頻區域中單位塊灰度與分享矩陣的映射關系, 增強恢復圖像中部分細節表現. 實驗結果表明, 本方案恢復圖像顆粒感較低, 秘密圖像細節恢復較為完整, 線條連續, 細線圖像測試結果表明, 本方案對不同走向的線條均有較好的恢復效果, 細線處理能力較對比方案有明顯優勢. 本方案基于(k,n) 門限存取結構, 同樣適用于通用存取結構.