(1) |

The minimum of can be found by solving the generalized eigensystem:

(2) |

For application to seismic salt interfaces, we merely apply the algorithm to instantaneous amplitude. Several cost saving techniques are explored in Lomask et al. (2004).

By applying bounds we greatly reduce the size of the problem. These initial rough bounds can be found by first running the algorithm with small search neighborhoods and coarse sampling.

pic2
A cartoon of a masked salt boundary. It is long and thin with a discontinuous salt boundary snaking across it.
Figure 1 |

Unfortunately, the normalized cut segmentation method tends to partition elongated images along their shortest dimension. For instance, Figure is a cartoon of an elongated image with a salt boundary snaking across it. If the segmentation algorithm were to function as hoped, the minimum cut would be found along the salt boundary. However, because the salt boundary is discontinuous, it is likely that the minimum of the normalized cut in equation (1) will be found by cutting the image vertically where the image is thin.

To correct this problem, we exploit the fact that the upper boundary will necessarily be in Group *A* and the lower boundary will be in Group *B*. In other words, we want to force the segmentation algorithm to put the coarsely picked bounds in different groups.

We can enforce this constraint during the creation of the weight matrix (). Recall that this matrix contains weights relating each sample to every other sample along paths within a neighborhood. For any given sample, if its search neighborhood happens to cross a coarse boundary, it becomes weighted to every other sample near the boundary. This can be imagined by wrapping the image on a globe so that both the upper and lower bounds collapse to points at the poles (see Figure ). When estimating the weight matrix, every time a path crosses the north or south pole, it continues down the other side. In Cartesian space, this can be seen in the cartoon in Figure .

pic6
A cartoon illustrating global bounds. The image is stretched onto a sphere and the upper and lower boundaries of the mask collapse to points.
Figure 2 |

pic5
A cartoon illustrating idealized global bounds. When the search area for a node reaches outside the mask (as shown by the circle on the left), it becomes connected to all points along the boundary.
Figure 3 |

This ``Global'' bounds approach is completely impractical because it creates as many new weights as are saved by the size reduction of the problem.

A more practical approach that is still essentially the same concept is ``Random'' bounds. This is illustrated in Figure . Every time a path crosses a bound, it jumps a random distance along the boundary.

pic4
A cartoon illustrating the more practical random bounds. When the search area for a node reaches outside the mask (as shown by the circle on the left), it is connected to a single node a random distance along the boundary.
Figure 4 |

We have implemented and tested this random bounds method and found that it works well in our preliminary test cases.

5/3/2005