Algoritmos para segmentos correspondentes

Quais são os melhores algoritmos para combinar segmentos?

Estou tentando corresponder segmentos correspondentes de duas fontes de mapa, uma menos precisa, mas com nomes de segmentos, e outra mais precisa, sem nomes de segmentos. Quero aplicar semi-automaticamente os nomes dos segmentos ao mapa mais preciso.

O algoritmo solicitado tem uma descrição bastante vaga, porque uma "correspondência" não está bem definida e muitos fatores (orientação, comprimento relativo, distância) podem ter peso diferente em diferentes cenários; No entanto, estou procurando um conhecimento básico sobre as abordagens gerais para lidar com esse problema.

As implementações de trabalho para o ambiente de código aberto (PostGIS, bem torneado, ...) são muito bem-vindas.

Segmentos de amostra : Veja a descrição abaixo das imagens.

A distância de Hausdorff pode ser usada: segmentos correspondentes podem ser segmentos "próximos" de acordo com essa distância. É bastante simples calcular em segmentos.

Uma implementação java gratuita está disponível no JTS - consulte Pacote de Distância JTS . Você também pode dar uma olhada no JCS Conflation Suite (agora abandonado, cópia de fontes, por exemplo, em https://github.com/oschrenk/jcs ).

Não sei o que seria o "melhor", porque isso dependerá dos detalhes de seus segmentos.

Uma abordagem geralmente boa é misturar os segmentos em informações geométricas cruciais . Isso incluiria, no mínimo, a localização do centro (x, y), orientação (0 a 180 graus) e comprimento. Com os pesos apropriados aplicados e um pouco de detalhamento da orientação (porque 180 "volta" para 0), você pode aplicar quase qualquer algoritmo estatístico de agrupamento à coleção de todos os segmentos. ( K-significa seria uma boa opção, mas a maioria dos métodos hierárquicos deve funcionar bem. Tais análises de cluster tendem a ser rápidas e fáceis de aplicar.) Idealmente, os segmentos ocorrerão em pares (ou singletons para segmentos sem correspondência) e o restante é fácil.

Uma maneira de lidar com a questão da orientação é fazer uma cópia dos segmentos rotulados. Adicione 180 graus à orientação da primeira cópia, se for menor que 90, e subtraia 180 graus da orientação. Isso aumenta seu conjunto de dados (obviamente), mas de outra forma não altera o algoritmo de nenhuma maneira.

Os pesos são necessários porque diferenças de coordenadas, comprimentos e orientações podem significar coisas bastante diferentes em relação às semelhanças de seus segmentos correspondentes. Em muitas aplicações, as diferenças entre segmentos surgem de diferenças nas localizações de seus pontos de extremidade. Como uma aproximação aproximada, podemos esperar que a variação típica nos comprimentos dos segmentos seja aproximadamente a mesma que a variação típica entre seus pontos finais. Portanto, os pesos associados a x, ye comprimento devem ser os mesmos. A parte complicada é ponderar a orientação, porque a orientação não pode ser equiparada à distância e, pior ainda, segmentos curtos teriam mais probabilidade de serem mal orientados do que segmentos longos. Considere um método de tentativa e erro que iguale alguns graus de desorientação ao tamanho de um intervalo típico entre os segmentos e depois ajuste-o até que o procedimento pareça funcionar bem. Para orientação, deixeL seja um comprimento típico de segmento. Uma mudança de orientação por um ângulo pequeno t graus varrerá uma distância de aproximadamente L / 2 * t / 60 (os 60 aproximam o número de graus em um radiano), que é L / 120 vezes t . Isso sugere começar com pesos unitários para x, ye comprimento e um peso de L / 120 para a orientação.

Em resumo , esta sugestão é:

1. Faça cópias dos segmentos rotulados (conforme descrito no parágrafo sobre como refinar a orientação).

2. Converta cada segmento no quádruplo (x, y, comprimento, orientação L / 120 *) em que L é um comprimento típico de segmento.

3. Execute uma análise de cluster dos quádruplos. Use um bom pacote estatístico ( R é gratuito).

4. Use a saída da análise de cluster como uma tabela de pesquisa para associar segmentos rotulados a segmentos não rotulados próximos.

Eu trabalhei em um projeto com um requisito semelhante há cerca de 5 anos. Envolveu a combinação de coordenadas das linhas centrais das ruas (com precisão de coordenadas relativamente alta) com os links da rede de tráfego do Sistema de Monitoramento de Desempenho da Rodovia (HPMS).

Na época, o FHWA não forneceu nenhuma ferramenta para fazer esse tipo de coisa. Isso pode ter mudado, você pode querer verificar. Mesmo se você não estiver trabalhando com dados da estrada, as ferramentas ainda podem ser relevantes.

Eu escrevi com o ArcGIS, mas o algoritmo deve funcionar em código aberto, desde que ofereça recursos de rastreamento semelhantes ao ISegmentGraph :

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link

Aqui vem uma ideia

Se você separar uma das cadeias de linhas para comparar e testar se os pontos de vértice estão a alguma distância da outra cadeia de linhas para comparar, você poderá controlar o teste de várias maneiras.

esses exemplos funcionam no PostGIS (quem poderia adivinhar :-))

Primeiro, se dissermos que existe uma correspondência se todos os pontos de vértice em uma cadeia de linhas na tabela_1 forem 0,5 metros (unidades do mapa) ou mais próximos de uma cadeia de linhas na tabela_2:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

Podemos dizer que existe uma correspondência se mais de 60% dos pontos de vertex em uma cadeia de linhas da tabela_1 estiverem a uma distância de uma cadeia de linhas da tabela_2

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

Ou podemos aceitar que um ponto não esteja dentro do alcance:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

Você também precisará executar a consulta com a tabela_1 e a tabela_2 em funções invertidas.

Eu não sei o quão rápido será. Atualmente, ST_Dumppoints é uma função sql no PostGIS e não uma função C que a torna mais lenta do que deveria. Mas acho que será bem rápido de qualquer maneira.

Os índices espaciais ajudarão muito o ST_Dwithin a ser eficaz.

HTH Nicklas

Eu escrevi um código para lidar com a correspondência de segmentos de linha desleixada (e sobrepô-los) no Boundary Generator. Eu escrevi a matemática (bastante elementar) por trás dela aqui: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html . O código é de código aberto e vinculado a partir dessa postagem do blog.

O código segue uma abordagem realmente simples:

• Um teste de segmento-segmento que informará se dois segmentos de linha se sobrepõem dentro de determinadas tolerâncias de ângulo e distância e a quantidade de sobreposição.
• Um índice espacial quick'n'dirty que elimina a necessidade de testar todos os segmentos de linha no conjunto de dados contra todos os outros segmentos de linha no conjunto de dados.

A principal vantagem dessa abordagem é obter botões bem precisos para ângulo, distâncias e comprimento de sobreposição válidos; no lado negativo, geralmente não é uma maneira de medir a semelhança de dois segmentos de linha, por isso é muito mais difícil, por exemplo, fazer agrupamentos estatísticos para determinar as correspondências prováveis ​​- você está preso aos botões precisos.

Nota: Estou supondo que, com chops SQL suficientes, você possa colocar o teste de segmento-segmento em uma cláusula WHERE ... :)

Felicidades!

Implementamos um protótipo aproximado para correspondência de mapas aqui , que é relativamente fácil de usar. É baseado no mecanismo de roteamento de código aberto e escrito em Java. O algoritmo usado é descrito aqui .