Fwd: Automatic pixel art cleaning

20 Feb 2015


      I finally have something that mostly works. Attached are example input and
result.
The algorithm I designed works as follows:
1. Compute a sum of Fourier transforms of each row and each column of the
image.
2. For both sums, look for the 'base frequency', i.e. the size of the pixel
grid. There are two variants here: if the pixel art does not have grid
lines, the base frequency is indicated by periodic values very close to
zero ("antipeaks"), and if it does, there are periodic peaks. Spacing
between peaks / antipeaks corresponds to the number of pixels. I use an
empirically derived scoring scheme.
3. Sample the image at the center of grid points. Currently I use bilinear
sampling at the center of the pixel, but something more clever would be
better to remove defacements. For instance, doing cluster analysis and
picking the average of the most numerous cluster should work.
4. Quantize colors. I wanted to avoid having to specify the number of
colors in advance, so I used single-link clustering in Lab color space.
Complete-link would probably work better.
5. Output the resulting image as PNG.
The only tunable value in the algorithm is the clustering diameter;
everything else is automatic. A value of deltaE = 8 seems to work fairly
well.
The algorithm works very well if the following conditions are met:
1. Pixel size is at least 5-6.
2. Image borders are aligned with the pixel art grid.
3. There is no skew or other deformation of the image.
We can handle small pixel sizes, e.g. 2-5, by simply checking whether the
art pixels given by these grid parameters contain approximately uniform
colors.
Limitations 2 and 3 could be lifted by preprocessing the image before the
FFT step. The Python script posted earlier in this thread can detect the
edges of the pixel art, but it doesn't work well in some cases, for example
in the case of sketches where the individual squares have jagged edges.
However, I think the approach of doing a Hough transform to detect lines
and then finding a projective transformation that straightens the image
could be promising. Another idea is to find areas of approximately uniform
color, mark them using something like flood fill, and then process the
edges.
I will soon post the code publicly and then integrate this into Inkscape as
an optional step in the Trace Pixel Art dialog, but can't give an ETA yet.
I think late March is realistic for integration. I will need to factor out
a few things which are more universally useful, e.g. conversion to Lab
color space and color quantization, or use an external library such as Babl
or LCMS.
Regards, Krzysztof

Krzysztof Kosiński

Tavmjong Bah

Jon A. Cruz

tags (0)

participants (3)