Graphics meets Big Data meets Machine Learning

We've all played Where's Waldo as children, and at least for me it was quite a fun game.  So today let's play an image-based Big Data version of Where's Waldo.  I will give you a picture, and you have to find it in a large collection of images!  This is a form of image retrieval, and this particular formulation is also commonly called "image matching."

The only catch is that you are only given one picture, and I am free to replace the picture with a painting or a sketch.  Any two-dimensional pattern is a valid query image, but the key thing to note is that there is only a single input image. Life would be awesome if Google's Picasa had this feature built in!


The classical way of solving this problem is via a brute-force nearest neighbor algorithm, an algorithm which won't match pixel pattern directly, but an algorithm which will also use a state-of-the-art image descriptor such as GIST for comparison.  Back in 2007, at SIGGRAPH, James Hays and Alexei Efros have shown this to work quite well once you have a very large database of images!  But the reason why the database had to be so large is because a naive Nearest Neighbor algorithm is actually quite dumb.  The descriptor might be cleverer than matching raw pixel intensities, but for a machine, an image is nothing but a matrix of numbers, and nobody told the machine which patterns in the matrix are meaningful and which ones aren't.  In short, the brute-force algorithm works if there are similar enough images such that all parts of the input image will match a retrieved image.  But ideally we would like the algorithm to get better matches by automatically figuring out which parts of the query image are meaningful  (e.g., the fountain in the painting) and which parts aren't (e.g., the reflections in the water).

A modern approach to solve this issue is to collect a large set of related "positive images" and a large set of un-related "negative images" and then train a powerful classifier which can hopefully figure out the meaningful bits of the image. But in this approach the problem is twofold.  First, working with a single input image it is not clear whether standard machine learning tools will have a chance of learning anything meaningful.  The second issue, a significantly worse problem, is that without a category label or tag, how are we supposed to create a negative set?!?  Exemplar-SVMs to the rescue!  We can use a large collection of images from the target domain (the domain we want to find matches from) as the negative set -- as long as the "negative set" contains only a small fraction of potentially related images, learning a linear SVM with a single positive still works.




Here is an excerpt from a Techcrunch article which summarizes the project concisely:

"Instead of comparing a given image head to head with other images and trying to determine a degree of similarity, they turned the problem around. They compared the target image with a great number of random images and recorded the ways in which it differed the most from them. If another image differs in similar ways, chances are it’s similar to the first image. " -- Techcrunch


Abhinav Shrivastava, Tomasz Malisiewicz, Abhinav Gupta, Alexei A. Efros. Data-driven Visual Similarity for Cross-domain Image Matching. In SIGGRAPH ASIA, December 2011. Project Page

---

Here is a short listing of some articles which mention our research (thank Abhinav!).

http://techcrunch.com/2011/12/06/cmu-researchers-one-up-google-image-search-and-photosynth-with-visual-similarity-engine/

http://news.cs.cmu.edu/article.php?a=2858

http://futureoftech.msnbc.msn.com/_news/2011/12/06/9252228-computer-mimics-human-ability-to-match-images

http://www.physorg.com/news/2011-12-team-computerized-method-images-photos.html

http://nanopatentsandinnovations.blogspot.com/2011/12/carnegie-mellon-creates-computerized.html

http://www.sciencecodex.com/read/carnegie_mellon_creates_computerized_method_for_matching_images_in_photos_paintings_sketches-82595

http://www.cra.org/ccc/rh-imatch.php

Google Scholar, My Citations, a new paradigm for finding great Computer Vision research papers

I have been finding great computer vision research papers by using Google Scholar for the past 2+ years.  My recipe is straightforward and has two key ingredients. First, by finding new papers that cite one of my published papers, I automatically get to read papers which will be relevant to my own research interests.  The best bit is that by using Google Scholar, I'm not limiting my search to a single conference -- Google finds papers from the raw web.

Second, I have a short list of superstar vision researchers (Jitendra Malik, among others) and I basically read anything and everything these gurus publish.  Regularly visiting academic homepages is the best way to do this, but Google Scholar also lets me search by name.  In addition, nobody lists on their homepage their papers' citation counts.  This means if I visit a researcher's personal website, I have to make a decision as to what paper to read based on (title, co-authors, publication venue).  But highly-cited papers are likely to be more important to read first.  I believe that this is a good rule of thumb, and very important if you are new to the field.

I am really glad that Google finally let researchers make public profiles to view their papers and see their citations, etc.  See Google Scholar blog for more information.  I've been using statcounter to monitor my blog's visitors, and now I can use Google Scholar to monitor who is citing my research papers!  I'm not claiming that the only way for me to read one of  your papers is to cite one of my papers, but believe me, even if we never met at a vision conference, if you cited one one my papers there's a good chance I already know about your research :-)  I would love to see Google Scholar Citations pages one day replace "my publications" sections on academic homepages...

My Citations screenshot

My only complaint with Google Scholar is that I can't seem to get it to recognize my two most recent papers.  I have these papers listed on my homepage, so do my co-authors, but Google isn't picking them up!!!  I manually added them to my Google My Citations page, and using Google Scholar I was able to find at least one other paper which cites on of these two papers.

I read the inclusion guidelines, and I'm still baffled.  The PDFs are definitely over 5MB, but my older papers which were indexed by Google were also over 5MB.  Dear Google, are you seriously not indexing my recent papers because they are over 5MB?  It takes us, researchers, months of hard work to get our work out the door.  We see the sun rise for weeks straight when we are in deadline-mode, and the conferences/journals give us size limitations -- we work hard to make our stuff fit within these limits (something like 20MB per PDF).  And we, researchers, are crazy about Google and what it means for organizing the world's information -- naturally we are jumping on the Google Scholar bandwagon. I really hope there's some silly reason why I can't find my own papers using Google Scholar, but if I can't find my own work, that means others can't find my own work, and until I can be confident that Google Scholar is bug-free, I cannot give it my full recommendation.

Problematic papers for Google Scholar:

Abhinav Shrivastava, Tomasz Malisiewicz, Abhinav Gupta, Alexei A. Efros. Data-driven Visual Similarity for Cross-domain Image Matching. In SIGGRAPH ASIA, December 2011.

Tomasz Malisiewicz, Abhinav Gupta, Alexei A. Efros. Ensemble of Exemplar-SVMs for Object Detection and Beyond. In ICCV, November 2011.

If anybody has any suggestions (there's a chance I'm doing something wrong), or an explanation as to why my papers haven't been indexed, I would love to hear from you.