Image => kleinste zusammenhängende Farbkombination (Pixel)

[Goddie]

Servus zusammen,

hätte da mal ein Problem für das ich gerne ein paar Gedankenanstösse hätte.
Danke schon mal im voraus.

Ich habe ein bmp-Bild in ein TImage geladen. Dann habe ich alle Farben bis auf rot und weiss eliminiert bzw. durch diese ersetzt. Es gibt also nur noch diese 2 Farben in oder auf dem Bild. Jetzt möchte ich die kleinste zusammenhängende Pixelkombination der Farbe rot bestimmen und anders einfärben.
Es zählen nur gerade Verbindungen, also nach links bzw. rechts oder oben und unten. Schräge Verbindungen zählen nicht.

Ich hoffe es ist einigermaßen verständlich erklärt...

Hat da jemand eine kleine oder auch große Idee, wie sich dies bewerkstelligen lassen könnte ?

FGGF

Goddie

[Sunday]

wie schaut denn deine idee bisher aus?

[Goddie]

Mmmhhhh, hab mir schon verschiedenes überlegt und wieder verworfen.

Meine letzte Idee wäre, den 1. Pixel, also 0/0 zu nehmen und dann nach rechts und unten zu prüfen ob die angrenzenden Pixel ebenfalls rot sind. Wenn ja muss ein counter erhöht werden und weiter geprüft werden. Das müsste ich dann für jeden Pixel machen. ==> Speicherung der Daten ??

Oder ich habe überlegt mit den Pixelkoordinaten( die die rot sind) zu ermitteln welche nebeneinander liegen.

Soweit so gut, ich hoffe immer noch dass es eine andere Möglichkeit gibt, die ich vielleicht nicht sehe oder nicht weis.

FGGF Goddie

[Sunday]

genauso wuerde ich es auch bloss machen. du kommst nicht drum herum, als ueber das gesamte bild zu gehen und jeden pixel auf rot zu testen. wenn du einen roten pixel findest, labelst du ihn mit einer anderen farbe und zu verdeutlichen, dass du diesen punkt schon bewertet hast (kann ja vorkommen, dass objekte u-förmig oder sonst wie verwurstelt sind und sonst diese doppelt zählst). dann schaust du von diesem punkt (x,y merken) ob die nachbarpunkte ebenfalls rot sind (könntest du rekursiv machen (terminiert dann, wenn keine roten pixel mehr zu finden sind, kann aber bei grossen objekten zum stack-ueberlauf fuehren (quasi ein floodfill)) und zählst und labelst somit die pixel. dann beginnst du bei deiner gemerkten position erneut mit der suche und uebergehst alle pixel die gelabelt sind.

wenn dich nur die kontur interessiert, solltest du dich mal mit konturverfolgung befassen, dass ist in etwa das oben beschriebene verfahren, nur das dort nur die randpixel eines objektes bewertet und gesucht werden).

[C++ Forumbot]

Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[C++ Forumbot]

Dieser Thread wurde von Moderator/in kingruedi aus dem Forum Rund um die Programmierung in das Forum Spiele-/Grafikprogrammierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[TGGC]

WWWR
WWRR
WRRW
RRWW
RWWW

Würde das als eine "Kombination" der Farbe Rot mit Größe 8 gelten?

Bye, TGGC (Dem beste BdT)

[Goddie]

Wenn du damit die Pixel meinst, JA.

WWWWWWRWWWWWWWWWWW
WWWWWWRRRWWWWWWWWW
RRWWWWWWWWWWWWWWWW  <== kleinste Pixelkombination von Rot
WWWWWWWWWWWWWWWWWW
RRRRRRWWWWWWWWWWWW
RRRWWWWWWWWWWWWWWW
RWWWWWWWWWWWWWWWWW
WWWWWWWRRRRRRRWWWW

(jeder Buchstabe steht für ein Pixel des Bildes)

FGGF

Goddie

[thordk]

die überprüfung, ob ein markierter pixel zu einer bereits vorhanden klasse gehört, rekursiv laufen zu lassen wird teilweise eklig lahm und lässt dir den speicher u.u. schnell überlaufen.

anstatt nu grossartig zu erklären, häng ich mal nen code auszug an, der pixelcluster in nem binärbild markiert. ist nicht besonders optimiert oder erhebt anspruch darauf gut zu sein, ausserdem ist er auf 1000 klassen beschränkt (jaja, sehr eklig ;)), aber als denkanstoss sollte er vielleicht genügen ^^

void ImageTool::classReplace( int source, int destination, int max, int may ){
	for(int y = 0; y < imageHeight; y++)
		for(int x = 0; x < imageWidth; x++)
			if(!(x > max && y > may))
				if(marked[x][y] == source) marked[x][y] = destination;
	classes[source] = 0;
}

int ImageTool::getRecentClass(){
	for(int i = 1; i < 1000; i++)
		if(classes[i] == 0)
		{
			classes[i] = 1;
			return(i);
		}
	return(0);
}

void ImageTool::pixelcluster()
{
	int left, top;
	marked = new long*[imageWidth];
	for(int i = 0; i < imageWidth; i++)
	{
		marked[i] = new long[imageHeight];
		for(int j = 0; j < imageHeight; j++)
			marked[i][j] = 0;
	}

	classes[0] = 1;

	for(int y = 0; y < imageHeight; y++)
		for(int x = 0; x < imageWidth; x++)
		{

      // Wenn der Pixel zum Hintergrund gehoert, dann gehoert er zur Klasse 0
		if(workImage[y*imageWidth + x] == 0) marked[x][y] = 0;

      // Wenn der Pixel von 4 anderen Pixeln umgeben ist ...
		else if(x != 0 && y != 0)
		{
			left = marked[x-1][y];
			top = marked[x][y-1];

	// ... und oben und links ist Hintergrund, dann erhaelt er eine neue Klasse
			if(left == 0 && top == 0) marked[x][y] = getRecentClass();

	// ... und links ist Hintergrund und oben nicht, gehoert er zur oberen Klasse
			else if(left == 0 && top != 0) marked[x][y] = top;

	// ... und oben ist Hintergrund und links nicht, gehoert er zur linken Klasse
			else if(left != 0 && top == 0) marked[x][y] = left;

	// ... und links und oben ist die gleiche Klasse, gehoert er zu der Klasse
			else if(left == top) marked[x][y] = top;

	// ... und links und oben sind unterschiedliche Klassen, gehoert der Pixel zur oberen Klasse, die linke wird durch die obere ersetzt
			else if(left != top)
			{
				marked[x][y] = top;
				classReplace(left, top, x, y);
			}
		}

      // Der Pixel liegt in der ersten Spalte, aber nicht in der ersten Zeile ...
		else if(x == 0 && y != 0)
		{

        // ... und oben ist Hintergrund, gehoert der Pixel zur neuen Klasse
			if(marked[x][y-1] == 0) marked[x][y] = getRecentClass();

	// oder der Pixel gehoert zur oberen Klasse
			else marked[x][y] = marked[x][y-1];
		}

      // Der Pixel liegt in der ersten Zeile, aber nicht in der ersten Spalte ...
		else if(x != 0 && y == 0)
		{

        // ... und links ist Hintergrund, gehoert der Pixel zu einer neuen Klasse
			if(marked[x-1][y] == 0) marked[x][y] = getRecentClass();

	// oder der Pixel gehoert zur linken Klasse
			else marked[x][y] = marked[x-1][y];
		}

      // Der erste Pixel bekommt eine neue Klasse
		else marked[x][y] = getRecentClass();
	}

  //std::cerr << "Marking: 100%";

	int new_classes[1000];
	for(int i = 0; i < 1000; i++) new_classes[i] = 0;
	int cnt = 0;

	for(int i = 0; i < 1000; i++)
		if(classes[i] == 1)
		{
			new_classes[cnt] = 1;
			classes[i] = cnt++;
		}

	classcount = 0;
	for(int y = 0; y < imageHeight; y++)
		for(int x = 0; x < imageWidth; x++)
		{
			marked[x][y] = classes[marked[x][y]];
			if(marked[x][y] > classcount) classcount = marked[x][y];
		}

	for(int i = 0; i < 1000; i++) classes[i] = new_classes[i];
	classcount = 0;
	for(int i = 0; i < 1000; i++) if(classes[i] == 1) classcount++;

	std::cerr << classcount << " Objekte gefunden:" << std::endl;

	for(int y = 0; y < imageHeight; y++)
		for(int x = 0; x < imageWidth; x++)
			workImage[y*imageWidth + x] = marked[x][y];
}

[Goddie]

Danke erstmal für deine Hilfe. Ist nicht ganz leicht zu verstehen, was aber wohl nicht an dir oder deinem code liegt

Wenn ich das ganze einigermaßen richtig verstanden habe, nutzt du hier das Mines-Prinzip. Und am ende wird ausgegeben wieviele Objekte, also zusammenhängende Pixel gefunden wurden.

Bin gerade noch dabei das alles zu verstehen....

FGGF
Goddie

[thordk]

nennt sich das mines? war nie so fit in namen für verfahren

das grundprinzip ist sehr simpel. man hat ein binäres bild, welches "hintergrund" und "interessante flächen" trennt.
nun will man horizontal oder vertikal zusammenhängende flächen finden.

dazu geht man das bild pixel für pixel ab (ich nehm mal ursprung oben links an), von links nach rechts und zeile für zeile.

für jeden pixel macht man nun einen vergleich mit dem pixel links davon und über dem pixel.
die einfachste variante guckt nur, ob oben (oder links) auch "interessantes" liegt. ist dies der fall, so bekommt der aktuelle pixel dieselbe klasse zugewiesen, wie der entsprechende andere pixel.

das funktioniert auch, wenn man nur rechtwinkelige objekte hat. diese hat man natürlich nicht
z.b. bei so einem U (O = Hintergrund)

OOOOOOO
OXOOOXO
OXOOOXO
OXXXXXO
OOOOOOO

an dem X ganz unten rechts wird man feststellen, dass oben und links "interessantes" liegt, diese aber verschiedenen klassen zugeordnet sind.

dies handelt obiger code, indem er das gesamte bild, welches links oberhalb des aktuellen pixels liegt, nochmal durchgeht und die "linke" klasse durch die "obere" ersetzt.

dadurch hat man u.u. zwar sehr viele "unnötige" pixelvergleiche, aber diese sind meiner erfahrung nach immer noch schneller als rekursive verfahren. immerhin muss man hier nur auf nem array arbeiten und hat nur schleifen, keine funktionsaufrufe.
kann man durch divide & conquer verfahren o.ä. bestimmt auch noch optimieren.

lässt man das bis zum ende durchlaufen, hat man allen zusammenhängenden pixelclustern ne klasse zugeordnet.
aus diesen kann man sich dann leicht die kleinste(n) raussuchen.

wofür brauchst du denn sowas?

[Goddie]

JIPPIEEEE

Habs geschafft !!! Jetzt hab ich deinen Code auch fast völlig kapiert
Hab noch paar Änderungen vornehmen müssen (class-Array muss auch wieder zurückgesetzt werden), bei mehrfachen Aufrufen. Aber ansonsten find ich deinen Code genial ==> RESPEKT
Ist ne klase Idee das so zu machen.

Super-Herzlichen Dank an DICH !!!

Ohne deine Hilfe hätte ich da wohl noch ne ganze weile gebraucht, wenn ich es überhaut geschafft hätte. Hat zwar so auch noch ein bisschen gedauert aber jetzt hats endlich geklappt.

FGGF
Goddie