{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:17Z","timestamp":1750309457272,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T00:00:00Z","timestamp":1744329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>The accurate and prompt mapping of flood-affected regions is important for effective disaster management, including damage assessment and relief efforts. While high-resolution optical imagery from satellites during disasters presents an opportunity for automated flood inundation mapping, existing segmentation models face challenges due to noises such as cloud cover and tree canopies. Thanks to the digital elevation model (DEM) data readily available from sources such as United States Geological Survey (USGS), terrain guidance was utilized by recent graphical models such as hidden Markov trees (HMTs) to improve segmentation quality. Unfortunately, these methods either can only handle a small area where water levels at different locations are assumed to be consistent or require restricted assumptions such as there is only one river channel.<\/jats:p>\n          <jats:p>This article presents an algorithm for flood extent mapping on large-scale Earth imagery, applicable to a large geographic area with multiple river channels. Since water level can vary a lot from upstream to downstream, we propose to detect river pixels to partition the remaining pixels into localized zones, each with a unique water level. In each zone, water at all locations flows to the same river entry point. Pixels in each zone are organized by an HMT to capture water flow directions guided by elevations. Moreover, a novel regularization scheme is designed to enforce inter-zone consistency by penalizing pixel-pairs of adjacent zones that violate terrain guidance. Efficient parallelization is made possible by coloring the zone adjacency graph to identify zones and zone-pairs that have no dependency and hence can be processed in parallel, and incremental one-pass terrain-guided scanning is conducted wherever applicable to reuse computations. Experiments demonstrate that our solution is more accurate than existing solutions and can efficiently and accurately map out flooding pixels in a giant area of size 24,805 \u00d7 40,129. Despite the imbalanced workloads caused by a few large zonal HMTs dominating the serial computing time, our parallelization approach is effective and manages to achieve up to 14.3\u00d7 speedup on a machine with Intel Xeon Gold 6126 CPU @ 2.60 GHz (24 cores, 48 threads) using 32 threads.<\/jats:p>","DOI":"10.1145\/3703157","type":"journal-article","created":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T10:53:39Z","timestamp":1730804019000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Scaling Terrain-Aware Spatial Machine Learning for Flood Mapping on Large Scale Earth Imagery Data"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7846-2200","authenticated-orcid":false,"given":"Saugat","family":"Adhikari","sequence":"first","affiliation":[{"name":"Computer Science, Indiana University Bloomington, Bloomington, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4653-0408","authenticated-orcid":false,"given":"Da","family":"Yan","sequence":"additional","affiliation":[{"name":"Computer Science, Indiana University Bloomington, Bloomington, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3576-6976","authenticated-orcid":false,"given":"Zhe","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4152-182X","authenticated-orcid":false,"given":"Jiao","family":"Han","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington, Bloomington, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4419-3155","authenticated-orcid":false,"given":"Zelin","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4448-9089","authenticated-orcid":false,"given":"Yupu","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5668-194X","authenticated-orcid":false,"given":"Arpan","family":"Sainju","sequence":"additional","affiliation":[{"name":"Middle Tennessee State University, Murfreesboro, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7839-4933","authenticated-orcid":false,"given":"Yang","family":"Zhou","sequence":"additional","affiliation":[{"name":"Auburn University, Auburn, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,11]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"LIDAR-Based Elevation Data from NC State University Libraries. Retrieved from https:\/\/www.lib.ncsu.edu\/gis\/elevation"},{"key":"e_1_3_2_3_2","unstructured":"National Geodetic Survey (NGS) from National Oceanic and Atmospheric Administration (NOAA). Retrieved from https:\/\/www.ngs.noaa.gov"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3557915.3560962"},{"key":"e_1_3_2_5_2","volume-title":"Spatial Econometrics: Methods and Models","author":"Anselin Luc","year":"2013","unstructured":"Luc Anselin. 2013. Spatial Econometrics: Methods and Models. Vol. 4. Springer Science & Business Media."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2016.2644615"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.3390\/rs13112220"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSTARS.2021.3051873"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW50498.2020.00113"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0034-4257(96)00067-3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2005.852196"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2699184"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46475-6_39"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V34I07.6695"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.rse.2018.06.019"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/IGARSS46834.2022.9884588"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.3390\/w12061543"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.3390\/w7041437"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.3390\/s19071486"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.rse.2019.111582"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0034-4257(03)00006-3"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/IGARSS46834.2022.9884604"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/3292500.3330878","volume-title":"Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD\u201919)","author":"Jiang Zhe","year":"2019","unstructured":"Zhe Jiang and Arpan Man Sainju. 2019. Hidden Markov contour tree: A spatial structured model for hydrological applications. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD\u201919). ACM, 804\u2013813."},{"key":"e_1_3_2_24_2","first-page":"316","volume-title":"Proceedings of the SIAM International Conference on Data Mining (SDM\u201923)","author":"Jiang Zhe","year":"2023","unstructured":"Zhe Jiang, Yupu Zhang, Saugat Adhikari, Da Yan, Arpan Man Sainju, Xiaowei Jia, and Yiqun Xie. 2023. A hidden Markov forest model for terrain-aware flood inundation mapping from earth imagery. In Proceedings of the SIAM International Conference on Data Mining (SDM\u201923). SIAM, 316\u2013324."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1680\/jwama.20.00002"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.3390\/rs13122334"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V36I1.19999"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.3390\/rs14195009"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V34I07.6809"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.isprsjprs.2019.04.014"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.isprsjprs.2019.10.017"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/WACV48630.2021.00043"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7298965"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2019.00336"},{"key":"e_1_3_2_35_2","first-page":"259","volume-title":"Proceedings of the British Machine Vision Conference (BMVC\u201918)","author":"Lutz Sebastian","year":"2018","unstructured":"Sebastian Lutz, Konstantinos Amplianitis, and Aljosa Smolic. 2018. AlphaGAN: Generative adversarial networks for natural image matting. In Proceedings of the British Machine Vision Conference (BMVC\u201918). BMVA Press, 259. Retrieved from http:\/\/bmvc2018.org\/contents\/papers\/0915.pdf"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scitotenv.2021.146927"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1979.4310076"},{"issue":"4","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1080\/01431160512331316838","article-title":"The utility of texture analysis to improve per-pixel classification for high to very high spatial resolution imagery","volume":"26","author":"Puissant Anne","year":"2005","unstructured":"Anne Puissant, Jacky Hirsch, and Christiane Weber. 2005. The utility of texture analysis to improve per-pixel classification for high to very high spatial resolution imagery. Int. J. Rem. Sens. 26, 4 (2005), 733\u2013745.","journal-title":"Int. J. Rem. Sens."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.01369"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP42928.2021.9506642"},{"key":"e_1_3_2_41_2","first-page":"234","volume-title":"Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI\u201915)","volume":"9351","author":"Ronneberger Olaf","year":"2015","unstructured":"Olaf Ronneberger, Philipp Fischer, and Thomas Brox. 2015. U-Net: Convolutional networks for biomedical image segmentation. In Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI\u201915), Vol. 9351. Springer, 234\u2013241."},{"issue":"4","key":"e_1_3_2_42_2","first-page":"1530","article-title":"A hidden Markov contour tree model for spatial structured prediction","volume":"34","author":"Sainju Arpan Man","year":"2022","unstructured":"Arpan Man Sainju, Wenchong He, and Zhe Jiang. 2022. A hidden Markov contour tree model for spatial structured prediction. IEEE Trans. Knowl. Data Eng. 34, 4 (2022), 1530\u20131543.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.3390\/rs11192331"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2009.2016214"},{"key":"e_1_3_2_45_2","first-page":"278","volume-title":"Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS\u201903) (Lecture Notes in Computer Science)","volume":"2731","author":"Tomita Etsuji","year":"2003","unstructured":"Etsuji Tomita and Tomokazu Seki. 2003. An efficient branch-and-bound algorithm for finding a maximum clique. In Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS\u201903) (Lecture Notes in Computer Science), Cristian Calude, Michael J. Dinneen, and Vincent Vajnovszki (Eds.), Vol. 2731. Springer, 278\u2013289."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.3390\/rs11131581"},{"key":"e_1_3_2_47_2","first-page":"2545","volume-title":"Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD\u201918)","author":"Xie Miao","year":"2018","unstructured":"Miao Xie, Zhe Jiang, and Arpan Man Sainju. 2018. Geographical hidden Markov tree for flood extent mapping. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD\u201918). ACM, 2545\u20132554."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.41"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/IGARSS47720.2021.9554825"},{"key":"e_1_3_2_50_2","first-page":"3:1\u20133:2","volume-title":"Proceedings of the XSEDE Conference","author":"Yildirim Ahmet Artu","year":"2016","unstructured":"Ahmet Artu Yildirim, David Tarboton, Yan Liu, Nazmus Shams Sazib, and Shaowen Wang. 2016. Accelerating TauDEM for extracting hydrology information from national-scale high resolution topographic dataset: Extended abstract. In Proceedings of the XSEDE Conference. ACM, 3:1\u20133:2."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V35I4.16432"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.3390\/sym11030431"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/MGRS.2016.2540798"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703157","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3703157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:18Z","timestamp":1750295418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,11]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3703157"],"URL":"https:\/\/doi.org\/10.1145\/3703157","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2025,4,11]]},"assertion":[{"value":"2024-02-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}