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