Wie dieses Muster am einfachsten erkennen?

123neu · 14. Apr 2021

Hallo, wie (also mit welchem Algorithmus) kann ich die Position dieses charakteristischen Musters auf dem Bildschirm:

am einfachsten erkennen, unabhängig der Größe, Position, Farbe der Kästchen, Ränder und Figurenstellung?

Danke 😊

mihe7 · 14. Apr 2021

Ich plädiere immer noch für Hough 🙂

123neu · 14. Apr 2021

Der hier: https://de.wikipedia.org/wiki/Hough-Transformation#Einfacher_Algorithmus ?

Wenn du mir einen Denkstubser gibst, dann zeichne ich deine Antwort als Lösung aus. 🙂

Das Gesamtbild hat eine Größe 1920x1080.

123neu · 14. Apr 2021

Dürfte ich mir hier: http://vase.essex.ac.uk/software/HoughTransform/HoughTransform.java.html herauspicken, was ich bräuchte?

* Java Implementation of the Hough Transform.<br />
* Used for finding straight lines in an image.<br />

das scheint das Gesuchte zu sein... Wenn es 9+9 Linien findet, die parallel verlaufen und den gleichen Abstand haben, müsste es doch das Muster sein?

mihe7 · 14. Apr 2021

Ja, den Ansatz hätte ich auch verfolgt.

123neu · 14. Apr 2021

@mihe7 kannst du mir sagen, was hier falsch ist?

Es berechnet "irgendwas"...

Ist meine drawLine()-Methode falsch?
Warum wird (im Orginalcode) getHighestValue() und getHoughArrayImage() nicht aufgerufen?

Hier ist der Spaß:

Java:

import java.awt.AWTException;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.Robot;
import java.awt.Toolkit;
import java.awt.image.BufferedImage;

import java.util.ArrayList;

import javax.swing.JFrame;

public class FindTemplate {
    public static class HoughLine {
        private double theta;
        private int r;

        public HoughLine(double theta, int r) {
            this.theta = theta;
            this.r = r;
        }

        public double getTheta() {
            return theta;
        }

        public void setTheta(double theta) {
            this.theta = theta;
        }

        public int getR() {
            return r;
        }

        public void setR(int r) {
            this.r = r;
        }

        public void drawLine(Graphics2D g2d, Color col, int w) {
            double startX = 0;
            double startY = r;
            double endX = startX + w * Math.sin(theta);
            double endY = startY + w * Math.cos(theta);
            g2d.setColor(col);
            g2d.drawLine((int) startX, (int) startY, (int) endX, (int) endY);
        }
    }

    public static void main(String[] args) throws AWTException, InterruptedException {
        Robot robot = new Robot();
        Rectangle rect = new Rectangle(Toolkit.getDefaultToolkit().getScreenSize());

        Thread.sleep(10_000);

        BufferedImage img = robot.createScreenCapture(rect);
        ArrayList<FindTemplate.HoughLine> lines = getLines(img, 30);

        JFrame f = new JFrame();
        Canvas c = new Canvas() {
            private static final long serialVersionUID = 1L;

            @Override
            public void paint(Graphics g) {
                Graphics2D g2d = (Graphics2D) g;
                for (HoughLine houghLine : lines) {
                    houghLine.drawLine(g2d, Color.red, this.getWidth());
                }
            }
        };
        f.add(c);
        f.setSize(rect.getSize());
        f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        f.setVisible(true);
    }

    public static ArrayList<HoughLine> getLines(BufferedImage img, int threshold) {
        // The size of the neighbourhood in which to search for other local maxima
        final int neighbourhoodSize = 4;

        // Calculate the maximum height the hough array needs to have
        final int houghHeight = (int) (Math.sqrt(2) * Math.max(img.getHeight(), img.getWidth())) / 2;

        // Double the height of the hough array to cope with negative r values
        final int doubleHeight = 2 * houghHeight;

        // How many discrete values of theta shall we check?
        final int maxTheta = 180;

        // Using maxTheta, work out the step
        final double thetaStep = Math.PI / maxTheta;

        // Create the hough array
        final int[][] houghArray = new int[maxTheta][doubleHeight];

        // Find edge points and vote in array
        final int centerX = img.getWidth() / 2;
        final int centerY = img.getHeight() / 2;

        // cache the values of sin and cos for faster processing
        final double[] sinCache = new double[maxTheta];
        final double[] cosCache = sinCache.clone();
        for (int t = 0; t < maxTheta; t++) {
            double realTheta = t * thetaStep;
            sinCache[t] = Math.sin(realTheta);
            cosCache[t] = Math.cos(realTheta);
        }
        // Now find edge points and update the hough array
        for (int x = 0; x < img.getWidth(); x++) {
            for (int y = 0; y < img.getHeight(); y++) {
                // Go through each value of theta
                for (int t = 0; t < maxTheta; t++) {
                    // Work out the r values for each theta step
                    int r = (int) (((x - centerX) * cosCache[t]) + ((y - centerY) * sinCache[t]));

                    // this copes with negative values of r
                    r += houghHeight;

                    if (r < 0 || r >= doubleHeight)
                        continue;

                    // Increment the hough array
                    houghArray[t][r]++;
                }
            }
        }

        // Initialise the vector of lines that we'll return
        ArrayList<HoughLine> lines = new ArrayList<HoughLine>(20);

        // Only proceed if the hough array is not empty
        // if (numPoints == 0) return lines;

        // Search for local peaks above threshold to draw
        for (int t = 0; t < maxTheta; t++) {
            loop: for (int r = neighbourhoodSize; r < doubleHeight - neighbourhoodSize; r++) {

                // Only consider points above threshold
                if (houghArray[t][r] > threshold) {

                    int peak = houghArray[t][r];

                    // Check that this peak is indeed the local maxima
                    for (int dx = -neighbourhoodSize; dx <= neighbourhoodSize; dx++) {
                        for (int dy = -neighbourhoodSize; dy <= neighbourhoodSize; dy++) {
                            int dt = t + dx;
                            int dr = r + dy;
                            if (dt < 0)
                                dt = dt + maxTheta;
                            else if (dt >= maxTheta)
                                dt = dt - maxTheta;
                            if (houghArray[dt][dr] > peak) {
                                // found a bigger point nearby, skip
                                continue loop;
                            }
                        }
                    }

                    // calculate the true value of theta
                    double theta = t * thetaStep;

                    // add the line to the vector
                    lines.add(new HoughLine(theta, r));

                }
            }
        }

        return lines;
    }
}

123neu · 14. Apr 2021

@mihe7 Ich erwarte eine Antwort asap 😅 Ansonsten wird es keine Auszeichnung geben 🤣

mihe7 · 14. Apr 2021

Du musst erstmal einen Edge-Detector drüberlaufen lassen.

123neu · 15. Apr 2021

Ja du hast recht, es fehlte nämlich noch:

Java:

// Find non-black pixels
if ((image.getRGB(x, y) & 0x000000ff) != 0) {

also

[CODE lang="java" highlight="112-113, 128"]import java.awt.AWTException;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.Robot;
import java.awt.Toolkit;
import java.awt.image.BufferedImage;

import java.util.ArrayList;

import javax.swing.JFrame;

public class FindTemplate {
public static class HoughLine {
private double theta;
private int r;

public HoughLine(double theta, int r) {
this.theta = theta;
this.r = r;
}

public double getTheta() {
return theta;
}

public void setTheta(double theta) {
this.theta = theta;
}

public int getR() {
return r;
}

public void setR(int r) {
this.r = r;
}

public void drawLine(Graphics2D g2d, Color col, int w) {
double startX = 0;
double startY = r;
double endX = startX + w * Math.sin(theta);
double endY = startY + w * Math.cos(theta);
g2d.setColor(col);
g2d.drawLine((int) startX, (int) startY, (int) endX, (int) endY);
}
}

public static void main(String[] args) throws AWTException, InterruptedException {
Robot robot = new Robot();
Rectangle rect = new Rectangle(Toolkit.getDefaultToolkit().getScreenSize());

Thread.sleep(10_000);

BufferedImage img = robot.createScreenCapture(rect);
ArrayList<FindTemplate.HoughLine> lines = getLines(img, 30);

JFrame f = new JFrame();
Canvas c = new Canvas() {
private static final long serialVersionUID = 1L;

@Override
public void paint(Graphics g) {
Graphics2D g2d = (Graphics2D) g;
for (HoughLine houghLine : lines) {
houghLine.drawLine(g2d, Color.red, this.getWidth());
}
}
};
f.add(c);
f.setSize(rect.getSize());
f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
f.setVisible(true);
}

public static ArrayList<HoughLine> getLines(BufferedImage img, int threshold) {
// The size of the neighbourhood in which to search for other local maxima
final int neighbourhoodSize = 4;

// Calculate the maximum height the hough array needs to have
final int houghHeight = (int) (Math.sqrt(2) * Math.max(img.getHeight(), img.getWidth())) / 2;

// Double the height of the hough array to cope with negative r values
final int doubleHeight = 2 * houghHeight;

// How many discrete values of theta shall we check?
final int maxTheta = 180;

// Using maxTheta, work out the step
final double thetaStep = Math.PI / maxTheta;

// Create the hough array
final int[][] houghArray = new int[maxTheta][doubleHeight];

// Find edge points and vote in array
final int centerX = img.getWidth() / 2;
final int centerY = img.getHeight() / 2;

// cache the values of sin and cos for faster processing
final double[] sinCache = new double[maxTheta];
final double[] cosCache = sinCache.clone();
for (int t = 0; t < maxTheta; t++) {
double realTheta = t * thetaStep;
sinCache[t] = Math.sin(realTheta);
cosCache[t] = Math.cos(realTheta);
}
// Now find edge points and update the hough array
for (int x = 0; x < img.getWidth(); x++) {
for (int y = 0; y < img.getHeight(); y++) {
// Find non-black pixels
if ((img.getRGB(x, y) & 0x000000ff) != 0) {
// Go through each value of theta
for (int t = 0; t < maxTheta; t++) {
// Work out the r values for each theta step
int r = (int) (((x - centerX) * cosCache[t]) + ((y - centerY) * sinCache[t]));

// this copes with negative values of r
r += houghHeight;

if (r < 0 || r >= doubleHeight)
continue;

// Increment the hough array
houghArray[t][r]++;
}
}
}
}

// Initialise the vector of lines that we'll return
ArrayList<HoughLine> lines = new ArrayList<HoughLine>(20);

// Only proceed if the hough array is not empty
// if (numPoints == 0) return lines;

// Search for local peaks above threshold to draw
for (int t = 0; t < maxTheta; t++) {
loop: for (int r = neighbourhoodSize; r < doubleHeight - neighbourhoodSize; r++) {

// Only consider points above threshold
if (houghArray[t][r] > threshold) {

int peak = houghArray[t][r];

// Check that this peak is indeed the local maxima
for (int dx = -neighbourhoodSize; dx <= neighbourhoodSize; dx++) {
for (int dy = -neighbourhoodSize; dy <= neighbourhoodSize; dy++) {
int dt = t + dx;
int dr = r + dy;
if (dt < 0)
dt = dt + maxTheta;
else if (dt >= maxTheta)
dt = dt - maxTheta;
if (houghArray[dt][dr] > peak) {
// found a bigger point nearby, skip
continue loop;
}
}
}

// calculate the true value of theta
double theta = t * thetaStep;

// add the line to the vector
lines.add(new HoughLine(theta, r));

}
}
}

return lines;
}
}[/CODE]

Das löst natürlich noch nicht das Problem mit dem "canny edge detection algorithm"... Wie es mit OpenCV geht, wird hier beschrieben: https://www.tutorialspoint.com/opencv-hough-line-transform-implementation-using-java

Falls das alles funktioniert ... müsste ich ja auch noch wissen, welche Linien zum Schachfeld gehören und wo das anfängt ...

😑

mihe7 · 15. Apr 2021

Im Hough-Raum hast Du ja den Winkel der Senkrechten auf die Linie und den Abstand zum Urprung gegeben (s. https://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm, Abb. 2). Im Array interessieren Dich also nur die 0-Grad und die 90-Grad Einträge mit den höchsten Werten. Das sind dann die vertikalen und horizontalen Linien.

Evtl. reicht hier schon eine einfache Kantenerkennung, schließlich ist es ja ein Screenshot und damit ohne großartiges Rauschen:

Java:

import java.awt.*;
import java.awt.color.*;
import java.awt.image.*;
import java.io.File;
import javax.imageio.*;

public class Test {

    private BufferedImage laplace(BufferedImage source) {
        ConvolveOp op = new ConvolveOp(new Kernel(3, 3, new float[] {
             0f,  -1f,  0f,
            -1f,   4f,  -1f,
             0f,  -1f,  0f
        }));

        return op.filter(source, null);
    }

    private BufferedImage grayscale(BufferedImage source) {
        ColorConvertOp op = new ColorConvertOp(
                ColorSpace.getInstance(ColorSpace.CS_GRAY), null);

        return op.filter(source, null);
    }

    public static void main(String[] args) throws Exception {
        GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment();
        GraphicsDevice screen = ge.getDefaultScreenDevice();
        GraphicsConfiguration config = screen.getDefaultConfiguration();
        Rectangle bounds = config.getBounds();

        Robot r = new Robot(screen);
        BufferedImage img = r.createScreenCapture(bounds);
        Test t = new Test();
        
        ImageIO.write(t.laplace(t.grayscale(img)), "jpg", new File("test.jpg"));
    }
}

Barista · 15. Apr 2021

123neu hat gesagt.:
Hallo, wie (also mit welchem Algorithmus) kann ich die Position dieses charakteristischen Musters auf dem Bildschirm:

Wenn die Größe, Farben und Helligkeiten fix sind, kannst Du einfach Punkt für Punkt vergleichen.

Bearbeitet:

Vergiss es, ich habe jetzt gesehen, dass unter dem Bild in Deinem Posting noch Text stand.

Barista · 15. Apr 2021

123neu hat gesagt.:
// Find non-black pixels if ((image.getRGB(x, y) & 0x000000ff) != 0)

Also ich habe letztens viel an einem OCR-Programm gearbeitet.

Schwarze Pixel habe ich folgendermassen erkannt:

[CODE lang="java" title="Detect black pixel"]public static boolean rgbToBlackBin(
final int rgb )
{
final int red = ( rgb >> 16 ) & 0xFF;

if ( red > 40 )
{
return false;
}

final int green = ( rgb >> 8 ) & 0xFF;

if ( green > 40 )
{
return false;
}

final int blue = rgb & 0xFF;

if ( blue > 40 )
{
return false;
}

return true;
}
[/CODE]

123neu · 15. Apr 2021

Danke mihe... Werde das später mal durchtesten. Eine Frage hab ich noch, weißt du wie man aus der Parameterform ( https://de.wikipedia.org/wiki/Parameterform#Darstellung ) zwei Geradenpunkte bekommt mit (x1, 0) und (x2, height) ? Also sprich vom kartesischen Koordinatensystem in das andere? 😉 Oder anders, wie ich die Linien einzeichnen kann.

@Barista Auch dir ein Danke, aber man braucht tatsächlich erst ein grayscale Bild ...

mihe7 · 15. Apr 2021

123neu hat gesagt.:
Oder anders, wie ich die Linien einzeichnen kann.

Lieber anders 🙂

x*cos(t) + y*sin(t) = r
<=> x = (r-y*sin(t)) / cos(t)

für y = 0 ist dann x = r/cos(t) und für y = height gilt x = (r-height*sin(t)) / cos(t)

Würde ich jetzt einfach mal sagen.

123neu · 15. Apr 2021

mihe7 hat gesagt.:
x*cos(t) + y*sin(t) = r
<=> x = (r-y*sin(t)) / cos(t)

für y = 0 ist dann x = r/cos(t) und für y = height gilt x = (r-height*sin(t)) / cos(t)

Wärst du so freundlich, und würdest das bitte erläutern?

Das hab ich bis jetzt...

Java:

        public void drawLine(Graphics2D g2d, Color col, int h) {
            double x1 = r * Math.sin(theta);
            double y1 = r * Math.cos(theta);
            double x2 = x1 + h * Math.sin(-theta);
            double y2 = y1 + h * Math.cos(-theta);
            // (x1,y1), (x2,y2) sind zwei Punkte auf der Geraden

//            double endX = startX + w * Math.sin(theta);
//            double endY = startY + w * Math.cos(theta);

            g2d.setColor(col);
            g2d.drawLine((int) ?, (int) 0, (int) ?, (int) h);
        }

theta ist der Alphawinkel, r ist die Länge, h steht für height.

mihe7 · 15. Apr 2021

123neu hat gesagt.:
Wärst du so freundlich, und würdest das bitte erläutern?

Örks, das dürfte falsch gewesen sein (=> Kreislinie) 🙂 Da muss ich später nochmal in mich gehen, bin momentan fertig...

123neu · 15. Apr 2021

mihe7 hat gesagt.:
bin momentan fertig

Hrhrhr, ich auch... mein Gehirn ist im Moment gebraten 😬

Aber ich danke dir vielmals schon jetzt!

mihe7 · 16. Apr 2021

So, also hat schon gestimmt - Winkel und Abstand sind ja konstant.

Es ist cos²(t) + sin²(t) = 1. Die Punkte (x,y) auf dem Rand eines Kreises mit Radius r sind durch x = r*cos(t) und y = r*sin(t) bestimmt, mit cos(t) = x/r und sin(t) = y/r folgt x/r*cos(t) + y/r*sin(t) = 1, multipliziert mit r gibt das x*cos(t)+y*sin(t) = r.

Löst man das nach y auf, erhält man y = (r-x*cos(t))/sin(t) = r/sin(t) - x*cos(t)/sin(t). Da r und t konstant sind, ist das die Gleichung einer Geraden, die durch den Punkt P=(r*cos(t), r*sin(t)) mit einer Steigung von -cos(t)/sin(t) verläuft und damit Senkrecht auf der durch OP gegebenen Strecke (mit Länge r) steht, deren Steigung r*sin(t)/r*cos(t) = sin(t)/cos(t) beträgt.

123neu · 16. Apr 2021

Ehrlich gesagt, hilft mir das überhaupt nicht weiter...

Kannst du diese Methode nicht einfach vervollständigen?

Java:

        public void drawLine(Graphics2D g2d, Color col, int w, int h) {
            double x1 = r * Math.sin(theta) - w / 2;
            double y1 = r * Math.cos(theta) - h / 2;
            double a = -x1 / Math.sin(-theta);
            double b = -y1 / Math.cos(-theta);
            double x2 = x1 + a * Math.sin(-theta);
            double y2 = y1 + b * Math.cos(-theta);

            g2d.setColor(col);
            g2d.drawLine((int) x2, (int) y2, (int) w, (int) h);
        }

Die Herleitung ist ja schön und gut, aber die hilft mir 0️⃣0️⃣0️⃣0️⃣

123neu · 16. Apr 2021

Dein Filter scheint aber zu funktionieren:

Java:

    BufferedImage img2 = new ConvolveOp(new Kernel(3, 3, new float[] { 0f, -1f, 0f, -1f, 4f, -1f, 0f, -1f, 0f })).filter(new ColorConvertOp(ColorSpace.getInstance(ColorSpace.CS_GRAY), null).filter(img, null), null);
    try {
        ImageIO.write(img2, "png", new File("testimg1.png"));
    } catch (IOException e) {
        e.printStackTrace();
    }

mihe7 · 16. Apr 2021

123neu hat gesagt.:
Ehrlich gesagt, hilft mir das überhaupt nicht weiter...

Ich hätte jetzt einfach mal

Java:

int y(int x) {
   return (int)((r - x*Math.cos(theta)) / Math.sin(theta));
}

Code:

g.drawLine(0, y(0), width, y(width));

probiert.

123neu · 16. Apr 2021

mihe7 hat gesagt.:
g.drawLine(0, y(0),

Aber nicht jede Linie beginnt bei x=0 (denke an horizontale oder vertikale Linien...)

mihe7 hat gesagt.:
width, y(width)

Und nicht jede Linie geht bis ganz nach unten

Diese Parameterform der Geraden ist einfach scheiße...

mihe7 · 16. Apr 2021

Ja vertikale Geraden sind speziell. Ansonsten enthält jede Gerade einen Punkt bei x=0, und (width, y(width)) bedeutet ja nicht, dass die Gerade bis "ganz nach unten" geht.

Beispiel: 45°, Abstand 10. Box-Breite 20. y(0) = 14.142135623730951, y(20) = -5.857864376269051

Nachtrag: für horizontale und vertikale Geraden kannst Du ja direkt r nehmen.

123neu · 16. Apr 2021

mihe7 hat gesagt.:
int y(int x) { return (int)((r - x*Math.cos(theta)) / Math.sin(theta)); }

Das funktioniert leider nicht...

Hast du bei der Transformation hieran gedacht?

mihe7 · 16. Apr 2021

Dann zieh es halt von der Bildhöhe ab.

123neu · 16. Apr 2021

mihe7 hat gesagt.:
Dann zieh es halt von der Bildhöhe ab.

Hab schon alles durchprobiert, aber ich komme da auf keinen grünen Zweig.

mihe7 · 16. Apr 2021

Kannst Du mal die komplette Klasse posten?

123neu · 16. Apr 2021

Java:

import java.awt.AWTException;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.Robot;
import java.awt.Toolkit;
import java.awt.color.ColorSpace;
import java.awt.image.BufferedImage;
import java.awt.image.ColorConvertOp;
import java.awt.image.ConvolveOp;
import java.awt.image.Kernel;

import java.io.File;
import java.io.IOException;

import java.util.ArrayList;

import javax.imageio.ImageIO;
import javax.swing.JFrame;

public class FindTemplate {
    public static class HoughLine {
        private double theta;
        private int r;

        public HoughLine(double theta, int r) {
            this.theta = theta;
            this.r = r;
        }

        public double getTheta() {
            return theta;
        }

        public void setTheta(double theta) {
            this.theta = theta;
        }

        public int getR() {
            return r;
        }

        public void setR(int r) {
            this.r = r;
        }

        private int y(int x) {
            return (int) ((r - x * Math.cos(theta)) / Math.sin(theta));
        }

        public void drawLine(Graphics2D g2d, Color col, int w, int h) {
            double x1 = r * Math.sin(theta) - h / 2;
            double y1 = r * Math.cos(theta) - h / 2;
//            double a = -x1 / -Math.sin(t);
//            double b = -y1 / -Math.cos(t);
            double x2 = x1 + 10 * -Math.sin(theta);
            double y2 = y1 + 10 * -Math.cos(theta);

            g2d.setColor(col);
            g2d.drawLine((int) x1, (int) y1, (int) x2, (int) y2);
        }
    }

    public static void main(String[] args) throws AWTException, InterruptedException {
        Robot robot = new Robot();
        Rectangle rect = new Rectangle(Toolkit.getDefaultToolkit().getScreenSize());

        Thread.sleep(10_000);

        BufferedImage img = robot.createScreenCapture(rect);
        ArrayList<FindTemplate.HoughLine> lines = getLines(img, 175);

        JFrame f = new JFrame();
        Canvas c = new Canvas() {
            private static final long serialVersionUID = 1L;

            @Override
            public void paint(Graphics g) {
                Graphics2D g2d = (Graphics2D) g;
                for (HoughLine houghLine : lines) {
                    houghLine.drawLine(g2d, Color.red, this.getHeight(), this.getHeight());
                }
            }
        };
        f.add(c);
        f.setSize(rect.getSize());
        f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        f.setVisible(true);
    }

    public static ArrayList<HoughLine> getLines(BufferedImage img, int threshold) {
        // The size of the neighbourhood in which to search for other local maxima
        final int neighbourhoodSize = 4;

        // Calculate the maximum height the hough array needs to have
        final int houghHeight = (int) (Math.sqrt(2) * Math.max(img.getHeight(), img.getWidth())) / 2;

        // Double the height of the hough array to cope with negative r values
        final int doubleHeight = 2 * houghHeight;

        // How many discrete values of theta shall we check?
        final int maxTheta = 180;

        // Using maxTheta, work out the step
        final double thetaStep = Math.PI / maxTheta;

        // Create the hough array
        final int[][] houghArray = new int[maxTheta][doubleHeight];

        // Find edge points and vote in array
        final int centerX = img.getWidth() / 2;
        final int centerY = img.getHeight() / 2;

        // cache the values of sin and cos for faster processing
        final double[] sinCache = new double[maxTheta];
        final double[] cosCache = sinCache.clone();
        for (int t = 0; t < maxTheta; t++) {
            double realTheta = t * thetaStep;
            sinCache[t] = Math.sin(realTheta);
            cosCache[t] = Math.cos(realTheta);
        }

        BufferedImage img2 = new ConvolveOp(new Kernel(3, 3, new float[] { 0f, -1f, 0f, -1f, 4f, -1f, 0f, -1f, 0f })).filter(new ColorConvertOp(ColorSpace.getInstance(ColorSpace.CS_GRAY), null).filter(img, null), null);
        try {
            ImageIO.write(img2, "png", new File("testimg1.png"));
        } catch (IOException e) {
            e.printStackTrace();
        }

        // Now find edge points and update the hough array
        for (int x = 0; x < img2.getWidth(); x++) {
            for (int y = 0; y < img2.getHeight(); y++) {
                // Find non-black pixels
                if ((img2.getRGB(x, y) & 0x000000ff) != 0) {
                    // Go through each value of theta
                    for (int t = 0; t < maxTheta; t++) {
                        // Work out the r values for each theta step
                        int r = (int) (((x - centerX) * cosCache[t]) + ((y - centerY) * sinCache[t]));

                        // this copes with negative values of r
                        r += houghHeight;

                        if (r < 0 || r >= doubleHeight)
                            continue;

                        // Increment the hough array
                        houghArray[t][r]++;
                    }
                }
            }
        }

        // Initialise the vector of lines that we'll return
        ArrayList<HoughLine> lines = new ArrayList<HoughLine>(20);

        // Only proceed if the hough array is not empty
        // if (numPoints == 0) return lines;

        // Search for local peaks above threshold to draw
        for (int t = 0; t < maxTheta; t++) {
            loop: for (int r = neighbourhoodSize; r < doubleHeight - neighbourhoodSize; r++) {

                // Only consider points above threshold
                if (houghArray[t][r] > threshold) {

                    int peak = houghArray[t][r];

                    // Check that this peak is indeed the local maxima
                    for (int dx = -neighbourhoodSize; dx <= neighbourhoodSize; dx++) {
                        for (int dy = -neighbourhoodSize; dy <= neighbourhoodSize; dy++) {
                            int dt = t + dx;
                            int dr = r + dy;
                            if (dt < 0)
                                dt = dt + maxTheta;
                            else if (dt >= maxTheta)
                                dt = dt - maxTheta;
                            if (houghArray[dt][dr] > peak) {
                                // found a bigger point nearby, skip
                                continue loop;
                            }
                        }
                    }

                    // calculate the true value of theta
                    double theta = t * thetaStep;

                    // add the line to the vector
                    lines.add(new HoughLine(theta, r));

                }
            }
        }

        return lines;
    }
}

mihe7 · 16. Apr 2021

OK, schau ich mir später mal an.

123neu · 16. Apr 2021

mihe7 hat gesagt.:
OK, schau ich mir später mal an.

Am besten, direkt mit einer Lösung. 😉

Edit: Mir fällt gerade auf, meine Zeichnung in #24 dürfte falsch sein ... 🙁

mihe7 · 16. Apr 2021

Gepfuscht:

Java:

import java.awt.AWTException;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.Robot;
import java.awt.Toolkit;
import java.awt.color.ColorSpace;
import java.awt.image.BufferedImage;
import java.awt.image.ColorConvertOp;
import java.awt.image.ConvolveOp;
import java.awt.image.Kernel;

import java.io.File;
import java.io.IOException;

import java.util.ArrayList;

import javax.imageio.ImageIO;
import javax.swing.JFrame;

public class FindTemplate {
    public static class HoughLine {
        private double theta;
        private int r;

        public HoughLine(double theta, int r) {
            this.theta = theta;
            this.r = r;
        }

        public double getTheta() {
            return theta;
        }

        public void setTheta(double theta) {
            this.theta = theta;
        }

        public int getR() {
            return r;
        }

        public void setR(int r) {
            this.r = r;
        }

        private int y(int x, int realR) {
            return (int) ((realR - x * Math.cos(theta)) / Math.sin(theta));
        }

        public void drawLine(Graphics2D g2d, Color col, int w, int h) {
            final int houghHeight = (int) (Math.sqrt(2) * Math.max(w, h)) / 2;
            int realR = r - houghHeight;
            double x1, y1, x2, y2;

            if (theta != 0.0) {
                x1 = 0;
                y1 = h/2 + y(0, realR);
                x2 = w;
                y2 = h/2 + y(w, realR);
            } else {
                System.out.println("r" +  r);                
                
                x1 = x2 = w/2 + realR;
                y1 = 0;
                y2 = h;
            }

            g2d.setColor(col);
            g2d.drawLine((int) x1, (int) y1, (int) x2, (int) y2);
        }

        public String toString() {
            return String.format("(\u03b8,r)=(%f,%d)", theta, r);
        }
        public String toString(int width, int height) {
            final int houghHeight = (int) (Math.sqrt(2) * Math.max(width, height)) / 2;
            return String.format("(\u03b8,r)=(%f,%d)", theta, r - houghHeight);
        }
    }

    public static void main(String[] args) throws Exception {
/*
        Robot robot = new Robot();
        Rectangle rect = new Rectangle(Toolkit.getDefaultToolkit().getScreenSize());

        Thread.sleep(10_000);

        BufferedImage img = robot.createScreenCapture(rect);

        Rectangle rect = new Rectangle(500, 500);
        BufferedImage img = new BufferedImage(rect.width, rect.height, BufferedImage.TYPE_INT_RGB);
        Graphics g = img.createGraphics();
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, img.getWidth(), img.getHeight());
        int size = 200;
        g.setColor(Color.WHITE);
        g.fillRect((rect.width - size)/2, (rect.height - size)/2, size, size);
        g.setColor(Color.YELLOW);
        g.fillRect((rect.width - size)/2 - 59, (rect.height - size)/2 - 50, size, size);
        g.dispose();
*/
        BufferedImage img = ImageIO.read(new File("testinput.png"));
        Rectangle rect = new Rectangle(0, 0, img.getWidth(), img.getHeight());

        ArrayList<FindTemplate.HoughLine> lines = getLines(img, 30);
        BufferedImage img2 = new BufferedImage(img.getWidth(), img.getHeight(), BufferedImage.TYPE_INT_RGB);
        Graphics g = img2.createGraphics();
        Graphics2D g2d = (Graphics2D) g;
        g.drawImage(img, 0, 0, null);
        for (HoughLine houghLine : lines) {
            houghLine.drawLine(g2d, Color.red, rect.width, rect.height);
        }
        g.dispose();

        ImageIO.write(img2, "png", new File("testoutput.png"));

        JFrame f = new JFrame();
        Canvas c = new Canvas() {
            private static final long serialVersionUID = 1L;

            @Override
            public void paint(Graphics g) {
                g.drawImage(img2, 0, 0, null);
            }
        };
        f.add(c);
        f.setSize(rect.getSize());
        f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        f.setVisible(true);
    }

    public static ArrayList<HoughLine> getLines(BufferedImage img, int thresholdPct) {
        // The size of the neighbourhood in which to search for other local maxima
        final int neighbourhoodSize = 4;

        // Calculate the maximum height the hough array needs to have
        final int houghHeight = (int) (Math.sqrt(2) * Math.max(img.getHeight(), img.getWidth())) / 2;

        // Double the height of the hough array to cope with negative r values
        final int doubleHeight = 2 * houghHeight;

        // How many discrete values of theta shall we check?
        final int maxTheta = 180;

        // Using maxTheta, work out the step
        final double thetaStep = Math.PI / maxTheta;

        // Create the hough array
        final int[][] houghArray = new int[maxTheta][doubleHeight];

        // Find edge points and vote in array
        final int centerX = img.getWidth() / 2;
        final int centerY = img.getHeight() / 2;

        // cache the values of sin and cos for faster processing
        final double[] sinCache = new double[maxTheta];
        final double[] cosCache = sinCache.clone();
        for (int t = 0; t < maxTheta; t++) {
            double realTheta = t * thetaStep;
            sinCache[t] = Math.sin(realTheta);
            cosCache[t] = Math.cos(realTheta);
        }

        BufferedImage img2 = new ConvolveOp(new Kernel(3, 3, new float[] { 0f, -1f, 0f, -1f, 4f, -1f, 0f, -1f, 0f })).filter(new ColorConvertOp(ColorSpace.getInstance(ColorSpace.CS_GRAY), null).filter(img, null), null);
        try {
            ImageIO.write(img2, "png", new File("testimg1.png"));
        } catch (IOException e) {
            e.printStackTrace();
        }

        // Now find edge points and update the hough array
        int maxIntensity = 0;
        for (int x = 0; x < img2.getWidth(); x++) {
            for (int y = 0; y < img2.getHeight(); y++) {
                // Find non-black pixels
                if ((img2.getRGB(x, y) & 0x000000ff) != 0) {
                    // Go through each value of theta
                    for (int t = 0; t < maxTheta; t++) {
                        // Work out the r values for each theta step
                        int r = (int) (((x - centerX) * cosCache[t]) + ((y - centerY) * sinCache[t]));

                        // this copes with negative values of r
                        r += houghHeight;

                        if (r < 0 || r >= doubleHeight)
                            continue;

                        // Increment the hough array
                        houghArray[t][r]++;
                        maxIntensity = Math.max(maxIntensity, houghArray[t][r]);
                    }
                }
            }
        }

        BufferedImage img3 = new BufferedImage(maxTheta, doubleHeight, BufferedImage.TYPE_INT_RGB);
        for (int y = 0; y < doubleHeight; y++) {
            for (int x = 0; x < maxTheta; x++) {
                int intensity = (int)(houghArray[x][y] * 255L / maxIntensity);
                int rgb = intensity << 16 | intensity << 8 | intensity;
                img3.setRGB(x, y, rgb);
            }
        }
        try {
            ImageIO.write(img3, "png", new File("testimg2.png"));
        } catch (IOException e) {
            e.printStackTrace();
        }
        

        // Initialise the vector of lines that we'll return
        ArrayList<HoughLine> lines = new ArrayList<HoughLine>(20);

        // Only proceed if the hough array is not empty
        // if (numPoints == 0) return lines;
        double threshold = maxIntensity * thresholdPct / 100.0;

        // Search for local peaks above threshold to draw
        for (int t = 0; t < maxTheta; t++) {
            loop: for (int r = neighbourhoodSize; r < doubleHeight - neighbourhoodSize; r++) {

                // Only consider points above threshold
                if (houghArray[t][r] > threshold) {

                    int peak = houghArray[t][r];

                    // Check that this peak is indeed the local maxima
                    for (int dx = -neighbourhoodSize; dx <= neighbourhoodSize; dx++) {
                        for (int dy = -neighbourhoodSize; dy <= neighbourhoodSize; dy++) {
                            int dt = t + dx;
                            int dr = r + dy;
                            if (dt < 0)
                                dt = dt + maxTheta;
                            else if (dt >= maxTheta)
                                dt = dt - maxTheta;
                            if (houghArray[dt][dr] > peak) {
                                // found a bigger point nearby, skip
                                continue loop;
                            }
                        }
                    }

                    // calculate the true value of theta
                    double theta = t * thetaStep;
                    if (t < 5 || t > 88 && t < 92) {
                        lines.add(new HoughLine(theta, r));
                    }

                }
            }
        }

        return lines;
    }
}

Ergebnis

:

Allerdings war Dein Bild der Input, das nochmal durch den Kantendetektor ging. Evtl. sollte man doch mal Canny probieren...

123neu · 16. Apr 2021

Danke dir @mihe7 😊 Das bringt mich schon einen riesigen Schritt weiter...

Ja, ich hab mir schon fast gedacht dass die Ränder die hier eher weiß sind problematisch werden könnten... Eventuell invertieren? 🙂

Oder ich lass das Ding auf Grau anspringen... 🤔

Edit: Du kannst auch noch mit dem Threshold rumspielen.

mihe7 · 16. Apr 2021

Vor ein paar Jahren habe ich die Hough-Lines dazu verwendet, eine Grafik waagerecht auszurichten. Das hatte ich wesentlich einfacher in Erinnerung.

Wie dieses Muster am einfachsten erkennen?

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Top Contributor

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Ähnliche Themen