Punkte in einem Bild finden

[Freetree]

Hallo Leute

Ich muss für ein eigenes Projekt Punkte in einem Bild finden.
Dabei handelt es sich um ein IR-Bild, auf den etwa 3 unterschiedlich große helle Punkte (IR-LEDs) zu sehen sind.

Mein erster Ansatz war, dass ich das Bild einfach Zeile für Zeile durch gehe, und immer wenn ich auf einen Punkt treffe, der einen Hellichkeitswert übersteigt, in der Umgebung nach weiteren hellen Punkten zu suchen. Dann deren Durchschnittswerte bestimmen, damit ich den Mittelpunkt habe.

Das Problem dabei war, dass es, wenn ein Punkt zu groß war, ihn nicht ganz gefunden hat, da die Suchrange zu klein war, und ihn dann als zwei Punkte interpretiert hat.

Dafür ging das Verfahren relativ schnell, was auch wichtig ist, da ein Webcamstream analysiert werden soll, auf den möglichst in Echtzeit reagiert werden soll.

Mein zweiter Ansatz war also, dass ich wenn ich einen hellen Pixel gefunden habe, "Suchpixel" erstellt habe, die um sich herrum suchen, und dann weitere Suchpixel erstellen. Also ein rekrusiver aufruf.
Dadurch werden die Punkte uach schön erkannt, aber:

1. Dauert das sehr lange. Ich habe eine Verzögerung von fast 2-5 Sekunden.
2. Ich bekomme manchmal einen Stackoverflow Fehler, wenn die Punkte zu groß sind.

Habt ihr eine Idee für einen anderen Anstaz?

Wäre es gut, wenn ich die kritischen teile in C/C++ implementiere?

Mit freundlichen Grüßen

freetree

 

[Gucky]

Java ist mittlerweile so schnell, mit seinen Optimizern, dass der Geschwindigkeitsvorteil zu C/C++ fast nicht mehr vorhanden ist. Was noch etwas bringen könnte wäre Assembler, wenn du auf eine andere Sprache umsteigen willst.

Eine Möglichkeit wäre die, dass du nicht den ganzen Punkt findest sondern den Punkt umrandest und anhand dessen die Mitte findest.

 

[Androbin]

Also 2-5 Sekunden finde ich überhaupt nicht schlimm opcorn:

 

[DrZoidberg]

Du könntest es mit dem Floodfill Algorithmus versuchen.
Floodfill ? Wikipedia

Du musst auch nicht sämtliche Pixel betrachten. Wenn z.B. die Punkte jeweils 100 x 100 Pixel groß sind, kannst du das Bild auch erst einmal um den Faktor 20 verkleinern. Dann hast du insgesamt 400 mal weniger Pixel.

 

[Thallius]

über was für eine Bildgröße gesammt reden wir hier die durchsucht werden muss und wie groß sind denn die "grpßen" Punkte dann?

Gruß

Claus

 

[Ruzmanz]

Spricht etwas gegen eine fertige Library? Klingt zumindest so, als könnte man das Problem mit OpenCV (JavaCV) lösen.

GT's Blog: Object tracking in Java - detect position of colored spot in image

Habe das Beispiel vor 2 Wochen getestet und es läuft ganz gut. Da wartet man keine Sekunde für das Ergebnis. Wollte es für eine Echtzeitanalyse verwenden, aber soweit bin ich noch nicht gekommen und habe wahrscheinlich auch die nächsten zwei Wochen keine Zeit.

 

[Thallius]

Spricht etwas gegen eine fertige Library? Klingt zumindest so, als könnte man das Problem mit OpenCV (JavaCV) lösen.

GT's Blog: Object tracking in Java - detect position of colored spot in image

Habe das Beispiel vor 2 Wochen getestet und es läuft ganz gut. Da wartet man keine Sekunde für das Ergebnis. Wollte es für eine Echtzeitanalyse verwenden, aber soweit bin ich noch nicht gekommen und habe wahrscheinlich auch die nächsten zwei Wochen keine Zeit.

Naja das ist schon irgendwie mit Kanonen auf Spatzen schiessen (aber irgendwie ist das bei Java glaube ich normal)

Ich würde fast drauf tippen dass der TO die Pixel irgendwie mit ReadPixel ausliest oder sowas. Denn wenn ich direkt in einem Byte-Puffer arbeite ist das so unglaublich schnell das kann gar keine 2-5 sekunden dauern. Höchstens wenn es sich um ein 8MP Bild handelt und die Punkte dann das ganze Bild einnehmen oder sowas. Deshalb meine Fragen.

Gruß

Claus

 

[Freetree]

erst mal Danke für die Antowrten

Das Bild ist 640X480 Pixel groß und ein IR-Punkt kann dabei 10X10 Pixel groß sein, aber auch 100X100 je nachdem, wie weit die LED von der Kamera entfert ist.

Ich finde auch, dass 2-5 Sekunden nicht viel sind, aber es geht ja darum einen Rpbpter zu steuern. Und dabei sind 2-5 Sekunden Reaktionszeit zu viel! Der knallt mir sonst gegen die Wand.

Ich habe noch überlegt, ob ich einfach mehrere Threads nehme. Und mit eine Art Versionsnummer die Bilder dann zum Schluss wieder in die richtige reinfolge bringe.

Aber ich glaube ja, dass mein Algorithmuss einfach nicht optimal ist. Habe ihn auch in Abendstunden geschrieben.
Aber mir fällt nicht mehr viel dazu ein:
Hier ein paar Ausschnitte:

public ArrayList<Pixel> getAllIrPixelNew(Floor floor)
	{
		ArrayList<String> alreadySeen = new ArrayList<String>();
		ArrayList<Pixel> IrPixels = new ArrayList<>();
		
		int width  = image.getWidth();
		int height = image.getHeight();
		for(int x = 0 ; x < width;x++)
		{
			for(int y = 0 ; y < height;y++)
		    {
			    Color c = new Color(image.getRGB(x, y));
			    int hell = c.getBlue() + c.getGreen() + c.getRed();
			    if(hell > 680 && !alreadySeen.contains(x+"X"+y))
			    {
			    	ArrayList<Pixel> oneIrPoint = new ArrayList<Pixel>();
			    	SearchPixel sp = new SearchPixel(oneIrPoint,x,y,this.image,680,alreadySeen,floor);
			    	sp = null;
			    	System.out.println(IrPixels.size());
			    	System.out.println(alreadySeen.size());
			    	System.gc();
			    	Log.logMessage("Hallo");
			    	Pixel middlePixel = this.calcMiddle(oneIrPoint);
			    	IrPixels.add(middlePixel);
			    }
		    }
		}
		return IrPixels;
		
	}

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.util.ArrayList;

import de.nkpmedia.rccar.log.Log;

public class SearchPixel
{

	public SearchPixel(ArrayList<Pixel> oneIrPoint, int x, int y, BufferedImage image,int highValue, ArrayList<String> alreadySeen, Floor floor)
	{
//		floor.drawRedIrPicutrePoint(x,y);
//		Log.logMessage(x+";"+y);
		Color c;
		int hell;
		if(this.imageContains(x+1, y, image)){
			c = new Color(image.getRGB(x+1, y));
		    hell = c.getBlue() + c.getGreen() + c.getRed();
			if(hell > highValue && !alreadySeen.contains((x+1)+"X"+y ))
			{
				alreadySeen.add((x+1)+"X"+y);
				oneIrPoint.add(new Pixel((x+1),y));
				new SearchPixel(oneIrPoint, x+1, y, image, highValue,alreadySeen,floor);
			}
		}
		
		if(this.imageContains(x-1, y, image)){
			c = new Color(image.getRGB((x-1), y));
		    hell = c.getBlue() + c.getGreen() + c.getRed();
			if(hell > highValue && !alreadySeen.contains((x-1)+"X"+y))
			{
				alreadySeen.add((x-1)+"X"+y);
				oneIrPoint.add(new Pixel((x-1),y));
				new SearchPixel(oneIrPoint, x-1, y, image, highValue,alreadySeen,floor);
			}
		}
		
		if(this.imageContains(x, y+1, image)){
			c = new Color(image.getRGB(x, (y+1)));
		    hell = c.getBlue() + c.getGreen() + c.getRed();
			if(hell > highValue && !alreadySeen.contains(x+"X"+(y+1)))
			{
				alreadySeen.add(x+"X"+y+1);
				oneIrPoint.add(new Pixel(x,y+1));
				new SearchPixel(oneIrPoint, x, y+1, image, highValue,alreadySeen,floor);
			}
		}
		
		if(this.imageContains(x, y-1, image)){
			c = new Color(image.getRGB(x, y-1));
		    hell = c.getBlue() + c.getGreen() + c.getRed();
			if(hell > highValue && !alreadySeen.contains(x+"X"+(y-1)))
			{
				alreadySeen.add(x+"X"+(y-1));
				oneIrPoint.add(new Pixel(x,y-1));
				new SearchPixel(oneIrPoint, x, y-1, image, highValue,alreadySeen,floor);
			}
		}
		
	}
	private boolean imageContains(int x,int y,BufferedImage image)
	{
		if(0 <= x && x < image.getWidth())
		{
			if(0 <= y && y < image.getHeight())
			{
				return true;
			}
		}
		return false;
	}

}

Eine Idee war noch, dass ich nicht immer den Hellichkeitswert ausrechne, sondern ein Mal eine schwarz/weiß Map erstelle(über den Hellichkeitsgrenzwert), und dann nur noch damit arbeite.

Mit freundlichen Grüßen

Freetree

Edit:
Ich habe gerade mal die Wikiseite von Floodfill durchgelesen.
Das sieht zimlich nach meinem Ansatz aus.
Aber das iterative Flutfüllen schau ich mir noch mal an. das hilft zu mindest gegen meinen Stackoverflow

 

[Thallius]

Also das mit dem 1000x image.getColor() ist sicher Mist.

Acuh das ArrayList<Pixel> erzeugt schon einen irren Overhead. Warum liest du die RGB Werte nicht einfach in einen int[] Buffer und arbeitest dann damit? (UByte gibt es unter Java ja leider nicht. Du könntest aber auch einen Byte[] Buffer nehmen und nur bis 128 testen, wenn denn der Hintergrund immer dunkel genug ist)

Du solltest dann direkt auf den ImageBuffer zugreifen und die Helligkeit ausrechnen indem die einfach jeweils die 3 RGB Werte addierst. Wenn die Punkte nur weiß sind, kannst du sogar auch einfach nur einen der drei Werte nehmen und die anderen ignorieren.

Gruß

Claus

 

[Freetree]

Hallo Leute

Also: Ich habe jetzt meine Ideen implementiert.
Doch leider ist die Performenc immer noch nicht sehr gut. Bei kleinen Punkten habe ich eine Verzögerun von 1 Sekunde. Doch wenn die Punkt größer werden komme ich auf verzögerungen on 10 Sekunden. Und das ist zu viel.

Ich habe jetzt auch einen Threadpool eingebaut, damit mehrere Bilder gleichzeitig analysiert werden können.

public synchronized void newImage(BufferedImage image)
	{
		HashMap aufgaben = new HashMap();
		LinkedList parameter1 = new LinkedList();
		parameter1.add(this);
		aufgaben.put("getAllIrPixelNew", parameter1);
		aufgaben.put("getCrossPixel", null);
		
		ImageAnalyser ana = new ImageAnalyser(this,aufgaben);
		ana.versionNumber = this.nextVersionNumber;
		ana.setImage(image);
		
		imageAnalyserExecutor.execute(ana);
		this.nextVersionNumber++;
	}
	public synchronized void giveNewImageAnalyserData(HashMap back)
	{
		Integer versionNumber = (Integer)back.get("versionNumber");
		this.analyseQueue.put(versionNumber,back);
		for(int num = this.showenVersionNumber+1 ;null != this.analyseQueue.get(this.showenVersionNumber+1);num++)
		{
			HashMap nextAnalyseData = (HashMap) this.analyseQueue.get(num);
			if(nextAnalyseData != null)
			{
				this.analyseImageData(nextAnalyseData);
				this.analyseQueue.remove(num);
				this.showenVersionNumber++;
			}
		}
	}

public ArrayList<Pixel> getAllIrPixelNew()
	{
		ArrayList<String> alreadySeen = new ArrayList<String>();
		ArrayList<Pixel> IrPixels = new ArrayList<>();
		
		int width  = image.getWidth();
		int height = image.getHeight();
		int[][] lightImagevalues = new int[image.getWidth()][image.getHeight()];
		for(int x = 0 ; x < width;x++)
		{
			for(int y = 0 ; y < height;y++)
		    {
			    Color c = new Color(image.getRGB(x, y));
			    int hell = c.getBlue() + c.getGreen() + c.getRed();
			    lightImagevalues[x][y] = hell;
		    }
		}
		
		for(int x = 0 ; x < width;x++)
		{
			for(int y = 0 ; y < height;y++)
		    {
			    if(lightImagevalues[x][y] > 680 && !alreadySeen.contains(x+"X"+y))
			    {
			    	ArrayList<Pixel> oneIrPoint = new ArrayList<Pixel>();
			    	oneIrPoint.add(new Pixel((x),y));
			    	InterativeSearchPixel sp = new InterativeSearchPixel(oneIrPoint,x,y,this.image,680,alreadySeen,floor,lightImagevalues);
			    	sp = null;
			    	System.gc();
			    	Pixel middlePixel = this.calcMiddle(oneIrPoint);
			    	IrPixels.add(middlePixel);
			    }
		    }
		}
		return IrPixels;
		
	}

	public Pixel getCrossPixel()
	{
		int width  = image.getWidth();
		int height = image.getHeight();
		for(int x = 0 ; x < width;x++)
		{
			for(int y = 0 ; y < height;y++)
		    {
			    Color c = new Color(image.getRGB(x, y));
			    int hell = c.getBlue() + c.getGreen() + c.getRed();
			    if(hell > 680)
			    {
			    	Pixel tmpPixel = new Pixel(x,y);
			    	this.pixel .add(tmpPixel);
			    }
		    }
		}
		
		Pixel middlePixel= calcMiddle(this.pixel);
		if(middlePixel != null)
		{
			this.pixel.clear();
			return middlePixel;
		}
		
		return null;
	}
	
	private Pixel calcMiddle(ArrayList<Pixel> pixelList)
	{
		int XAnzahl = 0;
		int YAnzahl = 0;
		int XAll = 0;
		int YAll = 0;
		for(Pixel onePixel : pixelList)
		{
			XAnzahl++;
			YAnzahl++;
			XAll += onePixel.getX();
			YAll += onePixel.getY();
		}
		if(XAnzahl == 0 || YAnzahl == 0)
		{
			return null;
		}
		Pixel middlePixel = new Pixel(XAll / XAnzahl,YAll / YAnzahl);
		return middlePixel;
	}

	@Override
	public void run()
	{
		HashMap back = new HashMap();
		
		Iterator it = this.aufgaben.entrySet().iterator();
	    while (it.hasNext()) {
	        Map.Entry pairs = (Map.Entry)it.next();
	        switch((String)pairs.getKey())
	        {
	        	case "getCrossPixel":
	        		Pixel middlePixel = this.getCrossPixel();
	        		back.put("getCrossPixel", middlePixel);
	        		break;
	        	case "getAllIrPixelNew":
	        		ArrayList<Pixel> irPixels1 = this.getAllIrPixelNew();
	        		back.put("getAllIrPixelNew", irPixels1);
	        		break;
	        	case "getAllIrPixel":
	        		ArrayList<Pixel> irPixels2 = this.getAllIrPixel();
	        		back.put("getAllIrPixelNew", irPixels2);
	        		break;
	        		
	        }
	    }
	    back.put("analysedBufferedImage", this.image);
	    back.put("versionNumber", this.versionNumber);
	    this.floor.giveNewImageAnalyserData(back);
		
	}

public InterativeSearchPixel(ArrayList<Pixel> oneIrPoint, int x, int y, BufferedImage image,int highValue, ArrayList<String> alreadySeen, Floor floor, int[][] lightImagevalues)
	{
		Stack<Integer> stackX = new Stack<Integer>();
		Stack<Integer> stackY = new Stack<Integer>();
		stackX.push(x);
		stackY.push(y);
		while(!stackX.isEmpty())
		{
			int xOfStack = stackX.pop();
			int yOfStack = stackY.pop();
			if(lightImagevalues[xOfStack][yOfStack] >= highValue)
			{
				floor.drawRedIrPicutrePoint(xOfStack,yOfStack);
				alreadySeen.add(xOfStack+"X"+yOfStack);
				oneIrPoint.add(new Pixel((xOfStack+1),yOfStack));
				
				if(this.imageContains(xOfStack+1, yOfStack, image)){
					if(!alreadySeen.contains((xOfStack+1)+"X"+yOfStack ))
					{
						stackX.push(xOfStack+1);
						stackY.push(yOfStack);
					}
				}
				if(this.imageContains(xOfStack-1, yOfStack, image)){
					if(!alreadySeen.contains((xOfStack-1)+"X"+yOfStack ))
					{
						stackX.push(xOfStack-1);
						stackY.push(yOfStack);
					}
				}
				if(this.imageContains(xOfStack, yOfStack+1, image)){
					if(!alreadySeen.contains((xOfStack)+"X"+(yOfStack+1) ))
					{
						stackX.push(xOfStack);
						stackY.push(yOfStack + 1);
					}
				}
				if(this.imageContains(xOfStack, yOfStack-1, image)){
					if(!alreadySeen.contains((xOfStack)+"X"+(yOfStack-1) ))
					{
						stackX.push(xOfStack);
						stackY.push(yOfStack - 1);
					}
				}
				
			}
		}

Habt ihre noch eine Idee, was ich optimieren kann?

Oder habe ich einfach den falschen Ansatz?

Ich freue mich über jede Antowrt

 

[Ruzmanz]

Naja das ist schon irgendwie mit Kanonen auf Spatzen schiessen (aber irgendwie ist das bei Java glaube ich normal)

Ich würde fast drauf tippen dass der TO die Pixel irgendwie mit ReadPixel ausliest oder sowas.

Tipp mal weiter ... evtl. kommst du noch auf das tatsächliche Problem.