We make preview sites in the style of Yandex Browser

Almost two months have passed since Yandex has pleased some users with a new product - Yandex Browser. Despite the incredible dynamics in the development of products in this area (Chrome and Firefox), Yandex managed to bring a number of new ideas into its browser.

Of all the features of this browser, most of all I was hooked by their design decision regarding the images of sites in “speed bookmarks” (Speed ​​dial). People love with their eyes and therefore it is nice to see in their new tabs not a blank white page, but colorful pictures. The only trouble is that I personally, most often, look at the caption under this picture or on the favicon, since it can be very difficult to recognize it from the screenshot of the site. Designers of Yandex, in my opinion, decided this problem very elegantly. In this post we will look at how to implement this idea on the client side.


')
The essence of the idea is as follows:

1. We get a favicon site
2. Determine the dominant favicon color
3. Draw a rectangle with the dominant color and insert a favicon into it
4. For greater attractiveness, a gradient is superimposed above.

It sounds really very simple. The most difficult moment here is the definition of the dominant color in favicon. To do this, we need to solve three problems:

1. Get favicon.
2. Get access to the value of each pixel of the image.
3. Decide on the algorithm for determining the dominant color.

Getting favicon

In order to get a favicon, you can either write a handler on the server that will search and return a favicon for the domain, or you can see how the Yandex browser does it ... And it does this with the help of a request for the same-name service Yandex. For example, such a request:

GET favicon.yandex.net/favicon/habrahabr.ru

Will return here such a picture:

Access to image pixels

Regarding the second task, the only way to access the pixel values ​​of the image on the client side is to use the element. Having loaded the image in canvas we will be able to receive value of any pixel.

However, there is some problem. Accessing image pixels using the canvas tag is possible only for those images that are loaded from the same domain as the page that processes them (cross-domain browser policy works).

Thus, to use the canvas element to search for the dominant color in favicon, you need to create a proxy on your server that download favicon (for example, from favicon.yandex.ru service) and return it back to you on the page.

In this regard, the implementation of such a preview of sites purely on the client side, alas, will not work. In fact, since we still need a server as a proxy for images, we could transfer the dominant color to the server and get the color, not the icon, back to the page. However, how to implement this on the server side is not so interesting and very heterogeneous, since depending on the language used on the server (Python, PHP, Java), the implementation will be different. Therefore, we will look at how to do this on the client using the canvas element.

Algorithm for determining the dominant color

There are many algorithms for determining the dominant color image. The general idea of ​​these algorithms is as follows. Each pixel of the image is a quadruple of numbers R, G, B, A. We go through all the pixels and in a special way analyze their components:

 //   canvas var canvas = document.createElement('canvas'); var ctx = canvas.getContext('2d'); //   canvas  favicon ctx.drawImage( faviconImage, 0, 0, 18, 18); //     var data = ctx.getImageData(0, 0, 18, 18); //    for ( i = 0; i<data.data.length; i=i+4 ) { rgb = {}; rgb.r = data.data[i]; rgb.g = data.data[i + 1]; rgb.b = data.data[i + 2]; } 

In our case, the implementation should take into account two features:

I. Many favicons have transparent pixels that, when drawn to the canvas element, are represented as rgba (0, 0, 0, 0). Since we ignore the alpha channel, for us these pixels will look like black (# 000000), which is not true. To fix this, just paint the canvas in white before drawing a favicon on it.

 //  canvas   ctx.fillStyle = 'rgb(255, 255, 255)'; ctx.fillRect(0, 0, 18, 18); //  favicon ctx.drawImage( faviconImage, 0, 0, 18, 18); 

Ii. Since the favicon is intended to fit into a white circle, if the predominant color in the image is white, we will not see either the circle or the borders of our element. To avoid this, we will simply ignore the white pixels in each algorithm.

I will consider three different algorithms for determining the dominant color by increasing their complexity.

Algorithm 1. Average color value

The first and most simple algorithm is as follows. We simply go through all the pixels and count the arithmetic average of the corresponding colors. In order not to overload the article with code - all source codes are available on gihub , I will only show the results of their work:

Algorithm 2. Euclidean distance

This algorithm is a little more complicated and is as follows. Each color is a vector in three-dimensional space (r, g, b). We traverse each pixel and count its distance to all other pixels (Euclidean distance between two vectors). Then we look for the pixel that is closest to everything else. The color of this pixel is our desired color. It should be noted here that this algorithm, unlike the previous one, does not create a new color, but only selects from those already existing in this image.

Algorithm 3. The k-means clustering method

The essence of this algorithm is as follows. Randomly selected k pixels (centers) of the image of a different color. We pass through all the other pixels and assign each of them to one of the centers on the basis of their proximity to each other (we consider the Euclidean distance as in algorithm 2). Then we recalculate the centers - we set for them a value equal to the average among all the pixels assigned to it (as in Algorithm 1). Again we go through all the pixels and distribute them to the new centers. We do all this until the value of the centers stops changing. The desired color will be the center value with the most pixels. It should be noted that this method is used for the same purpose in the Chrome browser. The result of his work for k = 3 is as follows:



For k = 5:



(for the remaining values ​​of the parameter k, the results are not so indicative)

Conclusion

The question of which of these algorithms is better is controversial.

• The average algorithm is incredibly simple and generally works, but it can give a rather dirty result.
• Calculation through Euclidean distance, for my taste, gives a rather nice result and at the same time is easy to implement.
• The clustering algorithm is the most complex. Gives the most vivid image and requires the most calculations.

PS Github-user static-lab proposed and implemented another algorithm "YUV averaged with contrast", which also gives a very good result:



The example can be run in your browser (favicons encoded in Base64): DEMO
Sources here: github