Modélisation et navigation d'images

Claudia Laramée et Maxime Leclerc

Partie 1 : Segmenatation et synthèse de texture

Algorithme de segmentation

Segmentation par Graph Cut

Cet algorithme est basé sur des coupes de graphes en vision par ordinateur. Nous effectuons un étiquetage binaire des pixels d'une image. Soit ils appartiennent au premier plan ou à l’arrière-plan. Puisque l’utilisateur est impliqué dans le processus, on qualifie cette segmentation d’interactive. Une des principales contributions au problème avec des graphiques a été proposé par Yuri Boykov et Marie-Pierre Jolly avec leurs coupes de graphes interactifs. Ils considèrent chaque pixel dans une image comme un noeud dans un graphique et ajoutent deux noeuds terminaux connectés à tous les pixels, nommés Source et Puit. Chacun de ces deux noeuds est associée au premier plan ou au fond.

Une fois que le graphique est construit, l'algorithme étiquette les pixels par une coupure du graphe. Cette coupe sépare deux types d’arcs: les arcs qui relient les pixels entre eux et les arcs qui relient les pixels à la source ou au puit.

Coupe minimale ou flot maximal

Le problème d’optimisation de coupe minimale est le dual du problème de flot maximal. On peut donc utiliser l’algorithme de Ford et Fulkerson (1962) pour calculer la coupe. Chaque arête possède une capacité. La somme des flux entrant dans un noeud doit correspondre à la somme des flux sortant.

Le coût entre les pixels pénalise les coupes qui séparent les pixels dont les intensités de couleur sont similaires. De plus, on modélise le background et l’avant-plan à l’aide d’histogramme de couleurs.

Résultats

Suppression de l'objet dans l'image originale

Nous avons choisi d'implémenter un algorithme de redimensionnement, tel que vu dans le travail pratique 2, afin de supprimer l'objet sélectionné par l'utilisateur. Nous avons débuté par affecter la valeur de -300 à chaque pixel de l'objet à supprimer de l'image. De cette façon, nous forçons l'algorithme à enlever des chemins qui passent par l'objet que nous désirons faire disparaître.


Voici le résultat de notre algorithme :

Agrandissement de l'image

Pour agrandir l'image redimensionnée jusqu'à sa taille originale, nous avons implémenté un algorithme d'insertion de joints. Cependant, lors de l'implémentation, nous avons dû porter une attention particulière aux joints ajoutés. En effet, puisque nous avons supprimé un objet de l'image, il est essentiel de s'assurer que les joints seront insérées dans la partie de l'image où se trouvait l'objet initialement. Aussi, si nous basons notre implémentation sur l'inverse de l'algorithme de redimensionnement décrit plus haut, le joint ajouté serait toujours au même endroit puisque le plus court chemin ne change pas.

Afin de s'assurer que la partie de l'image affectée par le redimensionnement sera agrandie par notre algorithme, nous avons choisi de découper cette portion de l'image et d'effectuer l'insertion de joints sur cette partie seulement. Par la suite, nous pouvons créer une nouvelle image en concaténant les portions de l'image originale non agrandies avec la portion de l'image agrandie.

Pour ce qui est de ne pas toujours insérer des joints au même endroit, nous avons créé une matrice "masque" qui est composée uniquement de "1" au départ. Par la suite, chaque fois qu'un joint est inséré dans l'image, la valeur de l'élément à la même position dans la matrice "masque" est changée pour 400. Nous multiplions ensuite la matrice "masque" avec la matrice de coûts avant de calculer le chemin minimal. Cette opération a pour but de forcer l'algorithme à ne par choisir un chemin qui a déjà été ajouté.

Malheureusement, comme le démontre le résultat ci-dessous, cette dernière partie de l'algorithme n'a pas très bien fonctionné.

Nous aurions pu tenter une autre approche et calculer les n joints à ajouter à partir de la matrice de coûts du départ. Par la suite, nous aurions conservé ces chemins en mémoire et nous les aurions ajoutés sans devoir recalculer la matrice de coûts à chaque itération. Cette approche nous aurait garanti de ne pas ajouter le même joint plusieurs fois.

Résultats supplémentaires

Partie 2 : Modélisation 3D d'une scène

Le but de cette partie est de créer une scène 3D à partir d'une seule photographie. Le projet s’inspire de Tour in the Picture par Horry et al. La modélisation de la scène comme une boîte 3D en forme de parallélépipède rectangle. Notre interface permet à l'utilisateur de spécifier des contraintes simples sur cette boîte: le mur du fond et le point de fuite.

Un point de fuite est un point dans le plan de l'image qui est l'intersection d'un ensemble de lignes parallèles dans l'espace sur le plan de l'image. Si deux lignes sont parallèles, elle ont le même point de fuite. Le rayon V passant par C est parallèle aux lignes.

Calcul des points de fuite

P_inf est un point à l’infini et v est sa projection. Les lignes parallèles P s’intersectent à P_inf.

Nous calculons aussi la géométrie et les coordonnées 3D de chaque sommet de chacun des cinq plans. Nous trouvons l’orientation de ces plans. Nous projetons ensuite les textures sur les faces de la boîte à l’aide d’homographies. Nous assumons que les murs sont orthogonaux.

Notre interface permet de se déplacer dans la scène: nous pouvons faire tourner le point de vue et zoomer dans la scène à partir d’une simple photo.

Résultats

Références

Liens vers les images utilisées