We present two algorithms for computing distances along convex and non-convex polyhedral surfaces. The first algorithm computes exact minimal-geodesic distances and the second algorithm combines these distances to compute exact shortest-path distances along the surface. Both algorithms have been extended to compute the exact minimal-geodesic paths and shortest paths. These algorithms have been implemented and validated on surfaces for which the correct solutions are known, in order to verify the accuracy and to measure the run-time performance, which is cubic or less for each algorithm. The exact-distance computations carried out by these algorithms are feasible for large-scale surfaces containing tens of thousands of vertices, and are a necessary component of near-isometric surface flattening methods that accurately transform curved manifolds into flat representations.

Spectral graph partitioning provides a powerful approach to image segmentation. We introduce an alternate idea that finds partitions with a small isoperimetric constant, requiring solution to a linear system rather than an eigenvector problem. This approach produces the high quality segmentations of spectral methods, but with improved speed and stability.

Shear has been known to exist for many years in the topographic structure of the primary visual cortex, but has received little attention in the modeling literature. Although the topographic map of V1 is largely conformal (i.e. zero shear), several groups have observed topographic shear in the region of the V1/V2 border. Furthermore, shear has also been revealed by anisotropy of cortical magnification factor within a single ocular dominance column. In the present paper, we make a functional hypothesis: the major axis of the topographic shear tensor provides cortical neurons with a preferred direction of orientation tuning. We demonstrate that isotropic neuronal summation of a sheared topographic map, in the presence of additional random shear, can provide the major features of cortical functional architecture with the ocular dominance column system acting as the principal source of the shear tensor. The major principal axis of the shear tensor determines the direction and its eigenvalues the relative strength of cortical orientation preference. This hypothesis is then shown to be qualitatively consistent with a variety of experimental results on cat and monkey orientation column properties obtained from optical recording and from other anatomical and physiological techniques. In addition, we show that a recent result of Das and Gilbert (Das, A., & Gilbert, C. D., 1997. Distortions of visuotopic map match orientation singularities in primary visual cortex. Nature, 387, 594-598) is consistent with an infinite set of parameterized solutions for the cortical map. We exploit this freedom to choose a particular instance of the Das-Gilbert solution set which is consistent with the full range of local spatial structure in V1. These results suggest that further relationships between ocular dominance columns, orientation columns, and local topography may be revealed by experimental testing.

Nonlinear anisotropic diffusion algorithms provide significant improvement in image enhancement as compared to linear filters. However, the excessive computational cost of solving nonlinear PDEs precludes their use in real-time vision applications. We show that two orders of magnitude speed improvement is provided by a new image filtering paradigm in which an adaptively determined vector field specifies nonlocal application points for an image filter.

Foveated, log-polar, or space-variant image architectures provide a high resolution and wide field workspace, while providing a small pixel computation load. These characteristics are ideal for mobile robotic and active vision applications, but have been little used due to the general lack of image processing tools that are applicable to the log-polar coordinate system. Recently, we have described a generalization of the Fourier transform (the fast exponential chirp transform), which allows frame-rate computation of full-field two-dimensional (2-D) frequency transforms directly in log-polar coordinates. In the present work, we show that is possible to achieve full-frame image de-blur at frame rate on a standard "PC" platform, using these methods, we illustrate this idea with a Wiener filter based restoration technique. The main contribution of this note is the implementation of (space-variant) image de-blur directly in log-polar coordinates, using the exponential chirp transform. The results show reasonable quality of de-blur, and suggest that these methods are relevant to applications in mobile image processing platforms in which real-time motion deblur is important, and for which it is not desirable to use extensive or custom fabricated hardware.

Template matching 1 via cross-correlation on Laplacian pyramid image architectures has been traditionally performed in a “coarse” to “fine” fashion. In the present paper, we show that by computing cross-correlation within each level of the pyramid independently, and considering the sum across (expanded) levels, a significant improvement in Peak to Correlation Energy (PCE) (Kumar and Hassebrook, 1992) is obtained. This result is illustrated with a number of numerical examples.

The leaky integrate-and-fire (LIF) model of neuronal spiking (Stein 1967) provides an analytically tractable formalism of neuronal firing rate in terms of a neuron's membrane time constant, threshold, and refractory period. LIF neurons have mainly been used to model physiologically realistic spike trains, but little application of the LIF model appears to have been made in explicitly computational contexts. In this article, we show that the transfer function of a LIF neuron provides, over a wide-parameter range, a compressive nonlinearity sufficiently close to that of the logarithm so that LIF neurons can be used to multiply neural signals by mere addition of their outputs yielding the logarithm of the product. A simulation of the LIF multiplier shows that under a wide choice of parameters, a LIF neuron can log-multiply its inputs to within a 5% relative error.

Local image structure is widely used in theories of both machine and biological vision. The form of the differential operators describing this structure for space-invariant images has been well documented. Although space-variant coordinates are universally used in mammalian visual systems, the form of the operators in the space-variant coordinate system has received little attention. In this report we derive the form of the most common differential operators and surface characteristics in the space-variant domain and show examples of their use. The operators include the Laplacian, the gradient and the divergence, as well as the fundamental forms of the image treated as a surface. We illustrate the use of these results by deriving the space-variant form of corner detection and image enhancement algorithms. The latter is shown to have interesting properties in the complex log domain, implicitly encoding a variable grid-size integration of the underlying PDE, allowing rapid enhancement of large scale peripheral features while preserving high spatial frequencies in the fovea. Copyright 1997 Elsevier Science Ltd.

Space-variant (or foveating) vision architectures are of importance in both machine and biological vision. In this paper, we focus on a particular space-variant map, the log-polar map, which approximates the primate visual map, and which has been applied in machine vision by a number of investigators during the past two decades. Associated with the log-polar map, we define a new linear integral transform, which we call the exponential chirp transform. This transform provides frequency domain image processing for space-variant image formats, while preserving the major aspects of the shift-invariant properties of the usual Fourier transform. We then show that a log-polar coordinate transform in frequency provides a fast exponential chirp transform. This provides size and rotation, in addition to shift, invariant properties in the transformed space. Finally, we demonstrate the use of the fast exponential chirp algorithm on a database of images in a template matching task, and also demonstrate its uses for spatial filtering.

Multiscale image enhancement and representation is an important part of biological and machine early vision systems. The process of constructing this representation must be both rapid and insensitive to noise, while retaining image structure at all scales. This is a complex task as small scale structure is difficult to distinguish from noise, while larger scale structure requires more computational effort. In both cases, good localization can be problematic. Errors can also arise when conflicting results at different scales require cross-scale arbitration. Structure sensitive multiscale techniques attempt to analyze an image at a variety of scales within a single image. Various techniques are compared. In this paper, we present a technique which obtains an approximate solution to the partial differential equation (PDE) for a specific time, via the solution of an integral equation which is the nonlinear analog of convolution. The kernel function of the integral equation plays the same role that a Green's function does for a linear PDE, allowing the direct solution of the nonlinear PDE for a specific time without requiring integration through intermediate times. We then use a learning technique to approximate the kernel function for arbitrary input images. The result is an improvement in speed and noise-sensitivity, as well as providing a means to parallelize an otherwise serial algorithm.

The use of visual representations in which retinal neurons receptive fields are not constant over the visual field is universal in the visual systems of higher vertebrates, and is coming to play an important role in active vision applications. The breaking of translation symmetry that is unavoidably associated with non-uniform sampling presents a major algorithmic complication for image processing. In this paper we use a Lie group approach to derive a kernel which provides a quasi-shift (i.e. approximate shift) invariant template matching capability, under normal convolution in the distorted (range) coordinates of the non-uniform mapping. We work out the special case of the log-polar mapping, which is of great interest in vision; in this case, we call the associated linear integral transform the "exponential chirp transform" (ECT). The method is, however, general for other forms of mapping, or warp, function.

In the machine vision community multi-scale image enhancement and analysis has frequently been accomplished using a diffusion or equivalent process. Linear diffusion can be replaced by convolution with Gaussian kernels, as the Gaussian is the Green's function of such a system. In this paper we present a technique which obtains an approximate solution to a nonlinear diffusion process via the solution of an integral equation which is the nonlinear analog of convolution. The kernel function of the integral equation plays the same role that a Green's function does for a linear PDE, allowing the direct solution of the nonlinear PDE for a specific time without requiring integration through intermediate times. We then use a learning technique to approximate the kernel function for arbitrary input images. The result is an improvement in speed and noise-sensitivity, as well as providing a parallel algorithm.

The term space-variant vision was introduced in the late 1980s to refer to sensor architectures based on a smooth variation of resolution across the workspace, like that of the human visual system. The use of such sensor architectures is rapidly becoming an important factor in machine vision in which the constraints of size weight, cost and performance must be jointly optimized. The structure of this paper consists of four parts. A review of the four generic architectures for vision will be presented, providing a context for the term “ active vision”, and a justification for the importance, and the connection between, space-variant architectures and active vision methods. A brief quantitative review of the specific space-variant properties of primate visual cortex topography will be provided, in the cortex of sensor design. The engineering and algorithmic problems that are associated with exploiting space-variant systems will be stated. Examples of several recently constructed miniature space-variant active vision systems will be briefly reviewed, along with a brief discussion of solutions to the basic problem areas in space-variant vision.

Outlines a method to derive geometric invariance kernels which may be applied to a space-variant sensor architecture. The basic idea as to transform a kernel with desired symmetry properties (e.g. the Fourier kernel) in the domain to the range of the transform. By combining this transformed kernel with the Jacobian of the transformation, the authors obtain a new integral transform, in the range, which has similar properties to the original transform. The authors illustrate this idea with a variant of the Mellin-Fourier transform, applied to an image which has been transformed by a log-polar mapping. The kernel obtained, which the authors call an "exponential chirp" has properties (unlike the Mellin-Fourier transform) which are both consistent with the spatial nature of human vision and can be applied directly in the space-variant image plane. The authors outline applications to visual template matching and auto-correlation, and show a one-dimensional example of a generalization of cepstral auto-correlation using this method.

In this paper, the design and implementation of a miniature visually guided robot vehicle are described. The design principle underlying this vehicle, which is called CORTEX-II, is the space-variant visual architecture of visual cortex. This allows a wide visual field and high resolution to be maintained in a small and relatively inexpensive system. With a total weight of under twenty kg and size of about .5 meters, CORTEX-II incorporates a three degree of freedom active vision system (pan, tilt and zoom) mounted on a 1 degree of freedom "neck", 160 Mflops (loosely coupled array of four TI320C40 parallel DSP's) and 48 megabytes of memory. Topics discussed here are modification of a stock RC vehicle platform, integration of the parallel DSP platform, active vision system, battery and power systems, communications, and a programming environment for development of the real-time parallel tasks that is transparently portable between simulation and robot run time contexts. Potential applications for systems of this type include traffic monitoring, autonomous driving research, security and surveillance, space-exploration, smart weapons systems, and other application domains in which small, low-cost, high performance visually guided robots are required.

Smoothing a random pattern of orientations causes the appearance of orientation "vortices." These patterns are similar to the hypercolumn pattern of orientation tuning in monkey visual cortex, and to the "pinwheels" that have been observed in cat area 18. The generic presence of such patterns in continuous orientation maps is a consequence of a basic topological theorem (nonretraction of R/sup 2/->S/sup 1/), together with the stochastic properties of random orientation distributions. There as a close correspondence between experimental results from cat area 18 and computer simulations based on smoothed random orientations. Several of the qualitative features of cortical hypercolumn patterns, including the "puff-extra" structure of monkey V-1, are evident in our simulations. There are two important conclusions from this work. (1) Experimental observation of orientation "vortex" structure in any visually excitable neural tissue must be evaluated in the light of the null hypothesis that these patterns are readily formed from smoothed, random orientation distributions, (2) The underlying explanation for the "vortex" patterns which likely exist in primate and cat visual cortex is fundamentally topological, and follows directly from the definition of orientation, and the existence of local correlation of orientation in cortex.

Image warping, often referred to as "rubber sheeting," represents the deformation of a domain image space into a range image space. In this paper, a technique which extends the definition of a rubber-sheet transformation to allow a polygonal region to be warped into one or more subsets of itself, where the subsets may be multiply connected, is described. To do this, it constructs a set of "slits" in the domain image, which correspond to discontinuities and concavities in the range image, using a technique based on generalized Voronoi diagrams. The concept of medial axis is extended to describe inner and outer medial contours of a polygon. Polygonal regions are decomposed into annular subregions, and path homotopies are introduced to describe the annular subregions. These constructions motivate the definition of a ladder, which guides the construction of grid point pairs necessary to effect the warp itself.

A pan-tilt mechanism is a computer-controlled actuator designed to point an object such as a camera sensor. For applications in active vision, a pan-tilt mechanism should be accurate, fast, small, inexpensive and have low power requirements. The authors have designed and constructed a new type of actuator meeting these requirements, which incorporates both pan and tilt into a single, two-degree-of-freedom device. The spherical pointing motor (SPM) consists of three orthogonal motor windings in a permanent magnetic field, configured to move a small camera mounted on a gimbal. It is an absolute positioning device and is run open-loop. The SPM is capable of panning and tilting a load of 15 grams, for example a CCD image sensor, at rotational velocities of several hundred degrees per second with a repeatability of .15/spl deg/. The authors have also built a miniature camera consisting of a single CCD sensor chip and miniature lens assembly that fits on the rotor of this motor. In this paper, the authors discuss the theory of the SPM, which includes its basic electromagnetic principles, and derive the relationship between applied currents and resultant motor position. The authors present an automatic calibration procedure and discuss open- and closed-loop control strategies. Finally, the authors present the physical characteristics and results of their prototype.>

The authors have developed a prototype miniaturized active vision system whose sensor architecture is based on a logarithmically structured space-variant pixel geometry. This system integrates a CCD sensor, miniature pan-tilt actuator, controller, general purpose processors and display. Due to the ability of space-variant sensors to cover large work-spaces yet provide high acuity with an extremely small number of pixels, space-variant active vision system architectures provide the potential for radical reductions in system size and cost. The authors describe a prototype space-variant active vision system which performs tasks such as moving object tracking and functions as a video telephone. The potential application domains for systems of this type include vision systems for mobile robots and robot manipulators, traffic monitoring systems, security and surveillance, and consumer video communications.>

An active vision system with a multiresolution sensor has the advantages of a wide visual field, high central resolution and low data rate. The authors use a special space-variant sensor based on complex log mapping to do character recognition in real scenes. The authors describe experiments with feature designs based on several statistical OCR methods: characteristic loci, partition and projection. The authors also examine several rotation-invariant feature designs based on the partition and projection methods. After studying the problem of recognizing strings in real scenes. The authors derive a rule based approach to solve the attention problem in the context of pattern recognition. Finally the authors describe an active vision system which successfully recognizes characters on a license plate in a real scene.>

The authors investigate two small robotic pan-tilt devices that differ from the conventional motor-on-motor design. The Platform Pantilt is based on a parallel linkage actuated by two small DC linear stepper motors. The spherical pointing motor (SPM) is a two-axis actuator built using three orthogonal motor windings. The SPM is controlled open-loop and is capable of panning and tilting a load of 15 grams, for example a CCD image sensor, at rotational velocities up to 600 degrees /sec. It is 4*5*6 cm and weight 160 grams. A subminiature camera consisting of a single CCD sensor chip and a lens assembly that fits on the rotor of this motor have also been built.>

Presents a robotic video telephone application of the Cortex-1 miniaturized space-variant active vision system. The embedded processor architecture of Cortex-1 enables it to implement a variety of functions not found in conventional video telephones, for example the camera tracks moving users with its pantilt mechanism. The authors also report an analog channel coding scheme to transmit logmap video images through band-limited analog channels such as the public switched telephone network (PSTN). The transmitter divides the frequency band into 768 channels, and modulates two values in quadrature on each channel. Some channels are reserved for special calibration signals enabling the receiver to recover both the phase and magnitude of the transmitted signal. The remaining channels carry pixel intensities.>

A space-variant sensor design based on the conformal mapping of the half disk, w=log (z+a), with real a>0, which characterizes the anatomical structure of the primate and human visual systems is discussed. There are three relevant parameters: the circumferential index kappa which is defined as the number of pixels around the periphery of the sensor, the visual field radius R (of the half-disk to be mapped), and the map parameter a, which displaces the logarithm's singularity at the origin out of the domain of the mapping. It is shown that the log sensor requires O( kappa /sup 2/log (R/a)) pixels. An analysis is presented which makes it possible to compare directly the space complexity of different sensor designs in the complex logarithmic family. In particular, rough estimates can be obtained of the parameters necessary to duplicate the field width/resolution performance of the human visual system.>

A characteristic feature of vertebrate sensory cortex (and midbrain) is the existence of multiple two-dimensional map representations. Some workers have considered single-map classification (e.g. Kohonen 1984) but little work has focused on the use of multiple maps. We have constructed a multiple-map classifier, which permits abstraction of the computational properties of a multiple-map architecture. We identify three problems which characterize a multiple-map classifier: classification in two dimensions, mapping from high dimensions to two dimensions, and combination of multiple maps. We demonstrate component solutions to each of the problems, using Parzen-window density estimation in two dimensions, a generalized Fisher discriminant function for dimensionality reduction, and split/merge methods to construct a “tree of maps” for the multiple-map representation. The combination of components is modular and each component could be improved or replaced without affecting the other components. The classifier training procedure requires time linear in the number of training examples; classification time is independent of the number of training examples and requires constant space. Performance of this classifier on Fisher's iris data, Gaussian clusters on a five-dimensional simplex, and digitized speech data is comparable to competing algorithms, such as nearest-neighbor, back-propagation and Gaussian classifiers. This work provides an example of the computational utility of multiple-map representations for classification. It is one step towards the goal of understanding why brain areas such as visual cortex utilize multiple map-like representations of the world.

Methods are described to unfold and flatten the curved, convoluted surfaces of the brain in order to study the functional architectures and neural maps embedded in them. In order to do this, it is necessary to solve the general mapmaker's problem for representing curved surfaces by planar models. This algorithm has applications in areas other than computer-aided neuroanatomy, such as robotics motion planning and geophysics. The algorithm maximizes the goodness of fit distances in these surfaces to distances in a planar configuration of points. It is illustrated with a flattening of monkey visual cortex, which is an extremely complex folded surface. Distance errors in the range of several percent are found, with isolated regions of larger error, for the class of cortical surfaces studied so far.>

The authors implement an algorithm that finds minimal (geodesic) distances on a three-dimensional polyhedral surface. The algorithm is intrinsically parallel, in as much as it deals with all nodes simultaneously, and is simple to implement. Although exponential in complexity, it can be used with a companion gradient-descent surface-flattening algorithm that produces an optimal flattening of a polyhedral surface. Together, these two algorithms have made it possible to obtain accurate flattening of biological surfaces consisting of several thousand triangular faces (monkey visual cortex) by providing a characterization of the distance geometry of these surfaces. The authors propose this approach as a pragmatic solution to characterizing the surface geometry of the complex polyhedral surfaces which are encountered in the cortex of vertebrates.>

Many primate visual cortex architectures have a prominent feature responsible for the mixing of left and right eye visual data: ocular dominance columns represent thin (about 5-10 minutes of arc) strips of alternating left and right eye input to the brain. It is shown that such an architecture, when operated upon with a cepstral filter, provides a strong cue for binocular stereopsis. Specifically, the vector of binocular disparity may be easily identified in the output of the (columnar based) cepstral filter. This algorithm is illustrated with application to a random dot stereogram and to natural images. The authors suggest that this provides a fast algorithm for stereo segmentation, in a machine vision context. In a biological context, it may provide a computational rationale for the existence of columnar systems with regard to both ocular mixing and other visual modalities that have a columnar architecture.>

The authors discuss three algorithms related to the blending of a single scene from multiple frames acquired from a space-variant sensor. Given a series of space-variant contour-based scenes with different fixation points, they show how to fuse these into a single multiscan view, which incorporates the information present in the individual scans. They demonstrate an (attentional) algorithm which recursively examines the current knowledge of the scene in order best to choose the next fixation point in terms of focusing attention on regions of maximum boundary curvature. They discuss a simple metric for evaluating convergence over a scan path. This may be used to compare the performance of various attentional algorithms. They discuss their work in light of both machine and biological vision.>

The calculus of two-dimensional mappings is reviewed. Currently available data suggests that a conformal (isotropic) mapping is sufficient to model the global topography of primate striate cortex. The addition of a shear component to this mapping is outlined. A similar analysis is applied to the local map structure of striate cortex. Models based on a local reiteration of the complex logarithm and on Radon (and backprojection) mappings are presented. A variety of computational functions associated with the novel architectures for image processing suggested by striate cortex neuroanatomy are discussed. Applications to segmentation, perceptual invariances, shape analysis, and visual data compression are included. Finally, recent experimental results on shape analysis by neurons of infero-temporal cortex are presented.