Interpolation of Multidimensional Functions - Control of Color Imaging Systems: Analysis and Design - page 279

TABLE 6.12
One-Dimensional DO Algorithm
Point

J ¼1 J ¼2 J ¼ J ¼N 2

x 1 [j 1 , E 1 ] [k 1 , l 1 , EE 1 ] [m 1 , n 1 ,...,E Total ]

x 2 [j 2 , E 2 ] [k 2 , l 2 , EE 2 ] —

x 3 [j 3 , E 3 ] [k 3 , l 1 , EE 3 ] —

. . . . .

x N 4 [j N 4 , E N 4 ] [k N 4 , l N 4 , EE N 4 ]

x N 3 [j N 3 , E N 3 ] [N 2, N 1, 0] — —

x N 2 [N 1, 0] — — —

x N 1 — — — —

x N — — — —

k ¼ arg min m E im þ E m ½ , m i þ 1

( 6 : 70 )

EE i ¼ E ik i þ E k i , l i ¼ j k i

where
E m is the MMSE corresponding to j ¼ 1

E im is the MSE between the original function and the linearly interpolated
function using grid points [xi, i , x m ] over the interval of [xi, i ,...,x m ]

Then the optimum two-point grid including boundary points will be [x 1 x k x l x N ], as
shown in column 2 of Table 6.12. We call this the 1-D two-stage grid allocation
algorithm. Using the same approach, we can now build an n-stage optimization
process for the 1-D case with N optimal grid points [x 1 x m 1 x n 1 x N 1 ].

6.5.3.2 Two-Dimensional DO Algorithm

Consider the 2-D discrete function f(X), where X ¼ [x, y] takes M M grid points

uniformly spaced in the x - y plane, as shown in Figure 6.17. We would like to choose
N N grid points out of M M available data points such that the mean-square
interpolation error between the original function and the approximation obtained by
upsampling the N N LUT is minimized. Since the boundary points should
be included for interpolation, degrees of freedom are less than N N. For example,
if A is an internal optimum point, then the four boundary points B, C, D, and E
(as shown in Figure 6.17) should also be included in this set. The 2-D DO algorithm
is very similar to the 1-D case. In the single-stage 2-D algorithm, assume we start
with point [xi, i , y j ] and try to optimally select one internal grid point in the set
extending from this point to the boundaries of the function f(X). The solution
is obtained by direct optimal search and is denoted by the two indices ki i and l j

with its associated four boundary points and MMSE J 1 (i, j) ¼ E i, j . This process is

repeated for each point in the set associated with the domain of the underlying
function. With three indices given by

½ k i l j E i,j i, j ¼ 1, 2, ... , M ( 6 : 71 )