La complejidad básica Pregunta - Convolución

Question

Estoy tratando de evaluar la complejidad de algunos algoritmos básicos de filtrado de imágenes. Me preguntaba si usted podría verificar esta teoría;

Para un pixel básico por el filtro de pixel como Inverse el número de operaciones crece linealmente con el tamaño de la entrada (en píxeles) y

Sea S = longitud del lado de la imagen Sea M = # píxeles de entrada

Inverse es de orden O (M) o O (S ^ 2).

A filtro de convolución en el otro lado tiene un R parámetro que determina el tamaño de la vecindad para convolve en el establecimiento de la siguiente valor de píxel para cada filtro.

Sea R = Radio de filtro de convolución

convolución es de orden O (M * ((R + R * 2) ^ 2) = O (M * (4R ^ 2) = O (MR ^ 2)

O debería dejar que N = el tamaño del filtro de convolución (nota) en píxeles?

O (M * (N)) = O (MN)

En última instancia un filtro de convolución es linealmente dependiente del producto del número de píxeles y el número de píxeles en el vecindario.

Si tiene alguna enlaces a un documento donde esto se ha documentado que sería muy apreciada.

Saludos cordiales,

Gavin

Answer 1

O (MN) parece correcto si entiendo que para cada píxel de la imagen de la convolución es el ajuste de valores de píxel en el entorno N, independientemente de N es cuadrada. N podría ser triángulo de mejor ajuste ... pero proporcionando los píxeles en la zona se ajusta para cada píxel de la imagen a continuación, O (MN) tiene más sentido, porque la dependencia es en los píxeles ajustados por pixel la imagen de origen.

Curiosamente, en una zona no regular algunos píxeles pueden ser ajustados por la máscara barrio más que otros, pero O (MN) todavía permanecerá.

Si el barrio es el centro de un píxel P y luego se trasladó a la siguiente P, que no estaba en el barrio (es decir, cada píxel se transforma una vez), entonces esto no se sostiene.