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

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

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

[Advertiser]

[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).