Canny Hysteresis Thresholding

hardPROEdge DetectionComputer Vision 2

Given an NMS edge map (2D matrix of magnitudes) and two thresholds (high, low), apply hysteresis thresholding to produce a binary edge map.

Algorithm:

Strong edges: pixels with magnitude $> \text{high}$ → mark as edge (1)
Weak edges: pixels with $\text{low} < \text{magnitude} \leq \text{high}$
Suppressed: pixels with magnitude $\leq \text{low}$ → non-edge (0)
Connectivity check: Weak edges that are connected to strong edges (8-connectivity) become strong edges. Use BFS/DFS to propagate from strong edges to connected weak edges.

Return a binary edge map where 1 = edge, 0 = non-edge.

Example

Input

edge_map = [[10, 5, 2], [3, 15, 8], [1, 6, 12]]
high = 9, low = 4

Output

[[1, 1, 0], [0, 1, 1], [0, 1, 1]]

Reasoning

Initially, we mark pixels with magnitude $> \text{high}$ $> high$ ( $9$ $9$ ) as strong edges (1) and pixels with magnitude $\leq \text{low}$ $\leq low$ ( $4$ $4$ ) as non-edges (0), resulting in:
- Strong edges: $(1,2)$ with magnitude $15$ , $(1,0)$ with magnitude $10$ , $(2,2)$ with magnitude $12$
- Non-edges: $(0,2)$ with magnitude $2$ , $(1,0)$ is an edge, $(2,0)$ with magnitude $1$
We then identify weak edges with $4 < \text{magnitude} \leq 9$ : $(0,1)$ with magnitude $5$ , $(1,2)$ is already marked as an edge, $(2,1)$ with magnitude $6$
Next, we apply the connectivity check:
- $(0,1)$ is connected to $(1,0)$ (strong edge), so it becomes a strong edge
- $(2,1)$ is connected to $(2,2)$ (strong edge), so it becomes a strong edge
- $(1,2)$ is already marked and $(2,0)$ is not connected to any strong edge
The final output is: [[1, 1, 0], [0, 1, 1], [0, 1, 1]]

Constraints

edge_map is a 2D list of non-negative magnitudes
high > low >= 0
Use 8-connectivity (all 8 neighbors)
Return binary 2D list (0 or 1)

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Concept primerPREVIEW

Background Knowledge

Edge detection is a fundamental concept in computer vision, which involves identifying and locating edges within an image. Edges are significant changes in the intensity of an image, and they often correspond to important features such as object boundaries. The Canny edge detection algorithm is a widely used technique for edge detection, which consists of several stages: noise reduction, gradient calculation, non-maximum suppression, and double thresholding. Hysteresis thresholding is a key component of the Canny algorithm, where two thresholds are used to determine whether a pixel is an edge or not.

The concept of hysteresis thresholding is based on the idea that edges in an image are not isolated points, but rather connected curves or lines. By using two thresholds, we can separate strong edges from weak edges and then connect weak edges to strong edges based on their proximity. This approach helps to reduce noise and produce more coherent edge maps. The use of $8$ -connectivity for checking the connectivity between weak and strong edges is also important, as it allows for more robust edge detection.

In the context of this problem, we are given a non-maximum suppressed (NMS) edge map, which represents the magnitude of the gradient at each pixel. Our goal is to apply hysteresis thresholding to this edge map to produce a binary edge map, where $1$ represents an edge and $0$ represents a non-edge. This involves identifying strong edges, weak edges, and suppressed pixels based on the given thresholds and then propagating strong edges to connected weak edges using a connectivity check.

Algorithm/Approach

The general approach to solving this problem involves the following algorithm pattern:

Initialize a binary edge map with the same dimensions as the input NMS edge map
Iterate over each pixel in the NMS edge map and apply the hysteresis thresholding rules to determine whether it is a strong edge, weak edge, or suppressed pixel
Use a graph traversal algorithm (such as BFS or DFS) to propagate strong edges to connected weak edges
Return the resulting binary edge map

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