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.
image-processing
discrete-signals
convolution
Mayank Tiwari
la source
la source
Réponses:
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
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
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 :
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:
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)
où
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) ] L y(n)=L[ x(n) ]
et invariance temps / décalage
le système peut être réécrit comme
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)
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∗δ n n+0 n×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 .
la source
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 tx t . 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,
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,
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[time−1]+k2x(time−2)+b∗y[time−1]
la source
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 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.
la source