Princeton University & NEC Research Institute Princeton, New Jersey October 28-30, 2001

Helmut Alt
Free University of Berlin

Geometric Methods in Shape Recognition and Matching

The talk will present work that has been done in our group in recent years on comparison and matching of shapes.  We assume that planar shapes are represented by polygonal curves and consider several {\em distance measures} to describe similarity between shapes, in particular the Hausdorff- and the Fre'chet-distance. Algorithms for measuring the distance between two shapes will be presented. Also the problem of {\em matching} shapes optimally with respect to a given distance measure will be considered. There are different variants of this problem depending on the set of allowable transformations, like translations, rigid motions, similarities etc. Also a few generalizations to three and higher dimensions will be presented. (project web page)

Medial Axis Approximation and Map Skeletonization

I will survey computational methods for approximating the medial axis in 3D (including my own), define a relationship between the medial axis and a related structure, the skeleton of a smooth map from R3->R, and speculate on methods for approximate skeletonization. (project web page)

The Shape of Proteins

Molecules have forever been modeled geometrically, either as stick-diagrams, emphasizing the covalent bonds between atoms, or as space-filling diagrams, representing the space they occupy.  This talk aims at further developing the geometric view of the molecular world.  We focus on local complementarity and feature analysis of smooth surface representations. (project web page)

Funding Opportunities at NSF

This talk will summarize various funding opportunities and trends at the National Science Foundation.    New money often flows to new initiatives, such as ITR, instead of to the regular programs.   Indeed those may even be cut back to support the new priorities.   Maximizing the impact by applying pure science to society, perhaps by collaborations with researchers in other disciplines, is also encouraged.

Shape Models for Medical Image Analysis

A central problem in medical image analysis is segmenting volumetric medical scans into models of anatomical tissue.  These models are crucial in supporting surgical planning and guidance.  While statistics of image intensities can guide the labelling of voxels by tissue type, anatomical knowledge is often required for robust segmentation.  In particular, knowledge of the distribution of shapes of a structure can guide the segmentation of noisy data and the localization of subtle boundaries.  By training a segmenter with a set of labelled images, one can extract statistical distributions on anatomical shapes and their common variations across a patient population.  This data forms a statistical prior on segmentation of new images, leading to robust performance even near subtle boundaries.
 

Recognition and Modeling of Objects from Local Shape

We present recent results on building 3-D models in a completely unconstrained manner from training views. The models can be used as starting points for recognition algorithms. For complex 3-D objects, recognition cannot rely solely on local appearance because of complex occlusion geometry and geometric transformations. We explore ways to capture shape constraints  by grouping local image features and matching images of 3-D objects with models based on the configurations of the groups. The goal is to assess the feasibility of representing complex shape for the purpose of recognition through arrangements of local features.

Matching Pictorial Structures

Reflective Symmetry Detection in Three Dimensions

In this talk, we present the reflective symmetry descriptor of a voxel model: a function that gives the measure of reflective symmetry of the model with respect to every reflection. We define the symmetry descriptor, show how it can be computed efficiently, and present applications in the areas of model registration and model matching. (powerpoint slides)

3D Shock Scaffold

The usefulness of the 3D Medial Axis (MA) is dependent on both the availability of accurate and stable methods for computing individual MA points and on schemes for deriving the local structure and connectivity among these points.  We propose a framework which achieves both by combining the advantages of exact bisector computations used in computational geometry, on the one hand, and the local nature of propagation-based algorithms, on the other, but without the computational complexity, connectivity, added dimensionality, and post processing issues commonly found in these approaches.  Specifically, the notion of flow of shocks along the MA manifold is used to identify flow along special points and curves which define a SHOCK SCAFFOLD. This 1D scaffold is of lower dimensional complexity than the typical geometric locus of medial points which are represented as 2D sheets. The scaffold not only organizes shape information in a hierarchical manner, but is a tool for the efficient recovery of the scaffold itself
and can lead to exact reconstruction.  We present examples of this approach for synthetic data, as well as for sherd data from the domain of digital archaeology. (project web page)

Structure of Pictorial Relief

When a human observer looks at a picture it appears as a two dimensional sheet covered with pigments in some simultaneous order. When the observer looks IN the picture a three dimensional pictorial space appears. The structure of this space differs from Euclidean space, for instance, rotations about axes parallel to the picture plane are parabolic (non-periodic). (For you can never see the back of the head of a person in a frontal portrait.) Analysis of the ambiguities of depth cues reveals the group of congruences of pictorial space. Pictorial relief is (by definition) the total of differential invariants of this group. This allows us to construct a complete theory of pictorial relief. Although in many respects similar to Euclidean shape, pictorial relief is different, the formal expressions being generally much simpler than in the familiar Euclidean differential geometry.

Image Searching: What You See Is What You Get, But Not What You Want

The basic paradigm for image retrieval is to crawl around the image with some low-level feature extractor, and then use the numbers resulting as classifiers for retrieval.  The simplest feature to extract is the color histogram, which is why Robert Wilensky always says to be suspicious of any image retrieval demo which concentrates on finding pictures of sunsets. Although we have moved on from that, we are still well short of something a photo or film librarian would use.   About half the queries asked of a film librarian require knowing the names of things in a picture - not just "tower" or "river" but "Eiffel Tower" or "River Seine".  Thus it may be as important to pursue projects based on recognizing existing images from a dictionary (e.g. faces) as to do basic feature extraction and classification.

Some interesting projects are the shape recognition and image labeling work at Berkeley (Malik and Forsyth), scale and viewpoint invariance search at Oxford (Zisserman), and face recognition at CMU.  Interesting applications include analysis of aerial photographs, analyzing images of geological structures, and (recently) a stress on individual tracking by looking through pictures.  The most recent research frontier is in 3-D models and searching, ranging from historic building reconstruction to drug design.
 

Unification of Vision, Geometry and Graphics Through Software Toolkits

Shape Matching and Recognition Using Shape Contexts

Considering a shape as a point set, the key issue is the arrangement of the points with respect to each other. This is captured conveniently by attaching to each point, a descriptor that we call the shape context. For a given point, this is a histogram in (log r, theta) space of the remaining points relative to it. By design, the shape context descriptor is translation and scale-invariant, and can be made rotation-invariant if it is necessary for a particular application. Shape contexts help solve a number of algorithmic problems associated with shape matching: (1) Corresponding points on two similar shapes will have similar shape contexts, enabling us to determine the correspondences as an optimal assignment problem. (2) Given the point correspondences, we can estimate the transformation that best aligns the two shapes; this enables one to operationalize a deformable template view (cf. D'Arcy Thompson) of shape matching. (3) This in turn enables one to define a notion of shape dissimilarity or distance as a sum of errors between corresponding points, together with a term measuring the magnitude of the aligning transform.

We have addressed a number of different applications using these techniques: (1) efficient retrieval of similar shapes (2) object recognition from 2D images using a nearest-neighbor classifier, for datasets such as handwritten digits, silhouettes and the MPEG-7 shape benchmark (3) estimating human body configurations in 3D using only a single 2D image. (project web page)

This talk is based on joint work with Serge Belongie, Greg Mori and Jan Puzicha.

Shape Models for Tracking, Recognition and Medical Applications

Evaluating Query Types for a 3D Model Search Engine

A potential application for shape analysis is a web search engine for 3D models. It is not obvious what form a query for such an engine should take: do we ask the user to, for example, create a simple 3D model, draw a 2D outline, or will a text query be sufficient? Apart from the issue of user-friendliness, the question is which types of input produce a useful result. We implemented a 3D model search engine, and evaluated the effectiveness of various types of 2D and 3D input, as well as a text only interface. (project web page) (powerpoint slides).

This is joint work with Joyce Chen and Tom Funkhouser.

Matching 3D Models with Shape Distributions

In this talk, we describe a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as a shape distribution sampled from a shape function measuring global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence, or model fitting. We find that the dissimilarities between sampled distributions of simple shape functions (e.g., the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g., cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, mirrors, tessellations, simplifications, and model degeneracies. They can be evaluated quickly, and thus the proposed method can be applied as a pre-classifier in a shape-based retrieval or analysis system. (powerpoint slides)

This is joint work with Thomas Funkhouser, Bernard Chazelle, and David Dobkin.

Issues in 3D Object Recognition

I will address the problem of recognizing three-dimensional objects from a single photograph, and discuss some representational issues involved in attempting to solve this problem: what are appropriate models for objects, image appearance, image formation and the recognition process? How do we recognize specific object instances and distinguish between object categories? I will illustrate some of these issues with a recognition system being developed in collaboration with David Kriegman and his students, that is capable of automatically acquiring geometric (but not three-dimensional) models of moderately complex objects from relatively small sets of viewpoints, and match new images of these objects to their stored models, but does not address the fundamental problem of recognizing object at the category level. (powerpoint slides)

Joint work with David Kriegman, Amit Sethi, and David Renaudie.

A Unified Non-rigid Feature Registration Method for Brain Mapping

We describe the design, implementation and results of a unified non-rigid feature registration method for the purposes of anatomical MRI brain registration. The method draws on our previous work on robust non-rigid point matching but with a crucial difference. In contrast to previous work, we pose the feature registration problem in a many-to-many as opposed to one-to-one matching framework. Our new non-rigid registration method implements  an iterative joint clustering and matching (JCM) strategy which effectively reduces the computational complexity, and ensures many-to-many matching. We demonstrate the application of the method using two different types of cortical anatomical features: the outer cortical surface and major sulcal ribbons. Points sub-sampled from each type of feature are fused into a common 3D point-set representation. We have conducted carefully designed synthetic experiments to study the effect of using different types of features either separately or together. A validation study examining the accuracy of non-rigid alignment of many brain structures is also presented. Finally, we extend the approach to the construction of anatomical atlases.

Shape Analysis in the Compression and Progressive Transmission of 3D Models

The speaker will discuss the fundamental technologies for the compression, simplification, and progressive transmission of 3D shapes and will point out open problems and needs for advanced shape analysis tools. (project web page)

Speed and Robustness in 3D Model Registration

The Iterative Closest Points (ICP) algorithm is the most widely used technique for registering 3D models, especially in applications such as aligning 3D scans.  Recent work has incorporated feature matching, soft assignment of correspondences, and non-rigid deformation to improve on the robustness of ICP under difficult conditions.  On the other hand, simplifications to ICP can result in an algorithm that aligns two models in a few milliseconds, thus permitting real-time applications.  In this talk, I will explore the relative benefits of smarts and simplicity at different stages of model registration, and examine whether it is possible to obtain some of the benefits of robust feature-based methods while retaining fast running times. (powerpoint slides)

Hamilton-Jacobi Skeletons

In this talk we review the Hamiltonian formulation of the eikonal equation, which offers specific advantages when it comes to the detection of singularities or shocks of a surface evolution process acting on the bounding surface of an object.  We specialize to the case of Blum's grassfire flow and measure the average outward flux of the vector field that underlies the Hamiltonian system. This measure has very different limiting behaviors depending upon whether the region over which it is computed shrinks to a singular point or a non-singular one. Hence, it is an effective way to distinguish between these two cases. We combine the flux measurement with a homotopy preserving thinning process applied in a discrete lattice.  This leads to a robust and accurate algorithm for computing skeletons in 3D, which has low computational complexity. We illustrate the approach with several computational examples. (project web page)

Joint work with Sylvain Bouix, Allen Tannenbaum and Steven W. Zucker

Normal Meshes and Digital Geometry Compression

Digital Geometry - large polygonal meshes coming from digitizing of complex geometry - is the fourth wave of multimedia after sound,  images, and video. However, unlike sound, images, and video, geometry is not defined on a Euclidean space and traditional  Fourier/DCT based techniques for representation/compression no longer apply.  Instead we propose a new paradigm called normal meshes formed by recursive subdivision and local normal displacements. We show how parameterizations can be used to build normal meshes and how normal meshes lead to superior compression capabilities.  Finally we show some recent theoretical results on regularity, stability, and approximation of normal meshes.
 

Retrieval of Three-Dimensional Models with Relevance Feedback

We examine the problem of searching a database of three-dimensional objects for objects similar to a given  object. We introduce an algorithm which is both iterative and interactive. Rather than base the search solely on geometric feature similarity, we propose letting the user influence future search results by marking some of the results of the current search as `relevant' or `irrelevant', thus indicating personal preferences. A novel approach, based on Support Vector Machine (SVM), is used for the adaptation of the distance measure consistently with this relevance feedback, which brings the `relevant' objects closer and pushes the `irrelevant' objects farther. We show that in practice very few iterations are needed for the system to retrieve the objects the user ``had in mind''.

This is a joint work with Michael Elad and Sigal Ar.