La complexité de base Question - Convolution

Question

Je suis en train d'évaluer la complexité de certains algorithmes de filtrage d'image de base. Je me demandais si vous pouviez vérifier cette théorie;

Pour un pixel de base par le filtre de pixel comme inverse du nombre d'opérations croît linéairement avec la taille de l'entrée (en pixels) et

Soit S = longueur du côté de l'image Soit M = # entrée pixels

Inverse est d'ordre O (M) ou O (S ^ 2).

Un filtre de convolution d'autre part a un paramètre R qui détermine la taille du voisinage pour convoluer la mise en place de la prochaine valeur de pixel pour chaque filtre.

Soit R = Rayon du filtre de convolution

Convolution est d'ordre O (M * ((R + R * 2) ^ 2) = O (M * (4R ^ 2) = O (MR ^ 2)

Ou devrais-je laisser N = la taille du filtre de convolution (de voisinage) en pixels?

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

En fin de compte un filtre de convolution est linéairement dépendante du produit du nombre de pixels et le nombre de pixels dans le voisinage.

Si vous avez des liens vers un document où cela a été documenté, il serait grandement apprécié.

Cordialement,

Gavin

Answer 1

O (MN) semble juste si je comprends que, pour chaque pixel dans l'image de la convolution est le réglage de valeurs de pixels dans le voisinage N, N étant indépendamment du carré. N pourrait être triangle meilleur ajustement ... mais fournissant les pixels dans le voisinage sont ajustées pour chaque pixel de l'image alors O (MN) est plus logique, parce que la dépendance se trouve dans les pixels corrigées par pixel dans l'image source.

Il est intéressant, dans un quartier non régulier des pixels peuvent être réglés par le masque de voisinage plus que d'autres, mais O (MN) sera toujours debout.

Si le quartier est central sur un pixel P, puis déplacé à l'autre P qui n'a pas été dans le quartier (qui signifie que chaque pixel est transformé une fois), cela ne tient pas.