对于具有数百万像素的2D无盒装像素阵列,建议使用什么Haskell表示？

Question

我想解决Haskell中的一些图像处理问题.我正在使用数百万像素的双色调(位图)和彩色图像.我有很多问题:

1. 我应该在什么基础上选择Vector.Unboxed和UArray？它们都是未装箱的阵列,但Vector抽象似乎大量宣传,尤其是循环融合.是Vector总是更好？如果没有,我何时应该使用哪种表示？

2. 对于彩色图像,我希望存储16位整数的三元组或单精度浮点数的三元组.为此目的,是Vector或者UArray更容易使用？性能更高？

3. 对于双色调图像,我需要每像素仅存储1位.是否有预定义的数据类型可以通过将多个像素打包成一个单词来帮助我,或者我是靠自己？

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

我是一名功能程序员,不需要变异:-)

Answer 1

对于多维数组,在我看来,Haskell中当前最好的选项是修复.

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的3D数组.

对于双色调图像,我需要每像素仅存储1位.

UArrays将Bools打包为位,Vector使用Bool实例进行位打包,而不是使用基于的表示Word8.但是,很容易为向量编写一个位打包实现 - 这里有一个来自(过时的)uvector库.在引擎盖下,Repa使用Vectors,所以我认为它继承了库表示选择.

是否有预定义的数据类型可以通过将多个像素打包成一个单词来帮助我

您可以将任何库的现有实例用于不同的单词类型,但是您可能需要使用Data.Bits编写一些帮助程序来滚动和展开打包数据.

最后,我的数组是二维的

UArray和Repa支持高效的多维数组.Repa还有一个丰富的界面.矢量本身没有.

值得注意的是:

• hmatrix,一种自定义数组类型,具有与线性代数包的广泛绑定.应该是必然使用的vector或repa类型.
• ix-shapeable,从常规数组获得更灵活的索引
• 黑板,Andy Gill用于操纵2D图像的库
• codec-image-devil,读取和写入各种图像格式到UArray

Answer 2

一旦我回顾了对我来说很重要的Haskell数组库的功能,并编译了一个比较表(只有电子表格:直接链接).所以我会尽力回答.

我应该在什么基础上选择Vector.Unboxed和UArray？它们都是未装箱的阵列,但Vector抽象似乎大量宣传,尤其是循环融合.Vector总是更好吗？如果没有,我何时应该使用哪种表示？

如果需要二维或多维数组,则UArray可能优于Vector.但Vector有更好的API来操作,好吧,矢量.通常,Vector不适合模拟多维数组.

Vector.Unboxed不能与并行策略一起使用.我怀疑UArray也不能使用,但至少很容易从UArray切换到盒装数组,看看并行化是否有利于拳击成本.

对于彩色图像,我希望存储16位整数的三元组或单精度浮点数的三元组.为此,Vector或UArray更容易使用吗？性能更高？

我尝试使用Arrays来表示图像(尽管我只需要灰度图像).对于彩色图像,我使用Codec-Image-DevIL库来读取/写入图像(绑定到DevIL库),对于灰度图像,我使用了pgm库(纯Haskell).

我对Array的主要问题是它只提供随机访问存储,但它没有提供很多构建数组算法的方法,也没有随时可以使用数组例程库(不与线性代数库接口,不不允许表达卷积,fft和其他变换.

几乎每次必须从现有阵列构建新阵列时,都必须构建一个中间值列表(如在Gentle Introduction 中的矩阵乘法中).阵列构建的成本通常超过了更快随机访问的好处,在某些用例中基于列表的表示更快.

STUArray可以帮助我,但我不喜欢与使用STUArray编写多态代码所需的神秘类型错误和努力作斗争.

所以Arrays的问题在于它们不适合数值计算.Hmatrix的Data.Packed.Vector和Data.Packed.Matrix在这方面更好,因为它们带有一个实体矩阵库(注意:GPL许可证).性能方面,在矩阵乘法上,hmatrix足够快(仅比Octave略慢),但是内存非常大(比Python/SciPy消耗的数倍).

矩阵也有blas库,但它不是建立在GHC7上的.

我还没有很多关于修复的经验,而且我不太了解修复代码.从我所看到的,它具有非常有限的随时可用的矩阵和阵列算法,但至少可以通过库来表达重要的算法.例如,已经存在用于矩阵乘法和修复算法中的卷积的例程.不幸的是,似乎卷积现在仅限于7×7内核(这对我来说还不够,但应该足以满足许多用途).

我没有尝试Haskell OpenCV绑定.它们应该很快,因为OpenCV真的很快,但我不确定绑定是否完整且足够好以至于可用.此外,OpenCV本质上是非常必要的,充满了破坏性的更新.我想很难在它上面设计一个漂亮而有效的功能界面.如果采用OpenCV方式,他可能会在任何地方使用OpenCV图像表示,并使用OpenCV例程来操作它们.

对于双色调图像,我需要每像素仅存储1位.是否有预定义的数据类型可以通过将多个像素打包成一个单词来帮助我,或者我是靠自己？

据我所知,Bobox的Unboxed数组负责打包和解包位向量.我记得在其他库中查看Bool数组的实现,并没有在其他地方看到这一点.

最后,我的数组是二维的.我想我可以处理由表示强加的额外间接作为"数组数组"(或向量向量),但我更喜欢具有索引映射支持的抽象.任何人都可以从标准库或Hackage推荐任何东西吗？

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

Answer 3

虽然,这并没有完全回答你的问题,并且实际上并不是像这样的问题,但我建议你看一下hackage 上的CV或CV-combinators库.它们将opencv库中许多相当有用的图像处理和视觉操作符绑定在一起,使得机器视觉问题的处理速度更快.

如果有人弄清楚如何使用opencv直接使用repa或某些这样的数组库,那将是相当不错的.