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

[CityAceE]

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

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

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

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

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

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

[diver]

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

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

[fk0]

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


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



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


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



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


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

[key-jee]

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

[CityAceE]

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

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

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

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

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

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

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

[CityAceE]

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

[maximk]

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

Короче ради интереса потестил. По-моему нормально.

Результат (с дополнительным приведением к 2бита на канал цвета)

[NovaStorm]

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

[SMT]

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


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

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

[maximk]

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

[SMT]

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

[CityAceE]

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

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


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


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

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

[maximk]

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

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

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



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;
}
}


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

[CityAceE]

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

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

[maximk]

Ну, там используются так называемые 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 нет таких функций, для работы с цветом покомпонентно? Прямо даже не верится...

[CityAceE]

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


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

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


А вообще, неужели в API PalmOS нет таких функций, для работы с цветом покомпонентно? Прямо даже не верится...
Наверняка есть! Но всё, что я пишу, я пишу на чистом ассемблере. Можно конечно и из ассемблера все эти API вызывать, но разбираться совсем нет желания, да и нет времени у программы пользоваться громоздкими и медленными процедурами API.

[maximk]

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

[CityAceE]

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

[maximk]

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



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


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

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

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

[captain cobalt]

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

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

[captain cobalt]

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

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

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

Цвет результирующего пикселя можно подсчитать так:

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

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

[CityAceE]

(((index / 6) % 3) * 2) + (index / 108) * 3 = индекс синего.
Для красного и зелёного формулы работают, а для синего нет :( Логически прикинув понял, что в формуле лишнее умножение на 2. То есть формула должна выглядеть так:

((index / 6) % 3) + (index / 108) * 3 = индекс синего

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

[CityAceE]

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

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

[SMT]

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

[CityAceE]

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

[captain cobalt]

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

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

Очень даже быстро! Значит можно быстрее.

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

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

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

[CityAceE]

Значит можно быстрее.
Я думаю, что наверняка можно! Но не для моего случая.


Видимо, 5 градаций [0..4] на компонент (R,G,B) в степени 3 (количество компонент). Не очень хорошее решение.
Да примерно так. Но в моём случае именно такое решение было идеальным.


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

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


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