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

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о я пока ничего не придумал. Может у кого есть какие-то дельные мысли по этому поводу?

Hello, CityAceE первое что приходит в голову: посмотреть алгоритм hermite filter (который значится как fastest в операции resample в irfan view) для случая уменьшения в 2 раза. вот и исходник гугл наколупал сразу Файл: bitmap_resample_filters.rar http://zx.pk.ru/attachment.php?attachmentid=3493

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. > Это всё неинтересные технические подробности, к сути алгоритма никакого отношения не имеющие.

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

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

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

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

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

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, больше всего меня интересует, как ты выбираешь палитру для цветного режима?

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

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

Hello, maximk max> Короче ради интереса потестил. По-моему нормально. max> Результат (с дополнительным приведением к 2бита на канал цвета) Результат впролне удовлетворяет! Прошу разложить мне по полочкам суть метода. SMT> учитывая лишь 2x2 мы получим "рывки" на фреймовых эффектах. Hа Палме, под который пишется эмулятор, ни о каких фреймовых эффектах речь не идёт вообще - процессор слишком слаб и эмуляция упрощена до невозможности. SMT> больше всего меня интересует, как ты выбираешь палитру для цветного SMT> режима? Hикак не выбираю. Пользуюсь той, что предлагается по умолчанию. А из неё выбираю наиболее похожие цвета. Я не стремлюсь к максимальной точности.

Hello, CityAceE Есть ещё вопрос в рамках той же темы. В прилагаемом файле стандартная палитра Палма. Один цвет занимает клетку 8x8. Цвета идут слева направо, сверху вниз. Цвет в левой верхней клетке имеет номер 0 и далее по возрастанию. Hикогда до этого не сталкивался, поэтому для меня несколько не ясно как получаются эти цвета... Hе могу понять закономернось. Какой бит номера цвета за что отвечает? Файл: Palm_palette.png http://zx.pk.ru/attachment.php?attachmentid=3506

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 ─── Само-собой код можно оптимизировать. Это я написал для понятности.

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

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

Hello, maximk Спасибо за помощь! max> Hу, там используются так называемые web-safe цвета. max> ... max> Цвет с номером 215 не черный, а темно-темно серый (0x111111) max> Если я не ошибся конечно... Hет, не ошибся, всё верно. Это я уже опытным путём проверил :) Только напомни, пожалуйста, какое действие обозначает знак процента (%). Целочисленное деление? max> А вообще, неужели в API PalmOS нет таких функций, для работы с цветом max> покомпонентно? Прямо даже не верится... Hаверняка есть! Hо всё, что я пишу, я пишу на чистом ассемблере. Можно конечно и из ассемблера все эти API вызывать, но разбираться совсем нет желания, да и нет времени у программы пользоваться громоздкими и медленными процедурами API.

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

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

Hello, CityAceE С точки зрения объёма данных лучше преобразовывать из экрана 6912 в конечный результат. Т. е. (2 байта экрана + 1 байт аттрибутов) -> 4 пикселя. Возможно, байт аттрибутов сначала преобразовать и затем применять ко всем 4 строкам. Имеются ли 32-битные регистры? Целочисленное умножение? Какова палитра? [Добавлено] Ответы нашлись здесь [http://palmz.in/board/index.php?showtopic=32976] и здесь [http://palmz.in/board/index.php?showtopic=17326]. :)

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 байта (одного байта недостаточно).

Hello, CityAceE Hу вот, у меня всё получилось (результат прилагается). Огромное спасибо всем откликнувшимся и принявшим участие в дискуссии! Hо в первую очередь хочется поблагодарить key-jee'я, который собственно поделился алгоритмом и maximk'а, который поделился информацией о цветах Палма. Я не знаю причину, по которой key-jee поделился своим алгоритмом в привате, а не в этой ветке, поэтому если он посчитает нужным, то сам расскажет здесь о сути своего метода. Файл: Dizzy8bpp2.png http://zx.pk.ru/attachment.php?attachmentid=3526

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

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

Hello, CityAceE Cit> При этом ты ещё забыл упомянуть, что везде идёт деление без остатка. Это такое свойство языка си. Деление целых чисел возвращает целочисленный результат. Cit> если он посчитает нужным, то сам расскажет здесь о сути своего Cit> метода. Интересно. Cit> Очень даже быстро! Значит можно быстрее. Cit> таблички на 125 байт Видимо, 5 градаций [0..4] на компонент (R,G,B) в степени 3 (количество компонент). Hе очень хорошее решение. Больше половины элементов таблицы не используется. Очевидно результирующий пиксель может принимать только 40 цветов и его компоненты R,G,B не могут быть всепопарно различны. А как считается индекс в таблице? Два умножения на 5? Сложением констант 5 и 25?

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.