A method for universal superpixels-based regionalization (preliminary results)
Generalization is one of the fundamentals of scientific research. In the context of spatial information, generalization needs to allow for finding common properties but also for spatial contiguity. Therefore, such generalization is often made through regionalization - partitioning of space into spatial clusters or regions. This process is vital for environmental studies, where many patterns and processes are autocorrelated spatially. Examples of regionalizations include delineation of ecoregions, detection of homogeneous zones for precision agriculture, definition of climate regions, and so on.
Traditionally spatial generalization was performed manually, often based on a compilation of pre-existing, independently conducted studies. This approach lack of quantitative framework, and thus no systematic checks, modifications or objective updates are possible. Currently, the abundance of remote sensing spatial data, such as satellite imagery, gridded climate data, or land cover maps, allows fast extraction of relevant spatial information on regional and global scales, making possible studies rooted in a clear quantitative framework.
Such data, however, still requires spatially-aware generalization to formulate general concepts or claims. Remote sensing data stores information as a set of raster cells, where a single cell is unaware of its spatial context. This is often not enough to understand underlying objects or processes.
(Geographic) object-based image analysis (OBIA) (Blaschke 2010) is frequently applied to resolve this issue. It is an approach to partition space consisting of raster cells into homogeneous objects and thus make spatial regionalization possible. Several generalization techniques were developed for OBIA, including a superpixels approach that proved to perform best for image processing and remote sensing data analysis (Csillik 2017).
The main idea of superpixels is to create connected groupings of cells with similar values (Ren and Malik 2003; Achanta et al. 2012). Each superpixel represents a desired level of homogeneity while at the same time maintaining spatial structures. Superpixels also carry more information than each cell alone, and thus they can speed up the subsequent processing efforts (Ren and Malik 2003; Achanta et al. 2012).
The original superpixels algorithm has, however, two major drawbacks for spatial data problems other than RGB images. Firstly, the algorithm uses the Euclidean distance, which is adequate in many cases, such as RGB images. However, it limits the possible usability for environmental datasets – Euclidean distance is not suitable for many types of spatial raster data (e.g., categorical rasters) and has undesirable properties for multi-dimensional data (e.g., a set of monthly climate data), where the results based on Euclidean distance contradict human intuition (Aggarwal, Hinneburg, and Keim 2001). Secondly, the superpixels technique does not result in regions per se but rather over-segmentation – some spatial objects/regions could be represented by one superpixel, while others could consist of many very similar superpixels.
Our preliminary results presented during the GIScience 2021 conference (Nowosad and Stepinski 2021) provide a basis for using other distance measures to create superpixels. The proposed extension can also be used for various scenarios, such as creating regions of similar multi-dimensional spatial and temporal patterns or similarly ranked areas. The extension is also already available as an open-source software in the form of an R package. The supercells package has extensive documentation in the form of a help file and additional vignettes that can be found, together with its installation instructions, at https://jakubnowosad.com/supercells/.
The second issue is, however, still not resolved. Many clustering methods exist that could be used for merging similar connected superpixels, including traditional ones such as hierarchical clustering and spatial-aware ones such as SKATER or REDCAP. Wang et al. (2018) developed a REDCAP-based workflow for merging superpixels, which showed good image results and outperformed similar techniques; however, their work was based on the original superpixels algorithm and thus used Euclidean distance on 3-dimensional RGB images only. Additionally, it could be worth testing how good modern unsupervised machine learning techniques would perform in this task.
Our main goal is to present the work in progress related to developing a robust method for merging superpixels and thus creating high-quality regionalization. We will test clustering/grouping methods based on three main criteria: accuracy, universality, and computational performance. Accuracy will be obtained based on the resulting regions’ internal homogeneity and their isolation compared to the neighbors. Universality will be tested on several datasets to check if the method works for various scenarios, including RGB images, categorical rasters, spatial time-series, etc. The computational performance will be evaluated based on the time needed for each method’s calculation and their use of computer resources.
References
Achanta, R., A. Shaji, et al. 2012. “SLIC Superpixels Compared to State-of-the-Art Superpixel Methods.” IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (11): 2274–82. https://doi.org/f39g5f.
Aggarwal, Charu C., Alexander Hinneburg, et al. 2001. “On the Surprising Behavior of Distance Metrics in High Dimensional Space.” In Database Theory — ICDT 2001, edited by Jan Van den Bussche and Victor Vianu, 1973:420–34. Lecture Notes in Computer Science. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-44503-X_27.
Blaschke, T. 2010. “Object Based Image Analysis for Remote Sensing.” ISPRS Journal of Photogrammetry and Remote Sensing 65 (1): 2–16. https://doi.org/d4ksqf.
Csillik, Ovidiu. 2017. “Fast Segmentation and Classification of Very High Resolution Remote Sensing Data Using SLIC Superpixels.” Remote Sensing 9 (3): 243. https://doi.org/f92zgd.
Nowosad, J., and T. Stepinski. 2021. “Generalizing the Simple Linear Iterative Clustering (SLIC) Superpixels.” GIScience 2021 Short Paper Proceedings. 11th International Conference on Geographic Information Science. September 27-30 2021. Poznań: Poland (Online). https://doi.org/gnw982.
Ren, and Malik. 2003. “Learning a Classification Model for Segmentation.” In Proceedings Ninth IEEE International Conference on Computer Vision, 10–17 vol.1. Nice, France: IEEE. https://doi.org/c6s237.
Wang, Mi, Zhipeng Dong, et al. 2018. “Optimal Segmentation of High-Resolution Remote Sensing Image by Combining Superpixels With the Minimum Spanning Tree.” IEEE Transactions on Geoscience and Remote Sensing 56 (1): 228–38. https://doi.org/gct8gv.