Discrete Convexity, Straightness, and the 16-Neighborhood

摘要

In this paper, we extend some results in discrete geometry based on the 8-neighborhood to that of the 16-neighborhood, which now includes the chessboard and the knight moves. We first present some analogies between an 8-digital arc and a 16-digital arc as represented by shortest paths on the grid. We present a transformation which uniquely maps a 16-digital arc onto an 8-digital arc (and vice versa). The grid-intersect-quantization (GIQ) of real arcs is defined with the 16-neighborhood. This enables us to define a 16-digital straight segment. We then present two new distance functions which satisfy the metric properties and describe the extended neighborhood space. Based on these functions, we present some new results regarding discrete convexity and 16-digital straightness. In particular, we demonstrate the convexity of a 16-digital straight segment. Moreover, we define a new property for characterizing a digital straight segment in the 16-neighborhood space. In comparison to the 8-neighborhood space, the proposed 16-neighborhood coding scheme offers a more compact representation without any loss of information.