20.2.1 ToD in the Fourier Transformed Domain

The model after the Fourier transform of the data (20.2) is

(20.3)

Since the waveform is known, its Fourier transform G(ω) is known and the observation can be judiciously deterministically deconvolved (i.e., S(ω) is divided by G(ω) except when ) so that after deconvolution:

This model resembles the frequency estimation in additive Gaussian noise, where the ToD τ_ℓ induces a linear phase‐variation vs. frequency, rather than a linear phase‐variation vs. time as in the frequency estimation model (Chapter 16).

Based on this conceptual similarity, the discrete‐time model can be re‐designed using the Discrete Fourier transform (Section 5.2.2) over N samples to reduce the model (20.2) to (20.3):

(20.4)

where the ℓ th ToD τ_ℓ makes the phase change linearly over the sample index k

behaving similarly to a frequency that depends on the sampling interval Δt. If considering multiple independent observations with randomly varying amplitudes as in the model in Section 20.1, the ToD estimation from the estimate of coincides with frequency estimation, and the high‐resolution methods in Chapter 16 can be used with excellent results.

In many practical applications, there is only one observation () and the model (20.4) can be represented in compact notation (N is even):

where

and

contains the DFT of the waveform . The estimation of multiple ToDs follows from LS optimization of the cost function:

The LS method coincides with MLE when the noise samples W[k] are Gaussian and mutually uncorrelated. Since the DFT of Gaussian white process w(nΔt) leaves the samples W[k] to be uncorrelated due to the unitary transformation property of DFT, the minimization of J(α, ω) coincides with the MLE.

One numerical method to optimize J(α, ω) is by the weighted Fourier transform RELAXation (W‐RELAX) iterative method that resembles the iterative steps of EM (Section 11.6), where at every iteration the estimated waveforms are stripped from the observations for estimation of one single parameter [95]. In detail, let the set be known as estimated at previous steps, after stripping these waveforms

one can use a local metric for the ℓ th ToD and amplitude

As usual, this is quadratic wrt α_ℓ and it can be easily solved for the frequency ω_ℓ (i.e., the ℓ th ToD)

and the amplitude follows once has been estimated as

Iterations are carried out until some degree of convergence is reached. Improved and faster convergence is achieved by adopting IQML (Section 16.3.1) in place of the iterations of W‐RELAX.

The methods above can be considered extensions of statistical methods discussed so far, but some practical remarks are necessary:

• Any frequency domain method needs to pay attention to the shape of G(ω), or the equivalent DFT samples G[k]. In definitions, the range of G should be limited to those values that are meaningfully larger than zero to avoid instabilities in convergence. However, restricting the range for ω reduces ToD accuracy considerably as it is dominated by higher frequencies in the computation of the effective bandwidth (Section 9.4). Similar reasoning holds when performing deterministic deconvolution if using other high‐resolution methods, as the deconvolution 1/G(ω) can be stabilized by conditioning that is adding a constant term to avoid singularities such as , where η is a small fraction of max{|G(ω)|}.
• Conditioning and accuracy are closely related. In some cases in iterative estimates it is better to avoid temporary ToD estimates getting too close one another: one can set a ToD threshold, say Δω, that depends on the waveforms. In this case, the estimates from the iterative methods above that are too close, say and with and , are replaced by and to improve convergence and accuracy.

20.2.2 CRB and Resolution

As usual, the CRB is a powerful analytic tool to establish the accuracy bound. In the case of ToD, the performance depends on the waveforms and their spectral content as detailed in Section 9.4 for ToDs. When considering multiple delays, the CRB depends on the FIM entries, which for white Gaussian noise with power spectral density N₀/2 can be evaluated in closed form as:

Recall that the choice of the waveform is a powerful degree of freedom in system design to control ToD accuracy when handling multiple and interfering echoes. Choice of waveform and range can satisfy and so that two (or more) ToDs are decoupled and the correlation‐based ML estimator can be applied iteratively on each echo. In all the other contexts when and/or , the CRB for multiple echoes is larger than the CRB for one isolated echo due to the interaction of the waveforms, and it can be made dependent on their mutual interaction as illustrated in the simple example in Section 9.4 with .

With multiple echoes, resolution is the capability to distinguish all the echoes by their different ToDs. Let a measurement be of echoes in τ₁ and τ₂ () with the same waveform; it is obvious that when the two ToDs are very close, if not coincident, the two waveforms coincide and are misinterpreted as one echo, possibly with a small waveform distortion that might be interpreted as noise. Most of the tools to evaluate the performance in this situation are by numerical experiments using common sense and experience. To exemplify in Figure 20.3, if the variance from the CRB is and the two echoes cannot be resolved as two separated echoes and estimates interfere severely with one another. On the contrary, when noise is small enough to make , one can evaluate the resolution probability for the two ToD estimates and . A pragmatic way to do this is by choosing two disjoint time intervals and around τ₁ and τ₂; the resolution probability P_res follows from the frequency analysis that and are into the two intervals:

and the corresponding MSE in a Montecarlo analysis is evaluated for every simulation run conditioned to the resolution condition. Usually and have the same width around each ToD: and .

20.3.1 Correlation Method for DToD

In DToD, what matters is the relative ToD of one signal wrt the other as the two measurements are equivalent, and there is no preferred one. The cross‐correlation method is

(20.5)

where the two signals are shifted against one another until the similarities of the two signals are proved by the cross‐correlation metric. For discrete‐time sequences, the method can be adapted either to evaluate the correlation for the two discrete‐time signals, or to interpolate the signals while correlating (Appendix B). Usually the (computationally expensive) interpolation is carried out as second step after having localized the delay and a further ToD estimation refinement becomes necessary for better accuracy.

Performance Analysis

The cross‐correlation among two noisy signals (20.5) is expected to have a degradation wrt the conventional correlation method for ToD, at least for the superposition of noise and the unknown waveform. Noise is uncorrelated over the two sensors, for every α, but it has the same statistical properties. The MSE performance is obtained by considering the cross‐correlation for all the terms that concur in s₁(t) and s₂(t):

and using a sensitivity analysis around the estimated value of DToD that peaks the cross‐correlation, from the derivative:

Recall that is the sample estimate of the stochastic cross‐correlation for a stationary process:

To simplify the notation, let the DToD be ; then the derivative of the correlation can be expanded into terms²

where the Taylor series has been applied only for the deterministic term on true DToD (): . For performance analysis of DToD, it is better to neglect any fluctuations of the second order derivative of the correlation of the waveform, which are replaced by its mean value , and thus

It is now trivial to verify that the DToD is unbiased, while its variance (see properties in Appendix A, with )

(20.6)

depends on the power spectral densities of stochastic waveform S_gg(f) and noise S_ww(f). Once again, the effective bandwidth for stochastic processes for signal and noise

plays a key role in the DToD method. When considering bandlimited processes sampled at sampling interval Δt and bandwidth smaller than 1/2Δt (Nyquist condition), the effective bandwidth can be normalized to the sampling frequency to link the effective bandwidth for the sampled signal (say or for signal and noise)

Some practical examples can help to gain insight.

DToD for Bandlimited Waveforms

Let the noise be spectrally limited to B_w in Hz, with power spectral density for , and the spectral power density of the waveform upper limited to B_g (to simplify, ) with signal to noise ratio

The variance of DToD from (20.6) is

(20.7)

This decreases with the observation length T and ρ, when the term in brackets is negligible as for large ρ, or when the noise is wideband () and the ratio cannot be neglected anymore. For small signal to noise ratio it decreases as 1/ρ².

Another relevant example is when all processes have the same bandwidth () with the same power spectral density S(f) up to a scale factor: , when

From the Schwartz inequality , the variance is lower bounded by

(20.8)

This value is attained only for const.

The case of time sequences with white Gaussian noise can be derived from the results above. In this case the overall number of samples is with noise bandwidth and power . The effective bandwidth of the noise is and for the signal is so that the variance of DToD follows from (20.7):

When considering sampled signals, it is more convenient to scale the variance to the sample interval so as to have the performance measured in sample units:

This depends on the number of samples (N) and the signal to noise ratio ρ; again the term 1/ρ² disappears for large ρ. In the case that both waveform and noise are white (), and thus

(20.9)

More details on DToD in terms of bias (namely when ) and variance are in [96].

20.3.2 Generalized Correlation Method

The cross‐correlation method for DToD is the most intuitive extension of ToD, but there is room for improvement if rigorously deriving the DToD estimator from ML theory. Namely, the ML estimator was proposed by G.C. Carter [97] who gave order to the estimators and methods discussed within the literature of the seventies. We give the essentials here while still preserving the formal derivations.

The basic assumption is that the samples of the Fourier transform of data s_i(t) (for ) evaluated at frequency binning

are zero‐mean Gaussian random variables. Provided that T is large enough to neglect any truncation effect due to the DToD τ (see Section 20.4), the correlation depends on the cross‐spectrum

and it follows that

is uncorrelated vs. frequency bins. The rv at the k th frequency bin is

where

The set of rvs for all the N frequency bins are Gaussian and independent, and the log‐likelihood is (apart from constant terms)

Still considering a large interval T, the ML metric for becomes

where the dependency on the DToD τ is in the phase of S(f) as

The inverse of the covariance

depends on the coherence of the two rvs defined as:

The ML metric (τ) can be expanded (recall the property: ) to isolate only the delay‐dependent term:

(20.10)

The MLE is based on is the search for the delayed cross‐correlation of the two signals (term ) after being filtered by Ψ(f). In practice, the DToD is by the correlation method provided that the two signals are preliminarily filtered by two filters H₁(f) and H₂(f) such that as sketched in Figure 20.4.

Filter Design

Inspection of the coherence term based on the problem at hand

shows that it depends on the signal to noise ratio for every frequency bin

and it can be approximated as

it downweights the terms when noise dominate the signal. The filter Ψ(f) is

and a convenient way to decouple Ψ(f) into two filters is

(20.11)

where the first term decorrelates the signal for the waveform, and the second term accounts for the signal to noise ratio. If ρ(f) is independent of frequency, the second term is irrelevant for the MLE of DToD.

CRB for DToD

CRB can be derived from the log‐likelihood term that depends on the delay (20.10) and it follows from the definitions in Section 8.1:

or compactly

(20.12)

To exemplify, consider the case where signal and noise have the same bandwidth (e.g., this might be the case that lacks of any assumption on what is signal and what is noise, and measurements are prefiltered within the same bandwidth to avoid “artifacts”) with (i.e., this does not imply that const), then

coincides with the variance of correlation estimator (20.8) derived from a sensitivity analysis, except that any knowledge of the power spectral density of the waveform could use now the prefiltering (20.11) to attain an improved performance for the DToD correlator. If sampling the signals at sampling interval (i.e., maximal sampling rate compatible with the processes here), the sequences have samples in total and the CRB coincides with (20.9).

Even if the generalized correlation method is clearly the MLE for DToD, there are some aspects to consider when planning its use. The filtering (20.11) needs to have a good control of the model, and this is not always the case as the difference ToD is typically adopted in passive sensing systems where there is poor control of the waveform from the source, and the use of one measurement as reference for the others is a convenient and simple trick, namely when measurements are very large. In addition, the filtering introduces edge effects due to the filters’ transitions h(t) that limits the valid range T of the measurements. When filters are too selective, the filter response h(t) can be too long for the interval T and the simple correlation method (20.5) is preferred.

20.5.1 Wavefront Estimation in Remote Sensing and Geophysics

In remote sensing and geophysical signal processing, the estimation of the wavefront of delays (in seismic exploration these are called horizons since they define the ToD originated by the boundary between different media, as illustrated at the beginning of this Chapter) is very common and of significant importance. Even if these remote sensing systems are usually active with known waveform, the propagation over the dispersive medium and the superposition of many backscattered echoes severely distort the waveform, and make it almost useless for ToD estimation. However, in DToD estimation the waveform is similarly distorted for two neighboring sensors. This is exemplified in Figure 20.8 where the waveforms are not exactly the same shifted copy, but there is some distortion both in wavefront and in waveform (see the shaded area that visually compares the waveforms at the center and far ends of the array).

One common way to handle these issues is by preliminarily selecting those pair of sensors where the waveforms are not excessively distorted between one another, and this reduces the number of equations associated with the selected pairs of the overdetermined problem (20.13) to be smaller than (all‐to‐all configuration). This has a practical implication as the number of scans can be as in the seismic image at the beginning in Figure 20.1, and the use of M²/2 would be intolerably complex. Selecting the K neighbors (say ) can reduce the complexity to manageable levels KM/2. If M is not excessively large, one could still use all the pairs and account separately for the waveform distortion by increasing the DToD variance (20.12). As a rule of thumb, the distortion increases with the sensors’ distance , and this degrades the variance proportionally

for an empirical choice of the scaling term η and exponent γ.

It is quite common to have outliers in DToD and this calls for some preliminary data classification (Chapter 23). In addition to the robust estimation methods (Section 7.9), another alternative is to solve for (20.13) by using an L1 norm. These methods are not covered here as they are based on the specific application, but usually they are not in closed form even if the optimization is convex, and are typically solved by iterative methods.

20.5.2 Narrowband Waveforms and 2D Phase Unwrapping

In narrowband signals, the waveform is the product of a slowly varying envelope a(t) with a complex sinusoid:

where ω_o is the angular frequency. The delays are so small compared to the envelope variations that the signals at the sensors (i, j) are

and the correlator‐based DToD estimator (neglecting the noise only for the sake of reasoning)

yields the estimate of the phase difference

(20.14)

that is directly related to the DToD. Wavefront estimation is the same as above with some adaptations [99]: phase difference (and phase in general³) is defined modulo‐ 2π from the arg[.] of the correlation of signals. Since phase is wrapped within (herein indicated as [.]_2π) so that the true measured phase difference differs from the true one by multiple of 2π, unless . 2D phase unwrapping refers to the estimation of the continuous phase‐function

(or the wavefront ) from the phase‐differences (20.14) evaluated modulo‐ 2π (also called wrapped phase). The LS unwrapping is similar to problem (20.13) by imposing for any pair of measurements the equality

(20.15)

in the LS sense. The system becomes

(20.16)

that yields the LS solution

(20.17)

Since phase is measured modulo‐ 2π, the choice of the sensor’s pairs is not extended to all the sensors, but rather to the neighborhood of each sensor as the phase‐variation among neighbor sensors is expected to be mostly smaller than π.

The concept of phase aliasing is illustrated by the example in Figure 20.9 where phase ϑ_i increases along the sensors’ position and the wrapped phase [ϑ_i]_2π has 2π jumps when close to . If considering the angular difference of the phase between two points coarsely sampled 1:2 (gray points with double‐spacing ), the modulo‐ 2π value coincides with the true value except where phase difference (gray lines) while the wrapped phase difference (i.e., the wrapped phase difference can be considered as the smallest angular difference between two consecutive vectors). Since the phase difference estimated from the wrapped phase differs from the true one by (a multiple of) 2π, there is no way to retrieve these jumps that impair the overall estimated phase‐function by the unwrapping algorithm. This is called phase aliasing condition. If sampling is dense enough (gray and black points in Figure 20.9), the phase‐differences are likely to be coincident with the true (unwrapped) phase without any artifacts.

20.5.3 2D Phase Unwrapping in Regular Grid Spacing

In addition to wavefront estimation, 2D phase unwrapping has several notable applications in magnetic resonance imaging, optical interferometry, and satellite synthetic aperture radar (SAR) imaging. All these applications collect measurements over a regular grid spacing and the phase‐differences (20.15) are computed between neighboring points along two orthogonal directions. Since the transformation A is the derivative along the two dimensions, the phase differences can be partitioned along these two directions as

so that the LS estimate becomes

(20.18)

which can be solved efficiently by exploiting the structure of the linear operators and their sparsity—see Appendix C.

Inspection of the term shows that it contains the second order derivatives (i.e., discrete Laplace operator) of the unwrapped phase field , while the terms on the right of (20.18) are the first‐order derivatives of the phase‐differences. This is the basis for several detailed lines of thought on the impact of phase‐difference artifacts such as the 2π discontinuities on the final solutions. The reader is referred to the copious literature on this fascinating topic that deals with the phase field as a continuous field that is sampled, and phase unwrapping artifacts are the results of coarse sampling of these phase fields.

The example in Figure 20.10 shows the consequences of phase aliasing from the wrapped phase image [ϑ(x, y)]_2π using (20.18) when the phase image is down‐sampled 1:n (i.e., take one sample out of n in both directions) to simulate phase aliasing when evaluating phase‐differences. The estimated phase is (visually) not affected by 1:2 decimation even if some residual is still visible on residual , while it is more severely affected when decimation is larger, as for 1:5, most of the artifacts are in those areas where there is a sudden change of the phase‐function (e.g., in the face, where luminance is abruptly changing from black to white). Residuals for 1:2 or 1:5 show a pattern that resembles the electric field with dipoles, there is a close analytical relationship, but the explanation is beyond the scope of the introductory discussion.

One might argue that the solution to these artifacts could be to oversample the wavefields, but this is not always possible as the sensors’ density is given by the application. The interpolation of phase images cannot provide the solution as unfortunately phase information is related to the dynamics of the phase and not (easily) to the spectrum of the signals. Since phase aliasing introduces missing 2π jumps that are smeared by the LS method as diffused error (see 1:5 decimation around the face with abrupt black‐white discontinuities), these can be interpreted as outliers that are surely not‐Gaussian and the L2‐norm can be replaced with L1 metrics, possibly iterated. There are methods that solve for the LS phase estimate by cosine‐transforms, but this method is questionable for small images due to the poor control of artifacts at the boundary as consequence of the periodicity of the cosine‐transformation.

20.6.1 Delay and Sum Beamforming

Delay and sum beamforming extends the beamforming methods in Chapter 19 to wideband waveforms. Making reference to the model (20.19), the wideband beamforming method delays each signal by a certain shape parameters and sums all the N delayed signals from all sensors:

(20.20)

When the shape parameters match the th wavefield , this value flattens s(t, x) in (20.20) and the sum enhances it; the resulting signal becomes

(20.21)

where the three terms are the signal of interest, interference from the other wavefronts () that are reduced by the summing, and the noise that is reduced by 1/N. When , the signal is somewhat attenuated by the sum.

Wideband beamforming is shown in the example in Figure 20.12 for a point source at and (or as from the vertex of the hyperbolic wavefield) from the linear array, and propagation velocity is as for ultrasound systems with Ricker waveform (Section 9.4). The delay and sum beamforming is for varying source point and the clearest waveform is when as expected, with small artifacts when that decrease with N. The interference mitigation capability of delay and sum beamforming is shown for the same example when considering the presence on another interfering wavefield at and , and noise is affected by the impairment, but surely much less than the original observation s(t, x).

The corresponding Matlab code for delay and sum beamforming described here follows, together with the generation of the signal (a gray‐scale image is used in place of wiggle plot in the figure, which enhances any waveform distortion after the sum).

Remark 1: The signal after the delay and sum beamforming is maximized for those choices of the shape parameters that flattens the wavefields before summing up. The energy of within a predefined window can be used to estimate the presence or not of one source for a certain combination of shape parameters. The search is over the bidimensional pairs for the value(s) that peak(s) the energy metric, and time resolution is limited by the time window adopted in the energy metric.

Remark 2: After delaying, the sum in (20.21) can take into account the different degree of noise and interference occurring in the flattened wavefield. This is obtained by weighting the terms before summing, and the weighting can be designed according to the degree of noise and interference that is experienced in the sum. The optimal weighting is the same as for BLUE (Section 6.5) and depends on the inverse of the power of the noise and interference for the specific shape parameters :

with normalization

20.6.2 Wideband Beamforming After Fourier Taransform

Implementation of delay and sum beamforming for discrete‐time signals needs to interpolate the signals when the delay is fractional. This is carried out by appropriate filtering as part of the delay for discrete‐time signals as detailed in Appendix B.

Alternatively, one can use the delay after the Fourier transform of the wavefields vs. time, which has several benefits. The model (20.19) after FT is

and, for every frequency, it is the superposition of spatial sinusoids each with appropriate spatial varying amplitudes α_ℓ(x). A wideband beamforming becomes:

and avoids any explicit interpolation step.

Another simplification of wideband modeling is for far‐field when the wavefront is planar, or around a certain position .

When the amplitude variations across space is negligible () the model is

where

These are the sum of spatial sinusoids that can be handled using the theory of narrowband array processing as illustrated in Chapter 19.

Preliminarily, we can notice that for any WSS process x(t) the mean values can be evaluated as

where the last equality is due to the limited range of the autocorrelation within . If the interval T is much larger than the decorrelation of the process:

These approximations ease the computations of the terms:

that reduce to those in the main text.

Fractional delay (not sample‐spaced) of a discrete‐time signal is very frequent in statistical signal processing. Let x₁, x₂, …, x_N be a sequence to be delayed by τ samples, with τ non‐integer (otherwise, this would be simply a time‐shift of the samples) and sample index indicated by subscript. The solution is to interpolate the sequence with an appropriate continuous‐time interpolating function h(t) that estimates at best the continuous‐time signal:

assuming that the sampling interval is unitary. The interpolated signal can now be arbitrarily delayed

and the delayed signal is uniformly resampled to have the delayed sequence:

The last equality shows that the delayed sequence is the convolution of the original sequence and the interpolating function delayed by τ and resampled.

Accuracy of fractional delay depends on the choice of the interpolating function h(t) that must honor the original samples (i.e., ) as discussed in Section 5.5. The ideal interpolating function

is not commonly used as the tails decay too slowly and the sequence needs to be very long to avoid edge effects. One of the most common ways to interpolate is by using the spline (see the book by de Boor [100] for an excellent overview).

A very pragmatic way to delay a sequence is by the use of the discrete Fourier transform (DFT) under the assumption of periodicity of the sequence. Namely, from the sequence x₁, x₂, …, x_N, the DFT is computed and the result in turn is delayed by a linear phase:

In spite of its simplicity, there are pitfalls to be considered to avoid “surprises” after fractional delays. Namely, the use of the DFT still uses an interpolation, which can be easily seen from the definition of the inverse DFT of Y(k):

which is periodic over N samples. Namely, when using the DFT all sequences are periodic, even if not originally. If the delay τ is small and the original sequence tapered to zero, these wrap‐around effects are negligible. Alternatively, the original sequence can be padded by zeros up to N′ (with ) to make the implicit periodic sequence long enough to reduce these artifacts (but still not zero after non‐fractional delays). Needless to say, the DFT must be computed with basis N′.

Let denote the matrix of (unknown) delay function (bold font indicates matrix), and the matrixes of gradients, and the shift matrix (i.e., ). The ToD of the wavefront can be related to the DToD along the two directions for the neighboring points (gradients of the wavefront):

(20.22)

or equivalently

(20.23)

where and are operators for the evaluation of the gradients from the wavefront . The equation (20.23) represents an overdetermined set of linear equations and MN unknowns that can be rearranged using the properties of the Kronecker products (Section 1.1.1)

(20.24)

here and . The LS wavefront estimator is

(20.25)

or equivalently

(20.26)

which is the discrete version of the partial differential equation with boundary conditions [99], where (or ) is the discrete version of the second order derivative along x (or y). The matrixes are large but sparse, and this can be taken into account when employing iterative methods for the solution (Section 2.9) that converge even if A is ill conditioned (i.e., the update rule is independent of any constant additive value).

The Matlab code below exemplifies how to build the numerical method to solve for the wavefront from the set of DToD, or for 2D phase unwrapping when the phase‐differences are evaluated modulo‐ 2π. Since all matrixes D_x and D_y are sparse, its is (highly) recommended to build these operators using the sparse toolbox (or any similar toolbox).