Bilder vergleichen auf gleichheit oder ähnlichkeit

[Allrounder93]

moin,

ich habe mich bereits erkundig bei Tante google, aber leider nichts passendes gefunden.

Frage
Ich würde gerne Bilder auf gleichheit oder ähnlichkeit überprüfen.

History
Ich habe einen Pool von Bildner aus den vergangenen Jahren angesammelt, durch viele Backups und hin und her haben sich nun viele doppelt eingeschlichen bzw. wurden auch komprimiert und sind somit vom Bildinhalt gleich nur haben eine schlechtere Qualität...

Idee
Kennt jemand eine methode / Funktion, mit der ich zwei Bilder überprüfen kann?
Auf gleichheit dürfte dies über den Hash-Wert bzw. die Prüfsumme funktionieren... gibts dafür eine funktion?
bei Ähnlichkeitsprüfung bin ich dann aber nun überfragt^^ Kennt jemand dafür eine Lösung?

Gruß Chris

 

[DrZoidberg]

Vielleicht hilft dir das hier.
Image similarity search with LIRE - Mayflower Blog

 

[DrZoidberg]

Hier ist mal ein ganz einfacher Ansatz. Ich skaliere die beiden Bilder erst mal auf die selbe Grösse und berechne dann die durchschnittliche Abweichung der Farbwerte.

import java.awt.image.BufferedImage;
import java.awt.Graphics2D;
import javax.imageio.ImageIO;
import java.io.File;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.ImageIcon;
import java.util.Arrays;

public class Test {
    
    private static BufferedImage scale(BufferedImage img, int width, int height) {
        BufferedImage temp = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = temp.createGraphics();
        g.scale(1.0*width/img.getWidth(), 1.0*height/img.getHeight());
        g.drawImage(img, 0, 0, null);
        g.dispose();
        return temp;
    }
    
    private static int[] splitRGB(int rgb) {
        return new int[] {(rgb>>>16)&0xFF, (rgb>>>8)&0xFF, rgb&0xFF};
    }
    
    private static void println(int[] array) {
        System.out.println(Arrays.toString(array));
    }
    
    private static int[] getData(BufferedImage image) {
        return image.getRGB(0, 0, image.getWidth(), image.getHeight(), null, 0, image.getWidth());
    }
    
    private static void display(int[] imageData, int width, int height) {
        BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        image.setRGB(0, 0, width, height, imageData, 0, width);
        JFrame frame = new JFrame();
        frame.add(new JLabel(new ImageIcon(image)));
        frame.pack();
        frame.setVisible(true);
    }
    
    public static void main(String[] args) throws Exception {
        BufferedImage image1 = ImageIO.read(new File("1.jpg"));
        BufferedImage image2 = ImageIO.read(new File("2.jpg"));
        
        int width = Math.min(image1.getWidth(), image2.getWidth());
        int height = Math.min(image1.getHeight(), image2.getHeight());
        image1 = scale(image1, width, height);
        image2 = scale(image2, width, height);
        
        int[] data1 = getData(image1);
        int[] data2 = getData(image2);
        
        display(data1, width, height);
        display(data2, width, height);
        
        long[] diff = {0,0,0};
        for(int i = 0; i < data1.length; i++) {
            int[] pixel1 = splitRGB(data1[i]);
            int[] pixel2 = splitRGB(data2[i]);
            diff[0] += pixel1[0]-pixel2[0];
            diff[1] += pixel1[1]-pixel2[1];
            diff[2] += pixel1[2]-pixel2[2];
        }
        
        double diffR = diff[0]*1.0/data1.length;
        double diffG = diff[1]*1.0/data1.length;
        double diffB = diff[2]*1.0/data1.length;
        
        System.out.println(diffR + ", " + diffG + ", " + diffB);
    }
}

 

[Allrounder93]

Genial...
Kommentare wären jetzt noch wünschenswert, aber die welt ist kein Honigkuchen^^

Was genau sagen nu die Differzenen von Rot Grün Blau aus?
wenn 0 gleich und so größer die abweichung um so anders ist das bild?

andre Frage, bei mir öffnen sich die bilder jeweils, kann ich dies display methode ganz löschen oder über sehe ich da was?

 

[DrZoidberg]

Da ich selbst auch tausende von Bildern auf meiner Platte rumliegen habe, habe ich das Programm mal halbwegs fertig geschrieben. Ich muss sagen es hat mir sehr dabei geholfen alle überflüssigen Bilder von meinem Rechner zu schmeissen.
Ich hätte nicht gedacht, dass es so gut funktioniert. Meine erste Version war etwas langsam. Hätte ewig gedauert meine gesamte Festplatte zu durchforsten. Deshalb habe ich da ein paar Optimierungen reingebaut und das ganze zusätzlich parallelisiert.
Jetzt schafft es 30,000 Bilder in ein paar Minuten.
Kommentare habe ich da leider keine drin. Vielleicht ergänze ich das noch.
Wenn du das Programm testen willst, musst du einfach nur den String "e:/downloads" abändern. Das Ergebnis der Suche wird in die Datei out.txt geschrieben.

import java.awt.image.BufferedImage;
import java.awt.Graphics2D;
import javax.imageio.ImageIO;
import java.io.File;
import java.io.PrintWriter;
import java.io.ByteArrayInputStream;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Comparator;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import java.util.concurrent.Callable;

public class Images {
    
    private static BufferedImage scale(BufferedImage img, int width, int height) {
        BufferedImage temp = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = temp.createGraphics();
        g.scale(1.0*width/img.getWidth(), 1.0*height/img.getHeight());
        g.drawImage(img, 0, 0, null);
        g.dispose();
        return temp;
    }
    
    private static int[] splitRGB(int rgb) {
        return new int[] {(rgb>>>16)&0xFF, (rgb>>>8)&0xFF, rgb&0xFF};
    }

    private static double[] averageBrightness(int[] data) {
        double[] b = {0, 0, 0};
        for(int i = 0; i < data.length; i++) {
            int[] pixel = splitRGB(data[i]);
            b[0] += pixel[0];
            b[1] += pixel[1];
            b[2] += pixel[2];
        }
        b[0] /= data.length;
        b[1] /= data.length;
        b[2] /= data.length;
        return b;
    }
    
    private static double[] averageDifference(int[] data1, int[] data2) {
        double[] diff = {0,0,0};
        for(int i = 0; i < data1.length; i++) {
            int[] pixel1 = splitRGB(data1[i]);
            int[] pixel2 = splitRGB(data2[i]);
            diff[0] += Math.abs(pixel1[0]-pixel2[0]);
            diff[1] += Math.abs(pixel1[1]-pixel2[1]);
            diff[2] += Math.abs(pixel1[2]-pixel2[2]);
        }
        diff[0] /= data1.length;
        diff[1] /= data1.length;
        diff[2] /= data1.length;
        return diff;
    }
    
    private static int[] getData(BufferedImage image) {
        return image.getRGB(0, 0, image.getWidth(), image.getHeight(), null, 0, image.getWidth());
    }

    private static int images = 0;
    private static synchronized void updateImageCounter() {
        images++;
        if(images%100 == 0) System.out.print(".");
    }
    
    private static synchronized void updateImageCounter(int n) {
        for(int i = 0; i < n; i++) updateImageCounter();
    }
    
    private static synchronized byte[] readAllBytes(File file) {
        try {
            return Files.readAllBytes(file.toPath());
        } catch(Exception e) {
            return new byte[0];
        }
    }
    
    private static BufferedImage readImage(File file) {
        try {
            byte[] array = readAllBytes(file);
            return ImageIO.read(new ByteArrayInputStream(array));
        } catch(Exception e) {
            return null;
        }
    }
    
    private static ArrayList<File> findAllPictures(File path) {
        ArrayList<File> list = new ArrayList<>();
        if(path == null) return list;
        
        File[] files = path.listFiles();
        if(files == null) return list;
        
        for(File file: files) {
            if(file.isDirectory()) list.addAll(findAllPictures(file));
            else if(file.isFile()) {
                String name = file.getName();
                if(name.endsWith(".jpg") || name.endsWith(".jpeg") ||
                   name.endsWith(".png") || name.endsWith(".gif") || 
                   name.endsWith(".bmp")) {
                    list.add(file);
                    updateImageCounter();
                }
            }
        }
        
        return list;
    }
    
    private static <T> List<List<T>> splitList(List<T> list, int n) {
        int chunkSize = list.size()/n + 1;
        ArrayList<List<T>> lists = new ArrayList<>();
        for(int start = 0; start < list.size(); start += chunkSize) {
            int end = start+chunkSize;
            if(end > list.size()) end = list.size();
            lists.add(list.subList(start, end));
        }
        return lists;
    }
    
    static class FileAB {
        final File file;
        final double[] ab;
        FileAB(File file, double[] ab) {
            this.file = file;
            this.ab = ab;
        }
        
        @Override
        public String toString() {
            return "(" + ab[0] + ", " + ab[1] + ", " + ab[2] + ") " + file.getName(); 
        }
    }
    
    static class CompRed implements Comparator<FileAB> {
        final double value;
        
        CompRed(double value) {
            this.value = value;
        }
        
        public int compare(FileAB a, FileAB b) {
            double va = Math.abs(a.ab[0]-value);
            double vb = Math.abs(b.ab[0]-value);
            if(va < vb) return -1;
            else if(va > vb) return 1;
            else return 0;
        }
    }
    
    static class CompGreen implements Comparator<FileAB> {
        final double value;
        
        CompGreen(double value) {
            this.value = value;
        }
        
        public int compare(FileAB a, FileAB b) {
            double va = Math.abs(a.ab[1]-value);
            double vb = Math.abs(b.ab[1]-value);
            if(va < vb) return -1;
            else if(va > vb) return 1;
            else return 0;
        }
    }
    
    static class CompBlue implements Comparator<FileAB> {
        final double value;
        
        CompBlue(double value) {
            this.value = value;
        }
        
        public int compare(FileAB a, FileAB b) {
            double va = Math.abs(a.ab[2]-value);
            double vb = Math.abs(b.ab[2]-value);
            if(va < vb) return -1;
            else if(va > vb) return 1;
            else return 0;
        }
    }
    
    private static List<FileAB> calcBrightness(List<File> pictures) {
        ArrayList<FileAB> result = new ArrayList<>();
        for(File file: pictures) {
            double[] b = null;
            try {
                BufferedImage image = readImage(file);
                int[] data = getData(image);
                b = averageBrightness(data);
            } catch(Exception e) {
            }
            if(b != null) {
                result.add(new FileAB(file, b));
            }
        }
        return result;
    }
    
    private static List<List<FileAB>> findMatchingPairs(List<FileAB> list) {
        ArrayList<List<FileAB>> result = new ArrayList<>();
        ArrayList<int[]> data = new ArrayList<>();
        for(FileAB fab: list) {
            BufferedImage image = readImage(fab.file);
            image = scale(image, 100, 100);
            data.add(getData(image));
        }
        boolean[] isUsed = new boolean[data.size()];
        for(int k = 0; k < data.size(); k++) {
            if(isUsed[k]) continue;
            ArrayList<FileAB> matches = new ArrayList<>();
            for(int l = k+1; l < data.size(); l++) {
                if(isUsed[l]) continue;
                double[] diff = averageDifference(data.get(k), data.get(l));
                if(diff[0] < 20 && diff[1] < 20 && diff[2] < 20) {
                    matches.add(list.get(l));
                    isUsed[l] = true;
                }
            }
            if(!matches.isEmpty()) {
                matches.add(list.get(k));
                result.add(matches);
            }
        }
        return result;
    }
    
    public static void main(String[] args) throws Exception {
        long start = System.nanoTime();
        System.out.println("Suche Bilder:");
        ArrayList<File> pictures = findAllPictures(new File("e:/downloads"));
        
        System.out.println();
        System.out.println(pictures.size() + " Bilder gefunden");
        images = 0;
        System.out.println();
        System.out.println("Berechne durchschnittliche Helligkeit:");
        
        ArrayList<FileAB> picturesPlusAB = new ArrayList<>();
        
        ExecutorService threadPool = Executors.newFixedThreadPool(8);
        
        {
            List<List<File>> picturesSplit = splitList(pictures, 256);
            ArrayList<Future<List<FileAB>>> futures = new ArrayList<>();
            for(List<File> _picturesChunk: picturesSplit) {
                final List<File> picturesChunk = _picturesChunk;
                futures.add(threadPool.submit(new Callable<List<FileAB>>() {
                    public List<FileAB> call() {
                        List<FileAB> result = calcBrightness(picturesChunk);
                        updateImageCounter(result.size());
                        return result;
                    }
                }));
            }
            
            for(Future<List<FileAB>> future: futures) {
                picturesPlusAB.addAll(future.get());
            }
        }
        
        Collections.sort(picturesPlusAB, new CompRed(0));
        
        images = 0;
        System.out.println(); System.out.println();
        System.out.println("Vergleiche Bilder:");
        
        ArrayList<Future<List<List<FileAB>>>> futures = new ArrayList<>();
        
        for(int i = 0; i < picturesPlusAB.size();) {
            double[] ab = picturesPlusAB.get(i).ab;
            int end = i+1;
            while(end < picturesPlusAB.size() && Math.abs(picturesPlusAB.get(end).ab[0] - ab[0]) < 2) end++;
            List<FileAB> subList1 = picturesPlusAB.subList(i, end);
            Collections.sort(subList1, new CompGreen(ab[1]));
            
            end = 0;
            while(end < subList1.size() && Math.abs(subList1.get(end).ab[1] - ab[1]) < 2) end++;
            List<FileAB> subList2 = subList1.subList(0, end);
            Collections.sort(subList2, new CompBlue(ab[2]));
            
            end = 0;
            while(end < subList2.size() && Math.abs(subList2.get(end).ab[2] - ab[2]) < 2) end++;
            final List<FileAB> subList3 = subList2.subList(0, end);

            if(!subList3.isEmpty()) {
                futures.add(threadPool.submit(new Callable<List<List<FileAB>>>() {
                    public List<List<FileAB>> call() {
                        List<List<FileAB>> result = findMatchingPairs(subList3);
                        updateImageCounter(subList3.size());
                        return result;
                    }
                }));
            }
            
            i += subList3.size();
            subList1 = subList1.subList(subList3.size(), subList1.size());
            Collections.sort(subList1, new CompRed(0));
        }
        
        PrintWriter out = new PrintWriter(new File("out.txt"));

        for(Future<List<List<FileAB>>> future: futures) {
            for(List<FileAB> list: future.get()) {
                for(FileAB fab: list) {
                    out.println(fab.file.getPath());
                }
                out.println("--------------------------------------------------------------------------");
            }
        }
        
        out.flush();
        out.close();
        
        threadPool.shutdown();
        
        long end = System.nanoTime();
        double time = (end-start)/1e9;
        System.out.println(); System.out.println();
        System.out.println("time = " + time);
    }
}

 

[Allrounder93]

uff... Da Blick ich nun wircklich nicht mehr durch^^

Kommentare habe ich da leider keine drin.

Die wären zum verstehen echt angebracht^^ Die Funktion ist echt klasse, aber grobe kommentare zum verstehen fänd ich echt klasse... für den :idea:-Effekt.


----------------------------------------------------------------------


Also für meine Anwendung bräuchte ich eigentlich eine Classe, die ich mit einem Konstrucktor(srcFile, dstFile) erstelle und mit folgenden getter getduplicates(), der mir alle gefundenen Duplikate mit folgenden Werte übergibt.
srcFile
dstFile
abweichung von srcFile zu dstFile

 

[Allrounder93]

Also ich hab mich mal probiert... Scheitere aber kläglich ;( an den fehlenden Kommentaren^^

Naja wäre es möglich Kommentar anzufügen oder den Code so umzuschriben, sodass ich:

• zwei Pfade angeben kann die vergleichen werden
• Alle Funde in eine List gespeichert werden im Format Eintrag1 (FundImErstenPfad,FundImZweitenPfad)
• Keine Löschung erfolgt sondern nur eine Auflistung in eine Liste (siehe Punkt 2)

Gruß Chris

 

[Allrounder93]

also mich habe im Code Fehler...

Exception in thread "main" java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError: Java heap space
at java.util.concurrent.FutureTask.report(Unknown Source)
at java.util.concurrent.FutureTask.get(Unknown Source)
at test.test.main(test.java:266)
Caused by: java.lang.OutOfMemoryError: Java heap space
at java.awt.image.BufferedImage.getRGB(Unknown Source)
at test.test.getData(test.java:64)
at test.test.calcBrightness(test.java:197)
at test.test.access$0(test.java:191)
at test.test$1.call(test.java:258)
at test.test$1.call(test.java:1)
at java.util.concurrent.FutureTask.run(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)

 

[Ikaron]

also mich habe im Code Fehler...

Das bedeutet, dass Java nicht genug Arbeitsspeicher zur Verfügung steht. Das kann daran liegen, dass du z.B. immer Bilder speicherst, die du gar nicht mehr brauchst o.Ä.

Andere Frage, könnte die schnelle Fourier-Transformation hier eigentlich Verwendung finden? Damit kann man ja die Frequenz einer Farbe über das ganze Bild verteilt errechnen. Untergliedert in kleine Abschnitte würden doch die Ergebnisse immer genauer werden, sehe ich das richtig?