Konturensuche

[Zakum]

Hallo.

Ich bin gerade auf ein (mMn ) ziemlich hartes Problem gestoßen, und wollte mal schauen, ob vieleicht jemand mir weiterhelfen könnte.

So sieht das Problem aus:

Ich hab ein 256*256 2D Feld, dass mit zahlen befüllt ist. Dabei gibt es mehere "Flecken" (sprich: zusammenhängende Domänen) von Nullen. Und nun möchte ich die Kontur des Flecks mit dem größten Umfang in einem Feld von Koordinaten speichern.

Ich hab ein bisschen hin und her überlegt, aber das einzige was mir eingefallen ist, ist so konfus und programiertechnisch hässlich, dass ichs nur ungern posten würde: Es würde einen haufen Platz einnehmen und nur potenzielle Helfer abschrecken.

Vieleicht hatte ja schonmal jemand ein ähnliches Problem oder kennt gar eine "Musterlösung"? Wobei ich latürnich auch für einzelne Anregungen dankbar bin.

Ciao

Zakum

[baba007]

(a)symmetrisch?

1. idee: Umfang ist abhängig vom Durchmesser, demnach würde ich zuerst nach der längsten kette von nullen suchen, vertikal und horizontal

2. idee: ich suche mir einen punkt aus und schaue obs ne null ist und überprüfe alle himmelsrichtungen nach angrenzenden nullen usw.

3. idee: umfang oder fläche?

[Gooose]

Versuch mal in Pseudocode eine Antwort zu formulieren, dann bist du an einer Lösung schon fast dran.

[flashpixx]

Hallo,

für mich hört sich das Problem nach "Bildverarbeitung" an. Wenn Du Dein 2D Array als Bild auffasst (Bei RGB müsstest Du die Bearbeitung für jede Farbe wiederholen), kannst Du mit Hilfe von Kantendedektion (z.B. Sobel) und einer Hough Transformation das Bild entsprechend bearbeiten. Ein Einstieg findest Du hier http://www-gs.informatik.tu-cottbus.de/~wwwgs/bia_v05.pdf

HTH Phil

[Zakum]

Hallo alle zusammen!

Endlich Männertag: Ich hab Zeit wieder zu posten.

Also natürlich erstmal vielen Dank für die ganzen Idee. Wie richtig erkannt, es handelt sich um Bildverarbeirung. Die pdf schau ich mir gleich mal an.

Babas 2te Idee ist mir zwischendurch auch erschienen, mal sehen wie sich das umsetzen lässt... An sich klingt es aber verdächtig rekursiv.

[Zakum]

Sodele, eine Woche ist rum und "isch hab fertisch".

flashpixx pdf ist seeeeeehr interessant, hätte ich mehr Zeit würd ich mich da auf jeden Fall ransetzen, die mathe ist sehr elegant, aber so muss ich mich mit einfachen Methoden begnügen.

Hab letztendlich babas 2te Idee umgesetzt, so sieht das Ding aus, fals jemand interesiert ist :

void lokalisieren(int x, int y) {

	tmp[count].x=x;		tmp[count].y=y;			//Koordinaten des schwarzen Punktes speichern

	grauwert[x][y]=50;							//schwarzen Punkt löschen, damit nicht doppel gezählt wird ++ Farbänderun, später weg

	++count;

	if (grauwert[x][y+1]==0) lokalisieren(x,y+1);  						

	if (grauwert[x][y-1]==0) lokalisieren(x,y-1); 

	if (grauwert[x-1][y+1]==0) lokalisieren(x-1,y+1);  

	if (grauwert[x-1][y]==0) lokalisieren(x-1,y);  

	if (grauwert[x-1][y-1]==0) lokalisieren(x-1,y-1);  

	if (grauwert[x+1][y+1]==0) lokalisieren(x+1,y+1); 

	if (grauwert[x+1][y]==0) lokalisieren(x+1,y);  

	if (grauwert[x+1][y-1]==0)  lokalisieren(x+1,y-1);  

}

tmp und grauwert sind globale Variablen, ist ja hier schlieslich die Testvariante. Der Aufruf:

	for (y=0;y<256;++y) {								

		for (x=0;x<256;++x) {

			if (grauwert[x][y]==0) {					//Wenn eine Pivot Null gefunden wird: starte lokalisation

				lokalisieren(x,y);

				++fleckenzahl;							//fleckenzahl merken (test)

				tmp[count].x=666;						//Länge wird gespeichert

				if (lang_ziel()<lang_tmp()) {			//sollte der neue Fleck größer sein als der alte

					for (count=0;count<lang_tmp();++count) {//Speichern des größeren Flecks

						ziel[count].x=tmp[count].x;

						ziel[count].y=tmp[count].y;

					}

					ziel[count+1].x=666;				//größe des Ziel speichern

				}

				count=0;

			}

		}

	}

Es ergab sich leider das Problem, dass einzelne "schwarze pixel" eingekesselt wurden, also im Prinzip alles um sie herum gelöscht wurde, so, dass sie ignoriert wurden. Die Rahmenbedingungen sind jedoch so, dass sie im Anschluss an lokalisieren leicht erkannt und beseitigt werden können:

void fuellen(double reproduktion[256][256]){

	int x=0,y=0;

	for (y=1;y<255;++y) {								

		for (x=1;x<255;++x) {

			if ((reproduktion[x][y]!=0)&&((reproduktion[x+1][y]==0)&&(reproduktion[x-1][y]==0))) {

				reproduktion[x][y]=0; //Löcher mit 1px breite gelöscht	

			}				

			if ((reproduktion[x][y]!=0)&&((reproduktion[x][y+1]==0)&&(reproduktion[x][y-1]==0))) {

				reproduktion[x][y]=0;//Löcher mit 1px Höhe gelöscht 	

			}

		}			

	}

}

In dem Sinne also nochmals ein Dankeschön für die Anregungen.