resolutions

I have never made New Year's resolutions before, but this time I actually have some idea of the things I want to accomplish in the coming year:

1. Graduate.
2. Create an interactive labeling demo, where users can annotate static objects in images and they get attached to the "real world". I'm working some of the techniques behind this right now, and I have a crappy demo built on top of LabelMe, but I would like to have a more scalable and usable one.
3. Work out the details of my convex formulation of visibility constraints in multiview stereo and write a paper on this.
4. Start training MMA, probably here.
   

lyrics quiz

Here's a lyrics quiz with a twist: all of the lyrics consist of syllables like "na" and "la" instead of actual words. Spacing and commas generally indicate time between syllables. The "X" indicates other words that are part of the phrase, but would give away the identity of the song. Name as many songs as you can in the comments. None of them are at all obscure, and I've included the decade in which each song was released.

1) 1980s
na na na na na
na na na na na, na na na na na, na
na na na na na, na na na na na na na, na
X

2) 1980s
na na nana na na
nana na na nanana na na

3) 1990s
nana nana nana nana na na
nana nana nana nana na na

4) 1960s
na, na na nanana na
nanana na, X

5) 1960s
na nana na nana na nana na

6) 1970s
fa fa fa fa, fa fa fa fa fa, fa

7) 1960s
na na na, na
na na na, na
X

8) 1980s
la la la lala la
la la la lala la la

9) 1970s
doo, doo doo, doo doo, doo, doo doo
doo, doo doo, doo doo, doo, doo doo

10) 2000s
la la la, la la lala la
la la la, la la lala la

ECCV 2008

ECCV 2008 happened over a month ago, but it's not too late for me to post a summary of some of my favorite papers from the conference, as well as my own paper. Let's start with my paper:

Scene Segmentation Using the Wisdom of Crowds
Ian Simon and Steven M. Seitz
There are many cues one could use when segmenting images, such as color, edges, recognizing objects, etc. Here we ignore all of these cues and segment 3D scenes based on the distribution of photos taken at the scenes (downloaded from Flickr). The basic idea is that people do not take photos simply by pointing the camera randomly, but take pictures "of" interesting objects. We effectively treat each photo as a vote that all of the scene points appearing in this photo belong to the same object. Of course, this is not precisely true for most photographs, but by combining information from multiple photographers, we can get accurate 3D segmentations.

Here are some other papers I liked:

Learning to Localize Objects with Structured Output Regression
Matthew B. Blaschko and Christoph H. Lampert
Object localization is usually done by training a classifier on positive and negative image regions, then running this classifier in sliding-window fashion on a new image. This paper proposes training directly for the localization task using a structured SVM.

Integration of Multiview Stereo and Silhouettes via Convex Functionals on Convex Domains
Kalin Kolev and Daniel Cremers
Several previous papers have tried to combine photoconsistency and silhouettes. The key insight here is a way to express silhouette constraints over a voxel grid in a way that yields a simple convex relaxation. There's no proof of a meaningful performance guarantee relative to the optimal solution of the discrete problem, but it's still cleaner than any of the other papers I've seen that address silhouettes in multiview stereo.

Image Segmentation by Branch-and-Mincut
Victor Lempitsky, Andrew Blake, and Carsten Rother
Suppose you're trying to segment a particular object with unknown pose in an image. For fixed pose, the problem can be solved with a graph cut. This paper describes a branch-and-bound search through a tree of hierarchically-clustered poses for the optimal pose and segmentation. The important observation is that a lower bound on the quality of the optimal solution in a particular subtree can be computed with a single graph cut.

What is a Good Image Segment? A Unified Approach to Segment Extraction
Shai Bagon, Oren Boiman, and Michal Irani
This paper proposes a simple criterion for segmentation: a segment should be easily composable using its own pieces, but difficult to compose from pieces outside the segment. The algorithm implied by this criterion sacrificies speediness for elegance, but I think there is value in figuring out the right thing to optimize, even if actually optimizing it proves impractical. Of course, it's not clear that composability is the right thing, and it would be interesting to compare against human segmentations.

Taleb's notebook

Nassim Nicholas Taleb, author of The Black Swan and Fooled by Randomness, keeps a notebook on his site, in somewhat unfriendly HTML. Using a cool tool called Feed43 (after having failed with several other tools), I was able to extract an RSS feed for Taleb's notes. The feed is here:

http://feed43.com/7032722802218873.xml

Taleb is brilliant and very entertaining, but why oh why can't he use a standard blogging platform?

RIP 8aweek

The only barrier between me and hours wasted browsing the likes of Digg, etc. has now been torn down. What self-control? The creators of 8aweek left a message on their home page (now completely gone) stating:

With the public launch of our new application Socialbrowse Zack and I no longer have the resources to support 8aweek.

Socialbrowse looks like a decent Web 2.0 app. It lives in your browser as a Firefox plugin and lets you leave comments on any web page, which are viewable to other users that have the plugin installed. Also, I am never, ever using it. I don't need social browsing, I need you to prevent me from doing too much social browsing.

I guess it's hard to make money blocking users from accessing ad-supported websites. So, 8aweek founders, I have an idea for you. 8aweek, when it existed (sniff), used to give me a fixed amount of time I was allowed to spend each day looking at crap, after which it would block me from accessing said crap. Put 8aweek back up (please?), but this time, get my credit card information, and charge me for each additional minute I spend looking at crap, warning me first of course.

I guarantee you this will make money, so you don't have to bother with all that boring Socialbrowse stuff.

whom to notify when you change your mailing address

I recently moved to a new apartment, which involved notifying many, many organizations of my change of address. I'd be happiest if some website handled this for me, and updated my address everywhere, but in the meantime I created a list of organizations to notify in the hope that it will be useful to someone, perhaps the future me:

• the USPS
• your school/job
  
• any banks at which you have an account
• any investment management companies, like Vanguard
• Amazon, eBay, PayPal, and any other sites that need your address
  
• your cell phone provider
• your cable and/or Internet provider
• any insurance providers (car, health, etc.)
• any credit card companies with whom you have an account
• voter registration
  
• vehicle and driver registration
  

Is there anything I missed? Also, does a list like this already exist anywhere? I couldn't find one...

"real-world" object recognition

A paper from earlier this year (actual paper here) argues that Caltech 101 and similar benchmarks used to test object recognition systems fail to capture what is truly difficult about visual object recognition, and good performance can be achieved by local models with no explicit higher-level processing. This, the authors claim, is not because these models are actually effective, but because the datasets used contain very little "real-world" variation. For instance, in Caltech 101 the objects are centered, similarly oriented, mostly unoccluded and free from clutter, and are correlated with the image backgrounds.

Instead, the authors argue, we should use synthetic data sets where the amount of variation is controlled. They test their simple model on such a data set where object size, position, and orientation vary and find that as the variation increases, performance quickly degrades to no better than chance.

I think the paper raises an important point, in that we should take care that our datasets are capturing the essence of the problem to be solved. A few comments:

1. The problem of object recognition has multiple essences, and Caltech 101 captures some of them. Our "texture recognition as object recognition" models work pretty well because they do capture some of the appearance variation across different object instances, illumination, and very small changes in viewpoint.
   
2. It's not clear that a dataset in which objects have large amounts of variation in viewing angle better captures object recognition in the "real world". In particular, cars and airplanes, the two objects used in the synthetic dataset, are rarely viewed from some angles.
   
3. I would like to see how humans perform on the synthetic data set with lots of variation.
   

Incidentally, here's another argument from the paper about the standard recognition datasets:

The majority of images are also ‘‘composed’’ photographs, in that a human decided how the shot should be framed, and thus the placement of objects within the image is not random and the set may not properly reflect the variation found in the real world.

My ECCV 2008 paper uses this observation as a cue for segmenting 3D scenes into objects of interest using photographs from Flickr.

transformations between point sets with no correspondence

Another problem that arises frequently in computer vision applications is finding a transformation that maps one set of points to another, where we have no information about point correspondences.

For instance, suppose I have a corner detector, and I want to align the set of detected corners to a floor plan, perhaps for an application like this one.

In addition, as will nearly always be the case, many of my detected corners are spurious. What I want to do is find a transformation that maps as many detected corners as possible to corners on the floor plan.

Unfortunately, even an extremely simplified version of this problem is thought to be hard, where hard means there is no solution better than quadratic. This implies that to find the exact solution, we will have to look at each pair of a detected corner and a floor plan corner.

Here's the simplified version: given two sets of numbers A and B, find the constant offset c that we can add to all elements of A to maximize the number of elements that A and B have in common. In other words, considering points in 1D, what is the translation that maximizes the number of correspondences?

It turns out that this problem is hard even if we are merely trying to detect whether or not there are two correspondences that agree on a translation. This is shown through a reduction to the 3SUM problem in this paper.