Indexed Color Palete - Image Format
 

Вот я тут задумался, если индексировать цвета палитры картинки, и затем для каждого пикселя выдавать только индекс цвета, то например если у нас максимум может быть 65,535 цветов, чего вполне хватит для избежания искажения цвета.
Конечно если в идеале, использовать RGB с 8 битами на канал, выходит: 255^3=16,581,375 - а это число вмещается в 24 битное unsigned int.
Таким образом имея всю палитру 8 битного RGB (без альфы), нам нужно держать для каждого индекса 24 бита.
Картинка 1024х1024 вмещает в себя 1,048,576 пикселей, таким образом нам нафиг не нужно столь много темплейтов цветов.
Число 1,048,576 вмещается в 20 бит.
Таким образом оптимизация(1) индексации, это индекс должен быть битного размера в зависимости от вместительности картинки (колличества пикселей).
Таким образом если это картинка 256х256, то это 16 бит на индексное число, без потери цветовой палитры.
Теперь оптимизация(2) в том что мы не всегда имеем столько цветов не в зависимости от размера картинки. По сути эта оптимизация, переврывает первую, т.к. вычисление колличества цветов будет зависеть от колличества пикселей и их индентичности.
Таким образом мы имеем зависимость от колличества цветов, которые зависят от колличества пикселей.
Например если это тупо белый фон, то это будет 1 цвет RGB8, и размер картинки 255х255 таким образом мы имеем:
((8*3*1)+(1*256*256)) bits = 8 kilobytes
Тоесть белая картинка занимает ~8 килобайт, когда картинка с уникальным цветом на каждый пиксель, и размером 256х256 будет занимать:
((8*3*65536)+(16*256*256)) bits = 320 kilobytes
320 килобайт, для маленькой картинки в 256х256, не малый вес.

Я сравнил с png, картинка с белым фоном без индексации весит 4 kilobytes, а картинка с шумом(noise в фотошопе, чтобы получить максимум уникальных цветов) 136 kilobytes. Если картинку индексировать на 256 цветов, то вес будет 68 kilobytes.
С алгоритмом на текущий моммент размышления, такая же картинка выйдет весом в ~65 kilobytes, практически то же самое.

До текущего моммента рассуждения были только о индексации цветов и битной размерности индекса цвета.
Теперь т.к. я не знаком с тем как устроены разные форматы данных, какие могут быть идеи для того чтобы оптимизировать индексацию, БЕЗ какой-либо потери качества?

Ответ: Indexed Color Palete - Image Format
 

Лажа...

> максимум может быть 65,535 цветов, чего вполне хватит для избежания искажения цвета
Извини, но мой глаз может распознать гораздо больше оттенков.

> ((8*3*65536)+(16*256*256)) bits = 320 kilobytes
ты тупо к обычному изображению без всякого сжатия еще таблицу индексов прикрутил. С учетом того, что палитра содержит уникальные данные, как ты их сжать собираешься? Я уж не говорю о том, что даже сжав таблицу индексов, конечный размер все равно получится больше, чем у несжатого изображения.

ЗЫ. Посмотри LZW.

Ответ: Indexed Color Palete - Image Format
 

:-D

...

Что скажешь насчёт того, чтобы применить подобный алгоритм:
Найти любые сходства на полосы или небольшие квадратные участки, так сказать Patern'ы.
Например имея градиент, который длиной в 5 пикселей, но много где повторяется, таким образом его можно загнать в список патернов, который содержит индексы цветов. И отдельно список первых индексов, которые начинают этот патерн. Далее при пробегу по индексам, когда наступает индекс который использовался в списке индексов пикселей патернов, использовать информацию из патерна, и проскакивать пиксели которые покрываются этим патерном.
Алогоритм анализа картинки на нахождение "оправданных" патернов не так и прост, но это вполне реально и уменьшит размер картинки, если она содержит большое колличество учатсков которые идентичны другим участкам. А это в основном графика, может быть и пиксель арт, но фотографии тут не подходят.
Такой метод не потеряет ни доли качества, но может в картинках с повторениями увеличить колосально размер.
Эллементарный пример: горизонтальный градиент, всю полоску можно загнать в патерн, а для следующих строк использовать только индекс патерна, таким образом для создания градиента 256x256, будет иметься только первая строка как индексы цветов. А для других строк не 256 индексов, а 1 индекс для патерна.
Патерн может быть любой высоты и ширины, естественно это должны быть маленькие патерны.
Но это весьма сложный алгоритм на нахождение патернов, и затем на потверждение их "оправданности".

Ответ: Indexed Color Palete - Image Format
 

:-D

Ответ: Indexed Color Palete - Image Format
 

А вопрос вообще в чем?
Не эффективно по двум причинам:
1. пиксель занимал 3 байта, а стал 2 байта => сжали размер битмапа на 1/3
но мы сделали lookup таблицу 65536 * 3 = 192 Кб, то где же выигышь? разве что на все картинки одна палитра, но это явно EPIC FAIL.
2. если дело идет о раскодировании в рилтайме, например, ты хочешь запатентовать метод аппаратного сжатия, что-то типа S3TC, то у тебя из-за большой таблицы будет куча кеш-промахов, и вот он EPIC FAIL №2.

Но пиши еще. Лучше это, чем "какое кино кто посмотрел".

Ответ: Indexed Color Palete - Image Format
 

ты постепенно подходишь к сжатому DDS.
http://software.intel.com/file/17248/