Ruta de trama siguiente algoritmos

Question

Tengo una cuadrícula de valores que se parece a la imagen siguiente (el blanco es valores altos, el valor de fondo negro es cero).

Estoy intentando escribir algún tipo de código de seguimiento de camino a empezar por el final de una de las líneas y rastrear hasta el otro extremo, pasando a través de los más altos valores posibles (es decir, el mientras más elegidos estén los píxeles en la línea, mejor) pero llegando al otro extremo.

He estado luchando con esto por un tiempo, y parece que no logro nada. Trato de trabajar. Entonces me pregunté si ya se había desarrollado un algoritmo genérico para este tipo de problema. He realizado muchas búsquedas, pero la mayoría de los algoritmos de ruta parecen estar diseñados para funcionar en vectores/redes, no en cuadrículas de trama como esta.

¿Alguna idea?

Answer 1

No creo que necesite un algoritmo genético o algo ridículo; una buena recursión antigua y una programación dinámica deberían ser suficientes. Inicialmente estoy pensando que usted debería ser capaz de lograr su objetivo haciendo una primera búsqueda de amplitud. Desde su punto de partida, visita a todos los vecinos con puntuaciones mayores que el valor de los caminos: todas las células comienzan en el infinito, y los costos para las celdas negras serían infinitos, y estos son los caminos que puede eliminar). Una vez que llegue a su destino, si puede comunicarse, debería poder retroceder para encontrar la ruta. Es codicioso, pero si tus caminos se comportan bien como estos, debería estar bien.

Para rutas con más gris y giros y vueltas, puede ser una buena idea convertir la imagen ráster a un gráfico, con el peso del borde como los valores de escala de grises de los vecinos (o diferencia en valores de escala de grises, dependiendo de lo que realmente significan estos datos). Por lo tanto, debería poder usar cualquier algoritmo para las rutas más cortas en función de esa interpretación.

Answer 2

La idea más simple probablemente sea usar el A* algorithm, donde cada píxel es un nodo, y el costo del nodo es la oscuridad del píxel.

Actualización: Encontré un buen tutorial.

Answer 3

Una forma de hacer esto:

1. filtro de la imagen para conseguir que más cerca de blanco y negro sólo los píxeles.
2. Dibuja una línea a través de los píxeles blancos. Para hacer esto, comience con un píxel blanco. Traza una línea de ese píxel con el otro a una distancia de 2 (o 3 o más), pero ignora los píxeles cerca de una línea anterior. Continúe hasta cubrir cada píxel no cerrado (2 o 3 píxeles) de una línea. Tendrás que hacer algunos ajustes menores aquí para que funcione bien.
3. Conecta los extremos de las líneas que dibujaste. Si hay dos puntos finales cerca (1 o 2 píxeles?) Entre sí, conéctelos. Deberías terminar con unas líneas compuestas de muchos segmentos cortos, posiblemente con algunos bucles y tenedores.
4. Deshágase de los pequeños bucles de las líneas y separe las líneas en las horquillas, de modo que tenga unas pocas líneas hechas de muchos segmentos cortos.
5. Reduce los puntos. Para cada línea, verifique si es casi recta. Si es así, elimina todos los puntos interiores. De lo contrario, verifique las dos mitades de la línea recursivamente hasta que llegue a las longitudes mínimas del segmento.
6. Opcionalmente puede ajustar una curva spline a través de las líneas en este punto.
7. Beneficio.

Tomará algunos ajustes para conseguir que funcione bien, pero es posible hacerlo de esta manera. Otra variante es delinear las secciones blancas, si son más anchas que 1 o 2 o 3 píxeles, y combinar las líneas dobles después.

Answer 4

Si usted está haciendo esto en gran escala o para la investigación puede probar con la pizca http://en.wikipedia.org/wiki/Ant_colony_optimization, pero si usted está haciendo esto por dinero sólo recoger algo así como inundar http://en.wikipedia.org/wiki/Flood_fill