Don Mosaic

   Here's the photomosaic of Don Greenberg

Don Greenberg is the founder and head of the Program of Computer Graphics at Cornell University. 1998 marks the 25th anniversary of the program, so in honor of the occasion I assembled a mosaic image of various people who have passed through the lab. The lab web site has an alumni page, if you want to know more.

A number of people sent digital images to Ben Trumbore for the Cornell reunion dinner at SIGGRAPH, many others I gleaned from the web, and a CFP (Call For Pixels) sent out to alumni brought in many more. A total of 119 photos were used in this photomosaic. Thanks to Ben for all his help and FTP space.

Eric Chen kindly donated time to create the FlashPix version of the image.

An excellent site for information about various photomosaic programs can be found at William Leigh Hunt's website.

The perl program which made the photomosaic can be downloaded - read the top of the file for how to use it. It works only for grayscale images. You can get details on the gory baling-wire-and-duct-tape story of how I made the photomosaic of Don using free & shareware tools.

What follows is the table of the 121 images that were used to make up the mosaic image itself. "Times used" is the number of times the image is used in the mosaic, i.e. the number of "pixels" this image replaced. "Grayscale value" is the grayscale value (0-255) that the image represented (see the story for the shocking details about gamma correction, or lack thereof).

Image	Name	Times used	Grayscale value
	Alppay, Gun	75	79.03
	Arvo, Jim	13	187.63
	Baraff, David	14	102.17
	Barsky, Brian - now	6	95.58
	Barsky, Brian - using a tablet	40	145.94
	Barsky, Brian - then (from his Cornell ID)	22	170.13
	Baum, Dan - FutureMan	86	49.66
	Baum, Dan - then (prehistoric)	120	42.47
	Berggren, Martin	13	135.06
	Blocksom, Jon	13	136.80
	Carey, Rikk	6	119.58
	Chen, Eric	6	92.45
	Cohen, Michael	6	122.40
	Cohen, Michael - age 3	207	195.12
	Cook, Rob	15	90.65
	Corson-Rikert, Jonathan - and friend	6	89.18
	Crane, Ted - doing Morris dance fooling	7	115.09
	Crane, Ted - now (in Puerto Rico)	22	81.96
	Crane, Ted - then	26	129.07
	Dorsey, Julie	13	83.63
	Dutre, Philip	8	115.99
	Feibush, Eliot	6	82.48
	Fernandez, Sebastian - about to be morphed	15	95.75
	Ferwerda, Jim	6	91.47
	Foo, Sing-Choog	21	148.41
	Gelb, Dan	17	92.05
	Gelb, Dan - 3D head scan	14	92.91
	Georgiades, Priamos - clown guy	6	89.67
	Georgiades, Priamos - now	30	177.15
	Georgiades, Priamos - then	11	95.42
	Gerstle, Walter	31	98.18
	Goral, Cindy	30	74.50
	Greenberg, Don - ooo, he's his own pixel	22	105.14
	Greger, Gene - old	6	156.38
	Greger, Gene - doh! It's just a close up	12	136.05
	Haber, Robert	14	113.55
	Haines, Eric	8	160.19
	Haines, Eric - 3D head scan	136	66.41
	Hajjar, Jerry	8	134.16
	Hall, Roy	17	104.12
	Hart, David	178	39.13
	Hedelman, Harold - ride 'em	6	95.49
	Hsieh, Patrick	14	128.71
	Hubbard, Philip	6	92.90
	Hubbard, Philip - jamming	15	103.42
	Immel, Dave	10	151.81
	Isaacs, Paul	14	151.43
	Joblove, George	14	108.42
	Joseph, Jonathan - flauting	7	152.27
	Joseph, Jonathan - with flipper	6	82.53
	Joseph, Jonathan - now	11	122.78
	Joseph, Jonathan - then (in drag)	6	117.18
	Kartch, Dan	338	231.59
	Kershaw, Kathy - 1992	6	120.62
	Kershaw, Kathy - glueing thesis pictures	15	173.54
	Kershaw, Kathy - 1995 (wedding)	6	120.77
	Kindlmann, Gordon - strung out	22	98.42
	Kindlmann, Gordon - with shrubbery	6	116.66
	Kindlmann, Gordon	11	155.82
	Kochevar, Peter	7	116.97
	Kunz, Andrew	40	189.55
	Kunz, Andrew - about to be morphed	38	106.16
	Kunz, Andrew - morphed	6	104.76
	Lafortune, Eric	6	103.42
	Lengyel, Jed - now	23	86.69
	Lengyel, Jed - then (Cornell photo ID)	24	86.72
	Levoy, Marc	40	54.07
	Lischinski, Dani	6	98.22
	Lobb, Richard	41	100.23
	Lu, Wei	19	163.27
	Lu, Wei - the heroic side	15	118.28
	Lu, Wei - then	8	159.91
	Malone, Michael	14	120.85
	Marschner, Steve	6	82.51
	Martha, Luiz - at Rand Hall	6	114.83
	Martha, Luiz - now, in Rio	32	109.22
	Meyer, Gary	8	123.67
	Monks, Michael	67	73.20
	Monks, Michael - then, with family	17	84.74
	Monks, Michael - then	6	89.33
	Monks, Michael	16	90.26
	Nall, Dan	7	160.08
	Novins, Kevin	27	132.90
	O'Connor, Tim	16	119.48
	O'Connor, Tim - then, with family	6	82.50
	O'Connor, Tim - wild man	7	153.73
	O'Connor, Tim - then	103	57.21
	Pattanaik, Sumant	37	183.26
	Peng, Liang	6	135.78
	Perucchio, Renato	6	89.04
	Rand Hall (with Luiz Martha's head)	18	93.97
	Ramasubramanian, Mahesh	6	116.08
	Reichert, Mark	59	56.98
	Rushmeier, Holly	15	81.14
	Rushmeier, Holly - measuring light at Rand Hall	6	134.69
	Rushmeier, Holly - measuring light from the Pietà	26	54.82
	Salesin, Dave	45	73.74
	Schulman, Michael	861	29.64
	Shaw, Erin	44	126.33
	Sheldon, Hurf	17	167.31
	Shirley, Pete	12	131.03
	Sillion, Francois	6	115.78
	Srivastav, Sanjeev	6	93.76
	Stettner, Adam	6	105.15
	Swenson, Dan	16	173.57
	Theory Center	30	112.19
	Toler, Corey	17	82.61
	Torrance, Ken	23	89.01
	Trumbore, Ben	6	112.20
	Verbeck, Chan	9	157.54
	Wade, Bretton - from his cool web page	45	50.43
	Wade, Bretton	11	122.32
	Wallace, John	35	66.65
	Wanuga, Paul	40	139.42
	White, Donald	10	165.63
	Wong, Eric	51	76.86
	Zareski, David - at Cornell	14	113.49
	Zareski, David	125	69.13
	Zatz, Harold - rotating 3D head scan	391	17.61
	pixel, black	30	0.00
	pixel, white	271	255.00

Gory Details

Probably my greatest worry was finding images, and finding images that were light and dark enough to cover the grayscale range. I also realized I'd have to bracket the image with pure white and black pixels (well, I could have shifted Don's image so that its minimum and maximum brightness levels fit into my grayscale gamut, but I didn't have a serious photo manipulation package available and didn't want to retouch Don's image anyway). Happily there were in the 79 photos I collected some fairly dark or light ones - enough images for a palette, but not so many that there would be a lot of palette collisions. I made some mistakes in collecting: I didn't realize Rich Coutts' picture wasn't him when he was young but was his son, for example. I was aiming for one picture per gray level - more than this would have complicated the process a fair bit. As it was, I had to cheat... but let's go back to the beginning.

I couldn't use the Macbeth software as I didn't run Unix (I'm in the Wintel world now). Instead, I used the following free or shareware packages (I paid for most of the shareware, that's how good they are) for Windows NT:

• Netscape: for finding and saving images.
• HyperSnap: for screen captures from Netscape.
• Paint Shop Pro: for resampling and viewing images.
• Image Alchemy: for batch conversion of images.
• JASC Image Robot: for batch resizing and cropping of images.
• Perl: for everything else that could not be done by packages.

After collecting, I found I couldn't view Rikk Carey's JPEG with Paint Shop Pro. I had to use HyperSnap to capture it directly from the screen.

Once the images were collected, they were viewed and borders trimmed off them (I missed a bit on Jerry Hajjar's picture). Any images larger than 640 x 480 were resized smaller than this, since the free, demo version of Image Alchemy is crippled to this size (otherwise it's mostly wonderful). All images were converted to grayscale GIFs by Image Alchemy, for simplicity. Then two different scripts (One for portrait, one for landscape. It was time consuming to have to use two different ones and have to separate the images by hand) were used to automatically resize and trim each image down to 64x64. A number of images had to then be redone by hand in Paint Shop Pro, as heads were cut off, etc. I picked a square image ratio because there were a fair number of landscape oriented shots; 64x64 because it would be easy to downsize if needed. In retrospect, this size was not ideal - in a number of images I was forced to chop off the top of the head.

In retrospect, if I had wanted to make more than one set of pixel images, I would have gone with NetPBM, which would have allowed me to write my own filter in C. Not a good option if you're not a programmer, though.

I converted the pixel-images to PBM format so I could easily read them with a Perl script. I then read in the pixel-images, figured out the average grayscale of each, and so created a palette to use to render Don. It turned out there were some images which had the same average grayscale value - I simply cheated by pushing other entries up or down a level or two in order to resolve these collisions, so that each grayscale level would have only one image associated with it.

Are you still awake? Anyway, here was something interesting: I now had 81 images to use for pixels. What I wanted to do was take Don's original picture (which used all 256 grayscale levels) and dither it down to this palette of 81. In Unix it would have been easy to do this, creating a palette to be read in by the Utah Raster Toolkit and applied to an image. In the Windows world this process is tough with the packages I had at hand. Both Paint Shop Pro and Image Alchemy profess to be able to apply a palette to an image, but both rot for grayscale images. I found this out after hand-editing a palette, grayscale-level by bloody grayscale-level, and applying it to Don's image. There were large gaps in how the palette was applied - I think the problem was that these programs do inverse color table lookup by building a 32x32x32 (5 bits) grid and mapping all locations to a palette entry. This is inappropriate for grayscale level work. What I had to do was write my own.

It turned out to be not that bad to do in Perl. I simply read in the palette and figured out how to map each grayscale level to the palette. Then I read Don's image in and did Floyd-Steinberg error-diffusion to get a new image - nice and simple for a grayscale image [looking back on it, I think the final mosaic had the error diffusion code off (oops) - see if you can find the row of Roy Halls in Don's right cheek]. I also wrote some perl programs to generate histograms and to check that the new image actually used all the palette entries (i.e. the images). This check was vital in detecting the limitations of Paint Shop Pro and Image Alchemy explained earlier.

The final step was to generate the mosaic itself. I was tempted to use the gd package, but it looked like a bit of work to compile and figure out. I finally ended out writing a Perl program that read in Don's image and the palette, then scanline by scanline filled in and wrote out an output pixel array with the images representing each input pixel. The uncompressed ascii output image file was around 60 megabytes. Happily, Paint Shop Pro was up to the task of reading and converting this file to GIF (still weighing in at 12 Meg). I then wrote a variant on the mosaic perl program that would create 4 separate tile images I could print on four separate sheets (Paint Shop Pro was not quite up to the task of accurately cropping an image this large, due to the GUI) - this took way too long to debug, but within an hour or two I was done. All in all the whole process took less than two days.

Once I finished, I realized I had made a mistake: I forgot to gamma correct. Say you have two images you want to use as "pixels". One is gray, (128,128,128), the other is alternating pixel-wide lines of black and white. It turns out that perceptually the black and white band image will be much lighter on most monitors, due to gamma. You need to boost the gray image up considerably to match. I actually tried to fold this in, but the image looked darker. It wasn't until I left for SIGGRAPH that I realized that what I needed to do was transform the "pixel" images to linear space, figure out the average value, then use this value against a linearized version of Don's image to get a better match. {follow-up: I tried this later, but it didn't look as good for some reason.}

Another interesting concept that John Wallace first pointed out was that I could try to match larger sample areas of Don's image with the pixel images. For example, say Don's image was 256x256 originally. My method was to simply resize it to 64x64 and match the grayscale value of pixel images with the pixel values in Don's image. Instead, I could have looked at each area on Don's image as a 4x4 set of pixel values. Now I could compare each pixel image with this 4x4 subimage, resizing each pixel image for comparison purposes to 4x4. The image with, say, the least absolute difference for all pixels would be the closest match. For example, if the 4x4 sample on Don's right eye was dark on the left side, light on the right, then an image that was dark on the left and light on the right would be the best match.

At least, that's the theory. I tried this out, and what actually happened is that the low contrast images were favored over all others in most locations. If you think about it, the majority of subimages are slowly changing gradients, which will favor low contrast images. The net effect was that about 30 of 79 images were never used at all, so I abandonned this technique. There are, I think, some interesting ways to make such matching techniques work better, especially if you allow the pixel images to be modified in brightness, contrast, or hue (for color mosaics). But, for now I'm done with the topic. Now, for the fiftieth anniversary I plan a holographic template with stereogram pairs in which you'll have to defocus your eyes while shaking your head back and forth in order to see it...

The Saga Continues