Wednesday, March 03, 2010
A few weeks ago we announced the launch of a new orkut application in Google Labs called People Hopper that lets you take your profile image and "morph" it into a friend's photo, using publicly available images from other orkut users along the way. No computer graphics tricks are used; every image along the transition comes from real orkut users.
The application hops across millions of public user images in orkut so that one image is smoothly transformed into another. First, faces are automatically detected in public profile images and normalized in contrast and size. Then, for each image, we find other public profile images that are similar to it. Finally, when you pick two faces, we just hop between similar public images, step-by-step, until the connection is made.
People Hopper was outcome of the following research question: Is it possible to learn a low-dimensional space (i.e. a manifold) in which all the human face images live? It is well-known in the machine learning community that to recover the true underlying manifold one needs a large number of samples from it. In 2008, we published a paper at CVPR in which we learned a face manifold using tens of millions of images, which is still the largest scale manifold learning study to date.
To be able to do manifold learning at such a large scale, we had to address two key issues: First, how to do nearest neighbor search in very large databases? We used spill-trees to speed up the search to construct the neighborhood graph. Second, how to do spectral decomposition of matrices which are hundreds of terabytes in size? We investigated sampling-based matrix decomposition methods to handle such matrices.
One way to visualize the quality of the manifold is to find shortest paths between pairs of faces in the manifold, and observe the smoothness of the transitions between them. This is exactly what People Hopper does. Curious? Try People Hopper on orkut now!
The quality of the face manifold depends on three main factors: the number of faces in the manifold, the appearances of those faces, and the similarity measure used for image matching. Since we cannot control the number or appearance of the faces in orkut profiles, it may happen that for a particular image there exists no visually similar image in the database. We plan to update our graph over public profile images frequently, so the quality of paths will change as users join orkut or update their profile images. Finding better contrast normalization and similarity measures is a topic of continuing research. Currently we don't use any face-specific features during this process, just simple image distances.
We are eager to hear your feedback on how we can make this application more fun and useful. Also, if for any reason you would prefer your profile image not to appear in any People Hopper path, you can choose to opt out by visiting our People Hopper homepage.