Exact algorithms for the satellite image selection problem

• Autorzy: Swat Sylwester , Antczak Maciej , Zok Tomasz , Blazewicz Jacek , Musial Jędrzej

Identyfikatory

DOI

10.61822/amcs-2025-0021

• Języki publikacji: EN

Abstrakty

EN

Space development is more relevant than ever with the increasing number of satellite launches for various applications. The amount of space data collected daily is growing exponentially and many customers are interested in continuously monitoring different regions of the Earth. It often requires stitching together many images from other providers to cover an Area of Interest (AOI), resulting in a mosaic. Each satellite image has various parameters, such as cost, download time, cloud coverage, and resolution. The main question is how to optimally select the subset of available images to fully cover the AOI while minimizing total cost and cloud coverage. The problem is known as satellite image mosaic selection (SIMS).Manual selection of promising images is often impossible, especially when dealing with large AOIs or many photos. To solve the problem, we propose several new exact algorithms using different techniques, such as branch-and-bound or mixed-integer linear programming. These algorithms show quality and efficiency compared with existing approaches and are expected to benefit various industrial applications.

Słowa kluczowe

EN

satellite image mosaic selection; set cover; hitting set; plane division

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2025
• Tom: Vol. 35, no. 2
• Strony: 293--309
• Opis fizyczny: Bibliogr. 30 poz., rys., tab., wykr.

Twórcy

autor

Swat Sylwester

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

autor

Antczak Maciej

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, ul. Noskowskiego 12/14, 61-704 Poznan, Poland

autor

Zok Tomasz

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

autor

Blazewicz Jacek

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, ul. Noskowskiego 12/14, 61-704 Poznan, Poland

autor

Musial Jędrzej

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

Bibliografia

• [1] Airbus (2023a). Pléiades, https://www.intelligenceairbusds.com/en/8692-pleiades.
• [2] Airbus (2023b). Pléiades neo, https://www.airbus.com/en/products-services/space/earth-observation/earth-observation-portfolio/pleiades-neo.
• [3] Airbus (2023c). SPOT, https://www.intelligence-a irbusds.com/en/8693-spot-67.
• [4] Asner, G.P., Powell, G.V.N., Mascaro, J., Knapp, D.E., Clark, J.K., Jacobson, J., Kennedy-Bownoten, T., Balaji, A., Paez-Acosta, G., Victoria, E., Secada, L., Valqui, M. and Hughes, R.F. (2010). High-resolution forest carbon stocks and emissions in the Amazon, Proceedings of the National Academy of Sciences 107(38): 16738-16742, DOI: 10.1073/pnas.1004875107.
• [5] Bennett, M.M. and Smith, L.C. (2017). Advances in using multitemporal night-time lights satellite imagery to detect, estimate, and monitor socioeconomic dynamics, Remote Sensing of Environment 192: 176-197, DOI: 10.1016/j.rse.2017.01.005.
• [6] Błazewicz, J., Kovalyov, M., Musiał, J., Urbański, A. and Wojciechowski, A. (2010). Internet shopping optimization problem, International Journal of Applied Mathematics and Computer Science 20(2): 385-390, DOI: 10.2478/v10006-010-0028-0.
• [7] Burke, M., Driscoll, A., Lobell, D.B. and Ermon, S. (2021). Using satellite imagery to understand and promote sustainable development, Science 371(6535): eabe8628, DOI: 10.1126/science.abe8628.
• [8] Chen, K., Luo, W., Lin, X., Song, Z. and Chang, Y. (2024). Evolutionary Biparty Multiobjective UAV Path Planning: Problems and Empirical Comparisons, IEEE Transactions on Emerging Topics in Computational Intelligence 8(3): 2433-2445, DOI: 10.1109/TETCI.2024.3361755.
• [9] Combarro Simón, M., Talbot, P., Danoy, G., Musial, J., Alswaitti, M. and Bouvry, P. (2023). Constraint Model for the Satellite Image Mosaic Selection Problem, LIPIcs, Volume 280, CP 2023 280: 44:1-44:15, DOI: 10.4230/LIPICS.CP.2023.44.
• [10] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M. and Saurabh, S. (2015). Parameterized Algorithms, Springer, Cham, DOI: 10.1007/978-3-319-21275-3.
• [11] Felegari, S., Sharifi, A., Moravej, K., Amin, M., Golchin, A., Muzirafuti, A., Tariq, A. and Zhao, N. (2021). Integration of Sentinel 1 and Sentinel 2 Satellite Images for Crop Mapping, Applied Sciences 11(21): 10104, DOI: 10.3390/app112110104.
• [12] Flood, N., Watson, F. and Collett, L. (2019). Using a U-net convolutional neural network to map woody vegetation extent from high resolution satellite imagery across Queensland, Australia, International Journal of Applied Earth Observation and Geoinformation 82: 101897, DOI: 10.1016/j.jag.2019.101897.
• [13] Goetz, S. (2007). Crisis in Earth Observation, Science 315(5820): 1767-1767, DOI: 10.1126/science.1142466.
• [14] Hall, K., Reitalu, T., Sykes, M.T. and Prentice, H.C. (2012). Spectral heterogeneity of QuickBird satellite data is related to fine-scale plant species spatial turnover in semi-natural grasslands, Applied Vegetation Science 15(1): 145-157, DOI: 10.1111/j.1654-109X.2011.01143.x.
• [15] Hansen, M.C., Stehman, S.V., Potapov, P.V., Loveland, T.R., Townshend, J. R.G., DeFries, R.S., Pittman, K.W., Arunarwati, B., Stolle, F., Steininger, M.K., Carroll, M. and DiMiceli, C. (2008). Humid tropical forest clearing from 2000 to 2005 quantified by using multitemporal and multiresolution remotely sensed data, Proceedings of the National Academy of Sciences 105(27): 9439-9444, DOI: 10.1073/pnas.0804042105.
• [16] Henderson, J.V., Storeygard, A. and Weil, D.N. (2012). Measuring Economic Growth from Outer Space, American Economic Review 102(2): 994-1028, DOI: 10.1257/aer.102.2.994.
• [17] Huangfu, Q. and Hall, J.A.J. (2018). Parallelizing the dual revised simplex method, Mathematical Programming Computation 10(1): 119-142, DOI: 10.1007/s12532-017-0130-5.
• [18] James, M. R. and Robson, S. (2014). Mitigating systematic error in topographic models derived from UAV and ground-based image networks, Earth Surface Processes and Landforms 39(10): 1413-1420, DOI: 10.1002/esp.3609.
• [19] Jean, N., Burke, M., Xie, M., Davis, W.M., Lobell, D.B. and Ermon, S. (2016). Combining satellite imagery and machine learning to predict poverty, Science 353(6301): 790-794, DOI: 10.1126/science.aaf7894.
• [20] Lopez-Loces, M.C., Musial, J., Pecero, J.E., Fraire-Huacuja, H.J., Blazewicz, J. and Bouvry, P. (2016). Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs, International Journal of Applied Mathematics and Computer Science 26(2): 391-406, DOI: 10.1515/amcs-2016-0028.
• [21] Müllerová, J., Brůna, J., Bartaloš, T., Dvořák, P., Vítková, M. and Pyšek, P. (2017). Timing Is Important: Unmanned Aircraft vs. Satellite Imagery in Plant Invasion Monitoring, Frontiers in Plant Science 8: 887, DOI: 10.3389/fpls.2017.00887.
• [22] Rovetto, R.J. (2017). An ontology for satellite databases, Earth Science Informatics 10(4): 417-427, DOI: 10.1007/s12145-017-0290-x.
• [23] Sánchez-Azofeifa, A., Rivard, B., Wright, J., Feng, J.-L., Li, P., Chong, M.M. and Bohlman, S.A. (2011). Estimation of the Distribution of Tabebuia guayacan (Bignoniaceae) Using High-Resolution Remote Sensing Imagery, Sensors 11(4): 3831-3851, DOI: 10.3390/s110403831.
• [24] Shean, D.E., Alexandrov, O., Moratto, Z.M., Smith, B.E., Joughin, I.R., Porter, C. and Morin, P. (2016). An automated, open-source pipeline for mass production of digital elevation models (DEMs) from very-high-resolution commercial stereo satellite imagery, ISPRS Journal of Photogrammetry and Remote Sensing 116: 101-117, DOI: 10.1016/j.isprsjprs.2016.03.012.
• [25] Tian, H., Pei, J., Huang, J., Li, X., Wang, J., Zhou, B., Qin, Y. and Wang, L. (2020). Garlic and Winter Wheat Identification Based on Active and Passive Satellite Imagery and the Google Earth Engine in Northern China, Remote Sensing 12(21): 3539, DOI: 10.3390/rs12213539.
• [26] Verpoorter, C., Kutser, T., Seekell, D.A. and Tranvik, L.J. (2014). A global inventory of lakes based on high-resolution satellite imagery, Geophysical Research Letters 41(18): 6396-6402, DOI: 10.1002/2014GL060641.
• [27] Virtanen, P. et al. (2020). SciPy 1.0: Fundamental algorithms for scientific computing in Python, Nature Methods 17(3): 261-272, DOI: 10.1038/s41592-019-0686-2.
• [28] Wang, Y., Zhang, D. and Dai, G. (2020). Classification of high resolution satellite images using improved U-Net, International Journal of Applied Mathematics and Computer Science 30(3): 399-413, DOI: 10.34768/amcs-2020-0030.
• [29] Yeh, C., Perez, A., Driscoll, A., Azzari, G., Tang, Z., Lobell, D., Ermon, S. and Burke, M. (2020). Using publicly available satellite imagery and deep learning to understand economic well-being in Africa, Nature Communications 11(1): 2583, DOI: 10.1038/s41467-020-16185-w.
• [30] Zok, T., Badura, J., Swat, S., Figurski, K., Popenda, M. and Antczak, M. (2020). New models and algorithms for RNA pseudoknot order assignment, International Journal of Applied Mathematics and Computer Science 30(2): 315-324, DOI: 10.34768/amcs-2020-0024.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).