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

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 debo elegir entre Vector.Unboxedy UArray? Ambos son arreglos sin caja, pero la Vectorabstracción parece muy publicitada, particularmente en torno a la fusión de bucles. ¿ VectorSiempre es mejor? Si no es así, ¿ cuándo debería usar qué representación?

2. Para imágenes en color, desearé almacenar triples de números enteros de 16 bits o triples de números de punto flotante de precisión simple. Para este propósito, es o bien Vectoro UArraymás fácil de usar? ¿Más rendimiento?

3. Para imágenes bitonales, necesitaré almacenar solo 1 bit por píxel. ¿Existe un tipo de datos predefinido que pueda ayudarme aquí al empaquetar varios píxeles en una palabra, o estoy solo?

4. Finalmente, mis matrices 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 mutación :-)

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

Repa proporciona matrices paralelas polimórficas, regulares, multidimensionales y de alto rendimiento. Todos los datos numéricos se almacenan sin caja. Las funciones escritas con los combinadores Repa son automáticamente paralelas siempre que proporcione + 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 de esténcil paralela eficiente en Haskell

Comencé a escribir un tutorial sobre el uso de repa , que es un buen lugar para comenzar si ya conoce las matrices de Haskell o la biblioteca de vectores. El trampolín clave es el uso de tipos de formas en lugar de tipos de índices simples, para abordar í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.

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

¿Sobre qué base debo elegir entre Vector.Unboxed y UArray?

Tienen aproximadamente la misma representación subyacente, sin embargo, la diferencia principal 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 UArrayque casi sin API.

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

UArraytiene un mejor soporte para datos multidimensionales, ya que puede usar tipos de datos arbitrarios para indexar. Si bien esto es posible en Vector(escribiendo una instancia de UApara su tipo de elemento), no es el objetivo principal de Vector; en cambio, aquí es donde Repainterviene, lo que facilita el uso de tipos de datos personalizados almacenados de 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, necesitaré almacenar solo 1 bit por píxel.

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

¿Existe un tipo de datos predefinido que pueda ayudarme aquí al empaquetar varios píxeles en una palabra?

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

Finalmente, mis matrices son bidimensionales.

UArray y Repa admiten matrices multidimensionales eficientes. Repa también tiene una rica interfaz para hacerlo. El vector por sí solo no lo hace.

Menciones destacadas:

• hmatrix , un tipo de arreglo personalizado con extensos enlaces a paquetes de álgebra lineal. Debería estar obligado a utilizar los tipos vectoro repa.
• ix-configurable , obteniendo una indexación más flexible de matrices regulares
• pizarra , la biblioteca de Andy Gill para manipular imágenes 2D
• codec-image-devil , lee y escribe varios formatos de imagen en UArray

Una vez revisé las características de las bibliotecas de matrices de Haskell que me importan y compilé una tabla de comparación (solo hoja de cálculo: enlace directo ). Así que intentaré responder.

¿Sobre qué base debo elegir entre Vector.Unboxed y UArray? Ambos son arreglos sin caja, pero la abstracción vectorial parece muy publicitada, en particular en torno a la fusión de bucles. ¿Vector siempre es mejor? Si no es así, ¿cuándo debería usar qué representación?

Puede preferirse UArray sobre Vector si se necesitan matrices bidimensionales o multidimensionales. Pero Vector tiene una API más agradable para manipular vectores. En general, Vector no es adecuado para simular matrices multidimensionales.

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

Para las imágenes en color, desearé almacenar triples de enteros de 16 bits o triples de números de punto flotante de precisión simple. Para este propósito, ¿es más 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 usé la biblioteca pgm (Haskell puro).

Mi principal problema con Array fue que solo proporciona almacenamiento de acceso aleatorio, pero no proporciona muchos medios para construir algoritmos de Array ni viene con bibliotecas listas para usar de rutinas de matriz (no interactúa con bibliotecas de álgebra lineal, no 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 gentil). El costo de la construcción de arreglos 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 gustaba luchar con errores de tipo críptico y los esfuerzos necesarios para escribir código polimórfico con STUArray .

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

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

Todavía no tenía mucha experiencia con Repa y no entiendo bien el código de reparación. Por lo que veo, tiene un rango muy limitado de algoritmos de matriz y matriz listos para usar escritos encima, pero al menos es posible expresar algoritmos importantes por medio de la biblioteca. Por ejemplo, ya existen rutinas para la multiplicación de matrices y para la convolución en repa-algoritmos. Desafortunadamente, parece que la convolución ahora está limitada a núcleos de 7 × 7 (no es suficiente para mí, pero debería ser suficiente para muchos usos).

No probé los enlaces Haskell OpenCV. Deberían 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 sobre ella. Si uno sigue el camino de OpenCV, es probable que use la representación de imágenes de OpenCV en todas partes y use rutinas de OpenCV para manipularlas.

Para imágenes bitonales, necesitaré almacenar solo 1 bit por píxel. ¿Existe un tipo de datos predefinido que pueda ayudarme aquí al empaquetar varios píxeles en una palabra, o estoy solo?

Hasta donde yo sé, las matrices sin caja de Bools se encargan de empaquetar y desempacar vectores de bits. Recuerdo haber visto la implementación de matrices de Bools en otras bibliotecas y no vi esto en ningún otro lugar.

Finalmente, mis matrices 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?

Aparte de Vector (y listas simples), todas las demás bibliotecas de matrices son capaces de representar matrices o matrices bidimensionales. Supongo que evitan la indirecta innecesaria.

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

Sería genial si alguien descubriese cómo repa o alguna biblioteca de matrices de este tipo podría usarse directamente con opencv.

Aquí hay una nueva biblioteca de procesamiento de imágenes de Haskell que puede manejar todas las tareas en cuestión y mucho más. Actualmente utiliza paquetes Repa y Vector para las representaciones subyacentes, lo que en consecuencia hereda la fusión, el cálculo 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:

• Indexación y sin caja píxeles 2D 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, Complex, etc.
• funcionalidad común de procesamiento de imágenes:
  • Morfología binaria
  • Circunvolución
  • Interpolación
  • Transformada de Fourier
  • Trazado de histograma
  • etc.
• Capacidad para tratar píxeles e imágenes como números regulares.
• Leer y escribir formatos de imagen comunes a través de la biblioteca JuicyPixels

Lo más importante es que es una biblioteca Haskell pura, por lo que no depende de ningún programa externo. También es muy ampliable, 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 un Word, en su lugar usa un Wordpíxel binario, tal vez en un futuro ...