Convolución Circular y Lineal

¿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?

Si tienes un vector de datos, $d$, que se compone de elementos $d_1, d_2,... d_N$, entonces la convolución lineal opera en ellos en orden, comenzando con $d_1$ y terminando con $d_N$.

Imagine que el vector de datos $d$ está representado por un trozo de papel con el $N$Elementos escritos en orden. Ahora, imagine formando el trozo de papel en un círculo tocando el extremo (donde$d_N$ está escrito) al principio (donde $d_1$está 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 "$d_0$"y"$d_{N+1}$"son 0), mientras que con convolución circular envolvemos los datos para que sean periódicos (es decir,"$d_0$" es igual a $d_N$ y "$d_{N+1}$" es igual a $d_1$)

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.

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.