Pracuję w dziedzinie cyfrowego odtwarzania obrazów. Przeczytałem wszystkie rzeczy o splotie, że dla systemu LTI , jeśli znamy jego odpowiedź impulsową , wówczas możemy znaleźć jego wynik, używając po prostu splotu między odpowiedzią wejściową a odpowiedzią impulsową.
Czy ktoś może mi powiedzieć, że jaka jest za tym podstawowa filozofia matematyczna? Twoje wrażenia z powiedzą mi więcej niż tylko surfowanie po Internecie.
image-processing
discrete-signals
convolution
Mayank Tiwari
źródło
źródło
Odpowiedzi:
Idea konwolucji
Moja ulubiona prezentacja tego tematu znajduje się w jednym z wykładów Brada Osgooda na temat transformaty Fouriera . Dyskusja na temat splotu zaczyna się około 36:00, ale cały wykład ma dodatkowy kontekst, który warto obejrzeć.
Podstawową ideą jest to, że gdy definiujesz coś w rodzaju transformacji Fouriera, zamiast cały czas pracować bezpośrednio z definicją, przydatne jest uzyskanie właściwości wyższego poziomu, które upraszczają obliczenia. Na przykład jedną z takich właściwości jest to, że transformacja sumy dwóch funkcji jest równa sumie transformat, tj
Oznacza to, że jeśli masz funkcję z nieznaną transformacją i można ją rozłożyć na sumę funkcji ze znanymi transformacjami, zasadniczo otrzymujesz odpowiedź za darmo.
Ponieważ mamy tożsamość sumy dwóch transformacji, naturalnym pytaniem jest, jaka jest tożsamość iloczynu dwóch transformacji, tj.
Okazuje się, że przy obliczaniu odpowiedzi pojawia się splot. Cała pochodna jest podana w filmie, a ponieważ twoje pytanie jest głównie koncepcyjne, nie podsumuję go tutaj.
Implikacja zbliżenia się do splotu w ten sposób jest taka, że jest to nieodłączna część sposobu, w jaki transformata Laplace'a (której szczególnym przypadkiem jest transformata Fouriera) przekształca zwykłe równania różniczkowe zwyczajne o stałym współczynniku (LCCODE) w równania algebraiczne. Fakt, że taka transformacja jest dostępna, aby uczynić LCCODE możliwym do analizy analitycznym, jest dużą częścią powodu, dla którego są badane w przetwarzaniu sygnału. Na przykład, aby zacytować Oppenheim i Schafer :
Tak więc jedna odpowiedź na pytanie brzmi: jeśli używasz metod transformacji do analizy i / lub syntezy systemów LTI, prędzej czy później dojdzie do splotu (pośrednio lub jawnie). Zauważ, że takie podejście do wprowadzenia splotu jest bardzo standardowe w kontekście równań różniczkowych. Na przykład zobacz wykład MIT Arthura Mattucka . Większość prezentacji albo przedstawia całkę splotu bez komentarza, a następnie czerpie jej właściwości (tj. Wyciąga ją z kapelusza), lub rąbka i maści o dziwnej formie całki, mówi o przerzucaniu i przeciąganiu, odwracaniu czasu itp. Itp. .
Powodem, dla którego podoba mi się podejście prof. Osgooda, jest to, że unika tego wszystkiego tsouris, a także, moim zdaniem, głęboki wgląd w to, w jaki sposób matematycy prawdopodobnie wpadli na ten pomysł. I cytuję:
Systemy LTI
W większości tekstów DSP splot jest zwykle wprowadzany w inny sposób (co pozwala uniknąć odniesienia do metod transformacji). Wyrażając dowolny sygnał wejściowy jako sumę skalowanych i przesuniętych impulsów jednostkowych,x(n)
gdzie
definiujące właściwości liniowych układów niezmienniczych w czasie prowadzą bezpośrednio sumę splotu obejmującą odpowiedź impulsową . Jeśli system zdefiniowany przez operatora LTI L jest wyrażony jako y ( n ) = L [ x ( n ) ] , to przez zastosowanie właściwości repatywnych, a mianowicie liniowościh(n)=L[ δ(n) ] L y(n)=L[ x(n) ]
oraz niezmienność czasu / zmiany
system można przepisać jako
To bardzo standardowy sposób prezentowania splotu i jest to całkowicie elegancki i użyteczny sposób na obejście tego. Podobne pochodne można znaleźć w Oppenheim i Schafer , Proakis i Manolakis , Rabiner i Gold i jestem pewien, że wiele innych. Niektóre głębszy wgląd [który idzie dalej niż standardowe wprowadzeń] jest dana przez Dilip w jego doskonałą odpowiedź tutaj .
Zauważ jednak, że to wyprowadzenie jest nieco magiczną sztuczką. Patrząc jeszcze raz na rozkład sygnału w , widzimy, że ma on już postać splotu. Gdyby(1)
wtedy to tylko x ∗ δ . Ponieważ funkcja delta jest elementem tożsamości dla splotu, powiedzenie, że dowolny sygnał może być wyrażony w tej formie, jest bardzo podobne do powiedzenia, że dowolna liczba n może być wyrażona jako n + 0 lub n × 1 . Teraz wybór opisania sygnałów w ten sposób jest genialny, ponieważ prowadzi bezpośrednio do idei odpowiedzi impulsowej - po prostu idea konwolucji jest już „wypalona” do rozkładu sygnału.(1) x∗δ n n+0 n×1
Z tej perspektywy splot jest nierozerwalnie związany z ideą funkcji delta (tj. Jest to operacja binarna, w której funkcja delta jest elementem tożsamości). Nawet bez uwzględnienia jego związku ze splotem opis sygnału zależy w głównej mierze od idei funkcji delta. Powstaje więc pytanie: skąd pomysł na funkcję delta? O ile mi wiadomo, sięga co najmniej tak daleko jak artykuł Fouriera o Analitycznej Teorii Ciepła, gdzie pojawia się niejawnie. Jednym ze źródeł dalszych informacji jest ten artykuł o pochodzeniu i historii konwolucji autorstwa Alejandro Domíngueza.
Są to dwa główne podejścia do pomysłu w kontekście teorii systemów liniowych. Jeden opowiada się za wglądem analitycznym, a drugi za rozwiązaniem numerycznym. Myślę, że oba są przydatne do pełnego obrazu znaczenia splotu. Jednak w przypadku dyskretnym, całkowicie pomijając układy liniowe, istnieje poczucie, że splot jest znacznie starszym pomysłem.
Mnożenie wielomianowe
Jedną dobrą prezentację idei dyskretnego splotu po prostu wielomianowego zwielokrotnienia podał Gilbert Strang w wykładzie rozpoczynającym się około 5:46. Z tej perspektywy idea sięga wstecz aż do wprowadzenia systemów liczb pozycyjnych (które domyślnie reprezentują liczby jako wielomiany). Ponieważ transformata Z reprezentuje sygnały jako wielomiany w z, również w tym kontekście powstanie splot - nawet jeśli transformacja Z jest formalnie zdefiniowana jako operator opóźnienia bez uciekania się do złożonej analizy i / lub jako szczególny przypadek Laplace'a Przekształć .
źródło
Ja raz dał odpowiedź w Wikipedia stronie splot Dyskusja, która zwróciła się w zasadzie to samo pytanie: dlaczego inwersji czasowej? . Filozofia polega na tym, że przykładasz pojedynczy impuls w czasie 0 do filtra i rejestrujesz jego reakcję w czasie 0,1,2,3,4,… Zasadniczo odpowiedź będzie wyglądać jak funkcja, h (t). Możesz to wykreślić. Jeśli puls był n razy wyższy / wyższy, impulsy odpowiedzi będą proporcjonalnie wyższe (dzieje się tak, ponieważ zawsze zakłada się filtr liniowy). Teraz wszystkie DSP (i nie tylko DSP) dotyczą tego, co się stanie, gdy zastosujesz filtr do swojego sygnału? Znasz odpowiedź impulsową. Twój sygnał (szczególnie cyfrowy) to nic innego jak seria impulsów o wysokości x (t). Ma wysokość / wartość w czasie tx t . Układy liniowe są fajne, że można zsumować wyjścia dla każdego takiego impulsu wejściowego, aby uzyskać funkcję odpowiedzi y (t) dla funkcji wejściowej x (t). Wiesz, że impuls wyjściowy y (t = 10) zależy od natychmiastowego wejścia x (10), co przyczynia się do h (0) * x (10). Ale jest też wkład, x (9) * h (1), w wyjście z poprzedniego impulsu, x (9), i wkład z jeszcze wcześniejszych wartości wejściowych. Widzisz, gdy dodajesz wkłady z wcześniejszych danych wejściowych, jeden argument zmniejsza się, a drugi rośnie. Ci MAC każdy wkład język Y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) + ..., który jest uwypuklony.
Funkcje y (t), h (t) i x (t) można traktować jak wektory. Macierze są operatorami w algebrze liniowej. Biorą wektor wejściowy (szereg liczb) i wytwarzają wektor wyjściowy (kolejna seria liczb). W tym przypadku y jest iloczynem macierzy splotu z wektorem x,
Teraz, z powodu splotu jest macierzą Toeplitza , to jest, a zatem operator splot (liniowy operatorów są przedstawione matryce, ale matrycy zależy również od masy) Fouriera eigenbasis miły macierzą diagonalną w domenie Fouriera
Note, much more zeroes and, thus, much simpler computation. This result is know as "convolution theorem" and, as first response answered, it is much simpler in the fourier domain. But, this is phylosophy behind the "convolution theorem", fourier basis and linear operators rather than ubiquitous need for convolution.
Normally, you do convolution because you have your input signal, impulse response and require output in time domain. You may transform into fourier space to optimize computation. But, it is not practical for simple filters, as I've seen in the DSPGuide. If your filter looks likey[currentTime]=k1x[time−1]+k2x(time−2)+b∗y[time−1] , it makes no sense to fourier transform. You just do n multiplications, for computing every y. It is also natural for real-time. In real-time you compute only one y at a time. You may think of Fourier transform if you have your signal x recorded and you need to compute the whole vector y at once. This would need NxN MAC operations and Fourier can help to reduce them to N log(N).
źródło
Although the previous answers have been really good, I would like to add my viewpoint about convolution where I just make it easier to visualize due to the figures.
One wonders if there is any method through which an output signal of a system can be determined for a given input signal. Convolution is the answer to that question, provided that the system is linear and time-invariant (LTI).
Assume that we have an arbitrary signals[n] . Then, s[n] can be decomposed into a scaled sum of shifted unit impulses through the following reasoning. Multiply s[n] with a unit impulse shifted by m samples as δ[n−m] . Since δ[n−m] is equal to 0 everywhere except at n=m , this would multiply all values of s[n] by 0 when n is not equal to m and by 1 when n is equal to m . So the resulting sequence will have an impulse at n=m with its value equal to s[m] . This process is clearly illustrated in Figure below.
This can be mathematically written as
The values[m′] is extracted at this instant. Therefore, if this multiplication is repeated over all possible delays −∞<m<∞ , and all produced signals are summed together, the result will be the sequence s[n] itself.
In summary, the above equation states thats[n] can be written as a summation of scaled unit impulses, where each unit impulse δ[n−m] has an amplitude s[m] . An example of such a summation is shown in Figure below.
Consider what happens when it is given as an input to an LTI system with an impulse responseh[n] .
This leads to an input-output sequence as
During the above procedure, we have worked out the famous convolution equation that describes the outputr[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 shiftn ,
[Flip] Arranging the equation asr[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 obtainh[−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 sequences[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 timen .
[Repeat] Repeat the above steps for every possible value ofn .
An example of convolution between two signalss[n]=[2−11] 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 signalss[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] .
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 outputr[n] as
Such a method is illustrated in Figure below. From an implementation point of view, there is no difference between both methods.
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.
źródło