By lifting the ReLU function into a higher dimensional space, we develop a smooth multi-convex formulation for training feed-forward deep neural networks (DNNs). This allows us to develop a block coordinate descent (BCD) training algorithm consisting of a sequence of numerically well-behaved convex optimizations. Using ideas from proximal point methods in convex analysis, we prove that this BCD algorithm will converge globally to a stationary point with R-linear convergence rate of order one. In experiments with the MNIST database, DNNs trained with this BCD algorithm consistently yielded better test-set error rates than identical DNN architectures trained via all the stochastic gradient descent (SGD) variants in the Caffe toolbox.

We propose a novel and an efficient method for reconstructing the 3D arrangement of lines extracted from a single image, using vanishing points, orthogonal structure, and an optimization procedure that considers all plausible connectivity constraints between lines. Line detection identifies a large number of salient lines that intersect or nearly intersect in an image, but relatively a few of these apparent junctions correspond to real intersections in the 3D scene. We use linear programming (LP) to identify a minimal set of least-violated connectivity constraints that are sufficient to unambiguously reconstruct the 3D lines. In contrast to prior solutions that primarily focused on well-behaved synthetic line drawings with severely restricting assumptions, we develop an algorithm that can work on real images. The algorithm produces line reconstruction by identifying 95% correct connectivity constraints in York Urban database, with a total computation time of 1 second per image.

Many image processing and computer vision problems can be solved as quadratic programs in the nonnegative cone. This paper develops a provably convergent multiplicative update that has a simple form and is amenable to fine-grained data parallelism. Classic algorithms for deblurring, matrix factorization, and tomography are recovered as special cases. This paper also demonstrates applications to super-resolution, labeling and segmentation.

View synthesis is an essential function for a number of 3D video applications including free-viewpoint navigation and view generation for auto-stereoscopic displays. Depth Image Based Rendering (DIBR) techniques are typically applied for this purpose. However, the quality of the rendered views is very sensitive to the quality of the depth image. In this paper, a novel trellis-based view synthesis framework is proposed to overcome the above limitations in depth images and reduce artifacts in the rendered picture. Our results demonstrate that the proposed approach offers visible improvements in rendering quality compared to existing view synthesis techniques.

This paper investigates the problem of geo-localization in GPS challenged urban canyons using only skylines. Our proposed solution takes a sequence of upward facing omnidirectional images and coarse 3D models of cities to compute the geo-trajectory. The camera is oriented upwards to capture images of the immediate skyline, which is generally unique and serves as a fingerprint for a specific location in a city. Our goal is to estimate global position by matching skylines extracted from omni-directional images to skyline segments from coarse 3D city models. Under day-time and clear sky conditions, we propose a sky-segmentation algorithm using graph cuts for estimating the geo-location. In cases where the skyline gets affected by partial fog, night-time and occlusions from trees, we propose a shortest path algorithm that computes the location without prior sky detection. We show compelling experimental results for hundreds of images taken in New York, Boston and Tokyo under various weather and lighting conditions (daytime, foggy dawn and night-time).

We introduce a method for fully automatic touch-up of face images by making inferences about the structure of the scene and undesirable textures in the image. A distribution over image segmentations and labelings is computed via a conditional random field; this distribution controls the application of various local image transforms to regions in the image. Parameters governing both the labeling and transforms are jointly optimized w.r.t. a training set of before-and-after example images. One major advantage of our formulation is the ability to approximately marginalize over all possible labelings and thus exploit much or most of the information in the distribution; this yields better results than MAP inference. We demonstrate with a system that is trained to correct red-eye, reduce specularities, and remove acne and other blemishes from faces, showing results with test images scavenged from acne-themed internet message boards.

Given a wireless network where each link undergoes small-scale (Rayleigh) fading, we consider the problem of routing a message from a source node to a target node while minimizing energy or power expenditure given a fixed time budget, or vice versa. Given instantaneous channel state information, we develop tight hyperbolic bounds on the quantities of interest and solve the related optimizations in closed form or via lightweight computations. If only average channel state information is available, probabilistical performance measures must be introduced. We therefore develop another set of bounds that supports resource-optimal routing with a guaranteed success probability. Our results rest on novel formulations and solution methods for hyperbolic convex programs and, more generally, nonlinear multicriterion combinatorial optimization.

In many wireless ad-hoc networks it is important to find a route that delivers a message to the destination within a certain deadline (delay constraint). We propose to identify such routes based on average channel state information (CSI) only, since this information can be distributed more easily over the network. Such cases allow probabilistic QoS guarantees i.e., we maximize and report the probability of on-time delivery. We develop a convolution-free lower bound on probability of on-time arrival, and a scheme to rapidly identify a path that maximizes this bound. This analysis is motivated by a class of infinite variance subexponential distributions whose properties preclude the use of deviation bounds and convolutional schemes. The bound then forms the basis of an algorithm that finds routes that give probabilistic delay guarantees. Simulations demonstrate that the algorithm performs better than shortest-path algorithm based on statistics of path loss or CSI.

The nonrigid structure-from-motion (NSFM) problem seeks to recover a sequence of 3D shapes, shape articulation parameters, and camera view matrices from 2D correspondence data. Factorization approaches relate the principal subspaces of the data matrix to the desired parameters through a linear corrective transform. Current methods for finding this transform are heuristic or depend on strong assumptions about the data. We show how to solve for this transform by directly minimizing deviation from the required orthogonal structure of the projection/articulation matrix. The solution is exact for noiseless data and an order of magnitude more accurate than state-of-the-art methods for noisy data.

We model consumer behavior such as web browsing, shopping, and entertainment choices as random walks on a weighted association graph. The graph is derived from a relational database that links products, consumers, and attributes such as product categories, consumer demographics, market segments, etc. The Markov chain that describes this walk amalgamates consumer behavior over the whole population; individuals are distinguished by their current state in the chain. We develop a geometrization of the chain that furnishes a key similarity measure for information retrieval—the cosine (correlation) angle between two states. Empirically, this proves to be highly predictive of future choices made by individuals, and is useful for recommending and semi-supervised classification. This statistic is obtained through a sparse matrix inversion, and we develop approximation strategies that make this practical for very large Markov chains. These methods also make it practical to compute recommendations to maximize long-term profit.

Face Transfer is a method for mapping videorecorded performances of one individual to facial animations of another. It extracts visemes (speech-related mouth articulations), expressions, and three-dimensional (3D) pose from monocular video or film footage. These parameters are then used to generate and drive a detailed 3D textured face mesh for a target identity, which can be seamlessly rendered back into target footage. The underlying face model automatically adjusts for how the target performs facial expressions and visemes. The performance data can be easily edited to change the visemes, expressions, pose, or even the identity of the target---the attributes are separably controllable. This supports a wide variety of video rewrite and puppetry applications.Face Transfer is based on a multilinear model of 3D face meshes that separably parameterizes the space of geometric variations due to different attributes (e.g., identity, expression, and viseme). Separability means that each of these attributes can be independently varied. A multilinear model can be estimated from a Cartesian product of examples (identities × expressions × visemes) with techniques from statistical analysis, but only after careful preprocessing of the geometric data set to secure one-to-one correspondence, to minimize cross-coupling artifacts, and to fill in any missing examples. Face Transfer offers new solutions to these problems and links the estimated model with a face-tracking algorithm to extract pose, expression, and viseme parameters.

Twenty years ago it was not obvious that subspace approximations would be such a successful representation for faces and other phenomena whose measurement-space manifolds exhibit clear nonlinearities. Now PCA is ubiquitous in computer vision and, although its globally linear view of the data manifold can be a liability as systems scale up, it is not obvious that one can reliably construct a better nonlinear data model. This question motivates a rapidly growing literature of graph-theoretic and tensorial approximations that view the data manifold as linear only in locales and slices, respectively. These limited-linearity ”submanifold methods” offer much richer descriptions of the data manifold, and may ultimately replace subspace methods in computer vision. First, problems with suboptimality, solution instability, and sample complexity must be overcome. Some of the obstacles to ”industrial-strength” manifold modeling are discussed, and some methods that offer significant improvements in robustness and accuracy are introduced which eschew the common assumptions about the manifold geometry in particular, a generalization of PCA that can exactly recover the intrinsic coordinate systems of a significant class of nowhere-linear manifolds. Connecting these data models to image analysis and synthesis algorithms is only slightly more complicated than using subspace methods. Some applications to tracking, recognition, and editing of objects and people in video are demonstrated. BMVC 2004 doi:10.5244/C.18.2

We consider the problem of optimally parking empty cars in an elevator group so as to anticipate and intercept the arrival of new passengers and minimize their waiting times. Two solutions are proposed, for the down-peak and up-peak traffic patterns. We demonstrate that matching the distribution of free cars to the arrival distribution of passengers is sufficient to produce savings of up to 80% in down-peak traffic. Since this approach Is not useful for the much harder case of up-peak traffic, we propose a solution based on the representation of the elevator system as a Markov decision process (MDP) model with relatively few aggregated states, and determination of the optimal parking policy by means of dynamic programming on the MDP model.

Spectral methods for nonlinear dimensionality reduction (NLDR) impose a neighborhood graph on point data and compute eigenfunctions of a quadratic form generated from the graph. We introduce a more general and more robust formulation of NLDR based on the singular value de- composition (SVD). In this framework, most spectral NLDR principles can be recovered by taking a subset of the constraints in a quadratic form built from local nullspaces on the manifold. The minimax formulation also opens up an interesting class of methods in which the graph is “dec- orated” with information at the vertices, offering discrete or continuous maps, reduced computational complexity, and immunity to some solu- tion instabilities of eigenfunction approaches. Apropos, we show almost all NLDR methods based on eigenvalue decompositions (EVD) have a so- lution instability that increases faster than problem size. This pathology can be observed (and corrected via the minimax formulation) in problems as small as N < 100 points. 1 Nonlinear dimensionality reduction (NLDR) Spectral NLDR methods are graph embedding problems where a set of N points X .= [x1,··· ,xN] ∈ RD×N sampled from a low-dimensional manifold in a ambient space RD is reparameterized by imposing a neighborhood graph G on X and embedding the graph with minimal distortion in a “parameterization” space Rd, d < D. Typically the graph is sparse and local, with edges connecting points to their immediate neighbors. The embedding must keep these edges short or preserve their length (for isometry) or angles (for conformality). The graph-embedding problem was first introduced as a least-squares problem by Tutte [1], and as an eigenvalue problem by Fiedler [2]. The use of sparse graphs to generate metrics for least-squares problems has been studied intensely in the following three decades (see [3]). Modern NLDR methods use graph constraints to generate a metric in a space of embed- dings RN. Eigenvalue decomposition (EVD) gives the directions of least or greatest variance under this metric. Typically a subset of d extremal eigenvectors gives the embedding of N points in Rd parameterization space. This includes the IsoMap family [4], the locally linear embedding (LLE) family [5,6], and Laplacian methods [7,8]. Using similar methods, the Automatic Alignment [6] and Charting [9] algorithms embed local subspaces instead of points, and by combining subspace projections thus obtain continuous maps between RD and Rd. This paper introduces a general algebraic framework for computing optimal embeddings directly from graph constraints. The aforementioned methods can can be recovered as spe- cial cases. The framework also suggests some new methods with very attractive properties, including continuous maps, reduced computational complexity, and control over the degree of conformality/isometry in the desired map. It also eliminates a solution instability that is intrinsic to EVD-based approaches. A perturbational analysis quantifies the instability. 2 Minimax theorem for graph embeddings We begin with neighborhood graph specified by a nondiagonal weighted adjacency matrix M ∈ RN×N that has the data-reproducing property XM = X (this can be relaxed to XM ≈ X in practice). The graph-embedding and NLDR literatures offer various constructions of M, each appropriate to different sets of assumptions about the original embedding and its sampling X (e.g., isometry, local linearity, noiseless samples, regular sampling, etc.). Typically Mi j 6= 0 if points i, j are nearby on the intrinsic manifold and |Mi j| is small or zero otherwise. Each point is taken to be a linear or convex combination of its neighbors, and thus M specifies manifold connectivity in the sense that any nondegenerate embedding Y that satisfies YM ≈ Y with small residual kYM− YkF will preserve this connectivity and the structure of local neighborhoods. For example, in barycentric embeddings, each point is the average of its neighbors and thus Mi j = 1/k if vertex i is connected to vertex j (of degree k). We will also consider three optional constraints on the embedding : A null-space restriction, where the solution must be outside to the column-space of C ∈ RN×M, M < N. For example, it is common to stipulate that the solution Y be centered, i.e., YC = 0 for C = 1, the constant vector. A basis restriction, where the solution must be a linear combination of the rows of basis Z ∈ RK×N, K ≤ N. This can be thought of as information placed at the vertices of the graph that serves as example inputs for a target NLDR function. We will use this to construct dimension-reducing radial basis function networks. A metric S ∈ RN×N that determines how error is distributed over the points. For example, it might be important that boundary points have less error. We assume is symmetric positive definite and has factorization S = AA> (e.g., A could that S be a Cholesky factor of S). In most settings, the optional matrices will default to the identity matrix. In this context, we define the per-dimension embedding error of row-vector yi ∈ rows(Y) to be

The singular value decomposition (svd) is fundamental to many data modeling/mining algorithms, but svd algorithms typically have quadratic complexity and require random access to complete data sets. This is problematic in most data mining settings. We detail a family of sequential update rules for adding data to a “thin” svd data model, revising or removing data already incorporated into the model, and adjusting the model when the data-generating process exhibits nonstationarity. We also leverage the svd to estimate the most probable completion of incomplete data. We use these methods to model data streams describing tables of consumer×product ratings, where fragments of rows and columns arrive in random order and individual table entries are arbitrarily added, revised, or retracted at any time. These purely online rules have very low time complexity and require a data stream cache no larger than a single user's ratings. We demonstrate this scheme in an interactive graphical movie recommender that predicts and displays ratings/rankings of thousands of movie titles in real-time as a user adjusts ratings of a small arbitrary set of probe movies. The system “learns” as it is used by revising the svd in response to user ratings. Users can asynchronously join, add ratings, add movies, revise ratings, get recommendations, and delete themselves from the model.

We present a generative model for isotropic bidirectional reflectance distribution functions (BRDFs) based on acquired reflectance data. Instead of using analytical reflectance models, we represent each BRDF as a dense set of measurements. This allows us to interpolate and extrapolate in the space of acquired BRDFs to create new BRDFs. We treat each acquired BRDF as a single high-dimensional vector taken from a space of all possible BRDFs. We apply both linear (subspace) and non-linear (manifold) dimensionality reduction tools in an effort to discover a lower-dimensional representation that characterizes our measurements. We let users define perceptually meaningful parametrization directions to navigate in the reduced-dimension BRDF space. On the low-dimensional manifold, movement along these directions produces novel but valid BRDFs.

We construct a nonlinear mapping from a high-dimensional sample space to a low-dimensional vector space, effectively recovering a Cartesian coordinate system for the manifold from which the data is sampled. The mapping preserves local geometric relations in the manifold and is pseudo-invertible. We show how to estimate the intrinsic dimensionality of the manifold from samples, decompose the sample data into locally linear low-dimensional patches, merge these patches into a single low- dimensional coordinate system, and compute forward and reverse map- pings between the sample and coordinate spaces. The objective functions are convex and their solutions are given in closed form. 1 Nonlinear dimensionality reduction (NLDR) by charting Charting is the problem of assigning a low-dimensional coordinate system to data points in a high-dimensional sample space. It is presumed that the data lies on or near a low- dimensional manifold embedded in the sample space, and that there exists a 1-to-1 smooth nonlinear transform between the manifold and a low-dimensional vector space. The data- modeler’s goal is to estimate smooth continuous mappings between the sample and co- ordinate spaces. Often this analysis will shed light on the intrinsic variables of the data- generating phenomenon, for example, revealing perceptual or configuration spaces. Our goal is to find a mapping—expressed as a kernel-based mixture of linear projections— that minimizes information loss about the density and relative locations of sample points. This constraint is expressed in a posterior that combines a standard gaussian mixture model (GMM) likelihood function with a prior that penalizes uncertainty due to inconsistent pro- jections in the mixture. Section 3 develops a special case where this posterior is unimodal and maximizable in closed form, yielding a GMM whose covariances reveal a patchwork of overlapping locally linear subspaces that cover the manifold. Section 4 shows that for this (or any) GMM and a choice of reduced dimension d, there is a unique, closed-form solution for a minimally distorting merger of the subspaces into a d-dimensional coordinate space, as well as an reverse mapping defining the surface of the manifold in the sample space. The intrinsic dimensionality d of the data manifold can be estimated from the growth pro- cess of point-to-point distances. In analogy to differential geometry, we call the subspaces “charts” and their merger the “connection.” Section 5 considers example problems where these methods are used to untie knots, unroll and untwist sheets, and visualize video data. 1.1 Background Topology-neutral NLDR algorithms can be divided into those that compute mappings, and those that directly compute low-dimensional embeddings. The field has its roots in map- ping algorithms: DeMers and Cottrell [3] proposed using auto-encoding neural networks with a hidden layer “ bottleneck,” effectively casting dimensionality reduction as a com- pression problem. Hastie defined principal curves [ 5] as nonparametric 1D curves that pass through the center of “ nearby” data points. A rich literature has grown up around properly regularizing this approach and extending it to surfaces. Smola and colleagues [10] analyzed the NLDR problem in the broader framework of regularized quantization methods. More recent advances aim for embeddings: Gomes and Mojsilovic [4] treat manifold com- pletion as an anisotropic diffusion problem, iteratively expanding points until they connect to their neighbors. The ISOMAP algorithm [12] represents remote distances as sums of a trusted set of distances between immediate neighbors, then uses multidimensional scaling to compute a low-dimensional embedding that minimally distorts all distances. The locally linear embedding algorithm (LLE) [9] represents each point as a weighted combination of a trusted set of nearest neighbors, then computes a minimally distorting low-dimensional barycentric embedding. They have complementary strengths: ISOMAP handles holes well but can fail if the data hull is nonconvex [12]; and vice versa for LLE [9]. Both offer em- beddings without mappings. It has been noted that trusted-set methods are vulnerable to noise because they consider the subset of point-to-point relationships that has the lowest signal-to-noise ratio; small changes to the trusted set can induce large changes in the set of constraints on the embedding, making solutions unstable [1]. In a return to mapping, Roweis and colleagues [8] proposed global coordination— learning a mixture of locally linear projections from sample to coordinate space. They constructed a posterior that penalizes distortions in the mapping, and gave a expectation-maximization (EM) training rule. Innovative use of variational methods highlighted the difficulty of even hill-climbing their multimodal posterior. Like [2, 7, 6, 8], the method we develop below is a decomposition of the manifold into locally linear neighborhoods. It bears closest relation to global coordination [8], although by a different construction of the problem, we avoid hill-climbing a spiky posterior and instead develop a closed-form solution. 2 Estimating locally linear scale and intrinsic dimensionality We begin with matrix of sample points Y : = [y1; (cid:1) (cid:1) (cid:1) ;yN]; yn 2 RD populating a D- dimensional sample space, and a conjecture that these points are samples from a man- ifold M of intrinsic dimensionality d < D. We seek a mapping onto a vector space G(Y) ! X : = [x1; (cid:1) (cid:1) (cid:1) ;xN]; xn 2 Rd and 1-to-1 reverse mapping G(cid:0)1(X) ! Y such that local relations between nearby points are preserved (this will be formalized below). The map G should be non-catastrophic, that is, without folds: Parallel lines on the manifold in RD should map to continuous smooth non-intersecting curves in Rd. This guarantees that linear operations on X such as interpolation will have reasonable analogues on Y. Smoothness means that at some scale r the mapping from a neighborhood on M to Rd is effectively linear. Consider a ball of radius r centered on a data point and containing n(r) data points. The count n(r) grows as rd, but only at the locally linear scale; the grow rate is inflated by isotropic noise at smaller scales and by embedding curvature at larger scales. : To estimate r, we look at how the r-ball grows as points are added to it, tracking c(r) = d log n(r) log r. At noise scales, c(r) (cid:25) 1=D < 1=d, because noise has distributed points in all directions with equal probability. At the scale at which curvature becomes significant, c(r) < 1=d, because the manifold is no longer perpendicular to the surface of the ball, so the ball does not have to grow as fast to accommodate new points. At the locally linear scale, the process peaks at c(r) = 1=d, because points are distributed only in the directions of the manifold’s local tangent space. The maximum of c(r) therefore gives an estimate of both the scale and the local dimensionality of the manifold (see figure 1), provided that the ball hasn’t expanded to a manifold boundary— boundaries have lower dimension than d Scale behavior of a 1D manifold in 2-space samples noise scale locally linear scale curvature scale Point-count growth process on a 2D manifold in 3-space radial growth process 1D hypothesis 2D hypothesis 3D hypothesis

Nonrigid 3D structure-from-motion and 2D optical flow can both be formulated as tensor factorization problems. The two problems can be made equivalent through a noisy affine transform, yielding a combined nonrigid structure-from-intensities problem that we solve via structured matrix decompositions. Often the preconditions for this factorization are violated by image noise and deficiencies of the data visa-vis the sample complexity of the problem. Both issues are remediated with careful use of rank constraints, norm constraints, and integration over uncertainty in the intensity values, yielding novel solutions for SVD under uncertainty, factorization under uncertainty, nonrigid factorization, and subspace optical flow. The resulting integrated algorithm can track and reconstruct in 3D nonrigid surfaces having very little texture, for example the smooth parts of the face. Working with low-resolution low-texture "found video," these methods produce good tracking and 3D reconstruction results where prior algorithms fail.

We introduce linear methods for model-based tracking of nonrigid 3D objects and for acquiring such models from video. 3D motions and flexions are calculated directly from image intensities without information-lossy intermediate results. Measurement uncertainty is quantified and fully propagated through the inverse model to yield posterior mean (PM) and/or mode (MAP) pose estimates. A Bayesian framework manages uncertainty, accommodates priors, and gives confidence measures. We obtain highly accurate and robust closed-form estimators by minimizing information loss from non-reversible (inner-product and least-squares) operations, and, when unavoidable, performing such operations with the appropriate error norm. For model acquisition, we show how to refine a crude or generic model to fit the video subject. We demonstrate with tracking, model refinement, and super-resolution texture lifting from low-quality low-resolution video.

We approach the problem of stylistic motion synthesis by learning motion patterns from a highly varied set of motion capture sequences. Each sequence may have a distinct choreography, performed in a distinct sytle. Learning identifies common choreographic elements across sequences, the different styles in which each element is performed, and a small number of stylistic degrees of freedom which span the many variations in the dataset. The learned model can synthesize novel motion data in any interpolation or extrapolation of styles. For example, it can convert novice ballet motions into the more graceful modern dance of an expert. The model can also be driven by video, by scripts or even by noise to generate new choreography and synthesize virtual motion-capture in many styles.

Hidden Markov models (HMMs) have become the workhorses of the monitoring and event recognition literature because they bring to time-series analysis the utility of density estimation and the convenience of dynamic time warping. Once trained, the internals of these models are considered opaque; there is no effort to interpret the hidden states. We show that by minimizing the entropy of the joint distribution, an HMM's internal state machine can be made to organize observed activity into meaningful states. This has uses in video monitoring and annotation, low bit-rate coding of scene activity, and detection of anomalous behavior. We demonstrate with models of office activity and outdoor traffic, showing how the framework learns principal modes of activity and patterns of activity change. We then show how this framework can be adapted to infer hidden state from extremely ambiguous images, in particular, inferring 3D body orientation and pose from sequences of low-resolution silhouettes.

We show how to learn a concise, interpretable model of scene activity directly from optical flow. The model represents the principal routes and modes of movement in complex scenes such as pedestrian plazas and traffic intersections, and supports a variety of inferences about the observed activities, including annotation, prediction, and anomaly detection. The model takes the form of a novel hidden Markov model generalization that observes a variable number of datapoints per frame (time step). A monotonic entropy-optimizing algorithm determines the parameters and structure of this model, exploiting the duality between learning and compression to produce highly predictive and interpretable models. This approach discovers minimal models of coherent motions and their switching dynamics-without tracking or prior knowledge about the spatial or temporal structure of the scene.

We develop a computationally efficient framework for finding compact and highly accurate hidden-variable models via entropy minimization. The main results are: (1) an entropic prior that favors small, unambiguous, maximally structured models. (2) A prior balancing manipulation of Bayes' rule that allows one to gradually introduce or remove constraints in the course of iterative reestimation. (1) and (2) combined give the information-theoretic free energy of the model and the means to manipulate it. (3) Maximum a posteriori (MAP) estimators such that entropy optimization and deterministic annealing can be performed wholly within expectation maximization (EM). (4) Trimming tests that identify excess parameters whose removal will increase the posterior, thereby simplifying the model and preventing over-fitting. The end result is a fast and exact hill-climbing algorithm that mixes continuous and combinatoric optimization and evades sub-optimal equilibria. Examples are given using speech and language problems.

The mapping between 3D body poses and 2D shadows is fundamentally many-to-many and defeats regression methods, even with windowed context. We show how to learn a function between paths in the two systems, resolving ambiguities by integrating information over the entire length of a sequence. The basis of this function is a configural and dynamical manifold that summarizes the target system's behaviour. This manifold can be modeled from data with a hidden Markov model having special topological properties that we obtain via entropy minimization. Inference is then a matter of solving for the geodesic on the manifold that best explains the evidence in the cue sequence. We give a closed-form maximum a posteriori solution for geodesics through the learned density space, thereby obtaining optimal paths over the dynamical manifold. These methods give a completely general way to perform inference over time-series; in vision they support analysis, recognition, classification and synthesis of behaviours in linear time. We demonstrate with a prototype that infers 3D from monocular monochromatic sequences (e.g., back-subtractions), without using any articulatory body model. The framework readily accommodates multiple cameras and other sources of evidence such as optical flow or feature tracking.

Article Voice puppetry Share on Author: Matthew Brand MERL -- a Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL -- a Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile Authors Info & Claims SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniquesJuly 1999 Pages 21–28https://doi.org/10.1145/311535.311537Online:01 July 1999Publication History 249citation1,623DownloadsMetricsTotal Citations249Total Downloads1,623Last 12 Months60Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We introduce an entropic prior for multinomial parameter estimation problems and solve for its maximum a posteriori (MAP) estimator. The prior is a bias for maximally structured and minimally ambiguous models. In conditional probability models with hidden state, iterative MAP estimation drives weakly supported parameters toward extinction, effectively turning them off. Thus, structure discovery is folded into parameter estimation. We then establish criteria for simplifying a probabilistic model's graphical structure by trimming parameters and states, with a guarantee that any such deletion will increase the posterior probability of the model. Trimming accelerates learning by sparsifying the model. All operations monotonically and maximally increase the posterior probability, yielding structure-learning algorithms only slightly slower than parameter estimation via expectation-maximization and orders of magnitude faster than search-based structure induction. When applied to hidden Markov model training, the resulting models show superior generalization to held-out test data. In many cases the resulting models are so sparse and concise that they are interpretable, with hidden states that strongly correlate with meaningful categories.

We present algorithms for coupling and training hidden Markov models (HMMs) to model interacting processes, and demonstrate their superiority to conventional HMMs in a vision task classifying two-handed actions. HMMs are perhaps the most successful framework in perceptual computing for modeling and classifying dynamic behaviors, popular because they offer dynamic time warping, a training algorithm and a clear Bayesian semantics. However the Markovian framework makes strong restrictive assumptions about the system generating the signal-that it is a single process having a small number of states and an extremely limited state memory. The single-process model is often inappropriate for vision (and speech) applications, resulting in low ceilings on model performance. Coupled HMMs provide an efficient way to resolve many of these problems, and offer superior training speeds, model likelihoods, and robustness to initial conditions.

Manipulations are a significant subset of human gestures that are distinguished by the fact that their logic and meaning are particularly clear, being heavily constrained by physical causality. We present techniques and causal semantics for interpreting video of manipulation tasks such as disassembly. Psychologically-based causal constraints are used to detect meaningful changes in the integrity and motions of foreground segmented blobs; a small causal model of manipulation is used to disambiguate and parse these into a coherent account of video's action. The causal constraints are drawn from studies of infant perceptual development; as with infants, they precede and may possibly even bootstrap the ability to reliably segment still objects. Our implementation produces a script of the causal evolution of the scene-output that supports cartoon summary, automated editing, and higher-level reasoning.

A class of region growing algorithms based on an analogy to a mass suspended in a field of forces is presented. The mass represents the growing region, and the field represents the degree of concordance between local pixel values and the color characteristics of the region. The algorithms are particularly well suited to systems that are looking for specific simply-connected shapes in local areas of interest, for example, a rectangle of unknown size, elongation, or orientation. Comparing pseudophysical region growing with Hough transforms, it is shown that region growing has competitive space and time complexity, and that it does not require image preprocessing for boundaries.>

Vision should provide an explanation of the scene in terms of a causal semantics. The authors propose a characterization of what constitutes visual understanding. The cornerstone of the proposal is that visual understanding is fundamentally a matter of developing a causal explanation of the scene, i.e., of determining the causal significance of the elements in a scene, and the causal relationships among those elements. Simple, naive physical knowledge is used as the basis of a vertically integrated vision system that explains arbitrarily complex stacked block structures. The semantics provides a basis for controlling the application of visual attention, and forms a framework for the explanation that is generated. It is shown that the program sequentially explores scenes of complex blocks structures, identifies functional substructures such as arches and cantilevers, and develops an explanation of why the whole construction stands and the role of each block in its stability.>