J'essaie d'évaluer la complexité de certains algorithmes de filtrage d'image de base. Je me demandais si vous pouviez vérifier cette théorie;Question de complexité de base - Convolution
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 = # pixels entrée
Inverse est d'ordre O (M) ou O (S^2). D'autre part, un filtre de convolution a un paramètre R qui détermine la taille du voisinage à convoluer en établissant la valeur de pixel suivante pour chaque filtre.
Soit R = Rayon de filtre de convolution
convolution est d'ordre O (M * ((R + R * 2)^2) = O (M * (4R^2) = O (MR^2)
Ou plutôt soit N = la taille du filtre de convolution (Quartier) en pixels?
O (M * (N)) = O (MN)
en fin de compte un filtre de convolution est linéairement dépend du produit du nombre de pixels et du nombre de pixels dans le voisinage
Si vous avez des liens vers un document où cela a été documenté, il serait grandement apprécié.
Kind regards,
Gavin
Travail à domicile? En tout cas, tes derniers gros-Ohs me vont bien. –
C'est un peu le contexte d'une dissertation que j'écris sur les limites des appareils mobiles. Je fais une application de filtrage d'image pour un téléphone android et j'espère que ceci déterminera où les goulots d'étranglement seront. J'utilise 20 nœuds de base construits dans des arbres, les 20 nœuds incluent de nombreuses opérations ponctuelles comme Add, Or et Subtract. J'ai aussi un filtre Convolution et un filtre Median qui est l'endroit où les goulets d'étranglement se produisent, je veux juste formaliser cela. L'entrée aux feuilles de l'arbre est toujours la même image qui est transformée et combinée pour obtenir la sortie à la racine. A bientôt – gav
Vos quartiers se chevauchent-ils en itérations? –