Final Project

C# Source (Visual Studio 2005) - 37KB (Zip File)

Executable - 16KB (Zip File)

Database - 386KB (Zip File) - Unzip .txt and .bmp files to a directory and load the text file as a database. This database was not my best one but it took several hours to compile and generates some interesting images if you play around setting the similarity threshold just right. And If you use the fast generation algorithm you can generate some large pictures fairly painlessly that look like linoleum flooring.

For an introduction please see project 3 and the project 4 proposal.

Texton algorithim:

Breakdown a picture into small pieces, put each piece into a data structure along with pointers to all the neighboring pieces around it. All pieces that go into the data structure that match a piece currently in the data structure are not added but they're neighbor data is added to the piece that was matched in the database. Once this is done for an entire picture or series of pictures, you have a networkof thousands of little pictures.

Reconstruction

By starting with a single picture you can then choose a possible neighbor, draw it, choose another neighbor, draw it....so on and so forth until you have filled a large image of your smaller images. It turns out there are many ways of reconstructing a scene.

The Left to Right, Top to Bottom Method

My first attempt was to reconstruct the textons starting from the top left corner and reconstructing line by line, from left to right, choosing each texton based on what was to the right and above it. Each line reconstructed very well horizontally for this algorithm but did not do so well vertically. The algorithim chose the best possible match allowing for a poor match if there was nothing better.

My reasoning behind this is that choosing neighbors was limited to the right and bottom neighbor lists of the previously drawn images. Had there simply been enough textons then this might have worked better. However, learned later on that the more textons you have, the more easier it is for your database to build a reconstruction but your reconstruction will tend to look very simple and ambiguous of any distinct features.

The Outward Spiral Method

In order to utilize more than just the bottom and right neighbors of an image during reconstruction, I devised an algorithm that starts at the center of an image and begins spiraling outward, circling around the larger growing mass of constructed images. It took awhile to perfect the algorithm and work all the bugs out of the code but the appearance of the output was much more pleasing. Some of the difficult parts to the solution was finding a way to choose the best image from the lists of possible images from each of the neighboring images. The algorithm had to accomodate finding the image from the lists of 2 to 4 neighbors. I found three ways of doing this. each algorthm finds a set of suitable images from any already drawn neighbors. From there I choose one at random (but not completely random, I bias the chances of winning toward images that have a high occurrence).

Using the image above the following is constructed.

Algorithm 1: . Each image in a neighbors list is compared to each image of all the other neighbors. The images from each neighbor that have an average comparison rate higher than the defined threshold are returned.

Algorithm 2: Each image in a neighbors list is compared to each image of all the other neighbors. The images that have a comparison rate higher than the defined threshold for at least one image in every neighbors list are returned.

Algorithm 2: Only the exact images that are shared by all the neighbors are returned.

Each algorithm seemed to vary in generating scenes that looked like something other than static. Some did better on some pictures than others. The threshold value seemed also be very important and if you could find a perfect value it would end up generating some nice images.

Original Image	High threshold with large texton size	Low threshold with small texton size

This is a series of images was constructed from the tropical photos (see project 3) using different starting images at different matching thresholds. Although they don't look much like tropical scenes, they are pretty interesting.

This was an image that was originally 2400x2400 that I sized down. You can see that the algorithim that spirals outward has an affect on the grain of the texture of the image. Amazingly it looks a lot like linoleum flooring.

This was an interesting image(enlarged) reconstructed from the middle image. The image on the far right is a blown up section of the middle picture that the reconstruction partially used.