Уменьшение палитры изображений

Ответ 1

EDIT: обновлено для поддержки палитры из 256 цветов

Если вам нужен простейший метод, то я бы предложил подход на основе гистограммы:

Calculate histograms of R/G/B channels
Define 4 intensity ranges
For each channel in intensity range
  Split histogram into 4 equal parts
  For each histogram part
    Extract most frequent value of that part

Теперь у вас будет палитра 4 * 4 ^ 3 = 256 цветов. При назначении цвета пикселя для палитры просто вычислите среднюю интенсивность пикселя, чтобы увидеть, какую область интенсивности вы должны использовать. После этого просто сопоставьте один из этих 64 цветов области интенсивности с пиксельным значением.

Удачи.

Ответ 2

• http://en.wikipedia.org/wiki/Color_quantization
• Octree
• Медиана-вырезать
• K-средства
• подразделение Gamut
• http://www.cs.berkeley.edu/~dcoetzee/downloads/scolorq/

Ответ 3

Полезные ссылки, которые люди предоставили, хороши, и есть несколько решений этой проблемы, но поскольку я недавно работал над этой проблемой (с полным невежеством относительно того, как другие ее решили), я предлагаю свой подход в простой английский:

Во-первых, осознайте, что (воспринимаемый человеком) цвет трехмерен. Это принципиально потому, что человеческий глаз имеет 3 различных рецептора: красный, зеленый и синий. Аналогично, ваш монитор имеет красные, зеленые и синие пиксельные элементы. Могут использоваться другие представления, например, оттенок, насыщенность, яркость (HSL), но в основном все представления трехмерны.

Это означает, что цветовое пространство RGB представляет собой куб с красной, зеленой и синей осей. Из 24-битного исходного изображения этот куб имеет 256 дискретных уровней на каждой оси. Наивный подход к уменьшению изображения до 8 бит - просто уменьшить уровни на ось. Например, палитра кубика 8x8x4 с 8 уровнями для красного и зеленого цветов, 4 уровня для синего цвета легко создаются, принимая высокие 3 бита красных и зеленых значений и высокие 2 бита синего значения. Это легко реализовать, но имеет несколько недостатков. В полученной 256 цветовой палитре многие записи не будут использоваться вообще. Если изображение имеет детали, используя очень тонкие цветовые сдвиги, эти сдвиги исчезнут, когда цвета защелкнутся в одной и той же палитре.

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

С этой целью я принял подход, в результате которого было получено 256 ведер, содержащих точно такое же количество различных значений. Поэтому, если исходное изображение содержало 256000 различных 24-битных цветов, этот алгоритм дает 256 кодов, каждый из которых содержит 1000 исходных значений. Это достигается путем двоичного пространственного разбиения цветового пространства с использованием медианы различных имеющихся значений (а не среднего значения).

По-английски это означает, что мы сначала разделим весь куб цвета на половину пикселей с меньшим, чем среднее значение красного цвета, и половину с более чем средним красным значением. Затем разделите каждую полученную половину на зеленый, затем синий и т.д. Для каждого разделения требуется один бит для указания нижней или более высокой половины пикселей. После 8 разделов дисперсия эффективно разделена на 256 одинаково важных кластеров в цветовом пространстве.

В psuedo-code:

// count distinct 24-bit colors from the source image
// to minimize resources, an array of arrays is used 
paletteRoot = {colors: [ [color0,count],[color1,count], ...]} // root node has all values 
for (i=0; i<8; i++) {
  colorPlane = i%3 // red,green,blue,red,green,blue,red,green
  nodes = leafNodes(paletteRoot) // on first pass, this is just the root itself
  for (node in nodes) {
    node.colors.sort(colorPlane) // sort by red, green, or blue
    node.lo = { colors: node.colors[0..node.colors.length/2] }
    node.hi = { colors: node.colors[node.colors.length/2..node.colors.length] } 
    delete node.colors // free up space! otherwise will explode memory
    node.splitColor = node.hi.colors[0] // remember the median color used to partition
    node.colorPlane = colorPlane // remember which color this node split on
  }
}

Теперь у вас есть 256 листовых узлов, каждый из которых содержит одинаковое количество различных цветов исходного изображения, кластерное пространственно в цветовом кубе. Чтобы присвоить каждому node один цвет, найдите средневзвешенное значение, используя подсчет цветов. Утяжение - это оптимизация, которая улучшает соответствие восприятия цвета, но это не так важно. Удостоверьтесь, что каждый цветной канал должен быть независимо. Результаты отличные. Обратите внимание, что это намеренно, что синий делится раз меньше красного и зеленого, так как синие рецепторы в глазу менее чувствительны к тонким изменениям, чем красный и зеленый.

Возможны другие оптимизации. Используя HSL, вы можете вместо этого использовать более высокое квантование в измерении яркости вместо синего. Кроме того, приведенный выше алгоритм будет немного уменьшать общий динамический диапазон (поскольку он в конечном счете усредняет значения цвета), поэтому еще одна возможность может быть динамически расширять результирующую палитру.