Fotos Duplikate finden

MiMa

Top Contributor
Hallo,
ich hoffe das ist hier der richtige Bereich!
Seit den digitalen Kameras werden die Ordner mit Bildern überflutet.
Einige Duplikate werden erkannt durch gleiche Namen + Dateigröße + Datum.
Oftmals ist dies nur die halbe Miete, exakt identische Fotos werden durch den Inhalt und MD5 verfahren ebenfalls erfolgreich gefunden.
Aber auch hier bleiben oft immer noch genügend Duplikate unentdeckt, weil das gleiche Bild in verschiedenen Größen vorliegt.
Zum Beispiel Aperture und andere Programme erstellen meist Vorschauansichten und beim Migrieren hat man eine unglaubliche Datenflut zu bearbeiten.
Bei mir sind es aktuell 4.75 Millionen Dateien die im Katalog gelistet werden. :(
Das sichtbare Bild ist zwar gleich aber auf die Daten des Inhaltes, Prüfsumme, Datum und andere Daten helfen hier nicht weiter.

Weis jemand ob es ein Programm gibt welches genau dieses Problem löst.
Oder kann man mit Java eine optische Bildprüfung programmieren um solche Duplikate auf zu spüren?

Danke
Mi
 
X

Xyz1

Gast
Hallo , hier mein Ansatz:
Java:
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;

public class ICompare {
    public static boolean equals(String fn1, String fn2, float threshold) throws IOException {
        BufferedImage i1 = ImageIO.read(new File(fn1));
        BufferedImage i2 = ImageIO.read(new File(fn2));

        Image tmp = i1.getScaledInstance(100, 100, Image.SCALE_FAST);
        BufferedImage i3 = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB);
        Graphics2D g2d = i3.createGraphics();
        g2d.drawImage(tmp, 0, 0, null);
        g2d.dispose();

        tmp = i2.getScaledInstance(100, 100, Image.SCALE_FAST);
        BufferedImage i4 = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB);
        g2d = i4.createGraphics();
        g2d.drawImage(tmp, 0, 0, null);
        g2d.dispose();

        int wrongs = 0;
        for (int y = 0; y < 100; y++) {
            for (int x = 0; x < 100; x++) {
                int rgb1 = i3.getRGB(x, y);
                int gray1 = (((rgb1 >> 16) & 0xFF) + ((rgb1 >> 8) & 0xFF) + ((rgb1 & 0xFF))) / 3;
                int rgb2 = i4.getRGB(x, y);
                int gray2 = (((rgb2 >> 16) & 0xFF) + ((rgb2 >> 8) & 0xFF) + ((rgb2 & 0xFF))) / 3;
                if (Math.abs(gray1 - gray2) >= 10) {
                    wrongs++;
                }
            }
        }
        System.out.println(1.0 - wrongs / 10000.0);
        return 1.0 - wrongs / 10000.0 >= threshold;
    }

    public static void main(String[] args) throws IOException {
        System.out.println(equals("C:\\Users\\\\Desktop\\th2.jpg", "C:\\Users\\\\Desktop\\th2.jpg", 0.5f));
        System.out.println(equals("C:\\Users\\\\Desktop\\th1.jpg", "C:\\Users\\\\Desktop\\th2.jpg", 0.5f));
        System.out.println(equals("C:\\Users\\\\Desktop\\th1.jpg", "C:\\Users\\\\Desktop\\th3.jpg", 0.5f));
        System.out.println(equals("C:\\Users\\\\Desktop\\th2.jpg", "C:\\Users\\\\Desktop\\th3.jpg", 0.5f));
    }
}

Folgende Testbilder:
th1
th1.jpg

th2
th2.jpg

th3
th3.jpg

Ausgabe:
Code:
1.0
true
0.5502
true
0.12270000000000003
false
0.11019999999999996
false
 
X

Xyz1

Gast
Mir fällt gerade auf, dass das mit einem Ordner mit nur 20 Bildern schon recht lange braucht:
Java:
		// ...
		ArrayList<Object[]> res = new ArrayList<Object[]>();
		for (int i = 0; i < paths.size(); i++) {
			for (int j = i + 1; j < paths.size(); j++) {
				float t = equals(paths.get(i).toString(), paths.get(j).toString(), 0.6f);
				if (t >= 0.6f) {
					res.add(new Object[] { paths.get(i).toString(), paths.get(j).toString(), t });
				}
			}
		}
		Collections.sort(res, new Comparator<Object[]>() {
			@Override
			public int compare(Object[] o1, Object[] o2) {
				int i1 = Float.compare((float) o2[2], (float) o1[2]);
				return i1;
			}
		});
		for (Object[] objects : res) {
			System.out.printf("%40s %40s %10s %n", objects);
		}


Das ist der Nachteil bei Bildervergleichen ;)
 

MiMa

Top Contributor
Vielen Dank für die Code-Vorschläge.
Aber wie arbeitet der Algorithmus?
Wenn ich mir ein Bild anschaue und dann das nächst, weis ich das die anders aussehen.
Aber der PC kann das so nicht, wie wird denn hier vor gegangen?
Mit Grafik habe ich in Java bisher noch nicht gearbeitet und kenne daher einige Funktionen oder Befehle nicht.
Ein Duplikat sollte erkannt werden wenn das gleiche Bild sagen wir 1200x800 pixel ist und das gleiche Bild in 600x400 pixel groß ist (Originalbild, Vorschaubild).

Ich kann mich morgen erst darum kümmern und würde mal fragen ob der Code das Duplikat erkennt, wenn die Testbilder in unterschiedlicher Auflösung als Duplikat erkannt wird?

Danke
Mi
 

mihe7

Top Contributor
Wenn du jedes Bild mit jedem anderen vergleichen willst, sind das sehr sehr viele Vergleiche. Da hilft auch keine "Beschleunigung" des Programms.
Wenn die Bilder tatsächlich optisch identisch sind, sollte das in O(n log n) möglich sein.

Die Skalierung auf 8x8-Pixel, dann Helligkeitswerte mit Threshold filtern (hell/dunkel), so erhält man einen 64-Bit-Hash. Sortieren, durchlaufen, fertig :)
 
X

Xyz1

Gast
Java:
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.nio.file.FileVisitResult;
import java.nio.file.FileVisitor;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import javax.imageio.ImageIO;
import javax.swing.JFileChooser;

public class ICompare {
	public static int[][] getGrayscale(String fn) throws IOException {
		int[][] r = new int[8][8];

		BufferedImage i1 = ImageIO.read(new File(fn));
		Image tmp = i1.getScaledInstance(8, 8, Image.SCALE_FAST);
		BufferedImage i3 = new BufferedImage(8, 8, BufferedImage.TYPE_INT_ARGB);
		Graphics2D g2d = i3.createGraphics();
		g2d.drawImage(tmp, 0, 0, null);
		g2d.dispose();

		for (int y = 0; y < 8; y++) {
			for (int x = 0; x < 8; x++) {
				int rgb1 = i3.getRGB(x, y);
				int gray1 = (((rgb1 >> 16) & 0xFF) + ((rgb1 >> 8) & 0xFF) + ((rgb1 & 0xFF))) / 3;
				r[y][x] = gray1;
			}
		}
		return r;
	}

	public static float equals(int[][] a, int[][] b, float threshold) {
		int c = 0;
		for (int y = 0; y < 8; y++) {
			for (int x = 0; x < 8; x++) {
				if (Math.abs(a[y][x] - b[y][x]) >= 10) {
					c++;
				}
			}
		}
		System.out.println((1.0f - c / 64.0f >= threshold) + " " + (1.0f - c / 64.0f));
		return 1.0f - c / 64.0f;
	}

	public static void main(String[] args) throws IOException {
		final float threshold = 0.45f;
		ArrayList<Path> paths = new ArrayList<Path>();
		JFileChooser jfc = new JFileChooser();
		jfc.setFileSelectionMode(JFileChooser.DIRECTORIES_ONLY);
		jfc.showOpenDialog(null);
		Files.walkFileTree(jfc.getSelectedFile().toPath(), new FileVisitor<Path>() {
			@Override
			public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) throws IOException {
				return FileVisitResult.CONTINUE;
			}

			@Override
			public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
				if (file.toString().toLowerCase().endsWith(".jpg") || file.toString().toLowerCase().endsWith(".jpeg")) {
					paths.add(file);
				}
				return FileVisitResult.CONTINUE;
			}

			@Override
			public FileVisitResult visitFileFailed(Path file, IOException exc) throws IOException {
				return FileVisitResult.CONTINUE;
			}

			@Override
			public FileVisitResult postVisitDirectory(Path dir, IOException exc) throws IOException {
				return FileVisitResult.CONTINUE;
			}
		});
		ArrayList<int[][]> hashes = new ArrayList<int[][]>();
		for (Path path : paths) {
			hashes.add(getGrayscale(path.toString()));
		}
		ArrayList<Object[]> res = new ArrayList<Object[]>();
		for (int i = 0; i < paths.size(); i++) {
			for (int j = i + 1; j < paths.size(); j++) {
				float t = equals(hashes.get(i), hashes.get(j), threshold);
				if (t >= threshold) {
					res.add(new Object[] { paths.get(i).toString(), paths.get(j).toString(), t });
				}
			}
		}
		Collections.sort(res, new Comparator<Object[]>() {
			@Override
			public int compare(Object[] o1, Object[] o2) {
				int i1 = Float.compare((float) o2[2], (float) o1[2]);
				return i1;
			}
		});
		for (Object[] objects : res) {
			System.out.printf("%40s %40s %10s %n", objects);
		}
	}
}
 

MiMa

Top Contributor
Oh das mit den 4 Mio. Bildern hatte ich wohl überlesen :D
Ja das ist übel. Besonders Apple Aperture hat freudig neben den Master Dateien noch diverse Vorschaudateien und anderes erzeugt. Somit wurde alles aufgebläht. Datensicherungen auf externen NAS-Systemen, externe Festplatten als Archive, dann kann sowas schon mal passieren.
Jetzt wo ich keinen Mac mehr habe muss ich alles unter Windows neu strukturieren und habe mich entschieden alles auf Dateibasis in Ordner ab zu legen und mit einem Katalogprogramm das Management zu übernehmen. So ist es Platformunabhängig und da wird nichts aufgebläht.
Also Frühjahrsputz in den Fotodateien. :cool:
Fotos.JPG

Zum Algorithmus würde ich gerne mehr erfahren.
Werden die Bilder Pixel für Pixel miteinander verglichen?
Grauwerte, Helligkeiten, 8x8 pixel vergleichen?
Bitte mal kurz erklären.
Danke
Mi
 
Zuletzt bearbeitet:

MiMa

Top Contributor
Java:
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.nio.file.FileVisitResult;
import java.nio.file.FileVisitor;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import javax.imageio.ImageIO;
import javax.swing.JFileChooser;

public class ICompare {
    public static int[][] getGrayscale(String fn) throws IOException {
        int[][] r = new int[8][8];

        BufferedImage i1 = ImageIO.read(new File(fn));
        Image tmp = i1.getScaledInstance(8, 8, Image.SCALE_FAST);
        BufferedImage i3 = new BufferedImage(8, 8, BufferedImage.TYPE_INT_ARGB);
        Graphics2D g2d = i3.createGraphics();
        g2d.drawImage(tmp, 0, 0, null);
        g2d.dispose();

        for (int y = 0; y < 8; y++) {
            for (int x = 0; x < 8; x++) {
                int rgb1 = i3.getRGB(x, y);
                int gray1 = (((rgb1 >> 16) & 0xFF) + ((rgb1 >> 8) & 0xFF) + ((rgb1 & 0xFF))) / 3;
                r[y][x] = gray1;
            }
        }
        return r;
    }

    public static float equals(int[][] a, int[][] b, float threshold) {
        int c = 0;
        for (int y = 0; y < 8; y++) {
            for (int x = 0; x < 8; x++) {
                if (Math.abs(a[y][x] - b[y][x]) >= 10) {
                    c++;
                }
            }
        }
        System.out.println((1.0f - c / 64.0f >= threshold) + " " + (1.0f - c / 64.0f));
        return 1.0f - c / 64.0f;
    }

    public static void main(String[] args) throws IOException {
        final float threshold = 0.45f;
        ArrayList<Path> paths = new ArrayList<Path>();
        JFileChooser jfc = new JFileChooser();
        jfc.setFileSelectionMode(JFileChooser.DIRECTORIES_ONLY);
        jfc.showOpenDialog(null);
        Files.walkFileTree(jfc.getSelectedFile().toPath(), new FileVisitor<Path>() {
            @Override
            public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) throws IOException {
                return FileVisitResult.CONTINUE;
            }

            @Override
            public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
                if (file.toString().toLowerCase().endsWith(".jpg") || file.toString().toLowerCase().endsWith(".jpeg")) {
                    paths.add(file);
                }
                return FileVisitResult.CONTINUE;
            }

            @Override
            public FileVisitResult visitFileFailed(Path file, IOException exc) throws IOException {
                return FileVisitResult.CONTINUE;
            }

            @Override
            public FileVisitResult postVisitDirectory(Path dir, IOException exc) throws IOException {
                return FileVisitResult.CONTINUE;
            }
        });
        ArrayList<int[][]> hashes = new ArrayList<int[][]>();
        for (Path path : paths) {
            hashes.add(getGrayscale(path.toString()));
        }
        ArrayList<Object[]> res = new ArrayList<Object[]>();
        for (int i = 0; i < paths.size(); i++) {
            for (int j = i + 1; j < paths.size(); j++) {
                float t = equals(hashes.get(i), hashes.get(j), threshold);
                if (t >= threshold) {
                    res.add(new Object[] { paths.get(i).toString(), paths.get(j).toString(), t });
                }
            }
        }
        Collections.sort(res, new Comparator<Object[]>() {
            @Override
            public int compare(Object[] o1, Object[] o2) {
                int i1 = Float.compare((float) o2[2], (float) o1[2]);
                return i1;
            }
        });
        for (Object[] objects : res) {
            System.out.printf("%40s %40s %10s %n", objects);
        }
    }
}
Habe mit diesem Code mal 34 Dateien geprüft und "total time: 16 seconds"
 
X

Xyz1

Gast
Image I/O has built-in support for GIF, PNG, JPEG, BMP, and WBMP. Image I/O is also extensible so that developers or administrators can "plug-in" support for additional formats. For example, plug-ins for TIFF and JPEG 2000 are separately available.
;)
 

MiMa

Top Contributor
Danke für den Link der App sieht gut und hilft bestimmt. Das werde ich mir heute auch mal näher ansehen.
Aber gut zu wissen das man das in Java auch machen kann und werde mich auch mit der Programmierung auseinander setzen.
Alles was helfen könnte sehe ich mir an Priorität ist es Duplikate zu entfernen.:)
 
X

Xyz1

Gast
Ggfs. ist das etwas schneller:
Java:
	public static int[][] getGrayscale(String fn) throws IOException {
		System.out.println("Start scaling: " + fn);
		long t0 = System.currentTimeMillis();
		int[][] r = new int[8][8];
		BufferedImage i1 = ImageIO.read(new File(fn));
		BufferedImage i2 = new BufferedImage(8, 8, BufferedImage.TYPE_INT_ARGB);
		Graphics2D g2d = i2.createGraphics();
		g2d.drawImage(i1, 0, 0, 8, 8, null);
		g2d.dispose();
		for (int y = 0; y < 8; y++) {
			for (int x = 0; x < 8; x++) {
				int rgb1 = i2.getRGB(x, y);
				int gray1 = (((rgb1 >> 16) & 0xFF) + ((rgb1 >> 8) & 0xFF) + ((rgb1 & 0xFF))) / 3;
				r[y][x] = gray1;
			}
		}
		long t1 = System.currentTimeMillis();
		System.out.println("Stop scaling: " + (t1 - t0));
		return r;
	}

Aber das dauert bei größeren Bildern 1 Sekunde, ich weiß nicht ob das noch akzeptabel wäre....
 

MiMa

Top Contributor
Ja das kann ich bestätigen, diese Version ist schneller.
Ich habe auch mit dem Programm AntiDuplNet etwas gearbeitet und muss sagen, das es schon sehr hilfreich und einfach zu bedienen ist.
Aber wenn im ersten Durchlauf schon 15.000 Bilder optisch zu sichten sind ist das leider immer noch nicht genug Automatisierung da es ja fast 5 Mio Bilder zu prüfen sind. Auch wenn man mit den Tasten 1, 2, 3 und 5 schon ziemlich schnell Duplikate entfernen kann ist es immer noch ein sehr großer Aufwand.

Daher habe ich mich doch dazu entscheiden selbst ein Programm zu schreiben und mehrere Ergebnislisten zu generieren.
Eine einfache GUI für optische Stichproben wird dann auch zum Einsatz kommen.

1. mehrere Pfade können definiert werden
2. Ergebnisliste 1 mit unterschiedlicher Bildschirmauflösung (meist Vorschaudateien und Thumbnails)
3. Ergebnisliste 2 mit gleicher Bildschirmauflösung (Gleiche Bilder oder mir geringen Abweichungen wie Serienbilder)

Bei der Ergebnisliste 1 können optische Stichproben durchgeführt werden da es immer eine Datei mit einer größeren und einer kleineren Bildauflösung existiert. Die Vormerkung zur Bildlöschung werde ich auf die Datei mit der kleineren Bildauflösung setzen. Wenn die Prüfung fertig ist, soll es eine Schaltfläche geben, die dann die Löschung dieser Ergebnisliste ausführt.

Bei der Ergebnisliste 2 werden nicht nur Stichproben erforderlich, sondern hier muss etwas genauer hingeschaut werden um das zu löschende Bild zu selektieren.

Ich hoffe das ich das mit der GUI hin bekomme, das ich in diesem Bereich erst einmal etwas mit Swing gemacht habe und sonst mit JavaFX eine FXML GUI nur rumprobiert habe.
 
X

Xyz1

Gast
Einen schnelleren Ansatz kann mit Bordmitteln nicht erreicht werden... :(
Es wäre bei Duplikaten sinnvoll, dasjenige Bild mit der geringeren Auflösung zu löschen - aber auch nicht immer... Ein Auswahldialog kann da helfen. Oder eine geschickte Auswahl der Bilder, wie Du sie bereits beschrieben hast.
Ich lasse das auch mal auf meine Fotos los. Die Biester haben aber teilweise 6 MB... Viel Erfolg! ;)
 

MiMa

Top Contributor
Heute muss ich noch die Terassenplatten verkleben, morgen werde ich coden und auch eine GUI dazu machen.
Meinst Du mit Bordmitteln?
Windows Bordmittel oder Java Java Befehlsumfang?
 
X

Xyz1

Gast
Ich meine damit Java-Bordmittel ohne fremde Lib. ;)
Viel Spaß beim Schuften! :D

Btw. Bei mir hats mit dem Duplikate finden eigentlich ganz gut geklappt, aber ich hab auch nur 300 Fotos, und in den Whatsapp/Telegram Ordner habe ich besser gar nicht geguckt.
 

White_Fox

Top Contributor
Etwas schneller geht es sicher noch, wenn du die Arbeit auf mehrere Threads verteilst. Z.B. vier Bilder parallel vergleichst und erst nach Duplikaten suchst und sortierst und erst wenn du alle Duplikate kennst das jeweils beste raussuchst.

Arbeitet die Bibliothek eigentlich mit der Grafikkarte? Wenn nicht, dann könnte man vielleicht darüber noch am Tempo drehen. Auch wenn du für ein Bild nachher drei Sekunden brauchst (etwa Faktor sechs im Vergleich zu 30Bildern/16s) geht das rasend schnell, wenn du ein paar hundert Bilder parallel verarbeiten kannst.
 

White_Fox

Top Contributor
Was meinst du damit, erst nach identischen Bildern suchen?
Indem du am Ende des ersten Durchlaufs z.B. eine ArrayList<ArrayList<String>> hast. Strings sind Dateipfade zu einem Bild, wobei alle Pfade von Bildern, die als Duplikat erkannt wurden, in einer List gespeichert sind. Wenn du über die äußere List iterierst, iterierst du über Dupplikatsammlungen.
Und kannst das Sortieren ebenfalls parallelisieren.

Das dürfte einiges vereinfachen. Vor allem mußt du nicht mehr jedes Bild mit jedem vergleichen, denn wenn du feststellst das ein Bild ein Duplikat des ersten Bildes in einer ArrayList ist, weißt du auch das es ein Duplikat der anderen fünf Bilder ist, die die List auch noch enthält. Und kannst dir allerhand Vergleiche ersparen, in diesem Fall z.B. fünf.

Außerdem hat man erstmal alle Duplikate zusammen, kann sich diese genau ansehen und danach immer noch überlegen nach welchen Kriterien man entfernt und filtert. Und muß sich diese Gedanken nicht schon ganz am Anfang machen. Vielleicht sehen die Bilder nur ähnlich aus, sind aber z.B. tatsächlich verschiedene (Serienaufnahme oder so?) und der TS möchte vielleicht doch beide behalten.
 

MiMa

Top Contributor
Das Parallelisieren finde ich eine sehr gute Idee.
Allerdings schreibst du das man nicht mehr jedes Bild mit jedem Vergleichen muss?
Kannst du mir das bitte etwas ausführlicher erklären?

Parallelisieren heißt doch, das es mehrere Threads startet die alle vergleichen!?
 

White_Fox

Top Contributor
Parallelisieren heißt doch, das es mehrere Threads startet die alle vergleichen!?
Genau.

Was du NICHT machen solltest (Buchstabe heißt gleiches Motiv, Zahl ist andere Version, Größe, usw.):
Java:
//Die Liste pictures enthält die Bilder A1, A2, A3, A4, A5, B1, B2, B3, B4, B5, C1, C2

ArrayList<Pucture> pictures = new ArrayList<>();
//...all pictures to pictures

for(Pictucre pica : pictures){
    for(Picture picb : pictures){
        compare(pica, picb);        //Hier vergleichst du jedes Bild mit jedem, der Aufwand wächst exponentiell
    }
}

Was besser wäre:
Java:
ArrayList<ArrayList<Picture>> sortedPictures = new ArrayList<>();
ArrayList<Picture> unsortedPictures = new ArrayList<>();

//...unsortedPictures füllen...

for(Picture pic : unsortedPictures){

    //Jede ArrayList enthält Duplikate. Ist das erste Bild gleich, sind alle anderen auch gleich.
    for(ArrayList duplicateGroup : sortedPictures){
        if(compare(pic, duplicateGroup.get(0))){
            duplicateGroup.add(pic);
            unsortedPictures.remove(pic);
            continue;    //Weitere Vergleiche nach Erfolg abbrechen
        }
    }
    
    //Nach Durchlauf der ersten Schleife ist klar: Dieses Bild gibt es noch nicht, mache eine neue Duplikatsammlung auf.
    ArrayList<Picture> newDuplicate = new ArrayList<>();
    newDuplicate.add(pic);
    sortedPictues.add(newDuplicate);
    unsortedPictures.remove(pic);
}

Das ist jetzt aber noch nicht parallelisiert. Das würde ungefähr wie folgt gehen:
Java:
public class PicSort extends Thread{

    //All diese Instanzvariablen mußt du im Konstruktor mitgeben
    ArrayList<ArrayList<Picture>> sortedPictures;
    ArrayList<Picture> unsortedPictures;
    EntreeLock sortedPicturesLock;        //Ich weiß nicht mehr genau, wie die Klasse heißt, so oder so ähnlich.
    EntreeLock unsortedPicturesLock;    //Dient jedenfalls der Zugriffskontrolle durch mehrere Threads.
    
    @Overrde
    public void run(){
        while(!unsortedPictures.isEmpty()){
            Picture pic;
            
            unsortedPicturesLock.lock();
            pic = unsortedPictures.get(0);
            unsortedPicturesLock.unlock();
            
            for(ArrayList<Picture> duplicateGroup : sortedPictures){
                //...siehe oben.
                //Zugriff über unsortedPicturesLock regeln nicht vergessen.
            }
        }
    }
}

So oder so ähnlich, ich hab schon eine Weile nicht mehr mit Threads gearbeitet. Ist die jedenfalls klar geworden, warum du nicht jedes Bild mit jedem vergleichen mußt? Wenn du bereits eine Handvoll Bilder hast und weißt: diese Handvoll Bilder sind alle Duplikate. Würdest du dann trotzdem noch ein neues Bild mit jedem vergleichen, oder reicht dir ein Vergleich?


Ne das Langsame ist hier die getGrayscale/hash Methode und diese Methodenaufrufe lassen sich parallelisieren.
Ich vermute mal, der Rechenaufwand steigt auch mit der Bildgröße. Dann wäre es klüger, sortierte Listen zu verwenden:
ArrayList<SortedList<Picture>> sortedPictures;
Über das Comparable-Interface wird dann so sortiert, daß stets das Bild auf Position 0 liegt. die sort-Methode wird immer dann aufgerufen, wenn ein neues Bild eingefügt wurde.

Ach man, ich wünschte meine eigenen Probleme wären so interessant und ansprechend zu lösen.
 

SonoHimitsu

Mitglied
Also ich weiß nicht genau, was du mit "sortierten Listen" meinst, aber die n^2/2 Vergleiche der 64 Grauwerte sind hier nicht das Problem oder das Langsame, das Aufstellen der Grauwerte für jedes Bild benötigt Zeit...
Wenn Bilder nicht exakt in der gleichen w und h vorliegen, also wenn sie reskaliert wurden, kann man ihnen anhand der Größe usw. nicht ansehen, ob sie gleich sind...
 

Barista

Top Contributor
Ein Duplikat sollte erkannt werden wenn das gleiche Bild sagen wir 1200x800 pixel ist und das gleiche Bild in 600x400 pixel groß ist (Originalbild, Vorschaubild)

Wenn es möglich ist, ein Bild mit 1200x800 Pixel in ein Bild mit 600x400 Pixel umzuwandeln, bzw. jedes beliebige Bild in ein bestimmtes einheitliches Format umzuwnadeln, könntest Du jedes Bild in das einheitliche Format umwandeln und von diesem dann eine Prüfsumme erstellen.

Bei gleicher Prüfsumme kannst Du dann noch mal genauer draufschauen, um zu entscheiden, ob es Duplikate sind und wenn ja, welches Bild Du behalten willst.
 

SonoHimitsu

Mitglied
@temi Danke, ich weiß, was sortieren bedeutet - nur ist das ein ziemlich weitläufiger Begriff...

Das ist so ziemlich der neuste Stand, den ich hab:
Java:
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.nio.file.FileVisitResult;
import java.nio.file.FileVisitor;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import javax.imageio.ImageIO;
import javax.swing.JFileChooser;

public class ICompare {
	public static int[] getGrayscale(String fn) throws IOException {
		System.out.println("Start scaling: " + fn);
		long t0 = System.currentTimeMillis();
		int[] r = new int[64];
		BufferedImage i1 = ImageIO.read(new File(fn));
		BufferedImage i2 = new BufferedImage(8, 8, BufferedImage.TYPE_INT_ARGB);
		Graphics2D g2d = i2.createGraphics();
		g2d.drawImage(i1, 0, 0, 8, 8, null);
		g2d.dispose();
		for (int y = 0; y < 8; y++) {
			for (int x = 0; x < 8; x++) {
				int rgb1 = i2.getRGB(x, y);
				int gray1 = (((rgb1 >> 16) & 0xFF) + ((rgb1 >> 8) & 0xFF) + ((rgb1 & 0xFF))) / 3;
				r[y * 8 + x] = gray1;
			}
		}
		long t1 = System.currentTimeMillis();
		System.out.println("Stop scaling: " + (t1 - t0));
		return r;
	}

	public static float equals(int[] a, int[] b, float threshold) {
		int c = 0;
		for (int i = 0; i < 64; i++) {
			if (Math.abs(a[i] - b[i]) >= 10) {
				c++;
			}
		}
		System.out.println((1.0f - c / 64.0f >= threshold) + " " + (1.0f - c / 64.0f));
		return 1.0f - c / 64.0f;
	}

	public static void main(String[] args) throws IOException {
		final float threshold = 0.45f;
		ArrayList<Path> paths = new ArrayList<Path>();
		JFileChooser jfc = new JFileChooser();
		jfc.setFileSelectionMode(JFileChooser.DIRECTORIES_ONLY);
		jfc.showOpenDialog(null);
		Files.walkFileTree(jfc.getSelectedFile().toPath(), new FileVisitor<Path>() {
			@Override
			public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) throws IOException {
				return FileVisitResult.CONTINUE;
			}

			@Override
			public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
				if (file.toString().toLowerCase().endsWith(".jpg") || file.toString().toLowerCase().endsWith(".jpeg")) {
					paths.add(file);
				}
				return FileVisitResult.CONTINUE;
			}

			@Override
			public FileVisitResult visitFileFailed(Path file, IOException exc) throws IOException {
				return FileVisitResult.CONTINUE;
			}

			@Override
			public FileVisitResult postVisitDirectory(Path dir, IOException exc) throws IOException {
				return FileVisitResult.CONTINUE;
			}
		});
		ArrayList<int[]> hashes = new ArrayList<int[]>();
		for (Path path : paths) {
			hashes.add(getGrayscale(path.toString()));
		}
		ArrayList<Object[]> res = new ArrayList<Object[]>();
		for (int i = 0; i < paths.size(); i++) {
			for (int j = i + 1; j < paths.size(); j++) {
				float t = equals(hashes.get(i), hashes.get(j), threshold);
				if (t >= threshold) {
					res.add(new Object[] { paths.get(i).toString(), paths.get(j).toString(), t });
				}
			}
		}
		Collections.sort(res, new Comparator<Object[]>() {
			@Override
			public int compare(Object[] o1, Object[] o2) {
				int i1 = Float.compare((float) o2[2], (float) o1[2]);
				return i1;
			}
		});
		for (Object[] objects : res) {
			System.out.printf("%40s %40s %10s %n", objects);
		}
	}
}

Und wie gesagt, das Berechnen der hashes dauert im Code am längsten - hier würde ich zuerst mit Optimieren ansetzen...

Wenn es möglich ist, [...] und von diesem dann eine Prüfsumme erstellen
ja
 

MiMa

Top Contributor
@White_Fox
so ganz habe ich noch nicht verstanden wie das finden von Duplikate mit den Listen funktionieren soll?
Dun hast also zwei Listen, für unsortierte und sortierte Bilder.
Die Liste für unsortiert ist eine eindimensionale Liste?
Die Liste für unsortiert ist eine mehrdimensionale Liste in der wieder nur Duplikat Listen enthalten sind?
Es wird für jedes Duplikat eine eigene ArrayList erstellt?
Was vergleichst du dann jetzt aus der Liste?
Die ersten beiden Dateien verglichen und wenn sie als Duplikat erkannt wurden, wird nur eines oder beide in die sortierte Liste gepackt?
Wohin kommen die wenn der erste Vergleich kein Duplikat erkannt hat?

Wäre super wenn du mir das anhand von pseudo Code erklären könntest um es zu verstehen.
Danke
 
Zuletzt bearbeitet:

White_Fox

Top Contributor
Ich probiere es mal:
  1. Nimm ein unsortiertes Bild.
  2. Nimm eine Duplikatsammlung.
  3. Nimm ein Bild aus der Duplikatsammlung und vergleiche es mit dem unsortierten Bild.
  4. Wenn das unsortierte Bild ein Duplikat des Bildes aus der Duplikatsammlung ist: Füge das Bild dieser Sammlung hinzu. Fang wieder bei 1. an.
  5. Andernfalls: Nimm die nächste Duplikatsammlung und wiederhole 4.
  6. Wenn es für das Bild noch keine Duplikatsammlung gibt, mach eine neue Sammlung auf und lege das Bild dort hinein.
  7. Fange wieder bei 1. an.
 

MiMa

Top Contributor
Danke, ich denke ich habe es verstanden.
Im Prinzip ist es ein Stapeln von gleichen Bildern die in den ArrayListen gesteckt werden.
Vergleichbar mit einem Kartenspiel mit nur roten, grünen und blauen Farben.
Alle roten Karten kommen auf den roten Stapel, die grünen auf dem grünen Stapel und die blauen auf den blauen Stapel.
Es müssen dann auch nicht alle Karten verglichen werden, da die neu gezogene Karte immer mit den obersten Karte verglichen werden muss und nicht noch mit denen die darunter liegen, weil alle Karten im Stapel gleich sind.
Kommt es so hin?

Und Parallelisieren kann man das indem man nicht immer nur eine Karte zieht, sondern gleich 4?
 

White_Fox

Top Contributor
Gut erkannt, so ist es.

Und Parallelisieren kann man das indem man nicht immer nur eine Karte zieht, sondern gleich 4?
Um mal bei deinem Beispiel zu bleiben: Parallelisierung kannst du erreichen, indem du nicht alleine, sondern mit drei Kumpels die Karten sortierst. Also jeder nimmt für sich eine Karte, und sortiert diese auf den passenden Stapel.

Der Code, den ich oben mit der Klasse PicSorter extends Thread schrieb, würde ja so von mehreren Threads ausgeführt werden.
 

White_Fox

Top Contributor
Noch etwas, was ich mit den sortierten Listen wollte: Die jeweiligen Bilderstapel sollen so sortiert werden, daß das Bild, das am einfachsten zu hashen ist, oben liegt. Da fällt mir noch etwas ein, was das Vergleichen der Bilder erheblich beschleunigen würde.

Statt ArrayList<ArrayList<Picture>> unsortedPictures nimmst du eine HashMap<PictureHash, ArrayList<Picture>>. Dann mußt du bei einem Bildvergleich nicht x-mal hashen (neues Bild und ein Bild aus dem Duplikatstapel, multipliziert mit der Anzahl der Duplikatstapel), sondern genau einmal. Und über die HashMap mußt du nicht iterieren, sondern nimmst den Hash bekommst direkt den richtigen Duplikatstapel.
 

MiMa

Top Contributor
OK, Danke
Das ist alles neues Zeug für mich und muss mich damit erstmal beschäftigen.
Außerdem ist das auch ein Fall für eine GUI und wird daher etwas dauern. ;)
Fragen kommen bestimmt noch etwas später.
 

White_Fox

Top Contributor
Das würde ich mir überlegen. Wenn HashMaps für dich schon neu sind, würde ich dir raten dich erstmal mit dem Wesentlichen zu befassen.

Ich jedenfalls würde für ein Programm, das ich für einen einmaligen Zweck schreibe, mir graphischen Zucker sparen. Da kommt sonst noch so viel mehr Neues für dich hinzu...das wird dich eher ablenken, denke ich.
 

MiMa

Top Contributor
Ja du hast recht, auch in der Vergangenheit habe ich Dateien in separate Verzeichnisse verlagert um vor dem endgültigen Löschen nochmal eine Stichprobe machen zu können. Ich nutze auch ADCSee und Directoy Opus.
Eine GUI kommt dann später und der Code wird dann wie alle Methoden die ich in den letzten 7 Jahren entwickelt habe in die Anwendung.
 

Barista

Top Contributor
so ganz habe ich noch nicht verstanden wie das finden von Duplikate mit den Listen funktionieren soll

Für das Finden von Duplikaten eignet sich die Datenstruktur Set.
Es gibt in Java vorgefertigt (JDK) HashSet und TreeSet.

HashSet ist super schnell. Damit das HashSet funktioniert, müssen die Methoden hashCode und equals korrekt implementiert werden.

Falls Du so viele Dateien hast, dass ds HashSet nicht in den Speicher passt, solltest Du eine Datenbank (mit Index) verwenden.
 

Neue Themen


Oben