Almost 50 years ago, Petersen and Middleton1 studied the general sampling problem in two and higher dimensions, and they showed that hexagonal lattice was optimal for circularly band-limited images. Besides 13.4% fewer samples than the rectangular counterpart, Mersereau2 further demonstrated that hexagonal processing was superior in filter performance and computational efficiency. Furthermore, hexagonal lattice has better geometric properties, such as equidistant neighbors and uniform connectivity,3 and it can also be widely found in the structure of biological visual sensors, such as compound eyes of insects and retina of human eyes; therefore, hexagonal processing is attractive in computer vision.
Generally, the coordinate systems for hexagonal lattice are not orthogonal, and this causes inconveniences for practical implementations. For instance, given a rectangular shape image, if it is sampled with rectangular lattice, as in the real world, the sampled data can be mapped into an array in memory naturally and can be addressed the same as in the Cartesian coordinates; if the image is sampled with hexagonal lattice, as shown in Fig. 1(a), things become different. Because the coordinates are skewed, if we want to address data as in the skewed coordinates, we may map the parallelogram region into an array;4,5 obviously it is not efficient in memory usage.
Intuitively, we need to store the image data only,4,5 i.e., map the rectangular region into an array as shown in Fig. 1(b). Meanwhile, new trouble arises. Consider two pixels located on an odd row and even row, respectively, together with their own six neighbors, it’s clear that the two area shapes are quite different in the storage array, which means two sets of filters are needed for the odd rows and the even rows separately.5,6 Recently, Rummelt et al.7 proposed a scheme called array set addressing (ASA), in which two arrays were used to store odd rows and even rows separately. Three coordinates were used in the system. Rummelt also developed fundamental operation rules for the ASA system, and its significant feature is that it provides uniform addressing and operations for all data. In addition, there are other addressing methods for hexagonal shape images,89.–10 and they are not the concern of this paper.
Except for the parallelogram region mapping, we observe that current implementations rely on the specific data storage and addressing closely, which results in expression difference from the original forms in the skewed coordinate system, and this also introduces a gap between theory and implementation. Motivated by the description of row-based storage in Ref. 5, we adopt the middleware concept, and use an address-mapping module to separate the algorithm and data addressing. In this scheme, any algorithm uses the coordinates in the skewed hexagonal system, and accesses data from the storage array through the module; therefore, any algorithm can keep the consistent forms through theory and implementation. We also discuss the implementation issues, and show it’s simple and feasible for practical use.
We can define another sampling matrix using and :
Given a sampled pixel in Fig. 2, and let its coordinates be in , and in , its position can be given as and . Since the same pixel corresponds with the same position, the following equality holds:
Because is nonsingular, we can get
Similarly, we have the following equation:
Middleware-Based Address Mapping
We aim to use both the natural hexagonal coordinates and the memory efficient array storage, and set up address mapping from the hexagonal coordinate system to the storage array, where the rectangular addressing serves as a bridge. Let , , and be the addresses of one pixel in the hexagonal coordinate system, in the Cartesian coordinate system, and in the storage array, respectively; then, we express the mapping process as . An example is shown in Fig. 3.
Hexagonal to rectangular
This conversion is based on Eq. (4), and can be rewritten as
Rectangular to array
Address Mapping Computation
Given a rectangular shape image is hexagonally sampled with rows and columns, and the data are stored in an array ImData. Suppose a pixel () is stored at (), we can access the pixel () by ImData  from Eq. (8). However, it’s not apparent which pixel is accessed in the expression. Instead, we choose to apply a macro substitution
Further, we can treat as followed by the floor operation . Since the multiplying and dividing of 2 can be efficiently executed by shift instructions, we prefer to rewrite as . Because the floor operation is a byproduct of the integer operations, and the coordinates are indeed integer values, the floor operator can be omitted. Therefore, we obtain the efficient expression:
Array Addressing Computation
In the addressing of two-dimensional (2-D) array ImData, i.e., , there is a multiplication instruction. Snyder et al.4 proposed an alternative approach, and we adopt here. The 2-D array is serialized to a one-dimensional (1-D) array row-by-row: ImData, and another 1-D array is also defined: FirstPtr, which is used to store the address of the start element of each row. Then, the macro is rewritten as
Neighbor and Distance Computation
Since the coordinates contain position information, we can perform geometry-related operations easily; for example, finding neighbors and computing distance.
As illustrated in Fig. 4, the relative positions of any pixel and its six neighbors are stable. We label the six neighbors as 0 to 5, and define two 1-D offset arrays:4 , and ; then, the coordinates of the ’th neighbor can be given as ().
For any two points and , the Euclidean distance can be defined as
We present a middleware-based storage and addressing scheme for practical hexagonal image processing. The scheme uses the original coordinates in the hexagonal system, and two benefits are kept. One is that we can implement the algorithm naturally as in the theory; the other is that we can perform geometry-related operations easily. The scheme is feasible and efficient.
D. P. PetersenD. Middleton, “Sampling and reconstruction of wave-number-limited functions in n-dimensional Euclidean spaces,” Inf. Control 5(4), 279–323 (1962).IFCNA40019-9958http://dx.doi.org/10.1016/S0019-9958(62)90633-2Google Scholar
L. MiddletonJ. Sivaswamy, Hexagonal Image Processing: A Practical Approach, Springer, London (2005).Google Scholar
J. Rosenthal, “Filters and filterbanks for hexagonally sampled signals,” Ph.D. Thesis, Georgia Institute of Technology (2001).Google Scholar
N. I. RummeltJ. N. Wilson, “Array set addressing: enabling technology for the efficient processing of hexagonally sampled imagery,” J. Electron. Imag. 20(2), 023012 (2011).JEIME51017-9909http://dx.doi.org/10.1117/1.3589306Google Scholar
P. Sheridan, Spiral Architecture for Machine Vision, Ph.D. Thesis, Univ. of Technology Sydney (1996).Google Scholar
D. E. DudgeonR. M. Mersereau, Multidimensional Digital Signal Processing, Prentice Hall, Englewood Cliffs, New Jersey (1984).Google Scholar