Browse Prior Art Database

Efficient Lattices for Sampling

IP.com Disclosure Number: IPCOM000118703D
Original Publication Date: 1997-May-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 120K

Publishing Venue

IBM

Related People

Johnson, A: AUTHOR

Abstract

A number of computer applications requires a sample point (in n-dimensions) to be selected from a fixed list which is closest to an actual point. The problem is to choose a way of allocating the points in the fixed list such that the maximum (or root-mean-square or other such measure) distance from any point to the closest sample point is minimized.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 43% of the total text.

Efficient Lattices for Sampling

      A number of computer applications requires a sample point (in
n-dimensions) to be selected from a fixed list which is closest to an
actual point.  The problem is to choose a way of allocating the
points in the fixed list such that the maximum (or root-mean-square
or other such measure) distance from any point to the closest sample
point is minimized.

      One example is the allocation of Red, Green, Blue (RGB) color
values in a palette of say 256 colors to represent any arbitrary RGB
value, which could have say a value out of (2**8)**3 possible values,
such that the error on choosing a color from the palette to represent
the arbitrary color is minimized.

      Other examples occur in modelling applications where sampling
points in three dimensional spaces are chosen to represent conditions
everywhere or where differential equations are modelled in three
dimensional space by modelling conditions at fixed sample points.

      In the case of a color palette, where the red, green, and blue
values correspond to x,y,z coordinates in three dimensional space,
the conventional solution is to space the colors evenly in RGB space
in a rectangular lattice.  This approach, while producing reasonable
results with large color palettes, can produce undesirable effects
with limited (typically 256) color palettes.

      The approach described allocates the colors in a body-centered
cubic arrangement.  This minimizes the maximum distance from any
point to one of the sampling points, compared with a rectangular
lattice.

Conventionally, for a rectangular lattice, the color points are
allocated as follows:
  for (b = 0; b < 6; b += 1) {
    for (r = 0; r < 6; r += 1) {
      for (g = 0; g < 6; g += 1) {
        allocatecolor(r*255/(6-1),g*255/(6-1),b*255/(6-1));
      }
    }
  }

This allocates 6*6*6=216 colors, in a rectangular lattice.

      Instead of a 6*6*6 lattice, the improved approach can use an
interspersed 5*5*5 and 4*4*4 lattice, with 125+64=189 points, to
ensure that any point in the color space will be closer to a sample
point in the lattice:
  for (b = 0; b <= (5-1)*2; b += 2) {
    for (r = 0; r <= (5-1)*2; r += 2) {
      for (g = 0; g <= (5-1)*2; g += 2) {
   allocatecolor(r*255/((5-1)*2),g*255/((5-1)*2),b*255/((5-1)*2));
      }
    }
  }
  for (b = 1; b <= (5-1)*2; b += 2) {
    for (r = 1; r <= (5-1)*2; r += 2) {
      for (g = 1; g <= (5-1)*2; g += 2) {
  allocatecolor(r*255/((5-1)*2),g*255/((5-1)*2),b*255/((5-1)*2));
      }
    }
  }

The worst-case distance can be calculated as follows:
  Rectangular grid.
  Color (25,25,25) is sqr((25-0)**2+(25-0)**2+(25-0)**2))
   =sqr(1825)=42.7 from the nearest point (0,0,0)

Body centered cubic lattice.
  Color (32,16,0) is sqr((32-32)**2+(16-32)**2+(32-0)**2))
   =sqr(1280)=35.7 from nearest point (32,32,32), (0,0,0), (64,0,0)

This is a significant improvement ov...