Quelle représentation Haskell est recommandée pour les tableaux de pixels 2D, sans boîte, avec des millions de pixels ?

Question

Je veux m'attaquer à des problèmes de traitement d'images en Haskell. Je travaille à la fois avec des images bitonales (bitmap) et en couleur avec des millions de pixels. J'ai un certain nombre de questions :

1. Sur quelle base devrais-je choisir entre Vector.Unboxed y UArray ? Ce sont tous les deux des tableaux unboxed, mais le Vector L'abstraction semble faire l'objet de beaucoup de publicité, en particulier autour de la fusion de boucles. Est-ce que Vector toujours mieux ? Si non, Quand dois-je utiliser quelle représentation ?

2. Pour les images en couleur, je souhaite stocker des triples d'entiers de 16 bits ou des triples de nombres à virgule flottante de simple précision. Dans ce but, soit Vector o UArray plus facile à utiliser ? Plus performant ?

3. Pour les images bitonales, je dois stocker un seul bit par pixel. Existe-t-il un type de données prédéfini qui puisse m'aider à regrouper plusieurs pixels dans un mot, ou dois-je me débrouiller seul ?

4. Enfin, mes tableaux sont bidimensionnels. Je suppose que je pourrais m'accommoder de l'indirection supplémentaire imposée par une représentation en tant que "tableau de tableaux" (ou vecteur de vecteurs), mais je préférerais une abstraction qui supporte le mappage d'index. Quelqu'un peut-il me recommander quelque chose dans une bibliothèque standard ou dans Hackage ?

Je suis un programmeur fonctionnel et je n'ai pas besoin de mutation :-)

Answer 1

Pour les tableaux multidimensionnels, la meilleure option actuelle en Haskell est, à mon avis, la suivante repa .

Repa fournit des tableaux parallèles de haute performance, réguliers, multidimensionnels et polymorphes. Toutes les données numériques sont stockées de manière unboxed. Les fonctions écrites avec les combinateurs Repa sont automatiquement parallèles si vous fournissez +RTS -Nwhatever sur la ligne de commande lors de l'exécution du programme.

Récemment, elle a été utilisée pour certains problèmes de traitement d'images :

• Détection des bords en temps réel
• Convolution Efficient Parallel Stencil en Haskell

J'ai commencé à écrire un tutoriel sur l'utilisation de repa qui est un bon point de départ si vous connaissez déjà les tableaux Haskell ou la bibliothèque vectorielle. Le principal point de départ est l'utilisation de types de forme au lieu de types d'index simples, pour traiter les index multidimensionnels (et même les stencils).

El repa-io comprend la prise en charge de la lecture et de l'écriture des fichiers image .bmp, bien que la prise en charge d'autres formats soit nécessaire.

Pour répondre à vos questions spécifiques, voici un graphique, accompagné d'une discussion :

---

---

Sur quelle base devrais-je choisir entre Vector.Unboxed et UArray ?

Ils ont à peu près la même représentation sous-jacente, mais la principale différence réside dans l'étendue de l'API permettant de travailler avec des vecteurs : ils disposent de presque toutes les opérations que l'on associe normalement à des listes (avec un cadre d'optimisation axé sur la fusion), alors que UArray n'ont presque pas d'API.

Pour les images en couleur, je souhaite stocker des triples d'entiers de 16 bits ou des triples de nombres à virgule flottante de simple précision.

UArray offre une meilleure prise en charge des données multidimensionnelles, car il peut utiliser des types de données arbitraires pour l'indexation. Bien que cela soit possible dans Vector (en écrivant une instance de UA pour votre type d'élément), ce n'est pas l'objectif premier de la Vector -- à la place, c'est ici que Repa intervient, ce qui permet d'utiliser très facilement des types de données personnalisées stockées de manière efficace, grâce à la fonction forme l'indexation.

En Repa votre triple short aurait le type :

Array DIM3 Word16

C'est-à-dire un tableau 3D de Word16.

Pour les images bitonales, je ne devrai stocker qu'un bit par pixel.

UArrays empaquette les Bools sous forme de bits, Vector utilise l'instance de Bool qui n'empaquette pas les bits, mais utilise plutôt une représentation basée sur Word8 . Cependant, il est facile d'écrire une implémentation du bit-packing pour les vecteurs -- en voici une de la bibliothèque uvector (obsolète). Sous le capot, Repa utilise Vectors Je pense donc qu'il hérite des choix de représentation des bibliothèques.

Existe-t-il un type de données prédéfini qui pourrait m'aider à regrouper plusieurs pixels dans un mot ?

Vous pouvez utiliser les instances existantes pour n'importe quelle bibliothèque, pour différents types de mots, mais vous devrez peut-être écrire quelques aides utilisant Data.Bits pour enrouler et dérouler les données emballées.

Enfin, mes tableaux sont bidimensionnels.

UArray et Repa prennent en charge les tableaux multidimensionnels efficaces. Repa dispose également d'une interface riche pour le faire. Ce n'est pas le cas de Vector.

---

Mentions notables :

• hmatrix un type de tableau personnalisé avec des liens étendus avec les paquets d'algèbre linéaire. Devrait être lié pour utiliser le vector o repa types.
• ix-formable obtenir une indexation plus souple à partir de tableaux réguliers
• Tableau noir La bibliothèque d'Andy Gill pour la manipulation d'images 2D.
• codec-image-devil lire et écrire divers formats d'images dans UArray.

Answer 2

Une fois que j'ai passé en revue les caractéristiques des bibliothèques de tableaux Haskell qui sont importantes pour moi, et que j'ai compilé un tableau comparatif (uniquement feuille de calcul : lien direct ). Je vais donc essayer de répondre.

Sur quelle base devrais-je choisir entre Vector.Unboxed et UArray ? Ce sont tous deux des tableaux non encapsulés, mais l'abstraction Vector semble faire l'objet de beaucoup de publicité, en particulier pour la fusion de boucles. Vector est-il toujours meilleur ? Si ce n'est pas le cas, quand dois-je utiliser quelle représentation ?

UArray peut être préféré à Vector si l'on a besoin de tableaux bidimensionnels ou multidimensionnels. Mais Vector dispose d'une API plus agréable pour manipuler les vecteurs. En général, Vector n'est pas bien adapté à la simulation de tableaux multidimensionnels.

Vector.Unboxed ne peut pas être utilisé avec des stratégies parallèles. Je soupçonne que UArray ne peut pas être utilisé non plus, mais au moins il est très facile de passer de UArray à Array boxé et de voir si les avantages de la parallélisation compensent les coûts du boxage.

Pour les images en couleur, je souhaite stocker des triples d'entiers de 16 bits ou des triples de nombres à virgule flottante de simple précision. À cette fin, Vector ou UArray sont-ils plus faciles à utiliser ? Est-il plus performant ?

J'ai essayé d'utiliser des tableaux pour représenter les images (bien que je n'aie eu besoin que d'images en niveaux de gris). Pour les images en couleur, j'ai utilisé la bibliothèque Codec-Image-DevIL pour lire/écrire les images (bindings à la bibliothèque DevIL), pour les images en niveaux de gris, j'ai utilisé la bibliothèque pgm (pure Haskell).

Mon principal problème avec Array était qu'il ne fournit qu'un stockage à accès aléatoire, mais il ne fournit pas beaucoup de moyens de construire des algorithmes Array et n'est pas livré avec des bibliothèques de routines Array prêtes à l'emploi (il ne s'interface pas avec les bibliothèques d'algèbre linéaire, ne permet pas d'exprimer des convolutions, des fft et d'autres transformations).

Presque à chaque fois qu'un nouveau tableau doit être construit à partir d'un tableau existant, un tableau intermédiaire est créé. liste de valeurs doit être construit (comme dans multiplication matricielle de l'introduction douce). Le coût de la construction d'un tableau l'emporte souvent sur les avantages d'un accès aléatoire plus rapide, au point qu'une représentation basée sur une liste est plus rapide dans certains de mes cas d'utilisation.

STUArray aurait pu m'aider, mais je n'aimais pas me battre avec des erreurs de type cryptiques et les efforts nécessaires pour écrire code polymorphe avec STUArray .

Le problème des tableaux est donc qu'ils ne sont pas bien adaptés aux calculs numériques. Data.Packed.Vector et Data.Packed.Matrix de hmatrix sont meilleurs à cet égard, car ils sont accompagnés d'une solide bibliothèque de matrices (attention : licence GPL). En termes de performance, pour la multiplication de matrices, hmatrix est suffisamment rapide ( seulement légèrement plus lent que Octave ), mais très gourmand en mémoire (il en consomme plusieurs fois plus que Python/SciPy).

Il existe aussi la bibliothèque blas pour les matrices, mais elle n'est pas construite sur GHC7.

Je n'avais pas encore beaucoup d'expérience avec Repa, et je ne comprends pas bien le code Repa. D'après ce que je vois, il y a une gamme très limitée d'algorithmes de matrices et de tableaux prêts à l'emploi écrits dessus, mais il est au moins possible d'exprimer des algorithmes importants au moyen de la bibliothèque. Par exemple, il existe déjà des routines pour multiplication de matrices et pour la convolution dans les repa-algorithmes. Malheureusement, il semble que la convolution soit maintenant limité à 7×7 noyaux (ce n'est pas suffisant pour moi, mais cela devrait suffire pour de nombreuses utilisations).

Je n'ai pas essayé les liaisons Haskell OpenCV. Ils devraient être rapides, car OpenCV est vraiment rapide, mais je ne suis pas sûr que les liaisons soient complètes et suffisamment bonnes pour être utilisables. De plus, OpenCV est par nature très impératif, plein de mises à jour destructives. Je suppose qu'il est difficile de concevoir une interface fonctionnelle agréable et efficace par-dessus. Si l'on suit la voie d'OpenCV, il est probable que l'on utilise la représentation d'image OpenCV partout, et que l'on utilise les routines OpenCV pour les manipuler.

Pour les images bitonales, je ne devrai stocker qu'un bit par pixel. Existe-t-il un type de données prédéfini qui puisse m'aider à regrouper plusieurs pixels dans un mot, ou dois-je me débrouiller tout seul ?

Pour autant que je sache, Tableaux de Bools sans boîte s'occupe de l'emballage et du déballage des vecteurs de bits. Je me souviens avoir regardé l'implémentation de tableaux de Bools dans d'autres bibliothèques, et je n'ai pas vu cela ailleurs.

Enfin, mes tableaux sont bidimensionnels. Je suppose que je pourrais m'accommoder de l'indirection supplémentaire imposée par une représentation sous forme de "tableau de tableaux" (ou de vecteur de vecteurs), mais je préférerais une abstraction qui prenne en charge le mappage d'index. Quelqu'un peut-il me recommander quelque chose dans une bibliothèque standard ou dans Hackage ?

En dehors de Vector (et des listes simples), toutes les autres bibliothèques de tableaux sont capables de représenter des tableaux ou des matrices à deux dimensions. Je suppose qu'elles évitent les indirections inutiles.

Answer 3

Bien que cela ne réponde pas exactement à votre question et que ce ne soit même pas du haskell en tant que tel, je vous recommande de jeter un coup d'œil à CV o Combinateurs CV bibliothèques à hackage. Ils lient les nombreux opérateurs de traitement d'image et de vision plutôt utiles de la bibliothèque opencv et rendent le travail sur les problèmes de vision industrielle beaucoup plus rapide.

Ce serait plutôt génial si quelqu'un trouvait comment repa ou une autre bibliothèque de tableaux pouvait être utilisée directement avec opencv.

Answer 4

Voici un nouveau Bibliothèque de traitement d'images Haskell qui peut prendre en charge toutes les tâches en question et bien plus encore. Actuellement, il utilise Repa y Vecteur pour les représentations sous-jacentes, qui hérite donc de la fusion, du calcul parallèle, de la mutation et de la plupart des autres avantages qui accompagnent ces bibliothèques. Il fournit une interface facile à utiliser qui est naturelle pour la manipulation d'images :

• Indexation 2D et pixels non boxés avec une précision arbitraire ( Double , Float , Word16 etc )
• toutes les fonctions essentielles comme map , fold , zipWith , traverse ...
• prise en charge de divers espaces de couleur : RVB, HSI, échelle de gris, bi-tonal, complexe, etc.
• une fonctionnalité commune de traitement des images :
  • Morphologie binaire
  • Convolution
  • Interpolation
  • transformée de Fourier
  • Tracé d'histogrammes
  • etc.
• Capacité à traiter les pixels et les images comme des nombres réguliers.
• Lecture et écriture de formats d'image courants par JuicyPixels bibliothèque

Plus important encore, il s'agit d'une bibliothèque purement Haskell, qui ne dépend donc d'aucun programme externe. Elle est également très extensible, de nouveaux espaces de couleurs et de nouvelles représentations d'images peuvent être introduits.

Une chose qu'il ne fait pas, c'est d'empaqueter plusieurs pixels binaires dans un même fichier. Word au lieu de cela, il utilise un Word par pixel binaire, peut-être dans un futur...