**1**- Find for every point the closest codebook entry. These points form a cell.
**2**- Find the average of all points associated with a given codebook entry. The average becomes the new codebook entry.
**3**- Remove codebook entries that have no, or few, points associated with them.

ref
In step 1, the data is dividing into cells. In step 2, the average
of each cell is calculated. In the third step new cell boundaries
are calculated between the centroids. If a cell contains no
points, the cell is removed.
Figure 1 |

Lloyd's method is attempting to solve a non-linear problem by an iterative scheme, so local minima can be problematic. To avoid prejudicing the solution the initial model is often a random set of vectors. To solve the problem, several methods have been developed Linde et al. (1980). These methods often rely on replacing an empty cell by splitting regions with high variance. Clapp (2002) followed a modified version of this approach for the velocity selection problem. Figure shows a velocity model, the selected reference velocities, and the percentage error between the two using the methodology described in Clapp (2002). The methodology proved effective in selecting appropriate reference velocities with two noticeable drawbacks. At each depth step a new non-linear estimate is performed. At some depths steps the solution gets stuck in local-minima. Note the striping in the right panel of Figure . In addition, the methodology will sometimes pick too few reference velocities to adequately describe a layer by getting stuck in a local minima. Both of these problems can be minimized by using as a starting solution the reference velocities at the previous depth step and adding a random component to the cell splitting. Figure shows the selected reference velocities and the percentage error in the selected reference velocities.

Figure 2

Figure 3

4/5/2006