Improving Web-based Image Search Via Content Based Clustering

SLAM 2006 in association with CVPR!

2006-05-05T12:37:00.000-07:00

We submitted a paper to a workshop called SLAM in association with CVPR, and got accepted. If you would like to read the paper, click here

We are currently not working on this project due to heavy course load and other factors. Stay tuned for more info in the future! This was definitely a fun project.

2006-03-15T17:56:00.000-08:00

We are currently in the process of writing up a paper on our findings. Until then, here are two things worth checking out:

A new & improved flow chart of our algorithm (click to see bigger version)

Also, click here to view our powerpoint slides from the talk we gave in CSE 190A. It includes more examples of our results. We will post a final draft of our report soon.

Finding objects in unlabelled images

2006-03-05T16:42:00.000-08:00

This was the top rank picture on the query "orange" for a set of 10 unlabelled photos on my computer.

2006-03-05T16:13:00.000-08:00

Here are some more examples (in a new and improved layout):

Coke can

Lakers Jersey

Interesting day at Eureka

2006-02-25T10:47:00.000-08:00

Here are some pictures from the "konference." We got one of the top 3 "best poster" awards (http://www.jacobsschool.ucsd.edu/events/eureka/)!

Strawberries

2006-02-23T13:18:00.000-08:00

In the past we were doing the re-ranking step on only 100 images. We realized that if we include more images, then there will be more correct images at the top of the list, so we tried the query "strawberries" and performed the re-ranking on 500 images. The results look great! Click here to see the output.

Eureka!

2006-02-21T19:45:00.000-08:00

This Friday we will be presenting a poster at the 7th annual Eureka (Engineering Undergrad Research "K"onnference & Assembly). You can check out a list of other presenters and their title/abstracts at http://www.jacobsschool.ucsd.edu/events/eureka/ . Please come and support us and look very impressed when we talk to you :)

Here is a link to the poster: http://ieng9.ucsd.edu/~bbabenko/joogle/eureka%20poster.ppt

L A B histograms

2006-02-17T10:45:00.000-08:00

The past few days I was spending trying to understand how LAB color histograms were constructed in Blobworld. I think I have a good grasp on how the histograms get constructed and I was able to implement LAB histograms in our code. The results of LAB are almost exactly what we wanted. Visually similar blobs are closer in distance than visually dissimilar blobs. Of course there are still some strange cases we need to look into, but for the most part the results are much better than other color spaces we used. The strange thing is that it's hard to get the main cluster when using meanshift with LAB histograms. Maybe we haven't gotten the parameters right for this colorspace yet, but it seems like it either gets a very small cluster that is good, or a large cluster that is very bad, depending on the parameters.

More flexible histograms

2006-02-15T20:25:00.000-08:00

One shortcoming with histograms is in the case when the blobs you compare are extremely flat in texture. Here is an example of the problem:

Let's say there are three colored blobs, dark red, blue, and medium red. Also, let's assume 100 pixels and 3 bins per color channel. The histograms would look like this (in RGB):
dark red: (0,1,0,0,0,0,0,0,0)
medium red: (0,0,1,0,0,0,0,0,0)
blue: (0,0,0,0,0,0,0,0,1)

Clearly the distance between any two histograms is equal. This is an undesired effect since we would hope that medium red would be much closer to dark red, than blue. To make things worse, the problem is not resolved by switching colorspaces to hsv or lab - if the blobs have uniform color, the problem is still present. We are currently working to fix this by convolving all the histograms with a gaussian filter. Unfortunately this will introduce a new parameter (the sigma of the filter) which will have to be tweaked.

Nice Diagram and info on the Voted Perceptron

2006-02-06T13:51:00.000-08:00

Here is a diagram of our program, to make things a little bit more clear.

Also, to those who are not familiar with the Voted Perceptron algorithm, here is a snapshot of the pseudocode from the original paper (Freund, Y. & Schapire, R. (1999). Large Margin Classification using the Perceptron Algorithm. In Machine Learning, 37(3), 277–296.)

Classifiers

2006-02-06T13:48:00.000-08:00

Our goal initially was to create a small training set from the first 20 results using the meanshift algorithm, and then to create a classifier that goes through the rest of the pages and collects "similar" images. We came upon a major problem. Our training set consisted only of positive examples. In order to get negative examples we used the first 200 images from the query "things." We then ran a simple k nearest neighbor classifier to classify each new blob as being either belonging to the class (e.g. "oranges") or not belonging. Our results were not impressive, knn only picked up about three more images at most and this was not good enough.

We also tried running the voted perceptron algorithm on the training data and got mediocre results as well.

After discussing our attempts with Serge, we realized that we may be approaching this the wrong way. We were trying classify images as either belonging to the set, or not belonging to the set. Perhaps instead, we can provide a simple way to "re-rank" the image results.

Plans for this week.

First, let me define the sets
Let A = the first X images retrieved from an image search (X=20 in our case)
Let B = the X+1 .... N images retrieved from an image search (We plan on getting 100 or so more images)

After we get the biggest cluster from set A using meanshift, we can compute the distance from each blob in set B to the mean of the biggest cluster. Now we can sort the blobs in set B by distance and re rank the corresponding images based on the order of the blobs.

For our distance function we will use euclidian distance, and chi-squared, and compare the two methods.

We are also planning to add the hack that takes blobs with white color on the edges out of consideration.

Progress

2006-02-02T23:24:00.000-08:00

We have made progress on training a classifier, and we'll talk about this in the next post. Here are some notes we have on our progress.

compare rgb with hsv histogram performance
ask serge about:
best classifier for our data points. (the main problem is that we don't have negative examples, only positive ones).
should we use chi-squared in our knn function?
block segmentation? (Boris is really into trying this)

More Screenshots

2006-01-24T13:17:00.000-08:00

After fixing our histogram bugs, our results are starting to look a lot more promising.. here are some examples we tried:

"oranges"

"us flag"

Then there were some examples, where not only the largest cluster of blobs looked significant, but also the second largest.. we'll have to figure out how to deal with that..

and finally...

WATCH OUT ROBART III, WE'RE HOT ON YOUR TRAIL!!

Issues/ Ideas

2006-01-24T12:57:00.000-08:00

Here are some issues were currently dealing with:

- black and white images don't work - bug in code
-white blobs touching edges should be excluded from being "significant clusters"
-talk to serge about how to add features such as texture and shape
-lab histograms, read blobworld paper
-playing with minimum blob area to include in clustering- seems pretty sensitive. We will post examples soon.
-in calculating the biggest cluster, count the number of IMAGES in the cluster, not the number of blobs. Multiple blobs may be present from the same image. We want the cluster with the most images, not blobs

Debugging

2006-01-22T16:10:00.000-08:00

We re-traced our steps to check our code. To get a sanity check we created a small toy example with red blobs, and that seemed to work well:

Next we used a "united states flag" example, and just did average L*a*b for each blob, so the blob space had 3 dimensions. The results looked good, here is the biggest blob cluster:

But when we looked at all the blobs in the 3-D blob space, it looked kind of peculiar and we are not sure if it is correct:

For some reason the points always look like they are in a straight line... which does not really make sense.

Next we tried to debug our histogram code. We had a huge a bug in our code where we were building the histograms. We wanted to bring this up becuase it's something that other people might get caught on. It has to do with the "hist" function in Matlab... We were calling it like this:

hist(points, 15) - to put things into 15 bins

However, this does not define the start and end bins of the histogram so it centers the whole thing. This is very bad! Instead you should do:

hist(points, [1:15]).

Nevertheless, we are still having problems with the histograms that we don't really get. Here is an example of a picture and the histogram that our code computes.. we are confused as to whether this is correct or not:

Color spaces and histograms

2006-01-17T15:12:00.000-08:00

We are playing with the mean shift algorithm and different color spaces / historgrams to cluster groups of images. Our main focus is simple objects such as bananas and strawberries. We have tried clustering using rgb averages, rgb histograms, hsv averages, hsv histograms, and l*a*b* averages. Our next step is to try l*a*b* histograms but we need to understand it before we go on. We plan on reading up on these color spaces and then trying to cluster with lab histograms.

2006-01-09T13:18:00.000-08:00

Some more screenshots:

Retrieving and segmenting images

2006-01-09T13:02:00.000-08:00

So after looking at the available tools, we have decided to use Yahoo! image search api to retrieve our images (Google has no image search api). After retrieving the images, we need to segment them into "blobs." We will be using Pedro Felzenszwalb's image segmenting program to do this.

Since the segment program takes input files in ppm format, we need to convert the jpg files retrieved from yahoo to ppm format. Matlab makes that easy by just letting you specify what format to read in an image using imread, and what format to output a new image using imwrite.

So the process will be like this:

-The input query is sent to an image search engine
-First several pages of thumbnail images are downloaded to a folder
-Convert all jpg images to ppm format
-Run the segment program on every converted image
-Separate into "blobs" and cluster

2005-12-19T00:11:00.000-08:00

While Nadav has been studying for the GREs, I couldn't help my curiosity and did some preliminary testing of our idea. I used Piotr Dollar's Matlab toolbox (which has a working implementation of the meanshift clustering algorithm). The first thing I did was split each image into blocks (rather than actually segmenting it into meaningful blobs) and clustered these blobs using 3 features - the average RGB. I then took the largest cluster and found the original images these blobs belonged to. Ironically, the very first example I tried worked very well.. unfortunately that wasn't the case for most of the other examples, but here are two that worked well:

Here is the biggest cluster of blocks:

And another example:

Lastly, I tried segmenting the images in a slightly less naive way than into square blocks - I used the built in kmeans function and used only color to segment. Here is a cool example of a banana:

Starting Out

2005-12-05T12:46:00.000-08:00

To get a start on the project I have been concentrating on learning two important tools - LATeX and Matlab:
1) LATeX is a typesetting system that most researchers in computer science use to write papers. It seems to be very useful especially when writing various mathy things. I had trouble finding an interface for windows, but a friend recommended MikTex and WinEDT, so I have installed the two and started to play around with them.
2) My first real exposure to Matlab was in CSE 166 this quarter (Math 20 had assignments in Matlab, but they were very far from programming. I also borrowed a book from Serge called "Matlab for Engineers" by Chapman, to start looking over more involved Matlab features such as cell arrays and structs (since I'm quite used to Object Oriented design).

That is all for now.

First Post

2005-11-29T13:30:00.000-08:00

Welcome to our 'CSE 190: Topics in Vision and Learning' blog for Winter 2006.