Conversion from the hexagonal grid to the rectangular grid (part 2)

While I only provided a brief introduction about how the algorithm works in the previous post, I will now try to explain in detail how it converts a hexagonal image into a square image. For easier understanding I will also present sample images for each step.

The hexagonal image

The starting point is a hexagonally sampled image. Note that the orientation of the hexagonal grid is selected so that every pixel has a corner left and right and a flat edge on the top and at the bottom. This means that every other column is shifted by 0.5 * pixel height. Of course the algorithm can also be programmed to accept hexagonal images with a 90° rotated grid, however, I always refer to this orientation.

So, here´s the hexagonally sampled image which I will use for the demonstration:

The image is actually stored in a normal two-dimensional array. Displaying this array like a normal image using Matlab´s imshow() command looks like this:

The shift of every other column is easily recognizeable in horizontal edges. By comparing both images you can also see that the aspect ratio is different. While the upper image uses hexagonally shaped pixels and therefore has a correct aspect ratio, the lower image uses square pixels to represent the hexagonal pixels which were used in image sampling. The hexagonal grid actually has a pixel aspect ratio of 1:1.1547 while the square grid has 1:1. This means that the second image appears about 15% wider than it should.

Expand to rectangular grid

The first thing that needs to be done is to fix the pixel shift. For this, the algorithm introduces new pixels in the image to produce a checkerboard pattern.

This will - obviously - again result in an incorrect pixel aspect ratio of 2:1.1547 or 1:0.5774.

Interpolation

The next step is the most tricky one: the new black pixels need to be filled with color. Obviously, we will use the surrounding pixels to interpolate the missing values.

 

The figure above shows the center positions of the pixels which are available for the interpolation as well as the center position of the pixel for which we want to calculate the color values. As it is exactly on the border between the above and below pixel, one could assume that using only these two pixels for the interpolation would be a good approach. However, the result is rather unsatisfying:

Applying a vertical linear interpolation results in a image where horizontal edges show strong artifacts. Another approach could be to use a weighted average of horizontal interpolation and vertical interpolation. The weights should represent the distances between the pixels on the horizontal and vertical axes, respectively. Therefore the vertically interpolated value needs to be weighted 1.7321 times stronger than the horizontally interpolated value.

In fact, the image looks even worse than the vertical-only interpolated image. Here, not only horizontal edges, but also vertical edges show strong artifacts. 

The solution is adaptive interpolation. The algorithm has to find whether horizontal interpolation or vertical interpolation leads to the best result. Therefore, it needs to analyze the image. It does this by analyzing each pixel´s neighbourhood in horizontal and vertical direction. The differences of a pixel´s values and those of its neighbours in each direction are stored in a map as displayed below.

Here you can see red areas where there are vertical edges and blue areas where there are horizontal edges. This map will then be blurred and finally used as a basis to decide if a pixel´s values shall be taken from the horizontally interpolated image or from the vertically interpolated image.

The combined image will then look like this:

Fixing the aspect ratio

Finally, the aspect ratio needs to be fixed. There are two options to do this: either stretch the image horizontally or squeeze it vertically. The results are as follows:

The horizontally stretched image measures 154*237 pixels (compared to the hexagonally captured 89*118 pixels). The total pixel count is more than three times higher than the pixel count of the captured hexagonal image.

The vertically squeezed image measures 89*136 pixels an has roughly 15% more pixels than the original hexagonal image. It appears less processed than the stretched image, but when having a closer look you will find that quite some detail is missing compared to the stretched image.

Code

hex_to_rect.m
This file contains the Matlab code to do the conversion. Feel free to use it and improve it. I will be happy about your feedback.