Zusammenhängende Pixel finden



  • Hi!

    Ich programmiere z.T. in einer C Angelehnte Scriptsprache(C4Script) und möchte
    die Fläche eines Sees in einer Pixellandschaft bestimmen. Erklärung zum verlinkten Bild: Weis=Himmel, RotBraun=Erde, Blau=Wasser, Schwarzes Kreuz Startpunkt des Algorithmus. Ich hab schon geschaut was man da machen könnte wie Z.B. Floodfill, aber bin auf das Problem gestoßen, dass ich keine komplexeren Datenstrukturen(wie den Stack) zur verfügung habe. Das höchste der Gefühle ist ein Array. Ausserdem müsste ich beim Floodfill die Pixel markieren, was auch nicht so einfach ginge. Mir geht es nur um die Größe der Fläche, aller anderen Informationen können verworfen werden. Gibt es da einen Algorithmus der das hinbekommt?



  • Wie eine Ameise am Rand entlanglaufen und die Fläche dabei integrieren.


  • Mod

    Kann der See Inseln haben? Kann es mehrere Seen geben? Falls ja: Zählen diese mit dazu oder einzeln?

    Wenn es nur einen See gibt oder alle Seen zusammen zählen, geht die Brute-Force-Methode, das gesamte Bild abzulaufen und die blauen Punkte zu zählen.

    Wenn du ein Array hast, dann kannst du da drin auch sämtlichen komplexen Datenstrukturen selber simulieren. Dieses Array ist dann eben dein "Hauptspeicher" und Indizes im Array sind deine Pointer. Ein Stack ist sogar relativ einfach.

    PS: Ich glaube, du hast da etwas ganz furchtbar missverstanden. Einen Stack zu haben bedeutet nicht, dass du wirklich einen Datentyp "stack" von der Programmiersprache angeboten bekommen musst. Die meisten Programmiersprachen haben ihren eigenen, versteckten Stack. Bei jedem Funktionsaufruf werden da die lokalen Variablen drauf gelegt und hinterher wieder abgeräumt. Das kann, wenn ich das richtig sehe, auch C4Script. Wäre auch ziemlich nutzlos, eine Sprache ohne Funktionsaufrufe zu haben. Du implementierst den Flood Fill Algorithmus nicht mit einem expliziten Stack, sondern du programmierst einfach eine rekursive Funktion und lässt die Sprache für dich arbeiten. Du nimmst einfach das erste Beispiel aus der (englischen) Wikipedia und übersetzt das Zeile für Zeile nach C und du bist fertig.

    Du musst natürlich immer noch deine bereits gezählten Pixel irgendwie markieren. Sei es im Original oder in einem neuen Feld. Da wirst du schwerlich drum herum kommen, außer mit Verfahren, wie sie im vorherigen Threadverlauf vorgeschlagen wurden.


  • Mod

    Hier ein ganz einfache Flood-Fill, nur mit Rekursion, das Programm selbst organisiert den Stack, einfach durch den Mechanismus des Funktionsaufrufs. Die Funktion selber hat nur ihre Parameter (ganz schön viele, da ich allgemein bleiben wollte, aber gleichzeitig keine structs einsetzen wollte) und einen Zeiger und einen unsigned int (die man beide wegoptimieren könnte, sie dienen nur der Übersicht) als lokale Variablen.

    Das Original wird hier leider verändert. Ein zerstörungsfreies Flood-Fill müsste sich ein Merkerfeld anlegen, wo es schon überall war. Wozu im allgemeinen Fall aber ein malloc nötig wäre und ich vermute mal, das geht über die zur Verfügung stehenden Mittel hinaus.

    #include <stdio.h>
    
    unsigned int count_pixels(unsigned char *image, 
                              int size_x, int size_y,
                              int start_x, int start_y, 
                              unsigned char target_color, unsigned char replacement_color)
    {
      unsigned char * color;
      unsigned count;
    
      if (start_x < 0 || start_x >= size_x || start_y < 0 || start_y >= size_y)
        return 0;
    
      color = image + start_x * size_x + start_y;
    
      if(*color == replacement_color) return 0;
      if(*color != target_color) return 0;
    
      *color = replacement_color;
      count = 1;
    
      count += count_pixels(image,
                            size_x, size_y,
                            start_x + 1, start_y,
                            target_color, replacement_color);
      count += count_pixels(image,
                            size_x, size_y,
                            start_x, start_y + 1,
                            target_color, replacement_color);
      count += count_pixels(image,
                            size_x, size_y,
                            start_x - 1, start_y,
                            target_color, replacement_color);
      count += count_pixels(image,
                            size_x, size_y,
                            start_x, start_y - 1,
                            target_color, replacement_color);
    
      return count;
    }
    
    int main()
    {
      unsigned char image[10][10] = 
        {{'X', 'X', 'X', 'X', 'O', 'O', 'X', 'X', 'X', 'X'},
         {'X', 'X', 'X', 'X', 'O', 'O', 'X', 'X', 'X', 'X'},
         {'X', 'X', 'X', 'X', 'O', 'O', 'X', 'X', 'X', 'X'},
         {'X', 'X', 'X', 'O', 'O', 'O', 'X', 'X', 'X', 'O'},
         {'X', 'X', 'X', 'O', 'O', 'X', 'X', 'O', 'O', 'X'},
         {'X', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'X', 'X'},
         {'X', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'X', 'X'},
         {'X', 'X', 'X', 'X', 'X', 'X', 'O', 'X', 'X', 'X'},
         {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
         {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}};
    
      unsigned count1 =  count_pixels
        (image[0], 
         sizeof(image) / sizeof(*image), sizeof(*image) / sizeof(**image),
         2, 4,
         'O', 'o');
    
      unsigned count2 =  count_pixels
        (image[0], 
         sizeof(image) / sizeof(*image), sizeof(*image) / sizeof(**image),
         4, 7,
         'O', 'o');
    
      printf("Count of 4-connected 'O's at (2,4): %d\n", count1);
      printf("Count of 4-connected 'O's at (4,7): %d\n", count2);
      return 0;
    }
    


  • Hi und Danke erstmal für die Vorschläge.
    Ich habe es jetzt so Implementiert, weil die Rekursion zum overflow führt.
    Ich habe jetzt noch ein Problem, der Algorithmus funktioniert nicht für Gerade Zahlen für den Parameter MaxWidth. MaxWidth gibt die Quadratgröße an in dem gesucht wird(ich will nicht die ganze Karte absuchen sondern nur lokal). Und die laufzeit hat mich überrascht 33 "Pops" für ein 3x3 Quadrat... optimierungsvorschläge?

    //Stack für Flächenberechnung(Floodfill algorithmus)
    local StackX;
    local StackY;
    local StackItemCount;
    local TotalPops;
    
    private func Pop(&x, &y) {
      if(StackItemCount==0) {
        x=-1; y=-1; return false;
      }
      Log("Pop:(%d, %d)", x, y);
      StackItemCount--;
      TotalPops++;
      x=StackX[StackItemCount];
      y=StackY[StackItemCount];
      return true;
    }
    
    private func Push(int x, int y) {
      Log("Push:(%d, %d)", x, y);
      var len=GetLength(StackX);
      if(len==0) {
        StackX=CreateArray(500);
        StackY=CreateArray(500);
      } else if(len<=StackItemCount) {
        SetLength (StackX, len+500);
        SetLength (StackY, len+500);
      }
      StackX[StackItemCount]=x;
      StackY[StackItemCount]=y;
      StackItemCount++;
    }
    
    //Liefert die Anzahl Flüssigkeitspixel innerhalb einer zusammenhängenden Flüssigkeitsfläche
    //CreateObject(PRES)
    //Object(104)->GetLiquidArea(1850, 73, 50)
    func GetLiquidArea(int xAbsolut, int yAbsolut, int MaxWidth) {
      var Area=1;
      if(MaxWidth%2==0) MaxWidth++;//Notlösung
      MaxWidth+=2;  //Rand hinzufügen
      var FloodFillSearchArea=CreateArray(MaxWidth*MaxWidth);
      //Rand des Suchbereichs als besucht makieren
      for(var i=0; i<MaxWidth+2; i++) {
        FloodFillSearchArea[i]=true;  //Oberer Rand
        FloodFillSearchArea[MaxWidth*i]=true;  //Linker Rand
        FloodFillSearchArea[MaxWidth*(MaxWidth-1)+i]=true;  //Unterer Rand
        FloodFillSearchArea[MaxWidth*i+(MaxWidth-1)]=true;  //Rechter Rand
      }
      var CenterX=xAbsolut;
      var CenterY=yAbsolut;
      Push(xAbsolut, yAbsolut);
      TotalPops=0;
      while(Pop(xAbsolut, yAbsolut)) {
        var Idx=(xAbsolut-CenterX)+(yAbsolut-CenterY)*MaxWidth + (MaxWidth*MaxWidth)/2;
        Log("Index=(%d-%d)+(%d-%d)*%d + (%d*%d)/2=%d", xAbsolut, CenterX, yAbsolut, CenterY, MaxWidth, MaxWidth, MaxWidth, Idx);
        Log("Liq(%d, %d)=%d, Array[i]=%d", xAbsolut-GetX(), yAbsolut-GetY(), GBackLiquid(xAbsolut-GetX(), yAbsolut-GetY()), FloodFillSearchArea[Idx]);
        if (GBackLiquid(xAbsolut-GetX(), yAbsolut-GetY()) && !FloodFillSearchArea[Idx]) {
          FloodFillSearchArea[Idx]=true;
          Push(xAbsolut-1, yAbsolut  );
          Push(xAbsolut+1, yAbsolut  );
          Push(xAbsolut  , yAbsolut-1);
          Push(xAbsolut  , yAbsolut+1);
          Area++;
        }
      }
      Log("Total Pops=%d", TotalPops);
      return Area;
    }
    

  • Mod

    😕 Wie kann die Rekursion überlaufen, aber ein äquivalenter, selbstgebauter Stack funktionieren? Dein Stack liegt doch auch nur auf dem Stack. edit: Ok wahrscheinlich ist "createArray" so etwas wie malloc in C. Dann liegt dein Stack nicht auf dem Stack 🙂 . Aber es heißt auch, dass die Prämisse, dass du keine komplexen Datenstrukturen zur Verfügung hättest, falsch war. Du hast doch alles, was es in C gibt und man braucht sich nicht zurück zu halten. Man kann doch sogar das Problem mit dem Markieren umgehen, wenn das denn wirklich ein Problem sein sollte. Ende edit.

    Du kannst natürlich in meinem Beispiel die Anzahl der lokalen Variablen massiv senken, wenn dein Compiler nicht dazu in der Lage ist:
    image: Bleibt immer gleich. Kann von einer Wrapperfunktion einmal global gesetzt werden, dann geht es in die eigentliche Rekursion.
    size_x und size_y: Siehe image
    target_color und replacement_color: Siehe image
    color: Dient nur zur Hilfe, damit man nicht jedes Mal den langen Ausdruck schreiben braucht. Einfach den Ausdruck überall explizit benutzen, wo nun color steht
    count: Kann ebenfalls komplett eliminiert werden, beispielsweise als globale Variable.

    Bleiben also nur start_x und start_y als Variablen, die man wirklich braucht. Also genau die beiden, die du derzeit bei deinem handgestricktem Stack hast.

    Deinen Code kann ich nicht nachvollziehen, es fängt gleich rätselhaft an, wie du den Rand markierst. Meiner Meinung nach sind deine Berechnungen, wo der Rand ist, falsch. Hast du mal deine Zwischenergebnisse geprüft?


Anmelden zum Antworten