Справочные ссылки, которые предоставили люди, хороши, и есть несколько решений этой проблемы, но, поскольку я недавно работал над этой проблемой (с полным незнанием относительно того, как другие решили ее), я предлагаю свой подход в простой английский:
Во-первых, осознайте, что (воспринимаемый человеком) цвет является трехмерным. Это в основном потому, что человеческий глаз имеет 3 различных рецептора: красный, зеленый и синий. Точно так же ваш монитор имеет красные, зеленые и синие пиксельные элементы. Можно использовать другие представления, такие как оттенок, насыщенность, яркость (HSL), но в основном все представления являются трехмерными.
Это означает, что цветовое пространство RGB представляет собой куб с красными, зелеными и синими осями. Из 24-битного исходного изображения этот куб имеет 256 дискретных уровней на каждой оси. Наивный подход к уменьшению изображения до 8-битного заключается в простом уменьшении уровней на ось. Например, кубическая палитра 8x8x4 с 8 уровнями для красного и зеленого, 4 уровня для синего легко создается путем взятия старших 3 битов красного и зеленого значений и старших 2 битов синего значения. Это легко реализовать, но имеет ряд недостатков. В полученной 256 цветовой палитре многие записи не будут использоваться вообще. Если изображение имеет детализацию с использованием очень тонких цветовых сдвигов, эти сдвиги исчезнут, когда цвета будут привязаны к одной и той же записи палитры.
Подход адаптивной палитры должен учитывать не только усредненные / общие цвета в изображении, но и то, какие области цветового пространства имеют наибольшую дисперсию. То есть, для изображения, имеющего тысячи тонких оттенков светло-зеленого, требуется другая палитра, чем для изображения, имеющего тысячи пикселей точно такого же оттенка светло-зеленого, поскольку в последнем случае для этого цвета в идеале должна использоваться одна запись палитры.
С этой целью я выбрал подход, который приводит к 256 сегментам, каждый из которых содержит одинаковое количество различных значений. Таким образом, если исходное изображение содержало 256000 различных 24-битных цветов, этот алгоритм приводит к 256 сегментам, каждый из которых содержит 1000 исходных значений. Это достигается путем двоичного пространственного разделения цветового пространства с использованием медианы различных имеющихся значений (а не среднего значения).
В английском это означает, что сначала мы делим весь цветной куб на половину пикселей с меньшим значением медианного красного и половину с большим значением медианного красного. Затем разделите каждую полученную половину на значение зеленого, затем на синий и так далее. Каждое разделение требует одного бита для указания нижней или верхней половины пикселей. После 8 разбиений дисперсия эффективно разделена на 256 одинаково важных кластеров в цветовом пространстве.
В псевдо-коде:
// 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 листовых узлов, каждый из которых содержит одинаковое количество отличных цветов от исходного изображения, пространственно сгруппированных в цветовой куб. Чтобы назначить каждому узлу один цвет, найдите средневзвешенное значение, используя количество цветов. Взвешивание - это оптимизация, которая улучшает восприятие цвета, но это не так важно. Удостоверьтесь, чтобы усреднить каждый цветной канал независимо. Результаты отличные. Обратите внимание, что преднамеренно, что синий делится один раз меньше, чем красный и зеленый, так как синие рецепторы в глазу менее чувствительны к тонким изменениям, чем красный и зеленый.
Возможны и другие варианты оптимизации. Используя HSL, вместо синего вы можете поместить более высокое квантование в измерение яркости. Кроме того, приведенный выше алгоритм немного уменьшит общий динамический диапазон (поскольку в конечном итоге он усредняет значения цвета), так что динамическое расширение результирующей палитры - еще одна возможность.