Convolución Circular y Lineal

7

¿Cuál es la diferencia entre convolución circular y lineal? ¿Cuándo elegiría uno sobre el otro? En el procesamiento de imágenes donde se aplica un filtro a una imagen con una máscara, ¿qué tipo de convolución debo elegir?

Juan
fuente
Le recomiendo que solicite a los moderadores que migren esta pregunta al sitio de procesamiento de señales dsp.SE
Dilip Sarwate
Tal vez pueda meterse con los saludos de demostración de Mathematica
mmm, entiendo pero ... Siempre leí que la convolución circular se usa para señalizar con soporte finito, pero también se usa cuando la señal tiene periodicidad. No entiendo esto porque una señal con soporte finito no siempre tiene periodicidad, por ejemplo, imágenes
Juan

Respuestas:

7

Si tienes un vector de datos, d, que se compone de elementos d1,d2,...dN, entonces la convolución lineal opera en ellos en orden, comenzando con d1 y terminando con dN.

Imagine que el vector de datos d está representado por un trozo de papel con el NElementos escritos en orden. Ahora, imagine formando el trozo de papel en un círculo tocando el extremo (dondedN está escrito) al principio (donde d1está escrito). Convolucionando eso es convolución circular. En la práctica, la convolución lineal y la convolución circular son casi iguales, la diferencia ocurre al principio y al final de la convolución lineal. En convolución lineal, usted asume que hay cero antes y después de sus datos (es decir, suponemos que "d0"y"dN+1"son 0), mientras que con convolución circular envolvemos los datos para que sean periódicos (es decir,"d0" es igual a dN y "dN+1" es igual a d1)

Los mismos principios son válidos para las matrices multidimensionales. Para convolución lineal hay un inicio y un final definidos para cada eje, con ceros asumidos antes y después. Para convolución circular, los datos se envuelven en cada eje.

When would I choose one over the other?

Con algunas excepciones muy raras, no "elegimos" la convolución circular. Casi siempre queremos convolución lineal. La razón por la cual las convoluciones circulares aparecen tanto como lo hacen es porque las convoluciones a través de FFT (FFT, multiplicar, FFT inversa) son convoluciones circulares, no lineales.

Jim Clay
fuente
Si utilicé convolución lineal sin rellenar ceros, ¿el nombre del problema en el límite es alias? y otra pregunta ¿Cuál es el mejor rendimiento (computacional) lineal o circular?
Juan
Con la convolución lineal no es necesario rellenar con ceros, está implícito en cómo se hace el cálculo. Con la convolución circular, rellena con ceros para que produzca los mismos resultados que la convolución lineal.
Jim Clay
Para núcleos de convolución pequeños, la convolución lineal tiene el mejor rendimiento. Para núcleos de gran convolución, la convolución circular a través de FFT tiene el mejor rendimiento. Sin embargo, existe la complicación de necesitar rellenar con ceros para obtener la respuesta correcta.
Jim Clay
ahora estoy confundido porque en la siguiente respuesta, diga "si llena los valores faltantes con 0 entonces permanece en convolución lineal", pero dice "Con convolución lineal no necesita rellenar con ceros"
Juan
Puede acortar el núcleo de convolución con convolución lineal o circular. Es un tema aparte. El relleno cero es solo para convolución circular.
Jim Clay
6

Cuando implementa la convolución en las imágenes, debe cuidar los valores límite, porque en algún momento su máscara de convolución se "saldrá" de la imagen para procesarla. Dependiendo de cómo complete los valores faltantes, determinará si implementa o no una convolución circular:

  • si llena los valores faltantes con 0, entonces permanece en convolución lineal
  • Si llena los valores faltantes por periodicidad, entonces es probable que use convolución circular.

Tenga en cuenta que si implementa la convolución en el dominio de Fourier, entonces no tiene otra opción que la convolución circular, porque el algoritmo FFT periodizará implícitamente sus imágenes.

- EDITAR -

La convolución a menudo se implementa en el dominio de Fourier (=> convolución circular) porque es significativamente más rápido en la mayoría de los casos gracias al algoritmo FFT. Existen algoritmos de convolución lineal rápida, pero generalmente están reservados para el caso de kernel separable donde puede filtrar la imagen horizontal y verticalmente por separado, lo que también produce menos operaciones que una implementación 2D ingenua.

sansuiso
fuente
3
+1. Puede rellenar la imagen con suficientes ceros para evitar esta "periodización" de Fourier.
Andrey Rubshtein
¿Cuál es la ventaja de uno u otro?
Juan
Circular conv. Es más rápido gracias a la FFT. Ver la respuesta editada.
sansuiso
ahora estoy confundido porque en la siguiente respuesta, diga "Con convolución lineal no necesita rellenar con ceros", pero dice "si llena los valores faltantes con 0, entonces permanece en convolución lineal"
Juan
Creo que la primera parte del comentario de Jim Clay es correcta: la convolución lineal generalmente evitará el relleno explícito con 0, pero es un artefacto de implementación (si no verifica los límites, entonces debe asignar una imagen grande y usar relleno). Los enfoques basados ​​en FFT pueden usar relleno para i) una ejecución más rápida (porque hay algoritmos aún más rápidos para algunos buenos tamaños de imagen) o ii) para el zoom de la imagen (esto es equivalente a la interpolación sinc). La convolución circular (incluida la convolución basada en FFT) no depende de ningún relleno per se.
sansuiso