Discussion :

[PerpetualSnow]

Connaissez vous des articles sur le multithreading en traitement d'images?

[pseudocode]

Qu'est-ce qu'il y aurait de particulier au "traitement d'image" ?

[PerpetualSnow]

L'image est une structure de données particulière.

La plupart des traitements qui lui sont appliqués exigent un ou plusieurs parcours de cette structure. On peut imaginer parallèliser ces parcours.

Ma question etait justement de savoir s'il existait des algorithmes de multithreading spécialisés pour le domaine de l'image.

[pseudocode]

Ma question etait justement de savoir s'il existait des algorithmes de multithreading spécialisés pour le domaine de l'image.

Généralement on procède à l'inverse. On crée des formules/algorithmes qui soient séparables/parallelisables => possibilité d'implémenter le multithreading.

De la même manière, on modifie la structure de données (de l'image) pour permettre le multithreading.

Par exemple la Transformée de Fourier 2D : on sépare la formule de convolution 2D en 2 formules de convolutions 1D. Ensuite on implémente un algorithme de convolution 1D qui soit parallèlisable. On modifie la structure de données de l'image pour y accéder par ligne puis par colonne. Enfin on utilise le multithreading pour exécuter simultanément les algos de convolution sur N lignes, puis sur N colonnes.

[souviron34]

Je rejoins pseudocode sur le fond. Il faut d'abord avoir préparé l'algo. Ensuite c'est de la technique et des choix : parallèle, multi-core, multi-threading, vaste débat dont tu trouveras des discussions sur le forum Débats sur le Développement.

Maintenant, une autre solution de préparation (suivant les cas des traitements à effectuer) : découper l'image en blocs (de lignes, de colonnes, de matrices).

[PerpetualSnow]

Par exemple la Transformée de Fourier 2D : on sépare la formule de convolution 2D en 2 formules de convolutions 1D. Ensuite on implémente un algorithme de convolution 1D qui soit parallèlisable. On modifie la structure de données de l'image pour y accéder par ligne puis par colonne. Enfin on utilise le multithreading pour exécuter simultanément les algos de convolution sur N lignes, puis sur N colonnes.

C'est ce genre d'exemple que j'essayais d'expliquer de manière générale.

Je voulais savoir si des personnes avaient déjà mis en oeuvre un tel algorithme et surtout avoir des articles, exemples ou sources pour mesurer le gain de performance que cela peut générer.

[millie]

Juste avant de commencer, je dirais juste qu'à l'heure actuel, le fait de multithreadé (je ne parle pas de parallélisation sur plein de machines) un opérateur de traitement d'images (sur un ordinateur classique avec moins de 4 processeur/coeurs) ne fera diviser l'opérateur final au mieux de 4 fois.
Il faut parfois se creuser la tête autrement car il existe parfois des méthodes qui réduisent nettement plus les calculs et qui sont purement liées à l'algo.



Il y a beaucoup d'opérateurs en traitement d'images que l'on peut catégoriser.

- Il y en a où il est nécessaire de connaître que le pixel d'entrée pour connaître le pixel de sortie
- Il y en a où il est nécessaire de connaître qu'un ensemble de pixel d'entrée (par exemple les n pixels autour du pixel d'entrée) pour connaître le pixel de sortie
- Il y en a d'autres où la position de l'image d'entrée et l'image d'entrée est suffisante
...


Dans ces cas là, il est possible de répartir les calculs aisément.


Ensuite, il y a des opérateurs itératifs qui ne peut en général pas être simplement et complètement paralléliser/multithreadé mais où chaque itération peut être catégorisé.

=> ici, il est possible de créer plusieurs threads et de mettre des sortes de points d'arrêt à chaque itération (les threads attendent que tous les autres aient fini l'itération pour reprendre l'itération suivante)



Exemple ici : http://subversion.developpez.com/pro.../commons/area/

La catégorie, c'est : pour calculer le pixel de sortie à la position (i,j), il est nécessaitre de connaître l'ensemble des pixels autour de (i,j) (de l'image d'entrée)

AreaOperator=> définie une classe abstraite à implémenter pour le coeur de l'algo
La méthode à implémenter est : public abstract float computeLocalArea(Image in, int x, int y, int canal);


Par exemple pour la convolution ça peut être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
public float computeLocalArea(Image in, int i, int j, int canal) {
		float t = 0;
 
		for (int kj = 0; kj < kernel.getHeight(); kj++)
			for (int ki = 0; ki < kernel.getWidth(); ki++) {
				t += kernel.getElement(ki, kj)
						* in.getPixel(i + ki - kernel.getXOrigin(), j + kj
								- kernel.getYOrigin(), canal);
 
			}
 
		return t;
	}

Pour effectuer le traitement générique, la classe AreaOperator peut utiliser plusieurs classes :
Implémentation classique (sans MT) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void compute(Image out, Image in, AreaOperator op) throws Exception {
		if (out.getNumComponents() != in.getNumComponents())
			throw new IllegalArgumentException("AreaOperator::compute");
 
		int leftpadding = op.getLeftPadding();
		int rightpadding = op.getRightPadding();
		int toppadding = op.getTopPadding();
		int bottompadding = op.getBottomPadding();
		int hauteur = in.getHeight();
		int largeur = in.getWidth();
 
		out.resize(largeur - (rightpadding + leftpadding), hauteur
				- (toppadding + bottompadding));
 
		for (int canal = 0; canal < in.getNumComponents(); canal++)
			for (int j = toppadding; j < hauteur - bottompadding; j++) {
				for (int i = leftpadding; i < largeur - rightpadding; i++) {
					out.setPixel(i - leftpadding, j - toppadding, canal, op
							.computeLocalArea(in, i, j, canal));
 
				}
			}
	}

Implémentation MT :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class BusinessAreaOperatorThread extends Thread {
 
	int numThread;
 
	int totalThread;
 
	Image out;
 
	Image in;
 
	AreaOperator op;
 
	public BusinessAreaOperatorThread(int numThread, int totalThread,
			Image out, Image in, AreaOperator op) {
		this.numThread = numThread;
		this.totalThread = totalThread;
		this.out = out;
		this.in = in;
		this.op = op;
	}
 
	public void run() {
 
		int leftpadding = op.getLeftPadding();
		int rightpadding = op.getRightPadding();
		int toppadding = op.getTopPadding();
		int bottompadding = op.getBottomPadding();
		int hauteur = in.getHeight();
		int largeur = in.getWidth();
 
		for (int canal = 0; canal < in.getNumComponents(); canal++)
			for (int j = toppadding + numThread; j < hauteur - bottompadding; j += totalThread) {
				for (int i = leftpadding; i < largeur - rightpadding; i++) {
					out.setPixel(i - leftpadding, j - toppadding, canal, op
							.computeLocalArea(in, i, j, canal));
 
				}
			}
	}
 
}
 
 
/**
 * Implémentation Multithreadé des AreaOperator
 * 
 */
public class MTBusinessAreaOperator implements BusinessAreaOperator {
 
	private int totalThreads;
 
	public MTBusinessAreaOperator(int totalThreads) {
		if (totalThreads < 1)
			throw new IllegalArgumentException("Total Thread <1");
 
		this.totalThreads = totalThreads;
	}
 
	public void compute(Image out, Image in, AreaOperator op) throws Exception {
		if (out.getNumComponents() != in.getNumComponents())
			throw new IllegalArgumentException(
					"PointOperator : num components problem");
 
		int leftpadding = op.getLeftPadding();
		int rightpadding = op.getRightPadding();
		int toppadding = op.getTopPadding();
		int bottompadding = op.getBottomPadding();
		int hauteur = in.getHeight();
		int largeur = in.getWidth();
 
		out.resize(largeur - (rightpadding + leftpadding), hauteur
				- (toppadding + bottompadding));
 
		PointSyncThreadGroup group = new PointSyncThreadGroup();
		for (int i = 0; i < totalThreads; i++)
			group.add(new BusinessAreaOperatorThread(i, totalThreads, out, in,
					op));
 
		group.startAll();
		group.joinAll();
	}
 
}

De la même manière, il est parfois possible de séparer les calculs sur les différents canaux (RGB) de l'image d'entrée (mais 3 threads maxi).

[PerpetualSnow]

Merci millie pour le partage de ton implémentation.

Je retiens, notamment que tout calcul qui peut être séparé peut être mis dans un thread à part.