Features
FeaturesEver wonder how those 3-D posters work? Here's the secret, and the code you need to generate your own.
Introduction to the Series:
This is the latest in a series of articles on the C Image Processing System (CIPS). This installment describes random dot stereograms and provides the source code so you can make your own. Previous articles in this series discussed reading, writing, and printing gray scale TIFF images. We have also dealt with many other topics, including filtering, segmentation, textures, shapes, and warping and morphing (see the "Previous Installments" sidebar).
Stereogram Basics
Stereograms are those strange 3-D pictures you see on books, calendars, and t-shirts everywhere. You focus past them and all the dots form what appear to be objects with surprising depth. Given different names by different people, these 3-D pictures are all similar in appearance and construction. Stereograms are a part of image processing because making a stereogram involves manipulating an existing image to give it a new appearance.
I'll first discuss why stereograms look the way they do, using text figures to illustrate. I'll move on to dots later.
Figure 1 shows one of the keys to stereograms: divergent viewing, or focusing on a point behind the image. When your two eyes (RI=right eye, LI=left eye) focus on a point x behind the picture, they see two different things (LI sees a and RI sees b). The brain mixes these two into a single image. Stereograms use this mixing to produce depth in the mind.
Figure 2 shows another basic concept in stereograms: the repeating pattern. The pattern 1234567890 runs from left to right and repeats itself for the width of the image. The repeating pattern has four properties.
(1) The pattern runs horizontally, so orientation must be correct (you cannot turn the image sideways).
(2) There is a fixed set of elements in the pattern.
(3) All the elements in the pattern are the same size (fixed font in this case).
(4) The width of the pattern must be less than the distance between your eyes.
Property (4) is critical with respect to a stereogram's final output. Most people's eyes are a little more than an inch apart, so one inch is a good width for a repeating pattern. Display screens show 60-70 dots per inch, while laser printers give 300 dots per inch, so two output devices require different pattern widths.
Figure 3 illustrates how to get depth from the repeating pattern. The top part of the figure shows that a 1 was deleted from the pattern. The left and right eyes, viewing the image divergently, are looking at two different places on the image. The right eye sees the 1 in the pattern while the left eye does not (it was deleted), so the brain adapts. The brain feels that the 1 is present for the left eye, so the brain tucks the 1 behind the 2 on the left side. This brings the right side of the image closer and creates an illusion of depth. Shortening the pattern by deleting an element thus brings the image closer to the viewer.
Conversly, Figure 4 illustrates how to push the image away from the viewer by inserting an element into the pattern. The top part of the figure shows that an A was inserted. The right eye sees the A, the left eye does not, so the brain adapts. The brain reasons that the left eye did not see the A because the A was tucked behind the 8. The right side of the image becomes farther away. Lengthening the pattern by inserting an element pushes the image away from the viewer.
Figure 5 combines deletion and insertion to pop an object out of the background. The top part of the figure shows that a 1 was deleted and an A was inserted. The two eyes see different things, so the brain adapts by tucking the 1 behind the 2 and the A behind the 8. The center section appears closer than the ends (the object pops out of the background).
You can extend this concept to create other depth levels (2, 3, 4, etc.) by shortening and lengthening the pattern by 2, 3, 4, etc. Keep the length of the repeating pattern about twice as large as the number of depth levels.
Figure 6 puts these concepts together into a character stereogram using the repeating pattern 0123456789. On the fourth line, the pattern is shortened by deleting an 8 and then lengthened by inserting an A. When the image is viewed divergently, a rectangle pops out of the center of the background.
Figure 7 shows the result of the final step in a random character stereogram. The viewer again sees a rectangle popping out of the background. Figure 7 is the result of a line-by-line random character substitution applied to Figure 6. For example, take the first line of Figure 6, substitute an R for each 0, an E for each 1, and so on, using the substitution values shown in Figure 8, and you will have the first line of Figure 7. A random number generator created these substitution values. The transition from Figure 6 to Figure 7 used a different set of substitution values for each line.
Figure 9 shows all the steps. First is the depth image with 0 being the background and 2 being closest to the viewer. Next is the processed pattern image, which it has a pattern length of 10 with the basic pattern of 0123456789. Elements were added and removed corresponding to depth level changes. The bottom is the result of a line-by-line random character substitution.
Here, then, are the basics of stereograms. Start with a depth image; choose an appropriate pattern length (less than the distance between your eyes and twice as great as the number of depth levels); shorten and lengthen the pattern length according to changes in depth; and produce a stereogram with line-by-line random substitution. (We also know that we can make character stereograms which are easy to e-mail.)
Extending these concepts from characters to dots is simple, with the difference being in the random substitution. Dot stereograms have only two values — 1 and 0 for white and black. If the output of the random number generator is odd, substitute a 1; otherwise, substitute a 0. In Figure 8 the G substitutes for both a 3 and a 4. In dot stereograms, a 1 will substitute for about half the values and a 0 will substitute for the others. Stereograms sometimes comprise colored dots. If there are four colors, the random number is reduced modulo 4 (producing 0, 1, 2, and 3), with the result substituting for the four color values in the pattern.
Stereogram Algorithms
Figures 10, 11, and 12 give the algorithms for turning a depth image into a random dot or character stereogram. Figure 10 shows the main processing loop — 12 steps that repeat for every line in the depth file. Step 2 initializes the pattern according to the pattern length. If the pattern length is 100, place 0 through 99 (just one time) in the pattern array. Steps 4 through 8 loop through each element or pixel in a depth line. The values of this_pixel and last_pixel cause the pattern to grow or shrink. The no change operation (copy the current element of the pattern array to the processed pattern array) is performed on every pixel in the depth line. After saving this line of the processed pattern, the code performs random substitution and saves the result. Processing and substitution occur line by line, with each line being independent.
Figure 11 shows how to shorten a pattern by deleting size elements (size can be 1, 2, 3, etc.). First, save the input pattern array to a temp_pattern and set new_width to the pattern width less size. Next, increase the pattern's index by size to skip over those elements to delete. Steps 4 through 6 copy the temp_pattern back to the pattern with index skipping over elements. Step 7 shortens the current pattern width.
Figure 12 shows how to lengthen a pattern by inserting size elements. First, copy the pattern to a temp_pattern and empty the pattern. Then, put the new element(s) at the front of the pattern, increase the width, and copy the old pattern onto the end of the pattern. For example, if the pattern is 0123456789 and size is 2, put AB at the start of the pattern and copy 0123456789 onto the end, producing AB1234567890. The max_width variable points to the last element added to the pattern (B, in this example). The next time you insert an element into the pattern, max_width will tell you to add a C, then a D, and so on.
Source Code and Examples
Listing 1 shows the source code for pstereo, which makes random dot stereograms and places them in gray-scale TIFF image files. The code for cstereo, which generates random character stereograms, differs from pstereo only in the type of data it processes and so is not printed here (it is included in the code disk for the issue). pstereo is compatible with the C Image Processing System (CIPS) and calls several routines from CIPS. pstereo, however, works line by line (one-dimensional array) while the other CIPS programs work on image blocks (two-dimensional arrays). The routines read_image_line and write_image_line call CIPS routines to perform image I/O one line at a time (the requisite CIPS routines are on this month's code disk). Run pstereo with a command line like:
pstereo 100 dfile.tif sfile.tif ppfile.tifwhere 100 is the pattern length and the remaining parameters are the names of the depth, stereogram, and processed pattern files.
Image 1 is a gray-scale TIFF depth file. The background is at level 0 while the squares are at levels 2, 4, 5, and 8. Image 2 is a random dot stereogram that pstereo produced from Image 1, using a pattern length of 100. The image is 400 X 400 pixels printed at 4" X 4", so the pattern length of 100 pixels translates to 1 inch. There are several ways to create depth files. Commercial paint and graphics programs can generate gray-scale TIFF files. Use these to set the background to all black (0) and the objects to other levels. You'll need to be careful, because some programs make gray shades by setting black pixels next to white ones and these do not work well. I use a program of my own that creates TIFF images with simple blobs like image 1 (included on this month's code disk).
Image 3 is another random dot stereogram. What's in it?
Summary
This article has described how stereograms work and shown how to make your own. There are many ways to experiment with these. You can filter the depth files to blur or round off the edges of objects, or try making depth files with different commercial packages. Use different pattern lengths and output devices. Stereograms are fun to play with and can become more addictive than playing Doom. cstereo allows you to make character stereograms that you can e-mail. Send hidden messages through the mail, experiment, and have fun. o
Reference
Hankinson, Bob, and Alfonso Hermida. Hidden Images: Making Random Dot Stereograms. Que Corporation, 1994.
Dwayne Phillips works as a software, systems, and computer engineer with the United States Government. He has a Ph.D. in Electrical and Computer Engineering from Louisiana State University. His interests include computer vision, artificial intelligence, software engineering, and programming languages.