RANDOM CHARACTER STEREOGRAM

EECS 741 Computer Vision
Semester Project:
Random Character Stereogram

Kang SoonLai 546307
28 April 1996

Introduction

Theory

Algorithm

Requirement

Source

More Stereograms

Introduction

Stereograms are images that look like random dots or with repeating patterns, but if you "know" how to see it, you will see some 3D images in them. A random character stereogram uses ASCII characters as the random patterns to achive the goal of st ereograms. I have always had the interest in how the stereograms are made or generated, and one day I had the chance to come across to how they were made, so I picked it as my semester project.

The theory behind it is simple, and the algorithm is easy as well.

Theory

This section is just going to explain how random character stereograms work in brief, not in too detail.

Figure below shows one of the keys to stereograms: divergent viewing or focusing on one point behind the image.

			focus point
			    *
			   . .
			  .   .		picture
            	   ------a-----b-----
			.       .
		       .         .
		      .           .
		     .             .
		    LI		   RI

When our two eyes (LI=left eye, RI=right eye) focus on a point * behind the picture, we see two different things(LI sees a and RI sees b). Our brain mixes these two things into single image. Stereograms use this mixing to produce depth in our mind.

			focus point
			    *
		
	
	1234567890123456789012345678901234567890	




		    LI		   RI

The second basic concept is the repeating pattern. Figure on top shows a repeating pattern, 1234567890, runs from left to right and repeats itself for the width of the image. The repeating pattern must have these four propeties in order for the stereograms to work:

The pattern runs horizontally.
There is a fixed set of elements in the pattern.
All elements in the pattern are same size.
The width of the pattern is less than the distance between our eyes.

Among all, property 4 is critical with respect to a stereogram's final output. A good guess of the width is 1 inch, that is about 6 characters long. However, if one is to view it from far away, then it could be wider than that. According to my experience, it is easier to view it from farther away.

When an element is deleted from the repeating sequence,

			 1 (a 1 is removed)
                1234567890234567890

our brain will see something like this:

		1234567890
			 1
			 234567890

Therefore, by deleting an element from the repeating sequence, we see something that is closer to us.

However, by adding an element to the pattern will create something that looks farther away from us.

			  A (an A is inserted)
		1234567890A1234567890
			
			we see
			
			 1234567890
			 A
		1234567890

Thus, by shortening and lenghtening the pattern, we are able to create an object which looks farther or closer to us, 3D effect. The amount of elements that we added or deleted creates different depth level. Difference of 1 creates a depth of 1, and difference of 3 creates depth level of 3, and so on.

Here shows an example of random character stereogram:

                     *     *                    
OPK4b=OPK4b=OPK4b=OPK4b=OPK4b=OPK4b=OPK4b=OPK4b=
4?UHH`4?UHH`4?UHH`4?UHH`4?UHH`4?UHH`4?UHH`4?UHH`
9QHKOQ9QHKOQ9QHKOQ9QHKOQ9QHKOQ9QHKOQ9QHKOQ9QHKOQ
VU;--BVU;--BVU;--BVU;--BVU;--BVU;--BVU;--BVU;--B
Ug@`MhUg@`MhUg@`MhUg@`MhUg@`MhUg@`MhUg@`MhUg@`Mh
Q@>CfDQ@>CfDQ@>CfDQ@>CfDQ@>CfDQ@>CfDQ@>CfDQ@>CfD
::Q;ZB::Q;ZB::Q;ZB:Q;;ZB:Q;ZZB:Q;ZZB:Q;ZZB:Q;ZZB
?(f5/1?(f5/1?(f5/?(f5/??f5/??ff5/??ff5/??ff5/??f
P@66PUP@66PUP@66UP@66UP@66UP@666UP@666UP@666UP@6
O]GV09O]GV09O]G09O]G09O]G09O]G099O]G099O]G099O]G
[S7B7d[S7B7d[S77d[S77d[S77d[S77dd[S77dd[S77dd[S7
N;6YH5N;6YH5N;6H5N;6H5N;6H5N;6H55N;6H55N;6H55N;6
=MLiOC=MLiOC=MLiC=MLiC=MLiC=MLiiC=MLiiC=MLiiC=ML
Q9*LCfQ9*LCfQ9*LCf9*LCf9*LCf99*LCf99*LCf99*LCf99
.IXACj.IXACj.IXACj.IACj.IACCj.IACCj.IACCj.IACCj.
?H5nVG?H5nVG?H5nVG?H5VG?H55VG?H55VG?H55VG?H55VG?
2Q7J8e2Q7J8e2Q7J8e2Q7J822Q7J822Q7J822Q7J822Q7J82
?[NI+=?[NI+=?[NI+=?[NI+=?[NI+=?[NI+=?[NI+=?[NI+=
ABcDQ2ABcDQ2ABcDQ2ABcDQ2ABcDQ2ABcDQ2ABcDQ2ABcDQ2
5LXk=?5LXk=?5LXk=?5LXk=?5LXk=?5LXk=?5LXk=?5LXk=?
XSY-\BXSY-\BXSY-\BXSY-\BXSY-\BXSY-\BXSY-\BXSY-\B

If you can really see it, it should look something like this:

000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000011000001100000000000000000000
000000000000000001111110111111000000000000000000
000000000000000011111111111111100000000000000000
000000000000000111111111111111110000000000000000
000000000000000111111111111111110000000000000000
000000000000000111111111111111110000000000000000
000000000000000011111111111111100000000000000000
000000000000000000111111111110000000000000000000
000000000000000000001111111000000000000000000000
000000000000000000000111110000000000000000000000
000000000000000000000001000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000

Algorithm

The algorithm involved here is simple and straight forward.

Open the image file to be processed
Read a line from the image file, $line
$last_pix=substr($line,0,1)
Loop through the $line

$current_pix=substr($line,$i,1)
if ($current_pix > $last_pix)
shorten_pattern
if ($current_pix < $last_pix)
lengthen_pattern
assign a char from the pattern to output line, $output
$last_pix=$current_pix

Perform random character substitution
Go back to 2 until EOF

One hard part that I faced in the algorithm was the shortening and the lenghtening parts. I will explain that in more detail here.

Shortening
After a pattern is shortened, it carries the shortened pattern over the rest of the same line until it is shortened or lengthened again. For example, assume that the pattern width is 6:

Input:		000000000000000111111111222222222333333333

Output:		ABCDEFABCDEFABCEFABCEFABEFABEFABEABEABEABE
			       ^--------^========^________
			       | new    |	 |
			       | pattern|	 |
			       |	|	 |
			       | EFABC 	| EFAB	 | ABE

Notice that everytime the pattern is shortened, it remains at that length until it is shortened or lengthened again. For the above example, the length went from 6 -> 5 -> 4 -> 3.

Lengthening
Lengthening shares the same algorithm as the shortening. Instead of deleting element from the sequence, it adds element to the sequence pattern. There are two ways of inserting the extra element to the pattern:

Get an element from the previous pattern and insert.
eg. ABCDEF ---> FABCDEF <--- new pattern
Randomly add an element to the pattern.
eg. ABCDEF ---> tABCDEF <--- new pattern

For me, I used the the method. Here is another example of a more complex input:

	
Input:	333333333333333222222222222111111111100000000000000

Output:	ABCDEFABCDEFABCCDEFABCCDEFAABCCDEFAABBCCDEFAABBCCDE
		       ^-----------^=========^_____________
		       | new 	   |         |             
		       | pattern   |         |             
		       | CDEFABC   |ABCCDEFA | BCCDEFAAB

Here I present with the phases of the process:

Phase 1, Input Image

000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000011000001100000000000000000000
000000000000000001111110111111000000000000000000
000000000000000011111111111111100000000000000000
000000000000000111111111111111110000000000000000
000000000000000111111111111111110000000000000000
000000000000000111111111111111110000000000000000
000000000000000011111111111111100000000000000000
000000000000000000111111111110000000000000000000
000000000000000000001111111000000000000000000000
000000000000000000000111110000000000000000000000
000000000000000000000001000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000



Phase 2, Sequencial Pattern
 
                     *     *                     
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFACDDEFACDEEFACDEEFACDEEFACDEEF
ABCDEFABCDEFABCDEABCDEAACDEAACCDEAACCDEAACCDEAAC
ABCDEFABCDEFABCDFABCDFABCDFABCDDFABCDDFABCDDFABC
ABCDEFABCDEFABCEFABCEFABCEFABCEFFABCEFFABCEFFABC
ABCDEFABCDEFABCEFABCEFABCEFABCEFFABCEFFABCEFFABC
ABCDEFABCDEFABCEFABCEFABCEFABCEFFABCEFFABCEFFABC
ABCDEFABCDEFABCDFABCDFABCDFABCDDFABCDDFABCDDFABC
ABCDEFABCDEFABCDEFBCDEFBCDEFBBCDEFBBCDEFBBCDEFBB
ABCDEFABCDEFABCDEFABDEFABDEEFABDEEFABDEEFABDEEFA
ABCDEFABCDEFABCDEFABCEFABCCEFABCCEFABCCEFABCCEFA
ABCDEFABCDEFABCDEFABCDEAABCDEAABCDEAABCDEAABCDEA
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEF





Phase 3, Random Character Pattern

                     *     *                     
RV``8VRV``8VRV``8VRV``8VRV``8VRV``8VRV``8VRV``8V
)UJUZT)UJUZT)UJUZT)UJUZT)UJUZT)UJUZT)UJUZT)UJUZT
HaB8NCHaB8NCHaB8NCHaB8NCHaB8NCHaB8NCHaB8NCHaB8NC
YLP*UfYLP*UfYLP*UfYLP*UfYLP*UfYLP*UfYLP*UfYLP*Uf
1'LKK_1'LKK_1'LKK_1'LKK_1'LKK_1'LKK_1'LKK_1'LKK_
Q:CCbIQ:CCbIQ:CCbIQ:CCbIQ:CCbIQ:CCbIQ:CCbIQ:CCbI
lO422XlO422XlO422Xl4222Xl4222Xl4222Xl4222Xl4222X
==\bI'==\bI'==\bI==\bI==\bI==\\bI==\\bI==\\bI==\
*iNgE-*iNgE-*iNg-*iNg-*iNg-*iNgg-*iNgg-*iNgg-*iN
X:2P8OX:2P8OX:28OX:28OX:28OX:28OOX:28OOX:28OOX:2
"Ws$LU"Ws$LU"WsLU"WsLU"WsLU"WsLUU"WsLUU"WsLUU"Ws
9LQ5=C9LQ5=C9LQ=C9LQ=C9LQ=C9LQ=CC9LQ=CC9LQ=CC9LQ
:mbOIB:mbOIB:mbOB:mbOB:mbOB:mbOOB:mbOOB:mbOOB:mb
TJd'JQTJd'JQTJd'JQJd'JQJd'JQJJd'JQJJd'JQJJd'JQJJ
/U'DBU/U'DBU/U'DBU/UDBU/UDBBU/UDBBU/UDBBU/UDBBU/
URL=XMURL=XMURL=XMURLXMURLLXMURLLXMURLLXMURLLXMU
fOLWW@fOLWW@fOLWW@fOLWWffOLWWffOLWWffOLWWffOLWWf
f=KTO!f=KTO!f=KTO!f=KTO!f=KTO!f=KTO!f=KTO!f=KTO!
M]nNL(M]nNL(M]nNL(M]nNL(M]nNL(M]nNL(M]nNL(M]nNL(
P7LBl1P7LBl1P7LBl1P7LBl1P7LBl1P7LBl1P7LBl1P7LBl1
Z0I;ZKZ0I;ZKZ0I;ZKZ0I;ZKZ0I;ZKZ0I;ZKZ0I;ZKZ0I;ZK

Requirement

There are a few requirements that need to be fulfilled before the program can be run.

Perl 4.X must be installed for kslstereo to run.
All input images must be in ASCII/text format.
Numbers should be used to define objects.
All lines in input image should be equal length.

Source

You can get the source at http://freenshare.granax.com/programs/kslstereo. The program is written in Perl.

More Stereograms

                 *     *                 
;8bUoc;8bUoc;8bUoc;8bUoc;8bUoc;8bUoc;8bU
i4`C;Hi4`C;Hi4`C;Hi4`C;Hi4`C;Hi4`C;Hi4`C
TIS9A_TIS9A_TIS9A_TIS9A_TIS9A_TIS9A_TIS9
dW@Y@ddW@Y@ddW@Y@ddW@Y@ddW@Y@ddW@Y@ddW@Y
X]b`R5X]b`R5X`R5X`R5X`R`R5X`R`R5X`R`R5X`
8/i(@Q8/i(8/i(8/i(8/i(8/i(i(8/i(i(8/i(i(
?[K?lT?[lT?[lT?[lT?[lT?[lT?[?[lT?[?[lT?[
ZZn=-QZ=-QZ=-QZ=-QZ=-QZ=-QZ=-=-QZ=-=-QZ=
A@=a8V=a8V=a8V=a8V=a8V=a8V=a8V8V=a8V8V=a
m6ZGM/ZGM/ZGM/ZGM/ZGM/ZGM/ZGM/M/ZGM/M/ZG
,T-fZ[-fZ[-fZ[-fZ[-fZ[-fZ[-fZ[Z[-fZ[Z[-f
\0K?W'\?W'\?W'\?W'\?W'\?W'\?W'W'\?W'W'\?
R,-ROcR,OcR,OcR,OcR,OcR,OcR,R,OcR,R,OcR,
[GHQ;V[GHQ[GHQ[GHQ[GHQ[GHQHQ[GHQHQ[GHQHQ
;6aD9U;6aD9U;D9U;D9U;D9D9U;D9D9U;D9D9U;D
.@OI3%.@OI3%.@OI3%.@OI3%.@OI3%.@OI3%.@OI



                        *     *                        
f=Qn==f=Qn==f=Q==f=Q==f=Q==f=Q==ff=Q==ff=Q==ff=Q==ff=Q
VTUBP^VTUBP^VTUBP^VTUBP^VTUBP^VTUBP^VTUBP^VTUBP^VTUBP^
-_HX5O-_HX5O-_HX5O-_HX5O-_HX5O-_HX5O-_HX5O-_HX5O-_HX5O
AASSG4AASSG4AASSG4AASSG4AASSG4AASSG4AASSG4AASSG4AASSG4
abC:K7abC:K7abC:K7abC:K7abC:K7abC:K7abC:K7abC:K7abC:K7
hbW?KjhbW?KjhbWKjhbWKjhbWKjhbWKjhhbWKjhhbWKjhhbWKjhhbW
cWqVVRcWqVVRcWqVRcWqVRcWqVRcWqVRccWqVRccWqVRccWqVRccWq
7BlBQT7BlBQT7BlQT7BlQT7BlQT7BlQT77BlQT77BlQT77BlQT77Bl
79GQi879GQi879Gi879Gi879Gi879Gi8779Gi8779Gi8779Gi8779G
UY@SL2UY@SL2UY@L2UY@L2UY@L2UY@L2UUY@L2UUY@L2UUY@L2UUY@
SWJ[=QSWJ[=QSWJ=QSWJ=QSWJ=QSWJ=QSSWJ=QSSWJ=QSSWJ=QSSWJ
-LU8'N-LU8'N-LU'N-LU'N-LU'N-LU'N--LU'N--LU'N--LU'N--LU
JP_QUWJP_QUWJP_UWJP_UWJP_UWJP_UWJJP_UWJJP_UWJJP_UWJJP_
YN\1hHYN\1hHYN\hHYN\hHYN\hHYN\hHYYN\hHYYN\hHYYN\hHYYN\
a-_B6Ca-_B6Ca-_6Ca-_6Ca-_6Ca-_6Caa-_6Caa-_6Caa-_6Caa-_
0RAO:H0RAO:H0RA:H0RA:H0RA:H0RA:H00RA:H00RA:H00RA:H00RA
;l1;27;l1;27;l1;27;l1;27;l1;27;l1;27;l1;27;l1;27;l1;27
JPIRJnJPIRJnJPIRJnJPIRJnJPIRJnJPIRJnJPIRJnJPIRJnJPIRJn
?0]S0c?0]S0c?0]S0c?0]S0c?0]S0c?0]S0c?0]S0c?0]S0c?0]S0c
`49/.H`49/.H`49/.H`49/.H`49/.H`49/.H`49/.H`49/.H`49/.H
'I-XgK'I-XgK'I-XgK'I-XgK'I-XgK'I-XgK'I-XgK'I-XgK'I-XgK
PGSBJ2PGSBJ2PGSBJ2PGSBJ2PGSBJ2PGSBJ2PGSBJ2PGSBJ2PGSBJ2








                   *     *                   
^lb9d]^lb9d]^lb9d]^lb9d]^lb9d]^lb9d]^lb9d]^l
VBCR.*VBCR.*VBCR.*VBCR.*VBCR.*VBCR.*VBCR.*VB
hAKJK8hAKJ8hAAKJ8AAKKJ8AAKJ88AAKJ88AAKJ88AAK
7JI*7&7JI*&7JJI*&JJII*&JJI*&&JJI*&&JJI*&&JJI
p[BZRVp[BZVp[BZVp[BZZVp[BZVpp[BZVpp[BZVpp[BZ
:PL*8d:PL*d:PL*d:PL**d:PL*d::PL*d::PL*d::PL*
LZ4T@NLZ4TNLZZ4TNZZ44TNZZ4TNNZZ4TNNZZ4TNNZZ4
a*K9$Ba*K9Ba**K9B**KK9B**K9BB**K9BB**K9BB**K
:NV.CD:NV.D:NNV.DNNVV.DNNV.DDNNV.DDNNV.DDNNV
m2S?2Am2S?Am22S?A22SS?A22S?AA22S?AA22S?AA22S
HaMT@7HaMT@7HaMT@7HaMT@7HaMT@7HaMT@7HaMT@7Ha
[WKKM9[WKKM9[WKKM9[WKKM9[WKKM9[WKKM9[WKKM9[W
@mpS\\@mpS\\@m\\@m\\@m\\@m@m\\@m@m\\@m@m\\@m
$+gN;M$+gN;+gN;+gN;+gN;+gN;+g+gN;+g+gN;+g+gN
II4@V:II4:II4:II4:II4:II4:II4:I:II4:I:II4:I:
Y&B@V5Y&V5Y&V5V5Y5V5Y5V5V5V5V5V5V5V5V5V5V5V5
.OLqJ..qJ..qJ.J...J...J.J.J.J.J.J.J.J.J.J.J.
;SCLj`;Lj`;Lj`;Lj`;Lj`;Lj`;Lj`;LjLj`;LjLj`;L
:9i'=U:'=U:'='='='='='='='='='='='='='='='='
.VSB_V.B_V.B_V_V_V_V_V_V_V_V_V_V_V_V_V_V_V_V
A2Lb&CA2LCA2LCACA2LCACA2LCA2LCACA2LCACA2LCAC
87;0@`87;0@7;0@7;0@7;0@7;0@7;7;0@7;7;0@7;7;0
(J_(RX(J_(RX(JRX(JRX(JRX(J(JRX(J(JRX(J(JRX(J
=)O5iJ=)O5iJ=)O5iJ=)O5iJ=)O5iJ=)O5iJ=)O5iJ=)
$7cUY7$7cUY7$7cUY7$7cUY7$7cUY7$7cUY7$7cUY7$7
`;^$Ud`;^$Ud`;^$Ud`;^$Ud`;^$Ud`;^$Ud`;^$Ud`;





ANSWERS


0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000222222222200000000000000000
0000000000222222222222222200000000000000
0000000022222222222222222222000000000000
0000000222222222222222222222200000000000
0000002222222222222222222222220000000000
0000002222222222222222222222220000000000
0000002222222222222222222222220000000000
0000000222222222222222222222220000000000
0000000022222222222222222222000000000000
0000000000222222222222222200000000000000
0000000000000222222222200000000000000000
0000000000000000000000000000000000000000

111111111111111222222222222222222111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111222222222222222222111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111



00000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000
00000000001110000111000001110000000000000000
00000000001110000111000001110000000000000000
00000000001111111111000001110000000000000000
00000000001111111111000001110000000000000000
00000000001110000111000001110000000000000000
00000000001110000111000001110000000000000000
00000000001110000111000001110000000000000000
00000000001110000111000001110000000000000000
00000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000
00000000000000222222222222000000000000000000
00000000000222222222222222222000000000000000
00000000022222222222222222222220000000000000
00000000222222000222222000222222000000000000
00000002222222000222222000222222200000000000
00000002222222222222222222222222200000000000
00000002222220022222222222002222200000000000
00000002222222002222222220022222200000000000
00000000022222200000000000222220000000000000
00000000000222222222222222222000000000000000
00000000000000222222222222000000000000000000
00000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000

EECS 741 Computer Vision Semester Project: Random Character Stereogram

Kang SoonLai 546307 28 April 1996