Subject:
|
Error Diffusion Dithering in LEGO (ministeck) mosaics
|
Newsgroups:
|
lugnet.build.mosaic
|
Date:
|
Thu, 13 Jan 2005 13:27:24 GMT
|
Viewed:
|
7031 times
|
| |
|
|
Before I started writing a program to create mosaics from my own pictures, I
needed lots of information on “how to reduce the colour palette of an image to a
custom colour palette”. I started searching on Google with simple keywords
“colour palette” and “dithering” (in the LUGNET mosaic maker you can choose
between a dithered image or an image without dithering), because I wanted to
find out more on the mathematical algorythms behind the dithering process (I
have a mathematical background myself).
The pages that I found particularly interesting were:
http://www.cs.princeton.edu/courses/archive/fall99/cs426/lectures/dither/sld001.htm
(pages 01 to 23)
http://www.compuphase.com/riemer.htm (check out the images
of “Lena”)
http://www.cs.indiana.edu/~dmiguse/Halftone/
and especially this one:
http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/floyd_steinberg_dithering.html
If you read these articles through carefully, then you will understand that the
“error diffusion dithering”-process always tries to approach the original image
with of course the use of a restricted number of colours.
Many programs claim
to have dithering possibilities such as Floyd-Steinberg, Burkes, or Stucki. But
when Bob Kojima contacted me to test the beta-version of his mosaic-maker
program, the first remark I had to make was that those algorythms were not the
real ones (probably just simplified variations of the original algorythms). If
you convert an image (grayscale or coloured) with an error diffusion dithering
algorythm, it is almost impossible to find several adjacent pixels in the same
colour (the largest brick used in my
Level 42
mosaic was a 1x8 tan brick - just 1 in the entire mosaic!). I now have to make
the same remark to Corey Sanders.
Here are a few examples: in these examples I use the Floyd-Steinberg error
diffusion dithering algorythm (not a variation). I don’t claim that the results
are the best (besides: I’m not a programmer); it is always possible that other
algorythms show better results (I tried to implement the Hilbert-curve, but that
didn’t work out well / I never tried to implement the Riemersma dithering
because it’s too theoretical and difficult, even for me). With mosaics out of
LEGO I can even reach better resolution with studs-up mosaics (pixel-heigth is
2/5 of pixel-width).
Picture 1: The original image sized to 160x192 pixels (that is 5x6 green
baseplates size 32x32 for LEGO, 2x3 baseplates size 80x64 for ministeck).
Picture 2: The original Floyd-Steinberg dithering algorythm which turns the
image in black & white.
Picture 3: Adding more “colour”: white, grey, black.
Picture 4: Adding more “colour”: white, grey, dark grey, black.
Picture 5:
In real colours: the most frequent colours white, yellow, red, blue and black.
Picture 6: White, grey, dark grey, black, yellow, red, blue, green, brown,
tan, orange, medium blue and lime (I chose these colours because they can all be
found in the large buckets in 2004).
Picture 7: No dithering; this is what
the image would look like if every pixel is simply converted to the best
matching LEGO-colour without error distribution to neighbouring pixels. This
method is particularly useful to create mosaics from cartoon characters (such as
my Bob the Builder
mosaic).
Picture 8: Because 1x1 elements represent only 5% of the total
amount of my ministeck mosaic pieces, I needed another algorythm that doesn’t
require so many 1x1 elements. The picture is “divided” in 7 shades of grey
(white, light-yellow, tan, earth-orange, dark-orange, brown and black). Changing
colour/brightness level may result in a better mosaic.
Picture 9: In my
ministeck assortment I have 9 brown-scales; with white and black added I have 11
colours (just like the mosaic of
my children).
Don’t sit with your nose on the screen if you look at the examples: take a few
steps back and the results are astonishing.
I am currently working on expanding my webpage with examples (both for LEGO- and
ministeck- enthousiasts): cartoon characters (no dithering) such as Bob the
Builder, Nemo and Winnie the Pooh; maybe I can add Cameron Diaz to the dithered
examples.
Maarten
(Maybe I shouldn’t have gotten involved in this discussion on dithering, but
once I’ve started I feel obliged to go on with it - it’s too late to crawl
back.)
|
|
Message has 3 Replies:
 | | Lifting a corner of the veil
|
| Tips & tricks: 1) If you decide to convert an image without dithering (e.g. a cartoon character), you may have noticed that a significant part of the image turns (dark) grey (in case this colour is in your list of colours to be used), even if you (...) (20 years ago, 7-Feb-05, to lugnet.build.mosaic, FTX)
|
17 Messages in This Thread:
  
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
