# DAVIDSTUTZ

## Implementation of Felzenszwalb and Huttenlocher’s Graph-Based Image Segmentation

This article presents an implementation of Felzenszwalb and Huttenlocher’s  graph-based image segmentation algorithm. The implementation is compared to the original implementation by Felzenszwalb in terms of Boundary Recall, Undersegmentation Error and Explained Variation, as used for evaluating superpixel algorithms. In addition, qualitative results are provided. The implementation is publicly available on GitHub.

### Introduction

Felzenszwalb and Huttenlocher's  graph-based image segmentation algorithm is a standard tool in computer vision, both because of the simple algorithm and the easy-to-use and well-programmed implementation provided by Felzenszwalb. Recently, the algorithm has frequently been used as pre-processing tool to generate oversegmentations or so-called superpixels ‐ groups of pixels perceptually belonging together. In this line of work, the algorithm is frequently used as baseline for state-of-the-art superpixel algorithms.

The algorithm has also been extended to video . In the course of my studies, I developed an implementation of the algorithm for video segmentation, as can be found on GitHub. As side product, the implementation can easily be adapted for image segmentation. The code is also available on GitHub:

Compared to the original implementation, the presented implementation tries to improve connectivity of the generated segments/superpixels. The underlying reasoning is that connectivity is an essential requirement of superpixel algorithms and has significant influence on evaluation metrics.

### Algorithm

The algorithm is briefly described below (click to collpse):

After introducing SEEDS  and SLIC , this article focusses on another approach to superpixel segmentation proposed by Felzenswalb & Huttenlocher. The procedure is summarized in algorithm 1 and based on the following definitions. Given an image $I$, $G = (V, E)$ is the graph with nodes corresponding to pixels, and edges between adjacent pixels. Each edge $(n,m) \in E$ is assigned a weight $w_{n,m} = \|I(n) - I(m)\|_2$. Then, for subsets $A,B \subseteq V$ we define $MST(A)$ to be the minimum spanning tree of $A$ and

$Int(A) = max_{n,m \in MST(A)} \{w_{n,m}\}$,

$MInt(A,B) = min\{Int(A) + \frac{\tau}{|A|}, Int(B) + \frac{\tau}{|B|}\}$.

where $\tau$ is a threshold parameter and $MInt(A,B)$ is called the minimum internal difference between components $A$ and $B$. Starting from an initial superpixel segmentation where each pixel forms its own superpixel the algorithm processes all edges in order of increasing edge weight. Whenever an edge connects two different superpixels, these are merged if the edge weight is small compared to the minimum internal difference.

function fh(
$G = (V,E)$ // Undirected, weighted graph.
)
sort $E$ by increasing edge weight
let $S$ be the initial superpixel segmentation
for $k = 1,\ldots,|E|$
let $(n,m)$ be the $k^{\text{th}}$ edge
if the edge connects different superpixels $S_i,S_j \in S$
if $w_{n,m}$ is sufficiently small compared to $MInt(S_i,S_j)$
merge superpixels $S_i$ and $S_j$
return $S$

Algorithm 1: The superpixel algorithm proposed by Felzenswalb & Huttenlocher.

The original implementation can be found on Felzenswalb's website. Generated superpixel segmentations can be found in figure 1.

•  R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Süsstrunk. SLIC superpixels. Technical report, École Polytechnique Fédérale de Lausanne, 2010.
•  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, pages 13–26, 2012.
•  P. Arbeláez, M. Maire, C. Fowlkes, J. Malik. Contour detection and hierarchical image segmentation. Transactions on Pattern Analysis and Machine Intelligence, volume 33, number 5, pages 898–916, 2011.

### Implementation

The provided implementation can easily be installed using CMake. On Ubuntu, this might look as follows:

$git clone https://github.com/davidstutz/graph-based-image-segmentation.git$ cd graph-based-image-segmentation
$mkdir build$ cd build
$cmake ..$ make


The implementation then provided an easy-to-use command line tool to run the algorithm on a folder containing one or several images:

### References

•  P. F. Felzenswalb, D. P. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision 59 (2) (2004) 167–181.
•  M. Grundmann, V. Kwatra, M. Han, I. Essa. Efficient Hierarchical Graph Based Video Segmentation. CVPR, 2010.
•  P. Arbeláez, M. Maire, C. Fowlkes, J. Malik. Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 33 (5), 2011.
•  P. Neubert, P. Protzel. Superpixel benchmark and comparison. In: Forum Bildverarbeitung, 2012.
•  A. P. Moore, S. J. D. Prince, J. Warrell, U. Mohammed, G. Jones. Superpixel lattices. IEEE Conference on Computer Vision and Pattern Recognition, 2008.