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.[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".[3] Frederic 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).One of the resampling techniques to obtain hexagona l grid is to suppress alternate rows and columns fr om the square * Email : fayas.a@tu.edu.sa , nisar@computer.org , aljahdali@tu.edu.sa , 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.[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).[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).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.[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).[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".(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).[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).[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.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).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.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).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.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.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.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.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.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).Once sampling lattice is digi tized into hexagons, various image processing operations can b e performed on these sub-sampled images.Implem entation of Hexagonal grid can be done in various methods inclu ding the spiral addressing scheme.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.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 .Lack of capturing and display devices in hexagonal grid mak es it impossible to attain the benefits of hexagona l grid.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.3 FEATURES OF HEXAGONAL SAMPLING SCHEME Digitization is one of the hardest tasks which scie ntists were worried about in image processing.Vitulli also found out that using the hexagonal grid, wider spectra of signal c an be sampled without aliasing with fewer amounts of samples.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 .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.6 CONCLUDING REMARKS From the above discussions and explanations it as c lear that there will be improvement while processin g with hexagonal sampling.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.Hexag onal grid is also a pixel tessellation scheme which is efficient than a ny other schemes.But all of t he methods are simulations only and thus we cannot achieve the rea l advantages of the hexagonal grid.Many resampling techniques were proposed like brick wall , quincunx sampling, least squares approximation of splines, etc 3 .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.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.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.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 .5 HEXAGONAL STRUCTURE ADDRESSING Till we have discussed about representing and mimi cking the hexagonal pixels to simulate the hexagona l grid.5.1 2-Axes coordinate addressing scheme Luczak and Rosenfield 24 , proposed the two axes oblique coordinate system ( Fig 4) to address hexagonal structure.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.' 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.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.There is no inconsistency in pixel connectivity and thus angul ar resolution is higher in this arrangement.Applying hexagon al grid in image processing is very advantageous and easy for mimicking human visual system.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.The fol lowing section describes the various features of hexagonal sampling scheme.Due to this limitation researchers are trying to mimic the hexa gonal grid on rectangular grid itself.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.3.6.3/2.4.2.If ' ?