CONNECT - Find 3D Connected Components

- Intro
- Papers
- Prior Art
- Implementation Details

Intro

Connect is a very efficient implementation on a laptop computer of the union-find algorithm for finding connected components when the input is more than a 1000x1000x1000 3D box of binary voxels. Each voxel may be connected either to its 6 orthogonal neighbors, or to all 26 neighbors. Component properties, such as area, and volume are also computed. This implementation is fast enough to permit experimental studies of random connectivity.

Determining the connected components of a 2D or 3D array of bits is a required operation in domains such as the following:

  1. Investigating the distribution of cracks in concrete as it is stressed to failure (which is what motivated this research),
  2. Extraction of connected components in image processing, and
  3. Determination of porosity of an underground fluid reservoir.

Connect is very space- and time-efficient. The largest test case had a universe of size 1024x1088x1088, which has 1,212,153,856 voxels, about 1/2 empty and found the 4,539,562 components. The implementation environment was a 2GHz IBM T43p laptop with SuSE linux and gcc 4.1.0. The virtual memory used, which is a function of the space preallocated for runs and components, which was sized for this example, was only 340MB. The program's elapsed time was equal to its CPU time, which was 51 CPU seconds. Smaller examples run proportionately faster, in perhaps 0.1 seconds for a 100x100x100 universe. Very complicated cases would run more slowly.

Papers

  1. Connected Components on 1000x1000x1000 Datasets. W. Randolph Franklin and E. Landis (extended abstract). In 16th Fall Workshop in Computational Geometry, Smith College, Northampton, MA, 10-11 Nov 2006. (BIB)
    two page abstract and Talk.
  2. . . (renamed to capri01). (BIB)
  3. 3D Analysis of Tomographic Images. Edwin Nagy, Tong Zhang, Wm Randolph Franklin, George Nagy and E Landis. In 16th {ASCE} Engineering Mechanics Conference, U Washington, Seattle, 16-18 July 2003. (electronic proceedings). (BIB)
  4. Cracking, damage and fracture in four dimensions. E. N. Landis, T. Zhang, E. N. Nagy, G. Nagy and W. R. Franklin. Materials and Structures, online date: 13 July 2006. (URL) (BIB)
    http://www.springerlink.com/content/ftgmk3m461716833/
    Abstract: Concrete and cracking are nearly synonymous despite our best efforts and intentions. Relationships between cracking and the stress states that lead to cracking can be instructive. In an effort to better understand these relationships, X-ray microtomography was used to make high-resolution three-dimensional digital images of small concrete specimens under load. Using 3D image analysis, quantitative measurements of internal crack growth were made that include effects of crack tortuosity, branching and microcracking. Successive images at different levels of cracking and damage provide us with a detailed picture of internal crack progression. When coupled with load-deformation response, bulk material properties such as fracture toughness or damage variables can be quantitatively linked with cracking. Measurements to date have shown distinct fracture regimes linked to crack formation and propagation. In addition, the crack measurements offer a way to provide a physical basis for a scalar damage variable.
    Keywords: Concrete - Fracture - Damage - Tomography

Prior Art

This is a very incomplete list, which will be enlarged at some time. The only reference actually used was a description of the union-find problem in, probably, Aho, Hopcroft and Ullmann.

Searching on 3d connected components produces several refs including implementations, altho apparently always on smaller datasets.

Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study. David A. Bader and Joseph JaJa. Journal of Parallel and Distributed Computing, 1994. (BIB)

This implements connected component algorithms on parallel machines like the CM-5 and SP-2 for 2-D 1024x1024 images. There are many references.

Implementation Details

  1. Implementation
  2. Test Results (sizes are approx)
    1. 1024 Cubed (approx) - our largest case
    2. 512 Cubed - including distribution of component volumes, and volume-area relationship of components, which suggests their fractal dimension
    3. Random - each voxel is independently 0 or 1, with probability p. How does the number of components vary with p, with either 6 or 26 connectivity?
    4. 2D


<< Fundamentals | Research Page List | Connected Components Implementation >>

nn