AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (38.5 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

FLIC: Fast linear iterative clustering with active search

Nankai University, Tianjin 300350, China.
Cardiff University, Wales, United Kingdom.
Show Author Information

Abstract

In this paper, we reconsider the clustering problem for image over-segmentation from a new per-spective. We propose a novel search algorithm called "active search" which explicitly considers neighbor continuity. Based on this search method, we design a back-and-forth traversal strategy and a joint assignment and update step to speed up the algorithm. Compared to earlier methods, such as simple linear iterative clustering (SLIC) and its variants, which use fixed search regions and perform the assignment and the update steps separately, our novel scheme reduces the number of iterations required for convergence, and also provides better boundaries in the over-segmentation results. Extensive evaluation using the Berkeley segmentation benchmark verifies that our method outperforms competing methods under various evaluation metrics. In particular, our method is fastest, achieving approximately 30 fps for a 481×321 image on a single CPU core. To facilitate further research, our code is made publicly available.

References

[1]
M.-M. Cheng,; Y. Liu,; Q. Hou,; J. Bian,; P. Torr,; S.-M. Hu,; Z. Tu, HFS: Hierarchical feature selection for efficientimage segmentation. In: Computer Vision - ECCV 2016. Lecture Notes in Computer Science, Vol. 9907. B. Leibe,; J. Matas,; N. Sebe,; M. Welling, Eds. Springer Cham, 867-882, 2016.
[2]
Z. Wang,; J. Feng,; S. Yan,; H. Xi, Image class-ificationvia object-aware holistic superpixel selection. IEEE Transactions on Image Processing Vol. 22, No. 11, 4341-4352, 2013.
[3]
D. Hoiem,; A. A. Efros,; M. Hebert, Automatic photopop-up. ACM Transactions on Graphics Vol. 24, No. 3, 577-584, 2005.
[4]
S. Wang,; H. Lu,; F. Yang,; M.-H. Yang, Super-pixeltracking. In: Proceedings of the IEEE Inter-national Conference on ComputerVision, 1323-1330, 2011.
[5]
P. F. Felzenszwalb,; D. P. Huttenlocher, Efficientgraph-based image segmentation. International Journal of Computer Vision Vol. 59, No. 2, 167-181, 2004.
[6]
D. Comaniciu,; P. Meer, Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 24, No. 5, 603-619, 2002.
[7]
L. Vincent,; P. Soille, Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, No. 6, 583-598, 1991.
[8]
J. Shi,; J. Malik, Normalized cuts and image seg-mentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 22, No. 8, 888-905, 2000.
[9]
Y. Boykov,; O. Veksler,; R. Zabih, Fast approxi-mate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 23, No. 11, 1222-1239, 2001.
[10]
O. Veksler,; Y. Boykov,; P. Mehrani, Superpixels and supervoxels in an energy optimization framework. In: Computer Vision - ECCV 2010. Lecture Notes in Computer Science, Vol. 6315. K. Daniilidis,; P. Maragos,; N. Paragios, Eds. Springer Berlin Heidelberg, 211-224, 2010.
[11]
Y. Boykov,; V. Kolmogorov, An experimental-comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 26, No. 9, 1124-1137, 2004.
[12]
V. Kolmogorov,; R. Zabin, What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 26, No. 2, 147-159, 2004.
[13]
A. Levinshtein,; A. Stere,; K. N. Kutulakos,; D. J. Fleet,; S. J. Dickinson,; K. Siddiqi, TurboPixels: Fast superpixels using geometric flows. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 31, No. 12, 2290-2297, 2009.
[14]
S. Osher,; J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics Vol. 79, No. 1, 12-49, 1988.
[15]
M. Van den Bergh,; X. Boix,; G. Roig,; B. de Capitani,; L. Van Gool, SEEDS: Superpixels extracted via energy-drivensampling. In: Computer Vision - ECCV 2012. Lecture Notes in Computer Science, Vol. 7578. A. Fitzgibbon,; S. Lazebnik,; P. Perona,; Y. Sato,; C. Schmid, Eds. Springer Berlin Heidelberg, 13-26, 2012.
[16]
M.-Y. Liu,; O. Tuzel,; S. Ramalingam,; R. Chellappa, Entropy rate superpixel segmentation. In: Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition, 2097-2104, 2011.
[17]
R. Achanta,; A. Shaji,; K. Smith,; A. Lucchi,; P. Fua,; S. Süsstrunk, SLIC superpixels compared to state-of-the-art superpixel methods. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 34, No. 11, 2274-2282, 2012.
[18]
S. P. Lloyd, Least squares quantization in PCM. IEEE Transactions on Information Theory Vol. 28, No. 2, 129-137, 1982.
[19]
P. Wang,; G. Zeng,; R. Gan,; J. Wang,; H. Zha, Structure-sensitive superpixels via geodesic distance. International Journal of Computer Vision Vol. 103, No. 1, 1-21, 2013.
[20]
G. Peyré,; M. Péchaud,; R. Keriven,; L. D. Cohen, Geodesic methods in computer vision and graphics. Foundations and Trends® in Computer Graphics and Vision Vol. 5, Nos. 3-4, 197-397, 2010.
[21]
Y.-J. Liu,; C.-C. Yu,; M.-J. Yu,; Y. He, Manifold SLIC: A fast method to compute content-sensitive superpixels. In: Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition, 651-659, 2016.
[22]
Q. Du,; V. Faber,; M. Gunzburger, Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review Vol. 41, No. 4, 637-676, 1999.
[23]
C. Barnes,; E. Shechtman,; A. Finkelstein,; D. B. Goldman, PatchMatch: A randomized correspondence algorithm forstructural image editing. ACM Transac-tions on Graphics Vol. 28, No. 3, Article No. 24,2009.
[24]
P. Arbelaez,; M. Maire,; C. Fowlkes,; J. Malik, Contourdetection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 5, 898-916, 2011.
[25]
D. Stutz, Superpixelsegmentation: An evaluation. In: Pattern Recognition. Lecture Notes in Computer Science, Vol. 9358. J. Gall,; P. Gehler,; B. Leibe, Eds. Springer Cham, 555-562, 2015.
[26]
R. Mottaghi,; X. Chen,; X. Liu,; N.-G. Cho,; S.-W. Lee,; S. Fidler,; R. Urtasun,; A. Yuille, The role of contextfor object detection and semantic segmentation in the wild. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 891-898, 2014.
[27]
M. Everingham,; L. Van Gool,; C. K. I. Williams,; J. Winn,; A. Zisserman, The PASCAL visual object classes challenge 2010 (VOC2010) results. 2010. Available at http://www.pascalnetwork.org/challenges/VOC/voc2010/workshop/index.html.
[28]
P. Neubert,; P. Protzel, Superpixel benchmark and comparison. In: Proceedings of the Forum Bildverarbeitung, 1-12, 2012.
Computational Visual Media
Pages 333-348
Cite this article:
Zhao J, Bo R, Hou Q, et al. FLIC: Fast linear iterative clustering with active search. Computational Visual Media, 2018, 4(4): 333-348. https://doi.org/10.1007/s41095-018-0123-y

878

Views

29

Downloads

32

Crossref

N/A

Web of Science

41

Scopus

5

CSCD

Altmetrics

Revised: 15 May 2018
Accepted: 31 August 2018
Published: 27 October 2018
© The Author(s) 2018

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return