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

In an earlier post I proposed a method to create hexagonally sampled images in order to overcome the problem of missing hexagonal image sensors. In this article I want to show you how to convert a hexagonal image into a rectangular image.

The algorithm quickly explained

First of all the algorithm expands the hexagonal image in vertical direction by introducing black pixels between the existing ones. The goal is to have a grid without 0.5-pixel shifts, as we have it in the hexagonal grid. After stretching the image, we have a checkerboard pattern.
The next step is to interpolate the values at the new pixel positions. There are various ways to do this. The easiest would be to use bilinear interpolation. However, I found that with a non-adaptive interpolation you will still be able to recognize the hexagonal pattern in the final image. This is why I designed the algorithm to first create two candidate images, one horizontally interpolated, the other vertically interpolated. After that the algorithm decides at every pixel position from which of the candidate images to take the color values.
After that you end up with a fully interpolated image with a weird pixel aspect ratio. You can now stretch or squeeze the image to achieve a pixel aspect ratio of 1:1. Horizontal stretching will make the resulting image much bigger than necessary, vertical squeezing may result in loss of information (even though the pixel count will still be higher than that of the original hexagonal image).

Sample images

Below there are some processed images. The left image is the hexagonally sampled image. The middle image has a rectangular grid, it is derived from the left image. The image to the right is a square sampled image for comparison.

Pixel count

It is quite obvious that the middle column (rectangular grid, derived from hexagonal grid) has much more pixels than the right column (square sampled images). This is due to the nature of the conversion. Of course, the rectangular image can be resized to have the same resolution as the square sampled image. However, this might result in loss of information. So, in order to keep as much information as possible in the images, I decided to leave them at the higher resolution.

Skewed edges

The higher resolution actually doesn´t bring much visible detail. Instead it makes the image look smoother. However, in some of the test images you may see that skewed edges look better in the middle column than in the right column. It is not so obvious in the posted examples, but hexagonal sampling has advantages in rendering skewed lines and also with high vertical frequencies (provided that you use the same orientation of the grid as I do). This is because on the hexagonal grid every other column is shifted by 0.5 pixels. This allows to introduce sub-pixel interpolation and achieve some gain in vertical resolution. However, the effect is only visible in few situations.

Artifacts

The conversion algorithm decides at every sub-pixel location whether to interpolate horizontally or vertically, depending on the surroundings. In some situations, especially when there´s a lot of fine detail, it happes that the algorithm makes a wrong decision which leads to visible artifacts (an example for that is the tree in the 'lake' image). However, all the images have been sampled without anti-aliasing filtering. In real world applications the situations in which artifacts are introduced would be much less. But anyway, there is room for improvement.

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.

In part 2 I explain in more detail how the algorithm works.