Scanline optimization -- stereovision [Résolu]

[saturn1]

Bonjour je rencontre des problèmes de performances(temps d'éxecution très lent) sur l'algorithme de "scanline optimization" dans le cadre de la stereovision.

Pour faire simple l'algorithme est le suivant:

Code :

1
2
3
4
5
6
7
8
𝐶r(p, 𝑑) at pixel p and disparity 𝑑 is updated as follows:
𝐶r(p, 𝑑) = 𝐶1(p, 𝑑) + min(𝐶r(p − r, 𝑑),
𝐶r(p − r, 𝑑 ± 1) + 𝑃1,
min
𝑘
𝐶r(p − r, 𝑘) + 𝑃2) − min
𝑘
𝐶r(p − r, 𝑘)

Donc c'est un algorithme récursif.
Pour tenter de l'optimiser j'ai tenté de stocker dans un tableau les valeurs déjà calculer et de les réutiliser. Mais c'est toujours très lent.

J'ai environ 20 niveaux de disparités pour une image de 300*300 environ.
Donc en gros j'appelle ce script 300*300*20 (3 boucles imbriquées).

Si quelqu'un sait comment optimiser ce genre d'algorithme, merci de son aide

[souviron34]

il y a des signes bizarres dans ton algo..

Peux-tu le reposter normalement ?

Et aussi, le code en tant que tel, pas juste l'algo..

Merci

[saturn1]

Bonjour, pour l'encodage c'est peut être parce que j'ai poster avec un firefox datant de la préhistoire...

L'algorithme que j'ai code semble marche mais il prend 20 secondes a s’exécuter pour un scanline dans une seule direction.

Je l'ai code en matlab il fait environ une 30e de lignes.

Les deux formules utilisées sont:

Let
mlt(dt) be the message that node t receives from its left
neighboring node s on disparity dt. It is updated in the
following way:

La ou je bloque c'est sur le terme V(dt, ds) qui est le smoothness terme entre 2 disparité, celle du noeud T et le précédent S. Donc pour moi je comprend qu'on est oblige de faire une double boucle imbrique sur les disparités pour calculer V entre le noeud précédent(s) et le courant(t) et ceux pour chaque disparité différentes entre les deux noeuds.

Merci de votre aide.

Edit: je n'ai pas poste le code car je ne sais pas si cette algorithme parle a quelqu'un a vrai dire^^, je n'en ai pas trouve d’implémentation sur internet.

[souviron34]

Envoyé par saturn1

La ou je bloque c'est sur le terme V(dt, ds) qui est le smoothness terme entre 2 disparité, celle du noeud T et le précédent S. Donc pour moi je comprend qu'on est oblige de faire une double boucle imbrique sur les disparités pour calculer V entre le noeud précédent(s) et le courant(t) et ceux pour chaque disparité différentes entre les deux noeuds.

Merci de votre aide.

Edit: je n'ai pas poste le code car je ne sais pas si cette algorithme parle a quelqu'un a vrai dire^^, je n'en ai pas trouve d’implémentation sur internet.

Oui, mais comme on n'a pas les références de l'algo et l'expression de V, on ne peut pas t'aider pour l'instant.

Soit plus précis stp.

En particulier un pointeur sur l'algo serait bien, et aussi l'expression réelle de V.

[saturn1]

Bonjour,
le smoothness term se calcule comme cela:



avec lambda constante.

voici en matlab mon algo:

Code :

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

 for x=1:1:size(i1,2) % on parcourt les x de l'image...
            for y=1:1:size(i1,1) % on parcourt les y de l'image...
                            
                iter = 1;            
                for id=mins:1:maxs % pour chaque disparite...
                    minni = 0;
                    if x > 1 && x < size(i1, 2)
                        iter2 =  1;
                        minni = single(100000000);
                        for id2=mins:1:maxs   % pour chaque disparite
                        
                            
                            iit = x +id;
                            if iit <= 0
                                iit = 1;
                            end
                            if iit > size(i1, 2)
                               iit = size(i1, 2); 
                            end
                            
                            iit2 = x  + id2;
                            if iit2 <= 0
                                iit2 = 1;
                            end
                            if iit2 > size(i1, 2)
                               iit2 = size(i1, 2); 
                            end

                            diff = abs(i1(y, iit2, 1) - i1(y, iit, 1)) ...
                                + abs(i1(y, iit2, 2) - i1(y, iit, 2)) ...
                                + abs(i1(y, iit2, 3) - i1(y, iit, 3));
                            diff = diff / 3;
                            lambda = 300;
                            thres = 20;
                            if diff > thres
                               lambda = lambda / 4; 
                            end

                            smooth = lambda * diff; % calcul du smooth entre le noeud precedent et le courant et ce pour chaque disparite.
                                             
                            myv = smooth + costs(iter2, y, x - 1) + costsscanlines(1, iter2, y, x - 1);
                            minni = min(minni, myv);
                            
                            iter2 = iter2 + 1;
                             
                        end
                    end
                    
                    costsscanlines(1, iter, y, x) = minni;    
                    iter = iter + 1;
                end
            end
        end
        dur = toc;
        disp(toc);
        tic;

        
        costsscanline = zeros(maxs + mins, size(i1, 1), size(i1, 2));
        for x=1:1:size(i1,2)
            for y=1:1:size(i1,1)
                iter = 1;
                for id=mins:1:maxs
                    costsscanline(iter, y, x) = costs(iter, y, x) +  costsscanlines(1, iter, y, x);
                    %disp(costsscanlines(1, iter, y, x));
                    iter = iter + 1;
                end
            end
        end

[saturn1]

C'est bon j'ai enfin trouve...^_^. je marque donc le problème en résolu.
Voici donc aussi le code du scanline optimisation (les valeur de theta peuvent etre changer le calcul du smoothness term peuvent etre ameliorer.) Si cela peut aider.

Code matlab :

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
    function costsscanline = so(costs, mins, maxs, step, stepy, i1, inidisp, idxso)
        tmpcosts = inf(maxs - mins + 1, size(i1, 1), size(i1, 2));
        tic
        if stepy >= 0
            yst = 1;
            endy = size(i1, 1);
        else
            endy = 1;
            yst = size(i1, 1);
        end
           
        if stepy == 0
            qsy = 1;
        else
            qsy = stepy;
        end
        for y=yst:qsy:endy
            if step >= 0
                xst = 1;
                endx = size(i1, 2);
            else
                endx = 1;
                xst = size(i1, 2);
            end
            
            if step == 0
                qsx = 1;
            else
                qsx = step;
            end
            
            for x=xst:qsx:endx
                ite = 1;
                
                for itedis=mins:1:maxs
                    if x == 1 || x == size(i1, 2) || y == 1 || y == size(i1, 1)
                       tmpcosts(ite, y, x) = costs(ite, y, x);
                    else
                        %myval = costs(ite, y, x);
                        ite2 = 1;
                        minn = inf;
                        theta1 = 80;
                        theta2 = 120;
                        %for itedis2=mins:1:maxs
                        %itedis2 = itedis + 1;
                        %    if diff1 == inf && abs(itedis2 - itedis) == 1
                                
                        diff1 = max(abs(i1(min(max(y-stepy, 1), size(i1, 1)), min(max(x - step, 1), size(i1, 2)), 1)...
                            - i1(y, x, 1)), ...
                            abs(i1(min(max(y-stepy, 1), size(i1, 1)), min(max(x - step, 1), size(i1, 2)), 2) - i1(y, x, 2)));
                        diff1 = max(diff1, abs(i1(min(max(y-stepy, 1), size(i1, 1)), min(max(x - step, 1), size(i1, 2)), 3) - i1(y, x, 3)));
                            %end
                            %itedis2 = itedis + 2;
                            %if diff2 == inf && abs(itedis2 - itedis) > 1
                        diff2 = max(abs(i1(min(max(y-stepy, 1), size(i1, 1)), min(max(x - step + itedis, 1), size(i1, 2)), 1) - i1(y, min(max(x + itedis, 1), size(i1, 2)), 1)), ...
                            abs(i1(min(max(y-stepy, 1), size(i1, 1)), min(max(x - step + itedis, 1), size(i1, 2)), 2) - i1(y, min(max(x + itedis, 1), size(i1, 2)), 2)));
                        diff2 = max(diff2, abs(i1(min(max(y-stepy, 1), size(i1, 1)), min(max(x - step + itedis, 1), size(i1, 2)), 3) - i1(y, min(max(x + itedis, 1), size(i1, 2)), 3)));                                
                            %end
                        %end
                        thresh = 5;
                        
                        %disp(diff2);
                        
                        if diff1 <= thresh && diff2 <= thresh
                            p1 = theta1;
                            p2 = theta2;
                        end
                        if diff1 <= thresh && diff2 >= thresh
                            p1 = theta1 / 4;
                            p2 = theta2 / 4;
                        end                        
                        if diff1 >= thresh && diff2 <= thresh
                            p1 = theta1 / 4;
                            p2 = theta2 / 4;
                        end         
                        if diff1 >= thresh && diff2 >= thresh
                            p1 = theta1 / 10;
                            p2 = theta2 / 10;
                        end    
                        minwpen = 0;
                        for itedis2=mins:1:maxs  
                            pen = 0;
                            if abs(itedis2 - itedis) == 1
                                pen = p1;
                            end
                            if abs(itedis2 - itedis) > 1
                                pen = p2;
                            end
                            if tmpcosts(ite2, y - stepy, x - step) + pen < minn
                                minn = tmpcosts(ite2, y - stepy, x - step) + pen;
                                %minwpen = tmpcosts(ite2, y, x - 1);
                            end
                            if tmpcosts(ite2, y - stepy, x - step) < minwpen
                                minwpen = tmpcosts(ite2, y - stepy, x - step);
                            end
                            ite2 = ite2 + 1;
                        end
                        myval = costs(ite, y, x) + minn - minwpen;
                        tmpcosts(ite, y, x) = myval;
                    end
                    ite = ite + 1;
                end
            end
        end
        costsscanline = tmpcosts;
        dur = toc;
        disp(dur);
    end