Algoritmo para contar el número de colores únicos en una imagen

Question

Buscando uno que sea lo suficientemente rápido y elegante con la memoria. La imagen es un 24bpp System.Drawing.Bitmap.

Answer 1

Si necesita un número exacto, entonces tendrá que recorrer todos los píxeles. Probablemente, almacenar el color y contar en hash es la mejor manera de hacerlo debido a la escasez de colores.

Usar el Color.ToArgb() en el hash en lugar del objeto de color probablemente sería una buena idea también.

Además, si la velocidad es una preocupación importante, no desea utilizar una función como GetPixel (x, y) - en su lugar, intente procesar los trozos a la vez (fila por vez). Si puede, obtenga un puntero al principio de la memoria de imagen y hágalo inseguro.

Answer 2

Antes de las tarjetas gráficas modernas, cuando la mayoría de las máquinas funcionaban en modo de paleta de 256 colores, esta era un área de considerable interés. Los límites en el poder de procesamiento y la memoria impusieron el tipo de restricción que podría serle útil, por lo que es probable que una búsqueda de algoritmos para manejar paletas resulte útil.

Answer 3

Eso depende de qué tipo de imágenes desee analizar. Para imágenes de 24 bits, necesitará hasta 2 MB de memoria (ya que en el peor de los casos deberá procesar cada color). Para esto, un mapa de bits sería la mejor idea (tienes un mapa de bits de 2 MB, donde cada bit corresponde a un color). Esta sería una buena solución para imágenes con un alto recuento de color que se puede realizar en O (# píxeles). Para imágenes de 16 bits, solo necesitaría 8 kB para este mapa de bits utilizando esta técnica.

Sin embargo, si tiene imágenes con pocos colores, sería mejor usar otra cosa. Pero entonces se necesitaría algún tipo de verificación para indicar qué algoritmo debe utilizar ...

Answer 4

nunca puestos en práctica algo como esto antes, pero como yo lo veo, una implementación primitiva:

una imagen de 24 bits Para , el número máximo de colores que la imagen podría tener es el mínimo de (2^24, número de píxeles de la imagen).

Solo necesita registrar si se ha contado un color en particular, no cuántas veces se ha contado. Eso significa que necesita 1 bit para registrar si se cuenta cada color. Eso es 2MB de memoria. Itere a través de los píxeles, establezca el bit relevante en su mapa de conjunto de colores de 2MB. Al final, recorra el mapa del conjunto de colores contando los bits establecidos (si tiene suerte, tendrá una instrucción POPCNT para ayudar con esto).

Para imágenes más pequeñas y, por supuesto, profundidades de color menores, es mejor que mantenga una tabla de colores y cuente para cada color que está en la imagen.

Answer 5

var cnt = new HashSet<System.Drawing.Color>(); 

foreach (Color pixel in image) 
    cnt.Add(pixel); 

Console.WriteLine("The image has {0} distinct colours.", cnt.Count); 

/Edit: Como dijo Lou, utilizando .GetArgb() en lugar del valor Color en sí podría ser un poco más rápido debido a la forma Color implementa GetHashCode.

Answer 6

El número máximo de colores únicos en una imagen es igual al número de píxeles, por lo que esto es predecible desde el inicio del proceso. Usar el método HashSet propuesto, por Konrad, parecería ser una solución razonable, ya que el tamaño del hash no debería ser mayor que el número de píxeles, mientras que usar el enfoque de mapa de bits sugerido por JeeBee requeriría 512 MB para un 32 imagen bit (si hay un canal alfa, y esto está determinado a contribuir a la unicidad del color)

El rendimiento del enfoque HashSet, sin embargo, es probablemente peor que el del 'bit-por-color 'enfoque: es posible que desee probar ambos y hacer algunos puntos de referencia, utilizando muchas imágenes diferentes

Answer 7

No definió exactamente los colores únicos. Si realmente quiere decir valores de código verdaderamente únicos (a diferencia de lo que ocurre visualmente), entonces la única solución exacta es contarlos usando una de las técnicas descritas en otras respuestas.

Si está buscando visualmente similares colores, esto destilar rápidamente a un problema de asignación de paleta en la que está buscando dicen las 256 mejores colores únicos a utilizar para más estrechamente representan la imagen del rango dinámico del color original completo. Para la mayoría de las imágenes, es sorprendente lo buena que se redujo una imagen de 24 bits y hasta 16 millones de colores diferentes para empezar se pueden asignar a una imagen con solo 256 colores únicos cuando esos 256 colores están bien seleccionados. Se ha demostrado que la selección óptima de esos 256 colores correctos (para este ejemplo) es NP completa, pero hay soluciones prácticas que pueden llegar a ser muy cercanas. Busca papeles de un tipo llamado Shijie Wan y cosas construidas sobre su trabajo.

Si está buscando una aproximación al número de colores del código de una imagen, comprimiría la imagen utilizando un esquema de compresión sin pérdida. La relación de compresión se relacionará directamente con el número de valores de código únicos en la imagen. Ni siquiera tiene que mantener la salida comprimida, simplemente acumule la cantidad de bytes a lo largo del camino y descarte los datos de salida reales. Utilizando un conjunto de imágenes de muestra como referencia, puede crear una tabla de búsqueda entre la relación de compresión y el número de valores de código diferentes en la imagen. Una vez más, esta última técnica, aunque bastante rápida, definitivamente será una aproximación, pero debería correlacionarse razonablemente bien.

Answer 8

La mayoría de las personas aquí han sugerido soluciones que probablemente sean rápidas (en realidad, la que solo usa 2 MB probablemente sea aceptable en cuanto al uso de memoria y muy rápida, la que tiene el hash podría ser incluso más rápida, pero definitivamente usará más más de 2 MB de memoria). La programación siempre es una compensación entre el uso de memoria y el tiempo de CPU. Generalmente puede obtener resultados más rápidos si está dispuesto a "desperdiciar" más memoria o puede obtener resultados más lentos "perdiendo" más tiempo de cálculo, sin embargo, esto generalmente le asegura mucha memoria.

Aquí hay una solución que nadie ha sugerido hasta ahora. Probablemente sea el que menos costos de memoria (puede optimizar, por lo que apenas utilizará más memoria de la necesaria para mantener la imagen en la memoria, sin embargo, la imagen se verá alterada, aunque es posible que tenga que copiarla primero). Dudo que pueda vencer la velocidad de la solución hash o bit-mask, es interesante si la memoria es su principal preocupación.

1. Ordene los píxeles en la imagen por color. Puede convertir fácilmente cada píxel a un número de 32 bits y los números de 32 bits se pueden comparar entre sí, un número es más pequeño que otro, más grande o igual. Si usa Quicksort, no se necesita espacio de almacenamiento adicional para la clasificación, aparte del espacio adicional de la pila. Si usa Shellsort, no se necesita memoria adicional (aunque Shellsort será mucho más lento que Quicksort).

   int num = (ROJO < < 16) + (VERDE < < 8) + AZUL;

2. Una vez que haya ordenado los píxeles de esa manera (lo que significa que los ha reorganizado dentro de la imagen), todos los píxeles del mismo color están siempre uno al lado del otro. De modo que puede iterar una vez sobre la imagen y observar con qué frecuencia cambia el color. P.ej. usted almacena el color actual del píxel en (0, 0) e inicia un contador con el valor 1. El siguiente paso es ir a (0, 1). Si es del mismo color que antes, no hay nada que hacer, continúe con el siguiente píxel (0, 2). Sin embargo, si no es lo mismo, aumente el contador en uno y recuerde el color de ese píxel para la siguiente iteración.

3. Una vez que haya mirado el último píxel (y posiblemente haya aumentado el contador nuevamente, si no fue el mismo que el segundo píxel), el contador contiene el número de colores únicos.

iterar sobre todos los píxeles al menos una vez es algo que debe hacer en cualquier caso, independientemente de la solución, por lo que no tiene impacto en esta solución es más lento o más rápido que otras soluciones. La velocidad de este algoritmo depende de qué tan rápido pueda ordenar los píxeles de la imagen por color.

Como dije, este algoritmo se supera fácilmente cuando la velocidad es su concierto principal (otras soluciones son probablemente más rápidas), pero dudo que pueda ser superado cuando el uso de memoria es su principal preocupación, ya que aparte del contador suficiente espacio de almacenamiento para almacenar un color y espacio de almacenamiento para la imagen en sí, solo necesitará memoria adicional si el algoritmo de clasificación elegido lo necesita.

Answer 9

La mayoría de las otras implementaciones aquí van a ser lentas. . Para que esto sea rápido, es necesario tener acceso línea de barrido directo y una especie de matriz dispersa para almacenar los datos de color en

En primer lugar voy a describir el caso 32bpp, es mucho más fácil:

• HashSet: matriz dispersa de colores
• ImageData: Utilice un objeto BitmapData a directamente el acceso de la memoria subyacente
• PixelAccess: Utilice un int * para hacer referencia a la memoria como enteros, que se puede recorrer en iteración

Para cada iteración simplemente haga un hashset.add de ese entero. Al final solo vea cuántas teclas hay en HashSet y esa es la cantidad total de colores. Es importante tener en cuenta que cambiar el tamaño de un HashSet es realmente doloroso (O (n) donde n es el número de elementos en el conjunto) y, por tanto, es posible que desee construir un HashSet de tamaño razonable para empezar, tal vez algo como imageHeight * imageWidth/4 sería bueno.

En el caso de 24bpp, PixelAccess debe ser un byte * y necesita iterar más de 3 bytes para cada color para construir un int. Para cada byte en el conjunto de 3 primeros bitshift a la izquierda por 8 (un byte) y agréguelo a un entero. Ahora tiene un Color de 24bpp representado por un int de 32 bits, el resto es el mismo.

Answer 10

La implementación popular moderna de color quantization utiliza la estructura de datos octree. Tenga en cuenta las páginas de wikipedia, el contenido es bastante bueno. El octário tiene la ventaja de tener la memoria tan limitada como desee, de modo que puede muestrear toda la imagen y decidir sobre su paleta sin mucha memoria adicional.Una vez que comprenda el concepto, siga el enlace al 1996 Dr Dobb's journal article's source code.

Dado que esta es una pregunta de C#, consulte el artículo de MSDN de mayo de 2003 Optimizing Color Quantization for ASP.NET Images, que incluye algunos códigos fuente.