## 1.

## Introduction

Almost 50 years ago, Petersen and Middleton^{1} 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, Mersereau^{2} 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,^{8}9.^{–}^{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.

## 2.

## Proposed Scheme

## 2.1.

### Fundamentals

We start with a regular hexagonal sampling lattice as shown in Fig. 2, in which four vectors ${v}_{h1}$, ${v}_{r1}$, ${v}_{h2}$, and ${v}_{r2}$ are defined. Then we can use ${v}_{h1}$ and ${v}_{h2}$ to define a sampling matrix:^{11}

## (1)

$${V}_{h}=[{v}_{h1}|{v}_{h2}]=[\begin{array}{cc}1& -\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\\ 0& \raisebox{1ex}{$\sqrt{3}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\end{array}].$$We can define another sampling matrix using ${v}_{r1}$ and ${v}_{r2}$:

## (2)

$${V}_{r}=[{v}_{r1}|{v}_{r2}]=[\begin{array}{cc}\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.& 0\\ 0& \raisebox{1ex}{$\sqrt{3}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\end{array}].$$Given a sampled pixel in Fig. 2, and let its coordinates be $({u}_{i},{v}_{i})$ in $(u,v)$, and $({x}_{i},{y}_{i})$ in $(x,y)$, its position can be given as ${V}_{h}{[\begin{array}{cc}{u}_{i}& {v}_{i}\end{array}]}^{\prime}$ and ${V}_{r}{[\begin{array}{cc}{x}_{i}& {y}_{i}\end{array}]}^{\prime}$. Since the same pixel corresponds with the same position, the following equality holds:

## (3)

$${V}_{h}\left[\begin{array}{c}{u}_{i}\\ {v}_{i}\end{array}\right]={V}_{r}\left[\begin{array}{c}{x}_{i}\\ {y}_{i}\end{array}\right].$$Because ${V}_{r}$ is nonsingular, we can get

## (4)

$$\left[\begin{array}{c}{x}_{i}\\ {y}_{i}\end{array}\right]={V}_{r}^{-1}{V}_{h}\left[\begin{array}{c}{u}_{i}\\ {v}_{i}\end{array}\right]=\left[\begin{array}{cc}2& -1\\ 0& 1\end{array}\right]\left[\begin{array}{c}{u}_{i}\\ {v}_{i}\end{array}\right].$$Similarly, we have the following equation:

## (5)

$$\left[\begin{array}{c}{u}_{i}\\ {v}_{i}\end{array}\right]={V}_{h}^{-1}{V}_{r}\left[\begin{array}{c}{x}_{i}\\ {y}_{i}\end{array}\right]=\left[\begin{array}{cc}\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.& \raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\\ 0& 1\end{array}\right]\left[\begin{array}{c}{x}_{i}\\ {y}_{i}\end{array}\right].$$## 2.2.

### 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 $({u}_{i},{v}_{i})$, $({x}_{i},{y}_{i})$, and $({r}_{i},{c}_{i})$ 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 $({u}_{i},{v}_{i})\Rightarrow \phantom{\rule{0ex}{0ex}}({x}_{i},{y}_{i})\Rightarrow ({r}_{i},{c}_{i})$. An example is shown in Fig. 3.

## 2.2.2.

#### Rectangular to array

It’s natural to map a block of rectangular data into an array, while the data are staggered in this case. From the coordinates corresponding between Fig. 3(b) and 3(c), we can reach the relation:

with $\lfloor \xb7\rfloor $ the floor operator.## 3.

## Implementation Issues

## 3.1.

### Address Mapping Computation

Given a rectangular shape image is hexagonally sampled with $nR$ rows and $nC$ columns, and the data are stored in an array ImData[$nR$][$nC$]. Suppose a pixel ($ui,vi$) is stored at ($ri,ci$), we can access the pixel ($ui,vi$) by ImData[$vi$] [$\lfloor (2*ui-vi)/2\rfloor $] 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 $\lfloor (2*ui-vi)/2\rfloor $ as $(2*ui-vi)/2$ followed by the floor operation $\lfloor \xb7\rfloor $. Since the multiplying and dividing of 2 can be efficiently executed by shift instructions, we prefer to rewrite $(2*ui-vi)/2$ as $((ui<<1)-vi)>>1$. Because the floor operation $\lfloor \xb7\rfloor $ is a byproduct of the integer operations, and the coordinates are indeed integer values, the floor operator $\lfloor \xb7\rfloor $ can be omitted. Therefore, we obtain the efficient expression:

## 3.2.

### Array Addressing Computation

In the addressing of two-dimensional (2-D) array ImData[$ri$][$ci$], i.e., $nC*ri+ci$, 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[$nR*nC$], and another 1-D array is also defined: FirstPtr[$nR$], which is used to store the address of the start element of each row. Then, the macro is rewritten as

## 3.3.

### 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} $ou=\phantom{\rule{0ex}{0ex}}\{1,1,0,-1-1,0\}$, and $ov=\{0,1,1,0,-1,-1\}$; then, the coordinates of the $k$’th neighbor can be given as ($ui+ou[k],\phantom{\rule{0ex}{0ex}}vi+ov[k]$).

For any two points ${P}_{i}({u}_{i},{v}_{i})$ and ${P}_{j}({u}_{j},{v}_{j})$, the Euclidean distance can be defined as

## 4.

## Conclusion

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.