栅格地图数据(以下简称栅格地图)是各种比例尺的纸介质地形图和各种专业使用的彩图的数字化产品，根据现有纸质、胶片等地形图经扫描、几何纠正及色彩校正后，形成在内容、几何精度和色彩上与地形图保持一致的栅格数据文件，其具有数字图像的特征和数据量大的特点。其中包含国家重要基础设施、国防重点目标符号和标识的栅格地图，必须提供必要的加密手段保证其安全性。

常用的栅格地图安全保护技术主要有：基于混沌理论的图像加密技术，依照混沌序列将待加密的图像位置置乱，将每一个像素进行加密处理，并进行循环迭代处理，完成加密过程，此类算法计算复杂度较高，成本较大^[1]；数字图像置乱技术，图像置乱主要针对像素位置和像素灰度值，此类算法存在置乱周期性，当算法进行迭代置乱一定的次数后，置乱后的图像将被还原^[2]；图像信息隐藏技术，将密文图像隐藏到掩盖图像后再隐蔽传输，可以提高秘密图像保护的安全性，但其安全性是建立在隐蔽性的基础上，一旦隐藏算法泄露，秘密图像信息很容易被获取^[3]。上述技术存在一个共同的不足，即单个载体在传输时一般情况下是通过一个通道来实现的，只要这个通道出现故障或破坏，接收方就不能正确接收到原图像信息^[4]。在某些具有丢失容忍、解密简单、共享份图像顺序可交换、权限控制等特点应用场合，上述技术将不再适用^[5]。

而图像分存技术可应用于上述场合，其基本原理是将秘密图像信息加密成为多个共享份图像，分发给多个参与者，只有授权参与者子集可以一起解密(还原)秘密图像，而非授权子集合无法解密(还原)。图像分存技术具有丢失容忍性的特点，当丢失部分共享份图像时，仍然可以解密秘密图像。目前，图像分存技术的研究主要集中在基于多项式的图像分存技术和基于视觉密码的图像分存技术两个方面。前者主要是利用Shamir的多项式共享算法将秘密图像共享为多个影子图像，然后利用插值原理得到精确恢复的秘密图像，该方法的计算复杂度高^[6]；后者最大的优点是秘密图像恢复时运算简单，仅利用人眼视觉系统或借助简单计算设备，便可以获得恢复图像的信息^[7]。

随着手持设备的应用，以及栅格地图的户外应用需要，对于解密运算简单的图像分存技术的需求越来越多。适合彩色栅格地图分存的视觉密码方案由Verheul等人^[8]在1997年首次提出，称之为彩色视觉密码方案(CVCS)，方案中像素扩展度$ m = {c^{n-l}} $($ c $表示秘密图像颜色的数量，$n $表示参与者数量，$ l $表示恢复后错误颜色数量的最大值)，其需要一个特殊的假设：不同颜色的像素进行叠加的结果是黑色像素。实际上，不同颜色的像素进行叠加，会得到另外一种颜色的像素。为了解决假设不切合实际的问题，Verheul等人基于有限域，对该方案进行了拓展，像素扩展度$m={{c}^{k}}$($ k $表示授权集合中参与者最小值)。Ramachandran等人^[9]对彩色视觉密码方案进行了总体概括并比较了一些典型的彩色视觉密码方案。Bali等人^[10]将彩色视觉密码应用于保护文本的信息安全。Hou等人^[11]采用半色调技术，以降低对比度为代价，构造能够分享真彩色图像的( $k, n$ )-CVCS，但恢复图像的效果不理想。

Yang等人^[12]基于Shamir^[6]方案，通过复杂的计算恢复秘密图像。此类方案中，共享份大小存在小于秘密图像大小的可能性，而且恢复图像的视觉效果能够跟秘密图像保持一致。其代价是恢复过程中需要插值计算，解密速度慢。Chao等人^[13]构造了一种( $k, n$ )-CVCS，通过设计共享份分配矩阵，方案像素扩展度$ m = \left( {2 \times \left( {n-k + 1} \right)} \right)/n $。在秘密恢复过程中，需要额外的共享份分配矩阵参与计算，而且需要进行多次异或运算(XOR)，秘密恢复过程较复杂。Wang等人^[14]基于布尔运算提出了一种分享灰度图像和彩色图像的$ \left( {n, n} \right) $方案和分享二值图像的$(2, n) $方案。$ \left( {n, n} \right) $方案基于异或运算，像素扩展度$ m=1 $，能够实现秘密图像的完全恢复。为了能够分享更加一般的门限结构，Chen等人^[15]基于随机栅格，给出了一种( $k, n$ )-CVCS的构造方法，Kumar等人^[16]给出了一种概率型( $k, n$ )-CVCS的构造方法。Chen等人和Kumar等人的方案，像素扩展度都为1，减小了参与者在携带和使用过程中的开销，但在分享前，需要对秘密图像进行半色调处理，导致恢复图像的视觉效果不理想。

为了解决彩色视觉密码方案中像素扩展度较大、秘密图像颜色受限等问题，使其适用于彩色栅格地图分存，本文基于异或运算，给出了概率型( $k, n$ )彩色视觉密码的定义并构造了一种( $k, n$ )-CVCS。方案直接对真彩色栅格地图进行分享，在保留秘密恢复简单特点的基础上，能够改善栅格地图的恢复效果。

为方便描述，本文中所用到的符号及其含义如表 1所示。

本文在24位RGB(红、绿、蓝)颜色模型下进行秘密分享，所不同的是，本文将每个24位像素颜色作为一个整体，不分通道。本文基于异或运算，两个相同颜色按位进行异或运算得到黑色，任何颜色与黑色按位异或运算的结果是其本身。为了描述方便，本文中用0表示24位全为0的颜色，即黑色。

定义1  集合$ \mathit{\boldsymbol{C}} = ({c_1}, {c_2}, \ldots, {c_{{2^{24}}}}) $包含所有24位RGB模型中的颜色。

定义2  彩色像素进行异或运算指像素颜色按位进行异或运算，即

$ \begin{matrix} {{c}_{u}}\oplus {{c}_{v}}={{c}_{u}}_{0}{{c}_{u}}_{1}\ldots {{c}_{u}}_{23}\oplus {{c}_{v}}_{0}{{c}_{v}}_{1}\ldots {{c}_{v}}_{23}= \\ ({{c}_{u}}_{0}\oplus {{c}_{v}}_{0})({{c}_{u}}_{1}\oplus {{c}_{v}}_{1})\ldots ({{c}_{u}}_{23}\oplus {{c}_{v}}_{23})= \\ {{c}_{(u\oplus {{v}_{0}})}}{{c}_{(u\oplus {{v}_{1}})}}\ldots {{c}_{(u\oplus {{v}_{23}})}}={{c}_{(u\oplus v}}_{)} \\ \end{matrix} $

(1)

式中，$ {c_u}, {c_v}, {c_{(u \oplus v}}_) \in \mathit{\boldsymbol{C}} $, $ {{c}_{u0}},{{c}_{u1}},\cdots ,{{c}_{u23}},{{c}_{v0}},{{c}_{v1}},\cdots ,{{c}_{v23}},{{c}_{\left( u\oplus v \right)0}},{{c}_{\left( u\oplus v \right)1}},\cdots ,{{c}_{\left( u\oplus v \right)23}}\in \left\{ 0,1 \right\} $。

定义3  共享份进行异或运算指共享份中相同坐标的彩色像素其颜色逐一进行异或运算，即

$ {\mathit{\boldsymbol{S}}_u} \oplus {\mathit{\boldsymbol{S}}_v} = {S_u}\left( {i, j} \right) \oplus {S_v}\left( {i, j} \right) $

在对视觉密码定义研究的基础上，本节给出了基于异或运算的概率型彩色视觉密码定义。在分享彩色图像一个像素颜色$ S\left( {i, j} \right) $的过程中，通过恢复算法得到的非秘密像素颜色$ \overline {S\left( {i, j} \right)} $构成非秘密像素颜色集合$ \mathit{\boldsymbol{\bar C}}\left( {\mathit{\boldsymbol{\bar C}} \subseteq \mathit{\boldsymbol{C}}} \right) $，则$ \overline {S\left( {i, j} \right)} \ne S\left( {i, j} \right) $，$ {P_{\overline {S\left( {i, j} \right)} }} > 0$，$ \left\{ {S{\rm{ }}\left( {i, j} \right)} \right\} \cap = \mathit{\boldsymbol{\bar C = }}\emptyset $。

定义4  在概率型$ \left( {k, n} \right) $彩色视觉密码方案中，分享秘密图像一个像素颜色$S\left( {i, j} \right) $的过程中，存在一个大小为$ n \times 1 $的矩阵$ \mathit{\boldsymbol{B}} $，其决定了$ n $个共享份中对应坐标位置的像素颜色，满足以下3个条件：

1) 对于矩阵$ \mathit{\boldsymbol{B}} $，异或运算其任意$ k $个元素得到颜色$ r $，$ \forall \overline {S\left( {i, j} \right)} \in \bar C$且$ \overline {S\left( {i, j} \right)} \ne 0 $，满足$ {P_{S(i, j)}} = P{\rm{ }}\left( {r = S{\rm{ }}\left( {i, j} \right)} \right) > {P_{\overline {S{\rm{ }}(i, j)} }} = P{\rm{ }}\left( {r = \overline {S{\rm{ }}\left( {i, j} \right)} } \right) $；

2) 对于参与者集合$ \left\{ {1, 2, \cdots, n} \right\} $的子集$ \{ {i_1}, {i_2}, \cdots, {i_v}\} \left( {v < k} \right) $，异或运算矩阵$ B $任意 $v$ 个元素得到颜色 $r$ ，$ \forall c \in \mathit{\boldsymbol{C}} $且$ c≠0 $，满足$ {P_0} \ge {P_c} = P{\rm{ }}\left( {r = c} \right) = \rho $；

3) 对于矩阵$ \mathit{\boldsymbol{B}} $，异或运算其任意$ k $个元素得到颜色$ r $，满足下列情况之一：

(1) 非秘密像素颜色集合全部为黑像素，即$ \mathit{\boldsymbol{\bar C = }}\left\{ 0 \right\} $；

(2) 非秘密像素区域为噪声图像或偏暗的噪声图像，即$ \forall \overline {S\left( {i, j} \right)} \in \mathit{\boldsymbol{\bar C}}\left( {\left\{ {S\left( {i, j} \right) \cup \mathit{\boldsymbol{\bar C = C}}} \right\}} \right)$，$ \overline {S\left( {i, j} \right)} \ne 0 $，${P_0} \ge {P_{\overline {S\left( {i, j} \right)} }} = P\left( {r = \overline {S\left( {i, j} \right)} } \right) = \rho ' $。

补充说明：由于相同颜色异或运算的结果为0(黑色)，黑色相比其他颜色有其特殊性。为了方便说明问题以及证明方案的有效性，假设使用的彩色秘密图像中不包含黑色，并给出了对应的彩色视觉密码的定义。在该定义下构造的秘密分享算法，同样适用于彩色图像中包含黑色的情况。

条件1)对应恢复条件，表示在恢复图像中秘密像素颜色的恢复概率大于除黑色外所有非秘密像素颜色的恢复概率。${P_{S{\rm{ }}(i, j)}} $越大，秘密图像中的像素颜色在恢复图像中出现的可能性越大，视觉效果越好。由于相同颜色异或运算的结果为黑色，黑色的恢复概率存在大于秘密图像像素颜色的可能性，会导致恢复图像变暗，但不会影响秘密信息的恢复。

条件2)对应安全性条件，表示任意不满足门限结构的参与者无法获取关于秘密图像的任何信息。对于参与者集合$ \{ {i_1}, {i_2}, \cdots, {i_v}\} $，异或运算矩阵$ \mathit{\boldsymbol{B}} $中任意 $v$ 个元素得到颜色$ r $。除黑色外，$ r $可能为颜色集合$ \mathit{\boldsymbol{C}} $中任意一个元素且概率相等，得到的恢复结果为噪声图像或偏暗的噪声图像，得不到秘密图像的任何信息。

条件3)对应防串扰条件，表示在恢复图像中，非秘密像素颜色不会呈现特定的图像，防止与秘密图像产生串扰，影响秘密信息的恢复。

本节中，给出了概率型( $k, n$ )-CVCS的详细构造方法，一幅彩色秘密图像被加密成$ n $个无意义的噪声图像。主要思路是在文献[13]的构造方法上，通过设计扩展变换算子$ f $将颜色序列$ {c_1}, {c_2}, \cdots, {c_k}$扩展成颜色序列$ {e_1}, {e_2}, \cdots, {e_n} $，从$ {e_1}, {e_2}, \cdots, {e_n} $中任取$ k $个颜色有一定几率恢复秘密像素颜色$ S{\rm{ }}\left( {i, j} \right) $。

概率型( $k, n$ )-CVCS秘密分享过程具体步骤如下：

输入：参与者人数$ n $ ($n \ge 2 $)，$ 2 \le k \le n $，大小为$ a \times b $的彩色秘密图像$ \mathit{\boldsymbol{S}} $。

输出：$ n $个大小为$ a \times b $的共享份$ {S_1}, {S_2}, \cdots, {S_n} $。

1) 令$ i=0$，$ i $表示行计数器；

2) 令$ j=0 $，$ j $表示列计数器；

3) 随机产生$ k－1 $个颜色$ {c_1}, {c_2}, \cdots, {c_{k-1}} $；

4) 计算$ {c_k} = {c_1} \oplus {c_2} \oplus \cdots \oplus {c_{k-1}} \oplus S{\rm{ }}\left( {i, j} \right)$；

5) 进行扩展变换$ f{\rm{ }}({c_1}, {c_2}, \cdots, {c_k}) = {e_1}, {e_2}, \cdots, {e_n} $；

6) 矩阵$ \mathit{\boldsymbol{B = }}{\left[{{e_1}, {e_2}, \cdots, {e_n}} \right]^{\rm{T}}} $；

7) 将矩阵$ \mathit{\boldsymbol{B}} $中的颜色依次分配给共享份$ {\mathit{\boldsymbol{S}}_1}, {\mathit{\boldsymbol{S}}_2}, \cdots, {\mathit{\boldsymbol{S}}_n} $中对应坐标位置的像素；

8) 令$ j=j+1$，若$ j<b $，则转至步骤3)；否则转至步骤9)；

9) 令$ i=i+1$，若$i<a $，则转至步骤2)；否则分享流程结束。

通过该秘密分享过程，对彩色秘密图像$ \mathit{\boldsymbol{S}} $中的每个像素颜色进行分享，得到共享份$ {\mathit{\boldsymbol{S}}_1}, {\mathit{\boldsymbol{S}}_2}, \cdots, {\mathit{\boldsymbol{S}}_n} $。

扩展变换算子$ f $的构造思路是：对于本文中的( $k, n$ )-CVCS，从矩阵$ \mathit{\boldsymbol{B}} $中任取$ k $个颜色为${c_1}, {c_2}, \cdots, {c_k} $可能性越大，恢复秘密像素颜色$c $的可能性越大。设颜色序列$ {e_1}, {e_2}, \cdots, {e_n} $由$ x_1 $个$ c_1 $，$ x_2 $个$ c_2 $，…，$ x_k $个$ {c_k}(1 \le {x_1}, {x_2}, \cdots, {x_k} 且 {x_1} + {x_2} + \cdots + {x_k} = n) $组成，则$ P = \frac{{{x_1}{x_2} \cdots {x_k}}}{{C_n^k}} $表示取出的$ k $个颜色刚好为$ {c_1}, {c_2}, \cdots, {c_k} $的可能性。令$ y = {x_1}{x_2} \cdots {x_k} $，若$ y $越大，则$ P $越大。对$ y $求条件极值

$ \left\{ \begin{array}{l} {x_1} + {x_2} + \cdots + {x_k} = n\\ y = {x_1}{x_2} \cdots {x_k} \end{array} \right. $

(2)

当$ {x_1} = {x_2} = \cdots = {x_k} = n/k $时，$y $取得极大值。由于$ {x_1}, {x_2}, \cdots, {x_k} $都是整数，因此取$ {x_1} = {x_2} = \cdots = {x_t} = s + 1$，$ {x_t} = {x_{t + 1}} = \cdots = {x_k} = s{\rm{ }}(s = \left| {n/k} \right|, t = n\;\bmod \;k) $时得到$ y $的极大值。

扩展变换算子$ f $具体构造过程如下：

1) 令$ s = \left| {n/k} \right| $，$ t = n\;\bmod \;k $；

2) 对于颜色序列$ {c_1}, {c_2}, \cdots, {c_k} $，前$ t{\rm{ }}\left( {1 \le t \le k} \right) $个颜色，每个颜色扩展成$ s+1 $个颜色；后$ k－t $个颜色，每个扩展成$ s $个颜色，得到颜色序列$ {d_1}, {d_2}, \cdots, {d_n} $；

3) 将$ {d_1}, {d_2}, \cdots, {d_n} $进行随机排列得到$ {e_1}, {e_2}, \cdots, {e_n} $。

任取$ k $个共享份进行异或运算可恢复秘密图像

$ \begin{array}{c} \mathit{\boldsymbol{R = }}{\mathit{\boldsymbol{S}}_{{i_1}}} \oplus {\mathit{\boldsymbol{S}}_{{i_2}}} \oplus \cdots \oplus {\mathit{\boldsymbol{S}}_{{i_k}}}\\ \left\{ {{i_1}.{i_2}, \cdots ,{i_k}} \right\} \subseteq \left\{ {1,2, \cdots ,n} \right\} \end{array} $

(3)

本节对方案的有效性进行分析，证明方案能够恢复秘密信息且满足安全性，恢复图像中非秘密像素颜色构成的图像不会与秘密像素颜色构成的图像发生串扰。

引理1  若$ {c_1}, {c_2}, \cdots, {c_t} $为$ t $个确定颜色($ t≥0 $)，$ c $为随机产生的颜色，异或运算$ {c_1} \oplus {c_2} \oplus \cdots \oplus {c_t} \oplus c{\rm{ }}\left( {{\rm{ }}{c_1}, {c_2}, \cdots, {c_t}, c \in \mathit{\boldsymbol{C}}{\rm{ }}} \right) $得到一个随机颜色。

证明

令$ c\prime = {c_1} \oplus {c_2} \oplus \cdots \oplus {c_t} $，则$ c′ $为确定颜色。$ c\prime \oplus c$为一个确定颜色异或运算一个随机颜色，结果随机。

证毕。

定理1  任意$ k $个共享份能够恢复出秘密图像中的信息。

证明 在矩阵$ \mathit{\boldsymbol{B}} $中，颜色$ {c_1}, {c_2} \cdots, {c_t}\left( {t = n\;\bmod \;k, s = \left\lfloor {n/k} \right\rfloor } \right) $各包含$ s+1 $个，$ {c_{t + 1}}, {c_{t + 2}}, \cdots, {c_k} $各包含$ s $个。从矩阵$ \mathit{\boldsymbol{B}} $中任取$ k $个颜色，设为${c_{{i_1}}}, {c_{{i_2}}}, \cdots, {c_{{i_k}}} $，若$ {c_{{i_1}}}, {c_{{i_2}}}, \cdots, {c_{{i_k}}} $刚好为颜色序列$ {c_1}, {c_2}, \cdots, {c_k} $，能够恢复出秘密像素颜色$ S(i, j) $，其概率为

$ P = \frac{{{{\left( {s + 1} \right)}^t}{s^{k-t}}}}{{C_n^k}} $

(4)

否则令$ r = {c_{{i_1}}} \oplus {c_{{i_2}}} \oplus \cdots \oplus {c_{{i_k}}} = {c_{{j_1}}} \oplus {c_{{j_2}}} \oplus \cdots \oplus {c_{{j_v}}} $($ 0≤v<k $，若${c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{i_v}}} $中有奇数个相同颜色变量，只保留其中一个，若有偶数个相同颜色变量，全部去掉，得到$ {c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_v}}} $，则$\{ {c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_v}}}\} \left\{ {{c_1}, {c_2}, \cdots, {c_k}} \right\} $)，计$ P\left( {v = 0} \right) = {\rho _1}, P\left( {0 < v < k} \right){\rm{ = }}{\rho _2}\left( {0 \le {\rho _1}, {\rho _2} \le 1, {\rho _1} + {\rho _2} = 1} \right) $。

1) 当$ v=0 $时，$ {P_{\overline {S\left( {i, j} \right)} }} = P\left( {r = \overline {S\left( {i, j} \right)} } \right) = {\rho _1}\left( {\mathit{\boldsymbol{\bar C = }}\left\{ 0 \right\}} \right) $；

2) 当$0<v<k $时，计$ P({c_k} \notin ({c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_v}}})) = {\rho _3} $, $ P({c_k} \in ({c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_v}}})) = {\rho _4}(0 \le {\rho _3}, {\rho _4} \le 1{\rm{ }}, {\rm{ }}{\rho _3} + {\rho _4} = 1{\rm{ }}) $。若${c_k} \notin ({c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_v}}}) $，由于颜色$ {c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_v}}} $全由秘密分享过程中的步骤1随机产生，则$ r = {c_{{j_1}}} \oplus {c_{{j_2}}} \oplus \cdots \oplus {c_{{j_v}}}$结果随机，可得

$ \begin{array}{c} {{P'}_{S\left( {i, j} \right)}} = {{P'}_0} = {{P'}_{\overline {S\left( {i, j} \right)} }} = \\ P\left( {r = \overline {S\left( {i, j} \right)} } \right) = \\ {\rho _2} \times {\rho _3} \times \left( {1/{2^{24}}} \right)\left( {\left\{ {S\left( {i, j} \right)} \right\} \cup \mathit{\boldsymbol{\bar C = C}}} \right) \end{array} $

(5)

若$ {{c}_{k}}\in ({{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{v}}}}) $，设$ {{c}_{{{j}_{v}}}}={{c}_{k}} $，则得到$ r={{c}_{{{j}_{1}}}}\oplus {{c}_{{{j}_{2}}}}\oplus \cdots \oplus {{c}_{jv-1}}\oplus {{c}_{1}}\oplus {{c}_{2}}\oplus \cdots \oplus {{c}_{k-1}}\oplus S\rm{ }\left( i, j \right) $。

由于$ \{{{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \ldots, {{c}_{{{j}_{v}}}}\}\subset \left\{ {{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k}} \right\} $，${{c}_{{{j}_{v}}}}={{c}_{k}} $，可得$ \{{{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{v-1}}}}\}\subset \{{{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k-1}}\} $，因此$ r={{c}_{{{h}_{1}}}}\oplus {{c}_{{{h}_{2}}}}\oplus \cdots \oplus {{c}_{{{h}_{w}}}}\oplus S\rm{ }\left( i, j \right) $ (从$ {{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k-1}} $中除去$ {{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{v-1}}}} $得到$ {{c}_{{{h}_{1}}}}, {{c}_{{{h}_{2}}}}, \cdots, {{c}_{{{h}_{w}}}} $，$ \{{{c}_{{{h}_{1}}}}, {{c}_{{{h}_{2}}}}, \cdots, {{c}_{{{h}_{w}}}}\}\subset \left\{ {{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k}} \right\} $，$ 1\le w\le k-1 $)。由引理1知，$r $随机，可得

$ \begin{array}{c} {{P''}_{S\left( {i, j} \right)}} = {{P''}_0} = {{P''}_{\overline {S\left( {i, j} \right)} }} = \\ P\left( {r = \overline {S\left( {i, j} \right)} } \right) = \\ {\rho _2} \times {\rho _4} \times \left( {1/{2^{24}}} \right) \end{array} $

(6)

综上所述，若$ {\rho _1} = 1 $，则$ \mathit{\boldsymbol{\bar C}} = \left\{ 0 \right\}$，非秘密像素颜色集合中只有黑色，可推出若$ \overline {S\left( {i, j} \right)} \ne 0 $，$ {P_{\overline {S\left( {i, j} \right)} }} = 0$，$ {P_{S(i, j)}} = \frac{{{{\left( {s + 1} \right)}^t}{s^{kt}}}}{{C_n^{^k}}} $，则${P_{S(i, j)}} > {P_{\overline {S(i, j)} }} $，满足定义4中的恢复条件。若${\rho _1} < 1 $，$\forall \overline {S\left( {i, j} \right)} \in \mathit{\boldsymbol{\bar C}}\left( {\left\{ {S\left( {i, j} \right)} \right\} \cup \mathit{\boldsymbol{\bar C}} = \mathit{\boldsymbol{C}}{\rm{ }}} \right) $，$ \overline {S\left( {i, j} \right)} \ne 0 $，则非秘密像素$ \overline {S\left( {i, j} \right)} $的恢复概率为

$ \begin{array}{c} {P_{\overline {S{\rm{ }}(i, j)} }} = \left( {1-P} \right)(P{\prime _{\overline {S{\rm{ }}(i, j)} }} + P\prime {\prime _{\overline {S{\rm{ }}(i, j)} }}) = \\ (1-\frac{{{{\left( {s + 1} \right)}^t}{s^{k-t}}}}{{C_n^{^k}}})({\rho _2} \times {\rho _3} \times (1/{2^{24}}) + \\ {\rho _2} \times {\rho _4} \times (1/{2^{24}})) = \\ (1 - \frac{{{{\left( {s + 1} \right)}^t}{s^{k - t}}}}{{C_n^{^k}}}) \times {\rho _2} \times (1/{2^{24}}) \end{array} $

(7)

秘密像素颜色$ S(i, j) $的恢复概率为

$ \begin{array}{c} {P_{S{\rm{ }}(i, j)}} = P + \left( {1-P} \right)(P{\prime _{S{\rm{ }}(i, j)}} + P\prime {\prime _{S{\rm{ }}(i, j)}}) = \\ \frac{{{{\left( {s + 1} \right)}^t}{s^{k-t}}}}{{C_n^{^k}}} + (1-\frac{{{{\left( {s + 1} \right)}^t}{s^{k - t}}}}{{C_n^{^k}}})\\ ({\rho _2} \times {\rho _3} \times (1/{2^{24}}) + {\rho _2} \times {\rho _4} \times (1/{2^{24}})) = \\ \frac{{{{\left( {s + 1} \right)}^t}{s^{k - t}}}}{{C_n^{^k}}} + (1 - \frac{{{{\left( {s + 1} \right)}^t}{s^{k - t}}}}{{C_n^{^k}}}) \times \\ {\rho _2} \times (1/{2^{24}}) \end{array} $

(8)

可得$ {P_{S(i, j)}} > {P_{\overline {S(i, j)} }} $，满足定义4中的恢复条件，能够恢复秘密图像。

证毕。

定理2  任意少于$ k $个共享份得不到秘密图像的任何信息。

证明 对于参与者集合$ \left\{ {1, 2, \cdots, n} \right\} $的子集$ \{ {i_1}, {i_2}, \cdots, {i_v}\} \left( {2 \le v < k} \right) $，从矩阵$ \mathit{\boldsymbol{B}} $中任取 $v$ 个颜色，计为$ {c_{{i_1}}}, {c_{{i_2}}}, \cdots, {c_{{i_v}}}$，令$ r = {c_{{i_1}}} \oplus {c_{{i_2}}} \oplus \cdots \oplus {c_{{i_v}}} = {c_{{j_1}}} \oplus {c_{{j_2}}} \oplus \cdots \oplus {c_{{j_u}}} $ ($0≤u≤v $，若$ {c_{{i_1}}}, {c_{{i_2}}}, \cdots, {c_{{i_v}}} $中有奇数个相同颜色变量，只保留其中一个，若有偶数个相同颜色变量，全部去掉，得到$ {c_{{j_1}}}, {c_{{j_2}}}, \cdots, {c_{{j_u}}} $，则$ \{{{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}}\}\subset \left\{ {{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k}} \right\} $)。计$P\rm{ }\left( u=0 \right)={{\mu }_{1}} $，$ P\left( 0<u\le v \right)={{\mu }_{2}} $，$ 0\le {{\mu }_{1}}<1 $，$ 0<{{\mu }_{2}}\le 1 $，$ {{\mu }_{1}}+{{\mu }_{2}}=1 $。

1) 当$ u=0 $时，$ {{{P}'}_{0}}=P\left( r=0 \right)={{\mu }_{1}} $；

2) 当$ 0<u≤v $时，计$ P({{c}_{k}}\notin ({{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}}))\rm{ }={{\mu }_{3}} $，$ P({{c}_{k}}\in ({{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}}))={{\mu }_{4}}~(\rm{ }0\le {{\mu }_{3}}, {{\mu }_{4}}~\le 1, \rm{ }{{\mu }_{3}}+{{\mu }_{4}}=1\rm{ }) $。若$ {{c}_{k}}\notin ({{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}}) $，可知$ {{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}} $随机产生，$ r={{c}_{{{j}_{1}}}}\oplus {{c}_{{{j}_{2}}}}\oplus \cdots \oplus {{c}_{{{j}_{u}}}} $结果随机，则$ \forall c\in C $，$\forall c\in C\rm{, }{{P}_{c}}^{\prime \prime }=P\left( r=c\prime \right)={{\mu }_{2}}\times {{\mu }_{3}}\times (1/{{2}^{24}}) $。

若$ {{c}_{k}}\in ({{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}}) $，设$ {{c}_{{{j}_{u}}}}={{c}_{k}} $，则可得$ r={{c}_{{{j}_{1}}}}\oplus {{c}_{{{j}_{2}}}}\oplus \cdots \oplus {{c}_{j_{u-1}}}\oplus {{c}_{1}}\oplus {{c}_{2}}\oplus \cdots \oplus {{c}_{k-1}}\oplus S\rm{ }\left( i, j \right) $。

由于$ \{{{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u}}}}\}\subset \left\{ {{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k}} \right\}$，$ {{c}_{{{j}_{u}}}}={{c}_{k}} $，可得$ \{{{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{j_{u-1}}}\}\subset \{{{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k-1}}\} $，因此$ r={{c}_{{{h}_{1}}}}\oplus {{c}_{{{h}_{2}}}}\oplus \cdots \oplus {{c}_{{{h}_{w}}}}\oplus S\rm{ }\left( i, j \right) $(从${{c}_{1}}, {{c}_{2}}, \cdots, {{c}_{k-1}} $中除去$ {{c}_{{{j}_{1}}}}, {{c}_{{{j}_{2}}}}, \cdots, {{c}_{{{j}_{u-1}}}} $得到$ {{c}_{{{h}_{1}}}}, {{c}_{{{h}_{2}}}}, \cdots, {{c}_{{{h}_{w}}}} $，$ \{{{c}_{{{h}_{1}}}}, {{c}_{{{h}_{2}}}}, \cdots, {{c}_{{{h}_{w}}}}\}\subset \left\{ {{c}_{2}}, {{c}_{2}}, \cdots, {{c}_{k}} \right\} $，$ 1≤w≤k-1 $)，由引理1知，$ r $随机，则$ \forall c\in C $，$ P_{_{c}}^{^{'''}}=P\rm{ }\left( r=c \right)={{\mu }_{2}}\times {{\mu }_{4}}\times (1/{{2}^{24}}) $。

综上所述，黑色的恢复概率

$ \begin{matrix} {{P}_{0}}={{P}_{0}}\prime +{{P}_{c}}\prime \prime +{{P}_{c}}\prime \prime \prime = \\ {{\mu }_{1}}+{{\mu }_{2}}\times {{\mu }_{3}}\times (1/{{2}^{24}})+ \\ {{\mu }_{2}}\times {{\mu }_{4}}\times (1/{{2}^{24}})= \\ {{\mu }_{1}}+{{\mu }_{2}}\times (1/{{2}^{24}}) \\ \end{matrix} $

(9)

其他颜色的恢复概率为

$ \begin{matrix} {{P}_{S\rm{ }(i, j)}}=P_{_{S\rm{ }(i, j)}}^{\prime \prime }+P_{_{S\rm{ }(i, j)}}^{\prime \prime \prime }= \\ {{\mu }_{2}}\times {{\mu }_{3}}\times (1/{{2}^{24}})+ \\ {{\mu }_{2}}\times {{\mu }_{4}}\times (1/{{2}^{24}})= \\ {{\mu }_{2}}\times (1/{{2}^{24}}) \\ \end{matrix} $

(10)

式中，$ \forall c\in C $，$ c≠0 $。则可推出${{P}_{0}}\ge {{P}_{c}}={{\mu }_{2}}\times (1/{{2}^{24}}) $，满足定义4中的安全性条件，得到的恢复结果为噪声图像或偏暗的噪声图像，保证了秘密分享的安全性。

证毕。

定理3  任意$ k $个共享份异或运算得到的恢复图像中，非秘密像素颜色$ \overline{S\rm{ }\left( i, j \right)}$所构成的图像不会与秘密图像发生串扰，影响秘密信息的恢复。

证明 从定理1可知，存在以下两种情况:

1) 若在分享秘密图像的所有颜色过程中${{\rho }_{1}}=1 $始终成立，即非秘密像素颜色集合$ \mathit{\boldsymbol{\bar{C}=}}\left\{ 0 \right\} $，满足定义4防串扰条件3)中的情况(1)；

2) $ \forall \overline{S\rm{ }\left( i, j \right)}\in \mathit{\boldsymbol{\bar{C}}}\rm{ }\left( \left\{ S\rm{ }\left( i, j \right) \right\}\cup \mathit{\boldsymbol{\bar{C}}}=\mathit{\boldsymbol{C}} \right) $，$ \overline{S\rm{ }\left( i, j \right)}\ne 0$，非秘密像素$ \overline{S\rm{ }\left( i, j \right)} $的恢复概率为

$ \begin{matrix} {{P}_{\overline{S\rm{ }(i, j)}}}=\left( 1-P \right)(P_{\overline{_{S\rm{ }(i, j)}}}^{\prime }+P_{\overline{_{S\rm{ }(i, j)}}}^{\prime \prime })= \\ (1-\frac{{{\left( s+1 \right)}^{t}}{{s}^{k-t}}}{C_{_{n}}^{^{k}}})({{\rho }_{2}}\times {{\rho }_{3}}\times (1/{{2}^{24}})+ \\ {{\rho }_{2}}\times {{\rho }_{4}}\times (1/{{2}^{24}}))= \\ (1-\frac{{{\left( s+1 \right)}^{t}}{{s}^{k-t}}}{C_{_{n}}^{^{k}}})\times {{\rho }_{2}}\times (1/{{2}^{24}}) \\ \end{matrix} $

(11)

黑色的恢复概率为

$ \begin{matrix} {{P}_{0}}={{\rho }_{1}}+\left( 1-P \right)({{P}_{0}}\prime +{{P}_{0}}\prime \prime )= \\ {{\rho }_{1}}+(1-\frac{{{\left( s+1 \right)}^{t}}{{s}^{k-t}}}{C_{_{n}}^{^{k}}})\times {{\rho }_{2}}\times (1/{{2}^{24}}) \\ \end{matrix} $

(12)

所以${{P}_{0}}\ge {{P}_{\overline{S\rm{ }(i, j)}}}=(1-\frac{{{\left( s+1 \right)}^{t}}{{s}^{k-t}}}{C_{_{n}}^{^{k}}})\times {{\rho }_{2}}\times (1/{{2}^{24}}) $，满足定义4防串扰条件3)中的情况(2)。

综上所述，在恢复图像中非秘密像素颜色$ \overline{S\rm{ }\left( i, j \right)} $构成的图像不会与秘密图像发生串扰，影响秘密信息的恢复。

证毕。

为验证方案的有效性，利用本文算法构造出的(3, 4)方案对栅格地图进行分存，并对实验结果进行分析。

根据第3节设计的方案，在秘密分享过程中，对于(3, 4)方案，先随机产生两个颜色$ {{c}_{1}}, {{c}_{2}}$，计算$ {{c}_{3}}={{c}_{1}}\oplus {{c}_{2}}\oplus S\rm{ }\left( i, j \right) $，由扩展变换$f\rm{ }({{c}_{1}}, {{c}_{2}}, {{c}_{3}}) $先得到$ {{d}_{1}}={{c}_{1}}, {{d}_{2}}={{c}_{1}}, {{d}_{3}}={{c}_{2}}, {{d}_{4}}={{c}_{3}} $。对$ {{d}_{1}}, {{d}_{2}}, {{d}_{3}}, {{d}_{4}} $进行随机排列得到$ {{e}_{1}}, {{e}_{2}}, {{e}_{3}}, {{e}_{4}} $，则可推出$ {{P}_{S\rm{ }(i, j)}}=1/2+1/{{2}^{25}} $，${{P}_{\overline{S\rm{ }(i, j)}}}=1/{{2}^{25}}\left( \left\{ S\rm{ }\left( i, j \right) \right\}\cup \mathit{\boldsymbol{\bar{C}}}=\mathit{\boldsymbol{C}} \right) $。则$ {{P}_{S\rm{ }(i, j)}}>{{P}_{\overline{S\rm{ }(i, j)}}} $，满足恢复条件，参与者能够得到秘密图像中的信息；非秘密像素颜色$ \overline{S\rm{ }\left( i, j \right)} $构成的图像呈杂乱无章的噪声图像，不会与秘密像素颜色构成的图像发生串扰。具体实验效果如图 1所示。其中，$\mathit{\boldsymbol{S}} $表示待分存的栅格地图，$ {{\mathit{\boldsymbol{S}}}_{1}}, {{\mathit{\boldsymbol{S}}}_{2}}, {{\mathit{\boldsymbol{S}}}_{3}}, {{\mathit{\boldsymbol{S}}}_{4}}$表示共享份，$ {{\mathit{\boldsymbol{R}}}_{1}}, {{\mathit{\boldsymbol{R}}}_{2}}, {{\mathit{\boldsymbol{R}}}_{3}}, {{\mathit{\boldsymbol{R}}}_{4}} $是随机选择3个共享份XOR后得到的恢复图像。从图 1可以看出，任意单个、两个共享份XOR得到的恢复图像呈杂乱无章的噪声图像，从中无法获取秘密图像的任何信息。

在彩色视觉密码中，现缺乏一种有效的性能参数衡量恢复图像的视觉效果。峰值信噪比(PSNR)是目前评价图像视觉效果较好的一种客观标准。其公式为

$ {\rm{PSNR = 10}} \times {\rm{lo}}{{\rm{g}}_{10}}\left( {\frac{{{D^2}ab}}{{\sum\limits_{x = 1}^a {\sum\limits_{y = 1}^b {{{\left( {R\left( {i, j} \right)-S\left( {i, j} \right)} \right)}^2}} } }}} \right) $

(13)

式中，$ D $是像素的峰值，$ a $和$ b $分别是恢复图像的高度和宽度，取10倍的以10为底的对数，目的是将计算出来的值换算成标准分贝(dB)，其值越大，图像视觉效果越好。文献[15-16]采用半色调技术，将连续色调彩色图像转换成半色调彩色图像进行分享。半色调是基于人眼视觉特性和图像的呈色特性，利用数字、计算机等工具，在二值(或多色)设备上实现图像最优再现的一门技术。半色调是利用人眼的低通特性，当在一定距离下观察时，人眼将图像中空间上接近的部分视为一个整体。利用此特性，人眼观察到的半色调图像局部平均灰度近似于原始图像的局部平均灰度值，从而整体上形成连续色调的效果。

图 2是本文方案与文献[15-16]中方案关于(3, 4)-CVCS恢复图像的视觉效果对比图。文献[15-16]需先对秘密图像进行半色调处理，再进行分享。半色调技术会降低原始图像的质量，加之像素不扩展方案在图像分享过程中会降低图像质量，导致恢复图像的视觉效果较差。本文方案直接对秘密图像进行分享，无需半色调处理，在一定程度上能够提高恢复图像的视觉效果。从图 2可以看出本文方案在视觉效果上具有更优的结果。通过计算，文献[15-16]方案与本文方案的恢复图像峰值信噪比分别是10.3、10.4、16.7，该参数在一定程度上能够反映恢复图像的视觉效果。

在表 2中，本文方案与相关方案在性能参数上进行了比较，包括门限结构、像素扩展、计算复杂度等。

1) 在存取结构方面，文献[12-13, 15-16]和本文方案适用于任意门限结构，因此具有更加丰富的应用场景。

2) 在像素扩展方面，对于门限结构都为$ (k, n) $的方案，文献[12, 15-16]和本文中的方案像素扩展度$m=1 $，共享份在存储和传输过程中不会产生额外的开销。其中文献[12]基于Shamir方案，通过多项式插值恢复秘密图像，得到的方案无像素扩展；文献[15-16]和本文通过概率型视觉密码的方法进行方案设计，得到的结果无像素扩展。

3) 在加密图像种类上，文献[12-16]和本文中的方案能够实现对彩色图像进行分享，彩色图像所呈现的色彩更接近于真实的自然界，相比二值图像更加美观且具有更加丰富的图像信息，具有更好的应用价值。

4) 对彩色图像进行分享，一般的视觉密码方案需先对图像进行半色调处理，这种处理方式导致彩色图像的视觉效果降低。本文方案直接对彩色图像进行处理，能够得到恢复效果更佳的秘密图像。

5) 在秘密图像恢复过程中的计算复杂度方面，文献[12]基于Shamir方案，在秘密恢复过程中需要进行多项式插值，计算复杂度较大；文献[13]在秘密恢复过程中，需要额外的共享份分配矩阵参与计算，而且需要进行多次异或运算，秘密恢复过程较复杂。文献[15-16]和本文方案在秘密恢复过程中，只需简单的异或运算，具有较低的计算复杂度。

本文对彩色栅格地图分存算法进行了研究，构造了一种基于异或运算的概率型$ (k, n) $彩色视觉密码方案，给出了秘密分享和恢复算法，并从理论上对方案的有效性进行了证明，将方案应用到彩色栅格地图的分存中，与其他方案的实验结果比较可以看出，本文方案在实现$ (k, n) $门限结构的前提下，改善了恢复后栅格地图的视觉效果且无像素扩展。