|
1.IntroductionAlmost 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,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 Scheme2.1.FundamentalsWe start with a regular hexagonal sampling lattice as shown in Fig. 2, in which four vectors , , , and are defined. Then we can use and to define a sampling matrix:11 Obviously, any sampled pixel can be located by a pair of integer values, and we can set up a hexagonal coordinate system , which is natural and complete for the hexagonal processing.We can define another sampling matrix using and : Because and are orthogonal, we can set up a Cartesian coordinate system . 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 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: That is, the coordinates in one system can be uniquely mapped into the other system and vice versa.2.2.Middleware-Based Address MappingWe 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. 3.Implementation Issues3.1.Address Mapping ComputationGiven 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 to hide the address mapping and data accessing. The form () is much close to the array form [][], and it’s clear and readable.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: 3.2.Array Addressing ComputationIn 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 in which the multiplication is eliminated through the lookup table.3.3.Neighbor and Distance ComputationSince 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 4.ConclusionWe 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. ReferencesD. P. PetersenD. Middleton,
“Sampling and reconstruction of wave-number-limited functions in n-dimensional Euclidean spaces,”
Inf. Control, 5
(4), 279
–323
(1962). http://dx.doi.org/10.1016/S0019-9958(62)90633-2 IFCNA4 0019-9958 Google Scholar
R. M. Mersereau,
“The processing of hexagonally sampled two-dimensional signals,”
Proc. IEEE, 67
(6), 930
–949
(1979). http://dx.doi.org/10.1109/PROC.1979.11356 IEEPAD 0018-9219 Google Scholar
L. MiddletonJ. Sivaswamy, Hexagonal Image Processing: A Practical Approach, Springer, London
(2005). Google Scholar
W. E. SnyderH. QiW. Sander,
“Coordinate system for hexagonal pixels,”
Proc. SPIE, 3661 716
–727
(1999). http://dx.doi.org/10.1117/12.348629 PSISDG 0277-786X Google Scholar
J. Rosenthal,
“Filters and filterbanks for hexagonally sampled signals,”
Georgia Institute of Technology,
(2001). Google Scholar
R. C. Staunton,
“Hexagonal sampling in image processing,”
Adv. Imag. Electron Phys., 107 231
–307
(1999). http://dx.doi.org/10.1016/S1076-5670(08)70188-5 AIEPFQ 1076-5670 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). http://dx.doi.org/10.1117/1.3589306 JEIME5 1017-9909 Google Scholar
I. Her,
“Geometric transformations on the hexagonal grid,”
IEEE Trans. Image Process., 4
(9), 1213
–1222
(1995). http://dx.doi.org/10.1109/83.413166 IIPRE4 1057-7149 Google Scholar
P. Sheridan, Spiral Architecture for Machine Vision, Univ. of Technology Sydney,
(1996). Google Scholar
L. MiddletonJ. Sivaswamy,
“Framework for practical hexagonal-image processing,”
J. Electron. Imag., 11
(1), 104
–114
(2002). http://dx.doi.org/10.1117/1.1426078 JEIME5 1017-9909 Google Scholar
D. E. DudgeonR. M. Mersereau, Multidimensional Digital Signal Processing, Prentice Hall, Englewood Cliffs, New Jersey
(1984). Google Scholar
|