868:
This variant runs normal JFA at a half resolution, and enlarge the result into the original resolution and run one additional pass with step size of 1. Because most of the passes has only half resolution, the speed of this variant is much faster than the full resolution
88:
grid of pixels (like an image or texture). All pixels will start with an "undefined" color unless it is a uniquely-colored "seed" pixel. As the JFA progresses, each undefined pixel will be filled with a color corresponding to that of a seed pixel.
50:
computation, notably for its efficient performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.
1479:
789:: JFA+1 has one additional pass with step size of 1, i.e. the step sizes are N/2, N/4, ..., 1, 1; JFA+2 has two additional passes with step sizes of 2 and 1, i.e. the step sizes are N/2, N/4, ..., 1, 2, 1; JFA
670:
Note that pixels may change color more than once in each step, and that the JFA does not specify a method for resolving cases where distances are equal, therefore the last-checked pixel's color is used above.
154:
535:
1483:
862:: 1+JFA has one additional pass with step size of 1, i.e. the step sizes are 1, N/2, N/4, ..., 1. 1+JFA has very low error rate (similar to JFA+2) and the same performance as JFA+1.
772:
330:
714:
852:
277:
86:
580:
210:
813:
660:
640:
620:
600:
555:
456:
436:
413:
393:
373:
353:
233:
178:
922:
The JFA has inspired the development of numerous similar algorithms. Some have well-defined error properties which make them useful for scientific computing.
674:
The JFA finishes after evaluating the last pixel in the last step size. Regardless of the content of the initial data, the innermost loop runs a total of
1306:
854:
additional passes, i.e. the step sizes are N/2, N/4, ..., 1, N/2, N/4, ..., 1. JFA+1 has much fewer errors than JFA, and JFA+2 has even fewer errors.
1438:
1393:
1351:
1281:
1197:
1044:
981:
1004:
The original paper uses the optimal case, a square grid, as an example, but a grid of any size works. Albeit with reduced efficiency. See
40:
95:
883:
1466:
1005:
1499:
1338:. Communications in Computer and Information Science. Vol. 68. Berlin, Heidelberg: Springer. pp. 215–228.
1184:. Communications in Computer and Information Science. Vol. 331. Berlin, Heidelberg: Springer. pp. 15–21.
461:
1334:. In Ranchordas, AlpeshKumar; Pereira, João Madeiras; Araújo, Hélder J.; Tavares, João Manuel R. S. (eds.).
1214:
1134:
907:
719:
282:
1372:
911:
677:
1475:
818:
1471:
1444:
1399:
1331:
1287:
1242:
1115:
1050:
987:
930:
36:
28:
1177:
238:
65:
1434:
1389:
1347:
1277:
1234:
1193:
1107:
1099:
1040:
977:
1426:
1381:
1339:
1269:
1226:
1185:
1089:
1081:
1032:
969:
895:
183:
926:
792:
32:
1180:. In Zhang, Wenjun; Yang, Xiaokang; Xu, Zhixiang; An, Ping; Liu, Qizhen; Lu, Yue (eds.).
560:
1159:
887:
645:
625:
605:
585:
540:
441:
421:
398:
378:
358:
338:
218:
163:
1068:
Guodong Rong; Yang Liu; Wenping Wang; Xiaotian Yin; Gu, X D; Xiaohu Guo (2011-03-25).
1029:
4th
International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007)
1493:
1423:
2016 26th
International Conference on Field Programmable Logic and Applications (FPL)
1268:. VRST '06. Limassol, Cyprus: Association for Computing Machinery. pp. 173–180.
1246:
899:
1448:
1403:
1291:
1119:
1332:"GPU-Based Euclidean Distance Transforms and Their Application to Volume Rendering"
991:
968:. Redwood City, California: Association for Computing Machinery. pp. 109–116.
958:
903:
1054:
959:"Jump flooding in GPU with applications to Voronoi diagram and distance transform"
1343:
966:
Proceedings of the 2006 symposium on
Interactive 3D graphics and games - SI3D '06
1189:
891:
879:
1418:
1368:
1069:
1024:
1419:"Configurable and scalable belief propagation accelerator for computer vision"
1385:
1230:
1430:
1238:
1103:
1025:"Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams"
1273:
973:
1478:
at Stack
Exchange, which is licensed in a way that permits reuse under the
1266:
Proceedings of the ACM symposium on
Virtual reality software and technology
1111:
1261:
1367:
Alchatzidis, Stavros; Sotiras, Aristeidis; Paragios, Nikos (2011-11-06).
1085:
1036:
878:
The jump flooding algorithm and its variants may be used for calculating
1094:
1336:
Computer Vision, Imaging and
Computer Graphics. Theory and Applications
1182:
Advances on
Digital Television and Wireless Multimedia Communications
716:
times over each pixel, for an overall computational complexity of
16:
Class of algorithms used for computing distance-related functions
933:
algorithms to accelerate the solution of a variety of problems.
914:
uses the JFA to render borders between countries and provinces.
149:{\displaystyle k\in \{{\frac {N}{2}},{\frac {N}{4}},\dots ,1\}}
47:
1070:"GPU-Assisted Computation of Centroidal Voronoi Tessellation"
1480:
Creative
Commons Attribution-ShareAlike 3.0 Unported License
1330:
Schneider, Jens; Kraus, Martin; Westermann, Rüdiger (2010).
1369:"Efficient parallel message computation for MAP inference"
1307:"Optimized Gradient Border Rendering in Imperator: Rome"
1074:
1461:
1178:"Parallel-Friendly Patch Match Based on Jump Flooding"
59:
The JFA original formulation is simple to implement.
1262:"Utilizing jump flooding in image-based soft shadows"
821:
795:
722:
680:
648:
628:
608:
588:
563:
543:
464:
444:
424:
401:
381:
361:
341:
285:
241:
221:
186:
166:
98:
68:
1215:"GPU-based efficient computation of power diagram"
846:
807:
766:
708:
654:
634:
614:
594:
574:
549:
529:
450:
430:
407:
387:
367:
347:
324:
271:
227:
204:
172:
148:
80:
1374:2011 International Conference on Computer Vision
1417:Choi, Jungwook; Rutenbar, Rob A. (2016-08-29).
39:. The JFA was introduced by Rong Guodong at an
8:
1260:Rong, Guodong; Tan, Tiow-Seng (2006-11-01).
957:Rong, Guodong; Tan, Tiow-Seng (2006-03-14).
319:
298:
143:
105:
1305:Boczula, Bartosz; Eriksson, Daniel (2020).
1160:"POINT CLOUD RENDERING USING JUMP FLOODING"
1023:Rong, Guodong; Tan, Tiow-Seng (July 2007).
1176:Yu, Pei; Yang, Xiaokang; Chen, Li (2012).
1018:
1016:
1014:
952:
950:
948:
946:
1093:
826:
820:
799:
794:
743:
733:
721:
688:
679:
647:
627:
607:
587:
562:
542:
463:
443:
423:
400:
380:
360:
340:
284:
240:
220:
185:
165:
121:
108:
97:
67:
942:
530:{\displaystyle dist(p,s)>dist(p,s')}
1486:. All relevant terms must be followed.
7:
1467:"Is Jump Flood Algorithm Separable?"
1006:this StackOverflow question for more
767:{\displaystyle O(N^{2}\log _{2}(N))}
46:The JFA has desirable attributes in
1135:"The Quest for Very Wide Outlines"
14:
1464:, this article uses content from
929:domain, the JFA has inspired new
325:{\displaystyle i,j\in \{-k,0,k\}}
884:centroidal Voronoi tessellations
860:Additional pass at the beginning
156:, run one iteration of the JFA:
841:
835:
761:
758:
752:
726:
703:
697:
524:
507:
489:
477:
266:
242:
199:
187:
1:
709:{\displaystyle 9\log _{2}(N)}
1344:10.1007/978-3-642-11840-1_16
1213:Zheng, Liping (2019-05-01).
847:{\displaystyle \log _{2}(N)}
622:, respectively, then change
31:used in the construction of
1190:10.1007/978-3-642-34595-1_3
1516:
787:Additional pass at the end
782:Some variants of JFA are:
1386:10.1109/ICCV.2011.6126392
1231:10.1016/j.cag.2019.03.011
1133:Golus, Ben (2021-04-01).
272:{\displaystyle (x+i,y+j)}
160:Iterate over every pixel
81:{\displaystyle N\times N}
1431:10.1109/FPL.2016.7577316
1219:Computers & Graphics
582:are the seed pixels for
1274:10.1145/1180495.1180531
1158:Farias, Renato (2014).
974:10.1145/1111411.1111431
21:jump flooding algorithm
1380:. pp. 1379–1386.
848:
809:
768:
710:
656:
636:
616:
596:
576:
551:
531:
452:
432:
409:
389:
369:
349:
326:
273:
229:
206:
174:
150:
82:
898:, the computation of
849:
810:
769:
711:
657:
637:
617:
597:
577:
552:
532:
453:
433:
410:
390:
370:
350:
327:
274:
230:
207:
205:{\displaystyle (x,y)}
175:
151:
83:
1482:, but not under the
1086:10.1109/TVCG.2010.53
1037:10.1109/ISVD.2007.41
1031:. pp. 176–181.
918:Further developments
819:
808:{\displaystyle ^{2}}
793:
720:
678:
646:
626:
606:
586:
561:
541:
462:
442:
422:
399:
379:
359:
339:
283:
239:
219:
184:
164:
96:
66:
1500:Flooding algorithms
912:Paradox Interactive
908:grand strategy game
375:is colored, change
92:For each step size
43:symposium in 2006.
37:distance transforms
931:belief propagation
886:(CVT), generating
844:
805:
764:
706:
652:
632:
612:
592:
575:{\displaystyle s'}
572:
547:
527:
448:
428:
405:
385:
365:
345:
322:
269:
225:
215:For each neighbor
202:
170:
146:
78:
29:flooding algorithm
1440:978-2-8399-1844-2
1395:978-1-4577-1102-2
1353:978-3-642-11840-1
1283:978-1-59593-321-8
1199:978-3-642-34595-1
1046:978-0-7695-2869-4
983:978-1-59593-295-2
655:{\displaystyle q}
635:{\displaystyle p}
615:{\displaystyle q}
595:{\displaystyle p}
550:{\displaystyle s}
451:{\displaystyle q}
431:{\displaystyle p}
408:{\displaystyle q}
388:{\displaystyle p}
368:{\displaystyle q}
355:is undefined and
348:{\displaystyle p}
228:{\displaystyle q}
173:{\displaystyle p}
129:
116:
1507:
1453:
1452:
1425:. pp. 1–4.
1414:
1408:
1407:
1379:
1364:
1358:
1357:
1327:
1321:
1320:
1318:
1317:
1302:
1296:
1295:
1257:
1251:
1250:
1210:
1204:
1203:
1173:
1167:
1166:
1164:
1155:
1149:
1148:
1146:
1145:
1130:
1124:
1123:
1097:
1065:
1059:
1058:
1020:
1009:
1002:
996:
995:
963:
954:
896:feature matching
866:Half resolution:
853:
851:
850:
845:
831:
830:
814:
812:
811:
806:
804:
803:
773:
771:
770:
765:
748:
747:
738:
737:
715:
713:
712:
707:
693:
692:
661:
659:
658:
653:
641:
639:
638:
633:
621:
619:
618:
613:
601:
599:
598:
593:
581:
579:
578:
573:
571:
556:
554:
553:
548:
536:
534:
533:
528:
523:
457:
455:
454:
449:
437:
435:
434:
429:
414:
412:
411:
406:
394:
392:
391:
386:
374:
372:
371:
366:
354:
352:
351:
346:
331:
329:
328:
323:
278:
276:
275:
270:
234:
232:
231:
226:
211:
209:
208:
203:
179:
177:
176:
171:
155:
153:
152:
147:
130:
122:
117:
109:
87:
85:
84:
79:
33:Voronoi diagrams
1515:
1514:
1510:
1509:
1508:
1506:
1505:
1504:
1490:
1489:
1457:
1456:
1441:
1416:
1415:
1411:
1396:
1377:
1366:
1365:
1361:
1354:
1329:
1328:
1324:
1315:
1313:
1304:
1303:
1299:
1284:
1259:
1258:
1254:
1212:
1211:
1207:
1200:
1175:
1174:
1170:
1162:
1157:
1156:
1152:
1143:
1141:
1132:
1131:
1127:
1067:
1066:
1062:
1047:
1022:
1021:
1012:
1003:
999:
984:
961:
956:
955:
944:
939:
927:computer vision
920:
906:rendering. The
888:distance fields
876:
822:
817:
816:
796:
791:
790:
780:
739:
729:
718:
717:
684:
676:
675:
644:
643:
624:
623:
604:
603:
584:
583:
564:
559:
558:
539:
538:
516:
460:
459:
458:is colored, if
440:
439:
438:is colored and
420:
419:
397:
396:
377:
376:
357:
356:
337:
336:
281:
280:
237:
236:
217:
216:
182:
181:
162:
161:
94:
93:
64:
63:
57:
17:
12:
11:
5:
1513:
1511:
1503:
1502:
1492:
1491:
1470:, authored by
1455:
1454:
1439:
1409:
1394:
1359:
1352:
1322:
1297:
1282:
1252:
1205:
1198:
1168:
1150:
1125:
1080:(3): 345–356.
1060:
1045:
1010:
997:
982:
941:
940:
938:
935:
919:
916:
900:power diagrams
875:
872:
871:
870:
863:
856:
855:
843:
840:
837:
834:
829:
825:
802:
798:
779:
776:
763:
760:
757:
754:
751:
746:
742:
736:
732:
728:
725:
705:
702:
699:
696:
691:
687:
683:
668:
667:
666:
665:
664:
663:
651:
631:
611:
591:
570:
567:
546:
526:
522:
519:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
447:
427:
416:
404:
384:
364:
344:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
268:
265:
262:
259:
256:
253:
250:
247:
244:
224:
201:
198:
195:
192:
189:
169:
145:
142:
139:
136:
133:
128:
125:
120:
115:
112:
107:
104:
101:
77:
74:
71:
56:
55:Implementation
53:
15:
13:
10:
9:
6:
4:
3:
2:
1512:
1501:
1498:
1497:
1495:
1488:
1487:
1485:
1481:
1477:
1473:
1468:
1465:
1463:
1450:
1446:
1442:
1436:
1432:
1428:
1424:
1420:
1413:
1410:
1405:
1401:
1397:
1391:
1387:
1383:
1376:
1375:
1370:
1363:
1360:
1355:
1349:
1345:
1341:
1337:
1333:
1326:
1323:
1312:
1308:
1301:
1298:
1293:
1289:
1285:
1279:
1275:
1271:
1267:
1263:
1256:
1253:
1248:
1244:
1240:
1236:
1232:
1228:
1224:
1220:
1216:
1209:
1206:
1201:
1195:
1191:
1187:
1183:
1179:
1172:
1169:
1161:
1154:
1151:
1140:
1136:
1129:
1126:
1121:
1117:
1113:
1109:
1105:
1101:
1096:
1091:
1087:
1083:
1079:
1075:
1071:
1064:
1061:
1056:
1052:
1048:
1042:
1038:
1034:
1030:
1026:
1019:
1017:
1015:
1011:
1007:
1001:
998:
993:
989:
985:
979:
975:
971:
967:
960:
953:
951:
949:
947:
943:
936:
934:
932:
928:
923:
917:
915:
913:
909:
905:
901:
897:
893:
889:
885:
881:
873:
867:
864:
861:
858:
857:
838:
832:
827:
823:
800:
797:
788:
785:
784:
783:
777:
775:
755:
749:
744:
740:
734:
730:
723:
700:
694:
689:
685:
681:
672:
649:
629:
609:
589:
568:
565:
544:
520:
517:
513:
510:
504:
501:
498:
495:
492:
486:
483:
480:
474:
471:
468:
465:
445:
425:
417:
402:
382:
362:
342:
334:
333:
316:
313:
310:
307:
304:
301:
295:
292:
289:
286:
263:
260:
257:
254:
251:
248:
245:
222:
214:
213:
196:
193:
190:
167:
159:
158:
157:
140:
137:
134:
131:
126:
123:
118:
113:
110:
102:
99:
90:
75:
72:
69:
60:
54:
52:
49:
44:
42:
38:
34:
30:
26:
22:
1469:
1459:
1458:
1422:
1412:
1373:
1362:
1335:
1325:
1314:. Retrieved
1310:
1300:
1265:
1255:
1222:
1218:
1208:
1181:
1171:
1153:
1142:. Retrieved
1138:
1128:
1095:10722/132211
1077:
1073:
1063:
1028:
1000:
965:
924:
921:
880:Voronoi maps
877:
865:
859:
786:
781:
673:
669:
642:'s color to
395:'s color to
91:
61:
58:
45:
24:
20:
18:
904:soft shadow
894:rendering,
892:point-cloud
1476:trichoplax
1472:alan-wolfe
1316:2021-03-28
1144:2021-08-19
937:References
910:developer
1462:this edit
1247:131923624
1239:0097-8493
1225:: 29–36.
1104:1077-2626
833:
750:
695:
302:−
296:∈
135:…
103:∈
73:×
1494:Category
1449:10923625
1404:17554205
1292:15339123
1120:11970070
1112:21233516
778:Variants
569:′
521:′
62:Take an
992:7282879
925:In the
27:) is a
1460:As of
1447:
1437:
1402:
1392:
1350:
1290:
1280:
1245:
1237:
1196:
1139:Medium
1118:
1110:
1102:
1055:386735
1053:
1043:
990:
980:
902:, and
537:where
279:where
1445:S2CID
1400:S2CID
1378:(PDF)
1311:Intel
1288:S2CID
1243:S2CID
1163:(PDF)
1116:S2CID
1051:S2CID
988:S2CID
962:(PDF)
1484:GFDL
1435:ISBN
1390:ISBN
1348:ISBN
1278:ISBN
1235:ISSN
1194:ISBN
1108:PMID
1100:ISSN
1041:ISBN
978:ISBN
882:and
874:Uses
869:JFA.
815:has
602:and
557:and
493:>
35:and
19:The
1427:doi
1382:doi
1340:doi
1270:doi
1227:doi
1186:doi
1090:hdl
1082:doi
1033:doi
970:doi
824:log
741:log
686:log
662:'s.
418:if
335:if
235:at
180:at
48:GPU
41:ACM
25:JFA
1496::
1474:,
1443:.
1433:.
1421:.
1398:.
1388:.
1371:.
1346:.
1309:.
1286:.
1276:.
1264:.
1241:.
1233:.
1223:80
1221:.
1217:.
1192:.
1137:.
1114:.
1106:.
1098:.
1088:.
1078:17
1076:.
1072:.
1049:.
1039:.
1027:.
1013:^
986:.
976:.
964:.
945:^
890:,
774:.
415:'s
332::
212:.
1451:.
1429::
1406:.
1384::
1356:.
1342::
1319:.
1294:.
1272::
1249:.
1229::
1202:.
1188::
1165:.
1147:.
1122:.
1092::
1084::
1057:.
1035::
1008:.
994:.
972::
842:)
839:N
836:(
828:2
801:2
762:)
759:)
756:N
753:(
745:2
735:2
731:N
727:(
724:O
704:)
701:N
698:(
690:2
682:9
650:q
630:p
610:q
590:p
566:s
545:s
525:)
518:s
514:,
511:p
508:(
505:t
502:s
499:i
496:d
490:)
487:s
484:,
481:p
478:(
475:t
472:s
469:i
466:d
446:q
426:p
403:q
383:p
363:q
343:p
320:}
317:k
314:,
311:0
308:,
305:k
299:{
293:j
290:,
287:i
267:)
264:j
261:+
258:y
255:,
252:i
249:+
246:x
243:(
223:q
200:)
197:y
194:,
191:x
188:(
168:p
144:}
141:1
138:,
132:,
127:4
124:N
119:,
114:2
111:N
106:{
100:k
76:N
70:N
23:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.