nils-herrmann/clean_scirepeval huggingface dataset:
Title How Do Heuristics Expedite Markov Chain Search ? Hitting-time Analysis of the Independence Metropolis Sampler Permalink

Solving vision problems often entails searching a solution space for optimal state(s) that has maximum Bayesian posterior probability or minimum energy. When the volume of the space is huge, exhaustive search becomes infeasible. Generic stochastic search (e.g. Markov chain Monte Carlo) could be even worse than exhaustive search as it may visit a state repeatedly. To expedite the Markov chain search, one may use heuristics as proposal probability to guide the search in promising portions of the space. Empirically the recent data-driven Markov chain Monte Carlo (DDMCMC) scheme[14, 12, 2], achieves fast search in a number of vision tasks,intuitively justified by two observations (i). The posterior probabilities in vision tasks often have very low entropy and thus are narrowly focused on a tiny portion of the state space (ii). The proposal probability computed in bottom-up methods can approximate the posterior well. In this paper, we study an independent Metropolis sampler which is often used in designing components of complex MCMC algorithms. We obtain an analytic formula for the expected time to first hit a certain state (“first hitting-time”), as well as very tight lower and upper bounds which depend on the total variation between the target posterior and the heuristic probabilities. These results show, though in humble cases, that one can indeed reach optimal solutions in very few steps with good proposal probabilities regardless of the size of the original search space. This result is different from previous analysis on the Markov chain convergence rate which is bounded by the second largest eigen-value (modulus) and often corresponds to the worst case in the entire search space. In comparison, our analysis bears more relevance to the optimization tasks in vision.
A Stochastic Algorithm for 3D Scene Segmentation and Reconstruction

In this paper, we present a stochastic algorithm by effective Markov chain Monte Carlo (MCMC) for segmenting and reconstructing 3D scenes. The objective is to segment a range image and its associated reflectance map into a number of surfaces which fit to various 3D surface models and have homogeneous reflectance (material) properties. In comparison to previous work on range image segmentation, the paper makes the following contributions. Firstly, it is aimed at generic natural scenes, indoor and outdoor, which are often much complexer than most of the existing experiments in the "polyhedra world". Natural scenes require the algorithm to automatically deal with multiple types (families) of surface models which compete to explain the data. Secondly, it integrates the range image with the reflectance map. The latter provides material properties and is especially useful for surface of high specularity, such as glass, metal, ceramics. Thirdly, the algorithm is designed by reversible jump and diffusion Markov chain dynamics and thus achieves globally optimal solutions under the Bayesian statistical framework. Thus it realizes the cue integration and multiple model switching. Fourthly, it adopts two techniques to improve the speed of the Markov chain search: One is a coarse-to-fine strategy and the other are data driven techniques such as edge detection and clustering. The data driven methods provide important information for narrowing the search spaces in a probabilistic fashion. We apply the algorithm to two data sets and the experiments demonstrate robust and satisfactory results on both. Based on the segmentation results, we extend the reconstruction of surfaces behind occlusions to fill in the occluded parts.
What Are Textons?

Textons refer to fundamental micro-structures in generic natural images and thus constitute the basic elements in early (preattentive) visual perception. However, the word "texton" remains a vague concept in the literature of computer vision and visual perception, and a precise mathematical definition has yet to be found. In this article, we argue that the definition of texton should be governed by a sound mathematical model of images, and the set of textons must be learned from, or best tuned to, an image ensemble. We adopt a generative image model that an image is a superposition of bases from an over-complete dictionary, then a texton is defined as a mini-template that consists of a varying number of image bases with some geometric and photometric configurations. By analogy to physics, if image bases are like protons, neutrons and electrons, then textons are like atoms. Then a small number of textons can be learned from training images as repeating micro-structures. We report four experiments for comparison. The first experiment computes clusters in feature space of filter responses. The second use transformed component analysis in both feature space and image patches. The third adopts a two-layer generative model where an image is generated by image bases and image bases are generated by textons. The fourth experiment shows textons from motion image sequences, which we call movetons.
Parsing Images into Region and Curve Processes

Natura scenes consist of a wide variety of stochastic patterns. While many patterns are represented well by statistical models in two dimensional regions as most image segmentation work assume, some other patterns are fundamentally one dimensional and thus cause major problems in segmentation. We call the former region processes and the latter curve processes. In this paper, we propose a stochastic algorithm for parsing an image into a number of region and curve processes. The paper makes the following contributions to the literature. Firstly, it presents a generative rope model for the curve processes in the form of Hidden Markov Model (HMM). The hidden layer is a Markov chain with each element being an image vase selected from an over-complete basis, such as Difference of Gaussians (DOG) or Difference of Offset Gaussians (DOOG) at various scales and orientations. The rope model accounts for the geometric smoothness and photometric coherence of the curve processes. Secondly, it integrates both 2D region models, such as textures, splines etc with 1D curve models uner the Bayes framework. Because both region and curve models are generative, they compete to explain input images in a layered representation. Thirdl, it achieves global optimization by effective Markov chain Monte Carlo methods in the sense of maximizing a posterior probability. The Markov chain consists of reversivle jumps and diffusions driven by bottom up information. The algorithm is applied to real images with satisfactory results. We verify the results through random synthesis and compare them against segmentations with region processes only.
A Generative Method for Textured Motion: Analysis and Synthesis

Natural scenes contain rich stochastic motion patterns which are characterized by the movement of a large number of small elements, such as falling snow, raining, flying birds, firework and waterfall. In this paper, we call these motion patterns textured motion and present a generative method that combines statistical models and algorithms from both texture and motion analysis. The generative method includes the following three aspects. 1). Photometrically, an image is represented as a superposition of linear bases in atomic decomposition using an overcomplete dictionary, such as Gabor or Laplacian. Such base representation is known to be generic for natural images, and it is low dimensional as the number of bases is often 100 times smaller than the number of pixels. 2). Geometrically, each moving element (called moveton), such as the individual snowflake and bird, is represented by a deformable template which is a group of several spatially adjacent bases. Such templates are learned through clustering. 3). Dynamically, the movetons are tracked through the image sequence by a stochastic algorithm maximizing a posterior probability. A classic second order Markov chain model is adopted for the motion dynamics. The sources and sinks of the movetons are modeled by birth and death maps. We adopt an EM-like stochastic gradient algorithm for inference of the hidden variables: bases, movetons, birth/death maps, parameters of the dynamics. The learned models are also verified through synthesizing random textured motion sequences which bear similar visual appearance with the observed sequences.
Statistical Modeling of Texture Sketch

Recent results on sparse coding and independent component analysis suggest that human vision first represents a visual image by a linear superposition of a relatively small number of localized, elongate, oriented image bases. With this representation, the sketch of an image consists of the locations, orientations, and elongations of the image bases, and the sketch can be visually illustrated by depicting each image base by a linelet of the same length and orientation. Built on the insight of sparse and independent component analysis, we propose a two-level generative model for textures. At the bottom-level, the texture image is represented by a linear superposition of image bases. At the top-level, a Markov model is assumed for the placement of the image bases or the sketch, and the model is characterized by a set of simple geometrical feature statistics.
Image Segmentation by Data-Driven Markov Chain Monte Carlo

This paper presents a computational paradigm called Data-Driven Markov Chain Monte Carlo (DDMCMC) for image segmentation in the Bayesian statistical framework. The paper contributes to image segmentation in four aspects. First, it designs efficient and well-balanced Markov Chain dynamics to explore the complex solution space and, thus, achieves a nearly global optimal solution independent of initial segmentations. Second, it presents a mathematical principle and a K-adventurers algorithm for computing multiple distinct solutions from the Markov chain sequence and, thus, it incorporates intrinsic ambiguities in image segmentation. Third, it utilizes data-driven (bottom-up) techniques, such as clustering and edge detection, to compute importance proposal probabilities, which drive the Markov chain dynamics and achieve tremendous speedup in comparison to the traditional jump-diffusion methods. Fourth, the DDMCMC paradigm provides a unifying framework in which the role of many existing segmentation algorithms, such as, edge detection, clustering, region growing, split-merge, snake/balloon, and region competition, are revealed as either realizing Markov chain dynamics or computing importance proposal probabilities. Thus, the DDMCMC paradigm combines and generalizes these segmentation methods in a principled way. The DDMCMC paradigm adopts seven parametric and nonparametric image models for intensity and color at various regions. We test the DDMCMC paradigm extensively on both color and gray-level images and some results are reported in this paper.
Learning in Gibbsian Fields: How Accurate and How Fast Can It Be?

Gibbsian fields or Markov random fields are widely used in Bayesian image analysis, but learning Gibbs models is computationally expensive. The computational complexity is pronounced by the recent minimax entropy (FRAME) models which use large neighborhoods and hundreds of parameters. In this paper, we present a common framework for learning Gibbs models. We identify two key factors that determine the accuracy and speed of learning Gibbs models: The efficiency of likelihood functions and the variance in approximating partition functions using Monte Carlo integration. We propose three new algorithms. In particular, we are interested in a maximum satellite likelihood estimator, which makes use of a set of precomputed Gibbs models called "satellites" to approximate likelihood functions. This algorithm can approximately estimate the minimax entropy model for textures in seconds in a HP workstation. The performances of various learning algorithms are compared in our experiments.
Learning Inhomogeneous Gibbs Model of Faces by Minimax Entropy

In this paper we propose a novel inhomogeneous Gibbs model by the minimax entropy principle, and apply it to face modeling. The maximum entropy principle generalizes the statistical properties of the observed samples and results in the Gibbs distribution, while the minimum entropy principle makes the learnt distribution close to the observed one. To capture the fine details of a face, an inhomogeneous Gibbs model is derived to learn the local statistics of facial feature points. To alleviate the high dimensionality problem of face models, we propose to learn the distribution in a subspace reduced by principal component analysis or PCA. We demonstrate that our model effectively captures important and subtle non-Gaussian face patterns and efficiently generates good face models.
Visual learning by integrating descriptive and generative methods

This paper presents a mathematical framework for visual learning that integrates two popular statistical learning paradigms in the literature: (I). Descriptive learning, such as Markov random fields and minimax entropy learning, and (II). Generative learning, such as PCA, ICA, TCA, image coding and HMM. We apply this integrated learning framework to texton modeling, and we assume that an observed texture image is generated by multiple layers of hidden stochastic "texton processes" with each texton being a window function, like a mini-template or a wavelet, under affine transformations. The spatial arrangements of the textons are characterized by minimax entropy models. The texton processes generate images by occlusion or linear addition. Thus given a raw input image, the learning framework achieves four goals: (i). Computing the appearance of the textons. (ii) Inferring the hidden stochastic texton processes. (iii). Learning Gibbs models for each texton process and (iv). Verifying the learnt textons and Gibbs models through random sampling and texture synthesis. The integrated framework subsumes the minimax entropy learning paradigm and creates a richer class of probability models for visual patterns, which are suited for middle level vision representations. Furthermore we show that the integration of description and generative methods yields a natural and general framework of visual learning. We demonstrate the proposed framework and algorithms on many real images.
Image segmentation by data driven Markov chain Monte Carlo

This paper presents a computational paradigm called Data Driven Markov Chain Monte Carlo (DDMCMC) for image segmentation in the Bayesian, statistical framework. The paper contributes to image segmentation in three aspects. Firstly, it designs effective and well balanced Markov Chain dynamics to explore the solution space and makes the split and merge process reversible at a middle level vision formulation. Thus it achieves globally optimal solution independent of initial segmentations. Secondly, instead of computing a single maximum a posteriori solution, it proposes a mathematical principle for computing multiple distinct solutions to incorporates intrinsic ambiguities in image segmentation. A k-adventurers algorithm is proposed for extracting distinct multiple solutions from the Markov chain sequence. Thirdly, it utilizes data-driven (bottom-up) techniques, such as clustering and edge detection, to compute importance proposal probabilities, which effectively drive the Markov chain dynamics and achieve tremendous speedup in comparison to traditional jump-diffusion method. Thus DDM-CMC paradigm provides a unifying framework where the role of existing segmentation algorithms, such as; edge detection, clustering, region growing, split-merge, SNAKEs, region competition, are revealed as either realizing Markov chain dynamics or computing importance proposal probabilities. We report some results on color and grey level image segmentation in this paper and refer to a detailed report and a web site for extensive discussion.
Discussion

When looking at our visual environment, we are not only aware of the rich details of the 3-D visual scene, but we also summarize the details into a simple description of “what is where,” which provides the crucial information of a visual scene. Therefore, we can formulate the problem of vision in terms of the following three variables.  a representation of the 3-D scene in full detail.  the abstract description of “what is where.” Of course, summary and details are relative concepts, and the two variables Details and Summary should be understood as the bottom and the top of a pyramid of increasingly abstract layers of visual concepts. We call this pyramid the “scene description.” For instance, for a scenery image, the Summary may consist of abstract concepts such as river, trees, and their overall shapes, and Details may consist of concepts like water ripples and waves, tree leaves, and branches, and their shapes and locations. The meaning of the Summary can be de ned in terms of how the details look and how they are composed together. Mathematically, this amounts to a generative model P (, which decomposes the complexity in Details into deterministic redundancy
Learning inhomogeneous Gibbs model of faces by minimax entropy

In this paper we propose a novel inhomogeneous Gibbs model by the minimax entropy principle, and apply it to face modeling. The maximum entropy principle generalizes the statistical properties of the observed samples and results in the Gibbs distribution, while the minimum entropy principle makes the learnt distribution close to the observed one. To capture the fine details of a face, an inhomogeneous Gibbs model is derived to learn the local statistics of facial feature paints. To alleviate the high dimensionality problem of face models, we propose to learn the distribution in a subspace reduced by principal component analysis or PCA. We demonstrate that our model effectively captures important and subtle non-Gaussian face patterns and efficiently generates good face models.
Asymptotically Admissible Texture Synthesis

Recently there is a resurgent interest in example based texture analysis and synthesis in both computer vision and computer graphics. While study in computer vision is concerned with learning accurate texture models, research in graphics is aimed at effective algorithms for texture synthesis without necessarily obtaining explicit texture model. This paper makes three contributions to this recent excitement. First, we introduce a theoretical framework for designing and analyzing texture sampling algorithms. This framework, built upon the mathematical definition of textures, measures a texture sampling algorithm using admissibility, effectiveness, and sampling speed. Second, we compare and analyze texture sampling algorithms based on admissibility and effectiveness. In particular, we propose different design criteria for texture analysis algorithms in computer vision and texture synthesis algorithms in computer graphics. Finally, we develop a novel texture synthesis algorithm which samples from a subset of the Julesz ensemble by pasting texture patches from the sample texture. A key feature of our algorithm is that it can synthesize high-quality textures extremely fast. On a mid-level PC we can synthesize a 512 512 texture from a 64 64 sample in just 0.03 second. This algorithm has been tested through extensive experiments and we report sample results from our experiments.
Visual Learning by Integrating Descriptive and Generative Methods

This paper presents a mathematical framework for visual learning that integrates two popular statistical learning paradigms in the literature: I) Descriptive learning, such as Markov random fields and minimax entropy learning, and II) Generative learning, such as PCA, ICA, TCA, and HMM. We apply the integrated learning framework to texture modeling, and we assume that an observed texture image is generated by multiple layers of hidden stochastic processes with various texture elements called textons . Each texton is expressed as a window function like a mini-template or a wavelet, and each hidden stochastic process is a spatial pattern with a number of textons subject to affine transfomrations. The hidden layers are characterized by minimax entropy models, and they generate images by occlusion or linear addition. Thus given a raw input image, the learning framework achieves four goals: i) Computing the appearance of textons. ii) Inferring the hidden stochastic processes iii) Learning Gibbs models for each hidden stochastic process and iv) Verifying the learnt textons and models through random sampling. The integrated framework subsumes the minimax entropy learning paradigm and creates a richer class of probability models for visual patterns. Furthermore we show that the integration of descriptive and generative methods is a natural path of visual learning. We demonstrate the proposed framework and algorithms on many real images.
Example-based facial sketch generation with non-parametric sampling

In this paper, we present an example-based facial sketch system. Our system automatically generates a sketch from an input image, by learning from example sketches drawn with a particular style by an artist. There are two key elements in our system: a non-parametric sampling method and a flexible sketch model. Given an input image pixel and its neighborhood, the conditional distribution of a sketch point is computed by querying the examples and finding all similar neighborhoods. An "expected sketch image" is then drawn from the distribution to reflect the drawing style. Finally, facial sketches are obtained by incorporating the sketch model. Experimental results demonstrate the effectiveness of our techniques.
Learning in Gibbsian fields: how accurate and how fast can it be?

In this article, we present a unified framework for learning Gibbs models from training images. We identify two key factors that determine the accuracy and speed of learning Gibbs models: (1). Fisher information, and (2). The accuracy of Monte Carlo estimate for partition functions. We propose three new learning algorithms under the unified framework. (I). The maximum partial likelihood estimator. (II). The maximum patch likelihood estimator, and (III). The maximum satellite likelihood estimator. The first two algorithms can speed up the minimax entropy algorithm by about 2D times without losing much accuracy. The third one makes use of a set of known Gibbs models as references-dubbed "satellites" and can approximately estimate the minimax entropy model in the speed of 10 seconds.
Mathematical modeling of clutter: descriptive vs. generative models

In this article, we present two mathematical paradigms for clutter modeling. Both paradigms pose clutter modeling as a statistical inference problem, and pursue probabilistic models for characterizing observed training images. The two paradigms differ in the forms (or families) of models that they choose and in their philosophical assumptions on real world clutter patterns. The first paradigm studies descriptive models, such as Markov random field (MRF) models and the minimax entropy models (Zhu, Wu, and Mumford 1997). In this modeling paradigm, image features are first extracted from images, and statistics of these features are calculated. The latter define an image ensemble-called the Julesz ensemble which is an equivalence class where all images share the same feature statistics. For any large images from this ensemble, a local patch given its boundary condition is then Gibbs (or MRF) models. We shall review the recent conclusions about ensemble equivalence studied in (Wu, Zhu and Liu, 1999). The second paradigm studies generative model, such as the random collage model (Lee and Mumford, 1999). In contrast to a descriptive model, a generative model introduces hidden variables which are assumed to be the underlying causes producing the observed image. For example, trees and rock for clutter. The learning process makes inference about the hidden variables. We shall discuss a texton model for clutter and effective Markov chain Monte Carlo methods for stochastic inference. We shall also reveal the deep relationship between the two modeling paradigm.