# Größte zusammenhängende Fläche erkennen



## Guest (9. Feb 2008)

Hi!

Ich möchte in einem Bild die größte zusammenhängende, sprich gleichfarbige, Fläche erkennen. Hat da jemand Code auf Lager oder Ideen? Ich hab es mal mit einem Flood-Fill-Algorithmus probiert, allerdings muss ich da ja sehr viele Pixel durchprobieren, bis ich die größte Fläche gefunden habe (und außerdem funktioniert mein Code irgendwie noch nicht richtig...).

LG


----------



## Ariol (9. Feb 2008)

Bei Wikipedia war noch ein Verweis auf "Boundary Fill":
http://en.wikipedia.org/wiki/Boundary_fill

Und hier ein Java-Beispiel für Flood-Fill.
http://www.codeuu.com/Flood_fill


----------



## Guest (9. Feb 2008)

Danke, das ist auch genau der Code, welchen ich verwende und einmal angewendet, funktioniert er auch. Nur leider bekomme ich nicht die größte Fläche raus...

Ich poste mal meinen (wirklich sehr schnell zusammengehackten- bitte Herzschrittmacher bereithalten ;-) ) Source- vielleicht findet ihr ja einen Fehler (was wirklich nervig ist, ist dass ich das Bild ständig neu von der Platte lesen muss, weil der FloodFill-Algorithmus das Original überschreibt, da WritableRaste scheinbar Referenz auf das Image darstellt):


```
package floodfill;

import java.awt.Rectangle;
import java.awt.image.WritableRaster;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import javax.swing.*;

public class Finder {

    public static void main(String[] args) throws IOException {    
	new Finder();
    }
    
    boolean[][] painted;
    private int[] curMaxPos = new int[2];
    private int curMax = 0;
    private int tmpcounter;
    int[] aux = new int[] {255,255,255,255};
    
    Finder() throws IOException {
	// This method ensures that all pixels have been loaded before returning
	BufferedImage bild = ImageIO.read(new File("irgendeinbild.png"));
	WritableRaster wr = bild.getRaster();
	
	Rectangle r = wr.getBounds();
	painted	= new boolean[r.width][r.height];
	
	// eventuell hier auch eine farbe, die im bild nie vorkommt, wählen.
	int[] fillBlack = {1, 255, 255, 255}; // first value: 0 = white, 1 = black
	int[] fillWhite = {0, 255, 255, 255};
	
	// find biggest fillable piece
	for (int y = 0; y < r.height; y++) {
	    for (int x = 0; x < r.width; x++) {
		if (!(painted[x][y]) && (checkPixel(wr.getPixel(x,y,aux),fillWhite)==0)) {
		   tmpcounter = 0;
		   //if (floodLoop(wr.createWritableChild(0, 0, r.width, r.height, 0, 0, null), x, y, fillBlack) > curMax) {
		   //wr = ImageIO.read(new File("irgendeinbild.png")).getRaster();
		   if (floodLoop(wr, x, y, fillBlack) > curMax) {
		       curMaxPos[0] = x;
		       curMaxPos[1] = y;
		   }
		}
	    }
	}
	
	// jetzt: painted komplett wieder auf false und wr neu erzeugen.
	// dann: fillLoop für curMaxPos[0], curMaxPos[1] ausführen
	// dann: schauen, welche positionen painted wurden
	// im loop alles weiß zeichnen, was nicht painted ist.
	System.out.println(curMaxPos[0]+", "+curMaxPos[1]);
	
	for (int y = 0; y < r.height; y++) {
	    for (int x = 0; x < r.width; x++) {
		painted[x][y] = false;
	    }
	}
	wr = ImageIO.read(new File("irgendeinbild.png")).getRaster();
	floodLoop(wr, curMaxPos[0], curMaxPos[1], fillBlack);
	
	WritableRaster wr2 = ImageIO.read(new File("irgendeinbild.png")).getRaster();
	for (int y = 0; y < r.height; y++) {
	    for (int x = 0; x < r.width; x++) {
		if (painted[x][y]) {
		    wr2.setPixel(x, y, fillBlack);
		} else {
		    wr2.setPixel(x, y, fillWhite);
		}
	    }
	}
		
	// remove border
	//floodLoop(wr, 0, 0, fill);
	BufferedImage scanned = new BufferedImage(bild.getColorModel(),wr2,bild.isAlphaPremultiplied(),null);

	JFrame frm = new JFrame("Finder");
	frm.setDefaultCloseOperation(JFrame. EXIT_ON_CLOSE);
	//frm.add(new JLabel(new ImageIcon(captcha)));
	frm.add(new JLabel(new ImageIcon(scanned)));
	frm.pack();
	frm.setVisible(true);
    }    
    
     int checkPixel(int[] oldPix, int[] newPix)
     {
       return (newPix[0] == oldPix[0] &&
       newPix[1] == oldPix[1]	&&
       newPix[2] == oldPix[2]  &&
       newPix[3] == oldPix[3] ? 1:0);
     }

     void floodLoop(WritableRaster raster, int x, int y, int[] fill, int[] old)
     {
       int fillL, fillR,i;
       int in_line=1;
       int[] aux =	{255,255,255,255};

       Rectangle d = raster.getBounds();

       // find left side, filling along the way
       fillL = fillR = x;
       while(in_line!=0)
       {
	 //int[] p = raster.getPixel(fillL,y,aux);     
	 raster.setPixel(fillL,y,fill);
	 painted[fillL][y] = true;
	 tmpcounter++;
	 fillL--;
	 in_line = (fillL < 0) ? 0 : checkPixel(raster.getPixel(fillL,y,aux),old);
       }
       fillL++;

       // find right side, filling along the way
       in_line = 1;
       while (in_line!=0)
       {
	 raster.setPixel(fillR,y,fill);
	 painted[fillR][y] = true;
	 tmpcounter++;
	 fillR++;
	 in_line = (fillR > d.width-1) ? 0 : checkPixel(raster.getPixel(fillR,y,aux),old);
       }
       fillR--;

       // look up and down
       for( i=fillL; i<=fillR; i++ )
       {
	 if ( y>0 && checkPixel(raster.getPixel(i,y-1,aux),old)!=0 )
	   floodLoop(raster,i,y-1,fill,old);
	 if ( y<d.height-1 && checkPixel(raster.getPixel(i,y+1,aux),old)!=0 )
	   floodLoop(raster,i,y+1,fill,old);
       }

     }

     // Initial method you must call
     int floodLoop(WritableRaster raster, int x, int y, int[] fill)
     {
       int[] aux = new int[] {255,255,255,255};

       // validation so we don't fall in an infinite loop trying to
       // paint in the same color
       if ( checkPixel(raster.getPixel(x,y,aux),fill)!=0 )
	 return 0;

       floodLoop(raster,x,y, fill,raster.getPixel(x,y,aux) );
       return tmpcounter;
     }

}
```


----------



## exi (10. Feb 2008)

Anonymous hat gesagt.:
			
		

> Hi!
> 
> Ich möchte in einem Bild die größte zusammenhängende, sprich gleichfarbige, Fläche erkennen. Hat da jemand Code auf Lager oder Ideen? Ich hab es mal mit einem Flood-Fill-Algorithmus probiert, allerdings muss ich da ja sehr viele Pixel durchprobieren, bis ich die größte Fläche gefunden habe (und außerdem funktioniert mein Code irgendwie noch nicht richtig...).
> 
> LG



tja, offenbar klappt es nicht mit fertigen Algorithmen. Und dein eigener Code sieht boah-bah-bombastisch aus. Wenn man da den Überblick verliert, dann ist das ganz normal. Meine Idee ist ein fundamentaler Neuanfang!
Zuerst liest du dein Bitmap ein und speicherst es als BufferedImage. Dann legst du dir zwei Listen an, eine speichert Farben, eine speichert BufferedImages.
Dann startest du eine doppelte Wiederholungsschleife über Bildweite und Bildhöhe 
Lese je ein Pixel ein. Bestimme seine Farbe. Kontrolliere ob diese bereits in der Farbliste enthalten ist. Falls nein, dann lege ein bufferedImage an. Schreibe das Pixel dort hinein. Vermerke die Farbe in der Farbliste. Falls ja, dann lasse dir den Index der Farbe aus der Farbliste geben. Nehme das BufferedImage Nr. Index. Schreibe dort das Pixel hinein. Next&next
Du hast jetzt eine Liste mit Bildern die jeweils den Ausschnitt in einer Farbe tragen. Aber jedes BufferedImage kann mehrere Teilbilder bergen. Hier mußt du also nochmals pixelweise durchgehen. Finde ein farbiges Pixel. Lösche es, untersuche die 8 Nachbarn ob sie dieselbe Farbe haben. Falls ja, dann sichere sie in einer Liste. Greife jeweils das erste aus der Liste, untersuche dessen Nachbarn auf Farbe, falls ja hänge die Pixel in die Liste. Lösche das Pixel. Und lasse bei jedem Löschvorgang einen Zähler mitlaufen. 
Wenn die Liste leer ist, dann hast du ein Teilbild identifiziert (und gelöscht). Suche nochmals ein Pixel in der Farbe. Falls eines da ist, dann gibt es ein weiteres Teilbild.

tschüs
exi


----------

