Baseband Optimal Sampling

Figure 2: 2D regular rectangular and hexagonal sampling in the spatial and frequency domains.

	spatial domain	frequency domain
rectangular sampling
hexagonal sampling

Usually, no a priori knowledge is available about the (continuous) underlying functions we are sampling. Therefore, we assume that these functions are isotropic, i.e., that they do not have a preferred direction. Another common assumption is that they are band-limited. Both assumptions together result in the property that the frequency responses of such functions are hyper-spheres (circles in 2D and spheres in 3D, respectively).

Sampling such spherically band-limited functions results in replicating the primary spectrum in the frequency domain [15]. In order to reconstruct the underlying continuous signal perfectly, we need to ensure that the samples in spatial domain are close enough, so that the aliased spectra in the frequency domain do not overlap. Optimal sampling is achieved when the number of samples that fulfill this condition is minimal. In 1D this is also known as the Nyquist sampling rate. In order to optimally sample in higher dimensions (i.e., to use as few samples as possible), aliased spectra in the frequency domain have to be packed as closely as possible. This problem is known as the sphere packing problem [14], which has been extensively studied and solutions for regular packing structures in 2D and 3D exist.

As a motivation and for the sake of simplicity we will first describe our method to find an optimal sampling pattern in 2D before we delve into the mysterious structure of 3D Euclidian space.

Optimal sampling density in 2D

We will describe sampling as a mapping from indices to actual sample positions [4]:

$$\left( \begin{array}{c} x\\ y \end{array}\right) = V \cdot \left( \begin{array}{c} i\\ j \end{array}\right)$$ (1)

Here the integers $i, j$ are the indices of the sample and $x, y$ is the corresponding sampling position. The matrix $V$, which is called sampling matrix, describes the mapping itself, e.g.,

$$V_{rect2D} = \left( \begin{array}{cc} T_1 & 0\\ 0 & T_2\end{array}\right)$$ (2)

is the matrix for rectangular sampling which simplifies to the commonly used regular (Cartesian) sampling for $T_1 = T_2$. Hexagonal sampling is most conveniently described by the matrix

$$V_{hex2D} = \left( \begin{array}{cc} T_1 & \frac{1}{2}T_1\\ 0 & T_2\end{array}\right) \qquad \textrm{for } T_2 = \frac{\sqrt{3}}{2}T_1$$ (3)

which virtually just performs a shear of the rectangular samples followed by a for-shortening. When $V$ describes the sampling in spatial domain, the matrix $U$, satisfying

$$U^\top V = 2\pi I$$ (4)

with $U^\top$ being the transpose of $U$ and $I$ being the identity matrix, describes the positions of the replicas in frequency domain. $U$ is therefore called the periodicity matrix [4]. Applying Eq. 4 to Eq. 2 we obtain the periodicity matrix for rectangular sampling

$$U_{rect2D} = \left( \begin{array}{cc} u_1 & 0\\ 0 & u_2\end{array}\right)$$ (5)

with $u_1 = \frac{2\pi}{T_1}$ and $u_2 = \frac{2\pi}{T_2}$. The periodicity matrix for hexagonal sampling is

$$U_{hex2D} = \left( \begin{array}{cc} u_1 & 0\\ -\frac{1}{2}u_2 & u_2\end{array}\right) \qquad \textrm{for } u_2 = \frac{2}{\sqrt{3}}u_1$$ (6)

where again $u_1 = \frac{2\pi}{T_1}$. The 2D Fourier Transform $F$ of a circularly band-limited signal has the property

$$\mathrm{F}(\omega_1, \omega_2) = 0 \qquad \textrm{for } \omega_1^2 + \omega_2^2 \geq W^2$$ (7)

where $W$ is the maximum frequency in the data set. This baseband can be inscribed, for example, in a square with length $l = 2W$ (corresponding to rectangular sampling). In other words, $u_1$ and $u_2$ in Eq. 5 have to be equal to $2W$. On the other hand, the baseband can also be inscribed in a hexagon with side length $l = \frac{2}{\sqrt{3}}W$ (corresponding to hexagonal sampling). This means that in Eq. 6 $u_2$ must be equal to $2W$ (see Fig. 2). Calculating the sampling matrices from these periodicity matrices, we end up with

$$V_{rect2D} = \left( \begin{array}{cc} \frac{\pi}{W} & 0\\ 0 & \frac{\pi}{W}\end{array}\right)$$ (8)

where

$$\vert\textrm{det }V_{rect2D}\vert = \frac{\pi^2}{W^2}$$ (9)

and

$$V_{hex2D} = \left( \begin{array}{cc} \frac{2}{\sqrt{3}}\frac{\pi}{W} & \frac{1}{\sqrt{3}}\frac{\pi}{W} \\ 0 & \frac{\pi}{W}\end{array}\right)$$ (10)

where

$$\vert\textrm{det }V_{hex2D}\vert = \frac{\pi^2}{W^2}\frac{2}{\sqrt{3}}.$$ (11)

The sampling density is proportional to $\frac{1}{\textrm{det }V}$ [4]. By taking the ratio

$$\frac{\vert\textrm{det }V_{rect2D}\vert}{\vert\textrm{det }V_{hex2D}\vert} = \frac{\sqrt{3}}{2} = 0.866$$ (12)

we see that hexagonal sampling requires 13.4% fewer samples than rectangular sampling.

Optimal sampling density in 3D

Analogous to the 2D case, we can describe the mapping from indices $i, j, k$ to coordinates $x, y, z$ for rectilinear grids using the following matrix:

$$V_{rect3D} = \left( \begin{array}{ccc} T_1 & 0 & 0\\ 0 & T_2 & 0\\ 0 & 0 & T_3\end{array}\right)$$ (13)

which is regular (rectangular) when $T_1 = T_2 = T_3$.

As expected, regular rectangular sampling in 3D is (as in 2D) not optimal. It is important to note that an optimal sphere packing for arbitrary packing structures in 3D is not known. However, several optimal packing structures, all with equal sampling density, are known for the case of regular sampling, i.e., structures that can be described by three base vectors. Fortunately, this is exactly what we need, since we do not want to sacrifice the implicit indexing of the grid points that makes regular grid representations so attractive.

Among the optimal regular packing structures are the hexagonal close packed (hcp) structure and the face centered cubic (fcc) structure [3]. In order to achieve a close packing in the frequency domain using an fcc lattice (the reason why not using an hcp lattice is explained at the end of this section), we use the following matrix:

$$U_{fcc} = U_{fcc}^\top = \left( \begin{array}{ccc} u & 0 & u\\ 0 & u & u\\ u & u & 0\end{array}\right)$$ (14)

An fcc lattice consists of simple cubic cells with additional sampling points in the center of each cell face. One cell of an fcc lattice is depicted in Fig. 3 with the base vectors from Eq. 14.

By plugging Eq. 14 in Eq. 4 we end up with a sampling matrix in spatial domain which describes a body centered cubic (bcc) lattice:

$$V_{bcc} = \frac{1}{2} \left( \begin{array}{rrr} T & -T & T\\ -T & T & T\\ T & T & -T \end{array}\right)$$ (15)

with $T = \frac{2\pi}{u}$.

A bcc lattice also consists of a simple cubic cell but with only one additional sampling point, which is right in the center of the cell. Fig. 4 depicts one cell of a bcc lattice. Note, that the base vectors of Fig. 4 do not correspond to Eq. 15, as these are rather unintuitive. We chose another set of base vectors, which is more convenient for our purpose of indexing the data points (see Section 3.1). They are described by the sampling matrix

$$V_{bcc} = \left( \begin{array}{ccc} T & 0 & \frac{1}{2}T\\ 0 & T & \frac{1}{2}T\\ 0 & 0 & \frac{1}{2}T \end{array}\right)$$ (16)

It is easily verified that the sampling matrices in Eqs. 15 and 16 describe the same set of sample points.

To guarantee that the replicas in frequency domain do not overlap, $u$ must be equal to $2W$ for rectangular sampling. Since the periodicity matrix is analogous to the 2D periodicity matrix we end up with

$$\vert\textrm{det }V_{rect3D}\vert = \frac{\pi^3}{W^3}$$ (17)

For the fcc lattice, $u$ must be equal to $\sqrt{2}W$, which yields

$$\vert\textrm{det }V_{bcc}\vert = \frac{\pi^3}{W^3}\sqrt{2}$$ (18)

By again taking the ratio

$$\frac{\vert\textrm{det }V_{rect3D}\vert}{\vert\textrm{det }V_{bcc}\vert} = 0.707$$ (19)

we see that we need 29.3% fewer samples than with rectangular sampling. This means that if we sample a function on a regular rectangular grid with sampling distance $T_r$, we can increase the sampling distance $T_b$ for a bcc grid to $\sqrt{2}T_r$.

Figure 3: One cell of an fcc lattice with base vectors $u_i$. The black dots mark additional sample points (in the center of the faces) as compared to a simple cubic cell.

Figure 4: One cell of a bcc structure with base vectors $b_i$. The only difference to a simple cubic cell is one additional sample point right in the center of the cell, marked with a black dot.

In the above example we started with an fcc lattice in the frequency domain which resulted in a bcc lattice in the spatial domain. We could also choose an hcp lattice, since it has the same packing density as an fcc lattice [3]. However, an hcp lattice in the frequency domain is also an hcp lattice in the spatial domain and hcp lattices are rather difficult to index [7]. Therefore, we prefer to use a bcc grid.