mais qui est tu seam carving ? - un algo de ouf, déja porté par des oufs
impressionnat hein?! vas y fait pas le blasé.
ou la blasée d'ailleurs.
Seam en anglais signifie: couture, filon, sillon.
'a seamless plan' c'est 'j'adore qu'un plan se déroule sans accrocs' /*mâchonne son cigare*/
et aux entournures ou sur les bords se dit "at the seams" comme dans l'expression "he's a bit of a moron at the seams" (il est un peu con sur les bords).
to carve, c'est creuser, extraire, couper, excaver ... beaucoup moins drôle.

on s'en fout.
bon du coup celui là m'a travillé pendant longtemps et puis, suite au déluge de réactions causé par la squelettisation (sauf toi mon jeanjean qui es un poète) et eût égard au fait que je ne suis pas satisfait du résultat, je suis allé voir chez développez.com où il y a un peu des brutes du traitement d'images avec un coeur gros comme ça qui bat dedans.

et du coup j'ai été redirigé vers la section contribuez : que du bon.

du coup cash t'as le seam carving, les snakes, la triangulation le tout gentiment porté en Java. c'est certain que ton cerveau de mollusque ne saurait pas quoi en faire mais pour les honnêtes gens, c'est de la boulette en forme de manne céleste aux mille reflets grenats.
ou un truc du genre, puis t'es pas un mollusque puisque tu lis mon blog :)

bon j'ai pas résolu mon problème de squelette parce que je me suis fait happer par le seam carving.
le mollusque qui vit dans toi va sûrement dire : "mais les simpsons l'ont déja fait" vu que Quasimondo ET Joa Ebert se sont mis à 2 dessus. je pense qu'il n'y a rien à ajouter. c'est vrai. mais si j'avais tenu ce raisonnement depuis le début, ce blog n'existerait pas.
Entrons dans le vif du sujet:
la savane réduite à 25% de sa hauteur
source

nous donne:

slipu hein ?!

alors, non c'est pas du photoshop.
ce qu'il y a de remarquable là dedans c'est la conservation de la morphologie des éléments. en gros malgré une réduction intense, les arbres n'ont pas été affectés alors que tout le reste, si. Pour déterminer ce qui est important, on regarde les changements de valeur d'un pixel à l'autre. c'est ce qu'on appelle une détection de contours et il existe des filtres bien rodés (Sobel, Prewitt, Laplace, Tutti & Quanti ). On garde en mémoire ce 'plan' dans un tableau 2D (energyMap) et au lieu de supprimer une ligne verticale ou horizontale comme un bête resize, on sélectionne un chemin qui traverse l'image horizontalement ou verticalement et qui passe par les endroits de l'image ayant le moins d'énergie. le chemin qui a la valeur la plus faible est celui qui se 'voit' le moins quand on le soustrait crapuleusement à sa famille d'origine.
du coup on obtient des lignes tordues qui sillonnent l'image (les seams) et qui arrêtent de saloper la morphologie quand on redimensionne une image.
voila pour la théorie, place à un peu d'amusement:


ça c'est des réductions à 50% faites avec mon filtre de Sobel de compagnie. l'image en dessous du seam carving est un con de rescale.
source: prototype de Marius Watz

résultat:

moralité: de toutes façons c'était moche son truc...

source: art génératif de Marius Watz

résultat:

moralité: l'art génératif c'est nul.

source: une île où la main de l'homme n'a jamais mis le pied

résultat:

moralité: on est foutus de saloper même les endroits où on n'est pas allés... déprimant.


source: paysage dévasté où t'as trop pas envie d'aller

résultat:

moralité: presqu'aussi bon que la savane. le seam carving est un mauvais tour operator.

source: photo de classe de secondes L boutonneux

résultat:

moralité: être en seconde ça écrase la tête et ça fait rétrécir les genoux.(j'en viens, j'en sais quelque chose)

source: un falcon 90 à louer :
2 pilotes, 1 hôtesse
12 / 14 places passagers First Class

moralité: les bourges ont la belle vie quand même...

source: notre président René Coty

moralité: la tête de René Coty présentait peu de variations d'intensité avec son arrière-plan, c'est pour ça qu'il n'est plus président

moralité de ce remarquable bench:

  • les motifs bruités encerclés de dégradés souples sont de bons candidats
  • les motifs pleins encerclés de bruit sont de bons candidats
  • les paysages pittoresques sont de bons candidats ; ils alternent bruit et espaces lissés ("regarde le ciel, porc!" comme disait Beckett)
  • les images trop 'composées' ou trop 'signifiantes' sont de mauvaises candidates ; leur lecture après le traitement est très altérée(cf.Coty).
  • si c'est mettable pour de faibles redimensionnements (0 à 10%), au delà, demander à un humain de vérifier


Alors après je me suis fait la réflexion suivante " damned! et si ces résultats exécrables venaient du filtre de détection de contours" et en fait oui et non.
j'utilisais un Sobel et je me suis implémenté un Prewitt plus gourmand (4passes) et miracle: René Coty retrouve sa tête. Prewitt fait mieux la détection d'angles et élimine certains artefacts et autres bruits indésirables.
après j'ai calculé la luminance des pixels au lieu de stocker la couleur dans l'energyMap. le top ce serait une carte des distances, genre un peu le résultat de l'exemple de squelettisation ; un map en niveaux de gris qui indique l'énergie émise par une forme. je pense que le résultat serait exact et beaucoup plus beau mais que la perte en temps de calcul rendrait la chose aussi imbitable qu'une squelettisation.

Toujours pour couper la chique au temps de calcul, je ne processe plus l'energy map à chaque modification de la taille mais seulement une fois tous les # passes. c'est une variable statique judicieusement appelée Carving.refreshRate qui dit quand re-parser l'energy map ceci dit, plus on espace les rafraîchissements, plus c'est sale, mais ça économise pas mal de ressources(crois moi).
Par exemple si on a 200pixels de ciel bleu, on sait que les 200 premières passes vont taper principalement dedans, du coup on peut élever le refreshRate. parcontre si on a ensuite un avant plant très détaillé, ça va être sale, donc bien doser la fréquence du refresh est importnat.

Avec le filtre de Prewitt, j'ai aussi mis un seuil (Carving.threshold défaut -1 > pas de seuil). ça ne marche pas avec Sobel (les nuances se font défoncer la gueule et l'energyMap ressort tout noir :/).
Le seuil ça permet de réduire les bruits donc ça donne une image en 2 couleurs, et ça permet à l'algo de choisir plus facilement quel chemin emprunter. parcontre ça peut éliminer des structures importantes de l'image ou au contraire conserver des structures secondaires.
pour mieux comprendre, voila ce que donne l'energyMap de René Coty (avec le filtre de Prewitt)
sans rien :

résultat à 50%.


avec un threshold à 0xFF333333 :

résultat à 50%.


avec un threshold à 0xFF888888 :

résultat à 50%.


avec un threshold à 0xFFAAAAAA :

résultat à 50%.

en général, 0xFF888888 marche pas trop mal.
on sent bien que plus le threshold est élevé, plus il y a de 'trous' dans l'energyMap. en sortie des bandes se créent et les seams se ruent dessus pour créer des rayures disgracieuses. mais par exemple sur un désert c'est top car ça rennforce les lignes horizontales et ça dégage les lignes verticales mieux que Vicks vaporub toux sèche:
original:

energyMap (filtre de Prewitt)

energyMap seuillé à 0xFF666666:

energyMap seuillé réduit et résultat final:

Bon donc en gros, c'est un algo assez complexe donc il n'y a pas LE réglage qui tue mais bien un myriade de réglages qui marchent plus ou moins. tout dépend de l'image d'entrée, du choix du filtre, du nombre et de la direction des itérations, de la fréquence de rafraîchissement et du fait qu'on seuille ou non l'image... autant dire que c'est le bordel.

2, 3 petits exemples interactifs pour la route: (energy > energyMap, render > start/stop )
c'est TRES gourmand en ressources /!\

filterType = PREWITT; refreshRate = 10; threshold = 0xFF666666;


filterType = PREWITT; refreshRate = 10; threshold = 0xFF666666;


filterType = PREWITT; refreshRate = 10; threshold = -1;


filterType = PREWITT; refreshRate = 5; threshold = 0xFF666666;


filterType = SOBEL; refreshRate = 5; threshold


filterType = PREWITT; refreshRate = 100; threshold = 0xFF666666;

les trucs:

J'ai sournoisement écrit 1/3 dans le titre. C'est juste qu'il y a encore deux choses importantes à faire avec cet algo :

  • 2/3 - faire un agrandissement. là c'est rigolo mais en vrai on peut recréer du motif en faisant la moyenne des couleurs autour du seam et en agrandissant l'image de sortie. ça ferait qu'à partir d'une petite image, on en obtiendrait une grande sans perte de qualité encore mieux que le Scale2x.
  • 3/3 - le must : dessiner à même l'energyMap. C'est ce qu'ils montrent à la fin de la vidéo et ce qu'on commence à faire avec le threshold. Comme l'algo se base sur l'émission d'énergie de l'image. on pourrait ajouter la possibilité d'éditer ce map à la volée en indiquant à l'algo des zones à préserver(un visage, un objet) et des zones à éliminer en priorité. mes petits tests prouvent que c'est possible (c'est ultraviolent d'ailleurs =D ) mais de là à systématiser bien comme il faut et tout il y a du chemin.