Sobel edges are thick. Canny's non-maximum suppression keeps only the crest of each edge.
What to build
A program that thins a Sobel edge map by keeping pixels that are peaks along their gradient direction.
Requirements
- For every inner pixel compute Sobel gx and gy, the magnitude √(gx² + gy²) and the direction atan2(gy, gx) in degrees, taken modulo 180 and rounded to the nearest of 0, 45, 90 or 135.
- Border pixels have magnitude 0 and are never edges. An inner pixel is an edge (
#) when its magnitude is at least T and at least as large as both neighbours along its direction (see the hints). - Print the H × W map of
#and., thenedge pixels: N.
Input
Line 1: H, W and the threshold T. Then H rows of W values.
Output
H map rows and the count line.
Constraints
3 ≤ H, W ≤ 40; T ≥ 1.
Example
Input:
3 5 10
0 0 4 8 8
0 0 4 8 8
0 0 4 8 8
Output:
.....
..#..
.....
edge pixels: 1
Why it works
Across an edge the magnitude rises to a crest and falls again; comparing each pixel with its two neighbours along the gradient keeps only the crest, which is the one-pixel-wide centre of the edge.
Examples
3 5 10 0 0 4 8 8 0 0 4 8 8 0 0 4 8 8
..... ..#.. ..... edge pixels: 1
5 3 10 0 0 0 0 0 0 4 4 4 8 8 8 8 8 8
... ... .#. ... ... edge pixels: 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Round the direction to the nearest of 0, 45, 90 and 135 degrees with `int((angle + 22.5) // 45) % 4 * 45`, where angle = degrees(atan2(gy, gx)) % 180.
Hint 2
The neighbours to compare are (r, c ± 1) for 0°, (r ± 1, c ± 1) for 45°, (r ± 1, c) for 90°, and (r + 1, c − 1) and (r − 1, c + 1) for 135°. Border pixels have magnitude 0.
Solution
Show one correct solution (try it yourself first)
import math
h, w, t = input().split()
h, w, t = int(h), int(w), float(t)
p = [list(map(int, input().split())) for _ in range(h)]
mag = [[0.0] * w for _ in range(h)]
ang = [[0] * w for _ in range(h)]
for r in range(1, h - 1):
for c in range(1, w - 1):
gx = (p[r - 1][c + 1] + 2 * p[r][c + 1] + p[r + 1][c + 1]) - (p[r - 1][c - 1] + 2 * p[r][c - 1] + p[r + 1][c - 1])
gy = (p[r + 1][c - 1] + 2 * p[r + 1][c] + p[r + 1][c + 1]) - (p[r - 1][c - 1] + 2 * p[r - 1][c] + p[r - 1][c + 1])
mag[r][c] = math.sqrt(gx * gx + gy * gy)
a = math.degrees(math.atan2(gy, gx)) % 180
ang[r][c] = int((a + 22.5) // 45) % 4 * 45
STEP = {0: (0, 1), 45: (1, 1), 90: (1, 0), 135: (1, -1)}
count = 0
for r in range(h):
line = ""
for c in range(w):
keep = False
if 0 < r < h - 1 and 0 < c < w - 1:
dy, dx = STEP[ang[r][c]]
m = mag[r][c]
keep = m >= t and m >= mag[r + dy][c + dx] and m >= mag[r - dy][c - dx]
line += "#" if keep else "."
count += keep
print(line)
print("edge pixels:", count)