Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Machine Vision and Applications
Published in: Machine Vision and Applications 6/2013

01-08-2013 | Original Paper

Towards a balanced trade-off between speed and accuracy in unsupervised data-driven image segmentation

Authors: Balázs Varga, Kristóf Karacs

Published in: Machine Vision and Applications | Issue 6/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

When it comes to image segmentation in the megapixel domain, most state-of-the-art algorithms use sampling to reduce the amount of data to be processed to reach a lower running time. Random patterns and equidistant sampling usually result in a suboptimal result because, in general, the distribution of image content is not homogeneous. The segmentation framework we propose in this paper, employs a content-adaptive technique that samples homogeneous and inhomogeneous regions sparsely and densely, respectively, thus it preserves information content in a computationally efficient way. Both the sampling procedure and the pixel-cluster assignment are guided by the same nonlinear confidence value, calculated for each image pixel with no overhead, which describes the strength of the pixel-cluster bond. Building on this confidence scheme, each pixel is associated with the most similar class with respect to its spatial position and color. We compare the performance of our framework to other segmentation algorithms on publicly available segmentation databases and using a set of 10-megapixel images, we show that it provides similar segmentation quality to a mean shift-based reference in an order of magnitude shorter time, the speedup being proportional to the amount of details in the input image. Based on our findings, we also sketch up novel design aspects to be taken into account when designing a high resolution evaluation framework.
previous article Geometric steerable medial maps
next article Pi-Tag: a fast image-space marker design based on projective invariants

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
Note: according to our experiments, the quality of the output of the framework is not sensitive to the choice of the \(\lambda \) parameter in a wide range. We performed experiments in the \(0.01 \le \lambda \le 0.2 \) interval, and used \(\lambda = 0.1 \) for all measurements shown.
 
2
Note: since the obtained bandwidth parameter values reside on the extreme of the evaluation intervals, further tests using a parameter domain enhanced with \( h_r = 0.055, h_s = 0.015 \) were carried out, but did not provide better overall results than the OPTIMAL setting.
 
3
The selection of system parameters used for the high resolution measurements was aided by the experience collected during the exhaustive measurements made on the BSDS300, e.g., we found it superfluous to try larger values for \( h_s \), since the resolution is higher.
 
Literature
1.
Abbadeni, N., Zhou, D., Wang, S.: Computational measures corresponding to perceptual textural features. In: ICIP, pp. 897–900 (2000)
2.
Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., Süsstrunk, S.: SLIC superpixels. EPFL Technical Report (2010)
3.
Alpert, S., Galun, M., Basri, R., Brandt, A.: Image segmentation by probabilistic bottom-up aggregation and cue integration. In: CVPR, pp. 1–8 (2007)
4.
Alpert, S., Galun, M., Brandt, A., Basri, R.: Image segmentation by probabilistic bottom-up aggregation and cue integration. PAMI 34, 315–327 (2012)CrossRef
5.
Arbeláez, P., Hariharan, B., Gu, C., Gupta, S., Bourdev, L., Malik, J.: Semantic segmentation using regions and parts. In: CVPR (2012)
6.
Arbeláez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. PAMI 33(5), 898–916 (2011)CrossRef
7.
Bagon, S., Boiman, O., Irani, M.: What is a good image segment? A unified approach to segment extraction. In: ECCV, pp 30–44 (2008)
8.
Beucher, S.: Watershed, hierarchical segmentation and waterfall algorithm. In: Mathematical Morphology and Its Applications to Image Processing, pp. 69–76 (1994)
9.
Biederman, I.: Recognition-by-components: a theory of human image understanding. Psychol. Rev. 94(2), 115–147 (1987)CrossRef
10.
Bitsakos, K., Fermller, C., Aloimonos, Y.: An experimental study of color-based segmentation algorithms based on the mean-shift concept. In: ECCV, pp. 506–519 (2010)
11.
Borenstein, E., Malik, J.: Shape guided object segmentation. In: CVPR, pp. 969–976 (2006)
12.
Borenstein, E., Ullman, S.: Combined top-down/bottom-up segmentation. PAMI 30, 2109–2125 (2007)
13.
Carreira-Perpiñán, M.A.: Acceleration strategies for Gaussian mean-shift image segmentation. In: CVPR, pp. 1160–1167 (2006)
14.
Carreira-Perpiñán, M.A.: Fast nonparametric clustering with Gaussian blurring mean-shift. In: ICML, pp. 153–160 (2006)
15.
Carron, T., Lambert, P.: Color edge detector using jointly hue, saturation and intensity. In: ICIP, pp. 977–981 (1994)
16.
Catanzaro, B.C., Su, B.-Y., Sundaram, N., Lee, Y., Murphy, M., Keutzer, K.: Efficient, high-quality image contour detection. In: ICCV, pp. 2381–2388 (2009)
17.
Chen, W., Song, Y., Bai, H., Lin, C., Chang, E.: Parallel spectral clustering in distributed systems. PAMI 33(3), 568–586 (2011)CrossRef
18.
Cheng, H., Jiang, X., Sun, Y., Wang, J.: Color image segmentation: advances and prospects. Pattern Recognit. 34(12), 2259–2281 (2001)MATHCrossRef
19.
Cheng, Y.: Mean shift, mode seeking, and clustering. PAMI 17(8), 790–799 (1995)CrossRef
20.
Christoudias, C., Georgescu, B., Meer, P.: Synergism in low level vision. In: ICPR, pp. 150–155 (2002)
21.
Comaniciu, D., Meer, P.: Mean shift: a robust approach toward feature space analysis. PAMI 24(5), 603–619 (2002)CrossRef
22.
DeMenthon, D.: Spatio-temporal segmentation of video by hierarchical mean shift analysis. Center for Automation Research, University of Maryland (2002)
23.
Dong, L., Izquierdo, E.: A biologically inspired system for classification of natural images. CSVT 17(5), 590–603 (2007)
24.
Dony, R., Wesolkowski, S.: Edge detection on color images using RGB vector angles. In: CCECE, pp. 687–692 (1999)
25.
Duarte, A., Sánchez, Á., Fernández, F., Montemayor, A.: Improving image segmentation quality through effective region merging using a hierarchical social metaheuristic. Pattern Recognit. Lett. 27(11), 1239–1251 (2006)CrossRef
26.
Felzenszwalb, P., Huttenlocher, D.: Efficient graph-based image segmentation. IJCV 59(2), 167–181 (2004)CrossRef
27.
28.
Fukunaga, K., Hostetler, L.: The estimation of the gradient of a density function, with applications in pattern recognition. IEEE IT 21(1), 32–40 (1975)MathSciNetMATHCrossRef
29.
Georgescu, B., Shimshoni, I., Meer, P.: Mean shift based clustering in high dimensions: a texture classification example. In: ICCV, pp. 456–463 (2003)
30.
Guo, H., Guo, P., Lu, H.: A fast mean shift procedure with new iteration strategy and re-sampling. In: IEEE SMC, pp. 2385–2389 (2006)
31.
He, X.M., Zemel, R.S., Ray, D.: Learning and incorporating top-down cues in image segmentation. In: ECCV, pp. 338–351 (2006)
32.
Hinneburg, A., Keim, D.: Optimal grid-clustering: towards breaking the curse of dimensionality in high-dimensional clustering. In: VLDB, pp. 517–529 (1999)
33.
Hoover, A., Jean-Baptiste, G., Jiang, X., Flynn, P., Bunke, H., Goldgof, D., Bowyer, K., Eggert, D., Fitzgibbon, A., Fisher, R.: An experimental comparison of range image segmentation algorithms. PAMI 18(7), 673–689 (1996)CrossRef
34.
Jiang, X., Marti, C., Irniger, C., Bunke, H.: Distance measures for image segmentation evaluation. In: EURASIP JASP, pp. 209–209 (2006)
35.
36.
Khan, S., Shah, M.: Object based segmentation of video using color, motion and spatial information. In: CVPR, pp. 746–751 (2001)
37.
Kim, J., Hong, K.: A new graph cut-based multiple active contour algorithm without initial contours and seed points. MVA 19(3), 181–193 (2008)
38.
Kim, T.H., Lee, K.M., Lee, S.U.: Learning full pairwise affinities for spectral segmentation. In: CVPR, pp. 2101–2108 (2010)
39.
Levinshtein, A., Stere, A., Kutulakos, K.N., Fleet, D.J., Dickinson, S.J., Siddiqi, K.: Turbopixels: fast superpixels using geometric flows. PAMI 31, 2290–2297 (2009)
40.
Li, L., Socher, R., Fei-Fei, L.: Towards total scene understanding: classification, annotation and segmentation in an automatic framework. In: CVPR, pp. 2036–2043 (2009)
41.
Luo, Q., Khoshgoftaar, T.: Unsupervised multiscale color image segmentation based on MDL principle. IEEE IP 15(9), 2755–2761 (2006)
42.
Maire, M., Arbelaez, P., Fowlkes, C., Malik, J.: Using contours to detect and localize junctions in natural images. In: CVPR, pp.1–8 (2008)
43.
Malisiewicz, T., Efros, A.A.: Improving spatial support for objects via multiple segmentations. In: BMVC (2007)
44.
Martin, D., Fowlkes, C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. PAMI 26(5), 530–549 (2004)CrossRef
45.
Martin, D.R., Fowlkes, C.C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: ICCV, pp. 416–423 (2001)
46.
Maurer Jr, C., Qi, R., Raghavan, V.: A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions. PAMI 25(2), 265–270 (2003)CrossRef
47.
Miller, G., Tolliver, D.: Graph partitioning by spectral rounding: applications in image segmentation and clustering. In: CVPR, pp. 1053–1060 (2006)
48.
Mishra, A.K., Aloimonos, Y., Cheong, L.-F., Kassim, A.: Active visual segmentation. PAMI 34(2), 639–653 (2012)CrossRef
49.
Moghaddam, B., Biermann, H., Margaritis, D.: Defining image content with multiple regions-of-interest. In: IEEE CBAIVL, pp. 89–93 (1999)
50.
Moore, A., Prince, S., Warrell, J., Mohammed, U., Jones, G.: Superpixel lattices. In:CVPR, pp. 1–8 (2008)
51.
Nikou, C., Galatsanos, N., Likas, A.: A class-adaptive spatially variant mixture model for image segmentation. IEEE IP 16, 1121–1130 (2007)
52.
Nikou, C., Likas, A., Galatsanos, N.: A Bayesian framework for image segmentation with spatially varying mixtures. IEEE IP 19(9), 2278–2289 (2010)
53.
Paris, S., Durand, F.: A topological approach to hierarchical segmentation using mean shift. In: CVPR, pp. 1–8 (2007)
54.
Pooransingh, A., Radix, C., Kokaram, A.: The path assigned mean shift algorithm: a new fast mean shift implementation for colour image segmentation. In: ICIP, pp. 597–600 (2008)
55.
Prati, A., Mikic, I., Trivedi, M., Cucchiara, R.: Detecting moving shadows: algorithms and evaluation. PAMI 25(7), 918–923 (2003)
56.
Ren, C.Y., Reid, I.: gSLIC: a real-time implementation of SLIC superpixel segmentation. Technical Report, University of Oxford, Department of Engineering and Science (2011)
57.
Ren, X., Malik, J.: Learning a classification model for segmentation. In: ICCV, pp. 10–17 (2003)
58.
Salah, M., Mitiche, A., Ayed, I.: Multiregion image segmentation by parametric kernel graph cuts. IEEE IP 20(2), 545–557 (2011)
59.
Shahbaz Khan, F., van de Weijer, J., Vanrell, M.: Top-down color attention for object recognition. In: ICCV, pp. 979–986 (2009)
60.
Shi, J., Malik, J.: Normalized cuts and image segmentation. PAMI 22(8), 888–905 (2000)CrossRef
61.
Shih, F., Cheng, S.: Automatic seeded region growing for color image segmentation. Image Vis. Comput. 23(10), 877–886 (2005)CrossRef
62.
Strandmark, P., Kahl, F.: Parallel and distributed graph cuts by dual decomposition. In: CVPR, pp. 2085–2092 (2010)
63.
Tomasi, C., Manduchi, R.: Bilateral filtering for gray and color images. In: ICCV, pp. 839–846 (1998)
64.
Treisman, A., Gelade, G.: A feature-integration theory of attention. Cognitive Psychol. 12(1), 97–136 (1980)CrossRef
65.
Unnikrishnan, R., Pantofaru, C., Hebert, M.: Toward objective evaluation of image segmentation algorithms. PAMI 29(6), 929–944 (2007)CrossRef
66.
Varga, B., Karacs, K.: High-resolution image segmentation using fully parallel mean shift. EURASIP JASP 111, 2011 (2011)
67.
Wassenberg, J., Middelmann, W., Sanders, P.: An efficient parallel algorithm for graph-based image segmentation. In: CAIP, pp. 1003–1010 (2009)
68.
Wesolkowski, S.: Color image edge detection and segmentation: a comparison of the vector angle and the euclidean distance color similarity measures. PhD thesis, University of Waterloo (1999)
69.
Xiao, C., Liu, M.: Efficient mean-shift clustering using Gaussian KD-tree. Comput. Graph. Forum 29(7), 2065–2073 (2010)MathSciNetCrossRef
70.
Yanai, K., Barnard, K.: Image region entropy: a measure of visualness of web images associated with one concept. In: ACM MM, pp. 419–422 (2005)
71.
Yang, A., Wright, J., Ma, Y., Sastry, S.: Unsupervised segmentation of natural images via lossy data compression. CVIU 110(2), 212–225 (2008)
72.
Yang, C., Duraiswami, R., Dementhon, D., Davis, L.: Mean-shift analysis using quasi-Newton methods. In: ICIP, vol. 3, pp. 447–450 (2003)
73.
Yu, S.: Segmentation induced by scale invariance. In: CVPR, vol. 1, pp. 444–451 (2005)
74.
Zhang, H., Fritts, J., Goldman, S.: Image segmentation evaluation: a survey of unsupervised methods. CVIU 110(2), 260–280 (2008)
75.
Zhang, K., Kwok, J.: Simplifying mixture models through function approximation. IEEE NN 21(4), 644–658 (2010)
76.
Zhao, R., Grosky, W.: Bridging the semantic gap in image retrieval. In: Distributed Multimedia Databases: Techniques and Applications, pp. 14–36 (2001)
77.
Zhou, F., Zhao, Y., Ma, K.-L.: Parallel mean shift for interactive volume segmentation. In: MLMI, pp. 67–75 (2010)
Metadata
Title
Towards a balanced trade-off between speed and accuracy in unsupervised data-driven image segmentation
Authors
Balázs Varga
Kristóf Karacs
Publication date
01-08-2013
Publisher
Springer Berlin Heidelberg
Published in
Machine Vision and Applications / Issue 6/2013
Print ISSN: 0932-8092
Electronic ISSN: 1432-1769
DOI
https://doi.org/10.1007/s00138-013-0503-3

Other articles of this Issue 6/2013

Machine Vision and Applications 6/2013 Go to the issue

Original Paper

Learning class-specific dictionaries for digit recognition from spherical surface of a 3D ball

Original Paper

A combined topological and statistical approach for interactive segmentation of 3D images

Original Paper

A new fusion scheme for multifocus images based on focused pixels detection

Original Paper

Geometric steerable medial maps

Original Paper

Pi-Tag: a fast image-space marker design based on projective invariants

Original Paper

Algorithmic methodologies for FPGA-based vision

Premium Partner

    Image Credits