Image Processing Reference
In-Depth Information
6.3 NONUNIFORMLY SPACED LOOKUP TABLES
There are several algorithms available to interpolate nonuniformly spaced LUTs.
Among them are the Shepard interpolation algorithm, the moving-matrix technique,
and the dynamic least-square interpolation algorithm. None of these techniques
provide accurate estimations of the values of the underlying functions at grid points
that are not part of the LUT. However, they are the only techniques known to us that
can be used for the interpolation of nonuniformly spaced LUTs that are not struc-
tured. These techniques are discussed in the following sections.
6.3.1 S
HEPARD
I
NTERPOLATION
The Shepard interpolation is an approach to interpolate multidimensional irregularly
spaced data [4]. The Shepard algorithm is based on a section of a local function to
approximate the underlying function at a given point using weighted regression. The
function selected is continuously differentiable. To discuss the algorithm, consider
a LUT that maps M-dimensional vector y to M-dimensional vector z through a
nonlinear transformation, where
P
x
!
y,
y
¼
P
(
z
)
(
6
:
21
)
Assume that a set of N irregularly spaced data points are available. Let the set be
given by
S
¼ (
x
1
, y
1
)(
x
2
, y
2
) (
x
N
, y
N
)
f
g
(
6
:
22
)
where x
i
2
R
M
and y
i
2
R
M
. Let x be a point in the input space with the corresponding
point y in the output space. Then the interpolated value at x is given by
8
<
P
i
¼
1
y
i
d
m
P
i
¼
1
d
m
if
d
i
for all
i
=0
i
y
¼
(
6
:
23
)
i
:
y
j
if
d
j
=0
for some
j
where d
i
is the distance (based on L
p
norm) between vectors x and x
i
, that is,
d
i
¼k
x
x
i
k
p
(
6
:
24
)
Note that if x is approaching a data point, then
y
!
y
¼
P(x), indicating that the
interpolation formula given in Equation 6.23 is a continuous function, as desired.
There are two parameters, p and
, that can be selected by the user. It can be shown
(see Problem 6.6) that if the parameter
m
m
is chosen to be greater than 1, the
interpolated function will be differentiable.
Search WWH ::
Custom Search