Documentation - C API

quickshift.h File Reference

Quick shift image segmentation. More...

#include "generic.h"
#include "mathop.h"

Go to the source code of this file.

Data Structures

struct  _VlQS
 quick shift results More...

Defines

#define VL_QS_INF   VL_INFINITY_D
 quick shift infinity constant

Typedefs

typedef double vl_qs_type
 quick shift datatype
typedef struct _VlQS VlQS
 quick shift results

Functions

Create and destroy

VlQS * vl_quickshift_new (vl_qs_type const *im, int height, int width, int channels)
 Create a quick shift object.
void vl_quickshift_delete (VlQS *q)
 Delete quick shift object.
Process data

void vl_quickshift_process (VlQS *q)
 Create a quick shift objet.
Retrieve data and parameters

vl_qs_type vl_quickshift_get_max_dist (VlQS const *q)
 Get tau.
vl_qs_type vl_quickshift_get_kernel_size (VlQS const *q)
 Get sigma.
vl_bool vl_quickshift_get_medoid (VlQS const *q)
 Get medoid.
int * vl_quickshift_get_parents (VlQS const *q)
 Get parents.
vl_qs_type * vl_quickshift_get_dists (VlQS const *q)
 Get dists.
vl_qs_type * vl_quickshift_get_density (VlQS const *q)
 Get density.
Set parameters

void vl_quickshift_set_max_dist (VlQS *q, vl_qs_type tau)
 Set max distance.
void vl_quickshift_set_kernel_size (VlQS *q, vl_qs_type sigma)
 Set sigma.
void vl_quickshift_set_medoid (VlQS *q, vl_bool medoid)
 Set medoid.

Detailed Description

Author:
Brian Fulkerson
Andrea Vedaldi

Overview

Quick shift [1] is a fast mode seeking algorithm, similar to mean shift. The algorithm segments a color image (or any image with more than one component) by identifying clusters of pixels in the joint spatial and color dimensions. Segments are local (superpixels) and can be used as a basis for further processing.

Given an image, the algorithm calculates a forest of pixels whose branches are labeled with a distance value (vl_quickshift_get_parents, vl_quickshift_get_dists). This specifies a hierarchical segmentation of the image, with segments corresponding to subtrees. Useful superpixels can be identified by cutting the branches whose distance label is above a given threshold (the threshold can be either fixed by hand, or determined by cross validation).

Parameter influencing the algorithm are:

  • Kernel size. The pixel density and its modes are estimated by using a Parzen window estimator with a Gaussian kernel of the specified size (vl_quickshift_set_kernel_size). The larger the size, the larger the neighborhoods of pixels considered.
  • Maximum distance. This (vl_set_max_dist) is the maximum distance between two pixels that the algorithm considers when building the forest. In principle, it can be infinity (so that a tree is returned), but in practice it is much faster to consider only relatively small distances (the maximum distance can be set to a small multiple of the kernel size).

[1] A. Vedaldi and S. Soatto. “Quick Shift and Kernel Methods for Mode Seeking”, in Proc. ECCV, 2008.

Usage

Technical details

For each pixel (x,y), quick shift regards $ (x,y,I(x,y)) $ as a sample from a d + 2 dimensional vector space. It then calculates the Parzen density estimate (with a Gaussian kernel of standard deviation $ \sigma $)

\[ E(x,y) = P(x,y,I(x,y)) = \sum_{x'y'} \frac{1}{(2\pi\sigma)^{d+2}} \exp \left( -\frac{1}{2\sigma^2} \left[ \begin{array}{c} x - x' \\ y - y' \\ I(x,y) - I(x',y') \\ \end{array} \right] \right) \]

Then quick shift construct a tree connecting each image pixel to its nearest neighbor which has greater density value. Formally, write $ (x',y') >_P (x,y) $ if, and only if,

\[ P(x',y',I(x',y')) > P(x,y,I(x,y))}. \]

Each pixel (x, y) is connected to the closest higher density pixel parent(x, y) that achieves the minimum distance in

\[ \mathrm{dist}(x,y) = \mathrm{min}_{(x',y') > P(x,y)} \left( (x - x')^2 + (y - y')^2 + \| I(x,y) - I(x',y') \|_2^2 \right). \]

Author:
Andrea Vedaldi
Brian Fulkerson

Definition in file quickshift.h.

Typedef Documentation

typedef struct _VlQS VlQS

------------------------------------------------------------------ This implements quick shift mode seeking.

Function Documentation

void vl_quickshift_delete ( VlQS *  q  ) 

-----------------------------------------------------------------

Parameters:
q quick shift object.

Definition at line 448 of file quickshift.c.

References vl_free().

vl_qs_type * vl_quickshift_get_density ( VlQS const *  q  )  [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
Returns:
the estimate of the density at each pixel.

Definition at line 164 of file quickshift.h.

vl_qs_type * vl_quickshift_get_dists ( VlQS const *  q  )  [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
Returns:
for each pixel, the distance in feature space to the pixel that is its parent in the quick shift tree.

Definition at line 152 of file quickshift.h.

vl_qs_type vl_quickshift_get_kernel_size ( VlQS const *  q  )  [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
Returns:
the standard deviation of the kernel used in the Parzen density estimate.

Definition at line 113 of file quickshift.h.

vl_qs_type vl_quickshift_get_max_dist ( VlQS const *  q  )  [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
Returns:
the maximum distance in the feature space between nodes in the quick shift tree.

Definition at line 100 of file quickshift.h.

vl_bool vl_quickshift_get_medoid ( VlQS const *  q  )  [inline]

------------------------------------------------------------------

Parameters:
q quick Shift object.
Returns:
true if medoid shift is used instead of quick shift.

Definition at line 125 of file quickshift.h.

int * vl_quickshift_get_parents ( VlQS const *  q  )  [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
Returns:
a height x width matrix containing linearized links to the parents in the quick shift tree. If there is no parent, the parent will be set to the index of the node.

Definition at line 139 of file quickshift.h.

VlQS* vl_quickshift_new ( vl_qs_type const *  image,
int  height,
int  width,
int  channels 
)

-----------------------------------------------------------------

Parameters:
image 
height 
width 
channels 
Returns:
New quick shift object.

Definition at line 223 of file quickshift.c.

References _VlQS::channels, _VlQS::height, _VlQS::image, vl_calloc(), VL_FALSE, vl_malloc(), VL_MAX, and _VlQS::width.

void vl_quickshift_process ( VlQS *  q  ) 

-----------------------------------------------------------------

Parameters:
q quick shift object.

Definition at line 250 of file quickshift.c.

References _VlQS::channels, _VlQS::height, _VlQS::image, vl_calloc(), vl_free(), VL_MAX, VL_MIN, VL_QS_INF, vl_quickshift_distance(), vl_quickshift_inner(), and _VlQS::width.

void vl_quickshift_set_kernel_size ( VlQS *  q,
vl_qs_type  sigma 
) [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
sigma standard deviation of the kernel used in the Parzen density estimate.

Definition at line 177 of file quickshift.h.

void vl_quickshift_set_max_dist ( VlQS *  q,
vl_qs_type  tau 
) [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
tau the maximum distance in the feature space between nodes in the quick shift tree.

Definition at line 190 of file quickshift.h.

void vl_quickshift_set_medoid ( VlQS *  q,
vl_bool  medoid 
) [inline]

------------------------------------------------------------------

Parameters:
q quick shift object.
medoid true to use kernelized medoid shift, false (default) uses quick shift.

Definition at line 203 of file quickshift.h.