# CS441 Systems Biology II Photomosaic

### Purpose

The project this week was to create a photomosaic. The main steps were to (1) create an image bank of 50*50 images from a folder containing many photographs; (2) display the bank to check that the images are correct; (3) produce three types of photomosaics by replacing pixels of a small picture by images from the bank using slightly different methods fo selecting images.

### Creating an Image Bank

The input images were photographs that did not have a uniform size. First, I used CV to load the image. CV has a method GetSize, which accesses the width and height of the photo. Using this information, my program then uses cv.Resize() to make a smaller image, with the smaller side equal to 50, and the other side proportional. To get a square, I converted the cv image into a numpy array (with cvnum), so that I could simply slice out the center 50 elements. This completes the image processing, unless you want a grayscale image, in which case it is easiest to convert the cv image ( using cv.CvtColor(source, dest, cv.CV_RGB2GRAY) ) before making it a numpy array.

When creating the mosaic, the intensity of the pixel to be replaced should be compared with the average intensity of the image. It is therefore necessary to compute this mean at this point. For grayscale images, this is simply the average intensity of all of the pixels in the image. For color images, the mean intensity is a 3-tuple , with each value the average of the corrosponding value in all of the pixels. To associate this intensity with the image, I created an object named ImageEntry, which simply held two fields: image and intensity. To make my code a little more organized, I made ImageEntry accept just an image, and then it calculates the mean using its own instance method. I also added a _cmp_ method so that I could sort my image bank using the sort() method from the python library, rather than write my own sort method.

### Viewing the Bank

It is hard to tell if the program processes the images correctly without displaying them. To do this, I created a new numpy array (by calling numpy.ones(size, 'uint8') -- the 'uint8' is imperative, as I learned after prolonged confusion) that was big enough to accomodate the images with a single-pixel black border.  I used nested loops to transfer the pixels from the imagese onto the test image, row by row. Afterward, I converted the array into a cv image, and displayed it, with this result (for grayscale images).
Creating a Mosaic

The first step in creating a mosaic is to prepare the target image. CV makes it easy to load the image, and then to resize to have a maximum dimension of 100 (this is to make it reasonably sized when the pixels are replaced by 50X50 images). Then nested loops allow the program to visit every pixel, find an appropriate image to replace it with, and transfer the intensities of the pixels from the mini-image onto a large mosaic canvas. Once the images are transfered, it is a simple matter to convert the array into a CV image and save or show it. The important step in this process is choosing which image with which to replace a pixel. Three methods are as follow:

##### Grayscale Closest-Intesity matching

As I mentioned earlier, I made my ImageEntries "comparable" (that's a Java term, but it's the same idea) so that I could sort my bank. A sorted bank of color images has only questionable usefulness, but for grayscale images, it is a great time-saver. Since grayscale images only have a single intensity channel, they can be sorted linearly. To find the image with the nearest intensity-value of a pixel, I executed a binary search on the bank. I stopped the search when the low and high indicies were adjacent, and knew that one was the closest to the image; I simply used the lower index at first. I later modified my method, but didn't want to change my color coding back to single-channel, so the following image took actually used the image with the greatest intensity that does not go over the pixel value.

##### Grayscale matching with randomization

There are only 256 possible values for the pixels, so matching them to the very closest image means that only 256 images will ever be used. I had over 500 images to choose from, and to make it possible to choose them, I introduced some randomness into my image selection algorithm. I used three binary searches for this. The first time, I stopped the search when the middle value landed within +-10 of the target intensity. The high and low indices were thus both outside the acceptable realm, but one acceptable index has been found. If an 'acceptable' index is not found, then high and low become adjacent to one another, and the algorithm acts like (1). If it was, I do a binary search between low and mid to find the lowest acceptable value, and then do another search to find the highest. Then I randomly select one of the intermediate indicies, and use the corrosponding image to replace the pixel.

##### Color matching

There are ways to store multi-dimensional values so that it is quicker to find nearby values, but I am not as comfortable with them as I am with sorted lists and binary searches. I didn't start this project early enough to give myself time to look it up, so to find the nearest color image to a given intensity, I calculate the Euclidean distance between each image's mean value and the target, saving the closest image and its distance for comparison to find the one with minimal distance. It helps when your mean intensity 3-tuple actually refers to the r, g, and b values, and not just the r values. When this happens, red images are put onto black pixel areas, which, while it looks sort of cool, is quite frustratingly baffling.
Here is another picture done with color matching

### Conclusion

This project took me a lot longer than I thought it would. The process is very straightforward, but I'm not very experienced in working with images, so I made several small mistakes that took a lot of time to find. I also had to spend a fair bit of time on documentation websites, learning what sort of methods were available through cv, numpy, and just python in general. I learned alot, though, and will probably be quicker next time.

I suppose you probably want to see what the picture of my cousins looks like originally for comparison, so here it is.

Labels