home  |  suche  |  kontakt/johner  |  institut 
studierende  |  tech-docs  |  mindmailer 

Schritt 1: Glättung des Bildes - entfernt Rauschen, Texturen, und Feinstruktur

Die Glättung des Bildes kann als eine Unstetigkeit der Grauwertfunktion g(x,y) des Ausgangsbildes aufgefasst werden. Da Unstetigkeiten auch ohne das Vorhandensein von Kanten einfach durch Bildrauschen, Texturen und Feinstrukturen auftreten können und diese sich nachteilig auf den nachfolgenden Schritt der Gradientenbildung auswirken kann, verwendet der Algorithmus die Normalverteilung zur Glättung des Bildes. Es wird daher auf das Bild die Gauss’sche Normalverteilungsfunktion mit der Standardabweichung Sigma (σ) angewandt um die „falschen“ Pixel im Bild zu vermindern. Je größer hier das Sigma (Paramater des Canny-Kantendektors) gewählt ist, desto stärker können diese Fehler minimiert werden. Der neue Grauwert eines Pixels gn(x,y) ergibt sich dabei aus den gewichteten Werten der ihn umgebenden Pixel.

	/**
	 * 
	 * Compute Gradients out of input picture
	 * 
	 * 1. Noise reduction
	 * 
	 * 2. Finding the intensity gradient of the image
	 * 
	 * 3. Non-maximum suppression
	 * 
	 */
	
	private void computeGradients(float kernelRadius, int kernelWidth) {

		// generate the gaussian convolution masks 1.
		float kernel[] = new float[kernelWidth];
		float diffKernel[] = new float[kernelWidth];
		int kwidth;
		for (kwidth = 0; kwidth < kernelWidth; kwidth++) {
			float g1 = gaussian(kwidth, kernelRadius);
			if (g1 <= GAUSSIAN_CUT_OFF && kwidth >= 2)
				break;
			float g2 = gaussian(kwidth - 0.5f, kernelRadius);
			float g3 = gaussian(kwidth + 0.5f, kernelRadius);
			kernel[kwidth] = (g1 + g2 + g3) / 3f
					/ (2f * (float) Math.PI * kernelRadius * kernelRadius);
			diffKernel[kwidth] = g3 - g2;
		}

		int initX = kwidth - 1;
		int maxX = width - (kwidth - 1);
		int initY = width * (kwidth - 1);
		int maxY = width * (height - (kwidth - 1));

		// perform convolution in x and y directions 2. 
		for (int x = initX; x < maxX; x++) {
			for (int y = initY; y < maxY; y += width) {
				int index = x + y;
				float sumX = data[index] * kernel[0];
				float sumY = sumX;
				int xOffset = 1;
				int yOffset = width;
				for (; xOffset < kwidth;) {
					sumY += kernel[xOffset]
							* (data[index - yOffset] + data[index + yOffset]);
					sumX += kernel[xOffset]
							* (data[index - xOffset] + data[index + xOffset]);
					yOffset += width;
					xOffset++;
				}

				yConv[index] = sumY;
				xConv[index] = sumX;
			}

		}

		for (int x = initX; x < maxX; x++) {
			for (int y = initY; y < maxY; y += width) {
				float sum = 0f;
				int index = x + y;
				for (int i = 1; i < kwidth; i++)
					sum += diffKernel[i]
							* (yConv[index - i] - yConv[index + i]);

				xGradient[index] = sum;
			}

		}

		for (int x = kwidth; x < width - kwidth; x++) {
			for (int y = initY; y < maxY; y += width) {
				float sum = 0.0f;
				int index = x + y;
				int yOffset = width;
				for (int i = 1; i < kwidth; i++) {
					sum += diffKernel[i]
							* (xConv[index - yOffset] - xConv[index + yOffset]);
					yOffset += width;
				}

				yGradient[index] = sum;
			}

		}

		initX = kwidth;
		maxX = width - kwidth;
		initY = width * kwidth;
		maxY = width * (height - kwidth);
		for (int x = initX; x < maxX; x++) {
			for (int y = initY; y < maxY; y += width) {
				int index = x + y;
				int indexN = index - width;
				int indexS = index + width;
				int indexW = index - 1;
				int indexE = index + 1;
				int indexNW = indexN - 1;
				int indexNE = indexN + 1;
				int indexSW = indexS - 1;
				int indexSE = indexS + 1;

				float xGrad = xGradient[index];
				float yGrad = yGradient[index];
				float gradMag = hypot(xGrad, yGrad);
				

				// perform non-maximal supression 4. 
				float nMag = hypot(xGradient[indexN], yGradient[indexN]);
				float sMag = hypot(xGradient[indexS], yGradient[indexS]);
				float wMag = hypot(xGradient[indexW], yGradient[indexW]);
				float eMag = hypot(xGradient[indexE], yGradient[indexE]);
				float neMag = hypot(xGradient[indexNE], yGradient[indexNE]);
				float seMag = hypot(xGradient[indexSE], yGradient[indexSE]);
				float swMag = hypot(xGradient[indexSW], yGradient[indexSW]);
				float nwMag = hypot(xGradient[indexNW], yGradient[indexNW]);
				float tmp;
				/*
				 * An explanation of what's happening here, for those who want
				 * to understand the source: This performs the "non-maximal
				 * supression" phase of the Canny edge detection in which we
				 * need to compare the gradient magnitude to that in the
				 * direction of the gradient; only if the value is a local
				 * maximum do we consider the point as an edge candidate.
				 * 
				 * We need to break the comparison into a number of different
				 * cases depending on the gradient direction so that the
				 * appropriate values can be used. To avoid computing the
				 * gradient direction, we use two simple comparisons: first we
				 * check that the partial derivatives have the same sign (1) and
				 * then we check which is larger (2). As a consequence, we have
				 * reduced the problem to one of four identical cases that each
				 * test the central gradient magnitude against the values at two
				 * points with 'identical support'; what this means is that the
				 * geometry required to accurately interpolate the magnitude of
				 * gradient function at those points has an identical geometry
				 * (upto right-angled-rotation/reflection).
				 * 
				 * When comparing the central gradient to the two interpolated
				 * values, we avoid performing any divisions by multiplying both
				 * sides of each inequality by the greater of the two partial
				 * derivatives. The common comparand is stored in a temporary
				 * variable (3) and reused in the mirror case (4).
				 */
				if (xGrad * yGrad <= (float) 0 /* (1) */
				? Math.abs(xGrad) >= Math.abs(yGrad) /* (2) */
				? (tmp = Math.abs(xGrad * gradMag)) >= Math.abs(yGrad * neMag
						- (xGrad + yGrad) * eMag) /* (3) */
						&& tmp > Math.abs(yGrad * swMag - (xGrad + yGrad)
								* wMag) /* (4) */
				: (tmp = Math.abs(yGrad * gradMag)) >= Math.abs(xGrad * neMag
						- (yGrad + xGrad) * nMag) /* (3) */
						&& tmp > Math.abs(xGrad * swMag - (yGrad + xGrad)
								* sMag) /* (4) */
				: Math.abs(xGrad) >= Math.abs(yGrad) /* (2) */
				? (tmp = Math.abs(xGrad * gradMag)) >= Math.abs(yGrad * seMag
						+ (xGrad - yGrad) * eMag) /* (3) */
						&& tmp > Math.abs(yGrad * nwMag + (xGrad - yGrad)
								* wMag) /* (4) */
				: (tmp = Math.abs(yGrad * gradMag)) >= Math.abs(xGrad * seMag
						+ (yGrad - xGrad) * sMag) /* (3) */
						&& tmp > Math.abs(xGrad * nwMag + (yGrad - xGrad)
								* nMag) /* (4) */
				) {
					magnitude[index] = gradMag >= MAGNITUDE_LIMIT ? MAGNITUDE_MAX
							: (int) (MAGNITUDE_SCALE * gradMag);
					// NOTE: The orientation of the edge is not employed by this
					// implementation. It is a simple matter to compute it at
					// this point as: Math.atan2(yGrad, xGrad);
				} else {
					magnitude[index] = 0;
				}
			}
		}
	}

	// NOTE: It is quite feasible to replace the implementation of this method
	// with one which only loosely approximates the hypot function. I've tested
	// simple approximations such as Math.abs(x) + Math.abs(y) and they work
	// fine.
	private float hypot(float x, float y) {
		return (float) Math.hypot(x, y);
	}

	private float gaussian(float x, float sigma) {
		return (float) Math.exp(-(x * x) / (2f * sigma * sigma));
	}

Schritt 2: Bestimmung des Gradienten (Kantenfilterung) - Falten des Bildes in X- bzw. Y-Richtung

Anschließend werden die Gradienten der einzelnen Pixel ermittelt (Kantenfindung). Der Sobeloperator ist ein Kantendetektor erster Ordnung und wird in x und y -Richtung auf das Bild angewendet, um horizontale bzw. vertikale Kanten zu ermitteln. Der neue Wert eines Pixels wird aus den gewichteten Werten der ihn umgebenden Pixel berechnet. Hierbei wird von der Faltung in die X- und y – Richtung eines Bildes gesprochen. Es ergeben sich also nach Anwendung des Sobeloperators zwei neue Bilder, wobei das eine die horizontalen und das andere die vertikalen Kanten betonen:

Sobel-Operator in X-Richtung:

Sobel-Operator in Y-Richtung:

Schritt 3: Berechnung des Gradienten – Richtungsbestimmung

Durch die mithilfe des Sobeloperators ermittelten horizontale und vertikale Gradienten, lassen sich die Anstiege einer potentiellen Kante durch einen Pixel leicht errechnen.

Es gilt:

Man erhält durch

die Richtung eines Gradienten, Hierbei beschreibt der Wert Θ = 0 eine vertikale Kante. Positive Werte beschreiben eine Drehung gegen den Uhrzeigersinn. Da ein Pixel nur 8 Nachbarn hat, ergeben sich lokal lediglich 4 mögliche Kantenrichtungen: 0°, 45°, 90° und 135°. Die Kanten können dadurch Horizontal, Vertikale und in den Diagonalen dargestellt werden.

Schritt 4: Nicht-Maximum-Unterdrückung

Nachdem die Richtung des Gradienten bekannt ist muss sichergestellt werden, dass eine Kante nicht mehr als einen Pixel breit ist. Es wird nach dem folgenden Schritt einzig die Maxima entlang einer Kante erhalten bleiben. Diese Technik wird "non-maximum suppression" genannt, sie unterdrückt also im Gradientenbetragsbild diejenigen Pixel, die entlang der Gradientenrichtung kein Maximum darstellen. Dafür wird vom Bild mit den absoluten Kantenstärken ausgegangen und für jeden Pixel die Werte G(x,y) mit denjenigen seiner 8 Nachbarn verglichen. Keiner der benachbarten Pixel darf einen höheren Wert aufweisen, es sei denn, der betreffende Nachbarspixel liegt entlang der berechneten Kantenrichtung. Ist dies nicht gegeben, wird der Grauwert des Pixels auf null gesetzt. Falls es kein Pixel mit einem größeren Gradienten in der Umgebung gibt, hat man das die Kante am besten verfolgende Pixel gefunden.

Schritt 5: Hysterese

Nachdem man so die Kanten auf einen Pixel Breite verjüngt hat, muss das Aufbrechen einer Kante durch Schwankungen in der errechneten Kantenstärke vermieden werden, also schließt man etwaige durchbrochene Kanten. Hierbei verwendet man die zwei Schwellwerte LowT1 < UpperT2 , um festzustellen ab welcher Kantenstärke ein Pixel zu einer Kante zu zählen ist oder nicht. Man scannt das Bild durch, bis ein Pixel gefunden wird, dessen Stärke größer UpperT2 ist. Dieser Kante folgt man dann beidseitig entlang des Gradienten. Alle Pixel entlang dieser Kante mit Stärke größer LowT1 werden als Kantenelement markiert.

  • Es werden alle Punkte, die unter der Grenze liegen verworfen.
  • Alle Punkte, die zwischen den beiden Grenzen liegen, werden bei der Linienverfolgung beachtet.
	/**
	 * 
	 * Combines calculated edges if necessary or deletes 
	 * calculated edges if not necessary. Depends on low and high Threshold parameter
	 * 
	 * 
	 * @param low Threshold
	 * @param high Threshold
	 */
	private void performHysteresis(int low, int high) {
		// NOTE: this implementation reuses the data array to store both
		// luminance data from the image, and edge intensity from the
		// processing.
		// This is done for memory efficiency, other implementations may wish
		// to separate these functions.
		Arrays.fill(data, 0);

		int offset = 0;
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				if (data[offset] == 0 && magnitude[offset] >= high) {
					follow(x, y, offset, low);
				}
				offset++;
			}
		}
	}

	private void follow(int x1, int y1, int i1, int threshold) {
		int x0 = x1 == 0 ? x1 : x1 - 1;
		int x2 = x1 == width - 1 ? x1 : x1 + 1;
		int y0 = y1 == 0 ? y1 : y1 - 1;
		int y2 = y1 == height - 1 ? y1 : y1 + 1;

		data[i1] = magnitude[i1];
		for (int x = x0; x <= x2; x++) {
			for (int y = y0; y <= y2; y++) {
				int i2 = x + y * width;
				if ((y != y1 || x != x1) && data[i2] == 0
						&& magnitude[i2] >= threshold) {
					follow(x, y, i2, threshold);
					return;
				}
			}
		}
	}
To view this content, you need to install Java from java.com

>weiter zur Kompression