Почему требуется свертка или какова философия свертки?

15

Я работаю в области восстановления цифровых изображений. Я прочитал все о свертке, что для системы LTI , если мы знаем ее импульсный отклик , то мы можем найти ее выход, просто используя свертку между входом и импульсным откликом.

Кто-нибудь может сказать мне, что является основной математической философией? Ваш опыт общения с ним скажет мне больше, чем просто интернет-серфинг.

Mayank Tiwari
источник
3
Я опускаю этот вопрос, потому что он (или его незначительные варианты) неоднократно задавался и отвечал на этом сайте, как говорится в комментарии пикенет. Вы должны иметь "интернет-серфинг" на этом сайте.
Дилип Сарватэ

Ответы:

14

Идея свертки

Моя любимая экспозиция этой темы - в одной из лекций Брэда Осгуда о преобразовании Фурье . Обсуждение свертки начинается около 36:00, но вся лекция имеет дополнительный контекст, который стоит посмотреть.

Основная идея заключается в том, что когда вы определяете что-то вроде преобразования Фурье, а не работаете напрямую с определением все время, полезно получить свойства более высокого уровня, которые упрощают вычисления. Например, одним из таких свойств является то, что преобразование суммы двух функций равно сумме преобразований, т.е.

F{f+g}=F{f}+F{g}.

Это означает, что если у вас есть функция с неизвестным преобразованием, и ее можно разложить на сумму функций с известными преобразованиями, вы в основном получите ответ бесплатно.

Теперь, поскольку у нас есть тождество для суммы двух преобразований, естественно задать вопрос, каково тождество для произведения двух преобразований, т.е.

F{f}F{g}= ?.

Оказывается, когда вы вычисляете ответ, появляется свертка. Весь вывод приведен в видео, и, поскольку ваш вопрос носит в основном концептуальный характер, я не буду здесь его повторять.

Смысл приближения к свертке таким образом заключается в том, что он является неотъемлемой частью того, как преобразование Лапласа (частный случай которого является преобразованием Фурье) превращает линейные обыкновенные дифференциальные уравнения с постоянными коэффициентами (LCCODE) в алгебраические уравнения. Тот факт, что такое преобразование доступно, чтобы сделать LCCODE аналитически поддающимся анализу, является большой частью причины, почему они изучаются в обработке сигналов. Например, чтобы процитировать Оппенгейма и Шефера :

Поскольку их относительно легко математически охарактеризовать и поскольку они могут быть разработаны для выполнения полезных функций обработки сигналов, класс систем, инвариантных к линейному сдвигу, будет широко изучаться.

Таким образом, один ответ на вопрос заключается в том, что если вы используете методы преобразования для анализа и / или синтеза систем LTI, рано или поздно возникнет свертка (неявно или явно). Обратите внимание, что этот подход к введению свертки является очень стандартным в контексте дифференциальных уравнений. Например, посмотрите эту лекцию MIT Артура Маттука . В большинстве презентаций либо представлен интеграл свертки без комментариев, а затем получены его свойства (т. Е. Вытащить его из шапки), либо рассказы о странной форме интеграла, разговоры о переворачивании и перетаскивании, обращении времени и т. Д. И т. Д. И т. Д. ,

Причина, по которой мне нравится подход профессора Осгуда, заключается в том, что он избегает всего этого цури, а также дает, на мой взгляд, глубокое понимание того, как математики, вероятно, пришли к идее в первую очередь. И я цитирую:

Я сказал: «Есть ли способ объединения F и G во временной области, чтобы в частотной области спектры умножались, а Фурье - умножались?» И ответ, да, есть, с помощью этого сложного интеграла. Это не так очевидно. Вы не встали бы с постели утром и не записали бы это, и не ожидали, что это решит эту проблему. Как мы это получим? Вы сказали: предположим, проблема решена, посмотрим, что должно произойти, и тогда мы должны были бы признать, когда пришло время объявить победу. И пришло время объявить победу.

Теперь, будучи отвратительным математиком, вы покрываете свои следы и говорите: «Ну, я просто собираюсь определить свертку двух функций по этой формуле».

Системы LTI

В большинстве текстов DSP свертка обычно вводится по-другому (избегая любых ссылок на методы преобразования). Выражая произвольный входной сигнал в виде суммы масштабированных и сдвинутых единичных импульсов,x(n)

(1)x(n)=k=x(k)δ(nk),

где

(2)δ(n)={0,n01,n=0,

определяющие свойства линейных не зависящих от времени систем приводят непосредственно к сумме свертки, включающей импульсный отклик . Если система, определенная оператором LTI L , выражается как y ( n ) = L [ x ( n ) ] , то путем применения соответствующих свойств, а именно линейностичас(N)знак равноL[ δ(N) ]LY(N)знак равноL[ Икс(N) ]

(3)L[ aИкс1(N)+бИкс2(N) ]Преобразование суммы масштабированных входовзнак равноaL[ Икс1(N) ]+бL[ Икс2(N) ]Сумма масштабированных преобразований,

и инвариантность времени / сдвига

(4)L[ x(n) ]=y(n) impliesL[ x(nk) ]=y(nk),

система может быть переписана как

y(n)=L[k=x(k)δ(nk)]Tranform of the sum of scaled inputs=k=x(k)L[δ(nk)]Sum of scaled transforms=k=x(k)h(nk).Convolution with the impulse response

Это очень стандартный способ представления свертки, и это очень элегантный и полезный способ сделать это. Подобные выводы можно найти в Оппенгейме и Шафере , Проакисе и Манолакисе , Рабинере и Голде , и , я уверен, многих других. Некоторое более глубокое понимание [которое идет дальше чем стандартные введения] дано Дилипом в его превосходном ответе здесь .

Обратите внимание, однако, что этот вывод является своего рода волшебным трюком. Еще раз посмотрев, как сигнал разлагается в , мы видим, что он уже в форме свертки. Если(1)

(fg)(n)f convolved with g=k=f(k)g(nk),

тогда является просто x δ . Поскольку дельта-функция является единичным элементом для свертки, сказать, что любой сигнал может быть выражен в этой форме, очень похоже на то, что любое число n может быть выражено как n + 0 или n × 1 . Теперь, выбор для описания сигналов таким способом является блестящим, потому что это приводит непосредственно к идее импульсного отклика - это просто, что идея свертки уже «запечатлена» в разложении сигнала.(1)xδnn+0n×1

С этой точки зрения свертка неразрывно связана с идеей дельта-функции (т. Е. Это двоичная операция, в которой дельта-функция имеет свой элемент идентичности). Даже без учета его отношения к свертке, описание сигнала в решающей степени зависит от идеи дельта-функции. Таким образом, возникает вопрос: откуда мы взяли идею дельта-функции? Насколько я могу судить, это относится, по крайней мере, к статье Фурье « Аналитическая теория тепла», где она появляется неявно. Одним из источников дополнительной информации является статья Алехандро Домингеса « Происхождение и история свертки ».

Вот два основных подхода к идее в контексте теории линейных систем. Один предпочитает аналитическое понимание, а другой предпочитает численное решение. Я думаю, что оба полезны для полной картины важности свертки. Однако в дискретном случае, если пренебрегать линейными системами полностью, есть смысл, в котором свертка является гораздо более старой идеей.

Полиномиальное Умножение

Гилберт Странг в этой лекции, начинающейся около 5:46, дал одно хорошее представление о том, что дискретная свертка - это просто полиномиальное умножение . С этой точки зрения идея возвращается к введению позиционных систем счисления (которые неявно представляют числа в виде полиномов). Поскольку Z-преобразование представляет сигналы как многочлены от z, свертка также возникнет в этом контексте - даже если Z-преобразование формально определено как оператор задержки без использования сложного анализа и / или как особый случай Лапласа. Transform .

специалист по обработке данных
источник
Спасибо, сэр, за ваше бесценное руководство, вы только что показали мне правильный путь. Ваша эта помощь научила меня тому, как стать хорошим человеком, начать для других .... :)
Mayank Tiwari
Как это большое совпадение объясняет, что вам нужно сделать свертку в случае, если его спросить? Я считаю, что в каждом домене есть операция, которая превращается в свертку, когда вы возвращаете аргументы во временную область. Может быть, нам нужно выполнить muiltiplication во временной области, чтобы получить ответ? Почему мы должны умножать частоты вместо разметок?
Val
1
Учитывая, что ОП уже задавал вопрос о роли импульсов по отношению к системам LTI , я прочитал этот вопрос в качестве его примера, используя его в качестве примера, чтобы мотивировать вопрос о том, откуда берется свертка - не обязательно ее роль в вычислении импульса. ответ сам по себе. Это то, что вы спрашиваете?
Datageist
1
Сказать, что нам нужна свертка, поскольку она идентична умножению Фурье, звучит для меня нонсенсом, если мы не знаем, зачем нам нужно умножение Фурье. Когда нам дают импульсный отклик, это означает временную область и свертку, а не любую черную магию на основе Фурье. Я не думаю, что ссылка на этот вопрос может прояснить это. В любом случае, нехорошо давать «локализованные ответы» на общие, фундаментальные (то есть философские) вопросы. Вопросы и ответы должны быть полезны для будущих посетителей.
Val
Комментарий Вэля выше точно в цель. Интересно, как работали линейные системы до того, как были изобретены / открыты преобразования Фурье. Как на земле не чувствующий неодушевленный объект обнаружил такую ​​сложную формулу?
Дилип Сарватэ
6

Однажды я дал ответ на странице обсуждения свертки Википедии, где задавался в основном тот же вопрос: почему инверсия времени? , Философия заключается в том, что вы применяете один импульс в момент времени 0 к своему фильтру и записываете его ответ в момент времени 0,1,2,3,4,…. В основном ответ будет выглядеть как функция h (t). Вы можете построить это. Если импульс был в n раз выше / выше, ответные импульсы будут пропорционально выше (это потому, что линейный фильтр всегда предполагается). Теперь все DSP (и не только DSP) о том, что происходит, когда вы применяете фильтр к своему сигналу? Вы знаете импульсный ответ. Ваш сигнал (особенно цифровой) является не чем иным, как серией импульсов высотой x (t). Имеет высоту / значение в момент времени txt, Линейные системы хороши тем, что вы можете суммировать выходы для каждого такого входного импульса, чтобы получить функцию отклика y (t) для функции входа x (t). Вы знаете, что выходной импульс y (t = 10) зависит от непосредственного входа x (10), который вносит h (0) * x (10). Но есть также вклад x (9) * h (1) в выходной сигнал предыдущего импульса x (9) и вклад от более ранних входных значений. Видите ли, когда вы добавляете вклады из более ранних входных данных, один временной аргумент уменьшается, а другой увеличивается. Вы вносите в MAC все вклады в y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) +…, что является сверткой.

Вы можете думать о функциях y (t), h (t) и x (t) как о векторах. Матрицы являются операторами в линейной алгебре. Они берут входной вектор (ряд чисел) и создают выходной вектор (другой ряд чисел). В этом случае у является произведением матрицы свертки с вектором х,

y=[y0y1y2]=[h000h1h00h2h1h0][x0x1x2]=Hx

Теперь, поскольку свертка является матрицей Теплица , она имеет собственное основание Фурье и, следовательно, оператор свертки (линейные операторы представлены матрицами, но матрица также зависит от базиса) является хорошей диагональной матрицей в области Фурье,

Y=[Y0Y1Y2]=[λ0000λ1000λ2][X0X1X2]=diag(H)X

Обратите внимание, гораздо больше нулей и, следовательно, гораздо проще вычислений. Этот результат известен как «теорема свертки», и, как ответил первый ответ, в области Фурье он намного проще. Но это философия, лежащая в основе «теоремы свертки», базиса Фурье и линейных операторов, а не повсеместная потребность в свертке.

y[currentTime]=k1x[time1]+k2x(time2)+by[time1]

Val
источник
Пара замечаний: как бы вы расширили это описание для случая с непрерывным временем (который явно предшествовал случаю с дискретным временем)? Кроме того, существует много приложений реального времени, которые используют методы на основе преобразования Фурье для быстрой свертки. Сказать, что выходные данные всегда рассчитываются по одному для приложений реального времени, просто не соответствует действительности.
Джейсон Р
С учетом сказанного, хорошая работа, указывающая на тот факт, что структура Тёплица матрицы свертки подразумевает, что она допускает диагональное представление под базисом Фурье.
Джейсон Р
Да, может быть, вы используете преобразование Фурье в режиме реального времени. Я далеко не эксперт по DSP. Я просто высказал идею (которую я получил от своей скудной практики и чтения DSPGuide). В любом случае, я хочу подчеркнуть, что Фурье не имеет ничего общего с философией свертки. Может быть, мне нужно удалить все обсуждения, связанные с Фурье, так как это отвлекает. Свертка естественна во временной области и необходима без какого-либо Фурье, независимо от того, насколько крут Фурье.
Val
f(x)dxf(x)dx=limdx0(f(x)dx)
@JasonR В непрерывном режиме вы бы заменили матрицу Теплица на оператор, инвариантный к сдвигу. Затем можно показать, что базисные функции Фурье диагонализуют этот оператор.
lp251
3

Хотя предыдущие ответы были действительно хорошими, я хотел бы добавить свою точку зрения на свертку, где я просто упрощаю визуализацию благодаря рисункам.

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

s[n]s[n]s[n]mδ[nm]δ[nm]n=ms[n]nmnmn=ms[m]

введите описание изображения здесь

s[n]δ[nm]=s[m]δ[nm]
m
s[n]δ[nm]=s[m]δ[nm]

s[m]<m<s[n]

s[n]=+s[2]δ[n+2]+s[1]δ[n+1]+s[0]δ[n]+s[1]δ[n1]+s[2]δ[n2]+=m=s[m]δ[nm]

s[n]δ[nm]s[m]

введите описание изображения здесь

h[n].

enter image description here

This leads to an input-output sequence as

enter image description here

During the above procedure, we have worked out the famous convolution equation that describes the output r[n] for an input s[n] to an LTI system with impulse response h[n].

Convolution is a very logical and simple process but many DSP learners can find it confusing due to the way it is explained. We will describe a conventional method and another more intuitive approach.

Conventional Method


Most textbooks after defining the convolution equation suggest its implementation through the following steps. For every individual time shift n,

[Flip] Arranging the equation as r[n]=m=s[m]h[m+n], consider the impulse response as a function of variable m, flip h[m] about m=0 to obtain h[m].

[Shift] To obtain h[m+n] for time shift n, shift h[m] by n units to the right for positive n and left for negative n.

[Multiply] Point-wise multiply the sequence s[m] by sequence h[m+n] to obtain a product sequence s[m]h[m+n].

[Sum] Sum all the values of the above product sequence to obtain the convolution output at time n.

[Repeat] Repeat the above steps for every possible value of n.

An example of convolution between two signals s[n]=[211] and h[n]=[112] is shown in Figure below, where the result r[n] is shown for each n.

Note a change in signal representation above. The actual signals s[n] and h[n] are a function of time index n but the convolution equation denotes both of these signals with time index m. On the other hand, n is used to represent the time shift of h[m] before multiplying it with s[m] point-wise. The output r[n] is a function of time index n, which was that shift applied to h[m].

enter image description here

Next, we turn to the more intuitive method where flipping a signal is not required.

Intuitive Method


There is another method to understand convolution. In fact, it is built on the derivation of convolution equation, i.e., find the output r[n] as

r[n] = +s[2]h[n+2] +s[1]h[n+1] +s[0]h[n] + s[1]h[n1] + s[2]h[n2] +
Let us solve the same example as in the above Figure, where s[n]=[2 11] and h[n]=[112]. This is shown in Table below.

enter image description here

Such a method is illustrated in Figure below. From an implementation point of view, there is no difference between both methods.

enter image description here

To sum up, convolution tells us how an LTI system behaves in response to a particular input and thanks to intuitive method above, we can say that convolution is also multiplication in time domain (and flipping the signal is not necessary), except the fact that this time domain multiplication involves memory. To further understand at a much deeper level where flipping comes from, and what happens in frequency domain, you can download a sample section from my book here.

Qasim Chaudhari
источник