(back to Connected Components main page)

Here is a smaller test case, also from Eric Landis. It has 512x544x544 = 151,519,232 voxels, 76,073,721 of them empty. 15 seconds CPU on a 1600 MHz Pentium are required to find all connected components, with their volumes and surface areas. There are 534,723 6-connected, or 223,339 26-connected components.

6-Connectivity

Our goal was to show connect's execution time, not the file I/O time. Therefore, before the following runs, I read the input file to force it into the disk cache. Also, the output was to /dev/null.

***** CONNECT starting at Mon Sep 20 13:40:47 1999
*****
nx=512, ny=544, nz=5440
Cumulative CPU time thru initialization= 0.02
Cumulative CPU time thru processing planes= 36.49
Cumulative CPU time thru check_tree_depth= 36.93
Cumulative CPU time thru assemble_components= 37.8
Component #0 with volume 74838470 is too large to write.
Cumulative CPU time thru sort_components= 39.33
# volume=1 components not written: 371612
Cumulative CPU time thru for write_components= 43.96
Universe has 512*544*544=151519232 voxels.
Type of connectivity: 6
# empty voxels= 76073721, fraction= 0.502073
# runs= 2615676, average size=29.0838
# components= 534723, average # runs/component=4.89165
# times a pair of possibly adjacent runs tested, but they didn't
overlap= 5833520
# times a pair of adjacent runs processed= 3976450
# times two adjacent runs were already in the same component= 1895497
# pointers followed when processing adjacent runs= 22585947
Average # pointers followed per run= 8.63484
# times find_root_of_run called= 7952900, average # pointers followed per call= 1.42007
# times update_root called= 7952900, average # pointers followed per call= 1.4199
# times find_roots finds a run not pointing directly to its root=0
# bytes used by one run= 12, total run storage= 32400000
# bytes used by one component= 16, total component storage= 12000000
rows1 storage= 1188104
Total storage used by large arrays= 45588104
Cumulative CPU time thru end= 43.97

26-Connectivity

The input was rotated twice about the grand diagonal.

***** CONNECT starting at Mon Sep 20 13:46:00 1999
*****
nx=512, ny=544, nz=54426
Cumulative CPU time thru initialization= 0.02
Cumulative CPU time thru processing planes= 42.2
Cumulative CPU time thru check_tree_depth= 42.71
Cumulative CPU time thru assemble_components= 43.28
Component #0 with volume 75408704 is too large to write.
Cumulative CPU time thru sort_components= 44.11
# volume=1 components not written: 144379
Cumulative CPU time thru for write_components= 46.98
Universe has 512*544*544=151519232 voxels.
Type of connectivity: 26
# empty voxels= 76073721, fraction= 0.502073
# runs= 2615676, average size=29.0838
# components= 223339, average # runs/component=11.7117
# times a pair of possibly adjacent runs tested, but they didn't
overlap= 10315294
# times a pair of adjacent runs processed= 9218060
# times two adjacent runs were already in the same component= 6825723
# pointers followed when processing adjacent runs= 50989708
Average # pointers followed per run= 19.4939
# times find_root_of_run called= 18436120, average # pointers followed per call= 1.3829
# times update_root called= 18436120, average # pointers followed per call= 1.38285
# times find_roots finds a run not pointing directly to its root=0
# bytes used by one run= 12, total run storage= 32400000
# bytes used by one component= 16, total component storage= 12000000
rows1 storage= 1188104
Total storage used by large arrays= 45588104
Cumulative CPU time thru end= 46.98

Volume - Area Relationship of the Components

6-Connectivity

http://wrfranklin.org/wiki/Main/ConnectedComponents/vol-area-stats-c6.txt classifies all the 6-connected components in p512, by volume and surface area, sorted by volume. All the components with the same volume and area are grouped together here, even tho they may have different geometries. Each line of the file describes one group of components thus.

Number of components in this group.
Their common volume.
Their common area.

E.g., the line

      2	54 206

means that there are 2 components each of whose volumes is 54 and whose areas is 206.

Here is a scatterplot of the components' volumes and areas. There is one dot for each (vol,area), regardless of how many components it represents. The lines have slopes 2/3 and 1, and are drawn to be close to the points. Their use is to estimate the fractal dimension of the components.

Referring to the fractal dimension of objects with a finite number of voxels is sloppy; we assume that the components are a sample from an infinite sequence of ever-larger objects of identical dimension, which we are estimating.

In any case, for objects of dimension 3, area grows as volume^2/3, which is not happening here.

26-Connectivity

http://wrfranklin.org/wiki/Main/ConnectedComponents/vol-area-stats-c26.txt does the same for the 26-connected components.

For a given volume, 26-connected components tend to have a larger area than 6-connected components of that volume. This is reasonable.

Volume Distribution

This graph shows histograms of the number of components with each volume for both connectivities. Having a log-log scale, it excludes volumes with a zero frequency.

Note that the histogram lines are quite straight, for frequencies above 2. Therefore I also drew experimentally determined lines to fit the observes slopes. For 6-connectivity, the number of component with volume V is proportional to about V^'-2.5^'. For 26-connectivity, it's about V^'-2.4^'.