MSER

I have used MSER for feature point detection largely due to its robustness in locating homogeneous regions. In some cases color threshold does not work well due to illumination change, so it is desirable to bypass the thresholds and detect regions with the same color automatically.

Maximally Stable Extreme Region (MESR) is discussed here. A region is part of an image where for any two pixels A, B, there is a path connecting them. Assume the intensity of image ranges from 1 - 255, for each intensity i we consider those pixels with intensity not larger than i. For example, suppose we have a 1D signal 1，2，3，4，1，2，3，4, then if i = 2, the first, second pixels are connected, fifth and sixth pixels are connected, but the two groups of pixels are separated by 3, 4. 

For an intensity i, extreme region means the region can not be any larger under the current i. One i may correspond to multiple extreme regions. For instance, consider a flag with stars, every star is an extreme region, but all the star as a whole is not an extreme region. On the other hand, any partial star is not an extreme region. 

All the extreme regions in an image can form a tree structure, with parent and children nodes. The relationships between extreme regions are either exclusive (no intersection at all), or inclusive (one is totally inside another), and thus it is a tree. If extreme region A contains extreme region B, and no other regions are involved, then A is the parent node of B. All the regions have the same ancestor node. For the flag with stars, the whole flag is one extreme region, so as the stars. Every pixel in the stars belongs to the flag region. 

To find the extreme regions, we build the tree in a bottom up way, listing the pixels in ascending order based on intensity value. Suppose current pixel being processed is x, and all the previous pixels have corresponding extreme regions as well as the parent children structure. To process x, we need to consider it case-by-case

1. Some pixels around x are processed, meaning those pixels are not larger than x. 

2. No pixels around x are processed. 

For case 2, simply build an extreme region centered at x. For case 1, suppose the pixels around x are y, then there are two cases

a. y < x, x will not influence the existing extreme region. We only need to create a parent node for the region containing y, to include x. 

b. This case is more complicated.