1 Definition and Intuition

1.1 Grid and cell model

In grid-based image analysis and lattice graph modeling, a 2D domain is represented as a set of cells (often pixels). Each cell occupies one location in a regular square lattice and is treated as an individual element whose neighbors are determined purely by their geometric positions on the grid. “Adjacency” is therefore a rule that assigns which pairs of cells can be considered directly connected.

1.2 8-neighborhood adjacency rule

Under the 8-neighborhood rule, a cell is adjacent to all cells in the 3×3 block centered on it, excluding the cell itself. Concretely, the neighbors include:

  • The four orthogonal neighbors (up, down, left, right), and
  • The four diagonal neighbors (up-left, up-right, down-left, down-right).

This yields up to eight possible adjacent positions for interior cells; fewer exist near boundaries.

1.3 Relationship to 4-neighborhood connectivity

4-neighborhood connectivity is defined using only orthogonal adjacency. The 8-neighborhood rule can be seen as a superset of 4-neighborhood adjacency that additionally treats diagonal-touching cells as directly connected. As a result, component structures, connectivity measurements, and path properties can differ substantially between the two choices.

1.4 When diagonal connectivity is appropriate

Diagonal adjacency is often appropriate when the underlying phenomenon being modeled is expected to allow “corner connections” to be meaningful. Examples include certain forms of blob detection where objects meet at corners, or topology-sensitive tasks where diagonal continuity represents a real connected trace. In practice, the choice should reflect how a downstream interpretation treats diagonal contact: whether corner contact signifies the same region or merely a near miss.

2 Graph Formulation

2.1 Constructing the adjacency graph

To express 8-neighborhood connectivity in graph terms, each cell becomes a node, and edges are added between nodes whose corresponding cells are adjacent under the 8-neighborhood rule. Typically, adjacency is added regardless of pixel intensity and then filtered by a condition (e.g., both cells belong to a foreground mask). Alternatively, edges can be restricted directly during construction to only connect eligible cells.

2.2 Node and edge interpretation

In this formulation:

  • A node represents a specific grid cell (pixel).
  • An edge represents the possibility of moving between two adjacent cells in one step.

If the model is used for traversal or labeling, an “active” node set (such as foreground pixels) determines which nodes and edges participate in the analysis.

2.3 Connectivity vs. adjacency

Adjacency describes the allowed local links between cells, whereas connectivity describes the existence of paths formed by repeated adjacency steps. Two nodes can be adjacent without being part of the same connected region if intermediate eligibility constraints prevent path formation. Conversely, nodes might not be adjacent but can still be connected via a chain of adjacent eligible cells.

2.4 Properties of the resulting graph

The 8-neighborhood adjacency graph on a 2D grid is planar only in a limited sense, since diagonal edges create additional crossings if drawn geometrically as straight segments. Nevertheless, its combinatorial properties are regular: interior nodes have degree eight, and boundary nodes have smaller degree. Connectivity under 8-neighborhood tends to merge regions and reduce the number of separate components relative to 4-neighborhood.

3 Connected Components in 8-Neighborhood

3.1 Component labeling overview

Connected components are maximal groups of eligible cells where any cell can reach any other via a sequence of 8-neighborhood adjacencies. Component labeling algorithms assign an identifier to each cell indicating which connected component it belongs to. The resulting count and shape of components depend on whether diagonal links are enabled.

3.2 Flood fill / region growing

Flood fill (or region growing) explores from a seed cell by repeatedly adding all adjacent eligible neighbors, then continuing outward from newly added cells. With 8-neighborhood, the frontier expands into diagonal-adjacent cells, which can cause structures that merely touch at a corner to be labeled as a single component. This effect is often desired when corner contact represents continuity in the data.

3.3 Union–find approach

Union–find (disjoint set union) supports efficient component identification by unifying sets of nodes that should be connected. One common method scans the grid and, for each eligible cell, unions it with eligible 8-neighborhood neighbors. After all unions, each set corresponds to a connected component. This approach can be advantageous when the grid is processed in a batch or when multiple merges are expected.

3.4 Complexity and implementation considerations

For a grid with \(N\) cells, typical flood fill and DFS/BFS-based labeling run in \(O(N)\) time, assuming constant-time neighbor generation. Union–find also achieves near-linear performance, often expressed as \(O(N \alpha(N))\) with path compression and union by rank, where \(\alpha\) is the inverse Ackermann function. Implementation details that affect correctness include consistent eligibility checks, avoiding double-processing, and correct handling of boundary degrees.

4 Traversal and Pathfinding

4.1 BFS with 8-neighborhood

Breadth-first search (BFS) explores layers of cells reachable in a fixed number of steps. With 8-neighborhood adjacency, each expansion considers up to eight next positions, producing an 8-directional wavefront. When all moves are treated as equal cost, BFS yields the shortest path in terms of number of adjacency steps rather than geometric distance.

4.2 DFS with 8-neighborhood

Depth-first search (DFS) uses a stack or recursion to follow a path as far as possible before backtracking. Under 8-neighborhood, DFS may traverse diagonally more readily than 4-neighborhood, which can change the order of exploration and the discovered path (even when the final reachable set is the same). DFS is typically used for reachability or for algorithms that require spanning structure rather than shortest paths.

4.3 Shortest paths on uniform grids

On a uniform grid, geometric shortest paths depend on how diagonal moves are weighted. If diagonals are assigned the same cost as orthogonal moves, the result approximates shortest paths in a step metric. If diagonals are weighted to reflect their longer geometric length (often \(\sqrt{2}\) relative to 1 for orthogonal moves), then path cost better matches Euclidean distance. The choice affects whether diagonal connectivity produces overly “aggressive” shortcutting.

4.4 Heuristics and practical routing

In heuristic pathfinding (such as A*), neighborhood connectivity influences both the branching factor and the suitability of heuristics. For 8-neighborhood grids with appropriately weighted diagonals, heuristic functions such as octile-distance can align well with the cost structure. Practically, 8-neighborhood routing can produce smoother-looking routes and reduce detours around corners, but it also increases the likelihood of corner-adjacent “tunneling” unless obstacle handling is consistent.

5 Effects on Geometry and Topology

Diagonal adjacency can merge components that would remain separate under 4-neighborhood. This merging can significantly alter quantitative measures such as component count, average area per component, and the inferred structure of objects. For thin shapes, a single diagonal connection may act like a bridge, connecting two otherwise distinct branches.

5.2 Corner-touching behavior

With 8-neighborhood, two regions that only touch at a corner are considered connected, because the corresponding corner cells are adjacent diagonally. This can be desirable when the intended notion of “contact” includes corner adjacency. In other contexts, it can be an artifact that collapses nearby but distinct structures into one component.

5.3 Implications for thinning and skeletonization

Morphological operations that rely on connectivity—especially thinning and skeletonization—depend on the rules used to decide which pixels may be removed without breaking connectivity. Using 8-neighborhood generally preserves diagonal connections more readily, which can yield different skeleton branches and endpoints compared with 4-neighborhood-based thinning criteria.

5.4 Measuring connectedness in analyses

Connectivity choice affects derived topology-like descriptors: how many components exist, how components merge, and how junctions are counted. Even when the raw pixel grid is the same, switching neighborhood rules can change the interpretation of whether a structure is continuous or fragmented. Robust analysis therefore often includes reporting the neighborhood definition used or validating results under multiple connectivity assumptions.

6 Boundary Conditions and Edge Handling

6.1 Borders and corners on finite grids

On finite images or lattices, cells near the boundary have fewer than eight possible neighbors. Correctly limiting neighbor indices prevents attempts to access cells outside the domain. From a modeling perspective, this means boundary connectivity is inherently weaker unless the domain is extended by padding or periodic conditions.

6.2 Padding strategies

Padding can be used to control how boundaries behave. Common approaches include:

  • Zero padding (treat out-of-bounds as background),
  • Replication (mirror or repeat boundary values),
  • Reflection padding (use mirrored contents),
  • Explicit boundary masks (mark out-of-bounds as ineligible).

Padding affects whether objects can connect through the border region and can change component labels.

6.3 Out-of-bounds neighbor handling

An algorithm must define how to treat neighbor positions that fall outside the grid. Typical choices are to ignore them (no edge) or treat them as background/inactive. For graph searches, ignoring out-of-bounds neighbors prevents spurious connectivity. For segmentation tasks, treating them as inactive generally prevents unwanted merges across the boundary.

6.4 Consistency requirements for algorithms

Neighbor definitions should be consistent across all steps of a pipeline: labeling, measurements, and morphological updates. If one stage assumes 8-neighborhood while another uses 4-neighborhood (or vice versa), the combined result can exhibit discontinuities or contradictory topology. Consistency also matters when mixing different libraries or implementations that may adopt different default connectivity conventions.

7 Applications

7.1 Image segmentation and blob detection

In segmentation, 8-neighborhood connectivity is used to turn a thresholded mask into labeled regions. Diagonal adjacency can capture connectivity in textured or noisy images where objects touch at corners. For blob detection, it influences whether closely spaced features become separate candidates or are merged into a single detected blob.

7.2 Morphological operations (high-level view)

Many morphological processes—such as opening, closing, dilation, and erosion—interact with neighborhood choices when defining structuring elements and connectivity constraints. While the operations themselves are defined via kernels, the interpretation of results such as connectedness, component survival, and post-filtering often depends on whether diagonal adjacency is considered.

7.3 Mask-based analysis and post-processing

After initial segmentation, post-processing steps frequently involve removing small components, filling holes, or applying connectivity-based filters. With 8-neighborhood, small diagonal bridges may cause two larger regions to be treated as one, affecting decisions about whether components should be pruned or merged.

7.4 Grid-based simulations and cellular models

Beyond image processing, 8-neighborhood rules appear in cellular automata and grid simulations, where each cell interacts with its surrounding Moore neighborhood (the 3×3 neighborhood). This interaction model affects pattern evolution: diagonal influence can change growth, diffusion-like behavior, and the emergence of connected clusters.

8.1 4-neighborhood vs 8-neighborhood comparison

4-neighborhood connectivity emphasizes side adjacency and tends to treat corner contact as insufficient for connection, often preserving separation between diagonally touching regions. 8-neighborhood treats diagonal contact as connected, typically producing fewer components and more merged structures. The comparison is central when selecting a connectivity notion that matches the semantics of the data.

8.2 N-neighborhood generalization (conceptual)

More general neighborhood concepts can be defined by expanding the adjacency region beyond the immediate 3×3 block. Conceptually, an N-neighborhood can specify additional offsets or a radius around each cell, potentially including farther diagonal and near-diagonal relationships. Such generalizations allow tuning between strict local connectivity and broader interaction models.

8.3 Connectivity in higher dimensions (brief)

In 3D grids, analogs of 8-neighborhood correspond to including face-adjacent and edge-/corner-adjacent voxels depending on the chosen connectivity model. The central idea remains the same: adjacency rules define which lattice neighbors are considered directly connected, thereby shaping component structure in volumetric data.

8.4 Mixed-connectivity strategies

Some pipelines combine connectivity types depending on the operation. For instance, component labeling might use 8-neighborhood to capture diagonal continuity, while certain morphological steps or skeleton constraints might rely on stricter adjacency to avoid unintended merges. Mixed strategies aim to balance sensitivity to structure with control over topological artifacts.