لخّصلي

Study on Hexagonal Grid in Image Processing

Fayas Asharindavida, Nisar Hundewale,Sultan Aljahda li Taif University, Saudi Arabia*

ABSTRACT

Image processing is very important in several appli cations and have been using in them very efficientl y.

Normally we use a rectangular grid for the processi ng of images. There could be some other approaches to use as an alternate for this. One new approach is to change t he grid from rectangular to hexagonal, because of i ts various advantages over the later. Out of the many advantag es for the hexagonal structure in image processing, the primary one is its resemblance with the arrangement of photorec eptors in the human eyes. Due to the change in arra ngement the amount of pixels required is very less. There is no inconsistency in pixel connectivity and thus angul ar resolution is higher in this arrangement. Hexagonal grid will be advantageous in many real time applications. Implem entation of

Hexagonal grid can be done in various methods inclu ding the spiral addressing scheme. Applying hexagon al grid in image processing is very advantageous and easy for mimicking human visual system.

Image processing, Hexagonal grid, Hexagonal address ing scheme, spiral addressing scheme 1 INTRODUCTION

Researchers have been studying the feasibility of i ntroducing the hexagonal grid in the area of image processing. There are various pixels tessellation s chemes available to represent digital images. Hexag onal grid is also a pixel tessellation scheme which is efficient than a ny other schemes. Normally digital images are mappe d on square lattice and here we are changing the square lattice to hexagonal lattice for the hexagonal image proce ssing. Hexagonal coordinate system is well suited for creating the a rtificial human visual system, because the arrangem ents of the photo receptors in the human retina are in hexagonal form .

The first section in this explains about the reason s for rectangular to hexagonal grid change. The fol lowing section describes the various features of hexagonal sampling scheme. In the next section various metho ds for hexagonal image representation are mentioned. Later section e xplains about the various addressing schemes and th en the conclusion of the present study. 2 RECTANGULAR TO HEXAGONAL GRIDS

In hexagonal lattice number of pixels required to s ample a data is very less 1 . Due to the resemblance of human vision with the hexagonal arrangement the computati onal operations will become faster. And thus it wil l give a new face in the processing speed and efficiency of image pro cessing operations. There are various works availab le in the literature which touches this field. All of them points to the advantages of the hexagonal grid with the normal s quare grid.

Even though there are many advantages, hexagonal gr id is not widely used in image processing. Lack of capturing and display devices in hexagonal grid mak es it impossible to attain the benefits of hexagona l grid. Due to this limitation researchers are trying to mimic the hexa gonal grid on rectangular grid itself. But all of t he methods are simulations only and thus we cannot achieve the rea l advantages of the hexagonal grid. In the real hex agonal structure pixels are not arranged in rows and columns. Resear chers introduced various addressing schemes and coo rdinate systems to implement the hexagonal grid atleast theoretical ly. Sampling lattice is one aspect of the sensing m ethodology used in computer vision. Thus we can represent a hexagonal grid of pixels on the existing rectangular screens for modeling and processing purpose, which is more suitable for comp uter vision modeling. Once sampling lattice is digi tized into hexagons, various image processing operations can b e performed on these sub-sampled images. According to Mersereau 2 , in a hexagonally sampled image there will be 13.4 % fewer sampling points compared with the square grid. All image processing operatio ns can be done on this grid with utilizing all the benefits. Many resampling techniques were proposed like brick wall , quincunx sampling, least squares approximation of splines, etc 3 .

One of the resampling techniques to obtain hexagona l grid is to suppress alternate rows and columns fr om the square * Email : [email protected] , [email protected] , [email protected] , Website: cit.tu.edu.sa

sampled image 4 as shown in the figure, Fig 1 and the image proces sing operations can be performed on the resampled hexagonal image. Fig 1 (a) Rectangular sampling (b) Hexagonal s ub sampling Another resampling method was proposed by Staunton 5 which is to shift the alternate rows of pixels in the image by a half pixel distance. 3 FEATURES OF HEXAGONAL SAMPLING SCHEME Digitization is one of the hardest tasks which scie ntists were worried about in image processing. Beca use the real scene will be in a continuous plane and the im ages are on a digital screen with discrete points. In the process of digitization, the discrete points referred as pixel s have to be arranged on the screen which should be properly addressed.

The arrangement of the pixels should be regular and its representation on the plane should be efficien t also. 3.1 Regular Tessellation schemes T here are only three tessellations available to tile a plane which is regular and the samples do not ov erlap among each other and with its gaps. All other tesse llation schemes will either be inconsistent in the neighborhood connectivity or will become gaps or overlaps among the samples. The square tessellation is the commonl y used one and it uses the Cartesian coordinate system for all ope rations and thus it is simple. The triangular one g ives a tight arrangement than the square one which explains that more information is contained in the same image. T he hexagonal one is the most compact and tight packing among the other two. Normally we used to take beehives as th e typical example for the tight packing which is in hexagonal arrangement. 3.2 More Efficient Sampling Schemes Aliasing will occur to the images whose sampling r ate is not sufficient. Peterson and Middleton 6 found out the fact that the least samples are required for the re construction of a wave number limited signal in hex agonal lattice. From this it is clear that square lattice is not the bes t one. Mersereau 2 also concluded that signals in Fourier space requi res only 13.4% lesser samples to represent the same ima ge data in hexagonal grid compared to the rectangul ar one. By using this advantage it is clear that the storage space r equired will become less and the computation cost w ill also become less.

Vitulli 7 also investigated the sampling efficiency using he xagonal grid and concluded that it’s the same as Me rsereau explained in his work. Vitulli also found out that using the hexagonal grid, wider spectra of signal c an be sampled without aliasing with fewer amounts of samples. 3.3 Smaller Quantization Error Quantization is compulsory for the image processing operations because of the limited capable sensors to represent the real world scenes. Quantization error is an important measure to analyze the merits of t he configurations of different types of sensors. Kamgar-Parsi 8,910 showed that hexagonal sampling gives lesser quanti zation error when compared to square. 3.4 Consistent Connectivity In an image, pixels are arranged adjacent to each other. Every pixel is connected to each other based on some specific criteria 11 . In a square grid, there are two types of pixel ne ighborhood. They are four-neighborhood and the othe r one is the eight-neighborhood. So there will be fou r-way connection or eight-way connection depending upon the number of common edges share among the pixels 12 . In the hexagonal grid there is only six way conne ctivity. In this there will be only one common edge and two common corners . This will be useful when we are doing the operati ons such as skeletonisation 12,13 . The connectivity in hexagonal domain is consisten t and it is fixed to six way connectivity 14, 15 . 3.5 Equidistance In the normal grid that is the square grid, we have two types of distant measures. The distance betwee n the diagonal pixels are √ 2 times than that between the horizontal pixels as in Fig 2(a).

2 (a) (b)

Fig 2 Distance in square grid and hexagonal gird In hexagonal grid, there is only one consistent con nectivity and each pixel has six neighboring pixels . And all the pixels are single unit distant from each other as in Fig 2 (b). 3.6. Greater Angular Resolution For representing curved images hexagonal grid is e fficient. Adjacent pixels in hexagonal grid are sep arated by sixty degree instead of ninety degree in the existi ng one. So, curved images can be represented in a b etter way. Main reason behind this is the consistent connectivity t hat we have already studied. Human eyes have a spec ial visual preference of seeing the lines which are at oblique angle 16 . So this is another reason for representing lines also in a better way in hexagonal grid. 3.7 Higher Symmetry Many morphological operations are developed by Ser ra 17 and are been widely used in Image processing .He studied the same on different grids and identified the fact that hexagonal grid has higher symmetry an d simple operations. 3.8 Other Features of Hexagonal Grid Hexagonal grid closely resembles with the human vi sual system. The rods and cones are arranged in a hexagonal fashion in the fovea. So in order to mimi c any of the human visual system activity we need t o be in the hexagonal grid to get the better results. 4 HEXAGONAL IMAGE REPRESENTATION Even after getting all the advantages of the hexago nal grid it has not been used widely in image proce ssing. The main reason is that there is no image capturing and display device which is in hexagonal grid. So lot of research is going on to simulate the hexagonal representation. Three of those methods will be explained in this section. By using this we will be able to mimic the hexagonal grid by utilizi ng the rectangular grid itself. 4.1 Mimic Hexagonal Pixels Using Square Pixels In this, He 16 proposed a method by delaying the alternate TV lin es by half a pixel width. In this method pixels will be in square shape and is simple in the case o f implementation also ( Fig 3 (a)). But the equidis tant property of the hexagonal grid is not maintained in this. From the figure it can be seen that the horizontal and verti cal distance is coming to 1 unit whereas the diagonal will be √ 3/2.

Fig 3 (a) Hexagonal structure using half pixel sh ift Fig 3 (b) Rectangular pixe ls on a hexagonal sampling grid

Staunton 13 proposed a new approach in which the central pixel which is the sampling point has all its neighboring pixels arranged in a circular shape as in Fig 3 (b). In this approach all the sampling poi nt pixel are equally distant from each other. Distance between the horiz ontal points is 2/ √ 3 and the angle between two neighboring points will be 60°. The aspect ratio of equally sized rows and columns will be 2/ √ 3:1 in this approach. 4.2. Pseudo Hexagonal Pixel Another approach was from Yuan 18 who evaluated the visual effect of hexagonal and s quare pixel. He simulated both lattices in which hexagonal pixel is called as hyperpel and was simulated using the squ are grid itself. But the results were very bad due to the vagueness in t he screen resolution.

Yabushita 19 took this idea and extended to create a pseudo hex agonal structure which was also made from square pixels in the aspect ratio of 12:14. Later M iddleton and Sivaswamy 20,21 done a great work which was a new approach in mimicking the hexagonal grid. In their work they introduced the resampling of square image into a hexagonal image. 4.3 Mimic Hexagonal Structure In this, one hexagonal pixel means four square pix els and the equivalent grey level value is the aver age of these pixels 22 . This mimicking scheme will preserve the consisten t neighborhood property. But by using the averaging method for calculating the grey value, resolution become l esser. Another important property known as equidist ant property is also not met in this approach. 4.4 Virtual Hexagonal Structure Wu 23 created a breakthrough in mimicking the hexagonal structure. In this he is using a virtual spiral architecture in which a spiral architecture is used during the processing part. The normal image in th e traditional square grid is mapped into virtual spiral architecture and does the processing. Once the processing is done i t is converted back into square grid and is displayed. It is different from all the above mimicking methods because it wil l neither create any distortion nor reduce resolution. 5 HEXAGONAL STRUCTURE ADDRESSING Till we have discussed about representing and mimi cking the hexagonal pixels to simulate the hexagona l grid.

But we can’t use the traditional row and column app roach for labeling hexagonal pixels. We need to hav e proper coordinate system for efficiently addressing and st oring hexagonal data. Research works in this area w ill be explained in the following section. 5.1 2-Axes coordinate addressing scheme Luczak and Rosenfield 24 , proposed the two axes oblique coordinate system ( Fig 4) to address hexagonal structure. Here they use two basis vectors which ar e orthogonal to each other for representing the hex agonal pixel as in the figure. Any point in the two dimensional space can be represented using this system. Each point is represented as a unique ordered pair of the vectors and can easily c onverted to and fro from Cartesian coordinate syste m.

Fig 4 2-axes coordinate system for hexagonal stru cture 5.2. Three-Coordinate Symmetrical Coordinate Frame In the previous method they used two vectors for a ddressing the data. Her 25 proposed a three coordinate system which is denoted as *R 3 , for representing the hexagonal data as in Fig 5 ( a). In this, the distance between the neighboring pixels is one unit. Fig 5 (a) Symmetrical hexagonal frame *R 3 (b) Relation between *R 3 and R 3 This method is very much connected with the 3-dimen sional Cartesian frame R 3 . The figure (Fig 5 (b)) gives a better understanding of the frame. All geometrical properties and the theoretical studies done can be easily transferred to *R 3 from R 3 . Her 25 has done many works based on this frame especially in deriving the affine transformation.

Geometrical operations in this will be simple due t o its relationship with the 3-dimensional Cartesian frame R 3 . The symmetry property of the hexagonal grid is also pre served in this coordinate system.

5.2 Single Indexing System

Another addressing scheme was introduced by Middlet on and Sivaswamy 6 which is called as Spiral Architecture (Fig 6 (a)) based on single dimensional addressing system. In this the addressing starts spirally from the middle of the image in powers of seven. Spiral architecture consi sts of this addressing scheme and two operations de fined on it which are spiral addition and spiral multiplication which corresponds to translation of the image and rotati on of the image respectively.

Fig 6 (a) Spiral addressing Fig.5.5. (a) Hexagon al image structure with indices (b) Balanced ternar y addition

Generalized Balanced Ternary System is modified by Middleton and Sivaswamy 6 and proposed the single index system for addressing pixels for hexagonal im age processing as in Fig 6(b) and 6 (c). For findin g the neighboring pixels spiral addition operation 6 is used. The spiral address of the whole image can be found by following the direction of the spiral rotation as in the figure Fig 7.

Fig 7 Spiral rotation direction

For representing an image in spiral addressing sche me we require 7 α hexagons, where ‘ α ’ denotes the level of spiral architecture. If ‘ α ’is 1 it is in the first level of spiral architectu re and it contains 7 elements. There is a relation to know approximately how many levels are required to represent an image in spiral architecture. log log log 7
M N α + = (1)

Where ‘ α ’ is the number of levels

M is the number of rows in the image

N is the number of columns in the image

The addressing scheme using spiral addressing schem e have many advantages over other addressing scheme s as well as from square image processing. Storage space required in this is very less and geometric transf ormations are very easy because of its origin at the centre. It also g ives consistent connectivity and unique neighborhoo d which is different from the traditional connectivity and neighborhood relationship. 6 CONCLUDING REMARKS From the above discussions and explanations it as c lear that there will be improvement while processin g with hexagonal sampling. Since there is no dedicated har dware available for hexagonal based image capturing and display, conversion has to be done from square to hexagonal image before hexagonal image processing. Spiral add ressing scheme gives a very good approach for trying the he xagonal image processing. The result will be clear only when we have the hardware for acquisition and display which works in hexagonal grid. A few companies are tryin g to build such devices, let’s hope that it will come in the near f uture.

7 REFERENCES [1] Golay, M., “Hexagonal parallel pattern transformati on”, IEEE Transactions on computers, 18(8), 733-740 (1969). [2] Mersereau, R.M., “The processing of Hexagonally Sam pled Two-Dimensional Signals”, Proceedings of the IEEE, 67,930-949 (1979). [3] Frédéric Chazal, David Cohen-Steiner, Andre Lieutie r, “A sampling theory for compact sets in Euclidean space”,.

Proceedings of the 22 nd annual symposium on Computational geometry, ACM ( 2006). [4] Rajan, E.G., Sanjay,T., and Pramod Sankar,K., “Hexa gonal Pixel Grid Modeling and Processing of Digital Images

Using CLAP Algorithms”, International Conference on Systemics, Cybernetics and Informatics, February 1 2–15, (2004). [5] Staunton, Richard C. and Storey Neil, "A comparison between square and hexagonal sampling methods for pipeline image processing", Proc.SPIE, Vol. 1194, 142-151 (1 989). [6] Lee Middleton and Jayanthi Sivaswamy, [ Hexagonal I mage Processing – A Practical Approach], Springer-V erlag

London Limited (2005). [7] Vitulli, R., et al., “Aliasing effects mitigation b y optimized sampling grids and impact on image acqu isition chains”,

IEEE International Geosciences and Remote Sensing S ymposium, IGARSS, 2, 979-981 (2002). [8] Kamgar-Parsi, B. and Sander, W.A., “Quantization er ror in spatial sampling: comparison between square and hexagonal pixels”, Proceedings of IEEE Computer Soc iety Conference on Computer Vision and Pattern

Recognition, CVPR, 604-611 (1989). [9] Kamgar-Parsi, B., “Evaluation of quantization error in computer vision”, IEEE Transactions on Pattern Analysis and

Machine Intelligence, 11(9) 929-940 (1989). [10] Kamgar-Parsi, B., “Quantization error in hexagonal sensory configurations”, IEEE Transactions on Patte rn Analysis and Machine Intelligence, 14(6),665-671 (1992). [11] Gonzalez, R.C. and Woods, R.E., [ Digital image pr ocessing], Prentice Hall, New Jersey, (2002). [12] Deutsch, E.S., “Thinning algorithms on rectangular, hexagonal, and triangular arrays”, Communications of the

ACM, 15(9), 827-837 (1972). [13] Staunton, R.C., “An analysis of hexagonal thinning algorithms and skeletal shape representation”, Patt ern recognition, 1131-1146,(1996). [14] Mylopoulos, J.P. and Pavlidis,T., “On the topologic al properties of quantized spaces I- the notion of dimension”.

Journal of the ACM (JACM), 18(2), 239-246 (1971). [15] Mylopoulos, J.P. and Pavlidis,T., “On the topologic al properties of quantized spaces II- connectivity and order of connectivity”, Journal of the ACM (JACM), 18(2),247 - 254 (1971). [16] Xiangjian He and Wenjing Jia , “Hexagonal structure for Intelligence Vision”, Computer Vision Research Group,

University of Technology, Sydney, Australia. [17] Serra,J., “ Introduction to Mathematical Morpholog y,” Computer Vision, Graphics, and Image Processing , 35, 283- 305 (1986). [18] Yuan. C. and Her,I., “Resampling on a Pseudo hexag onal Grid”, CVGIP:Graphical Models and Image Proces sing, .336-347 (1994). [19] Yabushita, A. and Ogawa. K., “Image reconstruction with a hexagonal grid”, IEEE Nuclear Science Sympos ium

Conference Record, 3, 1500-1503 (2002). [20] Middleton, L. and Sivaswamy. J., “Edge detection in a hexagonal-image processing framework”, Image and Vision

Computing, 19(14), 1071-1081 (2001). [21] Middleton, L. and Sivaswamy.J., “Framework for prac tical hexagonal-image processing”, Journal of Elect ronic

Imaging, 11(1), 104-114 (2002). [22] Qiang Wu, Xiangjian He, Tom Hintz, “Image segmentat ion on spiral architecture”, Proceedings of the Pan -Sydney area workshop on Visual information processing , Au stralian Computer Society Inc, 11(1), (2001). [23] Wu, Q., He, X., and Hintz, T., “Virtual Spiral Arch itecture”. Proceedings of the International Confere nce on Parallel and Distributed Processing Techniques and Applicati ons, 1, 399405 (2004). [24] Luczak, E. and Rosenfeld, A., “Distance on a Hexago nal Grid”. IEEE Transactions on Computers, 25(5),53 2- 533 (1976). [25] Her, I., “Geometric transformations on the hexagona l grid”, IEEE Transactions on Image Processing , 4( 9), 1213- 1222 (1995).