# Fotos Duplikate finden



## MiMa (24. Apr 2020)

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


----------



## Xyz1 (25. Apr 2020)

Hallo , hier mein Ansatz:

```
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


th2


th3


Ausgabe:

```
1.0
true
0.5502
true
0.12270000000000003
false
0.11019999999999996
false
```


----------



## Xyz1 (25. Apr 2020)

Mir fällt gerade auf, dass das mit einem Ordner mit nur 20 Bildern schon recht lange braucht:

```
// ...
		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 (25. Apr 2020)

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


----------



## Xyz1 (25. Apr 2020)

MiMa hat gesagt.:


> würde mal fragen ob der Code das Duplikat erkennt, wenn die Testbilder in unterschiedlicher Auflösung als Duplikat erkannt wird


ja


----------



## mihe7 (25. Apr 2020)

Das dürfte man erheblich beschleunigen können, wenn man das Bild auf 8x8 Pixel skaliert.


----------



## Xyz1 (25. Apr 2020)

Es wäre auch schon eine Beschleunigung, wenn man die Bildpunkte zwischenspeichert.


----------



## fhoffmann (25. Apr 2020)

MiMa hat gesagt.:


> Bei mir sind es aktuell 4.75 Millionen Dateien die im Katalog gelistet werden.


Wenn du jedes Bild mit jedem anderen vergleichen willst, sind das sehr sehr viele Vergleiche. Da hilft auch keine "Beschleunigung" des Programms.


----------



## mihe7 (25. Apr 2020)

fhoffmann hat gesagt.:


> 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


----------



## Xyz1 (25. Apr 2020)

Oh das mit den 4 Mio. Bildern hatte ich wohl überlesen


----------



## Xyz1 (25. Apr 2020)

```
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 (25. Apr 2020)

Xyz1 hat gesagt.:


> Oh das mit den 4 Mio. Bildern hatte ich wohl überlesen


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. 


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


----------



## MiMa (25. Apr 2020)

Xyz1 hat gesagt.:


> ```
> import java.awt.Graphics2D;
> import java.awt.Image;
> import java.awt.image.BufferedImage;
> ...


Habe mit diesem Code mal 34 Dateien geprüft und "total time: 16 seconds"


----------



## Xyz1 (25. Apr 2020)

MiMa hat gesagt.:


> Habe mit diesem Code mal 34 Dateien geprüft und "total time: 16 seconds"


Das liegt daran: `.getScaledInstance(8, 8, Image.SCALE_FAST);`
Es gibt auch schnellere image scaling libraries...


----------



## MiMa (26. Apr 2020)

Funktioniert das auch mit anderen Bildformaten wie .TIF, .png, Canon Raw .cr2 ??
Hab hier mal was zu Algorithmen gefunden Bildvergleich Algorithmen damit ich ein bessere Verständnis davon bekomme.


----------



## Xyz1 (26. Apr 2020)

> 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.


----------



## Dukel (26. Apr 2020)

Schau dir mal den Quellcode von z.B. http://antidupl.sourceforge.net/english/index.html?page=download.html an. Dann siehst du, wie man sowas machen kann.
Ich würde ein Tool suchen, wenn du z.B. Ähnliche Bilder (bearbeitet) finden möchtest, wird es sehr komplex.


----------



## Xyz1 (26. Apr 2020)

Na klar gibt es auch Tools dafür, aber das war glaube ich nicht seine Frage...


----------



## thecain (26. Apr 2020)

MiMa hat gesagt.:


> Weis jemand ob es ein Programm gibt welches genau dieses Problem löst.


Eigtl schon


----------



## MiMa (26. Apr 2020)

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.


----------



## Xyz1 (26. Apr 2020)

Ggfs. ist das etwas schneller:

```
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 (27. Apr 2020)

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.


----------



## Xyz1 (27. Apr 2020)

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 (27. Apr 2020)

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?


----------



## Xyz1 (27. Apr 2020)

Ich meine damit Java-Bordmittel ohne fremde Lib. 
Viel Spaß beim Schuften!  

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 (30. Apr 2020)

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.


----------



## SonoHimitsu (30. Apr 2020)

White_Fox hat gesagt.:


> und erst nach Duplikaten suchst


Was meinst du damit, erst nach identischen Bildern suchen?

Am Multithreading ist etwas dran!


----------



## White_Fox (30. Apr 2020)

SonoHimitsu hat gesagt.:


> 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 (1. Mai 2020)

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!?


----------



## SonoHimitsu (1. Mai 2020)

Ne das Langsame ist hier die getGrayscale/hash Methode und diese Methodenaufrufe lassen sich parallelisieren.


----------



## White_Fox (1. Mai 2020)

MiMa hat gesagt.:


> 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.):

```
//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:

```
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:

```
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?




SonoHimitsu hat gesagt.:


> 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 (1. Mai 2020)

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...


----------



## temi (1. Mai 2020)

White_Fox hat gesagt.:


> Arbeitet die Bibliothek eigentlich mit der Grafikkarte?


Das wollte ich auch schon anmerken. Speziell das Rescaling sollte über die Graka doch flotter gehen.


----------



## Barista (1. Mai 2020)

MiMa hat gesagt.:


> 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.


----------



## White_Fox (1. Mai 2020)

SonoHimitsu hat gesagt.:


> Also ich weiß nicht genau, was du mit "sortierten Listen" meinst











						Java Collections sort()
					

Learn to sort a collection of objects by field either in default ordering using Comparable or custom sorting using Comparator interfaces.




					howtodoinjava.com


----------



## SonoHimitsu (1. Mai 2020)

@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:

```
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...



Barista hat gesagt.:


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


ja


----------



## SonoHimitsu (1. Mai 2020)

Err, sorry, nicht @temi sondern @White_Fox .


----------



## MiMa (1. Mai 2020)

@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


----------



## White_Fox (1. Mai 2020)

Ich probiere es mal:

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


----------



## MiMa (1. Mai 2020)

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 (1. Mai 2020)

MiMa hat gesagt.:


> Kommt es so hin?


Gut erkannt, so ist es.



MiMa hat gesagt.:


> 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 (1. Mai 2020)

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 (1. Mai 2020)

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 (1. Mai 2020)

MiMa hat gesagt.:


> GUI


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 (1. Mai 2020)

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 (3. Mai 2020)

MiMa hat gesagt.:


> 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.


----------

