Pourquoi la convolution est-elle nécessaire, ou quelle est la philosophie derrière la convolution?

15

Je travaille dans le domaine de la restauration d'images numériques. J'ai lu tout sur la convolution, que, pour un système LTI , si nous connaissons sa réponse impulsionnelle , nous pouvons trouver sa sortie en utilisant simplement la convolution entre l'entrée et la réponse impulsionnelle.

Quelqu'un peut-il me dire quelle est la principale philosophie mathématique derrière cela? Votre expérience avec m'en dira plus que la simple navigation sur Internet à ce sujet.

Mayank Tiwari
la source
3
Je sous-vote cette question car elle (ou des variantes mineures de celle-ci) a été posée à plusieurs reprises et répondue sur ce site, comme l'indique le commentaire des pichenettes. Vous devriez plutôt avoir "surfé sur Internet" sur ce site.
Dilip Sarwate

Réponses:

14

L'idée de convolution

Mon exposition préférée du sujet est dans l'une des conférences de Brad Osgood sur la transformée de Fourier . La discussion sur la convolution commence vers 36h00, mais toute la conférence a un contexte supplémentaire qui mérite d'être regardé.

L'idée de base est que, lorsque vous définissez quelque chose comme la transformation de Fourier, plutôt que de travailler directement avec la définition tout le temps, il est utile de dériver des propriétés de niveau supérieur qui simplifient les calculs. Par exemple, une de ces propriétés est que la transformation de la somme de deux fonctions est égale à la somme des transformations, c'est-à-dire

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

Cela signifie que si vous avez une fonction avec une transformation inconnue, et qu'elle peut être décomposée comme une somme de fonctions avec des transformations connues, vous obtenez essentiellement la réponse gratuitement.

Maintenant, puisque nous avons une identité pour la somme de deux transformations, il est naturel de se demander quelle est l'identité pour le produit de deux transformations, c'est-à-dire

F{f}F{g}= ?.

Il s'avère que lorsque vous calculez la réponse, c'est la convolution qui apparaît. La dérivation entière est donnée dans la vidéo, et puisque votre question est principalement conceptuelle, je ne la récapitulerai pas ici.

L'implication de l'approche de la convolution de cette manière est qu'elle fait partie intrinsèque de la façon dont la transformée de Laplace (dont la transformée de Fourier est un cas spécial) transforme les équations différentielles ordinaires à coefficient constant linéaire (LCCODE) en équations algébriques. Le fait qu'une telle transformation soit disponible pour rendre le LCCODE analytiquement traitable est une grande partie de la raison pour laquelle ils sont étudiés dans le traitement du signal. Par exemple, pour citer Oppenheim et Schafer :

Parce qu'ils sont relativement faciles à caractériser mathématiquement et qu'ils peuvent être conçus pour effectuer des fonctions de traitement du signal utiles, la classe des systèmes linéaires invariants sera étudiée de manière approfondie.

Donc, une réponse à la question est que si vous utilisez des méthodes de transformation pour analyser et / ou synthétiser des systèmes LTI, tôt ou tard, une convolution se produira (implicitement ou explicitement). Notez que cette approche pour introduire la convolution est très standard dans le contexte des équations différentielles. Par exemple, voir cette conférence du MIT par Arthur Mattuck . La plupart des présentations présentent l'intégrale de convolution sans commentaire, puis dérivent ses propriétés (c.-à-d. La tirent d'un chapeau), ou ourlent la forme étrange de l'intégrale, parlent de retournement et de traînée, d'inversion du temps, etc., etc. .

La raison pour laquelle j'aime l'approche du professeur Osgood est qu'elle évite tous ces tsouris, tout en fournissant, à mon avis, un aperçu approfondi de la façon dont les mathématiciens sont probablement arrivés à l'idée en premier lieu. Et je cite:

J'ai dit: "Y a-t-il un moyen de combiner F et G dans le domaine temporel, de sorte que dans le domaine fréquentiel les spectres se multiplient, les transformées de Fourier se multiplient?" Et la réponse est, oui, il y a, par cette intégrale compliquée. Ce n'est pas si évident. Vous ne sortiriez pas du lit le matin et ne l'écririez pas, et vous vous attendriez à ce que cela résoudrait ce problème. Comment l'obtenons-nous? Vous avez dit, supposez que le problème soit résolu, voyez ce qui doit arriver, et ensuite nous devrons reconnaître quand il est temps de déclarer la victoire. Et il est temps de déclarer la victoire.

Maintenant, étant un mathématicien désagréable, vous couvrez vos traces et dites: "Eh bien, je vais simplement définir la convolution de deux fonctions par cette formule."

Systèmes LTI

Dans la plupart des textes DSP, la convolution est généralement introduite d'une manière différente (ce qui évite toute référence aux méthodes de transformation). En exprimant un signal d'entrée arbitraire comme une somme d'impulsions unitaires mises à l'échelle et décalées,x(n)

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

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

les propriétés déterminantes des systèmes linéaires invariants dans le temps conduisent directement à une somme de convolution impliquant la réponse impulsionnelle . Si le système défini par un opérateur LTI L est exprimé comme y ( n ) = L [ x ( n ) ] , alors en appliquant les propriétés répectives, à savoir la linéaritéh(n)=L[ δ(n) ]Ly(n)=L[ x(n) ]

(3)L[ ax1(n)+bx2(n) ]Transform of the sum of scaled inputs=aL[ x1(n) ]+bL[ x2(n) ]Sum of scaled transforms,

et invariance temps / décalage

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

le système peut être réécrit comme

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

C'est une façon très standard de présenter la convolution, et c'est une manière parfaitement élégante et utile de s'y prendre. Des dérivations similaires peuvent être trouvées dans Oppenheim et Schafer , Proakis et Manolakis , Rabiner et Gold , et je suis sûr que beaucoup d'autres. Un aperçu plus approfondi [qui va plus loin que les introductions standard] est donné par Dilip dans son excellente réponse ici .

Notez, cependant, que cette dérivation est en quelque sorte un tour de magie. En jetant un autre regard sur la façon dont le signal est décomposé en , nous pouvons voir qu'il est déjà sous la forme d'une convolution. Si(1)

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

alors est juste x δ . Parce que la fonction delta est l' élément d'identité pour la convolution, dire que n'importe quel signal peut être exprimé sous cette forme est un peu comme dire que n'importe quel nombre n peut être exprimé comme n + 0 ou n × 1 . Maintenant, choisir de décrire les signaux de cette façon est brillant car cela conduit directement à l'idée d'une réponse impulsionnelle - c'est juste que l'idée de convolution est déjà "intégrée" à la décomposition du signal.(1)xδnn+0n×1

De ce point de vue, la convolution est intrinsèquement liée à l'idée d'une fonction delta (c'est-à-dire qu'il s'agit d'une opération binaire qui a la fonction delta comme élément d'identité). Même sans considérer sa relation avec la convolution, la description du signal dépend essentiellement de l'idée de la fonction delta. Alors la question devient alors, où avons-nous eu l'idée de la fonction delta en premier lieu? Pour autant que je sache, il remonte au moins aussi loin que l'article de Fourier sur la théorie analytique de la chaleur, où il apparaît implicitement. Une source pour plus d'informations est cet article sur l'origine et l'histoire de la convolution par Alejandro Domínguez.

Maintenant, ce sont les deux des principales approches de l'idée dans le contexte de la théorie des systèmes linéaires. L'un favorise la perspicacité analytique, et l'autre favorise la solution numérique. Je pense que les deux sont utiles pour une image complète de l'importance de la convolution. Cependant, dans le cas discret, en négligeant complètement les systèmes linéaires, il y a un sens dans lequel la convolution est une idée beaucoup plus ancienne.

Multiplication polynomiale

Gilbert Strang donne une bonne présentation de l'idée que la convolution discrète n'est qu'une multiplication polynomiale dans cette conférence commençant vers 5 h 46. De ce point de vue, l'idée remonte à l'introduction des systèmes de nombres positionnels (qui représentent implicitement les nombres sous forme de polynômes). Parce que la transformée en Z représente les signaux sous forme de polynômes en z, la convolution se produira également dans ce contexte - même si la transformée en Z est définie formellement comme un opérateur de retard sans recourir à une analyse complexe et / ou comme un cas spécial du Laplace Transformez .

datageist
la source
merci monsieur pour vos précieux conseils, vous venez de me montrer la bonne voie à suivre. Votre aide m'a appris que comment être un bon humain commence pour les autres .... :)
Mayank Tiwari
Comment cette grande coïncidence explique-t-elle que vous devez faire la convolution dans le cas demandé? Je crois que dans chaque domaine, il y a une opération qui se transforme en convolution lorsque vous retournez les arguments dans le domaine temporel. Pourrait-on avoir besoin de multiplier les muiltiplications dans le domaine temporel pour obtenir la réponse? Pourquoi devrions-nous multiplier les fréquences au lieu de balayages temporels?
Val
1
Étant donné que le PO avait déjà posé une question sur le rôle des impulsions par rapport aux systèmes LTI , j'ai lu la question comme s'il l'utilisait comme exemple pour motiver une question sur l'origine de la convolution - pas nécessairement son rôle dans le calcul d'une impulsion réponse en soi. C'est bien ce que vous demandez?
datageist
1
Dire que nous avons besoin de la convolution parce qu'elle est identique à la multiplication de Fourier me semble insensé au cas où nous ne saurions pas pourquoi nous avons besoin de la multiplication de Fourier. Lorsque nous recevons la réponse impulsionnelle, cela signifie le domaine temporel et la convolution plutôt que toute magie noire en base de Fourier. Je ne pense pas que la référence à cette question puisse clarifier cela. Dans tous les cas, il n'est pas bon de donner des "réponses localisées" à des questions générales, fondamentales (c'est-à-dire phylosophiques). Les questions et réponses doivent être utiles aux futurs visiteurs.
Val
Le commentaire de Val ci-dessus est juste sur la cible. Je me demande comment les systèmes linéaires fonctionnaient avant que les transformées de Fourier soient inventées / découvertes. Comment diable un objet inanimé non sensible a-t-il pu découvrir une formule aussi compliquée?
Dilip Sarwate
6

J'ai une fois donné la réponse sur la page de discussion sur la convolution de Wikipédia, qui posait essentiellement la même question: pourquoi l'inversion du temps? . La philosophie est que vous appliquez une seule impulsion au temps 0 à votre filtre et enregistrez sa réponse au temps 0,1,2,3,4,…. Fondamentalement, la réponse ressemblera à une fonction, h (t). Vous pouvez le tracer. Si l'impulsion était n fois plus haute / plus élevée, les impulsions de réponse seront proportionnellement plus hautes (c'est parce que le filtre linéaire est toujours supposé). Maintenant, tout DSP (et pas seulement DSP) concerne ce qui se passe lorsque vous appliquez le filtre à votre signal? Vous connaissez la réponse impulsionnelle. Votre signal (surtout numérique) n'est rien d'autre qu'une série d'impulsions de hauteur x (t). Il a hauteur / valeur au temps txt. Les systèmes linéaires sont cool que vous pouvez additionner les sorties pour chacune de ces impulsions d'entrée pour obtenir la fonction de réponse y (t) pour la fonction d'entrée x (t). Vous savez que l'impulsion de sortie y (t = 10) dépend de l'entrée immédiate x (10), ce qui contribue à h (0) * x (10). Mais il y a aussi une contribution, x (9) * h (1), à la sortie de l'impulsion précédente, x (9), et des contributions de valeurs d'entrée encore antérieures. Vous voyez, lorsque vous ajoutez des contributions provenant d'entrées précédentes, un argument de temps diminue tandis qu'un autre augmente. Vous MAC toutes les contributions en y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) +…, qui est une convolution.

Vous pouvez considérer les fonctions y (t), h (t) et x (t) comme des vecteurs. Les matrices sont des opérateurs dans l'algèbre linéaire. Ils prennent un vecteur d'entrée (une série de nombres) et produisent un vecteur de sortie (une autre série de nombres). Dans ce cas, le y est un produit de la matrice de convolution avec le vecteur x,

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

Maintenant, comme la convolution est une matrice de Toeplitz , elle a une base propre de Fourier et, par conséquent, l'opérateur de convolution (les opérateurs linéaires sont représentés par des matrices, mais la matrice dépend également de la base) est une belle matrice diagonale dans le domaine de Fourier,

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

Notez bien plus de zéros et donc un calcul beaucoup plus simple. Ce résultat est connu sous le nom de "théorème de convolution" et, comme l'a répondu la première réponse, il est beaucoup plus simple dans le domaine de Fourier. Mais c'est la philosophie derrière le "théorème de convolution", la base de Fourier et les opérateurs linéaires plutôt que le besoin omniprésent de convolution.

Normalement, vous effectuez une convolution parce que vous avez votre signal d'entrée, une réponse impulsionnelle et que vous avez besoin d'une sortie dans le domaine temporel. Vous pouvez vous transformer en espace de Fourier pour optimiser le calcul. Mais, ce n'est pas pratique pour les filtres simples, comme je l'ai vu dans le DSPGuide . Si votre filtre ressemble à , la transformée de Fourier n'a aucun sens. Vous faites juste n multiplications, pour calculer chaque y. Il est également naturel en temps réel. En temps réel, vous ne calculez qu'un seul y à la fois. Vous pouvez penser à la transformée de Fourier si vous avez enregistré votre signal x et que vous devez calculer le vecteur entier y à la fois. Cela nécessiterait des opérations MAC NxN et Fourier peut aider à les réduire à N log (N).y[currentTime]=k1x[time1]+k2x(time2)+by[time1]

Val
la source
Quelques remarques: comment prolongeriez-vous cette description pour le cas à temps continu (qui est évidemment venu avant le cas à temps discret)? De plus, il existe de nombreuses applications en temps réel qui utilisent des méthodes basées sur la transformée de Fourier pour une convolution rapide. Dire que les sorties sont toujours calculées une à la fois pour les applications en temps réel n'est tout simplement pas vrai.
Jason R
Cela dit, beau travail soulignant le fait que la structure de Toeplitz de la matrice de convolution implique qu'elle admet une représentation diagonale sous une base de Fourier.
Jason R
Oui, il se peut que vous utilisiez la transmission Fourier en temps réel. Je suis loin d'être un expert DSP. Je viens d'exprimer l'idée (que j'ai tirée de ma pratique limitée et de la lecture de DSPGuide). Quoi qu'il en soit, je tiens à souligner que la fourier n'a rien à voir avec la philosophie de la convolution. Pourrais-je avoir besoin de supprimer toutes les discussions liées à Fourier, car elles sont distrayantes. La convolution est naturelle dans le domaine temporel et est nécessaire sans Fourier, quelle que soit la fraîcheur du Fourier.
Val
F(X)X est compris comme un cas limite de la somme discrète: F(X)X=limX0(F(X)X). Donc, cela ne peut pas venir avant une sommation discrète.
Val
@JasonR Dans le cadre continu, vous remplaceriez la matrice de Toeplitz par un opérateur invariant par décalage. Vous pouvez alors montrer que les fonctions de base de Fourier diagonalisent cet opérateur.
lp251
3

Bien que les réponses précédentes aient été vraiment bonnes, je voudrais ajouter mon point de vue sur la convolution où je le rend plus facile à visualiser en raison des chiffres.

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 signal s[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 δ[nm]. Since δ[nm] 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.

enter image description here

This can be mathematically written as

s[n]δ[nm]=s[m]δ[nm]
Repeating the same procedure with a different delay m gives
s[n]δ[nm]=s[m]δ[nm]

The value s[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.

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

In summary, the above equation states that s[n] can be written as a summation of scaled unit impulses, where each unit impulse δ[nm] has an amplitude s[m]. An example of such a summation is shown in Figure below.

enter image description here

Consider what happens when it is given as an input to an LTI system with an impulse response 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
la source