Array set addressing: enabling technology for the efficient processing of hexagonally sampled imagery

摘要

It has long been known that there are numerous advantages to sampling images hexagonally rather than rectangularly. However, due to various shortcomings of the addressing schemes, hexagonal sampling for digital images has not been embraced by the mainstream digital imaging community. The idea of using hexagonal sampling for digital imaging applications has been around since the early 1960s, yet no efficient addressing method for hexagonal grids has been developed in that time. This paper introduces a new hexagonal addressing approach, called array set addressing (ASA), that solves the problems exhibited by other addressing methods. The ASA approach uses three coordinates to represent the hexagonal grid as a pair of rectangular arrays. This representation supports efficient linear algebra and image processing manipulation. ASA-based implementations of several basic image processing operations are presented and shown to be efficient. A hexagonal fast Fourier transform, based on the fact that the Fourier kernel becomes separable when using ASA coordinates, is also presented.