Написание функциональной и в то же время функциональной библиотеки обработки изображений в Scala

Question

Мы разрабатываем небольшую библиотеку обработки изображений для Scala (студенческий проект). Библиотека является полностью функциональной (то есть не изменяемой). Растр изображения сохраняется как Stream[Stream[Int]], чтобы использовать преимущества ленивой оценки с наименьшими усилиями. Однако после выполнения нескольких операций над изображением куча заполняется, и OutOfMemoryError выбрасывается. (например, можно выполнить до 4 операций над изображением jpeg размером 500 x 400, 35 КБ, прежде чем в куче JVM не будет исчерпано пространство.)

Подходы, о которых мы думали:

• Поворачиваем с опциями JVM и увеличиваем размер кучи. (Мы не знаем, как это сделать в IDEA - в IDE, с которой мы работаем.)
• Выбор структуры данных, отличной от Stream[Stream[Int]], которая больше подходит для задачи обработки изображений. (Опять же, мы не имеем большого представления о функциональных структурах данных, кроме простых List и Stream.)

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

Спасибо,
Сиддхарт Райна.

ДОПОЛНЕНИЕ:
Для изображения размером 1024 x 768 JVM не хватает места в куче даже для одной операции сопоставления. Пример кода из нашего теста:

val image = Image from "E:/metallica.jpg"
val redded = image.map(_ & 0xff0000)
redded.display(title = "Redded")

И вывод:

"C:\Program Files (x86)\Java\jdk1.6.0_02\bin\java" -Didea.launcher.port=7533 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA Community Edition 10.0.2\bin" -Dfile.encoding=windows-1252 -classpath "C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\charsets.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\deploy.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\javaws.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\jce.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\jsse.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\management-agent.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\plugin.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\resources.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\rt.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\ext\dnsns.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\ext\localedata.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\ext\sunjce_provider.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\ext\sunmscapi.jar;C:\Program Files (x86)\Java\jdk1.6.0_02\jre\lib\ext\sunpkcs11.jar;C:\new Ph\Phoebe\out\production\Phoebe;E:\Inventory\Marvin.jar;C:\scala-2.8.1.final\lib\scala-library.jar;C:\scala-2.8.1.final\lib\scala-swing.jar;C:\scala-2.8.1.final\lib\scala-dbc.jar;C:\new Ph;C:\scala-2.8.1.final\lib\scala-compiler.jar;E:\Inventory\commons-math-2.2.jar;E:\Inventory\commons-math-2.2-sources.jar;E:\Inventory\commons-math-2.2-javadoc.jar;E:\Inventory\jmathplot.jar;E:\Inventory\jmathio.jar;E:\Inventory\jmatharray.jar;E:\Inventory\Javax Media.zip;E:\Inventory\jai-core-1.1.3-alpha.jar;C:\Program Files (x86)\JetBrains\IntelliJ IDEA Community Edition 10.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain phoebe.test.ImageTest
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at scala.collection.Iterator$class.toStream(Iterator.scala:1011)
    at scala.collection.IndexedSeqLike$Elements.toStream(IndexedSeqLike.scala:52)
    at scala.collection.Iterator$$anonfun$toStream$1.apply(Iterator.scala:1011)
    at scala.collection.Iterator$$anonfun$toStream$1.apply(Iterator.scala:1011)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$flatten1$1$1.apply(Stream.scala:453)
    at scala.collection.immutable.Stream$$anonfun$flatten1$1$1.apply(Stream.scala:453)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream.length(Stream.scala:113)
    at scala.collection.SeqLike$class.size(SeqLike.scala:221)
    at scala.collection.immutable.Stream.size(Stream.scala:48)
    at scala.collection.TraversableOnce$class.toArray(TraversableOnce.scala:388)
    at scala.collection.immutable.Stream.toArray(Stream.scala:48)
    at phoebe.picasso.Image.force(Image.scala:85)
    at phoebe.picasso.SimpleImageViewer.<init>(SimpleImageViewer.scala:10)
    at phoebe.picasso.Image.display(Image.scala:91)
    at phoebe.test.ImageTest$.main(ImageTest.scala:14)
    at phoebe.test.ImageTest.main(ImageTest.scala)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:115)

Process finished with exit code 1

Answer 1

Если я правильно понял, вы храните каждый отдельный пиксель в одном элементе Stream, и это может быть неэффективно.Что вы можете сделать, это создать свой собственный класс LazyRaster, который содержит ленивые ссылки на блоки изображения некоторого размера (например, 20x20).Когда первый блок записывается, соответствующий ему массив инициализируется, и с этого момента изменение пикселя означает запись в этот массив.

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

Еще одна вещь, которую можно сделать, - убедиться, что старые Stream * правильно собраны в мусор .Я подозреваю, что объект image в вашем примере является оберткой для ваших потоков.Если вы хотите объединить несколько операций с изображениями (например, отображение) и иметь возможность собирать ссылки, которые вам больше не нужны, вы должны убедиться, что у вас нет ссылок на поток - обратите внимание, что это не гарантируется, если:

1. у вас есть ссылка на ваше изображение в стеке (image в примере)
2. ваша Image оболочка содержит такую ​​ссылку.

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

Лично я бы вообще избежал Stream s и просто использовал бы некоторую неизменную структуру данных на основе массива, которая одновременно экономит пространствои избегает бокса.Единственное место, где я потенциально вижу использование Stream, - это итеративные преобразования изображений, такие как свертка или применение стека фильтров.У вас не будет Stream пикселей, а Stream изображений.Это может быть хорошим способом выразить последовательность преобразований - в этом случае применяются комментарии к gc в приведенной выше ссылке.

Answer 2

Если вы обрабатываете большие потоки, вам следует избегать ссылки на начало потока.Это предотвратит сборку мусора.

Возможно, что вызов определенных методов на Stream будет внутренне удерживать голову.Смотрите обсуждение здесь: Функциональная обработка потоков Scala без ошибок OutOfMemory

Answer 3

Stream вряд ли будет оптимальной структурой здесь.Учитывая природу JPEG, не имеет смысла «построчно» передавать его в память.

Поток также имеет линейное время доступа для чтения элементов.Опять же, возможно, это не то, что вам нужно, если вы не передаете данные.

Я бы порекомендовал использовать IndexedSeq[IndexedSeq[Int]] в этом сценарии.Или (если важна производительность) Array[Array[Int]], что позволит вам избежать некоторых затрат на упаковку / распаковку.

Мартин написал хороший обзор API 2.8 коллекций что должно помочь вам понять присущие им компромиссы в различных доступных типах коллекций.

Даже при использовании массивов все же есть все основания использовать их в качестве неизменных структур и поддерживать стиль функционального программирования.Тот факт, что структура изменчива, не означает, что у вас есть для ее изменения!

Answer 4

Я рекомендую также смотреть непрерывный , а не просто дискретные модели для изображений.Непрерывный, как правило, более модульный / составной, чем дискретный - будь то время или пространство.

Answer 5

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

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

ОБНОВЛЕНИЕ : Выше я имею в виду не использовать вложенный массив или IndexedSeq, а выделить блок и вычислить, какой элемент, используя значения строки и столбца.

Затем выберите подход «неизменный после инициализации». Однажды данное пиксель или образец был установлен в растре, вы никогда не позволите быть измененным. Это может потребовать однобитовой растровой плоскости для отслеживания установленные пиксели. Кроме того, если вы знаете, как вы будете заполнять растр (последовательность, в которой будут назначаться пиксели) вы можете получить с гораздо более простым и дешевым представлением того, сколько из Растр установлен и сколько осталось заполнить.

Затем, когда вы выполняете обработку растровых изображений, делайте это в конвейере. где ни одно изображение не изменяется на месте, а новое изображение всегда генерируется при применении различных преобразований.

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

Answer 6

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

Существует специальная опция командной строки, чтобы заставить JVM создавать дамп в OOME: -XX: + HeapDumpOnOutOfMemoryError. И хорошие инструменты, такие как jhat и VisualVM , которые могут помочь вам в анализе.

Answer 7

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

Answer 8

Чтобы увеличить размер кучи с помощью intellij, необходимо добавить следующее в раздел «Параметры виртуальной машины» в конфигурации «Run / Debug»:

-Xms256m -Xmx256m

Это увеличит максимальный размер кучи до 256 МБ, а также обеспечит, чтобы виртуальная машина запрашивала этот объем при запуске, что обычно представляет увеличение производительности.

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

Теперь, с точки зрения алгоритмов, я бы посоветовал вам следовать приведенному выше совету и разделить изображение на, скажем, блоки 9x9 (хотя любой размер подойдет). Затем я бы посмотрел на застежку-молнию Хуэта и подумал, как это можно применить к изображению, представленному в виде древовидной структуры, и как это может позволить вам смоделировать изображение как постоянную структуру данных. .

Answer 9

Одним из решений было бы поместить изображение в массив и сделать фильтры типа «карта», возвращающие оболочку для этого массива. По сути, у вас есть черта с именем Image. Эта черта требует операций извлечения абстрактных пикселей. Когда, например, вызывается функция map, вы возвращаете реализацию, которая делегирует вызовы старому Image и выполняет функцию на нем. Единственная проблема заключается в том, что преобразование может выполняться несколько раз, но поскольку это функциональная библиотека, это не очень важно.

Answer 10

Увеличение размера кучи в идее можно сделать в файле vmoptions, который находится в каталоге bin в каталоге установки вашей идеи (например, добавьте -Xmx512m, чтобы установить размер кучи равным 512 мегабайт).Кроме того, трудно сказать, что вызывает нехватку памяти, не зная, какие именно операции вы выполняете, но, возможно, этот вопрос дает несколько полезных советов.