(C) Research / Volgasoft
The method of Floyd-Steinberg
Long time I was asked to enlighten our readers on account
of the notorious method of FS. What kind of animal? - Ask some
of you. An interesting animal. It is used when converting
images from a larger the number of digits (colors) in the
least. Example - 3Color, printer drivers (). And
here and there the principle is the same.
In general, for dithering using 4 basic methods:
1) the method of Floyd-Steinberg (, the result
Recalls Spectrum chunks (the same
matrix));
3) method of comparing the intensity threshold (also all
seen;));
4) Method 3 with the admixture is uniformly
Distributed RND (still the same crap:).
All methods, except for FS, you can think of
himself. In the method of Bayer certain complexity is the
conclusion of the matrices, but stretched brains of the matrix
is still displayed, but FS unceremoniously not take it.
Method - Mathematics. These bourgeois
it somehow brought this fact. He was a stray
in some book publishers <World> think, the 80-th. Knizhentsiya
anything but entirely mathematics. Not school, not at all.
There have been filtering algorithms, and algorithms diterenga
and cluzhila this, and yet a pair of clever books, as expected,
I mean stand for the TV to work with Cache'a.
In a nutshell, the principle of: modified
not only the current pixel, but also neighboring
- Left, bottom, and bottom-left of our
pixel along the diterenga. Here's an example
implementation of the method (of books):
T = (white + black) / 2; threshold comparison
for y = yMax to yMin step -1
for x = xMin to xMax; array (X on Y)
if i (x, y) <T; take a pixel
then err = i (x, y)-black; i (x, y) = black
else
err = i (x, y)-white; i (x, y) = white
plot (x, y);
i (x +1, y) = i (x +1, y) +3 * err / 8
i (x, y-1) = i (x, y-1) +3 * err / 8
i (x +1, y-1) = i (x +1, y-1) +2 * err / 8
next x
next y
Take the pixel, comparing with threshold
comparison. If the brightness is less than the threshold,
We set the screen black, consider the error equal to the pixel
minus the black.
If the brightness above the threshold, then
We set the screen white, consider a mistake
equal to the pixel minus the white.
And decompose the error in accordance
with a picture:
+------+------+
| | +3 / 8 |
| Pixel | errors |
| | |
+------+------+
| +3 / 8 | +2 / 8 |
| Error | error |
| | |
+------+------+
Well, go to the next pixel.
That's the whole method.
Implementation Example - Free Art Demo -
4096 colors.
Here is a piece of her to the annex.
Go tell that to implement the classic
FS can only be a decent accuracy of the calculations -16.0, and
not 8.0 as in the example. 8.0 was preceded by a life a
thousand and one fitting. Due to errors in calculations
(Fission) and overflows occur <hole "and" angles>. The doctor
then made STS FS with an accuracy of 16.0 - feast for the eyes,
but 16.0 eats more memory for the matrix and more
registers for calculations. How Dieterich -
left to right, right to left, top to bottom
etc. - Decide for yourself:
In the example FS uses a single row of 256 bytes to store
one line and 2 rows of 256 bytes for diterenga (in the
method is processed by only 2 rows). Voschem, there will not
better See, it's easier to write your ;-))).
Advantages of the method:
1) Best quality;
2) the absence of additional tables and
generators (unlike Bayer and laced RND) - hawala minuscule
memory.
Disadvantages:
1) a large amount of computation, and therefore - Ping;
2) if diternut picture, and then in
it somewhere to put a pixel - to
Dieterich again, or at least supplied with the pixel to the end.
That's right, here. What to do with it - already
Each came up with .. And I'm on this and say goodbye.
P.S. that would paint the FS-ka translate it better in
chunks, say MacroEdit 'om, which is released in a recent issue
ADV.
