Récolter les images de Flickr pour la reconstruction 3D

Lors de la conférence Electronic Imaging de 2013 organisée par l’IS&T/SPIE, Steve Seitz qui travaille à l’université de Washington et chez Google a présenté une keynote très intéressante intitulée « a trillion photos ».

Le principe est d’exploiter les millions d’images présentes dans les bases de données telles que Flickr. L’objectif du projet Building Rome in a Day est de récolter un maximum d’image en tapant simplement le mot clé « Rome » ou « Venise » dans Flickr. Une grande partie des images seront inexploitables car elles ne peuvent pas être mise en correspondance avec d’autres images, par exemple une photo de famille, d’un restaurant, etc. En revanche, les lieux les plus touristiques telles que la place « San Marco » sont prises en photos sous de nombreux angles différents. En utilisant une chaine de traitement classique telles que j’ai utilisé pendant ma thèse (SIFT+FLANN+RANSAC) il est possible de mettre en correspondance les images puis de faire la reconstruction 3D.

Dans cette vidéo de démonstration, les pyramides filiformes représentent les positions estimées de chaque prise de vue. La reconstruction a été faite en utilisant 14 079 photos. La reconstruction de Venise c’est fait en utilisant 250 000 images, 496 cœurs de calcul, 27h sont nécessaires pour la mise en correspondance et 38h pour la reconstruction.

 

 

 

Comprendre comment marchent les sacs de mots visuels

Depuis 10 ans [1], les sacs de mots visuels (aussi appelés bags of visual words, bags of features ou bags of keypoints) sont très largement utilisés dans la communauté de vision par ordinateur pour la classification et la reconnaissance d’image.

Calculer la similarité entre deux images est compliqué car ils y a beaucoup de pixels dans une image. Habituellement, on chercher à extraire des caractéristiques telles que la couleur, la forme ou la texture pour comparer des images. Une difficulté est de calculer des caractéristiques robustes aux rotations, zooms, changements d’illumination, bruit et occlusions. La plupart des techniques nécessitent de segmenter les images avant de décrire les objets à reconnaitre.

Les points d’intérêt tels que SIFT, SURF, etc. résolvent la plupart de ces problèmes : ils sont robuste aux transformations et n’ont pas besoin de segmentation, il est donc très facile de les utiliser. Extraire des points d’intérêt pour comparer des images est une bonne idée. Après l’extraction des points, il y a principalement des options : 1) mettre en correspondance les points d’une image avec les points d’une autre image pour faire la reconstruction de panorama, la reconnaissance et la localisation des objets ou 2) faire une description statistique des images en comptant les différents « genres » de points d’intérêt contenus dans l’image. C’est la technique des sacs de mots visuels (BoVW). Les BoVW sont utilisés pour la classification d’images.

Comment fonctionnent les sacs de mots visuels?

Voici le principe en 4 étapes :

  1. Extraire les points d’intérêt des images avec SURF par exemple.
  2. Créer un dictionnaire visuel  en partitionnant les points d’intérêt. Pour cela on peut utiliser k-means et fixer k entre 200 et 2 000.
  3. Pour une image, il faut vérifier dans quelle partition est chaque point d’intérêt. Un histogramme à 1 000 bins est alors construit, où chaque bin correspond à une partition. La valeur d’un bin est égale au nombre de point d’intérêt de l’image qui sont la partition correspondante.
  4. Chaque image est décrite par un vecteur, la classification peut être faite par un algorithme de classification supervisé tel que les SVM.

bovw

[1] Csurka, G., Dance, C., Fan, L., Willamowski, J., & Bray, C. (2004, May). Visual categorization with bags of keypoints. In Workshop on statistical learning in computer vision, ECCV (Vol. 1, No. 1-22, pp. 1-2).

Combiner le texte et l’image pour améliorer la reconnaissance de documents

Les documents peuvent avoir un contenu très varié : un roman, un article scientifique, une facture, un formulaire, une lettre, un ticket de metro, de restaurant… Ces documents peuvent contenir du texte, des tableaux, des logos, des illustrations, ils peuvent également être tordus, pliés, taché, etc.

La technique la plus classique, et certainement la plus performante, est d’appliquer un OCR (lecture optique de caractères) sur l’image du document pour en extraire le texte, puis de comparer ce texte aux textes d’autres documents pour savoir si deux documents sont similaires.

Cependant, les techniques d’OCR fonctionnent beaucoup moins bien sur les tickets (de métro, restaurants, …) car ils sont petits, l’encre effacé et ils sont parfois tordus ou pliés. Certaine facture peuvent être aussi complexe car le contenu change complétement mais le logo reste similaire. Dans ce cas, les techniques de traitement d’image fonctionnent mieux.

La problématique est alors de trouver un moyen de combiner les techniques basées sur le texte et celles basées sur l’image pour que le document soit bien reconnu dans tout les cas. Cette combinaison est très complexe à faire car on souhaite privilégier le texte de temps en temps et l’image d’autres fois mais on ne sait pas à l’avance quelle techniques va fonctionner. Si on essaye de combiner les caractéristique avant (fusion précoce) de reconnaitre ou après (fusion tardive) les performance sont intermédiaire entre celles que l’on aurait eu en utilisant que le texte ou que l’image.

Combi

L’astuce est d’utiliser une combinaison tardive par apprentissage supervisé. L’apprentissage permet au système de comprendre dans quel cas il doit privilégier l’image et dans quel cas il doit privilégier le texte. Grâce à cette méthode les performances globale de reconnaissance sont améliorés.

Cette méthode à été publié dans la conférence DAS 2014, vous pouvez retrouver l’article sur HAL, le dépot d’article scientifique en ligne.

Présentation oral CIFED 2014

Demain débutera les conférences CORIA (COnférence en Recherche d’Information et Applications) et CIFED (Colloque International Francophone sur l’Écrit et le Document) qui sont cette année organisées simultanément à Nancy.

Cet événement est appelé la Semaine du Document Numérique et de la Recherche d’Information (SDNRI) et rassemble les communautés francophones en recherche d’information et analyse de l’écrit et des documents numérisés.

cifed14

Crédit photo : Muzzamil Luqman

A cette occasion je présenterai mes travaux de recherche que j’effectue à Gestform en tant que responsable R&D, portant sur la combinaison de caractéristiques texte et image pour améliorer les performances de classification. Ces travaux ont été effectués en partenariat avec Nicholas Journet et Jean-Philippe Domenger, tous deux chercheurs au LaBRI (Laboratoire Bordelais de Recherche en Informatique).

Vous pouvez trouver dans le lien qui suit un aperçu de la présentation orale que je vais donner demain après-midi lors de cette conférence :  cifed14Oral

Détection de panneaux de signalisation

La détection de panneau de signalisation peut se faire par différentes approches qui peuvent être combinées. Cette problématique se rapproche fortement de la détection de logo.

De mon point de vue, la méthode la plus simple et la plus générique est d’utiliser les points d’intérêt. Cependant les autres informations telles que la couleur ou la forme des contours peuvent aider à reconnaitre les formes.

Prenons l’exemple de la détection d’un panneau STOP.

stop-sign-modelstop-sign

1. Couleur

Une première étape (optionnelle) consiste à filtrer les pixels rouge de l’image. Pour faire cela on utilise l’espace de couleur HSV. La valeur H (teinte ou « hue ») contient essentiellement l’information de couleur, il faut donc faire un filtre passe bande en coupant au bonnes valeurs pour laisser passer uniquement la teinte rouge. Il faudra également filtrer S (saturation), en effet toutes les valeurs de moins de 10 se rapportent généralement au blanc.

      private static Image<Gray, Byte> GetRedPixelMask(Image<Bgr, byte> image)
      {
         using (Image<Hsv, Byte> hsv = image.Convert<Hsv, Byte>())
         {
            Image<Gray, Byte>[] channels = hsv.Split();

            try
            {
               //channels[0] is the mask for hue less than 20 or larger than 160
               CvInvoke.cvInRangeS(channels[0], new MCvScalar(20), new MCvScalar(160), channels[0]);
               channels[0]._Not();

               //channels[1] is the mask for satuation of at least 10, this is mainly used to filter out white pixels
               channels[1]._ThresholdBinary(new Gray(10), new Gray(255.0));

               CvInvoke.cvAnd(channels[0], channels[1], channels[0], IntPtr.Zero);
            }
            finally
            {
               channels[1].Dispose();
               channels[2].Dispose();
            }
            return channels[0];
         }
      }

2. Forme

Une seconde étape (optionnelle aussi) consiste à détecter les contours des objets présents dans l’image puis à comparer ces contours avec ceux de l’image modèle.

Dans la fonction suivante, on applique un filtre Gaussien, on filtre les pixels rouges, on fait une fermeture (dilatation + erosion), puis Canny. Tout les contours extraits sont passés à une autre fonction qui va les examiner.

      public void DetectStopSign(Image<Bgr, byte> img, List<Image<Gray, Byte>> stopSignList, List boxList)
      {
         Image<Bgr, Byte> smoothImg = img.SmoothGaussian(5, 5, 1.5, 1.5);
         Image<Gray, Byte> smoothedRedMask = GetRedPixelMask(smoothImg);

         //Use Dilate followed by Erode to eliminate small gaps in some countour.
         smoothedRedMask._Dilate(1);
         smoothedRedMask._Erode(1);

         using (Image<Gray, Byte> canny = smoothedRedMask.Canny(100, 50))
         using (MemStorage stor = new MemStorage())
         {
            Contour contours = canny.FindContours(
               Emgu.CV.CvEnum.CHAIN_APPROX_METHOD.CV_CHAIN_APPROX_SIMPLE,
               Emgu.CV.CvEnum.RETR_TYPE.CV_RETR_TREE,
               stor);
            FindStopSign(img, stopSignList, boxList, contours);
         }
      }

La fonction suivante passe en revu tout les contours. La première étape consiste à polygonaliser le contour, cela permet de le simplifier en filtrant ces imperfections. Ensuite, si les contours sont trop petits, on les ignore. On essaie de matcher le contours avec une forme octogonale, le matching est fait avec les moments de Hu et donne en sortie une valeur. Plus cette valeur est proche de 0, plus cela veux dire que les formes sont similaire. Si la valeur est supérieur à 0.1 on considère que les formes sont trop différentes pour pouvoir être semblables. Si la valeur est inférieur à 0.1 alors on extrait l’image correspondant à la boite englobante du contour pour ensuite extraire les points d’intérêts.

 

private void FindStopSign(Image<Bgr, byte> img, List<Image<Gray, Byte>> stopSignList, List boxList, Contour contours)
      {
         for (; contours != null; contours = contours.HNext)
         {
            contours.ApproxPoly(contours.Perimeter * 0.02, 0, contours.Storage);
            if (contours.Area > 200)
            {
               double ratio = CvInvoke.cvMatchShapes(_octagon, contours, Emgu.CV.CvEnum.CONTOURS_MATCH_TYPE.CV_CONTOURS_MATCH_I3, 0);

               if (ratio > 0.1) //not a good match of contour shape
               {
                  Contour child = contours.VNext;
                  if (child != null)
                     FindStopSign(img, stopSignList, boxList, child);
                  continue;
               }

               Rectangle box = contours.BoundingRectangle;

               Image<Gray, Byte> candidate;
               using (Image<Bgr, Byte> tmp = img.Copy(box))
                  candidate = tmp.Convert<Gray, byte>();

               //set the value of pixels not in the contour region to zero
               using (Image<Gray, Byte> mask = new Image<Gray, byte>(box.Size))
               {
                  mask.Draw(contours, new Gray(255), new Gray(255), 0, -1, new Point(-box.X, -box.Y));

                  double mean = CvInvoke.cvAvg(candidate, mask).v0;
                  candidate._ThresholdBinary(new Gray(mean), new Gray(255.0));
                  candidate._Not();
                  mask._Not();
                  candidate.SetValue(0, mask);
               }

               ImageFeature[] features = _detector.DetectFeatures(candidate, null);

               Features2DTracker.MatchedImageFeature[] matchedFeatures = _tracker.MatchFeature(features, 2);

               int goodMatchCount = 0;
               foreach (Features2DTracker.MatchedImageFeature ms in matchedFeatures)
                  if (ms.SimilarFeatures[0].Distance < 0.5) goodMatchCount++;  
              if (goodMatchCount >= 10)
               {
                  boxList.Add(box);
                  stopSignList.Add(candidate);
               }
            }
         }
      }

3. Points d’intérêt

Les points d’intérêts sont préalablement extrait de l’image modèle du panneau stop :

      public StopSignDetector(Image<Bgr, Byte> stopSignModel)
      {
         _detector = new SURFDetector(500, false);
         using (Image<Gray, Byte> redMask = GetRedPixelMask(stopSignModel))
         {
            _tracker = new Features2DTracker(_detector.DetectFeatures(redMask, null));  
         }
         _octagonStorage = new MemStorage();
         _octagon = new Contour(_octagonStorage);
         _octagon.PushMulti(new Point[] { 
            new Point(1, 0),
            new Point(2, 0),
            new Point(3, 1),
            new Point(3, 2),
            new Point(2, 3),
            new Point(1, 3),
            new Point(0, 2),
            new Point(0, 1)},
            Emgu.CV.CvEnum.BACK_OR_FRONT.FRONT);
      }

Il sont ensuite comparé au points d’intérêt extraits sur l’image testée, après le test de couleur et de forme (qui sont optionnels)  :

 

ImageFeature[] features = _detector.DetectFeatures(candidate, null);

               Features2DTracker.MatchedImageFeature[] matchedFeatures = _tracker.MatchFeature(features, 2);

               int goodMatchCount = 0;
               foreach (Features2DTracker.MatchedImageFeature ms in matchedFeatures)
                  if (ms.SimilarFeatures[0].Distance < 0.5) goodMatchCount++;                if (goodMatchCount >= 10)
               {
                  boxList.Add(box);
                  stopSignList.Add(candidate);
               }

C’est la fonction MatchFeature qui permet de faire le matching entre deux ensembles de points d’intérêt. La fonction renvoi un tableau de matchedFeatures, contenant les points matchés. Tout les points matchés ne sont pas forcément bon, il faut donc faire un dernier filtre testant la distance entre un point et son matching. Si la distance est suffisament basse, alors le matching est considéré comme bon. Si plus de 10 bon matching sont obtenus alors on considère que le panneau a été reconnu.

 

Pour plus d’information sur l’extraction des points d’intérêt je conseille la lecture d’articles discutant de SIFT ou SURF, pour la mise en correspondance FLANN. Il faut également lire la documentation d’OpenCV.

Le code source et les images de ce billet sont extraits des exemples de codes donnés par EMGU CV.