Canny Operator

[fluffy17]

Hallo,
ich bin gerade dabei den Canny Kantenfindungsoperator für ein Studienprojekt zu implementieren. Dabei soll der Sobel-Operator zur Kantenerkennung dienen. Da es in der Literatur viele verschiedene Varianten gibt, bin ich etwas verunsichert.

Bei den ganzen Ergebnisbildern ist immer nur eine Konturlinie zu sehen, mein Problem ist ich habe zwei. Muss die zweite Linie bei der Non-Maximum-Unterdrückung rausfliegen oder brauche ich noch die Zweite Ableitung?

Vielen vielen Dank für Eure Hilfe

fluffy17

[Tyrdal]

Wieso zwei Linen? Was genau hast du denn bis jetzt gemacht?

[fluffy17]

bisher war ich so vorgegangen:

- separierte Gaußglättung durchführen
- Sobel-Operator auf das geglättete Bild anwenden(x und y Richtung um die Ableitung zu bekommen).
Daraus bekomme ich ja den Gradientenbetrag( sqrt(x² + y²) ) und die Gradientenrichtung(tan-1(gy, gx)). Unter der Berücksichtigung:

else if (gx == 0 && gy == 0) {
					angle = 0;
				} else if (gx == 0 && gy != 0) {
					angle = 90;
				}

- dann mache ich die Non-Maximum-Unterdrückung, gucke wohin der Gradient zeigt(wobei 0° Senkrecht nach unten ist)
- dann mach ich die Hysterese, also alles was unter T_low wird wegworfen, was über T_high liegt gilt als sichere Kante. Und alles was zwischen T_low und T_high wird getestet. Also wird bei jeden Gradientenbetrag zwsichen T_low und T_high in einer Umgebung getestet, ob eine sichere Kante vorhanden ist. Wenn ja gilt der Punkt auch als Kante.

Beispielsweise soll das Ergebnis ja so aussehen:
http://www-graphics.stanford.edu/~jowens/223b/lena/lena.canny.jpg

bei mir sieht es aber so aus
http://www.bilder-space.de/show_img.php?img=e6e840-1292590343.png&size=original

[Nick Unbekannt]

Sieht doch schon mal ganz gut aus. Dein Schwellwert, um zu entscheiden, ob es sich um eine Kante handelt, ist aber eindeutig zu hoch. Das ist jetzt sicher keine mathematisch korrekte Lösung, aber ich würde mit den Werten (insbesondere Schwellwerten) rum spielen und die Tendenzen ansehen. Was mich ein wenig irritiert ist, dass du 3 Kanten findest. Zwei hätte ich noch nachvollziehen können, hell->dunkel und dunkel->hell. Oder arbeitest du mit einer Strichzeichnung? Wie sieht den dein Ausgangsbild aus? Also auf das du die Filter anwendest.

[krümelkacker]

Ich würde sagen, die Glättung könnte man vorher noch stärker machen. Und mit welcher Genauigkeit rechnest/speicherst Du? Mit floats oder mit Ints im Bereich 0-255?

[fluffy17]

Ich verwende das Lena-Bild (RGB in einer Auflösung 512x512) und wandel es in Grauwerte um,
also Grauwert = (rot + blau + grün) / 3
Intern rechne ich immer mit Integer-Werten, da die Gradientenbeträge auch negativ werden können. Am Ende kommt ein Schwarz/Weiß Bild raus, also weiß entspricht einer Kante.

Mit den Parametern, habe ich jetzt auch weiter rumgespielt und gemerkt um so größer die Glättung ist um so breiter werden die Kanten ist das normal?
Sigma 8:

Um so größer die Glättung ist um so mehr Kanten werden gefunden.
http://www.bilder-space.de/show_img.php?img=684e89-1292627080.png&size=original

Bei Sigma 1.1(Flättung), T_low = 40 und T_high = 80:
http://www.bilder-space.de/show_img.php?img=7f55a5-1292627331.png&size=original

Bevor die Methoden ausgeführt werden, wird die Gaußglättung durchgeführt.

protected void createGradients() {
		angles = new float[pixelOrg.length];
		posValues = new int[pixelOrg.length];

		float[][] maskY = new float[][] { { 1, 2, 1 }, { -1, -2, -1 },
				{ 0, 0, 0 } };

		float[][] maskX = new float[][] { { -1f, 0f, 1f }, { -2f, 0f, 2f },
				{ -1f, 0f, 1f } };

		for (int y = 1; y < height - 1; y++) { // Zeilenschleife
			for (int x = 1; x < width - 1; x++) { // Spaltenschleife

				int gx = 0, gy = 0;
				// Berechne Gradienten
				for (int mm = -maskX.length / 2; mm <= maskX.length / 2; mm++) {
					for (int nn = -maskX[0].length / 2; nn <= maskX[0].length / 2; nn++) { //
						int w = nn;
						int h = mm;

						// left and right
						if (x + nn < 0 || x + nn >= width) {
							w = -nn;
						}
						// bottom and up
						if (y + mm < 0 || y + mm >= height) {
							h = -mm;
						}

						float currentMatrixValueX = maskX[w + maskX[0].length
								/ 2][h + maskX.length / 2];
						float currentMatrixValueY = maskY[w + maskY[0].length
								/ 2][h + maskY.length / 2];

						// Color org = new Color(pixelOrg[(y * width + x)
						// + (h * width + w)]);
						int p = pixelOrg[(y * width + x) + (h * width + w)];
						int r = (p & 0xff0000) >> 16;
						int g = (p & 0x00ff00) >> 8;
						int b = (p & 0x0000ff);

						gx += ((0.333f * r) + (0.333f * g) + (0.333f * b))
								* currentMatrixValueX;
						gy += ((0.333f * r) + (0.333f * g) + (0.333f * b))
								* currentMatrixValueY;
					}
				}

				// Betrag berechnen
				// sqrt(gx² + gy²)
				posValues[y * width + x] = (int) Math.sqrt(gx * gx + gy * gy);

				// Winkel berechnen
				float angle = 0;
				if (gx != 0) {
					angle = (float) Math.toDegrees(Math.atan2(gy, gx));
				} else if (gx == 0 && gy == 0) {
					angle = 0;
				} else if (gx == 0 && gy != 0) {
					angle = 90;
				}

				angles[y * width + x] = (float) angle;
			}
		}
	}

// Gradientenbeträge werden liniear interpoliert
protected void nonMaximaSuppression() {
		for (int y = 0; y < height; y++) { // Zeilenschleife
			for (int x = 0; x < width; x++) { // Spaltenschleife
				// Prüfe in Welchen Quadrat der Gradient liegt
				float angle = angles[y * width + x];

				// es wird in beide Richtung geschaut, daher kann der Winkel auf
				// 0 ... 180 eingeschränkt werden
				if (angle >= 180)
					angle -= 180;
				if (angle < 0)
					angle += 180;

				float current = posValues[y * width + x];
				float a, b;

				// Q1
				if (angle > 135) {
					if (y - 1 >= 0 && x + 1 < width) {
						a = posValues[(y - 1) * width + x];
						b = posValues[(y - 1) * width + x + 1];
						float fac = (angle - 135f) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
					if (y + 1 < height && x - 1 >= 0) {
						a = posValues[(y + 1) * width + x];
						b = posValues[(y + 1) * width + x - 1];
						float fac = (angle - 135f) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
				}
				// Q1
				else if (angle > 90) {
					if (y - 1 >= 0 && x + 1 < width) {
						a = posValues[(y - 1) * width + x + 1];
						b = posValues[y * width + x + 1];
						float fac = (angle - 90f) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
					if (y + 1 < height && x - 1 >= 0) {
						a = posValues[(y + 1) * width + x - 1];
						b = posValues[y * width + x - 1];
						float fac = (angle - 90f) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
				}
				// Q3
				else if (angle > 45) {
					if (y + 1 < height && x + 1 < width) {
						a = posValues[y * width + x + 1];
						b = posValues[(y + 1) * width + x + 1];
						float fac = (angle - 45f) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
					if (y - 1 >= 0 && x - 1 >= 0) {
						a = posValues[y * width + x - 1];
						b = posValues[(y - 1) * width + x - 1];
						float fac = (angle - 45f) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
				}
				// Q3 0 - 45
				else {
					if (y + 1 < height && x + 1 < width) {
						a = posValues[(y + 1) * width + x + 1];
						b = posValues[(y + 1) * width + x];
						float fac = (angle) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
					if (y - 1 >= 0 && x - 1 >= 0) {
						a = posValues[(y - 1) * width + x - 1];
						b = posValues[(y - 1) * width + x];
						float fac = (angle) / 45f;
						float tmp = a * (fac) + b * (1 - fac);

						if (tmp >= current) {
							posValues[y * width + x] = 0;
							nonMax++;
						}
					}
				}

			}
		}
	}

protected void hysterese() {
		//Vorverarbeitung
		for (int y = 0; y < height; y++) { // Zeilenschleife
			for (int x = 0; x < width; x++) { // Spaltenschleife

				// die Gradientenbeträge die kleiner T1 sind werden nicht
				// beachtet => gelöscht
				if (posValues[y * width + x] < T1) {
					posValues[y * width + x] = 0;
				}
				// markiere alle Pixel mit Werten größer T2 als Kantenpixel
				if (posValues[y * width + x] > T2) {
					// bedeutet das es eine sichere Kante ist
					posValues[y * width + x] = T2;
				}
			}
		}

		for (int y = 0; y < height; y++) { // Zeilenschleife
			for (int x = 0; x < width; x++) { // Spaltenschleife
				if (posValues[y * width + x] == 0) {
					pixelNew[y * width + x] = Color.BLACK.getRGB();
				} else if (posValues[y * width + x] == T2) {
					pixelNew[y * width + x] = Color.WHITE.getRGB();
				}

				else if (posValues[y * width + x] >= T1
						&& posValues[y * width + x] < T2) {

					// prüfe das nächste Pixel
					if (hhhhhhhhh(x, y)
					// tracingEdge(x, y, 10)
					) {
						// setze das aktuelle Pixel als Kante
						// posValues[y * width + x] = T2;
						pixelNew[y * width + x] = Color.WHITE.getRGB();
					} else {
						// Pixel ist kleiner als T1 => löschen
						// posValues[y * width + x] = 0;
						pixelNew[y * width + x] = Color.BLACK.getRGB();
					}
				}
			}
		}
	}
		protected boolean hhhhhhhhh(int x, int y) {
		int S = 3;
		int s = (S - 1) / 2;

		if (posValues[y * width + x] >= T1 && posValues[y * width + x] < T2) {

			// prüfe die umliegenden Pixel
			for (int n = -s; n < s; n++) {
				for (int m = -s; m < s; m++) {
					if (n != 0 && m != 0 && x + n >= 0 && x + n < width
							&& y + m >= 0 && y + m < height) {

						if (posValues[y * width + x + ((m * width) + n)] == T2) {
							return true;
						}
					}
				}
			}
		}
		return false;
	}

Bisher habe ich den Algorithmus noch nicht implementiert, daher weiß ich leider auch nicht ob es normal das man mehrere Kanten bekommt, wobei nur eine real da ist.
Wenn T_low(T1) = 90 und T_high(T2) = 180 setze, bekomme ich zwar annährend das Ergebnis, aber der Canny Algorithmus soll ja eigentlich sehr rubust sein

http://www.bilder-space.de/show_img.php?img=4e905b-1292628907.png&size=original

PS: Sorry, das ich Java Code in C++ Rubrik poste.

Vielen vielen Dank für die bisherigen Antworten