Find dato un insieme di punti

Question

Dato un elenco di coordinate x, y ed una larghezza nota & altezza come può NUMERO delle zone delimitate determinata (in C#)?

Per esempio:

In questa immagine 5 ZONE ALLEGATI sono definite:

1. facciale (1)
2. Occhi (2)
3. Nose (1)
4. destro del volto (1)

L'elenco delle x, y punti sarebbe qualsiasi pixel di colore nero, compresa la bocca.

Answer 1

È possibile utilizzare questo semplice algoritmo, basato su un'idea di Riempi con bitmap aiutante:

// backColor is an INT representation of color at fillPoint in the beginning. 
// result in pixels of enclosed shape. 
private int GetFillSize(Bitmap b, Point fillPoint) 
{ 
    int count = 0; 
    Point p; 
    Stack pixels = new Stack(); 
    var backColor = b.GetPixel(fillPoint.X, fillPoint.Y); 
    pixels.Push(fillPoint); 
    while (pixels.Count != 0) 
    { 
     count++; 

     p = (Point)pixels.Pop(); 
     b.SetPixel(p.X, p.Y, backColor); 

     if (b.GetPixel(p.X - 1, p.Y).ToArgb() == backColor) 
      pixels.Push(new Point(p.X - 1, p.Y)); 

     if (b.GetPixel(p.X, p.Y - 1).ToArgb() == backColor) 
      pixels.Push(new Point(p.X, p.Y - 1)); 

     if (b.GetPixel(p.X + 1, p.Y).ToArgb() == backColor) 
      pixels.Push(new Point(p.X + 1, p.Y)); 

     if (b.GetPixel(p.X, p.Y + 1).ToArgb() == backColor) 
      pixels.Push(new Point(p.X, p.Y + 1)); 
    } 

    return count; 
} 

UPDATE

Il codice di cui sopra funziona solo queste aree chiuse quadruply collegate. Il seguente codice funziona con aree racchiuse con link ottuplicati.

// offset points initialization. 
Point[] Offsets = new Point[] 
{ 
    new Point(-1, -1), 
    new Point(-0, -1), 
    new Point(+1, -1), 
    new Point(+1, -0), 
    new Point(+1, +1), 
    new Point(+0, +1), 
    new Point(-1, +1), 
    new Point(-1, +0), 
}; 

... 

private int Fill(Bitmap b, Point fillPoint) 
{ 
    int count = 0; 
    Point p; 
    Stack<Point> pixels = new Stack<Point>(); 
    var backColor = b.GetPixel(fillPoint.X, fillPoint.Y).ToArgb(); 
    pixels.Push(fillPoint); 
    while (pixels.Count != 0) 
    { 
     count++; 

     p = (Point)pixels.Pop(); 
     b.SetPixel(p.X, p.Y, Color.FromArgb(backColor)); 

     foreach (var offset in Offsets) 
      if (b.GetPixel(p.X + offset.X, p.Y + offset.Y).ToArgb() == backColor) 
       pixels.Push(new Point(p.X + offset.X, p.Y + offset.Y)); 
    } 

    return count; 
} 

L'immagine in basso dimostra chiaramente cosa intendo. Inoltre è possibile aggiungere più punti lontani all'array offset per poter riempire le aree con spazi vuoti.

Answer 2

Ci sono alcuni casi speciali nell'immagine di esempio. Dovresti decidere come affrontarli.

In genere si inizia convertendo l'immagine raster in una serie di poligoni. Quindi è abbastanza banale calcolare l'area (vedi commento di Servy)

I casi speciali sarebbero il lato del viso e della bocca. Entrambe sono forme aperte, non chiuse. Devi capire come chiuderli.

Answer 3

Ho avuto un grande successo con OpenCV. C'è una biblioteca per NET chiamato Emgu CV

Qui è una domanda che copre alternative per Emgu CV: .Net (dotNet) wrappers for OpenCV?

Quella libreria contiene funzioni per identificare i contorni e la ricerca di proprietà su di loro. Puoi cercare cvContourArea per trovare maggiori informazioni.

Se stai cercando una soluzione rapida a questo specifico problema e vuoi scrivere il tuo codice piuttosto che riusare gli altri, non ho un algoritmo che potrei dare che lo faccia. Scusate.

Answer 4

Penso che si riduca a contare il numero di pixel (non neri) in ciascuna regione. Se scegli un pixel che non è nero, aggiungilo a HashSet<>, verifica se i pixel sopra, sotto, a sinistra ea destra del pixel scelto, sono anch'essi non neri.

Ogni volta che trovi nuovi pixel non neri (andando su/giù/sinistra/destra), aggiungili al tuo set. Quando li hai trovati tutti, contali.

L'area della tua regione è count/(pixelWidthOfTotalDrawing * pixelHeightOfTotalDrawing) moltiplicata per l'area del rettangolo completo (a seconda delle unità che desideri).

Commento: non penso che questo sia un poligono. Ecco perché avevo in mente la funzione "riempire con la vernice" del semplice software di disegno.