Application de la transformée de Hough

rectangulaire à la détection de droites discrètes

Mémoire présenté par

Cheick Amed Diloma Gabriel TRAORE
pour l'obtention du Diplôme de Master de mathémathiques
sous la direction du Docteur
Telesphore TIENDREBEOGO
co-dirigé par le Docteur
Abdoulaye SERE
Université Nazi BONI (U.N.B)

UNITÉ DE FORMATION ET DE RECHERCHE EN SCIENCES ET

TECHNIQUES (UFR/ST)

Laboratoire d'Algèbre, de Mathématiques Discrètes et d'Informatique (L.A.M.D.I)

11 novembre 2019
 Plan
Introduction
Espaces et objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes
Résultats numériques
Conclusion et perspectives

Plan de la présentation
1 Introduction
2 Espaces et objets discrets
Objets discrets
Transformée de Hough Standard
3 Méthode :Transformée de Hough rectangulaire et algorithmes
Image
Transformée de Hough rectangulaire
Génération de la grille
Reconnaissance
4 Résultats numériques
Conditions expérimentales
Résultats obtenus
5 Conclusion et perspectives
Conclusion
Perspectives 2 / 29
 Plan
Introduction
Espaces et objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes
Résultats numériques
Conclusion et perspectives

Plan
1 Introduction
2 Espaces et objets discrets
Objets discrets
Transformée de Hough Standard
3 Méthode :Transformée de Hough rectangulaire et algorithmes
Image
Transformée de Hough rectangulaire
Génération de la grille
Reconnaissance
4 Résultats numériques
Conditions expérimentales
Résultats obtenus
5 Conclusion et perspectives
Conclusion
Perspectives 3 / 29
 Plan
Introduction
Espaces et objets discrets Objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes Transformée de Hough Standard
Résultats numériques
Conclusion et perspectives

Plan
1 Introduction
2 Espaces et objets discrets
Objets discrets
Transformée de Hough Standard
3 Méthode :Transformée de Hough rectangulaire et algorithmes
Image
Transformée de Hough rectangulaire
Génération de la grille
Reconnaissance
4 Résultats numériques
Conditions expérimentales
Résultats obtenus
5 Conclusion et perspectives
Conclusion
Perspectives 5 / 29
 Plan
Introduction
Espaces et objets discrets Objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes Transformée de Hough Standard
Résultats numériques
Conclusion et perspectives

Dénition
Soit d une distance sur Rn . Les points d'un ensemble X ⊆ Rn sont
dits isolés si pour tout point x ∈ X , il existe  ∈ R∗+ tel que la
boule fermée Bd0 (x, ) ne contient que x . Un point isolé est aussi
appelé point discret

Dénition
La discrétisation est la détermination des points isolés constituants
un espace (continu).

Dénition
Un espace discret est un espace constitué de pavés ou carreaux, il
peut être le résultat d'une discrétisation. Dans ces pavés se
trouvent les points discrets.
6 / 29
 Plan
Introduction
Espaces et objets discrets Objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes Transformée de Hough Standard
Résultats numériques
Conclusion et perspectives

Dénition
Un objet discret est un ensemble de points discrets, en un ou
plusieurs morceaux.

Figure  Objets discrets

Droite discrète
C'est un objet discret vériant :

µ ≤ ax + by < µ + w , (a, b, µ, w ) ∈ Z4 (1)

7 / 29
 Plan
Introduction
Espaces et objets discrets Objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes Transformée de Hough Standard
Résultats numériques
Conclusion et perspectives

Dénition
Soit A = (x, y ) un point discret. La transformée de Hough standard
ou dual de A est la courbe d'équation

r = x cos θ + y sin θ, (θ, r ) ∈ [0, π] × R (2)

Figure  A et son dual 8 / 29

 Plan
Introduction
Espaces et objets discrets Objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes Transformée de Hough Standard
Résultats numériques
Conclusion et perspectives

Dual [SSA13] et pré-image [Dex06] d'un objet discret

Le dual d'un objet discret O est l'union
[ du dual de chaque point
discret p le constituant, Dual(O) = Dual(p).
p∈O
La pré-image Gp d'un objet discret est l'intersection du dual de
\n
chaque point discret p le constituant, Gp (P) = Dual(Pi ).
i=1

Figure  Préimage de pixels 9 / 29

 Plan
Introduction
Espaces et objets discrets Objets discrets
Méthode :Transformée de Hough rectangulaire et algorithmes Transformée de Hough Standard
Résultats numériques
Conclusion et perspectives

Transformée de Hough standard étendue

Le dual d'un segment est l'aire située entre les transformées de
Hough standard des points situés à ses extrémités ;
le dual d'un carré ou d'un rectangle est l'aire située entre les
transformées de Hough standard des points situés aux
extrémités de ses segments diagonaux.

(a) Dual [DB] (b) Dual [AC ]

(c) Union des duaux

Figure  Dual du carré ABCD

10 / 29
 Plan
Introduction Image
Espaces et objets discrets Transformée de Hough rectangulaire
Méthode :Transformée de Hough rectangulaire et algorithmes Génération de la grille
Résultats numériques Reconnaissance
Conclusion et perspectives

Plan
1 Introduction
2 Espaces et objets discrets
Objets discrets
Transformée de Hough Standard
3 Méthode :Transformée de Hough rectangulaire et algorithmes
Image
Transformée de Hough rectangulaire
Génération de la grille
Reconnaissance
4 Résultats numériques
Conditions expérimentales
Résultats obtenus
5 Conclusion et perspectives
Conclusion
Perspectives 11 / 29
 Plan
Introduction Image
Espaces et objets discrets Transformée de Hough rectangulaire
Méthode :Transformée de Hough rectangulaire et algorithmes Génération de la grille
Résultats numériques Reconnaissance
Conclusion et perspectives

Image
Une image est une représentation visuelle ou mentale d'un objet,
c'est un espace discret ni et borné pouvant être modélisée sous
forme matricielle.

Figure  Image échantillonnée et matrice associée

12 / 29
 Plan
Introduction Image
Espaces et objets discrets Transformée de Hough rectangulaire
Méthode :Transformée de Hough rectangulaire et algorithmes Génération de la grille
Résultats numériques Reconnaissance
Conclusion et perspectives

Pré-traitement
Le pré-traitement d'images est l'ensemble des opérations eectuées
sur une image, soit pour l'améliorer, soit pour en extraire de
l'information pour d'autres traitements ou calculs.

(a) Image d'un pentagone

(b) Pentagone après pré-traitement

13 / 29
 Plan
Introduction Image
Espaces et objets discrets Transformée de Hough rectangulaire
Méthode :Transformée de Hough rectangulaire et algorithmes Génération de la grille
Résultats numériques Reconnaissance
Conclusion et perspectives

Données : Une image numérique pré-traitée

début
1) Générer la grille rectangulaire;
2) sélectionner les rectangles qui contiennent au moins α%
pixels allumés ;
3) reconnaitre la(les) droite(s) dans l'image en fonction des
rectangles sélectionnés ;
4) identier les droites discrètes.
n

14 / 29
 Plan
Introduction Image
Espaces et objets discrets Transformée de Hough rectangulaire
Méthode :Transformée de Hough rectangulaire et algorithmes Génération de la grille
Résultats numériques Reconnaissance
Conclusion et perspectives

Munir l'image d'une grille rectangulaire et calculer le dual des pixels

contenus dans cette grille est un pilier central de la résolution de la
problématique.
Algorithmes de maillage
L'image étant une matrice munie d'un repère à coordonnées dans
Z, la distance entre les extrémités d'une grille doit être un entier.
Nous avons utilisés les algorithmes déterministes du cribles
d'Eratosthène et une fonction de factorisation.

15 / 29
Fonction erast(n : entier) : entier
Pré-condition : n>1
Variables : r , k : entiers
k ← 2;√
e← E ( n) ;
tant que k ≤ e faire
r ← n mod k ;
si r = 0 alors
retourner 0 ; % k divise n, n n'est donc pas premier
n
k ← k + 1;
n
retourner 1 ; % n est alors premier
n
Fonction factorisation(Nl : entier) : couple d'entiers
Pré-condition : Nl ∈/ P
Variables : k, k1 , k2 : entiers
tab : tableau d'entiers
Sorties : k1 , k2 : entiers
k ← 2;
√
e← E ( Nl) ;
tant que k ≤ e faire
si Nl mod k = 0 et erast( ) Vrai
k = alors
ajouter k dans tab % tab est ordonné et contient les
diviseurs premiers de Nl
n
k ← k + 1;
n
%on divise par 2 pour ne pas considéré un diviseur premier trop
petit ou trop grand de Nl
k ← E (longueur (tab)/2);
k2 ← tab[k];
k1 ← Nl/k2 ;
retourner k1 , k2 ; % Nl= k1 × k2
n
k2 est le nombre de grille.
Fonction maillage(Nl, Nc : entiers) : deux tableaux d'entiers
Variables : tab : tableau de 4 entiers, tabool : tableau de 2
booléens
Sorties : tab[1] (tab[3]) : largeur (hauteur) du rectangle de notre
maillage
tab[0] (tab[2]) : nombre de grille sur la ligne (la
colonne)
tabool[0] (tabool[1]) : primalité de Nl (Nc)
tabool[0]←erast(Nl);
si tabool[0] alors
tab[0], tab[1]←factorisation(Nl-1) ;
sinon
tab[0], tab[1]←factorisation(Nl) ;
n
tabool[1]←erast(Nc);
si tabool[1] alors
tab[2], tab[3]←factorisation(Nc-1) ;
sinon
tab[2], tab[3]←factorisation(Nc) ;
n
retourner tab,tabool;
n
 Nc

0 1 2 3 4 5 6 7 8 9 10 11 12

5
Nl
6

10

NL=11, Nc=13

tab00l=[1,1]

tab[0]=5, tab[1]=2

tab[2]=4, tab[3]=3
 Nc

0 1 2 3 4 5 6 7 8 9 10 11 12

0
≥α ≥α
1

4
≥α ≥α
5
Nl
6

8
≥α ≥α ≥α
6

10

Les rectangles ayant un taux de pixels ‘’allumés “ supérieurs à alpha (α) sont sélectionnés.

Tous les pixels situés dans la ligne et la colonne résiduelles sont traités.
 Plan
Introduction Image
Espaces et objets discrets Transformée de Hough rectangulaire
Méthode :Transformée de Hough rectangulaire et algorithmes Génération de la grille
Résultats numériques Reconnaissance
Conclusion et perspectives

Reconnaissance
Une fois muni de la grille rectangulaire on passe à la reconnaissance
des droites
Soit en utilisant la pré-image généralisée.
Soit en utilisant un accumulateur de données.

21 / 29
 Plan
Introduction
Espaces et objets discrets Conditions expérimentales
Méthode :Transformée de Hough rectangulaire et algorithmes Résultats obtenus
Résultats numériques
Conclusion et perspectives

Plan
1 Introduction
2 Espaces et objets discrets
Objets discrets
Transformée de Hough Standard
3 Méthode :Transformée de Hough rectangulaire et algorithmes
Image
Transformée de Hough rectangulaire
Génération de la grille
Reconnaissance
4 Résultats numériques
Conditions expérimentales
Résultats obtenus
5 Conclusion et perspectives
Conclusion
Perspectives 22 / 29
 Plan
Introduction
Espaces et objets discrets Conditions expérimentales
Méthode :Transformée de Hough rectangulaire et algorithmes Résultats obtenus
Résultats numériques
Conclusion et perspectives

Nous avons utilisés le langage de programmation et de calcul

mathématiques python.
Nous avons utilisés un ordinateur portable de caractéristiques
Processeur : AMD A8-6410 APU with AMD Radeon RS
Graphics 2.00GHz
Mémoire Ram utilisable : 4.94 GB
Type du système : système d'exploitation 64 bits, processeur
×64.

23 / 29
 Table  Résultats classiques, sans notre maillage

seuil Nombres de Temps de détections Temps nal

droites détectées
40 7 9.59 sec 15.95 sec

Table  Résultats avec notre maillage

α seuil Nombres de Temps de détections Temps nal

droites détectées
0.2 40 8 3.88 sec 11.39 sec
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

Plan
1 Introduction
2 Espaces et objets discrets
Objets discrets
Transformée de Hough Standard
3 Méthode :Transformée de Hough rectangulaire et algorithmes
Image
Transformée de Hough rectangulaire
Génération de la grille
Reconnaissance
4 Résultats numériques
Conditions expérimentales
Résultats obtenus
5 Conclusion et perspectives
Conclusion
Perspectives 25 / 29
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

Conclusion
Elaborer un maillage rectangulaire pour parcourir une image.

26 / 29
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

Conclusion
Elaborer un maillage rectangulaire pour parcourir une image.
Fourni une méthode de parcours d'image plus rapide.
Permet de détecter les droites présentent dans l'image en ne
considérant que certains rectangles.

26 / 29
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

Conclusion
Elaborer un maillage rectangulaire pour parcourir une image.
Fourni une méthode de parcours d'image plus rapide.
Permet de détecter les droites présentent dans l'image en ne
considérant que certains rectangles.
Réduire le temps de détections des droites avec la transformée
de Hough.

26 / 29
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

Développer des outils python an de permettre

l'implémentation de tous les algorithmes du mémoire.
D'étudier de la contrôlabilité du choix du paramètre α et du
seuil, dans le but d'optimiser et de ne détecter que des droites
jugées "utiles".
De coupler les algorithmes issus de ses travaux aux
deep-learning an de permettre des reconnaissances
automatisées sur de grands volumes d'images et en temps
"acceptable".
De conçevoir un maillage triangulaire de l'image et des
algorithmes de détections de droites en fonction de ce maillage
et dont les temps d'exécutions seront comparés à ceux de ce
mémoire. Envisager également une implémentation avec du
deep-learning ;
D'étendre nos travaux aux images 3D.
27 / 29
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

Fin de la présentation

MERCI, pour votre

attention !
M. Dexet.
Architecture d'un modeleur géométrique à base topologique

d'objets discrets et méthodes de reconstruction en dimensions

.
2 et 3

Thèse en informatique et applications, Université de Poitiers

(France), décembre 2006.

28 / 29
 Plan
Introduction
Espaces et objets discrets Conclusion
Méthode :Transformée de Hough rectangulaire et algorithmes Perspectives
Résultats numériques
Conclusion et perspectives

A. Sere, O. Sie, and E. Andres.

Extended standard hough transform for analytical line
recognition.
(IJACSA) International Journal of Advanced Computer Science

and Applications , 4(3) :256266, 2013.

29 / 29