Como medir a similaridade dos objetos SpatialLines

9

Eu criei dois SpatialLinesobjetos em R: figura.

Esses objetos foram criados desta maneira:

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

Agora, quero concluir de alguma forma que essa é a mesma linha girada e invertida, e que a diferença entre eles é igual a 0 (ou seja, a forma é igual).

Para fazer isso, pode-se usar o maptoolspacote e girar a linha 1, por exemplo:

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

Cada linha girada deve então ser verificada em relação à linha 2 usando o rgeospacote, por exemplo:

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

No entanto, essa é uma maneira computacionalmente cara de corresponder SpatialLinesobjetos, especialmente se o número de objetos for em torno de 1000.

Existe alguma maneira inteligente de fazer esse trabalho?

PS Além disso, a abordagem descrita acima não garante todas as rotações e giros possíveis.

P.S2. Se a linha 1 for reduzida com relação à linha 2, a diferença entre as linhas 1 e 2 ainda deve ser igual a 0.

ATUALIZAR:

insira a descrição da imagem aqui

Klausos Klausos
fonte

Respostas:

9

Qualquer método eficaz verdadeiramente de uso geral padronizará as representações das formas para que não sejam alteradas mediante rotação, translação, reflexão ou alterações triviais na representação interna.

Uma maneira de fazer isso é listar cada forma conectada como uma sequência alternada de comprimentos de arestas e ângulos (sinalizados), começando de uma extremidade. (A forma deve ser "limpa" no sentido de não ter arestas de comprimento zero ou ângulos retos.) Para tornar isso invariante sob reflexão, negue todos os ângulos se o primeiro diferente de zero for negativo.

(Como qualquer polilinha conectada de n vértices terá n -1 arestas separadas por n -2 ângulos, achei conveniente no Rcódigo abaixo usar uma estrutura de dados que consiste em duas matrizes, uma para os comprimentos das arestas $lengthse a outra para o ângulos, $angles. um segmento de linha não terá ângulos de todo, por isso é importante para manipular matrizes de comprimento zero, de tal estrutura de dados.)

Tais representações podem ser ordenadas lexicograficamente. Alguma permissão deve ser feita para erros de ponto flutuante acumulados durante o processo de padronização. Um procedimento elegante estimaria esses erros em função das coordenadas originais. Na solução abaixo, é usado um método mais simples, no qual dois comprimentos são considerados iguais quando diferem em uma quantidade muito pequena em uma base relativa. Os ângulos podem diferir apenas em uma quantidade muito pequena em uma base absoluta.

Para torná-los invariantes sob a reversão da orientação subjacente, escolha a representação lexicograficamente mais antiga entre a da polilinha e sua reversão.

Para lidar com polilinhas de várias partes, organize seus componentes em ordem lexicográfica.

Para encontrar as classes de equivalência sob transformações euclidianas ,

  • Crie representações padronizadas das formas.

  • Execute um tipo lexicográfico das representações padronizadas.

  • Faça um passe pela ordem classificada para identificar sequências de representações iguais.

O tempo de computação é proporcional a O (n * log (n) * N) em que n é o número de recursos e N é o maior número de vértices em qualquer recurso. Isso é eficiente.

Provavelmente, vale a pena mencionar de passagem que um agrupamento preliminar baseado em propriedades geométricas invariantes facilmente calculáveis, como comprimento da polilinha, centro e momentos sobre esse centro, geralmente pode ser aplicado para otimizar todo o processo. É preciso apenas encontrar subgrupos de características congruentes em cada um desses grupos preliminares. O método completo dado aqui seria necessário para formas que, de outra forma, seriam tão notavelmente semelhantes que tais invariantes simples ainda não as distinguiriam. Recursos simples construídos a partir de dados rasterizados podem ter essas características, por exemplo. No entanto, como a solução fornecida aqui é tão eficiente de qualquer maneira, que, se alguém se esforçar para implementá-la, ela poderá funcionar bem por si só.


Exemplo

A figura da esquerda mostra cinco polilinhas e mais 15 que foram obtidas através de translação aleatória, rotação, reflexão e reversão da orientação interna (que não é visível). A figura da direita os pinta de acordo com sua classe de equivalência euclidiana: todas as figuras de uma cor comum são congruentes; cores diferentes não são congruentes.

Figura

Rcódigo a seguir. Quando as entradas foram atualizadas para 500 formas, 500 formas extras (congruentes), com uma média de 100 vértices por forma, o tempo de execução nesta máquina foi de 3 segundos.

Esse código está incompleto: como Rnão possui uma classificação lexicográfica nativa e não senti vontade de codificá-lo do zero, simplesmente executei a classificação na primeira coordenada de cada forma padronizada. Isso será bom para as formas aleatórias criadas aqui, mas para o trabalho de produção, uma classificação lexicográfica completa deve ser implementada. A função order.shapeseria a única afetada por essa alteração. Sua entrada é uma lista de formas padronizadas se sua saída é a sequência de índices em sque a classificaria.

#
# 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
fonte
Quando se inclui dilatações arbitrárias (ou "isotetias") no grupo de transformações, as classes de equivalência são as classes de congruência da geometria afim . Essa complicação é facilmente tratada: padronize todas as polilinhas para ter um comprimento total da unidade, por exemplo.
whuber
Muito obrigado. Apenas uma pergunta: as formas devem ser representadas como SpatialLines ou SpatialPolygons?
Klausos Klausos
Os polígonos criam outra complicação: seus limites não têm pontos finais definidos. Existem várias maneiras de lidar com isso, como padronizar a representação para começar (digamos) o vértice que classifica primeiro na ordem lexicográfica xy e prosseguir no sentido anti-horário em torno do polígono. (Um polígono conectado topologicamente "limpo" terá apenas um desses vértices.) Se uma forma é considerada um polígono ou polilinha depende do tipo de recurso que representa: não há uma maneira intrínseca de dizer se há uma lista fechada de pontos. destinado a ser uma polilinha ou polígono.
whuber
Desculpe por uma pergunta simples, mas devo pedir que ele entenda seu exemplo. Seu objeto shapes.std possui $ comprimentos e $ ângulos. Se, no entanto, eu executar esse código nos meus dados xy (por exemplo, [1,] 3093,5 -2987,8 [2,] 3072,7 -2991,0 etc), ele não estima ângulos, nem desenha formas. Se eu executar plotagem (formas [[1]])), então posso ver claramente minha polilinha. Então, como devo salvar polilinhas no R para poder testar seu código nos meus dados?
Klausos Klausos
Comecei com a mesma estrutura de dados que você: uma matriz de coordenadas (x, y). Minhas matrizes colocam essas coordenadas em colunas (como se você tivesse usado em rbind(x,y)vez de cbind(x,y)). É tudo o que você precisa: a spbiblioteca não é usada. Se você gostaria de acompanhar o que é feito em detalhes, eu sugiro que você começa com, digamos, n.shapes <- 2, n.shapes.new <- 3, e p.mean <- 1. Então shapes, shapes.stdetc. são todos pequenos o suficiente para serem facilmente inspecionados. A maneira elegante - e "correta" - de lidar com tudo isso seria criar uma classe de representações padronizadas de recursos.
whuber
1

Você está pedindo muito com rotação e dilatação arbitrárias! Não tenho certeza de quão útil a distância de Hausdorff estaria lá, mas confira. Minha abordagem seria reduzir o número de casos a serem verificados através de dados baratos. Por exemplo, você pode pular comparações caras se o comprimento das duas cadeias de linhas não for uma proporção inteira ( assumindo a escala inteira / graduada ). Da mesma forma, você pode verificar se a área da caixa delimitadora ou suas áreas convexas do casco estão em uma boa proporção. Tenho certeza de que há muitos cheques baratos que você poderia fazer contra o centróide, como distâncias ou ângulos do início / fim.

Somente então, se você detectar a escala, desfaça-a e faça as verificações realmente caras.

Esclarecimento: Não conheço os pacotes que você está usando. Por razão de número inteiro, eu quis dizer que você deve dividir as duas distâncias, verificar se o resultado é um número inteiro, se não, inverter esse valor (pode ser que você tenha escolhido a ordem errada) e verificar novamente. Se você obtiver um número inteiro ou aproximar-se o suficiente, poderá deduzir que talvez houvesse dimensionamento em andamento. Ou poderia ser apenas duas formas diferentes.

Quanto à caixa delimitadora, você provavelmente obteve pontos opostos do retângulo que o representa, portanto, tirar a área deles é uma aritmética simples. O princípio por trás da comparação de proporção é o mesmo, apenas que o resultado seria ao quadrado. Não se preocupe com cascos convexos se você não conseguir tirá-los do pacote R com agrado, foi apenas uma ideia (provavelmente não é barata o suficiente).

lynxlynxlynx
fonte
Muito obrigado. Você poderia explicar como detectar se o comprimento das duas cadeias de linhas não é uma proporção inteira? Além disso, agradeço muito se você puder dar um exemplo de verificação "se a área da caixa delimitadora ou as áreas convexas do casco estão em uma boa proporção"
Klausos Klausos
Por exemplo, se eu extrair uma caixa delimitadora espacial de dados espaciais, receberei apenas dois pontos: spl <- sp :: SpatialLines (list (Lines (Line (xy.sp), ID = i))) b <- bbox ( spl)
Klausos Klausos
Extensão do post principal.
Lynxlynxlynx
"Se você obtiver um número inteiro ou fechar o suficiente, poderá deduzir que talvez houvesse escalonamento em andamento". Um usuário não poderia ter aplicado uma escala de 1,4 ou mais?
Germán Carrillo
Claro, mas minha suposição foi esclarecida, especialmente em edições posteriores. Eu estava imaginando o zoom no estilo de mapa da web, onde um é bastante limitado.
Lynxlynxlynx
1

Um bom método para comparar essas polilinhas seria confiar em uma representação como uma sequência de (distâncias, ângulos de virada) em cada vértice: Para uma linha composta de pontos P1, P2, ..., PN, essa sequência seria:

(distância (P1P2), ângulo (P1, P2, P3), distância (P2P3), ..., ângulo (P (N-2), P (N-1), PN), distância (P (N-1 ) PN)).

De acordo com seus requisitos, duas linhas são iguais se, e somente se, as seqüências correspondentes forem as mesmas (módulo a ordem e a direção do ângulo). Comparar sequências numéricas é trivial.

Calculando cada sequência de polilinha apenas uma vez e, como sugerido por lynxlynxlynx, testando a similaridade de sequência apenas para polilinha com as mesmas características triviais (comprimento, número de vértices ...), o cálculo deve ser muito rápido!

julien
fonte
Essa é a ideia certa. Para que ele funcione, muitos detalhes precisam ser abordados, como lidar com reflexões, orientação interna, possibilidade de múltiplos componentes conectados e erro de arredondamento de ponto flutuante. Eles são discutidos na solução que forneci.
whuber
Sim, eu apenas descrevi a idéia principal. A sua resposta é notavelmente mais completa (como muitas vezes :-)
julien