Medial axis lookup table and test neighborhood computation for 3D chamfer norms

Chamfer distances are discrete distances based on the propagation of local distances, or weights, defined in a mask. The medial axis, i.e. the centers of maximal balls (balls which are not contained in any other ball), is a powerful tool for shape representation and analysis. The extraction of maximal disks is performed in the general case by testing the inclusion of a ball in a local neighborhood with covering relations usually represented by lookup tables.The proposed method determines if a mask induces a norm and in this case, computes the lookup tables and the test neighborhood based on geometric properties of the balls of chamfer norms, represented as HH-polytopes. The method does not need to repeatedly scan the image space, and improves the computation time of both the test neighborhood detection and the lookup table computation.