Adventurer #13 31 марта 2002

Программирование

Exchange of experience - Floyd-Steinberg method for converting images from a larger number of colors in the least.

    (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.