[C++] Skelettierung mit Zhang/Suen-Algorithmus

K

kanonenfutter90

Grünschnabel
Hi.

Versuche mich gerade an der Skelettierung von binären Bildern und bin dabei über den Zhang/Suen-Algorithmus gestolpert. Habe den Code, wie ich meine, soweit auch vollständig, allerdings glaube ich in einer Endlosschleife zu hängen, weshalb ich kein Ergebnis zu Gesicht bekomme. Nach etwas Debugging denke ich das ich bei meiner "do-while" Schleife festhänge. Kann den Fehler leider nicht finden, vllt. stimmt auch im Algorithmus etwas nicht.

Wenn sich jmd. damit auskennt wäre es super wenn derjenige da mal drüberschaut. Ansonsten bin ich auch für andere Algorithmen offen, sofern diese verständlich und einfach zu implementieren sind...

PS: Ich arbeite wegen den Bildern mit der CImg-Library.

Der Code:
Code: 
#include "CImg.h"
using namespace cimg_library;

int main()
{
	CImg<int>image("test.jpg");
	CImg<int>skelett(image.width(), image.height(), 1, 1, 0);

	int x, y, i, Anzahl, Bedingung, Aenderung, Ende = 0;
	int P[11] = {0}; /* die 8 direkten Nachbarn */

	/* Iterativ verduennen nach modifiziertem Zhang/Suen-Algorith. */
	Ende = FALSE;
	do 
	{

	Aenderung=0;

	for (x=1; x<image.width()-1; x++) 
		{
			for (y=1; y<image.height()-1; y++) 
			{
				if (image(x,y,0,0) == 0) 
				{
					/* Nachbarn ermitteln
					P[2] = image(x,y-1,0,0);
					P[3] = image(x+1,y-1,0,0);
					P[4] = image(x+1,y,0,0);
					P[5] = image(x+1,y+1,0,0);
					P[6] = image(x,y+1,0,0);
					P[7] = image(x-1,y+1,0,0);
					P[8] = image(x-1,y,0,0);
					P[9] = image(x-1,y-1,0,0);
					P[10]= P[2]; /* Fuer 0-1-Uebergang von P[9]-P[2] */
					
					Bedingung	= 0;
					Anzahl		= 0; /* Anzahl der weissen Nachbarn */
					
					for (i=2; i<=9; i++)
					{
						if (P[i] == 255) 
						{
							Anzahl++;
						}
					}

					/* Zhang/Suen */
					if ((3<=Anzahl) && (Anzahl<=6)) /* 3<=S(P1)<=6 */
					{
						Bedingung += 1;
					}
					
					if (!(P[2] && P[4] && P[6])) /* P2*P4*P6=0 */
					{
						Bedingung += 2;
					}
					
					if (!(P[4] && P[6] && P[8])) /* P4*P6*P8=0 */
					{
						Bedingung += 4;
					}

					Anzahl = 0;

					for (i=2; i<10; i++)
					{
						if (!P[i] && P[i+1])
						{
							Anzahl++; /* 01-Muster */
						}
					}

					if (Anzahl==1)
					{
						Bedingung += 8;
					}
					
					/* Falls alle Bedingungen erfuellt, markieren*/
					if (Bedingung==15) 
					{
						skelett(x,y,0,0) = 128;/* Pixel mark.*/
						Aenderung++;
					}
				}
			}
		}
		
		Ende = (Aenderung==0);
	

		/* Nach einem Durchlauf alle markierten Pixel loeschen */
		for (x=0; x<image.width(); x++)
		{
			for (y=0; y<image.height(); y++)
			{
				if (skelett(x,y,0,0) == 128)
				{
					skelett(x,y,0,0) = 0;
				}
			}
		}
		
		/* von rechts unten nach links oben */
		Aenderung = 0;

		for (x=image.width()-1; x>=1; x--) 
			{
				for (y=image.height()-1; y>=1; y--) 
				{
					if (image(x,y,0,0)) 
					{
						// Nachbarn ermitteln
						P[2] = image(x,y-1,0,0);
						P[3] = image(x+1,y-1,0,0);
						P[4] = image(x+1,y,0,0);
						P[5] = image(x+1,y+1,0,0);
						P[6] = image(x,y+1,0,0);
						P[7] = image(x-1,y+1,0,0);
						P[8] = image(x-1,y,0,0);
						P[9] = image(x-1,y-1,0,0);
						P[10]=P[2]; // Fuer 0-1-Uebergang von P[9]-P[2]
						
						Bedingung=0;
						Anzahl =0; // Anzahl der weissen Nachbarn
						
						for (i=2; i<=9; i++)
						{
							if (P[i] == 255) 
							{
									Anzahl++;
							}
						}
	// Zhang/Suen
						if ((3<=Anzahl) && (Anzahl<=6)) // 3<=S(P1)<=6
						{
							Bedingung += 1;
						}

						if (!(P[2] && P[4] && P[8])) // P2*P4*P8=0
						{						
							Bedingung += 2;
						}

						if (!(P[2] && P[6] && P[8])) // P2*P6*P8=0
						{
							Bedingung += 4;
						}

						Anzahl=0;

						for (i=2; i<10; i++)
						{
							if (!P[i] && P[i+1]) 
							{
									Anzahl++; // 01-Muster 
							}
						}

						if (Anzahl==1) 
						{
							Bedingung += 8;
						}
						// alle Bedingungen erfuellt, markieren
						if (Bedingung==15) 
						{
							skelett(x,y,0,0) = 128;// Pixel mark.
							Aenderung++;
						}
					}
				}
			} 
		
		Ende =	(Ende && (Aenderung==0));
	
		// Nach einem Durchlauf nun alle markierten Pixel loeschen
		for (x=0; x<image.width(); x++)
		{
			for (y=0; y<image.height(); y++)
			{
				if (skelett(x,y,0,0)==128)
				{
					skelett(x,y,0,0)=0;
				}
			}
		}
	} while (!Ende); // Ende erst, falls keine Aenderung mehr 

	CImgList<int>list(image, skelett);
	list.display("Test", false, 'x', 'c');
}

mfg :)
 
Hallo,

die Zeilen 26-34 sind auskommentiert, ist das so gewollt? Die Endlosschleife kommt daher, dass die Abbruchbedingung nur an Eigenschaften von image geknüpft ist. Du greifst in der Schleife aber nur lesend auf image zu, weswegen sich die Abbruchbedingung nicht ändert.

Grüße,
Matthias
 
Die Auskommentierung steht da wohl noch von der letzten Debug-Session... ;) Die Kommentarstriche wegdenken, dann passts wieder :)

Danke für den Ansatz mit image, werd das gleich nochmal durchsehen und mich wieder melden.

thx
 
Alles klar, hab nochmal ein paar Kleinigkeiten geändert, jetzt scheints zu funktionieren :D

Hier nochmal der aktuelle, funktionierende Quelltext, falls jmd. mal das gleiche Problem hat:

Code: 
#include "CImg.h"
using namespace cimg_library;

int main()
{
	CImg<int>image("test.jpg");
	CImg<int>skelett(image.width(), image.height(), 1, 1, 0);

	int x, y, i, Anzahl, Bedingung, Aenderung = 0;
	int P[11] = {0}; /* die 8 direkten Nachbarn */
	bool Ende = false;
	
	/* Iterativ verduennen nach modifiziertem Zhang/Suen-Algorith. */
		
	for(x=0; x<image.width(); x++)			//Ausgangsbild kopieren
	{
		for(y=0; y<image.height(); y++)
		{
			skelett(x,y,0,0) = image(x,y,0,0);
		}
	}
	
/////

	do 
	{

	Aenderung=0;

	for (x=1; x<skelett.width()-1; x++) 
		{
			for (y=1; y<skelett.height()-1; y++) 
			{
				if (skelett(x,y,0,0) == 0) 
				{
					/* Nachbarn ermitteln. Zur leichteren Berechnung */
					P[2] = skelett(x,y-1,0,0);
					P[3] = skelett(x+1,y-1,0,0);
					P[4] = skelett(x+1,y,0,0);
					P[5] = skelett(x+1,y+1,0,0);
					P[6] = skelett(x,y+1,0,0);
					P[7] = skelett(x-1,y+1,0,0);
					P[8] = skelett(x-1,y,0,0);
					P[9] = skelett(x-1,y-1,0,0);
					P[10]= P[2]; /* Fuer 0-1-Uebergang von P[9]-P[2] */
					
					Bedingung	= 0;
					Anzahl		= 0; /* Anzahl der weissen Nachbarn */
					
					for (i=2; i<=9; i++)
					{
						if (P[i] == 255) 
						{
							Anzahl++;
						}
					}

					/* diese erste Bedingung weicht von Zhang/Suen ab*/
					if ((3<=Anzahl) && (Anzahl<=6)) /* 3<=S(P1)<=6 */
					{
						Bedingung += 1;
					}
					
					if (!(P[2] && P[4] && P[6])) /* P2*P4*P6=0 */
					{
						Bedingung += 2;
					}
					
					if (!(P[4] && P[6] && P[8])) /* P4*P6*P8=0 */
					{
						Bedingung += 4;
					}

					Anzahl = 0;

					for (i=2; i<10; i++)
					{
						if (!P[i] && P[i+1])
						{
							Anzahl++; /* 01-Muster */
						}
					}

					if (Anzahl==1)
					{
						Bedingung += 8;
					}
					
					/* Falls alle Bedingungen a-d erfuellt, markieren*/
					if (Bedingung==15) 
					{
						skelett(x,y,0,0) = 128;/* Pixel mark.*/
						Aenderung++;
					}
				}
			}
		}
		
		if(Aenderung == 0)
		{
			Ende = true;
		}	

		/* Nach einem Durchlauf nun alle markierten Pixel loeschen */
		for (x=0; x<skelett.width(); x++)
		{
			for (y=0; y<skelett.height(); y++)
			{
				if (skelett(x,y,0,0) == 128)
				{
					skelett(x,y,0,0) = 255;
				}
			}
		}
		
		// Nun von rechts unten nach links oben Skelett berechnen 
		Aenderung = 0;

		for (x=skelett.width()-1; x>=1; x--) 
		{
			for (y=skelett.height()-1; y>=1; y--) 
			{
				if (skelett(x,y,0,0)) 
				{
					// Nachbarn ermitteln. Zur leichteren Berechnung
					P[2] = skelett(x,y-1,0,0);
					P[3] = skelett(x+1,y-1,0,0);
					P[4] = skelett(x+1,y,0,0);
					P[5] = skelett(x+1,y+1,0,0);
					P[6] = skelett(x,y+1,0,0);
					P[7] = skelett(x-1,y+1,0,0);
					P[8] = skelett(x-1,y,0,0);
					P[9] = skelett(x-1,y-1,0,0);
					P[10]= P[2]; // Fuer 0-1-Uebergang von P[9]-P[2]
						
					Bedingung	= 0;
					Anzahl		= 0; // Anzahl der weissen Nachbarn
						
					for (i=2; i<=9; i++)
					{
						if (P[i] == 255) 
						{
								Anzahl++;
						}
					}
// diese erste Bedingung weicht von Zhang/Suen ab
					if ((3<=Anzahl) && (Anzahl<=6)) // 3<=S(P1)<=6
					{
						Bedingung += 1;
					}

					if (!(P[2] && P[4] && P[8])) // P2*P4*P8=0
					{						
						Bedingung += 2;
					}

					if (!(P[2] && P[6] && P[8])) // P2*P6*P8=0
					{
						Bedingung += 4;
					}

					Anzahl=0;

					for (i=2; i<10; i++)
					{
						if (!P[i] && P[i+1]) 
						{
								Anzahl++; // 01-Muster 
						}
					}

					if (Anzahl==1) 
					{
						Bedingung += 8;
					}
					// Falls alle Bedingungen a-d erfuellt, markieren
					if (Bedingung==15) 
					{
						skelett(x,y,0,0) = 128;// Pixel mark.
						Aenderung++;
					}
				}
			}
		} 

		if((Aenderung == 0) && (Ende == true))
		{
			Ende = true;
		}

//		Ende =	(Ende && (Aenderung==0));
	
		// Nach einem Durchlauf nun alle markierten Pixel loeschen
		for (x=0; x<skelett.width(); x++)
		{
			for (y=0; y<skelett.height(); y++)
			{
				if (skelett(x,y,0,0)==128)
				{
					skelett(x,y,0,0)=255;
				}
			}
		}
	} while (!Ende); // Ende erst, falls keine Aenderung mehr 

	CImgList<int>list(image, skelett);
	list.display("Test", false, 'x', 'c');
}

Im Detail:

In Zeile 11 hab ich Ende erstmal als bool genommen, weiß nich warum ich den als int hatte, egal... :)

In Zeile 15-21 hab ich dann erstmal das geladene Bild "image" in das Zielbild "skelett" kopiert. So kann ich danach alles auf skelett ausführen und muss nicht auf image zugreifen.

Dann kommen die ganzen Bedingungen...und in Zeile 99-102 (und 186-189) etwas Kosmetik, damit überschaubarer, sollte aber keinen Unterschied zum vorherigen Code darstellen.

In Zeile 111 (und dann nochmal in 200) hatte ich den Fehler die Pixel auf 0 zu setzen, was aber falsch ist. Diese müssen natürlich auf 255 gesetzt werden...

Damit passts...Danke auch nochmal... ;)

mfg
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück