Contact-rich tasks continue to present many challenges for robotic manipulation. In this work, we leverage a multimodal visuotactile sensor within the framework of imitation learning (IL) to perform contact-rich tasks that involve relative motion (e.g., slipping and sliding) between the end-effector and the manipulated object. We introduce two algorithmic contributions,tactile force matchingandlearned mode switching, as complimentary methods for improving IL. Tactile force matching enhances kinesthetic teaching by reading approximate forces during the demonstration and generating an adapted robot trajectory that recreates the recorded forces. Learned mode switching uses IL to couple visual and tactile sensor modes with the learned motion policy, simplifying the transition from reaching to contacting. We perform robotic manipulation experiments on four door-opening tasks with a variety of observation and algorithm configurations to study the utility of multimodal visuotactile sensing and our proposed improvements. Our results show that the inclusion of force matching raises average policy success rates by 62.5%, visuotactile mode switching by 30.3%, and visuotactile data as a policy input by 42.5%, emphasizing the value of see-through tactile sensing for IL, both for data collection to allow force matching, and for policy execution to enable accurate task feedback.

The accurate modeling of dynamics in interactive environments is critical for successful long-range prediction. Such a capability could advance Reinforcement Learning (RL) and Planning algorithms, but achieving it is challenging. Inaccuracies in model estimates can compound, resulting in increased errors over long horizons. We approach this problem from the lens of Koopman theory, where the nonlinear dynamics of the environment can be linearized in a high-dimensional latent space. This allows us to efficiently parallelize the sequential problem of long-range prediction using convolution while accounting for the agent's action at every time step. Our approach also enables stability analysis and better control over gradients through time. Taken together, these advantages result in significant improvement over the existing approaches, both in the efficiency and the accuracy of modeling dynamics over extended horizons. We also show that this model can be easily incorporated into dynamics modeling for model-based planning and model-free RL and report promising experimental results.

Converging evidence indicates that deep neural network models that are trained on large datasets are biased toward color and texture information. Humans, on the other hand, can easily recognize objects and scenes from images as well as from bounding contours. Mid-level vision is characterized by the recombination and organization of simple primary features into more complex ones by a set of so-called Gestalt grouping rules. While described qualitatively in the human literature, a computational implementation of these perceptual grouping rules is so far missing. In this article, we contribute a novel set of algorithms for the detection of contour-based cues in complex scenes. We use the medial axis transform (MAT) to locally score contours according to these grouping rules. We demonstrate the benefit of these cues for scene categorization in two ways: (i) Both human observers and CNN models categorize scenes most accurately when perceptual grouping information is emphasized. (ii) Weighting the contours with these measures boosts performance of a CNN model significantly compared to the use of unweighted contours. Our work suggests that, even though these measures are computed directly from contours in the image, current CNN models do not appear to extract or utilize these grouping cues.

In recent years there has been a resurgence of interest in our community in the shape analysis of 3D objects repre-sented by surface meshes, their voxelized interiors, or surface point clouds. In part, this interest has been stimulated by the increased availability of RGBD cameras, and by applications of computer vision to autonomous driving, medical imaging, and robotics. In these settings, spectral co-ordinates have shown promise for shape representation due to their ability to incorporate both local and global shape properties in a manner that is qualitatively invariant to iso-metric transformations. Yet, surprisingly, such coordinates have thus far typically considered only local surface positional or derivative information. In the present article, we propose to equip spectral coordinates with medial (object width) information, so as to enrich them. The key idea is to couple surface points that share a medial ball, via the weights of the adjacency matrix. We develop a spectral feature using this idea, and the algorithms to compute it. The incorporation of object width and medial coupling has direct benefits, as illustrated by our experiments on object classification, object part segmentation, and surface point correspondence.

We study a variety of notions of equivariance as an inductive bias in Reinforcement Learning (RL). In particular, we propose new mechanisms for learning representations that are equivariant to both the agent’s action, as well as symmetry transformations of the state-action pairs. Whereas prior work on exploiting symmetries in deep RL can only incorporate predefined linear transformations, our approach allows non-linear symmetry transformations of state-action pairs to be learned from the data. This is achieved through 1) equivariant Lie algebraic parameterization of state and action encodings, 2) equivariant latent transition models, and 3) the incorporation of symmetry-based losses. We demonstrate the advantages of our method, which we call Equivariant representations for RL (EqR), for Atari games in a data-efficient setting limited to 100K steps of interactions with the environment.

We combine ideas from shock graph theory with more recent appearance-based methods for medial axis extraction from complex natural scenes, improving upon the present best unsupervised method, in terms of efficiency and performance. We make the following specific contributions: i) we extend the shock graph representation to the domain of real images, by generalizing the shock type definitions using local, appearance-based criteria; ii) we then use the rules of a Shock Grammar to guide our search for medial points, drastically reducing run time when compared to other methods, which exhaustively consider all points in the input image; iii) we remove the need for typical post-processing steps including thinning, non-maximum suppression, and grouping, by adhering to the Shock Grammar rules while deriving the medial axis solution; iv) finally, we raise some fundamental concerns with the evaluation scheme used in previous work and propose a more appropriate alternative for assessing the performance of medial axis extraction from scenes. Our experiments on the BMAX500 and SK-LARGE datasets demonstrate the effectiveness of our approach. We outperform the present state-of-the-art, excelling particularly in the high-precision regime, while running an order of magnitude faster and requiring no post-processing.

Affinity graphs are widely used in deep architectures, including graph convolutional neural networks and attention networks. Thus far, the literature has focused on abstracting features from such graphs, while the learning of the affinities themselves has been overlooked. Here we propose a principled method to directly supervise the learning of weights in affinity graphs, to exploit meaningful connections between entities in the data source. Applied to a visual attention network, our affinity supervision improves relationship recovery between objects, even without the use of manually annotated relationship labels. We further show that affinity learning between objects boosts scene categorization performance and that the supervision of affinity can also be applied to graphs built from mini-batches, for neural network training. In an image classification task we demonstrate consistent improvement over the baseline, with diverse network architectures and datasets.

Computing object skeletons in natural images is challenging, owing to large variations in object appearance and scale, and the complexity of handling background clutter. Many recent methods frame object skeleton detection as a binary pixel classification problem, which is similar in spirit to learning-based edge detection, as well as to semantic segmentation methods. In the present article, we depart from this strategy by training a CNN to predict a two-dimensional vector field, which maps each scene point to a candidate skeleton pixel, in the spirit of flux-based skeletonization algorithms. This ``image context flux'' representation has two major advantages over previous approaches. First, it explicitly encodes the relative position of skeletal pixels to semantically meaningful entities, such as the image points in their spatial context, and hence also the implied object boundaries. Second, since the skeleton detection context is a region-based vector field, it is better able to cope with object parts of large width. We evaluate the proposed method on three benchmark datasets for skeleton detection and two for symmetry detection, achieving consistently superior performance over state-of-the-art methods.

Statistical shape modeling is a powerful tool for visualizing and quantifying geometric and functional patterns of the heart. After myocardial infarction (MI), the left ventricle typically remodels in response to physiological challenges. Several methods have been proposed in the literature to describe statistical shape changes. Which method best characterizes left ventricular remodeling after MI is an open research question. A better descriptor of remodeling is expected to provide a more accurate evaluation of disease status in MI patients. We therefore designed a challenge to test shape characterization in MI given a set of three-dimensional left ventricular surface points. The training set comprised 100 MI patients, and 100 asymptomatic volunteers (AV). The challenge was initiated in 2015 at the Statistical Atlases and Computational Models of the Heart workshop, in conjunction with the MICCAI conference. The training set with labels was provided to participants, who were asked to submit the likelihood of MI from a different (validation) set of 200 cases (100 AV and 100 MI). Sensitivity, specificity, accuracy and area under the receiver operating characteristic curve were used as the outcome measures. The goals of this challenge were to (1) establish a common dataset for evaluating statistical shape modeling algorithms in MI, and (2) test whether statistical shape modeling provides additional information characterizing MI patients over standard clinical measures. Eleven groups with a wide variety of classification and feature extraction approaches participated in this challenge. All methods achieved excellent classification results with accuracy ranges from 0.83 to 0.98. The areas under the receiver operating characteristic curves were all above 0.90. Four methods showed significantly higher performance than standard clinical measures. The dataset and software for evaluation are available from the Cardiac Atlas Project website1.

Abstract The heat kernel is a fundamental geometric object associated to every Riemannian manifold, used across applications in computer vision, graphics, and machine learning. In this article, we propose a novel computational approach to estimating the heat kernel of a statistically sampled manifold (e.g. meshes or point clouds), using its representation as the transition density function of Brownian motion on the manifold. Our approach first constructs a set of local approximations to the manifold via moving least squares. We then simulate Brownian motion on the manifold by stochastic numerical integration of the associated Ito diffusion system. By accumulating a number of these trajectories, a kernel density estimation method can then be used to approximate the transition density function of the diffusion process, which is equivalent to the heat kernel. We analyse our algorithm on the 2‐sphere, as well as on shapes in 3D. Our approach is readily parallelizable and can handle manifold samples of large size as well as surfaces of high co‐dimension, since all the computations are local. We relate our method to the standard approaches in diffusion geometry and discuss directions for future work.

We consider how to directly extract a road map (also known as a topological representation) of an initially-unknown 2-dimensional environment via an on-line procedure which robustly computes a retraction of its boundaries. While such approaches are well known for their theoretical elegance, computing such representations in practice is complicated when the data is sparse and noisy. In this paper we present the online construction of a topological map and the implementation of a control law for guiding the robot to the nearest unexplored area. The proposed method operates by allowing the robot to localize itself on a partially constructed map, calculate a path to unexplored parts of the environment (frontiers), compute a robust terminating condition when the robot has fully explored the environment, and achieve loop closure detection. The proposed algorithm results in smooth safe paths for the robot's navigation needs. The presented approach is an any-time-algorithm which allows for the active creation of topological maps from laser-scan data, as it is being acquired. The resulting map is stable under variations to noise and the initial conditions. The key idea is the use of a flux-based skeletonization algorithm on the latest occupancy grid map. We also propose a navigation strategy based on a heuristic where the robot is directed towards nodes in the topological map that open to empty space. The method is evaluated on both synthetic data and in the context of active exploration using a Turtlebot 2. Our results demonstrate complete mapping of different environments with smooth topological abstraction without spurious edges.

We study the space of first order models of smooth frame fields using the method of moving frames. By exploiting the Maurer-Cartan matrix of connection forms we develop geometrical embeddings for frame fields which lie on spherical, ellipsoidal and generalized helicoid surfaces. We design methods for optimizing connection forms in local neighborhoods and apply these to a statistical analysis of heart fiber geometry, using diffusion magnetic resonance imaging. This application of moving frames corroborates and extends recent characterizations of muscle fiber orientation in the heart wall, but also provides for a rich geometrical interpretation. In particular, we can now obtain direct local measurements of the variation of the helix and transverse angles, of fiber fanning and twisting, and of the curvatures of the heart wall in which these fibers lie.

The 2D stochastic completion field algorithm, introduced by Williams and Jacobs [1], [2], uses a directional random walk to model the prior probability of completion curves in the plane. This construct has had a powerful impact in computer vision, where it has been used to compute the shapes of likely completion curves between edge fragments in visual imagery. Motivated by these developments, we extend the algorithm to 3D, using a spherical harmonics basis to achieve a rotation invariant computational solution to the Fokker-Planck equation describing the evolution of the probability density function underlying the model. This provides a principled way to compute 3D completion patterns and to derive connectivity measures for orientation data in 3D, as arises in 3D tracking, motion capture, and medical imaging. We demonstrate the utility of the approach for the particular case of diffusion magnetic resonance imaging, where we derive connectivity maps for synthetic data, on a physical phantom and on an in vivo high angular resolution diffusion image of a human brain.

We study the problem of approximating a 3D solid with a union of overlapping spheres. In comparison with a state-of-the-art approach, our method offers more than an order of magnitude speedup and achieves a tighter approximation in terms of volume difference with the original solid while using fewer spheres. The spheres generated by our method are internal and tangent to the solid's boundary, which permits an exact error analysis, fast updates under local feature size preserving deformation, and conservative dilation. We show that our dilated spheres offer superior time and error performance in approximate separation distance tests than the state-of-the-art method for sphere set approximation for the class of (σ,θ)-fat solids. We envision that our sphere-based approximation will also prove useful for a range of other applications, including shape matching and shape segmentation.

Abstract In computer graphics, modeling the geometry of hair and hair‐like patterns such as grass and fur remains a significant challenge. Hair strands can exist in an extensive variety of arrangements and the choice of an appropriate representation for tasks such as hair synthesis, fitting, editing, or reconstruction from samples, is non‐trivial. To support such applications we present a novel mathematical representation of hair based on a class of minimal surfaces called generalized helicoids. This representation allows us to characterize the geometry of a single hair strand, as well as of those in its vicinity, by three intuitive curvature parameters and an elevation angle. We introduce algorithms for fitting piecewise generalized helicoids to unparameterized hair strands, and for interpolating hair between these fits. We showcase several applications of this representation including the synthesis of different hair geometries, wisp generation, hair interpolation from samples and hair‐style parametrization and reconstruction from real hair data.

This paper examines large partial occlusions in an image which occur near depth discontinuities when the foreground object is severely out of focus. We model these partial occlusions using matting, with the alpha value determined by the convolution of the blur kernel with a pinhole projection of the occluder. The main contribution is a method for removing the image contribution of the foreground occluder in regions of partial occlusion, which improves the visibility of the background scene. The method consists of three steps. First, the region of complete occlusion is estimated using a curve evolution method. Second, the alpha value at each pixel in the partly occluded region is estimated. Third, the intensity contribution of the foreground occluder is removed in regions of partial occlusion. Experiments demonstrate the method's ability to remove the effects of partial occlusion in single images with minimal user input.

We present a method to remove partial occlusion that arises from out-of-focus thin foreground occluders such as wires, branches, or a fence. Such partial occlusion causes the irradiance at a pixel to be a weighted sum of the radiances of a blurred foreground occluder and that of the background. The result is that the background component has lower contrast than it would if seen without the occluder. In order to remove the contribution of the foreground in such regions, we characterize the position and size of the occluder in a narrow aperture image. In subsequent images with wider apertures, we use this characterization to remove the contribution of the foreground, thereby restoring contrast in the background. We demonstrate our method on real camera images without assuming that the background is static.

We describe a geometric-flow-based algorithm for computing a dense oversegmentation of an image, often referred to as superpixels. It produces segments that, on one hand, respect local image boundaries, while, on the other hand, limiting undersegmentation through a compactness constraint. It is very fast, with complexity that is approximately linear in image size, and can be applied to megapixel sized images with high superpixel densities in a matter of minutes. We show qualitative demonstrations of high-quality results on several complex images. The Berkeley database is used to quantitatively compare its performance to a number of oversegmentation algorithms, showing that it yields less undersegmentation than algorithms that lack a compactness constraint while offering a significant speedup over N-cuts, which does enforce compactness.

Medial descriptions, such as shock graphs, have gained significant momentum in the shape-based object recognition community due to their invariance to translation, rotation, scale and articulation and their ability to cope with moderate amounts of within-class deformation. While they attempt to decompose a shape into a set of parts, this decomposition can suffer from ligature-induced instability. In particular, the addition of even a small part can have a dramatic impact on the representation in the vicinity of its attachment. We present an algorithm for identifying and representing the ligature structure, and restoring the non-ligature structures that remain. This leads to a bone graph, a new medial shape abstraction that captures a more intuitive notion of an objectpsilas parts than a skeleton or a shock graph, and offers improved stability and within-class deformation invariance. We demonstrate these advantages by comparing the use of bone graphs to shock graphs in a set of view-based object recognition and pose estimation trials.

Configurations of dense locally parallel 3D curves occur in medical imaging, computer vision and graphics. Examples include white matter fibre tracts, textures, fur and hair. We develop a differential geometric characterization of such structures by considering the local behaviour of the associated 3D frame field, leading to the associated tangential, normal and bi-normal curvature functions. Using results from the theory of generalized minimal surfaces we adopt a generalized helicoid model as an osculating object and develop the connection between its parameters and these curvature functions. These developments allow for the construction of parametrized 3D vector fields (sampled osculating objects) to locally approximate these patterns. We apply these results to the analysis of diffusion MRI data via a type of 3D streamline flow. Experimental results on data from a human brain demonstrate the advantages of incorporating the full differential geometry.

Hierarchical image structures are abundant in computer vision and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a framework for indexing such representations that embeds the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel spectral characterization of a DAG, this topological signature allows us to efficiently retrieve a promising set of candidates from a database of models using a simple nearest-neighbor search. We establish the insensitivity of the signature to minor perturbation of graph structure due to noise, occlusion, or node split/merge. To accommodate large-scale occlusion, the DAG rooted at each nonleaf node of the query "votes" for model objects that share that "part," effectively accumulating local evidence in a model DAG's topological subspaces. We demonstrate the approach with a series of indexing experiments in the domain of view-based 3D object recognition using shock graphs.

We present a fast, robust and automatic method for computing central paths through tubular structures for application to virtual endoscopy. The key idea is to utilize a medial surface algorithm, which exploits properties of the average outward flux of the gradient vector field of a Euclidean distance function the boundary of the structure of interest. The algorithm is modified to yield a collection of 3D curves, each of which is locally centered. The approach requires no user interaction, and is virtually parameter free and has low computational complexity. We illustrate the approach on segmented colon and vessel data.

We consider the average outward flux through a Jordan curve of the gradient vector field of the Euclidean distance function to the boundary of a 2D shape. Using an alternate form of the divergence theorem, we show that in the limit as the area of the region enclosed by such a curve shrinks to zero, this measure has very different behaviors at medial points than at non-medial ones, providing a theoretical justification for its use in the Hamilton-Jacobi skeletonization algorithm of Siddiqi et al. (2002). We then specialize to the case of shrinking circular neighborhoods and show that the average outward flux measure also reveals the object angle at skeletal points. Hence, formulae for obtaining the boundary curves, their curvatures, and other geometric quantities of interest, can be written in terms of the average outward flux limit values at skeletal points. Thus this measure can be viewed as a Euclidean invariant for shape description: it can be used to both detect the skeleton from the Euclidean distance function, as well as to explicitly reconstruct the boundary from it. We illustrate our results with several numerical simulations.

We employ a conformal mapping technique to flatten tubular structures with multi-branches for visualization of MRA and CT volumetric vessel imagery. This may be used for the study of possible vessel pathology or virtual colonoscopy for polyp detection. The method is based on a discrete Laplace-Beltrami operator to flatten a tubular surface onto a planar polygonal region in an angle-preserving manner. A thinned pruned medial surface (or skeleton) is used for the vessel partition.

Several geometric active contour models have been proposed for segmentation in computer vision and image analysis. The essential idea is to evolve a curve (in 2D) or a surface (in 3D) under constraints from image forces so that it clings to features of interest in an intensity image. Recent variations on this theme take into account properties of enclosed regions and allow for multiple curves or surfaces to be simultaneously represented. However, it is still unclear how to apply these techniques to images of narrow elongated structures, such as blood vessels, where intensity contrast may be low and reliable region statistics cannot be computed. To address this problem, we derive the gradient flows which maximize the rate of increase of flux of an appropriate vector field through a curve (in 2D) or a surface (in 3D). The key idea is to exploit the direction of the vector field along with its magnitude. The calculations lead to a simple and elegant interpretation which is essentially parameter free and has the same form in both dimensions. We illustrate its advantages with several level-set-based segmentations of 2D and 3D angiography images of blood vessels.

There has recently been significant interest in using representations based on abstractions of Bhum's skeleton into a graph, for qualitative shape matching. The application of these techniques to large databases of shapes hinges on the availability of numerical algorithms for computing the medial axis. Unfortunately this computation can be extremely subtle. Approaches based on Voronoi techniques preserve topology but heuristic pruning measures are introduced to remove unwanted edges. Methods based on Euclidean distance functions can localize skeletal points accurately, but often at the cost of altering the object's topology. In this paper we introduce a new algorithm for computing subpixel skeletons which is robust and accurate, has low computational complexity and preserves topology. The key idea is to measure the net outward flux of a vector field per unit area, and to detect locations where a conservation of energy principle is violated. This is done in conjunction with a thinning process applied in a rectangular lattice. We illustrate the approach with several examples of skeletal graphs for biological and man-made silhouettes.

The matching of hierarchical relational structures is of significant interest in computer vision and pattern recognition. We have recently introduced a new solution to this problem, based on a maximum clique formulation in an (derived) "association graph". This allows us to exploit the full arsenal of clique finding algorithms developed in the algorithm community. However, thus far we have only focussed on one-to-one correspondences (isomorphisms), which appears to be too strict a requirement for many vision problems. In this paper we provide a generalization of the association graph framework to handle many-to-one correspondences. We define a notion of an /spl epsiv/-homomorphism (a many-to-one mapping) between attributed trees, and provide a method of constructing a weighted association graph where maximal weight cliques are in one-to-one correspondence with maximal similarity subtree homomorphisms. We then solve the problem by using replicator dynamical systems from the evolutionary game theory.

Although the classical Blum skeleton has long been considered unstable, many have attempted to alleviate this defect through pruning. Unfortunately, these methods have an arbitrary basis, and, more importantly, they do not prevent internal structural alterations due to slight changes in an object's boundary. The result is a relative lack of development of skeleton representations for indexing object databases, despite a long history. Here we revisit a subset of the skeleton-called ligature by Blum-to demonstrate how the topological sensitivity of the skeleton can be eliminated. We relate ligature to a natural growth principle to provide an account of the perceptual parts of shape.

In an object recognition system, if the extracted image features are multilevel or multiscale, the indexing structure may take the form of a tree. Such structures are not only common in computer vision, but also appear in linguistics, graphics, computational biology, and a wide range of other domains. In this paper, we develop an indexing mechanism that maps the topological structure of a tree into a low-dimensional vector space. Based on a novel eigenvalue characterization of a tree, this topological signature allows us to efficiently retrieve a small set of candidates from a database of models. To accommodate occlusion and local deformation, local evidence is accumulated in each of the tree's topological subspaces. We demonstrate the approach with a series of indexing experiments in the domain of 2-D object recognition.

The eikonal equation and variants of it are of significant interest for problems in computer vision and image processing. It is the basis for continuous versions of mathematical morphology, stereo, shape-from-shading and for recent dynamic theories of shape. Its numerical simulation can be delicate, owing to the formation of singularities in the evolving front, and is typically based or, level set methods. However there are more classical approaches rooted in Hamiltonian physics, which have received little consideration in computer vision. In this paper we first introduce a new algorithm for simulating the eikonal equation, which offers a number of computational and conceptual advantages over the earlier methods when it comes to shock tracking. Next, we introduce a very efficient algorithm for shock detection, where the key idea is to measure the net outward flux of a vector field per unit volume, and to detect locations where a conservation of energy principle is violated. We illustrate the approach with several numerical examples including skeletons of complex 2D and 3D shapes.

Bounding contours of physical objects are often fragmented by other occluding objects. Long-distance perceptual grouping seeks to join fragments belonging to the same object. Approaches to grouping based on invariants assume objects are in restricted classes, while those based on minimal energy continuations assume a shape for the missing contours and require this shape to drive the grouping process. While these assumptions may be appropriate for certain specific tasks or when contour gaps are small, in general occlusion can give rise to large gaps, and thus long-distance contour fragment grouping is a different type of perceptual organization problem. We propose the long-distance principle that those fragments should be grouped whose fragmentation could have arisen from a shared, simple occluder. The gap skeleton is introduced as a representation of this virtual occluder, and an algorithm for computing it is given. Finally, we show that a view of the virtual occluder as a disk can be interpreted as an equivalence class of curves interpolating the fragment endpoints.

Although the classical Blum skeleton has long been considered unstable, many have attempted to alleviate this defect through pruning. Unfortunately, these methods have an arbitrary basis, and, more importantly, they do not prevent internal structural alterations due to slight changes in an object's boundary. The result is a relative lack of development of skeleton representations for indexing object databases, despite a long history. Here we revisit a subset of the skeleton—called ligature by Blum—to demonstrate how the topological sensitivity of the skeleton can be alleviated. In particular, we show how the deletion of ligature regions leads to stable hierarchical descriptions, illustrating this point with several computational examples. We then relate ligature to a natural growth principle to provide an account of the perceptual parts of shape. Finally, we discuss the duality between the problems of part decomposition and contour fragment grouping.

We earlier introduced an approach to categorical shape description based on the singularities (shocks) of curve evolution equations. The approach relates to many techniques in computer vision, such as Blum's grassfire transform, but since the motivation was abstract it is not clear that it should also relate to human perception. We now report that this shock-based computational model can account for recent psychophysical data collected by Burbeck and Pizer. In these experiments subjects were asked to estimate the local centers of stimuli consisting of rectangles with `wiggles' (sides modulated by sinusoids). Since the experiments were motivated by their `core' model, in which the scale of boundary detail is proportional to object width, we conclude that such properties are also implicit in shock-based shape descriptions. More generally, the results suggest that significance is a structural notion, not an image-based one, and that scale should be defined primarily in terms of relationships between abstract entities, not concrete pixels.

It is well-known that the problem of matching two relational structures can be posed as an equivalent problem of finding a maximal clique in a (derived) "association graph." However, it is not clear how to apply this approach to computer vision problems where the graphs are hierarchically organized, i.e., are trees, since maximal cliques are not constrained to preserve the partial order. We provide a solution to the problem of matching two trees by constructing the association graph using the graph-theoretic concept of connectivity. We prove that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms. This allows us to cast the tree matching problem as an indefinite quadratic program using the Motzkin-Straus theorem, and we use "replicator" dynamical systems developed in theoretical biology to solve it. Such continuous solutions to discrete problems are attractive because they can motivate analog and biological implementations. The framework is also extended to the matching of attributed trees by using weighted association graphs. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.

We have been developing a theory for the generic representation of 2-D shape, where structural descriptions are derived from the shocks (singularities) of a curve evolution process, acting on bounding contours. We now apply the theory to the problem of shape matching. The shocks are organized into a directed, acyclic shock graph, and complexity is managed by attending to the most significant (central) shape components first. The space of all such graphs is highly structured and can be characterized by the rules of a shock graph grammar. The grammar permits a reduction of a shockgraph to a unique rooted shock tree. We introduce a novel tree matching algorithm which finds the best set of corresponding nodes between two shock trees in polynomial time. Using a diverse database of shapes, we demonstrate our system's performance under articulation, occlusion, and changes in viewpoint.

We have been developing a theory of generic 2-D shape based on a reaction-diffusion model from mathematical physics. The description of a shape is derived from the singularities of a curve evolution process driven by the reaction (hyperbolic) term. The diffusion (parabolic) term is related to smoothing and shape simplification. However, the unification of the two is problematic, because the slightest amount of diffusion dominates and prevents the formation of generic first-order shocks. The technical issue is whether it is possible to smooth a shape, in any sense, without destroying the shocks. We now report a constructive solution to this problem, by embedding the smoothing term in a global metric against which a purely hyperbolic evolution is performed from the initial curve. This is a new flow for shape, that extends the advantages of the original one. Specific metrics are developed, which lead to a natural hierarchy of shape features, analogous to the simplification one might perceive when viewing an object from increasing distances. We illustrate our new flow with a variety of examples.

A number of active contour models have been proposed that unify the curve evolution framework with classical energy minimization techniques for segmentation, such as snakes. The essential idea is to evolve a curve (in two dimensions) or a surface (in three dimensions) under constraints from image forces so that it clings to features of interest in an intensity image. The evolution equation has been derived from first principles as the gradient flow that minimizes a modified length functional, tailored to features such as edges. However, because the flow may be slow to converge in practice, a constant (hyperbolic) term is added to keep the curve/surface moving in the desired direction. We derive a modification of this term based on the gradient flow derived from a weighted area functional, with image dependent weighting factor. When combined with the earlier modified length gradient flow, we obtain a partial differential equation (PDE) that offers a number of advantages, as illustrated by several examples of shape segmentation on medical images. In many cases the weighted area flow may be used on its own, with significant computational savings.

Several active contour models have been proposed to unify the curve evolution framework with classical energy minimization techniques for segmentation, such as snakes. The essential idea is to evolve a curve (in 2D) or a surface (in 3D) under constraints from image forces so that it clings to features of interest in an intensity image. Recently the evolution equation has been derived from first principles as the gradient flow that minimizes a modified length functional, tailored to features such as edges. However, because the flow may be slow to converge in practice, a constant (hyperbolic) term is added to keep the curve/surface moving in the desired direction. The authors provide a justification for this term based on the gradient flow derived from a weighted area functional, with image dependent weighting factor. When combined with the earlier modified length gradient flow they obtain a PDE which offers a number of advantages, as illustrated by several examples of shape segmentation on medical images. In many cases the weighted area flow may be used on its own, with significant computational savings.

Several active contour models have been proposed to unify the curve evolution framework with classical energy minimization techniques for segmentation, such as snakes. The essential idea is to evolve a curve (in 2D) or a surface (in 3D) under constraints from image forces so that it clings to features of interest in an intensity image. The evolution equation has been derived from first principles as the gradient flow that minimizes a modified length functional, tailored to features such as edges. However, because the flow may be slow to converge in practice, a constant (hyperbolic) term is added to keep the curve/surface moving in the desired direction. We provide a justification, for this term based on the gradient flow derived from a weighted area functional, with an image dependent weighting factor. When combined with the earlier modified length gradient flow we obtain a partial differential equation (PDE) which offers a number of advantages, as illustrated by several examples of shape segmentation on medical images. In many cases the weighted area flow may be used on its own, with significant computational savings.

Subpixel methods that locate curves and their singularities, and that accurately measure geometric quantities, such as orientation and curvature, are of significant importance in computer vision and graphics. Such methods often use local surface fits or structural models for a local neighborhood of the curve to obtain the interpolated curve. Whereas their performance is good in smooth regions of the curve, it is typically poor in the vicinity of singularities. Similarly, the computation of geometric quantities is often regularized to deal with noise present in discrete data. However, in the process, discontinuities are blurred over, leading to poor estimates at them and in their vicinity. In this paper we propose a geometric interpolation technique to overcome these limitations by locating curves and obtaining geometric estimates while (1) not blurring across discontinuities and (2) explicitly and accurately placing them. The essential idea is to avoid the propagation of information across singularities. This is accomplished by a one-sided smoothing technique, where information is propagated from the direction of the side with the “smoother” neighborhood. When both sides are nonsmooth, the two existing discontinuities are relieved by placing a single discontinuity, or shock. The placement of shocks is guided by geometric continuity constraints, resulting in subpixel interpolation with accurate geometric estimates. Since the technique was originally motivated by curve evolution applications, we demonstrate its usefulness in capturing not only smooth evolving curves, but also ones with orientation discontinuities. In particular, the technique is shown to be far better than traditional methods when multiple or entire curves are present in a very small neighborhood.

We confront the theoretical and practical difficulties of computing a representation for two-dimensional shape, based on shocks or singularities that arise as the shape's boundary is deformed. First, we develop subpixel local detectors for finding and classifying shocks. Second, to show that shock patterns are not arbitrary but obey the rules of a grammar, and in addition satisfy specific topological and geometric constraints. Shock hypotheses that violate the grammar or are topologically or geometrically invalid are pruned to enforce global consistency. Survivors are organized into a hierarchical graph of shock groups computed in the reaction-diffusion space, where diffusion plays a role of regularization to determine the significance of each shock group. The shock groups can be functionally related to the object's parts, protrusions and bends, and the representation is suited to recognition: several examples illustrate its stability with rotations, scale changes, occlusion and movement of parts, even at very low resolutions.

Bounding contours of physical objects are often fragmented by other occluding objects. Long-distance perceptual grouping seeks to join fragments belonging to the same object. Approaches to grouping based on invariants assume objects are in restricted classes, while those based on minimal energy continuations assume a shape for the missing contours and require this shape to drive the grouping process. We propose the more general principle that those fragments should be grouped whose fragmentation could have arisen from a generic occluder. The gap skeleton is introduced as a representation of this virtual occluder, and an algorithm for computing it is given.

We present an approach to recognition that is based on partitioning and invariant recognition in a Bayesian framework. The intended application domain is that of complex articulated objects in arbitrary position and under considerable occlusion. First, since the performance of traditional model-based recognition strategies degrades with increasing object data-base size, with partial occlusion, and with articulation, we employ a partitioning that does not rely on apriori primitives or models. Rather, this scheme decomposes segmented shapes into parts, where the form of each part is not known apriori, but is derived based on generic geometric assumptions about objects and their projections. Specifically, two types of parts, neck-based and limb-based, give rise to a shape decomposition that remains invariant under occlusion in the visible portion of the object, unaltered under articulation of parts, is stable under slight changes in viewing geometry and finally is robust with changes in resolution and scale. Second, the parts derived from the first stage are described by implicit polynomial curves. These polynomials represent the parts well and are computationally simple to fit to the data. However, the great advantage in using implicit polynomials is the algebraic invariance associated with them. Each part is represented by a vector of invariants that remains essentially independent of viewing geometry, and as such is suitable for matching purposes. The matching process is a Bayesian engine based on asymptotic distributions. In the conclusion section, we briefly indicate how this technology fits into a complete object recognition system.

Underlying recognition is an organization of objects and their parts into classes and hierarchies. A representation of parts for recognition requires that they be invariant to rigid transformations, robust in the presence of occlusions, stable with changes in viewing geometry, and be arranged in a hierarchy. These constraints are captured in a general framework using notions of a PART-LINE and a PARTITIONING SCHEME. A proposed general principle of "form from function" motivates a particular partitioning scheme involving two types of parts, neck-based and limb-based. Neck-based parts arise from narrowings in shape, or the local minima in distance between two points on the boundary, while limb-based parts arise from a pair of negative curvature minima which have "co-circular" tangents. In this paper, we present computational support for the limb-based and neck-based parts by showing that they are invariant, robust, stable and yield a hierarchy of parts. Examples illustrate that the resulting decompositions are robust in the presence of occlusion and clutter for a range of man-made and natural objects, and lead to natural and intuitive parts which can be used for recognition.>

We propose a geometric smoothing method based on local curvature in shapes and images which is governed by the geometric heat equation and is a special case of the reaction-diffusion framework proposed by Faugeras (1990). For shapes, the approach is analogous to the classical heat equation smoothing, but with a renormalization by arc-length at each infinitesimal step. For images, the smoothing is similar to anisotropic diffusion in that, since the component of diffusion in the direction of the brightness gradient is nil, edge location and sharpness are left intact. We present several properties of curvature deformation smoothing of shape: it preserves inclusion order, annihilates extrema and inflection points without creating new ones, decreases total curvature, satisfies the semi-group property allowing for local iterative computations, etc. Curvature deformation smoothing of an image is based on viewing it as a collection of iso-intensity level sets, each of which is smoothed by curvature and then reassembled. This is shown to be mathematically sound and applicable to medical, aerial and range images.>

A proposed general principle of form from function motivates a particular partitioning scheme involving two types of parts, neck-based and limb-based. Neck-based parts arise from narrowings in shape, or the local minima in distance between two points on the boundary, while limb-based parts arise from a pair of negative curvature extrema which have co-circular tangents. Computational support for the limb-based and neck-based parts is presented by showing that they are invariant, robust, stable, and yield a hierarchy of parts. Examples illustrate that the resulting decompositions are robust in the presence of occlusion and noise for a range of man-made and natural objects and that they lead to natural and intuitive parts which can be used for recognition.>