Computer vision: Thin edges with non-maximum suppression

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 ., then edge 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

Example 1 · Input
3 5 10
0 0 4 8 8
0 0 4 8 8
0 0 4 8 8
Expected output
.....
..#..
.....
edge pixels: 1
Example 2 · Input
5 3 10
0 0 0
0 0 0
4 4 4
8 8 8
8 8 8
Expected output
...
...
.#.
...
...
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)

Lesson: Edges with Sobel gradients →