In most applications of image processing data is collected and displayed in square pixels. Hexagonal pixels offer the advantage of greater rotational symmetry in addition to close packed structure and a nearly circular pixel.
For most modern display devices the shape of the pixels are square. It is due to this fact that in most applications of image processing, including computed tomography, data is gathered and arranged in square pixels. The compound eye of insects and crustaceans is made of smaller, simple eye units, called ommatidia. The rhabdome is the common area where light is transmitted to the reticular cells. Each of these cells is connected to an axon and since each ommatidium consists of seven or eight reticular cells, there are these numbers of axons, which form a bundle from each ommatidium. Each ommatidium passes information about a single point source of light. The eyes of strepsipteran insects are very unusual among living insects. Externally they differ from the usual "insect plan" by presenting far fewer but much larger lenses. Beneath each lens is its own independent retina. Anatomical and optical measurements indicate that each of these units is image forming, so that the visual field is subdivided into and represented by "chunks," unlike the conventional insect compound eye that decomposes the visual image in a point wise manner. This results in profound changes in the neural centers for vision and implies major evolutionary changes. The total image formed therefore is a sum of the ommatidia fired. This resultant image can be thought of as a series of dots, just like a computer image is composed of a series of discreet dots (pixels). The more pixels, the better the picture. The ommatidia are more hexagonal than square shaped. It is this natural occurrence that motivated me to hypothesize that hexagonal pixels would provide a better image quality than square pixels. [1]
Here's a hexagonal grid with a coordinate system mapped
to square grids. Note that this is just one possible orientation of the
hexagons--if you change it so hexes are adjacent horizontally instead of
vertically, you get a symmetric situation (the details of which i'm sure you can
work out; essentially, in (1) and (2) below, the "== " changes to a "!= ").[2]
Unlike the obvious route, these coordinates are not
orthogonal--that is, the y-coord increases to the upper-left, and the x-coord
increases to the upper-right. This means "A" has coords (2,5), B is (4,2), C =
(5,0), D =
(5,5), E = (3,3), F = (4,1) and G = (1,4). This also means that a "square" in this coordinate system is more of a diamond shape (as you can tell from the 6x6 "square" shown above). Circles, however, are reasonably circular [3,7].
A "square" or "rectangle" in the above hexagon coordinates unfortunately looks like a diamond-shape. This is fine when the boundary of your domain is irrelevant. However, it does not work out so well if you want your hexagons to fit neatly on a rectangular screen, while still keeping the information in an array. Fortunately, this is a rather simple transformation. Consider the following rectangular "patch" of hexspace, with the origin (0,0) at the upper left, and suppose you want to embed this into a 9x8 array so the upper row is at y=0, with x increasing to the right, the next row down is y=1, etc.
The idea is then to store this patch of hexspace into a 9x8 array, and be able to address hexes by their array coordinates. We need two transformations: 1. array -> hexspace given by: array2hex(x,y)= (x - floor(y/2),x+ceil(y/2)) 2. hexspace -> array given by: hex2array(x,y)= (floor((x+y)/2),y-x) Note that floor & ceiling here will need to deal with negative as well as positive inputs. Also note that this is for a rectangular patch as depicted above-if the topmost line is to be offset to the right (instead of to the left as is shown), then floor & ceil change places.
The algorithm given above computes LOS by finding a shortest, "straightest" path between two hexagons. Sometimes, though, it is desireable to compute LOS not just by trying to draw as straight a line as can be formed formed from hexagons, but by finding all the hexagons that intersect a Euclidean line drawn on the hexagonal grid. If our "line" is a infinite half-ray (ie an arrow which starts at a given hexagon but continues on forever), then this corresponds to the set of hexagons which would be "visible" by someone standing at a particular hexagon and looking in a given direction; it is the Euclidean LOS mapped to the hexagonal grid. The algorithm given above is not ideal for this purpose-it draws a "straight" line which does not deviate too much from a Euclidean line, but it does not *always* find *all* the hexagons which would intersect this line.
The brute force approach to this problem is just to go through every hexagon and calculate if a given straight line intersects the hexagon (intersection of a line and convex object like a hexagon is a simple problem, and an algorithm is given below; finding the actual intersection point is computationally more expensive), and then decide if it lies on the half-ray. This is quite wasteful, though, and it is a simple matter to restrict our intersection tests to a more realistic set, and in a way that does not actually require calculating any intersection points. We will still need functions to tell if a hexagon intersects a line, though. You could do this in many ways; here's an easy and efficient way.
This master's thesis will result in a study on the selected subject and a program written as an example according to a developed technique. The abstract presents a review material on the master's thesis which gives theory definition and explanation of the suggested technique. It presents general concepts that will assist in developing this technique.
J.P.Mylopoulos and T. Pavlidis, "On the topological properties of quantized spaces, I. the notion of dimension," Journal of the ACM (JACM), Vol.18, No.2, 1971.
R.Vitulli, et al., "Aliasing effects mitigation by optimized sampling grids and impact on image acquisition chains, "Geoscience and Remote Sensing Symposium, IGARSS '02, 2002
D. Van De Ville, T. Blu, M. Unser, W. Philips, I.Lemahieu, and R. Van De Walle, "Hex-spline: a novel family for hexagonal lattices," IEEE Transactions on Image Processing, Vol. 13, no. 6, June 2004
Laurent Condat and Van De Ville, "Quasi-Interpolating Spline Models for Hexagonally-Sampled Data," IEEE Transactions on Image Processing, Vol. 16, No. 5, May 2007
Eric Anterrieu, Philippe Waldteufel and Andre Lannes , "Apodization Functions for 2-D Hexagonally Sampled Synthetic Aperture Imaging Radiometers" IEEE Transactions On Geoscience And Remote Sensing, Vol. 40, No.12, December 2002
Lee Middleton and Jayanthi Sivaswamy, "Hexagonal Image Processing , A Practical Approach", Springer-Verlag London Limited, 2005.
J. Foley, A. Van Dam and J. Hughes, "Computer Graphics, Principles and Practice (Second Edition)". Addison Wesley, Sydney (1990).
E. Buschbeck, B. Ehmer and R. Hoy, "Chunk versus point sampling: visual imaging in a small insect". Science 286(5442), (1999).
M.Golay,"Hexagonal parallel pattern transformation," IEEE Transactions on computers, Vol 18,No.8,1969
R.M.Mersereau,"The process of Hexagonally sampled Two-dimensional signals," Proceedings of the IEEE,1979.
B.Kamgar-Parsi and W.A. Sander, III,"Quantization error in spatial sampling: comparison between square and hexagonal ICGST-GVIP Journal, ISSN 1687-398X, Volume (9), Issue (I), February 2009 32 pixels,"Computer vision and Pattern Recognition, Proceedings CVPR '89',1989.