1. Introduction

1.1 History

 2. The PHSCologram method

2.1 Creation of imagery

If the images are stored in columnar format and are all the same size, the basic algorithm can be implemented in a few lines of code, as in this pseudo code example.

open all input files and the output file

For(each column in image X)
        for(each image I) {
                read column X from image I
                stretch column by a factor of N
                write column to output }

close all files

Due to the large volume of output data (a 30"x40" PHSCologram at 400 pixels per inch takes over 700 Mb), the output image is usually written directly to tape, rather than being stored on disk first. Ideally, we would like to connect the interleaving computer directly to the output device.

The barrier screen is constructed on the same output device and at the same output resolution as the image. The basic algorithm for an N-image barrier screen is to write N-1 opaque (black) lines followed by one clear line. Writing more clear lines with less black lines increases the amount of light permitted through the barrier, at the expense of reduced clarity.

 2. Rotated Interleaving

2.1 Limitations of normal interleaving

While the above method has broad reaching applications and presents numerous advantages over previous methods of creating autostereoscopic lenticular and parallax barrier images, it has a number of limitations, mostly related to inflexibilities of output devices.

Barrier screen and lenticular images created by photographic means are often discussed in units of pitch, or the number of lenses or lines per inch in the lenticular or barrier screen. The pitch is trivially related to the output resolution and the number of images in a digitally interleaved image by the following formula:

pitch=resolution/num_images
Where pitch is the number of lines per unit of the completed autostereogram, resolution is the number of pixels per unit available from the output imaging device, and images is the number of images in the autostereogram.

Since images must be an integer not less than 2, there are only a finite number of possible resolutions. For example, if our output imaging device has a resolution of 406.4 pixels per inch (from 16 pixels per mm), 13 images yields a pitch of 31.26 lines per inch. 12 images yields a pitch of 33.87 lines per inch. Other pitches, such as 32 lines per inch, are then unavailable without changing the resolution of the output imaging device. The following table shows some of the pitches available relative to the number of images:

If an output device were available with infinitely variable resolution, this would not be a consideration, but most available imaging devices are only capable of certain resolutions, related to their gear or screw mechanism.

This is a severe limitation when working with lenticular material, which must be created to exactly match one of the pitches available on the desired output imaging device. This is far more expensive and time consuming than using available lenticular material, which is unlikely to match the available pitches.

Another limitation arises from the loss of resolution and light from the use of large numbers of images with a parallax barrier. the barrier screen blocks, ideally (N-1) of the N images. The more images used, the less light is transmitted. The percent of light transmitted by a barrier screen image is related number of images by the following formula:

percent=1/num_images ideal case
percent=open_cols/num_images real-world case

For 13 images, 7.7% of the light is transmitted by the barrier screen . While this is an acceptable amount of light for most applications, let us examine the result for 100 images with the resolution discussed above. The pitch for 100 images would be 4.064 lines per inch, and the amount of light transmitted would be 1%. This pitch and brightness are unacceptable, but we would still like to be able to use larger number of images for a variety of purposes.

In the method presented above, images are output so that the direction of lenticulation (e.g. the direction of the interleaving lines) is aligned with the rows and columns of the output device. While conceptually simple, both in understanding and implementation, research has shown this to be virtually the worst choice for many applications.

By rotating the image in the computer, we trade decreased vertical resolution for increased horizontal resolution. This is acceptable, since we lose so much resolution in the horizontal direction due to the linescreen or lenticular, that by comparison, we have resolution to spare in the vertical direction. This rotation may be accomplished by one of two means:

• First, the rotation may be accomplished as a separate step from the interleaving. A computer would first interleave the images at a higher resolution than ultimately desired, storing the interleaved image for further processing. The interleaved image is then rotated, and scaled down to the desired size.
• The second (and more efficient) method is to rotate the interleaved image implicitly as part of the interleaving step. The algorithm for this is significantly more general than the basic interleaving algorithm, and can automatically account for rescaling desired images, as well as interpolation, and even further image processing transformations, such as unsharp masking.

Postscript Diagram 1
Postscript Diagram 2
Given the desired output image size (Xs,Ys) and the desired angle of interleaving θ, compute the size of the output image (Xos,Yos) and allocate the needed storage. For each of the pixels desired in the output image, take the (X,Y) coordinate of that pixel and rotate it by q around the center (Xoc,Yoc). Test if the new location (X',Y') is in the active image area - that is, that it lies within the rectangle of size (Xs,Ys). If the pixel fails that test, set the color of the pixel to a color representing unused image area, such as black or white. If the test succeeds, determine the image to which that pixel belongs, by finding the horizontal position of that pixel relative to the edge of the nearest repetition of the pitch of interleaving. Further determine the position of a pixel in that image corresponding to the position in the output image. Set the pixel in the output image equal to the value of the pixel at the corresponding position in the selected planar input image. Continue this process for all of the pixels in the output image and output the finished product.

Two important variations on this algorithm should be noted:

1. Antialiasing may be achieved by supersampling each pixel of the output image, computing an average of several subpixels within the output pixel. This increases the computation time for the algorithm, but may provide a better image, especially when combined with the use of a continuous tone output device.
2. The value of a given pixel in the input planar images may be computed by interpolating values in-between the provided images. This latter change, while trivial, can greatly enhance the quality of the final image at a modest decrease in speed.

In actual practice, a much more optimal algorithm is used, which makes use of vector mathematics and the consistency in direction of computation due to the angle of interleaving. This alleviates the need for expensive computation of rotation, which must be otherwise computed using trigonometric functions.

The question is raised as to what the proper angle of interleaving should be. There are a variety of factors that come into play. For four color separations, the angle should be selected so as not to interfere with the printing angles of the offset colors, or there may be a moire with the lenticular or barrier screen . In general, this only applies when the pitch of interleaving is within roughly a factor of two of the line ruling of the output. In the case of other output methods, such as continuous tone output, the angle may be selected to allow a desired image to fit on the available output image size (rotating an image requires a larger available output image size, to accommodate space for the rotation). It may also be selected to provide an optimum tradeoff between horizontal and vertical resolution.

We have not yet discovered a means of computing an optimum angle for these purposes, since the horizontal and vertical resolutions vary discontinuously as a function of the angle of interleaving. We have empirically determined, however, that a wide variety of angles provide drastic improvements over the older computer interleaving method sufficient for our needs.

 The original PHSCologram interleaving algorithm amounted to little more than file manipulation, reading scan lines alternately from each of the input images and writing them to the output image. The rotated algorithm is somewhat more complex, requiring a more powerful computer.

• The scanning of the input proceeds at an angle, thus requiring at least vector mathematics instead of simple incrementation to find the correct pixel. The present algorithm is roughly 80% processor bound, with the remaining 20% going to I/O operations. The older algorithm, by contrast, was far more I/O bound.
• Because of the angled scanning of the input images, it is impractical to leave them on disk, or even to use virtual memory. They should be read into physical memory, or else the non-linear file accesses cause disk thrashing.
• More images means more memory. 32 images at 1024x1024 resolution, 32 bits per pixel is a total of 128 Mb of images. With the operating system, the interleaving program, various buffers, and extra color planes for special printing, memory requirements can rapidly exceed this value. This is beyond the upper limit of available memory for most desktop PC's, and is costly.
• Output pixel centers will usually not fall on the input pixel centers. This virtually requires the use of some sort of interpolation at each pixel, further adding to overhead.