Medial Axis for Chamfer Distances in 2D, 3D and 4D

E. Remy and E. Thiel.     [ pdf 957k]
Medial Axis for Chamfer Distances: computing Look-Up Tables and Neighbourhoods in 2D or 3D. Pattern Recognition Letters, 23(6):649-661, April 2002.

Here you can download the program sources (in C langage) to compute the Look-Up Tables and the Neighbourhoods in several dimensions: LutChamfer2D.c , LutChamfer3D.c , LutChamfer4D.c .

To compile, type cc LutChamfer2D.c -o LutChamfer2D and to run, type LutChamfer2D (the same for 3D and 4D). The program will ask the image size L, which stands for the maximum radius in pixels to be tested. Then, the program will ask to choose in a list of chamfer mask, or to enter your own chamfer mask in custom mode.

The resulting look-up table and the Lut mask are saved in a text file. We give the files for some known chamfer masks:

Dimension 2
2, 3	(J. Hilditch and D. Rutovitz, 1969)
3, 4	(G. Borgefors, 1984)
5, 7	(B.J.H. Verwer, 1991)
5, 7, 11	(G. Borgefors, 1986)
14, 20, 31, 44	(G. Borgefors, 1986)
72, 102, 161	(E. Thiel, 1994)
62, 88, 139, 196, 224	(E. Thiel, 1994)
68, 96, 152, 215, 245, 280, 340, 346, 413	(E. Thiel, 1994)
Dimension 3
3, 4, 5	(G. Borgefors, 1984)
3, 4, 5, 7	(E. Remy and E. Thiel, 2000)
4, 6, 7, 9, 10	(E. Remy and E. Thiel, 2000)
7, 10, 13, 18	(E. Remy and E. Thiel, 2000)
7, 10, 12, 16, 17	(E. Remy and E. Thiel, 2000)
11, 16, 19, 45	(E. Remy and E. Thiel, 2000)
19, 27, 33	(B.J.H. Verwer, 1991)
19, 27, 33, 43, 47	(E. Remy and E. Thiel, 2000)
Dimension 4
3, 4, 5, 6	(G. Borgefors, 1984)
7, 10, 12, 13	(G. Borgefors, 2000)

Remarks:

• On the right of the table we have quoted the author(s) of the chamfer masks. You can find the full references in our paper.
• The starting point of our work is the problem raised in (E. Thiel, 1994, p. 81), with the 2D mask 14,20,31,44. We give the solution in the table, with a 6 weightings Lut mask.
• From the moment that a look-up table and a Lut mask are computed for a given L, you can use it to compute the medial axis on any image up to 2*L side length.
• In 4D, we save memory by using hypercones in place of hypervolumes. Hypercones are 24 times smaller than hypervolumes. For instance for L = 128, we allocate only 2*22 Mbytes (versus 2*512 Mbytes if we were using hypervolumes). In the program source, we explain how a hyxel is accessed.

Medial axis from 3D objects, computed with (19, 27, 33, 43, 47). Click to enlarge:

Last update 19 feb 2002