Bilder-Ordner vergleichen

Hey.

Ich hab grad ein komisches Problem und weiß nicht woran es liegt. Ich hab gegoogled wie man am besten Bilder vergleicht, da wurde mir geraten mit dem RBG-Wert eines BufferedImages Pixel für Pixel die Bilder zu vergleichen. So das habe ich versucht umzusetzen (Statusmeldungen, also sout habe ich mal dringelassen)

Erstmal die Methode:
[spoiler]

        if (first == null || !first.toFile().isDirectory() || second == null || !second.toFile().isDirectory()) {
            throw new NoDirectoryException("Die Pfade müssen Ordner sein!");
        }

        long time = System.nanoTime();
        long time2 = System.currentTimeMillis();
        long ungleich = 0, for1 = 0, for2 = 0, for3 = 0, for4 = 0, for5 = 0, for6 = 0;

        File fp = first.toFile();
        File fo = second.toFile();
        File[] a = fp.listFiles();
        File[] b = fo.listFiles();

        for (File f : a) {
            for1++;
            for (File d : b) {
                for2++;
                ImageIcon icon = new ImageIcon(f.toURI().toURL());
                ImageIcon icon2 = new ImageIcon(d.toURI().toURL());
                if (!f.isDirectory() && !d.isDirectory()) {
                    BufferedImage image1 = new BufferedImage(icon.getIconHeight(), icon.getIconHeight(), BufferedImage.TYPE_INT_RGB);
                    BufferedImage image2 = new BufferedImage(icon2.getIconHeight(), icon2.getIconHeight(), BufferedImage.TYPE_INT_RGB);
                    int iHeight = 0, iWidth = 0, uHeight = 0, uWidth = 0;
                    for (; iHeight != image1.getHeight(); iHeight++) {
                        for3++;
                        for (; iWidth != image1.getWidth(); iWidth++) {
                            for4++;
                            for (; uHeight != image2.getHeight(); uHeight++) {
                                for5++;
                                for (; uWidth != image2.getWidth(); uWidth++) {
                                    for6++;
                                    if (image1.getRGB(iHeight, iWidth) != image2.getRGB(uWidth, uWidth)) {
                                        ungleich++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        long after = System.nanoTime();
        long after2 = System.currentTimeMillis();
        long dauer = after - time;
        long dauer2 = after2 - time2;
        DateFormat df = DateFormat.getTimeInstance(DateFormat.MEDIUM);
        DecimalFormat de = new DecimalFormat();
        df.setTimeZone(TimeZone.getTimeZone("GMT"));
        System.out.println("For1: " + de.format(for1));
        System.out.println("For2: " + de.format(for2));
        System.out.println("For3: " + de.format(for3));
        System.out.println("For4: " + de.format(for4));
        System.out.println("For5: " + de.format(for5));
        System.out.println("For6: " + de.format(for6));
        System.out.println("Ungleiche: " + ungleich);
        System.out.println("Dauer in Nanos: " + de.format(dauer) + "; Formatiert: " + df.format(dauer));
        System.out.println("Dauer in Millis: " + de.format(dauer2) + "; Formatiert: " + df.format(dauer2));

        return ungleich;
    }```
[/spoiler]
Ohne die Ausgaben:
```private static int compareImageDirectories(Path first, Path second) throws MalformedURLException, NoDirectoryException {
        File fp = first.toFile();
        File fo = second.toFile();
        File[] b = fp.listFiles();
        File[] a = fo.listFiles();
        
        int ungleich = 0;

        for (File f : a) {
            for (File d : b) {
                ImageIcon icon = new ImageIcon(f.toURI().toURL());
                ImageIcon icon2 = new ImageIcon(d.toURI().toURL());
                if (!f.isDirectory() && !d.isDirectory()) {
                    BufferedImage image1 = new BufferedImage(icon.getIconHeight(), icon.getIconHeight(), BufferedImage.TYPE_INT_RGB);
                    BufferedImage image2 = new BufferedImage(icon2.getIconHeight(), icon2.getIconHeight(), BufferedImage.TYPE_INT_RGB);
                    int iHeight = 0, iWidth = 0, uHeight = 0, uWidth = 0;
                    for (; iHeight != image1.getHeight(); iHeight++) {
                        for (; iWidth != image1.getWidth(); iWidth++) {
                            for (; uHeight != image2.getHeight(); uHeight++) {
                                for (; uWidth != image2.getWidth(); uWidth++) {
                                    if (image1.getRGB(iHeight, iWidth) != image2.getRGB(uWidth, uWidth)) {
                                        ungleich++;
                                    }
                                }
                            }
                        }
                    }
                }                                   
            }
        }
        return ungleich;
    }```
Die Ausgabe bei meinen beiden Testordnern war:

For1: 82
For2: 6.478
For3: 4.530.006
For4: 4.530.006
For5: 4.791.717
For6: 4.791.717
Ungleiche: 0
Dauer in Nanos: 8.016.962.697; Formatiert: 18:56:02
Dauer in Millis: 8.017; Formatiert: 00:00:08



Im ersten Ordner sind 82 Dateien, im 2. 79. Hab dabei mal die Pfadangaben umgedreht, dabei hat sich auch nur die erste Ausgabe in die Menge des anderen Ordners geändert, das passt also.
Aber wieso ist die 3. + 4. Ausgabe, sowie die 5. + 6. Ausgabe immer gleich? Dazu werden 0 ungleiche Bilder gefunden, obwohl einige Bilder nicht in beiden sind und einige auch nur einen Ausschnitt eines anderen sind.
Also wieso findet er keine ungleichen Bilder?
Bzw. wieso wird `if (image1.getRGB(iHeight, iWidth) != image2.getRGB(uWidth, uWidth)) {` nie true? Die Abfrage wird ja ausgeführt, aber anscheinend sind immer alle gleich... ich denk jetz schon ca 30min drüber nach und komm nicht drauf.

Dein Algorithmus funktioniert so nicht. Du zählst die Indizes der beiden Bilder unabhängig voneinander hoch. Du möchtest aber die Bilder doch sicherlich “übereinander legen”, oder? Also das oberste linke Pixel des ersten mit dem obersten linken Pixel des zweiten Bildes vergleichen etc…
Die Konstruktion mit den vier For-Schleifen ohne Initializer macht einen sofort stutzig und ist auch an dieser Stelle hier falsch.
Du benötigst nur zwei Schleifen und musst vor dem Iterieren über die Pixel prüfen, ob die Bilder gleich breit / hoch sind.

Abgesehen davon sind die Variablennamen nicht unbedingt sprechend.

[hr][/hr]

Wenn du nur duplizierte Bilder finden möchtest, ist der Ansatz übrigens nicht unbedingt optimal. Da würde es sich anbieten, die Dateien der Größe nach zu sortieren und dann nur genau gleich große zu vergleichen. Dabei müsstest du nicht einmal die Bilder als solche laden, sondern könntest einen binären Vergleich machen.

Okay, ich schaue mir den Ansatz mit dem binären vergleich der größe an, da mein vorheriger Ansatz noch nen Fehler hat und ich den nicht finde. bzw mir das grade zu kompliziert ist. Ich muss halt prüfen ob die Bilder gleich sind und wenn sie es sind sie aus dem Array schmeißen, da ansonsten viel zu hohe Zahlen bei rumkommen.

Ungefähr so hätte ich das gemacht, ist aber noch stark verbesserungswürdig:

        if (f1.length() == f2.length()) { // quasi unsicher
            // return 0;
        }
        BufferedInputStream bis1 = new BufferedInputStream(new FileInputStream(f1));
        BufferedInputStream bis2 = new BufferedInputStream(new FileInputStream(f2));
        int i1, i2;
        while ((i1 = bis1.read()) != -1 && (i2 = bis2.read()) != -1) {
            if (i1 != i2) { // überspringt Pixelvergleich
                // return 1;
            }
        }
        BufferedImage bi1 = ImageIO.read(f1);
        BufferedImage bi2 = ImageIO.read(f2);
        if (bi1.getWidth() != bi2.getWidth() || bi1.getHeight() != bi2.getHeight()) { // überspringt auch Pixelvergleich
            // return 1;
        }
        int result = 0;
        for (int x = 0; x < bi1.getWidth(); x++) {
            for (int y = 0; y < bi1.getHeight(); y++) {
                if (bi1.getRGB(x, y) != bi2.getRGB(x, y)) {
                    result++;
                }
            }
        }
        return result;
    }```

(Beim Test von zwei .png ergab sich 417538 Fehler ~ 300 Millisekunden, langsam),

Du hast einmal den binären Vergleich, und einmal den 1:1-Pixel-Vergleich,

was passiert bei gleicher Größe? Weitermachen, Rückgabe?
Was passiert bei ungleich Byte? Weitermachen, Rückgabe?
Was passiert bei ungleich Pixel? Weitermachen, Rückgabe?

Wie man jedes "Element" 'paarweise' aus zwei "Mengen" miteinander vergleicht, weißt du? Fakultät ... deswegen auch langsam.

Wir brauchen mehr Input.^^

Grüße

Edit: Empfohlen ist, das dringlichst in zwei Methoden aufzuteilen. :stumm:
if (image1.getRGB(iHeight, iWidth) != image2.getRGB(uWidth, uWidth)) {//Deine Code
if (image1.getRGB(iHeight, iWidth) != image2.getRGB(uHeight, uWidth)) {// uWidth mit uHeight ersetzt?
if (image1.getRGB(iHeight, iWidth) != image2.getRGB(iHeight, iWidth)) {// das gesuchte?


Habe schonmal nen großen Fehler bei mir gefunden: das BufferedImage hat mein Bild ja gar nicht drin, kennt ja nur die größe davon. Als ich es jetzt mit dem ImageIO probiert habe erkennt er auch die Bilder und vergleicht die Pixel. bei meinen Testordnern sind das allerdings über 6000 Vergleiche, die er prüfen muss. Daher hatte ich eingebaut, sollte er was gleiches finden, das er aus beiden Arrays die Bilder entfernt, damit das ganze dann nicht so lange dauert, er hat ja gleiches gefunden. Jetzt hast der Test auch 8 minuten gedauert und er hat 41 gleiche Bilder gefunden, passt in etwa auch (hab jetz nicht nachgezählt).

        if (first == null || !first.toFile().isDirectory() || second == null || !second.toFile().isDirectory()) {
            throw new NoDirectoryException("Die Pfade müssen Ordner sein!");
        }

        long time = System.currentTimeMillis();
        int gleiche = 0;

        File[] firstArray = first.toFile().listFiles();
        File[] secondArray = second.toFile().listFiles();
        int länge = firstArray.length + secondArray.length;
        
        boolean gleich = false;
        for (int lFirst = 0; lFirst < firstArray.length; lFirst++) {
            File file1 = firstArray[lFirst];
            for (int lSecond = 0; lSecond < secondArray.length; lSecond++) {
                File file2 = secondArray[lSecond];
                if (!file1.isDirectory() && !file2.isDirectory()) {
                    BufferedImage image1 = ImageIO.read(file1);
                    BufferedImage image2 = ImageIO.read(file2);

                    if (image1.getWidth() == image2.getWidth() && image1.getHeight() == image2.getHeight()) {
                        int width = image1.getWidth();
                        int height = image1.getHeight();
                        for (int i = 0; i < width; i++) {
                            for (int j = 0; j < height; j++) {
                                if (image1.getRGB(i, j) == image2.getRGB(i, j)) {
                                    gleich = true;
                                } else {
                                    gleich = false;
                                    break;
                                }
                                if (!gleich) {
                                    break;
                                }
                            }
                        }
                    } else {
                        gleich = false;
                    }
                    if (gleich) {
                        System.out.println("Gleich: " + ++gleiche);
                        List<File> list1 = Arrays.asList(firstArray);
                        List<File> list2 = Arrays.asList(secondArray);

                        list1.stream().filter((f1) -> (f1 == null)).forEach((f1) -> {
                            list1.remove(f1);
                        });
                        list2.stream().filter((f2) -> (f2 == null)).forEach((f2) -> {
                            list2.remove(f2);
                        });
                        firstArray = (File[]) list1.toArray();
                        secondArray = (File[]) list2.toArray();
                    }
                }
            }
        }

        long after = System.currentTimeMillis();
        long dauer = after - time;
        DateFormat date = DateFormat.getTimeInstance(DateFormat.MEDIUM);
        DecimalFormat decimal = new DecimalFormat();
        date.setTimeZone(TimeZone.getTimeZone("GMT"));
        System.out.println("Ungleiche: " + gleiche);
        System.out.println("Dauer in Millis: " + decimal.format(dauer) + "; Formatiert: " + date.format(dauer));
        
        int rückgabe = länge - gleiche*2;
        System.out.println("Rückgabe: " + rückgabe);
        return rückgabe;
    }```
Allerdings weiß ich, das das ganze ansich schon nicht optimal ist, da ich mit

```if (gleich) {
                        System.out.println("Gleich: " + ++gleiche);
                        List<File> list1 = Arrays.asList(firstArray);
                        List<File> list2 = Arrays.asList(secondArray);

                        list1.stream().filter((f1) -> (f1 == null)).forEach((f1) -> {
                            list1.remove(f1);
                        });
                        list2.stream().filter((f2) -> (f2 == null)).forEach((f2) -> {
                            list2.remove(f2);
                        });
                        firstArray = (File[]) list1.toArray();
                        secondArray = (File[]) list2.toArray();```

Sehr sehr unschönen Code erzeuge mMn.


Edit:  @CyborgBeta : Danke, ich schau mir den Code mal genauer an :) und bei ungleich byte/Pixel sollte er erstmal aufhören. Hätte zwar noch ne Idee, bei der das nicht soll, aber das mach ich ein ander mal.

Wie cmd schon sagt:
Typischerweise würde man die Bilder oder Dateien zuerst einmal

  • nach größe sortieren
  • einen HashCode bilden z.B. md5 und danach sortieren.
  • erst wenn größe und HashCode übereinstimmen die Bilder per Pixel miteinander vergleichen.

Größe einer Datei bestimmen und nach Größe sortieren, hat die Komplexität n + (n log(n))
n für das bestimmen der Dateigröße
n log(n) für das Sortieren nach der Dateigröße.

HashCode bilden und danach sortieren hat ebenfalls die Komplexität n + (n log(n))

Die Kandidaten die nun schon wegfallen sogen dafür, dass für den letzten Schritt nur noch relativ wenig Dateien Pixelweise überprüft werden müssen und diese höchstwahrscheinlich identisch sind.

Das hat immer noch die Komplexität n * n, wobei n nun sehr klein sein wird, da hier nur noch Dateien miteinander verglichen werden die höchstwahrscheinlich identisch sind.

Das meinte ich ja, das sind ganz viele kleine Schritte bis zum Ziel. :slight_smile:

Also byteweise vergleichen hätte bei 2 Bildern nur 2n.

Hash usw. …

Sollen zwei Bilder miteinander verglichen werden, oder alle überall?

Sollen alle Fehler gezählt werden, oder reicht 1 Fehler?

Größe → Hash → Byte → Pixel … so hätte ich das jetzt verstanden, aber das ergibt überhaupt keinen Sinn.

Picasa google hat das mit den Duplikaten übriges schon eingebaut und damit sind dir sehr gut.

Schreibe vom Handy aus, deswegen so knapp.

Ja, so ein ähnliches Tool wollte ich auch schon ewig mal schreiben, aber … wenn, dann eins, wo man eine “fuzzyness” für den Vergleich angeben kann. Also, Bilder wirklich Pixel für Pixel auf “identität” prüfen, macht nur selten Sinn: Wenn das JPGs sind, und das eine mit 84% Kompression und das andere mit 85% Kompression gespeichert ist, sind die “unterschiedlich”. Von Wasserzeichen, Größenänderungen oder cropping mal ganz abgesehen.

Zumindest der Hinweis ist diesmal gut: Du solltest den eigentlichen Vergleich definitiv in eine Methode auslagern. Erstens weil es deutlich übersichtlicher wird, zweitens ist es besser strukturiert, du sparst dir diesen “boolean gleich” und “break”-Murx, und es ist leichter zu testen.

Es ist noch nicht vollständig klar, was du eigentlich machen willst. Bei zwei Ordnern rausfinden, welche Bilder “gleich” sind? Was soll das ergebnis sein, wenn ein Bild aus einem Ordner “gleich” zu ZWEI Bildern aus dem anderen Ordner ist? (Oder auch zu einem oder mehreren aus demSELBEN Ordner?). Wie auch immer: Wenn du den Bildvergleich erstmal in eine Methode ausgelagert hast, geht es ja nur noch um die Frage, wo genau diese Methode aufgerufen wird - das läßt sich dann recht schnell und bequem ändern.

Der eigentliche Vergleich könnte, wie schon angedeutet wurde, in mehreren Stufen ablaufen:

  • Dateigröße
  • Dateiinhalt
  • Bildinhalt

Ob sich der Vergleich des Dateiinhalts lohnt, oder der Vergleich des Bildinhalts dann überhaupt noch notwendig ist, ist schwer zu sagen: Es könnte sein, dass irgendwann das reine Lesen der Daten das teuerste ist. Also, wenn man zwei Dateien hat, die byteweise gleich sind - dann beschreiben sie auch das gleiche Bild. Da braucht man keine Aufwändige JPG- oder PNG-Dekompression mehr zu machen.

Der Fall, das zwei Dateien NICHT byteweise gleich sind, aber trotzdem die RGB-Werte (also PIXELWEISE) gleich sind, ist schwer vorstellbar - bestenfalls bei PNGs mit unterschiedlichen Komprimierungen, oder allgemein zwei unterschiedlichen (aber verlustfreien!) Komprimierungsverfahren…

Wie auch immer. Dieses ganze Path- und Files-Zeug geht seit Java 7 mit der neuen Path-API, und da gibt’s ein paar recht praktische Funktiönchen. Hier ist mal was schnell hingeschriebenes, was den Pixelvergleich macht (obwohl der, wie oben gesagt, vielleicht überflüssig ist).

Nicht zuletzt soll das zeigen, dass der Ansatz, den Vergleich mit getRGB zu machen, schrecklich ineffizient ist. Eine schnellere Alternative ist da als equalImagesWithBuffer implementiert.

import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.awt.image.DataBuffer;
import java.awt.image.DataBufferInt;
import java.awt.image.WritableRaster;
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;

import javax.imageio.ImageIO;

public class ImageComparison
{
    public static void main(String[] args) throws IOException
    {
        Path path0 = new File("C:/PORN_OF_COURSE").toPath();
        Path path1 = new File("C:/PORN_OF_COURSE").toPath();
        compareImageDirectories(path0, path1);
    }

    private static void compareImageDirectories(
        Path path0, Path path1) throws IOException
    {
        Objects.requireNonNull(path0, "path0 is null");
        Objects.requireNonNull(path1, "path1 is null");
        if (!Files.isDirectory(path0))
        {
            throw new IllegalArgumentException(
                "path0 is not a directory: "+path0);
        }
        if (!Files.isDirectory(path1))
        {
            throw new IllegalArgumentException(
                "path0 is not a directory: "+path1);
        }
        
        List<File> files0 = Files.walk(path0)
            .filter(Files::isRegularFile)
            .map(Path::toFile)
            .collect(Collectors.toList());
        List<File> files1 = Files.walk(path0)
            .filter(Files::isRegularFile)
            .map(Path::toFile)
            .collect(Collectors.toList());
        
        long before = System.nanoTime();
        
        Set<File> duplicateImages = new LinkedHashSet<File>();
        for (File file0 : files0)
        {
            for (File file1 : files1)
            {
                System.out.println("Compare "+file0.getAbsolutePath());
                System.out.println("    and "+file1.getAbsolutePath());
                boolean equal = equalImagesWithBuffer(file0, file1);
                if (equal)
                {
                    duplicateImages.add(file0);
                    duplicateImages.add(file1);
                }
            }
        }
        
        long after = System.nanoTime();
        System.out.println("Duration: "+(after-before)/1e6+
            ", duplicate: "+duplicateImages.size());
    }

    
    private static boolean equalImages(File file0, File file1)
    {
        if (file0.length() != file1.length())
        {
            return false;
        }
        BufferedImage image0 = null;
        BufferedImage image1 = null;
        try
        {
            image0 = ImageIO.read(file0);
            image1 = ImageIO.read(file1);
        }
        catch (IOException e)
        {
            // At least one of them is not a valid image file
            return false;
        }
        int w0 = image0.getWidth();
        int h0 = image0.getHeight();
        int w1 = image1.getWidth();
        int h1 = image1.getHeight();
        if (w0 != w1 || h0 != h1)
        {
            return false;
        }
        for (int x = 0; x < w0; x++)
        {
            for (int y = 0; y < h0; y++)
            {
                if (image0.getRGB(x, y) != image1.getRGB(x, y))
                {
                    return false;
                }
            }
        }
        return true;
    }
    
    private static boolean equalImagesWithBuffer(File file0, File file1)
    {
        if (file0.length() != file1.length())
        {
            return false;
        }
        BufferedImage image0 = null;
        BufferedImage image1 = null;
        try
        {
            image0 = convertToARGB(ImageIO.read(file0));
            image1 = convertToARGB(ImageIO.read(file1));
        }
        catch (IOException e)
        {
            // At least one of them is not a valid image file
            return false;
        }
        int a0[] = getDataInt(image0);
        int a1[] = getDataInt(image1);
        return Arrays.equals(a0, a1);
    }
    
    private static int[] getDataInt(BufferedImage image)
    {
        WritableRaster raster = image.getRaster();
        DataBuffer dataBuffer = raster.getDataBuffer();
        DataBufferInt dataBufferInt = (DataBufferInt)dataBuffer;
        int data[] = dataBufferInt.getData();
        return data;
    }
    
    private static BufferedImage convertToARGB(BufferedImage image)
    {
        BufferedImage newImage = new BufferedImage(
            image.getWidth(), image.getHeight(),
            BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = newImage.createGraphics();
        g.drawImage(image, 0, 0, null);
        g.dispose();
        return newImage;
    }        
    
}

Dafür, dass getRGB langsam ist, kann ich nun wirklich nix^^

Es kommt auch drauf an, wie viele tausend Bilder er da hat.

Btw: Zwei Bilder können sehr wohl byteweise unterschiedlich, aber pixelweise genau gleich sein … So, jetzt hab ich 2x das schlimme Wort weise geschrieben, was ich eigentlich vermeiden wollte.

Ist es jetzt überhaupt sinnvoll, eine business Lösung zu posten?

OKay, danke. Evtl kurz der Umstand, warum ich das mache:

Ich bekomme Bilder aus einer Internetquelle und ich speicher diese in einem Ordner. Damit ich diese allerdings in einem anderen Programm weiterbenutzen kann, müssen diese alle eine bestimmte Größe haben (1215 x 717 Pixel). Die Bilder aber haben nicht unbedingt diese Größe. Also bearbeite ich sie, indem ich sie vergrößer/verkleiner und zur Not auch noch zurechtschneide, damit sie eben diese Größe haben. Da das allerdings immer mehr Bilder werden, wollte ich ein Programm basteln, das mir verrät, wieviele Bilder in beiden Ordnern die selben sind, da ich ja weiß, wieviele ich bearbeitet habe und auch weiß wieviele in beiden Ordnern sind. Und per Auge auf den Vorschaubildern zu schauen und zu gucken ob die in beiden drinne sind, oder ich vergessen hab eines zu kopieren und umzubenennen, hat mir gezeigt, das ich oft was übersehe. Dafür war das gedacht.
Daher auch mein letzter Satz im vorletzten Post:

Hätte zwar noch ne Idee, bei der das nicht soll, aber das mach ich ein ander mal.

Und zwar, das die Bilder nichtmehr die selbe Größe haben müssen, aber das selbe Motiv zeigen, also die, die ich bearbeitet habe und die originalen haben im Zwangsfall kleinere Unterschiede (eig nie mehr als 100 Pixel pro Seite unterschied). Dann müsste man quasi schauen ob eines der Bilder im jeweils anderen komplett enthalten ist, es also nur ein Ausschnitt ist. Wie man das dann aber umsetzt stelle ich mir sehr schwer vor.

Das werde ich auch in Zukunft noch öfters machen und meinem Kumpel würde das auch einige Arbeit wegnehmen, daher probiere ich das nachschauend er Bilder programmtechnisch zu lösen, damit man in der Zeit weiter Bilder bearbeiten kann und nicht noch damit Zeit verbringen muss.

Bilderausschnitt finden ist wiederum eine komplett andere Aufgabe. Ich bin mal raus aus der Diskussion. Jetzt klickt bestimmt jemand auf danke. :slight_smile:

Ja, einen Bildausschnitt in einem anderen finden ist einer der Fälle, die ich mit dem “fuzzy-Vergleich” ja schon angedeutet hatte (oder eben einfach Größenänderungen). Ich hatte vor Jahren mal ein Programm für sowas irgendwo runtergeladen, das nannte sich “UniqueFiler”, aber das soll keine Empfehlung sein - wenn man im Netz sucht, findet man einige Tools, die “sowas” hinkriegen. Aber selbst machen wäre natürlich cooler. Ich hab’ da zwar schon ein paar Ideen dazu, aber die sind sehr abstrakt und konzeptuell (nicht ganz so abgespact wie https://en.wikipedia.org/wiki/Scale-invariant_feature_transform oder so, aber … nichts, was man vernünftig an einem Nachmittag hinschreiben könnte…). Naja, vielleicht schau’ ich in den nächsten Tagen da nochmal. Würde mich schon reizen.

@Schesam : So muss/müsste das aussehen:

        Thread.sleep(10000);
        long t1 = System.currentTimeMillis();

        File[] fa1 = new File("").listFiles();
        File[] fa2 = new File("").listFiles();
        for (int i = 0; i < fa1.length; i++) {
            for (int j = i + 1; j < fa2.length; j++) {
                if (compareFast(fa1**, fa2[j])) {
                    if (compareSlow(fa1**, fa2[j]) == 0) { // od. kleiner Schwellenwert
                        System.out.println("fa1** = " + fa1**);
                        System.out.println("fa2[j] = " + fa2[j]);
                        System.out.println(" ... sind gleich ... ");
                        continue;
                    }
                }
                System.out.println(" ... sind ungleich ... ");
            }
        }

        long t2 = System.currentTimeMillis();
        System.out.println(t2 - t1);
    }

    private static boolean compareFast(File f1, File f2) throws IOException {
        return true;
    }

    private static int compareSlow(File f1, File f2) throws IOException {
        return 0;
    }```
(ungetestet)

compareFast weiß zum Bleistift einen Hash, und gibt nur false zurück, falls es stark abweicht.
compareSlow geht dann PIXELWEISE daran und gibt nur 0==true zurück, wenn kein Pixel abweicht.

Kann ein Hash gebildet werden, der immer für zwei ähnliche Bilder gleich ist? Das wäre doch mal cool.

Schreien die beiden if-Bedingungen nicht nach einem logischen und? Das spart dann auch das continue.

Ja, stimmt.

@TO
Bzgl. deines Posts mit “zurechtrücken” kommt hier weder ein Byte-wise noch Pixel-wise Vergleich in Frage, bzgl. des angesprochnen Problems z.B. mit Kompressions-Artefakten.
Der von @Marco13 angesprochene “fuzzy”-Vergleich wird hier schon wichtger.
Da ich mich selbst mal mit befasst habe wäre vielleicht eine Hough-Transformation möglich. Dabei werden Formen in den Hough-Raum überführt (hauptsächlich Kankten und Winkel). So funktioniert z.B. OCR (Texterkennung). So könnte man vergleichen ob die Bilder einen ähnlichen “logischen” Inhalt haben. Außerdem lässt sich im Hough-Raum auch einfacher mit Ähnlichkeit arbeiten da dort wie gesagt nur Kanten und Winkel erfasst werden.
[ot]Sidenote:
Meine Erfahrung liegt dabei im Bereich eines Captcha-Crackers für das Browser-Spiel “Pennergame”. Zu besagter Zeit (um Win7 rum, also Herbst/Winter '09) ging es darum in einem Zufallsbild eine Zahl zu erkennen. Die Schwierigkeit lag dabei sowohl in Rotation als auch Größenänderung. Wobei DAS noch vergleichsweise einfach war da man nur mit einem Font gearbeitet hat. Mit verschiedenen Fonts wäre es für mich eine Katastrophe geworden.
Zwar hab ich mich mit Hough-Transformation befasst und es theoretisch auch recht gut verstanden, hab aber letztlich nur den über einen Leak verfügaren PHP-Bot (zugegeben: extremst schlecht) nach Java portiert (war damals noch recht gut mit PHP) und dabei von einem in Delphi geschriebenen Bot “Matrix”-Files “geklaut”.
Diese Matix-Files waren wie folgt aufgebaut:
1.) Grayscale > ein farbiges Bild (war meist weist mit nem Grün) in Schwarz/Weis “übersetzen”
2.) Center-Punkte festlegen (diese wurden nachher als x/y-Koordinaten für den Request genutzt - 1-zu-1 vom AJAX-Script geklaut)
3.) markante Punkte festlegen: eine 4 wurd z.B. mit dem Font passenden “Eck-Punkten” makiert, diese mussten passen damit eine 4 eindeutig “erkannt” werden konnte
4.) entlang der in 3. gelegten Fix-Punkte “grob” verteilt “relative”-Punkte: z.B. entlang der geraden Kanten wurden alle 20-30 Pixel ein “Dot” gesetzt - so konnte man, wenn sich z.B. die Marker-Position mit einer anderen Ziffer überschitten haben, anhand der so definierten Kanten schon mal differenzieren
5.) Feintuning: da man ein S/W Bild hat kann man nun mit einer prozentualen Abweichung (ich hab glaub 90%-95% genutzt) dann die noch übrigen schwarzen Pixel 1-zu-1 vergleichen um so wirklich festzustellen hat man die Zahl gefunden oder nur eine zufällige Kombination von Linien die zufällig so zusammen lagen
Mein Code hatte dabei eine recht gute Erkennung von um 50/100 - 80/100 - nach etwas mehr feintuning und besseren “vorlagen” hab ichs bis auf um die 85/100-90/100 geschafft - was war ich stolz drauf … guck ich mir heute an : W T F ?=!
Die vorlagen zu rotieren (das kann Java ja selbst) und den gleichen Code drauf anzuwenden war dann nur noch ein loop mehr. Dabei half mir dass vom “geraden” Bild Abweichungen von max 35° Roatation in ca. 5° Abständen gab.[/ot]
Was ist jetzt aber der große Vorteil von Hough? Recht einfach: Das Bild wird in Kanten zerlegt, ähnlichen einem S/W ohne Graustufen. Diese werden dann mit Position und Winkel in eine Matrix übertragen. Eine Kante die mit 30° irgendwo im Bild liegt hat im Hough-Raum so nur einen kleinen Cluster an Zuordnungen, da mit Winkelfunktion und Position Höhe-durch-Breite der gleiche Referenz-Punkt rauskommt.
Kleines Rechenbeispiel:

in einem 100x100 liegt eine Kante mit 45° von 0x50 bis 50x0 im Bild. Umgerechnet in den Hough-Raum ergibt sich bei genügend guter Auflösung genau EIN “Referenz-Punkt” der irgendwo bei 20x40 liegt. Und egal ob ich bei 0x50 oder 50x0 der Kante im Original langgehe komm ich immer wieder auf ungefährt genau diesen Punkt +/- 5-10 Pixel. Dabei gibt, wenn ichs noch richtig im Kopf hab, x im Hough-Raum die “relative” Lage des Refenzpunktes an, und y den Winkel. Das kann man dann noch auf beliebig komplexe geometrische Formen ausweiten. So ergibt z.B. ein Kreis im Hough-Raum eine begrenzte Strecke.
Wie gesagt: ich habs nie selbst implementiert - hab die einfache Lösung vorgezogen - aber so ungefähr funktioniert letztlich Texterkennung ganz grob beschrieben.
Diese so nun erzeugten Hough-Matrizen kann man gegen Referenzen prüfen und so feststellen: gibt es das geometrische Objekt X im Bild Y. Das hilft sehr gut bei Scaling und “Rausch”-Artefakten.
[ot]Bei mir auf Arbeit verwenden wird eine so gute OCR-Software das diese einen handschriftlichen Brief in ein LaTeX/PDF so umwandeln kann dass nicht nur der eigentliche Text lesbar wird, sondern auch die “Höhe der Buchstaben auf der Linie” berücksichtigt werden. So kommt also keine gerade Text-Linie raus - sondern ein etwas merkwürdig aussehnder Wiggle-Worm.[/ot]
Wie aufwändig dass nun für dein Projekt wird - fraglich. Aber grundsätzlich gibt es solche Algorithmen die eben eine solche “fuzzy”-Prüfung eines Foto-Archives ermöglichen. Und soweit ich das rausgelesen habe ist es ja ungeführ sowas was du suchst.

Ja, tatsächlich wird die Frage, welches das „geeignetste“ Verfahren ist, um „ähnliche“ Bilder zu erkennen, auf dieser Ebene vom Inhalt der Bilder abhängen. Und natürlich kann man dabei in bezug auf die Semantik beliebig weit gehen. Und dann endet man hier: xkcd: Tasks

Wenn zwei Bilder „ähnlich“ sein sollen, weil sie beide einen Vogel zeigen, dann hat man ein Problem.
Wenn zwei Bilder „ähnlich“ sein sollten, weil sie beide einen ähnlichen Text (ggf. nur transformiert) mit ähnlichem Font, dann geht das in Richtung eines Capcha-Lösers
Wenn zwei Bilder „ähnlich“ sein sollten, weil sie das gleiche, geometrisch einfach aufgebaute Objekt zeigen, dann kann eine Hough-Transformation ein geeigneter Ansatz sein.

Auf der obersten Ebene ist die Frage, die sich stellt, aber immer die gleiche: Es geht um die Defintion eines „Distanzbegriffes“ für Bilder (analog zu (bzw. das Inverse von) einem „Ähnlichkeitsbegriff“).

Man könnte übertrieben vereinfacht annehmen, es ginge um eine ToDoubleBiFunction<BufferedImage,BufferedImage>, die für zwei gleiche Bilder 0.0 ausspuckt, und für zwei Bilder, die unterschiedlicher nicht sein könnten, 1.0 (oder +Unendlich…)

Ich hatte jetzt (einfach drauf los, ohne Anforderungsanalyse, als „recreational programming task“) mal angefangen, auf etwas hinzuarbeiten, was auf ein recht einfaches Distanzmaß rausläuft. (Ich weiß, es gibt da schon wahnsinnig viel Literatur dazu - ein bißchen habe ich schon gesucht, aber das ist wirklich nur ein Rumspielen, Rumhacken - also nicht ernst zu nehmen). Genaugenommen hatte ich mir verschiedene Testfälle erstellt:

Und man könnte sich ja jetzt verschiedene Distanzmaße vorstellen, nach denen diese Bilder „ähnlich“ sind oder eben nicht. Z.B. hatte ich eine Funktion erstellt, die (pixelweise) die Differenz der Hue, Saturation und Brightnesses aufsummiert (das sind die „einfachen“ Fälle - da gibt es ein Maximum :smiley: ). D.h. zwei Bilder, die sich nur in der Helligkeit unterscheiden, hätten mit dem „Hue-Distanzmaß“ einen Abstand von 0.0, aber mit dem Brighness-Distanzmaß eben 0.231 oder so.

Der Gedanke dabei ging in die Richtung, dass man dem Benutzer (bzw. erstmal dem Entwickler) überlassen könnte, was „Distanz“ für ihn denn bedeutet. Vielleicht WILL der Benutzer ja sagen: „Helligkeitsunterschiede sind mir nicht so wichtig: Wenn der Farbton der gleiche ist, sind sie ähnlich“. Sowas könnte mann dann modellieren, indem man eine Linearkombination (genaugenommen eine Konvexkombination) von verschiedenen Distanzmaßen erstellt. Vor meinem geistigen Auge gibt’s da also irgendwo eine handvoll Slider


Hue weight         [-------X---]
Saturation weight  [----X------]
Brighness weight   [-X---------]
Size weight        [-------X---] 
Distortion weight  [--------X--]
Cropping weight    [------X----]

(welche natürlich jeder durch Plugins erweitern kann :smiley: )

Das ist natürlich hoffnungslos naiv :slight_smile: Es drängen sich schnell recht offensichtliche Fragen auf, deren Beantwortung schwer bis unmöglich ist. Aber nochmal, das war nur so zum Spaß - vielleicht fällt neben der ImageComponent auch noch eine Sammlung von praktischen Image-Utility-Funktionen hinten runter…

@Schesam Wenn das ganze zu off-topic ist (oder wird), könnte man es an geeigneter Stelle abschneiden…