So messen Sie die Ähnlichkeit von SpatialLines-Objekten

9

Ich habe zwei SpatialLinesObjekte in R erstellt : Zahl.

Diese Objekte wurden folgendermaßen erstellt:

library(sp)
xy <- cbind(x,y)
xy.sp = sp::SpatialPoints(xy)
spl1 <- sp::SpatialLines(list(Lines(Line(xy.sp), ID="a")))

Jetzt möchte ich irgendwie zu dem Schluss kommen, dass dies dieselbe Linie ist, die gedreht und gespiegelt wird, und dass der Unterschied zwischen ihnen gleich 0 ist (dh die Form ist gleich).

Dazu kann man das maptoolsPaket verwenden und die Linie Nr. 1 drehen, z.

spl180 <- maptools::elide(spl1, rotate=180)

Jede gedrehte Linie muss dann mit dem rgeosPaket gegen Linie 2 geprüft werden , z.

hdist <- rgeos::gDistance(spl180, spl2, byid=FALSE, hausdorff=TRUE)

Dies ist jedoch eine so rechenintensive Methode, um SpatialLinesObjekte abzugleichen, insbesondere wenn die Anzahl der Objekte etwa 1000 beträgt.

Gibt es eine clevere Möglichkeit, diesen Job zu erledigen?

PS Darüber hinaus garantiert der oben beschriebene Ansatz nicht alle möglichen Rotationen und Flips.

P.S2. Wenn Zeile 1 in Bezug auf Zeile 2 verkleinert wird, muss die Differenz zwischen Zeile 1 und 2 immer noch gleich 0 sein.

AKTUALISIEREN:

Geben Sie hier die Bildbeschreibung ein

Klausos Klausos
quelle

Antworten:

9

Jede wirklich universelle effektive Methode standardisiert die Darstellungen der Formen so, dass sie sich bei Rotation, Translation, Reflexion oder geringfügigen Änderungen der internen Darstellung nicht ändern.

Eine Möglichkeit, dies zu tun, besteht darin, jede verbundene Form als abwechselnde Folge von Kantenlängen und (vorzeichenbehafteten) Winkeln aufzulisten, beginnend an einem Ende. (Die Form sollte "sauber" sein, da keine Kanten mit null Länge oder gerade Winkel vorhanden sind.) Um diese unter Reflexion unveränderlich zu machen, negieren Sie alle Winkel, wenn der erste Winkel ungleich Null negativ ist.

(Da jede verbundene Polylinie von n Eckpunkten n -1 Kanten hat, die durch n -2 Winkel getrennt sind, habe ich es im folgenden RCode als zweckmäßig empfunden, eine Datenstruktur zu verwenden, die aus zwei Arrays besteht, eines für die Kantenlängen $lengthsund das andere für die Winkel , $angles. Ein Liniensegment hat überhaupt keine Winkel, daher ist es wichtig, Arrays mit der Länge Null in einer solchen Datenstruktur zu behandeln.)

Solche Darstellungen können lexikographisch geordnet werden. Während des Standardisierungsprozesses akkumulierte Gleitkommafehler sollten berücksichtigt werden. Ein elegantes Verfahren würde diese Fehler als Funktion der ursprünglichen Koordinaten schätzen. In der folgenden Lösung wird ein einfacheres Verfahren verwendet, bei dem zwei Längen als gleich angesehen werden, wenn sie sich relativ um einen sehr kleinen Betrag unterscheiden . Winkel können sich absolut nur um einen sehr kleinen Betrag unterscheiden.

Um sie bei Umkehrung der zugrunde liegenden Ausrichtung invariant zu machen, wählen Sie die lexikographisch früheste Darstellung zwischen der der Polylinie und ihrer Umkehrung.

Um mehrteilige Polylinien zu handhaben, ordnen Sie ihre Komponenten in lexikografischer Reihenfolge an.

Um die Äquivalenzklassen unter euklidischen Transformationen zu finden, dann

  • Erstellen Sie standardisierte Darstellungen der Formen.

  • Führen Sie eine lexikografische Sortierung der standardisierten Darstellungen durch.

  • Durchlaufen Sie die sortierte Reihenfolge, um Sequenzen gleicher Darstellungen zu identifizieren.

Die Berechnungszeit ist proportional zu O (n * log (n) * N), wobei n die Anzahl der Merkmale und N die größte Anzahl von Eckpunkten in einem Merkmal ist. Das ist effizient.

Im Übrigen ist es wahrscheinlich erwähnenswert, dass eine vorläufige Gruppierung, die auf leicht zu berechnenden invarianten geometrischen Eigenschaften wie Polylinienlänge, Mittelpunkt und Momenten um diesen Mittelpunkt basiert , häufig angewendet werden kann, um den gesamten Prozess zu rationalisieren. Man muss nur Untergruppen von kongruenten Merkmalen innerhalb jeder solchen vorläufigen Gruppe finden. Die hier angegebene vollständige Methode wäre für Formen erforderlich, die ansonsten so bemerkenswert ähnlich wären, dass solche einfachen Invarianten sie immer noch nicht unterscheiden würden. Einfache Features, die aus Rasterdaten erstellt wurden, können beispielsweise solche Eigenschaften aufweisen. Da die hier angegebene Lösung jedoch ohnehin so effizient ist, dass sie möglicherweise von selbst funktioniert, wenn man sich die Mühe macht, sie zu implementieren.


Beispiel

Die linke Abbildung zeigt fünf Polylinien plus 15 weitere, die durch zufällige Translation, Rotation, Reflexion und Umkehrung der inneren Orientierung (die nicht sichtbar ist) erhalten wurden. Die rechte Figur färbt sie entsprechend ihrer euklidischen Äquivalenzklasse: Alle Figuren einer gemeinsamen Farbe sind kongruent; verschiedene Farben sind nicht kongruent.

Zahl

RCode folgt. Wenn die Eingaben auf 500 Formen, 500 zusätzliche (kongruente) Formen mit einem Mittelwert von 100 Eckpunkten pro Form aktualisiert wurden, betrug die Ausführungszeit auf dieser Maschine 3 Sekunden.

Dieser Code ist unvollständig: Da Res keine native lexikografische Sortierung gibt und ich keine Lust hatte, eine von Grund auf neu zu codieren, führe ich die Sortierung einfach an der ersten Koordinate jeder standardisierten Form durch. Das ist in Ordnung für die hier erstellten zufälligen Formen, aber für Produktionsarbeiten sollte eine vollständige lexikografische Sortierung implementiert werden. Die Funktion order.shapewäre die einzige, die von dieser Änderung betroffen ist. Seine Eingabe ist eine Liste standardisierter Formen sund seine Ausgabe ist die Folge von Indizes, in sdie sie sortiert werden.

#
# Create random shapes.
#
n.shapes <- 5      # Unique shapes, up to congruence
n.shapes.new <- 15 # Additional congruent shapes to generate
p.mean <- 5        # Expected number of vertices per shape
set.seed(17)       # Create a reproducible starting point
shape.random <- function(n) matrix(rnorm(2*n), nrow=2, ncol=n)
shapes <- lapply(2+rpois(n.shapes, p.mean-2), shape.random)
#
# Randomly move them around.
#
move.random <- function(xy) {
  a <- runif(1, 0, 2*pi)
  reflection <- sign(runif(1, -1, 1))
  translation <- runif(2, -8, 8)
  m <- matrix(c(cos(a), sin(a), -sin(a), cos(a)), 2, 2) %*%
    matrix(c(reflection, 0, 0, 1), 2, 2)
  m <- m %*% xy + translation
  if (runif(1, -1, 0) < 0) m <- m[ ,dim(m)[2]:1]
  return (m)
}
i <- sample(length(shapes), n.shapes.new, replace=TRUE)
shapes <- c(shapes, lapply(i, function(j) move.random(shapes[[j]])))
#
# Plot the shapes.
#
range.shapes <- c(min(sapply(shapes, min)), max(sapply(shapes, max)))
palette(gray.colors(length(shapes)))
par(mfrow=c(1,2))
plot(range.shapes, range.shapes, type="n",asp=1, bty="n", xlab="", ylab="")
invisible(lapply(1:length(shapes), function(i) lines(t(shapes[[i]]), col=i, lwd=2)))
#
# Standardize the shape description.
#
standardize <- function(xy) {
  n <- dim(xy)[2]
  vectors <- xy[ ,-1, drop=FALSE] - xy[ ,-n, drop=FALSE]
  lengths <- sqrt(colSums(vectors^2))
  if (which.min(lengths - rev(lengths))*2 < n) {
    lengths <- rev(lengths)
    vectors <- vectors[, (n-1):1]
  }
  if (n > 2) {
    vectors <- vectors / rbind(lengths, lengths)
    perps <- rbind(-vectors[2, ], vectors[1, ])
    angles <- sapply(1:(n-2), function(i) {
      cosine <- sum(vectors[, i+1] * vectors[, i])
      sine <- sum(perps[, i+1] * vectors[, i])
      atan2(sine, cosine)
    })
    i <- min(which(angles != 0))
    angles <- sign(angles[i]) * angles
  } else angles <- numeric(0)
  list(lengths=lengths, angles=angles)
}
shapes.std <- lapply(shapes, standardize)
#
# Sort lexicographically.  (Not implemented: see the text.)
#
order.shape <- function(s) {
  order(sapply(s, function(s) s$lengths[1]))
}
i <- order.shape(shapes.std)
#
# Group.
#
equal.shape <- function(s.0, s.1) {
  same.length <- function(a,b) abs(a-b) <= (a+b) * 1e-8
  same.angle <- function(a,b) min(abs(a-b), abs(a-b)-2*pi) < 1e-11
  r <- function(u) {
    a <- u$angles
    if (length(a) > 0) {
      a <- rev(u$angles)
      i <- min(which(a != 0))
      a <- sign(a[i]) * a
    }
    list(lengths=rev(u$lengths), angles=a)
  }
  e <- function(u, v) {
    if (length(u$lengths) != length(v$lengths)) return (FALSE)
    all(mapply(same.length, u$lengths, v$lengths)) &&
      all(mapply(same.angle, u$angles, v$angles))
    }
  e(s.0, s.1) || e(r(s.0), s.1)
}
g <- rep(1, length(shapes.std))
for (j in 2:length(i)) {
  i.0 <- i[j-1]
  i.1 <- i[j]
  if (equal.shape(shapes.std[[i.0]], shapes.std[[i.1]])) 
    g[j] <- g[j-1] else g[j] <- g[j-1]+1
}
palette(rainbow(max(g)))
plot(range.shapes, range.shapes, type="n",asp=1, bty="n", xlab="", ylab="")
invisible(lapply(1:length(i), function(j) lines(t(shapes[[i[j]]]), col=g[j], lwd=2)))
whuber
quelle
Wenn man willkürliche Dilatationen (oder "Isothetien") in die Gruppe der Transformationen einbezieht, sind die Äquivalenzklassen die Kongruenzklassen der affinen Geometrie . Diese Komplikation ist leicht zu handhaben: Standardisieren Sie beispielsweise alle Polylinien so, dass sie die Gesamtlänge der Einheit haben.
whuber
Vielen Dank. Nur eine Frage: Sollten Formen als SpatialLines oder SpatialPolygons dargestellt werden?
Klausos Klausos
Polygone verursachen eine weitere Komplikation: Ihre Grenzen haben keine bestimmten Endpunkte. Es gibt viele Möglichkeiten, dies zu handhaben, z. B. die Standardisierung der Darstellung, um an (etwa) dem Scheitelpunkt zu beginnen, der zuerst in xy-lexikografischer Reihenfolge sortiert wird und gegen das Uhrzeigersinn um das Polygon herum verläuft. (Ein topologisch "sauberes" verbundenes Polygon hat nur einen solchen Scheitelpunkt.) Ob eine Form als Polygon oder Polylinie betrachtet wird, hängt davon ab, welche Art von Merkmal sie darstellt: Es gibt keine intrinsische Möglichkeit, von einer geschlossenen Liste von Punkten zu sagen, ob dies der Fall ist soll eine Polylinie oder ein Polygon sein.
whuber
Entschuldigen Sie eine einfache Frage, aber ich sollte sie bitten, Ihr Beispiel zu verstehen. Ihre Objektform.std hat sowohl $ Längen als auch $ Winkel. Wenn ich diesen Code jedoch für meine xy-Daten ausführe (z. B. [1,] 3093.5 -2987.8 [2,] 3072.7 -2991.0 usw.), werden weder Winkel geschätzt noch Formen gezeichnet. Wenn ich Plot (Formen [[1]]) ausführe, kann ich meine Polylinie deutlich sehen. Wie sollte ich also Polylinien in R speichern, um Ihren Code anhand meiner Daten testen zu können?
Klausos Klausos
Ich habe mit derselben Datenstruktur begonnen, die Sie erstellt haben: einem Array von (x, y) -Koordinaten. Meine Arrays setzen diese Koordinaten in Spalten (als ob Sie rbind(x,y)statt verwendet hätten cbind(x,y)). Das ist alles was Sie brauchen: Die spBibliothek wird nicht verwendet. Wenn Sie möchten , folgen , was im Detail geschehen ist, schlage ich vor , Sie beginnen mit, sagen wir, n.shapes <- 2, n.shapes.new <- 3, und p.mean <- 1. Dann shapes, shapes.stdusw. sind alle klein genug , um leicht überprüft werden. Der elegante und "richtige" Weg, um mit all dem umzugehen, wäre die Erstellung einer Klasse standardisierter Merkmalsdarstellungen.
whuber
1

Sie verlangen viel mit willkürlicher Rotation und Erweiterung! Ich bin mir nicht sicher, wie nützlich die Entfernung zu Hausdorff sein würde, aber probieren Sie es aus. Mein Ansatz wäre es, die Anzahl der Fälle zu reduzieren, die über billige Daten überprüft werden sollen. Sie können beispielsweise teure Vergleiche überspringen, wenn die Länge der beiden Linestrings kein ganzzahliges Verhältnis ist (unter der Annahme einer ganzzahligen / abgestuften Skalierung ). Sie können auch prüfen, ob der Begrenzungsrahmenbereich oder die konvexen Rumpfbereiche in einem guten Verhältnis stehen. Ich bin sicher, es gibt viele billige Überprüfungen, die Sie gegen den Schwerpunkt durchführen können, wie Abstände oder Winkel von Anfang / Ende.

Nur dann, wenn Sie Skalierung erkennen, machen Sie es rückgängig und führen Sie die wirklich teuren Überprüfungen durch.

Klarstellung: Ich kenne die von Ihnen verwendeten Pakete nicht. Mit Ganzzahlverhältnis meinte ich, Sie sollten beide Abstände teilen, prüfen, ob das Ergebnis eine Ganzzahl ist, wenn nicht, diesen Wert invertieren (möglicherweise haben Sie die falsche Reihenfolge gewählt) und erneut prüfen. Wenn Sie eine Ganzzahl erhalten oder nahe genug sind, können Sie daraus schließen, dass möglicherweise eine Skalierung durchgeführt wurde. Oder es könnten nur zwei verschiedene Formen sein.

Was den Begrenzungsrahmen betrifft, haben Sie wahrscheinlich entgegengesetzte Punkte des Rechtecks, das ihn darstellt, so dass das Herausholen des Bereichs aus ihnen eine einfache Arithmetik ist. Das Prinzip hinter dem Verhältnisvergleich ist dasselbe, nur dass das Ergebnis quadriert wird. Kümmere dich nicht um konvexe Rümpfe, wenn du sie nicht gut aus dem R-Paket herausholen kannst, es war nur eine Idee (wahrscheinlich sowieso nicht billig genug).

lynxlynxlynx
quelle
Vielen Dank. Könnten Sie bitte erklären, wie Sie feststellen können, ob die Länge der beiden Linestrings kein ganzzahliges Verhältnis ist? Ich schätze es auch sehr, wenn Sie ein Beispiel für die Überprüfung geben können, "ob der Begrenzungsrahmenbereich oder die konvexen
Rumpfbereiche
Wenn ich beispielsweise einen räumlichen Begrenzungsrahmen aus räumlichen Daten extrahiere, erhalte ich nur zwei Punkte: spl <- sp :: SpatialLines (Liste (Linien (Linie (xy.sp), ID = i))) b <- bbox ( spl)
Klausos Klausos
Erweiterte den Hauptbeitrag.
Lynxlynxlynx
"Wenn Sie eine Ganzzahl erhalten oder nah genug dran sind, können Sie daraus schließen, dass möglicherweise eine Skalierung durchgeführt wurde." Könnte ein Benutzer nicht eine Skala von 1,4 oder so angewendet haben?
Germán Carrillo
Sicher, aber meine Annahme wurde klargestellt, insbesondere bei späteren Änderungen. Ich stellte mir das Zoomen im Webmap-Stil vor, bei dem man gut eingeschränkt ist.
Lynxlynxlynx
1

Eine gute Methode zum Vergleichen dieser Polylinien wäre, sich auf eine Darstellung als Folge von (Abständen, Drehwinkeln) an jedem Eckpunkt zu stützen: Für eine Linie, die aus Punkten besteht P1, P2, ..., PN, wäre eine solche Folge:

(Abstand (P1P2), Winkel (P1, P2, P3), Abstand (P2P3), ..., Winkel (P (N-2), P (N-1), PN), Abstand (P (N-1) ) PN)).

Entsprechend Ihren Anforderungen sind zwei Linien genau dann gleich, wenn ihre entsprechenden Sequenzen gleich sind (Modulo der Reihenfolge und Winkelrichtung). Der Vergleich von Zahlenfolgen ist trivial.

Indem Sie jede Polyliniensequenz nur einmal berechnen und, wie von lynxlynxlynx vorgeschlagen, die Sequenzähnlichkeit nur für Polylinien mit denselben trivialen Eigenschaften (Länge, Scheitelpunktnummer ...) testen, sollte die Berechnung wirklich schnell sein!

julien
quelle
Das ist die richtige Idee. Damit es tatsächlich funktioniert, müssen jedoch viele Details berücksichtigt werden, z. B. Umgang mit Reflexionen, interne Ausrichtung, Möglichkeit mehrerer verbundener Komponenten und Gleitkomma-Rundungsfehler. Sie werden in der von mir bereitgestellten Lösung besprochen.
whuber
Ja, ich habe nur die Hauptidee beschrieben. Ihre Antwort ist bemerkenswert vollständiger (wie oft :-)
Julien