Abstract. We model the functional architecture of the early stages of three-dimensional vision by extending the neurogeometric sub-Riemannian model for stereovision introduced in [M. V. Bolelli, G. Citti, A. Sarti, and S. W. Zucker, Front. Comput. Sci., 5 (2024), 1142621]. A new framework for correspondence is introduced that integrates a neural-based algorithm to achieve stereo correspondence locally while simultaneously organizing the corresponding points into global perceptual units. The result is an effective scene segmentation. We achieve this using harmonic analysis on the sub-Riemannian structure and show, in a comparison against Riemannian distance, that the sub-Riemannian metric is central to the solution.

The static synaptic connectivity of neuronal circuits stands in direct contrast to the dynamics of their function. As in changing community interactions, different neurons can participate actively in various combinations to effect behaviors at different times. We introduce an unsupervised approach to learn the dynamic affinities between neurons in live, behaving animals, and to reveal which communities form among neurons at different times. The inference occurs in two major steps. First, pairwise non-linear affinities between neuronal traces from brain-wide calcium activity are organized by non-negative tensor factorization (NTF). Each factor specifies which groups of neurons are most likely interacting for an inferred interval in time, and for which animals. Finally, a generative model that allows for weighted community detection is applied to the functional motifs produced by NTF to reveal a dynamic functional connectome. Since time codes the different experimental variables (e.g., application of chemical stimuli), this provides an atlas of neural motifs active during separate stages of an experiment (e.g., stimulus application or spontaneous behaviors). Results from our analysis are experimentally validated, confirming that our method is able to robustly predict causal interactions between neurons to generate behavior.

Invoking the manifold assumption in machine learning requires knowledge of the manifold's geometry and dimension, and theory dictates how many samples are required. However, in most applications, the data are limited, sampling may not be uniform, and the manifold's properties are unknown; this implies that neighborhoods must adapt to the local structure. We introduce an algorithm for inferring adaptive neighborhoods for data given by a similarity kernel. Starting with a locally conservative neighborhood (Gabriel) graph, we sparsify it iteratively according to a weighted counterpart. In each step, a linear program yields minimal neighborhoods globally, and a volumetric statistic reveals neighbor outliers likely to violate manifold geometry. We apply our adaptive neighborhoods to nonlinear dimensionality reduction, geodesic computation, and dimension estimation. A comparison against standard algorithms using, for example, k-nearest neighbors, demonstrates the usefulness of our approach.

We exploit a key result from visual psychophysics---that individuals perceive shape qualitatively---to develop the use of a geometrical/topological “invariant” (the Morse--Smale complex) relating image structure with surface structure. Differences across individuals are minimal near certain configurations such as ridges and boundaries, and it is these configurations that are often represented in line drawings. In particular, we introduce a method for inferring a qualitative three-dimensional shape from shading patterns that link the shape-from-shading inference with shape-from-contour inference. For a given shape, certain shading patches approach “line drawings” in a well-defined limit. Under this limit, and invariably with respect to rendering choices, these shading patterns provide a qualitative description of the surface. We further show that, under this model, the contours partition the surface into meaningful parts using the Morse--Smale complex. These critical contours are the (perceptually) stable parts of this complex and are invariant over a wide class of rendering models. Intuitively, our main result shows that critical contours partition smooth surfaces into bumps and valleys, in effect providing a scaffold on the image from which a full surface can be interpolated.

Many organisms navigate gradients by alternating straight motions (runs) with random reorientations (tumbles), transiently suppressing tumbles whenever attractant signal increases. This induces a functional coupling between movement and sensation, since tumbling probability is controlled by the internal state of the organism which, in turn, depends on previous signal levels. Although a negative feedback tends to maintain this internal state close to adapted levels, positive feedback can arise when motion up the gradient reduces tumbling probability, further boosting drift up the gradient. Importantly, such positive feedback can drive large fluctuations in the internal state, complicating analytical approaches. Previous studies focused on what happens when the negative feedback dominates the dynamics. By contrast, we show here that there is a large portion of physiologically-relevant parameter space where the positive feedback can dominate, even when gradients are relatively shallow. We demonstrate how large transients emerge because of non-normal dynamics (non-orthogonal eigenvectors near a stable fixed point) inherent in the positive feedback, and further identify a fundamental nonlinearity that strongly amplifies their effect. Most importantly, this amplification is asymmetric, elongating runs in favorable directions and abbreviating others. The result is a "ratchet-like" gradient climbing behavior with drift speeds that can approach half the maximum run speed of the organism. Our results thus show that the classical drawback of run-and-tumble navigation-wasteful runs in the wrong direction-can be mitigated by exploiting the non-normal dynamics implicit in the run-and-tumble strategy.

Fixation identification algorithms facilitate data comprehension and provide analytical convenience in eye-tracking analysis. However, current fixation algorithms for eye-tracking analysis are heavily dependent on parameter choices, leading to instabilities in results and incompleteness in reporting. This work examines the nature of human scanning patterns during complex scene viewing. We show that standard implementations of the commonly used distance-dispersion algorithm for fixation identification are functionally equivalent to greedy spatiotemporal tiling. We show that modeling the number of fixations as a function of tiling size leads to a measure of fractal dimensionality through box counting. We apply this technique to examine scale-free gaze behaviors in toddlers and adults looking at images of faces and blocks, as well as large number of adults looking at movies or static images. The distributional aspects of the number of fixations may suggest a fractal structure to gaze patterns in free scanning and imply that the incompleteness of standard algorithms may be due to the scale-free behaviors of the underlying scanning distributions. We discuss the nature of this hypothesis, its limitations, and offer directions for future work.

Vision problems are inherently ambiguous: Do abrupt brightness changes correspond to object boundaries? Are smooth intensity changes due to shading or material properties? For stereo: Which point in the left image corresponds to which point in the right one? What is the role of color in visual information processing? To answer these (seemingly different) questions we develop an analogy between the role of orientation in organizing visual cortex and tangents in differential geometry. Machine learning experiments suggest using geometry as a surrogate for high-order statistical interactions. The cortical columnar architecture becomes a bundle structure in geometry. Connection forms within these bundles suggest answers to the above questions, and curvatures emerge in key roles. More generally, our path through these questions suggests an overall strategy for solving the inverse problems of vision: decompose the global problems into networks of smaller ones and then seek constraints from these coupled problems to reduce ambiguity. Neural computations thus amount to satisfying constraints rather than seeking uniform approximations. Even when no global formulation exists one may be able to find localized structures on which ambiguity is minimal; these can then anchor an overall approximation.

Shape-from-shading (SFS) is a classical inverse problem in computer and human vision. This shape reconstruction problem is inherently ill-posed. We show that the isophotes on smooth surfaces with Lambertian reflectance can be directly related to surface properties without consideration of the light source. Using techniques from modern differential geometry, we derive relationships between the curvature of the isophotes and the shape operator for the surface. Neurobiology motivates the geometric approach, and our calculations allow us to characterize the matching local family of surfaces that can result from any given shading patch. We illustrate the local ambiguity in several examples.

Big data for security informatics requires an analysis of both actors and measurement instruments. By analogy with social and political network analyses, primary questions involve who is doing what and in concert with whom. We seek to examine these questions using cluster analysis, non-linear dimensionality reduction, and machine learning techniques. We apply them to available political science and international relations databases, as these are natural proxies for security informatics databases. In particular we develop an embedding/clustering algorithm that reveals those political themes driving UN voting patterns as well as IGO (Inter-Governmental Organization) memberships. Our algorithm could readily be applied to international conflict, urban crime, and military engagement databases.

Association field models have been used to explain human contour grouping performance and to explain the mean frequency of long-range horizontal connections across cortical columns in V1. However, association fields essentially depend on pairwise statistics of edges in natural scenes. We develop a spectral test of the sufficiency of pairwise statistics and show that there is significant higher-order structure. An analysis using a probabilistic spectral embedding reveals curvature-dependent components to the association field, and reveals a challenge for biological learning algorithms.

Sociopolitical databases provide a rich source of high-dimensional data with hidden spatial-temporal structure; for example countries voting for/against certain UN resolutions is a manifestation of the underlying political alignment among nations. We introduce the notion of diffusion distance as a natural measure in such datasets. and applied diffusion maps to databases of intergovernmental organizations' memberships and UN roll calls. Examination of the embeddings from these data across time reveals interesting historical narratives, suggesting the results serve as a proxy for analysis of security and terrorism datasets.

Many databases provide tabular data relating objects to entities; for example, which countries belong to certain organizations. We seek to infer implicit organizational variables over such objects (countries) as a function of these properties (organizational memberships), and vice versa. If kernels existed over objects, then machine learning and non-linear dimensionality reduction techniques could be used. But this requires a similarity or distance defined over objects, which does not exist a priori. We are exploring an approach to kernel identification based on bi-clustering in which an average over randomized biclusters approximates a kernel. We claim that such kernels provide a viable alternative to other, more common kernel approaches. Experiments with a database of memberships in conventional intergovernmental organizations supports this claim.

Many traditional two-view stereo algorithms explicitly or implicitly use the frontal parallel plane assumption when exploiting contextual information since, e.g., the smoothness prior biases toward constant disparity (depth) over a neighborhood. This introduces systematic errors to the matching process for slanted or curved surfaces. These errors are nonnegligible for detailed geometric modeling of natural objects such as a human face. We show how to use contextual information geometrically to avoid such errors. A differential geometric study of smooth surfaces allows contextual information to be encoded in Cartan's moving frame model over local quadratic approximations, providing a framework of geometric consistency for both depth and surface normals; the accuracy of our reconstructions argues for the sufficiency of the approximation. In effect, Cartan's model provides the additional constraint necessary to move beyond the frontal parallel plane assumption in stereo reconstruction. It also suggests how geometry can extend surfaces to account for unmatched points due to partial occlusion.

No abstract available.

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.

Belief propagation has been shown to be a powerful inference mechanism for stereo correspondence. However the classical formulation of belief propagation implicitly imposes the frontal parallel plane assumption in the compatibility matrix for exploiting contextual information, since the priors perfer no depth (disparity) change in surrounding neighborhoods. This results in systematic errors for slanted or curved surfaces. To eliminate these errors we propose to use contextual information geometrically, and show how to encode surface differential geometric properties in the compatibility matrix for stereo correspondence. This enforces consistency for both depth and surface normal, extending the traditional formulation beyond consistency for (constant) depth. With such geometric contextual information, the belief propagation algorithm shows dramatic improvement on generic non-frontal parallel scenes. Several such examples are provided.

Good continuation is a fundamental principle of perceptual organization that guides the grouping of parts based on how they should succeed one another within coherent wholes. Despite the general language that was used by the Gestalt psychologists in phrasing this principle, computational work has focused almost exclusively on the study of curve-like structures. Here we offer for the first time, a rigorous generalization of good continuation to arbitrary visual structures that can be abstracted as scalar functions over the image plane. The differential geometry of these structures dictates that their good continuation should be based both on their value and on the geometry of their level sets, which yield a coupled system of equations solvable for a formal model. We exhibit the resulting computation on shading and intensity functions, demonstrating how it eliminates spurious measurements while preserving both regular structure and singularities. Related implementations could be applied to color channels, motion magnitude, and disparity signals

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.

Neurons in primary visual cortex respond selectively to oriented stimuli such as edges and lines. The long-range horizontal connections between them are thought to facilitate contour integration. While many physiological and psychophysical findings suggest that collinear or association field models of good continuation dictate particular projection patterns of horizontal connections to guide this integration process, significant evidence of interactions inconsistent with these hypotheses is accumulating. We first show that natural random variations around the collinear and association field models cannot account for these inconsistencies, a fact that motivates the search for more principled explanations. We then develop a model of long-range projection fields that formalizes good continuation based on differential geometry. The analysis implicates curvature(s) in a fundamental way, and the resulting model explains both consistent data and apparent outliers. It quantitatively predicts the (typically ignored) spread in projection distribution, its nonmonotonic variance, and the differences found among individual neurons. Surprisingly, and for the first time, this model also indicates that texture (and shading) continuation can serve as alternative and complementary functional explanations to contour integration. Because current anatomical data support both (curve and texture) integration models equally and because both are important computationally, new testable predictions are derived to allow their differentiation and identification.

The denoising of color images is an increasingly studied problem whose state-of-the-art solutions employ a variety of diffusion schemes. Specifying the correct diffusion is difficult, however, in part because of the subtleties of color interactions. We address this difficulty by proposing a perceptual organization approach to color denoising based on the principle of good continuation. We exploit the periodic chromatic (hue) component of the color in its representation as a frame field. We derive two hue curvatures and use them to construct a local model for the behavior of the color, which in turn specifies consistency constraints between nearby color measurements. These constraints are then used to replace noisy pixels by examining their spatial context. Such a contextual analysis (combined with standard methods to handle the scalar channels, saturation and lightness), results in a robust noise removal process that preserves discontinuities, singularities, and fine chromatic structures, including those that diffusion processes are prone to distort. We demonstrate our approach on a variety of synthetic and natural images.

While complaints about typical edge operators are common, proposals articulating a notion of the "perfect" edge map are comparatively rare, hindering the improvement of contour enhancement techniques. To address this situation, we suggest that one objective of visual contour computation is the estimation of a clean sketch from a corrupted rendition, the latter modeling noisy and low contrast edge or line operator responses to an image. Our formal model of this clean sketch is the curve indicator random field (CIRF), whose role is to provide a basis for defining edge likelihood models by eliminating the parameter along each curve to create an image of curves. For curves modeled with stationary Markov processes, this ideal edge prior is non-Gaussian and its moment generating functional has a form closely related to the Feynman-Kac formula. This sketch model leads to a nonlinear, minimum mean squared error contour enhancement filter that requires the solution of two elliptic partial differential equations. The framework is also independent of the order of the contour model, allowing us to introduce a Markov process model for contour curvature. We analyze the distribution of such curves and show that its mode is the Euler spiral, a curve minimizing changes in curvature. Example computations using the contour enhancement filter with the curvature-based contour model are provided, highlighting how the filter is curvature-selective even when curvature is absent in the input.

Locally parallel dense patterns-sometimes called texture flows-define a perceptually coherent structure of particular significance to perceptual organization. We argue that with applications ranging from image segmentation and edge classification to shading analysis and shape interpretation, texture flows deserve attention equal to edge segment grouping and curve completion. This paper develops the notion of texture flow from a geometrical point of view to argue that local measurements of such structures must incorporate two curvatures. We show how basic theoretical considerations lead to a unique model for the local behavior of the flow and to a notion of texture flow "good continuation." This, in turn, translates to a specification of consistency constraints between nearby flow measurements which we use for the computation of globally (piecewise) coherent structure through the contextual framework of relaxation labeling. We demonstrate the results on synthetic and natural images.

Locally parallel dense patterns - sometimes called texture flows define a perceptually coherent structure which is important to image segmentation, edge classification, shading analysis, and shape interpretation. This paper develops the notion of texture flow from a geometrical point of view to argue that local measurements of such structures must incorporate two curvatures. We show how basic theoretical considerations lead to a unique model for the local behavior of the flow and allow for the specification of consistency constraints between nearby measurements. The computation of globally coherent structure via neighborhood relationships is demonstrated on synthetic and natural images, and is compared to orientation diffusion.

A natural sequel to edge detection is the interpretation of edges. This interpretation can provide useful information to various computer vision processes, including recognition, reconstruction, and tracking. In this paper we consider the problem of identifying occlusion edges in a single image. We examine the appearance of occlusion edges under variable illumination, both analytically and empirically, and find that the pattern of shading in the neighborhood of occlusion edges is a stable feature. Finally, we derive a filter for detecting occlusion and present the results of its application.

We consider the interactions between edges and intensity distributions in semi-open image neighborhoods surrounding them. Locally this amounts to a kind of figure-ground problem, and we analyze the case of smooth surface occluding one another. Techniques from differential topology permits a classification of edges based on what we call folds and cuts. Intuititively, folds arise when a surface "folds" out of sight, which in turn may "cut" another surface from view. The classification depends on tangency between an edge tangent map and a shading flow field. Examples are included.

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.

We describe a class of computations that is motivated by a model of line and edge detection in primary visual cortex, although the computations here are expressed in general, abstract terms. The model consists of a collection of processing units (artificial neurons) that are organized into cliques of tightly inter-connected units. Our analysis is based on a dynamic analog model of computation, a model that is classically used to motivate gradient descent algorithms that seek extrema of energy functionals. We introduce a new view of these equations, however, and explicitly use discrete techniques from game theory to show that such cliques can achieve equilibrium in a computationally efficient manner. Furthermore, we are able to prove that the equilibrium is the same as that which would have been found by a gradient descent algorithm. The result is a new class of computations that, while related to traditional gradient-following computations such as relaxation labeling and Hopfield artificial neural networks, enjoys a different and provably efficient dynamics. The implications of the model extend beyond efficient artificial neural networks to (i) timing considerations in biological neural networks; (ii) to building reliable networks from less-reliable elements; (iii) to building accurate representations from less-accurate components; and, most generally, to (iv) demonstrating an interplay between continuous “dynamical systems” and discrete “pivoting” algorithms.

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.

It is commonly held that skeleton variation due to noise is unmanageable. It is also believed that smoothing, invoked to combat noise, creates no new structures, as in the causality principle for smoothing images. We demonstrate that both views are incorrect. We characterize how smooth points of the skeleton evolve under a general boundary evolution, with the corollary that, when the boundary is smoothed by a geometric heat equation, the skeleton evolves according to a related geometric heat equation. The surprise is that, while certain aspects of the skeleton simplify, as one would expect, others can behave wildly, including the creation of new skeleton branches. Fortunately such sections can be flagged as ligature, or those portions of the skeleton related to shape concavities. Our analysis also includes junctions and an explicit model for boundary noise. Provided a smoothness condition is met, the skeleton can often reduce noise. However when the smoothness condition is violated, the skeleton can change violently, which, we speculate, corresponds to situations in which "parts" are created, e.g., when the handle appears on a rotating cup.

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.

We present a model of visual computation based on tightly inter-connected cliques of pyramidal cells. It leads to a formal theory of cell assemblies, a specific relationship between correlated firing patterns and abstract functionality, and a direct calculation relating estimates of cortical cell counts to orientation hyperacuity. Our network architecture is unique in that (1) it supports a mode of computation that is both reliable and efficient; (2) the current-spike relations are modeled as an analog dynamical system in which the requisite computations can take place on the time scale required for an early stage of visual processing; and (3) the dynamics are triggered by the spatiotemporal response of cortical cells. This final point could explain why moving stimuli improve vernier sensitivity.

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.

We show that knowledge of sensor properties and operator norms can be exploited to define a unique, locally computable minimum reliable scale for local estimation at each point in the image. This method for local scale control is applied to the problem of detecting and localizing edges in images with shallow depth of field and shadows. We show that edges spanning a broad range of blur scales and contrasts can be recovered accurately by a single system with no input parameters other than the second moment of the sensor noise. A natural dividend of this approach is a measure of the thickness of contours which can be used to estimate focal and penumbral blur. Local scale control is shown to be important for the estimation of blur in complex images, where the potential for interference between nearby edges of very different blur scale requires that estimates be made at the minimum reliable scale.

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.

Traditional light source modelling is concerned with specific types of light sources, the two most common of which are point sources and daylight. Little attempt has been made, however, to relate different types of sources to each other. For example, how may the lighting from an overcast sky be compared to that from a lamp? Having a theoretical framework to compare different types of light sources is important for computer vision, in particular for understanding shading and shadow cues. A vision system needs to take account of the light source in order to interpret these cues. In this paper, we present a framework for comparing types of light sources which is based on a dimensional analysis of the set of light rays in a free space. Specifically, we introduce a 4-D light source hypercube in which the different types of sources may be embedded and compared. We also present a novel definition for light sources which generalizes the standard definition of a source as an emitter.

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.

We attempt to cast light on illumination by introducing a computational model of light sources and illumination. Spatially varying illumination is computed using coordinate transformations on the manifold of rays in space, and the ray manifold is shown to be 4 dimensional. The illumination model can be used to recover shape from shading in situations when direct illumination varies across space and provides the basis for relating different types of light sources (e.g., an overcast sky, the sun, a panel light, and a spotlight). A formal definition for light sources emerges that generalizes the standard definition of a source as an emitter and leads to a 4-D light source hypercube in which the different types of sources may be embedded.

Many presume that parsing the shadows out of an image is a high-level task, because of the global nature of the shadow formation process. But shape-from-shading algorithms are low-level, in the sense that they seek solutions (surface normals or depth values) directly from image intensities. A dilemma arises: since shape-from-shading involves an illumination term, shadows must first be identified. We show that a structure intermediate between intensities and surfaces-the shading flow field-provides a solution to this dilemma. Our analysis is based on the observation that the geometric information that can be derived from images supports different inferences than the photometric information, and our specific goal will be to articulate this geometric structure and to show how shading flow fields can be reliably computed.

We have recently proposed a scale-adaptive algorithm for reliable edge detection and blur estimation. The algorithm produces a contour code which consists of estimates of position, brightness, contrast and blur for each edge point in the image. Here we address two questions: 1. Can scale adaptation be used to achieve precise localization of blurred edges? 2. How much of the perceptual content of an image is carried by the 1-D contour code? We report an efficient algorithm for subpixel localization, and show that local scale control allows excellent precision even for highly blurred edges. We further show how local scale control can quantitatively account for human visual acuity of blurred edge stimuli. To address the question of perceptual content, we report an algorithm for inverting the contour code to reconstruct an estimate of the original image. While reconstruction based on edge brightness and contrast alone introduces significant artifact, restitution of the local blur signal is shown to produce perceptually accurate reconstructions.

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.

In differential geometry curves are characterized as mappings from an interval to the plane. In topology curves are characterized as a Hausdorff space with certain countability properties. Neither of these definitions captures the role that curves play in vision, however, in which curves can denote simple objects (such as a straight line), or complicated objects (such as a jumble of string). The difference between these situations is in part a measure of their complexity, and in part a measure of their dimensionality. Note that the map defining such curves is unknown, as is the proper way to represent them. We propose a formal complexity theory of curves appropriate for computational vision in general, and for problems like separating straight lines from jumbles in particular. The theory is applied to the problem of perceptual grouping.>

Addresses the problem of estimating 3D space occupancy using video imagery in the context of mobile robotics. A stationary robot observes a cluttered scene from a single viewpoint, and a second robot illuminates the scene from a sequence of directions thus producing a sequence of grey-level images. Differences of successive images are used to compute a sequence of shadowimages. The problem is to compute free space and occupied space from these shadowimages. Solutions to this problem are known for the special case of terrain scenes. The authors generalize these solutions to non-terrain scenes by making two key observations. First, there is a subset constraint on the shadowimages of a non-terrain scene, which allows the visible surfaces of a non-terrain scene to be recovered by a terrain-based technique. Second, the remaining regions of the shadowimages provide a conservative estimate of the occupied space hidden by these visible surfaces.

We propose a language for designing image measurement operators suitable for early vision. We refer to them as logical/linear (L/L) operators, since they unify aspects of linear operator theory and Boolean logic. A family of these operators appropriate for measuring the low-order differential structure of image curves is developed. These L/L operators are derived by decomposing a linear model into logical components to ensure that certain structural preconditions for the existence of an image curve are upheld. Tangential conditions guarantee continuity, while normal conditions select and categorize contrast profiles. The resulting operators allow for coarse measurement of curvilinear differential structure (orientation and curvature) while successfully segregating edge-and line-like features. By thus reducing the incidence of false-positive responses, these operators are a substantial improvement over (thresholded) linear operators which attempt to resolve the same class of features.>

Proposes a theory of the complexity of curves that is sufficient to separate those which extend along their length (e,g., in one dimension) from those that cover an area (e.g., 2-D). The theory is based on original results in geometric measure theory, and is applied to the problems of (i) perceptual grouping and (ii) physiological interpretation, of axonal arbors in developing neurons.

A dominating sky principle is introduced. It states that under diffuse lighting conditions, ambient light has a bimodal structure: the sky is typically much brighter than the ground. The dominating sky principle suggests a general model of image formation under diffuse lighting conditions. The idea behind this model is that the luminous intensity of a surface is determined by the visible region of the diffuse source, or surface visibility function. The model is presented. A novel concept in shading analysis, surface aperture, is discussed. Surface aperture is the solid angle of the visible diffuse source. Although the unit surface normal is a factor under diffuse lighting conditions, in most situations surface aperture dominates. The surface visibility and aperture functions are embedded into visibility and aperture fields defined in the free space above the surfaces. The visibility field is useful because it satisfies simple local constraints. A fast, parallel computation is described for the forward problem of rendering a surface which is illuminated by a diffuse source and for the inverse problem, namely, shape from shading on a cloudy day. The forward and inverse solutions are quite similar. Experimental results are presented.>

It is shown how to actively compute qualitative shape properties of a surface directly from image intensities without first quantitatively reconstructing the surface. The approach diverges from classical active shape-from-shading in that two different types of lighting conditions (a diffuse source and a point source) are used, rather than two instances of a single type (a point source). There is no attempt to compute a dense depth map of the surface. Rather, the presence of certain qualitative geometric features is detected. In particular, a shape property, surface aperture, is introduced, and it is shown that under diffuse lighting there is typically a spatial correspondence between the minima of surface aperture and the minima of image intensity. Thus, the minima in surface aperture can be located. Different possible causes of the aperture minima can subsequently be distinguished by actively illuminating the surface with a point source positioned in the viewing direction.>

What is the complexity of computing equilibria for physically implementable analog networks (Hopfield 1984; Sejnowski 1981) with arbitrary connectivity? We show that if the amplifiers are piecewise-linear, then such networks are instances of a game-theoretic model known as polymatrix games. In contrast with the usual gradient descent methods for symmetric networks, equilibria for polymatrix games may be computed by vertex pivoting algorithms similar to the simplex method for linear programming. Like the simplex method, these algorithms have characteristic low order polynomial behavior in virtually all practical cases, though not certain theoretical ones. While these algorithms cannot be applied to models requiring evolution from an initial point, they are applicable to “clamping” models whose input is expressed purely as a bias. Thus we have an a priori indication that such models are computationally tractable.

Generic singularities can provide position-independent information about the qualitative shape of surfaces. The authors determine the singularities of the principal direction fields of a surface (its umbilic points) from a computation of the index of the fields. The authors present examples both for 3-D synthetic images to which noise has been added and for clinical magnetic resonance images.>

We deomonstrate the potential for fruitful interaction between those studying artificial vision systems and those studying biological vision systems with the task of inferring global curves with corners and bifurcations from images. The talk outlines one slice through a large project on the computational neurobiology of vision. The Dilemma of Curve Detection from previous ones in that no attempt is made to match curves directly against the image, or even against measurements (i.e., "curve operators") evaluated over the image. Instead we stress the organizational point that a stable, reliable, but coarse description should be computed as an intermediate between the image (measurements) and the global curves. A particular intermediate representation—the discrete tangent field—is proposed.

Consider two wire gratings, superimposed and moving across each other. Under certain conditions the two gratings will cohere into a single, compound pattern, which will appear to be moving in another direction. Such coherent motion patterns have been studied for sinusoidal component gratings, and give rise to percepts of rigid, planar motions. In this paper we show how to construct coherent motion displays that give rise to nonuniform, nonrigid, and nonplanar percepts. Most significantly, they also can define percepts with corners. Since these patterns are more consistent with the structure of natural scenes than rigid sinusoidal gratings, they stand as interesting stimuli for both computational and physiological studies. To illustrate, our display with sharp corners (tangent discontinuities or singularities) separating regions of coherent motion suggests that smoothing does not cross tangent discontinuities, a point that argues against existing (regularization) algorithms for computing motion. This leads us to consider how singularities can be confronted directly within optical flow computations, and we conclude with two hypotheses: (1) that singularities are represented within the motion system as multiple directions at the same retinotopic location; and (2) for component gratings to cohere, they must be at the same depth from the viewer. Both hypotheses have implications for the neural computation of coherent motion.

Early image understanding seeks to derive analytic representations from image intensities. The authors present steps towards this goal by considering the inference of surfaces from three-dimensional images. Only smooth surfaces are considered and the focus is on the coupled problems of inferring the trace points (the points through which the surface passes) and estimating the associated differential structure given by the principal curvature and direction fields over the estimated smooth surfaces. Computation of these fields is based on determining an atlas of local charts or parameterizations at estimated surface points. Algorithm robustness and the stability of results are essential for analyzing real images; to this end, the authors present a functional minimization algorithm utilizing overlapping local charts to refine surface points and curvature estimates, and develop an implementation as an iterative constraint satisfaction procedure based on local surface smoothness properties. Examples of the recovery of local structure are presented for synthetic images degraded by noise and for clinical magnetic resonance images.>

The problem of obtaining reliable estimates of the optic flow field and its variation is discussed. It is argued that circuitry in the middle temporal (MT) visual area is arranged to provide mean field approximations of the optical flow field, that is, the maximal neighborhood over which the local field can be well-approximated as uniform, parallel translation. In addition, the way the mean field approximation varies with neighborhood size and position is informative about the variation of the flow field. It is shown how receptive fields can be synthesized to represent the first-order differential information about the flow field. The same ideas are applicable to the binocular disparity vector field, and lead one to predict the existence of extrastriate neurons that are specialized for the local shear and stretch of the disparity and motion vector fields.>

The problem of detecting curves in visual images arises in both computer vision and biological visual systems. Our approach integrates constraints from these two sources and suggests that there are two different stages to curve detection, the first resulting in a local description, and the second in a global one. Each stage involves a different style of computation: in the first stage, hypotheses are represented explicitly and coarsely in a fixed, preconfigured architecture; in the second stage, hypotheses are represented implicitly and more finely in a dynamically constructed architecture. We also show how these stages could be related to physiology, specifying the earlier parts in a relatively fine-grained fashion and the later ones more coarsely.

An approach is described for curve inference that is based on curvature information. The inference procedure is divided into two stages: a trace inference stage, which is the subject of the present work, and a curve synthesis stage. It is shown that recovery of the trace of a curve requires estimating local models for the curve at the same time, and that tangent and curvature information are sufficient. These make it possible to specify powerful constraints between estimated tangents to a curve, in terms of a neighborhood relationship called cocircularity, and between curvature estimates, in terms of a curvature consistency relation. Because all curve information is quantized, special care must be taken to obtain accurate estimates of trace points, tangents, and curvatures. This issue is addressed specifically to the introduction of a smoothness constraint and a maximum curvature constraint. The procedure is applied to two types of images: artificial images designed to evaluate curvature and noise sensitivity, and natural images.>

Relaxation labeling uses contextual information for finding consistent labelings of graphs. Although relaxation labeling is parallel and iterative, the complexity of updating with standard rules is too costly for practical implementation. A description is given of a computationally more efficient updating rule that utilizes radial projection instead of normal projection to avoid the complexities incurred by previous update rules when boundaries to the labeling space are encountered. This reduction in complexity is achieved by first restricting support vectors to the positive quadrant, and then using radial projection onto the constraint instead of normal projection. Crucial order information is conserved through smooth convergence towards the optimum and a rate of convergence proportional to the magnitudes of the support functions.>

Generic singularities can provide position-independent information about the qualitative shape of surfaces. The authors determine the singularities of the principal direction fields of a surface (its umbilic points) from a computation of the index of the fields. The authors present examples both for 3-D synthetic images to which noise has been added and for clinical magnetic resonance images. >

We propose a new paradigm for curve detection in which an autonomous and atomic description is computed between measurements on the image and global curves. The description takes the form of a discrete tangent field, i.e.. an estimated representation of quantized tangents and curvatures at each possible trace point. We then present a new algorithm for inferring global curves through this tangent field. by inferring a covering of the global curve. The elements of the covering are short splines, each of which moves according to a potential distribution computed from the tangent field. Both stages of the algorithm are parallel and both bear some analogy to biological mechanisms for curve detection

Essential information about the differential structure of smooth surfaces is embodied in their principal curvature and principal direction fields. A particular type of fibre bundle, a frame bundle, is defined over estimated surface trace points and the computation of these fields is presented as the determination of the appropriate cross section through the frame bundle. Any approach to the recovery of surface structure must deal with the inherent limitations of local computations-an iterative constraint-satisfaction process is developed for the reliable extraction of the principal-direction cross section. Present methods are applied to the synthetic images corrupted by noise and to magnetic resonance imagery.>

Global geometric algorithms for trajectory planning are used in conjunction with a local avoidance strategy. Simulations have been developed for a mobile robot in the plane among stationary and moving obstacles. Essentially, the robot has a geometric planner that provides a coarse trajectory (the path and the velocity along it), which may be modified by a (low-level) local avoidance module if sensors detect obstacles in the vicinity of the robot. This hierarchy makes effective use of the complementarity between global trajectory planning and local obstacle avoidance.>

Orientation selection is the inference of orientation information out of images. It is one of the foundations on which other visual structures are built, since it must precede the formation of contours out of pointillist data and surfaces out of surface markings. We take a differential geometric view in defining orientation selection and develop algorithms for actually doing it. The goal of these algorithms is formulated in mathematical terms as the inference of a vector field of tangents (to the contours), and the algorithms are studied in both abstract and computational forms. They are formulated as matching problems, and algorithms for solving them are reduced to biologically plausible terms. We show that two different matching problems are necessary, the first for 1-dimensional contours (which we refer to as Type I processes) and the second for 2-dimensional flows (or Type II processes).

The detailed structure of intensities in the local neighborhood of an edge can often indicate the nature of the physical event givinig rise to that edge. We argue that the limit, as we approach arbitrarily close to either side of an edge, of such image parameters as type of texture, texture gradient, color, appropriate directional derivatives of intensity, etc., is a key aspect of this structure. However, the general problem of capturing this local structure is surprisingly complex. Thus, we restrict ourselves in this paper to a relatively simple domain¿one-dimensional cuts through idealized images modeled by piecewise smooth (C1) functions corrupted by Gaussian noise. Within this domain, we define local structure to be the limit of the uncorrupted intensity and of its derivatives as we approach arbitrarily close to either side of a discontinuity. We develop a technique that captures this local structure while simultaneously locating the discontinuities, and demonstrate that these tasks are in fact inseparable. The technique is an extension, using estimation theory, of the classical definition of discontinuity. It handles, in a consistent fashion, both jump discontinuities in the function and jump discontinuities in its first derivative (so-called step-edges are a special case of the former and roof-edges of the latter). It also integrates, again in a consistent fashion, information derived from a number of different neighborhood sizes.

A large class of problems can be formulated in terms of the assignment of labels to objects. Frequently, processes are needed which reduce ambiguity and noise, and select the best label among several possible choices. Relaxation labeling processes are just such a class of algorithms. They are based on the parallel use of local constraints between labels. This paper develops a theory to characterize the goal of relaxation labeling. The theory is founded on a definition of con-sistency in labelings, extending the notion of constraint satisfaction. In certain restricted circumstances, an explicit functional exists that can be maximized to guide the search for consistent labelings. This functional is used to derive a new relaxation labeling operator. When the restrictions are not satisfied, the theory relies on variational cal-culus. It is shown that the problem of finding consistent labelings is equivalent to solving a variational inequality. A procedure nearly identical to the relaxation operator derived under restricted circum-stances serves in the more general setting. Further, a local convergence result is established for this operator. The standard relaxation labeling formulas are shown to approximate our new operator, which leads us to conjecture that successful applications of the standard methods are explainable by the theory developed here. Observations about con-vergence and generalizations to higher order compatibility relations are described.

We consider a particular problem which arises when apply-ing the method of gradient projection for solving constrained optimiza-tion and finite dimensional variational inequalities on the convex set formed by the convex hull of the standard basis unit vectors. The method is especially important for relaxation labeling techniques applied to problems in artificial intelligence. Zoutendijk's method for finding feasible directions, which is relatively complicated in general situations, yields a very simple finite algorithm for this problem. We present an extremely simple algorithm for performing the gradient projection and an independent verification of its correctness.

This paper presents a model of motion suitable for cell tracking. It includes a representation for cell dynamics enabling it to maintain a correspondence between successive images of cells undergoing morphological changes. This model is based on a minimization problem whose computational solution is similar in form to a Newton-Rhapson iteration. The model is supported by experimental results from an actual tracking problem.

article Frame-to-frame coherence and the hidden surface computation: constraints for a convex world Share on Authors: H. Hubschman Computer Vision and Graphics Laboratory, Department of Electrical Engineering, McGill University, Montreal, Quebec, Canada Computer Vision and Graphics Laboratory, Department of Electrical Engineering, McGill University, Montreal, Quebec, CanadaView Profile , S. W. Zucker Computer Vision and Graphics Laboratory, Department of Electrical Engineering, McGill University, Montreal, Quebec, Canada Computer Vision and Graphics Laboratory, Department of Electrical Engineering, McGill University, Montreal, Quebec, CanadaView Profile Authors Info & Claims ACM Transactions on GraphicsVolume 1Issue 2April 1982 pp 129–162https://doi.org/10.1145/357299.357302Online:01 April 1982Publication History 28citation600DownloadsMetricsTotal Citations28Total Downloads600Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Frame-to-frame coherence is the highly structured relationship that exists between successive frames of certain animation sequences. From the point of view of the hidden surface computation, this implies that parts of the scene will become visible or invisible in a predictable fashion. In this paper the frame-to-frame coherence constraints are identified and characterized for static scenes restricted to stationary, closed, convex, nonintersecting polyhedra. The animation derives from a continuous movement of the viewer. The mathematical analysis of the constraints is geometric, and leads to a characterization of the self-occlusion relationship over a single polyhedron; and to a characterization of the occlusion or change of occlusion relationship over two polyhedra. Based on these constraints, an algorithm is presented which generates successive frames in an animation sequence.

Modern scanning techniques, such as computed tomography, have begun to produce true three-dimensional imagery of internal structures. The first stage in finding structure in these images, like that for standard two-dimensional images, is to evaluate a local edge operator over the image. If an edge segment in two dimensions is modeled as an oriented unit line segment that separates unit squares (i.e., pixels) of different intensities, then a three-dimensional edge segment is an oriented unit plane that separates unit volumes (i.e., voxels) of different intensities. In this correspondence we derive an operator that finds the best oriented plane at each point in the image. This operator, which is based directly on the 3-D problem, complements other approaches that are either interactive or heuristic extensions of 2-D techniques.

Relaxation labeling processes are a class of iterative algorithms for using contextual information to reduce local ambiguities. This paper introduces a new perspective toward relaxation-that of considering it as a process for reordering labels attached to nodes in a graph. This new perspective is used to establish the formal equivalence between relaxation and another widely used algorithm, local maxima selection. The equivalence specifies conditions under which a family of cooperative relaxation algorithms, which generalize the well-known ones, decompose into purely local ones. Since these conditions are also sufficient for guaranteeing the convergence of relaxation processes, they serve as stopping criteria. We feel that equivalences such as these are necessary for the proper application of relaxation and maxima selection in complex speech and vision understanding systems.

A relaxation process is described and is applied to the detection of smooth lines and curves in noisy, real world images. There are nine labels associated with each image point, eight labels indicating line segments at various orientations and one indicating the no-line case. Attached to each label is a probability. In the relaxation process, interaction takes place among the probabilities at neighboring points. This permits line segments in compatible orientations to strengthen one another, and incompatible segments to weaken one another. Similarly, no-line labels are reinforced by neighboring no-line labels and weakened by appropriately oriented line labels. This process converges, in only a few iterations, to a condition in which points lying on long curves have achieved high line probabilities, while other points have high no-line probabilities, There is some tendency, under this process, for curves to thicken; however, a thinning procedure can be incorporated to counteract this. The process is effective even for curves of low contrast, and even when many curves lie close to one another.

Two methods are introduced for reducing additive noise in approximately piecewise constant images. In the first method, the correct gray level of a point P is estimated by a weighted average of the gray levels of P's immediate neighbors. To assign these weights for a given P so that the local averaging operation does not blur the image, the presence of any edges or lines passing through P's neighborhood must be determined. For example, when an edge is present, only those points on P's side of the edge should be used. In general, the distribution of gray levels in P's neighborhood will suggest many possible line and edge configurations which can be used to compute the weight distribution for the averaging operation. The averaging is performed in parallel over the entire image and is iterated for additional smoothing. The second method is a relaxation labeling formulation which can be psed in cases of more severe noise. Each point is now assigned a vector of probabilities over its allowable gray level set. These probabilities are updated as weighted averages of the gray level probabilities at neighboring points. Once again the presence of lines and edges determines how the contribution from each neighboring point is weighted. Examples demonstrating both methods are given.

Given a set of objects in a scene whose identifications are ambiguous, it is often possible to use relationships among the objects to reduce or eliminate the ambiguity. A striking example of this approach was given by Waltz [13]. This paper formulates the ambiguity-reduction process in terms of iterated parallel operations (i.e., relaxation operations) performed on an array of (object, identification) data. Several different models of the process are developed, convergence properties of these models are established, and simple examples are given.

This correspondence describes a method of dividing a picture into differently textured regions by thresholding the values of a suitable local picture property. The approach used is a generalization to natural textures of a technique recently proposed by Tsuji. The examples given involve textures that differ in coarseness; a method of estimating texture coarseness by analysis of local property values is also described.