MSER and Sieve Details - Revision history

AndrewBangham: /* Could non-linear filter banks (sieves) have evolved in biological systems? */

2014-08-07T17:21:57Z

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

← Older revision		Revision as of 18:21, 7 August 2014
Line 60:		Line 60:

	====<span style="color:Navy;">Could non-linear filter banks (sieves) have evolved in biological systems?</span>====		====<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. ''We look where those lights are shining and what we find seems to fit that intuition'' e.g. [http://en.wikipedia.org/wiki/Scale_space#Why_a_Gaussian_filter.3F Gaussian]/[http://en.wikipedia.org/wiki/Gabor_filter Gabor]. ''Or perhaps has to fit for want of other ''torches''''. <br><br>		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 leaving us with the best hypothesis, theoretical framework, ~~so far~~.		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.		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.

AndrewBangham: /* Both Gaussian filters and Sieves preserve scale-space */

2014-08-07T17:00:09Z

Both Gaussian filters and Sieves preserve scale-space

← Older revision		Revision as of 18:00, 7 August 2014
Line 37:		Line 37:
	\|}		\|}
	'''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>		'''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]] Fig. 5<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>		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>		'''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>

AndrewBangham: /* Both Gaussian filters and Sieves preserve scale-space */

2014-08-07T15:53:36Z

Both Gaussian filters and Sieves preserve scale-space

← Older revision		Revision as of 16:53, 7 August 2014
Line 36:		Line 36:
	\|[[Image:UpsideDownWitkin.jpg\|300px\|AAMToolbox]]		\|[[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>		'''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]] 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>		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>		'''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>

AndrewBangham: /* Gaussian filters preserve scale space */

2014-08-06T15:59:54Z

Gaussian filters preserve scale space

← Older revision		Revision as of 16:59, 6 August 2014
Line 14:		Line 14:

	====<span style="color:#9457EB;">'''Gaussian filters preserve scale space''' </span> ====		====<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 ~~anisotropic~~ then there is one simple filter that will produce the same result. A Gaussian blur filter.<br><br>		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.		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>		<br><br>

AndrewBangham: /* Both Gaussian filters and Sieves preserve scale-space */

2014-07-31T12:12:26Z

Both Gaussian filters and Sieves preserve scale-space

← Older revision		Revision as of 13:12, 31 July 2014
Line 39:		Line 39:
	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>		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>		'''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>		(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.		'''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>		<br><br>

AndrewBangham: /* Implementation */

2014-07-31T12:10:35Z

Implementation

← Older revision		Revision as of 13:10, 31 July 2014
Line 49:		Line 49:
	===='''Implementation'''====		===='''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.		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]]		[[Image:Scan 10.jpeg\|350px\|right\|first hardware implementation of sieve]]<br>
	First hardware implementation of ~~the first~~ few stages ~~of a sieve~~. Later implementations used an application-specific integrated circuit (ASIC). We wanted speed for the line-scan cameras.<br><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''' ====		===='''Applications''' ====

AndrewBangham at 12:07, 31 July 2014

2014-07-31T12:07:39Z

← Older revision		Revision as of 13:07, 31 July 2014
Line 37:		Line 37:
	\|}		\|}
	'''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>		'''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>
	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 ~~worth~~ further characterisation as feature points.<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>		'''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>		(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>

AndrewBangham: /* Both Gaussian filters and Sieves preserve scale-space */

2014-07-31T12:03:59Z

Both Gaussian filters and Sieves preserve scale-space

← Older revision		Revision as of 13:03, 31 July 2014
Line 37:		Line 37:
	\|}		\|}
	'''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>		'''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>
	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 ~~interesting regions~~ worth further characterisation.<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 worth 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>		'''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 ~~...~~")<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>		(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>
	'''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.		'''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>		<br><br>

	*Small, hot areas (outliers) are smoothed out as are sharp edges.		*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		*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>
	(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. <span style="color:navy;">'''Gaussian filter banks and filter banks based on sieves ~~are~~ complementary to each other'''</span>.		One could consider <span style="color:navy;">'''Gaussian filter banks and filter banks based on sieves as complementary to each other'''</span>.

	===='''Implementation'''====		===='''Implementation'''====

AndrewBangham: /* Implementation */

2014-07-30T21:54:12Z

Implementation

← Older revision		Revision as of 22:54, 30 July 2014
Line 49:		Line 49:
	===='''Implementation'''====		===='''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.		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.
	<br><br>		[[Image:Scan 10.jpeg\|350px\|right\|first hardware implementation of sieve]]
			First hardware implementation of the first few stages of a sieve. Later implementations used an application-specific integrated circuit (ASIC). We wanted speed for the line-scan cameras.<br><br>

	===='''Applications''' ====		===='''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.		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.

AndrewBangham: /* Both Gaussian filters and Sieves preserve scale-space */

2014-07-30T21:41:57Z

Both Gaussian filters and Sieves preserve scale-space

← Older revision		Revision as of 22:41, 30 July 2014
Line 37:		Line 37:
	\|}		\|}
	'''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>		'''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>
	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 '''<span style="color:#9457EB;">important reasons why MSER's</span>''' are so useful for finding interesting regions worth further characterisation.<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 interesting regions worth further characterisation.<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>		'''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 ...")<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>		(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><br>