Visual Cryptography from Halftone Error Diffusion - Visual Cryptography and Secret Image Sharing - page 9

1.3 Halftone VSS Construction Using Error Diffusion
The introduced methods for halftone VSS are built upon the fundamental
principles of conventional VSS. Given a secret halftone image and multi-
ple grayscale images, halftone shares are generated such that the resultant
halftone shares are no longer random patterns, but take meaningful visual
images. Without loss of generality, the k-out-of-n scheme is described in the
following.
1.3.1 Share Structure
The first step in constructing a halftone VSS scheme is to construct the un-
derlying k-out-of-n VSS scheme where a secret image pixel is encoded into
pixels in each share. is the VSS pixel expansion and only a function of (k;n).
Furthermore, in halftone VSS, a share image is divided into nonoverlapping
halftone cells of size q = v 1 v 2 where q > . A secret image pixel is encoded
into one halftone cell in each share. Within the q pixels in a halftone cell,
only pixels called secret information pixels (SIPs) actually carry the secret
information. Here is exactly the VSS pixel expansion. Since SIPs are not
designed to carry share visual information, q 2 is desirable for good share
image quality.
It is required that when all qualified shares are stacked together, only the
secret visual information is revealed. Thus, besides SIPs, auxiliary pixels that
are forced to be black (value 1) are also introduced. These pixels are called
auxiliary black pixels (ABP). In each halftone cell, there are x ABPs. ABPs
are deliberately introduced into the shares so that some ABPs on one share
block the visual information of the other shares. Thus, when qualified shares
are stacked together, only the secret visual information is revealed on the
reconstructed image as a result of the OR operation. In each halftone cell, the
remaining qx pixels that are neither SIPs or ABPs are assigned to carry
the visual information of the shares.
An example of the halftone cells in a 2-out-of-2 scheme is shown in Fig-
ure 1.5 where the 1st and 2nd pixels in each cell are SIPs. The 3rd pixel in
share 1 and the 4th pixel in share 2 are ABPs. When stacking two shares to-
gether, the result is a white pixel with contrast 1=4. The 4th pixel in share 1
and the 3rd pixel in share 2 are assigned values to carry visual information of
the shares. They can take a value of 0 or 1, which will not affect the decoded
image.
There should be a sucient number of ABPs in the shares so that the
visual information of one share is completely blocked by the ABPs on the
other shares. Since the ABPs are not designed to carry visual information,
the number of ABPs in a share is to be minimized as follows. Let p(i;j) =
[p 1 (i;j);p 2 (i;j);:::;p n (i;j)] T be the vector where p l (i;j) is the (i;j)th pixel