用 Scala 编写一个实用且实用的图像处理库
我们正在为 Scala 开发一个小型图像处理库（学生项目）。该库功能齐全（即没有可变性）。图像的栅格存储为 Stream[Stream[Int]]，以便以最少的努力利用惰性求值的优势。然而，在对图像执行一些操作后，堆会变满，并引发 OutOfMemoryError 。 （例如，在 JVM 堆空间耗尽之前，可以对大小为 500 x 400、35 kb 的 jpeg 图像执行最多 4 次操作。）
我们想到的方法是：
- 调整 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
We are developing a small image processing library for Scala (student project). The library is completely functional (i.e. no mutability). The raster of image is stored as Stream[Stream[Int]] to exploit the benefits of lazy evaluation with least efforts. However upon performing a few operations on an image the heap gets full and an OutOfMemoryError is thrown. (for example, up to 4 operations can be performed on a jpeg image sized 500 x 400, 35 kb before JVM heap runs out of space.)
The approaches we have thought of are:
- Twiddling with JVM options and increase the heap size. (We don't know how to do this under IDEA - the IDE we are working with.)
- Choosing a different data structure than
Stream[Stream[Int]], the one which is more suited to the task of image processing. (Again we do not have much idea about the functional data structures beyond the simpleListandStream.)
The last option we have is giving up on immutability and making it a mutable library (like the popular image processing libraries), which we don't really want to do. Please suggest us some way to keep this library functional and still functional, if you know what I mean.
Thank you,
Siddharth Raina.
ADDENDUM:
For an image sized 1024 x 768, the JVM runs out of heap space even for a single mapping operation. Some example code from our test:
val image = Image from "E:/metallica.jpg"
val redded = image.map(_ & 0xff0000)
redded.display(title = "Redded")
And the output:
"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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
如果我理解正确的话，您将每个单独的像素存储在一个
Stream元素中，这可能效率很低。您可以做的是创建自定义LazyRaster类，其中包含对某些大小（例如 20x20）图像块的延迟引用。第一次写入某个块时，会初始化其相应的数组，从那时起更改像素意味着写入该数组。这是更多的工作，但可能会带来更好的性能。此外，如果您希望支持图像操作的堆叠（例如，进行映射 - 获取 - 映射），然后“一次性”评估图像，则实现可能会变得棘手 - 流实现是最好的证据。
人们可以做的另一件事是确保旧的 Stream 正在 已正确收集垃圾。我怀疑您的示例中的
image对象是您的流的包装器。如果您希望将多个图像操作（如映射）堆叠在一起并能够 gc 不再需要的引用，则必须确保不保留对流的任何引用 - 请注意，如果出现以下情况，则无法确保这一点：image），Image包装器包含这样的引用。在不了解更多确切用例的情况下，很难说更多。
就我个人而言，我会完全避免
Stream，而简单地使用一些不可变的基于数组的数据结构，既节省空间又避免装箱。我唯一可能看到 Stream 被使用的地方是迭代图像转换，例如卷积或应用一堆过滤器。您不会拥有像素的Stream，而是图像的Stream。这可能是表达一系列转换的好方法 - 在这种情况下，上面给出的链接中有关 gc 的注释适用。If I understood correctly, you store each individual pixel in one
Streamelement, and this can be inefficient. What you can do is create your customLazyRasterclass which contains lazy references to blocks of the image of some size (for instance, 20x20). The first time some block is written, its corresponding array is initialized, and from there on changing a pixel means writing to that array.This is more work, but may result in better performance. Furthermore, if you wish to support stacking of image operations (e.g. do a map - take - map), and then evaluating the image in "one-go", the implementation could get tricky - stream implementation is the best evidence for this.
Another thing one can do is ensure that the old
Streams are being properly garbage collected. I suspectimageobject in your example is a wrapper for your streams. If you wish to stack multiple image operations (like mapping) together and be able to gc the references you no longer need, you have to make sure that you don't hold any references to a stream - note that this is not ensured if:imagein the example)Imagewrapper contains such a reference.Without knowing more about the exact use cases, its hard to say more.
Personally, I would avoid
Streams altogether, and simply use some immutable array-based data structure which is both space-efficient and avoids boxing. The only place where I potentially seeStreams being used is in iterative image transformations, like convolution or applying a stack of filters. You wouldn't have aStreamof pixels, but aStreamof images, instead. This could be a nice way to express a sequence of transformations - in this case, the comments about gc in the link given above apply.如果处理大型流，则需要避免保留对流头部的引用。这将阻止垃圾收集。
在
Stream上调用某些方法可能会在内部保留头部。请参阅此处的讨论：没有 OutOfMemory 错误的 Scala 流的函数处理If you process large streams, you need to avoid holding onto a reference to the head of the stream. This will prevent garbage collection.
It's possible that calling certain methods on
Streamwill internally hold onto the head. See the discussion here: Functional processing of Scala streams without OutOfMemory errorsStream不太可能是这里的最佳结构。鉴于 JPEG 的性质，将其逐行“流”到内存中没有什么意义。Stream 还具有读取元素的线性访问时间。同样，除非您正在传输数据，否则可能不是您想要的。
我建议在这种情况下使用
IndexedSeq[IndexedSeq[Int]]。或者（如果性能很重要）Array[Array[Int]]，这将使您避免一些装箱/拆箱成本。Martin 编写了对 2.8 集合 API 的良好概述< /a> 这应该可以帮助您理解各种可用集合类型的固有权衡。
即使使用数组，仍然有充分的理由将它们用作不可变结构并保持函数式编程风格。仅仅因为结构是可变的并不意味着您必须改变它！
Streamis very unlikely to be the optimum structure here. Given the nature of a JPEG it makes little sense to "stream" it into memory line-by-line.Stream also has linear access time for reading elements. Again, probably not what you want unless you're streaming data.
I'd recommend using an
IndexedSeq[IndexedSeq[Int]]in this scenario. Or (if performance is important) anArray[Array[Int]], which will allow you to avoid some boxing/unboxing costs.Martin has written a good overview of the 2.8 collections API which should help you understand the inherent trade-offs in the various collection types available.
Even if using Arrays, there's still every reason to use them as immutable structures and maintain a functional programming style. Just because a structure is mutable doesn't mean you have to mutate it!
我建议还考虑连续图像模型，而不仅仅是离散模型。连续通常比离散更模块化/可组合——无论是时间还是空间。
I recommend also looking at continuous rather than just discrete models for imagery. Continuous is generally more modular/composable than discrete--whether time or space.
第一步，您应该进行内存转储并对其进行分析。您很可能会立即看到问题。
有一个特殊的命令行选项可以强制 JVM 在 OOME 上进行转储：-XX:+HeapDumpOnOutOfMemoryError。还有一些好的工具，例如 jhat 和 VisualVM，可以帮助你分析。
As a first step you should take a memory dump and analyze it. It is very possible that you will see the problem immediately.
There is special command line option to force JVM to make dump on OOME: -XX:+HeapDumpOnOutOfMemoryError. And good tools, like jhat and VisualVM, which can help you in analysis.
Stream 更多的是关于惰性评估而不是不变性。而你是
为每个像素强制大量的空间和时间开销
这样做。此外，只有当您可以推迟时间时，Streams 才有意义
确定（计算或检索）各个像素值。
当然，随机访问是不可能的。我不得不认为
流式传输完全不适合图像处理的数据结构。
我强烈建议您管理自己的光栅内存（额外的
不将单个光栅图像组织固定到您的系统中的要点
代码）并为整个通道或平面或频带分配存储空间
其中（取决于正在使用的光栅组织）。
更新：通过上述内容，我的意思是不要使用嵌套数组或 IndexedSeq，而是分配一个块并使用行和列值计算哪个元素。
然后采取“初始化后不可变”的方法。一旦给定
像素或样本已经在栅格中建立，你永远不允许它
被改变。这可能需要一位光栅平面来跟踪
建立的像素。或者，如果您知道如何填充
您可以获得的栅格（像素分配的顺序）
用一种更简单、更便宜的方式来表示有多少
栅格已建立，还有多少需要填充。
然后，当您对光栅图像执行处理时，在管道中执行此操作
没有任何图像被改变，而是总是有一个新图像
随着各种变换的应用而生成。
您可能会考虑对于某些图像转换（卷积，
例如）您必须采用这种方法，否则您将不会得到正确的结果
结果。
Stream is more about lazy evaluation than immutability. And you're
forcing an insane amount of space and time overhead for each pixel by
doing so. Furthermore, Streams only make sense when you can defer the
determination (calculation or retrieval) of individual pixel values.
And, of course, random access is impossible. I'd have to deem the
Stream an entirely inappropriate data structure for image processing.
I'd strongly recommend that you manage your own raster memory (bonus
points for not fixing a single raster image organization into your
code) and allocate storage for whole channels or planes or bands
thereof (depending on the raster organization in play).
UPDATE: By the foregoing, I mean don't use nested Array or IndexedSeq, but allocate a block and compute which element using the row and column values.
Then take an "immutable after initialization" approach. Once a given
pixel or sample has been established in the raster, you never allow it
to be changed. This might require a one-bit raster plane to track the
established pixels. Alternatively, if you know how you'll be filling
the raster (the sequence in which pixels will be assigned) you can get
away with a much simpler and cheaper representation of how much of the
raster is established and how much remains to be filled.
Then as you perform processing on the raster images, do so in a pipeline
where no image is altered in place, but rather a new image is always
generated as various transforms are applied.
You might consider that for some image transformations (convolution,
e.g.) you must take this approach or you will not get the correct
results.
如果您没有任何经验，我强烈推荐 Okasaki 的纯函数式数据结构具有功能数据结构（正如您似乎指出的那样）。
I strongly recommend Okasaki's Purely Functional Data Structures if you don't have any experience with functional data structures (as you seem to indicate).
要使用 intellij 增加堆大小，您需要将以下内容添加到运行/调试配置的 VM 参数部分：
这会将最大堆大小增加到 256MB，并确保 VM 在启动时请求此数量，这通常代表着性能的提升。
此外，您使用的是相对较旧的 JDK。如果可能，我建议您更新到最新的可用版本，因为较新的版本支持逃逸分析，这在某些情况下会对性能产生巨大影响。
现在，就算法而言，我建议您遵循上面的建议，将图像划分为 9x9 的块（不过任何尺寸都可以）。然后我会去看看 Huet 的 Zipper 并思考如何做到这一点可以应用于表示为树结构的图像，以及它如何使您能够将图像建模为持久数据结构。
To increase your heap size using intellij, you need to add the following to the VM Parameters section of the Run/Debug Configuration:
This will increase the maximum heap size to 256MB and also ensure this amount is requested by the VM at startup, which generally represents a performance increase.
Additionally, you're using a relatively old JDK. If possible, I recommend you update to the latest available version, as newer builds enable escape analysis, which can in some cases have a dramatic effect on performance.
Now, in terms of algorithms, I would suggest that you follow the advice above and divide the image into blocks of say, 9x9 (any size will do though). I'd then go and have a look at Huet's Zipper and think about how that might be applied to an image represented as a tree structure, and how that might enable you to model the image as a persistent data structure.
增加idea中的堆大小可以在vmoptions文件中完成，该文件可以在idea安装目录的
bin目录中找到（例如添加-Xmx512m将堆大小设置为512兆字节） 。除此之外，在不知道您到底执行了什么操作的情况下，很难说是什么导致了内存不足，但也许 这个问题提供了一些有用的提示。
Increasing the heap size in idea can be done in the vmoptions file, which can be found in the
bindirectory in your idea installation directory (add -Xmx512m to set the heap size to 512 megabyte, for example).Apart from that, it is hard to say what causes the out of memory without knowing what operations you exactly perform, but perhaps this question provides some useful tips.
一种解决方案是将图像放入数组中，并使“map”等过滤器返回该数组的包装器。基本上，你有一个名为图像的特征。该特征需要抽象的像素检索操作。例如，当调用“map”函数时，您将返回一个实现，它将调用委托给旧图像，并在其上执行该函数。唯一的问题是转换最终可能会被执行多次，但由于它是一个函数库，所以这并不是很重要。
One solution would be to put the image in an array, and make filters like "map" return a wrapper for that array. Basically, you have a trait named Image. That trait requires abstract pixel retrieving operations. When, for example, the "map" function is called, you return an implementation, which delegates the calls to the old Image, and executes the function on it. The only problem with that would be that the transformation could end up being executed multiple times, but since it is a functional library, that is not very important.