16862069
Progressive geometry compression for meshes
A novel progressive geometry compression scheme is presented in this paper. In this scheme, a mesh is represented as a base mesh followed by some groups of vertex split operations using an improved simplification method in which each level of the mesh can be refined into the next level by carrying out a group of vertex split operations in any order. Consequently, the progressive mesh (PM) representation can be effectively encoded by permuting the vertex split operations in each group. Meanwhile, a geometry predictor using the Laplacian operator is designed to predict each new vertex position using its neighbours. The correction is quantized and encoded using a Huffman coding scheme. Experimental results show that our algorithm obtains higher compression ratios than previous work. It is very suitable for the progressive transmission of geometric models over the Internet.
5676224
All-Frequency Precomputed Radiance Transfer for Glossy Objects
We introduce a method based on precomputed radiance transfer (PRT) that allows interactive rendering of glossy surfaces and includes shadowing effects from dynamic, "all-frequency" lighting. Specifically, source lighting is represented by a cube map at resolution nL = 6 × 32 × 32. We present a novel PRT formulation which factors glossy BRDFs into purely view-dependent and light-dependent parts, achieving reasonable accuracy with only m=10 dimensional factors. We then tabulate an m × nL transfer matrix at each surface vertex as a preprocess, representing the object's response to this lighting. Because this surface signal is so high-dimensional, reducing m is crucial for making practical both the preprocessing and run-time. To compress the transfer matrices, we divide the cube map into 24 lighting segments and apply the Haar wavelet basis in each segment to provide sensible quantization. We also apply clustered principal component analysis (CPCA) to each PRT segment to approximate it as a linear combination of a few (n=16) representative transfer matrices within a small set of clusters over the surface. This exploits spatial coherence to compress very effectively. Most important, it maintains fast rendering rates with 2-3 orders of magnitude more lighting coefficients than previous methods, which increases accuracy and avoids temporal artifacts in high-frequency lighting environments. We demonstrate interactive performance (1-5Hz) on models having up to 50,000 vertices.
2304584
Directional histogram model for three-dimensional shape similarity
In this paper, we propose a novel shape representation we call directional histogram model (DHM). It captures the shape variation of an object and is invariant to scaling and rigid transforms. The DHM is computed by first extracting a directional distribution of thickness histogram signatures, which are translation invariant. We show how the extraction of the thickness histogram distribution can be accelerated using conventional graphics hardware. Orientation invariance is achieved by computing the spherical harmonic transform of this distribution. Extensive experiments show that the DHM is capable of high discrimination power and is robust to noise.
8994921
Large mesh deformation using the volumetric graph Laplacian
We present a novel technique for large deformations on 3D meshes using the volumetric graph Laplacian. We first construct a graph representing the volume inside the input mesh. The graph need not form a solid meshing of the input mesh's interior; its edges simply connect nearby points in the volume. This graph's Laplacian encodes volumetric details as the difference between each point in the graph and the average of its neighbors. Preserving these volumetric details during deformation imposes a volumetric constraint that prevents unnatural changes in volume. We also include in the graph points a short distance outside the mesh to avoid local self-intersections. Volumetric detail preservation is represented by a quadric energy function. Minimizing it preserves details in a least-squares sense, distributing error uniformly over the whole deformed mesh. It can also be combined with conventional constraints involving surface positions, details or smoothness, and efficiently minimized by solving a sparse linear system.We apply this technique in a 2D curve-based deformation system allowing novice users to create pleasing deformations with little effort. A novel application of this system is to apply nonrigid and exaggerated deformations of 2D cartoon characters to 3D meshes. We demonstrate our system's potential with several examples.
7819313
Constrained Fairing for Meshes
In this paper, we present a novel fairing algorithm for the removal of noise from uniform triangular meshes without shrinkage and serious distortion. The key feature of this algorithm is to keep all triangle centers invariant at each smoothing step by including some constraints in the energy minimization functional. The constrained functional is then minimized efficiently using an iterative method. Further, we apply this smoothing technique to a multiresolution representation to remove arbitrary levels of detail. A volume-preserving decimation algorithm is presented to generate the multiresolution representation. The experimental results demonstrate the combined algorithm's stability and efficiency.
11755901
Interactive mesh deformation with pseudo material effects
This paper presents a novel interactive mesh deformation method that can achieve various dynamic material effects, including elastic membrane and cloth effects. In our framework, a mesh is encoded by some differential quantities based on edge length and dihedral angle; and the deformation is formulated as a least square problem for preserving the edge length and dihedral angle via the differential quantities. In order to obtain anisotropic material effects, we further propose an edge-weighting scheme based on a user-specified vector field. To avoid specifying the local transformations, we set up an iterative scheme for solving the deformation. At last, several examples are presented to show that our approach can interactively generate visually pleasing deformations. Copyright © 2006 John Wiley & Sons, Ltd.
1063503
Mutual anonymous overlay multicast
Multicast services are demanded by a variety of applications. Many applications require anonymity during their communication. However, there has been very little work on anonymous multicasting and such services are not available yet. Due to the fundamental differences between multicast and unicast, the solutions proposed for anonymity in unicast communications cannot be directly applied to multicast applications. In this paper we define the anonymous multicast system, and propose a mutual anonymous multicast (MAM) protocol including the design of a unicast mutual anonymity protocol and construction and optimization of an anonymous multicast tree. MAM is self-organizing and completely distributed. We define the attack model in an anonymous multicast system and analyze the anonymity degree. We also evaluate the performance of MAM by comprehensive simulations.
9148979
Face detection using spectral histograms and SVMs
We present a face detection method using spectral histograms and support vector machines (SVMs). Each image window is represented by its spectral histogram, which is a feature vector consisting of histograms of filtered images. Using statistical sampling, we show systematically the representation groups face images together; in comparison, commonly used representations often do not exhibit this necessary and desirable property. By using an SVM trained on a set of 4500 face and 8000 nonface images, we obtain a robust classifying function for face and nonface patterns. With an effective illumination-correction algorithm, our system reliably discriminates face and nonface patterns in images under different kinds of conditions. Our method on two commonly used data sets give the best performance among recent face-detection ones. We attribute the high performance to the desirable properties of the spectral histogram representation and good generalization of SVMs. Several further improvements in computation time and in performance are discussed.
17314700
Propagating uncertainty in microarray data analysis
Microarray technology is associated with many sources of experimental uncertainty. In this review we discuss a number of approaches for dealing with this uncertainty in the processing of data from microarray experiments. We focus here on the analysis of high-density oligonucleotide arrays, such as the popular Affymetrix GeneChip array, which contain multiple probes for each target. This set of probes can be used to determine an estimate for the target concentration and can also be used to determine the experimental uncertainty associated with this measurement. This measurement uncertainty can then be propagated through the downstream analysis using probabilistic methods. We give examples showing how these credibility intervals can be used to help identify differential expression, to combine information from replicated experiments and to improve the performance of principal component analysis.
16397904
A suite of web-based programs to search for transcriptional regulatory motifs
The identification of regulatory motifs is important for the study of gene expression. Here we present a suite of programs that we have developed to search for regulatory sequence motifs: (i) BioProspector, a Gibbs-sampling-based program for predicting regulatory motifs from co-regulated genes in prokaryotes or lower eukaryotes; (ii) CompareProspector, an extension to BioProspector which incorporates comparative genomics features to be used for higher eukaryotes; (iii) MDscan, a program for finding protein-DNA interaction sites from ChIP-on-chip targets. All three programs examine a group of sequences that may share common regulatory motifs and output a list of putative motifs as position-specific probability matrices, the individual sites used to construct the motifs and the location of each site on the input sequences. The web servers and executables can be accessed at http://seqmotifs.stanford.edu.
426496
Freeze: engineering a fast repeater insertion solver for power minimization using the ellipsoid method
This paper presents a novel repeater insertion algorithm for the power minimization of realistic interconnect trees under given timing budgets. Our algorithm judiciously combines a local optimizer based on the dynamic programming technique and a global search engine using the ellipsoid method. As a result, our approach is capable of producing high-quality solutions at a very fast speed. Furthermore, our scheme is robust and does not need any manual tuning of the iteration-control parameters. We have developed a repeater insertion tool, called Freeze, using the proposed algorithm and applied it to various interconnect trees with different timing targets. Experimental results demonstrate the high effectiveness of our approach. In comparison with the state-of-the-art low-power repeater insertion schemes, Freeze requires 5.8 times fewer iterations on the average, achieving up to 27 times speedup with even better power savings. When compared with a dynamic programming based scheme, which guarantees the optimal solution, our tool delivers up to 50 times speedup with 0.9% power increase on the average.