Seam Carving Thibaud COGNAT .pdf



Nom original: Seam Carving Thibaud COGNAT.pdf

Ce document au format PDF 1.5 a été généré par / Skia/PDF m52, et a été envoyé sur fichier-pdf.fr le 31/05/2016 à 11:08, depuis l'adresse IP 92.163.x.x. La présente page de téléchargement du fichier a été vue 301 fois.
Taille du document: 1.5 Mo (14 pages).
Confidentialité: fichier public


Aperçu du document


 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

SEAM CARVING
Projet de Traitement d’Image
4AI08
Thibaud COGNAT
Janvier-Mars 2016
 
 

 

 

 
Thibaud COGNAT

 
 

TABLE DES MATIÈRES
 

Problématique
Motivations et limites du projet
Introduction
Fonctions Matlab créées
Principe
Méthode
Matrice énergie
Chemins de pixels
Suppression ou duplication d’un chemin
Suppression
Duplication
Affichage
Présentation des résultats
Conclusion
Bibliographie
 



 
Thibaud COGNAT

 
 

Problématique
 
 
Comment interagir avec une image pour modifier ses dimensions et ses proportions 
sans en affecter son visuel ? 
 
 

Motivations et limites du projet
J’ai  choisi  de  travailler  sur  la  modification  d’images  car  j’ai toujours été intéressé par 
la  manipulation  et  la  retouche  de  photos,  tout  en  ayant un rendu aussi naturel que possible. 
Il  me  semblait  pertinent  d’observer  ce  type  de  modifications  apportées  de  manière 
automatique  à  l’aide  de  modifications  sur  les  pixels  de  l’images,  et  ainsi  sur  sa  matrice 
représentative.  L’étude  de  la  relativité  d’utilité  des  zones  importantes  d’une  image  à  ce 
traitement  ayant piqué ma curiosité, je me suis vite  penché sur ce sujet et j’ai   alors choisi de 
me lancer dans l’implémentation d’un traitement de Seam Carving. 
 
Au  cour  de  mes  recherches  sur  le  sujet,  et  plus  tard  tout   au  long   de  mon  travail 
dessus,   je  me  suis  aperçu  qu’il  existait  certaines  limites  à  cette  méthode.  Par  exemple,  le 
principe  même  repose  sur  le  fait  que  dans  une  image,  certaines  zones  sont  plus  ou  moins 
représentatives  d’une  information  utile,   et,  si  l’on  désirait diminuer la largeur d’une image,  le 
Seam  Carving  supprimerait  les  zones  moins  pertinentes  afin   de  conserver  les  zones 
importantes  et  ne  pas  déformer  l’information.  Or,  il  arrive  un  moment  où   le  programme  n’a 
d’autre  moyen  que  de  supprimer  des  informations  utiles.  En  effet,  l’efficacité  de  ce  type 
d’algorithme sera ainsi soumise au type d’image prise en entrée. 
De  plus,  cette  méthode   nécessitant  une  analyse  matricielle  poussée,  son  temps 
d’exécution  est  relativement  long, par rapport à un redimensionnement classique. J’ai eu, au 
long  de  mon   travail  sur  ce  sujet,  à  modifier  mon  algorithme  afin d’en accélérer la vitesse de 
calcul,   mais  je  me  suis,  au  bout  d’un  moment,  retrouvé  face  aux  limites  des  fonctions 
utilisées. 
 



 
Thibaud COGNAT

 
 

Introduction
 
 
Bon  nombre  de  personnes   se  sont un jour retrouvées confrontées au problème posé 
ici : comment diminuer seulement la largeur ou la hauteur d’une image sans la déformer ?  
 
Il  existe  plusieurs  méthodes  techniques   pour  y  parvenir.  L’une  d’elles,  automatisée, 
qui  s’applique  par  un  traitement  matriciel  sur  l’image  originale  est   appelé   Seam  Carving.  Il 
s’agit  d’une  technique  inventée  en  2007  par  Shai  Avidan  et   Ariel  Shamir.  Le  principe  est  
d’analyser  l’image  pixel  par  pixel  par  un  traitement  automatique  et  de   définir  les  pixels  qui 
changeraient  le  moins  l’information  de  l’image  s’ils  venaient  à  être  supprimés,  pour  ensuite  
les modifier. 
Un  recadrage  standard  d’une  image   selon  l’axe  x  par  exemple,  effectue  une 
approximation  sur  les  pixels  de  chaque  ligne  sur  l’intégralité  de  l’image.  A  l’échelle  d’une 
image,  cette  modification  représente  une  “écrasement”  de  l’image  en  largeur.   Le  Seam 
Carving,  contrairement  à  cette  méthode classique, n’applique une modification qu’aux pixels 
les  moins  pertinents  dans  l’image  (comme  un  point du ciel, un morceau d’asphalte, etc.), ne 
modifiant  pas  l’information  utile.  Ainsi,  à  l’échelle  de  l’image,  ce  traitement  donnera  plutôt 
l’impression  que  les  objets  dignes  d'intérêt   sont  au   premier  plan  de  l’image  et  le  reste  s’en 
éloigne. 
Je  propose,   au  long   de  ce  mémoire,  une  méthode  personnelle  de  Seam  Carving 
implémentée  en  langage  Maltab.  Certains  choix  ont  été  faits  afin  d’avoir  une  programme 
optimal entre le temps d'exécution, l’efficacité et la généralité d’application. 
 
Ma fonction de Seam Carving fonctionne en 3 temps : 
 
­ Calcul  de  la  pertinence  de  chaque  pixel  (c’est  à  dire  à  quel  point  il  est 
représentatif de l’information utile) 
­ Détermination  d’un  chemin  de  pixels  reliant  un  bord   de  l’image  à  l’autre pour 
un coût minimal 
­ Suppression  ou  “duplication”  du  chemin  le  moins  pertinent  (au  coût  total  le 
plus faible) 
 
 

 

 



 
Thibaud COGNAT

 
 

Fonctions Matlab créées
   ​
Resizing.m​
 : Fonction générale qui redimensionne une image. 
Elle prend en entrée:       ­ IO​
 : l’image originale 
­ nvtY​
 : la nouvelle taille désirée en hauteur 
­ nvtX​
 : la nouvelle taille désirée en largeur 
Elle donne en sortie :       ­ I​
 : l’image redimensionnée 
­ I2_original​
 : l’image des énergies 
 
   ​
SeamCarving.m​
 : Fonction qui diminue la largeur d’une image par Seam Carving.  
Elle prend en entrée :       ­ I​
 : l’image originale 
­ I2​
 : la matrice des énergies 
­ pix​
 : le nombre de pixels à supprimer en largeur 
Elle donne en sortie :        ­ I​
 : l’image diminuée 
­ limite​
 : la matrice contenant les chemins supprimés 
­  
   ​
SeamCarvingAugm.m​
 : Fonction qui augmente la largeur d’une image par Seam Carving. 
Elle prend en entrée :        ­ I​
 : l’image originale 
­ I2​
 : la matrice des énergies 
­ pix​
 : le nombre de pixels à ajouter en largeur 
Elle donne en sortie :        ­  I​
 : l’image diminuée 
­ chemin​
 : la matrice contenant les chemins supprimés 
­  
   ​
reduction.m​
 : Fonction qui supprime un chemin dans une image. 
Elle prend en entrée :        ­ originale​
 : l’image originale 
­ vecteur​
 : le chemin à supprimer 
Elle donne en sortie :        ­  plptt ​
: l’image tronquée du chemin 
 
   ​
energy.m​
 : Fonction qui calcule la matrice énergie d’une image. 
Elle prend en entrée :        ­ I​
 : l’image originale 
Elle donne en sortie :         ­ res ​
: la matrice des énergies 
 
   ​
recale.m​
 : Fonction qui redétermine les coordonnées de chaque chemin modifié à partir 
des chemins modifiés précédemment. 
Elle prend en entrée :         ­ matrice​
 : les chemins originaux 
Elle donne en sortie :          ­ nouvelle ​
: les chemins aux coordonnées recalés. 
 
 



 
Thibaud COGNAT

 
 

 

Principe
 
Quand  on  fait  une  modification   de  la  dimension  d’une  image  sur  un  seul  axe,  un 
logiciel  de  base  va  effectuer  un  moyennage  et   appliquer  une  modification  uniforme. 
Intéressons­nous à cette opération sur quelques pixels : 
 
Cas 1 : 

                 
                            
 
Dans  un   cas  simple,  comme  ci­dessus,  avec  une  colonne   qui  se  démarque  sur  un 
fond   uni  où  on  augmente  la  largeur  de  7  à   11  pixels,  l’augmentation  de  largeur  sera 
appliquée au fond avant d’être appliquée à la ligne. 
 
Cas 2 : 

                  
                             
 
Dans  un   cas  plus  complexe,  comme  celui  ci,  un  logiciel  de  base  verra  chaque  
colonne  de  pixels  porteuse  d’autant  d’information  que  les  autres.  Ainsi,  si  l’on  désire  en 
augmenter  la  largeur  de  7   à  10  pixels,   par  exemple,  le  logiciel choisira 3 colonnes de pixels  
de  manière  répartie  et  les  dupliquera.  La  colonne  rouge  d’information  utile  est  alors 
déformée. 
 
Seam Carving : 

     
 
Le  Seam  Carving  fonctionne  en  fait  comme  le cas 1 : L’algorithme détecte les zones 
de  pixels  les   plus  proches   en  couleurs  (les  plus  apparentées  à  un  fond  uni),  et  détermine 
alors  sur  l’image  les  zones  d’information  importante.  Ainsi,  si  l’on  doit  modifier  la largeur de 
cette  image  de  7  à  10  pixels,  l’algorithme  “dupliquera”  (ou  supprimera  dans  le  cas  d’une 
réduction) en priorité ce qu’il a détecté comme étant le “fond”. 
 
Pour  déterminer  les pixels plus ou moins  utiles dans l’image, intervient alors la notion 
d’​
énergie.  ​
L’énergie  d’un  pixel   est  déterminée  par sa proximité  aux pixels avoisinants. Ainsi, 
si  un  pixel  est  utile,   les  couleurs  des  pixels  adjacents   en  seront   relativement  éloignées  et 
son énergie sera faible. 
 
 



 
Thibaud COGNAT

 
 

 
La  différence  entre  une   image  et  un  exemple  comme  ceux­ci  est  qu’une  image  est 
rarement  constituée  exclusivement  de  colonnes  de  pixels  unis.  C’est  pourquoi  il  existe  la 
notion  de  ​
chemins  ​
dans  ce  procédé.  Un  chemin  est  une succession de pixels adjacents (de 
manière  directe  ou  en  diagonale) allant d’un bord à l’autre de l’image. Ainsi, dans une image 
de  dimensions  1920x1080,  un  chemin  en  hauteur,  par  exemple,  sera  constitué  de  1080 
pixels.   A  chaque  élément   du  chemin,  l’élément  suivant  est  déterminé  par  celui  des  trois 
pixels adjacents ayant l’énergie la plus faible. 
 

 

Image 1 : Exemple de chemins dans une image - S
​kyfall (2012) 

 



 
Thibaud COGNAT

 
 

Méthode
Matrice énergie
La  matrice  énergie  est  la  matrice  représentative  de  la  pertinence  d’un  pixel.  Pour  la 
T
déterminer,  on  applique  un  masque  [­1 0  1]  et un masque  [­1  0 1]​
  à la matrice de l’image 
originale.  Ce  masque  applique  une  corrélation  à  l’image  et  nous  permet, pour chaque pixel, 
d’évaluer  l’éloignement  entre  ceux  qui  le  borde  un  à  un.  Pour  cette  opération,  on  utilise  la 
fonction  Matlab  “imfilter.m”,  or  cette  fonction  fait  une  simplification  sur  les  bords  de  l’image 
qui  résulte   en un “ajout” artificiel d’une bordure nulle.  Afin que chaque élément de la matrice 
obtenue  soit  du  même  ordre,  on  ajoute  alors  une   bordure  à  l’image  qui  duplique  chaque 
élément  aux  extrémités.  On  retirera  cette  bordure  après  le  traitement.  C’est  ce  que  fait  ma 
  fonction ​
energy.m​

On   obtient   alors  une  matrice  qui fait les dimensions de l’image  et où chaque élément 
est   une valeur numérique allant de  0 à 1 représentant la pertinence du pixel  associé, comme 
le montre cet exemple de la matrice d’énergies d’une affiche de film : 
 

 

Image 2 : Image originale -The Hateful Eight (2016)
 

 

Image 3 : Image des énergies -The Hateful Eight (2016) 
 
 


 
Thibaud COGNAT

 
 

Chemins de pixels
Les  chemins  de   pixels  sont  déterminés  par  un  passage  sur  la  matrice  d’énergie. 
Comme  dit  précédemment, chaque pixel suivant dans le chemin est déterminé à partir des 3 
pixels  adjacents  au   pixel  courant   en­dessous.  Dans  les  travaux  sur  le  Seam  Carving,  on 
détermine  le  pixel  final  du  chemin  optimal,  en parcourant la matrice en hauteur du haut vers 
le  bas,  et  ensuite,  on  remonte  l’image  du  bas  vers  le  haut  en  partant  de  ce  pixel  comme 
début du chemin. D’un point de  vue logique, c’est optimal, car cela permet d’analyser les cas 
de  manière  plus  complète.  D’un  point  de  vue   pratique,  j’ai  constaté  que si le bas de l’image 
est   trop  complexe,  le  chemin  peut  alors   emprunter  un  parcours  différent,  aboutissant  alors 
vers  des  zones  d’information  utile  qui  seront   modifiées  plus  tard.  Or,  dans  une  image,  en 
général,  le  bas  est   bien  plus  complexe  que  le  haut,  c’est  pourquoi   j’ai  décidé  dans  mon 
traitement,  de   ne  parcourir  l’image  que  du  haut  vers  le  bas.  Le  calcul  des  chemins  se  fait 
  dans la fonction​
 SeamCarving.m​

Ayant  alors,  dans  certains  cas,  un  modèle  moins  parfait,  mais   plus  rapide  et  plus 
général,  j’ai  décidé  de  stocker  les  chemins  à  étudier  dans  une  matrice,  dont  je  me   servirai 
d’ailleurs  pour  les  copier  dans  le  but  d’un  affichage  ultérieur.  Par  exemple,  voici  l’affichage 
des 120 chemins de plus faible coût en x sur l’image prise en exemple précédemment. 
 

 

Image 4 : Affichage des chemins de plus faible coût -The Hateful
Eight (2016)



 
Thibaud COGNAT

 
 

Suppression ou duplication d’un chemin
Suppression
Il  existe  plusieurs  techniques  pour  supprimer  un  ensemble   d’éléments  prédéfinis 
dans  une  matrice.  Celle  que  j’ai  choisie, qui me semble la plus optimale et la plus rapide est 
de  mettre  tous   ces  pixels  à  une  valeur  qu’on  sait  que  l’on  ne  pourra  pas  avoir  autrement 
dans  la  matrice,  et   les  supprimer  (cette  suppression  redimensionnera  notre  matrice  en 
vecteur).  Il  ne  nous  restera  alors  plus  qu’à  redimensionner  la  matrice  dans  les  dimensions  
désirées. 
J’aurais   pu  les   supprimer  tous  à   la  fin  de  mon  programme  plutôt  qu’à  chaque 
itération,  mais  mon  algorithme  est  tel  que  j’aurais  alors  eu  des  recherches  de   chemins  qui 
n’auraient pas pu aboutir de la manière la plus efficace. 
J’appelle  à  chaque  itération,  pour  ma  fonction  de  Seam  Carving,  la  fonction 
  reduction.m​

 
 

Duplication
Pour  la  duplication  de  chemin,  J’ai,  à  chaque  itération,  pour  chaque  ligne,  fait  une 
concaténation  entre  la  partie  à  gauche  du  pixel  à  ajouter,  le  pixel  à ajouter, déterminé de  la 
moyenne  des  pixels  adjacents,  et  la  partie  à  droite.  Cette  méthode  n’est  pas  optimale  car 
elle  nécessite  une  boucle  qui  parcourt  l’image  en  hauteur,  mais  il  est,  hélas,  nécessaire  de 
s’y  prendre  ainsi  pour  l’augmentation  des  dimensions  d’une  image.  Je  fais  cette  opération 
  dans ma fonction ​
SeamCarvingAugm.m​


Affichage
 
Pour  les  affichages,  la  partie  la  plus  complexe  était  d’avoir   les  bonnes  coordonnées 
des  pixels  composants  les  chemins  supprimés,  étant  donné  qu’il   y  a  un  décalage à chaque 
  suppression. C’est pourquoi j’ai créé la fonction ​
recale.m​

Tous  les  affichages  et  la  gestion  entre  mes  fonction  se  fait  dans  ma  fonction 
  Resizing.m 

 
 

 



 
Thibaud COGNAT

 
 

 

Présentation des résultats
 
 
Prenons  une  image  simple  (ici,  une  affiche  de  film  de  taille  300x600),  et  observons 
les  résultats  d’une  augmentation  de  sa  largeur  de   600  à  900  pixels,  par  une  méthode 
classique, puis par notre méthode de Seam Carving : 
 

 

Image 5 : Image originale avant redimensionnement - Interstellar (2014)

 

Image 6 : Image après redimensionnement classique - Interstellar (2014)

 

Image 7 : Image après Seam Carving - Interstellar (2014)

10 

 
Thibaud COGNAT

 
 

 
On   s’intéresse  maintenant  à  une  autre  image  (une  image  de  taille  432x1022,  tirée 
d’un  film)  et  on  fait  la  même  comparaison  cette  fois­ci   pour  une  diminution  de  la  largeur  de 
l’image de 1022 à 700 pixels : 
 

 

Image 8 : Image originale avant redimensionnement - One Upon A Time In
The West (1968)

 

Image 9 : Image après redimensionnement classique - One Upon A Time In
The West (1968)

 

Image 10 : Image après Seam Carving - One Upon A Time In The West
(1968) 
 

11 

 
Thibaud COGNAT

 
 

Conclusion
 
Le  Seam  Carving,  bien  que  non­optimal  dans  certains  cas,  est  une  méthode  très 
complète  pour  la  manipulation  d’images.  En  effet,  un  tel  algorithme  permet  de  modifier  les  
proportions  d’une  image  sans  que   le  résultat  soit  choquant  visuellement,  c’est­à­dire  en 
respectant  les  informations  de  bases.  Le  temps  de  calcul  est  élevé,  mais  on  parle  bien  ici, 
d’un  traitement  qui  s’applique  à  une  image  de  manière  automatique  et  qui  sera,  de   toute 
manière,  plus  rapide  qu’un   traitement  manuel.  Les  limites  du  procédé,  bien  que  non 
négligeable  sont  des  limites  posées  davantage  par  l’appréciation  visuelle  que  par 
l’algorithme. 
Ma  fonction  personnelle  de  Seam  carving  n’est  pas  aussi  poussée   que  celle  de  ses 
créateurs,  mais  j’ai  tenu  à  essayer  d’implémenter  tous  mes  algorithmes  en   ne  me  basant 
que  sur  les   cours  de  traitement  d’image  que  j’avais  eus  et  que  sur  certains  aspects  de 
logique,  trouvant  le  sujet  intéressant  et  voulant  explorer  le  problème  par  mes  propres 
moyens. 
Les  limites  de  mon  algorithme  en  général  sont  surtout  des  limites  de  modifications. 
Par  exemple,  on  ne  peut  pas  multiplier  les  dimensions   d’une  image  par   plus  de  x2. 
cependant,   ce  sont  des  modifications  qui  ne  me  semblaient  pas  nécessaires,  voulant  me 
concentrer sur la rapidité de calcul, entre autres. 
 
Cependant,  on  peut  dire  que   le  Seam  Carving  est  non­pertinent  pour  une 
modification  de   la  largeur   et  de  la  hauteur  à  la  fois.  Ce  qui,  d’après  moi,  est  optimal   est 
d’associer  une  technique  de  redimensionnement  classique  en  conservant  les  proportions 
d’une  image,  puis  d’appliquer  le  Seam  Carving  afin  d’ajouter  ou  de  supprimer  des  pixels 
encore nécessaires à la modification sur un axe. 
 
 

12 

 
Thibaud COGNAT

 
 

Bibliographie
 
 
Alan C BOVIK   ­   2009 
   ​
The Essential Guide to Image Processing  
 
 
Shai AVIDAN & Ariel SHAMIR    ­   2007 
   ​
Seam Carving for Content­Aware Image Resizing
 
 
Mathieu CORD   ­   2015 
   ​
Bases de Traitement des Images ­ Opérations de bases et améliorations 

 

13 


Aperçu du document Seam Carving Thibaud COGNAT.pdf - page 1/14
 
Seam Carving Thibaud COGNAT.pdf - page 3/14
Seam Carving Thibaud COGNAT.pdf - page 4/14
Seam Carving Thibaud COGNAT.pdf - page 5/14
Seam Carving Thibaud COGNAT.pdf - page 6/14
 




Télécharger le fichier (PDF)


Télécharger
Formats alternatifs: ZIP




Documents similaires


seam carving thibaud cognat
corrige 2010 2011
corrige 2010 2011 septembre
corrige2
exercice1
o0u677l

Sur le même sujet..




🚀  Page générée en 0.11s