On considère des images définies sur un domaine discret D (par exemple une grille rectangulaire en 2D, parallépipédique en 3D). On suppose qu'à chaque pixel (ou voxel) p de D on associe une fenêtre W(p) incluse dans D. A partir d'une image I, on veut construire une nouvelle image dont la valeur en un pixel p est obtenue par application d'une fonction f aux valeurs I(q) des pixels q de la fenêtre W(p). En fonction de l'indépendance ou interdépendance des calculs effectués sur les différents pixels, on obtient deux sortes d'algorithmes :
Dans un algorithme parallèle, on suppose que le calcul effectué en un pixel est indépendant de celui effectué sur les autres pixels. Conceptuellement, cela revient à construire une nouvelle image J sur D comme suit :
Pour tout pixel p dans D, faire J(p) := f(I(q) | q dans W(p)) .
L'adjectif "parallèle" attribué à un tel algorithme provient de ce que cela correspond à une architecture de type SIMD (une Seule Instruction, Multiples Données) avec un processeur par pixel, et une interconnexion entre deux processeurs correspondant à deux pixels lorsque l'un est dans la fenêtre de l'autre. On suppose qu'initialement chaque processeur contient la valeur de ce pixel dans l'image. Dans un premier temps, chaque processeur récolte les valeurs des processeurs connectés, correspondant à la fenêtre ; dans un deuxième temps tous les processeurs appliquent la fonction f aux valeurs récoltées ; dans un troisième temps chaque processeur affecte à sa valeur d'image le résultat de cette fonction f. Le synchronisme entre les différents processeurs assure l'indépendance des calculs effectués sur les différents pixels.
En pratique, un tel algorithme peut s'effectuer sur un ordinateur séquentiel grâce à un ordre de balayage ; on n'a qu'à effectuer sur chaque pixel en succession le calcul de f et recopier le résultat dans la nouvelle image :
Pour le pixel p allant du premier au dernier, faire J(p) := f(I(q) | q dans W(p)) .
Les algorithmes parallèles sont utilisés dans de nombreuses situations : filtrage, squelettisation, opérations morphologiques, etc. Par défaut, tout algorithme basé sur un calcul de valeur dans le voisinage de chaque pixel, sera supposé parallèle, sauf indication contraire.
Cette terminologie utilisée en traitement d'images ne doit pas faire supposer que c'est la façon dont on mettrait en oeuvre une opération de traitement d'images sur un ordinateur parallèle. Tout d'abord, celui-ci ne comporte pas nécessairement un processeur par pixel. Mais surtout, les algorithmes dits parallèles sont généralement inefficaces, parce qu'il y a souvent une forte redondance entre les calculs effectués par deux pixels voisins. Dans certains cas, les calculs effectués sur la majorité des pixels sont inutiles, car seule une partie des pixels voit sa valeur changer ; c'est le cas par exemple dans la squelettisation (seuls les pixels du bord de la figure sont susceptibles d'être modifiés) et dans la transformée de distance (pour laquelle la valeur ne peut évoluer que suivant un front se propageant à partir du marqueur). C'est pourquoi on utilisera si possible un algorithme séquentiel ou à base de file.
Un tel algorithme s'appuie explicitement sur un ordre de balayage. Les pixels sont visités l'un à la suite de l'autre, et à chaque fois on calcule la valeur de f, mais à la différence de l'algorithme parallèle, cette valeur n'est pas mise dans une nouvelle image, mais bien récrite dans l'image de départ :
Pour le pixel p allant du premier au dernier, faire I(p) := f(I(q) | q dans W(p)) .
Donc quand on arrive à un pixel p, tous les pixels balayés avant p auront leur nouvelle valeur, tandis que p et les autres pixels pas encore balayés ont leur valeur de départ. En particulier, la valeur calculée en p peut dépendre de toutes les valeurs calculées sur les pixels précédemment balayés, ce qui explique l'adjectif "récursif".
Dans de nombreux cas, le résultat d'un tel algorithme dépend de l'ordre de balayage, ce qui induit un biais directionnel sur l'image traitée. Le plus célèbre algorithme séquentiel est celui pour la transformée de distance, qui utilise deux balayages de sens opposés (direct et inverse) ; de plus, celui-ci adapte les fenêtres en fonction de l'ordre de balayage, de façon à donner un résultat exact quel que soit l'ordre de balayage direct choisi.
Il existe des algorithmes séquentiels de squelettisation. Bien qu'ils tendent à déformer le squelette dans la direction du balayage, ils sont plus faciles à concevoir, parce que la préservation de la topologie ne requiert que la simplicité du pixel courant.
Dans tous les traitements reposant sur une propagation d'information, les algorithmes séquentiels conviennent mieux que les parallèles. Cependant, quand cette propagation est contrainte à l'intérieur d'un masque concave (par exemple, reconstruction de composantes connexes, ou opérations géodésiques), il vaut mieux adopter un algorithme à base de file.
Il existe une situation où les deux algorithmes parallèle et séquentiel donnent le même résultat, à savoir quand chaque fenêtre se réduit au point de référence : W(p) = {p}. Ici l'algorithme parallèle fait J(p) := f(I(p)) tandis que le séquentiel fait I(p) := f(I(p)), donc le calcul pour un pixel ne dépend pas de celui pour les autres. Il s'agit donc simplement des transformations sur les niveaux de gris, par exemple les rehaussements.
Dans certains cas il est souhaitable de combiner les avantages respectifs de l'algorithme parallèle et du séquentiel. On peut considérer que dans les deux on construit par calcul une nouvelle image J, et que pour cela on balaye les pixels du premier au dernier, mais le calcul effectué sera différent. Dans l'algorithme parallèle le calcul sera
J(p) := f(I(q) | q dans W(p)) ,
tandis que dans l'algorithme séquentiel, il sera
J(p) := f(H(q) | q dans W(p)) ,
où H(q) = J(q) pour q balayé avant p, et H(q) = I(q) sinon.
En vue de combiner les deux, il faut que J(p) soit fonction à la fois de I(q) pour tous les q dans W(p), mais aussi de J(q) pour les q dans W(p) balayés avant p :
J(p) := f(I(q) | q dans W(p) ; J(q) | q dans W(p), q balayé avant p) .
En pratique, on n'aura pas besoin de deux images I et J, pour le pixel p on récrira en I(p) une nouvelle valeur codant le couple (I(p),J(p)). Par exemple dans un algorithme diminuant une figure binaire (par exemple une squelettisation), on aura trois valeurs 0, 1 et 2 pour les pixels : 0 pour un pixel du fond, 1 pour un pixel de la figure non modifié, et 2 pour un pixel de la figure passant au fond (c.-à-d. I(p) = 1 et J(p) = 0).
Un tel algorithme sera appelé séquentiel à mémoire, parce qu'il fonctionne comme un algorithme séquentiel, mais qu'il garde toujours en mémoire la valeur initiale des pixels déjà balayés.
Un exemple typique d'algorithme séquentiel à mémoire est celui d'Hilditch (1968) pour la squelettisation. Comme la plupart des algorithmes dans ce domaine, il utilise une itération d'opérations locales sur la figure, et il gardera en mémoire non seulement l'état initial d'un pixel enlevé de la figure, mais aussi le numéro de l'itération où il l'a été. Cela est possible en donnant par exemple des valeurs entières aux pixels : 0 pour les pixels du fond, 1 pour les pixels de la figure non modifiés, et n > 1 pour ceux passant de la figure au fond lors de la (n - 1)-ème itération.