Partage

[Exercice][Moyen] Connexité et comptage d'objets

Un peu de traitement d'images :p

Sujet résolu
22 juillet 2010 à 0:18:51

Salut !

Aujourd'hui je vous propose un exercice de niveau intermédiaire ayant trait au traitement d'images. N'ayez pas peur si vous n'en avez jamais fait, aucune connaissance dans ce domaine n'est requise pour mener cette tâche à bien : vous n'aurez besoin que de quelques neurones à cramer. :p

Images binaires et composantes connexes



Prenons par exemple le tableau suivant:

00000000000000000000
00111000000000000000
00011100000011101000
01111100000111011100
01100000000011111100
11000000000111111110
00001111000111111100
00111111100011111100
00000111000000110000
00000000000000000000


On va considérer que ce tableau est une image binaire : les pixels dont la valeur est égale à 0 font partie du fond, et ceux dont la valeur est 1 font partie d'un objet.

On fait l'hypothèse que si deux pixels de valeur 1 sont connexes, alors ils font partie d'un seul et même objet.

Connexes ? Ça veut dire quoi ?! o_O


Grosso-modo, cela veut dire qu'ils « se touchent ».
On peut définir 2 sortes de connexité :
  • La 4-connexité : deux pixels sont 4-connexes s'ils se suivent sur la même ligne ou la même colonne. Dans le petit tableau ci-dessous, les paires de pixels connexes sont : (A,B), (A,C), (A,D) et (A,E). A et F ne sont pas 4-connexes.
  • La 8-connexité : deux pixels sont 8-connexes s'ils se suivent verticalement, horizontalement ou en diagonale. Dans l'exemple ci-dessous, A et F sont 8-connexes.

0 B 0
C A D
0 E F


Pour cet exercice, nous considérons que deux pixels sont connexes s'ils sont 4-connexes.

On appelle une composante connexe de l'image, un ensemble de pixels tels que, si l'on prend 2 pixels quelconques dans cet ensemble, il est possible de trouver un chemin 4-connexe qui les relie. En gros, une composante connexe est une tache. ;)

Dans l'image ci-dessous, nous avons 2 composantes 4-connexes.
00000
01100
00011
00011


Votre mission, si vous l'acceptez...



Le but de cet exercice est de trouver combien d'objets différents se trouvent sur une image binaire.
Cela revient donc à compter le nombre de composantes 4-connexes de l'image.

Pour l'image du tout début de cet énoncé, votre code doit trouver 3 composantes connexes.
Vous avez le choix de représenter l'image dans votre programme de la manière que vous voulez, et d'utiliser toutes les bibliothèques que vous voulez, mais le plus sympa serait de trouver et d'implémenter un algorithme adéquat. :p

Indices



Si jamais vous planchez sur un algorithme pour résoudre ce problème, voici une petite piste :

Le plus simple, pour compter les objets, est de les "colorier", et de compter le nombre de couleurs que vous avez utilisées...


Bon courage !!
Zeste de Savoir, le site qui en a dans le citron !
22 juillet 2010 à 1:43:18

Une version qui recense les pixels faisant partie d'un objet (mis à 1) puis en supprime un, ses voisins et les voisins de ses voisins (supprime un objet) et recommence l'opération jusqu'à ce que tous aient été supprimés :
#!/usr/bin/env python3
# -*- coding: utf8 -*-

def count_objects(image):
    width, height = len(image[0]), len(image)
    objects_members = [(x, y) for x in range(width) for y in range(height) if image[y][x] == 1]
    objects_count = 0
    while objects_members != []:
        remove_object(objects_members, objects_members.pop(0))
        objects_count += 1
    return objects_count

def remove_object(objects_members, start_point):
    x, y = start_point
    connex = [(x - 1, y), (x, y - 1),
              (x + 1, y), (x, y + 1)]
    for point in connex:
        try:
            objects_members.remove(point)
            remove_object(objects_members, point)
        except ValueError:
            pass

if __name__ == "__main__":
    image = []
    while True:
        line = input()
        if line == "":
            break
        image.append([int(pixel) for pixel in line])
    print(count_objects(image))

Utilisation :
[dentuk@myhost python]$ ./connexe.py 
00000000000000000000
00111000000000000000
00011100000011101000
01111100000111011100
01100000000011111100
11000000000111111110
00001111000111111100
00111111100011111100
00000111000000110000
00000000000000000000

3
22 juillet 2010 à 2:05:07

Joli !
C'est le principe du remplissage (flood-fill).
C'est la solution que j'ai retenue aussi (sauf que je colorie explicitement les composantes connexes) :

[Python 2.6]
#! /usr/bin/env python
# -*- coding: utf-8 -*-

def flood_fill(image, objects, row, col, color):
    """
    Colorie la composante connexe de l'image image contenant le pixel situé à la
    ligne row et à la colonne col. La composante connexe est coloriée sur la
    carte 'objects' et effacée de l'image.

    image: image contenant les composantes connexes
    objects: carte des composantes connexes
    n_rows: nombre de lignes de l'image (hauteur)
    n_cols: nombre de colonnes de l'image (largeur)
    row: numéro de ligne de la racine
    col: numéro de colonne de la racine
    color: couleur (entier) avec laquelle on colorie la composante connexe

    """
    image[row][col] = 0
    objects[row][col] = color
    directions = (row+1, col), (row-1, col), (row, col+1), (row, col-1)
    for y, x in directions:
        if y >= 0 and x >= 0 and y < len(image) and x < len(image[0]):
            if image[y][x] == 1:
                flood_fill(image, objects, y, x, color)

def nb_objects(image):
    """
    Compte les objets dans une image binaire.
    Affiche la carte des composantes connexes et retourne le nombre d'objets.

    >>> nb_objects(IMAGE)
    00000000000000000000
    00111000000000000000
    00011100000022202000
    01111100000222022200
    01100000000022222200
    11000000000222222220
    00003333000222222200
    00333333300022222200
    00000333000000220000
    00000000000000000000
    3

    
    """
    rows, cols = len(image), len(image[0])
    objects = [[0 for _ in xrange(cols)] for _ in xrange(rows)]
    color = 0
    for row_idx in xrange(rows):
        for col_idx in xrange(cols):
            if image[row_idx][col_idx] == 1:
                color += 1
                flood_fill(image, objects, row_idx, col_idx, color)
    print '\n'.join([''.join([str(i) for i in row]) for row in objects])
    return color

if __name__ == '__main__':
    import doctest
    DATA = \
"""
00000000000000000000
00111000000000000000
00011100000011101000
01111100000111011100
01100000000011111100
11000000000111111110
00001111000111111100
00111111100011111100
00000111000000110000
00000000000000000000
"""
    LINES = [ligne for ligne in DATA.splitlines() if ligne != '']
    IMAGE = [[int(pixel) for pixel in ligne] for ligne in LINES]
    fail, _ = doctest.testmod()
    if fail == 0:
        print "WIN!"
    else:
        print "FAIL!"


Son inconvénient, c'est qu'elle ne laisse pas l'image intacte, mais c'est probablement la méthode la plus rapide.
Niveau récursivité, sa stabilité dépend de la taille de la plus grosse composante connexe de l'image...

Il existe aussi des solutions itératives, j'espère que quelqu'un en proposera une. :p

Edit: @Dentuk, j't'ai piqué ta méthode pour parcourir les différentes directions, elle allège beaucoup le code. :)

Sinon, pour la solution itérative je propose celle-ci:


#! /usr/bin/env python
# -*- coding: utf-8 -*-

def bind(point1, point2, connex):
    """
    Relie la composante contenant point1 à celle contenant point2
    point1, point2: les deux points
    connex: la liste des composantes connexes
    
    >>> connex = [[(1, 1), (1, 2)], [(1, 3)], [(2, 4), (2, 5)]]
    >>> bind((1, 2), (1, 3), connex)
    >>> connex 
    [[(1, 1), (1, 2), (1, 3)], [(2, 4), (2, 5)]]
    >>> bind((1, 0), (1, 1), connex)
    >>> connex
    [[(1, 1), (1, 2), (1, 3), (1, 0)], [(2, 4), (2, 5)]]

    """
    comp1 = []
    comp2 = []
    for component in connex:
        if point1 in component:
            comp1 = component
        if point2 in component:
            comp2 = component
    if comp1 == []:
       comp2.append(point1)
    elif comp2 == []:
        comp1.append(point2)
    elif comp1 != comp2:
        comp1 += comp2
        connex.remove(comp2)

def nb_objects(image):
    """
    Compte les objets dans une image binaire.
    Affiche la carte des composantes connexes et retourne le nombre d'objets.

    >>> nb_objects(IMAGE)
    00000000000000000000
    00111000000000000000
    00011100000022202000
    01111100000222022200
    01100000000022222200
    11000000000222222220
    00003333000222222200
    00333333300022222200
    00000333000000220000
    00000000000000000000
    3

    """
    rows, cols = len(image), len(image[0])
    connex = []
    
    # On parcourt toute l'image.  Si le pixel 'objet' courant n'a pas de voisin
    # au-dessus ou à gauche de lui on crée une nouvelle composante connexe,
    # sinon, l'ajoute à la composante de son voisin.
    for row in xrange(rows):
        for col in xrange(cols):
            left, up = 0, 0
            if image[row][col] == 0:
                continue
            if row > 0:
                up = image[row-1][col]
            if col > 0:
                left = image[row][col-1]
            if left == up == 0:
                connex.append([(row, col)])
            if left != 0:
                bind((row, col), (row, col-1), connex)
            if up != 0:
                bind((row, col), (row-1, col), connex)
    
    # on colorie l'image:
    color = 0
    for component in connex:
        color += 1
        for row, col in component:
            image[row][col] = color 
    print '\n'.join([''.join([str(i) for i in row]) for row in image])
    return len(connex)

if __name__ == '__main__':
    import doctest
    DATA = \
"""
00000000000000000000
00111000000000000000
00011100000011101000
01111100000111011100
01100000000011111100
11000000000111111110
00001111000111111100
00111111100011111100
00000111000000110000
00000000000000000000
"""
    LINES = [ligne for ligne in DATA.splitlines() if ligne != '']
    IMAGE = [[int(pixel) for pixel in ligne] for ligne in LINES]
    fail, _ = doctest.testmod()
    if fail == 0:
        print "WIN!"
    else:
        print "FAIL!"
Zeste de Savoir, le site qui en a dans le citron !
22 juillet 2010 à 3:23:58

Salut !

C'est très classique, il suffit de faire un parcours

*) soit en largeur (la solution de Dentuk)
*) soit en profondeur (algo itératif ou encore récursif comme ta solution).
22 juillet 2010 à 3:38:45

Citation : candide

Salut !

C'est très classique, il suffit de faire un parcours

*) soit en largeur (la solution de Dentuk)
*) soit en profondeur (algo itératif ou encore récursif comme ta solution).



Hmm oui, c'est évident quand on a l'habitude de travailler avec des tableaux à 2 dimensions, mais la première fois qu'on est confronté à ce genre de problème, on se casse pas mal la tête et on se complique souvent la vie (je me rappelle de belles migraines pendant mes cours de géométrie discrète).
Zeste de Savoir, le site qui en a dans le citron !
Anonyme
22 juillet 2010 à 10:31:30

Bonjour,

J'ai plein de questions :)

En gros l'objectif de mes questions est de savoir si oui ou non je suis capable de faire cet exercice. Car je trouve ton descriptif Nohar, pas suffisamment détaillé pour quelqu'un comme moi qui ne connaît pas le sujet.

Les questions :

1) Peux-tu me donner un intérêt de ce genre de recherches, car ce que tu dis me semble abstrait, voir très abstrait. Genre une problématique, histoire que je sois motivé ;)

Citation

trouver combien d'objets différents se trouvent sur une image binaire.



objet : De quoi veux-tu parler exactement?

image binaire : Comment on récupère une image binaire, comment la créer, sous quelle forme est-elle ressortie?

2) Tu expliques ce qu'est une connexité, c'est super, j'ai compris, les "1" se touchent, mais qu'est-ce qui se passe dans ces différents cas? Quel est le résultat attendu?

11 --> ?

111 --> ?

1
111 --> ?
1

1
1 --> ?

1
1 --> ?
1

3) Est-ce que ça demande des formules mathématiques, si oui lesquelles? Et surtout à quel niveau sont-elles étudiées?

4) Une fois qu'on aura ces 3 composantes, peut-on utiliser ce résultat? Si oui, peux-tu donner un exemple?

Enfin tu vois pour ce genre d'exercice je suis complètement dans le flou, donc si tu pouvais m'aiguiller, histoire de ... :p

Merci par avance,

22 juillet 2010 à 11:17:56

Citation : fred1599


1) Peux-tu me donner un intérêt de ce genre de recherches, car ce que tu dis me semble abstrait, voir très abstrait. Genre une problématique, histoire que je sois motivé ;)



Bah c'est un exercice donc avant tout c'est pour s'entrainer à faire quelque chose. Avec celui ci tu découvriras comment faire un parcours en profondeur par exemple (utile pour tout ce qui est labyrinthe).

Citation : fred1599


Citation

trouver combien d'objets différents se trouvent sur une image binaire.



objet : De quoi veux-tu parler exactement?


Si tu as l'image binaire suivante :
01100000000
01100000010
00010001110
00111000000

Tu peux mieux la visualiser en remplaçant les 0 par un caractère vide et les 1 par un caractère bien visible.
Ca devient donc :
.##........
.##......#.
...#...###.
..###......

Le tu vois bien les 3 objets : un carré, un L couché et un T à l'envers (c'est des tétriminos :p ).
Il faut compter ces images.

Citation : fred1599


2) Tu expliques ce qu'est une connexité, c'est super, j'ai compris, les "1" se touchent, mais qu'est-ce qui se passe dans ces différents cas? Quel est le résultat attendu?


Sur l'image ci-dessus, tu vois que le O et le T ne touchent pas le L. Donc L est forcément un objet différent.
Ensuite le O et le T sont relié par une pointe. Or Nohar nous dit qu'on considère que des pixels appartiennent à la même image seulement si ils sont 4connexes (donc voisin sur les lignes et colonnes mais pas sur les diagonales).
Donc le O et le I sont deux objets différents.

Citation : fred1599


image binaire : Comment on récupère une image binaire, comment la créer, sous quelle forme est-elle ressortie?


Tu n'as qu'à en faire une toi même. Je ne vois ce qu'il y a de compliqué la dedans. C'est comme si tu avais une image en Noir et Blanc et que tu met des 1 à la place du noir et des 0 sur le blanc.

<citation rid="5213697">
3) Est-ce que ça demande des formules mathématiques, si oui lesquelles? Et surtout à quel niveau sont-elles étudiées?
<citation>
Non pas spécialement. On peut t'aiguiller sur le parcours en profondeur mais mieux découvrir ça soit même.

22 juillet 2010 à 11:49:44

Citation : NoHaR

def flood_fill(image, objects, row, col, color):
    # ...
    directions = (row+1, col), (row-1, col), (row, col+1), (row, col-1)
    for y, x in directions:
        try:
            if image[y][x] == 1:
                objects[y][x] = color
                flood_fill(image, objects, y, x, color)
        except IndexError:
            pass


[...]

Edit: @Dentuk, j't'ai piqué ta méthode pour parcourir les différentes directions, elle allège beaucoup le code. :)


Attention, en Python c'est valide de demander un indice négatif dans une liste (je pense que tu le sais mais que tu n'y as pas pensé). Du coup avec cette méthode, le pixel (0, y) est considéré "demi-voisin" du (width-1, y). Demi-voisin parce que si (0, y) est colorié ça entrainera le coloriage de l'autre, mais si c'est l'autre qui est colorié l'exception IndexError sera bien lancée et (0, y) ne sera pas colorié. Dans mon code c'est ok parce qu'il ne peut pas y avoir de coordonnées négatives dans la liste qui recense les pixels à 1 telle qu'elle est créée.
22 juillet 2010 à 13:52:02

Citation : Dentuk


Attention, en Python c'est valide de demander un indice négatif dans une liste (je pense que tu le sais mais que tu n'y as pas pensé). Du coup avec cette méthode, le pixel (0, y) est considéré "demi-voisin" du (width-1, y). Demi-voisin parce que si (0, y) est colorié ça entrainera le coloriage de l'autre, mais si c'est l'autre qui est colorié l'exception IndexError sera bien lancée et (0, y) ne sera pas colorié. Dans mon code c'est ok parce qu'il ne peut pas y avoir de coordonnées négatives dans la liste qui recense les pixels à 1 telle qu'elle est créée.



Ah m****e, j'y avais pas pensé (j'devrais éviter de coder quand j'ai sommeil). Je corrige ça tout de suite.

Sinon fred, si tu veux un discours plus concret : on pourrait obtenir ce genre d'image, par exemple, en sortie d'une fonction d'extraction du fond (qui différencie en gros ce qui bouge de ce qui ne bouge pas à chaque frame dans une vidéo), ou de segmentation colorimétrique (qui prend une image normale en entrée et retourne en sortie uniquement les objets dont la couleur est proche de celle que l'on cherche, par seuillage). C'est un moyen très simple (mais limité) de compter, voire suivre, les cibles mouvantes sur une vidéo.

Ça ne demande aucune formule ni réflexion mathématique, juste de trouver (si tu ne connais pas encore) une méthode a appliquer.

Zeste de Savoir, le site qui en a dans le citron !
22 juillet 2010 à 14:17:32

Bonjour,

Bon vais pas faire cet exercice qui est, comme on dit, un cas d'école, mais j'ai fait une classe qui génère une image binaire pour faire les tests.

from random import choice
class ImageBinaire(object):
    
    def __init__(self, dimension = (10,10)):
        self.image = []
        self.x = range(dimension[0])
        self.y = range(dimension[1])                       
        self.genere()



    def genere(self):
        """
        Génère une image binaire représentée par une liste contenant d'autres
        listes, selon les dimensions données,
        cette image est remplie aléatoirement.
        """

        nbBinaire = ('0','1')

        for i in self.x:
            self.image.append(list())
            for j in self.y:                
                self.image[i].append(choice(nbBinaire))


    def affiche(self):        
        for i in self.x:
            ligne = ''
            for j in self.y:
                ligne += self.image[i][j]
            print(ligne)


Et en prime une petit exemple d'utilisation :
>>>img = ImageBinaire((10,10))
>>>img.affiche()
1001110101
1011100101
0110111100
1100100100
1001010101
1100011000
1111011010
0000000011
1000101010
1010001000

La liste de listes représentant l'image est accessible avec l'attribut image, ici par exemple c'est img.image
26 juillet 2010 à 15:44:55

Vous pensiez que cet exercice n'est qu'un cas d'école ?
renseignez vous sur les algorithmes de traitement de l'image (sans bibliothèques :) style pour de l'embarquée) et vous verrez qu'il y a des l'applications :
connexité des pixels (sur une image bina-risée par exemple) afin d'en ressortir les différentes formes (donc leur coordonnées)

enjoy :D
19 juillet 2011 à 17:51:03

Bonjour,

Pour faire un peu original, j'ai utilisé un dictionnaire de dictionnaires (et non une liste de listes) pour représenter le tableau.

Sinon, l'algo n'a rien d'original, un bête flood-fill récursif comme tout le monde. Pas très difficile à réécrire en itératif, peut-être vais-je le faire.

Mon code :
def erase_object(tab2d,i,j):
    tab2d[i][j]='0'
    if i-1 in tab2d and tab2d[i-1][j]=='1':
        erase_object(tab2d,i-1,j)
    if i+1 in tab2d and tab2d[i+1][j]=='1':
        erase_object(tab2d,i+1,j)
    if j-1 in tab2d[i] and tab2d[i][j-1]=='1':
        erase_object(tab2d,i,j-1)
    if j+1 in tab2d[i] and tab2d[i][j+1]=='1':
        erase_object(tab2d,i,j+1)

def nb_objects(img):
    tab2d = { key_i:{key_j:val for key_j,val in enumerate(line)} for key_i,line in enumerate(img) }
    counter = 0
    for i in range(len(tab2d)):
        for j in range(len(tab2d[i])):
            if tab2d[i][j]=='1':
                erase_object(tab2d,i,j)
                counter += 1
    return counter

image = (   '00000000000000000000',
            '00111000000000000000',
            '00011100000011101000',
            '01111100000111011100',
            '01100000000011111100',
            '11000000000111111110',
            '00001111000111111100',
            '00111111100011111100',
            '00000111000000110000',
            '00000000000000000000'  )

print(nb_objects(image))


EDIT :
def erase_object_it(tab2d,i,j):
    l = [(i,j)]
    while l != []:
        i,j = l[0]
        tab2d[i][j]='0'
        if i-1 in tab2d and tab2d[i-1][j]=='1':
            l.append((i-1,j))
        if i+1 in tab2d and tab2d[i+1][j]=='1':
            l.append((i+1,j))
        if j-1 in tab2d[i] and tab2d[i][j-1]=='1':
            l.append((i,j-1))
        if j+1 in tab2d[i] and tab2d[i][j+1]=='1':
            l.append((i,j+1))
        l.pop(0)


EDIT 2:
Meilleure version itérative (utilise un deque à la place d'une liste conformément aux recommandations)
from collections import deque

def erase_object_it(tab2d,i,j):
    fifo = deque([(i,j)])
    while len(fifo) != 0:
        i,j = fifo.popleft()
        if i-1 in tab2d and tab2d[i-1][j]=='1':
            fifo.append((i-1,j))
        if i+1 in tab2d and tab2d[i+1][j]=='1':
            fifo.append((i+1,j))
        if j-1 in tab2d[i] and tab2d[i][j-1]=='1':
            fifo.append((i,j-1))
        if j+1 in tab2d[i] and tab2d[i][j+1]=='1':
            fifo.append((i,j+1))
        tab2d[i][j]='0'
23 juillet 2011 à 15:00:23

Bonjour, cet exercice est trop compliqué pour moi mais c'est fort intéressant.
Je vais essayer de comprendre.

PS: On ne sait jamais je fais une demande si jamais vous aviez un exercice un peu sur le même principe mais plus abordable ou de la documentation (tutoriel etc..) je suis preneur, j'ai pas réussi à trouver grand chose sur internet.

Merci à vous.
:)
19 mars 2015 à 11:46:33

salut , 

Aujourd'hui je vous propose un exercice de niveau intermédiaire ayant trait au traitement d'images. N'ayez pas peur

je reviens sur le sujet: compter les objets sur une image et donner le résultat

se sujet quelqu'un peut t'il le réaliser en C ou C++?

proposées des solutions et on en discute !!!!!!!!!!!!!!!!

20 mars 2015 à 9:35:53

@maxifongyang : propose d'abord ta solution. Là on dirait que tu cherches à ce que quelqu'un code un truc à ta place.

Zeste de Savoir, le site qui en a dans le citron !
22 novembre 2015 à 10:23:11

bonjour!il auraut-il quelqu'un pour traduire le code en java ??je ne connais pas le language python alors je veux connaitre le principe du comptage
15 septembre 2018 à 16:39:38

Bonjour,

Merci beaucoup pour cet exercice et solutions très utiles !

Par ailleurs, j'applique ce principe de comptage d'objets sur une image binaire de grande résolution, avec des objets de grande taille, et ne peut donc utiliser que la solution itérative, ce qui est assez long...connaîtriez-vous une bibliothèque qui optimise ce calcul ?

Merci d'avance !

[Exercice][Moyen] Connexité et comptage d'objets

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
  • Editeur
  • Markdown