Introduction

Normalized cuts image segmentation Shi and Malik (2000) is a pattern analysis technique developed to extract global impressions from images . Hale and Emanuel (2002, 2003) adapted this technique to painting 3D atomic meshes. Lomask et al. (2004); Lomask and Biondi (2003) have since applied this technique to tracking salt boundaries. In addition to sparse matrix storage and random sampling Shi and Malik (2000), other memory saving measures such as random bounds Lomask and Biondi (2005) have been implemented in order to reduce the size of problem thus reducing the exorbitant cost of applying this technique. However, to tackle realistic 3D data sets, the computational time of this algorithm still needs to be reduced significantly.

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.