0
# Connected Components 3D
1

2
A high-performance Python library for connected components analysis on 2D and 3D multilabel images. cc3d implements optimized algorithms for labeling connected regions in both discrete and continuous valued images, supporting multiple connectivity patterns and processing images with hundreds to thousands of distinct labels simultaneously.
3

4
## Package Information
5

6
- **Package Name**: connected-components-3d
7
- **Language**: Python (with C++ extensions)
8
- **Installation**: `pip install connected-components-3d`
9

10
## Core Imports
11

12
```python
13
import cc3d
14
```
15

16
Alternative import for direct access:
17

18
```python
19
from cc3d import connected_components, statistics, dust, largest_k
20
```
21

22
## Basic Usage
23

24
```python
25
import cc3d
26
import numpy as np
27

28
# Create a sample 3D multilabel image
29
labels_in = np.ones((100, 100, 100), dtype=np.int32)
30
labels_in[:50, :50, :50] = 2  # Different region
31

32
# Perform connected components labeling
33
labels_out = cc3d.connected_components(labels_in)  # 26-connected by default
34

35
# Get statistics about the components
36
stats = cc3d.statistics(labels_out)
37
print(f"Found {len(stats['voxel_counts'])-1} components")
38
print(f"Component sizes: {stats['voxel_counts'][1:]}")  # Skip background
39

40
# Extract individual components efficiently
41
for label, image in cc3d.each(labels_out, binary=False, in_place=True):
42
    print(f"Processing component {label} with {np.sum(image > 0)} voxels")
43

44
# Remove small components ("dust removal")
45
cleaned = cc3d.dust(labels_in, threshold=1000, connectivity=26)
46

47
# Keep only the 5 largest components
48
largest = cc3d.largest_k(labels_in, k=5, connectivity=26)
49
```
50

51
## Architecture
52

53
cc3d uses a sophisticated four-pass algorithm built on these key components:
54

55
- **SAUF Method**: Scan plus Array-based Union-Find with decision trees for optimized connectivity analysis
56
- **Phantom Labeling**: Advanced technique that reduces expensive unification calls during processing
57
- **Union-Find with Path Compression**: Efficient disjoint set data structure for managing label equivalencies
58
- **Memory Optimization**: Preprocessing passes estimate memory requirements and foreground locations
59

60
The library processes all labels simultaneously rather than requiring separate binary masks for each label, providing significant performance improvements for multilabel datasets common in biomedical imaging, computer vision, and scientific computing.
61

62
## Capabilities
63

64
### Core Connected Components
65

66
Primary connected components labeling functionality with support for multiple connectivity patterns, continuous value processing, and various output formats including memory-mapped files.
67

68
```python { .api }
69
def connected_components(
70
    data: NDArray[Any],
71
    max_labels: int = -1,
72
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
73
    return_N: bool = False,
74
    delta: float = 0,
75
    out_dtype: DTypeLike = None,
76
    out_file: Union[str, BinaryIO, None] = None,
77
    periodic_boundary: bool = False,
78
    binary_image: bool = False,
79
) -> Union[NDArray[Union[np.uint16, np.uint32, np.uint64]], tuple[NDArray[Union[np.uint16, np.uint32, np.uint64]], int]]
80

81
def connected_components_stack(
82
    stacked_images: typing.Iterable[NDArray[typing.Any]], 
83
    connectivity: Literal[6,26] = 26,
84
    return_N: bool = False,
85
    out_dtype: DTypeLike = None,
86
    binary_image: bool = False,
87
) -> Union[CrackleArray, tuple[CrackleArray, int]]
88
```
89

90
[Core Connected Components](./core-ccl.md)
91

92
### Statistics and Analysis
93

94
Compute comprehensive statistics about connected components including voxel counts, bounding boxes, centroids, and component extraction utilities.
95

96
```python { .api }
97
def statistics(
98
    out_labels: NDArray[Any],
99
    no_slice_conversion: bool = False,
100
) -> Union[StatisticsDict, StatisticsSlicesDict]
101

102
def each(
103
    labels: NDArray[UnsignedIntegerT],
104
    binary: bool = False,
105
    in_place: bool = False,
106
) -> Iterator[tuple[int, NDArray[UnsignedIntegerT]]]
107
```
108

109
[Statistics and Analysis](./statistics.md)
110

111
### Component Filtering
112

113
Filter and manipulate connected components by size, including dust removal and extraction of largest components with efficient memory management.
114

115
```python { .api }
116
def dust(
117
    img: NDArray[typing.Any], 
118
    threshold: Union[int,float,tuple[int,int],tuple[float,float],list[int],list[float]], 
119
    connectivity: Literal[4,6,8,18,26] = 26,
120
    in_place: bool = False,
121
    binary_image: bool = False,
122
    precomputed_ccl: bool = False,
123
    invert: bool = False,
124
    return_N: bool = False,
125
) -> Union[NDArray[typing.Any], tuple[NDArray[typing.Any], int]]
126

127
def largest_k(
128
    img: NDArray[typing.Any],
129
    k: int,
130
    connectivity: Literal[4,6,8,18,26] = 26,
131
    delta: Union[int,float] = 0,
132
    return_N: bool = False,
133
    binary_image: bool = False,
134
    precomputed_ccl: bool = False,
135
) -> Union[NDArray[Union[np.bool_,np.uint16,np.uint32,np.uint64]], tuple[NDArray[Union[np.bool_,np.uint16,np.uint32,np.uint64]], int]]
136
```
137

138
[Component Filtering](./filtering.md)
139

140
### Graph Analysis
141

142
Extract connectivity graphs between regions and voxel-level connectivity patterns for advanced analysis and network-based computations.
143

144
```python { .api }
145
def contacts(
146
    labels: NDArray[Any],
147
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
148
    surface_area: bool = True,
149
    anisotropy: tuple[Union[int, float], Union[int, float], Union[int, float]] = (1, 1, 1),
150
) -> dict[tuple[int, int], Union[int, float]]
151

152
def region_graph(
153
    labels: NDArray[np.integer],
154
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
155
) -> set[tuple[int, int]]
156

157
def voxel_connectivity_graph(
158
    data: NDArray[IntegerT],
159
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
160
) -> NDArray[IntegerT]
161

162
def color_connectivity_graph(
163
    vcg: NDArray[VcgT],
164
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
165
    return_N: bool = False,
166
) -> Union[NDArray[VcgT], tuple[NDArray[VcgT], int]]
167
```
168

169
[Graph Analysis](./graphs.md)
170

171
## Types
172

173
```python { .api }
174
class DimensionError(Exception):
175
    """The array has the wrong number of dimensions."""
176

177
class DisjointSet:
178
    """Union-Find data structure for managing disjoint sets."""
179
    def __init__(self): ...
180
    def makeset(self, x): ...
181
    def find(self, x): ...
182
    def union(self, x, y): ...
183

184
class StatisticsDict(typing.TypedDict):
185
    voxel_counts: NDArray[np.uint32]
186
    bounding_boxes: list[tuple[slice, slice, slice]]
187
    centroids: NDArray[np.float64]
188

189
class StatisticsSlicesDict(typing.TypedDict):
190
    voxel_counts: NDArray[np.uint32]
191
    bounding_boxes: NDArray[np.uint16]
192
    centroids: NDArray[np.float64]
193

194
# Type variables for generic functions
195
VcgT = typing.TypeVar("VcgT", np.uint8, np.uint32)
196
IntegerT = typing.TypeVar("IntegerT", bound=np.integer)
197
UnsignedIntegerT = typing.TypeVar("UnsignedIntegerT", bound=np.unsignedinteger)
198

199
# External types (requires optional dependencies)
200
from crackle import CrackleArray  # Available with 'pip install connected-components-3d[stack]'
201
```