preface

Pixel style first appeared in 8bit video games, limited by the size of the computer memory and the display of a single color, can only use a small number of pixels to present content, but the achievements of many classic pixel games. With the increase in memory capacity and screen resolution, the limitations of memory and display media are no longer an issue, and the pixel style has slowly evolved into a unique creative style.

The general drawing process of pixel painting includes line marking, color filling, etc., but it takes a lot of time to draw pixel by pixel. Some popular art forms, such as line drawing and painting, have gradually appeared automated or semi-automated generation methods. This paper will implement the SLIC[1] algorithm from scratch, and implement a tool to generate pixel paintings.

What is the SLIC algorithm

The reason why pixel drawing is not simple is that direct downsampling cannot accurately capture key pixels, and it is easy to lose edge information, and the generated pixel drawing is often unsatisfactory. Manual marking, color, are to select the right pixel point. Therefore, our problem becomes how to select the appropriate pixels to fill in.

First, introduce the concept of superpixels. Superpixel, an image segmentation technology proposed and developed by Xiaofeng Ren in 2003, refers to irregular pixel blocks with certain visual significance formed by adjacent pixels with similar texture, color, brightness and other characteristics [1].

By dividing the image into superpixels, similar pixel clusters can be obtained. Similar pixels are filled with the same color, and the resulting pixel paintings will be more reasonable.

The methods of superpixel point segmentation include contour extraction, clustering, gradient ascending and so on. The paper[1]Put forward theSLICSuperpixel point segmentation algorithm (simple linear iterative clustering,simple linear iterative clustering) is based onK-meansThe clustering algorithm performs clustering according to the color and distance features of pixels to achieve good segmentation results. Compared with several super-pixel point segmentation algorithms,SLICIt has the advantages of simple and flexible, good effect and fast processing speed.

How to implement THE SLIC algorithm

The basic process of SLIC is as follows:

  1. Image preprocessing.

    The image is converted from RGB color space to CI-Lab color space, which is more consistent with human visual perception of color. The distance in this space reflects the difference in color perceived by the person, and the calculation is more accurate.

    Lab color space also has three channels, namely l, a and b, where l represents brightness with a value range of [0,100], a represents the component from green to red with a value range of [-128,127], and b represents the component from blue to yellow with a value range of [-128,127].

    There is no direct conversion formula between RGB and LAB. RGB needs to be converted to XYZ color space and then converted to LAB. See the complete code at the end of the article for the code.

  2. Initialize the cluster center.

    Determine the number of superpixels according to the parameters, that is, how many regions need to be divided. Assuming that the image has N pixels, it is expected to be divided into K superpixels, the size of each superpixel is N/K, the distance between adjacent centers is S=Sqr(N/K), and K clustering coordinates are obtained.

  3. Optimize the initial clustering center. The pixel point with the smallest gradient in the 3*3 neighborhood of the cluster center was selected as the new cluster center.

    The image is regarded as a two-dimensional discrete function, and the gradient is the derivative of this function. When the value of adjacent pixels changes, there will be a gradient, and the gradient of pixels on the edge is the largest. Moving the clustering center to the place with the smallest gradient can avoid it falling on the edge contour and affect the clustering effect.

    The gradient calculation of discrete gradient will not be derived in detail here, because it involves several squares and roots, which requires a large amount of calculation. It is generally simplified to approximate square and square roots with absolute values. After simplification, the gradient formula of pixel points with calculated coordinates of (I,j) is:

    Where (I +1,j) and (I,j+1) are the coordinates of the point on the right side of the pixel and the point below the pixel. L (a,b) is the brightness channel value l of the pixel on the coordinate (a,b).

  4. Calculate the distance between pixels and the cluster center.

    The distance between pixels and each cluster center is calculated in the neighborhood of 2S*2S in the region with the distance from the cluster center S.

    Euclidean distance is used here. The total distance D is composed of dc color distance and DS space distance. The formula is as follows:

    If l, A, B, x and y are directly splinted into a vector to calculate the distance, when the size of the superpixel changes, the values of x and y can be very large. For example, if a picture is 1000*1000, the spatial distance can reach 1000*Sqr(2), while the maximum color distance is only 10*Sqr(2), leading to the final calculated distance value, The weight ratio of spatial distance DS is too large.

    So we need to normalize, divide by the maximum value, which is the initial width of the superpixel point S, and map the value to [0,1].

    The color space distance will also be given a fixed value m to adjust the influence weight between the color distance and the space distance. The value of m ranges from [1,40].

    So the formula for distance becomes

    When m is larger, the value of color space divided by m is smaller, that is, the weight of space distance is larger, and the generated pixels will be more regular in shape. When M is smaller, the weight of color distance is larger, and the super pixels will be more compact at the edge, but the shape and size are more irregular.

  5. Pixel point classification.

    Mark each pixel as the category from its smallest cluster center.

  6. Recalculate the cluster center.

    The mean vector values of all pixels belonging to the same cluster were calculated to get the cluster center again.

  7. Iteration 4 to 6 process.

    Until the distance between the old clustering center and the new clustering center is less than a certain threshold or reaches a certain number of iterations, generally speaking, when the number of iterations reaches 10, the algorithm can achieve convergence.

  8. Clustering optimization.

    At the end of iteration, isolated pixels that do not belong to the same connected domain as the cluster center may appear, which can be assigned to the nearest cluster label by using the connected algorithm.

    The specific implementation algorithm is not given in this paper. However, the application scene of this paper is to generate pixel paintings, which will take a sample of pixels and not refine each pixel. Therefore, clustering optimization is not done in this paper.

To sum up, the process of SLIC algorithm is basically the same as that of K-means, which continuously computes the cluster with the smallest distance iteratively. The difference is that it only computes the pixels within the s-distance of the cluster center, which reduces a lot of calculation.

Generate pixel art

Based on the SLIC algorithm, we can already divide a graph into N superpixels. The pixels within each superpixel are similar. That is, each pixel is classified as a superpixel with a clustering center. Then assign the color of the pixel to the color of its cluster center to get the desired effect.

Set the stride of a certain length, use Canvas, and assign the pixel to the color of its cluster center in every stride pixel, namely, obtain the final pixelation result.

However, everyone’s subjective feelings about pixel paintings are inconsistent. In order to give users more choices, they can get satisfactory results. More manual intervention parameters can be exposed, such as removing the termination condition of clustering optimization and letting the user set the number of iterations and the step size of the final pixel value. Manual parameters include

  • Superpixel point sizeblocksize;blocksizeThe smaller the pixel, the more delicate the segmentation.
  • The number of iterationsiters;itersThe larger the size is, the more accurate the segmentation result is and the longer the calculation time is.
  • Color space weightweight;weightThe larger the color is, the more influence it has on the segmentation result.
  • Take the pixel stepstride;strideThe smaller the pixel image, the closer it is to the superpixel point and the finer it is.

Implement user interface

As a tool, it naturally needs a user interaction interface. The front-end interface is built based on HTML/Javascript/CSS, and the Canvas API is used to draw image content. The dat. GUI [3] library is selected for the user interaction panel. Dat. GUI is a lightweight graphical interface library, very suitable for parameter modification, often used for visual Demo demonstration. The supported parameter types include Number, String, Boolean, and custom functions. You can bind corresponding response events for different properties, which are automatically triggered when the property value changes.

Add the following properties and events to generate the pixel tool:

  • whenIters, stride, blockSize, weight(color space weight m) re-perform when the parameter changesSLICAlgorithm calculation, and redraw the calculation results;
  • addUpload image 与Export imageButton, support users to upload pictures and download pixelated pictures;

Overlay a Canvas Canvas layer on top of the Canvas Canvas layer of the image to visualize the results of the algorithm and add the following functions

  • gridThe switch controls whether to draw a pixel grid;
  • CentersSwitch control whether display clustering center;
  • ContoursThe switch controls whether the cluster edge contour is displayed;

Among them, the cluster center Centers can be directly drawn by using CTx. fillRect to pass in the coordinates of the center points.

The drawing of Contours needs to calculate the contour points first.

Each pixel can be compared with the surrounding 8 pixels. If the number of different pixels in the cluster center is greater than 2, it means that there are more than two points of different categories around this pixel, and this point is the contour. The effect is as follows:

Finally, you have a simple tool for generating pixel art.

Experience the address

Full version code address (JS version)

reference

[1] Achanta R, Shaji A, Smith K, Lucchi A, Fua P, Su ̈sstrunk S. SLIC superpixels. Technical Report. IVRG CVLAB; 2010.

[2] Gerstner T , Decarlo D , Alexa M , et al. Pixelated image abstraction with integrated user constraints[J]. Computers & graphics, 2013.

[3] github.com/dataarts/da…