31 January 2013 Storage and addressing scheme for practical hexagonal image processing
Author Affiliations +
J. of Electronic Imaging, 22(1), 010502 (2013). doi:10.1117/1.JEI.22.1.010502
Abstract
We present a practical hexagonal storage and addressing scheme, which eliminates the difference between theory and implementation in other addressing methods. This scheme employs a middleware-based address-mapping module that separates the algorithm and specific data addressing; thus any hexagonal algorithm can keep the native and consistent forms as in the coordinate system through theory and implementation. The scheme simplifies the implementation work and preserves all excellent features of the hexagonal lattice. Finally, we discuss the implementation issues and show that it’s feasible and can be implemented efficiently.
Li: Storage and addressing scheme for practical hexagonal image processing

1.

Introduction

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.

Fig. 1

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

JEI_22_1_010502_f001.png

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.

2.

Proposed Scheme

2.1.

Fundamentals

We start with a regular hexagonal sampling lattice as shown in Fig. 2, in which four vectors vh1, vr1, vh2, and vr2 are defined. Then we can use vh1 and vh2 to define a sampling matrix:11

(1)

Vh=[vh1|vh2]=[112032].
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.

JEI_22_1_010502_f002.png

We can define another sampling matrix using vr1 and vr2:

(2)

Vr=[vr1|vr2]=[120032].
Because vr1 and vr2 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 (ui,vi) in (u,v), and (xi,yi) in (x,y), its position can be given as Vh[uivi] and Vr[xiyi]. Since the same pixel corresponds with the same position, the following equality holds:

(3)

Vh[uivi]=Vr[xiyi].

Because Vr is nonsingular, we can get

(4)

[xiyi]=Vr1Vh[uivi]=[2101][uivi].

Similarly, we have the following equation:

(5)

[uivi]=Vh1Vr[xiyi]=[121201][xiyi].
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 (ui,vi), (xi,yi), and (ri,ci) 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 (ui,vi)(xi,yi)(ri,ci). 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.

JEI_22_1_010502_f003.png

2.2.1.

Hexagonal to rectangular

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

(6)

{xi=2uiviyi=vi.

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:

(7)

{ri=yici=xi/2
with · the floor operator.

2.2.3.

Comprehensive mapping

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

(8)

{ri=vici=(2uivi)/2.

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

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] [(2*uivi)/2] from Eq. (8). However, it’s not apparent which pixel is accessed in the expression. Instead, we choose to apply a macro substitution

#define FunImData(ui,vi)ImData[vi][(2*uivi)/2]
to hide the address mapping and data accessing. The form (ui,vi) is much close to the array form [ri][ci], and it’s clear and readable.

Further, we can treat (2*uivi)/2 as (2*uivi)/2 followed by the floor operation ·. Since the multiplying and dividing of 2 can be efficiently executed by shift instructions, we prefer to rewrite (2*uivi)/2 as ((ui<<1)vi)>>1. 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:

#define FunImData(ui,vi)ImData[vi][((ui<<1)vi)>>1].

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

#define FunImData(ui,vi)ImData[FirstPtr[vi]+((ui<<1)vi)>>1],
in which the multiplication is eliminated through the lookup table.

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={1,1,0,11,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.

JEI_22_1_010502_f004.png

For any two points Pi(ui,vi) and Pj(uj,vj), the Euclidean distance can be defined as

(9)

D(Pi,Pj)=(uiuj)2+(vivj)2(uiuj)(vivj).

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.

References

1. 

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

2. 

R. M. Mersereau, “The processing of hexagonally sampled two-dimensional signals,” Proc. IEEE 67(6), 930–949 (1979).IEEPAD0018-9219http://dx.doi.org/10.1109/PROC.1979.11356Google Scholar

3. 

L. MiddletonJ. Sivaswamy, Hexagonal Image Processing: A Practical Approach, Springer, London (2005).Google Scholar

4. 

W. E. SnyderH. QiW. Sander, “Coordinate system for hexagonal pixels,” Proc. SPIE 3661, 716–727 (1999).PSISDG0277-786Xhttp://dx.doi.org/10.1117/12.348629Google Scholar

5. 

J. Rosenthal, “Filters and filterbanks for hexagonally sampled signals,” Ph.D. Thesis, Georgia Institute of Technology (2001).Google Scholar

6. 

R. C. Staunton, “Hexagonal sampling in image processing,” Adv. Imag. Electron Phys. 107, 231–307 (1999).AIEPFQ1076-5670http://dx.doi.org/10.1016/S1076-5670(08)70188-5Google Scholar

7. 

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

8. 

I. Her, “Geometric transformations on the hexagonal grid,” IEEE Trans. Image Process. 4(9), 1213–1222 (1995).IIPRE41057-7149http://dx.doi.org/10.1109/83.413166Google Scholar

9. 

P. Sheridan, Spiral Architecture for Machine Vision, Ph.D. Thesis, Univ. of Technology Sydney (1996).Google Scholar

10. 

L. MiddletonJ. Sivaswamy, “Framework for practical hexagonal-image processing,” J. Electron. Imag. 11(1), 104–114 (2002).JEIME51017-9909http://dx.doi.org/10.1117/1.1426078Google Scholar

11. 

D. E. DudgeonR. M. Mersereau, Multidimensional Digital Signal Processing, Prentice Hall, Englewood Cliffs, New Jersey (1984).Google Scholar

Xiangguo Li, "Storage and addressing scheme for practical hexagonal image processing," Journal of Electronic Imaging 22(1), 010502 (31 January 2013). http://dx.doi.org/10.1117/1.JEI.22.1.010502
Submission: Received ; Accepted
JOURNAL ARTICLE
3 PAGES


SHARE
KEYWORDS
Associative arrays

Data storage

Algorithms

Image processing

Data conversion

Imaging systems

Image storage

Back to Top