A new method for more efficient seismic image segmentation |

Thus, a more efficient global segmentation scheme that can include the entire image in the computational domain would be a very useful tool for interpretation of seismic images. One candidate for such a scheme is the algorithm from Felzenszwalb and Huttenlocher (2004), who write:

``Our algorithm is unique, in that it is both highly efficient and yet captures non-local properties of images.''These two features are crucial for the task of seismic image segmentation. The algorithm is designed to run in time, where is the number of pixels in the graph; in contrast, other methods such as NCIS require closer to time to run. This represents a significant cost savings, especially for very large 3D seismic datasets that are becoming increasingly common.

MST
Modified from Zahn (1971). A graph with weighted edges (a); a spanning tree of that graph (b); and the minimum spanning tree of the graph (c).
Figure 2. | |
---|---|

The algorithm proposed by Felzenszwalb and Huttenlocher (2004) relies heavily on the concept of the ``Minimum Spanning Tree'' [see Zahn (1971)]. A graph's edges may be weighted using a measure of dissimilarity between vertex pairs; a connected graph is defined as one in which all such edges are assigned a weight value. If a spanning tree is a connected graph which connects all vertices of the graph without forming a circuit, the minimum spanning tree (MST) of a graph is the spanning tree with the minimum sum of edge weights (see Figure 2). In Zahn (1971), partitioning of a graph was achieved simply by cutting through edges with large weights. However, this approach is inadequate for images with coherent regions that are nonetheless highly heterogeneous (for example, consider the heterogeneous nature of the intensity values within the salt bodies in the examples above). However, the MST concept allows Felzenszwalb and Huttenlocher (2004) to develop what they term a ``pairwise region comparison" predicate. They define the *internal difference* of a region
in the graph to be the largest edge weight of the MST of that region:

(1) |

where is a graph edge and is the edge's weight, defined according to some simple algorithm. When comparing two regions (such as and ), they define the

(2) |

where is a thresholding function that in a sense determines the scale at which the segmentation problem is approached, and thus indirectly the size of the regions in the final segmentation. Finally, they define the

(3) |

where and are vertices (or pixels) in the two different regions. When determining whether these two regions should be considered separate segments of the graph, or merged into a single region, they simply compare the values of and . If is greater, the ``pairwise comparison predicate'' is determined to be true, and the two regions are separated. While this is a relatively simple procedure, it is designed to allow highly heterogeneous regions to be segmented as a single component of an image. Additionally, Felzenszwalb and Huttenlocher (2004) note that their algorithm produces segmentations that are ``neither too coarse nor too fine," referring to the global capabilities of the segmentation process.

In the next section, I will provide more detail about the algorithm itself, and explain the modifications necessary to make it suitable for use with seismic images.

A new method for more efficient seismic image segmentation |

2010-05-19