Algoritmo de inundación de salto

Clase de algoritmos utilizados para calcular funciones relacionadas con la distancia.

El algoritmo de inundación por salto ( JFA ) es un algoritmo de inundación utilizado en la construcción de diagramas de Voronoi y transformadas de distancia . El JFA fue presentado por Rong Guodong en un simposio de la ACM en 2006. ^[1]

El JFA tiene atributos deseables en el cálculo de GPU , especialmente por su rendimiento eficiente. Sin embargo, es sólo un algoritmo aproximado y no siempre calcula el resultado correcto para cada píxel, aunque en la práctica los errores son pocos y la magnitud de los errores es generalmente pequeña. ^[1]

Implementación

La formulación original del JFA es sencilla de implementar.

Tome una cuadrícula de píxeles ^[2] (como una imagen o textura). Todos los píxeles comenzarán con un color "indefinido" a menos que sea un píxel "semilla" de color único. A medida que avanza el JFA, cada píxel indefinido se rellenará con un color correspondiente al de un píxel inicial. ${\displaystyle N\times N}$

Para cada tamaño de paso , ejecute una iteración del JFA: ${\displaystyle k\in \{{\frac {N}{2}},{\frac {N}{4}},\dots ,1\}}$

Itere sobre cada píxel en . ${\displaystyle p}$ ${\displaystyle (x,y)}$

Para cada vecino en donde : ${\displaystyle q}$ ${\displaystyle (x+i,y+j)}$ ${\displaystyle i,j\in \{-k,0,k\}}$

si no está definido y está coloreado, cambie el color de 's ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

si está coloreado y está coloreado, si dónde y están los píxeles iniciales para y , respectivamente, entonces cambie el color de 's. ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle dist(p,s)>dist(p,s')}$ ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

Tenga en cuenta que los píxeles pueden cambiar de color más de una vez en cada paso y que JFA no especifica un método para resolver casos en los que las distancias son iguales; por lo tanto, se utiliza el color del último píxel verificado arriba.

El JFA finaliza después de evaluar el último píxel en el tamaño del último paso. Independientemente del contenido de los datos iniciales, el bucle más interno se ejecuta un total de veces sobre cada píxel, para una complejidad computacional general de . ${\displaystyle 9\log _{2}(N)}$ ${\displaystyle O(N^{2}\log _{2}(N))}$

Variantes

Algunas variantes de JFA son:

• Pase adicional al final : JFA+1 tiene un paso adicional con un tamaño de paso de 1, es decir, los tamaños de paso son N/2, N/4, ..., 1, 1; JFA+2 tiene dos pasadas adicionales con tamaños de paso de 2 y 1, es decir, los tamaños de paso son N/2, N/4, ..., 1, 2, 1; JFA tiene pases adicionales, es decir, los tamaños de paso son N/2, N/4, ..., 1, N/2, N/4, ..., 1. JFA+1 tiene muchos menos errores que JFA y JFA. +2 tiene aún menos errores. ^[1] ${\displaystyle ^{2}}$ ${\displaystyle \log _{2}(N)}$

• Pase adicional al principio : 1+JFA tiene un paso adicional con un tamaño de paso de 1, es decir, los tamaños de paso son 1, N/2, N/4, ..., 1. 1+JFA tiene una tasa de error muy baja (similar JFA+2) y el mismo rendimiento que JFA+1. ^[3]
• Media resolución: esta variante ejecuta JFA normal a media resolución, amplía el resultado a la resolución original y ejecuta una pasada adicional con un tamaño de paso de 1. Debido a que la mayoría de las pasadas tienen solo la mitad de resolución, la velocidad de esta variante es mucho más rápida. que el JFA de resolución completa. ^[3]

Usos

El algoritmo de inundación por salto y sus variantes se pueden utilizar para calcular mapas de Voronoi ^{[1] [3]} y teselaciones centroidales de Voronoi (CVT), ^[4] generar campos de distancia , ^[5] representación de nubes de puntos , ^[6] coincidencia de características , ^{[ 7]} el cálculo de diagramas de potencia , ^[8] y la representación de sombras suaves . ^[9] El gran desarrollador de juegos de estrategia Paradox Interactive utiliza el JFA para representar las fronteras entre países y provincias. ^[10]

Nuevos desarrollos

La JFA ha inspirado el desarrollo de numerosos algoritmos similares. Algunos tienen propiedades de error bien definidas que los hacen útiles para la informática científica. ^[11]

En el ámbito de la visión por computadora , la JFA ha inspirado nuevos algoritmos de propagación de creencias para acelerar la solución de una variedad de problemas. ^{[12] [13]}

Referencias

1. Rong, Guodong; Bronceado, Tiow-Seng (14 de marzo de 2006). "Salte la inundación en GPU con aplicaciones al diagrama de Voronoi y transformación de distancia" (PDF) . Actas del simposio de 2006 sobre gráficos y juegos 3D interactivos: SI3D '06 . Redwood City, California: Asociación de Maquinaria de Computación. págs. 109-116. doi :10.1145/1111411.1111431. ISBN 978-1-59593-295-2. S2CID  7282879.
2. El artículo original utiliza el caso óptimo, una cuadrícula cuadrada, como ejemplo, pero una cuadrícula de cualquier tamaño funciona. Aunque con una eficiencia reducida. Consulte esta pregunta de StackOverflow para obtener más información.
3. Rong, Guodong; Tan, Tiow-Seng (julio de 2007). "Variantes del algoritmo de inundación por salto para calcular diagramas de Voronoi discretos". Cuarto Simposio Internacional sobre Diagramas de Voronoi en Ciencia e Ingeniería (ISVD 2007) . págs. 176–181. doi :10.1109/ISVD.2007.41. ISBN 978-0-7695-2869-4. S2CID  386735.
4. Guodong Rong; Yang Liu; Wenping Wang; Xiaotiano Yin; Gu, XD; Xiaohu Guo (25 de marzo de 2011). "Computación asistida por GPU de teselación centroidal de Voronoi". Transacciones IEEE sobre visualización y gráficos por computadora . 17 (3): 345–356. doi :10.1109/TVCG.2010.53. hdl : 10722/132211 . ISSN  1077-2626. PMID  21233516. S2CID  11970070.
5. Golus, Ben (1 de abril de 2021). "La búsqueda de contornos muy amplios". Medio . Consultado el 19 de agosto de 2021 .
6. Farías, Renato (2014). "RENDIMIENTO DE NUBE DE PUNTOS USANDO JUMP FLOODING" (PDF) .
7. Yu, Pei; Yang, Xiaokang; Chen, Li (2012). "Partido de parches compatible con paralelos basado en Jump Flooding". En Zhang, Wenjun; Yang, Xiaokang; Xu, Zhixiang; An, ping; Liu, Qizhen; Lu, Yue (eds.). Avances en Televisión Digital y Comunicaciones Multimedia Inalámbricas . Comunicaciones en Informática y Ciencias de la Información. vol. 331. Berlín, Heidelberg: Springer. págs. 15-21. doi :10.1007/978-3-642-34595-1_3. ISBN 978-3-642-34595-1.
8. Zheng, Liping (1 de mayo de 2019). "Cálculo eficiente del diagrama de potencia basado en GPU". Computadoras y gráficos . 80 : 29–36. doi :10.1016/j.cag.2019.03.011. ISSN  0097-8493. S2CID  131923624.
9. Rong, Guodong; Bronceado, Tiow-Seng (1 de noviembre de 2006). "Utilización de inundaciones por saltos en sombras suaves basadas en imágenes". Actas del simposio de ACM sobre software y tecnología de realidad virtual . VRST '06. Limassol, Chipre: Asociación de Maquinaria Informática. págs. 173–180. doi :10.1145/1180495.1180531. ISBN 978-1-59593-321-8. S2CID  15339123.
10. Boczula, Bartosz; Eriksson, Daniel (2020). "Representación optimizada del borde degradado en Imperator: Roma". Intel . Consultado el 28 de marzo de 2021 .
11. Schneider, Jens; Kraus, Martín; Westermann, Rüdiger (2010). "Transformaciones de distancia euclidiana basadas en GPU y su aplicación a la representación de volúmenes". En Ranchordas, Alpesh Kumar; Pereira, João Madeiras; Araújo, Hélder J.; Tavares, João Manuel RS (eds.). Visión por Computador, Imágenes y Gráficos por Computadora. Teoría y Aplicaciones . Comunicaciones en Informática y Ciencias de la Información. vol. 68. Berlín, Heidelberg: Springer. págs. 215-228. doi :10.1007/978-3-642-11840-1_16. ISBN 978-3-642-11840-1.
12. Alchatzidis, Stavros; Sotiras, Aristeidis; Paragios, Nikos (6 de noviembre de 2011). "Cálculo eficiente de mensajes paralelos para la inferencia MAP". Conferencia Internacional sobre Visión por Computadora de 2011 (PDF) . págs. 1379-1386. doi :10.1109/ICCV.2011.6126392. ISBN 978-1-4577-1102-2. S2CID  17554205.
13. Choi, Jungwook; Rutenbar, Rob A. (29 de agosto de 2016). "Acelerador de propagación de creencias configurable y escalable para visión por computadora". 2016 26a Conferencia Internacional sobre Aplicaciones y Lógica Programable en Campo (FPL) . págs. 1–4. doi :10.1109/FPL.2016.7577316. ISBN 978-2-8399-1844-2. S2CID  10923625.

A partir de esta edición, este artículo utiliza contenido de "¿Es separable el algoritmo Jump Flood?" , escrito por alan-wolfe, trichoplax en Stack Exchange, que tiene una licencia que permite la reutilización bajo la licencia Creative Commons Attribution-ShareAlike 3.0 Unported , pero no bajo la GFDL . Se deben seguir todos los términos relevantes.