nils-herrmann/clean_scirepeval huggingface dataset:
The g Factor: Relating Distributions on Features to Distributions on Images

We describe the g-factor, which relates probability distributions on image features to distributions on the images themselves. The g-factor depends only on our choice of features and lattice quantization and is independent of the training image data. We illustrate the importance of the g-factor by analyzing how the parameters of Markov Random Field (i.e. Gibbs or log-linear) probability models of images are learned from data by maximum likelihood estimation. In particular, we study homogeneous MRF models which learn image distributions in terms of clique potentials corresponding to feature histogram statistics (cf. Minimax Entropy Learning (MEL) by Zhu, Wu and Mumford 1997 ). We first use our analysis of the g-factor to determine when the clique potentials decouple for different features. Second, we show that clique potentials can be computed analytically by approximating the g-factor. Third, we demonstrate a connection between this approximation and the Generalized Iterative Scaling algorithm (GIS), due to Darroch and Ratcliff 1972 , for calculating potentials. This connection enables us to use GIS to improve our multinomial approximation, using Bethe-Kikuchi[8] approximations to simplify the GIS procedure. We support our analysis by computer simulations.
The Concave-Convex Procedure (CCCP)

We introduce the Concave-Convex procedure (CCCP) which constructs discrete time iterative dynamical systems which are guaranteed to monotonically decrease global optimization/energy functions. It can be applied to (almost) any optimization problem and many existing algorithms can be interpreted in terms of CCCP. In particular, we prove relationships to some applications of Legendre transform techniques. We then illustrate CCCP by applications to Potts models, linear assignment, EM algorithms, and Generalized Iterative Scaling (GIS). CCCP can be used both as a new way to understand existing optimization algorithms and as a procedure for generating new algorithms.
The KGBR viewpoint-lighting ambiguity and its resolution by generic constraints

We describe a novel viewpoint-lighting ambiguity which we call the KGBR. This ambiguity assumes orthographic projecting or an affine camera, and uses Lambertian reflectance functions including case/attached shadows and multiple light sources. A KGBR transform alters the geometry (by a three-dimensional affine transformation) and albedo properties of objects. If two objects are related by a KGBR transform then for any viewpoint and lighting of the first object there exists a corresponding viewpoint and lighting of the second object so that the images are identical up to an affine transformation. The Generalized Bas Relief (GBR) ambiguity is obtained as a special case of the KGBR. We describe generic viewpoint and lighting assumptions and show that either, or both, resolve this ambiguity by biasing towards objects with planar geometry.
Order parameters for minimax entropy distributions: when does high level knowledge help?

Many problems in vision can be formulated as Bayesian inference. It is important to determine the accuracy of these inferences and how they depend on the problem domain. In recent work, Coughlan and Yuille showed that, for a restricted class of problems, the performance of Bayesian inference could be summarized by an order parameter K which depends on the probability distributions which characterize the problem domain. In this paper we generalize the theory of order parameters so that it applies to domains for which the probability models can be obtained by Minimax Entropy learning theory. By analyzing order parameters it is possible to determine whether a target can be detected using a general purpose "generic" model or whether a more specific "high-level" model is needed. At critical values of the order parameters the problem becomes unsolvable without the addition of extra prior knowledge.
The Manhattan World Assumption: Regularities in Scene Statistics which Enable Bayesian Inference

Preliminary work by the authors made use of the so-called "Manhattan world" assumption about the scene statistics of city and indoor scenes. This assumption stated that such scenes were built on a cartesian grid which led to regularities in the image edge gradient statistics. In this paper we explore the general applicability of this assumption and show that, surprisingly, it holds in a large variety of less structured environments including rural scenes. This enables us, from a single image, to determine the orientation of the viewer relative to the scene structure and also to detect target objects which are not aligned with the grid. These inferences are performed using a Bayesian model with probability distributions (e.g. on the image gradient statistics) learnt from real data.
Fundamental Limits of Bayesian Inference: Order Parameters and Phase Transitions for Road Tracking

There is a growing interest in formulating vision problems in terms of Bayesian inference and, in particular, the maximum a posteriori (MAP) estimator. In this paper, we consider the special case of detecting roads from aerial images and demonstrate that analysis of this ensemble enables us to determine fundamental bounds on the performance of the MAP estimate. We demonstrate that there is a phase transition at a critical value of the order parameter; below this phase transition, it is impossible to detect the road by any algorithm. We derive closely related order parameters which determine the time and memory complexity of search and the accuracy of the solution using the n* search strategy. Our approach can be applied to other vision problems, and we briefly summarize the results when the model uses the "wrong prior". We comment on how our work relates to studies of the complexity of visual search and the critical behaviour in the computational cost of solving NP-complete problems.
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).
Efficient Deformable Template Detection and Localization without User Initialization

A novel deformable template is presented which detects the boundary of an open hand in a grayscale image without initialization by the user. A dynamic programming algorithm enhanced by pruning techniques finds the hand contour in the image in as little as 19 s on a Pentium 150 MHz. The template is translation- and rotation-invariant and accomodates shape deformation, significant occlusion and background clutter, and the presence of multiple hands.
Statistical cues for domain specific image segmentation with performance analysis

This paper investigates the use of colour and texture cues for segmentation of images within two specified domains. The first is the Sowerby dataset, which contains one hundred colour photographs of country roads in England that have been interactively segmented and classified into six classes-edge, vegetation, air, road, building, and other. The second domain is a set of thirty five-images, taken in San Francisco, which have been interactively segmented into similar classes. In each domain we learn the joint probability distributions of filter responses, based on colour and texture, for each class. These distributions are then used for classification. We restrict ourselves to a limited number of filters in order to ensure that the learnt filter responses do not overfit the training data (our region classes are chosen so as to ensure that there is enough data to avoid over fitting). We do performance analysis on the two datasets by evaluating the false positive and false negative error rates for the classification. This shows that the learnt models achieve high accuracy in classifying individual pixels into those classes for which the filter responses are approximately spatially homogeneous (i.e. road, vegetation, and air but not edge and building). A more sensitive performance measure, the Chernoff information, is calculated in order to quantify how well the cues for edge and building are doing. This demonstrates that statistical knowledge of the domain is a powerful tool for segmentation.
Unified framework for performance analysis of Bayesian inference

Many problems in image analysis and ATR can be formulated as Bayesian inference. In this paper we present a unified framework to quantify performance (i.e. the accuracy and uncertainty of inference) in terms of Bayesian decision theory. We demonstrate that existing work on image analysis and ATR performance can be summarized in terms of these concepts. This includes performance measures such as signal- to-noise ratios, Cramer-Rao lower bounds, Hilbert-Schmidt bounds, and ROC curves. Secondly, we describe how recent work by the authors on order parameters can be reformulated within this framework. This includes analyzing how phase transitions can occur for target detection problems so that at critical values of the order parameters it becomes impossible to detect the target. We also analyze the case where the inference process uses weaker prior knowledge to detect the target and quantify in what situations this strategy is effective.
Shadows, Shading, and Projective Ambiguity

In a scene observed from a fixed viewpoint, the set of shadow curves in an image changes as a point light source (nearby or at infinity) assumes different locations. We show that for any finite set of point light sources illuminating an object viewed under either orthographic or perspective projection, there is an equivalence class of object shapes having the same set of shadows. Members of this equivalence class differ by a four parameter family of projective transformations, and the shadows of a transformed object are identical when the same transformation is applied to the light source locations. Under orthographic projection, this family is the generalized bas-relief (GBR) transformation, and we show that the GBR transformation is the only family of transformations of an object's shape for which the complete set of imaged shadows is identical. Furthermore, for objects with Lambertian surfaces illuminated by distant light sources, the equivalence class of object shapes which preserves shadows also preserves surface shading. Finally, we show that given multiple images under differing and unknown light source directions, it is possible to reconstruct an object's shape up to these transformations from the shadows alone.
Convergence Properties of the Softassign Quadratic Assignment Algorithm

The softassign quadratic assignment algorithm is a discrete-time, continuous-state, synchronous updating optimizing neural network. While its effectiveness has been shown in the traveling salesman problem, graph matching, and graph partitioning in thousands of simulations, its convergence properties have not been studied. Here, we construct discrete-time Lyapunov functions for the cases of exact and approximate doubly stochastic constraint satisfaction, which show convergence to a fixed point. The combination of good convergence properties and experimental success makes the softassign algorithm an excellent choice for neural quadratic assignment optimization.
High-level and generic models for visual search: When does high level knowledge help?

We analyze the problem of detecting a road target in background clutter and investigate the amount of prior (i.e. target specific) knowledge needed to perform this search task. The problem is formulated in terms of Bayesian inference and we define a Bayesian ensemble of problem instances. This formulation implies that the performance measures of different models depend on order parameters which characterize the problem. This demonstrates that if there is little clutter then only weak knowledge about the target is required in order to detect the target. However at a critical value of the order parameters there is a phase transition and it becomes effectively impossible to detect the target unless high-level target specific knowledge is used. These phase transitions determine different regimes within which different search strategies will be effective. These results have implications for bottom-up and top-down theories of vision.
Two- and Three-Dimensional Patterns of the Face

The human face is perhaps the most familiar and easily recognized object in the world, yet both its three-dimensional shape and its two-dimensional images are complex and hard to characterize. This book develops the vocabulary of ridges and parabolic curves, of illumination eigenfaces and elastic warpings for describing the perceptually salient features of a face and its images. The book also explores the underlying mathematics and applies these mathematical techniques to the computer vision problem of face recognition, using both optical and range images.
Fundamental bounds on edge detection: an information theoretic evaluation of different edge cues

We treat the problem of edge detection as one of statistical inference. Local edge cues, implemented by filters, provide information about the likely positions of edges which can be used as input to higher-level models. Different edge cues can be evaluated by the statistical effectiveness of their corresponding filters evaluated on a dataset of 100 presegmented images. We use information theoretic measures to determine the effectiveness of a variety of different edge detectors working at multiple scales on black and white and color images. Our results give quantitative measures for the advantages of multi-level processing, for the use of chromaticity in addition to greyscale, and for the relative effectiveness of different detectors.
Bayesian A* Tree Search with Expected O(N) Convergence Rates for Road Tracking

This paper develops a theory for the convergence rates of A* algorithms for real-world vision problems, such as road tracking, which can be formulated in terms of maximizing a reward function derived using Bayesian probability theory. Such problems are well suited to A* tree search and it can be shown that many algorithms proposed to solve them are special cases, or variants, of A*. Moreover, the Bayesian formulation naturally defines a probability distribution on the ensemble of problem instances, which we call the Bayesian Ensemble. We analyze the Bayesian ensemble, using techniques from information theory, and mathematically prove expected O(N) convergence rates of inadmissible A* algorithms. These rates depend on an "order parameter" which characterizes the difficulty of the problem.
Manhattan World: compass direction from a single image by Bayesian inference

When designing computer vision systems for the blind and visually impaired it is important to determine the orientation of the user relative to the scene. We observe that most indoor and outdoor (city) scenes are designed on a Manhattan three-dimensional grid. This Manhattan grid structure puts strong constraints on the intensity gradients in the image. We demonstrate an algorithm for detecting the orientation of the user in such scenes based on Bayesian inference using statistics which we have learnt in this domain. Our algorithm requires a single input image and does not involve pre-processing stages such as edge detection and Hough grouping. We demonstrate strong experimental results on a range of indoor and outdoor images. We also show that estimating the grid structure makes it significantly easier to detect target objects which are not aligned with the grid.
Convergence Rates of Algorithms for Visual Search: Detecting Visual Contours

This paper formulates the problem of visual search as Bayesian inference and defines a Bayesian ensemble of problem instances. In particular, we address the problem of the detection of visual contours in noise/clutter by optimizing a global criterion which combines local intensity and geometry information. We analyze the convergence rates of A* search algorithms using results from information theory to bound the probability of rare events within the Bayesian ensemble. This analysis determines characteristics of the domain, which we call order parameters, that determine the convergence rates. In particular, we present a specific admissible A* algorithm with pruning which converges, with high probability, with expected time O(N) in the size of the problem. In addition, we briefly summarize extensions of this work which address fundamental limits of target contour detectability (i.e. algorithm independent results) and the use of non-admissible heuristics.
Efficient optimization of a deformable template using dynamic programming

A novel deformable template is presented which detects the boundary of an open hand in a grayscale image. A dynamic programming algorithm enhanced by pruning techniques finds the hand contour in the image in as little as 19 seconds without initialization by the user. The template is translation- and rotation-invariant and accommodates shape deformation, significant occlusion and background clutter, and the presence of multiple hands.
Signfinder: using color to detect, localize and identify informational signs

We describe an approach to detecting, locating and normalizing road signs. The approach will apply provided: (i) the signs have stereotypical boundary shapes (i.e. rectangular, or hexagonal-of course, we allow for these shapes to be distorted by projection to unknown viewpoint), (ii) the writing on the sign has one uniform color and the rest of the sign has a second uniform color (we allow for the color of the illuminant to be unknown). We show that the approach works even under significant illuminant color changes, viewpoint direction, shadowing, and occlusion. This work is part of a project intended to help people who are blind, or whose sight is impaired.
A Phase Space Approach to Minimax Entropy Learning and the Minutemax Approximations

There has been much recent work on measuring image statistics and on learning probability distributions on images. We observe that the mapping from images to statistics is many-to-one and show it can be quantified by a phase space factor. This phase space approach throws light on the Minimax Entropy technique for learning Gibbs distributions on images with potentials derived from image statistics and elucidates the ambiguities that are inherent to determining the potentials. In addition, it shows that if the phase factor can be approximated by an analytic distribution then this approximation yields a swift "Minutemax" algorithm that vastly reduces the computation time for Minimax entropy learning. An illustration of this concept, using a Gaussian to approximate the phase factor, gives a good approximation to the results of Zhu and Mumford (1997) in just seconds of CPU time. The phase space approach also gives insight into the multi-scale potentials found by Zhu and Mumford (1997) and suggests that the forms of the potentials are influenced greatly by phase space considerations. Finally, we prove that probability distributions learned in feature space alone are equivalent to Minimax Entropy learning with a multinomial approximation of the phase factor.
Visual motion estimation and prediction: a probabilistic network model for 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 motion flows in the image sequences. Our theory is expressed in terms of the Bayesian generalization of standard Kalman filtering which allows us to solve temporal grouping in conjunction with prediction and estimation. As demonstrated for tracking isolated contours the Bayesian formulation is superior to approaches which use data association as a first stage followed by conventional Kalman filtering. Our computer simulations demonstrate that our theory qualitatively accounts for several psychophysical experiments on motion occlusion and motion outliers.
Image Warping for Shape Recovery and Recognition

We demonstrate that, for a large class of reflectance functions, there is a direct relationship between image warps and the corresponding geometric deformations of the underlying three-dimensional objects. This helps explain the hidden geometrical assumptions in object recognition schemes which involve two-dimensional image warping computed by matching image intensity. In addition, it allows us to propose a novel variant of shape from shading which we call shape from image warping. The idea is that the three-dimensional shape of an object is estimated by determining how much the image of the object is warped with respect to the image of a known prototype shape. Therefore, detecting the image warp relative to a prototype of known shape allows us to reconstruct the shape of the imaged object. We derive properties of these shape warps and illustrate the results by recovering the shapes of faces.
Shape and albedo from multiple images using integrability

Previous work has developed an approach for estimating shape and albedo from multiple images assuming Lambertian reflectance with single light sources. The main contributions of this paper are: (i) to show how the approach can be generalized to include ambient background illumination, (ii) to demonstrate the use of the integrability constraint for solving this problem, and (iii) an iterative algorithm which is able to improve the analysis by finding shadows and rejecting them.
Relating Image Warping to 3D Geometrical Deformations

We demonstrate that, for a large class of reflectance functions, there is a direct relationship between image warps and the corresponding geometric deformations of the underlying three-dimensional objects. This helps explain the hidden geometrical assumptions in object recognition schemes which involve two-dimensional image warping computed by matching image intensity. In addition, it allows us to propose a novel variant of shape from shading which we call shape from image warping. The idea is that the three-dimensional shape of an object is estimated by determining how much the image of the object is warped with respect to the image of a known prototype shape. Therefore detecting the image warp relative to a prototype of known shape allows us to reconstruct the shape of the imaged object. We derive properties of these shape warps and illustrate the results by recovering the shapes of faces.