Statistical Region Merging (SRM)
Before we want to briefly introduce Statistical Region Merging (SRM), we would like to explain why we need this step, and why this algorithm is an ideal choice.
Compared to other clustering algorithms, SRM is quite leightweight, delivers yet deterministic results and is not dependant on a certain seed (like kmeans for example).
On the other hand it can create as many refinements as one wants and therefore is flexible enough for the task here. Finally there's already been knowledge about this algorithm in the group.
Statistical Region Merging (SRM) [1] is a clustering technique also used directly for image segmentation.
A region $R$ is a set of pixels and the cardinality $\lvert R \rvert$ determines how many pixels are in a region.
Starting with a sorted set of connected regions (w. r. t. some distance function $f$), two regions $R$ and $R'$ are merged if the qualification criteria $\vert \overline{R'}\overline{R} \vert \leq \sqrt{b^2(R)+b^2(R')}$ with $b(R) = g \cdot \sqrt{\frac{\ln \frac{\mathcal{R}_{\lvert R \rvert}}{\delta}}{2Q\lvert R \rvert}}$ is fulfilled.
Therefore, $\mathcal{R}_{\lvert R \rvert}$ is the set of regions with $\lvert R \rvert$ pixels.
Typically $Q$ is chosen as $Q \in \lbrack 256, 1\rbrack$ and $\delta = \frac{1}{\lvert I \rvert^2}$.
The $Q$ parameter mainly influences the merging process. See Figure SRM Regions for an example. Choosing lower values for $Q$, the regions are becoming more coarse. Using a unionfind structure, the segmentation does not need to be recalculated for each $Q$ level. For the step from $q$ to $\frac{q}{2}$, simply the qualification criteria needs to be applied to the regions from the $q$ result. A MATLAB implementation can be found in [2].
[1] Nock R, Nielsen F. Statistical region merging. IEEE Transactions on PAMI. 2004;26:1452–8.
[2] Boltz S. Statistical region merging matlab implementation; 2014. Available
from: http://www.mathworks.com/matlabcentral/fileexchange/
25619imagesegmentationusingstatisticalregionmerging. Accessed 12 Dec 2013.
