Какое представление Haskell рекомендуется для 2D, распакованных пиксельных массивов с миллионами пикселей?

Ответ 1

Для многомерных массивов наиболее подходящим вариантом в 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

То есть, 3D-массив из Word16s.

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

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

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

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

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

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

Известные упоминания:

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

Ответ 2

Как только я рассмотрел особенности библиотек массивов 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 и не имеет готовых к использованию библиотек подпрограмм массива (не взаимодействует с линейной алгеброй libs, не позволяет выражать свертки, fft и другие преобразования).

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

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

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

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

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

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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