1.

Introduction

Almost 50 years ago, Petersen and Middleton¹ 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² 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,³ 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.

Fig. 1

Illustration of one hexagonally sampled rectangular shape image: (a) pixels in the hexagonal coordinate system, and (b) data in the storage array.

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.⁷ 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–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:¹¹

Eq. (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}].$$

Obviously, any sampled pixel can be located by a pair of integer values, and we can set up a hexagonal coordinate system $(u,v)$, which is natural and complete for the hexagonal processing.

Fig. 2

Illustration of hexagonal lattice and the coordinate system.

We can define another sampling matrix using $v_{r1}$ and $v_{r2}$:

Eq. (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}].$$

Because $v_{r1}$ and $v_{r2}$ are orthogonal, we can set up a Cartesian coordinate system $(x,y)$. In this case, the coordinates of any sampled pixel are integers but not arbitrary; thus it is not suitable for hexagonal processing.

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:

Eq. (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

Eq. (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:

Eq. (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].$$

That is, the coordinates in one system can be uniquely mapped into the other system and vice versa.

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 (x_i,y_i)\Rightarrow (r_i,c_i)$. An example is shown in Fig. 3.

Fig. 3

Example of address mapping: (a) in the skewed hexagonal coordinate system; (b) in the Cartesian coordinate system; and (c) in the storage array.

2.2.1.

Hexagonal to rectangular

This conversion is based on Eq. (4), and can be rewritten as

Eq. (6)

$$\{\begin{array}{l}{x}_i=2u_i-v_i\\ y_i=v_i\end{array}.$$

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:

Eq. (7)

$$\{\begin{array}{l}{r}_i=y_i\\ c_i=\lfloor x_i/2\rfloor \end{array}$$

with $\lfloor ·\rfloor$ the floor operator.

2.2.3.

Comprehensive mapping

Combining Eqs. (6) and (7), we can get the final mapping formulae:

Eq. (8)

$$\{\begin{array}{l}{r}_i=v_i\\ c_i=\lfloor (2u_i-v_i)/2\rfloor \end{array}.$$

Based on the addressing relation, a middleware module can be designed to perform a data-accessing function.

3.

Implementation Issues

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:⁴ $ou=\{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],vi+ov[k]$).

Fig. 4

Illustration of relative position of one pixel and its six neighbors.

For any two points $P_i(u_i,v_i)$ and $P_j(u_j,v_j)$, the Euclidean distance can be defined as

Eq. (9)

$$D(P_i,P_j)=\sqrt{{(u_i-u_j)}^2+{(v_i-v_j)}^2-(u_i-u_j)(v_i-v_j)}\mathrm{.}$$

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.