Adventurer #13 31 марта 2002

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

Обмен опытом - Метод Floyd-Steinberg для конвертации картинок из большего числа цветов в меньший.

    (C) Research/Volgasoft

         Метод Floyd-Steinberg

    Давненько меня просили просветить на-
ших читателей на счет небезызвестного ме-
тода  FS. Что за зверь? - спросят некото-
рые из вас. Интересный зверек. Применяет-
ся  при  конвертации картинок из большего
числа разрядов (цветов) в меньший. Пример
-  3Color,  драйвера принтеров (<распыле-
ние>). И там и там принцип тот же.

    Вообще для дитеринга используют 4 ос-
новных метода:

    1) метод Флойда-Стеинберга (<распыле-
ние>);
    2) метод Байера (<матрица>, результат
напоминает  спектрумовские  чанки  (та же
матрица));
    3) метод порогового  сравнения интен-
сивности (тоже все видели ;) );
    4) метод 3 с подмешиванием равномерно
распределенного RND (лажа еще та:).

    Все методы, кроме ФС, можно придумать
самому. В методе Байера определенную сло-
жность вызывает вывод матриц, но раскинув
мозгами  матрицы  все же выводятся, а вот
ФС нахрапом не взять.

    Метод  -  математический.  Эти буржуи
его как-то вывели, это факт. Завалялся он
в  какой-то книжке издательства <Мир> ка-
жется,  года  80-го. Книженция ничего, но
сплошь  математика.  Не школьная, отнюдь.
Там  были и алгоритмы фильтрации, и алго-
ритмы  дитеренга,  и  cлужила  эта, и еще
пара  умных книжек, как положено, то бишь
подставкой для телевизора на работе у Ca-
che'а.

    В двух словах принцип: модифицируется
не  только текущий пиксель, но и соседние
-  слева,  снизу, и снизу-слева от нашего
пикселя  по  ходу  дитеренга.  Вот пример
реализации метода (из книжки):

 T=(white+black)/2; порог сравнения
 
 for y=yMax to yMin step -1
 for x=xMin to xMax; массив (X на Y)
 
 if i(x,y)<T; берем пиксель
 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
 
    Берем  пиксель,  сравниваем с порогом
сравнения. Если яркость меньше пороговой,
ложим на экран черный цвет, считаем ошиб-
ку равной пиксель минус черный.

    Если  же яркость больше пороговой, то
ложим на экран белый цвет, считаем ошибку
равной пиксель минус белый.

    И  раскладываем ошибку в соответствии
с картинкой:

             +------+------+
             |      |+3/8  |
             |pixel |ошибки|
             |      |      |
             +------+------+
             |+3/8  |+2/8  |
             |ошибки|ошибки|
             |      |      |
             +------+------+
 
    Ну  и переходим к следующему пикселю.
Вот и весь метод.

    Пример  реализации  - Free Art Demo -
4096 цветов.

    Привожу  кусок  из  нее в приложении.
Сразу скажу, что реализовать классический
FS можно только на приличной точности вы-
числений  -16.0,  а не 8.0 как в примере.
8.0  был предварен в жизнь тысяча и одним
подгоном.  Из-за  погрешностей вычислений
(деления)  и переполнений появляются <ды-
ры>  и <углы>. Доктор STS потом сделал FS
с  точностью  16.0  - загляденье, но 16.0
ест  больше  памяти  под матрицу и больше
регистров  для вычислений. Как дитерить -
слева направо, справа налево, сверху вниз
и т.д. - решайте сами:

    В примере FS используется одна строч-
ка  в  256  байт для хранения одной линии
<картинки> и 2 строки по 256 байт для ди-
теренга  (в методе обрабатывается всего 2
строки  матрицы).  Вощем,  лучше  туда не
смотреть, проще написать свой ;-))).

    Достоинства метода:

    1) лучшее качество;
    2) отсутствие дополнительных таблиц и
генераторов (в отличие от Байера и подме-
шанного RND) - хавает мизер памяти.

    Недостатки:

    1) большой объем вычислений, а следо-
вательно - тормознутость;
    2) если дитернуть картинку, а потом в
ней  где-нибудь поставить пиксель - нужно
дитерить заново, или как минимум с поста-
вленного пикселя и до конца.

    Вот так, вот. Чего с ним делать - уже
каждый придумал.. А я на сем прощаюсь.

    P.S.  что бы раскрасить ФС, переводи-
те-ка его лучше в чанки, допустим MacroE-
dit 'om,который выпущен в одном из после-
дних выпусков ADV.