¿Qué representación 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 tanto con imágenes bitonales (mapa de bits) como a color con millones de píxeles. Tengo una serie de preguntas:

  1. ¿Sobre qué base debo elegir entre Vector.Unboxed y UArray? Ambos son arrays sin caja, pero la abstracción Vector parece fuertemente publicitada, particularmente alrededor de la fusión de bucles. Es Vector siempre mejor? Si no, ¿cuándo debo usar qué representación?

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

  3. Para las imágenes bitonales necesitaré almacenar solo 1 bit por píxel. ¿Hay un tipo de datos predefinido que pueda ayudarme aquí empaquetando múltiples píxeles en una palabra, o estoy por mi cuenta?

  4. Finalmente, mis matrices son bidimensionales. Supongo que podría lidiar con la indirecta extra impuesta por un representación como "array of arrays" (o vector de vectores), pero preferiría una abstracción que tenga soporte para index-mapping. ¿Puede alguien recomendar algo de una biblioteca estándar o de Hackage?

Soy un programador funcional y no tengo necesidad de mutación: -)

Author: Norman Ramsey, 2011-05-15
Source

4 answers

Para matrices multidimensionales, el actual mejor opción 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 caja. Las funciones escritas con los combinadores Repa son automáticamente paralelas siempre y cuando suministre +RTS-Nwhatever en la línea de comandos al ejecutar el programa.

Recientemente, se ha utilizado para alguna imagen problemas de procesamiento:

He empezado 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 vectorial. El escalón clave es el uso de tipos de formas en lugar de tipos de índices simples, para abordar índices multidimensionales (e incluso plantillas).

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

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

Los tres de UArray, Vector y Repa admiten unboxing. Vector y Repa tienen una API rica y flexible, pero UArray no. UArray y Repa tienen indexación multidimensional, pero Vector no. Todos ellos tienen soporte para el embalaje de bits, aunque Vector y Repa tienen algunas advertencias en ese sentido. Vector y Repa interoperan con datos y código de C, pero UArray no lo hace. Solo Repa admite plantillas.

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 que UArray casi no tienen API.

Para las imágenes en color, desearé 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. Mientras que esto es posible en Vector (escribiendo una instancia de UA para su elemento type), no es el objetivo principal de Vector instead en cambio, aquí es donde Repa interviene, lo que facilita el uso de tipos de datos personalizados almacenados de manera eficiente, gracias a la indexación shape.

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

Array DIM3 Word16

Es decir, una matriz 3D de Word16s.

Para las imágenes bitonales necesitaré almacenar solo 1 bit por píxel.

UArrays pack Bools como bits, Vector utiliza la instancia de Bool que hace do empaquetamiento de bits, en su lugar usando una representación basada en Word8. Howver, es fácil escribir una implementación de empaquetado de bits para vectores { aquí hay uno, de la (obsoleta) biblioteca uvector. 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 pueda ayudarme aquí empaquetando múltiples píxeles en una palabra

Puede utilizar las instancias existentes para cualquiera de las bibliotecas, para diferentes tipos de palabras, pero es posible que necesite escribir algunos ayudantes usando Datos.Bits para rodar y desenrollar datos empaquetados.

Finalmente, mis matrices son bidimensionales

UArray y Repa soportan arreglos multidimensionales eficientes. Repa también tiene una interfaz rica para hacerlo. Vector por sí solo no lo hace.

Menciones notables:

  • hmatrix, un tipo de matriz personalizada con enlaces extensos a paquetes de álgebra lineal. Debe estar obligado a utilizar los tipos vector o repa.
  • ix-shapeable , 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
 89
Author: Don Stewart,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-06-17 02:20:55

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 matrices sin caja, pero la abstracción vectorial parece muy publicitada, particularmente alrededor de la fusión de bucles. Es Vector siempre mejor? Si no, ¿cuándo debo usar qué representación?

UArray puede ser preferido sobre Vector si uno necesita matrices bidimensionales o multidimensionales. Pero Vector tiene API más agradable 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 tampoco se puede usar, pero al menos es muy fácil cambiar de UArray a boxed Array y ver si los beneficios de paralelización superan los costos de boxeo.

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

Intenté usar matrices 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 (puro Haskell).

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

Casi cada vez que se tiene que construir una nueva matriz a partir de la existente, se tiene que construir una lista intermedia de valores (como en multiplicación de matrices de la Introducción Gentle). El costo de la matriz la construcción 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 .

Así que el problema con los arrays es que no son muy adecuados para cálculos numéricos. Datos de Hmatrix.Lleno.Vector y Datos.Lleno.Matrix 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 era suficientemente rápido (solo ligeramente 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 repa. Por lo que veo, tiene un rango muy limitado de usar algoritmos de matriz y array escritos encima, pero al menos es posible expresar algoritmos importantes por medio de la biblioteca. Por ejemplo, ya hay rutinas para multiplicación de matrices y para convolución en repa-algoritmos. Desafortunadamente, parece que la convolución está ahora limitada a núcleos 7×7 (no es suficiente para mí, pero debería ser suficiente para muchos usos).

No probé los enlaces Haskell OpenCV. Deben ser rápidos, porque OpenCV es muy rápido, pero no estoy seguro de si las fijaciones son completas y lo suficientemente buenas 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 encima de ella. Si uno va OpenCV, es probable que use la representación de imágenes OpenCV en todas partes, y use rutinas OpenCV para manipularlas.

Para las imágenes bitonales necesitaré almacenar solo 1 bit por píxel. Hay un tipo de datos predefinido que puede ayudarme aquí empaquetando múltiples píxeles en una palabra, o estoy solo?

Por lo que sé, Los arrays de Bools sin caja se encargan de empaquetar y desempaquetar los vectores de bits. Recuerdo haber mirado la implementación de matrices de Bools en otras bibliotecas, y no vi esto en otra parte.

Finalmente, mis matrices son bidimensionales. Supongo que podría lidiar con la indirecta extra impuesta por una representación como "matriz de matrices" (o vector de vectores), pero preferiría una abstracción que tiene soporte para mapeo de índices. ¿Puede alguien 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 indirectas innecesarias.

 17
Author: sastanin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-16 13:23:26

Aunque, esto no responde exactamente a su pregunta y no es realmente incluso haskell como tal, yo recomendaría echar un vistazo a CV o CV-combinators bibliotecas en hackage. Unen 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 bastante bueno si alguien se diera cuenta de cómo repa o alguna biblioteca de matrices podría ser utilizada directamente con opencv.

 5
Author: aleator,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-16 17:11:20

Aquí hay una nueva Haskell Image Processing library que puede manejar todas las tareas en cuestión y mucho más. Actualmente utiliza paquetes Repa y Vector para las representaciones subyacentes, que en consecuencia hereda fusión, computación paralela, mutación y la mayoría de las otras ventajas que vienen con esas bibliotecas. Proporciona una interfaz fácil de usar que es natural para la manipulación de imágenes:

  • Indexación 2D y píxeles sin caja con arbitrario precisión (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
    • Convolución
    • Interpolación
    • Transformada de Fourier
    • Trazado del histograma
    • etc.
  • Capacidad para tratar píxeles e imágenes como normales numero.
  • Leer y escribir formatos de imagen comunes a través de JuicyPixels biblioteca

Lo más importante es que es una biblioteca 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 un Word, en su lugar utiliza un Word por píxel binario, tal vez en un futuro...

 0
Author: Alexey Kuleshevich,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-04-17 07:25:53