Skip to main content
Research article - Peer-reviewed, 2005

Distance transforms for three-dimensional grids with non-cubic voxels

Strand R, Borgefors G


Distance transforms on the face-centered cubic (fee) grid and the body-centered cubic (bcc) grid are examined. Since the voxels on the fee and bee grids are better approximations of a Euclidean ball than the cube, the distance transforms (DTs) on these grids can be less rotation dependent than those in Z(3), which is a desirable feature. Optimal (according to the error function) weights are calculated and integer approximations of these weights are found. Also, the two-dimensional city block distance is generalized to the fee and bee grids by considering a unit distance between gridpoints whose corresponding voxels share a face. A method to compute the DTs is presented. The results are evaluated both theoretically and by actually computing some DTs. (c) 2005 Elsevier Inc. All rights reserved

Published in

Computer Vision and Image Understanding
2005, Volume: 100, number: 3, pages: 294-311

    SLU Authors

    • Borgefors, Gunilla

      • Centre for Image Analysis, Swedish University of Agricultural Sciences

    Publication Identifiers


    Permanent link to this page (URI)