EP04_09 — 🗺️ Distance Transform and the Object’s “Core”

4.9.9 EP04_09 🗺️ Distance Transform and the Object’s “Core”

In mobile robotics, when planning a route within a corridor, the robot wants to know not only where free space exists, but also how far each free point is from the nearest wall. The safest paths tend to pass through the corridor’s “core,” away from obstacles.

The morphological distance transform assigns to each pixel a value representing its distance to the nearest edge, according to the metric defined by the structuring element. Pixels near the edge receive low values, while more internal pixels receive higher values. The pixel with the maximum value corresponds to the most protected region of the object, often associated with its morphological center.

See Figure 4.38 for a simulation of this EP.

4.9.9.1 📋 Implementation Guidelines

Image dimensions: read the integers \(L\) (rows) and \(C\) (columns) of image \(f\).
Dimensions of \(B\): read the integers \(L_B\) (rows) and \(C_B\) (columns) of the structuring element.
Structuring element: read the matrix \(b\), containing value \(0\) at the center and negative values at other positions.
Image: read the binary matrix \(f\) (values \(0\) or \(1\)), row by row.
Preparation: multiply the image by \(L\times C\), ensuring that internal pixels have an initial value sufficiently high for distance propagation.
Distance transform: compute the distance matrix using the method mm.dist1(f,b).
Output: display the matrix resulting from the distance transform.

4.9.9.2 📌 Computational Constraints

Use the weighted erosion implementation provided by the library.
The structuring element may contain arbitrary negative values.
The transform must be obtained by iteratively applying weighted erosions until a fixed point is reached.

⚠️ Crucial Note on Matrix Reading: Since the structuring element may contain negative integer values (e.g., -1 and -99), do not use the mm.readImg function to read matrix \(b\). This function converts data to uint8 type, causing underflow and corrupting negative values. Read the \(L_B\) rows of \(b\) manually using the default int type. Image \(f\) can continue to be read normally using mm.readImg.

4.9.9.3 🧠 Theoretical Foundation

Concept	Meaning	Visual Impact
\(\text{dist}(y,x)\)	Morphological distance to the nearest edge according to the metric defined by \(b\)	More internal pixels receive higher values
Maximum value	Pixel farthest from the edge	Approximates the object’s morphological center
Weighted structuring element	Defines the displacement costs between neighboring pixels	Determines the distance metric used
Thin objects	Narrow regions of the object	Produce low distance values

4.9.9.4 📦 Input and Output Specification (VPL)

Input:

Line 1: integer \(L\).
Line 2: integer \(C\).
Line 3: integer \(L_B\).
Line 4: integer \(C_B\).
Next \(L_B\) lines: integer elements of matrix \(b\).
Next \(L\) lines: binary elements (\(0\) or \(1\)) of matrix \(f\).

⚠️ Implementation note: The elements of matrix \(f\) (0 or 1) must be multiplied by 255 to generate an adequate binary image (\(0\) and \(255\)) before applying the Distance Transform (DT).

Output:

Distance transform matrix with \(L\) rows and \(C\) columns.

4.9.9.5 📌 Example

Input	Output	Observation
5 9 3 3 -99 -1 -99 -1 0 -1 -99 -1 -99 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 2 2 2 2 2 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0	Result of the distance transform.

Note: the value -99 acts as a practical approximation of \(-\infty\), preventing propagation along diagonals. Thus, only horizontal and vertical neighbors contribute to the distance, producing the Manhattan distance.

🗺️ EP04_09 Simulator: Distance Transform Erosion Layers

Click cells to draw your own object or select a predefined shape to calculate the cascading distance map.

Calculated Distance Map

Figure 4.38: Simulador EP04_09: Distância por Transformada (Camadas de Erosão)

%%writefile EP04_09.py
# Python code

Overwriting EP04_09.py

TestSuite("EP04_09.py").run()

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

🔍 Testing Python: EP04_09.py
⚠️ EP04_09.py: Empty file (fewer than 3 lines). Tests skipped.