Maximally Stable Extremal Regions - Implementation

Implementation

The original algorithm of Matas et al. is in the number of pixels. It proceeds by first sorting the pixels by intensity. This would take time, using . After sorting, pixels are marked in the image, and the list of growing and merging connected components and their areas is maintained using the union-find algorithm. This would take time. In practice these steps are very fast. During this process, the area of each connected component as a function of intensity is stored producing a data structure. A merge of two components is viewed as termination of existence of the smaller component and an insertion of all pixels of the smaller component into the larger one. In the extremal regions, the 'maximally stable' ones are those corresponding to thresholds where the relative area change as a function of relative change of threshold is at a local minimum, i.e. the MSER are the parts of the image where local binarization is stable over a large range of thresholds.

The component tree is the set of all connected components of the thresholds of the image, ordered by inclusion. Efficient (quasi-linear whatever the range of the weights) algorithms for computing it do exist. Thus this structure offers an easy way for implementing MSER.

More recently, Nister and Stewenius have proposed a truly (if the weight are small integers) worst-case method in, which is also much faster in practice. This algorithm is similar to the one of Ph. Salembier et al.