Detecting Strength and Location of Jump Discontinuities in Numerical Data ()
1. Introduction
In a series of papers, Gelb and Tadmor published a means of edge detection from spectral data of a given function, [1-3], see also the review essay [4]. The theory given is based on the work of Fejér and Lukács on the conjugate trigonometric series, see [5-7]. A trigonometric series given in the form
is known to be the real part of the complex power series
on the unit circle. Taking the imaginary part of this power series results in the conjugate trigonometric series
(1.1)
Note that often is called the conjugate series.
The coefficients and are computed from
(1.2)
For purposes of numerical analysis we are not concerned with trigonometric series but with the partial sums of them,
(1.3)
as with the partial sums of the conjugate series,
(1.4)
For sake of reference we note that the partial sums mentioned can be rewritten as convolutions
of with the Dirichlet kernels
The main result exploited by Gelb and Tadmor from the works of Fejér and Lukács cited above is summarized in Theorem II.8.13 of [8]. We consider a periodic function which is smooth except at one point where it is assumed that there is a jump discontinuity. Then the Theorem says that if exists and if the height of the jump is
then
This property of the conjugate trigonomteric series is called the concentration property. Hence, the conjugate series is an indicator for a jump discontinuity which can be recovered by. The GelbTadmor theory exploits this property. As was shown in [1], if is a -periodic piecewise smooth function with a single simple jump of height
at, then
(1.5)
where denotes the Dirac distribution located at. As convergence is really slow Gelb and Tadmor developed so-called concentration factors so that finally they arrive at a concentrated conjugate partial sum
(1.6)
which directly leads to generalised conjugate kernels
(1.7)
with similar properties as the conjugated Dirichlet kernel. Given an admissible kernel (see Def. 1) they proved following theorem.
Theorem 1 (The Concentration Property) Let f(x) be a piecewise smooth function and denotes the set of its jump discontinuities. Consider the generalised conjugate partial sum
where is an admissible kernel. Then
With the help of this theorem Gelb and Tadmor were able to investigate the concentration factors in detail, in other words, they studied the conditions on the contration factor for being an admissible kernel. They analysed the case of being a continuous function and extended their results to the discrete case by constructing discrete concentration factors from the continuous ones. In this paper, the discrete factor is reformulated (Section 1.3.1) and a direct proof for the discrete concentration property is given using weaker preconditions (Section 1.3.2). Beforehand, some of the main classical results are reviewed (Section 1.2). Furthermore, an opportunity of generalising to the full 2-d case which was investigated by Móricz [9] is presented in Section 1.4.
Our main motivation for studying these edge detectors is not in image processing but in steering the spectral viscosity filter in spectral difference and spectral Discontinuous Galerkin methods for the numerical solution of hyperbolic conservation laws, cp. [10], and this was indeed also the background motivating Gelb and Tadmor to start their studies. In order to solve hyperbolic conservation laws with high-order spectral methods efficiently a knowledge of the loci of the discontinuities in the solution is essential.
2. A Review of Classical Results
Although Gelb and Tadmor took up only Theorem II.8.13 of [8] it turns out that much more techniques to detect jump discontinuities and their heights are to be found in the classical literature. In the following we briefly discuss the main results of three papers [5-7].
Let us start with the oldest of our choice of papers, [5], written by Fejér in 1913. Fejér started from a classical theorem by Dirichlet: If a function1 obeys the Dirichlet conditions, i.e. if is continuous and monotone on finitely many subintervals of and finitely many discontinuities are of the first kind (meaning the existence of rightand left-sided limits), see [11, p.226], then the Fourier series of converges pointwise to if is a point of continuity, and to
at a point of discontinuity. Fejér asks if there is a comparably simple limit process with which it would be possible to compute the rightand left-sided limits and itself and hence the height of the jump which is simply. In [5] he gives several positive answers to this question. The first of his results can be stated as follows, see [5, p.177].
Theorem 2 (Fejér 1913) Let be a function obeying the Dirichlet conditions and a point of a jump discontinuity of. If g denotes the smallest (in fact: any) positive root of the transcendent equation
(1.8)
then the sequence
converges to, while the sequence
converges to. Hence the sequence
converges to.
In fact, this theorem can be generalised to the following form, [5, p.178].
Theorem 3 (Fejér 1913) Let and be any positive numbers and. Under the assumptions of Theorem 2 it follows that the sequence
converges to.
It was well known in Fejér’s days (and, in fact, proven by Fejér himself earlier) that the sequence of arithmetic means defined by
converges to under mild conditions on. Fejér argues that it might be possible to also extract the jump height at a discontinuity of the first kind from the sequence of arithmetic means. In fact, he was able to prove the following result, [5, p.179].
Theorem 4 (Fejér 1913) Let and be any positive numbers and. Then the sequence
converges to.
Fejér then turns to exploit the conjugate Fourier series for the computation of the jump height. Note that Fejér considers as conjugate series in contrast to (1.1) so that a minus sign has to be included if we compare to Gelb and Tadmor’s results. He notices that even for a function obeying the Dirichlet conditions the conjugate Fourier series need not be convergent (Fejér calls it “eigentlich divergent” meaning “intrinsically divergent”).
This can be seen from to which the conjugate series is. On the point is a point of a jump discontinuity of the first kind. However, the conjugate series evaluated at obviously gives the harmonic series.
However, Fejér was able to come up with universal convergence factors (therebye anticipating Gelb’s and Tadmor’s concentration factors) and to prove the following theorem, [5, p.183].
Theorem 5 (Fejér 1913) Under the Dirichlet conditions on it holds
where again is the smallest positive solution of (1.8). In points of smoothness of this limit gives zero.
Hence, if one already got hold of
as well as then
Fejér also investigated another method to compute the jump height [5, p.186f].
Theorem 6 (Fejér 1913) If f obeys the Dirichlet conditions and if is a function of bounded variation on, then
At points of continuity of this limit again gives zero.
While he showed in [5] that a Fourier series of a function obeying the Dirichlet condition converges pointwise, the conjugate series fails to converge in general. In [6, p.56] he extended this result and gave necessary conditions for the convergence of the conjugate series.
Theorem 7 (Fejér 1914) If a trigonometric series converges uniformly in, then the conjugate series converges almost everywhere, i.e. with the exception of a set of measure zero.
Fejér’s ideas were taken up by Ferenc (Franz) Lukács, who died prematurely in 1918, in his paper [7] submitted in 1916 but published in 1920 (apparently delayed due to the first world war). Lukács was able to release Fejér’s assumption that itself is a function of bounded variation2 and to prove the following theorem [7, p.108].
Theorem 8 (Lukács 1920) If f is Lebesgue-integrable on and -periodic and if the limit
exists, then3
Note that this theorem gives nothing but (1.5).
3. The Concentration Property in the Discrete Case
In contrast to [1] we do not employ discrete Fourier series beforehand but discretise the Fourier coefficients by means of a quadrature rule and truncate the Fourier series. In order to compute the coefficients (1.2) the intervall is divided into subintervals of length
each. The grid points are given by
and applying the composite trapezoidal rule results in the formulae (for)
and
It is as obvious as important an observation that in the discrete case the data consists of jumps from grid point to grid point. The jumps of order are acceptable, but the jumps indicate a jump discontinuity in the underlying function. Hence, we indicate a jump discontinuity at a point by means of the grid cell in which the jump occurs. The jump is then characterized by
Unfortunetely, the convergence rate is very slow, which can be seen in Figure 1 based on example 3.1. To remedy this fact Gelb and Tadmor developed their theory of concentration factors by investigating the concentrated or generalised conjugated Fourier partial sum given in eq. (1.6), using, for example, the simplest continuous concentration factor
In the discrete case the continuous function is not sufficient to be a concentration factor since discrete data is pestered with jumps by the sheer nature of discrete data. Instead of using the continuous function alone one has to use a product of with the coefficient
, which leads to the simplest concentration factor
Note that in this paper we follow the notational conventions of Gelb and Tadmor [1]. The function is continuous and hence a continuous concentration factor. The notation is used for the discrete concentration factors. A discrete concentration factor is the product of a continuous one -- -- and the factor which we already described above. As will be shown in Theorem 9, if the continuous concentration factor satisfies the concentration property, so do all discrete concentration factors of the form
(1.9)
and vice versa.
Example 3.1 We consider a test function taken from [1], namely
on. Note that exhibits exactly one discontinuity of the first kind at. We first compute the Fourier series of and the conjugate series without using a concentration kernel. In order to avoid interference from quadrature errors we always choose. In Figure 1 the Fourier partial sum of and the corresponding conjugate sum for can be seen. It can be clearly observed that although the conjugate series in fact detects a jump ‘down’ of height approx. 2 the resolution is quite bad in that the values of the conjugate partial sum away from the discontinuity are not close to zero. Applying the simplest discrete concentration factor leads to the conjugated partial sum
with significantly better concentration rates as can be seen in Figure 2.
3.1. Discrete Admissible Concetration Factors
To prove the concentration property for factors in the discrete case in detail, we start with the definition of an admissible kernel taken directly from [1].
Definition 1 (Admissible Kernels) A conjugate kernel is called admissible if it satisfies the following four properties:
(P1)
(P2)
(P3)
(P4)
We call a bounded concentration factor admissible, if is an admissible kernel.
Inserting in the definition of an admissible kernel gives following equivalent conditions in terms of:
(P2’)
Figure 1. Fourier series (left) and conjugated series (right) for example 3.1.
Figure 2. Conjugate series for example 3.1 with simple concentration factor using N = 40 (left) resp. N = 80 (right).
(P3’)
(P4’)
We will now prove the following theorem in detail (see [1] where it first appeared).
Theorem 9 If the continuous concentration factor
satisfies the concentration property, then the generalised discrete conjugated Fourier partial sum with the factor
satisfies also the concentration property.
Proof 1 We have to investigate the generalised conjugate partial sum (1.6) and the discrete Fourier coefficients and. In using the -periodicity of and by summation by parts we get
Now the mid-term is moved into the first sum and telescoping of the last sum yields
Next we expand by and recognize the fact by periodicity of the function and
and we get
Finally
Note that denotes the midpoint of the cell which encloses the discontinuity at. In complete analogy we find
Turning to the discrete conjugate Fourier partial sum (1.6) and inserting the expressions for and as derived above, this yields for
By employing the formulae
and
it follows
Inserting with, we get
Since is admissible, we can now use the concentration property in the continuous case shown in [1] which states
thus.
3.2. Proof of the Discrete Concentration Property
Gelb and Tadmor proved in [1] that the concentration property holds in the discrete case if the discrete concentration factors are related to continuous ones as in eq. (1.9). Furthermore, they deduced certain conditions for a discrete concentration function to be admissible from the continuous case, see theorem 4.2 in [1]. We will show that this result can be generalised to functions by proving the discrete case directly and using different estimates as in the following theorem.
Theorem 10 Consider a discrete concentration function such that.
Then the factors are admissible and the concentration property is satisfied,
if the following conditions are met:
The main part of the proof is to show that the associated conjugated kernel is admissible. We will prove two useful lemmata beforehand.
Lemma 1 Assume that the concentration function satisfies
Then property (P2’) and hence (P2) hold.
Proof 2 Let. By continuity,
By summing such terms we get
Employing the series expansion of we arrive at
and by the series expansion of the logarithm it follows
An index transformation and expansion yields
Hence, the result is proven.
Lemma 2 Consider the conjugate kernel
with concentration function Then the following estimate holds:
Proof 3 Let. First, summation by parts yields
For the following calculation, we use
to get
Using and the telescoping sum of it follows
Once again summation by parts yields
We arrive at the following result
and hence
Now we use the identity
to estimate as follows:
With, and with the mean value theorem,
The required result is hence proven.
We can now show that our main Theorem 10 holds.
Proof 4 (Proof: of Theorem 10) It is sufficient to prove that is an admissible kernel. Then, by Theorem 1, it follows that satisfies the concentration property. Lemma 1 directly yields the required properties (P2) and (P2’), respectively. The remaining properties (P3’) and (P4’) follow form Lemma 2. We have for (P3’):
Using and for all leads to and so (P3’) is satisfied.
It remains to prove (P4’). We have
In the last step we used the fact that.
Hence we have shown (P2’)-(P4’) and thereby demonstrated that is an admissible kernel which finishes the proof.
4. Outlook: Extension to 2D
To treat the 2D case we now consider the square and a - periodic function. The Fourier series associated with is then given as
(1.10)
where
As in the one-dimensional case there is a complex form given by
where
However, unlike in the one-dimensional case, a conjugate Fourier series in two dimensions can not be derived from a complex power series on a polydisc, cp. [12]. Hence, one can derive only formally three different conjugate series, namely 1) conjugation w.r.t. the first variable
2) conjugation w.r.t. the second variable
3) conjugation w.r.t. both variables
cp. [13]. The conjugation w.r.t. one variable is a straight-forward extension of the one-dimensional case and has been covered for example in [3] both for the classical and generalised concentrated approach. We will now consider partial sums of the conjugate series w.r.t. both variables and thus define
(1.11)
Much can be said about conjugate Fourier series in multiple space dimensions and the interested reader is referred to [12-17]. The two formal conjugate series’ for each of the single variables are of no interest to us but we can easily see from these that the complex form of the one-dimensional conjugate series is
with
We are only interested in the main result of [9] where Móricz extends the celebrated result Theorem 8 to double series.
Theorem 11 (Móricz 2001) Let, , and
If there exists a number such that
and if there is a constant such that
where, then
As is well known from finite difference calculus,
and so we may conclude that the partial sums of the conjugate Fourier series w.r.t. both variables gives rise to an indicator of the jump in the mixed derivative, namely. Some approaches of this fully 2D edge detection using generalised conjugated partial sums are covered in [10] and would go beyond the scope of this paper. In summary, these generalised sums yield much better results that the classical ones and thus can be successfully used for enhanced edge detection.
5. Conclusion
Summarizing this work we have first given a review of both classical as well as modern approaches to detect jump discontinuities using conjugated Fourier partial sums. The ideas proposed by Gelb and Tadmor [1] of accelerating the convergence by using concentration kernels give an enormous improvement in the 1-d case. We have proven their main result for the discrete case in every detail using different estimates and techniques and thus have extended it to - instead of -functions as concentration factors. Furthermore, the concentration property for discrete concentration factors was proven with different techniques.
Interesting questions arise when the 2-d case is considered. Since the expansion of the conjugated partial sum is not unique, there are three different approaches, in which two of them (the pseudo-2-d case) have been covered by Gelb and Tadmor [3]. The fully 2-d case was considered by Móricz [9] only for the classical conjugated sum. It is an interesting question how generalised 2-d conjugated partial sums would behave if they were considered. Another field of future interest is the accuracy and efficiency of extensions of the edge detection procedure to different numerical methods for hyperbolic conservation laws as the Discontinuous Galerkin or Spectral Difference approach including numerical tests. Some of these topics have been covered in [10], but most parts are still subject to current research.
NOTES
1Although we consider Fourier series on we have given the results of Fejér here as they appear in [5] on.
2We have already tacitly not mentioned this assumption in the discussion of [5].
3Note that the minus sign is absent in [7] since Lukács—as Fejér—considers to be the conjugate series.