Scale-space segmentation


Scale-space segmentation

Scale-space segmentation or multi-scale segmentation is a general framework for signal and image segmentation, based on the computation of image descriptors at multiple scales of smoothing.

One-dimensional hierarchical signal segmentation

Witkin's seminal work in scale space [Witkin, A. P. "Scale-space filtering", Proc. 8th Int. Joint Conf. Art. Intell., Karlsruhe, Germany,1019--1022, 1983.] [A. Witkin, "Scale-space filtering: A new approach to multi-scale description," in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing (ICASSP), vol. 9, San Diego, CA, Mar. 1984, pp. 150--153.] included the notion that a one-dimensional signal could be unambiguously segmented into regions, with one scale parameter controlling the scale of segmentation.

A key observation is that the zero-crossings of the second derivatives (minima and maxima of the first derivative or slope) of multi-scale-smoothed versions of a signal form a nesting tree, which defines hierarchical relations between segments at different scales. Specifically, slope extrema at coarse scales can be traced back to corresponding features at fine scales. When a slope maximum and slope minimum annihilate each other at a larger scale, the three segments that they separated merge into one segment, thus defining the hierarchy of segments.

Image segmentation and primal sketch

There have been numerous research works in this area, out of which a few have now reached a state where they can be applied either with interactive manual intervention (usually with application to medical imaging) or fully automatically. The following is a brief overview of some of the main research ideas that current approaches are based upon.

The nesting structure that Witkin described is, however, specific for one-dimensional signals and does not trivially transfer to higher-dimensional images. Nevertheless, this general idea has inspired several other authors to investigate coarse-to-fine schemes for image segmentation. Koenderink [Koenderink, Jan "The structure of images", Biological Cybernetics, 50:363--370, 1984] proposed to study how iso-intensity contours evolve over scales and this approach was investigated in more detail by Lifshitz and Pizer. [ [http://portal.acm.org/citation.cfm?id=80964&dl=GUIDE&coll=GUIDE Lifshitz, L. and Pizer, S.: A multiresolution hierarchical approach to image segmentation based on intensity extrema, IEEE Transactions on Pattern Analysis and Machine Intelligence, 12:6, 529 - 540, 1990.] ] Unfortunately, however, the intensity of image features changes over scales, which implies that it is hard to trace coarse-scale image features to finer scales using iso-intensity information.

Lindeberg [ [http://www.nada.kth.se/~tony/abstracts/Lin92-IJCV.html Lindeberg, T.: Detecting salient blob-like image structures and their scales with a scale-space primal sketch: A method for focus-of-attention, International Journal of Computer Vision, 11(3), 283--318, 1993.] ] studied the problem of linking local extrema and saddle points over scales, and proposed an image representation called "the scale-space primal sketch" which makes explicit the relations between structures at different scales, and also makes explicit which image features are stable over large ranges of scale including locally appropriate scales for those. Bergholm [Bergholm, F: Edge focusing, IEEE Transactions on Pattern Analysis and Machine Intelligence, 9:6, pages 726 - 741, 1987.] proposed to detect edges at coarse scales in scale-space and then trace them back to finer scales with manual choice of both the coarse detection scale and the fine localization scale.

Gauch and Pizer [ [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=628490 Gauch, J. and Pizer, S.: Multiresolution analysis of ridges and valleys in grey-scale images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:6 (June 1993), pages: 635 - 646, 1993.] ] studied the complementary problem of ridges and valleys at multiple scales and developed a tool for interactive image segmentation based on multi-scale watersheds. The use of multi-scale watershed with application to the gradient map has also been investigated by Olsen and Nielsen [Olsen, O. and Nielsen, M.: Multi-scale gradient magnitude watershed segmentation, Proc. of ICIAP 97, Florence, Italy, Lecture Notes in Computer Science, pages 6–13. Springer Verlag, September 1997.] and been carried over to clinical use by Dam et al. [Dam, E., Johansen, P., Olsen, O. Thomsen,, A. Darvann, T. , Dobrzenieck, A., Hermann, N., Kitai, N., Kreiborg, S., Larsen, P., Nielsen, M.: "Interactive multi-scale segmentation in clinical use" in European Congress of Radiology 2000.] Vincken et al. [Vincken, K., Koster, A. and Viergever, M.: doi-inline|10.1109/34.574787|Probabilistic multiscale image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:2, pp. 109-120, 1997.] ] proposed a hyperstack for defining probabilistic relations between image structures at different scales. The use of stable image structures over scales has been furthered by Ahuja and his co-workers [ [http://vision.ai.uiuc.edu/~msingh/segmen/seg/MSS.html M. Tabb and N. Ahuja, Unsupervised multiscale image segmentation by integrated edge and region detection, IEEE Transactions on Image Processing, Vol. 6, No. 5, 642-655, 1997.] ] into a fully automated system.

More recently, these ideas for multi-scale image segmentation by linking image structures over scales have been picked up by Florack and Kuijper. [Florack, L. and Kuijper, A.: The topological structure of scale-space images, Journal of Mathematical Imaging and Vision, 12:1, 65-79, 2000.] Bijaoui and Rué [ [http://dx.doi.org/10.1016/0165-1684(95)00093-4 Bijaoui, A., Rué, F.: 1995, A Multiscale Vision Model, "Signal Processing" 46, 345] ] associate structures detected in scale-space above a minimum noise threshold into an object tree which spans multiple scales and corresponds to a kind of feature in the original signal. Extracted features are accurately reconstructed using an iterative conjugate gradient matrix method.

egmentation of vector functions of time

Scale-space segmentation was extended in another direction by Lyon [ [http://www.dicklyon.com/tech/Scans/ICASSP87_ScaleSpace-Lyon.pdf Richard F. Lyon. "Speech recognition in scale space," Proc. of 1987 ICASSP. San Diego, March, pp. 29.3.14, 1987.] ] to vector-valued functions of time, where the vector derivative does not have maxima and minima, and the second derivative does not have zero crossings, by putting segment boundaries instead at maxima of the Euclidean magnitude of the vector derivative of the smoothed vector signals. This technique has been applied to segmentation of speech and of text. [ [http://cobweb.ecn.purdue.edu/~malcolm/ibm/pubs/ICASSP2001-Segmentation.pdf Slaney, M. Ponceleon, D., "Hierarchical segmentation using latent semantic indexing in scalespace", "Proc. Intl. Conf. on Acoustics, Speech, and Signal Processing" (ICASSP '01) 2001] ]

References

ee also

*segmentation (image processing)
*scale-space


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Scale space — theory is a framework for multi scale signal representation developed by the computer vision, image processing and signal processing communities with complementary motivations from physics and biological vision. It is a formal theory for handling …   Wikipedia

  • Scale space implementation — Scale space Scale space axioms Scale space implementation Feature detection Edge detection Blob detection Corner detection …   Wikipedia

  • Segmentation (image processing) — In computer vision, segmentation refers to the process of partitioning a digital image into multiple regions (sets of pixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more… …   Wikipedia

  • Scale-invariant feature transform — Feature detection Output of a typical corner detection algorithm …   Wikipedia

  • Multi-scale approaches — The scale space representation of a signal obtained by Gaussian smoothing satisfies a number of special properties, scale space axioms, which make it into a special form of multi scale representation. There are, however, also other types of multi …   Wikipedia

  • Ridge detection — The ridges (or the ridge set) of a smooth function of two variables is a set of curves whose points are, loosely speaking, local maxima in at least one dimension. For a function of N variables, its ridges are a set of curves whose points are… …   Wikipedia

  • Сегментация (обработка изображений) — У этого термина существуют и другие значения, см. Сегментация. В компьютерном зрении, сегментация  это процесс разделения цифрового изображения на несколько сегментов (множество пикселей, также называемых суперпикселями). Цель сегментации… …   Википедия

  • Blob detection — Feature detection Output of a typical corner detection algorithm …   Wikipedia

  • Harris affine region detector — In the fields of computer vision and image analysis, the Harris affine region detector belongs to the category of feature detection. Feature detection is a preprocessing step of several algorithms that rely on identifying characteristic points or …   Wikipedia

  • Affine shape adaptation — is a methodology for iteratively adapting the shape of the smoothing kernels in an affine group of smoothing kernels to the local image structure in neighbourhood region of a specific image point. Equivalently, affine shape adaptation can be… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.