5807357
Layered Dynamic Textures
A novel video representation, the layered dynamic texture (LDT), is proposed. The LDT is a generative model, which represents a video as a collection of stochastic layers of different appearance and dynamics. Each layer is modeled as a temporal texture sampled from a different linear dynamical system. The LDT model includes these systems, a collection of hidden layer assignment variables (which control the assignment of pixels to layers), and a Markov random field prior on these variables (which encourages smooth segmentations). An EM algorithm is derived for maximum-likelihood estimation of the model parameters from a training video. It is shown that exact inference is intractable, a problem which is addressed by the introduction of two approximate inference procedures: a Gibbs sampler and a computationally efficient variational approximation. The trade-off between the quality of the two approximations and their complexity is studied experimentally. The ability of the LDT to segment videos into layers of coherent appearance and dynamics is also evaluated, on both synthetic and natural videos. These experiments show that the model possesses an ability to group regions of globally homogeneous, but locally heterogeneous, stochastic dynamics currently unparalleled in the literature.
5663
Mixtures of dynamic textures
A dynamic texture is a linear dynamical system used to model a single video as a sample from a spatio-temporal stochastic process. In this work, we introduce the mixture of dynamic textures, which models a collection of videos consisting of different visual processes as samples from a set of dynamic textures. We derive the EM algorithm for learning a mixture of dynamic textures, and relate the learning algorithm and the dynamic texture mixture model to previous works. Finally, we demonstrate the applicability of the proposed model to problems that have traditionally been challenging for computer vision.
2599785
On measuring the change in size of pulmonary nodules
The pulmonary nodule is the most common manifestation of lung cancer, the most deadly of all cancers. Most small pulmonary nodules are benign, however, and currently the growth rate of the nodule provides for one of the most accurate noninvasive methods of determining malignancy. In this paper, we present methods for measuring the change in nodule size from two computed tomography image scans recorded at different times; from this size change the growth rate may be established. The impact of partial voxels for small nodules is evaluated and isotropic resampling is shown to improve measurement accuracy. Methods for nodule location and sizing, pleural segmentation, adaptive thresholding, image registration, and knowledge-based shape matching are presented. The latter three techniques provide for a significant improvement in volume change measurement accuracy by considering both image scans simultaneously. Improvements in segmentation are evaluated by measuring volume changes in benign or slow growing nodules. In the analysis of 50 nodules, the variance in percent volume change was reduced from 11.54% to 9.35% (p=0.03) through the use of registration, adaptive thresholding, and knowledge-based shape matching.
2717049
Supervised Learning of Semantic Classes for Image Annotation and Retrieval
A probabilistic formulation for semantic image annotation and retrieval is proposed. Annotation and retrieval are posed as classification problems where each class is defined as the group of database images labeled with a common semantic label. It is shown that, by establishing this one-to-one correspondence between semantic labels and semantic classes, a minimum probability of error annotation and retrieval are feasible with algorithms that are 1) conceptually simple, 2) computationally efficient, and 3) do not require prior semantic segmentation of training images. In particular, images are represented as bags of localized feature vectors, a mixture density estimated for each image, and the mixtures associated with all images annotated with a common semantic label pooled into a density estimate for the corresponding semantic class. This pooling is justified by a multiple instance learning argument and performed efficiently with a hierarchical extension of expectation-maximization. The benefits of the supervised formulation over the more complex, and currently popular, joint modeling of semantic label and visual feature distributions are illustrated through theoretical arguments and extensive experiments. The supervised formulation is shown to achieve higher accuracy than various previously published methods at a fraction of their computational cost. Finally, the proposed method is shown to be fairly robust to parameter tuning
5980281
Scaling an object-oriented system execution visualizer through sampling
Increasingly, applications are being built by combining existing software components. For the most part, a software developer can treat the components as black-boxes. However, for some tasks, such as when performance tuning, a developer must consider how the components are implemented and how they interact. In these cases, a developer may be able to perform the task more effectively by using dynamic information about how the system executes. In previous work, we demonstrated the utility of a tool, called AVID (Architectural VIsualization of Dynamics), that animates dynamic information in terms of developer-chosen architectural views. One limitation of this earlier work was that AVID relied on trace information collected about the system's execution; traces for even small parts of a system's execution can be enormous, limiting the duration of execution that can be considered. To enable AVID to scale to larger longer-running systems, we have been investigating the visualization and animation of sampled dynamic information. In this paper, we discuss the addition of sampling support to AVID, and we present two case studies in which we experimented with animating sampled dynamic information to help with performance tuning tasks.
5717035
Coarse-Grained Parallel Geometric Search
We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O((n/p)logn) local computation, andO((n/p)logp) memory per processor, assumingn/p?p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires onlyO(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl.6(1996), 487?506), our algorithm is based on a distributed implementation of segment trees which are of sizeO(nlogn). This paper improves onop. cit.in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require onlyO((n/p)logn) local computation instead ofO(logp*(n/p)logn). (3) The algorithms require onlyO((n/p)logp) local memory instead ofO((n/p)logn).
17099314
A graph-theoretical analysis of multicast authentication
Message authentication is considered as a serious bottleneck to multicast security, particular for stream-type of traffic. The technique of hash chaining/signature amortization has been proposed in many schemes for stream authentication, with or without multicast settings. However, none of them is optimal. They either have a large packet overhead or are not robust to packet loss. Some even have a large receiver delay or require a large receiver buffer size. These schemes are constructed by trial-and-error methods. There lack tools to evaluate and compare their performances. There is no systematic way to construct these schemes either In this paper, we introduce the notion of dependence-graphs which links these hash-chained authentication schemes to the well-known graph theory, and provides an effective analytical tool. Many important metrics of a hash-chained authentication scheme can be readily and easily determined from its dependence-graph. As well, a dependence-graph demonstrates design tradeoff and provides insights into optimizing hash-chained schemes.
968718
Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs
In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and the bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining whether a graph G is bipartite, and (2) determining whether a bipartite graph G is convex. 
 
Our algorithms require O(log p) and O(log2 p) communication rounds, respectively, and linear sequential work per round on a CGM with p processors and N/p local memory per processor, N=|G|. The algorithms assume that N/p ≥ pƐ for some fixed Ɛ > 0, which is true for all commercially available multiprocessors. Our results imply BSP algorithms with O(log p) and O(log2 p) supersteps, respectively, O(g log(p)N/p) communication time, and O(log(p)N/p) local computation time. 
 
Our algorithm for determining whether a bipartite graph is convex includes a novel, coarse grained parallel, version of the PQ tree data structure introduced by Booth and Lueker. Hence, our algorithm also solves, with the same time complexity as indicated above, the problem of testing the consecutive-ones property for (0, 1) matrices as well as the chordal graph recognition problem. These, in turn, have numerous applications in graph theory, DNA sequence assembly, database theory, and other areas.
41263946
Coarse Grained Parallel Graph Planarity Testing
We present a coarse grained parallel algorithm for planarity testing and planar embedding. The algorithm requires O(log p) communication rounds and linear sequential work per round. It assumes that the local memory per processor, N=p, is larger than p for some xed > 0. This assumption is true for all commercially available multiprocessors. Our result implies a BSP algorithm with O(log p) supersteps, O(g log(p) p ) communication, and O(log(p) p ) local computation. Our algorithm is based on the general structure of a previous PRAM method presented by Klein, using a parallel implementation of PQ-trees. The main contribution of this paper lies in the study of many of the individual PRAM steps that are very inefcient on existing commercial parallel machines. We present non-trivial, eÆcient, CGM implementations of the various parts of the overall strategy proposed by Klein. Our main result is a parallel planarity testing algorithm which is much more practical and eÆcient on commercially available multi-