Computer Vision: 2.Segmentation

Transcript

1. Master Mathematical Analysis and Applications Course M1 - S2 Computer vision Segmentation and contours detection Week 2-4 Mohammed Hachama hachamam@gmail.com http://hachama.github.io/home/ University of Khemis Miliana -2020-
2. Introduction Contours Segmentation Plan 1. Introduction 2. D´ etection de contours 3. Segmentation de r´ egions Computer vision -Segmentation and contours detection- (Week 2-4) (2/18) M. Hachama (hachamam@gmail.com)
3. Introduction Contours Segmentation Qu’est ce que la segmentation ? • Partitionnement d’une image en un nombre minimal de r´ egions Ri connexes (en un sens ` a pr´ eciser) • Chaque r´ egion doit satisfaire une propri´ et´ e P(Ri ) Dualit´ e contour/r´ egion Computer vision -Segmentation and contours detection- (Week 2-4) (3/18) M. Hachama (hachamam@gmail.com)
4. Introduction Contours Segmentation Qu’est ce que la segmentation ? Dualit´ e contour/r´ egion Computer vision -Segmentation and contours detection- (Week 2-4) (3/18) M. Hachama (hachamam@gmail.com)
5. Introduction Contours Segmentation Qu’est-ce qu’un contour ? • C’est une fronti` ere qui s´ epare deux objets dans une image. • Une discontinuit´ e de l’image. • Variation brusque et forte de l’intensit´ e. Computer vision -Segmentation and contours detection- (Week 2-4) (4/18) M. Hachama (hachamam@gmail.com)
6. Introduction Contours Segmentation Qu’est-ce qu’un contour ? • Un contour est une variation brusque et forte de l’intensit´ e. Computer vision -Segmentation and contours detection- (Week 2-4) (4/18) M. Hachama (hachamam@gmail.com)
7. Introduction Contours Segmentation Qu’est-ce qu’un contour ? • Un contour est une variation brusque et forte de l’intensit´ e. Computer vision -Segmentation and contours detection- (Week 2-4) (4/18) M. Hachama (hachamam@gmail.com)
8. Introduction Contours Segmentation Qu’est-ce qu’un contour ? • Types de contours Computer vision -Segmentation and contours detection- (Week 2-4) (4/18) M. Hachama (hachamam@gmail.com)
9. Introduction Contours Segmentation Qu’est-ce qu’un contour ? • Types de contours Computer vision -Segmentation and contours detection- (Week 2-4) (4/18) M. Hachama (hachamam@gmail.com)
10. Introduction Contours Segmentation Qu’est-ce qu’un contour ? • Types de contours Computer vision -Segmentation and contours detection- (Week 2-4) (4/18) M. Hachama (hachamam@gmail.com)
11. Introduction Contours Segmentation D´ etecteurs simples • D´ etection de points : Application du masque suivant et seuillage de l’image r´ esultat    −1 −1 −1 −1 8 −1 −1 −1 −1    Computer vision -Segmentation and contours detection- (Week 2-4) (5/18) M. Hachama (hachamam@gmail.com)
12. Introduction Contours Segmentation D´ etecteurs simples • D´ etection de lignes : Filtres d´ efinissant 4 directions E-W, NW-SE, N-S, NE-SW    −1 −1 −1 2 2 2 −1 −1 −1       2 −1 −1 −1 2 −1 −1 −1 2       −1 2 −1 −1 2 −1 −1 2 −1       −1 −1 2 −1 2 −1 2 −1 −1    Computer vision -Segmentation and contours detection- (Week 2-4) (5/18) M. Hachama (hachamam@gmail.com)
13. Introduction Contours Segmentation D´ etecteurs simples • D´ etection de lignes : Exemple Computer vision -Segmentation and contours detection- (Week 2-4) (5/18) M. Hachama (hachamam@gmail.com)
14. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • D´ eriv´ ee d’une image et contours Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
15. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • D´ eriv´ ee d’une image et contours • Norme : G = G2 x + G2 y ∼ Gx + Gy • Direction : θ = arctan(Gy /Gx ) Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
16. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • Exemple de d´ etection de contours Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
17. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • Approximations simples de la d´ eriv´ ee discr` ete −1 1 −1 1 −1 0 1 −1 0 1 • Filtres de Roberts : d´ eriv´ ees directionnelles 1 0 0 −1 0 1 −1 0 Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
18. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • Filtres de Prewitt : lissage de l’image + d´ eriv´ ee de l’image −1 −1 −1 0 0 0 1 1 1 −1 0 1 −1 0 1 −1 0 1 • Moyenneur + D´ eriv´ ee    −1 0 1 −1 0 1 −1 0 1    =    1 1 1    ∗ (−1 0 1) D´ etection des contours moins sensible au brui. Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
19. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • Filtres de Sobel −1 −2 −1 0 0 0 1 2 1 −1 0 1 −2 0 2 −1 0 1 • Gaussienne + D´ eriv´ ee    −1 0 1 −2 0 1 −1 0 1    =    1 2 1    ∗ (−1 0 1) D´ etection des contours moins sensible au bruit Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
20. Introduction Contours Segmentation M´ ethodes d´ erivatives : Gradient • Exemple de d´ etection de contours Computer vision -Segmentation and contours detection- (Week 2-4) (6/18) M. Hachama (hachamam@gmail.com)
21. Introduction Contours Segmentation M´ ethodes d´ erivatives : Laplacien • D´ etection des contours Computer vision -Segmentation and contours detection- (Week 2-4) (7/18) M. Hachama (hachamam@gmail.com)
22. Introduction Contours Segmentation M´ ethodes d´ erivatives : Laplacien • Plusieurs approximations discr` etes du Laplacien existent.    0 1 0 1 −4 1 0 1 0       1 1 1 1 −8 1 1 1 1       1 4 1 4 −20 4 1 4 1    • Isotropique : Sym´ etrique par rapprt ` a la rotation. Computer vision -Segmentation and contours detection- (Week 2-4) (7/18) M. Hachama (hachamam@gmail.com)
23. Introduction Contours Segmentation M´ ethodes d´ erivatives : Laplacien • Le Laplacien, comme tous les d´ etecteurs de contours, est tr` es sensible aux bruits. On pr´ ef` ere lisser l’image avant de d´ etecter les contours. Pour ce faire, on combine un lissage Gaussien avec le Laplacien. La Gaussienne lisse l’image et rend les contours flous, mais conserve leurs positions Le Laplacien donne les passages par z´ ero aux contours • Laplacien de Gaussienne (LoG) LoG ∗ I = ∆ ∗ G ∗ I = ∆G ∗ I LoG(x, y) = − 1 πσ4 1 − x2 + y2 2σ2 e−x2+y2 2σ2 Computer vision -Segmentation and contours detection- (Week 2-4) (7/18) M. Hachama (hachamam@gmail.com)
24. Introduction Contours Segmentation M´ ethodes d´ erivatives : Laplacien • Filtre Laplacien Computer vision -Segmentation and contours detection- (Week 2-4) (7/18) M. Hachama (hachamam@gmail.com)
25. Introduction Contours Segmentation M´ ethodes d´ erivatives : Laplacien • Contours = passage par z´ ero du Laplacien Computer vision -Segmentation and contours detection- (Week 2-4) (7/18) M. Hachama (hachamam@gmail.com)
26. Introduction Contours Segmentation M´ ethodes d´ erivatives : Laplacien • Comparaison des d´ etecteurs des contours Aucun op´ erateur n’est parfait pour d´ etecter les contours. En pratique, on obtient des contours incomplets il y a des pixels superflus il y a des manques il y a des erreurs dans la position et l’orientation des pixels contours Chacun semble avoir sa pr´ ef´ erence pour une m´ ethode ou une autre. Un op´ erateur de d´ etection de contour n’est qu’une premi` ere ´ etape dans la chaˆ ıne de segmentation. Computer vision -Segmentation and contours detection- (Week 2-4) (7/18) M. Hachama (hachamam@gmail.com)
27. Introduction Contours Segmentation M´ ethode de Canny • Filtre optimal pour la d´ etection des contours • Filtre en plusieurs ´ etapes (pas seulement une convolution) • ´ Etant donn´ es • un mod` ele de contour (marche) • un mod` ele de bruit (blanc gaussien) • Caract´ eriser les performances en termes de : • d´ etection : surtout pour les contours faibles • localisation : contour d´ etect´ e proche du contour r´ eel • r´ eponse unique (un contour = une seule r´ eponse) Computer vision -Segmentation and contours detection- (Week 2-4) (8/18) M. Hachama (hachamam@gmail.com)
28. Introduction Contours Segmentation M´ ethode de Canny • 1. Appliquer un filtre Gaussien sur l’image • Filtre passe-bas pour enlever le bruit • 2. Calculer l’intensit´ e du gradient dans l’image • Filtre de Sobel en X et Y • Calcul de la norme |G| = |Gx | + |Gy | • 3. Calculer les directions du gradient dans l’image • Direction du gradient θ = arctan(Gy /Gx ) • Arrondi des directions par multiples de 45 degr´ es Computer vision -Segmentation and contours detection- (Week 2-4) (8/18) M. Hachama (hachamam@gmail.com)
29. Introduction Contours Segmentation M´ ethode de Canny • 4. Suppression des non-maxima • Si la norme du gradient en un pixel est inf´ erieure ` a la norme du gradient d’un de ses 2 voisins le long de la direction du gradient, alors mettre la norme pour le pixel ` a z´ ero. Computer vision -Segmentation and contours detection- (Week 2-4) (8/18) M. Hachama (hachamam@gmail.com)
30. Introduction Contours Segmentation M´ ethode de Canny • 5. Seuillage des contours (hyst´ er´ esis) • Utilise deux seuils : un seuil haut (Sh) et un seuil bas (Sb) • Pour chaque pixel • Si ∇I(x, y) < Sb, alors le pixel est mis ` a z´ ero (non-contour). • Si ∇I(x, y) > Sh, alors le pixel est contour. • Si Sb ≤ ∇I(x, y) ≤ Sh, alors le pixel est contour s’il est connect´ e ` a un autre pixel d´ ej` a accept´ e comme contour. Computer vision -Segmentation and contours detection- (Week 2-4) (8/18) M. Hachama (hachamam@gmail.com)
31. Introduction Contours Segmentation M´ ethode de Canny • Exemple Computer vision -Segmentation and contours detection- (Week 2-4) (8/18) M. Hachama (hachamam@gmail.com)
32. Introduction Contours Segmentation Quel filtre choisir pour les contours ? • Aucun op´ erateur n’est parfait pour d´ etecter les contours • En pratique, on obtient des contours incomplets • il y a des pixels superflus • il y a des manques • il y a des erreurs de position et d’orientation des pixels contours • Chacun semble avoir sa pr´ ef´ erence pour une m´ ethode ou une autre • Un op´ erateur de d´ etection de contour n’est qu’une premi` ere ´ etape dans la chaˆ ıne de segmentation Computer vision -Segmentation and contours detection- (Week 2-4) (9/18) M. Hachama (hachamam@gmail.com)
33. Introduction Contours Segmentation Quel filtre choisir pour les contours ? • Il existe des approches globales pour les contours • On ne recherche pas seulement des pixels contours • On cherche le contour au complet • On cherche plusieurs pixels correspondant ` a un contour • Comment d´ efinir le contour ? Probl` eme ? • Diff´ erentes techniques • Ici : Transform´ ee de Hough Computer vision -Segmentation and contours detection- (Week 2-4) (9/18) M. Hachama (hachamam@gmail.com)
34. Introduction Contours Segmentation M´ ethode de Hough • Approche globale : repr´ esentation des droites par des points • Plan x − y : yi = axi + b • Une inf. de lignes passent par (xi , yi ) et une seule pour (a, b) • Plan param´ etrique a − b : b = −xi a + yi • Une seule ligne pour (xi , yi ) et une inf. passent par (a, b) Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
35. Introduction Contours Segmentation M´ ethode de Hough • Principe de la transform´ ee de Hough • Cellules d’accumulation - Matrice (a,b) • On construit une image des votes • chaque point permet de voter pour une droite particuli` ere • Les droites recevant le plus de votes sont conserv´ ees Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
36. Introduction Contours Segmentation M´ ethode de Hough • 1. D´ etection des contours (Gradient, Laplace, ...) • 2. Pour chaque (xi , yi ) du plan x − y (retenu par le d´ etecteur) nous calculons pour toutes les valeurs de a la valeur de b r´ esultante : On obtient une droite dans le plan a − b • Le nombre de valeurs dans chaque cellule a’, b’ est le nombre de points du plan x-y qui existent sur chacune des lignes b = - x a + y du plan param´ etrique a-b. • 3. Les points de croisement des droites dans le plan a-b indiquent les vraies droites existantes dans le plan x-y Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
37. Introduction Contours Segmentation M´ ethode de Hough • Probl` eme : la pente approche l’infinie pour des lignes qui approchent la verticale ! • Solution : repr´ esentation sous forme polaire ρ = x cos θ + y sin θ Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
38. Introduction Contours Segmentation M´ ethode de Hough • Application Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
39. Introduction Contours Segmentation M´ ethode de Hough • Application Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
40. Introduction Contours Segmentation M´ ethode de Hough • Application Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
41. Introduction Contours Segmentation M´ ethode de Hough • Application Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
42. Introduction Contours Segmentation M´ ethode de Hough • Application Computer vision -Segmentation and contours detection- (Week 2-4) (10/18) M. Hachama (hachamam@gmail.com)
43. Introduction Contours Segmentation Seuillage • Le seuillage est une m´ ethode simple et tr` es populaire pour le traitement des images num´ eriques • Ce n’est pas une m´ ethode de segmentation en r´ egions • Approche pixel (pas r´ egion ni contour) • Mais on l’utilise souvent en segmentation (avec post- traitements) • Le seuillage peut ˆ etre • Global : un seuil pour toute l’image • Local : un seuil pour une portion de l’image • Adaptatif : un seuil s’ajustant selon les parties de l’image Computer vision -Segmentation and contours detection- (Week 2-4) (11/18) M. Hachama (hachamam@gmail.com)
44. Introduction Contours Segmentation Seuillage global Principe de base • Seuillage de base (2 classes) : • Si valeur(pixel) ≥ seuil alors valeur(pixel) = 1 • Si valeur(pixel) < seuil alors valeur(pixel) = 0 • Le r´ esultat du seuillage est une image binaire • 0 ou 1 (qu’on transforme parfois en 0 :255 pour l’affichage) • Probl` eme : choix du seuil ! Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
45. Introduction Contours Segmentation Seuillage global • Choix du seuil : Seuillage de l’histogramme Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
46. Introduction Contours Segmentation Seuillage global • Choix du seuil : Seuillage d’histogramme simple Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
47. Introduction Contours Segmentation Seuillage global • Choix du seuil : Seuillage de l’histogramme • Avantages • Universel, temps r´ eel, simplicit´ e • Fonctionne bien sur des histogrammes multi-modaux • Inconv´ enients • Connaˆ ıtre le nombre de classes. • Apparition de faux ´ el´ ements (aucune prise en compte de la composante spatiale). • Nombre de modes souvent nombre de classes attendu. Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
48. Introduction Contours Segmentation Seuillage global • Choix du seuil : Seuillage de l’histogramme • Comment trouver le bon seuil (T) ? • Une valeur obtenue par tests • La valeur moyenne des tons de gris • La valeur m´ ediane entre le ton maximum et le ton minimum • Une valeur qui balance les deux sections de l’histogramme • Il existe des algorithmes automatiques pour trouver le seuil : Moyennage, Otsu, Kittler, ... Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
49. Introduction Contours Segmentation Seuillage global • M´ ethode de moyennage 1 Choix d’un seuil initial S = S0. 2 Repartir les pixels en deux classes en utilisant S. 3 Mettre ` a jour le seuil S comme la moyenne des deux moyennes des niveaux de gris des deux classes S = m1+m2 2 . 4 Si |S − S | < δ, arrˆ eter. S = S . Sinon, S = S et retourner ` a l’´ etape 2. Img. init. (S0 = 76), Segm./S1 = 174.66+17.7 2 = 96.18, Segm. finale Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
50. Introduction Contours Segmentation Seuillage global • M´ ethode d’Otsu Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
51. Introduction Contours Segmentation Seuillage global • M´ ethode d’Otsu • Exemple : un et deux seuils Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
52. Introduction Contours Segmentation Seuillage global • Exemple : seuillage d’images bruit´ ees En pointill´ e : Histo. original - Ligne pleine : Histo. apr` es debruitage. Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
53. Introduction Contours Segmentation Seuillage global • Exemple : seuillage d’images bruit´ ees Segmentation avant et apr` es debruitage. Computer vision -Segmentation and contours detection- (Week 2-4) (12/18) M. Hachama (hachamam@gmail.com)
54. Introduction Contours Segmentation Seuillage local ou adaptatif • Seillage globale : probl` emes Computer vision -Segmentation and contours detection- (Week 2-4) (13/18) M. Hachama (hachamam@gmail.com)
55. Introduction Contours Segmentation Seuillage local ou adaptatif • Seillage globale : probl` emes Computer vision -Segmentation and contours detection- (Week 2-4) (13/18) M. Hachama (hachamam@gmail.com)
56. Introduction Contours Segmentation Seuillage local ou adaptatif • On divise l’image en sous-images • On seuille chaque sous-image ind´ ependamment • Les 4 sous-images de coins ne sont pas trait´ ees car var. < 100 Computer vision -Segmentation and contours detection- (Week 2-4) (13/18) M. Hachama (hachamam@gmail.com)
57. Introduction Contours Segmentation Seuillage local ou adaptatif • Exemple Computer vision -Segmentation and contours detection- (Week 2-4) (13/18) M. Hachama (hachamam@gmail.com)
58. Introduction Contours Segmentation Croissance de r´ egions • Faire croˆ ıtre une r´ egion en commenc ¸ant par une petite r´ egion (un pixel par exemple) • Crit` ere d’ajout d’un pixel ` a une r´ egion : • La diff´ erence entre l’intensit´ e du nouveau pixel et la moyenne des intensit´ es des pixels de la r´ egion ne d´ epasse pas un seuil pr´ ed´ efini δ. Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
59. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
60. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
61. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
62. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
63. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
64. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
65. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
66. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
67. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
68. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
69. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
70. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
71. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
72. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
73. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
74. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
75. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
76. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
77. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
78. Introduction Contours Segmentation Croissance de r´ egions • Exemple 1 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
79. Introduction Contours Segmentation Croissance de r´ egions • Exemple 2 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
80. Introduction Contours Segmentation Croissance de r´ egions • Exemple 2 Computer vision -Segmentation and contours detection- (Week 2-4) (14/18) M. Hachama (hachamam@gmail.com)
81. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • ´ Etape de division (split) : Diviser r´ ecursivement tout bloc non-homog` ene selon un pr´ edicat d´ efini : variance, max-min, ... • La division d’un bloc donne 4 sous-blocs. • Les attributs de chaque sous-bloc sont recalcul´ es. • ´ Etape de fusion (merge) : Regrouper les blocs adjacents repr´ esentant des r´ egions homog` enes selon un pr´ edicat d´ efini. • Exemple. Crit` ere d’homog´ en´ eit´ e : Une r´ egion est homog` ene si tous ses pixels ont la mˆ eme intensit´ e Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
82. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
83. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
84. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
85. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
86. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
87. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
88. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
89. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
90. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
91. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
92. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
93. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
94. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de Fusion Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
95. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
96. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
97. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemple : ´ Etape de division Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
98. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemples : Diff´ erents seuils Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
99. Introduction Contours Segmentation Division-fusion (Split-and-Merge) • Exemples : Diff´ erents seuils Computer vision -Segmentation and contours detection- (Week 2-4) (15/18) M. Hachama (hachamam@gmail.com)
100. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Limite du seuillage basique et la d´ etection des contours Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
101. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Limite du seuillage basique et la d´ etection des contours Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
102. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Limite du seuillage basique et la d´ etection des contours Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
103. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Limite du seuillage basique et la d´ etection des contours Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
104. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Algorithme de partage des eaux (objets qui se chevauchent). Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
105. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Visualisation de l’image en 3D : ton de gris en z Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
106. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • ”Compl´ ementer” les valeurs pour cr´ eer des zones inondables Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
107. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • ”Infiltrer” les cavit´ es des zones inondables Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
108. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • En 1D Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
109. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • En 1D Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
110. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • 1. Calculer la transformation de la distance euclidienne : pour chaque pixel, calculer la distance au plus proche 0 (pixel du fond, background pixel) • 2. D´ eterminer les pics (i.e., maxima locaux) de la matrice des distance. Une distance minimale (exp. 20 pixels) entre les pics est respect´ ee. • 3. Appliquer l’algorithme de ligne de partage des eaux. Le r´ esultat est une image de segmentation (labels). Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
111. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Exemples Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
112. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Exemples Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
113. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Transformation de distance • Image binaire : distance minimale de chaque pixel ` a la composante ”objet” Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
114. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) • Transformation de distance • Image binaire : distance minimale de chaque pixel ` a la composante ”objet” • Temps de calculs ´ elev´ es. Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
115. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) Algorithme rapide pour calculer des distances approximatives • 1. L’image initiale est ´ etendue par z´ ero-padding pour application d’un filtre 3 × 3. Ensuite, 0 est remplac´ e par ∞ et 1 est remplac´ e par 0, ce qui donne une matrice initiale de distance Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
116. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) Algorithme rapide pour calculer des distances approximatives • 2. Un masque direct est appliqu´ e : du coin sup´ erieur gauche, de gauche ` droite et haut vers le bas. Pour chaque pixel, on calcul la somme du masque avec l’image et on la valeur du pixel est mise a jours avec le minimum de l’imagette obtenue. Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
117. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) Algorithme rapide pour calculer des distances approximatives • R´ esultat de l’application du premier filtre direct Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
118. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) Algorithme rapide pour calculer des distances approximatives • 3. Un masque inverse est appliqu´ e comme pr´ ec´ edemment : de droite ` a gauche et d’en bas vers le haut, avec le filtre 0 1 1 ∞ Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
119. Introduction Contours Segmentation Ligne de partage des eaux (Watershed) Algorithme rapide pour calculer des distances approximatives • Autre choix des filtres et r´ esultats • On divise toutes les valeurs par 3. La 1` ere valeur est 14/3 = 4.6667 4.4721. Computer vision -Segmentation and contours detection- (Week 2-4) (16/18) M. Hachama (hachamam@gmail.com)
120. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Affecter un num´ ero unique (´ etiquette) pour chaque r´ egion • Effectuer deux parcours de l’image Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
121. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
122. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
123. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
124. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
125. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
126. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
127. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Premier parcours : de gauche ` a droite et de haut vers le bas • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi ses voisins haut et gauche ou bien une nouvelle ´ etiquette. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
128. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Deuxi` eme parcours : de droite ` a gauche et d’en bas vers le haut • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi la sienne et celles ses voisins bas et droite. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
129. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Deuxi` eme parcours : de droite ` a gauche et d’en bas vers le haut • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi la sienne et celles ses voisins bas et droite. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
130. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Deuxi` eme parcours : de droite ` a gauche et d’en bas vers le haut • On affecte ` a chaque pixel d’une r´ egion la plus petite ´ etiquette parmi la sienne et celles ses voisins bas et droite. Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
131. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • En deux parcours, nous avons termin´ e l’´ etiquetage des r´ egions. Parfois, il faut plus de deux parcours. Exemple : r´ egion en spirale ! • On continue les parcours, dans un sens puis l’autre, jusqu’` a ce qu’il n’y ait plus de changement d’´ etiquettes Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
132. Introduction Contours Segmentation ´ Etiquetages de composantes connexes • Il est possible de ne faire qu’un seul parcours • Gestion d’une table d’´ equivalence d’´ etiquettes • Mise ` a jour r´ ecursive des ´ etiquettes lorsque 2 ´ etiquettes se ”rencontrent” • Pour ´ etiqueter des contours, on peut utiliser le mˆ eme algorithme (avec la 8-connexit´ e) Computer vision -Segmentation and contours detection- (Week 2-4) (17/18) M. Hachama (hachamam@gmail.com)
133. Introduction Contours Segmentation Classification • Classification =r´ epartition d’un ensemble d’objets (pixels) en diff´ erents groupes (classes) en fonctions de leurs caract´ eristiques ou features (Niveau de gris, couleur, gradient, statistique locale, ...) • Types de classification • Supervis´ ee : les caracteristiques des classes sont connues a priori. Exp, : distance minimale, k-nearest neighbors, statistiques (distributions de probabilit´ e des mod` eles), ... • Non-supervis´ ee (regroupement - clustering-) : La classification est faites sur les donn´ ees et ` a partir des donn´ ees directement. Computer vision -Segmentation and contours detection- (Week 2-4) (18/18) M. Hachama (hachamam@gmail.com)
134. Introduction Contours Segmentation Classification • The k-Nearest Neighbors Classifier • Les classes sont d´ efinies par quelques ´ el´ ements dits de r´ ef´ erence. • Pour un nouveau objet (pixel), on d´ etermine les k plus proches objets de r´ ef´ erence. • Chaque nouvel objet est associ´ e ` a la classe de la majorit´ e de ses voisins. • The Minimum-Distance-to-Mean Classifier • Les classes sont d´ efinies par leurs centres. • Chaque nouvel objet est associ´ e ` a la classe de plus proche centre. Computer vision -Segmentation and contours detection- (Week 2-4) (18/18) M. Hachama (hachamam@gmail.com)
135. Introduction Contours Segmentation Classification : K-means • On veut diviser les points en k groupes (clusters) • k est donn´ e ` a l’avance (un param` etre de l’algorithme) • On d´ efinit le centre d’un groupe comme la moyenne des ´ el´ ements (pixels) du groupe Computer vision -Segmentation and contours detection- (Week 2-4) (18/18) M. Hachama (hachamam@gmail.com)
136. Introduction Contours Segmentation Classification : K-means • 1. Partitionnement des donn´ ees en k sous-ensembles (non vides) • 2. Calcul des centres des groupes de la partition courante • 3. Les donn´ ees sont affect´ ees au groupe dont le centre leur est le plus proche • 4. Retour ` a l’´ etape 2 • Arrˆ et lorsque les groupes sont ∼ constants Computer vision -Segmentation and contours detection- (Week 2-4) (18/18) M. Hachama (hachamam@gmail.com)
137. Introduction Contours Segmentation Classification Computer vision -Segmentation and contours detection- (Week 2-4) (18/18) M. Hachama (hachamam@gmail.com)
138. Introduction Contours Segmentation Classification Computer vision -Segmentation and contours detection- (Week 2-4) (18/18) M. Hachama (hachamam@gmail.com)