Welche Haskell-Darstellung wird für 2D-Pixel-Arrays ohne Box mit Millionen von Pixeln empfohlen?

Ich möchte einige Bildverarbeitungsprobleme in Haskell angehen. Ich arbeite sowohl mit bitonalen (Bitmap) als auch mit Farbbildern mit Millionen von Pixeln. Ich habe eine Reihe von Fragen:

1. Auf welcher Basis soll ich zwischen Vector.Unboxedund wählen UArray? Sie sind beide Arrays ohne Box, aber die VectorAbstraktion scheint stark beworben zu sein, insbesondere im Zusammenhang mit der Schleifenfusion. Ist Vectorimmer besser Wenn nicht, wann sollte ich welche Darstellung verwenden?

2. Für Farbbilder möchte ich Tripel von 16-Bit-Ganzzahlen oder Tripel von Gleitkommazahlen mit einfacher Genauigkeit speichern. Ist zu diesem Zweck entweder Vectoroder UArrayeinfacher zu bedienen? Performanter?

3. Für bitonale Bilder muss ich nur 1 Bit pro Pixel speichern. Gibt es einen vordefinierten Datentyp, der mir hier helfen kann, indem ich mehrere Pixel in ein Wort packe, oder bin ich allein?

4. Schließlich sind meine Arrays zweidimensional. Ich nehme an, ich könnte mich mit der zusätzlichen Indirektion befassen, die durch eine Darstellung als "Array von Arrays" (oder Vektor von Vektoren) auferlegt wird, aber ich würde eine Abstraktion bevorzugen, die Index-Mapping-Unterstützung bietet. Kann jemand etwas aus einer Standardbibliothek oder von Hackage empfehlen?

Ich bin ein funktionierender Programmierer und brauche keine Mutation :-)

Für mehrdimensionale Arrays ist aus meiner Sicht repa die derzeit beste Option in Haskell .

Repa bietet hochleistungsfähige, regelmäßige, mehrdimensionale, formpolymorphe parallele Arrays. Alle numerischen Daten werden ohne Box gespeichert. Mit den Repa-Kombinatoren geschriebene Funktionen werden automatisch parallel ausgeführt, sofern Sie beim Ausführen des Programms + RTS -Nwas auch immer in der Befehlszeile angeben.

In letzter Zeit wurde es für einige Bildverarbeitungsprobleme verwendet:

• Echtzeit-Kantenerkennung
• Effiziente parallele Schablonenfaltung in Haskell

Ich habe angefangen, ein Tutorial über die Verwendung von Repa zu schreiben. Dies ist ein guter Ausgangspunkt, wenn Sie Haskell-Arrays oder die Vektorbibliothek bereits kennen. Das wichtigste Sprungbrett ist die Verwendung von Formtypen anstelle einfacher Indextypen, um mehrdimensionale Indizes (und sogar Schablonen) zu adressieren.

Das Repa-Io- Paket bietet Unterstützung für das Lesen und Schreiben von BMP-Bilddateien, obwohl Unterstützung für weitere Formate erforderlich ist.

Hier ist eine Grafik mit Diskussion zu Ihren spezifischen Fragen:

Auf welcher Basis sollte ich zwischen Vector.Unboxed und UArray wählen?

Sie haben ungefähr die gleiche zugrunde liegende Darstellung, der Hauptunterschied ist jedoch die Breite der API für die Arbeit mit Vektoren: Sie haben fast alle Operationen, die Sie normalerweise mit Listen verknüpfen würden (mit einem fusionsgesteuerten Optimierungsframework), während UArraysie fast haben keine API.

Für Farbbilder möchte ich Tripel von 16-Bit-Ganzzahlen oder Tripel von Gleitkommazahlen mit einfacher Genauigkeit speichern.

UArraybietet eine bessere Unterstützung für mehrdimensionale Daten, da beliebige Datentypen für die Indizierung verwendet werden können. Dies ist zwar in Vector(durch Schreiben einer Instanz UAfür Ihren Elementtyp) möglich, aber nicht das Hauptziel von Vector- stattdessen Repatritt hier ein, wodurch es sehr einfach wird, benutzerdefinierte Datentypen zu verwenden, die auf effiziente Weise gespeichert werden. dank der Form Indizierung.

In würde RepaIhre dreifache Shorts den Typ haben:

Array DIM3 Word16

Das heißt, ein 3D-Array von Word16s.

Für bitonale Bilder muss ich nur 1 Bit pro Pixel speichern.

UArrays packen Bools als Bits, Vector verwendet die Instanz für Bool, die das Bitpacken ausführt, anstatt eine Darstellung basierend auf Word8. Es ist jedoch einfach, eine Bit-Packing-Implementierung für Vektoren zu schreiben - hier eine aus der (veralteten) Uvector-Bibliothek. Unter der Haube RepaverwendetVectors , so dass ich denke, es erbt, dass Bibliotheken Repräsentationsoptionen.

Gibt es einen vordefinierten Datentyp, der mir hier helfen kann, indem mehrere Pixel in ein Wort gepackt werden?

Sie können die vorhandenen Instanzen für jede der Bibliotheken für verschiedene Worttypen verwenden, müssen jedoch möglicherweise einige Helfer mit Data.Bits schreiben, um gepackte Daten zu rollen und zu entrollen.

Schließlich sind meine Arrays zweidimensional

UArray und Repa unterstützen effiziente mehrdimensionale Arrays. Repa hat auch eine reichhaltige Oberfläche dafür. Vektor allein nicht.

Bemerkenswerte Erwähnungen:

• hmatrix , ein benutzerdefinierter Array-Typ mit umfangreichen Bindungen an lineare Algebra-Pakete. Sollte verpflichtet sein, die Typen vectoroder zu repaverwenden.
• ix-formbar , flexiblere Indizierung durch reguläre Arrays
• Tafel , Andy Gills Bibliothek zur Bearbeitung von 2D-Bildern
• Codec-Image-Devil , lesen und schreiben Sie verschiedene Bildformate in UArray

Einmal habe ich die für mich wichtigen Funktionen der Haskell-Array-Bibliotheken überprüft und eine Vergleichstabelle erstellt (nur Tabellenkalkulation: direkter Link ). Also werde ich versuchen zu antworten.

Auf welcher Basis sollte ich zwischen Vector.Unboxed und UArray wählen? Sie sind beide Arrays ohne Box, aber die Vektorabstraktion scheint stark beworben zu sein, insbesondere im Bereich der Schleifenfusion. Ist Vector immer besser? Wenn nicht, wann sollte ich welche Darstellung verwenden?

UArray kann gegenüber Vector bevorzugt werden, wenn zweidimensionale oder mehrdimensionale Arrays benötigt werden. Aber Vector hat eine schönere API zum Manipulieren von Vektoren. Im Allgemeinen ist Vector nicht gut zum Simulieren mehrdimensionaler Arrays geeignet.

Vector.Unboxed kann nicht mit parallelen Strategien verwendet werden. Ich vermute, dass UArray auch nicht verwendet werden kann, aber es ist zumindest sehr einfach, von UArray zu Boxed Array zu wechseln und zu prüfen, ob die Vorteile der Parallelisierung die Boxkosten übersteigen.

Für Farbbilder möchte ich Tripel von 16-Bit-Ganzzahlen oder Tripel von Gleitkommazahlen mit einfacher Genauigkeit speichern. Ist zu diesem Zweck entweder Vector oder UArray einfacher zu verwenden? Performanter?

Ich habe versucht, Arrays zur Darstellung von Bildern zu verwenden (obwohl ich nur Graustufenbilder benötigte). Für Farbbilder habe ich die Codec-Image-DevIL-Bibliothek zum Lesen / Schreiben von Bildern (Bindungen an die DevIL-Bibliothek) verwendet, für Graustufenbilder habe ich die pgm-Bibliothek (reines Haskell) verwendet.

Mein Hauptproblem mit Array war, dass es nur Direktzugriffsspeicher bietet, aber nicht viele Möglichkeiten zum Erstellen von Array-Algorithmen bietet und auch keine gebrauchsfertigen Bibliotheken von Array-Routinen enthält (keine Schnittstelle zu linearen Algebra-Bibliotheken, nicht wahr? Erlaube nicht, Windungen, FFT und andere Transformationen auszudrücken.

Fast jedes Mal , wenn ein neues Array hat aus dem bestehenden gebaut werden, eine Zwischenliste von Werten muss so konstruiert werden (wie in der Matrixmultiplikation aus der sanften Einführung). Die Kosten für die Array-Konstruktion überwiegen häufig die Vorteile eines schnelleren Direktzugriffs, sodass eine listenbasierte Darstellung in einigen meiner Anwendungsfälle schneller ist.

STUArray hätte mir helfen können, aber ich mochte es nicht, mit kryptischen Typfehlern und den Anstrengungen zu kämpfen, die erforderlich waren, um mit STUArray polymorphen Code zu schreiben .

Das Problem mit Arrays ist also, dass sie für numerische Berechnungen nicht gut geeignet sind. Hmatrix 'Data.Packed.Vector und Data.Packed.Matrix sind in dieser Hinsicht besser, da sie mit einer soliden Matrixbibliothek geliefert werden (Achtung: GPL-Lizenz). In Bezug auf die Leistung war die Matrix bei der Matrixmultiplikation ausreichend schnell ( nur geringfügig langsamer als Octave ), aber sehr speicherhungrig (mehrmals mehr als Python / SciPy verbraucht).

Es gibt auch eine Blas-Bibliothek für Matrizen, die jedoch nicht auf GHC7 aufbaut.

Ich hatte noch nicht viel Erfahrung mit Repa und verstehe den Repa-Code nicht gut. Soweit ich sehe, gibt es nur eine sehr begrenzte Auswahl an gebrauchsfertigen Matrix- und Array-Algorithmen, die darüber geschrieben wurden, aber es ist zumindest möglich, wichtige Algorithmen mithilfe der Bibliothek auszudrücken. Beispielsweise gibt es bereits Routinen zur Matrixmultiplikation und zur Faltung in Repa-Algorithmen. Leider scheint die Faltung jetzt auf 7 × 7-Kernel beschränkt zu sein (es reicht mir nicht, sollte aber für viele Zwecke ausreichen).

Ich habe keine Haskell OpenCV-Bindungen ausprobiert. Sie sollten schnell sein, da OpenCV sehr schnell ist, aber ich bin mir nicht sicher, ob die Bindungen vollständig und gut genug sind, um verwendet werden zu können. Außerdem ist OpenCV von Natur aus sehr wichtig und voller destruktiver Updates. Ich nehme an, es ist schwierig, darüber eine schöne und effiziente funktionale Oberfläche zu entwerfen. Wenn jemand OpenCV-Weg geht, wird er wahrscheinlich überall OpenCV-Bilddarstellung verwenden und OpenCV-Routinen verwenden, um sie zu manipulieren.

Für bitonale Bilder muss ich nur 1 Bit pro Pixel speichern. Gibt es einen vordefinierten Datentyp, der mir hier helfen kann, indem mehrere Pixel in ein Wort gepackt werden, oder bin ich allein?

Soweit ich weiß, kümmern sich Unboxed-Arrays von Bools um das Packen und Entpacken von Bitvektoren. Ich erinnere mich, dass ich mir die Implementierung von Arrays von Bools in anderen Bibliotheken angesehen habe und dies anderswo nicht gesehen habe.

Schließlich sind meine Arrays zweidimensional. Ich nehme an, ich könnte mich mit der zusätzlichen Indirektion befassen, die durch eine Darstellung als "Array von Arrays" (oder Vektor von Vektoren) auferlegt wird, aber ich würde eine Abstraktion bevorzugen, die Index-Mapping-Unterstützung bietet. Kann jemand etwas aus einer Standardbibliothek oder von Hackage empfehlen?

Mit Ausnahme von Vector (und einfachen Listen) können alle anderen Array-Bibliotheken zweidimensionale Arrays oder Matrizen darstellen. Ich nehme an, sie vermeiden unnötige Indirektion.

Obwohl dies Ihre Frage nicht genau beantwortet und als solches nicht wirklich haskell ist, würde ich empfehlen, sich bei Hackage einen Blick auf die Bibliotheken von CV oder CV-Kombinatoren zu werfen. Sie binden die vielen nützlichen Bildverarbeitungs- und Bildverarbeitungsoperatoren aus der opencv-Bibliothek und beschleunigen die Arbeit mit Bildverarbeitungsproblemen erheblich.

Es wäre ziemlich großartig, wenn jemand herausfinden würde, wie repa oder eine solche Array-Bibliothek direkt mit opencv verwendet werden könnte.

Hier ist eine neue Haskell Image Processing-Bibliothek , die alle fraglichen Aufgaben und vieles mehr erledigt. Derzeit werden Repa- und Vektor- Pakete für zugrunde liegende Darstellungen verwendet, die folglich Fusion, parallele Berechnung, Mutation und die meisten anderen mit diesen Bibliotheken gelieferten Extras erben. Es bietet eine benutzerfreundliche Oberfläche, die für die Bildmanipulation selbstverständlich ist:

• 2D - Indizierung und unboxed Pixel mit beliebiger Genauigkeit ( Double, Float, Word16, etc ..)
• alle wesentlichen Funktionen wie map, fold, zipWith, traverse...
• Unterstützung für verschiedene Farbräume: RGB, HSI, Graustufen, Bi-Ton, Komplex usw.
• allgemeine Bildverarbeitungsfunktionen:
  • Binäre Morphologie
  • Faltung
  • Interpolation
  • Fourier-Transformation
  • Histogramm-Plotten
  • etc.
• Möglichkeit, Pixel und Bilder als reguläre Zahlen zu behandeln.
• Lesen und Schreiben gängiger Bildformate über die JuicyPixels- Bibliothek

Am wichtigsten ist, dass es sich um eine reine Haskell-Bibliothek handelt, sodass keine externen Programme erforderlich sind. Es ist auch sehr erweiterbar, neue Farbräume und Bilddarstellungen können eingeführt werden.

Eine Sache, die es nicht tut, ist das Packen mehrerer Binärpixel in a Word, stattdessen wird ein Wordpro Binärpixel verwendet, vielleicht in einer Zukunft ...