Generalizing the Simple Linear Iterative Clustering (SLIC) superpixels

class: inverse, left, nonum, clear
background-image: url("figs/animation.gif")
background-size: cover

.captionstyle[Jakub Nowosad, Tomasz Stepinski]
.pull-right2[.captionstyle[GIScience 2021, 2021-09-28]]

---
# Spatial segmentation

.pull-left[
**Segmentation** - partitioning space to identify homogeneous objects

Recently, **an approach of superpixel become considered as a promising segmentation technique**.
]

.pull-right[
<div class="figure" style="text-align: center">
<img src="figs/esch.png" alt="Esch (2008), doi:10.1109/LGRS.2008.919622" width="75%" />
Esch (2008), doi:10.1109/LGRS.2008.919622
</div>
]

---
# Superpixels

.pull-left[
<div class="figure" style="text-align: center">
<img src="figs/csillik.png" alt="Csillik (2017), doi:10.3390/rs9030243" width="100%" />
Csillik (2017), doi:10.3390/rs9030243
</div>
]

.pull-right[
**Main idea: create groupings of cells with similar values**, which result in an **over-segmentation**.

**Superpixels** also **carry more information than each cell alone**, and thus they **can speed up the subsequent processing efforts**.

A large number of methods for creating superpixels were developed (*Stutz et al (2018), doi:10.1016/j.cviu.2017.03.007*), with **the SLIC algorithm** (*Achanta et al. (2012), doi:10.1109/TPAMI.2012.120*) **being the most prominent**. 
]

---
# SLIC

**SLIC starts with regularly located cluster centers** spaced by the interval of `$S$`.

.pull-left[
<img src="figs/slic1.png" width="90%" style="display: block; margin: auto;" />
]

.pull-right[
<img src="figs/slic2.png" width="90%" style="display: block; margin: auto;" />
]

---
# SLIC

.pull-left[

Next, **each cell is assigned to the nearest cluster center**, and **the distance `$D$` is calculated between the cluster centers and cells** in the `$2S \times 2S$` region.

$$
D = \sqrt{\left(\frac{d_c}{m}\right)^2 + \left(\frac{d_s}{S}\right)^2}
$$

where `$d_c$` is the color (spectral) distance, `$m$` is the compactness parameter, `$d_s$` is the spatial (Euclidean) distance, and `$S$` is the interval between the initial cluster centers.

]

.pull-right[
<img src="figs/slic3.png" width="90%" style="display: block; margin: auto;" />
]

---
# SLIC

The color (spectral) distance is calculated between values `$I(x_i,y_i,s_p)$` and `$I(x_j,y_j,s_p)$` for a spectral band `$s_p$` in the set of spectral bands `$B$`:

$$
dc = \sqrt{\sum{p \in B}{(I(x_i,y_i,s_p)-I(x_j,y_j,s_p))^2}}
$$

<hr>

The spatial (Euclidean) distance between cells represents spatial proximity:

$$
d_s = \sqrt{(x_j - x_i)^2 + (y_j - y_i)^2}
$$

<hr>

**The color distance controls the homogeneity of superpixels.**

**The spatial distance is related to spatial contiguity.**

---
# SLIC

.pull-left[
Afterward, **new cluster centers (centroids) are updated for the new superpixels**, and their color values are the average of all the cells belonging to the given superpixel.

**The SLIC algorithm works iteratively**, repeating the above process until it reaches the expected number of iterations.

]
.pull-right[
<img src="figs/ga.gif" width="90%" style="display: block; margin: auto;" />
]

---
# SLIC

The last, optional, step **enforces the 4-connectivity of the cell belonging to the same superpixels** by reassigning disjoint cells.

.pull-left[
<img src="figs/slic4.png" width="88%" style="display: block; margin: auto;" />
]

.pull-right[
<img src="figs/slic5.png" width="88%" style="display: block; margin: auto;" />
]

---
class: left, middle, clear, inverse
# Problem

### Both color (spectral) and spatial distances in the SLIC algorithm are based on the Euclidean distance.

### Using the Euclidean distance to calculate color distances is adequate in many cases, however, it limits the possible usability of the SLIC for spatial data other than images.

---
# Generalization

**We propose an extension of SLIC that allows  using any distance measure to calculate the semantic distance.**

In this extension, ** `$d_c$` can be replaced with any distance/dissimilarity measure.**

<hr>

For example, **raster time-series could be compared with dynamic time warping**, while **distances between sets of categorical variables could be calculated using Jenson-Shannon distance**:

$$
d_c = H(\frac{A + B}{2}) - \frac{1}{2}[H(A) + H(B)]
$$

where A and B are normalized sets of values characterizing the compared cells, and `$H(A)$` and `$H(B)$` indicates values of Shannon's entropy for these sets:

$$
H(A) = -\sum_{p \in A}{A_p log_2 A_p}
$$

`$A_p$` is the `$pth$` value of the first of the compared cell.

---
# Generalization

Also, notice that in the SLIC iterations, **new cluster centers (centroids) have color values that are the average of all the cells belonging to the given superpixel**.

However, **different types of input variables could require different averaging functions**.

Simple averaging (mean) is proper for most of the continuous variables but is not appropriate for categorical ones.

Therefore, **our extension also allows applying other averaging functions that just the mean**.

---
# Generalization

.lc2[
We implemented the above idea in the R programming language as an open-source package **supercells**.

**The package allows for:**

- any number of variables (raster layers)
- the use of about 50 build-in distance measures (including Euclidean, Manhattan, Jensen-Shannon, and dynamic time wrapping), and accepts any user-defined ones
- the use of any defined averaging function, including mean and median
]

.rc2[
<img src="figs/logo.png" width="691" style="display: block; margin: auto;" />
]

The package installation instructions and documentation can be found at https://github.com/Nowosad/supercells.

---
# Examples

.pull-left[
<img src="figs/tm1.png" width="1099" style="display: block; margin: auto;" />
**A land cover classification of Ohio with a rectangle indicating the area around Mount Vernon, Ohio**
]

.pull-right[
<img src="figs/tm2a.png" width="1680" style="display: block; margin: auto;" />
A land cover classification of the area around Mount Vernon, Ohio
]

---
# Examples

.pull-left[
<img src="figs/tm1.png" width="1099" style="display: block; margin: auto;" />
A land cover classification of Ohio with a rectangle indicating the area around Mount Vernon, Ohio
]

.pull-right[
<img src="figs/tm2b.png" width="1685" style="display: block; margin: auto;" />
**Deriving proportions of land cover categories in windows of 10 by 10 cells**
]

---
# Examples

.lc[
**The proportions can be stored as 17 rasters with values between 0 and 1**

**This allows to create superpixels using the Jensen-Shannon distance**
]

.rc[
<img src="figs/tm3a.png" width="85%" style="display: block; margin: auto;" />
Superpixels created based on proportions of land cover categories
]

---
# Examples

.lc[
The proportions can be stored as 17 rasters with values between 0 and 1

This allows to create superpixels using the Jensen-Shannon distance
]

.rc[
<img src="figs/tm3b.png" width="85%" style="display: block; margin: auto;" />
**Superpixels created based on proportions of land cover categories**
]

---
# Examples

.pull-left[
<img src="figs/tm4.png" width="90%" style="display: block; margin: auto;" />

]

.pull-right[
**Possible next steps:**

- **External validation** based on some existing borders
- **Internal validation** using inhomogeneity and isolation measures
- **Post-processing** of the results (e.g., merging similar, adjacent superpixels)
]

---
# Other examples

.pull-left[
**One variable (e.g., NDVI) or multi-variable (e.g., RBG) rasters**
<img src="figs/tm_ndvi.png" width="2991" style="display: block; margin: auto;" /><img src="figs/tm_rgb.png" width="2988" style="display: block; margin: auto;" />
]

.pull-right[
**Time-series with the use of the dynamic time warping distance**
<img src="figs/tm_ts.png" width="1676" style="display: block; margin: auto;" />
]

---
class: left, top, clear2

.pull-left[

## Summary

- Spatial **segmentation techniques** (e.g., superpixels) **allows to create groupings of cells with similar values**
- SLIC is one of the most prominent superpixels algorithm
- **We propose an extension of SLIC that allows using any distance measure to calculate the color distance, and any averaging function**
- Superpixels for spatial data are now available in R with the **supercells** package 
- This is still a work in progress - **any comments, ideas, suggestions, use cases are welcomed**
]

.pull-right[
## Contact

Twitter: <svg viewBox="0 0 512 512" style="height:1em;position:relative;display:inline-block;top:.1em;" xmlns="http://www.w3.org/2000/svg"> <path d="M459.37 151.716c.325 4.548.325 9.097.325 13.645 0 138.72-105.583 298.558-298.558 298.558-59.452 0-114.68-17.219-161.137-47.106 8.447.974 16.568 1.299 25.34 1.299 49.055 0 94.213-16.568 130.274-44.832-46.132-.975-84.792-31.188-98.112-72.772 6.498.974 12.995 1.624 19.818 1.624 9.421 0 18.843-1.3 27.614-3.573-48.081-9.747-84.143-51.98-84.143-102.985v-1.299c13.969 7.797 30.214 12.67 47.431 13.319-28.264-18.843-46.781-51.005-46.781-87.391 0-19.492 5.197-37.36 14.294-52.954 51.655 63.675 129.3 105.258 216.365 109.807-1.624-7.797-2.599-15.918-2.599-24.04 0-57.828 46.782-104.934 104.934-104.934 30.213 0 57.502 12.67 76.67 33.137 23.715-4.548 46.456-13.32 66.599-25.34-7.798 24.366-24.366 44.833-46.132 57.827 21.117-2.273 41.584-8.122 60.426-16.243-14.292 20.791-32.161 39.308-52.628 54.253z"></path></svg> [jakub_nowosad](https://twitter.com/jakub_nowosad)

Websites:

- https://nowosad.github.io
- http://sil.uc.edu/

## Resources

Slides: [nowosad.github.io/giscience-2021](https://nowosad.github.io/giscience-2021/)

Short paper: [paper33](https://raw.githubusercontent.com/Nowosad/giscience2020-files/master/paper_33.pdf)

Software:

- *Spatial superpixels* - https://github.com/Nowosad/supercells
- *Quality of regions* - https://github.com/Nowosad/regional

]