Maximally stable extremal regions

In computer vision, maximally stable extremal regions (MSER) are used as a method of blob detection in images. This technique was proposed by Matas et al. to find correspondences between image elements from two images with different viewpoints. This method of extracting a comprehensive number of corresponding image elements contributes to the wide-baseline matching, and it has led to better stereo matching and object recognition algorithms. In computer vision, maximally stable extremal regions (MSER) are used as a method of blob detection in images. This technique was proposed by Matas et al. to find correspondences between image elements from two images with different viewpoints. This method of extracting a comprehensive number of corresponding image elements contributes to the wide-baseline matching, and it has led to better stereo matching and object recognition algorithms. Image I {displaystyle I} is a mapping I : D ⊂ Z 2 → S {displaystyle I:Dsubset mathbb {Z} ^{2} o S} . Extremal regions are well defined on images if: Region Q {displaystyle Q} is a contiguous subset of D {displaystyle D} . (For each p , q ∈ Q {displaystyle p,qin Q} there is a sequence p , a 1 , a 2 , . . , a n , q {displaystyle p,a_{1},a_{2},..,a_{n},q} and p A a 1 , a i A a i + 1 , a n A q {displaystyle pAa_{1},a_{i}Aa_{i+1},a_{n}Aq} .) (Outer) Region Boundary ∂ Q = { q ∈ D ∖ Q : ∃ p ∈ Q : q A p } {displaystyle partial Q={qin Dsetminus Q:exists pin Q:qAp}} , which means the boundary ∂ Q {displaystyle partial Q} of Q {displaystyle Q} is the set of pixels adjacent to at least one pixel of Q {displaystyle Q} but not belonging to Q {displaystyle Q} . Extremal Region Q ⊂ D {displaystyle Qsubset D} is a region such that either for all p ∈ Q , q ∈ ∂ Q : I ( p ) > I ( q ) {displaystyle pin Q,qin partial Q:I(p)>I(q)} (maximum intensity region) or for all p ∈ Q , q ∈ ∂ Q : I ( p ) < I ( q ) {displaystyle pin Q,qin partial Q:I(p)<I(q)} (minimum intensity region). Maximally Stable Extremal Region Let Q 1 , . . , Q i − 1 , Q i , . . . {displaystyle Q_{1},..,Q_{i-1},Q_{i},...} be a sequence of nested extremal regions ( Q i ⊂ Q i + 1 {displaystyle Q_{i}subset Q_{i+1}} ). Extremal region Q i ∗ {displaystyle Q_{i*}} is maximally stable if and only if q ( i ) = | Q i + Δ ∖ Q i − Δ | / | Q i | {displaystyle q(i)=|Q_{i+Delta }setminus Q_{i-Delta }|/|Q_{i}|} has a local minimum at i ∗ {displaystyle i*} . (Here | ⋅ | {displaystyle |cdot |} denotes cardinality.) Δ ∈ S {displaystyle Delta in S} is a parameter of the method. The equation checks for regions that remain stable over a certain number of thresholds. If a region Q i + Δ {displaystyle Q_{i+Delta }} is not significantly larger than a region Q i − Δ {displaystyle Q_{i-Delta }} , region Q i {displaystyle Q_{i}} is taken as a maximally stable region. The concept more simply can be explained by thresholding. All the pixels below a given threshold are 'black' and all those above or equal are 'white'. Given a source image, if a sequence of thresholded result images I t {displaystyle I_{t}} is generated where each image t {displaystyle t} corresponds to an increasing threshold t, first a white image would be seen, then 'black' spots corresponding to local intensity minima will appear then grow larger. These 'black' spots will eventually merge, until the whole image is black. The set of all connected components in the sequence is the set of all extremal regions. In that sense, the concept of MSER is linked to the one of component tree of the image. The component tree indeed provide an easy way for implementing MSER.