<jupyter_start><jupyter_text>TME 9: Merge> Consignes: le fichier TME8_Sujet.ipynb est à déposer sur le site Moodle de l'UE https://moodle-sciences.upmc.fr/moodle-2019/course/view.php?id=4248. Si vous êtes en binôme, renommez-le en TME8_nom1_nom2.ipynb.N'oubliez pas de sauvegarder fréquemment votre notebook !! Données et codes utiles au TME<jupyter_code>from PIL import Image
from pylab import *

### Données
img_test = full((64,64),150,dtype=uint8)
img_test[32:48,16:16+32] = 100
img_test[8:24,40:56] = 50
angio = array(Image.open('images/angiogra.png'))
cam = array(Image.open('images/cameraman.png'))
muscle = array(Image.open('images/muscle.png'))
prisme = array(Image.open('images/prisme.png'))
seiche = array(Image.open('images/seiche.png'))

### Fonction d'affichage
def affichage_14(affichages,titres=None):
    """ list[Array]*list[str] -> NoneType
    Dffectue entre 1 et 4 affichages avec leurs titres, pour des images ou courbes
    
    Paramètres :
      - liste des affichages (entre 1 et 4)
      - liste des titres (entre 1 et 4, autant que de affichages), optionnelle    
    """
    
    if not type(affichages) == type([]):
        affichages = [affichages]
        
    if titres is None:
        titres = ['',]*len(affichages)
        
    if not type(titres) == type([]):
        titres = [titres]
    
    nb_affichages = len(affichages)
    if nb_affichages >4 or nb_affichages < 1 :
        raise ValueError('affichage_14 nécéssite 1 à 4 entrées en paramètre')        
        
    if nb_affichages != len(titres):
        raise ValueError('affichage_14 nécéssite autant de titres que d\'affichages')
        
    courbes = False
    for i in range(0,nb_affichages):
        s = subplot(101+10*nb_affichages+i)
        s.set_title(titres[i])
        if len(affichages[i].shape)>=2 and affichages[i].shape[0] > 1 and affichages[i].shape[1] > 1:
            # on affiche une image
            s.imshow(affichages[i], cmap="gray",interpolation='nearest', aspect='equal')
        else :
            # il s'agit d'une seule ligne, à afficher comme une courbe
            plot(affichages[i])
            courbes=True

    agrandissement_h = nb_affichages
    agrandissement_v = nb_affichages*2 if courbes else nb_affichages
    params = gcf()
    plSize = params.get_size_inches()
    params.set_size_inches( (plSize[0]*agrandissement_v, plSize[1]*agrandissement_h) )
    show()<jupyter_output><empty_output><jupyter_text>Recopier ci-dessous le code des fonctions ``split()``, ``predsplit1()`` et ``splitprof()``écrites au TME 8:<jupyter_code>def split(I,reg,pred,*args):
    """ Array*Bloc*(Array*Bloc*...->bool)*... -> 4-aire
        Découpage de I en arbre 4-aire sur un critère d'écart-type minimal
    """
    x, y, width, height = reg
    
    if(pred(I, reg, *args) and width > 2 and height > 2):

        
        width_child, height_child = width//2, height//2
                

        # Nord ouest
        NO = split(I, (x, y, width_child, height_child), pred, *args)
        # Nord est
        NE = split(I, (x + width_child, y, width_child, height_child), pred, *args)
        # Sud Ouest
        SO = split(I, (x, y+height_child, width_child, height_child), pred, *args)
        # Sud Est
        SE = split(I, (x + width_child, y + height_child, width_child, height_child), pred, *args)
        
        
        return [NO, NE, SO, SE]

    return [reg]
    
def predsplit1(I,reg,*args):
    """ Array*Bloc*... -> bool
    """ 
    x, y, width, height = reg
    
#     print("x = ", x, "y = ", y)
    # variation supereir a un threshhold

    return I[y:y+height, x:x+width].std() > args[0]

def splitprof(L):
    """ 4-aire -> list[Bloc]"""
    
    if(len(L) == 1):
        return L

    childs = []
    for i in range(4):
        #print("L is = ", L[i])
        childs += splitprof(L[i])
        
    return childs

def splitdraw(LL,I):
    """ list[Bloc]*Array -> Array
        parcours de la liste dessin des régions 
    """
    I_copy = np.zeros_like(I)
    
#     cols = 5
#     rows = len(LL)//cols
    
#     fig1, f1_axes = plt.subplots(ncols=cols, nrows=rows, constrained_layout=True, figsize=(30,20))
    
    for i, reg in enumerate(LL):
        
        x, y, width, height = reg
        
        I_copy[y:y+height, x:x+width, 0] = I[y:y+height, x:x+width, 0].mean()
        I_copy[y:y+height, x:x+width, 1] = I[y:y+height, x:x+width, 1].mean()
        I_copy[y:y+height, x:x+width, 2] = I[y:y+height, x:x+width, 2].mean()
        
        if(y != 0):
        #horizontal
            I_copy[y, x:x+width, 0] = 255
            I_copy[y, x:x+width, 1] = 0
            I_copy[y, x:x+width, 2] = 0
        
        if(x != 0):
        #verticla
            I_copy[y:y+height, x, 0] = 255
            I_copy[y:y+height, x, 1] = 0
            I_copy[y:y+height, x, 2] = 0
        
        #affichage_14([RGB/255],['titre'])
#         row = i // cols 
#         col = i % cols
        
#     f1_axes[row, col].imshow(I_copy/255)
#     f1_axes[row, col].axis("off")
    plt.imshow(I_copy/255)
    plt.axis("off")
    plt.show()

def split_img_show(imgs):
    """
        dict[str*numpy]
    """
    
    for title, img in imgs.items():
        

        plt.figure(figsize=(20,10))

        #noise = random.randn(img.shape[0], img.shape[1]) * 1

        #img_noise = img + noise
        
        plt.subplot(121)
        plt.imshow(img, cmap="gray")
        plt.title(title)
        plt.axis("off")


        RGB = zeros((img.shape[0], img.shape[1],3))
        RGB[:,:,0] = img
        RGB[:,:,1] = img
        RGB[:,:,2] = img

        plt.subplot(122)
        plt.title(title + "_quadtree_split")
        split_test = split(img, (0, 0, img.shape[1], img.shape[0]), predsplit1, 20)
        split_prof_test = splitprof(split_test)
        splitdraw(split_prof_test, RGB)<jupyter_output><empty_output><jupyter_text>Exercice 1 Question 1Modifier la fonction ``splitprof(L)`` pour en faire une fonction ``splitprofstat(L,I)`` qui rend une liste de feuilles de l'arbre 4-aire ``L`` et telle que chaque élément de cette liste, de type ``Bloc``, est enrichi de trois scalaires, le premier étant la taille, le second la moyenne et la troisième la variance des valeurs de pixels du bloc dans l'image ``I``. Cette fonction rend alors une liste dont les éléments ont pour type formel:```pythontype Blocstat = tuple[int**4,int,float**2]```Les quatre premières valeurs sont celles du type ``Bloc``, la cinquième est la taille du bloc (en nombre de pixels) et les deux dernières correspondent à la moyenne et la variance calculées sur la région.<jupyter_code># type Blocstat = tuple[int**4,int,float**2]

def splitprofstats(L,I):
    """ 4-aire*Array -> list[Blocstat] """
    
    if(len(L) == 1):
        
        x, y, width, height = L[0]
        
        taille = width*height
        moy = I[y:y+height, x:x+width].mean()
        std = I[y:y+height, x:x+width].std()**2

        return [(x, y, width, height, taille, moy, std)]

    childs = []
    for i in range(4):
        #print("L is = ", L[i])
        childs += splitprofstats(L[i], I)
        
    return childs<jupyter_output><empty_output><jupyter_text>Question 2Dans la suite du TME, on considère le type formel:```pythontype Region = list[Blocstat]```Une région, comme vu au TME, est donc une liste de blocs. Écrire le prédicat de fusion ``predmerge(b,R,*args)`` vu en TD. Cette fonction retourne ```True``` si le bloc ``b`` doit fusionner dans la région ``R``. Si telle est le cas, alors le premier élément de la liste ``R`` voit ses statistiques modifiées: elles décrivent celles de l'ensemble des blocs de la région ainsi fusionnée.<jupyter_code>def predmerge(b,R,*args):
    """ Blocstat*Region*... -> bool 
        Si fusion, R[0] est modifié
    """
    
    if(b in R):
        return False
    
    # si la variance decroit
    x, y, width, height, taille, moy, std = b
    x_reg, y_reg, width_reg, height_reg, taille_reg, moy_reg, std_reg = R[0]
    
    #if(taille > taille_reg):
    #    return False
    
    # nouvel donné de la fusion
    n = taille + taille_reg
    mu = (taille*moy + taille_reg*moy_reg)/n
    std3 = 1/n * (taille*(std+moy**2) + taille_reg*(std_reg+moy_reg**2)) - mu**2
    #print("std3 : ", (std3 - (taille*std + taille_reg*std_reg)/n))
    # evite de specefier un seuil
    critere =  (std3 - (taille*std + taille_reg*std_reg)/n) <= 0
    
    if std3 < args[0]:
        # fusioner avec la region
        R[0] = x_reg, y_reg, width_reg, height_reg, n, mu, std3
        # ajouter dans la liste des voisins
        #R.append(b)
        
        return True
    
    
    return False<jupyter_output><empty_output><jupyter_text>Question 3Implémenter les fonctions ```estdans()```, ```sontvoisins()```, ```voisins()``` et finalement ```merge()``` vues en TD.<jupyter_code>def estdans(x,y,a):
    """ int*int*Blocstat -> bool 
        Teste si (x,y) est dans a 
    """
    x_a, y_a, width, height, n, m, v = a
    
    return (x >= x_a) and (x < (x_a + width)) and (y >= y_a) and (y < (y_a + height)) 


def sontvoisins(a,b):
    """ Blocstat**2 -> bool
        Teste si a et b sont voisins
    """
    
    # la region b doit étre la plus large, si ce n'est pas le cas , permute
    if (a[2]>b[2]) and (a[3]>b[3]):
        a, b = b, a
    
    # le centre de la region a
    x, y = a[0]+a[2]//2, a[1]+a[3]//2
             
    # verifier les 4 direction
    return (estdans(x+a[2], y, b) or
            estdans(x-a[2], y, b) or
            estdans(x, y+a[3], b) or
            estdans(x, y-a[3], b))

def voisins(b,K):
    """ Blocstat*list[Blocstat]->list[Blocstat]
        retourne la liste des elements de K voisins de b
    """
    return [n for n in K if(sontvoisins(b, n))]
    
    
# type Region = list[Blocstat]

def merge(S,I,pred,*args):
    """ 4-aire*Array*(Blocstat*Region*...->bool) -> list[Region]
        Fusionne les feuilles de S en une liste de régions
    """
    S = splitprofstats(S, I)
    S.sort(key=lambda x:x[4], reverse=True)
    #print(S)
    #K = [(x, y, n, m, n*m, I[x:x+n, y:y+m].mean(), I[x:x+n, y:y+m].std()) for (x, y, n, m) in S]
    K = S
    # liste des regions
    L = []
    
    # tanq qu'il reste un block dans K
    while(len(K) > 0):
        b = K[0]
        K =  K[1:]
        
        # nouvel region
        R = [b]
        
        # voisin de b
        
        N = voisins(b, K)
        N.sort(key=lambda x:x[4], reverse=True)
        # tant qu'on a pas visité tout les voisins
        while(len(N) > 0):
            
            bi = N[0]
            N = N[1:]
            
           
            if pred(bi, R, *args):
                # supprimer l'element 
                #print("merged !")
                K.remove(bi)
                
                R.append(bi)
                
                # ajouter les voisin de la regioné fusioné
                N = N + [j for j in voisins(bi, K)]
                #print("not merged !")
        # Ajouter cette nouvel region
        L.append(R)
        
    return L<jupyter_output><empty_output><jupyter_text>Question 4Faire la mise au point des fonctions précédentes à l'aide de l'image ``img_test``.<jupyter_code>s = split(img_test, (0,0,img_test.shape[1],img_test.shape[0]), predsplit1, 10)
m = merge(s, img_test, predmerge, 20)<jupyter_output><empty_output><jupyter_text>Question 5Écrire une fonction ``regions(LR,shape)`` qui prend une liste de régions telle que rendu par la fonction ``merge()`` et rend une image des régions. Chaque région sera colorée avec le niveau de gris correspondant à la moyenne de la région. Le paramètre ``shape`` donne la taille de l'image à produire. Tester la fonction sur l'exemple précédent.<jupyter_code>def regions(LR,shape):
    """ list[Region] -> Array """
    buf = zeros(shape,dtype=uint8)
    for R in LR:
        x,y,n,m,s,mu,v=R[0]
        for b in R:
            x,y,n,m,s,t,v=b
            buf[y:y+m,x:x+n] = int(mu)
    return buf
buff = regions(m, (64,64))
plt.imshow(buff, cmap="gray")<jupyter_output><empty_output><jupyter_text>Exercice 2: expérimentation Question 1:Tester la fonction ``merge()`` sur les images ``angio``, ``cam``, ``muscle``, ``prisme`` et ``seiche``.<jupyter_code>imgs = {"angio":angio, "cam":cam, "muscle":muscle, "prisme": prisme, "seiche": seiche}

#split_img_show(imgs)

for titre, img in imgs.items():
    
    s = split(img, (0,0,img.shape[1],img.shape[0]), predsplit1, 15)
    print("avant merge :", len(splitprof(s))," regions")
    m = merge(s, img, predmerge, 200)
    print("apre merge : ", len(m), " regions")
    plt.figure(figsize=(20,10))
    plt.subplot(121)
    plt.imshow(img, cmap="gray")
    plt.subplot(122)
    plt.imshow(regions(m, img.shape), cmap="gray")
    plt.show()<jupyter_output>avant merge : 2272  regions
apre merge :  674  regions
{'fraction_non_alphanumeric': 0.1457321848081441, 'fraction_numerical': 0.02004698512137823, 'mean_word_length': 2.5683151718357085, 'pattern_counts': {'":': 5, '<': 37, '<?xml version=': 0, '>': 61, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '425857', 'license': 'MIT', 'n_tokens_mistral': 4940, 'n_tokens_neox': 4774, 'n_words': 1208, 'path': 'TME9/.ipynb_checkpoints/TME9_Benimam-checkpoint.ipynb', 'repo_name': 'mbeni12333/Computer-Vision-Projects', 'size': '12770'}