Graphics Reference
In-Depth Information
concept, consider Figure 10.3, where the original image is shown, as well as the filter ker-
nel, during processing of a single pixel location.
If we consider this filter shifting operation in the context of what our shader program
must do to implement it, we can see that for every pixel in the output image, we must load
the image data surrounding the current pixel, apply the filter image to the loaded data, and
then sum the individual results and store the value in the output image. This is repeated
for every pixel of the output image. With this in mind, we can clearly see how the size of
the filter kernel can significantly impact the computational cost of performing a filtering
operation, since each pixel requires a number of calculations proportional to the filter size.
This interpretation is relatively simple to visualize, and provides a sufficient view of
image processing for the implementation discussions later in the chapter. However, this
description is only valid for a subset of image processing filters. Many other filters perform
different types of calculations over a pixel's surrounding neighborhood. Fortunately, the
same basic concept is still used in the other algorithms as well, in which a small neighbor-
hood of pixels surrounding the current pixel is loaded, some calculations are performed
on them, and the results of those calculations are used to determine the value that will be
stored in the output image. We will see this pattern in each of the algorithms that we imple-
ment in this chapter.
Of course, there is a significant amount of additional mathematical theory and analysis
that will be useful to a developer of image filtering algorithms, including frequency domain
representations, the various properties of filters in both spatial and frequency domains, and
alternative filter implementations and their trade-offs. As mentioned earlier, the reader is in-
vited to further explore these and other details in a complete image processing text.
10.1.3
Separable Filters
There is one final point to discuss before moving on to our sample algorithm implementa-
tions. Some filter kernels can be decomposed from a single 2D kernel into two ID kernels
that can be applied separately. This is depicted graphically in Figure 10.4.
This filter kernel is referred to as
separable,
a very important property for a filter
to exhibit due to its performance implications. In general, for a 2D filter of size
p×q
to
be applied to an image of size
m×n,
the number of operations that need to be performed
is proportional to
p*q*m*n.
However, if a filter is separable, it can be performed in two
steps—one for each of the ID filter kernels that the original 2D filter kernel is decomposed
into. This results in
p*m*n
operations in the first step, and
q*m*n
operations in the second
step. In comparison to the original 2D filter kernel, a separable filter reduces the number
of operations from
p*q*m*n
to
(p+q)*m*n.
This is a significant reduction in calculations,
especially when the values of
p
and
q
are relatively large. We will utilize this separability
property in our sample algorithms in this chapter.
Search WWH ::
Custom Search