EP02_04 — 📐 Distance Transform in Binary Images

2.17.4 EP02_04 📐 Distance Transform in Binary Images

Given a binary image where pixels with value 1 represent the object and pixels with 0 represent the background, the distance of a background pixel is the smallest distance to the nearest object pixel. Object pixels are assigned a distance of 0. For simplicity, consider that the image has only a single object consisting of one pixel with value 1.

Problem: Read a binary image \(L \times C\) and a metric, and compute this simplified distance by applying one of the three formulas:

\[d_{\text{Euclidean}} = \sqrt{(\Delta r)^2 + (\Delta c)^2}\]

\[d_{\text{City-block}} = |\Delta r| + |\Delta c|\]

\[d_{\text{Chessboard}} = \max(|\Delta r|,\; |\Delta c|)\]

where \(\Delta r\) is the row difference and \(\Delta c\) is the column difference between two pixels.

2.17.4.1 🖼️ Why does this matter? - Applications of the DT

The Distance Transform (DT) appears in dozens of computer vision pipelines:

Metric	Complexity	Typical application
Euclidean	🔴 \(O(n^2)\) naive	Skeletonization, shape matching
City-block	🟡 \(O(n)\) with 2 passes	Morphology, dilation/erosion
Chessboard	🟢 \(O(n)\) with 2 passes	Morphology, dilation/erosion

2.17.4.2 📌 Technical Requirements

Input: * First line: \(L\) and \(C\) (integers).
- Second line: metric name (euclidean, cityblock, or chessboard).
- Then, the binary matrix \(L \times C\) (values 0 or 1).
Object pixels (1): distance \(= 0\) (or \(0.00\) for Euclidean).
Background pixels (0): distance to the single object pixel in the image.
Rounding (Euclidean): print with 2 decimal places (format :.2f). City-block and Chessboard produce integers — print without decimals.
Output: space-separated values, one row of the matrix per line.
See Figure 2.15 for a simulation of this EP.

2.17.4.3 📌 Examples

Input	Output	Observation
4 4 chessboard 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0	2 2 2 2 2 1 1 1 2 1 0 1 2 1 1 1	The Chessboard distance is \(\max(\\|dx\\|, \\|dy\\|)\). The only object pixel is \((2,2)=0\); the others store their minimum distance to it.

2.17.4.4 📌 Final Remarks

Since the image has only one single-pixel object, the distance of each background pixel is simply the distance from that pixel to the single object point.
The implementation may use brute force (iterate over all image pixels and compute the distance directly), since \(L\) and \(C\) are small in the test cases.
This problem serves as a warm-up for the general Distance Transform, which will be addressed in later chapters with multiple objects and optimized algorithms.

📐 Simulator EP02_04: Interactive Distance Transform Metrics: L₁, L₂ and L_∞

Click on the cells of the Binary Image to toggle object pixels (1) and observe the minimum distance map computed in the resulting matrix.

Metric: Chessboard (L_∞) City-block (L₁) Euclidean (L₂)

Binary Image (Click to Edit)

Distance Transform

      5×5 grid · 1 object pixel(s) · Metric: Chessboard (integer)
    

Figure 2.15: EP02_04 Simulator: Distance Transform in Binary Image (Chessboard, City-block and Euclidean)

%%writefile EP02_04.cpp
// your solution

Overwriting EP02_04.cpp

TestSuite("EP02_04.cpp").run()

✔️ EP02_04.cases already exists in casos/
📋 5 case(s) loaded from casos/EP02_04.cases

🔍 Testing C++: EP02_04.cpp
⚠️ EP02_04.cpp: Empty file (fewer than 3 lines). Tests skipped.