Automatic pixel art cleaning

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Automatic pixel art cleaning

Krzysztof Kosiński
Hello

For one of the courses I am doing at the university, I want to create
a pixel art cleaner which would complement the recent GSoC pixel art
vectorizer. It is a well known problem that most pixel art images
available on the Internet are not appropriate inputs for the
vectorizer: they have multiplied pixels, additional grids, various
artifacts, defacements with watermarks, etc. Here are a few examples:

1. Multiplied pixels only:
http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/results_nearest/smw2_yoshi_01_nearest_16x.png

2. Border, grid, JPEG artifacts:
http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecraft.w654.jpg

3. Grid, imperfect alignment:
http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox99-d6mervk.png

4. Grid, imperfect alignment, defacement:
http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1600/flappy.PNG

5. Grid, nonuniform pixel colors:
http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d46lmjp.jpg

6. Scan of a hand-filled grid paper:
http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hidemaniac-d6fblrc.jpg

7. Photographs:
http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-d6whfrw.jpg
http://farm8.staticflickr.com/7258/7434425816_9b810a3b6d_z.jpg

I'm looking for a few ideas on how to design an algorithm that would
automatically convert these images to a clean input to the pixel art
vectorizer. Obviously any successful algorithm will exploit three
basic facts about pixel art:
1. The pixels are laid out in a rectangular grid.
2. Color within a pixel is uniform.
3. The color palette is limited.

My first guess is to use a GSL and find the parameters of the pixel
grid by using a generic optimizer. The cost function could include the
variance of color within a pixel, area of the pixels (larger pixels
should be preferred), and a few other parameters. After identifying
the parameters of the pixel grid, the colors of the pixels would be
found by averaging and then clustering (to eliminate JPEG artifacts
and defacements).

Initially I considered using FFT methods, but this would never work
for images such as 5, 6 or 7, and ideally I want to cover them as
well. Another possibility is to use the Hough transform to find sharp
lines in the image and then look for regularities in the lines.

Does anyone have more ideas?

Regards, Krzysztof

------------------------------------------------------------------------------
New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
GigeNET is offering a free month of service with a new server in Ashburn.
Choose from 2 high performing configs, both with 100TB of bandwidth.
Higher redundancy.Lower latency.Increased capacity.Completely compliant.
http://p.sf.net/sfu/gigenet
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Automatic pixel art cleaning

Mark Schafer
1. Hough transform for lines
2. Straighten op to align detected vert, horiz lines
3. quantizer to find regularity of grid and dimension
4. sampler (using various techniques) to detect color at center (area)
of grid points.
Implement using Python and openCV
     - initial start here as rough guide -
http://stackoverflow.com/questions/19054055/python-cv2-houghlines-grid-line-detection


On 1/25/2015 2:57 PM, Krzysztof Kosiński wrote:

> Hello
>
> For one of the courses I am doing at the university, I want to create
> a pixel art cleaner which would complement the recent GSoC pixel art
> vectorizer. It is a well known problem that most pixel art images
> available on the Internet are not appropriate inputs for the
> vectorizer: they have multiplied pixels, additional grids, various
> artifacts, defacements with watermarks, etc. Here are a few examples:
>
> 1. Multiplied pixels only:
> http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/results_nearest/smw2_yoshi_01_nearest_16x.png
>
> 2. Border, grid, JPEG artifacts:
> http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecraft.w654.jpg
>
> 3. Grid, imperfect alignment:
> http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox99-d6mervk.png
>
> 4. Grid, imperfect alignment, defacement:
> http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1600/flappy.PNG
>
> 5. Grid, nonuniform pixel colors:
> http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d46lmjp.jpg
>
> 6. Scan of a hand-filled grid paper:
> http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hidemaniac-d6fblrc.jpg
>
> 7. Photographs:
> http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-d6whfrw.jpg
> http://farm8.staticflickr.com/7258/7434425816_9b810a3b6d_z.jpg
>
> I'm looking for a few ideas on how to design an algorithm that would
> automatically convert these images to a clean input to the pixel art
> vectorizer. Obviously any successful algorithm will exploit three
> basic facts about pixel art:
> 1. The pixels are laid out in a rectangular grid.
> 2. Color within a pixel is uniform.
> 3. The color palette is limited.
>
> My first guess is to use a GSL and find the parameters of the pixel
> grid by using a generic optimizer. The cost function could include the
> variance of color within a pixel, area of the pixels (larger pixels
> should be preferred), and a few other parameters. After identifying
> the parameters of the pixel grid, the colors of the pixels would be
> found by averaging and then clustering (to eliminate JPEG artifacts
> and defacements).
>
> Initially I considered using FFT methods, but this would never work
> for images such as 5, 6 or 7, and ideally I want to cover them as
> well. Another possibility is to use the Hough transform to find sharp
> lines in the image and then look for regularities in the lines.
>
> Does anyone have more ideas?
>
> Regards, Krzysztof
>
> ------------------------------------------------------------------------------
> New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
> GigeNET is offering a free month of service with a new server in Ashburn.
> Choose from 2 high performing configs, both with 100TB of bandwidth.
> Higher redundancy.Lower latency.Increased capacity.Completely compliant.
> http://p.sf.net/sfu/gigenet
> _______________________________________________
> Inkscape-devel mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/inkscape-devel
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2015.0.5645 / Virus Database: 4273/8994 - Release Date: 01/24/15
>
>


------------------------------------------------------------------------------
New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
GigeNET is offering a free month of service with a new server in Ashburn.
Choose from 2 high performing configs, both with 100TB of bandwidth.
Higher redundancy.Lower latency.Increased capacity.Completely compliant.
http://p.sf.net/sfu/gigenet
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Automatic pixel art cleaning

Tavmjong Bah
In reply to this post by Krzysztof Kosiński
On Sun, 2015-01-25 at 02:57 +0100, Krzysztof Kosiński wrote:

> Hello
>
> For one of the courses I am doing at the university, I want to create
> a pixel art cleaner which would complement the recent GSoC pixel art
> vectorizer. It is a well known problem that most pixel art images
> available on the Internet are not appropriate inputs for the
> vectorizer: they have multiplied pixels, additional grids, various
> artifacts, defacements with watermarks, etc. Here are a few examples:
>
> 1. Multiplied pixels only:
> http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/results_nearest/smw2_yoshi_01_nearest_16x.png
>
> 2. Border, grid, JPEG artifacts:
> http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecraft.w654.jpg
>
> 3. Grid, imperfect alignment:
> http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox99-d6mervk.png
>
> 4. Grid, imperfect alignment, defacement:
> http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1600/flappy.PNG
>
> 5. Grid, nonuniform pixel colors:
> http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d46lmjp.jpg
>
> 6. Scan of a hand-filled grid paper:
> http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hidemaniac-d6fblrc.jpg
>
> 7. Photographs:
> http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-d6whfrw.jpg
> http://farm8.staticflickr.com/7258/7434425816_9b810a3b6d_z.jpg
>
> I'm looking for a few ideas on how to design an algorithm that would
> automatically convert these images to a clean input to the pixel art
> vectorizer. Obviously any successful algorithm will exploit three
> basic facts about pixel art:
> 1. The pixels are laid out in a rectangular grid.
> 2. Color within a pixel is uniform.
> 3. The color palette is limited.
>
> My first guess is to use a GSL and find the parameters of the pixel
> grid by using a generic optimizer. The cost function could include the
> variance of color within a pixel, area of the pixels (larger pixels
> should be preferred), and a few other parameters. After identifying
> the parameters of the pixel grid, the colors of the pixels would be
> found by averaging and then clustering (to eliminate JPEG artifacts
> and defacements).
>
> Initially I considered using FFT methods, but this would never work
> for images such as 5, 6 or 7, and ideally I want to cover them as
> well. Another possibility is to use the Hough transform to find sharp
> lines in the image and then look for regularities in the lines.
>
> Does anyone have more ideas?

No. 7 needs an extra step of transforming but a FFT should work directly
on the others. I imagine there is photography software that can do the
transforming of 7 automatically.

I am not sure why you think FFT won't work on 5. You have the background
grid which should provide a large amplitude for the grid frequency. Even
without the background, the shading within the pixel is like a sawtooth
function where the grid frequency should still be the largest component.

FFT should also work on 6. The roughness along the edges of the cells
shouldn't over-weigh the dominant frequency.

To remove defacement, histogram the color of the pixels within the cell
and take the color bin with the largest component. You can then compare
that value with the value for neighboring cells or other cells in the
drawing as an additional check.

This looks like a fun project! Keep us posted.

Tav




------------------------------------------------------------------------------
New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
GigeNET is offering a free month of service with a new server in Ashburn.
Choose from 2 high performing configs, both with 100TB of bandwidth.
Higher redundancy.Lower latency.Increased capacity.Completely compliant.
http://p.sf.net/sfu/gigenet
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Automatic pixel art cleaning

Jabier Arraiza
In reply to this post by Krzysztof Kosiński
Hi Krzysztof.

Dont see the problem in the first item.
We can assume -or maybe can check- the input image are not pixelArt and
each art pixel has a minimun of four real pixels? Maybe 16?

Regards, Jabier.

El dom, 25-01-2015 a las 02:57 +0100, Krzysztof Kosiński escribió:

> Hello
>
> For one of the courses I am doing at the university, I want to create
> a pixel art cleaner which would complement the recent GSoC pixel art
> vectorizer. It is a well known problem that most pixel art images
> available on the Internet are not appropriate inputs for the
> vectorizer: they have multiplied pixels, additional grids, various
> artifacts, defacements with watermarks, etc. Here are a few examples:
>
> 1. Multiplied pixels only:
> http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/results_nearest/smw2_yoshi_01_nearest_16x.png
>
> 2. Border, grid, JPEG artifacts:
> http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecraft.w654.jpg
>
> 3. Grid, imperfect alignment:
> http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox99-d6mervk.png
>
> 4. Grid, imperfect alignment, defacement:
> http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1600/flappy.PNG
>
> 5. Grid, nonuniform pixel colors:
> http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d46lmjp.jpg
>
> 6. Scan of a hand-filled grid paper:
> http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hidemaniac-d6fblrc.jpg
>
> 7. Photographs:
> http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-d6whfrw.jpg
> http://farm8.staticflickr.com/7258/7434425816_9b810a3b6d_z.jpg
>
> I'm looking for a few ideas on how to design an algorithm that would
> automatically convert these images to a clean input to the pixel art
> vectorizer. Obviously any successful algorithm will exploit three
> basic facts about pixel art:
> 1. The pixels are laid out in a rectangular grid.
> 2. Color within a pixel is uniform.
> 3. The color palette is limited.
>
> My first guess is to use a GSL and find the parameters of the pixel
> grid by using a generic optimizer. The cost function could include the
> variance of color within a pixel, area of the pixels (larger pixels
> should be preferred), and a few other parameters. After identifying
> the parameters of the pixel grid, the colors of the pixels would be
> found by averaging and then clustering (to eliminate JPEG artifacts
> and defacements).
>
> Initially I considered using FFT methods, but this would never work
> for images such as 5, 6 or 7, and ideally I want to cover them as
> well. Another possibility is to use the Hough transform to find sharp
> lines in the image and then look for regularities in the lines.
>
> Does anyone have more ideas?
>
> Regards, Krzysztof
>
> ------------------------------------------------------------------------------
> New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
> GigeNET is offering a free month of service with a new server in Ashburn.
> Choose from 2 high performing configs, both with 100TB of bandwidth.
> Higher redundancy.Lower latency.Increased capacity.Completely compliant.
> http://p.sf.net/sfu/gigenet
> _______________________________________________
> Inkscape-devel mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/inkscape-devel

------------------------------------------------------------------------------
New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
GigeNET is offering a free month of service with a new server in Ashburn.
Choose from 2 high performing configs, both with 100TB of bandwidth.
Higher redundancy.Lower latency.Increased capacity.Completely compliant.
http://p.sf.net/sfu/gigenet
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel

signature.asc (220 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Automatic pixel art cleaning

Krzysztof Kosiński
In reply to this post by Tavmjong Bah
2015-01-25 9:23 GMT+01:00 Tavmjong Bah <[hidden email]>:
> No. 7 needs an extra step of transforming but a FFT should work directly
> on the others. I imagine there is photography software that can do the
> transforming of 7 automatically.

I'm not sure how the transformation would work. If we can determine
the correct transformation of the grid to rectangular form, we can
also sample the pixels in the grid without transforming.

> I am not sure why you think FFT won't work on 5. You have the background
> grid which should provide a large amplitude for the grid frequency. Even
> without the background, the shading within the pixel is like a sawtooth
> function where the grid frequency should still be the largest component.

I did some tests with ImageMagick and it looks like FFT indeed works
even for the harder cases as long as the grid is rectangular, though
the heuristics required to pick the dominant frequency are not yet
obvious to me. I'm also not sure how to omit the border regions (like
in 2). Two cases that seem to fail are large images that are upscaled
so that each pixel is 2x2 and images where the borders between pixels
are slightly blurry, but maybe that's a numerical accuracy problem (I
inspected the FFT images by saving them to PNG and then auto-adjusting
in GThumb, which bumped every non-black pixel to 100% lightness).

> FFT should also work on 6. The roughness along the edges of the cells
> shouldn't over-weigh the dominant frequency.
>
> To remove defacement, histogram the color of the pixels within the cell
> and take the color bin with the largest component. You can then compare
> that value with the value for neighboring cells or other cells in the
> drawing as an additional check.

This will work OK when there are no JPEG artifacts or other color
variations within the cell other than the defacement, but in cases
such as 5 the histogram will be fairly flat. I think histogramming the
pixels according to luminosity with some quantization (e.g. 32 levels
of luminosity) and then averaging the pixels in the bin with the
dominant luminosity might work. The obtained value would then be
subject to global color quantization. However, I'm not sure how that
would extend to cases such as 6.

Regards, Krzysztof

------------------------------------------------------------------------------
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Automatic pixel art cleaning

Mark Schafer
python openCV program attached that:
- finds edges,
- calculates perspective correction if required.
- needs grid counting, boundary detection, and sampling to finish
- tested with the images indicated in thread.
Cheers...

On 1/27/2015 7:40 AM, Krzysztof Kosiński wrote:

> 2015-01-25 9:23 GMT+01:00 Tavmjong Bah <[hidden email]>:
>> No. 7 needs an extra step of transforming but a FFT should work directly
>> on the others. I imagine there is photography software that can do the
>> transforming of 7 automatically.
> I'm not sure how the transformation would work. If we can determine
> the correct transformation of the grid to rectangular form, we can
> also sample the pixels in the grid without transforming.
>
>> I am not sure why you think FFT won't work on 5. You have the background
>> grid which should provide a large amplitude for the grid frequency. Even
>> without the background, the shading within the pixel is like a sawtooth
>> function where the grid frequency should still be the largest component.
> I did some tests with ImageMagick and it looks like FFT indeed works
> even for the harder cases as long as the grid is rectangular, though
> the heuristics required to pick the dominant frequency are not yet
> obvious to me. I'm also not sure how to omit the border regions (like
> in 2). Two cases that seem to fail are large images that are upscaled
> so that each pixel is 2x2 and images where the borders between pixels
> are slightly blurry, but maybe that's a numerical accuracy problem (I
> inspected the FFT images by saving them to PNG and then auto-adjusting
> in GThumb, which bumped every non-black pixel to 100% lightness).
>
>> FFT should also work on 6. The roughness along the edges of the cells
>> shouldn't over-weigh the dominant frequency.
>>
>> To remove defacement, histogram the color of the pixels within the cell
>> and take the color bin with the largest component. You can then compare
>> that value with the value for neighboring cells or other cells in the
>> drawing as an additional check.
> This will work OK when there are no JPEG artifacts or other color
> variations within the cell other than the defacement, but in cases
> such as 5 the histogram will be fairly flat. I think histogramming the
> pixels according to luminosity with some quantization (e.g. 32 levels
> of luminosity) and then averaging the pixels in the bin with the
> dominant luminosity might work. The obtained value would then be
> subject to global color quantization. However, I'm not sure how that
> would extend to cases such as 6.
>
> Regards, Krzysztof
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming. The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> Inkscape-devel mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/inkscape-devel
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2015.0.5645 / Virus Database: 4273/9002 - Release Date: 01/26/15
>
>

------------------------------------------------------------------------------
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel

gridded_image_breakdown.py (9K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Fwd: Automatic pixel art cleaning

Krzysztof Kosiński
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


------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=190641631&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel

goku_paper.jpg (192K) Download Attachment
output.png (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Automatic pixel art cleaning

Tavmjong Bah

Nice!

Speaking of pixel art, the CSS Images 3 specification[1] has a value of
'crispy-edges' for 'image-rendering'. The algorithms they propose work
on integer scaling of pixel art. Any ideas on how to scale by a
non-integer value? I am thinking that scaling by an integer value
greater than the specified non-integer value and then scaling back down
might be the best solution.

Tav

[1] http://dev.w3.org/csswg/css-images-3/

On Fri, 2015-02-20 at 17:32 +0100, Krzysztof Kosiński wrote:

> 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
>
>
>
> ------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> with Interactivity, Sharing, Native Excel Exports, App Integration & more
> Get technology previously reserved for billion-dollar corporations, FREE
> http://pubads.g.doubleclick.net/gampad/clk?id=190641631&iu=/4140/ostg.clktrk
> _______________________________________________ Inkscape-devel mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/inkscape-devel



------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=190641631&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Automatic pixel art cleaning

Jon A. Cruz
In reply to this post by Krzysztof Kosiński
On Fri, Feb 20, 2015, at 08:32 AM, Krzysztof Kosiński wrote:
I finally have something that mostly works. Attached are example input and result.
 
 
Nice!
 
--
Jon A. Cruz
 

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=190641631&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel