Abstract
Nature-inspired computing has been a real source of motivation for the development of many meta-heuristic algorithms. The biological optic system can be patterned as a cascade of sub-filters from the photoreceptors over the ganglion cells in the fovea to some simple cells in the visual cortex. This spark has inspired many researchers to examine the biological retina in order to learn more about information processing capabilities. The photoreceptor cones and rods in the human fovea resemble hexagon more than a rectangular structure. However, the hexagonal meshes provide higher packing density, consistent neighborhood connectivity, and better angular correction compared to the rectilinear square mesh. In this paper, a novel 2-D interpolation hexagonal lattice conversion algorithm has been proposed to develop an efficient hexagonal mesh framework for computer vision applications. The proposed algorithm comprises effective pseudo-hexagonal structures which guarantee to keep align with our human visual system. It provides the hexagonal simulated images to visually verify without using any hexagonal capture or display device. The simulation results manifest that the proposed algorithm achieves a higher Peak Signal-to-Noise Ratio of 98.45 and offers a high-resolution image with a lesser mean square error of 0.59.
Introduction
In the fast-growing field of computer science and technology, natural computing has become a promising solution for upcoming researchers. Nature Inspired Computing (NIC) has inspired from the natural world led to many innovative algorithms and computations [1]. To bring a revolution in the application of computer vision, many extensive works are progressed in the hexagonal tessellation lattice. NIC methods are more flexible, robust, fast deliverable, easily understandable, and adaptable. Consequently, it is utilized to solve a broad range of computations and applications.
In order to replicate the characteristics of the Human Visual System (HVS), it is very significant that the spatial arrangement of machine vision sensors should be arranged based on the arrangement of high-density cones and rods in the human fovea. Nevertheless, today’s practical world adopts rectangular meshes rather than hexagonal meshes due to the ease of hardware implementation, availability, and familiarity with the cartesian coordinate system. There is a strong connection of hexagonal geometry with the human visual system as hexagonal pixels fit the shape of human fovea [2] as illustrated in Fig. 1. Moreover, the hexagonal lattice has typically seen in nature such as beehives, dragonfly eyes, bubble rafts, etc., [3].
Photoreceptor cons and rods in human fovea.
A brief description of how the picture is taken by the human eye is as follows. On the posterior portion of the eye, the retina is a thin membrane (or tissue). The major aim of the retina is to capture the light data and transform them into neural signals that can be sent to the brain for further visual processing. The fovea is a small retinal area whose structure comprises highly dense hexagonal-shaped rods and cones that are placed on a hexagonal grid. This kind of spatial arrangement in hexagonal lattice provides added advantage over the square lattice when it comes to detecting straight and circular edges with higher accuracy [4].
Given a 2-D image, in many instances, it is of a prominent challenge to build up a spatial domain structure that resembles HVS to achieve a real-time performance [5]. Rectilinear square mesh is generally used in camera sensors and display screens due to its ease of implementation in the cartesian coordinate systems and its orthogonal nature. But wherever the symmetric geometric computation between contiguous neighboring pixels is required, the square mesh does not satisfy this requirement. Even though commercially dedicated machinery visual sensors are trying to approximate photoreceptor densities seen in primate retinas, they can’t still reach and outperformed by HVS in terms of the wide range and the processing capabilities at the sensor level. This stimulus has given rise to the recent research about biological retinas to collect more information regarding the processing strategies with the ray of hope to the design and development of ideal visual sensors [6]. In practice, various lattice systems are accessible such as squares, triangles, and hexagons [7] as depicted in Fig. 2. These tessellation schemes allow us to tile a plane without any overlap and vacant spaces between them. All other spatial arrangements of tessellation will follow an uneven distance between neighborhood pixels and overlap between samples.
Common tessellation schemes a) square b) triangle c) hexagon.
Figure 2 a) illustrates the most common and simple tessellation that aligns with the cartesian coordinate system. Figure 2 b) is the triangular tessellation which is having a higher packing density than the square tessellations. Figure 2 c) is the hexagonal tessellation which is regarded to be the most efficient tessellation scheme that aligns with the HVS. It has many geometrical advantages like consistent neighbourhood pixels, higher packing density, equidistant neighbourhood connectivity, and better angular correction. Furthermore, the additional benefit of this geometric arrangement is derived from human anatomical thought of the primate’s perspective [8].
On the 2-D image frame, the image forms a group of hexagonal pixels, and this arrangement results in the sharp vision for capturing information. In addition to imitating the characteristics of the human retina, the hexagonal grid comprises other geometrical advantages such as the representation of curved structures more accurately, equidistance to the neighbouring pixels, and improved spatial isotropy for the efficient implementation of circular kernels which leads to the increase in accuracy when detecting both curved and straight edges [9]. Hexagonal architecture has arranged in a set of 7 hexagons whereas conventional square architecture exhibits 3×3 matrix units as demonstrated in Fig. 3.
Pixel architecture a) hexagon b) square.
The cartesian coordinate system can address only traditional square lattice images only. Hence, the hexagonal grid image system needs a proper coordinate system for efficient addressing and storing the data. Different dominant addressing schemes to deal with the hexagonal structure are two –axes oblique coordinate addressing scheme [10, 11], three–coordinate symmetrical coordinate frame, and a single indexing scheme as shown in Fig. 4.
Addressing schemes a) two-axes oblique b) three coordinates symmetrical *R3 c) relationship between *R3 and R3 d) single indexing-spiral architecture.
Using a two-axis oblique coordinate system, an ordered pair of vectors is employed to represent each hexagonal pixel in both horizontal and vertical direction as depicted in Fig. 4a. This system has the following advantages: (i) Complete - In 2-D space, a point can be represented efficiently and accurately; (ii) Unique - An exact ordered pair coordinates can be assigned to a point representation; (iii) Convertible - It is similar to the cartesian coordinate system and can be easily transformed to and from the co-ordinate system. In [12], the three-axis coordinate frame has been introduced and is also referred to as a symmetrical hexagonal coordinate frame. This coordinate frame uses three coordinates x, y, z as shown in Fig. 4b, and there exists a one-to-one mapping of a symmetrical hexagonal frame (*R3) and three-dimensional cartesian frames (R3) as shown in Fig. 4c. Any three-pixel coordinates follow the relationship which is given by Equation (1). The distance between the neighbouring pixel is unit distance.
Owing to the close and adjacent relationship between symmetrical hexagonal coordinate frame and three-dimensional, all geometrical transformation and theoretical explanation can be conveniently transferred to and from *R3 to R3. The structural symmetry property can be efficiently preserved in this scheme.
Spiral addressing is another way to represent the hexagonal structure based on a Hexagonal Discrete Fourier Transform (HDFT) method [13]. Hexagonal pixels are arranged in spiral clusters where each pixel having consistent 6 neighbouring pixels. The basic step in spiral addressing is the numbering each hexagon with a unique address from the middle of the image in raised powers of seven in a spiral curve pattern as shown in Fig. 4d. Primarily, the address has been applied to a group of 7 hexagons labelled consecutively like 0, 1, 2, 3, 4, 5, and 6.
As illustrated in Fig. 5, the structure can be dilated to place additional 6 hexagons consecutively and each address is multiplied by 10. For each newly installed hexagon, an address will be provided with respect to the centre pixel address as performed for the first seven hexagons. After that, the hexagons numbered form the cluster of size 7 n (n = 1, 2, 3, . . .). A one-dimensional addressing scheme with a collection of 49 pixels is exposed in Fig. 4d. This architecture provides an additional benefit of fixing the centre of the image at the origin and consistent 6-neighbourhood connectivity which is helpful for numerous computer vision applications.
Cluster of basic seven hexagonal cells.
In this paper, 2-axes oblique co-ordinate system has been exploited to simulate the hexagonal grid. It will effectively make use of existing hardware implementation. The major outperforming contribution of this paper is as follows: A new 2-D Interpolation Hexagonal Lattice Conversion (2IHLC) algorithm has been developed to attain an effective hexagonal mesh framework. This framework design will be employed for several image processing and computer vision applications. An appropriate development of pseudo-hexagonal structure in the proposed 2IHLC algorithm yields a better peak signal-to-noise ratio, and a lesser mean square error. More than 98%of the pixel contributes to the pseudo-hexagonal structure framework simulation and higher resolution images are obtained in the proposed 2IHLC algorithm.
The organization of this research article is as adhered. Section 2 summarizes the literature description of hexagonal image processing. Section 3 describes the hexagonal image lattice, representation, and processing. Section 4 states the proposed 2IHLC algorithm. The results and discussions are demonstrated in Section 5. Finally, Section 6 deals with a conclusion and all possible future work.
While there are obvious advantages of using hexagonal images, the dearth of the utilization of hexagonal lattice is mostly attributable to the inadequacy of hardware devices, including both sensors for collecting hexagonal images and devices for displaying them. In order to continue research advancements in this technology using the existing hardware, there is a need to build an effective resampling strategy so that we can benefit from the advantages that hexagonal lattice offers for the processing of images.
The Linear Hexagonal Resampling (LHR) technique can be determined to make it ready for display and processing using existing hardware devices [14]. The pixels in a real hexagonal structure are not organized in a spiral pattern. Instead, various addressing schemes and coordinate systems are introduced to simulate hexagonal grids [15, 16]. In this section, the details of hexagonal sampling and numerous resampling methodologies are illuminated to enable the conversion of square lattice to the hexagonal grid.
Hexagonal sampling
According to [17], a rectangular space sampling is not desirable because it has many disadvantages, such as spatial resolution varying with direction. As a result, the best sampling pattern will be a normal hexagonal pattern. Hexagonal sampling is considered as the best sampling scheme for signals that are band-limited over a circular region of the Fourier plane since the exact reconstruction of the waveform requires a lower sampling density than alternative schemes as shown in Fig. 6. For such signals, the hexagonal sampling use 13.4%fewer samples than rectangular sampling.
Different sampling schemes a) rectangular sampling b) hexagonal sampling.
a)Alternate Pixel Suppressed (APS) Method
According to [18], the hexagonal grid upon rectangular grid can be obtained by alternatively vanquishing horizontal rows and vertical columns of the pre-existing rectangular grid. The equation for sub-sampling is as follows:
In this method, there is no one-to-one correspondence between the pixels in the hexagonal grid and rectangular grid as some of the pixels are suppressed. Zero values are assigned to the suppressed pixels. While doing the computations with the sub-sampled images, the suppressed pixels are not taken into account. Therefore, new sampled images have only a quarter of a pixel compared to a rectangular grid as depicted in Fig. 7.
Mesh formation a) rectangular mesh b) sub-sampled hexagonal mesh.
b) Half-Pixel Shift (HPS) Method
The HPS method has been introduced to addresses the hexagonal lattice issues like imperfect hexagonal shape, lower intensity, and smaller resolution [19]. It is evaluated by applying the overlaps strategy between square and hexagonal pixels where these overlaps are framed mathematically using 8 separate circumstances. Every overlap scenario has sensed automatically and utilized to calculate the final hexagonal intensity. For each odd line, the midpoint is computed through simple interpolation equation (i.e., mid = (left _value + right _value)/2), discarding the left-most and right-most values, retaining only mid-point values. The hexagonal mapping equation is as follows:
The hexagonal sampling scheme offers several features as compared with existing schemes. Some of them are as follows:
More efficient sampling scheme
Aliasing is referred to as a process of insufficient sampling rate which leads to undesirable effects in the recovered signal. In [20], they investigated the fact that lesser samples are necessary for the regeneration of wave number limited input signal in hexagonal grid. Using this, the fundamental inference is that, the square lattice is not an efficient sampling scheme. Consequently, when using the 2-D isotropic function, the rhombic hexagon (1200) is considered as an effective sampling lattice as illustrated in Fig. 8. Here, the spacing between the sampling points is given by
Sampling lattice for a) circular function b) isotropic function.
Quantization error is a vital parameter to calculate the merit of the layout of different available sensors. The authors in [21, 22] developed an equation for calculating quantization error in hexagonal sampling lattice and proved that lesser quantization error can be achieved in comparison to square sampling lattice as depicted in Fig. 9.
Spectral packaging for a) square and b) hexagonal.
One of the fundamental concepts in digital image processing is the connectivity between the pixels. Two pixels are said to be connected, if they are neighbours and if they satisfy the specified condition of similarity [23]. In the case of a square grid, there is two-pixel neighbourhood. We consider the pixels are connected if they share a common edge or when they possess a common corner.
Accordingly, the square grid is having 4-neighbourhood and 8-neighbourhood pixels as illustrated in Fig. 10a and 10b. But in the case of the hexagonal grid, there is no choice of connectivity [24, 25]. We can define only, 6-neighbourhood connectivity and the neighbouring pixel share only one common edge and two common corners as illustrated in Fig. 10c. Due to the unavailability of choice of connectivity, many image processing as well as computer vision algorithms can be easily and efficiently implemented. The neighbourhood connectivity for the hexagonal grid is consistent and fixed to 6-way connectivity.
Neighbouring pixels in (a,b) square lattice, (c) hexagonal lattice.
In the conventional square lattice image, there are two different types of distance measures are taken into account [26–28]. The distance calculated between the adjacent pixels in the diagonal orientations is √2 times the corresponding horizontal orientation as shown in Fig. 11a. In the hexagonal grid, every hexagon is having consistent 6 neighbours and all are equidistant from the centre pixel along the six sides of the pixel as represented in Fig. 11b. Due to these features, the hexagonal sampling will be considered in the proposed 2IHLC algorithm and it is explained in the following section.
Distance measure for a) square b) hexagon.
The resampling as well as conversion of square latticed images to hexagonal latticed image is mandatory in proposed 2IHLC algorithm. In this new technique, each pixel is represented by a n × n pixel block. The sub-pixel hexagonal image is employed for processing of image in virtual hexagonal environment. The flow of converting the square grid image into hexagonal grid image with the aid of proposed algorithm is depicted in Fig. 12. It utilizes the benefit of hexagonal image processing that can be directly used in the today’s world, where it lacks the availability of hexagonal image sensors.
Processing of hexagonal images in proposed method.
Sub-pixel clustering effect is produced in the resampling process, which limits the loss of resolution effect. A 6×6 block of pixels represents each hexagonal pixel. Selection of the number of pixels that form the hexagonal pixel is collected separately and it is focused on two policy issues such as: Arrangement of pixels should allow tessellation extraction without overlap and there are no gaps between the six-dimensional neighbours pixels; Collection of pixels should resemble hexagons. For instance, Hexagonal pixel lattice should adhere to the properties of the geometry.
Hexagonal image simulation in proposed method is typically achieved by resampling rectilinear square pixel centred images using pseudo software simulation. From a group of square sub-pixels, the proposed algorithm generates hexagonal pixels where each pixel is represented by n × n pixel block in order to enable the sub-pixel clustering and attain same resolution. For example, in Fig. 13, each pixel of the given image is represented by a 6×6-pixel block with same intensity as that of the original square grid image is used for the construction of hexagonal image. Square pixels which are used to create six pixels labelled as ‘1’ with the remaining pixels labelled as ‘0’ discarded.
Hexagonal pixel arrangement from square pixel.
All square pixels in the input image can be transformed to hexagonal pixels using this method. Further, all hexagonal pixel clusters are arranged on the square grid as exposed in Fig. 14. The pixel-coloured yellow shows first row first column A (1,1) and pixel-coloured green implies first row first column A (1,2). Similarly, all the pixels are numbered like above where A represents the hexagonal structured image.
Collection of hexagonal pixels.
The complete square pixels can be converted to pseudo hexagonal pixels through Algorithm 1. It utilizes a 2-axes oblique coordinate system that follows the row-column addressing so that we can make use of existing hardware to process the image. The row-column addressing in the proposed 2IHLC algorithm follows in a similar way to the familiar Cartesian coordinate system. Besides, the proposed method of hexagonal pixel simulation can also be employed on colour images.
As the colour image consists of three channels, the proposed algorithm should be applied two-three (RGB) channels separately and superimpose these results. The proposed hexagonal grid possesses the same symmetry in 00, 600, and 1200. This higher symmetry makes many image processing and computer vision applications more beneficial. For example, if the images are rotated on a hexagonal grid, more information of the image will be retained by the proposed 2IHLC algorithm when compared with the square grid.
The effectiveness of the proposed 2IHLC algorithm has been evaluated in the Python platform and its system specification is demonstrated in Table 1. The performance of the proposed method is compared with the HDFT [13], LHR [14], APS [18], and HPS [19] methods in terms of Peak Signal-to-Noise Ratio (PSNR), Average Information Content (AIC), Mean Square Error (MSE), Average Running Time (ART), and Contrast Enhancement Index (CEI).
System Specification
System Specification
The comparative performance of these methods is enumerated in Table 2. To ensure that the comparisons were fair, all the methods have a similar network models as well as mapping strategies. Figure 15 and Figure 16 demonstrate the grey-scale image and color image with pseudo-hexagonal pixels simulated using the proposed 2IHLC algorithm. The pseudo hexagonal pixels can be seen in the zoomed view. Lena.jpg and fruits.jpg of different sizes are utilized for the proposed algorithm and verified.
Comparitive Analysis of Different Methods
Simulation results of grey scale image uing proposed algorithmn a) with hexagonal pixels b) with square pixels c) another zoomed version of hexagonal pixels d) and e) higher zoomed version of hexagonal pixels.
Simulation results of color image using proposed algorithmn a) with hexagonal pixels b) with square pixels c) zoomed view of hexagonal pixels.
From the Fig. 15 16, it is evident that the images simulated by the proposed algorithm provide equidistant, consistent connectivity pixels and high-resolution images. This is owing to the execution of efficient pseudo software simulation in the proposed 2IHLC method. It utilizes a 2-axes oblique coordinate system which follows the row-column addressing to process the image. Besides, the formation of hexagonal structure pixel in the proposed 2IHLC method follows high symmetric property where this higher symmetry makes many image processing and computer vision applications more beneficial.
Typically, the input images are utilized for simulation may be corrupted owing to noise and hence the evaluation of PSNR is required to quantify the presence of noise in the image. PSNR can be expressed as follows:
According to Fig. 17, it is evident that the proposed 2IHLC method yields a higher PSNR value as compared with existing methods under varying image sizes. In particular, the proposed 2IHLC still acquires with 96.8 PSNR value at the larger grey-scale image, whereas the HDFT method obtains 80 PSNR value only. The PSNR value of 2IHLC has enhanced by 14%, 13%, 11%, and 8%as compared to HDFT, LHR, APS, and HPS methods respectively.
PSNR comparison for various methods under varying image sizes (a) Grey-Scale Image; (b) Color Image.
The rationale behind the PSNR enhancement is the consideration of the equidistant neighbourhood pixels and consistent connectivity from the centre pixel of the proposed method. This consistent connectivity reduces the noise components in the output image which paves a way to yield a noise-free result during the training phase. Furthermore, the pseudo hexagonal pixels in the proposed method produce the output color images with higher pleasant quality. In contrast, the existing methods did not preserve the consistent connectivity that causes undesired artefacts and degrades the image quality.
The AIC of an image has been determined approximately from the simulated images. In general, a higher value of AIC denotes richer information of content and AIC can be calculated by
From Table 3, it is clearly manifest that the proposed 2IHLC method achieves maximum AIC value for both grey-scale and color images. In the case of color image, the proposed 2IHLC method maintains a higher AIC value of 7.62, whereas the HDFT, LHR, APS, and HPS are having 6.40, 6.68, 6.75, and 7.22 AIC respectively. This results owing to attaining an effective hexagonal mesh framework in the proposed 2IHLC method. The effective framework preserves the actual content more efficiently without loss any significant information. Additionally, more than 98%of the pixel contributes to the pseudo hexagonal structure framework simulation that leads to obtaining higher resolution images in the proposed 2IHLC. On the other hand, existing methods exploited complex conversion algorithms to retrieve the original information. They lose many valuable information while processing the high-resolution images.
Comparison of AIC results for different methods
MSE is generally used to estimate the quality of the image where the higher value of MSE infer that large variation between the input image and hexagonal simulated image. It can be calculated as follows:
It is apparent from Fig. 18 that the proposed 2IHLC outperforms well as compared with existing methods for varying image sizes. The lower value of MSE is obtained by the proposed method because the variation between the input image and the hexagonal simulated image is smaller. Evidently, the proposed 2IHLC method achieves lesser MSE by 46%, 42%, 41%, and 39%as compared to HDFT, LHR, APS, and HPS methods respectively.
Comparison of MSE for different methods (a) Grey-Scale Image; (b) Color Image.
The key reason behind the smaller MSE is the employment of the simpler operation on the whole image. Besides, the proposed 2IHLC does not require any interpolation filters for image enhancement. This leads to attain lower quantization error and sustain the simulated image with its natural appearance. Alternatively, the Gabor filter is necessitated in the APS and HPS methods for the pre-processing stage. This kind of filters yields more quantization error throughout the image and hence they elucidate a higher MSE value when compared with the proposed 2IHLC method.
According to Table 4, it is manifest that the proposed 2IHLC needs a lesser ART than APS and HPS methods. The ART value of the proposed 2IHLC has reduced by 22%, 19%, 14%, and 7%as compared to HDFT, LHR, APS, and HPS methods respectively. In the case of a larger size color image, the proposed 2IHLC method still preserves a minimum ART value of 25.25 ms, whereas the HDFT, LHR, APS, and HPS are having 33.07 ms, 30.98 ms, 29.89 ms, and 27.96 ms ART respectively. This is due to the fact that the proposed 2IHLC method operates with limited conversion parameters during the training phase. As a consequence, it necessitates lesser ART for managing the hexagonal structured image and supports for high-resolution images. This pseudo hexagonal structure maintains clarity in both grey-scale and color images. On the contrary, the existing methods exploit a more number of parameters for simulating the images. They do not evaluate the optimum learning rates for each conversion parameter which requires higher ART and produces a more complex structure.
Comparison of ART (msec) results for various methods
Comparison of ART (msec) results for various methods
CEI is one of the significant quantitative metrics for evaluating the contrast improvement of an input image and it is estimated by
Analysis of CEI for various methods under varying image size (a) Grey-Scale Image; (b) Color Image.
In this paper, a new and effective 2IHLC method is implemented in which hexagonal pixels are generated and allow the geometrical symmetry not only to contiguous neighbouring cells but also to the higher-order neighbouring cells. Even though the proposed 2IHLC method is not employing any interpolation filters for image enhancement, the image resolution has been retained and the percentage of unused pixels is very negligible. A highly parallel and real-time simulation is possible in the proposed method owing to consideration of equidistant neighbourhood pixels and consistent connectivity from the centre pixel.
The effectiveness of the proposed 2IHLC algorithm has been evaluated in the Python platform and results clearly manifest that the proposed method outperforms well as compared with existing state-of-the-art methods. In particular, the PSNR value of the proposed 2IHLC has enhanced by 14%, 13%, 11%, and 8%as compared to HDFT, LHR, APS, and HPS methods respectively. This higher PSNR value proves that the proposed method effectively retained the original information from the simulated images. It is capable to produce noise-free images and work accurately even for high-resolution images. Nevertheless, the proposed method has lack of hexagonal imaging and display device. Also, the memory is intensive with high-quality representation of images. In future work, the hex-convolutions will be introduced on hexagonally resampled images. It will also address the different addressing schemes for memory-efficient computations.