Fotos Duplikate finden

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

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! ;)
 
M

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

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

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

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

SonoHimitsu

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

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

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

Barista

Bekanntes Mitglied
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.
 
S

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
 
M

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

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

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

Neue Themen


Oben