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

信息工程大學(xué), 鄭州450001

1 引言

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

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

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

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

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

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

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

2 基本概念

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

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

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

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

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

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

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

(2) 安全性條件. 當(dāng)d

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

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

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

Liu 等人[16](k,n)-MEVC: 設(shè)(k,n) 確定型視覺密碼的基矩陣為n×m的B0和B1,C0=〈B0〉,C1=〈B1〉, (〈A〉表示矩陣A 的列向全排列組成的矩陣集合). Liu 等人以像素數(shù)量m的塊為單位分享秘密圖像, 單位塊中含有的黑色像素數(shù)量表示為b, 像素塊選擇分享矩陣的規(guī)則如算法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 中任一矩陣填至共享份相應(yīng)位置5. E[b] ←E[b]?1 6. N [b] ←N [b]?1 7. 否則8. 隨機選取C0 中任一矩陣填至共享份相應(yīng)位置9. N [b] ←N [b]?1 10. 若N [b] = 0,E[b] ←b,N [b] ←m

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

3 方案設(shè)計

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

3.1 分享原理

方案流程如圖1, 在分享秘密圖像時, 首先以初始尺寸分割秘密圖像, 當(dāng)檢測到當(dāng)前塊黑色像素密度大于等于上閾值時, 將此塊作為黑色塊處理; 當(dāng)檢測到當(dāng)前塊黑色像素密度小于等于下閾值時, 將此塊作為白色塊處理; 當(dāng)前塊灰度密度介于上閾值和下閾值之間時, 繼續(xù)分割并分享, 直至當(dāng)前塊尺寸與單位塊尺寸相同且不滿足上閾值和下閾值, 不再繼續(xù)分割, 以二級閾值選擇基矩陣. 通過設(shè)定二級閾值取值, 進而調(diào)控分享矩陣選擇, 當(dāng)意圖突出白色細節(jié)時, 閾值設(shè)置應(yīng)大于0.5; 當(dāng)意圖突出黑色細節(jié)時, 閾值設(shè)置應(yīng)不大于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 每一個當(dāng)前塊B do 5 if H(B)/|B| ≥level1_up then 4 if |B| > m then 6以C1 中元素分享當(dāng)前塊B 7 end 8 if H(B)/|B| ≤level1_down then以C0 中元素分享當(dāng)前塊B 10 end 11 else 9 12 分割當(dāng)前塊B, 轉(zhuǎn)步驟3 13 end 14 end 15 if |B| = m then 16 if H(B)/|B| ≥level2 then 17 以C1 中任一元素分享當(dāng)前塊B 18 end 19 else 20 以C0 中任一元素分享當(dāng)前塊B 21 end 22 end 23 end 24 return 共享份Si ∈ZM×N2 ,i ∈[1,n]

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

3.2 有效性證明

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

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

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

4 實驗及結(jié)果分析

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

4.1 有效性驗證

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

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

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

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

4.2 對比分析

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

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

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

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

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

4.3 參數(shù)對比

參數(shù)對比如表1 所示.

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

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

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

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

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

5 結(jié)論

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