Zusammenhängende Punkte in Raster

Hallo,
ich bin schon länger am googeln aber bisher war nichts passendes dabei. Zur Erklärung, ich vergleiche 2 Sammlungen von Bildern, Gleiche Anzahl, gleiche Benennung, gleiche Größe, unterschiedliche Tools zur Erzeugung.
Ich habe ein Objekt für die Sammlung, darin Objekte für die Bilder und in denen ein Objekt pro verglichenen Pixel. Das Vergleichen funktioniert soweit auch gut, allerdings würde ich gerne noch optional Stellen herausfiltern an denen mehrere Pixel nebeneinander(Anzahl einstellbar) abweichen. Fällt jemanden dazu eventuell ein bekannter Algorithmus ein? Ich habe schon überlegt mit Quadranten zu arbeiten, allerdings wäre dies wenig zweckdienlich da zusammenhängende Pixel in mehreren Quadranten liegen könnten.

Schon mal vielen Dank an alle die sich mit mir Gedanken machen.

Mir fehlt da noch etwas Verständnis…

Du hast also 2 Bilder und findest darin unterschiede.

Was Du jetzt willst ist, die Unterschiede in “Bereiche” zusammenzufassen?

Würde ich so machen:```class Change implements Comparable{
private final long x;
private final long y;
public Change(long x, long y){ this.x=x; this.y=y;}

public boolean isNeighbour(Change other){ return Math.abs(x-other.x) < 2 && Math.abs(y-other.y) < 2; }

public int compareTo(Change other){
int compare = Long.valueOf(x).compareTo(Long.valueOf(other.x));
return compare!=0?compare: Long.valueOf(y).compareTo(Long.valueOf(other.y));
}
}

class ChangeCluster{
private final Collection changes = new HashSet<>();

public boolean isConnected(Change change}
if(changes.isEmpty()){ changes.add(change); return true; }

 for(Change myChange:changes)
    if(myChange.isNeigbour(change)){ changes.add(change); return true; }

}

class ClusterBuilder{
public Collection findClusters(long[][] changeCoordinates){
Collection sortedChanges = sortChanges(changeCoordinates);
Collection clusters = buildClusters(sortedChanges);
// ggf. “ein Pixel Cluster” hier wieder raus filtern.
return clusters;
}
private Collection sortChanges(long[][]){
Collection sortedChanges = new TreeSet();
for(long[] changePoint: changeCoordinates){
sortedChanges.add(new Change(changePoint[0],changePoint[1]);
}
}
private Collection buildClusters(Collection sortedChanges){
Collection clusters = new HashSet<>();
ChangeCluster cluster = new ChangeCluster();
for(Change change : sortedChanges){
if(!cluster.isConnected(change)){
clusters.add(cluster);
cluster= new ChangeCluster();
cluster.isConnected(change);
}
}
clusters.add(cluster);
return clusters;
}
}```

bye
TT

Bei deinem Code sind ein paar Logik und Syntaxfehler drin. Habe mich allerdings daran orientiert. Allerdings arbeite ich nicht mit Rastern sondern mit Objekten. Hier die Umsetzung:


    private int x;

    private int y;

    public static String[] RGB_CHANNEL = {"r", "g", "b"};

    private static int MAX_RGB_DIFF = 3 * 255;

    private double rgbAccordance;

    public boolean isDistinction() {
        return rgbAccordance < 99.999;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public void setX(int x) {
        this.x = x;
    }

    public void setY(int y) {
        this.y = y;
    }

    public double getRgbAccordance() {
        return rgbAccordance;
    }


    public boolean isNeighbour(DistinctionPosition other) {
        return Math.abs(x - other.x) < 2 && Math.abs(y - other.y) < 2;
    }

    protected void calcRgbAccordance(Map<String, Integer> rgbMap1, Map<String, Integer> rgbMap2) {
        int diff = Math.abs(rgbMap1.get(RGB_CHANNEL[0]) - rgbMap2.get(RGB_CHANNEL[0]))
                + Math.abs(rgbMap1.get(RGB_CHANNEL[1]) - rgbMap2.get(RGB_CHANNEL[1]))
                + Math.abs(rgbMap1.get(RGB_CHANNEL[2]) - rgbMap2.get(RGB_CHANNEL[2]));
        rgbAccordance = (MAX_RGB_DIFF - diff) / MAX_RGB_DIFF * 100;
    }

    @Override
    public int compareTo(DistinctionPosition o) {
        int c = Long.valueOf(x).compareTo(Long.valueOf(o.x));
        return c != 0 ? c : Long.valueOf(y).compareTo(Long.valueOf(o.y));
    }```

```public class PixelComp extends DistinctionPosition {

    public PixelComp(int x, int y, Map<String, Integer> rgbMap1, Map<String, Integer> rgbMap2) {
        this(x, y);
        calcRgbAccordance(rgbMap1, rgbMap2);
    }

    private PixelComp(int x, int y) {
        setX(x);
        setY(y);
    }

}```

```public class DistinctionCluster {

    private final Collection<DistinctionPosition> distinctionPositions = new HashSet<>();

    public DistinctionCluster(DistinctionPosition dp){
        distinctionPositions.add(dp);
    }

    public boolean isConnected(DistinctionPosition dp) {

        for (DistinctionPosition temp : distinctionPositions) {
            if (temp.isNeighbour(dp)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        for(DistinctionPosition dp: distinctionPositions){
            sb.append(dp.getX()+","+dp.getY()+";");
        }
        return "DistinctionCluster{" +
                "distinctionPositions=" + sb.toString() +
                '}';
    }

    public void addDistinctionPosition(DistinctionPosition distinctionPosition){
        distinctionPositions.add(distinctionPosition);
    }

    public Collection<DistinctionPosition> getDistinctionPositions(){
        return distinctionPositions;
    }

    public boolean containsDistinctionPosition(DistinctionPosition distinctionPosition){
        return  distinctionPositions.contains(distinctionPosition);
    }```

```public class DistinctionClusterBuilder {

    private Collection<DistinctionPosition> distincts;

    /**
     * @param distincts Liste aller PixelComp Objekte die eine Abweichung aufweisen
     * @return Die ermittelten DistinctionCluster Objekte
     */
    public Collection<DistinctionCluster> findClusters(Collection<DistinctionPosition> distincts) {
        this.distincts = new TreeSet<>(new Comparator<DistinctionPosition>() {
            @Override
            public int compare(DistinctionPosition o1, DistinctionPosition o2) {
                if (Integer.compare(o1.getX(), o2.getX()) != 0) {
                    return Integer.compare(o1.getX(), o2.getX());
                } else if (Integer.compare(o1.getY(), o2.getY()) != 0) {
                    return Integer.compare(o1.getY(), o2.getY());
                }
                return 0;
            }
        });
        this.distincts.addAll(distincts);
        Collection<DistinctionCluster> clusters = buildClusters();
        // ggf. "ein Pixel Cluster" hier wieder raus filtern.
        return clusters;
    }

    private DistinctionCluster createCluster(DistinctionPosition basePos) {
        DistinctionCluster cluster = new DistinctionCluster(basePos);
        distincts.remove(basePos);
        Collection<DistinctionPosition> unregisteredNeighbours = getNeighbourDistinctionPositions(basePos);
        boolean isExtensible = !unregisteredNeighbours.isEmpty();
        while (isExtensible) {
            Collection<DistinctionPosition> tempNeighbours = new HashSet<>();
            for (DistinctionPosition dp : unregisteredNeighbours) {
                cluster.addDistinctionPosition(dp);
                this.distincts.remove(dp);
                tempNeighbours.addAll(getNeighbourDistinctionPositions(dp));
            }
            unregisteredNeighbours.removeAll(unregisteredNeighbours);
            isExtensible = false;
            for (DistinctionPosition dp : tempNeighbours) {
                if (!unregisteredNeighbours.contains(dp)&&distincts.contains(dp)) {
                    isExtensible = true;
                    unregisteredNeighbours.add(dp);
                }
            }
        }
        return cluster;
    }

    private Collection<DistinctionPosition> getNeighbourDistinctionPositions(DistinctionPosition basePos) {
        Collection<DistinctionPosition> neighbourDistinctPositions = new HashSet<>();
        for (DistinctionPosition dp : this.distincts) {
            if (basePos.isNeighbour(dp)) {
                neighbourDistinctPositions.add(dp);
            }

        }
        return neighbourDistinctPositions;
    }

    private Collection<DistinctionCluster> buildClusters() {
        Collection<DistinctionCluster> clusters = new HashSet<>();
        while (!this.distincts.isEmpty()) {
            clusters.add(createCluster(this.distincts.iterator().next()));
        }
        return clusters;
    }
}```

Kann sicher noch optimiert werden funktioniert allerdings vorerst. In späteren Schritten gehe ich jetzt daran die Cluster nach Größen zu filtern.

Kleinigkeit im ‘Kann sicher noch optimiert werden’ :

        int c = Long.valueOf(x).compareTo(Long.valueOf(o.x));
        return c != 0 ? c : Long.valueOf(y).compareTo(Long.valueOf(o.y));
    }
                if (Integer.compare(o1.getX(), o2.getX()) != 0) {
                    return Integer.compare(o1.getX(), o2.getX());
                } else if (Integer.compare(o1.getY(), o2.getY()) != 0) {
                    return Integer.compare(o1.getY(), o2.getY());
                }
                return 0;
            }

erstaunlich unterschiedlicher Aufbau, einmal Integer.compare(), warum im anderen Falle nicht dann auch Long.compare()?
wenn nicht eh genauso Integer.compare() reicht, es sind ja ints,
überhaupt könnte die zweite Methode die erste nutzen, return o1.compareTo(o2);
bzw. extra Methode hier gar nicht benötigt

auffällig jedenfalls weiterhin dass bei der ersten Variante eine Zwischenvariable c verwendet wird,
in der zweiten Variante unschöne Wiederholung, hier also die erste Variante besser,
ebenso ist das else if unnötig: auch wenn der y-Vergleich 0 ergibt ist das die passende Rückgabe, ganz wie in Variante 1

schließlich noch minimal fraglich ob es die Integer.compare()-Methode braucht,

        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }

sicher nicht ohne Grund in der API, aber das einfache c = x-y; würde auch negativen Wert, 0 oder positiven Wert liefern, nur nicht genau -1, 0, 1

Dann schlage ich mal

public static final Comparator<DistinctionPosition> COMPARATOR = 
    Comparator.<DistinctionPosition>comparingInt(dp -> dp.getX())
        .thenComparingInt(dp -> dp.getY());

vor.

Bevor das in einen Comparator-Krieg ausartet muss ich mal dazwischen gehen, die Methode ist in der Lösung sowieso nicht von großer Relevanz(Da Sortierung unnötig geworden). Und Landei nett gemacht, allerdings arbeite ich noch mit dem guten alten JDK 7.

Aber nur um die Gemüter zu beruhigen:... new Comparator<DistinctionPosition>() { @Override public int compare(DistinctionPosition o1, DistinctionPosition o2) { int c=Integer.compare(o1.getX(),o2.getX()); return c==0 ? Integer.compare(o1.getY(),o2.getY()):c; } } ...

ach, diese zweite Methode steht in einem Comparator für TreeSet,
wie gesagt, wenn die Klasse selber schon Comparable implementiert, dürfte das ganz überflüssig sein
new TreeSet<>(distincts); reicht

und für Comparable innerhalb einer Klasse kommt man mit der Comparator-Spielerei nicht weit :wink:
es sei denn von compareTo den Comparator aufgerufen…

[quote=SlaterB]schließlich noch minimal fraglich ob es die Integer.compare()-Methode braucht,
sicher nicht ohne Grund in der API, aber das einfache c = x-y; würde auch negativen Wert, 0 oder positiven Wert liefern, nur nicht genau -1, 0, 1[/quote]
Das hänft davon ab, wie oft x negativ und y gleichzeitig im Bereich Interger.MAX_VAL ist…
;o)

bye
TT