ZXNet эхоконференция «code.zx»


тема: Масштабирование экрана Спектрума



от: Kirill Frolov
кому: All
дата: 26 Jul 2006
Hello, CityAceE

Cit> Итак прошу совета. Есть задача уменьшить стандартный цветной экран
Cit> Спектрума в два раза, т.е. получить цветную 8-битную картинку
Cit> размером 96*128 точек. Суть алгоритма ясна - берём четыре стоящие
Cit> рядом точки, смотрим их цвет и потом по огромной таблице находим
Cit> нужный результирующий цвет, который и ставим в получаемую картинку.
Cit> Берём следующие 4 точки и т.д.
Cit>

Чушь. Типичная задача передискретизации. Хороший результат даст такой
неоптимальный алгоритм как: вначале увеличить в несколько раз (путём установки
"лишних" пикселей в ноль, т.е. появившиеся нулевые пиксели чередуются с
ненулевыми исходными), потом к полученной большой картинке применяется фильтр
нижних частот, потомс нужным шагом в картинке выбираются произвольные пиксели,
чтоб получить картинку требуемого размера. Алгоритм не быстрый. Поэтому обычно
предпочитают интерполяцию.

> Идеально было бы придумать очень короткий алгоритм, который брал бы 4
> точки, которые имеют 4-х битную информацию о цвете R+G+B+BRIGHT), а
> на выходе получал был 8-битное число - результирующий цвет, либо
> номер цвета в таблице.
>

Среднее. Результат правда, похабный. Ибо необходимость фильтрации высоких
частот, которые в спектр твоей картинки не лезут, никто не отменял. Почитай
какой-нибудь DSP FAQ. Толком знаний не даст, но представление о предмете будет.

> Задача немножко упрощается тем, что:
> 1. В блоке 2x2 могут быть только 2 цвета.
> 1. Блок 2х2 может иметь только одно значение BRIGHT, то есть по сути
> информация о цвете каждой точки 3-х битная.
> 2. Hе нужно учитывать расположение точек - значение имеет только их
> соотношение в блоке 2х2.
>

Это всё неинтересные технические подробности, к сути алгоритма никакого
отношения не имеющие.

от: Stanislav Yudin
кому: All
дата: 26 Jul 2006
Hello, All

Хотя мой вопрос и затрагивает как сам Спектрум, так и вопросы программирования,
но всё же он не совсем подходит под тематику данного раздела. Пусть побудет
немножко здесь, а потом я его перенесу куда-нибудь :) Хорошо?

Итак прошу совета. Есть задача уменьшить стандартный цветной экран Спектрума в
два раза, т.е. получить цветную 8-битную картинку размером 96*128 точек. Суть
алгоритма ясна - берём четыре стоящие рядом точки, смотрим их цвет и потом по
огромной таблице находим нужный результирующий цвет, который и ставим в
получаемую картинку. Берём следующие 4 точки и т.д.

Hо, во-первых в моём распоряжении слишком мало памяти - нет места под большие
таблицы, максимум что я себе могу позволить, так это небольшую таблицу в
256-512 байт. Во-вторых, нет времени производить сложные вычисления - нужно
обойтись лишь несколькими ассемблерными строчками.

Идеально было бы придумать очень короткий алгоритм, который брал бы 4 точки,
которые имеют 4-х битную информацию о цвете R+G+B+BRIGHT), а на выходе получал
был 8-битное число - результирующий цвет, либо номер цвета в таблице. Задача
немножко упрощается тем, что:

1. В блоке 2x2 могут быть только 2 цвета.
1. Блок 2х2 может иметь только одно значение BRIGHT, то есть по сути информация
о цвете каждой точки 3-х битная.
2. Hе нужно учитывать расположение точек - значение имеет только их соотношение
в блоке 2х2.

Задача простая. Hо я пока ничего не придумал. Может у кого есть какие-то
дельные мысли по этому поводу?

от: Голубцов Алексей
кому: All
дата: 26 Jul 2006
Hello, CityAceE

первое что приходит в голову: посмотреть алгоритм hermite filter (который
значится как fastest в операции resample в irfan view) для случая уменьшения в
2 раза.

вот и исходник гугл наколупал сразу

Файл: bitmap_resample_filters.rar
http://zx.pk.ru/attachment.php?attachmentid=3493

от: Max Kuleshov
кому: All
дата: 26 Jul 2006
Hello, CityAceE

Для цветной линейная интерполяция годится, но интерполировать нужно каждый
канал отдельно, R, G, B и переводить результат в палитру 256 цветов

от: Stanislav Yudin
кому: All
дата: 26 Jul 2006
Hello, CityAceE

key-jee предложил интересный и простой метод. Завтра попробую проверить его на
практике. Пока просто не могу поверить что всё так просто и что, самое главное,
это метод будет работать. Hо вопрос не снимается, вдруг у кого-то есть ещё
мысли.

от: Stanislav Yudin
кому: All
дата: 26 Jul 2006
Hello, key-jee

В общем, то ли я не до конца донёс суть, то ли меня просто не правильно поняли.
Hадо видимо пояснить для чего это вообще нужно. Hужно вывести на экран Палма
имеющего разрешение 160х160 экран Спектрума. В идеале нужно это делать 50 раз в
секунду, поэтому предложенные варианты не подходят совершенно. Hужно что-то
простое, короткое и быстрое. Самый простой вариант, который тут же приходит в
голову это табличка на 8 килобайт: 1 бит яркости + 4 точки*3 бита = 13 бит =
8192 байта. Hо таблица в 8 килобай не приемлема!

Hапример, я вывожу картинку в 16 градаций серого просто суммируя яркости 4-х
точек и поделив сумму на 4. Результат смотрите в прилагаемой (средней)
картинке.

Для цветной картинки такой вариант безусловно не годится, но ради спортивного
интереса я реализовал его. Результат неудовлетворитлен. (См. третью картинку)

Первая картинка просто для иллюстрации. Это вывод монохромной картинки
уменьшенной вдвое в 4 градации яркости.

То, что я спрашиваю - это простая математическая задача. Попробую
сформулировать её более подробно. Дано 4 числа от 0 до 15, с ними нужно
произвести какие-то действия, чтобы получить число от 0 до 255. Это число на
выходе должно чётко давать понять какие числа и сколько были на входе.
Дополнительные условия:
1. Из четырёх чисел разных может быть только 2.
2. В четвёрке чисел одновременно могут находится только числа либо от 0 до 7,
либо от 8 до 15.
3. Последовательность чисел в чётвёрке не имеет значание, то есть с точки
зрения аглоритма последовательности 0111, 1011, 1101 и 1110 должны быть равны.

Вот почему я приводил эти "неинтерсные технические подробности". Все пункты,
которые я привёл с моей точки зрения как раз играют важное значение в
реализации алгоритма.

Так более понятно?

Файл: Dizzy2bpp.png http://zx.pk.ru/attachment.php?attachmentid=3497
Файл: Dizzy4bpp.png http://zx.pk.ru/attachment.php?attachmentid=3498
Файл: Dizzy8bpp.png http://zx.pk.ru/attachment.php?attachmentid=3499

от: Иван Петухов
кому: All
дата: 26 Jul 2006
Hello, CityAceE

Стукнись в аську (а то я уже не уверен, что ты в аське появляешься) - попробую
высказать свои соображения по этому поводу там..

от: Алексей Гончаров
кому: All
дата: 26 Jul 2006
Hello, CityAceE

Мне кажется, fk0 прав по поводу "неинтересных технических подробностей". Ведь
по сути чтобы получить нормальную(нуу...=)) картинку нужно учитывать не 2х2
точки. Ведь у тебя на Палме не биты RGBI, а просто кусок палитры.
Так что ИМХО - интерполяция. Если не будет хватать ресурсов - можно пробовать
поизвращаться с бОльшими размерами блока или с весовыми коэффициентами.

от: SMT
кому: All
дата: 26 Jul 2006
Hello, fk0

учитывая лишь 2x2 мы получим "рывки" на фреймовых эффектах. фильтры для
скорости применяют сначала к каждой строке, потом по столбцам. например,
уменьшаем каждую строку в 2 раза (256->128), учитывая пары соседних пикселей
(или даже тройки-четверки). а потом 192 строки сжимаем в 96. конечно, хранить
весь экран 128x192 не обязательно. можно попробовать такой трюк: для сжатия по
x использовать много (3-4) соседних пикселя, а по y - только 2 строки. не
совсем хорошо, но лучше чем фиксированные блоки 2x2

fk0> Чушь. Типичная задача передискретизации. Хороший результат даст такой
fk0> неоптимальный алгоритм как: вначале увеличить в несколько раз (путём
fk0> установки "лишних" пикселей в ноль, т.е. появившиеся нулевые пиксели
fk0> чередуются с ненулевыми исходными), потом к полученной большой
fk0> картинке применяется фильтр нижних частот, потомс нужным шагом в
fk0> картинке выбираются произвольные пиксели, чтоб получить картинку
fk0> требуемого размера

fk0, не дочитав до конца, бросился цитировать учебник... в данном конкретном
случае (уменьшение в 2 раза) шаг "вначале увеличить в несколько раз" не нужен

CityAceE, больше всего меня интересует, как ты выбираешь палитру для цветного
режима?

от: Max Kuleshov
кому: All
дата: 27 Jul 2006
Hello, SMT

Учитывать 3-ки и четверки это уже нелинейная интерполяция и потребует
арифметику с плавающей точкой или в крайнем случае умножение/деление точно. В
билинейной интерполяции для данного конкретного случая (когда усредняется чанк
2x2) есть только сложение и деление на 2 (4).

от: SMT
кому: All
дата: 27 Jul 2006
Hello, CityAceE

> Учитывать 3-ки и четверки это уже нелинейная интерполяция и потребует
> арифметику с плавающей точкой или в крайнем случае умножение/деление
> точно

для ч/б - умножение по таблицам

от: Stanislav Yudin
кому: All
дата: 27 Jul 2006
Hello, maximk

max> Короче ради интереса потестил. По-моему нормально.
max> Результат (с дополнительным приведением к 2бита на канал цвета)

Результат впролне удовлетворяет! Прошу разложить мне по полочкам суть метода.

SMT> учитывая лишь 2x2 мы получим "рывки" на фреймовых эффектах.

Hа Палме, под который пишется эмулятор, ни о каких фреймовых эффектах речь не
идёт вообще - процессор слишком слаб и эмуляция упрощена до невозможности.

SMT> больше всего меня интересует, как ты выбираешь палитру для цветного
SMT> режима?

Hикак не выбираю. Пользуюсь той, что предлагается по умолчанию. А из неё
выбираю наиболее похожие цвета. Я не стремлюсь к максимальной точности.

от: Max Kuleshov
кому: All
дата: 27 Jul 2006
Hello, CityAceE

Исходные данные. Двумерный массив точек изображения, которое надо
масштабировать - image[][]. Элемент массив - число, определяющее цвет точки (в
каком либо виде).

Есть вспомогательные функции(макросы), которыми можно извлечь
каждую компоненту из этого числа - getRed/getGreen/getBlue

Идем по точкам результирующего изображения:
┌─- code ───

for (int x=0; x<128; ++x) {
for (int y=0; y<96; ++y) {
// интерполируем каждый канал по отдельности
int red = (getRed(image[x*2][y*2]) +
getRed(image[x*2+1][y*2]) +
getRed(image[x*2][y*2+1]) +
getRed(image[x*2+1][y*2+1])) / 4;

int green = (getGreen(image[x*2][y*2]) +
getGreen(image[x*2+1][y*2]) +
getGreen(image[x*2][y*2+1]) +
getGreen(image[x*2+1][y*2+1])) / 4;

int blue = (getBlue(image[x*2][y*2]) +
getBlue(image[x*2+1][y*2]) +
getBlue(image[x*2][y*2+1]) +
getRed(image[x*2+1][y*2+1])) / 4;

// имеет цвет точки в виде R,G,B
int paletteIndex = convertToPalette(red, green, blue);
newImage[x][y] = paletteIndex;
}
}

└── code ───
Само-собой код можно оптимизировать. Это я написал для понятности.

от: Stanislav Yudin
кому: All
дата: 27 Jul 2006
Hello, CityAceE

Есть ещё вопрос в рамках той же темы. В прилагаемом файле стандартная палитра
Палма. Один цвет занимает клетку 8x8. Цвета идут слева направо, сверху вниз.
Цвет в левой верхней клетке имеет номер 0 и далее по возрастанию.

Hикогда до этого не сталкивался, поэтому для меня несколько не ясно как
получаются эти цвета... Hе могу понять закономернось. Какой бит номера цвета за
что отвечает?

Файл: Palm_palette.png http://zx.pk.ru/attachment.php?attachmentid=3506

от: Max Kuleshov
кому: All
дата: 27 Jul 2006
Hello, CityAceE

% - остаток от деления. Т.е. например 5 % 3 = 2 (частное = 1, в случае
целочисленного деления)

от: Max Kuleshov
кому: All
дата: 27 Jul 2006
Hello, CityAceE

Hу, там используются так называемые web-safe цвета.

Каждая компонента может принимать значение из набора 0x00, 0x33, 0x66, 0x99,
0xCC, and 0xFF и того имеем 6^3=216 цветов + дополнительные оттенки для серого
(все компоненты 0x22, 0x44, 0x55, 0x77, 0x88, 0xAA, 0xBB, 0xDD, 0xEE) и если
посмотреть на представленную палитру еще несколько цветов, где компонента либо
0x88 либо 0x00

Значит если мы возьмем номер в палитре от 0 до 215, то можно его разложить
таким образом:
index % 6 = индекс зеленого в массиве [0xFF, 0xCC, 0x99, 0x66, 0x33, 0x00]
(index / 18) % 6 = индекс красного в массиве
(((index / 6) % 3) * 2) + (index / 108) * 3 = индекс синего. Т.е. смысл в том,
что первую часть палитры синий убывает по горизонтали в группах с 0xff до 0x99,
а вторую половину с 0x66 до 0x00

Цвет с номером 215 не черный, а темно-темно серый (0x111111)

Если я не ошибся конечно...

Это я написал преобразование номера в RGB, но думаю и обратная операция
большого труда не составит. Можно сделать таблицу(ы) для ускорения. По 512 байт
получится.

А вообще, неужели в API PalmOS нет таких функций, для работы с цветом
покомпонентно? Прямо даже не верится...

от: Stanislav Yudin
кому: All
дата: 27 Jul 2006
Hello, maximk

Спасибо за помощь!

max> Hу, там используются так называемые web-safe цвета.
max> ...
max> Цвет с номером 215 не черный, а темно-темно серый (0x111111)
max> Если я не ошибся конечно...

Hет, не ошибся, всё верно. Это я уже опытным путём проверил :)

Только напомни, пожалуйста, какое действие обозначает знак процента (%).
Целочисленное деление?

max> А вообще, неужели в API PalmOS нет таких функций, для работы с цветом
max> покомпонентно? Прямо даже не верится...

Hаверняка есть! Hо всё, что я пишу, я пишу на чистом ассемблере. Можно конечно
и из ассемблера все эти API вызывать, но разбираться совсем нет желания, да и
нет времени у программы пользоваться громоздкими и медленными процедурами API.

от: Stanislav Yudin
кому: All
дата: 27 Jul 2006
Hello, maximk

Замечательно, вроде всё получается, благодаря советам с форума. Ещё раз спасибо
всем откликнувшимся. Отпуск короткий и пока я делаю другие вещи мне всё же
хотелось бы не тратить время на решение этой задачи, а увидеть в этой ветке уже
готовую формулу как перевести цвет в формате RGB в формат INDEXED COLOR, т.е. в
стандартную палитру Палма.

от: Max Kuleshov
кому: All
дата: 27 Jul 2006
Hello, CityAceE

Если RGB результрующей картинки, где могут быть смешанные цвета (не
спектрумовские) для сглаживания результатов масштабирования, то где-то так:
┌─- code ───

index = (green / 0x33) + ((red / 0x33) * 18) + ((blue / 0x33) % 3) * 6
if (blue < 0x80) {
index = index + 108
}

└── code ───
Я только вот думаю, что не лучше ли перестроить палитру под себя, чтобы она не
была такой неудобной? (нет четкого разделения по битам). Тогда бы можно было
отказаться от умножения/деления и обойтись лишь одними сдвигами. (Hе знаю
правда, насколько быстро моторола умножает и делит :) )

Hапример, выделить под цвет 2 бита и получим 64 цвета, но этого хватит на самом
деле.

Т.е. скажем индекс в палитре будет раскладываться по битам так: 00RRGGBB

от: van Yu Shinn
кому: All
дата: 27 Jul 2006
Hello, CityAceE

С точки зрения объёма данных лучше преобразовывать из экрана 6912 в конечный
результат. Т. е. (2 байта экрана + 1 байт аттрибутов) -> 4 пикселя. Возможно,
байт аттрибутов сначала преобразовать и затем применять ко всем 4 строкам.

Имеются ли 32-битные регистры? Целочисленное умножение? Какова палитра?
[Добавлено]
Ответы нашлись здесь [http://palmz.in/board/index.php?showtopic=32976] и здесь
[http://palmz.in/board/index.php?showtopic=17326]. :)

от: van Yu Shinn
кому: All
дата: 28 Jul 2006
Hello, CityAceE

Вот моё решение.
Аналитическое, надо проверить на практике.
Маленькая таблица и никаких умножений-делений. ;)

Заведём таблицу:
t=[281,19,263,1,280,18,262,0];

Пусть p1,p2,p3,p4 - трёхбитовые цвета цвета четырёх пикселей.
Пусть bright - одна на всех яркость.

Цвет результирующего пикселя можно подсчитать так:
┌─- code ───
color=256+t[p1]+t[p2]+t[p3]+t[p4];
if (!bright) color+=281;
if (color & 0x0400) color+=90; //синий из второй половины
color&=0xff; //взять младший байт
└── code ───
Результат: color - цвет из вышенарисованной палитры.

Для переменной color и элементов таблицы t необходимо минимум 2 байта (одного
байта недостаточно).

от: Stanislav Yudin
кому: All
дата: 31 Jul 2006
Hello, CityAceE

Hу вот, у меня всё получилось (результат прилагается). Огромное спасибо всем
откликнувшимся и принявшим участие в дискуссии! Hо в первую очередь хочется
поблагодарить key-jee'я, который собственно поделился алгоритмом и maximk'а,
который поделился информацией о цветах Палма.

Я не знаю причину, по которой key-jee поделился своим алгоритмом в привате, а
не в этой ветке, поэтому если он посчитает нужным, то сам расскажет здесь о
сути своего метода.

Файл: Dizzy8bpp2.png http://zx.pk.ru/attachment.php?attachmentid=3526

от: SMT
кому: All
дата: 31 Jul 2006
Hello, CityAceE

качество хорошее. а насколько быстро?

от: Stanislav Yudin
кому: All
дата: 01 Aug 2006
Hello, SMT

SMT> а насколько быстро?

Очень даже быстро! В методе задействованы две таблички на 125 байт каждая. А
если перестроить палитру на свой лад, то и вовсе без таблиц обойтись можно.

от: van Yu Shinn
кому: All
дата: 02 Aug 2006
Hello, CityAceE

Cit> При этом ты ещё забыл упомянуть, что везде идёт деление без остатка.

Это такое свойство языка си. Деление целых чисел возвращает целочисленный
результат.

Cit> если он посчитает нужным, то сам расскажет здесь о сути своего
Cit> метода.

Интересно.

Cit> Очень даже быстро!

Значит можно быстрее.

Cit> таблички на 125 байт

Видимо, 5 градаций [0..4] на компонент (R,G,B) в степени 3 (количество
компонент).

Hе очень хорошее решение. Больше половины элементов таблицы не используется.
Очевидно результирующий пиксель может принимать только 40 цветов и его
компоненты R,G,B не могут быть всепопарно различны.

А как считается индекс в таблице?
Два умножения на 5? Сложением констант 5 и 25?

от: Stanislav Yudin
кому: All
дата: 02 Aug 2006
Hello, captain cobalt

cap> Значит можно быстрее.

Я думаю, что наверняка можно! Hо не для моего случая.

cap> Видимо, 5 градаций [0..4] на компонент (R,G,B) в степени 3
cap> (количество компонент). Hе очень хорошее решение.

Да примерно так. Hо в моём случае именно такое решение было идеальным.

cap> Больше половины элементов таблицы не используется.

Всего в участке 2х2 возможны 92 комбинации цветов. При этом часть комбинаций
дают в итоге одинаковый цвет. Hапример, я бы никогда не подумал, что если
смешать два чёрных и два жёлтых пикселя, то на выходе получится тот же цвет,
что даст смешение двух красных и двух зелёных точек. Всего же получается 83
уникальных цвета на выходе. Это количество используемых цветов в одной табличке
из 125 элементов. Табличек две, по числу градаций яркости.

cap> А как считается индекс в таблице?

Это уже детали алгоритма. Ждём, что на это ответит сам key-jee.




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

Похожие статьи:
Обратная связь - контакты редакции.
Программирование - Загрузчик для рабочей дискеты.
Интервью - SERGEY STURM LGN.

В этот день...   16 октября