constraint modeling; polygon covering; satellite imaging; set covering; constraint programming
Abstract :
[en] Satellite imagery solutions are widely used to study and monitor different regions of the Earth. However, a single satellite image can cover only a limited area. In cases where a larger area of interest is studied, several images must be stitched together to create a single larger image, called a mosaic, that can cover the area. Today, with the increasing number of satellite images available for commercial use, selecting the images to build the mosaic is challenging, especially when the user wants to optimize one or more parameters, such as the total cost and the cloud coverage percentage in the mosaic. More precisely, for this problem the input is an area of interest, several satellite images intersecting the area, a list of requirements relative to the image and the mosaic, such as cloud coverage percentage, image resolution, and a list of objectives to optimize. We contribute to the constraint and mixed integer lineal programming formulation of this new problem, which we call the satellite image mosaic selection problem, which is a multi-objective extension of the polygon cover problem. We propose a dataset of realistic and challenging instances, where the images were captured by the satellite constellations SPOT, Pléiades and Pléiades Neo. We evaluate and compare the two proposed models and show their efficiency for large instances, up to 200 images.
Research center :
ULHPC - University of Luxembourg: High Performance Computing
Disciplines :
Computer science
Author, co-author :
COMBARRO SIMON, Manuel ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PCOG
TALBOT, Pierre ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS) ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg
DANOY, Grégoire ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Musial, Jedrzej; Poznan University of Technology, Poland
ALSWAITTI, Mohammed ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PCOG ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg
BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS) ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg
External co-authors :
yes
Language :
English
Title :
Constraint Model for the Satellite Image Mosaic Selection Problem
Publication date :
September 2023
Event name :
The 29th International Conference on Principles and Practice of Constraint Programming
Event place :
Toronto, Can
Event date :
27-08-2023 => 31-08-2023
Audience :
International
Main work title :
29th International Conference on Principles and Practice of Constraint Programming, CP 2023
Editor :
Yap, Roland H. C. Yap
Publisher :
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN/EAN :
978-3-9597730-0-3
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
Development Goals :
9. Industry, innovation and infrastructure
FnR Project :
FNR16101289 - A Concurrent Model Of Computation For Trustworthy Gpu Programming, 2021 (01/01/2022-31/12/2024) - Pascal Bouvry FNR17395419 - Space Data Brokering Optimization System, 2022 (01/01/2023-31/12/2025) - Pascal Bouvry FNR17043604 - A Satellite Data Marketplace Model With Data Lake Storage, 2022 (01/03/2022-31/10/2025) - Manuel Combarro Simon
Funders :
FNR - Fonds National de la Recherche
Funding number :
17043604; C21/IS/16101289; C22/IS/17395419
Funding text :
Pierre Talbot: This work is supported by the FNR – COMOC Project, ref. C21/IS/16101289. Jedrzej Musial: This work is funded by the FNR – PolLux program under the SERENITY Project, ref. C22/IS/17395419. Funding Manuel Combarro Simón: This work is partially funded by the Luxembourg National Research Fund (FNR) – ASTRAL Project, ref. 17043604, and by the joint research programme UL/SnT-ILNAS on Technical Standardization for Trustworthy ICT, Aerospace, and Construction.
Pradeesha Ashok, Aniket Basu Roy, and Sathish Govindarajan. Local search strikes again: PTAS for variants of geometric covering and packing. Journal of Combinatorial Optimization, 39(2):618-635, June 2019. doi:10.1007/s10878-019-00432-y.
Nikhil Bansal and Kirk Pruhs. Weighted geometric set multi-cover via quasi-uniform sampling. In Algorithms - ESA 2012, pages 145-156. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33090-2_14.
Timothy M. Chan and Qizheng He. Faster approximation algorithms for geometric set cover. In Leibniz International Proceedings in Informatics, LIPIcs, volume 164. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, June 2020. doi: 10.4230/LIPIcs.SoCG.2020.27.
Chandra Chekuri, Sariel Har-Peled, and Kent Quanrud. Fast LP-based approximations for geometric packing and covering problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1019-1038. Society for Industrial and Applied Mathematics, January 2020. doi:10.1137/1.9781611975994.62.
V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, August 1979. doi:10.1287/moor.4.3.233.
Claudio Contardo and Alain Hertz. An exact algorithm for a class of geometric set-cover problems. Discrete Applied Mathematics, 300:25-35, 2021. doi:10.1016/j.dam.2021.05.005.
Joseph C. Culberson and Robert A. Reckhow. Covering polygons is hard. Annual Symposium on Foundations of Computer Science (Proceedings), pages 601-611, 1988. doi:10.1109/SFCS. 1988.21976.
Minati De and Abhiruk Lahiri. Geometric Dominating-Set and Set-Cover via Local-Search. Computational Geometry, 113:102007, August 2023. doi:10.1016/j.comgeo.2023.102007.
European Union Agency for the Space Programme. EUSPA EO and GNSS Market Report. Technical Report 1, European Union Agency for the Space Programme, 2022. URL: https://www.euspa.europa.eu/sites/default/files/uploads/euspa_market_report_2022.pdf.
Shilan Felegari, Alireza Sharifi, Kamran Moravej, Muhammad Amin, Ahmad Golchin, Anselme Muzirafuti, Aqil Tariq, and Na Zhao. Integration of Sentinel 1 and Sentinel 2 Satellite Images for Crop Mapping. Applied Sciences, 11:10104, 2021. doi:10.3390/app112110104.
Neil Flood, Fiona Watson, and Lisa Collett. 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, October 2019. doi:10.1016/J.JAG.2019.101897.
Marco Gavanelli. An algorithm for multi-criteria optimization in CSPs. In ECAI 2002: 15th European Conference on Artificial Intelligence, July 21-26, 2002, Lyon France: Including Prestigious Applications of Intelligent Systems (PAIS 2002): Proceedings, volume 77, page 136. IOS Press, 2002.
Tias Guns, Peter J. Stuckey, and Guido Tack. Solution Dominance over Constraint Satisfaction Problems, 2018. arXiv:1812.09207 [cs]. URL: http://arxiv.org/abs/1812.09207.
Yanan Guo, Xiaoqun Cao, Bainian Liu, and Mei Gao. Cloud detection for satellite imagery using attention-based u-net convolutional neural network. Symmetry, 12(6):1056, June 2020. doi:10.3390/sym12061056.
Ola Hall, Sigrun Dahlin, Håkan Marstorp, Maria Francisca Archila Bustos, Ingrid Öborn, and Magnus Jirström. Classification of maize in complex smallholder farming systems using UAV imagery. Drones, 2(3):1-8, 2018. doi:10.3390/drones2030022.
Jacob Høxbroe Jeppesen, Rune Hylsberg Jacobsen, Fadil Inceoglu, and Thomas Skjødeberg Toftegaard. A cloud detection algorithm for satellite imagery based on deep learning. Remote Sensing of Environment, 229:247-259, August 2019. doi:10.1016/j.rse.2019.03.039.
Martin Lukasiewycz, Michael Glaß, Christian Haubelt, and Jürgen Teich. Solving Multiobjective Pseudo-Boolean Problems. In Theory and Applications of Satisfiability Testing - SAT 2007, pages 56-69. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-72788-0_9.
Sina Sharif Mansouri, George Georgoulas, Thomas Gustafsson, and George Nikolakopoulos. On the covering of a polygonal region with fixed size rectangles with an application towards aerial inspection. In 2017 25th Mediterranean Conference on Control and Automation (MED). IEEE, July 2017. doi:10.1109/med.2017.7984284.
George Mavrotas. Effective implementation of the ϵ-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2):455-465, July 2009. doi:10.1016/j.amc.2009.03.037.
George Mavrotas and Kostas Florios. An improved version of the augmented ϵ-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems. Applied Mathematics and Computation, 219(18):9652-9669, May 2013. doi: 10.1016/j.amc.2013.03.002.
V. Megha and K. K. Rajkumar. Automatic Satellite Image Stitching Based on Speeded Up Robust Feature. In Proceedings - 2021 1st IEEE International Conference on Artificial Intelligence and Machine Vision, AIMV 2021, pages 1-6, Gandhinagar, India, 2021. Institute of Electrical and Electronics Engineers Inc. doi:10.1109/AIMV53313.2021.9670954.
Doug Mohney. Terabytes From Space: Satellite Imaging is Filling Data Centers, 2020. URL: https://datacenterfrontier.com/terabytes-from-space-satellite-imaging-is-filling-data-centers/.
Sébastien Mouthuy, Yves Deville, and Grégoire Dooms. Global constraint for the set covering problem. Journées Francophones de Programmation par Contraintes, pages 183-192, 2007.
Konstantinos G. Nikolakopoulos, Paraskevi Lampropoulou, Elias Fakiris, Dimitris Sardelianos, and George Papatheodorou. Synergistic use of UAV and USV data and petrographic analyses for the investigation of beachrock formations: A case study from Syros Island, Aegean sea, Greece. Minerals, 8(11):534, November 2018. doi:10.3390/min8110534.
Laurent Perron and Vincent Furnon. Or-tools. URL: https://developers.google.com/optimization/.
Simone Piaggesi, Laetitia Gauvin, Michele Tizzoni, Natalia Adler, Stefaan Verhulst, Andrew Young, Rihannan Price, Leo Ferres, Ciro Cattuto, and André Panisson. Predicting city poverty using satellite imagery. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, volume 2019-June, pages 90-96, 2019.
Pierre Schaus and Renaud Hartert. Multi-Objective Large Neighborhood Search. In Principles and Practice of Constraint Programming, volume 8124, pages 611-627. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. doi:10.1007/978-3-642-40627-0_46.
Christian Schulte, Guido Tack, and Mikael Lagerkvist. Modeling and Programming with Gecode, 2020.
Y. G. Stoyan, T. Romanova, G. Scheithauer, and A. Krivulya. Covering a polygonal region by rectangles. Computational Optimization and Applications 2009 48:3, 48(3):675-695, May 2009. doi:10.1007/S10589-009-9258-1.
Lin Sun, Xu Yang, Shangfeng Jia, Chen Jia, Quan Wang, Xinyan Liu, Jing Wei, and Xueying Zhou. Satellite data cloud detection using deep learning supported by hyperspectral data. International Journal of Remote Sensing, 41(4):1349-1371, September 2019. doi: 10.1080/01431161.2019.1667548.
Union of Concerned Scientists. UCS Satellite Database. URL: https://www.ucsusa.org/resources/satellite-database.
Haibo Wang, Xueshuang Gong, Bingbing Wang, Chao Deng, and Qiong Cao. Urban development analysis using built-up area maps based on multiple high-resolution satellite data. International Journal of Applied Earth Observation and Geoinformation, 103:102500, December 2021. doi:10.1016/J.JAG.2021.102500.
Lei Yu, Yongjun Zhang, Mingwei Sun, and Xinyu Zhu. Colour balancing of satellite imagery based on a colour reference library. International Journal of Remote Sensing, 37(24):5763-5785, December 2016. doi:10.1080/01431161.2016.1249306.
Weihua Zhang and Marc Reimann. A simple augmented ϵ-constraint method for multi-objective mathematical integer programming problems. European Journal of Operational Research, 234(1):15-24, April 2014. doi:10.1016/j.ejor.2013.09.001.
