Image Processing Reference
In-Depth Information
7.4 Convolution with Separable Filters
The 1D convolution, Eqs. (7.25) and (7.31), and the FT results are also valid in
multiple dimensions. Specially, when the filter size is large, it is more efficient to
perform the convolution in the frequency domain for general filters. However, there
is an exception to this rule if filters have a special form.
Here we will discuss how to implement a special class of filters in multiple di-
mensions, separable filters, that can be implemented very quickly. This class covers a
frequently used type of filters used in bandpass or scale space filtering, e.g., to change
the size of an image or to compress it. We discuss it for 2D continuous functions here,
but the results are also valid for both types of discrete convolutions discussed above,
and for even higher dimensions than 2.
Definition 7.5.
A function
g
(
x, y
)
is called a
separable function
if
g
(
x, y
)=
g
1
(
x
)
g
2
(
y
)
(7.33)
Assume that
g
(
x, y
) is a separable filter function with which we wish to convolve the
function
f
(
x, y
). Using separability of
g
, we can rewrite the convolution:
f
)(
x, y
)=
g
(
τ
x
,τ
y
)
f
(
x
h
(
x, y
)=(
g
∗
−
τ
x
,y
−
τ
y
)
dτ
x
dτ
y
(7.34)
=
g
1
(
τ
x
)
τ
y
)
dτ
y
dτ
x
g
2
(
τ
y
)
f
(
x
−
τ
x
,y
−
=
g
1
(
τ
x
)[
h
(
x
−
τ
x
,y
)]
dτ
x
(7.35)
h
)(
x, y
)
=(
g
1
∗
(7.36)
where
h
introduced in Eq. (7.35) is a function that represents the intermediary result:
h
(
x, y
)=
h
)(
x, y
)
g
2
(
τ
y
)
f
(
x, y
−
τ
y
)
dτ
y
=(
g
2
∗
(7.37)
This is in fact a convolution that involves only one of the argument dimensions of
f
(
x, y
), i.e.,
y
. It is computed by integrating along the
y
-axis of the image with the
1D filter
g
2
(
y
). The operation that follows is also a pure 1D convolution, but applied
to the
result
of the first convolution and along the remaining dimension,
x
,sothat
we can write the entire operation as a cascade of 1D convolutions.
h
(
x, y
)=(
g
1
(
x
)
·
g
2
(
y
))
∗
f
(
x, y
)=
g
1
(
x
)
∗
(
g
2
(
y
)
∗
f
)
(7.38)
Assuming that, in practice, the filter as well as the image are discrete, and the integra-
tions have to be implemented as summations, we can estimate the cost of convolution
as the number of arithmetic operations
2
per image point. If the filter
g
is
m
×
m
, then
2
One arithmetic operation in computational cost estimation corresponds to one multiplica-
tion plus one addition.
