MSER and Sieve Details: Difference between revisions

From BanghamLab
Jump to navigation Jump to search
 
(90 intermediate revisions by the same user not shown)
Line 2: Line 2:
==<span style="color:Navy;">What is the connection between MSER's and sieves'?</span>==
==<span style="color:Navy;">What is the connection between MSER's and sieves'?</span>==
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>))
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 (<span style="color:Navy;">'''''MSER’s''''' </span>) 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>
(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 (<span style="color:Navy;">'''''MSER’s''''' </span>) 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>, Kimmel 2011 <ref>Kimmel, R., Zhang, C., Bronstein, A.M., Bronstein, M. (2011) ''Are MSER features really interesting?'' IEEE Trans. Pattern Analysis and Machine Intelligence 33:2316–2320</ref>
<br><br>
<br><br>
<!--(This is a ''blast from the past''. I failed to popularise it at the time, however, '''MSER's are now attracting lots of attention''' so I'm now contributing my bit a little late in the day.) <br><br>-->
<!--(This is a ''blast from the past''. I failed to popularise it at the time, however, '''MSER's are now attracting lots of attention''' so I'm now contributing my bit a little late in the day.) <br><br>-->
Line 10: Line 10:
, 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?  
, 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?  
<br><br>
<br><br>
'''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 [http://en.wikipedia.org/wiki/Mesh_%28scale%29 Particle filters and sieves].)  There seems to be a lot of philosophical/biological sounding arguments in favour of [http://en.wikipedia.org/wiki/Scale_space 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.
====<span style="color:#9457EB;">'''Why call the family of feature finding algorithms ''sieves'' and not ''filters''?''' </span> ====
I thought it may be helpful to distinguish between <span style="color:#9457EB;">'''two very different signal simplifying algorithms'''</span> both of which preserve scale-space: <span style="color:#9457EB;">'''linear 'filters'''' </span> and <span style="color:#9457EB;">'''non-linear 'sieves''''</span>. In a linear-filter-bank such as a bank of Gaussian filters the input signal is separated, prism like, into frequency related scale bands (large and small blobs). Like all linear filters they spread outliers such as impulses and sharp edges over many scales. Sieves do not - hence the distinction. Now Gaussian filters have a very attractive property, that it turns out, is shared with sieves ...<br><br>


====<span style="color:#9457EB;">'''Gaussian filters preserve scale space''' </span> ====
In the 1980's-1990's there were many publications on the properties of Gaussian (diffusion) filters. Key is that they ''preserve'' [http://en.wikipedia.org/wiki/Scale_space scale-space] (Babaud et. al. 1986 "The uniqueness of the Gaussian kernel ...")<ref>Babaud, Jean; Witkin, Andrew P.; Baudin, Michel; Duda, Richard O., "Uniqueness of the Gaussian Kernel for Scale-Space Filtering," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.PAMI-8, no.1, pp.26,33, Jan. 1986 doi: 10.1109/TPAMI.1986.4767749</ref> To understand what is meant: imagine a photo projected onto a wall using a data projector. Leave it on for an hour. Then turn of the projector. Regions that were illuminated (white) will be warmer than those that were black. Now turn the projector off and turn on an infrared image viewer. Once again the image will be visible (warm and cold regions showing up). However, as we wait heat will diffuse from the warm to cooler regions - the image will become blurred. Heat will never flow to form new extrema. If the thermal conductivity of the surface is uniform and isotropic then there is one simple filter that will produce the same result. A Gaussian blur filter.<br><br>
Here, we have three panels illustrating one dimensional signals represented in scale space. I have used 'heat maps' to represent the signal intensity at each scale.
<br><br>
=====Both Gaussian filters and Sieves preserve scale-space=====
{| border="0" cellpadding="5" cellspacing="5"    3D extrema thumb.gif
|- valign="top"
|width="20%"| <!-- [[Image:IllustrateSIV_1_01_thumb.gif|140px|IllustrateSIV 1 01 thumb]]-->
|'''Consider a signal''', <math>X</math><br>
X=getData('PULSES3WIDE')
>blue  X=0 5 5 0 0 1 1 4 3 3 2 2 1 2 2 2 1 0 0 0 1 1 0 3 2 0 0 0 6 0 0
|}
{| border="0" cellpadding="5" cellspacing="5"
|- valign="top"
|width="50%"| The data has minima and maxima of different scales (lengths). 
|[[Image:IllustrateSIV_1_02.png|400px]]
|}
{| border="0" cellpadding="5" cellspacing="5"
|- valign="top"
|width="60%"| [[Image:Siv4 test 5.png|400px|'m' non-linear filter (sieve) compared to Gaussian filter]]
|[[Image:UpsideDownWitkin.jpg|300px|AAMToolbox]]
|}
'''Left Panel.''' Here, a '''A low-pass''' siv4.m gradually removes extrema (from the signal shown above) as scale increases from scale 1 to scale 64. The resulting traces are shown as a 'heat map' where the signal goes from left to right, bright colours like red are large amplitude, small scale extrema. At each increasing scale (down the map) extrema have been removed. The 'm'-sieve preserves scale-space so no new extrema (light regions) are formed as we move to increasing scales. Moreover, the features do not wander about in scale-space. We could say that in one dimension we measure pulse length using a sieve just as we might use a ruler or measuring tape in the physical world. <br><br>
([[siv4_test.m code|siv4_test code]] the code generates several Figures - the one above is Fig. 5.)<br><br>
Superficially it is clear that, by 'knocking off' outliers at increasingly large scales, sieves cannot introduce new extrema but to clarify the issue we<span style="color:#9457EB;"> formally proved that they do not introduce new extrema, i.e. preserve '''''scale-space'''''</span> (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>). Preserving scale-space is one of the '''<span style="color:#9457EB;">important reasons why MSER's</span>''' are so useful for finding interest points worthy of further characterisation as feature points.<br><br>
'''Middle Panel'''. A ''Gaussian'' filter bank also preserves scale-space as shown by Witkin 1986. No new features (local extrema) are formed. However, the features wander about in scale-space.<br>
(Babaud et. al. 1986 "The uniqueness of the Gaussian kernel  for Scale-Space Filtering")<ref>Babaud, Jean; Witkin, Andrew P.; Baudin, Michel; Duda, Richard O., "Uniqueness of the Gaussian Kernel for Scale-Space Filtering," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.PAMI-8, no.1, pp.26,33, Jan. 1986 doi: 10.1109/TPAMI.1986.4767749</ref>
<br><br>
'''Right Panel,''' Babaud's original Figure showing heat-map 'isotherms'. (Actually, to be consistent with the other Panels I have flipped the image vertically.) The features wander about in scale-space and sharp edged features do not sharply disappear - they are smudged over scale-space.
<br><br>
*Small, hot areas (outliers) are smoothed out as are sharp edges.
*Sieves are the opposite, impulses and regions with sharp edges do not spread over many scales (c.f. mechanical sieves in which particles (granules) either go through holes or they do not [http://en.wikipedia.org/wiki/Mesh_%28scale%29 Particle filters and sieves].)  They do however, spread smooth waveforms over many scales.<br><br>
One could consider <span style="color:navy;">'''Gaussian filter banks and filter banks based on sieves as complementary to each other'''</span>.
===='''Implementation'''====
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 [http://www.cambridgeconsultants.com/ CCL] we implemented the algorithm on a PC board to characterise the output, in real time, 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, but see Nister and Stewenius,  <ref>D. Nister and H. Stewenius ''Linear time maximally stable extremal regions'' ECCV 2008 part II LNCS 5303 pp 183-196. </ref> for a cool implementation of the MSER algorithm.
[[Image:Scan 10.jpeg|350px|right|first hardware implementation of sieve]]<br>
'''Dug up from the past.''' First hardware implementation of a sieve. Just a few stages.  Later implementations used an application-specific integrated circuit (ASIC). We wanted a full decomposition at speed for the line-scan cameras.<br><br>
===='''Applications''' ====
In addition to their role finding in objects in 2D images we have used sieves to analyse 1, 2 and 3D signals. We started in 1D (digital images were not available at the time). For example analysing protein hydrophobicity plots(Bangham, 1988<ref>Bangham, J.A. (1988) ''Data-sieving hydrophobicity plots. Anal. Biochem''. 174, 142–145</ref>) for which it was found by Fasman (1990) <ref>Fasman and Gilbert "The prediction of transmembrane protein sequences and their conformation: an evaluation" in Trends in Biochemistry 15 pp 89:91</ref> to "correctly predict the hydrophobic transmembrane regions ..." [[Details on hydrophobicity plots | (see more details)]]. , 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 The Journal of Physiology, (London: Physiological Society), pp. 3–5</ref>). Much later we used them for 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>) and 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 images through extremal trees  (c.f. MSER's) (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>)(Fo2Pix sold about 65,000 licences for our software package: ArtMaster); and in 3D for segmenting volumes in CAT scans.
====<span style="color:Navy;">Could non-linear filter banks (sieves) have evolved in biological systems?</span>====
Biological systems are too complex too huge to comprehend without some initial insights. In vision the particular theoretical 'torches' that light the experimental findings are the Fourier transform, Gaussian or Gabor filter banks. Is it possible that <span style="color:Navy;">''we look where those lights are shining and what we find seems to fit that intuition'' </span>e.g. [http://en.wikipedia.org/wiki/Scale_space#Why_a_Gaussian_filter.3F Gaussian]/[http://en.wikipedia.org/wiki/Gabor_filter Gabor]. <span style="color:Navy;">''Or perhaps has to fit for want of other ''torches''''.</span> <br><br>
So care is needed. Science should be creative,  we should create a number of torches pointing in different directions (based on different theoretical frameworks where possible) then use experimental evidence to reject those that do not fit. That will leaving us with the best hypothesis - theoretical framework, until it too is rejected. This is just science rhetoric of course.


====<span style="color:Navy;">What do we know about sieves among other filters?</span>====
We now know that sieves (MSER's) not only exist but offer significant practical advantages over other methods in computer vision. They are an alternative 'torch' that might need rejecting. Perhaps we should re-evaluate the biological evidence. Could the brain be understood in terms of sieves? Were this to be the case then it could change what we look for in brain structures. Hardware implementations of sieves are all about connectivity and relative thresholds as are brains, so perhaps it is possible.
*our hardware implementation of the 1D filter bank was very different to a linear filter bank.
*Likewise the linear time implementation of the 2D MSER algorithm (Nister and Stewenius,  <ref>D. Nister and H. Stewenius ''Linear time maximally stable extremal regions'' ECCV 2008 part II LNCS 5303 pp 183-196. </ref>) in which dynamic connectivity is everything.<br><br>
<span style="color:Navy;">Exploring this problem would be '''just the 'wild' opportunity that I have enjoyed exploring in my research life'''. It would be a wild ride whatever the outcome - unfortunately cancer now (June 2014) leaves me out of the game.<span>.
 
====<span style="color:Navy;">Summary of basic properties of sieves, linear and non-linear filters?</span>====
<br><br>
{| style="width: 80%; height: 60px" border="1"
{| style="width: 80%; height: 60px" border="1"
|- valign="top"
|- valign="top"
!   
!   
! Sieve 1D
! Sieve 2D
! Sieve 3D
! Gaussian 1D
! Gaussian 1D
! Gaussian 2D
! Gaussian 2D
! Median 1D
! Median 1D
! Median 2D
! Median 2D
! Sieve 1D
! Sieve 2D
! Sieve 3D
|-
|-
|- valign="top"
|- valign="top"
| Preserve Scale space || Yes || Yes || No || No
| Preserve Scale space  
! Yes || Yes || Yes
! Yes || Yes || Yes  
|| Yes || Yes || No || No
|-
|-
|- valign="top"
|- valign="top"
| Separate signals by || Pulse Frequency|| Blob Frequency 2D || Roughly Pulse length || Roughly Blob Area
| Separate signals by  
! Length|| Area || Volume
! Length|| Area || Volume
||Pulse Frequency|| Blob Frequency 2D || Roughly Pulse length || Roughly Blob Area
|}
|}
As low-pass filters, sieves robustly reject short lived outliers, e.g. impulses (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 but to be clear we formally proved that they do not introduce new extrema, i.e. preserve '''''scale-space''''' (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>)<br><br>
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.
<br><br>
'''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==
<references />
<references />


==<span style="color:Navy;">How does this measure shapes?</span>==
==<span style="color:Navy;">Limitations?</span>==
==<span style="color:Navy;">Limitations?</span>==

Latest revision as of 17:21, 7 August 2014

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>, Kimmel 2011 <ref>Kimmel, R., Zhang, C., Bronstein, A.M., Bronstein, M. (2011) Are MSER features really interesting? IEEE Trans. Pattern Analysis and Machine Intelligence 33:2316–2320</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 the family of feature finding algorithms sieves and not filters?

I thought it may be helpful to distinguish between two very different signal simplifying algorithms both of which preserve scale-space: linear 'filters' and non-linear 'sieves'. In a linear-filter-bank such as a bank of Gaussian filters the input signal is separated, prism like, into frequency related scale bands (large and small blobs). Like all linear filters they spread outliers such as impulses and sharp edges over many scales. Sieves do not - hence the distinction. Now Gaussian filters have a very attractive property, that it turns out, is shared with sieves ...

Gaussian filters preserve scale space

In the 1980's-1990's there were many publications on the properties of Gaussian (diffusion) filters. Key is that they preserve scale-space (Babaud et. al. 1986 "The uniqueness of the Gaussian kernel ...")<ref>Babaud, Jean; Witkin, Andrew P.; Baudin, Michel; Duda, Richard O., "Uniqueness of the Gaussian Kernel for Scale-Space Filtering," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.PAMI-8, no.1, pp.26,33, Jan. 1986 doi: 10.1109/TPAMI.1986.4767749</ref> To understand what is meant: imagine a photo projected onto a wall using a data projector. Leave it on for an hour. Then turn of the projector. Regions that were illuminated (white) will be warmer than those that were black. Now turn the projector off and turn on an infrared image viewer. Once again the image will be visible (warm and cold regions showing up). However, as we wait heat will diffuse from the warm to cooler regions - the image will become blurred. Heat will never flow to form new extrema. If the thermal conductivity of the surface is uniform and isotropic then there is one simple filter that will produce the same result. A Gaussian blur filter.

Here, we have three panels illustrating one dimensional signals represented in scale space. I have used 'heat maps' to represent the signal intensity at each scale.

Both Gaussian filters and Sieves preserve scale-space
Consider a signal, <math>X</math>
X=getData('PULSES3WIDE')
>blue  X=0 5 5 0 0 1 1 4 3 3 2 2 1 2 2 2 1 0 0 0 1 1 0 3 2 0 0 0 6 0 0
The data has minima and maxima of different scales (lengths). IllustrateSIV 1 02.png
'm' non-linear filter (sieve) compared to Gaussian filter AAMToolbox

Left Panel. Here, a A low-pass siv4.m gradually removes extrema (from the signal shown above) as scale increases from scale 1 to scale 64. The resulting traces are shown as a 'heat map' where the signal goes from left to right, bright colours like red are large amplitude, small scale extrema. At each increasing scale (down the map) extrema have been removed. The 'm'-sieve preserves scale-space so no new extrema (light regions) are formed as we move to increasing scales. Moreover, the features do not wander about in scale-space. We could say that in one dimension we measure pulse length using a sieve just as we might use a ruler or measuring tape in the physical world.

(siv4_test code the code generates several Figures - the one above is Fig. 5.)

Superficially it is clear that, by 'knocking off' outliers at increasingly large scales, sieves cannot introduce new extrema but to clarify the issue we formally proved that they do not introduce new extrema, i.e. preserve scale-space (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>). Preserving scale-space is one of the important reasons why MSER's are so useful for finding interest points worthy of further characterisation as feature points.

Middle Panel. A Gaussian filter bank also preserves scale-space as shown by Witkin 1986. No new features (local extrema) are formed. However, the features wander about in scale-space.
(Babaud et. al. 1986 "The uniqueness of the Gaussian kernel for Scale-Space Filtering")<ref>Babaud, Jean; Witkin, Andrew P.; Baudin, Michel; Duda, Richard O., "Uniqueness of the Gaussian Kernel for Scale-Space Filtering," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.PAMI-8, no.1, pp.26,33, Jan. 1986 doi: 10.1109/TPAMI.1986.4767749</ref>

Right Panel, Babaud's original Figure showing heat-map 'isotherms'. (Actually, to be consistent with the other Panels I have flipped the image vertically.) The features wander about in scale-space and sharp edged features do not sharply disappear - they are smudged over scale-space.

  • Small, hot areas (outliers) are smoothed out as are sharp edges.
  • Sieves are the opposite, impulses and regions with sharp edges do not spread over many scales (c.f. mechanical sieves in which particles (granules) either go through holes or they do not Particle filters and sieves.) They do however, spread smooth waveforms over many scales.

One could consider Gaussian filter banks and filter banks based on sieves as complementary to each other.

Implementation

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, in real time, 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, but see Nister and Stewenius, <ref>D. Nister and H. Stewenius Linear time maximally stable extremal regions ECCV 2008 part II LNCS 5303 pp 183-196. </ref> for a cool implementation of the MSER algorithm.

first hardware implementation of sieve


Dug up from the past. First hardware implementation of a sieve. Just a few stages. Later implementations used an application-specific integrated circuit (ASIC). We wanted a full decomposition at speed for the line-scan cameras.

Applications

In addition to their role finding in objects in 2D images we have used sieves to analyse 1, 2 and 3D signals. We started in 1D (digital images were not available at the time). For example analysing protein hydrophobicity plots(Bangham, 1988<ref>Bangham, J.A. (1988) Data-sieving hydrophobicity plots. Anal. Biochem. 174, 142–145</ref>) for which it was found by Fasman (1990) <ref>Fasman and Gilbert "The prediction of transmembrane protein sequences and their conformation: an evaluation" in Trends in Biochemistry 15 pp 89:91</ref> to "correctly predict the hydrophobic transmembrane regions ..." (see more details). , 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 The Journal of Physiology, (London: Physiological Society), pp. 3–5</ref>). Much later we used them for 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>) and 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 images through extremal trees (c.f. MSER's) (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>)(Fo2Pix sold about 65,000 licences for our software package: ArtMaster); and in 3D for segmenting volumes in CAT scans.

Could non-linear filter banks (sieves) have evolved in biological systems?

Biological systems are too complex too huge to comprehend without some initial insights. In vision the particular theoretical 'torches' that light the experimental findings are the Fourier transform, Gaussian or Gabor filter banks. Is it possible that we look where those lights are shining and what we find seems to fit that intuition e.g. Gaussian/Gabor. Or perhaps has to fit for want of other torches'.

So care is needed. Science should be creative, we should create a number of torches pointing in different directions (based on different theoretical frameworks where possible) then use experimental evidence to reject those that do not fit. That will leaving us with the best hypothesis - theoretical framework, until it too is rejected. This is just science rhetoric of course.

We now know that sieves (MSER's) not only exist but offer significant practical advantages over other methods in computer vision. They are an alternative 'torch' that might need rejecting. Perhaps we should re-evaluate the biological evidence. Could the brain be understood in terms of sieves? Were this to be the case then it could change what we look for in brain structures. Hardware implementations of sieves are all about connectivity and relative thresholds as are brains, so perhaps it is possible.

  • our hardware implementation of the 1D filter bank was very different to a linear filter bank.
  • Likewise the linear time implementation of the 2D MSER algorithm (Nister and Stewenius, <ref>D. Nister and H. Stewenius Linear time maximally stable extremal regions ECCV 2008 part II LNCS 5303 pp 183-196. </ref>) in which dynamic connectivity is everything.

Exploring this problem would be just the 'wild' opportunity that I have enjoyed exploring in my research life. It would be a wild ride whatever the outcome - unfortunately cancer now (June 2014) leaves me out of the game..

Summary of basic properties of sieves, linear and non-linear filters?



Sieve 1D Sieve 2D Sieve 3D Gaussian 1D Gaussian 2D Median 1D Median 2D
Preserve Scale space Yes Yes Yes Yes Yes No No
Separate signals by Length Area Volume Pulse Frequency Blob Frequency 2D Roughly Pulse length Roughly Blob Area

References

<references />

Limitations?