Convolució

De Viquipèdia
Dreceres ràpides: navegació, cerca

La convolució és una operació matemàtica que transforma dues funcions en una tercera funció que representa la magnitud de superposició de les dues funcions originals. La seva operació es representa amb el símbol *. Les seves aplicacions inclouen estadística, visió per computador, processament d'imatges i senyals, enginyeria elèctrica i equacions diferencials. Matemàticament es defineix de la manera següent:

(f * g )(t)\ \ \,{=}\ \int_{-\infty}^{\infty} f(\tau)*g(t-\tau)\,d\tau

A més, tenim tres mètodes gràfics per resoldre les convolucions: el lineal, el de malles i el circular.


Convolució de dos Polsos Quadrats (La funció resultant acaba sent un Pols Triangular)
Convolució d'un Pols Quadrat (com a senyal d'entrada) amb la resposta l'impuls d'un capacitor per a obtenir el senyal de sortida (resposta del capacitor a aquest senyal)

La convolució de f i g es denota f*g, i es defineix com la integral del producte de les dos funcions després desplaçada una distància τ.

f (t) * g (t) = \int f(\tau) g(t - \tau) d\tau


El rang d'integració dependrà del domini sobre el que estan definides les funcions. En el cas d'un rang d'integració finit, f i g es consideren com a esteses, periòdicament en dues direccions, tal que el terme g(t-τ) no implica una violació en el rang. Quan utilitzem aquests dominis periòdics la convolució a vegades es diu cíclica. També és possible estendre amb zeros els dominis. El nombre utilitzat quan posem en joc aquests dominis "zero-estesos" o bé els infinits és el de convolució lineal, especialment en el cas discret que presentarem abaix. El resultat final de g(x) només serà determinat per la funció f(x) en el punt t, però no de la posició de t. Aquesta propietat s'anomena invariant respecte a la posició (position-invariant) i és una condició necessària en la definició d'integrals de convolució.


Si X i Y són dues variables aleatòries independents amb funcions de densitat de probabilitat f i g, respectivament, llavors la densitat de probabilitat de la suma X + Y vindrà donada per la convolució f * g.

Per les funcions discretes es pot utilitzar d'una manera discreta la convolució. Això és:

 f[m] * g[m] = \sum_n {f[n] g[m - n]} \,


Quan multipliquem dos polinomis, els coeficients del producte estan donats per la convolució de les successions originals de coeficients, en el sentit donat aquí (utilitzant extensions amb zeros com hem mencionat).

Generalitzant els casos anteriors, la convolució pot ser definida per qualssevol dues funcions quadrades-integrables definides sobre un grup topològic localment compacte. Una generalització diferent és la convolució de distribucions.

Tipus de Convolució[modifica | modifica el codi]

Convolució Discreta

Quan es tracta de fer un processament digital de senyal no té sentit parlar de convolucions aplicant estrictament la definició, ja que només disposem de valors en instants discrets de temps. Cal, doncs, una aproximació numèrica. Per a realitzar la convolució entre dos senyals, s'avaluarà l'àrea de la funció:  x(\tau)*h(t-\tau)\,. Per a això, disposem de mostrejos dels dos senyals en els instants de temps  nt \,, que anomenarem  x[k]\, y  h[n-k]\, (on n i k són enters). L'àrea és, per tant,

 y[n]=[\sum_{k=-\infty}^{\infty} t*x[k]*h[n-k]]=t*[\sum_{k=-\infty}^{\infty} x[k]*h[n-k]],

La convolució discreta es determina per un interval de mostreig  t=1  :

y[n]=x[n]*h[n]=[\sum_{k=-\infty}^{\infty} x[k]*h[n-k]]

Convolució Circular

Quan una funció GT és periòdica, amb un període de T, llavors les funcions, f, com ara f * GT existents, la seva convolució és també periòdica i igual a:

(f * g_T)(t) \equiv \int_{t_0}^{t_0+T} \left[\sum_{k=-\infty}^{\infty} f(\tau + kT)\right] g_T(t - \tau)\ d\tau,\,

On es tria arbitràriament. La suma és anomenada com una extensió periòdica de la funció f.

Si GT és una extensió periòdica d'una altra funció, g, llavors f * GT se sap que és circular, cíclica, o periòdica d'una convolució de fil g.

Mètode per calcular la convolució circular:

Tenim 2 cercles, un exterior i un altre interior. Anem girant el cercle interior i sumant els seus valors. Si els dos cercles tenen diferents mides, llavors el més petit hi afegim "0" a l'inici, al final o l'inici i final.

[L >= L1 + L2-1]

Convolució lineal[modifica | modifica el codi]

Consisteix a fer unes taules on en cada cas els membres de les dues funcions es troben desplaçats una posició, de manera que es comença amb les dos funcions compartint un sol membre, en la segona taula en comparteixen 2, i així anar fent fins que les dues funcions s'han desplaçat una sobre l'altra i tornen a compartir un sol membre. En cada taula es fa el producte entre els membres que coincideixen en la mateixa columna i se sumen els productes de les columnes. A continuació hi ha un exemple:

x[n] = [4 1 3]

y[n] = [2 5]

c[n] = y[n]*x[n]


[0 4 1 3] i [2 5 0 0], resultat = 5*4 = 20

[4 1 3] i [2 5 0], resultat = 5*1 + 2*4 = 13

[4 1 3] i [0 2 5], resultat = 5*3 + 2*1 = 17

[4 1 3 0] i [0 0 2 5], resultat = 2*3 = 6


El resultat final de la convolució és el següent:

c[n] = [20 13 17 6]

Ús[modifica | modifica el codi]

La convolució i les operacions relacionades es troben a moltes aplicacions d'enginyeria i matemàtiques.

  • A l'estadística, una mitjana mòbil ponderada és una convolució.
  • A la teoria de la probabilitat, la distribució de probabilitat de la suma de dues variables aleatòries independents és la convolució de cadascuna de les seves distribucions de probabilitat.
  • A l'òptica, molts tipus de "taques" es descriuen amb convolucions. Una ombra (per exemple, l'ombra sobre la taula quan tenim la mà entre aquesta i la font de llum) és la convolució de la forma de la font de llum que crea l'ombra i de l'objecte l'ombra del qual s'està projectant. Una fotografia desenfocada és la convolució de la imatge correcta amb el cercle borrós format pel diafragma de l'iris.
  • A l'acústica, un eco és la convolució del so original amb una funció que representi els objectes variats que el reflecteixin.
  • A enginyeria elèctrica i en altres disciplines, la sortida d'un sistema lineal (estacionari, invariable en el temps, o invariable en l'espai) és la convolució de l'entrada amb la resposta del sistema a un impuls determinat.
  • A la física, on hi hagi un sistema lineal amb un "principi de superposició", apareix una operació de convolució.

Propietats[modifica | modifica el codi]

Les propietats dels diferents operadors de convolució són 12

Commutativitat[modifica | modifica el codi]

f * g = g * f \,

Associativitat[modifica | modifica el codi]

f * (g * h) = (f * g) * h \,

Distributivitat[modifica | modifica el codi]

f * (g + h) = (f * g) + (f * h) \,

Associativitat amb multiplicació escalar[modifica | modifica el codi]

a (f * g) = (a f) * g = f * (a g) \,

per a tot nombre complex o real a.

Regla de derivació[modifica | modifica el codi]

\mathcal{D}(f * g) = \mathcal{D}f * g = f * \mathcal{D}g \,

on Df és la derivada de f o, en el cas discret, l'operador diferència

\mathcal{D}f(n) = f(n+1) - f(n).

Teorema de convolució[modifica | modifica el codi]

\mathcal{F}(f * g) ={(\mathcal{F} (f)) \cdot (\mathcal{F} (g))}

on \mathcal{F} és la Transformada de Fourier de f. Aquest teorema també es compleix amb la Transformada de Laplace.


Matriu de convolució[modifica | modifica el codi]

A vegades és útil veure la convolució com un producte matricial, sigui x[n] una funció discreta de n elements, sigui h[n] un sistema discret de n elements i sigui y la resposta a la convolució de (2*n)-1 elements, llavors y[m]=x[n] * h[n] es pot expressar pel següent producte matricial.



 \begin{bmatrix}
 x[0] \\
 x[1] \\
 x[2] \\
. \\
. \\
. \\
 x[n]
 \end{bmatrix}
 ^T



 \begin{bmatrix}
 h[0] & h[1] & h[2] & ... & h[n] & 0_k & ... & 0_2*n-1\\
 0 & h[0] & h[1] & h[2] & ... & h[n] & 0_k & ... & 0_2*n-2\\
 0 & 0 & h[0] & h[1] & h[2] & ... & h[n] & 0_k & ... & 0_2*n-3\\
. \\
. \\
. \\
 0 & 0 & ... & h[0] & h[1] & h[2] & ... & h[n] \\
 \end{bmatrix}
=
 \begin{bmatrix}
 y[0] \\
 y[1] \\
 y[2] \\
. \\
. \\
. \\
 y[2*n-1]
 \end{bmatrix}

exemple

sigui x[n]=  [4 5 1 7] i sigui h[n]=  [1 2 3 1]

llavors la matriu de convolució serà 
 \begin{bmatrix}
 1 & 2 & 3 & 1 & 0 & 0 & 0\\
 0 & 1 & 2 & 3 & 1 & 0 & 0\\ 
 0 & 0 & 1 & 2 & 3 & 1 & 0\\ 
 0 & 0 & 0 & 1 & 2 & 3 & 1\\ 
 \end{bmatrix}

  • Podem observar com s'afegeixen zeros a tots dos cantons. Això es fa per a poder igualar i així poder fer la convolució. Aquesta tècnica és coneguda com a zero-padding.

Zero Padding[modifica | modifica el codi]

Consisteix en afegir 0 a una convolució o a l'espectre d'un senyal, en aquest últim cas augmentem el domini freqüencial del senyal, però no es millora la resolució.

Algoritmes ràpids de convolució[modifica | modifica el codi]

En moltes situacions, convolucions discretes es poden convertir en convolucions circulars de manera que podem aplicar transformacions ràpides amb una determinada caràcteqistica de la convolució i implementar-ho al computador. Per exemple, la convolució de seqüències de dígits és el funcionament del nucli d'un computador en la multiplicació de nombres de diversos dígits, que per tant pot ser implementat de manera eficient amb les tècniques de transformació (Knuth 1997, § 4.3.3.C; von zur Gather i Gerhard 2003, § 8.2).

Convolucions de grups[modifica | modifica el codi]

Si G és un grup dotat d'una mesura m i si f i g són funcions reals -o complexes- valuades i m-integrables de G, llavors podem definir la seva convolució com:

(f * g)(x) = \int_G f(y)g(xy^{-1})\,dm(y) \,

En aquest cas també és possible donar, per exemple, un teorema de convolució, encara que sigui molt més difícil de presentar i que requereixi la teoria de la representació per a aquests tipus de grups així com el Teorema de Peter-Weyl de l'Anàlisi harmònica. És molt difícil fer aquests càlculs sense més estructura i els grups de Lie són els marcs on s'han de fer les coses.

Convolucions amb deltes de Dirac[modifica | modifica el codi]

 f(t) * \delta(t) = f(t) \,
 f(t) * \delta(t-to) = f(t-to) \,
 f(t-t1) * \delta(t-to) = f(t-to-t1) \,

Bialgebra[modifica | modifica el codi]

Sigui (X, Δ, ∇, εη) una bialgebra amb comultiplicatió Δ, multiplicació ∇, unitat η, i counitat ε. La convolució és un producte definit en l'endomorfisme algebraic End(X). Sigui φ, ψ ∈ End(X), això és, φ,ψ : X → X són funcions que respecten tota 'estructura algebraica de X, llavors la convolució φ∗ψ és definida com una composició.

X \xrightarrow{\Delta} X\otimes X \xrightarrow{\phi\otimes\psi} X\otimes X \xrightarrow{\nabla} X. \,

La convolució apareix sobretot en la definició de l'àlgebra de Hopf (Kassel 1995, §III.3). Un biàlgebra és un àlgebra de Hopf si i només si té un antípoda: un endomorfisme a S de manera que:

S * \operatorname{id}_X = \operatorname{id}_X * S = \eta\circ\varepsilon.

Aplicacions[modifica | modifica el codi]

La convolució i les operacions relacionades es troben en moltes aplicacions en enginyeria i matemàtica:

  • Enginyeria elèctrica: La convolució d'una funció (l'entrada) amb una segona funció (la resposta a l'impuls) dóna la sortida d'un sistema invariant en el temps (Sistema LTI). En un moment donat, la sortida es un efecte acumulat de tots els valors anteriors de la funció d'entrada.
  • En processament digital d'imatges, la convolució es un dels algorismes més importants alhora de tractar les imatges. Millora del contrast, millora de la resolució, detecció de vores, són alguns dels processos afins que mitjançant "filtres" utilitzem més freqüentment.
  • En Òptica, molts tipus de "difuminats" es poden descriure amb convolucions. Una ombra (p. ex., l'ombra a la taula quan es posa la mà entre la taula i el llum) es la convolució de la forma del llum que projecta l'ombra i l'objecte l'ombra del qual és projectada. Una fotografía desenfocada és la convolució de la imatge enfocada amb la forma de l'iris del diafragma. El terme fotogràfic d'aquest efecte és enfocament selectiu (bokeh).
  • En l'acústica lineal, un ressò és la convolució del so original amb una funció de representació dels diversos objectes que ho estan reflectint.
  • En física, sempre que hi hagi un sistema lineal amb un principi de superposició, una operació de convolució fa una aparició.
  • En estadística, com un mitjana mòbil ponderada.
  • En teoria de la probabilitat, la distribució de probabilitat de la suma de dos variables aleatòries independents es la convolució de cadascuna de les seves distribucions de probabilitat.
  • La convolució amplifica o atenua cada component de freqüència de l'entrada de forma independent dels altres components.
  • En els sistemes de planificació de tractament per radioteràpia, gran part de tots els codis de càlcul moderns apliquen algorismes de convolució-superposició.

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Convolució Modifica l'enllaç a Wikidata