There are two significant computational time bottlenecks in the normalized cuts image segmentation with random bounds algorithm. This image segmentation technique creates a matrix containing weights relating each pixel to every other pixel in a local neighborhood. The weights are dependent on the negative absolute value of the complex trace (instantaneous amplitude) of the seismic. The matrix is then used to cut the image where the normalized sum of weights cut is minimized. This normalized cut is minimized by solving an eigenvector problem. The first bottleneck is the creation of the weight matrix as it can become quite large requiring a lot of computation time to build. The second bottleneck is the estimation of the eigenvector which requires numerous matrix-vector products involving the large sparse weight matrix.

In this paper, we present a parallel implementation of the normalized cuts image segmentation with random bounds technique for tracking 3D salt boundaries. We first review the algorithm. We then describe how we have distributed the calculation of the weight matrix on a parallel network. We then describe how we have parallelized the matrix-vector products of the eigenvector calculation. Lastly, we test this technique on a 3D field seismic cube.

4/5/2006