Sampling of functions with symmetries

Frank Natterer

February 1998

Let f be a function on IR^{n} which is sampled on the grid L_{1} = W_{1} Z^{n} + w_{1}, where W_{1} is a nonsingular real (n, n)-matrix and w_{1} an n-vector, the set-off. Assume that the support of f̂ is contained in a set K ⊆ IR^{n}. Then, f can be recovered exactly from the sampled values provided that

(K + ξ) ∩ (K + ξ′) = ϕ ,  ξ, ξ′ ∈ L_{1}^{⊥} , ξ ≠ ξ′  (1)

where L_{1}^{⊥} is the reciprocal lattice 2πW_{1}^{−T} Z^{n} [3].

In this note we address the following question. Assume f has the symmetry

f(Ax + a) = f(x)

for some real invertible (n, n)-matrix A and n-vector a. Then, f is known automatically on L_{2} = AL_{1} +a = W_{2}Z^{n} +w_{2} with W_{2} = AW_{1}, w_{2} = Aw_{1} +a. Can we use this additional information on f to reconstruct f under weaker assumptions on L_{1} than (1)? Below we give 3 examples. In the first two (the first one is trivial) the answer is yes. In the third one we don’t know.

Examples

1) Let n = 1 and K = [−Ω, Ω], i.e. f is an Ω- band-limited function. Let A = −1 and a = 0, i.e. f is even. By Shannon’s sampling theorem f can be recovered from any of the grids L = hZ + w provided h ≤ \frac{π}{Ω}. Let L_{1} = 2hZ + h/2. Then, L_{2} = 2hZ − h/2, and

L_{1} ∪ L_{2} = hZ + h/2 ,

see Fig. 1. Thus it suffices to sample f on L_{1} which is twice as coarse as required by Shannon’s theorem in the absence of symmetries.

If f, g satisfy the conditions on f, then

∫ fg dx = h ∑_{x∈L} f(x)g(x) = 2h ∑_{x∈L_{1}} f(x)g(x) .

Thus we can evaluate inner products by the trapeziodal rule on the coarse grid L_{1}.

2) Let g = Rf be the Radon transform of a function f in IR^{2} which is essentially Ω-band-limited. As a function of φ and s, g has the symmetries

g(φ + π, −s) = g(φ, s) ,

i.e.

A = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) , a = ( \begin{matrix}π \\ 0 \end{matrix} ) .

We sample g on the grid

L_{1} = \begin{aligned}φ & = & Δφ · j & , & j = 0, …, p − 1 , \\ s & = & Δs · (ℓ + 1/4) & , & ℓ ∈ Z . \end{aligned}

Here, Δφ = 2π/p with p odd. We call L_{1} a grid with quarter set-off. We have

\begin{aligned}W_{1} & = & ( \begin{matrix}Δφ & 0 \\ 0 & Δs \end{matrix} ) & , & w_{1} & = & ( \begin{matrix}0 \\ Δs/4 \end{matrix} ) & , \\ W_{2} & = & ( \begin{matrix}Δφ & 0 \\ 0 & −Δs \end{matrix} ) & , & w_{2} & = & ( \begin{matrix}π \\ −Δs/4 \end{matrix} ) & , \end{aligned}

i.e., since p is odd and g has period 2π in φ,

L_{2} : \begin{aligned}φ & = & Δφ(j + 1/2) & , & j = 0, …, p − 1, \\ s & = & Δs(ℓ − 1/4) & , & ℓ ∈ Z . \end{aligned}

Combining L_{1} and L_{2} yields the grid L from Fig. 2, namely

L : \begin{aligned}φ & = & \frac{Δφ}{2}j & , & j = 0, …, 2p − 1 , \\ s & = & Δs(ℓ + 1/4) & , & ℓ ∈ Z , ℓ + j even . \end{aligned}

L is the interlaced grid suggested by Cormack [1] and Rattey-Lindgren [6]. The sampling requirements for the grids L_{1}, L_{2}, L are as follows. Assume that f(x) = 0 for |x| > ρ and that f is essentially Ω-band-limited. f can be recovered reliably from the values of g on L_{1} provided that

Δφ ≤ \frac{π}{Ωρ} , Δs ≤ \frac{π}{Ω} .

This is a classical result in tomography, see e.g. [4].

Thus the required number of data is

\frac{2π}{Δφ} · \frac{2ρ}{Δs} = \frac{4}{π} ρ^{2}Ω^{2} .

For the interlaced grid L the sampling requirements are

\frac{Δφ}{2} ≤ \frac{π}{Ωρ} , \frac{Δs}{2} ≤ \frac{π}{Ω} ,

leading to \frac{1}{π}ρ^{2}Ω^{2} data points [2]. This is only 1/4 of the gridpoints of L_{1} or of any translate thereof. Note that we can do with \frac{2}{π}ρ^{2}Ω^{2} data points simply by choosing p even and the grid L_{1} without the set-off. Then, by the symmetry of g, the scanning can be restricted to j < p/2 leaving us with \frac{2}{π}ρ^{2}Ω^{2} data points.

It is clear that inner products can be evaluated on L_{1} exactly as in example 1, with h replaced by ΔφΔs.

3) Now let g be the fan beam transform of f, i.e.

g(β, α) = (Rf)(β + α, r sin α)

where r ≥ ρ and f(x) = 0 for |x| ≥ ρ. g is invariant under the affine transformation with

A = ( \begin{matrix}1 & 2 \\ 0 & −1 \end{matrix} ) , a = ( \begin{matrix}π \\ 0 \end{matrix} )

which, incidentally, is involutory.

We sample g on the grid

L_{1} : \begin{aligned}β & = & \frac{2π}{p}j & , & j = 0, …, p − 1 \\ α & = & \frac{2π}{p}a(ℓ + c) & , & ℓ ∈ Z . \end{aligned}

Here, c is the detector set-off. The parameter a can be chosen freely, but sampling theory [5] suggest the value ρ/(r + ρ), which, for commercial scanners, is rather small, typically 0.20. In our notation,

\begin{aligned}W_{1} & = & \frac{2π}{p} ( \begin{matrix}1 & 0 \\ 0 & a \end{matrix} ) & , & w_{1} & = & \frac{2π}{p} ( \begin{matrix}0 \\ ac \end{matrix} ) & , \\ W_{2} & = & \frac{2π}{p} ( \begin{matrix}1 & 2a \\ 0 & −a \end{matrix} ) & , & w_{2} & = & \frac{2π}{p} ( \begin{matrix}2ac + p/2 \\ −ac \end{matrix} ) & . \end{aligned}

Thus we obtain for L_{2}

L_{2} : \begin{aligned}β & = & \frac{2π}{p}(j + 2aℓ + 2ac + p/2) & , & j = 0, …, p − 1 \\ α & = & −\frac{2π}{p}a(ℓ + c) & , & ℓ ∈ Z . \end{aligned}

The combined grid L = L_{1} ∪ L_{2} may now be quite complicated, and it is not clear how to deal with sampling on L. At least we want to avoid redundancy, i.e. we want to avoid that L_{1}, L_{2} represent the same lines. It is easily seen that redundancy occurs exactly in the following cases:

(i) p even , 2a  integer , c = 0 ,
(ii) p even , a  integer , c = 1/2 ,
(iii) p odd , a − \frac{1}{2} integer , c = 1/2 .

Since the conditions on a are not satisfied for commercial scanners, redundancy will not occur in practice.

In commercial scanners, a detector set-off is available, at least as an option. So the existence of a parameter c such that the sampling properties of L are considerably better than those of L_{1} would be of immediate practical interest.

The conditions (i), (ii), (iii) characterize complete redundancy, i.e. each of the lines is represented exactly twice. A common way to prevent even partial redundancy is the quarter set-off, i.e. c = 1/4. In that case, L has the form

L : \begin{aligned}β & = & \frac{2π}{p}(j + γ_{ℓ}) & , & j = 0, …, p − 1 \\ α & = & \frac{πa}{p}a(ℓ + 1/2) & , \end{aligned}

where γ_{ℓ} is the non-integer part of 2aℓ + \frac{p+a}{2}. Except for this shift, L is a fan-beam geometry with p sources and the detector spacing πa/p (as opposed to 2πa/p for L_{1}). Thus one is tempted to take as sampling conditions for L those of [5] for such a geometry, i.e.

\frac{2π}{p} ≤ \frac{r + ρ}{ρ} \frac{π}{rΩ} , \frac{πa}{p} ≤ \frac{π}{rΩ} ,

allowing for a detector spacing twice as large as for L_{1}. However, this conclusion is questionable since the analysis of [5] is based on the rather special shape of the essential support of ĝ.

Fig. 1: The grids L_{1}(·), L_{2}(∗) for example 1. They combine to yield the grid L of stepsize h.

Fig. 2: The grids L_{1}(·), L_{2}(∗) for example 2 for p = 7. They combine to yield the interlaced grid L. The dotted line is at φ = π. Due to the oddness of p it is lying exactly between neighbouring gridpoints of L_{1}.

References

[1] Cormack, A. M.: Sampling the Radon transform with beams of finite width, Phys. Med. Biol. 23, 1141-1148 (1978).

[2] Faridani, A.: An application of a multidimensional sampling theorem to computed tomography, Contemporary Mathematics 113, 65-79 (1990).

[3] Faridani, A.: A generalized sampling theorem for locally compact abelian groups, Math. Comp. 63, 307-327 (1994).

[4] Natterer, F.: The mathematics of computerized tomography. Wiley-Teubner 1986.

[5] Natterer, F.: Sampling in fan beam tomography, SIAM J. Appl. Math. 53, 358-380 (1993).

[6] Rattey, P.A. - Lindgren, A.G.: Sampling the 2D Radon transform, IEEE Trans. Acoust. Speech Signal Processing, A SSP-29, 994-1002 (1981).

1

1/u/berg/f/berger/paperfne/Samfunsym.tex