Regionen erkennen aus einer Matrix

[Peter666]

Hi,

ich hab hier eine Aufgabe über der ich schon seit einiger Zeit grübele:

Als Vorgabe besitze ich eine eindimensionale Matrix (bestehend aus Breite*Höhe):

Map: array[0..256 * 256 - 1] of Boolean;

Die Aufgabe ist nun sämtliche gesetzte Punkte zu zählen und Regionen zuzuordnen. Mein Grundgerüst schaut wie folgt aus:

Code:

procedure FindRegions(const Width, Height: Integer; const Map: array of Boolean; var Regions: array of Integer);
var tmp: integer;
  i, j: integer;
  x, y: integer;
begin
  // Regionen löschen
  Fillchar(Regions, sizeof(regions), 0);

  for y := 0 to Height - 1 do
    for x := 0 to Width - 1 do
    begin
     
    end;

  // Bubblesort von Groß, zu Klein
  for i := 0 to high(regions) - 2 do
    for j := 0 to high(regions) - 2 do
      if (i <> j) and (regions[i] > regions[j]) then
      begin
        tmp := regions[i];
        regions[i] := regions[j];
        regions[j] := tmp;
      end;
end;

Als Ausgabe sollte eine Integer Liste mit der Pixelanzahl der jeweiligen Regionen sein. Meine Idee ist anstelle des Map: array[0..256 * 256 - 1] of Boolean;
ein Map: array[0..256 * 256 - 1] of Integer; zu machen, dem bei der Initialisierung eine fortlaufende Nummer zu geben - der Einfachheit der Offset und die Punkte drumherum zu zählen und ggf. zusammenzuführen, also Punkt links, Punkt Oben, Punkt rechts <> 0, dann setze alle Punkte auf den Wert des ersten Punktes.
Das ganze hat aber Macken, weiß jemand von euch eventuell Rat?

Peter

[Aphton]

Was ist eine "Region"?
Edit: Ist es eine Menge von Punkten, die sich benachbarn?

[Peter666]

Genau alle Punkte die benachbart sind, sollten in eine Region zusammengefasst werden. Ich brauche allerdings nur eine Liste mit wie viele Punkte pro Region zu finden sind.

Peter

[jfheins]

Das grundsätzliche Vorgehen das ich wählen würde sieht so aus:

Wenn du nicht nur die Anzahl der Regionen nund deren Felder haben willst, sondern auch die Zuordnung Punkt => Region dann musst du eine Integer-Array hernehmen. Ich definiere mir jetzt mal folgende Werte:
-1 : Zu zählender Punkt
-2 : Zu ignorierender Punkt
>=0: Punkt gehört zu der Region mit dem Index

Zuerst: Schreib eine rekursive Funktion, die dir die umliegenden Felder abklappert und zu einer Region verbindet. Klingt kompliziert, ist es aber nicht.
Dann: Alle Felder durchgehen und für jedes Feld die Funktion aufrufen.

Zu Punkt 1:

Delphi-Quellcode:

function MakeRegions(const Map: Array of Integer; index, regionindex, width: Integer): Integer;
Result := 0;
if (index >= 0) and (index < length(Map)) then
if Map[index] == -1 then
begin
  Map[index] = regionindex;
  Result := 1;

  Result += MakeRegions(Map, index + 1, regionindex, width);
  Result += MakeRegions(Map, index - 1, regionindex, width);
  Result += MakeRegions(Map, index + width, regionindex, width);
  Result += MakeRegions(Map, index - width, regionindex, width);
end;

Sowas in der Richtung. Ist jetzt ein wenig gemischter Code aber der Gedanke soll klar werden.

Aufruf dann für jeden Punkt:

Delphi-Quellcode:

  for o := 0 to length(Map) - 1 do
    begin
     MakeRegions(Map, i, i, width);
    end;

Falls der Rückgabewert > 0 ist, wurde eine neue Region gefunden, mit der angegebenen Zahl von Feldern.
Das Array sollte nur mit -1 und -2 initialisiert sein. Danach kannst du anhand des Werts im Array die Region ablesen, zu der der Punkt gehört.

[Aphton]

Wie sieht die Region aus? Muss sie rechteckig, quadratisch und noch wichtiger - müssen alle gleich sein (breite, höhe)?
Falls nicht, dann würde ich dir ein Quadtree vorschlagen, bei der du dann versuchen solltest, die Regionen durch das umgebende Quad zu bestimmen.

MfG

[Peter666]

Die ist nicht rechteckig.

@jfheins: So ähnlich hab ich mir das auch schon gedacht - ich probier das mal. Hmm das geht glaub ich nicht wirklich, denn bei nem Array aus 100 Feldern dauert das ja schon knapp ne Minute.

Peter

[BoolString]

Möglicherweise meinst du eine Implementation des Hoshen-Kopelman Algorithmus? Das ist ein recht komplexes Forschungsfeld; zumindest sobald es darum geht mehr als ein paar einzelne Pixel auf einer binären Maske zu erkennen.

Ich finde hier allerdings meine Delphi-Implementierung nicht mehr. Aber es ist nicht endlos kompliziert (Englisch vorausgesetzt). Man kann das wohl in ein-zwei Nachmittagen schaffen...

Hintergrundinformationen zum Hoshen-Kopelman Algorithmus.
Ein Vortrag zur Problematik der 'Musterfindung'.
Der Original-Artikel von Hoshen über den verbesserten Algorithmus von 1997.


Beste Grüße

Jan

[jfheins]

Zitat von Peter666:

Die ist nicht rechteckig.

@jfheins: So ähnlich hab ich mir das auch schon gedacht - ich probier das mal. Hmm das geht glaub ich nicht wirklich, denn bei nem Array aus 100 Feldern dauert das ja schon knapp ne Minute.

Peter

Da sollte noch was rauszuholen sein. Wichtig ist, dass das Array nicht ständig umherkopiert wird, also entweder nen Pointer übergeben oder das Array global machen.
Außerdem kannst du den letzten rekursiven Aufruf weglassen, wenn du immer von niedrigen zu hohen indexen iterierst.

[Peter666]

Genial, danke der Algorithmus scheint das wohl lösen zu können

[Medium]

Irgendwie erinnert mich das Problem an FloodFilling, nur dass man sich wegschreiben muss, welche Idizes man denn "gefüllt" hat.