IAM

Check out our CVPR'18 paper on weakly-supervised 3D shape completion — and let me know your opinion! @david_stutz

ARTICLE

An Up-to-Date List of Superpixel Algorithms

Recently, I started reviewing for different conferences and journals. Based on my previous work, specifically the Superpixel Benchmark, I mostly reviewed papers on superpixel algorithms. For most of these algorithms, and additional related work, I made notes; in this article I want to keep track of the algorithms and benchmarks. The goal is to have an up-to-date list of superpixel algorithms and their implementations.

Superpixel Algorithms

The below table is intended to be a comprehensive list of superpixel algorithms that have been introduced and used so far. This means that I am doing my best to regularly update this list; however, it is probably impossible to read every paper in every conference, journal or from ArXiv that proposes a new superpixel algorithm or introduced a novel variant of an existing one. Therefore, feel free to point me towards new papers.

This list is supposed to be as comprehensive as possible; however, feel free to point me to papers or implementations in the comments.

For some of the papers, I also provide some reading notes.

Benchmarks
AlgorithmReferenceImpl.WebNotes[][][][][][][][]
W[], 1992C/C++Code
EAMS[], 2002MatLab/CCode
NC[], 2003MatLab/CCodeNotes
FH[], 2004C/C++CodeNotes
reFH—"—C/C++Code
RW[][], 2004MatLab/CCode
SL[], 2008
QS[], 2008MatLab/CCodeNotes
PF[], 2009JavaCode
TP[], 2009MatLab/CCodeNotes
[], 2009
[], 2009
CIS[], 2010C/C++CodeNotes
SLIC[][], 2010C/C++CodeNotes
vlSLIC—"—C/C++Code
[], 2010
CRS[][], 2011C/C++CodeNotes
ERS[], 2011C/C++CodeNotes
PB[], 2011C/C++CodeNotes
[], 2011
[], 2011
DASP[], 2012C/C++Code
SEEDS[], 2012C/C++CodeNotes
reSEEDS—"—C/C++Code
TPS[][], 2012MatLab/CCodeNotes
VC[], 2012C/C++Code
[], 2012
CCS[][], 2013C/C++Code
VCCS[], 2013C/C++Code
[], 2013
[], 2013
[], 2013
[], 2013
CW[], 2014C/C++Code
ERGC[][], 2014C/C++Code
MSS[], 2014C/C++
preSLIC[], 2014C/C++Code
WP[][], 2014PythonCode
LRW[], 2014
[], 2014
[], 2014
[], 2014
[], 2014
[], 2014Notes
ETPS[], 2015C/C++Code
LSC[], 2015C/C++Code
POISE[], 2015MatLab/CCode
SEAW[], 2015MatLab/CCode
[], 2015
[], 2015
[], 2015Notes
[], 2016
[], 2016Notes
[], 2016Notes
[], 2016Notes
[], 2016Notes
SCALP[], 2016Notes
[], 2017Notes
[], 2017Notes
[], 2017Notes
[], 2018CodeNotes

Benchmarks

There are some benchmarks considering a subset of the above algorithms — including my own Superpixel Benchmark. These papers are listed below; note that the above table of superpixel algorithms also indicates which algorithms are evaluated in the respective papers:

ReferenceCommentsWebpageNotes
[], 2011Evaluates Undersegmentation Error, Boundary Recall and runtime; also evaluates superpixel algorithms as pre-processing task for image segmentation.
[], 2012Proposes Corrected Undersegmentation Error; evaluates Undersegmentation Error, Boundary Recall and Robustness against shift, scale, rotation, shear.Project Page
[], 2013Evaluates superpixel segmentations in video; propose Motion Undersegmentation Error and Motion Discontinuity Error.Project Page
[], 2012Introduces compactness metric (CO); evaluates CO only.
[], 2015Evaluates Undersegmentation Error, Boundary Recall and runtime; includes parameter optimization; evaluates on NYUV2 (in 3D, as well); proposes more efficient and improved implementation of SEEDS.Project Page
[], 2016Evaluates (Corrected) Undersegmentation Error, Boundary Recall, Explained Variation, Achievable Segmentation Accuracy and runtime; enforces connectivity and includes parameter optimization; also considers maximum/minimum and standard deviation of metrics and deviation from the desired number of superpixels; evaluates robustness against geometric transformations and noise; evaluates on 5 datasets.Project Page
[], 2017Introduces regularity metric (RI); evaluates Boundary Recall, - Precision and F1 Measure, Compactness, Undersegmentation Error, Sum-of-Squared Error and Explained Variation and runtime; and provide a code library.Code
[], 2017Introduce regularity metric; evaluates regularity only.Notes

References

  • [] F. Meyer. Color image segmentation. International Conference on Image Processing and its Applications, 1992, pp. 303-306.
  • [] D. Comaniciu, P. Meer. Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (5) (2002) 603–619.
  • [] X. Ren, J. Malik. Learning a classification model for segmentation. International Conference on Computer Vision, 2003, pp. 10–17.
  • [] P. F. Felzenswalb, D. P. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision 59 (2) (2004) 167–181.
  • [] L. Grady, G. Funka-Lea. Multi-label image segmentation for medical applications based on graph-theoretic electrical potentials. ECCV Workshops on Computer Vision and Mathematical Methods in Medical and Biomedical Image Analysis, 2004, pp. 230–245.
  • [] L. Grady. Random walks for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 28 (11) (2006) 1768–1783.
  • [] A. Vedaldi, S. Soatto. Quick shift and kernel methods for mode seeking. European Conference on Computer Vision, Vol. 5305, 2008, pp. 705–718.
  • [] F. Drucker, J. MacCormick. Fast superpixels for video analysis. Workshop on Motion and Video Computing, 2009, pp. 1–8.
  • [] 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 31 (12) (2009) 2290–2297.
  • [] O. Veksler, Y. Boykov, P. Mehrani. Superpixels and supervoxels in an energy optimization framework. European Conference on Computer Vision, Vol. 6315, 2010, pp. 211–224.
  • [] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Susstrunk. SLIC superpixels. Tech. rep., Ecole Polytechnique Federale de Lausanne (2010).
  • [] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Susstrunk. SLIC superpixels compared to state-of-the-art superpixel methods. IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (11) (2012) 2274–2281.
  • [] R. Mester, C. Conrad, A. Guevara. Multichannel segmentation using contour relaxation: Fast super-pixels and temporal propagation. Scandinavian Conference Image Analysis, 2011, pp. 250–261.
  • [] C. Conrad, M. Mertz, R. Mester, Contour-relaxed superpixels. Energy Minimization Methods. Computer Vision and Pattern Recognition, 2013, pp. 280–293.
  • [] M. Y. Lui, O. Tuzel, S. Ramalingam, R. Chellappa. Entropy rate superpixel segmentation. IEEE Conference on Computer Vision and Pattern Recognition, 2011, pp. 2097–2104.
  • [] Y. Zhang, R. Hartley, J. Mashford, S. Burn. Superpixels via pseudo-boolean optimization. International Conference on Computer Vision, 2011, pp. 1387–1394.
  • [] D. Weikersdorfer, D. Gossow, M. Beetz. Depth-adaptive superpixels. International Conference on Pattern Recognition, 2012, pp. 2087–2090.
  • [] M. van den Bergh, X. Boix, G. Roig, B. de Capitani, L. van Gool. SEEDS: Superpixels extracted via energy-driven sampling. European Conference on Computer Vision, Vol. 7578, 2012, pp. 13–26.
  • [] D. Tang, H. Fu, X. Cao. Topology preserved regular superpixel. IEEE International Conference on Multimedia and Expo, 2012, pp. 765–768.
  • [] H. Fu, X. Cao, D. Tang, Y. Han, D. Xu. Regularity preserved superpixels and supervoxels. IEEE Transactions on Multimedia 16 (4) (2014) 1165–1175.
  • [] J. Wang, X. Wang. VCells: Simple and efficient superpixels using edge-weighted centroidal voronoi tessellations. IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (6)(2012) 1241–1247.
  • [] H. E. Tasli, C. Cigla, T. Gevers, A. A. Alatan. Super pixel extraction via convexity induced boundary adaptation. IEEE International Conference on Multimedia and Expo, 2013, pp. 1–6.
  • [] H. E. Tasli, C. Cigla, A. A. Alatan. Convexity constrained efficient superpixel and supervoxel extraction. Signal Processing: Image Communication 33 (2015) 71–85.
  • [] J. Papon, A. Abramov, M. Schoeler, F. Wörgötter. Voxel cloud connectivity segmentation - supervoxels for point clouds. IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 2027–2034.
  • [] P. Neubert, P. Protzel. Compact watershed and preemptive SLIC: on improving trade-offs of superpixel segmentation algorithms. International Conference on Pattern Recognition, 2014, pp. 996–1001.
  • [] P. Buyssens, I. Gardin, S. Ruan. Eikonal based region growing for superpixels generation: Application to semi-supervised real time organ segmentation in CT images. Innovation and Research in BioMedical Engineering 35 (1) (2014) 20–26.
  • [] P. Buyssens, M. Toutain, A. Elmoataz, O. Lézoray. Eikonal-based vertices growing and iterative seeding for efficient graph-based segmentation. International Conference on Image Processing, 2014, pp. 4368–4372
  • [] W. Benesova, M. Kottman. Fast superpixel segmentation using morphological processing. Conference on Machine Vision and Machine Learning, 2014.
  • [] V. Machairas, E. Decencière, T. Walter. Waterpixels: Superpixels based on the watershed transformation. International Conference on Image Processing, 2014, pp. 4343–4347.
  • [] V. Machairas, M. Faessel, D. Cardenas-Pena, T. Chabardes, T. Walter, E. Decencière. Waterpixels. Transactions on Image Processing 24 (11) (2015) 3707–3716.
  • [] J. Yao, M. Boben, S. Fidler, R. Urtasun. Real-time coarse-to-fine topologically preserving segmentation. IEEE Conference on Computer Vision and Pattern Recognition, 2015, pp. 2947–2955.
  • [] Z. Li, J. Chen. Superpixel segmentation using linear spectral clustering. IEEE Conference on Computer Vision and Pattern Recognition, 2015, pp. 1356–1363.
  • [] J. M. R. A. Humayun, F. Li. The middle child problem: Revisiting parametric min-cut and seeds for object proposals. International Conference on Computer Vision, 2015, pp. 1600–1608.
  • [] J. Strassburg, R. Grzeszick, L. Rothacker, G. A. Fink. On the influence of superpixel methods for image parsing. International Conference on Computer Vision Theory and Application, 2015, pp. 518–527.
  • [] David Stutz, Alexander Hermans, Bastian Leibe. Superpixels: An Evaluation of the State-of-the-Art. CoRR abs/1612.01601 (2016)
  • [] David Stutz. Superpixel Segmentation: An Evaluation. GCPR 2015: 555-562
  • [] C. Rohkohl, K. Engel, Efficient image segmentation using pairwise pixel similarities, in: DAGM Annual Pattern Recognition Symposium, 2007, pp. 254–263.
  • [] D. Engel, L. Spinello, R. Triebel, R. Siegwart, H. H. B ̈ulthoff, C. Curio, Medial features for superpixel segmentation, in: IAPR International Conference on Machine Vision Applications, 2009, pp. 248–252.
  • [] A. Ducournau, S. Rital, A. Bretto, B. Laget, Hypergraph coarsening for image superpixelization, in: International Symposium on I/V Communications and Mobile Network, 2010, pp. 1–4.
  • [] G. Zeng, P. Wang, J. Wang, R. Gan, H. Zha, Structure-sensitive superpixels via geodesic distance, in: International Conference on Computer Vision, 2011, pp. 447–454.
  • [] F. Perbet, A. Maki, Homogeneous superpixels from random walks, in: Machine Vision and Applications, Conference on, 2011, pp. 26–30.
  • [] Y. Du, J. Shen, X. Yu, D. Wang, Superpixels using random walker, in: IEEE Global High Tech Congress on Electronics, 2012, pp. 62–63.
  • [] J. Yang, Z. Gan, X. Gui, K. Li, C. Hou, 3-d geometry enhanced superpixels for RGB-D data, in: Pacific-Rim Conference on Multimedia, 2013, pp. 35–46.
  • [] J. Zhang, C. Kan, A. G. Schwing, R. Urtasun, Estimating the 3d layout of indoor scenes and its clutter from depth sensors, in: International Conference on Computer Vision, 2013, pp. 1273–1280.
  • [] Z. Ren, G. Shakhnarovich, Image segmentation by cascaded region agglomeration, in: IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 2011–2018.
  • [] K.-S. Kim, D. Zhang, M.-C. Kang, S.-J. Ko, Improved simple linear iterative clustering superpixels, in: International Symposium on Consumer Electronics, 2013, pp. 259–260.
  • [] J. Shen, Y. Du, W. Wang, X. Li, Lazy random walks for superpixel segmentation, Transactions on Image Processing 23 (4) (2014) 1451–1462.
  • [] P. Morerio, L. Marcenaro, C. S. Regazzoni, A generative superpixel method, in: International Conference on Information Fusion, 2014, pp. 1–7.
  • [] P. Siva, A. Wong, Grid seams: A fast superpixel algorithm for real-time applications, in: Computer and Robot Vision, Conference on, 2014, pp. 127–134.
  • [] S. R. S. P. Malladi, S. Ram, J. J. Rodriguez, Superpixels using morphology for rock image segmentation, in: IEEE Southwest Symposium on Image Analysis and Interpretation, 2014, pp. 145–148.
  • [] O. Freifeld, Y. Li, J. W. Fisher, A fast method for inferring high-quality simply-connected superpixels, in: International Conference on Image Processing, 2015, pp. 2184–2188.
  • [] J. Lv, An improved slic superpixels using reciprocal nearest neighbor clustering, International Journal of Signal Processing, Image Processing and Pattern Recognition 8 (5) (2015) 239–248.
  • [] Yong-Jin Liu, Cheng-Chi Yu, Minjing Yu, Ying He. Manifold SLIC: A Fast Method to Compute Content-Sensitive Superpixels. CVPR, pages 651-659, 2016.
  • [] Alastair Philip Moore, Simon J. D. Prince, Jonathan Warrell, Umar Mohammed, Graham Jones. Scene shape priors for superpixel segmentation. ICCV, pages 771-778, 2009.
  • [] Yurui Xie, Linfeng Xu, Zhengning Wang. Automated co-superpixel generation via graph matching. Signal, Image and Video Processing 8(4): 753-763, 2014.
  • [] Se-Ho Lee, Won-Dong Jang, Chang-Su Kim. Contour-Constrained Superpixels for Image and Video Processing. CVPR, pages 5863-5871, 2017.
  • [] Yinlin Hu, Yunsong Li, Rui Song, Peng Rao, Yangli Wang. Minimum barrier superpixel segmentation. Image and Vision Computing, Volume 70, 2018.
  • [] Radhakrishna Achanta, Sabine Süsstrunk. Superpixels and Polygons Using Simple Non-iterative Clustering. CVPR, 2017.
  • [] Imanol Luengo, Mark Basham, Andrew P. French. SMURFS: Superpixels from Multi-scale Refinement of Super-regions. BMVC, 2016.
  • [] Chun-Rong Huang, Wei-An Wang, Szu-Yu Lin, Yen-Yu Lin. USEQ: Ultra-fast superpixel extraction via quantization. ICPR, 2016.
  • [] Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis. SCALP: Superpixels with Contour Adherence using Linear Path. ICPR, 2016.
  • [] Jia-Xin Zhao, Ren Bo, Qibin Hou, Ming-Ming Cheng. FLIC: Fast Linear Iterative Clustering with Active Search. CoRR, 2016.
  • [] Liuyun Duan, Florent Lafarge. Image partitioning into convex polygons. CVPR, 2015.
  • [] Y. J. Liu, M. Yu, B. J. Li and Y. He. Intrinsic Manifold SLIC: A Simple and Efficient Method for Computing Content-Sensitive Superpixels. PAMI, 2017.
  • [] Linfeng Xu, Liaoyuan Zeng, Zhengning Wang. Saliency-based superpixels. Signal, Image and Video Processing, 2014.
  • [] Jianbing Shen, Xiaopeng Hao, Zhiyuan Liang, Yu Liu, Wenguan Wang, Ling Shao. Real-Time Superpixel Segmentation by DBSCAN Clustering Algorithm. TIP, 2016.
  • [] A. P. Moore, S. J. D. Prince, J. Warrell, U. Mohammed, and G. Jones. Superpixel Lattices. In Proc. Computer Vision and Pattern Recognition, pages 1–8, 2008.
  • [] A. Schick, M. Fischer, R. Stiefelhagen, Measuring and evaluating the compactness of superpixels, in: International Conference on Pattern Recognition, 2012, pp. 930–934.
  • [] P. Neubert, P. Protzel, Superpixel benchmark and comparison, in: Forum Bildverarbeitung, 2012.
  • [] P. Neubert, P. Protzel, Evaluating superpixels in video. Metrics beyond figure-ground segmentation, in: British Machine Vision Conference, 2013.
  • [] M. Wang, X. Liu, Y. Gao, X. Ma, N. Q. Soomro. Superpixel segmentation: A benchmark. Sig. Proc.: Image Comm. 56: 28-39, 2017.
  • [] Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis. Robust Shape Regularity Criteria for Superpixel Evaluation. ICIP, 2017.

What is your opinion on this article? Did you find it interesting or useful? Let me know your thoughts in the comments below or get in touch with me:

@david_stutz