I provide a Picture class, which can read, manipulate, and display .jpeg images. . Picture manipulation is accomplished via the Red, Green, and Blue (RGB) components of every pixel in the picture (typically there are tens of thousands of these, even in small photos). The model is driven by a text-only view, allowing the user to execute a variety of methods, selected from a menu displayed on the console. Later in the semeseter, when we learn about Java controls and graphics, we will write a matching GUI View and Controller for this Model.

The assignment is to write a general purpose program that produces photomosaics. A photomosaic is large picture that is constructed from a a collection of smaller pictures. When an aesthetically pleasing photomosaic is viewed closely, the observer can identify the contents of each of the small pictures. When viewed from far away, these small pictures lose their detail, but the observer sees their gross visual characteristics fit together to form one large picture, whose overall image is clearly visible.

The actual assignment is to produce a photomosaic of yourself. . We will use a variety of data, from the trivial (blobs of b/w or color images) to b/w pictures of your fellow students (taken from this year's CMU Pic Book -I've got data for past years as well), to collections of color cd/video covers. You might want to search the web for databases of pictures; a requirement is that each picture in the collection should have the same aspect ratio (width/height).

Basically, a program that produces a photomosaic works as follows. It must first read and store a big database of small pictures (typically thousands). Then it must read a large picture to render as a photomosaic. Then, it must scan all the disjoint regions that comprise the large picture and find for each region the the small picture in the database that best matches it (there are various metrics), possible subject to other constraints like how often a picture can be used and if multiple uses are allowed, how far away they must be from each other. Finally, it must build a large picture (the photomosaic) by appropriately overlaying these small pictures onto a blank canvas. The details are discussed in the next major section.

Each class described below is either in a package in the Java standard or the course library (edu.cmu.cs.pattis.cs151xx), or is in the photomosaic package specific to this project.

1. View: This text-only class allows the user to execute a variety of Model methods, selected from a menu displayed on the console. Once a method is selected, it collects the necessary information and then calls it.

2. Prompt: This class is a library of many static methods used to prompt the user for information on the console. It's big virtue is that its is easy to use and it detects and reports simple typing errors (and the user is reprompted for the information). In a view that is text-only, calls to these methods take the place of controls. This file is in the course library.

3. FileSelector: It is easy to use objects constructed from this class to choose the file names of pictures to process (we will deal exclusively with those ending in .jpeg, .gif, and .jpg). We can build objects either to select a single file (returning a String with its name), or select multiple files (by selecting them individually or selecting the folder containing them files, returning a String of file names, with each file name separated from the other by a special separator character -we will use ;). In the latter case, we can easily construct a StringTokenizer object (see the two parameter constructor) to retrieve the individual file names. This file is in the course library.

4. Picture: Objects constructed from this class can store a picture (one read from a file or a photomosaic constructed from an initially blank picture). We can query each instance about the picture that it stores (including the RGB values at any of its pixels) and command it to change any RBG values of its pixels (thus, modifying the picture). We can overlay one picture onto another We can also display this picture in its own window.

5. Filter: This interface is implemented by the IdentityFilter and the GrayScaleFilter classes (and other like LighterFilter, DarkerFilter, RederFilter, GreenerFilter, BluerFilter). It has a method that specifies new RGB values for a pixel in a picture. The Picture class has a filter method that is called with a Filter, changing all the pixels in the picture accordingly. The FilterFactory class defines convenient static methods that allow us to select a filter easily.

6. Comparator: This interface (standard in Java) is implemented by the ByName, ByMetric, and and the ByFrequency classes. It has a method that helps Arrays.sort to sort the small pictures in the database (which the model stores). The ComparatorFactory class defines convenient static methods that allow us to select a comparator easily.

7. Metric: This interface is implemented by the IntensityMetric class and the QuadMetric decorator class. Each metric defines some code to compute and compare metrics, and store the data needed to cache the value of this metric computed on any picture (or region of a picture). We use metrics to generalize the notion of the distance between two pictures; the distance is smaller when the pictures are similar and larger when they a dissimilar. This information is critical when we are deciding which small pictures from the database belongs in the photomsaic. The MetricFactory class defines convenient static methods that allow us to select a metric easily. You will write a class implementing Metric to match color pictures

8. Application: The standard trivial program for constructing and interconnecting the MVC components in an application. Even more trivial here because the view is text-only, using prompting instead of a controller.

You need to modify only the files Model.java, PhotomosaicInfo.java, RBGMetric.java, and MetricFactory.java. You should NOT modify any of the other classes that I have provided unless you make the case to me that the class needs to be more general (in which case I might modify it myself or replace it with your modification so that other students can use it).

You can download the Javadoc for the prewritten classes supplied in this assignment, which contains documenation for all these classes. This shows all the package-friendly entries, because you are reading this code as the writer/maintainer of the photomosaic package. Some classes are fully documented (in English) others just contain the information automatically generated by Javadoc. Click on the index.html file that it contains to bring up the Javadoc. As you already know, navigating and reading Javadoc files are activities that all programmers must repeatedly perform, so this is another opportunity to build your skill doing so. You might even want to print some of the more important documentation.

As always, you can check the behavior of your programs against mine by downloading and running my Executable, to help you understand the specification of the problem and observe the programmer/user interaction you are to implement

photomosaic.Model methods
  ? - Comparators, Filters, and Metrics
  r - resetPictureDatabase
  l - loadMoreInPictureDatabase
  d - displayPictureDatabase
  s - shift
  < - resortPictureDatabase
  f - setFilter
  m - setMetric
  L - loadPictureToRender
  R - renderPicture
  q - quit

Enter Command[?rlds<fmLRq]: m
Enter Metric Name: QuadIntensityMetric
model.getResponse() = Metric set and applied to all Database Pictures



photomosaic.Model methods
  ? - Comparators, Filters, and Metrics
  r - resetPictureDatabase
  l - loadMoreInPictureDatabase
  d - displayPictureDatabase
  s - shift
  < - resortPictureDatabase
  f - setFilter
  m - setMetric
  L - loadPictureToRender
  R - renderPicture
  q - quit

Enter Command[?rlds<fmLRq]: f
Enter Filter Name: GrayScaleFilter
model.getResponse() = Filter set (applied to subsequent pictures only)



photomosaic.Model methods
  ? - Comparators, Filters, and Metrics
  r - resetPictureDatabase
  l - loadMoreInPictureDatabase
  d - displayPictureDatabase
  s - shift
  < - resortPictureDatabase
  f - setFilter
  m - setMetric
  L - loadPictureToRender
  R - renderPicture
  q - quit

Enter Command[?rlds<fmLRq]: l
Enter width  for Picture DB images (in pixels)[1,1000](13):
Enter height for Picture DB images (in pixels)[1,1000](16):
See Picture Database Selection pop-up window

Attempting to load 824 pictures
  Loaded 50 pictures
  Loaded 100 pictures
  Loaded 150 pictures
  Loaded 200 pictures
  Loaded 250 pictures
  Loaded 300 pictures
  Loaded 350 pictures
  Loaded 400 pictures
  Loaded 450 pictures
  Loaded 500 pictures
  Loaded 550 pictures
  Loaded 600 pictures
  Loaded 650 pictures
  Loaded 700 pictures
  Loaded 750 pictures
  Loaded 800 pictures
Loaded 824 pictures
model.getResponse() = 824 pictures displayed
824 pictures loaded: Picture Databse now contains 824 pictures
model.getResponse() = 824 pictures loaded: Picture Databse now contains 824
pictures



photomosaic.Model methods
  ? - Comparators, Filters, and Metrics
  r - resetPictureDatabase
  l - loadMoreInPictureDatabase
  d - displayPictureDatabase
  s - shift
  < - resortPictureDatabase
  f - setFilter
  m - setMetric
  L - loadPictureToRender
  R - renderPicture
  q - quit

Enter Command[?rlds<fmLRq]: L

See Picture to Render Selection pop-up window
model.getResponse() = Picture C:\Documents and Settings\Administrator\Desktop\
executable\cmu.gif loaded for rendering



photomosaic.Model methods
  ? - Comparators, Filters, and Metrics
  r - resetPictureDatabase
  l - loadMoreInPictureDatabase
  d - displayPictureDatabase
  s - shift
  < - resortPictureDatabase
  f - setFilter
  m - setMetric
  L - loadPictureToRender
  R - renderPicture
  q - quit

Enter Command[?rlds<fmLRq]: R
Picture to Render is 504 x 449
Enter # pixels for width in sample[1,504](13):
Sample height (conforming to image database) 16
Rendered picture will contain 1064 tiles: 38 x 28

Enter maximum # of times to reuse any picture[2,1064](2): 100
Enter minimum distance between picture reuse [1.0,38.0](1.0):
  Rendering 0 percent done
  Rendering 10 percent done
  Rendering 20 percent done
  Rendering 30 percent done
  Rendering 40 percent done
  Rendering 50 percent done
  Rendering 60 percent done
  Rendering 70 percent done
  Rendering 80 percent done
  Rendering 90 percent done
  Rendering 100 percent done
model.getResponse() = Picture C:\Documents and Settings\Administrator\Desktop\
xecutable\cmu.gif rendered and displayed

Second, the user specifies the filter to use on the small and large pictures to be loaded. Here the GrayScaleFilter is selected, which converts color images to b/w (and leaves b/w images unchanged).

Third, the user specifies to load "more" pictures into the database, which actually starts empty. The user specifies the number of pixels for each small picture (see the Javadoc for Prompt for interpreting the values in brackets and parentheses). As each actual small picture is read, it is resized to fit the specified size. Here I am using Picbook 2003 photos (see below), which are 127x165 rectangles, so pixel sizes of 13x16, 25x33, etc. are all reasonable values to enter here (keep the aspect ratio width/height at 127/165: these pictures are higher than they are wide).

Then a file-selection window pops up (it is mentioned in the console); the user can select a folder (or multiple files) containing the database of pictures to use when constructing photomosaics; then the user presses the Load Picture(s) button. The program traces loading every 50 images This is called a heartbeat (so you know the program is running). It also printis the number of pictures loaded and the total number of pictures in the database (we can perform this load operation any number of times, to keep increasing the size of the small picture database). When finished, it displays an approximately square window, populated by all the small pictures read into the database (labelled by the width x height of the entire window, measured in pixels).

Fourth, the user specifies to load a picture to render. Another file-selection window pops up (it is mentioned in the console); the user can select a single file containing the picture to render as a photomosaic (the one to approximate by all the images loaded earlier); then the user presses the Load Picture button. This picture is displayed in a window, labelled by the file read and its width x height measured in pixels.

Finally, the user specifies to render the picture as a photomosaic. The program first prompts for the # of pixels wide to sample in the large picture for each small picture. Here the picture's width is 504 pixels, if I chose a sample width that was 10 pixels, I'd have 50 (504/10) small pictures in each row of the photomosaic; instead I chose the default (13), so the photomosaic will have 38 (504/13) small pictures in each of its rows. Given the entered sampling width, the sampling height is fixed at 16 (according to the aspect ratio 13/16 of each small picture); thus, the photomosaic will have 28 (449/16) small pictures in each of its columns. Yielding a total of 1064 (38x28) small pictures in the photomosaic.

Notice that the default values in these prompts are choosen to create a photomosaic that is about the same size (measured in pixels) as the original. It will be actually 494 (13x38) x 448 (16x28) By sampling with different widths, the photomosaic can be made smaller (using a larger width) or larger (using a smaller width) than the original picture to be rendered. The program determines the number of pixels high to sample (keeping the same aspect ratio as the small pictures in the database) and prints this value. Note, if the sample size does not evenly divide the width or height of the picture, it will ignore some pixels at the far right or far bottom of the picture.

The program also allows us to specify two extra constraints when rendering the photomosaic. It asks for the maximum number of times to reuse any small picture. Note that with a database of 824 small pictures, and with 1064 small pictures in this photomosaic, we need to use at least some pictures twice; obviously we don't need to use any picture more than 1064 times. "Good" photomosiacs don't use the same pictures over and over, they use all the pictures in the database equally (even better if the database is bigger than the photomosaic, it uses pictures just once or not at all). But, if we use the upper bound here (allowing small pictures to be reused as often as necessary), the rendered image would look best. The user in this run has allowed for a reasonable amount of small picture reuse in this rendering.

Finally, the program asks for the minimum distance between reuses of the same small picture (this part, by the way, is extra credit; see below for details). Here the distance is euclidean, measured from the center of each picture (and assumes each picture is 1x1; so the centers of the closest pictures are 1 unit apart; on the diagonal they are sqrt(2), etc.). "Good" photomosiacs, if they do reuse small pictures, don't use the same ones near each other. Note if the minimum distance is 1, then it means that pictures can be repeated with no constraints. The user in this run has allowed for the small pictures to be arbitrarily close (the same as if this constraint were not implemented, since it is extra credit).

The program then selects which small pictures appear where in the photomosaic rendering of the large picture (in accordance with the two constaints just entered), printing a hearbeat every time 10% more of the image in completed. It then displays the large picture rendered as a photomosaic.

Look closely at this picture to see the individual faces (they are really a bit too small but I had to fit everything on a web page). Then look at the picture from a few yards away, to let the individual pictures meld into the original image.

The Model class itself must support the following methods and signatures. The menu-driven View class calls these methods; later our GUI View class will call exactly the same methods with exactly the same arguments. Mine stores about a dozen instance variables, of which a centrally important one is an array of PhotomosicaInfo. Some methods set these instance variables so that other, called later, can use them: they are used by different behaviors to communicated with each other. Discounting blank/comment lines, I have about 250 lines of code in this class (including imports, lines with just left/right braces on them, etc.); this includes solving the extra credit parts. In fact, removing lines with only left/right braces knocks the count down to almost 200.

• resetPictureDatabase: Parameterless. Reset the picture database to store no information.

• loadMoreInPictureDatabase: Two parameters, the width and height that the loaded pictures should be scaled to. Let the user select all the files to read (each a picture) and read them Apply the appropriate filter/metric to all incoming pictures. Note: if the parameters are not positive, or there are pictures already in the database and their sizes are different than the sizes specified by the parameters, return immediately with no changes to the database of pictures. Otherwise, display the new database of pictures.

• shift: Three parameters, an object constructed from a class implementing Decision (course library), an object constructed from a class implementing Filter, and a String to tag the label of each new picture with (its original name with this appended). This method scans the database of pictures: for each picture that is OK by the first parameter, a copy is made and filtered by the second parameter, and added to the database. Display the new database of pictures.

• displayPictureDatabase: Parameterless. Display all the pictures the database in an approximately square window.

• sortPictureDatabase: One parameter, an object constructed from a class implementing Comparator. Sort the database of pictures using this parameter and redisplay it.

• setFilter: One parameter, an object constructed from a class implementing Filter. Do not modify the database of pictures, but apply the filter to all subsequent files that are loaded. If the filter is a null reference, do nothing.

• setMetric: One parameter, an object constructed from a class implementing Metric. Apply the metric to each picture in the database of pictures, and apply the metric to all subsequent files that are loaded (it will also be used in renderPicture). If the metric is a null reference, do nothing.

• loadPictureToRender: Parameterless. Let the user select all the file to read (a picture) and read it (if the user presses cancel, do not change the state of the model). Otherwise, apply the filter only (not metric) to the picture and display it.

• renderPicture: Three parameters, the sample width, the maximum number of times each small picture can be used, and the minimum distance between reuses. If there is no picture to render, or no metric has been set, or any of the parameters don't make sense, don't attempt to render the picture. Otherwise, render the picture and display the rendering. I wrote a pair of helper methods for this method.

• getDatabasePictureSize: Parameterless, returns a Dimension object storing the width and height of each picture in the picture database.
• getPictureDatabaseLength: Parameterless, returns the number of pictures currently in the picture database.
• getPictureToRenderSize: Parameterless, returns a Dimension object storing the width and height of the picture to render: both 0 if no picture to render has been loaded.
• getResponse: Parameterless, returns a String that is a message left by whatever method executed most recently, indicating its status.

You must also write a RGBMetric which processes stores three averages: the intensity of all the Red, Green, and Blue components of the pixels. The distance between two such metrics is just the sum of the absolute values of their component differences (e.g., the red intensity of one minus the red intensity of the other). Integrate this class into the MetricFactory class, along with the name QuadRGBMetric (using the QuadMetric to decorate it).

Feel free to create any other classes that you might find useful for this project. A large part of this program is familiarizing yourself with this software. Do not write Javadoc code for any of your class, but put in appropriate amount of comments to help YOU write and debug the program.

Iterative Enhancement: You must become very familiar with the capabilities of the Picture class before thinking about the rest of the assignment. Experiment with the picture class by writing little programs that solve the following problems.

• Read a picture (select one file using the FileSelector class) and display it.
• Read a picture, filter it to be b/w (GrayScaleFilter) and display it.
• Read a picture, display it, filter it to be b/w (GrayScaleFilter) and display it.
• Prompt the user for a width and height, read a picture using those values, and display it.
• Read a bunch of pictures (select multiple files using in the FileSelector class) and display them all.
• Prompt the user for a width and height, read a picture using those values, then create an empty picture twice as wide and high and overlay four copies of the first picture into this one and display it. This is amazingly close to a photomosaic.
• Prompt the user for a width and height, read two pictures using those values, and display them each, then create an empty picture of the same size and make its RGB values the bigger of the equivalent RGB values at each location in the two pictures (merging them), and then display the result.

To start on the actual program, first stub all Model methods. Then implement each in the following order (each builds on the others). Each new method can be tested, via the menu, once the previous ones work.

• getResponse so you can get message from each method called.
• loadMoreInPictureDatabase and to test it displayPictureDatabase; also getPictureDatabaseLength.
• loadPictureToRender
• setMetric (sets on all pictures in the database, and on the picture to render (if it exists).
• getDatabasePictureSize and getPictureToRenderSize.
• renderPicture

• RGBMetric (and update MetricFactory); test this metric by rendering some color picture using a database of color pictures (or just color blobs).
• resetPictureDatabase
• setFilter (do this first, then load and display; now you can load color pictures, for example, and gray scale them)
• sort (test with displayPictureDatabase)
• shift (test with displayPictureDatabase)

You'll learn alot about using Picture objects during this phase. Write the picturing matching code to ignore any constraints (allow each small picture to match any number of times, anywhere). Then, add in the constraint of how often a small picture can be used. Then, for extra credit, add in the distance constraint.

The second picture database is much more interesting: it consists of a series of .jpeg files made by scanning this year's CMU Pic Book. It contains pictures of almost 1,000 students (many from this class). You can download these images via Pic Book.

I also have three color databases. You can download 1,000 random colored squares (also 10x10) Color Blobs. You can download 2003 CD cover images (64x64) via CD Covers. You can download 951 Videotape cover images (70x130) via Videotape Covers. You can download 2,505 Holiday cards (35x56) via Holiday Cards. All these can be used in various parts of the assignment. Whenever you are doing something new (either b/w or color), I suggest using the blobs.

For an interesting essay on Mr. Silvers' work, read Images and Icons: The Making and Unmaking of Pictures for Mass Consumption.

Mr. Silver's company, Runaway Technology has patented the realization of computer programs to produce photomosaics. You can download a copy of the Patent and examine it (read its claims). Unlike copyrighted works, there is no "fair use" of patented material for educational purposes. But primarily, patents are designed to protect revenue, which our use of photomosaics as a programming assignment should not affect (in fact one can use Google to find various photomosaic-producing programs available for sale on the internet: I'm not sure what action Mr. Silvers is taking in these cases). Therefore, to keep everyone's legal exposure to a minimum, we should not post any photomosaics on the web or even print any. I will be destroying the ones I brought to class after the assignment. Also, we should not share our code with anyone.

If you are still concerned about violating patent law, when you run your photomosaic program, use only the databases of Gray Blobs (or Color Blobs), but no pictures. Because the small pictures are now not really pictures, but gray squares, what you are producing is not really a photomosaic. Interestingly enough, the photomosaic program works regardless of whether the "small pictures" are really pictures or just a mish-mash of pixels.

I have mixed feelings about this patent in particular and the general idea of patents on software. I will discuss the US Patent system, and the topic of software patents in general, briefly in class. You might wish to google "Software Patents". I found one interesting web page on Software Patents that is run by the Programmers Freedom League. It contains links to many interesting essays on this topic (most anti-patent). Whether software is patentable is an issue that is hot now, and will be for a long time. For example, Europe will be deciding whther to adopt American-style software patents.

Lawrence Lessig, a faculty member at the Stanford Law school has written extensively on the interaction between law and technology. A book I found particular interesting and readable is Lessig, Free Culture: How Big Media Uses Technology and the Law to Lock Down Culture and Control Creativity.

I will also give 1 point of extra point for rendering the tiles from the middle of the picture outward. This is easy to test: render 0.jpg using 0.jpg, 120.jpg, and 240.jpg: the pattern should approximate a bullseye, with the center matching perfectly, and the matches getting worse as its concentric circles move outward. There is a fairly compact and elegant way to do do this using the Point class, which is in the standard Java library.