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/re...
2. Border, grid, JPEG artifacts: http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecra...
3. Grid, imperfect alignment: http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox...
4. Grid, imperfect alignment, defacement: http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1...
5. Grid, nonuniform pixel colors: http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d...
6. Scan of a hand-filled grid paper: http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hideman...
7. Photographs: http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-... 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
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-...
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:
- Multiplied pixels only:
http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/re...
- Border, grid, JPEG artifacts:
http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecra...
- Grid, imperfect alignment:
http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox...
- Grid, imperfect alignment, defacement:
http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1...
- Grid, nonuniform pixel colors:
http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d...
- Scan of a hand-filled grid paper:
http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hideman...
- Photographs:
http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-... 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:
- The pixels are laid out in a rectangular grid.
- Color within a pixel is uniform.
- 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 Inkscape-devel@lists.sourceforge.net 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
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:
- Multiplied pixels only:
http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/re...
- Border, grid, JPEG artifacts:
http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecra...
- Grid, imperfect alignment:
http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox...
- Grid, imperfect alignment, defacement:
http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1...
- Grid, nonuniform pixel colors:
http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d...
- Scan of a hand-filled grid paper:
http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hideman...
- Photographs:
http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-... 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:
- The pixels are laid out in a rectangular grid.
- Color within a pixel is uniform.
- 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
2015-01-25 9:23 GMT+01:00 Tavmjong Bah <tavmjong@...8...>:
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
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 <tavmjong@...8...>:
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 Inkscape-devel@lists.sourceforge.net 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
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:
- Multiplied pixels only:
http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/re...
- Border, grid, JPEG artifacts:
http://img.wonderhowto.com/img/56/01/63456484792752/0/make-pixel-art-minecra...
- Grid, imperfect alignment:
http://fc04.deviantart.net/fs70/i/2013/258/6/b/link_pixel_art_grid_by_matbox...
- Grid, imperfect alignment, defacement:
http://1.bp.blogspot.com/-jOu8vhgnSFQ/U7sQV0HSRwI/AAAAAAAACEs/2lGHanqeF90/s1...
- Grid, nonuniform pixel colors:
http://fc06.deviantart.net/fs71/f/2011/227/6/4/link_pixel_art_by_malandrus-d...
- Scan of a hand-filled grid paper:
http://th04.deviantart.net/fs71/PRE/f/2013/207/5/b/goku_pixel_art_by_hideman...
- Photographs:
http://fc03.deviantart.net/fs71/i/2013/336/1/6/glumanda_pixel_art_by_beffra-... 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:
- The pixels are laid out in a rectangular grid.
- Color within a pixel is uniform.
- 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 Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
participants (4)
-
Jabiertxo Arraiza Cenoz -
Krzysztof Kosiński -
Mark Schafer -
Tavmjong Bah