📘

Intensity Coherence Segmentation

MediumGraphs, Matrix, DFS/BFS 📚 CV - 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.

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:

Starting at (1,1) with value 5, all pixels are reachable through paths where adjacent intensity differences are ≤ 3.

More from CV - DSA

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

👑

Continue the full explanation

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

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.