Because the magnitude of inner products with its basis functions are invariant to rotation and scale change, the Fourier-Mellin transform has long been used as a component in Euclidean invariant 2D shape recognition systems. Yet Fourier-Mellin transform magnitudes are only invariant to rotation and scale changes about a known center point, and full Euclidean invariant shape recognition is not possible except when this center point can be consistently and accurately identified. In this paper, we describe a system where a Fourier-Mellin transform is computed at every point in the image. The spatial support of the Fourier-Mellin basis functions is made local by multiplying them with a polynomial envelope. Significantly, the magnitudes of convolutions with these complex filters at isolated points are not (by themselves) used as features for Euclidean invariant shape recognition because reliable discrimination would require filters with spatial support large enough to fully encompass the shapes. Instead, we rely on the fact that normalized histograms of magnitudes are fully Euclidean invariant. We demonstrate a system based on the VLAD machine learning method that performs Euclidean invariant recognition of 2D shapes and requires an order of magnitude less training data than comparable methods based on convolutional neural networks.

Object-oriented combinator chemistry (OOCC) is an artificial chemistry with composition devices borrowed from object-oriented and functional programming languages. Actors in OOCC are embedded in space and subject to diffusion; since they are neither created nor destroyed, their mass is conserved. Actors use programs constructed from combinators to asynchronously update their own states and the states of other actors in their neighborhoods. The fact that programs and combinators are themselves reified as actors makes it possible to build programs that build programs from combinators of a few primitive types using asynchronous spatial processes that resemble chemistry as much as computation. To demonstrate this, OOCC is used to define a parallel, asynchronous, spatially distributed self-replicating system modeled in part on the living cell. Since interactions among its parts result in the construction of more of these same parts, the system is strongly constructive. The system's high normalized complexity is contrasted with that of a simple composome.

For open-ended computational growth, we argue that: (i) instead of hardwiring and hiding component spatial relationships, computer architecture should soften and expose them; and (2) instead of relegating reliability to hardware, robustness must climb the computational stack toward the end users. We suggest that eventually all truly large-scale computers will be robust spatial computers—even if intended neither for spatial tasks nor harsh environments. This paper is an extended introduction for the spatial computing community to the Movable Feast Machine (MFM), a computing model in the spirit of an object-oriented asynchronous cellular automata. We motivate the approach and then present the model, touching on robustness mechanisms such as redundancy, compartmentalization and homeostasis. We provide simulation data from prototype movable elements such as self-healing wire for data transport and movable ‘membrane’ rings for spatial segregation, and illustrate how some larger computations like sorting or evaluating a lambda expression can be reconceived for robustness and movability within a spatial computing architecture.

The state-of-the-art in computer drawing programs is based on a number of concepts that are over two decades old. One such concept is the use of layers for ordering the surfaces in a drawing from top to bottom. Unfortunately, the use of layers unnecessarily imposes a partial ordering on the depths of the surfaces and prevents the user from creating a large class of potential drawings, e.g., of Celtic knots and interwoven surfaces. In this paper we describe a novel approach which only requires local depth ordering of segments of the boundaries of surfaces in a drawing rather than a global depth relation between entire surfaces. Our program provides an intuitive user interface which allows a novice to create complex drawings of interwoven surfaces that would be difficult and time-consuming to create with standard drawing programs.

Using a saliency measure based on the global property of contour closure, we have developed a segmentation method which identifies smooth closed contours bounding objects of unknown shape in real images. The saliency measure incorporates the Gestalt principles of proximity and good continuity that previous methods have also exploited. Unlike previous methods, we incorporate contour closure by finding the eigenvector with the largest positive real eigenvalue of a transition matrix for a Markov process where edges from the image serve as states. Element (i, j) of the transition matrix is the conditional probability that a contour which contains edge j will also contain edge i. We show how the saliency measure, defined for individual edges, can be used to derive a saliency relation, defined for pairs of edges, and further show that strongly-connected components of the graph representing the saliency relation correspond to smooth closed contours in the image. Finally, we report for the first time, results on large real images for which segmentation takes an average of about 10 seconds per object on a general-purpose workstation.

We describe a neural network which enhances and completes salient closed contours. Our work is different from all previous work in three important ways. First, like the input provided to V1 by LGN, the in- put to our computation is isotropic. That is, the input is composed of spots not edges. Second, our network computes a well defined function of the input based on a distribution of closed contours characterized by a random process. Third, even though our computation is implemented in a discrete network, its output is invariant to continuous rotations and translations of the input pattern.

A recent neural model of illusory contour formation is based on a distribution of natural shapes traced by particles moving with constant speed in directions given by Brownian motions. The input to that model consists of pairs of position and direction constraints, and the output consists of the distribution of contours joining all such pairs. In general, these contours will not be closed, and their distribution will not be scale-invariant. In this article, we show how to compute a scale-invariant distribution of closed contours given position constraints alone and use this result to explain a well-known illusory contour effect.

Using a saliency measure based on the global property of contour closure, we have developed a method that reliably segments out salient contours bounding unknown objects from real edge images. The measure also incorporates the Gestalt principles of proximity and smooth continuity that previous methods have exploited. Unlike previous measures, we incorporate contour closure by finding the eigen-solution associated with a stochastic process that models the distribution of contours passing through edges in the scene. The segmentation algorithm utilizes the saliency measure to identify multiple closed contours by finding strongly-connected components on an induced graph. The determination of strongly-connected components is a direct consequence of the property of closure. We report for the first time, results on large real images for which segmentation takes an average of about 10 secs per object on a general-purpose workstation. The segmentation is made efficient for such large images by exploiting the inherent symmetry in the task.

We describe an algorithm- and representation-level theory of illusory contour shape and salience. Unlike previous theories, our model is derived from a single assumption: that the prior probability distribution of boundary completion shape can be modeled by a random walk in a lattice whose points are positions and orientations in the image plane (i.e., the space that one can reasonably assume is represented by neurons of the mammalian visual cortex). Our model does not employ numerical relaxation or other explicit minimization, but instead relies on the fact that the probability that a particle following a random walk will pass through a given position and orientation on a path joining two boundary fragments can be computed directly as the product of two vector-field convolutions. We show that for the random walk we define, the maximum likelihood paths are curves of least energy, that is, on average, random walks follow paths commonly assumed to model the shape of illusory contours. A computer model is demonstrated on numerous illusory contour stimuli from the literature.

We describe a local parallel method for computing the stochastic completion field introduced in the previous article (Williams and Jacobs, 1997). The stochastic completion field represents the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. It is based on the assumption that the prior probability distribution of completion shape can be modeled as a random walk in a lattice of discrete positions and orientations. The local parallel method can be interpreted as a stable finite difference scheme for solving the underlying Fokker-Planck equation identified by Mumford (1994). The resulting algorithm is significantly faster than the previously employed method, which relied on convolution with large-kernel filters computed by Monte Carlo simulation. The complexity of the new method is O (n3m), while that of the previous algorithm was O(n4m2 (for an n × n image with m discrete orientations). Perhaps most significant, the use of a local method allows us to model the probability distribution of completion shape using stochastic processes that are neither homogeneous nor isotropic. For example, it is possible to modulate particle decay rate by a directional function of local image brightnesses (i.e., anisotropic decay). The effect is that illusory contours can be made to respect the local image brightness structure. Finally, we note that the new method is more plausible as a neural model since (1) unlike the previous method, it can be computed in a sparse, locally connected network, and (2) the network dynamics are consistent with psychophysical measurements of the time course of illusory contour formation.

We describe a local parallel method for computing the stochastic completion field introduced in an earlier paper Williams and Jacobs (1995). The stochastic completion field represents the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. It is based upon the assumption that the prior probability distribution of completion shape can be modeled as a random walk in a lattice of discrete positions and orientations. The local parallel method can be interpreted as a stable finite difference scheme for solving the underlying Fokker-Planck equation identified by Mumford (1994). The resulting algorithm is significantly faster than the previously employed method which relied on convolution with large-kernel filters computed by Monte Carlo simulation. The complexity of the new method is Of(n/sup 3/m) while that of the previous algorithm was 0(n/sup 4/m/sup 2/) (for an n x n image with m discrete orientations). Perhaps most significantly, the use of a local method allows us to model the probability distribution of completion shape using stochastic processes which are neither homogenous nor isotropic.

We describe an algorithm and representation level theory of illusory contour shape and salience. Unlike previous theories, our model is derived from a single assumption-namely, that the prior probability distribution of boundary completion shape can be modeled by a random walk in a lattice whose points are positions and orientations in the image plane (i.e. the space which one can reasonably assume is represented by neurons of the mammalian visual cortex). Our model does not employ numerical relaxation or other explicit minimization, but instead relies on the fact that the probability that a particle following a random walk will pass through a given position and orientation on a path joining two boundary fragments can be computed directly as the product of two vector-field convolutions. We show that for the random walk we define, the maximum likelihood paths are curves of least energy, that is, on average, random walks follow paths commonly assumed to model the shape of illusory contours. A computer model is demonstrated on numerous illusory contour stimuli from the literature.>

Researchers in computer vision have primarily studied the problem of visual reconstruction of environmental structure that is plainly visible. In this paper, the conventional goals of visual reconstruction are generalized to include both visible and occluded forward facing surfaces. This larger fraction of the environment is termed the anterior surfaces. In this paper, we show that the boundaries of the anterior surfaces can be represented in viewer-centered coordinates as a labeled knot diagram. Where boundaries are not occluded and where surface reflectance is distinct from that of the background, boundaries will be marked by image contours. However, where boundaries are occluded, or where surface reflectance matches background reflectance, there will be no detectable luminance change in the image. Deducing the complete image trace of the boundaries of the anterior surfaces under these circumstances is termed the figural completion problem. The second half of this paper describes a computational theory of figural completion. A working model is demonstrated on a variety of illusory contour displays. The experimental system employs a two stage process of completion hypothesis and combinatorial optimization. The labeling scheme is enforced by integer linear inequalities so that the optimal feasible solution of an integer linear program defines a typologically valid surface organization.>

The mechanics of occlusion of one surface by another are described by a set of integer linear constraints. These constraints insure that the output of a contour grouping process is physically valid and consistent with the image evidence. Among the many feasible solutions, the most compelling is the solution which best explains the presence and form of image structure. The problem of computing a complete and consistent surface boundary representation is reduced to solving an integer linear program.>

The collection of image sequences for quantitative experiments in motion analysis is discussed. To assess the effectiveness of a motion algorithm it is necessary to obtain motion data with ground truth of known accuracy. The authors describe motion data collected using the imaging facilities provided by the autonomous land vehicle (ALV). A total of eight sequences of about 30 frames each were collected at five different outdoor sites using move-and-shoot and stop-and-shoot methods. For all the sequences accurate ground truth of environmental objects were determined using theodolites and a laser range finder. The camera egomotion parameters (this included both translation and rotation) were determined using a land navigation system on the ALV. Example images of the data set collected and an analysis of one of the sequences are presented.>

MOTION IN THE ENVIRONMENT MANIFESTS ITSELF IN CHANGES OF MANY KINDS, NOT JUST IMAGE PLANE VELOCITIES, YET THESE ARE ALL THAT AN OPTICAL FLOW FIELD MAKES EXPLICIT. WE VIEW OPTICAL FLOW AS A USEFUL LOW-LEVEL REPRESENTATION FROM WHICH A SYMBOLIC DESCRIPTION OF CHANGE, IN THE FORM OF TOKEN MATCHES, CAN BE COMPUTED. THE TOKENS OF INTEREST TO US ARE THOSE PRODUCED BY PERCEPTUAL ORGANIZATION PROCESSES, AND ARE MORE ABSTRACT THAN EDGES OR INTEREST POINTS. WE DEMONSTRATE A WORKING SYSTEM FOR MATCHING LINE TOKENS WHICH USES THE OPTICAL FLOW FIELD IN A HEURISTIC MANNER TO LIMIT THE SEARCH FOR THE `MINIMAL BIPARTITE COVER'' OF THE SET OF TOKENS FROM EACH FRAME. AS AN EXAMPLE APPLICATION, WE DEMONSTRATE A TECHNIQUE FOR COMPUTING DISTANCE TO ENVIRONMENTAL SURFACES SUITABLE FOR OBSTACLE RECOGNITION BY A MOBILE ROBOT. ACCURATE KNOWLEDGE OF THE CAMERA MOTION PARAMETERS IS NOT REQUIRED. WE DESCRIBE HOW MOTION IN DEPTH MANIFESTS ITSELF IN THE PROJECTED LENGTHS AND AREAS OF ENVIRONMENTAL SURFACES WHOSE EXTENT IN DEPTH IS SMALL RELATIVE TO THEIR DISTANCE FROM THE CAMERA. RESULTS ON TWO SEQUENCES TAKEN BY A MOBILE ROBOT ARE PRESENTED TO DEMONSTRATE THE ACCURACY OF THE METHOD.