How to choose the `compactness` parameter?

[Nowosad]

@Nowosad, would these same parameters work for tuning compactness? And if so, would you be able to provide some guidance on how to choose the range of values to test? Adjusting the formula from your 2021 paper to be in terms of supercells parameters I believe the distance equation should be

$$D= \sqrt{(\frac{d\text{spectral}}{\text{compactness}})^2 +(\frac{d\text{spatial}}{\text{step}})^2} $$ (though I'm unsure if step should be converted from cell to map units).

From this equation I can see that if the same spectral data were run through the SLIC algorithm but it was measured in different units, the compactness parameter would need to change to get an equivalent result. From doing some reading and looking at the equation I know that larger values will emphasize space and be closer to k means clustering of coordinates whereas smaller values will emphasize spectral characteristics more, and that compactness depends on the range of input cell values and selected distance measure. That being said, given the range of data and selected distance measure (euclidean in my case), I'm unsure how to know what a small value for compactness is, what a large value is, and what a value that provides approximately equal weight would be. Do you have any guidance on that?

Originally posted by @ailich in https://github.com/Nowosad/supercells/issues/21#issuecomment-1875651483

[Nowosad]

Hi @ailich, I do not have enough time to provide a complete answer, but:

1. Equation (see https://github.com/Nowosad/supercells/blob/21ba30016e9501505fbcf638d74bf5e029570604/src/slic.cpp#L135) -- it looks correctly. Step is not converted to map units.
2. You are right that compactness depends on the range of the data values, their dimensions, the distance measure used, etc. Thus, currently, there is no easy way to decide on its best value.
3. I usually start with clean = FALSE and try a few different values of compactness to build an intuition of how it influences the results.
4. I am trying to think of how to normalize the d_spectral values -- it seems to be a tricky thing, as we do not know the maximum possible distance (in the data) beforehand.
5. "what a value that provides approximately equal weight would be" -- I am also trying to think about this... What would that even mean? What is the situation in which we can say that spectral and spatial distances impact are equal? It that even possible to say?

@ailich I look forward to reading your thoughts and ideas on this topic!

[ailich]

Thanks @Nowosad, I'll try running a few different values with clean=FALSE. In terms of what "equal weighting" would mean, I was mainly thinking that the extremes are clustering based only on spatial coordinates (e.g. k-means clustering of coordinates) and clustering on spectral data (e.g. running k-means clustering on the spectral data with no consideration of proximity and connectivity). compactness is tuning the balance between those two extremes, and I guess I wanted a sense of which end of the spectrum I'm closer to for a given compactness value. Based on the equation, since total distance is essentially a sum of dspectral/compactness and dspatial/step, I guess in the end result the average across all pixels relative to the center of the superpixel is contained in, dspectral/compactness would be approximately equal to dspatial/step if spectral and spatial distance were of "equal" weight.

In terms of optimizing the compactness factor I found this paper that suggests trying a range of values (with clean=TRUE) and finding a value that minimizes the variance of spectral values in the superpixels. I need to read it a bit more carefully to understand the details of the normalization, but this seems to be essentially the procedure. My intuition was that the variance would continuously decline, but since it is run with the connectivity step (clean=TRUE) it states "the mean [variance] increased if the compactness factor become too small. This can be explained as follows: A compactness factor that is too small results in a severe spatial fragmentation of superpixels at first, and then the small fragments are merged into the largest neighboring superpixels in the connectivity enforcement process."

[ailich]

Additionally in the original Achanta et al 2012 paper they state "simply defining D to be the five-dimenensional Euclidean distance in labxy space will cause inconsistencies in clustering behavior for different superpixel sizes... To combine the two distances into a single measure, it is necessary to normalize color proximity and spatial proximity by their respective maximum distances within a cluster." They then use step to normalize spatial distance since that is the expected maximum in a cluster, and state that compactness can be specified as a constant since "determining the maximum color distance is not so straightforward, as color distances can vary significantly from cluster to cluster and image to image." However, later they mention that an discussion a variant of SLIC called ASLIC that adaptively changes the compactness (and maximum spatial distance) parameter for each cluster. In this method, "instead of using constant values, ASLIC dynamically normalizes the proximities for each cluster using its maximum observed spatial and color distances (ms,mc) from the previous iteration." The method has the benefit of not needing to set compactness but it did have decreased performance relative to traditional SLIC. The equation in this case is

$$D= \sqrt{(\frac{d_c}{m_c})^2 + (\frac{d_s}{m_s})^2}$$

Perhaps it would be possible to implement ASLIC as an option and/or have a tool to estimate a "good" starting point for compactness. This tool could generate 0th iteration superpixels where each pixel is associated with one of the the initial cluster centers based only on spatial proximity. Then within each cluster the maximum spectral distance could be calculated and you could get a summary of the minimum, mean, median, and maximum across all clusters to get a feel for the range of values that may be appropriate. Lastly, in the paper they state that in CIELAB color space, compactness can take on values in the range of 1-40. They don't specify how they determined that, but if it could possible to calculate the the possible range of the compactness parameter based on the observed or possible known range of the spectral data variables, that could help in providing a more informed search window when testing different compactness values.