Medial axis for chamfer distances: Computing look-up tables and neighbourhoods in 2D or 3D

Medial axis, also known as centres of maximal disks, is a representation of a shape, which is useful for image description and analysis. Chamfer or weighted distances are discrete distances which allow to approximate the Euclidean distance with integers. Medial axis extraction for chamfer distances is discussed in the literature, but only for simple cases. The principle is to use local tests and look-up tables. In this paper, we give an algorithm which computes for any chamfer distance in 2D or 3D, the look-up table and, very important, the neighbourhood to be tested. (C) 2002 Elsevier Science B.V. All rights reserved.