Documentation - C API

homkermap.h File Reference

#include "generic.h"
#include <math.h>

Go to the source code of this file.

Functions

VlHomogeneousKernelMap * vl_homogeneouskernelmap_new (VlHomogeneousKernelType kernelType, vl_size order, double step)
 Create new map object.
void vl_homogeneouskernelmap_delete (VlHomogeneousKernelMap *self)
 Delete a map object.
void vl_homogeneouskernelmap_evaluate_d (VlHomogeneousKernelMap const *self, double *destination, vl_size stride, double x)
 Evaluate map.
void vl_homogeneouskernelmap_evaluate_f (VlHomogeneousKernelMap const *self, float *destination, vl_size stride, double x)
 Evaluate map.

Detailed Description

Homogeneous kernel map

homkermap.h is an implementation of the homogeneous kernel maps introduced in [1]. Such maps allow linearizing the intersection, Chi2 and other popular additive kernels.

  • [1] A. Vedaldi and A. Zisserman, Efficient Additive Kernels via Explicit Feature Maps, in Proc. CVPR, 2010.

Overview

An homogeneous kernel map computes a finite dimensional linear approximation of an homgeneous kernel such as the intersection kernel or the Chi2 kernel.

Formally, let $ x,y \in \mathbb{R}_+ $ be non-negative scalars. Let $ K(x,y) $ be an homogeneous kernel like the intersection kernel or Chi2 kernels

\[ k_{\mathrm{inters}}(x,y) = \min\{x, y\}, \quad k_{\chi^2}(x,y) = 2 \frac{(x - y)^2}{x+y}. \]

The kernel map $ \Psi(x) $ is a vectorial function such that

\[ k(x,y) \approx \langle \Psi(x), \Psi(y) \rangle. \]

Note that feature maps for the additive versions $ K(\mathbb{x},\mathbb{y}) = \sum_{i=1}^d k(\mathbb{x}_i,\mahtbb{y}_i) $ of such kernels are obtained by stacking the vectors $ (\Psi(\mathbb{x}_1), \dots, \Psi(\mathbb{x}_n)) $.

Usage

First, create VlHomogeneousKernelMap object instance by vl_homogeneouskernelmap_new, then use vl_homogeneouskernelmap_evaluate_d or vl_homogeneouskernelmap_evaluate_f to compute $ \Psi(x) $ for each scalar x that needs to be expanded. Finally, call vl_homogeneouskernelmap_delete to delete the map object.

vl_homogeneouskernelmap_new requires the kernel type (see VlHomogeneousKernelType), th approximation order order and the sampling step L. The approximation order trades off the quality and dimensionality of the approximation. The resulting feature map $ \Psi(x) $ is d*(2*order+1) dimensional.

The sampling step step should be tuned to optimize the representation for the range of logarithmic ratios $ | \log(x / y) | $ for which the kernel $ K(x,y) $ needs to be accurately represented (note that for large values of the ratio the kernel is very small in any case, so the approximation quality becomes less important). While the step should be tuned by numerical evaluation, values in the range (.25, .5) usually work well in applications. See [1] for details.

Technical details

The code uses the expressions given in [1] to compute in closed form the maps $ \Psi(x) $ for the Chi2 and intersection kernels. For efficiency reasons, it tabulates $ \Psi(x) $ when the map object is created.

The table stores $ \Psi(x) \in \mathbb{R}^{2n+1} $ for $ x \geq 0 $ sampled logarithmically. In particular, x is decomposed as 

   x = mantissa * (2**exponent),
   minExponent <= exponent <= maxExponent,
   1 <= matnissa < 2.

Each octave is further subdivided in numSubdivisions sublevels.

When the map is evaluated, x is decomposed in exponent and mantissa, and the result is computed by bilinear interpolation from the appropriate table entries.

Definition in file homkermap.h.

Function Documentation

void vl_homogeneouskernelmap_delete ( VlHomogeneousKernelMap *  self  ) 
Parameters:
self map object. The function deletes the specified map object.

Definition at line 213 of file homkermap.c.

References vl_free().

vl_homogeneouskernelmap_evaluate_d ( VlHomogeneousKernelMap const *  self,
double *  destination,
vl_size  stride,
double  x 
)
Parameters:
self map object.
destination output buffer.
stride stride of the output buffer.
x value to expand.

The function evaluates the feature map on x and stores the resulting 2*order+1 dimensional vector to destination[0], destination[stride], destination[2*stride], ....

vl_homogeneouskernelmap_evaluate_f ( VlHomogeneousKernelMap const *  self,
float *  destination,
vl_size  stride,
double  x 
)
Parameters:
self map object.
destination output buffer.
stride stride of the output buffer.
x value to expand.

The function evaluates the feature map on x and stores the resulting 2*order+1 dimensional vector to destination[0], destination[stride], destination[2*stride], ....

VlHomogeneousKernelMap* vl_homogeneouskernelmap_new ( VlHomogeneousKernelType  kernelType,
vl_size  order,
double  step 
)
Parameters:
kernelType type of homogeneous kernel.
order approximation order.
step sampling step.
Returns:
the new kernel map, or NULL if memory is exhausted.

The function intializes a new homogeneous kernel map for the specified kernel type, approximation order, and sampling step. See Overview for details.

Definition at line 119 of file homkermap.c.

References vl_free(), vl_malloc(), and VL_PI.