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.

Sample Images

In my previous posts you may have seen some sample images which I used to demonstrate certain issues or the result of a certain image processing algorithm. Maybe you wondered where these images come from. Well, it depends on what I am trying to achieve an what I use the images for.

Testing performance of real programs

When I examine how different programs process images, I naturally have to use source images in a special format from an origin that is supported by the program. When I investigate the quality of the demosaicking in a certain program, then it doesn´t help to use a PNG with monitor color space as a test image. In this case I use Raw image files which I typically download from the internet. A good source for such files is dpreview.com. They provide sample images of a huge number of different cameras in Jpeg and Raw format.

Sometimes I also use picture which I took with my own camera. 

Testing performance of self-written algorithms

This is something completely different. For testing my own algorithms I don´t want to use Raw image files which have a custom header and the actual information stored in a weird way. Using such files would require special knowledge about the file format and color reproduction. For this purpose it is much easier to use files which can be easily opened in Matlab and which use the monitor´s color space so you don´t have to mess around with converting colors. One good option for this is the Kodak image set which is used for almost every paper on image processing.

You can download the image suite from http://r0k.us/graphics/kodak/

Another very good source is ARRI. They provide a set of image sequences shot with their professional camera ARRI ALEXA. The files are available in TIFF format in monitor color space and as raw sensor data (Bayer) stored in TIFF files as well. Using TIFF as a container makes it very easy to use these files in your applications. They even share some Matlab code to convert the colors from the sensor´s color space into the monitor´s color space.

Refer to the paper BEYOND THE KODAK IMAGE SET: A NEW REFERENCE SET OF COLOR IMAGE SEQUENCES. The abstract already contains the credentials for ARRI´s FTP server to download the files.

hexagonal resampling

Introduction
Hexagonal image processing is a somewhat exotic part of imaging science. Digital images are typically considered as a number of pixels arranged in a square lattice. This is actually not predefined by nature, it is just the easiest way to describe two-dimensional data - which images are. Another way of representing such two-dimensional data is in the form of hexagonal lattices. There are actually scientists who have shown that hexagonal sampling is more efficient than square sampling. There are also scientists who investigated the performance of certain image processing algorithms on square and hexagonal lattices to prove that hexagonal sampling also enhances computational efficiency. What I found in most of these papers is that the authors typically don´t spend much time for the gathering the hexagonally sampled images. The biggest problem in hexagonal image processing currently is that there is no way to capture images on a hexagonal lattice, simply because there exists no such image sensor. So the only way to process hexagonal images is to create them artificially. In this article I will propose a method to create hexagonally sampled images.

Method

There are rather simple ways to create hexagonally sampled images from square sampled images. You could for example stretch the square sampled image using a simple interpolation method and then ignore every other pixel so that you end up with a virtual hexagonal grid. Other similar methods are used in the existing literature. What is common to all of them is that they try to convert the square sampled image into a hexagonally sampled image with approximately the same pixel count. This is actually a process which will always introduce loss of information and it is a very poor approximation of hexagonal sampling. What these approaches ignore is the fact that hexagonal sampling not only requires a hexagonal lattice, it also requires hexagonal shaped pixels. You can´t simply take a square pixel, put it into a hexagonal grid and call it a hexagonal pixel. So, what I propose is a resampling algorithm which imitates 'real' hexagonal sampling. Real image sampling means that there is a natural scene which reflects light into a camera´s lens. The lens may introduce some distortion which limits the spatial resolution of the image. Then the light hits the sensor surface to create a projection of the scene in front of the lens. This projection is band limited (because of the lens) but still continuous. The sensor is separated into pixels which will then do the sampling. This is the process that needs to be imitated in resampling. Obviously, we don´t want to use a natural scene, nor a lens or a physical sensor. So our starting point is the projection of the scene on the sensor´s surface. Unfortunately we can´t imitate a continuous image because this would have to have unlimited resolution. But as an approximation we can use an image with very high resolution and then sample it with rather low resolution. Still, this method is just an approximation, but it is far better than putting square pixels on a hexagonal grid. The greater the ratio between the input image and the output image the better the approximation. Typically, for testing image processing algorithms it is sufficient to use images with a few hundreds of pixels in each direction. By using an input image taken with a modern camera you can easily achieve ratios of about 10:1. If you are satisfied with smaller images or you need a better approximation, you can still increase this figure.

Algorithm

My algorithm takes an SquareImage and a ShrinkFactor as input parameters. The SquareImage is of course the high-res source image, the shrink factor is the ratio for subsampling. With a shrink factor of 10 the output image would be roughly 10 times smaller than the input image (the pixel count will be about 1/100 of the input image). It is not exactly 10 times smaller because of the fact that the aspect ratio of the hexagonal grid is different than for the square grid. A hexagonal image will have about 7% more pixels on the horizontal axis and 7% less on the vertical axis (note that this depends on the direction of the hexagonal grid). If you would use an 2880x1620 input image and set the ShrinkFactor to 10, then the output image would be 309x150. You might recognize that also the area is not exactly 1/100. This is because the hexagonal grid´s borders will never exactly match with the source images borders. In fact you will lose a view pixels at the borders of the image.

The algorithm crops hexagonal tiles out of the input image, calculates their mean value and inserts this value into the output image at the correct position. In order to crop these hexagonal tiles, I use a mask with a hexagonal shape with an area of 625. A square with a width of 25 has the same area. This makes it easy to create a square sampled image with the same pixel size to compare it with the hexagonally sampled image. In order to achieve the intended ShrinkFactor, I increase the image´s size using bicubic interpolation before resampling.

The code is designed with a lot of loops. This doesn´t look good and increases the time required for the operation. However, it helps saving memory. When working with big input images this can be an issue.

HexResampling.m

Hexagon25.png

HexResampling.m is the Matlab source file. Hexagon25.png is the mask which is required to create the tiles of the image.

Below are some examples. The images on the left side are hexagonally sampled with my algorithm. The images on the right side are created by square sampling the same input image with the same pixel size.

Demosaicking Algorithm for the X-Trans Color Filter Array

In my last post I showed that ACDSee´s demosaicking algorithm for X-Trans images has a few issues. Well, interpolating the X-Trans color filter array (CFA) is not as easy as interpolating a Bayer CFA, simply because the X-Trans CFA is much more complex. However, Fuji (inventor of the X-Trans CFA) claims that their layout can outperform the Bayer CFA in terms of image quality. Obviously this is only true when applying a demosaicking algorithm which is sophisticated enough to really handle the CFA.
Some time ago in 2013 I wrote my own demosaicking algorithm for the X-Trans CFA as part of my master thesis. Actually the goal of the thesis was to compare various CFAs which is not so easy because the quality of the resulting image does not only depend on the used CFA but also on the used demosaicking algorithm. But I don´t want to bother you with this here. Instead, I want to share my algorithm. I have written it in Matlab. Below you will find the links to the source files.

XTrans_to_RGB.m
RGB_to_XTrans.m
Test.m

I have to say I´m sorry for the missing comments in the source files. Let me briefly explain how it works. Best is to start with the test.m file. You can use it to load an RGB image and convert it into an X-Trans image (RGB_to_XTrans) or to load a tiff which contains the raw sensor data. The program is not ably to directly read *.RAF files. I used DCRaw with the options '-E -T -4' to convert the *.RAF into a 16bit TIFF.
After loading the image file, it will be converted into a full RGB image. No color correction will be applied to the image, this is why RAW files will appear dark after they have been processed. If you use RGB images for testing, however, then the result should be fine.
Below you'll find some processed test images (top) and the original image (bottom) to compare.




Well, decide for your own, but I think the quality is pretty good and for sure better than what ACDSee can achieve. But it´s not perfect. Let me discuss a few issues:

• The images have a strange pattern on their edges. This is not really a problem of the algorithm. It´s simply because my algorithm is just a prototype and I didn´t care about the edges. Maybe this is also what happens in ACDSee´s processing (but theirs is not a prototype). It could easily be fixed by adding a few pixel rows/columns before demosaicking and crop them afterwards.
• Loss of detail, e.g. in the grass in the first image. Well, of course. I can´t do magic.
• Strange colors on fine details, e.g. on the trousers of the driver in the foreground in the last image or in the water in front of the boat in the second image. The X-Trans CFA has a rather low color resolution. Without pre-filtering the image we should expect to see things like these. Maybe it is possible to fix it by tweaking the algorithm (e.g. increase the number of runs for the alias canceling), however, there´s always a tradeoff. Fixing this issue will most probably result in bleeding colors (like in the 'numbers' image in my last post).

Let me add a few words on how the algorithm works. I basically use the main principles of Hirakawa´s 'Adaptive Homogeneity-Directed Demosaicing Algorithm'. First, I interpolate the green channel in for directions (horizontally, vertically, and 2x diagonally). After that I interpolate the red and blue channels in the same way. For this I exploit the interchannel correlation. The result are four candidate images. In the next step I rate at every pixel location from which candidate image to take the RGB values to construct the final image. After that I add some alias canceling to suppress color seams. That´s it.

Feel free to play around with my algorithm. I will be happy about every feedback. Please don´t use it commercially!