Digital boundary tracking

In many three-dimensional imaging applications, the three-dimensional space is represented by an array of cubical volume elements (voxels) and a subset of the voxels is specified by some property. Objects in the scene are then recognised by being components of the specified set and individual boundaries are recognised as sets of voxel faces separating objects from components in the complement of the specified set. This paper deals with the problem of algorithmic tracking of such a boundary specified by one of the voxel faces lying in it. The paper is expository in that all ideas are carefully motivated and introduced. Its original contribution is the investigation of the question of whether the use of a queue (of loose ends in the tracking process which are to be picked up again to complete the tracking) is necessary for an algorithmic tracker of boundaries in three-dimensional space. Such a queue is not needed for two-dimensional boundary tracking, but published three-dimensional boundary trackers all make use of such a thing. We prove that this is not accidental: under some mild assumptions, a boundary tracker without a queue will fail its task on some three-dimensional boundaries.