Implémentation de la transformée de Hough pour les objets 3D

Version imprimable

19/03/2010, 23h32
Iori Yagami

Implémentation de la transformée de Hough pour les objets 3D

Bonsoir,
Je dois implémenter la transformée de Hough pour décrire des objets 3D. Après une longue journée à travers les petits "o" de google, j'ai trouvé un article de Zaharia et Prêteux traitant le problème.
Mon problème c'est que je retrouve des difficultés à comprendre les formules.
La partie traitant la transformée de Hough commence par rappeler la caractérisation d'un plan d'une manière unique avec le triplet (s, tetha, fi). et définir le vecteur normal au plan n (nx, ny, nz)
Les ambiguités commencent par la phrase suivante :

Citation:

En échantillonnant uniformément chaque axe de l'espace des
paramètres (s, q, j), on obtient respectivement Ns, Nq et Nj
éléments regroupés dans les ensembles suivants :
· X = { sk = kDs },
où Ds = Smax / Ns , k Î{0,1, ... , Ns -1} et Smax est une valeur
suffisamment grande définissant la taille du maillage,

Que veulent ils dire par échantillonner uniformément un axe?
Je serai reconnaissant si je reçois une aide.
20/03/2010, 11h10
pseudocode

Citation:

Envoyé par Iori Yagami

Que veulent ils dire par échantillonner uniformément un axe?
Je serai reconnaissant si je reçois une aide.

Je suppose que ca veut dire qu'ils discretisent les coordonnées.

(s, q, j) sont des valeurs réelles et sont approximées par (Ns, Nq et Nj) qui sont des valeurs entières. Ca revient a faire un quadrillage de l'espace.

L'échantillonnage "uniforme" veut simplement dire que le quadrillage est régulier.
24/03/2010, 13h35
Iori Yagami

Merci Pseudocode pour m'avoir répondu. J'ai pas vraiment saisi ce que tu veux dire par "quadrillage régulier"..
Je veux implémenter l'algorithme. dès le début on me dit qu'il faut déterminer ces 3 ensembles. Concrètement, qu'est ce que je fais?

Citation:

En échantillonnant uniformément chaque axe de l'espace des
paramètres (s, q, j), on obtient respectivement Ns, Nq et Nj
éléments regroupés dans les ensembles suivants :

· X = { s(k) = kDs }, où Ds = Smax / Ns , k Î{0,1, ... , Ns -1} et Smax est une valeur suffisamment grande définissant la taille du maillage,
· Q = {q(k) = (k + 0.5)Dq }, où Dq = 2pi / Nq , , k Î{0,1, ... , Nq -1} et
· Y = {j(k) = (k - Nj / 2 + 0.5)Dj }, où Dj =p / Nj , k Î{0,1, ... , Nj -1}.

D'après ce que j'ai compris, je définis tout seul les valeurs Ns, Nq et Nj (par exemple 8 pour Nq)
par suite je détermine les 3 ensembles. Par exemple :
Q = {q1 = 1.5/(2pi/8) = 12/2pi = 6/pi, q2, q3... q7}

Est ce que je suis en train de faire une bétise?
24/03/2010, 15h03
pseudocode

Citation:

Envoyé par Iori Yagami

D'après ce que j'ai compris, je définis tout seul les valeurs Ns, Nq et Nj (par exemple 8 pour Nq)
par suite je détermine les 3 ensembles. Par exemple :
Q = {q1 = 1.5/(2pi/8) = 12/2pi = 6/pi, q2, q3... q7}

Est ce que je suis en train de faire une bétise?

Oui c'est ça. Il s'agit simplement de "ranger" une infinité de valeurs réelles dans un nombre fini (Nq) d'ensembles, par une simple règle de 3.
27/03/2010, 10h20
Iori Yagami

d'accord, merci Pseudocode,
Une dernière question, y a t il une règle pour définir les valeurs Ns, Nq, Nj? ou simplement essayer des valeurs et voir celui qui donne le meilleur résultat?
27/03/2010, 12h04
pseudocode

Citation:

Envoyé par Iori Yagami

d'accord, merci Pseudocode,
Une dernière question, y a t il une règle pour définir les valeurs Ns, Nq, Nj? ou simplement essayer des valeurs et voir celui qui donne le meilleur résultat?

J'aimerai te dire qu'il y a une règle magique pour trouver ces valeurs. Mais par expérience, je te dirai plutot qu'il faut faire des essais.
27/03/2010, 16h21
Iori Yagami

OK, merci Pseudo. Je mettrai le code dès que je le termine.

Bon, voila ce que j'ai fait :

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
 
1 - Determiner 
	Smax = Taille du maillage
	Ns = Ntetha = Nfi = Cte (20)
 
2 - Définir les ensembles suivants : 
	S = {sk = k*Smax/Ns, k = 0, ... , Ns-1}
	TETHA = {tethak = (k+0.5)*2PI/Ntetha, k = 0, ... , Ntetha-1}
	FI = {fik = (k - Nfi/2 + 0.5)*PI/Nfi, k = 0, ... , Nfi - 1 }
 
3 - Définir E ensemble des centre de gravité de chaque maille
 
4 - Pour Tout p de E
                Pout Tout j = 0 à Ntetha-1
                        Pour Tout k = 0 à Nfi-1
                                plan = getPlanParOrientation(p, TETHA(j), FI(k)) ----> (A)
                                sjkp = getDistance(o, plan) ---> (B)
                                Si (sjkp >= 0) {
                                        index_sjkp = getNearestValue(sjkp, S)
                                        Accumuler(S(index_sjkp), TETHA(j), FI(k), Aire(maille(p)) )
                                }
                         FinPour
                FinPour
        FinPour
 
5 - Chercher le REFERENCE BIN
 
6 - Définir la liste des points contribuants au BIN

(A) = get N = (cos(tetha)cos(fi), cos(fi)sin(tetha), sin(fi))
(B) = distance d = |Nx*xp + Ny*yp + Nz*zp|

Après tout ça, j'aurai une sorte de tableaux à 3 dim, ce que je demande c'est : Je fais quoi avec pour déterminer le degré de similitude?

16/04/2010, 19h13
pseudocode

ET bien, visiblement la méthode que tu as choisie construit un descripteur d'une forme 3D.

Une fois que tu as calculé un descripteur pour toutes les formes 3D que tu possèdes, tu obtiens donc une base de données de descripteurs.

Si on te donne une nouvelle forme 3D, tu calcules son descripteur, et tu cherches dans ta base le(s) descripteur(s) le(s) plus proche(s).
16/04/2010, 19h38
Iori Yagami

OUI! C'est exactement ce que je veux savoir! ce que vous entendez dire par "le plus proche"!
Est ce que je dois comparer les valeurs des deux tableaux une par une et puis quoi? je fais la moyenne des différences par exemple?
Et comment je définis le seuil de différence? je veux dire la valeur au dessus de laquelle les deux objets sont jugés comme différents.
16/04/2010, 21h39
pseudocode

Citation:

Envoyé par Iori Yagami

OUI! C'est exactement ce que je veux savoir! ce que vous entendez dire par "le plus proche"!
Est ce que je dois comparer les valeurs des deux tableaux une par une et puis quoi? je fais la moyenne des différences par exemple?
Et comment je définis le seuil de différence? je veux dire la valeur au dessus de laquelle les deux objets sont jugés comme différents.

Ah. Tu cherches une mesure de similarité entre deux vecteurs.

Il y en a plein: Distance de Mahalanobis, de Hamming, Euclidienne, Cross-correlation, ...
23/03/2012, 11h21
maymoucha

bonjour,
comment je puisse afficher les différents points de la sphère en matlab afin d'appliquer la TH3D .
06/10/2012, 16h43
maymoucha

Bonjour,
Ma question est la suivante : est ce que la valeur de l'accumulateur est accumulateur = aire( maille)+ sjkp ?
ou bien
accumulateur= acumulateur(p-1) + sjkp?
merci