# Akkumulator Hough-Transformation offene Fragen



## Faber (11. Feb 2012)

Hallo zusammen,

nachdem ihr mir zum Erkennen von geometrischen Figuren die Hough-Transformationen vorgeschlagen habt, habe ich nun den Akkumulator dafür programmiert. Ich habe zwar ein Ergebnis, aber noch offene Fragen zum besseren Verständnis und um ein  Code Review würde ich auch bitten. Im Anhang findet ihr das Projekt mit Beispielbildern zum Testen, wenn ihr mögt.

Meine Fragsen sind:

1)Das .gif Format wird im Akkumulator nicht angezeigt. Konvertiert man .gif in .png gibt es keine Probleme.

2) In der Lektüre steht:rtfm:, dass es in der Praxis üblich ist, das Zentrum als Referenzpunkt für die x/y Bildkoordinate zu benutzen, dann ist der mögliche Bereich für den Radius auf die Hälfe der Bilddiagonale beschränkt. Das habe ichversucht umzusetzen, habe es aber nur teilweise geschafft.

3) In Zeile: 57 teile ich meine Anzahl der gewünschten Teilschritte durch PI und multipliziere anschließend mit der Zählvariablen.  Dieser Schritt ist mir noch etwas unklar.  Warum kann ich nicht direkt die Zählvariable als Grad in meine Hessesche Normalform einsetzten . z. B:

```
int r=(int) ((u*Math.cos(zaehlvaribale))+(v*Math.sin(zaehlvaribale)));
```
Oder ist das eine Maßnahme, damit man zwischen Radiant in Grad umrechnen kann?

Danke für jede Hilfe...


```
package hough;

import hough.viewer.ImageViewer;

import java.awt.image.BufferedImage;
import java.awt.image.WritableRaster;
import java.io.File;
import java.io.IOException;

public class HoughLine {

	private BufferedImage img;
	private int[][] houghArray;
	private int thetaMax=180;
	private int rmax=0;
	
	
	public HoughLine(BufferedImage input) {
		this.img=input;
	}
	
	public static void main(String[] args) throws IOException {
		String filename = "C://Users//jab//Programmierung//workspace_1//Hough//src//hough//pictures//oneEdge.png";
        
        BufferedImage image = javax.imageio.ImageIO.read(new File(filename));

        HoughLine hough=new HoughLine(image);
		hough.createAccumulator();
	}
	
	private int[][] createAccumulator(){
		
		int centerx=img.getWidth()/2;
		int centery=img.getHeight()/2;
		
		WritableRaster raster=img.getRaster();
		//längste Strecke vom Zentrum des Bildes ausgesehen
		rmax=(int) Math.sqrt((centerx*centerx)+(centery*centery));
		
		System.out.println("Bildhöhe: "+img.getHeight());
		System.out.println("Bildbreite: "+img.getWidth());
		System.out.println("rmax: "+rmax);
		System.out.println("------------------");

//		houghArray = new int[thetaMax][rmax];
		houghArray = new int[thetaMax][2*rmax];
		/**
		 * u=x
		 * v=y
		 */
		for(int u = 0; u < img.getHeight();u++){
			for(int v = 0; v < img.getWidth();v++){
				int value=raster.getSample(v, u, 0);
				if(value==255){
//					System.out.println("\nKante gefunden: P("+v+"|"+u+")(x|y)");
					for(int t=0; t<thetaMax;t++){
						double theta = t*(Math.PI/180);
						int r=(int) ((u*Math.cos(theta))+(v*Math.sin(theta)));
//						int r=(int) ((u*Math.cos(t))+(v*Math.sin(t)));
//						int r=(int) (u*Math.cos(((t)*Math.PI)/180)+v*Math.sin(((t)*Math.PI)/180));
//						System.out.println("Für Theta: "+t+" distance: "+r);
						
						//füllen des Akkumulator-Arrays
						if((r >= 0) && (r <= rmax)){
							houghArray[t][r]++;
						}
						
					}
				}
			}
		}

		/**
		 * Hough-Array (Voting-Matrix) auf Konsole ausgeben
		 */
//		 for (int k = 0; k < houghArray.length; k++) {  
//			 System.out.print(k+" Grad: ");
//			 for (int l = 0; l < houghArray[k].length; l++) {
//	                System.out.print(houghArray[k][l] + ",");
//	            }
//	            System.out.println("");
//	       }
		
		ImageViewer imageViewer = new ImageViewer(img,"Hough_input");
		imageViewer.setVisible(true);

		
		BufferedImage houghLine=getHoughImage();
		ImageViewer imageViewer2 = new ImageViewer(houghLine,"Hough_Line");
		imageViewer2.setVisible(true);
		
		
		System.out.println("HöchsterWert: "+getMaxHoughArray());
		
		return null;
		
	}
	/**
	 * finde den Maximalen Wert im Hough-Array
	 * @return
	 */
	  public int getMaxHoughArray() { 
	        int max = 0; 
	        for (int t = 0; t < thetaMax; t++) { 
	            for (int r = 0; r < (2*rmax); r++) { 
	                if (houghArray[t][r] > max) { 
	                    max = houghArray[t][r]; 
	                } 
	            } 
	        } 
	        return max; 
	    } 
	/**
	 * Zeige das Hough-Array als Bild an.
	 * @return
	 */
	 public BufferedImage getHoughImage() { 
	        int max = getMaxHoughArray(); 
	        BufferedImage image = new BufferedImage(thetaMax, rmax, BufferedImage.TYPE_BYTE_GRAY);
	        WritableRaster raster=image.getRaster();
	        for (int t = 0; t < thetaMax; t++) { 
	            for (int r = 0; r < (rmax); r++) { 
	            	//normalisierten
	                double value = 255 * ((double) houghArray[t][r]) / max; 
	                raster.setSample(t, r, 0,value);
	            } 
	        } 
	        System.out.println("Akku Breite: "+ image.getWidth());
	        System.out.println("Akku Höhe: "+image.getHeight());
	        image.setData(raster);
	        return image; 
	    } 
	
}
```


----------



## Marco13 (11. Feb 2012)

Uh-hu... beinahe hätte ich damit meine eigenen Hough.zip und das Projekt überschrieben 

Zu 1.: Du greifst über das Raster und getSample auf die Pixel zu. Da muss man ein bißchen aufpassen, weil man diese Daten erst "interpretieren" muss, bzw. sie bei unterschiedlichen Bildtypen unterschiedliche Bedeutungen haben können. Ein GIF hat z.B. immer nur höchstens 256 Farben (oder in diesem Fall nur zwei), und dort stehen die bytes dann ggf. für Indizes in einer Farbtabelle. D.h. nach dem Einlesen ist das Bild vielleicht vom Typ TYPE_BYTE_INDEXED, wo der Wert "0" für Weiß und "1" für schwarz steht oder so... Die einfachste Möglichkeit ist jetzt erstmal, das Einlesen zu

```
BufferedImage image0 = javax.imageio.ImageIO.read(new File(filename));
        BufferedImage image = new BufferedImage(image0.getWidth(), image0.getHeight(), BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = image.createGraphics();
        g.drawImage(image0, 0, 0, null);
        g.dispose();
        HoughLine hough=new HoughLine(image);
```
zu ändern, damit man immer ein INT_ARGB Bild hat. Aber du solltest genau überlegen, auf welchen Bildtyp zu arbeiten willst! Soll z.B. später irgendwann mal eine Kante zwischen einem Roten und einem Grünen Bereich erkannt werden? Vermutlich schon...

Zu 2 und 3... Muss ich sagen, dass ich etwas "raus" bin: Meine Hough-Tests sind schon eine Weile her - aber ich erinnere mich noch, dass die Frage, wie breit welcher Array ist und wie die Umrechnungen sein müssen ziemlich frickelig war...  

Speziell zu 2. weiß ich nicht (mehr) genau, was du meinst, vielleicht könnte ich im Verlauf der nächsten Woche mal versuchen, eine etwas genauere Beschreibung der Frage (bzw. was da bei dir nicht funktioniert hat) auf meinen alten Code zu "mappen"...

Zu 3: Falls ich das richtig verstanden habe bezieht sich die Frage nur darauf: Die ganzen Math.cos/sin/tan/usw Methoden erwarten den Winkel in _Radians_ und nicht in Grad. Wenn du als eine Laufvariable von 0 bis 180 oder 360 hast, dann sind das Grad - die muss die noch auf Radians umrechnen. (Ggf. auch mal Math.toRadians und Math.toDegrees ansehen...)


----------



## Faber (11. Feb 2012)

Danke Marco,

das zu Punkt 1 mit dem Raster wusste ich nicht. Ich dachte direkt die Rohdaten zu benutzen wäre besser.

dein tipp zu Punkt 3 hat mir auch sehr geholfen. Zwar war meine Frage etwas anders gemeint, aber die hat mir schon ein Buch beantwortet können. Da hieß es, ich zitiere:



> Eine Größe von 256 entlang der theta-Achse bedeutet z.B. eine Schrittweite der Geradenrichtung von PI/256 = 0.7°. Eine Vergrößerung des Akkumulators führt zu feineren Ergebnissen, bedeutet aber auch zusätzliche Rechenzeit und insbesondere einen höheren  Speicherbedarf.


  Burger&Burger, Digitale Bildverarbeitung mit java und ImageJ, Seite 166

Da PI ein Halbkreis von 180° ist, bedeutet das: 180/256=0.703125°. In meinem Fall also 180/180 = 1. Also sind meine Abstände 1° groß. Das muss dann als Radiant dann in die Hessesche NormalForm eingesetzt werden, glaub ich jedenfalls 
So klappts:

```
int r=(int) ((u*Math.cos(Math.toRadians(t)))+(v*Math.sin(Math.toRadians(t))));
```


Ansonsten habe ich die Maxima im Akkumulator extrahieren können. Also die Schnittstellen der Kurven im HoughRaum. Ich denke, der nächste Schritt wäre jetzt aus den Informationen geometrische Figuren zu erkennen. Kein Plan, wie das gehen soll. Ist dann wieder Recherche angesagt...


----------



## Dow Jones (13. Feb 2012)

Faber hat gesagt.:


> Ansonsten habe ich die Maxima im Akkumulator extrahieren können. Also die Schnittstellen der Kurven im HoughRaum. Ich denke, der nächste Schritt wäre jetzt aus den Informationen geometrische Figuren zu erkennen. Kein Plan, wie das gehen soll. Ist dann wieder Recherche angesagt...



Langsam... Die Peaks in der Houghtransformierten repäsentieren ja zunächst einmal nur Geraden die durch das Bild verlaufen und auf denen viele Pixel liegen. Das bedeutet leider noch nicht das es sich um im Bild verlaufende Linien handelt (wenn man eine Gerade durch ein verrauschtes Feld zieht kann man ja ebenfalls viele Pixel treffen, was sich dann als Peak in der Houghtransformierten äußert).

Was man nun weiter tun könnte (fällt mir so ad Hock ein, musst mal schauen in wie weit das sinnvolle Ergebnisse bringt):
- einen Graphen aufbauen. Die Schnittpunkte der gefundenen Geraden sind dabei (sofern sie innerhalb des Bildes liegen) die Knoten; die Kanten des Graphen ergeben sich dann freilich durch die Verbindungen der Schnittpunkte durch eine Gerade
- die Kanten des Graphen durchlaufen. Für jede Kante müsste man im Kantenbild überprüfen ob auf der Strecke hinreichend viele Pixel (hintereinander) gesetzt sind, ob dort also tatsächlich eine Linie zu sehen ist. Falls nicht: Kante verwerfen
- nun könnte man die Topologie des Graphen untersuchen, also sämtliche Teilgraphen mit 3 oder 4 Knoten extrahieren. Diese stellen dann Drei- bzw. Vierecke im Bild dar. (dabei muss man natürlich auch Teilgraphen berücksichtigen in denen weitere Kanten verlaufen; ein viereckiges Schild kann ja zum Beispiel durch über das Schild hängende Äste in mehrere n-Ecke "zerteilt" werden)

Mit den extrahierten Teilgraphen sollte man nun schon ganz gut Repräsentationen von dreieckigen bzw. viereckigen Formen im Bild gefunden haben. Jetzt könnte man eine Plausibilitätsprüfung vornehmen, ob es sich dabei auch wirklich um Schilder handeln kann. Also solche Tests wie:
- sind die gefundenen Formen konvex?
- Wie ist die Farbverteilung in dem Bildausschnitt (Histogramm)? Kommen mindestens 2 und höchstens 3 Farben vor? Und wenn ja - sind es "typische Schilderfarben"?


Erzähl doch bitte von Zeit zu Zeit mal wie du weiter vorgehst und welche Ergebnisse du erzielst hast (auch wenn es Fehlschlägen waren). Mich würde das sehr interessieren.


----------



## Faber (13. Feb 2012)

UIuiui, ich habe mir das etwas einfacher vorgestellt. Was ich mir überlegt hatte, klingt nicht so professionell wie dein Vorschlag. Ich danke dir dafür und werde mir den Link für meine Masterarbeit vormerken. Die braucht aber noch was… .
Was ich mir vorgestellt habe: Die Linien von der Hough-Transformation auf mein Binärbild zu übertragen und an den Schnittpunkten, den Start und den Endpunkt der Geraden zu finden, um anschließend die Fläche zu markieren. Ich habe ein paar Beispielbilder angehangen. Mit diesem Endergebnis würde ich zufrieden sein. 

Ich hätte da noch eine Frage zu den Akkumulator-Kurven. Diese sind nicht genau in einzelnen Zellen, sondern die Schnittpunkte sind über eine gewisse Umgebung verteilt. Die Ursache sind Rundungsfehler aufgrund der diskreten Koordinatengitter. Als simple Lösungsmöglichkeiten werden die Schwelloperation oder die Non-Maximum-Suppression(lokale Maxima) Variante vorgeschlagen. Wenn ich direkt die zwei Varianten hintereinander an meine Testbilder anwende, habe ich genau einen Koordinatenpunkt, der für den Schnittpunkt steht. Die Operationen finden direkt im Bild statt und nicht am HoughArray.
Zum Zeichnen der Linien ist es ja keine gute Idee ein Bild als Informationsquelle zu übergeben, sondern sollte lieber das Akkumulator-Array(mit den Winkelangaben und den Radien) übergeben. Das heißt, ich müsste die zwei oben genannten Varianten an mein Akkumulator-Array anwenden und diese dann der Klasse übergeben die, die Aufgabe hat, anhand des Winkels und der Länge des Radiusses eine Gerade zu zeichnen?

Ich kann ja ab und zu mal den aktuellen Codestand hochladen.


----------

