在C/C++中快速显示波形

Question

在C/C++中快速显示波形

9

我希望在Windows和Linux上用C或C ++实现音频编辑器。我无法在完全缩放的视图中快速显示波形。我不需要关于快速帧缓冲技术的信息。这是一个关于算法和数据结构的问题，以有效地确定要显示什么。

比如说，我想编辑一段长达2小时的5声道、48 KHz、24位声音。这是5 GB的样本数据。我希望能够从每个样本一个像素的缩放级别一直缩放到所有样本数据一次性可见。我希望应用程序感觉灵敏，即使在慢机器上，例如1 GHz Atom。当我说“灵敏”，我希望GUI更新通常在用户输入后的1/30秒内发生。

一种天真的实现方式是在决定完全缩小视图时扫描整个波形中的每个样本 - 它需要找到显示器每个像素宽度“覆盖”的所有样本的最大和最小样本值。我编写了一个简单的应用程序来测试这种方法的速度。我在我的2015年3.5 GHz Xeon上使用了一小时长的单声道、16位、44.1 KHz样本进行测试。它需要0.12秒。这太慢了数百倍。

您可以想象维护缩放数据的缓存，但我看不出如何避免在大多数插入或删除后必须重新计算整个缓存。感觉必须有更好的方法。

下面是一个显示我想要实现的内容的图表：

这是大多数当前可用音频编辑器中显示的方式。用户很可能期望这种行为。我使用Audacity进行了测试，并且它也是这样工作的（尽管还会以浅色显示样本的平均值之类的内容）。它可以即时处理大型声音的任意插入。我不会阅读75兆字节的源代码来找出它是如何做到的。

编辑：有人建议采用仅考虑缩小视图中的样本子集的方案。我得出结论，我不想这样做，因为这会损失太多有用的信息。例如，如果您正在查找声音中的故障（例如黑胶唱片转换中的单击），包括所有样本非常重要。在最坏的情况下，如果故障只有一个样本长，我仍然希望保证在完全缩小的视图中显示它。

- Andrew Bainbridge

2

降采样！降采样！在旧机器上，1/30秒是一个梦想，但您可以使用更好的硬件获得良好的结果。此外，请记住，图形和IO将是缓慢的部分，除非您十分小心。未经压缩的波形可以搜索以每n个样本读取1个样本（不精确但响应快），然后在后台读取并进行降采样。在完成其他所有事项之后进行缓存，并接受您将无法获得所需的性能。这不是一个算法或一个数据结构，而是一堆技术来给出那种印象。 - Adriano Repetti

什么是下采样？从术语中我理解，如果我对一个20 KHz的方波进行下采样，我会得到一个直流信号。而显示器应该仍然显示完整幅度的信号。我可以看出，读取每n个样本中的1以获得不准确但响应灵敏的显示是我最初问题的可能答案。顺便说一句，我已经可以快速将数据绘制到屏幕上。我只需将所有线条绘制到RAM位图中，然后将整个位图传输到屏幕上。 - Andrew Bainbridge

1

有关这些踩的解释吗？ - Andrew Bainbridge

1

你是如何更新GUI界面的？你使用的GUI框架是什么？ - Thomas Matthews

@andrew 肯定要使用双缓冲，并在单独的线程中进行绘制，以避免与读取和处理发生冲突。降采样是为了减少信号采样率。最小化算法可以得到最优结果，但为了给人一种响应迅速的印象，您可以跳过一些采样。然后按块处理，这将减少延迟（第一个三分之一用X，第二个三分之一用x*2，依此类推）。每个通道可以使用一个线程进行处理。最后，使用快速的绘图代码（在Windows上使用Direct 2D）来提高绘图速度。 - Adriano Repetti

显示剩余7条评论

3个回答

2

当缩放到每像素多个样本时，精确计算每个像素的平均样本值并没有意义。用户无法在这个缩放级别上精确定位GUI工具，因此没有什么好处。用户只需要一个定性的视图。

我会为窗口区域选择每个屏幕像素一个样本，并跳过不必要的样本。

类似于这个完全没有经过测试的代码：

std::vector<double> samples(1024*1024); // [-1.0 < s < 1.0]

int window_x = 1024; // window size in pixels
int window_y = 768; // window size in pixels

// visit every window pixel
for(int x = 0; x < window_x; ++x)
{
    // select relevant sample for the current screen pixel x
    double s = samples[(x * samples.size()) / window_x];

    int y = (window_y / 2) * s; // get y size for sample value

    // draw sample point/line at coordinate (x, f(y))
    gd.draw_line(x, (window_y / 2) - y, x, (window_y / 2) + y);
}

很显然，你还需要考虑窗口滚动等因素...

- Galik

我认为这与Adriano在我的问题评论中所说的类似。这绝对有一定的价值。使用您的方案，我担心当声音是正弦波且频率为samples.size() / window_x时会出现病态情况。然后，循环的每次迭代都将获得相同的s值。我认为Adriano建议通过考虑更多像素每个样本作为后台进程逐渐改善此近似值。 - Andrew Bainbridge

@AndrewBainbridge 嗯，发电机产生的纯正弦波在考虑相邻样本时可能也会继续表现出相同的效应，因为每种情况下它们都是相同的。所以它们将平均相同。至少在我选择用垂直线显示波形的方式中，显示将在您的情况下继续正确。但是，它可能无法表示非常低的频率。我想你可以引入随机抖动来精确地选择从其邻居中选择哪个样本？或者迭代屏幕像素位置的变量的进展？ - Galik

@AndrewBainbridge 是的，我会选择这样的方法进行第一次尝试（但不要在内存中执行 - 这几乎是无用的 - 甚至不要从磁盘读取不需要的样本！）它在人工信号下看起来好吗？当然不是，但对于真实信号来说已经足够好了... 然后在后台使用所有样本进行适当的抽取（最小化）。如果感知速度不够快，您可以分块进行抽取以保持界面响应。这是我几乎总是在声音编辑程序中看到的效果。 - Adriano Repetti

当然，你可以做得更好（也可以处理正弦波），但这将变得更加复杂，因为你必须优化你的I/O、缓存，并尽可能地异步执行（再次给出“瞬间完成”的印象）。 - Adriano Repetti

@AndrewBainbridge RAM中的5 GB？您可以在RAM中保留一个相对低分辨率版本（用于概览和2倍放大），但超过这个大小会使用太多资源，而且应该分块进行处理/降采样。如果有这个“问题”的简单代码，我很乐意看到，并会密切关注此事。 - Adriano Repetti

显示剩余2条评论

2

也许你可以使用来自图形学的mip-mapping技术，用更多的内存换取更快的速度？如果您有32个样本，请维护一个缓存，其中包括x2、x4、x8等缩小的缩略图。存储这些数据将再次占用与原始数据相同的空间（16 + 8 + 4 + 2 + 1个样本）。以下是一个可视化指南，其中“.”表示存储的数据点（最小/最大样本值），而“_”表示前一个“.”所覆盖的样本：

1st level: ................
2nd level: ._._._._._._._._
3rd level: .___.___.___.___
4th level: ._______._______
5th level: ._______________

然后只需查询适合缩放级别的相应级别 mip-map。

是的，当您插入/删除样本时，您将不得不重新创建 mip-map 缓存（或其一部分）。

但也许内存使用使这对您不合适？

编辑

如果添加和删除是频繁的操作，并且使重新计算缓存不可取（并且您想要准确地在间隔上进行下采样而不仅仅是在单个点上），那么您可以更改 mip-mapping 方法以将数据存储对齐到本地最小/最大样本点而不是基于时间的网格。

使用 --------|-------- 来表示区间内的本地最小/最大值，以下是图示：

                             --------|--------
   --------|--------
                   --------|--------
                                     --------|--
------|--------
                                     .
           .                        . .
.     .   . .   .          .       .   .     .
 . ... . .   . . .   . .. . .     .     .   . .
  .     .     .   . . .  .   .   .       . .   .
                   .          . .         .
                               .
--------|--------
           --------|--------
                                  --------|-----
                       --------|--------

然后添加和删除只需要重新计算添加/删除部分的起始和结束位置的即时局部区域。

您可能希望索引本地最小/最大值，这样您就不需要进行大量搜索。这是一种更复杂的实现方案 - 也许对您来说不值得？

- Peter Stock

是的，我一直在考虑这些方面。考虑到每帧扫描每个样本只需要几百倍的速度，我倾向于仅使用一个mip-map级别。其中数组中的一个项目表示类似于2^15个样本的东西（因为我预计需要支持的最大声音将约为2^30个样本）。这种方案的内存使用量很小。我的问题是，是否有任何方法可以避免在每次插入/删除后重新计算整个mip-map。我可以想到一些方法，使您只需要平均重新计算1/4，但对我来说仍然不太好。 - Andrew Bainbridge

你修改后的解决方案看起来差不多正确。我不太明白你是如何确定每个“局部最大值”搜索的范围起点和终点的。我发布了一个类似于你的答案，但是“局部最大值”是在每个固定的1024个样本范围内计算的，对齐于1024个样本边界。这听起来合理吗？还是我漏掉了什么技巧？ - Andrew Bainbridge

我只是在推测，实际上我没有做过这个，所以我没有更多的建议！是的，有一些细节需要填充：是否要有固定长度的“本地最大”区域？是否允许它们重叠？在我的例子中，我将它们居中于本地最大样本上，尽管看着最右边的最大值，它实际上不是最大样本-只是不被“本地最大”值覆盖的最大样本。我会从未被覆盖的最大样本开始分配它们，并继续进行，直到所有样本都被本地最大值所覆盖。 - Peter Stock

我刚刚做了一些计算。如果你在每个mip-map“步骤”中将分辨率减半，你将需要大约98%的额外内存。然而，如果你将分辨率除以4，额外的内存成本会急剧下降，只有约39%。进一步地，将分辨率除以8将产生约14%的额外内存成本。因此，在这种情况下，你可以尝试不同的分辨率，因为内存效率是可扩展的。即使在JavaScript中（虽然在我的情况下使用了很多GPU加速涂层），我也能得到可靠的60 fps可视化效果。 - John Weisz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andrew Bainbridge · Accepted Answer

阅读了Peter Stock的答案后，我想出了以下方案。我认为它将允许显示计算比朴素方案快约500倍，并且不应该增加任何明显的插入或删除成本。内存开销小于1％。

声音数据将分配在131072个样本的块中，以便插入和删除不需要重新分配和复制整个声音。当首次加载声音时，每个块将完全填充（除了可能是最后一个块）。插入和删除将导致一种碎片化。为简单起见，我将安排每个块的开始始终包含有效的样本数据，任何间隙都在块的末尾。

每个块都有两个与之关联的查找表，一个用于最大值，另一个用于最小值。查找表中的每个项目对应于1024个样本。

下面的图示说明了如何计算显示器一个像素宽度的最大值。它显示了与计算相关的几个块。假设没有“碎片化”。

在插入操作之后，情况稍微复杂一些。现在有两个块的末尾都有无效区域。最大查找表中存在对应于部分空白样本区域的条目。这些条目的值是通过仅考虑存在的样本的最大值来确定的。