对于数百万像素的2D未装箱像素数组,推荐使用哪种Haskell表示法?

119

我希望在Haskell中解决一些图像处理问题。 我使用百万像素的双色(位图)和彩色图像。我有一些问题:

  1. 选择Vector.UnboxedUArray之间应该根据什么依据? 它们都是未装箱数组,但Vector抽象似乎被大力推广,特别是在循环融合方面。 Vector总是更好吗? 如果不是,那么何时使用哪种表示?

  2. 对于彩色图像,我希望存储16位整数或单精度浮点数的三元组。 为此,VectorUArray哪个更易于使用? 更高效吗?

  3. 对于双色图像,我需要每个像素只存储1个位。 是否有预定义的数据类型可以通过将多个像素打包成一个字来帮助我,还是我自己动手?

  4. 最后,我的数组是二维的。 我想我可以处理由“数组的数组”(或向量的向量)表示所强加的额外间接性,但我更喜欢具有索引映射支持的抽象。 有没有人可以从标准库或Hackage中推荐任何东西?

我是一个函数式程序员,不需要变异:-)


2
我认为只有Repa符合第4点要求,请参见http://www.cse.unsw.edu.au/~chak/papers/repa.pdf。 - stephen tetley
5
标准的 Array 接口支持多维数组。你可以简单地使用一个元组作为索引。 - John L
14
这个问题被高度点赞和收藏(包括我自己)似乎表明,Haskell对于数组的处理文档不是很充分。 - Alexandre C.
2
@Alexandre C.:处理基本的日常数组已经有很好的文档记录;处理大块持有可变数据的内存与在C语言中一样简单;然而,如何尽可能高效地处理大型不可变多维数组则不太明显。这是关于性能调优的场景,其中微妙且文档记录较少的细节在任何语言中都会成为问题。 - C. A. McCann
1
@Alexandre C.:对于大多数应用程序来说,这是无缝的。问题并不在于 Haskell 本身,而在于库和编译器。一个由 Int 元组索引的普通 UArray 很容易使用,通常也足够好,但即使 GHC 的深度魔法也无法将使用其最小 API 的代码优化为与针对快速并行批量数据处理进行调整的库相竞争的东西。 - C. A. McCann
显示剩余3条评论
4个回答

89

对于多维数组,在我看来,Haskell目前最好的选择是repa

Repa提供高性能、规则的、多维的、形状多态的并行数组。所有数值数据都以非装箱方式存储。使用Repa组合器编写的函数在提供+RTS -Nwhatever命令行参数运行程序时会自动并行化。

最近它已经被用于一些图像处理问题:

我已经开始写有关repa使用的教程,如果你已经了解Haskell数组或向量库,这是一个很好的起点。关键的过渡是使用形状类型而不是简单的索引类型来处理多维索引(甚至是stencils)。

repa-io包包括支持读写.bmp图像文件的功能,尽管需要支持更多格式。

针对你具体的问题,这里有一张图表和讨论:


All three of UArray, Vector, and Repa support unboxing. Vector and Repa have a rich, flexible API, but UArray does not. UArray and Repa have multi-dimensional indexing, but Vector does not. They all have support for bit-packing, although Vector and Repa have some caveats in that regard. Vector and Repa interoperate with C data and code, but UArray does not. Only Repa supports stencils.


我应该根据什么基础来选择Vector.Unboxed和UArray?

它们具有大致相同的底层表示,然而,主要区别在于与向量一起使用的API的广度:它们几乎拥有您通常与列表相关的所有操作(具有融合驱动的优化框架),而 UArray 几乎没有API。

对于彩色图像,我希望存储16位整数或单精度浮点数的三元组。

UArray 对于多维数据具有更好的支持,因为它可以使用任意数据类型进行索引。虽然这在 Vector 中也是可能的(通过编写您的元素类型的 UA 实例),但这不是 Vector 的主要目标——相反,这就是 Repa 介入的地方,使得非常容易使用以有效方式存储的自定义数据类型,感谢形状索引。

Repa 中,您的三个shorts将具有以下类型:

Array DIM3 Word16

即,一个由Word16的3D数组。
对于二值图像,我只需要每个像素存储1位。
UArrays将布尔值打包为位,Vector使用Bool实例进行位打包,而不是使用基于Word8的表示。但是,很容易为向量编写位打包实现——这里有一个,来自(已过时的)uvector库。在底层,Repa使用Vectors,因此我认为它继承了那些库的表示选择。
这里是否有预定义的数据类型可以通过将多个像素打包到一个字中来帮助我?
您可以使用任何库的现有实例,用于不同的字类型,但您可能需要编写一些使用Data.Bits来滚动和展开打包数据的辅助程序。
最后,我的数组是二维的。
UArray和Repa支持高效的多维数组。Repa还具有丰富的接口来实现此目的。Vector本身则没有。

值得一提的是:

  • hmatrix,一个自定义的数组类型,具有广泛的线性代数包绑定。 应该绑定使用vectorrepa类型。
  • ix-shapeable,从常规数组获取更灵活的索引
  • chalkboard,Andy Gill的用于操作2D图像的库
  • codec-image-devil,将各种图像格式读写到UArray中

5
现在,由于**repa-devil**的帮助,您可以以多种格式进行三维repa数组的图像IO。 - Don Stewart
2
请问Repa如何与C代码进行互操作?我在Data.Array.Repa中没有找到Storable实例... - sastanin
2
将指针复制(Copying to pointers)可能是存储数据最简单的方法,但显然不是长期解决方案。为此,我们需要在底层使用可存储向量(Storable vectors)。 - Don Stewart
1
使用 Repa 和 Repa-Devil 进行图像去饱和度的示例。 - Don Stewart

17

我曾经回顾过与我相关的Haskell数组库的特点,并编制了比较表格(只有电子表格:直接链接)。所以我会试着回答。

在什么基础上应该在Vector.Unboxed和UArray之间进行选择?它们都是非装箱数组,但Vector抽象似乎在循环融合方面广泛宣传。Vector总是更好吗?如果不是,那么应该在什么情况下使用哪种表示?

如果需要二维或多维数组,则可以优先选择UArray。但是,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没有太多经验,也不太了解repa代码。从我所看到的来看,它具有非常有限的现成矩阵和数组算法,但至少可以通过该库的手段表达重要的算法。例如,在repa-algorithms中已经有了矩阵乘法和卷积例程。不幸的是,似乎卷积现在仅限于7×7内核(对我来说不够,但对许多用途应该足够)。

我没有尝试过Haskell OpenCV绑定。它们应该很快,因为OpenCV真的很快,但我不确定绑定是否完整且好用。此外,由于OpenCV本质上是非常命令式的,充满了破坏性更新,所以我认为很难在其上面设计一个漂亮而有效的函数接口。如果一个人选择使用OpenCV,他可能会在任何地方都使用OpenCV图像表示,并使用OpenCV例程来操作它们。

对于二值图像,我只需要存储每个像素的1位。是否有预定义的数据类型可以通过将多个像素打包到一个字中来帮助我,还是我需要自己处理?

据我所知,未打包的布尔数组 负责打包和解包位向量。我记得在其他库的布尔数组实现中看到过这个功能。

最后,我的数组是二维的。我想我可以处理由“数组的数组”(或向量的向量)表示所施加的额外间接性,但我更喜欢具有索引映射支持的抽象。有人能推荐标准库或 Hackage 中的任何内容吗?

除了 Vector(和简单列表)之外,所有其他数组库都能够表示二维数组或矩阵。我想它们避免了不必要的间接性。

下面提到的opencv绑定是不完整的。对于一个人来说,创建和维护这样一个庞大库的完整集合确实是不可能的。但是,即使您不得不自己构建所需功能的包装器,使用opencv仍然是成本效益高的,因为它实现了一些非常复杂的东西。 - aleator
@aleator 是的,我明白这对一个人来说是非常庞大的工作量。顺便问一下,如果你是维护者的话,能否请你将haddock文档发布到某个地方,以便在不安装本地库的情况下评估库和绑定的覆盖范围?(由于构建错误,文档在Hackage上不可用;而且它在我使用GHC 6.12.1或GHC 7.0.2时都无法构建,因为M_PI未声明)。 - sastanin
@jextee 嘿,谢谢你的提示!我已经上传了一个新版本,可能修复了这两个问题中的一个。 - aleator
@aleator 谢谢,现在它可以干净地构建了。 - sastanin

5
尽管这并没有确切回答你的问题,也不完全属于Haskell,但我建议看一下Hackage上的CVCV-combinators库。它们绑定了许多非常有用的图像处理和视觉运算符,可以使机器视觉问题的处理更加快速。

如果有人能找出如何直接将repa或类似的数组库与opencv配合使用,那将非常棒。


0

这里有一个新的Haskell图像处理库,可以处理所有相关任务以及更多。目前它使用RepaVector包作为底层表示,因此继承了融合、并行计算、变异和大部分其他与这些库一起使用的好处。它提供了一个易于使用的界面,非常适合图像操作:

  • 支持任意精度的2D索引和非装箱像素(DoubleFloatWord16等)
  • 所有基本函数,如mapfoldzipWithtraverse
  • 支持各种颜色空间:RGB、HSI、灰度、双色调、复杂等
  • 常见图像处理功能:
    • 二值形态学
    • 卷积
    • 插值
    • 傅里叶变换
    • 直方图绘制
    • 等等
  • 能够将像素和图像视为常规数字。
  • 通过JuicyPixels库读写常见图像格式

最重要的是,它是一个纯Haskell库,因此不依赖于任何外部程序。它也具有高度可扩展性,可以引入新的颜色空间和图像表示。

它没有做的一件事情是将多个二进制像素打包在一个Word中,而是每个二进制像素都使用一个Word,也许在未来会改变...


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接