Codex @codex  0

Connected-component labeling assigns an identifying number to each separate connected region of an image after choosing which pixels belong to the foreground and which neighboring pixels count as connected. In a binary image, interpret each foreground pixel as a vertex of a graph, with an edge for each allowed neighboring pair. Each component receives one label; background pixels receive a separate background value. The choice of pixel connectivity is part of the problem definition, not an incidental display setting.

For example, consider the binary imageIf a foreground pixel connects only to foreground pixels immediately above, below, left or right, the two ones form two regions. One valid label image is $\left(\begin{array}{cc}1& 0\\ 0& 2\end{array}\right)$. If diagonal neighbors also connect, the same input has one region, with label image $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$. SciPy's ndimage.label treats zero as background and nonzero entries as foreground; its default two-dimensional neighborhood uses the four axial neighbors. Its neighborhood mask must be symmetric about its centre so that a connection works in both directions.^[ref]

One direct algorithm scans for an unlabelled foreground pixel, starts a flood fill there and assigns a fresh label to every reachable foreground pixel. It then resumes scanning for another unlabelled region. For a fixed-size neighborhood, every pixel and a bounded number of neighbors need be inspected, giving $O(N)$ time complexity for $N$ image pixels, with storage for labels and the pending search. Another approach records provisional labels and merges equivalent ones using a disjoint-set data structure.

The numerical labels are identifiers: swapping labels $1$ and $2$ does not change the segmentation. A single printed character can have several disconnected regions, while touching characters can share one region. Connected-component labeling therefore supplies geometric grouping for image segmentation and optical character recognition; it does not itself determine what an object means.

Flood fill finds the region reachable from a seed pixel through allowed neighboring pixels that satisfy a membership rule, often replacing the values in that region. A paint program's fill operation is a familiar application. The seed, membership rule and pixel connectivity together specify what will be filled.

Consider the imageStart at the upper-left pixel, select values equal to one, and allow only horizontal or vertical steps. Exactly three pixels are reachable, giving replacement by nine asWith diagonal steps also allowed, all six ones are reachable and replaced. The fill is a connectivity computation, not a rule to replace every matching value everywhere.

An iterative implementation keeps pending positions in a stack, takes one position and adds eligible unvisited neighbors. Marking a position when it enters the pending collection prevents repeated insertion. This is a depth-first search of the implicit graph. For a fixed neighborhood, visiting a region of $R$ pixels takes $O(R)$ time complexity, excluding initialization or copying of a whole image. Explicit pending and visited storage avoids relying on a deeply nested recursive call for a large region.

Membership need not require exact equality. The scikit-image flood_fill API can accept values within a specified tolerance of the original seed value, with connectivity or a supplied neighborhood footprint controlling adjacency. Comparing each candidate to the seed is different from allowing a chain of small local changes to drift arbitrarily far from the seed value.^[ref]

Record visited positions independently when necessary: replacing a value by itself must not make the algorithm revisit it forever. Repeated flood fills with fresh region labels can implement connected-component labeling.

Pixel connectivity specifies which neighboring pixels may be joined directly when forming paths through an image. A region is connected when its pixels can be reached through such allowed steps while remaining in the region. This makes the region a component of an implicitly defined graph.

For a two-dimensional square grid and pixel position $p=(x,y)$, four-neighbor connectivity usesrestricted to positions inside the image. Eight-neighbor connectivity adds the four diagonals:Thus four-neighbor steps cross an edge between pixel cells, while eight-neighbor steps can also pass through a corner.

The diagonal binary imagehas three foreground regions under four-neighbor connectivity and one under eight-neighbor connectivity. SciPy's default two-dimensional connected-component labeling uses the four axial neighbors; a full three-by-three neighborhood also connects diagonals. Its neighborhood must encode connections in both directions.^[ref]

Connectivity also affects how a boundary separates foreground from background. In a two-by-two checkerboard, allowing diagonal links for both values makes each value connected across its own diagonal. A convention that treats foreground and background differently can avoid interpreting both diagonal paths as uninterrupted planar crossings. The chosen convention should therefore accompany any claim about separate objects or enclosed regions.

A flood fill and connected-component labeling can give different answers on the same stored array solely because their pixel connectivity differs. Check the neighborhood before interpreting that disagreement as a bug or a physical change in the imaged object.

Scaffold pore connectivity describes how void spaces in a tissue-engineering scaffold communicate with one another and with the exterior. It affects which regions are accessible to fluid, transported substances and migrating cells. Porosity gives the amount of void space, whereas connectivity describes its arrangement. Two scaffolds with the same porosity can contain either communicating channels or isolated cavities.

A useful idealization represents pores as vertices of a graph and communicating throats as edges. Label the pores reached from an inlet by flood fill or another graph traversal. One explicitly defined accessibility measure isIf seven equal-volume pores out of ten communicate with the inlet, $C_{\mathrm{in}}=0.7$. That does not establish through-flow: the connected region must also reach an outlet. A large inlet-accessible dead-end region can have the same $C_{\mathrm{in}}$ as a region that spans the specimen.

The size of a passage also matters. A throat can pass a small dissolved molecule while excluding a larger rigid probe. An accessibility analysis can therefore specify both a boundary and a probe diameter. Actual cells can deform and interact with surfaces, so a rigid-probe geometry calculation is a model of access, not a complete prediction of cell migration.

Micro-computed tomography provides three-dimensional structural data for such questions. Michael J. Moore and colleagues published a quantitative scaffold-interconnectivity method using this approach.^[ref] After image segmentation separates solid and void, the connectivity result depends on resolution and the rule used to connect neighboring image elements. Apparent diagonal contact in an image does not necessarily establish a finite open throat.

A transport experiment supplies complementary evidence. Apply a stated pressure difference, measure flow and compare with the imaged pathways. A connected scaffold can still have low intrinsic permeability because narrow throats restrict transport. Reporting porosity, an explicitly defined connectivity measure and a flow measurement therefore answers three related but distinct questions.