Search

In Chapter 6 we demonstrated the extension of the discontinuous Galerkin (DG) methods to problems in two spatial dimensions. This involved the introduction of nodal sets for the triangle and an orthonormal polynomial basis that we used as a reference basis for interpolation, differentiation, and the computation of inner products. In this chapter we will go further and consider the additional details required to extend this approach to three-dimensional domains. [ABSTRACT FROM AUTHOR]

In the preceding chapters, we have developed schemes and discussed basic properties such as stability and convergence. We have not, however, discussed the spectral properties of the operators apart from the discussion of the numerical dispersion relations in Section 4.6. In that discussion it became clear that the eigenvalues of the operators play a key role when determining the properties of the discrete operators and, thus, the behavior of the scheme. [ABSTRACT FROM AUTHOR]

All previous chapters have focused almost exclusively on the simplest cases of geometric discretizations where all boundaries are assumed to be piecewise linear and all elements share faces of equal size and order of approximation. However, one of the major advantages of discontinuous Galerkin (DG) methods lies in their flexibility to go beyond these cases and support more complex situation. In this chapter we discuss the modifications required to extend the linear conforming elements to include the treatment of meshes containing curvilinear elements and/or non-conforming elements. As we will see, the required changes are limited, but the advantages of doing so can be dramatic in terms of improvements in accuracy and reductions in computational effort. [ABSTRACT FROM AUTHOR]

So far, we have only considered problems with first order spatial derivatives (e.g., as in conservation laws), and shown the methods to perform well and in agreement with the strong theoretical foundation. It is natural to ask whether one can extend the formulation to include more general problem types. This is the topic of this chapter and, as we will see shortly, the generalization to deal with higher-order spatial operators is less direct than one would expect. Let us consider the following simple example, taken from [288]. [ABSTRACT FROM AUTHOR]

So far, we have focused entirely on linear problems with constant or piecewise constant coefficients. As we have seen, the methods and analysis for these cases is relatively complete. In this chapter we expand the discussion to include more complex problems — in particular, problems with smoothly varying coefficients and genuinely nonlinear problems. As we will see, this introduces new elements that need attention, and the analysis of the methods for such problems is more complex. In fact, we will often not attempt to give a complete analysis but merely outline the key results. However, the extension to strongly nonlinear problems displays many unique features and the power and robustness of the discontinuous Galerkin methods. [ABSTRACT FROM AUTHOR]

We have so far focused almost entirely on the formulation, analysis, and implementation of the discontinuous Galerkin schemes (DG-FEM) for onedimensional problems. In this chapter we consider in more detail the extension to multidimensional problems and the challenges introduced by this. We will quickly realize that what may have seemed unnecessarily complicated in the one-dimensional case now enables us to expand the formulation to multiple dimensions with only minor changes. [ABSTRACT FROM AUTHOR]

While the last chapters have focused on basic ideas and their implementation as a computational method, further insight into the performance of the method can be gained by revisiting some issues in more detail. To keep things relatively simple, we focus on the properties of the scheme for one-dimensional linear problems. However, as we will see later, many of the results obtained here carry over to multidimensional problems and even nonlinear problems with just a few modifications. [ABSTRACT FROM AUTHOR]

While we initially strive to stay away from complex notation a few fundamentals are needed. We consider problems posed on the physical domain Ω with boundary ∂Ω and assume that this domain is well approximated by the computational domain Ωh. This is a space filling triangulation composed of a collection of K geometry-conforming nonoverlapping elements, Dk. The shape of these elements can be arbitrary although we will mostly consider cases where they are d-dimensional simplexes. [ABSTRACT FROM AUTHOR]

As simple as the formulations in the last chapter appear, there is often a leap between mathematical formulations and an actual implementation of the algorithms. This is particularly true when one considers important issues such as efficiency, flexibility, and robustness of the resulting methods. In this chapter we address these issues by first discussing details such as the form of the local basis and, subsequently, how one implements the nodal DG-FEMs in a flexible way. To keep things simple, we continue the emphasis on one-dimensional linear problems, although this results in a few apparently unnecessarily complex constructions. We ask the reader to bear with us, as this slightly more general approach will pay off when we begin to consider more complex nonlinear and/or higher-dimensional problems. [ABSTRACT FROM AUTHOR]

When faced with the task of solving a partial differential equation computationally, one quickly realizes that there is quite a number of different methods for doing so. Among these are the widely used finite difference, finite element, and finite volume methods, which are all techniques used to derive discrete representations of the spatial derivative operators. If one also needs to advance the equations in time, there is likewise a wide variety of methods for the integration of systems of ordinary differential equations available to choose among. With such a variety of successful and well tested methods, one is tempted to ask why there is a need to consider yet another method. [ABSTRACT FROM AUTHOR]

In this chapter, we review and discuss precursory and alternative theories. We start in the first section with Lindenbaum et al. Their papers contain a theory of shape detection whose setting is essentially the same as the one developed in this book. The Bienenstock et al. compositional model discussed in Sections 15.2 and 15.5 is an ambitious theory attempting to build directly a grammar of visual primitives. A nice illustration of these compositional approaches is the work of Zhu et al. described in Section 15.2. Section 15.3 discusses the link among meaningful events, hypothesis testing, and Signal Detection Theory. It also shows that the Number of False Alarms (NFA) can be put in a classical statistical framework where multiple testing is involved. In Section 15.4 the Arias-Castro et al. geometric detection theory is addressed. This theory is very close in spirit to the tools in this book and are actually partly inspired from it. It gives complementary information on asymptotic geometric detection thresholds and hints on how to speed up detection algorithm. Section 15.5 discusses the Bayesian theory according to which the probability of the image interpretation given the observation must be maximized. An extension of this theory, the Minimum Description Length, is also invoked in the compositional model. In both cases, a probability is maximized. In contrast, meaningful events were obtained by minimizing an a-contrario probability. This point is discussed and the complementarity of both approaches are indicated. [ABSTRACT FROM AUTHOR]

Among gestalt principles, the color constancy principle is probably the most basic principle and the easiest to simulate. It states that points with the same color (or gray level) that touch each other are automatically grouped. Since by the Shannon principle an image is a continuous function, we can definitely apply this principle to the level lines of the image, namely the curves along which the gray level u(x, y) is constant. [ABSTRACT FROM AUTHOR]

Sets of parallel lines in 3-D space are projected into a 2-D image to a set of concurrent lines. The meeting point of these lines in the image plane is called a vanishing point. It can belong to the line at infinity of the image when the 3-D lines are parallel to the image plane. Even though concurrence in the image plane does not necessarily imply parallelism in 3-D, the counterexamples for this implication are rare in real images. Thus, the problem of grouping sets of parallel lines in 3-D is reduced to finding significant sets of concurrent lines in the image plane. In this chapter we will explain how vanishing points can be reliably and automatically detected with a low number of false alarms (NFA) and a high precision level without using any a priori information on the image or calibration parameters and without any parameter tuning. On the contrary, a vanishing point detector can be used to determine some calibration parameters of the camera or for other applications such as single-view metrology. [ABSTRACT FROM AUTHOR]

Chapter 2 proposed a classification of gestalt grouping processes. The basic grouping laws that group points if they share some geometric quality were called partial gestalts. A synopsis of all partial gestalts computed in this book is presented in Section 14.1. At the end of the chapter, a review of other gestalts computed in recent works confirms that all partial gestalts can be computed by similar methods. Thus, the focus in the computational gestalt programme should now be to formalize the more general gestalt principles, starting with gestalt collaboration and competition. How far do we stand in that direction? One of the grouping laws, the vanishing point detector, uses previously calculated gestalts, namely alignments. Thus, at least in this case, the recursive gestalt building up has been addressed. In Section 14.2 a successful complete gestalt analysis will be performed on a digital image by combining most partial gestalts computed so far. On the dark side, Section 14.3 presents a series of striking experimental examples showing perceptually wrong detections in the absence of collateral inhibition between conflicting partial gestalts. These experiments show that the gestalt programme still lacks some fundamental principle on gestalt interaction. A good candidate would be an extension of the exclusion principle introduced in Chapter 6. Another possibility would be to go back to variational principles like the Minimum Description Length principle. We address this possibility in the next and last chapter. [ABSTRACT FROM AUTHOR]

Is our perception driven by the Helmholtz principle? In this chapter, we describe two psycho-visual setups. The experiments were designed to test the ability of a subject to detect the presence of certain gestalts in an image. The first psycho-visual experiment tests human ability to detect dark or bright squares in a white noise image (Section 13.2). The second experiment tests alignment perception (Section 13.3). For each experiment, the responses of the tested subjects were measured as a function of two parameters, namely the size of the gestalt to be detected and theamount of noise. As we will see, the match between perception thresholds andtheoretical ones predicted by the Helmholtz principle is good. This is checked by comparing the theoretical iso-meaningfulness curves in parameter space with the observed ones. [ABSTRACT FROM AUTHOR]

In this chapter, we present an application of meaningful events to binocular vision. Binocular vision, also called Stereovision, is a major part of Computer Vision, as it theoretically allows us to reconstruct a 3-D representation of the world from two images taken from slightly different points of view. We focus here on the following problem: Given a set of n point matches between two images (i.e., a set of n points for each image with a one-to-one correspondence), can we decide when these points are the perspective projections on the two images of n physical points? Can we find the maximal group that satisfies this property? As we will see, the position of the point matches are constrained by the perspective projection as soon as n ≥ 8 (for uncalibrated cameras). However, to prove in practice the existence of a rigid motion between two images, more than 8 point matches are desirable to compensate for the limited accuracy of the matches. In this chapter we describe a computational definition of rigidity and show how the Heimholte principle can be applied to define a probabilistic criterion that rates the meaningfulness of a rigid set as a function of both the number of pairs of points (n) and the accuracy of the matches. This criterion yields an objective way to compare, say, precise matches of a few points and approximate matches of many points. It also yields absolute accuracy requirements for rigidity detection in the case of nonmatched points (i.e., when no one-to-one correspondence is available) and optimal values of n, depending on the expected accuracy of the matches and on the proportion of outliers. It can be used to build an optimized random sampling algorithm that is able to detect a rigid motion and estimate the fundamental matrix when the set of point matches contains up to 90% of outliers. [ABSTRACT FROM AUTHOR]

The global analysis of digital images can involve the histograms of variables like the gray level or the orientation. Usually histograms are not flat. Peaks and lacunary parts are observed. The peaks can correspond to meaningful groups and the lacunary intervals correspond to separations between them. We will call the peaks modes of the histogram. Lacunary intervals are called gaps. Since their analysis will in essence be symmetric, we will focus on the modes. How can we decide whether a mode or a gap is meaningful or not? This problem is very similar to the alignment detection problem. As in the meaningful alignment theory, the Heimholte principle can be adopted. There is indeed no a priori knowledge about the histogram model. Thus meaningfulness can be computed as though all samples were uniformly and independently distributed. Meaningful modes will be defined as counterexamples to this uniformity assumption and maximal meaningful modes will be the best counterexamples to uniformity. The exclusion principle will be involved again. It will be proven that maximal meaningful modes of the histogram are disjoint. This will give an algorithm that can be immediately applied to image analysis. Can such a detection theory give an account of the so-called "visual pyramid"? According to the visual pyramid doctrine geometric events (gestalts) are grouped recursively at different scales (see Chapter 1). This pyramidal assumption can be confirmed only if the detection of geometric events is robust enough. A first test of visual pyramid (i.e., a combination bottom up of gestalt grouping), is given in the last section. All maximal meaningful alignments of an image will be computed and the obtained segments grouped according to the mode of the orientation histogram to which they belong. This yields an implementation of the parallelism gestalt. [ABSTRACT FROM AUTHOR]

This chapter contains a brief review of the theory of edge detection and its nonlocal version — the "snake" or "active contour" theory. The snakes are curves drawn in the image and minimizing a contrast and smoothness energy. [ABSTRACT FROM AUTHOR]

We saw in the previous chapter that the Helmholtz principle in his generic form leads us to the computation of the probability of events of the type "at least k objects out of l have a considered quality". When the a-contrario assumption is that objects are independent and have the same probability p to have the quality, the probability of this event is given by the binomial distribution. In this chapter, we will give different inequalities and asymptotic results for the binomial tail. Such results are useful mainly because they help us to understand the "meaningfulness" of an event as a function of l, k, and p. The results given in this chapter will be used through the rest of the book. [ABSTRACT FROM AUTHOR]

In this chapter, we start in Section 2.1 with some examples of optic-geometric illusions and then give, in Section 2.2, an account of Gestalt Theory, centered on the initial 1923 Wertheimer program. In Section 2.3 the focus is on the problems raised by the synthesis of groups obtained by partial grouping laws. Following Kanizsa, we will address the conflicts between these laws and the masking phenomenon. In Section 2.4 several quantitative aspects implicit in Kanizsa's definition of masking are indicated. It is shown that one particular kind of masking, Kanizsa's masking by texture, may lead to a computational procedure. [ABSTRACT FROM AUTHOR]

The Helmholtz principle can be formulated two ways. The first way is commonsensical. It simply states that we do not perceive any structure in a uniform random image. In this form, the principle was first stated by Attneave [Att54]. This gestaltist was to the best of our knowledge the first scientist to publish a random noise digital image. This image was actually drawn by hand by U.S. Army privates using a random number table. In its stronger form, of which we will make great use, the Helmholtz principle states that whenever some large deviation from randomness occurs, a structure is perceived. As a commonsense statement, it states that "we immediately perceive whatever could not happen by chance". Our aim in this chapter is to discuss several intuitive and sometimes classical examples of exceptional events and their perception. We will see how hard it can be to calculate some rather simple events. This difficulty is solved by introducing a universal variable adaptable to many detection problems, the Number of False Alarms (NFA). The NFA of an event is the expectation of the number of occurrences of this event. Expectations are much easier to compute than probabilities because they add. After we have treated three toy examples in Section 3.1, we will define in Section 3.2 what we call ε-meaningful events, namely events whose NFA is less than ε. This notion is then applied to a first realistic problem: the dot alignment detection in an image. [ABSTRACT FROM AUTHOR]

Digital images usually have many alignments due to perspective, human made objects, and so forth. Can they and only they be detected? There should be detection thresholds telling us whether a particular configuration of points is aligned enough to pop out as an alignment. Alignments are not trivial events. They depend a priori on four different parameters, namely the total length l of the alignment, the number k of observed aligned points in it, the precision p of the alignment, and the size of the image N. So a decision threshold function kmin(l, p, N) is needed and will be established by the Helmholtz principle. In its weak formulation, this principle commonsensically formulates that kmin should be fixed in such a way as to seldom detect any alignment in a white noise image. In the stronger formulation, the Helmholtz principle tells us that whenever a configuration occurs, which could not arise by chance in white noise, this configuration is perceived and must be detected by a Computer Vision algorithm. In Section 5.1, we define and analyze the white noise image a contrario and show how to compute detection thresholds kmin(l, p, N) discarding alignments in white noise. Section 5.2 is devoted to the analysis of the Number of False Alarms (NFA) of an alignment and the rest of the chapter considers several estimates of the detection threshold kmin. Finally, several consistency problems associated with the definition of meaningfulness are considered. In Section 5.5, the important problem of choosing the precision p is finally addressed. [ABSTRACT FROM AUTHOR]

Why do we interpret stimuli arriving at our retina as straight lines, squares, circles, and any kind of other familiar shape? This question may look incongruous: What is more natural than recognizing a "straight line" in a straight line image, a "blue cube" in a blue cube image? When we believe we see a straight line, the actual stimulus on our retina does not have much to do with the mathematical representation of a continuous, infinitely thin, and straight stroke. All images, as rough data, are a pointillist datum made of more or less dark or colored dots corresponding to local retina cell stimuli. This total lack of structure is equally true for digital images made of pixels, namely square colored dots of a fixed size. [ABSTRACT FROM AUTHOR]

Interpolation spaces are useful technical tools. They allow one to bridge between known results, yielding new results that could not be obtained directly. They also provide a concept of fractional-order derivatives, extending the definition of the Sobolev spaces used so far. Such extensions allow one to measure more precisely, for example, the regularity of solutions to elliptic boundary value problems. [ABSTRACT FROM AUTHOR]

Equations of the form (12.3.1) or (12.5.14) are indefinite and require special care to solve. We will now consider one class of algorithms which involve a penalty method to enforce the second equation in (12.3.1) or (12.5.14). These algorithms transform the linear algebra to positive-definite problems in many cases. Moreover, the number of unknowns in the algebraic system can also be significantly reduced. [ABSTRACT FROM AUTHOR]

The name "mixed method" is applied to a variety of finite element methods which have more than one approximation space. Typically one or more of the spaces play the role of Lagrange multipliers which enforce constraints. The name and many of the original concepts for such methods originated in solid mechanics where it was desirable to have a more accurate approximation of certain derivatives of the displacement. However, for the Stokes equations which govern viscous fluid flow, the natural Galerkin approximation is a mixed method. [ABSTRACT FROM AUTHOR]

In most physical applications, quantities of interest are governed by a system of partial differential equations, not just a single equation. So far, we have only considered single equations (for a scalar quantity), although much of the theory relates directly to systems. We consider one such system coming from solid mechanics in this chapter. [ABSTRACT FROM AUTHOR]

The finite element approximation is essentially defined by a mean-square projection of the gradient. Thus, it is natural that error estimates for the gradient of the error directly follow in the L2 norm. It is interesting to ask whether such a gradient-projection would also be of optimal order in some other norm, for example L∞. We prove here that this is the case. Although of interest in their own right, such estimates are also crucial in establishing the viability of approximations of nonlinear problems (Douglas & Dupont 1975) as we indicate in Sect. 8.7. Throughout this chapter, we assume that the domain Ω ⊂ IRd is bounded and polyhedral. [ABSTRACT FROM AUTHOR]

In Section 0.8, we demonstrated the possibility of dramatic improvements in approximation power resulting from adaptive meshes. In current computer simulations, meshes are often adapted to the solution either using a priori information regarding the problem being solved or a posteriori after an initial attempt at solution (Babuška et al. 1983 & 1986). The resulting meshes tend to be strongly graded in many important cases, no longer being simply modeled as quasi-uniform. Here we present some basic estimates that show that such meshes can be effective in approximating difficult problems. For further references, see (Eriksson, Estep, Hansbo and Johnson 1995), (Verfürth 1996), (Ainsworth and Oden 2000), (Becker and Rannacher 2001), (Babuška and Strouboulis 2001), (Dörfler and Nochetto 2002), (Bangerth and Rannacher 2003), (Neittaanmäki and Repin 2004), (Han 2005), (Carstensen 2005) and (Carstensen, Hu and Orlando 2007). [ABSTRACT FROM AUTHOR]

The symmetric positive definite system arising from a finite element discretization of an elliptic boundary value problem can be solved efficiently using the preconditioned conjugate gradient method (cf. (Saad 1996)). In this chapter we discuss the class of additive Schwarz preconditioners, which has built-in parallelism and is particularly suitable for implementation on parallel computers. Many well-known preconditioners are included in this class, for example the hierarchical basis and BPX multilevel preconditioners, the two-level additive Schwarz overlapping domain decomposition preconditioner, the BPS, Neumann-Neumann, and BDDC nonoverlapping domain decomposition preconditioners. [ABSTRACT FROM AUTHOR]

We now give several examples of higher-dimensional variational problems that use the theory developed in previous chapters. The basic notation is provided by the Sobolev spaces developed in Chapter 1. We combine the existence theory of Chapter 2 together with the approximation theory of Chapters 3 and 4 to provide a complete theory for the discretization process. Several examples will be fully developed in the text, and several others are found in the exercises. Throughout this chapter, we assume that the domain Ω is bounded. [ABSTRACT FROM AUTHOR]

The multigrid method provides an optimal order algorithm for solving elliptic boundary value problems. The error bounds of the approximate solution obtained from the full multigrid algorithm are comparable to the theoretical bounds of the error in the finite element method, while the amount of computational work involved is proportional only to the number of unknowns in the discretized equations. [ABSTRACT FROM AUTHOR]

We will now develop the approximation theory appropriate for the finite elements developed in Chapter 3. We take a constructive approach, defining an averaged version of the Taylor polynomial familiar from calculus. The key estimates are provided by some simple lemmas from the theory of Riesz potentials, which we derive. As a corollary, we provide a proof of Sobolev's inequality, much in the spirit given originally by Sobolev. [ABSTRACT FROM AUTHOR]

This chapter is devoted to the functional analysis tools required for developing the variational formulation of differential equations. It begins with an introduction to Hilbert spaces, including only material that is essential to later developments. The goal of the chapter is to provide a framework in which existence and uniqueness of solutions to variational problems may be established. [ABSTRACT FROM AUTHOR]

This chapter is devoted to developing function spaces that are used in the variational formulation of differential equations. We begin with a review of Lebesgue integration theory, upon which our notion of "variational" or "weak" derivative rests. Functions with such "generalized" derivatives make up the spaces commonly referred to as Sobolev spaces. We develop only a small fraction of the known theory for these spaces—just enough to establish a foundation for the finite element method. [ABSTRACT FROM AUTHOR]

The finite element method provides a formalism for generating discrete (finite) algorithms for approximating the solutions of differential equations. It should be thought of as a black box into which one puts the differential equation (boundary value problem) and out of which pops an algorithm for approximating the corresponding solutions. Such a task could conceivably be done automatically by a computer, but it necessitates an amount of mathematical skill that today still requires human involvement. The purpose of this book is to help people become adept at working the magic of this black box. The book does not focus on how to turn the resulting algorithms into computer codes, but this topic is being pursued by several groups. In particular, the FEniCS project (on the web at fenics.org) utilizes the mathematical structure of the finite element method to automate the generation of finite element codes. [ABSTRACT FROM AUTHOR]

We have gathered in this chapter the notation and the most important results on different function spaces that we have used or will use throughout the book. We precisely fix the notations and state the theorems. But we provide almost no proof, since the results are standard. [ABSTRACT FROM AUTHOR]

In this chapter, we consider Dirichlet problems associated with some underdetermined equations, that are important in geometry as well as in applications, notably in fluid mechanics and elasticity. [ABSTRACT FROM AUTHOR]

In this chapter, we refer to the following books: Bellman [74], Ciarlet [153], Dacorogna-Marcellini [202], Horn-Johnson [345] and [346], Marshall-Olkin [432] and Serre [531]. [ABSTRACT FROM AUTHOR]

The chapter is organized as follows. In Section 10.2, we present an abstract existence theorem based on Baire category theorem. In Section 10.3, we give several examples, notably one involving singular values and one concerning potential wells, where the abstract theorem applies. [ABSTRACT FROM AUTHOR]

We now discuss the notions of polyconvex, quasiconvex and rank one convex sets. Contrary to the usual presentation of classical convex analysis, where the notion of a convex set is defined prior to that of a convex function; this is not the case for the generalized notions of convexity. This is of course due to historical reasons. The notions of polyconvex, quasiconvex and rank one convex functions were introduced, as already said, by Morrey in 1952, although the terminology is that of Ball [53]. It was not until the systematic studies of partial differential equations and inclusions by Dacorogna-Marcellini and Müller-Sverak, initiated in 1996 and discussed in Chapter 10, that the equivalent definitions for sets became an important issue. Moreover these notions were essentially seen through the different generalized convex hulls, leading somehow to terminologies that do not exactly cover the same concepts. We here try to imitate as much as possible the classical approach of convex analysis in the present context. Throughout the two first sections, we follow the presentation of Dacorogna-Ribeiro [213], following earlier results of Dacorogna- Marcellini [202]. [ABSTRACT FROM AUTHOR]

In Section 6.2, we start with the polyconvex envelope Pf, which is the most similar to the convex envelope Cf. We always recall, without proofs, what has already been said about Cf in Chapter 2 to show the resemblance between the two envelopes. In Section 6.3, we give a representation formula for the quasiconvex envelope, inspired by Carathéodory theorem. In Section 6.4, we discuss a representation formula for Rf, also in the spirit of Carathéodory theorem. In Section 6.5, we present a result that in some cases can simplify the computations of the different envelopes. In Section 6.6, we discuss several examples, relevant for applications, where one can compute these envelopes. [ABSTRACT FROM AUTHOR]