26
ICC (SV) – Mini-projet (Version 1.0) Ce document utilise des couleurs et contient des liens cliquables (textes soulignés). Il est préférable de le visualiser en format numérique. 1 Présentation L’objectif de ce mini-projet est de découvrir comment manipuler des images, et en par- ticulier les redimensionner. Imaginons que nous souhaitions rendre l’image Fig. 1 carrée, deux solutions s’offrent habituellement à nous : le rognage (Fig. 2) et l’étirement (Fig. 3). Fig. 1 : Originale Fig. 2 : Rognée Fig. 3 : Étirée 1

ICC (SV) – Mini-projet

  • Upload
    others

  • View
    7

  • Download
    0

Embed Size (px)

Citation preview

Page 1: ICC (SV) – Mini-projet

ICC (SV) – Mini-projet(Version 1.0)

Ce document utilise des couleurs et contient des liens cliquables (textessoulignés). Il est préférable de le visualiser en format numérique.

1 Présentation

L’objectif de ce mini-projet est de découvrir comment manipuler des images, et en par-ticulier les redimensionner. Imaginons que nous souhaitions rendre l’image Fig. 1 carrée,deux solutions s’offrent habituellement à nous : le rognage (Fig. 2) et l’étirement (Fig. 3).

Fig. 1 : Originale

Fig. 2 : Rognée Fig. 3 : Étirée

1

Page 2: ICC (SV) – Mini-projet

Toutefois, si l’on désire conserver les détails et une bonne qualité de l’image, il nous fautune autre solution.

Nous allons dans le cadre de ce mini-projet mettre en oeuvre une technique nommée seamcarving répondant à cet objectif.

L’idée est de réduire la taille de l’image en supprimant les zones qui ne contribuent quepeu à l’impression générale :

Fig. 4 : Seam carving

Si l’on suppose qu’une image est un tableau à deux dimensions de pixels1, on peut parexemple supprimer les colonnes de pixels qui sont peu différentes de leurs voisines. Eneffet, si, par exemple, une colonne de l’image est unie, la disparition de ses pixels passerainaperçue. À l’inverse, une colonne traversant des éléments clés de l’image ne devrait pasêtre affectée.

Il se pose donc la première question de répertorier les pixels en fonction de leur importancedans l’image.

Pour cela, nous allons associer une énergie à chaque pixel, c’est-à-dire une mesure de sonimportance. La technique dite du filtre de Sobel effectue une détection de contours del’image. Nous allons l’utiliser pour associer une énergie aux pixels :

Fig. 5 : Image filtrée avec Sobel, indiquant les zones importantes à préserver

1un pixel pouvant être représenté simplement par une couleur

2

Page 3: ICC (SV) – Mini-projet

Il est en effet naturel de considérer que les pixels faisant partie des contours doiventavoir une énergie (une importance dans l’image) plus forte que les autres. Notez que denombreuses autres variantes sont bien sûr envisageables.

Cela étant, supprimer des colonnes de pixels ne donne que rarement de bon résultats.La plupart des images ne possèdent d’ailleurs pas de régions unies qui couvrent toute lahauteur. Notre premier exemple (Fig. 1) en est notamment dépourvu.

Nous allons donc aussi considérer comme candidates à la suppression des séquences depixels qui ne sont pas forcément sur la même colonne. Néanmoins, pour garder une certainecontinuité, les pixels devront être contigus :

Fig. 6 : Considérer des séquences depixels contigus, pas forcément alignésverticalement, permet de trouver demeilleurs candidats à supprimer

Fig. 7 : Après suppression de208 séquences de pixels, on ob-tient une image carrée

Il s’agira donc de repérer une telle séquence candidate à la suppression, de la supprimerpuis de répéter l’opération : on va ainsi réduire la largeur de 1 à chaque étape jusqu’àatteindre la largeur souhaitée.

2 Structure et code fourni

Le projet est divisé en trois étapes :

• représenter des couleurs (ce qui nous permettra de modéliser les pixels) ;

• filtrer des images en niveaux de gris (notamment pour l’attribution de l’énergie auxpixels) ;

• redimensionner les images selon ce qui est décrit ci-dessus.

À chaque partie du projet correspond un certain nombre de fonctions à compléter. Lestypes à utiliser sont fournis, notamment dans le fichier seam_types.hpp. Le projet utilisele mécanisme de la compilation séparée pour produire un exécutable à partir de code

3

Page 4: ICC (SV) – Mini-projet

répartis sur plusieurs fichiers. Les principes liés à la compilation séparée vous seront ex-pliqués plus en détail au second semestre. Il faut simplement retenir ici que les prototypesde fonctions et déclarations de type se feront dans les fichiers d’entête (avec l’extension.h) alors que le corps des fonctions sera quant à lui situé dans des fichiers de définition(avec l’extension .cpp).

Vous aurez à compléter du code dans le fichier seam.cpp. Des indications précises vousseront données à ce sujet. Les prototypes des fonctions à implémenter sont fournis et nedoivent pas être modifiés. Ces prototypes se trouveront dans le fichier seam.h.

Notez qu’en dehors des méthodes imposées, vous êtes libre de définir toute fonctionsupplémentaire qui vous semble pertinente.

Modularisez et tentez de produire un code propre !

Dans le complément théorique (chapitre 7), à la fin de ce document se trouvent desexplications concernant les divers sujets abordés et les techniques à mettre en oeuvre.

Commencez par lire ces compléments dans les grandes lignes pour appré-hender les points importants impliqués. Une partie de ces éléments vous aura étéexpliquée en cours.

Utilitaires fournis

La manipulation de fichiers étant fastidieuse et trop avancée à ce stade du cours, unepartie du code vous est donnée. En effet, le fichier helper.cpp vous simplifie l’im-port et l’export d’images en C++. Les fonctions read_image(std::string name) etwrite_image(const RGBImage &image, std::string name) permettent de lire (en for-mat .png et .jpg et écrire des images (en format .png). Il n’est en principe pas nécessairede lire ou comprendre ce code.

Tests et contrôle des cas limites

Pour simplifier, vous considérerez que toutes les données fournies en paramètres desfonctions que nous vous demandons d’implémenter sont correctes. Il n’y a pas à vérifier parexemple que les tableaux sont correctement constitués. Les données que nous fournissonsde notre côté et notamment les images seront donc correctes.

Sachant cela, la vérification du comportement adéquat de votre programme vous incombe.Il est important de vérifier soigneusement à chaque étape que vous produisezbel et bien des données correctes avant de passer à l’étape suivante qui vautiliser ces données.

Pour vous aider dans vos vérifications, nous fournissons quelques exemples de tests pos-sibles dans le fichier main.cpp. Vous pourrez utiliser ces tests et les compléter pour vérifierque tout fonctionne. À noter que le programme main.cpp, ne sera pas testé en tant quetel lors de la correction. Modifiez le comme bon vous semble, pour répondre à vos besoins.

4

Page 5: ICC (SV) – Mini-projet

3 Étape 1 : Codage couleur

Cette première partie a pour but de vous familiariser avec la représentation des couleursen informatique, décrite dans le complément théorique (chapitre 7.1).

Dans le cadre de ce projet, nous avons choisi de représenter une image comme étant untableau à deux dimensions de couleurs RGB. L’alias de type RGBImage est fourni à cet effetdans le fichier seam_types.h. De façon analogue, les images en niveaux de gris seront destableaux en deux dimensions de double (alias de type GrayImage dans seam_types.h).

La première dimension représente la ligne, la seconde la colonne (convention utiliséeen algèbre linéaire, pour les matrices). Voici un exemple d’utilisation possible de cesreprésentations :

// On charge une image couleur depuis le disqueRGBImage colors(read_image("img/hiroshige.jpg"));

// Affiche la valeur du pixel en x=50, y=100// l'entier affiché est un code de couleur// dans la représentation RGBcout << colors[100][50] << endl;

// Convertit l'image en niveaux de grisGrayImage gray(to_gray(colors));

// Affiche le niveau de gris du pixel en x=50, y=100cout << gray[100][50] << endl;

Notez que les images sont usuellement manipulées dans un référentiel prenant son origineen haut à gauche et avec un axe des y dirigé vers le bas. Dans l’exemple ci-dessus, x estla coordonnée horizontale dans ce référentiel (c’à-d. une colonne de la matrice) et y lacoordonnée verticale (ligne dans la matrice).

Votre première tâche est donc de compléter le fichier seam.cpp pour passer d’une re-présentation RGB à celle en niveaux de gris, et vice-versa2. À noter qu’il y a une perted’information lors de la conversion en gris.

Consigne : Cette partie sera réalisée au moyen des opérateurs sur les bits. Pour toutesles parties suivantes, vous êtes libre d’utiliser tout outillage de votre choix vous semblantapproprié.

3.1 Codage d’un pixel

Comme expliqué dans le complément théorique (chapitre 7.1), un pixel n’est autre qu’unecouleur en représentation RGB.

2nécessaire pour programmer la technique du filtrage de Sobel notamment

5

Page 6: ICC (SV) – Mini-projet

Commencez par implémenter les fonctions get_red(int rgb), get_green(int rgb) etget_blue(int rgb) qui retournent séparément les différentes composantes (rouge, verteet bleue) d’une couleur. Cette couleur est donnée sous la forme d’un entier, et le résultatest retourné en format flottant, entre 0 et 1 inclus.

Ces fonctions vous permettront d’implémenter ensuite get_gray(int rgb) qui calcule etretourne la moyenne des composantes d’une couleur, toujours en format flottant.

L’opération inverse doit être effectuée par les fonctions get_RGB. La première, get_RGB(doublered, double green, double blue), encode dans un entier les trois composantes flot-tantes. La seconde, get_RGB(double gray), fait de même à partir d’un niveau de gris,c’est-à-dire que les trois composantes sont identiques.

Pour convertir un double, d, en un int utilisez la tournure int(d). Les carrés de couleurà côté des valeurs sont donnés à titre indicatif3.

// Un bleu pâleint color(0x20c0ff);// -> 2146559// On extrait les différentes valeursget_red(color); // -> 0.1254902get_green(color); // -> 0.7529412get_blue(color); // -> 1.0get_gray(color); // -> 0.6261438

// On encode des couleursget_RGB(0.0, 0.0, 1.0); // -> 255 (0x0000ff) ■get_RGB(0.5); // -> 8355711 (0x7f7f7f) ■

3.2 Codage de l’image complète

Grâce aux fonctions précédentes, implémentez to_gray(const RGBImage& image) et to_RGB(constGrayImage& gray). Il s’agit de convertir une image couleur (RGBImage, tableau bi-dimensionneld’entier) vers une image en niveaux de gris (GrayImage, tableau bi-dimensionnel dedouble). Pour cela, vous devez créer un tableau de la bonne taille, et utiliser respec-tivement get_gray et get_RGB pour chaque pixel.

// Une image couleur 2x2RGBImage image = {

{0x20c0ff ■, 0x123456 ■},{0xffffff □, 0x000000 ■}

};

// On la convertit en grisGrayImage gray(to_gray(image));// -> {3Il ne font évidemment pas partie du code et peuvent malheureusement se révéler peu utiles lors d’une

impression en noir et blanc...

6

Page 7: ICC (SV) – Mini-projet

// {0.62614375f, 0.20392157f},// {1.0f, 0.0f}// };

// On revient vers du RGBImageRGBImage back(to_RGB(gray);// -> {// {0x9f9f9f ■, 0x343434 ■},// {0xffffff □, 0x000000 ■}// };

3.3 Tests

Pour tester cette partie, vous pouvez utiliser le programme principal fourni. Ouvrez lecode du fichier fourni main.cpp. Vous verrez que ce programme commence par exécu-ter la fonction run_unit_tests. Cette dernière est définie dans unit_test.cpp. Pourle moment, vous pouvez faire abstraction de toutes les lignes en dessous de l’appelà run_unit_tests dans main.cpp. Ouvrez le fichier unit_test.cpp et examinez lafonction run_unit_tests. Vous verrez qu’elle fait appel à différents tests pre-programméspour vous. Pour cette partie du projet, il s’agit des tests déjà décommentés. Si vous lancezle programme principal, l’exécution doit indiquer le message [Passed] pour tous les tests.En cas d’erreur, vous devriez avoir un message d’erreur signalé par [Failed] et vousindiquant la valeur attendue et la valeur que vous calculez. Par exemple :

---------------test_color---------------....With color Blue:Testing get_red(): [Failed]

expected: 0computed: 0.2

qui indique que la fonction get_red appelée pour la couleur bleue donne par exemple lavaleur fausse 0.2 au lieu de la valeur correcte 0.

Les tests fournis ne sont pas exhaustifs. De manière générale dans le projet, vousêtes encouragés à tester votre code dans d’autres situations ou pour d’autres données envous inspirant du code fourni. Vous pouvez donc sans problème faire des ajouts pertinentsà main.cpp et unit_test.cpp.

Test graphiques Vous avez également la possibilité de tester graphiquement votreprogramme. Pour ceci, examinez à nouveau le contenu de main.cpp. La ligne

std::string in_path = "img/americascup.jpg";

permet de spécifier une image du répertoire fourni img à prendre comme jeu de test. Sivous décommentez la ligne

7

Page 8: ICC (SV) – Mini-projet

// test_to_gray(in_path);

un peu plus bas, vous devriez après exécution du code, voir un fichier nommé test_grayed.pngapparaître au même niveau que votre fichier main.cpp. Il s’agit du résultat graphique issude l’appel à to_gray sur le fichier d’entrée. Nous avons fourni dans expected_outputs/quelques exemples de résultats attendus. Par exemple pour img/americascup.jpg enentrée, le fichier de sortie, test_grayed.png, que vous obtenez devrait être identique àce que nous avons fourni dans expected_outputs/americascup_grayed.png. Les imagesobtenues, peuvent être visualisées en les ouvrant avec un outil tel que gimp ou dans unnavigateur.

4 Convolution

Cette deuxième partie se veut une introduction au traitement d’image. Parmi toutesles opérations possibles sur une image, nous n’aborderons que le flou et la détection decontour avec Sobel. Ces deux méthodes sont des applications du filtrage d’image, décritdans le complément théorique (chapitre 7.2).

L’application de filtres sur une image est ce que l’on appelle la convolution d’images4.Voici l’esprit dans lequel on souhaite par exemple tester le filtre de Sobel (mis en oeuvrepar une fonction sobel) :

// On charge une image en niveau de grisGrayImage gray(to_gray(read_image("img/hiroshige.jpg")));

// On applique un filtre de Sobel (détection de contours)GrayImage sobel(sobel(gray));

// On encode l'image pour l'afficherRGBImage result(to_RGB(sobel));write_image(result, "test_sobel.png"); // crée un fichier

// nommé test_sobel.png// que vous pouvez

visualiser// en l'ouvrant avec

un outil comme gimp// ou dans un navigateur

Pour cette partie, il vous est donc demandé de compléter le fichier seam.cpp pour appli-quer des filtres.

4.1 Étape 2 : Filtres

Tout d’abord, implémentez la fonction clamp(long int& val, long max) ramenant lavaleur val à zéro si elle est inférieure strictement à zéro et à max si elle est supérieure ou

4un filtre linéaire est appliqué sur une image via une matrice/noyau de convolution

8

Page 9: ICC (SV) – Mini-projet

égale à max.

Cette fonction permettra, si des coordonnées calculées pour un pixel se trouvent hors del’image, d’utilisez à la place la valeur du pixel le plus proche.

Grâce à cela, complétez la fonction filter(const GrayImage& gray, const Kernel&kernel) pour calculer la convolution d’une image avec un noyau. Pour rappel, la fa-çon de procéder est décrite dans les complément théorique (chapitre 7.2). Notez qu’unnoyau a forcément une largeur et une hauteur impaires, le type Kernel est fourni dansseam_types.h.

Vous supposerez les images et les noyaux correctement constitués.

Ensuite, utilisez cette fonction pour définir smooth(const GrayImage& gray), sobelX(constGrayImage& gray) et sobelY(const GrayImage& gray), ayant respectivement les noyauxsuivants : 1

10110

110

110

210

110

110

110

110

Fig. 8 : Noyau de smooth

−1 0 1−2 0 2−1 0 1

Fig. 9 : Noyau de sobelX

−1 −2 −10 0 01 2 1

Fig. 10 : Noyau de sobelY

Et enfin, la fonction sobel(const GrayImage& gray) doit utiliser sobelX et sobelY pourcalculer la magnitude du filtre de Sobel. C’est-à-dire calculer la norme des composantesde Sobel

√x2 + y2 pour chaque pixel de l’image5

// Une image en niveau de gris 2x2GrayImage gray = {

{0.5, 1.0},{0.2, 0.0}

};

// On peut utiliser clamp pour garantir de ne pas «déborder»//accès à gray en (0, 0); // -> 0.5//accès à gray en (1, 0); // -> 0.2//accèy à gray (2, -1); // -> 0.2

// On peut appliquer le flou et Sobelsmooth(gray); // -> {{0.49, 0.62}, {0.3, 0.29}}sobelX(gray); // -> {{1.3, 1.3}, {-0.1, -0.1}}sobelY(gray); // -> {{-1.9, -3.3}, {-1.9, -3.3}}sobel(gray);// -> {{2.302173, 3.5468295}, {1.9026297, 3.3015149}}

5vous utiliserez pour cela la méthode C++ sqrt de la bibliothèque cmath.

9

Page 10: ICC (SV) – Mini-projet

4.2 Tests

Pour tester cette étape, vous pouvez décommenter les tests test_SobelX_*, test_SobelY_*,test_Sobel_* et !test_smooth_*dans le fichier unit_test.cpp (où * est un chiffre). Sivotre code est correct, vous ne devriez obtenir que des messages [Passed].

Vous pouvez comme pour l’étape précédente, utiliser des tests graphiques (test_smoothet test_sobel). Des exemples de résultats graphiques attendus sont dansexpected_output/americascup_smoothed.png et expected_output/americascup_sobeled.png.

5 Étape 3 : Graphes et redimensionnement

Cette troisième et dernière partie se veut une introduction aux graphes. Et évidemment,l’implémentation du redimensionnement !

// On charge une image couleurRGBImage image(read_image("hiroshige.jpg"));

// On applique le filtre de Sobel, qu'on utilise comme énergieGrayImage sobel(sobel(to_gray(image)));

// On cherche le meilleur cheminPath seam = find_seam(sobel);/*on peut utiliser les utilitaires fournis pour colorer le

meilleurchemin (à des fins de vérification)*/RGBImage image_with_highlighted_seam(highlight_seam(image,

seam)

//on supprime le chemin de pixels de l'imageRGBImage shrinked_image(remove_seam(image, seam));/*on peut visualiser image_with_highlighted_seam ou

shrinked_imageen les ouvrant avec un outil comme gimp ou dans un navigateur*/

Pour cette partie, il vous est demandé de compléter le fichier seam.cpp. En utilisant unalgorithme pour trouver le chemin le plus court dans un graphe, vous pourrez identifier(et enlever) le chemin de pixels de l’image le moins significatif (celui qui participe le moinsà la qualité de l’image).

10

Page 11: ICC (SV) – Mini-projet

5.1 Chemin le plus court

L’aspect le plus important de cet exercice est la recherche du chemin le moins coûteuxentre deux sommets d’un graphe. Les divers aspects nécessaires concernant les graphessont décrits dans le complément théorique (chapitre 7.3)

Prenez note du fait que dans votre code :

• un noeud de graphe sera défini, au moyen du type fourni Node, comme une structure ;

• un graphe sera défini, au moyen du type fourni Graph, comme un tableau dynamiquede Node ;

• un chemin sera défini, au moyen du type fourni Path, comme un tableau dynamiqued’indices (il s’agit de l’ensemble des indices des noeuds constituant le chemin).

Un noeud est caractérisé par la liste de ses successeurs (donnés par leurs indices dans legraphe auquel appartient le noeud) et un coût. Comme expliqué dans les compléments,ce coût correpondra à la valeur/énergie d’un pixel.

Implémentez la fonction shortest_path(Graph& graph, size_t from, size_t to) quicalcule le chemin reliant deux noeuds entre eux et ayant le coût total le plus bas.

Pour cela, la fonction reçoit en argument le graphe, l’indice du noeuds de départ et l’indicedu noeud destination. Si aucun chemin n’existe, retournez un chemin vide.

Pour pouvoir mettre en oeuvre l’algorithme suggéré dans les compléments, un noeud doitmémoriser la distance (somme des coûts) entre chaque noeud et le noeuds de départ. Deplus, nous souhaitons aussi pouvoir reconstituer tout le chemin (l’ensemble des noeudspermettant d’aller du départ à la destination dans le chemin de meilleur coût). C’estprécisément ce qui permettra de supprimer tout un chemin de pixels non pertinents. Pourcela, la structure de données Node contient également une champs distance_to_target(distance séparant le noeuds de départ du noeud) et un champ predecessor_to_target(indice dans le graphe du prédécesseur du noeuds dans le plus court chemin).

Vous pourrez utiliser numeric_limits<double>::max() pour représenter une valeur « infinie ».Voici un exemple de graphe, un autre exemple avec détail du calcul du chemin est fournidans les compléments :

// Liste d'adjacenceconstexpr INF(numeric_limits <double >::max());Graph graph = {

/* 0 -> */ {{1, 2}, 0.5, INF, 0},/* 1 -> */ {{0, 3}, 1.0, INF, 0},/* 2 -> */ {{3} , 2.0, INF, 0},/* 3 -> */ {{2, 4}, 3.0, INF, 0},/* 4 -> */ {{4} , 4.0, INF, 0}

};

// Calcul du chemin le plus court entre 0 et 4Path path(shortest_path(graph, 0, 4));

11

Page 12: ICC (SV) – Mini-projet

// -> {1 ,3}/* graph ->/* 0 -> */ {{1, 2}, 0.5, 0.5, 0},/* 1 -> */ {{0, 3}, 1.0, 1, 0},/* 2 -> */ {{3} , 2.0, 1, 0},/* 3 -> */ {{2,4} , 3.0, 2, 1},/* 4 -> */ {{4} , 4.0, 5, 3}}

Dans l’ordre les champs de l’exemple ci-dessus sont : la liste des prédécesseurs, le coût, ladistance depuis le noeud de départ et l’indice du prédécesseur.

L’algorithme du plus court chemin va donc mémoriser dans chaque noeud, l’indice deson prédécesseur sur le chemin de moindre coût menant à la destination et c’est ce quipermettra de reconstituer le chemin à supprimer de l’image.

5.2 Application au redimensionnement

Codez enfin la fonction find_seam(const GrayImage& gray) en charge de trouver laséquence de pixel la moins coûteuse, au moyen de la méthode shortest_path. Pour cela,il faut construire le graphe qui correspond à l’image, tel qu’expliqué dans le complémentthéorique (chapitre 7.4). Le résultat contient la colonne de chaque pixel emprunté. Eneffet, vu qu’on supprime exactement un pixel par ligne, il est redondant de stocker laligne correspondante. Vous pourrez ensuite vérifier que la suppression de ce chemin depixels obéit aux objectifs du projet en utilisant des fonctions utilitaires fournies :

highlight_seam(const RGBImage& ,const Path& seam)

etremove_seam(const RGBImage& ,const Path& seam)

La première peint en bleu la séquence de pixels seam sur l’image. La seconde supprimeles pixels correspondant à la séquence seam.// Une image 3x3RGBImage image({

{0x888888, 0x666666, 0xcccccc},{0x000000, 0x111111, 0x222222},{0xbbbbbb, 0xffffff, 0x666666}

});write_image(image, "test3_3_image.png");

GrayImage gray(to_gray(image));// On cherche le meilleur cheminPath seam = find_seam(gray); // -> {1, 1, 2}

// On calcule une image où la séquence de pixel// est coloréeRGBImage image_with_colored_seam(highlight_seam(image, seam));write_image(image_with_colored_seam , "colored_seam_3_3.png");

12

Page 13: ICC (SV) – Mini-projet

// vous pouvez visualiser le fichier colored_seam_3_3.png enl'ouvrant

// avec gimp ou dans un navigateur

// On supprime les pixels concernésRGBImage resized = remove_seam(image, seam);// -> {// {0x888888, 0xcccccc},// {0x000000, 0x222222},// {0xbbbbbb, 0xffffff}// };

write_image(resized, "best3_3_image.png");// vous pouvez visualiser les fichiers .png en les ouvrant// avec gimp par exemple (il faudra beaucoup «zoomer»)

5.3 Tests

Procédez comme pour les étapes précédentes. Dans le fichier unit_test.cpp vous pouvezdécommenter les tests commençant par test_create_graph, test_shortest_path() ettest_find_seam. Pour les tests graphiques, il faut décommenter les lignes :

// size_t num_seam = 10u; /* high value will slow things down */// test_hightlight_seam(in_path, num_seam);// test_remove_seam(in_path, num_seam);

vous devriez obtenir pour "img/americascup.jpg" les images test_highlighted_seam.pnget test_removed_seam.png correspondant respectivement à americascup_10_highlighted_seam.pnget à americascup_10_removed_seam.png.

6 Aller plus loin

Si vous complétez avec succès les trois parties, vous obtiendrez la note maximale pour ceprojet. Néanmoins, si vous avez l’envie (et le temps), nous vous encourageons à continuer !Vos contributions supplémentaires seront rédigées dans un fichier extension.h (protoypeset nouveaux types) et extension.cpp (définitions des fonctions). L’inclusion #include"extensions.hpp" placée au début du fichier extension.cpp fera le lien entre les deux.La première instruction de extensions.h devra être #pragma once.

Cet exercice est basé sur le travail de Shai Avidan et Ariel Shamir, intitulé Seam Carvingfor Content-Aware Image Resizing. Libre à vous de le consulter en ligne pour voir à quoiressemble un paper. Ils présentent entre autres différentes applications de l’algorithme quevous avez implémenté.

Parmi les idées possibles, en voici quelques-unes :

13

Page 14: ICC (SV) – Mini-projet

• Appliquer l’algorithme horizontalement, pour réduire la hauteur des images. Enalternant entre les deux versions, vous pourrez ainsi redimensionner selon la largeuret la hauteur.

• Au lieu de supprimer le chemin, il est possible de le dupliquer et ainsi élargir l’image.Avidan et Shamir discutent de cette question en détail.

• Un autre point qu’ils proposent est de manuellement modifier le poids de certaineszones de l’image. Cela permet de forcer certaines zones à disparaître, ou au contraireà rester quoi qu’il advienne.

14

Page 15: ICC (SV) – Mini-projet

7 Complément théorique

7.1 Couleurs, pixels et binaire

Une image est formée à partir d’une infinité de rayons de lumière qui viennent heurternotre rétine. Toutefois, nos yeux et notre cerveau ne sont pas capables de percevoir etencore moins de gérer une quantité infinie d’information. C’est un problème récurrent dansde nombreux domaines, et les ordinateurs n’y font pas exception. La solution consiste àapproximer l’image par une quantité finie de valeurs. On parle donc d’approximationdiscrète d’un phénomène continu.

Il est fort probable que vous connaissiez la notion de pixel (littéralement picture element),qui représente un point de l’écran. Dans la même idée, une image dite matricielle estcomposée d’une grille à deux dimensions de pixels. En d’autres termes, il s’agit d’unematrice de couleurs. Bien qu’il existe d’autres formats, chacun ayant ses propres avantageset faiblesses, nous nous contenterons de cette représentation pour cet exercice. Il s’agit eneffet du modèle le plus simple et efficace pour le traitement d’image.

Quant aux couleurs elles-mêmes, il est aussi nécessaire de les discrétiser. Les couleurss’obtiennent par synthèse d’un nombre limité de couleurs primaires.

La peinture utilise un modèle de synthèse dit soustractif6. C’est avec un tel modèle quel’on peut dire que mélanger du jaune et du bleu donne du vert. A contrario, les modèlesdit additifs combinent les lumières de plusieurs sources colorées dans le but d’obtenir unelumière colorée.

La synthèse additivedes couleurs utilise généralement trois lumières colorées : une rouge,une verte et une bleue (RGB en anglais pour red, green, blue). Le mélange de ces troislumières colorées en proportions égales donne la lumière blanche. L’absence de lumièredonne du noir.

Les LEDs des écrans utilisent le procédé de la synthèse additive. Nous allons donc utiliserRGB pour représenter nos couleurs, bien qu’il soit tout à fait possible d’utiliser d’autresmodèles et de les combiner.

Fig. 11 : Pixel d’un écran Fig. 12 : Modèle additif Fig. 13 : Modèle soustractif

6soustractif, car plus on ajoute des couleurs, moins il y a de luminosité

15

Page 16: ICC (SV) – Mini-projet

Pour être précis, une couleur est représentée sur 3 bytes (soit 24 bits). Cela permet 28 = 256niveaux de rouge, vert et bleu, allant de 0 à 255. Ainsi, on peut représenter 2563 =16 777 216 couleurs différentes. L’oeil humain étant capable de percevoir dans l’ordre de300 000 nuances seulement, il n’est donc pas nécessaire d’avoir plus de précision ! L’unitéde base de la majorité des processeurs étant un entier 32 bits, il est possible d’y stocker les3 composantes. Il nous reste même 8 bits inutilisés, représentant parfois la transparenceque l’on nomme alpha (d’où le modèle ARGB).

Coleurs Inutilisé/Alpha Rouge Vert BleuChiffres binaires 00000000 00100000 11000000 11111111Chiffres décimaux 0 32 192 255

Le binaire a évidemment un rôle majeur à jouer en programmation. Même si vous neles avez probablement pas encore rencontrées, il existe des opérations qui permettentde manipuler les bits des entiers. Toutes les opérations booléennes ont leurs équivalentsbinaires.

// Notre couleur en binaireint x = 0b00000000001000001100000011111111;// -> 2146559 (0x20c0ff) ■

// Décale de 8 bits vers la droiteint y = x >> 8; // -> 0b000000000010000011000000

// ET binaire, ce qui a pour effet de ne garder que les 8// premiers bitsint z = y & 0b11111111; // -> 0b11000000 -> 192// On a bien récupéré notre composante verte à 192// on aurait aussi pu écrire: int z = y & 0xff;

Les code RGB donnés sous la forme d’entiers dans les exemples ci-dessus, sont parfoismanipulés dans une variante décimale entre 0 et 1. Pour obtenir la variante décimale duz de l’exemple ci-dessus, on écrirait :

double doubleZ = z / 255.0;

Notez qu’un entier peut être manipulé et affiché en différents formats. Les littéraux detype hexadécimal ou binaire sont respectivement préfixés par 0x et 0b. Peut importe letype de représentation utilisé pour les valeurs, le format en interne de l’entier reste lemême (codage sur 32 bits en général en C++ pour un int).

16

Page 17: ICC (SV) – Mini-projet

Voici un exemple de code qui illustre ces points (cela peut être utile de vous inspirer pourfaire des vérifications ou du « debugging ») :

//format hexadécimal:int i (0xFF0000); // affecte la valeur 16711680 à i

//format décimal:int j(16711680); // affecte à j la même valeur que

//celle stockée dans i

//format binaire:int k(0b00000000111111110000000000000000); //affecte à k la

// même valeur//(16711680)

// affiche i (par défaut le format d'affichage est endécimal):

std::cout << i << std::endl; // affiche 16711680

// impression en format hexadecimal:std::cout << hex << i << dec << std::endl; // affiche ff0000

// puis revient au// format décimal// pour la suite

// impression en format binaire// (nécessite l'inclusion de <bitset >) :std::cout << bitset <32>(i) << std::endl; // affiche:

// 00000000111111110000000000000000

17

Page 18: ICC (SV) – Mini-projet

7.2 Filtres et convolution

En traitement du signal, un filtre est une opération appliquée à l’ensemble des données.Un exemple simple est le lissage, consistant à supprimer les détails pour n’en garder queles formes principales. Une manière de calculer ceci est de faire la moyenne des valeursenvironnantes.

Fig. 14 : Signal original Fig. 15 : Moyennes locales

Ce concept peut s’appliquer aux images, en combinant les pixels voisins.

0.1 0.5 0.2

0.2 0.4 0.3

0.3 0.8 0.9

0.2 0.2 0.1 0.3 0.4

0.3 0.3

0.4 0.5

0.2 0.7

0.5 0.4 0.6 1.0 0.9

110

110

110

110

210

110

110

110

110

0.250.280.32

0.340.410.41

0.490.56 0.7

0.31

10+ 0.8

1

10+ 0.9

1

10+ 0.2

1

10+ 0.4

2

10+ 0.3

1

10+ 0.1

1

10+ 0.5

1

10+ 0.2

1

10= 0.41

Fig. 16 : Exemple de calcul de la valeur d’un pixel de convolution

Une remarque doit être faite quant aux bords de l’image. Avec un filtre 3×3, pour calculerle pixel en haut à gauche, il nous manque 5 valeurs. La solution que nous emploieronsdans ce projet consiste à prendre la valeur du pixel le plus proche :

? 0.5 0.2

? 0.4 0.3

? ? ?

0.1 0.3 0.4

0.3

0.5

0.5 0.5 0.2

0.4 0.4 0.3

0.4 0.4 0.3

0.1 0.3 0.4

0.3

0.5

Fig. 17 : Dans les bords de l’image, on utilise les valeurs les plus proches

Cette opération, la convolution, est uniquement définie par les coefficients utilisés, stockéssous forme d’une matrice nommée noyau. Ainsi, une multitude d’opérations différentes

18

Page 19: ICC (SV) – Mini-projet

peuvent être définies suivant les noyaux :

[1] 1

10110

110

110

210

110

110

110

110

−1 0 1−2 0 2−1 0 1

−1 −2 −10 0 01 2 1

Identité Lissage Sobel X Sobel Y

Fig. 18 : Noyaux et exemples

Les filtres de Sobel sont intéressants pour détecter les coutours de l’image. Sobel X etSobel Y représentent respectivement les variations horizontales et verticales de l’image.

En les combinant, c’est-à-dire en prenant la norme des composantes√

x2 + y2, on obtientla variation totale pour chaque pixel. En d’autres termes, on peut déterminer si un pixelest très différent ou non de ses voisins. Pour notre exercice, cela s’avère donc être unemesure de l’importance d’un pixel, ce qui en fait une bonne fonction d’énergie.

Soit im une image en niveaux de gris, imX l’image résultant de l’application du filtre SobelX à im et imY l’image résultant de l’application du filtre Sobel Y à im. Le filtre de Sobelva concrètement créer, à partir de im, une nouvelle image im' où chaque pixel [i][j]vaut

√x2 + y2, x étant la valeur du pixel [i][j] dans imX et y celle du pixel [i][j]

dans imY.

Fig. 19 : Le filtre de Sobel détecte les contours d’une image, ce qui en fait une bonnemesure de l’énergie

19

Page 20: ICC (SV) – Mini-projet

7.3 Graphes et chemin le plus court

Dans de nombreux cas, un problème peut être représenté par ce que l’on nomme un graphe.Il s’agit d’un objet mathématique composé de points, appelés sommets, connectés par desarêtes. Nous ne nous intéresserons qu’au graphes dits dirigés, c’est-à-dire que les arêtesont un sens. On nomme successeurs et prédécesseurs les sommets reliés à un sommeten particulier, suivant l’orientation. Enfin, on nomme chemin une séquence de sommetsconnectés entre eux. Dans l’exemple suivant (Fig. 20) :

• 1 et 3 sont les successeurs de 0, mais 2 n’a aucun successeur.

• 1 et 5 sont les prédécesseurs de 2, mais 0 n’a aucun prédécesseur.

• 0–1–2 et 0–3–4–5 sont des chemins, mais 2–1–0 n’en est pas un.

0 1 2

3 4 5

Fig. 20 : Un graphe dirigé avec 6 sommets

Il est aussi possible d’assigner des valeurs à chaque sommet, représentant par exemple lecoût pour emprunter ce chemin. Ainsi, dans le graphe pondéré suivant (Fig. 21), seuls 3chemins relient 0 à 2 : 0–1–2, 0–3–4–1–2 et 0–3–4–5–2, coûtant respectivement 12, 16 et8. Le chemin le plus court est donc 0–3–4–5–2.

0 1 2

3 4 5

1 9 2

1 3 1

Fig. 21 : Un graphe dirigé et pondéré, avec le chemin le plus court reliant 0 à 2

Pour représenter des graphes en C++, plusieurs solutions existent. Dans cet exercice,nous utiliserons une liste de noeuds, où chaque noeud représente un sommet du graphe etconnait la liste de ses successeurs directs. A chaque noeud correspond aussi un coût :

Graph graph = {// dans l'ordre: successeurs , coût, distance// vers la destination ,

20

Page 21: ICC (SV) – Mini-projet

// indice du predecesseur dans le// chemin menant à la destination.// Au départ le coût vaut// INF = numeric_limits <double >::max()// et l'indice du prédécesseur vaut zéro/* 0 -> */ {{1, 3}, 1.0, INF, 0},/* 1 -> */ {{2} , 9.0, INF, 0},/* 2 -> */ {{} , 2.0, INF, 0},/* 3 -> */ {{4} , 1.0, INF, 0},/* 4 -> */ {{1, 5}, 3.0, INF, 0},/* 5 -> */ {{2} , 1.0, INF, 0}

};

// Exemplesgraph.size() // 6 sommetsgraph[0].successors.size(); // le sommet 0 a 2 successeursgraph[1].successors[0]; // le sommet 1 est connecté à 2graph[4].costs; // le sommet 4 coûte 3.0

Il reste la question de trouver le chemin le plus court. Énumérer toutes les possibilitésétait possible dans l’exemple précédent. Mais pour des graphes plus grands, cela s’avèretrop long. Nous utiliserons donc une méthode inspirée de l’algorithme de Dijkstra.

Le principe est de déterminer le meilleur prédécesseur de chaque sommet, par rapport àun sommet initial. En d’autres termes, on cherche les successeurs qui forment les cheminsoptimaux, depuis la source vers tous les points du graphe. Dans l’exemple précédent(Fig. 21), le meilleur prédécesseur de 2 est 5, car il contribue au plus court chemin entre0 et 2. Pour arriver à ce résultat, l’idée est de prendre chaque sommet séparément et devérifier s’il peut améliorer un chemin. L’algorithme proposé est le suivant :

21

Page 22: ICC (SV) – Mini-projet

Algorithm 1 Algorithme de Dijkstra modifiéfor all v ∈ vertices do

distance(v)←∞bestPredecessor(v)← null

end fordistance(from)← cost(from)modified← truewhile modified do

modified← falsefor all v ∈ vertices do

for all n ∈ successors(v) doif distance(n) > distance(v) + cost(n) then

distance(n)← distance(v) + cost(n)bestPredecessor(n)← vmodified← true

end ifend for

end forend while

Vous trouverez ci-dessous (Fig. 22 et suivantes) un exemple de déroulement pas à pas decet algorithme. Dans ces figures, une étiquette x-y est associée à chaque sommet. x estle poids/coût du sommet et y est la distance connue à ce sommet en partant depuis 0.Ainsi au pas 3 (où l’on s’intéresse à tous les successeurs du noeud 1), la distance la plusfaible connue de 0 à 2 est 12. Cette distance sera réduite à 8 au pas 5 (où l’on s’intéresseà tous les successeurs du noeud 5).

0 1 2

3 4 5

1-1 9-∞ 2-∞

1-∞ 3-∞ 1-∞ Fig. 22 : 1. Aucun prédécesseur n’a étésélectionné, aucun chemin ne part de 0 pourl’instant.

0 1 2

3 4 5

1-1 9-10 2-∞

1-2 3-∞ 1-∞ Fig. 23 : 2. Les successeurs de 0 forment deschemins vers 1 et 3.

22

Page 23: ICC (SV) – Mini-projet

0 1 2

3 4 5

1-1 9-10 2-12

1-2 3-∞ 1-∞ Fig. 24 : 3. Le successeur de 1 forme unchemin vers 2.

0 1 2

3 4 5

1-1 9-10 2-12

1-2 3-5 1-∞ Fig. 25 : 4. Le successeur de 3 forme unchemin vers 4.

0 1 2

3 4 5

1-1 9-10 2-12

1-2 3-5 1-6 Fig. 26 : 5. Les successeur de 4 forment unchemin vers 1 et 5, mais celui vers 1 n’est pasmeilleur.

0 1 2

3 4 5

1-1 9-10 2-8

1-2 3-5 1-6 Fig. 27 : 6. Le successeur de 5 forme unmeilleur chemin vers 2.

0 1 2

3 4 5

1 9 2-8

1 3 1 Fig. 28 : 7. Reconsidérer les successeurs desautres sommets n’améliore aucun chemin. Lemeilleur chemin entre 0 et 2 est donc 0–3–4–5–2 avec un coût total de 8.

23

Page 24: ICC (SV) – Mini-projet

Une fois qu’on a déterminé tous les meilleurs prédécesseurs, il suffit de partir de l’objectifet de remonter jusqu’à la source.

7.4 Réduction de problèmes

Un concept important en algorithmique est nommé réduction. Le principe est simple : ilvaut mieux réutiliser des algorithmes existants que de réinventer la roue à chaque pro-blème. Ainsi, si un nouveau problème se présente, il est souvent plus simple de transformercette question en un problème connu.

Dans le cadre de cet exercice, nous savons déjà résoudre le problème du plus court cheminentre deux sommets. Pour trouver la séquence de pixel qui minimise l’énergie traversée,nous allons transformer notre image en graphe. Chaque pixel devient un sommet, connectéà ses voisins directs.

Pour être précis, nous devons partir de l’un des pixels de la première ligne de l’image.Puis, choisir à chaque ligne un des 3 pixels au-dessous, jusqu’à atteindre le bas. Pour cela,ajoutons un unique point de départ et point d’arrivée, et appliquons notre algorithme :

Fig. 29 : Originale

Fig. 30 : Graphe indiquant lemeilleur chemin

Fig. 31 : Image réduite

Le seul défi pour cette partie sera donc de créer ce graphe, le reste du travail ayant déjà étéfait. Pour cela, il faut attribuer un numéro à chaque pixel, correspondant aux sommets dugraphe. De plus, il doit être possible de récupérer la ligne et la colonne depuis ce numéro.Bien que vous soyez libres de construire ce graphe comme vous le préférez, nous voussuggérons la technique suivante :

24

Page 25: ICC (SV) – Mini-projet

20

210 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

21

Fig. 32 : Exemple de numérotation des pixels, ligne par ligne, tel que number = row ∗width+ column

Ce qui donne en C++ (et en explicitant chaque instruction, ce qui n’est pas forcément cequ’il est attendu que vous fassiez) :

constexpr INF(numeric_limits <double >::max());// Créer les tableaux pour stocker les pixelsGraph graph(vector<Node>(4 * 5 + 2));

// Le pixel "début" vert est connecté à la première lignesize_t from(4*5);graph[from]. successors= {0, 1, 2, 3, 4};graph[from].costs = 0;graph[from].distance_to_target = INF;graph[from].predecessor_to_target = 0;

// Le pixel "fin" rouge n'a pas de successeursize_t to(4 * 5 + 1);graph[to].successors = {};graph[to].costs = 0;graph[to].distance_to_target = INF;graph[to].predecessor_to_target = 0;

// Le premier pixel, en haut à gauchesize_t left_high(0 * 5 + 0);graph[left_high].successors = {5, 6};graph[left_high].costs = gray[0][0];graph[left_high].distance_to_target = INF;graph[left_high].predecessor_to_target = 0;

// Le deuxième pixel de la première ligne

25

Page 26: ICC (SV) – Mini-projet

size_t pixel12(0 * 5 + 1);graph[pixel12].successors = {5, 6, 7};graph[pixel12].costs = gray[0][1];

// ...

// Calcul du chemin le plus courtPath shortest(shortest_path(graph, from, to));

// On récupère la colonne pour chaque ligne (sans le début et// la fin)Path result(shortest.size(());size_t width = gray[0].size(); // 5for (size_t i(0); i < shortest.size(); ++i) {

result[i] = shortest[i] % width;}

return result; // -> {0, 6, 12, 16}

Évidemment, il s’agira de produire un code qui fonctionne pour toute taille d’image, etpas seulement des 4× 5.

26