DEPIXELIZING PIXEL ART

APERÇU

Depixelizing Pixel Art est une méthode de vectorisation spécialement conçue pour offrir de bons résultats sur les images de très basses résolutions. Cet algorithme a été présenté au SIGGRAPH 2011 PAR Johannes Kopf et Dani Lischinski, respectivement de Microsof Research et The Hebrew University. La technique présentée permet de transformer une image de basse résolution appelée « pixel art » en image lisse à échelle variable sans perte d’information.

1. DÉFINITION DES RÉGIONS CONNECTÉES

La première étape est de définir des régions sur l’image afin de reformer les pixels pour créer des régions s’adaptant aux formes et couleurs. Pour cela, on se sert d’un graphique de similarité.

1.1 GRAPHIQUE DE SIMILARITÉ

Ce type de graphique relit les pixels ayant des similitudes. On commence par connecter chaque pixel à ses 8 voisins. Le nœud du pixel est situé au centre de celui-ci. Ensuite, on doit déconnecter les zones de couleur différente. Il suffit de vérifier les voisins de chaque nœud et d’éliminer les liens si la couleur n’est pas semblable en luminosité et en couleur. Dans les zones de couleurs continues, les cases seront encore connectées aux 8 voisins. On élimine donc les 2 liens diagonaux superflus lorsqu’un bloque de 4 pixels est complètement connecté.

1.2 PLANARISATION DU GRAPHIQUE

À cette étape nous cherchons à élimer les liens diagonaux qui se croisent. Par contre, il est maintenant nécessaire de décider quelle zone doit être coupée et quelle zone doit être conservée. Une personne pourrait généralement identifier la forme dessinée par l’artiste. Il s’agit donc ici de programmer l’algorithme à prendre la décision la plus sensée. Pour cela, Kopf et Dani ont établi les règles suivantes. 1. On cherche à conserver une série de nœuds connectés en ligne simple. 2. On cherche à conserver les pixels en premier plan, et possédant donc moins de connexions sur une fenêtre de 8x8. 3. On veut éviter qu’un pixel se retrouve entouré d’autres pixels s’il est possible de le connecter à une série d’autres pixels. Pour chaque heuristique on accorde un certain poids et on élimine la connexion possédant le poids le plus bas.

2. DÉFORMATION DES PIXELS

Maintenant que les zones connectées sont établies, nous pouvons reformer les pixels afin d’adapter les courbes à ces zones pour permettre le redimensionnement de l’image. Le but de cette étape est de rendre l’image vectorielle grâce à des cases définies par un diagramme de Voronoï. On commence donc par créer ce diagramme en associant une case carrée pour chaque pixel.

2.1 REDÉCOUPAGE DES COINS

Pour adapter le diagramme de Voronoï au graphique de similitude, il faut identifier les connexions diagonales et déformer le bloc de pixels voisin en conséquence. On déforme donc ces pixels de façon à connecter les zones de couleurs similaires et à séparer les zones différentes. La technique est expliquée en détail dans l’article, mais pour résumer celle-ci, on cherche à établir des cases possédant un plus grand nombre d’arêtes adaptées aux similitudes. Cela rend un diagramme avec des cases représentant les pixels initiaux, mais reformés de manière à lisser l’image et permettre un agrandissement infini.

2.2 REMODELAGE PAR SPLINES

Pour améliorer ces pixels déformés, il est possible de transformer les côtés des cases en courbes à l’aide des splines. On cherche les arêtes connectées et délimitant des zones de couleurs différentes pour y fixer une courbe définie par une spline passant par les points de connexions. L’article présente aussi une série d’opérations afin d’optimiser la qualité de ces courbes et d’obtenir un résultat encore plus lisse et crédible.

3. INTERPOLATION DE COULEUR

Une fois que le diagramme de Voronoï est établi, il est assez simple de remplir les cases par l’interpolation de l’intensité des pixels de l’image initiale vers l’image agrandie avec la valeur désirée. Cette image finale est fabriquée à partir des cases du diagramme déformé et agrandi ainsi que de la couleur de l’image de basse résolution.

4. RÉSULTATS

La technique de vectorisation rend des résultats très intéressants, surtout en connaissant la très basse résolution des images de type « Pixel Art ». Les images vectorisées par l’algorithme sont déformables sans perte, car cette information est enregistrée en vecteurs sous forme points, de lignes et polygones. Le temps d’exécution de l’algorithme est assez rapide, car l’image d’entrée ne comporte généralement que peu de pixels. L’implémentation n’est pas conçue pour être utilisée sur des images de grande résolution et est trop lente et mal adaptée pour ce type d’image. Pour améliorer le résultat, il est possible d’optimiser la forme des courbes en détectant les contours isolés pour les transformer en courbe à l’aide de B-Splines. L'algorithme n'a pas été programmé en fonction de sa vitesse d'exécution, car cela ne semblait pas nécessaire. Néanmoins, il serait probablement possible d'optimiser la performance afin d'appliquer la technique en temps réel ou sur une séquence vidéo.

4.1 PRÉSENTATION DES RÉSULTATS

4.2 LIMITATIONS DE L'ALGORITHME

La technique utilisée n'est pas toujours aussi efficace et dépend beaucoup de la qualité artistique de l'image pixel. Une image de basse résolution qui a été obtenue par rétrécissement ne présentera pas de bon résultat. Aussi, si l'image utilisée n'est pas bien définie le résultat ne sera pas mieux défini. Comme l'optimisation des courbes par B-Spline n'est pas encore implémentée, on remarque quelques fois une courbe en escaliers selon la grandeur du cercle.

RÉFÉRENCES ET SOURCES

Johannes Kopf et Dani Lischinski • Bowser, Yoshi, Toad, Mario SNES, Mario NES, Dauphin, Boo, Bouclier ©Nintendo Co., Ltd. • Ghost(Bleu) Ghost(Rouge) ©Namco, Ltd. • Bomberman ©Hudson Soft Company, Ltd. • Bâton de Baseball ©Unknown-Power • Space invader ©Taito • Dragon ©Anamnese • Pingouin ©Rathari • Arbre de Noël ©MandysManips • Ordinateur, Disquette ©Microsoft Corp. • Images libres de droits.