Jaka reprezentacja Haskell jest zalecana dla 2D, nieopakowanych tablic pikseli z milionami pikseli?

Chcę rozwiązać kilka problemów z przetwarzaniem obrazu w Haskell. Pracuję zarówno z obrazami bitonalnymi (bitmapowymi), jak i kolorowymi z milionami pikseli. Mam kilka pytań:

1. Na jakiej podstawie mam wybierać między Vector.Unboxeda UArray? Obie są tablicami rozpakowanymi, ale Vectorabstrakcja wydaje się mocno reklamowana, szczególnie w przypadku fuzji pętli. Czy Vectorzawsze jest lepsze? Jeśli nie, kiedy należy użyć której reprezentacji?

2. W przypadku obrazów kolorowych będę chciał przechowywać trójek 16-bitowych liczb całkowitych lub trójek liczb zmiennoprzecinkowych o pojedynczej precyzji. W tym celu jest albo Vectorlub UArrayłatwiejsze w użyciu? Bardziej wydajne?

3. W przypadku obrazów bitonalnych będę musiał przechowywać tylko 1 bit na piksel. Czy istnieje predefiniowany typ danych, który może mi pomóc, pakując wiele pikseli w słowo, czy też jestem sam?

4. Wreszcie moje tablice są dwuwymiarowe. Przypuszczam, że mógłbym poradzić sobie z dodatkowym kierunkiem narzuconym przez reprezentację jako „tablica tablic” (lub wektor wektorów), ale wolałbym abstrakcję, która obsługuje mapowanie indeksów. Czy ktoś może polecić coś ze standardowej biblioteki lub z Hackage?

Jestem programistą funkcjonalnym i nie potrzebuję mutacji :-)

Moim zdaniem w przypadku tablic wielowymiarowych obecnie najlepszą opcją w Haskell jest repa .

Repa zapewnia wysokowydajne, regularne, wielowymiarowe, równoległe tablice o polimorficznych kształtach. Wszystkie dane liczbowe są przechowywane bez opakowania. Funkcje napisane za pomocą kombinatorów Repa są automatycznie równoległe, pod warunkiem, że podasz + RTS -Cokolwiek w linii poleceń podczas uruchamiania programu.

Ostatnio był używany do niektórych problemów z przetwarzaniem obrazu:

• Wykrywanie krawędzi w czasie rzeczywistym
• Efektywne równoległe zwoje szablonów w Haskell

Zacząłem pisać samouczek dotyczący korzystania z repa , który jest dobrym miejscem do rozpoczęcia, jeśli znasz już tablice Haskell lub bibliotekę wektorów. Kluczowym krokiem jest użycie typów kształtów zamiast prostych typów indeksowych w celu uwzględnienia wielowymiarowych indeksów (a nawet szablonów).

Pakiet repa-io zawiera obsługę odczytu i zapisu plików obrazów .bmp, chociaż potrzebna jest obsługa większej liczby formatów.

W odpowiedzi na Twoje konkretne pytania, oto grafika z omówieniem:

Na jakiej podstawie mam wybierać między Vector.Unboxed a UArray?

Mają w przybliżeniu tę samą podstawową reprezentację, jednak podstawową różnicą jest szerokość interfejsu API do pracy z wektorami: mają prawie wszystkie operacje, które normalnie kojarzysz z listami (z platformą optymalizacji opartą na fuzji), podczas gdy UArrayprawie brak API.

W przypadku obrazów kolorowych będę chciał przechowywać trójek 16-bitowych liczb całkowitych lub trójek liczb zmiennoprzecinkowych o pojedynczej precyzji.

UArrayma lepszą obsługę danych wielowymiarowych, ponieważ może używać dowolnych typów danych do indeksowania. Chociaż jest to możliwe w Vector(pisząc wystąpienie UAdla typu elementu), nie jest to głównym celem Vector- zamiast tego jest to miejsce, w którym Repawkracza, co bardzo ułatwia korzystanie z niestandardowych typów danych przechowywanych w efektywny sposób, dzięki indeksowaniu kształtu .

W Repatwoim potrójnym spodenku będzie typ:

Array DIM3 Word16

Oznacza to trójwymiarową tablicę Word16.

W przypadku obrazów bitonalnych będę musiał przechowywać tylko 1 bit na piksel.

UArrays pakują Bools jako bity, Vector używa instancji dla Bool, która wykonuje pakowanie bitów, zamiast tego używa reprezentacji opartej na Word8. Jakkolwiek, łatwo jest napisać implementację pakowania bitów dla wektorów - oto jedna z (przestarzałej) biblioteki uvector. Pod maską Repaużywa Vectors, więc myślę, że dziedziczy wybory reprezentacji bibliotek.

Czy istnieje predefiniowany typ danych, który może mi tutaj pomóc, pakując wiele pikseli w słowo

Możesz użyć istniejących instancji dla dowolnej biblioteki, dla różnych typów słów, ale może być konieczne napisanie kilku pomocników przy użyciu Data.Bits do przewijania i rozwijania spakowanych danych.

Wreszcie moje tablice są dwuwymiarowe

UArray i Repa obsługują wydajne tablice wielowymiarowe. Repa ma również bogaty interfejs do tego. Sam Vector tego nie robi.

Wybitne wzmianki:

• hmatrix , niestandardowy typ tablicy z rozbudowanymi powiązaniami z pakietami algebry liniowej. Powinien być zobowiązany do używania typów vectorlub repa.
• ix-shapeable , uzyskując bardziej elastyczne indeksowanie ze zwykłych tablic
• chalkboard , biblioteka Andy'ego Gilla do manipulowania obrazami 2D
• codec-image-devil , czytaj i zapisuj różne formaty obrazów na UArray

Kiedyś przejrzałem funkcje bibliotek tablicowych Haskell, które są dla mnie ważne, i skompilowałem tabelę porównawczą (tylko arkusz kalkulacyjny: bezpośredni link ). Więc spróbuję odpowiedzieć.

Na jakiej podstawie mam wybierać między Vector.Unboxed a UArray? Obie są tablicami rozpakowanymi, ale abstrakcja Vector wydaje się mocno reklamowana, szczególnie wokół fuzji pętli. Czy Vector jest zawsze lepszy? Jeśli nie, kiedy należy użyć której reprezentacji?

UArray może być preferowany względem Vector, jeśli potrzebne są tablice dwuwymiarowe lub wielowymiarowe. Ale Vector ma lepszy interfejs API do manipulowania, no cóż, wektorami. Ogólnie rzecz biorąc, Vector nie nadaje się dobrze do symulowania tablic wielowymiarowych.

Vector.Unboxed nie może być używany ze strategiami równoległymi. Podejrzewam, że UArray również nie może być używany, ale przynajmniej bardzo łatwo jest przejść z UArray na boxed Array i zobaczyć, czy korzyści z równoległości przewyższają koszty pakowania.

W przypadku obrazów kolorowych będę chciał przechowywać trójek 16-bitowych liczb całkowitych lub trójek liczb zmiennoprzecinkowych o pojedynczej precyzji. Czy w tym celu łatwiej jest używać Vector lub UArray? Bardziej wydajne?

Próbowałem używać tablic do reprezentowania obrazów (chociaż potrzebowałem tylko obrazów w skali szarości). Do obrazów kolorowych użyłem biblioteki Codec-Image-DevIL do odczytu / zapisu obrazów (powiązania z biblioteką DevIL), dla obrazów w skali szarości użyłem biblioteki pgm (czysty Haskell).

Moim głównym problemem związanym z Arrayem było to, że zapewnia on tylko pamięć o dostępie swobodnym, ale nie zapewnia wielu sposobów budowania algorytmów Array ani nie zawiera gotowych do użycia bibliotek procedur tablicowych (nie współpracuje z bibliotekami algebry liniowej, nie nie pozwalają na wyrażanie splotów, fft i innych przekształceń).

Prawie za każdym razem, gdy trzeba zbudować nową tablicę z istniejącej, należy skonstruować pośrednią listę wartości (jak w mnożeniu macierzy z Łagodnego wprowadzenia). Koszt budowy tablicy często przewyższa korzyści płynące z szybszego losowego dostępu do tego stopnia, że ​​reprezentacja oparta na liście jest szybsza w niektórych moich przypadkach użycia.

STUArray mógł mi pomóc, ale nie lubiłem walczyć z tajemniczymi błędami typu i wysiłkami niezbędnymi do napisania kodu polimorficznego za pomocą STUArray .

Problem z tablicami polega na tym, że nie nadają się one dobrze do obliczeń numerycznych. Hmatrix 'Data.Packed.Vector i Data.Packed.Matrix są lepsze pod tym względem, ponieważ są dostarczane wraz z solidną biblioteką macierzy (uwaga: licencja GPL). Pod względem wydajności, przy mnożeniu macierzy, hmatrix była wystarczająco szybka ( tylko nieznacznie wolniejsza niż Octave ), ale bardzo wymagała pamięci (zużywała kilka razy więcej niż Python / SciPy).

Istnieje również biblioteka blas dla macierzy, ale nie jest oparta na GHC7.

Nie miałem jeszcze dużego doświadczenia z Repą i nie rozumiem dobrze kodu repa. Z tego co widzę ma bardzo ograniczony zakres gotowych do użycia algorytmów macierzowych i tablicowych napisanych na wierzchu, ale przynajmniej da się wyrazić za pomocą biblioteki ważne algorytmy. Na przykład, istnieją już procedury mnożenia macierzy i splotu w algorytmach repa. Niestety wydaje się, że splot jest teraz ograniczony do jądra 7 × 7 (dla mnie to nie wystarcza, ale powinno wystarczyć do wielu zastosowań).

Nie próbowałem powiązań Haskell OpenCV. Powinny być szybkie, ponieważ OpenCV jest naprawdę szybkie, ale nie jestem pewien, czy wiązania są kompletne i wystarczająco dobre, aby nadawały się do użytku. Ponadto OpenCV ze swej natury jest bardzo niezbędny, pełen destrukcyjnych aktualizacji. Podejrzewam, że ciężko jest zaprojektować na dodatek ładny i wydajny funkcjonalny interfejs. Jeśli ktoś pójdzie drogą OpenCV, prawdopodobnie użyje reprezentacji obrazu OpenCV wszędzie i użyje procedur OpenCV do manipulowania nimi.

W przypadku obrazów bitonalnych będę musiał przechowywać tylko 1 bit na piksel. Czy istnieje predefiniowany typ danych, który może mi pomóc, pakując wiele pikseli w słowo, czy też jestem sam?

O ile wiem, Unboxed tablice Bools zajmują się pakowaniem i rozpakowywaniem wektorów bitowych. Pamiętam, jak patrzyłem na implementację tablic Bools w innych bibliotekach i nie widziałem tego nigdzie indziej.

Wreszcie moje tablice są dwuwymiarowe. Przypuszczam, że mógłbym poradzić sobie z dodatkowym kierunkiem narzuconym przez reprezentację jako „tablica tablic” (lub wektor wektorów), ale wolałbym abstrakcję, która obsługuje mapowanie indeksów. Czy ktoś może polecić coś ze standardowej biblioteki lub z Hackage?

Oprócz Vector (i prostych list), wszystkie inne biblioteki tablic mogą reprezentować dwuwymiarowe tablice lub macierze. Przypuszczam, że unikają niepotrzebnego pośrednictwa.

Chociaż nie jest to dokładna odpowiedź na twoje pytanie i tak naprawdę nie jest nawet haskellem jako takim, polecam przyjrzeć się CV lub kombinatorom CV bibliotekom podczas hackage. Łączą one wielu dość użytecznych operatorów przetwarzania obrazu i wizyjnych z biblioteki opencv i znacznie przyspieszają pracę z problemami z widzeniem maszynowym.

Byłoby raczej wspaniale, gdyby ktoś odkrył, w jaki sposób repa lub jakaś taka biblioteka tablic może być bezpośrednio używana z opencv.

Oto nowa biblioteka Haskell Image Processing, która może obsłużyć wszystkie wymienione zadania i wiele więcej. Obecnie używa pakietów Repa i Vector do reprezentacji bazowych, co w konsekwencji dziedziczy fuzję, obliczenia równoległe, mutację i większość innych dodatków, które są dostarczane z tymi bibliotekami. Zapewnia łatwy w użyciu interfejs, który jest naturalny do manipulacji obrazem:

• Indeksowanie 2D i Rozpakowanych pikseli z dowolną dokładnością ( Double, Float,Word16 itd ..)
• Wszystkie istotne funkcje, takie jak map, fold, zipWith,traverse ...
• obsługa różnych przestrzeni barwnych: RGB, HSI, skala szarości, Bi-tonal, Complex itp.
• wspólna funkcjonalność przetwarzania obrazu:
  • Morfologia binarna
  • Skręt
  • Interpolacja
  • Przekształcenie Fouriera
  • Wykres histogramu
  • itp.
• Możliwość traktowania pikseli i obrazów jako zwykłych liczb.
• Czytanie i pisanie popularnych formatów obrazów za pośrednictwem biblioteki JuicyPixels

Co najważniejsze, jest to czysta biblioteka Haskella, więc nie jest zależna od żadnych zewnętrznych programów. Jest również wysoce rozszerzalny, można wprowadzić nowe przestrzenie kolorów i reprezentacje obrazów.

Jedyną rzeczą, której nie robi, jest pakowanie wielu pikseli binarnych w a Word, zamiast tego używa Wordjednego piksela binarnego, być może w przyszłości ...