Canny Hysteresis Thresholding
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 >high → mark as edge (1)
- Weak edges: pixels with low<magnitude≤high
- Suppressed: pixels with magnitude ≤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:
edge_map = [[10, 5, 2], [3, 15, 8], [1, 6, 12]] high = 9, low = 4
[[1, 1, 0], [0, 1, 1], [0, 1, 1]]
- Initially, we mark pixels with magnitude >high (9) as strong edges (1) and pixels with magnitude ≤low (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<magnitude≤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)
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
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.