PubMed Health⌕ Search

Biomedical subjects

A L Yuille

Publications and source records attributed to A L Yuille.

12 recordsLinked to original sources

The concave-convex procedure.

The concave-convex procedure (CCCP) is a way to construct discrete-time iterative dynamical systems that are guaranteed to decrease global optimization and energy functions monotonically. This procedure can be applied to almost any optimization problem, and many existing algorithms can be interpreted in terms of it. In particular, we prove that all expectation-maximization algorithms and classes of Legendre minimization and variational bounding algorithms can be reexpressed in terms of CCCP. We show that many existing neural network and mean-field theory algorithms are also examples of CCCP. The generalized iterative scaling algorithm and Sinkhorn's algorithm can also be expressed as CCCP by changing variables. CCCP can be used both as a new way to understand, and prove the convergence of, existing optimization algorithms and as a procedure for generating new algorithms.

Algorithms↗

Manhattan world: orientation and outlier detection by Bayesian inference.

This letter argues that many visual scenes are based on a "Manhattan" three-dimensional grid that imposes regularities on the image statistics. We construct a Bayesian model that implements this assumption and estimates the viewer orientation relative to the Manhattan grid. For many images, these estimates are good approximations to the viewer orientation (as estimated manually by the authors). These estimates also make it easy to detect outlier structures that are unaligned to the grid. To determine the applicability of the Manhattan world model, we implement a null hypothesis model that assumes that the image statistics are independent of any three-dimensional scene structure. We then use the log-likelihood ratio test to determine whether an image satisfies the Manhattan world assumption. Our results show that if an image is estimated to be Manhattan, then the Bayesian model's estimates of viewer direction are almost always accurate (according to our manual estimates), and vice versa.

Artificial Intelligence↗

CCCP algorithms to minimize the Bethe and Kikuchi free energies: convergent alternatives to belief propagation.

This article introduces a class of discrete iterative algorithms that are provably convergent alternatives to belief propagation (BP) and generalized belief propagation (GBP). Our work builds on recent results by Yedidia, Freeman, and Weiss (2000), who showed that the fixed points of BP and GBP algorithms correspond to extrema of the Bethe and Kikuchi free energies, respectively. We obtain two algorithms by applying CCCP to the Bethe and Kikuchi free energies, respectively (CCCP is a procedure, introduced here, for obtaining discrete iterative algorithms by decomposing a cost function into a concave and a convex part). We implement our CCCP algorithms on two- and three-dimensional spin glasses and compare their results to BP and GBP. Our simulations show that the CCCP algorithms are stable and converge very quickly (the speed of CCCP is similar to that of BP and GBP). Unlike CCCP, BP will often not converge for these problems (GBP usually, but not always, converges). The results found by CCCP applied to the Bethe or Kikuchi free energies are equivalent, or slightly better than, those found by BP or GBP, respectively (when BP and GBP converge). Note that for these, and other problems, BP and GBP give very accurate results (see Yedidia et al., 2000), and failure to converge is their major error mode. Finally, we point out that our algorithms have a large range of inference and learning applications.

Algorithms↗

Bayesian A* tree search with expected O(N) node expansions: applications to road tracking.

Many perception, reasoning, and learning problems can be expressed as Bayesian inference. We point out that formulating a problem as Bayesian inference implies specifying a probability distribution on the ensemble of problem instances. This ensemble can be used for analyzing the expected complexity of algorithms and also the algorithm-independent limits of inference. We illustrate this problem by analyzing the complexity of tree search. In particular, we study the problem of road detection, as formulated by Geman and Jedynak (1996). We prove that the expected convergence is linear in the size of the road (the depth of the tree) even though the worst-case performance is exponential. We also put a bound on the constant of the convergence and place a bound on the error rates.

Algorithms↗

Probabilistic motion estimation based on temporal coherence.

We develop a theory for the temporal integration of visual motion motivated by psychophysical experiments. The theory proposes that input data are temporally grouped and used to predict and estimate the motion flows in the image sequence. This temporal grouping can be considered a generalization of the data association techniques that engineers use to study motion sequences. Our temporal grouping theory is expressed in terms of the Bayesian generalization of standard Kalman filtering. To implement the theory, we derive a parallel network that shares some properties of cortical networks. Computer simulations of this network demonstrate that our theory qualitatively accounts for psychophysical experiments on motion occlusion and motion outliers. In deriving our theory, we assumed spatial factorizability of the probability distributions and made the approximation of updating the marginal distributions of velocity at each point. This allowed us to perform local computations and simplified our implementation. We argue that these approximations are suitable for the stimuli we are considering (for which spatial coherence effects are negligible).

Bayes Theorem↗

A model for the estimate of local image velocity by cells in the visual cortex.

Some computational theories of motion perception assume that the first stage en route to this perception is the local estimate of image velocity. However, this assumption is not supported by data from the primary visual cortex. Its motion sensitive cells are not selective to velocity, but rather are directionally selective and tuned to spatio-temporal frequencies. Accordingly, physiologically based theories start with filters selective to oriented spatio-temporal frequencies. This paper shows that computational and physiological theories do not necessarily conflict, because such filters may, as a population, compute velocity locally. To prove this point, we show how to combine the outputs of a class of frequency tuned filters to detect local image velocity. Furthermore, we show that the combination of filters may simulate 'Pattern' cells in the middle temporal area (MT), whereas each filter simulates primary visual cortex cells. These simulations include three properties of the primary cortex. First, the spatio-temporal frequency tuning curves of the individual filters display approximate space-time separability. Secondly, their direction-of-motion tuning curves depend on the distribution of orientations of the components of the Fourier decomposition and speed of the stimulus. Thirdly, the filters show facilitation and suppression for responses to apparent motions in the preferred and null directions, respectively. It is suggested that the MT's role is not to solve the aperture problem, but to estimate velocities from primary cortex information. The spatial integration that accounts for motion coherence may be postponed to a later cortical stage.

Animals↗

Quadrature and the development of orientation selective cortical cells by Hebb rules.

We describe a new theoretical scenario for the development of orientation selective cells in a self-organizing feedforward network with modifiable synapses. A suitable choice of Hebb rule leads to a system that develops symmetric and antisymmetric response fields (quadrature pairs) at the same time as directional selectivity occurs using inhibition between neighboring cells. Quadrature phase relationships between the response properties of adjacent cortical cells is suggestive of several highly efficient information processing strategies.

Animals↗

Energy functions for early vision and analog networks.

This paper describes attempts to model the modules of early vision in terms of minimizing energy functions, in particular energy functions allowing discontinuities in the solution. It examines the success of using Hopfield-style analog networks for solving such problems. Finally it discusses the limitations of the energy function approach.

Models, Neurological↗

A computational theory for the perception of coherent visual motion.

When we see motion, our perception of how one image feature moves depends on the behaviour of other features nearby. In particular, the Gestaltists proposed the law of shared common fate, in which features tend to be perceived as moving together, that is, coherently. Recent psychophysical findings, such as the cooperativity of the motion system and motion capture, support this law. Computationally, coherence is a sensible assumption, because if two features are close then they probably belong to the same object and thus tend to move together. Moreover, the measurement of local motion may be inaccurate and so the integration of motion information over large areas may help to improve the performance. Present theories of visual motion, however, do not account fully for these coherent motion percepts. We propose here a theory that does account for these phenomena and also provides a solution to the aperture problem, where the local information in the image flow is insufficient to specify the motion uniquely.

Humans↗

Spontaneous symmetry-breaking energy functions and the emergence of orientation selective cortical cells.

The mammalian visual cortex is comprised of "hypercolumns" of orientation selective cells. The developmental process by which cells are generated with receptive fields tuned to a variety of orientations has so far remained a mystery. We present a model for the production of orientation selective cells that requires no external stimuli and a minimum of input parameters. The process involves spontaneous symmetry-breaking in an energy function that governs the maturation of the cortical cells in a multi-layer network of Hebb-type feedforward neurons. An important feature is that the symmetry breaking occurs for each cell separately and is not due to global organizing effects. We present examples of receptive field profiles calculated with the symmetry-breaking procedure and note that the results seem robust and may be useful in the study of development in several types of cortical cells. The inclusion of long range lateral (intra-layer) correlations in the energy function could result in the development of cell groups with correlated preferred orientations that resemble the hypercolumns seen in the visual cortex.

Animals↗

Massively parallel implementations of theories for apparent motion.

Two solutions for the correspondence problem for long-range motion are investigated. The first is a modification of the Minimal Mapping Theory (S. Ullman: The Interpretation of Visual Motion, MIT Press, Cambridge, 1979) that is implemented by a massively parallel network. In this network, every two units are interconnected, and thus, its convergence is fast and relatively independent of the number of image features. Computer simulations show that our method accounts as well as the Minimal Mapping Theory for apparent-motion phenomena, although some differences exist. Mathematical proofs provide conditions for the convergence of the network. The second 'solution' for the correspondence problem is called the Structural Theory. This theory assumes that the three-dimensional structure of viewed objects does not change fast in time. Then, the theory looks for the correspondence and three-dimensional structure that best fulfill this assumption. A massively parallel network implementation of this theory is also possible. However, its performance is poor due to the high complexity of its solution space. This supports Ullman's (1979) suggestion that the visual system separates the structure-from-motion process into two stages. First, a stage for motion measurement, and then a stage for structure recovery.

Humans↗

Dependence of speed and direction perception on cinematogram dot density.

In the present experiments, we find that with abrupt decreases in dot density of random-dot cinematograms, perceived speed decreases, while with abrupt increases in dot density, perceived speed increases. Further, in steady-state conditions, perceived speed is also affected in the same way, but to a lesser degree, by the dot density of cinematograms. Direction discrimination of random-dot cinematograms is enhanced when dot density increases abruptly from one stimulus to the next, but is degraded when dot density decreases abruptly. Finally, speed discrimination remains constant even when density changes abruptly. The perceived-speed and direction-discrimination data are consistent with the Motion Coherence theory which motivated this study, and with models that include a smoothing stage similar to this theory. Of the other models that we consider, most predict that increasing dot density reduces perceived speed. The speed-discrimination data could not distinguish between the different theories.

Discrimination, Psychological↗