对于具有数百万个像素的2D未装箱像素阵列,建议使用哪种Haskell表示形式?
image-processing
7
0

我想解决Haskell中的一些图像处理问题。我正在处理具有数百万像素的双色调(位图)和彩色图像。我有几个问题:

  1. 我应该在什么基础上选择Vector.UnboxedUArray ?它们都是未装箱的数组,但是Vector抽象似乎广为宣传,尤其是在循环融合方面。 Vector总是更好吗?如果没有, 我什么时候应该使用哪种表示形式?

  2. 对于彩色图像,我希望存储三位数的16位整数或三位数的单精度浮点数。为此, VectorUArray更易于使用?表现更好?

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

  4. 最后,我的数组是二维的。我想我可以处理表示形式为“数组数组”(或向量的向量)带来的额外间接,但我更喜欢具有索引映射支持的抽象。谁能推荐标准库或Hackage中的任何内容?

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

参考资料:
Stack Overflow
收藏
评论
共 3 个回答
高赞 时间 活跃

一旦我回顾了对我而言至关重要的Haskell数组库的功能,并编译了一个比较表 (仅电子表格: 直接链接 )。所以我会尽力回答。

我应该在什么基础上选择Vector.Unboxed和UArray?它们都是未装箱的数组,但是Vector抽象似乎广为宣传,尤其是在循环融合方面。 Vector总是更好吗?如果没有,我什么时候应该使用哪种表示形式?

如果需要二维或多维数组,则最好使用UArray而不是Vector。但是Vector有更好的API来处理向量。通常,Vector不太适合模拟多维数组。

Vector.Unboxed不能与并行策略一起使用。我怀疑不能同时使用UArray,但至少很容易从UArray切换到盒装Array,看看并行化是否带来的好处超过了装箱成本。

对于彩色图像,我希望存储三位数的16位整数或三位数的单精度浮点数。为此,Vector或UArray是否更易于使用?表现更好?

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

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

几乎每次必须从现有阵列中构建一个新数组时,都必须构造一个中间值列表 (就像Gentle Introduction中的矩阵乘法一样)。数组构建的成本通常超过了更快的随机访问带来的好处,以至于在我的一些用例中,基于列表的表示更快。

STUArray可以为我提供帮助,但我不喜欢与神秘的类型错误以及使用STUArray编写多态代码所需的工作抗争

因此,数组的问题在于它们不适用于数值计算。在这方面,Hmatrix的Data.Packed.Vector和Data.Packed.Matrix更好,因为它们带有固态矩阵库(注意:GPL许可证)。在性能方面,就矩阵乘法而言,hmatrix足够快( 仅比Octave稍慢 ),但是却非常耗内存(消耗的时间比Python / SciPy多几倍)。

也有用于矩阵的blas库,但它不是基于GHC7建立的。

我对Repa并没有太多的经验,而且我不太了解repa代码。从我的角度来看,它可以使用的矩阵和数组算法的使用范围非常有限,但是至少可以通过该库来表达重要的算法。例如,已经存在用于矩阵乘法和用于 REPA算法中的卷积的例程。不幸的是,似乎卷积现在仅限于7×7内核 (对我来说这还不够,但足以满足许多用途)。

我没有尝试过Haskell OpenCV绑定。它们应该很快,因为OpenCV确实非常快,但是我不确定绑定是否完整并且足够好以致无法使用。而且,OpenCV本质上是非常必要的,充满破坏性的更新。我想很难在其上设计一个美观而有效的功能接口。如果采用OpenCV方式,他很可能会在任何地方使用OpenCV图像表示,并使用OpenCV例程对其进行操作。

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

据我所知, 布尔的非装箱数组负责打包和解包位向量。我记得在其他库中看过布尔数组的实现,在其他地方都没有看到。

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

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

收藏
评论

对于多维数组,我认为Haskell当前的最佳选择是repa

Repa提供高性能,规则,多维,形状多态的并行阵列。所有数字数据均未装箱存储。如果您在运行程序时在命令行上提供+ RTS-无论如何,用Repa组合器编写的功能将自动并行执行。

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

我已经开始编写有关repa用法的教程,如果您已经知道Haskell数组或向量库,那么这是一个很好的起点。关键的垫脚石是使用形状类型而不是简单的索引类型来解决多维索引(甚至是模板)。

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

解决您的具体问题,以下是带有讨论的图形:


UArray,Vector和Repa的全部三个都支持拆箱。 Vector和Repa具有丰富,灵活的API,而UArray没有。 UArray和Repa具有多维索引,但Vector没有。它们都支持位打包,尽管Vector和Repa在这方面有一些警告。 Vector和Repa可与C数据和代码互操作,而UArray则不可以。仅Repa支持模具。


我应该在什么基础上选择Vector.Unboxed和UArray?

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

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

UArray可以更好地支持多维数据,因为它可以使用任意数据类型进行索引。尽管在Vector中可以做到这一点(通过为您的元素类型编写UA实例),但这并不是Vector的主要目标-而是Repa目标,这使得使用存储在其中的自定义数据类型非常容易有效的方式,得益于形状索引。

Repa ,您的三重短裤类型为:

Array DIM3 Word16

也就是说,Word16的3D数组。

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

UArrays将Bools打包为位,Vector使用Bool的实例进行位打包,而不是使用基于Word8的表示。但是,为向量编写位打包实现很容易- 这是 (过时的)uvector库中的一种。在内部, Repa使用Vectors ,因此我认为它继承了库表示形式的选择。

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

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

最后,我的数组是二维的

UArray和Repa支持高效的多维数组。 Repa还具有丰富的界面。向量本身没有。


值得注意的提及:

  • hmatrix ,一种自定义数组类型,具有对线性代数包的广泛绑定。应该绑定使用vectorrepa类型。
  • ix-shapeable ,从常规数组中获得更灵活的索引
  • 黑板 ,安迪·吉尔(Andy Gill)的库,用于处理2D图像
  • codec-image-devil ,将各种图像格式读取和写入UArray
收藏
评论

虽然,这并不能完全回答您的问题,甚至还不是Haskell,但我还是建议您看一下hackage的CVCV-combinators库。它们绑定了来自opencv库的许多相当有用的图像处理和视觉操作员,并使处理机器视觉问题的速度大大提高。

如果有人弄清楚repa或某些此类数组库可以直接与opencv一起使用,那将是相当不错的。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号