如何进行一维"有效"卷积？

Question

我正试图在C++中以"有效"模式(Matlab定义)实现一维卷积.

这看起来很简单,但是我无法在C++中找到代码(或者我可以适应的任何其他语言).如果我的矢量大小是一个幂,我可以使用2D卷积,但我想找到一些适用于任何输入和内核的东西.

那么如何在"有效"模式下执行一维卷积,给定一个大小为I的输入向量和一个大小为K的内核(输出通常应该是大小为I-K + 1的向量).

伪代码也被接受.

Answer 1

您可以使用以下实现之一:

完全卷积:

template<typename T>
std::vector<T>
conv(std::vector<T> const &f, std::vector<T> const &g) {
  int const nf = f.size();
  int const ng = g.size();
  int const n  = nf + ng - 1;
  std::vector<T> out(n, T());
  for(auto i(0); i < n; ++i) {
    int const jmn = (i >= ng - 1)? i - (ng - 1) : 0;
    int const jmx = (i <  nf - 1)? i            : nf - 1;
    for(auto j(jmn); j <= jmx; ++j) {
      out[i] += (f[j] * g[i - j]);
    }
  }
  return out; 
}

f :第一序列(1D信号).

g :第二序列(1D信号).

返回一个std::vector大小f.size() + g.size() - 1,这是离散卷积的结果.柯西产品(f * g) = (g * f).

现场演示

有效卷积:

template<typename T>
std::vector<T>
conv_valid(std::vector<T> const &f, std::vector<T> const &g) {
  int const nf = f.size();
  int const ng = g.size();
  std::vector<T> const &min_v = (nf < ng)? f : g;
  std::vector<T> const &max_v = (nf < ng)? g : f;
  int const n  = std::max(nf, ng) - std::min(nf, ng) + 1;
  std::vector<T> out(n, T());
  for(auto i(0); i < n; ++i) {
    for(int j(min_v.size() - 1), k(i); j >= 0; --j) {
      out[i] += min_v[j] * max_v[k];
      ++k;
    }
  }
  return out;
}

f :第一序列(1D信号).

g :第二序列(1D信号).

返回一个std::vector大小std::max(f.size(), g.size()) - std::min(f.size(), g.size()) + 1,这是有效的(即,没有填充)离散卷积的结果.柯西产品(f * g) = (g * f).

现场演示