## Separability

Consider Eq. (1) or (4) in multidimensions, with q>1. To simplify the situation, we restrict the interpolant or the noninterpolating ^ to be finite-support. Without loss of

FIGURE 4 Blurring. Iterated rotation may lose many small-scale structures when the quality of interpolation is insufficient (center). Better quality results in less loss (right). (Left) Original.

FIGURE 5 (Left) Nonseparable 2D interpolation with a square support of side 5 (25 function evaluations). Large central black dot: coordinate x at which f (x) = ckV(x — k) is computed. All black dots: coordinates x corresponding to the computation of ^(x — k). (Right) Separable 2D interpolation (10 function evaluations). Large central black dot: coordinate x where the value f(x) = c^1ji2v(x1 — ki)^ v(x2 — k2) is computed. All black dots: coordinates xt corresponding to the computation of (p(xt — kt). (Left and Right) The white and gray dots give the integer coordinates k where the coefficients Ck are defined. Gray dots: coefficients Ck that contribute to the interpolation.

FIGURE 5 (Left) Nonseparable 2D interpolation with a square support of side 5 (25 function evaluations). Large central black dot: coordinate x at which f (x) = ckV(x — k) is computed. All black dots: coordinates x corresponding to the computation of ^(x — k). (Right) Separable 2D interpolation (10 function evaluations). Large central black dot: coordinate x where the value f(x) = c^1ji2v(x1 — ki)^ v(x2 — k2) is computed. All black dots: coordinates xt corresponding to the computation of (p(xt — kt). (Left and Right) The white and gray dots give the integer coordinates k where the coefficients Ck are defined. Gray dots: coefficients Ck that contribute to the interpolation.

generality, we assume that this support is of size Sq (e.g., a 6.2 Symmetry square with side S in two dimensions, a cube in three dimensions). This means that the equivalent of 1-D interpolation with a synthesis function requiring, say, 5 evaluations, would require as many as 125 function evaluations in 3-D. Figure 5 shows what happens in the intermediate 2-D situation. This large computational burden can only be reduced by imposing restrictions on An easy and convenient way is to ask that the synthesis function be separable, as in

%ep(x) = n V(xii) Vx = (xl1 x21 ••• ' xq) e Rq■

The very beneficial consequence of this restriction is that the data can be processed in a separable fashion, line-by-line, column-by-column, and so forth. In particular, the determination of the interpolation coefficients needed for generalized interpolation is separable, too, because the form (4) is linear. In the previous example, the 53 = 125 evaluations needed in three dimensions reduce to 3 x 5 = 15 evaluations of a 1-D function when it is separable. We show in Fig. 5 how the 52 = 25 evaluations needed in the 2-D nonseparable case become 2x5 = 10 in the separable case. For the rest of this chapter, we concentrate on separable synthesis functions; we describe them and analyze them in one dimension, and we use the foregoing expression to implement interpolation efficiently in a multidimensional context.

Preserving spatial relations is a crucial issue for any imaging system. Since interpolation can be interpreted as the filtering (or equivalently, convolution) operation proposed in Eq. (3), it is important that the phase response of the involved filter not result in any phase degradation. This consideration translates into the well-known and desirable property of symmetry such that ^(x) = p(— x) or ^int(x) = ^int(— x). Symmetry is satisfied by all synthesis functions considered here, with the possible minor and very localized exception of nearest-neighbor interpolation. Symmetry implies that the only coefficients ck that are needed in Fig. 5 are those that are closest to the coordinates x corresponding to the computation of ^(x — k). In the specific case of Fig. 5, there are 25 of them, both for a separable ^sep and a non-separable

0 0