MSER and Sieve Details

Back to Software

What is the connection between MSER's and sieves'?

The papers by George Matas((Matas, et. al. 2002<ref>Matas, J., M. Urban, O. Chum and T. Pajdla (2002). Robust Wide baseline Stereo from Maximally Stable Extremal Regions. BMVC, Cardiff</ref>))((Matas et al., 2004)<ref>Matas, Jiri, et al. Robust wide-baseline stereo from maximally stable extremal regions. Image and vision computing 22.10 (2004): 761-767.</ref>)) (Mishkin et al., 2013)<ref>Dmytro Mishkin, Michal Perdoch,Jiri Matas (2013) Two-view Matching with View Synthesis Revisited arXiv preprint arXiv:1306.3855 </ref> put together an effective way of finding distinguished regions (DR’s) namely maximally stable extremal regions (MSER’s ) with a powerful way of describing the regions at multiple scales and robustly matching such measurements with others in a second image. Since then many authors have confirmed the algorithms as a powerful tool for finding objects in images (review Mikolajczyk et al 2006: <ref>Krystian Mikolajczyk, Tinne Tuytelaars, Cordelia Schmid, Andrew Zisserman, Jiri Matas, Frederik Schaffalitzky, Timor Kadir, L Van Gool, (2006) A Comparison of Affine Region Detectors.International Journal of Computer Vision. DOI: 10.1007/s11263-005-3848-x</ref>

The algorithm underlying that for finding Maximally stable extremal regions (MSER's) is an 'o' sieve. Such algorithms relate closely to mathematical morphology (dilations-erosion (Jackway et al 1996<ref>P. T. Jackway and M. Deriche. Scale-space properties of multiscale morphological dilation-erosion. IEEE Trans. Pattern Analysis and Machine Intelligence , 18(1):38–51</ref>) openings, closings and in particular watersheds (Vincent et al 1991 <ref>Vincent, Luc, and Pierre Soille. "Watersheds in digital spaces: an efficient algorithm based on immersion simulations." IEEE transactions on pattern analysis and machine intelligence 13.6 (1991): 583-598.</ref>) and reconstruction filters (Salembier, P. et. al. 1995<ref>Salembier P, Serra J (1995). Flat zones filtering, connected operators, and filters by reconstruction. IEEE Trans Image Process 4:1153</ref>). In mathematical morphology the 'filtering' element of the MSER algorithm might be called a 'connected-set opening' ('o' sieve) . It is one of a family of closely related algorithms which for which I coined the term sieves. Why?

Why call them sieves and not filters? It is useful to distinguish between two very different signal simplifying algorithms both of which preserve scale-space. So called diffusion 'filters' and non-linear 'sieves'. In a filter-bank, diffusion filters (e.g. the Gaussian filter) spread outliers such as impulses and sharp edged extrema over many scales. On the other hand, sieves do not. (C.f. mechanical sieves in which particles either go through holes or they do not Particle filters and sieves.) There seems to be a lot of philosophical/biological sounding arguments in favour of linear filters. Why? The non-linear 'o' sieve filter-bank appears to be a better feature finder (MSER's) and in the natural world of biology the fundamental signalling devices are non-linear, e.g. action potentials, GTP-binding switch proteins, etc. |}

What do we know about sieves?

As low-pass filters sieves robustly reject outliers (Bangham, J.A. 1993<ref>Bangham, JA (1993) Properties of a Series of Nested Median Filters, Namely the Data Sieve. IEEE Transactions on Signal Processing, 41 (1). pp. 31-42. ISSN 1053-587X</ref>). Superficially it is clear that, by 'knocking off' outliers at increasingly large scales, sieves cannot introduce new extrema. We formally proved that they do not introduce new extrema, i.e. preserve scale-scale (Bangham et al 1996<ref>Bangham, JA, Harvey, RW, Ling, PD and Aldridge, RV (1996) Morphological scale-space preserving transforms in many dimensions. The Journal of Electronic Imaging (JEI), 5 (3). pp. 283-299.</ref>Bangham et al 1996b<ref>Bangham, JA, Chardaire, P, Pye, CJ and Ling, PD (1996) Multiscale nonlinear decomposition: The sieve decomposition theorem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18 (5). pp. 529-539. ISSN 0162-8828</ref> (c.f. the properties of multiscale dilation and erosion, Jackway et al 1996<ref>Jackway, P.T. and Deriche, M. (1996) Scale-space properties of the multiscale morphological dilation-erosion IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.18, no.1, pp.38,51</ref>)

One dimensional sieves are easily implemented by run-length coding the signal, each extremum has a list of just two neighbours. Indeed, in collaboration with CCL we implemented the algorithm on a PC board to characterise the output from line-scan cameras (often used industrially when, in the early 1990's, 2D digital camera's were not easily available). Implementations for images in higher dimensions are similar but keeping track of lists of neighbours is a little more complex.

Applications in addition to their role in MSERs for finding objects in 2D image we have also used sieves in other ways; indeed we started in 1D. For example analysing protein hydrophobicity plots(Bangham, 1988<ref>Bangham, J.A. (1988). Data-sieving hydrophobicity plots. Anal. Biochem. 174, 142–145</ref>), de-noising single channel current data(Bangham et al, 1984<ref>Bangham, J.A., and T.J.C. Jacob (1984). Channel Recognition Using an Online Hardware Filter. In Journal of Physiology, (London: Physiological Society), pp. 3–5</ref>), texture analysis(Southam et al, 2009<ref>Southam, P., and Harvey, R. (2009). Texture classification via morphological scale-space: Tex-Mex features. J. Electron. Imaging 18, 043007–043007</ref>), lipreading(Matthews et al., 2002<ref>Matthews, I., Cootes, T.F., Bangham, J.A., Cox, S., and Harvey, R. (2002). Extraction of visual features for lipreading. Pattern Anal. Mach. Intell. Ieee Trans. 24, 198–213</ref>). In 2D for segmenting 2D through extremal trees(Bangham et al., 1998<ref>Bangham, J.A., Hidalgo, J.R., Harvey, R., and Cawley, G. (1998). The segmentation of images via scale-space trees. In Proceedings of British Machine Vision Conference, pp. 33–43</ref>), maximally stable contours(Lan et al., 2010<ref>Lan, Y., Harvey, R., and Perez Torres, J.R. (2010). Finding stable salient contours. Image Vis. Comput. 28, 1244–1254</ref>), creating painterly pictures from photos(Bangham et al., 2003<ref>Bangham, J.A., Gibson, S.E., and Harvey, R. (2003). The art of scale-space. In Proc. British Machine Vision Conference, pp. 569–578</ref>); and in 3D for segmenting volumes in CAT scans.

References

<references />