Discussion :

[contremaitre]

Bonjour

J'aimerai, à partir d'images vidéo, estimer le nombre de personnes présentes dans une zone (zone assez petite, nombre de personnes entre 0 et 3 par exemple).

Essais :
* soustraction image actuelle / image de référence. Problème : trop sensible aux changement de luminosité du capteur video.

* soustraction entre deux images successives (problème : depends de la vitesse du mouvement : si peu de mouvement, différence très faible voire nulle, si mouvement trop rapide, différence trop forte).

* detection de bord sur chaque image puis soustraction entre deux images de bord successives -> j'obtient les bords de la silhouette.

Pour estimer le nombre de personne : soit faire une estimation de la surface de présence, soit essayer de découper des zones et compter (mais probleme si deux personnes trop proches).

Pour faire une estimation de la surface de présence, le problème c'est qu'il faudrait déterminer une zone à partir de la détection de bord par exemple.
Mais les contours ne sont pas forcément fermés, et essayer de les fermer prends trop de temps.
J'avais pensé à calculer des ellipses englobant les personnes et calculer leurs surfaces, mais je n'y suis pas encore arrivé.

Je bloque donc sur :
- Découpage des zones de mouvement pour ensuite compter
- Calcul d'une ellipse englobante

Et avez vous d'autres idées?

merci

[ToTo13]

Bonjour,

la meilleure idée est sans doute de faire de la bibliographie sur le sujet. C'est un problème encore largement traité en recherche et tu trouveras un bon nombre d'articles pour t'orienter.

Sinon, les soustractions d'images fonctionnent rarement pour toutes les raisons que tu viens de citer.
Donc comme tu l'as compris, il vaut beaucoup mieux compter le nombre de visages que tu as sur UNE image. Là encore, encore plus de bibliographie disponible sur le sujet et en plus il a été traité sur le forum et PseudoCode à donné des liens me semble t-il.
Par contre, il faut faire attention au placement de ta caméra : au dessus => pas de visages mais des têtes, à l'horizontale => des visages mais certains sont masqués, ... Donc dis nous dans quelle situation tu es ?

[pseudocode]

Pour faire une "background substraction" il faut conserver un pool d'image (circulaire dans le temps) . Le background est calculé en faisant un filtrage median sur un meme pixel au cours du temps.

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
 
...
Image(t=...)  <-- vieilles images 
Image(t=...)  <-- ( a supprimer )
-----------
Image(t=-N)   <--
...           <--
Image(t=-3)   <-- Pool des N dernieres images
Image(t=-2)   <-- ( a conserver )
Image(t=-1)   <--
-----------
Image(t=0)   <--- nouvelle image
 
 
 
Background[x][y] = median( Image(t=-1)[x][y], ... , Image(t=-N)[x][y] )
 
Foreground[x][y] = Image(t=0)[x][y] - Background[x][y]

[contremaitre]

merci pour vos premieres réponse.
Pour la situation je pensai l'avoir dit, j'ai oublié : c'est en vue de dessus, donc je ne vois pas les visages, mais c'est pour éviter une personne caché derriere une autre.

Pour le background substraction : j'ai déjà essayé ca aussi, c'est pas trop mal pour régler les problème de changement de luminosités, mais une personne immobile sera trop rapidement effacé. Et ca ne regle pas les problèmes de comptages une fois les zones de présences détectés.

[pseudocode]

Pour le background substraction : j'ai déjà essayé ca aussi, c'est pas trop mal pour régler les problème de changement de luminosités, mais une personne immobile sera trop rapidement effacé.

Utilise un hystérésis: une fois que la cible est detectée (|foreground|>seuilHaut) elle reste marquée jusqu'a ce qu'elle disparaisse (|foreground|<seuilBas).

Et ca ne regle pas les problèmes de comptages une fois les zones de présences détectés.

Tu as essayé quelles methodes de détection de blob ?

[contremaitre]

Tu as essayé quelles methodes de détection de blob ?

Aucune encore, je ne connaissais pas.
Laquelle me conseille tu, sachant que mon problème va etre de détecter deux personnes assez proches? Et que la vitesse de calcul est importante.

Merci

[pseudocode]

Aucune encore, je ne connaissais pas.Laquelle me conseille tu, sachant que mon problème va etre de détecter deux personnes assez proches? Et que la vitesse de calcul est importante.

Tout dépend de tes images.

Les detecteurs te donnent des zones (rectangulaires, elliptiques,...) qui contiennent "probablement" une cible. A toi de décider si la zone contient en réalité 0, 1 ou plusieurs cibles.

Pour ton probleme de proximité, tu peux commencer par définir une taille maximum pour une zone. Si la zone est trop grande, tu peux considerer qu'il y a plusiseurs cibles dedans.

Pour la vitesse, pas de probleme. C'est tres rapide: quelques centaines de millisecondes...

[contremaitre]

très bien, je regarde ca alors.
Mais quelques centaines de millisecondes ca dépend de la taille des images par contre je suppose.
Dans une video à 25 images secondes il y a seulement 40 ms pour les calculs
Merci

[pseudocode]

très bien, je regarde ca alors.
Mais quelques centaines de millisecondes ca dépend de la taille des images par contre je suppose.
Dans une video à 25 images secondes il y a seulement 40 ms pour les calculs
Merci

Il n'y a peut-etre pas besoin de raffraichir le compteur avec une résolution de 1/25 ème de seconde....

[contremaitre]

Il n'y a peut-etre pas besoin de raffraichir le compteur avec une résolution de 1/25 ème de seconde....

effectivement.
Pour l'instant je fait des essais à 10 img secondes, mais c'est vrai que je peux refléchir à descendre encore selon la méthode choisi

[themadmax]

Voila un petit soft, assez basic :
http://www.codeproject.com/KB/audio-...Detection.aspx
avec background auto. ( 1 niveau par image )
Fait en C# et utilise la lib AForge http://code.google.com/p/aforge/

[contremaitre]

Pour la détection de blob ca semble interessant, mais la littérature que j'ai lu sur la détection de personnes en fait réference sans l'expliquer.
Et j'ai un peu du mal avec les notions trop mathématique comme ici : http://en.wikipedia.org/wiki/Blob_detection

De plus dans mon cas la détection de blob n'a pas besoin d'etre très performante car ca sera sur des images binaires (pixels à 0 ou 1, grace à un seuillage).
Mais j'aimerai que ca soit des blob elliptiques et non rectangulaires.

Si vous avez des ressources à me proposer je suis preneur.

Merci

[pseudocode]

Ah ces matheux de wikipedia, toujours a compliquer les trucs simples...

Bon alors en gros, un blob c'est un "paquet" de pixels a "1" au milieu d'une zone de pixels a "0".

Un exemple de détecteur de blob simpliste, c'est un filtre avec deux cercles concentriques:
- on compte les pixels à 1 dans le cercle central
- on compte les pixels à 0 dans la couronne (entre les 2 cercles)

Si ces 2 nombres sont élevés, alors le contenu du cercle central est un blob (beaucoup de 1 entourés par beaucoup de 0)

Après on peut raffiner le procédé en utilisant des ratio "pixels 1 / total pixel" au lieu de comptage absolu. On peut également pondérer la valeur des pixels suivant qu'on est proche/loin des bords des cercles. Et puis on peut faire varier le rayon des cercles pour trouver le rayon qui "maximise" la valeur des ratio.

Transcrit en langage mathématique, vous obtenez le détecteur DOG (difference of gaussian)... si vous regardez la forme de la courbe DOG, on peut voir les 2 zones: pixel="1" au centre (coef positif), pixel="0" dans la couronne (coef négatif), zéro ailleurs.

[contremaitre]

Merci,

Alors j'ai trouvé un algo qui à l'air assez simple et rapide :

Le principe est de parcourir l'image ligne par ligne.
Pour chaque ligne on numérote différement chaque région ayant des pixels adjacents. Mais les régions qui se superposent aux régions de la ligne précedente récuperent le numéro de la région précedente correspondante.

Cet algo est expliqué ici : Blob detection V: growing regions algorithm

Et cette librairie d'opencv d'apres ce que j'ai pu comprends utilise un peu le meme principe (voir section algorithme) : CVbloblist

De plus, je voulais pouvoir déconnecter deux régions pas assez connectés, et ca doit pouvoir etre possible en comptant le nombre de pixels par lequels elles sont connectés au fur et à mesure.

Exemple
000000
110011
111111
110011
110011
000000

Ici on pourra compter seulement deux pixels entre les regions a gauche et a droite.

Voila, que pensez vous de cette méthode d'extraction de blob, et en connaissez vous d'autres interessantes ?

Pseudocode -> quand tu parles de filtres, je suppose qu'il faut faire autant de filtres que de taille et formes de blob qu'on veut detecter?
Le problème de l'algo dont je parle ici c'est qu'il est "rigide", si il manque quelques pixels on aura deux regions, alors qu'avec un filtre on peut detecter des régions "parsemés" de pixels à 1.
Exemple Cette région pourrait etre considéré comme un blob non? :
00000000
00101010
00010100
00110110
00000000
00111010
00000000
Merci

[pseudocode]

Alors j'ai trouvé un algo qui à l'air assez simple et rapide :

Le principe est de parcourir l'image ligne par ligne.
Pour chaque ligne on numérote différement chaque région ayant des pixels adjacents. Mais les régions qui se superposent aux régions de la ligne précedente récuperent le numéro de la région précedente correspondante.

oui, c'est une variante du "Scanline Fill".

Pseudocode -> quand tu parles de filtres, je suppose qu'il faut faire autant de filtres que de taille et formes de blob qu'on veut detecter?

Oui, si tu utilises des filtres sous formes de masques binaires.

Mais c'est la que la magie des mathématiques intervient en transformant ces masques en fonctions à plusieurs parametres. Au lieu de construire des masques de toutes les tailles/orientations possibles, on fait varier les parametres de la fonction.

Généralement il suffit de faire varier un seul type de parametre: l'echelle ("t"). Comme la fonction est généralement "sympathique", on peut utiliser des methodes de convergence rapide pour trouver le meilleur "t" (newton,...). Ensuite, en jouant avec les valeurs/vecteurs propres on peut calculer directement l'orientation et la forme du blob (axes et taille de l'ellipse,...).

Les mathématiques sont nos amies.

Le problème de l'algo dont je parle ici c'est qu'il est "rigide", si il manque quelques pixels on aura deux regions, alors qu'avec un filtre on peut detecter des régions "parsemés" de pixels à 1.
Exemple Cette région pourrait etre considéré comme un blob non? :

Oui, tout a fait. Avec un masque carré (5x5) + bordure de 1:

Code :

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

1
2
3
4
5
6
7
8
00000000
00101010
00010100
00110110
00000000
00111010
00000000

ratio de 1 dans le masque: 13/25 = 52%
ratio de 0 dans la bordure: 24/24 = 100%

[contremaitre]

ok merci
Et connais tu des exemples d'implementation de ces fonctions, ou des articles qui les expliquent, car je vois pas trop comment le faire moi meme.

Sinon je vais déjà commencer par la variante du "Scanline Fill" avec une dilatation pour essayer de boucher quelques trous.

[contremaitre]

Bon voilà l'algo que j'ai ecrit et que je vais essayer d'implementer.
Ce qui me fait un peu peur c'est la complexité ( O(n^4) ) n = largeur = hauteur de l'image

Alors je maintient deux listes de blob lors de mon parcours ligne par ligne:
Liste de blobs courants : les blobs qui sont encore connectés à ma ligne précedente.
Liste de blobs finaux : les blobs qui ne sont plus connectés.

Pour chaque blob courrant : deux listes :
LISTE1 : liste de points de début/fin sur la ligne precedente.
LISTE2 : liste de points de début/fin sur la ligne courante.

Exemple :
0123456789
0111111110 A (ligne precedente)
0100000010 B (ligne courante)

LISTE1 = 1-8
LISTE2 = 1-1 ; 8-8

Maintenant l'algo :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Pour chaque ligne L O(n)
     Pour chaque pixel p de L  O(n)
          Si p-1 de L = 1 
               MAJ de ce blob (donc MAJ de la fin de LISTE2)
          Si p de L-1 = 1 
               Connecter au blob de p de L-1 (donc recherche dans LISTE1 et MAJ dans LISTE2) O(n^2)
          Sinon 
               Creer un nouveu blob dans liste courante.

     Supprimer blob non connectés a la ligne courante et les ajouter dans liste finale
     Pour les blobs toujours dans liste courante : LISTE1 <- LISTE2 et LISTE2 = NULL

Pour la complexité j'ai noté les pires.
Pour le O(n^2) c'est parce que la recherche du blob dans la liste courante est en O(n) (on peut avoir au maximum n/2 blob dans cette liste) et pour chaque blob il faut chercher dans la liste de debut/fin en (O(n) : ici aussi n/2 élément maximum dans cette liste).

Un point positif tout de meme : LISTE1 et LISTE2 sont automatiquement triés car j'ajoute les points dans l'ordre.

Voyez vous des amélioration à apporter ?

Sinon je suis toujours prenneur d'autres méthodes.

Merci

[pseudocode]

Pas mal pour un début... Maintenant regardons si ca marche correctement avec le cas suivant:

Code :

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

1
2
3
4
5
0123456789A
-----------
111     111
  111 111
    111

[contremaitre]

Pas mal pour un début... Maintenant regardons si ca marche correctement avec le cas suivant:

Code :

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

1
2
3
4
5
6
 
0123456789A
-----------
111     111
  111 111  
    111

Ha oui, merci. Il faut rajouter un test : si on a un blob avec un id de créé et qu'on rencontre un autre blob sur la ligne au dessus : il faut les fusionner.

Par conte je viens de tomber par hasard sur un autre algo pour récuperer les composantes connexes, dans ce cours page 5: images binaires
Il dit de parcourir l'image de gauche a droite et de haut en bas. On affecte une etiquette pour chaque pixel à 1. Cette étiquette sera : la plus petite étiquette entre le pixel haut ou gauche si ils existent, ou une nouvelle étiquette sinon.
Ensuite il faut faire une deuxieme passe :
Pour chaque pixel on lui affecte la plus petite étiquette parmiis les voisins bas et droite.

Il reste un probleme lors de composantes en spirales : a ce moment là il faut refaire des passes tant que des numeros changent. Mais on peut fixer une limite pour pas prendre trop de temps de calcul.

Mais je me pose la question de la complexité. Ce qui parait mieux c'est que les parcours sont seulement en O(k*n^2), k le nombre de passes necessaires... il n'y a pas de listes à parcourir.

Il parle aussi d'un parcours en une seule passe que j'ai pas bien compris. Je cite :

Il est possible de ne faire qu'un seul parcours :
- gestion d'une table d'equivalence d'etiquettes
- Mise a jours recursive des etiquettes lorsque 2 etiquettes se "rencontrent"

[pseudocode]

Bien... Je vois que tu avances a grand pas.

Le problème que tu cherches a résoudre s'appelle pompeusement "labelisation des composantes connexes" ().

Le 1er algorithme que tu décris s'appelle le "multi-pass line scanning" (ou qqc d'approchant). Il faut le passer jusqu'à ce que les labels ne changent plus.

Les variantes à 1 ou 2 passe s'appellent les algorithmes "union-find" et utilisent une table d'équivalence (ou table de connexions) et des arbres de décisions.

Pour ton problème, je te conseille le 1er algo qui est simple à mettre en oeuvre. Tu peux limiter le nombre de passe à 1 ou 2... Il y a peu de chance que tu ais des spirales dans ton cas, et meme si tu en as, elles seront juste labélisées comme des blobs distincts au lieu d'un seul blob.