Merge Similar Pixels

mediumPROUnion-FindUnion-Find, SimilarityCV - DSA

Problem Statement

In image segmentation, adjacent pixels with similar intensities are often merged into the same region.

Given a list of pixel values and a list of edges (i, j) indicating which pixels are adjacent, merge pixels into groups where the absolute intensity difference is at most threshold.

Return the number of distinct groups after merging.

Applications

Region-based segmentation
Color quantization
Superpixel generation

Constraints

$1 \leq len(pixels) \leq 1000$
$0 \leq pixels[i] \leq 255$
$0 \leq threshold \leq 255$

Example

Input

pixels = [10, 12, 50, 52], edges = [[0,1], [1,2], [2,3]], threshold = 5

Output

Reasoning

Inputs: pixels holds 4 intensities, $p = (10, 12, 50, 52)$ , indexed 0 to 3. edges lists which pixels touch: 0–1, 1–2 and 2–3, a simple chain. threshold $= 5$ is the largest intensity gap that still counts as "similar".
Which edges qualify: an edge $(i, j)$ $(i, j)$ merges its pixels only when $|p_i - p_j| \le 5$ $∣ p_{i} - p_{j} ∣ \leq 5$ .
- 0–1: $|10 - 12| = 2 \le 5$ , merge.
- 1–2: $|12 - 50| = 38 > 5$ , no merge, even though the pixels are adjacent.
- 2–3: $|50 - 52| = 2 \le 5$ , merge.
Resulting groups: $\{0, 1\}$ (the dark region) and $\{2, 3\}$ (the brighter region), so the output is 2.
Notice that merging is transitive along qualifying edges: with intensities $10, 12, 14$ chained by edges and a threshold of $2$ , all three pixels form one group, even though $|10 - 14| = 4$ . A pixel with no qualifying edge stays a group of its own.

Learn this in

Advanced Data StructuresDSA Study Plan

More from CV - DSA

Largest Connected Regionmedium Count Connected Regionsmedium Smallest Window Containing All Featureshard Maximum Brightness Windowmedium Moving Average Filtereasy

Concept primerPREVIEW

Merge Similar Pixels: Comprehensive Background and Solution Guide

1. Background Knowledge

This problem models image segmentation as union-find clustering on a graph where pixels are nodes and edges represent adjacency. Key concepts:

Graph Representation: Pixels as vertices, adjacency list as edges
Similarity Metric: $|pixels[i] - pixels[j]| \leq threshold$ defines mergeable regions
Connected Components: Final count of distinct groups after transitive merging (if A↔B and B↔C, then A,B,C form one group)
Applications: Region growing, superpixel generation, color quantization

Prerequisites: Graph theory, Union-Find (Disjoint Set Union - DSU) data structure.

2. Algorithm Approach

Union-Find (DSU) with Path Compression and Union by Rank is optimal:

Core Operations:
1. find(x): Return root parent of x (with path compression)
2. union(x, y): Merge sets containing x and y (by rank for balance)
3. count_components(): Number of unique roots

Why DSU? Handles transitive closure efficiently (A connects B, B connects C → A,B,C connected automatically).

Alternatives (less efficient here):

DFS/BFS traversal: $O(V+E)$ but requires explicit graph traversal
Kruskal's MST: Similar but more complex

3. Step-by-Step Strategy

class UnionFind:
 def __init__(self, n):
 self.parent = list(range(n))
 self.rank = * n
 self.components = n

 def find(self, x):
 if self.parent[x] != x:
 self.parent[x] = self.find(self.parent[x]) # Path compression
 return self.parent[x]

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.

PRO

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