Resolving the Alignment Problem in Visual Cryptography - Visual Cryptography and Secret Image Sharing - page 292

of share images are considered. First, the share images are misaligned by
integer number of subpixels (less than the pixel expansion). This part mainly
comes from [8]. In such a case, the secret image can still be observed as
its complementary image. Second, the share images are misaligned by less
than one subpixel. This part mainly comes from [16]). Conditions that the
secret image can still be recovered are studied, and the different misalignment
tolerances of large and small subpixels are compared. The results indicate
that the VCS, by itself, has some misalignment tolerance. At last, we provide
a misalignment tolerant VCS based on the trade-off between the usage of large
and small subpixels.
11.2 Preliminaries
In the VCS, there is a secret image that is encrypted into some shares. The
secret image is called the original secret image for clarity, and the shares are
the encrypted images (and are called the transparencies if they are printed).
When a qualified set of shares (transparencies) are stacked together, it gives
a visual image that is almost the same as the original secret image, we call it
the recovered secret image. In the case of black and white images, the original
secret image is represented as a pattern of black and white pixels. Each of
these pixels is divided into subpixels, which themselves are encoded as black
and white to produce the shares. The recovered secret image is also a pattern
of black and white subpixels that should visually reveal the original secret
image if a qualified set of shares is stacked.
In order to simplify the discussion, in this paper, we will only consider the
black and white VCS, where black pixels are denoted by 1 and white pixels
are denoted by 0.
By a (k;n)-VCS we mean a scheme where the original secret image is
divided into n shares, which are distributed to n participants. Any subgroup
of k out of these n participants can get a recovered secret image, but any
subgroup consisting of less than k participants does not have any information
other than the size about the original secret image.
For a vector v 2 GF m (2), we denote by w(v) the Hamming weight of the
vector v, i.e., the number of nonzero coordinates in v. A (k;n)-VCS, denoted
by (C 0 ;C 1 ), consists of two collections of nm binary matrices C 0 and C 1 .
To share a white (resp. black) pixel, a dealer (the one who sets up the system)
randomly chooses one of the matrices, called a share matrix, in C 0 (resp: C 1 )
and distributes its rows (representing a pattern of subpixels in the share) to
the n participants of the scheme, giving row i to participant i, i = 1; ;n.
More precisely, we give a formal denition of the (k;n)-VCS as follows:
Definition 1 Let k, n, m be nonnegative integers, l and h be positive numbers