AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Regionen erkennen aus einer Matrix

Ein Thema von Peter666 · begonnen am 9. Jan 2011 · letzter Beitrag vom 9. Jan 2011
Antwort Antwort
Seite 1 von 2  1 2      
Peter666

Registriert seit: 11. Aug 2007
357 Beiträge
 
#1

Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 13:03
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
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#2

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 13:18
Was ist eine "Region"?
Edit: Ist es eine Menge von Punkten, die sich benachbarn?
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Peter666

Registriert seit: 11. Aug 2007
357 Beiträge
 
#3

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 13:34
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
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#4

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 14:03
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.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#5

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 14:35
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
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Peter666

Registriert seit: 11. Aug 2007
357 Beiträge
 
#6

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 14:42
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

Geändert von Peter666 ( 9. Jan 2011 um 14:47 Uhr)
  Mit Zitat antworten Zitat
BoolString

Registriert seit: 2. Feb 2009
Ort: Varel
70 Beiträge
 
RAD-Studio 2009 Pro
 
#7

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 15:19
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
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#8

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 15:35
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.
  Mit Zitat antworten Zitat
Peter666

Registriert seit: 11. Aug 2007
357 Beiträge
 
#9

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 16:54
Genial, danke der Algorithmus scheint das wohl lösen zu können
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.685 Beiträge
 
Delphi 2007 Enterprise
 
#10

AW: Regionen erkennen aus einer Matrix

  Alt 9. Jan 2011, 17:21
Irgendwie erinnert mich das Problem an FloodFilling, nur dass man sich wegschreiben muss, welche Idizes man denn "gefüllt" hat.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:20 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz