Multi-scale representations are motivated by the scale invariant properties of natural images. While many low level statistical measures, such as the local mean and variance of intensity, behave in a scale invariant manner, there are many higher order deviations from scale invariance where zero-crossings merge and disappear. Such scale variant behavior is important information to represent because it is not easily predicted from lower resolution data. A scale variant image pyramid is a representation that separates this information from the more redundant and predictable scale invariant information.

Natural images are approximately scale invariant resulting in long range statistical regularities that typically obey a power law. For example, images have considerable regularity in their second order spatial correlations as measured by the power spectrum. Processing images to remove these expected correlations is known as whitening an image. Because the expected value of the power spectrum has a regular form (a power law) linear processing such as convolution can be used to whiten an image. After whitening an image, higher order regularities that cannot be removed with linear processing still exist in the form of correlations in the magnitude. In this paper it is shown that these correlations also obey a power law and a non-linear method is used to remove them, a process referred to as higher order whitening. The method is invertible demonstrating that while redundancy is removed no information is lost. Experiments are given showing that after higher order whitening the coefficients can be severely quantized yet a good reconstruction is possible despite the nonlinearities.

A commonly used representation of a visual pattern is a statistical distribution measured from the output of a bank of filters (Gaussian, Laplacian, Gabor, etc.). Both marginal and joint distributions of filter responses have been advocated and effectively used for a variety of vision tasks, including texture classification, texture synthesis, object detection, and image retrieval. This paper examines the ability of these representations to discriminate between an arbitrary pair of visual stimuli. Examples of patterns are derived that provably possess the same marginal and joint statistical properties, yet are "visually distinct." This is accomplished by showing sufficient conditions for matching the first k moments of the marginal distributions of a pair of images. Then, given a set of filters, we show how to match the marginal statistics of the subband images formed through convolution with the filter set. Next, joint statistics are examined and images with similar joint distributions of subband responses are shown. Finally, distinct periodic patterns are derived that possess approximately the same subband statistics for any arbitrary filter set.

A commonly used representation of a visual pattern is the set of marginal probability distributions of the output of a bank of filters (Gaussian, Laplacian, Gabor etc.). This representation has been used effectively for a variety of vision tasks including texture classification, texture synthesis, object detection and image retrieval. We examine the ability of this representation to discriminate between an arbitrary pair of visual stimuli. Examples of patterns are derived that provably possess the same marginal statistical properties, yet are "visually distinct." These results suggest the need for either employing a large and diverse filter bank or incorporating joint statistics in order to represent a large class of visual patterns.

This paper introduces a new method to register images that are rotated and translated with respect to each other. The method works by transforming each image to a gradient distribution space. This space represents the likelihood of finding a particular gradient in the image and is invariant to translation. Once transformed the rotation between the images is efficiently found using correlation. Unlike Fourier based methods, phase information is retained in the gradient distribution space, thus a larger class of images can be accurately registered. The method is computationally efficient and does not require nonlinear optimization or iterative methods. Furthermore, large rotations and translations can easily be handled.

It has been shown elsewhere how mirrors can be used to capture stereo images with a single camera, an approach termed catadioptric stereo. We present novel catadioptric sensors that use mirrors to produce rectified stereo images. The scanline correspondence of these images benefits real-time stereo by avoiding the computational cost and image degradation due to resampling when rectification is performed after image capture. First, we develop a theory which determines the number of mirrors that must be used and the constraints on those mirrors that must be satisfied to obtain rectified stereo images with a single camera. Then, we discuss in detail the use of both one and three mirrors. In addition, we show how the mirrors should be placed in order to minimize sensor size for a given baseline, an important design consideration. In order to understand the feasibility of building these sensors, we analyze rectification errors due to misplacement of the camera with respect to the mirrors.

Image rectification is the process of warping a pair of stereo images in order to align the epipolar lines with the scan-lines of the images. Once a pair of images is rectified, stereo matching can be implemented in an efficient manner. Given the epipolar geometry, it is straightforward to define a rectifying transformation, however, many transformations will lead to unwanted image distortions. In this paper, we present a novel method for stereo rectification that determines the transformation that minimizes the effects of resampling that can impede stereo matching. The effects we seek to minimize are the loss of pixels due to under-sampling and the creation of new pixels due to over-sampling. To minimize these effects we parameterize the family of rectification transformations and solve for the one that minimizes the change in local area integrated over the area of the images.

It has been previously shown how mirrors can be used to capture stereo images with a single camera, an approach termed catadioptric stereo. In this paper we present novel catadioptric sensors which use mirrors to produce rectified stereo images. The scan-line correspondence of these images benefits real-time stereo by avoiding the computational cost and image degradation due to resampling when rectification is performed after image capture. First, we develop a theory which determines the number of mirrors that must be used and the constraints on those mirrors that must be satisfied to obtain rectified stereo images with a single camera. Then we discuss in detail the use of both one and three mirrors. In addition, we show how the mirrors should be placed in order to minimize sensor size for a given baseline, an important design consideration.

A real-time visual recognition system, that enables a human conductor to control an electronic orchestra using gestures of a traditional conductor's baton, is described. The positions of the baton and conductor's hand are identified in a sequence of images from a pair of cameras, and tracked in 3D space. Gestures defining the musical beat are detected in the baton's trajectory, and conveyed to a sound synthesis system, as events that control the tempo and the phase of the music. Parameters that can enable the control of the volume of sound are computed from the range variations of the baton and the hand. The system's response is nearly instantaneous. The beat detection is reliable, and precise enough to be used by a professional conductor. It has been used to conduct an integrated electronic performance that combined a synthesized orchestra and animated ballet.

By using mirror reflections of a scene, stereo images can be captured with a single camera (catadioptric stereo). Single camera stereo provides both geometric and radiometric advantages over traditional two camera stereo. In this paper we discuss the geometry and calibration of catadioptric stereo with two planar mirrors and show how the relative orientation, the epipolar geometry and the estimation of the focal length are constrained by planar motion. In addition, we have implemented a real-time system which demonstrates the viability of stereo with mirrors as an alternative to traditional two camera stereo.

Recent research in image sensors has produced cameras with very large fields of view. An area of computer vision research which will benefit from this technology is the computation of camera motion (ego-motion) from a sequence of images. Traditional cameras suffer from the problem that the direction of translation may lie outside of the field of view, making the computation of camera motion sensitive to noise. In this paper, we present a method for the recovery of ego-motion using omnidirectional cameras. Noting the relationship between spherical projection and wide-angle imaging devices, we propose mapping the image velocity vectors to a sphere, using the Jacobian of the transformation between the projection model of the camera and spherical projection. Once the velocity vectors are mapped to a sphere, we show how existing ego-motion algorithms can be applied and present some experimental results. These results demonstrate the ability to compute egomotion with omnidirectional cameras. 1

Conventional video cameras have limited fields of view which make them restrictive in a variety of applications. A catadioptric sensor uses a combination of lenses and mirrors placed in a carefully arranged configuration to capture a much wider field of view. At Columbia University, we have developed a wide range of catadioptric sensors. Some of these sensors have been designed to produce unusually large fields of view. Others have been constructed for the purpose of depth computation. All our sensors perform in real time using just a PC.

High-level formalisms such as stochastic Petri nets can be used to model complex systems. Analysis of logical and numerical properties of these models often requires the generation and storage of the entire underlying state space. This imposes practical limitations on the types of systems that can be modeled. Because of the vast amount of memory consumed, we investigate distributed algorithms for the generation of state space graphs. The distributed construction allows us to take advantage of the combined memory readily available on a network of workstations. The key technical problem is to find effective methods for on-the-fly partitioning, so that the state space is evenly distributed among processors. In this article we report on the implementation of a distributed state space generator that may be linked to a number of existing system modeling tools. We discuss partitioning strategies in the context of Petri net models, and report on performance observed on a network of workstations, as well as on a distributed memory multicomputer.