Как выполнить одномерное «действительное» свертка?

Я пытаюсь реализовать одномерную свертку в «действительном» режиме (определение Matlab) в C ++.

Это кажется довольно простым, но я не смог найти код, делающий это на C ++ (или на любом другом языке, к которому я мог бы адаптироваться). Если мой размер вектора является степенью, я могу использовать двумерную свертку, но я хотел бы найти что-то, что будет работать для любого ввода и ядра.

Итак, как выполнить одномерную свертку в «действительном» режиме, учитывая входной вектор размера I и ядро ​​размера K (на выходе обычно должен быть вектор размера I — K + 1).

Псевдокод также принимается.

3

Решение

Вы можете использовать одну из следующих реализаций:

Полная свертка:

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),

LIVE DEMO

Допустимая свертка:

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),

LIVE DEMO

8

Другие решения

Я не понимаю, почему вам нужно реализовать функцию свертки. Разве у Matlab нет встроенной функции 1D свертки?

Оставляя это в стороне, вы можете реализовать свертку с помощью функции преобразования Фурье. Вы должны быть осторожны с длиной входного и выходного векторов. Длина результата I + K - 1 (не I - K + 1, право?). Расширить каждый входной вектор с нулями до длины N где N степень 2 больше или равна I + K - 1, Возьмите преобразование Фурье входных данных, затем умножьте результаты элемент за элементом. Возьмите обратное преобразование Фурье этого произведения и верните первое I + K - 1 элементы (выбросить остальные). Это твоя свертка.

Возможно, вам придется добавить коэффициент масштабирования 1/N где-то, поскольку не существует универсально согласованного масштабирования для преобразований Фурье, и я не помню, что Матлаб предполагает для этого.

1

Для выполнения 1-D действительной свертки на станд :: вектор (давайте назовем это VEC для примера, и выходной вектор будет outvec) размера L достаточно создать правильные границы, правильно установив параметры цикла, а затем выполнить свертку, как обычно, т.е.

for(size_t i = K/2; i < l - K/2; ++i)
{
outvec[i] = 0.0;
for(size_t j = 0; j < K+1; j++)
{
outvec[i - K/2] += invec[i - K/2 + j] * kernel[j];
}
}

Обратите внимание на начальное и конечное значение я.

Работает на любом одномерном ядре любого размера — при условии, что ядро ​​не большего размера, чем вектор;)

Обратите внимание, что я использовал переменную К как вы уже описали, но лично я бы понял «размер» иначе — вопрос вкуса, я думаю. В этом примере общая длина вектора ядра равна K + 1. Я также предположил, что outvec уже имеет л — к элементы (кстати: выходной вектор имеет l — K элементов, а не l — K + 1, как вы написали), поэтому нет отталкивать() нужно.

1