Short Note
A modified Lloyd algorithm for characterizing vector fields

Robert G. Clapp

bob@sep.stanford.edu

In geophysics we often encounter problems where we must balance between cost and accuracy. A specific class of these problems involve characterizing a field or a vector field with few points, as accurately as possible. An example is in Fourier-based downward continuation based migration Claerbout (1995). These methods are only accurate in a v(z) medium, but have been extended to work in variable velocity Le Rousseau and de Hoop (1998); Ristow and Ruhl (1994); Stoffa et al. (1990) by using one, or several, reference velocities and then applying a correction based on the difference between the reference velocity and the true velocity at a given location. The larger the difference, the less accurate the wave propagation at high angles. As a result, choosing appropriate reference velocities can have a meaningful impact in image quality. In anisotropic wave equation migration, choosing appropriate reference velocities becomes even more problematic. Instead of a single value, velocity, at a given location, you now have multiple values (e.g. velocity, $\delta$, and $\epsilon$) at each point. The dimensionality of the space that must be spanned, and potentially the cost, is now cubed. Efficiently spanning this 3-D vector space becomes essential.

Electrical engineers and image processors face similar problems. In speech compression, it is important to accurately describe a signal in as few bytes as possible. In image processing, it is often important to reduce the number of colors in an image with as minimal loss in image quality as possible. These problems have led to the field known as quantization. One family of method often employed is based on Lloyd's method Lloyd (1982), an iterative technique that allows for variable rate quantization. In previous work Clapp (2003), I demonstrated a modified version of the 1-D Lloyd's method for velocity selection.

In this paper I extend the ideas in Clapp (2003) to the case of vector fields. I show how the method can automatically identify a series of locations that best characterize the vector field. In a companion paper Tang and Clapp (2006) the methodology is applied to anisotropic migration problem.