Skip to main content
main-content

Über dieses Buch

This book contains the proceedings of the workshop Uncertainty in Geomet­ ric Computations that was held in Sheffield, England, July 5-6, 2001. A total of 59 delegates from 5 countries in Europe, North America and Asia attended the workshop. The workshop provided a forum for the discussion of com­ putational methods for quantifying, representing and assessing the effects of uncertainty in geometric computations. It was organised around lectures by invited speakers, and presentations in poster form from participants. Computer simulations and modelling are used frequently in science and engi­ neering, in applications ranging from the understanding of natural and artificial phenomena, to the design, test and manufacturing stages of production. This widespread use necessarily implies that detailed knowledge of the limitations of computer simulations is required. In particular, the usefulness of a computer simulation is directly dependent on the user's knowledge of the uncertainty in the simulation. Although an understanding of the phenomena being modelled is an important requirement of a good computer simulation, the model will be plagued by deficiencies if the errors and uncertainties in it are not consid­ ered when the results are analysed. The applications of computer modelling are large and diverse, but the workshop focussed on the management of un­ certainty in three areas : Geometric modelling, computer vision, and computer graphics.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Affine Intervals in a CSG Geometric Modeller

Abstract
Our CSG modeller, svLis, uses interval arithmetic to categorize implicit functions representing primitive shapes against boxes; this allows an efficient implementation of recursive spatial division to localize the primitives for a variety of purposes, such as rendering or the computation of integral properties.
Affine arithmetic allows a track to be kept on the contributing terms to an interval, which often reduces the conservativeness of interval arithmetic. In particular, by tracking the asymmetric contributions of even and odd powers of intervals that contain zero, tighter bounds can be kept on resulting interval values.
This paper shows how such techniques can be implemented in the svLis modeller, and offers a comparison of doing so with using conventional interval arithmetic.
Adrian Bowyer, Ralph Martin, Huahao Shou, Irina Voiculescu

Chapter 2. Fast and Reliable Plotting of Implicit Curves

Abstract
This paper presents a new, fast and reliable subdivision algorithm for adaptive enumeration and plotting of implicit curves. For this purpose, Implicit Linear Interval Estimations (ILIEs) based on affine arithmetics are introduced. They allow a significant acceleration of the subdivision process and a generation of reliable piecewise linear enclosures for the curve. The algorithm has been tested for algebraic curves of high degree and non-trivial trigonometric curves with remarkable results.
Katja Buehler

Chapter 3. Data Assimilation with Sequential Gaussian Processes

Abstract
We study a data assimilation problem using Gaussian processes (GPs) where the GPs act as latent variables for the observations. Inference is done using a convenient parameterisation and sequential learning for a faster algorithm. We are addressing the disadvantage of the GPs, namely the quadratic scaling of the parameters with data and eliminate the scaling by using a fixed number of parameters. The result is a sparse representation that allows us to treat problems with a large number of observations. We apply our method to the prediction of wind fields over the ocean surface from scatterometer data.
Lehel Csato, Dan Cornford, Manfred Opper

Chapter 4. Conformal Geometry, Euclidean Space and Geometric Algebra

Abstract
Projective geometry provides the preferred framework for most implementations of Euclidean space in graphics applications. Translations and rotations are linear transformations in projective geometry, which helps when it comes to programming complicated geometrical operations. But there is a fundamental weakness in this approach — the Euclidean distance between points is not handled in a straightforward manner. Here we discuss a solution to this problem, based on conformai geometry. The language of geometric algebra is best suited to exploiting this geometry, as it handles the interior and exterior products in a single, unified framework. A number of applications are discussed, including a compact formula for reflecting a line off a general spherical surface.
Chris Doran, Anthony Lasenby, Joan Lasenby

Chapter 5. Towards the Robust Intersection of Implicit Quadrics

Abstract
We are interested in efficiently and robustly computing a parametric form of the intersection of two implicit quadrics with rational coefficients. Our method is similar in spirit to the general method introduced by J. Levin for computing an explicit representation of the intersection of two quadrics, but extends it in several directions. Combining results from the theory of quadratic forms, a projective formalism and new theorems characterizing the intersection of two quadratic surfaces, we show how to obtain parametric representations that are both “simple” (the size of the coefficients is small) and “as rational as possible”.
Laurent Dupont, Sylvain Lazard, Sylvain Petitjean, Daniel Lazard

Chapter 6. Computational Geometry and Uncertainty

Abstract
From the prehistory of computational geometry it has been apparent that geometric computation is fraught with problems. Although these problems have become less troublesome over the ensuing thirty years, they have not been eliminated. The paper discusses the sources of geometric errors in applied computational geometry systems and reviews various attempts at eliminating them in practical systems. No completely satisfactory solution has been devised, but for some restricted cases, there has been progress. A possible way ahead which may enable provably correct systems to be implemented is suggested.
A. R. Forrest

Chapter 7. Geometric Uncertainty in Solid Modeling

Abstract
In solid modeling geometric uncertainty arises in several settings. For systems which use analytic solutions when possible, it is necessary to determine the type of surface so that the correct analytic solver will be used. In passing from 3-D space data to 2-D parametric data, the algorithms used are vulnerable to geometric uncertainty — examples and solutions from a project in a commercial solid modeler [ACIS, 2001] are presented. For any solid modeler, there is a fundamental uncertainty imposed by the use of exact logic for topology together with necessarily inexact logic for geometry.
Pierre J. Malraison, William A. Denker

Chapter 8. Reliable Geometric Computations with Algebraic Primitives and Predicates

Abstract
The problem of accurate and robust implementation of geometric algorithms has received considerable attention for more than a decade. Despite much progress in computational geometry and geometric modeling, practical implementations of geometric algorithms are prone to error. Much of the difficulty arises from the fact that reasoning about geometry most naturally occurs in the domain of the real numbers, which can only be represented approximately on a digital computer. Many times, the correctness of geometric algorithms depends on correctly evaluating the signs of arithmetic expressions, and errors due to rounding or imprecise inputs can lead to grossly incorrect results or failure to run to completion.
Mark Foskey, Dinesh Manocha, Tim Culver, John Keyser, Shankar Krishnan

Chapter 9. Feature Localization Error in 3D Computer Vision

Abstract
Uncertainty modeling in 3D Computer Vision typically relies on propagating the uncertainty of measured feature positions through the modeling equations to obtain the uncertainty of the 3D shape being estimated. It is widely believed that this adequately captures the uncertainties of estimated geometric properties when there are no large errors due to mismatching. However, we identify another source of error which we call feature localization error. This captures how well a feature corresponds to the true 3D point, rather than how well features correspond over multiple images. We model this error as independent of the tracking error, and when combined as part of the total error, we show that it is significant and may even dominate the 3D reconstruction error.
Daniel D. Morris, Takeo Kanade

Chapter 10. Bayesian Analysis of Computer Model Outputs

Abstract
We consider various statistical problems associated with the use of complex deterministic computer models. In particular, we focus on exploring the uncertainty in the output of the model that is induced by uncertainty in some or all of the model input parameters. In addition, we consider the case when the computer model is computationally expensive, so that it is necessary to be able to describe the output uncertainty based on a small number of runs of the model itself.
Jeremy Oakley, Anthony O’Hagan

Chapter 11. B

Abstract
In this chapter we summarize density properties of Reproducing Kernel Hilbert Spaces induced by different classes of kernels. They are important to characterize the power of the associated hypothesis spaces. In the process we characterize the role of b, which is the constant in the standard form of the solution provided by the Support Vector Machine technique \(f(x) = \sum\nolimits_{i = 1}^\ell {\alpha _i } K\left( {x,\:x_i } \right) + b,\) which is a special case of Regularization Machines.
T. Poggio, S. Mukherjee, R. Rifkin, A. Raklin, A. Verri

Chapter 12. Affine Arithmetic and Bernstein Hull Methods for Algebraic Curve Drawing

Abstract
We compare approaches to the location of the algebraic curve f(x,y) = 0 in a rectangular region of the plane, based on recursive use of conservative estimates of the range of the function over a rectangle. Previous work showed that performing interval arithmetic in the Bernstein basis is more accurate than using the power basis, and that affine arithmetic in the power basis is better than using interval arithmetic in the Bernstein basis. This paper shows that using affine arithmetic with the Bernstein basis gives no advantage over affine arithmetic with the power basis. It also considers the Bernstein coefficient method based on the convex hull property, which has similar performance to affine arithmetic.
Huahao Shou, Ralph Martin, Guojin Wang, Irina Voiculescu, Adrian Bowyer

Chapter 13. Local Polynomial Metrics for K Nearest Neighbor Classifiers

Abstract
In many pattern recognition systems, metrics are frequently employed to quantify the dissimilarity that exists between two given patterns. Common applications occur in clustering algorithms, radial basis function classifiers, and nearest neighbor classifiers (Duda et al., 2001). A bounty of results exist that demonstrate the importance of selecting a metric (or dissimilarity measure) with care (e.g., Simard et al., 1993). In the following, we present an adaptive algorithm that uses local polynomial regression to construct a metric useful for a pattern classification problem described by a set of correctly classified patterns. Although we introduce this algorithm in the context of the k nearest neighbor classifier, it is applicable to other pattern classifiers that use proximity in feature space as a measure of pattern similarity.
Robert R. Snapp

Chapter 14. Visualisation of Incomplete Data Using Class Information Constraints

Abstract
We analyse how the training algorithm for the Generative Topographic Mapping (GTM) can be modified to use class information to improve results on incomplete data. The approach is based on an Expectation-Maximisation (EM) method which estimates the parameters of the mixture components and missing values at the same time; furthermore, if we know the class membership of each pattern, we can improve the generic algorithm by eliminating multi-modalities in the posterior distribution over the latent space centres. We evaluate the method on a toy problem and a realistic data set. The results show that our algorithm can help to construct informative visualisation plots, even when many of the training points are incomplete.
Yi Sun, Peter Tino, Ian Nabney

Chapter 15. Towards Videorealistic Synthetic Visual Speech

Abstract
In this paper we present preliminary results of work towards a videorealistic visual speech synthesiser. A generative model is used to track the face of a talker uttering a series of training sentences and an inventory of synthesis units is built by representing the trajectory of the model parameters with spline curves. A set of model parameters corresponding to a new utterance is formed by concatenating spline segments corresponding to synthesis units in the inventory and sampling at the original frame rate. The new parameters are applied to the model to create a sequence of images corresponding to the talking face.
Barry Theobald, J. Andrew Bangham, Silko Kruse, Gavin Cawley, Iain Matthews

Chapter 16. Properties of the Companion Matrix Resultant for Bernstein Polynomials

Abstract
The computational implementation in a floating point environment of the companion matrix resultant is considered and it is shown that the numerical condition of the resultant matrix is strongly dependent on the basis in which the polynomials are expressed. In particular, a companion matrix of a Bernstein polynomial is derived and this is used to construct a resultant matrix for two Bernstein polynomials. A measure of the numerical condition of a resultant matrix is developed and then used to compare the stability of the resultant matrices of the same polynomials that are expressed in different bases. It is shown that it is desirable to express the polynomials in the Bernstein basis, but since the power basis is the natural choice in many applications, a transformation of the resultant matrix between these bases is required. It is shown that this transformation of the resultant matrix between the bases cannot be achieved by performing a basis transformation of each polynomial. Rather, the equation that defines the transformation of the companion matrix resultant between the bases is derived by considering the eigenvectors of the companion matrix of a polynomial in each basis. The numerical condition of this equation is considered and it is shown that it is ill-conditioned, even for polynomials of low degree.
Joab R. Winkler

Chapter 17. Computation with a Number of Neurons

Abstract
An essential feature of neural information processing in the brain is that a stimulus is not represented by the activity of a single neuron but rather by the joint activities of a number of them. Such a coding strategy is called population coding. This paper reviews the recent progress on the understanding of computational properties of population codes, with emphasis on how to implement a hierarchical Bayesian decoding procedure in a neural circuit.
Si Wu, Danmei Chen

Backmatter

Weitere Informationen