Convolució

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 ordinador, processament d'imatges i senyals, enginyeria de telecomunicació i equacions diferencials.

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 condensador per a obtenir el senyal de sortida (resposta del condensador a aquest senyal)

Definició matemàtica

Matemàticament es defineix de la següent manera:

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

A més a més, hi ha tres mètodes gràfics per resoldre les convolucions: el lineal, el de malles i el circular. La convolució de f i g es denota $f*g$, i es defineix com la integral del producte de les dues funcions després de reflectir-ne una respecte de l'eix Y i desplaçar-la una distància t, com es mostra a continuació:

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

El rang d'integració depèn 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-\tau )$ no implica una violació en el rang. Quan s'utilitzen aquests dominis periòdics la convolució a vegades es diu cíclica. També és possible estendre amb zeros els dominis. El nom utilitzat quan s'utilitza aquesta tècnica de dominis "zero-estesos" o bé els infinits és el de convolució lineal, especialment en el cas discret que es presenta també en aquest article. 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ó, és a dir:

$f[m]*g[m]=\sum _{n}{f[n]g[m-n]}\,$

Quan es multipliquen 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ó

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ó $g_{T}(t)$ és periòdica, amb un període de T, llavors les funcions, f, com ara f * $g_{T}(t)$ 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

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 dues 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].

Propietats

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

Commutativitat

$f*g=g*f\,$

Associativitat

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

Distributivitat

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

Associativitat amb multiplicació escalar

$a(f*g)=(af)*g=f*(ag)\,$

per a tot nombre complex o real $a$.

Regla de derivació

${\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ó

${\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.

Altres definicions

Matriu de convolució

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}}$

S'opera de la següent manera: ${\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}}$

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

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ó

En moltes situacions, convolucions discretes es poden convertir en convolucions circulars de manera que podem aplicar transformacions ràpides amb una determinada característica 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

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

$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

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 una à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 .$

Desconvolució

D'altra banda, s'anomena «desconvolució» la separació de dos senyals obtinguts a partir d'una convolució.

Aplicacions

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

• A enginyeria de telecomunicació i en altres disciplines, la sortida d'un sistema lineal (estacionari, invariable en el temps, o invariable en l'espai, el que es coneix com a Sistema LTI) és la convolució de l'entrada amb la resposta del sistema a un impuls determinat.
• Al processament digital d'imatges, la convolució és 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.
• 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. El terme fotogràfic d'aquest efecte és enfocament selectiu (bokeh).
• A l'acústica, un eco és la convolució del so original amb una funció que representi els objectes variats que el reflecteixin.
• A la física, on hi hagi un sistema lineal amb un "principi de superposició", apareix una operació de convolució.
• 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.
• Als sistemes de planificació de tractament per radioteràpia, gran part de tots els codis de càlcul moderns apliquen algorismes de convolució-superposició.
• La convolució amplifica o atenua cada component de freqüència de l'entrada de forma independent dels altres components.

Enllaços externs

• Informació sobre zero-padding. Arxivat 2009-05-17 a Wayback Machine.