Distance Transform (Chamfer)

Problem

Compute the city-block distance from every pixel to the nearest zero pixel of a binary mask.

Use two chamfer sweeps with unit steps over the 4 orthogonal neighbors (forward pass then backward pass). Pixels with value 1 and no reachable zero keep the sentinel H * W + 1.

Test cases

case 1

in: [[[1,1,1],[1,0,1],[1,1,1]]]

expected: [[2,1,2],[1,0,1],[2,1,2]]

case 2

in: [[[0,1,1],[1,1,1],[1,1,1]]]

expected: [[0,1,2],[1,2,3],[2,3,4]]

case 3

in: [[[0,0],[0,0]]]

expected: [[0,0],[0,0]]

case 4

in: [[[1,1],[1,1]]]

expected: [[5,5],[5,5]]

Starter codePython

def distance_transform(mask):
    # Your code here
    pass

4 test cases · run your code against them in the editor