CMU PhD Thesis: Spectral Matching

Spectral Matching, Learning, and Inference for Computer Vision

Marius Leordeanu

doctoral dissertation, tech. report CMU-RI-TR-09-27, Robotics Institute, Carnegie Mellon University, July, 2009

Abstract: Several important applications in computer vision, such as 2D and 3D object matching, object category and action recognition, object category discovery, and texture discovery and analysis, require the ability to match features efficiently in the presence of background clutter and occlusion. In order to improve matching robustness and accuracy it is important to take in consideration not only the local appearance of features but also the higher-order geometry and appearance of groups of features. In this thesis we propose several efficient algorithms for solving this task, based on a general quadratic programming formulation that generalizes the classical graph matching problem. First, we introduce spectral graph matching, which is an efficient method for matching features using both local, first-order information, as well as pairwise interactions between the features. We study the theoretical properties of spectral matching in detail and show efficient ways of using it for current computer vision applications. We also propose an efficient procedure with important theoretical properties for the final step of obtaining a discrete solution from the continuous one. We show that this discretization step, which has not been studied previously in the literature, is of crucial importance for good performance. We demonstrate its efficiency by showing that it dramatically improves the performance of state-of-the art algorithms. We also propose, for the first time, methods for learning graph matching in both supervised and unsupervised fashions. Furthermore, we study the connections between graph matching and the MAP inference problem in graphical models, for which we propose novel inference and learning algorithms. In the last part of the thesis we present an application of our matching algorithm to the problem of object category recognition, and a novel algorithm for grouping image pixels/features that can be effectively used for object category segmentation.

Link: WWW, PDF

A $1 Recognizer for User Interface Prototypes

It requires under 100 lines of easy code and achieves 97% recognition rates with only one template defined for each gesture below. With 3+ templates defined, accuracy exceeds 99%. Gestures should be regarded as fully rotation, scale, and position invariant.

UIST'07 Paper

Javascript Example

IROS07: Improved Likelihood Models for Probabilistic Localization based on Range Scans

Patrick Pfaff, Christian Plagemann, and Wolfram Burgard
University of Freiburg

Abstract—Range sensors are popular for localization since they directly measure the geometry of the local environment. Another distinct benefit is their typically high accuracy and spatial resolution. It is a well-known problem, however, that the high precision of these sensors leads to practical problems in probabilistic localization approaches such as Monte Carlo localization (MCL), because the likelihood function becomes extremely peaked if no means of regularization are applied. In practice, one therefore artificially smoothes the likelihood function or only integrates a small fraction of the measurements. In this paper we present a more fundamental and robust approach, that provides a smooth likelihood model for entire range scans. Additionally, it is location-dependent. In practical experiments we compare our approach to previous methods and demonstrate that it leads to a more robust localization.

IROS07: Global Urban Localization based on Road Maps

Jose Guivant and Roman Katz
ARC Centre of Excellence for Autonomous Systems
Australian Centre for Field Robotics
The University of Sydney, Australia

Abstract—This paper presents a method to perform localization in urban environments using segment-based maps together with particle filters. In the proposed approach, the likelihood function is generated as a grid, derived from segment-based maps. The scheme can efficiently assign weights to the particles in real time, with minimum memory requirements and without any additional pre-filtering procedure. Multi-hypotheses cases are handled transparently by the filter. A local history-based observation model is formulated as an extension to deal with ‘out-of-map’ navigation cases. This feature is highly desirable since the map can be incomplete, or the vehicle can be actually located outside the boundaries of the provided map. The system behaves like a ‘virtual GPS’, providing global localization in urban environments, without using an actual GPS. Experimental results show the performance of the proposed architecture in large scale urban environments using route network description (RNDF) segment-based maps.

SIGGRAPH 07: Seam Carving for Content-Aware Image Resizing

S. Avidan and A. Shamir
Seam Carving for Content-Based Image Retargeting
SIGGRAPH, San-Diego, 2007

Adobe's Avidan says that seam carving is fairly straightforward. If, for instance, a person wanted to compress a picture lengthwise by a single pixel, the software would scan the image to find the best pixels to remove. This is usually a zigzagging, vertical seam that is surrounded by pixels on the left and right that have a similar color. The pixel-wide seam is removed and the image is compressed without distorting the objects in the image. What makes the duo's algorithm impressive is that it can find and remove these pixels quickly, so a person can expand and compress a picture quickly. The process works well for photos with backgrounds such as sky or grass, in which there can be little variation in color and pattern, Avidan explains, although it works poorly for people's faces and more varied landscapes.

Video: Image Resizing by Seam Carving
News: New Tricks for Online Photo Editing

Online photo editor Rsizr implements the feature

CVPR07 poster: Wide-Area Egomotion Estimation from Known 3D Structure

Olivier Koch and Seth Teller

Robust egomotion recovery for extended camera excursions has long been a challenge for machine vision researchers. Existing algorithms handle spatially limited environments and tend to consume prohibitive computational resources with increasing excursion time and distance.

We describe an egomotion estimation algorithm that takes as input a coarse 3D model of an environment, and an omnidirectional video sequence captured within the environment, and produces as output a reconstruction of the camera’s 6-DOF egomotion expressed in the coordinates of the input model. The principal novelty of our method is a robust matching algorithm that associates 2D edges from the video with 3D line segments from the input model.

Our system handles 3-DOF and 6-DOF camera excursions of hundreds of meters within real, cluttered environments. It uses a novel prior visibility analysis to speed initialization and dramatically accelerate image-to-model matching. We demonstrate the method’s operation, and qualitatively and quantitatively evaluate its performance, on both synthetic and real image sequences.

[Paper] [Poster]

IEEE ITSS Newsletter vol 8 nr 4, December 2006

In this issue you will find a lot of interesting material:
- ITSS related news; in particular many new initiatives from the ITS Society
- technical papers
- conference reports and announcements
- research overview focusing nomadic devices in the new intelligent vehicles

You can find the ITSS Newsletter at the IEEE ITSS official web site address:
http://www.ewh.ieee.org/tc/its/
or directly at:
http://www.its.washington.edu/itsc/v8n4.pdf