Colin O'Brien

Project 3

Your data set,

Pictures used for creating textons

NOTE: TEXTON MAPS ARE ZOOMED FOR VIEWING (and sorted by best matching texton at top left)

		Ireland
		Snow Forrest
		Tropical
		Utah

Pictures classified:

Your classification confusion matrix

It seemed to like Ireland and Utah most.

Detail exactly what pre-processing you do (ie, do you scale all the images to be the same size? are you making all images grayscale?)

Because this project is computationally expensive I don't use large pictures (I use around around 250 pixels the most in any direction). Images are kept in color although only the intensity is looked at during computation. I wanted to add color to the processing but ran out of time.

Give a pseudocode algorithm of how you compute textons or sift feature responses, and how you implement your classifier.

The algorithm uses several parameters:

Texton width and height (I used 4x4)

Number of images used to build catagory dataset (I used 3 for each category)

Number of categories (I used 4)

Building the dataset

Foreach category

Foreach image to use in category dataset

Break image into texton sized pieces

Compare each piece to another, keeping track of the running average percentage that each piece matches other pieces. Avg% = (cumulative percentage/total comparisons)

Remove pieces with a low average percentage matching

 

Classifying images

Foreach image

Break image into texton sized pieces

Foreach category dataset

Foreach texton sized piece

Compare each piece to each piece in the dataset and sum the score (score = percent matching * (average percent matching of the data set piece), so for instance a image piece that matched a piece in the dataset 25% and the piece in the dataset had an average matching rate (computed when building the dataset) of 80% the resulting score would be 20%. Basically saying this piece matches a catagory 20% by matching 25% of a texton that matches the scene 80%.

divide the score sum by the number of comparisons (pieces in picture * number of pieces in the dataset) and this is the score for this catagory (will be in the range from 0 to 100).

The category with the highest score is chosen as the probably category of the image

The program originally started at the top left hand corner of the image, and compared a texton size piece of a picture to each possible same size piece in the picture, sliding down a pixel after each comparison, however, this was way too computationally expensive. So I changed the algorithm so that the next point of comparison was the width of the texton so basically what I'm doing is cutting the picture up into texton size pieces and comparing them to eachother.

Give a complexity analysis that lists the computational complexity of your approach (both for building the representation, and, again for using the representation to classify a new image), as a function of:
the size of the data set (both number of images and size of each)

For building the data set the complexity in terms of number of images and size was (for a single dataset)

(number of images to build the data set*(width/textonwidth) * (height/textonheight))^2

to classify the complexity is (for a single dataset comparison)

(number of textons*(width/textonwidth) * (height/textonheight))

the number of categories in the data set

For building the data set the complexity in terms of number of images and size was

((number of images to build the data set *(width/textonwidth) * (height/textonheight))^2) * number of datasets

to classify the complexity is

(number of textons*(width/textonwidth) * (height/textonheight)) * number of datasets

I was able to code in some tricks to reduce the computational complexity.