arrays - matrices - leer pixeles de una imagen en c++

¿Qué representación de Haskell se recomienda para los arrays de píxeles en 2D y sin caja con millones de píxeles?

Question

Quiero abordar algunos problemas de procesamiento de imágenes en Haskell. Estoy trabajando con imágenes bitonales (mapa de bits) y en color con millones de píxeles. Tengo un número de preguntas:

1. ¿Sobre qué base debería elegir entre Vector.Unboxed y UArray ? Ambas son matrices no compartidas, pero la abstracción de Vector parece muy publicitada, especialmente en torno a la fusión de bucle. ¿El Vector siempre es mejor? Si no, ¿ cuándo debería usar qué representación?

2. Para las imágenes en color, deseo almacenar triples de enteros de 16 bits o triples de números de coma flotante de precisión simple. Para este propósito, ¿es fácil usar Vector o UArray ? Más rendimiento?

3. Para imágenes bitonales tendré que almacenar solo 1 bit por píxel. ¿Hay algún tipo de datos predefinido que me pueda ayudar empacando varios píxeles en una palabra, o estoy solo?

4. Finalmente, mis arreglos son bidimensionales. Supongo que podría lidiar con la indirección adicional impuesta por una representación como "matriz de matrices" (o vector de vectores), pero preferiría una abstracción que tenga soporte de mapeo de índices. ¿Alguien puede recomendar algo de una biblioteca estándar o de Hackage?

Soy un programador funcional y no necesito mutar :-)

Answer 1

Aquí hay una nueva biblioteca de procesamiento de imágenes Haskell que puede manejar todas las tareas en cuestión y mucho más. Actualmente usa paquetes Repa y Vector para representaciones subyacentes, que heredan la fusión, el cálculo en paralelo, la mutación y la mayoría de los demás beneficios que vienen con esas bibliotecas. Proporciona una interfaz fácil de usar que es natural para la manipulación de imágenes:

• Índices 2D y píxeles no compartidos con precisión arbitraria ( Double , Float , Word16 , etc.)
• todas las funciones esenciales como map , fold , zipWith , traverse ...
• soporte para varios espacios de color: RGB, HSI, escala de grises, Bi-tonal, Complejo, etc.
• funcionalidad común de procesamiento de imágenes:
  • Morfología binaria
  • Circunvolución
  • Interpolación
  • Transformada de Fourier
  • Histograma trazado
  • etc.
• Capacidad de tratar píxeles e imágenes como números regulares.
• Lectura y escritura de formatos de imágenes comunes a través de la biblioteca JuicyPixels

Lo más importante es que es una biblioteca de Haskell pura, por lo que no depende de ningún programa externo. También es altamente extensible, se pueden introducir nuevos espacios de color y representaciones de imágenes.

Una cosa que no hace es empaquetar múltiples píxeles binarios en una Word , en su lugar usa una Word por píxel binario, tal vez en un futuro ...

Answer 2

Aunque esto no responde exactamente a su pregunta y realmente no es ni siquiera haskell como tal, recomendaría echar un vistazo a las bibliotecas de CV o CV-combinators en hackage. Vinculan los muchos operadores de visión y procesamiento de imágenes bastante útiles de la librería opencv y hacen que trabajar con problemas de visión artificial sea mucho más rápido.

Sería genial si alguien descubriera cómo repa o alguna de esas librerías de array podría usarse directamente con opencv.

Answer 3

Para las matrices multidimensionales, la mejor opción actual en Haskell, en mi opinión, es repa .

Repa proporciona matrices paralelas polimórficas de alto rendimiento, regulares, multidimensionales y de forma. Todos los datos numéricos se almacenan sin clasificar. Las funciones escritas con los combinadores Repa son paralelas automáticamente siempre que suministre + RTS -Nwhatever en la línea de comando cuando se ejecuta el programa.

Recientemente, se ha utilizado para algunos problemas de procesamiento de imágenes:

• Detección de bordes en tiempo real
• Convolución eficiente de la plantilla paralela en Haskell

Empecé a escribir un tutorial sobre el uso de Repa , que es un buen lugar para comenzar si ya conoces las matrices Haskell o la biblioteca de vectores. La piedra angular clave es el uso de tipos de formas en lugar de tipos de índices simples, para abordar los índices multidimensionales (e incluso plantillas).

El paquete repa-io incluye soporte para leer y escribir archivos de imagen .bmp, aunque se necesita soporte para más formatos.

Dirigiendo sus preguntas específicas, aquí hay un gráfico, con discusión:

¿Sobre qué base debería elegir entre Vector.Unboxed y UArray?

Tienen aproximadamente la misma representación subyacente, sin embargo, la principal diferencia es la amplitud de la API para trabajar con vectores: tienen casi todas las operaciones que normalmente asociaría con listas (con un marco de optimización impulsado por fusión), mientras que UArray tiene casi sin API.

Para las imágenes en color, deseo almacenar triples de enteros de 16 bits o triples de números de coma flotante de precisión simple.

UArray tiene mejor soporte para datos multidimensionales, ya que puede usar tipos de datos arbitrarios para la indexación. Si bien esto es posible en Vector (al escribir una instancia de UA para su tipo de elemento), no es el objetivo principal de Vector ; en cambio, aquí es donde Repa , lo que facilita el uso de tipos de datos personalizados almacenados en de una manera eficiente, gracias a la indexación de formas .

En Repa , tu triple de pantalones cortos tendría el tipo:

Array DIM3 Word16

Es decir, una matriz 3D de Word16s.

Para imágenes bitonales tendré que almacenar solo 1 bit por píxel.

UArrays empaqueta Bools como bits, Vector usa la instancia para Bool que sí hace el empaquetamiento de bits, en cambio usa una representación basada en Word8 . Sin embargo, es fácil escribir una implementación de empaquetamiento de bits para vectores: aquí hay uno , de la biblioteca uvector (obsoleta). Bajo el capó, Repa usa Vectors , así que creo que hereda las opciones de representación de las bibliotecas.

¿Hay un tipo de datos predefinido que me pueda ayudar empacando varios píxeles en una palabra?

Puede utilizar las instancias existentes para cualquiera de las bibliotecas, para diferentes tipos de palabras, pero es posible que deba escribir algunos ayudantes utilizando Data.Bits para desplegar y desenrollar datos empaquetados.

Finalmente, mis matrices son bidimensionales

UArray y Repa soportan matrices multidimensionales eficientes. Repa también tiene una interfaz rica para hacerlo. Vector por sí mismo no.

Menciones notables:

• hmatrix , un tipo de matriz personalizada con enlaces extensivos a paquetes de álgebra lineal. Debería estar obligado a usar los tipos vector o repa .
• ix-shapeable , obteniendo una indexación más flexible desde arreglos regulares
• chalkboard , la biblioteca de Andy Gill para manipular imágenes 2D
• codec-image-devil , lee y escribe varios formatos de imagen para UArray

Answer 4

Una vez revisé las características de las bibliotecas de arreglos de Haskell que son importantes para mí, y compilé una tabla de comparación (solo hoja de cálculo: enlace directo ). Entonces intentaré responder.

¿Sobre qué base debería elegir entre Vector.Unboxed y UArray? Ambas son matrices no compartidas, pero la abstracción de Vector parece muy publicitada, especialmente en torno a la fusión de bucle. ¿El vector siempre es mejor? Si no, ¿cuándo debería usar qué representación?

UArray puede preferirse a Vector si se necesitan matrices bidimensionales o multidimensionales. Pero Vector tiene una mejor API para manipular, bueno, vectores. En general, Vector no es muy adecuado para simular matrices multidimensionales.

Vector.Unboxed no se puede usar con estrategias paralelas. Sospecho que UArray no se puede usar tampoco, pero al menos es muy fácil cambiar de UArray a Array en caja y ver si los beneficios de paralelización superan los costos de boxeo.

Para las imágenes en color, deseo almacenar triples de enteros de 16 bits o triples de números de coma flotante de precisión simple. Para este propósito, ¿es fácil usar Vector o UArray? Más rendimiento?

Intenté usar Arrays para representar imágenes (aunque solo necesitaba imágenes en escala de grises). Para las imágenes en color utilicé la biblioteca Codec-Image-DevIL para leer / escribir imágenes (enlaces a la biblioteca DevIL), para las imágenes en escala de grises utilicé la biblioteca pgm (Haskell puro).

Mi principal problema con Array fue que proporciona solo almacenamiento de acceso aleatorio, pero no proporciona muchos medios para construir algoritmos Array ni viene con bibliotecas listas para usar de rutinas de matriz (no interactúa con las librerías de álgebra lineal, doesn no permite expresar convoluciones, fft y otras transformaciones).

Casi cada vez que se debe construir una nueva matriz a partir de la existente, se debe construir una lista intermedia de valores (como en la multiplicación de matrices de la Introducción suave). El costo de la construcción de conjuntos a menudo supera los beneficios de un acceso aleatorio más rápido, hasta el punto de que una representación basada en listas es más rápida en algunos de mis casos de uso.

STUArray podría haberme ayudado, pero no me gustó pelear con errores de tipo críptico y esfuerzos necesarios para escribir código polimórfico con STUArray .

Entonces, el problema con Arrays es que no son adecuados para cálculos numéricos. Hmatrix ''Data.Packed.Vector y Data.Packed.Matrix son mejores en este aspecto, ya que vienen con una biblioteca de matriz sólida (atención: licencia GPL). En lo que respecta al rendimiento, en la multiplicación de matrices, hmatrix fue lo suficientemente rápido ( solo un poco más lento que Octave ), pero muy hambriento de memoria (consumido varias veces más que Python / SciPy).

También hay una biblioteca blas para matrices, pero no se basa en GHC7.

Todavía no tengo mucha experiencia con Repa y no entiendo bien el código de reparación. Por lo que veo, tiene una gama muy limitada de algoritmos matriciales y de matrices listos para usar, pero al menos es posible expresar algoritmos importantes por medio de la biblioteca. Por ejemplo, ya hay rutinas para la multiplicación de la matriz y para la convolución en los algoritmos de reparación. Desafortunadamente, parece que la convolución ahora se limita a los núcleos 7 × 7 (no es suficiente para mí, pero debería ser suficiente para muchos usos).

No probé las uniones Haskell OpenCV. Deben ser rápidos, porque OpenCV es realmente rápido, pero no estoy seguro de si los enlaces están completos y son lo suficientemente buenos como para ser utilizables. Además, OpenCV por su naturaleza es muy imperativo, lleno de actualizaciones destructivas. Supongo que es difícil diseñar una interfaz funcional agradable y eficiente en la parte superior. Si uno usa OpenCV, es probable que use representación de imágenes OpenCV en todas partes, y use rutinas OpenCV para manipularlas.

Para imágenes bitonales tendré que almacenar solo 1 bit por píxel. ¿Hay algún tipo de datos predefinido que me pueda ayudar empacando varios píxeles en una palabra, o estoy solo?

Por lo que yo sé, las matrices de Bools sin caja se encargan de empaquetar y desempaquetar vectores de bits. Recuerdo haber observado la implementación de matrices de Bools en otras bibliotecas, y no lo vi en ningún otro lugar.

Finalmente, mis arreglos son bidimensionales. Supongo que podría lidiar con la indirección adicional impuesta por una representación como "matriz de matrices" (o vector de vectores), pero preferiría una abstracción que tenga soporte de mapeo de índices. ¿Alguien puede recomendar algo de una biblioteca estándar o de Hackage?

Además de Vector (y listas simples), todas las demás bibliotecas de arreglos son capaces de representar matrices o matrices bidimensionales. Supongo que evitan la indirección innecesaria.