Info Guide #07 31 мая 2005

Софт     Графика

Ликбез - Принципы конвертирования графики PC-ZX.

            Принципы конвертирования графики PC->ZX
 

   Эта  статья  писалась последней по счёту и в страшной спешке,
поэтому извините за смурноту. Возможно, в будущем я напишу более 
подробную статью о конверсии. 

   Раньше предпочитали конвертировать в 3 экрана, т.к. это чрез─
вычайно просто: достаточно в Фотошопе выгрузить экран в 8 цветах
и  перебросить  точки  из  bmp в спектрумовский формат маленькой
программкой  на ZX (теперь эту операцию можно провести автомати─
чески  в любом JPEG вьювере для ZX). Но у 3 экранов есть сущест─
 венные недостатки:
   1. Страшно мерцают;
   2. Сплошной белый цвет особенно страшно мерцает;
   3. На показ картинки тратится 2/3 процессорного времени;
  4. Всего 8 цветов (а даже на 6912 и то больше),соответственно,
 экран покрыт "пылью", "перхотью"; 
  5. Картинка очень много весит.
   Как вы могли видеть,я предпочитаю конвертировать в два экрана
или  в один. Один  экран  даёт  более грубое изображение, но его
значительно легче использовать в программе. Многие сюжеты вполне
прилично смотрятся на одном экране. Два экрана позволяют отобра─
зить  практически что угодно. Два экрана дают 83 цвета, если ис─
ходить из предположений о том, что:
- тёмный цвет светится вдвое слабее яркого;
- "чёрный"+"ярко-красный"="тёмно-красный"+"тёмно-красный" и т.п.
 

   .img (Gigascreen) - это просто 2 экрана со стандартной разли─
новкой.
   А вот что такое .mcx:
- 1-й экран спрайтом; 
- атрибуты 1-го экрана спрайтом; 
- 2-й экран спрайтом; 
- атрибуты 2-го экрана спрайтом. 
   Такие  картинки вы могли видеть в игре Hexagonal Filler. Есть
 идеи упрощённых mcx-режимов:
   a) один из экранов всегда ч/б;
  b) один из экранов чисто спектрумовский.
   Эти упрощённые режимы легко выводятся без турбо,без искажения
картинки.

   Представляю  вашему  вниманию конвертор на Delphi, написанный
от  нужды  и  не  предназначавшийся  для настоящего релиза (я не
намереваюсь  становиться  пцшным программером), но старая версия
которого  распространялась в оболочке SpeConvertor by Aprisobal.
Именно  им  я конвертирую графику для IG (до этого я использовал
8col ). Разумеется,  результат  конверсии  приходится  подчищать 
вручную  (экраны  6912 - в  BGE, экраны  img - в DBS ), но общий
результат вполне положительный.

   Экран  ZX  состоит  из  знакомест.  Поэтому  нужно  найти для
каждого   знакоместа  самую  удачную  палитру.  При  этом  можно
учитывать  "средний  цвет"  по  картинке,  а можно рассматривать
каждое   знакоместо  как  отдельное.  Но  настоящая  отдельность
реализуема только при конверсии с diamond (чанковой) штриховкой,
которая  даёт  достаточно размытое изображение. При конверсии со
Флойдом-Стейнбергом  нужно  распространять ошибку представления,
накопленную на краевых точках знакоместа, вправо и вниз.
   Теперь  небольшое  замечание.  Я держу ошибку не в регистрах/
переменных,  а  непосредственно  в  массиве,  хранящем  исходную
картинку.  То есть если я говорю "распространяю ошибку", то имею
в  виду,  что  просто  исправляю 4 пиксела (справа, снизу, слева
снизу  и  справа снизу от текущего), добавляя к ним ошибку пред─
ставления  текущего пиксела с коэффициентами соответственно 1/2,
1/4, 1/8 и 1/8. 
   Сначала   я   хотел  обрабатывать  границы  знакомест  особым
образом:  распространять ошибку пикселов, стоящих на правом краю
знакоместа,  по  всем  8  следующим справа точкам. Но получилось
отвратительно.  Поэтому  в  текущей  версии  конвертора  границы
знакомест  никакого  исключения из себя не представляют. К левой
границе  экрана  можно отнестись особенным образом: во избежание
появления  около  неё  сплошных  вертикальных  линий к цветам её
пикселов  прибавлять  некоторое  случайное  число. Это опасно на
сплошном  чёрном  или  белом  фоне. Но такую операцию производит
8col при конверсии из img/mcx в 8 цветов. 

   Рассказывать  буду  именно  о  проблемах  конверсии  именно в
img/mcx, конверсия в 6912 несколько проще (такой конвертор легко 
сделать из конвертора img/mcx упрощением программы)...

   Условно  обозначим  уровни каждой цветовой составляющей через
b0,b1,b2,b3,b4 (от  нуля  до  самого яркого) и получим наглядную 
таблицу  всех  цветов  (в  каждой скобке - уровни: r,g,b; справа
помечена включенная яркость: "B" ):
(b0,b1,b2)(b0,b2,b1)(b1,b0,b2)(b1,b2,b0)(b2,b0,b1)(b2,b1,b0) 
(b0,b1,b3)(b0,b3,b1)(b1,b0,b3)(b1,b3,b0)(b3,b0,b1)(b3,b1,b0) B 
(b0,b2,b3)(b0,b3,b2)(b2,b0,b3)(b2,b3,b0)(b3,b0,b2)(b3,b2,b0) B 
(b0,b2,b4)(b0,b4,b2)(b2,b0,b4)(b2,b4,b0)(b4,b0,b2)(b4,b2,b0) BB 
(b1,b2,b3)(b1,b3,b2)(b2,b1,b3)(b2,b3,b1)(b3,b1,b2)(b3,b2,b1) B 
014,124,234,034,134 нет 
(b0,b0,b1)(b0,b1,b0)(b1,b0,b0)(b0,b1,b1)(b1,b0,b1)(b1,b1,b0) 
(b0,b0,b2)(b0,b2,b0)(b2,b0,b0)(b0,b2,b2)(b2,b0,b2)(b2,b2,b0) 
(b0,b0,b3)(b0,b3,b0)(b3,b0,b0)(b0,b3,b3)(b3,b0,b3)(b3,b3,b0) B 
(b0,b0,b4)(b0,b4,b0)(b4,b0,b0)(b0,b4,b4)(b4,b0,b4)(b4,b4,b0) BB 
(b1,b1,b2)(b1,b2,b1)(b2,b1,b1)(b1,b2,b2)(b2,b1,b2)(b2,b2,b1) 
(b1,b1,b3)(b1,b3,b1)(b3,b1,b1)(b1,b3,b3)(b3,b1,b3)(b3,b3,b1) B 
(b2,b2,b3)(b2,b3,b2)(b3,b2,b2)(b2,b3,b3)(b3,b2,b3)(b3,b3,b2) B 
(b2,b2,b4)(b2,b4,b2)(b4,b2,b2)(b2,b4,b4)(b4,b2,b4)(b4,b4,b2) BB 
14,34 нет 
(b0,b0,b0)(b1,b1,b1)(b2,b2,b2)(b3,b3,b3)(b4,b4,b4) 
   Имея  такую широкую палитру, мы можем спокойно отображать как
телесные  цвета,  так  и  яркие  краски,  не  портя  их излишним
количеством "перхоти".
   Но помимо этой палитры нам нужно иметь в виду палитру другую:
множество  всех  наборов (i1,p1,i2,p2), то есть атрибутов знако─
места  на  обоих  экранах.  Сколько  из  них можно использовать,
совершенно неизвестно (ручной подсчёт - огромная работа,чреватая
ошибками). Я составил статистику по приблизительно 20 картинкам,
конвертируя  их  простым  перебором цветов в палитрах, и получил
файл  tablo.dat  (см.исходник  в  приложении),  содержащий  1708
палитр.  Палитры  отсортированы  по  частоте  использования,  но
ограничение  самыми  частыми 256 палитрами и даже самыми частыми
пятьюстами ни к чему хорошему не приводило...
   
   Вот  как  я  перебирал  цвета  в  палитрах  до появления этой
таблицы:
for b1:=0 to 1 do for b2:=b1 to 1 do 
for i1:=b1 shl 3 to b1 shl 3+6 do 
for i2:=i1+1 to b1 shl 3+7 do 
for i3:=b2 shl 3 to b2 shl 3+6 do 
for i4:=i3+1 to b2 shl 3+7 do begin 
... 

   А вот как перебираю теперь:
for ti:=0 to datcnt {1707} do begin 
i1:=tablo[ti,0];i2:=tablo[ti,1];i3:=tablo[ti,2];i4:=tablo[ti,3]; 
... 

   Внутри цикла происходит оценка качества выбранной палитры. За
таковую  оценку  принимается  сумма ошибок представления всех 64
пикселов  знакоместа  цветами  из  выбранной  палитры. За ошибку
представления  в данном случае принимается евклидово расстояние.
Но  простая сумма абсолютных величин разностей по 3 составляющим
даёт  результат ничуть не хуже. Почему тогда sqr, а не abs?  Так
оказалось, что на пц sqr работает быстрее...
   Расстояние  берётся между рассматриваемой точкой знакоместа и
самым  подходящим  цветом  рассматриваемой  палитры. В палитре 4
цвета (i1+i2, i1+p2, p1+i2, p1+p2), но в их число также добавля─
ется 5-й "средний" цвет: (i1+p1+i2+p2)/2. Раньше вместо 5 цветов
было 9, но разница на результирующей картинке почти незаметна.
   Этот перебор - самое медленное место всей программы.
    Как его ускорить?
  1. Прерываемся, не перебрав  все пикселы, при накоплении чрез─
вычайно большой суммарной ошибки  по данной палитре. Чрезвычайно
большой  ошибкой является такая, которая превышает найденный для
предыдущих  палитр  минимум  (хотя можно предложить вариант, при
котором  мы  прервёмся,  если, например, после 40 пикселов из 64
 превысили половину минимума).
  2. Этот  минимум  перед  перебором  всех палитр предварительно
ищется  для  палитры  предыдущего  (соседнего  слева или сверху)
знакоместа,  поскольку она имеет шансы быть самой удачной палит─
 рой и для текущего знакоместа.
  3. Этот  минимум  для  предыдущего  знакоместа  умножается  на
коэффициент,  меньший  единицы  (например, на  0.75 ) - тогда мы
будем  чаще  выбирать  предыдущий  цвет,  но  зато будем быстрее
выходить из расчёта ошибки по палитре.

Diver> 
Ты уверен, что выбираешь наиболее подходящие сочетания цветов? 
Alone Coder> 
Совершенно не уверен, иначе бы не было полосатых небес. 

   "Полосатые  небеса"  возникают  на широких областях картинки,
покрытых   цветами,   которые  нельзя  точно  представить  двумя
экранами.  А  такие  цвета  есть. Ведь если представить себе все
возможные цвета как некий куб (одна координата - R, 2-я - G, 3-я
- B), то  даже самая лучшая найденная нами палитра представляет
всего  лишь  параллелограмм  (некую  "плоскость  цветов") внутри
этого  куба.  А  поскольку  число палитр конечно, то они явно не
заполняют всё пространство внутри куба.
   Вот  этот  куб,  в  нём  параллелограмм, изображающий одну из
палитр,  а на параллелограмме те самые 5 точек, цвета которых мы
сравниваем с данной точкой:






















   Как найти лучшую палитру, зная об этом недостатке?  Возможно,
конвертор  должен  по  мере  сил избегать менять текущую палитру
(точнее,  реально  использованные  из  неё  цвета) на протяжении
более-менее  однотонного  (без изломов и границ) цветового пятна
на картинке. Но как это реализовать? Пока неизвестно.

Вот отрывок из моего письма к Diver'у:
 ──────────────────────────────────────────────────────────────── 
   Чем  у нас отличается 2-битплановая палитра от обычной?  Тем,
что   она  определяет  в  цветовом  кубе  не  отрезок,  а  часть 
плоскости (параллелограмм), все цвета внутри которого могут быть 
 определены нашей палитрой с помощью штриховок (точно). 
   Чем  у нас отличается знакоместо 8x8 от знакоместа 1x8?  Тем,
что    на    равномерном    участке   картинки   (без   изломов) 
использованные   в   знакоместе   цвета  определяют  в  первом - 
некоторую цветовую ПОВЕРХHОСТЬ, а во втором - некоторую цветовую 
ЛИHИЮ.  Таким  образом, нам нужно найти цветовой ПАРАЛЛЕЛОГРАММ, 
который  наиболее  точно  опишет  цвета  нашей цветовой ЛИHИИ, а 
ошибку   представления  запомним  и,  чтобы  она  не  пропадала, 
 прибавим к цветам нижележащего знакоместа. 
   Лучшим  ПАРАЛЛЕЛОГРАММОМ  будет такой параллелограмм, который
имеет минимальной некоторую суммарную ошибку представления точек 
знакоместа.  Всего  различных форм параллелограммов в 27-цветной 
(упрощенной)  палитре с известными нам ограничениями существует, 
если  мне  не  изменяет склероз, 20, а сколько в 83-цветной - не 
считал,  а  сколько всего не ФОРМ, а ШТУК различных палитр - тем 
 более хрен знает :) 
   У  меня  суммарная ошибка считается, сам знаю, неправильно, а
именно  так:  как сумма квадратов отклонений (по формуле длины в 
евклидовом  пространстве,  с разными коэффициентами для R, G, B) 
от девяти опорных точек цветового параллелограмма, которые точки 
лучше  всего  описываются  палитрой  этого  параллелограмма. Сам 
 знаешь, что это за 9 цветов :) 
   Почему этот метод неправильный? потому что он может посчитать
лучшей   такую  палитру,  что  все  точки  знакоместа  придутся, 
например,  по  одну сторону от параллелограмма, и всё знакоместо 
замажется  одним цветом, при этом у всех ошибок будет один и тот 
же знак. 
──────────────────────────────────────────────────────────────── 

    Меня позже посещала такая идея:
  1. Яркости  90%  пикселей знакоместа должны попасть в диапазон
 яркости, задаваемый выбранной палитрой. 
  2. Область  на  плоскости  UV  (Cb=Y-B,  Cr=Y-R),  заполненная
пикселями  знакоместа,  должна  на  90% попасть в палитру (нужна 
 таблица: для каждой палитры значения minU, maxU, minV, maxV ). 
  3. То  же,  что  (1, 2), но  в координатах  RGB, тогда область
цветового  пространства будет задана более точно, чем параллело─ 
 граммом. 
  4. Из равноподходящих палитр выбрать самую узкую.
   Эту  идею  надо  обдумать...  Она  должна  не только улучшить
качество   картинки,  но  и  ускорить  конверсию,  что  позволит
написать на ZX аналогичный конвертор.

   Отдельная  проблема - с  чанковой  штриховкой.  Она  пакуется
значительно  лучше  Флойда,  поэтому  области без мелких деталей
лучше  конвертировать  именно  через  неё.  Как видите, у меня в
конверторе  есть  для  такого выделения специальная кисточка. Но
попробовав помазать ею на img картинке, вы, скорее всего, будете
разочарованы  результатом - поплывут  цвета. Почему?  Не знаю. Я
исходил из очевидного для одноэкранной конверсии метода.
   Метод такой.
   Рассматриваем палитру как отрезок в RGB кубе, а цвет, который
нужно представить этой палитрой, как некую точку в этом же кубе.
Требуется  найти уровень штриховки (от 0 = чистого paper'а, до 1
= чистого ink'а). Создаём  на нашем отрезке числовую ось: ставим
0 на paper'ном конце  и 1 на ink'овом. Опускаем перпендикуляр из 
точки  на  отрезок.  Координата основания перпендикуляра и будет
искомым уровнем (если он меньше 0, то считаем нулём, если больше
1, то считаем единицей). 
   Этот метод даёт для чанковой штриховки такие же уровни, что и
Флойд.
   Усложняем метод для случая img.
   Создаём  на  параллелограмме нашей палитры координатную сетку
(по  углам  опять  нули  и  единицы).  Опускаем перпендикуляр на
плоскость  параллелограмма. Берём координаты основания перпенди─
куляра  (опять-таки  с  отсечением  переполнения) - они  и будут
плотностями штриховки на 1-м и 2-м экранах.
   Если  все  цвета  в палитре лежат на одной прямой (параллело─
грамм выродился в отрезок), то метод не срабатывает - приходится
применять шаманский пересчёт.
   И  всё  равно  результирующий  уровень штриховки почему-то не
совпадает  с  Флойдовским...  Может  быть,  я  неправильно вывел
формулы? Бывает...

   Что ещё есть в конверторе:
  - dithering level  -  уровень  "пыльности"  цветов, близких  к
чистым.  Если равен 1, то все цвета будет "пыльными". Если 0, то
будет  использоваться  ровно  две градации. Аналогичный параметр
есть  в  Фотошопе,  в моей версии JPEG и в моём видеоконверторе.
Без него конвертировать бессмысленно.
  - saturation - цветность ( 0 - ч/б, 1 - обычный  уровень цвет─
ности, 1.5 - чуть повыше, а вообще  можно повышать без ограниче─
ний). Без этого параметра конвертировать тоже бессмысленно.
  - чанковая штриховка есть в 2 вариантах: 65 уровней (8x8) - по
умолчанию, - и 5 уровней (2x2).
  - можно запретить использовать два уровня bright при конверсии
(иногда позволяет избежать излишней "квадратности" изображения).
  - при  елозении  мышкой  по  ZX  экрану  можно видеть атрибуты
каждого  знакоместа  (для  img/mcx - отдельно  по  1-му  экрану,
отдельно по 2-му).
  - dithering level  можно менять и во время кистемазания чанко─
вой  штриховкой (левая кнопка мышки - чанковая штриховка, правая
- Флойд).  Кистемазание  работает  только  в  том  случае,  если
картинка  изначально  конвертировалась  в  режиме  Floyd. Размер
кисточки  можно  менять.  После кистемазания нужно нажать кнопку
Save. 
  - квадратная  кнопка  слева  снизу  выключает изображения (для
тех, у кого на работе начальник за спиной :)).
  - выбирать  границы,  по  которым будет урезаться изображение,
можно  вводом  цифр,  а можно кликанием на самой картинке: левой
кнопкой (один угол) и правой кнопкой (другой угол).
  - ZX картинки  во всех форматах, которые программа умеет гене─
рировать, она умеет также загружать.
  - обо всех форматах (в том числе emg, который нигде не исполь─
зуется) читайте в справочнике Nuts'а "sprites.txt".
  - модуль tgapng - моя старая курсовая работа. Можете использо─
вать  в своих программах (там есть функции не только для загруз─
ки,  но  и для  выгрузки  этих  форматов). Исходник GifImage (by
Anders Malender ) я записывать не стал - он очень  большой. Если 
нужно, поищите  где-нибудь  в инете.  Исходника jpeg.dcu у меня,
кажется, нет.
   Я  проверил  архив:   на  Delphi 6  программа  компилируется.
Если у вас  будут  проблемы с компиляцией, выкиньте из программы
все левые  форматы  (jpg, gif, png, tga) вместе  с их модулями -
останется формат bmp.

A. Coder