bluuebunny/crossref_metadata_2025 huggingface dataset:
The RC2000
Authors: Lawrence J. L.
Published: October 2004

The literature is replete with software horror stories. Despite all the planning and case studies, software projects all too frequently fall short of expectations or utterly fail. In this article, a case study is made of a project in which software was delivered on time and under budget. The factors contributing to the success are emphasized as well as some factors which prevented an even greater success. This article describes the development of a General Electric Company product, but the opinions expressed herein are solely those of the author. The procedures described and comments made do not reflect an official endorsement by General Electric Company or its employees.
The MCC software technology program
Authors: Belady Les , Richter Charles
Published: October 2004

The Microelectronics and Computer Technology Corporation (MCC) is an industry consortium formed to conduct long-range research and develop computer technology in seven general areas. One of those areas is software technology, specifically the technology employed during the development of software systems. This paper outlines that research program, the MCC Software Technology Program.
Functional composition
Authors: Garg Vijay Kumar
Published: October 2004

We propose a mechanism to compose programs, which is more general than pipe facility and which provides more uniform model of computation to the user.
An EVES update
Authors: Craigen Dan , Saaltink Mark
Published: October 2004

This brief note discusses the status and goals of the "Euclid-based Verification and Evaluation System" project, currently underway at I. P. Sharp Associates.
The Practical Verification System Project
Authors: Williams James , Applebaum Charles
Published: October 2004

The purpose of this paper is to briefly describe the Practical Verification System (PVS), discuss its current implementation status, and sketch long term development plans. We begin with a review of ideas leading up to the PVS design.
Position paper to be presented at "Verification workshop III (verkshop III)" to be held in Watsonville, CA. Feb. 18--21, 1985
Authors: Smith Brian T.
Published: October 2004

This position paper describes a hardware and software verification effort at Argonne National Laboratory based upon the LMA (Logic Machine Architecture) collection of Pascal procedures. The reasoning component of the system is the Interactive Theorem Prover (ITP), a Pascal program using the procedures of LMA. ITP is in effect an enhanced portable implementation of our previous reasoning system AURA. A verification condition generator for the software will be developed using tools such as the TAMPR program transformation system. The resulting system is being applied to prove claims about hardware/software used in a control system running on a fault-tolerant computer.
Enhancing FDM for the expression of concurrency requirements
Authors: Pixon Mark R.
Published: October 2004

This paper describes extensions to SDC's Formal Development Methodology that support formal specification and verification of concurrent system requirements. It outlines antecedents from first-order temporal predicate logic for these extensions and how they will be implemented.
A rapid prototyping system based on data flow principles
Authors: Tate Graham , Docker Thomas W. G.
Published: October 2004

Data flow diagrams are commonly used in a semi-formal way (together with other associated tools) for the specification of a wide range of data processing applications. The main associated tools are those used for the definitions of data flows and processes, namely so-called data dictionaries, better perhaps lerned system or application dictionaries. A system is described which builds a directly executable model of an application from a data flow diagram/application dictionary specification. The system has certain analogies with data flow machines and languages, and with simulation systems. It is described as a rapid prototyping system because the application specification requirements are minimal, although performance may not be particularly efficient.
Agent trade servers in financial exchange systems
Authors: Lybäck David , Boman Magnus
Published: October 2004

New services based on the best-effort paradigm could complement the current deterministic services of an electronic financial exchange. Four crucial aspects of such systems would benefit from a hybrid stance: proper use of processing resources, bandwidth management, fault tolerance, and exception handling. We argue that a more refined view on Quality-of-Service control for exchange systems, in which the principal ambition of upholding a fair and orderly marketplace is left uncompromised, would benefit all interested parties.
Basic theory of feature trees
Authors: Mielniczuk Pawel
Published: October 2004

We present a decision algorithm for the problem
Val
(
FT
) of deciding validity of first-order sentences in the theory of feature trees. Its time complexity is exp
⌊c·m⌋
(
c
·
n
) where
n
is the length of a sentence,
m
is the quantifier depth of a sequence, and
c
is a constant. The function exp

i

(
j
) is an exponential tower of 2's of height
i
, to power
j
(exp
0
(
j
) =
j
and exp

i
+1

(
j
) = 2

exp

i

(
j
)

). Moreover we prove that the presented algorithm is optimal, deriving a lower bound which matches the upper one.
Software validation via scalable path-sensitive value flow analysis
Authors: Dor Nurit , Adams Stephen , Das Manuvir , Yang Zhe
Published: October 2004

In this paper, we present a new algorithm for tracking the flow of values through a program. Our algorithm represents a substantial improvement over the state of the art. Previously described value flow analyses that are control-flow sensitive do not scale well, nor do they eliminate value flow information from infeasible execution paths (
i.e.
, they are path-insensitive). Our algorithm scales to large programs, and it is path-sensitive.The efficiency of our algorithm arises from three insights: The value flow problem can be "bit-vectorized" by tracking the flow of one value at a time; dataflow facts from different execution paths with the same value flow information can be merged; and information about complex aliasing that affects value flow can be plugged in from a different analysis.We have incorporated our analysis in ESP, a software validation tool. We have used ESP to validate the Windows operating system kernel (a million lines of code) against an important security property. This experience suggests that our algorithm scales to large programs, and is accurate enough to trace the flow of values in real code.
An empirical study of profiling strategies for released software and their impact on testing activities
Authors: Elbaum Sebastian , Hardojo Madeline
Published: October 2004

An understanding of how software is employed in the field can yield many opportunities for quality improvements. Profiling released software can provide such an understanding. However, profiling released software is diffcult due to the potentially large number of deployed sites that must be profiled, the extreme transparency expectations, and the remote data collection and deployment management process. Researchers have recently proposed various approaches to tap into the opportunities and overcome those challenges. Initial studies have illustrated the application of these approaches and have shown their feasibility. Still, the promising proposed approaches, and the tradeoffs between overhead, accuracy, and potential benefits for the testing activity have been barely quantified. This paper aims to over-come those limitations. Our analysis of 1200 user sessions on a 155 KLOC system substantiates the ability of field data to support test suite improvements, quantifies different approaches previously introduced in isolation, and assesses the efficiency of profiling techniques for released software and the effectiveness of their associated testing efforts.
Where the bugs are
Authors: Ostrand Thomas J. , Weyuker Elaine J. , Bell Robert M.
Published: October 2004

The ability to predict which files in a large software system are most likely to contain the largest numbers of faults in the next release can be a very valuable asset. To accomplish this, a negative binomial regression model using information from previous releases has been developed and used to predict the numbers of faults for a large industrial inventory system. The files of each release were sorted in descending order based on the predicted number of faults and then the first 20% of the files were selected. This was done for each of fifteen consecutive releases, representing more than four years of field usage. The predictions were extremely accurate, correctly selecting files that contained between 71% and 92% of the faults, with the overall average being 83%. In addition, the same model was used on data for the same system's releases, but with all fault data prior to integration testing removed. The prediction was again very accurate, ranging from 71% to 93%, with the average being 84%. Predictions were made for a second system, and again the first 20% of files accounted for 83% of the identified faults. Finally, a highly simplified predictor was considered which correctly predicted 73% and 74% of the faults for the two systems.
Automated black-box testing of functional correctness using function approximation
Authors: Meinke Karl
Published: October 2004

We consider black-box testing of functional correctness as a special case of a satisfiability or constraint solving problem. We introduce a general method for solving this problem based on function approximation. We then describe some practical results obtained for an automated testing algorithm using approximation by piecewise polynomial functions.
An optimizing compiler for batches of temporal logic formulas
Authors: Ezick James
Published: October 2004

Model checking based on validating temporal logic formulas has proven practical and effective for numerous software engineering applications. As systems based on this approach have become more mainstream, a need has arisen to deal effectively with large batches of formulas over a common model. Presently, most systems validate formulas one at a time, with little or no interaction between validation of separate formulas. This is the case despite the fact that, for a wide range of applications, a certain level of redundancy between domain-related formulas can be anticipated.This paper presents an optimizing compiler for batches of temporal logic formulas. A component of the Carnauba model checking system, this compiler addresses the need to handle batches of temporal logic formulas by leveraging the framework common to optimizing programming language compilers. Just as traditional optimizing compilers attempt to exploit redundancy and other solvable properties in a program to reduce the demand on a runtime system, this compiler exploits similar properties in groups of formulas to reduce the demand on a model checking engine. Optimizations are performed via a set of distinct, interchangeable optimization passes operating on a common intermediate representation. The intermediate representation captures the full modal mu-calculus, and the optimization techniques are applicable to any temporal logic subsumed by that logic. The compiler offers a unified framework for expressing some well understood single-formula optimizations as well as numerous inter-formula optimizations that capitalize on redundancy, logical implication, and, optionally, model-specific knowledge. It is capable of working either in place of, or as a preprocessor for, other optimization algorithms. The result is a system that, when applied to a potentially heterogeneous collection of formulas over a common problem domain, is able to measurably reduce the time and space requirements of the subsequent model checking engine.
Improving the adaptability of multi-mode systems via program steering
Authors: Lin Lee , Ernst Michael D.
Published: October 2004

A multi-mode software system contains several distinct modes of operation and a controller for deciding when to switch between modes. Even when developers rigorously test a multi-mode system before deployment, they cannot foresee and test for every possible usage scenario. As a result, unexpected situations in which the program fails or underperforms (for example, by choosing a non-optimal mode) may arise. This research aims to mitigate such problems by creating a new mode selector that examines the current situation, then chooses a mode that has been successful in the past, in situations like the current one. The technique, called program steering, creates a new mode selector via machine learning from good behavior in testing or in successful operation. Such a strategy, which generalizes the knowledge that a programmer has built into the system, may select an appropriate mode even when the original controller cannot. We have performed experiments on robot control programs written in a month-long programming competition. Augmenting these programs via our program steering technique had a substantial positive effect on their performance in new environments.
Slicing tools for synchronous reactive programs
Authors: Ramesh S. , Kulkarni A. , Kamat V.
Published: October 2004

In this paper, we present two slicing tools: VHDL_Slice and Est_slice that compute static executable slices of VHDL and Esterel programs respectively. The slicers have been tested on a number of small and medium sized examples.
Faster constraint solving with subtypes
Authors: Edwards Jonathan , Jackson Daniel , Torlak Emina , Yeung Vincent
Published: October 2004

Constraints in predicate or relational logic can be translated into boolean logic and solved with a SAT solver. For faster solving, it is common to exploit the typing of predicates or relations, in order to reduce the number of boolean variables needed to encode the constraint. Here we show how to extend this idea to constraints expressed in a language with subtyping. Our technique, called
atomization
, refactors the type hierarchy into a flat collection of disjoint atomic types. The constraints are then decomposed into equivalent constraints involving smaller relations or predicates over these new types, which can then be solved in the normal fashion. Experiments with an implementation of this technique within the Alloy Analyzer show improved performance on practical software checking problems.
SABER
Authors: Reimer Darrell , Schonberg Edith , Srinivas Kavitha , Srinivasan Harini , Alpern Bowen , Johnson Robert D. , Kershenbaum Aaron , Koved Larry
Published: October 2004

In this paper, we present an approach to automatically detect high impact coding errors in large Java applications which use frameworks. These high impact errors cause serious performance degradation and outages in real world production environments, are very time-consuming to detect, and potentially cost businesses thousands of dollars. Based on 3 years experience working with IBM customer production systems, we have identified over 400 high impact coding patterns, from which we have been able to distill a small set of pattern detection algorithms. These algorithms use deep static analysis, thus moving problem detection earlier in the development cycle from production to development. Additionally, we have developed an automatic false positive filtering mechanism based on domain specific knowledge to achieve a level of usability acceptable to IBM field engineers. Our approach also provides necessary contextual information around the sources of the problems to help in problem remediation. We outline how our approach to problem determination can be extended to multiple programming models and domains. We have implemented this problem determination approach in the SABER tool and have used it successfully to detect many serious code defects in several large commercial applications. This paper shows results from four such applications that had over 60 coding defects.
Simultaneous shield insertion and net ordering for capacitive and inductive coupling minimization
Authors: Lepak Kevin M. , Xu Min , Chen Jun , He Lei
Published: October 2004

In this article, we first show that existing net ordering formulations to minimize noise are no longer sufficient with the presence of inductive noise, and shield insertion is needed to minimize inductive noise. Using a
K

eff

model as the figure of merit for inductive coupling, we then formulate two simultaneous shield insertion and net ordering (SINO) problems: the optimal SINO/NF problem to find a minimal area SINO solution that is free of capacitive and inductive noise, and the optimal SINO/NB problem to find a minimal area SINO solution that is free of capacitive noise and is under the given inductive noise bound. We reveal that both optimal SINO problems are NP-hard, and propose effective approximate algorithms for the two problems. Experiments show that our SINO/NB algorithm uses from 51% to 82% fewer shields compared to uniform shield insertion and net ordering (US + NO), and uses from 4% to 47% fewer shields compared to separated net ordering and shield insertion (NO + SI). Furthermore, the SINO/NB solutions under practical noise bounds use from 38% to 61% fewer shields compared to SINO/NF solutions, and use up to 36% fewer shields compared to the theoretical lower bound for optimal SINO/NF solutions. Moreover, we show that the
K

eff

model has a high fidelity versus the noise voltage computed using accurate RLC circuit models and SPICE simulations. To the best of our knowledge, it is the first work that presents an in-depth study on the automatic layout optimization of multiple nets to minimize both capacitive and inductive noise.
Annealing placement by thermodynamic combinatorial optimization
Authors: Vicente Juan D , Lanchares Juan , Hermida Román
Published: October 2004

Placement is key issue of integrated circuit physical design. There exist some techniques inspired in thermodynamics coping with this problem as Simulated Annealing. In this article, we present a combinatorial optimization method directly derived from both Thermodynamics and Information Theory. In TCO (Thermodynamic Combinatorial Optimization), two kinds of processes are considered: microstate and macrostate transformations. Applying the Shannon's definition of entropy to reversible microstate transformations, a probability of acceptance based on Fermi--Dirac statistics is derived. On the other hand, applying thermodynamic laws to macrostate transformations, an efficient annealing schedule is provided. TCO has been compared with a custom Simulated Annealing (SA) tool on a set of benchmark circuits for the FPGA (Field Programmable Gate Arrays) placement problem. TCO has provided the high-quality results of SA, while inheriting the adaptive properties of Natural Optimization (NO).
An adaptive cryptographic engine for internet protocol security architectures
Authors: Dandalis Andreas , Prasanna Viktor K.
Published: October 2004

Architectures that implement the Internet Protocol Security (IPSec) standard have to meet the enormous computing demands of cryptographic algorithms. In addition, IPSec architectures have to be flexible enough to adapt to diverse security parameters. This article proposes an FPGA-based Adaptive Cryptographic Engine (ACE) for IPSec architectures. By taking advantage of FPGA technology, ACE can adapt to diverse security parameters on the fly while providing superior performance compared with software-based solutions. In this paper, we focus on performance issues. A diverse set of private-key cryptographic algorithms is utilized to demonstrate the applicability of the proposed cryptographic engine. The time performance metrics are throughput and key-setup latency. The latency metric is the most important measure for IPSec where a small amount of data is processed per key and key context switching occurs repeatedly. We are not aware of any published results that include extensive key-setup latency results.
Frequent value encoding for low power data buses
Authors: Yang Jun , Gupta Rajiv , Zhang Chuanjun
Published: October 2004

Since the I/O pins of a CPU are a significant source of energy consumption, work has been done on developing encoding schemes for reducing switching activity on external buses. Modest reductions in switching can be achieved for data and address buses using a number of general purpose encoding schemes. However, by exploiting the characteristic of memory reference locality, switching activity on the address bus can be reduced by as much as 66%. Till now no characteristic has been identified that can be used to achieve similar reductions in switching activity on the data bus. We have discovered a characteristic of values transmitted over the data bus according to which a small number of distinct values, called
frequent values
, account for 32% of transmissions over the external data bus. Exploiting this characteristic we have developed an encoding scheme that we call the
FV encoding
scheme. To implement this scheme we have also developed a technique for dynamically identifying the frequent values which compares quite favorably with an optimal offline algorithm. Our experiments show that FV encoding of 32 frequent values yields an average reduction of 30% (with on-chip data cache) and 49% (without on-chip data cache) in data bus switching activity for SPEC95 and mediabench programs. Moreover the reduction in switching achieved by FV encoding is
2 to 4
times the reduction achieved by the
bus-invert
coding scheme and
1.5 to 3
times the reduction achieved by the
adaptive method
. The overall energy savings on data bus we attained considering the coder overhead is 29%.
An integrated approach to engineer and enforce context constraints in RBAC environments
Authors: Strembeck Mark , Neumann Gustaf
Published: October 2004

We present an approach that uses special purpose role-based access control (RBAC) constraints to base certain access control decisions on context information. In our approach a
context constraint
is defined as a dynamic RBAC constraint that checks the actual values of one or more contextual attributes for predefined conditions. If these conditions are satisfied, the corresponding access request can be permitted. Accordingly, a
conditional permission
is an RBAC permission that is constrained by one or more context constraints. We present an engineering process for context constraints that is based on goal-oriented requirements engineering techniques, and describe how we extended the design and implementation of an existing RBAC service to enable the enforcement of context constraints. With our approach we aim to preserve the advantages of RBAC and offer an additional means for the definition and enforcement of fine-grained context-dependent access control policies.
Content-triggered trust negotiation
Authors: Hess Adam , Holt Jason , Jacobson Jared , Seamons Kent E.
Published: October 2004

The focus of access control in client/server environments is on protecting sensitive server resources by determining whether or not a client is authorized to access those resources. The set of resources is usually static, and an access control policy associated with each resource specifies who is authorized to access the resource. In this article, we turn the traditional client/server access control model on its head and address how to protect the sensitive content that clients disclose to and receive from servers. Since client content is often dynamically generated at run-time, the usual approach of associating a policy with the resource (content) a priori does not work. We propose a general-purpose access control model designed to detect whenever sensitive information is being transmitted, and determine whether the sender or receiver is authorized. The model identifies sensitive content, maps the sensitive content to an access control policy, and establishes the trustworthiness of the sender or receiver before the sensitive content is disclosed or received. We have implemented the model within TrustBuilder, an architecture for negotiating trust between strangers based on properties other than identity. The implementation targets open systems, where clients and servers do not have preexisting trust relationships. The implementation is the first example of content-triggered trust negotiation. It currently supports access control for sensitive content disclosed by web and email clients.
On the performance of group key agreement protocols
Authors: Amir Yair , Kim Yongdae , Nita-Rotaru Cristina , Tsudik Gene
Published: October 2004

Group key agreement is a fundamental building block for secure peer group communication systems. Several group key management techniques were proposed in the last decade, all assuming the existence of an underlying group communication infrastructure to provide reliable and ordered message delivery as well as group membership information. Despite analysis, implementation, and deployment of some of these techniques, the actual costs associated with group key management have been poorly understood so far. This resulted in an undesirable tendency: on the one hand, adopting suboptimal security for reliable group communication, while, on the other hand, constructing excessively costly group key management protocols.This paper presents a thorough performance evaluation of five notable distributed key management techniques (for collaborative peer groups) integrated with a reliable group communication system. An in-depth comparison and analysis of the five techniques is presented based on experimental results obtained in actual local- and wide-area networks. The extensive performance measurement experiments conducted for all methods offer insights into their scalability and practicality. Furthermore, our analysis of the experimental results highlights several observations that are not obvious from the theoretical analysis.
Obituary
Authors: Henderson Austin
Published: October 2004

A remembrance.
Branding 101
Authors: Marcus Aaron
Published: October 2004

In 2001, CHI featured an unusual panel session: Marketing people were actually invited to come to CHI to explain what they did and why it was important to the objectives of SIGCHI. Boyd de Groot, Peter Eikelboom, and Florian Egger organized the session in which I was privileged to participate. As they remarked about how extraordinary it was to have dedicated marketing professionals at CHI, especially in presenter roles, the comments being exchanged among CHI professionals gave me the feeling that I was in a "Dilbert" comic strip, listening to the amusing, outrageous jibes of those characters.
Cultural probes and the value of uncertainty
Authors: Gaver William W. , Boucher Andrew , Pennington Sarah , Walker Brendan
Published: October 2004

When reason is away, smiles will play.     --- Paul Eluard and Benjamin Péret
NordiCHI 2004
Authors: Campbell Marisa
Published: October 2004

NordiCHI 2004
October 23-27, 2004
Tampere, Finland
Band moiré images
Authors: Hersch Roger David , Chosson Sylvain
Published: October 2004

We propose a new powerful way of synthesizing moiré images that enables the creation of dynamically moving messages incorporating text, symbols, and color elements. Moiré images appear when superposing a base layer made of replicated base bands and a revealing layer made of a line grating comprising thin transparent lines. Each replicated base band contains the same image, e.g. text or color motifs. Since the base bands and the revealing line grating have similar periods, the revealed moiré image is the image located within each base band, enlarged along one dimension. By considering the formation of the moiré image as a line sampling process, we derive the linear transformation between the base layer and the moiré image. We obtain the geometric layout of the resulting moiré image, i.e. its orientation, size and displacement direction when moving the revealing layer on top of the base layer. Interesting moiré images can be synthesized by applying geometric transformations to both the base and the revealing layers. We propose a mathematical model describing the geometric transformation that a moiré image undergoes, when its base layer and its revealing layer are subject to different freely chosen non-linear geometric transformations. By knowing in advance the layout of a moiré image as a function of the layouts of the base layer and of the revealing layer, we are able to create moiré components running up and down at different speeds and orientations upon translation of the revealing layer. We also derive layer transformations which yield periodic moiré images despite the fact that both the base and the revealing layers are curved. By offering a new means of artistic expression, band moiré images can be used to create new designs and to synthesize visually appealing applications.
Defining point-set surfaces
Authors: Amenta Nina , Kil Yong Joo
Published: October 2004

The MLS surface [Levin 2003], used for modeling and rendering with point clouds, was originally defined algorithmically as the output of a particular meshless construction. We give a new explicit definition in terms of the critical points of an energy function on lines determined by a vector field. This definition reveals connections to research in computer vision and computational topology.Variants of the MLS surface can be created by varying the vector field and the energy function. As an example, we define a similar surface determined by a cloud of surfels (points equipped with normals), rather than points.We also observe that some procedures described in the literature to take points in space onto the MLS surface fail to do so, and we describe a simple iterative procedure which does.
T-spline simplification and local refinement
Authors: Sederberg Thomas W. , Cardon David L. , Finnigan G. Thomas , North Nicholas S. , Zheng Jianmin , Lyche Tom
Published: October 2004

A typical NURBS surface model has a large percentage of superfluous control points that significantly interfere with the design process. This paper presents an algorithm for eliminating such superfluous control points, producing a T-spline. The algorithm can remove substantially more control points than competing methods such as B-spline wavelet decomposition. The paper also presents a new T-spline local refinement algorithm and answers two fundamental open questions on T-spline theory.
Energy-minimizing splines in manifolds
Authors: Hofer Michael , Pottmann Helmut
Published: October 2004

Variational interpolation in curved geometries has many applications, so there has always been demand for geometrically meaningful and efficiently computable
splines
in manifolds. We extend the definition of the familiar cubic spline curves and splines in tension, and we show how to compute these on parametric surfaces, level sets, triangle meshes, and point samples of surfaces. This list is more comprehensive than it looks, because it includes variational motion design for animation, and allows the treatment of obstacles via barrier surfaces. All these instances of the general concept are handled by the same geometric optimization algorithm, which minimizes an energy of curves on surfaces of arbitrary dimension and codimension.
"GrabCut"
Authors: Rother Carsten , Kolmogorov Vladimir , Blake Andrew
Published: October 2004

The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.
Poisson matting
Authors: Sun Jian , Jia Jiaya , Tang Chi-Keung , Shum Heung-Yeung
Published: October 2004

In this paper, we formulate the problem of natural image matting as one of solving Poisson equations with the matte gradient field. Our approach, which we call
Poisson matting
, has the following advantages. First, the matte is directly reconstructed from a continuous matte gradient field by solving Poisson equations using boundary information from a user-supplied trimap. Second, by interactively manipulating the matte gradient field using a number of filtering tools, the user can further improve Poisson matting results locally until he or she is satisfied. The modified local result is seamlessly integrated into the final result. Experiments on many complex natural images demonstrate that Poisson matting can generate good matting results that are not possible using existing matting techniques.
RFIG lamps
Authors: Raskar Ramesh , Beardsley Paul , van Baar Jeroen , Wang Yao , Dietz Paul , Lee Johnny , Leigh Darren , Willwacher Thomas
Published: October 2004

This paper describes how to instrument the physical world so that objects become self-describing, communicating their identity, geometry, and other information such as history or user annotation. The enabling technology is a wireless tag which acts as a radio frequency identity and geometry (RFIG) transponder. We show how addition of a photo-sensor to a wireless tag significantly extends its functionality to allow
geometric
operations - such as finding the 3D position of a tag, or detecting change in the shape of a tagged object. Tag data is presented to the user by direct projection using a handheld locale-aware mobile projector. We introduce a novel technique that we call interactive projection to allow a user to interact with projected information e.g. to navigate or update the projected information.The ideas are demonstrated using objects with active radio frequency (RF) tags. But the work was motivated by the advent of unpowered passive-RFID, a technology that promises to have significant impact in real-world applications. We discuss how our current prototypes could evolve to passive-RFID in the future.
Fluid control using the adjoint method
Authors: McNamara Antoine , Treuille Adrien , Popović Zoran , Stam Jos
Published: October 2004

We describe a novel method for controlling physics-based fluid simulations through gradient-based nonlinear optimization. Using a technique known as the
adjoint method
, derivatives can be computed efficiently, even for large 3D simulations with millions of control parameters. In addition, we introduce the first method for the full control of free-surface liquids. We show how to compute adjoint derivatives through each step of the simulation, including the fast marching algorithm, and describe a new set of control parameters specifically designed for liquids.
Simulating water and smoke with an octree data structure
Authors: Losasso Frank , Gibou Frédéric , Fedkiw Ron
Published: October 2004

We present a method for simulating water and smoke on an
unrestricted
octree data structure exploiting mesh refinement techniques to capture the small scale visual detail. We propose a new technique for discretizing the Poisson equation on this octree grid. The resulting linear system is symmetric positive definite enabling the use of fast solution methods such as preconditioned conjugate gradients, whereas the standard approximation to the Poisson equation on an octree grid results in a non-symmetric linear system which is more computationally challenging to invert. The semi-Lagrangian characteristic tracing technique is used to advect the velocity, smoke density, and even the level set making implementation on an octree straightforward. In the case of smoke, we have multiple refinement criteria including object boundaries, optical depth, and vorticity concentration. In the case of water, we refine near the interface as determined by the zero isocontour of the level set function.
A method for animating viscoelastic fluids
Authors: Goktekin Tolga G. , Bargteil Adam W. , O'Brien James F.
Published: October 2004

This paper describes a technique for animating the behavior of viscoelastic fluids, such as mucus, liquid soap, pudding, toothpaste, or clay, that exhibit a combination of both fluid and solid characteristics. The technique builds upon prior Eulerian methods for animating incompressible fluids with free surfaces by including additional elastic terms in the basic Navier-Stokes equations. The elastic terms are computed by integrating and advecting strain-rate throughout the fluid. Transition from elastic resistance to viscous flow is controlled by von Mises's yield condition, and subsequent behavior is then governed by a quasi-linear plasticity model.
Fast hierarchical importance sampling with blue noise properties
Authors: Ostromoukhov Victor , Donohue Charles , Jodoin Pierre-Marc
Published: October 2004

This paper presents a novel method for efficiently generating a good sampling pattern given an importance density over a 2D domain. A Penrose tiling is hierarchically subdivided creating a sufficiently large number of sample points. These points are numbered using the Fibonacci number system, and these numbers are used to threshold the samples against the local value of the importance density. Pre-computed correction vectors, obtained using relaxation, are used to improve the spectral characteristics of the sampling pattern. The technique is deterministic and very fast; the sampling time grows linearly with the required number of samples. We illustrate our technique with importance-based environment mapping, but the technique is versatile enough to be used in a large variety of computer graphics applications, such as light transport calculations, digital halftoning, geometry processing, and various rendering techniques.
Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces
Authors: Safonova Alla , Hodgins Jessica K. , Pollard Nancy S.
Published: October 2004

Optimization is an appealing way to compute the motion of an animated character because it allows the user to specify the desired motion in a sparse, intuitive way. The difficulty of solving this problem for complex characters such as humans is due in part to the high dimensionality of the search space. The dimensionality is an artifact of the problem representation because most dynamic human behaviors are intrinsically low dimensional with, for example, legs and arms operating in a coordinated way. We describe a method that exploits this observation to create an optimization problem that is easier to solve. Our method utilizes an existing motion capture database to find a low-dimensional space that captures the properties of the desired behavior. We show that when the optimization problem is solved within this low-dimensional subspace, a sparse sketch can be used as an initial guess and full physics constraints can be enabled. We demonstrate the power of our approach with examples of forward, vertical, and turning jumps; with running and walking; and with several acrobatic flips.
Synthesizing animations of human manipulation tasks
Authors: Yamane Katsu , Kuffner James J. , Hodgins Jessica K.
Published: October 2004

Even such simple tasks as placing a box on a shelf are difficult to animate, because the animator must carefully position the character to satisfy geometric and balance constraints while creating motion to perform the task with a natural-looking style. In this paper, we explore an approach for animating characters manipulating objects that combines the power of path planning with the domain knowledge inherent in data-driven, constraint-based inverse kinematics. A path planner is used to find a motion for the object such that the corresponding poses of the character satisfy geometric, kinematic, and posture constraints. The inverse kinematics computation of the character's pose resolves redundancy by biasing the solution toward natural-looking poses extracted from a database of captured motions. Having this database greatly helps to increase the quality of the output motion. The computed path is converted to a motion trajectory using a model of the velocity profile. We demonstrate the effectiveness of the algorithm by generating animations across a wide range of scenarios that cover variations in the geometric, kinematic, and dynamic models of the character, the manipulated object, and obstacles in the scene.
Pitching a baseball
Authors: Theobalt Christian , Albrecht Irene , Haber Jörg , Magnor Marcus , Seidel Hans-Peter
Published: October 2004

Athletes and coaches in most professional sports make use of high-tech equipment to analyze and, subsequently, improve the athlete's performance. High-speed video cameras are employed, for instance, to record the swing of a golf club or a tennis racket, the movement of the feet while running, and the body motion in apparatus gymnastics. High-tech and high-speed equipment, however, usually implies high-cost as well. In this paper, we present a passive optical approach to capture high-speed motion using multi-exposure images obtained with low-cost commodity still cameras and a stroboscope. The recorded motion remains completely undisturbed by the motion capture process. We apply our approach to capture the motion of hand and ball for a variety of baseball pitches and present algorithms to automatically track the position, velocity, rotation axis, and spin of the ball along its trajectory. To demonstrate the validity of our setup and algorithms, we analyze the consistency of our measurements with a physically based model that predicts the trajectory of a spinning baseball. Our approach can be applied to capture a wide variety of other high-speed objects and activities such as golfing, bowling, or tennis for visualization as well as analysis purposes.
Automated extraction and parameterization of motions in large data sets
Authors: Kovar Lucas , Gleicher Michael
Published: October 2004

Large motion data sets often contain many variants of the same kind of motion, but without appropriate tools it is difficult to fully exploit this fact. This paper provides automated methods for identifying logically similar motions in a data set and using them to build a continuous and intuitively parameterized space of motions. To find logically similar motions that are numerically dissimilar, our search method employs a novel distance metric to find "close" motions and then uses them as intermediaries to find more distant motions. Search queries are answered at interactive speeds through a precomputation that compactly represents all possibly similar motion segments. Once a set of related motions has been extracted, we automatically register them and apply blending techniques to create a continuous space of motions. Given a function that defines relevant motion parameters, we present a method for extracting motions from this space that accurately possess new parameters requested by the user. Our algorithm extends previous work by explicitly constraining blend weights to reasonable values and having a run-time cost that is nearly independent of the number of example motions. We present experimental results on a test data set of 37,000 frames, or about ten minutes of motion sampled at 60 Hz.
Obscuring length changes during animated motion
Authors: Harrison Jason , Rensink Ronald A. , van de Panne Michiel
Published: October 2004

In this paper we examine to what extent the lengths of the links in an animated articulated-figure can be changed without the viewer being aware of the change. This is investigated in terms of a framework that emphasizes the role of attention in visual perception. We conducted a set of five experiments to establish bounds for the sensitivity to changes in length as a function of several parameters and the amount of attention available. We found that while length changes of 3% can be perceived when the relevant links are given full attention, changes of over 20% can go unnoticed when attention is not focused in this way. These results provide general guidelines for algorithms that produce or process character motion data and also bring to light some of the potential gains that stand to be achieved with attention-based algorithms.
Video tooning
Authors: Wang Jue , Xu Yingqing , Shum Heung-Yeung , Cohen Michael F.
Published: October 2004

We describe a system for transforming an input video into a highly abstracted, spatio-temporally coherent cartoon animation with a range of styles. To achieve this, we treat video as a space-time volume of image data. We have developed an anisotropic kernel mean shift technique to segment the video data into contiguous volumes. These provide a simple cartoon style in themselves, but more importantly provide the capability to semi-automatically rotoscope semantically meaningful regions.In our system, the user simply outlines objects on keyframes. A mean shift guided interpolation algorithm is then employed to create three dimensional semantic regions by interpolation between the keyframes, while maintaining smooth trajectories along the time dimension. These regions provide the basis for creating smooth two dimensional edge sheets and stroke sheets embedded within the spatio-temporal video volume. The regions, edge sheets, and stroke sheets are rendered by slicing them at particular times. A variety of styles of rendering are shown. The temporal coherence provided by the smoothed semantic regions and sheets results in a temporally consistent non-photorealistic appearance.
Video matching
Authors: Sand Peter , Teller Seth
Published: October 2004

This paper describes a method for bringing two videos (recorded at different times) into spatiotemporal alignment, then comparing and combining corresponding pixels for applications such as background subtraction, compositing, and increasing dynamic range. We align a pair of videos by searching for frames that best match according to a robust image registration process. This process uses locally weighted regression to interpolate and extrapolate high-likelihood image correspondences, allowing new correspondences to be discovered and refined. Image regions that cannot be matched are detected and ignored, providing robustness to changes in scene content and lighting, which allows a variety of new applications.
Ridge-valley lines on meshes via implicit surface fitting
Authors: Ohtake Yutaka , Belyaev Alexander , Seidel Hans-Peter
Published: October 2004

We propose a simple and effective method for detecting view-and scale-independent ridge-valley lines defined via first- and second-order curvature derivatives on shapes approximated by dense triangle meshes. A high-quality estimation of high-order surface derivatives is achieved by combining multi-level implicit surface fitting and finite difference approximations. We demonstrate that the ridges and valleys are geometrically and perceptually salient surface features, and, therefore, can be potentially used for shape recognition, coding, and quality evaluation purposes.
Shape matching and anisotropy
Authors: Kazhdan Michael , Funkhouser Thomas , Rusinkiewicz Szymon
Published: October 2004

With recent improvements in methods for the acquisition and rendering of 3D models, the need for retrieval of models has gained prominence in the graphics and vision communities. A variety of methods have been proposed that enable the efficient querying of model repositories for a desired 3D shape. Many of these methods use a 3D model as a query and attempt to retrieve models from the database that have a similar shape.In this paper we consider the implications of anisotropy on the shape matching paradigm. In particular, we propose a novel method for matching 3D models that factors the shape matching equation as the disjoint outer product of anisotropy and geometric comparisons. We provide a general method for computing the factored similarity metric and show how this approach can be applied to improve the matching performance of many existing shape matching methods.