Images binaires et composantes connexes

00000000000000000000
00111000000000000000
00011100000011101000
01111100000111011100
01100000000011111100
11000000000111111110
00001111000111111100
00111111100011111100
00000111000000110000
00000000000000000000

Connexes ? Ça veut dire quoi ?!

• 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

00000
01100
00011
00011

Votre mission, si vous l'acceptez...

Indices

#!/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))

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

3

#! /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!"

#! /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!"

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).

Citation

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

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é

Citation : fred1599

Citation

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

objet : De quoi veux-tu parler exactement?

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?

Citation : fred1599

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

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.

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.

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)

>>>img = ImageBinaire((10,10))
>>>img.affiche()
1001110101
1011100101
0110111100
1100100100
1001010101
1100011000
1111011010
0000000011
1000101010
1010001000

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))

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)

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'

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 !!!!!!!!!!!!!!!!

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

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 !