Android: the evolution of the photo editor VK

How did the photo editor for Android - from the first version of Snapster to the filters in the official VKontakte application.

This story began in 2015, when we started to create Snapster - a standalone photo editing application. At that time, in our official applications, and in the same Instagram image editing was arranged primitively. We take a snapshot, apply simple color modifications to it using OpenGL shaders, overlay textures to make it more glamorous. Is done.

A few months after the start of development, when the first version of Snapster was ready, it still used filters from the main VKontakte application. At this point, we began to realize that the existing approach has become obsolete, and we need to come up with something new.
')
We decided that it would be cool if users can create their own filters right on the phone. The process of creating a filter should be simple - so that even by poking a couple of buttons at random you can get a decent result. In addition, the editor should work very quickly - performance is extremely important, which means that we need to make the most of the capabilities of the built-in GPUs.

Since the truly unique filters cannot be made from the twists for the basic parameters (brightness, contrast, etc.), we decided to add a full color correction to the editor.

Color correction

The basic algorithm consists of two steps:

1. Find on the image all the pixels that fit the specified conditions. For example, if we want to replace all pure red pixels with something else, then we need to find those pixels in which R will be 255 in the RGB color space and G and B will be zero.
2. Replace them with pixels of the desired color.

Sounds pretty simple. But immediately a few questions arise:

1. How to set search criteria? It is obvious that conditions like “the component R is equal to 255, and G and B - to zero” are not applicable in practice. How to explain to the algorithm that you need to choose pixels of approximately the same color?
2. How to quickly search for the right pixels in the image? If the conditions for the search are too complicated, then you can expect decent work only on very powerful devices.
3. If the search criteria can get pixels of different colors, then they need to be changed not strictly to the color N, but taking into account their original color.

So, to find the pixels of the desired color, you need to create search criteria. Suppose we want to find all the pixels that differ from the desired color by no more than N, where N is a dynamically set error. How to do it? Since in different color models the color is decomposed into separate components, which are, in fact, coordinates, we can use the Euclidean distance to calculate the difference between the two colors.

At first we tried to find the necessary pixels of the image, counting the distance between their values ​​in the RGB color model. But the search results were very far from ideal. Pixels, the colors of which, in the eyes of a person, are very similar to the desired ones, can be located at a considerable Euclidean distance from each other. The thing is that the change in color in the RGB model is very non-linear in terms of human perception. In other words, a small change in the RGB value can be very noticeable to the human eye and vice versa. Compare:


RGB (0,0,0) → RGB (50,0,0)


RGB (205,0,0) → RGB (255,0,0)

To solve this problem, we switched to using the CIELab color model.

CIELab is a color model as close as possible to the human color perception system. In CIELab, any color is uniquely determined by the lightness L and two chromatic components: a is the position between green and magenta, and b is the position between blue and yellow.


CIELab circuit

CIELab allows you to evaluate the difference of colors as it sees the human eye, by simply calculating the Euclidean distance between two colors. In other words, now using the condition “ if the Euclidean distance between the Lab-value of a pixel and the Lab-value of a color X is less than N, then the pixel suits us ”, we can find pixels that have approximately the same color as the one we are looking for, within a certain error N.

In addition, using this model, it is very natural for the human eye to replace the found pixels with the desired color. Based on the same Euclidean distance, we can calculate exactly how to change color, while preserving the naturalness of the image.


Change the selected color

First implementation

We wanted to give the user the ability to immediately see the result on the screen. In addition, the solution should be cross-platform. Therefore, the only option was OpenGL.

In addition to color correction, the editor had to be able to automatically improve the image, as well as perform basic operations such as changing brightness, contrast, and similar characteristics.

Auto-enhancement in our editor works based on the histogram alignment technique. The point is to bring the source image histogram to a linear function. There are several such techniques, we use CLAHE.

CLAHE (contrast-limited adaptive histogram equalization) is a contrast-limited adaptive histogram alignment. Adaptive - because the histogram is considered not for the whole image at once, but for its small fragments separately. Contrast-limited - because the contrast changes only within the specified limits, which allows you to avoid unwanted amplification of noise in the image.

The CLAHE is executed on the processor, but for each launch of the editor, this happens once, and the resulting texture is stored in the in-memory cache. Therefore, there were no special performance requirements.

In the first implementation, the editor pipeline looked like this:

1. The use of auto-enhancement with a given intensity.
2. Application of basic operations.
3. Converting the resulting image to Lab.
4. Apply color correction.

It is worth noting that we gave users the opportunity to choose any colors in any quantity for color correction. Therefore, the OpenGL shader was collected dynamically right at the time the user selected and edited the colors.

The conversion from RGB to Lab was done in the forehead, without any optimizations. This means that the color value from RGB is first converted to XYZ, and only then from XYZ to Lab. Both conversions are pretty hard to compute, and in the end it turned out to be a bottleneck for the entire editor. To solve the problem, we turned to 3D Lookup Table technology .

Its meaning is extremely simple. 3D LUT is a three-dimensional table that stores the correspondence of the input and output values ​​of colors. For any input value in one color model, we can uniquely set the output value to another. And it works very fast!


3D LUT Lab

This scheme of the organization of the conveyor proved to be relatively good. But, of course, the rich world of Android devices added us problems. From the banal lack of video memory and monstrously poor performance on some devices to tight restrictions on the number of instructions in one shader on some GPUs, which in some cases could not even compile the color correction shader. And if the problem with the lack of video memory and low performance could be solved by reducing the rendering resolution on weak devices, the problem with the number of instructions was not so simple. We had to learn how to split the color correction shader into parts - and dynamically, and only when necessary, because each additional step in the pipeline reduced performance.

What's next?

After the release of the first version I wanted to add more features for editing. So in the editor appeared the Tone Curve tool, popular with photographers, everyone's favorite “curves”. Using the curves in the application, you can affect the brightness of pixels in specific RGB ranges. The values ​​of the pixels vary in accordance with the shape of the curve that the user sees on the screen.


Editing with curves in snapster

The implementation of the curves helped to optimize some basic operations. Now the curves themselves, brightness, contrast, fade, temperature and tint (hue) were applied in one pass using three 1D Lookup Tables.

Using OpenGL means a rather strict limit on the size of the output image, since all textures must be stored in video memory. Some Android devices at that time could hardly render a square larger than 1500x1500 pixels with our pipeline, but we wanted even more. And if we couldn’t do anything with the editor himself, then there was a solution for rendering the final result. We have duplicated all the functionality of the pipeline on pure C. The resulting code stored all intermediate textures in conventional RAM and made the most of the capabilities of multi-core processors. Thanks to this, users even far from the most powerful devices were able to save the final images in very high resolutions.

Filters in the main application

Filter selection, VKontakte for Android

When it came time to update the photo editor in the main VKontakte application for Android, we decided to use it from the Snapster. Now it uses the same set of standard filters. The editor allows you to switch filters with a swipe through the image, and two filters can be on the screen at once. With fast swipes, there are no delays or loadings - for the user, everything happens instantly.

A full-fledged pipeline from the Snapster editor would not allow such results to be achieved. It is too heavy and adaptable for a much more accurate work with a photo. Here, an important role was played by the realization that almost the entire filter pipeline is static. If in the Snapster the user had the opportunity to change any filter as he liked, then in the main application we wanted to give the opportunity only to apply the already prepared filters. This allowed us to use the already familiar 3D Lookup Table technology to apply the filter. Instead of converting from RGB to Lab, we convert the color from the original photo into the filter colors, and this happens very quickly.

Let's sum up

We managed to come from clumsy color modifications to a powerful and flexible tool for advanced image correction. We managed to make it work and work fast. Snapster has become a field for experiment, and this is a successful experiment - we have created a cool editor to be proud of. This experience helped us in the official VKontakte application. It is possible that we will transfer there some more part of Snapster functionality.

If you know and love Android, come to us to work on the application that millions of people use every day.