14160695
Analysis and synthesis of textured motion: particles and waves
Natural scenes contain a wide range of textured motion phenomena which are characterized by the movement of a large amount of particle and wave elements, such as falling snow, wavy water, and dancing grass. In this paper, we present a generative model for representing these motion patterns and study a Markov chain Monte Carlo algorithm for inferring the generative representation from observed video sequences. Our generative model consists of three components. The first is a photometric model which represents an image as a linear superposition of image bases selected from a generic and overcomplete dictionary. The dictionary contains Gabor and LoG bases for point/particle elements and Fourier bases for wave elements. These bases compete to explain the input images and transfer them to a token (base) representation with an O(10/sup 2/)-fold dimension reduction. The second component is a geometric model which groups spatially adjacent tokens (bases) and their motion trajectories into a number of moving elements-called "motons". A moton is a deformable template in time-space representing a moving element, such as a falling snowflake or a flying bird. The third component is a dynamic model which characterizes the motion of particles, waves, and their interactions. For example, the motion of particle objects floating in a river, such as leaves and balls, should be coupled with the motion of waves. The trajectories of these moving elements are represented by coupled Markov chains. The dynamic model also includes probabilistic representations for the birth/death (source/sink) of the motons. We adopt a stochastic gradient algorithm for learning and inference. Given an input video sequence, the algorithm iterates two steps: 1) computing the motions and their trajectories by a number of reversible Markov chain jumps, and 2) learning the parameters that govern the geometric deformations and motion dynamics. Novel video sequences are synthesized from the learned models and, by editing the model parameters, we demonstrate the controllability of the generative model.
12345366
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.
122560265
Multigrid and multi-level Swendsen-Wang cuts for hierarchic graph partition
Many vision tasks can be formulated as partitioning an adjacency graph through optimizing a Bayesian posterior probability p defined on the partition-space. In this paper two approaches are proposed to generalize the Swendsen-Wang cut algorithm [A. Barbu and S.C. Zhu 2003] for sampling p. The first method is called multigrid SW-cut which runs SW-cut within a sequence of local "attentional" windows and thus simulates conditional probabilities of p in the partition space. The second method is called multi-level SW-cut which projects the adjacency graph into a hierarchical representation with each vertex in the high level graph corresponding to a sub-graph at the low level, and runs SW-cut at each level. Thus it simulates conditional probabilities of p at the higher level. Both methods are shown to observe the detailed balance equation and thus provide flexibilities in sampling the posterior probability p. We demonstrate the algorithms in image and motion segmentation with three levels (see Fig.1), and compare the speed improvement of the proposed methods.
398989
Parsing Images into Regions, Curves, and Curve Groups
In this paper, we present an algorithm for parsing natural images into middle level vision representations—regions, curves, and curve groups (parallel curves and trees). This algorithm is targeted for an integrated solution to image segmentation and curve grouping through Bayesian inference. The paper makes the following contributions. (1) It adopts a layered (or 2.1D-sketch) representation integrating both region and curve models which compete to explain an input image. The curve layer occludes the region layer and curves observe a partial order occlusion relation. (2) A Markov chain search scheme Metropolized Gibbs Samplers (MGS) is studied. It consists of several pairs of reversible jumps to traverse the complex solution space. An MGS proposes the next state within the jump scope of the current state according to a conditional probability like a Gibbs sampler and then accepts the proposal with a Metropolis-Hastings step. This paper discusses systematic design strategies of devising reversible jumps for a complex inference task. (3) The proposal probability ratios in jumps are factorized into ratios of discriminative probabilities. The latter are computed in a bottom-up process, and they drive the Markov chain dynamics in a data-driven Markov chain Monte Carlo framework. We demonstrate the performance of the algorithm in experiments with a number of natural images.
122817250
Modeling complex motion by tracking and editing hidden Markov graphs
We propose a generative model for representing complex motion, such as wavy river, dancing fire and dangling cloth. Our generative method consists of four components: (1) A photometric model using primal sketch[8] which transfers an image into an attribute graph representation. Each vertex of the graph is a scaled and oriented image patch selected from a dictionary. The graph connects and aligns these patches. (2) A geometric model which characterizes the deformation of the attribute graph. (3) A dynamic model, which specifies the motion dynamics of these vertices (patches) and their interactions in the form of coupled Markov chains. (4) A topological model, which interprets the graph topological changes over time. We learn this generative model by a stochastic gradient algorithm implemented by Markov Chain Monte Carlo (MCMC) sampling. This method is shown to be effective in handling the topological changes of graphs. The correctness of the learned model is verified by the low-dimension reconstruction of the original image as well as by the realistic motion sequences it synthesized.
206590834
Composite Templates for Cloth Modeling and Sketching
Cloth modeling and recognition is an important and challenging problem in both vision and graphics tasks, such as dressed human recognition and tracking, human sketch and portrait. In this paper, we present a context sensitive grammar in an And-Or graph representation which will produce a large set of composite graphical templates to account for the wide variabilities of cloth configurations, such as T-shirts, jackets, etc. In a supervised learning phase, we ask an artist to draw sketches on a set of dressed people, and we decompose the sketches into categories of cloth and body components: collars, shoulders, cuff, hands, pants, shoes etc. Each component has a number of distinct subtemplates (sub-graphs). These sub-templates serve as leafnodes in a big And-Or graph where an And-node represents a decomposition of the graph into sub-configurations with Markov relations for context and constraints (soft or hard), and an Or-node is a switch for choosing one out of a set of alternative And-nodes (sub-configurations) - similar to a node in stochastic context free grammar (SCFG). This representation integrates the SCFG for structural variability and the Markov (graphical) model for context. An algorithm which integrates the bottom-up proposals and the topdown information is proposed to infer the composite cloth template from the image.
654543
A survey on wavelet applications in data mining
Recently there has been significant development in the use of wavelet methods in various data mining processes. However, there has been written no comprehensive survey available on the topic. The goal of this is paper to fill the void. First, the paper presents a high-level data-mining framework that reduces the overall process into smaller components. Then applications of wavelets for each component are reviewd. The paper concludes by discussing the impact of wavelets on data mining research and outlining potential future research directions and applications.
1527832
Document clustering with cluster refinement and model selection capabilities
In this paper, we propose a document clustering method that strives to achieve: (1) a high accuracy of document clustering, and (2) the capability of estimating the number of clusters in the document corpus (i.e. the model selection capability). To accurately cluster the given document corpus, we employ a richer feature set to represent each document, and use the Gaussian Mixture Model (GMM) together with the Expectation-Maximization (EM) algorithm to conduct an initial document clustering. From this initial result, we identify a set of discriminative featuresfor each cluster, and refine the initially obtained document clusters by voting on the cluster label of each document using this discriminative feature set. This self-refinement process of discriminative feature identification and cluster label voting is iteratively applied until the convergence of document clusters. On the other hand, the model selection capability is achieved by introducing randomness in the cluster initialization stage, and then discovering a value C for the number of clusters N by which running the document clustering process for a fixed number of times yields sufficiently similar results. Performance evaluations exhibit clear superiority of the proposed method with its improved document clustering and model selection accuracies. The evaluations also demonstrate how each feature as well as the cluster refinement process contribute to the document clustering accuracy.
5743908
A Probabilistic Model for Clustering Text Documents with Multiple Fields
We address the problem of clustering documents with multiple fields, such as scientific literature with the distinct fields: title, abstract, keywords, main text and references. By taking into consideration of the distinct word distributions of each field, we propose a new probabilistic model, Field Independent Clustering Model (FICM), for clustering documents with multiple fields. The benefits of FICM come not only from integrating the discrimination abilities of each field but also from the power of selecting the most suitable component probabilistic model for each field. We examined the performance of FICM on the problem of clustering biomedical documents with three fields (title, abstract and MeSH). From the genomics track data of TREC 2004 and TREC 2005, we randomly generated 60 datasets where the number of classes in each dataset ranged from 3 to 12. By applying the appropriate configuration of generative models for each field, FICM outperformed a classical multinomial model in 59 out of the total 60 datasets, of which 47 were statistically significant at the 95% level, and FICM also outperformed a multivariate Bernoulli model in 52 out of the total 60 datasets, of which 36 were statistically significant at the 95% level.
570616
Least privilege and privilege deprivation: towards tolerating mobile sink compromises in wireless sensor networks
Mobile sinks are needed in many sensor network applications for efficient data collection, data querying, localized sensor reprogramming, identifying and revoking compromised sensors, and other network maintenance. Employing mobile sinks however raises a new security challenge: if a mobile sink is given too many privileges, it will become very attractive for attack and compromise. Using a compromised mobile sink, an adversary may easily bring down or even take over the sensor network. Thus, security mechanisms that can tolerate mobile sink compromises are essential. In this paper, based on the principle of least privilege, we first propose several efficient schemes to restrict the privilege of a mobile sink without impeding its capability of carrying out any authorized operations for an assigned task. To further reduce the possible damages caused by a compromised mobile sink, we then propose efficient message forwarding schemes for depriving the privilege assigned to a compromised mobile sink immediately after its compromise has been detected. Through detailed analysis and simulations, we show that our schemes are secure and efficient, and are highly practical for sensor networks consisting of the current generation of sensors.
38761790
Social Choice For Data Fusion
Social choice theory is the study of decision theory on how to aggregate separate preferences into group's rational preference. It has wide applications, especially on the design of voting rules, and brings far-reaching influence on the development of modern political science and welfare economics. With the advent of the information age, social choice theory finds its up-to-date application on designing effective Metasearch engines. Metasearch engines provide effective searching by combining the results of multiple source search engines that make use of diverse models and techniques. In this work, we analyze social choice algorithms in a graph-theoretic approach. In addition to classical social choice algorithms, such as Borda and Condorcet, we study one special type of social choice algorithms, elimination voting, to tackle Metasearch problem. Some new algorithms are proposed and examined in the fusion experiment on TREC data. It shows that these elimination voting algorithms achieve satisfied performance when compared with Borda algorithm.