对一个数字数组进行下采样

Question

我有一系列100个整数值，需要将其减少/子采样为77个值，以适应预定义的屏幕空间。这将给出77/100值每像素的分数 - 不是非常整齐。

假设77是固定的，不能改变，那么将100个数字下采样至77的一些典型技术是什么？我感觉这将是一个参差不齐的映射，也就是说，第一个新值是[0,1]的平均值，然后下一个值是[3]，接着是平均值[4,5]等等。但是我该如何获取此映射模式的方案？

我在使用C++，尽管我更关心的是技术而不是实现。

提前感谢您。

- cdevelop

---

为什么不使用标准的插值技术呢？ - n. m.

我投票关闭此问题，因为它与编程无关。 - Useless

Answer 1

无论是下采样还是过采样，您都在尝试在非采样时间点上重建信号...因此您必须做出一些假设。

采样定理告诉您，如果您采样一个信号，并知道其没有频率分量超过采样频率的一半，则可以连续完全地恢复整个时间段内的信号。有一种使用`sinc()`函数（即`sin(x)/x`）来重构信号的方法。

`sinc()`（确实是`sin(M_PI/Sampling_period*x)/M_PI/x`）是具有以下属性的函数：

1. 当 `x == 0.0` 时，它的值为1，当 `x == k*Sampling_period` 时，它的值为0，其中 `k == 0, +-1, +-2, ...` 2. 它没有超过由`Sampling_period`导出的采样频率的一半的频率分量。

因此，如果您认为函数`F_x(x) = Y[k]*sinc(x/Sampling_period - k)`的总和是等于位置`k`的采样值且在其他采样值处为0的`sinc()`函数，并对样本中的所有k求和，则将获得具有不具有超过采样频率一半的频率分量的最佳连续函数，并具有与样本集相同的值。

这样说，您可以在任何位置重新采样此函数，从而获得重新采样数据的最佳方法。

这绝对是一种复杂的重采样数据的方法（它也有不是因果的问题，因此无法实时实现），过去使用了几种简化插值的方法。您必须为每个采样点构造所有`sinc()`函数并将它们相加。然后，您必须将结果函数重新采样到新的采样点，并将其作为结果给出。

下面是刚才描述的插值方法的示例。它接受一些输入数据（`in_sz`个样本）并使用前面描述的方法输出插值数据（我假设极值相同，这使得`N+1`个样本等于`N+1`个样本，并且这使得代码中的有些复杂计算变得更加复杂（如果要进行普通的`N个样本->M个样本`转换，请将其更改为`in_sz/out_sz`）。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

/* normalized sinc function */
double sinc(double x)
{
    x *= M_PI;
    if (x == 0.0) return 1.0;
    return sin(x)/x;
} /* sinc */

/* interpolate a function made of in samples at point x */
double sinc_approx(double in[], size_t in_sz, double x)
{
    int i;
    double res = 0.0;
    for (i = 0; i < in_sz; i++)
            res += in[i] * sinc(x - i);
    return res;
} /* sinc_approx */

/* do the actual resampling.  Change (in_sz - 1)/(out_sz - 1) if you
 * don't want the initial and final samples coincide, as is done here.
 */
void resample_sinc(
    double in[],
    size_t in_sz,
    double out[],
    size_t out_sz)
{
    int i;
    double dx = (double) (in_sz-1) / (out_sz-1);
    for (i = 0; i < out_sz; i++)
            out[i] = sinc_approx(in, in_sz, i*dx);
}

/* test case */
int main()
{
    double in[] = {
            0.0, 1.0, 0.5, 0.2, 0.1, 0.0,
    };

    const size_t in_sz = sizeof in / sizeof in[0];
    const size_t out_sz = 5;
    double out[out_sz];
    int i;

    for (i = 0; i < in_sz; i++)
            printf("in[%d] = %.6f\n", i, in[i]);
    resample_sinc(in, in_sz, out, out_sz);
    for (i = 0; i < out_sz; i++)
            printf("out[%.6f] = %.6f\n", (double) i * (in_sz-1)/(out_sz-1), out[i]);

    return EXIT_SUCCESS;
} /* main */

- Luis Colorado

---

非常感谢您提供的详细解释，非常有用。 - luca

Answer 2

有不同的插值方法（参见 维基百科）。

线性插值可能是这样的：

std::array<int, 77> sampling(const std::array<int, 100>& a)
{
     std::array<int, 77> res;

     for (int i = 0; i != 76; ++i) {
         int index = i * 99 / 76;
         int p = i * 99 % 76;

         res[i] = ((p * a[index + 1]) + ((76 - p) * a[index])) / 76;
    }
    res[76] = a[99]; // done outside of loop to avoid out of bound access (0 * a[100])
    return res;
}

Live example

- Jarod42

Answer 3

一切都取决于您希望如何使用数据-您想如何可视化它。

一个非常简单的方法是将其渲染为100个宽度的图像，然后平滑缩小图像以适应较窄的尺寸。无论您使用的是什么图形/开发框架，肯定都支持这样的操作。

假设您的目标是保留数据的某些特性，例如最小值和最大值。在这种情况下，对于每个bin，您正在绘制一条较暗颜色的线到达最小值，然后继续用较浅颜色上升到最大值。或者，您可以不仅在平均值处放置一个像素，而是从最小值到最大值绘制一条线。

最后，您可能希望呈现的结果仅有77个值 - 那么目标是以某种方式将100个值转换为77个。这将意味着某种插值。线性或二次插值很容易，但会对信号添加扭曲。理想情况下，您可能希望使用sinc插值器解决问题。可以在这里找到一个好的列表。有关理论背景，请查看这里。

- Kuba hasn't forgotten Monica

Answer 4

基于位置的加权平均值创建77个新像素。

举个玩具例子，想象一下你要将3个像素下采样为2个像素的情况。

原始图像（表示为多维数组original，RGB为[0, 1, 2]）：

|----|----|----|

对数据进行子采样（用RGB表示的多维数组称为subsample）：

|------|------|

在这里，很容易看出第一个子样本看起来像是第一个原始像素的2/3和下一个像素的1/3。

对于第一个子样本像素subsample[0]，您将其设置为重叠的m个原始像素的RGB平均值，此处为original[0]和original[1]。但我们以加权方式进行。

subsample[0][0] = original[0][0] * 2/3 + original[1][0] * 1/3  # for red
subsample[0][1] = original[0][1] * 2/3 + original[1][1] * 1/3  # for green
subsample[0][2] = original[0][2] * 2/3 + original[1][2] * 1/3  # for blue

在这个例子中，original[1][2] 是第二个原始像素的绿色分量。

请记住，对于不同的子采样，您需要确定对子采样有贡献的原始单元集，并进行归一化以找到每个单元的相对权重。

还有更复杂的图形技术，但这个简单且有效。

- lollercoaster

---

谢谢lollercoaster，解释得非常清楚。幸运的是，我的问题只涉及1D值，所以我可以跳过RGB元素。3->2似乎非常直观，但100->77却不是。我该如何努力使这种思维飞跃成为可能？ - cdevelop

用笔和纸？尝试更多的情况并培养对数字工作方式的直觉？这不是一个编程问题，只是一个需要坐下来思考的问题。 - Useless

你需要一个函数，将n个原始数字通过为每个第m个样本分配每个n个原始数字的归一化权重来转换为m个新槽位。在实践中，贡献的原始bin数量不会很多，但您需要一个函数逐个步进并分配子采样数组。当您以1.0/100的步长进行操作时，当您越过1.0/77的每个倍数时，您需要以加权方式将最后一个子采样单元分配给最后一组原始单元。如果这种方法回答了您的问题，请将其标记为这样！ - lollercoaster