2

我正在寻找使用 3x3 过滤器过滤每像素 1 位的图像:对于每个输入像素,如果其周围像素的加权和(由过滤器确定的权重)超过某个阈值,则相应的输出像素设置为 1 .

我希望这比转换为 8 bpp 然后过滤它更有效,但我想不出一个好的方法来做到这一点。一种简单的方法是跟踪指向字节的九个指针(三个连续的行以及指向每行中当前字节任一侧的指针,用于计算这些字节中第一个和最后一个位的输出)和每个输入像素计算

sum = filter[0] * (lastRowPtr & aMask > 0) + filter[1] * (lastRowPtr & bMask > 0) + ... + filter[8] * (nextRowPtr & hMask > 0),

对于字节边缘的位有额外的 faff。但是,这很慢,而且看起来真的很难看。您没有从每个字节中有八个像素的事实中获得任何并行性,而是不得不做大量额外的工作来屏蔽事物。

有没有什么好的资源可以最好地做这种事情?这个特定问题的解决方案将是惊人的,但我很高兴有人指出任何在 C/C++ 中对 1bpp 图像进行高效图像处理的示例。我想在将来用 1 bpp 算法替换更多 8 bpp 的东西,以避免图像转换和复制,因此任何关于此的一般资源将不胜感激。

4

3 回答 3

2

查看可分离的过滤器。除其他外,它们允许在它们工作的情况下进行大规模并行。

例如,在您的 3x3 样本权重和过滤器案例中:

  1. 将1x3(水平)像素采样到缓冲区中。这可以针对每个像素单独完成,因此 1024x1024 图像可以同时运行 1024^2 个任务,所有这些任务都执行 3 个样本。
  2. 从缓冲区中采样 3x1(垂直)像素。同样,这可以同时在每个像素上完成。
  3. 使用缓冲区的内容从原始纹理中剔除像素。

从数学上讲,这种方法的优势在于它将样本操作的数量从n^2减少到2n,尽管它需要与源相同大小的缓冲区(如果您已经在执行复制,则可以将其用作缓冲区;您只是无法修改第 2 步的原始来源)。为了将内存使用保持在2n,您可以一起执行步骤 2 和 3(这有点棘手,并不完全令人愉快);如果内存不是问题,您可以花在3n两个缓冲区(source、hblur、vblur)上。

因为每个操作都在与不可变源完全隔离的情况下工作,所以如果您有足够的内核,您可以同时对每个像素执行过滤器。或者,在更现实的场景中,您可以利用分页和缓存来加载和处理单个列或行。这在处理奇数步幅、行尾填充等时很方便。第二轮样本(垂直)可能会破坏您的缓存,但最糟糕的是,一轮将是缓存友好的,并且您已经将处理从指数切割为线性。

现在,我还没有具体谈到以位存储数据的情况。这确实使事情变得稍微复杂了一点,但并不是非常复杂。假设您可以使用滚动窗口,例如:

d = s[x-1] + s[x] + s[x+1]

作品。有趣的是,如果您在步骤 1 的输出期间将图像旋转 90 度(微不足道,(y,x)读取时的样本),您可以为任何样本加载最多两个水平相邻的字节,并且只加载一个像 75 这样的字节% 的时间。这在读取过程中对缓存的友好程度稍低,但大大简化了算法(足以让它重新获得损失)。

伪代码:

buffer source, dest, vbuf, hbuf;

for_each (y, x)   // Loop over each row, then each column. Generally works better wrt paging
{
    hbuf(x, y) = (source(y, x-1) + source(y, x) + source(y, x+1)) / 3   // swap x and y to spin 90 degrees
}
for_each (y, x)
{
    vbuf(x, 1-y) = (hbuf(y, x-1) + hbuf(y, x) + hbuf(y, x+1)) / 3    // 1-y to reverse the 90 degree spin
}
for_each (y, x)
{
    dest(x, y) = threshold(hbuf(x, y))
}

访问字节内的位(source(x, y)表示访问/样本)相对简单,但在这里写出来有点痛苦,所以留给读者。该原理,特别是以这种方式实现的(使用 90 度旋转),n每次只需要 2 次采样,并且总是从紧邻的位/字节中采样(不需要您计算下一行中位的位置)。总而言之,它比任何替代方案都更快、更简单。

于 2012-06-21T20:39:08.430 回答
2

几年前,我发现将位解包为字节,进行过滤,然后将字节打包回位比直接使用位要快。这似乎违反直觉,因为它是 3 个循环而不是 1 个,但是每个循环的简单性足以弥补它。

我不能保证它仍然是最快的;编译器,尤其是处理器很容易发生变化。然而,简化每个循环不仅使优化更容易,而且更易于阅读。那一定是值得的。

解包到单独缓冲区的另一个优点是它为您在边缘执行的操作提供了灵活性。通过使缓冲区比输入大 2 个字节,您从字节 1 开始解包,然后将字节 0 设置n为您喜欢的任何内容,并且过滤循环根本不必担心边界条件。

于 2012-06-21T20:39:55.473 回答
1

与其将整个图像扩展为 1 位/字节(或 8bpp,本质上,正如您所指出的),您可以简单地扩展当前窗口 - 读取第一行的第一个字节,移位和掩码,然后读出您的三位需要; 对其他两行做同样的事情。然后,对于下一个窗口,您只需丢弃左列并从每一行中再获取一位。做到这一点的逻辑和代码并不像简单地扩展整个图像那么简单,但它会占用更少的内存。

作为中间立场,您可以扩展您当前正在处理的三行。以这种方式编码可能更容易。

于 2012-06-21T20:36:07.033 回答