Por que convolução é necessária ou qual é a filosofia por trás da convolução?

14

Estou trabalhando no campo de restauração de imagens digitais. Li todas as coisas sobre convolução, que, para um sistema de LTI , se conhecemos sua resposta ao impulso , podemos encontrar sua saída usando apenas convolução entre entrada e resposta ao impulso.

Alguém pode me dizer que qual é a principal filosofia matemática por trás disso? Sua experiência com me dirá mais do que apenas navegar na Internet sobre isso.

Mayank Tiwari
fonte
3
Estou votando negativamente nesta pergunta porque ela (ou pequenas variações dela) foi repetidamente solicitada e respondida neste site como afirma o comentário de pichenettes. Você deveria ter "navegado na Internet" neste site.
precisa

Respostas:

13

A idéia de convolução

Minha exposição favorita do tópico está em uma das palestras de Brad Osgood sobre a Transformada de Fourier . A discussão sobre convolução começa por volta das 36:00, mas toda a palestra tem um contexto adicional que vale a pena assistir.

A idéia básica é que, quando você define algo como a Transformada de Fourier, em vez de trabalhar diretamente com a definição o tempo todo, é útil derivar propriedades de nível superior que simplificam os cálculos. Por exemplo, uma dessas propriedades é que a transformação da soma de duas funções é igual à soma das transformações, ou seja,

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

Isso significa que, se você possui uma função com uma transformação desconhecida e ela pode ser decomposta como uma soma de funções com transformações conhecidas, basicamente você obtém a resposta gratuitamente.

Agora, como temos uma identidade para a soma de duas transformações, é uma pergunta natural perguntar qual é a identidade para o produto de duas transformadas, ou seja,

F{f}F{g}= ?.

Acontece que, quando você calcula a resposta, convolução é o que aparece. Toda a derivação é dada no vídeo e, como sua pergunta é principalmente conceitual, não recapitularei aqui.

A implicação de abordar a convolução dessa maneira é que é uma parte intrínseca do modo como a Transformada de Laplace (da qual a Transformação de Fourier é um caso especial) transforma equações diferenciais ordinárias lineares de coeficiente constante linear (LCCODE) em equações algébricas. O fato de essa transformação estar disponível para tornar o LCCODE analisável analiticamente é uma grande parte do motivo pelo qual eles são estudados no processamento de sinais. Por exemplo, para citar Oppenheim e Schafer :

Por serem relativamente fáceis de caracterizar matematicamente e por poderem ser projetados para executar funções úteis de processamento de sinal, a classe de sistemas lineares invariantes a deslocamento será estudada extensivamente.

Portanto, uma resposta para a pergunta é que, se você estiver usando métodos de transformação para analisar e / ou sintetizar sistemas de LTI, mais cedo ou mais tarde, a convolução surgirá (implícita ou explicitamente). Observe que essa abordagem para introduzir convolução é muito padrão no contexto de equações diferenciais. Por exemplo, veja esta palestra do MIT de Arthur Mattuck . A maioria das apresentações apresenta a integral de convolução sem comentários e, em seguida, obtém suas propriedades (ou seja, tira-a do chapéu), ou bainha e fala sobre a forma estranha da integral, fala sobre virar e arrastar, inversão de tempo etc. etc. .

A razão pela qual eu gosto da abordagem do Prof. Osgood é que ela evita tudo o que é tsouris, além de fornecer, na minha opinião, uma profunda compreensão de como os matemáticos provavelmente chegaram à idéia em primeiro lugar. E cito:

Eu disse: "Existe uma maneira de combinar F e G no domínio do tempo, de modo que no domínio da frequência os espectros se multipliquem, as transformadas de Fourier se multipliquem?" E a resposta é sim, existe essa integral complicada. Não é tão óbvio. Você não sairia da cama de manhã e escreveria isso, e esperaria que isso resolvesse esse problema. Como conseguimos isso? Você disse, suponha que o problema esteja resolvido, veja o que deve acontecer e, então, teremos que reconhecer quando for a hora de declarar vitória. E é hora de declarar vitória.

Agora, sendo um matemático desagradável, você cobre suas trilhas e diz: "Bem, eu simplesmente vou definir a convolução de duas funções por essa fórmula".

Sistemas LTI

Na maioria dos textos DSP, a convolução é geralmente introduzida de uma maneira diferente (que evita qualquer referência para transformar métodos). Ao expressar um sinal de entrada arbitrário como uma soma dos impulsos unitários dimensionados e deslocados,x(n)

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

Onde

2)δ(n)={0 0,n0 01,n=0 0,

as propriedades definidoras dos sistemas lineares invariantes no tempo levam diretamente a uma soma de convolução envolvendo a resposta ao impulso . Se o sistema definido por um operador LTI L for expresso como y ( n ) = L [ x ( n ) ] , aplique as propriedades respectivas, a saber linearidadeh(n)=eu[ δ(n) ]euy(n)=eu[ x(n) ]

(3)eu[ umax1(n)+bx2(n) ]Transformação da soma de entradas escalonadas=umaeu[ x1(n) ]+beu[ x2(n) ]Soma das transformações em escala,

e invariância de tempo / turno

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

o sistema pode ser reescrito como

y(n)=eu[k=-x(k)δ(n-k)]Transformação da soma das entradas em escala=k=-x(k)eu[δ(n-k)]Soma das transformações em escala=k=-x(k)h(n-k).Convolução com a resposta ao impulso

Essa é uma maneira muito padrão de apresentar a convolução e é uma maneira perfeitamente elegante e útil de fazer isso. Derivações semelhantes podem ser encontradas em Oppenheim e Schafer , Proakis e Manolakis , Rabiner e Gold , e tenho certeza de muitas outras. Uma visão mais profunda [que vai além das introduções padrão] é dada por Dilip em sua excelente resposta aqui .

Note, no entanto, que essa derivação é um truque de mágica. Examinando novamente como o sinal é decomposto em , podemos ver que ele já está na forma de uma convolução. E se(1)

(fg)(n)f convolvido com g=k=-f(k)g(n-k),

então é apenas x δ . Como a função delta é o elemento de identidade da convolução, dizer que qualquer sinal pode ser expresso dessa forma é muito parecido com dizer que qualquer número n pode ser expresso como n + 0 ou n × 1 . Agora, escolher descrever os sinais dessa maneira é brilhante porque leva diretamente à idéia de uma resposta de impulso - é apenas que a idéia de convolução já está "inserida" na decomposição do sinal.(1)xδnn+0 0n×1

Nessa perspectiva, a convolução está intrinsecamente relacionada à idéia de uma função delta (ou seja, é uma operação binária que tem a função delta como seu elemento de identidade). Mesmo sem considerar sua relação com a convolução, a descrição do sinal depende crucialmente da idéia da função delta. Então, a pergunta torna-se: de onde tiramos a ideia da função delta em primeiro lugar? Tanto quanto posso dizer, remonta pelo menos ao artigo de Fourier sobre a Teoria Analítica do Calor, onde aparece implicitamente. Uma fonte para mais informações é este artigo sobre Origem e História da Convolução, de Alejandro Domínguez.

Agora, essas são as duas principais abordagens da idéia no contexto da teoria de sistemas lineares. Um favorece o insight analítico e o outro favorece a solução numérica. Penso que ambos são úteis para uma imagem completa da importância da convolução. No entanto, no caso discreto, negligenciando inteiramente os sistemas lineares, existe um sentido em que convolução é uma ideia muito mais antiga.

Multiplicação polinomial

Uma boa apresentação da idéia de que convolução discreta é apenas multiplicação polinomial é dada por Gilbert Strang nesta palestra a partir das 5:46. A partir dessa perspectiva, a idéia remonta à introdução de sistemas de números posicionais (que representam números implicitamente como polinômios). Como a transformação Z representa sinais como polinômios em z, a convolução também ocorrerá nesse contexto - mesmo se a transformação Z for definida formalmente como um operador de atraso sem recorrer a análises complexas e / ou como um caso especial da Laplace. Transformar .

datagrama
fonte
obrigado senhor por sua orientação inestimável, você acabou de me mostrar o caminho certo a seguir. Seu esta ajuda ensinou-me que como ser começar um bom humano para os outros .... :)
Mayank Tiwari
Como essa grande coincidência explica que você precisa fazer a convolução no caso solicitado? Acredito que em todos os domínios, há uma operação que se transforma em convolução quando você reverte os argumentos no domínio do tempo. Talvez seja necessário executar a duplicação no domínio do tempo para obter a resposta? Por que devemos multiplicar as frequências em vez de varreduras de tempo?
Val
1
Considerando que o OP já havia feito uma pergunta sobre o papel dos impulsos em relação aos sistemas de LTI , li a pergunta enquanto ele usava isso como exemplo para motivar uma pergunta sobre a origem da convolução - não necessariamente seu papel no cálculo de um impulso resposta em si. É isso que você está perguntando?
datageist
1
Dizer que precisamos de convolução porque é idêntico à multiplicação de Fourier me parece absurdo, caso não saibamos por que precisamos da multiplicação de Fourier. Quando nos é dada a resposta ao impulso, isso significa domínio e convolução do tempo, em vez de qualquer magia negra em bases quadriênicas. Não creio que a referência a essa pergunta possa esclarecer isso. De qualquer forma, não é bom dar "respostas localizadas" a perguntas gerais, fundamentais (isto é, filosóficas). As perguntas e respostas devem ser úteis para futuros visitantes.
Val
O comentário de Val acima está bem no alvo. Eu me pergunto como os sistemas lineares funcionaram antes que as transformações de Fourier fossem inventadas / descobertas. Como diabos um objeto inanimado não senciente descobriu uma fórmula tão complicada?
precisa
6

Eu uma vez deu a resposta em Wikipedia página convolução discussão, que pediu basicamente a mesma pergunta: Por que a inversão do tempo? . A filosofia é que você aplique um único pulso no tempo 0 ao seu filtro e registre sua resposta no tempo 0,1,2,3,4,…. Basicamente, a resposta parecerá uma função, h (t). Você pode traçar isso. Se o pulso for n vezes mais alto / alto, os pulsos de resposta serão proporcionalmente mais altos (isso ocorre porque o filtro linear é sempre assumido). Agora, todo DSP (e não apenas DSP) é sobre o que acontece quando você aplica o filtro ao seu sinal? Você conhece a resposta ao impulso. Seu sinal (especialmente digital) nada mais é do que uma série de pulsos de altura x (t). Possui altura / valor no momento txt. Sistemas lineares são legais que você pode somar as saídas para cada pulso de entrada para obter a função de resposta y (t) para a função de entrada x (t). Você sabe que o pulso de saída y (t = 10) depende da entrada imediata x (10), o que contribui com h (0) * x (10). Mas também há contribuição, x (9) * h (1), para a saída do pulso anterior, x (9) e contribuições de valores de entrada ainda mais antigos. Veja que, ao adicionar contribuições de entradas anteriores, um argumento de tempo diminui enquanto outro aumenta. Você MAC todas as contribuições em y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) +…, que é uma convolução.

Você pode pensar nas funções y (t), h (t) e x (t) como vetores. Matrizes são operadores na álgebra linear. Eles pegam o vetor de entrada (uma série de números) e produzem o vetor de saída (outra série de números). Nesse caso, y é um produto da matriz de convolução com o vetor x,

y=[y0 0y1y2]=[h0 00 00 0h1h0 00 0h2h1h0 0][x0 0x1x2]=Hx

Agora, como a convolução é uma matriz de Toeplitz , ela tem base própria de Fourier e, portanto, operador de convolução (operadores lineares são representados por matrizes, mas a matriz também depende da base) é uma boa matriz diagonal no domínio de Fourier,

Y=[Y0 0Y1Y2]=[λ0 00 00 00 0λ10 00 00 0λ2][X0 0X1X2]=dEuumag(H)X

Observe muito mais zeros e, portanto, computação muito mais simples. Esse resultado é conhecido como "teorema da convolução" e, como a primeira resposta foi respondida, é muito mais simples no domínio de Fourier. Mas isso é filosofia por trás do "teorema da convolução", base de Fourier e operadores lineares, em vez da necessidade onipresente de convolução.

Normalmente, você realiza a convolução porque possui seu sinal de entrada, resposta ao impulso e requer saída no domínio do tempo. Você pode se transformar em espaço de quatro camadas para otimizar a computação. Mas, não é prático para filtros simples, como já vi no DSPGuide . Se a sua aparência de filtro como , não faz sentido transformar Fourier. Você apenas faz n multiplicações, para calcular todos os y. Também é natural em tempo real. Em tempo real, você calcula apenas um ano de cada vez. Você pode pensar na transformação de Fourier se tiver seu sinal x gravado e precisar calcular todo o vetor y de uma só vez. Isso exigiria operações NxN MAC e Fourier pode ajudar a reduzi-las para N log (N).y[cvocêrrentTEume]=k1x[tEume-1]+k2x(tEume-2)+by[tEume-1]

Val
fonte
Algumas notas: como você estenderia essa descrição para o caso de tempo contínuo (que obviamente veio antes do caso de tempo discreto)? Além disso, existem muitos aplicativos em tempo real que usam métodos baseados na transformação de Fourier para rápida convolução. Dizer que as saídas são sempre calculadas uma de cada vez para aplicativos em tempo real simplesmente não é verdade.
Jason R
Dito isto, um bom trabalho salientando o fato de que a estrutura Toeplitz da matriz de convolução implica que ela admita uma representação diagonal sob uma base de Fourier.
Jason R
Sim, você pode usar o transfrom fourier em tempo real. Estou longe de ser especialista em DSP. Acabei de expressar a ideia (que recebi da minha prática escassa e da leitura do DSPGuide). De qualquer forma, quero destacar que fourier não tem nada a ver com a filosofia da convolução. Talvez eu precise remover toda a discussão relacionada a fourier, pois é uma distração. A convolução é natural no domínio do tempo e é necessária sem nenhum Fourier, não importa o quão legal o Fourier seja.
Val
O fato de o caso de tempo contínuo ter sido apresentado historicamente não exige que aprendamos na mesma ordem. Eu acho que é mais fácil entender a filosofia de muitas coisas, incluindo a convolução, começando com o caso discreto (e estamos no D SP.se para adotar essa abordagem). Em casos contínuos, uma série de operações MAC é transformada em integração, à medida que diminuímos nossos pulsos. BTW, a própria integração é entendida como um caso limite do somatório discreto: f ( x ) d x = lim d x 0 ( f(x)dx . Portanto, não pode vir antes da soma discreta. f(x)dx=limdx0 0(f(x)dx)
Val
@JasonR Na configuração contínua, você substituiria a matriz Toeplitz por um operador invariável por turno. Você pode mostrar que as funções básicas de Fourier diagonalizam esse operador.
lp251
3

Embora as respostas anteriores tenham sido realmente boas, gostaria de acrescentar meu ponto de vista sobre convolução, onde apenas facilito a visualização devido às figuras.

Perguntamos se existe algum método pelo qual um sinal de saída de um sistema possa ser determinado para um determinado sinal de entrada. Convolução é a resposta para essa pergunta, desde que o sistema seja linear e invariável no tempo (LTI).

s[n]s[n]s[n]mδ[n-m]δ[n-m]n=ms[n]nmnmn=ms[m]

insira a descrição da imagem aqui

s[n]δ[n-m]=s[m]δ[n-m]
m
s[n]δ[n-m]=s[m]δ[n-m]

s[m]-<m<s[n]

s[n]=+s[-2]δ[n+2]+s[-1]δ[n+1]+s[0 0]δ[n]+s[1]δ[n-1]+s[2]δ[n-2]+=m=-s[m]δ[n-m]

s[n]δ[n-m]s[m]

insira a descrição da imagem aqui

h[n]

insira a descrição da imagem aqui

Isso leva a uma sequência de entrada-saída como

insira a descrição da imagem aqui

r[n]s[n]h[n]

A convolução é um processo muito lógico e simples, mas muitos alunos de DSP podem achar confuso devido à maneira como é explicada. Vamos descrever um método convencional e outra abordagem mais intuitiva.

Método convencional


n

r[n]=m=-s[m]h[-m+n]mh[m]m=0 0h[-m]

h[-m+n]nh[-m]nnn

s[m]h[-m+n]s[m]h[-m+n]

[Soma]n

[Repetir]n

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

s[n]h[n]nmnh[-m]s[m]r[n]nh[-m]

insira a descrição da imagem aqui

A seguir, passamos ao método mais intuitivo em que não é necessário acionar um sinal.

Método intuitivo


r[n] como

r[n] = +s[-2]h[n+2] +s[-1]h[n+1] +s[0 0]h[n] + s[1]h[n-1] + s[2]h[n-2] +
Vamos resolver o mesmo exemplo da Figura acima, onde s[n]=[2- 11] e h[n]=[-112]. Isso é mostrado na tabela abaixo.

insira a descrição da imagem aqui

Esse método é ilustrado na figura abaixo. Do ponto de vista da implementação, não há diferença entre os dois métodos.

insira a descrição da imagem aqui

Para resumir, a convolução nos diz como um sistema LTI se comporta em resposta a uma entrada específica e, graças ao método intuitivo acima, podemos dizer que convolução também é multiplicação no domínio do tempo (e não é necessário acionar o sinal), exceto pelo fato de que neste momento, a multiplicação do domínio envolve memória. Para entender melhor em um nível muito mais profundo de onde vem a inversão e o que acontece no domínio da frequência, você pode baixar uma seção de amostra do meu livro aqui .

Qasim Chaudhari
fonte