Non-photorealistic rendering (NPR) and image processing algorithms are widely assumed as a proxy for drawing. However, this assumption is not well assessed due to the difficulty in collecting and registering freehand drawings. Alternatively, tracings are easier to collect and register, but there is no quantitative evaluation of tracing as a proxy for freehand drawing. In this paper, we compare tracing, freehand drawing, and computer-generated drawing approximation (CGDA) to understand their similarities and differences. We collected a dataset of 1,498 tracings and freehand drawings by 110 participants for 100 image prompts. Our drawings are registered to the prompts and include vector-based timestamped strokes collected via stylus input. Comparing tracing and freehand drawing, we found a high degree of similarity in stroke placement and types of strokes used over time. We show that tracing can serve as a viable proxy for freehand drawing because of similar correlations between spatio-temporal stroke features and labeled stroke types. Comparing hand-drawn content and current CGDA output, we found that 60% of drawn pixels corresponded to computer-generated pixels on average. The overlap tended to be commonly drawn content, but people's artistic choices and temporal tendencies remained largely uncaptured. We present an initial analysis to inform new CGDA algorithms and drawing applications, and provide the dataset for use by the community.

BACKGROUND: Long read sequencing is changing the landscape of genomic research, especially de novo assembly. Despite the high error rate inherent to long read technologies, increased read lengths dramatically improve the continuity and accuracy of genome assemblies. However, the cost and throughput of these technologies limits their application to complex genomes. One solution is to decrease the cost and time to assemble novel genomes by leveraging "hybrid" assemblies that use long reads for scaffolding and short reads for accuracy. RESULTS: We describe a novel method leveraging a multi-string Burrows-Wheeler Transform with auxiliary FM-index to correct errors in long read sequences using a set of complementary short reads. We demonstrate that our method efficiently produces significantly more high quality corrected sequence than existing hybrid error-correction methods. We also show that our method produces more contiguous assemblies, in many cases, than existing state-of-the-art hybrid and long-read only de novo assembly methods. CONCLUSION: Our method accurately corrects long read sequence data using complementary short reads. We demonstrate higher total throughput of corrected long reads and a corresponding increase in contiguity of the resulting de novo assemblies. Improved throughput and computational efficiency than existing methods will help better economically utilize emerging long read sequencing technologies.

Before genotyping microarrays can be used, calling algorithms must first be calibrated with a control set. Calling algorithms that evaluate hybridization intensity data on the basis of individual markers are better able to compensate for sequence specific variations. However, they require that the control set includes samples sufficient to exercise every marker in all of its allelic states. Minimizing the size of the control set is an important cost-saving measure for the design and production of custom, population-specific microarrays. As the size of the population that the array must discriminate between increases, the naïve choice of a control set grows quadratically. We show that a control set that is linear in the population size always exists, but the problem of finding such a linear-sized set grows combinatorially. We examine the problem of finding an optimally-sized control set, in particular for arrays designed to discriminate among an inbred population and their crosses. We derive tight, in the sense of being attainable, lower and upper bounds on the solution size. Further, we show that the problem is equivalent to the set cover problem. We make use of greedy approximate methods to the set cover problem along with our established bounds to create a branch-and-bound framework. We demonstrate our methods on simulated data, available microarrays, and one microarray being developed.

Whole genome sequencing is becoming more affordable, but sequencing errors complicate the analysis and diminish the utility of the data. We present FMRC, a new tool for correcting errors in DNA short reads from high-throughput sequencing. It uses a Burrows-Wheeler Transform and FM-index to enable a k-mer counting approach for correcting substitution, insertion, and deletion errors. In general, it corrects errors more effectively than other error correction tools, leading to better alignments and de novo assemblies. FMRC is freely available at https://github.com/sgreenstein/fmrc.

MOTIVATION: The throughput of genomic sequencing has increased to the point that is overrunning the rate of downstream analysis. This, along with the desire to revisit old data, has led to a situation where large quantities of raw, and nearly impenetrable, sequence data are rapidly filling the hard drives of modern biology labs. These datasets can be compressed via a multi-string variant of the Burrows-Wheeler Transform (BWT), which provides the side benefit of searches for arbitrary k-mers within the raw data as well as the ability to reconstitute arbitrary reads as needed. We propose a method for merging such datasets for both increased compression and downstream analysis. RESULTS: We present a novel algorithm that merges multi-string BWTs in [Formula: see text] time where LCS is the length of their longest common substring between any of the inputs, and N is the total length of all inputs combined (number of symbols) using [Formula: see text] bits where F is the number of multi-string BWTs merged. This merged multi-string BWT is also shown to have a higher compressibility compared with the input multi-string BWTs separately. Additionally, we explore some uses of a merged multi-string BWT for bioinformatics applications.

MOTIVATION: RNA-seq techniques provide an unparalleled means for exploring a transcriptome with deep coverage and base pair level resolution. Various analysis tools have been developed to align and assemble RNA-seq data, such as the widely used TopHat/Cufflinks pipeline. A common observation is that a sizable fraction of the fragments/reads align to multiple locations of the genome. These multiple alignments pose substantial challenges to existing RNA-seq analysis tools. Inappropriate treatment may result in reporting spurious expressed genes (false positives) and missing the real expressed genes (false negatives). Such errors impact the subsequent analysis, such as differential expression analysis. In our study, we observe that ~3.5% of transcripts reported by TopHat/Cufflinks pipeline correspond to annotated nonfunctional pseudogenes. Moreover, ~10.0% of reported transcripts are not annotated in the Ensembl database. These genes could be either novel expressed genes or false discoveries. RESULTS: We examine the underlying genomic features that lead to multiple alignments and investigate how they generate systematic errors in RNA-seq analysis. We develop a general tool, GeneScissors, which exploits machine learning techniques guided by biological knowledge to detect and correct spurious transcriptome inference by existing RNA-seq analysis methods. In our simulated study, GeneScissors can predict spurious transcriptome calls owing to misalignment with an accuracy close to 90%. It provides substantial improvement over the widely used TopHat/Cufflinks or MapSplice/Cufflinks pipelines in both precision and F-measurement. On real data, GeneScissors reports 53.6% less pseudogenes and 0.97% more expressed and annotated transcripts, when compared with the TopHat/Cufflinks pipeline. In addition, among the 10.0% unannotated transcripts reported by TopHat/Cufflinks, GeneScissors finds that >16.3% of them are false positives. AVAILABILITY: The software can be downloaded at http://csbio.unc.edu/genescissors/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Genome browsers are a common tool used by biologists to visualize genomic features including genes, polymorphisms, and many others. However, existing genome browsers and visualization tools are not well-suited to perform meaningful comparative analysis among a large number of genomes. With the increasing quantity and availability of genomic data, there is an increased burden to provide useful visualization and analysis tools for comparison of multiple collinear genomes such as the large panels of model organisms which are the basis for much of the current genetic research. RESULTS: We have developed a novel web-based tool for visualizing and analyzing multiple collinear genomes. Our tool illustrates genome-sequence similarity through a mosaic of intervals representing local phylogeny, subspecific origin, and haplotype identity. Comparative analysis is facilitated through reordering and clustering of tracks, which can vary throughout the genome. In addition, we provide local phylogenetic trees as an alternate visualization to assess local variations. CONCLUSIONS: Unlike previous genome browsers and viewers, ours allows for simultaneous and comparative analysis. Our browser provides intuitive selection and interactive navigation about features of interest. Dynamic visualizations adjust to scale and data content making analysis at variable resolutions and of multiple data sets more informative. We demonstrate our genome browser for an extensive set of genomic data sets composed of almost 200 distinct mouse laboratory strains.

MOTIVATION: High-density SNP data of model animal resources provides opportunities for fine-resolution genetic variation studies. These genetic resources are generated through a variety of breeding schemes that involve multiple generations of matings derived from a set of founder animals. In this article, we investigate the problem of inferring the most probable ancestry of resulting genotypes, given a set of founder genotypes. Due to computational difficulty, existing methods either handle only small pedigree data or disregard the pedigree structure. However, large pedigrees of model animal resources often contain repetitive substructures that can be utilized in accelerating computation. RESULTS: We present an accurate and efficient method that can accept complex pedigrees with inbreeding in inferring genome ancestry. Inbreeding is a commonly used process in generating genetically diverse and reproducible animals. It is often carried out for many generations and can account for most of the computational complexity in real-world model animal pedigrees. Our method builds a hidden Markov model that derives the ancestry probabilities through inbreeding process without explicit modeling in every generation. The ancestry inference is accurate and fast, independent of the number of generations, for model animal resources such as the Collaborative Cross (CC). Experiments on both simulated and real CC data demonstrate that our method offers comparable accuracy to those methods that build an explicit model of the entire pedigree, but much better scalability with respect to the pedigree size.

Abstract A perspective image represents the spatial relationships of objects in a scene as they appear from a single viewpoint. In contrast, a multi‐perspective image combines what is seen from several viewpoints into a single image. Despite their incongruity of view, effective multi‐perspective images are able to preserve spatial coherence and can depict, within a single context, details of a scene that are simultaneously inaccessible from a single view, yet easily interpretable by a viewer. In computer vision, multi‐perspective images have been used for analysing structure revealed via motion and generating panoramic images with a wide field‐of‐view using mirrors. In this STAR, we provide a practical guide on topics in multi‐perspective modelling and rendering methods and multi‐perspective imaging systems. We start with a brief review of multi‐perspective image techniques frequently employed by artists such as the visual paradoxes of Escher, the Cubism of Picasso and Braque and multi‐perspective panoramas in cel animations. We then characterize existing multi‐perspective camera models, with an emphasis on their underlying geometry and image properties. We demonstrate how to use these camera models for creating specific multi‐perspective rendering effects. Furthermore, we show that many of these cameras satisfy the multi‐perspective stereo constraints and we demonstrate several multi‐perspective imaging systems for extracting 3D geometry for computer vision. The participants learn about topics in multi‐perspective modelling and rendering for generating compelling pictures for computer graphics and in multi‐perspective imaging for extracting 3D geometry for computer vision. We hope to provide enough fundamentals to satisfy the technical specialist without intimidating curious digital artists interested in multi‐perspective images. The intended audience includes digital artists, photographers and computer graphics and computer vision researchers using or building multi‐perspective cameras. They will learn about multi‐perspective modelling and rendering, along with many real world multi‐perspective imaging systems.

Many vision problems can be cast as optimizing the conditional probability density function p(C\I) where I is an image and C is a vector of model parameters describing the image. Ideally, the density function p(C\I) would be smooth and unimodal allowing local optimization techniques, such as gradient descent or simplex, to converge to an optimal solution quickly, while preserving significant nonlinearities of the model. We propose to learn a conditional probability density satisfying these desired properties for the given training data set. To do this, we formulate a novel regression problem that finds a function approximating the target density. Learning the regressor is challenging due to the high dimensionality of model parameters, C, and the complexity of relating the image and the model. Our approach makes two contributions. First, we take a multilevel refinement approach by learning a series of density functions, each of which guides the solution of optimization algorithms increasingly converging to the correct solution. Second, we propose a new data sampling algorithm that takes into account the gradient information of the target function. We have applied this learning approach to deformable shape segmentation and have achieved better accuracy than the previous methods.

Association analysis arises in many important applications such as bioinformatics and business intelligence. Given a large collection of measurements over a set of samples, association analysis aims to find dependencies of target variables to subsets of measurements. Most previous algorithms adopt a two-stage approach; they first group samples based on the similarity in the subset of measurements, and then they examine the association between these groups and the specified target variables without considering the inter-group similarities or alternative groupings. This can lead to cases where the strength of association depends significantly on arbitrary clustering choices. In this paper, we propose a tree-based method for quantitative association analysis. Tree hierarchies derived from sample similarities represent many possible sample groupings. They also provide a natural way to incorporate domain knowledge such as ontologies and to identify and remove outliers. Given a tree hierarchy, our association analysis evaluates all possible groupings and selects the one with strongest association to the target variable. We introduce an efficient algorithm, TreeQA, to systematically explore the search-space of all possible groupings in a set of input trees, with integrated permutation tests. Experimental results show that TreeQA is able to handlelarge-scale association analysis very efficiently and is more effective and robust in association analysis than previous methods.

A perspective image represents the spatial relationships of objects in a scene as they appear from a single viewpoint. In contrast, a multiperspective image combines what is seen from several viewpoints into a single image. Despite their incongruity of view, effective multiperspective images are able to preserve spatial coherence and can depict, within a single context, details of a scene that are simultaneously inaccessible from a single view, yet easily interpretable by a viewer. In computer vision, multiperspective images have been used for analyzing structure revealed via motion and generating panoramic images with a wide field-of-view using mirrors.

In this paper, we present a learning procedure called probabilistic boosting network (PBN) for joint real-time object detection and pose estimation. Grounded on the law of total probability, PBN integrates evidence from two building blocks, namely a multiclass boosting classifier for pose estimation and a boosted detection cascade for object detection. By inferring the pose parameter, we avoid the exhaustive scanning for the pose, which hampers real time requirement. In addition, we only need one integral image/volume with no need of image/volume rotation. We implement PBN using a graph-structured network that alternates the two tasks of foreground/background discrimination and pose estimation for rejecting negatives as quickly as possible. Compared with previous approaches, we gain accuracy in object localization and pose estimation while noticeably reducing the computation. We invoke PBN to detect the left ventricle from a 3D ultrasound volume, processing about 10 volumes per second, and the left atrium from 2D images in real time.

Elevation maps are a widely used spatial data representation in geographical information systems (GIS). Paths on elevation maps can be characterized by profiles, which describe relative elevation as a function of distance. In this research, we address the inverse of this mapping - given a profile, how to efficiently find paths that could have generated it. This is called the profile query problem. Profiles have a wide variety of uses that include registering tracking information, or even other maps, to a given map. We describe a probabilistic model to characterize the maximal likelihood that a point lying on a path matches the query profile. Propagation of such probabilities to neighboring points can effectively prune the search space. This model enables us to efficiently answer queries of arbitrary profiles with user-specified error tolerances. When compared to existing spatial index methods, our approach supports more flexible queries with orders of magnitude speedup.

The problem of selecting a sample subset sufficient to preserve diversity arises in many applications. One example is in the design of recombinant inbred lines (RIL) for genetic association studies. In this context, genetic diversity is measured by how many alleles are retained in the resulting inbred strains. RIL panels that are derived from more than two parental strains, such as the collaborative cross (Churchill et al., 2004), present a particular challenge with regard to which of the many existing lab mouse strains should be included in the initial breeding funnel in order to maximize allele retention. A similar problem occurs in the study of customer reviews when selecting a subset of products with a maximal diversity in reviews. Diversity in this case implies the presence of a set of products having both positive and negative ranks for each customer. In this paper, we demonstrate that selecting an optimal diversity subset is an NP-complete problem via reduction to set cover. This reduction is sufficiently tight that greedy approximations to the set cover problem directly apply to maximizing diversity. We then suggest a slightly modified subset selection problem in which an initial greedy diversity solution is used to effectively prune an exhaustive search for all diversity subsets bounded from below by a specified coverage threshold. Extensive experiments on real datasets are performed to demonstrate the effectiveness and efficiency of our approach.

We describe a computer graphics system that supports conceptual architectural design and analysis. We use as a starting point the traditional sketchbook drawings that architects use to experiment with various views, sections, and details. Rather than interpret or infer 3D structure from drawings, our system is designed to allow the designer to organize concept drawings in 3D, and gradually fuse a series of possibly geometrically-inconsistent sketches into a set of 3D strokes. Our system uses strokes and planar "canvases" as basic primitives; the basic mode of input is traditional 2D drawing. We introduce methods for the user to control stroke visibility and transfer strokes between canvases. We also introduce methods for the user to position and orient the canvases that have infinite extent. We demonstrate the use of the system to analyze existing structures and conceive new designs.

Given a set of objects V with a dissimilarity measure between pairs of objects in V, a PoCluster is a collection of sets P ⊂ powerset(V) partially ordered by the ⊂ relation such that S ⊂ T iff the maximal dissimilarity among objects in S is less than the maximal dissimilarity among objects in T. PoClusters capture categorizations of objects that are not strictly hierarchical, such as those found in ontologies. PoClusters can not, in general, be constructed using hierarchical clustering algorithms. In this paper, we examine the relationship between PoClusters and dissimilarity matrices and prove that PoClusters are in one-to-one correspondence with the set of dissimilarity matrices. The PoClustering problem is NP-Complete, and we present a heuristic algorithm for it in this paper. Experiments on both synthetic and real datasets demonstrate the quality and scalability of the algorithms.

We present a technique for enhancing underexposed visible-spectrum video by fusing it with simultaneously captured video from sensors in nonvisible spectra, such as Short Wave IR or Near IR. Although IR sensors can accurately capture video in low-light and night-vision applications, they lack the color and relative luminances of visible-spectrum sensors. RGB sensors do capture color and correct relative luminances, but are underexposed, noisy, and lack fine features due to short video exposure times. Our enhanced fusion output is a reconstruction of the RGB input assisted by the IR data, not an incorporation of elements imaged only in IR. With a temporal noise reduction, we first remove shot noise and increase the color accuracy of the RGB footage. The IR video is then normalized to ensure cross-spectral compatibility with the visible-spectrum video using ratio images. To aid fusion, we decompose the video sources with edge-preserving filters. We introduce a multispectral version of the bilateral filter called the "dual bilateral" that robustly decomposes the RGB video. It utilizes the less-noisy IR for edge detection but also preserves strong visible-spectrum edges not in the IR. We fuse the RGB low frequencies, the IR texture details, and the dual bilateral edges into a noise-reduced video with sharp details, correct chrominances, and natural relative luminances.

We present methods for generating novel time-lapse videos that address the inherent sampling issues that arise with traditional photographic techniques. Starting with video-rate footage as input, our post-process downsamples the source material into a time-lapse video and provides user controls for retaining, removing, and resampling events. We employ two techniques for selecting and combining source frames to form the output. First, we present a non-uniform sampling method, based on dynamic programming, which optimizes the sampling of the input video to match the user's desired duration and visual objectives. We present multiple error metrics for this optimization, each resulting in different sampling characteristics. To complement the non-uniform sampling, we present the virtual shutter , a non-linear filtering technique that synthetically extends the exposure time of time-lapse frames.

Illumination inconsistencies cause serious problems for classical computer vision applications such as tracking and stereo matching. We present a new approach to model illumination variations using an Illumination Ratio Map (IRM). An IRM computes the intensity ratio of corresponding points in an image pair. We formulate IRM recovery as a Markov network, which assumes spatially varying illumination changes can be modeled as a locally smooth function with boundaries. We show that the IRM Markov network can be easily incorporated into low-level vision problems, such as tracking and stereo matching, by integrating IRM estimation with the optical flow field/disparity map solution process. This leads to a unified Markov network. We develop an iterative optimization algorithm based on Belief Propagation to efficiently recover the illumination ratio map and the optical field/disparity map at the same time. Experiments demonstrate that our methods are robust and reliable.

Ontologies represent data relationships as hierarchies of possibly overlapping classes. Ontologies are closely related to clustering hierarchies, and in this article we explore this relationship in depth. In particular, we examine the space of ontologies that can be generated by pairwise dissimilarity matrices. We demonstrate that classical clustering algorithms, which take dissimilarity matrices as inputs, do not incorporate all available information. In fact, only special types of dissimilarity matrices can be exactly preserved by previous clustering methods. We model ontologies as a partially ordered set (poset) over the subset relation. In this paper, we propose a new clustering algorithm, that generates a partially ordered set of clusters from a dissimilarity matrix.

Motion capture data from human subjects exhibits considerable redundancy. In this paper, we propose novel methods for exploiting this redundancy. In particular, we set out to find a subset of motion-capture markers that are able to provide fast and high-quality predictions of the remaining markers. We then develop a model that uses this reduced marker set to predict the others. We demonstrate that this subset of original markers is sufficient to capture subtle variations in human motion.We take a data-driven modeling approach to learn piecewise local linear models from a marker-based training set. We first divide motion sequences into segments of low dimensionality. We then retrieve a feature vector from each of the motion segments and use these feature vectors as modeling primitives to cluster the segments into a hierarchy of local linear models via a divisive clustering method. The selection of an appropriate linear model for reconstruction of a full-body pose is determined automatically via a classifier driven by a reduced marker set. After offline training, our method can quickly reconstruct full-body human motion using a reduced marker set without storing and searching the large database. We also demonstrate our method's ability to generalize over a variety of motions from multiple subjects.

We present a novel method for analyzing reflections on arbitrary surfaces. We model reflections using a broader than usual class of imaging models, which include both perspective and multiperspective camera types. We provide an analytical framework to locally model reflections as specific multiperspective cameras around every ray based on a new theory of general linear cameras. Our framework better characterizes the complicated image distortions seen on irregular mirror surfaces as well as the conventional catadioptric mirrors. We show the connection between multiperspective camera models and caustic surfaces of reflections and demonstrate how they reveal important surface rulings of the caustics. Finally, we show how to use our analysis to assist mirror design and characterize distortions seen in catadioptric imaging systems.

We present theories of multiperspective projection and collineation. Given an arbitrary multiperspective imaging system that captures smoothly varying set of rays, we show how to map the rays onto a 2D ray manifold embedded in a 4D linear vector space. The characteristics of this imaging system, such as its projection, collineation, and image distortions can be analyzed by studying the 2D tangent planes of this ray manifold. These tangent planes correspond to the recently proposed general linear camera (GLC) model. In this paper, we study the imaging process of the GLCs. We show the GLC imaging process can be broken down into two separate stages: the mapping of 3D geometry to rays and the sampling of those rays over an image plane. We derive a closed-form solution to projecting 3D points in a scene to rays in a GLC. A GLC image is created by sampling these rays over an image plane. We develop a notion of GLC collineation analogous to pinhole cameras. GLC collineation describes the transformation between the images of a single GLC due to changes in sampling and image plane selection. We show that general GLC collineations can be characterized by a quartic (4th order) rational function. GLC projection and collineation provides a basis for developing new computer vision algorithms suitable for analyzing a wider range of imaging systems than current methods, based on simple pinhole projection models, permit.

We present a novel algorithm to efficiently render accurate reflections on programmable graphics hardware. Our algorithm overcomes problems that commonly occur in environment mapping such as the lack of motion parallax and inaccuracies when objects are close to the reflectors. In place of a 2D environment map, which only represents points infinitely far away from the reflector, we use six 4D light field slabs to represent the surrounding scene. Each reflected ray is rendered by indexing into these precaptured environment light fields. We are able to render accurate reflections with motion parallax at interactive frame rates independent of the reflector geometry and the scene complexity. Furthermore, we can move the reflectors within a constrained region of space and guarantee that the environment light field provides the necessary rays. We benefit from the programmability of existing graphics hardware to efficiently compute the reflected rays and transform them into the appropriate light field index. We also take advantage of the large texture memories and memory bandwidth available in today's graphics card to store and query hardware-compressed light fields.

We demonstrate a data-driven approach for representing, compressing, and indexing human-motion databases. Our modeling approach is based on piecewise-linear components that are determined via a divisive clustering method. Selection of the appropriate linear model is determined automatically via a classifier using a subspace of the most significant, or principle features (markers). We show that, after offline training, our model can accurately estimate and classify human motions. We can also construct indexing structures for motion sequences according to their transition trajectories through these linear components. Our method not only provides indices for whole and/or partial motion sequences, but also serves as a compressed representation for the entire motion database. Our method also tends to be immune to temporal variations, and thus avoids the expense of time-warping.

We enhance underexposed, low dynamic range videos by adaptively and independently varying the exposure at each photoreceptor in a post-process. This virtual exposure is a dynamic function of both the spatial neighborhood and temporal history at each pixel. Temporal integration enables us to expand the image's dynamic range while simultaneously reducing noise. Our non-linear exposure variation and denoising filters smoothly transition from temporal to spatial for moving scene elements. Our virtual exposure framework also supports temporally coherent per frame tone mapping. Our system outputs restored video sequences with significantly reduced noise, increased exposure time of dark pixels, intact motion, and improved details.

We present an approach to video editing where movie sequences are treated as spatio-temporal volumes that can be sheered and warped under user control. This simple capability enables new video editing operations that support complex postproduction modifications, such as object removal and/or changes in camera motion. Our methods do not rely on complicated and error-prone image analysis or computer vision methods. Moreover, they facilitate an editing approach to video that is similar to standard image-editing tasks. Central to our system is a movie representation framework called Proscenium that supports efficient queries and operations on spatio-temporal volumes while maintaining the original source content. We have adopted a graph-based lazy-evaluation model in order to support interactive visualizations, complex data modifications, and efficient processing of large spatio-temporal volumes.

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 describe a method for the acquisition of deformable human geometry from silhouettes. Our technique uses a commercial tracking system to determine the motion of the skeleton, then estimates geometry for each bone using constraints provided by the silhouettes from one or more cameras. These silhouettes do not give a complete characterization of the geometry for a particular point in time, but when the subject moves, many observations of the same local geometries allow the construction of a complete model. Our reconstruction algorithm provides a simple mechanism for solving the problems of view aggregation, occlusion handling, hole filling, noise removal, and deformation modeling. The resulting model is parameterized to synthesize geometry for new poses of the skeleton. We demonstrate this capability by rendering the geometry for motion sequences that were not included in the original datasets.

Motion confidence measures aim to identify how well an image patch determines image motion. These kinds of confidence measures are commonly used to select points for optical flow estimation and feature tracking. The brute force approach of computing confidence for every image patch is inefficient, especially when the patches are large. The faster approach of computing confidence for a regular grid of patches is sub-optimal; good patches may be missed because they straddle grid boundaries. We present a new algorithm that efficiently selects globally optimal patches. Our primary innovation is the use of confidence bounds to identify image regions that should be explored by a queue-based search algorithm.

In this paper we present a new variant of the light field representation that supports improved image reconstruction by accommodating sparse correspondence information. This places our representation somewhere between a pure, two-plane parameterized, light field and a lumigraph representation, with its continuous geometric proxy. Our approach factorises the rays of a light field into one of two separate classes. All rays consistent with a given correspondence are implicitly represented using a new auxiliary data structure, which we call a surface camera (or scam). The remaining rays of the light field are represented using a standard two-plane parameterized light field. We present an efficient rendering algorithm that combines ray samples from scams with those from the light field. The resulting image reconstructions are noticeably improved over that of a pure light field.

We present a procedural approach to authoring layered, solid models. Using a simple scripting language, we define the internal structure of a volume from one or more input meshes. Sculpting and simulation operators are applied within the context of the language to shape and modify the model. Our framework treats simulation as a modeling operator rather than simply as a tool for animation, thereby suggesting a new paradigm for modeling as well as a new level of abstraction for interacting with simulation environments.Capturing real-world effects with standard modeling techniques is extremely challenging. Our key contribution is a concise procedural approach for seamlessly building and modifying complex solid geometry. We present an implementation of our language using a flexible tetrahedral representation. We show a variety of complex objects modeled in our system using tools that interface with finite element method and particle system simulations.

We have built a system for acquiring and displaying high quality graphical models of objects that are impossible to scan with traditional scanners. Our system can acquire highly specular and fuzzy materials, such as fur and feathers. The hardware set-up consists of a turntable, two plasma displays, an array of cameras, and a rotating array of directional lights. We use multi-background matting techniques to acquire alpha mattes of the object from multiple viewpoints. The alpha mattes are used to construct an opacity hull. The opacity hull is a new shape representation, defined as the visual hull of the object with view-dependent opacity. It enables visualization of complex object silhouettes and seamless blending of objects into new environments. Our system also supports relighting of objects with arbitrary appearance using surface reflectance fields, a purely image-based appearance representation. Our system is the first to acquire and render surface reflectance fields under varying illumination from arbitrary viewpoints. We have built three generations of digitizers with increasing sophistication. In this paper, we present our results from digitizing hundreds of models.

We consider the problem of video stabilization: removing unwanted image perturbations due to unstable camera motions. We approach this problem from an image-based rendering (IBR) standpoint. Given an unstabilized video sequence, the task is to synthesize a new sequence as seen from a stabilized camera trajectory. This task is relatively straightforward if one has a Euclidean reconstruction of the unstabilized camera trajectory and a suitable IBR algorithm. However, it is often not feasible to obtain a Euclidean reconstruction from an arbitrary video sequence. In light of this problem, we describe IBR techniques for non-metric reconstructions, which are often much easier to obtain since they do not require camera calibration. These rendering techniques are well suited to the video stabilization problem. The key idea behind our techniques is that all measurements are specified in the image space, rather than in the non-metric space.

We present a novel drawing system for composing and rendering perspective scenes. Our approach uses a projective 2D representation for primitives rather than a conventional 3D description. This allows drawings to be composed with the same ease as traditional illustrations, while providing many of the advantages of a 3D model. We describe a range of user-interface tools and interaction techniques that give our system its 3D-like capabilities. We provide vanishing point guides and perspective grids to aid in drawing freehand strokes and composing perspective scenes. Our system also has tools for intuitive navigation of a virtual camera, as well as methods for manipulating drawn primitives so that they appear to undergo 3D translations and rotations. We also support automatic shading of primitives using either realistic or non-photorealistic styles. Our system supports drawing and shading of extrusion surfaces with automatic hidden surface removal and highlighted silhouettes. Casting shadows from an infinite light source is also possible with minimal user intervention. CR Categories: I.3.3 [Computer Graphics]: Graphics Utilities--- Graphics Editors; I.3.6 [Computer Graphics]: Methodologies and Techniques---Interaction Techniques Keywords: Image-based Modeling and Rendering, Misc. 2D graphics, Non-Euclidean Spaces, Non-Photorealistic Rendering 1

We describe an image based rendering approach that generalizes many current image based rendering algorithms, including light field rendering and view-dependent texture mapping. In particular, it allows for lumigraph-style rendering from a set of input cameras in arbitrary configurations (i.e., not restricted to a plane or to any specific manifold). In the case of regular and planar input camera positions, our algorithm reduces to a typical lumigraph approach. When presented with fewer cameras and good approximate geometry, our algorithm behaves like view-dependent texture mapping. The algorithm achieves this flexibility because it is designed to meet a set of specific goals that we describe. We demonstrate this flexibility with a variety of examples.

This research further develops the light field and lumigraph image-based rendering methods and extends their utility. We present alternate parameterizations that permit 1) interactive rendering of moderately sampled light fields of scenes with significant, unknown depth variation and 2) low-cost, passive autostereoscopic viewing. Using a dynamic reparameterization, these techniques can be used to interactively render photographic effects such as variable focus and depth-of-field within a light field. The dynamic parameterization is independent of scene geometry and does not require actual or approximate geometry of the scene. We explore the frequency domain and ray-space aspects of dynamic reparameterization, and present an interactive rendering technique that takes advantage of today's commodity rendering hardware.

In this paper, we describe an efficient image-based approach to computing and shading visual hulls from silhouette image data. Our algorithm takes advantage of epipolar geometry and incremental computation to achieve a constant rendering cost per rendered pixel. It does not suffer from the computation complexity, limited resolution, or quantization artifacts of previous volumetric approaches. We demonstrate the use of this algorithm in a real-time virtualized reality application running off a small number of video streams. Keywords: Computer Vision, Image-Based Rendering, Constructive Solid Geometry, Misc. Rendering Algorithms. 1 Introduction Visualizing and navigating within virtual environments composed of both real and synthetic objects has been a long-standing goal of computer graphics. The term "Virtualized Reality^TM", as popularized by Kanade [23], describes a setting where a real-world scene is "captured" by a collection of cameras and then viewed through a virtual camera, a...

The distribution of digital video content over computer networks has become commonplace. Unfortunately, most digital video encoding standards do not degrade gracefully in the face of packet losses, which often occur in a bursty fashion. We propose an new video encoding system that scales well with respect to the network's performance and degrades gracefully under packet loss. Our encoder sends packets that consist of a small random subset of pixels distributed throughout a video frame. The receiver places samples in their proper location (through a previously agreed ordering), and applies a reconstruction algorithm on the received samples to produce an image. Each of the packets is independent, and does not depend on the successful transmission of any other packets. Additionally, each packet contains information that is distributed over the entire image. We also apply spatial and temporal optimization to achieve better compression.

Freehand sketching has long had appeal as an artistic medium for conceptual design because of its immediacy in capturing and communicating design intent and visual experience. We present a sketching paradigm that supports the early stages of design by preserving the fluidity of traditional freehand drawings. In addition, it attempts to fill the gap between 2D drawing programs, which have fixed views, and 3D modeling programs that allow arbitrary views. We implement our application as a two-dimensional drawing program that utilizes a projective representation of points — i.e. points that lie on the surface of a unit sphere centered at the viewpoint. This representation facilitates the production of novel re-projections generated from an initial perspective sketch and gives the user the impression of being immersed in the drawing or space. We describe a method for aligning a sketch drawn outside the system using its vanishing points, allowing the integration of computer sketching and freehand sketching on paper in an iterative manner. The user interface provides a virtual camera, projective grids to guide in the construction of proportionate scenes, and the ability to underlay sketches with other drawings or photographic panoramas.

A pair of rendered images and tbek Z-buffers contain almost all of the information necessary tore-render from nearby viewpoints.For the small changes in viewpoint that occur in a fraction of a second, this information is sufficient for high quafity re-rendering with cost independent of scene complexity.Re-rendenng from previously computed views allows an order-of-magnitude increase in apparent frame rate over that provided by conventional rendering alone.It can also compensate for system latency in local or remote display.We use McMillan and Bishop's image warping algorithm to re-render, allowing us to compensate for viewpoint translation as well as rotation.We avoid occlusion-related artifacts by warping two different reference images and compositing the results, This paper explains the basic design of our system and provides details of our reconstruction and multi-image compositing afgoritbms.We present our method for selecting reference image locations and the heuristic we use for any portions of the scene which happen to be occluded in both reference images.We also discuss properties of our technique which make it suitable for real-time implementation, and briefly describe our simpler rerd-time remote dkplay system.

Article Free Access Share on Image-based rendering (panel): really new or déjà vu? Authors: Michael Cohen Microsoft Research Microsoft ResearchView Profile , Marc Levoy Stanford University Stanford UniversityView Profile , Jitendra Malik University of California, Berkeley University of California, BerkeleyView Profile , Leonard McMillan Massachusetts Institute of Technology Massachusetts Institute of TechnologyView Profile , Eric Chen Live Picture Live PictureView Profile Authors Info & Claims SIGGRAPH '97: Proceedings of the 24th annual conference on Computer graphics and interactive techniquesAugust 1997 Pages 468–470https://doi.org/10.1145/258734.258911Published:03 August 1997Publication History 5citation426DownloadsMetricsTotal Citations5Total Downloads426Last 12 Months7Last 6 weeks2 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 SiteeReaderPDF

Article Free Access Share on Plenoptic modeling: an image-based rendering system Authors: Leonard McMillan Department of Computer Science, University of North Carolina at Chapel Hill, CB 3175 Sitterson Hall, Chapel Hill, NC Department of Computer Science, University of North Carolina at Chapel Hill, CB 3175 Sitterson Hall, Chapel Hill, NCView Profile , Gary Bishop Department of Computer Science, University of North Carolina at Chapel Hill, CB 3175 Sitterson Hall, Chapel Hill, NC Department of Computer Science, University of North Carolina at Chapel Hill, CB 3175 Sitterson Hall, Chapel Hill, NCView Profile Authors Info & Claims SIGGRAPH '95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniquesSeptember 1995 Pages 39–46https://doi.org/10.1145/218380.218398Published:15 September 1995Publication History 651citation5,126DownloadsMetricsTotal Citations651Total Downloads5,126Last 12 Months352Last 6 weeks50 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 SiteeReaderPDF

We present a simple and intuitive algorithm for the quantization of full-color images which has been designed to apply to static images and motion sequences equally well. Our technique eliminates the perils of hardware colormap flashing which is inherent in other well known algorithms for selecting colormap representatives. We compare our technique with existing static image colormap generation techniques to show the quality of the resultant quantization.

The use of double-buffered displays, in which the previous image is displayed until the next image is complete, can impair the interactivity of systems that require tight coupling between the human user and the computer. We are experimenting with an alternate rendering strategy that computes each pixel based on the most recent input (i.e., view and object positions) and immediately updates the pixel on the display. We avoid the image tearing normally associated with single-buffered displays by randomizing the order in which pixels are updated. The resulting image sequences give the impression of moving continuously, with a rough approximation of motion blur, rather than jerking between discrete positions.

The paper presents a new realization of the inverse discrete cosine transform (IDCT). It exploits both the decorrelation properties of the discrete cosine transform (DCT) and the quantization process that is frequently applied to the DCT's resultant coefficients. This formulation has several advantages over previous approaches, including the elimination of multiplies from the central loop of the algorithm and its adaptability to incremental evaluation. The technique provides a significant reduction in computational requirements of the IDCT, enabling a software-based implementation to perform at rates which were previously achievable only through dedicated hardware.>

We describe the system architecture and the programming environment of the Pixel Machine - a parallel image computer for 2D and 3D image synthesis and analysis. The architecture of the computer is based on an array of asynchronous MIMD nodes with a parallel access to a large frame buffer. The system consists of a pipeline of pipe nodes which execute sequential algorithms and an array of m x n pixel nodes which execute parallel algorithms. A pixel node accesses every m-th pixel on every n-th scan line of a distributed frame buffer. Each processing node is based on a high-speed, floating-point programmable processor. The programmability of the computer allows all algorithms to be implemented in software. A set of mapping functions transfers image algorithms written for conventional single-processor computers to algorithms which execute in the pixel nodes and access the distributed frame buffer. The ability to use floating-point computations in pixel operations, such as antialiasing, ray tracing, and filtering, allows high-quality image generation and processing. The image computer provides up to 820 megaflops of peak processing power and 48 megabytes of memory for data-visualization applications.