ABSTRACT

In [1] and some following publications, Tadmor and Gelb took up a well known property of conjugate Fourier series in 1-d, namely the property to detect jump discontinuities in given spectral data. In fact, this property of conjugate series is known for quite a long time. The research in papers around the year 1910 shows that there were also other means of detecting jumps observed and analysed. We review the classical results as well as the results of Gelb and Tadmor and demonstrate their discrete case using different estimates in all detail. It is worth noting that the techniques presented are not global but local techniques. Edges are a local phenomenon and can only be found appropriately by local means. Furthermore, applying a different approach in the proof of the main estimate leads to weaker preconditions in the discrete case. Finally an outlook to a two-dimensional approach based on the work of Móricz, in which jumps in the mixed second derivative of a 2-d function are detected, is made.

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’)

(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.

REFERENCES

NOTES

^*Corresponding author.

¹Although we consider Fourier series on we have given the results of Fejér here as they appear in [5] on.

²We have already tacitly not mentioned this assumption in the discussion of [5].

³Note that the minus sign is absent in [7] since Lukács—as Fejér—considers to be the conjugate series.