Intensity Coherence Segmentation

mediumPROGraphsGraphs, Matrix, DFS/BFSCV - DSA

A key challenge in low-level image processing is grouping pixels that are "locally coherent" based on their intensity values. This technique forms the basis of early segmentation methods like superpixels.

You are given a grayscale image represented by an $M \times N$ matrix where each cell contains a non-negative integer intensity value. Two pixels $(r_1, c_1)$ and $(r_2, c_2)$ are considered coherently connected if they are 4-directionally adjacent (horizontally or vertically) AND the absolute difference between their intensities is less than or equal to a threshold $T$ .

Your task is, given a starting pixel $(r, c)$ , to find the size (total number of pixels) of the coherently connected region it belongs to. You should treat the image grid as an undirected graph where pixels are nodes and coherence defines the edges.

Implement Solution.coherenceSize(image, r_start, c_start, T): image is the $M \times N$ grid, the starting pixel is given as row r_start and column c_start (0-indexed), and T is the threshold. Return the region size as an integer.

Constraints:

The grid dimensions $M \times N$ are at most $50 \times 50$ .
Intensity values $\in [0, 255]$ .
Threshold $T \in [0, 255]$ .

About Topic: This implementation models a simplified approach to bottom-up segmentation, where pixels are recursively grouped based on local similarity constraints (similarity/proximity) to form larger, meaningful regions, often preceding full object recognition.

Example

Input

image = [[6,7,8],[5,5,9],[1,2,3]]
start = (1, 1)
threshold = 3

Output

Reasoning

image is a $3 \times 3$ intensity grid; the start (row 1, column 1, 0-indexed) has intensity $5$ , and $T = 3$ .
Neighbours of the start passing $|I_a - I_b| \le 3$ : up $7$ (diff $2$ ), left $5$ ( $0$ ), down $2$ ( $3$ , on the threshold, so it counts). Right $9$ fails: $|5-9| = 4$ .
Growing from those: $7 \to 6$ , $7 \to 8$ , $2 \to 1$ , $2 \to 3$ (each diff $1$ ).
The $9$ that the start rejected now joins through $8$ : $|8-9| = 1 \le 3$ .
Every one of the $3 \times 3 = 9$ pixels is in the region, so the output is 9.
Notice coherence compares adjacent pixels, never the start: the region spans intensities $1$ to $9$ (range $8 > T$ ) because each step is small. With $T = 0$ only the two $5$ s connect, giving $2$ .

More from CV - DSA

Concept primerPREVIEW

Intensity Coherence Segmentation: Comprehensive Background

1. Background Knowledge

Intensity coherence segmentation models pixels as nodes in an undirected graph, where edges exist between 4-adjacent pixels if $|I(r_1,c_1) - I(r_2,c_2)| \leq T$ . The task finds the connected component size containing starting pixel $(r,c)$ .

Key concepts:

4-connectivity: Horizontal/vertical neighbors only (no diagonals).
Graph representation: $M \times N$ nodes, edges defined by spatial adjacency + intensity constraint.
Connected component: Maximal set of mutually reachable pixels via coherence edges.
Applications: Foundation for superpixel generation (grouping similar pixels) and early image segmentation pipelines.

Prerequisites:

2D array traversal (matrix indexing).
Graph traversal fundamentals.
Queue/stack data structures.

2. Algorithm Approach

This is a classic connected component labeling problem in a constraint graph. Standard solutions:

Algorithm	Description	Suitability
BFS/DFS	Explore from seed, mark visited neighbors within T.	Ideal for single component, O(MN) time.
Union-Find	Pre-build all edges, find set size.	Overkill for single query.
Flood Fill	Recursive stack-based neighbor expansion.	Risk of stack overflow (50×50 safe).

BFS/DFS preferred due to small constraints ( $50 \times 50 = 2500$ pixels) and single-component focus.

3. Step-by-Step Strategy

Validation: Check bounds $0 \leq r < M$ , $0 \leq c < N$ .
Visited tracking: Create $M \times N$ boolean array, initialize False.
Initialize queue/stack: Add seed $(r,c)$ , mark visited[r][c] = True, size = 1.
Traverse (BFS example):

directions = [(-1,0), (1,0), (0,-1), (0,1)] # up, down, left, right

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.