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.



Другие статьи номера:

От авторов - help: описание оболочки журнала.

От авторов - о содержании нового номера журнала.

От авторов - Forever young, или Спектрум в новом тысячелетии. Призыв Jam/XPJ к спасению журнала ZX Power.

От авторов - авторы журнала.

Презентация - новая игра от Studio Stall - Открывашка.

Презентация - новый редактор шрифтов Hewly Font Editor.

Презентация - новая версия музыкального редактора Sound Tracker Pro.

Презентация - программа для оптимизации черно-белых картинок сконверченных с PC.

Презентация - редактор ASCII графики для каталогов в TR-DOS.

Презентация - "Bard's Tale Merger Programm" - программа для работы с отгрузками из игры Bard's Tale.

Интерфейс - Новости от: Placebo, Brain- wave, Phantom Family, Volga Soft, Studio Stall, Gogin, Anarchia, Image Crew, Hackerz' Design Software, Петерс+, Fatal Snipe, Ellipse.

Интерфейс - посмотрим какие тусни намечаются для спекки фриков втечение года: Forever 3, ASCII^02, 2nd International Sinclair Sam days, Millenium 1902, Twilight Demoparty 2002, Syndeecate Demoparty 2002, Paradox 2002, CaFe 2002, Chaos Constructions 2002.

Интерфейс - письма читалей: NoViSeT/Brutal Creators, Di/LSg, Moroz1999, Shame/Madness Technology, Cannibal/Techno Lab.

Интерфейс - "за базар ответишь!" русский язык настолько "велик и могуч", что грамотно пользоваться им, к сожалению, дано далеко не всем.

Интерфейс - обзор Windows подобных оболочек и систем на ZX Spectrum.

Интерфейс - Город Дзержинск и его СПЕКТРУМовские обитатели.

Обмен опытом - Как написать 3D игру типа DOOM.

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

Обмен опытом - ненаучный алгоритм получения Случайных Чисел (RND).

Обмен опытом - прямое программирование General Sound.

Обмен опытом - работа с западными дисковыми системами MDOS и MD02.

Chaos Construction 2001 - интервью с Raid.

Chaos Construction 2001 - интервью с Stanly/Studio Stall.

Chaos Construction 2001 - интервью с Gogin (Hacker Smir).

Chaos Construction 2001 - интервью с Constellation Team: Screamer, Kot, Justinas.

Chaos Construction 2001 - интервью с EYE-Q: Organism, Time Keeper, Mr. Wizard.

Chaos Construction 2001 - интервью с Justionas/Constellation.

Chaos Construction 2001 - интервью с московским кодером Asman/Proxium.

Chaos Construction 2001 - интевью с Vivid, Megus, Tiggr из Brain-Wave.

Chaos Construction 2001 - интервью с Stingrey и Steep из Ижевска.

Chaos Construction 2001 - интервью с амижником и организатором CC - Big Black.

Chaos Construction 2001 - интервью с кодером из Ульяновска Faster/TNL.

Chaos Construction 2001 - интервью с Cyberfreak (mooh).

Chaos Construction 2001 - интервью с минским спектрумистом Equator/PHD.

Chaos Construction 2001 - мини интервью с Kano.

Chaos Construction 2001 - эпический спор: Vivid VS Sairoos, Chanks VS Multicolor, Dogma VS Triptomine Dream.

Chaos Construction 2001 - интервью с Maddy и Drv53b6 из Phantom Family.

Chaos Construction 2001 - интервью с Paracels и Sairoos из Placebo.

Chaos Construction 2001 - интервью с Pheel и EA из Antares.

Chaos Construction 2001 - продолжение эпического спора между мегакодерами Vivid и Sairoos.

Chaos Construction 2001 - подробный репортаж от CPU.

Раскрутка - Еще одна разрушенная мечта или описания "500 игр" - где правда, а где ложь.

Раскрутка - история создателей игры Star Glider 2 - Steven dunn/Software developement and design.

Раскрутка - Диззи в подземелье или Омлет опять не получился: новелла по игре Dizzy Unterground.

Раскрутка - описание игры "Talisman" - RPG с элементами аркады.

Железо - доработанная схема IDE-HDD адаптера.

Оттяг - чиста оттяг: детская самодельная газета "Птичке Кар-Кар".

Оттяг - intro: Не будем тянуть кота за яйца и начнем с прогона...

Оттяг - Army Suxx или Как закосить от армии, если ты полностью здоров.

Оттяг - глубины сумрачного мировосприятия Максима Магнетика...


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Новинки - ZX-Platinum No.1, International 3D Tennis, Color Lines.
Слабо пройти - Описание-прохождение игры Monstrland (миссия 4).
Anigdot №43 - HELLO AMIGOS (Испаский :) , а не AMIGA :( ) !!!

В этот день...   22 июня