Reducción de la paleta de imagen

Question

Estoy jugando con programación de gráficos por primera vez. Quiero convertir imágenes RGB (24 bits) a imágenes de paleta indexada (8 bits) (como GIF). Mi pensamiento inicial es usar k-means (con k = 256).

¿Cómo se va a elegir la paleta óptima para una imagen determinada? Esta es una experiencia de aprendizaje para mí, por lo que preferiría una respuesta general al código fuente.

Edit: Dithering está actualmente fuera del tema. Solo me refiero a la conversión de color "simple", a un lado los modelos psico-visuales/perceptivos; espacio de color es también actualmente fuera de tema, aunque se mueve entre el color de espacios es lo que me hizo pensar acerca de esto en primer lugar :)

Answer 1

EDIT: actualizado para soportar la paleta de 256 colores

Si necesita método más simple entonces sugeriría enfoque basado en el histograma:

 
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 

Ahora usted tendrá 4 * 4^3 = 256 paleta de colores. Cuando asigne un píxel a un color de paleta, simplemente calcule la intensidad promedio del píxel para ver qué región de intensidad debe usar. Después de eso, solo mapea uno de esos 64 colores de región de intensidad a valor de píxel.

Buena suerte.

Answer 2

• http://en.wikipedia.org/wiki/Color_quantization
• octárbol
• -corte medio
• K -Medios
• Gama subdivisión
• http://www.cs.berkeley.edu/~dcoetzee/downloads/scolorq/

Answer 3

Los enlaces de referencia que la gente ha proporcionado son buenos, y hay varias soluciones para este problema, pero dado que he estado trabajando en este problema recientemente (ignorando por completo cómo otros lo han solucionado), ofrezco mi enfoque en inglés sencillo:

En primer lugar, tenga en cuenta que el color (percibido por el ser humano) es tridimensional. Esto se debe fundamentalmente a que el ojo humano tiene 3 receptores distintos: rojo, verde y azul. Del mismo modo, su monitor tiene elementos de píxeles rojos, verdes y azules. Se pueden usar otras representaciones, como tono, saturación, luminancia (HSL), pero básicamente todas las representaciones son tridimensionales.

Esto significa que el espacio de color RGB es un cubo, con los ejes rojo, verde y azul. A partir de una imagen fuente de 24 bits, este cubo tiene 256 niveles discretos en cada eje. Un enfoque ingenuo para reducir la imagen a 8 bits es simplemente reducir los niveles por eje. Por ejemplo, una paleta de cubo 8x8x4 con 8 niveles para rojo y verde, 4 niveles para azul se crea fácilmente tomando los 3 bits altos de los valores rojo y verde, y los 2 bits altos del valor azul. Esto es fácil de implementar, pero tiene varias desventajas. En la paleta resultante de 256 colores, muchas entradas no se usarán en absoluto. Si la imagen tiene detalles usando cambios de color muy sutiles, estos cambios desaparecerán a medida que los colores encajen en la misma entrada de paleta.

Un enfoque de paleta adaptable necesita tener en cuenta no solo los colores promediados/comunes en la imagen, sino también las áreas del espacio de color que tienen la mayor varianza.Es decir, una imagen que tiene miles de matices sutiles de luz verde requiere una paleta diferente que una imagen que tiene miles de píxeles exactamente del mismo tono de verde claro, ya que este último idealmente usaría una sola entrada de paleta para ese color.

Para este fin, tomé un enfoque que da como resultado 256 segmentos que contienen exactamente el mismo número de valores distintos cada uno. Entonces, si la imagen original contenía 256000 colores distintos de 24 bits, este algoritmo da como resultado 256 cubos cada uno que contiene 1000 de los valores originales. Esto se logra mediante la partición espacial binaria del espacio de color utilizando la mediana de los distintos valores presentes (no la media).

En inglés, esto significa que primero dividimos el cubo de color completo en la mitad de píxeles con menos del valor medio de rojo y la mitad con más que el valor medio de rojo. Luego, divida cada mitad resultante por verde, luego por azul, y así sucesivamente. Cada división requiere un solo bit para indicar la mitad inferior o superior de los píxeles. Después de 8 divisiones, la varianza se ha dividido en 256 clústeres igualmente importantes en el espacio de color.

En pseudo-código:

// 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 
    } 
} 

Ahora tiene 256 nodos hoja, cada una contiene el mismo número de colores distintos de la imagen original, agrupados espacialmente en el cubo de color. Para asignar a cada nodo un solo color, encuentre el promedio ponderado usando los recuentos de color. La ponderación es una optimización que mejora la coincidencia de color perceptual, pero no es tan importante. Asegúrese de promediar cada canal de color de forma independiente. Los resultados son excelentes Tenga en cuenta que es intencional que el azul se divida una vez menos que el rojo y el verde, ya que los receptores azules en el ojo son menos sensibles a los cambios sutiles que el rojo y el verde.

Existen otras optimizaciones posibles. Al usar HSL, en su lugar podría poner la cuantización más alta en la dimensión de luminancia en lugar de azul. Además, el algoritmo anterior reducirá ligeramente el rango dinámico general (ya que en última instancia promedia los valores de color), por lo que ampliar dinámicamente la paleta resultante es otra posibilidad.