Какое представление Haskell рекомендуется для двумерных массивов пикселей без упаковки с миллионами пикселей?

Я хочу решить некоторые проблемы с обработкой изображений в Haskell. Я работаю как с растровыми (растровыми), так и с цветными изображениями с миллионами пикселей. У меня есть ряд вопросов:

1. На каком основании мне выбирать между Vector.Unboxedи UArray? Оба являются распакованными массивами, но Vectorабстракция, кажется, сильно разрекламирована, особенно в отношении слияния циклов. Есть Vectorвсегда лучше? Если нет, то когда мне следует использовать какое представление?

2. Для цветных изображений я хочу хранить тройки 16-битных целых чисел или тройки чисел с плавающей запятой одинарной точности. Для этой цели использовать Vectorили UArrayпроще? Более производительный?

3. Для битональных изображений мне нужно будет хранить только 1 бит на пиксель. Есть ли предопределенный тип данных, который может помочь мне здесь, упаковав несколько пикселей в слово, или я один?

4. Наконец, мои массивы двумерны. Я полагаю, что мог бы иметь дело с дополнительным косвенным обращением, вызванным представлением в виде «массива массивов» (или вектора векторов), но я бы предпочел абстракцию, которая поддерживает отображение индекса. Кто-нибудь может посоветовать что-нибудь из стандартной библиотеки или от Hackage?

Я функциональный программист и не нуждаюсь в мутации :-)

На мой взгляд, для многомерных массивов лучшим вариантом в Haskell является repa .

Repa предоставляет высокопроизводительные, регулярные, многомерные, полиморфные параллельные массивы формы. Все числовые данные хранятся без упаковки. Функции, написанные с помощью комбинаторов Repa, автоматически распараллеливаются при условии, что вы укажете + RTS -Nwhatever в командной строке при запуске программы.

В последнее время его использовали для решения некоторых проблем с обработкой изображений:

• Обнаружение края в реальном времени
• Эффективная параллельная свертка трафарета в Haskell

Я начал писать учебник по использованию repa , который является хорошим началом, если вы уже знакомы с массивами Haskell или векторной библиотекой. Ключевым моментом является использование типов фигур вместо простых типов индексов для работы с многомерными индексами (и даже шаблонами).

Пакет repa-io включает поддержку чтения и записи файлов изображений .bmp, хотя требуется поддержка большего количества форматов.

Отвечая на ваши конкретные вопросы, вот рисунок с обсуждением:

На каком основании мне выбирать между Vector.Unboxed и UArray?

У них примерно одинаковое базовое представление, однако основное отличие заключается в широте API для работы с векторами: в них есть почти все операции, которые вы обычно связываете со списками (с фреймворком оптимизации на основе слияния), в то время как у UArrayних почти нет API.

Для цветных изображений я хочу хранить тройки 16-битных целых чисел или тройки чисел с плавающей запятой одинарной точности.

UArrayлучше поддерживает многомерные данные, так как может использовать произвольные типы данных для индексации. Хотя это возможно Vector(путем написания экземпляра UAдля вашего типа элемента), это не является основной целью Vector- вместо этого здесь Repaвступает в действие, упрощая использование настраиваемых типов данных, хранимых эффективным образом, благодаря индексации формы .

В Repa, ваша тройка шорт будет иметь тип:

Array DIM3 Word16

То есть трехмерный массив Word16s.

Для битональных изображений мне нужно будет хранить только 1 бит на пиксель.

UArrays упаковывает Bools как биты, Vector использует экземпляр для Bool, который выполняет битовую упаковку, вместо этого используя представление на основе Word8. Однако написать реализацию битовой упаковки для векторов несложно - вот она из (устаревшей) библиотеки uvector. Под капотом Repaиспользует Vectors, поэтому я думаю, что он наследует выбор представления библиотек.

Есть ли предопределенный тип данных, который может помочь мне здесь, упаковав несколько пикселей в слово?

Вы можете использовать существующие экземпляры для любой из библиотек для разных типов слов, но вам может потребоваться написать несколько помощников, использующих Data.Bits, для сворачивания и разворачивания упакованных данных.

Наконец, мои массивы двумерные

UArray и Repa поддерживают эффективные многомерные массивы. Repa также имеет для этого богатый интерфейс. Вектор сам по себе этого не делает.

Примечательные упоминания:

• hmatrix , настраиваемый тип массива с обширными привязками к пакетам линейной алгебры. Следует обязательно использовать типы vectorили repa.
• ix-shapeable , получение более гибкой индексации из обычных массивов
• chalkboard , библиотека Энди Гилла для работы с 2D-изображениями
• codec-image-devil , чтение и запись различных форматов изображений в UArray

Однажды я рассмотрел важные для меня функции библиотек массивов Haskell и составил сравнительную таблицу (только электронная таблица: прямая ссылка ). Так что попробую ответить.

На каком основании мне выбирать между Vector.Unboxed и UArray? Оба являются распакованными массивами, но абстракция Vector, кажется, сильно разрекламирована, особенно в отношении слияния циклов. Вектор всегда лучше? Если нет, то когда мне следует использовать какое представление?

UArray может быть предпочтительнее Vector, если нужны двумерные или многомерные массивы. Но у Vector есть более приятный API для управления векторами. В общем, Vector не очень хорошо подходит для моделирования многомерных массивов.

Vector.Unboxed нельзя использовать с параллельными стратегиями. Я подозреваю, что UArray также нельзя использовать, но, по крайней мере, очень легко переключиться с UArray на массив в штучной упаковке и посмотреть, перевешивают ли преимущества распараллеливания затраты на упаковку.

Для цветных изображений я хочу хранить тройки 16-битных целых чисел или тройки чисел с плавающей запятой одинарной точности. Что для этого проще использовать: Vector или UArray? Более производительный?

Я пробовал использовать массивы для представления изображений (хотя мне нужны были только изображения в оттенках серого). Для цветных изображений я использовал библиотеку Codec-Image-DevIL для чтения / записи изображений (привязки к библиотеке DevIL), для изображений в оттенках серого я использовал библиотеку pgm (чистый Haskell).

Моя основная проблема с Array заключалась в том, что он предоставляет только хранилище с произвольным доступом, но он не предоставляет многих средств для построения алгоритмов Array и не поставляется с готовыми к использованию библиотеками процедур массива (не взаимодействует с библиотеками линейной алгебры, не не позволяют выражать свертки, fft и другие преобразования).

Почти каждый раз, когда новый массив должен быть построен из существующего, должен быть построен промежуточный список значений (как в умножении матриц из мягкого введения). Стоимость построения массива часто перевешивает преимущества более быстрого произвольного доступа до такой степени, что представление на основе списка работает быстрее в некоторых из моих сценариев использования.

STUArray мог бы мне помочь, но мне не нравилось бороться с ошибками загадочного типа и усилия, необходимые для написания полиморфного кода с помощью STUArray .

Проблема с массивами в том, что они плохо подходят для численных вычислений. Hmatrix 'Data.Packed.Vector и Data.Packed.Matrix в этом отношении лучше, потому что они поставляются вместе с библиотекой твердых матриц (внимание: лицензия GPL). С точки зрения производительности при умножении матриц hmatrix была достаточно быстрой ( лишь немного медленнее, чем Octave ), но очень требовательной к памяти (потребляла в несколько раз больше, чем Python / SciPy).

Также существует библиотека blas для матриц, но она не построена на GHC7.

У меня еще не было большого опыта работы с Repa, и я плохо понимаю код репа. Насколько я понимаю, он имеет очень ограниченный набор готовых к использованию алгоритмов матрицы и массива, написанных поверх него, но, по крайней мере, можно выразить важные алгоритмы с помощью библиотеки. Например, в алгоритмах восстановления уже есть процедуры для умножения матриц и свертки . К сожалению, похоже, что свертка теперь ограничена ядрами 7 × 7 (для меня этого недостаточно, но должно хватить для многих целей).

Я не пробовал связывания Haskell OpenCV. Они должны быть быстрыми, потому что OpenCV действительно быстр, но я не уверен, что привязки полны и достаточно хороши, чтобы их можно было использовать. Кроме того, OpenCV по своей природе очень важен, полон деструктивных обновлений. Я полагаю, что сложно создать на его основе красивый и эффективный функциональный интерфейс. Если кто-то пойдет по пути OpenCV, он, вероятно, будет везде использовать представление изображений OpenCV и использовать процедуры OpenCV для управления ими.

Для битональных изображений мне нужно будет хранить только 1 бит на пиксель. Есть ли предопределенный тип данных, который может помочь мне здесь, упаковав несколько пикселей в слово, или я один?

Насколько я знаю, Unboxed-массивы Bools заботятся об упаковке и распаковке битовых векторов. Я помню, как смотрел на реализацию массивов Bools в других библиотеках и нигде не видел этого.

Наконец, мои массивы двумерны. Я полагаю, что мог бы иметь дело с дополнительным косвенным обращением, вызванным представлением в виде «массива массивов» (или вектора векторов), но я бы предпочел абстракцию, которая поддерживает отображение индекса. Кто-нибудь может посоветовать что-нибудь из стандартной библиотеки или от Hackage?

Кроме вектора (и простых списков), все другие библиотеки массивов могут представлять двумерные массивы или матрицы. Я полагаю, они избегают ненужного косвенного обращения.

Хотя это не совсем ответ на ваш вопрос и даже не haskell как таковой, я бы рекомендовал взглянуть на библиотеки CV или CV-комбинаторов на hackage. Они связывают многие довольно полезные операторы обработки изображений и зрения из библиотеки opencv и значительно ускоряют работу с проблемами машинного зрения.

Было бы неплохо, если бы кто-нибудь выяснил, как repa или какая-то такая библиотека массивов может быть напрямую использована с opencv.

Вот новая библиотека обработки изображений Haskell, которая может обрабатывать все рассматриваемые задачи и многое другое. В настоящее время он использует пакеты Repa и Vector для базовых представлений, которые, следовательно, наследуют слияние, параллельное вычисление, мутацию и большинство других преимуществ, которые поставляются с этими библиотеками. Он предоставляет простой в использовании интерфейс, естественный для работы с изображениями:

• 2D индексации и Unboxed пикселей с произвольной точностью ( Double, Float, Word16и т.д ..)
• все основные функции , такие как map, fold, zipWith, traverse...
• поддержка различных цветовых пространств: RGB, HSI, градации серого, двухтональный, сложный и т. д.
• общие функции обработки изображений:
  • Бинарная морфология
  • свертка
  • интерполирование
  • преобразование Фурье
  • Построение гистограммы
  • и т.п.
• Возможность рассматривать пиксели и изображения как обычные числа.
• Чтение и запись распространенных форматов изображений через библиотеку JuicyPixels

Что наиболее важно, это чистая библиотека Haskell, поэтому она не зависит от каких-либо внешних программ. Он также имеет широкие возможности расширения, могут быть введены новые цветовые пространства и представления изображений.

Одна вещь, которую он не делает, это упаковка нескольких двоичных пикселей в a Word, вместо этого он использует Wordкаждый двоичный пиксель, возможно, в будущем ...