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

ever, all these works are based at the pixel level, i.e., to reduce the number of
subpixels that represent a pixel of the original secret image.
We notice that, the final goal of reducing the pixel expansion is to re-
duce the size of the transparencies that are distributed to the participants,
because smaller transparencies are easier to transport. However, the size of
the subpixels that are printed on the transparencies affects the final size of
the transparencies; in fact, the size of the transparencies is the product of the
size of the subpixels and the number of the subpixels in each transparency.
Unfortunately, there is a dilemma when one tries to determine the size of the
subpixels: When the subpixel size is large, it is easy to align the shares (most
publications in the literature require aligning the shares precisely in the de-
crypting phase), but the large subpixel size will result in large transparencies.
On the other hand, when the subpixel size is small, it is relatively hard to align
the shares, but smaller transparencies result. From the point of view of the
participants of the VCS, the goal is to align the shares easily and have small
transparencies as well. Table 11.1 shows the relationship between the size of
the subpixels of the transparencies and the ease to align them (more compar-
isons will be given in Table 11.5 later). Hence, there is a trade-off between the
size of the subpixels of the transparencies and the ease to align them.

TABLE 11.1
The advantages and disadvantages of large and small subpixels.
size of the
subpixels

advantages disadvantages

larger easier to align larger transparency size

smaller smaller transparency size harder to align

The usual way of tackling the alignment problem of the VCS is by adding
frames to the shares. To align the shares one just needs to align the frames. Yan
et al. [13] employed the Walsh transform to embed marks in both of the shares
so as to find the alignment position of these shares. However, both methods
need to align the transparencies precisely. Besides, Kobara and Imai [6] con-
sidered a different problem. They calculated the visible space when viewing
the transparencies. The results are somehow related to the alignment prob-
lem, but not exactly, as [6] has no discussion about alignment at all. Kobara
and Imai [6] do not consider the stacking of more than two shares. Nakajima
and Yamaguchi [9] proposed a (2; 2), extended VCS, which the secret image
and shares are natural images. Their scheme can simultaneously reduce the
alignment diculty. However, their scheme does not hold the perfect security
like a secret sharing scheme.
In fact, the precise alignment of small subpixels is not critical. The secret
image can still be recovered visually even if the participants do not align the
transparencies precisely. This phenomenon helps to determine the size of the
subpixels printed on the transparencies.
This chapter focuses on some recent results about the alignment problem
of the visual cryptography scheme [8, 16]. Two kinds of alignment problems