Bilder Doubletten erkennen

Forum for developers

Bilder Doubletten erkennen

Beitragvon Lotus » Fr Jan 24, 2014 10:14 pm

Man kann Momente von Bildern berechnen, die unter anderem invariant gegen Skalierung sind, d.h. wenn ein Bild in der Größe verändert wird, ändert sich die Zahl nicht.
https://en.wikipedia.org/wiki/Image_moment

Ich habe das einfach mal programmiert. Jetzt habe ich 2 Zahlen (= Merkmale).
Was kann YaCy nun damit anfangen?
Ich habe die vorhandenen Parser angesehen, die speichern ihre Informationen offenbar in Prosa-Text in vorhandene Text-Felder in Solr.
Um Doubletten auszusortieren bräuchte man eine Suche nach "so ähnlich wie". Beispielsweise über eine Sortierung der Merkmale und eine Clusterbildung (= Klassifizierung) nahe beieinander liegender. Einfacher Ansatz: Zurückweisungssschwelle ab erstem Element je Klasse.
Dass sie relativ ähnlich sein müssen, ist auch schon über die Vorauswahl durch die Tatsache, dass sie bei der Suche anhand eines Wortes gefunden wurden bekannt.

Eigentlich auch eine ziemlich coole Sache:
Man könnte ein Bild zu YaCy hochladen, und dann finden lassen, wo es überall verwendet wurde. Komisch, dass Google das nicht kann.

Leider schluckt das Bild einlesen und Pixel extrahieren in Java einige Performance. Ich habe es auch nicht schneller hinbekommen. Die Zeiten unten sind von einem Athlon X2 6000+ (3.1Ghz) mit 64 Bit Java. Das erste Bild ist nur eine Dummy-Messung damit Java den Code lädt.

Code: Alles auswählen
import java.awt.image.BufferedImage;
import java.io.File;

import javax.imageio.ImageIO;


public class ImageParser {

   public static void main(String[] args) {

      File f[] = {
            new File("/mnt/Daten/dev/eclipse/testproj/kfz3.png"),
            new File("/mnt/Daten/dev/eclipse/testproj/kfz1.png"),
            new File("/mnt/Daten/dev/eclipse/testproj/kfz2.png"),
            new File("/mnt/Daten/dev/eclipse/testproj/kfz3.png"),
            new File("/mnt/Daten/dev/eclipse/testproj/kfz4.png"),
            new File("/mnt/Daten/dev/eclipse/testproj/kfz5.png")
      };

      for (int i = 0; i < f.length; i++)
      {
         System.out.println("Bild " + i);
         calculateMoments(f[i]);
         System.out.println("");
      }

   }

   private static void calculateMoments(File f) {
      long t = System.currentTimeMillis();

      BufferedImage img = null;
      try {
         img = ImageIO.read(f);
      } catch (Exception e) {
         System.out.println(e.getMessage());
         e.printStackTrace();
      }
      if (img != null) {

         System.out.println("Zeit (0): " + (System.currentTimeMillis() - t));

         final int xmax = img.getWidth();
         final int ymax = img.getHeight();
         final int pic[][] = new int[xmax][ymax];


         System.out.println("xmax: " + xmax + " ymax: " + ymax + ", " + (xmax*ymax*32/8/1024) + "kb");

         // moments
         long m00 = 0;
         long m10 = 0;
         long m01 = 0;

         // get raw image
         int raw[] = img.getRGB(0, 0, xmax, ymax, null, 0, xmax);

         System.out.println("Zeit (1): " + (System.currentTimeMillis() - t));

         for (int x = 0; x < xmax; x++) {
            for (int y = 0; y < ymax; y++) {
               //int pixel = img.getRGB(x, y);
               final int pixel = raw[y * xmax + x];
               //int alpha = (pixel >> 24) & 0xff;
               final int red   = (pixel >> 16) & 0xff;
               final int green = (pixel >>  8) & 0xff;
               final int blue  = (pixel      ) & 0xff;
               //int grey = (int) Math.sqrt((double) (red*red + green*green + blue*blue));
               final int grey = (red + green + blue) / 3;
               pic[x][y] = grey;
               m00 += grey;
               m10 += grey*x;
               m01 += grey*y;
               //System.out.print("" + x + "." + y + " " + alpha + " " + red + " " + green + " " + blue + "\n");
            }
         }
         System.out.println("Zeit (2): " + (System.currentTimeMillis() - t));

         // center of mass
         final long xs = m10/m00;
         final long ys = m01/m00;
         //System.out.println("xs=" + xs + " ys=" + ys);

         // central moments
         long u00 = m00;
         long u20 = 0;
         long u02 = 0;
         long u11 = 0;

         for (int x = 0; x < xmax; x++) {
            for (int y = 0; y < ymax; y++) {
               long dx = x - xs;
               long dy = y - ys;
               u20 += pic[x][y]*dx*dx;
               u02 += pic[x][y]*dy*dy;
               u11 += pic[x][y]*dx*dy;
            }
         }

         // normalized central moments
         double n20 = (double) u20 / (u00 * u00);
         double n02 = (double) u02 / (u00 * u00);
         double n11 = (double) u11 / (u00 * u00);

         // Hu invariant moments to translation, scale, rotation
         double i1 = n20 + n02;
         double i2 = (n20 - n02)*(n20 - n02) + 4*n11*n11;

         System.out.println("i1=" + i1);
         System.out.println("i2=" + i2);

         //System.out.println("u20=" + u20 + " u02=" + u02 + " u20+u02=" + (u20+u02));
         //System.out.println("n20=" + n20 + " n02=" + n02 + " n20+n02=" + (n20+n02));



      }

      System.out.println("Zeit (3): " + (System.currentTimeMillis() - t));
   }

}

Code: Alles auswählen
Bild 0
Zeit (0): 158
xmax: 200 ymax: 150, 117kb
Zeit (1): 257
Zeit (2): 351
i1=0.001496248385046892
i2=2.8157097923746405E-7
Zeit (3): 366

Bild 1
Zeit (0): 747
xmax: 3072 ymax: 2304, 27648kb
Zeit (1): 1353
Zeit (2): 1869
i1=0.0014866404030748307
i2=2.7724108030034244E-7
Zeit (3): 1900

Bild 2
Zeit (0): 57
xmax: 800 ymax: 600, 1875kb
Zeit (1): 96
Zeit (2): 102
i1=0.0014912386304618134
i2=2.7956183263973203E-7
Zeit (3): 106

Bild 3
Zeit (0): 3
xmax: 200 ymax: 150, 117kb
Zeit (1): 6
Zeit (2): 7
i1=0.001496248385046892
i2=2.8157097923746405E-7
Zeit (3): 8

Bild 4
Zeit (0): 24
xmax: 800 ymax: 600, 1875kb
Zeit (1): 67
Zeit (2): 73
i1=0.001496248385046892
i2=2.8157097923746405E-7
Zeit (3): 76

Bild 5
Zeit (0): 28
xmax: 800 ymax: 600, 1875kb
Zeit (1): 76
Zeit (2): 82
i1=0.0015016224895486679
i2=2.808167327318427E-7
Zeit (3): 85

Lotus
 
Beiträge: 1699
Registriert: Mi Jun 27, 2007 3:33 pm
Wohnort: Hamburg

Re: Bilder Doubletten erkennen

Beitragvon David » Mo Feb 03, 2014 9:49 am

Wow, das wäre cool, wenn diese Funktion mal in Yacy implementiert werden würde.

Lotus hat geschrieben:Man könnte ein Bild zu YaCy hochladen, und dann finden lassen, wo es überall verwendet wurde. Komisch, dass Google das nicht kann.

Google kann das schon ziemlich lang. Wenn man auf die Bildersuchmaske wechselt, hat es ganz rechts im Eingabefeld für den Suchbegriff, ein kleines Fotoapparat-Symbol, das man anklicken kann.
David
 
Beiträge: 170
Registriert: Di Mär 05, 2013 5:35 pm

Re: Bilder Doubletten erkennen

Beitragvon Low012 » Di Feb 04, 2014 1:24 pm

Lotus hat geschrieben:Man kann Momente von Bildern berechnen, die unter anderem invariant gegen Skalierung sind, d.h. wenn ein Bild in der Größe verändert wird, ändert sich die Zahl nicht.


Wenn die Momente sowieso invariant gegenüber Skalierung sind, kann man die Bilder doch auch erst (auf eine geeignete Größe, was auch immer das ist) verkleinern und dann die Momente berechnen. Ausreißer wie die 1900ms bei Bild 1 sollte es dann nicht mehr geben.

Ich hatte vor einiger Zeit mal einen etwas naiven Ansatz verfolgt, bin dann aber auf Probleme gestoßen, hatte dann keine Zeit mehr und habe den Kram ganz vergessen: viewtopic.php?f=8&t=3138

Dummerweise habe ich den Quellcode damals nicht angehängt, der müsste aber noch irgendwo im Backup eines Backups meiner Code-Müllhalde vor sich hin schimmeln. Das Skalieren ging, wenn ich mich richtig erinnere, recht flott. Ich muss den Kram aber nochmal ausgraben, um zu schauen, ob das wirklich so war.
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm

Re: Bilder Doubletten erkennen

Beitragvon kilian » Mi Feb 05, 2014 4:41 pm

Ist eine externe C-Bibliothek/Assembler-Programm keine Option?
kilian
 
Beiträge: 79
Registriert: Mi Feb 23, 2011 11:34 am
Wohnort: Bayern

Re: Bilder Doubletten erkennen

Beitragvon gTSj » Do Feb 06, 2014 7:22 pm

@killian: Damit geht dann halt die Platformunabhängigkeit verloren. Und die Distribution wird auch deutlich schwieriger.
gTSj
 
Beiträge: 21
Registriert: Mo Jan 27, 2014 10:49 pm

Re: Bilder Doubletten erkennen

Beitragvon Low012 » So Feb 09, 2014 9:37 pm

Hier mal mein alter Code von damals. Mein Versuch von damals ist mit Skalierung, Anpassung der Farben und Weichzeicher deutlich schneller als der ImageParser (zwischen 50% und 25 % der Zeit). Der große Nachteil meines Algorithmus ist, dass er sich durch geringfügig unterschiedliche Bildausschnitte schon durcheinander bringen lässt. Außerdem ist mein "ImageHash" viel länger als die Image-Momente.

Es wäre mal nett zu sehen, ob der Image-Parser mit meinen "Normalisierungsmethoden" deutlich schneller laufen würde und eventuell qualitativ ähnliche Ergebnisse liefern würde. Dazu bin ich nur heute Abend zu müde/faul.

Code: Alles auswählen
import java.awt.geom.AffineTransform;
import java.awt.image.AffineTransformOp;
import java.awt.image.BufferedImage;
import java.awt.image.BufferedImageOp;
import java.awt.image.ConvolveOp;
import java.awt.image.Kernel;
import java.io.File;
import java.io.IOException;
import java.util.Arrays;
import javax.imageio.ImageIO;

/**
*
* @author low012
*/
public final class ImageHash {

    private final static int BLOCK_WIDTH = 8;
    private final static int BLOCK_HEIGHT = 8;

    private final static int BLOCKS_HORIZONTAL = 8;
    private final static int BLOCKS_VERTICAL = 8;

    private final static int RESIZE_WIDTH = BLOCKS_HORIZONTAL * BLOCK_WIDTH;
    private final static int RESIZE_HEIGHT = BLOCKS_VERTICAL * BLOCK_HEIGHT;

    final static int DIVIDER = 8;

    private byte[] imageHash;

    public ImageHash(final BufferedImage image) {
        this(createImageHash(image));
    }

    public ImageHash(final byte[] imageHash) {
        this.imageHash = imageHash;
    }

    public byte[] getByteArray() {
        return imageHash;
    }
   
    @Override
    public boolean equals(final Object o) {
        final boolean ret;
        if (o == null) {
            ret = false;
        } else if (o instanceof BufferedImage) {
            ret = isSimilar(this.getByteArray(), (BufferedImage) o);
        } else if (o instanceof byte[]) {
            ret = isSimilar(this.getByteArray(), (byte[]) o);
        } else if (o instanceof ImageHash) {
            ret = isSimilar(this.getByteArray(), ((ImageHash) o).getByteArray());
        } else {
            ret = false;
        }

        return ret;
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 37 * hash + Arrays.hashCode(this.imageHash);
        return hash;
    }

    private boolean isSimilar(final byte[] imageHash, final BufferedImage image) {
        return isSimilar(imageHash, normalize(image));
    }

    private boolean isSimilar(final byte[] imageHash1, final byte[] imageHash2) {
       
        final int l = imageHash1.length;

        if (l != imageHash2.length) {
            throw new IllegalArgumentException("ImageHashs need to have same length: " +
                    l + " " + imageHash2.length);
        }

        int error = 0;

        for (int i = 0; i < l && error < 500; i++) {
            if (Math.abs((imageHash1[i] & 0xff) - (imageHash2[i] & 0xff)) > 1) {
                error++;
            }
        }

        /**
         * The value of 0.01 has been found by experimenting with images from
         * http://www.kasrl.org/jaffe.html and different size of the image at
         * http://en.wikipedia.org/wiki/File:Hillary_Clinton_Bill_Chelsea_on_parade.jpg
         *
         * 0.01 seems to be low enough to ensure that very similar, but still
         * clearly different images (slight change of angle from which an image
         * has been taken, small changes in facial expression) will be detected as
         * different, but resized images will be detected as not different.
         *
         * Try higher values to make the algorithm less strict.
         */
        return error < (l * 0.01);
    }

    private static byte[] createImageHash(final BufferedImage image) {
        if (image == null) {
            throw new IllegalArgumentException("Image may not be null!");
        }

        final byte[] b = normalize(image);
        final byte[] ret = new byte[BLOCKS_VERTICAL * BLOCKS_HORIZONTAL * 3];

        byte min;
        byte max;
        int sum;
        byte val;
        int i = 0;

        for (int v = 0; v < BLOCKS_VERTICAL; v++) {
            for (int h = 0; h < BLOCKS_HORIZONTAL; h++) {
                min = (byte) 0xff;
                max = (byte) 0x00;
                sum = (byte) 0x00;
                for (int bh = 0; bh < BLOCK_HEIGHT; bh++) {

                    for (int bw = 0; bw < BLOCK_WIDTH; bw++) {
                        val = b[(v * BLOCK_HEIGHT * RESIZE_WIDTH) + (h * BLOCK_WIDTH) + (bh * RESIZE_WIDTH) + bw];
                        if ((val & 0xff) < (min & 0xff)) {
                            min = val;
                        }
                        if ((val & 0xff) > (max & 0xff)) {
                            max = val;
                        }
                        sum += val & 0xff;
                       
                    }
                }

                ret[i++] = (byte) ((min & 0xff) / DIVIDER);
                ret[i++] = (byte) ((max & 0xff) / DIVIDER);
                // Besser statt Durchschnitt Median?
                ret[i++] = (byte) ((sum / (BLOCK_WIDTH * BLOCK_HEIGHT) & 0xff) / DIVIDER);
            }

        }

        return ret;
    }

    private static byte[] normalize(final BufferedImage image) {
        return bufferedGrayscaleImageToByteArray(spreadGrayValues(blur(toGrayScale(scale(image, RESIZE_WIDTH, RESIZE_HEIGHT)))));
    }

    private static BufferedImage scale(final BufferedImage image, final int width, final int height) {
        final AffineTransform tx = new AffineTransform();
        tx.scale((float)width/image.getWidth(), (float)height/image.getHeight());
        final AffineTransformOp affineTransformOp = new AffineTransformOp(tx, AffineTransformOp.TYPE_NEAREST_NEIGHBOR);

        return affineTransformOp.filter(image, null);
    }

    private static BufferedImage blur(final BufferedImage image) {
        final Kernel kernel = new Kernel(3, 3,
            new float[] {
                1f/9f, 1f/9f, 1f/9f,
                1f/9f, 1f/9f, 1f/9f,
                1f/9f, 1f/9f, 1f/9f});
        final BufferedImageOp op = new ConvolveOp(kernel);

        final BufferedImage ret = new BufferedImage(image.getWidth(), image.getHeight(), image.getType());
        op.filter(image, ret);
        return ret;
    }

    private static BufferedImage toGrayScale(final BufferedImage image) {
        final BufferedImage ret = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_BYTE_GRAY );
        ret.getGraphics().drawImage(image, 0, 0, null);
        return ret;
    }

    private static BufferedImage spreadGrayValues(final BufferedImage image) {
        int minGray = 255;
        int maxGray = 0;

        final int width = image.getWidth();
        final int height = image.getHeight();

        int rgb;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                rgb = image.getRGB(i, j) >> 16 & 0xff;
                if (rgb < minGray) {
                    minGray = rgb;
                }
                if (rgb > maxGray) {
                    maxGray = rgb;
                }
            }
        }

        final BufferedImage ret = new BufferedImage(width, height, image.getType());
        int o, n;

        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                o = image.getRGB(i, j) >> 16 & 0xff;
                n = (int)(255f * ((float)(o -minGray) / (float)(maxGray - minGray)));

                ret.setRGB(i, j, (n << 16) + (n << 8) + n);
            }
        }

        return ret;
    }

    private static byte[] bufferedGrayscaleImageToByteArray(final BufferedImage image) {
        final int width = image.getWidth();
        final int height = image.getHeight();
        final byte[] bytes = new byte[width * height];
        int a = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                bytes[a++] = (byte) (image.getRGB(j, i) & 0xff);
            }
        }
        return bytes;
    }

    public static void main(final String[] args) throws IOException {
       
       long t = System.currentTimeMillis();
       
        new ImageHash(ImageIO.read(new File("/mnt/Daten/dev/eclipse/testproj/kfz3.png")));
        System.out.println(System.currentTimeMillis() - t);
        t = System.currentTimeMillis();
        new ImageHash(ImageIO.read(new File("/mnt/Daten/dev/eclipse/testproj/kfz1.png")));
        System.out.println(System.currentTimeMillis() - t);
        t = System.currentTimeMillis();
        new ImageHash(ImageIO.read(new File("/mnt/Daten/dev/eclipse/testproj/kfz2.png")));
        System.out.println(System.currentTimeMillis() - t);
        t = System.currentTimeMillis();
        new ImageHash(ImageIO.read(new File("/mnt/Daten/dev/eclipse/testproj/kfz3.png")));
        System.out.println(System.currentTimeMillis() - t);
        t = System.currentTimeMillis();
        new ImageHash(ImageIO.read(new File("/mnt/Daten/dev/eclipse/testproj/kfz4.png")));
        System.out.println(System.currentTimeMillis() - t);
        t = System.currentTimeMillis();
        new ImageHash(ImageIO.read(new File("/mnt/Daten/dev/eclipse/testproj/kfz5.png")));
        System.out.println(System.currentTimeMillis() - t);
    }

}
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm

Re: Bilder Doubletten erkennen

Beitragvon Lotus » Di Feb 11, 2014 10:31 pm

Low012 hat geschrieben:Es wäre mal nett zu sehen, ob der Image-Parser mit meinen "Normalisierungsmethoden" deutlich schneller laufen würde und eventuell qualitativ ähnliche Ergebnisse liefern würde. Dazu bin ich nur heute Abend zu müde/faul.

Da im Code der gleiche Pfad wie in meinem angegeben ist, deute ich das mal als "führe das mal aus".
Das ist die Ausgabe:
Code: Alles auswählen
260
597
74
42
76
49

Das ist tatsächlich schneller bei großem Bild. Hätte ich kaum erwartet, dass eine Größenänderung so viel mehr Performance bringt, weil der direkte Pixel-Zugriff so langsam ist. Ist eine gute Idee!

Schön bei dem Hash ist (so wie ich verstehe), dass man für Doubletten sofort auf gleichen Hash prüfen kann. Die Momente sind da schon etwas unterschiedlich bei gleichem Ausgangsbild (siehe ersten Post). Das ließe sich vielleicht auch durch Weichzeichnen etwas vom Rauschen befreien.
Ich habe auch gelesen, dass für die Momente noch der Logarithmus gebildet werden kann, um die kleinen Zahlen etwas zu entzerren.

Meine erste Idee war, nachdem die Bilder gefunden wurden, und bevor sie angezeigt werden, eine unüberwachte Minimun-Distance Klassifikation auszuführen. (automatische Clusterbildung über Distanz, dann statistisch die Zugehörigkeit bestimmen) Das wäre wahrscheinlich beim derzeitigen Suchablauf aufwändig zu implementieren. (Ich habe nicht nachgesehen.)
Lotus
 
Beiträge: 1699
Registriert: Mi Jun 27, 2007 3:33 pm
Wohnort: Hamburg


Zurück zu YaCy Coding & Architecture

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast