next up previous [pdf]

Next: Calculating edge weights Up: Approach Previous: Transformation of input data

Creating the graph

The original implementation of the pairwise region comparison algorithm from Felzenszwalb (2010) creates a graph with eight edges per node (pixel). This graph is constructed by looping over every pixel, and performing four calculations at each vertex. The left side of Figure 5 illustrates this process - if the ``active'' pixel is the one in red, edges are drawn or built to each of the blue pixels. Since every pixel in the image undergoes this process, a form of reciprocity allows for each pixel to be connected to its eight immediate neighbors via edges. While this process allows for the extreme efficiency of the algorithm, the unique and often irregular nature of seismic data does not lend itself well to segmentations using so few edges per vertex or pixel. Instead, a much larger ``stencil,'' shown on the right of Figure 5, has been implemented. Rather than building edges that extend only one pixel in each direction, this stencil creates five edges extending in each horizontal, vertical and diagonal direction from the center pixel. This scheme allows for many more comparisons (40) per pixel, and a far greater amount of information goes into the segmentation algorithm. Near the boundaries of the image, the stencil shrinks to the largest size allowable by the image dimensions. While this approach obviously decreases the efficiency of the algorithm, the increased accuracy seen in the final results appears to make it a worthwhile trade-off. Even with the sharply increased number of edges per node, this algorithm is still far less computationally intensive than the NCIS algorithm from Shi and Malik (2000).

stencils
Figure 5.
Stencils used for comparing pixel values and assigning edge weights for the graph. At left, the five-point stencil (8 edges per pixel) used in the original implementation from Felzenszwalb and Huttenlocher (2004); at right, a modified 21-point stencil (40 edges per pixel) used for the seismic images.
stencils
[pdf] [png]


next up previous [pdf]

Next: Calculating edge weights Up: Approach Previous: Transformation of input data

2010-05-19