i
i
i
i
i
i
i
i
200 9. Signal Processing
f has radius 2, f is evaluated at 1.3, 0.3, −0.7,and−1.7. Note that for discrete-
continuous convolution we generally write the sequence first and the filter second,
so that the sum is over integers.
As with discrete convolution, we can put bounds on the sum if we know the
filter’s radius, r, eliminating all points where the difference between x and i is at
least r:
(af)(x)=
x+r
i=x−r
a[i]f(x − i).
Note, that if a point falls exactly at distance r from x (i.e., if x −r turns out to be
an integer), it will be left out of the sum. This is in contrast to the discrete case,
where we included the point at i − r.
Expressed in code, this is:
function reconstruct(sequence a, filter f , real x)
s =0
r = f.radius
for i = x − r to x + r do
s = s + a[i]f(x − i)
return s
As with the other forms of convolution, discrete-continuous convolution may
be seen as summing shifted copies of the filter (Figure 9.15):
(af)=
i
a[i]f
→i
.
Discrete-continuous convolution is closely related to splines. For uniform
splines (a uniform B-spline, for instance), the parameterized curve for the spline
Σ
a[i ]
a[i ]f
j
a f
Figure 9.15. Reconstruction (discrete-continuous convolution) as a sum of shifted copies
of the filter.
i
i
i
i
i
i
i
i
9.2. Convolution 201
is exactly the convolution of the spline’s basis function with the control point
sequence (see Section 15.6.2).
9.2.6 Convolution in More Than One Dimension
So far, everything we have said about sampling and reconstruction has been one-
dimensional: there has been a single variable x or a single sequence index i.
Many of the important applications of sampling and reconstruction in graphics,
though, are applied to two-dimensional functions—in particular, to 2D images.
Fortunately, the generalization of sampling algorithms and theory from 1D to 2D,
3D, and beyond is conceptually very simple.
Beginning with the definition of discrete convolution, we can generalize it to
two dimensions by making the sum into a double sum:
(ab)[i, j]=
i
j
a[i
,j
]b[i − i
,j− j
].
If a is a finitely supported filter of radius r (that is, it has (2r +1)
2
values),
then we can write this sum with bounds (Figure 9.16):
(ab)[i, j]=
i
=r
i
=−r
j
=r
j
=−r
a[i
,j
]b[i − i
,j−j
]
a[1, –1] a[0, –1] a[–1, –1]
a[1, 0] a[0, 0] a[–1, 0]
a[1, 1] a[0, 1] a[–1, 1]
j
i
Figure 9.16. The weights for the nine input samples that contribute to the discrete convolu-
tion at point (
i
,
j
)withafilter
a
of radius 1.
i
i
i
i
i
i
i
i
202 9. Signal Processing
and express it in code:
function convolve2d(sequence2da, sequence2d b,inti,intj)
s =0
r = a.radius
for i
= −r to r do
for j
= −r to r do
s = s + a[i
][j
]b[i − i
][j − j
]
return s
This definition can be interpreted in the same way as in the 1D case: each
output sample is a weighted average of an area in the input, using the 2D filter as
a “mask” to determine the weight of each sample in the average.
Continuing the generalization, we can write continuous-continuous (Figure
9.17) and discrete-continuous (Figure 9.18) convolutions in 2D as well:
y′
x′
(x, y)
f(–x′, –y′)dx ′dy′
dx′
dy′
Figure 9.17. The weight
for an infinitesimal area in
the input signal resulting
from continuous convolu-
tion at (
x, y
).
(fg)(x, y)=
f(x
,y
)g(x − x
,y− y
) dx
dy
;
(af)(x, y)=
i
j
a[i, j]f(x − i, y − j).
In each case, the result at a particular point is a weighted average of the input near
that point. For the continuous-continuous case, it is a weighted integral over a
region centered at that point, and in the discrete-continuous case it is a weighted
average of all the samples that fall near the point.
f(1.3, –1.5) f(.3, –1.5) f(–.7, –1.5) f(–1.7, –1.5)
f(1.3, –.5) f(.3, –.5) f(–.7, –.5) f(–1.7, –.5)
f(1.3, .5) f(.3, .5) f(–.7, .5) f(–1.7, .5)
f(1.3, 1.5) f(.3, 1.5) f(–.7, 1.5) f(–1.7, 1.5)
x
y
.5
.3
Figure 9.18. The weights for the 16 input samples that contribute to the discrete-continuous
convolution at point (
x, y
) for a reconstruction filter of radius 2.
i
i
i
i
i
i
i
i
9.3. Convolution Filters 203
Once we have gone from 1D to 2D, it should be fairly clear how to generalize
further to 3D or even to higher dimensions.
9.3 Convolution Filters
Now that we have the machinery of convolution, let’s examine some of the par-
ticular filters commonly used in graphics.
9.3.1 A Gallery of Convolution Filters
The Box Filter
The box filter (Figure 9.19) is a piecewise constant function whose integral is
equal to one. As a discrete filter, it can be written as
1
r–r
2r + 1
1
r–r
2r
x
i
Figure 9.19. The discrete
and continuous box filters.
a
box,r
[i]=
1/(2r +1) |i|≤r,
0 otherwise.
Note that for symmetry we include both endpoints.
As a continuous filter, we write
f
box,r
(x)=
1/(2r) −r ≤ x<r,
0 otherwise.
In this case, we exclude one endpoint which makes the box of radius 0.5 usable
as a reconstruction filter. It is because the box filter is discontinuous that these
boundary cases are important, and so for this particular filter, we need to pay
attention to them. We write just f
box
for the common case of r =
1
2
.
The Tent Filter
The tent, or linear filter (Figure 9.20) is a continuous, piecewise linear function:
Figure 9.20. The tent filter
and two scaled versions.
f
tent
(x)=
1 −|x||x| < 1,
0 otherwise;
f
tent,r
(x)=
f
tent
(x/r)
r
.
For filters that are at least C
0
(that is, there are no sudden jumps in the value,
as there are with the box), we no longer need to separate the definitions of the
i
i
i
i
i
i
i
i
204 9. Signal Processing
discrete and continuous filters: the discrete filter is just the continuous filter sam-
pled at the integers. Also note that for simplicity we define f
tent,r
by scaling the
“standard size” tent filter f
tent
. From now on, we’ll take this scaling for granted:
once we define a filter f, then we can use f
r
to mean “the filter f stretched out
by r and also scaled down by r.” Note that f
r
has the same integral as f,andwe
will always make sure that the value of the integral is equal to 1.0.
The Gaussian Filter
The Gaussian function (Figure 9.21), also known as the normal distribution, is
an important filter theoretically and practically. We’ll see more of its special
properties as the chapter goes on:
Figure 9.21. The
Gaussian filter.
f
g
(x)=
1
√
2π
e
−x
2
/2
.
The Gaussian does not have finite support, although because of the exponential
decay, its values rapidly become small enough to ignore. When necessary, then,
we can trim the tails from the function by setting it to zero outside some radius.
The Gaussian makes a good sampling filter because it is very smooth; we’ll make
this statement more precise later in the chapter.
The B-spline Cubic Filter
Many filters are defined as piecewise polynomials, and cubic filters with four
pieces are often used as reconstruction filters. One such filter is known as the B-
spline filter (Figure 9.22) because of its origins as a blending function for spline
curves (see Chapter 15):
Figure 9.22. The B-spline
filter.
f
B
(x)=
1
6
⎧
⎪
⎨
⎪
⎩
−3(1 −|x|)
3
+3(1−|x|)
2
+3(1−|x|)+1 −1 ≤ x ≤ 1,
(2 −|x|)
3
1 ≤|x|≤2,
0 otherwise.
Among piecewise cubics, the B-spline is special because it has continuous first
and second derivatives—that is, it is C
2
. A more concise way of defining this
filter is F
B
= f
box
f
box
f
box
f
box
; proving that the longer form above is
equivalent is a nice exercise in convolution (see Exercise 3).
The Catmull-Rom Cubic Filter
Figure 9.23. The Catmull-
Rom filter.
Another piecewise cubic filter named for a spline, the Catmull-Rom filter (Figure
9.23), has the value zero at x = −2, −1, 1,and2, which means it will interpolate
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.