Bonjour,
 
Comme dit dans le titre, je cherche un algo pour decomposer une image en le plus petit nombre de rectangles (de couleur unie) possibles.
Ou disons un nombre suffisament petit.
En gros je cherche à decrire une image en utilisant des rectanlges de couleur unie, et de la maniere la plus compacte possible.
 
Evidemment le but n'est pas de decrire une image complexe genre jpeg de paysage, mais plutot des trucs genre graph ou autres images générées.
 
Si vous avez une idée ou une piste, ca m'interesse
merci
 
EDIT: petite precision: les rectangles ne peuvent pas se chevaucher. Par exemple une image representant une simple ligne verticale au milieu de l'image sera decrite par 3 rectangle: le fond à gauche de la ligne, la ligne, et le fond à droite.

Tu peux faire un système qui ajoute à chaque rectangle de couleur unie existant une ligne ou une colonne de pixels adjascents au rectangle s'ils sont de la même couleur, en démarrant avec des rectangles de la taille d'un pixel de l'image.
Par contre, pour trouver la solution optimale, à mon avis ça ressemble à un problème NP-complet.

ouai effectivement ca doit etre NP complet, un peu comme les trucs genre binpack.
 
Je pensais effectivement faire comme ca, en prenant des points de depart au pif, et en essayant de maximiser un rectangle à partir de ca.
Il me faudrait une solution "satisfaisante", pas forcement optimale.
Le but est de faire ca sur des images genre graph ou chart, donc avec normalement de beaux gros rectangle à aller chercher.

Tu peut déja classer les couleurs de l'image par nombre d'occurences dans l'image, ca te donnera une idée d'endroits ou commencer (la ou y'a les couleurs les plus présentes dans l'image)

yep, bonne idée! merci

'alut
et une decomposition en quad-Tree c'est pas fait pour ca?
 
@pluche

ca consite à decouper l'image en 4, puis à continuer pour chaque region en s'arrettant des que la region est de couleur unie c'est ca?
 
Ouai c'est pas mal comme approche. Apres il faudrait faire une seconde passe pour eventuellement regrouper des carrée juxtant et de meme couleur dans deux zones differentes. Mais ca doit deja donner de bons resultat tels quels.
Je vais essayer ca.
merci

alut,
 
ouais cest tout a fait ca. Quand à la seconde passe je ne sais pas trop si elle est necessaire, dans la mesure où le critère de 'split' n'est pas respecté dans les cas de regions identiques.
 
@pluche

oui mais imagine le cas suivant:

l'ideal serait de ne pas systematiquement split au milieu mais aux endroits de fort contraste (et pas trop eloignés du milieu tout de meme). Ca donnerait ca:
 

 
mais bon, la c'est un cas simple
et puis ca demande à faire une passe avant chaque split, peut etre bcp plus couteuse qu'une passe finale

d'un autre coté (j'y reviens par moments, au cours de la journée...) le fait d'ajuster les frontieres de split au mieux devrait permettre de reduire le nombre de recursions de split necessaires dans la plupart des cas

ca ca me fait penser à un algo utiliser pour la compression en couleur, ou tu splits les populations defacon a avoir le meme nombre d'elements des deux cotés de la frontiere....
mais la, en fait ca serai plutot un truc du genre split & merge qui faudrai utiliser.