Pims Labs

In my previous post, Firefox Native Content Aware Image Resizing, I introduced a pure JavaScript implementation of the famous Content Aware Image Resizing algorithm also known as Liquid Rescale. I explained the idea and the possible future of this implementation.

Since then, I have had some precious feedbacks from Paul Rouget and Tristan Nitot. They suggested to make the demo a little bit more interactive. Paul gave me some guidelines to improve the overall performance and I tried to follow his advices. You can play with this demo here (Firefox 3.5b4+ required).

It also required a little bit more informations…

How does it work ?

Obviously, the only way to manipulate bitmap data in a browser is to use the Canvas API. In this demo, when the page is loaded, the process is launched with an image URL and some parameters. A little form enables the visitor to play with them.

The process involves 4 iterative steps, starting with a source image.

1 - It Generates a grayscale image from the source

Canvas only provides a low level API for pixel manipulation. Developers only have access to a 1 dimension array containing the 4 components (RGBA) in a row along with a width and a height properties. The ImageData object appears as follow :

The following luminance (Y) formula is used to obtain a grayscale :

Canvas only manipulates 4 components (RGBA) images. Thus, luminance must be applied to RGB components to display the grayscale version of the image.

2 - It generates an edge detection and an energy map from the grayscale image

The edge detection image is generated using a Sobel convolution. Since canvas does not provide a direct way to apply a convolution filter to an image, the Sobel matrix is applied to each pixel in a loop.
To increase performance, the Sobel and the energy are computed together in the same loop.

Energy is obtained with the following formula : “the energy of a pixel is computed from its own value plus the value of the lowest energy pixel from the three above it”. To obtain the energy map, the image is crawled from top left to bottom right.

3 - It generates a seam of the lowest energy

A seam is a 1 pixel wide vertical line.
The seam is generated from the bottom to the top row of the image :

1. It takes the lowest energy pixel of the bottom row of the energy map
2. It takes the lowest energy pixel from the three above it
3. It repeats 1 and 2 until it reaches the top row of the image

4 - It slices the seam from the source

The process computes an output image from the original picture by slicing the seam. The new generated picture is re-injected as a parameter for the next iteration.

Performances

The process has to be repeated for each seam. Reducing the image width of 50 pixels implies 50 vertical seams. Such algorithm is a good place for improvement because it involves a lot of repetitive tasks. A little improvement can result in seconds.
I tweaked many aspects of the algorithm to increase performances. For example, I reduced the crawl in the scope chain by using local variables. I avoided function calls in loops. I tried to use one loop instead of two inner loops when computing pixels (using the length property of canvas ImageData data object instead of its width and height properties).

I also tried a more radical way to improve performance by reducing the size of the image before entering the process and retrieving the original size after its completion. Such task has side effects. Indeed, when a 2 factor is used (reducing the image by half and then re-increasing it by 2), calculating the seam provides a 2 pixels wide seam instead of 1 pixel wide seam. Thus, the process is almost twice faster but only half of the intermediate results is obtained. For a 50 seams reduction, only 25 intermediates images are calculated in this way.

Finally, let’s mention memory usage. I had to store the artefacts generated along the process (grayscale image, energy map and seam map). Instead of creating a new ImageData object for each artefact, I stored all of them in a single ImageData object. For that purpose, I used the R component for grayscale values, the G component for energy map and the B component for seam map. In the demo, the pseudo image is displayed, on the fly, by regenerating a real ImageData object from a single component.

What’s next ?

The algorithm is not perfect and fits to some images better than to others.
Many improvements are possible :

• Adding expansion capability
• Adding vertical resizing
• Adding the feature of image removal portion
• Adding support for threading

In a future post I’ll surely try to go a little bit further and see what I can do with Workers, and maybe add some new features to this implementation : first on my roadmap is expansion capability.

How to use the demo ?

In this demo, you can compare both the liquid resized and the CSS resized image. Give a closer look at Wolverine head !

You can also change the bottom reference picture to compare liquid resize with the artefacts generated during the process (use the drop down list in the title of the picture) :

I must admit the process is very fast, but still not realtime. However, after a short process time, it’s possible to resize manually the images, by dragging the right border of the top image or even by using left and right arrows.

Finally, a little form will give you the chance to change some settings :

Any comments, any ideas, any suggestions are welcome !