CS465 Fall 2006
Homework 3 Solution
-------------------

See the accompanying illustration for the correct positioning of
the 25 relevant output samples relative to the input grid, and
the values of the nearby input samples.

You'll want to read or print this file using a fixed-width font
(most web browsers will do this by default).

1. Box filter

For the box filter each pixel takes the value of the nearest
input pixel.  The middle 9 samples all map to the center input
samples, and the only neighboring samples that are 1 are up and
to the left and to the right.

result:
[1 0 0 0 0
 0 1 1 1 1
 0 1 1 1 1
 0 1 1 1 1
 0 0 0 0 0]


2. Tent filter

For this one you can compute it quickly by linear interpolation,
using a separable approach.  All the values depend only on the
center 9 input samples.  Interpolating by 7ths across the three
rows, we get

v             v             v
7 6 5 4 3 2 1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 7 7 7 7 7 7 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  ^     ^     ^     ^     ^

(all times 1/7).  The vs above mark where the input columns are
and the ^s below mark where the output columns are.  Looking at
only the 5 relevant columns we have

42 21  0  0  0
 7 28 49 49 49
 0  0  0  0  0

(all times 1/49).  The center row is already part of the answer;
the other four rows are obtained by going 3/7 and 6/7 of the way
from the center to the top and bottom rows.  Work is saved by the
fact that the right three columns are the same.

final result:
1/49 * [37 22  7  7  7
        22 25 28 28 28
         7 28 49 49 49
         4 16 28 28 28
         1  4  7  7  7]


3. Catmull-Rom filter

For the cubic there is a little more computation.  Again it's
handy, but not required, to do it separably.  You only need to
compute 4 nontrivial values of the filter:

f(0)    = 1
f(3/7)  = 226/343  ~= 0.65889
f(4/7)  = 159/343  ~= 0.46355
f(7/7)  = 0
f(10/7) = -24/343  ~= -0.06997
f(11/7) = -18/343  ~= -0.05247

We are computing a 3x3 grid.  Doing the resampling separably
again, first along rows then along columns, the first step is to
compute 3 values in each of the 5 input rows that contribute, at
the center and 3/7 each way from center.  The center column is
easy because the filter is interpolating; the other points have
one or two nonzero pixels contributing.  The table winds up as:

f(4/7)             |  0  | f(10/7) + f(-11/7)
f(4/7)             |  0  | f(10/7)
f(-3/7) + f(-10/7) |  1  | f(3/7) + f(-4/7)
0                  |  0  | f(-11/7)
f(4/7)             |  0  | f(10/7) + f(-11/7)

or, resolving to decimals,

0.46355 0 -0.12244
0.46355 0 -0.06997
0.58892 1  1.12244
0       0 -0.05247
0.46355 0 -0.12244

The second step applies the same resampling process along the
columns.  Again, the center row is easy because of the
interpolating filter; the others use the same weights as in the
first step.

top row:
f(11/7) *  0.46355 + f(4/7) *  0.46355 + f(-3/7) *  0.58892 + f(-10/7) *  0
f(11/7) *  0       + f(4/7) *  0       + f(-3/7) *  1       + f(-10/7) *  0
f(11/7) * -0.12244 + f(4/7) * -0.06997 + f(-3/7) *  1.12244 + f(-10/7) * -0.05247

bottom row:
f(10/7) *  0.46355 + f(3/7) *  0.58892 + f(-4/7) *  0       + f(-11/7) *  0.46355
f(10/7) *  0       + f(3/7) *  1       + f(-4/7) *  0       + f(-11/7) *  0
f(10/7) * -0.06997 + f(3/7) *  1.12244 + f(-4/7) * -0.05247 + f(-11/7) * -0.12244

final result:
[0.5786 0.6589 0.7172
 0.5889    1   1.1224
 0.3313 0.6589 0.7266]