¿Por qué se requiere convolución, o cuál es la filosofía detrás de la convolución?

14

Estoy trabajando en el campo de la restauración de imágenes digitales. He leído todas las cosas sobre convolución, que, para un sistema LTI , si conocemos su respuesta al impulso , entonces podemos encontrar su salida simplemente usando la convolución entre la entrada y la respuesta al impulso.

¿Alguien puede decirme cuál es la filosofía matemática principal detrás de esto? Su experiencia con mí me dirá más que solo navegar por Internet al respecto.

Mayank Tiwari
fuente
3
Estoy rechazando esta pregunta porque (o pequeñas variaciones de la misma) se ha preguntado y respondido repetidamente en este sitio, como dicen los comentarios de pichenettes. En su lugar, debería haber "navegado por Internet" en este sitio.
Dilip Sarwate

Respuestas:

13

La idea de convolución

Mi exposición favorita del tema está en una de las conferencias de Brad Osgood sobre la Transformada de Fourier . La discusión sobre la convolución comienza alrededor de las 36:00, pero toda la conferencia tiene un contexto adicional que vale la pena ver.

La idea básica es que, cuando define algo como la Transformada de Fourier, en lugar de trabajar directamente con la definición todo el tiempo, es útil derivar propiedades de nivel superior que simplifiquen los cálculos. Por ejemplo, una de esas propiedades es que la transformación de la suma de dos funciones es igual a la suma de las transformaciones, es decir

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

Eso significa que si tiene una función con una transformación desconocida, y puede descomponerse como una suma de funciones con transformaciones conocidas, básicamente obtendrá la respuesta de forma gratuita.

Ahora, dado que tenemos una identidad para la suma de dos transformadas, es una pregunta natural preguntar cuál es la identidad para el producto de dos transformadas, es decir

F{f}F{g}= ?.

Resulta que cuando calcula la respuesta, la convolución es lo que aparece. Toda la derivación se da en el video, y dado que su pregunta es principalmente conceptual, no la resumiré aquí.

La implicación de acercarse a la convolución de esta manera es que es una parte intrínseca de la forma en que la Transformada de Laplace (de la cual la Transformada de Fourier es un caso especial) convierte ecuaciones diferenciales ordinarias de coeficiente constante lineal (LCCODE) en ecuaciones algebraicas. El hecho de que dicha transformación esté disponible para hacer que LCCODE sea analíticamente manejable es una gran parte de la razón por la que se estudian en el procesamiento de señales. Por ejemplo, para citar a Oppenheim y Schafer :

Debido a que son relativamente fáciles de caracterizar matemáticamente y porque pueden diseñarse para realizar funciones útiles de procesamiento de señales, la clase de sistemas lineales invariantes de desplazamiento se estudiará ampliamente.

Entonces, una respuesta a la pregunta es que si está utilizando métodos de transformación para analizar y / o sintetizar sistemas LTI, tarde o temprano, surgirá una convolución (ya sea implícita o explícitamente). Tenga en cuenta que este enfoque para introducir convolución es muy estándar en el contexto de ecuaciones diferenciales. Por ejemplo, vea esta conferencia MIT de Arthur Mattuck . La mayoría de las presentaciones presentan la integral de convolución sin comentarios, luego derivan sus propiedades (es decir, la sacan de un sombrero), o hablan sobre la extraña forma de la integral, hablan de voltearse y arrastrarse, inversión de tiempo, etc., etc. .

La razón por la que me gusta el enfoque del profesor Osgood es que evita todo ese tsouris, además de proporcionar, en mi opinión, una visión profunda de cómo los matemáticos probablemente llegaron a la idea en primer lugar. Y cito:

Dije: "¿Hay alguna forma de combinar F y G en el dominio del tiempo, de modo que en el dominio de la frecuencia se multipliquen los espectros y se multipliquen las transformadas de Fourier?" Y la respuesta es sí, por esta integral complicada. No es tan obvio. No saldrías de la cama por la mañana y escribirías esto, y esperarías que esto resolvería ese problema. ¿Cómo lo conseguimos? Usted dijo, suponga que el problema está resuelto, vea qué tiene que suceder, y luego tendríamos que reconocer cuándo es el momento de declarar la victoria. Y es hora de declarar la victoria.

Ahora, siendo un matemático desagradable, cubres tus huellas y dices: "Bueno, simplemente voy a definir la convolución de dos funciones con esta fórmula".

Sistemas LTI

En la mayoría de los textos DSP, la convolución generalmente se introduce de una manera diferente (que evita cualquier referencia a los métodos de transformación). Al expresar una señal de entrada arbitraria como una suma de impulsos unitarios escalados y desplazados,x(n)

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

dónde

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

Las propiedades definitorias de los sistemas lineales invariantes en el tiempo conducen directamente a una suma de convolución que involucra la respuesta al impulso . Si el sistema definido por un operador LTI L se expresa como y ( n ) = L [ x ( n ) ] , entonces aplicando las propiedades respectivas, es decir, linealidadh(norte)=L[ δ(norte) ]Ly(norte)=L[ X(norte) ]

(3)L[ unX1(norte)+siX2(norte) ]Transformación de la suma de entradas escaladas=unL[ X1(norte) ]+siL[ X2(norte) ]Suma de transformaciones escaladas,

e invariancia de tiempo / turno

(4)L[ X(norte) ]=y(norte) implicaL[ X(norte-k) ]=y(norte-k),

el sistema puede reescribirse como

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

Esa es una forma muy estándar de presentar convolución, y es una forma perfectamente elegante y útil de hacerlo. Se pueden encontrar derivaciones similares en Oppenheim y Schafer , Proakis y Manolakis , Rabiner y Gold , y estoy seguro de que muchos otros. Dilip da una idea más profunda [que va más allá de las presentaciones estándar] en su excelente respuesta aquí .

Tenga en cuenta, sin embargo, que esta derivación es algo así como un truco de magia. Echando otro vistazo a cómo se descompone la señal en , podemos ver que ya está en forma de convolución. Si(1)

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

entonces es solo x δ . Debido a que la función delta es el elemento de identidad para la convolución, decir que cualquier señal puede expresarse de esa forma es muy parecido a decir que cualquier número n puede expresarse como n + 0 o n × 1 . Ahora, elegir describir las señales de esa manera es brillante porque conduce directamente a la idea de una respuesta al impulso; es solo que la idea de convolución ya está "incorporada" a la descomposición de la señal.(1)xδnn+0n×1

Desde esta perspectiva, la convolución está intrínsecamente relacionada con la idea de una función delta (es decir, es una operación binaria que tiene la función delta como elemento de identidad). Incluso sin considerar su relación con la convolución, la descripción de la señal depende de manera crucial de la idea de la función delta. Entonces, la pregunta es, ¿de dónde surgió la idea de la función delta en primer lugar? Por lo que puedo decir, se remonta al menos al documento de Fourier sobre la teoría analítica del calor, donde aparece implícitamente. Una fuente de información adicional es este documento sobre Origen e Historia de la Convolución de Alejandro Domínguez.

Ahora, esos son los dos enfoques principales de la idea en el contexto de la teoría de sistemas lineales. Uno favorece la comprensión analítica y el otro favorece la solución numérica. Creo que ambos son útiles para tener una idea completa de la importancia de la convolución. Sin embargo, en el caso discreto, descuidando completamente los sistemas lineales, hay un sentido en el que la convolución es una idea mucho más antigua.

Multiplicación polinómica

Gilbert Strang da una buena presentación de la idea de que la convolución discreta es solo una multiplicación polinómica en esta conferencia que comienza alrededor de las 5:46. Desde esa perspectiva, la idea se remonta a la introducción de sistemas de números posicionales (que representan los números implícitamente como polinomios). Debido a que la transformación Z representa señales como polinomios en z, la convolución también surgirá en ese contexto, incluso si la transformación Z se define formalmente como un operador de retardo sin recurrir a análisis complejos y / o como un caso especial de Laplace transformar .

Datageist
fuente
gracias señor por su invaluable orientación, me acaba de mostrar el camino correcto a seguir. Tu ayuda me ha enseñado que cómo ser un buen ser humano comienza para los demás ... :)
Mayank Tiwari
¿Cómo explica esta gran coincidencia que necesitas hacer la convolución en el caso que se te pide? Creo que en cada dominio, hay una operación que se convierte en convolución cuando reviertes los argumentos en el dominio del tiempo. ¿Podríamos tener que hacer una multiplicación en el dominio del tiempo para obtener la respuesta? ¿Por qué deberíamos multiplicar las frecuencias en lugar de los barridos de tiempo?
Val
1
Teniendo en cuenta que el OP ya había formulado una pregunta sobre el papel de los impulsos en relación con los sistemas LTI , leí la pregunta mientras él la usaba como un ejemplo para motivar una pregunta sobre el origen de la convolución, no necesariamente su papel en el cálculo de un impulso. respuesta per se. ¿Es eso lo que estás preguntando?
Datageist
1
Decir que necesitamos convolución porque es idéntico a la multiplicación de Fourier me parece una tontería en caso de que no sepamos por qué necesitamos la multiplicación de Fourier. Cuando se nos da la respuesta al impulso, esto significa dominio del tiempo y convolución en lugar de cualquier magia negra en base a Fourier. No creo que esa referencia a esa pregunta pueda aclarar esto. En cualquier caso, no es bueno dar "respuestas localizadas" a preguntas generales, fundamentales (es decir, filosóficas). Las preguntas y respuestas deben ser útiles para futuros visitantes.
Val
El comentario anterior de Val está justo en el blanco. Me pregunto cómo funcionaban los sistemas lineales antes de que se inventaran / descubrieran las transformadas de Fourier. ¿Cómo demonios un objeto inanimado no sensible descubrió una fórmula tan complicada?
Dilip Sarwate
6

Una vez di la respuesta en la página de discusión sobre convolución de Wikipedia, que básicamente hacía la misma pregunta: ¿Por qué la inversión de tiempo? . La filosofía es que aplique un pulso único en el tiempo 0 a su filtro y registre su respuesta en el tiempo 0,1,2,3,4,…. Básicamente, la respuesta se verá como una función, h (t). Puedes trazarlo. Si el pulso era n veces más alto / más alto, los pulsos de respuesta serán proporcionalmente más altos (esto se debe a que siempre se supone un filtro lineal). Ahora, todo DSP (y no solo DSP) se trata de lo que sucede cuando aplica el filtro a su señal. Conoces la respuesta al impulso. Su señal (especialmente digital) no es más que una serie de pulsos de altura x (t). Tiene altura / valor en el tiempo txt. Los sistemas lineales son geniales porque puede sumar las salidas para cada pulso de entrada para obtener la función de respuesta y (t) para la función de entrada x (t). Usted sabe que el pulso de salida y (t = 10) depende de la entrada inmediata x (10), que contribuye h (0) * x (10). Pero también hay una contribución, x (9) * h (1), a la salida del pulso anterior, x (9), y contribuciones de valores de entrada incluso anteriores. Verá, a medida que agrega contribuciones de entradas anteriores, el argumento de una vez disminuye mientras que el otro aumenta. Usted MAC todas las contribuciones en Y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) + ..., que es una convolución.

Puede pensar en las funciones y (t), h (t) yx (t) como vectores. Las matrices son operadores en el álgebra lineal. Toman el vector de entrada (una serie de números) y producen el vector de salida (otra serie de números). En este caso, y es un producto de matriz de convolución con el vector x,

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

Ahora, debido a que la convolución es una matriz de Toeplitz , tiene una base propia de Fourier y, por lo tanto, el operador de convolución (los operadores lineales están representados por matrices, pero la matriz también depende de la base) es una buena matriz diagonal en el dominio de Fourier,

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

Tenga en cuenta, muchos más ceros y, por lo tanto, un cálculo mucho más simple. Este resultado se conoce como "teorema de convolución" y, como respondió la primera respuesta, es mucho más simple en el dominio de Fourier. Pero, esta es la filosofía detrás del "teorema de convolución", la base de Fourier y los operadores lineales en lugar de la necesidad ubicua de convolución.

Normalmente, haces convolución porque tienes tu señal de entrada, respuesta de impulso y requieres salida en el dominio del tiempo. Puede transformarse en un espacio de Fourier para optimizar la computación. Pero, no es práctico para filtros simples, como he visto en la DSPGuide . Si su filtro se ve como , no tiene sentido transformar Fourier. Simplemente haces n multiplicaciones, para calcular cada y. También es natural en tiempo real. En tiempo real, calcula solo una y a la vez. Puede pensar en la transformada de Fourier si tiene su señal x grabada y necesita calcular todo el vector y a la vez. Esto necesitaría operaciones MAC de NxN y Fourier puede ayudar a reducirlas a N log (N).y[currentTime]=k1x[time1]+k2x(time2)+by[time1]

Val
fuente
Un par de notas: ¿cómo ampliaría esta descripción para el caso de tiempo continuo (que obviamente vino antes del caso de tiempo discreto)? Además, hay muchas aplicaciones en tiempo real que utilizan métodos basados ​​en transformadas de Fourier para una convolución rápida. Decir que las salidas siempre se calculan de una en una para aplicaciones en tiempo real simplemente no es cierto.
Jason R
Dicho esto, un buen trabajo señalando el hecho de que la estructura Toeplitz de la matriz de convolución implica que admite una representación diagonal bajo una base de Fourier.
Jason R
Sí, puede usar transfrom de fourier en tiempo real. Estoy lejos de ser un experto en DSP. Acabo de expresar la idea (que obtuve de mi escasa práctica y leyendo DSPGuide). De todos modos, quiero resaltar que Fourier no tiene nada que ver con la filosofía de convolución. Es posible que necesite eliminar toda la discusión relacionada con Fourier, ya que es una distracción. La convolución es natural en el dominio del tiempo y se necesita sin Fourier, no importa cuán genial sea el Fourier.
Val
F(X)reXF(X)reX=limreX0 0(F(X)reX)
@JasonR En la configuración continua, reemplazaría la matriz de Toeplitz por un operador invariante de desplazamiento. Luego puede mostrar que las funciones básicas de Fourier diagonalizan este operador.
lp251
3

Aunque las respuestas anteriores han sido realmente buenas, me gustaría agregar mi punto de vista sobre la convolución donde simplemente hago que sea más fácil de visualizar debido a las figuras.

Uno se pregunta si existe algún método a través del cual se pueda determinar una señal de salida de un sistema para una señal de entrada dada. La convolución es la respuesta a esa pregunta, siempre que el sistema sea lineal e invariante en el tiempo (LTI).

s[norte]s[norte]s[norte]metroδ[norte-metro]δ[norte-metro]norte=metros[norte]nortemetronortemetronorte=metros[metro]

ingrese la descripción de la imagen aquí

s[norte]δ[norte-metro]=s[metro]δ[norte-metro]
metro
s[norte]δ[norte-metro]=s[metro]δ[norte-metro]

s[metro]-<metro<s[norte]

s[norte]=+s[-2]δ[norte+2]+s[-1]δ[norte+1]+s[0 0]δ[norte]+s[1]δ[norte-1]+s[2]δ[norte-2]+=metro=-s[metro]δ[norte-metro]

s[norte]δ[norte-metro]s[metro]

ingrese la descripción de la imagen aquí

h[norte]

ingrese la descripción de la imagen aquí

Esto conduce a una secuencia de entrada-salida como

ingrese la descripción de la imagen aquí

r[norte]s[norte]h[norte]

La convolución es un proceso muy lógico y simple, pero muchos estudiantes de DSP pueden encontrarla confusa debido a la forma en que se explica. Describiremos un método convencional y otro enfoque más intuitivo.

Método convencional


norte

r[norte]=metro=-s[metro]h[-metro+norte]metroh[metro]metro=0 0h[-metro]

h[-metro+norte]norteh[-metro]nortenortenorte

s[metro]h[-metro+norte]s[metro]h[-metro+norte]

norte

norte

s[norte]=[2-11]h[norte]=[-112]r[norte]norte

s[norte]h[norte]nortemetronorteh[-metro]s[metro]r[norte] es una función del índice de tiempo norte, que fue ese cambio aplicado a h[-metro].

ingrese la descripción de la imagen aquí

A continuación, pasamos al método más intuitivo donde no se requiere voltear una señal.

Método intuitivo


Hay otro método para entender la convolución. De hecho, se basa en la derivación de la ecuación de convolución, es decir, encontrar la salidar[norte] como

r[norte] = +s[-2]h[norte+2] +s[-1]h[norte+1] +s[0 0]h[norte] + s[1]h[norte-1] + s[2]h[norte-2] +
Resolvamos el mismo ejemplo que en la figura anterior, donde s[norte]=[2- 11] y h[norte]=[-112]. Esto se muestra en la tabla a continuación.

ingrese la descripción de la imagen aquí

Tal método se ilustra en la Figura a continuación. Desde el punto de vista de la implementación, no hay diferencia entre ambos métodos.

ingrese la descripción de la imagen aquí

En resumen, la convolución nos dice cómo se comporta un sistema LTI en respuesta a una entrada particular y, gracias al método intuitivo anterior, podemos decir que la convolución también es multiplicación en el dominio del tiempo (y no es necesario cambiar la señal), excepto el hecho de que Esta vez, la multiplicación del dominio implica memoria. Para comprender mejor a un nivel mucho más profundo de dónde proviene el volteo y lo que sucede en el dominio de la frecuencia, puede descargar una sección de muestra de mi libro aquí .

Qasim Chaudhari
fuente