bluuebunny/crossref_metadata_2025 huggingface dataset:
A data flow processor array system
Authors: Takahashi Naohisa , Amamiya Makoto
Published: November 2005

This paper presents the architecture of a highly parallel processor array system which executes programs by means of a data driven control mechanism. The data driven control mechanism makes it easy to construct an MIMD (multiple instruction stream and multiple data stream) system, since it unifies inter-processor data transfer and intra-processor execution control. The design philosophy of the data flow processor array system presented in this paper is to achieve high performance by adapting a system structure to operational characteristics of application programs, and also to attain flexibility through executing instructions based on a data driven mechanism.

The operational characteristics of the proposed system are analyzed using a probability model of the system behavior. Comparing the analytical results with the simulation results through an experimental hardware system, the results of the analysis clarify the principal effectiveness of the proposed system. This system can achieve high operation rates and is neither sensitive to inter-processor communication delay nor sensitive to system load imbalance.
Adaptive interpretation as a means of exploiting complex instruction sets
Authors: Norton Richard L. , Abraham Jacob A.
Published: November 2005

In this paper we concentrate on the effect of instruction set architecture on the performance potential of a computer system. These issues are key in considerations of what instruction set is most appropriate for the support of high level languages on general purpose machines. Two possible approaches are so called complex instruction sets, such as those of the VAX and IAPX 432, and the “reduced” instruction set of the RISC I [2] microcomputer, which is expected to have performance similar to that of a VAX 11-780.

We propose a method of instruction set interpretation that takes advantage of the architectural features of complex instruction sets. These methods have been simulated executing real programs and in the case of the VAX instruction set have resulted in a typical improvement of a factor of two, assuming the same cycle time as the VAX 11-780. The techniques presented exploit the context available in a complex instruction and retain this information for use in subsequent execution of that instruction. Since this context is available only within a single instruction, low level instruction sets cannot benefit from this technique. In this sense the reduced instruction set machines as implemented in RISC are at their architectural limits, while complex instruction sets such as the VAX are far from theirs. For these reasons, complex instruction sets can have a significantly greater performance potential than a RISC instruction set for a given technology.
A comparative study of distributed resource sharing on multiprocessors
Authors: Wah Benjamin W.
Published: November 2005

In this paper, we have studied the interconnection of resources to multiprocessors and the distributed scheduling of these resources. Three different classes of interconnection networks have been investigated; namely, single shared bus, multiple shared buses, and networks with logarithmic delays such as the cube and Omega networks. For a given network, the resource mapping problem entails the search of one (or more) of the free resources which can be connected to each requesting processor. To prevent the bottleneck of sequential scheduling, the type(s) and number(s) of resources desired by a processor are given to the network and it is the responsibility of the network to find the necessary resources and connect them to the processor. The addressing mechanism is, thus, distributed in the network. This is a generalization of conventional interconnection networks with routing tags in which all the resources are of different types.
Hierarchical function distribution - a design principle for advanced multicomputer architectures
Authors: Giloi W. K. , Behr P.
Published: November 2005

An abstract view of a computer system is provided by a hierarchy of functions, ranging from the high-level operating system functions down to the primitive functions of the hardware. Vertical migration of high-level functions into the microcode of a CPU or horizontal migration of hardware functions out of the CPU into dedicated processors alone is not an adequate realization method for innovative computer architectures with complex functionality. In the paper, a new design principle called
hierarchical function distribution
is introduced to cope with the task of designing innovative multicomputer systems with complex functionality. The design rules of hierarchical function distribution are presented, and the advantages of the approach are discussed and illustrated by examples.
EMMA-an industrial experience on large multiprocessing architectures
Authors: Stringa Luigi
Published: November 2005

EMMA (1) is a multiprocessor system designed and built by ELSAG of Genoa, Italy, to solve problems of pattern recognition arising in automatic mail sorting.

The resulting architecture is modular, organizable around several levels, and offers a theoretically unlimited possibility of increasing the processor power.

EMMA runs under a simple distributed operating system, supplying process communication, synchronization primitives and some diagnostic functions that complement analysis and reconfiguration modules residing in the supervisor.
A communication structure for a multiprocessor computer with distributed global memory
Authors: Philipson Lars , Nilsson Bo , Breidegard Bjorn
Published: November 2005

An experimental multiprocessor computer was designed and built in order to explore the feasibility of certain internal communication mechanisms. The system consisted of seven processing elements, each containing a part of the global memory connected to a local bus. For each processor the global memory is seen as one single, linearly addressable structure. The processing elements were all connected to a common, global bus, consisting of three separate busses in order to increase the capacity. A bus selection unit was designed, capable of making a unique bus selection for each request, within a fraction of a memory cycle. The experiments have shown that communication structures based on distributed global memory and global bus systems can be used efficiently for medium scale systems.
ALPHA-a high-performance LISP machine equipped with a new stack structure and garbage collection system
Authors: Hayashi Hiromu , Hattori Akira , Akimoto Haruo
Published: November 2005

ALPHA is a dedicated machine designed for high-speed list processing. In this article, we describe a highly effective stack which can support a value cache and virtual stack, and high-speed garbage collection algorithm for virtual memory. These new ideas have been studied in ALPHA. ALPHA is designed as a back end processor for a large computer under TSS. ALPHA allows TSS users to do more high-speed list processing than a large computer does.

Currently UTILISP is operating on ALPHA and runs several times faster than MACLISP on the DEC 2060.
A parallel execution model of logic programs
Authors: Umeyama Shinji , Tamura Koichiro
Published: November 2005

A logic programming language offers several kinds of parallelism for its execution. Among these, this paper concentrates on OR-parallelism which is an alternative to the backtracking mechanism of a serial interpreter, and proposes an abstract model for OR-parallel interpretation. It consists of tokens and five kinds of function units mutually connected as a process graph. The overall processing is done by the flows of tokens among these units. We also present a mechanism for token labeling, which makes this process graph reentrant. A simulation result is given to show how efficiently the model works in terms of parallelism.
A system architecture for the concurrent evaluation of applicative program expressions
Authors: Schmittgen Claudia , Kluge Werner
Published: November 2005

The paper outlines the principles for the concurrent evaluation of applicative programs based on Berklings reduction language. The recursive style of program design supported by this language lends itself to a recursive partitioning scheme which, for suitable program expressions, generates dynamically a hierarchy of processes for the concurrent evaluation of subexpressions. This hierarchy can elegantly be mapped onto a system of cooperating reduction machines featuring a stack architecture. A special ticket mechanism enforces an upper limit on the number of processes that, at any time, may exist within the system, which does not significantly exceed the number of the available machines.
A performance evaluation of a Lisp-based data-driven machine (EM-3)
Authors: Yamaguchi Yoshinori , Toda Kenji , Yuba Toshitsugu
Published: November 2005

In this paper, a Lisp-based data-driven machine with a novel parallel control mechanism and its performance evaluation are presented. The proposed control mechanism is the natural extension of a data-driven scheme to function evaluation and is achieved by packet communication architecture.

First, the organization of the data-driven machine is described and, then the results of the simulation studies are shown which confirm the effectiveness of the control mechanism. The performance characteristics of the data-driven machine obtained by the software simulator are also given.
A pyramidal approach to parallel processing
Authors: Tanimoto Steven L.
Published: November 2005

This paper presents the architecture of a parallel computer called a pyramid machine. The system consists of a pyramidal array of processing elements, each of which executes the instructions broadcast by a controller. Each processing element except those on the outside of the array is directly connected to thirteen neighboring elements: eight on the same level, four on the next finer level and one on the next coarser level. The architecture combines features of tree machines and features of mesh-connected parallel computers. As a result it is able to rapidly perform computations of local and global processing. The main areas of application are image processing, graphics and spatial problem solving. The motivation, basic structure, and applications of the system are discussed.
The design of a parallel processor for image processing on-board satellites
Authors: Gaillat Gérard
Published: November 2005

A parallel MIMD type processor for use in image processing applications on board satellites is described. Emphasis is given to the application requirements in terms of processing power, type of parallelism, communication need and to the impact of these requirements on the architecture design. The choice of a MIMD processor with a ring bus, the convenience of a multiple bus structure, the definition of the bus protocole, the synchronization mechanism and the typical performances are presented as successive choices and discussed in regard of the requirements. Possibilities and limits of the architecture are carefully analyzed: Typical examples of efficiently implementable applications in other fields of image processing are given. But limits of the structure are pointed out for other types of parallel processing.
Links-1 - a parallel pipelined multimicrocomputer system for image creation
Authors: Nishimura Hitoshi , Ohno Hiroshi , Kawata Toru , Shirakawa Isao , Omura Koichi
Published: November 2005

A multimicrocomputer system is described, stressing mainly software and hardware architectures, which has been constructed mainly for image creation. This system is distinctive mainly in that (i) 64 unit computers are interconnected with a root computer, each of equal performance, such that a number of unit computers constitute a pipelined computer and such pipelined computers work in parallel, all controlled by the root computer, and (ii) an intercomputer memory swapping unit is introduced, which is to be linked with a pair of unit computers to transfer a great amount of data at a time from one to the other through the use of a bus exchange switch.
LIPP - a SIMD multiprocessor architecture for image processing
Authors: Ericsson T. , Danielsson P. E
Published: November 2005

LIPP (Linköping Image Parallell Processor) is a multiprocessor system intended mainly for image analysis and image processing but even other computing tasks where large amount of data should be manipulated in forms of matrices, such as weather forecasts or other related problems namely systems of differential equations. The processors within the processor array are of bit-serial type with the capability of directly processing data with wordlengths in the range of 1 bit to 32 bits in one bit increments without time penalty. Bit-serial operation gives the possibility of designing suprisingly fast algorithms. To each processor is a fairly large memory (64 Kbit) associated. A processor can instantly reach 8 neighboring memories through an interconnecting network. The processor array whose size is thought to be 16 by 16 it running in SIMD mode. In this way memory access collisions can be minimized. Image and matrix data are mapped in the memory space so that each memory holds a subimage. We call this mapping
distributed processor topology
. Because of the memory mapping and interconnection network neighborhood operations such as two dimensional convolution are easily performed.
Inference machine
Authors: Uchida Shunichi
Published: November 2005

In this paper, the research and development plan for computer architecture in the fifth generation computer system project ( FGCS Project) is described, focusing on the research on the inference machine.
Overview to the Fifth Generation Computer System project
Authors: Moto-oka Tohru
Published: November 2005

Computers which have high performances for non-numeric data processing should be developed in order to satisfy and expand new applications which will become predominant fields in information processing of the 1990s.

Knowledge information processing forming the main part of applied artificial intelligence is expected to be one of the important fields in 1990s information processing and the dedicated computers for this have been selected as the main theme of the national project of the Fifth Generation computers.

The key technologies for the Fifth Generation Computer System (FGCS) seem to be VLSI architecture, parallel processing such as data flow control, logic programming, knowledge base based on relational database, and applied artificial intelligence and pattern processing.

Inference machines and relational algebra machines are typical of the core processors which constitute FGCS.
A relational data base machine
Authors: Murakami Kunio , Kakuta Takeo , Miyazaki Nobuyoshi , Shibayama Shigeki , Yokota Haruo
Published: November 2005

The Japan's Fifth Generation Computer System project is divided into three stages. In the first three-year stage, a working relational data base machine is developed for a software development support system to be used in the second stage and also for an experimental system which provides a research tool for the knowledge base machine.

The paper briefly describes the concepts and architecture of the relational data base machine named “Delta” which is currently under development at ICOT.
Achieving sub-second IGP convergence in large IP networks
Authors: Francois Pierre , Filsfils Clarence , Evans John , Bonaventure Olivier
Published: November 2005

We describe and analyse in details the various factors that influence the convergence time of intradomain link state routing protocols. This convergence time reflects the time required by a network to react to the failure of a link or a router. To characterise the convergence process, we first use detailed measurements to determine the time required to perform the various operations of a link state protocol on currently deployed routers. We then build a simulation model based on those measurements and use it to study the convergence time in large networks. Our measurements and simulations indicate that sub-second link-state IGP convergence can be easily met on an ISP network without any compromise on stability.
National ICT Australia (NICTA)
Authors: Seneviratne Aruna , Percival Terry
Published: November 2005

Information and Communications Technology (ICT) has had a profound impact on the world's social and economic development. National ICT Australia's (NICTA) has been established to ensure that Australia continues to capitalize on the massive opportunities that ICT research delivers and to create a vibrant ICT industry that boosts Australia's competitive advantage and builds the overall wealth of nation.
Computing research
Authors: Lazowska Edward D. , Patterson David A.
Published: November 2005

On June 11, Vint Cerf and Bob Kahn received computing's highest prize, the A.M. Turing Award, from the Association for Computing Machinery. Their Transmission Control Protocol (TCP), created in 1973, became the language of the Internet.In the May 6 issue of Science [1], we used this as the "news hook" for an invited editorial on the current state of computer science research in the United States. "Where will the next generation of groundbreaking innovations in IT arise?" we asked. "Where will the Turing Awardees 30 years hence reside?" Our conclusion: "Given current trends, the answers to both questions will likely be 'not in the United States.'"We take this opportunity to explore in greater depth the issues we raised in that editorial. What are the trends that concern us? What can all of us, as computer scientists, do to reverse them?
Part II
Authors: Raina Gaurav , Towsley Don , Wischik Damon
Published: November 2005

This article describes how control theory has been used to address the question of how to size the buffers in core Internet routers. Control theory aims to predict whether the is stable, i.e. whether TCP flows are desynchronized. If flows are desynchronized then small buffers are sufficient [14 ]; the theory here shows that small buffers actually promote desynchronization--a virtuous circle.
Part III
Authors: Enachescu Mihaela , Ganjali Yashar , Goel Ashish , McKeown Nick , Roughgarden Tim
Published: November 2005

Internet routers require buffers to hold packets during times of congestion. The buffers need to be fast, and so ideally they should be small enough to use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we need a bandwidth-delay product of buffering at each router so as not to lose link utilization. This can be prohibitively large. In a recent paper, Appenzeller et al. challenged this rule-of-thumb and showed that for a backbone network, the buffer size can be divided by pN without sacrificing throughput, where N is the number of ows sharing the bottleneck. In this paper, we explore how buffers in the backbone can be significantly reduced even more, to as little as a few dozen packets, if we are willing to sacrifice a small amount of link capacity. We argue that if the TCP sources are not overly bursty, then fewer than twenty packet buffers are sufficient for high throughput. Specifically, we argue that O(log W) buffers are sufficient, where W is the window size of each ow. We support our claim with analysis and a variety of simulations. The change we need to make to TCP is minimal--each sender just needs to pace packet injections from its window. Moreover, there is some evidence that such small buffers are sufficient even if we don't modify the TCP sources so long as the access network is much slower than the backbone, which is true today and likely to remain true in the future. We conclude that buffers can be made small enough for all-optical routers with small integrated optical buffers.
Experiences from the Sigcomm 2005 European shadow PC experiment
Authors: Feldmann Anja
Published: November 2005

This note is an informal report about the Shadow Program Commit-tee experiment that I organized for Sigcomm 2005. It (i) discusses the motivation for a Shadow Program Committee (PC), (ii) presents the expected benefit to the community, (iii) explains the process by which it was organized, (iv) gives some statistics on the program that the Shadow PC selected, how much, and why it differed from the real PC's program, and (v) discusses some of the insights from the Shadow PC process.
SCAPE
Authors: Anguelov Dragomir , Srinivasan Praveen , Koller Daphne , Thrun Sebastian , Rodgers Jim , Davis James
Published: November 2005

We introduce the SCAPE method (Shape Completion and Animation for PEople)---a data-driven method for building a human shape model that spans variation in both subject shape and pose. The method is based on a representation that incorporates both articulated and non-rigid deformations. We learn a
pose deformation model
that derives the non-rigid surface deformation as a function of the pose of the articulated skeleton. We also learn a separate model of variation based on body shape. Our two models can be combined to produce 3D surface models with realistic muscle deformation for different people in different poses, when neither appear in the training set. We show how the model can be used for
shape completion
--- generating a complete surface mesh given a limited set of markers specifying the target shape. We present applications of shape completion to partial view completion and motion capture animation. In particular, our method is capable of constructing a high-quality animated surface model of a moving person, with realistic muscle deformation, using just a single static scan and a marker motion capture sequence of the person.
Automatic determination of facial muscle activations from sparse motion capture marker data
Authors: Sifakis Eftychios , Neverov Igor , Fedkiw Ronald
Published: November 2005

We built an anatomically accurate model of facial musculature, passive tissue and underlying skeletal structure using volumetric data acquired from a living male subject. The tissues are endowed with a highly nonlinear constitutive model including controllable anisotropic muscle activations based on fiber directions. Detailed models of this sort can be difficult to animate requiring complex coordinated stimulation of the underlying musculature. We propose a solution to this problem automatically determining muscle activations that track a sparse set of surface landmarks, e.g. acquired from motion capture marker data. Since the resulting animation is obtained via a three dimensional nonlinear finite element method, we obtain visually plausible and anatomically correct deformations with spatial and temporal coherence that provides robustness against outliers in the motion capture data. Moreover, the obtained muscle activations can be used in a robust simulation framework including contact and collision of the face with external objects.
User-configurable automatic shader simplification
Authors: Pellacini Fabio
Published: November 2005

Programmable shading is a fundamental technique for specifying appearance in 3d environments. While shading architectures provides fast execution of shaders, shader evaluation is today a major cost in the rendering process. In the same manner in which geometric simplification lets us deal with large models, it would be beneficial to have an automatic technique that trades off shader quality for speed.This paper presents such a technique by introducing a framework for the automatic simplification of complex procedural shaders, where a sequence of increasingly simplified shaders is generated starting from an original shader together with ranges for all of its input parameters. Our approach works by applying simplification rules to the code of a shader to generate a series of candidates, whose differences from the original one are measured and used to select the candidate with the smallest error. This procedure is repeated until the last shader is a constant. While this automatic procedure generates high quality simplified shaders, the artist might want to emphasize particular aspects of a shader during simplification. Our framework supports this desire by allowing the user to specify additional rules to be considered during simplification. The term
user-configurable
simplification comes from this feature of our system.We implemented our algorithm to support the simplification of fragment shaders running on graphics hardware. Our results show that automatic simplification of complex procedural shaders is possible with high quality.
A relational debugging engine for the graphics pipeline
Authors: Duca Nathaniel , Niski Krzysztof , Bilodeau Jonathan , Bolitho Matthew , Chen Yuan , Cohen Jonathan
Published: November 2005

We present a new, unified approach to debugging graphics software. We propose a representation of all graphics state over the course of program execution as a relational database, and produce a query-based framework for extracting, manipulating, and visualizing data from all stages of the graphics pipeline. Using an SQL-based query language, the programmer can establish functional relationships among all the data, linking OpenGL state to primitives to vertices to fragments to pixels. Based on the Chromium library, our approach requires no modification to or recompilation of the program to be debugged, and forms a superset of many existing techniques for debugging graphics software.
Lpics
Authors: Pellacini Fabio , Vidimče Kiril , Lefohn Aaron , Mohr Alex , Leone Mark , Warren John
Published: November 2005

In computer cinematography, the process of lighting design involves placing and configuring lights to define the visual appearance of environments and to enhance story elements. This process is labor intensive and time consuming, primarily because lighting artists receive poor feedback from existing tools: interactive previews have very poor quality, while final-quality images often take hours to render.This paper presents an interactive cinematic lighting system used in the production of computer-animated feature films containing environments of very high complexity, in which surface and light appearances are described using procedural RenderMan shaders. Our system provides lighting artists with high-quality previews at interactive framerates with only small approximations compared to the final rendered images. This is accomplished by combining numerical estimation of surface response, image-space caching, deferred shading, and the computational power of modern graphics hardware.Our system has been successfully used in the production of two feature-length animated films, dramatically accelerating lighting tasks. In our experience interactivity fundamentally changes an artist's workflow, improving both productivity and artistic expressiveness.
Meshless deformations based on shape matching
Authors: Müller Matthias , Heidelberger Bruno , Teschner Matthias , Gross Markus
Published: November 2005

We present a new approach for simulating deformable objects. The underlying model is geometrically motivated. It handles pointbased objects and does not need connectivity information. The approach does not require any pre-processing, is simple to compute, and provides unconditionally stable dynamic simulations.The main idea of our deformable model is to replace energies by geometric constraints and forces by distances of current positions to goal positions. These goal positions are determined via a generalized shape matching of an undeformed rest state with the current deformed state of the point cloud. Since points are always drawn towards well-defined locations, the overshooting problem of explicit integration schemes is eliminated. The versatility of the approach in terms of object representations that can be handled, the efficiency in terms of memory and computational complexity, and the unconditional stability of the dynamic simulation make the approach particularly interesting for games.
MoXi
Authors: Chu Nelson S.-H. , Tai Chiew-Lan
Published: November 2005

This paper presents a physically-based method for simulating ink dispersion in absorbent paper for art creation purposes. We devise a novel fluid flow model based on the lattice Boltzmann equation suitable for simulating percolation in disordered media, like paper, in real time. Our model combines the simulations of spontaneous shape evolution and porous media flow under a unified framework. We also couple our physics simulation with simple implicit modeling and image-based methods to render high quality output. We demonstrate the effectiveness of our techniques in a digital paint system and achieve various realistic effects of ink dispersion, including complex flow patterns observed in real artwork, and other special effects.
Line drawings from volume data
Authors: Burns Michael , Klawe Janek , Rusinkiewicz Szymon , Finkelstein Adam , DeCarlo Doug
Published: November 2005

Renderings of volumetric data have become an important data analysis tool for applications ranging from medicine to scientific simulation. We propose a volumetric drawing system that directly extracts sparse linear features, such as silhouettes and suggestive contours, using a temporally coherent seed-and-traverse framework. In contrast to previous methods based on isosurfaces or nonrefractive transparency, producing these drawings requires examining an asymptotically smaller subset of the data, leading to efficiency on large data sets. In addition, the resulting imagery is often more comprehensible than standard rendering styles, since it focuses attention on important features in the data. We test our algorithms on datasets up to 512
3
, demonstrating interactive extraction and rendering of line drawings in a variety of drawing styles.
Motion magnification
Authors: Liu Ce , Torralba Antonio , Freeman William T. , Durand Frédo , Adelson Edward H.
Published: November 2005

We present motion magnification, a technique that acts like a microscope for visual motion. It can amplify subtle motions in a video sequence, allowing for visualization of deformations that would otherwise be invisible. To achieve motion magnification, we need to accurately measure visual motions, and group the pixels to be modified. After an initial image registration step, we measure motion by a robust analysis of feature point trajectories, and segment pixels based on similarity of position, color, and motion. A novel measure of motion similarity groups even very small motions according to correlation over time, which often relates to physical cause. An outlier mask marks observations not explained by our layered motion model, and those pixels are simply reproduced on the output from the original registered observations.The motion of any selected layer may be magnified by a user-specified amount; texture synthesis fills-in unseen "holes" revealed by the amplified motions. The resulting motion-magnified images can reveal or emphasize small motions in the original sequence, as we demonstrate with deformations in load-bearing structures, subtle motions or balancing corrections of people, and "rigid" structures bending under hand pressure.
Out-of-core tensor approximation of multi-dimensional matrices of visual data
Authors: Wang Hongcheng , Wu Qing , Shi Lin , Yu Yizhou , Ahuja Narendra
Published: November 2005

Tensor approximation is necessary to obtain compact multilinear models for multi-dimensional visual datasets. Traditionally, each multi-dimensional data item is represented as a vector. Such a scheme flattens the data and partially destroys the internal structures established throughout the multiple dimensions. In this paper, we retain the original dimensionality of the data items to more effectively exploit existing spatial redundancy and allow more efficient computation. Since the size of visual datasets can easily exceed the memory capacity of a single machine, we also present an out-of-core algorithm for higher-order tensor approximation. The basic idea is to partition a tensor into smaller blocks and perform tensor-related operations blockwise. We have successfully applied our techniques to three graphics-related data-driven models, including 6D bidirectional texture functions, 7D dynamic BTFs and 4D volume simulation sequences. Experimental results indicate that our techniques can not only process out-of-core data, but also achieve higher compression ratios and quality than previous methods.
Efficiently combining positions and normals for precise 3D geometry
Authors: Nehab Diego , Rusinkiewicz Szymon , Davis James , Ramamoorthi Ravi
Published: November 2005

Range scanning, manual 3D editing, and other modeling approaches can provide information about the geometry of surfaces in the form of either 3D positions (e.g., triangle meshes or range images) or orientations (normal maps or bump maps). We present an algorithm that combines these two kinds of estimates to produce a new surface that approximates both. Our formulation is linear, allowing it to operate efficiently on complex meshes commonly used in graphics. It also treats high-and low-frequency components separately, allowing it to optimally combine outputs from data sources such as stereo triangulation and photometric stereo, which have different error-vs.-frequency characteristics. We demonstrate the ability of our technique to both recover high-frequency details and avoid low-frequency bias, producing surfaces that are more widely applicable than position or orientation data alone.
Mean value coordinates for closed triangular meshes
Authors: Ju Tao , Schaefer Scott , Warren Joe
Published: November 2005

Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed polygons, mean value coordinates have been proven to be an excellent method for constructing such an interpolant. In this paper, we generalize mean value coordinates from closed 2D polygons to closed triangular meshes. Given such a mesh
P
, we show that these coordinates are continuous everywhere and smooth on the interior of
P
. The coordinates are linear on the triangles of
P
and can reproduce linear functions on the interior of
P
. To illustrate their usefulness, we conclude by considering several interesting applications including constructing volumetric textures and surface deformation.
Defocus video matting
Authors: McGuire Morgan , Matusik Wojciech , Pfister Hanspeter , Hughes John F. , Durand Frédo
Published: November 2005

Video matting is the process of pulling a high-quality alpha matte and foreground from a video sequence. Current techniques require either a known background (e.g., a blue screen) or extensive user interaction (e.g., to specify known foreground and background elements). The matting problem is generally under-constrained, since not enough information has been collected at capture time. We propose a novel, fully autonomous method for pulling a matte using multiple synchronized video streams that share a point of view but differ in their plane of focus. The solution is obtained by directly minimizing the error in filter-based image formation equations, which are over-constrained by our rich data stream. Our system solves the fully dynamic video matting problem without user assistance: both the foreground and background may be high frequency and have dynamic content, the foreground may resemble the background, and the scene is lit by natural (as opposed to polarized or collimated) illumination.
Automatic photo pop-up
Authors: Hoiem Derek , Efros Alexei A. , Hebert Martial
Published: November 2005

This paper presents a fully automatic method for creating a 3D model from a single photograph. The model is made up of several texture-mapped planar billboards and has the complexity of a typical children's pop-up book illustration. Our main insight is that instead of attempting to recover precise geometry, we statistically modelgeometric classesdefined by their orientations in the scene. Our algorithm labels regions of the input image into coarse categories: "ground", "sky", and "vertical". These labels are then used to "cut and fold" the image into a pop-up model using a set of simple assumptions. Because of the inherent ambiguity of the problem and the statistical nature of the approach, the algorithm is not expected to work on every image. However. it performs surprisingly well for a wide range of scenes taken from a typical person's photo album.
Video object cut and paste
Authors: Li Yin , Sun Jian , Shum Heung-Yeung
Published: November 2005

In this paper, we present a system for cutting a moving object out from a video clip. The cutout object sequence can be pasted onto another video or a background image. To achieve this, we first apply a new 3D graph cut based segmentation approach on the spatial-temporal video volume. Our algorithm partitions watershed presegmentation regions into foreground and background while preserving temporal coherence. Then, the initial segmentation result is refined locally. Given two frames in the video sequence, we specify two respective windows of interest which are then tracked using a bi-directional feature tracking algorithm. For each frame in between these two given frames, the segmentation in each tracked window is refined using a 2D graph cut that utilizes a local color model. Moreover, we provide brush tools for the user to control the object boundary precisely wherever needed. Based on the accurate binary segmentation result, we apply coherent matting to extract the alpha mattes and foreground colors of the object.
Surface compression with geometric bandelets
Authors: Peyré Gabriel , Mallat Stéphane
Published: November 2005

This paper describes the construction of second generation bandelet bases and their application to 3D geometry compression. This new coding scheme is orthogonal and the corresponding basis functions are regular. In our method, surfaces are decomposed in a bandelet basis with a fast bandeletization algorithm that removes the geometric redundancy of orthogonal wavelet coefficients. The resulting transform coding scheme has an error decay that is asymptotically optimal for geometrically regular surfaces. We then use these bandelet bases to perform geometry image and normal map compression. Numerical tests show that for complex surfaces bandelets bring an improvement of 1.5dB to 2dB over state of the art compression schemes.
Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition
Authors: Peng Jingliang , Kuo C.-C. Jay
Published: November 2005

A new progressive lossless 3D triangular mesh encoder is proposed in this work, which can encode any 3D triangular mesh with an arbitrary topological structure. Given a mesh, the quantized 3D vertices are first partitioned into an octree (OT) structure, which is then traversed from the root and gradually to the leaves. During the traversal, each 3D cell in the tree front is subdivided into eight childcells. For each cell subdivision, both local geometry and connectivity changes are encoded, where the connectivity coding is guided by the geometry coding. Furthermore, prioritized cell subdivision is performed in the tree front to provide better rate-distortion (RD) performance. Experiments show that the proposed mesh coder outperforms the kd-tree algorithm in both geometry and connectivity coding efficiency. For the geometry coding part, the range of improvement is typically around 10%~20%, but may go up to 50%~60% for meshes with highly regular geometry data and/or tight clustering of vertices.
Variational tetrahedral meshing
Authors: Alliez Pierre , Cohen-Steiner David , Yvinec Mariette , Desbrun Mathieu
Published: November 2005

In this paper, a novel Delaunay-based variational approach to isotropic tetrahedral meshing is presented. To achieve both robustness and efficiency, we minimize a simple mesh-dependent energy through global updates of both vertex positions
and
connectivity. As this energy is known to be the ∠
1
distance between an isotropic quadratic function and its linear interpolation on the mesh, our minimization procedure generates well-shaped tetrahedra. Mesh design is controlled through a gradation smoothness parameter and selection of the desired number of vertices. We provide the foundations of our approach by explaining both the underlying variational principle and its geometric interpretation. We demonstrate the quality of the resulting meshes through a series of examples.
Evaluation of tone mapping operators using a High Dynamic Range display
Authors: Ledda Patrick , Chalmers Alan , Troscianko Tom , Seetzen Helge
Published: November 2005

Tone mapping operators are designed to reproduce visibility and the overall impression of brightness, contrast and color of the real world onto limited dynamic range displays and printers. Although many tone mapping operators have been published in recent years, no thorough psychophysical experiments have yet been undertaken to compare such operators against the real scenes they are purporting to depict. In this paper, we present the results of a series of psychophysical experiments to validate six frequently used tone mapping operators against linearly mapped High Dynamic Range (HDR) scenes displayed on a novel HDR device. Individual operators address the tone mapping issue using a variety of approaches and the goals of these techniques are often quite different from one another. Therefore, the purpose of this investigation was not simply to determine which is the "best" algorithm, but more generally to propose an experimental methodology to validate such operators and to determine the participants' impressions of the images produced compared to what is visible on a high contrast ratio display.
Mesh saliency
Authors: Lee Chang Ha , Varshney Amitabh , Jacobs David W.
Published: November 2005

Research over the last decade has built a solid mathematical foundation for representation and analysis of 3D meshes in graphics and geometric modeling. Much of this work however does not explicitly incorporate models of low-level human visual attention. In this paper we introduce the idea of
mesh saliency
as a measure of regional importance for graphics meshes. Our notion of saliency is inspired by low-level human visual system cues. We define mesh saliency in a scale-dependent manner using a center-surround operator on Gaussian-weighted mean curvatures. We observe that such a definition of mesh saliency is able to capture what most would classify as visually interesting regions on a mesh. The human-perception-inspired importance measure computed by our mesh saliency operator results in more visually pleasing results in processing and viewing of 3D meshes. compared to using a purely geometric measure of shape. such as curvature. We discuss how mesh saliency can be incorporated in graphics applications such as mesh simplification and viewpoint selection and present examples that show visually appealing results from using mesh saliency.
Efficient content-based retrieval of motion capture data
Authors: Müller Meinard , Röder Tido , Clausen Michael
Published: November 2005

The reuse of human motion capture data to create new, realistic motions by applying morphing and blending techniques has become an important issue in computer animation. This requires the identification and extraction of logically related motions scattered within some data set. Such content-based retrieval of motion capture data, which is the topic of this paper, constitutes a difficult and time-consuming problem due to significant spatio-temporal variations between logically related motions. In our approach, we introduce various kinds of qualitative features describing geometric relations between specified body points of a pose and show how these features induce a time segmentation of motion capture data streams. By incorporating spatio-temporal invariance into the geometric features and adaptive segments, we are able to adopt efficient indexing methods allowing for flexible and efficient content-based retrieval and browsing in huge motion capture databases. Furthermore, we obtain an efficient preprocessing method substantially accelerating the cost-intensive classical dynamic time warping techniques for the time alignment of logically similar motion data streams. We present experimental results on a test data set of more than one million frames, corresponding to 180 minutes of motion. The linearity of our indexing algorithms guarantees the scalability of our results to much larger data sets.
Performance animation from low-dimensional control signals
Authors: Chai Jinxiang , Hodgins Jessica K.
Published: November 2005

This paper introduces an approach to performance animation that employs video cameras and a small set of retro-reflective markers to create a low-cost, easy-to-use system that might someday be practical for home use. The low-dimensional control signals from the user's performance are supplemented by a database of pre-recorded human motion. At run time, the system automatically learns a series of local models from a set of motion capture examples that are a close match to the marker locations captured by the cameras. These local models are then used to reconstruct the motion of the user as a full-body animation. We demonstrate the power of this approach with real-time control of six different behaviors using two video cameras and a small set of retro-reflective markers. We compare the resulting animation to animation from commercial motion capture equipment with a full set of markers.
Dynamic response for motion capture animation
Authors: Zordan Victor Brian , Majkowska Anna , Chiu Bill , Fast Matthew
Published: November 2005

Human motion capture embeds rich detail and style which is difficult to generate with competing animation synthesis technologies. However, such recorded data requires principled means for creating responses in unpredicted situations, for example reactions immediately following impact. This paper introduces a novel technique for incorporating unexpected impacts into a motion capture-driven animation system through the combination of a physical simulation which responds to contact forces and a specialized search routine which determines the best plausible re-entry into motion library playback following the impact. Using an actuated dynamic model, our system generates a physics-based response while connecting motion capture segments. Our method allows characters to respond to unexpected changes in the environment based on the specific dynamic effects of a given contact while also taking advantage of the realistic movement made available through motion capture. We show the results of our system under various conditions and with varying responses using martial arts motion capture as a testbed.
Real-time rendering of plant leaves
Authors: Wang Lifeng , Wang Wenle , Dorsey Julie , Yang Xu , Guo Baining , Shum Heung-Yeung
Published: November 2005

This paper presents a framework for the real-time rendering of plant leaves with global illumination effects. Realistic rendering of leaves requires a sophisticated appearance model and accurate lighting computation. For leaf appearance we introduce a parametric model that describes leaves in terms of spatially-variant BRDFs and BTDFs. These BRDFs and BTDFs, incorporating analysis of subsurface scattering inside leaf tissues and rough surface scattering on leaf surfaces, can be measured from real leaves. More importantly, this description is compact and can be loaded into graphics hardware for fast run-time shading calculations, which are essential for achieving high frame rates. For lighting computation, we present an algorithm that extends the Precomputed Radiance Transfer (PRT) approach to all-frequency lighting for leaves. In particular, we handle the combined illumination effects due to low-frequency environment light and high-frequency sunlight. This is done by decomposing the local incident radiance of sunlight into direct and indirect components. The direct component, which contains most of the high frequencies, is not pre-computed with spherical harmonics as in PRT; instead it is evaluated on-the-fly using pre-computed light-visibility convolution data. We demonstrate our framework by the rendering of a variety of leaves and assemblies thereof.