Comment déterminer les bords d'une image de manière optimale?

Question

J'ai récemment été confronté au problème du recadrage et du redimensionnement des images. Je devais recadrer le « contenu principal » d'une image par exemple si j'avais une image semblable à ceci: alt text http://blstb.msn.com/i/8C/10F73EB7EE231B1EA8E65EFA7D69B.jpg

le résultat devrait être une image avec le contenu msn sans les marges blanches (gauche & droite).

Je recherche la même chose sur l'axe X pour le premier et le dernier changement de couleur et sur l'axe Y. Le problème est que traverser l'image ligne par ligne prend un certain temps ... pour une image qui est 2000x1600px cela prend jusqu'à 2 secondes pour retourner les données CropRect => x1, y1, x2, y2.

J'ai essayé de faire pour chaque coordonnée une traversée et un arrêt sur la première valeur trouvée mais cela n'a pas fonctionné dans tous les cas de test ... parfois les données retournées n'étaient pas celles attendues et la durée des opérations était similaire

Une idée de comment réduire le temps de traversée et la découverte du rectangle autour du 'contenu principal'?

public static CropRect EdgeDetection(Bitmap Image, float Threshold) 
     { 
      CropRect cropRectangle = new CropRect(); 
      int lowestX = 0; 
      int lowestY = 0; 
      int largestX = 0; 
      int largestY = 0; 

      lowestX = Image.Width; 
      lowestY = Image.Height; 

      //find the lowest X bound; 
      for (int y = 0; y < Image.Height - 1; ++y) 
      { 
       for (int x = 0; x < Image.Width - 1; ++x) 
       { 
        Color currentColor = Image.GetPixel(x, y); 
        Color tempXcolor = Image.GetPixel(x + 1, y); 
        Color tempYColor = Image.GetPixel(x, y + 1); 
        if ((Math.Sqrt(((currentColor.R - tempXcolor.R) * (currentColor.R - tempXcolor.R)) + 
         ((currentColor.G - tempXcolor.G) * (currentColor.G - tempXcolor.G)) + 
         ((currentColor.B - tempXcolor.B) * (currentColor.B - tempXcolor.B))) > Threshold)) 
        { 
         if (lowestX > x) 
          lowestX = x; 

         if (largestX < x) 
          largestX = x; 
        } 

        if ((Math.Sqrt(((currentColor.R - tempYColor.R) * (currentColor.R - tempYColor.R)) + 
         ((currentColor.G - tempYColor.G) * (currentColor.G - tempYColor.G)) + 
         ((currentColor.B - tempYColor.B) * (currentColor.B - tempYColor.B))) > Threshold)) 
        { 
         if (lowestY > y) 
          lowestY = y; 

         if (largestY < y) 
          largestY = y; 
        } 
       }     
      } 

      if (lowestX < Image.Width/4) 
       cropRectangle.X = lowestX - 3 > 0 ? lowestX - 3 : 0; 
      else 
       cropRectangle.X = 0; 

      if (lowestY < Image.Height/4) 
       cropRectangle.Y = lowestY - 3 > 0 ? lowestY - 3 : 0; 
      else 
       cropRectangle.Y = 0; 

      cropRectangle.Width = largestX - lowestX + 8 > Image.Width ? Image.Width : largestX - lowestX + 8; 
      cropRectangle.Height = largestY + 8 > Image.Height ? Image.Height - lowestY : largestY - lowestY + 8; 
      return cropRectangle; 
     } 
    } 

Answer 1

Une optimisation possible consiste à utiliser Lockbits pour accéder aux valeurs de couleur directement plutôt que via le GetPixel beaucoup plus lent.

Si vous recherchez des Lockbits, le premier hit est http://www.bobpowell.net/lockingbits.htm. C'est une bonne référence. D'autre part, mon test a montré que la surcharge associée à Lockbits rend cette approche plus lente si vous essayez d'écrire un GetPixelFast équivalent à GetPixel et le déposer en remplacement. Au lieu de cela, vous devez vous assurer que tout l'accès aux pixels est fait en un seul coup plutôt que plusieurs coups. Cela devrait correspondre à votre code à condition de ne pas verrouiller/déverrouiller sur chaque pixel.

Voici un exemple

BitmapData bmd = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, b.PixelFormat); 

byte* row = (byte*)bmd.Scan0 + (y * bmd.Stride); 

//       Blue     Green     Red 
Color c = Color.FromArgb(row[x * pixelSize + 2], row[x * pixelSize + 1], row[x * pixelSize]); 

b.UnlockBits(bmd); 

Deux choses à noter:

1. Ce code est dangereux car il utilise des pointeurs
2. Cette approche dépend de la taille de pixel dans les données bitmap, de sorte que vous aura besoin de dériver pixelSize de bitmap.PixelFormat

Answer 2

Cela ne fera pas mieux de l'ordre ... mais si vous conciliez votre seuil, vous ne serez pas besoin de faire une racine carrée, ce qui est très cher.

Cela devrait donner une augmentation significative de la vitesse.

Answer 3

GetPixel est probablement votre principal coupable (je vous recommande d'utiliser des tests de profilage pour le suivre vers le bas), mais vous pouvez restructurer l'algorithme comme celui-ci:

1. première ligne de balayage (y = 0) de gauche à droite et de droite-to gauche et enregistrer le premier et le dernier emplacement de bord. Il n'est pas nécessaire de vérifier tous les pixels, comme vous voulez les bords extrêmes.
2. Balayez toutes les lignes suivantes, mais maintenant nous avons seulement besoin de rechercher vers l'extérieur (du centre vers les bords), en commençant à notre dernier bord minimum connu. Nous voulons trouver les limites extrêmes, donc nous avons seulement besoin de chercher dans la région où nous pourrions trouver de nouveaux extrema.
3. Répétez les deux premières étapes pour les colonnes, en établissant des extrema initiaux, puis en utilisant ces extrema pour lier de façon itérative la recherche.

Cela devrait considérablement réduire le nombre de comparaisons si vos images sont généralement principalement du contenu. Le pire des cas est une image complètement vide, pour laquelle cela serait probablement moins efficace que la recherche exhaustive. Dans les cas extrêmes, le traitement d'image peut également bénéficier du parallélisme (découper l'image et la traiter en plusieurs threads sur une CPU multi-cœurs), mais cela demande beaucoup de travail supplémentaire et il y a d'autres changements plus simples tu fais encore. L'overhead de thread tend à limiter l'applicabilité de cette technique et est principalement utile si vous comptez exécuter cette chose en 'temps réel', avec un traitement répété dédié des données entrantes (pour compenser les coûts d'installation initiaux).