Rise of Light

dev page: Moritz Willig

---

Home Projects About

DevPage: Moritz Willig

PySNIC

A python only implementation of Superpixels and Polygons using Simple Non-Iterative Clustering (SNIC) by Achanta and Süsstrunk [1].

Algorithm

The SNIC algorithm is based on a globally ordered queue. It selects the pixels one-by-one from the queue and assigns them to a super pixel until no more pixels remain unassigned. The next pixel to be assigned to a superpixel is choosen by selecting the pixel with the lowest metric value to any superpixel. The metric described in the paper is a combination of two factors:

1. The distance between a given pixel and the super pixels center.
2. The difference between the pixels color and the superpixels mean color.

The pixel with the smallest metric distance (first position in the queue), is removed from the queue and assigned to a superpixel. A pixel can be placed into the queue multiple times by different superpixels. Out of these candidate entries, the entry with the smallst metric value will be fetched first out of the queue. All successive entries for an already assigned pixel position will be discarded.
After a pixel got assigned to a superpixel, all its neigbours will be processed. For each neighbouring pixel, its metric value gets calculated, and a (metric_value, pixel_position, superpixel_id)-tuple is inserted back into the queue.

Modifications

The implementation differs from the originally described algorithm to improve performance:

• Adding (or removing) elements to (or from) the queue is costly. Therefore the implementation additionally introduces a distance map. For a given pixel position, this map tracks the minimum distance of any tuple that is currently in the queue. New metric values that are greater than values of already inserted tuples will be discarded.

Code is available at:

PySNIC https://github.com/MoritzWillig/pysnic

References

[1] https://infoscience.epfl.ch/record/227362/
Home Page: https://ivrl.epfl.ch/research-2/research-current/research-superpixels/research-snic_superpixels/

BibTex

@inproceedings{
  snic_cvpr17,
  author = {Achanta, Radhakrishna and Susstrunk, Sabine},
  title = {Superpixels and Polygons using Simple Non-Iterative Clustering},
  booktitle = {IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
  year = {2017}
}

Hosted on uberspace: