trovare le macchie di colore più grandi in un file PNG
« il: Settembre 05, 2019, 15:57 »
buon pomeriggio,
ho un problema con il seguente esercizio: dato un file png e dato un colore in input devo scrivere un codice che trovi la macchia di colore più grande e salvi una nuova immagine in formato png con solo la macchia trovata e come sfondo il colore complementare a quello dato. il mio codice consiste nell'avere una funzione che ritorni una lista di coordinate (row,col) di tutti i pixel del colore dato. modifico poi la matrice di RGB, che diventa una matrice di tuple (RGB, boolean=False in modo da ricordare se quel determinato pixel è stato già analizzato. a questo punto per gli elementi della lista delle coordinate di cui ho parlato prima, parte una ricerca ricorsiva in tutte e 4 le direzioni, e qualora trovi dei pixel del colore dato adiacente, il booleano viene convertito in True e la coordinata del pixel viene aggiunta ad una nuova lista che racchiude solo pixel della macchia. la ricorsione termina quando non ci sono più pixel adiacenti da analizzare,e si tornerà alla funzione che chiama la prima ricorsione per vedere se ci sono altri pixel di un'altra macchia non analizzati per far partire un'altra ricorsione. alla fine verranno create diverse liste "macchia" aggiunte in un dizionario con chiave la lunghezza della lista e valore la lista stessa in modo da prendere solo la lista più lunga. creare poi la nuova immagine è estremamente semplice.
il mio codice funziona perfettamente per file png fino ad una certa grandezza, ma quando le macchie immagini iniziano ad essere molto grandi, le limitazioni di python sulla ricorsione interrompno le ricerce dando l'errore "maximum recursion depth exceeded in comparison" non so come risolvere questo problema, un'idea sarebbe trovare un modo iterativo di fare questa ricerca ma non sono riuscito a. pensarlo.
qui c'è il codice ho cercato di essere più chiaro possibile nei commenti spero che qualcuno possa aiutarmi
grazie mille in anticipo
def es1(fname, colore, fnameout):
    # inserite qui il vostro codice
    matrice= immagini.load(fname)
    lista=coordinate(matrice,colore)
    true_false(matrice)
    diz=dizionario(matrice,lista,colore)
    macchia=max(diz)[1]
    #prendo la lista con lunghezza maggiore nel dizionaro/lista
    out=newIm(matrice,macchia,colore)
    immagini.save(out,fnameout)
    return len(macchia)


def coordinate(matrice,colore):
    #crea e ritorna una lista con tutte le coordinate (row,col) dei pixel del colore RGB richiesto
    lista=[]
    for y in list(range(len(matrice))):
        for x in list(range(len(matrice[0]))):
            if matrice[y][x]==colore:
                lista.append((y,x))
    return lista

def true_false(matrice):
    #modifica la matrice ed ogni tupla di RGB diventa una lista di 2 elementi con
    # l'RGB invariato e il valore booleano False
    for row in list(range(len(matrice))):
         for col in list(range(len(matrice[0]))):
             matrice[row][col]=[matrice[row][col], False]     
             
def dizionario(matrice,lista, colore):
    #la funzione inizialmente doveva creare un dizionario con chiave la lunghezza di ogni macchia del colore richiesto
    #e valore la lista delle coordinate di quella macchia. alcune macchie hanno uguale grandezza e in un dizionario non possono esserci
    #due chiavi uguali e le listre non possono essere chiavi quindi il dizionario è in realtà una lista
    dizionario_macchie=[]
    for coord in lista:
        #analizzo ogni elemento della lista di coordinate e se il suo valore booleano nella matrice è False da lì inizia una macchia di colore
        #e inizio la ricerca ai pixel adiacenti e alla fine delle ricorsioni aggiungo la macchia e la lunghezza al dizionario/lista,
        #se il booleano è True, già ho visto quella macchia in una ricorsione precedente e vado avanti
        if matrice[coord[0]][coord[1]][0]==colore and matrice[coord[0]][coord[1]][1]== False:
            macchia=[]
            ric(matrice,coord[0],coord[1],colore,macchia)
            dizionario_macchie.append((len(macchia), macchia))
    return dizionario_macchie


def ric(matrice, row, col, colore, macchia):
    #prendo in input la matrice, le coordinate del pixel dal quale parte la ricorsione, il colore e la macchia che si viene a formare
    # se nella matrice il punto alle coordinate row,col è il colore dato in input e il booleano è False, aggiungo quelle coordinate
    #alla lista macchia e cambio il valore da False a True per evitare di ripassare in futuro per quel punto.
    #mi assicuro poi che i pixel adiacenti non vadano oltre i bordi e richiamo la funzione ric per tutti e 4 i pixel adiacenti.
    #una volta finita la ricorsione si torna alla funzione dizionario, la macchia è completa e la aggiungo nel dizionario/lista
    if matrice[row][col][0]==colore and matrice[row][col][1] == False:
        matrice[row][col][1]=True
        macchia.append((row,col))
        if row-1>0:
            ric(matrice, row-1, col, colore, macchia)
        if row+1<len(matrice):
            ric(matrice, row+1, col, colore, macchia)
        if col+1<len(matrice[0]):
            ric(matrice, row, col+1, colore, macchia)
        if col-1>0:
            ric(matrice, row, col-1, colore, macchia)
   


def newIm(matrice,macchia,colore):
    #creo una nuova matrice che diventerà l'immagine in output
    prova=[]
    for row in list(range(len(matrice))):
        lista=[]
        prova.append(lista)
    for col in list(range(len(matrice[0]))):
        for elem in prova:
            elem.append((255-colore[0],255-colore[1],255-colore[2]))
    for elem in macchia:
        prova[elem[0]][elem[1]]=colore
    return prova