线性插值。如何实现这一算法的C？ （Python版本中给出） [英] Linear Interpolation. How to implement this algorithm in C ? (Python version is given)

问题描述

存在一个非常好的线性插值法。它的性能最多每输出采样一个多元线性插值需要的。我发现由里昂了解DSP的第三版其描述。这种方法涉及到一个特殊的保持缓冲器。给定一个号码的样品被任意两个输入样本之间插入的，它产生用线性插值输出点。在这里，我已经重写使用Python这种算法：

There exists one very good linear interpolation method. It performs linear interpolation requiring at most one multiply per output sample. I found its description in a third edition of Understanding DSP by Lyons. This method involves a special hold buffer. Given a number of samples to be inserted between any two input samples, it produces output points using linear interpolation. Here, I have rewritten this algorithm using Python:

temp1, temp2 = 0, 0
iL = 1.0 / L
for i in x:
   hold = [i-temp1] * L
   temp1 = i
   for j in hold:
      temp2 += j
      y.append(temp2 *iL)

其中x包含输入样本，L是要被插入多个点，Y将包含输出样本

where x contains input samples, L is a number of points to be inserted, y will contain output samples.

我的问题是如何以最有效的方式实现这种算法的ANSI C ，例如：是它能够避免第二环路？

My question is how to implement such algorithm in ANSI C in a most effective way, e.g. is it possible to avoid the second loop?

注：presented Python的code只是为了了解这种算法的工作。

NOTE: presented Python code is just to understand how this algorithm works.

更新：下面是一个例子它是如何工作在Python：

UPDATE: here is an example how it works in Python:

x=[]
y=[]
hold=[]
num_points=20
points_inbetween = 2

temp1,temp2=0,0

for i in range(num_points):
   x.append( sin(i*2.0*pi * 0.1) )

L = points_inbetween
iL = 1.0/L
for i in x:
   hold = [i-temp1] * L
   temp1 = i
   for j in hold:
      temp2 += j
      y.append(temp2 * iL)

让我们说X = [... ... 10，20，30 ....]。然后，如果L = 1时，会产生[... 10，15，20，25，30 ...]

Let's say x=[.... 10, 20, 30 ....]. Then, if L=1, it will produce [... 10, 15, 20, 25, 30 ...]

推荐答案

...或者我把它称为采样（错误的词，大概免责声明：我没有看过里昂）。我只是要明白什么是code做，然后重新写了可读性。由于赋予了它有几个问题：

Interpolation in the sense of "signal sample rate increase"

... or i call it, "upsampling" (wrong term, probably. disclaimer: i have not read Lyons'). I just had to understand what the code does and then re-write it for readability. As given it has couple of problems:

一）它是低效的 - 两个循环是好的，但它确实倍增为每一个输出项;同时它采用中介列表（持有），产生导致与追加（小啤酒）

a) it is inefficient - two loops is ok but it does multiplication for every single output item; also it uses intermediary lists(hold), generates result with append (small beer)

二）插错了第一区间;它产生在所述第一元件的前面假数据。假设我们有乘数= 5和seq = [20，30] - 它会产生[0,4,8,12,16,20,22,24,28,30]而不是[20,22,24,26， 28,30]。

b) it interpolates wrong the first interval; it generates fake data in front of the first element. Say we have multiplier=5 and seq=[20,30] - it will generate [0,4,8,12,16,20,22,24,28,30] instead of [20,22,24,26,28,30].

因此​​，这里的算法在发电机的形式：

So here is the algorithm in form of a generator:

def upsampler(seq, multiplier):
    if seq:
        step = 1.0 / multiplier
        y0 = seq[0];
        yield y0
        for y in seq[1:]:
            dY = (y-y0) * step
            for i in range(multiplier-1):
                y0 += dY;
                yield y0
            y0 = y;
            yield y0

好了，现在的一些测试：

Ok and now for some tests:

>>> list(upsampler([], 3))  # this is just the same as [Y for Y in upsampler([], 3)]
[]
>>> list(upsampler([1], 3))
[1]
>>> list(upsampler([1,2], 3))
[1, 1.3333333333333333, 1.6666666666666665, 2]
>>> from math import sin, pi
>>> seq = [sin(2.0*pi * i/10) for i in range(20)]
>>> seq
[0.0, 0.58778525229247314, 0.95105651629515353, 0.95105651629515364, 0.58778525229247325, 1.2246063538223773e-016, -0.58778525229247303, -0.95105651629515353, -0.95105651629515364, -0.58778525229247336, -2.4492127076447545e-016, 0.58778525229247214, 0.95105651629515353, 0.95105651629515364, 0.58778525229247336, 3.6738190614671318e-016, -0.5877852522924728, -0.95105651629515342, -0.95105651629515375, -0.58778525229247347]
>>> list(upsampler(seq, 2))
[0.0, 0.29389262614623657, 0.58778525229247314, 0.76942088429381328, 0.95105651629515353, 0.95105651629515364, 0.95105651629515364, 0.7694208842938135, 0.58778525229247325, 0.29389262614623668, 1.2246063538223773e-016, -0.29389262614623646, -0.58778525229247303, -0.76942088429381328, -0.95105651629515353, -0.95105651629515364, -0.95105651629515364, -0.7694208842938135, -0.58778525229247336, -0.29389262614623679, -2.4492127076447545e-016, 0.29389262614623596, 0.58778525229247214, 0.76942088429381283, 0.95105651629515353, 0.95105651629515364, 0.95105651629515364, 0.7694208842938135, 0.58778525229247336, 0.29389262614623685, 3.6738190614671318e-016, -0.29389262614623618, -0.5877852522924728, -0.76942088429381306, -0.95105651629515342, -0.95105651629515364, -0.95105651629515375, -0.76942088429381361, -0.58778525229247347]

这里是我翻译到C，适合克拉茨的FN模板：

And here is my translation to C, fit into Kratz's fn template:

/**
 *
 * @param src caller supplied array with data
 * @param src_len len of src
 * @param steps to interpolate
 * @param dst output param will be filled with (src_len - 1) * steps + 1 samples
 */
float* linearInterpolation(float* src, int src_len, int steps, float* dst)
{
    float step, y0, dy;
    float *src_end;
    if (src_len > 0) {
        step = 1.0 / steps;
        for (src_end = src+src_len; *dst++ = y0 = *src++, src < src_end; ) {
            dY = (*src - y0) * step;
            for (int i=steps; i>0; i--) {
                *dst++ = y0 += dY;
            }
        }
    }
}

请注意的C代码段类型的，但从来没有编译或运行，所以有可能是语法错误，关×1的误差等，但总的想法是存在的。

Please note the C snippet is "typed but never compiled or run", so there might be syntax errors, off-by-1 errors etc. But overall the idea is there.

这篇关于线性插值。如何实现这一算法的C？ （Python版本中给出）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！